1非対称通信路の通信路容量を達成する
符号化法に関する最近の進展

東京大学 大学院新領域創成科学研究科
複雑理工学専攻 講師
本多 淳也
情報理論研究会 2018/5/18

2

概要• 非対称通信路の符号化• polar符号を用いる方式• 無歪み圧縮を用いた符号化法の一般的な枠組み• Miyake-Muramatsuの方式• 連鎖構造に基づく方式• 無歪み圧縮の逆操作について

3

通信路符号化• ノイズを含む通信路を用いて情報を伝送したい≭ ビットのメッセージを ≮ ∾ ≭ ビットに冗長化して送信∨≘∱∻ ≘∲∻ ⊢ ⊢ ⊢ ∻ ≘≮∩≕ ≭ 符号器 ≘ ≮ 通信路 ≗ ≙ ≮ 復号器 ≕≞ ≭≐≙ ≪≘ ∨≹≪≸∩ ∽ ≗ ∨≹≪≸∩• 達成可能な符号化率 ≒ ∽ ≭∽≮ の上限： 通信路容量≃ ∨≗ ∩ ∽ ≭≐≡≘≸ ≉ ∨≘ ∻ ≙ ∩ ∽ ≭≐≡≘≸≦≈ ∨≘ ∩ ⊡ ≈ ∨≘ ≪≙ ∩≧•4対称通信路の符号化≃ ∨≗ ∩ ∽ ≭≐≡≘≸ ≉ ∨≘ ∻ ≙ ∩• 符号語の各シンボルの頻度分布は ≐≘ に近い必要がある• 通信路が対称な場合： ≐≘ は一様分布 → 線形符号で OK≃ ∽ ≦≸≮ ∲ ≦∰∻ ∱≧≮ ∺ ≸≮∱ ≈ ∽ ∰≧∻ ≪≃≪ ∽ ∲≭≮ ⊣ ∨≮ ⊡ ≭∩ 行列，≭∽≮ ⊼ ≃ ∨≗ ∩• ≈ のとり方： ランダム行列・LDPC 行列・polar 符号……
通信路容量：

01

≰≰

∱⊡≰

∱⊡≰

01

5

非対称通信路の符号化• 最適な入力分布は一般に非一様• 通信路容量を達成するには一様分布にしたがうメッセージを頻度分布の偏った符号語に変換する必要がある

≘
≪
∱
∲
≗
∨
≹
≸
∩
≉≳∨≗ ∩ ∽ ∲ ≗ ∨≹≪≸∩ ≬≯≧ ≗ ∨≹≪∰∩ ∫ ≗ ∨≹≪∱∩ ⊷ ≃ ∨≗ ∩≸∻ ≹• 一様入力で達成できる符号化率は≐≘ ∨∰∩ ∽ ∳∽∵0≐≘ ∨∱∩ ∽ ∲∽∵1∱∱∽∲

∱∽∲

01

6Gallager の方法∨≐ ∨∰∩∻ ≐≮≘ ∨∱∩∩ ∽ ∨∲∽≮∳∻ ∱∽≮∳∩ としたい場合：≦≸≾ ∲ ≦∰∻ ∱∻ ∲≧ ∺ ≸≾ ≈ ∽ ∰≧ の• 入力分布を ≘1) 3 元線形符号

符号語を生成する∸∼∰∻≸≾∽∰∻∱≩≸≩ ∺∽ ∺∱∻ ≸≾ ∽ ∲≩2) 2 元の符号語に写像する•

アルファベットサイズは計算量に関わるので大きくしにくい••≐ ∨≸∩ ∽ ≩∽∲≭ の形の分布を表現
m-user MAC を用いて ≘する方法も一応ある [Abbe-Telatar, 2012]

場合によっては誤り率や平均歪みも悪くなる

7概要• 非対称通信路の符号化• polar符号を用いる方式• 無歪み圧縮を用いた符号化法の一般的な枠組み• Miyake-Muramatsuの方式• 連鎖構造に基づく方式• 無歪み圧縮の逆操作について

8Polar 符号• 通信路分極を利用した符号• ２元対称通信路に対して通信路容量を達成 [Arikan, 2008]• 一般の通信路に対しても拡張可能• 多元通信路 [Sasoglu+, 2009, Mori-Tanaka, 2010]• 非対称通信路 [Honda-Yamamoto, 2012]• マルコフ通信路 [Sasoglu, 2011][Wang+, 2015][Sasoglu-Tal, 2016]• 無歪み圧縮や有歪み圧縮等の他の問題にも適用可能

≰≮∩⊡
≏
∨∲

≮

• 動的計画法により符号長 に対して計算量誤り確率を達成≏∨≮ ≬≯≧ ≮∩,9エントロピーの分極• ≘∱ ∻ ≘∲ ∲ ≦∰∻ ∱≧ : 分布 ≐≘ に独立にしたがう確率変数• ∨≕∱ ∻ ≕∲ ∩ ∽ ∨≘∱ ⊩ ≘∲ ∻ ≘∲ ∩≕∱ ∫ ≘∱≕∲≘∲• ≈ ∨≘ ∱ ∻ ≘ ∲ ∩ ∽ ≈ ∨≕∱ ∻ ≕ ∲ ∩∽ ≈ ∨≕∱ ∩ ∫ ≈ ∨ ≕∲ ≪ ≕∱ ∩∨∱∩∨∱∩≈∱ ∾ ≈∲• エントロピーが大きいものと小さいものに分離10エントロピーの分極• 同じ回路をコピー≕∱≕∲≕∳≕∴• お互いの回路は交わっていないので∫∫≘∱≘∲≘∳≘∴≈ ∨≕∱∩ ∽ ≈∱∨∱∩ ∽ ≈ ∨≕∲≪≕∱∩∻≈ ∨≕∳≪≕∱∲∩ ∽ ≈∲∨∱∩ ∽ ≈ ∨≕∴≪≕∱∳∩

11

エントロピーの分極• 同等なビット同士を結合

≕∱
≕∲≕∳
≕∴

∫∫∫

∫

• 対称性が崩れて≘∱≘∲≘∳≘∴≈ ∨≕∱∩ ∾ ≈∱∨∲∩ ∾ ≈ ∨≕∲≪≕∱∩∻≈ ∨≕∳≪≕∱∲∩ ∾ ≈∲∨∲∩ ∾ ≈ ∨≕∴≪≕∱∳∩• エントロピーの総和は結合前と同じ

12

エントロピーの分極• 以下 1,2 の操作を再帰的に繰り返す
1. 同じ回路を２個にコピーする
2. それぞれの回路で同等な位置のビットを∫の回路で結合する• エントロピーの和は結合前後で変わらない• 結合後はエントロピーが大小に分離• マルチンゲールの収束定理より，最終的に≕∱≮ ∽ ≇≘∱≮ のうち≈ ∨≕≩≪≕∱≩⊡∱∩ ⊼ ∱ ∺ ≮≈ ∨≘ ∩ 個• ≈ ∨≕≩ ≪≕∱≩⊡∱ ∩ ⊼ ∰ ∺ ≮∨∱ ⊡ ≈ ∨≘ ∩∩ 個•

13

Polar 符号による固定長無歪み圧縮≘∱≮ を，かわりに ≕∱≮ ∽ ≇≘∱≮ で表現する• ≈ ∨≕≩ ≪≕∱≩⊡∱ ∩ ⊼ ∰ : 凍結ビット≕≩ の情報は ≕∱≩⊡∱ を見ればほぼ一意に定まる• ≈ ∨≕≩ ≪≕∱≩⊡∱ ∩ ⊼ ∱ : 情報ビット≕≩ の情報は ≕∱≩⊡∱ を見ても全く分からない（一様ランダム）• 情報ビットの値だけを送信すれば受信者は ≕∱≮ 全体を復元可能→ ≘∱≮ ∽ ≇⊡∱ ≕∱≮ ∽ ≇≕∱≮ も復元可能• 偏りのある系列≕∱≘∱≕∮ ∲ ≇ ≘∮ ∲
∮
∮≘∴
≕∴

14

Polar 符号による対称通信路符号化• 一様分布にしがたう系列≘∱≮ を送信して ≙∱≮ を受信≈ ∨≕≩≪≕∱≩⊡∱∻ ≙≩∱⊡≮∱∩ ⊼ ∰≮: 情報ビット≕≩ の情報は ≕∱ と ≙∱ を見ればほぼ一意に定まる• ≈ ∨≕≩ ≪≕∱≩⊡∱ ∻ ≙∱≮ ∩ ⊼ ∱ : 凍結ビット≕≩ の情報は ≕∱≩⊡∱ と ≙∱≮ を見ても全く分からない•• 凍結ビットの情報を事前に固定しておけば，受信者は情報ビットに割り振られたメッセージを復元可能≕∱≘∱≕∮ ∲ ≇ ≘∮ ∲∮∮≘∴≕∴≗ ≙∱≗∮ ≙∮∲∮ ∮≗ ≙∴15非対称通信路の場合≐• 通信路容量を達成するためには通信路への入力系列一様でない分布 ≘ に従っていなければならない≘∱≮ が• 凍結ビットの値を固定すると線形符号になってしまうので非一様な入力分布を構成できない• エントロピーの分極を用いて非一様な系列を生成すればよい≕∱≘∱≕∮ ∲ ≇ ≘∮ ∲∮∮≘∴≕∴≗ ≙∱≗∮ ≙∮∲∮ ∮≗ ≙∴16

多段階の分極•≘∱≮ が一様でない場合には ≈ ∨≕≩≪≕∱≩⊡∱∩ と ≈ ∨≕≩≪≕∱≩⊡∱∻ ≙∱≮∩の両方について分極が生じる≈∨≕≩ ≪≕∱≩⊡∱∩ ⊼ ∰ ≈ ∨≕≩ ≪≕∱≩⊡∱∩ ⊼ ∱≈ ∨≕≩≪≕∱≩⊡∱∻ ≙∱≮∩ ⊼ ∰ ≮∨∱ ⊡ ≈ ∨≘ ∩∩ bits ≮≃ ∨≗ ∩ bits≮≈ ∨≘ ≪≙ ∩ bits
≈ ∨≕≩≪≕∱≩⊡∱∻ ≙∱≮∩ ⊼ ∱0 bits≕∱≘∱≕∮ ∲ ≇ ≘∮ ∲∮∮≘∴≕∴≗ ≙∱≗∮ ≙∮∲∮ ∮≗ ≙∴17多段階の分極•≘∱≮ が一様でない場合には ≈ ∨≕≩≪≕∱≩⊡∱∩ と ≈ ∨≕≩≪≕∱≩⊡∱∻ ≙∱≮∩の両方について分極が生じる≈∨≕≩ ≪≕∱≩⊡∱∩ ⊼ ∰ ≈ ∨≕≩ ≪≕∱≩⊡∱∩ ⊼ ∱≈ ∨≕≩≪≕∱≩⊡∱∻ ≙∱≮∩ ⊼ ∰ ≮∨∱ ⊡ ≈ ∨≘ ∩∩ bits ≮≃ ∨≗ ∩ bits≮≈ ∨≘ ≪≙ ∩ bits
≈ ∨≕≩≪≕∱≩⊡∱∻ ≙∱≮∩ ⊼ ∱0 bits≕∱≩⊡∱ から一意に定める必要あり（メッセージ割り当て不可）≕∱≘∱≕∮ ∲ ≇ ≘∮ ∲
∮
∮≘∴
≕∴

≗ ≙∱≗∮ ≙∮∲∮ ∮≗ ≙∴

18

多段階の分極•≘∱≮ が一様でない場合には ≈ ∨≕≩≪≕∱≩⊡∱∩ と ≈ ∨≕≩≪≕∱≩⊡∱∻ ≙∱≮∩の両方について分極が生じる≈∨≕≩ ≪≕∱≩⊡∱∩ ⊼ ∰ ≈ ∨≕≩ ≪≕∱≩⊡∱∩ ⊼ ∱≈ ∨≕≩≪≕∱≩⊡∱∻ ≙∱≮∩ ⊼ ∰ ≮∨∱ ⊡ ≈ ∨≘ ∩∩ bits ≮≃ ∨≗ ∩ bits≮≈ ∨≘ ≪≙ ∩ bits
≈ ∨≕≩≪≕∱≩⊡∱∻ ≙∱≮∩ ⊼ ∱0 bits≕∱≘∱≕∮ ∲ ≇ ≘∮ ∲∮∮≘∴≕∴≙∱≮ を見ても復元できない≗ ≙∱≗∮ ≙∮∲∮ ∮≗ ≙∴19

多段階の分極•≘∱≮ が一様でない場合には ≈ ∨≕≩≪≕∱≩⊡∱∩ と ≈ ∨≕≩≪≕∱≩⊡∱∻ ≙∱≮∩の両方について分極が生じる≈∨≕≩ ≪≕∱≩⊡∱∩ ⊼ ∰ ≈ ∨≕≩ ≪≕∱≩⊡∱∩ ⊼ ∱≈ ∨≕≩≪≕∱≩⊡∱∻ ≙∱≮∩ ⊼ ∰ ≮∨∱ ⊡ ≈ ∨≘ ∩∩ bits ≮≃ ∨≗ ∩ bits≮≈ ∨≘ ≪≙ ∩ bits
≈ ∨≕≩≪≕∱≩⊡∱∻ ≙∱≮∩ ⊼ ∱0 bits≙

一様分布にしたがうメッセージを割り当てておけば≮∱ を見て復元可能≕∱≘∱≕∮ ∲ ≇ ≘∮ ∲∮∮≘∴≕∴≗ ≙∱≗∮ ≙∮∲∮ ∮≗ ≙∴20

多段階の分極•≘∱≮ が一様でない場合には ≈ ∨≕≩≪≕∱≩⊡∱∩ と ≈ ∨≕≩≪≕∱≩⊡∱∻ ≙∱≮∩の両方について分極が生じる≈∨≕≩ ≪≕∱≩⊡∱∩ ⊼ ∰ ≈ ∨≕≩ ≪≕∱≩⊡∱∩ ⊼ ∱≈ ∨≕≩≪≕∱≩⊡∱∻ ≙∱≮∩ ⊼ ∰ ≮∨∱ ⊡ ≈ ∨≘ ∩∩ bits ≮≃ ∨≗ ∩ bits≮≈ ∨≘ ≪≙ ∩ bits
≈ ∨≕≩≪≕∱≩⊡∱∻ ≙∱≮∩ ⊼ ∱0 bits

• それぞれのビットの値を適切に定めることで通信路容量を達成[Honda-Yamamoto, 2012]≕∱≘∱≕∮ ∲ ≇ ≘∮ ∲∮∮≘∴≕∴≗ ≙∱≗∮ ≙∮∲∮ ∮≗ ≙∴21

概要• 非対称通信路の符号化• polar符号を用いる方式• 無歪み圧縮を用いた符号化法の一般的な枠組み• Miyake-Muramatsuの方式• 連鎖構造に基づく方式• 無歪み圧縮の逆操作について

22

無歪み圧縮
• 出現分布の偏った系列≸≮ をほぼ一様な短い系列 ≵≭ に変換• 符号化と復号を入れ替えることで一様な系列を偏った系列に変換できる → 通信路符号化のための符号語を生成可能(?)• 可変長無歪み圧縮 (ハフマン符号・算術符号……)：• 出現確率が大きい系列は短い符号語に，小さい系列は長い符号語に符号化• 実用上よく用いられる• 固定長無歪み圧縮 (LDPC符号・polar符号……)：• 復号に失敗する場合がある• 他の目的の符号の構成要素として使いやすい23

線形符号による固定長無歪み圧縮≸≮ ∲ ≦∰∻ ∱≧≮, 各要素は独立に分布 ∨≐≘ ∨∰∩∻ ≐≘ ∨∱∩∩ ∽ ∨∱ ⊡ ≰∻ ≰∩ にしたがう• 符号化： ≵≭ ∺∽ ≸≮ ≈ ∻ ≈ ∺ ≮ ⊣ ≭ 行列
• 情報源：• 復号：≸≞≮ ∺∽ ≸≮≡∺≲≸≧≮≭≈∽≡≸≵≭ ≐≘≮ ∨≸≮∩≸≮ は ∲≮ 通りあるが，それらのうち ∲≮≈∨≘∩ 個がほとんどの確率を占める≮で≾• ≸≮ ∷∡ ≸≮ ≈ はほぼ「ランダムな」写像なので， ≸≮ ∶∽ ≸≸≮≈ ∽ ≸≾≮≈ となる確率は ∲⊡≭ 程度• ≭ ∾ ≮≈ ∨≰∩ ならば１に近い確率で正しく復号可能
復号誤り確率の解析：

•24

概要
• 非対称通信路の符号化• polar符号を用いる方式• 無歪み圧縮を用いた符号化法の一般的な枠組み• Miyake-Muramatsuの方式• 連鎖構造に基づく方式• 無歪み圧縮の逆操作について

Miyake-Muramatsu の方法による非対称通信路の符号化• Miyake-Muramatsu (2009, 固定長), Honda (2013, 可変長)
• 符号化：≭ を確率分布≵∨ ∱ ≑≮ ≐ ∨≸≾ ∩∻ ≸≾≮≈ ∽ ∰∻≘≩≩∽∱≮≃≐≘≾ ≮ ∨≸≾ ∩ ∽ ∰∻≸≾≮≈ ∶∽ ∰∻にしたがう系列 ≸≾≮ に変換して送信 (≈ ∺ ≮ ⊣ ≫ 行列)• 無歪み圧縮の復号操作によりメッセージ• 復号：•≸≞≮ ∺∽ ≸≡≮≲∺≧≸≭≮≈≡∽≸∰ ≐≘≮≪≙ ≮ ∨≸≮≪≹≮∩ を計算• 無歪み圧縮の符号化操作により≸≞≮ から ≵≞≭ を復号

25

26

符号の解析

≐≘≾ ≮ ∨≸≾≮∩ にしたがう系列は実質的に ∲≮≈∨≘∩⊡≫ 通り• 無歪み圧縮の逆操作が可能な条件： ≭ ∼ ≮≈ ∨≘ ∩ ⊡ ≫• 受信系列 ≹ ≮ が出現しうるような ≸≮ は実質的に ∲≮≈ ∨≘ ≪≙ ∩ 通り≾≮ の復号が可能な条件： ≮≈ ∨≘ ≪≙ ∩ ∼ ≫• ≸• ≭ ∼ ≮∨≈ ∨≘ ∩ ⊡ ≈ ∨≘ ≪≙ ∩∩ ならば ≹ ≮ から ≵≭ の復号が可能→ 通信路容量 ≃ ∨≗ ∩ ∽ ≈ ∨≘ ∩ ⊡ ≈ ∨≘ ≪≙ ∩ を達成• 確率分布

無歪み圧縮と線形符号を用いた
通信路符号の特徴

27• 利点• ２元符号のまま扱える∨ ∱ ≑≮ ≐ ∨≸≾ ∩∻ ≸≾≮≈ ∽ ∰∻≘≩≩∽∱≮≃• 確率分布 ≐≘≾ ≮ ∨≸≾ ∩ ∽ ∰∻≸≾≮≈ ∶∽ ∰∻• 理論上は復号誤り確率を小さくしやすい• 欠点にしたがう系列を無歪み圧縮の逆操作により作る必要がある（通常の無歪み圧縮は単に≮≙≐ ≮ ∨ ≸≮ ∩ ∽ ≐ ∨ ≸ ∩≘≩∽∱≘ ≩にしたがう系列を符号化できればいいのでそれより複雑）

28

Polar 符号による符号構成の別解釈• Polar 符号による Honda-Yamamoto (2012) の方式は線形符号による通信路符号化と無歪み圧縮の両方にpolar 符号を用いたものと解釈できる• 無歪み圧縮に polar 符号を用いる必然性はない• 無歪み圧縮部分に可変長の homophonic 符号を用いることでも通信路容量を達成可能• 無歪み圧縮に関する分極が必要ないため（２次の）誤り指数が改善 (有歪み圧縮の場合の結果：[Wang-Honda-Yamamoto-Rongke, 2015])

29

概要• 非対称通信路の符号化• polar符号を用いる方式• 無歪み圧縮を用いた符号化法の一般的な枠組み• Miyake-Muramatsuの方式• 連鎖構造に基づく方式• 無歪み圧縮の逆操作について

30

連鎖構造を用いた通信路符号• 符号語全体は部分符号語≩⊡∱≩≋ ブロックからなる• 第ブロックの符号語を復号するための「手がかり」を第 ブロックで送信≋(図はMondelli-Hassani-Urbanke (2014) より)

31

符号化アルゴリズム•∱∻ ∲∻ ⊢ ⊢ ⊢ ∻ ≋ ブロックの順で部分符号語を構成≵≭∨∱∩ を≐≸
b. 第 ≩ ∽ ∲∻ ⊢ ⊢ ⊢ ∻ ≋ ⊡ ∱ ブロック：≫≮
1. 前ブロックの符号語 ≸≮から≳∽≸∨≩⊡∱∩∨≩⊡∱∩ ∨≩⊡∱∩ ≈ を計算≭⊡≫ と合わせた系列
2. ≭ ⊡ ≫ ビットのメッセージ ≵≾∨≩∩⊡≭≫≭≫≵∨≩∩ ∽ ∨≳∨≩⊡∱∩∻ ≵≾∨≩∩ ∩ を分布 ≐≘≮ にしたがう系列 ≸≮∨≩∩ に変換
c. 第≋ ブロック： ≳≫∨≋ ⊡∱∩ ∽ ≸≮を頻度分布が一様な≈⊡∨≋∱∩
符号語 ≮∰ ∽ ≫ ∽≉≳ ∨≗ ∩ ビットに符号化
a. 第1ブロック： 無歪み圧縮の復号操作によりメッセージ
確率分布 ≘ ≮ にしたがう系列 ≮∨∱∩ に変換

32

復号アルゴリズム≋∻ ≋ ⊡ ∱∻ ⊢ ⊢ ⊢ ∻ ∱ ブロックの順で部分符号語を推定∰≮
a. 第≋ ブロック： 受信系列 ≹∨≋ ∩ から ≳≞≫∨≋ ⊡∱∩ を復号
b. 第 ≩ ∽ ≋ ⊡ ∱∻ ⊢ ⊢ ⊢ ∻ ∱ ブロック：≮≮≮
1. ≸≮を≸≞∺∽≡≲≧≭≡≸≐∨≸∨≩∩ ∨≩∩ ≸≮∺≸≮≈ ∽≳≞≫ ≘ ∩ により推定∨≩∩2. 無歪み圧縮の符号化により ≸≞≮∨≩∩ から ≵≞≭∨≩∩ を計算•• 復号可能な条件：≭ ∼ ≮≈ ∨≘ ∩• 第 ≋ ⊡ ∱∻ ⊢ ⊢ ⊢ ∻ ∱ ブロックの復号が可能： ≮≈ ∨≘ ≪≙ ∩ ∼ ≫• 無歪み圧縮の逆操作が可能：

33

符号長の解析≭ ∼ ≮≈ ∨≘ ∩ ビット• 第 ∲∻ ∳∻ ⊢ ⊢ ⊢ ∻ ≋ ⊡ ∱ ブロック： ≭ ⊡ ≫ ∼ ≮≃ ∨≗ ∩ ビット• 第 ≋ ブロック： 0 ビット• 符号長：• 第 ∱∻ ∲∻ ⊢ ⊢ ⊢ ∻ ≋ ⊡ ∱ ブロック： ≮ ビット• 第≋ ブロック： ≫ ∽≉≳ ∨≗ ∩ ∾ ≮≈ ∨≘ ≪≙ ∩∽≉≳ ∨≗ ∩ ビット≈∨≘≪≙ ∩∱∫∨≋⊡∱∩≃∨≗ ∩• 符号化率は ≒ ∼ ≃ ∨≗ ∩ ⊢∱∫ ∨≋≈⊡∨∱≘∩≉≪≳≙∨∩≗ ∩• ≋ ∡ ∱ で通信路容量を達成• 送信できる情報：• 第１ブロック：34

歴史• Bocherer-Mathar (ITW2011): ガウス通信路に対して提案• 通信寄りの研究で理論寄りのコミュニティーには注目されず• Sasoglu-Vardy (ISIT2013): 盗聴通信路への手法として提案• Hassani-Urbanke (ISIT2014): ユニバーサル符号への応用• Mondelli-Hassani-Sason-Urbanke (IEEE IT2015):
放送通信路への応用• Mondelli-Hassani-Urbanke (IEEE IT2018):
通信路符号として改めて整理

35

性質
• 利点：
• 無歪み圧縮に対応する操作で単にi.i.d.確率分布したがう系列を生成すればいい≐≘ ≮ に• 非対称通信路に限らず極めて多くの符号化問題に適用可能• 欠点：• 部分符号語長≮ だけでなくブロック数 ≋ も大きい必要がある• 遅延が大きい・ブロック間で復号誤りが伝播• 可変長符号にやや適用しにくい

36

概要• 通信路符号化と通信路容量• Gallager の方法による非対称通信路符号化• 無歪み圧縮を用いた非対称通信路符号化• Miyake-Muramatsu の方式• 連鎖構造に基づく方式• 無歪み圧縮の逆操作について

37

無歪み圧縮の逆操作について• 線形符号を用いた固定長無歪み圧縮は実際には性能が悪い• 算術符号は適用不可（符号木が完全木でないため）• Homophonic 符号化 (distribution matching) を用いる
• 所望の確率分布•≐≘≮をもつ系列 ≸≮ を一様系列 ≵≮ から生成≸≮ から ≵≮ を一意に復元可能

38

Homophonic 符号化法の例• 区間アルゴリズムによるFV符号 [Hoshi-Han, 2001]• 非i.i.d.でも可，理論的に非常に扱いやすい• 誤り伝播が生じる• タイプ集合の数え上げに基づくFF符号 [Schulte-Bocherer, 2016]• FF符号なので実用上最も扱いやすい• 冗長度∨≬≯≧ ≮∩∽≮ ，非i.i.d.の場合はほぼ使用不能• １シンボル復号遅延を許すVF符号 [Honda-Yamamoto, 2017]• 非i.i.d.の場合にも適用可能• 理論解析に細かい制約が入る

39

まとめ
• 通信路符号化ではまず対称通信路において通信路容量を達成する方法が考えられた• 非対称通信路において容量を達成する通信を行うためには頻度分布が一様でない符号語を生成する必要がある• 古くから知られていた Gallager の方法は実用上ほぼ動かない• 無歪み圧縮に基づいた方式 (Miyake-Muramatsuの方式，連鎖構造に基づく方式) が有望• 無歪み圧縮の逆操作を実用的な性能で実現するにはhomophonic符号化 / distribution matching が必要