Charmsec® Error Correcting Characterization code.

Charmsec^®（Characterized Remainder Set Error Correcting code）符号は、筆者が考案した誤り訂正ブロック符号です。その数理的本質は剰余系ドメインから任意の離散シンボル空間への一般化された写像にあります。ここでは 7-bit ASCII の印字可能文字という制約された集合への写像としての適用例を示しています。

Charmsec はシンボル表現そのものには依存しないため、数理的には直交振幅変調のコンスタレーションや OFDM のサブキャリア、さらには量子状態といった、任意の離散的な次元や物理状態への拡張も可能です。

今回の ASCII への適用例では、数理マッピングの制約により印字不可能なコードが排除されています。そのため、物理層において電磁気的信号として扱われる場合には NUL (0x00) と DEL (0x7F) が除外されていることにより、連続同一符号の最大長が 12-bit 以内に制限されるため、スクランブラを使わなくても確実なクロック再生が可能です。

コード外の制御文字、例えば LF (0x0a)をデリミタとして利用するのを想定した場合に、その制御文字からのハミング距離が 1 の文字を、符号文字から除外することにより、1-bit誤り耐性のあるデリミタとして利用できます。

このデリミタをマクロな、たとえば複数のコードブロック構造のデリミタとして用いた場合には、同期ワードやその補足処理のオーバーヘッドなしで確実なブロック同期が実現できるため、 RS-232、RS-422、RS-485などの非同期シリアル通信だけでなく、独自の同期式バス通信にも広く応用が可能です。

また、情報エントロピーの余剰分（スーパーデータ）を利用することで、補助的なメタデータや独立した異種データを同一の符号空間に内包させるといった利用方法が考えられます。例えば、データストリーム中にタイムスタンプや各種の制御コードや、単発のあるいは別系統のデータを混在させることが可能となり、リアルタイム性と伝送効率が同時に要求される産業用ロボットや各種モビリティ（乗り物）の制御信号伝送などの低遅延システムに適しています。

印刷可能文字であるためロギングやメールへの添付も容易です。

実行時に必要なメモリリソースは 8 KB未満と軽量であるため、リソースの限られた組込み用プロセッサにも適しています。また、Charmsec における剰余系や多数決の演算は並列処理が可能であるため、FPGA や SoC への実装により、一層の高速化を図ることも可能です。

符号比較

符号文字のマッピング例

符号化と復号の例

Ｃ言語での実装例

▼ Charmsec7_5C 実装例 (クリックで展開します)

/** About this program
Charmsec7-5c : This program is a demonstration program for an error correcting characterization
code based on the Charmsec CoDec library Rev. 1.98, an example application of JP-A2021-202714.
This code is capable of correcting single-character errors. Charmsec is an error-correcting code
that uses the Chinese remainder theorem to encode information data into a set of characters -
especially ASCII characters.
http://www.finetune.co.jp/~lyuka/technote/charmsec/
*/

#include <stdint.h>
#include <inttypes.h>

/* Charmsec7 (9c, 44) */
#define NUM_COPRIME         9
#define DATA_LEN            44
#define NUM_SUBSET         (NUM_COPRIME - 2)
#define CHARMS_LEN         (NUM_COPRIME + 3)

typedef struct {
    uint64_t           status;
    uint64_t           data;
    char               code[CHARMS_LEN];
    const int          data_len;
    const uint64_t     data_mask;
    const int          charms_len;                       // Length of the code string encoded by Charmsec
    const int          num_coprime;                      // number of coprime numbers
    const int          num_subset;                       // number of subset of the coprime number set
    const uint64_t     coprime[NUM_COPRIME];             // coprimes
    const uint8_t      ascii_mask;
    const char         cmap[93];                         // charactor mapping table (92 characters + \0)
    const uint8_t      rmap[128];                        // charactor reverse mapping table
    const uint64_t     modmax[NUM_COPRIME];              // Maximum value of the modulus system
    const uint64_t     minmodmax;
    const uint64_t     invmat[NUM_COPRIME][NUM_COPRIME]; // Mudulus invert of the modulus system
    const uint64_t     corrected;                        // decode result flag : corrected
    const uint64_t     detected;                         // decode result flag : detected
    const uint64_t     superdata;                        // decode result flag : super code
    const char        *title;
    const char        *version;
    const char        *copyright;
} charms_t;

int          ischarms(char);
char        *encode(uint64_t);
uint64_t     decode(char *);

charms_t    charms = {
    .status            =  0,
    .data              =  0,
    .code              =  {0, 0, 0, 0, 0, 0, 0, 0, 0},
    .data_len          =  DATA_LEN,
    .data_mask         =  ~0UL >> (64 - DATA_LEN),
    .charms_len        =  CHARMS_LEN,
    .num_coprime       =  NUM_COPRIME,
    .num_subset        =  NUM_SUBSET,
    .coprime           = { 71,  73,  79,  83,  85,  87,  88,  89,  91},
    .ascii_mask        =  0x7f,
    /* Charmsec7-5c */
    .cmap              = "!\"#$%&'()+,-./0123456789:;<=>?@ABCDEFGHIKLMNOPQRSTUVWXYZ[]^_`abcdefghijklmnopqrstuvwxyz{|}~",
    .rmap = {\
        127, 127, 127, 127, 127, 127, 127, 127, \
        127, 127, 127, 127, 127, 127, 127, 127, \
        127, 127, 127, 127, 127, 127, 127, 127, \
        127, 127, 127, 127, 127, 127, 127, 127, \
        127,   0,   1,   2,   3,   4,   5,   6, \
          7,   8, 127,   9,  10,  11,  12,  13, \
         14,  15,  16,  17,  18,  19,  20,  21, \
         22,  23,  24,  25,  26,  27,  28,  29, \
         30,  31,  32,  33,  34,  35,  36,  37, \
         38,  39, 127,  40,  41,  42,  43,  44, \
         45,  46,  47,  48,  49,  50,  51,  52, \
         53,  54,  55,  56, 127,  57,  58,  59, \
         60,  61,  62,  63,  64,  65,  66,  67, \
         68,  69,  70,  71,  72,  73,  74,  75, \
         76,  77,  78,  79,  80,  81,  82,  83, \
         84,  85,  86,  87,  88,  89,  90, 127},
    .modmax             = { 22116033697560, 27722915480040, 34558702858680, 31059087379320, 27317028658920,\
                            25388767812408, 24221468142872, 23395736274365, 22869989391795},
    .minmodmax          = 0x0000141d4a551718,
    .invmat = { \
        { 9033309538440,  4544390485800,  3639347317320,  11457704204760,  9366790742496,  13981400613400,  14325158190465,  0,  0}, \
        { 0,  23545489859760,  12984150288120,  26720882390400,  14350685660256,  26129644475440,  27407882349585,  7475842376640,  0}, \
        { 0,  0,  9186490633320,  27480414321360,  33338983934256,  24230814648040,  1963562662425,  29122502409000,  12912042826320}, \
        { 15748269657120,  0,  0,  8232529184880,  8404223643816,  26418074322640,  4588274271945,  4187742118560,  25598148939000}, \
        { 1154240647560,  25071793426680,  0,  0,  5784782539536,  14443486417360,  19556509153545,  15039712407720,  900561384360}, \
        { 8224530418104,  21215271733656,  16068840387600,  0,  0,  16050370456120,  6058683227961,  20824494947256,  13112880078936}, \
        { 2388032070424,  8958625203528,  6438618113928,  6128323265064,  0,  0,  15688905501633,  14696171682192,  18365728591848}, \
        { 14498766141860,  16665455976260,  21026547790885,  3100639747205,  2477195605521,  0,  0,  15246659594530,  20567680241200}, \
        { 4509575373030,  15351088769835,  19975054025745,  15981438370170,  4843056577086,  20767001861515,  0,  0,  10052742589800}},
    /* decode status at bit 63..61 */
    .corrected         =  1ULL << 61,
    .detected          =  1ULL << 62,
    .superdata         =  1ULL << 63,
    .title             = "charmsec7_5c - a subset of the Charmsec CoDec library.",
    .version           = "Rev.1.98 (2026-07-17)",
    .copyright         = "(c) 2004 Takayuki HOSODA, Finetune co., ltd."
};

int ischarms(char c) {
    return charms.rmap[(int)c] == charms.ascii_mask ? 0 : charms.ascii_mask;
}

char * encode(uint64_t data) {
    int    i;
    if (data >= charms.minmodmax) data = (charms.minmodmax - 1UL);
    for (i = 0; i < charms.num_coprime; i++) {
        charms.code[i] = charms.cmap[data % charms.coprime[i]];
    }
    charms.code[i] = '\0';
    return charms.code;
}

/** decode() return value
no error   : data, superdata
corrected  : data, superdate | charms.corrected
detected   :                   charms.detected
*/
uint64_t decode(char *code) {
    int         i, j;
    uint8_t     a[NUM_COPRIME];
    uint64_t    b[NUM_COPRIME];
    uint64_t    data = 0;

    /* decompose code */
    for (i = 0; i < charms.num_coprime; i++) {
        a[i] = charms.rmap[(int)code[i] & charms.ascii_mask];
    }
    /* majority decision */
    /* subdecode 0 to 2 */
    for (i = 0; i < 3; i++) {
        /* subdecode */
        data = 0;
        /* mul-add in uint64_t followed by remainder calculation */
        for (j = 0; j < charms.num_coprime; j++) {
            data = data + a[j] * charms.invmat[i][j];
        }
        data %= charms.modmax[i];
        b[i] = data;
    }
    data = b[0];
    charms.status = charms.detected;
    if ((data == b[1]) && (data == b[2])) {
        charms.status = 0;
    } else {
        /* subdecode 3 to charms.num_coprime */
        for (i = 3; i < charms.num_coprime; i++) {
            /* subdecode*/
            data = 0;
            /* mul-add in uint64_t followed by remainder calculation */
            for (j = 0; j < charms.num_coprime; j++) {
                data = data + a[j] * charms.invmat[i][j];
            }
            data %= charms.modmax[i];
            b[i] = data;
        }
        data = b[0];
        /* compare adjacent data to find correct data. */
        if (data == b[charms.num_coprime - 1]) {
            charms.status = charms.corrected;
        } else {
            for (i = 0; i < charms.num_coprime - 1; i++) {
                if (b[i] == b[i + 1]) {
                    charms.status = charms.corrected;
                    data = b[i];
                    break;
                }
            }
        }
    }
    if (data > charms.data_mask) charms.status |= charms.superdata;
    return data;
}
#ifdef DEBUG
#include <stdio.h>
#ifndef PRIx64
#define PRIx64          "llx"      /* uint64_t */
#endif
const char    *myname  = "Charmsec7_5c_demo";
int main() {
    int        i, j;
    char       rxcode[CHARMS_LEN];
    char       rxdisp[CHARMS_LEN];
    uint64_t   rxdata, data;
    rxdata = 0UL;
    for (i = 0; i < charms.charms_len; i++) rxcode[i] = rxdisp[i] = '\0';
    printf("%s : %s %s\n", myname, charms.version, charms.copyright);
    printf("%s : Using %s\n", myname, charms.title);
    printf("%s : '\\' is to be used as the error position indicator here.\n", myname);
    for (i = 0; i < charms.charms_len; i++) rxcode[i] = '\0'; // initialize rxcode. Note that '\0' is not a Charmsec code charactor.
    data = 0xbadcafebabe; // A test data of 44-bit unsigned integer.
    printf("%s : txdata = 0x%015" PRIx64 " -> txcode = %s%s\n", myname, \
        data, encode(data), data > charms.data_mask ? data < charms.minmodmax - 1UL ? " (super data)" : " (saturated)" : "");
    for (j = 0; j < charms.num_coprime; j++) {
        for (i = 0; i < charms.charms_len; i++) rxcode[i] = charms.code[i];
        rxcode[j] = '\t'; // insert single character error. Note that '\t' is not a Charmsec code character.
        rxdata = decode(rxcode);
        for (i = 0; i < charms.num_coprime; i++) rxdisp[i] = ischarms(rxcode[i]) ? rxcode[i] : '\\';
        printf("%s : rxdata = 0x%015" PRIx64 " <- rxcode = %s%s - %s\n", myname, rxdata, rxdisp,
              charms.status & charms.superdata ? " (superdata)" : "",
              charms.status & charms.corrected ? "Corrected an error"
            : charms.status & charms.detected  ? "Unrecoverable error detected" : "No error");
    }
    data = charms.minmodmax - 1UL; // the maximum value for superdata
    printf("%s : txdata = 0x%015" PRIx64 " -> txcode = %s%s\n", myname, \
        data, encode(data), data > charms.data_mask ? data < charms.minmodmax - 1UL ? " (super data)" : " (saturated)" : "");
    for (j = 0; j < charms.num_coprime; j++) {
        for (i = 0; i < charms.charms_len; i++) rxcode[i] = charms.code[i];
        rxcode[j] = '\t'; // insert single character error. Note that '\t' is not a Charmsec code character.
        rxdata = decode(rxcode);
        for (i = 0; i < charms.num_coprime; i++) rxdisp[i] = ischarms(rxcode[i]) ? rxcode[i] : '\\';
        printf("%s : rxdata = 0x%015" PRIx64 " <- rxcode = %s%s - %s\n", myname, rxdata, rxdisp,
              charms.status & charms.superdata ? " (superdata)" : "",
              charms.status & charms.corrected ? "Corrected an error"
            : charms.status & charms.detected  ? "Unrecoverable error detected" : "No error");
    }
    return 0;
}
#endif

アーカイブのダウンロード : charmsec7_5c_demo-1.98.tar.gz [4kB tar.gz]

スーパーデータ利用例

Charmsec の特徴の一つであるスーパーデータを利用してデータストリームの合間に単発データや制御コードを送ったり、
またデータストリームの終了やチェックビットやタイムスタンプ等に利用することもできます。
下の図は Charmsec7 を RS-485 のマルチドロップでの装置・ロボット間通信に適用した場合の利用例です。

技術解説

あとがき

CRT による多数決誤り訂正は，互いに直交する n + 2t 個の単位ベクトルが与えられ、元の数がそれらとの内積によって得られる n 個の値の組として 1 + 2t 通りに表現可能である場合に、それらの復号結果に対する多数決により最大 t 個の誤りを訂正できるという考えに基づいている。

この数を分解してマッピングするという構造は、直交変復調や量子誤り訂正に関する将来の研究に対しても、何らかの示唆を与えるものであればと願う。

技術資料

特許公報特許第7142977号 — データ通信システム、送信装置、および受信装置

変更履歴

▼ 変更履歴（クリックで展開します）

2024/ 8/23 : Changed unsigned integers in C implementation examples to ISO C99 compliant (e.g. uint64_t)
2022/10/ 8 : Patent number is listed with the registration of the patent
2022/ 9/ 7 : Added C implementation example
2022/ 9/ 7 : Added technical explanation (excerpt from the patent specification)
2022/ 7/ 2 : Changed super data usage example
2021/12/17 : Code comparison table and super data usage examples are added
2021/12/18 : Encoding and error correction examples are added

Charmsec^® Error Correcting Characterization Code

概要

目次