巡回ハミング符号を実装してみた（JavaScript）

勉強したので習作。

1. 概念理解

解きたい課題1: 長さ4のビット列を転送したいのだが、転送中のノイズによりビット反転する可能性がある。そこで検査用に長さ3 のビット列を付け加え、全体で長さ 7のビット列を送信することにしよう。7 ビット中 1ビットのビット反転があったとしても、それを検知・訂正したい。

解きたい課題2: 長さ11のビット列を転送したいのだが、転送中のノイズによりビット反転する可能性がある。そこで検査用に長さ4 のビット列を付け加え、全体で長さ 15のビット列を送信することにしよう。15 ビット中 1ビットのビット反転があったとしても、それを検知・訂正したい。

解きたい課題3: 長さ $2^m - m - 1$ のビット列を転送したいのだが、転送中のノイズによりビット反転する可能性がある。そこで検査用に長さ $m$ のビット列を付け加え、全体で長さ $2^m - 1$のビット列を送信することにしよう。$2^m - 1$ ビット中 1ビットのビット反転があったとしても、それを検知・訂正したい。

イメージ図: m = 3 の場合

送信したいビット列:           1101
検査ビット列の付与:           1101001
-----送信--------------
ノイズによるビット反転:       1100001  (4番目のビットが反転)
-----受信--------------
検査:                       (誤りあり, 場所: 4)
訂正後のビット列             1101001
検査ビットの剥離             1101

以下、m = 3 の場合のみを考える

2. エンコード

例えば、送信したいビット列 1101 に検査用のビット列をつけて 1101001 にしたい。くっつける 3ビット長のビット列（この場合は 001）をどう生成する？以下がその処方:

1. 入力を 3ビットシフトする: 1101 ----> 1101000
2. それを魔法の数字 1011 で割って余りを求める（注: 2を法とした除算）
3. その余りが求めたいビット列

まずは、2を法とした除算を実装しよう。そもそも2を法とした除算というのを説明するのが難しいのだが 例えば、ここ（外部の個人サイト） がわかりやすそう。104 を 11 で割った余りが 5 ではなく 1 になる。どう実装すればよいのかわからなかったので定義に従って不格好に実装:

// 一番左端の1 が後ろから数えて何番目にあるか: 000110 なら 2
function findFirstNonZeroIdx (num, bufLen) {
  let tmp = 1 << (bufLen - 1);
  for (let i = 0; i < bufLen; i += 1) {
    if (num & tmp) {
      return bufLen - i - 1;
    }
    tmp = tmp >> 1;
  }
  return -1; // num === 0
}

// 2を法とした余り a % b
function amari (a, b, bufLen) {
  const idxB = findFirstNonZeroIdx(b, bufLen);
  let val = a;
  for (;;) {
    const idx = findFirstNonZeroIdx(val, bufLen);
    if (idx < idxB) return val;
    val = val ^ (b << (idx - idxB));
  }
}

console.log(104 % 11, amari(104, 11, 7)); // -> 5, 1

あとは処方に従って encode 関数を実装:

const A = parseInt('1011', 2);

// エンコーダー
function encode(num) {
  const shifted = num << 3;
  return shifted + amari(shifted, A, 7);
}

console.log(encode(parseInt('1101', 2)).toString(2)); // -> 1101001

考えられる入力はたった16 パターンしかないので全部書いておく（実際にはこれを記憶してエンコーダにするのがよいかも知らん）:

for(let i = 0; i < 16; i++) {
  const X = i.toString(2).padStart(4, '0');
  const Y = encode(i).toString(2).padStart(7, '0');
  console.log(`${X} -> ${Y}`);
}
/*
0000 -> 0000000
0001 -> 0001011
0010 -> 0010110
0011 -> 0011101
0100 -> 0100111
0101 -> 0101100
0110 -> 0110001
0111 -> 0111010
1000 -> 1000101
1001 -> 1001110
1010 -> 1010011
1011 -> 1011000
1100 -> 1100010
1101 -> 1101001
1110 -> 1110100
1111 -> 1111111
*/

3. デコード

7ビットの符号を受信したら、以下の処方で復号する

1. シンドロームの計算
2. シンドローム値に応じて誤り訂正

エンコード時に使った魔法の数字が 1101 ならば、デコード時には魔法の配列 [1, 2, 4, 3, 6, 7, 5] を使う。魔法の配列はシンドロームの計算の時にも使うし、誤り訂正時にも使う。

シンドロームの計算法：シンドロームの初期値を0 にする。受信ビット列の下から i番目が1 だったら、魔法の配列の i番目の数字をシンドロームに XOR する。それを全ての i について繰り返す。

誤り訂正法: 得られたシンドローム値は、0でない限り魔法の配列の a 番目に一致するはず。その a こそがビット反転箇所＝エラー箇所となる。0の場合はエラーが起きなかったといえる。

以上をまとめると以下のように実装できる:

const B = [1, 2, 4, 3, 6, 7, 5];
function decode (num) {
  // シンドロームの計算
  let syn = 0;
  for (let i = 0; i < 7; i += 1) {
    if ((1 << i) & num) {
      syn = syn ^ B[i];
    }
  }
  // シンドロームから誤り訂正
  if (syn === 0) { // no error
    return num >> 3;
  }
  const loc = B.findIndex(x => x === syn);
  return (num ^ (1 << loc)) >> 3;
}

// 1010 -> 1010011 -> (エラー) -> 1000011 -> (訂正) -> 1010
console.log(decode(parseInt('1000011',2)).toString(2)); // -> 1010

4. 動作確認

入力が 4bit なので、16種類しかなく、それぞれの符号語に対して 1種類の正常系と 7種類の異常系しかない（想定しない）ので、全部でもテストケースは 128 通りしかない。すべてのケースで符号化・復号ができることを確認するのは簡単:

const range = end => [...Array(end).keys()];

function check(num) {
  const word = encode(num);
  // 誤りなく転送できた時に復号できることを確認
  if (num !== decode(word)) {
     return false;
  }
  // 想定される 7つのビット反転ケースに対して復号できることを確認
  return range(7).every(loc => decode(word ^ (1 << loc)) === num);
}

// 任意の入力について確認
console.log(range(1 << 4).every(check)); // -> true

5. 雑記

回路での実装: 巡回ハミング符号は通信路符号化という特性上、プログラミング言語上での実装よりも、ハードウェア（回路）での実装方法を考えることが大事。この個人ブログでは、それについて簡潔な説明を行っている（が私はまだ内容を詳細に追ってはいない）

魔法の数字・魔法の配列: 魔法の数字は生成多項式のビット表現。魔法の配列は、検査行列のビット表現（プログラミングに親和させるために、列の順序を逆にした）

やり残し: 2を法とした除算は絶対もっと簡単なビット演算に落とし込めるはず。汎用的な話なので調べたい。