JP3196835B2 - ビタビ復号法及びビタビ復号器 - Google Patents
ビタビ復号法及びビタビ復号器Info
- Publication number
- JP3196835B2 JP3196835B2 JP20359098A JP20359098A JP3196835B2 JP 3196835 B2 JP3196835 B2 JP 3196835B2 JP 20359098 A JP20359098 A JP 20359098A JP 20359098 A JP20359098 A JP 20359098A JP 3196835 B2 JP3196835 B2 JP 3196835B2
- Authority
- JP
- Japan
- Prior art keywords
- data
- path
- metric
- selector
- maximum likelihood
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Expired - Fee Related
Links
Classifications
-
- H—ELECTRICITY
- H03—ELECTRONIC CIRCUITRY
- H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
- H03M13/00—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes
- H03M13/37—Decoding methods or techniques, not specific to the particular type of coding provided for in groups H03M13/03 - H03M13/35
- H03M13/39—Sequence estimation, i.e. using statistical methods for the reconstruction of the original codes
- H03M13/3961—Arrangements of methods for branch or transition metric calculation
-
- H—ELECTRICITY
- H03—ELECTRONIC CIRCUITRY
- H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
- H03M13/00—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes
- H03M13/37—Decoding methods or techniques, not specific to the particular type of coding provided for in groups H03M13/03 - H03M13/35
- H03M13/39—Sequence estimation, i.e. using statistical methods for the reconstruction of the original codes
- H03M13/41—Sequence estimation, i.e. using statistical methods for the reconstruction of the original codes using the Viterbi algorithm or Viterbi processors
- H03M13/4107—Sequence estimation, i.e. using statistical methods for the reconstruction of the original codes using the Viterbi algorithm or Viterbi processors implementing add, compare, select [ACS] operations
-
- H—ELECTRICITY
- H03—ELECTRONIC CIRCUITRY
- H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
- H03M13/00—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes
- H03M13/37—Decoding methods or techniques, not specific to the particular type of coding provided for in groups H03M13/03 - H03M13/35
- H03M13/39—Sequence estimation, i.e. using statistical methods for the reconstruction of the original codes
- H03M13/41—Sequence estimation, i.e. using statistical methods for the reconstruction of the original codes using the Viterbi algorithm or Viterbi processors
- H03M13/4161—Sequence estimation, i.e. using statistical methods for the reconstruction of the original codes using the Viterbi algorithm or Viterbi processors implementing path management
- H03M13/4169—Sequence estimation, i.e. using statistical methods for the reconstruction of the original codes using the Viterbi algorithm or Viterbi processors implementing path management using traceback
Landscapes
- Physics & Mathematics (AREA)
- Probability & Statistics with Applications (AREA)
- Engineering & Computer Science (AREA)
- Theoretical Computer Science (AREA)
- Error Detection And Correction (AREA)
Description
【０００１】
【発明の属する技術分野】本発明は、ビタビ復号法及び
ビタビ復号器に関する。
ビタビ復号器に関する。
【０００２】
【従来の技術】デジタル伝送における誤り訂正法とし
て、畳み込み符号の最尤復号法の一例であるビタビ復号
法（例えば、G. D. Forney Jr., "The Viterbi algorit
hm", Proceeding of IEEE, vol. 61, pp. 268-278, Ma
r. 1973を参照）があり、広く使用されている。ビタビ
復号法による復号器をビタビ復号器という。
て、畳み込み符号の最尤復号法の一例であるビタビ復号
法（例えば、G. D. Forney Jr., "The Viterbi algorit
hm", Proceeding of IEEE, vol. 61, pp. 268-278, Ma
r. 1973を参照）があり、広く使用されている。ビタビ
復号法による復号器をビタビ復号器という。
【０００３】ところで、デジタル伝送の一形態として、
送信すべきデータを所定のビット長（ワード長）のパケ
ットに分解し、パケットを単位として伝送するパケット
通信がある。パケット通信では、順番に送出された２つ
のパケットが受信側で受信されるときのパケット間の時
間間隔は、一般に不定である。衛星通信や携帯電話のよ
うな移動体通信の分野においては、パケット通信用の誤
り訂正に、ビタビ復号器を使用している。以下、従来の
ビタビ復号器をパケット動作で使用した場合の処理につ
いて検討する。図９は、パケットデータ処理用の従来の
ビタビ復号器の構成を示すブロック図である。ここで
は、ビタビ復号器に入力する受信軟判定Ｐデータ、受信
軟判定Ｑデータは、それぞれ３ビットであるとする。
送信すべきデータを所定のビット長（ワード長）のパケ
ットに分解し、パケットを単位として伝送するパケット
通信がある。パケット通信では、順番に送出された２つ
のパケットが受信側で受信されるときのパケット間の時
間間隔は、一般に不定である。衛星通信や携帯電話のよ
うな移動体通信の分野においては、パケット通信用の誤
り訂正に、ビタビ復号器を使用している。以下、従来の
ビタビ復号器をパケット動作で使用した場合の処理につ
いて検討する。図９は、パケットデータ処理用の従来の
ビタビ復号器の構成を示すブロック図である。ここで
は、ビタビ復号器に入力する受信軟判定Ｐデータ、受信
軟判定Ｑデータは、それぞれ３ビットであるとする。
【０００４】図９に示す従来のビタビ復号器５９は、受
信軟判定Ｐデータ及び受信軟判定Ｑデータをそれぞれ入
力する入力端子１，２と、入力した受信軟判定Ｐデータ
及び受信軟判定Ｑデータの組と“０００”データの組と
を切替えるセレクタ３と、セレクタ３の出力と各送信デ
ータを比べてセレクタ３の出力の確からしさを求めるブ
ランチメトリック生成器４と、生き残りパスの累積メト
リックを格納するパスメトリックレジスタ６と、ブラン
チメトリック生成器４の出力とパスメトリックレジスタ
６の出力に基づいてシンボル時刻ごとにｎ状態（ｎは２
以上の整数）のパスメトリック値とｎ状態の選択情報
（枝値）とを出力するＡＣＳ回路５と、シンボル時刻ご
とにＡＣＳ回路５が出力するｎ状態の選択情報を格納す
るパスメモリ７と、シンボル時刻ごとにＡＣＳ回路５が
出力するｎ状態のパスメトリック値の中から最大のパス
メトリックを持つ状態番号を求める最尤パス状態検出器
９と、パスメモリ７内のデータに対してトレースバック
処理を行い、得られた結果を復号データとして出力端子
１６から出力するトレースバック回路４８と、このビタ
ビ復号器５９全体の制御を行う制御回路５０と、を備え
ている。セレクタ３に入力する“０００”データは、パ
ケットデータが最後まで入力した後に、そのパケットデ
ータを復号しつつ、ビタビ復号器５９内の各回路をパケ
ットデータが入力する前の状態に戻すためデータ（ター
ミナルデータ）であり、ここでは３ビットの軟判定デー
タがビタビ復号器５９に入力することなっているから、
３ビットの“０”（２進表示）からなるデータである。
信軟判定Ｐデータ及び受信軟判定Ｑデータをそれぞれ入
力する入力端子１，２と、入力した受信軟判定Ｐデータ
及び受信軟判定Ｑデータの組と“０００”データの組と
を切替えるセレクタ３と、セレクタ３の出力と各送信デ
ータを比べてセレクタ３の出力の確からしさを求めるブ
ランチメトリック生成器４と、生き残りパスの累積メト
リックを格納するパスメトリックレジスタ６と、ブラン
チメトリック生成器４の出力とパスメトリックレジスタ
６の出力に基づいてシンボル時刻ごとにｎ状態（ｎは２
以上の整数）のパスメトリック値とｎ状態の選択情報
（枝値）とを出力するＡＣＳ回路５と、シンボル時刻ご
とにＡＣＳ回路５が出力するｎ状態の選択情報を格納す
るパスメモリ７と、シンボル時刻ごとにＡＣＳ回路５が
出力するｎ状態のパスメトリック値の中から最大のパス
メトリックを持つ状態番号を求める最尤パス状態検出器
９と、パスメモリ７内のデータに対してトレースバック
処理を行い、得られた結果を復号データとして出力端子
１６から出力するトレースバック回路４８と、このビタ
ビ復号器５９全体の制御を行う制御回路５０と、を備え
ている。セレクタ３に入力する“０００”データは、パ
ケットデータが最後まで入力した後に、そのパケットデ
ータを復号しつつ、ビタビ復号器５９内の各回路をパケ
ットデータが入力する前の状態に戻すためデータ（ター
ミナルデータ）であり、ここでは３ビットの軟判定デー
タがビタビ復号器５９に入力することなっているから、
３ビットの“０”（２進表示）からなるデータである。
【０００５】ここでＡＣＳ回路５は、シンボル時刻ごと
に、トレリス線図にしたがって、ブランチメトリック生
成器４の出力とパスメトリックレジスタ６の出力とを加
算(Add)、比較(Compare)、選択(Select)することによ
り、比較して選択したｎ状態のパスメトリック値とｎ状
態の選択情報とを出力する。また、トレースバック回路
４８は、パスメモリ制御信号をパスメモリ７に対して出
力しパスメモリ７からデータを読み出すことにより、
（ｇ−ｆ）シンボル時刻ごとに、最尤パス状態検出器９
の出力の状態番号からｇシンボル時刻分だけパスメモリ
７を過去に向かってたどっていき、最後に到達したビッ
トから（ｇ−ｆ）ビットを復号データとして出力する。
に、トレリス線図にしたがって、ブランチメトリック生
成器４の出力とパスメトリックレジスタ６の出力とを加
算(Add)、比較(Compare)、選択(Select)することによ
り、比較して選択したｎ状態のパスメトリック値とｎ状
態の選択情報とを出力する。また、トレースバック回路
４８は、パスメモリ制御信号をパスメモリ７に対して出
力しパスメモリ７からデータを読み出すことにより、
（ｇ−ｆ）シンボル時刻ごとに、最尤パス状態検出器９
の出力の状態番号からｇシンボル時刻分だけパスメモリ
７を過去に向かってたどっていき、最後に到達したビッ
トから（ｇ−ｆ）ビットを復号データとして出力する。
【０００６】さらにこのビタビ復号器５９には、受信ク
ロックを入力してブランチメトリック生成器４、ＡＣＳ
回路５、パスメトリックレジスタ６、パスメモリ７及び
トレースバック回路４８に供給するための入力端子５２
と、パケットデータ開始パルスを入力して制御回路５０
に供給する入力端子１４と、パケットデータ終了パルス
を入力しれ制御回路５０に供給する入力端子１５と、が
設けられている。制御回路５０は、セレクタ３に対して
セレクト信号を出力し、パスメトリックレジスタ６にパ
スメトリックセット信号を出力し、トレースバック回路
４８にトレースバック開始信号を出力するものである。
さらに制御回路５０は、パケットデータ開始パルスによ
って、パスメトリックレジスタ６の状態番号“０”に高
いパスメトリックを与え、他の状態番号には、すべて同
じ低いパスメトリック（例えば、０）を与えてビタビ復
号を実行させ、パケットデータ終了パルスが入力される
と、セレクタ３の出力を“０００”データの組に切り替
え、ビタビ復号を実行しながら、最尤パス状態検出器９
の出力が状態番号“０”になると、ブランチメトリック
生成器４、ＡＣＳ回路５、パスメトリックレジスタ６及
び最尤パス状態検出器９の動作を停止させ、状態番号
“０”の最尤パスに連なる系列からトレースバック回路
４８にトレースバックを実行させるように構成されてい
る。
ロックを入力してブランチメトリック生成器４、ＡＣＳ
回路５、パスメトリックレジスタ６、パスメモリ７及び
トレースバック回路４８に供給するための入力端子５２
と、パケットデータ開始パルスを入力して制御回路５０
に供給する入力端子１４と、パケットデータ終了パルス
を入力しれ制御回路５０に供給する入力端子１５と、が
設けられている。制御回路５０は、セレクタ３に対して
セレクト信号を出力し、パスメトリックレジスタ６にパ
スメトリックセット信号を出力し、トレースバック回路
４８にトレースバック開始信号を出力するものである。
さらに制御回路５０は、パケットデータ開始パルスによ
って、パスメトリックレジスタ６の状態番号“０”に高
いパスメトリックを与え、他の状態番号には、すべて同
じ低いパスメトリック（例えば、０）を与えてビタビ復
号を実行させ、パケットデータ終了パルスが入力される
と、セレクタ３の出力を“０００”データの組に切り替
え、ビタビ復号を実行しながら、最尤パス状態検出器９
の出力が状態番号“０”になると、ブランチメトリック
生成器４、ＡＣＳ回路５、パスメトリックレジスタ６及
び最尤パス状態検出器９の動作を停止させ、状態番号
“０”の最尤パスに連なる系列からトレースバック回路
４８にトレースバックを実行させるように構成されてい
る。
【０００７】次に、この従来のパケットデータ処理用の
ビタビ復号器５９の動作について説明する。ここでは、
説明を分かりやすくするために、符号化率Ｒ＝１／２、
拘束長Ｋ＝３の場合について考える。
ビタビ復号器５９の動作について説明する。ここでは、
説明を分かりやすくするために、符号化率Ｒ＝１／２、
拘束長Ｋ＝３の場合について考える。
【０００８】まず、このビタビ復号器と対になって使用
される送信側の符号器について説明する。送信側では、
図２に示すような３段のシフトレジスタ２０と排他的論
理和（ＥｘＯＲ）ゲート２１，２２で構成される畳み込
み符号器２３により符号化される。シンボル時刻ごとに
入力データ系列が入力端子２４からシフトレジスタ２０
に入力し、シフトレジスタ２０の指定された各段の出力
が排他的論理和ゲート２１，２２で論理処理され、出力
端子２５，２６から、それぞれ、Ｐデータ、Ｑデータと
して出力される。シフトレジスタ２０は、リセット信号
を与えることによってリセットされるように構成されて
いる。
される送信側の符号器について説明する。送信側では、
図２に示すような３段のシフトレジスタ２０と排他的論
理和（ＥｘＯＲ）ゲート２１，２２で構成される畳み込
み符号器２３により符号化される。シンボル時刻ごとに
入力データ系列が入力端子２４からシフトレジスタ２０
に入力し、シフトレジスタ２０の指定された各段の出力
が排他的論理和ゲート２１，２２で論理処理され、出力
端子２５，２６から、それぞれ、Ｐデータ、Ｑデータと
して出力される。シフトレジスタ２０は、リセット信号
を与えることによってリセットされるように構成されて
いる。
【０００９】図３に示すｄ個のパケットデータｉ1，
ｉ2，…，ｉdを畳み込み符号化する場合、一般的に、デ
ータｉ1が入力する前に畳み込み符号器２３をリセット
する。つまり、シフトレジスタ２０の各段の中身を
“０”にする。また、最後のパケットデータｉdがシフ
トレジスタ２０に入力した後に、（拘束長−１）個の
“０”データを入力する。ここでは、拘束長が３なの
で、２個の“０”データを入力する。図３では、畳み込
み符号器２３のＰデータ及びＱデータ出力を、それぞ
れ、Ｐ1，Ｐ2，…，Ｐd，Ｐd+1，Ｐd+2及びＱ1，Ｑ2，
…，Ｑd，Ｑd+1，Ｑd+2と表している。
ｉ2，…，ｉdを畳み込み符号化する場合、一般的に、デ
ータｉ1が入力する前に畳み込み符号器２３をリセット
する。つまり、シフトレジスタ２０の各段の中身を
“０”にする。また、最後のパケットデータｉdがシフ
トレジスタ２０に入力した後に、（拘束長−１）個の
“０”データを入力する。ここでは、拘束長が３なの
で、２個の“０”データを入力する。図３では、畳み込
み符号器２３のＰデータ及びＱデータ出力を、それぞ
れ、Ｐ1，Ｐ2，…，Ｐd，Ｐd+1，Ｐd+2及びＱ1，Ｑ2，
…，Ｑd，Ｑd+1，Ｑd+2と表している。
【００１０】畳み込み符号器２３の出力、すなわちＰデ
ータ及びＱデータは、伝送され、図９に示すビタビ復号
器５９に入力する。その際、Ｐデータ及びＱデータが伝
送路で生じた雑音よりどのように変わっているかをビタ
ビ復号器５９に伝えるために、軟判定表現されている。
図４は、“０”，“１”に対してそれぞれ３ビットで軟
判定表現を行ったものを示している。
ータ及びＱデータは、伝送され、図９に示すビタビ復号
器５９に入力する。その際、Ｐデータ及びＱデータが伝
送路で生じた雑音よりどのように変わっているかをビタ
ビ復号器５９に伝えるために、軟判定表現されている。
図４は、“０”，“１”に対してそれぞれ３ビットで軟
判定表現を行ったものを示している。
【００１１】次に、図９に示す従来のビタビ復号器５９
の動作について説明する。
の動作について説明する。
【００１２】図５は、畳み込み符号器２３をトレリス表
現した図である。図示左側の｛０,０｝，｛０,１｝，
｛１,０｝及び｛１,１｝は、｛ａ,ｂ｝すなわち畳み込
み符号器２３のシフトレジスタ２０の初段及び２段目の
内容を示したものである。ここでａ，ｂは、それぞれ、
シフトレジスタ２０の初段と２段目の各１ビットの内容
を表わす変数である。また、｛０,０｝，｛０,１｝，
｛１,０｝及び｛１,１｝の右側にある矢印の横の値は、
（ａ×２＋ｂ）を計算した値であり、今後、この値を状
態番号と呼ぶ。
現した図である。図示左側の｛０,０｝，｛０,１｝，
｛１,０｝及び｛１,１｝は、｛ａ,ｂ｝すなわち畳み込
み符号器２３のシフトレジスタ２０の初段及び２段目の
内容を示したものである。ここでａ，ｂは、それぞれ、
シフトレジスタ２０の初段と２段目の各１ビットの内容
を表わす変数である。また、｛０,０｝，｛０,１｝，
｛１,０｝及び｛１,１｝の右側にある矢印の横の値は、
（ａ×２＋ｂ）を計算した値であり、今後、この値を状
態番号と呼ぶ。
【００１３】図５に示すトレリス図を簡単に説明する
と、状態番号０の時、畳み込み符号器２３に次に入力さ
れるデータが“０”の場合には、状態番号０に遷移し、
Ｐデータ及びＱデータの出力値として“００”（状態番
号０から状態番号０へ遷移する矢印の上に示した値）を
出力する。状態番号が０で、入力されるデータが“１”
の場合には、状態番号１に遷移し、Ｐデータ及びＱデー
タの出力値として“１１”を出力する。他の状態番号の
場合においても、畳み込み符号器２３に入力するデータ
に応じて遷移先が決まる。それらの時のＰデータ及びＱ
データの出力値が、遷移を表わす矢印に付記されてい
る。ビタビ復号器５９は、このトレリス表現された図に
したがって、復号処理を実行する。
と、状態番号０の時、畳み込み符号器２３に次に入力さ
れるデータが“０”の場合には、状態番号０に遷移し、
Ｐデータ及びＱデータの出力値として“００”（状態番
号０から状態番号０へ遷移する矢印の上に示した値）を
出力する。状態番号が０で、入力されるデータが“１”
の場合には、状態番号１に遷移し、Ｐデータ及びＱデー
タの出力値として“１１”を出力する。他の状態番号の
場合においても、畳み込み符号器２３に入力するデータ
に応じて遷移先が決まる。それらの時のＰデータ及びＱ
データの出力値が、遷移を表わす矢印に付記されてい
る。ビタビ復号器５９は、このトレリス表現された図に
したがって、復号処理を実行する。
【００１４】ビタビ復号器５９においてパケット開始パ
ルスが制御回路５０に入力すると、制御回路５０は、パ
スメトリックセット信号をパスメトリックレジスタ６に
出力する。パスメトリックレジスタ６は、この信号によ
り、状態番号０のレジスタに高いメトリック（例えば、
６４）を与え、状態番号１，２，３のレジスタには、メ
トリック０を与える。このとき制御回路５０は、セレク
タ３が受信軟判定ＰデータＱ及びデータの組を選択して
出力するように、セレクタ３に対するセレクト信号を設
定している。
ルスが制御回路５０に入力すると、制御回路５０は、パ
スメトリックセット信号をパスメトリックレジスタ６に
出力する。パスメトリックレジスタ６は、この信号によ
り、状態番号０のレジスタに高いメトリック（例えば、
６４）を与え、状態番号１，２，３のレジスタには、メ
トリック０を与える。このとき制御回路５０は、セレク
タ３が受信軟判定ＰデータＱ及びデータの組を選択して
出力するように、セレクタ３に対するセレクト信号を設
定している。
【００１５】まず、Ｐ1，Ｑ1に対する軟判定データが、
入力端子１，２よりセレクタ３を通ってブランチメトリ
ック生成器４に入力すると、ブランチメトリック生成器
４は、（軟判定Ｐ1,軟判定Ｑ1）に対して、その時の送
信データの組（Ｐ,Ｑ）が（０,０），（１,０），（０,
１），（１,１）であったとした場合の確からしさ、す
なわちブランチメトリックを各々算出する。（軟判定Ｐ
1,軟判定Ｑ1）に対して、送信データの組が（０,０）で
あるときのブランチメトリックをλ0、送信データの組
が（１,０）の時のブランチメトリックをλ1、送信デー
タの組が（０,１）の時のブランチメトリックをλ2、送
信データの組が（１,１）の時のブランチメトリックを
λ3とする。ブランチメトリック生成器４は、このλ0，
λ1，λ2，λ3をＡＣＳ回路５に出力する。このとき、
図６に示すように、時刻ｍ0での各状態番号０〜４のパ
スメトリック値を、それぞれ、Γ0(ｍ0)，Γ1(ｍ0)，Γ
2(ｍ0)，Γ3(ｍ0)とする。実際には、メトリックセット
したばかりなので、Γ0(ｍ0)＝６４，Γ1(ｍ0)＝０，Γ
2(ｍ0)＝０，Γ3(ｍ0)＝０となっている。
入力端子１，２よりセレクタ３を通ってブランチメトリ
ック生成器４に入力すると、ブランチメトリック生成器
４は、（軟判定Ｐ1,軟判定Ｑ1）に対して、その時の送
信データの組（Ｐ,Ｑ）が（０,０），（１,０），（０,
１），（１,１）であったとした場合の確からしさ、す
なわちブランチメトリックを各々算出する。（軟判定Ｐ
1,軟判定Ｑ1）に対して、送信データの組が（０,０）で
あるときのブランチメトリックをλ0、送信データの組
が（１,０）の時のブランチメトリックをλ1、送信デー
タの組が（０,１）の時のブランチメトリックをλ2、送
信データの組が（１,１）の時のブランチメトリックを
λ3とする。ブランチメトリック生成器４は、このλ0，
λ1，λ2，λ3をＡＣＳ回路５に出力する。このとき、
図６に示すように、時刻ｍ0での各状態番号０〜４のパ
スメトリック値を、それぞれ、Γ0(ｍ0)，Γ1(ｍ0)，Γ
2(ｍ0)，Γ3(ｍ0)とする。実際には、メトリックセット
したばかりなので、Γ0(ｍ0)＝６４，Γ1(ｍ0)＝０，Γ
2(ｍ0)＝０，Γ3(ｍ0)＝０となっている。
【００１６】パスメトリックレジスタ６は、このΓ0(ｍ
0)，Γ1(ｍ0)，Γ2(ｍ0)，Γ3(ｍ0)をＡＣＳ回路５に出
力し、ＡＣＳ回路５は、図６に示すトレリス表現に基づ
いて、演算を実行する。以下、この演算について説明す
る。
0)，Γ1(ｍ0)，Γ2(ｍ0)，Γ3(ｍ0)をＡＣＳ回路５に出
力し、ＡＣＳ回路５は、図６に示すトレリス表現に基づ
いて、演算を実行する。以下、この演算について説明す
る。
【００１７】時刻ｍ1において状態番号０に合流してい
る遷移は、状態番号０と状態番号２からのものである。
状態番号０からの遷移のときの畳み込み符号器からの出
力データは“００”なのでそのときのブランチメトリッ
クはλ0となり、状態番号２からの遷移のときの畳み込
み符号器からの出力データは“１１”なのでそのときの
ブランチメトリックはλ3となり、時刻ｍ0での状態番号
０と状態番号２のパスメトリック値がそれぞれΓ
0(ｍ0)，Γ2(ｍ0)なので、それぞれ、Γ0(ｍ0)＋λ0，
Γ2(ｍ0)＋λ3の演算を行い、大きい方を時刻ｍ1の状態
番号０のパスメトリック値Γ0(ｍ1)として、パスメトリ
ックレジスタ６に格納する。同時に、選択された方の枝
値（図６で実線で示した方が選ばれると“０”、破線で
示した方が選ばれると“１”である）を、時刻ｍ1の状
態番号０の枝値Ｓ0(ｍ1)として、パスメモリ７に格納す
る。以下、時刻ｍ1のパスメトリック値Γ1(ｍ1)，Γ
2(ｍ1)，Γ3(ｍ1)、枝値Ｓ1(ｍ1)，Ｓ2(ｍ1)，Ｓ3(ｍ1)
を同様にして求め、それぞれ、パスメトリックレジスタ
６、パスメモリ７に格納する。ここでパスメモリ７は、
（ｆ＋ｇ）時刻分の枝値情報が格納できるメモリ容量を
持つものとする。また、ＡＣＳ回路５は、時刻ｍ1の求
めたパスメトリック値Γ0(ｍ1)，Γ1(ｍ1)，Γ2(ｍ1)，
Γ3(ｍ1)をパスメトリックレジスタ６に出力すると同時
に、最尤パス状態検出器９にも出力する。これで、時刻
ｍ1での一連の処理が終了する。以後、この一連の処理
のことをＡＣＳ処理と呼ぶ。
る遷移は、状態番号０と状態番号２からのものである。
状態番号０からの遷移のときの畳み込み符号器からの出
力データは“００”なのでそのときのブランチメトリッ
クはλ0となり、状態番号２からの遷移のときの畳み込
み符号器からの出力データは“１１”なのでそのときの
ブランチメトリックはλ3となり、時刻ｍ0での状態番号
０と状態番号２のパスメトリック値がそれぞれΓ
0(ｍ0)，Γ2(ｍ0)なので、それぞれ、Γ0(ｍ0)＋λ0，
Γ2(ｍ0)＋λ3の演算を行い、大きい方を時刻ｍ1の状態
番号０のパスメトリック値Γ0(ｍ1)として、パスメトリ
ックレジスタ６に格納する。同時に、選択された方の枝
値（図６で実線で示した方が選ばれると“０”、破線で
示した方が選ばれると“１”である）を、時刻ｍ1の状
態番号０の枝値Ｓ0(ｍ1)として、パスメモリ７に格納す
る。以下、時刻ｍ1のパスメトリック値Γ1(ｍ1)，Γ
2(ｍ1)，Γ3(ｍ1)、枝値Ｓ1(ｍ1)，Ｓ2(ｍ1)，Ｓ3(ｍ1)
を同様にして求め、それぞれ、パスメトリックレジスタ
６、パスメモリ７に格納する。ここでパスメモリ７は、
（ｆ＋ｇ）時刻分の枝値情報が格納できるメモリ容量を
持つものとする。また、ＡＣＳ回路５は、時刻ｍ1の求
めたパスメトリック値Γ0(ｍ1)，Γ1(ｍ1)，Γ2(ｍ1)，
Γ3(ｍ1)をパスメトリックレジスタ６に出力すると同時
に、最尤パス状態検出器９にも出力する。これで、時刻
ｍ1での一連の処理が終了する。以後、この一連の処理
のことをＡＣＳ処理と呼ぶ。
【００１８】次の軟判定Ｐ2，Ｑ2データが入力すると、
上記のＡＣＳ処理を繰り返し実行する。時刻ｍgでの処
理が終わると、制御回路５０はトレースバック回路４８
及び最尤パス状態検出器９に対し、以下に述べるトレー
スバック処理を行うための命令を与える。その結果、最
尤パス状態検出器９は、最尤パスメトリック値Γ
0(ｍ g)，Γ1(ｍg)，Γ2(ｍg)，Γ3(ｍg)の中から、最大
のパスメトリック値を持つ状態番号をトレースバック回
路４８に出力する。時刻ｍgにおいて最大パスメトリッ
ク値をもつ状態番号が“２”であるとすると、トレース
バック回路４８は、時刻ｍgにおいて図７の実線で示す
最大パスメトリックをもつ状態番号２に連なるパスを、
パスメモリ７の内容を読み出してさかのぼっていく。ト
レースバック回路４８は、状態番号２に合流するパスが
状態番号１及び状態番号３のどちらであるかを、パスメ
モリ７から、時刻ｍfの状態番号２に格納されているデ
ータを読み出すことにより調べ、状態番号１からである
ことを知る。以下、同様の操作を繰り返し、時刻ｍ0ま
でパスをさかのぼり、最後にパスメモリ７より読み出し
たデータから（ｇ−ｆ）個分のデータ（時刻ｍ1から時
刻ｍg-fのデータ）を復号データとして、出力端子１６
から出力する。以下において、この処理をトレースバッ
ク処理と呼ぶ。受信クロックに同期してトレースバック
処理を実行しているときも、ＡＣＳ処理は受信クロック
に同期して実行されている。パスメモリ７は、ＡＣＳ処
理時の書き込み、トレースバック処理時の読み出しを同
時に行えるものとする。パスメモリ７は、図８に示すよ
うにリング構造になっていて、（ｇ＋ｆ）時刻分のメモ
リ容量になっているので、ＡＣＳ処理によって必要なデ
ータに上書きされることはない。このあと、（ｇ−ｆ）
時刻分のＡＣＳ処理を実行するごとに、トレースバック
処理を行い復号データを出力する。
上記のＡＣＳ処理を繰り返し実行する。時刻ｍgでの処
理が終わると、制御回路５０はトレースバック回路４８
及び最尤パス状態検出器９に対し、以下に述べるトレー
スバック処理を行うための命令を与える。その結果、最
尤パス状態検出器９は、最尤パスメトリック値Γ
0(ｍ g)，Γ1(ｍg)，Γ2(ｍg)，Γ3(ｍg)の中から、最大
のパスメトリック値を持つ状態番号をトレースバック回
路４８に出力する。時刻ｍgにおいて最大パスメトリッ
ク値をもつ状態番号が“２”であるとすると、トレース
バック回路４８は、時刻ｍgにおいて図７の実線で示す
最大パスメトリックをもつ状態番号２に連なるパスを、
パスメモリ７の内容を読み出してさかのぼっていく。ト
レースバック回路４８は、状態番号２に合流するパスが
状態番号１及び状態番号３のどちらであるかを、パスメ
モリ７から、時刻ｍfの状態番号２に格納されているデ
ータを読み出すことにより調べ、状態番号１からである
ことを知る。以下、同様の操作を繰り返し、時刻ｍ0ま
でパスをさかのぼり、最後にパスメモリ７より読み出し
たデータから（ｇ−ｆ）個分のデータ（時刻ｍ1から時
刻ｍg-fのデータ）を復号データとして、出力端子１６
から出力する。以下において、この処理をトレースバッ
ク処理と呼ぶ。受信クロックに同期してトレースバック
処理を実行しているときも、ＡＣＳ処理は受信クロック
に同期して実行されている。パスメモリ７は、ＡＣＳ処
理時の書き込み、トレースバック処理時の読み出しを同
時に行えるものとする。パスメモリ７は、図８に示すよ
うにリング構造になっていて、（ｇ＋ｆ）時刻分のメモ
リ容量になっているので、ＡＣＳ処理によって必要なデ
ータに上書きされることはない。このあと、（ｇ−ｆ）
時刻分のＡＣＳ処理を実行するごとに、トレースバック
処理を行い復号データを出力する。
【００１９】最後の軟判定Ｐd+2，Ｑd+2データが入力端
子１，２より入力し、ＡＣＳ処理が終了すると、パケッ
ト終了パルスが制御回路５０に入力する。このパルスの
入力により、制御回路５０は、“０００”データ（ター
ミナルデータ）の組がセレクタ３から出力されるように
セレクタ３に対するセレクト信号を設定する。その後、
受信クロックに同期して、“０００”データの組を、少
なくとも（ｆ＋ｇ）時刻分入力し続けなければならな
い。この間、出力端子１６からパケット最後のデータｉ
dを得るために、前述のＡＣＳ処理、トレースバック処
理を繰り返し実行することになる。“０００”データの
組と説明したが、これは、受信軟判定データとして３ビ
ットのものを使用しているからであって、受信軟判定デ
ータが例えば２ビットであれば、“００”データの組を
少なくとも（ｆ＋ｇ）時刻分入力し続けることになる。
子１，２より入力し、ＡＣＳ処理が終了すると、パケッ
ト終了パルスが制御回路５０に入力する。このパルスの
入力により、制御回路５０は、“０００”データ（ター
ミナルデータ）の組がセレクタ３から出力されるように
セレクタ３に対するセレクト信号を設定する。その後、
受信クロックに同期して、“０００”データの組を、少
なくとも（ｆ＋ｇ）時刻分入力し続けなければならな
い。この間、出力端子１６からパケット最後のデータｉ
dを得るために、前述のＡＣＳ処理、トレースバック処
理を繰り返し実行することになる。“０００”データの
組と説明したが、これは、受信軟判定データとして３ビ
ットのものを使用しているからであって、受信軟判定デ
ータが例えば２ビットであれば、“００”データの組を
少なくとも（ｆ＋ｇ）時刻分入力し続けることになる。
【００２０】“０００”データの組を入力し続けなけれ
ばならないことについては、例えば、Ｑｕａｌｃｏｍｍ
（クゥァルコム）社製の市販のビタビ復号器ＬＳＩ（品
名Ｑ１９００）のデータブックを参照すると、「パケッ
トデータ終了後、１０３個の“０００”データを入力し
なければならない。」と言う記述がある。
ばならないことについては、例えば、Ｑｕａｌｃｏｍｍ
（クゥァルコム）社製の市販のビタビ復号器ＬＳＩ（品
名Ｑ１９００）のデータブックを参照すると、「パケッ
トデータ終了後、１０３個の“０００”データを入力し
なければならない。」と言う記述がある。
【００２１】
【発明が解決しようとする課題】上述した従来のビタビ
復号器には、パケットデータの復号を行わせたときに、
パケットデータ終了後に、必ず、（ｇ＋ｆ）時刻分の
“０００”データ（ターミナルデータ）を入力しなけれ
ばならないので、次に入力するパケットデータは（ｇ＋
ｆ）時刻分待たされることになり、パケット伝送効率が
悪くなるという問題点がある。また、（ｇ＋ｆ）時刻分
待たずに次のパケットデータを入力すると、前のパケッ
トデータの最後の部分のデータが正しく復号されない。
復号器には、パケットデータの復号を行わせたときに、
パケットデータ終了後に、必ず、（ｇ＋ｆ）時刻分の
“０００”データ（ターミナルデータ）を入力しなけれ
ばならないので、次に入力するパケットデータは（ｇ＋
ｆ）時刻分待たされることになり、パケット伝送効率が
悪くなるという問題点がある。また、（ｇ＋ｆ）時刻分
待たずに次のパケットデータを入力すると、前のパケッ
トデータの最後の部分のデータが正しく復号されない。
【００２２】本発明の目的は、前のパケットデータに引
き続いてすぐに次のパケットデータがビタビ復号器に入
力する場合であっても、前のパケットデータの最後の部
分を正しく復号できるビタビ復号法及びビタビ復号器を
提供することにある。
き続いてすぐに次のパケットデータがビタビ復号器に入
力する場合であっても、前のパケットデータの最後の部
分を正しく復号できるビタビ復号法及びビタビ復号器を
提供することにある。
【００２３】
【課題を解決するための手段】本発明のビタビ復号法
は、受信データを入力し、受信データからブランチメト
リックを生成し、ブランチメトリックに対してＡＣＳ処
理を実行して複数状態のパスメトリック値及び選択情報
を生成し、選択情報を蓄積し、最大のパスメトリック値
に基づいて最尤パスを決定し、決定された最尤パスに基
づき、蓄積した選択情報を過去に向かってたどり復号デ
ータを出力するビタビ復号法において、受信データがパ
ケットデータであり、パケットデータの受信中は、当該
パケットデータに同期した第１の動作クロックに基づい
て、ブランチメトリックの生成、ＡＣＳ処理、最尤パス
の決定及び復号データの出力を実行し、パケットデータ
の受信が終了した時点で、第１の動作クロックより速い
第２の動作クロックに切り替え、第２の動作クロックに
基づいて、ブランチメトリックの生成、ＡＣＳ処理及び
最尤パスの決定を実行することを特徴とする。
は、受信データを入力し、受信データからブランチメト
リックを生成し、ブランチメトリックに対してＡＣＳ処
理を実行して複数状態のパスメトリック値及び選択情報
を生成し、選択情報を蓄積し、最大のパスメトリック値
に基づいて最尤パスを決定し、決定された最尤パスに基
づき、蓄積した選択情報を過去に向かってたどり復号デ
ータを出力するビタビ復号法において、受信データがパ
ケットデータであり、パケットデータの受信中は、当該
パケットデータに同期した第１の動作クロックに基づい
て、ブランチメトリックの生成、ＡＣＳ処理、最尤パス
の決定及び復号データの出力を実行し、パケットデータ
の受信が終了した時点で、第１の動作クロックより速い
第２の動作クロックに切り替え、第２の動作クロックに
基づいて、ブランチメトリックの生成、ＡＣＳ処理及び
最尤パスの決定を実行することを特徴とする。
【００２４】本発明の第１のビタビ復号器は、受信デー
タとターミナルデータを切り替えて出力する第１のセレ
クタと、第１のセレクタの出力が入力し入力データの確
からしさを求めるブランチメトリック生成器と、生き残
りパスの累積メトリックを格納するパスメトリックレジ
スタと、シンボル時刻ごとに、ブランチメトリック生成
器の出力とパスメトリックレジスタの出力に基づいてＡ
ＣＳ処理を実行し、複数状態のパスメトリック値及び選
択情報とを出力するＡＣＳ回路と、複数状態のパスメト
リック値から最大のパスメトリック値を有する最尤パス
を検出する最尤パス状態検出器と、シンボル時刻ごと
に、複数状態の選択情報を格納するパスメモリと、（ｇ
−ｆ）シンボル時刻ごとに、最尤パスに基づいて、ｇシ
ンボル時刻だけパスメモリを過去に向かってたどってい
き、最後に到達したビットから（ｇ−ｆ）ビットを復号
データとして出力するトレースバック回路と、を有し、
受信データがパケットデータであり、パケットデータの
受信中は第１のセレクタによってパケットデータを選択
するとともに、パケットデータに同期した第１の動作ク
ロックによってブランチメトリック生成器、ＡＣＳ回
路、パスメトリックレジスタ、パスメモリ及びトレース
バック回路を駆動し、パケットデータの受信が終了した
時点で第１のセレクタがターミナルデータ側に切り替え
られ、パケットデータの受信が終了した後は、第１の動
作クロックより速い第２の動作クロックによってブラン
チメトリック生成器、ＡＣＳ回路、パスメトリックレジ
スタ及びパスメモリを駆動する。
タとターミナルデータを切り替えて出力する第１のセレ
クタと、第１のセレクタの出力が入力し入力データの確
からしさを求めるブランチメトリック生成器と、生き残
りパスの累積メトリックを格納するパスメトリックレジ
スタと、シンボル時刻ごとに、ブランチメトリック生成
器の出力とパスメトリックレジスタの出力に基づいてＡ
ＣＳ処理を実行し、複数状態のパスメトリック値及び選
択情報とを出力するＡＣＳ回路と、複数状態のパスメト
リック値から最大のパスメトリック値を有する最尤パス
を検出する最尤パス状態検出器と、シンボル時刻ごと
に、複数状態の選択情報を格納するパスメモリと、（ｇ
−ｆ）シンボル時刻ごとに、最尤パスに基づいて、ｇシ
ンボル時刻だけパスメモリを過去に向かってたどってい
き、最後に到達したビットから（ｇ−ｆ）ビットを復号
データとして出力するトレースバック回路と、を有し、
受信データがパケットデータであり、パケットデータの
受信中は第１のセレクタによってパケットデータを選択
するとともに、パケットデータに同期した第１の動作ク
ロックによってブランチメトリック生成器、ＡＣＳ回
路、パスメトリックレジスタ、パスメモリ及びトレース
バック回路を駆動し、パケットデータの受信が終了した
時点で第１のセレクタがターミナルデータ側に切り替え
られ、パケットデータの受信が終了した後は、第１の動
作クロックより速い第２の動作クロックによってブラン
チメトリック生成器、ＡＣＳ回路、パスメトリックレジ
スタ及びパスメモリを駆動する。
【００２５】本発明の第２のビタビ復号器は、受信デー
タとターミナルデータを切り替えて出力するセレクタ
と、セレクタの出力が入力し入力データの確からしさを
求めるブランチメトリック生成器と、生き残りパスの累
積メトリックを格納するパスメトリックレジスタと、シ
ンボル時刻ごとに、ブランチメトリック生成器の出力と
パスメトリックレジスタの出力に基づいてＡＣＳ処理を
実行し、複数状態のパスメトリック値及び選択情報とを
出力するＡＣＳ回路と、複数状態のパスメトリック値か
ら最大のパスメトリック値を有する最尤パスを検出する
最尤パス状態検出器と、シンボル時刻ごとに、複数状態
の選択情報を格納するパスメモリと、（ｇ−ｆ）シンボ
ル時刻ごとに、最尤パスに基づいて、ｇシンボル時刻だ
けパスメモリを過去に向かってたどっていき、最後に到
達したビットから（ｇ−ｆ）ビットを復号データとして
出力するトレースバック回路と、を有するビタビ復号器
において、受信データがパケットデータであり、パケッ
トデータの受信中はセレクタによってパケットデータが
選択され、パケットデータの受信終了に応じてセレクタ
がターミナルデータ側に切り替わるともにブランチメト
リック生成器がターミナルデータに対応するブランチメ
トリックを設定し、パスメモリが、（２ｆ＋ｇ）時刻分
の選択情報を格納するリングメモリである。
タとターミナルデータを切り替えて出力するセレクタ
と、セレクタの出力が入力し入力データの確からしさを
求めるブランチメトリック生成器と、生き残りパスの累
積メトリックを格納するパスメトリックレジスタと、シ
ンボル時刻ごとに、ブランチメトリック生成器の出力と
パスメトリックレジスタの出力に基づいてＡＣＳ処理を
実行し、複数状態のパスメトリック値及び選択情報とを
出力するＡＣＳ回路と、複数状態のパスメトリック値か
ら最大のパスメトリック値を有する最尤パスを検出する
最尤パス状態検出器と、シンボル時刻ごとに、複数状態
の選択情報を格納するパスメモリと、（ｇ−ｆ）シンボ
ル時刻ごとに、最尤パスに基づいて、ｇシンボル時刻だ
けパスメモリを過去に向かってたどっていき、最後に到
達したビットから（ｇ−ｆ）ビットを復号データとして
出力するトレースバック回路と、を有するビタビ復号器
において、受信データがパケットデータであり、パケッ
トデータの受信中はセレクタによってパケットデータが
選択され、パケットデータの受信終了に応じてセレクタ
がターミナルデータ側に切り替わるともにブランチメト
リック生成器がターミナルデータに対応するブランチメ
トリックを設定し、パスメモリが、（２ｆ＋ｇ）時刻分
の選択情報を格納するリングメモリである。
【００２６】すなわち本発明では、パケットデータの最
後の部分をスムーズにあるいは迅速に処理し、すぐに次
のパケットデータがビタビ復号器に入力しても前のパケ
ットデータの最後の部分を正しく復号できるようにする
ため、パケットデータの入力が終わった時点でビタビ復
号器の動作クロックを速くし、これによってターミナル
データ分の処理時間を短縮する。本発明では、動作クロ
ックを速くする代わりに、リングメモリとして構成され
るパスメモリの容量を大きくし、それとともに、ターミ
ナルデータ（上述の従来の技術における“０００”デー
タなど）に対するブランチメトリックは予め分かってい
るからブランチメトリック生成器がそのブランチメトリ
ックを予め設定するようにしてもよい。
後の部分をスムーズにあるいは迅速に処理し、すぐに次
のパケットデータがビタビ復号器に入力しても前のパケ
ットデータの最後の部分を正しく復号できるようにする
ため、パケットデータの入力が終わった時点でビタビ復
号器の動作クロックを速くし、これによってターミナル
データ分の処理時間を短縮する。本発明では、動作クロ
ックを速くする代わりに、リングメモリとして構成され
るパスメモリの容量を大きくし、それとともに、ターミ
ナルデータ（上述の従来の技術における“０００”デー
タなど）に対するブランチメトリックは予め分かってい
るからブランチメトリック生成器がそのブランチメトリ
ックを予め設定するようにしてもよい。
【００２７】
【発明の実施の形態】次に、本発明の好ましい実施の形
態について、図面を参照して説明する。図１は、本発明
の実施の一形態のビタビ復号器の構成を示すブロック図
である。ここでは、ビタビ復号器に入力する受信軟判定
Ｐデータ、受信軟判定Ｑデータは、それぞれ３ビットで
あるとする。
態について、図面を参照して説明する。図１は、本発明
の実施の一形態のビタビ復号器の構成を示すブロック図
である。ここでは、ビタビ復号器に入力する受信軟判定
Ｐデータ、受信軟判定Ｑデータは、それぞれ３ビットで
あるとする。
【００２８】このビタビ復号器１９は、受信軟判定Ｐデ
ータ及び受信軟判定Ｑデータをそれぞれ入力する入力端
子１，２と、入力した受信軟判定Ｐデータ及び受信軟判
定Ｑデータの組と“０００”データ（ターミナルデー
タ）の組とを切替える第１のセレクタ３と、第１のセレ
クタ３の出力と各送信データを比べて第１のセレクタ３
の出力の確からしさを求めるブランチメトリック生成器
４と、生き残りパスの累積メトリックを格納するパスメ
トリックレジスタ６と、ブランチメトリック生成器４の
出力とパスメトリックレジスタ６の出力に基づいてシン
ボル時刻ごとにｎ状態のパスメトリック値とｎ状態の選
択情報（枝値）とを出力するＡＣＳ回路５と、シンボル
時刻ごとにＡＣＳ回路５が出力するｎ状態の選択情報を
格納するパスメモリ７と、シンボル時刻ごとにＡＣＳ回
路５が出力するｎ状態のパスメトリック値の中から最大
のパスメトリックを持つ状態番号を求める最尤パス状態
検出器９と、パスメモリ７内のデータに対してトレース
バック処理を行い、得られた結果を復号データとして出
力端子１６から出力するトレースバック回路８と、この
ビタビ復号器１９全体の制御を行う制御回路１０と、を
備えている。
ータ及び受信軟判定Ｑデータをそれぞれ入力する入力端
子１，２と、入力した受信軟判定Ｐデータ及び受信軟判
定Ｑデータの組と“０００”データ（ターミナルデー
タ）の組とを切替える第１のセレクタ３と、第１のセレ
クタ３の出力と各送信データを比べて第１のセレクタ３
の出力の確からしさを求めるブランチメトリック生成器
４と、生き残りパスの累積メトリックを格納するパスメ
トリックレジスタ６と、ブランチメトリック生成器４の
出力とパスメトリックレジスタ６の出力に基づいてシン
ボル時刻ごとにｎ状態のパスメトリック値とｎ状態の選
択情報（枝値）とを出力するＡＣＳ回路５と、シンボル
時刻ごとにＡＣＳ回路５が出力するｎ状態の選択情報を
格納するパスメモリ７と、シンボル時刻ごとにＡＣＳ回
路５が出力するｎ状態のパスメトリック値の中から最大
のパスメトリックを持つ状態番号を求める最尤パス状態
検出器９と、パスメモリ７内のデータに対してトレース
バック処理を行い、得られた結果を復号データとして出
力端子１６から出力するトレースバック回路８と、この
ビタビ復号器１９全体の制御を行う制御回路１０と、を
備えている。
【００２９】ここでＡＣＳ回路５は、シンボル時刻ごと
に、トレリス線図にしたがって、ブランチメトリック生
成器４の出力とパスメトリックレジスタ６の出力とを加
算、比較、選択することにより、比較して選択したｎ状
態のパスメトリック値とｎ状態の選択情報とを出力す
る。また、トレースバック回路８は、パスメモリ制御信
号をパスメモリ７に対して出力しパスメモリ７からデー
タを読み出すことにより、（ｇ−ｆ）シンボル時刻ごと
に、最尤パス状態検出器９の出力の状態番号からｇシン
ボル時刻分だけパスメモリ７を過去に向かってたどって
いき、最後に到達したビットから（ｇ−ｆ）ビットを復
号データとして出力する。ここでパスメモリ７は、（ｇ
＋ｆ）時刻分の状態情報を格納するだけの容量を有する
リングメモリである。
に、トレリス線図にしたがって、ブランチメトリック生
成器４の出力とパスメトリックレジスタ６の出力とを加
算、比較、選択することにより、比較して選択したｎ状
態のパスメトリック値とｎ状態の選択情報とを出力す
る。また、トレースバック回路８は、パスメモリ制御信
号をパスメモリ７に対して出力しパスメモリ７からデー
タを読み出すことにより、（ｇ−ｆ）シンボル時刻ごと
に、最尤パス状態検出器９の出力の状態番号からｇシン
ボル時刻分だけパスメモリ７を過去に向かってたどって
いき、最後に到達したビットから（ｇ−ｆ）ビットを復
号データとして出力する。ここでパスメモリ７は、（ｇ
＋ｆ）時刻分の状態情報を格納するだけの容量を有する
リングメモリである。
【００３０】以上述べた構成は、制御回路１０の構成及
び機能が若干異なり、またトレースバック回路８に後述
するように受信クロックと動作クロックの両方が入力す
ること以外は、図９に示した従来のビタビ復号器５９と
同一である。
び機能が若干異なり、またトレースバック回路８に後述
するように受信クロックと動作クロックの両方が入力す
ること以外は、図９に示した従来のビタビ復号器５９と
同一である。
【００３１】さらにこのビタビ復号器１９には、受信ク
ロックが入力する入力端子１２と、受信クロックより速
い高速クロックが入力する入力端子１３と、入力端子１
２に入力する受信クロックと入力端子１３に入力する高
速クロックとを切り替えて動作クロックとして出力する
第２のセレクタ１１と、パケットデータ開始パルスを入
力して制御回路１０に供給する入力端子１４と、パケッ
トデータ終了パルスを入力しれ制御回路１０に供給する
入力端子１５と、が設けられている。このビタビ復号器
１９では、第２のセレクタ１１から出力される動作クロ
ックがブランチメトリック生成器４、ＡＣＳ回路５、パ
スメトリックレジスタ６、パスメモリ７及びトレースバ
ック回路８に供給されている。入力端子１２に入力した
受信クロックも、トレースバック回路８に直接供給され
ている。なお、受信クロックが第１の動作クロックに対
応し、高速クロックが第２の動作クロックに対応する。
ロックが入力する入力端子１２と、受信クロックより速
い高速クロックが入力する入力端子１３と、入力端子１
２に入力する受信クロックと入力端子１３に入力する高
速クロックとを切り替えて動作クロックとして出力する
第２のセレクタ１１と、パケットデータ開始パルスを入
力して制御回路１０に供給する入力端子１４と、パケッ
トデータ終了パルスを入力しれ制御回路１０に供給する
入力端子１５と、が設けられている。このビタビ復号器
１９では、第２のセレクタ１１から出力される動作クロ
ックがブランチメトリック生成器４、ＡＣＳ回路５、パ
スメトリックレジスタ６、パスメモリ７及びトレースバ
ック回路８に供給されている。入力端子１２に入力した
受信クロックも、トレースバック回路８に直接供給され
ている。なお、受信クロックが第１の動作クロックに対
応し、高速クロックが第２の動作クロックに対応する。
【００３２】制御回路１０は、第１のセレクタ３に対し
て第１のセレクト信号を出力し、第２のセレクタ１１に
対して第２のセレクト信号を出力し、パスメトリックレ
ジスタ６にパスメトリックセット信号を出力し、トレー
スバック回路８にトレースバック開始信号を出力するも
のである。通常時には、第２のセレクタ１１が受信クロ
ックを選択するように、第２のセレクト信号を出力す
る。制御回路１０は、パケットデータ開始パルスによっ
て、第１のセレクタ３が入力端子１１，１２側を選択す
るように第１のセレクト信号を出力し、パスメトリック
レジスタ６の状態番号“０”に高いパスメトリックを与
え、他の状態番号には、すべて同じ低いパスメトリック
（例えば、０）を与えてビタビ復号を実行させるように
構成されている。さらに制御回路１０は、パケットデー
タ終了パルスが入力されると、第１のセレクタ３が“０
００”データの組を選択し、第２のセレクタ１１が高速
パルスを選択するように、第１のセレクト信号及び第２
のセレクト信号を設定し、ビタビ復号を実行しながら、
最尤パス状態検出器９の出力が状態番号“０”になる
と、ブランチメトリック生成器４、ＡＣＳ回路５、パス
メトリックレジスタ６及び最尤パス状態検出器９の動作
を停止させ、状態番号“０”の最尤パスに連なる系列か
らトレースバック回路８にトレースバックを実行させる
ように構成されている。
て第１のセレクト信号を出力し、第２のセレクタ１１に
対して第２のセレクト信号を出力し、パスメトリックレ
ジスタ６にパスメトリックセット信号を出力し、トレー
スバック回路８にトレースバック開始信号を出力するも
のである。通常時には、第２のセレクタ１１が受信クロ
ックを選択するように、第２のセレクト信号を出力す
る。制御回路１０は、パケットデータ開始パルスによっ
て、第１のセレクタ３が入力端子１１，１２側を選択す
るように第１のセレクト信号を出力し、パスメトリック
レジスタ６の状態番号“０”に高いパスメトリックを与
え、他の状態番号には、すべて同じ低いパスメトリック
（例えば、０）を与えてビタビ復号を実行させるように
構成されている。さらに制御回路１０は、パケットデー
タ終了パルスが入力されると、第１のセレクタ３が“０
００”データの組を選択し、第２のセレクタ１１が高速
パルスを選択するように、第１のセレクト信号及び第２
のセレクト信号を設定し、ビタビ復号を実行しながら、
最尤パス状態検出器９の出力が状態番号“０”になる
と、ブランチメトリック生成器４、ＡＣＳ回路５、パス
メトリックレジスタ６及び最尤パス状態検出器９の動作
を停止させ、状態番号“０”の最尤パスに連なる系列か
らトレースバック回路８にトレースバックを実行させる
ように構成されている。
【００３３】このように制御回路１０が設定されている
ことにより、このビタビ復号器１９では、パケット終了
パルスの入力とともに、第１のセレクタ３の出力が、各
３ビットの受信軟判定Ｐデータ及び受信軟判定Ｑデータ
の組からターミナルデータである“０００”データの組
に切り替わり、第２のセレクタ１１の出力（動作クロッ
ク）が受信クッロクから高速クロックに切り替わり、そ
の結果、ブランチメトリック生成器４、ＡＣＳ回路５、
パスメトリックレジスタ６、最尤パス状態検出器９及び
パスメモリ７は、高速クロックで動作することになる。
最尤パス状態検出器９は、高速クロックの１周期ごと
に、現在、最尤パスがどの状態番号にいるか調べる。制
御回路１０は、最尤パスが状態番号“０”になると、ブ
ランチメトリック生成器４、ＡＣＳ回路５、パスメトリ
ックレジスタ６及び最尤パス状態検出器９の動作を停止
させ、トレースバック回路８を使って、状態番号“０”
の最尤パスに連なる系列をパスメモリ７格納されたデー
タから読み出して、復号データとして出力させる。
ことにより、このビタビ復号器１９では、パケット終了
パルスの入力とともに、第１のセレクタ３の出力が、各
３ビットの受信軟判定Ｐデータ及び受信軟判定Ｑデータ
の組からターミナルデータである“０００”データの組
に切り替わり、第２のセレクタ１１の出力（動作クロッ
ク）が受信クッロクから高速クロックに切り替わり、そ
の結果、ブランチメトリック生成器４、ＡＣＳ回路５、
パスメトリックレジスタ６、最尤パス状態検出器９及び
パスメモリ７は、高速クロックで動作することになる。
最尤パス状態検出器９は、高速クロックの１周期ごと
に、現在、最尤パスがどの状態番号にいるか調べる。制
御回路１０は、最尤パスが状態番号“０”になると、ブ
ランチメトリック生成器４、ＡＣＳ回路５、パスメトリ
ックレジスタ６及び最尤パス状態検出器９の動作を停止
させ、トレースバック回路８を使って、状態番号“０”
の最尤パスに連なる系列をパスメモリ７格納されたデー
タから読み出して、復号データとして出力させる。
【００３４】以上の高速クロック動作により、このビタ
ビ復号器１９では、パケットデータ終了後のビタビ復号
処理を迅速に行うことができ、すぐに次のパケットデー
タがビタビ復号器に入力する場合であっても、前のパケ
ットデータの最後の部分を正しく復号できるようにな
る。
ビ復号器１９では、パケットデータ終了後のビタビ復号
処理を迅速に行うことができ、すぐに次のパケットデー
タがビタビ復号器に入力する場合であっても、前のパケ
ットデータの最後の部分を正しく復号できるようにな
る。
【００３５】以下、このビタビ復号器１９の動作につい
て、詳しく説明する。
て、詳しく説明する。
【００３６】ここでは、説明を分かりやすくするため
に、符号化率Ｒ＝１／２、拘束長Ｋ＝３の場合について
考える。このビタビ復号器１９と対になって使用される
送信側の符号器は、上述の従来の技術欄で図２を用いて
説明したものと同じものである。従来の技術で説明した
のと同様に、図３に示すようなｄ個のパケットデータｉ
1，ｉ2，…，ｉdを畳み込み符号化するものとする。こ
のようなパケットデータの符号化を行う場合、一般的
に、最初のパケットデータｉ1が入力する前に畳み込み
符号器２３をリセットし、また、最後のパケットデータ
ｉdがシフトレジスタ２０に入力した後に、（拘束長−
１）個の“０”データを入力する。ここでは、拘束長が
３なので、２個の“０”データを入力する。畳み込み符
号器２３のＰデータ及びＱデータ出力を、それぞれ、Ｐ
1，Ｐ2，…，Ｐd，Ｐd+1，Ｐd+2及びＱ1，Ｑ2，…，
Ｑd，Ｑd+1，Ｑd+2とする。送信側の畳み込み符号器２
３の出力、すなわちＰデータ及びＱデータが伝送され、
従来の技術欄で述べたのと同様に軟判定表現され、ビタ
ビ復号器９に入力する。図４は、“０”，“１”に対し
てそれぞれ３ビットで軟判定表現を行ったものを示して
いる。また、送信側の畳み込み符号器２３のトレリス表
現は、従来の技術欄で説明した図５に示す通りのもので
あり、ビタビ復号器１９は、図５に示すトレリス表現に
したがって復号処理を行っている。
に、符号化率Ｒ＝１／２、拘束長Ｋ＝３の場合について
考える。このビタビ復号器１９と対になって使用される
送信側の符号器は、上述の従来の技術欄で図２を用いて
説明したものと同じものである。従来の技術で説明した
のと同様に、図３に示すようなｄ個のパケットデータｉ
1，ｉ2，…，ｉdを畳み込み符号化するものとする。こ
のようなパケットデータの符号化を行う場合、一般的
に、最初のパケットデータｉ1が入力する前に畳み込み
符号器２３をリセットし、また、最後のパケットデータ
ｉdがシフトレジスタ２０に入力した後に、（拘束長−
１）個の“０”データを入力する。ここでは、拘束長が
３なので、２個の“０”データを入力する。畳み込み符
号器２３のＰデータ及びＱデータ出力を、それぞれ、Ｐ
1，Ｐ2，…，Ｐd，Ｐd+1，Ｐd+2及びＱ1，Ｑ2，…，
Ｑd，Ｑd+1，Ｑd+2とする。送信側の畳み込み符号器２
３の出力、すなわちＰデータ及びＱデータが伝送され、
従来の技術欄で述べたのと同様に軟判定表現され、ビタ
ビ復号器９に入力する。図４は、“０”，“１”に対し
てそれぞれ３ビットで軟判定表現を行ったものを示して
いる。また、送信側の畳み込み符号器２３のトレリス表
現は、従来の技術欄で説明した図５に示す通りのもので
あり、ビタビ復号器１９は、図５に示すトレリス表現に
したがって復号処理を行っている。
【００３７】ビタビ復号器１９においてパケット開始パ
ルスが制御回路１０に入力すると、制御回路１０は、パ
スメトリックセット信号をパスメトリックレジスタ６に
出力する。パスメトリックレジスタ６は、この信号によ
り、状態番号０のレジスタに高いメトリック（例えば、
６４）を与え、状態番号１，２，３のレジスタには、メ
トリック０を与える。このとき、制御回路１０は、第１
のセレクタの出力が受信軟判定Ｐ，Ｑデータの組とな
り、第２のセレクタ１１の出力が、受信軟判定Ｐ，Ｑデ
ータに同期したクロックである受信クロックとなるよう
に、第１のセレクト信号及び第２のセレクト信号を設定
している。したがって、ブランチメトリック生成器４、
ＡＣＳ回路５、パスメトリックレジスタ６、パスメモリ
７及びトレースバック回路８は、受信軟判定Ｐ，Ｑデー
タに同期した受信クロックを動作クロックとして作動す
ることになる。
ルスが制御回路１０に入力すると、制御回路１０は、パ
スメトリックセット信号をパスメトリックレジスタ６に
出力する。パスメトリックレジスタ６は、この信号によ
り、状態番号０のレジスタに高いメトリック（例えば、
６４）を与え、状態番号１，２，３のレジスタには、メ
トリック０を与える。このとき、制御回路１０は、第１
のセレクタの出力が受信軟判定Ｐ，Ｑデータの組とな
り、第２のセレクタ１１の出力が、受信軟判定Ｐ，Ｑデ
ータに同期したクロックである受信クロックとなるよう
に、第１のセレクト信号及び第２のセレクト信号を設定
している。したがって、ブランチメトリック生成器４、
ＡＣＳ回路５、パスメトリックレジスタ６、パスメモリ
７及びトレースバック回路８は、受信軟判定Ｐ，Ｑデー
タに同期した受信クロックを動作クロックとして作動す
ることになる。
【００３８】この状態でまず、Ｐ1，Ｑ1に対する軟判定
データが、入力端子１，４よりセレクタ３を通ってブラ
ンチメトリック生成器４に入力すると、ブランチメトリ
ック生成器４は、（軟判定Ｐ1,軟判定Ｑ1）に対して、
その時の送信データの組（Ｐ,Ｑ）が（０,０），（１,
０），（０,１），（１,１）であったとした場合の確か
らしさ、すなわちブランチメトリックを各々算出する。
（軟判定Ｐ1,軟判定Ｑ1）に対して、送信データの組が
（０,０）であるときのブランチメトリックをλ0、送信
データの組が（１,０）の時のブランチメトリックを
λ1、送信データの組が（０,１）の時のブランチメトリ
ックをλ2、送信データの組が（１,１）の時のブランチ
メトリックをλ3とする。ブランチメトリック生成器４
は、このλ0，λ1，λ2，λ3をＡＣＳ回路５に出力す
る。このとき、図６に示すように、時刻ｍ0での各状態
番号０〜４のパスメトリック値を、それぞれ、Γ
0(ｍ0)，Γ1(ｍ0)，Γ2(ｍ0)，Γ3(ｍ0)とする。実際に
は、メトリックセットしたばかりなので、Γ0(ｍ0)＝６
４，Γ1(ｍ0)＝０，Γ2(ｍ0)＝０，Γ3(ｍ0)＝０となっ
ている。
データが、入力端子１，４よりセレクタ３を通ってブラ
ンチメトリック生成器４に入力すると、ブランチメトリ
ック生成器４は、（軟判定Ｐ1,軟判定Ｑ1）に対して、
その時の送信データの組（Ｐ,Ｑ）が（０,０），（１,
０），（０,１），（１,１）であったとした場合の確か
らしさ、すなわちブランチメトリックを各々算出する。
（軟判定Ｐ1,軟判定Ｑ1）に対して、送信データの組が
（０,０）であるときのブランチメトリックをλ0、送信
データの組が（１,０）の時のブランチメトリックを
λ1、送信データの組が（０,１）の時のブランチメトリ
ックをλ2、送信データの組が（１,１）の時のブランチ
メトリックをλ3とする。ブランチメトリック生成器４
は、このλ0，λ1，λ2，λ3をＡＣＳ回路５に出力す
る。このとき、図６に示すように、時刻ｍ0での各状態
番号０〜４のパスメトリック値を、それぞれ、Γ
0(ｍ0)，Γ1(ｍ0)，Γ2(ｍ0)，Γ3(ｍ0)とする。実際に
は、メトリックセットしたばかりなので、Γ0(ｍ0)＝６
４，Γ1(ｍ0)＝０，Γ2(ｍ0)＝０，Γ3(ｍ0)＝０となっ
ている。
【００３９】パスメトリックレジスタ６は、このΓ0(ｍ
0)，Γ1(ｍ0)，Γ2(ｍ0)，Γ3(ｍ0)をＡＣＳ回路５に出
力し、ＡＣＳ回路５は、図６に示すトレリス表現に基づ
いて、演算を実行する。この処理は、従来の技術欄にお
いてＡＣＳ処理として説明したものと同一である。次の
軟判定Ｐ2，Ｑ2データが入力すると、同様にＡＣＳ処理
を実行する。以下同様にして、ＡＣＳ処理を繰り返し実
行し、時刻ｍgでの処理が終わると、制御回路１０は、
トレースバック回路８及び最尤パス状態検出器９に対
し、トレースバック処理を行うための命令を与える。な
お、通常のビタビ復号器におけるトレースバック処理の
ことを通常のトレースバック処理ともいう。
0)，Γ1(ｍ0)，Γ2(ｍ0)，Γ3(ｍ0)をＡＣＳ回路５に出
力し、ＡＣＳ回路５は、図６に示すトレリス表現に基づ
いて、演算を実行する。この処理は、従来の技術欄にお
いてＡＣＳ処理として説明したものと同一である。次の
軟判定Ｐ2，Ｑ2データが入力すると、同様にＡＣＳ処理
を実行する。以下同様にして、ＡＣＳ処理を繰り返し実
行し、時刻ｍgでの処理が終わると、制御回路１０は、
トレースバック回路８及び最尤パス状態検出器９に対
し、トレースバック処理を行うための命令を与える。な
お、通常のビタビ復号器におけるトレースバック処理の
ことを通常のトレースバック処理ともいう。
【００４０】トレースバック処理を行うための命令が与
えられると、最尤パス状態検出器９は、、最尤パスメト
リック値Γ0(ｍg)，Γ1(ｍg)，Γ2(ｍg)，Γ3(ｍg)の中
から、最大のパスメトリック値を持つ状態番号をトレー
スバック回路８に出力する。時刻ｍgにおいて最大パス
メトリック値をもつ状態番号が“２”であるとすると、
トレースバック回路８は、時刻ｍgにおいて図７の実線
で示す最大パスメトリックをもつ状態番号２に連なるパ
スを、パスメモリ７の内容を読み出してさかのぼってい
く。トレースバック回路８は、状態番号２に合流するパ
スが状態番号１及び状態番号３のどちらであるかを、パ
スメモリ７から、時刻ｍfの状態番号２に格納されてい
るデータを読み出すことにより調べ、状態番号１からで
あることを知る。以下、同様の操作を繰り返し、時刻ｍ
0までパスをさかのぼり、最後にパスメモリ７より読み
出したデータから（ｇ−ｆ）個分のデータ（時刻ｍ1か
ら時刻ｍg-fのデータ）を復号データとして、出力端子
１６から出力する。このとき、第２のセレクタ１１は受
信クロックを選択しているから、このトレースバック処
理は、受信クロックに同期して実行されることになる。
また、トレースバック処理を実行しているときも、上述
したＡＣＳ処理は受信クロックに同期して実行されてい
る。パスメモリ７は、ＡＣＳ処理時の書き込み及びトレ
ースバック処理時の読み出しを同時に行えるものであ
り、また、上述したように（ｇ＋ｆ）時刻分のメモリ容
量になっているので、ＡＣＳ処理によって必要なデータ
に上書きされることはない。このあと、（ｇ−ｆ）時刻
分のＡＣＳ処理を実行するごとに、トレースバック処理
を行い復号データを出力する。
えられると、最尤パス状態検出器９は、、最尤パスメト
リック値Γ0(ｍg)，Γ1(ｍg)，Γ2(ｍg)，Γ3(ｍg)の中
から、最大のパスメトリック値を持つ状態番号をトレー
スバック回路８に出力する。時刻ｍgにおいて最大パス
メトリック値をもつ状態番号が“２”であるとすると、
トレースバック回路８は、時刻ｍgにおいて図７の実線
で示す最大パスメトリックをもつ状態番号２に連なるパ
スを、パスメモリ７の内容を読み出してさかのぼってい
く。トレースバック回路８は、状態番号２に合流するパ
スが状態番号１及び状態番号３のどちらであるかを、パ
スメモリ７から、時刻ｍfの状態番号２に格納されてい
るデータを読み出すことにより調べ、状態番号１からで
あることを知る。以下、同様の操作を繰り返し、時刻ｍ
0までパスをさかのぼり、最後にパスメモリ７より読み
出したデータから（ｇ−ｆ）個分のデータ（時刻ｍ1か
ら時刻ｍg-fのデータ）を復号データとして、出力端子
１６から出力する。このとき、第２のセレクタ１１は受
信クロックを選択しているから、このトレースバック処
理は、受信クロックに同期して実行されることになる。
また、トレースバック処理を実行しているときも、上述
したＡＣＳ処理は受信クロックに同期して実行されてい
る。パスメモリ７は、ＡＣＳ処理時の書き込み及びトレ
ースバック処理時の読み出しを同時に行えるものであ
り、また、上述したように（ｇ＋ｆ）時刻分のメモリ容
量になっているので、ＡＣＳ処理によって必要なデータ
に上書きされることはない。このあと、（ｇ−ｆ）時刻
分のＡＣＳ処理を実行するごとに、トレースバック処理
を行い復号データを出力する。
【００４１】ここまでは、上述の従来の技術欄で述べた
従来のビタビ復号器と同じ動作である。
従来のビタビ復号器と同じ動作である。
【００４２】最後の軟判定Ｐd+2，Ｑd+2データが入力端
子１，２より入力し、ＡＣＳ処理が終了すると、パケッ
ト終了パルスが入力端子１５を介して制御回路１０に入
力する。このパルスの入力により、制御回路１０は、第
１のセレクタ３から“０００”データの組が出力し、第
２のセレクタ１１が、入力端子１３から入力する高速ク
ロックを動作クロックとして出力するように、第１のセ
レクト信号及び第２のセレクト信号を設定する。そして
制御回路１０は、まず、最尤パス状態検出器９の出力が
状態番号０かどうかを調べる。もし状態番号０であれ
ば、以下に説明する高速トレースバック処理を実行す
る。
子１，２より入力し、ＡＣＳ処理が終了すると、パケッ
ト終了パルスが入力端子１５を介して制御回路１０に入
力する。このパルスの入力により、制御回路１０は、第
１のセレクタ３から“０００”データの組が出力し、第
２のセレクタ１１が、入力端子１３から入力する高速ク
ロックを動作クロックとして出力するように、第１のセ
レクト信号及び第２のセレクト信号を設定する。そして
制御回路１０は、まず、最尤パス状態検出器９の出力が
状態番号０かどうかを調べる。もし状態番号０であれ
ば、以下に説明する高速トレースバック処理を実行す
る。
【００４３】高速トレースバック処理では、第２のセレ
クタ１１から動作クロックとして出力されている高速ク
ロックを用い、時刻ｍd+2の状態番号０から、パケット
終了パルスが入力する直前に最後に通常のトレースバッ
ク処理を行って復号データとして出力した時刻の前ま
で、パスメモリ７より格納されているデータを読み出し
ながらトレースバック動作を行い、トレースバックで得
たすべてのデータを復号データとして、受信クロックに
同期して、出力端子１６より出力する。
クタ１１から動作クロックとして出力されている高速ク
ロックを用い、時刻ｍd+2の状態番号０から、パケット
終了パルスが入力する直前に最後に通常のトレースバッ
ク処理を行って復号データとして出力した時刻の前ま
で、パスメモリ７より格納されているデータを読み出し
ながらトレースバック動作を行い、トレースバックで得
たすべてのデータを復号データとして、受信クロックに
同期して、出力端子１６より出力する。
【００４４】ここでもし、最尤パス状態検出器９の出力
が状態番号０でなければ、ＡＣＳ処理を１時刻分実行す
る。このとき、ブランチメトリック生成器４に入力され
る軟判定Ｐ，Ｑデータの組は“０００”である。ＡＣＳ
処理を実行したあと、制御回路１０は、最尤パス状態検
出器９の出力が状態番号０かどうかを再度調べる。も
し、状態番号０であれば、上述した高速トレースバック
処理を実行し、状態番号０でなければ、再びＡＣＳ処理
を１時刻分実行する。最大パスメトリックの状態番号が
０と判定されるまで、この動作を繰り返し実行する。制
御回路１０は、最尤パス状態検出器９の出力が状態番号
０を示せば、高速トレースバック処理を実行して、すべ
ての復号データを得る。
が状態番号０でなければ、ＡＣＳ処理を１時刻分実行す
る。このとき、ブランチメトリック生成器４に入力され
る軟判定Ｐ，Ｑデータの組は“０００”である。ＡＣＳ
処理を実行したあと、制御回路１０は、最尤パス状態検
出器９の出力が状態番号０かどうかを再度調べる。も
し、状態番号０であれば、上述した高速トレースバック
処理を実行し、状態番号０でなければ、再びＡＣＳ処理
を１時刻分実行する。最大パスメトリックの状態番号が
０と判定されるまで、この動作を繰り返し実行する。制
御回路１０は、最尤パス状態検出器９の出力が状態番号
０を示せば、高速トレースバック処理を実行して、すべ
ての復号データを得る。
【００４５】なお、通常のトレースバック処理を実行し
ている途中でパケット終了パルスが制御回路１０に入力
した場合、一旦、通常のトレースバック処理を停止さ
せ、動作クロックが高速クロックに切り替わったら、再
び通常のトレースバック処理を行い速やかに処理を終了
させる。その後、制御回路１０は、最尤パス状態検出器
９の出力が状態番号０かどうかを調べる処理を実行す
る。
ている途中でパケット終了パルスが制御回路１０に入力
した場合、一旦、通常のトレースバック処理を停止さ
せ、動作クロックが高速クロックに切り替わったら、再
び通常のトレースバック処理を行い速やかに処理を終了
させる。その後、制御回路１０は、最尤パス状態検出器
９の出力が状態番号０かどうかを調べる処理を実行す
る。
【００４６】以上説明したようにこのビタビ復号器１９
では、制御回路１０にパケット終了信号が入力すると、
第１のセレクタ３の出力が各３ビットの受信軟判定Ｐデ
ータ及び３ビット受信軟判定Ｑデータの組から、“００
０”データの組に切り替わり、第２のセレクタ１１の出
力が受信クッロクから高速クロックに切り替わり、その
結果、ブランチメトリック生成器４、ＡＣＳ回路５、パ
スメトリックレジスタ６、パスメモリ及び最尤パス状態
検出器９が、受信クロックより速い高速クロックで動作
することになる。最尤パス状態検出器９は、高速クロッ
クの１周期ごとに、現在、最尤パスがどの状態番号にい
るか調べる。そして、最尤パスが状態番号“０”になる
と、制御回路１０が、ブランチメトリック生成器４、Ａ
ＣＳ回路５、パスメトリックレジスタ６及び最尤パス状
態検出器９の動作を停止させ、トレースバック回路８を
使用して高速トレースバック処理を実行させる。それに
より、状態番号“０”の最尤パスに連なる系列が、パス
メモリ７に格納されたデータから読み出され、復号デー
タとして出力される。この高速クロック動作により、パ
ケットデータ終了後のビタビ復号処理が迅速に行われ
る。
では、制御回路１０にパケット終了信号が入力すると、
第１のセレクタ３の出力が各３ビットの受信軟判定Ｐデ
ータ及び３ビット受信軟判定Ｑデータの組から、“００
０”データの組に切り替わり、第２のセレクタ１１の出
力が受信クッロクから高速クロックに切り替わり、その
結果、ブランチメトリック生成器４、ＡＣＳ回路５、パ
スメトリックレジスタ６、パスメモリ及び最尤パス状態
検出器９が、受信クロックより速い高速クロックで動作
することになる。最尤パス状態検出器９は、高速クロッ
クの１周期ごとに、現在、最尤パスがどの状態番号にい
るか調べる。そして、最尤パスが状態番号“０”になる
と、制御回路１０が、ブランチメトリック生成器４、Ａ
ＣＳ回路５、パスメトリックレジスタ６及び最尤パス状
態検出器９の動作を停止させ、トレースバック回路８を
使用して高速トレースバック処理を実行させる。それに
より、状態番号“０”の最尤パスに連なる系列が、パス
メモリ７に格納されたデータから読み出され、復号デー
タとして出力される。この高速クロック動作により、パ
ケットデータ終了後のビタビ復号処理が迅速に行われ
る。
【００４７】したがって、このビタビ復号器１９は、例
えば衛星通信や携帯電話のような移動体通信の分野にお
いてパッケト通信用の誤り訂正に使用する場合に、パケ
ットデータの最後の部分をスムーズに復号でき、すぐに
次のパケットデータが入力する場合であっても、前のパ
ケットデータの最後の部分を正しく復号することができ
る。
えば衛星通信や携帯電話のような移動体通信の分野にお
いてパッケト通信用の誤り訂正に使用する場合に、パケ
ットデータの最後の部分をスムーズに復号でき、すぐに
次のパケットデータが入力する場合であっても、前のパ
ケットデータの最後の部分を正しく復号することができ
る。
【００４８】次に、本発明の他の実施の形態について説
明する。
明する。
【００４９】上述の実施の形態のビタビ復号器１９で
は、パケットデータ終了パルスが入力したときには動作
クロックを受信クロックから高速クロックに切り替えて
いたが、受信クロックのままで処理しつつ、前のパケッ
トデータに引き続いて次のパケットデータがすぐに入力
する場合であっても前のパケットデータの最後の部分を
正しく復号できるようにすることも可能である。受信ク
ロックのままで処理しようとする場合には、“０００”
データに対するブランチメトリックは既知であるため、
図９に示す従来のビタビ復号器において、ブランチメト
リック生成器４が予めλ0，λ1，λ2，λ3を設定するよ
うにするとともに、パスメモリ７のメモリ容量を（ｆ＋
ｇ）時刻分から（２ｆ＋ｇ）時刻分に増加すればよい。
ＡＣＳ回路５、パスメトリックレジスタ６、最大パス状
態検出器９については、図９に示すビタビ復号器５９に
おけるものと同じ構成とする。このようにすることで、
ビタビ復号器の動作クロックを受信クロックとしたまま
で、パケットデータの伝送レートが大きい場合であって
も正確にビタビ復号を行うことが可能になる。
は、パケットデータ終了パルスが入力したときには動作
クロックを受信クロックから高速クロックに切り替えて
いたが、受信クロックのままで処理しつつ、前のパケッ
トデータに引き続いて次のパケットデータがすぐに入力
する場合であっても前のパケットデータの最後の部分を
正しく復号できるようにすることも可能である。受信ク
ロックのままで処理しようとする場合には、“０００”
データに対するブランチメトリックは既知であるため、
図９に示す従来のビタビ復号器において、ブランチメト
リック生成器４が予めλ0，λ1，λ2，λ3を設定するよ
うにするとともに、パスメモリ７のメモリ容量を（ｆ＋
ｇ）時刻分から（２ｆ＋ｇ）時刻分に増加すればよい。
ＡＣＳ回路５、パスメトリックレジスタ６、最大パス状
態検出器９については、図９に示すビタビ復号器５９に
おけるものと同じ構成とする。このようにすることで、
ビタビ復号器の動作クロックを受信クロックとしたまま
で、パケットデータの伝送レートが大きい場合であって
も正確にビタビ復号を行うことが可能になる。
【００５０】
【発明の効果】以上説明したように本発明は、（１）パ
ケットデータの入力が終わった時点でビタビ復号器の動
作クロックを速くし、これによってターミナルデータ分
の処理時間を短縮する、あるいは、（２）リングメモリ
として構成されるパスメモリの容量を大きし、それとと
もに、ターミナルデータに対するブランチメトリックは
予め分かっているからブランチメトリック生成器がその
ブランチメトリックを予め設定するようにすることによ
り、パケットデータの最後の部分をスムーズにあるいは
迅速に処理できるようになり、すぐに次のパケットデー
タがビタビ復号器に入力しても前のパケットデータの最
後の部分を正しく復号できるようなるという効果があ
る。
ケットデータの入力が終わった時点でビタビ復号器の動
作クロックを速くし、これによってターミナルデータ分
の処理時間を短縮する、あるいは、（２）リングメモリ
として構成されるパスメモリの容量を大きし、それとと
もに、ターミナルデータに対するブランチメトリックは
予め分かっているからブランチメトリック生成器がその
ブランチメトリックを予め設定するようにすることによ
り、パケットデータの最後の部分をスムーズにあるいは
迅速に処理できるようになり、すぐに次のパケットデー
タがビタビ復号器に入力しても前のパケットデータの最
後の部分を正しく復号できるようなるという効果があ
る。
【図１】本発明の実施の一形態のビタビ復号器の構成を
示すブロック図である。
示すブロック図である。
【図２】畳み込み符号器の構成を示すブロック図であ
る。
る。
【図３】送信データ系列と畳み込み符号化後のデータ系
列を示す図である。
列を示す図である。
【図４】“０”，“１”データに対する３ビットの軟判
定データを表した図である。
定データを表した図である。
【図５】図２の畳み込み符号器のトレリス表現を示す図
である。
である。
【図６】ＡＣＳ回路の構成を説明する図である。
【図７】トレースバック処理を説明するトレリス表現図
である。
である。
【図８】パスメモリの構成を示す図である。
【図９】従来のビタビ復号器の構成を示すブロック図で
ある。
ある。
１，２，１２〜１５ 入力端子 ３，１１ セレクタ ４ ブランチメトリック生成器 ５ ＡＣＳ回路 ６ パスメトリックレジスタ ７ パスメモリ ８ トレースバック回路 ９ 最尤パス状態検出器 １０ 制御回路 １６ 出力端子 １９ ビタビ復号器
Claims (8)
- 【請求項１】 受信データを入力し、前記受信データか
らブランチメトリックを生成し、前記ブランチメトリッ
クに対してＡＣＳ処理を実行して複数状態のパスメトリ
ック値及び選択情報を生成し、前記選択情報を蓄積し、
最大の前記パスメトリック値に基づいて最尤パスを決定
し、前記決定された最尤パスに基づき、前記蓄積した選
択情報を過去に向かってたどり復号データを出力するビ
タビ復号法において、 前記受信データがパケットデータであり、 前記パケットデータの受信中は、当該パケットデータに
同期した第１の動作クロックに基づいて、前記ブランチ
メトリックの生成、前記ＡＣＳ処理、前記最尤パスの決
定及び前記復号データの出力を実行し、 前記パケットデータの受信が終了した時点で、前記第１
の動作クロックより速い第２の動作クロックに切り替
え、前記第２の動作クロックに基づいて、前記ブランチ
メトリックの生成、前記ＡＣＳ処理及び前記最尤パスの
決定を実行することを特徴とするビタビ復号法。 - 【請求項２】 前記パケットデータの受信が終了した時
点で、ターミナルデータを前記受信データの後に入力す
る請求項１に記載のビタビ復号法。 - 【請求項３】 前記パケットデータの受信が終了した
後、前記第２の動作クロックの１周期ごとにその時点で
の最尤パスが前記ターミナルデータに対応するものであ
るかを調べ、前記ターミナルデータに対応するものであ
るときに前記最尤パスに連なる系列の選択情報を過去に
向かってたどり復号データとして出力する、請求項２に
記載のビタビ復号法。 - 【請求項４】 受信データとターミナルデータを切り替
えて出力する第１のセレクタと、 前記第１のセレクタの出力が入力し前記入力データの確
からしさを求めるブランチメトリック生成器と、 生き残りパスの累積メトリックを格納するパスメトリッ
クレジスタと、 シンボル時刻ごとに、前記ブランチメトリック生成器の
出力と前記パスメトリックレジスタの出力に基づいてＡ
ＣＳ処理を実行し、複数状態のパスメトリック値及び選
択情報とを出力するＡＣＳ回路と、 前記複数状態のパスメトリック値から最大のパスメトリ
ック値を有する最尤パスを検出する最尤パス状態検出器
と、 シンボル時刻ごとに、前記複数状態の選択情報を格納す
るパスメモリと、 （ｇ−ｆ）シンボル時刻ごとに、前記最尤パスに基づい
て、ｇシンボル時刻だけ前記パスメモリを過去に向かっ
てたどっていき、最後に到達したビットから（ｇ−ｆ）
ビットを復号データとして出力するトレースバック回路
と、を有し、 前記受信データがパケットデータであり、 前記パケットデータの受信中は前記第１のセレクタによ
って前記パケットデータを選択するとともに、前記パケ
ットデータに同期した第１の動作クロックによって前記
ブランチメトリック生成器、前記ＡＣＳ回路、前記パス
メトリックレジスタ、前記パスメモリ及び前記トレース
バック回路を駆動し、 前記パケットデータの受信が終了した時点で前記第１の
セレクタが前記ターミナルデータ側に切り替えられ、 前記パケットデータの受信が終了した後は、前記第１の
動作クロックより速い第２の動作クロックによって前記
ブランチメトリック生成器、前記ＡＣＳ回路、前記パス
メトリックレジスタ及び前記パスメモリを駆動する、ビ
タビ復号器。 - 【請求項５】 第１の動作クロックと第２の動作クロッ
クとを切り替える第２のセレクタと、 パケット開始パルスの入力に応じて、前記第１のセレク
タが前記受信データを選択し前記第２のセレクタが前記
第１の動作クロックを選択し、パケット終了パするの入
力に応じて、前記第１のセレクタが前記ターミナルデー
タを選択し前記第２のセレクタが前記第２の動作クロッ
クを選択するように、前記第１のセレクタ及び前記第２
のセレクタを制御する制御回路と、をさらに備える請求
項４に記載のビタビ復号器。 - 【請求項６】 前記パスメモリが、（ｆ＋ｇ）時刻分の
前記選択情報を格納するリングメモリである請求項４ま
たは５に記載のビタビ復号器。 - 【請求項７】 前記パケットデータの受信が終了した
後、前記最尤パス状態検出器が前記第２の動作クロック
の１周期ごとにその時点での最尤パスが前記ターミナル
データに対応するものであるかを調べ、前記ターミナル
データに対応するものであるときに前記トレースバック
回路が前記最尤パスに連なる系列の選択情報を過去に向
かってたどり復号データとして出力する、請求項４乃至
６いずれか１項に記載のビタビ復号器。 - 【請求項８】 受信データとターミナルデータを切り替
えて出力するセレクタと、前記セレクタの出力が入力し
前記入力データの確からしさを求めるブランチメトリッ
ク生成器と、生き残りパスの累積メトリックを格納する
パスメトリックレジスタと、シンボル時刻ごとに、前記
ブランチメトリック生成器の出力と前記パスメトリック
レジスタの出力に基づいてＡＣＳ処理を実行し、複数状
態のパスメトリック値及び選択情報とを出力するＡＣＳ
回路と、前記複数状態のパスメトリック値から最大のパ
スメトリック値を有する最尤パスを検出する最尤パス状
態検出器と、シンボル時刻ごとに、前記複数状態の選択
情報を格納するパスメモリと、（ｇ−ｆ）シンボル時刻
ごとに、前記最尤パスに基づいて、ｇシンボル時刻だけ
前記パスメモリを過去に向かってたどっていき、最後に
到達したビットから（ｇ−ｆ）ビットを復号データとし
て出力するトレースバック回路と、を有するビタビ復号
器において、 前記受信データがパケットデータであり、 前記パケットデータの受信中は前記セレクタによって前
記パケットデータが選択され、前記パケットデータの受
信終了に応じて前記セレクタが前記ターミナルデータ側
に切り替わるともに前記ブランチメトリック生成器がタ
ーミナルデータに対応するブランチメトリックを設定
し、 前記パスメモリが、（２ｆ＋ｇ）時刻分の前記選択情報
を格納するリングメモリであるビタビ復号器。
Priority Applications (3)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP20359098A JP3196835B2 (ja) | 1998-07-17 | 1998-07-17 | ビタビ復号法及びビタビ復号器 |
| US09/352,681 US6408420B1 (en) | 1998-07-17 | 1999-07-14 | Viterbi decoding method and apparatus thereof |
| EP99113938A EP0973266A1 (en) | 1998-07-17 | 1999-07-16 | Viterbi decoding method and apparatus therefor |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP20359098A JP3196835B2 (ja) | 1998-07-17 | 1998-07-17 | ビタビ復号法及びビタビ復号器 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JP2000036762A JP2000036762A (ja) | 2000-02-02 |
| JP3196835B2 true JP3196835B2 (ja) | 2001-08-06 |
Family
ID=16476599
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP20359098A Expired - Fee Related JP3196835B2 (ja) | 1998-07-17 | 1998-07-17 | ビタビ復号法及びビタビ復号器 |
Country Status (3)
| Country | Link |
|---|---|
| US (1) | US6408420B1 (ja) |
| EP (1) | EP0973266A1 (ja) |
| JP (1) | JP3196835B2 (ja) |
Families Citing this family (17)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| EP0930845B1 (en) * | 1997-06-27 | 2009-10-14 | The Trustees Of Columbia University In The City Of New York | Apparatus for circulatory valve repair |
| FR2768324B1 (fr) * | 1997-09-12 | 1999-12-10 | Jacques Seguin | Instrument chirurgical permettant, par voie percutanee, de fixer l'une a l'autre deux zones de tissu mou, normalement mutuellement distantes |
| JP3271663B2 (ja) * | 1999-06-15 | 2002-04-02 | 日本電気株式会社 | ビタビ復号装置 |
| US6654929B1 (en) * | 1999-10-01 | 2003-11-25 | Matsushita Electric Industrial Co., Ltd. | Viterbi decoder and Viterbi decoding method |
| US7225393B2 (en) * | 1999-10-01 | 2007-05-29 | Matsushita Electric Industrial Co., Ltd. | Viterbi decoder and Viterbi decoding method |
| KR100350502B1 (ko) * | 1999-10-05 | 2002-08-28 | 삼성전자 주식회사 | 이동통신시스템의 구성 복호기 및 방법 |
| US7050517B1 (en) * | 2000-04-28 | 2006-05-23 | National Semiconductor Corporation | System and method suitable for receiving gigabit ethernet signals |
| US6865711B2 (en) * | 2000-12-15 | 2005-03-08 | Conexant Systems, Inc. | System of and method for decoding trellis codes |
| TW543301B (en) * | 2000-12-22 | 2003-07-21 | Mediatek Inc | Decoding circuit and method of Vieterbi decoder |
| US6928605B2 (en) * | 2002-03-29 | 2005-08-09 | Intel Corporation | Add-compare-select accelerator using pre-compare-select-add operation |
| US7103831B1 (en) * | 2003-01-22 | 2006-09-05 | Conexant Systems, Inc. | Burst reliability and error locator for trellis codes |
| JP2005045727A (ja) | 2003-07-25 | 2005-02-17 | Matsushita Electric Ind Co Ltd | ビタビ復号器 |
| US7733972B2 (en) * | 2004-10-26 | 2010-06-08 | Broadcom Corporation | Trellis decoder for decoding data stream including symbols coded with multiple convolutional codes |
| US7603613B2 (en) * | 2005-02-17 | 2009-10-13 | Samsung Electronics Co., Ltd. | Viterbi decoder architecture for use in software-defined radio systems |
| EP1903702A1 (en) * | 2006-09-19 | 2008-03-26 | STMicroelectronics N.V. | Method and device for estimating the drift between two clocks, in particular for ranging applications in UWB-LDR technology |
| US8111767B2 (en) * | 2007-05-31 | 2012-02-07 | Renesas Electronics Corporation | Adaptive sliding block Viterbi decoder |
| JP5445829B2 (ja) * | 2009-05-29 | 2014-03-19 | ソニー株式会社 | 受信装置、受信方法、およびプログラム、並びに受信システム |
Family Cites Families (9)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US5424882A (en) * | 1989-03-13 | 1995-06-13 | Hitachi, Ltd. | Signal processor for discriminating recording data |
| FR2686751B1 (fr) | 1992-01-24 | 1997-03-28 | France Telecom | Procede de decodage a maximum de vraisemblance a treillis de decodage sous-echantillonne, et dispositif de decodage correspondant. |
| ZA947317B (en) * | 1993-09-24 | 1995-05-10 | Qualcomm Inc | Multirate serial viterbi decoder for code division multiple access system applications |
| US5710756A (en) * | 1995-02-13 | 1998-01-20 | Netro Corporation | Burst-error resistant ATM microwave link and network |
| JPH09266448A (ja) * | 1996-03-28 | 1997-10-07 | Sony Corp | ビタビ復号化装置およびビタビ復号化方法 |
| US5982818A (en) * | 1997-01-07 | 1999-11-09 | Daniel J. Krueger | Method for implementing trellis codes for ISI channels |
| JP4103152B2 (ja) * | 1997-04-18 | 2008-06-18 | ソニー株式会社 | 情報再生装置および再生方法 |
| US5987638A (en) * | 1997-04-22 | 1999-11-16 | Lsi Logic Corporation | Apparatus and method for computing the result of a viterbi equation in a single cycle |
| JP3464121B2 (ja) * | 1997-06-11 | 2003-11-05 | 沖電気工業株式会社 | ビタビ復号方法及びビタビ復号装置 |
-
1998
- 1998-07-17 JP JP20359098A patent/JP3196835B2/ja not_active Expired - Fee Related
-
1999
- 1999-07-14 US US09/352,681 patent/US6408420B1/en not_active Expired - Fee Related
- 1999-07-16 EP EP99113938A patent/EP0973266A1/en not_active Withdrawn
Also Published As
| Publication number | Publication date |
|---|---|
| EP0973266A1 (en) | 2000-01-19 |
| JP2000036762A (ja) | 2000-02-02 |
| US6408420B1 (en) | 2002-06-18 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| JP3196835B2 (ja) | ビタビ復号法及びビタビ復号器 | |
| US6445755B1 (en) | Two-step soft output viterbi algorithm decoder using modified trace back | |
| JP3239870B2 (ja) | データ誤り訂正システム | |
| US4614933A (en) | Viterbi decoder with the pipeline processing function | |
| US8122327B2 (en) | Symbol-level soft output viterbi algorithm (SOVA) and a simplification on SOVA | |
| EP3996285A1 (en) | Parallel backtracking in viterbi decoder | |
| JP3271663B2 (ja) | ビタビ復号装置 | |
| JP2008118327A (ja) | ビタビ復号方法 | |
| JP3753822B2 (ja) | ビタビ復号方法および装置 | |
| US20050138535A1 (en) | Method and system for branch metric calculation in a viterbi decoder | |
| JP3337950B2 (ja) | 誤り訂正復号化方法及び誤り訂正復号化装置 | |
| JP4295871B2 (ja) | 誤り訂正復号器 | |
| JP3351414B2 (ja) | ビタビ復号装置 | |
| KR0169680B1 (ko) | 비터비 복호기 | |
| JP4226165B2 (ja) | 復号装置及び復号方法 | |
| JP3530451B2 (ja) | ビタビ復号装置 | |
| JP3120342B2 (ja) | ビタビ復号器 | |
| JPH08279765A (ja) | 畳込み符号ならびにトレリス符号用の復号アルゴリズムとそれを用いる受信装置 | |
| KR0169679B1 (ko) | 비터비 복호기 | |
| KR0140779B1 (ko) | 비터비 복호기 | |
| KR0169678B1 (ko) | 비터비 복호기 | |
| JP3342424B2 (ja) | ブランチメトリック演算装置及びビタビ復号装置 | |
| JP2803627B2 (ja) | 畳込み復号化回路 | |
| JPH09247002A (ja) | ビタビ復号化装置およびビタビ復号化方法 | |
| KR100359805B1 (ko) | 비터비 디코더 및 비터비 디코더의 디코딩 방법 |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| LAPS | Cancellation because of no payment of annual fees |