# what does the redundancy of a code means?

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?)

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

## 1 Answer

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).$$

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