Message Passing Decoding of Codes from Complete Graphs

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  be a codeword from the binary code from an incidence matrix of a complete graph. Suppose  is sent through the binary symmetric channel (BSC) with parameter . Let N and  be the length and dimension of the code respectively. We show that errors occurring in the first  positions are correctable by SP while those occurring in the last N− positions are correctable by BF. Keywords: Binary Symmetric Channel, Bit flipping; Complete graphs; Incidence matrix; LDPC codes; Linear code; Sum product; Tanner graph.