error-correcting codes, error-detecting codes and related algebraic and/or combinatorial constructions
13
votes
6answers
586 views
Cryptography and Coding Theory
What is the difference between Cryptography and Coding Theory?
What books are good books on these topics? Especially from the algebraic viewpoint.
9
votes
3answers
282 views
Has error correction been “solved”?
I recently came across Dan Piponi's blog post An End to Coding Theory and it left me very confused. The relevant portion is:
But in the sixties Robert Gallager looked at generating random sparse ...
8
votes
3answers
114 views
Is there a $(6,9,3)_2$ code?
Does there exist a $1$-error-correcting binary code with block length $6$ and $9$ codewords?
The Hamming bound says that for any code $C$ with those parameters, $|C| \le \frac{2^6}{1+6} \approx ...
8
votes
3answers
137 views
Using Hensel's Lemma to Factor a Polynomial over $\mathbb{Z}_4[x]$
We recently learned about codes over $\mathbb{Z}_4$, and Hensel's Lemma. The lemma is as follows:
Let $f(x) \in \mathbb{Z}_4[x]$. Suppose $\mu(f(x)) = h_1(x)h_2(x) \cdots h_k(x)$, where $h_1(x), ...
7
votes
5answers
193 views
Simplest error detecting/correcting codes for math newbies
Suppose you have been given the task of teaching some basic coding theory to folks who are interested in math but have not taken algebra, number theory, etc. If you want to introduce codes, you might ...
7
votes
2answers
552 views
Is the set of all finite sequences of letters of Latin alphabet countable/uncountable? How to prove either?
Today in Coding/Cryptography class, we were talking about basic definitions, and the professor mentioned that for a set $A=\left \{ \left. a, b, \dots, z \right \} \right.$ (the alphabet) we can ...
7
votes
1answer
128 views
“Anti-Gray codes” that maximize the number of bits that change at each step
Let $N$ be a non-negative integer and let $S$ be some ordering of the $2^N$ distinct $N$-tuples of binary digits. We can look at the number of bits that change from each element to the next, and add ...
7
votes
1answer
204 views
Closest pair of vectors in $\{0,1\}^n$
Suppose we are given $k$ points in $\{0,1\}^n$ (using Hamming distance as metric).
Consider the two points that have the smallest distance between
them.
Does there exist any results bounding this ...
7
votes
1answer
176 views
A property of the Golay codes
I've been reading about Golay codes, and I found an interested property that I am having trouble showing. The property says:
If the $[24, 12, 8]$ binary Golay code $\mathcal{G}$ is punctured in ...
7
votes
3answers
355 views
Optimization problem for a parity-check code
I have $n$ data blocks and $k$ parity blocks distributed across $m$ boxes where each box can contain atmost $b$ blocks. Each parity block is Ex-or of some data blocks (for ease of understanding we can ...
7
votes
0answers
98 views
Error correction code handling deletions and insertions
I have data which is expressed in form of fixed-length sequence of decimal digits, typically 10 digits in length.
I'm looking for error correction code that would allow me to append one or more ...
5
votes
3answers
2k views
Addition and multiplication in a Galois Field
I am attempting to generate QR codes on an extremely limited embedded platform. Everything in the specification seems fairly straightforward except for generating the error correction codewords. I ...
5
votes
2answers
3k views
Reed Solomon Polynomial Generator
I am developing a sample program to generate a 2D Barcode. And i am using reed solomon error correction code. By Going through this article i am developing the program. But i couldn't understand how ...
5
votes
4answers
158 views
Increasing the number of repetitions decreases the error probability
In coding theory when we encode 101 with 111000111 we have certain error probability. how can one prove that increasing the number of repetitions decreases the error probability.
Let the probability ...
5
votes
2answers
301 views
What requirements should a CRC polynomial satisfy?
What requirements should a CRC polynomial of a given degree satisfy to make the CRC catch a maximum of errors?
edit
I'm talking about GF(2) polynomials.
As an example of the kind of requirements ...
