通信路分極とポーラ符号

摘要

低計算複雑度の符号化法，復号法をもち，なおかつ通信路容量に漸近する性能を有する通信路符号化法を構成する問題に対して，ポーラ符号と呼ばれる新たな符号の族が，最近になってArlkanにより提案された．ポーラ符号の符号化，復号の計算複雑度は符号長をNとするとそれぞれO（N log N）である．ポーラ符号はまた，二元入力無記憶通信路に対して長符号長極限において対称通信路容量を漸近的に達成することが厳密に証明されている．本稿では，ポーラ符号が理論的な基礎をおく通信路分極と呼ばれる現象を含めてポーラ符号の基礎的事項を整理するとともに，研究の現状について概説する．