(57)【要約】  ビタビ復号器のようなパーシャルレスポンス最尤復号器が，一連の組み合わされた状態を演算する。各々の組み合わされた状態は，状態の複数の相補完するセットから少なくとも二つの状態を表すことが出来るよう組み合わされている。各データシンボル及び各組み合わされた状態に対して，ビタビプロセッサ703は，組み合わされた状態への各パスに対するパスメトリックと準状態の表示とを決定する。ビタビプロセッサ703のパス選択プロセッサ709は，最尤性のあるパスメトリックに対応するパスに対して，選択されたパス及び選択された準状態の表示を選定する。準状態の表示は，組み合わされた状態が，データシンボルに対して，相補完し合う状態のセットのどれを表わしているかを示す表示である。ビタビ・アルゴリズムが，より少ない数の組み合わされた状態に適用され得るので，本発明は，複雑さの顕著な減少を可能にし，計算のより少ない負担を可能にする。
2009512962.tif 000002
【特許請求の範囲】
【請求項１】
一連の組み合わされた状態を演算するパーシャルレスポンス最尤復号器であって，各々の前記組み合わされた状態は，複数の相補完し合う状態のセットの内から少なくとも二つの状態を表しており，前記復号器は，複数のデータシンボルに対して，各々の組み合わされた状態へ向かうパスメトリックと前記組み合わされた状態へ向かう各パスの準状態の表示とを決定し，最尤のパスメトリックに対応している選択されたパスと選択された準状態の表示とを選択するためのパス選択手段を有し，前記準状態の表示は，組み合わされた状態が，前記データシンボルに対して，相補完し合う状態のセットのどれを表しているかを示す表示である，パーシャルレスポンス最尤復号器。
【請求項２】
各々の組み合わされた状態に対する，及び複数のデータシンボルの少なくとも幾つかに対する前記選択された準状態の表示を記憶するための手段を更に有する，請求項１に記載の復号器。
【請求項３】
前記複数のデータシンボルに対して記憶された前記選択された準状態の表示に応じたデータシンボル値を決定するためのトレースバック手段を更に有する，請求項２に記載の復号器。
【請求項４】
第１のパスが始まる先行する組み合わされた状態の準状態の表示に応じて，第１のパスに対する第１のブランチメトリックを前記パス選択手段が決定する，請求項１に記載の復号器。
【請求項５】
第１のパスが始まる先行する組み合わされた状態の準状態の表示に応じて，第１の準状態の表示を前記パス選択手段が決定する，請求項１に記載の復号器。
【請求項６】
前記第１の準状態の表示は，先行する組み合わされた状態の前記準状態の表示によって一意的に決まる，請求項５に記載の復号器。
【請求項７】
前記データシンボルは2値のデータシンボルである，請求項１に記載の復号器。
【請求項８】
前記相補完し合う状態のセットが，第1のデータシンボル値の仮定に対応している，状態の第1のセットと，相補完するデータシンボル値に対応している，状態の第2のセットとを有する，請求項７に記載の復号器。
【請求項９】
一つ以上のデータシンボルの最小のラン長を持っている，ラン長が制限された符号を用いて前記データシンボルが符号化された，請求項１に記載の復号器。
【請求項１０】
1個のデータシンボルの最小のラン長を持っている，ラン長が制限された符号を用いて前記データシンボルが符号化された，請求項９に記載の復号器。
【請求項１１】
請求項１に従う復号器を有する，光ディスク読取り装置。
【請求項１２】
一連の組み合わされた状態を演算するパーシャルレスポンス最尤復号器の復号方法であって，各々の前記組み合わされた状態は，複数の相補完し合う状態のセットの内から少なくとも二つの状態を表しており，前記復号方法は，
−  複数のデータシンボルに対して，各々の組み合わされた状態へ向かうパスメトリックと前記組み合わされた状態へ向かう各パスの準状態の表示とを決定するステップ，及び
−  最尤のパスメトリックを持っている選択されたパスと選択された準状態の表示とを選択するステップを有し，前記準状態の表示は，組み合わされた状態が，データシンボルに対して，相補完し合う状態のセットのどれを表しているかを示す表示である，パーシャルレスポンス最尤復号器の復号方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は，パーシャルレスポンス最尤復号化に関し，特に，しかし排他的にではなく，オプィカルストレージディスクの読取りシステム用のビタビ復号化に関する。
【背景技術】
【０００２】
データ処理システム又はデータ配給システム中のビットエラーの検知と訂正とのための方法及び技術は，広く知られている。例えば，データが信頼性の無い通信リンクを通じて通信される通信システムは，通信エラーの量を減じるために，一般に順方向のエラー訂正符号及び復号を採用する。別の例として，光ディスクの読取りシステムは，読取りエラーの量を減らすためにエラーの復号化を採用する傾向がある。
【０００３】
ビットエラーが在る中で正しいビット値を検知するための，特に効率の良い技術は，パーシャルレスポンス最尤（PRML）ビット検知として知られている。特にビタビ・アルゴリズムは，通信システム用に，及び媒体と電子ノイズとが在る光ディスクのような格納媒体からのデータ抽出用に一般に使われている。
【０００４】
具体的には，ビタビに基づいたビット検知は，光ディスクに蓄積されたデータの信頼性のある抽出を達成するために，高級でモダンな光ディスクシステム中で頻繁に使われている。更に，ビタビ・ビット検知は，オプチカルストレージの次世代用で主要な役割を演じることが期待されている。特に，ビタビ検知の使用は，Blu-ray（登録商標）ディスク（BD）システムの，12cmディスクの記録層当たり25GBから35GBへの容量の増加を可能にする。
【発明の開示】
【発明が解決しようとする課題】
【０００５】
しかしながら，ビタビ・アルゴリズムは比較的複雑で，大量の処理パワーと計算のリソースとを必要とする。実に，付随するハードウエアのコストは，光ディスク格納システム中でのビタビ・アルゴリズムの拡張されてゆく許容を現在制限している，ファクタの一つである。かなりの数のビタビ検知器が並行して使われている高速光ディスク読取りシステムで，高速の並行ビタビ構成が採用されると，この問題は特に危機的になる。斯様なシステムでは，沢山のビタビ検知器がハードウエア中で（又はデジタル信号処理器（DSP）ベースで実行される場合はソフトウエア中で）同時に利用可能にされねばならない。
【０００６】
ビタビ・ビット検知器の実施に付随するハードウエア/ソフトウエアの負担を減らすために，複数の種々異なる解決策が提案されてきた。
【０００７】
例えば米国特許公報US6,580,766は，複雑さを減じたPRMLビット検知器を開示している。ここではビタビのトレリスを規定している有限の状態機械中の特定の状態が，ハードウエアのコストは減じるが全体の検知性能は基本的には変化することなく残るように，融合されている。
【０００８】
更に，国際特許公開公報WO 01/10044 Aは，複雑度の低い特定のビタビ復号器を開示している。これは，3個のデータシンボルの最小のラン長を持つ（即ち，データの遷移に続き，同一データ値が連続する回数の最小値が３である，（制約長d=2に対応））ランレングスリミッテッド（RRL）符号の在るチャネルコードを採用した比較的短いメモリ長を持ったチャネル（伝送路）用の復号器である。
【０００９】
しかしながら，これらの技術は幾つかの特定の部類のデータ符号化に対しては複雑さを減じるかも知れないが，当該技術は他の符号化システムへは一般には適用出来ない。具体的には，上で説明したアルゴリズムは，大変特定のビタビのトレリス構造のみに用いることが出来る。例えば国際特許公開公報WO 01/10044 Aで開示されたシステムは，最小ラン長3（即ちd=2のRLL符号）を必要とし，ラン長2（即ちd=1のRLL符号）を持つRLL符号には適用出来ない。
【００１０】
これゆえ，改善されたPRML復号システムは好都合であろうし，特に柔軟性を増したシステムや，複雑さを減じたシステムや，計算リソースの要求を減じたシステムや，適用性を増したシステム及び/又は改善された性能のシステムには好都合であろう。
【課題を解決するための手段】
【００１１】
従って本発明は，上で述べられた一つ以上の欠点を，単独で又は何らかの組み合わせにて好ましくは軽減し，緩和し，又は削除することを追及する。
【００１２】
本発明の第1の態様によれば，一連の組み合わされた状態を演算するPRML復号器であって，各々の組み合わされた状態は，複数の相補完し合う状態のセットの内の少なくとも二つの状態を表すよう配置され，復号器は，組み合わされた状態へ向かう各パスに対するパスメトリックと準状態の表示とを，各々の組み合わされた状態に対して決定するための複数のデータシンボルに対するパス選択手段を有し，更に最尤のパスメトリックに対応している選択されたパスと選択された準状態の表示とを選択するための，複数のデータシンボルに対するパス選択手段を有するPRML復号器が供される。ここで準状態の表示は，組み合わされた状態が，データシンボルに対して，相補完し合う状態のセットのどれを表しているかを示す表示である。
【００１３】
本発明は，PRML復号器の複雑さを減じ，及び/又は計算リソースの要件を減じる。本発明はハードウエアの要件を減じ，及び/又はPRML復号器のコストを減じる。所与のハードウエア及び/又はソフトウエアの制限で複雑さの増加の程度が決まるので，改善された復号化を達成することが出来る。
【００１４】
ある組み合わされた状態に対して選択された準状態の表示を決定し追跡することによって，状態を融合する技術が，1個又は2個のデータシンボルの最小ラン長を持つラン長が制限された（RLL）符号を含む符号化手法の，より広い分類にも適用されることが出来る。
【００１５】
PRML復号器は，ビタビ復号器でもよい。
【００１６】
パスメトリックは，先行する状態のパスメトリックに，先行する状態から組み合わせ状態へ向かうブランチのブランチメトリックをプラスしたものとして決定される。最尤のパスメトリックは，パスメトリックの中の，対応するパスの最尤性が正しいパスであることを示している組み合わされた状態に対して決定されたパスメトリックである。従って，増加してゆく値が，同パスが正しいとの，より高い確度を示すパスメトリックを用いるシステムでは，最尤性のあるパスメトリックは，最高値を持つパスメトリックである。同様に，減少してゆく値が，同パスが正しいとの，より高い確度を示すパスメトリックを用いるシステムでは，最尤性のあるパスメトリックは，最低値を持つパスメトリックである。
【００１７】
組み合わされた状態の演算に加えて，復号器は複数の準状態を表してはいない単一の状態も演算してもよい。特に，状態トレリス又は状態機械は，組み合わされた状態と非‐組み合わされた状態との両方を含んで演算されることが出来る。
【００１８】
本発明の更なる特徴によれば，復号器は，各々の組み合わされた状態と，複数のデータシンボルの少なくとも幾つかとに対する選択された準状態の表示を記憶する手段を他に有する。
【００１９】
これは復号を容易にし，効率の良い演算を供する。
【００２０】
本発明の更なる特徴によれば，復号器は，複数のデータシンボルに対して記憶された，選択された準状態の表示に応じてデータシンボルを決定するためのトレースバック手段を更に有する。
【００２１】
これは復号を容易にし，効率の良い演算を供する。特にこの特徴は，組み合わされた状態を用いるPRML復号器の効率の良いパス復号を可能にする。
【００２２】
本発明の更なる特徴によれば，パス選択手段は，第1のパスが始まる先行する組み合わされた状態の準状態の表示に対応して，第1のパスに対する第1のブランチメトリックを決定する。
【００２３】
これは改善されたPRML復号器を供する。第1のブランチメトリックは，ブランチに対して予想される基準信号に対応して決定され，当該予想される基準信号は先行する組み合わされた状態の準状態に依存する。
【００２４】
本発明の任意の特徴によれば，パス選択手段は，最初のパスが始まる先行する組み合わされた状態の準状態の表示に応じて第1のパスの第1の準状態の表示を決定する。
【００２５】
これは改善されたPRML復号器を供し，特に準状態の表示を決定するための効率の良い信頼性のある手段を可能にし，よって，組み合わされた状態が，現在のデータシンボルに対して，相補完し合う状態のセットのどれを表していると考えられるかを可能にする。
【００２６】
本発明の更なる特徴によれば，第1の準状態の表示は，先行する組み合わされた状態の準状態の表示によって一意的に決定される。
【００２７】
パス選択手段は，先行する組み合わされた状態の準状態の表示から準状態の表示を，一意的に選択する。先行する組み合わされた状態は，具体的に，現在の組み合わされた状態に対する選択された最尤の先行する状態であることが出来る。一つの組み合わされた状態の準状態の表示は，演算された状態機械又は状態トレリスの所与の構造に対する先行する組み合わされた状態の準状態の表示によって一意的に規定されることが出来る。従って，組み合わされた状態によって表わされる準状態と，選択されたパスに対して先行する組み合わされた状態によって表された準状態との間には，1対1の対応がある。
【００２８】
幾つかの実施例において，第1の準状態の表示は，先行する非−組み合わされた状態の準状態の表示によって一意的に決定される。
【００２９】
これは改善されたPRML復号器を供し，特に準状態の表示を決定するための効率の良い信頼性のある手段を可能にし，したがって，相補完し合う状態のセットのどの組み合わされた状態が，現在のデータシンボルを表していると考えられるかを可能にする。
【００３０】
本発明の更なる特徴によれば，データシンボルは2値のデータシンボルである。
【００３１】
本発明は，2値データに対する改善されたPRML復号器を可能にする。
【００３２】
本発明の更なる特徴によれば，相補完し合う状態のセットは，第1のデータシンボル値の仮定に対応する状態の第1のセットと，相補完し合うデータシンボル値に対応する状態の第2のセットとを有する。
【００３３】
本発明は2値データに対する改善されたPRML復号器を可能にする。一つの組み合わされた状態で反対符号の仮定に対応する相補完する状態を表すことによって，複雑さ及び/又は計算リソースの要件が減じられる。特に好都合な特性が，相補完し合うたった二つの状態のセットを持つ2値のデータによって得られ，特に二つの状態のセットのどちらが組み合わされた状態によって表されているかの，信頼性のある検知が達成されることが出来る。
【００３４】
本発明の更なる特徴によれば，一つ以上のデータシンボルの最も小さなラン長を持つラン長制限符号を用いて，データシンボルは符号化される。
【００３５】
本発明は，ラン長を制限して符号化したデータに対する改善されたPRML復号器を可能にし，増加した符号の部類に対する複雑さの減少及び/又は計算リソースの減少を可能にする。
【００３６】
本発明の更なる特徴によれば，データシンボルは1個のデータシンボル中の最小のラン長を持つ，ラン長制限符号を用いて符号化される。
【００３７】
本発明は，ラン長が制限された符号化データに対する改善されたPRML復号器を可能にし，たった1個のデータシンボルの最小のラン長を持つラン長が制限された符号に対する複雑さの減少及び/又は計算リソースの減少を可能にする。
【００３８】
本発明の別の態様によれば，上で説明された復号器を有する光ディスク読取り装置が供される。
【００３９】
本発明の別の態様によれば，各々の組み合わされた状態が，複数の相補完し合う状態のセットの内の少なくとも二つの状態を表す，組み合わされた状態のセットを演算するPRML復号器の復号方法が供され，当該方法は，
−  複数のデータシンボルに対して，各々の組み合わされた状態へ向かうパスメトリックを決定し，及び当該組み合わされた状態へ向かう各パスに対する準状態の表示を決定することと，
−  選択されたパスを選択し，及び最尤のパスメトリックを持っている選択された準状態の表示を選択することとを含む。ここで準状態の表示とは，組み合わされた状態が，データシンボルに対して，相補完し合う状態のセットのどれを表しているかの表示である。
【００４０】
本発明のこれらの態様及び他の態様，特徴及び長所は，これ以降説明される（複数の）実施例を参照して明らかにされ，説明されることであろう。
【００４１】
本発明の実施例が，添付の図面を参照して，単に例示的態様にて説明されよう。
【発明を実施するための最良の形態】
【００４２】
以下の説明は，ラン長が制限された（RLL）符号を用いる光ディスクの読取りシステムに適用可能な本発明の実施例に焦点を当てる。しかしながら本発明は，このアプリケーションに限定されることなく，例えば通信システムの復号器を含む多くの他の復号システムにも適用されることができることが理解されよう。
【００４３】
図１は，本発明の幾つかの実施例を有する光ディスク読取り機の例を例示している。
【００４４】
この例において光ディスクデータ読取り機101は，光ディスク103からのデータを読み取る。光ディスク103に蓄積されているデータは，RLLで符号化されている。光ディスクから読み取られたデータサンプルは，光ディスクデータ読取り機101からビタビ・ビット検知器105へ送信される。ビタビ・ビット検知器105は，光ディスク103から読取られたデータの値を決定するためにビタビ・アルゴリズムを用いる。検知されたデータは，外部機器へと橋渡しするデータインタフェイス107へと送信される。例えばこのデータインタフェイス107は，パソコンへの橋渡しを供する。
【００４５】
当業者には良く知られているように，ビタビ復号器のようなPRML復号器は，状態機械を用いて通常はデータを復号する。新しいデータサンプルの各々に対して，起こり得る状態遷移及びこれらの遷移に付随するペナルティ値が調べられ，これらは，起こり得る状態の各々へのサバイバルパスを選定するために使われる。
【００４６】
具体的な例として，図2は，ビタビ復号器の四つの状態トレリス線図を例示している。この例では各状態は，二つの起こり得る先行の状態を持っており，従って，各状態に入って来る（2値データ及び二つのデータ値のメモリに対応した）二つのパスを持っている。各々の状態に対し，当該状態に入って来る両方のパスに対してパスメトリックが調べられる。最尤のパスメトリックを持っているパス（即ち正しいパスである最も高い確度を示している）パスが選択され，他のパスは放棄される。斯様にして，各々の状態に対して唯一つのサバイバルパス（最尤で正しいとされるパス）のみが選定される。
【００４７】
パスメトリックは，先行する状態のパスメトリックに先行の状態から現在の状態への状態遷移に対するブランチメトリックをプラスして決定される。このブランチメトリックは，受信したサンプルと遷移で予想されるサンプルとの間の距離の測度として，一般に計算される。従って，斯様な実施例においてパスメトリックは，パスに対するペナルティ値として捉えられ，各状態のサバイバルパスは，最も低いパスメトリックを持つパスである。
【００４８】
従って，所与のデータサンプルに対して，ビタビ復号器はどの起こり得る状態が正しい状態かを正確に知ることは出来ない。しかしながら，各状態に対する最尤のパスは既知であり，従って最尤の受信ビット列は既知である。幾つかの事例において，入力されてくるデータは，特定の状態に終わるように知られているデータ列が含まれるよう符号化される。この事例においては正しい状態が判っており，最尤のビット列は，選択されたパスに沿ったトレリスのバックトラッキング（後方追跡）によって特定することが出来る。更に，異なる状態のパスは，十分に長い遅れの後で同じパスに融合される傾向があり，従って正しい状態についての明白な知識に頼ることなしに，復号化されたビットが連続して生成されることが出来るのが，ビタビ復号化の特徴である。
【００４９】
国際特許公開公報WO 01/10044 Aは，3ビットのメモリを持ち，d=2の（即ち，最小のラン長は3ビットである）RLL符号を用いるシステムのビタビ・ビット検知に関している。これに対応するビタビ状態及び遷移が，図3に例示されている。図3では，トレリス状態は状態機械として（即ち，時間領域を反映せずに）示されている。
【００５０】
この例では，d=2のRLL符号に起因して状態のうち二つは起こり得ないので，六つの状態のみが必要とされる。具体的には，（データ列101及び010（又は逆の配列も）に相当する）状態＋−＋及び状態−＋−は起こり得ない。更に見てとれるように，RLL符号が起こり得る状態遷移を著しく限定している。
【００５１】
斯様なビタビ復号器においては，パスメトリックは，順方向のパス中で次のルールに従って更新される；
2009512962.tif 000003
ここで，ブランチメトリック
2009512962.tif 000004
は，実際の波形値と予想値との間の差の絶対値として，次式のように決定されることが出来る；
2009512962.tif 000005
例えば差の絶対値の特定のパワーのような，他の距離の測度も同様に使うことができる。
【００５２】
この式において
2009512962.tif 000006
は，時間kにおけるトレリス状態mに対するパスメトリックを表し，
2009512962.tif 000007
は，時間k‐1で状態miから，時間kで状態mへの遷移に対応するブランチメトリックを表し，miは状態mに対して先行する状態を表し，
2009512962.tif 000008
は，状態mi経由で状態mへ到着する候補のパスのパスメトリックを表す。
【００５３】
ブランチメトリックは，実際に受信した信号サンプルzkと，状態miから状態mへの遷移に対して予想される信号サンプルに対応する，所謂基準レベルrmi->mとの間の差の距離の測度として計算される（基準レベルは，目前の実際の伝送路に適合すると仮定される）。
【００５４】
上記の手順において，miからm（基準レベル）への遷移に対して予想される信号サンプルは，元の状態miと，目標の状態mとによって一意的に規定されると明確に仮定されている。
【００５５】
国際特許公開公報WO 01/10044 Aのシステムでは，計算への要求を減じることが，幾つかのビタビ状態を組み合わせた状態へ融合することによって達成されている。具体的には，図3の状態線図を図4の状態線図へと畳むことが示唆されている。見てとれるように，状態は，符号が反転した状態に対応する相補完する状態の二つの異なるセットに分割され，一つの組合された状態が，第1のセットからの状態及び第2のセットからの状態の両方を表すために用いられる。
【００５６】
具体的な例では，状態Saは，ビット列＋＋＋及びビット列‐‐‐ の両方に対応する状態S1及び状態S4の両方を表すことが出来る。同様に，組合された状態Sbは，状態S2及び状態S5の両方を表すことが出来，組み合された状態Scは，状態S3及び状態S6の両方を表すことが出来る。RLL符号の遷移は検知するのが困難であり，これゆえ拡張ビタビ検知のアプローチを要するものの，長いラン長は現在のビット列の符号を比較的容易に決定することを可能にするので，斯様な状態の組合せは，一般に実現可能である。例えば，2値データの長いラン（例えば50−100個の連続したデータシンボル）に対して，復号器が状態S1に居るのか又は状態S4に居るのかを信頼性良く決定し，組み合わされた状態が状態S1に対応するセットを表しているのか，又は状態S4に対応するセットを表しているのかを信頼性良く決定することは容易である。
【００５７】
所与のデータ値に対して，全ての状態のうちの半分だけが効率よく調べられることが必要なので，状態の組合せは計算リソースのかなりの減少をもたらす。斯様にこの例では，殆ど2倍の改善を達成することが出来る。
【００５８】
しかしながら，国際特許公開公報WO 01/10044 Aのシステムは，効率の良いアルゴリズムを可能にしているものの，当該システムは少ないチャネルメモリ及び最小のラン長が3のシステムを具体的に目指している。このシステムは，異なる組み合わされた状態間の限定された動きの自由度を反映するために，パスメトリックを修正するよう開発されている。具体的にはこのシステムは，一つのラン長の状態（S1又はS4）からのパスが，中間に介在する状態の特定のビット列を常に通っていることを反映している，修正されたパスメトリックを用いている。例えば，図3や図4の例では，状態S1から状態S4（又は状態S4から状態S1）へのビット列を反映しているパスメトリックスは，常に組み合わされた状態のビット列Sa‐Sb‐Sc−Saになる。従って，ビタビ状態の二つの異なるセットの一つを表している組み合わされた状態の可能性を反映するよう，パスメトリックは修正される。
【００５９】
残念ながら，国際特許公開公報WO 01/10044 Aのシステムは，より小さい最小のラン長を用いているシステムへ適用されることが出来ない。例えば，3個のチャネルメモリ及び最小ラン長が2のデータシンボル（d=1）のシステムでは，パスメトリックをただ単に修正することは不可能であり，又はフルラン長の状態の（S1及びS4）間には，唯一つの起こり得るビット列しかないと仮定をすることは不可能である。
【００６０】
具体的には，メモリ長が3で，最小のラン長が2のデータシンボル（d=1）を持つシステムに対して，ビタビの状態機械は図5の状態線図によって表されることが出来る。国際特許公開公報WO 01/10044 Aのシステムに対するものと同じ原則を用いると，この状態線図は，図6の組み合わされた状態線図へと畳まれることが可能である。図6に例示されているように，この状態線図は両方向への遷移を有し，Saに対応しているラン長の状態S1とS4とをただ単に考えるだけでは十分ではない。
【００６１】
図7は，本発明の幾つかの実施例に従った復号器を例示している。
【００６２】
図7の復号器は，国際特許公開公報WO 01/10044 Aのシステムの欠点の幾つかを克服するためのものである。特に図7の復号器は，組み合された状態が最小のラン長が1又は2のデータシンボルを用いるシステム（d=1又はd=2に相当）を含んだ広範囲の符号化システムのビタビ復号で用いられることを可能にする。
【００６３】
特に復号器は，各データシンボルに対して各々の組合された状態の準状態を次々に決定してゆく。よって，新しいデータシンボルが調べられるとき，組み合わされた状態へと入って来る各パスに対するパスメトリックが決まる。（パスメトリックがペナルティ値として計算されている事例では）最小値のパスメトリックを持っているパスが選定され，このパスに対応する組み合わされた状態の準状態が決定される。この準状態の表示は，次に，当該パスメトリックと共々この状態用に記憶される。このように図7の復号器は，経過を連続して追跡していて，各々の組合された状態に対して，追跡の準状態は，組み合わされた状態によって表されている。トレースバックの際，記憶された準状態の表示は，正しいデータ値を決めるために更に使われる。
【００６４】
幾つかの状況では，所与の組み合わされた状態に対する準状態のいずれも，先行する状態の準状態の表示と対応していないことが生じ得，このような場合，無限のパスメトリックが，この遷移に連想される。例えば，先行の状態の幾つかは，符号に対する両方の選択肢を持っている組み合わされた状態であるのに，ビタビ状態の幾つかの状態は，当初は非−融合の状態（即ち，組み合わされてはいない状態）であり得，これゆえ，それ自身の符号を持ち続けている。
【００６５】
（単にフルラン長を持っている状態よりもむしろ）各々の組み合わされた状態によって表された適切な準状態の経過を連続して追い続けることによって，状態の融合のコンセプトを，いかなる有限な状態機械にも適用することが出来る。特に， 3個のデータシンボルのメモリ長を持つシステム中で，最小のラン長2（d=1）を持つRLL符号のビタビ検知のために，組み合わされた状態の線図が使われることが出来る。
【００６６】
図7の検知器によって使われているアルゴリズムは，例えば2値のオプチカルストレージの伝送路と見做される部類に対して，ビタビ検知器は鏡に映った（相補完する）相方からのいかなるトレリス状態も容易に認知出来るという観察に基づいている。従って，ある状態へのパスが正しいパスである高い確度を持っているとビタビ検知器が考えた場合，考慮された状態の鏡に映った（符号が反転した）相方へのパスは，低い確度を持っている。この観察は相補完する状態が，考慮せねばならない状態の数を半分にして，効果的に組み合わされることを可能にする。準状態（トレリス状態）のどれが，組み合わされた状態によって表されているのかを示す準状態の表示の選定は，ランタイムの間に動的に決定され，ビタビの順方向パス中でのパスメトリックの追跡のみならず，先行の状態の準状態の表示の追跡にも基づいて行われ，特に，選択されたパスに対する先行状態の準状態の表示に基づいて行われる。
【００６７】
更に，適切な準状態の検知は，高い信頼性がある。具体的には，間違った仮定に対するパスメトリックは非常に迅速に増大するので，同一のデータ値を持つ，いかなる拡張されたランも，復号器が正しい準状態の仮定をするよう強くバイアスをかける。従って，複雑さの減少に付随するエラーレート性能の悪化は，殆どのアプリケーションにおいて無視できる。
【００６８】
図7の例では，状態機械又はトレリスは，複数の準状態を表している組み合わされた状態のみを用いて演算される。しかし他の実施例では，復号器は一つ以上の組み合わされた状態を，一つ以上の非−組み合わされた状態と一緒に有することが理解されよう。即ち，幾つかの元の状態のみが一つの状態へと組み合わされ，他の元の状態はそれぞれ一つの状態として維持されている状態機械又はトレリスを用いることが出来る。
【００６９】
復号器は，光ディスクデータ読取り機101からデータサンプルを受信するビット受信機701を有する。このビット受信機701は，ビタビプロセッサ703へ結合されている。ビタビプロセッサ703は，ビタビトレリスに対して決定された情報が記憶されるデータストレージ705へ結合されている。具体的には，このビタビプロセッサ703は，累積されたパスメトリックと，各々の組み合わされた状態に対する準状態の表示及び各々のデータシンボルに対する準状態の表示とを前記データストレージ705中に記憶する。データストレージ705は更に，選択されたパスのデータビットを生成するために，組み合わされた準状態を通じてトレリスを選択されたパスに沿ってトレースバックするためのトレースバックプロセッサ707へ結合されている。このトレースバックプロセッサ707は，次に，復号化されたデータをデータインターフェィス107へと送信する。
【００７０】
ビタビプロセッサは，各々の組み合わされた状態に対する，及び各データシンボルに対するサバイバルパスを選定するパス選択プロセッサ709を有する。このパス選択プロセッサ709は，所与の状態に入ってくるパスに対するパスメトリックを決定するパスメトリックプロセッサ711へ結合されている。これに加えて，このパス選択プロセッサ709は，所与の状態に対する適切な準状態の表示を決定する準状態プロセッサ713へ結合されている。よって，準状態プロセッサ713は，特定のデータサンプルに対して，相補完し合う状態のセットのどれを，現在の組み合わされた状態が表しているかを決定する。
【００７１】
特に新しいデータサンプルが前記受信機701から受信されたとき，ビタビプロセッサ703は，全ての組み合わされた状態を調べるステップへと進む。各々の組み合わされた状態に対して，この組み合わされた状態に入って来る全てのパスが調べられる。各パスに対して，パス選択プロセッサ709は，データストレージ705から先行する状態のパスメトリックを抽出し，これをパスメトリックプロセッサ711へと送る。パスメトリックプロセッサ711は，次に，先行する組み合わされた状態から現在の組み合わされた状態への遷移のためのブランチメトリックを計算する。遷移での予想されるデータ値に対応する基準レベルが，先行する準状態の表示に依存するので，このブランチメトリックは，先行する準状態の表示にも一般に依存し，現在のパスに対するパスメトリックを生成するために，計算されたブランチメトリックの値を，抽出したパスメトリックに加える。パス選択プロセッサ709が組み合わされた状態に入って来る全てのパスに対するパスメトリックを得たとき，同プロセッサは最も低いパスメトリックを持っているパスを選定するステップへと進む。何故なら，当該のパスがこの組み合わされた状態に入って来る正しいパスである最尤性を持つパスだからである。
【００７２】
パス選択プロセッサ709が，組み合わされた状態に対するサバイバルパスを選定したとき，同プロセッサは，このパスに対する先行する組み合わされた状態の準状態の表示をデータストレージ705から抽出するステップへと進む。この準状態の表示は，現在の組み合わされた状態に対する準状態の表示を決定する準状態プロセッサ713へと送られる。
【００７３】
沢山の事例において，現在の組み合わされた状態に対する準状態の表示は，先行する状態の準状態の表示と，特定の遷移とによって一意的に規定される。従って，どのようにして，ある組み合わされた状態の準状態の表示が，先行する状態の準状態の表示から続くのかを規定する一連の規則が事前に決められることが可能である。
【００７４】
例えば図6の状態線図で，もしも先行する状態が，第1のセット（例えば，状態S1，＋＋＋）に対応する準状態の表示を持つ状態Saであり，遷移が状態Sbへの遷移であれば，この組み合わされた状態に対する準状態の表示も，第1のセット（状態S2，+ + ‐）に対応する準状態の表示であろう。別の例として，もしも先行する状態が，第1のセット（例えば，状態S3，＋‐‐）に対する準状態の表示を持つ状態Scであり，遷移が状態Sbへの遷移であれば，状態Sbに対する組み合わされた準状態の表示は，第2のセット（状態S5,‐‐＋）に対する準状態の表示であろう。同じ原則が全ての状態遷移に対して適用されることが出来，もたらされた規則は，現在の組み合わされた状態に対する準状態の表示を容易に一意的に決めることを可能にする準状態プロセッサ713中で実行されることが出来る。
【００７５】
従って，有限の状態機械の特定の部類に対しては，もしも準状態の表示が正しく合わない場合miからmへの遷移は不可能であるので，先行する組み合わされた状態miの準状態は，目標の組み合わされた状態mの符号を一意的に決定する。逆もまた真である。目標の組み合わされた状態mの符号は，先行する組み合わされた状態miの符号を一意的に決定する。言い換えれば，有限の状態機械線図は，状態miの準状態の表示から状態mの準状態の表示へのマッピングと，状態mの準状態の表示から状態miの準状態の表示へと戻るマッピングとを一意的に規定している。
【００７６】
パス選択プロセッサ709は，次に，現在の組み合わされた状態に対する決定された準状態の表示及びパスメトリックを，データストレージ705中に記憶するステップへと進む。当該プロセッサは，順番に，現在のデータシンボルに対する次の組み合わされた状態を調べるステップへと進む。これは，全ての組み合わされた状態が調べられるまで行われる。その後，同じ態様にて，次のデータシンボルを処理するステップへと進む。
【００７７】
パスメトリックプロセッサ711によるブランチメトリックの決定は，従来のビタビ復号器と同様，予想値に対する距離の測定に基づくことが可能である。しかしながら，図7の復号器中では，所与のパスに対するブランチメトリックは，このパスに対する先行する組み合わされた状態の準状態の表示に応じて決められる。具体的には，パス選択プロセッサ709は，先行するパスに対する準状態の表示をデータストレージ705から抽出し，これをパスメトリックプロセッサ711へと送る。パスメトリックプロセッサ711は，次にこれを，基準レベルと呼ばれる予想値を決定するために用いる。具体的には，組み合わされた状態に対するパスメトリックは，次式のように決められる；
2009512962.tif 000009
ここで，ブランチメトリック
2009512962.tif 000010
は次式で計算される；
2009512962.tif 000011
ここで
2009512962.tif 000012
は，距離の測度を規定し，s(mi)は，元の超状態miの準状態の表示を意味し，
2009512962.tif 000013
は，遷移に対する予想されるデータサンプル値であり，zkはデータサンプルである。もしも先行する状態の表示が，現在の状態の準状態と不適合である場合，ブランチメトリックは，パスの遷移が放棄されるであろうことを保証する，無限値に設定されることが出来る。一般に，演算の複雑さを考慮して，差の絶対値が距離の測度を規定するために用いることが出来る。miからmへの遷移に対して予想される信号のサンプル値
2009512962.tif 000014
（基準レベル）は，先行する組み合わされた状態miと，目標の組み合わされた状態mと，元の超状態miの準状態の表示s(mi)とによって，一意的に規定される。
【００７８】
トレースバックプロセッサ707は，記憶された各々の組み合わされた状態に対する準状態の表示を用いて，サバイバルパスを通るトレースバックを実行する。具体的には，組み合わされた状態の準状態の表示は，上で説明されたビタビのトレリスの組み立て中に順方向パス中で使用されねばならないのみならず，トレリスを通るパスからビット決定のストリームへの唯一のマッピングであることを保証するために，トレースバック工程中でも使用されねばならない。即ち，組み合わされた状態の適切な準状態の表示に対応したビットの決定が成されねばならない。トレースバックパスに沿った先行する状態の準状態の表示の追跡は，順方向パスに対して用いられたアプローチと同様にして容易に行うことが出来る。時間kでの，既知の組み合わされた状態の準状態の表示から開始して，先行する組み合わされた状態miの準状態の表示が，状態mの準状態の表示から状態miの準状態の表示までの同定されたマッピングにより，有限の状態機械線図によるセットとして与えられる。
【００７９】
これまでの説明は2値のデータシンボルに焦点を当ててきたが，本原則は2値以外のデータシンボルにも等しく適用することが出来ることが理解されよう。
【００８０】
更に，これまでの説明は二つのビタビ状態を一つの組み合わされた状態に組合わせることに焦点を当ててきたが，他の実施例で用いられている他のグループ分けも使用することが出来る。具体的には他の実施例では，他の大きさのグループを用いることが出来る。
【００８１】
図8から図11は，他の状態機械に適用された，状態の組合せの他の例を例示している。特に図8は，図9に示されている，より少ない状態機械へと融合された，d=1を持つ4-タップの状態機械を例示している。図10は，図11に示されている，より少ない状態機械へと融合された，d=1を持つ5-タップの状態機械を例示している。
【００８２】
明確にするための上記の記述が，種々異なる機能ユニット及びプロセッサを参照して，本発明の実施例を説明してきたことが理解されよう。しかしながら，本発明を損ねることなく，種々異なる機能ユニット又はプロセッサ間で，いかなる適切な機能の分散を行うことも可能である。例えば，別々のプロセッサ又は別々のコントローラによって実行されるべく例示されている機能は，同一のプロセッサ又は同一のコントローラによって行うことが可能である。これゆえ，特定の機能ユニットに対する基準は，厳密に論理的若しくは物理的な構造又は構成の表示というよりはむしろ，説明された機能を提供するための適切な手段に対する基準としてのみ捉えられる。
【００８３】
本発明は，ハードウエア，ソフトウエア，ファームウエア又はこれらの何らかの組合せを含んだいかなる適切な様式によっても実行されることが出来る。本発明は，一つ以上のデータプロセッサ及び/又はデジタル信号プロセッサ上で走るコンピュータソフトウエアとして，少なくとも部分的に実行されることも任意で可能である。本発明の実施例の素子及び要素は，何らかの適切な態様で物理的，機械的及び論理的に実行されることが可能である。実に，機能は，単独のユニット，複数のユニット又は他の機能ユニットの一部として実行されることが可能である。斯様に本発明は単一のユニットで実行されることが出来，又は種々異なるユニット及びプロセッサ間に物理的及び機能的に分散されることが出来る。
【００８４】
本発明は，幾つかの実施例に関連して説明されてきたが，これは，ここで説明された特定の様式に限定されることを意図したものではない。それよりむしろ，本発明の範囲は，添付の請求項によってのみ限定される。これに加えて，特徴が，特定の実施例に関連して説明されるべく登場しているが，説明された実施例の様々な特徴が本発明に従って組み合わされることが出来ることを当業者は認識していよう。請求項において，有するという単語は，他の要素又はステップの存在を排除するものではない。
【００８５】
更に，個々にリストアップされているものの，複数の手段，複数の要素又は複数の方法のステップは，例えば単一のユニット又は単一のプロセッサによって実行されることが可能である。これに加えて，個々の特徴が異なる請求項中に含まれているが，これらは恐らく好都合に組み合わせることが出来，異なる請求項中への包含は，これらの特徴の組合せが実現可能ではない及び/又は好都合ではないとは暗示していない。また，請求項の一つのカテゴリ中への特徴の包含は，このカテゴリを限定すると暗示しているわけではなく，むしろ，当該特徴は他の請求項のカテゴリへも適切なものとして，等しく適用可能であることを示している。更に，請求項中の特徴の順序は，特徴が機能しなければならない如何なる特定の順序をも暗示しているわけではなく，特に，方法についての請求項中の個々のステップの順序は，当該ステップがこの順序で実行されねばならないことを暗示しているわけではない。それよりむしろ，上記のステップは，いかなる適切な順序で実行されることも可能である。これに加えて，単数の引例は複数を除くものではない。従って，「a」，「an」，「第1の」，「第2の」等々の引例は，複数を排除するものではない。いかなる態様においても，明確にされた例が請求項の範囲を限定するものとして解釈されるべきではないので，請求項中の引例の符号は単に供されているのみである。
【図面の簡単な説明】
【００８６】
【図１】本発明の幾つかの実施例を有する，光ディスク読取り機の例を例示する。
【図２】ビタビ復号器の，状態トレリスの例を例示する。
【図３】ビタビ復号器の，状態機械の例を例示する。
【図４】ビタビ復号器の，状態機械の例を例示する。
【図５】ビタビ復号器の，状態機械の例を例示する。
【図６】ビタビ復号器の，状態機械の例を例示する。
【図７】本発明の幾つかの実施例による復号器の例を例示する。
【図８】ビタビ復号器の，状態機械の例を例示する。
【図９】ビタビ復号器の，状態機械の例を例示する。
【図１０】ビタビ復号器の，状態機械の例を例示する。
【図１１】ビタビ復号器の，状態機械の例を例示する。
【図１】
2009512962.tif 000015
【図２】
2009512962.tif 000016
【図３】
2009512962.tif 000017
【図４】
2009512962.tif 000018
【図５】
2009512962.tif 000019
【図６】
2009512962.tif 000020
【図７】
2009512962.tif 000021
【図８】
2009512962.tif 000022
【図９】
2009512962.tif 000023
【図１０】
2009512962.tif 000024
【図１１】
2009512962.tif 000025
【国際調査報告】
2009512962.tif 000026
2009512962.tif 000027