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?

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ Why would you restrict yourself to binary codes if your transmission medium/technology can handle many more? $\endgroup$
    – Raphael
    Commented Mar 24, 2012 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$
    – Mohammad Alaggan
    Commented Mar 24, 2012 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
    Commented Mar 24, 2012 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.
    Commented Mar 24, 2012 at 18:12

1 Answer 1

Reset to default
7
$\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").

Improve this answer
$\endgroup$
2
  • $\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.
    Commented Mar 25, 2012 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
    Commented Jun 15, 2014 at 13:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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