Iterative decoding of one-step majority logic decodable codes based on belief propagation

Recently, the belief propagation (BP) algorithm has received a lot of atten tion in the coding community, mostly due to its near-optimum decoding for l ow-density parity check (LDPC) codes and its connection to turbo decoding, In this paper, we investigate the performance achieved by the BP algorithm for decoding one-step majority logic decodable (OSMLD) codes. The BP algori thm is expressed in terms of likelihood ratios rather than probabilities, a s conventionally presented. The proposed algorithm fits better the decoding of OSMLD codes with respect to its numerical stability due to the fact tha t the weights of their check sums are often much higher than that of the co rresponding LDPC codes. Although it has been believed that OSMLD codes are far inferior to LDPC codes, we show that for medium code lengths (say betwe en 200-1000 bits), the BP decoding of OSMLD codes can significantly outperf orm BP decoding of their equivalent LDPC codes, The reasons for this behavi or are elaborated.