论文标题
概括性逆解码
Generalized Inverse Based Decoding
论文作者
论文摘要
引入了广义基于逆的解码（GID）的概念，作为综合征解码问题（SDP）和低体重代码字问题（LWP）的代数框架。该框架通过广义逆（GIS）进行了两个表征，一个用于矩阵的无空空间，另一个用于有限场上线性方程系统的解决方案空间。提出了用于SDP和LWP的通用GID求解器。结果表明，信息集解码（ISD）算法，例如Prange，Lee-Brickell，Leon和Stern的算法，是GID求解器的特定情况。他们所有人都在各种特定策略下搜索GIS或零空间的要素。但是，由于论文显示ISD变体并未搜索整个空间，而我们的求解器也只使用一个高斯消除。除此之外，我们的GID框架清楚地表明了除Prange解决方案外，每个ISD算法如何用作SDP或LWP求解器。还提供了从我们的问题（视为优化问题）严重减少到最低问题问题。实验结果表明，GID求解器的行为非常好。易于重量的范围可以通过极少数的迭代来达到，甚至扩大。
The concept of Generalized Inverse based Decoding (GID) is introduced, as an algebraic framework for the syndrome decoding problem (SDP) and low weight codeword problem (LWP). The framework has ground on two characterizations by generalized inverses (GIs), one for the null space of a matrix and the other for the solution space of a system of linear equations over a finite field. Generic GID solvers are proposed for SDP and LWP. It is shown that information set decoding (ISD) algorithms, such as Prange, Lee-Brickell, Leon, and Stern's algorithms, are particular cases of GID solvers. All of them search GIs or elements of the null space under various specific strategies. However, as the paper shows the ISD variants do not search through the entire space, while our solvers do even when they use just one Gaussian elimination. Apart from these, our GID framework clearly shows how each ISD algorithm, except for Prange's solution, can be used as an SDP or LWP solver. A tight reduction from our problems, viewed as optimization problems, to the MIN-SAT problem is also provided. Experimental results show a very good behavior of the GID solvers. The domain of easy weights can be reached by a very few iterations and even enlarged.
