0x944a → "Aqpdk"
            ↓
           "Aqbdk" → 0x944a 

中国人剰余定理 (Chinese remainder theorem) ^[1] によると正整数 m は m < Π_i=1^k である 互いに素な数 p₁ .. p_k の剰余の組で 一意に表される。 これに互いに素な数 p_k < p_{k + 1} < p_{k + 2} を 2 つ追加して m を k + 2 個の剰余で表すように冗長性を持たせると、 1 つの剰余に誤りがあった場合に k + 2 個中の k 個の剰余から逆算され得る _{k + 2}Ｃ_k 個の正整数のうち _{k + 1}Ｃ_{k - 1} 個は互いに異なった ものとなるが _{k + 1}Ｃ_k 個は同一となるため 多数決により誤り訂正が可能となる。また 2 つの剰余に誤りがあった場合には 逆算した結果が全て異なるため誤り検出も可能である。

まず 16-bit の数を 3 つの剰余にしてそれを文字で表すためには 1 文字あたり約 5.4-bit 程度の情報量が必要で、 p₁ < p₂ < p₃ < p₄ < p₅ とすると

2¹⁶ <= p₁ * p₂ * p₃ …(1)

である必要がある。 各剰余をアルファベットで表すとすると大文字と小文字で 52 文字なので

p₅ <= 52 …(2)

である必要がある。(1), (2) の条件を満たす互いに素な数の組はいくつかあるが、 アルファベットから紛らわしい文字 {I, O, i, l, o} を除いた 47 文字 (List1)でも 実現可能な互いに素な数の組 {38, 41, 43, 45, 47} が見付かったのでこれを使用することにする。

List1 [紛らわしい文字 (I, O, i, l, o) を含まないアルファベット]

ABCDEFGHJKLMNPQRSTUVWXYZabcdefghjkmnpqrstuvwxyz

例として元のデータの値が 0xcafe とすると、これは剰余の組として {20, 19, 22, 36, 31} と表され、これを List1 により文字変換して "WVYph" となる。 この文字列が 1 文字誤って例えば "sVYph" となった場合には、隣り合う 3 つの剰余から 計算される値は {0x4825, 0xcafe, 0xcafe, 0x2e05, 0x3bf9} となる。この中で同一のものが 2 つあればそれを選び単一文字誤り訂正とする。 この場合、第２項と第３項が同じで 0xcafe となり訂正が確認できた。 List2 にＣプログラム例を示す。

List2 [Ｃプログラム例 (単一文字誤りテスト)]

/* crtecc: modulous error correction code test program v.0.2 Nov. 7, 2004 * Copyright (c) 2004, Hosoda Takayuki. All rights reserved. * * This program demonstrates an error correction code utilizing the * chinese remainder theorem, which encodes 16-bit information data * to a set of five ASCII charactors. This code is capable to correct * single charactor error, and to detect two charactor errors. * * http://www.finetune.co.jp/~lyuka/ mailto:[email protected] */ #include <stdio.h> #include <stdlib.h> #include <math.h> #include <string.h> #define NUM_VECT 5 #define NUM_SET 3 #define BIT_MASK 0x40000000L #define DATA_LEN 16 #define DATA_MASK 0x0000ffffL #define N2D 0x00010000L long vect[NUM_VECT] = {38, 41, 43, 45, 47}; long vmax[NUM_VECT] = {66994, 79335, 90945, 80370, 73226}; long inv[NUM_VECT][NUM_SET] = {{58179, 55556, 20254}, {69660, 59040, 29971}, {57105, 22231, 11610}, {74025, 28576, 58140}, {59737, 44650, 42066}}; int vsel[NUM_VECT][NUM_SET] = {{0, 1, 2}, {1, 2, 3}, {2, 3, 4}, {0, 3, 4}, {0, 1, 4}}; char *cmap = "ABCDEFGHJKLMNPQRSTUVWXYZabcdefghjkmnpqrstuvwxyz0123456789@=+-/*#"; char tmap[128]; void init() { extern char tmap[]; extern char *cmap; int i; for (i = 0; i < 128; i++) tmap[i] = '?'; for (i = 0; i < 64; i++) tmap[(int)cmap[i]] = i; } long encode(d) long d; { long code; extern long vect[]; d &= DATA_MASK; code = (((d % vect[0])) | ((d % vect[1]) << 6) | ((d % vect[2]) << 12) | ((d % vect[3]) << 18) | ((d % vect[4]) << 24)); return code; } long decode(code) long code; { int i, j; long d, data; long a[NUM_VECT]; long b[NUM_VECT]; for (i = 0; i < NUM_VECT; i++) a[i] = ((code >> (6 * i)) & 0x3f); for (i = 0; i < NUM_VECT; i++) { d = 0; for (j = 0; j < NUM_SET; j++) d = (d + (a[vsel[i][j]] * inv[i][j]) % vmax[i]) % vmax[i]; b[i] = d; } if ((b[0] ^ b[1] ^ b[2] ^ b[4]) == 0) { data = b[0]; } else { if (b[0] == b[1]) { data = b[0]; } else if (b[2] == b[3]) { data = b[2]; } else if (b[1] == b[2]) { data = b[1]; } else if (b[3] == b[4]) { data = b[3]; } else if (b[4] == b[0]) { data = b[4]; } else { data = 0xffffffffL; } data |= 0x80000000L; } return data; } char * bin2text(code, s) long code; char *s; { int i; extern char *cmap; for (i = 0; i < NUM_VECT; i++) s[i] = cmap[(code >> (6 * i)) & 0x3f]; s[NUM_VECT] = '\0'; return s; } long text2bin(text) char *text; { int i; long code; extern char tmap[]; code = 0; for (i = 0; i < NUM_VECT; i++) code |= ((long)tmap[(int)text[i]]) << (6 * i); return code; } #define MAX_TEST 10 int main(argc, argv) int argc; char *argv[]; { int i, ecount; long data, code, ecode, cdata; char txstr[NUM_VECT + 1]; char rxstr[NUM_VECT + 1]; init(); ecount = 0; for (i = 0; i < MAX_TEST; i++) { data = random() & DATA_MASK; code = encode(data); bin2text(code, txstr); strncpy(rxstr, txstr, NUM_VECT + 1); rxstr[(int)(random() % NUM_VECT)] ^= (random() & 0x3f); ecode = text2bin(rxstr); cdata = decode(ecode); printf("data = 0x%04lx, code = %s, ", data, txstr); printf("code+error = %s, ", bin2text(ecode, rxstr)); if (cdata != 0xffffffffL) { if (cdata & 0x80000000L) { cdata &= ~0x80000000L; /* clear error flag */ printf("data = 0x%04lx(corrected)\n", cdata); } else { printf("data = 0x%04lx(no error)\n", cdata); } } else { printf("data = 0x%04lx(unrecoverble)\n", cdata); ecount++; } } printf("%d of %d SEC test passed.\n", MAX_TEST - ecount, MAX_TEST); return ecount; }

Download : crtecc-0.2.tar.gz
MD5 (crtecc-0.2.tar.gz) = 2329550516d260a76278fea5da41197e

誤り訂正例

List3 [プログラム実行例]

data = 0x4567, code = XQJqB, code+error = XxJqB, data = 0x4567(corrected) data = 0x4873, code = DRQHf, code+error = DRQwf, data = 0x4873(corrected) data = 0x944a, code = Aqpdk, code+error = AqYdk, data = 0x944a(corrected) data = 0x7ccd, code = fLAxp, code+error = fLjxp, data = 0x7ccd(corrected) data = 0x41f2, code = LhcHK, code+error = LhcHh, data = 0x41f2(corrected) data = 0xe146, code = aaHbB, code+error = caHbB, data = 0xe146(corrected) data = 0x0854, code = EAbTT, code+error = EZbTT, data = 0x0854(corrected) data = 0xe9e8, code = gWagC, code+error = gW#gC, data = 0xe9e8(corrected) data = 0x0f76, code = GYCwL, code+error = #YCwL, data = 0x0f76(corrected) data = 0x7263, code = ZKAkC, code+error = ZK#kC, data = 0x7263(corrected) 10 of 10 SEC test passed.

まとめ

１文字誤りの符号語から 16-bit のデータへの誤り訂正復号が確認できた。 この符号の場合 16-bit のデータが 5 文字 30-bit 相当の文字列になるわけで、単純に 符号化率や誤り訂正能力で考えた場合 (28, 16, l=6) とか (48, 32, l=8) バースト誤り訂正符号などの 方がましであるし、中国人剰余定理を用いた符号としても初歩的で復号方法も 最適とは言えないが、アルファベットの文字列として符号化できるという点に おいて、例えばバーコードなどと違い電話や印刷ででも伝えられるといったところに、 適用箇所があるのではなかろうか。 例えば、企業や省庁の長くなりがちな部署名の略号への適用等が考えられる。

履歴

Jun. 22, 2022 : タイトル・表示等変更
Feb. 13, 2016 : 誤記修正
Aug. 31, 2014 : 誤記修正

SEE ALSO

1. Charmsec™ 誤り訂正文字化符号
2. 中国人剰余定理を利用した剰余系による数値計算法の例