Decoder for Linear Codes

Kenny Barrese

Linzhi Shen, Fang‐Wei Fu

In this paper, we study the decoding error probability of linear codes over the erasure channel under the list decoding. The notion of the qℓ-incorrigible sets of linear codes is introduced to characterize its decoding error probability under the list decoding or the maximum likelihood decoding. By calculating the qℓ-incorrigible set distributions, the decoding error probability of a linear code over the erasure channel under the list decoding or the maximum likelihood decoding is expressed by its support weight distributions. For the ensemble of all [n,k] linear codes, the average decoding error probability under the maximum likelihood decoding and the average unsuccessful decoding probability under unambiguous decoding are determined. Furthermore, the error exponent of the average unsuccessful decoding probability under the unambiguous decoding is determined for the ensemble of all [n,nR] linear codes.

Martin Bossert, F. Hergert

Lucky Galvez, Jon-Lark Kim

Practically good error-correcting codes should have good parameters and efficient decoding algorithms. Some algebraically defined good codes, such as cyclic codes, Reed–Solomon codes, and Reed–Muller codes, have nice decoding algorithms. However, many optimal linear codes do not have an efficient decoding algorithm except for the general syndrome decoding which requires a lot of memory. Therefore, a natural question to ask is which optimal linear codes have an efficient decoding. We show that two binary optimal [ 36 , 19 , 8 ] linear codes and two binary optimal [ 40 , 22 , 8 ] codes have an efficient decoding algorithm. There was no known efficient decoding algorithm for the binary optimal [ 36 , 19 , 8 ] and [ 40 , 22 , 8 ] codes. We project them onto the much shorter length linear [ 9 , 5 , 4 ] and [ 10 , 6 , 4 ] codes over G F ( 4 ) , respectively. This decoding algorithm, called projection decoding, can correct errors of weight up to 3. These [ 36 , 19 , 8 ] and [ 40 , 22 , 8 ] codes respectively have more codewords than any optimal self-dual [ 36 , 18 , 8 ] and [ 40 , 20 , 8 ] codes for given length and minimum weight, implying that these codes are more practical.

Linzhi Shen, Fang‐Wei Fu

In this paper, we study the list decoding error probability of a linear code over the erasure channel. The notion of L-incorrigible sets of a linear code is introduced to characterize its performance under list decoding. The L-incorrigible set distribution of a linear code can also be used to completely determine its decoding error probability under maximum likelihood decoding over the erasure channel. Furthermore, we show that the L-incorrigible set distribution of a linear code can be determined by its support weight distribution. Finally, the error exponent of the unsuccessful decoding probability under optimal decoding for the ensemble of all [n, nR] linear codes is determined.

Ilya I. Dumer