---
title: 通信符号理論 04
tags: 
author: [Akinori Ito](https://docswell.com/user/akinori-ito)
site: [Docswell](https://www.docswell.com/)
thumbnail: https://bcdn.docswell.com/page/3JK96G1RJD.jpg?width=480
description: アダマール符号、リード・マラー符号 シングルトン限界式、ハミング限界式
published: July 02, 26
canonical: https://docswell.com/s/akinori-ito/KY884N-2026-07-02-160914
---
# Page. 1

![Page Image](https://bcdn.docswell.com/page/3JK96G1RJD.jpg)

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


# Page. 2

![Page Image](https://bcdn.docswell.com/page/LE3W6NQGE5.jpg)

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


# Page. 3

![Page Image](https://bcdn.docswell.com/page/8EDKVW9N7G.jpg)

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 に「符号化率が小さく最小距離が大きい」符号を選ぶ


# Page. 4

![Page Image](https://bcdn.docswell.com/page/V7PKV9ZNJ8.jpg)

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


# Page. 5

![Page Image](https://bcdn.docswell.com/page/2JVVZMWYJQ.jpg)

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


# Page. 6

![Page Image](https://bcdn.docswell.com/page/5EGL4GDWJL.jpg)

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


# Page. 7

![Page Image](https://bcdn.docswell.com/page/4JQYGX1Q7P.jpg)

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


# Page. 8

![Page Image](https://bcdn.docswell.com/page/K74W56RYE1.jpg)

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


# Page. 9

![Page Image](https://bcdn.docswell.com/page/LJ1YWVQNEG.jpg)

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


# Page. 10

![Page Image](https://bcdn.docswell.com/page/GJWG6LLM72.jpg)

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


# Page. 11

![Page Image](https://bcdn.docswell.com/page/4EZLYMMM73.jpg)

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 )


# Page. 12

![Page Image](https://bcdn.docswell.com/page/Y76WDNN57V.jpg)

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)


# Page. 13

![Page Image](https://bcdn.docswell.com/page/G75M355G74.jpg)

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


# Page. 14

![Page Image](https://bcdn.docswell.com/page/9J29ZNNDER.jpg)

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)


# Page. 15

![Page Image](https://bcdn.docswell.com/page/DEY4RPPMJM.jpg)

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) の組み合わせ


# Page. 16

![Page Image](https://bcdn.docswell.com/page/VJNYD55378.jpg)

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


# Page. 17

![Page Image](https://bcdn.docswell.com/page/YE9PGYYPJ3.jpg)

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


# Page. 18

![Page Image](https://bcdn.docswell.com/page/GE8DV66XED.jpg)

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


# Page. 19

![Page Image](https://bcdn.docswell.com/page/LELM599N7R.jpg)

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


# Page. 20

![Page Image](https://bcdn.docswell.com/page/4JMY3ZZQJW.jpg)

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


# Page. 21

![Page Image](https://bcdn.docswell.com/page/PJR9Q66K79.jpg)

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


# Page. 22

![Page Image](https://bcdn.docswell.com/page/PEXQ5MM5JX.jpg)

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元符号で最大分離なのは単一パリティ符号と繰り返し符号の
み


# Page. 23

![Page Image](https://bcdn.docswell.com/page/3EK96GGRED.jpg)

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だとハミング限界式を満たさない）


# Page. 24

![Page Image](https://bcdn.docswell.com/page/L73W6NNG75.jpg)

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


# Page. 25

![Page Image](https://bcdn.docswell.com/page/87DKVWWNJG.jpg)

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


# Page. 26

![Page Image](https://bcdn.docswell.com/page/VJPKV99NE8.jpg)

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


# Page. 27

![Page Image](https://bcdn.docswell.com/page/2EVVZMMYEQ.jpg)

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


# Page. 28

![Page Image](https://bcdn.docswell.com/page/57GL4GGWEL.jpg)

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


# Page. 29

![Page Image](https://bcdn.docswell.com/page/4EQYGXXQJP.jpg)

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) と比べるとだいぶ効率がよくない