8.6 並列ガウス通信路と注水

8.5 節の帯域制限ガウス通信路では,どの標本にも同じ分散の雑音が乗るとした.実際の経路はそうとはかぎらない.周波数の帯域を細かく切ると,雑音の強さは帯域ごとに違う.これは,8.5 節の帯域制限ガウス通信路から,どの標本にも同じ分散という仮定だけを外した場合にあたる.いくつもの経路を束ねて使うときも,経路ごとに雑音の強さが違う.そのとき,限られた総電力をどう配るのがよいか.これが本節の問いで,答えは 注水 と呼ばれる形をとる.

答えを先に言えば,雑音の弱い経路ほど多くの電力を配り,雑音が強すぎる経路には何も配らない,という配分が最適になる.どこで打ち切るかを決めるのが水位と呼ばれる一つの数で,配る電力はその水位と雑音の強さの差である.8.2 節例 8.2.6 が「同じ電力を分けたほうが得」を示していたが,分ける相手の条件が違うときにどう分けるか,というのが本節の内容である.

本節のは各通信路に配る電力で,定義 8.3.1 の誤り確率とは別のものである.添字が通信路の番号か文字かで見分ける.通信路の番号は本節に限りからまでとする.本節のは並列に使う通信路の本数で,8.3 節8.4 節がブロック長に使ったとは別である.

電力配分の問題

定義 8.6.1(並列ガウス通信路と電力配分). とし,を正の実数とする.雑音の分散がそれぞれである本のガウス通信路(定義 8.1.1)を,たがいに独立に回ずつ同時に使うものを 並列ガウス通信路 と呼ぶ.総電力の制約のもとでの 電力配分 とは,𝑃𝑖 01 𝑖 𝑛)かつを満たす実数の組のことをいう.その 合計容量

𝑛𝑖=112log(1+𝑃𝑖𝑁𝑖)

で定める.

合計容量の各項は,であれば,定理 8.2.4 により第通信路を電力で使ったときの容量である.の本は定理 8.2.4 の対象から外れる.8.2 節で見たとおり,電力の制約を満たす入力は密度をもたないので,そこでは容量が定まらないからである.ただし項の値そのものはで,電力を配らない本では何も運べない,という読みと食い違わない.運べる量について言えるのは,本ずつの話までである.の各本については,系 8.4.2 により,その本だけを使ったときの達成レートの上限が第に等しい.本を別々の符号で使ったときにレートの合計がそのまま達成できるか,また本をまとめて符号化すればそれを超えられるかは,どちらも本書では示さない.本節が解くのは合計容量という一つの式を電力配分について最大にする問題であって,それ以上でも以下でもない.

形式化上の注記. 並列ガウス通信路全体の容量,すなわち本の入力をまとめて一つの確率変数として選んでよいとしたときの相互情報量の上限が,定義 8.6.1 の合計容量の最大値に等しいことを,本書は示さない.形式化の側にも,そのままの形の単独の宣言はない.parallel_gaussian_capacity_formula_minimal (InformationTheory/Shannon/ParallelGaussian/PerCoordRegularity.lean) が与えるのは,測度論の言葉で定義した容量 parallelGaussianCapacity (InformationTheory/Shannon/ParallelGaussian/Basic.lean) が注水配分の合計容量に等しいところまでで,それが最大値でもあることは,定理 8.6.5 にあたる isWaterFillingOptimal_of_kkt (InformationTheory/Shannon/ParallelGaussian/KKT.lean) との合成で出る.仮定は,総電力が正であること,各雑音の分散がでないこと,二つの可測性(どちらも正則性の条件である),および水位が定理 8.6.3 の等式を満たすことである.

形式化: parallelGaussianChannel (ソース)

形式化上の注記. 形式化の parallelGaussianChannel は,入力の組に対して,成分ごとに平均分散のガウス分布をとった積測度を返す核で,定義 8.6.1 の並列ガウス通信路にあたる.核が可測であるという正則性の前提が二つ付くが,これは通信路の形を決める条件ではない.定義 8.6.1 の電力配分と合計容量には,対応する単独の宣言がない.合計容量の式は,注水配分の最適性を述べる IsWaterFillingOptimal (InformationTheory/Shannon/ParallelGaussian/Basic.lean) の中に書き下されている.電力の側の制約も,実数の組ではなく入力の分布に対する条件 parallelGaussianPowerConstraintSet (InformationTheory/Shannon/ParallelGaussian/Basic.lean) として書かれていて,定義 8.6.1 とは対象が違う.

定義 8.6.2(注水配分). とし,を正の実数,を実数とする.

𝑃𝑖(𝜈):=max(0,𝜈𝑁𝑖)(1𝑖𝑛)

で定まる組を,水位 注水配分 と呼ぶ.

形式化: waterFillingPower (ソース)

名前の由来は絵にある.底が段になった一続きの容器を思い浮かべる.横幅を等分し,第の区画の底の高さをにとる.そこに水を注ぐと,区画のあいだで水は行き来できるので,水面はどの区画でも同じ高さでそろう.第の区画に入る水の深さは,底が水面より低ければ,底が水面より高ければ(𝑁𝑖 𝜈である.どの区画も横幅が同じなので,入った水の量は深さに比例し,全体の量はに比例する.これが総電力に等しくなるように水位を決める,というのが以下の筋である.

水面がそろうところが最適なのはなぜか,を絵の言葉で言っておく.以下では,対数の導関数がであることと合成関数の微分を,微積分の計算規則として既知とする.当てる相手は,この段落でで微分するところだけである.第通信路に電力をほんの少し足したとき,合計容量の第が電力単位あたりどれだけ増えるかは,で微分してである.分母のは,底の高さに水の深さを足したもの,すなわちその区画の水面の高さにほかならない.だから,水面の低い区画ほど電力単位あたりの増分が大きい.任意の配分は,区画のあいだに仕切りを立てて水面の高さをばらばらにした状態にあたり,仕切りを外すと水面がそろう,と見ればよい.水の入っている区画のうち水面がいちばん高いものから,水面がいちばん低い区画へ電力を少し移せば,減るぶんより増えるぶんが大きく,合計は増える.移して得をする組がなくなるのは,水の入っている区画の水面がすべてそろい,しかも水の入っていない区画の底がその水面以上にあるときで,これが注水配分の形にほかならない.そこでは水の入っているどの区画でも増分が同じになる.このが,あとで補題 8.6.4 が上から抑えるのに使う接線の傾きである.

水位の存在と一意性

道具を一つ借りる.中間値の定理,すなわち「有界閉区間の上の実数値連続関数は,両端での値のあいだのどの値もとる」という微積分の定理である.当てる相手は,定理 8.6.3 の証明で置く変数の実数値関数の,有界閉区間への制限だけであり,依存するのは定理 8.6.3 の証明と,同じ定理を 9.4 節で借り直している第9章 定理 9.4.9 の証明である.また,連続関数の有限個の最大値と有限和がふたたび連続であることを,微積分の計算規則として既知とする.

定理 8.6.3(水位の存在と一意性). 𝑛 1とし,を正の実数とする.このとき

𝑛𝑖=1max(0,𝜈𝑁𝑖)=𝑃

を満たす実数がただ一つ存在する.

証明. とおく.各は連続関数の最大値だから連続であり,その有限和であるも連続である.

両端の値を見る.よりである.とおくと,第項だけを残してである.

は閉区間の上で連続で,だから,借りた中間値の定理よりを満たすが存在する.

そのようなが二つとないことを見る.のうち最小のものをと書く.を満たすについては,ある,すなわちだから,そのようなはすべてより大きい.そこでとすると,各についてだからであり,第項についてはより二つの項がに等しい.項ごとに足し合わせるとである.よって以上のところで狭義単調増加であり,そこで値をとるは一つしかない.

形式化上の注記. 定理 8.6.3 に対応する単独の宣言はない.存在の側を与えるのが exists_waterFillingKKT_of_pos (InformationTheory/Shannon/ParallelGaussian/KKT.lean) で,こちらは雑音の分散が正であることを仮定にもたない(でもよい)ので,定理 8.6.3 より広い場合を覆っている.仮定は総電力が正であること一つだけで,通信路が本以上あることは仮定になっていない.通信路の本数をと書き,添字の型が個の値をもつようにとることで,型のほうから出るようにしてある.一意性の側は,形式化されていない.

接線による上界

最適性の証明は,補題 1.1.7 の対数不等式だけで通る.対数のグラフが接線より下にあるという,第7章 補題 7.2.3 でも使ったのと同じ道具である.注水配分の点で対数に接線を引き,そのぶんだけ上から抑える.それを述べるのが補題 8.6.4 である.

補題 8.6.4(注水配分での接線). 𝑁 >0とし,とおく.このとき,どの実数についても

12log(1+𝑡𝑁)12log(1+𝑝𝑁)+log𝑒2𝜈(𝑡𝑝)

である.

証明. はどちらも正である.補題 1.1.7 の対数不等式に当てると

log(1+𝑡𝑁)log(1+𝑝𝑁)=log𝑢𝑡𝑝𝑁+𝑝log𝑒

である.両辺をで割ると,示すべきことは

𝑡𝑝2(𝑁+𝑝)log𝑒log𝑒2𝜈(𝑡𝑝)

に帰着する.の大小で場合を分ける.

のときはだからであり,両辺は等しい.

のときはだからであり,である.からであり,これが示すべき不等式である.

形式化: waterFillingCost_tangent_le (ソース)

形式化上の注記. 形式化の waterFillingCost_tangent_le の仮定は,補題 8.6.4 と一つずつ対応している.雑音の分散がでないこと,水位が正であること,引数が以上であることの三つで,これがすべてである.形式化では分散を非負の量として扱っているので,一つめは本文のと同じことである.形式化はを自然対数にとるのでであり,本文のにあたる係数がと書かれている.

注水の最適性

定理 8.6.5(注水配分の最適性). 𝑛 1とし,を正の実数とする.実数を満たすとする.このとき注水配分は総電力の制約のもとでの電力配分(定義 8.6.1)であり,𝑃𝑖 01 𝑖 𝑛)かつを満たすどの実数の組についても

𝑛𝑖=112log(1+𝑃𝑖𝑁𝑖)𝑛𝑖=112log(1+𝑃𝑖(𝜈)𝑁𝑖)

である(定義 8.6.2 の注水配分).

証明. 注水配分が電力配分であることを見る.各の形から以上であり,総和は仮定よりちょうどで,以下である.よって定義 8.6.1 の電力配分の条件を満たす.

まずを見る.仮定の和はだから,ある,すなわちである.

各項に補題 8.6.4 を,𝑁 :=𝑁𝑖ととって当てると,であり

12log(1+𝑃𝑖𝑁𝑖)12log(1+𝑃𝑖(𝜈)𝑁𝑖)+log𝑒2𝜈(𝑃𝑖𝑃𝑖(𝜈))

である.について足すと

𝑛𝑖=112log(1+𝑃𝑖𝑁𝑖)𝑛𝑖=112log(1+𝑃𝑖(𝜈)𝑁𝑖)+log𝑒2𝜈(𝑛𝑖=1𝑃𝑖𝑛𝑖=1𝑃𝑖(𝜈))

となる.仮定よりであり,だから括弧の中は以下である.より係数は正だから,最後の項は以下であり,落として主張を得る.

形式化: isWaterFillingOptimal_of_kkt (ソース)

形式化上の注記. 形式化のルートも本文と同じで,注水配分の点で対数に接線を引く段(補題 8.6.4)を各成分に当ててから和をとる.

証明で効いたのは二つだけである.接線の傾きがという,によらない一つの値で抑えられること(補題 8.6.4)と,注水配分が総電力を使い切っていること(𝑖𝑃𝑖(𝜈) =𝑃)である.前者があるので,本ぶんの接線の項がという一つの和にまとまる.後者があるので,その和が電力制約と直接くらべられる.雑音が強すぎて水位に届かない通信路(𝑁𝑖 𝜈)で接線の傾きがそのままでは足りないところを,補題 8.6.4 の第の場合がで吸収している.

数で見る

例 8.6.6(本の並列ガウス通信路). 𝑛 =2𝑁1 =1とする.総電力のとき水位はで,注水配分は,その合計容量はで約ビットである.等分した配分の合計容量は約ビットで,これより小さい.総電力のときは水位がで,注水配分は,合計容量は約ビット,等分した配分の合計容量は約ビットである.

証明. のとき.水位が第通信路の底に届かないと見当をつけると,水が入るのは第通信路だけで,すなわちである.これは以下だから見当と整合する.実際定理 8.6.3 の等式を満たし,それを満たす実数はただ一つだから,これが水位である.注水配分はで,合計容量はである.だから約である.等分した配分ではで約である.

のとき.今度は水位がを超えると見当をつけると,両方の通信路に水が入るので,すなわちである.これはより大きいから見当と整合する.実際で,これが水位である.注水配分はで,合計容量はで約である.等分した配分ではで約である.

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

例 8.6.6 の前半は,雑音の強い通信路を使わないほうがよい場合である.総電力では水位が第通信路の雑音に届かないので,そちらには何も配らない.後半では総電力がに増えて水位がまで上がり,第通信路にもだけ配られる.注水の絵でいえば,注ぐ水の量を増やしていくと,あるところで二つめの区画の底が水没する,ということである.どちらの場合も等分した配分より合計容量が大きい.差は前半が約ビット,後半が約ビットで,合計容量に対する割合で見ると前半が約パーセント,後半が約パーセントである.後半では水位が第通信路の底を超えていて,注水配分も等分した配分もどちらの通信路にも電力を配っており,二つの配分の違いがそれだけ小さい.

帯域ごとに雑音が違うとき. 定義 8.6.1 の並列ガウス通信路は,8.5 節の帯域制限ガウス通信路の雑音が帯域ごとに違う場合にあたる.帯域を等しい幅に切り,第の帯域を,標本あたりの雑音の分散がであるガウス通信路と読む.8.5 節が帯域制限ガウス通信路を分散のガウス通信路の使用に読み替えたのと同じ換算である.第の帯域に配る電力も標本あたりで測ってと書けば,総電力をどの帯域に配るかという問題がそのまま定義 8.6.1 の形になる.どの帯域も幅が同じで秒あたりの標本の個数がそろっているので,標本あたりで測るか秒あたりで測るかは,全体に共通の因子の違いにしかならない.雑音の弱い帯域に電力を集め,雑音が水位を超える帯域は使わない,というのが定理 8.6.5 の答えである.雑音の強さが帯域によらないときは全部のが等しく,注水配分は等分になって,8.5 節の設定に戻る.

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