(57)【要約】  【課題】  ２進入力データ・ストリームの変調コーディング方法及び装置を提供する。  【解決手段】  ４進列挙型エンコーディング・アルゴリズムが前記入力ビット・ストリームに適用され、それによって一連の４進出力シンボルが生成される。前記４進アルゴリズムは、前記入力ビット・ストリームの奇数インターリーブ及び偶数インターリーブにおけるフィボナッチ・コードをそれぞれ同時にエンコードするように動作可能である。次に、連続する各４進出力シンボルのビットがインターリーブされ、それによってグローバル・ラン・レングス制約及びインターリーブ・ラン・レングス制約を有する出力ビット・ストリームが生成される。前記４進出力シンボルのビット反転により、逆連結変調システムで使用されるＰＲＭＬ（Ｇ，Ｉ）コードの場合と同様に、（Ｇ，Ｉ）制約を有する出力ビット・ストリームが生成される。対応するデコーディング・システムも提供される。  【選択図】  図３
2011503762.tif 000002
【特許請求の範囲】
【請求項１】
２進入力データ・ストリームの変調コーディング方法であって、
前記入力ビット・ストリームの奇数インターリーブ及び偶数インターリーブにおける一般化フィボナッチ・コードをそれぞれ同時にエンコードするように動作可能な４進列挙型エンコーディング・アルゴリズムを前記入力ビット・ストリームに適用して、一連の４進出力シンボルを生成するステップと、
連続する各４進出力シンボルのビットをインターリーブして出力ビット・ストリームを生成するステップと、
を含む方法。
【請求項２】
前記４進出力シンボルの前記ビットを反転させて（Ｇ，Ｉ）制約された出力ビット・ストリームを生成するステップを含む、請求項１に記載の方法。
【請求項３】
前記４進アルゴリズムは、前記奇数インターリーブ及び偶数インターリーブにおける同じフィボナッチ・コードを同時にエンコードするように動作可能である、請求項１に記載の方法。
【請求項４】
前記又は各フィボナッチ・コードのベースは、限られたスパンを有する、請求項１に記載の方法。
【請求項５】
一連の２Ｎビットのコードワードを含む出力ビット・ストリームは、前記入力ビット・ストリーム内の一連のＭビットのワードから生成され、前記４進アルゴリズムは、Ｍビットのワード毎に、入力値を前記Ｍビットのワードの値に初期化するステップと、その後ｉ＝１〜Ｎの反復ｉ毎に、
（ａ）可能な入力値の範囲を４つの部分範囲に区分化する区分化指標を計算するステップと、
（ｂ）前記入力値と前記区分化指標とを比較して、前記入力値がどの前記部分範囲に含まれるかを判定するステップと、
（ｃ）前記入力値が含まれる前記部分範囲に依存する値の４進出力シンボルを生成するステップと、
（ｄ）前記入力値から前記入力値が含まれる前記部分範囲の下位境界値を減じることによって前記入力値を更新するステップと、
を含む、請求項１に記載の方法。
【請求項６】
前記区分化指標は、前記反復数ｉに応じて選択されるフィボナッチ・ベースにそれぞれ依存する部分的辞書式指標の第１の対及び第２の対から計算される、請求項５に記載の方法。
【請求項７】
Ｍ＝２Ｎ−１である、請求項５に記載の方法。
【請求項８】
Ｎ＝１１８であり、前記４進アルゴリズムは、前記奇数インターリーブ及び偶数インターリーブにおける、ｊ＝７の制約と、以下によって定義される限られたスパンＬ＝９のベースと、を有する同じ一般化フィボナッチ・コードをエンコードするように動作可能である、請求項７に記載の方法。
Ｂｎ２９＝５１２  （但し、ｎ＝１，２，．．．，５）
Ｂｎ２９＝４９６  （但し、ｎ＝６，７，．．．，９）
Ｂｎ２９＝５０５−ｎ  （但し、ｎ＝１０，１１，．．．，１１８）
【請求項９】
Ｍ＝２Ｎ−３である、請求項５に記載の方法。
【請求項１０】
Ｎ＝１００であり、前記４進アルゴリズムは、前記奇数インターリーブ及び偶数インターリーブにおける、ｊ＝５の制約と、図６の表で定義される限られたスパンＬ＝９のベースと、を有する同じ一般化フィボナッチ・コードをエンコードするように動作可能である、請求項９に記載の方法。
【請求項１１】
Ｎ＝２００であり、前記４進アルゴリズムは、前記奇数インターリーブ及び偶数インターリーブにおける、ｊ＝６の制約と、図７の表で定義される限られたスパンＬ＝９のベースと、を有する同じ一般化フィボナッチ・コードをエンコードするように動作可能である、請求項９に記載の方法。
【請求項１２】
請求項１に記載の変調コーディング方法によって生成される出力ビット・ストリームのデコーディング方法であって、
前記出力ビット・ストリームのビットをデインターリーブして一連の４進シンボルを生成するステップと、
４進列挙型デコーディング・アルゴリズムを前記４進シンボルに適用して、前記４進エンコーディング・アルゴリズムによって前記奇数インターリーブ及び偶数インターリーブに適用された前記一般化フィボナッチ・コードを同時にデコードし、それによって前記２進入力データ・ストリームを復元するステップと、
を含む方法。
【請求項１３】
２進入力データ・ストリームの変調コーディング装置であって、
前記入力ビット・ストリームの奇数インターリーブ及び偶数インターリーブにおける一般化フィボナッチ・コードをそれぞれ同時にエンコードするように動作可能な４進列挙型エンコーディング・アルゴリズムを前記入力ビット・ストリームに適用して、一連の４進出力シンボルを生成する４進エンコーダと、
連続する各４進出力シンボルのビットをインターリーブして出力ビット・ストリームを生成するマルチプレクサと、
を備える装置。
【請求項１４】
前記４進出力シンボルの前記ビットを反転させて（Ｇ，Ｉ）制約された出力ビット・ストリームを生成するインバータを含む、請求項１３に記載の装置。
【請求項１５】
前記４進エンコーダは、前記奇数インターリーブ及び偶数インターリーブにおける同じフィボナッチ・コードを同時にエンコードするように適合される、請求項１３に記載の装置。
【請求項１６】
前記又は各フィボナッチ・コードのベースは、限られたスパンを有し、前記４進エンコーダは、幅２Ｌ＋２のスライディング・ウィンドウ・エンコーダとして動作するように適合される、請求項１３に記載の装置。
【請求項１７】
前記４進エンコーダは、前記出力ビット・ストリームが一連の２Ｎビットのコードワードを含むように、前記入力ビット・ストリーム内の一連のＭビットのワードをエンコードするように適合され、また、Ｍビットのワード毎に、入力値を前記Ｍビットのワードの値に初期化するステップと、その後ｉ＝１〜Ｎの反復ｉ毎に、
（ａ）可能な入力値の範囲を４つの部分範囲に区分化する区分化指標を計算するステップと、
（ｂ）前記入力値と前記区分化指標とを比較して、前記入力値がどの前記部分範囲に含まれるかを判定するステップと、
（ｃ）前記入力値が含まれる前記部分範囲に依存する値の４進出力シンボルを生成するステップと、
（ｄ）前記入力値から前記入力値が含まれる前記部分範囲の下位境界値を減じることによって前記入力値を更新するステップと、
を含む４進アルゴリズムを適用するように適合される、請求項１３に記載の装置。
【請求項１８】
前記４進エンコーダは、前記区分化指標を、前記反復数ｉに応じて選択されるフィボナッチ・ベースにそれぞれ依存する部分的辞書式指標の第１の対及び第２の対から計算するように適合される、請求項１７に記載の装置。
【請求項１９】
Ｍ＝２Ｎ−１である、請求項１７に記載の装置。
【請求項２０】
Ｎ＝１１８であり、前記４進エンコーダは、前記奇数インターリーブ及び偶数インターリーブにおける、ｊ＝７の制約と、以下によって定義される限られたスパンＬ＝９のベースと、を有する同じ一般化フィボナッチ・コードをエンコードするように適合される、請求項１９に記載の装置。
Ｂｎ２９＝５１２  （但し、ｎ＝１，２，．．．，５）
Ｂｎ２９＝４９６  （但し、ｎ＝６，７，．．．，９）
Ｂｎ２９＝５０５−ｎ  （但し、ｎ＝１０，１１，．．．，１１８）
【請求項２１】
Ｍ＝２Ｎ−３である、請求項１７に記載の装置。
【請求項２２】
Ｎ＝１００であり、前記４進エンコーダは、前記奇数インターリーブ及び偶数インターリーブにおける、ｊ＝５の制約と、図６の表で定義される限られたスパンＬ＝９のベースと、を有する同じ一般化フィボナッチ・コードをエンコードするように適合される、請求項２１に記載の装置。
【請求項２３】
Ｎ＝２００であり、前記４進エンコーダは、前記奇数インターリーブ及び偶数インターリーブにおける、ｊ＝６の制約と、図７の表で定義される限られたスパンＬ＝９のベースと、を有する同じ一般化フィボナッチ・コードをエンコードするように適合される、請求項２１に記載の装置。
【請求項２４】
請求項１３に記載の変調コーディング装置によって生成される出力ビット・ストリームのデコーディング装置であって、
前記出力ビット・ストリームのビットをデインターリーブして一連の４進シンボルを生成するデマルチプレクサと、
４進列挙型デコーディング・アルゴリズムを前記４進シンボルに適用して、前記４進エンコーディング・アルゴリズムによって前記奇数インターリーブ及び偶数インターリーブに適用された前記一般化フィボナッチ・コードを同時にデコードし、それによって前記２進入力データ・ストリームを復元する４進デコーダと、
を備える装置。
【請求項２５】
データ・ストレージ・システムであって、
一連のＭビットのワードを含む２進入力データ・ストリームを変調コーディングして一連の２Ｎビットのコードワードを含む出力ビット・ストリームを生成する、請求項１３に記載の変調コーディング装置と、
ストレージ・メディアと、前記一連のコードワードを前記ストレージ・メディア上に記録し、前記ストレージ・メディアを読み取って再生信号を生成する記録／再生機構と、を備える記録チャネルと、
前記再生信号内の一連の２Ｎビットのワードを検出する検出装置と、
検出された前記２Ｎビットのワードのビットをデインターリーブして一連の４進シンボルを生成するデマルチプレクサと、
４進列挙型デコーディング・アルゴリズムを各２Ｎビットのワードの前記４進シンボルに適用して、前記４進エンコーディング・アルゴリズムによって前記奇数インターリーブ及び偶数インターリーブに適用された前記一般化フィボナッチ・コードを同時にデコードし、それによって一連のＭビットのデータ・ワードを生成する４進デコーダと、
を備えるデータ・ストレージ・システム。
【請求項２６】
請求項２５に記載のデータ・ストレージ・システムを備えるテープ・ドライブであって、前記ストレージ・メディアは、磁気テープを含む、テープ・ドライブ。
【請求項２７】
データ・ストレージ・システムであって、
一連のＭビットのワードを含む２進入力データ・ストリームを変調コーディングして一連の２Ｎビットのコードワードを含む出力ビット・ストリームを生成する、請求項１４に記載の変調コーディング装置と、
前記変調コーディング装置からの前記出力ビット・ストリームを１／（１＋Ｄ２）コーディングしてプレコード済みビット・ストリームを生成するプレコーダと、
前記プレコード済みビット・ストリームをエラー訂正コーディングしてＥＣＣコード化ビット・ストリームを生成するＥＣＣコーダと、
ストレージ・メディアと、前記ＥＣＣコード化ビット・ストリームを前記ストレージ・メディア上に記録し、前記ストレージ・メディアを読み取って再生信号を生成する記録／再生機構と、を備える記録チャネルと、
前記再生信号内の一連の２Ｎビットのワードを検出する検出装置であって、検出された前記２Ｎビットのワード内のエラーを訂正するＥＣＣデコーダを含む検出装置と、
検出された前記２Ｎビットのワードのビットをデインターリーブして一連の４進シンボルを生成するデマルチプレクサと、
４進列挙型デコーディング・アルゴリズムを各２Ｎビットのワードの前記４進シンボルに適用して、前記４進エンコーディング・アルゴリズムによって前記奇数インターリーブ及び偶数インターリーブに適用された前記一般化フィボナッチ・コードを同時にデコードし、それによって一連のＭビットのデータ・ワードを生成する４進デコーダと、
を備えるデータ・ストレージ・システム。
【請求項２８】
請求項２７に記載のデータ・ストレージ・システムを備えるテープ・ドライブであって、前記ストレージ・メディアは、磁気テープを含む、テープ・ドライブ。
【請求項２９】
ストレージ・メディア上に記録されたデータを、請求項１に記載の変調コーディング方法を実施する記録システムによって再生するデータ再生システムであって、
前記ストレージ・メディアを読み取って再生信号を生成する読み取り機構と、
前記再生信号内の一連の２Ｎビットのワードを検出する検出装置と、
検出された前記２Ｎビットのワードのビットをデインターリーブして一連の４進シンボルを生成するデマルチプレクサと、
４進列挙型デコーディング・アルゴリズムを各２Ｎビットのワードの前記４進シンボルに適用して、前記変調コーディング方法の前記４進エンコーディング・アルゴリズムによって前記奇数インターリーブ及び偶数インターリーブに適用された前記一般化フィボナッチ・コードを同時にデコードし、それによって一連のＭビットのデータ・ワードを生成する４進デコーダと、
を備えるデータ再生システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は一般に、入力データの変調コーディング方法及び装置ならびに対応する変調デコーディング・システムに関するものである。
【背景技術】
【０００２】
変調コードは、データ・ストレージ・システムにおいてデータ記録時の望ましくないビット・シーケンス、例えば再生プロセス中にエラーを生じさせるビット・シーケンスを除去するのに使用される。望ましくないビット・シーケンスの一例は、同じ値のビットの長いラン（ｒｕｎ）である。別の例は、同じ値のビットがビット・ストリーム内の交互位置に現れる、即ち、ビット・ストリームの奇数（Ｏ）インターリーブ又は偶数（Ｅ）インターリーブ（．．．ＥＯＥＯＥＯ．．．）の形をとる、同じ値のビットの長いランである。例えば、０ａ０ｂ０ｃ０ｄ０．．．（ａ、ｂ、ｃ等は０又は１のいずれかであり得る）の形式の長いシーケンスは、一般に望ましくないはずである。変調コードは、エンコードされたビット・ストリーム内の望ましくないビット・シーケンスの発生に対して何らかの形の制約を課す。例えば、変調コードの中にはいわゆるＪ制約を課すものがあり、それによってエンコードされたビット・ストリーム内の連続する「１」の最大ラン・レングスは、所定値ｊに制限される。変調コードの中には連続する「０」の最大ラン・レングスに制約を課すものもある。この制約は、ｋ制約又はＧ制約と呼ばれるが、それによって連続する「０」の最大ラン・レングスは、それぞれ値ｋ又はＧに制限される。後者のコード・タイプの一例は、ＰＲＭＬ（ｐａｒｔｉａｌ‐ｒｅｓｐｏｎｓｅ  ｍａｘｉｍｕｍ  ｌｉｋｅｌｉｈｏｏｄ：部分応答最尤法）ベースのテープ・ドライブや光ストレージ・システムのような記録システムで使用されるＰＲＭＬ（Ｇ，Ｉ）コードによって提供される。これらのコードは、「グローバル（ｇｌｏｂａｌ）」制約、即ちＧ制約に加えて「インターリーブ（ｉｎｔｅｒｌｅａｖｅ）」制約、即ちＩ制約も課す。これにより、奇数インターリーブ及び偶数インターリーブのそれぞれにおける「０」の最大ラン・レングスは、値Ｉに制限される。無論、Ｉ制約されたビット・ストリームは、Ｇ＝２Ｉの場合は必然的にＧ制約される。
【０００３】
ＰＲＭＬ（Ｇ，Ｉ）コードは、変調コーディングがエラー訂正コーディング（ＥＣＣ）に先立って実行される逆連結（ｒｅｖｅｒｓｅ  ｃｏｎｃａｔｅｎａｔｉｏｎ：ＲＣ）変調方式で特に有用である。ＲＣ方式では、ＥＣＣデコーダが変調デコーダよりも先に再生動作を行うので、エラー伝搬が低減される。即ち、ＥＣＣデコーダでエラーが発生しなければ、変調デコーダへのエラー伝搬も発生しない。それ故、ＲＣを用いると長い変調コード（即ち、コードワード長が長いコード）の使用が可能となり、その結果、選択された制約の容量付近で動作する高レート・コード及びエンコーダの設計が容易となる。しかしながら、ＰＲＭＬ（Ｇ，Ｉ）コードを利用するにあたっては、効率的なエンコーディング及びデコーディング・アルゴリズムに基づく実用的な実装環境が必要となる。
【０００４】
米国特許第５，７６０，７１８号には、エンコードされたビット・ストリームにｋ制約を課す実用的なエンコーダが開示されている。このエンコーダは、一般化（ｇｅｎｅｒａｌｉｚｅｄ）フィボナッチ・コードのクラスに基づく列挙型エンコーディング（ｅｎｕｍｅｒａｔｉｖｅ  ｅｎｃｏｄｉｎｇ）技法を実施する。列挙型エンコーディングは、「“EnumerativeSource Encoding”, T.M. Cover, IEEE Trans. Inform. Theory, Vol. 19, pp. 73-77,January 1973」に記載されている。フィボナッチ・コードは、「“Fibonacci Codes forSynchronisation Control”, W.H. Kautz, IEEE Trans. Inform. Theory, Vol. 11, pp. 284-292,April 1965」に記載されている。詳細な論述は、上記の各文献を参照していただきたい。本明細書では、以下で説明する本発明の理解を助けるために、これらの技法の簡単な説明を行うことが有用であろう。
【０００５】
簡単に言うと、列挙型エンコーディングは、出力コードワードの辞書式順序に基づいて、入力ワードを出力コードワードにマッピングするプロセスである。即ち、Ｘ個の２進コードワードのセットが２進値に従って順序付けされる場合、各コードワードには、順序付けされたセット内のそれぞれの位置に従って１〜Ｘの番号を割り当てることができる。次に、このように割り当てられた１〜Ｘの各番号によって２進入力ワードの値を定義する場合、Ｘ個の各２進入力ワードは、それぞれ対応するコードワードと関連付けられる。列挙型エンコーディングは、このタイプの方式に従って入力ワードを出力コードワードにマッピングするプロセスである。基礎となるエンコード原理はごく単純なものであるが、コードワードを２進入力ワードから生成する効率的なエンコーダの設計には、実用上の問題がある。例えば、２１００個のコードワードが存在する場合、効率的なエンコーダ設計が必要とされることは容易に理解されるだろう。
【０００６】
フィボナッチ・コードは、２進コードワード表現の各位置において２進数の「１」の値を定義する、ベース（ｂａｓｅ）とも呼ばれる重みのセットによって特徴付けられる。即ち、２進コードワード内の所与の位置における「１」は、通常の２のべき乗ではなく当該位置のフィボナッチ・ベースの値を表す。簡単な一例として、｛ｗｎ｝＝｛１，２，３，５，８，１３，２１｝によって与えられるＮ＝７のベース・セットによってフィボナッチ・コードが定義される場合を考える。各ベースは、以下の線形回帰を満足することが分かる。
ｗｎ＋１＝ｗｎ＋ｗｎ−１  （但し、ｎ＝２，３，．．．，６）
（Ｎ＝７）ビットの完全なフィボナッチ・コードワード・セットは、ｗＮ＋１＝１３＋２１＝３４の可能な値を表すことができる。３４≧２５である故に、この簡単なフィボナッチ・コードは、５ビットの入力を、列挙型エンコーディング・プロセスによって長さＮ＝７のコードワードにエンコードすることができる。このエンコード・プロセスは、次式によって定義される。
ｕ＝ΣｘｉｗＮ−ｉ＋１  （但し、ｉ＝１〜７）
上式で、ｕは入力ワード値であり、（ｘ１，ｘ２，．．．，ｘ７）は出力コードワードである。このエンコード・プロセスは、図１に示されるように入力ワード値からフィボナッチ・ベースを連続的に減じることによって実行される。具体的には、数ｕは、値の降順に取り出される、負の結果を与えない任意のベースｗｎによって連続的に減じられる。その一連の差（ｒｕｎｎｉｎｇ  ｄｉｆｆｅｒｅｎｃｅ）から実際に所与の重みｗＮ−ｉ＋１を減じると、ｘｉ＝１となる。そうでなければ、ｘｉ＝０となる。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】米国特許第５，７６０，７１８号
【特許文献２】米国特許第７，０６４，６８７号
【特許文献３】米国特許第７，０７１，８５１号
【非特許文献】
【０００８】
【非特許文献１】“Enumerative Source Encoding”, T.M.Cover, IEEE Trans. Inform. Theory, Vol. 19, pp. 73-77, January 1973
【非特許文献２】“Fibonacci Codes forSynchronisation Control”, W.H. Kautz, IEEE Trans. Inform. Theory, Vol. 11, pp. 284-292,April 1965
【発明の概要】
【発明が解決しようとする課題】
【０００９】
図１を考察すると、上記の簡単なフィボナッチ・コードはｊ＝１の制約を課すこと、即ち、あるコードワードにおいて「１」が２つ以上連続して発生することはないことが証明される。一般化フィボナッチ・コードを用いると、ｎ＝１〜Ｎのとき、ベースｗｎは以下の線形回帰（不等式）を満足する。
ｗｎ＋１≦ｗｎ＋ｗｎ−１＋．．．＋ｗｎ−ｊ  （但し、ｎ＝ｊ＋１，ｊ＋２，．．．，Ｎ−１）
上式で、指定された正の整数ｊは、上記のコードのｊ制約を定義する。このような一般化フィボナッチ・コードにおけるコードワードの最大数は、次式によって与えられる。
ｗＮ＋１＝ｗＮ＋ｗＮ−１＋．．．＋ｗＮ−ｊ
図１の簡単なコードの場合と同様に、一般化フィボナッチ・コードにおける２進コードワード（ｘ１，ｘ２，．．．，ｘＮ）は、入力ｕ（０≦ｕ＜ｗＮ＋１）をベース｛ｗｎ｝で表すことによって、即ち、ｕ＝ΣｘｉｗＮ−ｉ＋１によって得られる。実装においては、前述の米国特許第５，７６０，７１８号に記載されるように、各ベースは限られたスパンＬを有するように、即ち、
ｗｎ＝Ｂｎ２ｎ−１
となるように選択される。上式で、Ｂｎは２−Ｌ≦Ｂｎ≦１の範囲であり、Ｌビット表現を有する。スパンＬのベースを用いると、エンコードは、Σｕｋ２ｋの最上位ビットから最下位ビットに及ぶ（Ｌ＋１）ビットの幅広いウィンドウを使用して、スライディング・ウィンドウ形式で実行することができる。
【００１０】
米国特許第７，０６４，６８７号及び同第７，０７１，８５１号には、前述の米国特許第５，７６０，７１８号と同様の列挙型エンコーディング概念に基づいてＰＲＭＬ（Ｇ，Ｉ）コード向けに設計されたエンコーダ及びデコーダが開示されている。これらは、一般化フィボナッチ・コードに由来するものである。具体的には、入力ビット・ストリームが奇数インターリーブと偶数インターリーブに分離され、それらの２つのインターリーブ・ビット・ストリームは、個別のフィボナッチ・エンコーダによってエンコードされる。フィボナッチ・コードは「１」のランにｊ制約を課すので、エンコーダ出力のビット反転により、それぞれ「０」のランに対する制約を有する２つのエンコードされたビット・ストリームが得られる。次に、それらのエンコードされたビット・ストリームは、Ｇ＝２Ｉ（但し、Ｉは元のフィボナッチ・コードのｊの値と等しい）の場合に（Ｇ，Ｉ）制約された単一の出力ビット・ストリームが与えられるように、マルチプレクサによってインターリーブされる。米国特許第７，０６４，６８７号の変調エンコーダでは、奇数インターリーブと偶数インターリーブの分離に先立って入力データ・ビットのサブセットをエンコードするために、ショート・ブロック・エンコーダが必要となる。このため、入力ビット・ストリームには２つのフィボナッチ・エンコーダに対する可能な入力を制限する初期制約が課される。これによって実用的な実装環境が提供されるが、ショート・ブロック・コード向けの効率的なブール論理が必要とされる故に、結果として得られるＰＲＭＬ（Ｇ，Ｉ）コードの高レートの達成は、非常に困難である。
【課題を解決するための手段】
【００１１】
本発明の第１の態様は、２進入力データ・ストリームの変調コーディング方法を提供する。前記方法は、
前記入力ビット・ストリームの奇数インターリーブ及び偶数インターリーブにおける一般化フィボナッチ・コードをそれぞれ同時にエンコードするように動作可能な４進列挙型（４‐ａｒｙ  ｅｎｕｍｅｒａｔｉｖｅ）エンコーディング・アルゴリズムを前記入力ビット・ストリームに適用して、一連の４進出力シンボルを生成するステップと、
連続する各４進出力シンボルのビットをインターリーブして出力ビット・ストリームを生成するステップと、
を含む。
【００１２】
先述のとおり、従来技術の技法では、２つの個別の２進エンコーディング・アルゴリズムが入力ビット・ストリームの分離された奇数インターリーブ及び偶数インターリーブに独立して作用する。一方、本発明の変調技法では、４進列挙型エンコーディング・アルゴリズムは、（Ｏ／Ｅインターリーブされた）入力ビット・ストリームを形成する一連の２進入力ビットに作用して、奇数インターリーブ及び偶数インターリーブを、４進出力シンボルを有する単一の列挙型コードとして同時にフィボナッチ・エンコードする。この単一のコードは、本明細書では「インターリーブされたフィボナッチ・コード（ｉｎｔｅｒｌｅａｖｅｄ  Ｆｉｂｏｎａｃｃｉ  ｃｏｄｅ）」と呼ばれる。それ故、上述の列挙型エンコーディングの原理によれば、インターリーブされたフィボナッチ・コードの４進アルゴリズムは、入力ビット・ストリームのＭビットのワードを、値に応じて、４進シンボルを有する１組の順序付けされた出力コードワードにマッピングする。４進シンボルは、それぞれ２つの並列ビットで表される。その後、これらのビットは、一連の出力シンボル用にインターリーブされ、その結果、フィボナッチ・エンコードされた奇数インターリーブ及び偶数インターリーブを伴う２進出力ストリームが生成される。先述のフィボナッチ・コード固有の特性により、グローバル・ラン・レングス制約及びインターリーブ・ラン・レングス制約を有する出力ビット・ストリームが提供される。「１」の最大ラン・レングスに対する制約が必要となる応用例も想定され得るが、ビット反転によって上述のＰＲＭＬコードに適した（Ｇ，Ｉ）制約が得られる。
【００１３】
上記から分かるように、出力ビット・ストリームの奇数インターリーブと偶数インターリーブの両方を生成する上で、従来技術では２つのエンコーダが必要とされるのに比べて、本発明の変調技法では単一の４進列挙型エンコーダがあれば足りる。また、ショート・ブロック・エンコーダも必要とされない。更に、本発明の変調技法を用いると、基礎となる一般化フィボナッチ・コードのすべてのコードワードを余すことなく利用することが可能となり、それ故、ＰＲＭＬ（Ｇ，Ｉ）コードの可能な最大長さを容易に実現することができる。これにより、ＰＲＭＬコードの可能な最高レートが達成される。一方、米国特許第７，０６４，６８７号の変調エンコーダを用いる場合は、特に１３／１４を上回るレートではショート・ブロック・コード向けの効率的なブール論理の設計が困難である故に、このような最大長さの達成は非常に困難となる可能性がある。
【００１４】
本発明は、４進出力シンボルのビットが反転されたＰＲＭＬコードのような応用例においても、シンボル・ビットのインターリーブ前あるいはインターリーブ後に実行可能であることは言うまでもない。
【００１５】
一般に、４進アルゴリズムによって出力のＯ／Ｅインターリーブの形でエンコードされるフィボナッチ・コードは、異なるコードであることも同じコードであることもあるが、多くの場合同じコードが使用される。いずれにせよ、好ましい諸実施形態では、基礎となるフィボナッチ・コード（単数又は複数）のベースが限られたスパンを有するので、エンコード・プロセスをスライディング・ウィンドウ形式で実行することが可能となる。
【００１６】
本発明の第２の態様は、本発明の第１の態様に係る変調コーディング方法によって生成される出力ビット・ストリームのデコーディング方法を提供する。前記デコーディング方法は、
前記出力ビット・ストリームのビットをデインターリーブして一連の４進シンボルを生成するステップと、
４進列挙型デコーディング・アルゴリズムを前記４進シンボルに適用して、前記４進エンコーディング・アルゴリズムによって前記奇数インターリーブ及び偶数インターリーブに適用された前記一般化フィボナッチ・コードを同時にデコードし、それによって前記２進入力データ・ストリームを復元するステップと、
を含む。
【００１７】
本発明の第３の態様は、２進入力データ・ストリームの変調コーディング装置を提供する。前記変調コーディング装置は、
前記入力ビット・ストリームの奇数インターリーブ及び偶数インターリーブにおける一般化フィボナッチ・コードをそれぞれ同時にエンコードするように動作可能な４進列挙型エンコーディング・アルゴリズムを前記入力ビット・ストリームに適用して、一連の４進出力シンボルを生成する４進エンコーダと、
連続する各４進出力シンボルのビットをインターリーブして出力ビット・ストリームを生成するマルチプレクサと、
を備える。
【００１８】
本発明の第４の態様は、本発明の第３の態様に係る変調コーディング装置によって生成される出力ビット・ストリームのデコーディング装置を提供する。前記デコーディング装置は、
前記出力ビット・ストリームのビットをデインターリーブして一連の４進シンボルを生成するデマルチプレクサと、
４進列挙型デコーディング・アルゴリズムを前記４進シンボルに適用して、前記４進エンコーディング・アルゴリズムによって前記奇数インターリーブ及び偶数インターリーブに適用された前記一般化フィボナッチ・コードを同時にデコードし、それによって前記２進入力データ・ストリームを復元する４進デコーダと、
を備える。
【００１９】
本発明の第５の態様は、データ・ストレージ・システムであって、
一連のＭビットのワードを含む２進入力データ・ストリームを変調コーディングして一連の２Ｎビットのコードワードを含む出力ビット・ストリームを生成する、本発明の第３の態様に係る変調コーディング装置と、
ストレージ・メディアと、前記一連のコードワードを前記ストレージ・メディア上に記録し、前記ストレージ・メディアを読み取って再生信号（ｒｅｐｒｏｄｕｃｅｄ  ｓｉｇｎａｌ）を生成する記録／再生機構と、を備える記録チャネルと、
前記再生信号内の一連の２Ｎビットのワードを検出する検出装置と、
検出された前記２Ｎビットのワードのビットをデインターリーブして一連の４進シンボルを生成するデマルチプレクサと、
４進列挙型デコーディング・アルゴリズムを各２Ｎビットのワードの前記４進シンボルに適用して、前記４進エンコーディング・アルゴリズムによって前記奇数インターリーブ及び偶数インターリーブに適用された前記一般化フィボナッチ・コードを同時にデコードし、それによって一連のＭビットのデータ・ワードを生成する４進デコーダと、
を備えるデータ・ストレージ・システムを提供する。
【００２０】
かかるデータ・ストレージ・システムにおいて、前記変調装置において生成される前記一連の２Ｎビットのコードワードは、典型的には前記チャネルに記録される前に、ＰＲＭＬシステムの場合のプレコードやＥＣＣコーディングのような他の様々な処理ステップを経ることになる。好ましい諸実施形態では、逆連結変調方式においてＰＲＭＬ（Ｇ，Ｉ）コードが利用される。これにより、前記データ・ストレージ・システムは、前記変調コーディング装置からの前記出力ビット・ストリームを１／（１＋Ｄ２）コーディングしてプレコード済みビット・ストリーム（ｐｒｅｃｏｄｅｄ  ｂｉｔ‐ｓｔｒｅａｍ）を生成するプレコーダと、前記プレコード済みビット・ストリームをエラー訂正コーディングして、前記記録チャネルに供給されるＥＣＣコード化ビット・ストリーム（ＥＣＣ‐ｃｏｄｅｄ  ｂｉｔ‐ｓｔｒｅａｍ）を生成するＥＣＣコーダと、を含む。また、前記検出装置は、前記再生信号内で検出された前記２Ｎビットのワード内のエラーを訂正するＥＣＣデコーダを含む。
【００２１】
無論、記録メディアの読み取りは許可されるが書き込みは許可されない、読み取り専用ＣＤ又はＤＶＤプレーヤ等のシステムも想定され得る。そのため、かかるシステムでは、対応するエンコーディング装置を伴わずに本発明を実施するデコーディング装置が利用され得る。特に、本発明の第６の態様は、ストレージ・メディア上に記録されたデータを、本発明の第１の態様に係る変調コーディング方法を実施する記録システムによって再生するデータ再生システムを提供する。前記データ再生システムは、
前記ストレージ・メディアを読み取って再生信号を生成する読み取り機構と、
前記再生信号内の一連の２Ｎビットのワードを検出する検出装置と、
検出された前記２Ｎビットのワードのビットをデインターリーブして一連の４進シンボルを生成するデマルチプレクサと、
４進列挙型デコーディング・アルゴリズムを各２Ｎビットのワードの前記４進シンボルに適用して、前記変調コーディング方法の前記４進エンコーディング・アルゴリズムによって前記奇数インターリーブ及び偶数インターリーブに適用された前記一般化フィボナッチ・コードを同時にデコードし、それによって一連のＭビットのデータ・ワードを生成する４進デコーダと、
を備える。
【００２２】
本明細書では一般に、各特徴が本発明の一態様の諸実施形態に関して説明されるが、それらに対応する特徴が本発明の別の態様の諸実施形態で提供されてもよい。
【００２３】
以下では単なる例示として、添付図面を参照しながら本発明の好ましい諸実施形態について説明する。
【図面の簡単な説明】
【００２４】
【図１】簡単なフィボナッチ・コードを使用したエンコード・プロセスを示す図である。
【図２】本発明を実施するデータ処理システムの概略ブロック図である。
【図３】図２のシステムの変調エンコーダのブロック図である。
【図４】図２のシステムの変調デコーダのブロック図である。
【図５】図３の変調エンコーダによって実施されるエンコーディング・アルゴリズムの動作において実行される処理ステップの内訳を示す図である。
【図６】図３の変調エンコーダの諸実施形態で利用されるフィボナッチ・コードのベースを表形式で示す図である。
【図７】図３の変調エンコーダの諸実施形態で利用されるフィボナッチ・コードのベースを表形式で示す図である。
【図８】変調エンコーダの諸実施形態で利用される３つのＰＲＭＬ（Ｇ，Ｉ）コードを比較した図である。
【発明を実施するための形態】
【００２５】
図２のブロック図は、本発明を実施するデータ記憶システムの概略図であり、記録／再生プロセスに関与する主要なコンポーネントを示す。本実施形態において、データ記憶システムは、全体的に１で示されるテープ・ドライブであり、それ故、磁気テープ４の読み書きを行う読み取り／書き込みヘッド３を備えた記録チャネル２を有する。記録側において、テープ・ドライブ１は、ＰＲＭＬ（Ｇ，Ｉ）エンコーダ５、プレコーダ（ｐｒｅｃｏｄｅｒ）６、及び全体的に７で示されるＥＣＣコーダの形をとる変調コーディング装置を有する。ＥＣＣコーダ７は、ＲＣ（Ｒｅｅｄ‐Ｓｏｌｏｍｏｎ：リード・ソロモン）パリティ・ジェネレータ８と、部分的インターリーバ（ｐａｒｔｉａｌ  ｉｎｔｅｒｌｅａｖｅｒ）９とから構成される。再生側において、テープ・ドライブ１は、全体的に１１で示され、検出器１２及びＥＣＣデコーダ１３を備える検出装置と、変調デコーダ１４と、を含む。
【００２６】
動作において、記録対象データは、一連のＭビットのデータ・ワードを含む入力ビット・ストリームの形でＰＲＭＬ（Ｇ，Ｉ）エンコーダ５に供給される。ＰＲＭＬ（Ｇ，Ｉ）エンコーダ５は、後で詳述する入力データの変調コーディングを実行して、一連の２Ｎビットのコードワードを含む（Ｇ，Ｉ）制約されたエンコード済みビット・ストリームを生成する。通常のＰＲＭＬ（Ｇ，Ｉ）コードに基づく変調システムの場合と同様に、エンコードされたビット・ストリームはその後、プレコーダ６によって１／（１＋Ｄ２）プレコードされる。この場合の「＋」は、２を法とする加法を示す。先述した逆連結の概念によれば、ＥＣＣコーディングは本実施形態の変調コーディングの後に実行される。本例において、ＥＣＣコーディングは、プレコーダ６からのコードワード・ストリームにおけるパリティ・シンボルの部分的インターリーブを行う。無制約のＲＳパリティ・シンボルは、パリティ・ジェネレータ８によって２Ｎビットのコードワードから既知の手法で生成される。次に、これらのシンボルは、部分的インターリーバ９によってエンコードされたビット・ストリーム内の所望の地点に挿入される。次に、その結果得られるＥＣＣコード化ビット・ストリームは、チャネル２内の通常の信号処理を経て磁気テープ４上に記録される。再生時は、磁気テープ４によって取得された再生信号が通常の再生信号処理を経て検出器１２に供給される。検出器１２は、典型的にはビタビ（Ｖｉｔｅｒｂｉ）検出器のようなソフト入力／ハード出力検出器、又は各記録ビットの尤度尺度を提供し、再生信号内の２Ｎビットのワードを既知の手法で検出するソフト入力／ソフト出力検出器である。次に、パリティ検査及びエラー訂正処理がＥＣＣデコーダ１３によって既知の手法で実行される。次に、その結果得られる一連の２Ｎビットのワードが変調デコーダ１４に供給され、変調デコーダ１４は、後で詳述するように元の入力データに対応する一連のＭビットのワードを生成するように動作する。
【００２７】
次に図３及び図４を参照して、テープ・ドライブ１のＰＲＭＬ（Ｇ，Ｉ）エンコーダ５及び変調デコーダ１４の動作について詳細に説明する。これらのコンポーネントは、原理的にはソフトウェアの形で実施することもハードウェアとソフトウェアの組合せで実施することもできるが、実用的な実装環境では簡潔さ及び処理速度の観点からハードウェア・ロジックの形で実施されることが好ましい。適切な実装環境は、本明細書の説明を読めば当業者には理解されるだろう。
【００２８】
図３に示されるように、ＰＲＭＬ（Ｇ，Ｉ）エンコーダ５は、４進列挙型エンコーダ１６と、マルチプレクサ１７と、インバータ１８と、を備える。要約すると、４進列挙型エンコーダ１６は、４進列挙型エンコーディング・アルゴリズムを入力ビット・ストリームに適用して、上記で定義したようなインターリーブされたフィボナッチ・コードを実装する。即ち、４進列挙型エンコーダ１６は、入力ビット・ストリームの奇数インターリーブ及び偶数インターリーブにおける生成された各フィボナッチ・コードを、４進出力シンボルを有する単一の列挙型コードとして同時にエンコードするように動作する。４進列挙型エンコーダ１６は、図３の太線で示されるように、入力ビット・ストリーム内のＭビットのワード毎に一連のＮ個の４進出力シンボルを生成する。４進シンボルは、それぞれ２ビットで表される。次に、これらのビットは、一連の４進シンボルについてマルチプレクサ１７によってインターリーブされ、それにより、入力されたＭビットのワード毎に２Ｎビットの２進出力ストリームが生成される。次に、結果として得られる変調エンコード済みビット・ストリームが上述の（Ｇ，Ｉ）制約を満足する一連の２Ｎビットのコードワードから構成されるように、インバータ１８によるビット変換が実行される。
【００２９】
列挙型エンコーディングの原理によれば、４進列挙型エンコーダ１６によって実施される４進列挙型エンコーディング・アルゴリズムは、入力されたＭビットのワードを入力ワードの値に依存する４進コードワードに直接マッピングする。本実施形態の４進アルゴリズムは、４進列挙型エンコーダ１６において、２進出力対（ｘｏｉ，ｘｅｉ）で表される１つの４進シンボルを反復ステップｉ毎に生成する反復プロセスとして適用される。このアルゴリズムは、インターリーブされたフィボナッチ・コードＩＦに関して、定義されたＮ個のベース｛ｗｎ｝（ｎ＝１〜Ｎ）をそれぞれ有する２つの基礎となるフィボナッチ・コードを同時にエンコードするために、値ｕＩＦ＝Σｕｋ２ｋ（ｋ＝０〜Ｍ−１）の入力ワード（ｕＭ−１，ｕＭ−２，．．．，ｕ０）をｕＩＦに依存する４進コードワード（（ｘｏ１，ｘｅ１），（ｘｏ２，ｘｅ２），．．．，（ｘｏＮ，ｘｅＮ））にマッピングする。特に、
０≦ｕＩＦ＜（ｗＮ＋１）２
の範囲の入力が与えられた場合、アルゴリズムは以下のようになる。
【表１】
2011503762.tif 000003
【００３０】
上記を考察すると、このアルゴリズムは本質的に、入力値ｕをＭビットのワード値ｕＩＦに初期化し、その後ｉ＝１〜Ｎの反復ｉ毎に変数Ｎ００、Ｎ０１、Ｎ１０の値を計算し、入力値ｕとＮ００、Ｎ０１、Ｎ１０とを比較することによって出力シンボル（ｘｏｉ，ｘｅｉ）を生成するものであることが分かるだろう。変数Ｎ００、Ｎ０１、Ｎ１０は、可能な入力値ｕの範囲を反復毎に４つの部分範囲（ｓｕｂ‐ｒａｎｇｅ）、即ち、
ｕ＜Ｎ００；
Ｎ００≦ｕ＜Ｎ０１；
Ｎ０１≦ｕ＜Ｎ１０；及び
ｕ≧Ｎ１０
に区分化する働きをするので、本明細書では「区分化指標（ｐａｒｔｉｔｉｏｎｉｎｇ  ｉｎｄｅｘ）」と呼ばれる。
【００３１】
反復毎の可能な入力値ｕの範囲は、０≦ｕ＜ＵｏＵｅである。ここで、Ｕｏ及びＵｅは、それぞれ更新前の反復ｉにおける奇数上限（ｏｄｄ  ｕｐｐｅｒ  ｂｏｕｎｄ）及び偶数上限（ｅｖｅｎ  ｕｐｐｅｒ  ｂｏｕｎｄ）である。初期入力値ｕＩＦはＭビットのワードであり、且つ０≦ｕＩＦ＜２Ｍ  ≦（ｗＮ＋１）２である故に、可能なＭビットの値の範囲は、最初の反復ｉ＝１の区分化指標によって４つに区分化される。より詳細には、出力シンボル（ｘｏｉ，ｘｅｉ）の生成は、以下のステップを含む：
（ａ）区分化指標Ｎ００、Ｎ０１、Ｎ１０を計算するステップ；
（ｂ）現在の入力値ｕと区分化指標とを比較して、当該入力値が上記で定義した４つの部分範囲のうちのどの部分範囲に含まれるかを判定するステップ；
（ｃ）当該入力値がどの特定の部分範囲に含まれるかに従って、（ｘｏｉ，ｘｅｉ）の２ビットを設定するステップ；及び
（ｄ）ｕの現在の値から当該ｕの値が含まれる部分範囲の下位境界値（ｌｏｗｅｒ  ｂｏｕｎｄａｒｙ  ｖａｌｕｅ）を減じることによって入力値を更新するステップ。（なお、この場合の下位境界値は０であるため、ｕが最も低い部分範囲に含まれる場合は、更新後も入力値は変更されないままである。）
【００３２】
区分化指標Ｎ００、Ｎ０１、Ｎ１０は、「部分的辞書式指標（ｐａｒｔｉａｌ  ｌｅｘｉｃｏｇｒａｐｈｉｃ  ｉｎｄｅｘ）」の第１の対ｖｏ、ｖｅ及び第２の対Ｕｏ、Ｕｅから計算される。以下、各指標ｖｏ、ｖｅは「下位部分的辞書式指標（ｌｏｗｅｒ  ｐａｒｔｉａｌ  ｌｅｘｉｃｏｇｒａｐｈｉｃ  ｉｎｄｅｘ）」と呼ばれ、各上限Ｕｏ、Ｕｅは、「上位部分的辞書式指標（ｕｐｐｅｒ  ｐａｒｔｉａｌ  ｌｅｘｉｃｏｇｒａｐｈｉｃ  ｉｎｄｅｘ）」と呼ばれる。これらの値の各対は、その対の各値がそれぞれインバータ１８からの２進出力ストリームの奇数インターリーブ及び偶数インターリーブのうちの１つと関連付けられ、したがって、実際にインターリーブされたフィボナッチ・コードの基礎となるフィボナッチ・コードの一方又は他方と関連付けられるという点で、「部分的」指標と呼ばれる。上記のアルゴリズムに示されるように、ｖｏ、ｖｅ及びＵｏ、Ｕｅの各対の部分的辞書式指標は、反復数ｉに応じて選択されるそれぞれのフィボナッチ・ベース（即ち、ｗＮ−ｉ＋１）に依存する。基礎となるフィボナッチ・コードが異なる場合は、一方のコードに由来する適切なベースがｖｏ、Ｕｏの計算に使用され、他方のコードに由来する適切なベースがｖｅ、Ｕｅの計算に使用されることに留意していただきたい。しかしながら、４進列挙型エンコーダ１６の好ましい諸実施形態では、基礎となるフィボナッチ・コードは同じであり、以下では特に好ましい実例について説明する。更に、好ましい諸実施形態では、基礎となるフィボナッチ・コードは、先に定義した限られたスパンＬのベースを有する。この場合、４進列挙型エンコーダ１６は、当業者には理解されるように幅２Ｌ＋２のスライディング・ウィンドウ・エンコーダとして動作する。
【００３３】
図４は、ＰＲＭＬ（Ｇ，Ｉ）エンコーダ５に対応する変調デコーダ１４を示す。図示のとおり、変調デコーダ１４は、インバータ２０と、デマルチプレクサ２１と、４進デコーダ２２と、を備える。インバータ２０は、再生信号から検出された一連の２Ｎビットのワードを受け取り、それらのビットを反転させて２進出力ストリームをデマルチプレクサ２１に提供する。これにより、受信された２進ストリームの奇数ビット及び偶数ビットがデインターリーブ（ｄｅ‐ｉｎｔｅｒｌｅａｖｅ）され、その結果、検出された２Ｎビットのワード毎に一連のＮ個の４進出力シンボル（ｘｏ，ｘｅ）が生成される。次に、Ｎ個の４進シンボルの各群は、４進デコーダ２２によってデコードされ、その結果、元の入力データ・ストリーム内のＭビットのワードに対応する出力対象のＭビットのワードが復元される。４進デコーダ２２は、４進列挙型エンコーダ１６によって適用されるエンコーディング・アルゴリズムの逆を実施し、したがって４進列挙型デコーディング・アルゴリズムを適用して、４進列挙型エンコーダ１６によって適用されるインターリーブされたフィボナッチ・コードの基礎となるフィボナッチ・コードを同時にデコードする。このアルゴリズムでは、連続する反復ステップにおいて連続する４進シンボル（ｘｏｉ，ｘｅｉ）のビット対が処理される。特に、奇数インターリーブ及び偶数インターリーブにおける基礎となるフィボナッチ・コードに対して、コードワードｘｏ１，ｘｏ２，．．．，ｘｏＮ、及びコードワードｘｅ１，ｘｅ２，．．．，ｘｅＮが与えられた場合、アルゴリズムは以下のようになる。
【表２】
2011503762.tif 000004
【００３４】
先述のとおり、基礎となるフィボナッチ・コードが異なる場合、ｖｏ，ｖｅ及びＵｏｉ，Ｕｅｉの各対のベースｗＮ−ｉ＋１は、奇数指標と偶数指標とで異なる可能性があり、また、各ベースが限られたスパンＬを有する好ましい例では、デコーダは幅２Ｌ＋２のスライディング・ウィンドウ・デコーダとして動作する。
【００３５】
図５の表は、４進列挙型エンコーダ１６の複雑さのレベルを、反復毎に必要とされる様々なタイプの処理ステップ数の内訳として示す。特に重要な（ｃｒｉｔｉｃａｌ）複雑さは、必要とされる乗算の回数である。図５の表に示されるように、フィボナッチ・ベースが限られたスパンＬを有する場合、（Ｌ＋１）ビットの数の乗算は３回しか必要とされない。デコーディング・アルゴリズムでは（Ｌ＋１）ビットの数の比較が必要とされないため、複雑さはずっと低くなる。ストレージ要件に関しては、奇数インターリーブ及び偶数インターリーブにおける基礎となるフィボナッチ・コードがスパンＬのベースと同一である場合、４進列挙型エンコーダ１６は、Ｎ個のＬビット・ベース要素を記憶するだけでよい。また、デコーダは、Ｌビットの数である２Ｎ個の上位部分的辞書式指標を記憶する必要がある。
【００３６】
上述の４進列挙型エンコーディング技法は、非常に効率的な変調エンコーディング及びデコーディング・システムを提供することが理解されるだろう。これらの技法を用いると、基礎となる一般化フィボナッチ・コードのすべてのコードワードを余すことなく利用することが可能となり、その結果、ＰＲＭＬ（Ｇ，Ｉ）コードの可能な最大長さを容易に実現することができる。これにより、ＰＲＭＬコードの可能な最高レートを達成することが可能となる。その結果得られるコード・レート利得は、図２のＲＣ方式の場合と同様に無制約シンボルの部分的インターリーブの使用を支援する。更に、このような高レート・コーディング技法は、ＬＤＰＣ（ｌｏｗ‐ｄｅｎｓｉｔｙ  ｐａｒｉｔｙ‐ｃｈｅｃｋ：低密度パリティ検査）コードに基づくＥＣＣ技法との併用、又は検出器からエンコーダへのソフト情報のメッセージ・パッシングを必要とするターボ・コーディング方式との併用に適している。以下では図６乃至図８を参照して、本発明の諸実施形態に関する好ましいＰＲＭＬコードの具体例について説明する。
【００３７】
以下では、レート（２Ｎ−Ｐ）／２Ｎ（即ち、Ｍ＝２Ｎ−Ｐ）の３つのコードについて説明する。各例において、インターリーブされたフィボナッチ・コードの基礎となる２つのフィボナッチ・コードは同じものとする。１つ目のコードでは、Ｐ＝１とする。スパンＬ＝９、且つｊ＝７の基礎となる一般化フィボナッチ・コードについて、ベースｗｎ＝Ｂｎ２ｎ−１（ｎ＝１，２、Ｎ＝１１８）は、以下のように定義される。
Ｂｎ２９＝５１２  （但し、ｎ＝１，２，．．．，５）
Ｂｎ２９＝４９６  （但し、ｎ＝６，７，．．．，９）
Ｂｎ２９＝５０５−ｎ  （但し、ｎ＝１０，１１，．．．，１１８）
【００３８】
これらのベースは、長さ２３６及びレート２３５／２３６のインターリーブされたフィボナッチ・コードを提供する。その結果得られるＰＲＭＬコードは、コードワード内、及び連結されたコードワードのコードワード境界をまたいで、Ｉ＝７且つＧ＝１４の制約を満足する。このＰＲＭＬコードは、少なくとも１６ビット分の位置だけ離間された任意の所望の位置における、８ビットのＲＳパリティ・バイトの部分的シンボル・インターリーブ（ｐａｒｔｉａｌ  ｓｙｍｂｏｌ  ｉｎｔｅｒｌｅａｖｉｎｇ）をサポートする。このような無制約バイトの挿入により、変調制約はＩ＝１１且つＧ＝２２に緩和される。Ｎ＝１１８よりも少ないベース要素を使用することによって得られるＰＲＭＬコードは、より長いコードと同じ変調制約を満足し、また、同じ制約が課されるＰＲＭＬコードでは、短いコードほど容易に構築することができる（例えば、レート２２３／２２４のコード）。
【００３９】
２つ目及び３つ目のコードでは、Ｐ＝３とする。この形式、即ち（２Ｎ−３）／２Ｎのコード・レートを選択することにより、それぞれ長さ２００及び４００の非常に高いレートの２つのコードを設計することが可能となる。そのうちの１つは、レート１９７／２００のＰＲＭＬ（Ｇ＝１０，Ｉ＝５）コードである。このコードは、Ｎ＝１００且つｊ＝５のとき、図６の表に示されるように基礎となる一般化フィボナッチ・コードのベース及びｊプロファイルによって完全に定義される。もう１つは、レート３９７／４００のＰＲＭＬ（Ｇ＝１２，Ｉ＝６）コードである。このコードに関しては、Ｎ＝１００且つｊ＝６のときの基礎となる一般化フィボナッチ・コードのベースが図７の表に示されている。基礎となるフィボナッチ・コードのｊ制約プロファイルは、コードワード内でｊ（ｎ）＝６、即ち、ｎ＝６，７，．．．，１９９となる。各境界では、それぞれ以下のｊ制約が適用される。
左側の境界：ｊ（１）＝１，ｊ（２）＝２，ｊ（３）＝３，ｊ（４）＝３，ｊ（５）＝４，ｊ（６）＝５
右側の境界：ｊ（２００）＝３
それ故、ｊ＝６の制約は、コードワード内及びコードワード境界をまたいで適用される。したがって、結果として得られるＰＲＭＬコードは、コードワード内及びコードワード境界をまたいで、制約Ｇ＝１２且つＩ＝６を満足する。
【００４０】
上述の３つのコードは、図８の比較表で証明されるように、それぞれ以下の特徴的な特性を有する：ＰＲＭＬ（Ｇ＝１４、Ｉ＝７）コードは、最も高いレートとなるが、最も緩い制約が課される；ＰＲＭＬ（Ｇ＝１０、Ｉ＝５）コードは、最も厳しい制約が課されるが、最も低いレートとなる；ＰＲＭＬ（Ｇ＝１２、Ｉ＝６）コードは、中間の強度の制約が課され、ＰＲＭＬ（Ｇ＝１４，Ｉ＝７）コードとほぼ同様のレートを達成する点で、他の２つのコードの良好な妥協点となる。３つのコードはすべて、適切に離間された任意の挿入位置における、無制約パリティ・シンボルの部分的シンボル・インターリーブをサポートする。
【００４１】
以上、本発明の好ましい諸実施形態について説明してきたが、これらの実施形態には本発明の範囲から逸脱しない限り様々な変更及び修正を施すことができる。
【図１】
2011503762.tif 000005
【図２】
2011503762.tif 000006
【図３】
2011503762.tif 000007
【図４】
2011503762.tif 000008
【図５】
2011503762.tif 000009
【図６】
2011503762.tif 000010
【図７】
2011503762.tif 000011
【図８】
2011503762.tif 000012
【手続補正書】
【提出日】平成22年6月16日(2010.6.16)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
２進入力データ・ストリームの変調コーディング方法であって、
入力ビット・ストリームの奇数インターリーブ及び偶数インターリーブにおける一般化フィボナッチ・コードをそれぞれ同時にエンコードするように動作可能な４進列挙型エンコーディング・アルゴリズムを前記入力ビット・ストリームに適用して、一連の４進出力シンボルを生成するステップと、
連続する各４進出力シンボルのビットをインターリーブして出力ビット・ストリームを生成するステップと、
を含む方法。
【請求項２】
前記４進出力シンボルの前記ビットを反転させて（Ｇ，Ｉ）制約された出力ビット・ストリームを生成するステップを含む、請求項１に記載の方法。
【請求項３】
前記４進列挙型エンコーディング・アルゴリズムは、前記奇数インターリーブ及び偶数インターリーブにおける同じフィボナッチ・コードを同時にエンコードするように動作可能である、請求項１に記載の方法。
【請求項４】
前記フィボナッチ・コードのベース又は各フィボナッチ・コードのベースは、限られたスパンを有する、請求項１に記載の方法。
【請求項５】
一連の２Ｎビットのコードワードを含む出力ビット・ストリームは、前記入力ビット・ストリーム内の一連のＭビットのワードから生成され、前記４進列挙型エンコーディング・アルゴリズムは、Ｍビットのワード毎に、入力値を前記Ｍビットのワードの値に初期化するステップと、その後ｉ＝１〜Ｎの反復ｉ毎に、
（ａ）可能な入力値の範囲を４つの部分範囲に区分化する区分化指標を計算するステップと、
（ｂ）前記入力値と前記区分化指標とを比較して、前記入力値がどの前記部分範囲に含まれるかを判定するステップと、
（ｃ）前記入力値が含まれる前記部分範囲に依存する値の４進出力シンボルを生成するステップと、
（ｄ）前記入力値から前記入力値が含まれる前記部分範囲の下位境界値を減じることによって前記入力値を更新するステップと、
を含む、請求項１に記載の方法。
【請求項６】
前記区分化指標は、前記反復ｉの数に応じて選択されるフィボナッチ・ベースにそれぞれ依存する部分的辞書式指標の第１の対及び第２の対から計算される、請求項５に記載の方法。
【請求項７】
Ｍ＝２Ｎ−１である、請求項５に記載の方法。
【請求項８】
Ｎ＝１１８であり、前記４進列挙型エンコーディング・アルゴリズムは、前記奇数インターリーブ及び偶数インターリーブにおける、ｊ＝７の制約と、以下によって定義される限られたスパンＬ＝９のベースと、を有する同じ一般化フィボナッチ・コードをエンコードするように動作可能である、請求項７に記載の方法。
Ｂｎ２９＝５１２  （但し、ｎ＝１，２，．．．，５）
Ｂｎ２９＝４９６  （但し、ｎ＝６，７，．．．，９）
Ｂｎ２９＝５０５−ｎ  （但し、ｎ＝１０，１１，．．．，１１８）
【請求項９】
Ｍ＝２Ｎ−３である、請求項５に記載の方法。
【請求項１０】
Ｎ＝１００であり、前記４進列挙型エンコーディング・アルゴリズムは、前記奇数インターリーブ及び偶数インターリーブにおける、ｊ＝５の制約と、図６の表で定義される限られたスパンＬ＝９のベースと、を有する同じ一般化フィボナッチ・コードをエンコードするように動作可能である、請求項９に記載の方法。
【請求項１１】
Ｎ＝２００であり、前記４進アルゴリズムは、前記奇数インターリーブ及び偶数インターリーブにおける、ｊ＝６の制約と、図７の表で定義される限られたスパンＬ＝９のベースと、を有する同じ一般化フィボナッチ・コードをエンコードするように動作可能である、請求項９に記載の方法。
【請求項１２】
請求項１に記載の変調コーディング方法によって生成される出力ビット・ストリームのデコーディング方法であって、
前記出力ビット・ストリームのビットをデインターリーブして一連の４進シンボルを生成するステップと、
４進列挙型デコーディング・アルゴリズムを前記４進シンボルに適用して、前記４進列挙型エンコーディング・アルゴリズムによって前記奇数インターリーブ及び偶数インターリーブに適用された前記一般化フィボナッチ・コードを同時にデコードし、それによって前記２進入力データ・ストリームを復元するステップと、
を含む方法。
【請求項１３】
２進入力データ・ストリームの変調コーディング装置であって、
入力ビット・ストリームの奇数インターリーブ及び偶数インターリーブにおける一般化フィボナッチ・コードをそれぞれ同時にエンコードするように動作可能な４進列挙型エンコーディング・アルゴリズムを前記入力ビット・ストリームに適用して、一連の４進出力シンボルを生成する４進エンコーダと、
連続する各４進出力シンボルのビットをインターリーブして出力ビット・ストリームを生成するマルチプレクサと、
を備える装置。
【請求項１４】
前記４進出力シンボルの前記ビットを反転させて（Ｇ，Ｉ）制約された出力ビット・ストリームを生成するインバータを含む、請求項１３に記載の装置。
【請求項１５】
前記４進エンコーダは、前記奇数インターリーブ及び偶数インターリーブにおける同じフィボナッチ・コードを同時にエンコードするように適合される、請求項１３に記載の装置。
【請求項１６】
前記フィボナッチ・コードのベース又は各フィボナッチ・コードのベースは、限られたスパンを有し、前記４進エンコーダは、幅２Ｌ＋２のスライディング・ウィンドウ・エンコーダとして動作するように適合される、請求項１３に記載の装置。
【請求項１７】
前記４進エンコーダは、前記出力ビット・ストリームが一連の２Ｎビットのコードワードを含むように、前記入力ビット・ストリーム内の一連のＭビットのワードをエンコードするように適合され、また、Ｍビットのワード毎に、入力値を前記Ｍビットのワードの値に初期化するステップと、その後ｉ＝１〜Ｎの反復ｉ毎に、
（ａ）可能な入力値の範囲を４つの部分範囲に区分化する区分化指標を計算するステップと、
（ｂ）前記入力値と前記区分化指標とを比較して、前記入力値がどの前記部分範囲に含まれるかを判定するステップと、
（ｃ）前記入力値が含まれる前記部分範囲に依存する値の４進出力シンボルを生成するステップと、
（ｄ）前記入力値から前記入力値が含まれる前記部分範囲の下位境界値を減じることによって前記入力値を更新するステップと、
を含む４進アルゴリズムを適用するように適合される、請求項１３に記載の装置。
【請求項１８】
前記４進エンコーダは、前記区分化指標を、前記反復ｉの数に応じて選択されるフィボナッチ・ベースにそれぞれ依存する部分的辞書式指標の第１の対及び第２の対から計算するように適合される、請求項１７に記載の装置。
【請求項１９】
Ｍ＝２Ｎ−１である、請求項１７に記載の装置。
【請求項２０】
Ｎ＝１１８であり、前記４進エンコーダは、前記奇数インターリーブ及び偶数インターリーブにおける、ｊ＝７の制約と、以下によって定義される限られたスパンＬ＝９のベースと、を有する同じ一般化フィボナッチ・コードをエンコードするように適合される、請求項１９に記載の装置。
Ｂｎ２９＝５１２  （但し、ｎ＝１，２，．．．，５）
Ｂｎ２９＝４９６  （但し、ｎ＝６，７，．．．，９）
Ｂｎ２９＝５０５−ｎ  （但し、ｎ＝１０，１１，．．．，１１８）
【請求項２１】
Ｍ＝２Ｎ−３である、請求項１７に記載の装置。
【請求項２２】
Ｎ＝１００であり、前記４進エンコーダは、前記奇数インターリーブ及び偶数インターリーブにおける、ｊ＝５の制約と、図６の表で定義される限られたスパンＬ＝９のベースと、を有する同じ一般化フィボナッチ・コードをエンコードするように適合される、請求項２１に記載の装置。
【請求項２３】
Ｎ＝２００であり、前記４進エンコーダは、前記奇数インターリーブ及び偶数インターリーブにおける、ｊ＝６の制約と、図７の表で定義される限られたスパンＬ＝９のベースと、を有する同じ一般化フィボナッチ・コードをエンコードするように適合される、請求項２１に記載の装置。
【請求項２４】
請求項１３に記載の変調コーディング装置によって生成される出力ビット・ストリームのデコーディング装置であって、
前記出力ビット・ストリームのビットをデインターリーブして一連の４進シンボルを生成するデマルチプレクサと、
４進列挙型デコーディング・アルゴリズムを前記４進シンボルに適用して、前記４進列挙型エンコーディング・アルゴリズムによって前記奇数インターリーブ及び偶数インターリーブに適用された前記一般化フィボナッチ・コードを同時にデコードし、それによって前記２進入力データ・ストリームを復元する４進デコーダと、
を備える装置。
【請求項２５】
データ・ストレージ・システムであって、
一連のＭビットのワードを含む２進入力データ・ストリームを変調コーディングして一連の２Ｎビットのコードワードを含む出力ビット・ストリームを生成する、請求項１３に記載の変調コーディング装置と、
ストレージ・メディアと、前記一連のコードワードを前記ストレージ・メディア上に記録し、前記ストレージ・メディアを読み取って再生信号を生成する記録／再生機構と、を備える記録チャネルと、
前記再生信号内の一連の２Ｎビットのワードを検出する検出装置と、
検出された前記２Ｎビットのワードのビットをデインターリーブして一連の４進シンボルを生成するデマルチプレクサと、
４進列挙型デコーディング・アルゴリズムを各２Ｎビットのワードの前記４進シンボルに適用して、前記４進列挙型エンコーディング・アルゴリズムによって前記奇数インターリーブ及び偶数インターリーブに適用された前記一般化フィボナッチ・コードを同時にデコードし、それによって一連のＭビットのデータ・ワードを生成する４進デコーダと、
を備えるデータ・ストレージ・システム。
【請求項２６】
請求項２５に記載のデータ・ストレージ・システムを備えるテープ・ドライブであって、前記ストレージ・メディアは、磁気テープを含む、テープ・ドライブ。
【請求項２７】
データ・ストレージ・システムであって、
一連のＭビットのワードを含む２進入力データ・ストリームを変調コーディングして一連の２Ｎビットのコードワードを含む出力ビット・ストリームを生成する、請求項１４に記載の変調コーディング装置と、
前記変調コーディング装置からの前記出力ビット・ストリームを１／（１＋Ｄ２）コーディングしてプレコード済みビット・ストリームを生成するプレコーダと、
前記プレコード済みビット・ストリームをエラー訂正コーディングしてＥＣＣコード化ビット・ストリームを生成するＥＣＣコーダと、
ストレージ・メディアと、前記ＥＣＣコード化ビット・ストリームを前記ストレージ・メディア上に記録し、前記ストレージ・メディアを読み取って再生信号を生成する記録／再生機構と、を備える記録チャネルと、
前記再生信号内の一連の２Ｎビットのワードを検出する検出装置であって、検出された前記２Ｎビットのワード内のエラーを訂正するＥＣＣデコーダを含む検出装置と、
検出された前記２Ｎビットのワードのビットをデインターリーブして一連の４進シンボルを生成するデマルチプレクサと、
４進列挙型デコーディング・アルゴリズムを各２Ｎビットのワードの前記４進シンボルに適用して、前記４進列挙型エンコーディング・アルゴリズムによって前記奇数インターリーブ及び偶数インターリーブに適用された前記一般化フィボナッチ・コードを同時にデコードし、それによって一連のＭビットのデータ・ワードを生成する４進デコーダと、
を備えるデータ・ストレージ・システム。
【請求項２８】
請求項２７に記載のデータ・ストレージ・システムを備えるテープ・ドライブであって、前記ストレージ・メディアは、磁気テープを含む、テープ・ドライブ。
【請求項２９】
ストレージ・メディア上に記録されたデータを、請求項１に記載の変調コーディング方法を実施する記録システムによって再生するデータ再生システムであって、
前記ストレージ・メディアを読み取って再生信号を生成する読み取り機構と、
前記再生信号内の一連の２Ｎビットのワードを検出する検出装置と、
検出された前記２Ｎビットのワードのビットをデインターリーブして一連の４進シンボルを生成するデマルチプレクサと、
４進列挙型デコーディング・アルゴリズムを各２Ｎビットのワードの前記４進シンボルに適用して、前記変調コーディング方法の前記４進列挙型エンコーディング・アルゴリズムによって前記奇数インターリーブ及び偶数インターリーブに適用された前記一般化フィボナッチ・コードを同時にデコードし、それによって一連のＭビットのデータ・ワードを生成する４進デコーダと、
を備えるデータ再生システム。
【国際調査報告】
2011503762.tif 000013
2011503762.tif 000014