Study on a construction of Polar codes for a binary symmetric channel

Arikan提出了一种新的基于极化的编码，称为极性编码。期望极性码能为各种编码问题提供具有低计算复杂度和空间复杂度的编码和解码技术的基本原理。我们已经用近似的方法讨论了源极化和通道极化，(1) Kurkoski和Yagi针对对称二进制输入无记忆信道或二进制无记忆源，提出了一种利用量化器设计的具有线性复杂度的近似极码的编码构造方法。(2)利用SMAWK算法改进任意二输入离散无记忆信道的量化器设计算法的时间复杂度。

Arikan has proposed a new class of codes, called polar codes, based on the polarization. It is expected that polar codes will provide fundamental principles for encoding and decoding techniques with low computational and space complexities for various coding problems. We have discussed about source polarization and channel polarization with approximation, and have proposed a code construction of approximation polar code by evaluating approximate value of the information in complexity linear with respect to the codeword length N. The main results are followings:(1) A code construction method of approximation polar codes using quantizer design an algorithm was recently proposed by Kurkoski and Yagi with complexity linear for symmetric binary-input memoryless channel or binary memoryless source.(2) An improvement of the time complexity of the quantizer design algorithm using the SMAWK algorithm for arbitrary binary-input discrete memoryless channels.