JPH05244016A

JPH05244016A - Ｃｒｃ計算回路

Info

Publication number: JPH05244016A
Application number: JP4039001A
Authority: JP
Inventors: Yasushi Kakukawa; 泰史各川
Original assignee: Toshiba Corp
Current assignee: Toshiba Corp
Priority date: 1992-02-26
Filing date: 1992-02-26
Publication date: 1993-09-21

Abstract

(57)【要約】【目的】この発明は、簡易な構成でＣＲＣ符号の計算速
度をより一層高速化することができるＣＲＣ計算回路を
提供することを目的としている。【構成】ｎ次多項式の上位ｋ項が取り得る全ての式をｍ
次基本式で除算した各剰余が記録されたメモリ２２と、
多項式の上位ｋ項に付加された各係数に基づいてメモリ
２２のアドレスを指定し対応する剰余を読み出すアクセ
ス手段２１と、このアクセス手段２１で読み出された剰
余を多項式の上位ｋ項を除く下位項に加算する加算手段
２０とを備えている。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】この発明は、デジタルデータのエ
ラーチェックのためのＣＲＣ（Cyclic Redu-ndancy Che
ck）符号を計算するＣＲＣ計算回路の改良に関する。

【０００２】

【従来の技術】周知のように、近年におけるコンピュー
タのデータ処理速度の向上は著しく、扱うデータ量も増
大してきており、これに伴って、コンピュータの周辺装
置も大容量化が進み、その大量のデータに対するエラー
チェックが大きな問題となっている。

【０００３】現在では、デジタルデータのエラーチェッ
クには一般にＣＲＣが利用されている。ＣＲＣは、一連
のデータ列を高次の多項式と考え、その多項式をある基
本式Ｐ（ｘ）で除算し、その剰余（ＣＲＣ符号）を元の
データ列の末尾に付加するものである。データのエラー
チェックは、ＣＲＣ符号を付加したデータ列を先の基本
式Ｐ（ｘ）で除算することにより行なわれ、エラーがな
ければ除算結果は０となる。

【０００４】すなわち、元のデータ列である被除式をｆ（ｘ）＝ａ_nｘⁿ ＋ａ_n-1ｘ^n-1 ＋ａ_n-2ｘ^n-2 ＋……＋ａ₀ｘ⁰ とし［ただし、ａ_i（ｎ≦ｉ≦０）は１または０］、こ
の被除式ｆ（ｘ）を基本式Ｐ（ｘ）で割った商をＡ
（ｘ），剰余（ＣＲＣ符号）をｒ（ｘ）とすると、ｆ（ｘ）＝Ａ（ｘ）・Ｐ（ｘ）＋ｒ（ｘ）となる。

【０００５】図２は、ＣＲＣ符号を計算するための従来
のＣＲＣ計算回路を示している。図中符号１１は入力端
子で、上記被除式ｆ（ｘ）のｘの次数の上位から順にそ
の項の係数ａ_iが入力される。この入力端子１１に入力
された係数ａ_iは、入力端子１２に供給されるクロック
ＣＫに同期してラッチ動作を行なう直列接続された８個
のＤ（Delay ）タイプのラッチ回路１３ａ〜１３ｈによ
り、図中右方向に順次シフトされる。

【０００６】一方、図２中符号１４は入力端子で、上記
基本式Ｐ（ｘ）［ここではｘ⁷ 以下の次数の式とする］
の係数ａ_jが設定されている。この係数ａ_jは、入力端
子１５に供給される書き込み／読み出し信号ＷＲが書き
込み状態になることにより、８ビットのレジスタ１６に
ラッチされる。この場合、係数ａ_jは、ｘの次数の上位
から下位にかけてレジスタ１６の図中右側から左側のビ
ットにラッチされる。そして、レジスタ１６にラッチさ
れた各係数ａ_jは、入力端子１５に供給される書き込み
／読み出し信号ＷＲが読み出し状態になることにより、
各アンド回路１７ａ〜１７ｈの一方の入力端に出力され
ている。

【０００７】これらアンド回路１７ａ〜１７ｈの各他方
の入力端には、最終段のラッチ回路１３ｈの出力が供給
されている。このため、最終段のラッチ回路１３ｈから
１が出力されたとき、つまり被除式ｆ（ｘ）の最高次の
係数ａ_nが出力されたとき、各アンド回路１７ａ〜１７
ｈはゲート開状態となり、基本式Ｐ（ｘ）の各係数ａ_j
が出力される。

【０００８】ここで、各ラッチ回路１３ａ〜１３ｈの前
段には、入力端子１１及び前段のラッチ回路１３ａ〜１
３ｇから出力される係数ａ_iと、アンド回路１７ａ〜１
７ｈから得られる係数ａ_jとを排他的論理和演算する加
算回路１８ａ〜１８ｈが設置されており、ここに、被除
式ｆ（ｘ）が基本式Ｐ（ｘ）で除算される。そして、被
除式ｆ（ｘ）の全データ列の係数ａ_iが入力端子１１に
入力された後、入力端子１１に８ビット分の０データを
入力することにより、各ラッチ回路１３ａ〜１３ｈにＣ
ＲＣ符号である剰余ｒ（ｘ）の各次数の係数ａ_k（６≦
ｋ≦０）が得られ、ＣＲＣ符号が生成されることにな
る。

【０００９】しかしながら、上記のような従来のＣＲＣ
計算回路では、ラッチ回路１３ａ〜１３ｈによる被除式
ｆ（ｘ）の次数ｎだけのシフト動作が必要となり、例え
ば２５６バイトのデータ列からＣＲＣ符号を生成するに
は、２５６×８＝２０４８クロックが必要であり、計算
速度にハード的な限界が生じることになる。

【００１０】

【発明が解決しようとする課題】以上のように、従来の
ＣＲＣ計算回路では、計算速度にハード上の制限が生じ
るという問題を有している。

【００１１】そこで、この発明は上記事情を考慮してな
されたもので、簡易な構成でＣＲＣ符号の計算速度をよ
り一層高速化することができる極めて良好なＣＲＣ計算
回路を提供することを目的とする。

【００１２】

【課題を解決するための手段】この発明に係るＣＲＣ計
算回路は、一連のデータ列をｎ次（ｎは正の整数）の多
項式ｆ（ｘ）で表わし、該多項式ｆ（ｘ）をｍ次（ｍは
正の整数）の基本式Ｐ（ｘ）で除算した剰余ｒ（ｘ）を
ＣＲＣ符号として生成するものを対象としている。そし
て、多項式ｆ（ｘ）の上位ｋ項（ｋはｋ＜ｎの正の整
数）が取り得る全ての式を基本式Ｐ（ｘ）で除算した各
剰余が記録されたメモリと、多項式ｆ（ｘ）の上位ｋ項
に付加された各係数に基づいてメモリのアドレスを指定
し対応する剰余を読み出すアクセス手段と、このアクセ
ス手段で読み出された剰余を多項式ｆ（ｘ）の上位ｋ項
を除く下位項に加算する加算手段とを備えるようにした
ものである。

【００１３】

【作用】上記のような構成によれば、多項式ｆ（ｘ）の
上位ｋ項を基本式Ｐ（ｘ）で除算した剰余をメモリから
アクセスして多項式ｆ（ｘ）の下位項に加えるようにし
たので、ｋ回のシフト動作が１回のメモリのアクセス動
作に置換されることになり、簡易な構成でＣＲＣ符号の
計算速度を従来に比してｋ倍に高速化することができ
る。

【００１４】

【実施例】以下、この発明の一実施例について図面を参
照して詳細に説明する。図１において、符号１９は４ビ
ットの入力端子で、被除式ｆ（ｘ）のｘの次数の上位か
ら４ビットづつ順にその項の係数ａ_iが入力される。こ
の入力端子１９に供給された係数ａ_iは、排他的論理和
演算機能を有する８ビットレジスタ２０の図中左側４ビ
ットに供給される。この８ビットレジスタ２０の左側４
ビットに取り込んだデータは、右側４ビットに移行させ
ることができ、右側４ビットに取り込んだデータは、４
ビットレジスタ２１に移行させることができる。

【００１５】そして、この４ビットレジスタ２１に取り
込んだデータは、８ビット×２⁴ 語構成のメモリ２２
に、その８ビットで指定されるアドレスの内の４ビット
アドレスとして供給される。また、このメモリ２２に
は、７次の基本式Ｐ（ｘ）＝ａ₇ｘ⁷ ＋ａ₆ｘ⁶ ＋ａ₅ｘ⁵ ＋……＋ａ₁ｘ¹ ＋ａ₀ｘ⁰ の係数ａ_j（７≦ｊ≦０）が８ビットの入力端子２３を
介して入力されるとともに、アドレスの残りの４ビット
が４ビットの入力端子２４を介して供給されている。

【００１６】ここで、上記メモリ２２に記憶されている
内容について説明する。今、ｘの１１次から８次までの
項を持つ式ｇ（ｘ）＝ａ₁₁ｘ¹¹＋ａ₁₀ｘ¹⁰＋ａ₉ｘ⁹ ＋ａ₈ｘ⁸ を考えると、その各係数ａ_m（１１≦ｍ≦８）は０また
は１であるので、この式ｇ（ｘ）は２⁴ ＝１６通りが存
在することになる。そして、メモリ２２には、この式ｇ
（ｘ）を基本式Ｐ（ｘ）で除算した剰余が書き込まれて
いる。すなわち、除算した商をＡ（ｘ），剰余をｈ
（ｘ）とすると、ｇ（ｘ）＝Ａ（ｘ）・Ｐ（ｘ）＋ｈ（ｘ）であり、剰余ｈ（ｘ）も１６種類存在することになる。

【００１７】そして、今、入力端子１９に被除式ｆ（ｘ）＝ａ₁₁ｘ¹¹＋ａ₁₀ｘ¹⁰＋……＋ａ₁ｘ¹ ＋ａ₀ｘ⁰ の各係数ａ_i（１１≦ｉ≦０）が入力されたとする。す
ると、４ビットレジスタ２１には、係数ａ₁₁〜ａ₈がセ
ットされ、８ビットレジスタ２０には、係数ａ₇〜ａ₀
がセットされる。このとき、メモリ２２からは、（ａ₁₁ｘ¹¹＋ａ₁₀ｘ¹⁰＋ａ₉ｘ⁹ ＋ａ₈ｘ⁸ ）／Ｐ（ｘ）の剰余ｈ（ｘ）が出力され、８ビットレジスタ２０の内
容と排他的論理和演算が行なわれる。

【００１８】次に、８ビットレジスタ２０の右側４ビッ
トの内容を４ビットレジスタ２１に移行し、８ビットレ
ジスタ２０の左側４ビットの内容を右側４ビットに移行
し、８ビットレジスタ２０の左側４ビットに入力端子１
９に供給された新たな４ビットの係数ａ_iを移行する。
すると、上記と同様に、メモリ２２から４ビットレジス
タ２１の内容で決まる剰余ｈ（ｘ）が出力され、８ビッ
トレジスタ２０の内容と排他的論理和演算が行なわれ
る。

【００１９】すなわち、この回路は、被除式ｆ（ｘ）の
上位４項を基本式Ｐ（ｘ）で除算した剰余ｈ（ｘ）を被
除式ｆ（ｘ）の上位４項を除く下位８項に加え、その
後、被除式ｆ（ｘ）を上位側に４項分シフトさせた上位
４項を基本式Ｐ（ｘ）で除算した剰余ｈ（ｘ）を被除式
ｆ（ｘ）の上位４項を除く下位４項に加えるという動作
を繰り返すことでｆ（ｘ）／Ｐ（ｘ）を実現していくも
ので、最後に８ビットレジスタ２０に残ったデータがＣ
ＲＣ符号となる。

【００２０】したがって、上記実施例のような構成によ
れば、被除式ｆ（ｘ）の上位４項を基本式Ｐ（ｘ）で除
算した剰余ｈ（ｘ）をメモリ２２からアクセスして被除
式ｆ（ｘ）の下位項に加えるようにしたので、４回のシ
フト動作が１回のメモリ２２のアクセス動作に置換され
ることになり、簡易な構成でＣＲＣ符号の計算速度を従
来に比して４倍高速化することができる。また、上記実
施例では４ビット毎の処理としたが、これに限らず例え
ば８ビット毎の処理とすれば、ＣＲＣ符号の計算速度を
従来に比して８倍高速化することができる。

【００２１】ここで、具体的な計算例について説明す
る。すなわち、被除式ｆ（ｘ）を基本式Ｐ（ｘ）で除算
したときの商をＡ（ｘ），剰余をｒ（ｘ）とすると、先
に述べたように、ｆ（ｘ）＝Ａ（ｘ）・Ｐ（ｘ）＋ｒ（ｘ） …（１）が成立し、剰余ｒ（ｘ）がＣＲＣ符号となる。そこで、
被除式ｆ（ｘ）を、基本式Ｐ（ｘ）の最高次数以上の項
のみの式ｆ₁（ｘ）と、基本式Ｐ（ｘ）の最高次数未満
のみの式ｆ₂（ｘ）とに分け、ｆ（ｘ）＝ｆ₁（ｘ）＋ｆ₂（ｘ） …（２）と表わすと、（１），（２）式より、ｆ（ｘ）＝Ａ₁（ｘ）・Ｐ（ｘ）＋ｒ₁（ｘ）＋Ａ₂（ｘ）・Ｐ（ｘ）＋ｒ₂（ｘ） …（３）となる。

【００２２】この場合、式ｆ₂（ｘ）の次数は基本式Ｐ
（ｘ）の最高次数よりも低いのだから、（３）式におい
てＡ₂（ｘ）・Ｐ（ｘ）の項は０となる。つまり、ｆ₂（ｘ）＝ｒ₂（ｘ）である。このため、ｆ（ｘ）＝Ａ₁（ｘ）・Ｐ（ｘ）＋ｒ₁（ｘ）＋ｒ₂（ｘ）となり、ｒ₁（ｘ）＋ｒ₂（ｘ）がＣＲＣ符号となる。

【００２３】このため、ＣＲＣ符号の計算においては、
基本式Ｐ（ｘ）の最高次数以上の項だけで計算を施した
後に、残りの項を余りに加えればよい。具体的には、Ｐ（ｘ）＝ｘ⁴ ＋ｘ³ ＋１＝ 11001 ｆ（ｘ）＝ｘ⁹ ＋ｘ⁷ ＋ｘ⁵ ＋ｘ² ＋ｘ¹ ＋１＝1010100111 ＝1010100000＋00111 ｆ₁（ｘ）＝ｘ⁹ ＋ｘ⁷ ＋ｘ⁵ ＝Ａ₁（ｘ）・Ｐ（ｘ）＋ｒ₁（ｘ）＝1010100000 ｆ₂（ｘ）＝ｘ⁴ ＋ｘ³ ＋１＝ 00111 ｒ（ｘ）＝ｒ₁（ｘ）＋ｆ₂（ｘ）＝ｒ₁（ｘ）＋00111 となる。なお、この発明は上記実施例に限定されるもの
ではなく、この外その要旨を逸脱しない範囲で種々変形
して実施することができる。

【００２４】

【発明の効果】以上詳述したようにこの発明によれば、
簡易な構成でＣＲＣ符号の計算速度をより一層高速化す
ることができる極めて良好なＣＲＣ計算回路を提供する
ことができる。

【図面の簡単な説明】

【図１】この発明に係るＣＲＣ計算回路の一実施例を示
すブロック構成図。

【図２】従来のＣＲＣ計算回路を示すブロック構成図。

【符号の説明】

１１，１２…入力端子、１３ａ〜１３ｈ…ラッチ回路、
１４，１５…入力端子、１６…レジスタ、１７ａ〜１７
ｈ…アンド回路、１８ａ〜１８ｈ…加算回路、１９…入
力端子、２０…８ビットレジスタ、２１…４ビットレジ
スタ、２２…メモリ、２３，２４…入力端子。

Claims

【特許請求の範囲】

【請求項１】一連のデータ列をｎ次（ｎは正の整数）
の多項式ｆ（ｘ）で表わし、該多項式ｆ（ｘ）をｍ次
（ｍは正の整数）の基本式Ｐ（ｘ）で除算した剰余ｒ
（ｘ）をＣＲＣ符号として生成するＣＲＣ計算回路にお
いて、前記多項式ｆ（ｘ）の上位ｋ項（ｋはｋ＜ｎの正
の整数）が取り得る全ての式を前記基本式Ｐ（ｘ）で除
算した各剰余が記録されたメモリと、前記多項式ｆ
（ｘ）の上位ｋ項に付加された各係数に基づいて前記メ
モリのアドレスを指定し対応する剰余を読み出すアクセ
ス手段と、このアクセス手段で読み出された剰余を前記
多項式ｆ（ｘ）の上位ｋ項を除く下位項に加算する加算
手段とを具備してなることを特徴とするＣＲＣ計算回
路。