(16, 8) 2-bit ランダム誤り訂正符号

概要

この符号は 2 ビットまでのランダム誤りとバースト長が 3 までのバースト誤りを訂正することが出来ます。
また符号語の全ビットが 1 になった場合には訂正不可能な誤りとして検出することが出来ます。

(16, 8) 2-bit ランダム誤り訂正符号デモンストレーション


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

(16, 8) 符号について

文献を探せばきっとあるのではとは思うのですが、 この符号は計算機探索によって見つけ出した 生成多項式
GP(x) = x8 + x7 + x6 + x4 + x2 + x + 1
の (17, 9) 符号を 1 ビット短縮したものです。
この (17, 9) 符号も 2 ビットランダム誤り訂正、3 ビットバースト誤り訂正、 全符号語ビットが 1 の検出ができます。
また (17, 9) 符号を修正して 2 ビット誤り訂正、3 ビット誤り検出 (17, 8) 符号 にする場合の生成多項式は
GP(x) = x9 + x6 + x5 + x4 + x3 + 1
になります。
後日、(17,9) 二元非原始 BCH 符号 であることの確認がとれました[1,2]。

C プログラム例

List.1
/* ecc1608.c - (16,8) error correction code test program.
 * Rev 1.00 (Nov. 13, 2004)
 * (c) 2004, Takayuki HOSODA.
 * mailto:[email protected]
 * http://www.finetune.co.jp/~lyuka/
 */

#include <stdio.h>

#define DEBUG
#define GENPOLY    0xeb80
#define BITMASK    0x8000
#define DATAMASK   0x00ff
#define ECCMASK    0x00ff
#define CODEMASK   0xffff
#define CODELEN        16
#define DATALEN         8
#define ECCLEN          8
#define N2E        0x0100
#define N2D        0x0100

unsigned short errtbl[N2E];
unsigned short enctbl[N2D];

unsigned short
encode(data)
    unsigned short data;
{
    return enctbl[data & DATAMASK];
}

unsigned short
getsyn(code)
    unsigned short code;
{
    return code ^ enctbl[code >> ECCLEN];
}

unsigned short
decode(code)
    unsigned short code;
{
    unsigned short status;

    status = errtbl[getsyn(code)];
    if (status == 0xffff)
        return status;
    return (code ^ status) >> ECCLEN;
}

void
init() {
    int                i, j;
    unsigned short     code;
    unsigned short     data;
    unsigned short      ecc;
    unsigned short  genpoly;
    unsigned short  bitmask;
    extern unsigned short errtbl[N2E];
    extern unsigned short enctbl[N2D];

    for (data = 0; data < N2D; data++) {
        genpoly = GENPOLY;
        bitmask = BITMASK;
        ecc = (data << ECCLEN);
        for (i = DATALEN; i > 0; i--){
            if (ecc & bitmask)
                ecc ^= genpoly;
            bitmask >>= 1;
            genpoly >>= 1;
        }
        enctbl[data] = ((data << ECCLEN) | ecc) & CODEMASK;
    }
    errtbl[0] = 0;
    for (i = 1; i < CODELEN; i++) {
        errtbl[i] = CODEMASK;
    }
    errtbl[getsyn(CODEMASK)] = CODEMASK;
    for (i = 0; i < CODELEN; i++) {
        j = 0x7;
        code = ((j << i) | (j >> (CODELEN - i))) & CODEMASK;
        errtbl[getsyn(code)] = code;
    }
    for (i = 0; i < CODELEN - 1; i++) {
        for(j = i + 1; j < CODELEN; j++){
            code = (1 << i) | (1 << j);
            errtbl[getsyn(code)] = code;
        }
    }
    for (i = 0; i < CODELEN; i++) {
        code = (1 << i);
        errtbl[getsyn(code)] = code;
    }
}

#ifdef DEBUG
char *
binstr(bin)
    unsigned short bin;
{
    int i;
    static char str[CODELEN];
    str[CODELEN] = '\0';
    for (i = CODELEN - 1; i >= 0; i--)
        str[CODELEN - 1 - i] = bin & (1 << i) ? '1' : '0';
    return str;
}

int
main()
{
    int i, j, error;
    unsigned short data, code;
    unsigned long  total;

    init();
    i = GENPOLY >> (DATALEN - 1);
    printf("(%d,%d) GP = %s (0x%x)\n", CODELEN, DATALEN,
        binstr(i) + DATALEN - 1, i);
    printf("Generator matrix\n");
    for (i = 0; i < DATALEN; i++){
        data = 1 << (DATALEN - 1 - i);
        printf("%d: %s\n", i, binstr(encode(data)));
    }
    printf("\n");
    total = 0;
    error = 0;
    if (CODEMASK != decode(CODEMASK))
        error = 1;
    printf("test0: stack to '1' detection - %s.\n", error ? "FAIL" : "Passed");
    total++;
    error = 0;
    for (data = 0; data < N2D; data++) {
        code = encode(data);
        for(i = 0; i < CODELEN; i++){
            if (data != decode(code ^ (1 << i)))
                error = 1;
            total++;
        }
    }
    printf("test1: single error correction - %s.\n", error ? "FAIL" : "Passed");
    error = 0;
    for (data = 0; data < N2D; data++) {
        code = encode(data);
        for(i = 0; i < CODELEN - 1; i++){
            for(j = i + 1; j < CODELEN; j++){
                if (data != decode(code ^ ((1 << i) | (1 << j))))
                    error = 1;
                total++;
            }
        }
    }
    printf("test2: random double error correction - %s.\n", error ? "FAIL" : "Passed");
    error = 0;
    for (data = 0; data < N2D; data++) {
        code = encode(data);
        for(i = 0; i < CODELEN; i++){
            j = 0x7;
            if (data != decode(code ^ (((j << i) | (j >> (CODELEN - i))) & CODEMASK)))
                error = 1;
            total++;
        }
    }
    printf("test3: 3 bit length burst error correction - %s.\n", error ? "FAIL" : "Passed");
    printf("totl %ld vectors tested.\n", total);
    return 0;
}
#endif
Download the program shown above — ecc1608test-1.00.tar.gz
MD5 (ecc1608test-1.00.tar.gz) = f404d95a27f6f389d78626f2cadcfda1

参考文献

  1. 符号理論, 今井秀樹, 電子情報通信学会, ISBN4-88552-090-8
  2. (3) Hans J.Matt, James L. Massey (May 1980), "Determining the Burst-Correcting Limit of Cyclic Codes", IEEE Transactions on Information Theory IT-26 (3)

関連項目

2元 BCH 符号及びバースト誤り訂正符号
www.finetune.co.jp [Mail] © 2000 Takayuki HOSODA.