10-bit DAC のデータの装置間伝送用に設計した誤り訂正モジュールの動作説明用に作成したものです。

⚠️ Demo の実行には JAVA のインストール と 例外サイトへの追加 が必要かも知れません

• Send code の Data 部分をクリックすると該当ビットを反転出来ます。
• Error bit の任意の部分をクリックすると該当ビットを反転出来ます。
• 最初はランダムな値の Data とランダムな 1 ビットの誤りになっています。
• タイトル部分をクリックすると Data がランダムに変更されます。
• Auto run 部分をクリックすると誤りテストを自動的に実行します。
  左から 1-bit 誤り訂正、2-bit 誤り検出のテストになっています。
• Control 部分をクリックすると制御用コードを送出します。
  

アプリケーション・ノート

この符号が完全符号では無い事を利用して、シンドロームが 10011 になるように チェックビットを 10011 で反転したワードを制御用に使用する事が可能です。
シリアル通信などでは例えば 010100110111000 をフレーム同期用ユニークワード として利用したり、パラレル通信では LSB 等の誤りが許容できる部分を同期信号と して利用することが考えられます。
このワードが１ビット誤ったもののシンドロームは２ビット誤りのものになります。
また全ビットが 1 になったものも同じく 10011 のシンドロームになりますので ケーブル抜けなどの検出に使う事も考えられます。

JAVA プログラム例

List.1

import java.util.*; // テスト用 main で Random クラスを使用するため。 /** 修正ハミング(15,10) 誤り訂正符号クラス * @author Takayuki HOSODA * @version $Id$ * @copyright (c) 2004, Takayuki HOSODA. All rights reserved. */ public class H1510 { /** 誤り位置と誤り状況テーブル */ private final int[] errorTable = {0x00000000, 0x00000001, 0x00000002, 0x80030000, 0x00000004, 0x80300000, 0x80060006, 0x00000400, 0x00000008, 0x8c000000, 0x80600060, 0x00000080, 0x800c0000, 0x00002000, 0x00000800, 0x83000000, 0x00000010, 0xb0000000, 0x98000000, 0x93008000, 0x80c00000, 0x00000020, 0x00000100, 0xe0000000, 0x80180000, 0x00000200, 0x00004000, 0xc0010000, 0x00001000, 0x81800000, 0x86000000, 0x00000040 }; /** 符号化テーブル。 */ private int[] encodeTable; /** 誤り状況を保持する。 * 0 の場合誤りが検出されなかった事を示す。 * 正の値の場合訂正が行われた誤り位置を示す。 * 負の値の場合訂正不可能な誤りが検出された事を示す。 */ protected int status; /** シンドロームを保持する。*/ protected int syndrome; /** 符号を保持する。 * bit 14..5 : 情報ビット, bit 4..0 : チェックビット */ protected int code; /** バーストエラーの訂正許可。 */ protected boolean burstErrorCorrection = false; /** Hamming(15,10) 生成多項式 GP(x) = x5 + x4 + x2 + x0 */ private final int GEN_POLY = 0x6a00; private final int BIT_MASK = 0x4000; private final int CODE_MASK = 0x7fff; private final int DATA_MASK = 0x03ff; private final int N2D = 0x0400; private final int DATA_LEN = 10; private final int ECC_LEN = 5; /** H1510 オブジェクトを生成する。 * 符号化テーブルが初期化されていない場合には初期化を行う。 */ public H1510() { if (encodeTable == null) { encodeTable = new int[N2D]; for (int data = N2D - 1; data > 0; data--) { int genpoly = GEN_POLY; int bitmask = BIT_MASK; int ecc = data << ECC_LEN; for (int i = DATA_LEN; i > 0; i--) { if ((ecc & bitmask) != 0) ecc ^= genpoly; bitmask >>= 1; genpoly >>= 1; } encodeTable[data] = (data << ECC_LEN) | ecc; } } } /** 符号のシンドロームを求める。*/ public H1510 getSyndrome() { syndrome = code ^ encodeTable[code >> ECC_LEN]; status = errorTable[syndrome]; return this; } /** 符号の誤り訂正を行う。 */ public H1510 correct(){ code ^= burstErrorCorrection ? status >> 16 : status ; code &= CODE_MASK; return this; } /** 符号化処理を行う。 * 10 bit のデータから 15 bit の符号を生成する。 */ public H1510 encode(int data) { code = encodeTable[data & DATA_MASK]; return this; } /** 復号処理を行う。 * 15 bit の符号から 10 bit のデータを取り出す。 */ public int decode() { return (code >> ECC_LEN) & DATA_MASK; } /** H1510 クラスのテスト用。*/ public static void main(String[] args) { Random random = new Random(12345); H1510 h = new H1510(); int code, data; final String[] test = {"Passed.", "FAIL!"}; /* 生成行列を表示 */ System.out.println("Generator matrix."); for(int i = 0; i < h.DATA_LEN ; i++) { StringBuffer sb = new StringBuffer(); int c = h.encode(1 << i).code; for(int b = h.BIT_MASK; b != 0; b >>= 1) sb.append((c & b) == 0 ? '0' : '1'); System.out.println((i) + ": " + sb.toString()); } /* 符号化と復号のテスト */ int test0 = 0; for(int i = 1; i < h.N2D ; i <<= 1) { data = random.nextInt() & h.DATA_MASK; code = h.encode(data).code; if(h.getSyndrome().correct().decode() != data) test0 |= 1; } System.out.println("test0: Encode and decode - " + test[test0]); /* 単一誤り訂正テスト */ int test1 = 0; for(int i = h.BIT_MASK; i > 0; i >>= 1) { data = random.nextInt() & h.DATA_MASK; h.encode(data).code ^= i; // add single error if(h.getSyndrome().correct().decode() != data) test1 |= 1; } System.out.println("test1: Single error correction - " + test[test1]); /* ２重誤り検出テスト */ int test2 = 0; for(int i = h.BIT_MASK; i > 1; i >>= 1) { for(int j = i >> 1; j > 0; j >>= 1) { data = random.nextInt() & h.DATA_MASK; h.encode(data).code ^= (i ^ j); // add double error if(h.getSyndrome().status >= 0) test2 |= 1; } } System.out.println("test2: Double error detection - " + test[test2]); /* 制御コード検出テスト */ int test3 = 0; final int controlCode[] = {0x0013, 0x0d53, 0x354c, 0x7fff}; for(int i = 0; i < 4; i++){ h.code = controlCode[i]; if(h.getSyndrome().syndrome != 0x13) test3 |= 1; } System.out.println("test3: Control code detection - " + test[test3]); /* バーストエラー訂正テスト */ h.burstErrorCorrection = true; int test4 = 0; for(int i = h.BIT_MASK; i > 1; i >>= 1) { data = random.nextInt() & h.DATA_MASK; h.encode(data).code ^= i ^ (i >> 1); // add 2 bit burst error if(h.getSyndrome().correct().decode() != data) test4 |= 1; } h.burstErrorCorrection = false; System.out.println("test4: Burst error correction - " + test[test4]); } }

参考文献

1. 符号理論, 今井秀樹, 電子情報通信学会, ISBN4-88552-090-8

関連項目

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