10
$\begingroup$

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 designed using a large alphabet (rather than binary one). And then, the code is good if it can deal with a large rate of erroneous "symbols".

Why isn't this consider cheating? I mean, shouldn't we only care about what happens when we "translate" each symbol into a binary string? The "rate of bit error" is different than the rate of "symbol error". For instance, the rate of bit-error cannot go above 1/2 while (if I understand this correctly), with large enough alphabet, the symbol-error can go up to $1-\epsilon$. Is this because we artificially restrict the channel to change only "symbols" rather than bits, or is it because the code is actually better?

$\endgroup$
  • 1
    $\begingroup$ Why would you restrict yourself to binary codes if your transmission medium/technology can handle many more? $\endgroup$ – Raphael Mar 24 '12 at 12:19
  • $\begingroup$ @Raphael It would help if you could justify your point with a few practical examples of real-life technologies handling non-binary symbols and post that as an answer. $\endgroup$ – M. Alaggan Mar 24 '12 at 16:23
  • $\begingroup$ @M.Alaggan: I'm no expert on this; I figure if you can encode 0/1 on a wave carrier, you can encode many more symbols, too, transmitting more information by time interval. It would surprise me if modern technology would not do this (think code-multiplexing) but I can not name a concrete example. $\endgroup$ – Raphael Mar 24 '12 at 16:37
  • $\begingroup$ @Raphael I think you are right, current digital-communication channels DO work with larger symbols, but not more than, say, 256-bit per symbol (which is quite rare for wireless, but may be common for cables). But the symbol-size is limited to very small sizes, and cannot (practically) grow at will. $\endgroup$ – Ran G. Mar 24 '12 at 18:12
8
$\begingroup$

Many widely used codes for binary data are concatenated codes, which are composed by using two error-correcting codes. The inner code is over a binary alphabet, and the outer code is over an alphabet whose symbols correspond to the codewords of the inner code. This allows you to use the superior power of larger alphabet sizes to encode binary messages without "cheating".

The standard definition of minimum distance is a natural one to use when considering concatenated codes, as well as in the theory of codes over large alphabet sizes. It would only be "cheating" if you used these numbers to compare a binary code with a large-alphabet code that encodes binary input without using an inner code as well; coding theorists are clever enough not to do this (and I believe that since concatenated codes were invented, large-alphabet codes have often been used along with an inner code, but large-alphabet codes are also very good for correcting error in bursty channels such as CDs, since a large number of consecutive bit errors will only affect a few "symbols").

$\endgroup$
  • $\begingroup$ Peter, thanks for the answer. For a concatenated code, isn't it true that the (bit) error rate cannot exceed 1/2? so this method just allows us getting closer to 1/2 while keeping the decoding efficient, right? $\endgroup$ – Ran G. Mar 25 '12 at 20:20
  • $\begingroup$ @Ran: For a binary code, the bit error rate cannot exceed 1/2. Concatenated codes need not be binary. But that's nitpicking; your comment is essentially correct. $\endgroup$ – Peter Shor Jun 15 '14 at 13:09

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.