JPS6162235A

JPS6162235A - ビタビ復号法

Info

Publication number: JPS6162235A
Application number: JP18489884A
Authority: JP
Inventors: Masato Tajima; 田島　正登; Hideo Suzuki; 秀夫鈴木
Original assignee: Toshiba Corp
Current assignee: Toshiba Corp
Priority date: 1984-09-04
Filing date: 1984-09-04
Publication date: 1986-03-31

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】〔発明の技術分野〕この発明は、たたみ込み符号等の復号に適したビタビ復
号法に関する。

〔発明の技術的背景とその問題点〕

たたみ込み符号化／ビタビ復号法は、ランダム誤りに対
して強力な誤り訂正が可能で、高い符号化利得を実現し
うる魅力的な誤り訂正方式として衛星通信システム等へ
の実際的な適用が実現されているが、特に近年、ディジ
タル信号処理技術やＩＣ技術の発展に伴なって、次第に
高速動作が可能で、かつより回路規模の小さなものへの
関心が高まってきている。しかし、一般にビタビ復号法
では、用いる符号の符号化率ｒが高くなるにつれて１復
号ステップ当りのｇＡ杯杯数数指数関数的に増大し、ま
た符号化率ｒを固定した場合、符号の拘束長にと共に復
号器のハードウェア規模が４５はり指数関数的に増大す
るという特質がある。従って、できるだけ回路規模の増
大を抑えて、しかも高速で動作させるための工夫が従来
より求められていた。

文献：　ｒ　Ｐ　ｒｏｃｅｅｄｉｎｏｓ　ｏｆ　ｔｈｅ
　Ｉ　Ｅ　Ｅ　Ｅ　ＪＶ　ｏｆ、６１．　Ｎ　ｏ、３．
ｐｐ　２Ｇ８〜２７８．１９７３４等により知られてい
るビタビ復号法について概略を説明する。

ビタビ復号法の対象となる受信信号の一例であるたたみ
込み符号の構造は通常、第１３図に示すような符号器の
内部状態を各時刻毎に書き出したトレリス（格子状図）
によって実現される。なお、第１３図はたたみ込み符号
の符号化率ｒが１／２゜拘束長Ｋが３の場合の例を示し
ている。

このようなトレリスを使うと、とタビ復号アルゴリズム
は次のように要約される。すなわち受信信号であるたた
み込み符号が入力される毎に、その時刻にの各内部状態
（黒点で示す）に対して１つの生残りパス、つまり初期
状態（既知とする）からスタートしてその着目した状態
に至るパスのうちで実際の受信信号系列との距１（これ
をパスメトリックと呼ぶ）がＲ短となるパスと、このよ
うにして決定される生残りパスの持つパスメトリックと
いう合計２種の量を更新して記憶してゆくものである。

ところで、第１３図の符号トレリスを注意深く観察する
と、時刻ｋからに＋１へと遷移する場合、第１４図に示
されるように４つの状態１１０　ＩＴ〜“３パから構成
される基本単位（これを単位セルという）に分割されて
いることがわかる。このことに注目すれば、ビタビ復号
アルゴリズムはざらに具体的に次のように表現される。

まず、時刻ｋに至るまでの復号演算が全て終了　　　１
１１している状態を想定し、ここで新たに受信信号が入
力されたとして、時刻に＋１における１つの状態Ｘ　（
ｋ＋１　）に対する更新パスメトリックおよび更新生残
りパスを算出する手順に注目する。第１４図に示される
基本セルの構造より、状態Ｘ（ｋ＋１）へ遷移する時刻
にの状態はＸ　（ｋ）およびＸ’　　（ｋ）に限定され
る。従って、これら２つの状態に対して記憶されている
パスメトリックＰ　（ｋ）およびＰ’　　（ｋ＞と、２
つの遷移Ｘ　（ｋ）→Ｘ　（ｋ＋１　）およびＸ’　　
（ｋ）→Ｘ（ｋ＋１）に伴うブランチメトリックλ（ｋ
）およびλ’　　（ｋ）（これらの値は入力受信信号に
依存して算出される）を使って、その和Ｐ　（ｋ）＋λ
（ｋ）とＰ’　　（ｋ）＋λ′　（ｋ）とを比較し、よ
り小さなパスメトリックに相当するパスをＸ（ｋ＋１＞
に対する更新生残りパスとして、またそれに対応するパ
スメトリックを更新パスメトリックとして新たに記１ｎ
すればよい。このような基本演算は、加算（ａｄｄ）、
比較（ｃｏｍｐａｒｅ　　）および選択（５ｅｌｅｃｔ
　）の３つの演算により構成されているので、通常ＡＣ
３演算と呼ばれ、これが符号器の内部状態数だけ繰返さ
れる。これによって時刻に＋１の全ての状態に対する更
新パスメトリックおよび更新生残りパスが決定され、同
時に次の復号ステップのために記憶される。

ところで、パスメトリックおよび生残りパスの記憶回路
には、通常ＲＡＭ　（ランダムアクセスメモリ）が使用
されるが、今までの説明から明らかなように復号ステッ
プ毎にＲＡＭからの読出しおよびＲＡＭへの書込みが反
復されることになる。

この場合、通常はＲＡＭのアドレスを直接、符号器の内
部状態に対応させるという方法（例えば内部状態“Ｏ１
１に対しＲＡＭのアドレス“ＯＩＩを対応させる）が採
用される。このため、単位セルを構成する時刻にと時刻
に＋１の状態が異なるという理由から、従来では一対の
ＲＡＭ　（ＲＡＭＩおＪ：びＲＡＭ２とする）を用意し
、復号ステップ毎に読出しと書込みを行なうＲＡＭを交
互に切換えるという方法がとられていた。すなわち、あ
る復帰ステップではＲＡＭＩより一方的に読出してＲＡ
Ｍ２へ一方的に書込み、次の復号ステップではＲＡＭ２
より一方的に読出してＲ’ＡＭ１へ一方的に書込むとい
う手順を繰返すものでおる。

しかし、このような方法では符号の拘束長と共に、特に
生残りパス記憶のための容量が増大するため、そのハー
ドウェアが膨大なものとなるという欠点があった。一方
、ＡＣ８演算回路については受信信号のデータごットレ
ートが比較的低い場合、１個のＡＣ３演算回路を時分割
的に共用する方法を採用し、データごットレートが高く
なる場合はＡＣ８演算回路を複数個設けて、いくつかの
内部状態に対するパスメトリックを同時に算出するとい
う方法が考えられる。但しこの場合、単にＡＣ３演算回
路の速度を上げても演算に伴う記憶回路の書込みおよび
読出しが演算のスピードに追随しなければ、本質的な高
速化にはならない。これに対処するためには、ＡＣ８演
算回路数に合せて記憶回路もまた複数個持てばよいと考
えられるが、ここで新たな問題が発生する。この問題点
を第１４図に示した単位セル構造を参照して説明する。

今、復号演算の高速化を考慮して２つのＡＣ８演算回路
を持つものと仮定し、ざらに説明の簡単のため、読出し
および書込み対応してそれぞれ２個ずつの記憶回路（メ
モリαとメモリβ、およびメ・モリα′とメモリβ′と
する）を持つものとする。時刻に＋１の状態゛○′°お
よび１１１　ＩＩに対するパスメトリックを算出する場
合、メモリαの０番地およびメモリβの２番地よりそれ
ぞれ時刻ｋにおける２つの状態ｒｉ　Ｏ″みよび“２″
に対するパスメトリックを同時に胱出し、それぞれＡＣ
３演算を実行した後、メモリα′の０番地およびメモリ
β′の１番地へ書込んだとする。同様に、時刻に＋１の
状態゛２”および“３″に対するパスメトリックを算出
するため、メモリαの１番地およびメモリβの３番地よ
り時刻ｋにおけるパスメトリックを同時に読出し、それ
ぞれＡＣ３演算を実行した後、メモリα′の２番地およ
びメモリ覧 β′の３番地へ書込むものとする。このように記　　　
ｆ　、、（、ｉ憶回路の読出し、書込みを行なうと、次
の復号ステップ、つまり時刻に＋２において例えば状態
“０パに対するパスメトリックを算出しようとする場合
、必要となる前の時刻に＋１の２つの状態、つまりＩＩ
　ＯＴｌおよび２″に対するパスメトリックは共にメモ
リα′に記憶されているので、同時には読出せない。従
って、これら２つの状態に対するパスメトリックを同時
に算出することは不可能である。

すなわち、高速化を目的としてＡＣ８演算回路を複数Ｉ
ＩＭｌ設け、それに合せて記憶回路もまた複数個設けた
としても、各記憶回路の読出しおよび書込み動作や、そ
の記憶番地を都合よく制御できなければ、効率の良いと
タビ復号回路を構成することはできない。　゛〔発明の目的〕この発明の目的は、演算スピードの高速化を図ると共に
、ハードウェア規模を効果的に縮小できるビタビ復号法
を提供することにある。

〔発明の概要〕

この発明は、パスメトリックおよび生残りバスを記憶す
るそれぞれＭＩＩ！ｉｆ　（１＜Ｍ＜符号トレリスの状
態数）のパスメトリックおよび生残りバス記憶回路と、
Ｍ個のパスメトリック記憶回路がら読出されるパスメト
リックを入力とし受信信号に基いて前記パスメトリック
記憶回路へ新たに書込むべき更新パスメトリックを演算
し、かつ前記生残りバス記憶回路へ新たに書込むべき更
新生残りバスを指定するＭ個の演算回路とを用い、ピタ
ご復号アルゴリズムに基いて受信信号を復号するビタピ
復号法であって、前記Ｍ個のパスメトリックおよび生残
りバス記憶回路からそれぞれ前記符号トレリスの異なる
状態に対応したパスメトリックおよび生残りバスを同時
に読出し、該演算回路から出力される更新パスメトリッ
クと、該演算回路によって指定される更新生残りパスを
それぞれ前記パスメトリックおよび生残りバス記憶回路
の直前の読出し番地と同一番地に同時に書込む一連の単
位動作を、前記パスメトリックおよび生残りバス記憶回
路の胱出しおよび書込み番地を各単位動作毎に異ならせ
て前記符号トレリスの状態数の１／Ｍ回繰返し、１復号
ステップを終了することを特徴とする。この場合、Ｍは
２のべき乗が適当である。

〔発明の効果〕

この発明によれば、復号動作の高速化のために？！２数
の演痒回路と同数のパスメトリックおよび生残りパス記
憶回路を設けた場合、各復号ステップで必要となる１時
刻前の状態に対するパスメトリックおよび生残りパスを
複数の記憶回路から常に分離して同時に読出せるように
制御し、さらにこのとき記憶容量を最大限有効に利用す
るため、読出した記憶回路と同一の記憶回路の、しかも
読出し番地と同一の番地へ再び書込を行なうという具合
に記憶回路の書込みおよび読出し動作を制御することに
より、演算スピードの高速化を図ると共に、記憶回路の
ハードウェア規模を従来の１／２に縮小することができ
る。しかも、このような記憶回路の制御方式の採用に伴
う煩雑さの増加は従来と同程度に抑えられる。

また、この発明によれば次のような副次的な効果も期待
できる。すなわち、従来のように書込みおよび読出しを
行なう記憶回路を分離し、復号ステップ毎に読出しと書
込みを交互に切操えるという方法を採用した場合、一方
の記憶回路の読出し動作が終了した後、直ちに書込み動
作へ移行することができず、演算に要する時間だけ遅れ
を持つ。

換言すれば、他方の記憶回路の書込み動作が完全に終了
するのを待って、初めて自込み動作へ移ることが可能と
なるので、このロスタイムのために演算効率の低下が避
けられなかった。

これに対し、この発明では読出しおよび次の書込みを同
一の記憶回路で行なうため、このようなロスタイムは存
在しない。従って記憶回路の書込みモードと読出しモー
ドとを交互に切換えることによって、受信信号の基本ク
ロックに完全に同期した動作を行なうことが可能となる
。

〔発明の実施例〕

以下、この発明の一実施例を説明するが、その前にこの
発明の中心をなす記憶回路の書込みおよ　　　８．１１
び読出し制御と番地制御に関して、−膜性を失うことな
く第１３図の符号トレリスおよび第１４図の単位セル構
造を使って詳細に説明する。なお、生残りバスの記憶動
作はパスメトリックの記憶動作に従属していると考える
ことができるので、パスメトリックの記憶動作にのみ注
目することにする。

第１４図の単位セル構造に着目し、ビタビ復号回路が２
つのＡＣ３演算回路（ＡＣ８αおよびＡＣ８βとする）
と、同数のパスメトリック記憶回路（メモリαおよびメ
モリβ）を持つものと仮定する。このとき、復号回路を
高速で動作させるためには、例えば時刻に＋１の状態に
対するパスメトリックを算出する場合、必要となる時刻
にの２つの状態に対するパスメトリックが常に２つのメ
モリα、βより分離して同時に読出ゼることが重要であ
る。従って、この要求を満たすように、１時刻前で都合
よくパスメトリックが２つのメモリα、βに分離されて
いなければならない。

この発明の原理を明確にするため、まず最初にパスメト
リック記憶回路が２組のメモリα、β。

およびα′、β′の４つある場合を想定してみる。

この場合、第１３図および第１４図の構造を持つ符号に
ついては、次のように記憶すればよいことがわかる。

メモリα（α′）・・・０．３メモリβ（β′）・・・１．２このような記憶原理に従えば、第１４図の単位セル構造
に注目して、記憶回路からの読出しおよび書込みが次の
ように表現される。

（メモリαの０番地とメモリβの２番地）より読出して
、ＡＣ８演算結果を【メモリα′の０番地とメモリβ′の１番地）へ書込む
。

（メモリβの１番地とメモリαの３番地）より読出して
、ＡＣ３８ｑ算結果を（メモリβ′の２番地とメモリα′の３番地）へ書込む
。

そして、次の時刻ではαおよびβと、α′およびβ′の
立場を反転させる。このようにすれば、時刻に＋１の状
態に対するパスメトリックを算出する場合に必要となる
時刻にの２つの状態に対するパスメトリックを、常に２
つのメモリより分離して同時に読出せることがわかる。

しかし、この方法では記憶回路の容■が増大する。回路
規模を抑制するためには、さらに読出しおよび書込みを
行なう記憶回路が共通となるように制御することが必要
である。但しこの場合、単にα−α′、β＝β′とする
ような単純な方法では不都合が生じることは明らかであ
る。しかし、ここで再び第１４図の単位セルの構造に注
目すれば、比較的簡単な繰返しの規則により復号演算の
高速化と、記憶容量の低減という２つの要求を同時に満
足させることができる。

第２図はこの発明による記憶回路の書込みおよび読出し
制御の方式を表したものであり、書込みを行なう記憶回
路と口込み番地が、その直前の読出しを行なった記憶回
路およびその読出し番地と一致していることが特徴的で
ある。

このように、この発明は単位セルを構成する１時刻前の
状態（つまり読出し側の状態）に対するパスメトリック
が記憶回路より常に分離して同時に読出せるようにする
と同時に、符号器の内部状態と記憶番地とを独立に考え
ることにより、同一の記憶回路の、直前の読出し番地と
同一の番地へ書込みを行なうことによって、記憶容量を
有効に使用しつつ、高速で復号ができるようにしたもの
である。

第１図はこの発明の一実施例のビタビ復号回路の構成を
示すものであり、ブランチメトリック発生回路１０１、
ＡＣ３演算回路１０２α、１０２β、パスメトリック記
憶回路１０３α、１０３β、第１の選択回路１０４、第
２の選択回路１０５、生残りバス記憶回路１０６α、１
０６β、第３の選択回路１０７、セレクタ１０８α、１
０８β、第４の選択回路１０９、バスセレクト回路１１
０および制御回路１１１により構成されている。

この実施例では、端子１０に入力される受信信号である
たたみ込み符号の拘束長Ｋが３．状態数ｔｉｚｓ−”″
４″ｒ　ｓ　８ｔ：　ｕ・ＡＣ３ａＮｉ［ｉｌｇ、？ｚ
＜　　　。

スメトリックおよび生残りバス記憶回路の個数ＭをＭ−
２としている。

以下、特にパスメトリック記憶回路１０３α。

１０３βおよび生残りバス記憶回路１０６α、１０６β
の動作に着目して説明を行なう。なお、前述と同様に一
般性を失うことのないように、受信信号が第１３図およ
び第１４図によって示されたたみ込み符号の場合に限定
して説明する。

今、時刻ｋに至るまでの復号演算が全て終了している状
態を想定し、ここで新たに受信信号が端子１・０より入
力されたとして、時刻に＋１の２つの状態“０″および
１′°に対する更新パスメトリックおよび更新生残りバ
スを決定し記憶する手順について考える。

まず、端子１０より受信信号データが入力されると、ブ
ランチメトリック発生回路１０１でそれに対応するブラ
ンチメトリックが計算され、これがＡＣ３演算回路１０
２α、１０２βへ同時に導かれる。一方、パスメトリッ
ク記憶回路１０３α。

１０３βへは、端子２０を介して外部から入力される基
準制御信号に基いて制御回路１１１で生成される記憶番
地制御信号が入力されており、この記憶番地制御信号に
従って第２図の記憶回路制御パターンに示される如く時
刻にの２つの状態“０゛′、“２″に対するパスメトリ
ックがパスメトリック記憶回路１０３α、１０３βの指
定の番地より同時に読出されて、第１の選択回路１０４
へ導かれる。第１の選択回路１０４へは同様に制御回路
１１１で生成される記憶回路制御信号が入力されており
、この記憶回路制御信号に従って上記２つのパスメトリ
ックが第２図の記憶回路制御パターンに示される如く所
定の配列でＡＣ８Ｉ算回路１０２α、１０２βに入力さ
れる。ＡＣ８演算回路１０２α、１０２βでこれらの入
力値に対して加算、比較および選択演算が実行され、状
態１１　Ｑ　ＩＴ　、　　ｌ“１”に対する更新パスメ
トリックがそれぞれＡＣ８演算回路１０２α、１０２β
で同時に決定される。そして、これらの更新パスメトリ
ックが共に第２の選択回路１０５へ導かれる。第２の選
択回路１０５へは制御回路１１１より第１の選択回路１
０４へ入力されているのと同じ記憶回路制御信号が入力
されており、この記憶回路制御信号に従って上記２つの
更新パスメトリックを記憶する記憶回路が、読出しが行
なわれた記憶回路と一致するように指定され、パスメト
リック記憶回路１０３α、１０３βへその更新パスメト
リックが分離して書込まれる。このとき２つのパスメト
リック記憶回路１０３α、１０３βへは同じく制御２１
１回路１１１により生成された記憶番地制御信号が入力
されており、この記憶番地制御信号に従って第２図に示
される如く読出し番地と同一番地へ更新パスメトリック
が書込まれる。すなわち、状態１１０　Ｉｌに対する更
新パスメトリックはパスメトリック記憶回路１０３αの
０番地へ、また状態゛１″に対する更新パスメトリック
はパスメトリック記憶回路１０３βの２番地へそれぞれ
書込まれる。

以上の動作は生残りパスについてもほぼ同様に適用され
る。すなわち、パスメトリックの読出しに同期して生残
りパス記憶回路１０６α、１ｏ６βの指定の番地より読
出された時刻にの２つの状態“Ｉ　Ｑ　Ｉｌ、“２パに
対する生残りパスは第３の選択回路１０７を経由してそ
れぞれ共にセレクタ１Ｏ８α、１０８βへ入力される。

一方、このときパスメトリック更新の過程でＡＣ８演算
回路１０２α、１０２βにおいて発生された生残りパス
指定信号が同じくセレクタ１０８α、１０８βに入力さ
れており、その生残りバス指定信号に基いて状態“ＩＱ
ＴＺ１１１″′に対する更新生残りパスが決定され、そ
れらが共に第４の選択回路１０９へ導かれる。第４の選
択回路１０９へはパスメトリック記憶回路へと同様に制
御回路１１１より記憶回路制御信号が入力されており、
この制御信号に従って２つの更新生残りパスを記憶する
記憶回路が、読出された記憶回路と一致するように指定
される。

さらに、上記２つの生残りパス記憶回路１０６α。

１０６βへ入力されている記憶番地制御信号に従って、
読出し番地と同一番地へ分離して同時に更新生残りパス
が書込まれる。

上述した基本演算は状態゛２″、および３″に対しても
同様に実行され、時刻に＋１の全ての　　　ｊ′１１状
態に対する更新パスメトリックおよび更新生残リパスが
それぞれ２つのパスメトリック記憶回路１０３α、１０
３βおよび生残りパス記憶回路１０６α、１０６βへ分
類して書込まれる。また、各更新生残りパスはパスセレ
クト回路１１０へも入力されており、それぞれの生残り
パスが持つ最古のビットに対して適当な判断を下すこと
によって最終的な復号結果が決定され、それが端子３０
へ復号出力信号として出力される。

次に、時刻に＋２における復号演算は、記憶回路制御信
号が第２図の後半に示される制御パターンによって支配
される以外は時刻に＋１のときと全く同様である。以下
、第２図に示される２個の制御モードが繰返し使用され
て復号動作が継続される。

こうして、制御回路１１１はパスメトリック記憶回路１
０３α、１０３βおよび生残りパス記憶回路１０６α、
１０６βの復号に使用されるそれぞれの番地のｌ８ｖｌ
が、受信信号であるたたみ込み符号の状態数と同じ数（
この例では４）となるように、これらの各記憶回路の出
込みおよび読出し動作を制御する。

なお、帰納法により容易に類推されるように、符号化率
ｒが１／２．拘束長がＫのたたみ込み符号に対しては、
制御パターン（書込みおよび読出し動作を制御すべき記
憶回路と当該記憶回路の書込みおよび読出しをすべき番
地との関係）の異なる（ｋ−１）個（上記例では２個）
の制御モードが現われることになるが、その構造は極め
て規則的なものである。従って、例えば予めこの制御モ
ード（ＩＩ！御パターン）を記憶したＲＯＭ　（読出し
専用メモリ）を設け、このＲＯＭの内容を規則的に読出
すことにより、容易に記憶回路の書込みおよび読出しを
制御することが可能である。

上記実施例ではＡＣ３演算回路、パスメトリックおよび
生残りパス記憶回路の個数Ｍが２以外の場合をも考慮し
てＡＣ８演算回路とパスメトリック記憶回路との間、お
よびセレクタと生残りパス記憶回路との間に選択回路を
設けたが、第２図の記憶回路制御図を第３図のように変
形することにより、Ｍ−２の場合にはこのような選択回
路を必要としない構成、すなわち第４図に示すようにＡ
Ｃ８演算回路とパスメトリック記憶回路との間、セレク
タと生残りパス記憶回路との間をそれぞれ直結して、番
地制御のみを行なうイｌり成とすることもできる。

また、以上の、説明では第１３図に示されるたたみ込み
符号に対してそれぞれ２個のＡＣ８演算回路とパスメト
リックおよび生残りパス記憶回路を設けたが、この発明
は任意の拘束長に、符号化率ｒのたたみ込み符号に対し
て、任意のＭ個（１〈Ｍ〈符号トレリスの状態数）のＡ
Ｃ８演算回路とパスメトリックおよび生残りパス記憶回
路を設ける場合に適用が可能である。Ｍは一般に２のべ
き乗である。その場合、所期の目的を達成するためには
最低限、直前の時刻において読出した記憶回路の読出し
た番地へ書込みを行なうという条件を満たすことが必要
であるが、さらに具体的には例えば次のような記憶回路
制御則を用いればよい。

すなわち、第１の制御則は例えば上記実施例のように、
たたみ込み符号の符号化率ｒがｒ＝１／２のとき、第２
図に示した如く書込みおよび読出しをすべき記憶回路番
号と当該記憶回路の書込みおよび読出しをすべき番地と
の関係を示す制御パターンが異なるに−１（Ｉ！！ｌの
制御モードを有し、各制御モードは２　Ｋ−１／Ｍ個の
ブロックに分割され、第１制御モードの第２ｍ（ｍ≧１
）ブロックの制御パターンが記憶回路番号に関して第（
２ｍ−１）ブロックの制御パターンの折返しパターンで
あるようにするというものである。但し、第２図はに−
３，Ｍ＝２の場合の例であり、それぞれＭ−２個の記憶
回路α、βからパスメトリック（または生残りパス）を
同時に読出し、それによって得られた更新パスメトリッ
クおよび更新生残リバスをそれぞれ２個の記憶回路α、
βの直前の読出し番地と同一番地に同時に書込むという
一連の単位動作を、各ブロックの制御パターンに従い読
出しおよび書込み番地を各単位動作毎に異ならせて、状
態数４の１置Ｍである２回繰返すことで　　　　　ｔｌ
つ（７）ｆｔｉ’Ｊ１２ｎｆ　　ｔ’に：Ｊ：８１１Ｍ
２？ッ７＃：ｉ；７７　　　　”ることを示している。

次に、第２の制御則は同様にｒ−１／２で、かつに−Ｎ
＋１の場合の制御パターンは、第１制御モードの第２ｍ
（ｍ≧１）ブロックの制御パターンが記憶回路番号に関
して第（２ｍ−１）ブロックの制御パターンの折返しパ
ターンであり、また第５図に示すように１＜−Ｎの場合
の制御パターンの延長とするというものである。

但し、第５図はに＝４．Ｍ＝２の場合の例であり、各モ
ードの左側は記憶回路番号を、また右側は読出しおよび
書込み番地を表す。各モードにおける各ブロックに記憶
回路番号として１，２の数字がそれぞれ１回だけ現われ
る条件を考慮して、Ａ−２，８＝１と決定される。

以下、任意のＫとＭに対しこのような制御則を適用する
ことにより、所望の制御パターンを１ｑることができる
。例えば第６図はｒ＝１／２．に＝４の場合の記憶回路
制御２′ｌＩ態様を示したもので、この例では４個の記
憶回路α１．β１．Ｃ２，Ｃ２が使用され、Ｃ１につい
ては０番地と７番地のみが、β１については３番地と４
番地のみが、Ｃ２。

については１番地と６番地のみが、そしてＣ２について
は２番地と５番地のみがそれぞれ使用されており、全体
で使用される記憶容量（番地数）は８となっている。こ
の容Ｈはちょうど符号トレリスの内部状態数２　”’１
−２’−１−２３−８に一致しており、このことは全体
として最少限（内部状態数分）の記憶番地を使って復号
がなされていることを意味する。

なお、上記説明では全て符号化率ｒが１／２という低符
号化率符号を復号する場合について説明したが、これが
１／２を越えるような高符号化率のたたみ込み符号を復
号するときの記憶回路制御則は以上の低符号化率符号に
対する記憶回路制御則から容易に導くことができる。

すなわち、ｒ−１／２を基準として内部状態数を一定（
２に−１）とすると、ｒ＝（ｎ−１）／ｎのたたみ込み
符号についてはｒ−１／２．拘束長に、Ｍ＝２”−１に
対する制御モードをｎ−２置きに選択したものとして実
現される。

例えばに＝７とすれば、ｒ＝２／３のときは第６図に示
したｒ＝１／２．Ｍ＝４に対する制御モ−ドを１つ置き
に３１択し、またｒ＝３／４のときはｒ＝１／２．Ｍ＝
８に対する制御モードを２つ置きに選択すればよい。

第７図、第８図はそれぞれ符号化率がｒ＝２／３、ｒ＝
３／４の場合の単位セルの構造を示したもので、また第
９図、第１０図はそれぞれ第７図第８図の単位セル（Ｒ
造に対応する記憶回路制御態様を示したものである。第
９図および第１０図においては、第６図と同様に各モー
ドの左側が記憶回路番号を、右側が読出しおよび書込み
番地をそれぞれ表している。

なお、復号に必要な記憶容量′＠最少限（符号トレリス
の内部状態数分）に抑えながらＡＣ８演算回路とパスメ
トリックおよび生残りパス記憶回路の数Ｍに比例した速
度で復号できるような記憶回路制御則のうち、第２図お
よび第６図で説明したような規則性を有しないものも存
在する。第１１図および第１２図はそのような記憶回路
制御態様の一例を示したものであり、符号化率ｒ−１／
２拘束長に＝５．Ｍ＝４の場合の例である。図に示すよ
うに第１制御モードの第２ブロツクおよび第４ブロツク
は記憶回路番号に関してそれぞれ第１ブロツクおよび第
３ブロツクの折返しパターンで表現されていないし、ま
たに＝４のときの制御則（第６図）の延長としても構成
されていない。但し、復号に使用されている記憶番地の
総数は１６で、符号トレリスの状態数２’−１−１６に
一致しており、この発明の目的が達成されている。

なお、この発明は上記した実施例に限定されるものでは
なく、例えば記憶回路制御則についてはさらに他の変形
が考えられ、要はＭ個のパスメトリンクおよび生残りパ
ス記憶回路から符号トレリスの異なる状態に対応したパ
スメトリックおよび生残りパスを同時に読出し、次いで
演算回路から出力される更新パスメトリックと、演算回
路によって指定される更新生残りパスをそれぞれパスメ
トリックおよび生残りパス記憶回路の直前の読出し番地
と同一番地へ同時に書込むという一連の単　　　＋□１
１位動作を、パスメトリックおよび生残りバス記憶回路
の読出しおよび書込み番地を各単位動作毎に異ならせて
符号トレリスの状態数の１／Ｍ回繰返すことで１復号ス
テップが完了するように、各記憶回路の制御を行なえば
よい。

また、以上の説明ではたたみ込み符号の復号の例を示し
たが、この発明のとタビ復号法は例えばＭ　Ｓ　Ｋ　（
ｍｉｎｉｍｕｍ　５ｈｉｒｔ　ｋｅｙｉｎｇ）信号等の
他の信号の復号にも適用することが可能である。

【図面の簡単な説明】

第１図はこの発明のとタビ復号法を適用したビタビ復号
回路の一実施例の回路構成図、第２図は同実施例にあけ
る記憶回路制御態様を示す図、第３図は第２図を変形し
た記憶回路制御態様を示す図、第４図は第３図の記憶回
路制御態様を使用したビタビ復号回路の回路構成図、第
５図は符号化率１／２．拘束長が２以上のたたみ込み符
号に対して演算回路および記憶回路数を２とした場合の
この発明に基く記憶回路制御態様を示す図、第６図は符
号化率１／２．拘束長４のたたみ込み符号に対して演算
回路および記憶回路数を４とした場合のこの発明に基く
記憶回路制御態様を示す図、第７図は符号化率２／３．
拘束長４のたたみ込み符号に対する符号トレリス上での
時刻ｋから時刻に＋１への遷移状態を表わす単位セルの
構造を示す図、第８図は符号化率３／４．拘束長３のた
たみ込み符号に対する符号トレリス上での時刻ｋから時
刻に＋１への遷移状態を表わす単位セルの構造を示す図
、第９図は第７図のたたみ込み符号に対して演算回路お
よび記憶回路数を４とした場合のこの発明に基く記憶回
路制御態様を示す図、第１０図は第８図のたたみ込み符
号に対して演算回路および記憶回路数を８とした場合の
この発明に基く記憶回路制御１１悪様を示す図、第１１
図および第１２図は符号化率１／２．拘束長５のたたみ
込み符号に対して演算回路および記憶回路数を４とした
場合の単位セルの構造とこの発明に基く記憶回路制御態
様を示す図、第１３図はたたみ込み符号の構造を表わす
符号トレリスの一例を示す図、第１４図は第１３図の符
号トレリス上での時刻ｋから時刻に＋１への遷移状態を
表わす単位セルの構造を示す図である。１０・・・受信信号（たたみ込み符号）入力端子、２０
・・・基準制御信号入力端子、１０１・・・ブランチメ
トリック発生回路、１０２α、１ｏ２β・・・ＡＣ８演
算回路、１０３α、１０３β・・・パスメトリック記憶
回路、１０４・・・第１の選択回路、１０５・・・第２
の選択回路、１０６α、１０６β・・・生残りパス記憶
回路、１０７・・・第３の選択回路、１０８α。１０８β・・・セレクタ、１０９・・・第４の選択回路
、１１０・・・パスセレクト回路、１１１・・・制御回
路。出願人代理人　弁理士　鈴江武彦第２　図モード＃１　　　　　　　　冠−Ｆ井２１＜　　　　　
　　　　　　ｋ令１　　　　　　　　　　ｋ条１　　　
　　　　　　ｋ争２（Ｒｅａ（１）　　　（Ｗｒｉｔｅ
）　　　　（Ｒｅａｄ）　　　（Ｗｒｉｔｅ）第３図ｋ　　　　　　　　　　　　　　　　　ｋや１　　　　
　　　　　　　　　　ｋ争１　　　　　　　　　　　　
　　ｋ会２（Ｒｅａｄ）　　　　（Ｗｒｉｔｅ）　　　
　　（Ｒｅａｃｊ　）　　　　（Ｗｒｉｔｅ）第４図第５図第７図第８図第１３図第１４図

Claims

【特許請求の範囲】

（１）パスメトリックおよび生残りパスを記憶するそれ
ぞれＭ個（１＜Ｍ＜符号トレリスの状態数）のパスメト
リックおよび生残りパス記憶回路と、Ｍ個のパスメトリ
ック記憶回路から読出されるパスメトリックを入力とし
受信信号に基いて前記パスメトリック記憶回路へ新たに
書込むべき更新パスメトリックを演算し、かつ前記生残
りパス記憶回路へ新たに書込むべき更新生残りパスを指
定するＭ個の演算回路とを用い、ビタビ復号アルゴリズ
ムに基いて受信信号を復号するビタビ復号法であって、
前記Ｍ個のパスメトリックおよび生残りパス記憶回路か
らそれぞれ前記符号トレリスの異なる状態に対応したパ
スメトリックおよび生残りパスを同時に読出し、該演算
回路から出力される更新パスメトリックと、該演算回路
によって指定される更新生残りパスをそれぞれ前記パス
メトリックおよび生残りパス記憶回路の直前の読出し番
地と同一番地に同時に書込む一連の単位動作を、前記パ
スメトリックおよび生残りパス記憶回路の読出しおよび
書込み番地を各単位動作毎に異ならせて前記符号トレリ
スの状態数の１／Ｍ回繰返し、１復号ステップを終了す
ることを特徴とするビタビ復号法。
（２）Ｍが２のべき乗であることを特徴とする特許請求
の範囲第１項記載のビタビ復号法。