---
title: 通信符号理論 01
tags: 
author: [Akinori Ito](https://docswell.com/user/akinori-ito)
site: [Docswell](https://www.docswell.com/)
thumbnail: https://bcdn.docswell.com/page/L73W6QY575.jpg?width=480
description: 誤り訂正符号とは 符号の数学的定義と復号則
published: July 02, 26
canonical: https://docswell.com/s/akinori-ito/ZJWWPJ-2026-07-02-155828
---
# Page. 1

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

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


# Page. 2

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

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


# Page. 3

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

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


# Page. 4

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

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


# Page. 5

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

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


# Page. 6

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

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


# Page. 7

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

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


# Page. 8

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

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


# Page. 9

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

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


# Page. 10

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

10
ここからが本番です


# Page. 11

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

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


# Page. 12

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

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


# Page. 13

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

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


# Page. 14

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

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


# Page. 15

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

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


# Page. 16

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

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


# Page. 17

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

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


# Page. 18

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

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


# Page. 19

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

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


# Page. 20

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

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


# Page. 21

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

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


# Page. 22

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

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


# Page. 23

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

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


# Page. 24

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

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


# Page. 25

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

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


# Page. 26

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

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


# Page. 27

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

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


# Page. 28

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

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


# Page. 29

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

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


# Page. 30

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

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


# Page. 31

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

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


# Page. 32

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

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