(57)【要約】  １クロックサイクルの計算遅延を伴うデジタル実装で具体化することができる、多項式ジェネレータの長さおよびデータストリームの長さとは無関係に巡回冗長検査（ＣＲＣ）を計算するためのアルゴリズムの構成方法。本方法により、情報のシーケンスおよび対応する多項式ジェネレータが、変換テーブルの中に構成されることができるようになる。【選択図】図１
2018515985.tif 000002
【特許請求の範囲】
【請求項１】
並列巡回冗長検査（ＣＲＣ）を行うためのアルゴリズムの構成方法であって、（ｉ）多項式ジェネレータｇ（ｘ）＝ｇｋ−１ｘｋ−１＋ｇｋ−２ｘｋ−２＋ｇｋ−２ｘｋ−２＋・・・＋ｇ０、およびｆ（ｘ）＝ｍ（ｘ）ｘｋ−１＋ｃ（ｘ）について考慮するステップであって、ｍ（ｘ）＝ｍＬ−１ｘＬ−１＋ｍＬ−２ｘＬ−２＋ｍＬ−２ｘＬ−２＋・・・＋ｍ０であるステップと、（ｉｉ）前記ｆ（ｘ）および前記ｇ（ｘ）を互いの関数としてテーブルに変換するステップと、（ｉｉｉ）ｋ＝７およびＬ＝７の代表的な場合を考慮すると、ｆｎ−１＝Ａ、ｆｎ−１＝Ａ＋Ｂ、ｆｎ−１＝Ａ＋Ｂ＋Ｃ、・・・、ｆ２＝Ｅ＋Ｆ＋Ｇ、ｆ１＝Ｆ＋Ｇ、ｆ０＝Ｇを得るステップであって、Ａ、Ｂ、Ｃ、・・・、Ｇが除数係数であるステップと、（ｉｖ）ｃｋ−２＝ｆｋ−２、ｃｋ−２＝ｆｋ−２、・・・、ｃ１＝ｆ１、ｃ０＝ｆ０を得るステップとを備えるアルゴリズムの構成方法。
【請求項２】
前記ステップ（ｉｉｉ）で、前記多項式ジェネレータの前記ｇ（ｘ）の前記係数がすべて１に等しいわけではない場合、前記導出には前記多項式ジェネレータの前記除数係数に基づく余分な乗算因数が必要である、請求項１に記載のアルゴリズムの構成方法。
【請求項３】
請求項１に記載の前記ステップ（ｉｉｉ）で具体化することができる数学的定式化を利用することにより、前記多項式ジェネレータのシーケンスによりデータストリームからＣＲＣチェックサムを得るために、前記除数係数Ａ、Ｂ、・・・、Ｆ、Ｇが使用される、請求項１に記載のアルゴリズムの構成方法。
【請求項４】
前記アルゴリズムが、前記多項式ジェネレータの長さおよび前記データストリームの長さとは無関係である、請求項１に記載のアルゴリズムの構成方法。
【請求項５】
デジタル論理回路実装で具体化される前記アルゴリズムが、典型的な１システム・クロック・サイクルの遅延を伴う最も遅い合成組合せ論理経路の伝播遅延だけにより速度が制限される、請求項１に記載のアルゴリズムの構成方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、デジタルデータ処理での誤り訂正の分野に関し、より詳細には多項式ジェネレータの長さおよびデータストリームの長さとは無関係にＣＲＣを計算するためのシステムを生成するためのアルゴリズムに関する。
【背景技術】
【０００２】
誤り訂正の技法およびアーキテクチャが、磁気、光、または半導体に基づくメモリ記憶装置などのデータ記憶サブシステムを有するシステムを含むデジタルデータ処理および通信システムでよく知られている。エンコーダ回路を使用して、選択されたデータのブロック内の情報を数学的に特徴づける「冗長な」ｍビット誤り検査記号からなる何らかの数字を構築することにより、誤ったデータの検出、および可能な場合には誤ったデータの訂正を実現している。次いで、誤り検査記号はデータブロックに付加され、通信チャネルを通して転送される。データブロックを受信したとき、または後でメモリから取り出したとき、これらの付加された誤り検査記号を使用することにより、データの正確さまたは信頼性を評価することができる。
【０００３】
巡回冗長検査（Ｃｙｃｌｉｃ  Ｒｅｄｕｎｄａｎｃｙ  Ｃｈｅｃｋ、ＣＲＣ）は、当技術分野で広く知られており、かつ送信された情報のストリームから誤りを検出するための手段として数多くの適用分野で使用される、古典的誤り検出機構である。ＣＲＣが一般に受け入れられているのは、ＣＲＣを情報のストリームの中に符号化して送信し、受信者で引き続き検査するために使用することができる、実装のしやすさのためである。
【０００４】
ＣＲＣの計算は多項式演算の形で行われ、それにより、アルゴリズムの基本は、データストリームから誤り検査記号（ＣＲＣの関連では、誤り検査記号はまた、チェックサムとしても知られている）を構築し、検証するために使用される、本質的に一続きの情報である同じ多項式ジェネレータを使用することを、送信者と受信者の両方が相互に同意しているという前提で、情報のストリーム（パケットまたはフレームとしても知られている）が送信され、それにより、選ばれた多項式ジェネレータによる多項式の除算をデータストリームに対して行うことにより誤り検査記号の計算結果が作成されるものである。
【発明の概要】
【発明が解決しようとする課題】
【０００５】
従来技術では、固定データ幅を有する誤り検査記号を計算することができる速度を最適化するために、特定の多項式ジェネレータに有効なブール式または論理式を得る解決策を選んだ方法論があれば、その一方で、ＬＦＳＲ（ｌｉｎｅａｒ  ｆｅｅｄｂａｃｋ  ｓｈｉｆｔ  ｒｅｇｉｓｔｅｒ、線形帰還シフトレジスタ）を使用する考えを最適化する方法論もあったが、単一ビットのシフトではなく多くのビットまたはバイトがクロックサイクルごとにシフトとされることがあり、しかしながら、この場合、これによりアルゴリズムに追加の規則が課される。さらにまた、従来技術により提案された方法論の中には、ある種の情報のストリームのうち変化のない部分を検査することにより、ＣＲＣを行う操作を最適化しようと試みるものがあれば、その一方で、情報のパケットのセグメントに基づき部分剰余を計算することにより、方法論を改善しようと試みるものもある。
【課題を解決するための手段】
【０００６】
本発明は、（ｉ）多項式ジェネレータｇ（ｘ）＝ｇｋ−１ｘｋ−１＋ｇｋ−２ｘｋ−２＋ｇｋ−２ｘｋ−２＋・・・＋ｇ０、およびｆ（ｘ）＝ｍ（ｘ）ｘｋ−１＋ｃ（ｘ）について考慮するステップであって、ｍ（ｘ）＝ｍＬ−１ｘＬ−１＋ｍＬ−２ｘＬ−２＋ｍＬ−２ｘＬ−２＋・・・＋ｍ０であるステップ、（ｉｉ）ｆ（ｘ）およびｇ（ｘ）を互いの関数としてテーブルに変換するステップ、（ｉｉｉ）ｋ＝７およびＬ＝７の代表的な場合を考慮すると、ｆｎ−１＝Ａ、ｆｎ−１＝Ａ＋Ｂ、ｆｎ−１＝Ａ＋Ｂ＋Ｃ、・・・、ｆ２＝Ｅ＋Ｆ＋Ｇ、ｆ１＝Ｆ＋Ｇ、ｆ０＝Ｇを得るステップであって、式中、Ａ、Ｂ、Ｃ、・・・、Ｇは除数係数であるステップ、および（ｉｖ）ｃｋ−２＝ｆｋ−２、ｃｋ−２＝ｆｋ−２、・・・、ｃ１＝ｆ１、ｃ０＝ｆ０を得るステップを備える並列巡回冗長検査（ＣＲＣ）を行うためのアルゴリズムの構成方法を提供する。
【０００７】
巡回冗長検査で使用されるチェックサムを計算する、一般的で、多項式ジェネレータの長さおよびデータストリームの長さとは無関係なアルゴリズムの構成方法を提供することが本発明の目的であり、本方法は、最も遅い合成組合せ論理経路の伝播遅延だけにより制限されるデジタル論理実装で具体化することができ、典型的には単一のシステム・クロック・サイクルの１周期以内で計算することができる。
【０００８】
本発明の他の目的は、巡回冗長検査で使用されるチェックサムを計算するアルゴリズムの構成方法を提供することであり、合成可能な論理回路の形で方法の具体化および実装を簡素化するために、一続きの情報、および対応する多項式ジェネレータがテーブルに変換される。
【０００９】
本発明のこれらおよび他の目的、様態、利点、および特徴が、添付図面と併せて提示される、好ましい実施形態についての以下の詳細な説明を考慮したとき、当業者によりより完全に理解され、認識されるであろう。
【００１０】
添付図面は、例示する目的のためだけに提供され、本発明を限定する範囲を規定するものとして意図されるものではないことを理解されたい。図面は本発明の好ましい実施形態を例示する。
【図面の簡単な説明】
【００１１】
【図１】本発明による、７ビット・データ・ストリームおよび７ビット多項式ジェネレータを具体的に表現する変換テーブルを示す。
【図２】本発明による、代表的なＣＲＣチェックサムの計算を示す。
【図３】従来の方法の生成多項式Ｇ（ｘ）＝ｘ５＋ｘ２＋１を使用する、ＬＦＳＲとしてのＵＳＢ  ＣＲＣ５実装を示す。
【発明を実施するための形態】
【００１２】
ＣＲＣの計算は多項式演算の形で行われ、それにより、アルゴリズムの基本は、送信者と受信者の両方が同じ多項式ジェネレータシーケンスを使用することが前提であり、情報のストリーム（パケットまたはフレームとしても知られている）が送信される前に、選択された多項式ジェネレータによる多項式の除算によって計算が行われる。多項式の除算の結果得られた剰余が、送信すべき当初の情報のパケットに付加される。そこから、情報が送信され、受信者が受信したとき、受信した情報のパケットに対して同じ多項式の除算を行い、結果の剰余がゼロに等しいかどうかを検査することにより、検証を行うことができ、したがって、剰余がゼロに等しくないときに、誤りが容易に判定される。
【００１３】
本発明では、本方法は、ＣＲＣで使用されるチェックサムを計算するアルゴリズムの構成方法を提供するために利用される。数学的関連では、上記の開示を以下の表現により説明することができる。
【００１４】
データストリームを、係数ｍＬ−１、ｍＬ−２、・・・を有するｍ（ｘ）で表し、多項式の次数それぞれをｘｎ−１で表し、この場合ｎは、範囲が｛０，ｎ−１｝の多項式の次数と仮定すると、データストリームを次式で現すことができる。
ｍ（ｘ）＝ｍＬ−１ｘＬ−１＋ｍＬ−２ｘＬ−２＋ｍＬ−２ｘＬ−２＋・・・＋ｍ０
式中、Ｌはデータパケットの長さである。
【００１５】
さらに、多項式ジェネレータを同様に次式で表すことができる。
ｇ（ｘ）＝ｇｋ−１ｘｋ−１＋ｇｋ−２ｘｋ−２＋ｇｋ−２ｘｋ−２＋・・・＋ｇ０
式中、ｋは多項式ジェネレータの長さである。本発明では、計算されるＣＲＣチェックサムを次式で表すことができる。
ｃ（ｘ）＝ｃｋ−２ｘｋ−２＋ｃｋ−３ｘｋ−３＋ｃｋ−４ｘｋ−４＋・・・＋ｃ０
【００１６】
ＣＲＣを計算し、ｍ（Ｌ）に付加した後の、送信すべき最終的な情報のフレームを以下のように表すことができる。
ｆ（ｘ）＝ｍ（ｘ）ｘｋ−１＋ｃ（ｘ）
【００１７】
さらに、（ｋ−１ビットだけ付加された）データストリームおよび多項式ジェネレータから作られる商をｑ（ｘ）とすると、ｍ（ｘ）を次式のように書き直すことができる。
ｍ（ｘ）ｘｋ−１＝ｇ（ｘ）ｑ（ｘ）＋ｃ（ｘ）
この場合、次式から解が得られる。
ｃ（ｘ）＝剰余｛（ｍ（ｘ）ｘｋ−１）／ｇ（ｘ）｝
【００１８】
従来技術では、図２は、ｃ（ｘ）がどのように具体化されるかを示し、多項式の除算からなる本方法は、過去に関する情報を提示し、かつ剰余となる最終結果の値に最終的に到達するために、過去に関する情報を保持する必要があることを意味することを理解することができる。デジタル論理回路システムでは、多項式ジェネレータに関連する、最上位の次数までの多項式の次数にそれぞれ対応するいくつかの線形帰還シフトレジスタ（ＬＦＳＲ）が、多項式ジェネレータの次数が１である場合はいつでも、追加の排他的論理和（ＸＯＲ）論理回路と直列にカスケード接続される。その一例を図３で参照することができる。
【００１９】
その結果、図３の例は、所与の送信されたストリームに関するＣＲＣを受信側で計算するために、最小限ｋ−１（ここで、ｋ−１は多項式ジェネレータに関連する最高次数である）のクロックサイクル数を必要とする。
【００２０】
図１は、本発明による、７ビット・データ・ストリームおよび７ビット多項式ジェネレータからテーブルへの代表的な変換を示す。図示するように、ＣＲＣチェックサムを加えたデータストリーム（ｆ（ｘ）：ｆ０，ｆ１，ｆ２，ｆ３，・・・，ｆ１０，ｆ１１，ｆ１２）と多項式ジェネレータシーケンス（ｇ（ｘ）：ｇ０，ｇ１，・・・，ｇ５，ｇ６）の、本発明で説明するような変換テーブルにより、除数係数Ａ、Ｂ、・・・、Ｆ、Ｇが形成される。本発明によれば、除数係数を使用してＣＲＣシーケンスを計算する。
【００２１】
図２に示すように、追加の００００が１１００１００１１１に付加されたデータストリーム対して、多項式シーケンス１０１０１、すなわちｘ４＋ｘ２＋１による長い除算の計算が行われる。好ましい本実施形態では、最下部の剰余がＣＲＣチェックサムとして、データストリームに付加された追加の００００に取って代わる。
【００２２】
本発明の好ましい実施形態では、アルゴリズムを効率的に導き出すために、ｆ（ｘ）およびｇ（ｘ）は、図１に示すように互いの関数としてテーブルに変換される。代表的なＬ＝７およびｋ＝７の場合を取り上げると、この場合、余白の値は、結果として生じるゼロである。ｑ（ｘ）の数学的意義は、変換を行った後には重要ではなくなり、係数Ａ、Ｂ、Ｃ、・・・、Ｆ、Ｇが得られることを理解することができ、これらの係数を除数係数と呼ぶ。
【００２３】
多項式ジェネレータが、ｋ番目の次数０〜６から得られる全係数がすべて１であるようなものである特別な場合について考慮し、データストリームの長さとＣＲＣチェックサムの長さの合計（Ｌ＋（ｋ−１））をｎとすると、次式が得られる。
ｆｎ−１＝Ａ、ｆｎ−１＝Ａ＋Ｂ、ｆｎ−１＝Ａ＋Ｂ＋Ｃ、・・・、ｆ２＝Ｅ＋Ｆ＋Ｇ、ｆ１＝Ｆ＋Ｇ、ｆ０＝Ｇ
したがって、
ｃｋ−２＝ｆｋ−２，ｃｋ−２＝ｆｋ−２、・・・、ｃ１＝ｆ１，ｃ０＝ｆ０
である。
【００２４】
多項式ジェネレータが特別な場合ではなければ、上記の導出には、シフトされた除数係数の行に対して、図１に示すように多項式ジェネレータの行インデックスに基づき余分な乗算因数が必要である。
【００２５】
本発明によれば、典型的には１クロックサイクル以内に計算され、最も遅い合成組合せ論理経路の伝播遅延だけにより制限される、データまたは多項式ジェネレータの長さとは無関係なＣＲＣチェックサムのためのシステムを生成するためのアルゴリズムが、開示されるように使用されている。本システムを生成することにより、過去に関する知識を必要とすることなく、または記憶を意味するフィードバックを実装する必要なしに、構成可能な多項式ジェネレータによる多項式の除算をデータシーケンスに対して行うことにより最終結果の剰余が決定される。本発明は、全体の商の残りのｋ−１ビットが多項式の除算の剰余となるものであるということを意味する、剰余がゼロであると仮定することにより、多項式の除算を行うことから得られる結果の商の係数を決定することで新規な手法を提供する。
【００２６】
したがって、本明細書の本発明の概念を逸脱することなく、さらに多くの修正形態が可能であることが当業者には明らかであろう。したがって、本発明は、添付の特許請求の範囲の精神以外で制限されない。
【図１】
2018515985.tif 000003
【図２】
2018515985.tif 000004
【図３】
2018515985.tif 000005
【国際調査報告】
2018515985.tif 000006
2018515985.tif 000007