紛らわしい文字を含まない (5-char, 16-bit) 誤り訂正文字化符号


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

細田隆之
Nov. 8, 2004

16-bit の数を中国人剰余定理を利用して紛らわしい文字を含まないアルファベット^*List1 5 文字に符号化し、１文字誤り訂正、２文字誤り検出が可能な初歩的な誤り訂正文字化符号を考案した。

(5-char,16-bit) １文字誤り訂正、２文字誤り検出誤り訂正文字化符号

中国人剰余定理 (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:lyuka@finetune.co.jp
 */

#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) バースト誤り訂正符号などの方がましであるし、中国人剰余定理を用いた符号としても初歩的で復号方法も最適とは言えないが、アルファベットの文字列として符号化できるという点において、例えばバーコードなどと違い電話や印刷ででも伝えられるといったところに、適用箇所があるのではなかろうか。例えば、企業や省庁の長くなりがちな部署名の略号への適用等が考えられる。

追記

Charmsec^® 誤り訂正文字化符号に倣うと、ここで例示の (5-char, 16-bit) 符号で扱える数の範囲は [0, p1 * p2 * p3 - 1] までであるので、 p1 * p2 * p3 - 1 = 38 * 41 * 43 - 1 = 66993 (0x105b1) までとなり、情報エントロピーは ln(66993) / ln(2) ≃ 16.0317 bit となって 16-bit の情報に対して、約 0.317 bit 分の余剰情報エントロピーがある。つまり Charmsec^® でいうところの Super data として、 0x1000 – 0x105b1 の値を管理用などの別用途として用いることができる。

実は互いに素な数の組として {41, 43, 44, 45, 47} を選ぶと 41 * 43 * 44 - 1 = 77571(0x0x12f03) → 0.243… bit 分の余剰情報エントロピーとなって Charmsec^® 的にはもう少し Super data の範囲というかビット幅を増やせる。

履歴

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

(5-char,16-bit) １文字誤り訂正、２文字誤り検出 誤り訂正文字化符号

プログラム例

誤り訂正例

まとめ

追記

履歴

SEE ALSO

(5-char,16-bit) １文字誤り訂正、２文字誤り検出誤り訂正文字化符号