(57)【要約】【課題】復号処理の高速化を実現する。【解決手段】時刻t-1において、比較器１３３は、所定の状態でマージされる３以上のブランチのうち、そのブランチのブランチメトリックが同一であるブランチに対応するパスのパスメトリックに対して比較を行い、セレクタ１３４は、最大値の選択の演算を行う。時刻tにおいて、加算器１３６−２は、セレクタ１３４により選択されるパスメトリックと、ブランチメトリックに対して、加算の演算を行う。加算器１３６−１は、ブランチメトリックとパスメトリックに対して加算の演算を行う。比較器１３７は、加算器１３６−１と１３６−２による加算の演算の結果得られる加算値に対して比較の演算を行い、セレクタ１３８は、その２つの加算値のうちの最大値の選択の演算を行う。本発明は、例えば、磁気記録再生装置に適用することができる。【選択図】図１８
2008034008.tif 000002
【特許請求の範囲】
【請求項１】
符号制約をパーシャルレスポンスの状態遷移と組み合わせた場合のトレリスであって、前記パーシャルレスポンスのチャネルメモリ長よりも前記符号制約の記述に必要なメモリ長が長い場合のトレリスにしたがって、パーシャルレスポンスチャネル出力からチャネル入力ビットを復号する復号装置において、
所定の状態でマージされる３以上の数のブランチのうち、その数より少ない数のブランチを第１のブランチとし、その第１のブランチに関する情報である第１のブランチ情報と、その第１のブランチに対応する第１のパスに関する情報である第１のパス情報に対して、第１の演算を行う第１の演算手段と、
前記第１の演算の結果得られる第１の演算値に対して第２の演算を行う第２の演算手段と
を備える復号装置。
【請求項２】
前記所定の状態でマージされる３以上の数のブランチのうち、ブランチ情報が同一である第２のブランチに対応する第２のパスに関する情報である第２のパス情報に対して、第２の演算を行う第３の演算手段
をさらに備え、
前記第１のブランチ情報は、前記第２のブランチのブランチ情報である第２のブランチ情報と、前記所定の状態でマージされる３以上の数のブランチのうちの、前記第２のブランチ以外のブランチである第３のブランチのブランチ情報である第３のブランチ情報であり、
前記第１のパス情報は、前記第３の演算手段による第２の演算の結果得られる第３の演算値と、前記第３のブランチに対応する第３のパスのパス情報である第３のパス情報であり、
前記第１の演算手段は、前記第１のブランチ情報と第３の演算値に対して、第１の演算を行うとともに、前記第３のブランチ情報と前記第３のパス情報に対して、前記第１の演算を行い、
前記第３の演算手段は、前記第１と第２の演算手段による演算の所定の時刻前に、前記第２の演算を行う
請求項１に記載の復号装置。
【請求項３】
前記所定の状態でマージされる３以上の数のブランチのうち、その数より少ない数のブランチがマージされるように前記所定の状態が分割された後の各状態でマージされるブランチを第１のブランチとする
請求項１に記載の復号装置。
【請求項４】
前記復号装置は、ビタビアルゴリズム、BCJR（Bahl,Cocke,Jelineck,Raviv）アルゴリズム、Log-MAP（Maximum A Posteriori Probability）アルゴリズム、または、Max-Log-MAPアルゴリズムで前記チャネル入力ビットを復号する
請求項１に記載の復号装置。
【請求項５】
前記復号装置は、１時刻ごとに前記チャネル入力ビットを復号し、
前記第１の演算手段は、前記第２乃至第４の演算手段による演算の前記１時刻前に、前記第１の演算を行う
請求項１に記載の復号装置。
【請求項６】
前記復号装置は、複数時刻ごとに前記チャネル入力ビットを復号し、
前記第１の演算手段は、前記第２乃至第４の演算手段による演算の前記複数時刻前に、前記第１の演算を行う
請求項１に記載の復号装置。
【請求項７】
符号制約をパーシャルレスポンスの状態遷移と組み合わせた場合のトレリスであって、前記パーシャルレスポンスのチャネルメモリ長よりも前記符号制約の記述に必要なメモリ長が長い場合のトレリスにしたがって、パーシャルレスポンスチャネル出力からチャネル入力ビットを復号する復号装置の復号方法において、
所定の状態でマージされる３以上の数のブランチのうち、その数より少ない数のブランチを第１のブランチとし、その第１のブランチに関する情報である第１のブランチ情報と、その第１のブランチに対応する第１のパスに関する情報である第１のパス情報に対して、第１の演算を行い、
前記第１の演算の結果得られる第１の演算値に対して第２の演算を行う
ステップを含む復号方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、復号装置および復号方法に関し、特に、符号制約をパーシャルレスポンスの状態遷移と組み合わせた場合のトレリスであって、パーシャルレスポンスのチャネルメモリ長よりも符号制約の記述に必要なメモリ長が長い場合のトレリスにしたがって、パーシャルレスポンスチャネル出力からチャネル入力ビットを復号する場合において、復号処理の高速化を実現することができるようにした復号装置および復号方法に関する。
【背景技術】
【０００２】
磁気ディスクや光ディスクなどに対して記録または再生を行う記録再生装置では、パーシャルレスポンスに等化した検出方法が広く用いられている。記録再生装置において、その記録再生装置の伝達特性に合ったパーシャルレスポンスが用いられる場合、雑音の強調を抑えることができる。また、記録再生装置において、パーシャルレスポンスの状態遷移を表すトレリスを用いたビタビアルゴリズムなどにより、チャネル入力ビット系列の最尤復号を容易に行うことが可能である。
【０００３】
例えば、伝達関数H(D)がH(D)=1-D2で表されるパーシャルレスポンスは、PR4(パーシャルレスポンス・クラス４)と呼ばれ、磁気記録再生装置においてよく用いられる。ここで、Ｄはチャネルビット１ビット分の時間Ｔの遅延を表す演算子である。PR4は、チャネルメモリ長が２であるため、状態数が４（=２2）の状態遷移で記述することができる。
【０００４】
図１は、PR4の状態遷移図である。
【０００５】
図１において、丸は、状態を表しており、丸の中に記述されるＳijは、状態名を表している。以下では、状態名がＳijである状態を状態Ｓijという。状態Ｓijのiとjは、チャネルビットのメモリに記憶される値を表しており、状態Ｓijは、状態Ｓijに到達する直前のチャネルビットがjであり、１つ前のチャネルビットがiである状態である。即ち、状態Ｓijの状態名であるＳijは、Ｓの後にチャネルビットのメモリに記憶される値が過去のものから順番に記述され、最後に状態Ｓijに到達する直前にチャネルビットのメモリに記憶された値が記述されたものである。
【０００６】
また、図１において、２つの状態Ｓijのうちの一方から他方に向かう矢印には、ラベルx/yが付されており、矢印は、チャネルビットの入力ｘに応じた状態Ｓijの遷移を表している。なお、ラベルのｙは、PR4の期待される出力値（以下、出力期待値という）である。
【０００７】
図１に示すように、PR４では、状態Ｓ00において、チャネルビットの入力が０である場合、状態Ｓ00は、状態Ｓ00に遷移し、このときの出力期待値は０であり、チャネルビットの入力が１である場合、状態Ｓ00は、状態Ｓ01に遷移し、このときの出力期待値は１である。また、状態Ｓ01において、チャネルビットの入力が０である場合、状態Ｓ01は、状態Ｓ10に遷移し、このときの出力期待値は０であり、チャネルビットの入力が１である場合、状態Ｓ01は、状態Ｓ11に遷移し、このときの出力期待値は１である。
【０００８】
さらに、状態Ｓ10において、チャネルビットの入力が１である場合、状態Ｓ10は、状態Ｓ01に遷移し、このときの出力期待値は０であり、チャネルビットの入力が０である場合、状態Ｓ10は、状態Ｓ00に遷移し、このときの出力期待値は−１である。また、状態Ｓ11において、チャネルビットの入力が０である場合、状態Ｓ11は、状態Ｓ10に遷移し、このときの出力期待値は−１であり、チャネルビットの入力が１である場合、状態Ｓ11は、状態Ｓ11に遷移し、このときの出力期待値は０である。
【０００９】
図２は、チャネルメモリ長が２である場合のトレリス線図を示している。
【００１０】
なお、図２においては、状態Ｓijを表す丸の中に状態名が記述されるのではなく、最も左側の列に、その右側のすべての丸に対応する状態Ｓijの状態名が記述されている。即ち、横方向に並ぶすべての丸は、最も左側の列に記述されている状態名の状態Ｓijを表している。また、図２において、矢印（ブランチ）に付与されるラベルは省略している。これらのことは、後述する図５、図６、図１２、図１５、図２０、図２１においても同様である。
【００１１】
図２では、状態Ｓ00は、チャネルビットの入力に応じて、状態Ｓ00または状態Ｓ01に遷移する。また、状態Ｓ10は、チャネルビットの入力に応じて、状態Ｓ00または状態Ｓ01に遷移し、状態Ｓ01は、チャネルビットの入力に応じて、状態Ｓ10または状態Ｓ11に遷移する。さらに、状態Ｓ11は、チャネルビットの入力に応じて、状態Ｓ10または状態Ｓ11に遷移する。
【００１２】
次に、パーシャルレスポンスチャネルに等化された再生信号の復号方法について説明する。再生信号に対しては、トレリスにしたがって、チャネル入力ビット系列の最尤復号またはビットごとのMAP（Maximum A Posteriori Probability）復号を行うことができる。チャネル入力ビット系列の最尤復号を行う復号器としては、ビタビ復号器がよく用いられる。
【００１３】
図３は、ビタビ復号器１０の構成を示すブロック図である。
【００１４】
図３のビタビ復号器１０は、BMU(Branch Metric Unit)１１、ACSU(Add-Compare-Select Unit)１２、およびSMU(Survivor Memory Unit)１３により構成される。
【００１５】
BMU１１には、ある時刻の再生信号が入力され、BMU１１は、その再生信号を基に、ブランチに関する情報として、ブランチメトリックと呼ばれるトレリス上の遷移が起こる確からしさを演算する。BMU１１は、ブランチメトリック(ブランチ情報)をACSU１２に供給する。
【００１６】
ACSU１２は、１つ前の処理で更新された、パスに関する情報である、パスメトリックと呼ばれる、各状態に到達した最も確からしいパスの確からしさと、BMU１１から供給されるブランチメトリックとに基づいて、次の時刻での各状態に到達する最も確からしいパスを選択し、パスメトリック(パス情報)を更新する。また、ACSU１２は、選択した最も確からしいパスを特定する情報をSMU１３に供給する。
【００１７】
SMU１３は、ACSU１２から供給される最も確からしいパスにを特定する情報に基づいて、各状態において最も確からしいパスに対応するトレリスへの入力を蓄積し、現在生き残っているパス上にある過去のトレリスへの入力を、復号結果として出力する。
【００１８】
以上のように、ビタビ復号器１０では、ACSU１２が、１つ前の処理で更新されたパスメトリックをフィードバックするので、復号処理の高速化に限界が生じる。
【００１９】
図４は、ACSUのうちの、状態ｓ１のパスメトリックを更新する回路３０の構成を示している。
【００２０】
なお、図４では、状態ｓ１でマージされるブランチは、４つの状態ｓ１乃至ｓ４からのブランチであるものとする。
【００２１】
図４の回路３０は、４つのメモリ３１−１乃至３１−４、加算器３２−１乃至３２−４、比較器３３、およびセレクタ３４により構成される。なお、図４において、SMU１３に供給する最も確からしいパスを特定する情報、即ちブランチの選択情報の出力については省略している。このことは、後述する図７乃至図１１、図１３、図１６、図１８と図１９、並びに図２２乃至図２５においても同様である。
【００２２】
メモリ３１−１乃至３１−４は、例えばフリップフロップ回路であり、時刻k-1における状態ｓ１，ｓ２，ｓ３，ｓ４のパスメトリックPMs1,k-1,PMs2,k-1,PMs3,k-1,PMs4,k-1をそれぞれ記憶する。メモリ３１−１乃至３１−４は、記憶しているパスメトリックPMs1,k-1,PMs2,k-1,PMs3,k-1,PMs4,k-1を、加算器３２−１乃至３２−４にぞれぞれ供給する。
【００２３】
加算器３２−１乃至３２−４は、メモリ３１−１乃至３１−４から供給されるパスメトリックPMs1,k-1,PMs2,k-1,PMs3,k-1,PMs4,k-1と、BMUから供給される状態ｓ１に入力されるブランチのブランチメトリックBM1,k,BM2,k,BM3,k,BM4,kとをそれぞれ加算する。加算器３２−１乃至３２−４は、加算した結果得られる加算値を、パスメトリックとして、比較器３３とセレクタ３４にそれぞれ供給する。
【００２４】
比較器３３は、パスメトリックを比較し、最も確からしいパスのパスメトリックを特定する情報を、セレクタ３４に供給する。例えば、比較器３３は、４つのパスメトリックのうちの最大のパスメトリックを、最も確からしいパスのパスメトリックとして、そのパスメトリックを特定する情報をセレクタ３４に供給する。
【００２５】
セレクタ３４は、比較器３３からの情報に基づいて、最も確からしいパスのパスメトリックを、時刻ｋにおける状態ｓ１のパスメトリックPMs1,kとして選択し、出力する。セレクタ３４により出力されたパスメトリックPMs1,kは、パスメトリックPMs1,k-1として、メモリ３１−１にフィードバックされ、記憶される。即ち、メモリ３１−１に記憶されている、時刻k-1における状態ｓ１のパスメトリックPMs1,k-1が、セレクタ３４から供給される時刻ｋにおける状態ｓ１のパスメトリックPMs1,kに更新される。
【００２６】
状態ｓ２乃至ｓ３に対応する回路も、回路３０と同様に構成される。なお、メモリ３１−１乃至３１−４は、各回路で共有される。即ち、ACSUは、回路３０と、回路３０と同様に構成される状態ｓ２乃至ｓ４に対応する回路からメモリ３１−１乃至３１−４を削除した回路により構成される。ACSUは、加算、比較、および選択の演算を、毎時刻、逐次行うことにより、パスメトリックを更新する。
【００２７】
以上のように、時刻kのパスメトリックは、時刻k+1のパスメトリックを更新する際に用いられるため、ACSUにおける演算は１時刻で完了される必要がある。
【００２８】
そこで、ACSUにおける演算を簡略化する手法として、ブランチメトリックを加算する順序を変更する方法が考案されている。(例えば、特許文献１参照)
【００２９】
次に、チャネルビットの符号化について説明する。
【００３０】
記録再生されるチャネルビット系列には、系に適した符号化が施される場合が多い。例えば、RLL（Run-Length Limited）符号化は、同じビットが連続する最小の回数と最大の回数のいずれか一方または両方を制限する。２つの符号ビット「１」の間に挟まれた「０」の連続の最小の回数ｄと最大の回数kが制限された(d,k)-RLL符号を、NRZI（Non Return to Zero Invert）方式で記録すると、同一の値のチャネルビットの連続は、最小(d+1)回、最大(k+1)回となる。
【００３１】
例えば、ブルーレイディスクで用いられている17PP（Parity Preserve）符号では、回数dが１に制限され、回数kが７に制限されている。このように、回数dが１に制限される場合、チャネルビットの極性反転の間隔は、最小でも時間２Ｔとなる。さらに、17PP符号では、最小の間隔の極性反転が連続する最大の回数ｒを６に制限している。また、MTR（maximum transition run）符号化は、チャネルビットの極性反転の連続回数を制限する。
【００３２】
上述したようなチャネルビットの符号制約は、パーシャルレスポンスの状態遷移と組み合わせることで、符号制約により禁止されたパターンに復号されることを防止することができる。また、場合によっては、トレリス上でのユークリッド距離を拡大し、エラーレート特性を改善することができる。
【００３３】
図５は、回数ｄが１に制限されたRLL符号がNRZI方式で記録されるときの符号制約を、チャネルメモリ長が２のパーシャルレスポンスの状態遷移と組み合わせた場合のトレリス線図である。
【００３４】
図５では、回数ｄが１に制限されるので、図５のトレリスは、図２のトレリスから、状態Ｓ10から状態Ｓ01への遷移を表すブランチと、状態Ｓ01から状態Ｓ10への遷移を表すブランチとが削除されたものとなっている。
【００３５】
図６は、回数kが２に制限されたRLL符号がNRZI記録されるときの符号制約を、チャネルメモリ長が２のパーシャルレスポンスの状態遷移と組み合わせた場合のトレリス線図である。
【００３６】
図６のトレリスでは、回数ｋが２の符号制約を状態遷移に組み入れるために、チャネルメモリ長が２である図２のトレリスにおける状態Ｓ00とＳ11がそれぞれ２つの状態Ｓ000とＳ100、状態Ｓ011とＳ111に分割されている。即ち、図６のトレリスでは、状態数が増加して６となっている。
【００３７】
また、図６では、回数ｋが２に制限されているので、図６のトレリスでは、過去にチャネルビット「０」が３回連続している状態Ｓ000では、チャネルビットの入力が「０」となる状態Ｓ000への遷移を表すブランチがない。同様に、過去にチャネルビット「１」が３回連続している状態Ｓ111では、チャネルビットの入力が「１」となる状態Ｓ111への遷移を表すブランチがない。
【００３８】
図７は、図６のトレリスにしたがって、１時刻ごとに復号を行う、従来のビタビ復号器のACSUの構成例を示している。
【００３９】
ここで、まず最初に、図７のACSU５０が演算する各状態Ｓのパスメトリックの更新式について説明する。
【００４０】
チャネルメモリ長が２のパーシャルレスポンスでは、チャネルビットの000,001,010,011,100,101,110,111に対応する最大８通りの出力期待値があり、BMUは、その出力期待値と、時刻k-1から時刻kに遷移する際の再生信号とから、ブランチメトリックBM0,k乃至BM7,kを演算する。
【００４１】
各状態Ｓのパスメトリックの更新は、８種類のブランチメトリックBM0,k乃至BM7,kを用いて、以下の式（１）で表される。
【００４２】
PMS000,k=PMS100,k-1+BM0,k
PMS100,k=PMS10,k-1+BM4,k
PMS10,k=max(PMS01,k-1+BM2,k,PMS011,k-1+BM6,k,PMS111,k-1+BM6,k)
PMS01,k=max(PMS10,k-1+ BM5,k,PMS100,k-1+BM1,k,PMS000,k-1+ BM1,k)
PMS011,k=PMS01,k-1+BM3,k
PMS111,k=PMS011,k-1+BM7,k
・・・（１）
【００４３】
なお、式（１）において、PMS000,k，PMS100,k，PMS10,k，PMS01,k，PMS011,k，PMS111,kは、時刻kの状態Ｓ000，Ｓ100，Ｓ10，Ｓ01，Ｓ011，Ｓ111のパスメトリックであり、PMS000,k-1，PMS100,k-1，PMS10,k-1，PMS01,k-1，PMS011,k-1，PMS111,k-1は、時刻k-1の状態Ｓ000，Ｓ100，Ｓ10，Ｓ01，Ｓ011，Ｓ111のパスメトリックである。
【００４４】
次に、式（１）の更新式を演算するACSU５０の構成について説明する。
【００４５】
図７のACSU５０は、メモリ５１−１乃至５１−６、加算器５２−１乃至５２−１０、並びに、max回路５３−１と５３−２により構成される。
【００４６】
メモリ５１−１乃至５１−６は、時刻k-1における状態Ｓ000,k-1，Ｓ100,k-1，Ｓ10,k-1，Ｓ01,k-1，Ｓ011,k-1，Ｓ111,k-1のパスメトリックPMS000,k-1，PMS100,k-1，PMS10,k-1，PMS01,k-1，PMS011,k-1，PMS111,k-1をそれぞれ記憶する。メモリ５１−１は、記憶しているパスメトリックPMS000,k-1を加算器５２−１に供給し、メモリ５１−２は、記憶しているパスメトリックPMS100,k-1を加算器５２−２と５２−３に供給する。
【００４７】
また、メモリ５１−３は、記憶しているパスメトリックPMS10,k-1を加算器５２−４と５２−５に供給し、メモリ５１−４は、記憶しているパスメトリックPMS01,k-1を加算器５２−６と５２−７に供給する。さらに、メモリ５１−５は、記憶しているパスメトリックPMS011,k-1を、加算器５２−８と５２−９に供給し、メモリ５１−６は、記憶しているパスメトリックPMS111,k-1を、加算器５２−１０に供給する。
【００４８】
加算器５２−１は、メモリ５１−１からのパスメトリックPMS000,k-1と、BMUからのブランチメトリックBM1,kとを加算し、その結果得られる加算値を、max回路５３−１に供給する。
【００４９】
加算器５２−２は、メモリ５１−２からのパスメトリックPMS100,k-1と、BMUからのブランチメトリックBM0,kとを加算し、パスメトリックPMS000,kを求める。即ち、加算器５２−２は、式（１）の１行目の式を演算する。このパスメトリックPMS000,kは、パスメトリックPMS000,k-1として、メモリ５１−１にフィードバックされ、記憶される。
【００５０】
加算器５２−３は、メモリ５１−２からのパスメトリックPMS100,k-1と、BMUからのブランチメトリックBM1,kとを加算し、その結果得られる加算値を、max回路５３−１に供給する。加算器５２−４は、メモリ５１−３からのパスメトリックPMS10,k-1と、BMUからのブランチメトリックBM4,kとを加算し、パスメトリックPMS100,kを求める。即ち、加算器５２−４は、式（１）の２行目の式を演算する。このパスメトリックPMS100,kは、パスメトリックPMS100,k―1として、メモリ５１−２にフィードバックされ、記憶される。
【００５１】
加算器５２−５は、メモリ５１−３からのパスメトリックPMS10,k-1と、BMUからのブランチメトリックBM5,kとを加算し、その結果得られる加算値を、max回路５３−１に供給する。加算器５２−６は、メモリ５１−４からのパスメトリックPMS01,k-1と、BMUからのブランチメトリックBM2,kとを加算し、その結果得られる加算値を、max回路５３−２に供給する。加算器５２−７は、メモリ５１−４からのパスメトリックPMS01,k-1と、BMUからのブランチメトリックBM3,kとを加算し、パスメトリックPMS011,kを求める。即ち、加算器５２−７は、式（１）の５行目の式を演算する。このパスメトリックPMS011,kは、パスメトリックPMS011,k-1として、メモリ５１−５にフィードバックされ、記憶される。
【００５２】
加算器５２−８は、メモリ５１−５からのパスメトリックPMS011,k-1と、BMUからのブランチメトリックBM6,kとを加算し、その結果得られる加算値を、max回路５３−２に供給する。加算器５２−９は、メモリ５１−５からのパスメトリックPMS011,k-1と、BMUからのブランチメトリックBM7,kとを加算し、パスメトリックPMS111,kを求める。即ち、加算器５２−９は、式（１）の６行目の式を演算する。このパスメトリックPMS111,kは、パスメトリックPMS111,k-1として、メモリ５１−６にフィードバックされて、記憶される。加算器５２−１０は、メモリ５１−６からのパスメトリックPMS111,k-1と、BMUからのブランチメトリックBM6,kとを加算し、その結果得られる加算値を、max回路５３−２に供給する。
【００５３】
max回路５３−１は、加算器５２−１、５２−３、および５２−５から供給される加算値のうちの最大値を、パスメトリックPMS01,kとして選択する。即ち、max回路５３−１は、式（１）の４行目の式を演算する。このパスメトリックPMS01,kは、パスメトリックPMS01,k-1として、メモリ５１−４にフィードバックされ、記憶される。
【００５４】
max回路５３−２は、加算器５２−６、５２−８、および５２−１０から供給される加算値のうちの最大値を、パスメトリックPMS10,kとして選択する。即ち、max回路５３−２は、式（１）の３行目の式を演算する。このパスメトリックPMS10,kは、パスメトリックPMS10,k-1として、メモリ５１−３にフィードバックされる。
【００５５】
以上のように、ACSU５０では、max回路５３−１と５３−２により、３つの加算値の最大値を選択する必要がある。これは、同一の状態Ｓにマージするブランチの数が３以上となるためであり、符号制約を記述するためのメモリ長が、パーシャルレスポンスのチャネルメモリ長よりも長いために、状態数が増加することによるものである。
【００５６】
このように、同一の状態Ｓにマージするブランチの数が増加すると、最大値の選択候補となる加算値が増加して、その選択に多大な時間を要することになり、これにより、ACSUの動作速度が低下してしまう。
【００５７】
図８は、図６のトレリスにしたがって、２時刻ごとに復号を行う、従来のビタビ復号器のACSUの構成例を示している。
【００５８】
ここで、まず最初に、図８のACSU６０が演算する各状態Ｓのパスメトリックの更新式について説明する。
【００５９】
図８では、BMUが、ブランチメトリックBM0,k,BM1,k,BM2,k,BM3,k,BM4,k,BM5,k,BM6,k、およびBM7,kのほかに、チャネルビットの000,001,010,011,100,101,110,111に対応する８通りの出力期待値と、時刻k-2から時刻k-1に遷移する際の再生信号とから、ブランチメトリックBM0,k-1,BM1,k-1,BM2,k-1,BM3,k-1,BM4,k-1,BM5,k-1,BM6,k-1,BM7,k-1を演算する。
【００６０】
各状態Ｓのパスメトリックの２時刻ごとの更新は、以下の式（２）で表される。
【００６１】
PMS000,k=PMS10,k-2+BM4,k-1+ BM0,k
PMS100,k=max(PMS01,k-2+BM2,k-1+BM4,k,PMS011,k-2+BM6,k-1+BM4,k,PMS111,k-2+BM6,k-1+BM4,k)
PMS10,k=max(PMS10,k-2+BM5,k-1+BM2,k,PMS100,k-2+BM1,k-1+BM2,k,PMS000,k-2+BM1,k-1+BM2,k,PMS01,k-2+BM3,k-1+BM6,k,PMS011,k-2+BM7,k-1+BM6,k)
PMS01,k=max(PMS01,k-2+BM2,k-1+BM5,k,PMS011,k-2+BM6,k-1+BM5,k,PMS111,k-2+BM6,k-1+BM5,k, PMS10,k-2+BM4,k-1+BM1,k,PMS100,k-2+ BM0,k-1+ BM1,k)
PMS011,k= max(PMS10,k-2+ BM5,k-1+BM3,k,PMS100,k-2+BM1,k-1+BM3,k,PMS000,k-2+ BM1,k-1+BM3,k) 
PMS111,k= PMS01,k-2+BM3,k-1+BM7,k
・・・（２）
【００６２】
次に、式（２）の更新式を演算するACSU６０の構成について説明する。
【００６３】
図８のACSU６０は、メモリ６１−１乃至６１−６、加算器６２−１乃至６２−１８、および、max回路６３−１乃至６３−４により構成される。
【００６４】
図８のACSU６０では、図７のACSU５０と同様に、加算器６２−１乃至６２−１８がパスメトリックPMS,kとブランチメトリックBMを加算し、max回路６３−１乃至６３−４が、最大値を選択して、メモリ６１−１乃至６１−６にフィードバックする。
【００６５】
具体的には、式（２）の１行目の式は、加算器６２−６により演算される。式（２）の２と３行目の式は、加算器６２−１０、６２−１４、および６２−１７、並びにmax回路６３−１により演算される。式（２）の４と５行目の式は、加算器６２−１，６２−３，６２−７，６２−１１、および６２−１５、並びにmax回路６３−２により演算される。
【００６６】
また、式（２）の６と７行目の式は、加算器６２−４，６２−８，６２−１２，６２−１６，６２−１８、並びにmax回路６３−３により演算される。式（２）の８と９行目の式は、加算器６２−２，６２−５、および６２−９、並びにmax回路６３−４により演算される。式（２）の１０行目の式は、加算器６２−１３により演算される。
【００６７】
以上のように、ACSU６０では、max回路６３−２と６３−３により、５つの加算値の最大値を選択する必要がある。従って、ACSU６０においても、最大値の選択に多くの時間を要する。
【００６８】
また、トレリスにしたがう復号のアルゴリズムは、ビタビアルゴリズムの他にも、BCJR（Bahl,Cocke,Jelineck,Raviv）アルゴリズムとして知られるMAPアルゴリズム、MAP復号を対数領域で行うLog-MAPアルゴリズム、その近似にあたるMax-Log-MAPアルゴリズムなどがある。これらのアルゴリズムにおいても、１つの状態でマージされるブランチの数が増加するにつれて演算が複雑になるという問題点がある(例えば、非特許文献１と２)。
【００６９】
図９は、図６のトレリスにしたがって、BCJRアルゴリズムで１時刻ごとに復号を行う従来の復号器の、各状態Ｓの確率を更新する回路７０の構成例を示している。
【００７０】
ここで、まず最初に、BCJRアルゴリズムにしたがう各状態Ｓの確率の更新式について説明する。
【００７１】
BCJRアルゴリズムでは、パスに関する情報である、トレリスを正方向に辿ったときの状態Ｓの時刻kの確率αS,k（パス情報）の更新は、時刻k-1の遷移前の状態Ｓ´の確率αS´,k-1と、ブランチに関する情報であるブランチの遷移確率γ（ブランチ情報）とを用いて、以下の式（３）で表される。
【００７２】
αS000,k=αS100,k-1×γ0,k
αS100,k=αS10,k-1×γ4,k
αS10,k=αS01,k-1×γ2,k＋αS011,k-1×γ6,k＋αS111,k-1×γ6,k
αS01,k=αS10,k-1×γ5,k＋αS100,k-1+γ1,k＋αS000,k-1×γ1,k
αS011,k=αS01,k-1×γ3,k
αS111,k=αS011,k-1×γ7,k
・・・（３）
【００７３】
なお、式（３）において、遷移確率γ0,k乃至γ7,kは、以下の式（４）で表される。
【００７４】
γ0,k=γk(Ｓ100,Ｓ000)
γ1,k=γk(Ｓ100,Ｓ01)=γk(Ｓ000,Ｓ01)
γ2,k=γk(Ｓ01，Ｓ10)
γ3,k=γk(Ｓ01，Ｓ011)
γ4,k=γk(Ｓ10，Ｓ100)
γ5,k=γk(Ｓ10，Ｓ01)
γ6,k=γk(Ｓ011，Ｓ10)=γk(Ｓ111，Ｓ10)
γ7,k=γk(Ｓ011，Ｓ111)
・・・（４）
【００７５】
なお、式（４）において、γk(Ｓ´,Ｓ)は時刻kに状態Ｓ´から状態Ｓに遷移するブランチの遷移確率を表す。
【００７６】
式（３）によれば、BCJRアルゴリズムにおける確率αS,kの更新は、ビタビアルゴリズムにおけるパスメトリックPMS,kの更新において、パスメトリックPMS,kを確率αS,kに、ブランチメトリックBMを遷移確率γに、最大値の選択の演算を加算の演算に、パスメトリックPMS,kとブランチメトリックBMの加算を確率αS,kと遷移確率γの乗算に、それぞれ置換することにより得られる。
【００７７】
従って、図９の回路７０は、図７のACSU５０のメモリ５１−１乃至５１−６をメモリ７１−１乃至７１−６に置換し、加算器５２−１乃至５２−１０を乗算器７２−１乃至７２−１０に置換し、max回路５３−１と５３−２をsum回路７３−１と７３−２に置換することにより構成される。即ち、図９の回路７０は、メモリ７１−１乃至７１−６、乗算器７２−１乃至７２−１０、並びにsum回路７３−１と７３−２により構成される。
【００７８】
乗算器７２−１乃至７２−１０には、メモリ７１−１乃至７１−６から確率αS,k-1が入力されるとともに、外部から遷移確率γが入力され、乗算器７２−１乃至７２−１０は、確率αS,kと遷移確率γを乗算し、その結果得られる乗算値を出力する。出力される乗算値のうちの確率αS,kは、確率αS,k-1として、メモリ７１−１，７１−２，７１−５、または７１−６にフィードバックされ、記憶される。その他の乗算値は、sum回路７３−１または７３−２に供給され、sum回路７３−１と７３−２は、入力されるすべての乗算値を加算し、その結果得られる確率αS,kを、確率αS,k-1として、メモリ７１−３または７１−４にフィードバックし、記憶させる。
【００７９】
具体的には、式（３）の１行目の式は、乗算器７２−２により演算される。式（３）の２行目の式は、乗算器７２−４により演算される。式（３）の３行目の式は、乗算器７２−６，７２−８、および７２−１０により得られた乗算値を、sum回路７３−２が加算することにより演算される。
【００８０】
式（３）の４行目の式は、乗算器７２−１、７２−３、および７２−５により得られた乗算値を、sum回路７３−１が加算することにより演算される。式（３）の５行目の式は、乗算器７２−７により演算される。式（３）の６行目の式は、乗算器７２−９により演算される。
【００８１】
以上のように、回路７０では、SUM７３−１と７３−２により、３つの乗算値を加算する必要があり、２つの乗算値を加算する場合に比べて加算に要する時間が増加する。その結果、復号処理に要する時間が増加する。
【００８２】
図１０は、図６のトレリスにしたがって、Log-MAPアルゴリズムで１時刻ごとに復号を行う従来の復号器の、各状態Ｓの尤度を更新する回路８０の構成例を示している。
【００８３】
ここで、まず最初に、Log-MAPアルゴリズムにしたがう各状態Ｓの尤度の更新式について説明する。
【００８４】
Log-MAPアルゴリズムでは、パスに関する情報である、トレリスを正方向に辿ったときの状態Ｓの時刻kの尤度αS,k（パス情報）の更新は、時刻k-1の遷移前の状態Ｓ´の尤度αS´、k-1と、ブランチに関する情報であるブランチの遷移における尤度γ（ブランチ情報）とを用いて、以下の式（５）で表される。
【００８５】
αS000,k=ln（exp（αS100,k-1＋γ0,k））
αS100,k=ln（exp（αS10,k-1＋γ4,k））
αS10,k=ln（exp（αS01,k-1＋γ2,k）＋exp（αS011,k-1＋γ6,k）＋exp（αS111,k-1＋γ6,k））
αS01,k=ln（exp（αS10,k-1＋γ5,k）＋exp（αS100,k-1+γ1,k）＋exp（αS000,k-1＋γ1,k））
αS011,k=ln（exp（αS01,k-1＋γ3,k））
αS111,k=ln（exp（αS011,k-1＋γ7,k））
・・・（５）
【００８６】
なお、式（５）において、尤度γ0,k乃至γ7,kは、上述した式（３）で表される。但し、この場合、式（３）におけるγk(Ｓ´,Ｓ)は、時刻kに状態Ｓ´から状態Ｓに遷移するブランチの遷移における尤度を表す。
【００８７】
また、右辺において、３以上のexpを加算した値の対数をとる場合、尤度αS,kの更新は、Log-Sum演算と呼ばれる以下の式（６）を繰り返し用いることにより計算することができる。
【００８８】
ln(exp(A)+exp(B))=max(A,B)+ln(1+exp(-|B-A|)
・・・（６）
【００８９】
式（５）によれば、Log-MAPアルゴリズムにおける尤度αS,kの更新は、ビタビアルゴリズムにおけるパスメトリックPMS,kの更新において、パスメトリックPMS,kを尤度αS,kに、ブランチメトリックBMを尤度γに、最大値の選択の演算をLog-Sum演算に、パスメトリックPMS,kとブランチメトリックBMの加算を尤度αS,kと尤度γの加算に、それぞれ置換することにより得られる。
【００９０】
従って、図１０の回路８０は、図７のACSU５０のメモリ５１−１乃至５１−６をメモリ８１−１乃至８１−６に置換し、加算器５２−１乃至５２−１０を加算器８２−１乃至８２−１０に置換し、max回路５３−１と５３−２をlog-sum回路８３−１と８３−２に置換することにより構成される。即ち、図１０の回路８０は、メモリ８１−１乃至８１−６、加算器８２−１乃至８２−１０、並びに、log-sum回路８３−１と８３−２により構成される。
【００９１】
加算器８２−１乃至８２−１０には、メモリ８１−１乃至８１−６から尤度αS,k-1が入力されるとともに、外部から尤度γが入力され、加算器８２−１乃至８２−１０は、尤度αS,kと尤度γを加算し、その結果得られる加算値を出力する。出力される加算値のうちの尤度αS,kは、尤度αS,k-1として、メモリ８１−１，８１−２，８１−５、または８１−６にフィードバックされ、記憶される。その他の加算値は、log-sum回路８３−１または８３−２に供給され、Log-sum回路８３−１と８３−２は、上述した式（６）にしたがって、入力されるすべての加算値のLog-Sum演算を行い、その結果得られる尤度αS,kを、尤度αS,k-1として、メモリ８１−３または８１−４にフィードバックし、記憶させる。
【００９２】
具体的には、式（５）の１行目の式は、加算器８２−２により演算される。式（５）の２行目の式は、加算器８２−４により演算される。式（５）の３行目の式は、加算器８２−６，８２−８、および８２−１０により得られた加算値を、log-sum回路８３−２が加算することにより演算される。
【００９３】
式（５）の４行目の式は、加算器８２−１、８２−３、および８２−５により得られた加算値を、log-sum回路８３−１が加算することにより演算される。式（５）の５行目の式は、加算器８２−７により演算される。式（５）の６行目の式は、加算器８２−９により演算される。
【００９４】
以上のように、回路８０では、log-sum回路８３−１と８３−２により、３入力のLog-Sum演算を行う必要があり、２入力のLog-Sum演算を行う場合に比べて、Log-Sum演算に要する時間が増加する。その結果、復号処理に要する時間が増加する。
【００９５】
図１１は、図６のトレリスにしたがって、Max-Log-MAPアルゴリズムで１時刻ごとに復号を行う従来の復号器の、各状態Ｓの尤度を更新する回路９０の構成例を示している。
【００９６】
ここで、まず最初に、Max-Log-MAPアルゴリズムにしたがう各状態Ｓの尤度の更新式について説明する。
【００９７】
Max-Log-MAPアルゴリズムでは、トレリスを正方向に辿ったときの状態Ｓの時刻kの尤度αS,kの更新式は、上述した式（５）のLog-Sum演算を最大値の選択の演算に置換することにより得られる。即ち、尤度αS,kの更新は、以下の式（７）で表される。
【００９８】
αS000,k=ln（exp（αS100,k-1＋γ0,k））
αS100,k=ln（exp（αS10,k-1＋γ4,k））
αS10,k=max（ln（exp（αS01,k-1＋γ2,k）），ln（exp（αS011,k-1＋γ6,k）），ln（exp（αS111,k-1＋γ6,k）））
αS01,k=max（ln（exp（αS10,k-1＋γ5,k）），ln（exp（αS100,k-1+γ1,k）），ln（exp（αS000,k-1＋γ1,k）））
αS011,k=ln（exp（αS01,k-1＋γ3,k））
αS111,k=ln（exp（αS011,k-1＋γ7,k））
・・・（７）
【００９９】
式（７）によれば、Max-Log-MAPアルゴリズムにおける尤度αS,kの更新は、ビタビアルゴリズムにおけるパスメトリックPMS,kの更新において、パスメトリックPMS,kを尤度αS,kに、ブランチメトリックBMを尤度γに、パスメトリックPMS,kとブランチメトリックBMの加算を尤度αS,kと尤度γの加算に、それぞれ置換することにより得られる。
【０１００】
従って、図１１の回路９０は、図７のACSU５０のメモリ５１−１乃至５１−６をメモリ９１−１乃至９１−６に置換し、加算器５２−１乃至５２−１０を加算器９２−１乃至９２−１０に置換し、max回路５３−１と５３−２をmax回路９３−１と９３−２に置換することにより構成される。即ち、図１１の回路９０は、メモリ９１−１乃至９１−６、加算器９２−１乃至９２−１０、並びに、max回路９３−１と９３−２により構成される。
【０１０１】
加算器９２−１乃至９２−１０には、メモリ９１−１乃至９１−６から尤度αS,k-1が入力されるとともに、外部から尤度γが入力され、加算器９２−１乃至９２−１０は、尤度αS,kと尤度γを加算し、その結果得られる加算値を出力する。出力される加算値のうちの尤度αS,kは、尤度αS,k-1として、メモリ９１−１，９１−２，９１−５、または９１−６にフィードバックされ、記憶される。その他の加算値は、max回路９３−１または９３−２に供給され、max回路９３−１と９３−２は、入力される加算値の最大値の選択の演算を行い、その結果得られる尤度αS,kを、尤度αS,k-1として、メモリ９１−３または９１−４にフィードバックし、記憶させる。
【０１０２】
具体的には、式（７）の１行目の式は、加算器９２−２により演算される。式（７）の２行目の式は、加算器９２−４により演算される。式（７）の３行目の式は、加算器９２−６，９２−８、および９２−１０により得られた加算値を、max回路９３−２が加算することにより演算される。
【０１０３】
式（７）の４行目の式は、加算器９２−１、９２−３、および９２−５により得られた加算値を、max回路９３−１が加算することにより演算される。式（７）の５行目の式は、加算器９２−７により演算される。式（７）の６行目の式は、加算器９２−９により演算される。
【０１０４】
以上のように、回路９０では、max回路９３−１と９３−２により、３つの加算値から最大値を選択する必要があり、２つの加算値から最大値を選択する場合に比べて、選択に要する時間が増加する。その結果、復号処理に要する時間が増加する。
【０１０５】
【特許文献１】特開平７−１８３８１９号公報
【非特許文献１】L. R. Bahl, J. Cocke, F. Jelinek, and J. Raviv, ”Optimal Decoding of Linear COdes for Minimizing Symbol Error Rate,” IEEE Transactions on Information Theory, vol. IT-20, pp. 284-287, March 1974.
【非特許文献２】P. Robertson, E. Villebrum, and P. Hoeher, ”A Comparison of Optimal and Sub-Optimal MAP Decoding Algorithms Operating in the Log Domain,” in Proc. ICC ’95, pp. 1009-1013, June 1995.
【発明の開示】
【発明が解決しようとする課題】
【０１０６】
以上のように、符号制約を記述するためのメモリ長が、パーシャルレスポンスのチャネルメモリ長よりも長い場合、同一の状態Ｓでマージされるブランチの最大の数が３以上となるため、ブランチの最大の数が２である場合に比べて、復号処理に要する時間が増加してしまう。
【０１０７】
本発明は、このような状況に鑑みてなされたものであり、符号制約をパーシャルレスポンスの状態遷移と組み合わせた場合のトレリスであって、パーシャルレスポンスのチャネルメモリ長よりも符号制約の記述に必要なメモリ長が長い場合のトレリスにしたがって、パーシャルレスポンスチャネル出力からチャネル入力ビットを復号する場合において、復号処理の高速化を実現することができるようにするものである。
【課題を解決するための手段】
【０１０８】
本発明の一側面の復号装置は、符号制約をパーシャルレスポンスの状態遷移と組み合わせた場合のトレリスであって、前記パーシャルレスポンスのチャネルメモリ長よりも前記符号制約の記述に必要なメモリ長が長い場合のトレリスにしたがって、パーシャルレスポンスチャネル出力からチャネル入力ビットを復号する復号装置において、所定の状態でマージされる３以上の数のブランチのうち、その数より少ない数のブランチを第１のブランチとし、その第１のブランチに関する情報である第１のブランチ情報と、その第１のブランチに対応する第１のパスに関する情報である第１のパス情報に対して、第１の演算を行う第１の演算手段と、前記第１の演算の結果得られる第１の演算値に対して第２の演算を行う第２の演算手段とを備える。
【０１０９】
前記復号装置は、前記所定の状態でマージされる３以上の数のブランチのうち、ブランチ情報が同一である第２のブランチに対応する第２のパスに関する情報である第２のパス情報に対して、第２の演算を行う第３の演算手段をさらに設け、前記第１のブランチ情報は、前記第２のブランチのブランチ情報である第２のブランチ情報と、前記所定の状態でマージされる３以上の数のブランチのうちの、前記第２のブランチ以外のブランチである第３のブランチのブランチ情報である第３のブランチ情報であり、前記第１のパス情報は、前記第３の演算手段による第２の演算の結果得られる第３の演算値と、前記第３のブランチに対応する第３のパスのパス情報である第３のパス情報であり、前記第１の演算手段は、前記第１のブランチ情報と第３の演算値に対して、第１の演算を行うとともに、前記第３のブランチ情報と前記第３のパス情報に対して、前記第１の演算を行い、前記第３の演算手段は、前記第１と第２の演算手段による演算の所定の時刻前に、前記第２の演算を行うことができる。
【０１１０】
前記所定の状態でマージされる３以上の数のブランチのうち、その数より少ない数のブランチがマージされるように前記所定の状態が分割された後の各状態でマージされるブランチを第１のブランチとすることができる。
【０１１１】
前記復号装置は、ビタビアルゴリズム、BCJR（Bahl,Cocke,Jelineck,Raviv）アルゴリズム、Log-MAP（Maximum A Posteriori Probability）アルゴリズム、または、Max-Log-MAPアルゴリズムで前記チャネル入力ビットを復号することができる。但し、ここで、チャネル入力ビットの復号とは、各チャネル入力ビットの硬判定情報を出力するものだけではなく、事後確率や尤度などの軟判定情報を出力するものも含むものとする。
【０１１２】
前記復号装置は、１時刻ごとに前記チャネル入力ビットを復号し、前記第１の演算手段は、前記第２乃至第４の演算手段による演算の前記１時刻前に、前記第１の演算を行うことができる。
【０１１３】
前記復号装置は、複数時刻ごとに前記チャネル入力ビットを復号し、前記第１の演算手段は、前記第２乃至第４の演算手段による演算の前記複数時刻前に、前記第１の演算を行うことができる。
【０１１４】
本発明の一側面の復号方法は、符号制約をパーシャルレスポンスの状態遷移と組み合わせた場合のトレリスであって、前記パーシャルレスポンスのチャネルメモリ長よりも前記符号制約の記述に必要なメモリ長が長い場合のトレリスにしたがって、パーシャルレスポンスチャネル出力からチャネル入力ビットを復号する復号装置の復号方法において、所定の状態でマージされる３以上の数のブランチのうち、その数より少ない数のブランチを第１のブランチとし、その第１のブランチに関する情報である第１のブランチ情報と、その第１のブランチに対応する第１のパスに関する情報である第１のパス情報に対して、第１の演算を行い、前記第１の演算の結果得られる第１の演算値に対して第２の演算を行うステップを含む。
【０１１５】
本発明の一側面においては、所定の状態でマージされる３以上の数のブランチのうち、その数より少ない数のブランチが第１のブランチとされ、その第１のブランチに関する情報である第１のブランチ情報と、その第１のブランチに対応する第１のパスに関する情報である第１のパス情報に対して、第１の演算が行われ、前記第１の演算の結果得られる第１の演算値に対して第２の演算が行われる。
【発明の効果】
【０１１６】
以上のように、本発明の一側面によれば、符号制約をパーシャルレスポンスの状態遷移と組み合わせた場合のトレリスであって、パーシャルレスポンスのチャネルメモリ長よりも符号制約の記述に必要なメモリ長が長い場合のトレリスにしたがって、パーシャルレスポンスチャネル出力からチャネル入力ビットを復号する場合において、復号処理の高速化を実現することができる。
【発明を実施するための最良の形態】
【０１１７】
以下に本発明の実施の形態を説明するが、本発明の構成要件と、明細書又は図面に記載の実施の形態との対応関係を例示すると、次のようになる。この記載は、本発明をサポートする実施の形態が、明細書又は図面に記載されていることを確認するためのものである。従って、明細書又は図面中には記載されているが、本発明の構成要件に対応する実施の形態として、ここには記載されていない実施の形態があったとしても、そのことは、その実施の形態が、その構成要件に対応するものではないことを意味するものではない。逆に、実施の形態が構成要件に対応するものとしてここに記載されていたとしても、そのことは、その実施の形態が、その構成要件以外の構成要件には対応しないものであることを意味するものでもない。
【０１１８】
本発明の一側面の復号装置は、
符号制約をパーシャルレスポンスの状態遷移と組み合わせた場合のトレリスであって、前記パーシャルレスポンスのチャネルメモリ長よりも前記符号制約の記述に必要なメモリ長が長い場合のトレリスにしたがって、パーシャルレスポンスチャネル出力からチャネル入力ビットを復号する復号装置において、
所定の状態でマージされる３以上の数のブランチのうち、その数より少ない数のブランチを第１のブランチとし、その第１のブランチに関する情報である第１のブランチ情報（例えば、ブランチメトリック）と、その第１のブランチに対応する第１のパスに関する情報である第１のパス情報（例えば、パスメトリック）に対して、第１の演算(例えば、加算)を行う第１の演算手段（例えば、図１８の加算器１３６−１と１３６−２）と、
前記第１の演算の結果得られる第１の演算値に対して第２の演算（例えば、最大値の選択）を行う第２の演算手段(例えば、図１８の比較器１３７とセレクタ１３８)と
を備える。
【０１１９】
本発明の一側面の復号装置は、
前記所定の状態でマージされる３以上の数のブランチのうち、ブランチ情報が同一である第２のブランチに対応する第２のパスに関する情報である第２のパス情報に対して、第２の演算を行う第３の演算手段(例えば、図１８の比較器１３３とセレクタ１３４)
をさらに備え、
前記第１のブランチ情報は、前記第２のブランチのブランチ情報である第２のブランチ情報と、前記所定の状態でマージされる３以上の数のブランチのうちの、前記第２のブランチ以外のブランチである第３のブランチのブランチ情報である第３のブランチ情報であり、
前記第１のパス情報は、前記第３の演算手段による第２の演算の結果得られる第３の演算値と、前記第３のブランチに対応する第３のパスのパス情報である第３のパス情報であり、
前記第１の演算手段は、前記第１のブランチ情報と第３の演算値に対して、第１の演算を行うとともに、前記第３のブランチ情報と前記第３のパス情報に対して、前記第１の演算を行い、
前記第３の演算手段は、前記第１と第２の演算手段による演算の所定の時刻前に、前記第２の演算を行う。
【０１２０】
本発明の一側面の復号方法は、
符号制約をパーシャルレスポンスの状態遷移と組み合わせた場合のトレリスであって、前記パーシャルレスポンスのチャネルメモリ長よりも前記符号制約の記述に必要なメモリ長が長い場合のトレリスにしたがって、パーシャルレスポンスチャネル出力からチャネル入力ビットを復号する復号装置の復号方法において、
所定の状態でマージされる３以上の数のブランチのうち、その数より少ない数のブランチを第１のブランチとし、その第１のブランチに関する情報である第１のブランチ情報（例えば、ブランチメトリック）と、その第１のブランチに対応する第１のパスに関する情報である第１のパス情報(例えば、パスメトリック)に対して、第１の演算(例えば、加算)を行い(例えば、図１４のステップＳ１)、
前記第１の演算の結果得られる第１の演算値に対して第２の演算(例えば、最大値の選択)を行う(例えば、図１４のステップＳ２)
ステップを含む。
【０１２１】
以下、本発明を適用した具体的な実施の形態について、図面を参照しながら詳細に説明する。
【０１２２】
図１２は、回数kが２に制限されたRLL符号がNRZI記録されるときの符号制約を、チャネルメモリ長が２のパーシャルレスポンスの状態遷移と組み合わせた場合のトレリス線図である。
【０１２３】
図１２のトレリス線図では、８つの状態Ｓ000，Ｓ100，Ｓ010，Ｓ110，Ｓ001，Ｓ101，Ｓ011、およびＳ111の遷移が表されている。
【０１２４】
なお、状態Ｓ010とＳ110の遷移は同一であり、状態Ｓ001とＳ101の遷移は同一であるが、図１２では、それぞれの状態遷移が別々に表されている。即ち、図１２では、図６のトレリス線図における状態Ｓ10とＳ01が、それぞれ、状態Ｓ010とＳ110、状態Ｓ001とＳ101に分割されている。
【０１２５】
具体的には、図１２のトレリス線図は、状態Ｓ000が状態Ｓ001に遷移し、状態Ｓ100が状態Ｓ000またはＳ001に遷移することを表している。また、状態Ｓ010とＳ110は、状態Ｓ100とＳ101に遷移し、状態Ｓ001とＳ101は、状態Ｓ010とＳ011に遷移することを表している。さらに、状態Ｓ011が状態Ｓ110とＳ111に遷移し、状態Ｓ111が状態Ｓ110に遷移すること表している。
【０１２６】
以上のように、図１２では、図６のトレリス線図における状態Ｓ10とＳ01が、それぞれ、状態Ｓ010とＳ110、状態Ｓ001とＳ101に分割されているので、同一の状態Ｓでマージされるブランチの最大の数は２となっている。
【０１２７】
図１３は、図１２のトレリスにしたがって１時刻ごとにチャネル入力ビット系列を復号する、本発明を適用したビタビ復号器のACSU１００の構成例を示している。
【０１２８】
ここで、まず最初に、図１２のACSU１００が演算する各状態Ｓのパスメトリックの更新式について説明する。
【０１２９】
上述したように、チャネルメモリ長が２のパーシャルレスポンスでは、チャネルビットの000,001,010,011,100,101,110,111に対応する最大８通りの出力期待値があり、BMUは、その出力期待値と、時刻k-1から時刻kに遷移する際の再生信号とから、ブランチメトリックBM0,k乃至BM7,kを演算する。
【０１３０】
なお、パーシャルレスポンスの伝達関数の係数によっては、異なるチャネルビットに対応する出力期待値が一致する場合があるため、必ずしも８種類の異なるブランチメトリックを演算する必要はない。
【０１３１】
各状態Ｓのパスメトリックの更新は、８種類のブランチメトリックBM0,k乃至BM7,kを用いて、以下の式（８）で表される。
【０１３２】
PMS000,k=PMS100,k-1+BM0,k
PMS100,k=max（PMS010,k-1+BM4,k,PMS110,k-1+BM4,k）
PMS010,k=max(PMS001,k-1+BM2,k,PMS101,k-1+BM2,k)
PMS110,k=max(PMS011,k-1+BM6,k,PMS111,k-1+BM6,k)
PMS001,k=max(PMS100,k-1+BM1,k,PMS000,k-1+ BM1,k)
PMS101,k=max(PMS010,k-1+BM5,k,PMS100,k-1+ BM5,k)
PMS011,k=max（PMS001,k-1+BM3,k,PMS101,k-1+ BM3,k）
PMS111,k=PMS011,k-1+BM7,k
・・・（８）
【０１３３】
次に、式（８）の更新式を演算するACSU１００の構成について説明する。
【０１３４】
図１３のACSU１００は、メモリ１０１−１乃至１０１−８、加算器１０２−１乃至１０２−１４、およびmax回路１０３−１乃至１０３−６により構成される。
【０１３５】
メモリ１０１−１乃至１０１−８は、時刻k-1における状態Ｓ000，Ｓ100，Ｓ010，Ｓ110，Ｓ001，Ｓ101，Ｓ011，Ｓ111のパスメトリックPMS000,k-1，PMS100,k-1，PMS010,k-1，PMS110,k-1，PMS001,k-1，PMS101,k-1，PMS011,k-1，PMS111,k-1をそれぞれ記憶する。メモリ１０１−１は、記憶しているパスメトリックPMS000,k-1を加算器１０２−１に供給し、メモリ１０１−２は、記憶しているパスメトリックPMS100,k-1を加算器１０２−２と１０２−３に供給する。
【０１３６】
また、メモリ１０１−３は、記憶しているパスメトリックPMS010,k-1を加算器１０２−４と１０２−５に供給し、メモリ１０１−４は、記憶しているパスメトリックPMS110,k-1を加算器１０２−６と１０２−７に供給する。さらに、メモリ１０１−５は、記憶しているパスメトリックPMS001,k-1を、加算器１０２−８と１０２−９に供給し、メモリ１０１−６は、記憶しているパスメトリックPMS101,k-1を、加算器１０２−１０と１０２−１１に供給する。また、メモリ１０１−７は、記憶しているパスメトリックPMS011,k-1を、加算器１０２−１２と１０２−１３に供給し、メモリ１０１−８は、記憶しているパスメトリックPMS111,k-1を、加算器１０２−１４に供給する。
【０１３７】
加算器１０２−１は、メモリ１０１−１からのパスメトリックPMS000,k-1と、BMUからのブランチメトリックBM1,kとを加算し、その結果得られる加算値をmax回路１０３−４に供給する。加算器１０２−２は、メモリ１０１−２からのパスメトリックPMS100,k-1と、BMUからのブランチメトリックBM0,kとを加算し、パスメトリックPMS000,kを求める。即ち、加算器１０２−２は、式（８）の１行目の式を演算する。このパスメトリックPMS000,kは、パスメトリックPMS000,k-1として、メモリ１０１−１にフィードバックされる。
【０１３８】
加算器１０２−３は、メモリ１０１−２からのパスメトリックPMS100,k-1と、BMUからのブランチメトリックBM1,kとを加算し、その結果得られる加算値をmax回路１０３−４に供給する。加算器１０２−４は、メモリ１０１−３からのパスメトリックPMS010,k-1と、BMUからのブランチメトリックBM4,kとを加算し、max回路１０３−１に供給する。
【０１３９】
加算器１０２−５は、メモリ１０１−３からのパスメトリックPMS010,k-1と、BMUからのブランチメトリックBM5,kとを加算し、その結果得られる加算値をmax回路１０３−５に供給する。加算器１０２−６は、メモリ１０１−４からのパスメトリックPMS110,k-1と、BMUからのブランチメトリックBM4,kとを加算し、その結果得られる加算値をmax回路１０３−１に供給する。加算器１０２−７は、メモリ１０１−４からのパスメトリックPMS110,k-1と、BMUからのブランチメトリックBM5,kとを加算し、max回路１０３−５に供給する。
【０１４０】
加算器１０２−８は、メモリ１０１−５からのパスメトリックPMS001,k-1と、BMUからのブランチメトリックBM2,kとを加算し、その結果得られる加算値をmax回路１０３−２に供給する。加算器１０２−９は、メモリ１０１−５からのパスメトリックPMS001,k-1と、BMUからのブランチメトリックBM3,kとを加算し、その結果得られる加算値をmax回路１０３−６に供給する。
【０１４１】
加算器１０２−１０は、メモリ１０１−６からのパスメトリックPMS101,k-1と、BMUからのブランチメトリックBM2,kとを加算し、その結果得られる加算値をmax回路１０３−２に供給する。加算器１０２−１１は、メモリ１０１−６からのパスメトリックPMS101,k-1と、BMUからのブランチメトリックBM3,kとを加算し、その結果得られる加算値をmax回路１０３−６に供給する。加算器１０２−１２は、メモリ１０１−７からのパスメトリックPMS011,k-1と、BMUからのブランチメトリックBM6,kとを加算し、その結果得られる加算値をmax回路１０３−３に供給する。
【０１４２】
加算器１０２−１３は、メモリ１０１−７からのパスメトリックPMS011,k-1と、BMUからのブランチメトリックBM7,kとを加算し、パスメトリックPMS111,k-1を供給する。即ち、加算器１０２−１３は、式（８）の８行目の式を演算する。このパスメトリックPMS111,kは、パスメトリックPMS111,k-1として、メモリ１０１−８にフィードバックされる。加算器１０２−１４は、メモリ１０１−８からのパスメトリックPMS111,k-1と、BMUからのブランチメトリックBM6,kとを加算し、その結果得られる加算値をmax回路１０３−３に供給する。
【０１４３】
max回路１０３−１は、加算器１０２−４と１０２−６から供給される加算値を比較し、その２つの加算値の最大値を、パスメトリックPMS100,kとして選択する。即ち、max回路１０３−２は、式（８）の２行目の式を演算する。このパスメトリックPMS100,kは、パスメトリックPMS100,k-1として、メモリ１０１−２にフィードバックされる。
【０１４４】
max回路１０３−２は、加算器１０２−８と１０２−１０から供給される加算値を比較し、その２つの加算値の最大値を、パスメトリックPMS010,kとして選択する。即ち、max回路１０３−２は、式（８）の３行目の式を演算する。このパスメトリックPMS010,kは、パスメトリックPMS010,k-1として、メモリ１０１−３にフィードバックされる。
【０１４５】
max回路１０３−３は、加算器１０２−１２と１０２−１４から供給される加算値を比較し、その２つの加算値の最大値を、パスメトリックPMS110,kとして選択する。即ち、max回路１０３−３は、式（８）の４行目の式を演算する。このパスメトリックPMS110,kは、パスメトリックPMS110,k-1として、メモリ１０１−４にフィードバックされる。
【０１４６】
max回路１０３−４は、加算器１０２−１と１０２−３から供給される加算値を比較し、その２つの加算値の最大値を、パスメトリックPMS001,kとして選択する。即ち、max回路１０３−４は、式（８）の５行目の式を演算する。このパスメトリックPMS001,kは、パスメトリックPMS001,k-1として、メモリ１０１−５にフィードバックされる。
【０１４７】
max回路１０３−５は、加算器１０２−５と１０２−７から供給される加算値を比較し、その２つの加算値の最大値を、パスメトリックPMS101,kとして選択する。即ち、max回路１０３−５は、式（８）の６行目の式を演算する。このパスメトリックPMS101,kは、パスメトリックPMS101,k-1として、メモリ１０１−６にフィードバックされる。
【０１４８】
max回路１０３−６は、加算器１０２−９と１０２−１１から供給される加算値を比較し、その２つの加算値の最大値を、パスメトリックPMS111,kとして選択する。即ち、max回路１０３−６は、式（８）の７行目の式を演算する。このパスメトリックPMS111,kは、パスメトリックPMS111,k-1として、メモリ１０１−８にフィードバックされる。
【０１４９】
以上のように、ACSU１００は、状態Ｓ10とＳ01を、それぞれ、状態Ｓ010とＳ110、状態Ｓ001とＳ101に分割したトレリスにしたがって復号処理を行うので、max回路１０３−１乃至１０３−６は、２つの加算値の最大値を選択すればよい。従って、ACSU１００は、３つの加算値の最大値を選択する必要がある図７のACSU５０に比べて、演算に要する時間を短縮することができる。
【０１５０】
次に、図１４を参照して、図１３のACSU１００が各状態Ｓのパスメトリックの更新を行う更新処理について説明する。この更新処理は、加算器１０２−１乃至１０２−１４にパスメトリックPMS,k-1とブランチメトリックBMが供給されたとき、開始される。
【０１５１】
ステップＳ１において、加算器１０２−１は、パスメトリックPMS000,k-1とブランチメトリックBM1,kとを加算し、その結果得られる加算値をmax回路１０３−４に供給する。また、同様に、加算器１０２−３乃至１０２−１２、および、加算器１０２−１４は、パスメトリックPMS,k-1とブランチメトリックBMとを加算し、その結果得られる加算値をmax回路１０３−１乃至１０３−６のいずれかに供給する。さらに、加算器１０２−２と１０２−１３は、パスメトリックPMS,k-1とブランチメトリックBMとを加算してパスメトリックPMS,kを求め、そのパスメトリックPMS,kをパスメトリックS,k-1として、メモリ１０１−１または１０１−８にフィードバックする。
【０１５２】
ステップＳ１の処理後は、ステップＳ２に進み、max回路１０３−１は、加算器１０２−４と１０２−６から入力される加算値を比較し、その２つの加算値の最大値をパスメトリックPMS100,kとして選択する。また、同様に、max回路１０３−２乃至１０３−６は、入力される２つの加算値を比較し、その２つの加算値の最大値をパスメトリックPMS,kとして選択する。
【０１５３】
ステップＳ２の処理後は、ステップＳ３に進み、max回路１０３−１は、ステップＳ２において選択された最大値であるパスメトリックPMS100,kを、パスメトリックPMS100,k-1として、メモリ１０１−２にフィードバックする。また、同様に、max回路１０３−２乃至１０３−６は、ステップＳ２において選択された最大値であるパスメトリックPMS,kを、パスメトリックPMS,k-1として、メモリ１０１−３乃至１０１−７のいずれかにフィードバックする。そして、処理は終了する。
【０１５４】
次に、図１５乃至図２２を参照して、状態Ｓ10とＳ01を分割しないトレリスにしたがって、チャネル入力ビット系列を復号する場合のビタビ復号器について説明する。
【０１５５】
図１５は、回数kが２に制限されたRLL符号がNRZI記録されるときの符号制約を、チャネルメモリ長が２のパーシャルレスポンスの状態遷移と組み合わせた場合のトレリス線図である。
【０１５６】
図１５のトレリスでは、図１２のトレリスにおける状態Ｓ010とＳ110、および、状態Ｓ001とＳ101が、それぞれ、状態Ｓ10,Ｓ01として共通化されている。即ち、図１５のトレリス線図は、図６のトレリス線図と同一である。
【０１５７】
図１６は、図１５のトレリスにしたがって１時刻ごとにチャネル入力ビット系列を復号するビタビ復号器のACSUのうちの、状態Ｓ10のパスメトリックPMS10,kを更新する回路１１０の構成例を示している。
【０１５８】
図１６の回路１１０は、メモリ１１１−１乃至１１１−３と１１７、比較器１１２と１１５、セレクタ１１３と１１６、並びに、加算器１１４−１と１１４−２により構成され、上述した式（１）の３行目の式を演算する。
【０１５９】
メモリ１１１−１は、パスメトリックPMS01,k-1を記憶し、記憶しているパスメトリックPMS01,k-1を加算器１１４−１に供給する。メモリ１１１−２と１１１−３は、パスメトリックPMS011,k-1とPMS111,k-1を記憶し、記憶しているパスメトリックPMS011,k-1とPMS111,k-1を比較器１１２とセレクタ１１３に供給する。
【０１６０】
比較器１１２は、メモリ１１１−２と１１１−３から供給されるパスメトリックPMS011,k-1とPMS111,k-1を比較し、パスメトリックPMS011,k-1とPMS111,k-1のうちの最大値を特定する情報を、比較結果としてセレクタ１１３に供給する。
【０１６１】
セレクタ１１３は、比較器１１２からの比較結果に基づいて、メモリ１１１−２と１１１−３から供給されるパスメトリックPMS011,k-1とPMS111,k-1のうちの最大値（max（PMS011,k-1,PMS111,k-1））を、加算器１１４−２に供給する。
【０１６２】
加算器１１４−１は、メモリ１１１−１からのパスメトリックPMS01,k-1と、BMUからのブランチメトリックBM2,kを加算し、その結果得られる加算値（PMS01,k-1＋BM2,k）を比較器１１５とセレクタ１１６に供給する。加算器１１４−２は、セレクタ１１３からの最大値と、BMUからのブランチメトリックBM6,kを加算し、その結果得られる加算値（max（PMS011,k-1,PMS111,k-1）＋BM6,k）を比較器１１５とセレクタ１１６に供給する。
【０１６３】
比較器１１５は、加算器１１４−１と１１４−２から供給される加算値を比較し、２つの加算値のうちの最大値を特定する情報を、比較結果としてセレクタ１１６に供給する。セレクタ１１６は、比較器１１５からの比較結果に基づいて、加算器１１４−１と１１４−２から供給される加算値のうちの最大値（max（max（PMS011,k-1,PMS111,k-1）＋BM6,k,PMS01,k-1＋BM2,k））を、パスメトリックPMS10,kとして選択し、出力する。このパスメトリックPMS01,kは、メモリ１１７にフィードバックされ、記憶される。このパスメトリックPMS10,kは、パスメトリックPMS10,k-1として、式（１）の２行目の式の演算に用いられる。
【０１６４】
以上のように、図１６の回路１１０は、式（１）の３行目の右辺の式max(PMS01,k-1+BM2,k,PMS011,k-1+BM6,k,PMS111,k-1+BM6,k)の順序を入れ替えた式max(max(PMS011,k-1,PMS111,k-1)+BM6,k,PMS01,k-1+BM2,k)を演算している。即ち、回路１１０は、まず最初にパスメトリックPMS011,k-1とPMS111,k-1のうちの最大値を求め、その最大値にBM6,kを加算し、その結果得られる加算値と、パスメトリックPMS01,k-1とブランチメトリックBM2,kの加算値との最大値を求める。
【０１６５】
これにより、図１６の回路１１０は、図７のACSU５０のうちの状態Ｓ10のパスメトリックを更新する、メモリ５１−４乃至５１−６、加算器５２−６、５２−８、および５２−１０、並びにmax回路５３−２からなる回路に比べて、１つの加算器を削減することができる。即ち、max回路５３−２は、入力される３つの値を比較して、最大値を選択する回路であり、図１６の比較器１１２と１１５、並びにセレクタ１１３と１１６により構成される回路と同一の回路である。従って、図１６の回路１１０は、図７の対応する回路から、１つの加算器を削減したものである。
【０１６６】
次に、図１７を参照して、回路１１０が状態Ｓ10のパスメトリックの更新を行う更新処理について説明する。この更新処理は、パスメトリックPMS01,k-1，PMS011,k-1、およびPMS111,k-1が、加算器１１４−１または比較器１１２に供給されたとき、開始される。
【０１６７】
ステップＳ２１において、比較器１１２は、パスメトリックPMS011,k-1とPMS111,k-1とを比較し、パスメトリックPMS011,k-1とPMS111,k-1のうちの最大値を特定する情報を、比較結果としてセレクタ１１３に供給する。
【０１６８】
ステップＳ２１の処理後は、ステップＳ２２に進み、セレクタ１１３は、比較結果に基づいて、パスメトリックPMS011,k-1とPMS111,k-1のうちの最大値（max（PMS011,k-1,PMS111,k-1））を選択して、加算器１１４−２に出力し、ステップＳ２３に進む。
【０１６９】
ステップＳ２３において、加算器１１４−２は、最大値とブランチメトリックBM6,kを加算し、その結果得られる加算値（max（PMS011,k-1,PMS111,k-1）＋BM6,k）を比較器１１５とセレクタ１１６に供給する。また、加算器１１４−１は、パスメトリックPMS01,k-1とブランチメトリックBM2,kを加算し、その結果得られる加算値（PMS01,k-1＋BM2,k）を比較器１１５とセレクタ１１６に供給する。
【０１７０】
ステップＳ２３の処理後は、ステップＳ２４に進み、比較器１１５は、加算器１１４−１と１１４−２から供給される加算値を比較し、２つの加算値のうちの最大値を特定する情報を、比較結果としてセレクタ１１６に供給する。
【０１７１】
ステップＳ２４の処理後は、ステップＳ２５に進み、セレクタ１１６は、比較器１１５からの比較結果に基づいて、加算器１１４−１と１１４−２から供給される加算値のうちの最大値（max（max（PMS011,k-1,PMS111,k-1）＋BM6,k,PMS01,k-1＋BM2,k））を、パスメトリックPMS10,kとして選択し、そのパスメトリックPMS10,kをメモリ１１７にフィードバックして、処理を終了する。
【０１７２】
以上のように、回路１１０では、図１６の四角形Ａで囲まれるメモリ１１１−２と１１１−３、比較器１１２、およびセレクタ１１３からなる回路が、１回目の２つの値の比較と選択を行い、四角形Ｂで囲まれるメモリ１１１−１、加算器１１４−１と１１４−２、比較器１１５、およびセレクタ１１６が、加算、並びに２回目の２つの値の比較と選択を行う。
【０１７３】
次に、図１８を参照して、図１５のトレリスにしたがって１時刻ごとにチャネル入力ビット系列を復号する、本発明を適用したビタビ復号器のACSUのうちの、状態Ｓ10のパスメトリックPMS10,kを更新する回路１３０の処理について説明する。
【０１７４】
図１８の回路１３０では、図１６の四角形Ａで囲まれたメモリ１１１−２と１１１−３、比較器１１２、並びにセレクタ１１３からなる回路の処理が、四角形Ｂで囲まれたメモリ１１１−１、比較器１１５、およびセレクタ１１６からなる回路の処理の１時刻前に行われる。
【０１７５】
即ち、まず最初に、時刻t-1において、四角形Ａで囲まれたメモリ１１１−２と１１１−３、比較器１１２、並びにセレクタ１１３からなる回路の処理が行われる。具体的には、時刻t-1において、加算器１３２−１に、メモリ１３１−１からパスメトリックPMS01,k-2が入力されるとともに、BMUからブランチメトリックBM3,k-1が入力され、加算器１３２−２に、メモリ１３１−２からパスメトリックPMS011,k-2が入力されるとともに、BMUからブランチメトリックBM7,k-1が入力されると、加算器１３２−１は、パスメトリックPMS01,k-2とBM3,k-2を加算してパスメトリックPMS011,k-1を求め、加算器１３２−２は、パスメトリックPMS011,k-2とブランチメトリックBM7,k-1を加算してパスメトリックPMS111,k-1を求める。
【０１７６】
即ち、加算器１３２−１は、上述した式（１）の５行目の式にしたがってパスメトリックPMS011,k-1を求め、加算器１３２−２は、上述した式（１）の６行目の式にしたがってパスメトリックPMS111,k-1を求める。
【０１７７】
また、加算器１３２−１と１３２−２は、パスメトリック（PMS011,k-1，PMS111,k-1）を比較器１３３に供給するとともに、セレクタ１３４に供給する。比較器１３３は、図１６の比較器１１２と同様に、加算器１３２−１と１３２−２から供給される２つのパスメトリックPMS011,k-1とPMS111,k-1を比較し、その２つのパスメトリックのうちの最大値を特定する情報を、比較結果としてセレクタ１３４に供給する。
【０１７８】
セレクタ１３４は、図１６のセレクタ１１３と同様に、比較器１３３からの比較結果に基づいて、加算器１３２−１と１３２−２から供給されるパスメトリックPMS011,k-1とPMS111,k-1のうちの最大値（max（PMS011,k-1，PMS111,k-1））を、１時刻後の時刻ｔにおいて状態Ｓ10,kのパスメトリックPMS10,kとして選択される可能性のあるパスメトリックPMS*11,k-1として、メモリ１３５に供給して記憶させる。以上の処理を、回路１３０は１時刻で行う。
【０１７９】
以上のようにして、時刻t-1において、回路１３０は、パスメトリックPMS011k-1,kとPMS111,k-1を求めるとともに、図１６の四角形Ａで囲まれた回路の処理、即ち、１回目の比較と選択を行う。
【０１８０】
次に、時刻ｔにおいて、四角形Ｂで囲まれたメモリ１１１−１、比較器１１５、およびセレクタ１１６からなる回路の処理が行われる。具体的には、時刻ｔにおいて、加算器１３６−１には、メモリ１３１−１からパスメトリックPMS01,k-1が入力されるとともに、BMUからブランチメトリックBM2,kが入力され、加算器１３６−１は、パスメトリックPMS01,k-1とブランチメトリックBM2,kを加算し、その結果得られる加算値（PMS01,k-1+BM2,k）を比較器１３７とセレクタ１３８に供給する。
【０１８１】
また、加算器１３６−２には、メモリ１３５からパスメトリックPMS*11,k-1が入力されるとともに、BMUからブランチメトリックBM6,kが入力され、加算器１３６−２は、パスメトリックPMS*11,k-1とブランチメトリックBM6,kを加算し、その結果得られる加算値（max（PMS011,k-1，PMS111,k-1）＋BM6,k）を比較器１３７とセレクタ１３８に供給する。
【０１８２】
比較器１３７は、加算器１３６−１と１３６−２から供給される加算値を比較し、その２つの加算値のうちの最大値を特定する情報を、比較結果としてセレクタ１３８に供給する。セレクタ１３８は、比較器１３７からの比較結果に基づいて、加算器１３６−１と１３６−２から供給される加算値の最大値（max（max（PMS011,k-1，PMS111,k-1）＋BM6,k，PMS01,k-1+BM2,k））を、パスメトリックPMS10,kとして選択し、そのパスメトリックPMS10,kをメモリ１３９にフィードバックする。このパスメトリックPMS10,kは、パスメトリックPMS10,k-1として、式（１）の２行目の式の演算に用いられる。回路１３０は、以上の処理を１時刻で行う。
【０１８３】
以上のように、図１８の回路１３０は、１回目の比較と選択を、１時刻前において行い、その結果をメモリ１３５に記憶させる。これにより、図１８の回路１３０では、時刻k-1におけるパスメトリックPMS01,k-1とPMS*11,k-1が入力される時刻tにおいて、１時刻で行う処理が、加算、および、２回目の比較と選択となり、図１６の回路１１０に比べて、１時刻に行う処理に要する時間を短縮することが可能となる。その結果、復号処理を高速化することができる。
【０１８４】
なお、図１８では、状態Ｓ10のパスメトリックPMS10,kを更新する場合について説明したが、３つのブランチがマージする状態Ｓ01のパスメトリックPMS01,kを更新する場合についても同様の処理が行われる。
【０１８５】
図１９は、図１８に示した処理を行うACSUの構成例を示している。
【０１８６】
ここで、まず最初に、図１９のACSU１６０が演算する各状態Ｓのパスメトリックの更新式について説明する。図１９では、図１８で上述したように、３つのブランチがマージする状態Ｓ10とＳ01のパスメトリックPMS10,kとPMS01,kの更新において、１時刻前に１回目の比較および選択を行い、その結果をメモリに記憶させるので、更新式は、以下の式（９）で表される。
【０１８７】
PMS*00,k=max(PMS100,k-1+BM0,k,PMS10,k-1+ BM4,k)
PMS100,k=PMS10,k-1+BM4,k
PMS10,k=max(PMS01,k-1+ BM2,k,PMS*11,k-1+BM6,k)
PMS01,k=max(PMS10,k-1+ BM5,k,PMS*00,k-1+ BM1,k)
PMS011,k=PMS01,k-1+BM3,k
PMS*11,k=max(PMS011,k-1+ BM7,k,PMS01,k-1+BM3,k)
・・・（９）
【０１８８】
なお、式（９）において、PMS*00,kは、時刻kのパスメトリックPMS000,kとPMS100,kのうちの最大値であり、１時刻後に状態Ｓ01のパスメトリックPMS01,k+1として選択される可能性のあるパスメトリックである。
【０１８９】
式（９）によれば、パスメトリックPMS,kの更新において、１時刻に３つ以上の加算値から最大値を選択する必要がない。即ち、式（９）によれば、同一の状態Ｓにマージされるブランチの最大の数が２のトレリスの場合と同様に、１時刻に２つの加算値から最大値を選択することにより、パスメトリックPMS,kを更新することができる。従って、１時刻に行う処理に要する時間が短縮され、これにより、復号処理を高速化することができる。
【０１９０】
次に、式（９）の更新式を演算するACSU１６０の構成について説明する。
【０１９１】
ACSU１６０は、メモリ１６１−１乃至１６１−６、加算器１６２−１乃至１６２−８、max回路１６３−１乃至１６３−４により構成される。
【０１９２】
なお、ACSU１６０のメモリ１６１−４，１６１−５，１６１−６は、図１８のメモリ１３１−１，１３１−２，１３５，１３９に対応しており、加算器１６２−６，１６２−７，１６２−５，１６２−８は、図１８の加算器１３２−１，１３２−２，１３６−１，１３６−２に対応している。また、ACSU１６０のmax回路１６３−３，max回路１６３−４は、図１８の比較器１３３とセレクタ１３４、比較器１３７とセレクタ１３８にそれぞれ対応している。
【０１９３】
メモリ１６１−１は、max回路１６３−２から供給されるパスメトリックPMS*00,k-1を記憶する。メモリ１６１−１は、既に記憶しているパスメトリックPMS*00,k-1を加算器１６２−１に供給する。メモリ１６１−２は、加算器１６２−３から供給されるパスメトリックPMS100,k-1を記憶する。メモリ１６１−２は、既に記憶しているパスメトリックPMS100,k-1を加算器１６２−２に供給する。
【０１９４】
また、メモリ１６１−３は、max回路１６３−４から供給されるパスメトリックPMS10,k-1を記憶する。メモリ１６１−３は、既に記憶しているパスメトリックPMS10,k-1を加算器１６２−３と１６２−４に供給する。メモリ１６１−４は、max回路１６３−１から供給されるパスメトリックPMS01,k-1を記憶する。メモリ１６１−４は、既に記憶しているパスメトリックPMS01,k-1を加算器１６２−５と１６２−６に供給する。
【０１９５】
さらに、メモリ１６１−５は、加算器１６２−６から供給されるパスメトリックPMS011,k-1を記憶する。メモリ１６１−５は、既に記憶しているパスメトリックPMS011,k-1を加算器１６２−７に供給する。メモリ１６１−６は、max回路１６３−３から供給されるパスメトリックPMS*11,k-1を記憶する。メモリ１６１−６は、既に記憶しているパスメトリックPMS*11,k-1を加算器１６２−８に供給する。
【０１９６】
加算器１６２−１は、メモリ１６１−１から供給されるパスメトリックPMS*00,k-1と、BMUから入力されるブランチメトリックBM1,kとを加算し、その結果得られる加算値（PMS*00,k-1＋BM1,k）をmax回路１６３−１に供給する。加算器１６２−２は、メモリ１６１−２から供給されるパスメトリックPMS100,k-1と、BMUから入力されるブランチメトリックBM0,kとを加算し、その結果得られる加算値（PMS100,k-1＋BM0,k）をmax回路１６３−２に供給する。
【０１９７】
また、加算器１６２−３は、メモリ１６１−３から供給されるパスメトリックPMS10,k-1と、BMUから入力されるブランチメトリックBM4,kとを加算して、パスメトリックPMS100,kを求める。即ち、加算器１６２−３は、式（９）の２行目の式を演算する。加算器１６２−３は、パスメトリックPMS100,kをパスメトリックPMS100,k-1として、メモリ１６１−２にフィードバックするとともに、パスメトリックPMS100,kである加算値（PMS10,k-1＋BM4,k）をmax回路１６３−２に供給する。
【０１９８】
さらに、加算器１６２−４は、メモリ１６１−３から供給されるパスメトリックPMS10,k-1と、BMUから入力されるブランチメトリックBM5,kとを加算し、その結果得られる加算値（PMS10,k-1＋BM5,k）をmax回路１６３−１に供給する。加算器１６２−５は、メモリ１６１−４から供給されるパスメトリックPMS01,k-1と、BMUから入力されるブランチメトリックBM2,kとを加算し、その結果得られる加算値（PMS01,k-1＋BM2,k）をmax回路１６３−４に供給する。
【０１９９】
また、加算器１６２−６は、メモリ１６１−４から供給されるパスメトリックPMS01,k-1と、BMUから入力されるブランチメトリックBM3,kとを加算し、パスメトリックPMS011,kを求める。即ち、加算器１６２−６は、式（９）の５行目の式を演算する。加算器１６２−６は、パスメトリックPMS011,kをパスメトリックPMS011,k-1として、メモリ１６１−５にフィードバックするとともに、パスメトリックPMS011,kである加算値（PMS01,k-1＋BM3,k）をmax回路１６３−３に供給する。
【０２００】
さらに、加算器１６２−７は、メモリ１６１−５から供給されるパスメトリックPMS011,k-1と、BMUから入力されるブランチメトリックBM7,kとを加算し、その結果得られる加算値（PMS011,k-1＋BM7,k）をmax回路１６３−３に供給する。加算器１６２−８は、メモリ１６１−６から供給されるパスメトリックPMS*11,k-1と、BMUから入力されるブランチメトリックBM6,kとを加算し、その結果得られる加算値（PMS*11,k-1＋BM6,k）をmax回路１６３−４に供給する。
【０２０１】
max回路１６３−１は、加算器１６２−１と加算器１６２−４から供給される２つの加算値を比較し、その２つの加算値のうちの最大値（max（PMS*00,k-1＋BM1,k，PMS10,k-1＋BM5,k））をパスメトリックPMS01,kとして選択する。即ち、max回路１６３−１は、式（９）の４行目の式を演算する。max回路１６３−１は、選択したパスメトリックPMS01,kを、パスメトリックPMS01,k-1として、メモリ１６１−４にフィードバックする。
【０２０２】
また、max回路１６３−２は、加算器１６２−２と１６２−３から供給される２つの加算値を比較し、その２つの加算値のうちの最大値（max（PMS100,k-1＋BM0,k，PMS10,k-1＋BM4,k））をパスメトリックPMS*00,kとして選択する。即ち、max回路１６３−２は、式（９）の１行目の式を演算する。max回路１６３−２は、選択したパスメトリックPMS*00,kを、パスメトリックPMS*00,k-1として、メモリ１６１−１にフィードバックする。
【０２０３】
さらに、max回路１６３−３は、加算器１６２−６と１６２−７から供給される加算値とを比較し、その２つの加算値のうちの最大値（max（PMS01,k-1＋BM3,k，PMS011,k-1＋BM7,k））をパスメトリックPMS*11,kとして選択する。即ち、max回路１６３−３は、式（９）の６行目の式を演算する。max回路１６３−３は、選択したパスメトリックPMS*11,kを、パスメトリックPMS*11,k-1として、メモリ１６１−６にフィードバックする。
【０２０４】
また、max回路１６３−４は、加算器１６２−５と１６２−８から供給される加算値とを比較し、その２つの加算値のうちの最大値（max（PMS01,k-1＋BM2,k，PMS*11,k-1＋BM6,k））をパスメトリックPMS10,kとして選択する。即ち、max回路１６３−４は、式（９）の３行目の式を演算する。max回路１６３−４は、選択したパスメトリックPMS10,kを、パスメトリックPMS10,k-1として、メモリ１６１−３にフィードバックする。
【０２０５】
なお、図１９の回路１６０では、パスメトリックPMS100,kと、パスメトリックPMS*00,kを求める式（９）の１行目の式の選択候補となる加算値（PMS10,k-1＋BM4,k）が同一であるので、メモリ１６１−３と加算器１６２−３は、パスメトリックPMS100,kと加算値（PMS10,k-1＋BM4,k）を求める回路として共用されている。
【０２０６】
また、同様に、パスメトリックPMS011,kと、パスメトリックPMS*11,kを求める式（９）の６行目の式の選択候補となる加算値（PMS01,k-1＋BM3,k）が同一であるので、メモリ１６１−４と加算器１６２−６は、パスメトリックPMS011,kと加算値（PMS01,k-1＋BM3,k）を求める回路として共用されている。
【０２０７】
また、図１９の回路１６０の更新処理は、図１４と同様の処理であり、図示は省略する。即ち、図１９の回路１６０は、１時刻で、加算、２つの加算値の比較、および最大値の選択を行う。
【０２０８】
図２０は、回数dが１に制限され、最小の間隔の極性反転が連続する最大の回数rが２に制限されるRLL符号制約を組み合わせた、チャネルビットメモリ長が４のパーシャルレスポンスのトレリス線図を示している。
【０２０９】
図２０のトレリス線図では、回数d=1の制約条件により、状態Ｓ000110，Ｓ1100110，Ｓ1110からはチャネルビットの入力が１となる遷移が削除され、状態Ｓ111001，Ｓ0011001，Ｓ0001からはチャネルビットの入力が０となる遷移が削除されている。また、回数r=2の制約条件により、状態Ｓ1001100からはチャネルビットの入力が１となる遷移が削除され、状態Ｓ0110011からはチャネルビットの入力が０となる遷移が削除されている。
【０２１０】
また、図２０のトレリス線図では、状態Ｓ11000とＳ00111でマージされるブランチの数が最大の３となっている。
【０２１１】
次に、図２０のトレリスにしたがう復号において行われるパスメトリックの更新について説明する。
【０２１２】
ここで、チャネルメモリ長が４のパーシャルレスポンスでは、チャネルビットの00000から11111までに対応する最大３２通りの出力期待値があり、その出力期待値と時刻k-1から時刻kに遷移する際の再生信号とから演算されるブランチメトリックを、BM0,k乃至BM31,kで表す。
【０２１３】
なお、図２０の例では、回数dが１に制限されているので、出力期待値の種類は最大１６種類である。また、パーシャルレスポンスの伝達関数の係数によっては、異なるチャネルビットに対応する出力期待値が一致する場合があるため、必ずしも１６種類の異なるブランチメトリックを演算する必要はない。
【０２１４】
各状態Ｓのパスメトリックの更新式は、以下の式（１０）で表される。
【０２１５】
PMS0000,k=max(PMS0000,k-1+BM0,k,PMS11000,k-1+BM16,k)
PMS11000,k=  max(PMS0001100,k-1+BM24,k,PMS1001100,k-1+BM24,k,PMS11100,k-1+BM24,k)
PMS0001100,k=PMS000110,k-1+BM12,k
PMS1001100,k=PMS1100110,k-1+BM12,k
PMS11100,k=  PMS1110,k-1+BM28,k
PMS000110,k=PMS00011,k-1+BM6,k
PMS1100110,k=PMS1110011,k-1+BM6,k
PMS1110,k=max(PMS00111,k-1+BM14,k,PMS1111,k-1+BM30,k)
PMS0001,k=max(PMS11000,k-1+BM17,k,PMS0000,k-1+BM1,k)
PMS0011001,k=PMS0001100,k-1+BM25,k
PMS111001,k=PMS11100,k-1+BM25,k
PMS00011,k=  PMS0001,k-1+BM3,k
PMS0110011,k=PMS0011001,k-1+BM19,k
PMS1110011,k=PMS111001,k-1+BM19,k
PMS00111,k=  max(PMS1110011,k-1+BM7,k,PMS0110011,k-1+BM7,k,PMS00011,k-1+BM7,k)
PMS1111,k=max(PMS1111,k-1+BM31,k,PMS00111,k-1+BM15,k)
・・・（１０）
【０２１６】
式（１０）によれば、３つのブランチがマージする状態Ｓ11000とＳ00111のパスメトリックPMS11000とPMS00111の更新において、３つの加算値から最大値を選択する必要がある。
【０２１７】
これに対して、図２０に示したトレリスにしたがってチャネル入力ビット系列を復号するビタビ復号器においても、本発明を適用することにより、３つの加算値から最大値を選択する必要がなくなる。
【０２１８】
即ち、本発明を適用したビタビ復号器のACSUは、２つのパスメトリックPMS0001100,k-1とPMS1001100,k-1からの最大値の選択、パスメトリックPMS1110011,k-1とPMS0110011,k-1からの最大値の選択を、それぞれ１時刻前に行い、選択された最大値を、それぞれパスメトリックPMS*001100,k-1、PMS*110011,k-1として、メモリに記憶する。即ち、本発明を適用したビタビ復号器のACSUは、以下の式（１１）で表される式を更新式として、パスメトリックの更新を行う。
【０２１９】
PMS0000,k=max(PMS0000,k-1+BM0,k,PMS11000,k-1+BM16,k)
PMS11000,k=max(PMS*001100,k-1,PMS11100,k-1)+BM24,k
PMS0001100,k=PMS000110,k-1+BM12,k
PMS*001100,k=max(PMS000110,k-1,PMS1100110,k-1)+BM12,k
PMS11100,k=  PMS1110,k-1+BM28,k
PMS000110,k=PMS00011,k-1+BM6,k
PMS1100110,k=PMS1110011,k-1+BM6,k
PMS1110,k=max(PMS00111,k-1+BM14,k,PMS1111,k-1+BM30,k)
PMS0001,k=max(PMS11000,k-1+BM17,k,PMS0000,k-1+BM1,k)
PMS0011001,k=PMS0001100,k-1+BM25,k
PMS111001,k=PMS11100,k-1+BM25,k
PMS00011,k=PMS0001,k-1+BM3,k
PMS*110011,k=max(PMS111001,k-1,PMS0011001,k-1)+BM19,k
PMS1110011,k=PMS111001,k-1+BM19,k
PMS00111,k=  max(PMS*110011,k-1,PMS00011,k-1)+BM7,k
PMS1111,k=    max(PMS1111,k-1+BM31,k,PMS00111,k-1+BM15,k)
・・・（１１）
【０２２０】
式（１１）によれば、パスメトリックPMS,kの更新において、１時刻に３つ以上の加算値から最大値を選択する必要がない。即ち、式（１１）によれば、同一の状態Ｓにマージされるブランチの最大の数が２のトレリスの場合と同様に、１時刻に２つの加算値から最大値を選択することにより、パスメトリックPMS,kを更新することができる。従って、１時刻に行う処理に要する時間が短縮され、これにより、復号処理を高速化することができる。
【０２２１】
なお、式（１１）においては、パスメトリックPMS0001100,kとPMS1001100,kからの最大値の選択と、パスメトリックPMS1110011,kとPMS0110011,kからの最大値の選択を１時刻前に行うことにしたが、１時刻前に行う２つの最大値の選択は、パスメトリックPMS0001100,k-1,PMS1001100,k-1、およびPMS11100,k-1のうちのいずれか２つからの最大値の選択と、PMS1110011,k-1,PMS0110011,k-1、およびPMS00011,k-1のうちのいずれか２つからの最大値の選択であればよい。
【０２２２】
また、式（１１）において、パスメトリックPMS11000,k,PMS*001100,k,PMS*110011,k、およびPMS00111,kの更新式における、加算と選択は可換である。従って、パスメトリックPMS*001100,kとPMS*110011,kの更新式において選択よりも加算を先に行う場合、ACSUでは、パスメトリックPMS*001100,kの更新式で選択候補となる加算値（PMS000110,k-1+BM12,k）を求める回路を、パスメトリックPMS0001100,kを更新する回路として共用し、パスメトリックPMS*110011,kの更新式で選択候補となる加算値（PMS111001,k-1+BM19,k）を求める回路を、パスメトリックPMS1110011,kを更新する回路として共用することができる。
【０２２３】
図２１は、チャネルビットの極性反転の連続する最大の回数を４回に制限するMTR符号制約を組み合わせた、チャネルビットメモリ長が４のパーシャルレスポンスのトレリス線図を示している。
【０２２４】
図２１のトレリス線図では、MTR符号の制約条件により、状態Ｓ01010からはチャネルビットの入力が１となる遷移が削除され、状態Ｓ10101からはチャネルビットの入力が０となる遷移が削除されている。また、図２１のトレリス線図では、状態Ｓ0100とＳ1011でマージされるブランチの数が最大の３となっている。
【０２２５】
次に、図２１のトレリスにしたがう復号において行われるパスメトリックの更新について説明する。各状態Ｓのパスメトリックの更新式は、以下の式（１２）で表される。
【０２２６】
PMS0000,k=max(PMS0000,k-1+BM0,k,PMS1000,k-1+BM16,k)
PMS1000,k=    max(PMS0100,k-1+BM8,k,PMS1100,k-1+BM24,k)
PMS0100,k=    max(PMS0010,k-1+BM4,k,PMS01010,k-1+BM20,k,PMS11010,k-1+BM20,k)
PMS1100,k=    max(PMS0110,k-1+BM12,k,PMS1110,k-1+BM28,k)
PMS0010,k=    max(PMS0001,k-1+BM2,k,PMS1001,k-1+BM18,k)
PMS01010,k=  PMS00101,k-1+BM10,k
PMS11010,k=  PMS1101,k-1+BM26,k
PMS0110,k=    max(PMS0011,k-1+BM6,k,PMS1011,k-1+BM22,k)
PMS1110,k=    max(PMS0111,k-1+BM14,k,PMS1111,k-1+BM30,k)
PMS0001,k=    max(PMS1000,k-1+BM17,k,PMS0000,k-1+BM1,k)
PMS1001,k=    max(PMS1100,k-1+BM25,k,PMS0100,k-1+BM9,k)
PMS00101,k=  PMS0010,k-1+BM5,k
PMS10101,k=  PMS11010,k-1+BM21,k
PMS1101,k=    max(PMS1110,k-1+BM29,k,PMS0110,k-1+BM13,k)
PMS0011,k=    max(PMS1001,k-1+BM19,k,PMS0001,k-1+BM3,k)
PMS1011,k=    max(PMS1101,k-1+BM27,k,PMS10101,k-1+BM11,k,PMS00101,k-1+BM11,k)
PMS0111,k=    max(PMS1011,k-1+BM23,k,PMS0011,k-1+BM7,k)
PMS1111,k=    max(PMS1111,k-1+BM31,k,PMS0111,k-1+BM15,k)
・・・（１２）
【０２２７】
式（１２）によれば、３つのブランチがマージする状態Ｓ0100とＳ1011のパスメトリックPMS0100とPMS1011の更新において、３つの加算値から最大値を選択する必要がある。
【０２２８】
これに対し、図２１に示したトレリスにしたがってチャネル入力ビット系列を復号するビタビ復号器においても、本発明を適用することにより、３つの加算値から最大値を選択する必要がなくなる。
【０２２９】
即ち、本発明を適用したビタビ復号器のACSUは、２つのパスメトリックPMS01010,k-1とPMS11010,k-1からの最大値の選択、パスメトリックPMS10101,k-1とPMS00101,k-1からの最大値の選択を、それぞれ１時刻前に行い、選択された最大値を、それぞれパスメトリックPMS*1010,k-1、PMS*0101,k-1として、メモリに記憶する。即ち、本発明を適用したビタビ復号器のACSUは、以下の式（１３）で表される式を更新式として、パスメトリックの更新を行う。
【０２３０】
PMS0000,k=max(PMS0000,k-1+BM0,k,PMS1000,k-1+BM16,k)
PMS1000,k=max(PMS0100,k-1+BM8,k,PMS1100,k-1+BM24,k)
PMS0100,k=max(PMS0010,k-1+BM4,k,PMS*1010,k-1+BM20,k)
PMS1100,k=max(PMS0110,k-1+BM12,k,PMS1110,k-1+BM28,k)
PMS0010,k=max(PMS0001,k-1+BM2,k,PMS1001,k-1+BM18,k)
PMS*1010,k=max(PMS00101,k-1+BM10,k,PMS1101,k-1+BM26,k)
PMS11010,k=PMS1101,k-1+BM26,k
PMS0110,k=max(PMS0011,k-1+BM6,k,PMS1011,k-1+BM22,k)
PMS1110,k=max(PMS0111,k-1+BM14,k,PMS1111,k-1+BM30,k)
PMS0001,k=max(PMS1000,k-1+BM17,k,PMS0000,k-1+BM1,k)
PMS1001,k=max(PMS1100,k-1+BM25,k,PMS0100,k-1+BM9,k)
PMS00101,k=  PMS0010,k-1+BM5,k
PMS*0101,k=max(PMS11010,k-1+BM21,k,PMS0010,k-1+BM5,k)
PMS1101,k=max(PMS1110,k-1+BM29,k,PMS0110,k-1+BM13,k)
PMS0011,k=max(PMS1001,k-1+BM19,k,PMS0001,k-1+BM3,k)
PMS1011,k=max(PMS1101,k-1+BM27,k,PMS*0101,k-1+BM11,k)
PMS0111,k=max(PMS1011,k-1+BM23,k,PMS0011,k-1+BM7,k)
PMS1111,k=max(PMS1111,k-1+BM31,k,PMS0111,k-1+BM15,k)
・・・（１３）
【０２３１】
式（１３）によれば、パスメトリックPMS,kの更新において、１時刻に３つ以上の加算値から最大値を選択する必要がない。即ち、式（１３）によれば、同一の状態Ｓにマージされるブランチの最大の数が２のトレリスの場合と同様に、１時刻に２つの加算値から最大値を選択することにより、パスメトリックPMS,kを更新することができる。従って、１時刻に行う処理に要する時間が短縮され、これにより、復号処理を高速化することができる。
【０２３２】
なお、式（１３）において、パスメトリックPMS11010,kを求める演算と、パスメトリックPMS*1010,kの更新式で選択候補となる加算値（PMS1101,k-1+BM26,k）の演算は共通しているので、ACSUでは、パスメトリックPMS11010,kを求める回路を、加算値（PMS1101,k-1+BM26,k）を求める回路として共用することができる。
【０２３３】
また、パスメトリックPMS00101,kを求める演算と、パスメトリックPMS*0101,kの更新式で選択候補となる加算値（PMS0010,k-1+BM5,k）の演算は共通しているので、ACSUでは、パスメトリックPMS00101,kを求める回路を、加算値（PMS0010,k-1+BM5,k）を求める回路として共用することができる。
【０２３４】
図２２は、図１５のトレリスにしたがって、２時刻ごとにチャネル入力ビット系列を復号する本発明を適用したビタビ復号器のACSUの構成例を示している。
【０２３５】
ここで、まず最初に、図２２のACSU１８０が演算する各状態Ｓのパスメトリックの更新式について説明する。各状態Ｓのパスメトリックの２時刻ごとの更新は、以下の式（１４）で表される。
【０２３６】
PMS*00,k=max(PMS10,k-2+BM4,k-1+BM0,k,PMS01,k-2+BM2,k-1+BM4,k,PMS*11,k-2+BM6,k-1+BM4,k)
PMS100,k=max(PMS01,k-2+BM2,k-1+BM4,k,PMS*11,k-2+BM6,k-1+BM4,k)
PMS10,k=max(PMS10,k-2+BM5,k-1+BM2,k,PMS*00,k-2+BM1,k-1+BM2,k,PMS011,k-2+BM7,k-1+BM6,k,PMS01,k-2+BM3,k-1+BM6,k)
PMS01,k=max(PMS01,k-2+BM2,k-1+BM5,k,PMS*11,k-2+BM6,k-1+BM5,k,PMS100,k-2+BM0,k-1+BM1,k,PMS10,k-2+BM4,k-1+BM1,k)
PMS011,k=max(PMS10,k-2+BM5,k-1+BM3,k,PMS*00,k-2+BM1,k-1+BM3,k)
PMS*11,k=max(PMS01,k-2+BM3,k-1+BM7,k,PMS10,k-2+BM5,k-1+BM3,k,PMS*00,k-2+BM1,k-1+BM3,k)
・・・（１４）
【０２３７】
式（１４）によれば、パスメトリックPMS,kの更新において、２時刻に５つ以上の加算値のうちの最大値を選択する必要がない。即ち、式（１４）によれば、同一の状態Ｓにマージされるブランチの最大の数が２のトレリスの場合と同様に、２時刻に４つの加算値から最大値を選択することにより、パスメトリックPMS,kを更新することができる。従って、５つの加算値から最大値を選択する必要がある図８のACSU６０に比べて、２時刻に行う処理に要する時間が短縮され、これにより、復号処理を高速化することができる。
【０２３８】
次に、式（１４）の更新式を演算するACSU１８０の構成について説明する。
【０２３９】
図２２のACSU１８０は、メモリ１８１−１乃至１８１−６、加算器１８２−１乃至１８２−１４、およびmax回路１８３−１乃至１８３−６により構成される。
【０２４０】
図２２のACSU１８０では、図１９のACSU１６０と同様に、加算器１８２−１乃至１８２−１４がパスメトリックPMS,kとブランチメトリックBMを加算し、max回路１８３−１乃至１８３−６が最大値を選択して、メモリ１８１−１乃至１８１−６にフィードバックする。
【０２４１】
具体的には、式（１４）の１と２行目の式は、加算器１８２−４，１８２−８、および１８２−１３、並びにmax回路１８３−１により演算され、その結果得られるパスメトリックPMS*00,kは、パスメトリックPMS*00,k-2としてメモリ１８１−１に記憶される。式（１４）の３行目の式は、加算器１８２−８と１８２−１３、並びにmax回路１８２−２により演算され、その結果得られるパスメトリックPMS100,kは、パスメトリックPMS100,k-2としてメモリ１８１−２に記憶される。
【０２４２】
式（１４）の４と５行目の式は、加算器１８２−１，１８２−５，１８２−９、および１８２−１２、並びにmax回路１８３−３により演算され、その結果得られるパスメトリックPMS10,kは、パスメトリックPMS10,k-2としてメモリ１８１−３に記憶される。また、式（１４）の６と７行目の式は、加算器１８２−３，１８２−６，１８２−１０、および１８２−１４、並びにmax回路１８３−４により演算され、その結果得られるパスメトリックPMS01,k-2は、パスメトリックPMS01,kとしてメモリ１８１−４に記憶される。
【０２４３】
式（１４）の８行目の式は、加算器１８２−２と１８２−７、並びにmax回路１８３−５により演算され、その結果得られるパスメトリックPMS011,kは、パスメトリックPMS011,k-2としてメモリ１８１−５に記憶される。式（１４）の９と１０行目の式は、加算器１８２−２，１８２−７、および１８２−１１、並びにmax回路１８３−６により演算され、その結果得られるパスメトリックPMS*11,kは、パスメトリックPMS*11,k-2としてメモリ１８１−６に記憶される。
【０２４４】
図２３は、図１５のトレリスにしたがって、BCJRアルゴリズムで１時刻ごとにチャネル入力ビット系列を復号する本発明を適用した復号器の、各状態Ｓの確率を更新する回路１９０の構成例を示している。
【０２４５】
図２３の回路１９０は、メモリ１９１−１乃至１９１−６、乗算器１９２−１乃至１９２−８、およびsum１９３−１乃至１９３−４により構成される。
【０２４６】
即ち、上述したように、BCJRアルゴリズムにおける確率αS,kの更新は、ビタビアルゴリズムにおけるパスメトリックPMS,kの更新において、パスメトリックPMS,kを確率αS,kに、ブランチメトリックBMを遷移確率γに、最大値の選択の演算を加算の演算に、パスメトリックPMS,kとブランチメトリックBMの加算を確率αS,kと遷移確率γの乗算に、それぞれ置換することにより得られるので、図２３のACSU１９０では、図１９のメモリ１６１−１乃至１６１−６が図２３のメモリ１９１−１乃至１９１−６に、加算器１６２−１乃至１６２−８が乗算器１９２−１乃至１９２−８に、max回路１６３−１乃至１６３−４がsum１９３−１乃至１９３−４に置換されている。
【０２４７】
その結果、図１９の場合と同様に、確率αS,kの更新において、１時刻に３つ以上の乗算値を加算する必要がない。即ち、同一の状態Ｓにマージされるブランチの最大の数が２のトレリスの場合と同様に、１時刻に２つの乗算値を加算することにより、確率αS,kを更新することができる。従って、１時刻に行う処理に要する時間が短縮され、これにより、復号処理を高速化することができる。
【０２４８】
図２４は、図１５のトレリスにしたがって、Log-MAPアルゴリズムで１時刻ごとにチャネル入力ビット系列を復号する本発明を適用した復号器の、各状態Ｓの尤度を更新する回路２００の構成例を示している。
【０２４９】
図２４の回路２００は、メモリ２０１−１乃至２０１−６、加算器２０２−１乃至２０２−８、およびlog-sum２０３−１乃至２０３−４により構成される。
【０２５０】
即ち、上述したように、Log-MAPアルゴリズムにおける尤度αS,kの更新は、ビタビアルゴリズムにおけるパスメトリックPMS,kの更新において、パスメトリックPMS,kを尤度αS,kに、ブランチメトリックBMを尤度γに、最大値の選択の演算をLog-Sum演算に、パスメトリックPMS,kとブランチメトリックBMの加算を尤度αS,kと尤度γの加算に、それぞれ置換することにより得られるので、図２４のACSU２００では、図１９のメモリ１６１−１乃至１６１−６が図２４のメモリ２０１−１乃至２０１−６に、加算器１６２−１乃至１６２−８が加算器２０２−１乃至２０２−８に、max回路１６３−１乃至１６３−４がlog-sum２０３−１乃至２０３−４に置換されている。
【０２５１】
その結果、図１９の場合と同様に、尤度αS,kの更新において、１時刻に３つ以上の加算値のlog-sum演算を行う必要がない。即ち、同一の状態Ｓにマージされるブランチの最大の数が２のトレリスの場合と同様に、１時刻に２つの加算値のlog-sum演算を行うことにより、尤度αS,kを更新することができる。従って、１時刻に行う処理に要する時間が短縮され、これにより、復号処理を高速化することができる。
【０２５２】
図２５は、図１５のトレリスにしたがって、Max-Log-MAPアルゴリズムで１時刻ごとにチャネル入力ビット系列を復号する本発明を適用した復号器の、各状態Ｓの尤度を更新する回路２１０の構成例を示している。
【０２５３】
回路２１０は、メモリ２１１−１乃至２１１−６、加算器２１２−１乃至２１２−８、およびmax回路２１３−１乃至２１３−４により構成される。
【０２５４】
即ち、上述したように、Max-Log-MAPアルゴリズムにおける尤度αS,kの更新は、ビタビアルゴリズムにおけるパスメトリックPMS,kの更新において、パスメトリックPMS,kを尤度αS,kに、ブランチメトリックBMを尤度γに、パスメトリックPMS,kとブランチメトリックBMの加算を尤度αS,kと尤度γの加算に、それぞれ置換することにより得られるので、図２５のACSU２１０では、図１９のメモリ１６１−１乃至１６１−６が図２３のメモリ２１１−１乃至２１１−６に、加算器１６２−１乃至１６２−８が加算器２１２−１乃至２１２−８に、max回路１６３−１乃至１６３−４がmax回路２１３−１乃至２１３−４に置換されている。
【０２５５】
その結果、図１９の場合と同様に、尤度αS,kの更新において、１時刻に３つ以上の加算値を加算する必要がない。即ち、同一の状態Ｓにマージされるブランチの最大の数が２のトレリスの場合と同様に、１時刻に２つの加算値から最大値を選択することにより、尤度αS,kを更新することができる。従って、１時刻に行う処理に要する時間が短縮され、これにより、復号処理を高速化することができる。
【０２５６】
なお、本明細書において、プログラム記録媒体に格納されるプログラムを記述するステップは、記載された順序に沿って時系列的に行われる処理はもちろん、必ずしも時系列的に処理されなくとも、並列的あるいは個別に実行される処理をも含むものである。
【０２５７】
また、本発明の実施の形態は、上述した実施の形態に限定されるものではなく、本発明の要旨を逸脱しない範囲において種々の変更が可能である。
【図面の簡単な説明】
【０２５８】
【図１】PR4の状態遷移図である。
【図２】チャネルメモリ長が２である場合のトレリス線図である
【図３】ビタビ復号器の構成を示すブロック図である。
【図４】状態ｓ１のパスメトリックを更新する回路の構成の一例を示す図である。
【図５】他のトレリス線図である。
【図６】さらに他のトレリス線図である。
【図７】従来のビタビ復号器のACSUの構成の一例を示す図である。
【図８】従来のビタビ復号器のACSUの他の構成の一例を示す図である。
【図９】BCJRアルゴリズムで復号を行う従来の復号器の回路の構成の一例を示す図である。
【図１０】Log-MAPアルゴリズムで復号を行う従来の復号器の回路の構成の一例を示す図である。
【図１１】Max-Log-MAPアルゴリズムで復号を行う従来の復号器の回路の構成例を示す図である。
【図１２】さらに他のトレリス線図である。
【図１３】本発明を適用した一実施の形態のビタビ復号器のACSUの構成例を示す図である。
【図１４】更新処理について説明するフローチャートである。
【図１５】さらに他のトレリス線図である。
【図１６】ビタビ復号器のACSUの回路の構成例を示す図である。
【図１７】他の更新処理について説明するフローチャートである。
【図１８】本発明を適用したビタビ復号器のACSUの回路の処理について説明する図である。
【図１９】ビタビ復号器のACSUの他の構成例を示す図である。
【図２０】さらに他のトレリス線図を示している。
【図２１】さらに他のトレリス線図を示している。
【図２２】本発明を適用したビタビ復号器のACSUの他の構成例を示す図である。
【図２３】BCJRアルゴリズムで復号する本発明を適用した復号器の回路の構成例を示す図である。
【図２４】Log-MAPアルゴリズムで復号する本発明を適用した復号器の回路の構成例を示す図である。
【図２５】Max-Log-MAPアルゴリズムで復号する本発明を適用した復号器の回路の構成例を示す図である。
【符号の説明】
【０２５９】
１３３  比較器，  １３４  セレクタ，  １３６−１，１３６−２  加算器，  １３７  比較器，  １３８  セレクタ
【図１】
2008034008.tif 000003
【図２】
2008034008.tif 000004
【図３】
2008034008.tif 000005
【図４】
2008034008.tif 000006
【図５】
2008034008.tif 000007
【図６】
2008034008.tif 000008
【図７】
2008034008.tif 000009
【図８】
2008034008.tif 000010
【図９】
2008034008.tif 000011
【図１０】
2008034008.tif 000012
【図１１】
2008034008.tif 000013
【図１２】
2008034008.tif 000014
【図１３】
2008034008.tif 000015
【図１４】
2008034008.tif 000016
【図１５】
2008034008.tif 000017
【図１６】
2008034008.tif 000018
【図１７】
2008034008.tif 000019
【図１８】
2008034008.tif 000020
【図１９】
2008034008.tif 000021
【図２０】
2008034008.tif 000022
【図２１】
2008034008.tif 000023
【図２２】
2008034008.tif 000024
【図２３】
2008034008.tif 000025
【図２４】
2008034008.tif 000026
【図２５】
2008034008.tif 000027