JPS63126325A - シ−ケンシヤル復号器 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 〔）既要〕 サブスタックを設けたシーケンシャル復号器に於いて、
親ノードカψ技を伸ばした子ノードのメトリック値が増
加した時は、サブスタックを用いて最大メトリック値の
ノードの検索処理及びサブスタックの更新処理を省略し
て、復号処理の高速化を図るものである。

〔産業上の利用分野〕

本発明は、スタックアルゴリズムを用いて畳込み符号の
誤り訂正復号を行うシーケンシャル復号器に関するもの
である。

シーケンシャル復号器（Ｓｅｑｕｅｎｔｉａｌ　ｄｅｃ
ｏｄｅｒ）（逐次復号２５）は、局所的に最も確からし
いバスを選択することにより、畳込み符号の誤り訂正復
号を行うものであり、誤り訂正能力が大きいことから、
衛星通信方式等に於ける復号器として使用されている。

又スタックアルゴリズム（Ｓ　ｔａｃｋ　ａｌｇｏｒｉ
ｔｈｍ）を用いたシーケンシャル復号方式は、ファノア
ルゴリズム（Ｆ　ａｎｏ　ａｌｇｏｒｉ　ｔｈｍ）を用
いたシーケンシャル復号方式に比較して、所要演算量が
少なくて済み、且つ通信回線の品質が悪い場合でも、誤
り訂正能力の劣化が小さい利点がある。しかし、その反
面、−回の演算に要する時間が長くなる為、復号速度を
向上することが容易でなく、且つ大容量のメモリを必要
とし回路規模が大きくなるものである。従って、高速動
作が可能で且つ回路規模が小さいスタックアルゴリズム
を用いたシーケンシャル復号器が要望されている。

〔従来の技術〕

スタックアルゴリズムを用いたシーケンシャル復号器は
、符号化率をＲｗ　ｎ　／　ｍとすると、未だ技を伸ば
したことがないノードのうちで、メトリック値が最大の
ノードから２１本の枝を伸ばしていくことにより復号す
るものである。ノードのメトリック値は、そのノードに
至るバスの確からしさを表す尤度値であり、メトリック
値が大きい程、そのバスが正しいバスである確率が高い
と見做されている。

第４図はシーケンシャル復号器の要部ブロック図であり
、２１は受信符号を一旦蓄積する受信バッファ、２２は
ノードから技を伸ばす処理等を行う計算処理部、２３は
ノード対応のアドレスを有するスタックメモリ部、２４
は＋１回路、２５は内部符号化器、２６はブランチメト
リック計算部、２７は加算器、２８はノードの木構造に
於ける深さを記憶させる深さスタックメモリ、２９はノ
ードの内部状態を記憶させる内部状態スタックメモリ、
３０はノードのメトリック値を記憶させるメトリック値
スタックメモリである。

未だ技を伸ばしていないノードのうちのメトリック値が
最大のノードを検索し、そのノードに関する情報、即ち
、そのノードの深さ、内部状態、メトリック値をそれぞ
れ深さスタックメモリ２８、内部状態スタックメモリ２
９、メトリック値スタックメモリ３０から読出して、計
算処理部２２に於いて新しいノードに関する情報を計算
する。

即ち、＋１回路により新しいノードの深さＣが得られ、
内部符号化器２５から新しいノードの内部状１ｂが出力
され、加算器２７から新しいノードのメトリック値ａが
出力される。

これらの新しいノードに関する情報ａ、ｂ、ｃはスタッ
クメモリ部２３に加えられ、深さスタックメモリ２８．
内部状態スタックメモリ２９及びメトリック値スタック
メモリ３０の新しいノードに対応するアドレスに書込ま
れる。

そして、１ブロツクの復号処理が終了すると、メトリッ
ク値が最大のノードのバスをトレースバックして、復号
出力を得るものである。

前述のメトリック値が最大のノードの検索処理を高速化
する為に、サブスタックを用いる構成が知られている。

即ち、第５図に示すように、サブスタック３４を設ける
ものであり、３１は受信バッファ、３２は枝を伸ばす処
理等を行う計算処理部、３３はスタックメモリ部、３５
はメトリック値が最大のノードを検索するノード検索部
、３６はメトリック値が最大となるノードの親ノードを
記憶αするバスメモリ、３７はバストレースにより復号
出力を得るバストレース部である。

サブスタック３４は、メトリック値をアドレスとして、
そのメトリック値を有するノードに関する情報が記憶さ
れているスタックメモリ部３３のアドレスを記憶するメ
モリであり、新しいノードのメトリック値に応じて更新
される。又スタックメモリ部３３は、第４図に於けるス
タックメモリ部２３と同様の構成を有し、新しいノード
に関する深さ、内部状態、メトリック値等の情報を、ノ
ードに対応したアドレスに記憶しているものである。

ノード検索部３５は、サブスタック３４に書込まれてい
るスタックメモリ部３３のアドレス値から、最大のメト
リック値を有するノーζを容易に検索することができる
もので、そのノードに関する情報がスタックメモリ部３
３から読出されて計算処理部３２に加えられ、次の新し
いノードに関する情報が計算されてスタックメモリ部３
３に書込まれると共に、サブスタック３４の更新が行わ
れる。

第６図は従来例のフローチャートを示し、復号開始によ
り、ノード検索部３５によりサブスタック３４を用いて
メトリック値が最大の節点（ノードＮｍａ　ｘ）を検索
する０゜次にこのメトリック値が最大のノードＮｍａｘ
をサブスタック３４から削除する０゜即ち、一度技を伸
ばしたノードからは、再度技を伸ばす処理を行わないの
で、そのノードは不要となるから削除するものである。

次に、メトリック値が最大のノードＮｍａｘの深さ、状
態番号（内部状Ｂ＞、メトリック値等の情報をスタック
メモリ部３３から読出す■。この読出したノードＮｍａ
ｘの深さに対応する受信符号を受信バッファ３１から読
出す［相］。そして、このノードＮｍａｘから新しい技
を伸ばす処理を行う［相］。即ち、ステップ０．＠ｌで
読出した情報を用いて、計算処理部３２で新しいノード
のメトリック値等の計算を行うものである。

次にステップ［相］で求めた新しいノードの深さ。

内部状態、メトリック値等の情報をスタックメモリ部３
３へ書込む［相］。そして、１ブロック分の復号処理が
終了したか否か判断する０゜終了していない場合は、ス
テップ０から処理を繰り返す。又終了している場合は、
バスのトレースバックにより最尤バスを決定し［相］、
その最尤バスによって復号出力を決定する。そして、サ
ブスタック３４をクリアする［相］。

第７図は従来例のタイムチャートを、１回の演算（技を
伸ばす処理）について示すものであり、（ａｌは受信バ
ッファ３１に対するアクセス、（ｂｌは計算処理部３２
に於けるメトリック値の計算、（Ｃ）はスタックメモリ
部３３に対するアクセス、ｆｄ）はサブスタック３４に
対するアクセスを示す。サブスタック３４に対して、（
ｄ）及び第６図に於けるステップ■に示すように、メト
リック値の最大のノードＮｍａｘを検索し、次にステッ
プ［相］に示すように、そのノードＮｍａｘを削除する
。又そのノードＮｍａ　ｘの情報を（Ｃ）及びステップ
０に示すようにスタックメモリ部３３から読出し、（ａ
）及びステップ［相］に示すように、ノードＮｍａ　ｘ
の深さに対応する受信符号を受信バッファ３工から読出
し、ｆｂ）及びステップ■に示すように、新しいノード
のメトリック値の計算を行う。計算結果を（Ｃ）及びス
テップ［相］に示すように、スタックメモリ部３３に書
込み、又（ｄ）に示すように、サブスタック３４を更新
する。

第８図（Ａ）〜（Ｊ）は復号過程説明図で、ノードから
２本の技を伸ばして復号する場合について示す。同図に
於いて、スタックメモリ部３３は、スタックポインタ５
ＴＡＫＰＴ、メトリック値スタックメモリＶＡＬＵＥ、
内部状態スタックメモリ５ＴＡＴＥ等から構成され、ノ
ード対応のアドレスを有するものである。又サブスタッ
クＡＵＸＰＴ３４は、メトリック値をアドレスとして、
スタックメモリ部３３のノード対応のアドレスが書込ま
れるものである。尚、Ｅはエンプティ　（空）を示し、
黒丸は展開済み（技を伸ばした）ノード、白丸は未展開
（技を伸ばしていない）ノードを示す。

第８図の（Ａ）は深さｌの場合を示し、始点のノードＮ
Ｏは、スタックメモリ部３３のアドレス０に対応し、初
期値０のメトリック値としているので、スタックメモリ
部３３のメトリック値スタックメモリＶＡＬＵＥのアド
レス０に０が書込まれている。又このノードＮＯから２
本の枝を伸ばしたノードＮｌ、Ｎ２は、スタックメモリ
部３３のアドレス１．２に対応し、それぞれのメトリッ
ク値の計算結果が−１，−２の時、メトリック値スタッ
クメモリＶＡＬＵＥのアドレス１．２にそれぞれ−１，
−２が書込まれる。又内部状態スタックメモリ５ＴＡＴ
Ｅ等に対する書込みも行われる。

スタックメモリ部３３に対する書込みが終了すると、そ
のアドレスｌ、２と、書込んだメトリック値−１，−２
との対応を基に、サブスタックＡＵＸＰＴの更新が行わ
れる。即ち、メトリック値をアドレスとして、ノードＮ
ｌ、Ｎ２対応のアドレス１，２が書込まれる。従って、
メトリック値が最大のノードは、この場合、サブスタッ
クＡＵＸＰＴのメトリック値−１対応のアドレスに書込
まれている１から、Ｎ１であることが容易に識別される
。

第８図の（Ｂ）は深さ２の場合で、ノードＮ１から技を
伸ばした場合を示す。この場合のノードＮ３．Ｎ４のメ
トリック値が＋３．−２であり、スタックメモリ部３３
のメトリック値スタックメモリＶＡＬＵＥのノードＮ３
．Ｎ４対応のアドレス３．４にそれぞれメトリック値の
＋３．−２が書込まれる。

そして、サブスタックＡＵＸＰＴの更新が行われる。こ
の場合、技を伸ばしたノードがＮｌであったから、サブ
スタックＡＵＸＰＴのメトリック値−１に対応したアド
レスの１がクリア（エンプティＥに更新）される。この
処理は、スタックポインタ５ＴＡＫＰＴのアドレス１の
内容がエンプティＥであり、メトリック値スタックメモ
リＶＡＬＵＥのアドレス１の内容が−１であるから、こ
れらが読出され、−１をサブスタックＡＵＸＰＴのアド
レスとして、読出されたエンプティＥの書込みを行うこ
とになる。

又サブスタックＡＵＸＰＴには、ノードＮ３のメトリッ
ク値の＋３をアドレスとして、ノードＮ３対応のアドレ
スの３が書込まれ、ノードＮ４のメトリック値の−２を
アドレスとして、ノードＮ４対応のアドレスの４が書込
まれる。この場合、メトリック値−２対応のアドレスに
は、前回のノードＮ２対応のアドレス２が書込まれてい
たので、この２をスタックポインタ５ＴＡＫＰＴのアド
レス４に転送して書込む。即ち、スタックポインタ５Ｔ
ＡＫＰＴにより、メトリック値が−２の前回のノードは
Ｎ２であることを表示するものである。

この場合もサブスタックＡＵＸＰＴのメトリック値＋３
対応のアドレスに書込まれている３から、メトリック値
が最大のノードはＮ３であることが容易に識別できる。

従って、次にノードＮ３から枝が伸ばされる。

第８図の（Ｃ）は深さ３の場合で、ノードＮ３から枝を
伸ばしたノードＮ５．Ｎ６を示ず。ノードＮ５．Ｎ６の
メトリック値が＋４．＋２であり、スタックメモリ部３
３のメトリック値スタックメモリＶＡＬＵＥのノードＮ
５．Ｎ６対応のアドレス５．６にそれぞれメトリック値
＋４．＋２が書込まれる。そして、サブスタックＡＵＸ
ＰＴには、前述と同様に、ノードＮ３についてのメトリ
ック値＋３対応のアドレスの３は、スタックポインタ５
ＴＡＫＰＴのアドレス３の内容がエンプティＥであるか
ら、このＥに更新され、又メトリック値＋４．＋２対応
のアドレスに、５．６が書込まれる。そして、サブスタ
ックＡＵＸＰＴのメトリック値＋４対応のアドレスの５
から、メトリック値が最大のノードはＮ５であることが
識別され、次はノードＮ５から枝が伸ばされる。

第８図の（Ｄ）は深さ４の場合で、ノードＮ５から枝を
伸ばしたノードＮ７．Ｎ８を示す。前述の場合と同様に
、スタックメモリ部３３のメトリック値スタックメモリ
ＶＡＬＵＥのノードＮ７゜Ｎ８対応のアドレス７．８に
メトリック値＋２゜＋１がそれぞれ書込まれる。そして
、サブスタックＡＵＸＰＴの更新が行われる。即ち、ノ
ードＮ５についてのメトリック値＋４対応のアドレスの
５がエンプティＥに更新され、メトリック値＋２対応の
アドレスに７、メトリック値＋１対応のアドレスに８が
それぞれ書込まれる。この場合、メトリック値＋２対応
のアドレスには、前回のノードＮ６対応のアドレスの６
が書込まれていたから、スタックポインタ５ＴＡＫＰＴ
のアドレス７にごの６を転送して書込み、メトリック値
＋２の前回のノードがＮ６であることを表示する。

第８図の（Ｅ）は深さ５の場合で、ノードＮ７から枝を
伸ばしたノードＮ９．ＮＩＯを示す。この場合のメトリ
ック値は共に−２であり、メトリソクイ直スタックメモ
リＶＡＬＵＥのノードＮ９゜ＮＩＯ対応のアドレス９．
１０に−２が書込まれる。

又サブスタックＡＵＸＰＴに於いて、ノードＮ７につい
てのメトリック値＋２対応のアドレスの７は、スタック
ポインタＳ　Ｔ　Ａ　Ｋ　Ｐ　Ｔのアドレス７の内容が
６であるから、この６が転送されて更新される。又ノー
ドＮ９．Ｎ１０についてのメトリック値−２対応のアド
レスに、ノードＮ１２対応のアドレスの１０が書込まれ
、スタックポインタ５ＴＡＫＰＴのアドレス９には、前
回のサブスタックＡＵＸＰＴのメトリック値−２対応の
アドレスの４が転送されて書込まれ、又スタックポイン
タ５ＴＡＫＰＴのアドレス１０には、ノードＮ９のアド
レスの９が書込まれる。従って、未展開で、同一のメト
リック値−２を有するノードは、スタックポインタ５Ｔ
ＡＫＰＴを矢印の経路でたどることにより、識別するこ
とができる。

この場合のノードＮ９．ＮＩＯはメトリック値が未展開
のノードＮ６．Ｎ８のメトリック値より小さいので、未
展開のノードＮ２．Ｎ４．Ｎ６゜Ｎ８のうちの最大のメ
トリック値を有するノードＮ６を見つけて技を伸ばすこ
とになる。その為に、サブスタックＡＵＸＰＴを検索す
ると、メ］・リンク値＋２対応のアドレスに６が書込ま
れているので、次はノードＮ６に戻って枝を伸ばすこと
になる。

第８図の（Ｆ）は深さ３のノードＮ６に戻って技を伸ば
した場合を示し、メトリック値が一←４゜−２のノード
ＮＩＬ、Ｎ１２に展開され、メトリック値が最大の＋４
のノードＮｉｌから次に技が伸ばされる。サブスタック
ＡＵＸＰＴについても前述の場合と同様にミメトリソク
値＋４対応のアドレスに、ノードＮｉｌ対応のアドレス
の１１が書込まれることになり、又メトリック値＋２対
応のアドレスの６はエンプティＥに更新され、メトリッ
ク値−２対応のアドレスの１０は、ノードＮ１２対応の
アドレスの１２に更新される。

第８図のくＧ）はノードＮｉｌから技を伸ばした場合を
示し、ノードＮ１３．Ｎ１４のメトリック値がそれぞれ
＋５と＋１であるから、次はメトリック値が最大のノー
ドＮ１３から技が伸ばされる。

第８図の（Ｈ）はノードＮ１３から枝を伸ばした場合を
示し、ノードＮ１５．Ｎ１６のメトリック値がそれぞれ
０．−１であるから、未展開のノード（白丸）のうちで
、メトリック（直が最大のノードＮ１４がサブスタック
ＡＵＸＰＴの検索で見つかるから、このノードＮ１４に
戻って技を伸ばすことになる。

第８図の（１）は、ノードＮ１４から枝を伸ばした場合
を示し、メトリ・ツク値が＋２．−２のノードＮ１７．
Ｎ１８に展開される。

第８図の（Ｊ）は１ブロツクの復号処理が終了した場合
を示し、終端ノードＮ２０に到達したことにより、トレ
ースバックが行われ、太線で示すように、ノードＮｏ、
Ｎｌ、Ｎ３．Ｎ６．Ｎｌ　１、Ｎ１４．Ｎ１７．Ｎ１９
．Ｎ２０のバスが求められて、復号出力が決定される。

〔発明が解決しようとする問題点〕

サブスタック３４　（ＡＵＸＰＴ）を設けることにより
、メトリック値が最大のノードの検索が容易となる利点
があるが、前述のように、スタックメモリ部３３とサブ
スタック３４とをアクセスする回数が多いものであるか
ら、１回の演算に要する時間が長くなり、それによって
、復号処理を高速化することが困難であった。

本発明は、サブスタックやスタックメモリ部へのアクセ
ス回数を削減できるようにして、復号処理の高速化を図
ることを目的とするものである。

〔問題点を解決するための手段〕

本発明のシーケンシャル復号器は、サブスタックを設け
、畳込み符号をスタックアルゴリズムを用いて復号する
ものであり、第１図を参照して説明する。スタッメモリ
部１と、計算処理部６と、サブスタック７と、ノード検
索部８と、受信符号を一時蓄積する受信バッファ９と、
メトリック値が最大のノードの親ノードを記憶するバス
メモリ１０と、トレースバックにより復号出力を決定す
るバストレース部１１とを備えている。

スタックメモリ部１は、ノードの木構造に於ける深さを
記憶する深さスタックメモリ２と、ノードの内部状態を
記憶する内部状態スタックメモリ３と、ノードのメトリ
ック値を記憶するメトリック値スタックメモリ４と、ス
タックポインタ５とから構成されている。又計算処理部
６は、スタックメモリ部１から読出した未展開のメトリ
ック値最大のノードの情報と、受信バッファ９から読出
した受信符号とから、新しいノードのメトリック値を含
む情報を算出して、スタックメモリ部ｌのノード対応の
アドレスに書込み、且つその新しいノードのメトリック
値が増加している時に、そのノードをメトリック値が最
大のノードとして処理するものである。

又サブスタック７は、計算処理部６に於ける計算結果、
メトリック値が増加したノードについては更新処理が行
われず、増加しなかったノードについてのみ更新処理が
行われるものである。

〔作用〕

メトリック値が増加した新しいノードは、未展開のノー
ドのうちで、最大のメトリック値を持つノードであるか
ら、サブスタック７を検索することなく、メトリック値
最大のノードとして、次の枝を伸ばす処理を行うことが
できる。即ち、スタックメモリ部１からメトリック値が
最大のノードの情報の読出し、及びサブスタック７の更
新を行わないので、復号処理を高速化できる。

〔実施例〕

以下図面を参照して本発明の実施例について詳細に説明
する。

第１図は本発明の実施例のブロック図であり、■はノー
ド対応のアドレスを有するスタックメモリ部、２はノー
ドの木構造の深さを記憶する深さスタックメモリ、３は
ノードの内部状態を記憶する内部状態スタックメモリ、
４はノードのメトリック値を記憶するメトリック値スタ
ックメモリ、５はスタックポインタ、６は新しいノード
のメトリック値を含む情報を算出する計算処理部、７は
メトリック値をアドレスとしたサブスタック、８はメト
リック値が最大のノードを検索するノード検索部、９は
受信符号を一時蓄積する受信バッファ、１０は新しいノ
ードでメトリック値が増加する場合の親ノードを記憶す
るバスメモリ、１１は１ブロツクの復号処理終了により
トレースバックして復号出力を決定する為のバストレー
ス部である。

第２図は本発明の実施例のフローチャートであり、復号
開始により、サブスタック７よりメトリック値が最大の
ノードＮｍａｘを探し出す■。これはノード検索部８に
よりサブスタック７を検索することにより行うことがで
きる。次にこのノードＮｍａｘをサブスタック７から削
除する■。そして、このノードＮｍａｘの深さ、状態番
号（内部状態）、メトリック値等の情報をスタックメモ
リ部１から読出す■。

次にこのノードＮｍａｘの深さに対応する受信符号を受
信バッファ９から読出す■。そして、このノードＮｍａ
ｘから枝を伸ばす処理を行うもので、受信バッファ９か
ら読出された受信符号と、スタックメモリ部１から読出
されたメトリック値最大のノードＮｍａｘの情報とから
、新しいノードのメトリック値を含む情報を算出する■
。このステップ■により算出された新しいノードの情報
をスタックメモリ部１に書込む■。

そして、メトリック値が増加する技があったか否か判定
する■。これは、計算処理部６に於いて、スタックメモ
リ部１のメトリック値スタックメモリ部３から読出した
メトリック値と、新しいノードの算出したメトリック値
とを比較することにより、容易に判定することができる
。

メトリック値が増加する技があった場合は、メトリック
値が増加しなかった枝についてのみサブスタック７を更
新する■。例えば、従来例の復号過程を説明する第８図
の（Ｃ）に於いて、メトリック値が＋３のノードＮ３に
対して、新しいノードＮ５はメトリック値が増加し、新
しいノードＮ６はメトリック値が減少している。この場
合、メトリック値が増加しなかったノードＮ６について
のみサブスタック７を更新する。即ち、第８図の（Ｃ）
に於けるサブスタック３４のメトリック値＋４対応のア
ドレスにノードＮ５対応のアドレスの５を書込むことは
せず、メトリック値＋２対応のアドレスにノードＮ６対
応のアドレスの６を書込む。そして、１ブロツク分の復
号終了か否か判定する■。

１ブロック分の復号終了でない場合は、メトリック値が
増加した枝のノードをメトリック値最大のノードＮｍａ
ｘとする■“。例えば、前述の第８図の（Ｃ）に於いて
は、サブスタック３４を検索することなく、メトリック
値が増加したノードＮ５を、メトリック値最大のノード
Ｎｍａｘとし、ステップ■に移行する。この場合、サブ
スタ、２り３４に対して、ノードＮ６について処理する
為にアクセスするが、メトリック値最大のノードを検索
する為のアクセスは行う必要がないものである。又メト
リック値最大のノードのメトリック値を含む情報は、ス
タックメモリ部１に書込まれると共に、計算処理部６に
於ける次の計算処理に使用されるので、スタックメモリ
部１から読出す処理は不要となる。

又メトリック値が増加する技がない場合は、総ての枝に
ついてサブスタックを更新する［相］。例えば、第８図
の（Ｄ）に於いては、メトリック値が＋４のノードＮ５
に対して、ノードＮ’７．Ｎ８のメトリック値は減少し
ているので、サブスタック３４を更新し、メトリック値
＋２対応のアドレスに、ノードＮ７対応のアドレスの７
を書込み、スタックポインタ５ＡＴＫＰＴ　（第１図に
於ける５）に、同一のメトリック値を有するノード対応
のアドレスの値を書込む。又サブスタック３４のメトリ
ック値＋１対応のアドレスに、ノードＮ８対応のアドレ
スの８を書込む。

そして、１ブロック分の復号終了か否か判定し０、終了
していない場合は、ステップ■に移行する。即ら、ノー
ド検索部８によりサブスタック７の検索が行われ、メト
リック値が最大のノードが探し出される。この場合は、
第８図の（Ｄ）に示す場合と同様に、サブスタック７及
びスタックメモリ部１に対する書込み読出しのアクセス
が行われる。

ステップ■、■に於いて、１ブロック分の復号終了と判
定すると、バスのトレースバックにより最尤バスが決定
され＠、その最尤バスにより復号出力が決定される。そ
して、サブスタック７のクリア０が行われ、次のブロッ
クについての復号処理を行う為にステップ■に移行する
。

第３図は本発明のタイムチャートであり、ｆａ）は受信
バッファ９へのアクセス、（ｂｌは計算処理部６に於け
るメトリック値等の計算、（Ｃ１はスタックメモリ部ｌ
へのアクセス、ｆｄ）はサブスタック７へのアクセスを
示す。即ち、（ａ）に示すように、受信バッファ９から
受信符号を読出した次のタイミングで、ｆｂｌに示すよ
うに、計算処理部６に於いてメ］・リンク値等の計算が
行われ、次のタイミングでｆｃ）に示すように、スタッ
クメモリ部１へ計算結果が書込まれる。それと同時に、
（ｄ）に示すように、メトリック値が増加しなかったノ
ードに対応するサブスタック７の更新を行う。

従って、１回の演算（枝を伸ばす処理）は、受信符号読
出、計算、書込、更新の並列処理の時間で済むことにな
り、メトリック値が増加する場合には、一種のバイブラ
イン処理を行うことが可能となるから、復号処理時間を
短縮することができる。

例えば、１回の演算時間を、内部クロック数で示すと、
メトリック値が増加する枝がなかった場合、ｎｃ＋ｘ　
（クロック〕、（Ｘはサブスタックよりメトリック値が
最大のノードＮｍａｘを探し出すのに要する時間）、又
メトリック値が増加する枝がある場合、ｎｃｉ（クロッ
ク〕　（但し、ｎｃ＜ｎｃｉ）とすると、１シンボルの
復号に要する平均時間は、 （（ｎｃ＋ｘ）Ｐ、、−＋ｎｃ　ｉ　　（１−ＰＭＭ）
）ＸＣＲ＋１　　　　（クロック〕　　　　　・−（１
）となる。但し、ＣＲはｌシンボルの復号に要する平均
演算回数、Ｐｏはメトリック値が増加する枝が存在しな
い確率を示す。又最後の＋１は、最尤バス決定の為のト
レースバックに要する時間を示す。

従って、復号速度Ｖｄは、 （（ｎｃ＋ｘ）　Ｐｓｗ＋ｎｃｉ（１−ＰＭ、）　）　
ＣＲ＋１〔シンボル／Ｓ）　　・・−（２） となる。

例えば、内部クロックレート＝１２．５ＭＨｚ、ｎｃ＝
８、ｎｃｉ＝２、ｘ＃２　（平均値）、ＣＲ−２、と仮
定すると、確率Ｐ−は、Ｅ　３　／　Ｎ　ｇ　”Ｑ、５
　ｄ　Ｂの時、約１．４Ｘ１０−’と推定されるから、
復号速度Ｖｄは約１７００（Ｋシンボル／Ｓ）となる。

これに対して、従来例に於いては、１回の演算に要する
時間は、ｎｃ＋ｘ　（クロック）となり、１シンボルの
復号に要する平均時間は、（ｎｃ＋ｘ）ＣＲ＋１　　　
　（クロック）　−・（３）となるから、復号速度Ｖｄ
’は、 （ｎｃ＋ｘ）ＣＲ＋１ 〔シンボル／　Ｓ　）　　　−４４） となる。従って、前述の条件と同一の条件に於いて、復
号速度Ｖｄ’は、約５９５（Ｋシンボル／Ｓ〕となる。

即ち、本発明によれば、従来例に比較して約３倍の復号
速度が得られる。

前述の実施例に於いては、符号化率ＲをＲ＝ｎ／ｍとし
、一つのノードから２ｆｉ本の枝を伸ばす場合に、ｎ＝
１として、２本の技を伸ばす例について示すものである
が、ｎ＝２以上の符号化率とした場合にも適用すること
ができるものである。

即ち、一つのノードから４本以上の技を伸ばした場合で
も、そのうちの最大のメトリック値が親ノードのメトリ
ック値より大きいか否かを判定し、大きい場合は、サブ
スタック７を更新することなく、次の復号処理に移行す
るものである。又送信符号をブロック化しないで、連続
的にシーケンシャル復号を行う場合に適用することがで
きる。

〔発明の効果〕

以上説明したように、本発明は、親ノードから技を伸ば
した新しいノードの最大のメトリック値が、親ノードの
メトリック値より増加している場合に、サブスタック７
を更新することなく、その最大のメトリック値のノード
から次の技を伸ばす処理を行うものであり、それによっ
て、サブスタック７及びスタックメモリ部１に対するア
クセス回数を減少することができ、従って、畳込み符号
の誤り訂正復号を高速化できる利点がある。

【図面の簡単な説明】

第１図は本発明の実施例のブロック図、第２図は本発明
の実施例のフローチャート、第３図は本発明の実施例の
タイムチャート、第４図はシーケンシャル復号器の要部
ブロック図、第５図は従来例のブロック図、第６図は従
来例のフローチャート、第７図は従来例のタイムチャー
ト、第８図（Ａ）〜（Ｊ）は復号過程説明図である。 １はスタックメモリ部、２は深さスタックメモリ、３は
内部状態スタックメモリ、４はメトリ・ツク値スタック
メモリ、５はスタックポインタ、６はメトリック値等を
計算する計算処理部、７はサブスタック、８はノード検
索部、９は受信バ・ソファ、ｌＯはバスメモリ、１１は
バストレース部である。

Claims (1)

1. 【特許請求の範囲】 スタックアルゴリズムを用いて畳込み符号の誤り訂正復
   号を行うスタック型のシーケンシャル復号器に於いて、 ノードの木構造に於ける深さを記憶する深さスタックメ
   モリ（２）と、ノードの内部状態を記憶する内部状態ス
   タックメモリ（３）と、ノードのメトリック値を記憶す
   るメトリック値スタックメモリ（４）と、スタックポイ
   ンタ（５）とからなるスタックメモリ部（１）と、 受信符号と、前記スタックメモリ部（１）から読出した
   未展開のメトリック値最大のノードの情報とから新しい
   ノードのメトリック値を含む情報を算出して、前記スタ
   ックメモリ部（１）に書込み、且つ新しいノードのメト
   リック値が増加している時に、該ノードをメトリック値
   が最大ノードとして処理を行う計算処理部（６）と、 該計算処理部（６）に於ける計算結果、メトリック値が
   増加したノードについては更新処理を行わず、増加しな
   かったノードについてのみ更新処理を行うサブスタック
   （７）とを備えた ことを特徴とするシーケンシャル復号器。