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


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

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

(n, k) 2 元 BCH 符号 (t はランダム誤り訂正能力, b はバースト誤り訂正能力とする) (n, k) バースト誤り訂正符号 (b はバースト誤り訂正能力とする, Reiger bound : 2 bn - k)
⚠️ Demo の実行には Java 8 のインストール例外サイトへの追加 が必要です。

生成多項式一覧

ハードウェア的にも実装が容易な検査ビット数 m が 17 以下の 2 〜 3 ビットランダム誤り訂正 2 元 BCH 符号を 表 1 にまとめました。
2 元 非原始 BCH 符号は計算機探索によって見付けたものを含みます。
表 1 [検査ビット数が 17 以下の 2 元 BCH 符号]
nkmdGPRECREDBECComment
179850x1d72 -3r
2112950x3b32-3r
178960x27923-
31211050x4c32-4rBCH(31, 21) M3*M5
22121060x51d23-
23121170xae33--Golay(23, 12)
33221160xdfb23*3r
39271260x1a2323*3r
36241260x1a2323*4
28161250x12bb2-5r
63511250x15392-3rBCH(63, 51) M1*M3
65531250x11f12--
64511360x321323*3r
1271131450x547d2-?BCH(127, 113)
31161570xa943
0xdd5d
3-6rBCH(31, 16) M1*M3*M9
M1*M7*M9
35191670x126b53--
2552391650x16f632-?BCH(255, 239)
39221780x237eb34-
63461770x2ea373-4rBCH(63, 46)
n : 符号ビット数
k : 情報ビット数
m : 検査ビット数
d : ハミング距離
GP : 生成多項式 (16 進数表示)
REC : ランダム誤り訂正ビット数
RED : ランダム誤り検出ビット数
BEC : バースト誤り訂正ビット数 ( r : バースト誤りの巡回パターンを含む、* : ランダム誤り検出もれを許容した場合)
表 2 [その他の 2 元非原始 BCH 符号]
nkmdGPRECREDBECComment
41212090x1b4e5b4-(9)0x17ce7d
472423110x8c76ef5-(11)0xf76e31
65402590x3b180374-(10)0x1519a87b
73462790xf3ff75f4-(12)0xfaeffcf
表 3 [2 元原始 BCH 符号の生成多項式]
nkd最小多項式生成多項式 GP(x)

743M1 = 10111011

15113M1 = 1 00111 0011
1575M3 = 1 11111 1101 0001
1557M5 = 0 0111101 0011 0111

31263M1 = 10 010110 0101
31215M3 = 11 1101111 0110 1001
31167M5 = 11 01111000 1111 1010 1111
311111M7 = 10 11111011 0001 0011 0110 0101
31615M9 = 11 101111 0010 1101 1110 1010 0010 0111

63573M1 = 100 0011100 0011
63515M3 = 101 01111 0101 0011 1001
63457M5 = 110 0111111 1000 0010 1100 1111
63399M7 = 100 10011 1101 1011 0010 0111 0111 0111
633611M9 = 000 11011000 0110 1110 1000 0001 0001 0011
633013M13 = 110 110111 0111 1100 1101 0000 1110 1011 0110 0111
632415M15 = 101 1011
631821M21 = 111 0101
631623M23 = 000 0111
631027M27 = 111 0011
63731M31 = 000 1011

1271203M1 = 1000 10011000 1001
1271135M3 = 1000 1111100 0011 0111 0111
1271067M5 = 1001 110110 0110 1101 1001 1110 0011
127999M7 = 1111 01111110 0100 1110 0001 00110 1011 1001
1279211M11 = 1111 10011011 1100 1011 0010 0001 0101 1101 0000 0001
1278513M13 = 1000 1001
1277815M15 = 1110 0101
1277119M19 = 1011 1111
1276421M21 = 1110 1111
1275723M23 = 1100 1011
1275027M27 = 1010 0111
1274329M29 = 1111 0111
1273631M31 = 1001 0001
1272943M43 = 1101 0101
1272247M47 = 1101 0011
1271555M55 = 1111 0001
127863M63 = 1001 1101

2552473M1 = 1 0001 11011 0001 1101
2552395M3 = 1 0111 01111 0011 0111 1011 0001
2552317M5 = 1 1111 00111 1011 1011 1010 0001 1011 0101
2552239M7 = 1 0110 10011 1110 1110 0101 1011 0100 0010 1111 1101
25521511M11 = 1 1011 1101
25520713M13 = 1 1110 0111
25519915M15 = 1 0010 1011
25519117M17 = 1 1101 0111
25518719M19 = 0 0000 1011
25517921M21 = 1 0110 0101
25517123M23 = 1 1000 1011
25516325M25 = 1 0110 0011
25515527M27 = 1 0001 1011
25514729M29 = 1 0011 1111
25513931M31 = 1 1000 1101
25513137M37 = 1 0010 1101
25512339M39 = 1 0101 1111
25511543M43 = 1 1111 1001
25510745M45 = 1 1100 0011
2559947M47 = 1 0011 1001
2559151M51 = 1 1010 1001
2558753M53 = 0 0001 1111
2557955M55 = 1 1000 0111
2557159M59 = 1 1011 0001
2556361M61 = 1 0100 1101
2555563M63 = 1 1100 1111
2554785M85 = 1 1101 1101
2554587M87 = 0 0000 0111

5115023M1 = 10 0001 000110 0001 0001
5114935M3 = 10 0101 1001100 1001 0101 1100 1001

誤り改善率

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

図1[符号の誤り改善率]
Error reduction characteristics

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
Pc / Pd : 符号誤り改善率
Pc : ランダム誤り訂正後の符号誤り率
Pd : 誤り訂正無しの場合のデータ誤り率
Pe : 伝送路のビット誤り率
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;
}

関連項目


www.finetune.co.jp [Mail] © 2000 Takayuki HOSODA.