情報理論・符号理論の問題

難易度 4大学院入試の標準レベル証明問題大学数学情報理論・符号理論

$n \geq 2$ を整数とし、情報源記号 $a_{1}, a_{2}, \dots, a_{n}$ がそれぞれ確率 $p_{1}, p_{2}, \dots, p_{n}$ で現れるとする。ただし $p_{i} > 0$ $(i = 1, \dots, n)$ , $\sum_{i = 1}^{n} p_{i} = 1$ とする。

各 $a_{i}$ に ${0, 1}$ 上の語 $w_{i}$ を割り当て、 $i \neq = j$ ならば $w_{i}$ が $w_{j}$ の接頭語（ $w_{j}$ の先頭部分。 $w_{j}$ 自身も含む）でないものを 2 元の語頭符号とよぶ。 $w_{i}$ の長さを $l_{i}$ （ $0$ 以上の整数）とし、平均符号長を $L ˉ = \sum_{i = 1}^{n} p_{i} l_{i}$ とする。

2 元の語頭符号のうち平均符号長が最小のもの（最適符号）の 1 つを $C$ とし、 $C$ の符号長を $l_{1}, \dots, l_{n}$ 、その最大値を $L = max_{i} l_{i}$ とする。このとき、 $C$ において長さが $L$ の符号語の個数は偶数である（特に $2$ 以上である）ことを証明せよ。

なお、次のクラフトの不等式とその逆は用いてよい: $0$ 以上の整数 $m_{1}, \dots, m_{n}$ に対し、符号長が $m_{1}, \dots, m_{n}$ の 2 元の語頭符号が存在するための必要十分条件は $\sum_{i = 1}^{n} 2^{- m_{i}} \leq 1$ である。

この問題で使うもの

語頭符号とクラフトの不等式（説明と入口の問題）

この問題を解けるようになるまで（12 技能）

算数中学高校大学大学院

読み込み中…

右端（太枠）がこの問題で使う技能です。左へドラッグすると、さらに前の前提をさかのぼれます。技能を押すと、そこまでの道筋が光ります。

一覧で見る（前提が先）

ヒント

行き詰まったら、上から順に 1 つずつ開いてください。

ヒント 1

最適符号ではクラフトの不等式 $\sum_{i} 2^{- l_{i}} \leq 1$ が等号で成り立つことをまず示し、その等式の偶奇を調べましょう。

ヒント 2

$\sum_{i} 2^{- l_{i}} < 1$ と仮定すると、 $2^{L} \sum_{i} 2^{- l_{i}}$ が整数であることから $\sum_{i} 2^{- l_{i}} \leq 1 - 2^{- L}$ がいえます。このとき最長の符号語を 1 つだけ 1 文字短くできます。

ヒント 3

短くした符号長でもクラフトの和が $1$ 以下に収まるので、クラフトの不等式の逆から語頭符号が存在し、平均符号長が $p_{j} > 0$ だけ小さくなって最適性に矛盾します。等式が示せたら、両辺に $2^{L}$ を掛けて長さ $L$ の項とそれ以外の項に分けます。

採点の観点と模範解答

自分で証明を書いてから、採点の観点で見比べてください。

採点の観点を見る

$n \geq 2$ と語頭条件から空語が符号語になりえないことを示し、 $L \geq 1$ を確認している（1 点）
$\sum_{i} 2^{- l_{i}} < 1$ と仮定し、 $2^{L} \sum_{i} 2^{- l_{i}}$ が整数であることから $\sum_{i} 2^{- l_{i}} \leq 1 - 2^{- L}$ を導いている（2 点）
最長の符号語 1 つの長さを $L - 1$ にしてもクラフトの和が $1$ 以下であることを確かめ、クラフトの不等式の逆で語頭符号の存在を述べている（2 点）
平均符号長が $p_{j} > 0$ だけ減ることから最適性に矛盾させ、 $\sum_{i} 2^{- l_{i}} = 1$ を結論している（2 点）
等式に $2^{L}$ を掛け、 $l_{i} < L$ の項がすべて偶数で $2^{L}$ も偶数であることから長さ $L$ の符号語の個数が偶数（したがって 2 以上）であると結論している（3 点）

結果を記録する（このブラウザにだけ保存されます）:

模範解答を読む

方針. まず最適符号ではクラフトの不等式が等号 $\sum_{i} 2^{- l_{i}} = 1$ で成り立つことを背理法で示す。次に両辺に $2^{L}$ を掛けて偶奇を比べる。

ステップ 1（ $L \geq 1$ ）. ある $i$ で $l_{i} = 0$ と仮定すると、 $w_{i}$ は空語である。 $n \geq 2$ なので $j \neq = i$ がとれ、空語は任意の語 $w_{j}$ の接頭語であるから、語頭符号の条件に反する。よってすべての $i$ で $l_{i} \geq 1$ であり、特に $L \geq 1$ 。

ステップ 2（クラフトの等式）. $S = \sum_{i = 1}^{n} 2^{- l_{i}}$ とおく。 $C$ は語頭符号なので、クラフトの不等式より $S \leq 1$ 。 $S = 1$ を背理法で示すため、 $S < 1$ と仮定する。

各 $i$ で $l_{i} \leq L$ なので $2^{L - l_{i}}$ は正の整数であり、
$N = 2^{L} S = i = 1 \sum n 2^{L - l_{i}}$
は整数である。 $S < 1$ より $N < 2^{L}$ 、整数なので $N \leq 2^{L} - 1$ 、すなわち
$S \leq 1 - 2^{- L} . (1)$

$l_{j} = L$ となる $j$ を 1 つとり、新しい符号長を $l_{j}^{'} = L - 1$ , $l_{i}^{'} = l_{i} (i \neq = j)$ と定める。ステップ 1 より $L - 1 \geq 0$ なので、これらは $0$ 以上の整数である。 $2^{- (L - 1)} = 2^{- L} + 2^{- L}$ だから、 $(1)$ より
$i = 1 \sum n 2^{- l_{i}^{'}} = S - 2^{- L} + 2^{- (L - 1)} = S + 2^{- L} \leq 1.$
クラフトの不等式の逆より、符号長が $l_{1}^{'}, \dots, l_{n}^{'}$ の 2 元の語頭符号 $C^{'}$ が存在する。その平均符号長は
$i = 1 \sum n p_{i} l_{i}^{'} = L ˉ - p_{j} < L ˉ$
（ $p_{j} > 0$ による）であり、 $C$ の平均符号長が最小であることに矛盾する。よって $S = 1$ 。

ステップ 3（偶奇の比較）. $S = 1$ の両辺に $2^{L}$ を掛けると
$i = 1 \sum n 2^{L - l_{i}} = 2^{L} . (2)$
長さが $L$ の符号語の個数を $m$ とする（ $L$ は最大値なので $m \geq 1$ ）。 $(2)$ の左辺を $l_{i} < L$ の項と $l_{i} = L$ の項に分けると
$i : l_{i} < L \sum 2^{L - l_{i}} + m = 2^{L} .$
$l_{i} < L$ の項では $L - l_{i} \geq 1$ なので $2^{L - l_{i}}$ は偶数であり、その和も偶数である。右辺 $2^{L}$ はステップ 1 より $L \geq 1$ なので偶数である。したがって $m = 2^{L} - \sum_{i : l_{i} < L} 2^{L - l_{i}}$ は偶数である。

結論. $m$ は偶数であり、 $m \geq 1$ と合わせて $m \geq 2$ 。よって最適符号 $C$ において長さが $L$ の符号語の個数は偶数（特に 2 以上）である。 $■$

（注: この事実は、ハフマン符号の構成で確率の小さい 2 記号を最長の兄弟符号語として扱ってよいことの根拠の 1 つになる。）

この問題の確認

AI が作成した問題です。公開前に次の確認を行いました。

別の AI が模範解答を見ずに 3 回証明を試み、3 回証明できました
2 つの AI が独立に、模範解答の証明を 1 ステップずつ確かめました
AI の査読で、条件・解説・表記を確認しました
答えの正しさについて慎重に扱うべき点が見つからなかったため、自動で公開しました

確認の方法について

間違いを報告する

この問題の誤り・分かりにくい点・難易度や学年のずれを知らせる