Questions tagged [coding-theory]
The mathematical theory of codes, as used in communication, data compression, and cryptography.
123
questions
0
votes
0
answers
7
views
High-proba lower bound for $\prod_i \sum_{j\in G_i} y_j$, where the $G_i$'s are partition of $[n]$ with equal sizes, and the $y_j$'s are iid Bernoulli
Let $n$ be a large positive integer and let $G_1,\ldots,G_k$ be a partition of $[n]:= \{1,2,\ldots,n\}$ it $k$ blogs of roughly equal size $n_1$. Let $x=(x_1,\ldots,x_n) \in \{\pm 1\}^n$ be a random ...
- 291
0
votes
0
answers
24
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
83
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
166
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,859
1
vote
0
answers
18
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$ ...
- 518
0
votes
0
answers
55
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
82
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
204
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
0
answers
62
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
162
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
83
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 ...
- 600
0
votes
0
answers
112
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
164
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 ...
- 250
1
vote
1
answer
68
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
164
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) =...
- 241
3
votes
0
answers
147
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
83
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 ...
- 778
10
votes
1
answer
430
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,368
8
votes
1
answer
160
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
178
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
136
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
195
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
125
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
2
votes
1
answer
157
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 ...
- 133
0
votes
1
answer
113
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
97
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
82
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
197
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
91
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.6k
3
votes
2
answers
342
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
189
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
109
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
315
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
104
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
146
views
Why are folded Reed Solomon Codes considered non linear?
This is for my understanding. What am I missing?
- 395
1
vote
1
answer
71
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
155
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,351
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
190
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
116
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,419
1
vote
0
answers
169
views
The edit distance of BWT of two strings with one difference
Let $BWT$ stand for the Burrows-Wheeler transform on strings.
What is the maximal edit distance of $BWT(w)$ and $BWT(u)$, if $w$ and $u$ differ only in one character.
- 19
1
vote
0
answers
84
views
Convex hull of codebook (LP-decoding)
So the well-cited article by Feldman et al from 2005 has a method of constructing the convex hull of the feasible set for ML-decoding.
Basically, he considers the parity check matrix $H$ as a Tanner ...
- 263