紛らわしい文字を含まない誤り訂正文字化符号

{38, 41, 43, 45, 47}

ABCDEFGH JKLMN PQRSTUVWXYZ
abcdefgh jk mn pqrstuvwxyz

/* 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;
}

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 相当^*note1 の文字列になるわけで、単純に 符号化率や誤り訂正能力で考えた場合 (28, 16, l=6) とか (48, 32, l=8) バースト誤り訂正符号などの 方がましであるし、中国人剰余定理を用いた符号としても初歩的で復号方法も 最適とは言えないが、アルファベットの文字列として符号化できるという点に おいて、例えばバーコードなどと違い電話や印刷ででも伝えられるといったところに、 適用箇所があるのではなかろうか。

履歴

2026-07-27 : html5/css 化、加筆修正
2025-01-06 : 追記
2022-06-22 : タイトル・表示等変更
2016-02-13 : 誤記修正
2014-08-31 : 誤記修正
2004-11-08 : 初版

追記

Charmsec^® への発展

本稿から発展した、Charmsec^® 誤り訂正文字化符号 に倣うと、 crtecc で例示の (5-char, 16-bit) 符号で扱える数の範囲は [0, p₁ × p₂ × p₃ - 1] までであるので、 p₁ × p₂ × p₃ - 1 = 38 × 41 × 43 - 1 = 66993 (0x105b1) までとなり、 情報エントロピーは ln(66993) / ln(2) ≃ 16.0317 bit となって 16-bit の情報に対して、 約 0.0317-bit 分の余剰情報エントロピーがある。

つまり Charmsec でいうところの Super-data として、0x1000–0x105b1 の値を管理用などの別用途として用いることができる。

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

紛らわしい文字を含まない英数字セット

List1 では、紛らわしい文字を含まないアルファベット として 47文字を選んだが、{w, W}, {x, X} など手書きでは紛らわしくなりやすい文字がまだ含まれている。

その対策として、アルファベットに数字を加え、手書きの時に紛らわしくなる文字の組の中、例えば
{0, C, c, O, o}, {1, I, i}, {j, i}, {2, Z, z}, {6, b}, {8, B}, {U, V}, {w, W}, {X, x}
では、数字を優先で選んで制限した次のような 47種の英数字セットの利用も考えられる。

0123456789
A  DEFGH  KLMN PQR TUV XY 
a cdefgh jk mn pqrstu w y 

関連項目

オンライン・デモンストレーション

• Charmsec^® (9c,44) Error Correcting Characterization Code Online Demonstration
• Charmsec^® (8c,38) Error Correcting Characterization Code Online Demonstration
• Charmsec^® (7c,32) Error Correcting Characterization Code Online Demonstration
• CRTECC-AN (5c,16) Error Correcting Characterization Code Online demonstration
• CRTEC (5c,16) Error Correcting Characterization Code Online demonstration

アーティクル

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

参考文献

1. 宮川 洋, 岩垂 好裕, 今井 秀樹 共著, 符号理論（コンピュータ基礎講座 18）, 電子情報通信学会 編, コロナ社, 1973年, ISBN4-88552-180-7.