JPH04215332A - データ転送エラー検出装置及びその方法 - Google Patents
データ転送エラー検出装置及びその方法Info
- Publication number
- JPH04215332A JPH04215332A JP9144222A JP4422291A JPH04215332A JP H04215332 A JPH04215332 A JP H04215332A JP 9144222 A JP9144222 A JP 9144222A JP 4422291 A JP4422291 A JP 4422291A JP H04215332 A JPH04215332 A JP H04215332A
- Authority
- JP
- Japan
- Prior art keywords
- bit
- data
- signature
- register
- error detection
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Pending
Links
- 238000012546 transfer Methods 0.000 title claims description 18
- 238000000034 method Methods 0.000 title description 25
- 238000001514 detection method Methods 0.000 claims abstract description 33
- 238000004891 communication Methods 0.000 claims description 7
- PCTMTFRHKVHKIS-BMFZQQSSSA-N (1s,3r,4e,6e,8e,10e,12e,14e,16e,18s,19r,20r,21s,25r,27r,30r,31r,33s,35r,37s,38r)-3-[(2r,3s,4s,5s,6r)-4-amino-3,5-dihydroxy-6-methyloxan-2-yl]oxy-19,25,27,30,31,33,35,37-octahydroxy-18,20,21-trimethyl-23-oxo-22,39-dioxabicyclo[33.3.1]nonatriaconta-4,6,8,10 Chemical compound C1C=C2C[C@@H](OS(O)(=O)=O)CC[C@]2(C)[C@@H]2[C@@H]1[C@@H]1CC[C@H]([C@H](C)CCCC(C)C)[C@@]1(C)CC2.O[C@H]1[C@@H](N)[C@H](O)[C@@H](C)O[C@H]1O[C@H]1/C=C/C=C/C=C/C=C/C=C/C=C/C=C/[C@H](C)[C@@H](O)[C@@H](C)[C@H](C)OC(=O)C[C@H](O)C[C@H](O)CC[C@@H](O)[C@H](O)C[C@H](O)C[C@](O)(C[C@H](O)[C@H]2C(O)=O)O[C@H]2C1 PCTMTFRHKVHKIS-BMFZQQSSSA-N 0.000 description 3
- 238000010586 diagram Methods 0.000 description 3
- 238000012545 processing Methods 0.000 description 3
- 230000005540 biological transmission Effects 0.000 description 2
- 230000007423 decrease Effects 0.000 description 2
- 101000582320 Homo sapiens Neurogenic differentiation factor 6 Proteins 0.000 description 1
- 101000929942 Megasphaera elsdenii Acyl-CoA dehydrogenase, short-chain specific Proteins 0.000 description 1
- 102100030589 Neurogenic differentiation factor 6 Human genes 0.000 description 1
- 210000001072 colon Anatomy 0.000 description 1
- 238000012937 correction Methods 0.000 description 1
- 125000004122 cyclic group Chemical group 0.000 description 1
- 230000001419 dependent effect Effects 0.000 description 1
- 238000013461 design Methods 0.000 description 1
- 230000000694 effects Effects 0.000 description 1
- 230000007613 environmental effect Effects 0.000 description 1
- 235000015067 sauces Nutrition 0.000 description 1
Classifications
-
- H—ELECTRICITY
- H03—ELECTRONIC CIRCUITRY
- H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
- H03M13/00—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes
Landscapes
- Physics & Mathematics (AREA)
- Probability & Statistics with Applications (AREA)
- Engineering & Computer Science (AREA)
- Theoretical Computer Science (AREA)
- Detection And Correction Of Errors (AREA)
- Error Detection And Correction (AREA)
- Detection And Prevention Of Errors In Transmission (AREA)
Abstract
(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。
め要約のデータは記録されません。
Description
【０００１】
【産業上の利用分野】本発明は、一般に、１つのロケー
ションから別のロケーションに、データ・チャンネル等
を介して、デジタル・データを通信または伝送する分野
に関するものである。特に、本発明は、データ転送エラ
ーを検出するための方法および装置に関する。
ションから別のロケーションに、データ・チャンネル等
を介して、デジタル・データを通信または伝送する分野
に関するものである。特に、本発明は、データ転送エラ
ーを検出するための方法および装置に関する。
【０００２】
【０００３】最新データ処理および通信システムでは、
個別のデバイスおよびしばしば異種（ｄｉｓｐａｒａｔ
ｅ）デバイス間でデータを転送することが望まれること
がある。送信デバイス（すなわち「ソース（ｓｏｕｒｃ
ｅ）」）から受信デバイス（すなわち「レシーバ」）に
転送されるデータがその行き先に達する前に何らかによ
ってひずむと、このようなシステムに共通の問題が生じ
る。このようなひずみには、環境ノイズ（無線周波数シ
ステムの場合）、不良またはノイズの多い伝送回線、ま
たは不良データ・チャンネル、または「バス」などの様
々な原因が考えられる。後者は、特にデジタル・システ
ムにおいて特に共通のエラー原因である。１００％エラ
ーのないデータ転送を保証するための手段は現在ないの
で、システム設計者は、エラーが発生したときにエラー
を検出したり、適切な処理をおこなうための手段を得る
ために努力しなければならなかった。
個別のデバイスおよびしばしば異種（ｄｉｓｐａｒａｔ
ｅ）デバイス間でデータを転送することが望まれること
がある。送信デバイス（すなわち「ソース（ｓｏｕｒｃ
ｅ）」）から受信デバイス（すなわち「レシーバ」）に
転送されるデータがその行き先に達する前に何らかによ
ってひずむと、このようなシステムに共通の問題が生じ
る。このようなひずみには、環境ノイズ（無線周波数シ
ステムの場合）、不良またはノイズの多い伝送回線、ま
たは不良データ・チャンネル、または「バス」などの様
々な原因が考えられる。後者は、特にデジタル・システ
ムにおいて特に共通のエラー原因である。１００％エラ
ーのないデータ転送を保証するための手段は現在ないの
で、システム設計者は、エラーが発生したときにエラー
を検出したり、適切な処理をおこなうための手段を得る
ために努力しなければならなかった。
【０００４】周知のエラー検出方法は、チェックサム（
ｃｈｅｃｋｓｕｍ）およびＣＲＣ法がある。両者は、伝
送するデータ・ワードのブロックのための「シグネチュ
ア（ｓｉｇｎａｔｕｒｅ）」の計算を伴うものである。 データ・ワード（または、「データ・セット」）のブロ
ックをバス上で送信するときには、データ・セットを表
す準固有ワード（ｑｕａｓｉ−ｕｎｉｑｕｅ ｗｏｒ
ｄ）を計算するための手段をバスのソース端部に設ける
。この準固有ワードは「シグネチュア」と呼ばれている
。バスのソース端部で計算するときには、期待「シグネ
チュア」（ＳＥ）と呼ばれている。同様なシグネチュア
が、バスのレシーバ端において計算される。これは、「
エラー検出シグネチュア（Ｓ）」と呼ばれ、期待シグネ
チュアと比較される。ＳＥおよびＳが異なる場合、受信
データにエラーが発生したとみられ、データを再伝送す
る。しかし、予想とは逆に、ＳＥとＳが等しいことは、
送信信にエラーがないとは必ずしも示すものではない。 これは、エラー検出方法の複雑性が減少するにつれてエ
ラー検出の確率が一般に小さくなるという事実による。
ｃｈｅｃｋｓｕｍ）およびＣＲＣ法がある。両者は、伝
送するデータ・ワードのブロックのための「シグネチュ
ア（ｓｉｇｎａｔｕｒｅ）」の計算を伴うものである。 データ・ワード（または、「データ・セット」）のブロ
ックをバス上で送信するときには、データ・セットを表
す準固有ワード（ｑｕａｓｉ−ｕｎｉｑｕｅ ｗｏｒ
ｄ）を計算するための手段をバスのソース端部に設ける
。この準固有ワードは「シグネチュア」と呼ばれている
。バスのソース端部で計算するときには、期待「シグネ
チュア」（ＳＥ）と呼ばれている。同様なシグネチュア
が、バスのレシーバ端において計算される。これは、「
エラー検出シグネチュア（Ｓ）」と呼ばれ、期待シグネ
チュアと比較される。ＳＥおよびＳが異なる場合、受信
データにエラーが発生したとみられ、データを再伝送す
る。しかし、予想とは逆に、ＳＥとＳが等しいことは、
送信信にエラーがないとは必ずしも示すものではない。 これは、エラー検出方法の複雑性が減少するにつれてエ
ラー検出の確率が一般に小さくなるという事実による。
【０００５】例えば、従来のチェックサム方法では、オ
ーバフローとは無関係に一群のデータ・ワードを合計す
る。オーバフローが起こったときには以下のようになり
、そうでなければ検出可能なエラーが消失することがあ
る。
ーバフローとは無関係に一群のデータ・ワードを合計す
る。オーバフローが起こったときには以下のようになり
、そうでなければ検出可能なエラーが消失することがあ
る。
【０００６】データ・セットが３つの４ビット・ワード
「Ａ」、「Ｂ」および「Ｃ」から成るものと仮定する。 Ａ＝１０００、Ｂ＝０１００、Ｃ＝００１０とする。セ
ットＡ、Ｂ、Ｃに対するチェックサム期待シグネチュア
ＳＥは、数１に示すように「１１１０」となる。
「Ａ」、「Ｂ」および「Ｃ」から成るものと仮定する。 Ａ＝１０００、Ｂ＝０１００、Ｃ＝００１０とする。セ
ットＡ、Ｂ、Ｃに対するチェックサム期待シグネチュア
ＳＥは、数１に示すように「１１１０」となる。
【数１】
【０００７】ここでデータ・バスに関する問題により、
各ワードの最上位ビット（ＭＳＢ）が１になったまま（
ｓｔｕｃｋ）の状態であった場合を仮定する。これは、
Ａに影響を及ぼさないが、ＢおよびＣの受信値にエラー
を引き起こす。受信データ・ワードを各々Ａ’、Ｂ’、
Ｃ’で示すと、エラー補正シグネチュアＳ’は、「１１
１０」となる。
各ワードの最上位ビット（ＭＳＢ）が１になったまま（
ｓｔｕｃｋ）の状態であった場合を仮定する。これは、
Ａに影響を及ぼさないが、ＢおよびＣの受信値にエラー
を引き起こす。受信データ・ワードを各々Ａ’、Ｂ’、
Ｃ’で示すと、エラー補正シグネチュアＳ’は、「１１
１０」となる。
【数２】
【０００８】このように、受信データの重大なエラーに
もかかわらず、ＳＥとＳ’は等しく、エラーは１つも検
出されない。
もかかわらず、ＳＥとＳ’は等しく、エラーは１つも検
出されない。
【０００９】従来のＣＲＣ（「サイクリック冗長コード
」（ｃｙｃｌｉｃ ｒｅｄｕｎｄａｎｃｙ ｃｏｄ
ｅ））方法では、ワードの既知シーケンスを多項定数で
割り、その余りは蓄積されて期待シグネチュアを形成す
る。例えば、１９８２年出版（Ｄｉｇｉｔａｌ Ｐｒ
ｅｓｓ）のＳｃｅｗｉｏｒｅｋ、Ｓｗａｒｚ著の「Ｔｈ
ｅＴｈｅｏｒｙ ＆ Ｐｒａｃｔｉｃｅ ｏｆ
Ｒｅｌｉａｂｌｅ ＳｙｓｔｅｍＤｅｓｉｇｎ」の
第１０１頁以降を参照されたい。ＣＲＣ方法に関する主
な不利な点は、生成されるシグネチュアが、データ・ワ
ードの送られる順序に依存することである。シーケンス
ＡＢＣＤは、ＢＡＣＤとは異なるシグネチュアを生成す
る。したがって、例えば、この方法はグラフィックス・
システムにおいて特に困難をもたらし、ここでは、ディ
スプレイ上にピクセルを生成するためにグラフィックス
回路からデータを読み込むシーケンスの変動するおそれ
がある。
」（ｃｙｃｌｉｃ ｒｅｄｕｎｄａｎｃｙ ｃｏｄ
ｅ））方法では、ワードの既知シーケンスを多項定数で
割り、その余りは蓄積されて期待シグネチュアを形成す
る。例えば、１９８２年出版（Ｄｉｇｉｔａｌ Ｐｒ
ｅｓｓ）のＳｃｅｗｉｏｒｅｋ、Ｓｗａｒｚ著の「Ｔｈ
ｅＴｈｅｏｒｙ ＆ Ｐｒａｃｔｉｃｅ ｏｆ
Ｒｅｌｉａｂｌｅ ＳｙｓｔｅｍＤｅｓｉｇｎ」の
第１０１頁以降を参照されたい。ＣＲＣ方法に関する主
な不利な点は、生成されるシグネチュアが、データ・ワ
ードの送られる順序に依存することである。シーケンス
ＡＢＣＤは、ＢＡＣＤとは異なるシグネチュアを生成す
る。したがって、例えば、この方法はグラフィックス・
システムにおいて特に困難をもたらし、ここでは、ディ
スプレイ上にピクセルを生成するためにグラフィックス
回路からデータを読み込むシーケンスの変動するおそれ
がある。
【００１０】したがって、従来よりも高いエラー検出率
を有し、データ・ワードを送信する順序とは無関係にエ
ラーを検出し、比較的複雑でなく容易に実施することが
できるエラー検出シグネチュア装置および方法が必要と
されている。本発明はこれらの目標を達成する。
を有し、データ・ワードを送信する順序とは無関係にエ
ラーを検出し、比較的複雑でなく容易に実施することが
できるエラー検出シグネチュア装置および方法が必要と
されている。本発明はこれらの目標を達成する。
【００１１】
【発明の目的】本発明の目的は、上述の問題点を解消し
、高いエラー検出率を備え、簡易な方法でデータ転送に
生じるエラーを検出することにある。
、高いエラー検出率を備え、簡易な方法でデータ転送に
生じるエラーを検出することにある。
【００１２】
【発明の概要】本発明では、通信媒体を介してソース（
または通信媒体のソース端部）からレシーバにＮビット
のデータ・ワードを転送する方式のシステムにおいて、
期待シグネチュアおよびエラー検出シグネチュアを生成
するための方法を得る。本発明の好適な一実施例は次の
ステップから成る。（イ）第１のＮ＋１ビット・レジス
タのＮビット位置のデータ・ワードを累積し、ソースか
ら転送されるデータ・ワードをモジュロ２Ｎ 演算によ
り合計することにより、ソース端において期待シグネチ
ュアＳＥを生成する。この第１のＮ＋１ビット・レジス
タの内容はＳＥを定義する。総和プロセスにより生成さ
れるキャリー・アウト（ＣＯ）は、Ｎ＋１ビット位置の
指定ビットに記憶される。（ロ）第２のＮ＋１ビット・
レジスタのＮビット位置の受信データ・ワードを累積さ
せ、モジュロ２Ｎ 演算により合計することにより、レ
シーバ端においてエラー検出シグネチュアＳを生成する
。この第２のＮ＋１ビット・レジスタの内容はＳを定義
する。ステップ（イ）と同様に、ＣＯはＮ＋１ビット位
置の指定ビットに記憶される。（ハ）ＳとＳＥを比較し
、その間に何かの相違（ｄｉｓｃｒｅｐａｎｃｙ）があ
るかどうかを見つける。相違がある場合には、データ転
送でエラーが起こったと想定され、適切な表示が与えら
れる。
または通信媒体のソース端部）からレシーバにＮビット
のデータ・ワードを転送する方式のシステムにおいて、
期待シグネチュアおよびエラー検出シグネチュアを生成
するための方法を得る。本発明の好適な一実施例は次の
ステップから成る。（イ）第１のＮ＋１ビット・レジス
タのＮビット位置のデータ・ワードを累積し、ソースか
ら転送されるデータ・ワードをモジュロ２Ｎ 演算によ
り合計することにより、ソース端において期待シグネチ
ュアＳＥを生成する。この第１のＮ＋１ビット・レジス
タの内容はＳＥを定義する。総和プロセスにより生成さ
れるキャリー・アウト（ＣＯ）は、Ｎ＋１ビット位置の
指定ビットに記憶される。（ロ）第２のＮ＋１ビット・
レジスタのＮビット位置の受信データ・ワードを累積さ
せ、モジュロ２Ｎ 演算により合計することにより、レ
シーバ端においてエラー検出シグネチュアＳを生成する
。この第２のＮ＋１ビット・レジスタの内容はＳを定義
する。ステップ（イ）と同様に、ＣＯはＮ＋１ビット位
置の指定ビットに記憶される。（ハ）ＳとＳＥを比較し
、その間に何かの相違（ｄｉｓｃｒｅｐａｎｃｙ）があ
るかどうかを見つける。相違がある場合には、データ転
送でエラーが起こったと想定され、適切な表示が与えら
れる。
【００１３】本発明は、データ・ワードがソースから転
送される順序とは無関係に、データ転送における相違を
検出することができる。
送される順序とは無関係に、データ転送における相違を
検出することができる。
【００１４】ＳＥおよびＳを生成する望ましい一実施例
は、各々通信媒体のソース端およびレシーバ端にある実
質的に同等な回路から成る。本発明を実施するための回
路は、Ｎビットの和および加算器からのキャリー・アウ
トを記憶するためのＮ＋１ビット・レジスタに結合し、
転送すべきデータ・ワードの和を求めるための加算器か
ら成る。Ｎ＋１ビット・レジスタの内容は、レジスタが
通信媒体のソース端またはレシーバ端のどちらにあるか
により、ＳまたはＳＥを定義する。
は、各々通信媒体のソース端およびレシーバ端にある実
質的に同等な回路から成る。本発明を実施するための回
路は、Ｎビットの和および加算器からのキャリー・アウ
トを記憶するためのＮ＋１ビット・レジスタに結合し、
転送すべきデータ・ワードの和を求めるための加算器か
ら成る。Ｎ＋１ビット・レジスタの内容は、レジスタが
通信媒体のソース端またはレシーバ端のどちらにあるか
により、ＳまたはＳＥを定義する。
【００１５】加算器は、第１のＮまたはＮ＋１ビット・
データ・ワードを受信する第１入力ポートと、Ｎ＋１ビ
ット・レジスタから第２のＮまたはＮ＋１ビット・デー
タ・ワードを受信するための、Ｎ＋１ビット・レジスタ
に結合した第２入力ポートと、第１および第２Ｎまたは
Ｎ＋１ビット・データ・ワードの和をＮ＋１ビット・レ
ジスタに与えるための、Ｎ＋１ビット・レジスタに結合
した出力ポートと、ＣＯをＮ＋１ビット・レジスタの指
定ビットに提供合する、Ｎ＋１ビット・レジスタに結合
したキャリー・ポートから成る。
データ・ワードを受信する第１入力ポートと、Ｎ＋１ビ
ット・レジスタから第２のＮまたはＮ＋１ビット・デー
タ・ワードを受信するための、Ｎ＋１ビット・レジスタ
に結合した第２入力ポートと、第１および第２Ｎまたは
Ｎ＋１ビット・データ・ワードの和をＮ＋１ビット・レ
ジスタに与えるための、Ｎ＋１ビット・レジスタに結合
した出力ポートと、ＣＯをＮ＋１ビット・レジスタの指
定ビットに提供合する、Ｎ＋１ビット・レジスタに結合
したキャリー・ポートから成る。
【００１６】Ｎ＋１ビット・レジスタは、第１および第
２ＮまたはＮ＋１ビット・データ・ワード（すなわち、
ＳＥまたはＳ）の和を記憶するためのＮビット、および
ＣＯを記憶するための指定ビットから成る。ＣＯビット
・ロケーションは、シグネチュアの一部であると考える
ことができる。Ｎが２の累乗、例えば２、４、８、１６
、３２等で、通信媒体がＮビット・データ・ワード・バ
スであることがさらに好ましいが、本発明は２の累乗の
Ｎ値に限定されない。
２ＮまたはＮ＋１ビット・データ・ワード（すなわち、
ＳＥまたはＳ）の和を記憶するためのＮビット、および
ＣＯを記憶するための指定ビットから成る。ＣＯビット
・ロケーションは、シグネチュアの一部であると考える
ことができる。Ｎが２の累乗、例えば２、４、８、１６
、３２等で、通信媒体がＮビット・データ・ワード・バ
スであることがさらに好ましいが、本発明は２の累乗の
Ｎ値に限定されない。
【００１７】
【発明の実施例】発明に従ってエラー検出シグネチュア
を生成するための装置の望ましい実施例についてこれか
ら図面を参照しながら説明するが、同じ参照番号が付さ
れているものは同様な構成素子を示すものである。
を生成するための装置の望ましい実施例についてこれか
ら図面を参照しながら説明するが、同じ参照番号が付さ
れているものは同様な構成素子を示すものである。
【００１８】図１では、Ｎビット・データ・ワード（Ｎ
は整数、望ましくは２の累乗、例えば４、８、１６、３
２等）は、Ｎビット・チャンネルまたはバス１２を介し
てソース１０からレシーバ１４に転送される。ソース１
０およびレシーバ１４は、各々が別個のコンピュータで
あるか、１つのコンピュータ・システム内の別個のプロ
セッサにすることもできる。例えば、ソース１０をグラ
フィックス・モニタに供給するピクセル・データを処理
するためのピクセル・プロセッサとし、レシーバ１４を
図形データに対して数学的計算を行うためのデバイスと
して設けることができる。本発明は、ソース１０から送
信されるデータとレシーバ１４の受信するデータとの相
違（ある場合）を検出することのできる手段を含む。
は整数、望ましくは２の累乗、例えば４、８、１６、３
２等）は、Ｎビット・チャンネルまたはバス１２を介し
てソース１０からレシーバ１４に転送される。ソース１
０およびレシーバ１４は、各々が別個のコンピュータで
あるか、１つのコンピュータ・システム内の別個のプロ
セッサにすることもできる。例えば、ソース１０をグラ
フィックス・モニタに供給するピクセル・データを処理
するためのピクセル・プロセッサとし、レシーバ１４を
図形データに対して数学的計算を行うためのデバイスと
して設けることができる。本発明は、ソース１０から送
信されるデータとレシーバ１４の受信するデータとの相
違（ある場合）を検出することのできる手段を含む。
【００１９】本発明では、装置１６は、バス１２のソー
ス端において期待シグネチュアＳＥを、バス１２のレシ
ーバ端においてエラー検出シグネチュアＳを生成するた
めに設けられる。ワードがソース１０からレシーバ１４
にシリアルに送信されるときに、ＳＥは、以下に説明す
る方法により、データ・ワードの１セット２０から誘導
することができる。例えば、４個のデータ・ワード「Ａ
」「Ｂ」「Ｃ」および「Ｄ」がソース１０からレシーバ
１４にシリアルに転送されるものと仮定する。簡単にす
るために、Ａ、Ｂ、Ｃ、Ｄは夫々４ビット・ワード（す
なわち、Ｎ＝４）とする。Ａ、Ｂ、Ｃ、Ｄは、バス１２
を介してソース１０から連続的に送られるので、本発明
により期待シグネチュアＳＥを計算するシグネチュア装
置１６にこれらは同時に供給される。期待シグネチュア
ＳＥは、Ｎ＋１ビット幅（この例では、５ビット）であ
り、ワードＡ、Ｂ、Ｃ、Ｄ等がバス１２を介して送られ
るときに連続的に更新される。本発明では、シグネチュ
ア装置１６は、バスのソース端１０およびバスのレシー
バ１４に設けられる。期待シグネチュアＳＥはデータ・
セット２０（例えば、Ａ、Ｂ、Ｃ、Ｄから成るワード）
から計算されるので、エラー検出シグネチュアＳは受信
データ・セット２０’から計算される。エラーがないと
き、すなわち送信および受信データ・セット２０、２０
’の間に差がない場合、ＳおよびＳＥは等しい。エラー
がある場合には、ＳおよびＳＥは異なるので、適切な処
理例えばデータの再伝送などを施こすことができる。
ス端において期待シグネチュアＳＥを、バス１２のレシ
ーバ端においてエラー検出シグネチュアＳを生成するた
めに設けられる。ワードがソース１０からレシーバ１４
にシリアルに送信されるときに、ＳＥは、以下に説明す
る方法により、データ・ワードの１セット２０から誘導
することができる。例えば、４個のデータ・ワード「Ａ
」「Ｂ」「Ｃ」および「Ｄ」がソース１０からレシーバ
１４にシリアルに転送されるものと仮定する。簡単にす
るために、Ａ、Ｂ、Ｃ、Ｄは夫々４ビット・ワード（す
なわち、Ｎ＝４）とする。Ａ、Ｂ、Ｃ、Ｄは、バス１２
を介してソース１０から連続的に送られるので、本発明
により期待シグネチュアＳＥを計算するシグネチュア装
置１６にこれらは同時に供給される。期待シグネチュア
ＳＥは、Ｎ＋１ビット幅（この例では、５ビット）であ
り、ワードＡ、Ｂ、Ｃ、Ｄ等がバス１２を介して送られ
るときに連続的に更新される。本発明では、シグネチュ
ア装置１６は、バスのソース端１０およびバスのレシー
バ１４に設けられる。期待シグネチュアＳＥはデータ・
セット２０（例えば、Ａ、Ｂ、Ｃ、Ｄから成るワード）
から計算されるので、エラー検出シグネチュアＳは受信
データ・セット２０’から計算される。エラーがないと
き、すなわち送信および受信データ・セット２０、２０
’の間に差がない場合、ＳおよびＳＥは等しい。エラー
がある場合には、ＳおよびＳＥは異なるので、適切な処
理例えばデータの再伝送などを施こすことができる。
【００２０】２つの他の好ましい方法、およびシグネチ
ュアＳおよびＳＥを生成するための対応する装置を本願
明細書に説明されている。明らかな理由により、所与の
システムにおいて同じ方法を用いなければならない。こ
れらの代替方法および装置については、各々図２および
図３を参照して次に述べる。
ュアＳおよびＳＥを生成するための対応する装置を本願
明細書に説明されている。明らかな理由により、所与の
システムにおいて同じ方法を用いなければならない。こ
れらの代替方法および装置については、各々図２および
図３を参照して次に述べる。
【００２１】図２には、期待シグネチュアＳＥおよびエ
ラー検出シグネチュアＳを生成するための装置１６の第
一の好適な実施例は、Ｎ＋１ビット加算器２２およびＮ
＋１ビットのシグネチュア・レジスタ２４から構成され
る。加算器２２は、モジュロ２Ｎ 演算を用いて、シグ
ネチュア・レジスタ２４の内容を、入力データ・セット
２０’の各ワードＡ、Ｂ、Ｃ、Ｄ等に累積的に加算する
。 各和（Σ２ ）はシグネチュア・レジスタ２４に記憶さ
れる。シグネチュア・レジスタ２４の内容は、ソース１
０またはレシーバ１４のどちらにあるかにより、期待シ
グネチュアＳＥまたはエラー検出シグネチュアＳのいず
れかである。したがって、ＳおよびＳＥは、以後は総称
的にΣ１ と呼ぶ。図２の実施例では、「１」の値のビ
ットが、入力データ・セット２０’の最下位ビット（Ｌ
ＳＢ）の右に追加される。例えば、４ビット・ワードＡ
＝「１０００」が与えられると、加算器２２はビット「
１０００１」を受信する。同様に、４ビット・ワードＢ
＝「０１００」が与えられると、加算器２２は「０１０
０１」を受信する。本発明によれば、連続するワードが
合計されると、その結果はシグネチュア・レジスタ２４
に記憶される。しかし、その結果が記憶される前に、該
結果のＬＳＢが廃棄される。ＭＳＢからのキャリー・ア
ウト（ＣＯ）は、シグネチュア・レジスタ２４のＬＳＢ
、すなわちΣ１ のＬＳＢに記憶される。このようにし
て、従来のオーバフロー問題は解決される。さらに、所
与のデータ・セット２０および２０’に対して生成され
るシグネチュアは、個別のデータ・ワードの送られる正
確な順序より独立している。言い換えると、ＡＢＣＤの
シグネチュアは、ＢＡＣＤ、ＢＣＡＤ等のシグネチュア
と同じである。以下の例では、当該方法の応用を示す。
ラー検出シグネチュアＳを生成するための装置１６の第
一の好適な実施例は、Ｎ＋１ビット加算器２２およびＮ
＋１ビットのシグネチュア・レジスタ２４から構成され
る。加算器２２は、モジュロ２Ｎ 演算を用いて、シグ
ネチュア・レジスタ２４の内容を、入力データ・セット
２０’の各ワードＡ、Ｂ、Ｃ、Ｄ等に累積的に加算する
。 各和（Σ２ ）はシグネチュア・レジスタ２４に記憶さ
れる。シグネチュア・レジスタ２４の内容は、ソース１
０またはレシーバ１４のどちらにあるかにより、期待シ
グネチュアＳＥまたはエラー検出シグネチュアＳのいず
れかである。したがって、ＳおよびＳＥは、以後は総称
的にΣ１ と呼ぶ。図２の実施例では、「１」の値のビ
ットが、入力データ・セット２０’の最下位ビット（Ｌ
ＳＢ）の右に追加される。例えば、４ビット・ワードＡ
＝「１０００」が与えられると、加算器２２はビット「
１０００１」を受信する。同様に、４ビット・ワードＢ
＝「０１００」が与えられると、加算器２２は「０１０
０１」を受信する。本発明によれば、連続するワードが
合計されると、その結果はシグネチュア・レジスタ２４
に記憶される。しかし、その結果が記憶される前に、該
結果のＬＳＢが廃棄される。ＭＳＢからのキャリー・ア
ウト（ＣＯ）は、シグネチュア・レジスタ２４のＬＳＢ
、すなわちΣ１ のＬＳＢに記憶される。このようにし
て、従来のオーバフロー問題は解決される。さらに、所
与のデータ・セット２０および２０’に対して生成され
るシグネチュアは、個別のデータ・ワードの送られる正
確な順序より独立している。言い換えると、ＡＢＣＤの
シグネチュアは、ＢＡＣＤ、ＢＣＡＤ等のシグネチュア
と同じである。以下の例では、当該方法の応用を示す。
【００２２】データ・セットＡ、Ｂ、Ｃ、Ｄが、バス１
２を介してソース１０からレシーバ１４に送られること
、およびＡ、Ｂ、Ｃ、Ｄは以下の値を有することを仮定
する。 Ａ＝１０００ Ｂ＝０１００ Ｃ＝００１０ Ｄ＝０００１
２を介してソース１０からレシーバ１４に送られること
、およびＡ、Ｂ、Ｃ、Ｄは以下の値を有することを仮定
する。 Ａ＝１０００ Ｂ＝０１００ Ｃ＝００１０ Ｄ＝０００１
【００２３】ＳおよびＳＥは、最初、ともにゼロまたは
「００００：０」である。表１は、ワードＡ、Ｂ、Ｃ、
Ｄが連続的に加算されるときに、期待シグネチュアＳＥ
がどのようにして計算されるのかを示すものである。表
１において「Σ１ 」はシグネチュア・レジスタ２４の
現在の内容を示し、「Σ２ 」は各データ・ワードを追
加した後の加算器２２の内容を表す。入力データ・ワー
ドに追加される追加ビットは、表１にはコロン（：）で
分離する。
「００００：０」である。表１は、ワードＡ、Ｂ、Ｃ、
Ｄが連続的に加算されるときに、期待シグネチュアＳＥ
がどのようにして計算されるのかを示すものである。表
１において「Σ１ 」はシグネチュア・レジスタ２４の
現在の内容を示し、「Σ２ 」は各データ・ワードを追
加した後の加算器２２の内容を表す。入力データ・ワー
ドに追加される追加ビットは、表１にはコロン（：）で
分離する。
【表１】
【００２４】したがって、データ・セットＡＢＣＤの期
待シグネチュアＳＥは「１１１１：０」である。合計が
加算器２２からシグネチュア・レジスタ２４に転送され
ると、ＬＳＢは廃棄され、キャリー・アウトＣＯはシグ
ネチュア・レジスタ２４のＬＳＢに記憶される。（上述
の実施例にはキャリー・アウトは１つもない。）さらに
、この結果は、ワードを送る順序と関係ない。バス１２
に関する問題により、ワードＡ、Ｂ、Ｃ、Ｄの各々のＭ
ＳＢは「１」に「なったまま」である。エラー検出シグ
ネチュアＳが得られるデータ・セット２０’は、表２に
示す通りＡ’、Ｂ’、Ｃ’およびＤ’から成る。
待シグネチュアＳＥは「１１１１：０」である。合計が
加算器２２からシグネチュア・レジスタ２４に転送され
ると、ＬＳＢは廃棄され、キャリー・アウトＣＯはシグ
ネチュア・レジスタ２４のＬＳＢに記憶される。（上述
の実施例にはキャリー・アウトは１つもない。）さらに
、この結果は、ワードを送る順序と関係ない。バス１２
に関する問題により、ワードＡ、Ｂ、Ｃ、Ｄの各々のＭ
ＳＢは「１」に「なったまま」である。エラー検出シグ
ネチュアＳが得られるデータ・セット２０’は、表２に
示す通りＡ’、Ｂ’、Ｃ’およびＤ’から成る。
【表２】
【００２５】エラー検出シグネチュアＳ’はしたがって
「０１１１：０」である。これは期待シグネチュアＳＥ
（＝１１１１：０）とは異なるので、ＳＥとＳ’を比較
することにより、受信したデータ・セットが無効である
ことを示す信号を与える。
「０１１１：０」である。これは期待シグネチュアＳＥ
（＝１１１１：０）とは異なるので、ＳＥとＳ’を比較
することにより、受信したデータ・セットが無効である
ことを示す信号を与える。
【００２６】期待シグネチュアＳＥおよびエラー検出シ
グネチュアＳおよびＳ’（ＳおよびＳ’は各々エラーの
あるおよびエラーのないエラー検出シグネチュアを表す
）を生成するための代替の方法および装置を図３に示す
。装置１６’は、Ｎビット加算器２２’およびＮ＋１ビ
ット・レジスタ２４から成る。図２の加算器２２および
図３の加算器２２’は、モジュロ２ｎ 演算（例、Ｎ＝
４ではモジュロ１６）を行う。加算器２２は、入力デー
タ・ワードを左の１ビットにシフトさせ、ＬＳＢに「１
」を加える。その結果得たＮ＋１ビットの和のＬＳＢを
その和がシグネチュア・レジスタ２４に記憶されるとき
に廃棄する。けた上げのある場合のみ、レジスタ２４の
ＬＳＢがセットされる。図３の他の方法では、別の「１
」ビットを入力データ・ワードに追加することを必要と
しない。図３の実施例では、シグネチュア・レジスタ２
４のＬＳＢは、図示のように加算器２２’へのキャリー
・イン（ＣＩ）として与えられる。すべてのＣＯは、ま
だレジスタ２４のＬＳＢに記憶されている。図２および
図３では、ＣＯビット・ロケーションはシグネチュアの
一部であると考えることができる。以下に図３の具体例
を示す。
グネチュアＳおよびＳ’（ＳおよびＳ’は各々エラーの
あるおよびエラーのないエラー検出シグネチュアを表す
）を生成するための代替の方法および装置を図３に示す
。装置１６’は、Ｎビット加算器２２’およびＮ＋１ビ
ット・レジスタ２４から成る。図２の加算器２２および
図３の加算器２２’は、モジュロ２ｎ 演算（例、Ｎ＝
４ではモジュロ１６）を行う。加算器２２は、入力デー
タ・ワードを左の１ビットにシフトさせ、ＬＳＢに「１
」を加える。その結果得たＮ＋１ビットの和のＬＳＢを
その和がシグネチュア・レジスタ２４に記憶されるとき
に廃棄する。けた上げのある場合のみ、レジスタ２４の
ＬＳＢがセットされる。図３の他の方法では、別の「１
」ビットを入力データ・ワードに追加することを必要と
しない。図３の実施例では、シグネチュア・レジスタ２
４のＬＳＢは、図示のように加算器２２’へのキャリー
・イン（ＣＩ）として与えられる。すべてのＣＯは、ま
だレジスタ２４のＬＳＢに記憶されている。図２および
図３では、ＣＯビット・ロケーションはシグネチュアの
一部であると考えることができる。以下に図３の具体例
を示す。
【００２７】前述と同様、Ａ＝１０００、Ｂ＝０１００
、Ｃ＝００１０およびＤ＝０００１と仮定する。表３は
、ワードＡ、Ｂ、Ｃ、Ｄがバス１２を介して送られると
きに、図３の装置が期待シグネチュアＳＥをどのように
して計算するかを示す。
、Ｃ＝００１０およびＤ＝０００１と仮定する。表３は
、ワードＡ、Ｂ、Ｃ、Ｄがバス１２を介して送られると
きに、図３の装置が期待シグネチュアＳＥをどのように
して計算するかを示す。
【表３】
【００２８】期待シグネチュアＳＥは再び「１１１１：
０」である。バス１２のＭＳＢが１になったままである
ことを再度仮定すると、表４は、ワードＡ’、Ｂ’、Ｃ
’、Ｄ’が各々レシーバ１４に受信されるときの、加算
器２２’（Σ２ ）およびシグネチュア・レジスタ２４
（Σ１ ）の内容を示す。
０」である。バス１２のＭＳＢが１になったままである
ことを再度仮定すると、表４は、ワードＡ’、Ｂ’、Ｃ
’、Ｄ’が各々レシーバ１４に受信されるときの、加算
器２２’（Σ２ ）およびシグネチュア・レジスタ２４
（Σ１ ）の内容を示す。
【表４】
エラー検出シグネチュアＳ’はしたがって０１１１：１
である。これをＳＥ＝１１１１：０と比較することによ
りエラーを示すことができる。
である。これをＳＥ＝１１１１：０と比較することによ
りエラーを示すことができる。
【００２９】本願明細書に述べた２つの方法と、従来の
チェックサムおよびＣＲＣ方法とを比較すると、本発明
はチェックサム方法の簡易性を保ちながら、該方法より
もエラー検出の確率が高い。さらに、本願発明は、さら
に複雑なＣＲＣ方法では得られない順序独立（ｏｒｄｅ
ｒ−ｉｎｄｅｐｅｎｄｅｎｔ）シグネチュアを得ること
ができる。
チェックサムおよびＣＲＣ方法とを比較すると、本発明
はチェックサム方法の簡易性を保ちながら、該方法より
もエラー検出の確率が高い。さらに、本願発明は、さら
に複雑なＣＲＣ方法では得られない順序独立（ｏｒｄｅ
ｒ−ｉｎｄｅｐｅｎｄｅｎｔ）シグネチュアを得ること
ができる。
【００３０】
【発明の効果】以上説明したように、本発明は２つのロ
ケーション間のデータ転送においてデータ（ワード）の
順序に依存することなく、また簡易な方法で高精度にエ
ラー発生を検出することができる。
ケーション間のデータ転送においてデータ（ワード）の
順序に依存することなく、また簡易な方法で高精度にエ
ラー発生を検出することができる。
【図１】本発明の一実施例に用いられるデータ転送シス
テムのブロック図。
テムのブロック図。
【図２】本発明に用いられるエラー検出シグネチュア発
生装置のブロック図。
生装置のブロック図。
【図３】本発明に用いられる他のエラー検出シグネチュ
ア発生装置のブロック図。
ア発生装置のブロック図。
１０：ソース
１４：レシーバ
１６：シグネチュア発生装置
２２、２２’：加算器
２４：シグネチュア・レジスタ
Claims (5)
- 【請求項１】通信媒体上でソース端からレシーバにＮビ
ット・データ・ワードのセットを転送するシステムにお
いて、（イ）第１のＮ＋１ビット・レジスタのＮビット
位置にデータ・ワードを累積することによりソース端か
ら受信したデータ・ワードを２Ｎ モジュロ演算で総和
させ、同時に前記第１のＮ＋１ビット・レジスタの指定
Ｎ＋１ビット位置にキャリー・アウト（ＣＯ）を記憶さ
せ、前記第１のＮ＋１ビット・レジスタの内容は期待シ
グネチュア（ＳＥ）を定義し、（ロ）第２のＮ＋１ビッ
ト・レジスタのＮビット位置にデータ・ワードを累積す
ることによりソース端から受信したデータ・ワードを２
Ｎ モジュロ演算で総和させ、同時に前記第２のＮ＋１
ビット・レジスタの指定Ｎ＋１ビット位置にＣＯを記憶
させ、前記第２のＮ＋１ビット・レジスタの内容はエラ
ー検出シグネチュア（Ｓ）を定義し、（ハ）前記ＳとＳ
Ｅを比較し、これらに相違があるかどうか検出し、該相
違が検出されるとデータ転送にエラーが生じたことを指
示することより成り、被検出受信データの相違は前記ソ
ース端から転送されるデータ・ワードの順序と独立して
いることを特徴とするデータ転送エラー検出方法。 - 【請求項２】請求項１のデータ転送エラー検出方法のス
テップ（イ）はさらにソース端部から転送されるＮビッ
トのデータ・ワードに１の値を有するビットを追加する
ことを含むデータ転送エラー検出方法。 - 【請求項３】請求項１のデータ転送エラー検出方法のス
テップ（ロ）はさらにソース端部から転送されるＮビッ
トのデータ・ワードに１の値を有するビットを追加する
ことを含むデータ転送エラー検出方法。 - 【請求項４】通信媒体上でＮビットのデータ・ワードを
ソースからレシーバに転送するシステムにおいて、転送
されるデータ・ワードを２Ｎ モジュロ演算を用いて加
算する加算器と、前記加算器の出力ポートと連結し、デ
ータ・ワードのＮビットの総和とキャリー・アウトを記
憶するＮ＋１ビット・レジスタから成るデータ転送エラ
ー検出器。 - 【請求項５】請求項第４項記載のデータ転送エラー検出
器において、前記加算器は、Ｎ＋１ビット・レジスタの
出力ポートと連結し、第１のＮビット・データ・ワード
を受信する第１の入力ポートと、前記Ｎ＋１ビット・レ
ジスタの出力ポートから第２のＮ＋１ビット・データ・
ワードを受信する第２の入力ポートと、前記Ｎ＋１ビッ
ト・レジスタの第１の入力ポートに連結し、前記Ｎ＋１
ビット・レジスタにＮビットの和を供給する出力ポート
と、前記Ｎ＋１ビット・レジスタの第２の入力ポートに
連結し、加算器によって求められたキャリー・アウトを
供給するキャリー・アウト・ポートから構成されること
を特徴とするデータ転送エラー検出器。
Applications Claiming Priority (2)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| US480417 | 1990-02-14 | ||
| US07/480,417 US5121397A (en) | 1990-02-14 | 1990-02-14 | Method and apparatus for producing order independent signatures for error detection |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| JPH04215332A true JPH04215332A (ja) | 1992-08-06 |
Family
ID=23907882
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP9144222A Pending JPH04215332A (ja) | 1990-02-14 | 1991-02-15 | データ転送エラー検出装置及びその方法 |
Country Status (4)
| Country | Link |
|---|---|
| US (1) | US5121397A (ja) |
| EP (1) | EP0443753B1 (ja) |
| JP (1) | JPH04215332A (ja) |
| DE (1) | DE69120552T2 (ja) |
Families Citing this family (8)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US5212696A (en) * | 1990-02-14 | 1993-05-18 | Hewlett-Packard Company | Method and apparatus for producing order independent signatures for error detection |
| US5454000A (en) * | 1992-07-13 | 1995-09-26 | International Business Machines Corporation | Method and system for authenticating files |
| EP0675447B1 (en) * | 1994-03-29 | 2001-07-11 | Matsushita Electric Industrial Co., Ltd. | Data transfer device and method for reducing electrical transitions |
| US5691997A (en) * | 1995-09-28 | 1997-11-25 | Cisco Systems, Inc. | Encoder for use in asynchronous transfer mode systems |
| US6038694A (en) * | 1997-03-24 | 2000-03-14 | Cisco Systems, Inc. | Encoder for producing a checksum associated with changes to a frame in asynchronous transfer mode systems |
| RU2231823C2 (ru) * | 2002-08-20 | 2004-06-27 | Российский государственный открытый технический университет путей сообщения | Устройство для контроля позиционных сумматоров по модулю |
| US7010469B2 (en) * | 2003-09-30 | 2006-03-07 | International Business Machines Corporation | Method of computing partial CRCs |
| TW200712863A (en) * | 2005-09-23 | 2007-04-01 | Via Tech Inc | Method of detecting data error code |
Family Cites Families (5)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| MX4130E (es) * | 1977-05-20 | 1982-01-04 | Amdahl Corp | Mejoras en sistema de procesamiento de datos y escrutinio de informacion utilizando sumas de comprobacion |
| US4503536A (en) * | 1982-09-13 | 1985-03-05 | General Dynamics | Digital circuit unit testing system utilizing signature analysis |
| IT1168840B (it) * | 1983-09-15 | 1987-05-20 | Cselt Centro Studi Lab Telecom | Decodificatore di codice binario ciclico perfetto |
| US4712215A (en) * | 1985-12-02 | 1987-12-08 | Advanced Micro Devices, Inc. | CRC calculation machine for separate calculation of checkbits for the header packet and data packet |
| US4849978A (en) * | 1987-07-02 | 1989-07-18 | International Business Machines Corporation | Memory unit backup using checksum |
-
1990
- 1990-02-14 US US07/480,417 patent/US5121397A/en not_active Expired - Fee Related
-
1991
- 1991-02-07 EP EP91301017A patent/EP0443753B1/en not_active Expired - Lifetime
- 1991-02-07 DE DE69120552T patent/DE69120552T2/de not_active Expired - Fee Related
- 1991-02-15 JP JP9144222A patent/JPH04215332A/ja active Pending
Also Published As
| Publication number | Publication date |
|---|---|
| EP0443753A1 (en) | 1991-08-28 |
| US5121397A (en) | 1992-06-09 |
| DE69120552D1 (de) | 1996-08-08 |
| EP0443753B1 (en) | 1996-07-03 |
| DE69120552T2 (de) | 1996-12-12 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US8914698B2 (en) | Cyclic redundancy check circuit and communication system having the same for multi-channel communication | |
| EP4216444B1 (en) | Pipelined forward error correction for vector signaling code channel | |
| EP1458105B1 (en) | Method and device for decoding of Reed-Solomon codes | |
| JPH04215332A (ja) | データ転送エラー検出装置及びその方法 | |
| US4914660A (en) | Method and apparatus for decoding error correcting code | |
| US7100103B2 (en) | Efficient method for fast decoding of BCH binary codes | |
| JP3768613B2 (ja) | ログの近似値の計算回路 | |
| JP2881773B2 (ja) | 誤り訂正装置 | |
| US5212696A (en) | Method and apparatus for producing order independent signatures for error detection | |
| JPH0629956A (ja) | Ｓｄｈ信号における誤り訂正符号挿入処理方式及び光伝送装置 | |
| JP3223513B2 (ja) | 誤り訂正復号装置 | |
| JPH06276106A (ja) | 誤り訂正復号装置 | |
| JPS61288524A (ja) | Ｂｃｈ符号復号方式 | |
| US5304994A (en) | Minimal delay leading one detector with result bias control | |
| US6101523A (en) | Method and apparatus for controlling calculation error | |
| KR100234703B1 (ko) | 데이타 오류체크 방법 | |
| JP3099890B2 (ja) | Ｂｃｈ符号の誤り訂正装置 | |
| JP2823158B2 (ja) | 誤り訂正装置 | |
| JP2001251196A (ja) | リードソロモン復号方法及びリードソロモン復号装置 | |
| JP3253381B2 (ja) | 誤り訂正回路 | |
| JP2780503B2 (ja) | パリティチェック検出回路 | |
| JPH0613915A (ja) | 誤り検出方法 | |
| JPS61135233A (ja) | Ｂｃｈ符号復号方式 | |
| KR20010057408A (ko) | 병렬 순회 용장 코드 계산장치 | |
| JPH04291627A (ja) | 演算装置 |