Skip to main content

Questions tagged [coding-theory]

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

Filter by
Sorted by
Tagged with
4 votes
1 answer

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: ...
S. Robert James's user avatar
5 votes
1 answer

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 ...
smoes's user avatar
  • 163
9 votes
4 answers

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 ...
Jack M's user avatar
  • 264
7 votes
2 answers

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 ...
hatch22's user avatar
  • 211
7 votes
1 answer

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^{...
user1374864's user avatar
3 votes
1 answer

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 ...
methuselah's user avatar
10 votes
1 answer

Error-correcting rate is misleading

In coding theory, 'how good a code is' means how many channel errors can be corrected, or better put, the maximal noise level that the code can deal with. In order to get better codes, the codes are ...
Ran G.'s user avatar
  • 20.7k

1 2 3 4