Questions & Comments

Are there situations where an algebraic code is applicable and a probabilistic code is not?

Yes.  Whenever a short block length is required or if all error patterns of t or fewer symbols must be corrected, then algebraic codes must be used.  Examples include Hamming codes, SECDED and Chipkill for main memory, RAID and RS RAID and adaptive ECC where the block length can be shortened to only one or a few symbols.  Probabilistic codes require very long block lengths.


Are there situations where a probabilistic code is applicable and an algebraic code is not?

Yes.  When block lengths are very long, raw error rates a very high and a minimum amount redundancy is desired, then probabilistic codes are more applicable than algebraic codes.  Space channels are a prime example.


Does minimum distance matter?

In some situations it does and in others it doesn't.  For deep space and other wireless communications, it probably doesn't matter.  However for things like SECDED and RAID it does matter because all combinations of failures must be corrected.  It also matters if for whatever reason it is necessary to guarantee that all error patters of t or fewer symbols will *always* be corrected.


Idealism vs. Pragmatism

Researchers tend to be idealists and Implementers tend to be pragmatists.  Researchers or theorists tend to ask, "What is the best possible way to do this?", while Implementers tend to ask, "Is this way good enough for all practical purposes?"  For example, a theorist might design an algebraic decoder to correct a variable number of symbols - more symbols would be corrected for those codewords that are more than the minimum distance away from every other codeword while an Implementer would probably conclude that the most practical way to design an algebraic decoder is to correct a fixed number of symbols all the time based on the minimum distance.  For further elaboration on this topic, see The Danger of Overemphasizing Theory.


What causes error floors?

Good question.  The behavior of LDPC decoders seems to defy rationality.  You would expect that if you had a high enough signal to noise ratio, there would be no errors.  However the error rate after decoding does not drop like you would expect it to as the signal to noise ratio increases.  It appears to me that every once in a while the decoder miscorrects even very simple error patterns.  What other explanation is there?  The behavior seems to make no logical sense.  It looks like LDPC decoders can effectively be used to reduce a very high error rate down to some lower level but that some other means must be taken to reduce it further.

I appears to me that LDPC decoders can often correct very severe error patterns, but also miscorrect some very simple error patterns.  It seems to me that is the only explanation which explains the error floor phenomenon.  Miscorrection means errors are "inserted" rather than removed.  It seems to me that's why the error rate does not decrease as one would expect as the signal to noise ratio is increased.  What other explanation is there for that type of decoder behavior?


Why do probabilistic decoders not correct error patterns with only a few errors?

I don't know the answer to this question. 


What are the steps in developing an LDPC encoder and decoder system?

It appears that one needs to be a Researcher to implement a LDPC system or that they be developed by teams of people with Researchers in the team.  If I were given the task of developing a LDPC encoder and decoder, I would not know where to start or what the steps are.


What are the steps in developing a binary BCH encoder and decoder system?

The steps are well-known by many.  Choose a finite field, compute a generator polynomial and implement the encoder and decoder.


What the the steps in developing a RS encoder and decoder system?

The steps are well-known by many.  Choose a finite field, compute a generator polynomial and implement the encoder and decoder.


Will LDPC codes obsolete algebraic codes?  Why? Why not?

In some applications such as deep space channels and some wireless channels, probably yes,  In other applications, no.


The Role of LDPC Codes

In the last decade or so, most of the coding theory literature has been on LDPC codes or other probabilistic codes.  Algebraic codes have been pretty much left in the dust.

With all the emphasis on probabilistic codes, I am concerned that most implementers believe all algebraic codes have become obsolete which I do not believe is true.

I believe probabilistic codes such as LDPC code and Polar codes require very long block lengths, and there are some applications where they just are not appropriate. Several such applications come to mind - the ECC such as SECDED and Chipkill used for main memory, lateral/horizontal ECC across components in RAID systems where the block lengths are short and adaptive ECC for communications such as the programmable RS ECC used in the IEEE802.16 standard where message lengths can be programmed on-the-fly to be any length - messages can be just one RS symbol if desired. In those cases I do not think probabilistic codes can possibly be used. Am I wrong?


The Role of Algebraic Codes

Their role up to now is well-known.  They have been used in main memories, HDDs, CDs, DVDs, Blue-ray disks, for Flash memory, and with all kinds of communications channels and have performed well.  They are good.  For short block lengths, they are all very efficient.  Hamming codes are perfect.  As mentioned in The Danger of Overemphasizing Theory, probably the only people who are concerned about meeting the Shannon capacity limit are coding theorists.  The extra redundancy required by some codes such as binary BCH codes for long block lengths is useful because it dramatically decreases the probability of miscorrection - miscorrection is a very bad thing - if decoders are designed properly.


Decoder Performance

It is well-known that decoder performance cannot be determined by exhaustive testing.  The only way to be able prove performance is by mathematical proofs.

When implementing algebraic codes, it can be proven that all error patterns of t or fewer symbols will be correctly corrected and simulations can be done to fairly accurately predict the probability of miscorrection based on very severe error patterns.

Based on my current knowledge, it does not appear that those type of claims can be made for probabilistic codes such as LDPC codes.  It appears that some very simple error patterns will sometimes be miscorrected.  That seems to be the only explanation for error floors.


Performance of Probabilistic Codes

You can say they will significantly reduce the error rate in channels that have a very high raw error rate which is a very good thing.  What else can you say?  It seems to me you cannot say much more.  You cannot say what the minimum distance is.  You cannot guarantee that all simple error patterns will always be correctly corrected.


What can be said about the performance of Algebraic Codes?

You can say that all error patterns with t or fewer errors will be correctly corrected and that you can reduce the probability of miscorrection to any desired level by using more redundancy than is necessary to correct t errors.