Belief propagation decoding using factor graph permutations

Tosun, Berna
Capacity-achieving polar codes, introduced by Arıkan have attracted significant attention over a decade. The bottleneck in coding is the decoder structure that achieves good performance with low hardware implementation cost and high throughput. Unlike the successive cancellation decoder, belief propagation decoder that can be improved by decoding on multiple factor graphs, allows for parallel decoding. For a polar code of length N, there are ({u1D459}{u1D45C}{u1D454}2{u1D441})!={u1D45B}!different permutations of the layers in the factor graph. Multiple factor graph belief propagation decoders that employ {u1D45B}factor graphs have the complexity of O({u1D441}(log{u1D441})2), and the choice of proper sets among {u1D45B}!factor graphs for performance optimization is a challenging topic that has not yet been fully explored. n this thesis, belief propagation decoding performance of polar codes over the additive white Gaussian noise channel is studied, by using single or multiple factor graphs within the decoder. The performance gap between the best and worst single factor graph decoders is found; and for multiple factor graph decoders, it is shown that random choice of factor graphs is incompetent for long code lengths. Two set-choice methods, MaxSON and MaxofMax rules are suggested for multiple factor graph decoders with nelements, as an alternative to the cyclically shifted set of factor graphs. viPerformance of proposed set-choice rulesare compared with cyclic, randomand two other multiple factor graph belief propagation decoders given in the literature, for different code lengths with 6 ≤{u1D459}{u1D45C}{u1D454}2{u1D441}≤14