JPS6343833B2 - - Google Patents

Description

【発明の詳細な説明】

本発明の背景 本発明は磁気テープ記憶システムのような複数
チヤネル並列データ処理システムにおける既知の
誤りチヤネルを検出し訂正する装置に関する。更
に具体的には、本発明は冗長チヤネルの数を増加
させないで、同一記録媒体上に記録された訂正可
能誤りチヤネルの数を増加させることに関する。 磁気テープ記憶システムではテープ・サイズ、
データ形式、記録密度に関して工業規格が定めら
れてきた。例えば、テープ上に９トラツクを記録
するためには、1.27cm幅のテープが使用される。
通常、データはテープ上でビツト並列及びバイト
直列になるように記録される。この記録形式によ
れば、異なつた密度でデータをテープから読取り
又はそこへ書込むために、同一の９トラツク・ヘ
ツドを使用することができる。 磁気テープは柔軟であり可撓性に富む。磁気テ
ープ記憶システムは、例えば剛性磁気デイスクの
ような他の形態の移動型磁気記憶媒体と異なり、
データを転送する時に１個又はそれ以上の固定ヘ
ツドに対してテープの不均一な接触関係で移動さ
せることを必要とする。ヘツドとテープとの間で
遊離した微小な屑、又はテープの酸化物欠損地点
は信号振幅の損失を生じ、１つ又はそれ以上のチ
ヤネルでデータ・エラーを生じる。このような状
況の下では、誤りチヤネルの再生クロツクは他の
チヤネルのデータと同期を失う可能性がある。そ
の結果、テープへのデータの記録又はその読取り
は、非常に長いセグメントにわたつて誤りとなる
かも知れない。この点に関して、テープの雑音長
は一時的雑音又はバースト雑音のいずれとも異な
つたデータ復元問題を生じる。一時的雑音又はバ
ースト雑音によつて誘起されたエラーの特徴は、
それが通常有限の持続時間を有することである。
欠陥データの再生は巡回特性を有する誤り検査コ
ードを使用すれば可能である。このコードは理論
及び使用法において複雑である。 可変密度で記録することができ、かつ誤りの検
出及び訂正のために巡回コードを利用することの
できる磁気テープ記憶システムの例は、
IBM3420モデル４，６，８磁気テープ装置と共
に使用されるIBM3803磁気テープ制御装置であ
る。実際に使用される巡回コードは米国特許第
3868632号に説明されている。 現在のテープ使用上の慣習として、９本のチヤ
ネルより成る一組のチヤネルの中で、７本のチヤ
ネルについての冗長情報は残りの２本のチヤネル
に記録される。この構成によれば、２本までの誤
りチヤネルを訂正することができる。一組のチヤ
ネルに２本の冗長チヤネルが設けられ、二組以上
の論理的に独立した並列チヤネルをテープ上に記
録する場合については、特開昭54−88109号公報
を参照されたい。この公開公報は、１つのチヤネ
ル組における複数本の誤りチヤネルを訂正するた
めに、他のチヤネル組の未使用の冗長度を利用す
る方法及び装置を開示している。９チヤネル・デ
ータ処理システムにおいて誤りの検出及び訂正を
行う先行技術は、米国再発行特許第28923号、米
国特許第3868632号、IBM技術開示公報（IBM
Technical Disclosure Bulletin、Vcl.14、pp38
〜46、May1972）、及びIEEE文献「磁気テープ
のための二重トラツク誤り訂正コード」（Ａ
Double Track Error Correction Code for
Magnetic Tape、IEEE Transactions on
Computers、June 1976、pp642〜645）に示され
ている。 上記米国再発行特許第28923号及び第3868632号
に開示されるコードは、情報を連続的にブロツク
に区分し、巡回パリテイ符号化計画に従つて個々
のブロツクのために検査ビツトを計算することを
必要とする。これら検査ビツトは後で記録され
る。並列チヤネルからデータを復元する場合、各
ブロツクの検査ビツトは、事実上再度計算され比
較されねばならない。そのような巡回コードを使
用する装置は、複雑であり費用がかかる。更に重
要なことは、１つのデータ・ブロツクを復元する
時に得られた検査情報は、次のデータ・ブロツク
を復元する時には捨てられてしまうことである。 上記IEEE文献は、２本の誤りチヤネルを訂正
するために、２本の冗長チヤネル上に記憶された
垂直パリテイ検査符号と単一の対角線パリテイ検
査符号とを使用するコード構成を開示している。
前記IBM技術開示公報は、利用可能なデータへ
モジユーロ２加算された単純パリテイから、利用
不可能なデータに代るデータ値を計算することに
よつて、複数のテープからレコードを復元する方
法を説明している。 本発明の要約 本発明の目的は、巡回訂正又はブロツク解読の
必要なしに、複数チヤネル並列データ処理システ
ム上の誤りチヤネルが検出されて訂正され、記録
されたデータの復元時に得られた検査情報が続い
て復元されるデータの誤りを検出し訂正するため
に使用される装置を提供することである。 本発明の他の目的は、長い（殆んど無限の）誤
りランがあつても３本までの既知の誤りチヤネル
を検出し訂正する装置を提供することである。 本発明の他の目的は、外部ポインタが無い場合
又は外部ポインタを補うために、誤りチヤネルを
指示する内部ポインタを発生する装置を提供する
ことである。 本発明の他の目的は、単一のパリテイ符号を多
様なデータ形式で記録し、検査バイトをデータ・
バイトの中へ選択的に介在させることができる装
置を提供することである。 上記の目的は、少なくとも１本の冗長チヤネル
を有する複数チヤネル・データ処理システムが、
３本までの誤りチヤネルを訂正する装置へ結合さ
れる本発明の実施例によつて達成される。誤りチ
ヤネル訂正装置において、垂直パリテイ検査符号
は第１冗長チヤネルに記録され、所定の正又は負
の傾斜方向で取られた対角線パリテイ検査符号は
一群のフオーマツト（形式）から選択された１つ
のフオーマツトへ記録される。一群のフオーマツ
トは第２及び第３の冗長チヤネルのような非分散
フオーマツト、規則的に間隔をとられたチヤネル
横断バイト位置の対を含む分散フオーマツト、規
則的に間隔をとられたチヤネル横断バイトが冗長
チヤネルと共に使用される混合フオーマツトより
成る。並列チヤネルに記録されたデータを正確に
再生するために、誤りチヤネル訂正装置はパリテ
イ検査符号及びデータからシンドロームを決定す
る。更に具体的に云えば、誤りチヤネル訂正装置
はパリテイ検査符号及びデータから対角線シンド
ローム及び垂直シンドロームの両者を決定する。
誤りの検出は２つのシンドロームが既知の誤りチ
ヤネルにおいて同一の誤り個所で交差したことに
基づいてなされる。訂正は誤り乃至訂正信号を元
のチヤネル・データと論理的に結合することによ
つてなされる。この場合、２つの交差シンドロー
ムの１つは対角線シンドロームでなければならな
い。訂正信号を発生する場合、２つの対角線シン
ドロームから既知の誤りチヤネルに近いシンドロ
ームを選択する手段が設けられる。 本発明において、既知のチヤネルで誤りが検出
された時、その誤り個所を対角線的に横切るシン
ドロームのパリテイを反転することによつて、シ
ンドロームの連続的な修正がなされる。従つて、
残りの対角線シンドロームは未だ訂正されない新
しい誤りによつてのみ影響を受けている。 本発明の１つの局面として、誤りチヤネルを指
示する内部ポインタは、外部ポインタの不在の場
合又は外部ポインタの補助として、対角線シンド
ローム及び垂直シンドロームから発生される。内
部ポインタの発生は、専用のカウンタを使用し、
対角線シンドローム及び垂直シンドロームにおけ
るパリテイ検査符号の不一致に基づくビツト位置
の差の関数としてカウンタ値を修正することによ
つてなされる。誤り個所を横切る対角線シンドロ
ームと垂直シンドロームとのパリテイ検査符号の
不一致は、カウンタの初期値及びそれが変更され
る方向を決定する。対角線シンドロームと垂直シ
ンドロームとの次の不一致は、何時カウンタが停
止するかを決定する。ポインタそれ自体は、第１
のシンドローム不一致と第２のシンドローム不一
致との間に存在するチヤネル内ビツト位置のカウ
ント差である。遠い対角線シンドロームと垂直シ
ンドロームとの間の不一致はカウンタを増加さ
せ、近い対角線シンドロームと垂直シンドローム
との間の不一致はカウンタを減少させる。唯一の
例外は垂直パリテイ符号を記録するチヤネルに誤
りが生じる場合がある。この場合、２つの対角線
シンドロームは一致し、垂直シンドロームは不一
致を示す。 実施例の説明 第１図を参照すると、そこには本発明を組込ん
だ複数チヤネル並列データ記憶システムの既略ブ
ロツク図が示される。情報源１からの情報はバツ
フア付き制御装置３へ印加される。制御装置３は
データを形式化し、必要なパリテイ符号化を行な
い、形式化されパリテイ符号化されたデータを記
憶ユニツト５の並列チヤネル上に記録せしめる。
バツフア付き制御装置７は上記並列チヤネル上に
記録されたデータを読取り、それを利用装置１１
へ与えるために再形式化し解読する。 動作的には、制御装置３の情報は並列形式で通
路２を介してパリテイ検査符号器９へ送られる。
符号器９では、パリテイ検査ビツトがバイトと呼
ばれる情報信号の組について逐次に発生される。
パリテイ検査ビツトが情報信号と共に記録された
後、これらの双方を記憶ユニツト５から読出し、
２つのシンドローム及びポインタを利用して訂正
信号を誘導し、訂正信号と読出し情報とを結合す
ることによつて、情報中のパリテイ検出された誤
りを変更することができる。シンドローム及び訂
正信号の誘導は解読器１９でなされる。解読器１
９は検査ビツトを用いてシンドロームを誘導す
る。情報（データ）信号をカバーする検査ビツト
は、垂直方向及び正又は負の傾斜を有するチヤネ
ル横断方向に記録されている。 ここで再び第１図を参照すると、解読器１９は
通路２１を介してデータを受取り、通路３３を介
して解読されたデータを戻すように制御装置７と
相互に作用する。第４図は解読器によるシンドロ
ームの発生、その修正、及び訂正信号の発生を示
す論理図である。解読器入力通路２１を介して印
加されたデータは対角線シンドローム発生器２
３、誤りパターン発生器２５、誤り訂正器２７に
よつて処理される。概略的には、並列トラツク上
に誤りを有するデータは、シンドローム発生器２
３へ接続された通路２１の並列線へ印加される。
シンドローム発生器２３の出力は誤りパターン発
生器２５へ印加される。単一チヤネル（ｉ＝ｊ）
を訂正する場合の訂正信号e_n(i)は、通路２９を介
して誤り訂正器２７へ印加される。２本のチヤネ
ルを訂正する場合には、信号e_n(i)及びe_n(j)が通路
２９及び３５を介して誤り訂正器２７へ印加され
る。連続的なシンドローム修正は、通路６０１を
介して訂正信号をゲート装置２２へフイードバツ
クし、シンドローム発生器２３から誤りパターン
発生器２５へ入力されつつある新しいシンドロー
ム情報と相互に作用させることによつて達成され
る。 ２本のチヤネルを訂正する記録フオーマツト及び
検査ビツト ここで第２Ａ図〜第２Ｃ図を参照すると、そこ
にはテープに沿つて９本の並列チヤネルを記録す
るフオーマツトが示されている。第２Ａ図では、
８本のチヤネル（トラツク）についてパリテイ・
ビツトを記録するためチヤネルＰが設けられてい
る。このようなパリテイ・ビツトは米国特許第
3508194号、同第3508195号、同第3508196号に記
載されるように垂直冗長検査（VRC）ビツトと
して知られている。８ビツト及びVRCビツトよ
り成るバイトB_nは９本のチヤネル上に同時に記
録される。それは米国再発行特許第25527号に開
示されるところに従つて、記録されたチヤネルか
ら読出されバイトへ再編成されてよい。 第２Ａ図において、B_n(k)はｋ番目のチヤネル
に沿つて左から右へ進む場合のｍ番目のビツトを
指すものとする。更に、B_nは磁気テープの如き
記録媒体の並列チヤネル０〜７に記録された８ビ
ツト・バイトを表わすものとする。B_nは次のよ
うに表わすことができる。 B_n＝〔B_n（０），B_n(1)，B_n(2)，…B_n(7)〕 ……(1) ここでｍ＝０〜Ｍ、Ｍ＝8xnである。B_n(8)はチ
ヤネルＰ上に記録されたB_nのバイト・パリテイ
である。即ち、 B_n(8)＝₇ 〓^k=0 B_n(k) ……(2) （総和記号上の円はモジユーロ２合計を示す。） B₀，B₈，B₁₆，B₂₄，……，B_8Nはチエツク・バ
イトである。その各々はその両側にある７個のデ
ータ・バイトについて次のような対角線パリテイ
検査ビツトを与える。 B_n(k)＝_7-k 〓Γ^t=0 B_n-t（ｋ＋ｔ）_k 〓Γ^t=1 B_n+t（ｋ−ｔ）
……(3) レコードの２つの端部においてバイトB_-1，
B_-2，……，B_-7及びバイトB_M+1，B_M+2，……，
B_M+7は存在せず。これらは式(3)の計算ではオー
ル・ゼロと考えられる。パリテイ検査式(2)及び(3)
は次のように書く直すことができる。 ₈ 〓Γ^k=0 B_n(k)＝０ ……(4) ₇ 〓Γ^k=0 B_n-k(k)＝０ ……(5) 読出されたバイトは誤りを有するかも知れな
い。もし式４及び５のパリテイ検査が満足されな
ければ、結果は誤りのシンドロームと呼ばれる。 第２Ｂ図及び第２Ｃ図において、チヤネル（ト
ラツク）０はパリテイ・ビツトのために設けられ
ている。即ち、チヤネル０は正の傾斜方向で取ら
れた対角線パリテイ検査ビツトを記録するために
設けられている。第２Ｄ図において、対角線パリ
テイ検査は負及び正の傾斜方向で行われるように
示される。第２Ｂ図及び第２Ｃ図のフオーマツト
は２トラツクの訂正に用いられ、第２Ｄ図のフオ
ーマツトは３トラツクの訂正に用いられる。 対角線検査ビツトを発生する符号器 ここで第３図を参照すると、そこには第２Ａ図
のフオーマツトで必要とされるパリテイ検査ビツ
トを発生する符号器９が示されている。垂直パリ
テイ検査ビツトは、垂直（チヤネル横断）方向の
チヤネル・ビツト値を単純にモジユーロ２加算す
ることによつて得られる。垂直検査（VRC）の
論理及び装置は、先行技術で詳細に説明されてい
るので（例えば米国再発行特許第28923号を参
照）、これ以上の説明は不必要であろう。従つて、
ここでは対角線パリテイ検査ビツト発生部分のみ
を示す。それは対角線パリテイ検査ビツトを発生
することのできるシフト・レジスタより成る。対
角線パリテイ検査ビツトは後に第２Ａ図のフオー
マツトを満足させるために、制御装置３によつて
トラツク横断バイト位置B₀，B₈，B₁₆，……，
B_8Nに記録される。垂直パリテイ検査ビツトはチ
ヤネル８（トラツクＰ）に記録される。符号器９
の対角線パリテイ検査ビツト発生部分は、７段フ
リツプ・フロツプ（FF１，FF２，……FF６，
FF７）を含むシフト・レジスタより成る。各シ
フト・レジスタ段の間には、複数入力単一出力の
排他的OR（XOR）ゲートが介在している。XOR
ゲート１９５，１９７，１９９，２０１，２０
３，２０５の各々は１つのレジスタ段を他のレジ
スタ段へ（例えばFF２をFF３へ）接続する他
に、チヤネル組のチヤネルを対角線的に横断する
ように配置されたビツトへ接続された入力を有す
る。XORゲート１９３はB_n+i（０）の終端であ
り、XORゲート２０５は位置B_n+i(6)からビツト
を受取る。位置B_n+i(7)からのビツト値は段FF７
を直接に駆動する。 このシフト・レジスタ構成は式(3)及び(5)に従つ
て動作する。φはオール・ゼロ・バイトである。 φバイト及びデータ・バイトが図示された順序
で入れられるにつれて、検査バイトB₀，B₈，B₁₆
……の各ビツトが連続的なシフト及び入力処理に
よつて出力６に発生される。即ち、先ず検査バイ
トB₀が発生され、次にB₈が発生され、以下同様
にして全ての検査バイトが発生される。これは
B_nを発生するためには（ｍ＝０，８，16，24，
……）、φ，B_n+1，B_n+2，……，B_n+7のバイトを
この順序でシフト・レジスタへ入れる必要がある
ことを意味する。B_n+iが入れられる時、B_nのｉ
番目のビツトが符号器９の出力６に発生される。
これまでのところ、垂直パリテイ検査及び対角線
パリテイ検査の組合せは、２本までの誤りチヤネ
ルを訂正することができる。ここでは正傾斜の対
角線パリテイ検査ビツトを発生する場合のみを説
明するので、負傾斜の対角線パリテイ検査ビツト
の発生については前記公開公報を参照されたい。 ３チヤネルを訂正する場合の記録フオーマツト及
び検査 第２Ｄ図を参照すると、そこにはＴ本のチヤネ
ルのうち３本までの既知の誤りチヤネルを訂正す
ることのできるフオーマツトが示される。後述す
るように、これは３本の検査チヤネルの外に、単
に２（Ｔ−１）個の追加的な検査ビツトを必要と
するのみである。 第２Ｄ図に示されるフオーマツトにおいて、
Z_n（ｔ）はｔ番目のチヤネルに沿つたｍ番目のビ
ツトを示すものとする。０からＴ＋１までの番号
を付けられた（Ｔ＋２）本のトラツクが存在す
る。ビツト位置ｍは１からＭまで変化する。０番
目、Ｔ番目、（Ｔ＋１）番目のチヤネルはパリテ
イ検査ビツトを記録するために設けられる。（Ｔ
＋１）番目のチヤネルにある検査ビツトは、残り
の（Ｔ＋１）本のチヤネルにある同一位置ｍのビ
ツトをモジユーロ２合計したものである。この検
査は垂直パリテイ検査と呼ばれる。対応する符号
化式は次の通りである。 Z_n（Ｔ＋１）＝_T 〓Γ^t=0 Z_n（ｔ） ……（Ａ−１） 第２Ｄ図に示されるように、０番目のチヤネル
の各検査ビツトは正傾斜を有する対角線に沿つて
パリテイ検査を与える。同様に、Ｔ番目のチヤネ
ルの各検査ビツトは負傾斜を有する対角線に沿つ
てパリテイ検査を与える。正傾斜を有するｍ番目
の対角線検査はd⁺ _n検査と呼ばれ、次の符号化式
によつて与えられる。 Z_n（０）＝_T 〓Γ^t=1 Z_n-t（ｔ） ……（Ａ−２） 負傾斜を有するｍ番目の対角線検査はd^- _n検査
と呼ばれ、次の符号化式によつて与えられる。 Z_n（Ｔ）＝_T 〓Γ^t=1 Z_n-t（Ｔ−ｔ） ……（Ａ−３） レコードの最初の部分において、位置０から
（Ｔ−１）までの対角線検査ビツトを計算するに
は、負の番号を有する空の位置からのデータ・ビ
ツトを必要とする。便宜上、これらのデータ・ビ
ツトは０の２進値を有するものと考えられる。レ
コードの終りにおいて、各チヤネルの全ビツトへ
対角線検査ビツトを与えるために、検査チヤネル
０及びＴは（Ｔ−１）個のビツト位置だけ延長さ
れる。延長された位置の検査ビツトは、空の位置
からのデータ・ビツトを必要とするが、これらの
データ・ビツトも０の２進値をとるものと仮定す
る。 第１図において、制御装置３及び７の構造、及
び記憶ユニツト５の内部制御は先行技術の領域に
属し、従つて符号器９と制御装置３との関係、及
び制御装置７と解読器１９との関係の詳細な説明
は省略する。バツフアリング、符号化、解読の一
般的機能を含む典型的システムは、IBM3803磁
気テープ制御装置及びIBM3420磁気テープ装置
に見出される。 符号化データの復元 垂直及び対角線のパリテイ検査ビツトが発生さ
れ、フオーマツト化され、複数チヤネル並列記憶
媒体上に記録されるメカニズムから離れて、説明
の中心を本発明の究極的目的へ移すことにする。
本発明の究極的目的は、所与のチヤネル組におい
て３本までの既知の誤りチヤネルを検出し訂正す
ることである。以下の説明において、先ず誤りシ
ンドロームを説明し、次いで解読プロセスを説明
する。解読プロセスを説明するに当つては、第２
Ａ図〜第２Ｃ図に示されるフオーマツトを参照し
て、誤りチヤネル・ポインタを有する場合の２チ
ヤネル訂正、及びポインタを有しない場合の単一
チヤネル訂正について別々に説明する。次いで第
２Ａ図のフオーマツトを使用して、ポインタを有
する場合の３チヤネル訂正、及びポインタを有し
ない場合の単一チヤネル訂正を説明する。最後
に、順方向読取りと同じように逆方向読取りにお
いても誤り訂正が読取り対称形について説明する
こととする。 ２チヤネル訂正のためのシンドローム決定 前述した如く、読出されたバイトは誤りを有す
るかも知れない。式(4)及び(5)で表わされたパリテ
イ検査が満足されなければ、その結果は誤りのシ
ンドロームと呼ばれる。換言すれば、非ゼロのシ
ンドロームは誤りが存在することを明瞭に示す。
記録媒体から読出されたｍ番目の８ビツト・バイ
トをB^_nとする。更に、記録媒体から読出された
バイト・パリテイをB^_n(8)とする。ｍ番目の垂直
パリテイ検査シンドロームは次の関係式に従い
Sv_nによつて表わされる。 Sv_n＝₈ 〓Γ^k=0 B^_n(k) ……(6) ｍ番目の対角線パリテイ検査誤りシンドローム
Sd_nは次のように表わされる。 Sd_n＝₇ 〓Γ^k=0 B^_n-k(k) ……(7) 読出されたB^_n(k)と書込まれたB_n(k)とのモジユ
ーロ２差はｍ番目のバイトのｋ番目のビツト位置
にある誤りパターンe_n(k)である。 B_n(k)＝B^_n(k)e_n(k) ……(8) もし式(4)及び(6)，(5)及び(7)がそれぞれ結合さ
れ、〔B^_n(k)B_n(k)〕に対してe_n(k)を代入すれば
次のようになる。 Sv_n＝₈ 〓Γ^k=0 〔B^_n(k)B_n(k)〕＝₈ 〓Γ^k=0 e_n(k) ……(9) Sd_n＝₇ 〓Γ^k=0 〔B^_n-k(k)B^_n-k(k)〕＝₇ 〓Γ^k=0 e_n-k(k) ……(10) 今や１本の未知の誤りトラツクにある誤り、又
は２本までの既知の誤りトラツクにある誤りは、
シンドロームSv_n及びSd_nを処理することによつ
て訂正することができる。 ３チヤネル訂正のためのシンドローム決定 第２Ｄ図に示されるフオーマツトに関連するシ
ンドローム処理は、第２Ａ図のものと同じように
してなされる。３トラツク訂正の場合、記録され
読出されたデータとシンドロームと訂正信号とを
識別するために（第２Ｄ図）、記録されたビツト
値をZ_n（ｔ）とし、読出されたビツト値をZ^_n（ｔ）
とする。この読出されたビツト値は誤りを有する
かも知れない。読出しデータへ適用される式（Ａ
−１），（Ａ−２）、又は（Ａ−３）のパリテイ検
査の結果は誤りのシンドロームと呼ばれる。 ｍ番目の垂直パリテイ検査は次のようなシンド
ロームを生じる。 Sv_n＝_T+1 〓Γ^t=0 Z^_n（ｔ） ……（Ａ−４） 正傾斜を有するｍ番目の対角線パリテイ検査は
次のようなシンドロームを生じる。 Sd⁺ _n＝_T 〓Γ^t=0 Z^_n-t（ｔ） ……（Ａ−５） 負傾斜を有するｍ番目の対角線パリテイ検査は
次のようなシンドロームを生じる。 Sd^- _n＝_T 〓Γ^t=0 Z^_n-t（Ｔ−ｔ） ……（Ａ−６） 式（Ａ−１）及び（Ａ−４）、式（Ａ−２）及
び（Ａ−５）、式（Ａ−３）及び（Ａ−６）を結
合すると次のような結果を得る。 Sv_n＝_T+1 〓Γ^t=0 〔Z^_n（ｔ）Z_n（ｔ）〕 ……（Ａ−７） Sd⁺ _n＝_T 〓Γ^t=0 〔Z^_n-t（ｔ）Z_n-t（ｔ）〕 ……（Ａ−８） Sd^- _n＝_T 〓Γ^t=0 〔Z^_n-t（Ｔ−ｔ） Z_n-t（Ｔ−ｔ）〕 ……（Ａ−９） e_n（ｔ）を次のように定義して e_n（ｔ）＝Z^_n（ｔ）Z_n（ｔ） ……（Ａ−10） 式（Ａ−７），（Ａ−８），（Ａ−９）へ式（Ａ−
10）を代入すると、次のような結果を得る。 Sv_n＝_T+1 〓Γ^t=0 e_n（ｔ） ……（Ａ−11） Sd⁺ _n＝_T 〓Γ^t=0 e_n-t（ｔ） ……（Ａ−12） Sd^- _n＝_T 〓Γ^t=0 e_n-t（Ｔ−ｔ） ……（Ａ−13） これらのシンドロームを処理することによつ
て、各種の誤りを訂正することができる。磁気テ
ープにおいて、圧倒的に多い誤りは磁気媒体中の
大きなキズに起因するチヤネル誤りである。誤り
チヤネルは信号損失、超過位相誤り、許容できな
い記録パターン、その他の同様な外部ポインタに
よつて知られる。このような外部ポインタが不在
の場合、誤りチヤネルはシンドロームを処理する
ことによつて知ることができる。上記のシンドロ
ームを処理することによつて、３本までの既知の
誤りチヤネルが訂正され、且つ外部ポインタが存
在しない場合でも１本の誤りチヤネルが決定され
訂正され得る。１本の誤りチヤネルを指定するポ
インタが存在する場合には、第２の誤りチヤネル
を決定することができ、これら２つの誤りチヤネ
ルを訂正することができる。 解読プロセス及び解読装置 解読プロセスはデータへアクセスし、記憶ユニ
ツト５の並列になつた複数チヤネルから制御装置
７へデータを転送することを含む。ここで制御装
置７は解読器１９と協働して、どのチヤネルが誤
りであるかを決定し訂正信号を発生する。複数チ
ヤネルの訂正を考える場合に、所与のチヤネルの
ビツトが誤りであることを決定するために冗長度
を使用することと、誤りを訂正するために冗長度
を使用することとの間には相殺関係があることに
注意されたい。誤りの訂正とは、誤り値に代るデ
ータ値を計算することである。 ポインタを使用する２チヤネル訂正 もし誤りがチヤネル誤りポインタｉ及びｊで指
示されるような最大２本の既知のチヤネルへ限定
されるならば（ここでｉ＜ｊ）、全ての誤りを訂
正することができる。式(9)はｍ番目のバイトであ
る誤りに関して次のように書き直すことができ
る。 Sv_n＝e_n(i)e_n(j) ……(11) 各々の対角線パリテイ検査は最大２つの誤りパ
ターンによつて影響を受ける。全ての誤りは各チ
ヤネルの（ｍ−１）番目のビツト位置へ至るまで
訂正され、シンドローム式は全ての訂正された誤
りパターンについて調整されるものと仮定すれ
ば、ｍ番目のバイトの誤りは（ｍ＋ｉ）番目及び
（ｍ＋ｊ）番目の対角線検査に影響を与える。即
ち、これらの対角線検査のために、式(10)は次のよ
うに書き直すことができる。 Sd_n+i＝e_n(i) ……(12) Sd_n+j＝e_n(j)e_n+j-i(i)
ｊ≠８の場合 ……（13） 式(11)及び(12)は次のような誤りパターンを発生す
る。 e_n(i)＝Sd_n+i ……（14） e_n(j)＝Sd_n+iSv_n ……（15） 次いでバイトB_nは次のように式(8)，（14），
（15）を使用して訂正される。 B^_n(i)＝B_n(i)e_n(i) ……（16） B^_n(j)＝B_n(j)e_n(j) ……（17） もしｊ≠８であれば、（ｍ＋ｊ）番目の対角線
シンドロームは次のようにB_n(j)の訂正を反映す
るように修正される。 Sd_n+j←Sd_n+je_n(j)
ｊ≠８の場合 ……（18） 上記の訂正手順は、ｍを＋１だけ増加させるこ
とによつて、次のバイトへ同様に適用される。チ
ヤネル誤りポインタｉ及びｊの新しい値が前の値
よりも小さくなければ、それらは任意のバイト位
置ｍで変更されることができる。ポインタ値は割
当てられる前に、全てのチヤネルが少なくとも７
個の連続バイトについて誤りを有しなければ、ｉ
及びｊへ任意の値を割当てることができる。ここ
でｉ＜ｊとする。 内部ポインタの発生及び単一チヤネル誤り訂正 この場合、ｊ番目のチヤネルは誤りであり、ｊ
は知られていない。ｍ番目のバイトにある誤りは
ｍ番目の垂直パリテイ検査及び（ｍ＋ｊ）番目の
対角線パリテイ検査に影響を与える。これらのパ
リテイ検査のために、式(9)及び(10)は次のように書
き直すことができる。 Sv_n＝e_n(j) ……（19） Sd_n+j＝e_n(j)、 ｊ≠８の場合 ……（20） Sv_n＝１は誤りの存在を示すことに注意された
い。ポインタｊは数値０〜７の中で次式を満足さ
せるような最小の整数である。 Sv_n＝１＝Sd_n+j ……（21） もし０から７までの全てのｊについてSv_n＝１
及びSd_n+j＝０であれば、ｊ＝８である。次いで、
バイトB_nは次のように訂正される。 B^_n(j)＝B^_n(j)e_n(j) ……（22） もしｊ≠８であれば、後に使用される（ｍ＋
ｊ）番目の対角線シンドロームは、次のように
B^_n(j)の訂正を反映するように修正される。 Sd_n+j←Sd_n+je_n(j) ……（23） もしポインタｊがバイトによつて変更されるよ
うなことがあれば、誤りは１本のトラツクに限定
されないことに注意されたい。そのような誤りは
間違つた訂正をすることなしには訂正することが
できない。ｊのための新しい値は、誤りのない少
なくとも７個の連続したビツト位置の次に使用す
ることができる。 解読器の実施例 第４図を参照すると、そこには解読器１９の詳
細な論理図が示される。それは対角線シンドロー
ム発生器２３、誤りパターン発生器２５、誤り訂
正器２７を含む。データB^_n+i（０），B^_n+i(1)，…
…，B^_n+i(6)，B^_n+i(7)はバイト直列及びビツト並列
でシンドローム発生器２３へ印加される。シンド
ローム発生器２３は７段シフト・レジスタ（段
FF１〜FF７）を含み、最後の段を除く各段への
入力は、シフト・レジスタ段の内容と印加された
データ・ビツトとをモジユーロ２加算したもので
ある。 データ・バイトB^_n+8がシンドローム発生器２
３へ印加されるのと同時に、データ・バイトB^_n
が同様に通路２１を介して誤り訂正器２７へ印加
されている。第５図に示される誤り訂正器２７
は、通路２９及び３５から与えられる誤り訂正信
号e_n(i)もしくはe_n(j)とデータ・バイトの対応する
要素とを論理結合（モジユーロ加算）して、通路
３３へ訂正データを与えるように構成されてい
る。 第４図の誤りパターン発生器２５はシンドロー
ム・プロセツサ２４、プロセツサ２４に含まれる
シンドロームを修正して誤り訂正信号e_n(i)もしく
はe_n(j)を発生させるゲート装置２２及び２６を含
む。この実施例において、２本までの誤りチヤネ
ルが訂正されてよい。 シンドローム・プロセツサ２４は８段シフト・
レジスタ（FF７……FF０）を含む。最初の段を
除く各段への入力は、各段の内容とゲート装置２
２から誘導されたシンドローム修正値とをモジユ
ーロ２加算したものである。このゲート構成は、
通路６０１上の誤り訂正信号e_n(j)をポインタ値J₁
〜J₇によつて決定されたシンドローム・プロセツ
サ２４の対応するXORゲートへ印加する。同様
に、シンドローム・プロセツサ２４のシフト・レ
ジスタ内容は、他のポインタ値I₀〜I₇によつて制
御されるゲート装置２６を通過する。 対角線シンドロームSd_n+iの０から７まで変位
された全ての値は、シンドローム・プロセツサ２
４のシフト・レジスタ段FF₇〜FF₀及びゲート装
置２６の関連したゲートによつて容易に利用可能
となる。シフト・レジスタの各段を接続する
XORゲートは、シンドローム値が新しい位置へ
変位される時に、前サイクルからの訂正された誤
りパターンによつてシンドローム値を修正する。
各バイトがシンドローム発生器２３へ挿入される
各サイクルで、１ビツトがそこからシフトされ、
シンドローム・プロセツサ２４の最初の段に入
る。ゲート装置２６中に示されるように、２本の
誤りチヤネルが訂正されている時にのみ、AND
ゲート６０５はSd_n+iの値を訂正信号として通過
させるであろう。これはゲート６０５を能動化す
ることによつてなされる。他方、この値は入力６
３上の垂直パリテイ・シンドロームと排他的OR
結合され、その結果は通路６０１へ印加される。
もし１本だけのチヤネルが訂正されているのであ
れば、通路６０１を介してなされるシンドローム
の修正は必要でない。即ち、単一チヤネルの訂正
では、訂正信号e_n(i)のみが通路２９を介して誤り
訂正器２７へ送られる。 Ｉ及びＪは最大２本の誤りチヤネルを指定する
ポインタを表わす。これらのポインタは外部的に
誘導されるか、又は内部的に発生される。ポイン
タを内部的に発生する方法は後に説明される。

【表】 表１にはブール変数P₀，P₁，D₂，……，P₈に
対するポインタＩ及びＪの関数が示される。 P_k＝１
ｋ番目のチヤネルが誤りであることを示す。 P_k＝０
ｋ番目のチヤネルが誤りでないことを示す。 ここで０ｋ８である。 シンドロームの発生及び誤りの訂正は共に連続
的なプロセスであることが分る。第４図において
B^₀，B^₁，……，B^_n，B^_n+1はシンドローム発生器
２３へシフト的に入れられる。B₈が入れられた
時にe₀(i)及びe₀(j)が現われる。一般的に云えば、
B^_n+8がシンドローム発生器２３へ入れられた時
に、e_n(i)及びe_n(j)が誤り訂正器２７へ印加され
る。 論理装置による第１チヤネル誤りポインタの発生 最初の誤りチヤネルのポインタｊは、式（21）
が成立するｍ及びｊの最低値を発見することによ
つて決定することができる。これは論理装置又は
カウンタ装置によつてなされ得る。表２におい
て、垂直シンドロームと対角線シンドロームとの
関係は、次式を満足させるようなｊの最小値を指
定する通常のブール関数式で表現されている。 Sv_n＝１ 及び Sd_n+j＝１ カウンタ装置を使用する方法は、（Ｔ＋１）本
のトラツクがあるものと仮定した一般的な場合に
ついて後に説明する。

【表】 ここで、Sv_nはｍ番目の垂直パリテイ検査シン
ドロームであり、Sd_n+iは（ｍ＋ｉ）番目の対角
線パリテイ検査シンドロームである。 チヤネル誤りポインタを使用する３チヤネル訂正 解読目的のためには、誤りは最大３本の既知の
チヤネルに限定され、これらの誤りチヤネルはチ
ヤネル誤りポインタｉ，ｊ，ｋによつて指示され
るものと仮定する。ここでｉはチヤネル番号０か
らＴまでを有する誤りチヤネルの中で最低番号の
チヤネルを表わし、ｋは最高番号のチヤネルを表
わすものと仮定する。ポインタｊは残りの誤りチ
ヤネルを表わし、従つてｉ＜ｊ＜ｋ又はｊ＝Ｔ＋
１が成立する。 全ての誤りは各チヤネルにおいて（ｍ−１）番
目のビツト位置まで訂正され、全ての訂正された
誤りパターンについてシンドローム式が調整され
たものと仮定すると、誤りチヤネルのｍ番目の位
置にある誤りパターンはシンドロームSd⁺ _n+i，
Sd^- _T-k、及びSv_nから決定することができる。こ
れらシンドロームの式は式（Ａ−11），（Ａ−12），
（Ａ−13）から誘導することができる。従つて、
誤りのないチヤネルに対応する既知のゼロ誤りパ
ターン、及び（ｍ−１）番目の位置までの訂正さ
れた誤りパターンを除去すれば、シンドローム式
は次のように書くことができる。 Sd⁺ _n+i＝e_n(i) ……（Ａ−14） Sd^- _n+T-k＝e_n(k) ……（Ａ−15） Sv_n＝e_n(i)e_n(j)e_n(k) ……（Ａ−16） 式（Ａ−14），（Ａ−15），（Ａ−16）は次のよう
な誤りパターンを発生する。 e_n(i)＝Sd⁺ _n+i ……（Ａ−17） e_n(k)＝Sd^- _n+T-k ……（Ａ−18） e_n(j)＝Sv_nSd⁺ _n+iSd^- _n+T-k……（Ａ−19） ｍ番目の位置にある誤りは次のように訂正する
ことができる。 Z_n(i)＝Z^_n(i)e_n(i) ……（Ａ−20） Z_n(j)＝Z^_n(j)e_n(j) ……（Ａ−21） Z_n(k)＝Z^_n(k)e_n(k) ……（Ａ−22） もし２本だけのチヤネルが誤りであれば、誤り
のない１本のチヤネルへポインタを割当て、上記
アルゴリズムに従つて処理を行なつてよい。この
誤りのないチヤネルに対する結果の誤りパターン
はゼロにならなければならない。これは誤つた訂
正に対する追加的な検査法となる。 次のビツト位置の訂正へ進む前に、訂正によつ
て影響を受けたシンドロームは修正されねばなら
ない（特に後に使用されるシンドローム）。修正
は、前に計算されたシンドローム値から新しい値
へ、矢印によつて示される。 Sd^- _n+T-i←Sd^- _n+T-ie_n(i) ……（Ａ−23） Sd⁺ _n+k←Sd⁺ _n+ke_n(k) ……（Ａ−24） Sd⁺ _n+j←Sd⁺ _n+je_n(j)
ｊ＜Ｔ＋１の場合 ……（Ａ−25） Sd^- _n+T-j←Sd^- _n+T-je_n(j)
ｊ＜Ｔ＋１の場合 ……（Ａ−26） 上記の訂正手順は、ｍの値を１だけ増加して次
のビツト位置へ適用することができる。 ポインタの発生及び使用 これまでの説明において、誤りチヤネル（又は
トラツク）を指定するポインタについて頻々言及
してきた。以下の説明においては、主としてポイ
ンタを内部的に発生しそれを使用する方法につい
て説明する。ポインタは外部的に誘導されるか内
部的に発生されてよい。通常、外部ポインタを発
生するためには、チヤネルに記録されたデータの
読出し条件を何らかの形でアナログ的に感知しな
ければならない。外部ポインタを発生する方法及
び装置は本発明の範囲外にある。本発明は、外部
ポインタが存在しない場合には外部ポインタが存
在する場合と同じように、誤り訂正のために１つ
又はそれ以上の内部ポインタを発生する手段を含
む。 テープからレコードを誤りなしに再生すること
を目的として、テープ上にレコードを書込むもの
と仮定する。テープが起動されたばかりでレコー
ドがｍ＝０にある時、誤りは存在せず全てのポイ
ンタはオフであると仮定する。或る時間の後、も
しもチヤネルの１本上で誤りが発生し、チヤネル
の誤りを示す外部ポインタが発生されなければ、
誤りチヤネルを指定するために最初（第１）の内
部ポインタを発生することが必要である。 最初の内部ポインタが１度発生されると、それ
は再生動作が続いている間、指示されたチヤネル
の誤りを訂正するためにオンになつていなければ
ならない。勿論、そのようなポインタの割当て方
法はシステムの訂正能力を不当に制限するかも知
れない。これは特に指示されたチヤネルに連続的
な誤りがない場合にそうである。しかし或る種の
システムでは、最初の誤りが検出された後の所定
時間内に誤りが生じなければ、ポインタを消滅さ
せることができる。 本実施例において、１つの誤りが１本のチヤネ
ルに生じるものと仮定する。そのチヤネルの表示
は外部ポインタ又は第１の内部ポインタによつて
与えられる。最初の誤りチヤネルの検出はシステ
ムの訂正能力内にある。更にこの場合、指示され
たチヤネルの誤りを訂正するために、第１の内部
ポインタはオンに維持される。しかし、他の誤り
が他のチヤネルで正じたならばどうなるであろう
か、これは同様に第２の内部ポインタによつて指
示することができる。しかし第３の誤りチヤネル
を指示するポインタは外部的にのみ発生すること
ができる。 換言すれば、第１の内部ポインタは他のポイン
タが不在の時にオンになる。第２の内部ポインタ
は第１ポインタが存在する時にのみ内部的に能動
化されてよい。第２の内部ポインタは、第１ポイ
ンタが内部的に発生されたものであれ、外部的に
発生されたものであれ能動化される。 内部ポインタは非常に信頼性があると考えられ
るが、実施例のシステムで利用する３個のポイン
タの中で最大２個までを内部的に発生してよい。
更に、２個の内部ポインタを同時に発生すること
はできない。これは第２の内部ポインタが既知の
第１ポインタの存在をその前提条件として必要と
するからである。内部ポインタの発生は、チヤネ
ルをカバーする対角線パリテイ検査と垂直パリテ
イ検査とを利用するものである。 第１及び第２のチヤネル誤りポインタの発生 チヤネル誤りポインタが存在しない場合、誤り
は１本だけのチヤネルへ限定されるものと仮定す
る。この誤りチヤネルは指示することができ、誤
りは訂正することができる。 １本のチヤネルのｍ番目の位置にある非ゼロ・
パターンは、非ゼロの垂直パリテイ検査シンドロ
ームSv_nによつて指示される。この誤りは未知の
ポインタｊを有するチヤネル内にあり、他のチヤ
ネルに誤りはない場合を考える。この場合、式
（Ａ−11），（Ａ−12）から次のような式が得られ
る。 Sv_n＝e_n(j)＝１ ……（Ａ−27） Sd⁺ _n+j＝e_n(j)＝１
ｊ≠Ｔ＋１の場合 ……（Ａ−28） ポインタｊは次式を満足させるような０からＴ
までの整数の中で最小のものである。 Sd⁺ _n+j＝Sv_n＝１ ……（Ａ−29） もしｊが、０からＴまでの全てについてSv_n＝
１及びSd⁺ _n+j＝０であれば、ｊ＝Ｔ＋１である。 ここで第６Ａ図を参照すると、そこには他にポ
インタが存在しない場合に、最初の誤りチヤネル
の指標を得るための第１誤りポインタ発生器が示
される。この発生器は一対のラツチ４０１及び４
０７を含む。これらのラツチはそれぞれ計数降下
形リング・カウンタ４０５を起動及び停止する。
リング・カウンタ４０５の出力はポインタｊを表
わす。ラツチ４０１及び４０７はそれぞれシンド
ロームSd⁺ _n+T及びSv_nに応答する。Sd⁺ _n+T＝１の
時、ラツチ４０１がセツトされ、カウンタ４０５
の計数値はＴへ等しくされる。チヤネルに沿つて
ビツト位置ｍが変化する度に、カウンタは１だけ
減少される。これに対し、Sv_n＝１の時、ラツチ
４０７がセツトされ、カウンタ４０５は停止され
る。この時点のカウンタ値はポインタｊを形成す
る。ラツチ４０１がセツトされる前にラツチ４０
７がセツトされる特別の場合、ｊはＴ＋１に等し
い。 第２誤りポインタの発生理論は前記公開公報に
説明されている。そこで説明されている式は２組
のチヤネルに関するシンドロームに関連してい
る。これらの式は少しの修正を施して本実施例へ
適用することができる。そこで開示される第２誤
りポインタ発生器の実施例は各種のシンドローム
によつて駆動されるカウンタ装置により構成され
ている。 ここで第６Ｂ図を参照すると、そこには第１ポ
インタがＴ＋１以外のチヤネルを指示している時
の第２誤りポインタ発生器が示されている。この
発生器器は一対のリング・カウンタ４０５及び４
０６を含み、これらカウンタはそれぞれポート４
１５及び４１７にポインタｉ及びｊを発生する。
ラツチ４０１は計数降下形のリング・カウンタ４
０５を値ｊへセツトし、ラツチ４０７は計数上昇
形のリング・カウンタ４０６を値ｊへセツトす
る。セツトされたラツチ４０１，４０７によつて
ANDゲート４１３が能動化される時、「停止及び
ゲート・アウト」信号がリング・カウンタ４０
５，４０６へ与えられる。排他的ORゲート４２
３及び４２５の双方で同時的不一致が生じる場合
にのみ、ANDゲート４１１の出力は第２ポイン
タｊがＴ＋１へセツトされたことを示す。通路６
３及び７５上にある入力Sv_n及びSd⁺ _n+jの不一致
はラツチ４０１をセツトし、通路６３及び７１上
にある入力Sv_n及びSd^- _n+T-jの不一致はラツチ４０
７をセツトする。 ここで第６Ｃ図を参照すると、そこには第１ポ
インタがチヤネルＴ＋１を指示している時の第２
誤りポインタ発生器が示される。目的とするとこ
ろは、第１ポインタｊ＝Ｔ＋１が与えられた場合
に、第２ポインタｉを得ることである。この発生
器は、入力Sd^- _n+Tが１の時にラツチ４２７によつ
て０へセツトされる計数上昇形のリング・カウン
タを含む。ｍが１だけ増加される時、このカウン
タは１だけ増加される。最初、ｉは０へセツトさ
れ、次いでｉはカウンタの値に従う。Sd⁺ _n+iが１
に等しくなつた時にカウンタは停止され、その計
数値はポインタ値となることに注意すべきであ
る。

【図面の簡単な説明】

第１図はデータ書込みのためのパリテイ符号器
及びデータがシステムから読出される時に誤り検
査を行なうパリテイ解読器を含む複数チヤネル並
列記憶システムを表わすブロツク図、第２Ａ図乃
至第２Ｄ図はパリテイ符号を記録するための種々
のフオーマツトを示す図、第３図は対角線パリテ
イ符号器を示す図、第４図は解読器におけるシン
ドロームの発生、その修正、及び訂正信号の発生
を示す概略論理図、第５図は第４図に示される解
読器の誤り訂正器２７を詳細に示す図、第６Ａ図
は第１内部ポインタ発生器の論理図、第６Ｂ図及
び第６Ｃ図はそれぞれ第１ポインタがＴ＋１へセ
ツトされない時又はセツトされた時の第２ポイン
タ発生器を示す図である。 １９……解読器、２２，２６……ゲート装置、
２３……対角線シンドローム発生器、２４……シ
ンドローム発生器、２５……誤りパターン発生
器、２７……誤り訂正器。

Claims (1)

1. 【特許請求の範囲】 １ データが書込まれた複数の並列チヤネルのう
   ちの誤りチヤネルを訂正する装置にして、 上記データに対する垂直パリテイ検査符号を第
   １チヤネルに書込み、上記チヤネルに対して所定
   の正及び負の傾斜方向でとられた対角線パリテイ
   検査符号を別のチヤネル又は規則的に間隔をとら
   れたチヤネル横断位置に書込む手段と、 上記垂直パリテイ検査符号及びデータから垂直
   シンドロームを決定し、上記対角線パリテイ検査
   符号及びデータから対角線シンドロームを決定す
   る手段と、 同一の誤りを横切る垂直シンドロームと対角線
   シンドロームとの間の不一致を検出する手段と、 チヤネルに沿つてビツト位置を連続的に更新し
   ながら上記検出する手段の出力を調べ、最初の不
   一致検出から次の不一致検出までのビツト位置数
   に応じて未知の誤りチヤネルを示すポインタを発
   生する手段と、を具備する誤りチヤネル訂正装
   置。 ２ データが書込まれた複数の並列チヤネルのう
   ちの誤りチヤネルを訂正する装置にして、 上記データに対する垂直パリテイ検査符号を第
   １チヤネルに書込み、上記データに対して所定の
   正又は負の傾斜方向でとられた対角線パリテイ検
   査符号を別のチヤネル又は規則的に間隔をとられ
   たチヤネル横断位置に書込む手段と、 上記垂直パリテイ検査符号及びデータから垂直
   シンドロームを決定し、上記対角線パリテイ検査
   符号及びデータから対角線シンドロームを決定す
   る手段と、 チヤネルに沿つてビツト位置を連続的に更新し
   ながら上記垂直シンドローム及び上記対角線シン
   ドロームを比較することによつて未知の誤りチヤ
   ネルを示すポインタを発生する手段と、 上記誤りチヤネル上のビツトを横切る垂直シン
   ドローム及び対角線シンドロームから該ビツトに
   対する訂正信号を発生する手段と、 訂正されたビツトを横切る対角線シンドローム
   を反転する手段と、を具備する誤りチヤネル訂正
   装置。