語頭符号とクラフトの不等式

符号長 $l_{1}, \dots, l_{m}$ の $D$ 元語頭符号（瞬時符号）が存在するかを、クラフトの不等式 $\sum_{i} D^{- l_{i}} \leq 1$ で判定でき、存在するときは符号語を 1 組作れる

前提

指数の拡張と指数関数（数学II 指数関数と対数関数）

この技能までの道筋（11 技能）

算数中学高校大学大学院

読み込み中…

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

一覧で見る（前提が先）

分数のたし算・ひき算（算数計算と数のきまり）
小数の四則計算（算数計算と数のきまり）
正負の数の加法・減法（中学数学数と式）
分数のかけ算・わり算（算数計算と数のきまり）
四則の混じった計算の順序（算数計算と数のきまり）
正負の数の乗除・累乗と四則混合（中学数学数と式）
約数の見つけ方（算数整数の性質）
素因数分解と約数の個数（算数整数の性質）
平方根の意味と根号の簡単化（中学数学数と式）
根号の乗除と加減（中学数学数と式）
指数の拡張と指数関数（数学II 指数関数と対数関数）

説明

語頭符号（瞬時符号）とは、どの符号語も他の符号語の先頭部分（語頭）になっていない符号のことです。この性質があれば、受け取った記号列を先頭から読み、符号語に一致した時点ですぐに区切って解読できます。この技能では、符号長 $l_{1}, \dots, l_{m}$ を指定したときに、 $D$ 種類の記号 $0, 1, \dots, D - 1$ で作る語頭符号が存在するかを、クラフトの不等式 $\sum_{i = 1}^{m} D^{- l_{i}} \leq 1$ で判定します。存在する場合は、符号語を実際に 1 組作ります。データ圧縮で記号ごとの符号長を設計するときの基本になる考え方です。

なぜそうしてよいのか

長さ $l$ の符号語 $w = w_{1} w_{2} \dots w_{l}$ （各 $w_{k}$ は $0, \dots, D - 1$ の整数）に、数 $v (w) = \sum_{k = 1}^{l} w_{k} D^{- k}$ を対応させます。これを $D$ 進小数 $0. w_{1} \dots w_{l}$ と呼びます。 $D^{l} v (w) = w_{1} D^{l - 1} + \dots + w_{l}$ は $0$ 以上 $D^{l} - 1$ 以下の整数で、この整数を $D$ 進法で $l$ 桁に書いた並びがちょうど $w$ です。さらに $I (w) = {x ∣ v (w) \leq x < v (w) + D^{- l}}$ と定め、これを $w$ の区間と呼びます。 $I (w)$ の長さは $D^{- l}$ です。この議論は $D$ 進展開の一意性を使わず、数の不等式だけで進めます。

要になるのは次の評価です。各桁が $D - 1$ 以下なので、 $\sum_{k = p + 1}^{l} w_{k} D^{- k} \leq (D - 1) \sum_{k = p + 1}^{l} D^{- k} = D^{- p} - D^{- l}$ が成り立ちます。
- (ア) $u$ が $w$ の語頭のとき（ $u$ の長さ $p < l$ ）、 $v (w) = v (u) + \sum_{k = p + 1}^{l} w_{k} D^{- k}$ です。よって $v (u) \leq v (w)$ かつ $v (w) + D^{- l} \leq v (u) + D^{- p}$ となり、 $I (w) \subset I (u)$ です。
- (イ) $u$ （長さ $p$ ）と $w$ （長さ $q$ ）のどちらも他方の語頭でないとき、両方に共通する長さの範囲内に、初めて食い違う桁 $r$ があります。 $u_{r} < w_{r}$ としてよく、共通部分を $c = u_{1} \dots u_{r - 1}$ とおきます。上の評価から $v (u) + D^{- p} \leq v (c) + u_{r} D^{- r} + D^{- r} \leq v (c) + w_{r} D^{- r} \leq v (w)$ となります。つまり $I (u)$ は $I (w)$ より完全に左にあり、両者は重なりません。
- (ウ) $p = 0$ として評価を使うと $v (w) + D^{- l} \leq 1$ となるので、どの区間も $[0, 1)$ に収まります。

必要性：語頭符号なら、(イ) より区間どうしは重なりません。左端の小さい順に並べると、各区間は前の区間の右端以降から始まります。 $[0, 1)$ の中に重ならずに並ぶので、長さの合計は 1 以下、すなわち $\sum_{i} D^{- l_{i}} \leq 1$ です。

十分性： $\sum_{i} D^{- l_{i}} \leq 1$ とし、長さを $l_{1} \leq \dots \leq l_{m}$ と並べて $a_{i} = \sum_{j < i} D^{- l_{j}}$ （ $a_{1} = 0$ ）とおきます。 $N_{i} = D^{l_{i}} a_{i} = \sum_{j < i} D^{l_{i} - l_{j}}$ は、 $l_{i} - l_{j} \geq 0$ なので整数です。また $a_{i} + D^{- l_{i}} \leq \sum_{j} D^{- l_{j}} \leq 1$ より $0 \leq N_{i} \leq D^{l_{i}} - 1$ なので、 $N_{i}$ は $D$ 進法でちょうど $l_{i}$ 桁に書けます（頭に 0 を補う）。その並びを $w_{i}$ とすると $v (w_{i}) = a_{i}$ で、区間 $I (w_{i}) = [a_{i}, a_{i + 1})$ は隙間なく順に並び、互いに重なりません。もし $w_{j}$ が $w_{i}$ の語頭なら、(ア) より $I (w_{i}) \subset I (w_{j})$ となって重なってしまうので、これは起こりません。よって語頭符号になります。

手順

クラフト和 $K = \sum_{i = 1}^{m} D^{- l_{i}} = \sum_{i = 1}^{m} \frac{1}{D ^{l_{i}}}$ を計算する。
$K \leq 1$ なら語頭符号は存在し、 $K > 1$ なら存在しないと判定する（等号 $K = 1$ の場合も存在する）。
符号語を作るときは、符号長を小さい順 $l_{1} \leq l_{2} \leq \dots \leq l_{m}$ に並べ替える。
累積和 $a_{i} = \sum_{j < i} D^{- l_{j}}$ （ $a_{1} = 0$ ）を求め、整数 $N_{i} = D^{l_{i}} a_{i}$ を計算する。 $N_{i + 1} = (N_{i} + 1) D^{l_{i + 1} - l_{i}}$ で順に求めてもよい。
$N_{i}$ を $D$ で割り、余りを書き留めて商をまた $D$ で割る、ということを商が 0 になるまで繰り返す。余りを逆順に並べたものが $D$ 進表記である。
$N_{i}$ の $D$ 進表記がちょうど $l_{i}$ 桁になるよう、桁が足りなければ頭に 0 を補う。その $l_{i}$ 桁の並びを $i$ 番目の符号語とする。

例題

3 元（記号 $0, 1, 2$ ）の語頭符号で、符号長が $1, 2, 2, 2, 3, 3, k$ の 7 個の符号語をもつものを作りたい。そのような語頭符号が存在する最小の正の整数 $k$ を求めよ。

例題の解答

【手順 1】 $k$ 以外の 6 個のクラフト和を計算します。 $\frac{1}{3} + 3 \cdot \frac{1}{9} + 2 \cdot \frac{1}{27} = \frac{9}{27} + \frac{9}{27} + \frac{2}{27} = \frac{20}{27}$ なので、全体は $K = \frac{20}{27} + 3^{- k}$ です。

【手順 2】存在の条件は $K \leq 1$ 、すなわち $3^{- k} \leq \frac{7}{27}$ です。
- $k = 1$ のとき： $3^{- 1} = \frac{9}{27} > \frac{7}{27}$ なので不成立で、存在しません。
- $k = 2$ のとき： $3^{- 2} = \frac{3}{27} \leq \frac{7}{27}$ なので成立し、存在します。

よって最小の $k$ は $2$ です。

確認として、 $k = 2$ で実際に符号を作ります。
【手順 3】長さを並べ替えると $1, 2, 2, 2, 2, 3, 3$ です。

【手順 4〜6】 $a_{i}$ から $N_{i} = 3^{l_{i}} a_{i}$ を求め、3 進法で $l_{i}$ 桁に書きます。
- $a_{1} = 0$ ： $N_{1} = 0$ を 1 桁にして $0$ 。
- $a_{2} = \frac{1}{3}$ ： $N_{2} = 9 \cdot \frac{1}{3} = 3$ 。 $3 \div 3 = 1$ 余り $0$ 、 $1 \div 3 = 0$ 余り $1$ なので $10$ 。
- $a_{3} = \frac{4}{9}$ ： $N_{3} = 4$ で $11$ 。
- $a_{4} = \frac{5}{9}$ ： $N_{4} = 5$ で $12$ 。
- $a_{5} = \frac{6}{9}$ ： $N_{5} = 6$ で $20$ 。
- $a_{6} = \frac{7}{9}$ ： $N_{6} = 27 \cdot \frac{7}{9} = 21$ 。 $21 \div 3 = 7$ 余り $0$ 、 $7 \div 3 = 2$ 余り $1$ 、 $2 \div 3 = 0$ 余り $2$ なので $210$ 。
- $a_{7} = \frac{22}{27}$ ： $N_{7} = 27 \cdot \frac{22}{27} = 22$ 。 $22 \div 3 = 7$ 余り $1$ 、 $7 \div 3 = 2$ 余り $1$ 、 $2 \div 3 = 0$ 余り $2$ なので $211$ 。

得られた符号 ${0, 10, 11, 12, 20, 210, 211}$ は、どの語も他の語の語頭になっていないので、確かに語頭符号です。

答え: $2$

よくある誤り

指数の符号を逆にして $\sum_{i} D^{l_{i}} \leq 1$ を調べてしまう誤り。長さ $l$ の符号語の区間の長さは $D^{- l} = \frac{1}{D ^{l}}$ で、長い符号語ほど小さくなる。正しくは $\sum_{i} D^{- l_{i}} \leq 1$ を調べる。
不等式を満たせば、与えられた符号そのものが語頭符号だと思ってしまう誤り。例えば ${0, 01}$ は $2^{- 1} + 2^{- 2} = \frac{3}{4} \leq 1$ を満たすが、 $0$ が $01$ の語頭なので語頭符号ではない。不等式が保証するのは、その符号長をもつ語頭符号が少なくとも 1 つ存在することだけである。
長さを並べ替えずに累積和で割り当ててしまう誤り。例えば 2 元で長さ $2, 1$ の順に処理すると、1 個目は $00$ になる。2 個目は $a_{2} = \frac{1}{4}$ で、 $N_{2} = 2^{1} \cdot \frac{1}{4} = \frac{1}{2}$ が整数にならない。無理に切り捨てて $0$ とすると、 $0$ が $00$ の語頭になってしまう。正しくは長さを $1, 2$ と小さい順に並べ、 $N_{1} = 0, N_{2} = 4 \cdot \frac{1}{2} = 2 = 1 0_{(2)}$ から $0, 10$ とする。
桁数を合わせるための 0 を末尾に付けてしまう誤り。例えば 2 元で $N = 1$ 、 $l = 3$ のとき、 $100$ とするのは誤り。 $10 0_{(2)} = 4 \neq = 1$ である。正しくは頭に 0 を補って $001$ とする。このとき $v (001) = \frac{1}{8} = \frac{N}{2 ^{3}}$ となる。

この説明は AI が書き、別の AI が例題を独立に解いて答えを確かめ、説明を一歩ずつ査読しました。

入口の問題

この技能を使う問題

この技能の次に学べること

ハフマン符号（大学数学情報理論・符号理論）