Skip to main content

Questions tagged [coding-theory]

The mathematical theory of codes, as used in communication, data compression, and cryptography.

Filter by
Sorted by
Tagged with
5 votes
0 answers
78 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 ...
39 votes
13 answers
3k views

Using error-correcting codes in theory

What are applications of error-correcting codes in theory besides error correction itself? I am aware of three applications: Goldreich-Levin theorem about hard core bit, Trevisan's construction of ...
-1 votes
1 answer
120 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 ...
1 vote
1 answer
156 views

Why are folded Reed Solomon Codes considered non linear?

This is for my understanding. What am I missing?
1 vote
1 answer
77 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 ...
21 votes
2 answers
3k views

How good is the Huffman code when there are no large probability letters?

The Huffman code for a probability distribution $p$ is the prefix code with the minimum weighted average codeword length $\sum p_i \ell_i$, where $\ell_i$ is the length of the $i$th codword. It is a ...
2 votes
0 answers
159 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 ...
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 ...
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$ ...
2 votes
1 answer
121 views

Subspace-evasive set performance in the random case

A subspace evasive set is defined as a large subset of a vector space which has small intersection with any $k$ dimensional affine space. That is, it "evades" all affine subspaces of small enough ...
1 vote
1 answer
119 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 vote
0 answers
185 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.
1 vote
0 answers
43 views

Reference request on dynamic flows combined with network coding

I have read some papers about network coding and dynamic flows (flows over time). I think I have made comprehensive searches on google, google scholar and IEEE Xplore. IMHO, the reasons for the ...
1 vote
0 answers
88 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 ...
3 votes
0 answers
76 views

Communication complexity of edit resilient synchronization

Supposing we have two strings $A$ and $B$ that are both edit distance $\tau$ from each other at two different sites is there a communication complexity model where synchronizing such strings have been ...
1 vote
0 answers
69 views

Optimal distribution of integer edge weights

I am not sure whether the following problem has been studied. Any help would be greatly appreciated. I have $L$ sets, $S_1, S_2,...,S_L$, each of $n$ elements, taken from a universe of $N$ elements. ...
4 votes
2 answers
221 views

Are there Similar Distance Binary Error Correcting Codes?

I'm trying to find a low distortion embedding of the trivial metric space into hamming space. It seems this should be doable by using a large set of low dimensional vectors, with approximately equal ...
3 votes
0 answers
54 views

Reference for randomized GMD decoding

The GMD decoder is an algorithm for decoding concatenated codes up to half their minimal distance. The standard presentation of this algorithm usually proceeds in two steps: First, one shows a ...
1 vote
0 answers
68 views

The curve used in Parvaresh-Vardy decoding

Consider the Parvaresh-Vardy list decoder. As I understand it, the idea is to decide on a curve over an extension field of the form $(f,f^h mod E, f^{h^2} mod E,\dots)$ and then evaluate each of ...
0 votes
0 answers
54 views

Number of different cycles in cyclic codes with length n

I am studying Information theory, coding theory in particular at the moment, and I am having trouble determining how many different cycles are defined by a certain generator polinomial? Given a ...
4 votes
0 answers
118 views

What is the largest noise rate $\eta(n)$ for which learning parities with noise is easy?

Learning Parity with Noise (LPN) is usually stated with constant noise rate $\eta < 1/2$ on the labels, and it is believed to be hard to learn because of the high statistical dimension of the ...
2 votes
0 answers
126 views

Universal constant for bivariate testing

In the seminal paper of Polishchuk and Spielman where they give a construction of nearly linear sized $PCP$ for an $NP$ problem, one of the key ingredients is a low-degree test for bivariate ...
5 votes
0 answers
157 views

Applications of small Kakeya sets over finite fields

It was proved by Dvir that a Kakeya set in $\mathbb{F}_q^n$ has size at least $q^n/n!$, a bound which was later improved to $q^n/2^n$. For $n = 2$ and $q$ odd the exact bound is $q(q+1)/2 + (q-1)/2$ ...
-3 votes
1 answer
68 views

Complicated Huffman coding [closed]

I am trying to figure out how to code these symbols. I am pretty sure I have it, but it gets a little tricky. Let A,B, and C have probabilities .71, .16, and .13 respectively. I am trying to code the ...
4 votes
2 answers
435 views

On the need for a self-correcting function in the PCP theorem

Original proof of the PCP theorem, uses self-correction property of linear functions. Assume we have $f: \{0,1\}^n \rightarrow \{0,1\}$, a function or table of values, that is $(1-\delta)$-close to ...
3 votes
1 answer
586 views

Distance of arbitrary vectors to Hadamard code

Let $n$ be a positive integer and $N = 2^n$. The Hadamrd code of "block length" $N$ can be generated using the inner product $f_u(x) = \langle u,x \rangle$ mod $2$ for all $u \in \{0,1\}^n$. It is ...
4 votes
1 answer
438 views

Approximation algorithms for min vector subset-sum over GF(2)

In this question vzn asked about the following problem, which I'll call Vector-Subset-Sum. Given a set of vectors $v_i$ over GF(2) and a target vector $y$, is there a subset of the $v_i$ summing to ...
4 votes
1 answer
330 views

Reference request: Classical analog of quantum threshold theorem

For quantum circuits, once the gate error is below a threshold, the error probability of an entire computation can be driven exponentially small with polylog costs in time and space: http://arxiv.org/...
2 votes
1 answer
422 views

Question about "typical set" in Shannon's source coding theorem

I was following the textbook by David Mackay: Information theory inference and learning algorithms. I have question on asymptotic equiparition' principle: For an ensemble of $N$ $i.i.d$ random ...
0 votes
1 answer
373 views

Source Coding Theorem: what happen when we go below N*H(x) bits?

I was following the textbook by David Mackay: Information theory inference and learning algorithms. I have question on Shannon's source coding theorem (p81): $N$ i.i.d. random variables each with ...
0 votes
2 answers
141 views

Determining the distribution of results of a simple algorithm

Setting Consider repeating the following process on the numbers $N=\{1, 2, 3, \ldots, n\}$: Pick an integer $k \in N$, uniformly at random. Pick a subset of $k$ elements from $N$, uniformly at random....
27 votes
1 answer
538 views

Good codes decodable by linear-sized circuits?

I'm looking for error-correcting codes of the following type: binary codes with constant rate, decodable from some constant fraction of errors, by a decoder implementable as a Boolean circuit of ...
1 vote
0 answers
45 views

Decoding of Gabidulin codes

Consider the space of matrices in $\mathbb{F}_q^{n \times m}$ where $\mathbb{F}_q$ is the finite field with $q$ elements. We can define a metric on this space, given by $d(A,B) := rank(A-B)$, called ...
4 votes
1 answer
140 views

Are there good locally decodable _erasure_ codes

Are there known locally decodable erasure codes with linear codeword length and $\:n^{o(1)}\:$ query complexity? According to pages 1 and 4 of this link (which annoying does not give its own ...
2 votes
1 answer
140 views

Ambivalent Coding

Consider the following situation, I want to send one of two bitstrings, A or B, to a receiver. Clearly, I can do this by sending the shortest, but is there a better way? It seems that the requirement ...
2 votes
0 answers
87 views

Complexity of counting codeword length distribution

Suppose I have a code $C$ over $GF(2)$. I would like to count exactly the number of codewords of $C$ of weight $k$. Here $k$ should be thought of as small compared to the dimensions of the code. ...
4 votes
4 answers
2k views

Research in Coding Theory

I have just started learning about coding theory. Hence, I would like to ask for your suggestions and guidance for a very beginner like me. Which books are good for beginning coding theory? (I start ...
7 votes
1 answer
231 views

Coding theory and complete problems

Coding theory is an useful topic in theoretical computer science. There are known examples of problems coming from coding theory which turn out to be NP complete. My questions are the following: $(1)...
2 votes
0 answers
75 views

Weight enumerator and levels of polynomial hierarchy

Let $A_i$ be the number of codewords in a binary linear code $\mathcal{C}$ of weight $i$. It is known that: $A_k$ is in $P$, where $k = \mathcal{O}(\log_2 n)$. $A_{n}$ is in $\#P-Complete$, ...
4 votes
2 answers
218 views

The length of non perfect binary 1 error correcting codes

I am interested in the best known number of code words in binary 1 error correcting codes of length $n$. I am aware of the Hamming code when $n=2^r-1$, but i would like to get lower bounds for other $...
1 vote
0 answers
20 views

can constant weight codes achieve channel capacity

Can a sequence of constant weight linear codes achieve channel capacity on Additive White Gaussian Noise channel? (by a sequence achieving capacity I mean a sequence of linear codes of increasing ...
13 votes
0 answers
193 views

Name and references for balanced variant of the long code?

The long code (arising in PCP theory etc) is an encoding of a set of $k$ values, using binary strings of length $2^k$ (double exponential in the number of bits needed to specify a value), with one ...
1 vote
0 answers
61 views

Number of non-isomorphic codes

We have number of non-isomorphic graphs given in http://planetmath.org/enumeratinggraphs Over an alphabet $q$ how many non-isomorphic $[n,k,d]_q$ codes are possible particularly in the special case ...
6 votes
0 answers
114 views

Codes that are both locally testable and locally decodable

Are there any known constructions of binary locally testable codes with very low (e.g., independent of the length of the codeword) query complexity and "good" rate (e.g., mapping strings of length $k$ ...
1 vote
0 answers
114 views

On Labeling the cube

Regularly in a Hamming hypercube, the vertices are labelled so that edge difference equals path difference. That is greater the edge difference, greater the hamming distance of the labelled vertices ...
5 votes
0 answers
330 views

Weight enumerator of a binary linear code

The weight enumerator polynomial of a $(n,k)$ binary linear code $\mathcal{C}$ is defined as $$WE(\mathcal{C}) = \sum_{i=0}^{n}WE_{i}(\mathcal{C}) x^{i}$$ where $$WE_{i}(\mathcal{C}) = \#\{c\in\...
7 votes
4 answers
749 views

Optimal encoding of $k$-subsets of $n$

A colleague asks the following question: Let $S_k$ denote the subsets of $n$ of size $k$. Is there an optimal and efficient encoding of these subsets ? Namely, is there an function $f$ from $[0,...
5 votes
2 answers
130 views

Reference Request: Error correction code for a random projection

I'm interested in a variant of the Binary Channel, where the bits aren't flipped with some probability, but rather they are completely erased. Output words therefore vary in length. I'm quite sure ...
6 votes
1 answer
261 views

Best upper bound on rate for q-ary codes

Among the many upper bounds for families of codes in $\mathbb F _2 ^n$, the best known bound is the one by McEliece, Rodemich, Rumsey and Welch (derived through a linear programming relaxation ...
5 votes
2 answers
1k views

Asymptotically good codes

In short my question is what are all known explicit constructions of asymptotically good codes over finite alphabet? In more details: A sequence of codes codes $C_i: F^{k_i}\rightarrow F^{n_i}$ with ...