Message Passing Decoding of Codes from Complete Graphs

Francisco Chamera and Khumbo Kumwenda

Abstract:

We describe iterative decoding of binary codes from incidence matrices of complete graphs. Parameters for these codes are well known. The codes are also known to be low density parity-check (LDPC). We determine cases where they are decodable by bit flipping (BF) and sum product (SP) decoding algorithms.

Let c be a codeword from the binary code from an incidence matrix of a complete graph. Suppose c is sent through the binary symmetric channel (BSC) with parameter p. Let N and k be the length and dimension of the code respectively. We show that errors occurring in the first k positions are correctable by SP while those occurring in the last N-k positions are correctable by BF.

Keywords: Binary Symmetric Channel, Bit flipping; Complete graphs; Incidence matrix; LDPC codes; Linear code; Sum product; Tanner graph.

Pages: 75 – 88 | Full PDF Paper