Berman Codes: A Generalization of Reed–Muller Codes That Achieve BEC Capacity
Lakshmi Prasad Natarajan, Prasad Krishnan · IEEE Transactions on Information Theory · 2023
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$\mathscr {C}_{n}(r,m)$, and their duals are denoted as$\mathscr {B}_{n}(r,m)$. The length of these codes is$n^{m}$, where$n \geq 2$, and$r$is their ‘order’. When$n=2$,$\mathscr {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$\mathscr {B}_{n}(r,m)$as the Berman code and$\mathscr {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$\mathscr {B}_{n}(r,m)$and$\mathscr {C}_{n}(r,m)$and which achieves BEC capacity.