201
問題の解答
1 章の問題の解答
1-1 (a) 復号可能, C4 を反転した Ĉ4 = {0, 100, 101, 11} を考える. 実は , これはプ
レフィックス符号 (1.3 節参照) である.
a
b
c
d
^
C4
(b) 復号可能でない. (c) 復号可能. “01” が先頭の目印.
1-2 (a) と (b) は Kraft の不等式を満足するのでプレフィックス符号が作れるが ,
(c) には作れない. 例えば , (b) に対しては
1-3 終端ノード s が表す 2 進列の長さを `(s) とし , 2−`(s) をその終端ノード s の
重みとする. 完全ならその重み (全終端ノード の重みの総和) が 1 であること
を言えばよい. ある完全な (2 進) 木 T があったとして, そのなかで同じ親ノー
ド s0 を持つ二つの終端ノード s1 と s2 を考える. s1 と s2 を取り去って, s0
を代りの終端ノード とした木もやはり完全である. これを T 0 とする. 明らか
に 2−`(s0 ) = e−`(s1 ) + e−`(s2 ) であるから , s1 と s2 の重みの和は s0 の重み
に等しい. したがって, T 0 の重みは T の重みに等しい. さらに , T 0 から二つ
の終端ノード を取り去って得られる完全木 T 00 を考えると, T 00 の重みも T の
重みと同じである. この手続きを繰り返していくと完全木をどんどんと小さ
くすることができ, 最後にルート・ノード のみからなる木が得られる. この木
の重みは明らかに 1 である. したがって, 最初の完全木 T の重みも 1 である.
202
問題の解答
1-4 符号 CA は例えば次のように書ける.
4
2
5
1
6
3
7
1-5
P∞
(1) 整数 i は長さ i の符号語で表されるから , f (CB ) =
2−` = 1. 一
`=1
方, i > 0 の標準 2 進表現では , 長さ 1 のものが 1 個, 長さ 2 のものが
2 個, 長さ 3 のものが 4 個, 一般に , 長さ ` のものが 2`−1 個ある. した
P∞ `−1 −2`
がって, f (CC ) =
2 2
= 1/2. 同様にして, f (CD ) = 1.
`=1
(2) CD がプレフィックス符号. CB と CC は各符号語を逆にひっくり返せ
ばプレフィックス符号 ĈB と ĈC になる.
2
1
3
6
2
3
1
^
CB
^
CC
(3) ĈB と CD は完全な符号.
なお, CB や CC , 問題 1-1 の (a) の符号などは逆さまに見るとプレフィックス
符号となる. プレフィックス (prefix) とは語頭という意味があり, プレフィッ
クス (条件) 符号は本来は「どの符号語も他の符号語の先頭部に現れない条件
を満足する符号」として定義される. この条件は符号木のど の中間ノード も
符号語にならないと言い替えることができる. ひっくり返すとプレフィックス
符号になるとは , 逆に , 「どの符号語も他の符号語の語尾 (suffix) に現れない
条件を満足する符号」ということができる. その意味で , そのような符号はサ
フィックス (条件) 符号ということができる.
1-6
(1) 1 ビット . 最適な符号が簡単に見つかる. (2) 2 − (3/4) log2 3 ビット
(3) 21/8 ビット . 最適な符号が簡単に見つかる. (4) 約 2.2464 ビット
最適な符号は以下の通り.
1 章の問題の解答
203
(3)
(1)
1-7
(1) p = {2−2 , 2−2 , 2−2 , 2−3 , 2−4 , 2−4 }
(2) この符号は Kraft の不等式を満たさないので , すべての符号語を用いよ
うとすると復号可能ではなくなる. しかし , 幾つかの符号語は決して使
われないとすれば復号可能になる. 例えば , 出現確率が p = {1/2, 1/2,
0, 0, 0, 0} であれば文字 “c”, “d”, “e”, “f” は決して現れないので復号
可能で , しかもこの符号は最適になる. p = {0, 0, 1/4, 1/4, 1/4, 1/4}
でも同様.
1-8
(1) 二元エント ロピ 関数を
∆
h2 (x) = − x log2 x − (1 − x) log2 (1 − x)
とおけば , H(p) = h(pa ). これは , 下図のように , pa = 0, 1 で H(p) =
0, pa = 1/2 で最大値 H(p) = 1 を取り, 上に凸で pa = 1/2 を中心に左
右対称な関数になる. pa = 0, 1 付近で傾きが無限大になる.
1
0.8
0.6
0.4
0.2
0
0
0.2
0.4
0.6
0.8
1
pa
(2) H(p) = 1 − pa + h(pa ).
1-9 最初と 3 番目に対する最適符号はわかっている. 2 番目と最後の情報源に対し
て Huffman のアルゴ リズムを適用する. (1) Lmin = 1 = H(p), (2) Lmin =
1 > H(p), (3) Lmin = 21/8 = H(p), (4) Lmin = 2.3 > H(p) ≈ 2.246.
1-10 定理 1-1 (1) より, 復号可能な符号 C があったとすれば , その符号語長 la は
Kraft の不等式 (1.2 ) をみたす. したがって, 定理1-1 (2) より, 各文字の符号
204
問題の解答
語長が la であるようなプレフィックス符号 C0 が存在する. 明らかに C と C0
の平均符号長は同じである. このことから , 平均符号長 Lmin の最適な符号が
あれば Lmin を平均符号長とするプレフィックス符号も存在することがいえ
る. したがって, 最適な符号はプレフィックス符号の中にもある.
1-11
(1) “64W +36W 20B 320W +30W (EOL)” を対応表で符号語に置き換える.
(2) 最初に白の Make up 符号, 次に白の Terminating 符号, そして黒の
Make up 符号と Terminating 符号の順に見ていけば , “64W + 5W 3B
960W +6W (EOL)” = “69W 3B 966W (EOL)”. 最初を黒と仮定する
と , “2B 2W 3B 1608W 3B (EOL)” となる.
1-12 pa ≥ pb ≥ pc と仮定すると, Huffman のアルゴ リズムが与える符号は必ず
Lmin = 2 − pa を満たすので , pa → 1 のとき, Lmin → 1. 一方, このときに
は H(p) → 0 でもあるから , H(p) + 1 − Lmin → 0 となり, 文字の出現確率
のエントロピと最小平均符号長の差が上限 1 に近付く. エントロピはいくら
でも小さくなるが , 文字が 2 個以上なら符号語長は 1 以上のためである. 一
方, pa = pb なら , Lmin = (3/2) + (pc /2) であるから , 問題 1-8 の結果より,
g(p) =
1
3
− pc + {−pc log2 pc − (1 − pc ) log2 (1 − pc )} .
2
2
g(p) は pc の関数として上に凸なので , 最小値は pc = 0 もしくは pc = 1/3 で
得られる. 計算すれば , pc → 0 で g(p) は最小値 1/2 に近付く. このように ,
極端な出現確率の偏りがない限り, 定理 1-5 による Lmin の上界はかなり粗い
ことがわかる.
∆
1-13 n 次の拡大情報源の i 番目の出力文字を Xn
i = X(i−1)n+1 X(i−1)n+2 · · · Xin
n
n
n
とする. 仮定より, 任意の xn ∈ An に対して, Pr{Xn
i = x } = Pr{X = x }
(n)
∆
であるから , pxn = Pr{Xn = xn } とおけば , この拡大情報源はアルファベッ
(n)
ト An , 文字の出現確率 p(n) = {pxn , xn ∈ An } を持つ情報源と考えること
ができる. 今までと同じように , 各 (拡大) 文字 xn に対して符号語を割り当
てて符号化を行なえば , 定理 1-5 より, 最適な符号の平均符号長 L(n) に対して
H(p(n) ) ≤ L(n) ≤ H(p(n) ) + 1 が成立する. H(p(n) ) = H(X n ) であるか
ら , 系が得られる.
1-14 N = |A|n とすれば , 総単位操作数は αN log N + β
PN
log ` である. N は十
R N`=1
分に大きいとして積分近似を行なえば , 第二項は β 1 log x dx ≈ βN (log N −
1) で近似できる. したがって, 必要な操作は約 (α + β)n|A|n log |A| 単位. n
を 10 倍にすれば必要操作単位は約 10|A|9n 倍になる.
情報源の確率を知らないままに符号化を始める場合 (ユニバーサル情報源符号
化) では , 出現確率の推定と符号化を同時に行なう. その場合, 符号木を推定
された出現確率に合わせて作り直さなければならないが , Huffman のアルゴ
リズムを何回も行なうのは負担が大きい. そのため, 一度作った最適な符号木
を確率の変化に合わせて更新していく動的 Huffman アルゴ リズム, あるいは
別の適応的な符号化の手法が用いられる.
1 章の問題の解答
205
1-15 H(X|Y ) = H(X, Y ) − H(Y ) より H(X|Y ) = log2 3. 一方, Y と Z に関す
る同時確率は次のように求まる.
PY Z (y, z)
y=0
y=1
z=0
Pr{X = 2} = 1/6
Pr{X = 1} = 1/6
z=1
Pr{X = 4 or 6} = 1/3
Pr{X = 3 or 5} = 1/3
これより,
1
1
1
1
1
1
1
1
1
H(Y, Z) = − log2 − log2 − log2 − log2 = log2 3 +
6
6
6
6
3
3
3
3
3
したがって, H(Y |Z) = 1, H(Z|Y ) = log2 3 − (2/3) が得られる. 上の表よ
り, PY Z (y, z) = PY (y)PZ (z), all y, z, であることからわかるように , H(Y )
= H(Y |Z), H(Z|Y ) = H(Z) である.
1-16 性質 2 の残りを示すには
H(X) + H(Y ) − H(X, Y ) =
X
x∈A,y∈B
PX,Y (x, y) log2
PX,Y (x, y)
PX (x)PY (y)
に着目する. 性質 3 は定義にしたがって計算すれば良い. 性質 4 は性質2 の証明
を参考にする. 性質 2 を仮定して良いなら , H(X, Y ) − H(X) = H(Y |X) よ
り直接に導き出しても良い.
1-17 5 個の玉の中から 2 個を取り出すやり方は 5 × 4 = 20 だけあり, その中で両
方とも白玉の場合が 2 × 1 = 2, 両方とも赤玉の場合が 3 × 2 = 6, 最初に白
玉で次に赤玉の場合と最初に赤玉で次に白玉の場合が両方とも 3 × 2 = 6 だ
けある. これより, PX1 ,X2 (白, 白) = 1/10, PX1 ,X2 (白, 赤) = PX1 ,X2 (赤, 白) =
PX1 ,X2 (赤, 赤) = 3/10 が得られるから , H(X1 ) = H(X2 ) ≈ 0.970, H(X1 , X2 )
≈ 1.895, H(X1 |X2 ) ≈ 0.924.
1-18
(1) エントロピの性質より, H(X, Y, Z) = H(X, Y ) + H(Z|X, Y ). (X,Y )
がわかれば Z が確定することから H(Z|X, Y ) = 0 である. したがって,
H(X, Y ) = H(X, Y, Z) = H(Z) + H(X, Y |Z) ≥ H(Z).
(2) (X, Y ) の取る値はすべて同じ確率 1/36 であるから , H(X, Y ) = log2 36.
一方, 下表より, H(Z) ≈ 3.274.
z
PZ (z)
1
2
3
4
5
6
7
8
9 10 11 12
0/36 1/36 2/36 3/36 4/36 5/36 6/36 5/36 4/36 3/36 2/36 1/36
1-19 二つの確率変数 V , W に対し , 一般に H(V, W ) = H(W ) + H(V |W ) = H(V )
+ H(W |V ). ところで , W は V から決まるから , H(W |V ) = 0. したがって,
H(V ) = H(W ) + H(V |W ).
206
問題の解答
1-20 I(p, Q) は次のように書ける.
XX
px Q(y|x) log2 Q(y|x) −
x∈A y∈B
XX
px Q(y|x) log2
X
px0 Q(y|x0 )
x0 ∈A
x∈A y∈B
第一項は p に関して上に凸 (正確には線形) である. 第二項は B 上の確率分布
©P
ª
¡P
¢
p P (b|x), b ∈ B のエントロピなので , これを H
p P (·|x) と書
x x
x x
∆
く. A 上の任意の確率分布 p, q と任意の 0≤α≤1 と β = 1 − α に対し ,
Ã
H
!
X
(αpx + βqx )Q(·|x)
Ã
=H
α
X
x
px Q(·|x) + β
X
x
!
qx Q(·|x)
.
x
すでにエントロピは上に凸な確率分布の関数であることがわかっているから,
H
Ã
X
!
(αpx + βqx )Q(·|x)
Ã
≥ αH
X
!
Ã
px Q(·|x) +βH
x
x
X
!
qx Q(·|x)
x
したがって, 第二項目も p に関して上に凸である.
1-21 図 1.23 (a) より連立方程式
pa = (1 − p)pa + pb ,
pb = qpc ,
pc = pd + (1 − q)pc ,
pd = ppa
が得られるので , これより確率分布
½
p=
q
pq
p
pq
,
,
,
p + 2pq + q p + 2pq + q p + 2pq + q p + 2pq + q
¾
となる. 一方, 図 1.23 (b) より方程式
p1 =
1
p1 + p3 ,
2
p2 =
1
p1 ,
2
p 3 = p2
が得られ , 確率分布は p = {1/2, 1/4, 1/4}.
1-22 各々の状態遷移図は次の通り.
_2
3
1
0
_1
3
1
1
_
2
1
_
2
0
1
1
_
2
1
(1)
1
_
2
1
_
2
(2)
3
1
_
2
2
.
1 章の問題の解答
207
(1) 定常確率の満たすべき方程式を書けば
p0 =
2
1
p0 + p1 ,
3
2
1
1
p0 + p1 .
3
2
p1 =
これより, 定常確率は一意に求まり, p = {3/5, 2/5}.
(2) 定常確率の満たすべき方程式を書けば
p0 =
1
1
1
1
p1 + p2 + p3 , p1 = p0 , p2 = p1 , p3 = p2 .
2
2
2
2
これより, 定常確率は一意に求まり, p = {4/11, 4/11, 2/11, 1/11}.
1-23
(1) 問題 1-21 で求めた定常確率より, (a) の情報源では
H(X)
=
pa {−p log2 p + (1 − p) log2 (1 − p)}
+pc {−q log2 q + (1 − q) log2 (1 − q)} .
ただし , pa , pc は先に求めた値である. (b) の情報源では H(X) = 1/2.
(2) 問題 1-22 (1) の解より,
³
H(X) =
3
2
1
2
1
− log2 − log2
5
3
3
3
3
´
³
+
2
1
1
1
1
− log2 − log2
5
2
2
2
2
´
これを計算すれば H(X) = (3/5) log2 3. 同様にして, 問題 1-22 (2) の解
より, H(X) = 6/11.
1-24 マルコフ情報源に対するエントロピの式 (1.20 ) より,
³
1
1
2
2
H(X) = α − log2 − log2
3
3
3
3
´
³
´
1
1
3
3
+ (1 − α) − log2 − log2
.
4
4
4
4
a と b の部分のエントロピを Ha,b , c と d の部分のエントロピを Hc,d とすれ
ば , H(X) = αHa,b + (1 − α)Hc,d の形をしていることに注意. α は最初に
a もしくは b が選ばれる確率.
1-25 情報源の定常性より,
H(Xn |Xn−1 Xn−2 · · ·X1 )
=
H(Xn+k−1 |Xn+k−2 Xn+k−3 · · ·Xk )
H(Xn )
=
H(Xn+k−1 )
が任意の n と k に対して成り立つ. したがって,
H(X1 ) = H(X2 ) ≥ H(X2 |X1 ) = H(X3 |X2 ) ≥ H(X3 |X2 X1 ) =
1-26 すべての xn の確率の和が 1 であるから ,
1≥
X
xn ∈S
ε,n
PXn (xn ) ≥ |Sε,n | e−n[ H(X)+ε] .
··· .
208
問題の解答
また, Xn ∈ Sε,n の確率は少なくとも 1 − ε であるから ,
1−ε
X
≤
PXn (xn )
xn ∈Sε,n
|Sε,n | e−n[ H(X)−ε] .
≤
1-27 出現確率が 0 の文字は決して現れないので考えなくても良い. そこで , はじめ
からすべての文字の出現確率は正であり
0 < pmin ≤ pa ≤ 1,
for all a ∈ A
の範囲にあるものとする. 集合 Ŝε̂,n を
½
∆
Ŝε̂,n =
na (xn )
x ∈ A : pa − ε̂ ≤
≤ pa + ε̂, for all a ∈ A
n
n
¾
n
とおくと , xn ∈ Ŝε̂,n なら ,
(
−ε̂|A| log2
1
pmin
≤
X na (xn )
−
a∈A
n
)
log2 pa
− H(p) ≤ ε̂|A| log2
1
pmin
が成立する. ε̂|A| log2 (1/pmin ) を ε とおき, n を PXn (Ŝε̂,n ) ≥ 1 − ε となる
ように十分に大きくすれば良い.
1-28
(1) 初期確率が定常確率に一致している場合は定常情報源なので, 各文字の出
現確率は定常確率. 問題 1-21 の解答より, 出現確率は p = {1/2, 1/4, 1/4}.
1 文字のエントロピは H(X1 ) = H(p) = 3/2. 出現確率が 2 の巾乗な
ので最小符号長 Lmin は 1 文字のエントロピに一致する.
(2) 2 文字組の出現確率で , 0 以外のものは以下の通り.
p11
p23
=
=
1
2
1
4
· 12
·1
=
=
1
,
4
1
,
4
p12
p31
=
=
1
2
1
4
· 12
·1
=
=
1
,
4
1
.
4
これより, 2 文字のエントロピは H(X1 X2 ) = 2, 最小平均符号長は
Lmin (2) = 2 で , この場合も両者は一致する. 1 文字あたりのエントロ
ピと平均符号長は 2/2 = 1 ビットになる.
(3) 3 文字組について同様にすると, 0 でないのは
P111
P231
=
=
1
,
8
1
,
4
P112
P311
=
=
1
,
8
1
,
8
P123
P312
=
=
1
,
4
1
.
8
最小平均符号長 Lmin (3) も 3 文字のエントロピ H(X1 X2 X3 ) も 5/2 ビッ
トになる. これを 1 文字あたりにすると 5/(2 × 3) = 5/6 ビット .
(4) この情報源のエントロピは 1/2 ビットである. 横軸に n, 縦軸に `min (n)
= Lmin (n)/n をとって図示すれば次のようになる.
1 章の問題の解答
209
一文字あたりの平均符号長
1.5
1
0.5
0
1-29
情報源のエントロピ
1
2
n
3
4
(1) 文字 a, b, c の相対頻度 fa , fb , fc は
fa =
40
1
= ,
80
2
fb =
24
3
=
,
80
10
fc =
16
1
=
80
5
である. これをもとにして Huffman のアルゴ リズムで平均符号長最小
の符号を作れば , その 1 文字あたりの符号長は `(1) = L = 3/2 ビット .
一方, 確率 p = {fa , fb , fc } のエントロピは H(p) ≈ 1.485. エントロ
ピが平均符号長の下界になっている. この場合注意すべきなのは , p が
文字の出現確率ではなく, 与えられた文字列から求められた相対頻度で
あっても , それから計算されたエント ロピはその文字列を符号化したと
きの平均符号長の下界になっていることである.
(2) 文字列を 2 文字ずつに区切って各文字組の出現頻度を調べる. 2 文字ず
つに区切ると
bb, ca, ab, ca, aa, ab, bc, aa, bb, bc, aa, ab, ca, ab, ca, ba, bc, aa, aa, bb,
ca, ca, bc, aa, ab, ca, ab, ca, ab, bb, ca, ab, ca, aa, bc, aa, ab, bc, aa, aa,
であるから ,
faa =
fba =
fca =
10
,
40
1
,
40
10
,
40
9
fab = 40
,
4
fbb = 40
,
fcb = 0,
fac = 0,
6
fbc = 40
,
fcc = 0
を得る. これから Huffman のアルゴ リズムにより平均符号長 L = 12/5,
したがって, 1 文字あたり `(2) = 6/5 ビットの符号ができる. 一方, 2 文
字組の出現確率を p0 = {faa , fab , . . . , fcc } として 2 文字のエントロ
ピを求めれば H(p0 ) ≈ 2.3599. したがって, 1 文字あたりのエントロピ
は (1/2)H(p0 ) ≈ 1.179. この場合も, 1 文字あたりのエントロピは 1 文
字あたりの平均符号長の下界になっている.
1-30 これは情報源の判定ができて各々に最適な符号が使える場合と, 情報源の判定
ができなくて単一の符号しか使えない場合を比較する問題である.
(1) 文字の出現確率は αp + βq = {αpa + βqa , a ∈ A}. 各時刻において, 文
字は互いに独立にこの出現確率で現れるので, V は記憶のない情報源.
210
問題の解答
(2) 出力 Vi を符号化した時の平均符号長の下界は文字の出現確率のエント
ロピ H(Z) で与えられる. したがって, 下界は H(Z) = H(αp + βq).
(3) タイプ (II) の複合情報源を符号化する時には , ど ちらの情報源から文字
が出ているかがわかるので , X に合わせた符号と Y に合わせた符号を用
意して使い分けることができる. 情報源 X と Y とに対する平均符号長
の下界は各々の文字の出現確率のエントロピ H(p) と H(q) とで与えら
れるから , V̂ に対する平均符号長の下界は αH(p) + βH(q) で与えられ
る. エントロピが上に凸であることより (問題 1-20 参照), H(αp + βq)
≥ αH(p) + βH(q). したがって, タイプ (II) の情報源 V̂ の方が小さ
な下界を持つ.
(4) この場合, 時刻 i におけるタイプ (I) 複合情報源の出力が xn = x1 x2
· · · xn ∈ An である確率は
∆
rxn = αPXn (xn ) + βPYn (xn )
で与えられ , 1 文字あたりの平均符号長の下界は
1
1 X
rxn log2 rxn
H(r) = −
n
n n n
x ∈A
で与えられる. 一方, タイプ (II) の場合, 対応する下界は
¤
1 £
αH(XN ) + βH(YN ) = αH(p) + βH(q)
N
となる. 拡大しない場合と同じように考えれば , 後者は前者より大きく
ないことが示せる.
ところで , W を確率 α で 0, β で 1 の値をとる (X, Y とは独立な) 確率
変数とする. そうすると , 上の複合情報源の各時刻における出力文字は
½
Zn =
Xn ,
Yn ,
if W = 0
if W = 1
という確率変数であると考えることができる. タイプ (I) とタイプ (II)
の違いは W を知っているかど うかであり, タイプ (I) の場合の一文字
当たりの平均符号長の下界は (1/N )H(Z n ), タイプ (II) の場合の下界は
(1/n)H(Zn |W ) と表せる. 下界の大小は条件付エントロピの性質 H(Z n )
≥ H(Z n |W ) の結果でもある. さらに , エントロピの性質
H(Zn ) ≤ H(Zn , W ) = H(Zn |W ) + H(W ) ≤ H(Zn |W ) + 1
より, n → ∞ のとき,
(1/n)H(Zn ) → (1/n) [αH(Xn ) + βH(Yn )] .
結局, 両者の下界は極限で一致し , αH(p) + βH(q) になる.
2 章の問題の解答
211
[補足:ユニバーサル情報源符号化]
上の議論では , 情報源を拡大していった極限では , どの情報源が選ばれて
いるかという副次情報は必要のないことが示された. それでは , 実際に 1
文字あたりの平均符号長も一致するだろうか . 答えはイエスである. な
ぜなら , 十分に長い文字列を見れば , それがど ちらの情報源から出たも
のかがわかるのであるから , 調べた結果に応じて符号を使い分ければ良
いのである. この問題のように情報源が二つしかない場合に限らず, 無
数の情報源の候補がある場合でも同様に「一つの符号ですべての情報源
を最適に符号化できるか ?」という問いかけができる. これもある種の
条件の下ではイエスである. このような問題はユニバーサル情報源符号
化とよばれ , 多くの興味深い結果が得られている.
2 章の問題の解答
2-1 磁化の一つの方向を “l” (left) 反対方向を “r”(right) とし , “-” を変化なしと
する. 符号化する前の部分は “r” であったとする. PE では “l”→“r” の変化
で “0” を表し , MFM では図 2.4 (b) の状態 “a” から出発するものとする. た
だし ,“?” は次のビットで決まる.
(a)⇒
(b)⇒
2-2
NRZI
PE
MFM
→
→
→
NRZI
PE
MFM
→
→
→
(r)
- --------l------ lrlrlr-l-rlrlr?
- l-r-l-r--l--r-l -
(r) (l) r
(r)
(r)
- --l---r-l-r---l l-r-lrlrl-r-l?
- l--r--- l-r-l---r
(r) (l) r (r)
(1) 記録データの 1 ビットがディスク上で占める長さは vT (m) である. NRZI
方式では “1” のたびに磁化方向が変わるので, 変化の最小間隔は vT (m).
PE 方式は “0” や “1” が連続すると仮の記録方向変化が入るので vT /2(m).
MFM 方式では 2 倍のビット量に変換してから NRZI で記録するが , 書
き込みデータ中の “1” と “1” との間に少なくとも一つの “0” があるの
で , 結局, 最小変化間隔は vT (m).
(2) 許容ピーク間隔をデ ィスク上の距離にすると vW (mm) である. 上の結
果より, NRZI では vW , PE では 2vW . MFM では , 最小変化間隔が符
号化データの 2 ビットに , そして, 記録データの 1 ビットが符号化デー
タの 2 ビットに対応するので , 結局, vW (mm).
(3) NRZI と MFM では読み取り信号中のピーク間隔を計ってその間のビッ
ト数を求めるので , パルス・ピークの間に位相が π 以上ずれると, 余分
なビットが挿入されたり, あるべきビットが削除されたりする. したがっ
て, ピーク間隔の最大値が局部発信器の要求精度を決める. NRZI では
212
問題の解答
ピーク間隔に上限はないので, α = 0 でないと読み取り誤りがいつかは
起きる. MFM ではピークの間隔は最大 4 ビット分である. 符号化ビッ
トの間隔は上の記録ビット間隔の半分の vW/2(m), 時間に換算すると
W/2(sec) であるから , 4×(W/2)(sec) の間に π ずれなければ良い. し
たがって, |α| < π/(2W )(rad/sec) なら良い. PE では書き込みビット
の位置に必ずピークがあり, 一つのピークが観測されたらそれは書き込
みビットを表すか , あるいはピークの方向を調整するための余分なピー
クであるかのいずれかである. 時計がずれると余分なピークを書き込み
ビットと判定してしまうので , 一つの書き込みビットの時間間隔 2W (sec)
の間に π/2 ずれるとビットの挿入や削除が起きる. したがって, |α| <
π/(4W )(rad/sec) でなければならない. 以上を整理すると
方式
NRZI
PE
MFM
記録ビットの長さ (m)
vW
2vW
vW
位相変化の余裕 (rad/sec)
0
π/4W
π/2W
となる. 読み出しクロックの余裕と記録ビットの密度は共に MFM が優
れていることがわかる. ただし , この結果はセルフ・クロックの方式に
依存し , やり方によっては評価が変わる可能性もある.
2-3 各自確かめよ.
2-4 [d, k]RL 制約, [d, ∞]RL 制約, [0, k]RL 制約の各々の状態遷移グラフは (a),
(b), (c) のようになる.
0
s=1
0
s=0
(b)
(a)
0
1
s=1
s=0
s=d-1
1
s=d-1
s _> d
0
0
0
1
1
s=d
s=k
1
0
s=k-1
1
0
s=1
0
1
s=0
0
s=d+1
0
1
1
(c)
s=k
s=k-1
0
2-5 [1, 1]RL 制約は “0” と “1” の数が常にバランスするので DC フリーになるが ,
情報を載せられない. [α, α, α, α]RL 制約でもバランスするが , 情報は載せら
れない. それ以外では “0” と “1” は必ずしもバランスしない.
2-6 [d, k; d0 , k 0 ]RL 制約は “0” のランもしくは “1” のランがどのくらい続くかを
制約するものであるから , d と d0 は決して 0 ではない. ただし , 85 ページの脚
注で述べたような (dkd0 k 0 ) 制約の定義を用いた場合には d や d0 は 0 になり
得る.
2 章の問題の解答
213
2-7 2.3.1 項のように状態を定めれば , 次のようになる.
0
0
s= 1
s= 1
0
t= 2
s= 2
1
1
s= 2
0
1
1
(a)
2-8
1
0
t= 2
1
t= 1
0
1
t= 3
t= 1
(b)
(1) 表は次のようになる.
n
N (n)
(1/n) log2 N (n)
k
k/n
1
2
1
1
1
2
3
0.792
1
1/2
3
5
0.773
2
2/3
4
7
0.701
2
1/2
5
10
0.664
3
3/5
(1/n) log2 N (n) は単調に減少するが , k/n は単調には変化しない.
(2) 1 ビットしか送らないなら良いが , たくさんのビットを送るならこの議論
は正しくない. 実際, “0” もしくは “1” をそのまま送れば最初の 1 ビッ
トは確かに送れる. しかし , その次にもう 1 ビットを送ろうとした時, 前
に送ったビットによって次のビットが制限される. したがって, 比率 k/n
= 1 は最初の 1 ビットに限っては正しいが , それ以降には正しくない. n
= 2 でも 3 でも同じである. n ビットを一度だけ送るなら良いが , その後
にメッセージを再び送ろうとすると必ず前のビットの制約を受ける. 後
にも先にも一度だけ n ビットを送る問題を one-shot 符号化といい, 実
際の符号化とは区別する必要がある.
(n)
(n)
(n)
2-9 ai から aj へ n 回の遷移で至るパスの数を si,j とおき, si,j = ti,j を帰納法
で示す. n
(1)
ti,j
(1)
(1)
= 1 の場合は ti,j =
と ti,j の定義より si,j = ti,j は明らかな
(l)
(l)
(l+1)
(l+1)
l の場合に si,j = ti,j であると仮定して, si,j = ti,j を示す. さ
ので , n =
て, 長さ l + 1 の ai から aj に至るパスは l 番目に適当な状態 ak に来てから ,
最後に ak から aj に至る形に書ける. したがって,
(l+1)
si,j
=
=
[ai から aj へ l + 1 回の遷移で至るパスの数]
X
[ai から ak へ l 回の遷移で至るパスの数]
k
×[ak から aj へ 1 回の遷移で至るパスの数].
仮定より, この右辺は
P
(n)
t t
k i,k k,j
P
(l)
(n+1)
t t . 一方, 行列の積の演算則より ti,j
k i,k k,j
(l+1)
(l+1)
si,j = ti,j であることがわかる. したがって,
であるから ,
納法によりすべての n について命題が証明された.
2-10 (a) 周期 2. (b) 周期的でない. (c) 周期 3.
=
帰
214
2-11
問題の解答
(1) a を含む閉路の長さは p で割り切れ , b を含む閉路の長さは q で割り切
れる. したがって, a と b を含む閉路の長さは p と q 各々で割り切れる.
(2) p 6= q であると仮定する. この場合, 一般性を失うことなく, q は p を割
り切らないと仮定できる. さて, a から b へ至る任意のパスを Pab , b か
ら a へ至る任意のパスを Pba としよう.
Pab
b
a
P ba
Paa
パス Pab と Pba をつなぐと a と b とを同時に含む閉路 Paba ができる.
この閉路の長さ laba は p と q の最小公倍数 m で割り切れる. 一方, a
の周期は p であり q は p を割り切らないから , a を含む閉路の中にはそ
の長さ laa が q では割り切れないものがある. これを Paa としよう. こ
の閉路 Paa と Paba をつなぐと a と b とを含む新しい閉路 Paaba がで
きるが , この長さ laa + laba は q では割り切れない. これは上の結果に
矛盾するから , p = q でなければならない.
(3) 既約なグラフでは , その中の任意の二つの状態を含む閉路は必ず存在す
る. したがって, 任意の二つの状態の周期は同じになる.
2-12
(1) 図 2.13 と図 2.14 の状態遷移図の各状態を状態変数 d の小さな順に (図
の左から ) 番号をふれば , 各々の遷移行列は
µ
T1 =
0
1
0
1
0
1
0
1
0

0
 10
T2 = 
0
0
¶
,
1
0
1
0
0
0
1
0
1
0
0
0
1
0
1

0
0 
0 
1
0
となる. これから固有多項式を求めると, 各々,
|T1 − λI| = −λ(λ2 − 2),
|T2 − λI| = −λ(λ4 − 4λ2 + 3)
√
√
となるので , 最大固有値は各々λmax = 2 と λmax = 3. したがって,
[1]RS 制約と [2]RS 制約の通信路容量は各々 (1/2) ビットと (1/2) log2 3
ビットとになる.
(2) 図 2.9 の状態を状態変数の小さな順に番号付ければ遷移行列
µ
T =
0
0
1
1
0
0
0
1
1
¶
が得られる. これより固有多項式は |T − λI| = (−λ3 + λ2 + 1). 最大
固有値は λmax ≈ 1.4655. これより通信路容量は C ≈ 0.55.
2 章の問題の解答
215
(3) 図 2.12 の状態を t = 2, t = 1, s = 1, s = 2 の順に番号付ければ遷移行列
à 0 0 1 0 !
T =
1
0
0
0
1
1
1
0
0
0
1
0
が得られる. これより固有多項式は |T − λI| = (λ2 − λ − 1) (λ2 + λ + 1),
√
最大固有値は λmax = (1 + 5)/2. 通信路容量は C ≈ 0.69.
2-13
(1) T` の固有多項式, つまり f` (λ) は
¯
¯ −λ
¯ 1
¯
¯
f` (λ) = |T` − λI| = ¯¯
¯
¯
¯
¯
¯
¯
1
¯
−λ 1
¯
¯.
..
..
..
¯
.
.
.
¯
1 −λ
1 ¯
1
−λ ¯
1
−λ
1
余因子展開によりこの行列式を変形すれば
¯ −λ 1
¯
¯ 1 −λ 1
¯
..
..
..
(−λ) ¯¯
.
.
.
¯
1
−λ
¯
1
¯ ¯ 1
¯ ¯
¯ ¯ 1 −λ 1
¯ ¯
..
..
..
¯−¯
.
.
.
¯ ¯
1 −λ
1 ¯¯ ¯¯
1
−λ
¯
¯
¯
¯
¯
¯
1 ¯¯
−λ
を得る. 第一項目は (−λ)f`−1 (λ) であり, 第二項目はさらに行列式の展
開を行なうことにより −f`−2 (λ) であることがわかる.
(2) λ = −2 cos x を (−λ)f`−1 (λ) − f`−2 (λ) に代入して計算すれば sin[(` +
1)x]/ sin x を得る. これは f` (λ) に等しい. 次に , 0 ≤ x ≤ π の範囲内
で sin[(` + 1)x]/ sin x が 0 になる x は x = πi/(` + 1), i = 1, 2, · · · , `.
f` (λ) は ` 個の根を持つから , これらが求める固有値を与える.
(3) [k] RS 制約の遷移行列は ` = 2k +1 の場合に当たるから , C = log2 λmax
= 1 + log2 cos[π/(2k + 2)].
(4) 行列式
¯
¯ α1 − λ 1
¯ α2
−λ
¯ α
3
¯
¯
..
¯
.
¯
¯
¯ α`−1
¯ α
`
の余因子展開を行なえば
¯
¯ α1 −λ 1
¯ α2 −λ 1
¯
..
.. ..
¯
(−λ) ¯
. .
.
¯
¯ α`−2
−λ 1
¯ α
−λ
`−1 · · ·
1
−λ
1
..
.
..
.
−λ
¯
¯
¯
¯
¯
¯
¯
¯
¯
1 ¯¯
−λ
¯
¯
¯
¯ 1
¯
¯ −λ 1
¯
¯
−λ 1
¯
¯
`−1
¯ + (−1) a` ¯
.. ..
¯
¯
. .
¯
¯
¯
¯
−λ 1
¯
¯
¯
¯
¯
¯
¯
¯
¯
216
問題の解答
となるが , 第二項目は (−1)`−1 a` になる. 以下, これを繰り返せば良い.
詳細は省略する.
(5) [d, k]RL 制約の遷移行列では ` = k で αi = 0, i ≤ d, かつ αi = 1, d <
i ≤ k + 1 となるので ,
f (λ) = λk+1 − λk−d − λk−d−1 − · · · − 1.
一方, [d, ∞]RL 制約の場合は ` = d + 1 で α1 と αd+1 のみが 1, 残りは
すべて 0 となるので ,
f (λ) = λd+1 − λd − 1.
2-14
(1) 長さが r の閉路を c1 , 長さが r + 1 の閉路を c2 とする. c1 を r 回繰り返
すと長さが r2 の閉路ができる. この r 回の中の一つを c2 に換えれば長
さが r2 + 1 の閉路ができる. 二つを c2 に換えれば長さが r2 + 2 の閉路
ができる. 順次繰り返していくと, 長さが r2 から r(r + 1) までの r 個
の閉路ができる. 次に c1 を r + 1 回繰り返した長さ (r + 1)r のものか
ら始めて順に長さが (r + 2)r 迄の閉路が得られ , そして c2 を r + 2 回繰
り返した閉路から始めて順に長さが (r + 2)r から (r + 3)r 迄の閉路が
得られる. このように考えると, r2 以上の任意の長さの閉路が得られる.
(2) 非周期的な状態はその状態を含む閉路でその長さが互いに素であるよう
な組を必ず持つ. ` 個の閉路 ci , i = 1, 2, · · · , `, がそのような閉路の組
で , 各々の長さ qi , i = 1, 2, · · · , `, が互いに素であるとする. ところで ,
互いに素な整数の組に対して
α1 p1 + α2 p2 + · · · + α` p` = 1
が成立するような整数 (必ずしも正ではない) の組 αi , i = 1, 2, · · · , `,
がある. そのなかで , αi∗ = mini αi であるとし , m = −αi∗ としよう.
すべての閉路を m 回ずつ繰り返して得られる閉路を cA とすれば , その
P
長さは m i pi . これに対して, 各々の閉路 ci を m + αi ずつ繰り返し
P
P
(m + αi )pi = m i pi
て得られる閉路を cB とすれば , その長さは
i
+ 1. したがって, cA と cB の長さはちょうど 1 違う.
(3) 補題2-3 の最初の命題は (1) と (2) から証明される. ai から aj へ至る長
さ l のパスがあるなら , ai の閉路を幾つか通った後に aj に行くパスを考
∆
えれば , ni,i + l 以上の任意の長さのパスが得られる. no = maxi,j ni,j
(n)
とすれば , すべての n ≥ no で ti,j > 0 が成立する. したがって, 補題の
後半の二つの命題が証明された.
2-15 単位ベクトル ei は θ 個の固有ベクトル vk とすべてが 0 ではない θ 個の係数
βi,k によって, ei = βi,1 v1 + βi,2 v2 + · · · + βi,θ vθ と表される. この結果,
ti,j = ei T n etj =
θ
X
k=1
t
βi,k λn
k vk ej
2 章の問題の解答
217
すでに固有ベクトルは固有値の絶対値が大きな順に並んでいるものとすれば ,
λmax = λ1 , かつ v1 À 0. このとき, v1 À 0 より βj,1 > 0 かつ v1 etj > 0 で
あり, さらに , 定理 2-2 より, λmax = λ1 > |λ2 | ≥ · · · であるから , n が十分に
(n)
n
t
大きければ , ti,j =
∼ αi,j λ1 . ただし , αi,j = βi,1 v1 ej とした.
2-16 符号語を構成する際には , 符号語をつなげた時に制約が破られないように考え
なければならない. 簡単なのは同一の状態で始まり終る文字列を符号語とす
ることである. ここでは状態 a1 をそのような状態として考える. 状態 a1 から
出発した時の [0, 1]RL 制約の状態遷移を表す木は次のようになる.
a2
a2
1
0
a1
a1
1
a1
a2
0
a1
1
1
a1
1
a1
a1
a2
0
1
0
1
a1
1
a1
1
a1
a2
0
0
1
a1
1
a2
1
a1
1
a1
1
a1
a1
一番簡単な符号語の選び方は
メッセージ
0
1
→
→
符号語
01
1
である. メッセージ中の “0” に “1” が出現確率 1/2 で独立に現れるとすれば ,
この時のメッセージ長 k = 1 ビットに対する平均符号長 n̄ は
n̄ =
1
1
3
×2+ ×1=
2
2
2
ビット .
したがって, 符号化レートは k/n̄ ≈ 0.666. [0, 1]RL 制約の通信路容量が C ≈
0.694 であるから , この可変長・可変レート符号によって通信路容量の 96%の
符号化レートが達成できた.
一方, 等長符号化を行なうために符号語となり得る文字列ととして, 長さ 3 の
ものと長さ 6 のものを選んで ,
メッセージ
0000
0001
0010
0011
→
→
→
→
符号語
010101
010111
110101
110111
メッセージ
10
01
11
→
→
→
符号語
011
101
111
とする. これらの符号語は状態遷移木の中で終端ノードになっているから復号
可能で , メッセージ長と符号語長の比が 2 : 3 で一定であるから , 符号化レー
ト 2/3 ≈ 0.666 の固定レート符号を得たことになる.
218
問題の解答
等長符号を求めるにも上と同じように発見的に符号語を見つけても良いが , 遷
移行列 T の巾乗を計算して組織的に行なってみる.
T5 =
³
8
5
5
3
´
(5)
より, t1,1 = 8 であるから , 符号化レート 3/5 = 0.60 の符号が構成できるこ
とがわかる. 例えば ,
メッセージ
000
001
010
011
→
→
→
→
符号語
01011
01101
01111
10101
メッセージ
100
101
110
111
→
→
→
→
符号語
10111
11011
11101
11111
が求める等長符号の一例になる.
なお, 上の巾乗の計算からも明らかなように , [0, 1]RL では a1 から a1 に至る
パスの数が 1 番多い. 実は , これが状態 a1 を符号構成の基本に選んだ理由.
(n)
2-17 blog2 t3,3 c が 0.51n, 0.52n 以上になる最小の n を求めれば良い. 遷移行列 T
(n)
(n)
の巾乗を計算するのだが , 実際には , T n の (3, 3) 要素 t3,3 が差分方程式 t3,3
(n−1)
t3,3
(n−3)
t3,3
=
+
を満たすことから , 求めていけば良い. その結果, n = 18
でこの値が 0.51n, n = 23 でこの値が 0.52n を初めて越える. なお, 上の差分
方程式の特性方程式 1 = x−1 + x−3 は T の固有方程式に一致することに注意
せよ. グラフが規約で非周期的なら両者の最大根は等しい.
2-18 初期状態から始まって可能性のある状態を追っていくと, “0” を上, “1” を下
とすれば , (a) は
00
→
&
C
D
10
01
&
%
B
A
00
→
&
C
D
00
%
→
C
01
→
A
D
00
→
&
C
D
00
%
→
C
D
となる. 最後の文字が “1”(下側) であるから , 求めるメッセージは “01010011”.
同様にして, (b) で求めるメッセージは “01110101” である.
2-19 yt の論理表は以下の通り. これを論理回路にうつせば良い.
y1t の論理表
s1,t s2,t xt = 0 xt = 1
00
0
0
0
0
01
11
0
0
10
0
1
y2t の論理表
s1,t s2,t xt = 0 xt = 1
00
0
0
1
0
01
11
0
0
10
1
0
2-20 時刻 t の状態 “a”, “b” を各々st = 0, 1 と表し , その時の符号器入力を xt , 符
∆
号器出力を y = y1t y2t と書くことにする. 論理表は次のようになる.
st
0
1
st+1 の論理表
xt = 0 xt = 1
0
1
0
1
st
0
1
y1t の論理表
xt = 0 xt = 1
1
0
0
0
st
0
1
y2t の論理表
xt = 0 xt = 1
0
1
0
1
2 章の問題の解答
219
これをもとに論理回路を書けば以下の通り.
xt
符号器入力
符号器状態
st
a=0
b=1
s t +1
y 1 ,t
次の状態の決定
y 2 ,t
符号器出力
2-21 “1” の個数から “0” の個数を引いた値を d, 連続する “0” の個数を s として,
(d, s) を状態変数とする. 状態の遷移は次の通りである. ただし , 遷移先の内,
“0” で遷移する方を先に示してある.
(dt , st )
(−2, 0)
(−2, 1)
(−2, 2)
(−1, 0)
(−1, 1)
(−1, 2)
(0, 0)
(0, 1)
⇒
⇒
⇒
⇒
⇒
⇒
⇒
⇒
⇒
(dt+1 , st+1 )
(−1, 0)
(−1, 0)
(−1, 0)
(−2, 1), (0, 0)
(−2, 2), (0, 0)
(0, 0)
(−1, 1), (1, 0)
(−1, 2), (1, 0)
(dt , st )
(0, 2)
(1, 0)
(1, 1)
(1, 2)
(2, 0)
(2, 1)
(2, 2)
⇒
⇒
⇒
⇒
⇒
⇒
⇒
⇒
(dt+1 , st+1 )
(1, 0)
(0, 1), (2, 0)
(0, 2), (2, 0)
(2, 0)
(1, 1)
(1, 2)
無し
これから状態遷移図を書くと次のようになる.
(-1,1)
(-2,1)
(1,1)
(-1,2)
(0,1)
(-2,2)
(2,1)
(0,2)
(2,0)
(0,0)
(-2,0)
(1,2)
(2,2)
(1,0)
(-1,0)
既約なグラフにするためには , 破線の枝と状態を除く.
2-22
(1) 発光できる状態を a1 , 発光まで 2 秒, および 1 秒の準備が必要な状態を
各々a2 , a3 とする. システム A の状態遷移グラフは次のようになる.
無光
発光
a
a2
無光
1
無光
a3
220
問題の解答
(2) 遷移行列は
µ
1
0
1
1
0
0
0
1
0
¶
である. λmax を対応する固有多項式 f (λ) = −λ3 + λ2 + 1 の最大根と
すれば通信路容量は C = log2 λmax . これ以上は解析的に求まらないが ,
状態遷移グラフは図2.9 (b) と同じになるので , 通信路容量も同じ .
(3) システム B の通信路容量 0.5bit/sec より C が大きいかど うかを知るに
√
は , 2 より λmax が大きいかを調べる. 固有多項式 f (λ) の増減表
λ
f (λ)
増減
0
1
&
2/3
23/27
%
&
√
√
と f ( 2) > 0 より, λmax > 2 である. したがって, システム A の方
が高速な通信が可能である.
2-23
(1) これは「 ”00”の後は ”1” 」, 「 ”1”の後は ”2” 」, 「 ”2”の後は ”0” 」とい
う制約である. “0” が一つ, あるいは連続して二つ現れた直後の状態を
各々“s10 ”, “s20 ” と表し , “1” の直後の状態を “s1 ”, “2” の直後の状態を
“s2 ” と表すことにすれば , 状態遷移規則は
前の状態
後の状態
s10
s20
s20 ,
s1
s2
s10
→
→
→
→
s1
s2
s1
となる. これより, 制約のグラフは以下のようになる.
0
s 10
s 20
1
s2
0
1
s1
2
このように禁止文字組リストを用いた制約を遷移グラフによって表すこ
とができる. このように , 遷移グラフ17 でも, 禁止文字組リストでも同
じ制約を表すことができる.
(2) 状態 s10 , s20 , s1 , s2 の順に番号をつければ , 遷移行列は
à 0 1 1 0 !
T =
17
遷移グラフは許された文字組を表す.
0
0
1
0
0
0
1
0
0
0
1
0
,
2 章の問題の解答
221
固有多項式は λ4 − λ − 1 となる. したがって, C = log2 λmax ≈ 0.287.
(9)
(9)
(3) T 9 を計算すれば , t1,4 + t2,4 = 3 + 2 = 5. したがって, そのような文
字列の総数は 5. ちなみにそのようなパスは以下の通り.
s10 →s1 →s2 →s10 →s1 →s2 →s10 →s20 →s1 →s2
s10 →s1 →s2 →s10 →s20 →s1 →s2 →s10 →s1 →s2
s10 →s20 →s1 →s2 →s10 →s1 →s2 →s10 →s1 →s2
s20 →s1 →s2 →s10 →s1 →s2 →s10 →s20 →s1 →s2
s20 →s1 →s2 →s10 →s20 →s1 →s2 →s10 →s1 →s2
(4) “000” の禁止がなくなるとグラフは [2, ∞]RL 制約と同じ形になる.
2-24
(1) dt の値を状態とすれば制約のグラフは次のようになる.
1
1
d =-1
1
d =0
d =1
0
d =2
0
0
(2) dt の値の小さな方から状態を番号付ければ遷移行列は
à 0 1 0
T =
1
0
0
0
1
0
1
0
1
0 !
0
.
1
0
この固有多項式は f (λ) = λ4 − 3λ2 + 1, そして最大固有値は λmax =
√
(1 + 5)/2. したがって, この制約の通信路容量は C ≈ 0.694 ビット .
(3) 遷移行列の 4 乗
à 2 0 3 0 !
4
T =
0
3
0
5
0
3
0
5
0
3
0
2
より, 文字列の総数は 26. このうち, −1 → −1, −1 → 1, 0 → 0, 0 →
2 の遷移を書き出すと次のようになる. 2 → 2, 2 → 0, 1 → 1, 1 → −1
の遷移では文字列の”0”と ”1”を反転させたものになる.
最初の d
−1
最終の d
−1
−1
1
0
0
文字列
1010
1100
1110
1101
1011
0101
0110
最初の d
0
最終の d
0
0
2
文字列
1001
1010
1100
0111
1011
1101
(4) 状態 “0” から状態 “0” に至る文字列が五つあるので , これから符号化
レート 2/4 = 1/2 の等長符号ができる. メッセージと符号語の対応は適
当に決めれば良い. 省略する.
222
2-25
問題の解答
(1) [2, 7]RL 制約である. “0” の最長のランは “d → a → f → g → d” の遷
移で出現する. 一方, 最短のランは “g → c → b” で出現する.
(2) 変換規則は次のようになる.
s1,t s2,t s3,t
000
001
010
011
100
101
110
xt = 0
s1,t+1 s2,t+1 s3,t+1
011
010
001
001
010
011
011
y1,t y2,t
00
00
01
10
00
00
00
xt = 1
s1,t+1 s2,t+1 s3,t+1
101
100
000
000
010
110
010
y1,t y2,t
00
00
01
10
10
00
10
(3) 変数 s1,t+1 に関するカルノー図表はつぎのようになる.
xt s1,t
00
01
11
10
s2,t s3,t
01 11
0
0
0
1
1
0
00
0
0
0
1
10
0
0
0
0
この中で , “-” は値がど ちらでも構わないことを表す. ∨ で OR, ∧ で
AND を表すことにすれば , この表から
s1,t+1 = (xt ∧x2,t ∧s3,t ) ∨ (xt ∧s1,t ∧s2,t ).
同様にして,
s2,t+1
=
(xt ∧s1,t ∧s2,t ) ∨ s1,t
s3,t+1
=
(s1,t ∧s2,t ∧s3,t ) ∨ (xt ∧s1,t ∧s3,t ) ∨ (xt ∧s2,t )
y1,t
=
(s2,t ∧s3,t ) ∨ (xt ∧s1,t ∧s3,t )
y2,t
=
s1,t ∧s2,t ∧s3,t .
3 章の問題の解答
3-1 任意の文字 a, b, c に対して δ(a, b) ≤ δ(a, c) + δ(c, b) が成立する. 実際, a =
b なら , δ(a, b) = 0 ≤ δ(a, c) + δ(c, b) であり, a 6= b なら c = a と c = b が
同時に成立することはないから , δ(a, b) = 1 ≤ δ(a, c) + δ(c, b) である. した
がって, 任意に与えられた三つの文字列 a = a1 a2 . . .an , b = b1 b2 . . .bn , c =
c1 c2 . . .cn に対して
dH (a, c) + dH (c, b) − dH (a, b) =
n
X
i=1
{δ(ai , ci ) + δ(ci , bi ) − δ(ai , bi )} ≥ 0.
3 章の問題の解答
223
3-2 2 進文字列 a に含まれている “1” の数を wa , もう一つの 2 進文字列 b 含まれ
ている “1” の数を wb とする. さらに , a と b を比較して, ai = 1 で bi = 0
である座標 i の数を α, ai = 0 で bi = 1 である座標の j の数を β とする. こ
のとき, dH (a, b) = α + β かつ wa − wb = α − β が成立するから , dH (a, b)
= wa − wb + 2β. したがって, a と b が共に偶パリティ(奇パリティ) なら
dH (a, b) は偶数. つまり, パリティ・ビット方式でも二重パリティ・ビット方
式でも最小距離は偶数であることがわかる.
パリティ・ビット方式では Hamming 距離が 2 の符号語の例が作れるので , 最
小距離は 2. 二重パリティ・ビット方式では Hamming 距離が 4 の符号語が作
れるので , 最小距離は 2 もしくは 4 である. しかし , 3.2 節で見たように , 符号
語の中のどの 2 ビットをいじっても誤りとして検出されるので, 符号語の間の
Hamming 距離は 2 ではなく 4.
3-3
(a) この受信語を行列の形に並べると
1
1
1
1
0
0
1
0
1
0
1
1
1
1(←)
1
0
1
0
0
1
ここで , (4, 3) のビット (図中の矢印) を直すと符号語になる. この符号
語と受信語の Hamming 距離は 1 であるから , この符号語がもっとも近
い符号語である. したがって, 復号したメッセージは “111101011110”.
(b) 受信語との Hamming 距離が 1 もしくは 2 の符号語はなく, 3 のものが
二つ以上見つかるので , 復号できない.
3-4 Hamming 距離に関する三角不等式より,
dH (x, x0 ) ≤ dH (x, y) + dH (y, x0 ).
ここで dmin ≤ dH (x, x0 ), dH (x, y) = t であることを用いれば ,
dH (y, x0 ) ≥ dH (x, x0 ) − dH (x, y) ≥ dmin − t.
したがって, 定理 3-1 の条件の下では dH (y, x0 ) > 0.
3-5 to ≤ tmax であるから , t ≤ to なら最小距離復号によって正し く復号できる
のは明らか . t ≤ dmin − to − 1 なら他のどんな符号語 x̂ を持ってきても, 受
信語 y との Hamming 距離 dH (y, x̂) が to より大きくなることを示す. 実際,
Hamming 距離に関する三角不等式より
dH (y, x̂) ≥ dH (x, x̂) − dH (x, y) ≥ dmin − (dmin − to − 1) = to + 1.
3-6 限界距離復号法は , to 個以上の誤りが起きたときには訂正を行なわないので,
最小距離復号ではない. なお, 限界距離復号では Hamming 距離 to 以内にあ
る符号語のみを探せば良いので, 1 番近い符号語を探さなければならない最小
224
問題の解答
距離復号に較べて復号の手間はずっと小さい. このため, 誤り検出が目的では
ない場合でも, 復号器のコストを下げるために限界距離復号を考えることも
ある.
3-7 問題 3-3 と同じように受信語を行列の形に書くと考えやすい.
(a) e = 0 または e = 1 として 1 番近い符号語を考える.
e=0
e=1
→
→
x = 11110000001011101001
x = 11110010101110101001
dH (y, x) = 3
dH (y, x) = 2
このうち, 後の方が受信語にもっとも近い. したがって, 復号されるメッ
セージは “111101011110”.
(b) 同様して, “11110010101000100101” が Hamming 距離 3 で受信語に
もっとも近い. 復号されるメッセージは “111101011000”.
3-8 受信語と符号語の Hamming 距離の計算では消失ビットをすべて 1 と数える
ので , 消失していないビット位置だけに着目して最小距離復号すれば良い. 符
号長が n で s 個の消失ビットが ij , j = 1, 2, . . . , s にあるとする. さらに ,
受信語 y からこれらの座標を除いて得られる長さ n − s の文字列を y0 , 符号
C の各符号語 x からこれらの座標を除いて得られる長さ n − s の新しい符号
語 x0 からなる符号 C0 とする. 消失があるときの最小距離復号は文字列 y0
を受信語として符号 C0 の中から 1 番近い符号語を選ぶ最小距離復号になる.
このときの誤り訂正限界は C0 の最小距離 d0 min で定まる. C の最小距離を
dmin とすれば d0 min ≥ dmin − s である. したがって, ビット誤りの個数 t が
b(dmin − s − 1)/2c を越えないなら最小距離復号は成功する.
[注意] 多くの符号では d0 min = dmin − s だが , 中には d0 min > dmin − s で
ある符号もある. この場合, s 個の消失位置の重要性が薄かったと考えられる.
∆
例えば , パリティ・ビット方式の符号語 x の先頭に “0” をつけた文字列 x0 =
0x を符号語とする符号では 1 ビット目の重要性が著しく薄い. 実際, 誤り訂
正や検出ではこのビットは何の役目も果たさないビットである. 逆にいえば ,
良く作られた符号では d0 min = dmin − s である場合が多い.
3-9 Mod 2 の加算の性質より, a 6= b ⇔ a⊕b 6= 0. したがって, 定義式 (3.2 ) か
ら , δ(a, b) = δ(a⊕b, 0). これより, 任意の 2 進文字列 a と b に対して,
dH (a, b) =
n
X
δ(ai , bi ) =
i=0
n
X
δ(ai ⊕bi , 0) = dH (a⊕b, 0)
i=0
を得る. したがって,
min
x,y∈C, x6=y
3-10
dH (x, y) =
min
x,y∈C, x⊕y6=0
dH (x⊕y, 0) =
min
x∈C, x6=0
dH (x, 0).
(1) 生成行列は 2×5 であるから , メッセージ長 2, 符号長 5, 符号化レート
2/5 の符号ができる. 符号とメッセージ対応表は以下の通り.
3 章の問題の解答
225
メッセージ
00
01
10
11
0
0
1
1
符号語
0000
1011
0101
1110
(2) 繰り返し符号は 1 ビットを繰り返すものであるから , 符号化レート 1/7
の繰り返し符号の生成行列 G は 1×7 行列
G=
3-11
¡
1
1
1
1
1
1
1
¢
.
(1) この符号は組織符号であるから , 式 (3.18 ) に従って,

1
 11
H=
 1
1
1

1
1
1
1

.

1
1
(2) これも同様にして,
µ
H=
0
1
1
1
0
1
1
1
0
1
0
0
0
1
0
0
0
1
¶
.
(3) 生成行列より, 符号生成の式
½
x1
x2
x3
=
=
=
( x
4
u1
u1 ⊕ u2
u2 ⊕ u3
=
=
=
=
x5
x6
x7
u 1 ⊕ u3 ⊕ u4
u 2 ⊕ u4
u3
u4
を得る. これをもとにして符号語よりメッセージを求める式を書く.
( u
1
=
=
=
=
u2
u3
u4
x1
x1 ⊕ x2
x6
x7
これを先の符号生成の式に代入すれば次の三つの独立な式を得る.
(
x1 ⊕ x2 ⊕ x3 ⊕ x6
x1 ⊕ x4 ⊕ x6 ⊕ x7
x1 ⊕ x2 ⊕ x5 ⊕ x7
=
=
=
0
0
0
これより, 検査行列は
µ
1
1
1
1
0
1
1
0
0
0
1
0
0
0
1
1
1
0
0
1
1
¶
.
226
問題の解答
3-12 GF(4) 上の演算表3.6 を対応関係 (3.21 ) に従って 2 進ベクトルど うしの演算
として見ると, 加算はベクトルの mod 2 の加算になっていることがわかる. こ
れに対して, i ∈ GF(4) をかける積は次の行列をかけることで表される.
∆
M0 =
³
0 0
0 0
´
∆
³
, M1 =
1 0
0 1
´
∆
, M2 =
³
1 1
1 0
´
∆
³
, M3 =
0 1
1 1
´
.
実際, 乗算の結果は 2·2 → (10)M2 = (11) → 3. したがって, 式 (3.22 ) の生
成行列の各要素を対応する Mi で置き換えれば良く, 生成行列 (3.23 ) を得る.
一般に , GF(pm ) 上の加算と乗算を素体 GF(p) 上の m 次元ベクトルの上で考
えると , 加算はベクトルの加算, GF(pm ) 上の要素 a をかける演算は対応する
m×m 行列 Ma を GF(p) 上の意味でかける演算として表すことができる.
3-13 問題 3-11 (3) の答より, 検査行列は
µ
1
1
1
1
0
1
1
0
0
0
1
0
0
0
1
1
1
0
0
1
1
¶
.
この検査行列の各列はすべて異なっているので, どの二つをたし合わせても 0
にならない. 一方, 三つの列の組でたし合わせると 0 になるものは容易に見
つけられるから , 定理 3-8 より, 最小距離は 3 である. 実は , これは 3.10 節の
Hamming 符号の一種である.
3-14 符号化レ ート 1/r の繰り返し 符号は “0” および “1” を r 回繰り返すので ,
k = 1, n = r, dmin = r である. したがって, n − k + 1 = r = dmin .
3-15 式 (3.20 ) の検査行列を一般化すれば次の (k0 +k1 +1) × (k0 +1)(k1 +1) 検査
行列となる.











1tk0 +1

1tk0 +1
..
.
..
.
1tk0 +1
Ik0 +1
Ik0 +1
···
···
Ik0 +1
Ik0 +1










ここで , 例えば , h1 ⊕ h2 ⊕ hk0 +2 ⊕ hk0 +3 = 0 であるから , dmin ≤ 4. どの
二つの列ベクトルを足しても 0 にならないのは明らか . また, hi は第 k1 ∼n
行要素に 1 を一つだけ持つから , どの三つの列ベクトルを足しても決して 0 に
ならない. したがって, dmin = 4. なお, k = k0 ×k1 と n = (k0 + 1) × (k1 + 1)
より, n − k + 1 − dmin = k0 + k1 − 2.
3-16 符号 C の各符号語 x = x1 x2 . . .xn の座標を置換 ( i1 i2 .. .. .. in ) で並べ換え
1 2
n
た符号語 x̂ = xi1 xi2 . . .xin は新しい符号 Ĉ を作る. このとき C と Ĉ は互い
に同値であるという. すべてのパリティ検査符号は組織符号に同値であること
3 章の問題の解答
227
が知られており, 組織符号で Singleton 限界が成立すればすべてのパリティ検
査符号でも成立する. もっと直接的に証明するなら , 長さ n − k のベクトルが
n − k 個あれば , その中から一つ以上のベクトルを選んで和が 0 になるように
できることをいえば良い.
3-17 2 次の Hamming 符号の検査行列は , 例えば ,
µ
H=
1
0
0
1
1
1
¶
と書ける. これからパリティ検査方程式を書くと x1 ⊕ x3 = 0, x2 ⊕ x3 = 0.
したがって, x1 = x2 = x3 となるから , 符号化レート 1/3 の繰り返し符号で
ある. この結論は検査行列の列ベクトルの並べ方に依存しない.
3-18 符号長 n, メッセージ長 k については作り方から明らか . dmin = 3 を示すに
は , 2 個以下の列ベクトルの和は 0 にならず , 3 個の列ベクトルで和が 0 にな
るものがあることを言えば良い. これも次のようにほぼ明らかである. 列ベク
トルはすべて異なるのであるから 2 個の和は 0 でない. また, 0 以外のすべて
の 2 進ベクトルがあるのであるから , 任意の hi と hj の和 hi ⊕hj も (0 でな
いから ) ある列ベクトル hk に一致する. したがって, hi ⊕hj ⊕hk = 0 となる
列ベクトルがある.
3-19 m 次の Hamming 符号に対して n = 2m − 1, k = 2m − m − 1 である.
(1) Hamming 符号の最小距離が 3 であるから , 一つの受信語が同時に二つ
以上の符号語から Hamming 距離 1 以内にあることはない. 一つの符号
語から Hamming 距離 1 以内の受信語の数は符号語自身を含めて n + 1
個であるから , 2k = 2n /2m であることを用いれば総数は (n + 1)2k =
2n .
(2) 長さ n の受信語の総数は 2n であるから , すべての受信語がどれか一つ
の符号語から Hamming 距離 1 以内にある. さらに , 上で述べたように ,
二つの符号語から同時に Hamming 距離 1 以内にあることはない.
(3) 以上の結果より, 一つの符号語から Hamming 距離で 2 以上離れると,
他の符号語で Hamming 距離 1 以内のものが必ずあるので , 復号誤りが
起きる.
Pt
一般に , 長さ n の文字列で Hamming 重み t 以内のものは
( n ) 個ある.
i=0 i
(パリティ検査) 符号が t 個のビット誤りを訂正できるとすれば , 一つの符号
語から Hamming 距離 t 以内にある文字列は他の符号語から Hamming 距離
t + 1 以上離れていなければならない. したがって,
2k ≤ Pt
2n
i=0
( ni )
が成立する. これを Hamming 限界という. この式から定理3-13 (1) が得ら
れる. なお, Hamming 限界が等号になる符号を完全符号という. 繰り返し符
号も完全符号である. ただし , 完全符号は多くはない.
228
問題の解答
3-20 問題3-2 より, 同じパリティを満たす符号語の間の Hamming 距離は必ず偶数
になる. 拡大 Hamming 符号は偶パリティを満たすように拡大されているので,
符号語間の Hamming 距離は偶数で , その最小距離も偶数である. ビットを付け
加えることにより最小距離が小さくなることはないので, 拡大 Hamming 符号
の最小距離は Hamming 距離の最小距離 3 以上の偶数. したがって, Hamming
重み 4 の符号語があることをいえば 最小距離が 4 であることになる. 実際,
Hamming 符号の中の Hamming 重みが 3 の符号語 x に “1” を付け加えた x1
は拡大 Hamming 符号の符号語になるから , 重み 4 の符号語がある.
3-21
(a) s = xH t = 0. したがって, 復号したメッセージは u4 = 1001.
(b) s = 101. 同じシンド ロームを持つ最小の誤りパターンは e = 1000000.
推定された符号語は x = e⊕y = 0001011. したがって, 復号したメッ
セージは u4 = 0001.
(c) s = 100. 最小の誤りパターンは e = 0000100. 復号されたメッセージ
は 0111.
3-22
(1) 符号長 n, メッセージ長 k の符号に対する検査行列は (n − k)×n の大き
さになるから , 符号長は 8, メッセージ長は 4. したがって, 符号語数は
2k = 16.
(2) 生成行列は
à 10001011 !
G=
0 1 0 0 1 1 1 0
0 0 1 0 0 1 1 1
0 0 0 1 1 1 0 1
(3) 符号語を書き出してみると
メッセージ
0000
0001
0010
0011
0100
0101
0110
0111
符号語
00000000
00011101
00100111
00111010
01001110
01010011
01101001
01110100
メッセージ
1000
1001
1010
1011
1100
1101
1110
1111
符号語
10001011
10010110
10101100
10110001
11000101
11011000
11100010
11111111
最小距離は dmin = 4 であるから , 3 個のビット誤りを検出し , 1 個のビッ
ト誤りを訂正できる.
(4) 結果は次の通り. ただし , Hamming 距離が最も小さい符号語が複数あ
る場合は二つまであげる.
3 章の問題の解答
3-23
229
受信語
00100111
01010000
誤り
なし
あり
11000001
0e001010
111eee11
111eee01
あり
あり
あり
あり
一番近い符号語
00100111
00000000
01010011
11000101
01001110
11111111
01101001
10110001
距離 (消失)
0
2
2
1
2(1)
3(3)
4(3)
4(3)
復号結果
0010
復号不可
1100
0100
1111
復号不可
(1) 符号語をすべて書き出すと次の通り.
メッセージ
0000
0001
0010
0011
0100
0101
0110
0111
符号語
00000000
00101110
01010110
01111000
10011010
10110100
11001100
11100010
メッセージ
1000
1001
1010
1011
1100
1101
1110
1111
符号語
11111111
11010001
10101001
10000111
01100101
01001011
00110011
00011101
(a) 24 個の長さ 8 の符号語があるから , 符号化レートは r = 1/2.
(b) 最小距離は dmin = 4. この結果より, この符号は 3 誤り検出符号
であり, 1 誤り訂正符号でもある.
¡
¢
(2) メッセージ u = u1 u2 u3 u4 に対する符号語は x = u1 ·18 ⊕ (u2 u3 u4 )G̃, 0
¡
¢
と書ける. ただし , (u2 u3 u4 )G̃, 0 は始めの 7 個の要素が (u2 u3 u4 )G̃,
最後の要素が 0 である長さ 8 の行ベクトルを表す. この符号語に対して,
xH t
¡
¢
=
u1 · 18 H t ⊕ (u2 u3 u4 )G̃, 0 H t
=
u1 · 17 H̃ t ⊕ at ⊕ (u2 u3 u4 )G̃H̃ t
¡
¢
となる. ここで , H̃ が G̃ に対する検査行列であることから , (u2 u3 u4 )G̃H̃ t
= 04 . したがって, xH t = 04 であるためには a = 17 H̃ t であれば良い.
これより, 検査行列は
à 11010001 !
H=
3-24
1 0 1 0 1 0 0 1
0 1 1 0 0 1 0 1
1 1 1 0 0 0 1 0
.
(1) 符号長は 3×3×3 = 27. したがって, 符号化レートは 8/27
(2) 条件から決まる検査方程式は , 各々,
½
ステップ (b)
⇒
x1 ⊕x2 ⊕x3 =0
x4 ⊕x5 ⊕x6 =0
½
x10 ⊕x11 ⊕x12 =0
,
x13 ⊕x14 ⊕x15 =0
230
問題の解答
½
ステップ (c)
⇒
(
ステップ (d)
⇒
xi ⊕x3+i ⊕x6+i =0
x9+i ⊕x12+i ⊕x15+i =0
i = 1, 2, 3,
xi ⊕x9+i ⊕x18+i =0
x3+i ⊕x12+i ⊕x21+i =0
x6+i ⊕x15+i ⊕x24+i =0
i = 1, 2, 3.
したがって, 検査行列 H は次に示すようになる.
 111
111
111


111
 1
1
1
 1
1
1

1
1
1

1
1
1

1
1
1

H=
1
1
1
 1
1
1
 1
1
1

1
1
1

1
1
1

1
1
1

1
1
1

1
1
1
1
1
1
1

















1
1
次に , 符号語の文字とメッセージの文字との間の関係
u1
m
x1
u2
m
x2
u3
m
x4
u4
m
x5
u5
m
x10
u6
m
x11
u7
m
x13
u8
m
x14
を検査方程式に代入して, 各々の xi を ui の和として表せば
x1
x2
x3
..
.
=
=
=
u1
u2
u1 ⊕u2
..
.
これより, 次の生成行列を得る.



G=


1 1
11
1 1
11
1 11 1
11 11
∆
1 1
11
1 1
11
1 11 1
11 11
1 1
1 11 1
1 1
11
11 11
11
1 11 1
1 11 1
11 11
11 11






∆
(3) 上の生成行列から , x(1) = (x1 x2 . . .x9 ) と x(2) = (x10 x11 . . .x18 ) と
∆
∆
は各々が メッセージ u(1) = (u1 u2 u3 u4 ) と u(2) = (u5 u6 u7 u8 ) とに
対する二重パリティ・ビット方式による符号語になっていることがわか
∆
る. さらに , x(3) = (x19 x20 . . .x27 ) は u(1) と u(2) 各々の符号語の和に
なっている. 二重パリティ・ビット方式の最小距離が 4 であることはわ
かっている. さて, 次の二つの場合を考る.
4 章の問題の解答
231
¡
¢
(a) u(1) 6= 0 で u(2) = 0 である場合, 符号語の形は x(1) , 09 , x(1) . こ
こで 0` は 0 からなる長さ ` の行ベクトル . x(1) の最小重みが 4 で
あるから , この形をした符号語の最小重みは 8. u(1) = 0 で u(2) 6=
0 である場合, も同様に最小重み 8 が得られる.
¡
¢
(b) u(1) 6= 0 で u(2) 6= 0 である場合, 符号語の形は x(1) , x(2) , x(3) .
x(1) と x(2) の最小重みは共に 4 だから , この形をした符号語の最
小重みは少なくとも 8 である.
したがって, 三重パリティ・ビット方式にもとづく符号の最小距離は少
なくとも 8. 一方, 重みが 8 の符号語があるから , 最小距離は 8.
4 章の問題の解答
4-1 (この問題を解くにはガウス分布に関する知識が必要である.) 積分値に含まれ
ている雑音成分を W , 送られた文字は “1” で , −a(V) の電圧がかけられてい
るものとすると, 判定器入力は y = −aT + W と表される. どの文字が送ら
れたとしても結果は同じなので, これで議論を進めていく.
(a) 硬判定を用いる場合, ビット誤りは W > aT であるときに起きる. W
は分散 σ 2 , 平均値 0 のガウス分布に従う確率変数であるから , W/σ は
分散 1, 平均値 0 のガウス分布に従う確率変数になる. したがって,
n
Pr{W > aT } = Pr
W
aT
>
σ
σ
o
³
=Q
aT
σ
´
を得る. 通信路はビット誤り確率が Q(aT /σ) の BSC になる.
(b) 三値軟判定を用いる場合, 通信路は図4.4 に示した, ビット誤りのある (点
線の遷移のある) 消失通信路になる. ビット誤り確率は上と同様にして
³
Pr{W > aT + v} = Q
aT + v
σ
´
.
消失確率は
Pr{aT − v < W < aT + v}
=
=
Pr{aT − v < W } − Pr{aT + v ≤ W }
³
´
³
´
aT − v
aT + v
Q
−Q
.
σ
σ
4-2 文字 “0” が送られたとする. cos 成分の判定を誤ると結果は “1” になり, sin
成分の判定を誤ると結果は “3” になる. これらの誤りが起きる確率は p であ
る. 両成分の判定を同時に誤ると結果は “2” になるが , 両者が同時に起きる確
率は p2 であり, これは 0 と考える. 他の文字についても同様に考えれば , 次の
DMC を得る.
232
問題の解答
入力
0
0
1
1
2
2
3
3
出力
1-2 p
p
4-3 ε < 1 のときには , 任意の y に対して 1 > Q(y|1) > 0 であることに注意. 受
信語 y に “1” が一つでもあれば , Q(y|0) = 0. したがって, Q(y|1) > Q(y|0).
一方, Q(0|0) = 1 であるから , Q(0|0) > Q(0|1). これから , 復号法 Z が最尤
復号であることがわかる.
4-4
(a) “0” は必ず誤りなしに受けとられる. Q(0|x) は x = 0 のときに最大と
なるので , 受信語は誤りなしに復号される. したがって, Pe (0) = 0.
(b) “0” は決して “1” にならないので , 受信語は次の確率で現れる.
受信語
1100010
確率
(1 − ε)3
1100000
1000010
0100010
ε(1 − ε)2
0000010
0100000
1000000
ε2 (1 − ε)
0000000
ε3
次に , 各々の受信語に対して可能性のある符号語の尤度を調べる. 例え
ば , “1100000” の場合,
符号語
尤度
1100010
ε(1 − ε)2
1110100
ε2 (1 − ε)2
1101001
ε2 (1 − ε)2
1111111
ε5 (1 − ε)2
となるので , 正しく復号される. 同様に , “1000010”, “0100010” も正し
く復号される. 逆に , “0000010”, “0100000”, “1000000” では他にも同
じ尤度の符号語があり, 正しく復号されない. “0” は常に “0” と復号さ
れ , 正しく復号されない. したがって, Pe (1100010) = 3ε2 (1 − ε) + ε3 .
(c) 同様に考えると, Pe (1110100) = 6ε2 (1 − ε)2 + 4ε3 (1 − ε) + ε4 .
4-5
(a) 例えば符号語 “000” が送られ , 受信語 “003” が得られたとする. この確
率は p(1 − 2p)2 であるが , 符号語 “013” が送られても同じ確率で同じ受
信語が得られるので , “003” は復号できない. 受信語 “033” が得られた
とすると , 最尤復号では符号語 “133” が選ばれるので , やはり正しく復
号できない. 同様にして, 一文字でも通信路で誤ると正しく復号できな
いことが分かり, Pe = 1 − (1 − 2p)3 .
(b) 例えば , 符号語 “000” が送られたとする. 簡単のために “x” を “1” も
しくは “3” の文字とする. この時, 通信路で一文字誤って受信語 “00x”
が得られた時には常に正しく “000” と復号される. 二文字誤る場合, 受
信語 “0x1” は符号語 “021” に誤って復号されるが受信語 “0x3” は正し
4 章の問題の解答
233
く復号され . 受信語 “x0x” は符号語 “202” からの受信語と区別できず ,
受信語 “xx0” は正しく “000” と復号される. 三文字誤った “xxx” の形
の受信語は少なくとも符号語 “202” と区別がつかないので復号できな
い. 他の符号語でも同様である. したがって, Pe = 1 − (1 − 2p)3 −
6p(1 − 2p)2 − 6p2 (1 − 2p) = 6p2 − 4p3 .
4-6 定理 4-1 の証明中で , 式 (4.8 ) は次のようになる.
Pe = 1 −
X
X
P (x)Q(y|x)
x∈C y; ψ(y)=x
これより, 定理の証明と同様に考えると, 各 y ごとに P (x)Q(y|x) を最大にす
る符号語を選べば Pe を最小にできることがわかる.
なお, P (x)Q(y|x) は x が送られて, かつ y が受けとられる確率であるから ,
上の復号法は y が受けとられたときの x の条件付確率 (あるいは事後確率)
P (x)Q(y|x)
x∈C P (x)Q(y|x)
∆
P (x|y) = P
を最大にする復号と同じになる. これが本来の最尤復号であり, 上の条件付確
率が本来の尤度である. P (x) = 1/M のとき, これは本文中の最尤復号に一
致する. しかし , すべての符号語が符号が等確率で使われる場合がほとんどな
ので , Q(y|x) を最大にする復号も最尤復号とよぶ. このような習慣から , 通信
路符号化では Q(y|x) を尤度とよび慣わす.
4-7 ε = 0, 1/2 については直接計算すれば明らか . ε → 1 については 2−h2 (ε)/(1−ε)
≤ 1 − ε を最初に示す.
4-8 テスト入力確率 p = {p0 , p1 } に対して
H(Y )
=
−{p0 (1−ε1 −ε2 ) + p1 ε2 } log2 {p0 (1−ε1 −ε2 ) + p1 ε2 }
−{p1 (1−ε1 −ε2 ) + p0 ε2 } log2 {p1 (1−ε1 −ε2 ) + p0 ε2 }
−ε1 log2 ε1
H(Y |X)
=
−(1−ε1 −ε2 ) log2 (1−ε1 −ε2 ) − ε1 log2 ε1 − ε2 log2 ε2 .
BSC の場合と同様にして, Y のエントロピは p = peq のときに最大になるこ
とを確かめる. このとき,
n
C = (1 − ε1 ) 1 + h2
³
ε2
1 − ε1
´o
.
ビット誤りがないとき (ε2 = 0) には BEC の通信路容量 C = (1 − ε1 ) に一
致し , 消失がないとき (ε1 = 0) には C = 1 + h2 (ε2 ) になる.
4-9 テスト入力 X に対する通信路出力を Y とすれば , I(X; Y ) = H(Y ) − h2 (ε).
A = {0, 1, 2} だから , H(Y ) ≤ log2 3. X が等確率, つまり PX = {1/3, 1/3,
1/3} のときに , Y も等確率になり, 最大値 H(Y ) = log2 3 が得られる. した
がって, C = log2 3 − h2 (ε).
234
問題の解答
4-10 出力アルファベット B = {0, 2} ∪ {1} と分割すれば , これが対称通信路であ
ることがわかるので , 等確率で A の文字をとるテスト入力 X で通信路容量が
達成できる. このとき, 計算すれば
C = −0.9 log2
0.9
+ 0.8 log2 0.8 + 0.1 log2 0.1 ≈ 0.447.
2
P
4-11 全対称通信路では , − b P (b|a) log2 P (b|a) は a ∈ A に無関係に一定値とな
る. この値を α とおく. そうすると, 任意のテスト入力 X に対して, I(X; Y )
= H(Y ) − α となる. したがって, 通信路容量は通信路出力のエントロピ H(Y )
を最大にする X で達成する. ところで , X が等確率なら , 全対称通信路では
Y も等確率になり, そのときに H(Y ) は最大値 log2 |B| を取る.
4-12 全対称通信路の場合と同じように , 任意のテスト入力 X に対して相互情報量
は I(X; Y ) = H(Y ) − α という形で書ける. 後は , H(Y ) は X が等確率のと
きに最大になることを示せば良い. さて, B1 , B2 , . . . , BL が対称通信路の定
義に述べられている B の分割であるとし , Y ∈ B` である時に W = ` という
値を持つ新しい確率変数 W を考える. 明らかに , Y は {1, 2, . . . , L} に値を
持つ.
X
X
∆
PW (`) = Pr{W = `} =
PX (a)
P (b|a)
a∈A
b∈Bj
であるが , {P (b|a), b∈B` } はすべての a∈A について互いに置換の関係にあ
P
P (b|a) は a に依らない. したがって, PW は PX に依らない.
るから ,
b∈B`
ところで , 問題 1-19 より, H(Y ) = H(W ) + H(Y |W ) と書ける. W の確率が
X の確率によらないから , H(Y ) を最大にするには H(Y |W ) を最大にする X
を求めれば良い. エントロピの性質より,
H(Y |W )
=
X


PW (`)
`
≤
X
−

X


PY |X (b|`) log2 PY |X (b|`)

b∈B`
PW (`) log2 |B` |
`
であり, 最大値は
PY |W (b|`) =
PY (b)
1
=
,
PW (`)
|B` |
for all b ∈ B` ,
が各々の ` で成り立つと言う条件の下で達成される. この条件は PX (a) =
1/|A| とすれば成立するので , X が等確率のときに通信路容量が達成される.
235
索引
+ (有限体上の和) 148
⊕
(排他的論理和) 139, 142
·
(有限体上の積) 139, 148
0n
(要素が 0 のベクトル ) 141
1`
(要素が 1 の行ベクトル ) 92
=
(漸近的等号) 99
∼
<
(漸近的不等号) 162
∼
∆
=
(定義) 7
An
(巾集合) 41
C
(通信路容量) 89, 193
C (符号) 3, 88, 129
dH (a, b) (Hamming 距離) 131
dmin
(最小距離) 132
δmin
(相対最小距離) 162
ei
(単位ベクトル ) 101
∈ (包含関係) 6
∅
(空集合) 49
GF(q) (ガロア体) 149
h2 (δ) (二元エントロピ関数) 162,
195
H(p)
(出現確率のエントロピ )
22
H(X)
(確率変数のエントロピ )
44
H(Y |X)
(確率変数の条件付エ
ントロピ ) 45
H(X) (情報源のエントロピ ) 41
Ik
(k×k 単位行列) 144
I(X; Y ) (相互情報量) 194
I(p, Q) (相互情報量) 51, 193
lim inf
(下極限) 162
lim sup (上極限) 162
mod
(mod 演算) 139, 148
max (最大値) 15
min (最小値) 15
Pe
(復号誤り確率) 184
PX (x) (X = x の確率) 44
PY |X (y|x)
(Y = y の条件付確
率) 45
Q
(通信路確率行列) 197
Q(b|a) (通信路遷移確率) 177
Q(x) (ガウス積分関数) 178
R
(実数空間) 50
Rn
(ユークリッド 空間) 50
rank (ランク) 143
tr (トレース) 119
H t , vt
(行列/ベクトルの転置)
92, 145
wH (a) (Hamming 重み) 142
χ[α] (α の特性関数) 62
( nk ) (組合せの数) 182
{xa , a ∈ A}
(集合) 14
{xa , a ∈ A : · · ·}
(集合) 64
|·|
(サイズ ) 7
d·e
(切り上げ ) 37
b·c
(切捨て) 18
3PM(→ 符号)
4 相位相変調 179
ACK(⇒ アクノリッジ )
AD 変換器 68
α 線によるソフト誤り (→ 誤り)
ARQ(⇒ 自動再送要求)
Bain, A. 170
BEC(⇒ 通信路, 二元消失—)
236
Bell, A.G. 170
bit(⇒ ビット )
Boole 代数 43
bps 30
BSC(⇒ 通信路, 二元対称—)
Carson, J.R. 170
Caselli, G. 2, 170
CD(⇒ デ ィスク, コンパクト —)
CIRS 符号 (→ 符号)
DC フリー (→ 制約)
DMC(⇒ 通信路, 離散無記憶—)
DMS(⇒ 情報源, 離散無記憶—)
DPCM(⇒ 量子化, 差分—)
Dudley, H. 170
EFM(→ 符号)
Euclid アルゴ リズム 122
FAX 2, 29
FD(⇒ デ ィスク, フロッピー—)
Feller, W. 115, 199
Gallager, R.G. iii
Galois 体 (⇒ 有限体)
GCR(→ 符号)
Gilbert-Varshamov 限界 (→ 限界)
Hamming, R.W. 157, 170
Hamming
—重み 142, 151, 158, 182, 227
—距離 131, 133, 138, 155, 186,
223, 224, 227, 228
—限界 162, 227
Hartley, R.V.L. 170
HD(⇒ デ ィスク, ハード —)
Henry, J. 170
Hertz, H.R. 170
Huffman のアルゴ リズム 28
ID 受信器 178
IEEE 172
Immink, K.A.S. 114
索引
ISI(⇒ 符号間干渉)
ISIT 172
Jordan 標準形 120
Kelvin, T.W. 170
Kraft の不等式 14, 18, 20, 201,
203
Küpfmüller, K. 170
Lagrange
—関数 21, 24
—方程式 24
—の方法 (→—の未定乗数法)
—の未定乗数法 21, 24
Marconi, G 170
Mbit 30
MFM(→ 符号)
MMR 符号 (→ 符号)
MNRZI(⇒ 符号,GCR—)
MO(→ デ ィスク, 光磁気—)
mod2 の演算 139, 152, 225
modq の演算 148
Modified Huffman(⇒ 符号,MH—
)
Modified MR(⇒ 符号,MMR—)
Modified Read(⇒ 符号,MR—)
Morse 符号 (→ 符号)
Morse, S.F.B. 170
MT(⇒ 磁気テープ )
NAK(⇒ ネガティブ・アクノリッ
ジ)
NRZI 74, 76–79, 83, 116, 211, 212
Nyquist, H 170
Oersted, H.C. 170
Pantelegraph 2
PE(→ 符号)
Perron-Frobenius の定理 98
Q 関数 (→ ガウス積分関数)
237
索引
q を法とする演算 (⇒mod q の演
算)
QPSK(⇒4 相位相変調)
Reeves, A.H. 170
RLL 列 (⇒ ラン・レングス制限列)
Run(⇒ ラン )
Shannon, C.E. 43, 170, 172, 199
Singleton 限界 (→ 限界)
Strowger, A.B. 170
Varshamov-Gilbert 限界 (→ 限界)
von Neumann, J. 43, 170
Wiener, N. 170, 199
アクノリッジ 124
誤り
—検出 36, 124–126, 129, 130,
132, 137, 138, 144, 168,
223
—指数 194
—訂正 122, 125, 129, 130, 132,
135, 156, 160, 162
—伝播 35
—パターン 122, 158, 159, 228
一方向— 175
ソフト — 164, 175
訂正—(⇒ 復号—)
ビット — 35, 36, 123, 124, 126,
127, 129, 132–138, 155, 167,
173–176, 181–183, 188, 189,
224, 231, 233
ビット —確率 (→ 確率)
ビット —率 123
復号— 135, 155, 181, 183, 185,
186, 188, 191, 227
有本の方法 198
アルファベット 6
出力— 176
情報源— 6
入力— 176
イーサネット 76
位数 149
一意復号可能 (⇒ 復号可能)
一次従属 143
一次独立 143
インターリーブ 165, 177
枝 10
エントロピ 22
確率変数の— 44, 46
出現確率の— 22, 23, 25, 38,
62, 210
45, 46, 49, 58, 61,
194, 195, 205, 207, 210,
233, 234
情報源の— 41, 42, 44, 58, 61,
62, 71
二元—関数 162, 195, 203
分割の— 49
マルコフ情報源の— 58, 60
n 文字の— 41, 58, 61, 71
条件付—
書き込みデータ 74
拡大
情報源の— 38–40, 52, 71
体の— 149, 150
符号の— 156
拡大体 150, 151, 161
確率
条件付— 45, 46, 48, 51, 53,
174, 175, 177, 186, 190,
233
通信路の遷移— 177, 197
定常— 56, 57, 60, 71, 105, 207,
208
テスト入力— 195, 233
ビット誤り— 174, 188, 195,
231
復号誤り— 182–189, 191
マルコフ情報源の初期— 54–
56, 60, 61, 71, 105, 208
マルコフ情報源の遷移— 54,
55, 57, 59, 105
238
文字の出現—
7, 22, 23, 25,
28, 36, 40, 50, 51, 54–56,
59, 62, 208
Gilbert 通信路の遷移— 180
確率事象 40
確率変数 40, 44
カルノー図表 114, 117, 222
関数
凹— 50
距離—(→ 距離)
凸— 50
二元エントロピ —(→ エントロ
ピ)
レート歪み—(→ レート歪み)
Lagrange—(⇒Lagrange)
完全 12
—な木 12
—な符号 16, 20, 201, 202
—符号 227
ガウス積分関数 178
木 8, 11
q 進— 12
3 進— 20
距離 131
最小— 132, 133, 135, 138, 141,
142, 151–154, 156, 158, 160–
162, 166, 169, 188, 189,
192, 223, 224, 226, 228–
231
相対最小— 162
記録方式 76, 78, 113, 114
記録密度 75
禁止文字組リスト 115, 220
行列
検査— 144–146, 151–153, 155,
158, 167–169, 225, 226, 228,
229
生成— 141–147, 150, 153, 154,
167–169, 224, 225, 228, 230
正値— 98
正定値— 98
遷移— 91–95, 98, 100, 101,
索引
103, 104, 106, 110
通信路確率— 197, 198
マルコフ情報源の遷移確率—
105
グラフ 10
既約な — 96–100, 103–105, 115,
214, 218, 219
—の分解 102, 103, 115
周期的な — 97, 103, 115
状態遷移— 54, 81, 82, 86–88,
90, 92, 94, 103, 105, 212,
219, 220
非周期的な — 97–99, 103–105,
218
無向— 11
有向— 11
誘導された遷移— 103, 104
検査ビット 145
限界
—距離復号法 (→ 復号)
レート歪み—(→ レート歪み)
Gilbert-Varshamov— 162
Hamming—(→Hamming)
Singleton— 152, 226
原始多項式 149
コード ・ブック (⇒ 変換表)
固有
—多項式 119
—値 90, 93, 95, 98, 119
—ベクトル 93, 95, 98, 105,
119
—方程式 119, 218
最大—値 98–100, 102–105, 214,
215, 221
コンパクトディスク (→ ディスク)
誤訂正 (⇒ 誤り, 復号—)
最大固有値 (→ 固有)
サフィックス (条件) 符号 (→ 符号)
差分量子化 (→ 量子化)
三角不等式 131, 133, 223
サンプリング 66–68
239
索引
—周期 66
—周波数 66
—定理 66
サンプル値 66
三重パリティ・ビット方式 (→ パ
リティ・ビット方式)
雑音 123
熱— 178
周期 96, 97, 102–104, 213
グラフの— 97, 103
—的 96
状態の— 96, 97, 214
非—的 96
周波数帯域幅 66
消失 136, 176, 224
—バイト 167
—ビット 136–138, 179, 224
ビット — 136–138, 174, 176
信号
離散時間— 66, 67, 69
連続— 66–68
連続時間— 66, 67
シンド ローム 122, 145, 153, 158–
160, 228
—復号 (→ 復号)
磁気
—ディスク装置 (→ ディスク)
—ヘッド 73
—テープ 113
自動再送要求 36, 123
受信語 130, 173
上極限 162
状態 80
固執的—(⇒ 再帰的—)
再帰的— 96
初期— 80–82, 87, 92, 94–96,
107, 218
—クラス 103, 104
—遷移行列 (→ 行列)
—遷移グラフ (→ グラフ)
—変数 80–82, 86, 87, 214, 219
推移的—(⇒ 非再帰的—)
非再帰的— 96
状態分割法 112, 115
情報源 6
拡大— 39–41, 72, 204
記憶のない— 52, 62, 64, 71,
209
—出力文字 6
—のエントロピ (→ エントロ
ピ)
—符号化 (→ 符号化)
—符号化定理 (→ 符号化定理)
—モデル 51–54
定常— 41, 61, 208
定常マルコフ— 61
波形— 67
マルコフ— 41, 54, 56–58, 71,
105, 207
離散無記憶— 52
連続— 67
垂直モード 34, 35
水平モード 34, 35
スペース 85
制約
積和— 87
対称な — 84
通信路— 78, 79, 83, 88–90, 94,
95, 106, 113, 115, 116
非対称な — 85
ラン・レングス— 80
DC フリー— 86
[0, 1]RL— 19, 92, 94, 95, 114,
217
[0, 2]RL— 115
[0, 3]RL— 81, 82
[0, k]RL— 82, 212
[1, 3]RL— 80, 89, 90, 95
[2, 4]RL— 82
[2, 7]RL— 222
[2, ∞]RL— 82, 100, 106, 114
[d, ∞]RL— 82, 212, 216
[d, k] ラン・レングス—(⇒ [d, k]RL—
)
240
索引
79, 82, 83, 86, 87,
99, 101, 116, 212, 216
[0, 3; 1, 2]RL— 88
[1, 2; 1, 2]RL— 86, 100
[1, 2; 1, 3]RL— 88
[1, 2; 2, 2]RL— 88
—モデル 174
二元消失— 176, 197, 233
二元対称— 174, 175, 181, 186,
[d, k; d0 , k 0 ] ラン・レング ス—
(⇒ [d, k; d0 , k 0 ]RL—)
[d, k; d0 , k 0 ]RL— 85, 87, 212
[1]RS— 87, 95, 100, 102, 214
[2]RS— 87, 100, 115, 214
[k] 積和—(⇒ [k]RS—)
[k]RS— 87
セルフ・クロック 75, 76, 78, 212
遷移確率行列 (→ 行列)
線形空間 118
線形写像 118
全対称 (→ 通信路)
素 101, 216
相互情報量 193, 194
相対頻度 62, 71, 123, 209
相変化デ ィスク (→ デ ィスク)
組織的 (→ 符号, 組織—)
185, 186, 193, 194, 197,
231
Gilbert— 181
[d, k]RL—
大数の弱法則 63
多重経路干渉 180
単調性 61
狭義— 61
広義— 61
頂点 10
通信路 3, 88, 126, 193
記憶のある— 180
三元対称— 197
雑音のある— 123, 173, 174,
193
制約のある— 19, 88, 90
全対称— 197, 198, 234
対称— 197, 198, 233, 234
—確率行列 (→ 行列)
—の遷移確率 177
—符号化 (→ 符号化)
—符号化定理 (→ 符号化定理)
188, 189, 195, 231, 233
符号間干渉— 181
離散無記憶— 176, 177, 180,
ISI—(⇒ 符号間干渉—)
Z— 182, 184–187, 190, 195
通信路符号化 (→ 符号化)
通信路容量 106, 193, 195
三元対称通信路の— 197
制約のある通信路の— 89, 90,
95, 99, 100, 102, 221
対称通信路の— 198
二元消失通信路の— 197, 233
二元対称通信路の— 195
離散無記憶通信路の— 193,
197
Z 通信路の— 195, 196
[0, 1]RL 制約の— 92, 94
[2, ∞]RL 制約の— 100
[d, k]RL 制約の— 99
[1, 2; 1, 2]RL 制約の— 100, 215
[1]RS 制約の— 100, 102, 103
[2]RS 制約の— 100, 214
[k]RS 制約の— 101
ツリー (⇒ 木)
テスト入力 195, 233, 234
—確率 195
典型列 64
データ圧縮 6, 8, 18, 30, 31, 33,
36, 37, 42, 65
デ ィスク
コンパクト — 65, 83, 113, 125,
164
磁気— 73, 74, 76, 84, 106, 113
磁気—装置 73
相変化— 84
ハード — 73, 113
241
索引
光—(→ 光デ ィスク)
フロッピー— 73, 78, 89, 113
光磁気— 84
デジタル変調 (⇒ 変換符号)
伝送レート (→ レート )
等分割性 62, 64
特性
—多項式 (⇒ 固有多項式)
—方程式 (行列の)(⇒ 固有方程
式)
—方程式 (差分方程式の) 218
凸 (とつ)
上に — 50
下に — 50
—関数 50
トラック 74
トレリス 12
同値な符号 (→ 符号)
二重パリティ・ビット方式 (→ パ
リティ・ビット方式)
根 (グラフの) 11
ネガティブ・アクノリッジ 124
ノード 8, 10–12, 25, 27–29, 77
アクティブな — 28, 29, 42
親— 11, 12, 27, 28, 201
子— 11, 12, 28, 29
終端— 8, 11–13, 16, 25, 27,
28, 42, 201, 217
中間— 27, 202
葉— 11
リーフ— 11
ルート — 11, 25, 201
ハード ・デ ィスク (→ デ ィスク)
排他的論理和 139
ハフマンのアルゴリズム (→Huffman)
判定 (信号の) 136, 178–180, 231
硬— 178, 180, 231
軟— 178, 231
パケット 36
パスモード 34
パリティ 127
奇— 127
偶— 127
—検査符号 (→ 符号)
—検査方程式 145, 226
—ビット 36, 127–129, 139, 140,
145, 156
127, 129,
130, 132, 134, 136, 137,
139, 141, 145, 223, 224
三重— 168, 231
二重— 128–130, 132, 134, 138,
140, 141, 146, 153, 230
パリティ・ビット方式
光磁気デ ィスク (⇒ デ ィスク)
光デ ィスク 84, 106, 113
消去可能な — 84
追記型の— 84
非周期的 (→ 周期)
歪みレート関数 (⇒ レート歪み)
標準 2 進表現 18–20, 202
標数 (有限体の) 149
標本化 (⇒ サンプリング )
標本値 (⇒ サンプル値)
ビット 3
—誤り (→ 誤り)
—消失 (→ 消失)
—挿入方式 94
—同期 75
ピット 83
フェージング 180
復号 7, 88
限界距離— 135, 136, 188, 189,
223
最小距離— 133, 134, 136, 138,
154, 158, 167, 182–184, 186,
188, 223, 224
最尤— 186, 187, 189, 190, 192,
232, 233
消失がある時の最小距離— 224
シンド ローム— 158
—可能 9, 13–16, 18, 20, 29,
106, 109, 112, 201, 203,
217
242
索引
本来の最尤— 233
MD—(⇒ 最小距離—)
ML—(⇒ 最尤—)
復号誤り確率 (→ 確率)
復号器 7, 111, 130, 173, 188, 192,
223
復号法 Z 185, 187, 232
符号 3, 6, 14, 17, 20, 88, 129, 132,
134, 145, 184, 186, 192,
193, 203, 224, 226
拡大 Hamming— 155, 156, 227
拡大— 156
可変長— 3, 5, 6, 109–112, 114,
217
可変レート — 109, 217
完全な —(→ 完全)
完全— 227
記録—(⇒ 変換符号)
繰り返し — 133, 143, 146, 153,
154, 184, 185, 187, 225–
227
固定長—(⇒ 等長—)
固定レ ート — 109–111, 114,
217
最大距離分離— 152, 153, 166
サフィックス— 202
線形— 147, 148
組織— 144, 145, 152, 160, 168,
225, 226
伝送路—(⇒ 変換符号)
等長— 3, 5, 110–112, 114, 116,
217, 218, 221
同期— 109
同値な — 226
バイ・フェーズ —(⇒PE—)
パリティ検査— 141, 144, 145,
147, 151–153, 158,
161, 226
非同期— 109
160,
復号可能な —(→ 復号可能)
ブロック—(⇒ 等長—)
プレフィックス— 13–16, 20,
21, 23, 25–29, 37, 201,
202, 204
変換— 106, 113, 125
有限状態— 112
可変長— 109
(1,7)— 113
(2,7)— 113
3PM— 113
8/9— 113
BCH— 151, 160–163, 188, 189
CIRS— 165, 166
EFM— 113, 165
GCR— 113
Hamming— 151–156, 158, 160,
163, 170, 182, 183, 187,
189, 226, 227
MFM— 77–79, 83, 89, 112–
114, 211, 212
MH— 31–36
MMR— 36
MR— 31, 33–36
Make up— 204
Manchester—(⇒PE—)
Morse— 85, 170
PE— 76, 78, 79, 113, 211, 212
RM— 163
RS— 122, 151, 160, 163, 166
Reed-Muller—(⇒RM—)
Reed-Solomon—(⇒RS—)
Terminating— 32, 204
U 値— 18
(n,k) 線形— 147
(n, k) パリティ検査— 141, 142,
154
(n, k, d) パリティ検査— 141
t 誤り訂正/s 誤り検出— 136,
154
符号化 7, 88, 129, 173
情報源— 65, 69, 177
通信路— 88, 114, 129, 130,
173, 177, 188, 192, 233
—歪み 69, 70
243
索引
—レート (→ レート )
ユニバーサル情報源—
204,
211
2 次元— 35, 36
one-shot— 213
符号化定理
雑音のある通信路に対する—
173, 193
情報源— 40, 42, 51
制約のある通信路に対する—
90
歪みを許す情報源— 70
符号間干渉 (→ 通信路)
符号器 7, 111, 112, 114, 116, 125,
129, 173, 192
有限状態— 111, 112
符号語 3, 88, 129, 173
符号長 3, 110, 111, 114, 116, 129,
130, 147, 151, 161, 166,
192, 194
符号理論 138, 163
節 10
フラグ方式 19
フレーム 36, 124, 165
フロッピー・ディスク (→ ディスク)
分解 (→ グラフ)
分割 (集合の) 49
プレフィックス符号 (→ 符号)
平均符号長 7–9, 13, 20–23, 25, 27–
29, 36–38, 41, 42, 68, 71,
72, 204, 208–211
最小— 20
閉道 (⇒ 閉路)
閉路 96–98, 101, 214, 216
辺 (グラフの) 10
変化点 33–35
変換表 111
ベクトル空間 50, 118, 119
マーク 85
マルコフ情報源 (→ 情報源)
室賀の方法) 198
メッセージ 129, 173
メッセージ長 130, 161, 166
文字 6
モデム 30, 123
ユークリッド 空間 50
有限状態機械 112
有限体 149, 150
尤度 186, 191, 233
ライン・コード 106, 113
ラン 31, 79
ランク (行列の) 143
ラン長 31
ラン・レングス (⇒ ラン長)
ラン・レングス制限列 84
量子化 68–70, 164
差分— 69
—器 68, 69
—歪み 68
—レート 68
量子通信 175
レート
伝送— 70, 193, 194
符号化— 89, 90, 94, 107, 109,
110,
143,
189,
218,
114,
146,
190,
221,
116, 130, 133,
162, 168, 169,
192, 193, 217,
224–226, 229
107, 109
平均符号化—
量子化—(→ 量子化)
符号化レート 110
レート歪み
—関数 70
—限界 70
ダウンロード

Document