(57)【要約】【課題】トレースバック処理に用いるパス選択情報を格納するメモリのサイズと、復号に伴うレイテンシを抑えることができるようにする。【解決手段】シフトレジスタ８１に対しては、radix-2xのパス選択情報が１クロックあたりxNビットずつ入力され、k入力分蓄積された後、kxNビットのパス選択情報がまとめてパスメモリ用RAM８２の１アドレスに書き込まれる。トレースバック回路８３においては、パスメモリ用RAM８２に格納されているパス選択情報に基づいてトレースバック処理が行われることによって最尤パスが選択され、最尤パス上にある各状態に対応する値を復号系列として出力される。本発明は受信装置に適用することができる。【選択図】図６
2010206570.tif 000002
【特許請求の範囲】
【請求項１】
N及びxを正の整数、kを１より大きい正の整数として、
状態数Nの畳み込み符号の各遷移状態におけるradix-2xで構成されたxNビットの生き残りパスの情報であるパス選択情報をk入力分蓄積するk段のシフトレジスタと、
前記シフトレジスタに蓄積されたk入力分の前記パス選択情報を１アドレスに格納する、バンク数が１のパスメモリと、
tをkxの約数、rを2または1/tとして、前記パスメモリから読み出した前記パス選択情報を用いて、１クロックの間にm=rkx時刻分のパスを遡り、復号結果を出力するトレースバック回路と
を備える復号装置。
【請求項２】
１個設けられる前記トレースバック回路のトレースバック長をkxで割り切れる正の整数Tで表し、
前記パスメモリに対する前記パス選択情報の書き込みがs回行われる毎に次のトレースバック処理が開始される場合の１回のトレースバック処理に要するクロック数をlで表し、
α=T/(kx)とし、
ceiling(b)を実数b以上の最小の整数を表すものとしたとき、
sとlがそれぞれ、
【数１】
2010206570.tif 000028
【数２】
2010206570.tif 000029
で表され、
前記トレースバック回路は、T+skx時刻分の１回のトレースバック処理をlクロック分の時間をかけて行い、skxビットの復号結果を出力する
請求項１に記載の復号装置。
【請求項３】
２個設けられる前記トレースバック回路のトレースバック長をkxで割り切れる正の整数Tで表し、
前記パスメモリに対する前記パス選択情報の書き込みがs回行われる毎に次のトレースバック処理が開始される場合の１回のトレースバック処理に要するクロック数をlで表し、
α=T/(kx)とし、
uをu≦sを満たす正の整数とし、
ceiling(b)を実数b以上の最小の整数を表すものとしたとき、
sとlがそれぞれ、
【数３】
2010206570.tif 000030
【数４】
2010206570.tif 000031
で表され、
前記トレースバック回路は、T+skx時刻分の１回のトレースバック処理をlクロック分の時間をかけて行い、skxビットの復号結果を出力する
請求項１に記載の復号装置。
【請求項４】
前記パスメモリを構成するRAMの深さaが
【数５】
2010206570.tif 000032
によって表される
請求項２または３に記載の復号装置。
【請求項５】
r=2、または前記トレースバック回路の数が２である場合、前記パスメモリは、読み出しポートを２つ備えるデュアルポートRAMによって構成される
請求項１に記載の復号装置。
【請求項６】
r≦1かつs=1である場合、前記パスメモリは、シングルポートRAMによって構成される
請求項２に記載の復号装置。
【請求項７】
前記パスメモリは、書き込みを行った次の時刻の読み出しポートから、直前に書き込んだ書き込み情報を出力する動作を行うRAMによって構成される
請求項１に記載の復号装置。
【請求項８】
mの最大値をmfcとしてmの値を制限し、kおよびrの値として、m≦mfcを満たす値を用いる
請求項１に記載の復号装置。
【請求項９】
kおよびrの値として、前記シフトレジスタの回路規模と、前記パスメモリとして用いるRAMの回路規模を足し合わせたものが最小となる値を用いる
請求項１に記載の復号装置。
【請求項１０】
kおよびrの値として、前記トレースバック回路を含むモジュールに設けられる、前記パスメモリから読み出した情報を保持するフリップフロップの回路規模をさらに足し合わせたものが最小となる値を用いる
請求項９に記載の復号装置。
【請求項１１】
前記シフトレジスタがk段のpretrace-back回路である
請求項１に記載の復号装置。
【請求項１２】
N及びxを正の整数、kを１より大きい正の整数として、
状態数Nの畳み込み符号の各遷移状態におけるradix-2xで構成されたxNビットの生き残りパスの情報であるパス選択情報をk段のシフトレジスタによってk入力分蓄積し、
前記シフトレジスタに蓄積されたk入力分の前記パス選択情報を１アドレスに格納する、バンク数が１のパスメモリによって前記パス選択情報を格納し、
tをkxの約数、rを2または1/tとして、前記パスメモリから読み出した前記パス選択情報を用いて、１クロックの間にm=rkx時刻分のパスをトレースバック回路によって遡り、復号結果を出力する
ステップを含む復号方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、復号装置、復号方法に関し、特に、トレースバック処理に用いるパス選択情報を格納するメモリのサイズと、復号に伴うレイテンシを抑えることができるようにした復号装置、復号方法に関する。
【背景技術】
【０００２】
送信装置から受信装置にデータを送信する場合や、記録装置によって記録媒体に記録された情報を再生装置によって再生する、つまり記録装置から再生装置にデータを伝送する場合などにおいて、その伝送路上でデータに誤りが生じることがある。
【０００３】
伝送路上で生じた誤りを訂正する代表的な方法の一つとして畳み込み符号（convolutional code）があり、畳み込み符号の最尤復号を実現する方法としてビタビ復号がある。ビタビ復号（Viterbi decoding）については例えば非特許文献１に開示されている。
【０００４】
図１は、送受信システムの構成例を示すブロック図である。
【０００５】
図１の送受信システムは、送信装置１と受信装置３が伝送路２を介して接続されることによって構成される。送信装置１は、畳み込み符号器１１と伝送路符号器１２から構成され、受信装置３は、符号検出器３１、伝送路復号器３２、およびビタビ復号器３３から構成される。伝送対象の情報系列は、送信装置１の畳み込み符号器１１に入力される。
【０００６】
送信装置１の畳み込み符号器１１は、入力された情報系列に対して畳み込み符号化処理を施し、誤り訂正符号化を行うことによって得られた符号系列を伝送路符号器１２に出力する。
【０００７】
伝送路符号器１２は、畳み込み符号器１１から供給された符号系列に対して、伝送路２に応じた変調処理等の符号化処理を施し、得られたデータを、伝送路２を介して受信装置３に送信する。伝送路符号器１２から送信された信号は伝送路２を介して受信装置３の符号検出器３１に入力される。
【０００８】
受信装置３の符号検出器３１は、受信した信号に基づいてデータを検出し、検出したデータを伝送路復号器３２に出力する。
【０００９】
伝送路復号器３２は、符号検出器３１から供給されたデータに対して復調処理等の復号処理を施し、得られた受信系列をビタビ復号器３３に出力する。
【００１０】
ビタビ復号器３３は、伝送路復号器３２から供給された受信系列に対してビタビ復号処理を施し、誤り訂正を行うことによって得られた復号系列を復号結果として出力する。
【００１１】
ここで、ビタビ復号の原理について簡単に説明する。
【００１２】
ある符号系列Wを送信したときの受信系列がVである条件付き確率（尤度関数）P0(V|W)は下式（１１）で表される。
【数１１】
2010206570.tif 000003
【００１３】
式（１１）において、Sは受信系列数、viはi番目の受信信号、wiはある符号系列Wにおけるi番目の送信信号を表す。P(vi|wi)は、wiを送信したときの受信信号がviである条件付確率となる。最尤復号は、このP0(V|W)を最大にする符号系列を求めることによって行われる。
【００１４】
-logｅP(vi|wi)をブランチメトリック（branch metric）と呼び、あるパスに対応する符号系列Wに対するブランチメトリックの和、つまり、-logｅP(V|W)をパスメトリック（path metric）と呼ぶ。
【００１５】
図２は、最尤復号をトレリス線図に基づいて実現するビタビ復号器３３の構成例を示すブロック図である。
【００１６】
図２に示すように、ビタビ復号器３３は、ブランチメトリック計算器４１、ACS（Add Compare Select）処理器４２、パスメトリックメモリ４３、および生き残りパス処理器４４から構成される。畳み込み符号器１１の拘束長（constraint length）をKとすると、トレリス線図における状態数NはN=2K-1で表される。K，Nは正の整数である。
【００１７】
ブランチメトリック計算器４１は、受信系列を構成する各受信信号に対するブランチメトリックを計算し、ACS処理器４２に出力する。
【００１８】
ACS処理器４２は、ブランチメトリック計算器４１により計算されたブランチメトリックを参照し、畳み込み符号器１１の拘束長によって定まる状態数のトレリス線図に従って各状態の生き残りパス（survivor path）を決定する。生き残りパスは、ある状態と、その状態に接続される前状態とを結ぶ複数のパスの中からハミング距離に基づいて選択されたパスである。
【００１９】
また、ACS処理器４２は、生き残りパスの情報であるパス選択情報を生き残りパス処理器４４に出力し、生き残りパス処理器４４内のパスメモリ（path memory）４４Ａに記憶させる。ACS処理器４２は、パス選択情報を生き残りパス処理器４４に出力するのと同時に、各状態のメトリックを記憶するメモリであるパスメトリックメモリ４３の値を更新する。
【００２０】
生き残りパス処理器４４は、パスメモリ４４Ａに記憶されているパス選択情報に基づいて、受信系列の入力が終了した時点で各状態について生き残ったパスの中から、パスメトリックが最小のパス（最尤パス）を選択する。生き残りパス処理器４４により選択された最尤パス上の状態に対応する値が復号系列として出力され、これにより最尤復号が実現される。
【００２１】
ところで、受信系列が長い場合、このことが、最尤パスを選択するまでにパスメモリに記憶させておくパス選択情報の長さであるパスメモリ長の増大や、復号に要する時間（レイテンシ）の増大を生じさせてしまう。このため、通常、パスメモリは、復号特性にほとんど影響を与えない長さにパスメモリ長を打ち切って用いられる。一般に、畳み込み符号器の拘束長Kや符号化率が大きくなる程、パスメモリ長を長く確保する必要がある。
【００２２】
ところで、パスメモリに記憶されたパス選択情報から最尤パスを選択する方法として、トレースバック（Traceback）方式と、レジスタエクスチェンジ（Register Exchange）方式が知られている。
【００２３】
レジスタエクスチェンジ方式は、回路構成が単純で高速動作が可能である反面、パスメモリ長が長くなると回路規模や消費電力が大きくなるという性質を有する。このため、パスメモリ長が長い場合には、RAM(Random Access Memory)を用いて生き残りパスの情報を記憶し、その情報をパスメモリ長分遡ることで最尤パスを選択するトレースバック方式が用いられることが多い。
【００２４】
ここで、トレースバック方式において遡るパスメモリの長さであるトレースバック長をTとする。また、ビタビ復号器に対する入力はradix-2xで構成されているものとする。T，xは正の整数である。
【００２５】
非特許文献２においては、トレースバック方式のアルゴリズムとして、k-pointerアルゴリズム、One-pointerアルゴリズムが提案されている。また、非特許文献３においては、これらの２つのアルゴリズムを組み合わせたHybridアルゴリズムが提案されている。
【００２６】
k-pointerアルゴリズムは、パスメモリ用のRAMをビット幅xN、深さT/{x・(k-1)}の2k個のバンクに分割し、k個の読み出しポインタを用いて、１回の書き込みに対してk箇所の読み出しを並列に行うアルゴリズムである。kは１より大きい正の整数であり、トレースバック方式において必要な、パスメモリ用のRAMからの読み出し操作の数を表す。
【００２７】
One-pointerアルゴリズムは、RAMをビット幅xN、深さT/{x・(k-1)}のk+1個のバンクに分割し、書き込み速度のk倍の速度で読み出しを行うことで、１回の書き込みに対してk回の読み出しを行うアルゴリズムである。
【００２８】
Hybridアルゴリズムは、k=k１k２を満たす正の整数k１，k２を用い、書き込み速度のk１倍の速度で、k２個の読み出しポインタを用いてk箇所の読み出しを並列に行うアルゴリズムである。
【００２９】
非特許文献４においては、pretrace-back回路を用いてk入力に１回の書き込みを行うことで、one-pointerアルゴリズムと同様のメモリ構成およびレイテンシを実現するHybrid pretrace-backアルゴリズムが提案されている。
【００３０】
Hybrid pretrace-backアルゴリズムは、ACS処理器から出力されるパス選択情報をパスメモリに書き込む前にpretrace-back回路を用いて予め並び替えておくことで、トレースバック処理時の負荷を減らすアルゴリズムである。pretrace-back回路はk段のレジスタエクスチェンジ構造を持つ回路である。
【００３１】
特許文献１においては、パスメモリとして1-writeポート、1-readポートのデュアルポートRAMをk個用いることで１回の書き込みに対してk箇所の読み出しを実現し、１クロックでkx時刻分のトレースバックを行うことが提案されている。これによりRAMのサイズを小さくすることが可能になっている。
【００３２】
特許文献２においては、k-pointerアルゴリズムにおいて書き込みを行うバンクと復号のための読み出しを行うバンクを共有することによってバンクを１つ減らし、2k-1個のバンクに分割する構成が提案されている。これによりRAMに対するアドレスの指定が簡単なメモリマネジメントが可能になっている。
【００３３】
従来のトレースバック方式の各アルゴリズムを用いた場合の生き残りパス処理器のパスメモリサイズM、およびレイテンシLの関係をまとめると下の表１のようになる。レイテンシLは、ACS処理器がxNビットのパス選択情報を出力する時間間隔を１としたときの、生き残りパス処理器にパス選択情報が最初に入力されてから最初の復号結果が出力されるまでの時間である。
【００３４】
【表１】
2010206570.tif 000004
【００３５】
また、T=112，x=2としてkを変化させたときのMの変化を図３に示し、Lの変化を図４に示す。
【００３６】
図３、図４には示していないが、HybridアルゴリズムのM，Lの値は、k=k１k２を満たすk１，k２の値によって、one-pointerアルゴリズムのM，Lの値以上、k-pointerアルゴリズムのM，Lの値以下となる。例えば、HybridアルゴリズムのM，Lの値は、k１=1のときk-pointerアルゴリズムの値と一致し、k２=1のときone-pointerアルゴリズムの値と一致する。
【００３７】
なお、表１、図３に示すpretrace-backアルゴリズムのMの値は、パスメモリのメモリサイズに加えてpretrace-back回路のメモリサイズを考慮して求められたものである。
【先行技術文献】
【非特許文献】
【００３８】
【非特許文献１】A. J. Viterbi and J. K. Omura: Principles of Digital Communication and Coding, MacGraw-Hill, New York, 1979.
【非特許文献２】G. Feygin and P. G. Gulak, “Architectural Tradeoffs for Survivor Sequence Memory Management in Viterbi Decoders,” IEEE Transactions on Communications, vol. 41, no. 3, pp. 425 - 429, March 1993.
【非特許文献３】R. Cypher and C. B. Shung, “Generalized Trace Back Techniques for Survivor Memory Management in the Viterbi Algorithm,” IEEE Global Telecommunications Conference and Exhibition. 'Communications: Connecting the Future', vol. 2, pp. 1318 - 1322, Dec 1990.
【非特許文献４】P. J. Black and T. H. -Y. Meng, “Hybrid Survivor Path Architectures for Viterbi Decoders,” ICASSP, vol. 1, pp. 433 - 436, April 1993.
【特許文献】
【００３９】
【特許文献１】T. Miyauchi and M. Hattori, “Viterbi Decoding apparatus and Viterbi Decoding Method,” US 6,651,215 B2, Sony Corporation, Nov. 18, 2003, Filed Dec. 17, 1998.
【特許文献２】M. Rim and Y. Oh, “Traceback-Performing Apparatus in Viterbi Decoder,” US 6,712,880, Samsung Electronics Co., Ltd., Jan. 27, 1998, Filed Nov. 14, 1995.
【特許文献３】S. Thurnhofer, “Traceback Buffer Management for VLSI Viterbi Decoders,” US 6,601,215 B1, Agere Systems Inc., Jul. 29, 2003, Filed Feb. 1, 2000.
【発明の概要】
【発明が解決しようとする課題】
【００４０】
従来のトレースバック方式の各アルゴリズムによれば、表１の各式から分かるように、kの値を大きくすることによってメモリサイズM、およびレイテンシLの値を小さくすることが可能である。
【００４１】
しかしながら、kの値が大きくなるに従ってパスメモリのバンク数も増加することになるため、それらのバンクから読み出した情報を選択するセレクタやコントローラなどの周辺回路の回路規模が大きくなってしまう。
【００４２】
このため、kの値として３以下の値が設定されることが多く、この場合、パスメモリのメモリサイズMは2TNビット以上必要になる。一般的に、Nの値が大きくなるに従って、長いトレースバック長Tが必要になり、2TNビットのサイズのパスメモリの回路規模は大きいものになってしまう。
【００４３】
また、特許文献１において提案されているような１クロックでkx時刻分のトレースバック処理を行う構成は、kの値が大きいと１クロックの時間内に完了しなければならない処理が多くなるために、高いクロック周波数での動作が困難になる。
【００４４】
そのため、メモリサイズと、周辺回路を含めた回路規模ができるだけ小さく、かつ、高いクロック周波数での動作が可能なトレースバック方式のアルゴリズムが望まれている。また、無線通信システムなどで短い処理時間が要求される場合には、レイテンシができるだけ小さくなるようなアルゴリズムが求められる。
【００４５】
本発明はこのような状況に鑑みてなされたものであり、例えばトレースバック処理に用いるパス選択情報を格納するメモリのサイズと、復号に伴うレイテンシを抑えることができるようにするものである。
【課題を解決するための手段】
【００４６】
本発明の一側面の復号装置は、N及びxを正の整数、kを１より大きい正の整数として、状態数Nの畳み込み符号の各遷移状態におけるradix-2xで構成されたxNビットの生き残りパスの情報であるパス選択情報をk入力分蓄積するk段のシフトレジスタと、前記シフトレジスタに蓄積されたk入力分の前記パス選択情報を１アドレスに格納する、バンク数が１のパスメモリと、tをkxの約数、rを2または1/tとして、前記パスメモリから読み出した前記パス選択情報を用いて、１クロックの間にm=rkx時刻分のパスを遡り、復号結果を出力するトレースバック回路とを備える。
【００４７】
１個設けられる前記トレースバック回路のトレースバック長をkxで割り切れる正の整数Tで表し、前記パスメモリに対する前記パス選択情報の書き込みがs回行われる毎に次のトレースバック処理が開始される場合の１回のトレースバック処理に要するクロック数をlで表し、α=T/(kx)とし、ceiling(b)を実数b以上の最小の整数を表すものとしたとき、sとlがそれぞれ、
【数１】
2010206570.tif 000005
【数２】
2010206570.tif 000006
で表され、前記トレースバック回路には、T+skx時刻分の１回のトレースバック処理をlクロック分の時間をかけて行わせ、skxビットの復号結果を出力させることができる。
【００４８】
２個設けられる前記トレースバック回路のトレースバック長をkxで割り切れる正の整数Tで表し、前記パスメモリに対する前記パス選択情報の書き込みがs回行われる毎に次のトレースバック処理が開始される場合の１回のトレースバック処理に要するクロック数をlで表し、α=T/(kx)とし、uをu≦sを満たす正の整数とし、ceiling(b)を実数b以上の最小の整数を表すものとしたとき、sとlがそれぞれ、
【数３】
2010206570.tif 000007
【数４】
2010206570.tif 000008
で表され、前記トレースバック回路には、T+skx時刻分の１回のトレースバック処理をlクロック分の時間をかけて行わせ、skxビットの復号結果を出力させることができる。
【００４９】
前記パスメモリを構成するRAMの深さaが
【数５】
2010206570.tif 000009
によって表されるようにすることができる。
【００５０】
r=2、または前記トレースバック回路の数が２である場合、前記パスメモリを、読み出しポートを２つ備えるデュアルポートRAMによって構成することができる。
【００５１】
r≦1かつs=1である場合、前記パスメモリを、シングルポートRAMによって構成することができる。
【００５２】
前記パスメモリを、書き込みを行った次の時刻の読み出しポートから、直前に書き込んだ書き込み情報を出力する動作を行うRAMによって構成することができる。
【００５３】
mの最大値をmfcとしてmの値を制限し、kおよびrの値として、m≦mfcを満たす値を用いるようにすることができる。
【００５４】
kおよびrの値として、前記シフトレジスタの回路規模と、前記パスメモリとして用いるRAMの回路規模を足し合わせたものが最小となる値を用いることができる。
【００５５】
kおよびrの値として、前記トレースバック回路を含むモジュールに設けられる、前記パスメモリから読み出した情報を保持するフリップフロップの回路規模をさらに足し合わせたものが最小となる値を用いることができる。
【００５６】
前記シフトレジスタがk段のpretrace-back回路であるようにすることができる。
【００５７】
本発明の復号方法は、N及びxを正の整数、kを１より大きい正の整数として、状態数Nの畳み込み符号の各遷移状態におけるradix-2xで構成されたxNビットの生き残りパスの情報であるパス選択情報をk段のシフトレジスタによってk入力分蓄積し、前記シフトレジスタに蓄積されたk入力分の前記パス選択情報を１アドレスに格納する、バンク数が１のパスメモリによって前記パス選択情報を格納し、tをkxの約数、rを2または1/tとして、前記パスメモリから読み出した前記パス選択情報を用いて、１クロックの間にm=rkx時刻分のパスをトレースバック回路によって遡り、復号結果を出力するステップを含む。
【００５８】
本発明の一側面においては、状態数Nの畳み込み符号の各遷移状態におけるradix-2xで構成されたxNビットの生き残りパスの情報であるパス選択情報がk段のシフトレジスタによってk入力分蓄積され、前記シフトレジスタに蓄積されたk入力分の前記パス選択情報を１アドレスに格納する、バンク数が１のパスメモリによって前記パス選択情報が格納される。また、tをkxの約数、rを2または1/tとして、前記パスメモリから読み出した前記パス選択情報を用いて、１クロックの間にm=rkx時刻分のパスをトレースバック回路によって遡り、復号結果を出力することが行われる。
【発明の効果】
【００５９】
本発明の一側面によれば、トレースバック処理に用いるパス選択情報を格納するメモリのサイズと、復号に伴うレイテンシを抑えることができる。
【図面の簡単な説明】
【００６０】
【図１】送受信システムの構成例を示すブロック図である。
【図２】ビタビ復号器の構成例を示すブロック図である。
【図３】T=112，x=2としてkを変化させたときのMの変化を示す図である。
【図４】T=112，x=2としてkを変化させたときのLの変化を示す図である。
【図５】本発明の一実施形態に係る受信装置の構成例を示すブロック図である。
【図６】生き残りパス処理器の基本的な構成例を示すブロック図である。
【図７】パスメモリ用RAMの構成例を示す図である。
【図８】T=112，x=2の場合において、r=2としてkを変化させたときのMの変化を示す図である。
【図９】T=112，x=2の場合において、r=2としてkを変化させたときのLの変化を示す図である。
【図１０】生き残りパス処理器の構成パラメータの決定手順について説明するフローチャートである。
【図１１】図１０のステップＳ２において行われる計算の手順について説明するフローチャートである。
【図１２】図１０のステップＳ０において行われる決定の手順について説明するフローチャートである。
【図１３】生き残りパス処理器の構成例を示すブロック図である。
【図１４】図１３のパスメモリ用RAMのメモリアクセスチャートである。
【図１５】生き残りパス処理器の他の構成例を示すブロック図である。
【図１６】生き残りパス処理器のさらに他の構成例を示すブロック図である。
【図１７】図１６のパスメモリ用RAMのメモリアクセスチャートである。
【図１８】パスメモリ用RAMのレイアウトの例を示す図である。
【図１９】図１０のステップＳ０において行われる決定の手順の変形例について説明するフローチャートである。
【図２０】図１０のステップＳ０において行われるkとrの決定の手順の他の変形例について説明するフローチャートである。
【図２１】生き残りパス処理器の構成例を示すブロック図である。
【図２２】図２１のパスメモリ用RAMのメモリアクセスチャートである。
【図２３】畳み込み符号器の構成例を示す図である。
【図２４】図２３の畳み込み符号器によって符号化される系列のトレリス線図である。
【図２５】生き残りパス処理器の構成例を示すブロック図である。
【図２６】図２５のパスメモリ用RAMのメモリアクセスチャートである。
【発明を実施するための形態】
【００６１】
＜受信装置の構成例＞
図５は、本発明の一実施形態に係る受信装置５１の構成例を示すブロック図である。
【００６２】
図５に示す受信装置５１の構成は、図１、図２に示す受信装置の構成を組み合わせたものと同じ構成である。重複する説明については適宜省略する。
【００６３】
受信装置５１の符号検出器６１は、受信した信号に基づいて検出したデータを伝送路復号器６２に出力する。
【００６４】
伝送路復号器６２は、符号検出器６１から供給されたデータに対して復号処理を施し、得られた受信系列をビタビ復号器６３に出力する。
【００６５】
ビタビ復号器６３はブランチメトリック計算器７１、ACS処理器７２、パスメトリックメモリ７３、および生き残りパス処理器７４から構成される。伝送路復号器６２から出力された受信系列はブランチメトリック計算器７１に入力される。
【００６６】
ブランチメトリック計算器７１は、受信系列を構成する各受信信号に対するブランチメトリックを計算し、ACS処理器７２に出力する。
【００６７】
ACS処理器７２は、各状態の生き残りパスを決定し、パス選択情報を生き残りパス処理器７４に出力する。また、ACS処理器７２はパスメトリックメモリ７３の値を更新する。
【００６８】
図６は、生き残りパス処理器７４の基本的な構成例を示すブロック図である。
【００６９】
詳細な構成については後述するが、図６に示すように、生き残りパス処理器７４は、シフトレジスタ８１、パスメモリ用RAM８２、およびトレースバック回路８３から構成される。シフトレジスタ８１に対しては、radix-2xで構成されるパス選択情報が１クロックあたりxNビットずつ入力される。生き残りパス処理器７４の各部には同一周波数のクロックが入力され、そのクロックを基準として動作が行われる。
【００７０】
シフトレジスタ８１は、入力されたパス選択情報をkクロック分蓄積し、kxNビットのパス選択情報をまとめて、パスメモリ用RAM８２の１アドレスに書き込む。
【００７１】
パスメモリ用RAM８２はシフトレジスタ８１から供給されたパス選択情報を格納する。
【００７２】
トレースバック回路８３は、受信系列の入力がトレースバック処理を開始するべき数だけ終了した時点で、パスメモリ用RAM８２に格納されているパス選択情報に基づいてトレースバック処理を行い、最尤パスを選択する。生き残りパス処理器７４は、最尤パス上の状態に対応する値を復号系列として出力する。
【００７３】
［パスメモリ用RAMのアドレス構成］
実現するシステムにおいて要求される誤り率性能やスループットに応じて、状態数N、トレースバック長T、およびxは予め定められている。N，xは正の整数であり、kは１より大きい正の整数である。Tはkxで割り切れる正の整数である。
【００７４】
図７は、パスメモリ用RAM８２の構成例を示す図である。
【００７５】
図７の例においては、横方向にパス選択情報r1乃至raが示されている。また、状態数Nが16とされ、縦方向に状態N1乃至N16が示されている。
【００７６】
各マス目にはパス選択情報に対応するkxビットの値が格納される。kxNビットのパス選択情報をまとめて記憶させる生き残りパス処理器７４においては、パスメモリ用RAM８２の１アドレスにはkx時刻分のパス選択情報が格納されることになる。
【００７７】
また、αを下式（１２）のように定義する。
【数１２】
2010206570.tif 000010
【００７８】
１アドレスあたりkx時刻分のパス選択情報が格納されているので、αはT時刻分のパス選択情報を格納するために必要なパスメモリ用RAM８２のアドレス数を表す。Tはkxで割り切れるのでαは必ず正の整数となる。
【００７９】
１アドレスに対するパス選択情報の書き込み、または１アドレスからのパス選択情報の読み出しは１つのポートを用いて行われる。パスメモリ用RAM８２がシングルポートのRAMである場合は同一時刻に書き込みと読み出しのうちのいずれかしかできない。これに対して、書き込みポートと読み出しポートがそれぞれ１つずつ設けられているデュアルポートのRAMである場合は同一時刻に書き込みと読み出しを行うことが可能となる。
【００８０】
また、パスメモリ用RAM８２が、読み出しポートが２つ設けられるデュアルポートのRAMである場合、同一時刻に２アドレス分まとめてパス選択情報の読み出しを行うことも可能となる。
【００８１】
なお、図７の例においては、パス選択情報rα+sまで蓄積されたタイミングで、生き残りパスを遡るトレースバック処理が開始される。パス選択情報rα+s,rα+s-1,…,rα,…,rs,…,r2,r1と読み出してトレースバック処理を行うことによって、skxビットの復号結果を得る。Sは正の整数である。
【００８２】
また、パスメモリ用RAM８２は、従来のアルゴリズムで用いられるパスメモリとは異なり、複数のバンクに分割して用いるようなことはされず、単一のバンクを有するRAMで構成される。従って、kの値を増加させたとしてもセレクタなどの周辺回路を用意する必要がなく、それによって回路規模が増大するようなことはない。上述したように複数のバンクがパスメモリに構成されている場合、読み出したデータを選択するセレクタなどの周辺回路が必要になる。
【００８３】
なお、パス選択情報の書き込みの単位であるkxNビットの幅が大きく、このビット幅を持つRAMを用意することができない場合、kxNビットのパス選択情報を分割して複数のRAMに分けて格納するようにしてもよい。
【００８４】
この場合、複数のRAM全てに対して同一アドレス、同一タイミングで書き込みと読み出しを行うことによって、複数のRAMが等価的に１つのRAMとして用いられる。これにより、パスメモリ用RAM８２が複数のRAMによって構成されることになるが、動作は１つのRAMとみなせるのでバンク数は１であるといえる。
【００８５】
［パス選択情報を用いたトレースバック処理］
トレースバック回路８３は１クロックでm時刻分のパスを遡ってトレースバック処理を行う回路である。mは下式（１３）で表される。
【数１３】
2010206570.tif 000011
【００８６】
式（１３）において、rの値は２または1/tである。tはkxの約数である。
【００８７】
r=2の場合、m=2kxとなり、１クロックで2kx時刻分のパスを遡ってトレースバック処理が行われる。パスメモリ用RAM８２には１アドレスあたりkx時刻分のパス選択情報が格納されているので、トレースバック処理においては１クロックで２つのアドレスに格納されたパス選択情報を読み出す必要がある。
【００８８】
従って、r=2の場合は、２つの読み出しポートを備えたデュアルポートRAMがパスメモリ用RAM８２として用いられる。ただし、２つのポートを使ってパス選択情報を読み出している最中に書き込みが生じた際、一方のポートを書き込みに使用する必要があり、その際の読み出しは他方のポートからしか行うことができない。
【００８９】
一方、rの値が1/tであり、 r≦１の場合、１クロックでkx/t時刻分のパスを遡ってトレースバック処理が行われる。kx時刻分のパス選択情報のトレースバック処理がtクロックで行われることになる。トレースバック処理においては１クロックで１つのアドレスに格納されたパス選択情報を読み出せば済む。
【００９０】
r≦１の場合も２つのポートを備えたデュアルポートRAMがパスメモリ用RAM８２として用いられるようにしてもよい。この場合、パス選択情報を読み出している最中に書き込みが生じても一方のポートを使用して読み出しを続けることが可能となる。パス選択情報の読み出しと書き込みをそれぞれ独立に行うことが出来るため、パス選択情報の読み出しが書き込みの影響を受けることはない。
【００９１】
次に、正の整数sを用いて、一回のトレースバック処理によって得られる復号ビット数をskxビットとする。トレースバック回路８３はT+skx時刻分のパス選択情報がパスメモリ用RAM８２に書き込まれた後、トレースバック処理を開始する。トレースバック回路８３により行われるトレースバック処理は、パスメモリ用RAM８２に書き込まれたT+skx時刻分のパス選択情報を順次読み出してパスを遡り、skxビットの復号結果を得る処理となる。
【００９２】
上述したようにパスメモリ用RAM８２の１アドレスにはkx時刻分のパス選択情報が書き込まれているので、T+skx時刻分のパス選択情報はα+s個のアドレスに格納されている。トレースバック処理のためにT+skx時刻分のパス選択情報を読み出すにはα+s回の読み出し操作が必要になる。
【００９３】
その後、パスメモリ用RAM８２に対するパス選択情報の書き込みがs回行われる毎に次のトレースバック処理がトレースバック回路８３により開始される。
【００９４】
s回の書き込みのうちの最後の１回の書き込みは、s回の書き込みの直後に開始されるトレースバック処理において最初に使用される情報である。従って、書き込みを行った後、その読み出しポートから、直前に書き込んだ書き込み情報を出力するいわゆるWrite-first動作を行うRAMをパスメモリ用RAM８２として用いるようにしてもよい。また、後述するように、遅延素子を用い、遅延させた書き込み情報がトレースバック処理において最初に使用されるようにしてもよい。
【００９５】
以上のように、パス選択情報が毎クロック入力される場合、生き残りパス処理器７４においては、kクロック毎にパスメモリ用RAM８２に対する書き込みが行われ、書き込みがs回行われる毎にトレースバック処理が開始される。次のトレースバック処理を開始するまでの時間であるskクロックの間に１回のトレースバック処理を終了するには、skクロックの間に、T+skx時刻分のパス選択情報の読み出しとs回の書き込みを行う必要がある。
【００９６】
よって、rとsは下式（１４）に示す関係を満たす必要がある。式（１４）よりsは下式（１５）で表される。関数ceiling(ｂ)は、実数ｂの値を超える整数のうちの最小の整数を表す。
【数１４】
2010206570.tif 000012
【数１５】
2010206570.tif 000013
【００９７】
T+skx時刻分のパス選択情報を読み出してトレースバック処理をlクロックかけて行い、skxビットの復号結果が得られる。トレースバック処理に要するクロック数lは下式（１６）で表される。
【数１６】
2010206570.tif 000014
【００９８】
また、１クロックでm時刻分のパスを遡るトレースバック回路８３の個数をpとする。後述するように、トレースバック回路を複数設けることによって生き残りパス処理器７４を構成することも可能である。
【００９９】
lクロックに渡って１回のトレースバック処理を行う一方で、kクロック毎にパスメモリ用RAM８２に対する書き込みが行われるため、パスメモリ用RAM８２のアドレス数はceiling(l/k)-1だけ増やされる。これは、トレースバック処理に使用するパス選択情報が読み出される前に上書きされるのを防ぐためのものである。
【０１００】
パスメモリ用RAM８２のアドレス数（深さ）aは下式（１７）で表される。
【数１７】
2010206570.tif 000015
【０１０１】
以上より、生き残りパス処理器７４に設けられるメモリサイズMは下式（１８）で表され、レイテンシLは下式（１９）で表される。式（１８）のMは、パスメモリ用RAM８２のメモリサイズakxNと、シフトレジスタ８１のメモリサイズkxNを加算したものに相当する。
【数１８】
2010206570.tif 000016
【数１９】
2010206570.tif 000017
【０１０２】
生き残りパス処理器７４のメモリサイズMとレイテンシLを表１に対応する形でまとめると表２に示すようなものになる。
【表２】
2010206570.tif 000018
【０１０３】
また、T=112，x=2の場合において、r=2としてkの値を変化させたときの生き残りパス処理器７４のメモリサイズMを図８に示し、レイテンシLを図９に示す。トレースバック長T=112がkxで割り切れない場合には、112を超え、かつkxで割り切れる最小の整数をTとして計算を行った結果を図８，９に示している。
【０１０４】
以上のような生き残りパス処理器７４の構成によれば、通常用いられるようにkの値を３としたときには、one-pointerアルゴリズムやpretrace-backアルゴリズムと比較して約２３％のメモリサイズ、レイテンシの削減が可能となる。また、生き残りパス処理器７４の構成によれば、特許文献１で提案されているアルゴリズムと比較すると、レイテンシは約９％増加してしまうが、メモリサイズについては約２３％の削減が可能となる。
【０１０５】
［生き残りパス処理器の構成パラメータの決定手順］
図１０のフローチャートを参照して、生き残りパス処理器７４の構成パラメータの決定手順について説明する。
【０１０６】
この手順に従って、各構成パラメータが受信装置５１の設計時などにおいて決定され、決定された構成パラメータによって規定される生き残りパス処理器７４が生成される。
【０１０７】
ステップＳ０において、２または1/tであるrの値と、r=2のときk＞１、r≦１のときk＞1/r=tを満たす正の整数kの値が決定される。tはkxの約数である。rとkの決定手順については図１２のフローチャートを参照して後述する。
【０１０８】
ステップＳ１において、ステップＳ０で決定されたrとkの値を用いて、上式（１３）に従ってmの値が計算される。xは要求される性能などによって予め定められている値である。
【０１０９】
ステップＳ２において、x，T，k，rの値を用いて、その他の構成パラメータであるs，l，aの値が計算される。Tの値も要求される性能などによって予め定められている値である。
【０１１０】
次に、図１１のフローチャートを参照して、図１０のステップＳ２において行われるs，l，aの値の計算の手順について説明する。説明の便宜上、ステップＳ０の詳細より先にステップＳ２の詳細について説明する。
【０１１１】
ステップＳ１０において、上式（１２）に従ってαの値が計算される。
【０１１２】
ステップＳ１１においてr=2であるか否かが判定される。
【０１１３】
r=2であるとステップＳ１１において判定された場合、ステップＳ１２において、上式（１５）に従ってsの値が計算される。
【０１１４】
また、ステップＳ１３において、上式（１６）に従ってlの値が計算される。
【０１１５】
r=2ではなく、r=1/tであるとステップＳ１１において判定された場合、ステップＳ１４において、上式（１５）に従ってsの値が計算される。
【０１１６】
また、ステップＳ１５において、上式（１６）に従ってlの値が計算される。
【０１１７】
s，lの値が計算された後、ステップＳ１６において、上式（１７）に従ってaの値が計算される。その後、図１０のステップＳ２に戻り、パラメータの決定手順が終了される。
【０１１８】
N=64，T=114，x=2とした場合の計算結果の具体例について説明する。
【０１１９】
ここでは、k=3，r=2が図１０のステップＳ０において決定されているものとする。図１０のステップＳ１においてはm=2・3・2=12が求められている。
【０１２０】
この場合、図１１のステップＳ１０においては、α=114/(3・2)=19が計算される。ここではr=2であるためステップＳ１１の判定の後、ステップＳ１２においてs=ceiling((19-1)/(2・(3-1)))=5が計算される。
【０１２１】
ステップＳ１３においてl=ceiling((19+2・5-1)/2)=14が計算され、ステップＳ１６においてa=19+5+ceiling(14/3)-1=28が計算される。
【０１２２】
N=64，T=114，x=2，k=3，r=2として求められた各構成パラメータの計算結果を表３の左から２列目に示す。左から３列目、４列目、５列目に示す構成パラメータの計算については順に後述する。
【表３】
2010206570.tif 000019
【０１２３】
次に、図１２のフローチャートを参照して、図１０のステップＳ０において行われるkとrの値の決定の手順について説明する。
【０１２４】
kとrの値はメモリサイズとレイテンシが最小、かつ回路規模が最小となるように決定するのが望ましいが、生き残りパス処理器７４のkとrの値については、メモリサイズが最小となるkとrの値が、回路規模が最小となるkとrの値であるとは限らない。なぜならば、生き残りパス処理器７４のメモリサイズはパスメモリ用RAM８２のメモリサイズとシフトレジスタ８１のメモリサイズを足し合わせたものであり、一般的に、フリップフロップを用いて構成されるシフトレジスタの１ビットあたりの回路規模はRAMの１ビットあたりの回路規模と比べて大きいためである。
【０１２５】
また、r=2のときはパスメモリ用RAM８２としてデュアルポートRAMを用いる必要があるが、p=1かつr≦1かつs=1のときはシングルポートRAMを用いて構成可能である。これは、上述したように、r=2のときは１クロックで２アドレス分のパス選択情報を読み出す必要があり、読み出しポートを２つ備えたRAMが必要になる。一方、r≦1かつs=1のときはトレースバック回路８３が１つのポートを用いてパス選択情報を読み出せばよく、さらに、読み出しを行っている間に新たなパス選択情報の書き込みが発生することもないからである。
【０１２６】
一般的に、RAMの深さが浅い場合、デュアルポートRAMの回路規模はシングルポートRAMの回路規模よりも約２０％大きくなる（非特許文献４）。パスメモリ用RAM８２のメモリサイズがデュアルポートRAMの場合と比べて２０％程度大きかったとしても、シングルポートRAMで実現することができれば、そのパスメモリ用RAM８２の回路規模はデュアルポートRAMで実現した場合と同等の規模になる。
【０１２７】
よって、kとrの値の選択に際しては、単にメモリサイズやレイテンシだけでなく、回路規模も考慮される。具体的には、下式（２０）で表されるパスメモリ用RAM８２の回路規模yRAMと、シフトレジスタ８１の回路規模yREG・kxNとを合わせた回路規模B１が最小となるkとrの値が決定される。
【数２０】
2010206570.tif 000020
【０１２８】
ここで、yRAMは、RAMの種類、RAMのビット幅、および深さによって定まる。RAMの種類としては、シングルポートRAM、1-writeポート1-readポートのデュアルポートRAM、2-writeポート2-readポートのデュアルポートRAMなどがある。また、yREGは、１ビットあたりの回路規模であり、使用するセルライブラリによって定まる。
【０１２９】
ステップＳ２０において、検索対象とするkの最大値kmaxとrの最小値rminが設定される。ただし、kmaxとrminは、kmax>1/rminの関係を満たすものとする。また、yREGが設定される。
【０１３０】
ステップＳ２１において、kとrが初期化され、それぞれの値として２が設定される。
【０１３１】
ステップＳ２２において、トレースバック長Tが下式（２１）に従って計算される。
【数２１】
2010206570.tif 000021
【０１３２】
式（２１）において、Tinitはトレースバック長の初期値である。kの値を変化させたときにTinitがkxで割り切れればそのTinitを生き残りパス処理器７４のトレースバック長Tとし、kxで割り切れなければTinitを超え、かつkxで割り切れる最小の整数をTとする。
【０１３３】
ステップＳ２３において、図１１を参照して説明した手順に従って構成パラメータs，l，aの値が計算される。
【０１３４】
ステップＳ２４において、いまのrの値と、ステップＳ２３で計算された構成パラメータs，aの値と、kxNの値から、RAMの種類とyRAMが定められる。
【０１３５】
具体的には、RAMの種類としては、p=1かつr≦1かつs=1の場合にはシングルポートRAMが定められる。また、r=2もしくはp=2の場合には読み出しポートを２つ備えるデュアルポートRAMが定められ、それ以外の場合には読み出しポートを１つ備えるデュアルポートRAMが定められる。また、決定した種類のRAMでビット幅kxN、深さaとしたときに回路規模yRAMがどの程度であるのかが、データシートやコンパイルなどによって定められる。
【０１３６】
ここで、浅すぎるために深さaのRAMを実現することができない場合には、実現可能な最低の深さのRAMの回路規模がyRAMとされる。また、幅が広すぎるためにビット幅kxNのRAMを実現することができない場合には、kxNビットを分割して複数のRAMに格納するようにされ、その複数のRAMの回路規模の合計がyRAMとされる。
【０１３７】
ステップＳ２５において、上式（２０）に従って回路規模B１が計算され、計算結果が保存される。
【０１３８】
ステップＳ２６において、いまのkの値がkmax以上であるか否かが判定される。
【０１３９】
いまのkの値がkmax以上ではないとステップＳ２６において判定された場合、ステップＳ２７において、kの値が１だけインクリメントされ、その後、ステップＳ２２以降の処理が繰り返される。
【０１４０】
一方、いまのkの値がkmax以上であるとステップＳ２６において判定された場合、ステップＳ２８において、いまのrの値がrmin以下であるか否かが判定される。
【０１４１】
いまのrの値がrmin以下ではないとステップＳ２８において判定された場合、ステップＳ２９において、いまのrの値が２であるか否かが判定される。
【０１４２】
いまのrの値が２であるとステップＳ２９において判定された場合、ステップＳ３０において、tの値として１が設定される。
【０１４３】
また、ステップＳ３１において、rの値として１が設定される。
【０１４４】
ステップＳ３２において、kの値としてt+1が設定され、その後、ステップＳ２２以降の処理が繰り返される。
【０１４５】
一方、いまのrの値が２ではないとステップＳ２９において判定された場合、ステップＳ３３において、tの値が１だけインクリメントされる。
【０１４６】
ステップＳ３４において、いまのtの値がkxの約数であるか否かが判定される。
【０１４７】
いまのtの値がkxの約数ではないとステップＳ３４において判定された場合、ステップＳ３３に戻り、tの値を１だけインクリメントすることが繰り返される。
【０１４８】
いまのtの値がkxの約数であるとステップＳ３４において判定された場合、ステップＳ３５において、rの値として1/tが設定され、その後、ステップＳ３２以降の処理が行われる。
【０１４９】
一方、いまのrの値がrmin以下であるとステップＳ２８において判定された場合、ステップＳ３６において、それまでに保存しておいたB１の中で、B１を最小にするkとrの値が選択される。
【０１５０】
ステップＳ３７において、上式（２１）に従ってトレースバック長Tが計算される。その後、図１０のステップＳ０に戻り、それ以降の処理が行われる。
【０１５１】
N=64，Tinit=112，x=2とした場合の具体的な計算について説明する。
【０１５２】
ステップＳ２０においてはkmax，rmin，yREGが設定されるが、ここでは、kmax=10，rmin=1/2，yREG=10とする。
【０１５３】
ステップＳ２１においてkとrの値として２が設定され、ステップＳ２２においてTの値が計算された後、ステップＳ２３において構成パラメータs，l，aの値が計算される。この場合、s=14，l=28，a=55が計算される。
【０１５４】
ステップＳ２４においてその計算結果からRAMの種類とyRAMが定められる。ここでは説明を簡単にするため、RAMの１ビットあたりの回路規模がビット幅kxNと深さaに依存せず一定で、yRAMはRAMのメモリサイズakxNのみに依存するものとする。
【０１５５】
RAMの種類がシングルポートRAMの場合、つまりp=1かつr≦1かつs=1の場合、yRAM=2akxNとなり、デュアルポートRAMの場合、yRAM=2.4akxとする。また、ここでは比較的深さの浅いRAMを仮定している。これより、いまのrの値はr=2であるので、yRAM=2.4akxN=2.4・55・2・2・64=33792となる。
【０１５６】
ステップＳ２５においては、B１=33792+10・2・2・64=36352が計算され、この計算結果が保存される。ステップＳ２６においては、いまkの値はk=2であり、kmax=10より小さいためステップＳ２７に進み、k=3が設定された後、ステップＳ２２に戻る。
【０１５７】
ステップＳ２２乃至Ｓ２７の処理が繰り返され、k=10になっている場合、いまのkの値がkmax=10以上であるとステップＳ２６において判定され、ステップＳ２８に進む。
【０１５８】
ステップＳ２８においては、いまのrの値はr=2であり、rmin=1/2より大きいためステップＳ２９に進む。その後、上述したようなステップＳ２９乃至Ｓ３２の処理が、いまのrの値が1/2となり、rmin=1/2以下であるとステップＳ２８において判定されるまで繰り返される。
【０１５９】
ステップＳ３６においては、B１の値を最小にするkとrの値としてk=8，r=1が選択され、ステップＳ３７において、T=112が計算される。
【０１６０】
以上のような具体的な値を用いて計算され、ステップＳ２５において保存されるB１の値を示すと表４に示すようなものになる。表４の計算結果の数字に重ねて示す矢印は、計算により求められる順番を示す。k=8，r=1であるとき、B１の値として26624が求められる。
【表４】
2010206570.tif 000022
【０１６１】
N=64，T=112，x=2，k=8，r=1とし、図１０の手順によって求められた各構成パラメータの計算結果を表３の左から３列目に示す。
【０１６２】
以上のように、メモリサイズやレイテンシだけでなく、回路規模なども考慮してkとrの値が決定され、他の構成パラメータが決定される。
【０１６３】
これにより、従来のアルゴリズムの場合と比べて同等もしくはそれ以下のメモリサイズおよびレイテンシを実現する事が可能となる。また、パスメモリ用RAM８２を分割して用いないため、読み出した情報を選択するセレクタも不要となり、読み出しの制御も容易となるため、周辺回路の回路規模も少なくて済む。さらに、パスメモリ用RAMの種類を考慮することによっても回路規模を削減することが可能になる。
【０１６４】
［生き残りパス処理器の構成の詳細］
図１３は、生き残りパス処理器７４の構成例を示すブロック図である。
【０１６５】
図１３は、k=3，r=2のときに求められた表３の左から２列目の構成パラメータによって規定される生き残りパス処理器７４の構成を示す。図６に示される構成と同じ構成には同じ符号を付してある。重複する説明については適宜省略する。上述したようにN=64，x=2であるとき、他の構成パラメータの値はそれぞれT=114，s=5，l=14，m=12，p=1，a=28となる。
【０１６６】
p=1であるから、トレースバック処理を行う回路としてトレースバック回路８３が１つ設けられる。
【０１６７】
コントローラ９１は、パスメモリ用RAM８２に対するパス選択情報の書き込み、パスメモリ用RAM８２からのパス選択情報の読み出しを制御する。
【０１６８】
LIFO(Last-In First-Out)９２は、トレースバック回路８３から供給されたデータを格納し、新しく格納したデータから順に読み出して復号結果として出力する。
【０１６９】
図１４は、図１３のパスメモリ用RAM８２に対するパス選択情報の書き込みとパスメモリ用RAM８２からのパス選択情報の読み出しのタイミングを示すメモリアクセスチャートである。コントローラ９１による制御に従って、図１４に示すような動作が実現される。
【０１７０】
図１４の横軸はクロックを表し、縦軸はパスメモリ用RAM８２のアドレスを表す。また、黒塗りの１つの四角は、ポート１を使って行われるパス選択情報の書き込みのタイミングと書き込み先となるアドレスを表す。白抜きの１つの四角は、ポート１を使って行われるパス選択情報の読み出しのタイミングと読み出し元となるアドレスを表す。柄付の１つの四角は、ポート２を使って行われるパス選択情報の読み出しのタイミングと読み出し元となるアドレスを表す。後述するメモリアクセスチャートにおいても同様である。
【０１７１】
k=3であるから、シフトレジスタ８１においては毎クロック入力されるxN=2・64=128ビットのパス選択情報が３入力分蓄積され、３入力分の情報がまとめて出力される。
【０１７２】
図１４に示すように、１つのアドレスに対するパス選択情報の書き込みは、３クロック毎に、ポート１を使用して行われることになる。１回の書き込みによって書き込まれるパス選択情報のビット幅はkxN=3・2・64=384ビットとなる。
【０１７３】
図１４の例においては、３クロック目のタイミングにおいてアドレス０に対して書き込みが行われ、６クロック目のタイミングにおいてアドレス１に対して書き込みが行われている。
【０１７４】
パスメモリ用RAM８２にT+skx=114+5・3・2=144時刻分のパス選択情報が格納された７２クロック目のタイミングにおいて、パスメモリ用RAM８２からのパス選択情報の読み出しが開始される。読み出しが開始された後も、パスメモリ用RAM８２に対するパス選択情報の書き込みは続けられる。
【０１７５】
r=2であるから、１クロック毎に２つのアドレスにアクセスしてパス選択情報の読み出しが行われる。この場合、kx=3・2=6時刻分の２倍、すなわち2kx=12時刻分の情報である、2kxN=768ビットのパス選択情報が１クロック毎に読み出され、１クロックでm=12時刻分のパスを遡るトレースバック回路８３に入力される。トレースバック回路８３においては、T+skx=144時刻分のトレースバック処理がl=14クロック分の時間だけかけて行われる。
【０１７６】
ただし、一方のポートを使って書き込みが行われるタイミングでは、他方のポートを使ってしかパス選択情報の読み出しを行うことができない。この場合、１アドレスから読み出されたパス選択情報だけがトレースバック回路８３に入力され、トレースバック回路８３においては１クロックでm/2=6時刻分のパスだけを遡ってトレースバック処理が進められる。
【０１７７】
図１４の例においては、７２クロック目のタイミングにおいてアドレス２３に対する書き込みがポート１を使用して行われるとともに、アドレス２２からの読み出しがポート２を使用して行われている。また、パス選択情報の書き込みが行われない７３クロック目のタイミングにおいてはアドレス２１からの読み出しがポート１を使用して行われ、アドレス２０からの読み出しがポート２を使用して行われている。読み出されたパス選択情報は順次、トレースバック回路８３によりパスを遡るのに用いられる。
【０１７８】
７２クロック目のタイミングまでに格納されたパス選択情報の読み出しは、８５クロック目のタイミングまで続けられ、その後、パス選択情報の書き込みと読み出しが繰り返される。
【０１７９】
トレースバック回路８３からの１クロック毎の出力であるm=12ビットのうち、最後のs=5アドレス分のパス選択情報に対する出力がLIFO９２に入力され、１回のトレースバック処理が行われる毎に、skx=30ビットが復号結果として出力される。
【０１８０】
ここで、パスメモリ用RAM８２は読み出しポートを２つ備えるデュアルポートRAMであり、さらに、書き込みを行った後の読み出しポートから、直前に書き込んだ情報を出力するWrite-first動作を行うものである。
【０１８１】
図１５は、生き残りパス処理器７４の他の構成例を示すブロック図である。
【０１８２】
図１５の構成を実現するのに用いられる構成パラメータは、図１３の構成を実現するのに用いられる構成パラメータと同じである。図１３の構成と同じ構成には同じ符号を付してある。
【０１８３】
例えば、図１３のパスメモリ用RAM８２のようなWrite-first動作を行うRAMを用いないとした場合、図１５に示すように、図１３の構成と同じ構成に加え、遅延素子１０１とセレクタ１０２が用いられて生き残りパス処理器７４が構成される。
【０１８４】
遅延素子１０１は、シフトレジスタ８１の出力を、パスメモリ用RAM８２からのパス選択情報の読み出しにかかる時間と同じ時間だけ遅延させ、セレクタ１０２に出力する。
【０１８５】
セレクタ１０２は、遅延素子１０１の出力と、ポート１を使用してパスメモリ用RAM８２から読み出したパス選択情報のうちのいずれかを選択し、トレースバック回路８３に出力する。セレクタ１０２は、例えば図１４の７２クロック目のように、トレースバック処理を開始するタイミングに読み出すアドレス２２のパス選択情報が、パスメモリ用RAM８２から出力されるタイミングでは遅延素子１０２の出力を選択し、それ以外のタイミングではパスメモリ用RAM８２から読み出したパス選択情報を選択する。パスメモリ用RAM８２のポート２から読み出されたパス選択情報は、トレースバック回路８３に直接供給される。
【０１８６】
これにより、Write-first動作によって供給される情報と同じ情報をトレースバック回路８３に供給することが可能になる。図１５のパスメモリ用RAM８２においても、図１４に示されるのと同じタイミングでパス選択情報の書き込みと読み出しが行われる。
【０１８７】
遅延素子１０１による遅延が１クロック分の時間であるとき、書き込み情報を１クロック分の時間だけ遅延させたのと同じ出力を生成するのにkxNビット分の遅延素子は必要ない。例えば、シフトレジスタ８１を構成するレジスタの段数をもう一段追加し、k+1段とすることによっても書き込み情報を１クロック分の時間だけ遅延させたのと同じ出力を生成することが可能である。
【０１８８】
このときの生き残りパス処理器７４の構成は、xNビット分のレジスタをシフトレジスタ８１の内部に追加するだけでよく、他の構成は図１３の構成と同じ構成である。
【０１８９】
図１６は、生き残りパス処理器７４のさらに他の構成例を示すブロック図である。
【０１９０】
図１６は、k=8，r=1のときに求められた表３の左から３列目の構成パラメータによって規定される生き残りパス処理器７４の構成を示す。上述したようにN=64，x=2であるとき、他の構成パラメータの値はそれぞれT=112，s=1，l=8，m=16，p=1，a=8となる。
【０１９１】
構成パラメータの値は異なるが、パスメモリ用RAM８２のポートの数が異なる点を除いて、他の構成自体は図１３の構成と同じ構成である。
【０１９２】
図１７は、図１６のパスメモリ用RAM８２に対するパス選択情報の書き込みとパスメモリ用RAM８２からのパス選択情報の読み出しのタイミングを示すメモリアクセスチャートである。
【０１９３】
k=8であるから、シフトレジスタ８１においては毎クロック入力されるxN=2・64=128ビットのパス選択情報が８入力分蓄積され、８入力分の情報がまとめて出力される。
【０１９４】
図１７に示すように、１つのアドレスに対するパス選択情報の書き込みは、８クロック毎に行われることになる。１回の書き込みによって書き込まれるパス選択情報のビット幅はkxN=8・2・64=1024ビットとなる。
【０１９５】
図１７の例においては、８クロック目のタイミングにおいてアドレス０に対して書き込みが行われ、１６クロック目のタイミングにおいてアドレス１に対して書き込みが行われている。
【０１９６】
パスメモリ用RAM８２にT+skx=112+1・8・2=128時刻分のパス選択情報が格納された６４クロック目のタイミングの次のタイミングである６５クロック目のタイミングにおいてパス選択情報の読み出しが開始される。
【０１９７】
r=1であるから、１クロック毎に異なる１アドレスにアクセスしてパス選択情報の読み出しが行われる。この場合、kx=16時刻分の情報である、kxN=1024ビットのパス選択情報が１クロック毎に読み出され、１クロックでm=16時刻分のパスを遡るトレースバック回路８３に入力される。トレースバック回路８３においては、T+skx=128時刻分のトレースバック処理がl=8クロック分の時間だけかけて行われる。
【０１９８】
図１７の例においては、６５クロック目のタイミングにおいてアドレス６からの読み出しが行われ、６６クロック目のタイミングにおいてアドレス５からの読み出しが行われている。読み出されたパス選択情報は順次、トレースバック回路８３によりパスを遡るのに用いられる。
【０１９９】
６４クロック目のタイミングまでに格納されたパス選択情報の読み出しは、７１クロック目のタイミングまで続けられ、その後、同様にしてパス選択情報の書き込みと読み出しが繰り返される。
【０２００】
トレースバック回路８３からの１クロック毎の出力であるm=16ビットのうち、最後のs=1アドレス分のパス選択情報に対する出力がLIFO９２に入力され、１回のトレースバック処理が行われる毎に、skx=16ビットが復号結果として出力される。
【０２０１】
図１６のパスメモリ用RAM８２は、表３の左から３列目に示されるようにp=1かつr≧1かつs=1であるのでシングルポートRAMである。また、このシングルポートRAMはWrite-first動作を行うものである。
【０２０２】
＜変形例１＞
一般的に、チップにおけるパスメモリ用RAM８２のレイアウト位置は決まっている。配線遅延に伴うモジュールのレイアウトの自由度低下を防ぐために、モジュール内に設けられるトレースバック回路８３においては、RAMから読み出した情報を一度フリップフロップで保持してから使用するようになされている。
【０２０３】
図１８は、チップにおけるパスメモリ用RAM８２のレイアウトの例を示す図である。
【０２０４】
図１８に示すように、同じチップ上に、トレースバック回路８３を含むモジュールとパスメモリ用RAM８２が配設される。図１８においてはトレースバック回路８３とパスメモリ用RAM８２だけを示しているが、受信装置５１の他の構成も、適宜、トレースバック回路８３と同じモジュール内、または異なるモジュール内に設けられる。受信装置５１の他の構成が、トレースバック回路８３が設けられるチップと異なるチップに設けられることもある。
【０２０５】
トレースバック回路８３とパスメモリ用RAM８２間の、トレースバック回路８３を含むモジュールの部分には図１８に示すようにフリップフロップ（文字“Ｄ”を付して示すブロック）が設けられる。例えばパスメモリ用RAM８２から読み出されたデータはそのフリップフロップで保持してからトレースバック回路８３に供給され、トレースバック処理に用いられる。
【０２０６】
このフリップフロップの回路規模も考慮して、図１２のフローチャートを参照して説明した手順と同様の手順によってkとrの値を決定することも可能である。
【０２０７】
この場合、下式（２２）で表されるパスメモリ用RAM８２の読み出しポート数zの値が用いられる。また、このフリップフロップの回路規模も考慮した回路規模を表すB２が計算され、B２を最小にするkとrの値が決定される。B２は下式（２３）によって表される。
【数２２】
2010206570.tif 000023
【数２３】
2010206570.tif 000024
【０２０８】
図１９のフローチャートを参照して、図１０のステップＳ０において行われるkとrの決定の手順の変形例について説明する。
【０２０９】
図１９のステップＳ５０乃至Ｓ５３，Ｓ５６乃至Ｓ６５，Ｓ６７の処理は、図１２のステップＳ２０乃至Ｓ２３，Ｓ２６乃至Ｓ３５，Ｓ３７の処理と同じ処理である。重複する説明については適宜省略する。
【０２１０】
ステップＳ５０においてkmax，rmin、およびyREGが設定され、ステップＳ５１においてkとrの値としてそれぞれ２が設定される。
【０２１１】
ステップＳ５２においてトレースバック長Tが計算され、ステップＳ５３において構成パラメータs，l，aの値が計算される。
【０２１２】
ステップＳ５４において、いまのrの値と、ステップＳ５３で計算された構成パラメータs，aの値と、kxNの値から、RAMの種類とyRAMが定められる。また、上式（２２）に従って読み出しポート数zが定められる。
【０２１３】
定められたRAMの種類がシングルポートRAM、もしくは１つの読み出しポートを備えるデュアルポートRAMのときはz=1となり、２つの読み出しポートを備えるデュアルポートRAMのときはz=2となる。
【０２１４】
ステップＳ５５において、上式（２３）に従って回路規模B２が計算され、計算結果が保存される。
【０２１５】
ステップＳ５６においていまのkの値がkmax以上であると判定され、ステップＳ５８においていまのrの値がrmin以下であると判定された場合、ステップＳ６６に進む。
【０２１６】
ステップＳ６６において、それまでに保存しておいたB２の中で、B２の値を最小にするkとrの値が選択される。
【０２１７】
ステップＳ６７においてトレースバック長Tが計算され、その後、図１０のステップＳ０以降の処理が行われる。
【０２１８】
上述した例と同様にN=64，Tinit=112，x=2とした場合、図１９の手順によってk=8，r=1，T=112が計算される。この場合に図１０の手順によって求められる各構成パラメータの計算結果も、表３の左から３列目に示される結果と同様の結果になる。
【０２１９】
＜変形例２＞
トレースバック回路８３においては１クロックでm/x段のN to 1セレクト処理を行う必要がある。N to 1セレクト処理はNの状態の中から１つの状態（パス）を選択する処理である。１クロックでm/x段のN to 1セレクト処理を行うことの詳細については後述する。
【０２２０】
生き残りパス処理器７４内の動作のタイミングの基準となるクロックの周波数として使用したいクロック周波数をfｃとすると、このクロック周波数fｃでの動作が不可能である場合に問題となる。mが大きいために１クロックの時間内に完了しなければならないトレースバック処理の遅延が大きい場合などに、クロック周波数fｃでの動作が不可能になることがある。
【０２２１】
これを解決するには、クロック周波数fｃで動作可能となるように、遡るパスの数（時刻）を表すmの値を小さくすればよく、mの値を小さくするには、上式（１３）より、kかrの値を小さくすればよい。クロック周波数fｃで動作可能なmの最大値をmfcとし、図２０に示す手順によってkとrの値を決定することで、クロック周波数fｃで動作可能となるmの値を求めることができる。
【０２２２】
図２０のフローチャートを参照して、図１０のステップＳ０において行われるkとrの決定の手順の他の変形例について説明する。
【０２２３】
図２０に示す処理は、ステップＳ８３，Ｓ８４の処理が追加されている点を除いて、図１９を参照して説明した処理と同様の処理である。重複する説明については適宜省略する。
【０２２４】
ステップＳ８１においてkmax，rmin、およびyREGが設定され、ステップＳ８２においてkとrの値としてそれぞれ２が設定される。
【０２２５】
ステップＳ８３において、上式（１３）に従ってmの値が計算され、ステップＳ８４において、mの値がmfc以下であるか否かが判定される。
【０２２６】
mの値がmfc以下であるとステップＳ８４において判定された場合、ステップＳ８５においてトレースバック長Tが計算され、ステップＳ８６において構成パラメータs，l，aが計算される。
【０２２７】
ステップＳ８７において、いまのｒの値と、ステップＳ８６で計算された構成パラメータs，aの値と、kxNの値から、RAMの種類とyRAMが定められる。また、上式（２２）に従って読み出しポート数zが定められる。
【０２２８】
ステップＳ８８において、上式（２３）に従って回路規模B２が計算され、計算結果が保存される。
【０２２９】
一方、mの値がmfc以下ではないとステップＳ８４において判定された場合、ステップＳ８５乃至Ｓ８９はスキップされる。
【０２３０】
ステップＳ８９においていまのkの値がkmax以上であると判定され、ステップＳ９１においていまのrの値がrmin以下であると判定された場合、ステップＳ９９に進む。
【０２３１】
ステップＳ９９において、それまでに保存しておいたB２の中で、B２の値を最小にするkとrの値が選択される。
【０２３２】
ステップＳ１００においてトレースバック長Tが計算され、その後、図１０のステップＳ０以降の処理が行われる。
【０２３３】
上述した例と同様にN=64，Tinit=112，x=2とし、さらに、mfc=8とした場合、図２０の手順によってk=4，r=1，T=112が計算される。この場合に図１０の手順によって求められる各構成パラメータの計算結果を表３の左から４列目に示す。
【０２３４】
なお、図２０においてはパスメモリ用RAM８２から読み出したデータを保持するフリップフロップの回路規模を考慮して構成パラメータを計算する場合について説明したが、この回路規模を考慮することなく、図１２の処理にステップＳ８３，Ｓ８４の処理を追加して構成パラメータが計算されるようにしてもよい。
【０２３５】
図２１は、生き残りパス処理器７４の構成例を示すブロック図である。
【０２３６】
図２１は、k=4，r=1のときに求められた表３の左から４列目の構成パラメータによって規定される生き残りパス処理器７４の構成を示す。上述したようにN=64，x=2であるとき、他の構成パラメータの値はそれぞれT=112，s=5，l=19，m=8，p=1，a=23となる。構成パラメータの値は異なるが、構成自体は図１６の構成と同じ構成である。
【０２３７】
図２２は、図２１のパスメモリ用RAM８２に対するパス選択情報の書き込みとパスメモリ用RAM８２からのパス選択情報の読み出しのタイミングを示すメモリアクセスチャートである。
【０２３８】
k=4であるから、シフトレジスタ８１においては毎クロック入力されるxN=2・64=128ビットのパス選択情報が４入力分蓄積され、４入力分の情報がまとめて出力される。
【０２３９】
図２２に示すように、１つのアドレスに対するパス選択情報の書き込みは、４クロック毎に行われることになる。１回の書き込みによって書き込まれるパス選択情報のビット幅はkxN=4・2・64=512ビットとなる。
【０２４０】
図２２の例においては、４クロック目のタイミングにおいてアドレス０に対して書き込みが行われ、８クロック目のタイミングにおいてアドレス１に対して書き込みが行われている。
【０２４１】
パスメモリ用RAM８２にT+skx=112+5・4・2=152時刻分のパス選択情報が格納された７６クロック目のタイミングの次のタイミングである７７クロック目のタイミングにおいてパス選択情報の読み出しが開始される。
【０２４２】
r=1であるから、１クロック毎に異なる１アドレスにアクセスしてパス選択情報の読み出しが行われる。この場合、kx=8時刻分の情報である、kxN=512ビットのパス選択情報が１クロック毎に読み出され、１クロックでm=8時刻分のパスを遡るトレースバック回路８３に入力される。トレースバック回路８３においては、T+skx=152時刻分のトレースバック処理がl=19クロック分の時間だけかけて行われる。
【０２４３】
図２２の例においては、７７クロック目のタイミングにおいてアドレス１７からの読み出しが行われ、７８クロック目のタイミングにおいてアドレス１６からの読み出しが行われている。読み出されたパス選択情報は順次、トレースバック回路８３によりパスを遡るのに用いられる。
【０２４４】
７６クロック目のタイミングまでに格納されたパス選択情報の読み出しは、９４クロック目のタイミングまで続けられ、その後、同様にしてパス選択情報の書き込みと読み出しが繰り返される。
【０２４５】
トレースバック回路８３からの１クロック毎の出力であるm=8ビットのうち、最後のs=5アドレス分のパス選択情報に対する出力がLIFO９２に入力され、１回のトレースバック処理が行われる毎に、skx=40ビットが復号結果として出力される。
【０２４６】
図２１のパスメモリ用RAM８２は、表３の左から４列目に示されるようにp=1かつr≧1かつs=5であるので、1-writeポート1-readポートのデュアルポートRAMである。
【０２４７】
ここで、トレースバック回路８３において１クロックでm/x段のN to 1セレクト処理を行うことの詳細について説明する。
【０２４８】
一般的に、ビタビ復号器に対する入力は、図２３に示すような畳み込み符号器によって符号化されている。
【０２４９】
図２３の例においては、レジスタ１１１−１乃至１１１−６によってシフトレジスタが構成され、１ビットのデータが入力データIとして順次それぞれのレジスタによって保持される。
【０２５０】
入力データI、レジスタ１１１−２の値、レジスタ１１１−３の値、レジスタ１１１−５の値、レジスタ１１１−６の値が加算器１１２に入力され、排他的論理和演算の結果が畳み込み符号化された出力データAとして出力される。また、入力データI、レジスタ１１１−１の値、レジスタ１１１−２の値、レジスタ１１１−３の値、レジスタ１１１−５の値、レジスタ１１１−６の値が加算器１１３に入力され、排他的論理和演算の結果が畳み込み符号化された出力データBとして出力される。図２３の畳み込み符号器は符号化率１／２の回路である。
【０２５１】
図２３の畳み込み符号器によって符号化される系列は図２４に示すトレリス線図で表すことができる。
【０２５２】
図２４において、Sn,tは時刻tにおける状態nを表す。図２４は、全状態数を例えば６４とし、時刻tおいてS0,tとなる２時刻分のパスをトレリス線図で表したものである。状態は図２３の６ビットのレジスタの値に対応し、初期状態は状態0となる。
【０２５３】
図２４の例において、各パスの近くに示す数字と「／」は、図２３の畳み込み符号器における入力と出力の関係を表す。例えばパスp４は入力データIとして0の値が入力されたとき、出力データAの値として１、出力データBの値として0が出力されたことを表す。
【０２５４】
例えば、時刻t-2において状態が0、つまりS0,t-2のとき、入力データIが0であれば図２３の各レジスタの値も0のままとなり、次の時刻t-1における状態も0、つまりS0,t-1となる。同様に、時刻t-2において状態16、つまりS16,t-2のとき、入力データIが0であれば図２３の各レジスタ値は２進数で100000となり、次の時刻t-1における状態は32、つまりS32,t-1となる。
【０２５５】
ACS処理器においては、各時刻において、64個の各状態Sn,t（0≦n≦63）に接続された２通りのパスのパスメトリックが計算される（状態間のハミング距離が加算される）。また、パスメトリックが最小のパスが生き残りパスとして選択され、１ビットのパス選択情報yn,tが出力される。
【０２５６】
そして、このパス選択情報をパスメモリに記憶しておき、後段のトレースバック回路において生き残りパスを遡ることで最も確からしい符号系列（復号結果）を得ることになる。
【０２５７】
生き残りパスの選択においては、例えば図２４のS0,t-1に接続されたS0,t-2からのパスp１とS32,t-2からのパスp３の中からパスを選択することになる。ここでp１を選択したときは0を、パスp３を選択したときは１をパス選択情報として記憶しておくことにより、トレースバックを行う際に、いずれのパスを選択したのかが分かり、前の状態を遡ることが可能になる。
【０２５８】
図２３のシフトレジスタは、入力データＩがそのLSB側に入力される構成であるため、図２４におけるパス選択情報yn,tは選択したパスの状態のMSBと一致することになる。
【０２５９】
例えば、時刻t-1における状態32のパスの選択において、S32,t-1に接続されたS16,t-2からのパスp４とS48,t-2からのパスp５のうち、パスp４を選択し、パス選択情報y32,t-1として0を記憶したとする。
【０２６０】
さらに、次の時刻tにおける状態0のパスの選択において、S0,tに接続されたS0,t-1からのパスp２とS32,t-1からのからのパスp６のうち、パスp６を選択し、パス選択情報y0,tとして１を記憶したとする。
【０２６１】
このとき、時刻tの状態0、つまりS0,tからトレースバックを開始すると、まず、トレースバック回路は、時刻tにおけるパス選択情報yn,tをパスメモリから読み出して、その中から、状態0のパス選択情報を選択してy0,t=1を得る。これにより、一つ前の状態がS32,t-1であることが分かる。
【０２６２】
次に、トレースバック回路は、時刻t-1におけるパス選択情報yn,t-1をパスメモリから読み出して、その中から、状態32のパス選択情報を選択してy32,t-1=0を得る。これにより、さらに一つ前の状態がS16,t-2であることが分かる。
【０２６３】
このように、トレースバック処理においては、順次、１時刻前の状態を遡っていくことで最も確からしい復号結果を得ることが可能となる。
【０２６４】
ここで、１時刻分の状態を遡るためには、上述したようにパスメモリから読み出した64状態分のパス選択情報yn,tの中から、現在遡っている状態におけるパス選択情報を選択する必要がある。以上においては状態数をNとしているため、これにより、N to 1セレクト処理が必要になる。
【０２６５】
また、上述したように、トレースバック回路８３においては、1クロックでm時刻分の状態を遡るようになされている。通常はm段のN to 1セレクト処理を行えばよいが、radix-2xのパス選択情報が入力される場合にはx時刻分のパス選択情報が一度にパスメモリ用RAM８２に書き込まれるため、N to 1セレクト処理の段数はm/x段となる。
【０２６６】
＜変形例３＞
トレースバック処理が、(s+u)・kクロック分の時間だけかけて行われるようにしてもよい。uはu≦sを満たす正の整数である。
【０２６７】
この場合、skクロック分の時間ではトレースバック処理は終了しない。従って、トレースバック回路を並列に複数設け、複数のトレースバック回路にパスメモリ用RAM８２のポートをそれぞれ割り当てて時間的に並行してトレースバック処理を行わせるようにしてもよい。
【０２６８】
例えば、ポート１を用いてパス選択情報を読み出して行っているトレースバック処理の途中で開始する必要のある次のトレースバック処理については、他方のトレースバック回路にポート２を用いてパス選択情報を読み出させ、その処理を行わせる。
【０２６９】
このとき、ポート１においては、(s+u)・kクロックの間にT+skx時刻分のパス選択情報の読み出しとu回の書き込みを行う必要がある。u回の書き込みのうちの１回は、式（１４）のところで説明したように直後に開始するトレースバック処理において最初に使用する情報であるので、パス選択情報の書き込みと読み出しを兼ねることができる。
【０２７０】
よって、r，sおよびuは下式（２４）に示す関係を満たす必要がある。また、式（２４）よりsは下式（２５）で表される。この例においては、上式（１５）のsを、式（２５）で表されるものに置き換えて他の構成パラメータの計算が行われる。
【数２４】
2010206570.tif 000025
【数２５】
2010206570.tif 000026
【０２７１】
さらに、式（１６）で表される、トレースバック処理に必要なクロック数lが下式（２６）で表されるものに置き換えられる。また、式（２５）はskクロック毎に開始されるトレースバック処理を(s+u)・kクロックの間に終了するように導いた条件であり、uはu≦sを満たす正の整数である。このため、この例においては、生き残りパス処理器が備える、１クロックでm時刻分のパスを遡るトレースバック回路の数は２（p=2）となる。
【数２６】
2010206570.tif 000027
【０２７２】
T=112，x=2，k=8，r=1/2，u=1として、図１０のステップＳ１においてmの値を求め、ステップＳ２において計算して求められた構成パラメータを表３の左から５列目に示す。ステップＳ２において行われる計算の手順を示す図１１のステップＳ１４，Ｓ１５においては、それぞれ上式（２５），（２６）の計算が行われる。
【０２７３】
図２５は、生き残りパス処理器７４の構成例を示すブロック図である。
【０２７４】
図２５は、表３の左から５列目の構成パラメータによって規定される生き残りパス処理器７４の構成を示す。上述したようにN=64，x=2であるとき、他の構成パラメータの値はそれぞれk=8，r=1/2，u=1，T=112，s=1，l=16，m=8，p=2，a=9となる。
【０２７５】
p=2であるから、図２５に示すように、トレースバック回路としてトレースバック回路８３−１と８３−２が設けられる。パスメモリ用RAM８２のポート１はトレースバック回路８３−１用のポートとして割り当てられ、ポート２はトレースバック回路８３−２用のポートとして割り当てられている。また、トレースバック回路８３−１，８３−２の後段にはセレクタ１２１が設けられている。他の構成自体は、例えば図２１に示す構成と同じ構成である。
【０２７６】
トレースバック回路８３−１と８３−２は、それぞれ、パスメモリ用RAM８２から読み出したパス選択情報に基づいてトレースバック処理を行い、処理の結果をセレクタ１２１に出力する。
【０２７７】
セレクタ１２１は、トレースバック回路８３−１と８３−２から供給されたデータのうちのいずれかを、コントローラ９１による制御に従って選択し、LIFO９２に出力する。
【０２７８】
図２６は、図２５のパスメモリ用RAM８２に対するパス選択情報の書き込みとパスメモリ用RAM８２からのパス選択情報の読み出しのタイミングを示すメモリアクセスチャートである。
【０２７９】
k=8であるから、シフトレジスタ８１においては毎クロック入力されるxN=2・64=128ビットのパス選択情報が８入力分蓄積され、８入力分の情報がまとめて出力される。
【０２８０】
図２６に示すように、１つのアドレスに対するパス選択情報の書き込みは、８クロック毎に行われることになる。１回の書き込みによって書き込まれるパス選択情報のビット幅はkxN=8・2・64=1024ビットとなる。
【０２８１】
図２６の例においては、８クロック目のタイミングにおいてアドレス０に対して書き込みが行われ、１６クロック目のタイミングにおいてアドレス１に対して書き込みが行われている。
【０２８２】
パスメモリ用RAM８２にT+skx=112+1・8・2=128時刻分のパス選択情報が格納された６４クロック目のタイミングの次のタイミングである６５クロック目のタイミングにおいてパス選択情報の読み出しが開始される。
【０２８３】
r=1/2であるから、２クロック毎に異なる１アドレスにアクセスしてパス選択情報の読み出しが行われる。この場合、kx=16時刻分の情報である、kxN=1024ビットのパス選択情報が２クロック毎に読み出される。
【０２８４】
読み出されたパス選択情報は、１クロックでm=8時刻分のパスを遡るトレースバック回路８３−１と８３−２のうちの、ポート１に接続されているトレースバック回路８３−１に入力される。トレースバック回路８３−１においては、T+skx=128時刻分のトレースバック処理をl=16クロック分の時間だけかけて行われる。
【０２８５】
一方、sk=8クロック毎に次のトレースバック処理を開始する必要があるので、ポート１を用いてトレースバック処理を行っている途中に開始する必要のある次のトレースバック処理は、読み出しポート２を用いてトレースバック回路８３−２によって行われる。
【０２８６】
それぞれのトレースバック回路から出力されるm=8ビットのうち、最後のs=1アドレス分のパス選択情報に対する出力が、セレクタ１２１によりsk=8クロック毎に切り替えられ、LIFO９２に入力される。LIFO９２からは、１回のトレースバック処理が行われる毎に、skx=16ビットが復号結果として出力される。
【０２８７】
図２５のパスメモリ用RAM８２は、2-writeポート2-readポートのデュアルポートRAMである。
【０２８８】
＜変形例４＞
入力信号をk入力分貯めるk段のシフトレジスタをk段のpretrace-back回路に変更するようにしてもよい。これにより、より高いクロック周波数での動作に対応することが可能となる。すなわち、上述した例においては１クロックでm/x段のN to 1セレクト処理を行う必要があるが、k段のpretrace-back回路に替えることによって１クロックで１段のN to 1セレクト処理をトレースバック回路に行わせるだけで済む。
【０２８９】
例えば上述のT=112，x=2，k=8、およびr=1の場合では、従来のpretrace-backアルゴリズムと比べてレイテンシは同じであるがメモリサイズは約10％削減可能である。従来のpretrace-backアルゴリズムが表１に示すメモリサイズを実現するにはパスメモリをデュアルポートRAMで構成する必要がある。これに対して、例えば図１６の構成においてシフトレジスタをpretrace-back回路に替えることによってパスメモリをシングルポートRAMで構成可能であり、より小さい回路規模でパスメモリを実現することが可能となる。
【０２９０】
また、実現したいクロック周波数に応じて生き残りパス処理器を設計することができ、高いクロック周波数での動作にも対応させることが可能である。
【０２９１】
本発明の実施の形態は、上述した実施の形態に限定されるものではなく、本発明の要旨を逸脱しない範囲において種々の変更が可能である。
【符号の説明】
【０２９２】
５１  受信装置，  ６１  符号検出器，  ６２  伝送路復号器，  ６３  ビタビ復号器，  ７１  ブランチメトリック計算器，  ７２  ACS処理器，  ７３  パスメトリックメモリ，  ７４  生き残りパス処理器，  ８１  シフトレジスタ，  ８２  パスメモリ用RAM，  ８３  トレースバック回路
【図１】
2010206570.tif 000033
【図２】
2010206570.tif 000034
【図３】
2010206570.tif 000035
【図４】
2010206570.tif 000036
【図５】
2010206570.tif 000037
【図６】
2010206570.tif 000038
【図７】
2010206570.tif 000039
【図８】
2010206570.tif 000040
【図９】
2010206570.tif 000041
【図１０】
2010206570.tif 000042
【図１１】
2010206570.tif 000043
【図１２】
2010206570.tif 000044
【図１３】
2010206570.tif 000045
【図１４】
2010206570.tif 000046
【図１５】
2010206570.tif 000047
【図１６】
2010206570.tif 000048
【図１７】
2010206570.tif 000049
【図１８】
2010206570.tif 000050
【図１９】
2010206570.tif 000051
【図２０】
2010206570.tif 000052
【図２１】
2010206570.tif 000053
【図２２】
2010206570.tif 000054
【図２３】
2010206570.tif 000055
【図２４】
2010206570.tif 000056
【図２５】
2010206570.tif 000057
【図２６】
2010206570.tif 000058
【手続補正書】
【提出日】平成22年2月25日(2010.2.25)
【手続補正１】
【補正対象書類名】明細書
【補正対象項目名】０１５５
【補正方法】変更
【補正の内容】
【０１５５】
RAMの種類がシングルポートRAMの場合、つまりp=1かつr≦1かつs=1の場合、yRAM=2akxNとなり、デュアルポートRAMの場合、yRAM=2.4akxNとする。また、ここでは比較的深さの浅いRAMを仮定している。これより、いまのrの値はr=2であるので、yRAM=2.4akxN=2.4・55・2・2・64=33792となる。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】０１８５
【補正方法】変更
【補正の内容】
【０１８５】
セレクタ１０２は、遅延素子１０１の出力と、ポート１を使用してパスメモリ用RAM８２から読み出したパス選択情報のうちのいずれかを選択し、トレースバック回路８３に出力する。セレクタ１０２は、例えば図１４の７２クロック目のように、トレースバック処理を開始するタイミングに読み出すアドレス２２のパス選択情報が、パスメモリ用RAM８２から出力されるタイミングでは遅延素子１０１の出力を選択し、それ以外のタイミングではパスメモリ用RAM８２から読み出したパス選択情報を選択する。パスメモリ用RAM８２のポート２から読み出されたパス選択情報は、トレースバック回路８３に直接供給される。