Questions tagged [coding-theory]

The study of data representations that enable error detection, error correction and/or compression.

Filter by
Sorted by
Tagged with
8
votes
4answers
2k views

No compression algorithm can compress all input messages?

I just started reading a book called Introduction to Data Compression, by Guy E. Blelloch. On page one, he states: The truth is that if any one message is shortened by an algorithm, then some other ...
4
votes
1answer
32k views

Hamming distance required for error detection and correction

I have already asked a pair of questions on the hamming distance, hamming code, valid and invalid codewords on this website, because I cannot understand those concepts fully, and in a few weeks or ...
52
votes
8answers
19k views

Is Morse code without spaces uniquely decipherable?

Are all Morse code strings uniquely decipherable? Without the spaces, ......-...-..---.-----.-..-..-.. could be Hello World ...
12
votes
3answers
1k views

PRNG for generating numbers with n set bits exactly

I'm currently writing some code to generate binary data. I specifically need to generate 64-bit numbers with a given number of set bits; more precisely, the procedure should take some $0 < n < ...
7
votes
1answer
169 views

Prove fingerprinting

Let $a \neq b$ be two integers from the interval $[1, 2^n].$ Let $p$ be a random prime with $ 1 \le p \le n^c.$ Prove that $$\text{Pr}_{p \in \mathsf{Primes}}\{a \equiv b \pmod{p}\} \le c \ln(n)/(n^{...
-1
votes
1answer
62 views

A max-even subset problem

I want to know if there is any polynomial algorithm for the problem, or any NP-completeness result. Given a set $S$ and $m$ subsets $C_1, \dots, C_m$ of $S$, we want to find a non-empty set $X\...
3
votes
2answers
3k views

How to decode multiple-digit gamma codes and get the gap sequence?

How to decode gamma code ($\gamma$ code): 1110001110101011111101101111011 and get the gap sequence? Detailed information about Gamma codes ($\gamma$ codes) ...
2
votes
1answer
903 views

Compute minimum hamming distance of a code

How do you find the minimum hamming distance of a code? A naive way is computing the distance of each pair of codewords in our code. It becomes hard when the code is sufficiently large. Is there a ...
0
votes
0answers
24 views

How to decode multiple-digit gamma codes and get the gap sequence? [duplicate]

How to decode gamma code ($\gamma$ code): 1110001110101011111101101111011 and get the gap sequence? Detailed information about Gamma codes ($\gamma$ codes) ...