A note on a decoding algorithm of codes on graphs with small loops

Author

Kobayashi, Naoto ; Matsushima, Toshiyasu ; Hirasawa, Shigeichi

Author_Institution

Sch. of Sci. & Eng., Waseda Univ., Tokyo, Japan

fYear

2005

fDate

29 Aug.-1 Sept. 2005

Abstract

The best-known algorithm for the decoding of low-density parity-check (LDPC) codes is the sum-product algorithm (SPA). The SPA is a message-passing algorithm on a graphical model called a factor graph (FG). The performance of the SPA depends on a structure of loops in a FG. Pearl showed that loops in a graphical model could be erased by the clustering method. This method clusters plural nodes into a single node. In this paper, we show several examples about a decoding on a FG to which the clustering method is applied. And we propose an efficient decoding algorithm for it. For a binary erasure channel (BEC), the performance with this method goes up clearly.

Keywords

decoding; message passing; parity check codes; pattern clustering; binary erasure channel; clustering method; decoding algorithm; factor graph; graphical model; low density parity check codes; message-passing algorithm; sum-product algorithm; Character generation; Clustering algorithms; Clustering methods; Computational complexity; Decoding; Graphical models; Parity check codes; Probability; Random variables; Sum product algorithm;

fLanguage

English

Publisher

ieee

Conference_Titel

Information Theory Workshop, 2005 IEEE

Print_ISBN

0-7803-9480-1

Type

conf

DOI

10.1109/ITW.2005.1531867

Filename

1531867