JPH03136524A - 長バースト誤りに対する誤り検出及び訂正システム - Google Patents

長バースト誤りに対する誤り検出及び訂正システム

Info

Publication number
JPH03136524A
JPH03136524A JP2171304A JP17130490A JPH03136524A JP H03136524 A JPH03136524 A JP H03136524A JP 2171304 A JP2171304 A JP 2171304A JP 17130490 A JP17130490 A JP 17130490A JP H03136524 A JPH03136524 A JP H03136524A
Authority
JP
Japan
Prior art keywords
error correction
error
data
matrix
symbols
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
Application number
JP2171304A
Other languages
English (en)
Inventor
Lih-Jyh Weng
リー　イー　ウェン
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Digital Equipment Corp
Original Assignee
Digital Equipment Corp
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 Digital Equipment Corp filed Critical Digital Equipment Corp
Publication of JPH03136524A publication Critical patent/JPH03136524A/ja
Pending 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/13—Linear codes
    • H03M13/15—Cyclic codes, i.e. cyclic shifts of codewords produce other codewords, e.g. codes defined by a generator polynomial, Bose-Chaudhuri-Hocquenghem [BCH] codes
    • 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/1833—Error detection or correction; Testing, e.g. of drop-outs by adding special lists or symbols to the coded information

Landscapes

  • Physics & Mathematics (AREA)
  • Engineering & Computer Science (AREA)
  • Algebra (AREA)
  • General Physics & Mathematics (AREA)
  • Mathematical Physics (AREA)
  • Pure & Applied Mathematics (AREA)
  • Probability & Statistics with Applications (AREA)
  • Theoretical Computer Science (AREA)
  • Signal Processing (AREA)
  • Error Detection And Correction (AREA)
  • Detection And Correction Of Errors (AREA)
  • Detection And Prevention Of Errors In Transmission (AREA)

Abstract

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

Description

【発明の詳細な説明】 〔発明の分野〕 本発明は、−船釣には記憶されたコンピュータデータの
誤り検出及び訂正に関し、特定的には長バースト誤りの
訂正に関する。
〔発明の背景〕
ディジタルコンピュータシステムにおけるデータの誤り
訂正コーディングの重要性は、大量記憶媒体、特定的に
は磁気テープに記録されるデータの密度が増加するにつ
れて、極度に増大して来た。
記録密度が大きくなると、テープの僅かな不完全性でも
大量のデータを崩壊させる恐れがある。データが失われ
るのを避けるために、名前が暗に示すように誤ったデー
タを訂正する誤り訂正コード（°“ＥＣＣ”）が使用す
る。
一列のデータ記号は、テープ上に記録される前に冗長記
号を形成するために数学的にコーディングされる。冗長
記号にはデータ列に追加されてコードワード、即ちデー
タ記号プラス冗長記号、が形成される。これらのコード
ワードがテープに記録される。記憶されたデータがテー
プからアクセスされる場合には、データ記号を含むコー
ドワードがテープから検索され、数学的に復号される。
復号中、データ内に何等かの誤りが検出され、そしても
し可能であれば、冗長記号の操作を通して訂正される（
復号の詳細な説明に関しては１９７２年のＭＩＴプレス
のピータソン及びウェルトンの誤り訂正コード、第２版
を参照されたい）。記憶されたディジタルデータは複数
の独立した誤りを含み得る。これらの多重誤りの訂正に
使用される誤り訂正コードの最も効果的な型の１つはリ
ード・ソロモンコードである（リード・ソロモンコード
の詳細に関してはピータソン及びウェルトンの誤り訂正
コードを参照されたい）。データ記号のストリング内の
多重誤りを訂正するために、リード・ソロモンコードは
“ＧＦ（ＰＱ　）″で表わされるガロアフィールドとし
て知られる複数組の記号の種りの数学的特性を効率的且
つ効果的に使用する。但し、“Ｐ　”は素数であり、“
′ｑ゛はこのフィールド内の各要素即ち記号内のデイジ
ット数（基数Ｐ）として考えることができる°“Ｐ”は
、ディジタルコンピュータ応用においては通常は値２を
有し、従って“ｑ”は各記号内のビット数である。
典型的にはデータは記号の長シーケンスとしてテープ上
に記憶される。テープに記憶されたデータ内の誤りは長
ペースト、即ちある行内に多くの誤りの記号として現わ
れることが多い。単独の、または始めはバーストとして
現われることがない多くの独立した誤りの検出及び訂正
の両方或は何れか一方を行うように設計された技術は、
これらの長バースト誤りの検出或は訂正に充分に適して
はいない。従って、典型的にこれらの長バースト誤りを
操作するために、特別な検出及び訂正の両方或は一方の
技術が使用される。
現在使用されている長バースト誤り検出技術は、それぞ
れが所定最大数までの誤りの記号を含む単一または二重
バーストを検出する。より多数の誤りの記号を含むバー
ストを検出するコードは、より少ない誤りの記号を含む
バーストを検出するコードよりもパワフルであると考え
られる。例えば周知のファイヤコードは、２キロバイト
のデータ内の２２ビツトずつまでの二重バーストを検出
し、また周知の、よりパワフルなバートンコードは２キ
ロバイトのデータ内の２６ビツトまでの二重バーストを
検出する。テープに記憶されたデータの密度が増加する
につれて、長バーストｉＭ　リ、内ニ含まれるデータ記
号の数も増加する。これらの長バースト誤りは、記憶さ
れたデータの密度の増加のために、ディスクに記憶され
るデータに直ちに発生し得る。従って、より長い誤リバ
ーストを検出するメカニズムが望ましい。
一旦長バースト誤りが検出されると、もし可能であれば
含まれる誤りの記号は訂正される。誤りをよく迅速に訂
正できるほど、そのデータはより迅速に利用者が利用で
きることになる。即ち、誤り訂正の速度が増すにつれて
実効データ転送速度が増大する。従って、検出した長バ
ースト誤りを迅速に訂正するメカニズムが望ましい。
〔発明の概要〕
本発明はその広い形において、誤りを検出し訂正しつつ
データを符号化しそれを磁気テープに記録するシステム
に関し、このシステムは：Ａ、ｄデータ記号のストリー
ムを、ジェネレータ多項式ｇ（ｘ）として（８進形の） ｇ　（ｘ）　＝　（３）　”　（３）　”　（１０００
０３）　”　（１０２０４３）　”　（１１００１３）
　”　（１５６０５１３）或は ｇ　（ｘ）　＝２４１３６０７０３６５６５１７２４３
３２２３を有し、これらのベクトル成分が左から右へ最
高次項から最低次項の係数を表わす多項式の項の２進係
数である周期冗長コードを使用して誤り検出冗長記号を
生成し、生成された冗長記号をデータ記号に追加して一
連のＣＲＣコードワードを形成する第１のエンコーダ； Ｂ、誤り訂正コードを使用して所定数りのＣＲＣコード
ワードからｈデータ記号を符号化し、ｈデータ記号と共
に誤り訂正コードワードを形成する対応付けられた誤り
訂正冗長記号を生成する第２のエンコーダ；及び Ｃ，ｈＣＲＣコードワード及び対応付けられた誤り訂正
冗長記号をテープに記録する記録手段を含む。
以下は説明するように、誤り訂正システムは磁気テープ
に記録されるデータを２回符号化する。
即ち１回は誤り検出のために水平に、また１回は誤り訂
正のために垂直に符号化する。先ず、システムはパワフ
ルな周期冗長検査（ＣＲＣ）コードを使用してｄマルチ
ビットデータ記号のストリームを符号化しＣ冗長記号を
形成する。ＣＲＣコードは以下のようなジェネレータ多
項式ｇ（ｘ）　　（８進ベクトル形〕 ｇ（ｘ）＝２４１３６０７０３６５６５１７２４３３２
２３であることを特徴とし、ベクトル成分は左から右へ
多項式の最高から最低の次項の係数を表わす多項式の項
の２進係数である。ＣＲＣコードは、６４ピントまでを
含む単一の長バースト誤り及び２８ビツトまでずつを含
む二重長バースト誤りを検出することができる。
誤り訂正システムはｄデータ記号とｃＣＲＣ冗長記号と
を連結してＣＲＣコードワードを形成する。次いでエン
コーダは、ある群内のＣＲＣコードワード内の各対応記
号が垂直に整列するようにＣＲＣコードワードの群を形
成する。整列された記号は一連の１記号中列を形成する
。
システムは更に、リード・ソロモン誤り訂正コードを使
用してデータ記号を含む各列を符号化する。ＣＲＣ冗長
記号を含む列は符号化されない。
この符号化によって各列毎に所定数ｎのＥＣＣ冗長記号
が生成される。次でエンコーダはこれらのＥＣＣ冗長記
号を、ＥＣＣ冗長記号がそれらに対応するデータ記号と
整列するように群内に包含させる。これによってエンコ
ーダは、それぞれがｂ記号、ｂ−ｎデータ記号、及びｎ
ＥＣＣ冗長記号を有する一連の列を形成する。
ある群内のデータ記号に対応するＥＣＣ冗長記号自体は
、ＣＲＣコードを使用して符号化される。
種々のＥＣＣ冗長記号及び対応ＣＲＣ冗長記号はｎＥＣ
Ｃコードワードを形成する。即ち、ｎ番目のＥＣＣコー
ドワードは（ｉ）データ記号の各列に対応するｎ番目の
ＥＣＣ記号、及び（ｉｉ）関連ｃＣＲＣ記号を含む。コ
ードワードの１つの完全な群はｂ−ｎデータコードワー
ド及びｎＥＣＣコードワードを含む。種々のコードワー
ドは群として、即ち多重トラック内に、またはビット直
列に（即ち単一のトラック内に）テープに記録される。
従って、群はデータが検索される時に再組立てする必要
があろう。
データがテープから検索される時、必要ならばデータは
先ず群に組立てられ、次で各群は各コードワード毎にそ
の中に含まれるＣＣＲ冗長ビットを使用してコードワー
ド単位で復号される。ＣＲＣコードは６４ビツト或はそ
れ以下の単一の誤り及びそれぞれが２８ビツトまでの長
さであり得る二重長バースト誤りの両方或は何れか一方
の確実性をもって検出する。コードは各ＯＣＲコードワ
ード内のランダムな７つまでの誤りをも検出する。
もしデータＣＲコードワード内に誤りが検出されれば、
システムはリード・ソロモンコードＥＣＣ冗長記号及び
幾つかの復号アルゴリズムの１つを使用して列毎にそれ
らを訂正する。ＣＲＣ復号は誤りの垂直位置を指し示す
ので、殆んどの場合誤り訂正は簡略化される。
データを符号化するために使用される特定のリード・ソ
ロモンコードは、既知の位置を有する単一の誤りを迅速
且つ容易に訂正可能なようにデータを符号化する。もし
ＣＲＣコードが１つのコードワード、即ちコードワード
ｔだけの中に誤りを検出すれば、列当り多くとも１つの
誤りのデータ記号が存在する、即ち位置ｔの列内の記号
が誤っている。特定の列内の位置りの記号に対応付けら
れた誤り値を計算するために、システムはその列内の記
号と一緒に加算（排他的論理和）する。この和は誤り値
であり、従ってシステムは記号と対応付けられた誤り値
とを一緒に加算することによって誤りを訂正する。もし
位置もの記号が誤りでなければ、計算された誤りは０で
ある。
ＣＲＣ復号が特定コードワード誤りを指示すると、シス
テムはそのコードワード内の全てのデータ記号を誤りと
して処理する、従ってシステムは各列毎に誤り値を計算
する。
ＣＲＣ複合が、多重ＣＲＣコードワードが誤りを含むこ
とを指示し、ｌ或はそれ以上のＣＲＣコードワードがデ
ータコードワードであれば、システムは先ずどの列が誤
りを含むかを決定する。次いでシステムはこれら特定の
列の誤り訂正に携わる。
特定の列が何等かの誤りを含むか否かを決定するために
、システムはリード・ソロモンコードを使用して列デー
タ記号を符号化し、新ＥＣＣ冗長記号を生成する。次で
システムはこれらの記号をテープから検索された対応Ｅ
ＣＣ冗長記号に加算（排他的論理和）され残りの記号Ｒ
ＥＭ、、ＲＥＭ、、−−−−１ＲＥＭｎを公式化する。
もし残りの記号が全てＯであれば２組のＥＣＣ記号は同
一であり、従ってその列内のデータ記号に誤りはない。
もし１或はそれ以上の残りの記号が非０であれば、２ｍ
のＥＣＣ記号は同一ではなく、列は１或はそれ以上の誤
りの記号を含む。従ってシステムは誤りを含む各列毎に
誤り訂正を遂行する。
もしＣＲＣがＩＣＲＣコードワードとｎＣＲＣコードワ
ードとの間に誤りを指摘すれば、システムは残りの記号
ＲＥＭ、　、ＲＥＭ、　、−−−−１ＲＥＭｆｉ及び誤
りのコードワードの特定垂直位置に基いて１・組のｎ方
程式を同時に解く。システムはこれらの方程式を解くた
めにガロアフィールド操作によって処理される行列を使
用する。これらの解が誤りのコードワードに対応する位
置における列配置に対応する誤り値である。
もしＣＲＣコードが、ｎ＋１或はそれ以上のコードワー
ドが誤りを含むことを指示すれば、システムは列当りｎ
或はそれより少い実際の誤りが存在するものとして、及
び若干の訂正手順の１つを使用することによって誤りを
訂正する。次でシステムはＣＲＣコードを使用してデー
タコードワード内の全ての誤りが訂正されたか否かを決
定する。
もしＣＲＣが更なる誤りを検出すれば、システムはＣＲ
Ｃコードが全ての誤りが訂正されたことを指示するまで
誤り訂正の全手順を繰り返すが、或はシステムはデータ
が訂正不能であることをラベル付けする。
ｎ＋１の誤りを訂正するための１手順は、何れかの特定
の列内の未知の位置に１つだけの誤りの記号が存在する
ものと仮定することである。この誤りは未知の位置を有
する単一の誤りを訂正するためのメカニズムを使用して
訂正することができる。システムは１つの誤りの記号が
考え得る多くの誤り位置のどこに存在しているのかを知
らず、従って誤りの位置は未知と考えられる。
先ず、システムは特定の列に関する残りの記号ＲＥＭ、
　、ＲＥＭ、　、−−−−１ＲＥＶ、を調べる。
もし残りの記号全てが０であれば、それは列データが誤
ってなく誤り訂正は不要であることを表わす。もし残り
の記号の１つ、例えばＲＥＭ、だけが非Ｏであれば、そ
れは列位置ｉ内の記号が誤っていることを表わす。この
記号に対応する誤り値はＲＥＶ、であり、従ってＲＥＭ
、をその記号に加算することによって誤りが訂正される
。
もし２以上の残りの記号が非Ｏであれば、システムは残
りの記号を使用して巡回シフタのｎシフトレジストを初
期化する。シフタは、データを符号化するために使用し
たリード・ソロモンジェネレータ多項式の逆数で残りの
記号を除すことによって列内の記号を後方に周期的にシ
フトさせる。
リード・ソロモンコードが周期的特性のために、列内の
誤りを訂正するために必要な誤り値が影響を受けること
はない。
シフティングメカニズムは、レジスタ１．２、−（ｎ−
１）の内容が全てＯになり、ｎ番目のレジスタ内に得ら
れる記号が非Ｏになるまで列配置をシフトさせる。もし
シックが記号を合計り回シフトさせれば、列位置ｎ＋Ｌ
内の記号は誤りであり、ｎ番目のレジスタは対応誤り値
を含む。
もしシックが５回シフトさせた後、即ち列内の各記号位
置毎に１回のシフトを行った後に誤り位置が見出されな
ければ、その特定の列に対する誤り訂正は失敗したこと
になる。次でシステムは次の列の誤りの訂正に向う。
一旦誤り訂正が各列に対して企図されると、システムは
ＣＲＣコードを使用してコードワード群の誤りを調べる
。もし更なる誤りが存在すればシステムは、もし可能で
あれば、複数の残りの誤りのために設計された誤り訂正
手順を使用してそれらを訂正する。
〔実施例〕
リード・ソロモンコードＥＣＣ冗長記号を含む数学的操
作は、ガロアフィールド加算、乗算及び除算の全て或は
何れかを使用して遂行される。ガロアフィールド加算は
コード記号をビット毎に排他的論理和（ＸＯＲ）するこ
とによって遂行され、記号°°１”によって表わされる
ガロアフィールド乗算はモジュロｐ　（ｘ）である（但
しｐ　（ｘ）はガロアフィールドを特徴付ける基本多項
式である）。
第１図はｂコードワード４の群６を示す。好ましい実施
例においてはｂ＝２０である。水平に配向されているコ
ードワード４はｄデータ（即ち情報）記号及び対応付け
られたＣ冗長ビットを含む。
Ｃ冗長ビットの生成を以下に説明する。コードワード４
は、各コードワード４内の対応記号が一連の１記号巾の
列を形成するように垂直に整列されている。
各コードワード４内のＣビットは、長バースト誤りを検
出するのに適する巡回冗長検査（ＣＲＣ）コードを使用
してコードワードデータ（即ち情報）記号を符号化する
ことによって生成される。ｃＣＲＣ冗長ビットは対応付
けられたデータ（即ち情報）記号に追加されてＣＲＣコ
ードワードが形成される。第１図のコードワード番号５
〜２０はデータ記号及びｃＣＲＣ冗長ビットを含む。コ
ードワード番号１〜４はｄ情報記号及びｃＣＲＣ冗長ビ
ットを含む。好ましい実施例においては、ｄ＝２キロバ
イトであり、またＣ−６４ビツトである。
ＣＲＣコード符号化の詳細に関して以下に説明する。
各コードワード１〜４内のｄ情報記号は、リード・ソロ
モン誤り訂正コード（ＥＣＣ）冗長記号である。ＥＣＣ
冗長記号はデータ記号を含む各列を符号化することによ
って生成され、ＣＲＣビットを含む列は符号化されない
。特定の列内に記録されたＥＣＣ冗長記号、即ちデータ
記号を含む列のコードワード０〜４内の記号はその列内
のデータ記号に対応する。従って、これらの各列はリー
ド・ソロモンコードのコードワードを形成する。
次で各コードワード１〜４内のｄＥＣＣ冗長記号は、Ｃ
ＲＣコードを使用して符号化される。この符号化によっ
て生成されたｃＣＲＣ冗長ビットがＥＣＣ冗長記号に追
加されてＥＣＣコードワード、即ちＣＲＣコードの形の
コードワードが形成される。従って、記憶されたＥＣＣ
冗長記号内の誤りが検出できる。またリード・ソロモン
コード及びＣＲＣコードが共に線形コードである故に、
ＣＲＣビットを含む各列はリード・ソロモンコードワー
ドを形成する。
ＣＲＣビットを生成するために、エンコーダ（図示せず
）は、日進ヘクトルとして表わされる次の６４次２進ジ
工ネレータ多項弐ｇ　（ｘ）によっ特徴付けられた巡回
冗長検査コードを使用して、適切なデータ或はＥＣＣ冗
長記号を符号化する。
ｇ　（ｘ）　＝　（３）　”　（３）　”　（１０００
０３）“（１０２０４３）　”　（１１００１３）　”
　（１５６０５１３）或は ｇ　（ｘ）　＝２４１３６０７０３６５６５１７２４３
３２２３但し、ベクトル成分は、左から右へ最高から最
低の次項の係数を表わす多項式の項の２進係数である。
普通の設計のＣＲＣエンコーダは、このＣＲＣジェネレ
ータ多項式を使用して普通の技法でデータ（即ち情報）
記号を符号化する。データはｇ　（ｘ）の逆数ｇ”（ｘ
）　　（８進形）を使用して符号化することもできる。
ｇ”　（ｘ）　＝　（３）　”　（３）　”　（１４０
００１）　”　（１１４２０４１）　”　（１５００１
１）　”　（１５１２０７３）或は ｇ”（ｘ）・３１１３３０５３６２５６５７０３４１７
２０５゜ＣＲＣコードの長さは、その自然長である８０
億ビット以上から１７．０００ビツトよりや−多いまで
短縮される。短縮されたコードは、１７．０００ビツト
の中から６４ビツトまでの長さの単一パースト誤りを検
出できる確度を持つパワフルなコードである。このコー
ドは更に２８ビツトずつまでの二重バースト誤りを検出
する確度である。コードのハミング距離は少なくとも８
であり、従ってコードは如何なる位置においても７つま
での独立した誤り、即ちバースト誤りに対抗する７つの
ランダムな誤りのビットを検出する。
短縮されたコードは、１７．９０７ビツトのデータ内の
２８ビット二重バースト誤りを実際に検出する。
従って、ブロックは２キロバイトの実際のデータと、１
５２３ビツトの追加制御情報とを含むことができる。
前述の如く、ある群内のデータの列は、誤り訂正の目的
で、リード・ソロモンコードを使用して符号化される。
このコードは２進形ではｘ８＋ｘ５＋ｘ３＋ｘ２＋　１ である８進ヘクトルｐ（ｘ）＝４５５によって表わされ
る基本多項式ｐ　（ｘ）によって特徴付けられたガロア
フィールドＧＦ（２”）上でデータを符号化する。デー
タ列を符号化するために使用される特定のリード・ソロ
モンコードはジェネレータ多項式％式％） によって規定される。但しαはガロアフィールドの基本
要素である。フィールドの要素は８ビット記号、即ちバ
イトであり、また殆んどのコンピュータハードウェアが
バイトに編成されたデータを処理するように準備されて
いるから、好ましい実施例においてはデータをガロアフ
ィールドＧＦ（２”）上で符号化する。
第２図は列データ記号を符号化するためのエンコーダ１
０を示す。エンコーダ１０は、符号化操作に先立ってク
リヤされる一組の８ビツトレジスタ１６．１８．２０及
び２２を含む。レジスタの内容は、それぞれ排他的ＯＲ
（ＸＯＲ）回路１１．１２．１３及び１４に印加される
。エンコーダへの入力は８人カラインを通してバイト直
列、ビット並列の形でＸＯＲ１４へ印加される。
入力操作中スイッチ３２は、ＸＯＲ１４の出力がガロア
フィールド乗算器２４．２６．２８及び３０に印加され
るような位置にある。乗算器２６．２８及び３０の出力
はそれぞれＸ０ＲＩＩ、１２及び１３に印加され、乗算
器２４の出力はレジスタ１６に供給される。ガロアフィ
ールド乗算器２４〜３０はそれらへの入力にそれぞれ係
数α６α７−α２４９及びα７５を乗する。
従って、各入力バイトはエンコーダ１０に印加されるに
つれてレジスタ２２の内容にビット毎に（モジュロ２）
加算される。次でこの和は、全ての、しかしＧ　（ｘ）
内のＸ最高のべきの係数を含むガロアフィールド乗算器
２４〜３０によって同時に乗算（モジュロｐ（ｘ）　）
される。次で、バイトと係数のそれぞれの積はレジスタ
１６〜２２の内容に加えられる（モジュロ２）。
特定の列内の全てのデータバイトがエンコーダ１０に印
加された後、エンコーダスイッチ３２は位置２に倒され
、レジスタ１６〜２２の内容は、左シフトされることに
よってそれぞれＥＣＣ冗長記号記号　、Ｒ，、Ｒ，ＳＲ
，とじてアンロードされる。スイッチ３２が位置２へ倒
されてシフティング動作中には、ＸＯＲの垂直入力はレ
ジスタ２２〜２６の内容を変更することなく渡すことが
理解されよう。
この型のエンコーダは当分野においては周知である。
符号化システムは、コードワード１〜４内の適切な列デ
ータ記号の下にＥＣＣ冗長記号を整列させることによっ
て完全群を公式化する。即ちコードワード４はＲ３冗長
記号を含み、コードワード４はＲ２冗長記号を含む等々
である。完全群、即ちコードワード１〜２０内の対応デ
ータ記号及び対応付けられたＥＣＣ冗長記号はリード・
ソロモンコードワードを形成する。
プロセッサ（図示せず）はこれらのコードワードをテー
プに書き込む。プロセッサはコードワードを如何なる書
式でも書き込み得ることは理解されよう。例えばプロセ
ッサは、コードワードが次々と後続するビットのストリ
ックとして、コードワードを書き込むことができる。爾
後にコードワードがテープから検索される時、プロセッ
サは群６を再組立てする。
利用者がテープからデータを要求すると、プロセッサは
要求されたデータ記号及び群６を再組立てするために必
要な他の何等かのコードワードを含むコードワード４（
第１図）をテープから検索する。次で誤り訂正プロセッ
サ（図示せず）は、群６内の何れかのコードワード内の
誤りが存在するか否かを成分ＣＲＣビットを使用して各
コードワードを復号することによって決定する。もしＣ
ＲＣコードが何等の誤りも検出しなければ、誤り訂正プ
ロセッサは要求されたデータを要求した利用者に送る。
もしＣＲＣコードが誤りを検出すれば、ＣＲＣコードは
誤りのコードワードを、従って誤りの位置を指示する。
それによって誤り訂正プロセッサは適切な誤り訂正を遂
行してこれらのコードワード内の記号を訂正する。
もし全ての誤りがコードワード１〜４、即ちＥＣＣコー
ドワード内に位置していれば、データは誤りないものと
見做され、誤り訂正プロセッサは直ちにデータを要求し
た利用者へ送る。しかし、もし誤りがデータ記号を含む
コードワード内に検出されれば、誤り訂正プロセッサは
（もし可能であれば）ＥＣＣ冗長記号を使用して誤りを
訂正する。誤りを訂正するために、誤り訂正プロセッサ
は検出した誤りの数及び位置に基いて適切な誤り訂正ル
ーチンを選択する。
もしＣＲＣビットが１つのＣＲＣコードワード、例えば
コードワードｂ８だけが誤っていることを指示すれば、
プロセッサは既知の位置にある単一の誤りを訂正するた
めに特別に設計された手順を使用してそのコードワード
内の誤りのデータ記号を訂正する。データ記号を含む任
意の列の場合、その列は誤りがないか或は１つの誤りの
行列（列位置内の記号はコードワードｂ８に対応する）
を含むかの何れかである。
この時点においては誤り訂正プロセッサは、特定の列が
誤りの記号を含むか否かを決定しない。
その代りに全ての列内の位置ｂ８内の記号を訂正するこ
とを試みる。即ち全列に対して、誤り訂正プロセッサは
位置ｂ、内の記号に対応する誤り値を生成する。次で記
号と生成した誤り値とを組合わせる、即ち記号を生成し
た誤り値に加算することによって記号を訂正する。誤っ
ていない記号に関して生成した誤り値はＯである。従っ
てこの誤り値を記号に加算してもそれを変化させること
はない。変形として、誤り訂正プロセッサはデータ記号
を含む列に対してだけ誤り値を計算し、ＣＲＣ記号を含
む列を無視することができる。
位１ｂ、内の潜在的な誤りの記号に関する誤り値を生成
するために、プロセッサはガロアフィールド加算を使用
して列内の全ての記号を加え合わせる。この和は位置ｂ
、内のデータ記号に対応付けられた誤り値である。従っ
て誤り訂正プロセッサはこの和を誤りの記号に加えてそ
れを訂正する。
位置ｂ、内の記号を除く列内の全ての記号を加え合わせ
ても同じ結果が得られる。この和は訂正されたデータ記
号である。従って利用者に伝送されるデータ内の位置ｂ
、内の記号をこの和に置換する。
この単一誤り訂正手順は、ジェネレータ多項式の因数と
して（ＸＩα０）を有するリード・ソロモンコードにお
いてのみ可能である。因数としてこの項を有することは
、４次多項式であるジェネレータ多項式が非Ｏ係数を有
する２つより多い別個の項を有し得ることを意味する。
従って対応付けられたエンコーダ１０は２以上の分離し
たガロアフィールド乗算器を含む可能性が大である。こ
のためエンコーダは単一の誤り訂正のためにデータを符
号化する最も簡易なエンコーダではあり得ない。しかし
、リード・ソロモンコードの使用によに単一のＣＲＣコ
ードワードに含まれる誤り訂正の容易さは、エンコーダ
の複雑さの増加よりも重要である。
もしＣＲＣビットが１つ以上のコードワード、ＥＣＣ冗
長記号２つのコードワードが誤りの記号を含んでいるこ
とを指示すれば、プロセッサは既知の位置にある１つか
ら４つまでの誤りを訂正するように設計された誤り訂正
手順を使用して誤りを訂正する。先ず誤り位置プロセッ
サが各列毎に残りを計算することによってどの列が誤り
を含むかを決定する。特定の列の残りは、（ｉ）エンコ
ーダ１０を使用して検索した列データ記号を符号化して
検索したデータ記号に対応する新ＥＣＣ冗長記号を生成
し、（ｉｉ）これらの新ＥＣＣ冗長記号と検索したＥＣ
Ｃ冗長記号とを比較することによって計算する。
２＆ＩｌのＥＣＣ記号は、ビット毎にＸＯＲすることに
よって対応記号が比較される。得られた記号が残り記号
ＲＥＭ、　、ＲＥＭ、　、ＲＥＭ、及びＲＥＭ３である
。もし残り記号が全てＯであれば２組のＥＣＣ記号は同
一であり、データ列は誤りがないものとされる。もし１
或はそれ以上の残り記号が非０であれば、列は誤りを含
んでいる。
誤りを含む列、即ち残りが非Ｏである列のための誤り値
を計算するために、誤り訂正プロセッサはこれらの各列
毎に４つの連立方程式を解く。これらの各方程式は異な
る列の残り記号を含む。
方程式を公式化するために、プロセッサはＸ１′モジユ
ロＧ　（ｘ）に対応する行を有する行列Ｍを生成する。
ここにｅは行列の任意行に対応付けられた記号位置であ
り、Ｇ　（ｘ）はリード・ソロモンコードジェネレータ
多項式である。行列Ｍの行は（Ｘ”　、Ｘ”　、Ｘ’　
、Ｘ’）の係数に対応する成分を有するベクトルと考え
ることができる。従って例えば、行列ＭのＸ３に対応す
る行は（ｌ、０．０．０）であり、Ｘ４に対応する行は
（Ｘ７５Ｘ２４９　、Ｘ）−ｘｂ）である。
誤り訂正プロセッサはエンコーダｌＯを使用し以下のよ
うにして行列Ｍの行を生成できる。先ず、プロセッサは
エンコーダのレジスタ１６．１８．２０及び２２をそれ
ぞれ値Ｏ１０，０，１に初期化する。次にレジスタに行
列のＸｏに対応する行に要素を含ませる。次でプロセッ
サはスイッチ３２を位置１にしてエンコーダｌＯを１回
巡回させ（即ちクロックして）行列Ｍの第２行（即ちＸ
Ｉ）の要素をレジスタ内に生成させる。プロセッサはス
イッチ３２を位置ｌにしたまま合計１９回エンコーダを
クロックし、エンコーダサイクルによって生成されたレ
ジスタ１６．１８．２０及び２２の内容を行Ｘ１乃至Ｘ
Ｉ９として使用する。
次での行列は将来の使用のために記憶される。第３図は
８進形及び２進形で完全行列Ｍを示す。この行列が１回
だけ生成され、爾後全ての誤り訂正に使用されることは
当業者ならば理解されよう。
誤りが検出された例えばブロック４及び６内の特定の列
の誤り値方程式は ＲＥＭ３＝Ｙ（ｅ４）＊　　１７＋Ｙ（ｅｂ）＊　　１
３４ＲＥＭｚ＝Ｙ（ｅｎ）＊　６６＋Ｙ（ｅｂ）＊　７
ＲＥＭ＋＝Ｙ（ｅ４）＊　１７０＋Ｙ（ｅ６）＊　２７
７ＲＥＭｏ−Ｙ（ｅａ）＊　１００＋Ｙ（ｅｂ）＊　３
４５である。但し、Ｙ（ｅａ）及びＹ（ｅｂ）はそれぞ
れ列位置４及び６内の列記号の誤り値であり、Ｙ（ｅ４
）及びＹ（ｅ６）項の係数はそれぞれ行列Ｍの行Ｘ４及
びＸ６の要素である。例えばＲＥＭ３の方程式は係数と
して行列Ｍの行Ｘ４及びＸ６の第４列要素を有し、ＲＥ
Ｍ２の方程式は係数としてこれらの行の第３列要素を有
する等々である。誤り訂正プロセッサはこれら方程式の
何れか２つを解いて誤り値を決定できる。しかしプロセ
ッサは４つの方程式を全て及び以下に説明する手順を使
用して、検出した２、３或は４の誤りのための誤り値を
決定する。
方程式を解いた後、誤り訂正プロセッサは誤りを含む各
列毎に行列Ｍ′を公式化する。行列Ｍ′は、ＣＲＣが誤
りを検出した各コードワードに対応する行と、要素とし
て列残り記号ＲＥＭｏ、ＲＥＭ、　、ＲＥＭｔ及びＲＥ
Ｍ、を含む、最下行とを有、する０本例においては誤り
を含むコードワードは２つ（即ちコードワード４及び６
）であるから行列Ｍ′の行１及び２は行列Ｍの行Ｘ４及
びＸｈと同一である。行列Ｍ′の第３行は列残りＲＥＭ
ｏ　、ＲＥＭ＋　、ＲＥＭｔ及びＲＥＭ３である。この
特定例においては列残りは８進ベクトル１７５．４７．
２１１．１２３である。従って８進形の行列Ｍ′は である。
次に誤り訂正プロセッサは列演算を使用して行列Ｍ′を
処理し、最初の２行の最初の２列の要素として２×２恒
等行列と、行ｌ及び２の残り要素として０だけを有する
行列Ｍ″に圧縮する。本例では行列Ｍ“は である。
もしＣＲＣが３つの誤りを指示すれば、対応行列Ｍ′は
４行を有し、それは最初の３行の最初の３列に３×３恒
等行列を含み行１〜３の残り要素としてＯだけを有する
行列Ｍ″に圧縮される。
行列Ｍ′を圧縮する際に遂行される２列演算は、（１）
　　”ａ”とＧＦ（２”）の非０要素、１１　ｂ　ＩＩ
をＧＦ（２”の任意要素として、ａ８　〔列ｉ）＋ｂ”
　　（列ｊ〕を列ｉに置換し、 （２）２つの列を交換する ことである。
行列Ｍ″がこの圧縮された形である時、行列の最後の行
は誤りのコードワード内のデータ或はＥＣＣ冗長記号に
対応付けられた誤り値を含む。
従って、第１列の行列要素３５５はコードワード４内の
ＥＣＣ冗長記号に対応付けられた誤り値であり、第２列
の要素１３５はコードワード６内のデータ記号に対応付
けられた誤り値である。誤り位置に対応しない２の列内
の要素は０である筈である。そうでない場合には、訂正
不能な誤り状態が存在し、計算された誤り値は拒絶され
る。
もし検出された誤りの１つだけがデータコードワード内
にあり、他の検出された各誤りがＥＣＣコードワード内
にあれば、検出された誤りに対応する行列Ｍ′を誤りの
データ記号の誤り値を計算するために直接使用すること
ができる。従って行列を圧縮させる必要はない。例えば
、もし誤りがＥＣＣコードワーリードび３、データコー
ドワード５内で検出され、所与の列の残り記号は３２１
．３３５．３６０及び３７５であれば、行列Ｍ′はであ
る。
行列Ｍ′はその最初の２行即ちＥＣＣコードワードに対
応する行内に１と０だけを有する。従ってこの行列は、
前述の圧縮された形ではないにしても、既に圧縮された
形である。コードワード５データ記号に対応する誤り値
は、この行列を使用し行列の列１或は列２の何れかの最
終行即ち行ｌ及び行２内でＯを有する何れかの列内の要
素を、同じ行列の列の行３内の要素で除すことによって
計算される。即ち、コードワード５データ記号の誤り値
（８進形）は、 ３６０／１２７＝３３５／３２２＝１１５である。
既知の位置を有する二重データ記号誤りを訂正する変形
誤り訂正手順は、リード・ソロモンコードの巡回特性を
利用して誤りの１つをＦＣＣ記号位置内八°へシフトさ
せる。即ち記号はそれらに対応付けられた誤り値を変化
させることなく周期的に若干の位置数だけ後方にシフト
させられる。
シフト後、誤り訂正プロセッサは単一のデータ記号誤り
に関して記述した手順を使用して、未だにデータ記号位
置にある記号に対応付けられた誤り値を計算する。次で
プロセッサは上述の既知位置を有する単一の誤り訂正手
順を使用して、即ち訂正されたデータ記号を含む列内の
全ての記号を加え合わせることによって、残りの誤りの
記号に対応する誤り値を計算する。
第４図を参照する。ある列内の記号を循環的にシフトさ
せるために、誤り訂正プロセッサは循環シフタ４０を使
用する。このシフタ４０はレジスタ４４．４６．４８．
５０内の記号にＧ　（ｘ）の逆数を乗するようになって
いる線形シフトレジスタである。即ちガロアフィールド
乗算器５２．５４．５６．５８はＧ　（ｘ）の逆数の項
の係数を含む。例えば、乗算器５２はα７８／α６　（
これはＧ　（ｘ）のＸ１項の係数をＧ　（ｘ）のＸ０項
の係数で除したもの）によって項を乗算する。乗算器５
４〜５８の被乗数はＧ（ｘ）　（７）Ｘ”　、　Ｘ３及
びＸ４係数をＸＯ係数で除したものである（Ｘ４項の係
数は１であり、これはＧＦ（２１′）ではα２５５と同
一である）。
特定の列をシフトさせるために、誤り訂正プロセッサは
列残り記号ＭＥＲｏ　、ＭＥＲ，、ＭＥＲｚ及びＭＥＲ
，をそれぞれレジスタ４４．４６．４８．５０内ヘロー
ドする。次でプロセッサは、誤りの１つだけの位置がデ
ータ記号に対応し、他の誤りの位置がＥＣＣ記号に対応
するまで循環シフタ４０をＬ回シフトさせる。従って誤
り位置は位置ｅ、及びｅ２から位置ｅ、−Ｌ及びｅ２−
Ｌまでシフトする。
次で誤り訂正プロセッサは、行列Ｍ′を公式化するため
にレジスタ４４．４６．４８．５０内の記号を列残り記
号として使用する。行列Ｍ′の最初の２行は列位置ｅ、
−Ｌ及びｅ、−Ｌに対応し、第３行はシフトした残り記
号に対応する。次にプロセッサは行列Ｍ′の行２及び３
の適切な要素を除すことによってデータ記号の誤り値を
計算する。
プロセッサは記号に計算した誤り値を加算することによ
って記号を訂正する。
残りの誤り、即ち位置ｅ２内の記号の誤り値を計算する
ために、プロセッサは位置ｅ１内の訂正された記号を含
む列記号を加え合わせる。次でプロセッサは位置ｅ２内
の記号に計算した誤り値を加算することによってその記
号を訂正する。
４より多い誤りが検出されると、誤り訂正プロセッサは
、先ず所定数ｆの誤りを訂正し、残りの誤りのための誤
り訂正手段を繰り返すことによって、それらを訂正する
。第５図は５或はそれ以上の誤りのコードワードの若干
の形態を示す。“Ｘ“。
は誤りの記号を表わす。例えば形態（１）は、各列が多
くても１つの誤りを含むように誤りが現われるコードワ
ードを示す。従って誤りは単一誤り訂正行列を使用して
訂正することができる。同様に形態（２）は列当り多く
とも２つの誤りを有し、これらの誤りは二重誤り訂正技
術を使用して訂正できる等々である。しかしシステムは
５或はそれ以上の誤りのコードワード内に誤りがどのよ
うに分布しているのかを正確に決定できる何等のメカニ
ズムも有していない。従って、これらの誤りを訂正すた
めには特別な誤り訂正手順を使用しなければならない。
１つの誤り訂正手順は、既知の位置を有する特定数の誤
りＶと未知の位置を有する単一の誤りとに対応付けられ
た誤り値を計算する。即ち誤り訂正プロセッサはＶ個の
検出された誤り位置を選択し、これらの位置に対応付け
られた行列Ｍの行を列残り記号と共に使用して単一の未
知の誤り位置に関して解く。未知の位置を見出した後、
プロセッサは既知の位置を有するｖ＋１個の誤りのため
の手順を使用してｖ＋１個の誤りを訂正する。■の値は
１或は２の何れかであり得る。システムが特定の列内の
誤りの記号の正確な位置を知らず、誤りがＣＲＣコード
によって指示される残りの位置の１つの中にあることだ
けを知っているので、単一の誤りの位置は未知である。
ある列に対応付けられた残りは、誤りの記号を含むある
列内の全ての記号の線形組合せである。
即ち、例えば既知の位置を有する２つの誤り及び未知の
位置を有する単一の誤りのための方程式はＲＥＭ：ｔ＝
Ｙ（ＥＶＩ）＊Ｘ３”　＋Ｙ（Ｅｖｚ）＊Ｘｏ”＋Ｙ（
Ｅｕ）＊Ｘ３”ＲＥＭＺ＝Ｙ（Ｅｖｌ）＊ＸＺ”　＋Ｙ
（Ｅｖｔ：）＊Ｘ２ｖ２＋Ｙ（Ｅｕ）＊ＸＺ。
ＲＥＭ＋　＝Ｙ（Ｅｖｌ）＊ＸＩ”　＋Ｙ（Ｅｖｚ）＊
ＸＩ”＋Ｙ（Ｅｕ）＊Ｘ＋ＵＲＥＭｏ＝Ｙ（Ｅｖｌ）＊
Ｘｏ”　＋Ｙ（Ｅｖｚ）＊Ｘｏ”　＋Ｙ（Ｅｕ）＊Ｘｏ
”である。但し、Ｙ（Ｐｉ）は位置ｉにおける誤りに対
応付けられた誤り値（スカラー）であり、Ｘｌ゛は行列
Ｍ（第２図）のけ１０３番目の要素である。
これらの式は Ｘ：１ＬＩ−（１／Ｙ（Ｅｕ））　”ＲＥＭ、＋　（Ｙ
（Ｅｖｌ）／Ｙ（Ｅｕ））　”Ｘｌ”＋　（Ｙ（Ｅｖｚ
）／Ｙ（Ｅｕ）　〕”Ｘ３”Ｘｚ”＝　（１／Ｙ（Ｅｕ
））　”ＲＥＭｚ＋　（Ｙ（Ｅｖｌ）／Ｙ（Ｅｕ）：］
　”Ｘｚ”＋　（Ｙ（Ｅｖｚ）／Ｙ（Ｅｕ）　）　”Ｘ
Ｚ”Ｌ”＝　（１／Ｙ（Ｅｕ）　）　”ＲＥＭ＋＋　（
Ｙ（Ｅｖｔ）／Ｙ（Ｅｕ）　）　”Ｘｌ”＋　（Ｙ（Ｅ
ｖｚ）／Ｙ（Ｅｕ）　）　”Ｌｖ２Ｘｏ’　（１／Ｙ（
Ｅｕ））　”ＲＥＭｏ＋　（Ｙ（Ｅｖｌ）／Ｙ（Ｅｕ）
）　”Ｘ。”＋　（Ｙ（Ｅｖｚ）／Ｙ（Ｅｕ））　”Ｘ
Ｉ、”或はより一般的に Ｘ’−Ａ、”ＲＥＭｃ＋Ａｉ　　”Ｘ”　　十Ａｊ”Ｘ
”と書き直すことができる。但しＡ、はスカラー係数で
ある。即ち、未知の誤り位置に対応するベクトルＸｕは
、（１）列残り記号ベクトルＲＥＭｃ、及び（２）２つ
の既知の誤り位置に対応する行列Ｍの２つの行或はベク
トル、即ち×ｖＩ及びＸＶ２の線形組合せである。
未知の誤り位置を解くために、即ち行列Ｍのどの行或は
ベクトルを残り記号と誤り位置ベクトルとの線形組合せ
として表わし得るかを決定するために、誤り訂正プロセ
ッサは前述の手順に従って行列Ｍ′を公式化する。例と
してｖ＝２とする。
誤り訂正プロセッサは２つの選択された誤り位置と列残
り記号とに対応する３×４行列Ｍ′を公式化する。次で
誤り訂正プロセッサは行演算のみを使用して行列Ｍ′を
、（ｖ＋１）Ｘ　（ｖ十１）恒等行列をその中に含む行
列Ｍ″に圧縮する。行演算のみを使用することによって
、誤り訂正プロセッサは行列の列間の関係を確保し、従
って種々のベクトル間の関係を保存する。
この例においては圧縮された行列Ｍ“は３×３恒等行列
を含む。これは以下の何れかの形をとる。
行列Ｍ′を行列Ｍ″に圧縮する際に遂行される２行演算
は、 （１）　　”ａ”をＧＦ（２’）の任意非０要素とし、
Ｉｌ　ｂ”をＧＦ（２”）の任意要素として、ａｌ（行
ｉ）＋ｂ”（行ｊ〕を行ｉに置換し、 （２）２つの行を交換する である。
次に、誤り訂正プロセッサは、大型行列Ｍ（第図）の行
Ｘｊを、先ず新しい最後の行としてベクトルＸｊを追加
した行列Ｍ″である新行列Ｎを創作することによって行
列Ｍ＃の行の線形組合せとして表わし得るか否かを決定
する。即ち行列Ｎの最後の行は要素ｓ３＝、Ｓ３＋、Ｓ
ｊ＋及びＳｊｏを有する。次で誤り訂正プロセッサは、
含まれている恒等行列が右上角に位置するまで行列Ｎの
列を回転（ｖ＝１）或は入れ替える（ｖ＝２）。即ち行
列Ｎは以下の形である。
誤り訂正プロセッサは次に、入れ替えた行列Ｎの適切な
要素を式 ％式％ に置換することによって、行Ｘｊが行列Ｍ″の行の線形
組合せであるかを検査する。
もし式が満足されれば、Ｘ・は未知の誤り位置である。
そうでない場合には誤り位置プロセ・ンサは、誤りの位
置が見出されるか、または考え得る全ての誤り位置が試
みられてしまうまで、誤りが検出された行列Ｍの行列Ｘ
Ｊ″ｌ　、　Ｘｊ”Ｚ　　−−−Ｘ　ｊ　＋　＋　９に
関して手順を繰り返す。
もし誤り訂正プロセッサが１つの既知の誤り位置だけを
使用して未知の誤り位置を見出そうとすれば（即ちｖ−
１）、回転した行列Ｎの要素が置換されている式は以下
の式の一方である。
ｓｊｔ’　＝ａｔ’　”　Ｓｊｏ’　＋ｂ、’　”　ｓ
ｊｌ’Ｓｊ３’　＝ａｘ”ｓＪ　ｏ　’　十ｂ　３’　
”　ｓ　ｊ、　ｒこの場合冗長方程式が存在し、計算さ
れた誤り位置は適切な行列Ｎ要素を第２式内に置換する
ことによって検査することができる。
データ記号を含む全ての群６（第１図）の列に対して誤
り訂正が試みられた後、誤り訂正プロセッサはＣＲＣコ
ードを使用して再びプロ・ンク５〜２０内の残りの誤り
の存否を調べる。せし全ての誤りが訂正されていれば、
プロセッサは誤りのないデータを要求した利用者に転送
する。もし全ての誤りが訂正されていなければ、プロセ
・ンサは、もし可能であれば、残りの誤りの数及び位置
に対して適切な誤り訂正手順を使用してそれらを訂正す
る。
もし行列Ｍのどの行も対応付けられた行列Ｍ＃の行の線
形組合せとして表わすことができなければ、特定の列の
誤り訂正は失敗する。そこでシステムはこの列を無視し
、他の列内の誤りの訂正に向う。訂正可能な全ての列を
訂正し終ねと誤り訂正プロセッサはＣＲＣビットを使用
して残りの誤りのためにコードワードを検査し、誤りを
含むコードワードの現在数が誤り訂正前の誤りを含むコ
ードワード数よりも少ない場合に限って誤り訂正が続行
される。そうでない場合にはプロセッサはデータ訂正不
能のラベルを付ける。
５或はそれ以上の誤りを訂正する変形方法は、先ず誤り
訂正プロセッサが未知の位置を有する単一の誤りを訂正
する手順を使用して単一の誤りを含む列を訂正し、次で
誤りの数及び位置のために設計された手順を使用して何
れかの残りの誤りを訂正する。多分、単一の誤りを有す
る列を訂正することによって、残りの誤りを含むコード
ワードの数は４或はそれ以下に減少する。それ故、既知
の位置を有する誤りを訂正する手順の１つを、誤り訂正
を完了させるために使用できることになる。
特定の列内の単一の誤りを訂正するために、システムは
先ず列残り記号を調べる。もし全ての残り記号がＯであ
ればその列に誤りは存在せず、誤り訂正は必要としない
。もし残り記号の１つ、例えばＲＥＭ、だけが非０であ
れば誤りは列位置３内にあり、残り記号は対応付けられ
た誤り値である。もし残り記号の２つ、ＲＥＭ、及びＲ
ＥＭ。
だけが非Ｏであれば、それはその特定の列が１つではな
く２つの誤りを含むことを意味する。これら２つの誤り
は残りの記号に対応する位置、即ち列位置ｌ及び３内に
あり、これらの残り記号は誤り値に対応する。
もし２より多い残りの行列が非０であれば、プロセッサ
はこれらの残りの記号を循環シック４０（第４図）のレ
ジスタ４４．４６．４８及び５０にロードし、レジスタ
５０内の記号が非Ｏとなりレジスタ４４．４６．４８内
の記号が全てＯとなるまでシックをクロックする。もし
シックがこの結果を得るまでにに回クロックされれば、
位置に＋３内の列記号が誤りであり、レジスタ５０内の
記号はその記号に対応付けられた誤り値である。
ｂサイクルの後、もし誤り位置が見出されなければ、そ
れはその列が１より多い誤りを含んでいないことを意味
する。プロセッサはこの列を無視して次の列へ進む。プ
ロセッサは各列毎にこの単一誤り訂正手順を遂行し、次
でＣＲＣコードを使用して群６（第１図）内に何等かの
残りの誤りが無いか否かを検査する。もしデータ記号を
含むコードワード内に誤りが乗っていれば、システムは
適切な別の手順を使用してそれらを訂正する。
循環シフタ４０は未知の位置にある二重誤りを訂正する
ためにも使用できる。しかし、シフタがロードされる前
に、列残り記号が前述のように調べられ１つ或は２つの
残り記号だけが非Ｏであるのか否かが決定される。もし
そうであれば、これらの誤りは非０の残り記号に対応す
る位置に位置しており、残り記号はこれらの位置にある
記号に対応する誤り値である。
もし２より多い残りの記号が非Ｏであれば、誤り訂正プ
ロセッサは残りの記号を循環シフタ４０のレジスタ４４
．４６．４８．５０内ヘロードする。次で誤り訂正プロ
セッサはレジスタの内容を調べてレジスタ４６．４８及
び５０内の記号が大型行列Ｍ（第３図）の行列ｘｊの最
後の３要素、即ち要素３ｊｓ、Ｓｊｚ　、Ｓｊ＋に比例
するか否かを決定する。即ち誤り訂正プロセッサは ＲＥＶ３　＝Ｕｊ”　３ｊ３ ＲＥＭｚ　　＝Ｕｊ”　Ｓｊｚ ＲＥＭＩ　　＝Ｕｊ”　Ｓｊ＋ であるか否かを決定する。
もしこれらの条件が特定の行Ｘｊに対して満足されれば
、誤りは位置０及び位置０＋ｊにあり、対応する誤り値
はそれぞれＵｊ”ｓｊｏ＋ＲＥＭ。及びＵｊである。も
しこれらの条件が行列Ｍのどの行に対しても満足されな
ければ、誤り訂正プロセッサは循環シフタ４０をクロッ
クしてレジスタ４４．４６．４８．５０内に新しい残り
の記号ＲＥＭｏ’ＲＥＶ、’　、ＲＥＶ、’及びＲＥＶ
３’を発生させる。次でプロセッサはこれらの新しい残
りの記号が上述の条件を満足するか否かを決定する。こ
の手順は、必要ならば各潜在的誤り位置毎に１回、計１
９回繰り返される。
充分に設計されたシステムにおいて群６（第１図）が４
より多い誤りのブロックを含みそうにないことは当業者
には理解されよう。従って５以上のコードワードのため
の誤り訂正手順が使用されることは殆んど無い。従って
誤りを有する４コードワードまでを訂正する手順を含み
且つ誤りを有する５以上のコードワードを含む群に訂正
不能のラベルを付けるシステムが、システム性能を重大
に劣化させることはない。
上述した誤り訂正コード及び誤り訂正手順は磁気テープ
上の検出不可能及び訂正不可能の両方或は何れか一方の
誤りの数を、磁気ディスク上に記録されたデータを用い
て達成されるレベルに比肩し得るレベルまで減少させる
。誤り検出のためにデータを符号化するのに使用される
パワフルなＣＲＣコードは従来のＣＲＣコードよりも長
いバースト誤りを検出する。従って、テープにおいては
最も一般的な型の誤りの１つであるこれらの誤りはより
正確に検出される。
ＣＲＣコードのパワフルな検出能力と既知の位置を有す
る誤りを迅速に訂正するリード・ソロモンコードとを組
合わせることによって高速誤り訂正方式がもたらされる
。従ってデータの転送率は高い。特別なリード・ソロモ
ンコードは既知の位置を有する単一の（列）誤りを訂正
するのに特に適している。単一の誤り訂正は、誤り訂正
プロセッサが、先ずどの列が誤りを含むかを決定するの
ではなく各列を訂正することを試みるために高速である
。従って誤りの長さ、即ちバースト長はプロセッサが誤
りを訂正するために要する時間に影響を与えることなく
、長バースト誤りはより短かい誤りと同様に迅速に訂正
される。
以上の説明は本発明の種々の実施例に限られていた。し
かし本発明の若干のまたは全ての長所を取入れて本発明
に更なる変化及び変形を施し得ることは明白であろう。
従って特許請求の範囲はこれら全ての変化及び変形を本
発明の範囲内に含めるようにカバーすることである。
【図面の簡単な説明】
第１図は好ましい実施例に従って記録された磁気テープ
の図であり、 第２図はリード・ソロモンコードエンコーダを示し、 第３図は誤り訂正に使用される行列Ｍを示し第４図は循
環シフタを示し、 第５図は種々の誤りの形態の図である。 ４・・・コードワード ６・・・群 １０・・・エンコーダ １１．１２．１３．１４．４１．４２．４３・・・排他
的論理和回路１６．１８．２０．２２．４４．４６．４
８．５０・・・レジスタ２４．２６．２８．３０．５２
．５４．５６．５８・・・乗算器３２・・・スイッチ ４０・・・循環シフタ。 ４＃す 奢憂手 畳参令 ＋手早 乎ナナ 令◆手 ◆令 ■ 手 続 補 正 書 １、事件の表示 平成２年特許願第１ １３０４号 ３、補正をする者 事件との関係 出 願 人 ４、代 理 人 ５、補正命令の日付 自 発 １、明細書第２３頁第１３行と第１８行、”ＣＣＲ”を
ｒｃＲｃＪに訂正する。 ２、明細書第２３頁第２０行“ＣＲ”をｒｃＲｃＪに訂
正する。 １、事件の表示 ２、発明の名称 ３、補正をする者 事件との関係 （方式） ％式％ 長バースト誤りに対する誤り検出 及び訂正システム ４、代

Claims (1)

  1. 【特許請求の範囲】 １、誤りを検出し訂正しつつデータを符号化しそれを磁
    気テープに記録するシステムであって：Ａ、ｄデータ記
    号のストリームを、ジェネレータ多項式ｇ（ｘ）として
    （８進形の） ｇ（ｘ）＝（３）＾＊（３）＾＊（１００００３）＾＊
    （１０２０４３）＾＊（１１００１３）＾＊（１５６０
    ５１３）或は ｇ（ｘ）＝２４１３６０７０３６５６５１７２４３３２
    ２３を有し、これらのベクトル成分が左から右へ最高次
    項から最低次項の係数を表わす多項式の項の２進係数で
    ある周期冗長コードを使用して誤り検出冗長記号を生成
    し、生成された冗長記号をデータ記号に追加して一連の
    ＣＲＣコードワードを形成する第１のエンコーダ；Ｂ、
    誤り訂正コードを使用して所定数ｈのＣＲＣコードワー
    ドからｈデータ記号を符号化し、ｈデータ記号と共に誤
    り訂正コードワードを形成する対応付けられた誤り訂正
    冗長記号を生成する第２のエンコーダ；及び Ｃ、ｈＣＲＣコードワード及び対応付けられた誤り訂正
    冗長記号をテープに記録する記録手段 を具備することを特徴とする符号化及び記録システム。 ２、Ａ、第１のエンコーダは所定数の誤り訂正コードワ
    ード内の対応誤り訂正冗長をも符号化してＣＲＣ冗長記
    号を生成し、ＣＲＣコードワードを形成させ； Ｂ、記録手段は生成されたＣＲＣコードワードをも記録
    する 請求項１記載の符号化及び記録システム。 ３、第２のエンコーダは、αをガロアフィールドの基本
    要素、“＾＊”をガロアフィールド乗算を表わす記号、
    “＋”をガロアフィールド加算を表わす記号とし、ジェ
    ネレータ多項式Ｇ（ｘ）として Ｇ（ｘ）＝（ｘ＋α＾０）＾＊（ｘ＋α＾１）＾＊（ｘ
    ＋α＾２）＾＊（ｘ＋α＾３）＝ｘ＾４＋α＾７＾５ｘ
    ＋α＾２＾４＾９ｘ＾２＋α＾７＾８ｘ＋α＾６を有す
    るリード・ソロモンコードを使用してデータ記号を符号
    化する請求項２記載の符号化及び記録システム。 ４、データを；誤り検出のために周期冗長検査（ＣＲＣ
    ）コードを使用して符号化し、データと共にＣＲＣコー
    ドワードを形成するＣＲＣ冗長ビットを形成させ；また
    誤り訂正のために誤り訂正コードを使用して符号化し、
    データと共に誤り訂正コードワードを形成する誤り訂正
    冗長記号を形成させてデータ内の誤りを訂正する誤り訂
    正表置であって： Ａ、ＣＲＣコードを使用してデータを複号し、データ内
    の誤りの位置を検出するデコーダ；Ｂ、検出された誤り
    の位置に応答し、ｖを所定の最大値ｆより小さい値とし
    てｖ個の検出した誤りに関する誤り値を計算するべく、 １、各誤り訂正コードワード毎に残りを計算する手段、 ２、Ｇ（ｘ）をデータを符号化するために使用する誤り
    訂正コードのジェネレータ多項式と し、Ｙ（ｅ＿ｉ）を位置ｉ内の記号に対応付けられた誤
    り値とし、Ｘ＿ｉ＿ｋをベクトルＸ＾ｉモジュロＧ（ｘ
    ）のｋ番目の項として、式 ΣＸ＿ｉ＿ｋＹ（ｅ＿ｉ）＝ＲＥＭ＿ｋを同時に解くた
    めに、ｉ、非０残りを有する各誤り訂正コードワード毎
    に、 ａ、ｅを検出した誤りの位置としてＸ＾ｅモジュロＧ（
    ｘ）を表わす成分を有するベクトルに対応する要素を有
    し、検出した誤りに対応するｖ行、及び ｂ、コードワード残りに対応する最後の行を有する行列
    Ｍ′を公式化する公式化手段、 ｉｉ、行列Ｍ′の列を操作して、行列の行１−ｖの最初
    のｖ行列の列内にｖ×ｖ恒等行列を有し且つ行列の行１
    −ｖの残り要素として０を有する行列Ｍ″を形成する手
    段、及び ｉｉｉ、検出した誤り位置内の記号に対応付けられた誤
    り値として行列Ｍ″の最後の行の要素を使用することに
    よって誤り値と対応信号とを組合わせる手段を含む手段 を含む誤り訂正手段 を具備することを特徴とする誤り訂正装置。 ５、残りを計算するために、 Ａ、データに対応する新しい誤り訂正コード冗長記号を
    生成する手段； 及び Ｂ、ガロアフィールド加算を使用することによって、新
    しい誤り訂正コード冗長記号をデータ内の誤り訂正コー
    ド冗長記号に加算する手段 を含む請求項４記載の誤り訂正装置。 ６、誤り訂正手段は、行列Ｍ′の行ｖの要素を行列Ｍ′
    の行（ｖ−１）の要素（これらの要素は行１−（ｖ−２
    ）内に０のみを含む行列Ｍ′の列内にある）によって除
    すことによって、データ記号に対応する位置にある誤り
    のみに関する誤り値を計算する手段をも含む請求項５記
    載の誤り訂正装置。 ７、誤り訂正手段は、０に等しい残りを有するコードワ
    ードに誤りなしのラベルを付け、これらのコードワード
    内の記号に対するそれ以上の誤り訂正の遂行を中断せし
    める手段をも含む請求項６記載の誤り訂正装置。 ８、検出した誤りがｆより多い場合に１つの誤りの位置
    を決定する手段をも含み、該手段が：Ａ、検出した位置
    からｖ個所の誤り位置を選択し、選択した位置を選択さ
    れた行に対応する行列Ｍ′を公式化する公式化手段へ供
    給する手段； Ｂ、行列Ｍ′を操作して最初のｖ行内にｖ×ｖ恒等行列
    を有する行列Ｍ″を形成する手段；Ｃ、ｅを選択された
    位置以外の検出した誤りの垂直位置として、ベクトルＸ
    ＾ｅを最後の行として行列Ｍ″に追加して行列Ｎを形成
    する手段； Ｄ、含まれている恒等行列が行列Ｎの右上角に位置する
    まで該行列の列を操作する手段；及び Ｅ、追加された行Ｘ＾ｅが行列Ｍ′の行の線形組合せで
    あるか否かを決定するために、 ｉ、操作した行列Ｎの要素が、 選択した誤り位置の数が１である時には ｓｊ＿２′＝ａ＿２′＾＊ｓｊ＿０′＋ｂ＿２′＾＊ｓ
    ｊ＿１′ｓｊ＿３′＝ａ＿３′＾＊ｓｊ＿０′＋ｂ＿３
    ′＾＊ｓｊ＿１′の条件を、或は 選択した誤り位置の数が２である時には ｓｊ＿３′＝ａ＿３′＾＊ｓｊ＿０′＋ｂ＿３′＾＊ｓ
    ｊ＿１′＋ｂ＿３′＾＊ｓｊ＿２′の条件を満足するか
    否かを決定する手段 を含む手段 を含む請求項７記載の誤り訂正装置。 ９、データ記号のストリームを、ジェネレータ多項式ｇ
    （ｘ）として（８進形の） ｇ（ｘ）＝（３）＾＊（３）＾＊（１００００３）＾＊
    （１０２０４３）＾＊（１１００１３）＾＊（１５６０
    ５１３）或は ｇ（ｘ）＝２４１３６０７０３６５６５１７２４３３２
    ２３を有し、これらのベクトル成分が左から右へ最高次
    項から最低次項の係数を表わす多項式の項の２進係数で
    ある周期冗長コードを使用して符号化し、誤りの検出を
    可能ならしめる方法。 １０、データを符号化しそれを磁気テープに記録する方
    法であって： Ａ、ｄデータ記号のストリームを、ジェネレータ多項式
    ｇ（ｘ）として（８進形の） ｇ（ｘ）＝（３）＾＊（３）＾＊（１００００３）＾＊
    （１０２０４３）＾＊（１１００１３）＾＊（１５６０
    ５１３）或は ｇ（ｘ）＝２４１３６０７０３６５６５１７２４３３２
    ２３を有し、これらのベクトル成分が左から右へ最高次
    項から最低次項の係数を表わす多項式の項の２進係数で
    ある周期冗長コードを使用して誤り冗長記号を生成し、
    生成された冗長記号をデータ記号に追加して一連のＣＲ
    Ｃコードワードを形成し； Ｂ、誤り訂正コードを使用して所定数ｈのＣＲＣコード
    ワードからｈデータ記号を符号化し、データ記号と共に
    誤り訂正コードワードを形成する対応誤り訂正冗長記号
    を生成し；Ｃ、ｈＣＲＣコードワード及び対応付けられ
    た誤り訂正冗長記号をテープに記録する 諸段階を含む方法。 １１、誤り検出符号化段階及び記録段階が：Ａ、所定数
    の誤り訂正コードワード内の対応誤り訂正冗長記号を符
    号化してＣＲＣ冗長記号を生成し、ＣＲＣコードワード
    を形成させ；Ｂ、生成されたＣＲＣコードワードを記録
    する段階を含む請求項１０記載の符号化及び記録方法。 １２、αをガロアフィールドの基本要素、“＾＊”をガ
    ロアフィールド乗算を表わす記号、“＋”をガロアフィ
    ールド加算を表わす記号とし、ジェネレータ多項式Ｇ（
    ｘ）としてＧ（ｘ）＝（ｘ＋α゜）＾＊（ｘ＋α＾１）
    ＾＊（ｘ＋α＾２）＾＊（ｘ＋α＾３）＝ｘ＾４＋α＾
    ７＾５ｘ＾３＋α＾２＾４＾９ｘ＾２＋α＾７＾８ｘ＋
    α＾６を有するリード・ソロモンコードを使用してデー
    タ記号を符号化する段階をも含む請求項１１記載の符号
    化及び記録方法。 １３、データを；誤り検出のためにＣＲＣコードを使用
    して符号化し、データと共にＣＲＣコードワードを形成
    するＣＲＣ冗長コードビットを形成させ；また誤り訂正
    のために誤り訂正コードを使用して符号化し、データと
    共に誤り訂正コードワードを形成する誤り訂正冗長記号
    を形成させてデータ内の誤りを訂正する方法であって：
    Ａ、ＣＲＣコードを使用してデータを復号し、データ内
    の誤りの位置を検出し； Ｂ、ｖを所定の最大値ｆより小さい値としてｖ個の誤り
    だけが検出されることを条件として：１、各誤り訂正コ
    ードワード毎に残りを計算し、 ２、Ｇ（ｘ）をデータを符号化するために使用する誤り
    訂正コードのジェネレータ多項式と し、Ｙ（ｅ＿ｉ）を位置ｉ内の記号に対応付けられた誤
    り値とし、Ｘ＿ｉ＿ｋをベクトルＸ＾ｉモジュロＧ（ｘ
    ）のｋ番目の項として、式 ΣＸ＿ｉ＿ｋＹ（ｅ＿ｉ）＝ＲＥＭ＿ｋを同時に解くた
    めに、ｉ、非０残りを有する各誤り訂正コードワード毎
    に、 ａ、ｅを検出した誤りの位置としてＸ＾ｅモジュロＧ（
    ｘ）を表わす成分を有するベクトルに対応する要素を有
    し、検出した誤りに対応するｖ行、及び ｂ、コードワード残りに対応する最後の行を有する行列
    Ｍ′を公式化し、 ｉｉ、行列Ｍ′の列を操作して、行列の行１−ｖの最初
    のｖ行列の列内にｖ×ｖ恒等行列を有し且つ行列の行１
    −ｖの残り要素として０を有する行列Ｍ″を形成させ、 ｉ、検出した誤り位置内の記号に対応付けられた誤り値
    として行列Ｍ″の最後の行の要素を使用することによっ
    て誤り値と対応信号とを組合わせる諸段階を含む 諸段階を含み、検出した位置内の誤りを訂正する諸段階
    を含む方法。 １４、残りを計算する段階が： Ａ、データに対応する新しい誤り訂正コード冗長記号を
    生成し； Ｂ、ガロアフィールド加算を使用することによって、新
    しい誤り訂正コード冗長記号をデータ内の誤り訂正コー
    ド冗長記号に加算する 諸段階を含む請求項１３記載の誤りを訂正する方法。 １５、行列Ｍ′の行の要素を行列Ｍ′の行（ｖ−１）の
    要素（これらの要素は行１−（ｖ−２）内に０のみを含
    む行列Ｍ′の列内にある）によって除すことによって、
    データ記号に対応する位置にある誤りのみに関する誤り
    値を計算する段階を含む請求項１４記載の誤りを訂正す
    る方法。 １６、０に等しい残りを有するコードワードに誤りなし
    のラベルを付け、これらのコードワード内の記号に対す
    るそれ以上の誤り訂正の遂行を中断せしめる段階をも含
    む請求項１５記載の誤り訂正する方法。 １７、検出した誤りがｆより多い場合に１つの誤りの位
    置を決定するために： Ａ、検出した位置からｖ個所の誤り位置を選択し、選択
    した位置を選択された行に対応する行列Ｍ′を公式化す
    る公式化手段へ供給し；Ｂ、行列Ｍ′を操作して最初の
    ｖ行内にｖ×ｖ恒等行列を有する行列Ｍ″を形成し； Ｃ、ｅを選択された位置以外の検出した誤りの垂直位置
    として、ベクトルＸ＾ｅを最後の行として行列Ｍ″に追
    加して行列Ｎを形成し； Ｄ、含まれている恒等行列が行列Ｎの右上角に位置する
    まで該行列の列を操作し； Ｅ、追加された行Ｘ＾ｅが行列Ｍ′の行の線形組合せで
    あるか否かを操作した行列Ｎの要素がもし選択した誤り
    位置の数が１であれば ｓｊ＿２′＝ａ＿２′＾＊ｓｊ＿０′＋ｂ＿２′＾＊ｓ
    ｊ＿１′ｓｊ＿３′＝ａ＿３′＾＊ｓｊ＿０′＋ｂ＿３
    ′＾＊ｓｊ＿１′の条件を、或は もし選択した誤り位置の数が２であれば ｓｊ＿３′＝ａ＿３′＾＊ｓｊ＿０′＋ｂ＿３′＾＊ｓ
    ｊ＿１′＋ｂ＿３′＾＊ｓｊ＿２′の条件を満足するか
    否かを決定する 諸段階をも含む請求項１６記載の誤りを訂正する方法。 １８、データ記号のストリームを、ジェネレータ多項式
    ｇ＾＊（ｘ）として（８進形の）ｇ＾＊（ｘ）＝（３）
    ＾＊（３）＾＊（１４０００１）＾＊（１１４２０４１
    ）＾＊（１５００１１）＾＊（１５１２０７３）或は ｇ＾＊（ｘ）＝３１１３３０５３６２５６５７０３４１
    ７２０５を有し、これらのベクトル成分が左から右へ最
    高次項から最低次項の係数を表わす多項式の項の２進係
    数である周期冗長コードを使用して符号化するエンコー
    ダを含み、誤りの検出を可能ならしめたデータ符号化シ
    ステム。 １９、データ記号のストリームを、ジェネレータ多項式
    ｇ＾＊（ｘ）として（８進形の）ｇ＾＊（ｘ）＝（３）
    ＾＊（３）＾＊（１４０００１）＾＊（１１４２０４１
    ）＾＊（１５００１１）＾＊（１５１２０７３）或は ｇ＾＊（ｘ）＝３１１３３０５３６２５６５７０３４１
    ７２０５を有し、これらのベクトル成分が左から右へ最
    高次項から最低次項の係数を表わす多項式の項の２進係
    数である周期冗長コードを使用して符号化することによ
    って誤りの検出を可能ならしめた符号化方法。
JP2171304A 1989-06-28 1990-06-28 長バースト誤りに対する誤り検出及び訂正システム Pending JPH03136524A (ja)

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
US373323 1989-06-28
US07/373,323 US5136592A (en) 1989-06-28 1989-06-28 Error detection and correction system for long burst errors

Publications (1)

Publication Number Publication Date
JPH03136524A true JPH03136524A (ja) 1991-06-11

Family

ID=23471910

Family Applications (1)

Application Number Title Priority Date Filing Date
JP2171304A Pending JPH03136524A (ja) 1989-06-28 1990-06-28 長バースト誤りに対する誤り検出及び訂正システム

Country Status (4)

Country Link
US (1) US5136592A (ja)
EP (1) EP0407101A3 (ja)
JP (1) JPH03136524A (ja)
CA (1) CA2016847A1 (ja)

Families Citing this family (110)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP2591242B2 (ja) * 1990-04-02 1997-03-19 松下電器産業株式会社 誤り検出方法
NL9101376A (nl) * 1990-08-16 1992-03-16 Digital Equipment Corp Een verbeterd foutendetectie-codeerstelsel.
US5280488A (en) * 1990-11-08 1994-01-18 Neal Glover Reed-Solomon code system employing k-bit serial techniques for encoding and burst error trapping
US5210760A (en) * 1991-02-15 1993-05-11 International Business Machines Corporation Optimized pointer control system
JP2554219B2 (ja) * 1991-11-26 1996-11-13 日本電信電話株式会社 ディジタル信号の重畳伝送方式
US5375127A (en) * 1992-03-25 1994-12-20 Ncr Corporation Method and apparatus for generating Reed-Soloman error correcting code across multiple word boundaries
EP0582748B1 (en) * 1992-07-14 1997-03-05 ALCATEL BELL Naamloze Vennootschap Divider device to divide a first polynomial by a second one
DE69327212T2 (de) * 1992-09-14 2000-07-27 Ntt Mobile Communications Network Inc., Tokio/Tokyo System für Übertragung von Informationsbitfolgen
US5446745A (en) * 1992-10-05 1995-08-29 Mitsubishi Semiconductor America, Inc. Apparatus for correcting errors in optical disks
JP2821324B2 (ja) * 1992-11-04 1998-11-05 三菱電機株式会社 誤り訂正回路
FI940322L (fi) * 1993-01-25 1994-07-26 Hughes Aircraft Co Parannettu virheen korjaava dekooderi ja menetelmä vastaanottajille digitaalisissa solukkokommunikaatiojärjestelmissä
US5463642A (en) * 1993-06-29 1995-10-31 Mitsubishi Semiconductor America, Inc. Method and apparatus for determining error location
US5465260A (en) * 1993-11-04 1995-11-07 Cirrus Logic, Inc. Dual purpose cyclic redundancy check
US5602857A (en) * 1993-09-21 1997-02-11 Cirrus Logic, Inc. Error correction method and apparatus
US5629949A (en) * 1993-09-21 1997-05-13 Cirrus Logic, Inc. Error correction verification method and apparatus using CRC check remainders
US6125469A (en) * 1994-10-18 2000-09-26 Cirrus Logic, Inc. Error correction method and apparatus
US5864440A (en) * 1994-12-27 1999-01-26 International Business Machines Corporation Data processing method and data storage system
FR2740280B1 (fr) * 1995-10-20 1997-11-21 Cga Hbs Systeme permettant un decodage correct, sous forme d'un message binaire, d'un code magnetique enregistre sur une piste magnetique
US5828513A (en) * 1995-12-07 1998-10-27 International Business Machines Corporation Servo address apparatus and positioning methods for read, write and seek operations in a direct access storage device
US5721744A (en) * 1996-02-20 1998-02-24 Sharp Microelectronics Technology, Inc. System and method for correcting burst errors in digital information
US5787094A (en) * 1996-06-06 1998-07-28 International Business Machines Corporation Test and diagnostics for a self-timed parallel interface
WO1997048097A1 (en) * 1996-06-13 1997-12-18 Philips Electronics N.V. A method and apparatus for trackwise burst error correction in a multitrack storage format
JP3249405B2 (ja) * 1996-09-30 2002-01-21 株式会社東芝 誤り訂正回路および誤り訂正方法
GB2324445B (en) * 1997-04-17 2002-08-21 United Microelectronics Corp Error correction and detection system for mass storage controller
US6081918A (en) * 1997-11-06 2000-06-27 Spielman; Daniel A. Loss resilient code with cascading series of redundant layers
US6092231A (en) * 1998-06-12 2000-07-18 Qlogic Corporation Circuit and method for rapid checking of error correction codes using cyclic redundancy check
US6307487B1 (en) 1998-09-23 2001-10-23 Digital Fountain, Inc. Information additive code generator and decoder for communication systems
US7068729B2 (en) 2001-12-21 2006-06-27 Digital Fountain, Inc. Multi-stage code generator and decoder for communication systems
JP4071879B2 (ja) * 1998-12-09 2008-04-02 富士通株式会社 誤り検出器、この誤り検出器を備えた通信システム、および誤り検出方法
US6681203B1 (en) * 1999-02-26 2004-01-20 Lucent Technologies Inc. Coupled error code protection for multi-mode vocoders
US6331978B1 (en) * 1999-03-09 2001-12-18 Nokia Telecommunications, Oy Generic label encapsulation protocol for carrying label switched packets over serial links
US7277388B1 (en) 2000-03-31 2007-10-02 Nokia Corporation Method and apparatus for random packet marking for differentiated services
US6701336B1 (en) * 1999-11-12 2004-03-02 Maxtor Corporation Shared galois field multiplier
EP1146650A1 (en) 2000-04-10 2001-10-17 Hewlett-Packard Company, A Delaware Corporation Error detection for data storage and transmission
EP1146651A1 (en) * 2000-04-10 2001-10-17 Hewlett-Packard Company Error detection for data storage and transmission
US6477777B1 (en) 2000-06-29 2002-11-12 Joseph A. Oliveri Gravity knife and backbone
US6772390B2 (en) 2000-11-30 2004-08-03 Quantum Corporation Erasure correction for ECC entities
US6836869B1 (en) 2001-02-02 2004-12-28 Cradle Technologies, Inc. Combined cyclic redundancy check (CRC) and Reed-Solomon (RS) error checking unit
US6868517B1 (en) * 2001-05-15 2005-03-15 Marvell International Ltd. Method and apparatus for checking read errors with two cyclic redundancy check stages
US20020199153A1 (en) * 2001-06-22 2002-12-26 Fall Thomas G. Sampling method for use with bursty communication channels
US6986092B2 (en) 2001-12-04 2006-01-10 Qualcomm Inc. Erasure-and-single-error correction decoder for linear block codes
US7111228B1 (en) 2002-05-07 2006-09-19 Marvell International Ltd. System and method for performing parity checks in disk storage system
US9240810B2 (en) 2002-06-11 2016-01-19 Digital Fountain, Inc. Systems and processes for decoding chain reaction codes through inactivation
EP1552617A2 (en) 2002-10-05 2005-07-13 Digital Fountain, Inc. Systematic encoding and decoding of chain reaction codes
US7007114B1 (en) 2003-01-31 2006-02-28 Qlogic Corporation System and method for padding data blocks and/or removing padding from data blocks in storage controllers
US7287102B1 (en) 2003-01-31 2007-10-23 Marvell International Ltd. System and method for concatenating data
US7181677B1 (en) * 2003-02-10 2007-02-20 Maxtor Corporation System and method for producing data and ECC code words using a high rate restricted-symbol code
US7492545B1 (en) 2003-03-10 2009-02-17 Marvell International Ltd. Method and system for automatic time base adjustment for disk drive servo controllers
US7039771B1 (en) 2003-03-10 2006-05-02 Marvell International Ltd. Method and system for supporting multiple external serial port devices using a serial port controller in embedded disk controllers
US7064915B1 (en) 2003-03-10 2006-06-20 Marvell International Ltd. Method and system for collecting servo field data from programmable devices in embedded disk controllers
US7870346B2 (en) 2003-03-10 2011-01-11 Marvell International Ltd. Servo controller interface module for embedded disk controllers
US7080188B2 (en) 2003-03-10 2006-07-18 Marvell International Ltd. Method and system for embedded disk controllers
US7076723B2 (en) 2003-03-14 2006-07-11 Quantum Corporation Error correction codes
US7290197B2 (en) * 2003-06-03 2007-10-30 Quantum Corporation Correcting data using redundancy blocks
CN100361222C (zh) * 2003-09-05 2008-01-09 三洋电机株式会社 纠错码产生电路及其方法
KR101183843B1 (ko) 2003-10-06 2012-09-19 디지털 파운튼, 인크. 단일 송신기 또는 다중 송신기를 갖는 통신 시스템의 에러정정 다중-스테이지 코드 생성기 및 디코더
US7228467B2 (en) * 2003-10-10 2007-06-05 Quantum Corporation Correcting data having more data blocks with errors than redundancy blocks
US7526691B1 (en) 2003-10-15 2009-04-28 Marvell International Ltd. System and method for using TAP controllers
US7139150B2 (en) 2004-02-10 2006-11-21 Marvell International Ltd. Method and system for head position control in embedded disk drive controllers
US7228490B2 (en) * 2004-02-19 2007-06-05 Quantum Corporation Error correction decoder using cells with partial syndrome generation
EP1743431A4 (en) 2004-05-07 2007-05-02 Digital Fountain Inc SYSTEM FOR DOWNLOADING AND RECORDING AND CONTINUOUS READING OF FILES
US7120084B2 (en) 2004-06-14 2006-10-10 Marvell International Ltd. Integrated memory controller
US8166217B2 (en) 2004-06-28 2012-04-24 Marvell International Ltd. System and method for reading and writing data using storage controllers
US7757009B2 (en) 2004-07-19 2010-07-13 Marvell International Ltd. Storage controllers with dynamic WWN storage modules and methods for managing data and connections between a host and a storage device
US8032674B2 (en) * 2004-07-19 2011-10-04 Marvell International Ltd. System and method for controlling buffer memory overflow and underflow conditions in storage controllers
US9201599B2 (en) 2004-07-19 2015-12-01 Marvell International Ltd. System and method for transmitting data in storage controllers
US7386661B2 (en) 2004-10-13 2008-06-10 Marvell International Ltd. Power save module for storage controllers
US7240267B2 (en) 2004-11-08 2007-07-03 Marvell International Ltd. System and method for conducting BIST operations
US7802026B2 (en) * 2004-11-15 2010-09-21 Marvell International Ltd. Method and system for processing frames in storage controllers
US7609468B2 (en) 2005-04-06 2009-10-27 Marvell International Ltd. Method and system for read gate timing control for storage controllers
US7676735B2 (en) 2005-06-10 2010-03-09 Digital Fountain Inc. Forward error-correcting (FEC) coding and streaming
US7590920B2 (en) * 2005-08-05 2009-09-15 Hitachi Global Storage Technologies Netherlands, B.V. Reduced complexity error correction encoding techniques
US7694208B2 (en) * 2005-12-20 2010-04-06 Quantum Corporation Error correction algorithm using interleaved parity check and Reed-Solomon code
KR100734307B1 (ko) 2006-01-23 2007-07-02 삼성전자주식회사 포스트 비터비 에러 정정 방법 및 이에 적합한 장치
KR101292851B1 (ko) 2006-02-13 2013-08-02 디지털 파운튼, 인크. 가변적 ｆｅｃ 오버헤드 및 보호 구간을 이용하는 스트리밍및 버퍼링
US9270414B2 (en) 2006-02-21 2016-02-23 Digital Fountain, Inc. Multiple-field based code generator and decoder for communications systems
US7610519B1 (en) * 2006-03-03 2009-10-27 Xilinx, Inc. Vector generation for codes through symmetry
US7971129B2 (en) 2006-05-10 2011-06-28 Digital Fountain, Inc. Code generator and decoder for communications systems operating using hybrid codes to allow for multiple efficient users of the communications systems
US9178535B2 (en) 2006-06-09 2015-11-03 Digital Fountain, Inc. Dynamic stream interleaving and sub-stream based delivery
US9209934B2 (en) 2006-06-09 2015-12-08 Qualcomm Incorporated Enhanced block-request streaming using cooperative parallel HTTP and forward error correction
US9432433B2 (en) 2006-06-09 2016-08-30 Qualcomm Incorporated Enhanced block-request streaming system using signaling or block creation
US9419749B2 (en) 2009-08-19 2016-08-16 Qualcomm Incorporated Methods and apparatus employing FEC codes with permanent inactivation of symbols for encoding and decoding processes
US9380096B2 (en) 2006-06-09 2016-06-28 Qualcomm Incorporated Enhanced block-request streaming system for handling low-latency streaming
US9386064B2 (en) 2006-06-09 2016-07-05 Qualcomm Incorporated Enhanced block-request streaming using URL templates and construction rules
DE112006003922T5 (de) * 2006-06-28 2009-04-30 Intel Corporation, Santa Clara Modifikation bei einem Meggit-Decodierer für Fehlerkorrekturverfahren bei Bursts
US7937643B1 (en) 2006-09-18 2011-05-03 Mediatek Inc. Mobile communication device and data reception method
KR101221913B1 (ko) * 2006-12-20 2013-01-15 엘지전자 주식회사 디지털 방송 시스템 및 데이터 처리 방법
US7836230B1 (en) * 2007-02-14 2010-11-16 Marvell International Ltd. Managing multiple host requests in queued commands that corresponds to receipt of stored acknowledgement commands from the host
US20080205229A1 (en) * 2007-02-26 2008-08-28 Yung-Chih Li Method of identifying optical disc
TWI332611B (en) * 2007-05-24 2010-11-01 Realtek Semiconductor Corp Method for writing data in flash memory and error correction coding/decoding method thereof
CN101802797B (zh) 2007-09-12 2013-07-17 数字方敦股份有限公司 生成和传达源标识信息以实现可靠的通信
RU2390051C2 (ru) * 2008-07-09 2010-05-20 Государственное образовательное учреждение высшего профессионального образования "Северо-Кавказский государственный технический университет" Устройство спектрального обнаружения и коррекции ошибок в кодах полиномиальной системы классов вычетов
US9281847B2 (en) 2009-02-27 2016-03-08 Qualcomm Incorporated Mobile reception of digital video broadcasting—terrestrial services
US9288010B2 (en) 2009-08-19 2016-03-15 Qualcomm Incorporated Universal file delivery methods for providing unequal error protection and bundled file delivery services
US9917874B2 (en) 2009-09-22 2018-03-13 Qualcomm Incorporated Enhanced block-request streaming using block partitioning or request controls for improved client-side handling
US9626243B2 (en) * 2009-12-11 2017-04-18 Advanced Micro Devices, Inc. Data error correction device and methods thereof
US8339726B2 (en) * 2009-12-22 2012-12-25 Quantum Corporation Unique media identifier
US9225961B2 (en) 2010-05-13 2015-12-29 Qualcomm Incorporated Frame packing for asymmetric stereo video
US9596447B2 (en) 2010-07-21 2017-03-14 Qualcomm Incorporated Providing frame packing type information for video coding
US8806050B2 (en) 2010-08-10 2014-08-12 Qualcomm Incorporated Manifest file updates for network streaming of coded multimedia data
US8958375B2 (en) 2011-02-11 2015-02-17 Qualcomm Incorporated Framing for an improved radio link protocol including FEC
US9270299B2 (en) 2011-02-11 2016-02-23 Qualcomm Incorporated Encoding and decoding using elastic codes with flexible source block mapping
US9253233B2 (en) 2011-08-31 2016-02-02 Qualcomm Incorporated Switch signaling methods providing improved switching between representations for adaptive HTTP streaming
US9843844B2 (en) 2011-10-05 2017-12-12 Qualcomm Incorporated Network streaming of media data
US9294226B2 (en) 2012-03-26 2016-03-22 Qualcomm Incorporated Universal object delivery and template-based file delivery
US10977466B2 (en) * 2015-07-09 2021-04-13 Hewlett-Packard Development Company, L.P. Multi-dimensional cyclic symbols
CN112130749B (zh) 2019-06-25 2023-12-22 慧荣科技股份有限公司 数据储存装置以及非挥发式存储器控制方法
TWI718709B (zh) * 2019-06-25 2021-02-11 慧榮科技股份有限公司 資料儲存裝置以及非揮發式記憶體控制方法
CN112130750B (zh) 2019-06-25 2023-11-07 慧荣科技股份有限公司 数据储存装置以及非挥发式存储器控制方法
CN116954982A (zh) * 2022-04-19 2023-10-27 华为技术有限公司 数据写入方法以及处理系统

Family Cites Families (14)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US4142174A (en) * 1977-08-15 1979-02-27 International Business Machines Corporation High speed decoding of Reed-Solomon codes
JPS5857781B2 (ja) * 1978-01-17 1983-12-21 三菱電機株式会社 符号化復号化方式
US4359772A (en) * 1980-11-14 1982-11-16 International Business Machines Corporation Dual function error correcting system
US4413339A (en) * 1981-06-24 1983-11-01 Digital Equipment Corporation Multiple error detecting and correcting system employing Reed-Solomon codes
JPS6050669A (ja) * 1983-08-29 1985-03-20 Hitachi Ltd デ−タ復調方式
US4653051A (en) * 1983-09-14 1987-03-24 Matsushita Electric Industrial Co., Ltd. Apparatus for detecting and correcting errors on product codes
KR930003997B1 (ko) * 1983-12-20 1993-05-19 소니 가부시끼가이샤 에러 정정부호의 복호방법 및 복호장치
JPS6276825A (ja) * 1985-09-30 1987-04-08 Hitachi Ltd 符号誤り訂正方法
CA1264091A (en) * 1986-01-10 1989-12-27 Yoichiro Sako Generator for error correcting code and decoder for the code
US4763332A (en) * 1987-03-02 1988-08-09 Data Systems Technology Corp. Shared circuitry for the encoding and syndrome generation functions of a Reed-Solomon code
JPS63267018A (ja) * 1987-04-24 1988-11-04 Ricoh Co Ltd ロングデイスタンスコ−ドの誤り訂正方式および誤り訂正装置
US4856003A (en) * 1987-05-07 1989-08-08 Digital Equipment Corporation Error correction code encoder
US4866716A (en) * 1987-05-15 1989-09-12 Digital Equipment Corporation Real-time BCH error correction code decoding mechanism
US4975867A (en) * 1987-06-26 1990-12-04 Digital Equipment Corporation Apparatus for dividing elements of a Galois Field GF (2QM)

Also Published As

Publication number Publication date
CA2016847A1 (en) 1990-12-28
EP0407101A3 (en) 1992-04-08
EP0407101A2 (en) 1991-01-09
US5136592A (en) 1992-08-04

Similar Documents

Publication Publication Date Title
US5136592A (en) Error detection and correction system for long burst errors
US4525838A (en) Multibyte error correcting system involving a two-level code structure
US7404134B2 (en) Encoding/decoding device using a reed-solomon encoder/decoder
KR930008683B1 (ko) 리드-솔로몬 에러 보정 코드 엔코더
US4504948A (en) Syndrome processing unit for multibyte error correcting systems
EP0114938A2 (en) On-the-fly multibyte error correction
US5856987A (en) Encoder and decoder for an SEC-DED-S4ED rotational code
CN101814922B (zh) 基于bch码的多位错纠错方法和装置以及存储系统
JPH01155721A (ja) エラー訂正方法
EP0233075B1 (en) Method and apparatus for generating error detection check bytes for a data record
JP2011514743A (ja) 受信したシンボル列におけるフェーズドバーストエラー、消失、シンボルエラー、及び、ビットエラーを検出及び訂正するための方法及びシステム
WO1999009694A2 (en) Reed-solomon decoder and vlsi implementation thereof
JPH02189032A (ja) エラー訂正方法
JPH0736717A (ja) 単一記号エラーと単一ビット・エラー検出のためのエラー訂正方法及び装置
US7093183B2 (en) Symbol level error correction codes which protect against memory chip and bus line failures
US5107506A (en) Error trapping decoding method and apparatus
EP1102406A2 (en) Apparatus and method for decoding digital data
US20260050514A1 (en) Low Complexity System and Method for Detection and Correction of Data with additional Metadata from Corruption
US6643819B1 (en) Hybrid root-finding technique
Wolf An introduction to tensor product codes and applications to digital storage systems
US7461329B2 (en) Channel encoding adapted to error bursts
EP0341851A2 (en) Method and apparatus for interleaved encoding
Tang et al. Coding for error control
CA1082815A (en) Table lookup direct decoder for double-error- correcting (dec) bch codes using general pair of syndromes
Al Jabri et al. Array Codes with Error Detection For E cient Storage Systems