Questions tagged [coding-theory]
The mathematical theory of codes, as used in communication, data compression, and cryptography.
125
questions
0
votes
1
answer
58
views
Detecting Erroneous Corrections
A block code $C$, with minimum distance $d$ can be used to:
Detect $d - 1$ errors
Correct $\lfloor\frac{d - 1}{2}\rfloor$ errors
However, the above usually assumes that the number of errors that are ...
- 1
2
votes
0
answers
64
views
The existence of (non-rectangular) two dimensional Gray code
A Gray code consists of $n$-bit distinct strings $s_1,s_2, \ldots,s_N$ such that each $s_i$ and $s_{i+1}$ differs by one bit.
For example: $000, 001, 010, 011, 111, 110, 101, 100$.
It is known that we ...
0
votes
0
answers
37
views
How to turn algorithm for decoding into one for a small weight codeword?
I keep seeing (in the coding theory literature) that if I have an algorithm for decoding in a binary linear code, I can turn it into one for finding codewords of small weight. How?
Ideally, without ...
0
votes
0
answers
86
views
Existence of a family of size 2^Ω(n) of subsets of {1,...,n} each of cardinality n/4 where two subsets have at most n/8 elements in common
Let $\mathcal{G}$ be a family of $t=2^{\Omega(n)}$ subsets of $N=\{1,2,...,n\}$, each of cardinality $n / 4$ so that any two distinct members of $\mathcal{G}$ have at most $n / 8$ elements in common.
...
- 101
3
votes
1
answer
178
views
Theorem of Sudan, Trevisan and Vadhan about list-decoding
My question is about the following result about list-decoding of
Sudan, Trevisan and Vadhan.
(The formulation is taken from Shuichi Hirahara's paper.)
I do not understand how this is possible. I ...
- 1,973
1
vote
0
answers
20
views
Coloring the $k$-deletion graph “constructively”
For $n,k\ge 1$, we define the graph $D_{n,k}$ to have vertex set $\{0,1\}^n$, with distinct $x,y$ being adjacent if $LCS(x,y)\ge n-k$.
My question is: fixing $k>1$, does there exist some $C=C_k$ ...
- 603
2
votes
0
answers
180
views
On the number of optimal prefix-free binary codes [closed]
Let $T$ be a text of length $L$ containing the symbols $$\mathcal{A}=\{a_1, a_2, \ldots, a_n\},$$ where each symbol appears at least once and no other symbol appears in $T$.
Define the weights $$\...
- 21
0
votes
0
answers
58
views
Is there a name/terminology for binary codes with evenly spaced number of ones?
I am generating a random binary matrix $A \in \{0, 1\}^{m \times n}$ with the number of ones in each row set to evenly spaced numbers from an interval. For example, if $n=50$, the number of ones for $...
- 109
1
vote
1
answer
88
views
Do Programming Languages classify as Language? [closed]
Much classification work has been done classifying programming languages, however do programming languages classify as languages themselves.
Languages as "the primary means of communication",...
5
votes
1
answer
210
views
Are all linear-rate and -distance classical linear codes expanding?
Consider a LDPC linear code defined as $\ker H$ for a $O(1)$ row- and column-sparse matrix $H \in \{0,1\}^{n \times r}$ with independent rows. Assume the code is linear-rate meaning $n - r = \Omega(n)$...
1
vote
1
answer
88
views
Code indistinguishability assumption for Code based cryptography (in special cases)
Cryptosystems that are based on error correcting codes are often based with hardness of the two problem.
Computational syndrome decoding is hard
Indistinguishability Assumption (IA): Distinguishing ...
- 387
3
votes
1
answer
166
views
Maximal uniquely decodable codes
This question is about the Kraft-McMillan inequality:
If $w_1,\ldots,w_n$ are words of lengths $l_1,\ldots,l_n$ from an alphabet with $r$ letters, which form a uniquely decodable code, then
$$ \sum_{i=...
- 33
2
votes
0
answers
86
views
Approximate (in hamming distance) subset representation
Let us have a set $S$ and a subset $T \subseteq S$. I want to find an approximate representation of $T$, i.e. I want to represent (exactly) a set $T'$ that is close to $T$. That is, I want the ...
- 630
0
votes
0
answers
145
views
Is the following graph an expander graph?
Let's say we have the following bipartite-graph, denoted $G=(L,R,E)$:
It has the following adjacency matrix:
I am having problems decoding a received word from what I was told is an expander code ...
6
votes
2
answers
191
views
Reference request for linear algebra over GF(2)
I have been looking for materials on the linear algebra over $GF(2)$ but so far I haven't found any substantial textbooks or notes on this subject. In fact in one of the notes I found the introduction ...
- 260
1
vote
1
answer
73
views
Non-random errors with a Reed Solomon code
If I have a RS code, say [46, 16, 31], then I have a guaranteed error correction up to 15 symbols. I have no idea if it matters, but the code I have in front of me ...
- 121
2
votes
2
answers
291
views
Information and Coding Theory Texts
I am coming from a pure mathematics (in analysis) background and am curious to learn some information and coding theory. I am after some recommendations on texts. Due to my personal background I am ...
- 121
1
vote
0
answers
77
views
BCH codes and polynomials with many values in a subfield
For points $P=\{x_1, \ldots, x_n\} \subset {\mathbb F}_{2^m}$ define $$\mathcal{C}(P, t) =\{(f(x_1), \ldots, f(x_n)) \mid \mbox{$f\in {\mathbb F}_{2^m}[X]$ has degree $t$}\}$$ and $\mathcal{C}'(P, t) =...
- 1,242
3
votes
0
answers
154
views
Computational complexity of minimum distance of rate $\frac{1}{2}$ codes
We know from Berlekamp, McEliece and Van Tilborg [On the inherent intractability of certain coding problems, IEEE Trans. Information Theory, 24 (1978)] that computing minimum distance of a (binary) ...
- 387
4
votes
0
answers
84
views
Is there a standard interpretation of this quantity?
Define an encoding scheme by a pair of functions:
$$\mathsf{encode} : \mathcal{M}\to\mathcal{X},\quad \mathsf{decode} : \mathcal{X}\to\mathcal{M}$$
Typical examples of encoding schemes are things like ...
- 918
10
votes
1
answer
444
views
Is subtractive dithering the optimal algorithm for sending a real number using one bit?
Consider the problem of sending a real number $x\in[0,1]$ using a single bit $X\in\{0,1\}$ in an unbiased manner.
We assume that the sender and receiver have access to shared randomness $h\sim U[-1/2,...
- 9,438
8
votes
1
answer
162
views
What are the general direction and target question in the field of quantum error correction?
After quantum error correction was introduced in mid '90s, in subsequent years many of the classical analogues regarding the structure of code (such as singleton bound, GV bound etc) were obtained in ...
- 387
4
votes
1
answer
224
views
Survey on Quantum error correction
Are there any standard recent survey articles on quantum error correction (and may be including fault Tolerant computing)? The most standard ones that many people refer to are this and this. Both of ...
- 387
2
votes
0
answers
170
views
Damerau–Levenshtein distance with transposition of non-adjacent characters?
Wondering if it's possible to calculate Damerau–Levenshtein distance with transposition of non-adjacent characters (DL distance allows transposition of immediately adjacent characters only). I want ...
- 21
2
votes
1
answer
200
views
Explicit Bits-back Coding (a.k.a. Free Energy Coding) applied to Gaussian mixtures
I've been trying to understand Bits-back coding (Frey, B. J., and G. E. Hinton. 1997.) a bit more (pun intended), which can be used to encode data with latent variable models. This tutorial by Pieter ...
- 139
1
vote
0
answers
131
views
Quantum error correction and graph codes
I was reading combinatorial approach towards quantum correction. A lot of work in this is on finding diagonal distance of a graph. Let me add definition of diagonal distance so that this remains self-...
- 387
3
votes
1
answer
190
views
Why Asymptotic Equipartition Property theorem proofs assume the source is memoryless?
I do not understand the assumption $X_1, X_2, \cdots$ are i.i.d. ~p(x) in the AEP proofs I have seen. I have read some different sources for understanding the Asymptotic Equipartition Property. Using ...
- 143
0
votes
1
answer
118
views
Notation of sequences in rate distortion theory
I have been reading whatever sources I could get my hands on today, regarding this problem.
Most notes online about rate distortion theory come from the book Elements of Information Theory by Thomas ...
- 133
2
votes
0
answers
106
views
Relation between automorphism group of a linear code and its dual code
Are there any strong connections between automorphism groups of codes that are dual codes of each other? I am looking for statements like one charcterizes other or one gives bounds on other etc.
In ...
- 387
1
vote
0
answers
85
views
Explicit binary codes with block length n, distance n / log n, rate 1 - o(1)?
What are the best (i.e., highest-rate) explicit binary codes with block length $n$ and minimum distance $d$, in the regime $d = n^{1 - o(1)}$?
The "redundancy" of a code is the difference between the ...
- 1,733
0
votes
1
answer
55
views
weights in low density codes
Generally, low density parity codes are decoded using sum product decoder (also known as decoding under belief propagation). Such codes are usually decoded nicely if there are no short length cycles ...
- 387
5
votes
1
answer
217
views
Complexity of finding automorphism group of code
What is the computational complexity (may be both classical or quantum) for finding automorphism group of a general linear code?
Is there better bound on complexity if structure of code is known for ...
- 387
2
votes
0
answers
98
views
How hard is it to approximate distance of linear code
I'm trying to figure out what is the current knowledge about how hard it is, given a generating matrix of a linear code over a field $F_{q}$, approximate it's distance.
I of course found that ...
- 203
5
votes
0
answers
121
views
Quantum security of cryptosystems: Are any non-Goppa code-based systems resistant to hidden subgroup attacks?
One of the main candidates for post-quantum cryptography is code-based cryptography (as opposed to lattice-based). The Niederreiter cryptosystem based on Goppa codes is shown to be resistant to hidden ...
- 387
1
vote
0
answers
53
views
Underlying codes in Niederreiter cryptosystems
Niederreiter cryptosystem is usually described by a parity check matrix $H$ over $\mathbb{F}_{2^n}$.
The minimum distance $d$ is given by
$d= min\lbrace k \text{ such that there are $k$ linearly ...
- 387
4
votes
0
answers
103
views
Where in $PH$ are these problems?
Is 'Given two codes with alphabet in $\mathbb F_2$ with Generator matrices $G_1$ and $G_2$ do they have the same minimum distance?' in $NP$ or is it in $coNP$ (I can see it in $P^{NP}$)?
If $G_1$ is ...
- 12.8k
3
votes
2
answers
387
views
Minimum distance of a code
Is there a way to compute minimum distance of a code given a systematic parity check matrix? I know that min dist is smallest number $d$ such that there exists $d$ linearly dependant columns. I am ...
- 387
0
votes
0
answers
33
views
Minimum distance of a code [duplicate]
Is there a way to compute minimum distance of a code given a systematic parity check matrix? I know that min dist is smallest number $d$ such that there exists $d$ linearly dependant columns. I am ...
- 387
0
votes
2
answers
213
views
Bounds for maximum number of code-words in a ternary error correcting code with length n and distance d?
I'm not sure I can find an explicit formula. Wondering if anyone can come up with lower/upper bounds.
- 113
2
votes
0
answers
117
views
Explicit Formula of Delsarte's Linear Programming Upper Bound for $A_q(n,3)$
The problem of giving an explicit formula for $A_q(n,d)$ is sometimes referred to as "the main problem in coding theory." The value of $A_q(n,d)$ is given by the maximum number of codewords in a q-ary ...
- 225
2
votes
2
answers
335
views
Why can't codes be defined over infinite fields?
In Coding Theory, people use $q$-ary alphabets: why do we need a finite set? Why can't we define codes over infinite sets. such as $\mathbb{R}$ or $\mathbb{C}$?
- 21
5
votes
0
answers
77
views
Error correction with asymmetric channel
Suppose A is trying to transmit a message to B over a noisy low bandwidth channel, while B has the ability to simultaneously transmit arbitrary amounts of information losslessly to A. Are there ...
- 917
-1
votes
1
answer
113
views
Does a code need at least two symbols to be defined as a code? [closed]
I am wondering whether you could still call a code something that, if transmitting, only transmits one symbol. Or does the formal definition of code require 2 or more symbols? (and would the answer ...
2
votes
1
answer
124
views
Function which detects rotation of bit string
Consider a function $F: \mathbb{F}_2^d \to \mathbb{Z}^n = (f_1,\ldots,f_n)$ with the property that if $y \in \mathbb{F}_2^d$ is a rotation of $x \in \mathbb{F}_2^d$, i.e. $y$ is $x$ permuted by an ...
- 225
1
vote
1
answer
150
views
Why are folded Reed Solomon Codes considered non linear?
This is for my understanding. What am I missing?
- 395
1
vote
1
answer
73
views
Families of LDPC codes with constant error fraction corrected
I am looking for families of error-correcting LDPC codes with a constant error fraction corrected by a decoding algorithm.
For example, I know that Sipser and Spielman proved that there is an ...
- 113
2
votes
0
answers
156
views
Unit hypercube encodings
How can we chose to place $k$ points in $[0,1]^d$, such that the minimum Euclidian distance between any two points is maximized?
Is there a more common term for these combinatorial designs than unit ...
- 2,359
5
votes
2
answers
1k
views
Relation between group theory and information theory
Motivation: I am interested about the application of group theory to information theory. To be precise, I am interested in data compression (source coding theory).
Question:
Is there any paper/survey ...
- 533
1
vote
1
answer
192
views
Structured set of binary words
Definitions:
Let $n\in \mathbb N$ be an integer, and consider the field $\mathbb K=GF(2^n)$.
For $c\in \mathbb N$, let $S_c$ be a set of $n$ elements from $\mathbb K$ such that:
Every element $e$ ...
- 205
1
vote
1
answer
117
views
The noise distribution on $F_2^n$: probability of landing in a subspace versus a coset
Let $V = F_2^n$ be the $n$-dimensional vector space over the field of two elements. The $\epsilon$-noise distribution on $V$, denoted $\mu_\epsilon$, is a probability distribution on $V$ for which ...
- 1,429