8.6 並列ガウス通信路と注水
8.5 節の帯域制限ガウス通信路では,どの標本にも同じ分散𝑁0/2の雑音が乗るとした.実際の経路はそうとはかぎらない.周波数の帯域を細かく切ると,雑音の強さは帯域ごとに違う.これは,8.5 節の帯域制限ガウス通信路から,どの標本にも同じ分散という仮定だけを外した場合にあたる.いくつもの経路を束ねて使うときも,経路ごとに雑音の強さが違う.そのとき,限られた総電力をどう配るのがよいか.これが本節の問いで,答えは 注水 と呼ばれる形をとる.
答えを先に言えば,雑音の弱い経路ほど多くの電力を配り,雑音が強すぎる経路には何も配らない,という配分が最適になる.どこで打ち切るかを決めるのが水位と呼ばれる一つの数で,配る電力はその水位と雑音の強さの差である.8.2 節の例 8.2.6 が「同じ電力を分けたほうが得」を示していたが,分ける相手の条件が違うときにどう分けるか,というのが本節の内容である.
本節の𝑃1,…,𝑃𝑛は各通信路に配る電力で,定義 8.3.1 の誤り確率𝑃𝑒とは別のものである.添字が通信路の番号か文字𝑒かで見分ける.通信路の番号は本節に限り1から𝑛までとする.本節の𝑛は並列に使う通信路の本数で,8.3 節・8.4 節がブロック長に使った𝑛とは別である.
電力配分の問題
定義 8.6.1(並列ガウス通信路と電力配分). 𝑛 ≥1とし,𝑁1,…,𝑁𝑛を正の実数とする.雑音の分散がそれぞれ𝑁1,…,𝑁𝑛である𝑛本のガウス通信路(定義 8.1.1)を,たがいに独立に1回ずつ同時に使うものを 並列ガウス通信路 と呼ぶ.総電力𝑃 >0の制約のもとでの 電力配分 とは,𝑃𝑖 ≥0(1 ≤𝑖 ≤𝑛)かつ∑𝑛𝑖=1𝑃𝑖 ≤𝑃を満たす実数の組(𝑃1,…,𝑃𝑛)のことをいう.その 合計容量 を
𝑛∑𝑖=112log(1+𝑃𝑖𝑁𝑖)で定める.
合計容量の各項は,𝑃𝑖 >0であれば,定理 8.2.4 により第𝑖通信路を電力𝑃𝑖で使ったときの容量である.𝑃𝑖 =0の本は定理 8.2.4 の対象から外れる.8.2 節で見たとおり,電力0の制約を満たす入力は密度をもたないので,そこでは容量が定まらないからである.ただし項の値そのものは12log1 =0で,電力を配らない本では何も運べない,という読みと食い違わない.運べる量について言えるのは,1本ずつの話までである.𝑃𝑖 >0の各本については,系 8.4.2 により,その1本だけを使ったときの達成レートの上限が第𝑖項12log(1 +𝑃𝑖/𝑁𝑖)に等しい.𝑛本を別々の符号で使ったときにレートの合計がそのまま達成できるか,また𝑛本をまとめて符号化すればそれを超えられるかは,どちらも本書では示さない.本節が解くのは合計容量という一つの式を電力配分について最大にする問題であって,それ以上でも以下でもない.
定義 8.6.2(注水配分). 𝑛 ≥1とし,𝑁1,…,𝑁𝑛を正の実数,𝜈を実数とする.
𝑃∗𝑖(𝜈):=max(0,𝜈−𝑁𝑖)(1≤𝑖≤𝑛)で定まる組を,水位 𝜈の 注水配分 と呼ぶ.
名前の由来は絵にある.底が段になった一続きの容器を思い浮かべる.横幅を𝑛等分し,第𝑖の区画の底の高さを𝑁𝑖にとる.そこに水を注ぐと,区画のあいだで水は行き来できるので,水面はどの区画でも同じ高さ𝜈でそろう.第𝑖の区画に入る水の深さは,底が水面より低ければ𝜈 −𝑁𝑖,底が水面より高ければ(𝑁𝑖 ≥𝜈)0である.どの区画も横幅が同じなので,入った水の量は深さに比例し,全体の量は∑𝑖max(0,𝜈 −𝑁𝑖)に比例する.これが総電力𝑃に等しくなるように水位を決める,というのが以下の筋である.
水面がそろうところが最適なのはなぜか,を絵の言葉で言っておく.以下では,対数の導関数が(log𝑒)/𝑡であることと合成関数の微分を,微積分の計算規則として既知とする.当てる相手は,この段落で12log(1 +𝑃𝑖/𝑁𝑖)を𝑃𝑖で微分するところだけである.第𝑖通信路に電力をほんの少し足したとき,合計容量の第𝑖項12log(1 +𝑃𝑖/𝑁𝑖)が電力1単位あたりどれだけ増えるかは,𝑃𝑖で微分してlog𝑒2(𝑁𝑖+𝑃𝑖)である.分母の𝑁𝑖 +𝑃𝑖は,底の高さに水の深さを足したもの,すなわちその区画の水面の高さにほかならない.だから,水面の低い区画ほど電力1単位あたりの増分が大きい.任意の配分は,区画のあいだに仕切りを立てて水面の高さをばらばらにした状態にあたり,仕切りを外すと水面がそろう,と見ればよい.水の入っている区画のうち水面がいちばん高いものから,水面がいちばん低い区画へ電力を少し移せば,減るぶんより増えるぶんが大きく,合計は増える.移して得をする組がなくなるのは,水の入っている区画の水面がすべてそろい,しかも水の入っていない区画の底がその水面以上にあるときで,これが注水配分の形にほかならない.そこでは水の入っているどの区画でも増分が同じlog𝑒2𝜈になる.このlog𝑒2𝜈が,あとで補題 8.6.4 が上から抑えるのに使う接線の傾きである.
水位の存在と一意性
道具を一つ借りる.中間値の定理,すなわち「有界閉区間の上の実数値連続関数は,両端での値のあいだのどの値もとる」という微積分の定理である.当てる相手は,定理 8.6.3 の証明で置く1変数の実数値関数𝜙(𝜈) =∑𝑛𝑖=1max(0,𝜈 −𝑁𝑖)の,有界閉区間[0,𝑁1 +𝑃]への制限だけであり,依存するのは定理 8.6.3 の証明と,同じ定理を 9.4 節で借り直している第9章 定理 9.4.9 の証明である.また,連続関数の有限個の最大値と有限和がふたたび連続であることを,微積分の計算規則として既知とする.
定理 8.6.3(水位の存在と一意性). 𝑛 ≥1,𝑃 >0とし,𝑁1,…,𝑁𝑛を正の実数とする.このとき
𝑛∑𝑖=1max(0,𝜈−𝑁𝑖)=𝑃を満たす実数𝜈がただ一つ存在する.
証明. 𝜙(𝜈) :=∑𝑛𝑖=1max(0,𝜈 −𝑁𝑖)とおく.各𝜈 ↦max(0,𝜈 −𝑁𝑖)は連続関数の最大値だから連続であり,その有限和である𝜙も連続である.
両端の値を見る.𝑁𝑖 >0より𝜙(0) =∑𝑖max(0, −𝑁𝑖) =0である.𝜈1 :=𝑁1 +𝑃とおくと,第1項だけを残して𝜙(𝜈1) ≥max(0,𝜈1 −𝑁1) =𝑃である.
𝜙は閉区間[0,𝜈1]の上で連続で,𝜙(0) =0 ≤𝑃 ≤𝜙(𝜈1)だから,借りた中間値の定理より𝜙(𝜈) =𝑃を満たす𝜈 ∈[0,𝜈1]が存在する.
そのような𝜈が二つとないことを見る.𝑁1,…,𝑁𝑛のうち最小のものを𝑁𝑖0と書く.𝜙(𝜈) =𝑃 >0を満たす𝜈については,ある𝑖でmax(0,𝜈 −𝑁𝑖) >0,すなわち𝜈 >𝑁𝑖 ≥𝑁𝑖0だから,そのような𝜈はすべて𝑁𝑖0より大きい.そこで𝑁𝑖0 ≤𝜈𝑎 <𝜈𝑏とすると,各𝑖について𝜈𝑎 −𝑁𝑖 <𝜈𝑏 −𝑁𝑖だからmax(0,𝜈𝑎 −𝑁𝑖) ≤max(0,𝜈𝑏 −𝑁𝑖)であり,第𝑖0項については𝜈𝑎 ≥𝑁𝑖0より二つの項が𝜈𝑎 −𝑁𝑖0と𝜈𝑏 −𝑁𝑖0に等しい.項ごとに足し合わせると𝜙(𝜈𝑏) −𝜙(𝜈𝑎) ≥𝜈𝑏 −𝜈𝑎 >0である.よって𝜙は𝑁𝑖0以上のところで狭義単調増加であり,そこで値𝑃をとる𝜈は一つしかない.◼
接線による上界
最適性の証明は,補題 1.1.7 の対数不等式log𝑡 ≤(𝑡 −1)log𝑒だけで通る.対数のグラフが接線より下にあるという,第7章 補題 7.2.3 でも使ったのと同じ道具である.注水配分の点で対数に接線を引き,そのぶんだけ上から抑える.それを述べるのが補題 8.6.4 である.
補題 8.6.4(注水配分での接線). 𝑁 >0,𝜈 >0とし,𝑝∗ :=max(0,𝜈 −𝑁)とおく.このとき,どの実数𝑡 ≥0についても
12log(1+𝑡𝑁)≤12log(1+𝑝∗𝑁)+log𝑒2𝜈(𝑡−𝑝∗)である.
証明. 1 +𝑡/𝑁 =(𝑁 +𝑡)/𝑁と1 +𝑝∗/𝑁 =(𝑁 +𝑝∗)/𝑁はどちらも正である.補題 1.1.7 の対数不等式log𝑢 ≤(𝑢 −1)log𝑒を𝑢 :=(𝑁 +𝑡)/(𝑁 +𝑝∗)に当てると
log(1+𝑡𝑁)−log(1+𝑝∗𝑁)=log𝑢≤𝑡−𝑝∗𝑁+𝑝∗log𝑒である.両辺を2で割ると,示すべきことは
𝑡−𝑝∗2(𝑁+𝑝∗)log𝑒≤log𝑒2𝜈(𝑡−𝑝∗)に帰着する.𝜈と𝑁の大小で場合を分ける.
𝜈 >𝑁のときは𝑝∗ =𝜈 −𝑁だから𝑁 +𝑝∗ =𝜈であり,両辺は等しい.
𝜈 ≤𝑁のときは𝑝∗ =0だから𝑁 +𝑝∗ =𝑁であり,𝑡 −𝑝∗ =𝑡 ≥0である.0 <𝜈 ≤𝑁とlog𝑒 >0から𝑡log𝑒2𝑁 ≤𝑡log𝑒2𝜈であり,これが示すべき不等式である.◻
注水の最適性
定理 8.6.5(注水配分の最適性). 𝑛 ≥1,𝑃 >0とし,𝑁1,…,𝑁𝑛を正の実数とする.実数𝜈が∑𝑛𝑖=1max(0,𝜈 −𝑁𝑖) =𝑃を満たすとする.このとき注水配分(𝑃∗1(𝜈),…,𝑃∗𝑛(𝜈))は総電力𝑃の制約のもとでの電力配分(定義 8.6.1)であり,𝑃′𝑖 ≥0(1 ≤𝑖 ≤𝑛)かつ∑𝑛𝑖=1𝑃′𝑖 ≤𝑃を満たすどの実数の組(𝑃′1,…,𝑃′𝑛)についても
𝑛∑𝑖=112log(1+𝑃′𝑖𝑁𝑖)≤𝑛∑𝑖=112log(1+𝑃∗𝑖(𝜈)𝑁𝑖)である(𝑃∗𝑖(𝜈)は定義 8.6.2 の注水配分).
証明. 注水配分が電力配分であることを見る.各𝑃∗𝑖(𝜈) =max(0,𝜈 −𝑁𝑖)はmaxの形から0以上であり,総和は仮定よりちょうど𝑃で,𝑃以下である.よって定義 8.6.1 の電力配分の条件を満たす.
まず𝜈 >0を見る.仮定の和は𝑃 >0だから,ある𝑖でmax(0,𝜈 −𝑁𝑖) >0,すなわち𝜈 >𝑁𝑖 >0である.
各項に補題 8.6.4 を,𝑁 :=𝑁𝑖,𝑡 :=𝑃′𝑖ととって当てると,𝑝∗ =𝑃∗𝑖(𝜈)であり
12log(1+𝑃′𝑖𝑁𝑖)≤12log(1+𝑃∗𝑖(𝜈)𝑁𝑖)+log𝑒2𝜈(𝑃′𝑖−𝑃∗𝑖(𝜈))である.𝑖について足すと
𝑛∑𝑖=112log(1+𝑃′𝑖𝑁𝑖)≤𝑛∑𝑖=112log(1+𝑃∗𝑖(𝜈)𝑁𝑖)+log𝑒2𝜈(𝑛∑𝑖=1𝑃′𝑖−𝑛∑𝑖=1𝑃∗𝑖(𝜈))となる.仮定より∑𝑖𝑃∗𝑖(𝜈) =𝑃であり,∑𝑖𝑃′𝑖 ≤𝑃だから括弧の中は0以下である.𝜈 >0とlog𝑒 >0より係数は正だから,最後の項は0以下であり,落として主張を得る.◼
証明で効いたのは二つだけである.接線の傾きがlog𝑒2𝜈という,𝑖によらない一つの値で抑えられること(補題 8.6.4)と,注水配分が総電力を使い切っていること(∑𝑖𝑃∗𝑖(𝜈) =𝑃)である.前者があるので,𝑛本ぶんの接線の項が∑𝑖𝑃′𝑖という一つの和にまとまる.後者があるので,その和が電力制約と直接くらべられる.雑音が強すぎて水位に届かない通信路(𝑁𝑖 ≥𝜈)で接線の傾きがそのままでは足りないところを,補題 8.6.4 の第2の場合がlog𝑒2𝑁𝑖 ≤log𝑒2𝜈で吸収している.
数で見る
例 8.6.6(2本の並列ガウス通信路). 𝑛 =2,𝑁1 =1,𝑁2 =4とする.総電力𝑃 =2のとき水位は𝜈 =3で,注水配分は(2,0),その合計容量は12log23で約0.7925ビットである.等分した配分(1,1)の合計容量は約0.6610ビットで,これより小さい.総電力𝑃 =5のときは水位が𝜈 =5で,注水配分は(4,1),合計容量は約1.3219ビット,等分した配分(2.5,2.5)の合計容量は約1.2539ビットである.
証明. 𝑃 =2のとき.水位が第2通信路の底4に届かないと見当をつけると,水が入るのは第1通信路だけで𝜈 −1 =2,すなわち𝜈 =3である.これは4以下だから見当と整合する.実際max(0,3 −1) +max(0,3 −4) =2 +0 =2で定理 8.6.3 の等式を満たし,それを満たす実数はただ一つだから,これが水位である.注水配分は(2,0)で,合計容量は12log2(1 +2/1) +12log2(1 +0/4) =12log23である.log23 =1.5849…だから約0.7925である.等分した配分では12log22 +12log21.25 =0.5 +0.1610…で約0.6610である.
𝑃 =5のとき.今度は水位が4を超えると見当をつけると,両方の通信路に水が入るので(𝜈 −1) +(𝜈 −4) =5,すなわち𝜈 =5である.これは4より大きいから見当と整合する.実際max(0,5 −1) +max(0,5 −4) =4 +1 =5で,これが水位である.注水配分は(4,1)で,合計容量は12log25 +12log21.25 =1.1610… +0.1610…で約1.3219である.等分した配分では12log23.5 +12log21.625 =0.9037… +0.3502…で約1.2539である.◼
例 8.6.6 の前半は,雑音の強い通信路を使わないほうがよい場合である.総電力2では水位3が第2通信路の雑音4に届かないので,そちらには何も配らない.後半では総電力が5に増えて水位が5まで上がり,第2通信路にも1だけ配られる.注水の絵でいえば,注ぐ水の量を増やしていくと,あるところで二つめの区画の底が水没する,ということである.どちらの場合も等分した配分より合計容量が大きい.差は前半が約0.13ビット,後半が約0.07ビットで,合計容量に対する割合で見ると前半が約17パーセント,後半が約5パーセントである.後半では水位が第2通信路の底を超えていて,注水配分も等分した配分もどちらの通信路にも電力を配っており,二つの配分の違いがそれだけ小さい.
帯域ごとに雑音が違うとき. 定義 8.6.1 の並列ガウス通信路は,8.5 節の帯域制限ガウス通信路の雑音が帯域ごとに違う場合にあたる.帯域を等しい幅に切り,第𝑖の帯域を,1標本あたりの雑音の分散が𝑁𝑖であるガウス通信路と読む.8.5 節が帯域制限ガウス通信路を分散𝑁0/2のガウス通信路の使用に読み替えたのと同じ換算である.第𝑖の帯域に配る電力も1標本あたりで測って𝑃𝑖と書けば,総電力をどの帯域に配るかという問題がそのまま定義 8.6.1 の形になる.どの帯域も幅が同じで1秒あたりの標本の個数がそろっているので,1標本あたりで測るか1秒あたりで測るかは,全体に共通の因子の違いにしかならない.雑音の弱い帯域に電力を集め,雑音が水位を超える帯域は使わない,というのが定理 8.6.5 の答えである.雑音の強さが帯域によらないときは全部の𝑁𝑖が等しく,注水配分は等分になって,8.5 節の設定に戻る.
InformationTheory — 形式化検証つき情報理論教科書(レビュー版).数式は MathJax + AMS Euler で事前レンダリング.