特許ウォッチ

公開番号2025118408
公報種別公開特許公報(A)
公開日2025-08-13
出願番号2024013719
出願日2024-01-31
発明の名称誤り訂正装置及び誤り訂正方法
出願人個人
代理人個人
主分類H03M 13/37 20060101AFI20250805BHJP(基本電子回路)
要約【課題】巡回冗長検査(CRC)によって、受信データ列に誤りが発生したと判断されたときに、そのデータ列を訂正する誤り訂正装置を提供する。
【解決手段】受信した送信データ(X)のCRC剰余項(CRC(X))と、受信データ(Y)から生成したCRC剰余項(CRC(Y))との排他的論理和をとり、その結果に基づいて通信エラーを検知する誤り検知手段と、送信データ(受信データ)と同じビット数を有する誤りビットの分布パターンと、該誤りビットの分布パターンのCRC剰余項とを対応付けて格納したルックアップテーブルと、受信データ(Y)の訂正を行う誤り訂正手段とを備えるとともに、誤り訂正手段は、RC(X)とCRC(Y)との排他的論理和をルックアップテーブルに入力し、出力された誤りビットの分布パターンと受信データ(Y)との排他的論理和を取ることにより、受信データ(Y)の語りを訂正する。
【選択図】図3
特許請求の範囲【請求項１】
誤り検出方法として巡回冗長検査（以下「CRC」という。）を採用するデジタル通信における通信エラーの発生の有無を検知するとともに、誤った受信データを訂正する機能を備えた誤り訂正装置であって、該誤り訂正装置は、
受信した送信データ(X)のCRC剰余項（以下CRC(X)という。）と、前記受信データ(Y)から生成したCRC剰余項（以下CRC(Y)という。）との排他的論理和をとり、その結果に基づいて前記通信エラーを検知する誤り検知手段と、
前記送信データ（受信データ）と同じビット数を有する誤りビットの分布パターンと、該誤りビットの分布パターンのCRC剰余項とを対応付けて格納したルックアップテーブルと、
前記受信データ(Y)の訂正を行う誤り訂正手段とを備えるとともに、
前記誤り検知手段が前記通信エラーを検知すると、前記誤り訂正手段は、前記CRC(X)と前記CRC(Y)との排他的論理和を前記ルックアップテーブルに入力し、出力された誤りビットの分布パターンと前記受信データ(Y)との排他的論理和を取ることにより、前記受信データ(Y)の誤りを訂正することを特徴とする誤り訂正装置。
続きを表示（約 1,800 文字）【請求項２】
誤り検出符号としてハッシュ値を採用するデジタル通信における、通信エラーの発生の有無を検知するとともに、誤った受信データを訂正する機能を備えた誤り訂正装置であって、
受信した送信データ(X)のハッシュ値（以下HASH(X)という。）と、前記受信データ(Y)から生成したハッシュ値（以下HASH(Y)という。）との排他的論理和をとり、その結果に基づいて前記通信エラーを検知する誤り検知手段と、
前記送信データ（受信データ）と同じビット数を有する誤りビットの分布パターンと、該誤りビットの分布パターンのハッシュ値とを対応付けて格納したルックアップテーブルと、
前記受信データ(Y)の訂正を行う誤り訂正手段とを備えるとともに、
前記ハッシュ値を生成する関数は線形性を有し、HASH(X^Y)=HASH(X)^HASH(Y)を満たすとともに（「^」は排他的論理和を表す。）、
前記誤り検知手段が前記通信エラーを検知すると、前記誤り訂正手段は、前記HASH(X)と前記HASH(Y)との排他的論理和を前記ルックアップテーブルに入力し、出力された誤りビットの分布パターンと前記受信データ(Y)との排他的論理和を取ることにより、前記受信データ(Y)の誤りを訂正することを特徴とする誤り訂正装置。
【請求項３】
誤り検出方法としてCRCを採用するデジタル通信における通信エラーの発生の有無を検知するとともに、誤った受信データを訂正する誤り訂正方法であって、該方法は、
受信した送信データ(X)のCRC(X)と、前記受信データ(Y)から生成したCRC(Y)とを比較して前記通信エラーを検知するステップと、
前記通信エラーが検知されたときに、前記CRC(X)と前記CRC(Y)との前記排他的論理和を、誤りビットの分布パターンと該誤りビットの分布パターンのCRC剰余項とを対応付けて格納したルックアップテーブルに入力するステップと、
前記ルックアップテーブルから出力された誤りビットの分布パターンと前記受信データ(Y)との排他的論理和を取ることにより、前記受信データ(Y)の誤りを訂正するステップとを備えたことを特徴とする誤り訂正方法。
【請求項４】
誤り検出符号としてハッシュ値を採用するデジタル通信における、通信エラーの発生の有無を検知するとともに、誤った受信データを訂正する誤り訂正方法であって、該方法は、
受信した送信データ(X)のハッシュ値（以下HASH(X)という。）と、前記受信データ(Y)から生成したハッシュ値（以下HASH(Y)という。）との排他的論理和をとり、その結果に基づいて前記通信エラーを検知するステップと、
前記通信エラーが検知されたときに、前記HASH(X)と前記HASH(Y)との前記排他的論理和を、誤りビットの分布パターンと該誤りビットの分布パターンのハッシュ値とを対応付けて格納したルックアップテーブルに入力するステップとを備え、
前記ハッシュ値を生成する関数は線形性を有し、HASH(X^Y)=HASH(X)^HASH(Y)を満たすとともに（「^」は排他的論理和を表す。）、
前記ルックアップテーブルから出力された誤りビットの分布パターンと前記受信データ(Y)との排他的論理和を取ることにより、前記受信データ(Y)の誤りを訂正するステップとを備えたことを特徴とする誤り訂正方法。
【請求項５】
誤り検出方法としてCRCを採用するデジタル通信における通信エラーの発生の有無を検知するとともに、誤った受信データを訂正する誤り訂正方法であって、該方法は、
受信した送信データ(X)のCRC(X)と、前記受信データ(Y)から生成したCRC(Y)との排他的論理和をとるステップと、
前記CRC(X)と前記CRC(Y)の前記排他的論理和を、誤りビットの分布パターンと該誤りビットの分布パターンのCRC剰余項とを対応付けて格納したルックアップテーブルに入力するステップと、
前記ルックアップテーブルから出力された誤りビットの分布パターンと前記受信データ(Y)との排他的論理和を取ることにより、前記受信データ(Y)の誤りを訂正するステップとを備えたことを特徴とする誤り訂正方法。

発明の詳細な説明【技術分野】
【０００１】
本発明は、本発明は、誤り訂正装置に関し、特に、デジタル信号によるデータ通信における通信エラー発生の有無を判定し、エラーが発生したときは訂正する機能を備えた誤り訂正装置に関する。
続きを表示（約 3,400 文字）【背景技術】
【０００２】
デジタル通信の分野におけるデータ伝送の誤りを検出する方法として、巡回冗長検査（Cyclic Redundancy Check、以下「CRC」という。）が用いられている。CRCとは、ディスク等の読み出し／書き込み等、主にシリアルインタフェースのＩ／Ｏアクセスにおいて、データに誤りを検出する符号を付加することでデータ伝送の誤りを検出する機能である。データを送信する側では、送信するデータを特定の数を用いて割り算を行い、割り算の「余り」を誤り検出符号としてデータに付加して送信する。データの受信側では、受信したデータを同じ特定の数を用いて割り算を行い、算出した「余り」が受信した「余り」と等しければ、データ伝送途中にデータに誤りがなかったことになり、受信データは正しいと判断できる。これに対し、「余り」が一致しなかった場合は、データ伝送に誤りがあると判断できる。
【０００３】
しかしながら、CRCでは誤りのあるデータを訂正することはできないとされ、今まで技術的検討が充分にはなされてこなかった。したがって、これに関する先行技術文献（特許文献）は見つかっていない。これはCRCが、多くの教育機関等で「誤り訂正不可能な符号」として分類され、長年固定観念的に教育されてきたことも原因だと思われる。
誤りが訂正できない場合は、受信側は送られてきたデータを破棄し、送信側にデータの再送を要求し、送信側は再送の要求を受けて再度データを送信することになる。
【０００４】
このように、訂正不可能と思われた一つの理由として、受信したデータのどの部分（ビット）に誤りがあるのかが分からないことが挙げられる。
誤りビットが一つと仮定すると、ｎビットのデータの右（最下位）からｍ番目（１≦ｍ≦ｎ）に誤りがあることが分かれば、ｍ番目のみを「１」残りをすべて「０」にした「訂正用データ」を作り、それと受信データ（ｎビット）とのビット毎の排他的論理和（以下断らない限り、「排他的論理和」は「ビット毎の排他的論理和」を指すものとする。）をとれば、受信データのｍ番目のビットを訂正し（「１→０」又は「０→１」）、元の正しいデータを復元することができる。
誤りビットの数が２以上の場合でも、誤りの場所を特定できれば、同様の方法で訂正することができる。
【先行技術文献】
【非特許文献】
【０００５】
Keith,Lockstone, Mark Lomas, “Active attacks on stream ciphers with cyclic redundancy checks (crcs),”、インターネット<URL: https://www.cix.co.uk/~klockstone/crchack.htm>
Amitangshu Pal, Alireza Jolfaei, Krishna Kant, “A Fast Prekeying Based Integrity Protection for Smart Grid Communications”, IEEE Transactions on Industrial Informatics,Volume17,Issue8, August 2021, インターネット<URL: https://ieeexplore.ieee.org/ielaam/9424/9422988/9222075-aam.pdf>
Wikipedia, “Cyclic redundancy check”, インターネット、<URL: https://en.wikipedia.org/wiki/Cyclic_redundancy_check>
【発明の概要】
【発明が解決しようとする課題】
【０００６】
しかしながら、受信側で得られる情報は、受信データ（「Y」とする。）、送信データ（以下「X」とする。）を特定の数（以下「生成多項式」という。）で割った剰余項（以下CRC(X)とする。）及び受信データ(Y)から生成した剰余項CRC(Y)の３つしかない。
もし、送信データ(X)と受信データ(Y)との排他的論理和（以下これを「X^Y」と表す。）をとることができれば、エラーが発生した場所のビットだけが「１」となるので、それがそのまま上記の「訂正用データ」になるので、誤り訂正ができる。
しかしながら、受信側では送信データ(X)を知ることはできないから、直接(X^Y)を求めることはできない。そこで、本発明者は、CRC(X)とCRC(Y)を用いて(X^Y)を求める方法について鋭意検討を重ねた結果、次の考えに到達した。
【０００７】
CRC(X)の計算においては、次の式１が成り立つことが知られている（上記非特許文献１～３参照）。
CRC(X^Y)＝CRC(X)^CRC(Y)…（式１）
本発明者は、式１の右辺の計算を行うことによってCRC(X^Y)を求めれば、そこからエラービットの数等に関して一定の制限はあるが、(X^Y)を求めることができることに想到した。
本発明は、上述のような事情に鑑みなされたものであり、送信データ(X)のCRC剰余項CRC(X)と受信データ(Y)のCRC剰余項CRC(Y)に基づいて通信エラーの発生の有無を検出するとともに、通信エラーが発生したときはCRC(X)とCRC(Y)に基づいてエラーの訂正を行う機能を備えた誤り訂正装置を提供することを目的とする。
【課題を解決するための手段】
【０００８】
本発明は、誤り検出方法として巡回冗長検査（以下「CRC」という。）を採用するデジタル通信における通信エラーの発生の有無を検知するとともに、誤った受信データを訂正する機能を備えた誤り訂正装置に関し、本発明の上記目的は、該誤り訂正装置が、受信した送信データ(X)のCRC剰余項（以下CRC(X)という。）と、前記受信データ(Y)から生成したCRC剰余項（以下CRC(Y)という。）との排他的論理和をとり、その結果に基づいて前記通信エラーを検知する誤り検知手段と、前記送信データ（受信データ）と同じビット数を有する誤りビットの分布パターンと、該誤りビットの分布パターンのCRC剰余項とを対応付けて格納したルックアップテーブルと、前記受信データ(Y)の訂正を行う誤り訂正手段とを備えるとともに、前記誤り検知手段が前記通信エラーを検知すると、前記誤り訂正手段は、前記CRC(X)と前記CRC(Y)との排他的論理和を前記ルックアップテーブルに入力し、出力された誤りビットの分布パターンと前記受信データ(Y)との排他的論理和を取ることにより、前記受信データ(Y)の誤りを訂正することによって達成される。
【０００９】
また、本発明は、誤り検出方法としてCRCを採用するデジタル通信における通信エラーの発生の有無を検知するとともに、誤った受信データを訂正する誤り訂正方法に関し、本発明の上記目的は、該方法が、受信した送信データ(X)のCRC(X)と、前記受信データ(Y)から生成したCRC(Y)とを比較して前記通信エラーを検知するステップと、前記通信エラーが検知されたときに、前記CRC(X)と前記CRC(Y)との前記排他的論理和を、誤りビットの分布パターンと該誤りビットの分布パターンのCRC剰余項とを対応付けて格納したルックアップテーブルに入力するステップと、前記ルックアップテーブルから出力された誤りビットの分布パターンと前記受信データ(Y)との排他的論理和を取ることにより、前記受信データ(Y)の誤りを訂正するステップとを備えることにより達成される。
【発明の効果】
【００１０】
本発明に係る誤り訂正装置及びその方法によれば、簡便な方法により、エラーが生じたデータの訂正を行うことができる。
【図面の簡単な説明】
（【００１１】以降は省略されています）

関連特許