Title :
Generalized minimum distance iterative decoding of expander codes
Author :
Skachek, Vitaly ; Roth, Ron M.
Author_Institution :
Dept. of Comput. Sci., Technion-Israel Inst. of Technol., Haifa, Israel
Abstract :
Recently, G. Zemor (see IEEE Trans. Inf. Theory, vol.47, p.835-7, 2001) proposed an improvement on the Sipser-Spielman analysis of expander codes (Sipser, M. and Spielman, D.A., IEEE Trans. Inf. Theory, vol.42 , p.1710-22, 1996) and presented a linear-time iterative decoder that can correct a number of errors up to approximately 1/4 the known lower bound on the minimum distance of the code. We propose an improvement on Zemor´s decoder for F=GF(2), with the number of correctable errors becoming close to half the lower bound on the minimum distance. The improvement is obtained by inserting into the decoding algorithm features akin to generalized minimum distance decoding of concatenated codes.
Keywords :
Galois fields; codes; graph theory; iterative decoding; bipartite graph; bipartite undirected graph; concatenated codes; correctable errors; expander codes; generalized minimum distance decoding; iterative decoding; lower bound; minimum distance; Computer errors; Computer science; Concatenated codes; Eigenvalues and eigenfunctions; Error correction; Error correction codes; Graph theory; Hamming weight; Iterative algorithms; Iterative decoding;
Conference_Titel :
Information Theory Workshop, 2003. Proceedings. 2003 IEEE
Print_ISBN :
0-7803-7799-0
DOI :
10.1109/ITW.2003.1216740
