JPH0690672B2 - データ処理装置におけるデータを記憶し、回復する方法及び装置 - Google Patents

データ処理装置におけるデータを記憶し、回復する方法及び装置

Info

Publication number
JPH0690672B2
JPH0690672B2 JP59206453A JP20645384A JPH0690672B2 JP H0690672 B2 JPH0690672 B2 JP H0690672B2 JP 59206453 A JP59206453 A JP 59206453A JP 20645384 A JP20645384 A JP 20645384A JP H0690672 B2 JPH0690672 B2 JP H0690672B2
Authority
JP
Japan
Prior art keywords
data
byte
checksum
result value
exclusive
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.)
Expired - Lifetime
Application number
JP59206453A
Other languages
English (en)
Other versions
JPS60124735A (ja
Inventor
リチヤード・エヌ・ウーレイ
ニール・グローバー
リチヤード・ウイリアムズ
Original Assignee
アプル・コンピュータ・インコーポレーテッド
Priority date (The priority date 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 date listed.)
Filing date
Publication date
Application filed by アプル・コンピュータ・インコーポレーテッド filed Critical アプル・コンピュータ・インコーポレーテッド
Publication of JPS60124735A publication Critical patent/JPS60124735A/ja
Publication of JPH0690672B2 publication Critical patent/JPH0690672B2/ja
Anticipated expiration legal-status Critical
Expired - Lifetime legal-status Critical Current

Links

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
    • H03M13/03—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words
    • H03M13/05—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words using block codes, i.e. a predetermined number of check bits joined to a predetermined number of information bits
    • H03M13/09—Error detection only, e.g. using cyclic redundancy check [CRC] codes or single parity bit
    • G—PHYSICS
    • G11—INFORMATION STORAGE
    • G11B—INFORMATION STORAGE BASED ON RELATIVE MOVEMENT BETWEEN RECORD CARRIER AND TRANSDUCER
    • G11B20/00—Signal processing not specific to the method of recording or reproducing; Circuits therefor
    • G11B20/10—Digital recording or reproducing
    • G11B20/18—Error detection or correction; Testing, e.g. of drop-outs
    • G11B20/1866—Error detection or correction; Testing, e.g. of drop-outs by interleaving
    • 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
    • H03M13/27—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 using interleaving techniques

Landscapes

  • Engineering & Computer Science (AREA)
  • Physics & Mathematics (AREA)
  • Probability & Statistics with Applications (AREA)
  • Theoretical Computer Science (AREA)
  • Signal Processing (AREA)
  • Detection And Correction Of Errors (AREA)
  • Error Detection And Correction (AREA)

Description

【発明の詳細な説明】 〔発明の技術分野〕 本発明はデータ処理装置におけるデータのエラー検出に
係わり、更に詳細にはエラーを検出し易くするための方
法及び装置に関する。
〔従来技術〕
最近のデータ処理装置は複雑なため、記憶され、検索さ
れかつその他マニピユレートされたデータビツトにおけ
るエラーを検出するには、何らかの装置を使用しなけれ
ばならなかつた。たとえば、テープまたはデイスクのマ
スメデイア記憶装置の磁気書込み一読出しヘツドに異物
が付着したりすることにより、データ処理装置に機械的
ないし電気的変化が起こり、データにエラーが生じるこ
とがある。また、宇宙線や記憶装置のハウジングにおけ
る放射性不純物により引き起される“ソフト”エラーの
他、記憶媒体の自然摩耗やデータ処理装置用の電源電圧
の変動により、データビツトにエラーを生じたり、デー
タビツトを変化させたりすることもある。
これまで、記憶された、または、その他マニピユレート
されたデータに生じたエラーを検出するために、様々な
方法が開発されてきた。そのうちの一般的なエラー検出
装置は、簡単なチエツクサムコードを使用している。代
表的には、データは複数のバイトから成るレコードによ
り構成されており、各バイトは複数（代表的には８個）
のビツトから成つている。この簡単なチエツクサム方法
を用いた装置は、レコード内の連続した各バイト間で排
他OR操作を行なうものである。すなわち第１図に示すよ
うに、バイトA1を構成する８ビツトは、A2を構成する８
ビツトと排他ORがとられる。A1とA2間の操作により得ら
れたバイナリ量は、同様に、バイトA3を構成するビツト
と排他ORがとられ、以下同様に続けられる。チエツクサ
ムは、これら繰返し排他OR操作から得られた正味結果の
バイナリ量として規定される。この結果生じたチエツク
サム量は、第１図に示すようにAiとしてレコードの最後
に挿入される。
多くのデータ処理装置では、データは、磁気デイスクま
たはテープのような磁気記録媒体上に書き込まれる。一
方、チエツクサム・エラー検出方法を使用した装置で
は、バイトA1を先ず書き込み、続いてその後のバイトを
書き込み、最後に、チエツクサム結果を構成する１つま
たは複数のバイトをレコードの最後に配置するように、
全レコードを構成する多くのバイトの形式のデータを磁
気媒体上に順次書き込む。磁気媒体からデータを検索す
る場合、チエツクサムの値を再計算しながら、データ処
理装置は全レコードの内容を順次読み出す。全レコード
が記録媒体から読み出されると、再計算されたチエツク
サム値は、レコードの一部として前に記録されたチエツ
クサムと比較される。そして、２つのチエツクサムが等
しくない場合には、データにエラーがあると判定され
る。
しかし、この簡単なチエツクサム・エラー検出方法を使
用した装置は、思つたほど有効ではなかつた。たとえ
ば、この簡単なチエツクサム方法は、レコードにわたつ
て任意に存在する短いバーストエラーに対して固有のパ
ターン感度を有している。従つて、レコード内のシーケ
ンシヤルバイト間で排他OR操作を行なうと、エラーが互
いに相殺され、エラーを検出できないという可能性があ
つた。たとえば、レコードの特定バイト内のビツト＃２
のビツト状態が、機械的や電気的の悪影響により変化し
（例えば、１が０ビツト状態にシフトし）、かつ他のバ
イトのビツト＃２が同様に変化する（０ビツト状態がた
またま１ビツト状態に変化する）と、バイト内エラーは
排他OR操作の際に相殺されてしまう。たとえば、２つの
ランダムビツトにエラーがある場合、エラーの検出ミス
の確率は、ほぼ1/8となる。
この簡単なチエツクサムのエラー検出率を改善する１つ
の方法に、“インタリービング”を付加する方法があ
る。たとえば、３バイトのチエツクサムは、１つのレコ
ードに対して３つの別個の結果たるチエツクサム値を発
生する。第２図に示すように、第１のチエツクサム値
は、シーケンシヤル・チエツクサム・インターリーブド
・バイトを表わすバイトA1,A2,A3等に関して決定され
る。同様に、第２チエツクサムは、バイトB1,B2,B3等に
関して計算され、第３チエツクサムは、バイトC1,C2,C3
等に関して計算される。しかし、インターリーブするこ
とにより、長いランダムエラー・バーストに対する検出
ミスの可能性を著しく低下させはするが、散在するエラ
ー・バーストに対する検出ミスの可能性は依然高いまま
である。
従つて、記憶されかつマニピユレートされたデータにお
けるエラーを検出する能力を高める装置が必要とされて
いる。
〔発明の概要〕
本発明は、データレコードにわたりエラーをランダム化
しかつ伝播することにより、エラーの検出能力を改善す
る装置及び方法を提供する。エラーのこのランダム化及
び伝播は、検出能力を著しく増すものである。
本発明はデータ処理装置における改善されたエラー検出
方法及び装置に関する。本発明の技術は、データレコー
ド（各レコードは複数のデータビツトから成る）におけ
るエラーを検出する能力を高めるもので、エラーがある
場合には、レコード内のその後のビツトを変化させかつ
レコードにわたりエラーを伝播し、さらにランダム化し
てその見かけの大きさを拡大するランダム化作用をエラ
ーに対して行なう。このようなエラーのランダム化及び
伝播は、レコード内のランダムエラーに対する検出ミス
の可能性を著しく減少し、従来のようなエラーの検出能
力でのパターン感度はもはやない。この伝播及びランダ
ム化作用の両方を使用することにより、エラーを含むデ
ータは著しく変化されるので、チエツクサム技術を用い
た検出能力は一層高くなる。
〔実施例〕
序 説 以下に述べる詳細な記述は、大部分、コンピユータメモ
リのデータビツトに対する操作のアルゴリズム及び記号
表示に基づいて行なわれている。しかし、これらアルゴ
リズム記述及び表示は、本発明の内容を当業者に最も有
効に伝えるための単なる手段であるに過ぎない。
アルゴリズムは、ここでは、目標結果に導く過程の自己
矛盾のないシーケンスのことを言う。これら過程は、物
理的量の物理的マニピユレーシヨンを要する過程であ
る。通常、必ずしも必要ではないが、これら量は、記
憶，伝送，比較，結合等の操作を行なうことができる電
気的または磁気的信号の形になつている。これは、ビツ
ト，値，エレメント，記号，キヤラクタ，語，番号等と
してこれら信号を示す際、主に慣例上の理由で、便利な
ことが多い。しかし、これら及び同様の語の全ては、適
当な物理量に関連しており、かつこれらの量に与えられ
る単なる便宜上の呼び名にすぎないということに注目す
べきである。
さらに、実行されるマニピユレーシヨンは、操作者が頭
の中でやる操作に一般に関連したたとえば加算または比
較のような語で示されることがある。操作者のこのよう
な能力は、本発明の一部を成している、ここで示された
操作のいずれにおいても、必要なく、また、要求されて
もいない。なお、この操作とは、マシン操作のことであ
る。本発明の操作を実行する有効なマシンは、汎用デイ
ジタルコンピユータや他の同様の装置を含んでいる。い
ずれも場合において、コンピユータを操作する際の順序
操作とそれ自身の計算方法との間の差違に注目すべきで
ある。
本発明は、電気的または他（たとえば、機械的，化学
的）の物理的信号を処理し、目標とする他の物理的信号
を発生するのにコンピユータを操作する順序過程に関す
る。
また、本発明は、これらの操作を実行する装置に関して
いる。この装置は、要求された目的のため特に構成され
るかまたは、コンピユータに記憶されるコンピユータプ
ログラムにより選択的に稼動または再構成される汎用コ
ンピユータから構成してもよい。またここにおけるアル
ゴリズムは、特定のコンピユータや他の装置に特に関係
しているわけではない。すなわち、本発明においては、
様々の汎用マシンを使用することができ、また、本発明
は、必要とされる順序過程を実行するさらに専用化した
装置を構成するのに一層便利である。なお、これら様々
のマシンの構成については、以下に説明する。
本発明について、いくつかの部分にそれを分けて説明す
る。先ず、第１には、データを記憶し、検索し、マニピ
ユレートする汎用システムについて述べる。その後の部
分では、データ処理装置に、改良されたエラー検出能力
を与える装置及び方法について述べる。
さらに、本発明の理解を助けるため、アルゴリズム規
約，特定数のビツト，バイナリ操作等、多数の詳細な記
載が以下の説明において示されているが、本発明は、こ
れら記載に限定されるものではないことは当業者には明
白であろう。また、周知の回路や構成については、本発
明を不明瞭なものとしないよう、詳細な説明は省略す
る。
システムの概略構成 第３図は、データを書込み、記憶し、かつ、マニピユレ
ートする代表的なコンピユータシステムを示している。
ここで示されているコンピユータ20は、３つの主な構成
部分から成つている。第１の部分は、入力／出力（I/
O）回路22で、これは、コンピユータ20の他の部分と、
適当に構成された形式で情報を伝達するのに使用され
る。コンピユータ20の他の構成部分は、中央処理装置
（CPU）24と、メモリ26から成る。これら２つの構成部
分は、大体のコンピユータにおいて使用されている。実
際、コンピユータ20内に含まれているいくつかの装置
は、データプロセツサのこの幅広いカテゴリーを表わし
ている。たとえば、コンピユータ20の役割を満たす適当
なデータプロセツサとしては、カリフオルニア州のアプ
ル・コンピユータ・インコーポレーテツド社製のマシン
がある。むろん、同様の能力を有する他のコンピユータ
を、以下に示したいくつかの機能を実行するのに使用す
ることもできる。
第３図に示した入力装置30は、キーボードとして示され
ている。しかし、この入力装置は、実際には、カードリ
ーダーや、磁気または紙テープリーダーや、他の周知の
入力装置（むろん、他のコンピユータを含む）であつて
もよい。I/O回路22に接続したマスメモリ装置32は、コ
ンピユータ20に対してさらに記憶能力を与えている。マ
スメモリは、別のプログラム等を含み、かつ、磁気また
は紙テープリーダや、他の周知装置のいずれでもよい。
また、マスメモリ32に含まれているデータは、メモリ26
の一部としてコンピユータ内に標準的な形で内蔵されて
いる。
さらに、本発明により操作されるデータをデイスプレイ
するには、デイスプレイモニタ34を使用している。この
デイスプレイモニタは、様々な周知のCRTデイスプレイ
のいずれでもよい。
コンピユータ20の動作において、メモリ26及びマスメモ
リ32に記憶されかつ検索されたデータにエラーがあると
する。記憶された、または、操作（マニピユレート）さ
れたデータにおけるエラーを検出し損なうと、偽りのコ
ンピユータレスポンスを発生してしまう。後述するよう
に、本発明は、記憶された、または、操作されたデータ
におけるエラーの検出能力を、増加する方法及び装置を
提供するもので、これにより、コンピユータ動作の信頼
性を改善する。
エラーの伝播 前述したように、レコードにおける長いランダムエラー
・バーストの場合には、インタリーブすることにより検
出ミスの可能性をかなり減少することができる。しか
し、レコードにわたつてランダムに散在するエラー・バ
ーストに対しては、エラーの検出ミスの可能性は、いぜ
ん高いままである。従つて、本発明は、レコードにわた
りエラーを伝播し、それにより検出の可能性を増すよう
にしている。
第１表は、本発明によるエラー伝播方法を示している。
レコードにおけるシーケンシヤル・インタリーブド・バ
イトから成るデータA,B,C,Dの各バイトが、コンピユー
タシステムにおいて記憶またはその他の操作を受ける。
本発明は、磁気的記憶媒体等から成るたとえばメモリ26
またはマスメモリ32に、第１バイトＡを直接的に記憶す
る。第１表（ａ）に示すように、次のバイトＢの内容
は、前のバイトＡの内容と排他ORをとられ、これらバイ
トＢ及びＡ間のこの排他OR操作から得たバイナリ量が記
憶される。同様に、前のバイトＢの内容と、上記得られ
たバイナリ量もまた記憶される。従つて、記憶装置にデ
ータを記憶する従来のエンコード方法とは異なり、本発
明は、レコードのシーケンシヤル（またはインタリーブ
ド）バイト間の一連の排他OR操作による結果を記憶す
る。
第１表（ｂ）は、第１表（ａ）に従つて記憶されたデー
タの回復を示している。表に示すように、データは、別
の排他OR操作を使用することにより、第１表（ａ）に関
して述べた方法に従つて記憶したバイナリ量からデコー
ドされる。また、検索されるバイナリ量は、すぐ前の
（またはインタリーブド）バイトから得られた、デコー
ド化結果と排他ORされる。たとえば、バイトＡの、マス
メモリ32またはメモリ26からの検索は、バイトＡが記憶
装置内で変更なく検索されるならば、バイトＡの内容を
表わすバイナリ量を単に生じる。一方、記憶装置32等か
らの、連続的に記憶されたバイナリ量（ＢＡ）の検索
は、前にデコードされたバイトＡと排他ORされる。第１
表（ａ）の記憶されたバイナリ量と、前に回復したデー
タ（たとえば、バイトＡ）との間の排他OR操作は、バイ
トＢを有効にデコードしかつ回復する。同様に、回復し
たバイトＢとエンコード化した量（ＣＢ）との間の排
他OR操作は、バイトＣの回復を行なう。このように、第
１表に示した方法によれば、簡単な一連の排他OR操作を
行なうことにより、データをエンコードしかつ記憶装置
に記憶し、その後デコードすることができる。
第２表は、データ・レコードにおけるランダムエラーの
伝播を示している。本発明によれば、第１レコードバイ
トＡは、コンピユータ20のマスメモリ32またはメモリ26
のような記憶装置に記憶される。それに続く（連続的
な、またはインタリーブド）バイトＢは、バイトＡの内
容と排他ORされ、その結果生じた量は上記記憶装置に記
憶される。同様に、その後のバイトC,D他は、第１表
（ａ）の方法に従つて、前のデータバイトと排他ORされ
る。
レコードのバイトＡにエラー“e"が存在していると仮定
する。このエラーは、リードバツクまたは最初の書込み
サイクルにおいて、または、前述したような可能性のあ
る多くの原因のいずれかの結果として生じたものであ
る。従つて、レコードの第１バイトを検索すると、バイ
トＡｅを表わす量が生じる。本発明の方法を用いて、
この量（Ａｅ）は、続いて記憶されたバイト量（Ｂ
Ａ）と排他ORされる。この排他OR操作から得た正味結果
は、量（Ｂｅ）である。このように、エラーｅはその
後のバイトＢに伝播され、また第２表からわかるよう
に、エラーｅはレコードの各バイトにわたつて同様に伝
播される。動作において、簡単なチエツクサム・プロセ
デユアを含むデータ処理システムは、第２表に示した検
索データに基づいて再計算されたチエツクサム値を、第
１表（ａ）のプロセデユアにより最初に記憶されたデー
タに関する、前に記憶されたチエツクサム量と比較す
る。この本発明の方法に従つたエラーの伝播によつて、
２つのチエツクサムが一致しないことから、エラーがあ
ることがわかる。
伝播およびランダム化 第３表は、データレコードにおけるエラーの伝播及びラ
ンダム化の方法を示している。前にも使用したA,B,C,D
は、レコードにおける連続的（シーケンシヤルまたはイ
ンタリーブド）バイトを表わしている。プライム符
号「′」はある作用、すなわちランダム化することを表
わしている。また、二重のプライム符号「″」は２回こ
の作用を行なうことを表わし、以下同様である。前に述
べたように、本発明では、使用される特定のメモリ装置
に、第１バイトＡを直接的に記憶している。第３表
（ａ）に示すように、次のシーケンシヤルバイトＢは、
ランダム化作用が行なわれた前のバイトＡの内容と排他
ORされる。次に、バイトＢ及びＡ′間でのこの排他OR操
作から得たバイナリ量は、記憶装置に記憶される。同様
に、シーケンシヤルバイトＣの内容は、この作用が行な
われた前のバイトＢの内容と排他ORされ、その結果生じ
たバイナリ量も記憶される。なお、特定のランダム化作
用は、周知のいろいろな種類のランダム化アルゴリズム
から形成できるが、本発明では、リニアランダム化作用
（linear randomizing function）を使用している。
第３表（ｂ）は、データレコードにランダム的に位置す
るエラーの作用を示している。たとえば、レコードのバ
イトＡに、エラー“e"が存在すると仮定する。第３表
（ｂ）に示すように、レコードの第１バイトの検索によ
り、バイトＡｅを表わす量が生ずる。本発明を使用し
て、量Ａｅにランダム化作用を行ない、量（Ａ
ｅ）′を生じさせる。この量（Ａｅ）′は、その後記
憶された量Ｂ＋Ａ′と排他ORされる。この排他OR作用か
ら得た正味結果は量Ｂ＋ｅ′であり、ここでｅ′はＡ′
（Ａｅ）′に等しい。このように、エラーｅはその
後のバイトＢに伝播され、かつ選択されたランダム化作
用に従つてランダム化される。同様に、バイナリ量Ｂ
ｅ′にランダム化作用を行ない、それにより（Ｂ
ｅ′）′を得、続いてこれは前に記憶された量ＣＢ′
と排他ORされる。これにより検索されたバイナリ量Ｃ
ｅ″が得られる。このｅ″はＢ′（Ｂｅ′）′に等
しい。このように、ランダム化作用はエラーｅに対して
２回行なわれ、従つて、エラーがレコードを伝播させら
れる時、前にランダム化されたエラーをランダム化す
る。このプロセデユアはデータがレコードから順次読出
される時、繰返され、これにより、レコード全体にわた
りエラーをランダム化しかつ伝播し、さらにチエツクサ
ム技術を使用して検出の可能性を著しく増加している。
第4a図，第4b図および第４表は、本発明の他の実施例を
示している。本発明は、データレコードにおけるシーケ
ンシヤルまたはインタリーブド・バイトに対するランダ
ム化及び伝播方法を使用して述べられているが、チエツ
クサム量自体に直接的に本発明の技術を使用することに
より、検出の可能性が高くなることが分つた。第4a図に
示すように、データレコードは、バイトA,B,C,D等を含
んでいる。チエツクサム量C1,C2,C3は、データレコード
の終りに位置している。図示のように、本実施例は、３
バイト・インタリーブド・チエツクサム・システムを使
用している。ここで、バイトA,D,G等は、チエツクサムC
1のシーケンシヤル・インタリーブド・バイトから成つ
ている。同様に、シーケンシヤル・インタリーブド・バ
イトB,E,H等は、チエツクサムC2のバイトから成つてい
る。終りに、バイトC,F,I等は、チエツクサムC3のシー
ケンシヤルインタリーブドバイトから成つている。な
お、“c"は前の操作からのキヤリーを表わしている。
第4b図に示すように、この実施例のランダム化作用は、
チエツクサムC3の内容が左へ１ビツト（すなわち、最下
位ビツトから最上位ビツトへ向けて）シフトされ、かつ
最上位ビツトが最下位ビツト位置に循環する“循環（ro
tate）”から成つている。なお、ランダム化するのに
“循環”を使用することにより、種々のコンピユータシ
ステムをリアルタイムにすることができる。
第４表（ａ）に示すように、本発明によるデータエンコ
ードは、最初にチェックサムC3の循環（プロセデュアの
開始時、予めデータが記憶されていないので、単にバイ
ナリゼロの循環となる）を行う。続いて、チェックサム
C1はそれにバイナリＡを加えた値に等しくなるように設
定される（キャリーｃを加える）。最初C1はゼロである
ので、新しいC1はバイトＡの内容に単に等しい。第４表
に示すように、このバイトＡが循環されたC3と排他ORさ
れ、その結果が適当な記憶装置に記憶される。C3が最初
はゼロに設定されているので、単にバイトＡの内容がそ
のままコンピュータ20のマスメモリ32またはメモリ26に
記憶される。なお、キャリーｃはＡともとのC1とのMSB
を示すもので、キャリーが１であると双方が１、０であ
ると双方が０でる。以下同様にチェックサム量C2は、C2
の前の内容プラス、バイトＢからなるバイナリ量及びキ
ャリーに等しくなるように設定される。次に、レコード
のバイトＢはチェックサムC1（循環されない）の内容と
排他ORされ、その結果生じた量は適当な記憶装置に記憶
される。さらに、チエツクサムC3は、C3の前の内容プラ
ス、バイトＣの内容プラスキヤリーに等しくなるよう設
定される。バイトＣの内容は、チエツクサムC2の内容と
排他ORされ、続いてこの量は記憶される。第１の３バイ
トＡC3,BC1,CC2が、前に述べたように一旦記憶装
置に記憶されると、チエツクサムC3の内容は、もう一度
第4a図に示すように１ビツトシフトにより循環される。
次に、チエツクサムC1の内容は、レコードのバイトＤの
内容プラスキヤリーに加算される。バイトＤの内容はチ
エツクサムC3の内容と排他ORされ、この結果生じた量は
記憶装置に記憶される。表に示すように、チエツクサム
C2の内容は、チエツクサムC2の内容を再形成するため、
レコードのバイトＥの内容プラスキヤリーに加算され
る。同様に、第4a図に示したレコードから成るその後の
バイトは、適当な記憶装置に記憶され、従つて、チエツ
クサムC1,C2,C3は更新される。
第４表（ｂ）は、第4a図，第4b図および第４表（ａ）に
示したエンコード方法に従つたデータ回復を示してい
る。検索する前に、コンピユータ20のコンピユータメモ
リ26内でチエツクサムC1,C2,C3を規定し、かつこれらを
ゼロに等しくなるように設定する。チエツクサム量C1,C
2,C3は、第4a図に示すようにレコードの終りに記憶され
る。表に示すように、検索された量ＡC3はチエツクサ
ムC3の内容（ゼロに等しい）と排他ORされ、これによ
り、ＡC3がエラーを含まないならば、バイトＡの内容
を真に検索することになる。バイトＡが一旦検索される
と、C1は、C1の内容にバイトＡプラスキヤリー（本実施
例にはない）を加えることにより更新される。同様に、
前のバイナリ量ＢC1は、C1の新たに更新された値と排
他ORされ、これによりバイトＢがデコード及び検索され
る。続いて、バイトＢの内容（プラスキヤリー）を加え
ることにより、C2は更新される。バイトＣは、前に記憶
された量ＣC2をC2の新しく更新された値と排他ORする
ことにより検索される。次に、バイトＣの値を加えるこ
とによりC3は更新され、かつ前述したように循環を行な
う。このように、レコードを形成するシーケンシヤルバ
イトはデコードされかつ検索される。
コーデイングの詳細 前述した種々のプロセデユアを実行するための特定のプ
ログラミング言語は、ここに示されていない。これは、
全ての言語が共通に使用できるわけではないからで、特
定のコンピユータの各ユーザは、当面の目的に最も適し
た言語を選択すればよい。実際、マシン実行可能オブジ
エクトコードを供給するアセンブリ言語で本発明を実施
するのは有効であることが判明している。
本発明を実施するのに使用されるコンピユータ及びモニ
タ装置は、多くの様々の素子から成つているので、プロ
グラムはあまり詳しくはリストしていないが、上述した
または図示した作用及び他のプロセデユアは、当業者が
本発明を実施するには十分開示されている。
このように、本発明は、デイジタルコンピユータに対し
て最も有効な、かつ改良されたエラー検出を行なう方法
及び装置を提供する。また、本発明のデータレコードに
わたつてエラーをランダム化しかつ伝播することは、エ
ラーの検出ミスの可能性を著しく減少し、かつ、これに
よりデータ処理システムの信頼性を増すことができる。
【図面の簡単な説明】
第１図は、簡単なチエツクサム・エラー検出システムを
示し、第２図はインタリーブド・チエツクサム・エラー
検出システムを示し、第３図は本発明の技術を含んだコ
ンピユータのブロツク図、第4a図および第4b図は本発明
の他の実施例を説明するための図である。 20……コンピユータ、22……I/O回路、24……CPU、26…
…メモリ、30……キーボード、32……マスメモリ、34…
…デイスプレイモニタ。
フロントページの続き (72)発明者 ニール・グローバー アメリカ合衆国80020 コロラド州・ブル ームフイールド・アスペン ストリート・ 1801 (72)発明者 リチヤード・ウイリアムズ アメリカ合衆国95129 カリフオルニア 州・サン・ホセ・アパートメント 23・ア ルバニイ ドライブ・4380

Claims (25)

    【特許請求の範囲】
  1. 【請求項１】データ処理装置で複数（Ｎ）の連続するバ
    イトに構成されたデータをあるバイトから後に続くバイ
    トにエラーを拡散するように記憶し、回復する方法にお
    いて、 結果値（Ri）を得るため各バイト（ｉ）と前のバイト
    （ｉ−１）との間で排他OR操作を行う過程と： 記憶装置に上記結果値Riを記憶する過程と： 上記記憶装置から上記結果値Riを読み出す過程と： 「Ｎ」が上記データのバイト数を、かつ「」が排他OR
    操作を表しているとき、次の式 となるよう、各結果値Riと前に回復したデータのバイト
    （ｉ−１）との間で排他OR操作を行なって前記結果値か
    らバイトを回復する過程と： によってあるバイトでのエラーを後続のバイトに伝搬
    し、そのエラーの検出をし易くしたことを特徴とするデ
    ータの記憶及び回復方法。
  2. 【請求項２】特許請求の範囲第１項記載の方法におい
    て、結果値を記憶する前にデータの第１チェックサムを
    計算し、前記結果値Riとともに記憶するデータの記憶及
    び回復方法。
  3. 【請求項３】特許請求の範囲第２項記載の方法において
    前記データの回復の際第２チェックサムを計算するデー
    タの記憶及び回復方法。
  4. 【請求項４】特許請求の範囲第３項記載の方法におい
    て、その第１チェックサムと第２チェックサムとが一致
    しないならばエラーが発生しているとするデータの記憶
    及び回復方法。
  5. 【請求項５】特許請求の範囲第４項記載の方法におい
    て、バイトｉがデータにおける位置ｉ（ｉ＝０、１、
    ２、３・・・）のバイトを示しているとき、前記第１チ
    ェックサムを前記結果値を読み出す前に下記の式で計算
    し、 前記結果値を読み出す過程の後に第２チェックサムを下
    記の式で計算する データの記憶及び回復方法。
  6. 【請求項６】特許請求の範囲第５項記載の方法におい
    て、データの複数の第１及び第２チェックサムを計算す
    るときに最初に決めたバイトの倍数ごとにインターリー
    ブして計算するデータの記憶及び回復方法。
  7. 【請求項７】複数の連続するバイトとしてデータを記憶
    するための記憶装置、及び 上記記憶装置に接続されて前記データに対して論理処理
    を行う処理装置であって、 各バイト（ｉ）と前のバイト（ｉ−１）との間で排他OR
    操作を行って得た結果値Riを前記記憶装置に記憶させる
    書込み装置と、 「Ｎ」が上記データのバイト数を、かつ「」が排他OR
    操作を表しているとき、次の式 となるよう、各結果値Riと前に回復したデータのバイト
    （ｉ−１）との間で排他OR操作を行なって前記結果値か
    らバイトを回復するための読出し装置とからなる処理装
    置 を有し、あるバイトでのエラーを後続のバイトに伝搬
    し、そのエラーの検出をし易くしたことを特徴とするデ
    ータの記憶及び回復装置。
  8. 【請求項８】特許請求の範囲第７項記載の装置におい
    て、前記処理装置がデータの第１チェックサムを計算
    し、前記結果値Riとともにそのチェックサムを記憶する
    装置を有するデータの記憶及び回復装置。
  9. 【請求項９】特許請求の範囲第８項記載の装置において
    前記処理装置が前記データの回復に関する第２チェック
    サムを計算する装置を有するデータの記憶及び回復装
    置。
  10. 【請求項１０】特許請求の範囲第９項記載の装置におい
    て、その第１チェックサムと第２チェックサムとが一致
    しないならばエラーが発生しているとするデータの記憶
    及び回復装置。
  11. 【請求項１１】特許請求の範囲第７項記載の装置におい
    て、バイトｉがデータにおける位置ｉ（ｉ＝０、１、
    ２、３・・・）のバイトを示しているとき、前記第１チ
    ェックサムを前記結果値を読み出す前に下記の式で計算
    し、 前記結果値を読み出す過程の後に第２チェックサムを下
    記の式で計算する データの記憶及び回復装置。
  12. 【請求項１２】特許請求の範囲第11項記載の装置におい
    て、データの複数の第１及び第２チェックサムを計算す
    るときに最初に決めたバイトの倍数ごとにインターリー
    ブして計算するデータの記憶及び回復装置。
  13. 【請求項１３】データ処理装置で複数（Ｎ）の連続する
    バイトに構成されたデータをあるバイトから後に続くバ
    イトにエラーを拡散するように記憶し、回復する方法に
    おいて、 結果値（Ri）を得るため各バイト（ｉ）と所定の作用に
    よってランダム化された前のバイト（ｉ−１）との間で
    排他OR操作を行う過程と： 記憶装置に上記結果値Riを記憶する過程と： 上記記憶装置から上記結果値Riを読み出す過程と： 「Ｎ」が上記データのバイト数を、「」が排他OR操作
    をおよび「′」が上記所定の作用を表しているとき、次
    の式 となるよう、各結果値Riと前に回復したデータのバイト
    （ｉ−１）との間で、排他OR操作を行なって前記結果値
    からバイトを回復する過程と、ただし前記前に回復した
    データへの前記作用はこの排他ORの前に行う、： ことによってあるバイトでのエラーを後続のバイトに伝
    搬し、そのエラーの検出をし易くしたことを特徴とする
    データの記憶及び回復方法。
  14. 【請求項１４】特許請求の範囲第13項記載の方法におい
    て、結果値を記憶する前にデータの第１のチェックサム
    を計算し、前記結果値Riとともに記憶するデータの記憶
    及び回復方法。
  15. 【請求項１５】特許請求の範囲第14項記載の方法におい
    て、前記データの回復の際第２チェックサムを計算する
    データの記憶及び回復方法。
  16. 【請求項１６】特許請求の範囲第15項記載の方法におい
    て、その第１チェックサムと第２チェックサムとが一致
    しないならばエラーが発生しているとするデータの記憶
    及び回復方法。
  17. 【請求項１７】特許請求の範囲第16項記載の方法におい
    て、バイトｉがデータにおける位置ｉ（ｉ＝０、１、
    ２、３・・・）のバイトを示しているとき、前記第１チ
    ェックサムを前記結果値を読み出す前に下記の式で計算
    し、 前記結果値を読み出す過程の後に第２チェックサムを下
    記の式で計算する データの記憶及び回復方法。
  18. 【請求項１８】特許請求の範囲第17項記載の方法におい
    て、データの複数の第１及び第２チェックサムを計算す
    るときに最初に決めたバイトの倍数ごとにインターリー
    ブして計算するデータの記憶及び回復方法。
  19. 【請求項１９】特許請求の範囲第18項記載の方法におい
    て、前記インターリーブの数が３であるデータの記憶及
    び回復方法。
  20. 【請求項２０】特許請求の範囲第18項記載の方法におい
    て、前記データはレコードに構成され、各レコードは８
    ビットを有する複数のバイトからなっているデータの記
    憶および回復方法。
  21. 【請求項２１】複数の連続するバイトとしてデータを記
    憶するための記憶装置、及び 上記記憶装置に接続されて前記データに対して論理処理
    を行う処理装置であって、 各バイト（ｉ）と所定の作用によってランダム化された
    前のバイト（ｉ−１）との間で排他OR操作を行って得た
    結果値Riを前記記憶装置に記憶させる書込み装置と、 「Ｎ」が上記データのバイト数を、「」が排他OR操作
    をおよび「′」が上記所定の作用を表しているとき、次
    の式 となるよう、前記前に回復したデータへの前記作用はこ
    の排他ORの前に行って、各結果値Riとその作用を施した
    前に回復したデータのバイト（ｉ−１）との間で排他OR
    操作を行なって前記結果値からバイトを回復するための
    読出し装置とからなる処理装置 を有し、あるバイトでのエラーを後続のバイトに伝搬
    し、そのエラーの検出をし易くしたことを特徴とするデ
    ータの記憶及び回復装置。
  22. 【請求項２２】特許請求の範囲第21項記載の装置におい
    て、前記処理装置がデータの第１チェックサムを計算
    し、前記結果値Riとともにそのチェックサムを記憶する
    装置を有するデータの記憶及び回復装置。
  23. 【請求項２３】特許請求の範囲第22項記載の装置におい
    て、前記処理装置が前記データの回復に関する第２チェ
    ックサムを計算する装置を有するデータの記憶及び回復
    装置。
  24. 【請求項２４】特許請求の範囲第23項記載の装置におい
    て、データの複数の第１及び第２チェックサムを計算す
    るときに最初に決めたバイトの倍数ごとにインターリー
    ブして計算するデータの記憶及び回復装置。
  25. 【請求項２５】特許請求の範囲第24項記載の装置におい
    て前記インターリーブの数が３であるデータの記憶及び
    回復装置。
JP59206453A 1983-12-08 1984-10-03 データ処理装置におけるデータを記憶し、回復する方法及び装置 Expired - Lifetime JPH0690672B2 (ja)

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
US06/559,210 US4564941A (en) 1983-12-08 1983-12-08 Error detection system
US559210 1995-11-13

Publications (2)

Publication Number Publication Date
JPS60124735A JPS60124735A (ja) 1985-07-03
JPH0690672B2 true JPH0690672B2 (ja) 1994-11-14

Family

ID=24232730

Family Applications (1)

Application Number Title Priority Date Filing Date
JP59206453A Expired - Lifetime JPH0690672B2 (ja) 1983-12-08 1984-10-03 データ処理装置におけるデータを記憶し、回復する方法及び装置

Country Status (8)

Country Link
US (1) US4564941A (ja)
JP (1) JPH0690672B2 (ja)
AU (1) AU574714B2 (ja)
CA (1) CA1208794A (ja)
DE (1) DE3443272C2 (ja)
FR (1) FR2556483B1 (ja)
GB (2) GB2151052B (ja)
HK (2) HK76788A (ja)

Families Citing this family (7)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP2557838B2 (ja) * 1986-02-18 1996-11-27 株式会社東芝 Ｉｃカ−ド
JPS63165930A (ja) * 1986-12-27 1988-07-09 Toshiba Corp エラ−検査装置
US4982401A (en) * 1988-07-06 1991-01-01 Tandy Corporation Method and apparatus for detecting transmission errors in cordless telephones
US5406279A (en) * 1992-09-02 1995-04-11 Cirrus Logic, Inc. General purpose, hash-based technique for single-pass lossless data compression
GB9314479D0 (en) * 1992-11-06 1993-08-25 Hewlett Packard Co Encoding data
US5434719A (en) * 1994-03-18 1995-07-18 Seagate Technology, Inc. Correction of header information in a magnetic disc drive
US6961000B2 (en) * 2001-07-05 2005-11-01 Amerasia International Technology, Inc. Smart tag data encoding method

Family Cites Families (6)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
DE1449837A1 (de) * 1964-06-30 1969-02-20 Philips Patentverwaltung Verfahren und Vorrichtung zur Pruefzeichenherstellung fuer die Informationsabsicherung
US3404373A (en) * 1965-02-18 1968-10-01 Rca Corp System for automatic correction of burst errors
NL6800871A (ja) * 1968-01-19 1969-07-22
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
JPS54139406A (en) * 1978-04-21 1979-10-29 Sony Corp Digital signal transmission method
US4525838A (en) * 1983-02-28 1985-06-25 International Business Machines Corporation Multibyte error correcting system involving a two-level code structure

Also Published As

Publication number Publication date
JPS60124735A (ja) 1985-07-03
FR2556483A1 (fr) 1985-06-14
HK76788A (en) 1988-09-30
GB2151052B (en) 1987-10-14
AU3289484A (en) 1985-06-13
AU574714B2 (en) 1988-07-14
GB2181581A (en) 1987-04-23
GB8628271D0 (en) 1986-12-31
HK77188A (en) 1988-09-30
DE3443272A1 (de) 1985-06-13
US4564941A (en) 1986-01-14
GB2181581B (en) 1987-10-14
FR2556483B1 (fr) 1988-07-01
GB2151052A (en) 1985-07-10
DE3443272C2 (de) 1994-02-17
CA1208794A (en) 1986-07-29
GB8417671D0 (en) 1984-08-15

Similar Documents

Publication Publication Date Title
US8495454B2 (en) Methods, apparatuses, systems, and architectures for quickly and reliably encoding and/or decoding system data
US6802031B2 (en) Method and apparatus for increasing the effectiveness of system debug and analysis
EP0388031B1 (en) Reliability enhancement of nonvolatile tracked data storage devices
US9983959B2 (en) Erasure coding of data within a group of storage units based on connection characteristics
US5333143A (en) Method and means for b-adjacent coding and rebuilding data from up to two unavailable DASDS in a DASD array
JP4709485B2 (ja) オンドライブ統合化セクタ・フォーマットｒａｉｄの誤り訂正符号システムおよび方法
WO1994011800A2 (en) Data storage system with stale data detection and error detection and correction system
JPS6074160A (ja) ビデオ・デイスクにおけるデイジタル・デ−タのエラ−訂正コ−ド
US5627843A (en) Correcting up to two disc drive read errors and detecting the occurrence of more than two read errors
CN101473308A (zh) 非易失性存储器纠错系统和方法
JPH0710048B2 (ja) 同一の連続したデータ単位のランを検出し圧縮する方法
JP2021508138A5 (ja)
CN87100929A (zh) 由或不由纠错码保护的存储和读出信息的方法和设备
JP2013543159A (ja) 統合されたデータおよびヘッダ保護を含むコード化データをデコードするための方法および磁気テープ・ドライブ（統合されたデータおよびヘッダ保護を含むコード化データのデコード）
JPH0690672B2 (ja) データ処理装置におけるデータを記憶し、回復する方法及び装置
US6457156B1 (en) Error correction method
US3439331A (en) Error detection and correction apparatus
CN1048607C (zh) 数字信息中纠错和纠正删除的方法及适于实现此方法的装置
AU604545B2 (en) A method for storing data
JP2024046388A (ja) 情報処理装置、情報処理方法及びプログラム
TW441195B (en) Signal decoding method
CN119440901B (zh) 数据的管理方法、电子设备以及存储介质
JP3813337B2 (ja) 消失誤り訂正方法とその装置
US6675345B1 (en) Method and apparatus for detecting errors in DVD data
CN113438050B (zh) 一种编码方法、解码方法、编码装置和解码装置