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.

翻译：作为综合解码问题(SDP)和低重量编码问题(LWP)的代数框架,引入了普遍化反向解码(GID)的概念。该框架基于两种特征,一种是通用反向(GIs),一种是矩阵空格,另一种是线性方程系统在有限字段上的解决空间。为SDP和LWP提出了通用的GID解码(ISD)算法。显示信息集解码(ISD)算法(ISD)算法,如Prange、Lee-Brickell、Leon和Stern的算法,是GID解算法的特例。所有信息集解算法都以一般反向反向反向反向反向反向反向的空格(GISD)或空格元素进行搜索,然而,文件显示ISD变量不在整个空间进行搜索,而我们的解算法即使只用一个高斯清除法。此外,我们的GID框架还清楚显示,除Prange(Prange)的解码之外,每种ISD算法都可被用作SDP或LWP解算法的解算法。从我们最容易的实验性地展示问题,从GISD的精确的模型可以显示一个问题,从GISD的缩小到最重的精确的系统,从一个问题可以展示到最重的磨问题。