The Stopping Set Property and the Iterative Decoding Performance of Binary Block Codes on BSC and AWGN Channel

Abstract

In the field of Error Correcting Coding (ECC), the concept of ''stopping set'' recently became a hot topic. A stopping set for a parity-check matrix is the set of bits which would cause the iterative decoding progress in Binary Erasure Channel (BEC) to ''stop'' when it is erased. It has already been proved in several papers that the decoding performance under iterative decoding algorithm of any linear block code in BEC is determined by their stopping set performance, in particular, their size and number. And it is commonly assumed by the coding researchers that those codes which have better stopping set performance would also perform better in other channels. In this thesis, the decoding performance of linear block codes, in particular, Hamming Codes, the original LDPC code proposed by Gallager and FG-LDPC codes is studied in Binary Symmetric Channel (BSC) and Additive White Gaussian Noise (AWGN) channel. Three iterative decoding algorithms, respectively Bit-Flipping algorithm, Weighted Bit-Flipping algorithm and Sum Product Algorithm are used. To emphasize the influence of stopping set property, the parity-check matrix for each code is modified by adding linearly dependent rows to the original parity-check matrix, or removing rows from it. These modifications are made in order to change the stopping set property of the codes. The performance of the modified parity-check matrices is thus analyzed, by comparing them to the original ones, using both theoretical analysis and simulation. The results show that the stopping set performance of linear block codes is not a crucial factor to their performances on other channels as it is in BEC. Sometimes the linear block codes of a better stopping set property do perform better in other channels, but sometimes the performance barely changes or even degrades. More precisely, the decoding performance of a certain parity-check matrix is determined by the type of codes, the type of channel and the decoding algorithm, rather than its stopping set property.