(57)【特許請求の範囲】
【請求項１】
ホスト・データをフォーマットする方法であって、
予め定義されたデータのグループのメンバーをｍビットのコードワードでコード化し、他のデータをｍビットを超える長さのコードワードでコード化してコード化データストリームを生成するステップを含み、
すべての前記他のデータが共通のmビットのルート・シーケンスを持つコードワードでコード化され、共通のmビットのルート・シーケンス自体は前記予め定義されたデータのグループのいずれのメンバーも表さない、方法。
【請求項２】
前記他のデータがnビットのコードワードでコード化される、請求項１に記載の方法。
【請求項３】
前記mビットのルート・シーケンスが、可能なmビットのコードワードのセットのうち確保された1つを含む、請求項２に記載の方法。
【請求項４】
前記データのグループには２mのメンバーがあり、前記確保されたmビットのルート・シーケンスが、２mの可能なメンバーの1つを表すために確保されたより長いｐビットのコードワードの一部を形成する、請求項３に記載の方法。
【請求項５】
m=8、n=13、p=9である、請求項４に記載の方法。
【請求項６】
前記他のデータが0xffのルート・シーケンスおよび0xff + 1 + #によって表される一般的なコードワード形を持ち、ここで、#は４ビットの値である、請求項５に記載の方法。
【請求項７】
0xff + 0によって表されるコードワードが8ビット値0xffを表す９ビットのコードワードである、請求項６に記載の方法。
【請求項８】
前記他のデータがホスト・データ構造情報および／または制御情報を含む、請求項７に記載の方法。
【請求項９】
テープにホスト・データを書き込む方法であって、
テープに書き込まれるべきホスト・データを受け取るステップと、
受け取られたホスト・データをフォーマットするステップであって、データの予め定義されたグループのメンバーをmビットのコードワードでコード化するステップと、mビットを超える長さのコードワードで他のデータをコード化してコード化データストリームを生成するステップと、を含み、他のすべてのデータが共通のmビットのルート・シーケンスを持つコードワードでコード化され、共通のmビットのルート・シーケンスは前記予め定義されたデータのグループのメンバーのいずれも表さない、ステップと、
テープにデータを書き込むステップと、
を有する方法。
【請求項１０】
請求項１乃至請求項８のいずれかに従ってフォーマットされたデータを復号する方法であって、
mビットのフォーマットされたデータを読み取るステップと、
mビットのデータがmビットのルート・シーケンスでないならば、コードワードを予め定義されたグループのコードワードのメンバーに復号するステップと、
mビットのデータがmビットのルート・シーケンスを表すならば、予め定義された数のさらなるビットを読み取り、該さらなるビットに基づいて、結合したルート・シーケンスおよびさらなるビットをそれぞれの他のデータに復号するステップと、
を有する方法。
【請求項１１】
請求項１０の方法に従ってデータを復号するよう構成された装置。
【請求項１２】
請求項１乃至請求項８のいずれかの方法に従ってデータをフォーマットするよう構成された装置。
【請求項１３】
テープへデータを格納するための装置であって、
ホストコンピュータからホスト・データを受け取るためのインターフェイス手段と、
ホスト・データをテープにデータを書き込むのに適した形に変えるためのデータをフォーマットする手段であって、データの予め定義されたグループのメンバーをmビットのコードワードでコード化し、他のデータをmビットを超える長さのコードワードでコード化してコード化データストリームを生成するコード化手段を含み、他のすべてのデータが共通のmビットのルート・シーケンスを持つコードワードでコード化され、共通のmビットのルート・シーケンスは前記予め定義されたデータのグループのメンバーのいずれも表さない、データフォーマット手段と、
テープにフォーマットされたデータを書き込むデータ書き込み手段と、
を有する装置。
【請求項１４】
請求項１乃至請求項８のいずれかに従ってデータをコード化するよう構成されたASIC装置。
【請求項１５】
データの予め定義されたグループを表すmビットのコードワードおよび他のデータを表すｍビットを超える長さのコードワードを含むデータを復号するよう構成され、他のデータを表すすべてのコードワードが共通のmビットのルート・シーケンスを持ち、共通のmビットのルート・シーケンス自身は前記予め定義されたデータのグループのメンバーのいずれも表さない、ASIC装置。
【請求項１６】
磁気テープ記憶装置を有する請求項１１乃至請求項１３のいずれかに記載の装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
この発明はデータの格納方法に関係し、特に、しかし排他的でなく、例えばテープなどの磁気媒体に格納するためにデータをコード化またはフォーマットするための方法および装置に関する。
【０００２】
【従来の技術】
テープへのデータ格納を例にとると、ホストコンピュータシステムは典型的には、テープドライブのような記憶装置装置にレコードごとにデータを書く。さらに、ホストコンピュータは、ファイル・マーク(FILE MARKs)やセット・マーク(SET MARKs)などのレコード分離文字を使用してレコード自体を分離してもよい。レコード長、およびレコードおよびレコード分離文字が受け取られる順序がホストコンピュータによって判断される。
【０００３】
典型的には、 レコードはユーザデータを含み、例えばワードプロセッサのドキュメント、コンピュータグラフィック画像またはデータベースを構成するデータを含む。対照的に、ファイル・マークなどのレコード分離文字は、ワードプロセッサのドキュメントの終わりおよび次の始まりを示すためにホストコンピュータによって使用される。言い換えれば、 レコード分離文字は典型的には関連するレコードのグループを分離する。
【０００４】
例として、図1(A)は、既存の型のホストコンピュータがテープ記憶装置に書くことがあるユーザデータおよび分離文字の論理的なシーケンスを図示する。具体的には、 ホストコンピュータは、R1からR5の5つの固定長レコードを供給し、レコードR1、 R2およびR5の後に3つのファイル・マーク(FM)を置く。
【０００５】
テープドライブのような記憶装置がホストコンピュータ・データを受け取り、データ・レコードをレコード構造とは独立に固定サイズのグループに整理し、それぞれのグループのインデックス形成部分においてレコード構造をレコードおよびファイルマーク位置によって表すことが知られている。そのような手法は、ISO/IEC標準10777:1991 Eに定義されるテープドライブのためのDDS(デジタルデータ記憶装置)データフォーマット標準の基礎を形成する。ヨーロッパ特許出願EP 0 324 542号明細書は、このような手法を実現するDDSテープドライブの1つの例を記述する。データのグループが形成されると、テープドライブは、典型的には何らかの形態の誤り検出/修正コーディングを適用した後に、グループをテープに格納する。
【０００６】
図1(B)は、図1(A)で示されるホストコンピュータ・データをDDSグループに構成する態様を示す。典型的に、ホストコンピュータ・データ・レコードは、それぞれのグループにおいて連続したコード化されたデータ・ストリームを形成するようコード化されるか圧縮される。ファイル・マークはテープドライブによって受け取られ（インターセプトされ）、コード化されたデータストリームにおけるファイルマークの出現および位置を記述する情報がテープドライブ゛によって生成され、それぞれのグループのインデックスに格納される。この例で、レコードR1、 R2およびレコードR3の一部分は圧縮されコード化されたデータストリームにされ最初のグループに格納され、コード化されたデータストリームにおける存在と位置を示す情報並びに１番目および２番目のファイルマークが最初のグループのインデックスに格納される。次いで、残りのレコードR3、レコードR4およびR5が圧縮され連続したコード化データストリームにされ2番目のグループに格納され、コード化データストリームにおける存在と位置を示す情報および第３のファイルマークが2番目のグループのインデックスに格納される。
【０００７】
グループのインデックスの長さは分離マークの数およびそのグループにあるレコードの数に比例して変わることが理解されるであろう。したがって、それぞれのグループについてコード化データストリームのレコードデータのために残されるスペースは、逆比例して変わる。
【０００８】
そのような手法では、テープドライブは、記憶データを読み取るときホストコンピュータに戻すためにインデックス内の情報に依存してオリジナルのホストコンピュータ・データを再構築する。
【０００９】
図2は非常に一般的に図1(Ｂ)で示され両方のグループのインデックスの形を図示する。示されるように、各インデックスは、2つのメイン・データ構造、すなわちブロックアクセス・テーブル(BAT)とグループ情報テーブル(GIT)を含む。BATのエントリの数はGITのBATエントリ・フィールドに格納される。また、GITは、記録の始まり(BOR)マーク以来書き込まれるFMの数であるファイルマーク・カウント(FMC)のような様々なカウントを含んでいる。これには、現在のグループに含まれるものおよびレコード・カウント（ＲＣ）が含まれる。レコード・カウントは、現在のグループに含まれるものを含み記録の始まり(BOR)マーク以来書き込まれるレコードの数である。この簡単な例でのエントリのための値が括弧に示される。GITは、現在のグループだけに生じるファイルマークおよびレコードのそれぞれの数のような他の情報を含んでもよい。
【００１０】
BATは一連ののエントリを通してグループの内容、特にグループで保持されるレコード・データの論理的な区分化（すなわち、それはそれぞれのレコードの長さおよびそのグループでのそれぞれのセパレータ・マークの位置を記述するエントリを保持する）を記述する。BATでのアクセス・エントリはそのグループの内容の順番であとに続き、そして BAT自体はグループの終わりから内側に成長しレコード・データのコード化データストリームに出会う。
【００１１】
【発明が解決しようとする課題】
本願出願人による同日出願のヨーロッパ特許出願97308756.2は、レコード境界を表す特別で、確保されたファイル・マークのようなコードワードをコード化データストリームの中に埋め込むことによってBATのための条件が取り除かれる発明を記載する。
【００１２】
そこでは、それぞれの埋め込まれたコードワードによってレコード境界およびファイル・マークを見つけることができる。本願出願人によるもう１つのヨーロッパ特許出願97308778.6は、圧縮データと非圧縮データの両方を同じ連続的なコード化データストリームにコード化することができる発明を記述している。その発明にとって、非圧縮データは単にエンコーダを通り抜けコード化されない形で格納されるのが望ましい。
【００１３】
出願中の2つの特許出願の発明を実施するためには、データ圧縮が入力データに適用されないときであっても、確保されたコードワードをコード化データストリームにコード化する必要がある。２つの出願中の特許出願の発明を結合する問題を取り扱ううちに、出願人は特に有利な解決策に到達した。
【００１４】
【課題を解決するための手段】
第1の面に従うと、この発明はホスト・データをフォーマットする方法を提供し、データの予め定義されたグループのメンバーをｍビットのコードワードでコード化し、他のデータをｍビット長を超えるコードワードでコード化してコード化データストリームを生成するステップを含む。他のすべてのデータは共通のmビットのルート・シーケンスを有するコードワードでコード化され、共通のmビットのルート・シーケンス自身は予め定義されたデータのグループのどのメンバーも代表しない。
【００１５】
この発明に従うと、少なくとも2mのコードワードがあることができ、それの2mー1は自由にグループのメンバーを表すことができる。言い換えれば、mビットのルート・シーケンスはグループのメンバーを自由に表すことができない。実用的な実施例で、mビットのルート・シーケンスは、データ復号化中にmビットよりも大きい長さを持つ確保されたコードワードの始まりとして検出されている。明らかに、確保されたコードワードのルート・シーケンスのあとに続くビット数が、どれくらい多くの保留コードワードがフォーマットのなかにありうるかを決定する。
【００１６】
1つの実施例に従うと、データの最初のグループには2mのメンバーがあり、確保されたmビットのルート・シーケンスが、より長いｐビットのコードワードの一部を形成する。このコードワードは、２ｍの可能なメンバーの残りの１つを表すために保留されている。
【００１７】
ここでの利点は、グループのメンバーを表すために2mのコードワードを使用することができることである。例えば、m=8では、 28-1（すなわち255）のコードワードが８ビット長であり、28番目（すなわち256番目）のコードワードが例えば９ビット長である。９番目のビットの状態が、9ビットのコードワードが256番目の文字であるか、9ビットのコードワードが１０ビット以上の長さでありうるさらに他の確保されたコードワードのルート・シーケンスであるかを決定する。
【００１８】
以下で記述する好ましい実施例では、確保されたコードワード(ルート・シーケンスを含む)の長さ(n)は13である。ルート・シーケンスの後の９番目のビットの状態は、9ビットがグループの2m番目のメンバーを表すことを示すか、次の4ビット（すなわち、合計13ビット)が確保された16の可能なコードワードの1つを表わすことを示す。
【００１９】
この発明の実施例は、データ圧縮が適用されないホスト・データをコード化するのに特に有利である。例えば、ホスト・データがASCIIベースならば、グループ・メンバーがASCII文字セットである場合があり、コードワードの1つを除いたすべてがASCII文字セットの単純なコピーである場合がある。本当に、コードワードの1つを除いたすべては、エンコーダによるさらなる動作なしでエンコーダに単にASCII文字データを通すことによって形成されてもよい。1つの残りのコードワードが次いで、レコード境界やファイルマークまたはデータフォーマット制御データのように他のデータを表すコードワードのルートとして使用されてもよい。この例で、そうでなければルート・コードワードによって表されるASCII文字は、より長いコードワードによって表される必要がある。
【００２０】
この発明の他の面、特にこの発明の方法を実施する装置は、以下の説明から明らかになるであろう。さらに、発明のいくつかの面は、フォーマットされたデータを読み取り復号するための方法および装置に関連する。
【００２１】
この発明の他の面と実施例は以下の説明と請求項から明らかになるであろう。
【００２２】
【発明の実施の形態】
この実施例は、テープドライブによって受け取られるデータをテープへのその後の格納のために整理するための新データ・フォーマットに基づく。そのフォーマットを次に詳述する。
【００２３】
フォーマット概要
図4に描かれているように、ホストコンピュータによってテープドライブに書かれる、フォーマットに規定されるデータの最も小さい集まりがレコード400である。レコード400はホストコンピュータによってテープドライブによる処理のために供給されることができ、テープドライブによって再処理されホストコンピュータに提供される。レコードがホストコンピュータによって「書かれる」データの最小の集まりであるという概念は、データが実際にホストコンピュータとテープドライブの間で「転送される」または「トランスポートされる」メカニズムと混同されてはならない。そのようなメカニズムは、典型的には基本的なプロトコル、例えば、 SCSI(スモールコンピュータシステムインタフェース)を利用する。このプロトコルは、ホスト・データの性質または構造と関係なく比較的小さいパケットかバーストの点で明確に規定された(すなわち、交渉済みの)の方法でデータを転送する。SCSIなどのプロトコルは、後続のパケットまたはバーストを受け付ける前にそれぞれのパケットかバーストを有効にする。
【００２４】
このフォーマットは、ファイル・マーク書き込みコマンドの形でホストコンピュータによってテープドライブに書き込まれることができるファイル・マーク410をサポートする。
【００２５】
また、このフォーマットは、それぞれのレコード400におけるデータが可能な場合はデータ圧縮(DC)アルゴリズムによって連続的な(圧縮された)シリーズのデータ・コードワード(CW)にコード化されることを指定する。このデータ・コードワードは図４においてラベル420で示される。
【００２６】
このフォーマットと既存のフォーマットの間の主要な違いは、レコード境界とファイル・マークの両方がシンボルまたは確保された（reserved：残してある、予備の）コードワードとしてコード化され、連続的な(圧縮された)コード化されたデータストリームに埋め込まれることである。例えばDDSのような他のフォーマットと比べて、これは、コード化された、または、圧縮されたデータストリームが、別々に記録されるか転送されたテーブルまたはインデックスを参照することなく、レコードおよびファイル・マーク書き込みコマンドの直列の流れに復号されるのを許容する。図4では、確保されたレコード終り(EOR)コードワードは430で示され、確保されたファイル・マーク・コードワード(FMC)は440で示される。
【００２７】
このフォーマットによると、この発明の本質的な部分ではないが、コード化されたデータストリーム(データおよび確保されたコードワードを含む)は、下に述べるようにさらにデータセット形に整理される。次に、データはテープに書かれ、その過程において周知の誤り検知・訂正コーディング、例えば、 リード-ソロモンのコーディングの形で冗長性を加えることができる。
【００２８】
データセット
コードワードは、図5のダイヤグラムで示されるように40万4352バイトのデータから成るデータセットに整理される。各データセット500は、固定長コードワード領域510および固定長データセット情報テーブル(DSIT)領域520を含む。各データセットはゼロから始まり連続的に割り当てられる連続番号によって同定される。それぞれのデータセットの中で、バイトは0〜40万4351まで連続番号によって同定され、コードワードはバイト0から左から右にデータセット内で配列される。DSITはDDSフォーマットのGITと性質的に似ており、１つの相違点は、このフォーマットにはBAT(または、同等物)がないので、DSITにおいてBATへの参照がないことである。。
【００２９】
プロセスされたデータ・コードワード
既に述べたように、可能な場合には、データはDCアルゴリズムを使用してプロセスされる。この実施例によると、アルゴリズムはALDC-2として知られているLZ-1スライディング辞書圧縮アルゴリズムに基づく。ALDC-2アルゴリズムは、1024バイトの履歴バッファを使用してバイト幅のデータをコード化し、バイト(リテラル)または履歴バッファの中のバイトの文字列への参照を表すデータ・コードワードのシーケンスを出力する。ALDC-2は周知のECMA(ECMA-222)およびQIC(QIC-154)標準であり、ここでは詳細を述べない。LZ-1方法は考案者であるA. LempelとJ. Zivにちなんで名付けられたものであり、 James A. Storerによる本"Data Compression: methods and theory"（1988年にコンピュータサイエンスプレスによって発行された）に詳細が記述されている。LZ-2として知られている他の同様の方法、すなわちこの本に記載されているコードワード辞書技法も代わりに使用することができる。
【００３０】
この実施例によると、ここに詳細を記述するように、コード化手法はALDC-2 DCアルゴリズムの変更されたバージョンを利用し、2つのコード化手法、すなわちデータを圧縮するためのもの(手法1)とデータを圧縮しないで通すもの（手法２）とを切り換える能力、並びに後続の復号化関数を制御するためまたはファイルマークなどのホストコンピュータ・データ分離情報を識別するために、コード化されたデータストリームに含めることができるたくさんの確保されたコードワードをサポートする。
【００３１】
多重データコード化手法
データをコード化するアルゴリズムは2つの異なったコード化手法から成り、そのどちらも処理中のデータの特性に従って選択することができる。第1の手法(手法1)は、履歴バッファのデータへの逆方向参照の使用でデータの冗長度を減少させ、 2番目の手法(手法2)は、修正することなくデータを全般的にコピーする。手法2は、ほとんどまたは全く冗長性を持たない、手法１において拡張を実際に生じさせるデータを守るために提供される。そのような圧縮不可能なデータはグラフィカルなデータか、既に圧縮されているデータでありうる。
【００３２】
どちらの手法が動作中であろうと、すべてのデータが履歴バッファを通り抜ける。したがって、手法2から手法1への変化の後に、手法２を使って受け取られ処理された履歴バッファ中のデータに手法１の逆方向参照を使用することが可能である。それは、あたかも手法2におけるデータ出力が手法１におけるリテラルとして出力されていたかのようである。
【００３３】
手法を変えるときに、アクセスポイント(以下で説明される)でとか、さらにデータを追加するときとかのように、そうすべき別の理由がないかぎり履歴バッファはリセットされる必要がない。リセットは、意味のある逆方向参照を提供するために履歴バッファが再充填を必要とするので、典型的には圧縮比の潜在的な短期間の減少を引き起こすだろう。
【００３４】
手法1のデータ・コードワード
この実施例によると、手法1がデータを圧縮するのに使用され次のような３つのタイプのデータ・コードワードを出力する。
1)リテラル：  ‘0'にコード化中の８ビットのバイト（またはそのコピー）が続く 9ビットのコードワード。
2)逆方向参照：  ’１’に、マッチ長をバイトで表現する可変長２ないし12ビットのマッチカウント／フィールドが続き、これに履歴バッファにおける逆方向参照の始まりの位置を示す10ビットの変位フィールドが続く可変長コードワード。このように、 逆方向参照コードワードは13ビットから23ビットの範囲の長さでありうる。
3)手法１の確保されたコードワード：  いつもルート・コードワード1.1111.11112で始まり、4ビットのフィールドで終わり、図６に示すように確保されたコードワードを同定する13ビット長のコードワード。16の可能な確保されたコードワードは（図12に示されるように）有効な逆方向参照でなく、逆方向参照と混同されることはない。
【００３５】
手法2のデータ・コードワード
この実施例によると、手法2は3つのタイプのデータ・コードワードを出力する。
1)非コード化リテラル：  0x00から0xFEの範囲の8ビットのデータ値について、8ビット入力のコピーである8ビットのデータ・コードワードが出力される。
2)コード化されたリテラル：  8ビット・データ値0xFFについて9ビットのコードワード1111.1111.02が出力される。
3)手法２の確保されたコードワード：  いつもルート・コードワード1111.1111.12で始まり図6で示されるように確保されたコードワードを同定する4ビットのフィールドで終る13ビット長のコードワード。
【００３６】
手法１の逆方向参照
レコード・データが受信されるにつれて、各バイトは一致するバイトを求めて履歴バッファのすべてのバイトと比較される。任意の一致は潜在的逆方向参照として扱われる。一致が現れるならば、次の受け取られたバイトはそれぞれの潜在的逆方向参照に続くバイトと比較される。一致があるならば、2バイトについて逆方向参照が発見されたことになる。一致が生じなくなるかまたは不一致が起こるまで、これは続く。ミスマッチ前のバイトの最も長いマッチングしている文字列がマッチカウントおよび変位フィールドで規定された逆方向参照として使用され、圧縮されコード化されたデータストリームに出力される。図12のテーブルに示されるように、一致カウント・フィールドは、より短い一致フィールドがより長い一致フィールドの始まりとして誤って解釈されるのを防ぐために、2、 4、 6、 8または12ビットのフィールドとしてコード化される。
【００３７】
確保されたコードワード
説明したように、手法1および手法2の両方ともたくさんの13ビットの確保されたコードワードを出力し、最初の9ビットが１で、後続の4ビットは後に規定する確保されたコードワードの1つを表す値である。こうしなければならない理由はないが、便宜上、同じ13ビットの確保されたコードワードが両方の手法に使用される。
【００３８】
確保されたコードワードは、データをコード化するプロセス中にテープドライブによって、コード化されたデータストリームに挿入され、復号化プロセスの操作を制御し、ファイルマークのようなデータ分離情報をコード化する。
【００３９】
しかしながら、 確保されたコードワードはコード化または復号化中に、履歴バッファにパスされない。
【００４０】
DDSフォーマットとは異なり、どこでレコードまたはファイル・マークが始まり終わるかを示す別のインデックス（例えばBAT）がないので、この実施例によるフォーマットは、コード化されたデータストリーム内でのデータ追加または動作の場所を見つけることをイネーブルするための代替のメカニズムを提供する。
【００４１】
このメカニズムは、追加ポイントと呼ばれる予定位置で生じるコード化データストリームの特定の規定された部分をあてにする。これを容易にするために、コード化されたデータストリームは、ホストコンピュータからのデータ転送の始まりから32ビットのワードに論理的に仕切られ、追加ポイントは常に32ビットのワード境界と整列するかこれに詰められている。ワードの32のビット長は、２のべき乗であり便利な数であるが、ワードが他の長さとして規定されてはならない理由はない。
【００４２】
さらに、履歴バッファ不一致が追加ポイントで強制されるので、追加ポイントが逆方向参照に埋め込まれるようにならない。追加ポイント前に見つけられたバイトの最も長いマッチング文字列が、マッチング文字列が追加ポイントを超えて拡張してもよいかどうかとは無関係に出力される。
【００４３】
追加ポイントの存在は、図６に示されるように「詰め」条件をもつ任意の確保されたコードワード、すなわちファイルマーク、EOR、フラッシュ（詰め）およびエンドマーカのコードワードの１つによって決定される。ワード境界との整列を行うために、コード化されたデータストリームにおけるこれらの確保されたコードワード（エンドマーカとは別に）の任意のものとその次のワード境界との間のスペースは、もしあれば、０でビット詰めされている。エンドマーカとその次の境界との間のスペースは、もしあれば、１でビット詰めされている。
【００４４】
実際上、コード化されたデータストリームにおけるコードワードは、手法1と手法2の両方に必要とされるようにそれぞれのデータセットのコードワード領域510に格納するために３２ビットのワードにビット詰めされており、最も有意なビットが出力されるか復号中に遭遇されるようにビット順が逆にされている。次にそれぞれの確保されたコードワードのより詳細な説明を行う。
【００４５】
リセット1
リセット1コードワードに遭遇するときはいつも履歴バッファがリセットされ（すなわち、後続のデータがバッファの始めに置かれ）、続くすべてのデータ・コードワードは、手法１のデータコードワードである。リセット2か手法2コードワードのどちらかに遭遇するまで、これが適用される。
【００４６】
手法1または手法2を適用するかどうかを決定する基礎が、達成した（または達成可能な）圧縮率に完全に依存し、入ってくるデータの構造とは独立なので、リセット1コードワードはレコードの中か外のどちらで生じてもよい。それがレコード外で生じる場合、コードワードは詰め条件を持たないが、EORコードワードのあとに続いて32ビット境界でいつも始まり、そのすぐ後にフラッシュ（詰め）コードワードがいつも続く。こうしてその次のレコードまたはファイルマークはワード境界で始まる。
【００４７】
リセット1コードワードはレコードの最初のコードワードとして生じてもよく、この場合レコード内にあるとされ、フラッシュ・コードワードがこれに続く必要はない。
【００４８】
リセット1コードワードは、前のデータの知識なしに伸長がそのポイントで確実に始まることができるように、アクセスポイントに書かれている。アクセスポイントは、伸長が始まることができるデータデータセットのポイントであり、アクセスポイント後の逆方向参照は、そのアクセスポイント後に受け取られた履歴バッファ内のデータを参照することができるだけである。伸長は、DSITを参照する必要性なしにアクセスポイントを交差してシームレスに続くことができる。
【００４９】
リセット1は、履歴バッファが再成長する必要があるので、圧縮率の潜在的な短期間の低減を引き起こすだろう。
【００５０】
リセット2
リセット2コードワードに遭遇するときはいつも、履歴バッファがリセットされ（すなわち、後続のデータがバッファの始めに置かれる）、あとに続くすべてのデータ・コードワードは手法2のデータ・コードワードである。リセット1か手法1コードワードのどちらかに遭遇するまで、これが適用される。
【００５１】
他のすべてにおいて、リセット2コードワードはリセット1コードワードに同じに扱われる。
【００５２】
手法1
手法1コードワードは、あとに続くすべてのデータ・コードワードが手法1データ・コードワードであることを示し、リセット2または手法2コードワードのどちらかに遭遇するまで、これが適用される。手法1コードワードはレコードの中と外の両方に生じることができる。
【００５３】
コードワードには詰め条件がないが、それがレコードの外で生じるとき、EORコードワードに続いてそれはいつも32ビット境界で始まり、そのすぐ後に常にフラッシュ（詰め）コードワードが続くので、次のレコードまたはファイル・マークはワード境界で始まる。
【００５４】
手法1コードワードはレコードの最初のコードワードとして出力されてもよく、この場合レコード内にあるのと考えられ、詰めコードワードがあとに続く必要はない。
【００５５】
手法2
手法2コードワードは、あとに続くすべてのデータ・コードワードが手法2データ・コードワードであることを示し、これは、リセット1か手法1コードワードのどちらかに遭遇するまで適用される。他のすべてにおいて、それは手法1コードワードと同じ効用を与える。
【００５６】
ファイル・マーク
ファイル・マーク・コードワードはファイル・マーク書き込み(Write FILE MARK)コマンドを表し、従ってレコード内には生じない。ファイル・マーク・コードワードは、32ビット境界でいつも始まる。なぜなら、それはいつも、データ転送の始め、レコードの後、または、別のファイル・マークの後のいずれかに位置するからである。ファイル・マーク・コードワードには、 それぞれの詰め条件があるので、デフォルトとして、32ビットの定数（1.1111.1111.0100 + 000.0000.0000.0000.00002 = FF980000h）として扱うことができる。
【００５７】
EOR
EORコードワードはレコードの最後のコードワードであり、したがって、レコードの外では決して生じることができない。このコードワードに続くのは、次の32ビットのワード境界まで埋め込むためのゼロから３１の０である。
【００５８】
フラッシュ（詰め）
詰めコードワードによって、次のコードワードは次の32ビット境界を始めることになり、EORコードワードと同様に、次の32ビットのワード境界まで埋め込むためのゼロから３１の０が続く。詰めコードワードはレコードの中または外のどちらで使用されてもよく、レコード中間のコードワードを32ビット境界で整列させるために中に置かれ、手法XおよびリセットXのコードワードの直後に続くように外側に置かれる。こうして、任意の後続のレコード(または部分レコード)、ファイル・マークおよびエンドマーカーのコードワードが確実に32ビット境界で始まる。
【００５９】
既に示したように、詰めコードワードはリセットXおよび手法Xのコードワードをサポートするためにレコードの外で使用することができる。このような訳で、これらのコードワードも次の表に示すように32ビットの定数として扱うことができる。
【００６０】
【表１】
'Reset 1 → Flush' = 1.1111.1111.0000 + 1.1111.1111.0110 + 0000002 = FFAFFC00h
'Reset 2 → Flush' = 1.1111.1111.0001 + 1.1111.1111.0110 + 0000002 = FFB7FC00h
'Scheme 1 → Flush' = 1.1111.1111.0010 + 1.1111.1111.0110 + 0000002 = FF8FFC00h
'Scheme 2 → Flush' = 1.1111.1111.0011 + 1.1111.1111.0110 + 0000002 = FF97FC00h
【００６１】
これらの場合に、詰めコードワードは常に32ビットのワードの14番目のビットで始まる。
【００６２】
これまで、例えばDDSフォーマットにおいて、レコードかファイル・マークの後、またはデータの終りに追加する能力を提供することが知られている。このフォーマットの詰めコードワードは、レコードの内部に追加ポイントおよび任意の位置を生成する一層の能力を提供する。この機能が非常に役に立つ場合の例を以下に示す。
【００６３】
エンドマーカー
エンド・マーカー・コードワードは、データセットの中でそれに続くデータは意味を持たず（それが任意の誤り検知・訂正冗長性によってカバーされているかもしれないが）、それが遭遇されるデータセットの残りについての伸長を止めるために使用される。
【００６４】
エンド・マーカー・コードワードが32ビット境界で始まり次の３２ビット境界まで（１で）埋められているので、それは、32ビットの定数'1.1111.1111.1111 +111.1111.1111.1111.11112' = FFFFFFFFh.として扱うことができる。
【００６５】
アクセスポイント
アクセス・ポイントは、履歴バッファがリセットされる位置およびデータセットのデータの伸長を始めることができる位置を示すのに使用される。この実施例によるとデータセットあたり多くても1つのアクセスポイントがあり、その位置がDSITに登録されている。コード化されたデータにおける任意のレコードまたはファイル・マークをアクセスするために、復号化は、レコードまたはファイル・マークの前のストリームにおけるアクセスポイントから始まらなければならず、ターゲットに到達するまで継続する。
【００６６】
具体的には、アクセスポイントは、 データ転送における最初のデータセットの始めにあるものとして規定され、その後は後続のデータセットの始めにあるものとして、または前のデータセットからデータセットにスパンする任意のレコードの終わりのすぐあとに続くものとして規定される。データセットにスパンするレコードが長く次のデータセットにもスパンするならば、有効なアクセスポイントはなく、DSITにファイルされたアクセスポイントの内容がこのことを示すためにFFFFFFFFhにセットされる。
【００６７】
アクセスポイントで履歴バッファがリセットされ、コードワードの1つ(リセット1かリセット2)が任意のレコード・データに先行すし、任意のデータが書かれるかまたはこれに遭遇する前にコード化手法が確実に規定される。これにより、コード化手法が規定される前にファイル・マーク・コードワードがアクセス・ポイントに書かれることが可能になる。どの処理手法がそのポイントから必要であるかに依存して適切なリセット・コードワードが使用される。
【００６８】
アクセスポイントでは次の１つがなければならない：
1)フラッシュが後に続くリセットX;
2)レコード・データが後に続くリセットX；
3)エンドマーカー(End Marker);または、
4)上記のいずれかが続くファイル・マーク。
【００６９】
アクセスポイントでの履歴バッファ「リセット」は、アクセスポイントの前にデータ入力を参照する逆方向参照が出力されるのを防止する。こうして、圧縮と伸長は常にアクセスポイントで始まらなければならない。
【００７０】
データセット充填
データセットの一部分だけがコードワードで満たされており、テープにそのデータセットを書くことが必要であるならば、一層の処理ステップが生じる前にデータセットが「完成される」。そのような場合、レコードが完全でないならばそれはEORコードワードで終えられる。最後の有効なコードワードは、その位置がDSITと符合（この場合はいずれにしても部分的データセットではない）しない限り、エンド・マーカー・コードワードである。オプションで、 エンド・マーカー・コードワードでデータセットの残りを満たすことができる。
【００７１】
データセット情報テーブル
DSITの内容は図7のテーブルの中に示されており、ここで説明する。テーブルにおいて、最も有意のバイトは最も低い番号のバイト位置であり、最も低有意のバイトは最も大きい番号のバイト位置である。
【００７２】
データセットの番号
この4バイトのフィールドは、ゼロで始まるテープの始まり(BOT)からのデータセットの順序数である。
【００７３】
有効なデータ長
この4バイトのフィールドが、データセットの中に存在するかもしれないエンド・マーカーまで（エンド・マーカーを含まず）のプロセスされたコードワードに使用されるデータセットの完全なバイトの数を示す。
【００７４】
アクセスポイント・オフセット
この4バイトのフィールドはアクセスポイントのデータセット内でのバイトオフセットである。 カウントはバイト0で始まりDSITの始めからである。したがって、アクセスポイントがデータセットの最初のバイトであれば、アクセスポイント・オフセットはゼロであろう。
データセット中にアクセスポイントがないならば、このフィールドはすべて１に設定される(すなわち、 FFFFFFFFh)。
【００７５】
「現在のアクセスポイント」は、ここでこのデータセットに存在するアクセスポイントとして定義され、データセットにアクセスポイントがないならば、前の最も近いアクセスポイントとして定義される。
【００７６】
「次のアクセスポイント」は、ここで次か後続のデータセットに生じる最初のアクセスポイントとして定義される。
【００７７】
合計レコード
この6バイトのフィールドは、BOTから現在のアクセスポイントまでのすべてのデータセットにおける完全にプロセスされたすべてのレコードのカウントを指定する。
【００７８】
合計のファイル・マーク
この6バイトのフィールドは、BOTから現在のアクセスポイントまでのすべてのデータセットにおいてプロセスされたすべてのファイル・マークのカウントを指定する。
【００７９】
レコードカウント
この4バイトのフィールドは、現在のアクセスポイントと次のアクセスポイントの間に存在するレコードの数を指定する。したがって、レコードが前のデータセットで始まり、いまのデータセットで終わるならば、そのレコードは数えられない。現在のデータセットにアクセスポイントがないならば、このデータセットの中で始まったり終わったりするレコードはなく、レコード・カウントは前のデータセットのDSITでのレコード・カウントと同じである。レコードがこのデータセットで始まるが後のデータセットまで完成しないならば、それはカウントされる。したがって、データセットの中にアクセスポイントを持ったりゼロのレコードカウントを持つことはできない。この実施例によるとまた、ファイル・マークはレコードとしてカウントされない。
【００８０】
ファイル・マーク・カウント
この4バイトのフィールドは現在のアクセスポイントと次のアクセスポイントの間に書かれたファイル・マークの数を示す。
【００８１】
部分的レコードの長さ
この4バイトのフィールドは、レコードがデータセットで終わらないならば、どれくらい多くのデータ・バイトが現在のデータセットの最後のレコードにあるかを示す。さもなければ、 値はゼロである。
【００８２】
バイト36から468からの残りのDSITフィールドは、ベンダ特定の情報または テープ用法情報のためのものであり、この発明とは関係しない。残りのDSITフィールドは、したがってここでは詳細に記述しない。
【００８３】
テープドライブ・アーキテクチャ
この発明にしたがってテープとの間でデータの格納および回復を行うためのテープドライブのための模範的なアーキテクチャが図８に示されている。図8を参照すると、テープドライブ800がSCSIバス806を介してホストコンピュータ(図示されない)に接続される。ホストコンピュータは、適切な‘アプリケーション'および‘ドライバー'のソフトウェアをロードしており、テープドライブ800と適切な方法で通信することができる。
【００８４】
「書き込み」操作においてテープドライブ800は、テープ876にバックアップすべきデータをホストコンピュータから受け取り、「読み取り」操作においてテープドライブ800は、テープ876から検索されたデータをホストコンピュータに送り返す。ここで記述される実施例では、SCSIバス806がホストコンピュータにテープドライブ800を接続する。しかしながら、たくさんの他の一般的なインタフェース・タイプの任意のものを使用してもよい。
【００８５】
ここで記述されるテープドライブ800は、上で記述されたフォーマットによりデータを格納し検索する。図8でテープドライブ800はテープ・メカニズム870を含み、その他のすべてのコンポーネントで「コントローラ」805が形成される。
【００８６】
コントローラ805は、それぞれが特定のデータ処理操作を実行するように設けられた一連のASIC(適用業務に特化された集積回路)を含む。ASICは、SCSIバス806を介してホストコンピュータとテープドライブ800の間でのデータの転送を管理するためのホストインタフェース810、第1のデータバス815によってホストインタフェース810に接続されるフォーマッタ820、およびは第2のデータバス835によってフォーマッタ820に接続された読取り書込み回路840である。また、含まれているのは、データセット形のデータを格納するめの主バッファ830であり、メモリバス825によってフォーマッタ820に接続されている。メインバッファ830は、少なくとも1つのデータセットを格納するに十分なサイズである1ブロックのDRAM(ダイナミックRAM)を含む。
【００８７】
フォーマッタ820の主な構成要素は図9のダイヤグラムに詳細に図示される。示されるように、フォーマッタ820は、受け取られるホストコンピュータ・データ・バイトを手法Xコードワードとしてコード化するためのエンコーダ900を含み、このエンコーダは手法1または手法2のコードワードをホストコンピュータのデータに適用すべきであるかどうか決定するために履歴バッファ903および比較器907を組み込んでいる。フォーマッタ820は、32ビットのワード境界の観点からコードワードをコード化されたデータストリームに設えるためのパッカー910を含み、このパッカーは、どのコードワードが確保されたコードワードであるか、およびどの確保されたコードワードがそれぞれの詰め（フラッシュ）条件を持つかを解釈するために使われる参照用テーブル915を組み込んでいる。
【００８８】
コントローラ805は、さらに例えばモトローラ68000シリーズ・マイクロプロセッサのようなマイクロプロセッサ850、およびメインメモリ860を含む。このメインメモリは、マイクロプロセッサ850によってアクセス可能なROM(固定メモリ)またはEEPROM(電気的に消去可能なプログラマブルROM)であってもよい。マイクロプロセッサ850は、メインメモリ860に格納されたファームウェア命令によって制御され、後述するようにドライブ805のすべての構成要素を制御する。マイクロプロセッサ850はシステムバス852を通してテープドライブの他の構成要素に接続され、テープドライブ800のそれぞれの構成要素の総合的な操作を制御する。
【００８９】
ホストインタフェース810とフォーマッタ820との間でデータを転送するための第１データバス815は、16ビットのデータチャネルと2ビットの制御チャネルを備える。それぞれ835および845とラベルされる第２および第３のデータバスは16ビットのデータチャネルを含む。データチャネルの実際の幅は重要でないが、より多くのビットを並列に運ぶことができる広いチャンネルは、より速い処理パイプラインを提供することができる。
【００９０】
テープ・メカニズム870は、第3のデータバス845によって読取り書込み回路840に接続された読み出し/書き込みヘッド874、およびヘッド874の動きを制御するためのヘッド・アクチュエータ833を備える。図3(A)と3(B)はデータをテープに書き込むことができる2つの一般的な方法を図示する。
【００９１】
図3(A)において、データは、一端から他端まで一連の斜めのトラック300としてテープの長さに沿って書き込まれている。一般に、このタイプのデータの格納方法はヘリカルスキャン方式として知られており、典型的には4つのヘッド（読み取り書き込みにそれぞれ２つ）を持つ回転ドラムを有するテープドライブ依存している。そのようなテープドライブはよく知られており、上述のDDSデータ記憶装置標準の基礎を形成する。
【００９２】
図3(B)はテープ330の長さに沿った一連の並列チャンネル320として書き込まれたデータを図示する。この技法は線データ記録として一般的に知られている。この図で、集合的にトラック340として知られる4つ(あるいはそれ以上)の並列チャンネルのグループは、テープの一端Aから他端Bまで静止形の多重チャネルヘッドで書かれている。ヘッドがテープの端Bにデータを書き込むとき、それはxだけ位置ずれし、テープは巻き戻されるのでデータはテープの他端Aに向けて逆方向に書き込むことができる。テープの全体の幅が使用されるまで、データが受け取られる限り、このプロセスを続けることができる。
【００９３】
上記の技法のどちらでもテープにこの実施例によってコード化されたデータを書き込むのに使用することができる。この実施例は特定の技法に限られるものではない。このデータフォーマットは、しかしながら、線形テープ記録技法に向けられると特に有利であると期待される。
【００９４】
テープドライブ操作
テープドライブ800において、ホストインタフェース810は、基本的なSCSIプロトコルに従ってSCSIバス806を通してホストコンピュータからデータを受け取る。データが制御データ(例えば、ロード、アンロードまたはスペース）であるならば、ホストインタフェース810がマイクロプロセッサ850にデータをパスし、マイクロプロセッサ制御がテープドライブ800を制御ししかるべく動作させる。
【００９５】
書き込みデータ操作のためにデータがテープに格納されるべきレコード・データならばホストインタフェース810は、データをフォーマッタ820に送り、データはコード化され可能な場合はコード化されたデータストリームに圧縮される。エンコーダ900は、レコード・データのバイトをコード化し、圧縮する目的のために履歴バッファの903および比較器907と対話する。パッカー910は、それぞれの詰め条件に従って必要に応じてストリームのコードワードをビット詰めする。参照用（ルックアップ）テーブル915は確保されたコードワードに関連する情報を含んでおり、このコードワードによってパッカー910はデータストリームにおいてエンコーダによって提供された確保されたコードワードを認識することができ、それらを適切にパックすることができる。コード化されパックされたデータはメインバッファ830に転送される。
【００９６】
また、フォーマッタ820は、データを読取り書込み回路840に送る前にエラー訂正/検出コーディングを適用してもよい。その詳細はこの明細書の範囲外であり、説明を省略する。適切な場合、フォーマッタ820はバッファの主な830からのデータを検索し、それを読取り書込み回路840に送る。
【００９７】
読取り書込み回路840はコード化されたデータを受け取り、データを読み出し/書き込みヘッド(s)874を駆動するのに適当な信号に変える。データを書き込む目的のために、ヘッド・アクチュエータ872はテープ876に関しヘッド874を動かし、テープ・メカニズム870はヘッド874に関しテープ876を動かす。既に述べたように、この実施例に従う操作に適したメカニズムを含むテープデッキは、一般にテープ記憶装置の技術で知られているので、ここでの説明は省略する。
【００９８】
データを書き込むことに関し上述したコンポーネントは、読取り操作のために、テープからデータを読み取り、適切であるならば誤り検出/修正コーディングを取り除き、テープ876から回復されたデータを解凍復号し、データをホストコンピュータ810にパスするために、逆に動作する。
【００９９】
コントローラのいくつかの構成要素の動作をここで説明する。
【０１００】
ホストインタフェース
書き込み操作のために、ホストコンピュータは、 レコードかファイル・マークを書き込むために書き込み（ライト）コマンドをホストインタフェース810に送る。テープドライブが要求に応じるかどうかが、次に説明するようにフォーマッタ820がホストコンピュータからデータを受け取る準備ができているかどうかによって決定される。総合的な書き込みプロセスはマイクロプロセッサ850によって制御される。
【０１０１】
ホストコンピュータからの書き込み要求を受け取り次第、データ・レコードを書くために、ホストインタフェース810はリクエスト信号をマイクロプロセッサ850に送ることによって、レコードに値するデータをフォーマッタ820に送る許可を要求する。マイクロプロセッサ850は続いてフォーマッタ820の状態部をテストする。フォーマッタ820の状態部が許容するならば、データ・レコード全体を受け取るスペースがメインバッファ830にあり、以前に受け取られたデータの処理が完了しているので、マイクロプロセッサ850はホストインタフェース810にフォーマッタ820へのデータ転送を始める信号を送る。一方、フォーマッタ820の状態が、メインバッファが充満していること、または既存のデータがまだプロセス中であることを示すならば、要求は拒絶され、または「保留（オフにする）」にされる。準備ができている場合、ホストインタフェース810は、レコードに値するデータを一度に16ビット第１のデータバスを介してフォーマッタ820に転送する。ファイル・マークを書くためのプロトコルは、ホストコンピュータ・インタフェース810がマイクロプロセッサ850へファイル・マーク書き込み命令が受け取られたことを知らせる信号を送ることである。これに応答して、マイクロプロセッサ850は、ファイル・マーク・コードワードをコード化されたデータストリームに、前のレコード（またはファイル・マーク）の終わりの後に挿入するようフォーマッタ820に信号を送る。
【０１０２】
このフォーマットは、テープドライブ800との間で書き込むことができるデータの最も小さいチャンクとしてレコードを扱うが、ホストインタフェースおよびテープドライブ・ホストインタフェース810によってサポートされる基本的なSCSIプロトコルは、実際に、「バースト」として知られるSCSI定義されたチャンクにおけるデータ転送を管理する。バーストは典型的にはレコードよりも小さい。このように、事実上それぞれのレコード内で、ホストコンピュータとテープドライブ800がバーストによってデータを転送する。SCSIはこの機能をサポートし、 同時に多重デバイスをサービスすることを可能にする。バースト長さは、典型的にはホストコンピュータとテープドライブ800(一般にはSCSIプロトコルの下で作動する任意のデバイス)によってデータ転送の前に交渉される値であり、一般的に、32キロバイトか64キロバイトに設定される。
【０１０３】
ホストコンピュータによってホストインタフェース810にパスされるデータのバーストのそれぞれは、典型的にはSCSIバスの送信端(例えば、 書き込み操作中のホストコンピュータのホスト・バス・アダプター)によって加算され、SCSIバスの受信端(例えば、 書き込み操作中のテープドライブ800のホストインタフェース810)によってチェックされる、２ビットのパリティ情報を含む。パリティ情報は受信端でバーストデータの完全性の簡単なチェックとして使用され、ホストコンピュータ・インタフェース810を超えてはパスされない。
【０１０４】
ホストインタフェース810は、バーストカウンタ811とレコード・カウンタ812の2つのバイト・カウンタを組み込んでおり、レコードおよびバーストの転送中にホストインタフェース810からフォーマッタ820までのバイト・パスとしてカウンタにサービスを提供する。カウンタ(811と812)は、それぞれのバーストまたはレコードについてバーストまたはレコード内のバイトの数をプレロードされている。各バイトがホストインタフェース810から去るに従ってカウンタ(811と812)はディクレメントする。この方法によって、カウントの1つがゼロであるときにホストインタフェース810がバーストかレコードの終わりが生じたと判断し、フォーマッタ820のためにそれぞれのシグナルまたは「フラグ」を生成する。
【０１０５】
この実施例に従ってバーストとEORシグナルの終わりはフォーマッタ820に、第１のデータバス815の2ビットの制御チャネル上の2ビットの制御信号として伝えられる。実際上、これらの信号は、 バーストまたはレコードの最後のバイトと同時にパスするようにタイミングを合わせられている。これに応答して、フォーマッタ820は、信号を受信し、コード化されたデータストリームにおける前のコードワードの最後のバイトの後に、詰めコードワード(バーストの終わりについて)かEORコードワード(EORのための)を挿入するよう構成されている。バーストの終わりとEORが一致する場合、EORが優先順位を取り、フォーマッタ820は、EORコードワードを加算するだけになっている。
【０１０６】
このように、ホストインタフェース810は、適切な信号によって、ファイル・マーク、EORおよび詰めコードワードのコード化されたデータストリームへの加算を制御するためにフォーマッタ820によって必要とされるすべての情報を提供する。
【０１０７】
読取り操作のために、プロセスは、ホストインタフェース810がタイミングを制御することを除いて、概して書き込みプロセスの逆である。すなわち、フォーマッタ820は、復号されたデータ、レコードまたはファイル・マークを、ホストインタフェース810とホストコンピュータがデータを受け取る準備ができているかどうかに基づいて、ホストインタフェース810に送るための許可を一度に要求しなければならない。
【０１０８】
コード化されたデータストリームに詰めコードワードを加算する能力の1つの利点を次に説明する。
【０１０９】
これまで、この発明者にとって知られているテープドライブはホストインタフェースを構成する、データの1つまたは複数の全体のバーストを受けることができるくらい大きいバッファを使った。バッファにおけるデータの各バーストは前処理され、バーストのバイトがデータ圧縮のようなデータ処理に進められる前にパリティ情報を参照してその完全性を検査された。パリティ情報によって、バーストが‘悪い'ことが決定されるならば、ホストインタフェース(または同等なホスト・バス・アダプター)はバーストの再転送を要求する。
【０１１０】
この前処理検査の主な理由は、データがデータ処理ステージに入り、コード化され、特に圧縮されると、典型的にレコードの中にある「バースト境界」が結果の圧縮データストリームで「失われる」ことにある。この場合、例えば、1回のバーストにおける最後のバイトおよび次のバーストの最初のバイトが単一の逆方向参照によってコード化されたデータストリームに表されるときに、バースト境界が「失われる」ことがある。このように、再びバーストを送りコード化されたデータストリーム内の正しい位置に置くことは、極度に難しく、処理面からは扱いにくい。
【０１１１】
一般に、前処理はデータ処理のボトルネックとして認識され、バッファメモリとして高価で速いSRAMを使うことによってこれまである程度低減されてきている。
【０１１２】
この発明者はボトルネック問題を異なる態様で記述し、前処理のためのホストインタフェースのバッファの必要性を大きく取り除いた。
【０１１３】
述べられた問題を克服するためのメカニズムは、コード化されたデータストリームのバーストの終わりを識別するのに詰めコードワードを使用することによって可能になる。既に記述したように、詰めコードワードは、ホストコンピュータ・データストリームでの任意の点をコード化されたデータストリームにおけるワード境界と整列させるために使用することができる。この場合、詰めコードワードは、それぞれのバーストの終わりで次のバーストの始まりをコード化されたデータストリームにおける次の32ビットのワード境界と整列させるのに使用される。このように、バースト境界は、圧縮データ・ストリームにおいてでも任意の詰めコードワードのあとに続く32ビットの境界として明確に識別できる。
【０１１４】
このように、再試行され、コード化されたバーストは、データが圧縮されているときであっても、それぞれのデータセットの「悪い」コード化されたデータの上に書き込むことができる。
【０１１５】
データセットの正しい位置へのバーストの書き直しは、フォーマッタ820によって制御され、このフォーマッタは、第1のポインタと2番目のポインタの２つのポインタを有する。第１のポインタはメインバッファ830における次のデータ・バイトが書き込まれべき記憶位置を示し、この記憶位置は、1バイトがメイン・バッファに書き込まれるたびにインクリメントされる。第２のポインタは、データの最新のバーストに先行する、詰めコードワードによって生成された、32ビット・ワードの境界の記憶位置を示す。それぞれの新しい詰めコードワードがメインバッファ830に書き込まれるにつれて、第２のポインタの値が更新される。ホストインタフェース810がバースト・リトライを要求するとき、マイクロプロセッサ850を通してフォーマッタ820は第１のポインタを最新のアクセスポイントの位置にリセットし、このアクセスポイントから第２のポインタによって指し示される記憶位置へと読み出す。その後、 悪いバーストは再送されたバーストによって上書きされる。このバーストが首尾よくバッファのメイン820に書き込まれるまで、このプロセスは繰り返される。
【０１１６】
また、バースト・リトライが要求されるとき、ホストインタフェース810のカウンタ(811と812)は、再び通り抜ける同じバイトを収容するため、バーストにおけるバイトの数だけインクリメントされる。
【０１１７】
このバースト・リトライ手法の別の利点は、履歴バッファ903がデフォルトで、再送処理されたバーストを書き込むため元々送られたバージョンのバーストを書くためのものと同じ状態にリセットされることである。
【０１１８】
このように、ホストインタフェース810によってバーストにおけるバイトは、受け取られるにつれて圧縮のためにフォーマッタ820にパスされることができる。言い換えれば、バイトをフォーマッタ820に送る前にバースト全体を受け取るのを待つ必要がないので、ボトルネックが取り除かれる。さらに、前処理のためにデータの1つまたは複数の全体バーストを保持する、ホストインタフェース810におけるバッファの必要性もない。
【０１１９】
パリティ検査は、バーストが‘悪い'かどうか判断するために必要である。しかしながら、パリティチェックは、そのバイトがホストインタフェース810を通り抜けるときホストインタフェース810によって計算され、結果のパリティチェック数値は、ホストコンピュータから受信されたバーストについてパリティ情報と比較される。バーストの任意のデータが「悪い」場合、ホストインタフェース810はホストコンピュータに、標準のSCSIコマンドであるバースト・リトライを要求する。
【０１２０】
この原理は、再ボジショニングのためにメインバッファ830における任意の位置に拡張することができる。例えば、 ホストコンピュータは任意の時にSCSIコマンド「セーブ・ポインタ」を発行することができる。このコマンドは、ホストインタフェース810によって詰めコードワードをコード化されたデータストリームに挿入する要求として解釈されることができる。ホストコンピュータがデータの各バーストの前に「セーブ・ポインタ」コマンドを発行するならば、ホストインタフェース810はこれを詰めコードワードを付加する要求として解釈してもよく、これによりバースト・カウンタ811が不要になる。
【０１２１】
フォーマッタ
フォーマッタ820の操作を図10のフローチャートを参照して書き込み操作に関してより詳細に説明する。
【０１２２】
フローチャートにおいて書き込みプロセスは、テープドライブ800がホストコンピュータから書き込みコマンドを受け取り、マイクロプロセッサ850が書き込み操作のためにテープドライブを初期化した後にステップ1000で始まる。ステップ1010で書き込みコマンドが「ファイル・マーク書き込み」であり、フォーマッタ820の準備ができているならば、ホストインタフェース810がファイル・マーク信号をマイクロプロセッサ850に送り、マイクロプロセッサ850がステップ1020でファイル・マークコードワードを出力するためフォーマッタ820に信号を送る。
【０１２３】
書き込みコマンドがレコードを書くためのものであり、フォーマッタ820の準備ができているならば、フォーマッタ820がホストインタフェース810からレコード・データを受け取り、エンコーダ900は、ステップ1030においてバイトごとに手法Xコード化を適用する。Xは、以下に説明するある基準に依存して１または２であることができる。
【０１２４】
どの手法が使われるかに関係なく、すべてのバイトデータが履歴バッファ903を通る。このように、手法1の場合、エンコーダ900は、可能であれば履歴バッファ903に存在するコードワードを参照してコードワード・データを出力する。手法2の場合、エンコーダ900にはパススルーモードがあり、エンコーダ900によって受け取られるバイト値は、単にエンコーダを通りエンコーダの外にパスされる。データがなんの処理も受けることなくパススルーする場合であっても、各バイトはまだコード化されたデータストリームにおけるコードワードと呼ばれる。
【０１２５】
既に述べたように、バースト処理は、フォーマッタ820がホストインタフェース810から詰めポイント信号を受信するとき、コード化されたデータストリームのバーストの最後のバイトの後に詰めコードワードを挿入することによって達成される。また、ホストインタフェース810からのEOR信号に対応して、コード化されたデータストリームのレコードの最後のコードワードの後にEORコードワードが付加される。
【０１２６】
それぞれのレコードかファイル・マークについてコードワードが書き込まれた後、次のステップ1040は、アクセスポイントが必要かどうかを判断するためのものである。新しいデータセットの始まりの後できるだけ早くアクセスポイントが必要とされる。これは実際上、データセットの始め、またはデータセットにおける第1の部分レコードの終わり(レコードが前のデータセットで始まったならば)の後であるだろう。アクセスポイントが必要とされるとき、ステップ1050でフォーマッタ820は、それぞれのEORコードワードを出力した後、パッカー910における残りのデータがメインバッファ830にパスするまで、ホストインタフェース810からのさらなるデータを「ホールドオフ」する。そして、メインバッファ830に保持された現在のデータセットについて、フォーマッタ820はアクセスポイントの位置(現在のデータセットの始まりからのバイト・オフセット)をDSITに登録する。その後、フォーマッタ820は適切なリセットXコードワードを出力し、ホストコンピュータ・インタフェース810からのデータ・バイトを受け取り続ける。
【０１２７】
最後にステップ1060において、プロセスはステップ1010に返りレコードまたはファイル・マークをさらに処理するか、またはプロセスはステップ1070で終了する。
【０１２８】
データセットのためのDSIT値は、ホストインタフェース810から受け取られる信号、特にEORおよびファイル・マーク信号、に基づいてフォーマッタ820によって生成される。
【０１２９】
メインバッファ830から読取り書込み回路までのデータをパスすることは、データセットごとにマイクロプロセッサ850によって制御される。言い換えれば、マイクロプロセッサは、少なくとも1つのデータセットが完全になるまでメインバッファ830からテープへのデータ転送に着手しない。逆に、テープからデータを読取るとき、1つのデータセット全体のために十分な空間がメインバッファ830にあるようになるまで、マイクロプロセッサ850はテープドライブ800がデータを読み取るのを許可しない。
【０１３０】
任意の時間にどのコード化手法が動作中であるかに関し、フォーマッタ820は、手法１を使ってコード化されたデータの圧縮比をモニタするために比較器907の形でモニタ機能を含む。比較器907は、2つのカウンタ、すなわち1バイトがエンコーダにパスされるたびにインクリメントする第１カウンタ904、およびエンコーダ900から出力される（手法１において）かまたは出力されるであろう（すなわち、手法２における逆方向参照）圧縮されたビットの数に沿ってインクリメントする第２のカウンタ905を含む。また、比較器は分割回路906を含み、この分割回路は、所与の時間における第１のカウンタ906の値にわたって第2のカウンタ905の値の比率を計算する。明らかに、分割の前に、同等の数のビット入力を与えて正しい比率を提供するために、バイト入力の数に８を掛けることが必要である。この比率は所与の期間にわたる圧縮率の平均(真または潜在的な)を表している。この所与の期間はエンコーダ900へのバイト入力の数によって測定することができる。例えば、比率は、それぞれのワードに値するデータ（すなわち３２ビット）、それぞれのバーストに値する（例えば３２ｋバイト）のデータ、またはその他任意の期間（例えば１つのバイトの後ごと）にわたって計算されてもよい。比率が計算されるたびに、比較器はどの手法が動作中であるかを示すフラグを生成し、カウンタは、次の比率計算を始めるためにリセットされる。明らかに、圧縮比の計算法には他の多くの方法がある。
【０１３１】
好ましい実施例において、比率が第1のしきい値の下より小さいならば、比較器907は手法1から手法2へのスワップをフラグする。手法2にあるとき、すべての入力データが履歴バッファ903をパススルーするので、事実上、手法1コード化はまだイネーブルされており、潜在的な圧縮比測定が続けられる。比率が第2のしきい値を超えて上昇するならば、手法1へのスワップが比較器907によって合図される。期間としきい値は構成可能であり、手法1から手法2へのスワップのための第１のしきい値は、手法2から手法1へのスワップのための第２のしきい値と同じであっても異なってもよい。最も良い総合的な圧縮性能を提供するための期間としきい値の値は、発見的に決定することができる。代わりに、値は受け取り中のデータの性質に基づいて適応的に決定してもよい。もちろん、適応型のオプションは余分な機能性がテープドライブ800に組み込まれることを必要とするだろうが、これについての説明は省略する。
【０１３２】
このように、手法1が動作中であるとき（最初のデータセットの最初のレコードに対するデフォルトであり、リセット１コードワードによって判断される）、圧縮比が例えば１：１より低下するならば、フォーマッタ820が手法2コードワードをコード化されたデータストリームに挿入する。その後、フォーマッタ820によって受け取られるレコード・バイトは、コード化されないで、エンコーダ900をパススルーする。
【０１３３】
圧縮比のモニタは手法2の動作中続く。圧縮比が例えば1.5：１より上に上昇するならば（すなわち、手法1と2のスイッチングレベルの間には、ヒステリシスの要素がある）、エンコーダ900は手法1コードワードを挿入し、後続のレコード・データ・バイトは、手法1コード化を使用して出力される。
【０１３４】
コード化中に、手法Xコードワードの加算は、履歴バッファ903に影響せず、履歴バッファはリセットされない。このことは、手法2から手法1へのスイッチの後に完全な履歴バッファの内容が潜在的逆方向参照として利用可能であることを意味する。
【０１３５】
読取り動作のためにフォーマッタ820の動作は、書き込み動作の正反対であり、既知の態様で圧縮の代わりにデータ伸長がエンコーダ900（デコーダとして機能する）によって、コード化されたデータに適用される。実施例によっては、エンコーダ900とは別のデコーダを備えるのが好ましいことがあり、これはデザイン選択の問題である。
【０１３６】
この実施例において、圧縮比のモニタは必要とされないので、伸長は圧縮よりも直接的である。伸長は単に、フォーマッタ820が受け取る手法XおよびリセットXのコードワードのあとに続いている。確保されたコードワードは別として、データ・コードワードは、既知のそれぞれの伸長アルゴリズムを適用することによって単に復号される。
【０１３７】
復号化中に、確保されたコードワードが検出され、データストリームから取り除かれ、必要な場合はエンコーダ900（デコーダとして動作している）によって処理される。エンコーダ900によって検出されたファイル・マーク・コードワードは、マイクロプロセッサ850を通してフォーマッタ820が、ファイル・マークがホストコンピュータに送り返されるべきであることを示す信号をホストインタフェース810に送るようにさせる。その他の確保されたコードワードは、どれもホストコンピュータに関する限り意味をもたないので、それらはデータストリームから単に取り除かれる。しかしながら、手法XおよびリセットXのコードワードは、それぞれフォーマッタ820にコード化されたデータを復号させ、履歴バッファをリセットさせる。
【０１３８】
パッカー910の動作を図11のフローチャートを参照してより詳細に説明する。
【０１３９】
パッカー910はエンコーダ900から得られるコードワード・データに作用する。ステップ1100においてデータは一度に１つのコードワードでパッカー910に渡される。それぞれのコードワードが受け取られるにつれて、パッカー920は参照用テーブル915を参照して、コードワードがワード境界条件に関連するフラッシュ（詰め）を持つ確保されたコードワードであるかどうかを判断する。参照用テーブル915は、確保された各コードワードについてエントリを含んでおり、このエントリは、詰め条件があるかどうかおよびコードワードの埋め込みに１を使うのか０を使うのかを示す。また、 参照用テーブル915におけるエントリは、どのコードワードが確保されたコードワードであるかおよび確保されたコードワードはどうプロセスされるべきであるかを判断するために、復号化中に使用される。
【０１４０】
ステップ1105において、受け取られたコードワード・データはパッカー910の「バーレル・シフタ」関数912にわたされる。これは、動作的にはFIFOレジスタと似ており、データビットのストリームをその概念的な「トップエンド（最先端）」に受ける作用を行い、そのビット（複数）をその概念的な「ボトムエンド（下端）」にパススルーし、その概念的な「側」から３２ビット幅のデータワードを並列に出力する。この実施例によると、データバスの幅は１６ビットなので、ビットは必然的に「側」から１６ビットの２ブロックとして出力される。
【０１４１】
バーレル・シフタ関数912は以下のように動作する。ステップ1110でコードワード・データの付加が既にバーレル・シフタ（もし必要であればその中に任意のビットが既に入っている）にあるビットの数を３２ビット以上に増加させるならば、ステップ1115でシフタは最も末尾の３２ビットをメインバッファ830の現在のデータセットにシフトさせる。
次いでステップ1120では、バーレル・シフタの残りのビット(残りのビットがあるならば) は、バーレル・シフタの末尾にシフト(32ビットだけ)される。プロセスは、次いでステップ1110に返り、シフタにおけるビットの数がさらにチェックされる。
【０１４２】
シフタにあるビットが32ビットよりも少ないならば、ステップ1125でパッカがシフタに残りのビットがあるかどうかチェックする。残りのビットがないならば、パッカープロセスはステップ1145で終わる。残りのビットがあるならば、ステップ1130において、パッカ910が参照用テーブル915を参照して詰め条件を持つ確保されたコードワードの存在を検出したかどうかに基づいて、ワード境界へのフラッシュ（詰め）条件がアクセスされる。詰め条件があるならば、ステップ1135において、バーレル・シフタは、詰め条件に依存して最後に受け取られたコードワードの後から３２ビットしきい値までゼロまたは１によって満たされまたは「埋められる」。次に、ステップ1140でシフタはその32ビットをメインバッファ830のデータセットにシフトアウトする。最後に、ステップ1145において、プロセスは、受け取られたコードワード・データについて終了する。
【０１４３】
この方法でパッカー826は、デフォルトとして３２ビットのワード単位で、コード化データの転送を制御し、同時に詰めコードワードについて必要とされる、各データセットの３２ビット境界へのビット埋め込みを制御する。
【０１４４】
読取り動作のために、パッカーはテープから読まれたデータを「解凍する」作用も行う。この動作は、パッカー920が32ビットのワードを受け取り、コードワード・バイトをエンコーダ900（いまデコーダとして動作している）に返す点で、「パッキング」の逆である。そうする際に、パッカー920(「アンパッカー」として機能している)は、参照用テーブル915を参照し、以前に「パック」された確保されたコードワードを検出し、パッキング・プロセスで付加された埋め込みを取り除く。さらに、いくつかの実施例では、パッカー910は、詰めコードワードおよびEORコードワードをコード化されたデータストリームから取り除くようになっていてもよい。フォーマッタ820が復号化プロセス中にこれらのコードワードの受けとりを必要としないからである。
【０１４５】
以上にこの発明の1つの特定の実施例を説明した。この発明は、実施例に限られるものではなく、他の多くのデータ記憶装置において使用することができる。いくつかの例は、ハードディスク・システム、並びにDVD-RAM(ディジタルビデオ・ディスクRAM)を含む光書き込みまたは読み取り可能なディスクシステムである。
【０１４６】
この発明は、例として次の実施態様を含む。
【０１４７】
(1)予め定義されたデータのグループのメンバーをｍビットのコードワードでコード化し、他のデータをｍビットを超える長さのコードワードでコード化してコード化データストリームを生成することを含み、他のすべてのデータが共通のmビットのルート・シーケンスを持つコードワードでコード化され、共通のmビットのルート・シーケンス自体はデータの予め定義されたグループのいずれのメンバーも表さない、ホスト・データをフォーマットする方法
(2) 上記1による方法であって、他のデータはnビットのコードワードでコード化される。
【０１４８】
(3)上記2による方法であって、mビットのルート・シーケンスは可能なmビットのコードワードのセットの確保された1つを含む。
【０１４９】
(4) 上記3による方法であって、データの最初のグループにはmメンバーがあり、確保されたmビットのルート・シーケンスはmの可能なメンバーの1つを表すために確保されたより長いｐビットのコードワードの一部を形成する。
【０１５０】
(5) 上記4による方法であって、m=8、n=13、p=9である上記方法。
【０１５１】
(6) 上記5による方法であって、他のデータが0xffのルート・シーケンスおよび0xff + 1 + #によって表される一般的なコードワード形を持つ。ここで、#は４ビットの値である。
【０１５２】
(7) 上記6による方法であって、0xff + 0によって表されるコードワードは8ビット値0xffを表す９ビットのコードワードである。
【０１５３】
(8)上記7による方法であって、他のデータはホスト・データ構造情報および／または制御情報を含む。
【０１５４】
(9) テープにホスト・データを書き込む方法であって、
テープに書き込まれるべきホスト・データを受け取るステップと、
受け取られたホスト・データをフォーマットするステップであって、データの予め定義されたグループのメンバーをmビットのコードワードでコード化し、mビットを超える長さのコードワードで他のデータをコード化してコード化データストリームを生成するステップと、テープにデータを書き込むステップとを含み、
他のすべてのデータが共通のmビットのルート・シーケンスを持つコードワードでコード化され、共通のmビットのルート・シーケンスはデータの予め定義されたグループのメンバーのいずれも表さないデータ書き込み方法。
【０１５５】
(10) 上記1〜8の任意の1つに従ってフォーマットされたデータを復号する方法であって：
mビットのフォーマットされたデータを読み取るステップと、
mビットのデータがmビットのルートシーケンスでないならば、コードワードを予め定義されたグループのコードワードのメンバーに復号するステップと、
mビットのデータがmビットのルート・シーケンスを表すならば、さらなるビットに基づいて、予め定義された数のさらなるビットを読み取り、結合したルート・シーケンスおよびさらなるビットをそれぞれの他のデータに復号するステップと、を含む復号方法。
【０１５６】
(11) 上記10の方法に従ってデータを復号するために構成される装置。
【０１５７】
(12) 上記1〜8の任意の1つの方法に従ってデータをフォーマットするよう構成された装置。
【０１５８】
(13) テープへのデータ格納のための装置であって、
ホストコンピュータからホスト・データを受け取るためのインターフェイス手段と、
ホスト・データをテープにデータを書き込むのに適した形に変えるためのデータをフォーマットする手段であって、データの予め定義されたグループのメンバーをmビットのコードワードでコード化し、他のデータをmビットを超える長さのコードワードでコード化してコード化データストリームを生成する手段と、テープにフォーマットされたデータを書き込むデータ書き込み手段とを備え、
他のすべてのデータが共通のmビットのルート・シーケンスを持つコードワードでコード化され、共通のmビットのルート・シーケンスはデータの予め定義されたグループのメンバーのいずれも表さないデータ格納装置。
【０１５９】
(14) 上記1〜8の任意の1つに従ってフォーマットされたデータを保持するためのデータ記憶媒体。
【０１６０】
(15) 上記1〜8の任意の1つに従ってデータをコード化するよう構成されたASIC。
【０１６１】
(16)データの予め定義されたグループを表すmビットのコードワードおよび他のデータを表すｍビットを超える長さのコードワードを含むデータを復号するよう構成され、他のデータを表すすべてのコードワードが共通のmビットのルート・シーケンスを持ち、共通のmビットのルート・シーケンス自身はデータの予め定義されたグループのメンバーのいずれも表さない、ASIC。
【０１６２】
(17)データの予め定義されたグループのメンバーを表すｍビットのコードワードおよび他のデータを表すｍビットを超える長さのコードワードのストリームを含み、他のデータを表すすべてのコードワードが共通のmビットのルート・シーケンスを持ち、共通のmビットのルート・シーケンス自身はデータの予め定義されたグループのメンバーのいずれも表さない、コード化されたデータ。
【０１６３】
(18)磁気テープ記憶装置を有する請求項11〜13の任意の1つによる装置。
【０１６４】
【発明の効果】
この発明によると、テープドライブなどのデータ格納装置とコンピュータとの間のデータ交換処理効率を向上させることができる。
【図面の簡単な説明】
【図１】（Ａ）はホストコンピュータからのホストコンピュータ・データの一般的な形を示す図、（Ｂ）は、ホストコンピュータ・データをホストコンピュータ・データをフォーマットする従来技術に従って分類する図。
【図２】図１（Ｂ）のデータグループのインデックスに格納されるタイプのデータをより詳細な態様で示す図。
【図３】（Ａ）および（Ｂ）は、データをテープに書くことができる2つの共通のフォーマットを示す図。
【図４】この発明の実施例に従ってコード化されたデータの一般的な形を示す図。
【図５】この発明の実施例に従って規定されるデータセットの一般的な形を示す図。
【図６】この発明の実施例に従って規定される確保されたコードワードのテーブルを示す図。
【図７】この発明の実施例に従って規定されるデータセット情報テーブルのエントリのテーブルを示す図。
【図８】この発明の実施例に従ってデータをフォーマットするためのテープドライブのアーキテクチャを示すブロック図。
【図９】この発明の実施例に従ってデータをフォーマットするフォーマッタの主要部のブロック図。
【図１０】この発明の実施例に従ってデータをコード化する際のステップを図示するフローチャート。
【図１１】この発明の実施例に従ってコード化されたデータをパックする際のステップを図示するフローチャート。
【図１２】特定の実施例で使用されるデータ圧縮手法におけるマッチフィールド・データに使用されるコード化手法のテーブルを示す図。
【符号の説明】
４００        レコード
４１０        ファイルマーク（分離を表すマーク）
４２０        コードワード
４４０        分離シグナルを表すデータ
【図１】
0004124886.tif 000002
【図２】
0004124886.tif 000003
【図３】
0004124886.tif 000004
【図４】
0004124886.tif 000005
【図５】
0004124886.tif 000006
【図６】
0004124886.tif 000007
【図７】
0004124886.tif 000008
【図８】
0004124886.tif 000009
【図９】
0004124886.tif 000010
【図１０】
0004124886.tif 000011
【図１１】
0004124886.tif 000012
【図１２】
0004124886.tif 000013