第十二回レポート課題 1. Huﬀman アルゴリズムで確率分布が Table 1 で与えられる情報源 X を符号化せよ． Table 1: 情報源 X の確率分布 PX (x) x1 0.35 x2 0.3 x3 0.2 x4 0.1 x5 0.04 x6 0.005 x7 0.005 【解答例】 Huﬀman アルゴリズムにより，与えられた確率を値が大きい順に並べ，確率が最も小さい二つに 0 と 1 の符号語を割り当ててから加算する．この作業を最後の確率の和が 1 になるまで繰り返すと，Table 1 の情報源に対して，次のグラフが描ける． 0 x1 0.35 0.35 0.35 0.35 0.35 0.35 x2 0.3 0.3 0.3 0.3 x3 0.2 0.2 0.2 0.2 x4 0.1 0.1 0.1 x5 x6 0.04 0.04 0.005 x7 0.005 0 0 0.35 0.35 End 1 1 0.2 1 0 0.15 0 0 0.01 0.05 1 1 1 Figure 1: Haﬀman アルゴリズムによるグラフ最後に、上の図にある xi から End までのパスで，太い線で示した符号を逆順に書くと次の符号が得られる． 1 E(x1 ) 1 E(x2 ) 01 E(x3 ) 000 E(x4 ) 0010 E(x5 ) 00110 E(x6 ) 001110 E(x7 ) 001111 2. Lempel-Zip アルゴリズムでビット列 (1010110100100111010100001100111010110001) を符号化せよ．【解答例】 Lempel-Zip アルゴリズムは辞書式符号であるが、与えられた系列を一ビットずつ読み込み、新しいフレーズが出ると辞書に登録する．全ての系列を読み込んだ後は、辞書に登録されているフレーズに 1 から始まるインデェックスを付け、各フレーズは最後の一ビット以外の部分を辞書に登録されているインデェックスに置き換えて符号語を生成するが、一ビットからなるフレーズは前にインデェックスとして 0 を付加する．その故に (1, 0, 10, 11, 01, 00, 100, 111, 010, 1000, 011, 001, 110, 101, 10001) を Lempel-Zip アルゴリズムで符号化するとフレーズの辞書としてが生成さ Index 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Phrase 1 0 10 11 01 00 100 111 010 1000 011 001 110 101 10001 Code 01 00 10 11 21 20 30 41 50 70 51 61 40 31 101 2 Binary 00001 00000 00010 00011 00101 00100 00110 01001 01010 01110 01011 01101 01000 00111 10101 れ、送信ビット列は (00001 | {z } 00000 | {z } 00010 | {z } 00011 | {z } 00101 | {z } 00100 | {z } 00110 | {z } 01001 | {z } 01010 | {z } 01110 | {z } 01011 | {z } 01101 | {z } 01000 | {z } 00111 | {z } 10101 | {z }) 1 0 10 11 01 00 100 に符号化される． 3 111 010 1000 011 001 110 101 10001