Binary BCH code and Burst error correction code

2元 BCH 符号及びバースト誤り訂正符号

誤り訂正デモンストレーション

2 元非原始 BCH 符号を含むいくつかの、ランダム誤り訂正符号と、バースト誤り訂正符号の誤り訂正デモンストレーションです。

(n, k) 2 元 BCH 符号 (t はランダム誤り訂正能力, b はバースト誤り訂正能力とする)

(31,25) t = 1 修正ハミングランダム誤り訂正符号 + 誤り訂正デモンストレーション

(15,10) t = 1, b = 2 修正ハミングランダム誤り訂正符号 + 誤り訂正デモンストレーション + JAVA プログラム例

(64,51) t = 2 BCH ランダム誤り訂正符号 + 誤り訂正デモンストレーション

(63,51) t = 2, b = 3 BCH符号 + 誤り訂正デモンストレーション

(39,27) t = 2 ランダム誤り訂正符号 + 誤り訂正デモンストレーション

(33,22) t = 2 ランダム誤り訂正符号 + 誤り訂正デモンストレーション

(16, 8) t = 2, b = 3 短縮 BCH ランダム誤り訂正符号 + 誤り訂正デモンストレーション + C プログラム例

(31,16) t = 3, b = 6 BCH ランダム誤り訂正符号 + 誤り訂正デモンストレーション - NTT方式無線呼出システムで使用された符号の仲間

(24,12) t = 3 拡大 Golay ランダム誤り訂正符号 + 誤り訂正デモンストレーション - Voyger 1,2 で使用された完全符号

(39,22) t = 3 ランダム誤り訂正符号 + 誤り訂正デモンストレーション

(41,21) t = 4 ランダム誤り訂正符号 + 誤り訂正デモンストレーション

(47,24) t = 5 ランダム誤り訂正符号 + 誤り訂正デモンストレーション

(n, k) バースト誤り訂正符号 (b はバースト誤り訂正能力とする, Reiger bound : 2 b ≤ n - k)

(19,11) b = 4 最適バースト誤り訂正符号

(27,17) b = 5 最適バースト誤り訂正符号 + 誤り訂正デモンストレーション

(48,37) b = 5 　　バースト誤り訂正符号 + 誤り訂正デモンストレーション

(34,22) b = 6 最適バースト誤り訂正符号

(38,24) b = 7 最適バースト誤り訂正符号

(48,32) b = 8 最適バースト誤り訂正符号 + 誤り訂正デモンストレーション

(50,34) b = 8 最適バースト誤り訂正符号

(56,38) b = 9 最適バースト誤り訂正符号 + 誤り訂正デモンストレーション

(59,39) b =10 最適バースト誤り訂正符号 + 誤り訂正デモンストレーション

(64,42) b =11 最適バースト誤り訂正符号 + 誤り訂正デモンストレーション

(56,32) b =12 最適バースト誤り訂正符号 + 誤り訂正デモンストレーション - 航空機のトランスポンダで使用されている符号

(64,40) b =12 最適バースト誤り訂正符号 + 誤り訂正デモンストレーション

(78,52) b =13 最適バースト誤り訂正符号

(82,54) b =14 最適バースト誤り訂正符号

⚠️ Demo の実行には Java 8 のインストールと例外サイトへの追加が必要です。

生成多項式一覧

ハードウェア的にも実装が容易な検査ビット数 m が 17 以下の 2 ～ 3 ビットランダム誤り訂正 2 元 BCH 符号を表 1 にまとめました。
2 元非原始 BCH 符号は計算機探索によって見付けたものを含みます。

表 1 [検査ビット数が 17 以下の 2 元 BCH 符号]

n k m d GP REC RED BEC Comment

17 9 8 5 0x1d7 2 - 3r

21 12 9 5 0x3b3 2 - 3r

17 8 9 6 0x279 2 3 -

31 21 10 5 0x4c3 2 - 4r BCH(31, 21) M3*M5

22 12 10 6 0x51d 2 3 -

23 12 11 7 0xae3 3 - - Golay(23, 12)

33 22 11 6 0xdfb 2 3 *3r

39 27 12 6 0x1a23 2 3 *3r

36 24 12 6 0x1a23 2 3 *4

28 16 12 5 0x12bb 2 - 5r

63 51 12 5 0x1539 2 - 3r BCH(63, 51) M1*M3

65 53 12 5 0x11f1 2 - -

64 51 13 6 0x3213 2 3 *3r

127 113 14 5 0x547d 2 - ? BCH(127, 113)

31 16 15 7 0xa943
0xdd5d 3 - 6r BCH(31, 16) M1*M3*M9
M1*M7*M9

35 19 16 7 0x126b5 3 - -

255 239 16 5 0x16f63 2 - ? BCH(255, 239)

39 22 17 8 0x237eb 3 4 -

63 46 17 7 0x2ea37 3 - 4r BCH(63, 46)

n : 符号ビット数
k : 情報ビット数
m : 検査ビット数
d : ハミング距離
GP : 生成多項式 (16 進数表示)
REC : ランダム誤り訂正ビット数
RED : ランダム誤り検出ビット数
BEC : バースト誤り訂正ビット数 ( r : バースト誤りの巡回パターンを含む、* : ランダム誤り検出もれを許容した場合)

表 2 [その他の 2 元非原始 BCH 符号]

n k m d GP REC RED BEC Comment

41 21 20 9 0x1b4e5b 4 - (9) 0x17ce7d

47 24 23 11 0x8c76ef 5 - (11) 0xf76e31

65 40 25 9 0x3b18037 4 - (10) 0x1519a87b

73 46 27 9 0xf3ff75f 4 - (12) 0xfaeffcf

表 3 [2 元原始 BCH 符号の生成多項式]

n k d 最小多項式生成多項式 GP(x)

7 4 3 M1 = 1011 1011

15 11 3 M1 = 1 0011 1 0011

15 7 5 M3 = 1 1111 1 1101 0001

15 5 7 M5 = 0 0111 101 0011 0111

31 26 3 M1 = 10 0101 10 0101

31 21 5 M3 = 11 1101 111 0110 1001

31 16 7 M5 = 11 0111 1000 1111 1010 1111

31 11 11 M7 = 10 1111 1011 0001 0011 0110 0101

31 6 15 M9 = 11 1011 11 0010 1101 1110 1010 0010 0111

63 57 3 M1 = 100 0011 100 0011

63 51 5 M3 = 101 0111 1 0101 0011 1001

63 45 7 M5 = 110 0111 111 1000 0010 1100 1111

63 39 9 M7 = 100 1001 1 1101 1011 0010 0111 0111 0111

63 36 11 M9 = 000 1101 1000 0110 1110 1000 0001 0001 0011

63 30 13 M13 = 110 1101 11 0111 1100 1101 0000 1110 1011 0110 0111

63 24 15 M15 = 101 1011 略

63 18 21 M21 = 111 0101 略

63 16 23 M23 = 000 0111 略

63 10 27 M27 = 111 0011 略

63 7 31 M31 = 000 1011 略

127 120 3 M1 = 1000 1001 1000 1001

127 113 5 M3 = 1000 1111 100 0011 0111 0111

127 106 7 M5 = 1001 1101 10 0110 1101 1001 1110 0011

127 99 9 M7 = 1111 0111 1110 0100 1110 0001 00110 1011 1001

127 92 11 M11 = 1111 1001 1011 1100 1011 0010 0001 0101 1101 0000 0001

127 85 13 M13 = 1000 1001 略

127 78 15 M15 = 1110 0101 略

127 71 19 M19 = 1011 1111 略

127 64 21 M21 = 1110 1111 略

127 57 23 M23 = 1100 1011 略

127 50 27 M27 = 1010 0111 略

127 43 29 M29 = 1111 0111 略

127 36 31 M31 = 1001 0001 略

127 29 43 M43 = 1101 0101 略

127 22 47 M47 = 1101 0011 略

127 15 55 M55 = 1111 0001 略

127 8 63 M63 = 1001 1101 略

255 247 3 M1 = 1 0001 1101 1 0001 1101

255 239 5 M3 = 1 0111 0111 1 0011 0111 1011 0001

255 231 7 M5 = 1 1111 0011 1 1011 1011 1010 0001 1011 0101

255 223 9 M7 = 1 0110 1001 1 1110 1110 0101 1011 0100 0010 1111 1101

255 215 11 M11 = 1 1011 1101 略

255 207 13 M13 = 1 1110 0111 略

255 199 15 M15 = 1 0010 1011 略

255 191 17 M17 = 1 1101 0111 略

255 187 19 M19 = 0 0000 1011 略

255 179 21 M21 = 1 0110 0101 略

255 171 23 M23 = 1 1000 1011 略

255 163 25 M25 = 1 0110 0011 略

255 155 27 M27 = 1 0001 1011 略

255 147 29 M29 = 1 0011 1111 略

255 139 31 M31 = 1 1000 1101 略

255 131 37 M37 = 1 0010 1101 略

255 123 39 M39 = 1 0101 1111 略

255 115 43 M43 = 1 1111 1001 略

255 107 45 M45 = 1 1100 0011 略

255 99 47 M47 = 1 0011 1001 略

255 91 51 M51 = 1 1010 1001 略

255 87 53 M53 = 0 0001 1111 略

255 79 55 M55 = 1 1000 0111 略

255 71 59 M59 = 1 1011 0001 略

255 63 61 M61 = 1 0100 1101 略

255 55 63 M63 = 1 1100 1111 略

255 47 85 M85 = 1 1101 1101 略

255 45 87 M87 = 0 0000 0111 略

511 502 3 M1 = 10 0001 0001 10 0001 0001

511 493 5 M3 = 10 0101 1001 100 1001 0101 1100 1001

誤り改善率

符号の誤り改善率を図１に示します。
図中 1 Mbps decade はビット誤り率 P_i × 伝送速度 1 Mbps × 10 年(≃ 3.1556925 × 10⁸ s) の逆数です。

図１［符号の誤り改善率］

$P_\mathrm{code} &=& \sum_{i = t + 1}^{n} {P_\mathrm{e}}^i \, (1 - P_\mathrm{e})^{n - i} \, {}_n \mathrm{C}_i\\ P_\mathrm{data} &=& 1 - (1 - {P_\mathrm{e}})^k$

P_c / P_d : 符号誤り改善率
P_c : ランダム誤り訂正後の符号誤り率
P_d : 誤り訂正無しの場合のデータ誤り率
P_e : 伝送路のビット誤り率
n : 符号のビット幅
k : データのビット幅
t : ランダム誤り訂正可能なビット数

補足

二元多項式のかけ算
リスト 1 [二元多項式のかけ算のプログラム例]
long polymul(long a, long b) { int i; long c = 0; for (i = 0; (b >> i) != 0; i++) { c ^= (a << i) * ((b >> i) & 1); } return c; }

n	k	m	d	GP	REC	RED	BEC	Comment
17	9	8	5	0x1d7	2	-	3r
21	12	9	5	0x3b3	2	-	3r
17	8	9	6	0x279	2	3	-
31	21	10	5	0x4c3	2	-	4r	BCH(31, 21) M3*M5
22	12	10	6	0x51d	2	3	-
23	12	11	7	0xae3	3	-	-	Golay(23, 12)
33	22	11	6	0xdfb	2	3	*3r
39	27	12	6	0x1a23	2	3	*3r
36	24	12	6	0x1a23	2	3	*4
28	16	12	5	0x12bb	2	-	5r
63	51	12	5	0x1539	2	-	3r	BCH(63, 51) M1*M3
65	53	12	5	0x11f1	2	-	-
64	51	13	6	0x3213	2	3	*3r
127	113	14	5	0x547d	2	-	?	BCH(127, 113)
31	16	15	7	0xa943 0xdd5d	3	-	6r	BCH(31, 16) M1M3M9 M1M7M9
35	19	16	7	0x126b5	3	-	-
255	239	16	5	0x16f63	2	-	?	BCH(255, 239)
39	22	17	8	0x237eb	3	4	-
63	46	17	7	0x2ea37	3	-	4r	BCH(63, 46)

n	k	m	d	GP	REC	RED	BEC	Comment
41	21	20	9	0x1b4e5b	4	-	(9)	0x17ce7d
47	24	23	11	0x8c76ef	5	-	(11)	0xf76e31
65	40	25	9	0x3b18037	4	-	(10)	0x1519a87b
73	46	27	9	0xf3ff75f	4	-	(12)	0xfaeffcf

n	k	d	最小多項式	生成多項式 GP(x)

7	4	3	M1 = 1011	1011

15	11	3	M1 = 1 0011	1 0011
15	7	5	M3 = 1 1111	1 1101 0001
15	5	7	M5 = 0 0111	101 0011 0111

31	26	3	M1 = 10 0101	10 0101
31	21	5	M3 = 11 1101	111 0110 1001
31	16	7	M5 = 11 0111	1000 1111 1010 1111
31	11	11	M7 = 10 1111	1011 0001 0011 0110 0101
31	6	15	M9 = 11 1011	11 0010 1101 1110 1010 0010 0111

63	57	3	M1 = 100 0011	100 0011
63	51	5	M3 = 101 0111	1 0101 0011 1001
63	45	7	M5 = 110 0111	111 1000 0010 1100 1111
63	39	9	M7 = 100 1001	1 1101 1011 0010 0111 0111 0111
63	36	11	M9 = 000 1101	1000 0110 1110 1000 0001 0001 0011
63	30	13	M13 = 110 1101	11 0111 1100 1101 0000 1110 1011 0110 0111
63	24	15	M15 = 101 1011	略
63	18	21	M21 = 111 0101	略
63	16	23	M23 = 000 0111	略
63	10	27	M27 = 111 0011	略
63	7	31	M31 = 000 1011	略

127	120	3	M1 = 1000 1001	1000 1001
127	113	5	M3 = 1000 1111	100 0011 0111 0111
127	106	7	M5 = 1001 1101	10 0110 1101 1001 1110 0011
127	99	9	M7 = 1111 0111	1110 0100 1110 0001 00110 1011 1001
127	92	11	M11 = 1111 1001	1011 1100 1011 0010 0001 0101 1101 0000 0001
127	85	13	M13 = 1000 1001	略
127	78	15	M15 = 1110 0101	略
127	71	19	M19 = 1011 1111	略
127	64	21	M21 = 1110 1111	略
127	57	23	M23 = 1100 1011	略
127	50	27	M27 = 1010 0111	略
127	43	29	M29 = 1111 0111	略
127	36	31	M31 = 1001 0001	略
127	29	43	M43 = 1101 0101	略
127	22	47	M47 = 1101 0011	略
127	15	55	M55 = 1111 0001	略
127	8	63	M63 = 1001 1101	略

255	247	3	M1 = 1 0001 1101	1 0001 1101
255	239	5	M3 = 1 0111 0111	1 0011 0111 1011 0001
255	231	7	M5 = 1 1111 0011	1 1011 1011 1010 0001 1011 0101
255	223	9	M7 = 1 0110 1001	1 1110 1110 0101 1011 0100 0010 1111 1101
255	215	11	M11 = 1 1011 1101	略
255	207	13	M13 = 1 1110 0111	略
255	199	15	M15 = 1 0010 1011	略
255	191	17	M17 = 1 1101 0111	略
255	187	19	M19 = 0 0000 1011	略
255	179	21	M21 = 1 0110 0101	略
255	171	23	M23 = 1 1000 1011	略
255	163	25	M25 = 1 0110 0011	略
255	155	27	M27 = 1 0001 1011	略
255	147	29	M29 = 1 0011 1111	略
255	139	31	M31 = 1 1000 1101	略
255	131	37	M37 = 1 0010 1101	略
255	123	39	M39 = 1 0101 1111	略
255	115	43	M43 = 1 1111 1001	略
255	107	45	M45 = 1 1100 0011	略
255	99	47	M47 = 1 0011 1001	略
255	91	51	M51 = 1 1010 1001	略
255	87	53	M53 = 0 0001 1111	略
255	79	55	M55 = 1 1000 0111	略
255	71	59	M59 = 1 1011 0001	略
255	63	61	M61 = 1 0100 1101	略
255	55	63	M63 = 1 1100 1111	略
255	47	85	M85 = 1 1101 1101	略
255	45	87	M87 = 0 0000 0111	略

511	502	3	M1 = 10 0001 0001	10 0001 0001
511	493	5	M3 = 10 0101 1001	100 1001 0101 1100 1001

誤り訂正デモンストレーション

生成多項式一覧

誤り改善率

補足

関連項目