JPH0730438A - ビタビ復号方法 - Google Patents
ビタビ復号方法Info
- Publication number
- JPH0730438A JPH0730438A JP19428493A JP19428493A JPH0730438A JP H0730438 A JPH0730438 A JP H0730438A JP 19428493 A JP19428493 A JP 19428493A JP 19428493 A JP19428493 A JP 19428493A JP H0730438 A JPH0730438 A JP H0730438A
- Authority
- JP
- Japan
- Prior art keywords
- path
- memory
- state
- branch metric
- metric value
- 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.)
- Withdrawn
Links
Landscapes
- Error Detection And Correction (AREA)
- Detection And Prevention Of Errors In Transmission (AREA)
Abstract
(57)【要約】
【目的】 畳込み符号化された受信系列をプロセッサに
よる演算処理で復号するビタビ復号方法に関し、枝メト
リック計算に要する演算量を大幅に削減することを目的
とする。 【構成】 畳込み符号化された受信系列をプロセッサに
より復号化するビタビ復号方法であって、各状態に対応
した枝メトリック値をテーブル化してメモリ１に記憶さ
せておき、生き残りパス選択のための演算にあたっては
メモリ１から枝メトリック値を読み出して使用するよう
にしたものである。
よる演算処理で復号するビタビ復号方法に関し、枝メト
リック計算に要する演算量を大幅に削減することを目的
とする。 【構成】 畳込み符号化された受信系列をプロセッサに
より復号化するビタビ復号方法であって、各状態に対応
した枝メトリック値をテーブル化してメモリ１に記憶さ
せておき、生き残りパス選択のための演算にあたっては
メモリ１から枝メトリック値を読み出して使用するよう
にしたものである。
Description
【０００１】
【産業上の利用分野】本発明は畳込み符号化された受信
系列をプロセッサによる演算処理で復号するビタビ復号
方法に関する。
系列をプロセッサによる演算処理で復号するビタビ復号
方法に関する。
【０００２】衛星通信あるいは移動通信などでは、伝送
路が無線区間になるため有線伝送に比べて誤り率が非常
に高く、このため符号化／復号化方式としては誤り訂正
能力の優れた訂正符号化／復号化方式が用いられる。そ
のなかでも畳込み符号化された受信系列を最尤復号する
ビタビ復号法は誤り訂正能力が特に優れているので、用
いられることが多い。
路が無線区間になるため有線伝送に比べて誤り率が非常
に高く、このため符号化／復号化方式としては誤り訂正
能力の優れた訂正符号化／復号化方式が用いられる。そ
のなかでも畳込み符号化された受信系列を最尤復号する
ビタビ復号法は誤り訂正能力が特に優れているので、用
いられることが多い。
【０００３】
【従来の技術】図４には符号化率が１／２で、生成行列
が Ｇ＝〔１＋Ｄ2 ，１＋Ｄ＋Ｄ2 〕 の二元畳込み符号を生成する畳込み符号器の例が示され
る。この２元畳込み符号を用いた場合のビタビ復号法を
図５に示す。
が Ｇ＝〔１＋Ｄ2 ，１＋Ｄ＋Ｄ2 〕 の二元畳込み符号を生成する畳込み符号器の例が示され
る。この２元畳込み符号を用いた場合のビタビ復号法を
図５に示す。
【０００４】図５は遅延素子Ｄの状態Ｓab（ａ，ｂ∈
０，１）の遷移を時間軸に対して表したトレリスを示
す。各状態間の遷移は、時点ｔk における情報ビット
０，１にそれぞれ対応して実線および破線の枝で示され
る。各枝に付されている２ビットの数値はそのときの畳
込み符号器の出力を表し、（ ）内の値はパスメトリッ
ク値を表す。
０，１）の遷移を時間軸に対して表したトレリスを示
す。各状態間の遷移は、時点ｔk における情報ビット
０，１にそれぞれ対応して実線および破線の枝で示され
る。各枝に付されている２ビットの数値はそのときの畳
込み符号器の出力を表し、（ ）内の値はパスメトリッ
ク値を表す。
【０００５】いま、送信側の入力情報系列が“１１０１
００１０”であるとすると、畳込み符号器出力の符号系
列は、上述の生成行列より、“１１ １０ ００ ００
０１ １１ １１ ０１ ”となる。
００１０”であるとすると、畳込み符号器出力の符号系
列は、上述の生成行列より、“１１ １０ ００ ００
０１ １１ １１ ０１ ”となる。
【０００６】ここで、伝送路上においてこの出力符号系
列に雑音による誤り系列“００ ０１ ００ １０ ０
１ ００ ００ １０”が付加されたため、受信側では
受信系列として“１１ １１ ００ １０ ００ １１
１１ １１”というパターンが受信されたものとす
る。
列に雑音による誤り系列“００ ０１ ００ １０ ０
１ ００ ００ １０”が付加されたため、受信側では
受信系列として“１１ １１ ００ １０ ００ １１
１１ １１”というパターンが受信されたものとす
る。
【０００７】図５における各状態Ｓabは、状態Ｓ00が送
信側の畳込み符号器の遅延素子Ｄに入っている情報系列
が“００”、状態Ｓ10が“１０”、状態Ｓ01が“０
１”、状態Ｓ11が“１１”であることをそれぞれ表す。
信側の畳込み符号器の遅延素子Ｄに入っている情報系列
が“００”、状態Ｓ10が“１０”、状態Ｓ01が“０
１”、状態Ｓ11が“１１”であることをそれぞれ表す。
【０００８】このトレリス遷移図を説明すると、最初
（時点ｔ0 ）は状態Ｓ00から始まり、このとき畳込み符
号器に入力された情報系列が“０”であれば、畳込み符
号器は出力符号系列“００”を生成して状態Ｓ00に遷移
（実線の枝）し、一方、“１”であれば“１１”を生成
して状態Ｓ01に遷移（破線の枝）する。
（時点ｔ0 ）は状態Ｓ00から始まり、このとき畳込み符
号器に入力された情報系列が“０”であれば、畳込み符
号器は出力符号系列“００”を生成して状態Ｓ00に遷移
（実線の枝）し、一方、“１”であれば“１１”を生成
して状態Ｓ01に遷移（破線の枝）する。
【０００９】次に、時点ｔ1 においては、状態Ｓ00で情
報系列が“０”であれば、畳込み符号器は“００”を生
成して状態Ｓ00に遷移し、“１”であれば“１１”を生
成して状態Ｓ10に遷移する。状態Ｓ10では情報系列が
“０”であれば畳込み符号器では“０１”を生成して状
態Ｓ01に遷移し、“１”であれば“１０”を生成して状
態Ｓ11に遷移する。以下、同様の操作を繰り返す。
報系列が“０”であれば、畳込み符号器は“００”を生
成して状態Ｓ00に遷移し、“１”であれば“１１”を生
成して状態Ｓ10に遷移する。状態Ｓ10では情報系列が
“０”であれば畳込み符号器では“０１”を生成して状
態Ｓ01に遷移し、“１”であれば“１０”を生成して状
態Ｓ11に遷移する。以下、同様の操作を繰り返す。
【００１０】ここで、各時点ｔk での受信系列と各枝と
のハミング距離（枝メトリック）を計算し、トレリスに
沿った枝列をつなげて作られるパスの枝メトリックを加
算することでパスメトリックを求め、各時点で各状態Ｓ
abに入る複数のパスのうちその時点でのパスメトリック
が最小のものを生き残りパスとして選択し、最後に生き
残ったパス（すなわちパスメトリックが最小のパス）に
対応する入力情報系列を出力することで、送信側で送信
したと考えられることが最も確からしい入力情報系列を
推定し、伝送路での誤りを除去する。
のハミング距離（枝メトリック）を計算し、トレリスに
沿った枝列をつなげて作られるパスの枝メトリックを加
算することでパスメトリックを求め、各時点で各状態Ｓ
abに入る複数のパスのうちその時点でのパスメトリック
が最小のものを生き残りパスとして選択し、最後に生き
残ったパス（すなわちパスメトリックが最小のパス）に
対応する入力情報系列を出力することで、送信側で送信
したと考えられることが最も確からしい入力情報系列を
推定し、伝送路での誤りを除去する。
【００１１】上述の操作を行うための従来のビタビ復号
法の処理について以下に述べる。上述の二元畳込み符号
においては、図６に示されるように、４つの状態Ｓ00、
Ｓ10、Ｓ01、Ｓ11に対して情報ビット“０”、“１”が
入力されると、畳込み符号器からは図示の各出力符号が
出力される。これらの値をテーブル用ＲＯＭに格納して
おく。この畳込み符号器状態用メモリをtrelで表すこと
にすると、図７に示されるように、trel(0),trel(1) に
は状態Ｓ00に対し情報ビット“０”が入力した場合の畳
込み符号器の出力を格納し、trel(2),trel(3) には状態
Ｓ10に対し情報ビット“０”が入力した場合の畳込み符
号器の出力を格納し、・・・trel(6),trel(7) には状態
Ｓ11に対し情報ビット“０”が入力した場合の畳込み符
号器の出力を格納する。同様にtrel(8) 〜trel(15)には
各状態Ｓ00、Ｓ10、Ｓ01、Ｓ11に対し情報ビット“１”
が入力した場合の畳込み符号器の出力をそれぞれ格納す
る。
法の処理について以下に述べる。上述の二元畳込み符号
においては、図６に示されるように、４つの状態Ｓ00、
Ｓ10、Ｓ01、Ｓ11に対して情報ビット“０”、“１”が
入力されると、畳込み符号器からは図示の各出力符号が
出力される。これらの値をテーブル用ＲＯＭに格納して
おく。この畳込み符号器状態用メモリをtrelで表すこと
にすると、図７に示されるように、trel(0),trel(1) に
は状態Ｓ00に対し情報ビット“０”が入力した場合の畳
込み符号器の出力を格納し、trel(2),trel(3) には状態
Ｓ10に対し情報ビット“０”が入力した場合の畳込み符
号器の出力を格納し、・・・trel(6),trel(7) には状態
Ｓ11に対し情報ビット“０”が入力した場合の畳込み符
号器の出力を格納する。同様にtrel(8) 〜trel(15)には
各状態Ｓ00、Ｓ10、Ｓ01、Ｓ11に対し情報ビット“１”
が入力した場合の畳込み符号器の出力をそれぞれ格納す
る。
【００１２】すなわち、入力情報ビット“０”のときの
畳込み符号器の出力として、 trel(0) ＝０ trel(1) ＝０ 状態Ｓ00に対する畳込み符号器出力 trel(2) ＝０ trel(3) ＝１ 状態Ｓ10に対する畳込み符号器出力 trel(4) ＝１ trel(5) ＝１ 状態Ｓ01に対する畳込み符号器出力 trel(6) ＝１ trel(7) ＝０ 状態Ｓ00に対する畳込み符号器出力
畳込み符号器の出力として、 trel(0) ＝０ trel(1) ＝０ 状態Ｓ00に対する畳込み符号器出力 trel(2) ＝０ trel(3) ＝１ 状態Ｓ10に対する畳込み符号器出力 trel(4) ＝１ trel(5) ＝１ 状態Ｓ01に対する畳込み符号器出力 trel(6) ＝１ trel(7) ＝０ 状態Ｓ00に対する畳込み符号器出力
【００１３】入力情報ビット“１”のときの畳込み符号
器の出力として、 trel(8) ＝１ trel(9) ＝１ 状態Ｓ00に対する畳込み符号器出力 trel(10)＝１ trel(11)＝０ 状態Ｓ10に対する畳込み符号器出力 trel(12)＝０ trel(13)＝０ 状態Ｓ01に対する畳込み符号器出力 trel(14)＝０ trel(15)＝１ 状態Ｓ00に対する畳込み符号器出力 となる。
器の出力として、 trel(8) ＝１ trel(9) ＝１ 状態Ｓ00に対する畳込み符号器出力 trel(10)＝１ trel(11)＝０ 状態Ｓ10に対する畳込み符号器出力 trel(12)＝０ trel(13)＝０ 状態Ｓ01に対する畳込み符号器出力 trel(14)＝０ trel(15)＝１ 状態Ｓ00に対する畳込み符号器出力 となる。
【００１４】また、受信系列を格納する受信系列メモリ
をinp で表すことにすると、図５の例の場合には、inp
(0)・・・inp(7)・・・には受信系列“１１ １１ ０
０ １０ ００ １１ １１ １１・・・”が格納され
る。その他、各状態のメトリック値を格納するメトリッ
ク値メモリmetric、枝メトリックの計算の際に作業用に
用いるワーク用メモリwork、生き残りパスの情報を格納
するパスメモリpathmemが用意される。
をinp で表すことにすると、図５の例の場合には、inp
(0)・・・inp(7)・・・には受信系列“１１ １１ ０
０ １０ ００ １１ １１ １１・・・”が格納され
る。その他、各状態のメトリック値を格納するメトリッ
ク値メモリmetric、枝メトリックの計算の際に作業用に
用いるワーク用メモリwork、生き残りパスの情報を格納
するパスメモリpathmemが用意される。
【００１５】図８にはプロセッサ形のビタビ復号回路の
例が示される。図示するように、書換え可能なＲＡＭと
固定値を格納するＲＯＭが、それぞれデータバス＃１、
＃２に接続され、論理演算回路ＡＬＵへの演算入力用レ
ジスタとしてレジスタＡ、レジスタＢを、また演算結果
出力用レジスタとしてレジスタＣ、レジスタＤをそれぞ
れ備え、これらの各レジスタＡ、Ｂ、Ｃ、Ｄもデータバ
ス＃１、＃２に接続される。
例が示される。図示するように、書換え可能なＲＡＭと
固定値を格納するＲＯＭが、それぞれデータバス＃１、
＃２に接続され、論理演算回路ＡＬＵへの演算入力用レ
ジスタとしてレジスタＡ、レジスタＢを、また演算結果
出力用レジスタとしてレジスタＣ、レジスタＤをそれぞ
れ備え、これらの各レジスタＡ、Ｂ、Ｃ、Ｄもデータバ
ス＃１、＃２に接続される。
【００１６】図９には従来のビタビ復号法の処理手順が
示される。二元畳込み符号においては、各状態Ｓabに対
して受信系列データ二つが対応づけられ、各状態に対す
るパスメトリックを計算する。
示される。二元畳込み符号においては、各状態Ｓabに対
して受信系列データ二つが対応づけられ、各状態に対す
るパスメトリックを計算する。
【００１７】まず、受信系列inp(i),inp(i+1) とトレリ
スの各枝trel(j),trel(j+1) との枝メトリックをステッ
プＳ1 〜Ｓ１２で計算する。すなわち、受信系列inp
(i),inp(i+1) のうちのinp(i)をレジスタＡに、またtre
l(j) （ここではｊ＝１から始めるものとする）をレジ
スタＢにロードし (ステップＳ１) 、レジスタＡとレジ
スタＢの内容の排他的論理和を計算してレジスタＣに格
納する (ステップＳ２) 。次いで、受信系列inp(i),inp
(i+1) のうちのinp(i+1)をレジスタＡに、またtrel(j+
1) をレジスタＢにロードし (ステップＳ３) 、レジス
タＡとレジスタＢの内容の排他的論理和を計算してレジ
スタＤに格納する (ステップＳ４) 。次いで、レジスタ
ＣとレジスタＤの内容を加算することで状態Ｓ00に入る
入力情報ビット“０”対応の枝の枝メトリックを求め
て、これをメモリwork１に格納する。
スの各枝trel(j),trel(j+1) との枝メトリックをステッ
プＳ1 〜Ｓ１２で計算する。すなわち、受信系列inp
(i),inp(i+1) のうちのinp(i)をレジスタＡに、またtre
l(j) （ここではｊ＝１から始めるものとする）をレジ
スタＢにロードし (ステップＳ１) 、レジスタＡとレジ
スタＢの内容の排他的論理和を計算してレジスタＣに格
納する (ステップＳ２) 。次いで、受信系列inp(i),inp
(i+1) のうちのinp(i+1)をレジスタＡに、またtrel(j+
1) をレジスタＢにロードし (ステップＳ３) 、レジス
タＡとレジスタＢの内容の排他的論理和を計算してレジ
スタＤに格納する (ステップＳ４) 。次いで、レジスタ
ＣとレジスタＤの内容を加算することで状態Ｓ00に入る
入力情報ビット“０”対応の枝の枝メトリックを求め
て、これをメモリwork１に格納する。
【００１８】同様にして、受信系列inp(i)をレジスタＡ
に、またtrel(j+8) をレジスタＢにロードし (ステップ
Ｓ６) 、レジスタＡとレジスタＢの内容の排他的論理和
を計算してレジスタＣに格納し (ステップＳ７) 、次い
で、受信系列inp(i+1)をレジスタＡに、またtrel(j+9)
をレジスタＢにロードし (ステップＳ８) 、レジスタＡ
とレジスタＢの内容の排他的論理和を計算してレジスタ
Ｄに格納する (ステップＳ９) 。次いで、レジスタＣと
レジスタＤの内容を加算することで状態Ｓ00に入る入力
情報ビット“１”に対応する枝の枝メトリックを求め
て、これをメモリwork２に格納する。
に、またtrel(j+8) をレジスタＢにロードし (ステップ
Ｓ６) 、レジスタＡとレジスタＢの内容の排他的論理和
を計算してレジスタＣに格納し (ステップＳ７) 、次い
で、受信系列inp(i+1)をレジスタＡに、またtrel(j+9)
をレジスタＢにロードし (ステップＳ８) 、レジスタＡ
とレジスタＢの内容の排他的論理和を計算してレジスタ
Ｄに格納する (ステップＳ９) 。次いで、レジスタＣと
レジスタＤの内容を加算することで状態Ｓ00に入る入力
情報ビット“１”に対応する枝の枝メトリックを求め
て、これをメモリwork２に格納する。
【００１９】次に、上述のようにして求めた枝メトリッ
クに基づいてＡＣＳ (加算・比較・選択) 処理を行う
(ステップＳ１１) 。すなわち、求めた枝メトリックを
メモリwork１, work２からそれぞれ読み出して、その枝
のパスの一時点前のパスメトリック値metricと加算して
現時点でのパスメトリック値を計算し、このパスメトリ
ック値の大小を比較して、値の小なるほうを生き残りパ
スとして選択する。
クに基づいてＡＣＳ (加算・比較・選択) 処理を行う
(ステップＳ１１) 。すなわち、求めた枝メトリックを
メモリwork１, work２からそれぞれ読み出して、その枝
のパスの一時点前のパスメトリック値metricと加算して
現時点でのパスメトリック値を計算し、このパスメトリ
ック値の大小を比較して、値の小なるほうを生き残りパ
スとして選択する。
【００２０】このステップ１〜Ｓ１１の処理 (枝メトリ
ックの計算処理) をｊが７となるまで、順次にｊに２を
加算して更新しつつ繰り返し行う (ステップＳ１２) 。
これにより、他の状態Ｓ10、Ｓ01、Ｓ11についても順次
に枝メトリックを計算してそれに基づいてパスメトリッ
ク値を求め、生き残りパスを決定する。
ックの計算処理) をｊが７となるまで、順次にｊに２を
加算して更新しつつ繰り返し行う (ステップＳ１２) 。
これにより、他の状態Ｓ10、Ｓ01、Ｓ11についても順次
に枝メトリックを計算してそれに基づいてパスメトリッ
ク値を求め、生き残りパスを決定する。
【００２１】ステップ１〜Ｓ１１の処理が終了したら、
その結果に基づいて受信系列inp(i),inp(i+1) に対する
各枝のパスメトリック、すなわちパスメトリック値メモ
リmetric(0) 〜metric(7) の内容を更新する (ステップ
Ｓ１３) 。また生き残りパスの情報をパスメモリpathme
m に書き込む (ステップＳ１４) 。
その結果に基づいて受信系列inp(i),inp(i+1) に対する
各枝のパスメトリック、すなわちパスメトリック値メモ
リmetric(0) 〜metric(7) の内容を更新する (ステップ
Ｓ１３) 。また生き残りパスの情報をパスメモリpathme
m に書き込む (ステップＳ１４) 。
【００２２】次に、ｉに２を加算することでｉの値を更
新し (ステップＳ１５) 、上述のステップＳ１〜Ｓ１４
を繰り返すことで、次の受信系列に対してパスメトリッ
クの計算と生き残りパスの決定を行う。この処理をｉを
更新することで順次に行っていく。
新し (ステップＳ１５) 、上述のステップＳ１〜Ｓ１４
を繰り返すことで、次の受信系列に対してパスメトリッ
クの計算と生き残りパスの決定を行う。この処理をｉを
更新することで順次に行っていく。
【００２３】
【発明が解決しようとする課題】図９に示すフローチャ
ートからも分かるように、枝メトリック値の計算処理
（ステップＳ１〜Ｓ１２）は、二重ループのなかに組み
込まれており、従ってｉ、ｊを更新しつつ多数回繰り返
して実行する必要がある。このため、これをプロセッサ
で行う場合には膨大な演算量が必要となり、この演算量
は畳込み符号器の状態数、受信データ数が増えるにつれ
て増加する。この結果、プロセッサの負担が大きくな
り、またその演算処理に長時間を要するようになる。し
たがって、順次に入力された受信データに対してリアル
タイムで復号出力を得るためには、この演算量をできう
る限り削減する必要がある。
ートからも分かるように、枝メトリック値の計算処理
（ステップＳ１〜Ｓ１２）は、二重ループのなかに組み
込まれており、従ってｉ、ｊを更新しつつ多数回繰り返
して実行する必要がある。このため、これをプロセッサ
で行う場合には膨大な演算量が必要となり、この演算量
は畳込み符号器の状態数、受信データ数が増えるにつれ
て増加する。この結果、プロセッサの負担が大きくな
り、またその演算処理に長時間を要するようになる。し
たがって、順次に入力された受信データに対してリアル
タイムで復号出力を得るためには、この演算量をできう
る限り削減する必要がある。
【００２４】本発明はかかる問題点に鑑みてなされたも
のであり、その目的とするところは、枝メトリック計算
に要する演算量を大幅に削減することにある。
のであり、その目的とするところは、枝メトリック計算
に要する演算量を大幅に削減することにある。
【００２５】
【課題を解決するための手段】図１は本発明に係る原理
説明図である。図１中、１はメモリ、２はビタビ復号処
理を行うプロセッサを含む部分である。本発明のビタビ
復号方法は、畳込み符号化された受信系列をプロセッサ
により復号化するビタビ復号方法であって、各状態に対
応した枝メトリック値をテーブル化してメモリ１に記憶
させておき、生き残りパス選択のための演算にあたって
はメモリ１から枝メトリック値を読み出して使用するよ
うにしたものである。
説明図である。図１中、１はメモリ、２はビタビ復号処
理を行うプロセッサを含む部分である。本発明のビタビ
復号方法は、畳込み符号化された受信系列をプロセッサ
により復号化するビタビ復号方法であって、各状態に対
応した枝メトリック値をテーブル化してメモリ１に記憶
させておき、生き残りパス選択のための演算にあたって
はメモリ１から枝メトリック値を読み出して使用するよ
うにしたものである。
【００２６】上述のビタビ復号方法は、パンクチャド畳
込み符号化された受信系列に対する枝メトリック値をテ
ーブル化してメモリ１に記憶させることにより、パンク
チャド畳込み符号化した受信系列を復号化するようにで
きる。
込み符号化された受信系列に対する枝メトリック値をテ
ーブル化してメモリ１に記憶させることにより、パンク
チャド畳込み符号化した受信系列を復号化するようにで
きる。
【００２７】
【作用】従来のビタビ復号方法で演算量を要していた枝
メトリック値の計算を、枝メトリック値を記憶したメモ
リ１によるテーブル・ルック・アップ処理に置き換える
ことで、演算量を大幅に削減できる。
メトリック値の計算を、枝メトリック値を記憶したメモ
リ１によるテーブル・ルック・アップ処理に置き換える
ことで、演算量を大幅に削減できる。
【００２８】
【実施例】以下、図面を参照して本発明の実施例を説明
する。図２には本発明の一実施例としてのビタビ復号方
法の処理手順が示され、図３には実施例方法で用いる各
種メモリが示される。この実施例で用いるハードウェア
は図８に示したものと同じプロセッサ形の復号回路であ
る。メモリとしては従来の畳込み符号器状態用メモリtr
elに換えて枝メトリック値メモリpathが新たに用意され
ている。またワーク用メモリとしてメモリｋが用意され
ている。
する。図２には本発明の一実施例としてのビタビ復号方
法の処理手順が示され、図３には実施例方法で用いる各
種メモリが示される。この実施例で用いるハードウェア
は図８に示したものと同じプロセッサ形の復号回路であ
る。メモリとしては従来の畳込み符号器状態用メモリtr
elに換えて枝メトリック値メモリpathが新たに用意され
ている。またワーク用メモリとしてメモリｋが用意され
ている。
【００２９】各状態Ｓabにおいて、受信系列は、inp
(i),inp(i+1) の組合せが“００”、“１0 ”、“０1
”、“１1 ”を取りえる。したがって、各状態におい
て入力情報ビットが“０”と“１”のそれぞれに対する
枝メトリック値を予めテーブル化して枝メトリック値メ
モリpathに格納しておく。
(i),inp(i+1) の組合せが“００”、“１0 ”、“０1
”、“１1 ”を取りえる。したがって、各状態におい
て入力情報ビットが“０”と“１”のそれぞれに対する
枝メトリック値を予めテーブル化して枝メトリック値メ
モリpathに格納しておく。
【００３０】すなわち、状態Ｓ00においてinp(i),inp(i
+1) の組合せが“００”に対する枝メトリック「０」を
path(0) に、" ０1 ”に対する枝メトリック値「１」を
path(1) に、“１０”に対する枝メトリック値「１」を
path(2) に“１１”に対する枝メトリック値「２」をpa
th(3) にそれぞれテーブル値として格納する。以下同様
にして入力情報ビットが“０”のときの各状態Ｓ10、Ｓ
01、Ｓ11における枝メトリック値を順次に並べ、そのあ
とに、入力情報ビットが“１”のときの各状態Ｓ00、Ｓ
10、Ｓ01、Ｓ11における枝メトリック値を順次に並べ
る。すなわち、
+1) の組合せが“００”に対する枝メトリック「０」を
path(0) に、" ０1 ”に対する枝メトリック値「１」を
path(1) に、“１０”に対する枝メトリック値「１」を
path(2) に“１１”に対する枝メトリック値「２」をpa
th(3) にそれぞれテーブル値として格納する。以下同様
にして入力情報ビットが“０”のときの各状態Ｓ10、Ｓ
01、Ｓ11における枝メトリック値を順次に並べ、そのあ
とに、入力情報ビットが“１”のときの各状態Ｓ00、Ｓ
10、Ｓ01、Ｓ11における枝メトリック値を順次に並べ
る。すなわち、
【００３１】 inp(i),inp(i+1) 入力情報ビット 状態 枝メトリック値メモリ ００ ０ Ｓ00 path(0) ＝０ ０１ ０ Ｓ00 path(1) ＝１ １０ ０ Ｓ00 path(2) ＝１ １１ ０ Ｓ00 path(3) ＝２ ００ ０ Ｓ10 path(4) ＝１ ０１ ０ Ｓ10 path(5) ＝０ １０ ０ Ｓ10 path(6) ＝２ １１ ０ Ｓ10 path(7) ＝１ ００ ０ Ｓ01 path(8) ＝２ ０１ ０ Ｓ01 path(9) ＝１ １０ ０ Ｓ01 path(10)＝１ １１ ０ Ｓ01 path(11)＝０ ００ ０ Ｓ11 path(12)＝１ ０１ ０ Ｓ11 path(13)＝２ １０ ０ Ｓ11 path(14)＝０ １１ ０ Ｓ11 path(15)＝１ ００ １ Ｓ00 path(16)＝２ ０１ １ Ｓ00 path(17)＝１ １０ １ Ｓ00 path(18)＝１ １１ １ Ｓ00 path(19)＝０ ００ １ Ｓ10 path(20)＝１ ０１ １ Ｓ10 path(21)＝２ １０ １ Ｓ10 path(22)＝０ １１ １ Ｓ10 path(23)＝１ ００ １ Ｓ01 path(24)＝０ ０１ １ Ｓ01 path(25)＝１ １０ １ Ｓ01 path(26)＝１ １１ １ Ｓ01 path(27)＝２ ００ １ Ｓ11 path(28)＝１ ０１ １ Ｓ11 path(29)＝０ １０ １ Ｓ11 path(30)＝２ １１ １ Ｓ11 path(31)＝１
【００３２】この枝メトリック値メモリを用いた本発明
によるビタビ復号方法を図２のフローチャートを参照し
て以下に説明する。
によるビタビ復号方法を図２のフローチャートを参照し
て以下に説明する。
【００３３】この実施例方法においては、最適なパスを
選択する前に、受信系列データに対する枝メトリック値
メモリのアドレスを算出する（ステップＳ２１〜Ｓ２
３）。この演算は新たに追加されたものであるが、二重
ループの外で行うため、二重ループ内の演算（ステップ
Ｓ２４〜Ｓ２７）をそれ以上に削減することで、ビタビ
復号全体としての演算量は大きく削減される。本発明で
は二重ループ内の処理は入力情報ビット“０”のとき、
および入力情報ビット“１”のときの枝メトリック値を
それぞれメモリから読み出すだけの処理となるので、演
算量が大幅に削減される。
選択する前に、受信系列データに対する枝メトリック値
メモリのアドレスを算出する（ステップＳ２１〜Ｓ２
３）。この演算は新たに追加されたものであるが、二重
ループの外で行うため、二重ループ内の演算（ステップ
Ｓ２４〜Ｓ２７）をそれ以上に削減することで、ビタビ
復号全体としての演算量は大きく削減される。本発明で
は二重ループ内の処理は入力情報ビット“０”のとき、
および入力情報ビット“１”のときの枝メトリック値を
それぞれメモリから読み出すだけの処理となるので、演
算量が大幅に削減される。
【００３４】まず、枝メトリック値メモリpathのアドレ
スを算出する処理として、レジスタＡにinp(i)をロード
し、レジスタＢにinp(i+1)をロードし (ステップＳ２
１) 、レジスタＢとレジスタＡの内容を加算してその結
果をレジスタＣに格納し (ステップＳ２２) 、このレジ
スタＣの内容をさらにワーク用メモリｋに移して、この
ｋを枝メトリック値メモリpathを読み出すときのアドレ
スとする。
スを算出する処理として、レジスタＡにinp(i)をロード
し、レジスタＢにinp(i+1)をロードし (ステップＳ２
１) 、レジスタＢとレジスタＡの内容を加算してその結
果をレジスタＣに格納し (ステップＳ２２) 、このレジ
スタＣの内容をさらにワーク用メモリｋに移して、この
ｋを枝メトリック値メモリpathを読み出すときのアドレ
スとする。
【００３５】すなわち、上記のｋを用いて、枝メトリッ
ク値メモリpath(j+k) から枝メトリック値を読み出して
これをワーク用メモリwork１に格納する (ステップＳ２
４)。この枝メトリック値は入力情報ビットが“０”の
ときの値となる。
ク値メモリpath(j+k) から枝メトリック値を読み出して
これをワーク用メモリwork１に格納する (ステップＳ２
４)。この枝メトリック値は入力情報ビットが“０”の
ときの値となる。
【００３６】次に、枝メトリック値メモリpath(j+k+16)
から枝メトリック値を読み出してこれをワーク用メモリ
work２に格納する (ステップＳ２５) 。この枝メトリッ
ク値は入力情報ビットが“１”のときの値となる。
から枝メトリック値を読み出してこれをワーク用メモリ
work２に格納する (ステップＳ２５) 。この枝メトリッ
ク値は入力情報ビットが“１”のときの値となる。
【００３７】このワーク用メモリwork１, work２の内容
を用いて従来と同様のＡＣＳ (加算・比較・選択) 処理
を行ってパスメトリック値の計算、生き残りパスの選択
をする (ステップＳ２９) 。その後で、ｊに４を加算し
て更新し (ステップＳ２７)、ステップＳ２４〜Ｓ２６
の処理を繰り返す。これにより、同じ受信系列inp(i),i
np(i+1) に対して、状態Ｓ00、Ｓ10、Ｓ01、Ｓ11の枝メ
トリック値が順次に読み出されて処理されることにな
る。
を用いて従来と同様のＡＣＳ (加算・比較・選択) 処理
を行ってパスメトリック値の計算、生き残りパスの選択
をする (ステップＳ２９) 。その後で、ｊに４を加算し
て更新し (ステップＳ２７)、ステップＳ２４〜Ｓ２６
の処理を繰り返す。これにより、同じ受信系列inp(i),i
np(i+1) に対して、状態Ｓ00、Ｓ10、Ｓ01、Ｓ11の枝メ
トリック値が順次に読み出されて処理されることにな
る。
【００３８】その後で、メトリック値メモリの更新、生
き残りパスの書込みを従来方法と同じにして行い（ステ
ップＳ２８、Ｓ２９）、ｉに２を加算する更新を行って
（ステップＳ３０）、次の受信系列に対して同様の処理
を行う。
き残りパスの書込みを従来方法と同じにして行い（ステ
ップＳ２８、Ｓ２９）、ｉに２を加算する更新を行って
（ステップＳ３０）、次の受信系列に対して同様の処理
を行う。
【００３９】本発明の実施にあたっては種々の変形形態
が可能である。例えば本発明は、パンクチャド畳込み符
号化された受信系列に対しても、枝メトリック値メモリ
pathの値を書き換えるのみで対応可能である。このパン
クチャド畳込み符号化は、例えば特開昭５７−１５５８
５７号公報等に開示されているように、周波数利用効率
を高めるために、符号ビットの一部を消去することによ
り符号化率を高めた方式である。
が可能である。例えば本発明は、パンクチャド畳込み符
号化された受信系列に対しても、枝メトリック値メモリ
pathの値を書き換えるのみで対応可能である。このパン
クチャド畳込み符号化は、例えば特開昭５７−１５５８
５７号公報等に開示されているように、周波数利用効率
を高めるために、符号ビットの一部を消去することによ
り符号化率を高めた方式である。
【００４０】また、二つの多項式の次数が同じ場合 (本
発明の例で用いたような場合) には、図６からも分かる
ように、状態数が半分のテーブルを用意すればよい。
発明の例で用いたような場合) には、図６からも分かる
ように、状態数が半分のテーブルを用意すればよい。
【００４１】
【発明の効果】以上に説明したように、本発明によれ
ば、、枝メトリック計算に要する演算量を大幅に削減す
ることができる。
ば、、枝メトリック計算に要する演算量を大幅に削減す
ることができる。
【図１】本発明に係る原理説明図である。
【図２】本発明の一実施例としてのビタビ復号方法を示
すフローチャートである。
すフローチャートである。
【図３】実施例方法で用いる各種メモリを示す図であ
る。
る。
【図４】畳込み符号器の例を示す図である。
【図５】トレリス表現による遷移図である。
【図６】畳込み符号器の状態を示す図である。
【図７】従来方法で用いる各種メモリを示す図である。
【図８】プロセッサ形の復号器を示す図である。
【図９】従来のビタビ復号方法を示すフローチャートで
ある。
ある。
＃１、＃２ データバス ＲＡＭ ランダムアクセスメモリ ＲＯＭ 読出し専用メモリ Ａ、Ｂ、Ｃ、Ｄ レジスタ ＡＬＵ 論理演算回路 ｉｎｐ 受信系列メモリ ｐａｔｈ 枝メトリック値メモリ ｍｅｔｒｉｃ メトリック値メモリ ｐａｔｈｍｅｍ パスメモリ ｗｏｒｋ ワーク用メモリ ｔｒｅｌ 畳込み符号器状態用メモリ
Claims (2)
- 【請求項１】 畳込み符号化された受信系列をプロセッ
サにより復号化するビタビ復号方法であって、各状態に
対応した枝メトリック値をテーブル化してメモリ（１）
に記憶させておき、生き残りパス選択のための演算にあ
たっては該メモリから枝メトリック値を読み出して使用
するようにしたビタビ復号方法。 - 【請求項２】 パンクチャド畳込み符号化された受信系
列に対する枝メトリック値をテーブル化して該メモリに
記憶させることにより、パンクチャド畳込み符号化した
受信系列を復号化するようにした請求項１記載のビタビ
復号方法。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP19428493A JPH0730438A (ja) | 1993-07-09 | 1993-07-09 | ビタビ復号方法 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP19428493A JPH0730438A (ja) | 1993-07-09 | 1993-07-09 | ビタビ復号方法 |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| JPH0730438A true JPH0730438A (ja) | 1995-01-31 |
Family
ID=16322047
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP19428493A Withdrawn JPH0730438A (ja) | 1993-07-09 | 1993-07-09 | ビタビ復号方法 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JPH0730438A (ja) |
Cited By (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US6467064B1 (en) | 1999-03-19 | 2002-10-15 | Fujitsu Limited | Viterbi decoder |
| US6535345B1 (en) | 1999-07-21 | 2003-03-18 | Fujitsu Limited | Signal processing apparatus and signal processing method |
| US8808470B2 (en) | 2010-12-13 | 2014-08-19 | Nippon Steel & Sumitomo Metal Corporation | High-carbon chromium bearing steel and production method of the same |
-
1993
- 1993-07-09 JP JP19428493A patent/JPH0730438A/ja not_active Withdrawn
Cited By (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US6467064B1 (en) | 1999-03-19 | 2002-10-15 | Fujitsu Limited | Viterbi decoder |
| US6535345B1 (en) | 1999-07-21 | 2003-03-18 | Fujitsu Limited | Signal processing apparatus and signal processing method |
| US8808470B2 (en) | 2010-12-13 | 2014-08-19 | Nippon Steel & Sumitomo Metal Corporation | High-carbon chromium bearing steel and production method of the same |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US6448910B1 (en) | Method and apparatus for convolution encoding and viterbi decoding of data that utilize a configurable processor to configure a plurality of re-configurable processing elements | |
| CA2293079C (en) | A repeatable data error correction system | |
| JP3281868B2 (ja) | ビタビ復号方法 | |
| US7765459B2 (en) | Viterbi decoder and viterbi decoding method | |
| JP3233847B2 (ja) | ビタビ復号方法及びビタビ復号回路 | |
| US6697442B1 (en) | Viterbi decoding apparatus capable of shortening a decoding process time duration | |
| US8489972B2 (en) | Decoding method and decoding device | |
| US20070201586A1 (en) | Multi-rate viterbi decoder | |
| JPH0730438A (ja) | ビタビ復号方法 | |
| KR100262303B1 (ko) | 비터비알고리즘을적용하는복호과정에서의생존경로역추적방법및그장치 | |
| JP5370487B2 (ja) | 復号方法および復号装置 | |
| JP2591332B2 (ja) | 誤り訂正復号装置 | |
| JP3272173B2 (ja) | 誤り訂正符号／復号化装置 | |
| JP4295871B2 (ja) | 誤り訂正復号器 | |
| JP3837913B2 (ja) | ビタビ復号器 | |
| JP3351414B2 (ja) | ビタビ復号装置 | |
| US20070168845A1 (en) | Viterbi decoder | |
| JP3257060B2 (ja) | ビタビ復号器 | |
| JP4729938B2 (ja) | ビタビ復号器及びそれを用いる移動体通信装置、基地局装置、移動体通信端末 | |
| JP3269845B2 (ja) | ヴィタビ復号器 | |
| JP2002198827A (ja) | 最尤復号方法及び最尤復号器 | |
| KR100205547B1 (ko) | 비터비 디코더의 트레이스 백 장치 | |
| JPH11163742A (ja) | 軟出力復号装置 | |
| JP2000252840A (ja) | 誤り訂正復号器 | |
| JPH0832456A (ja) | ビタビ最尤復号装置 |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| A300 | Withdrawal of application because of no request for examination |
Free format text: JAPANESE INTERMEDIATE CODE: A300 Effective date: 20001003 |