The coding-theory tag has no wiki summary.
3
votes
1answer
71 views
Upperbound on cardinality of product of two string sets at pairwise Hamming distance $> 1$
I am considering products $U\times V$ of subsets $U, V\subset \{0, 1\}^p$ with a pairwise Hamming distance greater than 1 : $\forall uv\in U\times V, D(u,v) \geq 2$.
Given $p$, I am looking for a ...
0
votes
0answers
68 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 ...
3
votes
1answer
160 views
Surveys on Algorithmic Problems in Coding Theory
Coding Theory has many algorithmic problems that enriched theoretical computer science. I want to learn specifically the connection between coding theory and the hardness of computational problems. ...
2
votes
0answers
76 views
Bayesian compression
Suppose you have a sequence generated by an i.i.d. process (such as repeatedly rolling a die and recording the values in order) parameterized by some K-dimensional vector $\vec{\gamma}$ (the ...
0
votes
0answers
92 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 ...
7
votes
2answers
129 views
How do I construct an optimal affix code?
An affix code is a code that is simultaneously a prefix and suffix code. That is, no codeword is neither the prefix nor the suffix of any other codeword. Affix codes can be instantaneously decoded in ...
3
votes
0answers
91 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 ...
1
vote
1answer
127 views
fast range summable hash functions
I'm finding is there any range summable hash function.
ADD: The hash function I refer to is the one that is typically used in tug-of-war sketch(AMS sketch). Please refer to The space complexity of ...
4
votes
2answers
106 views
Gift bits when encoding a sequence of messages, how is that?
Recently a friend of mine asked a question I couldn't give immediate answer to.
Say we have $ n $ messages of length $ m $ bits each. Now we can pack them in a single message of length $ n * m $ ...
5
votes
2answers
406 views
Transposition of any characters in Damerau–Levenshtein edit distance computation
Is it possible to modify the computation of Damerau–Levenshtein distance to take into account not only the transposition of adjacent characters, but the transposition of any characters?
Maybe some ...
6
votes
3answers
567 views
Maximum subset of words with Hamming distance ≥ D
For all words of fixed length L over a given alphabet, I am interested in a practical algorithm that can give me a subset of maximal cardinality such that the Hamming distance between any two words in ...
9
votes
1answer
191 views
Boolean error correcting code over $\mathbb{F}_q$
Is there any known construction of a linear error correcting code $\mathsf{ECC}:\mathbb{F}_q^n \to \mathbb{F}_q^m$ (with reasonable parameters), such that when given a Boolean vector $v\in \{0,1\}^n$, ...
10
votes
1answer
228 views
Constructing vectors in general position
Let a real $k\times n$ ($k\le n$) matrix ${\bf A}$ with the property that any collection of $k$ columns is full rank.
Q: Is there an efficient way to deterministically find a vector ${\bf a}$ such ...
15
votes
0answers
303 views
Looking for an operator on polynomials
I have a small, self-contained, math question, whose motivation is from theoretical computer science (specifically, list decoding of algebraic codes, derivative/multiplicity codes, etc).
I wonder ...
6
votes
0answers
167 views
Tree rotation, a problem similar to Huffman coding
I am not sure whether the following problem has been studied.
We have a undirected tree $T$.
We would like to construct another tree $T'$.
$T'$ is a binary tree. Each inner nodes of $T'$ ...
-4
votes
2answers
352 views
Covering Codes with Game Theory Application
Here is a question I came up with and i have been pondering for a while. It relates to covering codes, a subset of coding theory. I could not come up with an adequate solution, so here I am, asking ...
3
votes
1answer
198 views
reduction of maximum independet set to minimum distance of code
Is there a reference for direct reduction of computing maximum independent set of a suitably constructed graph to computing minimum distance of a linear code when the code is specified by its parity ...
7
votes
1answer
237 views
Applications of Spectral Graph Theory in Information and Coding Theory
I wanted to find out what are some application of SGT in the area of information and coding theory and maybe communications. The most related that comes to mind is the work on Expander Codes
Michael ...
2
votes
1answer
268 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 ...
4
votes
2answers
480 views
“long code test” and “dictatorship test”
Why is "long code test" also called "dictatorship test"?
I got really confused when I read about it in Arora's survey.
1
vote
0answers
93 views
Information theory and Tsfasman-Manin's problem
Yuri Manin recently posted an interesting paper on computability of boundary regions of distance-rate trade-offs for error correction codes.
http://arxiv.org/PS_cache/arxiv/pdf/1107/1107.4246v1.pdf
I ...
11
votes
5answers
1k views
Why does Huffman coding eliminate entropy that Lempel-Ziv doesn't?
The popular DEFLATE algorithm uses Huffman coding on top of Lempel-Ziv.
In general, if we have a random source of data (= 1 bit entropy/bit), no encoding, including Huffman, is likely to compress it ...
8
votes
4answers
495 views
Surveys on Network Coding
I want to start learning about Network Coding:
http://en.wikipedia.org/wiki/Network_coding
Do you know any good survey (e.g. from IEEE Surveys and Tutorials) on the above subjects. I found some ...
0
votes
0answers
195 views
Lee metric Gilbert-Varshamov and Hamming bounds for larger relative distance ranges
Smaller version of the cross-posting from http://mathoverflow.net/questions/70524/lee-metric-constructive-and-asymptotic-bounds
The following link provides a Gilbert-Varshamov lower bound and a ...
11
votes
2answers
256 views
Solvability of matrix filling
Matrix $A$ has dimension $n \times n(n-1)$. We want to fill $A$ using integers between $1$ and $n$, inclusive.
Requirements:
Each column of $A$ is a permutation of $1, \dots, n$.
Any submatrix ...
2
votes
3answers
365 views
Is there a lower bound of number of redundant bits necessary to encode a word with certain Hamming distance?
Is there a lower bound (in coding theory or elsewhere) of number of redundant bits necessary to encode a word with certain Hamming distance?
There is some known data for parity checks, CRC, Hamming ...
23
votes
0answers
319 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 ...
4
votes
1answer
103 views
Lower bounds on 2-query locally decodable codes
Does any one knows if there is a non-quantum proof of the fact that non-linear 2-query LDC must have exponential size?
12
votes
2answers
722 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 ...
6
votes
0answers
211 views
Huffman “terminator” bitstring
Motivation
Imagine a huffman compressed file that gets downloaded partially, like in P2P software, so we allocate disk space for the whole file first and then start downloading random file chunks. ...
8
votes
2answers
315 views
Finding out a set by intersection comparison
The following problem recently emerged from my research and I would like to ask if anyone knows if this problem was considered before or has heard of anything that might be related.
The general ...
1
vote
0answers
319 views
Soft decoding of linear block (20,10) codes - what methods are used ?
What algorithms are advised for soft-decoding of linear block codes (20,10) ?
What are advised references ?
Sincerely Yours Alex
PS
By soft-decoding - I mean that input - is set of 20 real ...
6
votes
1answer
566 views
Dual BCH codes of design distance $d$
The SODA 2008 Ailon-Liberty paper on fast Johnson-Lindenstrauss transforms uses a "dual BCH code of design distance 5" as part of the construction. They cite the
MacWilliams-Sloane book on ...
32
votes
11answers
1k 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 ...
