I was reading a paper about a transposition and single deletion error correcting code and they claim that the redundancy of the code was only $\log(6n-3)$ bits.

But what does that means? I was trying to get that from the proof of that fact but what they proved instead was that

there exists a such (with the structure they propose) code whose redundancy is at most $\log(6n-3)$ bits

and in the proof itself they just said that the cardinality of the code is greater or equal than $\frac{2^n}{6n-3}$.

How does that proved the hypothesis?

Also, if I have my own code how do I compute the redundancy (or a reasonable bound on it?)

  • $\begingroup$ What paper were you reading? $\endgroup$ – Yuval Filmus Nov 6 '18 at 16:58

A linear error-correcting code encodes $m$ message bits using $w$ encoded bits. The redundancy is $r = w-m$. In other words, it is a collection of $M = 2^m$ codewords out of the possible $W = 2^w$ words of length $w$. We can extract the redundancy using the formula $$ r = \log_2 \frac{W}{M}. $$ This formula makes sense for arbitrary error-correcting codes.

In your case, codewords are of length $n$, and there are at least $2^n/(6n-3)$ of them. Therefore the redundancy is at most $$ \log_2 \frac{2^n}{2^n/(6n-3)} = \log_2 (6n-3). $$

  • $\begingroup$ thanks for your answer, I think this formula works as well for non linear codes, isn't it? $\endgroup$ – Luis GC Nov 8 '18 at 8:56
  • $\begingroup$ Yes, that’s what I wrote in the answer. $\endgroup$ – Yuval Filmus Nov 8 '18 at 15:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.