We consider near maximum-likelihood (ML) decoding of short linear block codes
based on neural belief propagation (BP) decoding recently introduced by
Nachmani et al.. While this method significantly outperforms conventional BP
decoding, the underlying parity-check matrix may still limit the overall
performance. In this paper, we introduce a method to tailor an overcomplete
parity-check matrix to (neural) BP decoding using machine learning. We consider
the weights in the Tanner graph as an indication of the importance of the
connected check nodes (CNs) to decoding and use them to prune unimportant CNs.
As the pruning is not tied over iterations, the final decoder uses a different
parity-check matrix in each iteration. For Reed-Muller and short low-density
parity-check codes, we achieve performance within 0.27 dB and 1.5 dB of the ML
performance while reducing the complexity of the decoder.

本文提出了一种使用机器学习来定制超完备校验矩阵的方法，通过裁剪不重要的检测节点并优化 Tanner 图中的权重，每个迭代使用不同的校验矩阵，从而在短线性块码上，实现比 BP 译码更好的性能且减少了解码器的复杂度。

神经置信传播解码器修剪

Pruning Neural Belief Propagation Decoders

Linear programming (LP) decoding approximates maximum-likelihood (ML)
decoding of a linear block code by relaxing the equivalent ML integer
programming (IP) problem into a more easily solved LP problem. The LP problem
is defined by a set of box constraints together with a set of linear
inequalities called "parity inequalities" that are derived from the constraints
represented by the rows of a parity-check matrix of the code and can be added
iteratively and adaptively. In this paper, we first derive a new necessary
condition and a new sufficient condition for a violated parity inequality
constraint, or "cut," at a point in the unit hypercube. Then, we propose a new
and effective algorithm to generate parity inequalities derived from certain
additional redundant parity check (RPC) constraints that can eliminate
pseudocodewords produced by the LP decoder, often significantly improving the
decoder error-rate performance. The cut-generating algorithm is based upon a
specific transformation of an initial parity-check matrix of the linear block
code. We also design two variations of the proposed decoder to make it more
efficient when it is combined with the new cut-generating algorithm. Simulation
results for several low-density parity-check (LDPC) codes demonstrate that the
proposed decoding algorithms significantly narrow the performance gap between
LP decoding and ML decoding.

本研究提出了一种新的算法来生成奇偶校验不等式，用于解码线性分组码，可以通过消除线性规划解码器产生的赝码字显著提高解码器误码率性能，并实现了与 ML 解码之间的性能接近。

自适应割生成算法改进二元线性码线性规划译码

Adaptive Cut Generation Algorithm for Improved Linear Programming  Decoding of Binary Linear Codes

It is now well known that the performance of a linear code $C$ under
iterative decoding on a binary erasure channel (and other channels) is
determined by the size of the smallest stopping set in the Tanner graph for
$C$. Several recent papers refer to this parameter as the \emph{stopping
distance} $s$ of $C$. This is somewhat of a misnomer since the size of the
smallest stopping set in the Tanner graph for $C$ depends on the corresponding
choice of a parity-check matrix. It is easy to see that $s \le d$, where $d$ is
the minimum Hamming distance of $C$, and we show that it is always possible to
choose a parity-check matrix for $C$ (with sufficiently many dependent rows)
such that $s = d$. We thus introduce a new parameter, termed the \emph{stopping
redundancy} of $C$, defined as the minimum number of rows in a parity-check
matrix $H$ for $C$ such that the corresponding stopping distance $s(H)$ attains
its largest possible value, namely $s(H) = d$.
We then derive general bounds on the stopping redundancy of linear codes. We
also examine several simple ways of constructing codes from other codes, and
study the effect of these constructions on the stopping redundancy.
Specifically, for the family of binary Reed-Muller codes (of all orders), we
prove that their stopping redundancy is at most a constant times their
conventional redundancy. We show that the stopping redundancies of the binary
and ternary extended Golay codes are at most 35 and 22, respectively. Finally,
we provide upper and lower bounds on the stopping redundancy of MDS codes.

研究线性编码在二元擦除通道上的表现，发现停止图中最小停止集的大小决定了编码的性能，并引入了停止冗余参数来描述这个特性。进一步探讨了线性编码的停止冗余及其构造方法和限制。研究表明，对于二进制 Reed-Muller 编码，他们的停止冗余最多是他们传统冗余的常数倍。同时，二进制和三进制扩展 Golay 码的停止冗余分别不超过 35 和 22。