JPS5840770B2 - 誤り訂正装置に使用されるプログラム可能な多項式発生装置 - Google Patents

Description

【発明の詳細な説明】 本発明は誤り検出ならびに訂正装置に関するものである
。

そのような装置では、情報を受ける装置の方で、データ
転送中に生じた誤りを検出し訂正出来るように情報を送
り出す側で冗長なチェック文字（ｃｈｅｃｋ ｃｌｌａ
ｒａｃｔｅｒ ）をデータの流れに付加している。

そのような装置の基本原理は、多項式の形にした既知の
数学的な関係を先に述べたデータの流れの中に入れられ
た冗長なチェック文字に変換する手順である。

一般的に、この手順は、遅動的移動技法（ｃｙｃｌ ｉ
ｃ ５ｈｉｆｔ ｔｅｃｈｎｉｑｕｅ ）を用いて行な
われ、その中では、データ及び残余チェック文字が互い
に半加算されあるビット（ｂｉｔ）が新しい残余チェッ
ク文字に変えられている。

その手順はデータの流れの中のすべてのデータビットが
処理されるまで繰り返えされる。

したがって最終の残余チェック文字がデータの流れに付
は加えられるチェック文字となる。

本発明はそのような装置内で、データの流れに付は加え
られるチェック文字を発生させるための装置である。

先の出願の中で重要なものは米国特許 ３．８１１，１０８でありこれは誤まり符号発生装置を
示しており、反転誤まりを同定するために用いられてい
る。

今回の発明が前記の特許と違う点は今回の発明は前進方
向及び反転方向の両方における異なった語長のデータに
対しても調整出来るのに対し前記の特許は標準語長のデ
ータに対してのみ反転出来るというところである。

さらに今回の発明が前記の特許に示された装置と異なる
足は、多項式の発生部分を組み入れた事及びその多項式
を計画的に随意に変えられるところである。

米国特許４，００１，７７９には全てが零の場合の特殊
な処理を必要とする誤り訂正装置が示されているが、こ
のような処理は今回の発明では必要無い。

その他出願人の知っている米国特許は、米国特許３．６
７８，４６９；同３，８６６．１７０；同３．７０３，
７０５；及び同３，８７２．４ ：ｊＯｌである。

、本発明は好適実施例では、論理回路に論理積と排他的
論理和素子を使用した形で示されている。

しかしながらこれは発明を限定するものと考えるべきで
は無い、なぜなら、本発明は、論理積と排他的論理和と
なる論理素子を構成する、他の論理装置等を使用する事
によって実行出来るからである。

本発明ではすべての入力信号のオペランドは、入力デー
タマルチプレクサから受信している。

このデータマルチプレクサは、たとえば前進、反転のモ
ードとか、データの長さとかの装置の動作モードを示す
、制御信号を受信している。

したがってマルチプレクサは、受信した入力のオペラン
ドに応じて、個々のビットの通路を整理している。

与えられるか発生させられた使用される多項式は、多数
の多項式許可ゲート、本発明では論理積ゲートを通して
与えられる、そして、これによってチェック文字を発生
させるために、入力データに加えられる処理回路を特徴
づけている。

複数のチェック文字発生ゲートが用意されていてそれは
第１及び第２の組を構成している。

本発明のこの実施例においては、これらのゲートは排他
的論理和ゲートである。

排他的論理和ゲートの第１の組は入力データマルチプレ
クサの出力を受けている。

排他的論理和ゲートの第２の組は入力として、多項式付
勢ゲートからと、それぞれ関連づけられた第１の組の排
他的論理和ゲートからの出力を受けている。

排他的論理和ゲートの第２の組の出力は、出力保持記憶
装置の入力を構成している。

出力保持記憶装置の個々のゲートの出力はすぐ隣のビッ
ト位置にある第１の組の排他的論理和ゲートの入力とな
っている。

図には本発明による、プログラム可能な多項式チェック
文字発生装置１０が示されている。

データ入力はそれぞれの命令語構成ビットに対して図の
左側に示されるように入力端子ＤＯからＤ８に与えられ
る。

これら入力は、入力データマルチプレクサの種々の入力
に共有転送方式すなわち、適当な入力制御信号が存在す
る事又は、制御信号が存在しないという事によって、共
有伝送器制御回路１４に対してマルチプレクサによって
表される与えられた出力位置に適当な入力を接続させる
ような、マルチプレクサ方式によって接続されている。

入力データ共有転送器からのこれら９つの出力のそれぞ
れは図の中の点線で囲まれた、第１の組のチェック文字
付勢ゲート１６を構成している９つの排他論理和ゲート
の１つの入力端子に接続されて示されている。

排他的論理和ゲート１６の組の排他的論理和の個々の出
力は図の中で点線で示されているチェック文字発生ゲー
ト１８の第２の組のそれぞれ対応する排他的論理和ゲー
トの１つの入力となっている。

入力データマルチプレクサ１２の制御入力は「８ビツト
」、「反転」そして「入力付勢（ｅｎａｂｌｅ ）、Ｊ
で示されている。

これら３つの制御入力はデータマルチプレクサに対して
データ入力の４種類のり能な組み合わせの中の１つを選
択するようにさせる。

あらかじめ定められている多項式は図の左上方に示され
ている入力端子ＥＯからＥ８を通して多項式チェック文
字発生装置１０に入れられている。

これらの多項式のビットは本発明の実施例では論理積ゲ
ートで構成されているところの図の中で点線で示された
多数の多項式付勢ゲート２０に与えられている。

これらの論理積ゲートは入力としてあらかじめ定められ
た多項式の１つのビットと、図の左上隅に示された「補
数１人力線からの制御入力とを持ち、それら２つで装置
を管理している。

論理積ゲートの個々の出力は第２の組のチェック文字付
勢発生ゲート１８の排他的論理和ゲートの第２番目の入
力を構成している、第２の組の排他的論理和ゲート１８
のそれぞれの出力は、出力データ保持レジスタ２２の入
力を構成している。

出力データ保持レジスタ２２は出力として、その記憶内
容と等価な信号と、それと論理的に補数関係にある信号
との２つを出す。

保持レジスタ２２の各ビットの直接出力は第１の組のチ
ェック文字付勢発生ゲート１６の排他的論理和ゲートの
第２の入力となり、ここで保持レジスタ２２の各ビット
出力はデータの流れにおけるオペランドの隣のビット位
置のものが入力される排他的論理和ゲートの入力となる
。

図において、保持レジスタ２２の直接出力Ａ乃至Ｈは第
１の組のチェック文字付勢発生ゲート１６の各排他的論
和ゲートの第２の入力Ａ乃至Ｈに夫々接続される。

保持レジスタ２２の直接出力は又論理積ゲート２４に接
続されておりこれは出力信号の特殊な状態を示すデコー
ド素子となっている。

図において保持レジスタ２２の出力Ａ乃至Ｉは論理積ゲ
ート２４の入力Ａ乃至工に夫々接続される。

保持レジスタ２２のすべてのビットの反転出力はもう二
つの論理積ゲート２６の入力として使われておりこれは
保持レジスタの出力内容が２進数字ですべて零である状
態を検出するために使われている。

保持レジスタ２２の反転出力Ｊ乃至Ｓは論理積ゲート２
６の入力Ｊ乃至Ｓに夫々接続される。

保持レジスタ２２は、その名の通りの機能を持つ「基準
動作実施信号（ｃｘｏｃｋ ） Ｊ及び「消去（ｃｌｅ
ａｒ）信号」と名付けられた入力制御線で操作されてい
る。

本発明によるさらに大きな装置は、与えられた任意の語
長の大きな命令語に対して、図に示されているような異
なった語長の小部分を互いに組み合わせて行くことによ
って拡張することが出来る。

一連の似かよった素子の中の第一番目又は最上位に置か
れた素子に与えられる帰環入力信号制御線２８は、この
ような一連の装置の最後の装置の多項式出力ビットとな
る。

どの基板の上の帰環入力信号２８はその前の基板の多項
式出力ビットである。

すなわち、一つの装置の出力線３０はその次の装置の入
力２８の入力線に接続されている。

出力チェック文字は、次のような様式で形造られる。

基準動作実施信号の立ち上がりで、残余チェック文字が
保持レジスタ２２に転送される。

基準動作実施信号はデータビットと同一の周波数である
。

この残余チェック文字は、別の基準動作実施信号が更新
されるか、残余消去信号が記憶を消去するまで保持レジ
スタ内に保持されている。

一連のすべての装置における各装置の補数前進出力信号
（ｃｏｍｐｌｅｍｅｎｔ ｆｏｒｗａｒｄ ｏｕｔｐ
ｕｔｓｉｇｎａｌ ）３２は次の装置の補数入力信号３
４として使用される。

この信号は多項式文字のある特定のビットが反転したこ
とを判定するために使用される。

本発明によれば、循環符号又は残余は次のような方法で
造られる。

最初に、保持レジスタ２２を消去するために、消去信号
が与えられる。

そこで１．多項式許ＯＴＥ’０乃至Ｅ８が望みの多項式
の型に準備される。

これらの項はすべてのデータのかたまりが供給されるま
で付勢線に残存している。

論理積ゲート２０は拡張された装置における多項式付勢
を制御するために使用される。

拡張された装置において第１段目には論理的な補数信号
が入力として加えられる。

それに続く段では補数入力には、前段の補数前進出力が
接続される。

第１段では帰環入力には、最終段の保持レジスタの最下
位の出力が接続される。

それに引き続く段では、帰環入力には前段の保持レジス
タの最下位の出力が接続される。

多項式付勢信号といっしょに、制御信号がデータマルチ
プレクサに準備される。

これらの信号はすべてのデータのかたまりが入力される
まで、効力を残存させている。

付勢入力は、他の制御入力によって定められた方向にマ
ルチプレクサを通してデータを通過させる。

この入力が無い時には、データマルチプレクサの出力は
すべて論理的に零の状態となる。

これは、転送路にデータが有るか否かの確認をする事無
しに残余を移動（ｓｈｉｆｔ）するために用いられる。

「反転」入力はデータ入力、ＤＯ乃至Ｄ８を反転（すな
わちＤ８乃至ＤＯ）とする。

８ビット信号は８ビツト基準でデータを反転（すなわち
Ｄｌ乃至ＤＯ）させる。

これら先に述べた事は限定的に考えられるべきでは無く
、特別な設計の目的でブロック途中で多項式付勢及びデ
ータマルチプレクサ制御は必要に応じて変えられても良
い。

他の入力が準備された後データビットはデータ入力ＤＯ
乃至Ｄ８に入力される。

直列モードではＤＯのみが使用され、並列モードではす
べてのデータ入力が使用される。

直列モードでは次の段階に進む前にすべてのデータを適
当な番地に移される。

データ共有転送器１２の出力は第１の組の排他的論理和
ゲート１６において保持レジスタ２２の一つづつずらさ
れた出力に半加算される。

データの第１番目の時点では保持レジスタはすべて零で
あるため、この段階では何も行なわれない。

第１の組の排他的論理和ゲートの出力は第２の組の排他
的論理和ゲート１８において、多項式付勢ゲート２０出
力に半加算される。

第２の組の排他的論理和ゲートは、多項式付勢入力と、
帰環入力がある際に信号を論理的に反転する役割を持っ
ている。

基準動作実施信号は、基準動作実施入力切換器が論理的
な零から、論理的な１に切り換わった時に供給される。

第２の組の排他的論理和ゲートの出力は基準動作信号に
よって保持レジスタに保持される。

保持記憶装置の出力は次のデータのフレーム（並行方式
の時）又はビット信号（直列方式の時）及びそれに伴な
う基準動作実施信号とを待受けるように、第１の組の排
他的論理和ゲートの次の高位のビットに帰環される。

データ入力、基準動作実施信号、移動という過程はすべ
てのデータのかたまりが入力されるまで個々のデータの
一群に対して繰り返えされる。

データのかたまりの最終段では、保持レジスタにはこの
装置が送信端にある時には循環符号が、又、この装置が
受信端にある時には残余が含まれている。

【図面の簡単な説明】

図面は、本発明の一実施例を含む論理構成の模式的系統
図である。 １０：誤り検出装置、１２：マルチプレクサ、１４：マ
ルチプレクサ制御回路、１６：排他的論理和ゲート、１
８：排他的論理和ゲート、２０：論理積ゲート、２２：
保持レジスタ、２４．２６：論理積ゲート、２８：帰環
入力信号制御線、３０：保持レジスタの出力、３２：補
数前進出力信号、３４：補数入力信号、ＩＡ：基準動作
実施信号、１Ｂ二消去信号、ＥＯ〜Ｅ８：多項式入力端
子、ＩＮ、ＩＰ、ＩＱ：マルチプレクサ制御入力、ＤＯ
〜Ｄ８：データ入力端子。

Claims (1)

1. 【特許請求の範囲】 １ 誤り訂正装置ｊこ使用されるプログラム可能な多項
   式発生装置において： 多項式入力を表わす複数の多項式付勢入力信号を受ける
   ための装置； 入力オペランドのビットを表わす入力データ信号を受け
   るための装置； 前記の入力データ信号を受けるための装置に接続され、
   制御信号に応じてあらかじめ定められた数のパターンの
   内の任意のパターンに前記信号を選択的にマルチプレク
   サするためのデータ入力マルチプレクサ； 少なくとも１つの制御信号に応答するようにされた複数
   の多項式付勢ゲートであって、前記ゲートの各々が前記
   複数の多項式付勢入力信号を受けるための装置に接続さ
   れている前記複数の多項式付勢ゲート； 第１の組の複数個のチェック文字発生用ゲート、及び第
   ２の組の複数個のチェック文字発生用ゲート；及び 少なくとも１つの制御信号に応答するようにされ、前記
   第２の組のチェック文字発生用ゲートの各々に接続され
   前記第２の組のチェック文字発生用ゲートからの信号の
   各々を記憶する保持レジスタ； を有し、前記第１の組のチェック文字発生用ゲートの各
   々は第１の入力を前記データ入力マルチプレクサから受
   けかつ第２の入力を前記保持レジスタから受け、前記第
   ２の組のチェック文字発生用ゲートの各々は第１の入力
   を前記多項式付勢ゲートから受けかつ第２の入力を前記
   第１の組のチェック文字発生ゲートから受け；更に 前記保持レジスタの出力に接続され前記のレジスタの内
   容がすべて零である場合にデコード信号を出力する第１
   のデコードゲート；及び 前記保持レジスタからの出力信号を受けるように接続さ
   れ、前記記憶装置の内容があらかじめ定められた量にな
   った場合にデコード信号を出力する第２のデコードゲー
   ト； を有する誤り訂正装置に使用されるプログラム可能な多
   項式発生装置。 ２、特許請求の範囲第１項に記載の多項式発生装置にお
   いて、前記第１の組のチェック文字発生ゲートの第２の
   入力が前記第２のデコードゲートへの入力と同じになさ
   れた、誤り訂正装置に使用されるプログラム可能な多項
   式発生装置。