GoToTheFuture D言語とかやってます

注水定理のお気持ち

2019-02-24
けーさん

注水定理とは,雑音の大きさが異なる複数の通信路(チャネル)が存在するときに,チャネルに配分する電力の最適解を与える定理です.

注水定理について検索しても日本語でのわかりやすい解説が無い気がしたので,注水定理のお気持ちをまとめておきます.

注水定理での問題設定と注水定理は次の通りです.

問題
$M$個のチャネルがあり,それぞれには電力$N_i$の白色雑音が存在する. 限られた電力$P$を各チャネルに$P_i$ずつ配分して通信するとき,合計の通信路容量が最大になるようにするにはどのように電力を配分すればいいか?

注水定理
ある電力$Q$が存在して$N_i \leq Q$を満たすチャネルに対して$P_i + N_i = Q$を満たすように電力$P_i$を配分するとき通信路容量が最大となる

注水(Water filling)定理とは,底に$M$個の山がある水槽に合計$P$だけの水を注いでみたときの様子から名前が付けられているようです. それぞれの山の高さを$N_i$とすると,全領域で水面の高さが一定値$Q$になり,各場所には$P_i = Q - N_i$だけ水が注がれているので,注水定理の主張と一致します.

この注水定理はMIMOの電力割当や,有色雑音においてOFDM通信のサブキャリアへの電力割当などに応用されます.

注水定理の導出

では,注水定理の簡単な導出を考えます.

問題を数式で形式的に書くと次のようになります.

問題
$$ \begin{align} &\text{maximize} &\sum_{m=1}^{M}\log(1 + P_i / N_i) \\ &\text{subject to} &\left\{ \begin{array}{l} P = \displaystyle \sum_{m=1}^{M} P_i \\ P_i \geq 0 \end{array} \right. \end{align} $$

この問題を解くために($P_i \geq 0$を忘れて)ラグランジュの未定乗数法を用いてもいいですが,もう少し直感的な導出をします.

最適化手順

  1. 制約に合致するように適当に(ランダムに)各チャネルに電力$P_i > 0$を割り当てる
  2. $P_i > 0$なチャネルの中で「最も効率の悪いチャネル」から「最も効率の良いチャネル」へ電力を少しだけ移動する
  3. 2.を繰り返す

ここでいう効率とは,「追加で微小電力$\Delta P$だけ与えたときのチャネル容量の増分」と定義し,数式では次のように書けます.

手順2.ではあるチャネルから$\Delta P$だけ引いて,別のチャネルに$\Delta P$を与えているので制約条件は満たされています.

この最適化手順が停止するのは,明らかに$P_i > 0$な全チャネルで効率が一致するときで,そのときにはどのチャネル間で電力を移動してもチャネル容量は変化せず収束しています.

これは,ある定数$A$が存在して,$P_i > 0$を満たすチャネル$i$が以下を満たすということです.

また$P_i \leq 0$は,$N_i \leq \Delta P / A$のときです. 冒頭に示した注水定理では$Q= \Delta P / A$と置いています.

このようにして注水定理の気持ちを考えることができます.


Similar Posts

Comments