IIIT Hyderabad Publications |
|||||||||
|
On Polar Codes with Product Kernels and Polarisation of RM CodesAuthor: Manan Bhandari Date: 2020-11-12 Report no: IIIT/TH/2020/98 Advisor:Lalitha Vadlamani AbstractToday the communication technology relies on state of the art in networks, which is lead by 5G. Polar codes are one such class of codes known to achieve very high speed in 5G. Any message that needs to be transferred from a noisy channel requires encoding and decoding to keep the message intact and not let the noise corrupt it. Using polar codes, transmission can be done at a rate arbitrarily close to capacity and decoded at the receiver with very small probability of error. These codes, introduced by Arikan, achieve the capacity of arbitrary binary-input discrete memoryless channel W under successive cancellation decoding. For any such channel having capacity I(W) and for any coding scheme allowing transmission at rate R, the scaling exponent is a parameter that characterizes how fast the gap to capacity decreases as a function of code length N for a fixed probability of error. Scaling exponent for small-sized kernels up to L = 8 has been exhaustively found, but as kernel size increases, the complexity to find this exponent increases. In this thesis, we find a simple solution to reduce complexity of finding the scaling exponent for a specific type of kernel. We consider product kernels TL obtained by taking Kronecker product of component kernels and derive the properties of polarizing product kernels relating to the number of product kernels, self-duality and partial distances in terms of the respective properties of the smaller component kernels. Subsequently, the polarization behavior of component kernel Tl is used to calculate scaling exponent of TL = T2 ⊗Tl , which has lower complexity as compared to the basic method. Using this method, we show that µ(T2 ⊗ T5) = 3.942. Further, we employ a heuristic approach to construct a good kernel of L = 14 from kernel having size l = 8 having best µ and find µ(T2 ⊗ T7) = 3.485. Plotting all these values, we make some interesting observations about the nature of this parameter as kernel size increases. Further, the work of this thesis which focuses on finding scaling exponent for a specific type of kernel (T2 ⊗ Tl), can be extended to any general kernel. This will result in calculating scaling exponent much efficiently. Another interesting problem to solve is to find if the scaling exponent for modified polar codes like polar subcodes or RM codes exists and, if so, finding those values. RM codes are known to polarize as well, and an algorithm to find the basis matrix of any RM(m, r) codes are presented in the thesis, which leads to the generator matrix of these codes needed for encoding. Another category of codes that are very similar to RM codes are twin codes, and it is conjectured that under certain conditions, twin codes are equal to RM codes for binary symmetric channel (BSC). We give a detailed proof of them being same till m = 4 and conclude the proof for a particular case of any general m. Full thesis: pdf Centre for Others |
||||||||
Copyright © 2009 - IIIT Hyderabad. All Rights Reserved. |