---
title: 通信符号理論 08
tags: 
author: [Akinori Ito](https://docswell.com/user/akinori-ito)
site: [Docswell](https://www.docswell.com/)
thumbnail: https://bcdn.docswell.com/page/VEPKV92P78.jpg?width=480
description: リード・ソロモン符号 復号法（後半） BCH符号 QRコード
published: July 02, 26
canonical: https://docswell.com/s/akinori-ito/K1QQG2-2026-07-02-161347
---
# Page. 1

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

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


# Page. 2

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

2
前回までのあらすじ
• リード・ソロモン(RS)符号
• RS符号の検査行列について
• RS符号の符号化法
• メッセージ多項式に𝑧 2𝑡 をかけて生成多項式𝑔(𝑧)で割った余りがパリティ
• RS符号の復号法：Peterson復号
1. 誤りの個数𝑣を調べる
2. 誤りの位置を調べる
3. 誤差ベクトルの値を求める ←説明済み


# Page. 3

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

3
一般のRS符号の検査行列
𝐻=
1 𝛼
1 𝛼2
⋮
⋮
1 𝛼 2𝑡
⋯
𝛼 𝑛−1
⋯ 𝛼 2(𝑛−1)
⋱
⋮
⋯ 𝛼 2𝑡(𝑛−1)
• ただし𝑛 = 𝑞 − 1、1 ≤ 𝑡 ≤ (𝑑 − 1)/2
• 𝑘 = 𝑛 − 2𝑡、𝑑 = 2𝑡 + 1
• 𝑡シンボルの誤りを訂正できる
𝒒
4
8
• 𝑡の最大値は⇒
16
32
64
𝑛
3
7
15
31
63
max 𝑡
1
3
7
15
31
• ただし𝑡を最大にとると𝑘 = 1なので繰り返し符号になる


# Page. 4

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

4
Peterson–Gorenstein–Zierler 復号法
• 基礎的情報
• 受信語𝒀 = 𝑿 + 𝑬 ここで𝑿は符号語、𝑬は誤差ベクトル
• 𝑬 = (𝐸0 , … , 𝐸𝑛−1 )とする（未知）
• 𝑬のうち𝑣個の要素が非ゼロ（𝑣 ≤ 𝑡）
• 𝑺 = 𝐻𝑬𝑇 = 𝑆1 , … 𝑆2𝑡 𝑇
• 誤り位置に関する式
• 誤り位置を 0 ≤ 𝑗1 < ⋯ < 𝑗𝑣 < 𝑛 とする
• 最初は未知だが、これがわかっていたとする
• 𝐸𝑗𝑘 ≠ 0 (𝑘 = 1, … 𝑣)
• 𝒆 = 𝑒1 , … , 𝑒𝑣 = (𝐸𝑗1 , … , 𝐸𝑗𝑣 )とする
• 𝑬のうち0でない要素だけを集めて作ったベクトル。𝑒𝑘 ≠ 0 (𝑘 = 1, … , 𝑣)


# Page. 5

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

5
Peterson–Gorenstein–Zierler 復号法
• 誤り位置に関する式
• 検査行列は
1 𝛼 ⋯
𝛼 𝑛−1
2
2(𝑛−1)
1
𝛼
⋯
𝛼
𝐻=
⋮
⋮
⋱
⋮
1 𝛼 2𝑡 ⋯ 𝛼 2𝑡(𝑛−1) 𝑇
• 𝐻の𝑘列目（０から数える）は 𝛼 𝑘 , 𝛼 2𝑘 , … , 𝛼 2𝑡𝑘
2𝑡 𝑇
2
𝑗𝑘
• 𝑥𝑘 = 𝛼 とおく。 𝐻の𝑗𝑘 列目は 𝑥𝑘 , 𝑥𝑘 , … , 𝑥𝑘
となる
• シンドロームの第𝑘要素
𝑛−1
𝑣
𝑣
𝑆𝑘 = ෍ 𝛼 𝑘𝑖 𝐸𝑖 = ෍ 𝛼 𝑘𝑗𝑖 𝐸𝑗𝑖 = ෍ 𝑥𝑖𝑘 𝑒𝑖
𝑖=0
𝑖=1
𝑖=1
0でない要素だけ加算


# Page. 6

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

誤り個数と位置がわかる状態で
誤りの値を求める
• 誤差ベクトルの0じゃないところだけ寄せ集めて作った式
𝑥1 ⋯ 𝑥𝑣
⋱
⋮ 𝒆T = 𝑋𝒆𝑻 = 𝑺
𝐻𝑬𝑇 = ⋮
𝑥12𝑡 ⋯ 𝑥𝑣2𝑡
• これを解けば𝒆がわかり、誤り位置と合わせれば誤りベクトル
がわかる
6


# Page. 7

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

7
ここまでが前回までのあらすじ
ここから今回の内容


# Page. 8

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

誤りの個数がわかった時に
誤りの位置を知る
• 前提
• 誤りの個数𝑣がわかっている
• 目標
• 𝑥1 , … , 𝑥𝑣 = (𝛼 𝑗1 , … , 𝛼 𝑗𝑣 )を知る
• 検査行列の1行目には特定の𝛼 𝑗 は1回しか出てこないので、位置がわか
る
• 誤り位置多項式
• 𝜎 𝑧 = 1 + 𝜎1 𝑧 + 𝜎2 𝑧 2 + ⋯ + 𝜎𝑣 𝑧 𝑣
• 𝜎 𝑥𝑖−1 = 0 を満たすと仮定する（あとからつじつまを合わせる）
8


# Page. 9

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

9
誤り位置多項式
• 誤り位置多項式の係数 𝜎1 , … , 𝜎𝑣 を求めたい
• テクニカルなことをします
• 𝜎 𝑥𝑗−1 = 0 (𝑗 = 1, … , 𝑣) より、
𝑣
෍ 𝑒𝑗 𝑥𝑗𝑖+𝑣 𝜎 𝑥𝑗−1 = 0
𝑗=1
• したがって
𝑣
෍ 𝑒𝑗 𝑥𝑗𝑖+𝑣 1 + 𝜎1 𝑥𝑗−1 + ⋯ + 𝜎𝑣 𝑥𝑗−𝑣 = 0
𝑗=1
𝑣
෍ 𝑒𝑗 𝑥𝑗𝑖+𝑣 + 𝜎1 𝑒𝑗 𝑥𝑗𝑖+𝑣−1 + ⋯ + 𝜎𝑣 𝑒𝑗 𝑥𝑗𝑖 = 0
𝑗=1


# Page. 10

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

10
誤り位置多項式
• 前の結果から
𝑣
෍ 𝑒𝑗 𝑥𝑗𝑖+𝑣 + 𝜎1 𝑒𝑗 𝑥𝑗𝑖+𝑣−1 + ⋯ + 𝜎𝑣 𝑒𝑗 𝑥𝑗𝑖 = 0
𝑗=1
෍ 𝑒𝑗 𝑥𝑗𝑖+𝑣 + 𝜎1 ෍ 𝑒𝑗 𝑥𝑗𝑖−𝑣+1 + ⋯ + 𝜎𝑣 ෍ 𝑒𝑗 𝑥𝑗𝑖 = 0
𝑗
𝑗
𝑗
• ここで 𝑆𝑖 = σ𝑣𝑘=1 𝑒𝑘 𝑥𝑘𝑖 より、
𝑆𝑖+𝑣 + 𝜎1 𝑆𝑖+𝑣−1 + ⋯ + 𝜎𝑣 𝑆𝑖 = 0
𝜎1 𝑆𝑖+𝑣−1 + ⋯ + 𝜎𝑣 𝑆𝑖 = 𝑆𝑖+𝑣
これが𝑖 = 1,2, …について成り立つ


# Page. 11

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

11
誤り位置多項式
• 𝜎1 𝑆𝑖+𝑣−1 + ⋯ + 𝜎𝑣 𝑆𝑖 = 𝑆𝑖+𝑣
• 行列形式にすると（足し算が逆順になることに注意）
𝜎𝑣
𝑆1
𝑆2
⋯
𝑆𝑣
𝑆𝑣+1
𝜎𝑣−1
𝑆2
𝑆3
⋯ 𝑆𝑣+1
𝑆𝑣+2
=
⋮
⋮
⋮
⋱
⋮
⋮
𝜎1
𝑆𝑣 𝑆𝑣+1 ⋯ 𝑆2𝑣−1
𝑆2𝑣
• これを解いて 𝜎1 , … , 𝜎𝑣 を得る


# Page. 12

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

12
誤り位置多項式
• 𝜎1 , … , 𝜎𝑣 がわかると、𝜎 𝑧 = 1 + 𝜎1 𝑧 + ⋯ + 𝜎𝑣 𝑧 𝑣 が計算できる
• 𝛼 𝑘 (𝑘 = 0, … , 𝑛 − 1) について実際に 𝜎(𝛼 −𝑘 )を計算し、値が0に
なったらその位置が誤り
→𝛼 𝑗1 , … , 𝛼 𝑗𝑣 がわかり、誤り位置が確定する


# Page. 13

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

13
例
• 原始多項式𝑧 3 + 𝑧 + 1による𝐺𝐹(23 )の(7,3,5)RS符号
• 𝑡=2
• 検査行列
1 𝛼
2
1
𝛼
𝐻=
1 𝛼3
1 𝛼4
• 符号語 (1 1 1 1 1 1 1)
• 受信語 (1 0 1 𝛼 1 1 1)
𝛼2
𝛼4
𝛼6
𝛼8
𝛼3
𝛼6
𝛼9
𝛼 12
𝛼4
𝛼8
𝛼 12
𝛼 16
𝛼5
𝛼 10
𝛼 15
𝛼 20
𝛼6
𝛼 12
𝛼 18
𝛼 24


# Page. 14

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

14
例
• 誤りが2個であることは既知だとする
• シンドローム 𝛼 2 + 𝛼 + 1 0 𝛼 2 𝛼 2 T
• 誤り位置多項式の係数を知る（誤りが2個であることは既知）
𝛼 2 + 𝛼 + 1 0 𝜎2 = 𝛼 2
𝛼2
0
𝛼 2 𝜎1
• 逆行列は
2
𝜎2
𝛼
𝜎1 = 0
𝛼2
0
0
𝛼2 + 𝛼 + 1
0
𝛼2 = 𝛼2 + 𝛼
𝛼2 + 𝛼 + 1 𝛼2
1


# Page. 15

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

15
例
• 誤り位置多項式
𝜎 𝑧 = 1 + 𝑧 + 𝛼2 + 𝛼 𝑧2
𝒊
0
1
2
3
4
5
6
𝑧
1
𝛼
𝛼2
𝛼3
𝛼4
𝛼6
𝑧 −1
1
𝛼6
𝛼4
𝛼3
𝜎(𝑧 −1 )
𝛼2 + 𝛼
0
𝛼5
𝛼2 + 𝛼 + 1
𝛼5
𝛼2
0
1
𝛼2 + 𝛼 + 1
𝛼2 + 𝛼
𝒊 = 𝟏, 𝟑の位置（2シンボル目と４シンボル
目）に誤りがあることがわかる
𝛼


# Page. 16

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

16
ついでに誤りの値も求めてみる
• 検査行列で誤りの列（𝑖 = 1,3）を集めて方程式を作る
𝛼 𝛼3
𝛼2 + 𝛼 + 1
𝑒1
𝛼2 𝛼6
0
=
𝑒2
𝛼3 𝛼9
𝛼2
𝛼 4 𝛼 12
𝛼2
• 冗長なので上２行だけでよい
𝛼 𝛼 3 𝑒1 = 𝛼 2 + 𝛼 + 1
𝛼 2 𝛼 6 𝑒2
0
逆行列をかけ
2
2
2
𝑒1
1
𝛼
𝛼
+
1
𝛼
+𝛼+1 =
=
𝑒2
𝛼+1
𝛼2 + 𝛼 + 1 𝛼2 + 𝛼
0


# Page. 17

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

17
復号する
• 求まった𝑒1 , 𝑒2 を２番目と４番目に入れて誤差ベクトルを作る
𝑬 = (0 1 0 𝛼 + 1 0 0 0)
• 復号
1 0 1 𝛼 1 1 1 + 0 1 0 𝛼 + 1 0 0 0 = (1 1 1 1 1 1 1)


# Page. 18

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

18
誤りの個数を知る
• シンドロームによる行列（誤り位置多項式の計算に利用）
𝑆1
𝑆2
⋯
𝑆𝑣
𝑆2
𝑆3
⋯ 𝑆𝑣+1
⋮
⋮
⋱
⋮
𝑆𝑣 𝑆𝑣+1 ⋯ 𝑆2𝑣−1
• この行列の行列式は、𝑣が実際の誤り個数より多いときは0にな
る
• 誤り個数より多い𝑣について行列式が0でないとすると、存在しない誤
り位置が推定できてしまう


# Page. 19

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

19
誤りの個数を知る
• この行列の行列式は、𝑣が実際の誤り個数より多いときは0にな
る
• 𝑣 = 𝑡, 𝑡 − 1, … , 1について行列式を求め、行列式が0でなくなっ
たところが誤り個数になる


# Page. 20

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

20
例
• 原始多項式𝑧 3 + 𝑧 + 1による𝐺𝐹(23 )の(7,3,5)RS符号
• 𝑡=2
• 符号語 (1 1 1 1 1 1 1)
• 受信語 (1 1 1 𝛼 1 1 1) 誤り１個
• シンドローム
𝐻 111𝛼111 𝑇 =
𝛼2 + 1
𝛼2
𝛼2 + 𝛼 + 1
𝛼
=
𝑆1
𝑆2
𝑆3
𝑆4


# Page. 21

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

21
例
• 𝑡 = 2より、𝑣 = 2と仮定すると
2
2
𝑆1 𝑆2
𝛼
+
1
𝛼
=
𝑆2 𝑆3
𝛼2
𝛼2 + 𝛼 + 1
= 𝛼2 + 1 𝛼2 + 𝛼 + 1 + 𝛼4 = 𝛼2 + 𝛼 + 𝛼 𝛼 + 1 = 0
• 𝑣 = 1と仮定すると
𝑆1 = 𝛼 2 + 1 ≠ 0
• したがって𝑣 = 1であることがわかる


# Page. 22

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

22
例（ついでに復号まで）
• 𝑆1 𝜎1 = 𝑆2 より 𝛼 2 + 1 𝜎1 = 𝛼 2
• べき表現にすると𝛼 6 𝜎1 = 𝛼 2 = 𝛼 9 より 𝜎1 = 𝛼 3 = 𝛼 + 1
• 誤り位置多項式 𝜎 𝑧 = 1 + 𝛼 3 𝑧
• 𝑧 = 𝛼 4 なら𝜎 𝑧 = 1 + 𝛼 7 = 1 + 1 = 0
1
𝛼7
• したがって誤り位置は𝛼4 = 𝛼 4 = 𝛼 3 より誤り位置は４番目
• 誤りベクトルを求める方程式
𝛼2 + 1
𝛼3
𝛼 2 +1
𝛼6 𝑒 =
𝛼2
4
2
より
𝑒
=
=
𝛼
𝛼
+1 =𝛼+1
1
1
3
9
2
𝛼
𝛼
𝛼 +𝛼+1
𝛼 12
𝛼


# Page. 23

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

23
例（ついでに復号まで）
• 𝑒1 = 𝛼 + 1で誤り位置は4番目なので
𝐸 = (0 0 0 𝛼 + 1 0 0 0)
• 元の符号語は
1 1 1 𝛼 1 1 1 + 0 0 0 𝛼 + 1 0 0 0 = (1 1 1 1 1 1 1)


# Page. 24

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

24
演習
• 原始多項式𝑧 3 + 𝑧 + 1による𝐺𝐹(23 )の(7,3,5)RS符号で
受信語 (0 0 0 0 0 0 1) を復号せよ。


# Page. 25

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

25
BCH符号
• Reed-Solomon符号と関連する符号
• 教科書ではReed-Solomon符号からBCH符号を導出しているが、BCH
符号の特殊な場合がReed-Solomon符号であるという立場もある
• 𝐺𝐹(2)上の符号で、RS符号の検査行列から導出される
• 例：𝐺𝐹(22 )上のRS符号の検査行列
2
1
𝛼
𝛼
1 𝛼
𝐻=
=
1 𝛼2 𝛼4
1 𝛼2
𝛼2
𝛼


# Page. 26

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

26
BCH符号の例
• 拡大体の元のベクトル表現
• 0=
0
1
0
1
,1 =
,𝛼=
, 𝛼2 = 𝛼 + 1 =
0
0
1
1
• 𝐺𝐹(22 )の検査行列から𝐺𝐹(2)の検査行列を作る
𝒉1
0 1 1
1 𝛼 𝛼 2 → 1 0 1 = 𝒉2
𝒉3
0 1 1
1 𝛼2 𝛼
𝒉4
1 1 0
• 𝒉3 = 𝒉1 , 𝒉4 = 𝒉1 + 𝒉2 より、これは次の検査行列と同じ：長さ3の繰り
返し符号
0 1 1
1 0 1


# Page. 27

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

27
もう一つ例
• 原始多項式 𝑧 3 + 𝑧 + 1 による 𝐺𝐹(23 ) のRS符号の検査行列
2
3
4
5
6
1
𝛼
𝛼
𝛼
𝛼
𝛼
𝛼
𝐻=
1 𝛼 2 𝛼 4 𝛼 6 𝛼 8 𝛼10 𝛼12
2
3
4
5
6
1
𝛼
𝛼
𝛼
𝛼
𝛼
𝛼
=
1 𝛼2 𝛼4 𝛼6 𝛼 𝛼3 𝛼5
2
2
2
2
1
𝛼
𝛼
𝛼
+
1
𝛼
+
𝛼
𝛼
+
𝛼
+
1
𝛼
+1
=
1 𝛼2 𝛼2 + 𝛼 𝛼2 + 1
𝛼
𝛼+1
𝛼2 + 𝛼 + 1


# Page. 28

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

28
もう一つ例
2
2
1
𝛼
𝛼
𝛼
+
1
𝛼
+𝛼
•
1 𝛼2 𝛼2 + 𝛼 𝛼2 + 1
𝛼
をベクトル表現にすると
0 0 1 0 1
0 1 0 1 1
1 0 0 1 0
0 1 1 1 0
0 0 1 0 1
1 0 0 1 0
𝛼2 + 𝛼 + 1
𝛼+1
1
1
1
0
1
1
1
0
1
1
1
1
=
𝛼2 + 1
𝛼2 + 𝛼 + 1
𝒉1
𝒉2
𝒉3
𝒉4
𝒉5
𝒉6
• 𝒉4 = 𝒉1 + 𝒉2 , 𝒉5 = 𝒉1 , 𝒉6 = 𝒉3 より、上3行だけ有効→ハミング符号


# Page. 29

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

29
BCH符号の符号化
• RS符号の符号化とよく似ているが、生成多項式の扱いが異なる
• RS符号：𝑔 𝑧 = 𝑧 − 𝛼 𝑧 − 𝛼 2 ⋯ (𝑧 − 𝛼 2𝑡 )
• BCH符号：𝑔 𝑧 = 𝐿𝐶𝑀[𝑚1 𝑧 , 𝑚2 𝑧 , ⋯ , 𝑚2𝑡 (𝑧)]
• 𝑚𝑖 (𝑧): 最小多項式
• 最小多項式
• 𝑚𝑖 𝑧 = 𝑧 − 𝛼 𝑖 𝑧 − 𝛼 2𝑖 𝑧 − 𝛼 4𝑖 𝑧 − 𝛼 8𝑖 ⋯
2𝑗 𝑖
ただし𝛼 が巡回して同じ要素が出現したらそこで止める
• 例：原始多項式𝑧 4 + 𝑧 + 1による𝐺𝐹(24 )の場合 𝛼 15 = 1より
𝑚1 𝑧 = (𝑧 − 𝛼)(𝑧 − 𝛼 2 )(𝑧 − 𝛼 4 )(𝑧 − 𝛼 8 ) （𝛼 16 = 𝛼 15 𝛼 = 𝛼）
𝑚2 𝑧 = (𝑧 − 𝛼 2 )(𝑧 − 𝛼 4 )(𝑧 − 𝛼 8 )(𝑧 − 𝛼)
𝑚3 𝑧 = (𝑧 − 𝛼 3 )(𝑧 − 𝛼 6 )(𝑧 − 𝛼 12 )(𝑧 − 𝛼 9 ) （𝛼 24 = 𝛼 9 , 𝛼 48 = 𝛼 3 ）
𝑚4 (𝑧) = (𝑧 − 𝛼 4 )(𝑧 − 𝛼 8 )(𝑧 − 𝛼)(𝑧 − 𝛼 2 ) （𝛼 32 = 𝛼 2 ）


# Page. 30

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

30
BCH符号の符号化
• 最小多項式
𝑚1 𝑧 = 𝑧 − 𝛼 𝑧 − 𝛼 2 𝑧 − 𝛼 4 z − 𝛼 8 = 𝑧 4 + 𝑧 + 1
𝑚3 𝑧 = 𝑧 − 𝛼 3 𝑧 − 𝛼 6 𝑧 − 𝛼12 𝑧 − 𝛼 9
= 𝑧4 + 𝑧3 + 𝑧2 + 𝑧 + 1
• 生成多項式 𝑔 𝑧 = 𝐿𝐶𝑀[𝑚1 𝑧 , 𝑚2 𝑧 , ⋯ , 𝑚2𝑡 (𝑧)]
• 例の場合、𝑡 = 2とすれば
𝑔 𝑧 = 𝐿𝐶𝑀 𝑚1 𝑧 , 𝑚2 𝑧 , 𝑚3 𝑧 , 𝑚4 𝑧
= 𝑧8 + 𝑧7 + 𝑧6 + 𝑧4 + 1
= 𝑚1 𝑧 𝑚3 𝑧


# Page. 31

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

31
最小多項式の計算例
𝑚1 𝑧 = 𝑧 − 𝛼 𝑧 − 𝛼 2 𝑧 − 𝛼 4 z − 𝛼 8
= 𝑧 4 + 𝛼 + 𝛼 2 + 𝛼 4 + 𝛼 8 𝑧 3 + 𝛼 3 + 𝛼 5 + 𝛼 6 + 𝛼 9 + 𝛼10 + 𝛼12 𝑧 2 +
𝛼 7 + 𝛼11 + 𝛼13 + 𝛼14 𝑧 + 𝛼15
𝛼 + 𝛼2 + 𝛼4 + 𝛼8 = 𝛼 + 𝛼2 + 𝛼 + 1 + 𝛼2 + 1 = 0
𝛼 3 + 𝛼 5 + 𝛼 6 + 𝛼 9 + 𝛼10 + 𝛼12
= 𝛼3 + 𝛼2 + 𝛼 + 𝛼3 + 𝛼2 + 𝛼3 + 𝛼 + 𝛼2 + 𝛼 + 1 + 𝛼3 + 𝛼2 + 𝛼 + 1 = 0
𝛼 7 + 𝛼11 + 𝛼13 + 𝛼14 = 𝛼 3 + 𝛼 + 1 + 𝛼 3 + 𝛼 2 + 𝛼 + 𝛼 3 + 𝛼 2 + 1 + 𝛼 3 + 1 = 1
𝛼15 = 1
より
𝑚1 𝑧 = 𝑧 4 + 𝑧 + 1
𝑧 4 + 𝑧 + 1 = 0による𝐺𝐹(24 )の元
𝛼 4 = 𝛼 + 1, 𝛼 5 = 𝛼 2 + 𝛼, 𝛼 6 = 𝛼 3 + 𝛼 2 , 𝛼 7 = 𝛼 3 + 𝛼 + 1, 𝛼 8 = 𝛼 2 + 1, 𝛼 9 = 𝛼 3 + 𝛼,
𝛼10 = 𝛼 2 + 𝛼 + 1, 𝛼11 = 𝛼 3 + 𝛼 2 + 𝛼, 𝛼12 = 𝛼 3 + 𝛼 2 + 𝛼 + 1, 𝛼13 = 𝛼 3 + 𝛼 2 + 1, 𝛼14 = 𝛼 3 + 1


# Page. 32

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

32
BCH符号の符号化
• 符号化プロセス
• メッセージ多項式 𝑚(𝑧)、生成多項式𝑔(𝑧)
• 符号語の多項式を 𝑅 𝑧 + 𝑧 𝑛−𝑘 𝑚(𝑧)とする
• 𝑧 𝑛−𝑘 𝑚(𝑧)を𝑔(𝑧)で割った余りが𝑅 𝑧 となる
• 例：原始多項式𝑧 4 + 𝑧 + 1によるBCH符号の符号化
• n=15, k=7, t=2とする
• メッセージ 1010110 →𝑚 𝑧 = 1 + 𝑧 2 + 𝑧 4 + 𝑧 5
• 生成多項式𝑔 𝑧 = 𝑧 8 + 𝑧 7 + 𝑧 6 + 𝑧 4 + 1
• 𝑧 𝑛−𝑘 𝑚(𝑧)を𝑔(𝑧)で割った余りは 𝑧 6 + 𝑧 5 + 𝑧 4 + 𝑧 3 + 1
• パリティビット 10011110, メッセージビット 1010110


# Page. 33

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

33
BCH符号の生成行列
• メッセージ1000000, 0100000, 0010000,…についてパリティ
ビットをそれぞれ求めれば生成行列が作れる
10001011
11001110
01100111
10111000
01011100
00101110
00010111
1000000
0100000
0010000
0001000
0000100
0000010
0000001
復号時の多項式の
作り方が違うだけ
なので列を入れ替
えても問題ない
1000000
0100000
0010000
0001000
0000100
0000010
0000001
10001011
11001110
01100111
10111000
01011100
00101110
00010111
1101000
0110100
0011010
0001101
1101110
0110111
1110011
1010001
10000000
01000000
00100000
00010000
00001000
00000100
00000010
00000001
検査行列


# Page. 34

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

34
Reed-Solomon符号の応用：QRコード
• 代表的な２次元コード
• 誤り訂正符号としてReed-Solomon符号が利用されている
• 複数の誤り訂正レベルが設定できる
レベル
訂正可能な面積
L
7%
M
15%
Q
25%
H
30%
• 複数のモデル（モデル１、モデル２、マイクロQR）
• モデル2では最大2953バイトのデータが格納可能


# Page. 35

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

35
QRコードのパターン
ファインダー
パターン
タイミングパターン
クワイエットゾーン
アライメントパターン


# Page. 36

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

36
QRコードのデータ配置
形式情報
誤り訂正レベル(LMQH)などの情報を
BCH符号化(15,5)して15ビット情報と
したあと２重に埋め込む
データとパリティを配置
（モデル２，バージョン２、レベルMの例）
キーエンス「よくわかる２次元コードの基本vol.1」より引用