2入力対称通信路における近似Polar符号の動的計画法を用いた符号構成に関する考察

摘要

与えられた2入力定常無記憶通信路に対してPolar符号の構成を考える場合，Arikanの定義したPolar符号を正確に構成する多項式時間の構成方法は，通信路が2元消失通信路の場合を除いては明確には知られていない．Arikanの定義したPolar符号を正確に構成する代わりに近似的な構成法であれば符号長の多項式時間で提案されている．小文では2入力対称通信路における通信路容量と同じ通信路容量をもつ2元対称通信路の結合の形式を確認し，2元対称通信路の結合において動的計画法を用いた通信路容量の近似を述べ，Polar符号の近似を用いた構成法を述べる．