Questions tagged [coding-theory]

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

207 questions
Filter by
Sorted by
Tagged with
747 views

Algorithm for determining minimal set of covering prefixes

I have a set of strings. My goal is to find a minimal set of longest prefixes which will match most of that set. For instance, if my set is: ...
246 views

Application of Expander Codes

I need to give a talk about expander codes at university (I'm a student of computer science). Since they have been introduced to show a family of codes looking good when thinking of the Shannon ...
• 163
3k 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 ...
• 264
1k views

What is a good binary encoding for $\phi$-based balanced ternary arithmetic algorithms?

I've been looking for a way to represent the golden ratio ($\phi$) base more efficiently in binary. The standard binary golden ratio notation works but is horribly space inefficient. The Balanced ...
• 211
200 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^{...
• 641
8k views

Encoding the sequence 0110 and determining parity, data bit and value

I've been struggling with several Hamming code/error detection questions because the logic behind it doesn't seem to make sense. eg.1 eg.2 I don't really understand the above two examples and the ...
• 153