Introduction to Cryptography with Coding Theory, 3rd Edition

24.3 Bounds on General Codes

We have shown that an $(n\text{,}M\text{,}d)$ code can correct $t$ errors if $d\ge 2t+1$. Hence, we would like the minimum distance $d$ to be large so that we can correct as many errors as possible. But we also would like for $M$ to be large so that the code rate $R$ will be as close to $1$ as possible. This would allow us to use bandwidth efficiently when transmitting messages over noisy channels. Unfortunately, increasing $d$ tends to increase $n$ or decrease $M$.

In this section, we study the restrictions on $n$, $M$, and $d$ without worrying about practical aspects such as whether the codes with good parameters have efficient decoding algorithms. It is still useful to have results such as the ones we’ll discuss since they give us some idea of how good ...