Outcomes of Decoding

Algebraic and probabilistic codes are block codes.  Information emitted from a source is chopped into "blocks" or "messages" and messages are encoded and decoded independently. Probabilistic codes are only applicable if messages are long.  Algebraic codes can be used with messages of any length.

For all decoders (either algebraic or probabilistic) there are three possible decoding outcomes ...

  1. Correct decoding
  2. Incorrect decoding (or miscorrection)
  3. Failure to decode
The first outcome is good, the second is bad and the third is OK.

Generally speaking, decoding is the process (iterative or non-iterative) of trying find the answer to the question, "what message was sent?" and the process either ends up with ...

  1. The right answer
  2. The wrong answer
  3. No answer
With algebraic codes, it is well-understood which error patterns will be correctly corrected because the minimum distance of the code is known, and the decoding process finds which legitimate codeword is "closest" to the received word.

For probabilistic codes, it does not seem to be possible to make many assertions as to which error patterns will be correctly corrected because the minimum distance is generally unknown, and the decoding process does not find which legitimate codeword is "closest" to the received word as is the case for algebraic decoders.

With algebraic codes, the probability of miscorrection (a bad thing) can be made arbitrarily low by adding more redundancy.

There does not seem to be any remedy for reducing the probability of miscorrection when using probabilistic codes.  If you add more redundancy to reduce the probability of miscorrection, then you are making the code sub-optimal and taking away the feature of the code that made it attractive in the first place.

For algebraic codes that correct t symbols in error, in almost all cases when a decoder miscorrects it will insert an additional t errors into the block that already contains T > t errors, and the decoder cannot know that it miscorrected and therefore cannot signal that fact.

Consider an information source that emits symbols continuously and those symbols go through a channel that adds many errors.   Let's just say that error patterns with more than 10 errors occur very infrequently - maybe only a few times a month.  If we implement a decoder that corrects 10 errors and always miscorrects if more than 10 errors occur, then, the decoder will correctly correct the vast majority of error patterns and, although the decoder itself inserts 10 errors a few times each month, overall the average decoder output error rate will be much less than the decoder input error rate.  I believe this is the type of thing that causes error floors when using probabilistic codes.