An iterative algorithm for decoding block codes transmitted over a memoryless channel

Abstract

An algorithm was developed which optimally decodes a block code for minimum probability of symbol error in an iterative manner. The initial estimate is made by looking at each bit independently and is improved by considering bits related to it through the parity check equations. The dependent bits are considered in order of interesting probability of error. Since the computation proceeds in a systematic way with the bits having the greatest effect being used first, the algorithm approaches the optimum estimate after only a fraction of the parity check equations were used.