Weak Flip Codes and Applications to Optimal Code Design on the Binary Erasure Channel

Abstract

A new family of nonlinear codes, called weak flip codes,is presented and is shown to contain many beautiful properties. In particular, the subfamily of fair weak flip codes can be seen as a generalization of linear codes. Different from linear codes that only exist for a number of codewords M being an integer-power of 2, the fair weak flip code can be defined for an arbitrary M. It is then noted that the fair weak flip codes are related to binary nonlinear Hadamard codes : both code families maximize the minimum Hamming distance and meet the Plotkin bound. However, while the binary nonlinear Hadamard codes have only been shown to possess good Hamming-distance properties, the fair weak flip codes are proven to be globally optimal (in the sense of minimizing the error probability) among all linear or nonlinear codes for the binary erasure channel (BEC) for many values of the blocklength n and for M <= 6. For M > 6, similar optimality results are conjectured. The results in this paper are founded on a new powerful tool for the analysis and generation of block codes: the column-wise approach to the codebook matrix.