通信符号理論 04

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

2 長い符号を作る • 用途によっては、符号化率を下げてもよいので誤り耐性を上げ たいことがある • 宇宙機との通信など • 符号長を長くすると誤りに強い符号が作れる • 繰り返し符号の繰り返し長を長くするなど • もう少し符号化率の良い方法が欲しい • 短い符号語を組み合わせて長い符号語を作る • システマティックに符号が作れる • 用途に合わせて、どの程度強力な符号にするかを選べる

3 u|u+v構成法 • ２種類の短い符号から長い符号を作る方法 • (𝑛, 𝑘1 , 𝑑1 )符号𝐶1 と、(𝑛, 𝑘2 , 𝑑2 )符号𝐶2 がある • 𝒖 ∈ 𝐶1 , 𝒗 ∈ 𝐶2 のとき、| をベクトルの連結として、 𝒖|𝒖 + 𝒗 は (2𝑛, 𝑘1 + 𝑘2 , min(2𝑑1 , 𝑑2 )) の符号になる。 𝑘1 𝑘2 𝑘1 +𝑘2 • 符号化率は , → 𝑛 𝑛 2𝑛 • 𝐶1 に「符号化率が大きく最小距離が小さい」符号、 𝐶2 に「符号化率が小さく最小距離が大きい」符号を選ぶ

4 例 • 𝐶1 : (4,3,2)符号（４ビットのパリ ティ符号） • 𝐶1 = 0000, 0011, … , 1111 • 𝐶2 : (4,1,4)符号（４ビットの繰り 返し符号） • 𝐶2 = {0000,1111} • 組み合わせてできる符号 • 符号長 8、メッセージ長4、 最小距離 min 2 × 2, 4 = 4 • 1ビット誤りが訂正でき、 2ビット誤りは検出できる u╲v 0000 1111 0000 00000000 00001111 0011 00110011 00111100 0101 01010101 01011010 0110 01100110 01101001 1001 10011001 10010110 1010 10101010 10100101 1100 11001100 11000011 1111 11111111 11110000

5 最小距離について • 新しい符号の最小距離は min(2𝑑1 , 𝑑2 ) これを示してみよう • その１ • 𝑑1 < 𝑑2 とし、𝒖 ∈ 𝐶1 ∖ {𝟎}, 𝒗 ∈ 𝐶2 ∖ {𝟎}とする。𝑤ℎ 𝒖 ≥ 𝑑1 , 𝑤ℎ 𝒗 ≥ 𝑑2 • 𝒖 + 𝒗 のハミング重みを考えると、ハミング重みが最も小さくなるのは、 𝒖と𝒗で1となるビットができるだけ重なった場合である。このとき、 min 𝑤ℎ 𝒖 + 𝒗 = 𝑑2 − 𝑑1 である。 • 例 𝑤ℎ 01010 = 2, 𝑤ℎ 11011 = 4 𝑤ℎ 01010 + 11011 = 𝑤ℎ 10001 = 2 = 4 − 2

6 最小距離について • その２ • 𝒖 ∈ 𝐶1 ∖ {𝟎}, 𝒗 ∈ 𝐶2 ∖ {𝟎}とする。𝑤ℎ 𝒖 ≥ 𝑑1 , 𝑤ℎ 𝒗 ≥ 𝑑2 • 𝑤ℎ 𝒖 𝒖 ≥ 𝑑1 + 𝑑1 = 2𝑑1 これは 𝒗 = 𝟎 の場合と同じ • 𝑤ℎ 𝟎 𝒗 ≥ 𝑑2 これは 𝒖 = 𝟎 の場合と同じ • 𝑤ℎ 𝒖 𝒖 + 𝒗 ≥ 𝑑1 + (𝑑2 − 𝑑1 ) = 𝑑2 これは𝒖 ≠ 𝟎, 𝑣 ≠ 𝟎 の場合 • したがって最小距離は min(2𝑑1 , 𝑑2 )

7 生成行列と検査行列 • 𝐶1 の生成行列を𝐺1 、𝐶2 の生成行列を𝐺2 とする • 新しい符号は前半が𝐺1 、後半が𝐺1 + 𝐺2 なので 𝐺1 𝐺1 𝐺= 𝑂 𝐺2 • メッセージを𝒎 = (𝒎1 𝒎2 )とすれば、符号語は 𝒎𝐺 = (𝒎1 𝐺1 𝒎1 𝐺1 + 𝒎2 𝐺2 )

8 生成行列と検査行列 • 𝐶1 の検査行列を𝐻1 、𝐶2 の検査行列を𝐻2 とする • 𝐻1 は𝑛 − 𝑘1 行𝑛列、𝐻2 は𝑛 − 𝑘2 行𝑛列 • 生成行列と検査行列の関係より、𝐻1 𝐺1𝑇 = 𝑂, 𝐻2 𝐺2𝑇 = 𝑂 𝐴 𝐵 • 組み合わせた符号の検査行列を 𝐻 = とすると 𝐶 𝐷 𝐴 𝑇 𝐻𝐺 = 𝐶 𝐵 𝐷 𝐺1𝑇 𝐺1𝑇 𝑂 𝐴𝐺1𝑇 + 𝐵𝐺1𝑇 𝑇 = 𝐺2 𝐶𝐺1𝑇 + 𝐷𝐺1𝑇 𝐵𝐺2𝑇 𝑇 =𝑂 𝐷𝐺2

9 生成行列と検査行列 • 𝐵𝐺2𝑇 = 𝑂, 𝐷𝐺2𝑇 = 𝑂より、𝐵 = 𝑂または𝐵 = 𝐻2 （𝐷も同様） • 𝐵 = 𝑂とすれば、𝐴𝐺1𝑇 = 𝑂より𝐴 = 𝑂または𝐴 = 𝐻1 • 検査行列の各行は0ベクトルにならないので、𝐴 = 𝐻1 • 𝐷 = 𝑂とすれば上記と同じになるが、検査行列の各行は一次独 立なので、𝐷 = 𝐻2 • このとき 𝐶 + 𝐻2 𝐺1𝑇 = 𝑂 したがって𝐶 = 𝐻2 𝐻1 𝑂 • したがって𝐻 = （行を入れ替えてもよい） 𝐻2 𝐻2

10 例の場合 1 0 0 1 • 𝐶1 : 4,3,2 𝐺1 = 0 1 0 1 𝐻1 = (1 1 1 1) 0 0 1 1 1 1 0 0 • 𝐶2 : 4,1,4 𝐺2 = 1 1 1 1 𝐻2 = 1 0 1 0 1 0 0 1 1 0 0 1 1 0 𝐺 𝐺1 0 1 0 1 0 1 • 𝐶: 8,4,4 𝐺 = 1 = 𝑂 𝐺2 0 0 1 1 0 0 0 0 0 0 1 1 1 1 1 1 0 0 0 0 𝐻 𝑂 1 1 0 0 1 1 0 0 • 𝐻= 1 = 𝐻2 𝐻2 1 0 1 0 1 0 1 0 1 0 0 1 1 0 0 1 0 0 1 1 1 1 1 1

11 アダマール符号 • u|u+v構成法によって作られる符号の特殊な場合 • 指数mによって特徴づけられる • m=1 のアダマール符号は2ビットの空間全体 {00,01,10,11} • m=t+1のアダマール符号は、 • m=tのアダマール符号を2回繰り返したものと、 m=tのアダマール符号にその反転を連結したものからなる • m=tのアダマール符号を𝐶1 、2𝑚 ビットの繰り返し符号を𝐶2 としたとき、 これらをu|u+v構成法で組み合わせるとm=t+1のアダマール符号が得られる • 特性は(2𝑚 , 𝑚 + 1, 2𝑚−1 )

12 アダマール符号 m=1 m=2 00 0000 00000000 00001111 0000000000000000 0000000011111111 0000111100001111 0000111111110000 01 0101 01010101 01011010 0101010101010101 0101010110101010 0101101001011010 0101101010100101 10 1010 10101010 10100101 1010101010101010 1010101001010101 1010010110100101 1010010101011010 11 1111 11111111 11110000 1111111111111111 1111111100000000 1111000011110000 1111000000001111 0011 00110011 00111100 0011001100110011 0011001111001100 0011110000111100 0011110011000011 0110 01100110 01101001 0110011001100110 0110011010011001 0110100101101001 0110100110010110 1001 10011001 10010110 1001100110011001 1001100101100110 1001011010010110 1001011001101001 1100 11001100 11000011 1100110011001100 1100110000110011 1100001111000011 1100001100111100 (2,2,1) (4,3,2) m=3 (8,4,4) m=4 (16,5,8)

13 リード・マラー符号 • 同じくu|u+v構成法で作られる一連の符号 • 2つの指数𝑟, 𝑚を使って𝑅(𝑟, 𝑚)と表記する • 𝑅(0, 𝑚)は2𝑚 ビットの繰り返し符号 (2𝑚 , 1,2𝑚 ) 𝑚 2𝑚 • 𝑅(𝑚, 𝑚)は2 ビットの全空間 0,1 : (2𝑚 , 2𝑚 , 1) • 𝑅(𝑟 + 1, 𝑚)と𝑅(𝑟, 𝑚)を合成すると𝑅(𝑟 + 1, 𝑚 + 1)

14 リード・マラー符号 2ビット繰り 返し符号 𝑅(0,1) 2ビット全体 𝑅(1,1) 訂正能力が高い 4ビット繰り 返し符号 8ビット繰り 返し符号 16ビット繰 り返し符号 𝑅(0,2) 𝑅(0,3) 𝑅(0,4) 4ビットパリ ティ符号 𝑅(1,2) 8ビットアダ マール符号 𝑅(1,3) 16ビットアダ マール符号 𝑅(1,4) 8ビットパリ ティ符号 𝑅(2,3) 𝑅(2,4) 𝑅(2,5) 8ビット全体 𝑅(3,3) 16ビットパ リティ符号 𝑅(3,4) 𝑅(3,5) 4ビット全体 𝑅(2,2) 全空間 符号化率が高い パリティ符号 繰り返し符号 アダマール符号 𝑅(3,6)

15 リード・マラー符号 • R(2,4): (16,13,4) • 8ビットパリティ符号(8,7,2)と8ビットアダマール符号 (8,4,4)の組み合 わせ • R(2,5): (32,18,8) • R(2,4) (16,13,4) と16ビットアダマール符号 (16,5,8)の組み合わせ • R(3,5): (32,28,4) • 16ビットパリティ符号 (16,15,2) と R(2,4) (16,13,4)の組み合わせ • R(3,6): (64,46,8) • R(3,5) (32,28,4) と R(2,5) (32,18,8) の組み合わせ

リード・マラー符号の 符号化率と最小距離 16

リード・マラー符号の 符号化率とビット当たり誤り耐性 縦軸は 𝑑−1 2 Τ𝑛 17

18 演習 • 3ビット単一パリティ符号(3,2,2) と3ビット繰り返し符号 (3,1,3)を組み合わせて符号を作ってみよう • (n, k, d) を示せ • 全符号語を列挙せよ • 生成行列と検査行列を示せ

19 どこまで良い符号が作れるのか

20 どこまで良い符号が作れるのか • 良い符号とは：(𝑛, 𝑘, 𝑑)の符号について • 符号化率𝑘/𝑛が大きく（余計な情報がない） • 最小距離𝑑が大きい（誤り訂正能力が高い） • 上記2つの条件はトレードオフ（両方良くはできない） • では，どこに限界があるのか？

21 シングルトン限界式 • 符号語長𝑛，メッセージ長𝑘，最小距離𝑑について 𝑑 ≤𝑛−𝑘+1 • 組織符号化の場合， メッセージ（長さk） ←これだけだとd=1 うまくやれば，この分だけ最小距離が伸ばせる メッセージ（長さk） パリティ（長さ𝑛 − 𝑘） 符号長 n

22 最大分離符号 • 符号語長𝑛，メッセージ長𝑘，最小距離𝑑について 𝑑 =𝑛−𝑘+1 の場合，これを最大分離符号と呼ぶ • 例：単一パリティ符号 (4,3,2) は最大分離符号 (2 = 4 − 3 + 1) • 例：ハミング符号 (7,4,3) は最大分離符号ではない （3 < 7 − 4 + 1） • 例：3ビット繰り返し符号 (3,1,3) は最大分離符号 （3 = 3 − 1 + 1） • 2元符号で最大分離なのは単一パリティ符号と繰り返し符号の み

23 ハミング限界式 • もう一つのn, k, d に関する関係式 • どこまでの訂正能力があるかを示す •𝑡= 𝑑−1 2 とするとき， 𝑡 𝑛 ෍ ≤ 2𝑛−𝑘 𝑖 𝑖=0 𝑛−𝑘 • 例：n=8, k=4 のとき，2 = 24 = 16 8 8 8 = 1, = 8, = 28 0 1 2 より，𝑡 ≤ 1 （𝑡 ≥ 2だとハミング限界式を満たさない）

24 ハミング限界式 • もう一つ例 𝑡 𝑛 ෍ ≤ 2𝑛−𝑘 𝑖 𝑖=0 • 例：n=8のとき， 8 8 8 = 1, = 8, = 28 0 1 2 より，𝑡 = 2 （2ビット訂正可能）のためには， 1 + 8 + 28 = 37 ≤ 28−𝑘 したがって64 = 26 ≤ 28−𝑘 なので，𝑘 ≤ 2

25 ハミング限界式の導出 • ハミング球 𝐵𝑟 (𝒄): ベクトル𝒄とのハミング距離が𝑟以下であるベ クトルの集合 𝐵𝑟 𝒄 = {𝒙|𝑑ℎ 𝒄, 𝒙 ≤ 𝑟} • ベクトル𝒄とのハミング距離がちょうど𝑟であるベクトルの集合 を𝑄𝑟 (𝒄)とすると，𝐵𝑟 𝒄 = 𝑄0 𝒄 ∪ ⋯ ∪ 𝑄𝑟 𝒄 𝑄𝑟 𝒄 = {𝒙|𝑑ℎ 𝒄, 𝒙 = 𝑟} 𝑛 • 𝒄の長さを𝑛とすると，|𝑄𝑟 𝒄 | = 𝑟 • nビットのうちr箇所が違うベクトルの集合なので

26 ハミング限界式の導出 • 𝐵𝑟 𝒄 = 𝑄0 𝒄 ∪ ⋯ ∪ 𝑄𝑟 𝒄 で，𝑟 ≠ 𝑟′なら𝑄𝑟 𝒄 ∩ 𝑄𝑟 ′ 𝒄 = ∅ • したがって 𝑡 𝑡 𝑛 𝐵𝑟 𝒄 = ෍ |𝑄𝑖 𝒄 | = ෍ 𝑖 𝑖=0 𝑖=0 • すべての符号語について半径𝑡のハミング球が重なっていない とすると，ハミング球の中のベクトルの全符号語についての総 和はすべてのベクトルの数2𝑛 を超えない．符号語は2𝑘 種類ある ので 𝑡 𝑛 𝑘 2 ෍ ≤ 2𝑛 𝑖 𝑖=0

27 ハミング限界式の導出 𝑡 𝑛 2 ෍ ≤ 2𝑛 𝑖 𝑘 𝑖=0 • 両辺を2𝑘 で割れば 𝑡 𝑛 ෍ ≤ 2𝑛−𝑘 𝑖 𝑖=0

28 限界式からわかること 𝑛 ≤ 2𝑛−𝑘 𝑖 𝑛 𝑡 𝐿 𝑛, 𝑡 = σ𝑖=0 とすると 𝑖 log 2 𝐿 𝑛, 𝑡 ≤ 𝑛 − 𝑘 𝑘 ≤ 𝑛 − log 2 𝐿(𝑛, 𝑡) より、𝑛, 𝑡を決めたときの𝑘の上限がわかる。 例：𝑛 = 128, 𝑡 = 15 （128ビット符号で15ビットエラーを許容） log 2 𝐿 𝑛, 𝑡 = 63.72012 𝑘 ≤ 𝑛 − log 2 𝐿 𝑛, 𝑡 = 64.27988 したがってメッセージ長の上限は64ビット • σ𝑡𝑖=0

29 限界式からわかること • これがシングルトン限界式だと • 𝑡 = 15 = 𝑑−1 2 より𝑑 = 31 • 𝑑 ≤ 𝑛 − 𝑘 + 1より31 ≤ 129 − 𝑘、𝑘 ≤ 98 • ハミング限界式だと𝑘 ≤ 64なのでハミング限界式が厳密である ことがわかる • ちなみにリード・マラー符号では R(3,7) が (128, 64, 16) R(2,7) が (128, 29, 32) なので(128, 64, 31) と比べるとだいぶ効率がよくない