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

Arikan提出了一类新的基于极化的码，称为极性码。预计极性码将为各种编码问题提供低计算和空间复杂度的编解码技术的基本原理。讨论了信源极化和信道极化的近似问题，提出了一种近似极化码的构造方法，通过计算近似极化码的信息量与码字长度N的线性近似值。主要结果如下：(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.