|
この符号は符号文字中の文字単位での誤りを許容して復号することができます。下記実装例では 1 文字の誤りに対処出来ます。
情報エントロピーの余剰分を利用して、データ長の大きさを超えて扱える範囲の数（スーパーデータ）があります。
下記の実装例では LF (0x0a) を 1-bit 誤り訂正付きのコードデリミタとして使用可能です。
RS-232, RS-422, RS-485 のような非同期シリアル通信での装置やデバイス間通信に適しています。
実時間性と伝送効率が同時に要求される分野（e.g. 産業ロボットや乗り物の制御信号の伝送）に適しています。
印刷可能文字であるためロギングやメールへの添付も容易です。
必要なリソースは 8 k byte 程度ですので、比較的小規模のシステムにも実装が容易です。
Charmsec™ 符号はいくつかありますが、実用上ポピュラーなものを次に紹介します。
Charmsec の符号文字の 7-bit ASCII コードへのマッピング例 (デリミタ : LF, 除外文字 : ∖)
Note 1 : NL (0x0A) の 1-bit 誤りは符号文字にならないようにマッピングしてあるので、 NL を 1-bit 誤り訂正付きのコードブロックデリミタとして利用できます。
Note 2 : ∖ (0x5C) も符号文字から除外してあるため、∖ を誤り位置インジケータ等に利用できます。
Charmsec7_5C １文字誤り訂正文字化符号
44-bit のデータを 9-char の ASCII 文字列に符号化します。除外文字は ∖ です。
符号化率は約 0.698 です。 Base64 に対しては、約 22 % の符号文字の増加となります。
符号化と復号の例
▼ 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.9, 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 <sys/types.h> #include <sys/stdint.h> #include <inttypes.h> #include <string.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 { u_int64_t status; u_int64_t data; char code[CHARMS_LEN]; const int data_len; const u_int64_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 u_int64_t coprime[NUM_COPRIME]; // coprimes const u_int8_t ascii_mask; const char cmap[92]; // charactor mapping table const u_int8_t rmap[128]; // charactor reverse mapping table const u_int64_t modmax[NUM_COPRIME]; // Maximum value of the modulus system const u_int64_t minmodmax; const u_int64_t invmat[NUM_COPRIME][NUM_COPRIME]; // Mudulus invert of the modulus system const u_int64_t corrected; // decode result flag : corrected const u_int64_t detected; // decode result flag : detected const u_int64_t superdata; // decode result flag : super code const char *title; const char *version; const char *copyright; } charms_t; int ischarms(char); char *encode(u_int64_t); u_int64_t decode(char *); charms_t charms = { .status = 0, .data_len = DATA_LEN, .data_mask = ~0UL ^ -(1UL << DATA_LEN), .charms_len = CHARMS_LEN, .num_coprime = NUM_COPRIME, .num_subset = NUM_SUBSET, .ascii_mask = 0x7f, /* Charmsec7-5c */ .cmap = "!\"#$%&'()+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[]^_`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, 40, 41, 42, 43, 44, 45,\ 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 127, 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, 91, 127}, .coprime = { 71, 73, 79, 83, 85, 87, 88, 89, 91}, .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}}, .title = "charmsec7_5c - a subset of the Charmsec CoDec library.", /* decode status at bit 63..61 */ .corrected = 1UL << 61, .detected = 1UL << 62, .superdata = 1UL << 63, .version = "Rev.1.92 (Jun. 12, 2022)", .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(u_int64_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 */ u_int64_t decode(char *code) { int i, j; u_int8_t a[NUM_COPRIME]; u_int64_t b[NUM_COPRIME]; u_int64_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 u_int64_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 u_int64_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> const char *myname = "Charmsec7_5c_demo"; charms_t charms; int main() { int i, j; char rxcode[CHARMS_LEN]; char rxdisp[CHARMS_LEN]; u_int64_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.92.tar.gz [4kB tar.gz]
スーパーデータ利用例
Charmsec™ の特徴の一つであるスーパーデータを利用してデータストリームの合間に単発データや制御コードを送ったり、
またデータストリームの終了やチェックビットやタイムスタンプ等に利用することもできます。
下の図は Charmsec7 を RS-485 のマルチドロップでの装置・ロボット間通信に適用した場合の利用例です。
技術解説
▼ 特許明細書より抜粋（クリックで展開します）【発明の名称】データ通信システム、送信装置、および受信装置 【技術分野】 【０００１】 本発明は、誤り訂正が可能な通信システムに関する。 【背景技術】 【０００２】 データの伝送が文字やバイト単位で行われる通信媒体を用いるデジタルデータ伝送にお いて、デジタルデータを印字可能な文字に変換して伝送するコーデック（符号化／復号） が用いられている（例えば電子メールにおけるＭＩＭＥ ＢＡＳＥ６４コーデック）。こ のようなコーデックにおいて、デジタルデータに冗長度を付加した誤り訂正符号に変換し 、それを印字可能な文字の組に再変換して送信し、受信した文字の組を誤り訂正符号に変 換して復号し伝送時に文字に生じた誤りの影響を除去することによってデジタルデータを 回復することができる。 【発明の概要】 【発明が解決しようとする課題】 【０００３】 しかしながら、上述のようなコーデックでは、誤り訂正符号化と文字化が別々に行われ るため、伝送時に文字に生じる誤りが文字からの変換時に拡大することがある。また、符 号化にも文字化にも冗長度が必要なために符号化率が低く、符号化率を改善しようとする と１つの伝送単位が大きくて伝送処理遅延が大きくなってしまう。また、符号の区切りを 知るための同期ワードや伝送サイズなどの付帯情報を必要としフレーム構造や情報ヘッダ ーなどの特別なしくみが必要である。このようなコーデックは信頼性と実時間性と伝送効 率が同時に要求される分野（例えば産業ロボットや乗り物の制御信号の伝送）には利用困 難であった。 【０００４】 上記の課題に鑑み、本発明は、データの伝送単位が比較的小さく、符号の区切りを知る ことが容易で、伝送時の誤りの影響を除去しうる、高符号化率のコーデックが適用された 通信システム、送信装置、および受信装置を提供することを目的とする。 【課題を解決するための手段】 【０００５】 上記の従来技術の欠点の本質は、言い換えれば伝送用の文字の持つ情報エントロピーを 全く活用出来ていないことに起因している。そのことに鑑み、本発明では、誤り訂正符号 化と文字化を合わせて行うこと、つまり印字可能な文字種の組み合わせとして実現できる 数の表現方法と、その情報エントロピーが大となる組み合わせを選ぶことで解決する。 【０００６】 本発明の実施形態に係るデータ通信システムは、送信装置と受信装置とを備え、送信装 置から受信装置へ、デジタルデータを誤り訂正可能に伝送する。送信装置は、予め定めら れた複数のコプライムで構成されるコプライムセットに基づいて、予め定められた情報ビ ットのビット数を有するデジタルデータについて、コプライムセットを構成するコプライ ムのそれぞれを除数として得られる複数の剰余の組である剰余数系を算出する剰余数系算 出部と、剰余系算出部が算出した剰余数系に含まれる個々の剰余を、予め定められた変換 マップＭに基づいて、印刷可能な文字である符号文字に変換することにより、剰余数系を 符号文字により構成される文字列に変換するマッピング処理部と、を備える。受信装置は 、送信装置から受け取った文字列を、変換マップに基づいて逆変換し、剰余数系を復元す るマッピング解除部と、剰余数系算出部で剰余数系を算出するのに用いたものと同じ予め 定められた複数のコプライムとマッピング解除部が復元した剰余数系とに基づいて、デジ タルデータを復号するデータ復号部とを備える。コプライムセットは、ｎ＋ｒ（ただしｒ ≧１）個のコプライムにより構成され、情報ビットのビット数で表されるデジタルデータ を、コプライムセットを構成するコプライムのうち下位ｎ個のコプライムによる剰余の組 により一意に表すことができるように定められる。 【０００７】 本発明では、コプライムセットを構成するコプライムのうち下位ｎ個のコプライムによ る情報エントロピーの整数部分を情報ビットの伝送に利用し、小数部分に相当する余剰分 を主情報以外の情報の伝送に利用するとよい。 【０００８】 本発明では、送信装置から受信装置に、予め定められた符号語間の分離用のデリミタ文 字を伝送可能に構成され、変換マップは、デリミタ文字の１ビット誤りになる文字を符号 文字に用いないようにするとよい。 【０００９】 本発明の実施形態に係る送信装置は、予め定められた複数のコプライムで構成されるコ プライムセットに基づいて、予め定められた情報ビットのビット数を有するデジタルデー タについて、コプライムセットを構成するコプライムのそれぞれを除数として得られる複 数の剰余（以下、シンボルと呼ぶ場合がある）の組である剰余数系を算出する剰余数系算 出部と、剰余系算出部が算出した剰余数系に含まれる個々の剰余を、予め定められた変換 マップＭに基づいて、印刷可能な文字である符号文字に変換することにより、剰余数系を 符号文字により構成される文字列に変換するマッピング処理部と、を備える。 【００１０】 本発明では、コプライムセットを構成するコプライムのうち下位ｎ個のコプライムによ る情報エントロピーの整数部分を情報ビットの送信に利用し、小数部分に相当する余剰分 を主情報以外の情報の送信に利用するとよい。 【００１１】 本発明では、送信装置から受信装置に、予め定められた符号語間の分離用のデリミタ文 字を伝送可能に構成され、変換マップは、デリミタ文字の１ビット誤りになる文字を符号 文字に用いないようにするとよい。 【００１２】 本発明の実施形態に係る受信装置は、上記の何れかの送信装置により符号化された、符 号文字により構成される文字列を受信して復号する。受信装置は、送信装置から受け取っ た文字列を、変換マップに基づいて逆変換し、剰余数系を復元するマッピング解除部と、 剰余数系算出部で剰余数系を算出するのに用いたものと同じ予め定められた複数のコプラ イムとマッピング解除部が復元した剰余数系とに基づいて、デジタルデータを復号するデ ータ復号部とを備える。 【図面の簡単な説明】 【００１３】 【図１】データ通信システム１の構成を示すブロック図である。 【図２】７−ｂｉｔ ＡＳＣＩＩコードの文字コード表を示す。 【図３】変換マップＭの一例を示す。 【発明を実施するための形態】 【００１４】 以下、本発明の実施形態を図面に基づいて説明する。なお、以下の説明では、同一の部 材には同一の符号を付し、一度説明した部材については適宜その説明を省略する。また、 以下の説明では互いに素な数のことをコプライムと呼ぶ。 【００１５】 〔ハードウェアの概略構成〕 図１は、本実施形態に係るデータ通信システム１の構成を示すブロック図である。図１ に示すように、データ通信システム１は、送信装置２と、受信装置３とを備える。送信装 置２と受信装置３とは、有線または無線の通信路により通信可能に接続されている。 【００１６】 送信装置２は、送信データｄｔｘを誤り訂正可能に符号化して、受信装置３に送信する 。送信データｄｔｘは送信装置２の内部で生成されてもよいし、外部から与えられてもよ いが、予め定められた情報ビット数を単位として、符号化される。図１に示すように、送 信装置２は、剰余数系算出部２１、マッピング処理部２２、及び送信部２３を備える。 【００１７】 剰余数系算出部２１は、複数のコプライムのそれぞれを除数、送信データｄｔｘを被除 数として得た、コプライムの数に応じた数の剰余の組（以下、この剰余の組を剰余数系と という）を算出する。中国人剰余定理 (Chinese remainder theorem) によるとコプライ ムの総乗未満の正整数ｘは、各コプライムによる剰余の組で一意に表される。この性質を 利用し、剰余数系算出部２１が算出する剰余数系は、送信データｄｔｘを一意に表すこと ができる。剰余数系算出部２１で剰余数系を算出するために用いる複数のコプライムの組 を、コプライムセットＣｓｅｔと呼ぶ。コプライムセットＣｓｅｔの選択については後に 詳述するが、コプライムセットＣｓｅｔは、一度に送信できる情報ビット数を表すのに必 要なコプライムよりも多くのコプライムを含み、この冗長なコプライムによる剰余を剰余 数系に含めることで誤り訂正可能な符号化を実現する。 【００１８】 マッピング処理部２２は、剰余数系算出部２１が算出した剰余数系に含まれる個々の剰 余を、予め定められた変換マップＭに基づいて、符号文字に変換する。変換マップＭは、 剰余と印刷可能な文字とを１対１に割り当てる。変換マップＭについては後に詳述するが 、符号文字には、例えば図２に示す７−ｂｉｔ ＡＳＣＩＩコードなどの文字コード表に おける印刷可能な文字を用いるとよい。送信データｄｔｘは、剰余数系算出部２１および マッピング処理部２２での処理を経て、剰余数系を表す文字列に変換される。この文字列 の個々の文字は、コプライムセットＣｓｅｔに含まれる個々のコプライムを除数とした剰 余を表している。 【００１９】 送信部２３は、無線または有線によるデータ送信を実現する。送信部２３は、マッピン グ処理部２２が出力する文字列を、符号化された送信データｄｔｃｏｄｅとして、受信装 置３に送信する。 【００２０】 受信装置３は、送信装置２からの符号化された送信データを受信し、これを復号して、 送信装置２が送信した元のデータを得る。図１に示すように、受信装置３は、受信部３１ 、マッピング解除部３２、及びデータ復号部３３を備える。 【００２１】 受信部３１、無線または有線によるデータ受信を実現する。受信部３１は、送信部２３ から送信される符号化された送信データを受信し、マッピング解除部３２に供給する。 【００２２】 受信部３１からマッピング解除部３２に供給される符号化された送信データは、符号文 字により構成された文字列である。マッピング解除部３２は、この文字列を、マッピング 処理部２２で用いる変換マップＭと同じマップを用いて逆変換し、剰余数系を復元する。 すなわち、マッピング解除部３２は、符号化された送信データである文字列の個々の文字 を、変換マップＭを用いて剰余を表す数に変換し、剰余数系を復元する。マッピング解除 部３２は復元した剰余数系をデータ復号部３３に供給する。 【００２３】 データ復号部３３は、剰余数系算出部２１で剰余数系を算出するのに用いたものと同じ コプライムセットＣｓｅｔとマッピング解除部３２が復元した剰余数系とに基づいて、既 知の中国人剰余定理の解法アルゴリズムにより受信データｄｒｘを算出する。このとき、 コプライムセットＣｓｅｔの冗長性により、コプライムセットＣｓｅｔと剰余数系は、受 信データｄｒｘを算出するために必要な数を超える、冗長なコプライムおよび冗長な剰余 を含んでいる。データ復号部３３は、コプライムおよび剰余について複数通りの組み合わ せで受信データｄｒｘを算出し、複数の受信データｄｒｘを算出する。通信過程でエラー が生じていなければデータ復号部３３で算出されるすべての受信データｄｒｘは同じ値と なるので、その値を最終的な受信データｄｒｘとする。 【００２４】 伝送中に、許容可能なビット数の以下のエラーが生じていた場合には、エラーの影響を 受けていない剰余のみを組み合わせて算出される受信データｄｒｘは共通の値となり、エ ラーの影響を受けた剰余を含む剰余の組み合わせにより算出される受信データｄｒｘは、 他の組み合わせから算出される受信データｄｒｘとは異なる値となる。したがって、多数 決により、エラーの影響を受けていない剰余のみを組み合わせて算出される受信データｄ ｒｘを、最終的な受信データｄｒｘとする。 【００２５】 伝送中に、許容可能なビット数を超えるエラーが生じていた場合には、データ復号部３ ３で算出される受信データｄｒｘはすべて互いに異なる値となり、多数決により受信デー タｄｒｘを得ることができない。この場合、受信装置３は、送信装置２にデータの再送信 を要求する等、正しいデータを受信するための事後処理を行う。 【００２６】 このような構成により、本実施形態に係るデータ通信システム１は、送信装置２と受信 装置３との間で、誤り訂正可能な通信を実現する。 【００２７】 上述のように送信装置２と受信装置３により構成されるデータ通信システム１において 、送信装置２と受信装置３は共通の変換マップＭとコプライムセットＣｓｅｔを持ち、そ れぞれにおける処理に利用する。以下で説明する変換マップＭとコプライムセットＣｓｅ ｔを利用することで、本発明のデータ通信システムの作用効果が実現される。 【００２８】 〔変換マップ〕 変換マップＭは、送信データｄｔｘを被除数、コプライムセットＣｓｅｔに属する各コ プライムＣを除数としたときの剰余を、符号文字に変換するための変換マップであり、剰 余と文字とが１対１に割り当てられている。この変換マップＭに用いる符号文字には、７ −ｂｉｔ ＡＳＣＩＩコードなどの文字コード表における印刷可能な文字を用いることが できる。図２に示した７−ｂｉｔ ＡＳＣＩＩコードの文字コード表において、印刷可能 な文字は、「!"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcd efghijklmnopqrstuvwxyz{|}~」の９４文字（図２において、網掛けが付されていない文字 ）である。したがって、符号文字として７−ｂｉｔ ＡＳＣＩＩコードの印刷可能な文字 を用いる場合にコプライムセットＣｓｅｔに含まれる最大のコプライムＣの値は９４とな る。剰余と文字の割り当ては任意であるが、特に断りのない限り、印刷可能なＡＳＣＩＩ コードの値が小さい方から順に剰余を表す数を割り当てるとよい。なお、当然のことなが ら７−ｂｉｔ ＡＳＣＩＩコード以外の文字コードを利用することも可能であるが、以下 の説明では、７−ｂｉｔ ＡＳＣＩＩコードの印刷可能な文字を用いる場合を例に説明す る。単に文字コード表と称する場合には、７−ｂｉｔ ＡＳＣＩＩコードなどの文字コー ド表を指すものと理解されたい。 【００２９】 本実施形態のデータ通信システム１では、変換マップＭにより、最大限の印刷可能な文 字を用いて符号化と文字化を一度に行うことによりＢＣＨ符号などのブロック符号を文字 化したものと比べ良好な符号化率を得ることができる。変換マップＭが符号文字として印 刷可能な文字を用いることにより、送信データのロギングや送信データのメールへの添付 が容易である。 【００３０】 〔デリミタによる符号文字の制限〕 上述の通り、符号文字として利用できる文字の数によりコプライムセットＣｓｅｔに含 まれる最大のコプライムＣの値が規定されるが、本発明に係る通信システムの通信方法は ブロック符号の一種であるので、符号語間を分離するデリミタと呼ばれる制御コードが必 要な場合がある。そこで、文字コード表における任意の１文字をデリミタを表す文字とし て扱うとよい。デリミタを表す文字は印刷可能な文字以外の文字（制御文字等）としても よい。このとき、デリミタにも誤りに対する耐性を持たせるべく、デリミタを割り当てる 文字のコードに対し１ビットの誤りが生じたコードに対応する文字については剰余を割り 当てないようにするとよい。すなわち、デリミタに文字コードを割り当てられることによ り、コプライムセットＣｓｅｔに含まれる最大のコプライムＣの値は、デリミタを用いな い場合と比較して減少することがある。 【００３１】 例えば、ＡＳＣＩＩコード（図２）での改行文字のＬＦ（０ｘ０ａ）をデリミタして用 いる場合を考える。文字コード表においてＬＦ（０ｘ０ａ）が１ビット誤ったコードに対 応する文字は、ＶＴ（０ｘ０ｂ）、ＢＳ（０ｘ０８）、ＳＯ（０ｘ０ｅ）、ＳＴＸ（０ｘ ０２）、ＳＵＢ（０ｘ１ａ）、＊（０ｘ２ａ）、Ｊ（０ｘ４ａ）の７文字であるが、これ らのうちで印刷可能な文字は＊（０ｘ２ａ）とＪ（０ｘ４ａ）の２文字である。そこで、 ＬＦ（０ｘ０ａ）をデリミタして用いる場合には、＊（０ｘ２ａ）とＪ（０ｘ４ａ）に剰 余を割り当てないようにすることで、コプライムセットＣｓｅｔに含まれる最大のコプラ イムＣの値が９２に制限されつつ、デリミタに対して１ビットの誤り耐性を持たせること ができる。図３はこのようにデリミタに対して誤り耐性を持たせたときの変換マップＭの 一例を示している。 【００３２】 以上で説明したように、変換マップＭにおける剰余に対する文字の割当に自由度がある ため、１ビット誤り訂正付きデリミタの利用も可能となり、デリミタのために特別な同期 ワードを必要としない。 【００３３】 デリミタの７ビット中１ビットの誤り訂正による誤り率の改善の程度は、７文字中１文 字、あるいは７シンボル中１シンボルの誤り訂正によるものと同じオーダーであるので本 発明に係る通信システムとしては誤り訂正能力のバランスがよい。 【００３４】 〔その他の符号文字の制限〕 上述の通り、ＡＳＣＩＩコードでの改行文字のＬＦ（０ｘ０ａ）をデリミタして用いる 場合、符号文字は９２に制限されるが、他の任意の文字を符号文字として利用しないよう にすることもできる。例えば、コンマ（，）を符号文字として利用しないようにしてもよ い。この場合、符号文字はさらに１つ減少し、９１に制限されるが、剰余数系を変換マッ プＭにより符号文字の配列としてあらわした符号語をＣＳＶ(コンマ分離テキスト)形式で 保存するといった利用法が想定される場合には、符号語中のコンマが符号語の区切りを表 すものとして誤認されることを防ぐことができる。 【００３５】 〔コプライムセットの選択〕 中国人剰余定理(Chinese remainder theorem)によると正整数ｘは、式（１）を満たす 互いに素な数（コプライム）p 1 …p k の剰余の組（剰余数系）で一意に表される。 【数１】つまり、コプライムの組を決めれば、それらの数の総乗未満の正整数で表される情報を 、剰余数系により表すことが可能となる。 【００３６】 コプライムセットＣｓｅｔには、変換マップＭで用いることのできる符号文字の種類以 下であり、且つ、互いに素な数の組が用いられる。例えば、変換マップＭとして、上記の 例のように９４種の印刷可能な文字を含むものを用いる場合、９４以下の数で構成される 互いに素な数の組を用いることができる。素数同士はもちろん互いに素であるが、合成数 でもその素因数が重複しなければ、互いに素となりうる。以下に、９４以下の数で構成さ れる互いに素な数の組の例を示す。識別のために互いの素な数の組中の最大の要素をｍで 表すものとし、ｍ以下の互いに素な数の組をＣｏｐｒｉｍｅｓ＿ｍ（例えば、最大の要素 が９４であれｂＣｏｐｒｉｍｅｓ＿９４）と表記するものとする。 【００３７】 Coprimes_94 = {94, 93, 91, 89, 85, 83, 79, 73, 71, 67, 61, 59, 53, 43, 41, 37, 2 9, 23, 19, 11} Coprimes_93 = {93, 92, 91, 89, 85, 83, 79, 73, 71, 67, 61, 59, 53, 47, 43, 41, 3 7, 29, 19, 11} Coprimes_92 = {92, 91, 89, 87, 85, 83, 79, 73, 71, 67, 61, 59, 53, 47, 43, 41, 3 7, 31, 19, 11} Coprimes_91 = {91, 89, 88, 87, 85, 83, 79, 73, 71, 67, 61, 59, 53, 47, 43, 41, 3 7, 31, 23, 19} Coprimes_90 = {90, 89, 85, 83, 79, 73, 71, 67, 61, 59, 53, 47, 43, 41, 37, 31, 2 9, 23, 19, 17, 13, 11} Coprimes_89 = {89, 88, 87, 85, 83, 79, 73, 71, 67, 61, 59, 53, 49, 47, 43, 41, 3 7, 31, 23, 19, 13} 【００３８】 例えば、Ｃｏｐｒｉｍｅｓ＿９２中の上位３個のコプライム（９２，９１，８９）による 剰余数系を用いれば、９２×９１×８９＝７４５１０８未満の正整数を表現できる。 【００３９】 本実施形態のデータ通信システム１では、送信データｄｔｘを、コプライムセットＣｓ ｅｔの各要素で割ったときの剰余の組である剰余数系により表すが、コプライムの組であ るコプライムセットＣｓｅｔに冗長性を持たせることで、誤り訂正を可能とする。すなわ ち、コプライムｐ １ …ｐ ｋ の剰余の組（剰余数系）により式（１）を満たす正整数ｘを表 現する場合、２つの互いに素な数ｐ ｋ＋１ 、ｐ ｋ＋２ （ただし、ｐ ｋ ＜ｐ ｋ＋１ ＜ｐ ｋ＋ ２ ）を追加してｘをｋ＋２個の剰余で表すように冗長性を持たせると、１つの剰余に誤り があった場合に、ｋ＋２個中のｋ個の剰余から逆算され得る ｋ＋２ Ｃ ｋ 個の正整数のうち ｋ＋１ Ｃ ｋ−１ 個は互いに異なるものとなるが ｋ＋１ Ｃ ｋ 個は同一となるため多数決によ り１シンボルの誤り訂正が可能となる。 【００４０】 より多くの多数決判定が出来るように上記ｒを増して冗長度を増加すれば２シンボル以 上の誤りの訂正も可能である。また、ｒ＝１とした場合には、誤りの検出が可能であるも のの、訂正はできない。ｒ＝１として、誤りが検出された場合、受信装置３は送信装置２ に送信データｄｔｘの再送を促すようにするとよい。 【００４１】 以下、ある数（送信するデータ）をｎ個のコプライムを除数とする剰余で表す体系をｎ 個のコプライムによる剰余数系と呼ぶこととする。そして、ｎ個のコプライムに、それら より大きいｒ（１≦ｒ）個以上のコプライムを追加して、ｎ＋ｒ個のコプライムの剰余で ある数を表す体系を「冗長な剰余数系」と呼ぶこととする。本実施形態のデータ通信シス テム１では、送信データをこの「冗長な剰余数系」により表す。典型的には、ｎ個のコプ ライムに２個の冗長なコプライムを追加して「冗長な剰余数系」により送信データを表現 する。 【００４２】 具体例としては、Ｃｏｐｒｉｍｅｓ＿９２中の最上位２個のコプライム（９２，９１） を冗長なコプライム（ｒ＝２）とし、それに続く上位３つのコプライム（８９，８７，８ ５）を冗長でないコプライム（ｎ＝３）として用いる「冗長な剰余数系」とすれば、３つ のコプライム（８９，８７，８５）の総乗である８９×８７×８５＝６５８１５５未満の 正整数を表現でき、かつ、冗長性により１シンボルの誤り訂正が可能である。 【００４３】 冗長な剰余数系で表す数の情報エントロピーの最小値を考える。例えば、前記のＣｏｐｒ ｉｍｅｓ＿９２中のｎ＋ｒ個中の下位ｎ個の数の組で表しうる冗長な剰余数系の数の情報 エントロピーの最小値は、および情報エントロピーを自然数に切り捨てた情報ビット数は、 ｒ＝２，ｎが１〜９において次のようになる。 【００４４】 ｎ＝１のとき: ln(89) / ln(2) ≒ 6.47 > 6 bit ｎ＝２のとき: ln(87 * 89) / ln(2) ≒ 12.91 > 12 bit ｎ＝３のとき: ln(85 * 87 * 89) / ln(2) ≒ 19.32 > 19 bit ｎ＝４のとき: ln(83 * 85 * 87 * 89) / ln(2) ≒ 25.70 > 25 bit ｎ＝５のとき: ln(79 * 83 * 85 * 87 * 89) / ln(2) ≒ 32.00 > 32 bit ｎ＝６のとき: ln(73 * 79 * 83 * 85 * 87 * 89) / ln(2) ≒ 38.19 > 38 bit ｎ＝７のとき: ln(71 * 73 * 79 * 83 * 85 * 87 * 89) / ln(2) ≒ 44.34 > 44 bit ｎ＝８のとき: ln(67 * 71 * 73 * 79 * 83 * 85 * 87 * 89) / ln(2) ≒ 50.41 > 50 bi t ｎ＝９のとき: ln(61 * 67 * 71 * 73 * 79 * 83 * 85 * 87 * 89) / ln(2) ≒ 56.34 > 56 bit ｎ＝１０のとき: ln(59 * 61 * 67 * 71 * 73 * 79 * 83 * 85 * 87 * 89) / ln(2) ≒ 6 2.22 > 62 bit ｎ＝１１のとき: ln(53 * 59 * 61 * 67 * 71 * 73 * 79 * 83 * 85 * 87 * 89) / ln(2) ≒ 67.95 > 67 bit 【００４５】 なお、前述のように、符号文字として７−ｂｉｔ ＡＳＣＩＩコードなどの文字コード 表における印刷可能な文字を用い、ＡＳＣＩＩコードでの改行文字のＬＦ（０ｘ０ａ）を デリミタして用いる場合、デリミタが誤った場合の文字を除外するための冗長度のために 、印字可能な文字数より２つ小さいＣｏｐｒｉｍｅｓ＿９２からコプライムセットＣｓｅ ｔを構成するコプライムＣを選択するのが好ましい。 【００４６】 〔情報ビットとスーパーデータ〕 上述のように、データの伝送に用いる情報ビット数は、冗長な剰余数系で表す数の情報 エントロピーを自然数に切り捨てたビット数であるが、本実施形態のデータ通信システム １では、情報エントロピーの小数部分を利用して、例えば、伝送先アドレスや伝送符号長 やハッシュ値あるいは日付などのいわゆるヘッダー情報に代表される付加的な情報（以下 ではこの情報エントロピーの小数部分を利用した情報をスーパーデータと呼ぶ）を、デー タとは区別して伝送することができ、そのために特別なフレーム構造は不要である。スー パーデータを符号化したものも通常のデータを符号化したものと同じ符号語であるため誤 り訂正も同様に行われる。 【００４７】 例えば、先述のＣｏｐｒｉｍｅｓ＿９２においてｎ＝７、ｒ＝２とした場合の情報エン トロピーは約、４４．３４ビットであるので４４ビットまでの情報ビット、すなわち１６ 進数表記で0〜0x0fffffffffffまでの値の情報ビットを扱うことができるが、情報エント ロピーの余剰分として、符号化できる値としては0x000000000000から0x1457ce160ea0まで であるので、この0x100000000000〜0x1457ce160ea0をスーパーデータとして使用すること ができる。スーパーデータは、送信装置２の内部で生成されてもよいし、送信装置２に外 部から提供されてもよい。また、受信装置３は、受信したスーパーデータを受信装置３の 内部での処理に用いてもよいし、受信装置の外部に出力してもよい。 【００４８】 このようにスーパーデータを伝送することにより、情報エントロピーを有効利用するこ とができる。本発明の手法は、情報ビットの伝送だけを考えも十分に高い符号化率を実現 するが、スーパーデータを含めると、より高い符号化率を実現することができる。 【００４９】 〔動作例〕 続いて、以上で説明したデータ通信システム１において、送信装置２から受信装置３に データを送信する際の動作の一例を説明する。 以下の例では、変換マップＭは、符号文字として７−ｂｉｔ ＡＳＣＩＩコードなどの 文字コード表における印刷可能な文字を用い、ＡＳＣＩＩコードでの改行文字のＬＦ（０ ｘ０ａ）をデリミタして用いる。また、コプライムセットＣｓｅｔは、Ｃｏｐｒｉｍｅｓ ＿９２においてｎ＝６、ｒ＝２とし３８ビットの情報ビットを伝送する。コプライムセッ トＣｓｅｔに含まれるコプライムＣは、小さい順に、７３，７９，８３，８５，８７，８ ９，９１，９２の８個である。これらのコプライムＣによる送信データの剰余を用いて冗 長な剰余数系を表す。 【００５０】 送信装置２から受信装置３への送信データｄｔｘを0x000003dbabeface（１０進数で表 すと265126083278）とする。送信装置２の剰余数系算出部２１は、コプライムセットＣｓ ｅｔに含まれる各コプライムＣによる送信データｄｔｘの剰余を次のように算出する。 ２６５１２６０８３２７８ ％ ７３ ＝ ３６ ２６５１２６０８３２７８ ％ ７９ ＝ ４８ ２６５１２６０８３２７８ ％ ８３ ＝ ８１ ２６５１２６０８３２７８ ％ ８５ ＝ ４３ ２６５１２６０８３２７８ ％ ８７ ＝ ５０ ２６５１２６０８３２７８ ％ ８９ ＝ ８３ ２６５１２６０８３２７８ ％ ９１ ＝ ５６ ２６５１２６０８３２７８ ％ ９２ ＝ ２ 【００５１】 送信装置２のマッピング処理部２２は、上記のようにして求めた剰余を変換マップＭを 用いて次のように符号文字に変換する。 ３６ → Ｆ ４８ → Ｓ ８１ → ｔ ４３ → Ｎ ５０ → Ｕ ８３ → ｖ ５６ → ［ ２ → ＃ 【００５２】 すなわち、送信装置２において、送信データｄｔｘである0x3dbabefaceは、８個の符号 文字による文字列FStNUv[#で表される剰余数系に変換される。この剰余数系が符号化され た送信データtxcodeとなる。 【００５３】 符号化された送信データtxcodeは、通信路を介して受信装置３に伝送される。伝送中に エラーが生じない場合、受信装置３が受信する符号化された受信データrxcodeは符号化さ れた送信データtxcodeと同じFStNUv[#となる。受信装置３のマッピング解除部３２は、変 換マップＭを用いて剰余数系を復元する。すなわち、FStNUv[#から、８個の剰余の組であ る剰余数系｛３６，４８，８１，４３，５０，８３，５６，２｝が得られる。受信装置３ のデータ復号部３３は、剰余数系の中の６つの剰余および剰余に対応するコプライムＣを 用いて、中国人剰余定理により送信データを復号する。例えば、コプライムセットＣｓｅ ｔ｛７３，７９，８３，８５，８７，８９，９１，９２｝のうち、隣接する２つのコプラ イム（または両端のコプライム）を不使用として、下記の８通りのコプライムの組み合わ せで復号を行うとよい。 ｛８３，８５，８７，８９，９１，９２｝ ｛７３，８５，８７，８９，９１，９２｝ ｛７３，７９，８７，８９，９１，９２｝ ｛７３，７９，８３，８９，９１，９２｝ ｛７３，７９，８３，８５，９１，９２｝ ｛７３，７９，８３，８５，８７，９２｝ ｛７３，７９，８３，８５，８７，８９｝ ｛７９，８３，８５，８７，８９，９１｝ 【００５４】 このように復号に用いる剰余の組み合わせにより、複数通りの復号が可能であるが、エ ラーが無い場合には、どの剰余の組み合わせで復号しても、得られる送信データは共通の 、0x3dbabefaceとなる。 【００５５】 次に、伝送中に１ビットのエラーが生じた場合を考える。一例として、符号化された送 信データtxcode ＝FStNUv[#における３文字目のtを表す１６進数０ｘ７４の２ビット目に エラーが生じて、０ｘ３４（符号文字4）となり、受信データrxcodeがFS4NUv[#となった 場合、受信装置３のマッピング解除部３２は、変換マップＭを用いて剰余数系を復元し、 剰余数系｛３６，４８，１８，４３，５０，８３，５６，２｝が得られる。データ復号部 ３３は、剰余数系の中の６つの剰余および剰余に対応するコプライムＣを用いて、中国人 剰余定理により送信データを復号する。復号に用いる剰余にエラーの影響を受けた剰余（ 上記の例では剰余数系における３番目の１８；８３を除数としたときの剰余）が含まれな い場合には、復号の結果は0x3dbabefaceとなる。一方、復号に用いる剰余に、エラーの影 響を受けた剰余が含まれる場合には、復号の結果は0x3dbabefaceと異なり、且つ、他の組 み合わせでの復号結果とも異なる値となる。このようにして得られる複数の復号結果のな かで、同じ値が複数得られるのは正しい復号結果である0x3dbabefaceのみとなる。したが って、複数の復号結果を対象とする多数決により、誤りのない正しい復号結果が特定され る。 【００５６】 以上で説明したデータ通信システム１で実現される符号／復号方法は、復号を中国人剰 余定理に基づく計算により行えるため、大きな変換テーブルを必要とせず、リソースに制 限のある機器でも利用しやすい。また、符号の構造が単純なためメモリーが少ない装置や ＭＣＵなどに於いても利用しやすい。また、符号の単位が３〜十数バイトであるため伝送 および処理遅延が少なく、リアルタイム性の要求されるロボットや車などの装置間シリア ル通信での利用に適している。また、非同期シリアル通信の送受信装置やデバイス間通信 へ適用することができる。…（１）
図１
図２
図３
変更履歴
▼ 変更履歴（クリックで展開します）関連項目
- 紛らわしい文字を含まない (5-char, 16-bit) 誤り訂正文字化符号
- 中国人剰余定理を利用した剰余系による数値計算法の例
- アブソリュート型エンコーダ (特許第6083034号)
- BCHTX — バイナリ・テキスト変換プログラム
- 2元 BCH 符号及びバースト誤り訂正符号
- モータ駆動装置 (特許第5979649号)
Copyright (c) Finetune co., ltd.
