通信符号理論 01

1 通信符号理論 第１回 伊藤彰則

2 通信とは • 送信者（情報源）から何らかの情報を物理的変化として送信 • 途中（通信路）では雑音によって情報が一部変化 • 受信者は情報を受け取って解釈 送信者 通信路(communication channel) （電気、光、音、化学物質、etc） 雑音 受信者 Shannon’s Noisy Channel Model

3 アナログ通信 • 信号𝑆に対して雑音𝑁が混入 • 信号対雑音比 (SNR) 𝑆/𝑁 送信者 受信者 N S 雑音 S/N

4 ディジタル通信 • 送信信号𝑆 = 𝑥1 𝑥2 … 𝑥𝑁 , 𝑥𝑖 ∈ {0,1} • 受信信号𝑅 = 𝑦1 𝑦2 … 𝑦𝑁 • 雑音の影響により、信号がところどころ反転 • ビット誤り率 (BER) 1 𝑁 ∑|𝑥𝑖 − 𝑦𝑖 | 送信者 S 受信者 雑音 BER

5 チャンネル符号化 • ディジタル通信では、さまざまな機能を実現するため、信号を そのまま送信せず、一旦変換（符号化）してから送信する • 受信側ではそれを下の情報に戻す（復号） チャンネル符号化 送信者 符号化 encode 復号 decode 受信者

6 重要なチャンネル符号化 • 暗号 (encryption/cipher) • 通信路の情報を観測しても通信内容がわからないよ うにする • 圧縮 (compression) • 送信する情報のデータ量を低減する • 誤り訂正 (error correction) • 送信した情報に誤りが混入しても元の情報が復元で きるようにする

7 通信でのビット誤りを減らしたい • ディジタル通信でのBERはアナログ通信でのS/Nと関係 • S/Nが高ければBERは小さい 𝜔 • 𝑆 = 𝐴 ‫𝜔𝑑 𝜔 𝑠 𝐻 𝜔׬‬ 𝐿 • 対策 • 送信パワーを増やす（𝐴を大きく） • 送信信号の帯域を増やす（𝜔𝐻 − 𝜔𝐿 を大きく） • 実際には • 送信パワーには上限がある（物理的、法律的） • 送信信号帯域にも上限がある

8 通信でのビット誤りを減らしたい • 送信パワーも帯域も変えられないとしたら？ • 冗長な情報を送り、受信者がそれを利用して情報を復元 •例 • 1ビットの情報を３回繰り返して送る 10 111000 111010 10 送信者 符号化 encode 復号 decode 受信者

9 情報の冗長化と誤り訂正 • 例：同じ情報を３回送る（繰り返し符号） • 受信側では • 同じ情報が３つ来たら、それをそのまま1ビットに • 000→0, 111→1 • ３つの情報に違いがあったら、多数決により決定 • 001→0, 101→1, etc. • 最初の対策（送信パワー、帯域）との関係は？ • 実質的な通信速度は1/3になっている→正味の通信帯域を狭くして、そ れを冗長に広げているのと同じ

10 ここからが本番です

11 通信路のモデル化 • 符号について、数学的な分析が必要 • その符号がどのくらい冗長で、誤りをどのくらい訂正するのか • 実際の通信系で分析をするのは難しい（場合が多すぎる）ので、数学 的に単純なモデルを作って分析を行う • 通信路のモデル • 0,1の系列が入力されたとき、ある確率で0,1が出力される 010010110010… 通信路 モデル 011010100010…

12 通信路のモデル化 • ２元対称通信路 (Binary Symmetric Channel, BSC) • 最も単純な通信路モデル • 無記憶 • あるビットが出力される確率は、その時の入力だけに依存し、それより前の入力 には依存しない • 対称 • 0が入力された時に1が出力される確率 𝑃 1 0 • 1が入力された時に0が出力される確率 𝑃(0|1) 0 入力 1 1−𝑝 𝑝 𝑝 1−𝑝 0 出力 1 同じ 𝑃 01 =𝑃 10 =𝑝

13 ２元対称通信路 • ２元(0, 1)、無記憶、対称 • ビット誤り率 (BER) 𝑝 • 𝑘ビットの系列の中に誤りが１つ以 上含まれる確率 （ブロック誤り率）1 − 1 − 𝑝 𝑘 • 𝑘ビットの中に誤りが𝑛個含まれる 確率 𝑘 𝑛 𝑝 1 − 𝑝 𝑘−𝑛 𝑛 𝑝 = 0.01の場合の8ビットの ブロック誤り確率

14 ハミング距離 (Hamming distance) • 2つの同じ長さの系列が「どのくらい違うのか」を表す • 𝒙 = (𝑥1 , … 𝑥𝑛 ), 𝒚 = (𝑦1 , … , 𝑦𝑛 ) 𝑥𝑖 , 𝑦𝑖 ∈ {0,1} • 𝑑ℎ 𝒙, 𝒚 = ∑𝑖 |𝑥𝑖 − 𝑦𝑖 | • 同じ位置で0/1が違う場所の数 • 𝑑ℎ 0010, 1010 = 1 • ハミング重み 𝑤ℎ 𝒙 = 𝑑ℎ (𝒙, 𝟎) • 系列の中の 1 の個数

15 ふたたび繰り返し符号 繰り返し符号を使うと、どれくらい誤りが減るのか • ビット誤り率𝑝の２元対称通信路を仮定 • 送信されるのは 000 と 111 のどちらか • 受信されるのはあらゆるビット列 000, 001,…, 110, 111 • 送信・受信の確率はどうなるか？

16 ブロック受信確率 000を送信した場合 受信シンボル 確率 000 1−𝑝 3 001 𝑝 1−𝑝 2 010 𝑝 1−𝑝 2 011 𝑝2 (1 − 𝑝) 100 𝑝 1−𝑝 2 111を送信した場合 受信シンボル 確率 000 𝑝3 001 𝑝2 (1 − 𝑝) 010 𝑝2 (1 − 𝑝) 011 𝑝 1−𝑝 2 100 𝑝2 (1 − 𝑝) 101 𝑝2 (1 − 𝑝) 101 𝑝 1−𝑝 2 110 𝑝2 (1 − 𝑝) 110 𝑝 1−𝑝 2 111 𝑝3 111 1−𝑝 3

17 ブロック受信確率 𝑝 < 1 − 𝑝である場合、送信元がどちらの方が確率が大きいか 000を送信した場合 受信シンボル 確率 000 1−𝑝 3 001 𝑝 1−𝑝 2 010 𝑝 1−𝑝 2 011 𝑝2 (1 − 𝑝) 100 𝑝 1−𝑝 2 111を送信した場合 受信シンボル 確率 000 𝑝3 001 𝑝2 (1 − 𝑝) 010 𝑝2 (1 − 𝑝) 011 𝑝 1−𝑝 2 100 𝑝2 (1 − 𝑝) 101 𝑝2 (1 − 𝑝) 101 𝑝 1−𝑝 2 110 𝑝2 (1 − 𝑝) 110 𝑝 1−𝑝 2 111 𝑝3 111 1−𝑝 3

18 復号領域 • 符号 𝒙 ∈ {000,111} • 復号領域はどう決めても良い が、普通は確率が高くなるよ • 受信語 𝒚 ∈ 0,1 3 うに決める（最尤復号） • 符号ごとに集合 𝑅(𝒙) が決まり、 𝒚 ∈ 𝑅(𝒙)ならば𝒚は𝒙に復号さ • 𝑅 000 = 000, 001, 010, 100 れる • 𝑅 111 = {111, 110, 101, 011} • 𝑅 𝒙 : 𝒙の復号領域

19 誤りはどれくらい減るのか • 誤り率＝３ビットの受信語が正し い復号領域に入らない確率 • ２ビット誤り 3𝑝2 (1 − 𝑝) • ３ビット誤り 𝑝3 • 誤り率 3𝑝2 1 − 𝑝 + 𝑝3 = 𝑝2 3 − 2𝑝

20 通信路に関する基礎知識

21 情報のエントロピー • 確率変数 𝑋 のエントロピー（平均情 報量） 𝐻 𝑋 = − ෍ 𝑃(𝑋 = 𝑥) log 𝑃(𝑋 = 𝑥) 𝑥 • 𝑋の分布に偏りがあるほど小さい • ２元の情報源のエントロピー 0を生成する確率を𝑝0 とする 𝐻 𝑋 = −𝑝0 log 𝑝0 − 1 − 𝑝0 log(1 − 𝑝0 )

22 結合エントロピーと相互情報量 • 確率変数 𝑋, 𝑌の相互情報量 𝐼 𝑋; 𝑌 = 𝐻 𝑋 + 𝐻 𝑌 − 𝐻 𝑋, 𝑌 • 𝐻(𝑋, 𝑌)：結合エントロピー • ２元情報源と通信路の場合 𝑝0 • 𝐻 𝑋, 𝑌 = − ∑𝑥,𝑦 𝑃 𝑥, 𝑦 log 𝑃(𝑥, 𝑦) • 誤り確率𝑝の場合 𝑃 0,0 = 𝑝0 1 − 𝑝 , 𝑃 0,1 = 𝑝0 𝑝, 𝑃 1,0 = 1 − 𝑝0 𝑝, 𝑃 1,1 = (1 − 𝑝0 )(1 − 𝑝) 𝑝 𝐻(𝑋, 𝑌)

23 結合エントロピーと相互情報量 • 確率変数 𝑋, 𝑌の相互情報量 𝐼 𝑋; 𝑌 = 𝐻 𝑋 + 𝐻 𝑌 − 𝐻 𝑋, 𝑌 • 𝑋, 𝑌が独立なら𝐼 𝑋; 𝑌 = 0 • 𝑋 = 𝑌なら𝐼 𝑋; 𝑌 = 𝐻 𝑋 = 𝐻(𝑌) • ２元情報源と通信路の場合 𝑝0 • 0の発生確率𝑝0 、ビット誤り確率𝑝 • 𝑝 = 0なら𝑋 = 𝑌 𝑝 𝐼(𝑋; 𝑌)

24 通信路容量 • 相互情報量 𝐼(𝑋; 𝑌) は、送信シン ボル𝑋と受信シンボル𝑌がどれだ け一致するかを表す • 通信路容量 𝐶 = sup 𝐼(𝑋; 𝑌) 𝑃(𝑋) 𝑝0 • 送信シンボルの分布ができるだけ ランダムである場合の相互情報量 • ２元対称通信路の場合 • 赤い線上の値 • 𝐶 = 1 − 𝐻(𝑝) • ビット誤りがない場合に容量最大 (𝐶 = 1)であり、𝑝 = 0.5のとき𝐶 = 0 𝑝 𝐼(𝑋; 𝑌)

25 演習 • 同じビットを5回繰り返す符号を考える • 0 → 00000, 1 → 11111 • ビット誤り率𝑝であり、多数決によって復号するとき、復号が 誤る確率はいくらか。 • ３回繰り返し符号と比べて、どの程度良いか考察せよ。

26 「符号」の数学的扱い • これまで勘でやっていた符号（繰り返し符号）を 数学的に扱えるようにしたい • 準備 ２元符号 • シンボルの集合 X = {0,1} • シンボルがn個並んだ系列（ベクトル）の集合 X𝑛 • X2 = {00, 01, 10, 11} • 符号 𝐶 ⊂ X𝑛 （シンボルのベクトルの部分集合） • 例えば 𝐶 = {00, 11}

27 符号長と符号化率 • 符号化する前の情報＝メッセージ • メッセージ長 𝑘 • 符号 𝒘 ∈ 𝐶 ⊂ X𝑛 • 符号長 𝑛 • 符号化率 𝑅 = log |𝐶| log |X𝑛 | = log2 |𝐶| 𝑛 = 𝑘 𝑛 • 例：３回繰り返し符号 𝐶 = 000, 111 • メッセージは {0, 1} メッセージ長 𝑘 = 1 • 𝑛=3 • 𝑅= log2 2 3 = 1 3

28 最小距離 • 最小距離：符号の中の２つの符号語のハミング距 離の最小値 𝑑= •例 min 𝒗,𝒘∈𝐶,𝒗≠𝒘 𝑑ℎ (𝒗, 𝒘) • 𝐶 = 000, 111 最小距離3 • 𝐶 = 000, 011, 101, 110 最小距離2 • 最小距離が大きいほど訂正能力が高く、符号化率 が悪い

29 符号化、復号 • 符号化 (encoding) とは • メッセージを符号語に対応させる操作 • 符号化器 (encoder)：メッセージから符号語への全単射（一対一対 応） • 復号 (decoding) とは ෝ ∈ 𝐶 を対応させる • 受信語 𝒚 ∈ X𝑛 に対して 𝒙 • 対応させる写像：復号則 • 復号則に基づく復号結果を計算する方法：復号法 • 復号領域に基づく復号則 ෝ = 𝒄𝑖 • 𝒚 ∈ 𝑅(𝒄𝒊 ) かつ 𝒚 ∉ 𝑅 𝒄𝑗 , 𝒄𝑖 ≠ 𝒄𝑗 のとき 𝒙

30 符号化、復号 メッセージ 符号語 受信語 符号語 メッセージ 𝑚 𝑥 𝑦 𝑥ො 𝑚 ෝ 000 0 111 1 000 0 001 000 010 011 100 101 1 111 符号化 110 伝送 111 復号

31 復号則 • 最小距離復号則 • 𝑅 𝒄𝑖 = {𝒚 ∈ X𝑛 | arg min 𝑑ℎ 𝒚, 𝒄 = 𝒄𝑖 } 𝒄 • 符号の要素が多い場合は計算が困難 • 限界距離復号則 𝑛 𝑑−1 • 𝑅 𝒄𝑖 = 𝒚 ∈ X 𝑑ℎ 𝒚, 𝒄𝑖 ≤ 𝑟 , 𝑟 = 2 • どの復号領域にも入らない受信語がありうる

32 例 • メッセージ 𝑀 = {00,01,10,11} • 符号 𝐶 = {00000, 11100, 00111, 11011} １ビットの誤り が訂正可能 • メッセージ長2、符号長5、符号化率 2/5、最小距離3 00000 00111 11100 • 復号領域 紫：距離0 黒：距離1 赤：距離2 限界距離復号法 では赤は復号領 域に入らない 11011 00000 00011 01100 01001 00001 00101 01101 01010 00010 00110 01110 01011 00100 00111 10100 10001 01000 01101 10101 10010 01001 01110 10110 10011 01010 01111 11000 11001 10000 10101 11100 11010 10001 10110 11101 11011 10010 10111 11110 11111