Breaking Cycles with Dummy Bits: Improved Rate-Compatible LDPC Codes with Short Block Lengths

Abstract:
It is well-known that the presence of cycles in a factor graph degrades the performance of message-passing algorithms due to the violation of the assumption of statistical independence of messages. While finding and counting all cycles in a graph is a very hard problem, efficient algorithms have been proposed recently to find all short cycles up to some maximum length. For the message-passing decoding of Low-Density Parity-Check (LDPC) codes, these short cycles are the main cause for the existing performance gap to optimal Maximum Likelihood (ML) decoding. In this paper, we exploit this observation in the proposed novel method of realizing rate-compatible (RC) LDPC codes with short block lengths by inserting known dummy bits into the information bit sequence before encoding. This technique can be seen as a special case of traditional code shortening and allows to achieve lower code rates using one fixed rate mother code. The novelty of the proposed method lies in the selection of the specific dummy bit positions in a way that “breaks” a significant number of short cycles in the mother code’s graph which, thus, no longer degrade the decoding performance.