説明

ビット・ストリームの変調コーディング及びデコーディング方法、装置、及びシステム(変調コーディング及びデコーディング)

【課題】 2進入力データ・ストリームの変調コーディング方法及び装置を提供する。
【解決手段】 4進列挙型エンコーディング・アルゴリズムが前記入力ビット・ストリームに適用され、それによって一連の4進出力シンボルが生成される。前記4進アルゴリズムは、前記入力ビット・ストリームの奇数インターリーブ及び偶数インターリーブにおけるフィボナッチ・コードをそれぞれ同時にエンコードするように動作可能である。次に、連続する各4進出力シンボルのビットがインターリーブされ、それによってグローバル・ラン・レングス制約及びインターリーブ・ラン・レングス制約を有する出力ビット・ストリームが生成される。前記4進出力シンボルのビット反転により、逆連結変調システムで使用されるPRML(G,I)コードの場合と同様に、(G,I)制約を有する出力ビット・ストリームが生成される。対応するデコーディング・システムも提供される。

【発明の詳細な説明】
【技術分野】
【0001】
本発明は一般に、入力データの変調コーディング方法及び装置ならびに対応する変調デコーディング・システムに関するものである。
【背景技術】
【0002】
変調コードは、データ・ストレージ・システムにおいてデータ記録時の望ましくないビット・シーケンス、例えば再生プロセス中にエラーを生じさせるビット・シーケンスを除去するのに使用される。望ましくないビット・シーケンスの一例は、同じ値のビットの長いラン(run)である。別の例は、同じ値のビットがビット・ストリーム内の交互位置に現れる、即ち、ビット・ストリームの奇数(O)インターリーブ又は偶数(E)インターリーブ(...EOEOEO...)の形をとる、同じ値のビットの長いランである。例えば、0a0b0c0d0...(a、b、c等は0又は1のいずれかであり得る)の形式の長いシーケンスは、一般に望ましくないはずである。変調コードは、エンコードされたビット・ストリーム内の望ましくないビット・シーケンスの発生に対して何らかの形の制約を課す。例えば、変調コードの中にはいわゆるJ制約を課すものがあり、それによってエンコードされたビット・ストリーム内の連続する「1」の最大ラン・レングスは、所定値jに制限される。変調コードの中には連続する「0」の最大ラン・レングスに制約を課すものもある。この制約は、k制約又はG制約と呼ばれるが、それによって連続する「0」の最大ラン・レングスは、それぞれ値k又はGに制限される。後者のコード・タイプの一例は、PRML(partial‐response maximum likelihood:部分応答最尤法)ベースのテープ・ドライブや光ストレージ・システムのような記録システムで使用されるPRML(G,I)コードによって提供される。これらのコードは、「グローバル(global)」制約、即ちG制約に加えて「インターリーブ(interleave)」制約、即ちI制約も課す。これにより、奇数インターリーブ及び偶数インターリーブのそれぞれにおける「0」の最大ラン・レングスは、値Iに制限される。無論、I制約されたビット・ストリームは、G=2Iの場合は必然的にG制約される。
【0003】
PRML(G,I)コードは、変調コーディングがエラー訂正コーディング(ECC)に先立って実行される逆連結(reverse concatenation:RC)変調方式で特に有用である。RC方式では、ECCデコーダが変調デコーダよりも先に再生動作を行うので、エラー伝搬が低減される。即ち、ECCデコーダでエラーが発生しなければ、変調デコーダへのエラー伝搬も発生しない。それ故、RCを用いると長い変調コード(即ち、コードワード長が長いコード)の使用が可能となり、その結果、選択された制約の容量付近で動作する高レート・コード及びエンコーダの設計が容易となる。しかしながら、PRML(G,I)コードを利用するにあたっては、効率的なエンコーディング及びデコーディング・アルゴリズムに基づく実用的な実装環境が必要となる。
【0004】
米国特許第5,760,718号には、エンコードされたビット・ストリームにk制約を課す実用的なエンコーダが開示されている。このエンコーダは、一般化(generalized)フィボナッチ・コードのクラスに基づく列挙型エンコーディング(enumerative encoding)技法を実施する。列挙型エンコーディングは、「“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」に記載されている。詳細な論述は、上記の各文献を参照していただきたい。本明細書では、以下で説明する本発明の理解を助けるために、これらの技法の簡単な説明を行うことが有用であろう。
【0005】
簡単に言うと、列挙型エンコーディングは、出力コードワードの辞書式順序に基づいて、入力ワードを出力コードワードにマッピングするプロセスである。即ち、X個の2進コードワードのセットが2進値に従って順序付けされる場合、各コードワードには、順序付けされたセット内のそれぞれの位置に従って1〜Xの番号を割り当てることができる。次に、このように割り当てられた1〜Xの各番号によって2進入力ワードの値を定義する場合、X個の各2進入力ワードは、それぞれ対応するコードワードと関連付けられる。列挙型エンコーディングは、このタイプの方式に従って入力ワードを出力コードワードにマッピングするプロセスである。基礎となるエンコード原理はごく単純なものであるが、コードワードを2進入力ワードから生成する効率的なエンコーダの設計には、実用上の問題がある。例えば、2100個のコードワードが存在する場合、効率的なエンコーダ設計が必要とされることは容易に理解されるだろう。
【0006】
フィボナッチ・コードは、2進コードワード表現の各位置において2進数の「1」の値を定義する、ベース(base)とも呼ばれる重みのセットによって特徴付けられる。即ち、2進コードワード内の所与の位置における「1」は、通常の2のべき乗ではなく当該位置のフィボナッチ・ベースの値を表す。簡単な一例として、{w}={1,2,3,5,8,13,21}によって与えられるN=7のベース・セットによってフィボナッチ・コードが定義される場合を考える。各ベースは、以下の線形回帰を満足することが分かる。
n+1=w+wn−1 (但し、n=2,3,...,6)
(N=7)ビットの完全なフィボナッチ・コードワード・セットは、wN+1=13+21=34の可能な値を表すことができる。34≧2である故に、この簡単なフィボナッチ・コードは、5ビットの入力を、列挙型エンコーディング・プロセスによって長さN=7のコードワードにエンコードすることができる。このエンコード・プロセスは、次式によって定義される。
u=ΣxN−i+1 (但し、i=1〜7)
上式で、uは入力ワード値であり、(x,x,...,x)は出力コードワードである。このエンコード・プロセスは、図1に示されるように入力ワード値からフィボナッチ・ベースを連続的に減じることによって実行される。具体的には、数uは、値の降順に取り出される、負の結果を与えない任意のベースwによって連続的に減じられる。その一連の差(running difference)から実際に所与の重みwN−i+1を減じると、x=1となる。そうでなければ、x=0となる。
【先行技術文献】
【特許文献】
【0007】
【特許文献1】米国特許第5,760,718号
【特許文献2】米国特許第7,064,687号
【特許文献3】米国特許第7,071,851号
【非特許文献】
【0008】
【非特許文献1】“Enumerative Source Encoding”, T.M.Cover, IEEE Trans. Inform. Theory, Vol. 19, pp. 73-77, January 1973
【非特許文献2】“Fibonacci Codes forSynchronisation Control”, W.H. Kautz, IEEE Trans. Inform. Theory, Vol. 11, pp. 284-292,April 1965
【発明の概要】
【発明が解決しようとする課題】
【0009】
図1を考察すると、上記の簡単なフィボナッチ・コードはj=1の制約を課すこと、即ち、あるコードワードにおいて「1」が2つ以上連続して発生することはないことが証明される。一般化フィボナッチ・コードを用いると、n=1〜Nのとき、ベースwは以下の線形回帰(不等式)を満足する。
n+1≦w+wn−1+...+wn−j (但し、n=j+1,j+2,...,N−1)
上式で、指定された正の整数jは、上記のコードのj制約を定義する。このような一般化フィボナッチ・コードにおけるコードワードの最大数は、次式によって与えられる。
N+1=w+wN−1+...+wN−j
図1の簡単なコードの場合と同様に、一般化フィボナッチ・コードにおける2進コードワード(x,x,...,x)は、入力u(0≦u<wN+1)をベース{w}で表すことによって、即ち、u=ΣxN−i+1によって得られる。実装においては、前述の米国特許第5,760,718号に記載されるように、各ベースは限られたスパンLを有するように、即ち、
=Bn−1
となるように選択される。上式で、Bは2−L≦B≦1の範囲であり、Lビット表現を有する。スパンLのベースを用いると、エンコードは、Σuの最上位ビットから最下位ビットに及ぶ(L+1)ビットの幅広いウィンドウを使用して、スライディング・ウィンドウ形式で実行することができる。
【0010】
米国特許第7,064,687号及び同第7,071,851号には、前述の米国特許第5,760,718号と同様の列挙型エンコーディング概念に基づいてPRML(G,I)コード向けに設計されたエンコーダ及びデコーダが開示されている。これらは、一般化フィボナッチ・コードに由来するものである。具体的には、入力ビット・ストリームが奇数インターリーブと偶数インターリーブに分離され、それらの2つのインターリーブ・ビット・ストリームは、個別のフィボナッチ・エンコーダによってエンコードされる。フィボナッチ・コードは「1」のランにj制約を課すので、エンコーダ出力のビット反転により、それぞれ「0」のランに対する制約を有する2つのエンコードされたビット・ストリームが得られる。次に、それらのエンコードされたビット・ストリームは、G=2I(但し、Iは元のフィボナッチ・コードのjの値と等しい)の場合に(G,I)制約された単一の出力ビット・ストリームが与えられるように、マルチプレクサによってインターリーブされる。米国特許第7,064,687号の変調エンコーダでは、奇数インターリーブと偶数インターリーブの分離に先立って入力データ・ビットのサブセットをエンコードするために、ショート・ブロック・エンコーダが必要となる。このため、入力ビット・ストリームには2つのフィボナッチ・エンコーダに対する可能な入力を制限する初期制約が課される。これによって実用的な実装環境が提供されるが、ショート・ブロック・コード向けの効率的なブール論理が必要とされる故に、結果として得られるPRML(G,I)コードの高レートの達成は、非常に困難である。
【課題を解決するための手段】
【0011】
本発明の第1の態様は、2進入力データ・ストリームの変調コーディング方法を提供する。前記方法は、
前記入力ビット・ストリームの奇数インターリーブ及び偶数インターリーブにおける一般化フィボナッチ・コードをそれぞれ同時にエンコードするように動作可能な4進列挙型(4‐ary enumerative)エンコーディング・アルゴリズムを前記入力ビット・ストリームに適用して、一連の4進出力シンボルを生成するステップと、
連続する各4進出力シンボルのビットをインターリーブして出力ビット・ストリームを生成するステップと、
を含む。
【0012】
先述のとおり、従来技術の技法では、2つの個別の2進エンコーディング・アルゴリズムが入力ビット・ストリームの分離された奇数インターリーブ及び偶数インターリーブに独立して作用する。一方、本発明の変調技法では、4進列挙型エンコーディング・アルゴリズムは、(O/Eインターリーブされた)入力ビット・ストリームを形成する一連の2進入力ビットに作用して、奇数インターリーブ及び偶数インターリーブを、4進出力シンボルを有する単一の列挙型コードとして同時にフィボナッチ・エンコードする。この単一のコードは、本明細書では「インターリーブされたフィボナッチ・コード(interleaved Fibonacci code)」と呼ばれる。それ故、上述の列挙型エンコーディングの原理によれば、インターリーブされたフィボナッチ・コードの4進アルゴリズムは、入力ビット・ストリームのMビットのワードを、値に応じて、4進シンボルを有する1組の順序付けされた出力コードワードにマッピングする。4進シンボルは、それぞれ2つの並列ビットで表される。その後、これらのビットは、一連の出力シンボル用にインターリーブされ、その結果、フィボナッチ・エンコードされた奇数インターリーブ及び偶数インターリーブを伴う2進出力ストリームが生成される。先述のフィボナッチ・コード固有の特性により、グローバル・ラン・レングス制約及びインターリーブ・ラン・レングス制約を有する出力ビット・ストリームが提供される。「1」の最大ラン・レングスに対する制約が必要となる応用例も想定され得るが、ビット反転によって上述のPRMLコードに適した(G,I)制約が得られる。
【0013】
上記から分かるように、出力ビット・ストリームの奇数インターリーブと偶数インターリーブの両方を生成する上で、従来技術では2つのエンコーダが必要とされるのに比べて、本発明の変調技法では単一の4進列挙型エンコーダがあれば足りる。また、ショート・ブロック・エンコーダも必要とされない。更に、本発明の変調技法を用いると、基礎となる一般化フィボナッチ・コードのすべてのコードワードを余すことなく利用することが可能となり、それ故、PRML(G,I)コードの可能な最大長さを容易に実現することができる。これにより、PRMLコードの可能な最高レートが達成される。一方、米国特許第7,064,687号の変調エンコーダを用いる場合は、特に13/14を上回るレートではショート・ブロック・コード向けの効率的なブール論理の設計が困難である故に、このような最大長さの達成は非常に困難となる可能性がある。
【0014】
本発明は、4進出力シンボルのビットが反転されたPRMLコードのような応用例においても、シンボル・ビットのインターリーブ前あるいはインターリーブ後に実行可能であることは言うまでもない。
【0015】
一般に、4進アルゴリズムによって出力のO/Eインターリーブの形でエンコードされるフィボナッチ・コードは、異なるコードであることも同じコードであることもあるが、多くの場合同じコードが使用される。いずれにせよ、好ましい諸実施形態では、基礎となるフィボナッチ・コード(単数又は複数)のベースが限られたスパンを有するので、エンコード・プロセスをスライディング・ウィンドウ形式で実行することが可能となる。
【0016】
本発明の第2の態様は、本発明の第1の態様に係る変調コーディング方法によって生成される出力ビット・ストリームのデコーディング方法を提供する。前記デコーディング方法は、
前記出力ビット・ストリームのビットをデインターリーブして一連の4進シンボルを生成するステップと、
4進列挙型デコーディング・アルゴリズムを前記4進シンボルに適用して、前記4進エンコーディング・アルゴリズムによって前記奇数インターリーブ及び偶数インターリーブに適用された前記一般化フィボナッチ・コードを同時にデコードし、それによって前記2進入力データ・ストリームを復元するステップと、
を含む。
【0017】
本発明の第3の態様は、2進入力データ・ストリームの変調コーディング装置を提供する。前記変調コーディング装置は、
前記入力ビット・ストリームの奇数インターリーブ及び偶数インターリーブにおける一般化フィボナッチ・コードをそれぞれ同時にエンコードするように動作可能な4進列挙型エンコーディング・アルゴリズムを前記入力ビット・ストリームに適用して、一連の4進出力シンボルを生成する4進エンコーダと、
連続する各4進出力シンボルのビットをインターリーブして出力ビット・ストリームを生成するマルチプレクサと、
を備える。
【0018】
本発明の第4の態様は、本発明の第3の態様に係る変調コーディング装置によって生成される出力ビット・ストリームのデコーディング装置を提供する。前記デコーディング装置は、
前記出力ビット・ストリームのビットをデインターリーブして一連の4進シンボルを生成するデマルチプレクサと、
4進列挙型デコーディング・アルゴリズムを前記4進シンボルに適用して、前記4進エンコーディング・アルゴリズムによって前記奇数インターリーブ及び偶数インターリーブに適用された前記一般化フィボナッチ・コードを同時にデコードし、それによって前記2進入力データ・ストリームを復元する4進デコーダと、
を備える。
【0019】
本発明の第5の態様は、データ・ストレージ・システムであって、
一連のMビットのワードを含む2進入力データ・ストリームを変調コーディングして一連の2Nビットのコードワードを含む出力ビット・ストリームを生成する、本発明の第3の態様に係る変調コーディング装置と、
ストレージ・メディアと、前記一連のコードワードを前記ストレージ・メディア上に記録し、前記ストレージ・メディアを読み取って再生信号(reproduced signal)を生成する記録/再生機構と、を備える記録チャネルと、
前記再生信号内の一連の2Nビットのワードを検出する検出装置と、
検出された前記2Nビットのワードのビットをデインターリーブして一連の4進シンボルを生成するデマルチプレクサと、
4進列挙型デコーディング・アルゴリズムを各2Nビットのワードの前記4進シンボルに適用して、前記4進エンコーディング・アルゴリズムによって前記奇数インターリーブ及び偶数インターリーブに適用された前記一般化フィボナッチ・コードを同時にデコードし、それによって一連のMビットのデータ・ワードを生成する4進デコーダと、
を備えるデータ・ストレージ・システムを提供する。
【0020】
かかるデータ・ストレージ・システムにおいて、前記変調装置において生成される前記一連の2Nビットのコードワードは、典型的には前記チャネルに記録される前に、PRMLシステムの場合のプレコードやECCコーディングのような他の様々な処理ステップを経ることになる。好ましい諸実施形態では、逆連結変調方式においてPRML(G,I)コードが利用される。これにより、前記データ・ストレージ・システムは、前記変調コーディング装置からの前記出力ビット・ストリームを1/(1+D)コーディングしてプレコード済みビット・ストリーム(precoded bit‐stream)を生成するプレコーダと、前記プレコード済みビット・ストリームをエラー訂正コーディングして、前記記録チャネルに供給されるECCコード化ビット・ストリーム(ECC‐coded bit‐stream)を生成するECCコーダと、を含む。また、前記検出装置は、前記再生信号内で検出された前記2Nビットのワード内のエラーを訂正するECCデコーダを含む。
【0021】
無論、記録メディアの読み取りは許可されるが書き込みは許可されない、読み取り専用CD又はDVDプレーヤ等のシステムも想定され得る。そのため、かかるシステムでは、対応するエンコーディング装置を伴わずに本発明を実施するデコーディング装置が利用され得る。特に、本発明の第6の態様は、ストレージ・メディア上に記録されたデータを、本発明の第1の態様に係る変調コーディング方法を実施する記録システムによって再生するデータ再生システムを提供する。前記データ再生システムは、
前記ストレージ・メディアを読み取って再生信号を生成する読み取り機構と、
前記再生信号内の一連の2Nビットのワードを検出する検出装置と、
検出された前記2Nビットのワードのビットをデインターリーブして一連の4進シンボルを生成するデマルチプレクサと、
4進列挙型デコーディング・アルゴリズムを各2Nビットのワードの前記4進シンボルに適用して、前記変調コーディング方法の前記4進エンコーディング・アルゴリズムによって前記奇数インターリーブ及び偶数インターリーブに適用された前記一般化フィボナッチ・コードを同時にデコードし、それによって一連のMビットのデータ・ワードを生成する4進デコーダと、
を備える。
【0022】
本明細書では一般に、各特徴が本発明の一態様の諸実施形態に関して説明されるが、それらに対応する特徴が本発明の別の態様の諸実施形態で提供されてもよい。
【0023】
以下では単なる例示として、添付図面を参照しながら本発明の好ましい諸実施形態について説明する。
【図面の簡単な説明】
【0024】
【図1】簡単なフィボナッチ・コードを使用したエンコード・プロセスを示す図である。
【図2】本発明を実施するデータ処理システムの概略ブロック図である。
【図3】図2のシステムの変調エンコーダのブロック図である。
【図4】図2のシステムの変調デコーダのブロック図である。
【図5】図3の変調エンコーダによって実施されるエンコーディング・アルゴリズムの動作において実行される処理ステップの内訳を示す図である。
【図6】図3の変調エンコーダの諸実施形態で利用されるフィボナッチ・コードのベースを表形式で示す図である。
【図7】図3の変調エンコーダの諸実施形態で利用されるフィボナッチ・コードのベースを表形式で示す図である。
【図8】変調エンコーダの諸実施形態で利用される3つのPRML(G,I)コードを比較した図である。
【発明を実施するための形態】
【0025】
図2のブロック図は、本発明を実施するデータ記憶システムの概略図であり、記録/再生プロセスに関与する主要なコンポーネントを示す。本実施形態において、データ記憶システムは、全体的に1で示されるテープ・ドライブであり、それ故、磁気テープ4の読み書きを行う読み取り/書き込みヘッド3を備えた記録チャネル2を有する。記録側において、テープ・ドライブ1は、PRML(G,I)エンコーダ5、プレコーダ(precoder)6、及び全体的に7で示されるECCコーダの形をとる変調コーディング装置を有する。ECCコーダ7は、RC(Reed‐Solomon:リード・ソロモン)パリティ・ジェネレータ8と、部分的インターリーバ(partial interleaver)9とから構成される。再生側において、テープ・ドライブ1は、全体的に11で示され、検出器12及びECCデコーダ13を備える検出装置と、変調デコーダ14と、を含む。
【0026】
動作において、記録対象データは、一連のMビットのデータ・ワードを含む入力ビット・ストリームの形でPRML(G,I)エンコーダ5に供給される。PRML(G,I)エンコーダ5は、後で詳述する入力データの変調コーディングを実行して、一連の2Nビットのコードワードを含む(G,I)制約されたエンコード済みビット・ストリームを生成する。通常のPRML(G,I)コードに基づく変調システムの場合と同様に、エンコードされたビット・ストリームはその後、プレコーダ6によって1/(1+D)プレコードされる。この場合の「+」は、2を法とする加法を示す。先述した逆連結の概念によれば、ECCコーディングは本実施形態の変調コーディングの後に実行される。本例において、ECCコーディングは、プレコーダ6からのコードワード・ストリームにおけるパリティ・シンボルの部分的インターリーブを行う。無制約のRSパリティ・シンボルは、パリティ・ジェネレータ8によって2Nビットのコードワードから既知の手法で生成される。次に、これらのシンボルは、部分的インターリーバ9によってエンコードされたビット・ストリーム内の所望の地点に挿入される。次に、その結果得られるECCコード化ビット・ストリームは、チャネル2内の通常の信号処理を経て磁気テープ4上に記録される。再生時は、磁気テープ4によって取得された再生信号が通常の再生信号処理を経て検出器12に供給される。検出器12は、典型的にはビタビ(Viterbi)検出器のようなソフト入力/ハード出力検出器、又は各記録ビットの尤度尺度を提供し、再生信号内の2Nビットのワードを既知の手法で検出するソフト入力/ソフト出力検出器である。次に、パリティ検査及びエラー訂正処理がECCデコーダ13によって既知の手法で実行される。次に、その結果得られる一連の2Nビットのワードが変調デコーダ14に供給され、変調デコーダ14は、後で詳述するように元の入力データに対応する一連のMビットのワードを生成するように動作する。
【0027】
次に図3及び図4を参照して、テープ・ドライブ1のPRML(G,I)エンコーダ5及び変調デコーダ14の動作について詳細に説明する。これらのコンポーネントは、原理的にはソフトウェアの形で実施することもハードウェアとソフトウェアの組合せで実施することもできるが、実用的な実装環境では簡潔さ及び処理速度の観点からハードウェア・ロジックの形で実施されることが好ましい。適切な実装環境は、本明細書の説明を読めば当業者には理解されるだろう。
【0028】
図3に示されるように、PRML(G,I)エンコーダ5は、4進列挙型エンコーダ16と、マルチプレクサ17と、インバータ18と、を備える。要約すると、4進列挙型エンコーダ16は、4進列挙型エンコーディング・アルゴリズムを入力ビット・ストリームに適用して、上記で定義したようなインターリーブされたフィボナッチ・コードを実装する。即ち、4進列挙型エンコーダ16は、入力ビット・ストリームの奇数インターリーブ及び偶数インターリーブにおける生成された各フィボナッチ・コードを、4進出力シンボルを有する単一の列挙型コードとして同時にエンコードするように動作する。4進列挙型エンコーダ16は、図3の太線で示されるように、入力ビット・ストリーム内のMビットのワード毎に一連のN個の4進出力シンボルを生成する。4進シンボルは、それぞれ2ビットで表される。次に、これらのビットは、一連の4進シンボルについてマルチプレクサ17によってインターリーブされ、それにより、入力されたMビットのワード毎に2Nビットの2進出力ストリームが生成される。次に、結果として得られる変調エンコード済みビット・ストリームが上述の(G,I)制約を満足する一連の2Nビットのコードワードから構成されるように、インバータ18によるビット変換が実行される。
【0029】
列挙型エンコーディングの原理によれば、4進列挙型エンコーダ16によって実施される4進列挙型エンコーディング・アルゴリズムは、入力されたMビットのワードを入力ワードの値に依存する4進コードワードに直接マッピングする。本実施形態の4進アルゴリズムは、4進列挙型エンコーダ16において、2進出力対(x,x)で表される1つの4進シンボルを反復ステップi毎に生成する反復プロセスとして適用される。このアルゴリズムは、インターリーブされたフィボナッチ・コードIFに関して、定義されたN個のベース{w}(n=1〜N)をそれぞれ有する2つの基礎となるフィボナッチ・コードを同時にエンコードするために、値uIF=Σu(k=0〜M−1)の入力ワード(uM−1,uM−2,...,u)をuIFに依存する4進コードワード((x,x),(x,x),...,(x,x))にマッピングする。特に、
0≦uIF<(wN+1
の範囲の入力が与えられた場合、アルゴリズムは以下のようになる。
【表1】

【0030】
上記を考察すると、このアルゴリズムは本質的に、入力値uをMビットのワード値uIFに初期化し、その後i=1〜Nの反復i毎に変数N00、N01、N10の値を計算し、入力値uとN00、N01、N10とを比較することによって出力シンボル(x,x)を生成するものであることが分かるだろう。変数N00、N01、N10は、可能な入力値uの範囲を反復毎に4つの部分範囲(sub‐range)、即ち、
u<N00
00≦u<N01
01≦u<N10;及び
u≧N10
に区分化する働きをするので、本明細書では「区分化指標(partitioning index)」と呼ばれる。
【0031】
反復毎の可能な入力値uの範囲は、0≦u<Uである。ここで、U及びUは、それぞれ更新前の反復iにおける奇数上限(odd upper bound)及び偶数上限(even upper bound)である。初期入力値uIFはMビットのワードであり、且つ0≦uIF<2≦(wN+1である故に、可能なMビットの値の範囲は、最初の反復i=1の区分化指標によって4つに区分化される。より詳細には、出力シンボル(x,x)の生成は、以下のステップを含む:
(a)区分化指標N00、N01、N10を計算するステップ;
(b)現在の入力値uと区分化指標とを比較して、当該入力値が上記で定義した4つの部分範囲のうちのどの部分範囲に含まれるかを判定するステップ;
(c)当該入力値がどの特定の部分範囲に含まれるかに従って、(x,x)の2ビットを設定するステップ;及び
(d)uの現在の値から当該uの値が含まれる部分範囲の下位境界値(lower boundary value)を減じることによって入力値を更新するステップ。(なお、この場合の下位境界値は0であるため、uが最も低い部分範囲に含まれる場合は、更新後も入力値は変更されないままである。)
【0032】
区分化指標N00、N01、N10は、「部分的辞書式指標(partial lexicographic index)」の第1の対v、v及び第2の対U、Uから計算される。以下、各指標v、vは「下位部分的辞書式指標(lower partial lexicographic index)」と呼ばれ、各上限U、Uは、「上位部分的辞書式指標(upper partial lexicographic index)」と呼ばれる。これらの値の各対は、その対の各値がそれぞれインバータ18からの2進出力ストリームの奇数インターリーブ及び偶数インターリーブのうちの1つと関連付けられ、したがって、実際にインターリーブされたフィボナッチ・コードの基礎となるフィボナッチ・コードの一方又は他方と関連付けられるという点で、「部分的」指標と呼ばれる。上記のアルゴリズムに示されるように、v、v及びU、Uの各対の部分的辞書式指標は、反復数iに応じて選択されるそれぞれのフィボナッチ・ベース(即ち、wN−i+1)に依存する。基礎となるフィボナッチ・コードが異なる場合は、一方のコードに由来する適切なベースがv、Uの計算に使用され、他方のコードに由来する適切なベースがv、Uの計算に使用されることに留意していただきたい。しかしながら、4進列挙型エンコーダ16の好ましい諸実施形態では、基礎となるフィボナッチ・コードは同じであり、以下では特に好ましい実例について説明する。更に、好ましい諸実施形態では、基礎となるフィボナッチ・コードは、先に定義した限られたスパンLのベースを有する。この場合、4進列挙型エンコーダ16は、当業者には理解されるように幅2L+2のスライディング・ウィンドウ・エンコーダとして動作する。
【0033】
図4は、PRML(G,I)エンコーダ5に対応する変調デコーダ14を示す。図示のとおり、変調デコーダ14は、インバータ20と、デマルチプレクサ21と、4進デコーダ22と、を備える。インバータ20は、再生信号から検出された一連の2Nビットのワードを受け取り、それらのビットを反転させて2進出力ストリームをデマルチプレクサ21に提供する。これにより、受信された2進ストリームの奇数ビット及び偶数ビットがデインターリーブ(de‐interleave)され、その結果、検出された2Nビットのワード毎に一連のN個の4進出力シンボル(x,x)が生成される。次に、N個の4進シンボルの各群は、4進デコーダ22によってデコードされ、その結果、元の入力データ・ストリーム内のMビットのワードに対応する出力対象のMビットのワードが復元される。4進デコーダ22は、4進列挙型エンコーダ16によって適用されるエンコーディング・アルゴリズムの逆を実施し、したがって4進列挙型デコーディング・アルゴリズムを適用して、4進列挙型エンコーダ16によって適用されるインターリーブされたフィボナッチ・コードの基礎となるフィボナッチ・コードを同時にデコードする。このアルゴリズムでは、連続する反復ステップにおいて連続する4進シンボル(x,x)のビット対が処理される。特に、奇数インターリーブ及び偶数インターリーブにおける基礎となるフィボナッチ・コードに対して、コードワードx,x,...,x、及びコードワードx,x,...,xが与えられた場合、アルゴリズムは以下のようになる。
【表2】

【0034】
先述のとおり、基礎となるフィボナッチ・コードが異なる場合、v,v及びU,Uの各対のベースwN−i+1は、奇数指標と偶数指標とで異なる可能性があり、また、各ベースが限られたスパンLを有する好ましい例では、デコーダは幅2L+2のスライディング・ウィンドウ・デコーダとして動作する。
【0035】
図5の表は、4進列挙型エンコーダ16の複雑さのレベルを、反復毎に必要とされる様々なタイプの処理ステップ数の内訳として示す。特に重要な(critical)複雑さは、必要とされる乗算の回数である。図5の表に示されるように、フィボナッチ・ベースが限られたスパンLを有する場合、(L+1)ビットの数の乗算は3回しか必要とされない。デコーディング・アルゴリズムでは(L+1)ビットの数の比較が必要とされないため、複雑さはずっと低くなる。ストレージ要件に関しては、奇数インターリーブ及び偶数インターリーブにおける基礎となるフィボナッチ・コードがスパンLのベースと同一である場合、4進列挙型エンコーダ16は、N個のLビット・ベース要素を記憶するだけでよい。また、デコーダは、Lビットの数である2N個の上位部分的辞書式指標を記憶する必要がある。
【0036】
上述の4進列挙型エンコーディング技法は、非常に効率的な変調エンコーディング及びデコーディング・システムを提供することが理解されるだろう。これらの技法を用いると、基礎となる一般化フィボナッチ・コードのすべてのコードワードを余すことなく利用することが可能となり、その結果、PRML(G,I)コードの可能な最大長さを容易に実現することができる。これにより、PRMLコードの可能な最高レートを達成することが可能となる。その結果得られるコード・レート利得は、図2のRC方式の場合と同様に無制約シンボルの部分的インターリーブの使用を支援する。更に、このような高レート・コーディング技法は、LDPC(low‐density parity‐check:低密度パリティ検査)コードに基づくECC技法との併用、又は検出器からエンコーダへのソフト情報のメッセージ・パッシングを必要とするターボ・コーディング方式との併用に適している。以下では図6乃至図8を参照して、本発明の諸実施形態に関する好ましいPRMLコードの具体例について説明する。
【0037】
以下では、レート(2N−P)/2N(即ち、M=2N−P)の3つのコードについて説明する。各例において、インターリーブされたフィボナッチ・コードの基礎となる2つのフィボナッチ・コードは同じものとする。1つ目のコードでは、P=1とする。スパンL=9、且つj=7の基礎となる一般化フィボナッチ・コードについて、ベースw=Bn−1(n=1,2、N=118)は、以下のように定義される。
=512 (但し、n=1,2,...,5)
=496 (但し、n=6,7,...,9)
=505−n (但し、n=10,11,...,118)
【0038】
これらのベースは、長さ236及びレート235/236のインターリーブされたフィボナッチ・コードを提供する。その結果得られるPRMLコードは、コードワード内、及び連結されたコードワードのコードワード境界をまたいで、I=7且つG=14の制約を満足する。このPRMLコードは、少なくとも16ビット分の位置だけ離間された任意の所望の位置における、8ビットのRSパリティ・バイトの部分的シンボル・インターリーブ(partial symbol interleaving)をサポートする。このような無制約バイトの挿入により、変調制約はI=11且つG=22に緩和される。N=118よりも少ないベース要素を使用することによって得られるPRMLコードは、より長いコードと同じ変調制約を満足し、また、同じ制約が課されるPRMLコードでは、短いコードほど容易に構築することができる(例えば、レート223/224のコード)。
【0039】
2つ目及び3つ目のコードでは、P=3とする。この形式、即ち(2N−3)/2Nのコード・レートを選択することにより、それぞれ長さ200及び400の非常に高いレートの2つのコードを設計することが可能となる。そのうちの1つは、レート197/200のPRML(G=10,I=5)コードである。このコードは、N=100且つj=5のとき、図6の表に示されるように基礎となる一般化フィボナッチ・コードのベース及びjプロファイルによって完全に定義される。もう1つは、レート397/400のPRML(G=12,I=6)コードである。このコードに関しては、N=100且つj=6のときの基礎となる一般化フィボナッチ・コードのベースが図7の表に示されている。基礎となるフィボナッチ・コードのj制約プロファイルは、コードワード内でj(n)=6、即ち、n=6,7,...,199となる。各境界では、それぞれ以下のj制約が適用される。
左側の境界:j(1)=1,j(2)=2,j(3)=3,j(4)=3,j(5)=4,j(6)=5
右側の境界:j(200)=3
それ故、j=6の制約は、コードワード内及びコードワード境界をまたいで適用される。したがって、結果として得られるPRMLコードは、コードワード内及びコードワード境界をまたいで、制約G=12且つI=6を満足する。
【0040】
上述の3つのコードは、図8の比較表で証明されるように、それぞれ以下の特徴的な特性を有する:PRML(G=14、I=7)コードは、最も高いレートとなるが、最も緩い制約が課される;PRML(G=10、I=5)コードは、最も厳しい制約が課されるが、最も低いレートとなる;PRML(G=12、I=6)コードは、中間の強度の制約が課され、PRML(G=14,I=7)コードとほぼ同様のレートを達成する点で、他の2つのコードの良好な妥協点となる。3つのコードはすべて、適切に離間された任意の挿入位置における、無制約パリティ・シンボルの部分的シンボル・インターリーブをサポートする。
【0041】
以上、本発明の好ましい諸実施形態について説明してきたが、これらの実施形態には本発明の範囲から逸脱しない限り様々な変更及び修正を施すことができる。

【特許請求の範囲】
【請求項1】
2進入力データ・ストリームの変調コーディング方法であって、
前記入力ビット・ストリームの奇数インターリーブ及び偶数インターリーブにおける一般化フィボナッチ・コードをそれぞれ同時にエンコードするように動作可能な4進列挙型エンコーディング・アルゴリズムを前記入力ビット・ストリームに適用して、一連の4進出力シンボルを生成するステップと、
連続する各4進出力シンボルのビットをインターリーブして出力ビット・ストリームを生成するステップと、
を含む方法。
【請求項2】
前記4進出力シンボルの前記ビットを反転させて(G,I)制約された出力ビット・ストリームを生成するステップを含む、請求項1に記載の方法。
【請求項3】
前記4進アルゴリズムは、前記奇数インターリーブ及び偶数インターリーブにおける同じフィボナッチ・コードを同時にエンコードするように動作可能である、請求項1に記載の方法。
【請求項4】
前記又は各フィボナッチ・コードのベースは、限られたスパンを有する、請求項1に記載の方法。
【請求項5】
一連の2Nビットのコードワードを含む出力ビット・ストリームは、前記入力ビット・ストリーム内の一連のMビットのワードから生成され、前記4進アルゴリズムは、Mビットのワード毎に、入力値を前記Mビットのワードの値に初期化するステップと、その後i=1〜Nの反復i毎に、
(a)可能な入力値の範囲を4つの部分範囲に区分化する区分化指標を計算するステップと、
(b)前記入力値と前記区分化指標とを比較して、前記入力値がどの前記部分範囲に含まれるかを判定するステップと、
(c)前記入力値が含まれる前記部分範囲に依存する値の4進出力シンボルを生成するステップと、
(d)前記入力値から前記入力値が含まれる前記部分範囲の下位境界値を減じることによって前記入力値を更新するステップと、
を含む、請求項1に記載の方法。
【請求項6】
前記区分化指標は、前記反復数iに応じて選択されるフィボナッチ・ベースにそれぞれ依存する部分的辞書式指標の第1の対及び第2の対から計算される、請求項5に記載の方法。
【請求項7】
M=2N−1である、請求項5に記載の方法。
【請求項8】
N=118であり、前記4進アルゴリズムは、前記奇数インターリーブ及び偶数インターリーブにおける、j=7の制約と、以下によって定義される限られたスパンL=9のベースと、を有する同じ一般化フィボナッチ・コードをエンコードするように動作可能である、請求項7に記載の方法。
=512 (但し、n=1,2,...,5)
=496 (但し、n=6,7,...,9)
=505−n (但し、n=10,11,...,118)
【請求項9】
M=2N−3である、請求項5に記載の方法。
【請求項10】
N=100であり、前記4進アルゴリズムは、前記奇数インターリーブ及び偶数インターリーブにおける、j=5の制約と、図6の表で定義される限られたスパンL=9のベースと、を有する同じ一般化フィボナッチ・コードをエンコードするように動作可能である、請求項9に記載の方法。
【請求項11】
N=200であり、前記4進アルゴリズムは、前記奇数インターリーブ及び偶数インターリーブにおける、j=6の制約と、図7の表で定義される限られたスパンL=9のベースと、を有する同じ一般化フィボナッチ・コードをエンコードするように動作可能である、請求項9に記載の方法。
【請求項12】
請求項1に記載の変調コーディング方法によって生成される出力ビット・ストリームのデコーディング方法であって、
前記出力ビット・ストリームのビットをデインターリーブして一連の4進シンボルを生成するステップと、
4進列挙型デコーディング・アルゴリズムを前記4進シンボルに適用して、前記4進エンコーディング・アルゴリズムによって前記奇数インターリーブ及び偶数インターリーブに適用された前記一般化フィボナッチ・コードを同時にデコードし、それによって前記2進入力データ・ストリームを復元するステップと、
を含む方法。
【請求項13】
2進入力データ・ストリームの変調コーディング装置であって、
前記入力ビット・ストリームの奇数インターリーブ及び偶数インターリーブにおける一般化フィボナッチ・コードをそれぞれ同時にエンコードするように動作可能な4進列挙型エンコーディング・アルゴリズムを前記入力ビット・ストリームに適用して、一連の4進出力シンボルを生成する4進エンコーダと、
連続する各4進出力シンボルのビットをインターリーブして出力ビット・ストリームを生成するマルチプレクサと、
を備える装置。
【請求項14】
前記4進出力シンボルの前記ビットを反転させて(G,I)制約された出力ビット・ストリームを生成するインバータを含む、請求項13に記載の装置。
【請求項15】
前記4進エンコーダは、前記奇数インターリーブ及び偶数インターリーブにおける同じフィボナッチ・コードを同時にエンコードするように適合される、請求項13に記載の装置。
【請求項16】
前記又は各フィボナッチ・コードのベースは、限られたスパンを有し、前記4進エンコーダは、幅2L+2のスライディング・ウィンドウ・エンコーダとして動作するように適合される、請求項13に記載の装置。
【請求項17】
前記4進エンコーダは、前記出力ビット・ストリームが一連の2Nビットのコードワードを含むように、前記入力ビット・ストリーム内の一連のMビットのワードをエンコードするように適合され、また、Mビットのワード毎に、入力値を前記Mビットのワードの値に初期化するステップと、その後i=1〜Nの反復i毎に、
(a)可能な入力値の範囲を4つの部分範囲に区分化する区分化指標を計算するステップと、
(b)前記入力値と前記区分化指標とを比較して、前記入力値がどの前記部分範囲に含まれるかを判定するステップと、
(c)前記入力値が含まれる前記部分範囲に依存する値の4進出力シンボルを生成するステップと、
(d)前記入力値から前記入力値が含まれる前記部分範囲の下位境界値を減じることによって前記入力値を更新するステップと、
を含む4進アルゴリズムを適用するように適合される、請求項13に記載の装置。
【請求項18】
前記4進エンコーダは、前記区分化指標を、前記反復数iに応じて選択されるフィボナッチ・ベースにそれぞれ依存する部分的辞書式指標の第1の対及び第2の対から計算するように適合される、請求項17に記載の装置。
【請求項19】
M=2N−1である、請求項17に記載の装置。
【請求項20】
N=118であり、前記4進エンコーダは、前記奇数インターリーブ及び偶数インターリーブにおける、j=7の制約と、以下によって定義される限られたスパンL=9のベースと、を有する同じ一般化フィボナッチ・コードをエンコードするように適合される、請求項19に記載の装置。
=512 (但し、n=1,2,...,5)
=496 (但し、n=6,7,...,9)
=505−n (但し、n=10,11,...,118)
【請求項21】
M=2N−3である、請求項17に記載の装置。
【請求項22】
N=100であり、前記4進エンコーダは、前記奇数インターリーブ及び偶数インターリーブにおける、j=5の制約と、図6の表で定義される限られたスパンL=9のベースと、を有する同じ一般化フィボナッチ・コードをエンコードするように適合される、請求項21に記載の装置。
【請求項23】
N=200であり、前記4進エンコーダは、前記奇数インターリーブ及び偶数インターリーブにおける、j=6の制約と、図7の表で定義される限られたスパンL=9のベースと、を有する同じ一般化フィボナッチ・コードをエンコードするように適合される、請求項21に記載の装置。
【請求項24】
請求項13に記載の変調コーディング装置によって生成される出力ビット・ストリームのデコーディング装置であって、
前記出力ビット・ストリームのビットをデインターリーブして一連の4進シンボルを生成するデマルチプレクサと、
4進列挙型デコーディング・アルゴリズムを前記4進シンボルに適用して、前記4進エンコーディング・アルゴリズムによって前記奇数インターリーブ及び偶数インターリーブに適用された前記一般化フィボナッチ・コードを同時にデコードし、それによって前記2進入力データ・ストリームを復元する4進デコーダと、
を備える装置。
【請求項25】
データ・ストレージ・システムであって、
一連のMビットのワードを含む2進入力データ・ストリームを変調コーディングして一連の2Nビットのコードワードを含む出力ビット・ストリームを生成する、請求項13に記載の変調コーディング装置と、
ストレージ・メディアと、前記一連のコードワードを前記ストレージ・メディア上に記録し、前記ストレージ・メディアを読み取って再生信号を生成する記録/再生機構と、を備える記録チャネルと、
前記再生信号内の一連の2Nビットのワードを検出する検出装置と、
検出された前記2Nビットのワードのビットをデインターリーブして一連の4進シンボルを生成するデマルチプレクサと、
4進列挙型デコーディング・アルゴリズムを各2Nビットのワードの前記4進シンボルに適用して、前記4進エンコーディング・アルゴリズムによって前記奇数インターリーブ及び偶数インターリーブに適用された前記一般化フィボナッチ・コードを同時にデコードし、それによって一連のMビットのデータ・ワードを生成する4進デコーダと、
を備えるデータ・ストレージ・システム。
【請求項26】
請求項25に記載のデータ・ストレージ・システムを備えるテープ・ドライブであって、前記ストレージ・メディアは、磁気テープを含む、テープ・ドライブ。
【請求項27】
データ・ストレージ・システムであって、
一連のMビットのワードを含む2進入力データ・ストリームを変調コーディングして一連の2Nビットのコードワードを含む出力ビット・ストリームを生成する、請求項14に記載の変調コーディング装置と、
前記変調コーディング装置からの前記出力ビット・ストリームを1/(1+D)コーディングしてプレコード済みビット・ストリームを生成するプレコーダと、
前記プレコード済みビット・ストリームをエラー訂正コーディングしてECCコード化ビット・ストリームを生成するECCコーダと、
ストレージ・メディアと、前記ECCコード化ビット・ストリームを前記ストレージ・メディア上に記録し、前記ストレージ・メディアを読み取って再生信号を生成する記録/再生機構と、を備える記録チャネルと、
前記再生信号内の一連の2Nビットのワードを検出する検出装置であって、検出された前記2Nビットのワード内のエラーを訂正するECCデコーダを含む検出装置と、
検出された前記2Nビットのワードのビットをデインターリーブして一連の4進シンボルを生成するデマルチプレクサと、
4進列挙型デコーディング・アルゴリズムを各2Nビットのワードの前記4進シンボルに適用して、前記4進エンコーディング・アルゴリズムによって前記奇数インターリーブ及び偶数インターリーブに適用された前記一般化フィボナッチ・コードを同時にデコードし、それによって一連のMビットのデータ・ワードを生成する4進デコーダと、
を備えるデータ・ストレージ・システム。
【請求項28】
請求項27に記載のデータ・ストレージ・システムを備えるテープ・ドライブであって、前記ストレージ・メディアは、磁気テープを含む、テープ・ドライブ。
【請求項29】
ストレージ・メディア上に記録されたデータを、請求項1に記載の変調コーディング方法を実施する記録システムによって再生するデータ再生システムであって、
前記ストレージ・メディアを読み取って再生信号を生成する読み取り機構と、
前記再生信号内の一連の2Nビットのワードを検出する検出装置と、
検出された前記2Nビットのワードのビットをデインターリーブして一連の4進シンボルを生成するデマルチプレクサと、
4進列挙型デコーディング・アルゴリズムを各2Nビットのワードの前記4進シンボルに適用して、前記変調コーディング方法の前記4進エンコーディング・アルゴリズムによって前記奇数インターリーブ及び偶数インターリーブに適用された前記一般化フィボナッチ・コードを同時にデコードし、それによって一連のMビットのデータ・ワードを生成する4進デコーダと、
を備えるデータ再生システム。

【図1】
image rotate

【図2】
image rotate

【図3】
image rotate

【図4】
image rotate

【図5】
image rotate

【図6】
image rotate

【図7】
image rotate

【図8】
image rotate


【公表番号】特表2011−503762(P2011−503762A)
【公表日】平成23年1月27日(2011.1.27)
【国際特許分類】
【出願番号】特願2010−531613(P2010−531613)
【出願日】平成20年10月23日(2008.10.23)
【国際出願番号】PCT/IB2008/054372
【国際公開番号】WO2009/060332
【国際公開日】平成21年5月14日(2009.5.14)
【出願人】(390009531)インターナショナル・ビジネス・マシーンズ・コーポレーション (4,084)
【氏名又は名称原語表記】INTERNATIONAL BUSINESS MASCHINES CORPORATION
【Fターム(参考)】