Berman Codes: A Generalization of Reed-Muller Codes that Achieve BEC Capacity
share
We identify a family of binary codes whose structure is similar to Reed-Muller (RM) codes and which include RM codes as a strict subclass. The codes in this family are denoted as C_n(r,m), and their duals are denoted as B_n(r,m). The length of these codes is n^m, where n ≥ 2, and r is their `order'. When n=2, C_n(r,m) is the RM code of order r and length 2^m. The special case of these codes corresponding to n being an odd prime was studied by Berman (1967) and Blackmore and Norton (2001). Following the terminology introduced by Blackmore and Norton, we refer to B_n(r,m) as the Berman code and C_n(r,m) as the dual Berman code. We identify these codes using a recursive Plotkin-like construction, and we show that these codes have a rich automorphism group, they are generated by the minimum weight codewords, and that they can be decoded up to half the minimum distance efficiently. Using a result of Kumar et al. (2016), we show that these codes achieve the capacity of the binary erasure channel (BEC) under bit-MAP decoding. Furthermore, except double transitivity, they satisfy all the code properties used by Reeves and Pfister to show that RM codes achieve the capacity of binary-input memoryless symmetric channels. Finally, when n is odd, we identify a large class of abelian codes that includes B_n(r,m) and C_n(r,m) and which achieves BEC capacity.
READ FULL TEXT