JPH0832456A - ビタビ最尤復号装置 - Google Patents

Abstract

(57)【要約】 【目的】ビタビ最尤復号装置において、少ないメモリ量
で、簡単に各パスに対するブランチメトリックを得るこ
とを目的とする。 【構成】本発明は、各パスに対するブランチメトリック
を与える環状構造を持ったテーブル１０２を持ち、受信
系列が決まると、ブランチメトリック導出回路１０１に
より、前記テーブルの読み出しを始める位置を決め、決
められた読み出し方法によって前記テーブルの読み出し
を行ない、前記テーブルに対して、読み出しを始める位
置を更新していくことで、各状態に対応したブランチメ
トリックを導出し、ＡＣＳ回路１０３にその結果を与え
る。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明はビタビ最尤復号装置に関
する。

【０００２】

【従来の技術】ビタビ復号は畳み込み符号化されたデー
タをビタビアルゴリズムと呼ばれるアルゴリズムを用い
て行なう最尤復号である。

【０００３】ビタビ復号では、情報ビット１ビットに対
応する符号化データ（受信系列）を得るごとに、その時
点での各状態の生き残りパスのメトリック（累積計量）
を計算し、更新する演算処理を行なう。このとき、その
時点の受信系列の値に対して各パスが取るブランチメト
リックを毎回計算しては演算量が膨大になる。

【０００４】そこで、従来、ビタビ復号を使用した誤り
訂正復号装置は、あらかじめ各パスが取るブランチメト
リックの値を受信系列の値ごとに記憶したテーブルを記
憶回路に備え、それぞれの時点での受信系列の値に応じ
てテーブルから各ブランチメトリックの値を引き出すこ
とによって少ない演算で各状態のメトリックを計算し更
新していくことが出来るよう構成されている。

【０００５】図５および図６は、従来のビタビ復号を使
用した誤り訂正復号装置のブランチメトリック記憶回路
に記憶されているテーブル化されたブランチメトリック
の値の一例を示す図である。

【０００６】これは、符号化率＝９／１７、拘束長＝６
のパンクチャド符号で、生成多項式は、

【０００７】

【数１】

【０００８】である。また、パンクチャリングマトリッ
クスは、

【０００９】

【数２】

【００１０】である。このとき、ビタビ復号を使用した
誤り訂正復号装置において、拘束長Ｋ＝６より状態数は
３２となり、また硬判定復号を行なうとすると受信系列
は２ビットになり、ダミービットを含まない場合は、 Ａ：（０、０） Ｂ：（０、１） Ｃ：（１、０） Ｄ：（１、１） の４通りであり、また、ダミービット（＊で示す）を含
む場合、 Ｅ：（０、＊） Ｆ：（１、＊） の２通りに、それぞれ場合分けされる。また、各状態で
は１つ前の時点からその状態に伸ばすパスが２本あるの
で、Ａ〜Ｆのいずれにおいても各状態のブランチメトリ
ックの値は２つ持つことになる。このようにして得られ
たテーブルが図５および図６のものである。

【００１１】上記ビタビ復号を使用した誤り訂正復号装
置では、上述のようなテーブルを使用して次のように復
号化している。

【００１２】受信データが入力されると、受信系列がＡ
〜Ｆのどれに当たるかを判断し、それに応じてブランチ
メトリック記憶回路に記憶されている図５または図６に
示すようなテーブルにおける２本のパスのブランチメト
リック値を引き出し、その値と１つ前の時点からその状
態にパスを伸ばす２状態のメトリックの値とを、それぞ
れ加え比較することにより生き残りパスを決定する。

【００１３】このように、上記従来技術の誤り訂正復号
装置では、受信系列の値に対して各パスが取るブランチ
メトリックを毎回計算せずに、受信系列ごとのブランチ
メトリックのテーブルを用いることにより少ない演算量
でメトリックの計算をすることが出来る。

【００１４】

【発明が解決しようとする課題】しかしながら、上記従
来のビタビ復号の誤り訂正装置では、各受信系列ごとに
全てのブランチメトリックの値をメモリ回路に記憶して
おく必要があるため、多くのメモリ量を必要とするとい
う問題があった。

【００１５】また、それを解決するための手法として、
特開平４ー１７７９１７（Ｈ０３Ｍ１３／１２）がある
が、これは、受信系列に対して、ブランチメトリックの
候補を決めるテーブルと、状態に対して、その候補を組
み合わせるためのテーブルの２つのテーブルを引かなけ
ればならないため、１つのテーブルを引く方法に比して
処理量が増し、また、依然として多くのメモリ量を必要
とするという問題点があった。

【００１６】そこで、本発明は、上述した従来の問題を
解決するものであり、処理量の増加がなく、さらにメモ
リ量を大幅に減少させてビタビ復号を行なうことの出来
る優れたビタビ最尤復号装置を提供することを目的とす
るものである。

【００１７】

【課題を解決するための手段】上記の課題に鑑み、本発
明はビタビ最尤復号装置において、受信系列に対して、
各時点における各状態が取り得るパスのブランチメトリ
ックを与える環状構造、またはそれと同様の効果をもた
らすテーブルと、受信系列から前記テーブルを用い、各
状態が取り得るパスのブランチメトリックを導出するブ
ランチメトリック回路と、導出されたブランチメトリッ
クと前時点までの生き残りパスの累計メトリックを加算
比較するＡＣＳ回路と、その累計結果を記憶するメトリ
ック記憶回路と、比較結果を生き残りパスとして記憶す
るメトリック記憶回路を備え、受信系列が決まると、ブ
ランチメトリック導出回路は前記テーブルの読み出しを
始める位置を決め、決められた読み出し方法によって前
記テーブルの読み出しを行ない、前記テーブルに対し
て、読み出しを始める位置を更新していくことで、各状
態に対応したブランチメトリックを導出することを特徴
とするものである。

【００１８】

【作用】本発明は上記のような構成により次のような効
果を有する。受信系列が入力されると、その値から、ブ
ランチメトリックテーブルからブランチメトリックを読
み出すパターンと、リングバッファを読み出す時の基準
のアドレスの初期値が決まり、各状態に対して、読み出
しパターンに従った読み出しと基準アドレスの更新を繰
り返すことで、少ないメモリ量で簡単に各パスのブラン
チメトリックを得ることが出来る。

【００１９】

【実施例】以下、本発明について図示の実施例に基づい
て説明する。図１は本発明の実施例を示す図である。図
２、および図３は本発明の実施例で使用するブランチメ
トリックテーブルを示す説明図である。

【００２０】図１に示すビタビ最尤復号装置は、ブラン
チメトリック導出回路１０１と、ブランチメトリックテ
ーブル１０２と、ＡＣＳ回路１０３と、メトリック記憶
回路１０４と、パスメモリー回路１０５と最尤判定回路
１０６を備えており、下記のように構成されている。

【００２１】ここで、ブランチメトリック導出回路１０
１は受信データを入力端子Ｔｉから取り込み、ブランチ
メトリックテーブル１０２からブランチメトリックを求
め、加算比較（ＡＣＳ：Add Compare Select）回路１０
３にその結果を与える。ＡＣＳ回路１０３はブランチメ
トリック導出回路１０１からのブランチメトリックとメ
トリック記憶回路１０４からのメトリックを加算比較
し、メトリック値の少ない方を尤度の高いパスとして選
択し、パスメモリー回路１０５に記憶し、メトリック値
をメトリック記憶回路１０４に記憶する。最尤判定回路
１０６はパスメモリー回路１０５とメトリック記憶回路
１０４より、生き残りパスから復号結果を導出し、復号
データとして出力端子Ｔｏから出力する。

【００２２】ブランチメトリックテーブル１０２は、受
信符号がダミービットを含むパンクチャド符号の場合は
図２、および図３に示す２つのブランチメトリックテー
ブルから構成され、また受信符号がダミービットを含ま
ない畳み込み符号の場合は図２に示すブランチメトリッ
クテーブルのみから構成される。

【００２３】ところで、図２に示すテーブル２０１と図
３に示すテーブル３０１は、リング（環状）バッファ構
造を有するものになっている。リングバッファとはある
メモリ領域における最大番地の次の番地が最小番地に等
しくなる構造を持つバッファで、例えば２０１のテーブ
ル内容を読み出すためのアドレスを左から順に０、１、
２、３とすると、アドレス３を１増すとアドレス０にな
り、またアドレス２を３増すとアドレス１になる。この
ようなバッファを実現する方法の一つとしては、テーブ
ルに供給するアドレス信号線のうち、下位の何ビットか
のみを有効にする方法がある。２０１のテーブルのよう
にテーブルの要素数が４つの場合は、テーブルに供給さ
れるアドレス信号線のうち、下位２ビットのみを有効に
することで、所望のリングバッファ構造が得られる。

【００２４】次に、上記実施例の動作について以下に説
明する。受信符号が、符号化率Ｒ＝１／２、拘束長Ｋ＝
６の畳み込み符号で、生成多項式は、

【００２５】

【数３】

【００２６】とする。ビタビ復号を使用した誤り訂正復
号装置において、硬判定復号を行おうとすると、受信系
列は２ビットになり、 Ａ：（０、０） Ｂ：（０、１） Ｃ：（１、０） Ｄ：（１、１） の４通りである。これらは、それぞれ場合分けされる。
このとき、復号器のシフトレジスタが５ビットで構成さ
れているとするなら、ビタビ復号器において状態Ｓｉは
ｉ＝０〜３１の３２通りをとる。

【００２７】図４は、ある時点における状態Ｓ２ｎと状
態Ｓ２ｎ＋１に対し、一つ前の時点の状態Ｓｎと状態Ｓ
ｎ＋１６から４本のパスが伸びている様子を示してい
る。各状態について一つ前の時点から、その状態に伸び
るパスが２本あるので、ブランチメトリックの値は、 Ｐ２ｎ（ａ）、 Ｐ２ｎ（ｂ）、 Ｐ２ｎ＋１（ａ）、 Ｐ２ｎ＋１（ｂ） の４つがある。

【００２８】図２のブランチメトリックテーブルの内容
はこれら２つの状態に対応する Ｐ２ｎ（ａ）、 Ｐ２ｎ（ｂ）、 Ｐ２ｎ＋１（ａ）、 Ｐ２ｎ＋１（ｂ） の４つの値と、 その次の２つの状態に対応する Ｐ２ｎ＋２（ａ）、 Ｐ２ｎ＋２（ｂ）、 Ｐ２ｎ＋３（ａ）、 Ｐ２ｎ＋３（ｂ） の４つの値に対応している。すなわち一度のテーブル読
み出しに対し、４つの状態に対応する８つのブランチメ
トリックが読み出されることになる。これら８つの値と
ブランチメトリックテーブル２０１との対応関係は図２
におけるパターン１とパターン２の２種類の読み出しパ
ターンに分けられる。読み出しパターンは基準となるア
ドレスｒ、およびｒから相対的に離れたアドレスｒ＋
１、ｒ＋２、およびｒ＋３からテーブルの内容を読み出
す手段であり、パターン１とパターン２は状態がＳ０〜
Ｓ１５の時と、Ｓ１６〜３１の時とで使い分けられる。
すなわち受信信号が００、または１１の時は、 Ｓ０〜Ｓ１５：パターン１ Ｓ１５〜Ｓ０：パターン２ 受信信号が０１、または１０の時は、 Ｓ０〜Ｓ１５：パターン２ Ｓ１５〜Ｓ０：パターン１ の関係を持つ。

【００２９】ある時点において、受信信号を与えられた
ブランチメトリック回路は、まず受信信号に対して読む
出しパターンの基準アドレスｒを次のように初期化す
る。ブランチメトリックテーブルの内容が（０１２１）
であるとすると、受信信号が００、または０１の時は、
ｒ＝０に初期化し、受信信号が１０、または１１の時は
ｒ＝２に初期化する。ブランチメトリックテーブルはリ
ングバッファとして実現されているので、ｒ＝０の時、
ｒ、ｒ＋１、ｒ＋２、ｒ＋３は、それぞれ０、１、２、
１、に対応し、ｒ＝２の時は、それぞれ２、１、０、１
に対応する。

【００３０】次に、各状態Ｓ０〜３１で逐次行なわれる
処理について説明する。パターン１もしくはパターン２
に対応した方法で Ｓ２ｎ、 Ｓ２ｎ＋１、 Ｓ２ｎ＋２、 Ｓ２ｎ＋３ に伸びる計８つのパスに対応したブランチメトリックを
読みだす。メトリック読み出し後、読み出しパターンの
基準アドレスｒを１つ増やす。すなわち、基準アドレス
ｒ、ｒ＋１、ｒ＋２、ｒ＋３が、テーブルの値（０１２
１）に対応する読み出しが行なわれた後、次に読み出し
が行なわれる時、基準アドレスｒ、ｒ＋１、ｒ＋２、ｒ
＋３が、（１２１０）に対応する読み出しが行なわれる
ことになる。

【００３１】読み出されたブランチメトリックはＡＣＳ
回路１０３、メトリック記憶回路１０４により、前時点
までの生き残りパスの持つ累計メトリックにそれぞれ加
算され、Ｓ２ｎ、Ｓ２ｎ＋１に伸びる２つずつ計４つの
パスのうち、累計メトリックの少ない、すなわち尤度の
高いパスが一つずつ選択され、その結果がパスメモリー
回路１０５に記憶され、累計メトリックがメトリック記
憶回路１０４に記憶される。

【００３２】状態Ｓ１５からＳ１６に移る時は、前述し
たように読み出しパターンの変更が行なわれるが、基準
アドレスｒはあらためて初期化する必要はない。

【００３３】上記の処理を行なうことで、ある時点の受
信信号に対してＳ０〜３１に伸びる生き残りパスと、そ
れに対応した累計メトリックを求めることが出来る。

【００３４】また、受信符号が符号化率Ｒ＝９／１７、
拘束長Ｋ＝６のパンクチャド符号の場合、パンクチャリ
ングマトリックスを、

【００３５】

【数４】

【００３６】とすると、受信系列は上記Ａ〜Ｄの４通り
に加え、ダミービット（＊で示す）を含むので、 Ｅ：（０、＊） Ｆ：（１、＊） の２通りが増え、計６通りとなる。この場合、図２のブ
ランチメトリックテーブル２０１に加え、図３のブラン
チメトリックテーブル３０１を用いる。ブランチメトリ
ックテーブル３０１は２０１同様リングバッファにより
構成されているが、読み出しパターンは１種類のみであ
る。

【００３７】受信系列にダミービットが含まれる場合、
ブランチメトリック回路１０１はブランチメトリックテ
ーブル３０１を用い、受信系列がＥの場合、読み出しパ
ターンの基準アドレスｒを０に、受信系列がＦの場合
は、ｒを２に初期化する。

【００３８】次に、各状態Ｓ０〜３１での処理について
は読み出しパターンに従って、 Ｐ２ｎ（ａ）、 Ｐ２ｎ（ｂ）、 Ｐ２ｎ＋１（ａ）、 Ｐ２ｎ＋１（ｂ） の４つのブランチメトリックを読み出されるが、基準ア
ドレスｒは、受信系列Ａ〜Ｄの場合と異なり、読み出し
パターンにより２回の読み出しが行なわれた後で、２加
算される。それ以外のＡＣＳ回路１０３以降の動作は受
信系列がＡ〜Ｄの場合と変わるところはない。

【００３９】ここで受信系列にダミービットが含まれる
場合のブランチメトリックテーブル３０１は、テーブル
の内容が０と１の２通りだけであるので、読み出しパタ
ーンと基準アドレスの更新方法の変更により、０と１だ
けの２つの要素からなるリングバッファで構成すること
も出来る。

【００４０】このように上記実施例によれば、受信系列
により、リングバッファにより実現されたテーブルに対
する基準アドレスの初期化、読み出しパターンの選択を
行ない、各状態において、リングバッファの読み出しと
基準アドレスの更新を逐次行なうことで、ブランチメト
リックの値を容易に得ることができる。また、上記実施
例によれば、各受信系列ごとに全てのブランチメトリッ
クを記憶しておく必要がなく、わずかなメモリ量から構
成されるリングバッファを使用することで、メモリ量を
大幅に削減することが出来る。

【００４１】

【発明の効果】本発明によれば、ビタビ最尤復号装置に
おいて、受信系列に対して、各時点における各状態が取
り得るパスのブランチメトリックを与える環状構造、ま
たはそれと同様の効果をもたらすテーブルと、受信系列
から前記テーブルを用い、各状態が取り得るパスのブラ
ンチメトリックを導出するブランチメトリック回路と、
導出されたブランチメトリックと前時点までの生き残り
パスの累計メトリックを加算比較するＡＣＳ回路と、そ
の累計結果を記憶するメトリック記憶回路と、比較結果
を生き残りパスとして記憶するメトリック記憶回路を備
え、受信系列が決まると、ブランチメトリック導出回路
は前記テーブルの読み出しを始める位置を決め、決めら
れた読み出し方法によって前記テーブルの読み出しを行
ない、前記テーブルに対して、読み出しを始める位置を
更新していくことで、各状態に対応したブランチメトリ
ックを導出できるという利点を有する。そして、本発明
は、各受信系列に対して、全てのブランチメトリックを
メモリ回路に記憶しておく必要がなく、また２種類のテ
ーブルを介して、ブランチメトリックを求める必要がな
く、わずかなメモリ量から構成されるリングバッファを
使用することで、メモリ量を大幅に削減することが出来
るという効果を有する。

【図面の簡単な説明】

【図１】本発明の一実施例を示すブロック図である。

【図２】本発明の一実施例で使用するテーブルを表す図
である。

【図３】本発明の一実施例で使用するテーブルを表す図
である。

【図４】本発明の一実施例の作用を説明するための図で
ある。

【図５】従来装置で使用されているブランチメトリック
テーブルを示す説明図である。

【図６】従来装置で使用されているブランチメトリック
テーブルを示す説明図である。

【符号の説明】

１０１ ブランチメトリック導出回路 １０２ ブランチメトリックテーブル １０３ ＡＣＳ回路 １０４ メトリック記憶回路 １０５ パスメモリー回路 １０６ 最尤判定回路 ２０１ ブランチメトリックテーブル ３０１ ブランチメトリックテーブル

Claims (1)

【特許請求の範囲】
1. 【請求項１】 ビタビ最尤復号装置において、受信系列
   に対して、各時点における各状態が取り得るパスのブラ
   ンチメトリックを与える環状構造のテーブルと、受信系
   列から前記テーブルを用い、各状態が取り得るパスのブ
   ランチメトリックを導出するブランチメトリック回路
   と、導出されたブランチメトリックと前時点までの生き
   残りパスの累計メトリックを加算比較するＡＣＳ回路
   と、その累計結果を記憶するメトリック記憶回路と、比
   較結果を生き残りパスとして記憶するメトリック記憶回
   路を備え、受信系列が決まると、ブランチメトリック導
   出回路は前記テーブルの読み出しを始める位置を決め、
   決められた読み出し方法によって前記テーブルの読み出
   しを行ない、前記テーブルに対して読み出しを始める位
   置を更新することにより各状態に対応したブランチメト
   リックを導出することを特徴とするビタビ最尤復号装
   置。