JPH03216026A - 並列的に発生された循環冗長エラーチェックコードにアクセスする装置及び方法 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】 皮逝旦１ 本発明は、概略、循環冗長エラーチェックコド発生器に
関するものであって、更に詳細には、本発明は、バイト
幅デークを並列的に処理し且つ発生された循環エラーチ
ェックコードへアクセスする手段を与える循環的エラー
チェックコード発生器に関するものである。

兜汰肢莢 通信システムにおいては、データは、典型的に、処理ユ
ニットと、周辺ユニット、格納装置又はユーザターミナ
ルとの間で転送される．読取り、書込み又は実際の伝送
プロセスにおいてエラーが導入される場合がある。エラ
ー制御は、コンピュータ及び通信システムの構成におけ
る重要な部分となっている．エラー検知のために使用さ
れる１つの方法は、情報担持ビットのブロックの終りに
冗長ビットと呼ばれる１つ又はそれ以上のビットを付加
する．冗長ビットは、何等データ情報を担持するもので
はなく、それは、情報を担持するピットストリームの正
確性を決定するために使用されるに過ぎない． 循還冗長チェック（．Ｃ　Ｒ　Ｃ　）は、受信デジタル
情報が正しいものであることを検証するために使用され
るアルゴリズムによるエラー検知技術である。デジタル
データワード（ｄ）は多項式Ｄ（Ｘ）として書かれ、該
データビットの各々は各項に対する係数である。データ
多項式Ｄ　（ｘ）は、所定の生成元多項式Ｇ　（ｘ）に
よってモジュロ２割算され、且つこの割算の残部Ｒ　（
ｘ）は循環冗長チェック（ＣＲＣ）文字としてデジタル
デークワードｄに添付される．該残部は、元の多項式よ
りも短く、各データワードに対する独特の数字である．
生成元多項弐Ｇ　（ｘ）の次数が高ければ高い程、エラ
ー検知の可能性はより大きいが，ハードウエアにおいて
割算を実行することが一層困難であり、且つその情報を
送るために犠牲とされる帯域幅の量は一層大きい． メッセージ内に包含されるＣＲＣは、同一の割算を実行
することにより、受信端部において得られるＣＲＣ文字
と比較される．これら２つのＣＲＣが合致する場合には
、そのメッセージは正しいものと仮定される．それらが
合致しない場合には受信端乃至は受信ターミナルは何ら
がの適宜の動作を行う。

どのようにしてこの文字Ｃ，Ｒ　Ｃが発生するがという
ことを示゛すために、デジタルデータヮードｄがＬ個の
ビットから構成されるものとする、即ち、ｄ＝ａＬ−　
１．．．ａｔ　ａｏ．尚ａ＋＝０又は１である．（Ｌ−
１）次数の多項式Ｄ　（ｘ）は次式で表わされる． Ｌ−１ Ｄ（Ｘ）”ａＬ−＋ＸＬ−’　”””　ａ＋Ｘ’÷ａａ
Ｘ０＝Σ　ａ＋Ｘ’ｉ＝０　　　（１） 前述した如く、ＣＲＣは単一文字又はＲ個のビットとす
ることが可能であり、尚Ｒ＜Ｌである。Ｄ　（ｘ）は　
ｘｒで乗算される．このことは、メッセージビットをｒ
個の位置左側ヘシフトすることと等価である．　Ｇ　（
ｘ）を次数ｒの「ゼネレータ（ｇｅｎｅｒａｔｏｒ、即
ち発生器ないし生成元）」即ち「チェック用」多項式で
あるとし、その係数は０又は１であるとする．シフトさ
れた多項式データＤ　（ｘ）はＧ　（ｘ）で割算し、次
式が得られる． 向、Ｒ　（ｘ）　＝残部（即ち、ＣＲＣ）Ｑ　（ｘ）　
＝商（ｑｕｏｔｉｅｎｔ）ｍｏｄ　　２＝計算がモジュ
ロ２で行われるモジュロ２演算においては、全ての加算
及び減算の結果は、２で割算した後の「通常」の和又は
差の残部である．例えば、モジュロ２演算においては、 １＋１＝０ １＋１＋１＝１ 注意すべきことであるが、１つの位置から次の位置へｒ
ｃａｒｒｙ　（キャリイ）」又はｒｂ　ｏ　ｒ　ｒＯＷ
（ボロー）」が発生されることはない．式（ｚ）から、
次式が得られる． Ｒ　ｆｘ）　；ｘ’　Ｄ（ｘ）　＋　Ｑ（ｘｌ　Ｇ（ｘ
）　ｍｏｄ　２　　　（　４　）ＣＲＣを添付したコー
ド化データワード（即ち、データ）はＷ（ｘ）であり、
次式で表わされる。

ｌＨｘｌ　＝Ｑｆｘ）　Ｇ（ｘｌ　＝ｘ’　Ｄ［ｘ）＋
Ｒ（ｘｌ　ｍｏｄ２　（５　）Ｗ（ｘ）は次数ｒ＋ｒ−
１であり，且つ元のＬ個のメッセージビット（ｘ’　Ｄ
　（ｘ）→及びｒ個のチェックビット（Ｒ　（Ｘ）項）
）を有している．更に、Ｗ（ｘ）は、正確にＧ　（ｘ）
によって割算可能である．Ｗ（ｘ）の係数は送信される
ものである．受信端において、Ｗ（ｘ）はＧ　（ｘ）に
よって割算され、且つこの場合における残部は０でなけ
ればならない．そうでない場合、即ち残部が発生される
場合には、エラーが発生したこととなる． 従って、ＣＲＣ及び検知プロセスにおいて３つのステッ
プが行われる． （−１）ＣＲＣ　（残部多項式）を発生するためにデー
タ多項式を生成元多項式によって割算することによるＣ
ＲＣの発生 （ｚ）データと共にＣＲＣの送信 （３）エラーチェック一一受信された全多項式は送信デ
ータとそれに続＜ＣＲＣとから構成されており、生成元
多項式によって割算される．該残部がＯである場合には
、エラーは発生していない。

該残部が０でない場合には，送信期間中に少なくとも１
つのエラーが発生したことになる．例えばＦＤＤＩ等の
ようなあるシステムにおいては、残部それ自身ではなく
残部の１の補数を実際に送信する。このようなシステム
においては、受信器は、送信されたワードの計算された
残部を、予定される一定値と比較し、且つ合致がない場
合にはエラーを報告する．このようなシステムは、何れ
かのメッセージの終りに偶発的に一連の０が付加される
ことに対して影響を受けにくいものとしている。

例えば、データワードｄが１０１００１０００１である
場合、Ｄ　（ｘ）＝ｘ’　＋ｘ’　＋ｘ’　＋１である
。Ｇ　（ｘ）＝ｘ’　＋ｘ’　＋ｘ”　＋１である場合
には、Ｇ　（ｘ）によるｘ５Ｄ　（ｘ）のモジュロ２割
算は次式の結果を発生する。

Ｑ　（ｘ）＝ｘ’　＋ｘ’　＋ｘ’及びＲ　（ｘ）＝ｘ
’　＋ｘ３ Ｗ（ｘ） ＝ｘ”＋ｘ′２＋ｘ”　＋ｘ’　＋ｘ’　＋ｘ３及び、
ＣＲＣを添付した送信データワードは次の如くに表わさ
れる。

１０１００１０００１　　　　　　１１０００元のデー
ク　　　　　　　　　　　ＣＲＣビットエラーチェック
コードを発生するために複数個のデータビットを並列的
に読取り且つ並列的にシフトする並列ビットＣＲＣ処理
は公知である．Ｎ個のビットを並列的にシフトさせるこ
とにより、並列回路における１個のシフトは直列システ
ムにおけるＮ個のシフトと等価である．更に、複数個の
データビットが並列的に処理されるＣＲＣ発生回路を実
施する場合に、ハードウエア要素のあるものを共用する
ことが可能なことは公知である．受信データは２進デー
タであるので、ＣＲＣを発生するための排他的ＯＲ型論
理要素と関連して使用する複数個のシフトレジスタをＣ
ＲＣ発生回路が使用することが可能であることも公知で
ある．１９７２年１１月２１日に発行された発明者Ｐａ
ｔｅ　１の「マルチチャンネルシフトレジスタ（（Ｍｕ
ｌｔｉ−Ｃｈａｎｎｅｌ　　ＳｈｉｆｔＲｅｇｉｓｔｅ
ｒ）Ｊという名称の米国特許第３，７０３．７’０５号
は、式（４）に従ってエラーチェックコードを発生する
ために入力データビットストリームを並列的に処理する
マルチチャンネルフィードバックシフトレジスク回路を
開示している． 入力データビットは、夫々、並列的に受信され、且つエ
ラーコード発生回路は、エラーチェックコードを発生す
るために使用される特定の生成元多項式に従って配列さ
れる．上記特許の開示するところによれば、次数ｒの多
項弐Ｇ　（ｘ）の場合、Ｙ個のビットを並列的に処理す
る並列フィードバックシフトレジスク回路を発生するこ
とが可能である。且つなお、Ｙ≦Ｒである。

しかしながら、上掲した特許は、最後の受信データバイ
トに対して発生されるエラーチェックコードをどのよう
にして読出すかということを記載するものでも示唆する
ものでもない。

１９８６年６月３日に発行された発明者Ｍｅａｄの「準
並列１ｆｔｊ＋　ｂｉ冗長チェック（Ｑｕａｓｉ　　Ｐ
ａｒａｌｌｅｌ　　Ｃｙｃｌｉｃ　　Ｒｅｄｕｎｄａｎ
ｃｙ　　ｃｈｅｃｋ）Ｊという名称の米国特許第４．５
９３　　３９３号は，エラーチェックエンコード及びデ
コード回路が、並列的に複数個の入力ビットを受信し且
つ該データを並列的に処理することによりＣＲＣを発生
することが可能であることを開示している．該ビットは
、第一組の排他的ＯＲゲート内へ読込まれ、且つその出
力は第二組の排他的ＯＲゲート内へ入力される．この第
二組の排他的ＯＲゲートからの出力は、第三組の排他的
ＯＲゲート内へ入力され、尚、各組は、８個の排他的Ｏ
Ｒゲートを有している．なぜならば、８ビットのデータ
が並列的に処理されるからである。第一クロックパルス
において、第三組のゲートから出力される信号はフリツ
プフロツブ内へ転送され、且つ第二クロツクパルスにお
いて、該信号が第一組のフリップフロツブから第二組の
フリップフロツプへシフトされる．第二組のフリツブフ
ロツブからの出力は、ＡＮＤゲートへ供給され、そこで
該信号がＡＮＤ処理されてＣＲＣ信号を発生する。シス
テムが複数個のビットを並列的に処理することによりＣ
ＲＣを発生する間に、該システムはハードウエア要素を
共用することはない． 同様に、１９８５年２月５日に発行された発明者ＬｅＧ
ｒｅｓ　１　ｅｙの［並列循環冗長チェック回路（Ｐａ
ｒａｌ１、ｅｌ　　Ｃｙｃｌｉｃ　　Ｒｅｄｕｎｄａｎ
ｃｙ　　Ｃｈｅｃｋｉｎｇ　　Ｃｉｒｃｕ１ｔ）」と言
う名称の米国特許第４，４９８，１７４号は、データビ
ットが並列的に入力され且つ並列的に処理されるＣＲｃ
エンコード及びデコド回路を示している，１９７８年８
月８日に発行された発明者Ｎａｋａｍｕｒａの「並列処
理エラー補正システム（Ｐａｒａｌｌｅｌ−Ｐｒｏｃｅ
ｓｓｉｎｇ　　Ｅｒｒｏｒ　　Ｃｏｒｒｅｃｔｉｏｎ　
　Ｓｙｓｔｅｍ）Ｊという名称の米国特許第４，１０５
，９９９号は、複数個のデータビットが並列的に受信さ
れ且つ使用される論理回路がＣＲＣを発生するために使
用される生成元多項式に基づいて配列されている並列Ｃ
ＲＣ発生器回路を開示している。しかしながら、何れの
並列処理エラーコード発生システムも、データシーケン
スを受信した後に、どのようにしてシフトレジスタがら
ＣＲＣを読出すかということを開示するものでも示唆す
るものでもない． 格納したエラーコード信号を読出すために使用すること
が可能なアプローチは、上部２４個の格納装置の入力端
上に２入力ＭＬＩＸを取付けることにより格納要素から
４ディープ（深さ）×８ビット幅シフトレジスクを形成
することである．各ＭＵＸへの２つの入力端の１つは、
前に格納要素の入力端へ配綿した論理から来るものとす
ることが可能である．他方の入力は、８個のいち早い格
納要素の出力端から直接的に来る．結果を読出すために
、これらのＭＵＸ、即ちマルチプレクサへの入力が変化
される．このアプローチの欠点は、それが、２４個のＭ
ＵＸを必要とし、そのことは実現上かなりの空間を占有
し、パワーを消費し、且つ長い経路に遅延を付加し、実
行速度を制限する可能性があるということである。

址−ｍ 本発明は、以゛上の点に鑑みなされたものであって、上
述した如き従来技術の欠点を解消し、並列データを処理
し、共通論理回路を共用し、且つ爾後のクロックサイク
ル期間中に格納部がら変更することなしに発生されたエ
ラーコードを読取る手段を提供する循環冗長エラーコー
ド発生装置及び方法を提供することである． １一戒 本発明によれば、複数個のデータ情報ビットがシフトレ
ジスタへ入力され、且つ入力分布マトリクスＢヘモジュ
ロ２加算される．この入力分布マトリクスＢは、どのよ
うにして入力データビットストリームＩが状態遷移マト
リクスＡへ加算されるかということを決定し、状態遷移
マトリクスＡにおいては、次の状態情報８１．２を発生
するために現在の状態情報が格納されている． 入力分布マトリクスＢは、複数個の論理要素とシフトレ
ジスタとから構成されており、それらは、送信されるべ
き情報データビットストリームへ添付される循環冗長エ
ラーチェックコードを発生されるために使用される生成
元多項式Ｇ　（ｘ）に基づいて所定の形態に配設されて
いる．状態遷移マトリクスも、複数個の論理要素とシフ
トレジスタとから構成されている．マトリクスＡ及びＢ
をハードウエアで実現する場合、システムは、マトリク
スＢのコラムはマトリクスＡのコラムの適切なサブセッ
ト、即ち副組を構成するという点において入力分布マト
リクスＢが状態遷移マトリクスＡと関連しているという
事実を利用する．格納レジスタから計算されたエラーチ
ェックコードを読取るために、格納レジスタを介してデ
ータがシフトされ、且つエラーチェックコードの一部が
Ｚビット幅×２人カマルチプレクサへ供給される。更に
変更されることなしにエラーチェックコードの残部を更
にシフトするためには、格納レジスクのあるものに対す
る入力端における論理排他的ＯＲゲートへ論理０信号を
印加させることが必要である．これらの０は、入力分布
マトリクスの出力端における複数個のＡＮＤゲートの各
々の１入力端へ論理Ｏ信号を印加するか、又は入力分布
ヤトリクスへの入力端における複数個のＡＮＤゲートの
各々の１入力端へ論理Ｏ信号を印加することによって強
制的に設定することが可能である。マトリクスＢへの入
力端において必要とされるＡＮＤゲートの数は、マトリ
クスＢの出力端におけるＡＮＤゲートの数よりも少ない
。

本発明によれば、並列データを処理し、共通の論理回路
を共用し、且つ爾後のクロツクサイクル期間中に格納部
から変更することなしに発生され？エラーコードを読出
す手段を提供する循環冗長エラーコード発生システム乃
至は装置が提供される．そのエラーチェックコードは、
送信されるデータワードへ添付される。

見立舅 以下、添付の図面を参考に、本発明の具体的実施の態様
について詳細に説明する． ｎビットＣＲＣ発生器の直列形態での実現化においては
、状態情報の各ビットは、次式で示される如く、前のビ
ット、即ち最大桁ビットと、入力ビットとの関数である
。

Ｓ　Ｊ　，　ｍ　＊　ｌ　”　Ｓ　ｊ　−　１　．、＋
ｇ，Ｘ　（ｉｍ　＋　Ｓｎ−＋．ｍ）　　（　９）尚、
ｎ＝生成元多項式の次数 ｍ＝処理されるビット数 ｊ＝状態変数Ｓ内の位置、尚Ｓｍ ”　（Ｓｏ，ｍ＋　Ｓ＋，ｍ　＋　・．　．　Ｓｎ−＋
，ｍ　）ＳＪ ＝ｍ番目のビットを処理する前の現在の状態変数Ｓｍの
ｊ−１番目のビット ｓＪ，ｆｆｌ◆ｌ ？ｍ番目のビットを処理した後の状態変数Ｓ．，のＪ番
目のビット ｇｒ＝生成元多項式Ｇ　（ｘ）のｊ番目の係数 ｉｎ＝ｍ番目の入力ビット ＋＝論理排他的ＯＲ操作を意味する ×＝論理ＡＮＤ操作 式（９）は、０≦ｊ≦ｎ−１の場合に成立し、尚Ｓ１、
ｍは０であると定義される． 式（９）は、実際にｎ個の別々の式を表わすものである
から、それは、次式の如くマトリクス形態で表わすこと
が可能である． Ｓｍｉｔ　：ＡＸｓ．　＋　Ｂｘｉｍ　　　　　　　　
（　１　０）尚、Ｓｆｆｌ＝現在の状態情報（即ち、ｍ
番目の入力ビットＩｆｆｉを処理する前の状態値）．Ｓ
ゆは前の受信デーク１，迄であるが それを包含しない（即ち、１１■ 迄）のデータストリームに対する残部 多項式である． Ａ＝状態遷移マトリクス．この状態遷移マトノクスは、
現在の状態Ｓ．が爾後の状態Ｓｆｆｉ４１に与える影響
を決定する．それは、Ｇ　（ｘ）に直接的に関係してい
る． Ｂ−入力分布ベクトル。この入力分布ベクトルは、爾後
の状態Ｓ　．ｎ＊　１に与える入力データ１ｍの影響を
記述する．それもＧ（ｘ）に関係している。

１ｆｆｉ＝入力データストリームエ。ＩＬＩのｍ番目の
入力データビット データストリーム■，内にＬ個のビットが存在すると仮
定すると、ピットストリームの全体は■。−Ｉ　Ｌ−１
のビットから構成される。エラーチェックコード（即ち
、エラーコード発生器システムの最終的状態）はＳＬで
ある。面、ｒｒｒ＝Ｌの場合、ＳＬ＝Ｓ．．である． チェックコード発生プロセスの開始時において、状態ビ
ット８は、何らかの所定の値Ｓ０にセットされる。その
値は、しばしば０であるが、好適実施例においては、及
び、ＦＤＤ　Ｉにおいては）、それは全て１である６該
データストリームの各ビットは、式（１０）に従って状
態変化を発生させる．入力ビット（　ｆｏ　．−　，ｉ
Ｌ−＋の全てのＬが処理されると、状態値ＳＬは残部多
項式（又は、エラーチェックコード）と等しい。

マトリクスＡは、複数個の行及び列から構成されており
、Ｎ−１番目のコラム、即ち列は、生成元多項式Ｇ　（
ｘ）の係数（ｇＪ）から構成されており、尚、０≦Ｊ≦
ｎ−１である。

ａＪ．＋！−１　＝ｇ　Ｊ（　１ｉ　）マトリクスＡの
残部は、対角線を外れた組が１である場合を除いて０で
埋め尽くす。Ｏ≦ｊ≦ｎ−１及び０≦ｋ≦ｎ−２の場合
には、ｊ＝ｋ−１であると、ａ　Ｊ，　ｗ　＝　１であ
り、そうでない場合には、ａ，，．＝０　　　　　　　
（１２）式（１１）及び（１２）において、ａｊ，ｋは
マトリクスＡのｋ番目の列のＪ番目の行における要素で
あり、且つａ，は生成元多項式Ｇ　（ｘ）におけるＪ番
目の項の係数である。

状態遷移マトリクスＡは係数（乃至は要素）のｎＸｎマ
トリクスであり、尚ｎは生成元多項式Ｇ（ｘ）における
最大の冨である．同様に、入力分布ベクトルをＢの要素
（ｂユ）は、次式の如く、生成元多項式に直接的に関係
している。

ｂ，＝ｇ，　　　　　　　　　　　（１３）２つのマト
リクスの間で乗算を実行する場合、結果的に得られるマ
トリクスＺにおける各項Ｚｊ．ｋは、第一マトリクス才
ペランドのｊ番目の行と第二マトリクスオペランドのｋ
番目の列とのクロス乗積を計算することによって形成さ
れる。

このクロス乗積は、一対の対応する要素を論理的にＡＮ
Ｄ処理し、次いでそれらの結果を一体的に排他的ＯＲ処
理することによって計算される。オペランドの一方がマ
トリクスではなくスカラである場合には、該乗積は、オ
ペランドマトリクスの各要素を該スカラで乗算すること
によって形成される。

２つのマトリクス又はベクトルの間の加算の場合、結果
的に得られるマトリクス又はベクトルの要素は、２つの
マトリクス又はベクトルの対応する要素を論理的に一体
的に排他的ＯＲ処理するこ？によって形成される。

従って、エラーチェックコード発生装置は、使用される
生成元多項式Ｇ　（ｘ）と、受信データシーケンスエ。

ＩＬＩと，分布マトリクスＢと、状態遷移マトリクスＡ
と、現在の状態情報Ｓとを使用して、ピットストリーム
エ。《，》の全体に対応するエラーチェックコードＳＬ
を発生する．受信した各データビットＩ■に対して、次
の状態Ｓ　ｍ＋＋が計算され、且つ前の８１の値と置換
し、且つ現在の状態情報となる．従って、データシーケ
ンスに対する次の状態情報を発生することは繰返しプロ
セスである。

本発明の循環冗長エラーチェックコード発生器は、例え
ば、ファイバ分散型データインターフェース（ＦＤＤＩ
）等のようなデータ伝送ネットワークと関連して使用し
、受信データ送信の完全性を決定することが可能である
。

ファイバ分散型データインターフェース（ＦＤＤＩ）プ
ロトコルは、オプチ力ルファイバ伝送媒体を使用する１
００メガビット／秒のトークンリングネットワークへ適
用される米国国家基準（ＡＮＳ）データ伝送スタンダー
ドである．ＦＤＤＩプロトコルは、ｒＦＤＤＩ一外観（
ＦＤＤＩ−ａｎ　　Ｏｖｅｒｖ　ｉ　ｅｗ）Ｊ　，ダイ
ジェスト・オブ・ペーパーズ・ｒ　ＥＥＥ・コンピュー
タ・ソサエティ国際会議、Ｃｏｍｐｃｏｎ　　　８７、
１９８７年１月の文献に記載されている。

ＦＤＤ　Ｉプロトコルはコンピュータ間及びコンピュー
タとそれと関連する大量記憶サブシステム及びその他の
周辺機器との間における高性能相互接続として意図され
ているものである。情報は、５ビットデータ文字乃至は
「記号」のシーケンスから構成される「フレーム」の形
態でＦＤＤＩリング上を送信される．情報は、典型的に
、記号対乃至は「バイト」の形態で送信される．ステー
ション間におけるデータを送信するための権利を意味す
るものとしてトークンが使用される．ＦＤＤ　Ｉにおい
て、特定の生成元多項式Ｇ（Ｘ）は、循環冗長エラーチ
ェックコードを発生するために使用される．このＦＤＤ
　Ｉ生成元多項式及び直列的にエラーチェックコード多
項式を発生するための簡単な具体化方法は、ｒ．Ｆ　Ｄ
　Ｄ　Ｉ媒体アクセス制御（ｍａｃ−Ｍ）Ｊ　、Ｘ３Ｔ
９．５／８８−１３９、Ｒｅｖ．２、１９８９年６月１
日の文献に記載されている。

ＦＤＤ　Ｉにおいて、生成元多項弐Ｇ　（ｘ）は次式で
与えられる Ｇ（　ｘ　ｌ　　＝　ｘ　３　２４　ｘ２　ａ　　＋　
ｘ　２’　　４　ｘ　２　２　４　ｘ　！　８　４　ｘ
　＋　２　４Ｘ目　÷ｘ”　　＋ｘ’　　＋ｘ’　　＋
ｘ’　　＋ｘ’　　＋ｘ”　　＋ｘ　　＋１（ｌ　４） 式（ｌ４）における好適な生成元多項式における最大次
数は３２であるので、ｎ＝３２である．状態遷移マトリ
クス要素における係数の値は、生成元多項弐Ｇ　（ｘ）
及び並列的に処理されるべきデータビット数によって決
定される。（式（ｌ１）及び（１２）） チェックコード発生値Ｓ　ｍａ１の次の状態は、次式の
マトリクス表示に従って直列的に発生される． Ｓｎ＋＋　＝　ＡｘＳｓｔ　＋　Ｂｘｉｍ　　　　　　
　　（　１　５）？、Ｓｍは、入力ビットエ．を印加す
る前の発生器の状態であり、Ｓ　ｍ４１はｍ番目のビッ
トを処理した後のエラーチェックコード生成元多項式の
状態であり（即ち、次の状態情報Ｓ．．．．Ａは変換を
記述するｎＸｎ状態遷移マトリクスであり、且つＢは結
果に与えるｍ番目の入力ビットの影響を記述するｎＸ１
ベクトルである． 状態遷移マトリクスＡは、生成元多項弐〇（ｘ）に直接
的に関係しており、且つ入力分布ベクトルＢはマトリク
スＡのコラムｎ−１と同一である。式（１４）における
好適な生成元多項式の場合、Ａは３２Ｘ３２マトリクス
であり、且っＢは３２×１ベクトルである。

次のビット１１。，を適用すると、次の如くに８■．２
が得られる。

Ｓｍ−２・ＡＸ　Ｓｍ−＋　”　１３ｘ　１ｍ＋１　　
　　　　（　１　６　）式（１５）を式（１６）内に代
入すると、次式が得られる。

Ｓｍｉｔ−ＡＸ　（Ａ×れ＋１３ｘ　ｘＪ＋Ｂ　Ｘ　１
ｍ＋＋　（　１　７　）又、次式が得られる。

？１１１４２　　＝Ａ２ｘＳ＋ｓ　　＋　　ＡＸＢ　　
Ｘｌｍ　　”Ｂ　　Ｘｌｍ＋＋　　（　１　８　）又次
式の如くになる Ｓ．ｚ　＝Ａ２×Ｓ＋ｍ　”　Ｂｉ　Ｘ　１ｍ＋２＋　
　　　　　（　１　９　）尚、Ａ２はマトリクスＡの２
乗であり、Ｂ２はベクトルＢとＡＸＢとから構成される
ｎＸ２マトリクスであり、且つＩ　＋ａ（ｚ１は工，で
スタートする２つの入カビットから構成される２×１ベ
クトルである。一穀的に、Ｉ　ｍ　＋ｚ＋　”　｛　１
　＠＊よ−１１■１−２１　．　．　．　　ＩＩ，ｌ）
であり、尚Ｉ　ｖａｌｚｌはＺ×１ベクトルである。

継続して適用し且つ８ビット入力（ｚ＝８）の場合に拡
張すると、次式が得られる。

Ｓｍ＋ａ　；Ａ”Ｘ　Ｓｍ　”　Ｂａ　Ｘ　Ｉｍ（ａｌ
　　　　　（　２　０　）尚、Ｓ１，８は、８個の入力
ビットを並列的に処理した後の発生器（即ち、生成元多
項式）の状態であり、Ａａは罵指数が８であるマトリク
スＡであり、ＢｅはベクトルＢ及びＡＸＢ，ＡＸＡＸＢ
等から構成される３２×８マトリクスであり、且つ工■
＋ａｌはｌｍでスタートする８個の入力ビットから形成
される８×１ベクトルである． 第１１図及び第１３図に従ってＡ８マトリクス及びＢ８
マトリクスを形成し、且つこれら２つのマトリクスを観
察することにより、Ａ８マトリクスの８個の最も高いコ
ラムはＢ８マトリクスを有する８個のコラムと同一であ
ることが明らかである。Ｂ８マトリクスは、Ａ８マトリ
クスの８個のコラム（列）と同一である．なぜならば、
Ａ８マトリクスを形成するためにＡに関して行われる処
理は、Ｂ，マトリクスを形成するためにＢに関して行わ
れる処理と同一だからである。

ハードウエアで式（ｚ０）のエラーチェックコード発生
器の物理的に具体化したものは、一度に８個の入力ビッ
トで動作する。排他的ＯＲ操作の性質により及びＢ８マ
トリクスとＡ８マトリクスとの間の類似性を観察するこ
とにより、入力ビットＩ。は、Ｂ８マトリクスが適用さ
れる前に、Ｓ．の８個の最大桁ビットと俳他的ＯＲ処理
することが可能である．そのようにすることにより、Ａ
８マトリクス内の８個のコラムが実行されるハードウエ
アは、ハードウエア要素のダブリを？避するために除去
することが可能である．Ａ８の最も左側の８個のコラム
（列）は、正確にＢ，と同一であるので、新たなベクト
ルＴＩＩ１は次式に従って形成することが可能である．
ｔｊ．ｍ　＝Ｓｊ，ｍ　　ＩＪ−２４　　　　（ｚ　１
）尚、ｔ，＝Ｔｍのｊ番目の要素 ＳＪｆｆｉ＝ＳのＪ番目の要素 １　４−ｘ４＝入力ベクトルＩのＪ−２４番目の要素で
、０未溝の全ての添字に対して ０に等しい。

従って、式（ｚ０）は次式の如《変形することが可能で
ある。

Ｓｆｆｌ。：＝　Ａ８　ｘ　丁■　　　　　　（ｚ２）
上式をハードウエアで具現化するには以下の条件を必要
とする。

（１）各々が状態変数Ｓイを保持する８個の要素からな
る４つのランクの形態に配設した１組の３２個の格納要
素． （ｚ）上部８個の格納要素の出力をＴｆｆｉベクトルの
上部８個のビットを形成する８個の入力と結合するため
の１組の８個の排他的ＯＲゲート．これら８個のゲート
の出力はマトリクスＢを供給する． （３）Ａ’マトリクス内の２４個の対角線以外のものに
対応する１組の２４個の排他的ＯＲゲート。これらのゲ
ートの出力は，上部２４個の格納要素の入力を供給する
．これらのゲートの各々の一方の入力は、次の下側のラ
ンクの対応する位置における格納要素から、即ち８番目
の下位格納要素から来る．該ゲートへの他方の入力はマ
トリクスＢから来る． （４）マトリ２スＢと呼ばれる一組の排他的ＯＲゲート
。マトリクスＢへの入力は、Ｔ．，ｌベクトルの上部８
個のビットから来る．マトリクスＢの出力の内の２４個
は、上部２４個の格納要素の前方の排他的ＯＲゲートへ
行き、且つ残りの８個の出力は下部８個の格納要素へゆ
く．特定の８力へいくマトリクスＢ内の排他的ＯＲゲー
トの特定の組合わせは，Ａ″マトリクスの左側８個のコ
ラム内の対応する行に沿っての位置の存在によって決定
される． 第１図を参照すると，式（ｌ４）のｎ次生成元多項式用
の状態遷移マトリクス（Ａ’）１０１ａ及び対応する入
力分布ベクトル（Ｂｚ）２０１ａが示されている． 第２図を参照すると、式（ｌ４）のｎ次生成元多項式用
の状態遷移マトリクスＡ”ｌ０１が示されている．（ｎ
＝３２），特に、状態遷移マトリクス１０１は、８ビッ
トのデータが受信され且つ並列的に処理され（ｚ＝８）
且つ状態遷移マトリクス１０１が「Ａ″マトリクス」と
して示されるシステムに対して構成されている． Ｂ８マトリクス２０１は、状態遷移マトリクス１０１内
のＺ最高コラムと同一である．特に、Ｂ２は、Ａマトリ
クス１０１のコラムｎ−１乃至ｎ−ｚと同一である． 第３図を参照すると、８ビットが並列的に処理される（
ｚ＝８）及び共通ハードウエア要素が共用される場合の
式（ｚ１）をハードウエアで実施するためのエラーチェ
ックコード発生装置３００が示されている．尚、式（ｚ
０）に従って、エラーチェックコードを発生するため、
又はエラーチェックコードがデータシーケンスを処理し
た後の格納要素内に格納される残部項と対応する場合の
エラーチェックコードを発生するためのその他の種々の
システム乃至は装置は、当業者によって容易に構成する
ことが可能であることに注意すべきである． システム乃至は装置３００は、入力格納レジスタ１４と
、入力分布マトリクス要素２００と，状態遷移マトリク
ス要素１００とを有している．ハードウエアで式（ｚ０
）を実施する場合，４Ｂマトリクス２０１を実施するた
めに使用するものと同一であるＡマトリクス１０１を実
施するために使用される論理要素は共用させることが可
能である． ハードウエア要素を共用とすることにより、必要とされ
る構成要素の数が減少されるので、システム３００の全
体的な寸法が減少される．状態遷移マトリクス要素１０
０及び入力分布マトリクス要素２００は、両方とも、ハ
ードウエアでマトリクスを実現する論理要素から構成さ
れている．何れかの入力データバイト信号１２を受信す
る前に、状態遷移マトリクス要素１００内の複数個の状
態格納レジスク４０，４２，４４．４６は、状態格納レ
ジスタ４０，４２，４４．４６の入力端に複数個の組の
論理ＯＲゲート５０を挿入することにより、ブリセット
制御器５１によって全てｌヘプリセットされる．従って
、システム３００がプリセットされる場合、状態格納抵
抗４０，４２，４４．４６は、複数個の論理１信号を格
納し、且つ全てが論理１である複数個の現在の状態信号
３３，３５，３７．３９を発生する．データバイトとし
て定義されＺビットから構成される並列入力データ信号
（１、）１２は、Ｚ個の入力ポートを有する入力レジス
タｌ４によって受信される．複数個のクロックサイクル
に亘って受信される複数個のデータバイトは、エラーチ
ェックコードＳＬが発生されるデータシーケンスエ。Ｉ
ＬＩを有する場合がある．■。，。は、工。

？（Ｌ−１等のビットから構成されている．好適実施例
においては、入力データバイト信号１２は８ビット幅■
。１−■，であり、従って入力レジスタ１４は８ビット
の格納レジスタである。１つのクロックが必要とされる
に過ぎない．なぜならば、データバイト１２の入力ビッ
トｌ　１，ｌ＋７　　　１　ｒａの全てが並列的に読取
られる． マルチプレクサ（ＮＵＸ）５２を制御する制御信号５４
は、システム３００が入力データバイｌ−１２　（１■
ｙ，．．．ｌ■）を受信している場合、論理高信号乃至
は「ｌ」を発行する。制御信号２４は、論理高又は論理
低信号の何れかとすることが可能である。ＭＵＸ５２は
、Ｚビット幅マルチプレクサである。好適実施例におい
ては、８ビットが並列的に処理されるので、ＭＵＸ５２
は８ビット幅のＭＵＸである．同様に、ＭＵＸ５２は２
つの入力（信号１６又は信号３９）の間で選択を行うの
で、ＭＵＸは８ビット２入力幅のＭＵＸ５２である． 入力レジスク１４は、上昇エッジ感応性であり、且つ上
昇エッジクロツク信号（不図示）を受取ると、入力レジ
スク１４はその受信したデータバイト信号１２を格納し
（　１ｍ＋７　−　−　．　　ｌｍ　）且つそれは、又
、受信したデータ信号１２と同一の値を持ったデータバ
イト信号１６を出力する．データバイト信号ｌ６は、複
数個の排他的ＯＲゲート（ＸＯＲ）２０を介して、複数
個の現在の状態残部信号３９　（Ｓ２４．．．．　）の
最後の１つと並列的にモジュロ２加算され、尚信号３９
はＳ，Ｉ１の上部８個のビットである（ＳＬ，，　．ｎ
−３２．，．）。

一Ｍ的に、最後の現在の状態信号３９は、現在の状態信
号Ｓ．ＲのＮ−１乃至Ｎ−ｚのビットに対応しテイル。

ＸＯＲゲート２０は、信号１６　３９内の各ビットを一
体的に加算し、且つ第一加算Ｚビット並列信号２２が発
生される。第一加算信号２２はＴ　ｍ１、　　−Ｔ２４
．＋ｅである。

信号３９．１６の両方が共に加算されて、論理要素をセ
ーブする。なぜならば、式（ｌ４）によれば、信号１６
．３９の両方が、入力分布マ｝・リクス２００によって
乗算されるからである．信号１６．３９は、乗算される
前に、最初に加算させることが可能である．後述する如
く、第一加算信号２２は、制御信号２４とモジュロ２乗
算されて、Ｚビット制御加算信号２８を発生し、好適実
施例においては、この制御加算信号２８はＴ′３１，　
　　Ｔ′ｚａ．ｍである．モジュロ２乗算は、各々が制
御信号２４と第一加算信号２２の各ビットとを論理的に
ＡＮＤ処理する複数個の論理ＡＮＤゲート２６によって
達成される． 制御信号２４が論理１である場合、Ｚビット制御加算信
号２８は２ビット並列第一加算信号２２と同一である．
制御信号２４が０である場合、制御加算信号２８は０で
ある。

Ｚビット並列制御加算信号２８は、入力分布マトリクス
要素２００内へ入力され、そこで、それは、入力分布マ
トリクス（Ｂｚマトリクス）２０１によって乗算される
。Ｂマトリクス乗算によって発生される残部項は、Ｎビ
ット並列分布信号Ｂ．−Ｂ，．有している．Ｂマトリク
ス２０１は、Ａ８マトリクスの８個の最高コラムを計算
し、且つこれらの３２個の出力信号（分布信号３２，３
４，３６．３８）を８ビット分布信号の４つの組として
供給する．分布信号３２，３４，３６．３８は、それら
が、Ｔマトリクスの最高の８ビットとＡ８マトリクスの
最高の８個のコラム（即ち、コラム３１−２４）との間
のクロス乗積を表わすという点において部分和である． 入力分布マトリクス２０１は、Ｚビット並列制御加算信
号２８をＮビット並列分布信号Ｂ０Ｂｍｌへ変換する．
好適実施例においては、並列分布信号の第一のものは、
該分布信号のビットＯ−７（Ｂｚ，）に対応しており、
本明細書においては、「第一分布信号３２」として呼称
し、該信号の第二のものはビット８　−　１　５　（Ｂ
ｚ，，）に対応し、且つ、本明細書では、「分布信号３
４」として呼称し、該並列信号の第三のものはビット１
６−２３　（Ｂ，．２，）に対応し、且つ本明細書では
、「分布信号３６」と呼称し、且つ該並列信号の第四の
ものはビット２４−３１　（Ｂ２４−，，，）に対応し
、且つ、本明細書では，（最後の分布信号？８）として
呼称する． 任意の与えられたクロックストロークにおいて、Ｓ，ａ
は状態格納レジスク４０，４２，４４．４６へエンタし
、且つｉ。は入力格納レジスタ１４ヘエンタする．その
クロツクストローク及び通常の伝搬遅延の後、Ｓ　ｍｉ
ｌｌの値が計算され且つ格納レジスク４０，４２，４４
．４６の入力端へ供給され、従って次のクロックストロ
ークにおいて、Ｓ．．８はレジスク４０，４２，４４．
４６内へクロツク入力される． １ｍｆ８１が入力格納レジスタ１４内に格納され且つＳ
１がレジ，スク４０，４２，４４．４６内に格納される
ものと仮定すると、特定のクロックサイクルの期間中、
Ｓ　Ｓｌ＋　ｍ　　Ｓｚａ，ｍ　（現在の状態残部信号
３９の最後のもの）が、ＸＯＲゲート２０によって、１
■や，−１０。。（データバイト信号１６）とをＸＯＲ
処理されて、Ｔ　ｍ１、ｍ　　Ｔ２４．＋＋＋（第一加
算信号２２）を発生する。通常動作においては、データ
バイト１。が受信中であり且つ制御信号２４が論理１で
あると、ＡＮＤゲート２６は、信号２２と信号２４とを
ＡＮＤ処理し、Ｔ１１ａＴ２４．ｍ　　の値が制御加算
信号２８（Ｔ’　ｓ＋−Ｔ′２４として、ＡＮＤゲート
２６の出力端において繰返される．制御加算信号２８は
、Ｂマトリクス２００へ入力される． 特定のクロックサイクル期間中、第一分布信号３２を除
いて、そのクロツクサイクルにおいて発生される全ての
分布信号３４，３６．３８は、論理排他的ＯＲゲート（
ＸＯＲ）６０ａ．６０ｂ，６０ｃによって、夫々、複数
個の状態遷移格納レジスタ４０，４２．４４から読出さ
れる複数個の現在の状態残部゜信号Ｓ，３３，３５．３
７　（前のクロックサイクルにおいて発生されているが
そのクロツクサイクルの終りに該レジスタ内に格納され
る）と、モジュロ２加算される． Ａ８マトリクスの８個の最高のコラムのＯ−７行を表わ
す第一分布信号３２は，直接的に格納レジスク４０へ供
給される．（なぜならば、ブリセット信号が１だからで
ある）．これら最高の８個のコラムはＢ８マトリクスと
同一である．？１マトリクスの最高の８個のコラムの８
−１５行である第二分布信号３４は、複数個のＸＯＲゲ
ート６０ａを介して、レジスタ４０によって出力される
規在の状態残部信号Ｓｏ．ｍ　　Ｓｙ．ｍ３３とをＸＯ
Ｒ処理される．このマトリクス乗算によて発生される残
部項４１はＳ＠．，や，，Ｓ１５１。８である。残部項
４ｌは、レジスタ４２の入力端において与えられるが、
次のクロックサイクル迄レジスク４２内に格納されるこ
とはない。

次のクロックサイクルにおいて、Ｓｓ，ｍ＊ａ、Ｓ　＋
ｓ　ｌｌｌ＊ａがレジスタ４２内に格納される．同様に
第三分布信号３６は、Ａ”マトリクスの最高の８個のコ
ラムの１６−２３行である。第三分布信号は、複数個の
ＸＯＲゲート６０ｂを介して、レジスク４２によって出
力される現在の状態残部信号３５Ｓ８■−Ｓ＋５．ｍと
ＸＯＲ処理される。このマトリクス乗算によって発生さ
れる残部項４３はＳ　＋６，ｍｈｓ−　−　．　　Ｓ　
２１ｍ＋ｌ！である．それらは、レジスタ４４の入力端
において与えられるが、この場合にも、次のクロツクサ
イクル迄レジスタ４４内に格納されることはない．次の
クロックサイクルで、Ｓ＋ａ．＋＋＋・６．　．　．　
　Ｓ２！．・・Ｓがレジスク４４内に格納される． 最後の分布信号３８は、Ａ６マトリクスの最高の８個の
コラムの最高の８個の行（行２４−３１）の値を表わし
ている．！！ｋ後の分布信号３８は、複数個のＸＯＲゲ
ート６０ｃを介して、レジスク４４によって出力される
現在の状態残部信号３７とＸＯＲ処理される．現在の状
態残部信号３７はＳ’ｓ。−Ｓ２２ユである．このマト
リクス乗算によって発生される残部項４５はＳｘ４．ｍ
。６，．．３３１ｍ＋。であり、且つそれらは最後の状
態レジスタ４６の入力端に与えられるが、次のクロツク
サイクルで、Ｓ　２４．ｍ＊Ｍ．　．　．　Ｓ　ｓ＋．
ｍ＊ｍがレジスタ４６内に格納される． 最後のデータバイトＩ　Ｌ−ａを発生器システム３００
へ供給した後のクロックストロークにおいて，発生器３
００の格納要素４０，４２，４４．４６はデータシーケ
ンスＩＯＩＬＩに対する残部項乃至はエラーチェックコ
ードＳＬを有している．このエラーチェックコードをデ
ータシーケンスＩ．ゆ，へ添付するために使用可能な幾
つかのアプローチがある．その各アプローチにおいて、
（１）８個の２入力ＭＵＸを使用して８人カビット１６
か又は上部８個の格納要素３９の何れかからの出力の供
給元を選択し、且つ（ｚ）Ｉ！後のデータバイト■，−
，がデータ格納レジスタ１４内にクロック入力された後
にそのＭＵＸ５２へ入力される制御信号２４を変化させ
る． 最初のアプローチは、格納要素４２，４４．４６の上部
２４個の出力の各々の入力端に２入力ＭＵＸを配置させ
る．このＭＵＸは、８個の出力ＭＵｘを制御するものと
同一の信号で制御される。

これらの２４個のＭＵＸは、通常入力を格納要素へ供給
する排他的ＯＲゲート６　０　ａ，　６　０　ｂ，　６
０Ｃか、又は次の下位のランクにおける対応する格納要
素の出力の何れかを選択する．このアプローチは、爾後
のクロツクストロークで該格納要素を介してデータがシ
フトすることを可能とする． ２番目のアプローチ（第４図に示してある）は、２４個
の排他的ＯＲゲートは、既に、格納要素４２，４４．４
６の上部２４個の出力を、次の下位のランクにおける対
応する要素へ接続しているという事実を利用する．２入
力ＡＮＤゲートで他の入力を排他的ＯＲゲート６０ａ，
６０ｂ，６０Ｃへ供給するマトリクスＢからの２４本の
ライン３２，３４．３６をインクラブトし、且つ出力Ｍ
ＵＸを制御するものと同一の信号２４でこれらのＡＮＤ
ゲートの各々の第二入力を制御することによって、２４
個の排他的ＯＲゲートの入力端へ０を強制的に印加する
ことが可能であり、その際に該ゲートが情報を変更する
ことなしに、通過させることを可能とする． ３番目のアプローチは、好適実施例（第３図）において
使用するアプローチであり、Ｔベクトルの最高の８個の
ビットを強制的にＯとすることによりマトリクスＢの出
力も強制的に０とされ、その際に２番目のアプローチに
おける２４個の２入力ＡＮＤゲートと同一の効果を発生
するという事実を利用する．しかしながら、この３番目
のアプローチは、８個の２入力ＡＮＤゲートを必要とす
るに過ぎないので、より効果的である．状態格納レジス
タ４０，４２，４４．４６の内容は、Ｓ１を形成するＮ
ビットの現在の状態信号３３，３５，３７．３９として
並列に読出される．状態格納レジスク４０，４２，４４
．４６の各々は、Ｎビットの現在の状態信号ＳＩＩのう
ちのＺ個のビットを出力する．このマトリクス乗算４１
，４３．４５によって発生される残部項は，複数個の状
態格納レジスタ４２，４４．４６内に格納され、且つレ
ジスタ４０内に格納される第一分布信号３２はＮビット
の次の状態信号Ｓ　ｍ＋８である． 前述した如く、第一分布信号３２は、現在の状態残部信
号Ｓ，のＺビットと論理的にＸＯＲ処理されることなし
に、Ｚビット状態格納レジスク４０の最初のものの中に
並列的に格納される．従って、Ｎビット並列分布信号３
２，３４，３６．３８は、状態遷移マトリクス１０１の
Ｎ−ｚ行とモジュ口２乗算される．第一分布信号３２を
ＸＯＲ処理する必要はない．なぜならば，前述した如く
、それは、状態遷移マトリクス（上０−７）２０ｌの下
部Ｚ上に対応しているからである．Ａマトリクス１０１
の下部Ｚコラムにおける最初のＺ行は論理Ｏ（第２図）
であるので、０項と第一分布信号３２とのＸＯＲ処理（
モジエ口２乗算の実行）により、変化されることのない
第一分布信号３２が得られる．従って、論理要素を節約
するために、第１状態格納レジスタ４０への入力端に論
理ＸＯＲゲートを設けることは必要ではない。

好適実施例においては、状態遷移マトリクス要素１００
は、３２ｘ３２マトリクスであり、それは、複数個の論
理ＸＯＲゲート５０を使用して、ハードウエアの形態で
実現される。状態遷移マトリクス要素１００によって受
信される並列８ビット分布信号３４，３６．３８　（第
一分布信号３２を除外）の各ビットに対して１つの論理
ＸＯＲゲート５０が存在している．状態遷移マトリクス
要素１００は、更に、マトリクス乗算によって発生され
る２４個の残部項と第一分布信号３２を同時的に格納す
るための４−８ビット状態格納レジスタ４２，４４，４
６．４８を有している．状態格納レジスタ４０，４２，
４４，４６．４８の各々は、夫々、３２ビット状態信号
３３，３５，３７，３９の８ビットを出力する。

入力分布マトリクス要素２００は、３２×８マトリクス
であり、それは、例えば複数個の論理排他的ＯＲ要素（
不図示）等のような従来技術を使用してハードウエアで
実現することが可能である．好適実施例においては、分
布マトリクス要素２００は、状態遷移マトリクス要素１
００と同様に構成されているが、好適実施例においては
，それは格納レジスタを有していない。

状態遷移マトリクス１０１の対角線を外れたｌのセクシ
ョンは、ＸＯＲゲートによってハードウエアで構成され
ており、１番目のビット位置は９番目のビット位置とＸ
ＯＲ処理され、２番目のビット位置は１０番目のビット
位置とＸＯＲ処理され、３番目のビット位置は１１番目
のビット位置とＸＯＲ処理され，以下同様であって、ク
ロックサイクル当たり、８ビットマトリクス乗算及びレ
ジスタシフト動作が発生する．状態レジスク４０，４２
，４４．４６内に格納される残部項は、受信したデータ
ビットのシーケンスに対する次の状態情報Ｓ．、６に対
応する． このプロセスは，爾後に受信したデータバイトに対して
繰返し行われる． 従って、ｌクロックサイクル期間中、受信した１つ又は
複数個のデータバイトに対する次の状態情報（夫々、１
つ又は複数個のクロックサイクルに亘って）が発生され
、且つ次のクロツクサイクル期間中、それは状態格納レ
ジスタ４０，４２，４４．４６内に格納される．次の状
態情報は受信したデータバイトに対して累積的である．
好適実施例においては、それは、データシーケンスエ。

ＩＬ＋全体を受信した後に状態格納レジスタ４０，４２
，４４．４６からエラーチェックコードＳＬを読出すの
に数個のクロツクサイクルを必要とする． クロックサイクル数は、残部多項式内のビット数を並列
処理中のビット数で割算したものに等しい。好適実施例
においては、一度に３２ビットの残部８ビットを処理す
るには、残部項を全てシフト出力するのに４つのクロツ
クサイクルを必要とする． 全てのデータバイトを受信した後に状態格納レジスタ４
０，４２，４４．４６内に現在格納されている信号は、
「最後のクロックサイクル」又はサイクルＯにおいて発
生されたものといわれる．サイクル０は、エラーチェッ
クコードの発生を完了するクロツクサイクルである． 最後のクロックサイクル（サイクル０）期間中、データ
シーケンス内の最後の入力データシーケンスバイトｌ２
は、データバイト信号１６として出力され、データバイ
ト信号ｌ６はシステム出力信号５４として読出され、且
つエラーチェックコードを形成する残部項は、状態レジ
スタ４０，４２，４４．４６の入力端に供給される．次
の４つのクロツクサイクル（サイクルｌ−サイクル４）
の期間中、その外の有効データが受信されない場合、エ
ラーチェックコードはレジスク４０，４２，４４．４６
から読出される．第一クロックサイクル（サイクル１）
は、有効データが受取られない場合の第一クロックサイ
クルである．制御信号２４は、論理低乃至は０となり、
且つＭＵＸ５２を０ヘスイッチし、その際に最後の状態
遷移残部信号３５をシステム出力信号５４として出力さ
せる．データバイトｌ２が受取られている場合、制御信
号は論理項であり、それはＭＵＸ５４を制御してデータ
バイト信号１６を出力する．最後の状態遷移残部信号３
９は、レジスタ４６内に格納されているエラーチェック
コードの最初の８個のビットである（Ｓ−＋−Ｓｓ−）
−エラーチェックコード項の最初の８個のビットは、前
のクロックサイクル期間中にＭＵＸ５２によって出力さ
れるデータシーケンス５４へ添付される． エラーチェックコード項が読出される場合にクロツクサ
イクル（サイクル１−４）期間中にシステムによって受
取られる非データ信号は、最後のしながら、発生された
第一加算信号２２は、次いで、論理Ｏは制御信号２４と
論理的にＡＮＤ処理され、且つ定義によって、その結果
発生する制御加算信号２８は論理Ｏである。従って、入
力分布マトリクス要素２００へ入力される信号２８は論
理０信号であり、従ってこれら４個のクロツクサイクル
期間中に発生される分布信号３２，３４，３６．３８は
論理Ｏである。

状態格納レジスタの内容（即ち、エラーチェックコード
項）を論理Ｏ分布信号２８とＸＯＲ処理することにより
、状態格納レジスク４０，４２，４４．４６内に格納さ
れるエラーチェック値は、保存され、且つ格納レジスタ
４２．４４の中間バンクを介して最後レジスタ４６へ相
次いでシフト動作される． 特に、サイクル１の期間中、状態レジスタ４４の内容（
即ち、エラーチェックコード項ｓ１６−３２３）を論理
０分布信号２８とＸＯＲ処理することにより、それは、
基本的に、レジスク４４から最後の状態レジスク４６へ
転送乃至はシフト動作される．第一及び第二の状態格納
レジスタ４０，４２の内容（即ち、エラーチェックコー
ド項Ｓ０　Ｓｔ及びＳ．−Ｓ，．）も、夫々、次の状態
シフトレジスタ４２．４４へシフト動作される。

なぜならば、対応する現在の状態信号３３．３５は、対
応する論理０分布信号３４．３６とＸＯＲ処理されるか
らである． 第二クロックサイクル、即ちサイクル２の期間中、３　
１６　　Ｓｘｓに対応するエラーチェックコードの次の
８個のビットは、レジスタ４６から出力される。なぜな
らば、それらは、サイクル１期間中に、レジスタ４６内
にシフト入力されているからである。信号３９は、シス
テム出力信号５４として出力される．なぜならば、制御
信号２４は未だに論理低だからである．シフト動作プロ
セスが継続して行われ、Ｓ−　　Ｓ，ｓがレジスタ４６
内に格納され、且つＳ．−Ｓ，がレジスタ４４内に格納
される． 第三クロックサイクルであるサイクル３の期間中、８番
目乃至１５番目のエラーチェックコード項が信号３９と
して最後のレジスタ４６から呼び出され、且つ信号３９
の反転したものがシステム出力信号５４である．４番目
のクロツクサイクル、即ちサイクル４期間中、Ｏ乃至７
番目のエラーチェックコード項（最初は、サイクル０期
間中に、Ｓ０−Ｓ．内に格納）は最後の状態シフトレジ
スク４６から読出され、且つその反転したものはシステ
ム出力信号５４として出力れる。

信号３９がシステム出力信号５４として出力されるべく
選択されると、それは、ＭＵＸ５２の前端におけるイン
バータ６０によって反転される。

好適実施例においては、信号３９は反転される。

なぜならば．ＦＤＤＩは、残部多項式の非反転ビットで
はなく反転ビットがメッセージにおけるデータビットに
付随することを特定しているからである． 第４図を参照すると、別の実施例４００において、分布
マトリクス要素２００の入力端にＺ論理ＡＮＤゲートを
位置させる代わりに、論理ＡＮＤゲート２６０を分布マ
トリクス要素２００の出力端に位置させ、分布信号３２
，３４，３６．３８の３２ビットの内の２４ビットを制
御信号２４と論理的にＡＮＤ処理させている．ＡＮＤゲ
ート２６０は、制御Ｚビット分布信号３４０，３６０，
３８０を発生し、制御信号２４が論理Ｏである場合、複
数個の制御分布信号３４０，３６０，３８０が論理Ｏで
あり、そうでない場合には、それらは対応する分布信号
３４，３６．３８と同一である．従って、ＡＮＤゲート
２６０は、システム３００におけるＡ’Ｎ　Ｄゲート２
６（第３図）と同一の機能を達成する． 第５図を参照すると、システム３００，４００によって
発生されるエラーチェックコード（ＥＣＣ）に対するタ
イミング線図を示してある。初期的には、ＰＲＥＳＥＴ
　（プリセット）信号５ｌは論理項である。制御信号２
４は高状態であり、且つ高状態を維持し、一方データシ
ーケンス（１０１　０　１　０　１　０）がシステムに
よって受信される．制御信号２４が高状態であると、特
定のクロックサイクル期間中に受信されるデータバイト
が出力される．データシーケンス（１０１０１０１０）
が受信された後に、制御信号２４が論理低状態（即ちＯ
レベル）へ変化し、且つ爾後のクロツクサイクル（４サ
イクル）期間中に、受信したデータシーケンス（１　０
　１　０　１　０　Ｌ　Ｏ）に対応するエラーチェック
コード（０１１０１１１１　　０１０１００１０　　１
１００００００　　１００１００１１）が、相次いで、
格納レジスタ（４０，４２，４４．４６）から読出され
、且つ前に出力したデータバイト・（１　０　１　０　
１　０　１　０）へ添付される。

状態格納レジスタ４０，４２．４４内に格納されている
エラーチェックコードを爾後のクロツクサイクル期間中
に変更することなしに読出すことが可能であるようにす
るために、分布マトリクス要素２００へ入力される（又
は、第３図におけるシステム４００から出力される）信
号を初期化即ち「ゼロ」化させることが必要であると考
えられる．分布信号３４，３４．３８が０信号でなかっ
た場合には、サイクル１−４期間中に，状態レジスタ４
０，４２．４４内に格納されるエラーチェックコード項
は変更されてしまい（非データ信号のために発生される
分布信号３４，３６．３８とＸＯＲ処理されて）、且つ
読出されたエラーチェックコード項は、前に受信したデ
ータシーケンスに対応するエラーチェックコードではな
くなってしまう． 以上、本発明の具体的実施の態様について詳細に説明し
たが、本発明は、これら具体例にのみ限定されるべきも
のではな《、本発明の技術的範囲を逸脱することなしに
、種々の変形が可能であることは勿論である．

【図面の簡単な説明】

第１図は好適実施例の生成元（発生器）多項式に対する
状態遷移マトリクス及び入力分布マトリクスの概略図、
第２図は複数個のデータビットが並列的に受信される場
合の生成元（発生器）多項式に対する状態遷移マトリク
ス及び入力分布マトリクスの概略図、第３図は並列的に
エラーチェックコードへアクセスする本発明の一実施例
に基づいて構成されたエラーチェックコード発生器装置
の概略ブロック図、第４図は本発明の別の実施例に基づ
いて構成されたエラーチェックコード発生器装置を示し
た概略ブロック図、第５図は本発明によって発生される
エラーチェックコードに対応するタイミング線図を示し
た概略図、である．（符号の説明） １４．入力格納レジスタ ４４，４２，４４，４６：状態格納レジスクｌ００：状
態遷移マトリクス要素 ２００：入力分布マトリクス要素 ３００．エラーチェックコード発生システム図面の浄書
（内容に変更なし） ＦＩＧ．　７ 手続補正書 平成３年３ 月！２日

Claims (1)

1. 【特許請求の範囲】 １、発生され且つ複数個の格納手段内に格納されている
   一群の剰余多項式項を読取る装置において、前記剰余多
   項式項が発生器多項式及び相次ぎ受取ったデータバイト
   のシーケンスに従って発生され、 （Ａ）第一又は第二論理状態を有する制御信号、 （Ｂ）前記制御信号に応答し前記制御信号が第一論理状
   態を有する場合に第一論理状態を持った格納制御信号を
   発生する手段、 （Ｃ）剰余多項式項の複数個のグループを順次且つ並列
   的に格納するための複数個の相次いで配列された格納手
   段、 を有しており、前記格納手段が、前記格納制御信号が前
   記第一論理状態である場合に、前記複数個のグループの
   剰余多項式項が修正されることなしに相次ぐ格納手段へ
   逐次的に転送され且つ前記相次いで配列された格納手段
   の最後のものにおける剰余多項式項が本装置によって出
   力されるように、前記格納制御信号に応答することを特
   徴とする装置。 ２、特許請求の範囲第１項において、前記格納制御信号
   を発生する手段が、複数個の論理ＡＮＤゲート要素を有
   することを特徴とする装置。 ３、特許請求の範囲第１項において、前記第一論理状態
   が論理０であることを特徴とする装置。 ４、特許請求の範囲第２項において、前記格納手段の各
   々が、更に、 （Ｄ）前記格納手段のあるものの出力端に複数個の論理
   排他的ＯＲゲート要素を有しており、前記論理排他的Ｏ
   Ｒゲート要素の各々は、第一入力信号として前記第一論
   理状態を持った前記格納制御信号を受取ると共に第二入
   力信号として前の格納手段から転送された剰余多項式項
   の１つを受取り、且つ前記格納制御信号が前記第一論理
   状態である場合に受取った剰余多項式項と同一の出力信
   号を発生し、且つ前記格納手段の各々が前記出力信号を
   成功した格納手段へ逐次的に転送する手段を有すること
   を特徴とする装置。 ５、複数個の係数項を持った生成元多項式に従ってデー
   タシーケンス（Ｉ＿ｏ＿（＿Ｌ＿））へ添付すべき複数
   個のエラーチェックコード項と、それと関連する少なく
   とも１つのコラムを持った分布マトリクス（Ｂ＿ｚ）と
   、それと関連する所定数のコラムを持った状態遷移マト
   リクス（Ａ＿ｚ）とから構成されるエラーチェックコー
   ド信号（Ｓ＿Ｌ）を発生する装置において、前記状態遷
   移マトリクス及び前記分布マトリクスは前記生成元多項
   式と関連しており且つ前記分散マトリクスのコラムは前
   記状態遷移マトリクスのコラムのサブセットであり、且
   つ前記データシーケンス（Ｉ＿ｏ＿（＿Ｌ＿））は所定
   数（ｚ）のデータバイトを持ったデータバイトのシーケ
   ンスに配列されており、 （Ａ）前記データバイトをシーケンシャルに受取る第一
   手段が設けられており、 （Ｂ）複数個の分布信号を発生するために前記分布マト
   リクス（Ｂ＿ｚ）を受信データバイト（Ｉ＿ｍ＿（＿ｚ
   ＿））とモジュロ２乗算する第一手段が設けられており
   、 （Ｃ）複数個の状態信号を発生するために前に受信した
   データビット（Ｓ＿ｍ）のシーケンスに対応するエラー
   チェックコード信号と状態遷移マトリクスＡ＾ｚとをモ
   ジュロ２乗算する第二手段が設けられており、 （Ｄ）受信したデータビット（ｍ＋ｚ）に対応するエラ
   ーチェックコード信号（Ｓ＿ｍ＿＋＿ｚ）を発生するた
   めに前記分布信号と前記状態信号とをモジュロ２加算す
   る手段が設けられており、 （Ｅ）上記要素（Ｄ）によって発生されるエラーチェッ
   クコード信号を格納するための第二格納手段が設けられ
   ており、前記第二格納手段は並列的な前記エラーコード
   項の複数個のグループをシーケンシャルに格納するため
   に複数個の相次いで配設された格納要素を有しており、
   前記第二格納手段は格納制御信号に応答し、 （Ｆ）上記要素（Ａ）−（Ｅ）を繰返し使用する手段が
   設けられており、前記繰返し使用する手段は、各受信デ
   ータパートに対して、 Ｓ＿ｍ＿＋＿ｚ＝Ａ＾ｚ×Ｓ＿ｍ＋Ｂ＿ｚ×Ｉ＿ｍ＿（
   ＿ｚ＿）の式に従ってデータシーケンスに対応するエラ
   ーチェックコードを発生し、その際に、各繰返しに対し
   て、全てのデータバイトが受信されている場合には、Ｓ
   ＿ｍ＿＋＿ｚが前記データシーケンスに対応するエラー
   チェックコード信号であるように、Ｓ＿ｍ＿＋＿ｚがＳ
   ＿ｍを置換し、 （Ｇ）制御信号に応答してシステム出力信号として前記
   受信データバイトと前記第二格納手段の最後のものに格
   納されているエラーチェックコード項との間で選択する
   手段が設けられており、前記制御信号はそれと関連して
   第一又は第二論理状態を有しており、且つ前記受信デー
   タバイトは、前記制御信号が第二論理状態である場合に
   前記システム出力信号であり、且つ前記第二格納手段の
   最後のものに格納されている前記エラーチェックコード
   項は、前記制御信号が第一論理状態である場合に前記シ
   ステム出力信号であり、 （Ｈ）前記制御信号に応答し前記制御信号が前記第一論
   理状態である場合に第一論理状態を持った前記格納制御
   信号を発生する手段が設けられており、 （Ｉ）前記第一論理状態を持った前記格納制御信号に応
   答し修正なしで前記第二格納手段の相次ぐ１つへのデー
   タシーケンスに対応する前記複数個のエラーチェックコ
   ード項を転送し且つ前記システム出力信号として前記第
   二格納手段の最後のものにおける前記エラーチェックコ
   ード項を供給する手段が設けられており、 （Ｊ）前記エラーチェックコード信号を有する前記複数
   個のグループのエラーチェックコード項を転送出力する
   ために上記要素（Ｉ）を繰返し使用する手段が設けられ
   ている、 ことを特徴とする装置。 ６、特許請求の範囲第５項において、前記受信データバ
   イトと前記第二格納手段の最後のものにおける前記エラ
   ーチェックコード項との間で選択する手段がマルチプレ
   クサであることを特徴とする装置。 ７、特許請求の範囲第５項において、前記格納制御信号
   を発生する手段が複数個の論理ＡＮＤゲート要素を有す
   ることを特徴とする装置。 ８、特許請求の範囲第７項において、前記分布信号のあ
   るものは前記複数個の論理ＡＮＤゲート要素の対応する
   １つによって受信され、且つ前記制御信号は、前記複数
   個の論理ＡＮＤゲート要素によって受信されると共に前
   記ＡＮＤゲート要素によって論理的にＡＮＤ処理され、
   従って前記制御信号が第一論理状態である場合には、前
   記論理ＡＮＤゲート要素が前記第一論理状態を持った格
   納制御信号を発生することを特徴とする装置。 ９、特許請求の範囲第７項において、前記分布マトリク
   スと前記受信データ信号とをモジュロ２乗算する第一手
   段が前記格納制御信号を発生する手段を有しており、且
   つ前記受信データバイトの各ビットが前記複数個の論理
   ＡＮＤゲート要素の１つへの１入力として与えられ、且
   つ前記制御信号は、前記複数個の論理ＡＮＤゲート要素
   への第二入力として供給され、前記複数個の論理ＡＮＤ
   ゲート要素は、前記制御信号と前記受信データバイトの
   各ビットとを論理ＡＮＤ処理して前記格納制御信号を発
   生し、従って前記格納制御信号が前記分布マトリクスに
   よって乗算されて前記複数個の分布信号を発生すること
   を特徴とする装置。 １０、特許請求の範囲第９において、前記制御信号が第
   一論理レベルである場合に、前記分布信号が第一論理レ
   ベルであることを特徴とする装置。 １１、特許請求の範囲第７項において、前記制御信号及
   び上記要素（Ｂ）によって発生される前記分布信号のあ
   るものが前記論理ＡＮＤゲート要素の１つへ入力され、
   前記論理ＡＮＤゲート要素が、前記制御信号が第一論理
   状態である場合に、前記第一論理状態を持った格納制御
   信号を発生することを特徴とする装置。 １２、並列的にエラーチェックコード信号 （Ｓ＿Ｌ）を発生すると共に発生されたエラーチェック
   コード信号を読出す方法において、前記エラーチェック
   コード信号は、複数個のエラーチェックコード項を有す
   ると共に、複数個の生成元項（ｎ）を持った生成元多項
   式及び各々が所定数のデータビット（ｚ）を持った複数
   個のデータバイトから構成される受信データシーケンス
   （Ｉ＿ｏ＿（＿Ｌ＿））に従って発生されるものであり
   、（Ａ）並列的なデータバイト（Ｉ＿ｍ＿（＿ｚ＿））
   をシーケンシャルに受信し、 （Ｂ）受信した並列的なデータバイトと前に受信したデ
   ータバイトのシーケンスに対応する最後のグループのエ
   ラーチェックコード項とをモジュロ２加算して複数個の
   並列状態信号を発生し、最後のグループのエラーチェッ
   クコード項は複数個のシーケンシャルに配設された第二
   格納要素の最後の１つからシフト出力され、 （Ｃ）並列的な前記複数個の状態信号と分布マトリクス
   （Ｂ＿ｚ）とをモジュロ２乗算して各々がそれと関連す
   る論理状態を有する複数個の分布信号を発生し、 （Ｄ）複数個のシーケンシャルに配設した格納要素の各
   々から前に受信したデータバイトのシーケンスに対応す
   る１グループのエラーチェック項を同時的にシフト出力
   し、前記シフト出力されるグループのエラーチェックコ
   ード項は前に受信したデータバイト（Ｉ＿ｍ＿（＿ｚ＿
   ））に対応するエラーチェックコード（Ｓ＿ｍ）を有し
   ており、 （Ｅ）上記ステップ（Ｄ）においてシフト出力された前
   記エラーチェックコード項と状態遷移マトリクス（Ａ＾
   ｚ）とを並列的にモジュロ２乗算して複数個の状態信号
   を発生し、 （Ｆ）前記複数個の状態信号と前記複数個のグループの
   分布信号のあるものとをモジュロ２加算して前記受信デ
   ータバイトと関連するエラーチェックコード信号（Ｓ＿
   ｍ＿＋＿ｚ）を有するエラーチェックコード項のあるも
   のを並列的に発生し、（Ｇ）上記ステップ（Ｆ）におけ
   る複数個のグループのエラーチェックコード項を前記格
   納要素の夫々のものへ同時的に格納し、 （Ｈ）制御信号に応答して前記受信データバイトと前記
   格納要素の最後のものから格納された前記グループのエ
   ラーチェックコード項との間でシステム出力信号として
   選択し、 （Ｉ）第一論理状態を持った制御信号に応答して前記分
   布信号の論理状態を修正し、 （Ｊ）前記制御信号が第一論理状態である場合に前記格
   納要素内に格納されている前記複数個のグループのエラ
   ーチェックコード項を修正なしで前記格納要素の相次ぐ
   ものへ転送し、 （Ｋ）データシーケンス（Ｉ＿ｏ＿（＿Ｌ＿））と関連
   するエラーチェックコード信号（Ｓ＿Ｌ）を有する前記
   複数個のグループのエラーチェックコード項を転送出力
   するために上記ステップ（Ｊ）を実行し、尚受信データ
   バイト（Ｉ＿ｏ＿（＿Ｌ＿））に対応するエラーチェッ
   クコード信号が Ｓ＿ｍ＿＋＿ｚ＝Ａ＾ｚ×Ｓ＿ｍ＋Ｂ＿ｚ×Ｉ＿ｍ＿（
   ＿ｚ＿）の式に従って発生され、前記分布マトリクスは
   それと関連するｚ分布コラムを有しており、且つ前記状
   態遷移マトリクスはそれと関連するｎ遷移コラムを有し
   ており、且つ前記分布マトリクスのｚコラムは前記状態
   遷移マトリクスにおける最高のｚコラムと同一であり、
   且つ各繰返しに対して、Ｓ＿ｍがＳ＿ｍ＿＋＿ｚを置換
   する、 上記各ステップを有することを特徴とする方法。 １３、特許請求の範囲第１２項において、前記第一論理
   状態が論理０であることを特徴する方法。 １４、特許請求の範囲第１２項において、前記分布信号
   の論理状態を修正するステップが、（Ｌ）第一論理状態
   を有する制御信号と前記並列状態信号とを論理的にＡＮ
   Ｄ処理して複数個の格納制御信号を発生し、従って、ス
   テップ（Ｃ）において、前記格納制御信号が前記分布マ
   トリクスとモジュロ２乗算されて前記分布信号を発生す
   る、ステップを有することを特徴とする方法。 １５、特許請求の範囲第１２項において、前記分布信号
   の論理状態を修正するステップが、（Ｍ）ステップ（Ｃ
   ）において発生された分布信号を前記制御信号と論理的
   にＡＮＤ処理して格納制御信号を発生し、従って、ステ
   ップ（Ｆ）において、前記状態信号が前記格納制御信号
   へモジュロ２加算されて前記エラーチェックコード項の
   あるものを発生する、ステップを有することを特徴とす
   る方法。