JPH0884082A

JPH0884082A - ビタビ復号方法及びビタビ復号装置

Info

Publication number: JPH0884082A
Application number: JP21987394A
Authority: JP
Inventors: Hiroyuki Ino; 浩幸井野; Toshihiko Hirose; 俊彦廣瀬
Original assignee: Sony Corp
Current assignee: Sony Corp
Priority date: 1994-09-14
Filing date: 1994-09-14
Publication date: 1996-03-26
Anticipated expiration: 2017-07-22
Also published as: JP3304631B2

Abstract

(57)【要約】【目的】本発明は、従来の装置に比して、より高速動
作が可能なビタビ復号方法及びビタビ復号装置を提供す
る。【構成】ブランチメトリック計算部１０は、Ｎ標本点
離れた始点と終点間における隣接した標本点のＭ個の状
態とＭ個の状態をそれぞれ連結するブランチのブランチ
メトリックを算出する。ＡＣＳ回路２０は、ブランチメ
トリックを加算して、部分パスのメトリックを求め、メ
トリックが最も高い部分パスを検出する。ＡＣＳ回路４
０は、部分パスのメトリックと、パスメモリ６０からの
ステートメトリックとを加算して、パスのステートメト
リックを求め、ステートメトリックが最も高いパスを検
出する。ステートメトリック記憶部５０は、ステートメ
トリックを記憶した後、Ｎ標本点後にＡＣＳ回路４０に
供給する。パスメモリ６０は、検出された部分パス、パ
スの情報に基づいて復号データを出力する。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、ビタビ復号方法及びビ
タビ復号装置に関する。

【０００２】

【従来の技術】所謂パーシャルレスポンスや畳み込み符
号に対する最尤復号方式（Maximum Likehod Decoding）
として、ビタビ復号（Viterbi decoding）が知られてい
る。ビタビ復号は、伝送路等で生じるランダムエラーに
対するエラー訂正能力が高く、データの記録再生系では
パーシャルレスポンスと組み合わせられて、例えば磁気
ディスク装置等に用いられる。一方、データ通信系で
は、ビタビ復号化は、畳み込み符号の復号化方法とし
て、例えば衛星通信等への実用化が進められている。

【０００３】ここで、制御可能な符号間干渉を許容し、
伝送効率を高めたパーシャルレスポンスとビタビ復号を
組み合わせた一般的なデータの記録再生装置について説
明する。

【０００４】図４に示すように、変調器１０１は、例え
ば８−１０変換等の記録媒体１０４へのデータの記録に
適した変調を行う変調器であり、端子１７１を介し、情
報系列として入力されるデータ（以下、単に情報系列と
いう。）を変調系列ｘ_t（ｔ＝０、１、２・・・）に変
換する。

【０００５】プリコーダ１０２は、パーシャルレスポン
スにおけるプリコーダであり、変調系列ｘ_tを所定の符
号則に基づいて符号化して、中間系列ｙ_tを生成する。
そして、プリコーダ１０２は、この中間系列ｙ_tを、記
録ヘッド等からなる記録アンプ１０３を介して記録媒体
１０４に記録する。かくして、端子１７１を介して入力
されたデータ（情報系列）が記録媒体１０４に記録され
る。

【０００６】再生ヘッド等からなる再生アンプ１０５
は、記録媒体１０４から再生信号を検出し、等化器１０
６は、再生信号の波形等化を行い、伝送路出力Ｚを出力
する。

【０００７】フェイズロックドループ（以下、ＰＬＬ：
Phase Locked Loop という。）１０７は、記録媒体１０
４等からなる伝送路の出力Ｚからクロック成分を抽出
し、すなわち再生信号に同期したクロックを生成する。

【０００８】標本化回路１０８は、ＰＬＬ１０７からの
クロックにより、伝送路出力Ｚをサンプリングしてデー
タに変換し、得られる標本系列ｚ_tをビタビ復号器１０
９に供給する。ビタビ復号器１０９は、この標本系列ｚ
_tに対してビタビ復号を施し、記録系の変調器１０１の
出力に相当する変調系列ｘ_tを再生する。

【０００９】復調器１１０は、記録系の変調器１０１に
対応したものであり、変調系列ｘ_tを復号化して、元の
情報系列を再生し、この情報系列を復調系列とし、端子
１７２を介して出力する。かくして、記録媒体１０４か
らデータが再生される。

【００１０】つぎに、パーシャルレスポンスを所謂パー
シャルレスポンス（１，１）（以下、ＰＲ（１，１）と
いう。）としたときの伝送システムについて説明する。

【００１１】ＰＲ（１，１）を適用した伝送システム
は、図５に示す等価回路で表すことができる。

【００１２】具体的には、この伝送システムは、その送
信系として、ＰＲ（１，１）に対するプリコーダを備
え、このプリコーダは、排他的論理和回路（以下、ＥＸ
ＯＲ回路という。）１２１と、該ＥＸＯＲ回路１２１の
出力である中間系列ｙ_tを遅延してＥＸＯＲ回路１２１
に供給する遅延器１２２とから構成される。

【００１３】そして、ＥＸＯＲ回路１２１は、端子１７
３を介して、例えば上述の図４に示す変調器１０１から
供給される変調系列ｘ_tと、遅延器１２２で１サンプリ
ング時間遅延された中間系列ｙ_tとの排他的論理和を求
める。すなわち、ＥＸＯＲ回路１２１と遅延器１２２か
ら構成されるプリコーダは、法２の加算器（Mod2加算
器）として機能し、変調系列ｘ_tを法２の加算すること
により、中間系列ｙ_tを生成し、この中間系列ｙ_tを伝
送路に出力する。

【００１４】ＰＲ（１，１）に対する伝送路は、中間系
列ｙ_tを遅延する遅延器１２３と、中間系列ｙ_tと遅延
器１２３で遅延された中間系列ｙ_tを加算する加算器１
２４とから構成される回路と等価であり、遅延器１２３
は、ＥＸＯＲ回路１２１からの中間系列ｙ_tを１サンプ
リング時間遅延し、加算器１２４は、中間系列ｙ_tと遅
延された中間系列ｙ_tを加算して、伝送路出力Ｚを出力
する。

【００１５】したがって、ＥＸＯＲ回路１２１乃至加算
器１２４から構成される回路（以下、ＰＲ（１，１）回
路という。）の動作は、図６に示す状態遷移図で表すこ
とができる。

【００１６】すなわち、端子１７３を介して供給される
変調系列ｘ_tの値を０又は１とし、伝送路出力Ｚの値を
＋Ａ、０又は−Ａとし、中間系列ｙ_tの値（以下、状態
という。）をＳ０又はＳ１とすると、このＰＲ（１，
１）回路は、中間系列ｙ_tが状態Ｓ０のときに変調系列
ｘ_tとして０が入力されると、伝送路出力Ｚをサンプリ
ングして得られる標本系列ｚ_tとして−Ａを出力し、中
間系列ｙ_t+1は状態Ｓ０になる。

【００１７】同様に、ＰＲ（１，１）回路は、中間系列
ｙ_tが状態Ｓ０のときに１（ｘ_t)が入力されると、０
（ｚ_t）を出力し、中間系列ｙ_t+1は状態Ｓ１になる。

【００１８】また、ＰＲ（１，１）回路は、中間系列ｙ
_tが状態Ｓ１のときに０（ｘ_t）が入力されると、＋Ａ
（ｚ_t）を出力し、中間系列ｙ_t+1は状態Ｓ１になる。

【００１９】また、ＰＲ（１，１）回路は、中間系列ｙ
_tが状態Ｓ１のときに１（ｘ_t）が入力されると、０
（ｚ_t）を出力し、中間系列ｙ_t+1は状態Ｓ０になる。

【００２０】図７は、上述の図６に示す状態遷移図を所
謂トレリス線図（Trellis diagram)に展開したものであ
る。ここで、状態から状態への矢印１本をブランチ
（枝）と呼び、ブランチの連なりをパスと呼ぶ。すなわ
ち、このＰＲ（１，１）回路の入力である変調系列ｘ_t
とブランチは１対１に対応している。

【００２１】また、この伝送システムは、その受信系と
して、Mod2加算器１２５からなる復調器を備える。そし
て、Mod2加算器１２５は、伝送路出力Ｚを法２の加算を
することにより、変調系列ｘ_tを再生し、この変調系列
ｘ_tを端子１７４を介して出力する。

【００２２】ここで、上述の図４に示すデータ記録再生
装置にＰＲ（１，１）を適用した場合のビタビ復号器１
０９について説明する。したがって、このビタビ復号器
１０９の動作は、上述の図６、図７に示す状態遷移図、
トレリス線図を用いて説明することができる。

【００２３】ところで、等化器１０６の出力である伝送
路出力Ｚは、−Ａ〜＋Ａの範囲の値をとり、それを標本
化回路１０８でサンプリングして得られる標本系列ｚ_t
の各データ（以下、サンプルデータｚ_tという。）は、
必ずしも−Ａ、０、＋Ａではない。そこで、状態Ｓ０に
あるときにサンプルデータｚ_tが受信され、その原因、
すなわち変調系列ｘ_tが０である確率をＰ₀₀(z_t) とす
る。

【００２４】同様に、状態Ｓ０にあるときにサンプルデ
ータｚ_tが受信され、変調系列ｘ_tが１である確率をＰ
₀₁(z_t) とし、状態Ｓ１にあるときにサンプルデータｚ
_tが受信され、変調系列ｘ_tが０である確率をＰ
₁₀(z_t) とし、状態Ｓ１にあるときにサンプルデータｚ
_tが受信され、変調系列ｘ_tが１である確率をＰ
₁₁(z_t) とする。

【００２５】また、これらの確率Ｐ₀₀(z_t) 、Ｐ
₀₁(z_t) 、Ｐ₁₀(z_t) 、Ｐ₁₁(z_t) の自然対数の負の値
で表される各ブランチの確からしさの度合い、すなわち
各ブランチの尤度（以下、ブランチメトリックとい
う。）をそれぞれＩ₀₀(z_t) 、Ｉ₀₁(z_t) 、Ｉ₁₀(z_t)
、Ｉ₁₁(z_t) とすると、上述の図７にトレリス線図
は、図８に示すトレリス線図に変形することができる。

【００２６】そして、ビタビ復号器１０９では、この図
８に示すように、サンプルデータｚ₁、ｚ₂、ｚ₃・・
・が得られると、それぞれのパスを通ったときのメトリ
ックが計算でき、これらのメトリックの比較により、最
も確からしいパスを決定することができる。

【００２７】具体的には、ビタビ復号器１０９は、図９
に示すように、ブランチメトリックを算出するブランチ
メトリック計算部１３０と、該ブランチメトリック計算
部１３０からのブランチメトリックとステートメトリッ
クを加算して新たなステートメトリックを算出するＡＣ
Ｓ（Add Compare Select) 回路１４０と、該ＡＣＳ回路
１４０からのステートメトリックを記憶するステートメ
トリック記憶部１５０と、上記ＡＣＳ回路１４０からの
ステートメトリックの比較結果に基づいて、復号データ
を出力するパスメモリ１６０とを備える。ここで、例え
ば時刻０における状態Ｓ０に到る生き残りパスのメトリ
ック、すなわち過去の生き残ったブランチメトリックの
累積和であるステートメトリックをＳＰ０とし、状態Ｓ
１に至るパスのステートメトリックをＳＰ１とする。

【００２８】また、ブランチメトリック計算部１３０
は、図１０に示すように、４つの演算回路１３１、１３
２、１３４、１３４から構成される。

【００２９】そして、演算回路１３１〜１３４は、標本
化回路１０８から端子１７５を介して供給されるサンプ
ルデータｚ_tに基づいて、それぞれブランチメトリック
Ｉ₀₁(z_t) 、Ｉ₁₀(z_t) 、Ｉ₀₀(z_t) 、Ｉ₁₁(z_t) を計
算し、これらのブランチメトリックをＡＣＳ回路１４０
に供給する。具体的には、演算回路１３１〜１３４は、
それぞれ例えば下記式１、２、３、４により、ブランチ
メトリックＩ₀₁(z_t)、Ｉ₁₀(z_t) 、Ｉ₀₀(z_t) 、Ｉ
₁₁(z_t) を求める。

【００３０】Ｉ₀₁(z_t) ＝（ｚ_t−０)²・・・式１Ｉ₁₀(z_t) ＝（ｚ_t−Ａ)²・・・式２Ｉ₀₀(z_t) ＝（ｚ_t＋Ａ)²・・・式３Ｉ₁₁(z_t) ＝（ｚ_t−０)²・・・式４ＡＣＳ回路１４０は、上述の図１０に示すように、４つ
の加算器１４１、１４２、１４３、１４４と、該加算器
１４１、１４２からのステートメトリックを比較する比
較器１４５と、該比較器１４５の出力に基づいて、加算
器１４１、１４２からのステートメトリックの何れか一
方を選択するセレクタ１４７と、上記加算器１４３、１
４４からのステートメトリックを比較する比較器１４６
と、該比較器１４６の出力に基づいて、加算器１４３、
１４４からのステートメトリックの何れか一方を選択す
るセレクタ１４８とを備える。

【００３１】また、ステートメトリック記憶部１５０
は、上述の図１０に示すように、上記セレクタ１４７で
選択されたステートメトリックＳＰ１を記憶するメモリ
１５１と、上記セレクタ１４８で選択されたステートメ
トリックＳＰ０を記憶するメモリ１５２とを備える。

【００３２】そして、加算器１４１は、演算回路１３１
からのブランチメトリックＩ₀₁(z_t) を、メモリ１５２
から供給されるステートメトリックＳＰ０に加算して、
新たなステートメトリックＳＰ１（＝ＳＰ０＋Ｉ
₀₁(z_t))を求め、このステートメトリックＳＰ１を比較
器１４５とセレクタ１４７に供給する。

【００３３】同様に、加算器１４２は、演算回路１３２
からのブランチメトリックＩ₁₀(z_t) を、メモリ１５１
から供給されるステートメトリックＳＰ１に加算して、
新たなステートメトリックＳＰ１（＝ＳＰ１＋Ｉ
₁₀(z_t))を求め、このステートメトリックＳＰ１を比較
器１４５とセレクタ１４７に供給する。

【００３４】また、加算器１４３は、演算回路１３３か
らのブランチメトリックＩ₀₀(z_t)を、メモリ１５２か
ら供給されるステートメトリックＳＰ０に加算して、新
たなステートメトリックＳＰ０（＝ＳＰ０＋Ｉ₀₀(z_t))
を求め、このステートメトリックＳＰ０を比較器１４６
とセレクタ１４８に供給する。

【００３５】また、加算器１４４は、演算回路１３４か
らのブランチメトリックＩ₁₁(z_t)を、メモリ１５１か
ら供給されるステートメトリックＳＰ１に加算して、新
たなステートメトリックＳＰ０（＝ＳＰ１＋Ｉ₁₁(z_t))
を求め、このステートメトリックＳＰ０を比較器１４６
とセレクタ１４８に供給する。

【００３６】比較器１４５は、加算器１４１からの新た
なステートメトリックＳＰ１と加算器１４２からの新た
なステートメトリックＳＰ１を比較して、値が小さなス
テートメトリックＳＰ１を選択するように、セレクタ１
４７を制御する。そして、メモリ１５１は、セレクタ１
４７で選択された新たなステートメトリックＳＰ１を次
の時刻におけるステートメトリックの計算に使用するた
めに記憶する。また、このとき、比較器１４５は、その
比較結果を端子１７６ａを介してパスメモリ１６０に供
給する。換言すると、比較器１４５は、例えば図８に示
す時刻ｔ＝３の状態Ｓ１に到る２つのパスの尤度、すな
わち時刻ｔ＝２での状態がＳ０であって変調系列ｘ_tと
して１が入力された尤度と、状態がＳ１であって変調系
列ｘ_tとして０が入力された尤度とを比較して、例えば
変調系列ｘ_tとして１が入力された尤度が高いとき、１
を出力する。そして、セレクタ１４７は、加算器１４１
からのステートメトリックＳＰ１を選択する。

【００３７】比較器１４６は、加算器１４３からの新た
なステートメトリックＳＰ０と加算器１４４からの新た
なステートメトリックＳＰ０を比較して、値が小さなス
テートメトリックＳＰ０を選択するように、セレクタ１
４８を制御する。そして、メモリ１５２は、セレクタ１
４８で選択された新たなステートメトリックＳＰ０を次
の時刻におけるステートメトリックの計算に使用するた
めに記憶する。また、比較器１４６は、その比較結果を
端子１７６ｂを介してパスメモリ１６０に供給する。換
言すると、比較器１４６は、例えば図８に示す時刻ｔ＝
３の状態Ｓ０に到る２つのパスの尤度、すなわち時刻ｔ
＝２での状態がＳ０であって変調系列ｘ_tとして０が入
力された尤度と、状態がＳ１であって変調系列ｘ_tとし
て１が入力された尤度とを比較して、例えば変調系列ｘ
_tとして０が入力された尤度が高いとき、１を出力す
る。そして、セレクタ１４８は、加算器１４３からのス
テートメトリックＳＰ１を選択する。

【００３８】すなわち、このＡＣＳ回路１４０は、例え
ば図８に示す時刻ｔ＝１における状態Ｓ１に到る２つの
パス、すなわち時刻ｔ＝０の状態Ｓ０からのブランチメ
トリックがＩ₀₁(z_t) であるブランチのパスと、状態Ｓ
１からのブランチメトリックがＩ₁₀(z_t) であるブラン
チのパスとを、それらのパスのステートメトリックＳＰ
１を比較して、値が小さい、すなわち尤度が高いパスを
生き残りパスとして選択する。また、このＡＣＳ回路１
４０は、時刻ｔ＝１における状態Ｓ０に到るパスの内の
尤度が高いパスを選択する。

【００３９】パスメモリ１６０は、図１１に示すよう
に、各段がセレクタ１６１及びメモリ１６２からなる回
路と、セレクタ１６３及びメモリ１６４からなる回路と
から構成され、これらの回路がパスが１本化されるのに
必要なＫ個縦続接続されたシフトレジスタからなる。

【００４０】また、シフトレジスタの各段の接続は、例
えば＃ｋ（ｋ＝１〜Ｋ）段目のセレクタ１６１、１６３
に、＃（ｋ−１）段目のメモリ１６２、１６４の両出力
が供給される接続となっている。なお、＃１段目のセレ
クタ１６１（以下、単にセレクタ１６１_#1という。）に
は、端子１７７ａ、１７７ｂを介して１、０が供給さ
れ、セレクタ１６３_#1には、端子１７８ａ、１７８ｂを
介して０、１が供給されている。

【００４１】そして、セレクタ１６１_#1は、端子１７６
ａを介し、比較器１４５から比較結果として例えば１が
供給されると、端子１７７ａを介して供給される１を選
択し、セレクタ１６１_#kは、前段のメモリ１６４_#(k-1)
の出力を選択する。一方、比較結果として０が供給され
ると、セレクタ１６１_#1は、端子１７７ｂを介して供給
される０を選択し、セレクタ１６１_#kは、前段のメモリ
１６２_#(k-1)の出力を選択する。

【００４２】また、同様に、セレクタ１６３_#1は、比較
器１４６から端子１７６ｂを介して１が供給されると、
端子１７８ａを介して供給される０を選択し、セレクタ
１６３_#kは、前段のメモリ１６４_#(k-1)の出力を選択す
る。一方、比較結果として０が供給されると、セレクタ
１６３_#1は、端子１７８ｂを介して供給される１を選択
し、セレクタ１６３_#kは、前段のメモリ１６２_#(k-1)の
出力を選択する。

【００４３】すなわち、このパスメモリ１６０は、ＡＧ
Ｃ回路１４０で選択されたパスに対応した変調系列ｘ_t
を順次記憶し、Ｋ段目の例えばメモリ１６２_#Kから変調
系列ｘ_tを復号データとし、端子１７４を介して復調器
１１０に出力する。なお、Ｋ段目のメモリ１６４_#Kから
も同じデータが出力されるので、このメモリ１６４_#Kの
出力を復号データとしてもよい。また、ＡＣＳ回路１４
０とステートメトリック記憶部１５０の間にＡＣＳ回路
１４０で求められたステートメトリックを正規化する正
規化部を設けるようにしてもい。

【００４４】

【発明が解決しようとする課題】ところで、ビタビ復号
器の問題点の１つとして動作速度の高速化が難しいとい
う点がある。具体的には、ビタビ復号器には、上述した
ようにＡＣＳ回路１４０の出力であるステートメトリッ
クをステートメトリック記憶部５０で記憶し、この記憶
したステートメトリックをＡＣＳ回路１４０の入力とす
るループが存在し、このループ部での演算を情報系列の
速度、すなわち１タイムスロット内で行う必要がある。
したがって、情報系列の速度を高くして行くと、ループ
部の１回の演算に許容される時間が短くなり、ある速度
以上になると、１回の演算を終えることができなくな
る。すなわち、ループ部以外の回路では、所謂パイプラ
イン処理や回路の並列化等の一般的な高速化の手法を用
いることができるが、ループ部では、１つ前の演算結果
を現在の演算にすぐに使用するため、これらの手法を適
用することができず、上述したように、ビタビ復号器の
動作速度の高速化は困難であった。

【００４５】本発明は、このような実情に鑑みてなされ
たものであり、従来の装置に比してより高速動作が可能
なビタビ復号方法及びビタビ復号装置の提供を目的とす
る。

【００４６】

【課題を解決するための手段】上述の課題を解決するた
めに、本発明に係る第１のビタビ復号方法は、ビタビ復
号の系を表現するＭ（Ｍ＞１：整数）個の状態の時間的
な推移を表すトレリス線図において、始点のＭ個の状態
のうちの１つの状態と、始点からＮ（Ｎ＞１：整数）標
本点離れた終点のＭ個の状態のうちの１つの状態とをそ
れぞれ連結する複数の部分的なパスの尤度を算出すると
共に、各部分的なパスの尤度に基づいて、尤度が最も高
い部分的なパスを検出する処理を、始点と終点の全て状
態のＭ×Ｍ個の組合せで繰り返す第１の工程と、始点の
それぞれの状態に到るＭ個のパスの尤度と、第１の工程
で検出されたＭ×Ｍ個の部分的なパスの尤度とを対応す
る始点の状態毎に加算して、終点のそれぞれの状態に到
るＭ×Ｍ個のパスの尤度を求めると共に、各パスの尤度
に基づいて、尤度が最も高いパスを終点のＭ個の状態毎
に検出する第２の工程と、第２の工程で検出されたＭ個
のパスの尤度を記憶すると共に、記憶した各パスの尤度
を、Ｎ標本点後に始点のそれぞれの状態に到るＭ個のパ
スの尤度とする第３の工程を有することを特徴とする。

【００４７】本発明に係る第２のビタビ復号方法は、第
１のビタビ復号方法において、第１の工程は、互いにＮ
標本点離れた始点と終点間において、互いに隣接した標
本点のＭ個の状態とＭ個の状態をそれぞれ連結する複数
の枝の尤度を算出する第４の工程と、第４の工程で算出
された各枝の尤度を加算して、複数の部分的なパスの尤
度を求める第５の工程と、第５の工程で求められた各部
分的なパスの尤度を比較して、尤度が最も高い部分的な
パスを、終点のＭ個の状態毎に検出する第６の工程から
なることを特徴とする。

【００４８】本発明に係る第３のビタビ復号方法は、第
１又は第２のビタビ復号方法において、始点又は終点の
状態の数Ｍを２とし、始点と終点の間隔Ｎを２とするこ
とを特徴とする。

【００４９】本発明に係る第１のビタビ復号装置は、ビ
タビ復号の系を表現するＭ（Ｍ＞１：整数）個の状態の
時間的な推移を表すトレリス線図において、始点のＭ個
の状態のうちの１つの状態と、始点からＮ（Ｎ＞１：整
数）標本点離れた終点のＭ個の状態のうちの１つの状態
とをそれぞれ連結する複数の部分的なパスの尤度を算出
すると共に、各部分的なパスの尤度に基づいて、尤度が
最も高い部分的なパスを、始点と終点の全ての状態のＭ
×Ｍ個の組合せで求める第１の演算手段と、始点のそれ
ぞれの状態に到るＭ個のパスの尤度と、第１の演算手段
から供給されるＭ×Ｍ個の部分的なパスの尤度とを対応
する始点の状態毎に加算して、終点のそれぞれの状態に
到るＭ×Ｍ個のパスの尤度を求めると共に、各パスの尤
度に基づいて、尤度が最も高いパスを終点のＭ個の状態
毎に検出する第２の演算手段と、第２の演算手段からの
Ｍ個のパスの尤度を記憶すると共に、記憶した各パスの
尤度を、Ｎ標本点後に始点のそれぞれの状態に到るＭ個
のパスの尤度として、第２の演算手段に供給する記憶手
段とを備えることを特徴とする。

【００５０】本発明に係る第２のビタビ復号装置は、第
１のビタビ復号装置において、第１の演算手段は、互い
にＮ標本点離れた始点と終点間において、互いに隣接し
た標本点のＭ個の状態とＭ個の状態をそれぞれ連結する
枝の尤度を算出する枝尤度計算手段と、枝尤度計算手段
からの各枝の尤度を加算して、Ｍ×Ｍ個の部分的なパス
の尤度を求める部分パス尤度計算手段と、部分パス尤度
計算手段からの部分的なパスの尤度を比較して、尤度が
最も高い部分的なパスを、終点のＭ個の状態毎に検出す
る比較手段とを備えることを特徴とする。

【００５１】本発明に係る第３のビタビ復号装置は、第
１又は第２のビタビ復号装置において、始点又は終点の
状態の数Ｍを２とし、始点と終点の間隔Ｎを２とするこ
とを特徴とする。

【００５２】

【作用】本発明では、始点のＭ個の状態のうちの１つの
状態と、始点からＮ標本点離れた終点のＭ個の状態のう
ちの１つの状態とをそれぞれ連結する複数の部分的なパ
スの尤度を算出すると共に、各部分的なパスの尤度に基
づいて、尤度が最も高い部分的なパスを検出する処理
を、始点と終点の全て状態のＭ×Ｍ個の組合せで繰り返
す。この検出されたＭ×Ｍ個の部分的なパスの尤度と、
始点のそれぞれの状態に到るＭ個のパスの尤度とを対応
する始点の状態毎に加算して、終点のそれぞれの状態に
到るＭ×Ｍ個のパスの尤度を求めると共に、各パスの尤
度に基づいて、尤度が最も高いパスを終点のＭ個の状態
毎に検出する。そして、検出されたＭ個のパスの尤度を
記憶すると共に、記憶した各パスの尤度を、Ｎ標本点後
に始点のそれぞれの状態に到るＭ個のパスの尤度とす
る。

【００５３】

【実施例】以下、本発明に係るビタビ復号方法及びビタ
ビ復号装置の一実施例を図面を参照しながら説明する。

【００５４】本発明を適用したビタビ復号装置は、例え
ば図１に示すように、ビタビ復号の系を表現するＭ（Ｍ
＞１：整数）個の状態の時間的な推移を表すトレリス線
図において、互いにＮ（Ｎ＞１：整数）標本点離れた始
点と終点間における互いに隣接した標本点のＭ個の状態
とＭ個の状態をそれぞれ連結する複数の枝（以下、ブラ
ンチという。）の尤度（以下、メトリックという。）を
求めるブランチメトリック計算部１０と、該ブランチメ
トリック計算部１０からの各ブランチメトリックを加算
して、ブランチの連なりからなる複数の部分的なパス
（以下、部分パスという。）のメトリックを求めると共
に、これらの部分パスのメトリックを比較して、メトリ
ックが最も高い部分パスを上記終点のＭ個の状態毎に検
出するＡＣＳ（Add Compare Select) 回路２０と、上記
始点のそれぞれの状態に到るＭ個のパスの尤度（以下、
ステートメトリックという。）と、上記ＡＣＳ回路２０
から供給されるＭ×Ｍ個の部分パスのメトリックとを対
応する始点の状態毎に加算して、上記終点のそれぞれの
状態に到るＭ×Ｍ個のパスのステートメトリックを求め
ると共に、該各パスのステートメトリックに基づいて、
ステートメトリックが最も高いパスを上記終点のＭ個の
状態毎に検出するＡＣＳ回路４０と、該ＡＣＳ回路４０
からのＭ個のパスのステートメトリックを記憶すると共
に、該記憶した各パスのステートメトリックを、Ｎ標本
点後に上記始点のそれぞれの状態に到るＭ個のパスのス
テートメトリックとして、上記ＡＣＳ回路４０に供給す
るステートメトリック記憶部５０と、上記ＡＣＳ回路２
０、４０で検出された部分パス、パスの情報に基づい
て、復号データを出力するパスメモリ６０とを備える。

【００５５】ここで、この本発明を適用したビタビ復号
装置を、所謂パーシャルレスポンス（１，１）（以下、
ＰＲ（１，１）という。）に対する復号手段として用い
た具体例について説明する。したがって、トレリス線図
における状態の数Ｍは２（以下、状態Ｓ１、Ｓ０とす
る。）となる。

【００５６】そして、ブランチメトリック計算部１０に
は、伝送路の出力をサンプリングしてデータに変換し
た、例えば従来の技術で述べた図４に示す標本化回路１
０８の出力である標本系列ｚ_tが、端子１を介し、入力
データ（以下、サンプルデータｚ_tという。）として供
給される。

【００５７】そして、始点と終点の間隔Ｎを例えば２と
すると、ブランチメトリック計算部１０は、互いに２標
本点離れた始点と終点間における互いに隣接した標本点
の２つの状態Ｓ１、Ｓ０と２つの状態Ｓ１、Ｓ０をそれ
ぞれ連結する、全体として８個のブランチのメトリック
（以下、ブランチメトリックという。）を、サンプルデ
ータｚ_tに基づいて求める。そして、ブランチメトリッ
ク計算部１０は、これらのブランチメトリックをＡＣＳ
回路２０に供給する。

【００５８】ＡＣＳ回路２０は、ブランチメトリック計
算部１０から供給される各ブランチメトリックを、連続
した３つの標本点の各状態Ｓ１、Ｓ０を連続して連結す
る部分パス毎に加算して、８個の部分パスのメトリック
を求めると共に、これらの部分パスのメトリックを比較
して、メトリックが最も高い部分パスを終点の２個の状
態毎に検出する。そして、ＡＣＳ回路２０は、検出した
部分パスを示す情報をパスメモリ６０に供給すると共
に、これらの部分パスのメトリックをＡＣＳ回路４０に
供給する。すなわち、このＡＣＳ回路２０は、部分パス
のメトリックを２標本点毎に出力する。

【００５９】ＡＣＳ回路４０は、ステートメトリック記
憶部５０から供給される始点のそれぞれの状態Ｓ１、Ｓ
０に到る２つのパスのステートメトリックと、ＡＣＳ回
路２０から供給される４個の部分パスのメトリックとを
対応する始点の状態毎に加算して、終点のそれぞれの状
態Ｓ１、Ｓ０に到る４のパスのステートメトリックを求
める。また、ＡＣＳ回路４０は、これらのパスのステー
トメトリックに基づいて、ステートメトリックが最も高
いパスを終点の２個の状態毎に検出する。そして、検出
したパスを示す情報をパスメモリ６０に供給すると共
に、これらのパスのステートメトリックをステートメト
リック記憶部５０に供給する。

【００６０】すなわち、このＡＣＳ回路４０は、上述の
終点の状態に到る４つのパスのステートメトリックを求
める演算と最高のステートメトリックのパスを検出する
処理を、標本点毎に行うのではなく、２標本点毎に行
う。したがって、ＡＣＳ回路４０に許容される処理時間
は、従来の装置の２倍となる。換言すると、始点と終点
間隔をＮとすると、ＡＣＳ回路４０に許容される処理時
間は、従来の装置のＮ倍となる。

【００６１】ステートメトリック記憶部５０は、ＡＣＳ
回路４０から供給される２つのパスのステートメトリッ
クを記憶すると共に、記憶した各パスのステートメトリ
ックを、２標本点後に始点のそれぞれの状態に到る２つ
のパスのステートメトリックとして、ＡＣＳ回路４０に
供給する。

【００６２】パスメモリ６０は、ＡＣＳ回路２０、４０
から供給される部分パスとパスの情報に基づいて、復号
データを再生し、この復号データを端子２を介して後段
に接続された復調器（例えば図４に示す復調器５０）に
出力する。

【００６３】以上のように、この本発明を適用したビタ
ビ復号装置には、ビタビ復号の動作速度を制限するルー
プ、すなわちＡＣＳ回路４０からのステートメトリック
をステートメトリック記憶部５０で記憶し、記憶したス
テートメトリックをＡＣＳ回路４０の入力とするループ
が存在するが、上述したように、ＡＣＳ回路４０での演
算処理は、Ｎ（例えば２）標本点毎に行えばよく、ＡＣ
Ｓ回路４０に許容される処理時間を従来の装置に比して
Ｎ倍にすることができる。換言すると、このビタビ復号
装置では、従来の装置に比して情報を伝送する伝送速度
を２倍にすることができる。

【００６４】つぎに、上述したビタビ復号装置を構成す
る各部の具体的な構成について説明する。

【００６５】ブランチメトリック計算部１０は、例えば
図２に示すように、隣接する状態と状態を結ぶブランチ
のブランチメトリックをそれぞれ求める８個の演算回路
１１ａ、１１ｂ、１２ａ、１２ｂ、１３ａ、１３ｂ、１
４ａ、１４ｂから構成される。また、端子１は２つの端
子１ａ、１ｂからなり、演算回路１１ａ〜１４ａには、
端子１ａを介して奇数のサンプルデータｚ_tが供給さ
れ、演算回路１１ｂ〜１４ｂには、端子１ｂを介して偶
数のサンプルデータｚ_tが供給される。ここで、奇数の
サンプルデータｚ_tとは、例えば従来の技術で述べた図
８に示す時刻ｔ＝０、２・・・の状態から時刻ｔ＝１、
３・・・の状態にそれぞれ到る各ブランチに対応したサ
ンプルデータｚ₁、ｚ₃・・・であり、偶数のサンプル
データｚ_tとは、時刻ｔ＝１、３・・・の状態から時刻
ｔ＝２、４・・・の状態にそれぞれ到る各ブランチに対
応したサンプルデータｚ₂、ｚ₄・・・である。

【００６６】そして、状態Ｓ０にあるときにサンプルデ
ータｚ_tが受信され、その原因、すなわちパーシャルレ
スポンスにおけるプリコーダ（例えば図８に示すプリコ
ーダ５２）に入力される変調系列ｘ_tが０である確率を
Ｐ₀₀(z_t) とする。同様に、状態Ｓ０にあるときにサン
プルデータｚ_tが受信され、変調系列ｘ_tが１である確
率をＰ₀₁(z_t) とし、状態Ｓ１にあるときにサンプルデ
ータｚ_tが受信され、変調系列ｘ_tが０である確率をＰ
₁₀(z_t) とし、状態Ｓ１にあるときにサンプルデータｚ
_tが受信され、変調系列ｘ_tが１である確率をＰ
₁₁(z_t) とすると、これらの演算回路１１ａ、１１ｂ
は、確率Ｐ₁₀(z_t) の自然対数の負の値で表されるブラ
ンチの確からしさの度合い、すなわちブランチメトリッ
クＩ₁₀(z_t) を算出する。したがって、ブランチの確か
らしさの度合いは、この計算で求められるブランチメト
リックＩ₁₀(z_t) の値が小さいとき、高いことになる。

【００６７】同様に、演算回路１２ａ、１２ｂは、確率
Ｐ₁₁(z_t) からブランチメトリックＩ₁₁(z_t) を算出
し、演算回路１３ａ、１３ｂは、確率Ｐ₀₁(z_t) からブ
ランチメトリックＩ₀₁(z_t) を算出し、演算回路１４
ａ、１４ｂは、確率Ｐ₀₀(z_t) からブランチメトリック
Ｉ₀₀(z_t) 算出する。なお、演算回路１１ａ〜１４ａで
は、ｔは奇数であり、演算回路１１ｂ〜１４ｂでは、ｔ
は偶数である。

【００６８】具体的には、例えば従来の技術で述べた図
８に示すように、演算回路１１ａは、例えば時刻ｔ＝０
における状態Ｓ１から時刻ｔ＝１における状態Ｓ１に到
るブランチに対応した（以下、ブランチ（状態Ｓ１_t=0
−状態Ｓ１_t=1)と表す。）ブランチメトリックＩ₁₀(z₁)
を求める。

【００６９】同様に、演算回路１２ａは、ブランチ（状
態Ｓ１_t=0−状態Ｓ０_t=1)のブランチメトリックＩ₁₁(z
₁)を求め、演算回路１３ａは、ブランチ（状態Ｓ０_t=0
−状態Ｓ１_t=1)のブランチメトリックＩ₀₁(z₁)を求め、
演算回路１４ａは、ブランチ（状態Ｓ０_t=0−状態Ｓ０
_t=1)のブランチメトリックＩ₀₀(z₁)を求める。

【００７０】一方、演算回路１１ｂは、ブランチ（状態
Ｓ１_t=1−状態Ｓ１_t=2)のブランチメトリックＩ₁₀(z₂)
を求め、演算回路１２ｂは、ブランチ（状態Ｓ１_t=1−
状態Ｓ０_t=2)のブランチメトリックＩ₁₁(z₂)を求め、演
算回路１３ｂは、ブランチ（状態Ｓ０_t=1−状態Ｓ１
_t=2)のブランチメトリックＩ₀₁(z₂)を求め、演算回路１
４ｂは、ブランチ（状態Ｓ０_t=1−状態Ｓ０_t=2)のブラ
ンチメトリックＩ₀₀(z₂)を求める。そして、これらの８
個のブランチメトリックはＡＣＳ回路２０に供給され
る。

【００７１】ところで、演算回路１１ａ、１１ｂは、例
えば下記式５により、演算回路１２ａ、１２ｂは、例え
ば下記式６により、演算回路１３ａ、１３ｂは、例えば
下記式７により、演算回路１４ａ、１４ｂは、例えば下
記式８により、それぞれのブランチメトリックＩ
₁₀(z_t) 、Ｉ₁₁(z_t) 、Ｉ₀₁(z_t) 、Ｉ₀₀(z_t) を求め
るようにしてもよい。なお、ｔは、演算回路１１ａ〜１
４ａでは奇数であり、演算回路１１ｂ〜１４ｂでは偶数
である。

【００７２】Ｉ₀₁(z_t) ＝（ｚ_t−０)²・・・式５Ｉ₁₀(z_t) ＝（ｚ_t−Ａ)²・・・式６Ｉ₀₀(z_t) ＝（ｚ_t＋Ａ)²・・・式７Ｉ₁₁(z_t) ＝（ｚ_t−０)²・・・式８ＡＣＳ回路２０は、例えば上述の図２に示すように、連
続した３標本点の各状態を連続してそれぞれ連結する各
部分パスのメトリックをそれぞれ算出する８個の加算器
２１、２２、２３、２４、２５、２６、２７、２８と、
該加算器２１〜２８で算出された部分パスのメトリック
を比較する４つの比較器３１、３２、３３、３４と、該
比較器３１〜３４の比較結果に基づいて、上記加算器２
１〜２８からの部分パスのメトリックを切り換え選択す
る４個のセレクタ３５、３６、３７、３８とを備える。

【００７３】そして、例えば、加算器２１は、演算回路
１１ａから供給されるブランチメトリックＩ₁₀(z₁)と演
算回路１１ｂから供給されるブランチメトリックＩ₁₀(z
₂)を加算して、状態Ｓ１_t=0−状態Ｓ１_t=1−状態Ｓ１
_t=2からなる部分パス（以下、部分パス（状態Ｓ１_t=0
−状態Ｓ１_t=1−状態Ｓ１_t=2)という。）のメトリック
（Ｉ₁₀(z₁)＋Ｉ₁₀(z₂)) を求め、この部分パスのメトリ
ックを比較器３１とセレクタ３５に供給する。

【００７４】同様に、加算器２２は、演算回路１２ａか
らのブランチメトリックＩ₁₁(z₁)と演算回路１３ｂから
のブランチメトリックＩ₀₁(z₂)を加算して、部分パス
（状態Ｓ１_t=0−状態Ｓ０_t=1−状態Ｓ１_t=2)のメトリ
ック（Ｉ₁₁(z₁)＋Ｉ₀₁(z₂)) を求め、この部分パスのメ
トリックを比較器３１とセレクタ３５に供給する。

【００７５】加算器２３は、演算回路１３ａからのブラ
ンチメトリックＩ₀₁(z₁)と演算回路１１ｂからのブラン
チメトリックＩ₁₀(z₂)を加算して、部分パス（状態Ｓ０
_t=0−状態Ｓ１_t=1−状態Ｓ１_t=2)のメトリック（Ｉ
₀₁(z₁)＋Ｉ₁₀(z₂)) を求め、この部分パスのメトリック
を比較器３２とセレクタ３６に供給する。

【００７６】加算器２４は、演算回路１４ａからのブラ
ンチメトリックＩ₀₀(z₁)と演算回路１３ｂからのブラン
チメトリックＩ₀₁(z₂)を加算して、部分パス（状態Ｓ０
_t=0−状態Ｓ０_t=1−状態Ｓ１_t=2)のメトリック（Ｉ
₀₀(z₁)＋Ｉ₀₁(z₂)) を求め、この部分パスのメトリック
を比較器３２とセレクタ３６に供給する。

【００７７】加算器２５は、演算回路１１ａからのブラ
ンチメトリックＩ₁₀(z₁)と演算回路１２ｂからのブラン
チメトリックＩ₁₁(z₂)を加算して、部分パス（状態Ｓ１
_t=0−状態Ｓ１_t=1−状態Ｓ０_t=2)のメトリック（Ｉ
₁₀(z₁)＋Ｉ₁₁(z₂)) を求め、この部分パスのメトリック
を比較器３３とセレクタ３７に供給する。

【００７８】加算器２６は、演算回路１２ａからのブラ
ンチメトリックＩ₁₁(z₁)と演算回路１４ｂからのブラン
チメトリックＩ₀₀(z₂)を加算して、部分パス（状態Ｓ１
_t=0−状態Ｓ０_t=1−状態Ｓ０_t=2)のメトリック（Ｉ
₁₁(z₁)＋Ｉ₀₀(z₂)) を求め、この部分パスのメトリック
を比較器３３とセレクタ３７に供給する。

【００７９】加算器２７は、演算回路１３ａからのブラ
ンチメトリックＩ₀₁(z₁)と演算回路１２ｂからのブラン
チメトリックＩ₁₁(z₂)を加算して、部分パス（状態Ｓ０
_t=0−状態Ｓ１_t=1−状態Ｓ０_t=2)のメトリック（Ｉ
₀₁(z₁)＋Ｉ₁₁(z₂)) を求め、この部分パスのメトリック
を比較器３４とセレクタ３８に供給する。

【００８０】加算器２８は、演算回路１４ａからのブラ
ンチメトリックＩ₀₀(z₁)と演算回路１４ｂからのブラン
チメトリックＩ₀₀(z₂)を加算して、部分パス（状態Ｓ０
_t=0−状態Ｓ０_t=1−状態Ｓ０_t=2)のメトリック（Ｉ
₀₀(z₁)＋Ｉ₀₀(z₂)) を求め、この部分パスのメトリック
を比較器３４とセレクタ３８に供給する。

【００８１】比較器３１は、加算器２１から供給される
部分パス（状態Ｓ１_t=0−状態Ｓ１_t=1−状態Ｓ１_t=2)
のメトリック（Ｉ₁₀(z₁)＋Ｉ₁₀(z₂)) と、加算器２２か
ら供給される部分パス（状態Ｓ１_t=0−状態Ｓ０_t=1−
状態Ｓ１_t=2)のメトリック（Ｉ₁₁(z₁)＋Ｉ₀₁(z₂)) とを
比較して、メトリック（計算値）が小さい方を選択する
ようにセレクタ３５を制御する。例えば、比較器３１
は、部分パス（状態Ｓ１_t=0−状態Ｓ１_t=1−状態Ｓ１
_t=2)のメトリックが小さいときは１を出力し、セレクタ
３５は、比較器３１の出力に基づいて、例えば比較結果
が１のときは、加算器２１から供給される部分パス（状
態Ｓ１_t=0−状態Ｓ１_t=1−状態Ｓ１_t=2)のメトリック
（Ｉ₁₀(z₁)＋Ｉ₁₀(z₂)) を選択し、比較結果が０のとき
は、加算器２２から供給される部分パス（状態Ｓ１_t=0
−状態Ｓ０_t=1−状態Ｓ１_t=2)のメトリック（Ｉ₁₁(z₁)
＋Ｉ₀₁(z₂)) を選択して、選択したメトリックをＡＣＳ
回路４０に供給する。

【００８２】同様に、比較器３２は、加算器２３から供
給される部分パス（状態Ｓ０_t=0−状態Ｓ１_t=1−状態
Ｓ１_t=2)のメトリック（Ｉ₀₁(z₁)＋Ｉ₁₀(z₂)) と、加算
器２４から供給される部分パス（状態Ｓ０_t=0−状態Ｓ
０_t=1−状態Ｓ１_t=2)のメトリック（Ｉ₀₀(z₁)＋Ｉ₀₁(z
₂)) とを比較して、メトリックが小さい方を選択するよ
うにセレクタ３６を制御する。

【００８３】また、比較器３３は、加算器２５から供給
される部分パス（状態Ｓ１_t=0−状態Ｓ１_t=1−状態Ｓ
０_t=2)のメトリック（Ｉ₁₀(z₁)＋Ｉ₁₁(z₂)) と、加算器
２６から供給される部分パス（状態Ｓ１_t=0−状態Ｓ０
_t=1−状態Ｓ０_t=2)のメトリック（Ｉ₁₁(z₁)＋Ｉ
₀₀(z₂)) とを比較して、メトリックが小さい方を選択す
るようにセレクタ３７を制御する。

【００８４】また、比較器３４は、加算器２７から供給
される部分パス（状態Ｓ０_t=0−状態Ｓ１_t=1−状態Ｓ
０_t=2)のメトリック（Ｉ₀₁(z₁)＋Ｉ₁₁(z₂)) と、加算器
２８から供給される部分パス（状態Ｓ０_t=0−状態Ｓ０
_t=1−状態Ｓ０_t=2)のメトリック（Ｉ₀₀(z₁)＋Ｉ
₀₀(z₂)) とを比較して、メトリックが小さい方を選択す
るようにセレクタ３８を制御する。

【００８５】かくして、このＡＣＳ回路２０は、始点の
状態がＳ１から終点の状態がＳ１に到る２つの部分パス
のうちの尤度（メトリック）が高い（計算値が小さい）
部分パスと、始点の状態がＳ０から終点の状態がＳ１に
到る２つの部分パスのうちのメトリックが高い部分パス
と、始点の状態がＳ１から終点の状態がＳ０に到る２つ
の部分パスのうちのメトリックが高い部分パスと、始点
の状態がＳ０から終点の状態がＳ０に到る２つの部分パ
スのうちのメトリックが高い部分パスとを検出して、検
出した４つの部分パスのメトリックをＡＣＳ回路４０に
供給する。また、ＡＣＳ回路２０は、比較器３１〜３４
からの比較結果、すなわち選択した部分パスを示す情報
を、端子３ａ、３ｂ、３ｃ、３ｄを介してパスメモリ６
０に供給する。

【００８６】ＡＣＳ回路４０は、例えば上述の図２に示
すように、始点のそれぞれの状態に到る２個のステート
メトリックＳＰ１、ＳＰ０と、上記ＡＣＳ回路２０から
供給される４個の部分パスのメトリックとを対応する始
点の状態毎に加算して、終点のそれぞれの状態に到る４
つのパスのステートメトリックを求める加算器４１、４
２、４３、４４と、該加算器４１〜４４で算出されたス
テートメトリックを比較する２つの比較器４５、４６
と、該比較器４５、４６の比較結果に基づいて、上記加
算器４１〜４４からのステートメトリックを切り換え選
択する２つのセレクタ４７、４８とを備える。

【００８７】また、ステートメトリック記憶部５０は、
例えば上述の図２に示すように、上記セレクタ４６で選
択されたステートメトリックＳＰ１を記憶するメモリ５
１と、上記セレクタ４８で選択されたステートメトリッ
クＳＰ０を記憶するメモリ５２とを備える。

【００８８】そして、加算器４１は、下記式９により、
セレクタ３５から供給される始点の状態がＳ１であって
終点の状態がＳ１の部分パスのメトリックと、メモリ５
１から供給される始点の状態Ｓ１に到るパスのステート
メトリックＳＰ１とを加算して、終点の状態Ｓ１に到る
パスのステートメトリックＳＰ１を求め、このステート
メトリックＳＰ１を比較器４５とセレクタ４７に供給す
る。

【００８９】ＳＰ１＝min[Ｉ₁₀(z₁)＋Ｉ₁₀(z₂)，Ｉ₁₁(z₁)＋Ｉ₀₁(z₂)] ＋ＳＰ１・・・式９ここで、min[Ｘ，Ｙ] は、ＸとＹの値が小さい方を選択
することを表す。

【００９０】同様に、加算器４２は、下記式１０によ
り、セレクタ３６から供給される始点の状態がＳ０であ
って終点の状態がＳ１の部分パスのメトリックと、メモ
リ５２から供給される始点の状態Ｓ０に到るパスのステ
ートメトリックＳＰ０とを加算して、終点の状態Ｓ１に
到るパスのステートメトリックＳＰ１を求め、このステ
ートメトリックＳＰ１を比較器４５とセレクタ４７に供
給する。

【００９１】ＳＰ１＝min[Ｉ₀₁(z₁)＋Ｉ₁₀(z₂), Ｉ₀₀(z₁)＋Ｉ₀₁(z₂)] ＋ＳＰ０・・・式１０また、加算器４３は、下記式１１により、セレクタ３７
から供給される始点の状態がＳ１であって終点の状態が
Ｓ０の部分パスのメトリックと、メモリ５１から供給さ
れる始点の状態Ｓ１に到るパスのステートメトリックＳ
Ｐ１とを加算して、終点の状態Ｓ０に到るパスのステー
トメトリックＳＰ０を求め、このステートメトリックＳ
Ｐ０を比較器４６とセレクタ４８に供給する。

【００９２】ＳＰ０＝min[Ｉ₁₀(z₁)＋Ｉ₁₁(z₂) ,Ｉ₁₁(z₁)＋Ｉ₀₀(z₂)] ＋ＳＰ０・・・式１１また、加算器４４は、下記式１２により、セレクタ３８
から供給される始点の状態がＳ０であって終点の状態が
Ｓ０の部分パスのメトリックと、メモリ５１から供給さ
れる始点の状態Ｓ１に到るパスのステートメトリックＳ
Ｐ１とを加算して、終点の状態Ｓ０に到るパスのステー
トメトリックＳＰ０を求め、このステートメトリックＳ
Ｐ０を比較器４６とセレクタ４８に供給する。

【００９３】ＳＰ０＝min[Ｉ₀₁(z₁)＋Ｉ₁₁(z₂) ,Ｉ₀₀(z₁)＋Ｉ₀₀(z₂)] ＋ＳＰ１・・・式１２比較器４５は、加算器４１から供給される終点の状態Ｓ
１に到るパスのステートメトリックＳＰ１と、加算器４
２から供給される終点の状態Ｓ１に到るパスのステート
メトリックＳＰ１とを比較して、ステートメトリックＳ
Ｐ１が大きい方を選択するようにセレクタ３５を制御す
る。例えば、比較器４１は、加算器４１からのステート
メトリックＳＰ１が大きいときは１を出力し、セレクタ
４７は、比較器３１の出力に基づいて、例えば比較結果
が１のときは、加算器４１からのステートメトリックＳ
Ｐ１を選択し、比較結果が０のときは、加算器４２から
のステートメトリックＳＰ１を選択して、選択したステ
ートメトリックＳＰ１をメモリ５１に供給する。

【００９４】同様に、比較器４７は、加算器４４から供
給される終点の状態Ｓ０に到るパスのステートメトリッ
クＳＰ０と、加算器４４から供給される終点の状態Ｓ０
に到るパスのステートメトリックＳＰ０とを比較して、
ステートメトリックＳＰ０が大きい方を選択するように
セレクタ４８を制御する。

【００９５】かくして、このＡＣＳ回路４０は、終点の
状態がＳ１に到る２つのパスのうちのステートメトリッ
クＳＰ１が高い（計算値が小さい）パスと、終点の状態
がＳ０に到る２つのパスのうちのステートメトリックＳ
Ｐ０が高いパスとを検出して、検出した２つのパスのス
テートメトリックＳＰ１、ＳＰ０をステートメトリック
記憶部５０に供給する。また、ＡＣＳ回路４０は、比較
器４５、４６からの比較結果、すなわち選択したパスを
示す情報を、端子４ａ、４ｂを介してパスメモリ６０に
供給する。

【００９６】パスメモリ６０は、例えば図３に示すよう
に、各段が、奇数ビット用のセレクタ７１及びメモリ７
２からなる回路と、偶数ビット用のセレクタ７３及びメ
モリ７４からなる回路と、奇数ビット用のセレクタ７５
及びメモリ７６からなる回路と、偶数ビット用のセレク
タ７７及びメモリ７８からなる回路とから構成され、こ
れらの回路がパスが１本化されるのに必要なＫ個縦続接
続されたシフトレジスタを備える。

【００９７】また、このパスメモリ６０は、上記比較器
３１〜３４からの比較結果に基づいて、上記セレクタ３
５〜３８で選択された部分パスの各ブランチに対応した
変調系列ｘ_tの値を選択する８個のセレクタ６１ａ、６
１ｂ、６２ａ、６２ｂ、６３ａ、６３ｂ、６４ａ、６４
ｂと、上記Ｋ段目のメモリ７２、７３の各出力をシリア
ルデータに変換して出力するパラレル／シリアル変換器
８１とを備える。

【００９８】そして、シフトレジスタの各段の接続は、
例えば＃ｋ（ｋ＝１〜Ｋ）段目のセレクタ７１に、＃
（ｋ−１）段目のメモリ７２、７６（以下、単にメモリ
７２_#( _k-1)、７６_#(k-1)という。）の各出力が供給さ
れ、セレクタ７３_#kにメモリ７４_#(k-1)、７８_#(k-1)の
各出力が供給され、セレクタ７５_#kにメモリ７
２_#(k-1)、７６_#k-1の各出力が供給され、セレクタ７７
_#kにメモリ７４_#(k-1)、７８_#(k-1)の各出力が供給され
る接続となっている。なお、＃１段目のセレクタ７１_#1
には、端子５ａ、５ｂを介して供給される０、１を選択
するセレクタ６１ａの出力と、端子６ａ、６ｂを介して
供給される１、０を選択するセレクタ６２ａの出力とが
接続されている。また、セレクタ７３_#1には、端子５
ａ、５ｂを介して供給される０、１を選択するセレクタ
６１ｂ、６２ｂの各出力が接続されている。また、セレ
クタ７５_#1には、端子５ａ、５ｂを介して供給される
０、１を選択するセレクタ６３ａの出力と、端子６ａ、
６ｂを介して供給される１、０を選択するセレクタ６４
ａの出力とが接続されている。また、セレクタ７７_#1に
は、端子６ａ、６ｂを介して供給される１、０を選択す
るセレクタ６３ｂ、６４ｂの各出力が接続されている。

【００９９】そして、セレクタ６１ａ、６１ｂは、端子
３ａを介し、比較器３１から比較結果として例えば１が
供給されると、端子５ａを介して供給される０を選択
し、比較結果として０が供給されると、端子５ｂを介し
て供給される１を選択する。

【０１００】同様に、端子３ｂを介し、比較器３２から
比較結果として例えば１が供給されると、セレクタ６２
ａは、端子６ａを介して供給される１を選択し、セレク
タ６２ｂは、端子５ａを介して供給される０を選択し、
比較結果として０が供給されると、セレクタ６２ａは、
端子６ｂを介して供給される０を選択し、セレクタ６２
ｂは、端子５ｂを介して供給される１を選択する。

【０１０１】また、端子３ｃを介し、比較器３３から比
較結果として例えば１が供給されると、セレクタ６３ａ
は、端子５ａを介して供給される０を選択し、セレクタ
６３ｂは、端子６ａを介して供給される１を選択し、比
較結果として０が供給されると、セレクタ６３ａは、端
子５ｂを介して供給される１を選択し、セレクタ６３ｂ
は、端子６ｂを介して供給される０を選択する。

【０１０２】また、セレクタ６４ａ、６４ｂは、端子３
ｄを介し、比較器３４から比較結果として例えば１が供
給されると、端子６ａを介して供給される１を選択し、
比較結果として０が供給されると、端子６ｂを介して供
給される０を選択する。

【０１０３】かくして、セレクタ６１ａ〜６４ｂは、Ａ
ＣＳ回路２０の比較器３１〜３４からの比較結果、すな
わち選択した部分パスを示す情報に基づいて、ＡＣＳ回
路２０のセレクタ３５〜３８で選択された部分パスの各
ブランチに対応した変調系列ｘ_tの値を選択して、選択
した０又は１をセレクタ７１_#1、７３_#1、７５_#1、７７
_#1に供給する。

【０１０４】セレクタ７１_#1、は、端子４ａを介し、比
較器４５から比較結果として１が供給されると、セレク
タ６１ａの出力を選択し、このとき、セレクタ７３_#1は
セレクタ６１ｂの出力を選択し、ｋ段目のセレクタ７１
_#kは、メモリ７２_#(k-1)の出力を選択し、セレクタ７３
_#kは、メモリ７４_#(k-1)の出力を選択する。

【０１０５】一方、比較結果として０が供給されると、
セレクタ７１_#1、は、セレクタ６２ａの出力を選択し、
セレクタ７３_#1はセレクタ６２ｂの出力を選択し、セレ
クタ７１_#kはメモリ７６_#(k-1)の出力を選択し、セレク
タ７３_#kは、メモリ７８_#(k- ₁₎の出力を選択する。

【０１０６】同様に、端子４ｂを介し、比較器４６から
比較結果として１が供給されると、セレクタ７５_#1は、
セレクタ６３ａの出力を選択し、セレクタ７７_#1はセレ
クタ６３ｂの出力を選択し、セレクタ７５_#kは、メモリ
７２_#(k-1)の出力を選択し、セレクタ７７_#kは、メモリ
７４_#(k-1)の出力を選択する。一方、比較結果として０
が供給されると、セレクタ７５_#1、は、セレクタ６４ａ
の出力を選択し、セレクタ７７_#1はセレクタ６４ｂの出
力を選択し、セレクタ７５_#kはメモリ７６_#(k- ₁₎の出力
を選択し、セレクタ７７_#kは、メモリ７８_#(k-1)の出力
を選択する。

【０１０７】かくして、セレクタ７１_#k、７３_#k、７５
_#k、７７_#kは、ＡＣＳ回路４０の比較器４５、４６から
の比較結果、すなわち選択したパスを示す情報に基づい
て、ＡＣＳ回路４０のセレクタ４７、４８で選択された
パスの各ブランチに対応した変調系列ｘ_tの値を選択
し、メモリ７２_#k、７４_#k、７６_#k、７８_#kは、これら
の値を記憶する。そして、Ｋ段目のメモリ７２_#K、７４
_#Kから、選択されたパスに対応した変調系列ｘ_tが、奇
数サンプルデータｚ_tと偶数サンプルデータｚ_tとに分
離されて出力される。

【０１０８】Ｐ／Ｓ変換器８１は、パラレルデータとし
て供給される再生された変調系列ｘ _tをシリアルデータ
に変換し、端子２ａを介し、復号データとして復調器
（例えば図１に示す復調器１１０）に出力する。なお、
Ｋ段目のメモリ７６_#K、７８_#Kからも同じデータが出力
されるので、これらのメモリ７６_#K、７８_#Kの出力をＰ
／Ｓ変換器でシリアルデータに変換し、復号データとし
て出力するようにしてもよい。また、ＡＣＳ回路４０と
ステートメトリック記憶部５０の間にＡＣＳ回路４０で
求められたステートメトリックを正規化する正規化部を
設けるようにしてもい。なお、上述の実施例では、ト
レリス線図における状態の数Ｍを２とし、始点と終点の
間隔Ｎを２としているが、本発明では、これらの値は２
に限定されるものではなく、例えば始点と終点の間隔Ｎ
をさらに大きくすると、ビタビ復号の動作速度を制限す
るループ内のＡＣＳ回路４０に許容される処理時間を、
従来の装置に比してＮ倍に長くすることができ、情報を
伝送する伝送速度を速くすることができる。

【０１０９】

【発明の効果】以上の説明で明かなように、本発明で
は、始点のＭ個の状態のうちの１つの状態と、始点から
Ｎ標本点離れた終点のＭ個の状態のうちの１つの状態と
をそれぞれ連結する複数の部分的なパスの尤度を算出す
ると共に、各部分的なパスの尤度に基づいて、尤度が最
も高い部分的なパスを検出する処理を、始点と終点の全
て状態のＭ×Ｍ個の組合せで繰り返す。この検出された
Ｍ×Ｍ個の部分的なパスの尤度と、始点のそれぞれの状
態に到るＭ個のパスの尤度とを対応する始点の状態毎に
加算して、終点のそれぞれの状態に到るＭ×Ｍ個のパス
の尤度を求めると共に、各パスの尤度に基づいて、尤度
が最も高いパスを終点のＭ個の状態毎に検出する。そし
て、検出されたＭ個のパスの尤度を記憶すると共に、記
憶した各パスの尤度を、Ｎ標本点後に始点のそれぞれの
状態に到るＭ個のパスの尤度とする。これにより、本発
明では、ビタビ復号の動作速度を制限するループ内の演
算処理に許容される時間を、従来の装置に比してＮ倍に
することができ、従来の装置に比して情報を伝送する伝
送速度を速くすることができる。

【図面の簡単な説明】

【図１】本発明を適用したビタビ復号装置の具体的な構
成を示すブロック図である。

【図２】上記ビタビ復号装置を構成するブランチメトリ
ック計算部、ＡＣＳ回路、ステートメトリック記憶部の
具体的な回路構成を示すブロック図である。

【図３】上記ビタビ復号装置を構成するパスメモリの具
体的な回路構成を示すブロック図である。

【図４】ビタビ復号を適用したデータ記録再生装置の構
成を示すブロック図である。

【図５】パーシャルレスポンス（１，１）を適用した伝
送システムの等価回路を示すブロック図である。

【図６】上記伝送システムの動作を説明するための状態
遷移図である。

【図７】上記伝送システムの動作を説明するためのトレ
リス線図である。

【図８】パーシャルレスポンス（１，１）を適用したデ
ータ記録再生装置の動作を説明するためのトレリス線図
である。

【図９】上記データ記録再生装置を構成するビタビ復号
器の構成を示すブロック図である。

【図１０】上記ビタビ復号器を構成するブランチメトリ
ック計算部、ＡＣＳ回路、ステートメトリック記録部の
回路構成を示すブロック図である。

【図１１】上記ビタビ復号器を構成するパスメモリの回
路構成を示すブロック図である。

【符号の説明】

１０ブランチメトリック計算部１１ａ、１１ｂ、１２ａ、１２ｂ、１３ａ、１３ｂ、１
４ａ、１４ｂ演算回路２０ＡＣＳ回路２１、２２、２３、２４、２５、２６、２７、２８加
算器３１、３２、３３、３４比較器３５、３６、３７、３８セレクタ４０ＡＣＳ回路４１、４２、４３、４４加算器４５、４６比較器４７、４８セレクタ５０ステートメトリック記憶部５１、５２メモリ６０パスメモリ７１_#k、７３_#k、７５_#k、７７_#k セレクタ７２_#k、７４_#k、７６_#k、７８_#k メモリ

Claims

【特許請求の範囲】

【請求項１】ビタビ復号の系を表現するＭ（Ｍ＞１：
整数）個の状態の時間的な推移を表すトレリス線図にお
いて、始点のＭ個の状態のうちの１つの状態と、上記始
点からＮ（Ｎ＞１：整数）標本点離れた終点のＭ個の状
態のうちの１つの状態とをそれぞれ連結する複数の部分
的なパスの尤度を算出すると共に、該各部分的なパスの
尤度に基づいて、尤度が最も高い部分的なパスを検出す
る処理を、上記始点と終点の全て状態のＭ×Ｍ個の組合
せで繰り返す第１の工程と、上記始点のそれぞれの状態に到るＭ個のパスの尤度と、
上記第１の工程で検出されたＭ×Ｍ個の部分的なパスの
尤度とを対応する始点の状態毎に加算して、上記終点の
それぞれの状態に到るＭ×Ｍ個のパスの尤度を求めると
共に、該各パスの尤度に基づいて、尤度が最も高いパス
を上記終点のＭ個の状態毎に検出する第２の工程と、該第２の工程で検出されたＭ個のパスの尤度を記憶する
と共に、該記憶した各パスの尤度を、Ｎ標本点後に上記
始点のそれぞれの状態に到るＭ個のパスの尤度とする第
３の工程を有することを特徴とするビタビ復号方法。
【請求項２】前記第１の工程は、互いにＮ標本点離れた始点と終点間において、互いに隣
接した標本点のＭ個の状態とＭ個の状態をそれぞれ連結
する複数の枝の尤度を算出する第４の工程と、該第４の工程で算出された各枝の尤度を加算して、前記
複数の部分的なパスの尤度を求める第５の工程と、該第４の工程で求められた各部分的なパスの尤度を比較
して、尤度が最も高い部分的なパスを、前記終点のＭ個
の状態毎に検出する第６の工程からなることを特徴とす
る請求項１記載のビタビ復号方法。
【請求項３】前記始点又は終点の状態の数Ｍを２と
し、前記始点と終点の間隔Ｎを２とすることを特徴とす
る請求項１又は２記載のビタビ復号方法。
【請求項４】ビタビ復号の系を表現するＭ（Ｍ＞１：
整数）個の状態の時間的な推移を表すトレリス線図にお
いて、始点のＭ個の状態のうちの１つの状態と、上記始
点からＮ（Ｎ＞１：整数）標本点離れた終点のＭ個の状
態のうちの１つの状態とをそれぞれ連結する複数の部分
的なパスの尤度を算出すると共に、該各部分的なパスの
尤度に基づいて、尤度が最も高い部分的なパスを、上記
始点と終点の全ての状態のＭ×Ｍ個の組合せで求める第
１の演算手段と、上記始点のそれぞれの状態に到るＭ個のパスの尤度と、
上記第１の演算手段から供給されるＭ×Ｍ個の部分的な
パスの尤度とを対応する始点の状態毎に加算して、上記
終点のそれぞれの状態に到るＭ×Ｍ個のパスの尤度を求
めると共に、該各パスの尤度に基づいて、尤度が最も高
いパスを上記終点のＭ個の状態毎に検出する第２の演算
手段と、該第２の演算手段からのＭ個のパスの尤度を記憶すると
共に、該記憶した各パスの尤度を、Ｎ標本点後に上記始
点のそれぞれの状態に到るＭ個のパスの尤度として、上
記第２の演算手段に供給する記憶手段とを備えることを
特徴とするビタビ復号装置。
【請求項５】前記第１の演算手段は、互いにＮ標本点離れた始点と終点間において、互いに隣
接した標本点のＭ個の状態とＭ個の状態をそれぞれ連結
する枝の尤度を算出する枝尤度計算手段と、該枝尤度計算手段からの各枝の尤度を加算して、前記Ｍ
×Ｍ個の部分的なパスの尤度を求める部分パス尤度計算
手段と、該部分パス尤度計算手段からの部分的なパスの尤度を比
較して、尤度が最も高い部分的なパスを、前記終点のＭ
個の状態毎に検出する比較手段とを備えることを特徴と
する請求項４記載のビタビ復号装置。
【請求項６】前記始点又は終点の状態の数Ｍを２と
し、前記始点と終点の間隔Ｎを２とすることを特徴とす
る請求項４又は５記載のビタビ復号装置。