TY - JOUR

T1 - Weak Flip Codes and their Optimality on the Binary Erasure Channel

AU - Lin, Hsuan Yin

AU - Moser, Stefan Michael

AU - Chen, Po-Ning

PY - 2018/7

Y1 - 2018/7

N2 - This paper investigates fundamental properties of nonlinear binary codes by looking at the codebook matrix not row-wise (codewords), but column-wise. The family of weak flip codes is presented and shown to contain many beautiful properties. In particular the subfamily fair weak flip codes, which goes back to Shannon et al. and which was shown to achieve the error exponent with a fixed number of codewords M , can be seen as a generalization of linear codes to an arbitrary number of codewords. The fair weak flip codes are related to binary nonlinear Hadamard codes. Based on the column-wise approach to the codebook matrix, the r -wise Hamming distance is introduced as a generalization to the well-known and widely used (pairwise) Hamming distance. It is shown that the minimum $r$ -wise Hamming distance satisfies a generalized r -wise Plotkin bound. The r -wise Hamming distance structure of the nonlinear fair weak flip codes is analyzed and shown to be superior to many codes. In particular, it is proven that the fair weak flip codes achieve the $r$ -wise Plotkin bound with equality for all $r$. In the second part of this paper, these insights are applied to a binary erasure channel with an arbitrary erasure probability 0 < δ < 1. An exact formula for the average error probability of an arbitrary (linear or nonlinear) code using maximum likelihood decoding is derived and shown to be expressible using only the $r$ -wise Hamming distance structure of the code. For a number of codewords M satisfying M 4 and an arbitrary finite blocklength $n$ , the globally optimal codes (in the sense of minimizing the average error probability) are found. For M = 5 or M = 6 and an arbitrary finite blocklength $n$ , the optimal codes are conjectured. For larger M , observations regarding the optimal design are presented, e.g., that good codes have a large r -wise Hamming distance structure for all r. Numerical results validate our code design criteria and show the superiority of our best found nonlinear weak flip codes compared with the best linear codes.

AB - This paper investigates fundamental properties of nonlinear binary codes by looking at the codebook matrix not row-wise (codewords), but column-wise. The family of weak flip codes is presented and shown to contain many beautiful properties. In particular the subfamily fair weak flip codes, which goes back to Shannon et al. and which was shown to achieve the error exponent with a fixed number of codewords M , can be seen as a generalization of linear codes to an arbitrary number of codewords. The fair weak flip codes are related to binary nonlinear Hadamard codes. Based on the column-wise approach to the codebook matrix, the r -wise Hamming distance is introduced as a generalization to the well-known and widely used (pairwise) Hamming distance. It is shown that the minimum $r$ -wise Hamming distance satisfies a generalized r -wise Plotkin bound. The r -wise Hamming distance structure of the nonlinear fair weak flip codes is analyzed and shown to be superior to many codes. In particular, it is proven that the fair weak flip codes achieve the $r$ -wise Plotkin bound with equality for all $r$. In the second part of this paper, these insights are applied to a binary erasure channel with an arbitrary erasure probability 0 < δ < 1. An exact formula for the average error probability of an arbitrary (linear or nonlinear) code using maximum likelihood decoding is derived and shown to be expressible using only the $r$ -wise Hamming distance structure of the code. For a number of codewords M satisfying M 4 and an arbitrary finite blocklength $n$ , the globally optimal codes (in the sense of minimizing the average error probability) are found. For M = 5 or M = 6 and an arbitrary finite blocklength $n$ , the optimal codes are conjectured. For larger M , observations regarding the optimal design are presented, e.g., that good codes have a large r -wise Hamming distance structure for all r. Numerical results validate our code design criteria and show the superiority of our best found nonlinear weak flip codes compared with the best linear codes.

KW - Binary erasure channel (BEC)

KW - finite blocklength

KW - generalized Plotkin bound

KW - maximum likelihood (ML) decoder

KW - minimum average error probability

KW - optimal nonlinear code design

KW - r-wise Hamming distance

KW - weak flip codes

KW - GENERALIZED HAMMING WEIGHTS

KW - DIGITAL INFORMATION

KW - BOUNDS

KW - STORAGE

UR - http://www.scopus.com/inward/record.url?scp=85046764553&partnerID=8YFLogxK

U2 - 10.1109/TIT.2018.2834924

DO - 10.1109/TIT.2018.2834924

M3 - Article

AN - SCOPUS:85046764553

SN - 0018-9448

VL - 64

SP - 5191

EP - 5218

JO - IEEE Transactions on Information Theory

JF - IEEE Transactions on Information Theory

IS - 7

ER -