In this paper, we study binary constrained codes that are resilient to bit-flip errors and erasures. In our first approach, we compute the sizes of constrained subcodes of linear codes. Since there exist well-known linear codes that achieve vanishing probabilities of error over the binary symmetric channel (which causes bit-flip errors) and the binary erasure channel, constrained subcodes of such linear codes are also resilient to random bit-flip errors and erasures. We employ a simple identity from the Fourier analysis of Boolean functions, which transforms the problem of counting constrained codewords of linear codes to a question about the structure of the dual code. We illustrate the utility of our method in providing explicit values or efficient algorithms for our counting problem, by showing that the Fourier transform of the indicator function of the constraint is computable, for different constraints. Our second approach is to obtain good upper bounds, using an extension of Delsarte's linear program (LP), on the largest sizes of constrained codes that can correct a fixed number of combinatorial errors or erasures. We observe that the numerical values of our LP-based upper bounds beat the generalized sphere packing bounds of Fazeli, Vardy, and Yaakobi (2015).
翻译:在本文中, 我们研究能适应位翻错误和擦除的二进制限制代码。 在我们的第一种方法中, 我们计算线性代码限制子代码的大小。 由于有众所周知的线性代码, 在二进制对称信道( 导致位翻错误) 和二进制删除通道上, 实现错误概率消失的已知线性代码, 限制线性代码的子代码也具有随机点翻错误和擦除的复原力。 我们从对布林函数的 Freier 分析中采用一个简单的身份, 它将线性代码限制的编码转换成对双进制代码结构的质疑。 我们通过显示 Fourier 约束性指标函数的转换为可兼容性, 取决于不同的限制。 我们的第二个方法是利用 Delsarte 线性程序( LP ) 的扩展获得良好的上限值。 在限制值的最大尺寸上, 能够纠正固定的组合错误数, 并打破了我们压强的压强的Ya- PAR- III 区域。