Rengaswamy, Narayanan (2015-12). On Cyclic Polar Codes and the Burst Erasure Performance of Spatially-Coupled LDPC Codes. Master's Thesis. Thesis uri icon

abstract

  • In this thesis, we produce our work on two of the state-of-the-art techniques in modern coding theory: polar codes and spatially-coupled LDPC codes. Polar codes were introduced in 2009 and proven to achieve the symmetric capacity of any binary-input discrete memoryless channel under low-complexity successive cancellation decoding. Since then, finite length (non-asymptotic) performance has been the primary concern with respect to polar codes. In this work, we construct cyclic polar codes based on a mixed-radix Cooley-Tukey decomposition of the Galois field Fourier transform. The main results are: we can, for the first time, construct, encode and decode polar codes that are cyclic, with their blocklength being arbitrary; for a given target block erasure rate, we can achieve significantly higher code rates on the erasure channel than the original polar codes, at comparable blocklengths; on the symmetric channel with only errors, we can perform much better than equivalent rate Reed-Solomon codes with the same blocklength, by using soft-decision decoding; and, since the codes are subcodes of higher rate RS codes, a RS decoder can be used if suboptimal performance suffices for the application as a trade-o_ for higher decoding speed. The programs developed for this work can be accessed at https://github.com/nrenga/cyclic_polar. In 2010, it was shown that spatially-coupled low-density parity-check (LDPC) codes approach the capacity of binary memoryless channels, asymptotically, with belief-propagation (BP) decoding. In our work, we are interested in the finite length average performance of randomly coupled LDPC ensembles on binary erasure channels with memory. The significant contributions of this work are: tight lower bounds for the block erasure probability (PB) under various scenarios for the burst pattern; bounds focused on practical scenarios where a burst affects exactly one of the coupled codes; expected error floor for the bit erasure probability (Pb) on the binary erasure channel; and, characterization of the performance of random regular ensembles, on erasure channels, with a single vector describing distinct types of size-2 stopping sets. All these results are verified using Monte-Carlo simulations. Further, we show that increasing variable node degree combined with expurgation can improve PB by several orders of magnitude in the number of bits per coupled code.
  • In this thesis, we produce our work on two of the state-of-the-art techniques in modern coding theory: polar codes and spatially-coupled LDPC codes.
    Polar codes were introduced in 2009 and proven to achieve the symmetric capacity of any binary-input discrete memoryless channel under low-complexity successive cancellation decoding. Since then, finite length (non-asymptotic) performance has been the primary concern with respect to polar codes. In this work, we construct cyclic polar codes based on a mixed-radix Cooley-Tukey decomposition of the Galois field Fourier transform. The main results are: we can, for the first time, construct, encode and decode polar codes that are cyclic, with their blocklength being arbitrary; for a given target block erasure rate, we can achieve significantly higher code rates on the erasure channel than the original polar codes, at comparable blocklengths; on the symmetric channel with only errors, we can perform much better than equivalent rate Reed-Solomon codes with the same blocklength, by using soft-decision decoding; and, since the codes are subcodes of higher rate RS codes, a RS decoder can be used if suboptimal performance suffices for the application as a trade-o_ for higher decoding speed. The programs developed for this work can be accessed at https://github.com/nrenga/cyclic_polar.
    In 2010, it was shown that spatially-coupled low-density parity-check (LDPC) codes approach the capacity of binary memoryless channels, asymptotically, with belief-propagation (BP) decoding. In our work, we are interested in the finite length average performance of randomly coupled LDPC ensembles on binary erasure channels with memory. The significant contributions of this work are: tight lower bounds for the block erasure probability (PB) under various scenarios for the burst pattern; bounds focused on practical scenarios where a burst affects exactly one of the coupled codes; expected error floor for the bit erasure probability (Pb) on the binary erasure channel; and, characterization of the performance of random regular ensembles, on erasure channels, with a single vector describing distinct types of size-2 stopping sets. All these results are verified using Monte-Carlo simulations. Further, we show that increasing variable node degree combined with expurgation can improve PB by several orders of magnitude in the number of bits per coupled code.

publication date

  • December 2015