New majority logic decoding algorithm for Reed-Muller codes

Costas, Argyrides, Dhiraj K. Pradhan

Jun Asatani, Takuya Koumoto, Toru Fujiwara +1 more

Ting‐Ya Yang, Houshou Chen

This study investigates the decoding algorithms of binary Reed–Muller (RM) codes. The main goal of the study is to modify majority‐logic decoding using sum‐product or min‐sum decoding algorithms at the highest‐order information bits in RM codes. Numerical results show that compared with the traditional majority‐logic decoding algorithm, the modified majority‐logic decoding method proposed in this study can reduce the bit error rate by a large margin. This is achieved without incurring a significant increase in decoding complexity because soft‐decision decoding is only used in the highest information bits in RM codes whereas majority‐logic decoding is still applied at the other orders of information bits in RM codes.

Paul D. Laity

Hoang Ly, Emina Soljanin

The classical majority-logic decoder proposed by Reed for Reed-Muller codes RM(r, m) of order r and length 2^m, unfolds in r+1 sequential steps, decoding message symbols from highest to lowest degree. Several follow-up decoding algorithms reduced the number of steps, but for a limited set of parameters, or at the expense of reduced performance, or relying on the existence of some combinatorial structures. We show that any one-step majority-logic decoder-that is, a decoder performing all majority votes in one step simultaneously without sequential processing-can correct at most d_min/4 errors for all values of r and m, where d_min denotes the code's minimum distance. We then introduce a new hard-decision decoder that completes the decoding in a single step and attains this error-correction limit. It applies to all r and m, and can be viewed as a parallel realization of Reed's original algorithm, decoding all message symbols simultaneously. Remarkably, we also prove that the decoder is optimum in the erasure setting: it recovers the message from any erasure pattern of up to d_min-1 symbols-the theoretical limit. To our knowledge, this is the first 1-step decoder for RM codes that achieves both optimal erasure correction and the maximum one-step error correction capability.

A. Murad, Thomas E. Fuja