6.5 フィードバックのある通信路

ここまで，送る側は符号語を決めたら最後まで送りきるものとしてきた．受け取る側に何が届いたかは，送る側には分からない．では，受け取る側が受け取った記号をそのつど送る側へ完全に返せるとしたら，つまり次の記号を決めるまでに，いま何が届いたかを送る側が知っていられるとしたら，容量は増えるだろうか．

直感は「増える」と答える．送る側は通信路がいまどう振る舞ったかを見て次の入力を選べる．消失したと分かればもう一度送ればよいし，雑音の出方に合わせて送るものを変えることもできる．何も知らずに送りっぱなしにするより，賢く振る舞えるはずである．ところが答えは，容量は増えない，である．この意外さが本節の主題で，なぜ増えないのか，そして増えないのにフィードバックの何が有用なのかを見る．

フィードバック符号

定義 6.5.1（フィードバック符号）. 長さ $𝑛$ の フィードバック符号 とは，メッセージ数 $𝑀 \geq 1$ ，符号化写像の族 $𝑐 𝑖 : {1, \dots, 𝑀} \times Y 𝑖 \to X$ （ $𝑖 = 0, \dots, 𝑛 - 1$ ），復号器 $𝑑 : Y 𝑛 \to {1, \dots, 𝑀}$ の組である．メッセージ $𝑚$ を送るとき，時刻 $𝑖$ の入力を

𝑥 𝑖 = 𝑐 𝑖 (𝑚, 𝑦 < 𝑖), 𝑦 < 𝑖 : = (𝑦 0, \dots, 𝑦 𝑖 - 1)

で定める．すなわち，時刻 $𝑖$ の入力はそれまでに受け取られた出力に依存してよい．レート は $𝑅 : = 1 𝑛 l o g 𝑀$ ，メッセージ $𝑚$ の 誤り確率 は $𝑃 𝑒 (𝑚) : = P r [𝑑 (𝑌 𝑛) \neq 𝑚]$ （ $𝑌 𝑛$ はこの手順で通信路を $𝑛$ 回使ったときの出力）とし，最大誤り確率 と 平均誤り確率 は定義 6.2.1 と同じく $𝑚$ についての最大と平均で定める．

$𝑐 𝑖$ が $𝑦 < 𝑖$ によらない場合が定義 6.2.1 のブロック通信路符号である．すなわちフィードバック符号は定義 6.2.1 の符号をすべて含む．だから，フィードバックを許して達成できるレートの範囲は，少なくとも許さないときと同じだけはある．本節の内容は，それが広がりもしない，ということである．

返せるとしたら，を問うている. 定義 6.5.1 が置いている前提は強い．受け取る側の記号が遅れなく，誤りもなく送る側へ戻るとしている．現実の通信路でそれが可能かは別の問いで，ここでは可能だとしたら何が変わるかを問うている．実際にはフィードバックの経路自身も雑音をもつので，この定義は「フィードバックがいちばん有利に働いたとき」を表している．それでも容量が増えないなら，雑音のあるフィードバックでも増えない．

形式化上の注記. 符号化写像の族は FeedbackCode (InformationTheory/Shannon/ChannelCoding/Feedback.lean) として形式化されている．時刻ごとの符号化器がメッセージと長さ $𝑖$ の過去出力だけを見るという因果性は型に入っており，過去出力によらない場合が定義 6.2.1 のブロック通信路符号だという埋め込みも同じところにある．ただし本節の逆定理はそれを使わず，入力の列 $𝑋 𝑖$ を確率変数としてそのまま扱って，それが過去の出力とメッセージから決まるという構造を定義 6.5.2 の条件付き独立に吸収させている．

記憶のなさと因果性

定義 6.5.2（フィードバックのもとで各時刻で記憶がない）. 確率変数 $M s g$ ，入力の組 $𝑋 𝑛 = (𝑋 0, \dots, 𝑋 𝑛 - 1)$ ，出力の組 $𝑌 𝑛 = (𝑌 0, \dots, 𝑌 𝑛 - 1)$ が フィードバックのもとで各時刻で記憶がない とは，すべての $𝑖$ について

(𝑌 < 𝑖, M s g) \to 𝑋 𝑖 \to 𝑌 𝑖

がマルコフ連鎖（定義 1.8.3）をなすことをいう．ここで $𝑌 < 𝑖 : = (𝑌 0, \dots, 𝑌 𝑖 - 1)$ である．

形式化: IsMemorylessFeedback (ソース)

一つの条件が二つのことを同時に言っている．一つは記憶のなさで，時刻 $𝑖$ の入力さえ決まれば出力はそれまでに何が受け取られたかによらない．もう一つは因果性で， $𝑋 𝑖$ を決めてしまえば出力はメッセージそのものを覗き見ない．言い換えれば，メッセージの影響は入力を通ってしか届かない．

条件に並んでいるのが過去の出力とメッセージであって，他の時刻の入力ではないことに注意したい．定義 6.4.4 は他の時刻の入出力を条件に置いていた．フィードバックがあると $𝑋 𝑖$ が過去の出力の関数になるので，入力どうしの独立性を問う形にはもう意味がない．代わりに， $𝑋 𝑖$ を決めるのに使えた情報（過去の出力とメッセージ）をすべて条件に並べ，それでも $𝑌 𝑖$ は $𝑋 𝑖$ しか見ないと述べている．

1 時刻ごとの評価

補題 6.5.3. $𝑛 \geq 1$ とし， $M s g$ ， $𝑋 𝑛 = (𝑋 0, \dots, 𝑋 𝑛 - 1)$ ， $𝑌 𝑛 = (𝑌 0, \dots, 𝑌 𝑛 - 1)$ をフィードバックのもとで各時刻で記憶がない（定義 6.5.2）確率変数の組とする．このとき各 $𝑖$ について

𝐼 (M s g; 𝑌 𝑖 ∣ 𝑌 < 𝑖) \leq 𝐼 (𝑋 𝑖; 𝑌 𝑖)

が成り立つ．

証明. $𝐿 : = (𝑌 < 𝑖, M s g)$ とおく．定義 6.5.2 は $𝐿 \to 𝑋 𝑖 \to 𝑌 𝑖$ がマルコフ連鎖であることをいうので，定理 1.8.4 より $𝐼 (𝐿; 𝑌 𝑖) \leq 𝐼 (𝑋 𝑖; 𝑌 𝑖)$ である．

いっぽう定理 1.5.1 を $𝑍 \leftarrow 𝑌 < 𝑖$ ， $𝑋 \leftarrow M s g$ ， $𝑌 \leftarrow 𝑌 𝑖$ として当てると

𝐼 (𝐿; 𝑌 𝑖) = 𝐼 (𝑌 < 𝑖; 𝑌 𝑖) + 𝐼 (M s g; 𝑌 𝑖 ∣ 𝑌 < 𝑖)

であり，命題 1.3.2 より第 1 項は非負だから $𝐼 (M s g; 𝑌 𝑖 ∣ 𝑌 < 𝑖) \leq 𝐼 (𝐿; 𝑌 𝑖)$ である．二つを合わせて主張を得る． $◻$

形式化: feedback_per_letter_bound (ソース)

補題 6.5.3 が本節の核である．左辺は「これまでに受け取ったものを踏まえたうえで，時刻 $𝑖$ の出力がメッセージについて新しく教えてくれる情報」，右辺は「時刻 $𝑖$ の入力と出力が共有する情報」である．フィードバックは左辺の側にいくらでも仕掛けを入れられる．過去の出力を見て $𝑋 𝑖$ を選び直せるからである．しかしその結果はやはり右辺で抑えられる．フィードバックが変えられるのは各時刻の入力の選び方だけで，選んだ入力に対して通信路が運べる量そのものではない，というのがこの補題の内容である．

フィードバック逆定理

定理 6.5.4. $𝑀 \geq 2$ ， $𝑛 \geq 1$ とし， $𝐶$ を実数とする． $M s g$ を ${1, \dots, 𝑀}$ 上の一様分布に従う確率変数， $𝑋 𝑛 = (𝑋 0, \dots, 𝑋 𝑛 - 1)$ ， $𝑌 𝑛 = (𝑌 0, \dots, 𝑌 𝑛 - 1)$ を有限集合に値をとる確率変数の組， $𝑑$ を $𝑌 𝑛$ の値から ${1, \dots, 𝑀}$ への写像とし， $𝑃 𝑒 : = P r [𝑑 (𝑌 𝑛) \neq M s g]$ とおく．組がフィードバックのもとで各時刻で記憶がなく（定義 6.5.2），かつすべての $𝑖$ で $𝐼 (𝑋 𝑖; 𝑌 𝑖) \leq 𝐶$ なら

l o g 𝑀 \leq 𝑛 𝐶 + 𝐻 𝑏 (𝑃 𝑒) + 𝑃 𝑒 l o g (𝑀 - 1)

が成り立つ．

証明. 定理 6.4.1 を，観測を $𝑌 𝑛$ ，復号器を $𝑑$ として当てると

l o g 𝑀 \leq 𝐼 (M s g; 𝑌 𝑛) + 𝐻 𝑏 (𝑃 𝑒) + 𝑃 𝑒 l o g (𝑀 - 1)

である．第 1 項を $𝑛 𝐶$ で抑えればよい．

相互情報量は対称（命題 1.3.3）だから $𝐼 (M s g; 𝑌 𝑛) = 𝐼 (𝑌 𝑛; M s g)$ である．定理 1.5.2 を，変数列 $𝑌 0, \dots, 𝑌 𝑛 - 1$ と，相手側の変数 $M s g$ として当てると

𝐼 (𝑌 𝑛; M s g) = 𝑛 - 1 \sum 𝑖 = 0 𝐼 (𝑌 𝑖; M s g ∣ 𝑌 < 𝑖)

となる．条件付き相互情報量も対称（命題 1.4.2）なので，各項は $𝐼 (M s g; 𝑌 𝑖 ∣ 𝑌 < 𝑖)$ に等しい．これを補題 6.5.3 で $𝐼 (𝑋 𝑖; 𝑌 𝑖)$ で抑え，仮定でさらに $𝐶$ で抑えると，和は $𝑛 𝐶$ 以下である． $◼$

形式化: channel_coding_feedback_converse_memoryless (ソース)

分解の軸を入力から出力に取り替える. 6.4 節の逆定理は，まず系 6.4.2 で $𝐼 (M s g; 𝑌 𝑛)$ を $𝐼 (𝑋 𝑛; 𝑌 𝑛)$ に移し，そこから入力の側でチェイン則を使った（定理 6.4.3）．フィードバックがあると最初の一歩が壊れる． $𝑋 𝑖$ が過去の出力の関数になるので，メッセージから出力への影響が符号語だけを通るとはいえなくなり， $M s g \to 𝑋 𝑛 \to 𝑌 𝑛$ はもうマルコフ連鎖ではない．出力が入力へ回り込むからである．そこで $𝐼 (M s g; 𝑌 𝑛)$ をそのまま抱えたまま，出力の側でチェイン則を使う．分解の軸を入力から出力へ取り替えたことが，この節の技術的な要点である．回り込みが起きる軸を避けて，起きない軸で分解した，と読める．

フィードバックは容量を増やさない

系 6.5.5（フィードバックは容量を増やさない）. $𝑊$ を通信路（定義 6.1.1）とする．第 $𝑛$ 項が長さ $𝑛$ の符号であるフィードバック符号の族 $(𝑀 𝑛, (𝑐 𝑛, 𝑖) 𝑖, 𝑑 𝑛) 𝑛 \geq 1$ が，最大誤り確率 $𝑃 (𝑛) 𝑒, m a x \to 0$ を満たし，レートの列 $𝑅 𝑛 = 1 𝑛 l o g 𝑀 𝑛$ が上に有界であるとする．このとき $l i m i n f 𝑛 𝑅 𝑛 \leq 𝐶 (𝑊)$ である．

証明. 達成可能性が最大誤り確率で書かれているのでメッセージには一様分布を入れてよく， $𝑃 (𝑛) 𝑒 : = P r [𝑑 𝑛 (𝑌 𝑛) \neq M s g]$ は平均誤り確率に等しくて $𝑃 (𝑛) 𝑒 \leq 𝑃 (𝑛) 𝑒, m a x \to 0$ である． $𝑀 𝑛 \geq 1$ より $𝑅 𝑛 \geq 0$ であり， $𝛿 𝑛 : = 𝐻 𝑏 (𝑃 (𝑛) 𝑒) / 𝑛 + 𝑃 (𝑛) 𝑒 𝑅 𝑛$ とおくと，これは非負で， $(𝑅 𝑛)$ の有界性と合わせて補題 6.4.7 より $𝛿 𝑛 \to 0$ である． $𝑀 𝑛 = 1$ の $𝑛$ では $𝑅 𝑛 = 0$ で，命題 6.1.6 より $𝑅 𝑛 \leq 𝐶 (𝑊) \leq 𝐶 (𝑊) + 𝛿 𝑛$ が成り立つ．以下 $𝑀 𝑛 \geq 2$ とする．

定理 6.5.4 の仮定を確かめる. 時刻 $𝑖$ の入力は $𝑋 𝑖 = 𝑐 𝑛, 𝑖 (M s g, 𝑌 < 𝑖)$ であり，それを通信路に通すのだから， $(M s g, 𝑌 < 𝑖)$ を知ったうえでの $𝑌 𝑖$ の条件付き分布は $𝑊 (\cdot ∣ 𝑋 𝑖)$ である．これは $𝑋 𝑖$ だけで決まるので，組はフィードバックのもとで各時刻で記憶がない（定義 6.5.2）．同じ条件付き分布を $(M s g, 𝑌 < 𝑖)$ について平均すれば， $𝑋 𝑖$ だけで条件付けても $𝑊 (\cdot ∣ 𝑋 𝑖)$ である．よって $𝑋 𝑖$ の分布を $𝑝 𝑖$ と書けば対 $(𝑋 𝑖, 𝑌 𝑖)$ の同時分布は $𝑝 𝑖 (𝑥) 𝑊 (𝑦 ∣ 𝑥)$ であり，命題 6.1.3 と定義 6.1.4 より $𝐼 (𝑋 𝑖; 𝑌 𝑖) = 𝐼 (𝑝 𝑖; 𝑊) \leq 𝐶 (𝑊)$ である．

定理 6.5.4 を $𝐶 \leftarrow 𝐶 (𝑊)$ として使い， $𝑛$ で割ると

𝑅 𝑛 \leq 𝐶 (𝑊) + 𝐻 𝑏 (𝑃 (𝑛) 𝑒) 𝑛 + 𝑃 (𝑛) 𝑒 l o g (𝑀 𝑛 - 1) 𝑛

である． $𝑀 𝑛 \geq 2$ より $l o g (𝑀 𝑛 - 1) \leq l o g 𝑀 𝑛 = 𝑛 𝑅 𝑛$ だから，右辺の第 3 項は $𝑃 (𝑛) 𝑒 𝑅 𝑛$ 以下であり， $𝑅 𝑛 \leq 𝐶 (𝑊) + 𝛿 𝑛$ を得る．どの $𝑛$ でもこれが成り立ち $𝛿 𝑛 \to 0$ だから，両辺で下極限をとって主張を得る． $◼$

形式化上の注記. 系 6.5.5 に対応する単独の宣言はない．定理 6.5.4 に紐付けた宣言は各時刻の上界 $𝐶$ を引数として受け取る形なので，そこに $𝐶 (𝑊)$ を渡した合成で得られる．

系 6.5.5 が示したのは片側だけである． $𝐶 (𝑊)$ 未満のレートがフィードバックを使っても達成できるというもう片側は，定義 6.5.1 の直後に見たとおり，フィードバックを使わない符号がそのままフィードバック符号になることから出る．定理 6.3.7 が作った符号をそのまま使えばよい．二つを合わせると，フィードバックのあるなしで到達できるレートの範囲は変わらない．

最大をとったあとでは動かせない. 増えない理由は，補題 6.5.3 と容量の定義の組み合わせに尽きる．フィードバックが与えるのは各時刻の入力分布を履歴に応じて選び直す自由だが， $𝐶 (𝑊)$ はもともと入力分布のすべてにわたる最大値（定義 6.1.4）である．どの時刻にどんな分布を選んでも，その時刻に運べる量は最大値を超えない．すでに最大をとってある量は，選び方を工夫しても動かない．

増えないのに，何が変わるのか

例 6.5.6（消失した記号を送り直す）. $𝜂 \in [0, 1]$ ， $𝑛 \geq 1$ とし，消失確率 $𝜂$ の二元消失通信路（例 6.1.9）にフィードバックを付ける．送る側は，いま送ったビットが届いたか消失したかを，次の入力を決めるまでに知ることができる．そこで，消失していたら同じビットをもう一度送り，届いていたら次のビットへ進む，という方式をとる． $𝑛$ 回の使用でこの方式が運ぶビット数を $𝑁 𝑛$ とすると

𝔼 [𝑁 𝑛] = (1 - 𝜂) 𝑛

である．

証明. 時刻 $𝑖$ の出力が消失でないという事象の指示変数を $𝑍 𝑖$ とおく．例 6.1.9 の通信路では $𝑊 (* ∣ 𝑥) = 𝜂$ が入力によらないので，送る側が何を選んでも $P r [𝑍 𝑖 = 1] = 1 - 𝜂$ であり， $𝔼 [𝑍 𝑖] = 1 - 𝜂$ である．

この方式では，消失しなかった記号がそのつどちょうど 1 ビットを運ぶ．届いた記号がどのビットのものかは，受け取る側も消失の位置を見ているので分かる．よって $𝑛$ 回で運ばれたビット数は $𝑁 𝑛 = \sum 𝑛 - 1 𝑖 = 0 𝑍 𝑖$ であり，期待値の線形性から $𝔼 [𝑁 𝑛] = (1 - 𝜂) 𝑛$ を得る． $◼$

$𝜂 = 1$ は全時刻が消失する縮退した場合で，この方式は 1 ビットも進まない．そのときは右辺も 0 になるので，等式はそのまま成り立っている．

1 回の使用あたり平均 $1 - 𝜂$ ビットであり，これは例 6.1.9 で計算した容量とちょうど同じ値である． $𝜂 = 0.1$ なら $𝑛$ 回で運べるビット数の期待値は $0.9 𝑛$ ，すなわち 1 回あたり $0.9$ ビットである．

この方式には符号語も復号器の設計も入っていない．届かなければもう一度送るだけで， $𝑛$ を大きくとる必要さえない．同じレートにフィードバックなしで達するには，6.3 節のランダム符号化と結合典型復号器が要った．しかも作れることが分かるだけで，どの符号帳が当たりかは分からないままだった．フィードバックが変えるのは，到達できるレートではなく，そこへ届くための手間である．系 6.5.5 が否定しているのは前者だけで，後者については何も言っていない．

なお，この方式で $1 - 𝜂$ 未満のどのレートでも誤り確率が 0 に向かうことまで言うには， $𝑁 𝑛$ が期待値のまわりに集中することを示す必要がある．ここでは期待値の計算までにとどめる．

形式化上の注記. 例 6.5.6 に対応する宣言は形式化されていない．例 6.5.6 に付した証明が，この主張の保証のすべてである．

InformationTheory — 形式化検証つき情報理論教科書（レビュー版）．数式は MathJax + AMS Euler で事前レンダリング．