---
title: 通信符号理論 03
tags: 
author: [Akinori Ito](https://docswell.com/user/akinori-ito)
site: [Docswell](https://www.docswell.com/)
thumbnail: https://bcdn.docswell.com/page/LJ3W6QMGJ5.jpg?width=480
description: 単一パリティ符号、ハミング符号、拡大ハミング符号 シンドローム表復号
published: July 02, 26
canonical: https://docswell.com/s/akinori-ito/KE11D6-2026-07-02-160803
---
# Page. 1

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

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


# Page. 2

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

2
線形符号の実例
• いくつかの線形符号の実例を紹介する
• 単一パリティ符号 (n,n-1,2)：1ビットの誤りを検出する
• ハミング符号 (7,4,3)：1ビットの誤りを訂正する
• 拡大ハミング符号 (8,4,4)：1ビットの誤りを訂正し、2ビットの誤りを
検出する


# Page. 3

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

3
単一パリティ符号
• メッセージに1ビットのパリティを付加する
• メッセージ 𝒎 = (𝑚1 , … 𝑚𝑘 )
• パリティ 𝑝 = 𝑚1 + ⋯ + 𝑚𝑘
• 符号語 𝒄 = (𝑚1 , … , 𝑚𝑘 , 𝑝)
• 符号語のパリティは必ず0になる（1が偶数個含まれる）
• 1ビット誤るとパリティが1になるので検出できる
• 検査行列（n=3の例）𝐻 = (1 1 1)
符号語の全ビットを足して０にな
ればよい
1 0 1
• 生成行列（n=3の例）𝐺 =
0 1 1
1ビット目＝メッセージの1ビット目
2ビット目＝メッセージの2ビット目
3ビット目＝1ビット目＋2ビット目


# Page. 4

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

4
単一パリティ符号の例
• 符号𝐶 = {000,011,101,110}
• 最初の2ビットがメッセージ、3ビット目がパリティ
• メッセージ 𝒎 = (1 0)の場合
1 0 1
𝒎𝐺 = 1 0
= 1⋅1+0⋅0 1⋅0+0⋅1 1⋅1+0⋅1
0 1 1
= (1 0 1)
1
• パリティチェック 𝐻𝒙𝑇 = 1 1 1 0 = 1 + 0 + 1 = 0
1


# Page. 5

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

5
ハミング符号 (7,4,3)
1 1 1 0 1 0 0
• 検査行列 𝐻 = 0 1 1 1 0 1 0
1 1 0 1 0 0 1
1
• 生成行列 𝐺 = 0
0
0
0
1
0
0
0
0
1
0
0
0
0
1
1
1
1
0
0
1
1
1
1
1
0
1
すべての列が異な
るところに注目
どうしてこうなる
のかは後ほど説明
します


# Page. 6

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

6
ハミング符号の例
• メッセージ 𝒎 = (1 1 0 1)
• 符号語 𝒙 = 𝒎𝐺 = 1 1 0 1
1
0
0
0
0
1
0
0
0
0
1
0
0
0
0
1
1
1
1
0
0
1
1
1
1
1 = (1 1 0 1 0 0 1)
0
1


# Page. 7

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

7
ハミング符号の例
1 1 1 0 1 0 0
• パリティチェック 𝐻𝒙𝑇 = 0 1 1 1 0 1 0
1 1 0 1 0 0 1
1+1+0+0+0+0+0
0
= 0+1+0+1+0+0+0 = 0
1+1+0+1+0+0+1
0
1
1
0
1
0
0
1


# Page. 8

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

8
ハミング符号のしくみと復号
• ハミング符号の検査行列は、すべての列が異なる値
• 3ビットの値は8種類あるが、そのうち0を除く7種類が1回ずつ現れる
• 𝐻 = (𝒉1 , … , 𝒉7 )
• 誤差ベクトル𝒆について𝑤ℎ 𝒆 = 1と仮定する（1ビット誤り）
• 𝒆 = 𝑒1 , … , 𝑒7 , 𝑒𝑖 = 1とする
• 𝐻𝒚𝑇 = 𝐻𝒆𝑇 = 𝒉1 , … , 𝒉7
𝑒1
⋮ = 𝑒1 𝒉1 + ⋯ + 𝑒7 𝒉7 = 𝒉𝑖
𝑒7
• シンドロームは検査行列のどれかの列と一致し、
そのビットが誤り


# Page. 9

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

9
生成行列と検査行列
• 生成行列𝐺: 𝑘 × 𝑛、検査行列𝐻: 𝑚 × 𝑛
• 行列𝑃: 𝑘 × 𝑚とし、𝐼𝑚 は𝑚 × 𝑚の単位行列とする
• 𝐻 = 𝑃𝑇 𝐼𝑚 , 𝐺 = (𝐼𝑘 𝑃) と表されるとすると
𝐼𝑘
• 𝐻𝒄𝑇 = 𝐻 𝒎𝐺 𝑇 = 𝐻𝐺 𝑇 𝒎𝑇 = 𝑃𝑇 𝐼𝑚
𝒎
𝑇
𝑃 𝑇
𝑇
𝑇
= (𝑃 𝐼𝑘 + 𝐼𝑚 𝑃 )𝒎 = 𝑃 + 𝑃𝑇 𝒎 = 0
1
𝐻= 0
1
1
1
1
𝑃𝑇
1
1
0
0
1
1
1
0
0
0
1
0
0
0
1
単位行列
1
𝐺= 0
0
0
0
1
0
0
0
0
1
0
単位行列
0
0
0
1
1
1
1
0
0
1
1
1
𝑃
1
1
0
1


# Page. 10

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

10
生成行列と検査行列
• 𝐺 = (𝐼𝑘 𝑃)の形式の場合、生成される符号語は
𝒎𝐺 = 𝒎 𝐼𝑘 𝑃 = 𝒎𝐼𝑘 𝒎𝑃 = (𝒎 𝒎𝑃)
• 符号語の前半kビットはメッセージそのもの、後半mビットはパリティ
• これを組織符号化という
• GやHが単位行列を含まない形だったら？
0
• 𝐻= 0
1
0
1
0
0
1
1
1
0
0
1
0
1
1
1
0
1
1
1
これでも性質は同じなので
符号はハミング符号になる


# Page. 11

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

11
生成行列と検査行列
0
• 𝐻= 0
1
0
1
0
0
1
1
1
0
0
1
0
1
1
1
0
𝝓1
1
1 = 𝝓2
𝝓3
1
𝝓1 𝒄𝑇
• 符号𝒄について 𝐻𝒄𝑇 = 𝝓2 𝒄𝑇 = 𝟎より、各行が𝝓1 … 𝝓3 の線形結合になっ
𝝓 3 𝒄𝑇
ている行列𝐻′も同じ符号の検査行列である。
𝝓1 + 𝝓2
• 例 𝐻 ′ = 𝝓2 + 𝝓3
𝝓3 + 𝝓1


# Page. 12

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

12
生成行列と検査行列
• 検査行列を変形することによって右半分を単位行列にできる
• 掃き出し法と類似のアルゴリズム
0
0
1
2行目＋=
3行目
0 0 1
1 1 0
0 1 0
0 1 1
1 0 1
1 1 0
1 1 1
0 1 1
1 0 1
1 1 0
1 0 1
1 0 0
1行目＋=
2行目
0
0
1
0 1
0 1
1 0
左半分を転置
単位行列をつ
なげる
1 1 1
1 0 0
1 0 1
0 0 3行目＋=
1 1
1行目
0 1
1
𝐺= 0
0
0
0
1
0
0
0
0
1
0
0
0
0
1
0
1
1
1
0
0
1
1
0
1
1
1 1 1
1 1 0
1 0 1
1
1
0
1
1 0 0
0 1 1
0 0 1


# Page. 13

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

13
例と演習
1 0 0 0 1 0 1
𝐺= 0 1 0 0 1 1 1
0 0 1 0 1 1 0
0 0 0 1 0 1 1
• 上記のハミング符号で、受信語 𝒚 = 1101011 を復号せよ。
1 1 1 0 1 0 0
•𝐻= 0 1 1 1 0 1 0
1 1 0 1 0 0 1
• シンドロームは 0 1 0 𝑇 。これは検査行列の6ビット目にあたるので、6
ビット目を反転させて、
𝑥ො = 1101001
• メッセージは先頭4ビットなので 1101
• 演習：𝒚 = 1101010 を復号せよ。


# Page. 14

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

14
一般ハミング符号
• (7,4,3)以外のハミング符号も同じ考え方で作れる
• 長さ𝑚 ≥ 3のベクトル𝒗1 , … , 𝒗𝑛 ここで𝑛 = 2𝑚 − 1
• 𝒗𝑖 ≠ 0 かつ 𝑖 ≠ 𝑗ならば 𝒗𝑖 ≠ 𝒗𝑗 とする
• 𝐻 = (𝒗1𝑇 , … , 𝒗𝑇𝑛 ) が一般ハミング符号の検査行列
• m=3なら (7,4,3), m=4 なら (15, 11, 3)
• 一般には (2𝑚 − 1, 2𝑚 − 1 − 𝑚, 3)


# Page. 15

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

15
拡大ハミング符号(8,4,4)
• ハミング符号は1ビットの誤りを訂正できるが、2ビットの誤り
は検出も訂正もできない
•例
• 符号語𝒄 = 0000000、受信語𝒚 = 0000011
• シンドロームは 0 1 1 𝑇 したがって4ビット目が誤りと判定され、
ෝ = 0001011となる
𝒙
• せめて2ビット誤りを検出できるようにならないか
⇒拡大ハミング符号


# Page. 16

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

16
拡大ハミング符号(8,4,4)
• 拡大ハミング符号は、ハミング符号にパリティビットを付加し
たもの
• ハミング符号をさらに単一パリティ符号で符号化したのとおなじ
• 例 符号語𝒄 = 00000000、受信語𝒚 = 00000110
• 最後の1ビットはパリティなので除いて復号すると、
ෝ = 0001011となる
𝒙
• 復号結果にもう一度元のパリティビットを連結すると
ෝ = 00010110 となる
𝒙
• この復号結果には1が奇数個含まれているので、
パリティが合わない⇒誤りであることがわかる


# Page. 17

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

17
きちんと説明すると
• ハミング符号の符号語を𝒄とする
• 受信語 𝒚 = 𝒄 + 𝒆, 𝑤ℎ 𝒆 = 2 とし、復号結果を𝒄′ ≠ 𝒄 とする
• 誤差ベクトル 𝒆 = 𝒆1 + 𝒆2 , 𝑤ℎ 𝒆1 = 𝑤ℎ 𝒆2 = 1 とする
• シンドローム 𝐻𝒚𝑇 = 𝐻𝒆𝑇 = 𝐻𝒆1𝑇 + 𝐻𝒆𝑇2 = 𝒉𝑖 + 𝒉𝑗 ≠ 0
• 誤りを1ビットと仮定して訂正するので、𝑑ℎ 𝒚, 𝒄′ = 1
• 𝑑ℎ 𝒚, 𝒄 = 2なので、𝑑ℎ (𝒄, 𝒄′ )は1または3である。符号の最小距
離は3なので、 𝑑ℎ 𝒄, 𝒄′ = 3 とわかる。
• したがって𝒄と𝒄′のパリティは異なるので、
単一パリティ符号によって誤りが検出できる


# Page. 18

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

18
表による復号
• ハミング符号は、シンドロームを見ればただちにどのビットが
誤ったかわかるようになっていた
• そのような特殊な符号ではなく、一般の線型符号に利用できる
復号法：シンドローム表復号
• シンドロームが同じ値になるベクトルの集合を「コセット」と呼ぶ
• シンドロームの値ごとに、誤差ベクトルを記録しておく
• 通常はコセットの中で最もハミング重みが小さいベクトル（コセットリーダー）
• シンドロームがわかれば、そこから表を引くことで誤りがわかる


# Page. 19

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

19
例
1 1 1 0 0
1 0 1 0 1
•𝐺=
,𝐻= 0 1 0 1 0
0 1 1 1 0
1 0 0 0 1
• 5ビットの値に対して片っ端からシンドロームを計算する
受信語
S
受信語
S
受信語
S
受信語
S
00000
000
01000
110
10000
101
11000
011
00001
001
01001
111
10001
100
11001
010
00010
010
01010
100
10010
111
11010
001
00011
011
01011
101
10011
110
11011
000
00100
100
01100
010
10100
001
11100
111
00101
101
01101
011
10101
000
11101
110
00110
110
01110
000
10110
011
11110
101
00111
111
01111
001
10111
010
11111
100


# Page. 20

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

20
例
• シンドロームが001となる受信語と、それに最も近い符号語
受信語
シンドローム
復号結果
誤差ベクトル
00001
001
00000
00001
01111
001
01110
00001
10100
001
10101
00001
11010
001
11011
00001
シンドロームの値が同じ
＝誤り位置が同じ
（シンドロームは誤りの情報の
みを含むため）
シンドロームが001 ⇒誤りベクトル＝00001 という情報を表にしておけばよい
シンドロームの種類2𝑚 は、符号語の種類2𝑛 よりも少ないので表が小さくなる
（例では2𝑛 = 32, 2𝑚 = 8）


# Page. 21

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

21
シンドローム表
• シンドロームの値ごとに誤差ベクトルを記録したもの
シンドローム
誤差ベクトル
001
00001
010
00010
011
00011/11000
100
00100
101
10000
110
01000
111
01001/10010
1ビットしか誤りがない場合は
これらのシンドロームは現れ
ない