(57)【要約】【課題】αメトリクス及びβメトリクスの計算に要する時間を短縮することが望ましい。【解決手段】一実施形態によるターボデコーダは、データとフラグと前段の事前確率とから状態遷移確率を求める状態遷移確率計算部と、前記状態遷移確率計算部において求めた状態遷移確率からアルファメトリクス及びベータメトリクスを求めるアルファ・ベータメトリクス計算部と、前記状態遷移確率計算部において求めた状態遷移確率と、前記アルファ・ベータメトリクス計算部において求めたアルファメトリクス及びベータメトリクスとに基づき、復号データ及び次段の事前確率とを求める正規化部とを有し、前記アルファ・ベータメトリクス計算部は時系列における複数回分の処理を同時に計算する。【選択図】図１５
2009246474.tif 000002
【特許請求の範囲】
【請求項１】
データとフラグと前段の事前確率とから状態遷移確率を求める状態遷移確率計算部と、
前記状態遷移確率計算部において求めた状態遷移確率からアルファメトリック及びベータメトリックを求めるアルファ・ベータメトリック計算部と、
前記状態遷移確率計算部において求めた状態遷移確率と、前記アルファ・ベータメトリック計算部において求めたアルファメトリック及びベータメトリックとに基づき、復号データ及び次段の事前確率とを求める正規化部とを有するターボデコーダであって、
前記アルファ・ベータメトリック計算部は時系列における複数回分の処理を同時に計算するターボデコーダ。
【請求項２】
前記アルファ・ベータメトリック計算部は、
時間ｔにおける状態遷移確率を保持する保持回路と、
前記保持回路が保持している時間ｔにおける状態遷移確率と、時間ｔ＋１における状態遷移確率とを加算する加算回路とを有する、請求項１に記載のターボデコーダ。
【請求項３】
さらに、状態遷移確率の最大値の累積加算値を用いて前記アルファメトリックまたは前記ベータメトリックを圧縮する圧縮部と、
減算圧縮部により圧縮された前記アルファメトリックまたは前記ベータメトリックを記憶する記憶部とを有する、請求項１または２に記載のターボデコーダ。
【請求項４】
データとフラグと前段の事前確率とから状態遷移確率を求める状態遷移確率計算部と、
前記状態遷移確率計算部において求めた状態遷移確率からアルファメトリック及びベータメトリックを求めるアルファ・ベータメトリック計算部と、
前記状態遷移確率計算部において求めた状態遷移確率と、前記アルファ・ベータメトリック計算部において求めたアルファメトリック及びベータメトリックとに基づき、復号データ及び次段の事前確率とを求める正規化部とを有するターボデコーダであって、
さらに、状態遷移確率の最大値の累積加算値を用いて前記アルファメトリックまたは前記ベータメトリックを圧縮する圧縮部と、
減算圧縮部により圧縮された前記アルファメトリックまたは前記ベータメトリックを記憶する記憶部とを有するターボデコーダ。
【請求項５】
データとフラグと前段の事前確率とから状態遷移確率を求める状態遷移確率計算部と、
前記状態遷移確率計算部において求めた状態遷移確率からアルファメトリック及びベータメトリックを求めるアルファ・ベータメトリック計算部と、
前記状態遷移確率計算部において求めた状態遷移確率と、前記アルファ・ベータメトリック計算部において求めたアルファメトリック及びベータメトリックとに基づき、復号データ及び次段の事前確率とを求める正規化部とを有するターボデコーダであって、
さらに、状態遷移確率の最大値の累積加算値を用いて前記アルファメトリックを圧縮するアルファ圧縮部と、
前記状態遷移確率の最大値の累積加算値を用いて前記ベータメトリックを圧縮するベータ圧縮部と、
前記アルファ圧縮部により圧縮された前記アルファメトリック、または前記ベータ圧縮部により圧縮された前記ベータメトリックのいずれかを記憶する記憶部とを有し、
前記正規化部は、前記圧縮されたアルファメトリック及び前記圧縮されたベータメトリックに基づき、復号データ及び次段の事前確率とを求めるターボデコーダ。
【発明の詳細な説明】
【技術分野】
【０００１】
本件はターボ符号の復号に関し、より具体的には、アルファ及びベータ計算の高速化及びメモリ削減を行えるターボデコーダに関する。
【背景技術】
【０００２】
シャノン限界に近づく符号化方法として、ターボ符号が注目されている。ターボ符号は、送信側において二つ以上の相互に統計的に無相関の畳み込み符号器により符号化されデータを、受信側において、その無相関性を利用して、繰り返し再帰演算をすることにより誤り率を下げるという「ターボ原理」に基づいている。
【０００３】
まず、ターボ符号のエンコーダの一般的な構成を説明する。図１は、ターボエンコーダの一般的な構成を示すブロック図である。
【０００４】
図１に示したターボエンコーダ１０では、分配器１１において、送信データを偶数・奇数のデータ列Ａ、Ｂに分け、畳み込み符号器１２において、フラグビットＹ１、Ｗ１を計算して送信する。さらにバーストデータはバースト上に発生するノイズに弱いために、インターリーバー１３において、各データ列の並びを変えた後に、畳み込み符号器１４において、再びフラグビットＹ２、Ｗ２を計算して送信する。フラグビットＹ１、Ｗ１、Ｙ２、Ｗ２は必ずしもすべてを同時に送信するものではなく、その一部を送信して、受信側でエラーが生じた場合に、別の組合せで送信する等の処理が行われる。
【０００５】
畳み込み符号器１２、１４は基本的に同一のものであり、図１にはその構成を拡大して示した。
【０００６】
なお、本例ではＩＥＥＥ８０２．１６（ＷｉＭＡＸ）で規定されている符号計算を示したが、その他の通信方式（例えば、ＣＤＭＡ）であっても、符号計算式は異なるが、基本的な構成は変わらない。
【０００７】
次に、ターボデコーダにおける処理を説明するが、デコーダの構成を説明する前に、ターボ符号の復号法の１つである、トレリス状態遷移を用いた最大事後確率（ＭＡＰ）復号アルゴリズムの概要を説明する。
【０００８】
図１に示したエンコーダで生成された畳み込み方式のデータ列を復号するためには、図２に示したように、トレリスを用いて、その遷移確率を計算して、遷移毎にスコアをつけることで、遷移状態からデータ列を推測していく方法が使われている。図２は、トレリス状態遷移の一例を示す図である。
【０００９】
ターボデコーダでは、トレリス遷移の繰り返し処理により遷移確率を上げる様にしている（図３参照）。またターボデコーダでは、最大事後確率復号（ＭＡＰ復号）と称して、データを前方から遷移させていくトレリスの他に、データを後方から遷移させていくトレリスを用意している（図４参照）。前方方向からの計算がαメトリクス、後方方向からの計算がβメトリクスと呼ばれるものである。そしてこれら２つを考慮することで、より精度の高い推測を行うものである。
【００１０】
αとβの遷移は、図１に示したターボエンコーダ１００の畳み込み符号器１２、１４のレジスタＳ１、Ｓ２、Ｓ３の遷移に依存する。これらのαとβは遷移しながら、重み数を増やしていくのだが、それらの重み数がαとβ値としてその次の段の回路へ渡される。表１に、実際のαメトリクスの値の一例を示す。各列は、左からトレリス０、．．．、７に対応している。
【００１１】
【表１】
2009246474.tif 000003
これらの事を前提として、ターボデコーダの構成を説明する。図５は、ターボデコーダ単体の一般的な構成を示すブロック図である。図５に示したターボデコーダ（単体）５０は、状態遷移確率計算部５１と、λ正規化部５２と、前方方向トレリスα５３と、後方方向トレリスβ５４とを有する。
【００１２】
状態遷移確率計算部５１は、データＡ、Ｂと、フラグＹ、Ｗと、前段の事前確率Ｌｅとから、状態遷移確率γを求める。前方方向トレリスα５３と、後方方向トレリスβ５４とは、状態遷移確率計算部５１において求めた状態遷移確率γから、それぞれ、前方方向及び後方方向のトレリス計算を行う。λ正規化部５２は、状態遷移確率計算部５１で求めた状態遷移確率γと、前方方向トレリスα５３及び後方方向トレリスβ５４において行った前方方向及び後方方向のトレリス計算の結果α、βとから、復号データ及び事前確率Ｌｅとを求める。この事前確率Ｌｅは次段のターボデコーダ単体に送られる。
【００１３】
トレリスに関しては、トレリスをより確実なものにするために、復号データに対して２倍の長さを実施する。これは入力データ列をA０〜An  、B０〜Bn  、Y０〜Yn  、W０〜Wn  として求めたγをγ０〜γnとしてこれが、αとβの入力になるときに、状態は８状態存在するので、トレリスは以下の様に検索していく。ここで最初のγ０〜γn までに関してはトレリス遷移のみ精度を上げていくだけで、λ入力には使用しないようにするのである。
【００１４】
以上は、ターボデコーダ単体の説明であるが、ターボデコーダでは、バーストノイズに対する復号率を高めるためにインターリーブした符号に対しても同様な処理を行うので、ターボデコーダ全体としては、図６に示す様な構成になる。図６は、ターボデコーダ全体の一般的な構成を示すブロック図である。
【００１５】
図６に示したターボデコーダ全体６０は、入力したデータ列Ａ、Ｂと、フラグＹ１、Ｗ１との入力を受けて事前確率Ｌｅを求めるターボデコーダ（単体）６１（図５に示したターボデコーダ（単体）５０に対応するもの）を有する。ターボデコーダ（単体）６１で求めた事前確率Ｌｅは、インターリーバー６２に入力され、インターリーブされる。インターリーバー６２でインターリーブされた事前確率Ｌｅと、インターリーバー６３でインターリーブされた入力データ列Ａ′、Ｂ′とは、ターボデコーダ（単体）６４（図５に示したターボデコーダ（単体）５０に対応するもの）に入力される。ターボデコーダ６４は、これらの入力とフラグＹ２、Ｗ２との入力を受けて、事前確率Ｌｅを求める。ターボデコーダ（単体）６４が求めた事前確率は、デインターリーバー６５においてデインターリーブされて、次段のデータとして、ターボデコーダ６１に入力される。
【００１６】
デコーダ側では、前方検索と後方検索のトレリスを組み合わせて正規化したものを事前確率Ｌｅとして蓄積していく。これを元のデータ列に対して行った後に、インターリーブしたものに対して同様に行い、この結果となる事前確率Ｌｅの精度を高めていくのである。
【００１７】
ここで、αメトリクスの計算の詳細を説明する。図７は、αメトリクスの算出方法を示す図である。前段で計算されたγ（２,４）の８個の要素に対して、前回のα値を基に４種類の加算を行う。これがトレリスの候補になるのだが、全ての遷移の可能性を残すことは、メモリ容量と処理容量が莫大となるので、一回毎に最大値のみを選択して、その値を新しいα値として残すのである。例えば、α（０）の計算では、α（０）とγ（０，０）の加算、α（６）とγ（０，１）の加算、α（１）とγ（０，２）の加算、α（７）とγ（０，３）の加算を行い、その最大値のみを選択（ＭＡＸ選択）して新しいα（０）とする。
【００１８】
図８に示したように、同様に後方遷移によって求められたβ値を、α値と時系列的に加算し、前回のトレリス値より精度の高い値を求める。図８は、λの算出方法（前半）を示す図である。その値を基にもう一度遷移の可能性を計算する。
【００１９】
図９に示したように、図８で求めたλ値から８値ごとの最大値を取得し（最大値選択）、その４つの値から最大値となるλの番号（第２引数）が、デコード結果として出力される。各λｏｕｔは可能性を示し、例えばλｏｕｔ（０）は、出力が「００」である確率であり、λｏｕｔ（１）は、出力が「０１」である確率であり、λｏｕｔ（２）は、出力が「１０」である確率であり、λｏｕｔ（３）は、出力が「１１」である確率である。
【００２０】
次に、事前確率Ｌｅの計算の詳細を説明する。図１０は、Ｌｅの算出方法を示す図である。新しいＬｅは、符号の状態遷移確率（図９で求めたλｏｕｔ）から、Ａ、Ｂの要素と、前回のＬｅの値とを取り除いた値であり、フラグＹ、Ｗが示す確率値となる。例えばＬｅ（０）は答えが「００」になる確率であり、Ｌｅ（１）は答えが「０１」になる確率であり、Ｌｅ（２）は答えが「１０」になる確率であり、Ｌｅ（３）は答えが「１１」になる確率である。
【００２１】
このＬｅは、初期値が０であり、図１１に示したように、標準処理（非インターリーブ処理）とインターリーブ処理とが繰り返されるごとに更新され、ビット正当性の確率を高めていくのである。言い換えると、繰り返しごとの出力はＬｅということになる。図１１は、Ｌｅの更新のタイミングを示す図である。
【００２２】
ターボデコーダの高速化は種々検討されており、例えば、特許文献１には、α及びβメトリクス演算において、パイプライン化された複数段のγメトリクスを供給する手段を有し、該γを入力する複数段の縦続構成のＡＣＳ演算処理をするターボデコーダが記載されている。また、特許文献２には、加算器の演算結果の極性と、セレクタの選択出力の極性とにより、逆極性を含む加算結果と、逆極性を含む選択結果と、その加算結果と、ゼロとの中から１つを第２のセレクタで選択し、これら第２のセレクタの各出力を元にαメトリクスとベータメトリクスとを演算するターボデコーダが記載されている。さらに、トレリスプロセッサの適切なパスメトリクスアドレス化を計算する装置が特許文献３等に記載されている。
【特許文献１】特開２００１−３２０２８２号公報
【特許文献２】特開２００１−２４５２１号公報
【特許文献３】特開２００２−１５２０５７号公報
【発明の開示】
【発明が解決しようとする課題】
【００２３】
図７に示したように、αメトリクスは、１回前に求めたのαメトリクスの値をフィードバックして計算するので、計算の高速化の点でボトルネックになる。βメトリクスの計算でも同じ問題が生じる。すなわち、時系列ｎのデータは、時系列ｎ−１を計算してからでないと始められないので、一回あたりの計算に要する時間をｔとし、データ数をｎとすると、ｔ×ｎ時間が必然的に必要になる。例えば、現在市販されているデバイスの速度と、必要なビット数として１８ビットを仮定すると、１回のαメトリクス及びβメトリクスの計算に要する時間として、３クロック（加算、４：１選択、２：１選択）が必要になる。この時間をさらに短縮することが望ましい。
【００２４】
また、計算されるαメトリクスとβメトリクスの値は時系列的に逆向きであるため、図１２に示したように、βメトリクスを先に計算して降順にメモリに格納してから、格納したβメトリクスを昇順（時系列的に反対向き）に読み出しつつ、αメトリクスを昇順に計算してλ計算を行わなければならない。そこで、αメトリクスとβメトリクスの時系列的な順序を合わせるために、βメトリクスを格納するメモリが必要になる。
【００２５】
例えば、ＷｉＭＡＸでは、データサイズは可変であり、最大データサイズは２４００ワードとなり、１ワードあたり１８ｂｉｔで８ステート分が必要になるので、βメトリクスを格納するメモリのサイズは２４００×１８ｂｉｔ×８＝３４５，６００ｂｉｔとなる。集積回路を設計する場合、βメトリクスの格納のためにこのように大きなメモリ領域を確保することは現状困難であり、できるだけ削減する必要がある。
【課題を解決するための手段】
【００２６】
上記の少なくとも１つの課題を解決するために、一実施形態によるターボデコーダは、データとフラグと前段の事前確率とから状態遷移確率を求める状態遷移確率計算部と、前記状態遷移確率計算部において求めた状態遷移確率からアルファメトリクス及びベータメトリクスを求めるアルファ・ベータメトリクス計算部と、前記状態遷移確率計算部において求めた状態遷移確率と、前記アルファ・ベータメトリクス計算部において求めたアルファメトリクス及びベータメトリクスとに基づき、復号データ及び次段の事前確率とを求める正規化部とを有し、前記アルファ・ベータメトリクス計算部は時系列における複数回分の処理を同時に計算する。
【００２７】
他の実施形態によるターボデコーダは、データとフラグと前段の事前確率とから状態遷移確率を求める状態遷移確率計算部と、前記状態遷移確率計算部において求めた状態遷移確率からアルファメトリクス及びベータメトリクスを求めるアルファ・ベータメトリクス計算部と、前記状態遷移確率計算部において求めた状態遷移確率と、前記アルファ・ベータメトリクス計算部において求めたアルファメトリクス及びベータメトリクスとに基づき、復号データ及び次段の事前確率とを求める正規化部とを有し、さらに、状態遷移確率の最大値の累積加算値を用いて前記アルファメトリクスまたは前記ベータメトリクスを圧縮する圧縮部と、減算圧縮部により圧縮された前記アルファメトリクスまたは前記ベータメトリクスを記憶する記憶部とを有する。
【発明の効果】
【００２８】
アルファ・ベータメトリクス計算部は時系列における複数回分の処理を同時に計算することにより、アルファメトリクスまたはベータメトリクスの計算時間を短縮することができる。また、状態遷移確率の最大値の累積加算値を用いて前記アルファメトリクスまたは前記ベータメトリクスを圧縮する圧縮部と、減算圧縮部により圧縮された前記アルファメトリクスまたは前記ベータメトリクスを記憶する記憶部とを有することにより、記憶部の記憶容量を縮小することができる。
【発明を実施するための最良の形態】
【００２９】
以下、図面を参照して本実施形態を詳細に説明する。図面を参照して以下に説明する実施形態は例示であり、本発明を限定するものではない。図面を通して、同じ構成要素には同じ参照符号を付した。
αメトリクス及びβメトリクスの計算時間の短縮化
まずαメトリクス及び／またはβメトリクスの計算において、時系列の２回分の処理を一度に行うことにより、計算時間を短縮することができる。図１３は、αメトリクスの計算において２回分の処理を一度に実施する方法を説明するための図である。
【００３０】
以下、α（０）に着目して説明する。α（０）以外のαメトリクスについても同様であることは、当業者には明らかである。図１３には、時系列ｎにおけるα（０）、α（６）、α（１）、α（７）の計算と、時系列ｎ＋１におけるα（０）の計算とが示されている。
【００３１】
時系列ｎのα（０）は、時系列ｎ−１のα（０）とγ（０，０）を加算し、時系列ｎ−１のα（６）とγ（０，１）を加算し、時系列ｎ−１のα（１）とγ（０，２）を加算し、時系列ｎ−１のα（７）とγ（０，３）を加算し、これらの加算結果から最大値を選択（ＭＡＸ選択）することにより求められる。時系列ｎにおけるα（６）、α（１）、α（７）も同様である。
【００３２】
時系列ｎ＋１のα（０）は、時系列ｎのα（０）とγ（０，０）を加算し、時系列ｎのα（６）とγ（０，１）を加算し、時系列ｎのα（１）とγ（０，２）を加算し、時系列ｎのα（７）とγ（０，３）を加算し、これらの加算結果から最大値を選択（ＭＡＸ選択）することにより求められる。このように、２回分の処理により、時系列ｎ−１のαメトリクスと状態遷移確率γとから時系列ｎ＋１のαメトリクスが求められる。
【００３３】
これを並び替えると、図１４に示す通りになる。図１４は、図１３に示した構成を並び替えた図である。図１３に示した構成と図１４に示した構成とは等価である。図１４は、時系列ｎ−１のαメトリクス及び状態遷移確率γと、時系列ｎの状態遷移確率γとから時系列ｎ＋１のαメトリクス（図１４ではα（０））が求められる。
【００３４】
これをさらに並び替えると、図１５に示す通りになる。図１５は、図１４に示した構成をさらに並び替えた図である。図１４では、例えば、時系列ｎ−１のα（０）とγ（０，０）とを加算してから、その加算結果に時系列ｎのγ（０，０）を加算しているが、図１５では、時系列ｎ−１のα（０）に、時系列ｎ−１のγ（０，０）と時系列ｎのγ（０，０）の加算結果を加算している点が異なるが、構成としては等価である。
【００３５】
図１５の計算に要するクロック数はαとγの加算に１クロックが必要であり、１６：１の最大値選択に４クロックが必要であり、合計５クロックとなる。従来の方法では、１回の処理をするのに３クロックが必要であったから、２回の処理をするには３×２＝６クロックが必要である。従って、２回分の処理を一度に実施することにより、１クロックを節約することができる。
【００３６】
図１５を表にまとめると、次のようになる。
【００３７】
【表２】
2009246474.tif 000004
時系列ｎ＋１のα（０）を求めるためには、表２の各行の要素を加算して、その結果の最大値を選択すればよい。
【００３８】
α（１）乃至α（７）についても同様であるが、参考のため、各場合について加算すべき要素を表にまとめると次の通りである。
【００３９】
【表３】
2009246474.tif 000005
【００４０】
【表４】
2009246474.tif 000006
【００４１】
【表５】
2009246474.tif 000007
【００４２】
【表６】
2009246474.tif 000008
【００４３】
【表７】
2009246474.tif 000009
【００４４】
【表８】
2009246474.tif 000010
【００４５】
【表９】
2009246474.tif 000011
以上から、入力されるγ加算はα（０）、α（３）で共通、α（４）、α（７）で共通、α（１）、α（２）で共通、α（５）、α（６）で共通であり、それぞれ１６通りなので、１６×４＝６４通りを計算すればよいことに留意すべきである。
【００４６】
図１５に示して説明したαメトリクスの計算は、図１６のような回路構成で実現することができる。図１６は、一実施形態による、αメトリクスの２回分の処理を一度に実施する回路構成を示すブロック図である。
【００４７】
図１６に示した回路構成１６０は、状態遷移確率計算部５１と、保持回路１６２と、加算回路１６３と、αβ算出部１６４Ａ乃至１６４Ｄとを含む。状態遷移確率計算部５１は、図５に示した状態遷移確率計算部５１である。図１５に示した構成と比較すると分かるように、保持回路１６２は、時系列ｎ−１において状態遷移確率計算部５１が求めた状態遷移確率γ（０，０）乃至γ（１，３）を保持しておき、保持した値を時系列ｎ＋１のαメトリクスの計算の再に加算回路１６３に渡す。また、状態遷移確率計算部５１は、時系列ｎにおいて求めた状態遷移確率γ（０，０）乃至γ（１，３）を、直接、加算回路１６３に渡す。加算回路１６３は、時系列ｎ−１のγと時系列ｎのγとを加算し、加算結果をαβ算出部１６４Ａ乃至１６４Ｄに渡す。αβ算出部１６４Ａ乃至１６４Ｄは、加算回路１６３から受け取ったγの加算値（例えば、α（０）及びα（３）の計算の場合、γ（０，ｎ）＋γ（０，０）、γ（１，ｎ）＋γ（０，１）、γ（１，ｎ）＋γ（０，２）、γ（０，ｎ）＋γ（０，３）の値、ただしｎ＝０〜４）と、時系列ｎ−１のαメトリクス（図示せず）とを加算して、最大値を求めて、時系列ｎ＋１のαメトリクスを求める。αβ算出部１６４Ａ乃至１６４Ｄは、求めた時系列ｎ＋１のαメトリクスを、λ正規化部（図５参照）に送る。
【００４８】
以上説明したように、α値の計算のクロック数を短縮することにより、ターボ符号の復号処理に要する時間を削減することができる。
【００４９】
なお、以上の説明では、αメトリクスの計算について計算時間の短縮化を例にして説明したが、βメトリクスの計算についても同様の方法を適用できるということは当業者には明らかである。このことをふまえて、図１６では、αメトリクスを算出する要素１６４Ａ乃至１６４Ｄを、αβ算出部と呼んだ。
【００５０】
また、αメトリクスの計算について、２回分の処理を一度に行うことを前提として説明したが、回路構成はより複雑になるが、３回分以上の処理を一度に行い、より大きな時間短縮効果を得ることも可能である。
【００５１】
なお、半導体集積回路の設計においては、αメトリクスの計算時間を短縮化できなければ、αメトリクスの計算をするモジュールが余分に必要となるところを、計算時間の短縮化により、その余分なモジュールが必要なくなり、その余分なモジュールを形成したであろう領域を他の用途に使用できるという効果も奏する。
βメモリの縮小
図１２を参照して説明したように、ターボデコーダでは、βメトリクスの降順の計算を先に行い、その結果をメモリに格納し、αメトリクスの昇順の計算を行うのと同時にβメトリクスを昇順にメモリから読み出すことにより、同一時系列のαメトリクスとβメトリクスを加算することを実現している。
【００５２】
ところで、βメトリクスの意味を考えてみると、βメトリクスの８ステートともに、γの示す最大値に収束するような計算が行われている。これは言い換えると、すべてのステートにおいて、トレリスの遷移が繰り返されるたびに、最大値のみが残されて蓄積されていくことを意味する。つまり、βメトリクスは、γ最大値の累積加算値を基準にした場合に、その値に近づこうとするということである。この洞察に基づき、シミュレーションした結果、βメトリクス（β値）と［γ最大値の累積加算値-βメトリクス］を求めてみると、１００万回のランダムトライアルで、βメトリクスの最大値が５５３，７９６であるのに対し、［γ最大値の累積加算値-βメトリクス］は２，２５８となった。もちろんこれらの値は入力ビット数と繰り返し回数とに依存するが、少なくとも前者が２０ビットの数値であるのに対して、後者が１２ビットの数値である。これはメモリの節約の観点から注目すべき点である。
【００５３】
また、例えば時系列の各時点の最大値を基準にする場合は、その最大値を時間分記録する必要があるが、これに対して、γの累積加算値は以下に説明するように、メモリに記録することなく即時計算できるのである。したがって、２０ビット必要であったメモリが１２ビットで済むことになる。
【００５４】
一実施形態によるβメトリクス用メモリとその周辺回路を説明するために、まず従来のβメトリクス用メモリとその周辺回路を示す。図１７は、従来のβメトリクス用メモリとその周辺回路を含むターボデコーダ単体を示す図である。図１７に示したターボデコーダ１７００は、入力されたデータＡ、ＢとフラグＷ、Ｙとを記憶するメモリ１７１０と、事前確率Ｌｅを記憶するメモリ１７２０と、メモリ１７１０、１７２０に記憶されたデータに基づき状態遷移確率γを計算する状態遷移確率計算部１７３０と、状態遷移確率計算部１７３０が求めた状態遷移確率等に基づきαメトリクス及びβメトリクスを計算するα／β回路１７４０と、α／β回路１７４０が求めた降順のβメトリクスを記憶して昇順に読み出させるための２０ビットβメモリ１７５０と、λ正規化部１７６０とを有する。λ正規化部１７６０は、状態遷移確率１７３０が求めた状態遷移確率γと、α／β回路１７４０が求めたαメトリクスと、βメモリに記憶され昇順に読み出されたβメトリクスとにより、復号データと、事前確率Ｌｅとを求める。λ正規化部１７６０が求めた事前確率Ｌｅは、Ｌｅ用メモリ１７２０に記憶される。ターボデコーダ１７００は、さらに、αβ切り替え制御回路１７７０を有する。このαβ切り替え制御回路１７７０は、α／β回路１７４０に制御信号を送り、α／β回路１７４０におけるαメトリクスの計算とβメトリクスの計算を切り替える。また、αβ切り替え制御回路１７７０は、βメモリ１７５０に書き込みアドレスを送り、α／β回路１７４０で降順に計算されたβメトリクスをβメモリ１７５０に記憶させる。また、αβ切り替え制御回路１７７０は、βメモリ１７５０に読み出しアドレスを送り、βメモリ１７５０に記憶されたβメトリクスを昇順に読み出させて、λ正規化部に送らせる。
【００５５】
次に、一実施形態によるβメトリクス用メモリとその周辺回路を含むターボデコーダ単体を説明する。図１８は、一実施形態によるβメトリクス用メモリとその周辺回路を含むターボデコーダ単体を示すブロック図である。図１８に示したターボデコーダ１８００は、入力されたデータＡ、ＢとフラグＷ、Ｙとを記憶するメモリ１８１０と、事前確率Ｌｅを記憶するメモリ１８２０と、メモリ１８１０、１８２０に記憶されたデータに基づき状態遷移確率γを計算する状態遷移確率計算部１８３０と、状態遷移確率計算部１８３０が求めた状態遷移確率等に基づきαメトリクス及びβメトリクスを計算するα／β回路１８４０とを有する。ターボデコーダ１８００は、さらに、状態遷移確率計算部１８３０が求めたγの値の最大値を求めるγ最大値部１８８１と、その最大値を累積加算する累積加算部１８８２と、その累積加算値から、α／β回路１８４０が求めたβ値を引く減算β圧縮部１８８３とを有する。この構成により、一実施形態によるターボデコーダ単体１８００は、［γ最大値の累積加算値-βメトリクス］の値を求め、その結果を１２ビットのβメモリ１８５０に記憶するのである。図１７に示した従来のターボデコーダ１７００のβメモリ１７５０が２０ビット幅であるのと比較して、図１８に示した一実施形態によるターボデコーダ１８００のβメモリ１８５０は１２ビット幅とすることができ、メモリ形成に要する領域を節約することができる。
【００５６】
しかし、λ正規化部１８６０に入力するのはβ値である。そこで、βメモリ１８５０に記憶されている［γ最大値の累積加算値-βメトリクス］に、γ最大値部１８８１で求めたγの最大値を累積減算部１８８５で累積減算した結果を加えて、加算β復元部１８８４において、βメトリクスを復元する必要がある。加算β復元部１８８４は、復元した２０ビットのβ値をλ正規化部１８６０に送る。λ正規化部１８６０は、状態遷移確率計算部１８３０が求めた状態遷移確率γと、α／β回路１８４０が求めたαメトリクスと、加算β復元部１８８４で復元されたβメトリクスとにより、復号データと、事前確率Ｌｅとを求める。λ正規化部１８６０が求めた事前確率Ｌｅは、Ｌｅ用メモリ１８２０に記憶される。ターボデコーダ１８００は、さらに、αβ切り替え制御回路１８７０を有する。このαβ切り替え制御回路１８７０は、α／β回路１８４０に制御信号を送り、α／β回路１８４０におけるαメトリクスの計算とβメトリクスの計算を切り替える。また、αβ切り替え制御回路１８７０は、１２ビットのβメモリ１８５０に書き込みアドレスを送り、減算β圧縮部１８８３で圧縮した結果（［γ最大値の累積加算値-βメトリクス］）をβメモリ１８５０に記憶させる。また、αβ切り替え制御回路１８７０は、βメモリ１８５０に読み出しアドレスを送り、加算β復元部１８８４で復元されたβメトリクスをλ正規化部に送らせる。
【００５７】
β計算の場合、累積加算部１８８２は、データ数をｎとすると、データ番号ｎ−１から０までのγ最大値の累積加算を有している。β計算終了後、α計算開始時に、データ番号０番からのβ値が必要となるので、例えばデータ番号０番の場合は累積加算最終値、１番の場合は累積加算最終値から０番のγ最大値を減算したもの、２番の場合はさらにそこから１番のγ最大値を減算したもの、以下同様、というように累積減算部１８８５で累積減算していけば、各ｎについて累積加算値を記憶しなくても、β値を復元できるのである。
【００５８】
以上説明したように、一実施形態によるターボデコーダでは、ターボ符号の復号処理に必要とするメモリ量（βメモリ）を削減することができる。
αメモリの縮小
以上では、βメトリクスの降順計算を先に計算してその結果をメモリに格納して、αメトリクスの計算時に昇順に読み出すことを前提とした。ターボデコーダでは、図１９に示したように、αメトリクスの昇順計算を先に計算してその結果をメモリに格納して、βメトリクスの計算時に降順に読み出してもよい。これにより、同一時間のαメトリクスとβメトリクスを加算することができる。
【００５９】
この場合でもα値は、γの示す最大値に収束するような計算が行われている。これは言い換えると、すべてのステートにおいて、トレリス遷移の繰り返しのたびに、最大値のみが残されて蓄積されていくということである。
【００６０】
シミュレーションした結果、αメトリクス（α値）と［γ最大値の累積加算値-αメトリクス］、を求めてみると、１００万回のランダムトライアルで、α値の最大値が５５３，７９６に対して２，２５８となった。これらの値は入力ビット数と繰り返し回数に依存するのだが、少なくとも前者が２０ビットの数値であるのに対して、後者は１２ビットの数値である。これもメモリの節約の観点から注目すべき点である。
【００６１】
また、例えば各時間の最大値を基準にした場合は、結局その最大値を時間分記録する必要があるのに対して、γの累積加算値は以下に説明するように、メモリに記録することなく即時計算できるのである。したがって、２０ビット必要であったメモリが１２ビットで済むことになる。
【００６２】
一実施形態によるαメトリクス用メモリとその周辺回路を説明するために、まず従来のαメトリクス用メモリとその周辺回路を示す。図２０は、従来のαメトリクス用メモリとその周辺回路を含むターボデコーダ単体を示す図である。図２０に示したターボデコーダ２０００は、入力されたデータＡ、ＢとフラグＷ、Ｙとを記憶するメモリ２０１０と、事前確率Ｌｅを記憶するメモリ２０２０と、メモリ２０１０、２０２０に記憶されたデータに基づき状態遷移確率γを計算する状態遷移確率計算部２０３０と、状態遷移確率計算部２０３０が求めた状態遷移確率等に基づきαメトリクス及びβメトリクスを計算するα／β回路２０４０と、α／β回路２０４０が求めた昇順のαメトリクスを記憶して降順に読み出させるための２０ビットαメモリ２０５０と、λ正規化部２０６０とを有する。λ正規化部２０６０は、状態遷移確率２０３０が求めた状態遷移確率γと、α／β回路２０４０が求めたβメトリクスと、αメモリに記憶され降順に読み出されたαメトリクスとにより、復号データと、事前確率Ｌｅとを求める。λ正規化部２０６０が求めた事前確率Ｌｅは、Ｌｅ用メモリ２０２０に記憶される。ターボデコーダ２０００は、さらに、αβ切り替え制御回路２０７０を有する。このαβ切り替え制御回路２０７０は、α／β回路２０４０に制御信号を送り、α／β回路２０４０におけるαメトリクスの計算とβメトリクスの計算を切り替える。また、αβ切り替え制御回路２０７０は、αメモリ２０５０に書き込みアドレスを送り、α／β回路２０４０で昇順に計算されたαメトリクスをαメモリ２０５０に記憶させる。また、αβ切り替え制御回路２０７０は、αメモリ２０５０に読み出しアドレスを送り、αメモリ２０５０に記憶されたαメトリクスを降順に読み出させて、λ正規化部２０６０に送らせる。
【００６３】
次に、一実施形態によるαメトリクス用メモリとその周辺回路を含むターボデコーダ単体を説明する。図２１は、一実施形態によるαメトリクス用メモリとその周辺回路を含むターボデコーダ単体を示すブロック図である。図２１に示したターボデコーダ２１００は、入力されたデータＡ、ＢとフラグＷ、Ｙとを記憶するメモリ２１１０と、事前確率Ｌｅを記憶するメモリ２１２０と、メモリ２１１０、２１２０に記憶されたデータに基づき状態遷移確率γを計算する状態遷移確率計算部２１３０と、状態遷移確率計算部２１３０が求めた状態遷移確率等に基づきαメトリクス及びβメトリクスを計算するα／β回路２１４０とを有する。ターボデコーダ２１００は、さらに、状態遷移確率計算部２１３０が求めたγの値の最大値を求めるγ最大値部２１８１と、その最大値を累積加算する累積加算部２１８２と、その累積加算値から、α／β回路２１４０が求めたα値を引く減算α圧縮部２１８３とを有する。この構成により、一実施形態によるターボデコーダ単体２１００は、［γ最大値の累積加算値-αメトリクス］の値を求め、その結果を１２ビットのαメモリ２１５０に記憶するのである。図２０に示した従来のターボデコーダ２０００のαメモリ２０５０が２０ビット幅であるのと比較して、図２１に示した一実施形態によるターボデコーダ２１００のαメモリ２１５０は１２ビット幅とすることができ、メモリ形成に要するチップ領域を節約することができる。
【００６４】
しかし、λ正規化部２１６０に入力するのはα値である。そこで、αメモリ２１５０に記憶されている［γ最大値の累積加算値-αメトリクス］に、γ最大値部１８８１で求めたγの最大値を累積減算部２１８５で累積減算した結果を加えて、加算α復元部２１８４において、αメトリクスを復元する必要がある。加算α復元部２１８４は、復元した２０ビットのα値をλ正規化部２１６０に送る。λ正規化部２１６０は、状態遷移確率計算部２１３０が求めた状態遷移確率γと、α／β回路２１４０が求めたβメトリクスと、加算α復元部２１８４で復元されたαメトリクスとにより、復号データと、事前確率Ｌｅとを求める。λ正規化部２１６０が求めた事前確率Ｌｅは、Ｌｅ用メモリ２１２０に記憶される。ターボデコーダ２１００は、さらに、αβ切り替え制御回路２１７０を有する。このαβ切り替え制御回路２１７０は、α／β回路２１４０に制御信号を送り、α／β回路２１４０におけるαメトリクスの計算とβメトリクスの計算を切り替える。また、αβ切り替え制御回路２１７０は、１２ビットのαメモリ２１５０に書き込みアドレスを送り、減算α圧縮部２１８３で圧縮した結果（［γ最大値の累積加算値-αメトリクス］）をαメモリ２１５０に記憶させる。また、αβ切り替え制御回路２１７０は、αメモリ２１５０に読み出しアドレスを送り、加算α復元部２１８４で復元されたαメトリクスをλ正規化部に送らせる。
【００６５】
α計算の場合、累積加算部２１８２は、データ数をｎとすると、データ番号ｎ−１から０までのγ最大値の累積加算を有している。α計算終了後、β計算開始時に、データ番号ｎ−１番からのα値が必要となるので、例えばｎ−１番の場合は累積加算最終値、ｎ−２番の場合は累積加算最終値からｎ−１番のγ最大値を減算したもの、ｎ−２番の場合はさらにそこからｎ−２番のγ最大値を減算したもの、以下同様、というように累積減算部２１８５で累積減算していけば、累積加算値を記憶しなくても、α値を復元できるのである。
【００６６】
以上説明したように、一実施形態によるターボデコーダでは、ターボ符号の復号処理に必要とするメモリ量（αメモリ）を削減することができる。
αβを加算復元しない方法
以上、β値（またはα値）を減算圧縮してメモリに格納し、λ正規化部に渡す時に加算復元する方法について説明したが、α値とβ値を共に減算圧縮して、加算復元せずにλ正規化部に渡すこともできる。この場合、最初にλの最大値選択を実施して、事前確率Ｌｅを計算するときに、累積値を加算してもよい。
【００６７】
これは、図８及び図９から分かるように、λは、α値とβ値を加算してから最大値選択されるのだが、最大値を選択するだけなので、α値及びβ値からともに定数値を減算しても同じ結果になることによる。ただし、Ｌｅは、その値自体が意味をもち、求める必要があるので、最大値選択された後にそのλｏｕｔにその定数値を加算する処理をすればよい。
【００６８】
これは図２２に示す回路構成で実施可能である。図２２は、一実施形態によるαβ圧縮とβ用メモリとその周辺回路を示すブロック図である。
【００６９】
図２２に示した、一実施形態によるαβ圧縮とβ用メモリとその周辺回路を含むターボデコーダ単体２２００は、入力されたデータＡ、ＢとフラグＷ、Ｙとを記憶するメモリ２２１０と、事前確率Ｌｅを記憶するメモリ２２２０と、メモリ２２１０、２２２０に記憶されたデータに基づき状態遷移確率γを計算する状態遷移確率計算部２２３０と、状態遷移確率計算部２２３０が求めた状態遷移確率等に基づきαメトリクス及びβメトリクスを計算するα／β回路２２４０とを有する。ターボデコーダ２２００は、さらに、状態遷移確率計算部２２３０が求めたγの値の最大値を求めるγ最大値部２２８１と、その最大値を累積加算するβ累積加算部２２８２と、その累積加算値から、α／β回路１８４０が求めたβ値を引く減算β圧縮部２２８３とを有する。この構成により、一実施形態によるターボデコーダ単体２２００は、［γ最大値の累積加算値-βメトリクス］の値を求め、その結果を１２ビットのβメモリ２２５０に記憶するのである。図２２に示した一実施形態によるターボデコーダ２２００のβメモリ２２５０は１２ビット幅とすることができ、メモリ形成に要する領域を節約することができる。βメモリに格納された［γ最大値の累積加算値-βメトリクス］の値は、λ正規化部２２６０に送られる。
【００７０】
さらに、ターボデコーダ２２００は、γ最大値部２２８１が求めたγの最大値を累積加算するα累積加算部２２９２と、その累積加算値から、α／β回路２２４０が求めたα値を引く減算α圧縮部２２９３とを有する。この構成により、一実施形態によるターボデコーダ単体２２００は、［γ最大値の累積加算値-αメトリクス］の値を求め、λ正規化部２２６０に送る。
【００７１】
ここで、留意すべき点として、図２２ではα累積加算部２２９２とβ累積加算部２２８２は別々のブロックとして示したが、α計算とβ計算は同時に行う必要はないので、実際には同一の回路を時分割して使用することができる。この時分割は、αβ切り替え制御回路２２７０からの制御信号（αβ切り替え）に基づき行われる。同様に、図２２では減算α圧縮部２２９３と減算β圧縮部２２８３は別々のブロックとして示したが、実際には同一の回路を時分割して使用することができる。この時分割は、αβ切り替え制御回路２２７０からの制御信号（図示せず）に基づき行われる。
【００７２】
また、αβ切り替え制御回路２２７０は、α／β回路１８４０に制御信号を送り、α／β回路１８４０におけるαメトリクスの計算とβメトリクスの計算を切り替える。αβ切り替え制御回路２２７０は、さらに、βメモリ２２５０に書き込みアドレスと読み出しアドレスを送り、減算β圧縮２２８３からのデータの書き込みと、βメモリ２２５０からのデータの読み出しを制御する。
【００７３】
図２３は、一実施形態による、αβ圧縮をした場合の事前確率Ｌｅを求める演算回路を説明するための図である。図２３の演算回路２３００は、図２２のλ正規化部２２６０の一部である。例えば、新しいＬｅ（０）を求める場合を考える。新しいＬｅ（０）は、符号の状態遷移確率λ（０，０）〜λ（７，０）から最大値（λｏｕｔ（０））を選択（最大値選択部２３１０）して、Ａ、Ｂの要素（Ｌｅ（０）の場合Ａ＋Ｂ）と、前回のＬｅ（０）の値とを取り除いた値である（減算回路２３２０）。ここまでは、図１０に示した事前確率Ｌｅを求める演算回路と同様である。しかし、図２２には加算β復元部１８８４（図１８）と加算α復元部２１８４（図２１）がない。つまり、λｏｕｔ（０）の値からは、αの累積加算値とβの累積減算値とが抜けている。そこで、この減算回路２３２０の入力として、α累積加算部２２９２（図２２）からα累積加算値と、β累積減算部２２８５（図２２）からβ累積減算値を入力する必要がある。
【００７４】
以上説明したように、一実施形態によるターボデコーダでは、圧縮したα値及び／またはβ値を加算復元しないことにより、λ演算回路の入力ビット数を減らすことができ、加算回路と最大値選択回路のビット数を減らすことができ、動作の高速化と回路規模の縮小とが可能になる。
【００７５】
以下、より具体的な実施例を説明する。
［実施例１］
実施例１は、ＩＥＥＥ８０２．１６（ＷｉＭＡＸ）での使用を想定して、αβ計算の２回分の計算時間を６から５クロックへ縮小し、さらにβメモリを縮小したターボデコーダである。図２４は、実施例１のターボデコーダを示すブロック図である。
【００７６】
受信データとして、Ｂ、Ａ、Ｙ１、Ｙ２を受信する。受信データＢ、Ａ、Ｙ１、Ｙ２は、通常はデグループ、デサブブロックされたものが入力される。書き込み制御部２４０１は、受信データを書き込むための制御信号（アドレス及び書き込みイネーブル信号）を発生する。これらの受信データは受信データ格納メモリ２４０２に格納される。図２５に示したように、受信データの入力が完了すると、書き込み制御部２４０１から読み出し制御部２４０３に対して書き込み完了がアサートされ、読み出し制御がスタートする。
【００７７】
読み出し制御部２４０３は、読み出しアドレスを生成する。読み出しは、図２６に示したように、最初にβ計算のためのデータを出力するために、降順に（アドレス４７から００への順序で）出力し、さらにその後でα計算のためのデータを昇順に（アドレス００から４７への順序で）を出力する。また、その処理がノーマル（インターリーブしていない標準処理）かインターリーブかどうかで、アドレスのインターリーブ変換が行われる。インターリーブはデータサイズによって切り替わり、例えばデータサイズ４８ビットの場合には、図２７に示したインターリーブ変換表に基づき変換される。インターリーブかどうかの切り替えは、何回目の処理であるかで決められる。何回目の処理であるかはiterationで定義される回数で決定される。例えば、iteration＝３の場合は、図２８に示したように、合計６回の処理が繰り返される。
【００７８】
γ計算部２４０４は、エンコーダの構成から決定される計算である。ＷｉＭＡＸではＨＡＲＱを使用しない場合はＷ１、Ｗ２を使用しないので、γ計算は実質的にＡ、Ｂ、Ｙ１、Ｙ２とＬｅで決定される。Ｙ１とＹ２は標準処理かインターリーブ処理かで切り替えられ、標準処理時はＹ１、インターリーブ処理時はＹ２が選択される。γ計算部２４０４は、図２９に示したγ計算対応表に示したようにγを計算し、２Ｘ４の配列としてγを出力する。
【００７９】
γ最大値取得部２４０５は、γ計算部２４０４が出力したγの最大値を計算する。
【００８０】
α／β回路２４０６は、αメトリクスとβメトリクスを計算する回路である。図３０にその詳細を示した。図３０に示したα／β回路は、α１回分回路３０１０と、α２回分回路３０１１と、β１回分回路３０１２と、β２回分回路３０１３とを有する。これらの計算は、下に示す表の組み合わせの加算値から最大値を選択する。これらの回路からの処理結果は、セレクタ３０２０、３０２１、３０３０により、図３１のαβ切り替え処理タイムチャートに示したように、時間軸多重されて出力される。αまたはβの２回分処理は、αまたはβの２回分処理回路３０１１、３０１３により、５クロックで行われる。これと平行して、αまたはβの１回分処理が、αまたはβ１回分処理回路３０１０、３０１２により、３クロックで行われる。そして、セレクタにより、１回分処理の結果と２回分処理の結果とを選択的に出力する。
【００８１】
なお、α処理に関しては、１回分の処理としては、次を計算すればよい。
α(0)=
MAX(α(0)+γ(0,0) , α(6)+γ(0,1) , α(1)+γ(0,2) , α(7)+γ(0,3) )
α(1)=
MAX(α(2)+γ(1,0) , α(4)+γ(1,1) , α(3)+γ(1,2) , α(5)+γ(1,3) )
α(2)=
MAX(α(5)+γ(1,0) , α(3)+γ(1,1) , α(4)+γ(1,2) , α(2)+γ(1,3) )
α(3)=
MAX(α(7)+γ(0,0) , α(1)+γ(0,1) , α(6)+γ(0,2) , α(0)+γ(0,3) )
α(4)=
MAX(α(1)+γ(0,0) , α(7)+γ(0,1) , α(0)+γ(0,2) , α(6)+γ(0,3) )
α(5)=
MAX(α(3)+γ(1,0) , α(5)+γ(1,1) , α(2)+γ(1,2) , α(4)+γ(1,3) )
α(6)=
MAX(α(4)+γ(1,0) , α(2)+γ(1,1) , α(5)+γ(1,2) , α(3)+γ(1,3) )
α(7)=
MAX(α(6)+γ(0,0) , α(0)+γ(0,1) , α(7)+γ(0,2) , α(1)+γ(0,3) )
また、αメトリクスの２回分の処理としては、表２乃至表９を参照して上で説明した入力要素を全て加算した後で、最大値を選択することになる。
【００８２】
また、β処理に関しては1回分の処理としては、次を計算すればよい。
β(0)=
MAX(β(0)+γ(0,0) , β(7)+γ(0,1) , β(4)+γ(0,2) , β(3)+γ(0,3) )
β(1)=
MAX(β(4)+γ(0,0) , β(3)+γ(0,1) , β(0)+γ(0,2) , β(7)+γ(0,3) )
β(2)=
MAX(β(1)+γ(1,0) , β(6)+γ(1,1) , β(5)+γ(1,2) , β(2)+γ(1,3) )
β(3)=
MAX(β(5)+γ(1,0) , β(2)+γ(1,1) , β(1)+γ(1,2) , β(6)+γ(1,3) )
β(4)=
MAX(β(6)+γ(1,0) , β(1)+γ(1,1) , β(2)+γ(1,2) , β(5)+γ(1,3) )
β(5)=
MAX(β(2)+γ(1,0) , β(5)+γ(1,1) , β(6)+γ(1,2) , β(1)+γ(1,3) )
β(6)=
MAX(β(7)+γ(0,0) , β(0)+γ(0,1) , β(3)+γ(0,2) , β(4)+γ(0,3) )
β(7)=
MAX(β(3)+γ(0,0) , β(4)+γ(0,1) , β(7)+γ(0,2) , β(0)+γ(0,3) )
また、βメトリクスの２回分の処理としては、下表の入力要素を全て加算した後で、最大値を選択することになる。
【００８３】
【表１０】
2009246474.tif 000012
【００８４】
【表１１】
2009246474.tif 000013
【００８５】
【表１２】
2009246474.tif 000014
【００８６】
【表１３】
2009246474.tif 000015
【００８７】
【表１４】
2009246474.tif 000016
【００８８】
【表１５】
2009246474.tif 000017
【００８９】
【表１６】
2009246474.tif 000018
【００９０】
【表１７】
2009246474.tif 000019
図２４に戻り、累積加算部２４０７は、γ最大値取得部２４０５が求めたγの最大値を時間軸に合わせて累積加算する回路である。減算β圧縮部２４０８は、β演算の時のみ有効にされ、累積加算部２４０７からの累積加算値から、βの値を減算する回路である。βメモリ２４０９は、減算β圧縮部２４０８で求めた結果を記憶するためのメモリであり、そのサイズは１２ビットに縮小されている。
【００９１】
累積減算部２４１０は、加算β復元２４１１の復元時に利用する累積加算値を算出するために、累積加算部２４０７の最終値から減算していく回路である。加算β復元部２４１１は、累積減算部２４１０の値とβメモリ２４０９の値を加算することで、元のβの値を復元する。λ計算部２４１２は、従来のターボデコーダのλ計算部である。
【００９２】
デインターリーブ部２４１３は、λ計算部２４１２から最終的に得られるデータはインターリーブされたものなので、そのデータを逆インターリーブして並びを戻すための回路である。繰り返し処理の結果として、事前確率Ｌｅの値は、Ｌｅメモリ２４１４に記憶され、λ計算部２４０４に供給される。
［実施例２］
実施例２は、実施例１と同様に、ＩＥＥＥ８０２．１６（ＷｉＭＡＸ）での使用を想定して、β圧縮とα圧縮したものをλ計算部のγ入力として、累積加算値をＬｅ計算に使用するターボデコーダである。図３２は、実施例２のターボデコーダを示すブロック図である。このうち、参照符号２４０１乃至２４０６までの構成要素は、図２４に示して上で説明した実施例１のターボデコーダと基本的に同じである。以下、実施例１との相違点のみを説明する。
【００９３】
図２４の累積加算部２４０７がβについてのみ累積加算をするのに対し、累積加算３２０７は、βメトリクスの計算中はβ値を累積加算し、αメトリクスの計算に切り替わると、一旦初期化して、α値を累積加算する。減算αβ圧縮部３２０８は、α計算とβ計算で共通の回路であり、β計算時はβに対して減算処理をし、α計算時はαに対して減算処理を実施する。λ計算部３２１１はラムダの演算の方法自体は図８を参照して説明した従来のターボデコーダと変わらないが、入力データの内容が累積値を減算したものになる。従ってＬｅを演算する際には、図２３を参照して説明したように、α累積加算値とβ累積減算値とを考慮する必要が生じる。
【００９４】
図３３は、一実施形態によるターボデコーダを用いた基地局を示すブロック図である。図３３に示したＩＴＳ向け基地局装置３３００は、ベースバンド部３３１０と無線ユニット３３２０とを有する。  ベースバンド部３３１０は、基地局装置３３００のスケジューリングを行うＭＡＣスケジューラ（MAC scheduler）３３１０を有する。
【００９５】
送信されるデータには、ＦＥＣコーデック３３１２において、ターボ符号を用いて、ＦＥＣ（フォワードエラーコレクション）の符号化が行われる。符号化されたデータは、ＭＡＰ生成用のＳＤＲＡＭ３３１３に記憶され、並び替え部３３１４において、論理チャネルを物理チャネルに並び替えられる。次に、パイロット挿入部３３１５において、パイロット信号が挿入される。パイロット信号が挿入されたデータは、逆高速フーリエ変換部（ｉＦＦＴ）３３１６で逆フーリエ変換された後、ＲＦユニット３３２０に高速シリアル転送される。転送されたデータは、ＲＦユニット３３２０によりＲＦ信号に変換され、アンテナ（図示せず）に送られる。
【００９６】
一方、アンテナが受信したＲＦ信号は、ＲＦユニット３３２０に入力され、デジタルデータに変換された後、ベースバンド部３３１０に高速シリアル転送される。転送されたデータは、高速フーリエ変換部３３３１に入力され、周波数領域に高速フーリエ変換される。パイロット補正部３３３２において、変換されたデータからパイロットを受信して、そのパイロット信号を元に信号補正を行う。補正されたデータは、並び替え部３３３３において、物理チャネルから論理チャネルに並び替えられる。並び替えられたデータは、ＳＤＲＡＭ３３１３に記憶され、ＦＥＣデコーデック３３３４において、復号される。ＦＥＣデコーデック３３３４は、一実施形態によるターボデコーダ３３３５を含む。このターボデコーダは、例えば、図１８に示した実施例１によるターボデコーダや、図２４に示した実施例２によるターボデコーダであってもよい。
【００９７】
以上、本実施の形態について詳述したが、本発明は特定の実施形態に限定されるものではなく、特許請求の範囲に記載された本発明の要旨の範囲内において、種々の変形及び変更が可能である。１つの実施形態または実施例に含まれるとして説明した構成要素または工程は、別の実施形態または実施例の構成要素または工程と組み合わせることも可能である。
【００９８】
なお、一部の実施形態を整理すると、以下の通りである。
（付記１）
データとフラグと前段の事前確率とから状態遷移確率を求める状態遷移確率計算部と、
前記状態遷移確率計算部において求めた状態遷移確率からアルファメトリクス及びベータメトリクスを求めるアルファ・ベータメトリクス計算部と、
前記状態遷移確率計算部において求めた状態遷移確率と、前記アルファ・ベータメトリクス計算部において求めたアルファメトリクス及びベータメトリクスとに基づき、復号データ及び次段の事前確率とを求める正規化部とを有するターボデコーダであって、
前記アルファ・ベータメトリクス計算部は時系列における複数回分の処理を同時に計算するターボデコーダ。
（付記２）
前記アルファ・ベータメトリクス計算部は、
時間ｔにおける状態遷移確率を保持する保持回路と、
前記保持回路が保持している時間ｔにおける状態遷移確率と、時間ｔ＋１における状態遷移確率とを加算する加算回路とを有する、付記１に記載のターボデコーダ。
（付記３）
さらに、状態遷移確率の最大値の累積加算値を用いて前記アルファメトリクスまたは前記ベータメトリクスを圧縮する圧縮部と、
減算圧縮部により圧縮された前記アルファメトリクスまたは前記ベータメトリクスを記憶する記憶部とを有する、付記１または２に記載のターボデコーダ。
（付記４）
データとフラグと前段の事前確率とから状態遷移確率を求める状態遷移確率計算部と、
前記状態遷移確率計算部において求めた状態遷移確率からアルファメトリクス及びベータメトリクスを求めるアルファ・ベータメトリクス計算部と、
前記状態遷移確率計算部において求めた状態遷移確率と、前記アルファ・ベータメトリクス計算部において求めたアルファメトリクス及びベータメトリクスとに基づき、復号データ及び次段の事前確率とを求める正規化部とを有するターボデコーダであって、
さらに、状態遷移確率の最大値の累積加算値を用いて前記アルファメトリクスまたは前記ベータメトリクスを圧縮する圧縮部と、
減算圧縮部により圧縮された前記アルファメトリクスまたは前記ベータメトリクスを記憶する記憶部とを有するターボデコーダ。
（付記５）
さらに、記憶部に格納されていた圧縮された前記アルファメトリクスまたは前記ベータメトリクスから、圧縮される前のアルファメトリクスまたはベータメトリクスを復元する復元部を有する、付記４に記載のターボデコーダ。
（付記６）
さらに、状態遷移確率の最大値を累積加算する累積加算部を有する、付記５に記載のターボデコーダ。
（付記７）
さらに、状態遷移確率の最大値を累積減算する累積減算部を有する、付記５または６に記載のターボデコーダ。
（付記８）
前記アルファ・ベータメトリクス計算部は時系列における複数回分の処理を同時に計算する、付記４乃至７いずれか一項に記載のターボデコーダ。
（付記９）
データとフラグと前段の事前確率とから状態遷移確率を求める状態遷移確率計算部と、
前記状態遷移確率計算部において求めた状態遷移確率からアルファメトリクス及びベータメトリクスを求めるアルファ・ベータメトリクス計算部と、
前記状態遷移確率計算部において求めた状態遷移確率と、前記アルファ・ベータメトリクス計算部において求めたアルファメトリクス及びベータメトリクスとに基づき、復号データ及び次段の事前確率とを求める正規化部とを有するターボデコーダであって、
さらに、状態遷移確率の最大値の累積加算値を用いて前記アルファメトリクスを圧縮するアルファ圧縮部と、
前記状態遷移確率の最大値の累積加算値を用いて前記ベータメトリクスを圧縮するベータ圧縮部と、
前記アルファ圧縮部により圧縮された前記アルファメトリクス、または前記ベータ圧縮部により圧縮された前記ベータメトリクスのいずれかを記憶する記憶部とを有し、
前記正規化部は、前記圧縮されたアルファメトリクス及び前記圧縮されたベータメトリクスに基づき、復号データ及び次段の事前確率とを求めるターボデコーダ。
（付記１０）
さらに、状態遷移確率の最大値を累積加算する累積加算部を有する、付記９に記載のターボデコーダ。
（付記１１）
さらに、状態遷移確率の最大値を累積減算する累積減算部を有する、付記９または１０に記載のターボデコーダ。
（付記１２）
前記アルファ・ベータメトリクス計算部は時系列における複数回分の処理を同時に計算する、付記９乃至１１いずれか一項に記載のターボデコーダ。
（付記１３）
付記１乃至１２いずれか一項に記載のターボデコーダを有する復号部を有するベースバンド部と、
前記ベースバンド部からのデジタルデータをＲＦ信号に変換してアンテナに送り、または前記アンテナからのＲＦ信号をデジタルデータに変換して前記ベースバンド部に送るＲＦ部とを有する基地局装置。
（付記１４）
データとフラグと前段の事前確率とから状態遷移確率を求める状態遷移確率計算工程と、
前記状態遷移確率計算工程において求めた状態遷移確率からアルファメトリクス及びベータメトリクスを求めるアルファ・ベータメトリクス計算工程と、
前記状態遷移確率計算工程において求めた状態遷移確率と、前記アルファ・ベータメトリクス計算工程において求めたアルファメトリクス及びベータメトリクスとに基づき、復号データ及び次段の事前確率とを求める正規化工程とを有するターボ符号の復号方法であって、
前記アルファ・ベータメトリクス計算工程において、時系列における複数回分の処理を同時に計算する復号方法。
（付記１５）
データとフラグと前段の事前確率とから状態遷移確率を求める状態遷移確率計算工程と、
前記状態遷移確率計算工程において求めた状態遷移確率からアルファメトリクス及びベータメトリクスを求めるアルファ・ベータメトリクス計算工程と、
前記状態遷移確率計算工程において求めた状態遷移確率と、前記アルファ・ベータメトリクス計算工程において求めたアルファメトリクス及びベータメトリクスとに基づき、復号データ及び次段の事前確率とを求める正規化工程とを有するターボ符号の復号方法であって、
さらに、状態遷移確率の最大値の累積加算値を用いて前記アルファメトリクスまたは前記ベータメトリクスを圧縮する圧縮工程と、
前記圧縮工程において圧縮された前記アルファメトリクスまたは前記ベータメトリクスをメモリに記憶する記憶工程とを有する復号方法。
（付記１６）
データとフラグと前段の事前確率とから状態遷移確率を求める状態遷移確率計算工程と、
前記状態遷移確率計算工程において求めた状態遷移確率からアルファメトリクス及びベータメトリクスを求めるアルファ・ベータメトリクス計算工程と、
前記状態遷移確率計算工程において求めた状態遷移確率と、前記アルファ・ベータメトリクス計算工程において求めたアルファメトリクス及びベータメトリクスとに基づき、復号データ及び次段の事前確率とを求める正規化工程とを有するターボ符号の復号方法であって、
さらに、状態遷移確率の最大値の累積加算値を用いて前記アルファメトリクスを圧縮するアルファ圧縮工程と、
前記状態遷移確率の最大値の累積加算値を用いて前記ベータメトリクスを圧縮するベータ圧縮工程と、
前記アルファ圧縮工程において圧縮された前記アルファメトリクス、または前記ベータ圧縮工程において圧縮された前記ベータメトリクスのいずれかをメモリに記憶する記憶工程とを有し、
前記正規化工程において、前記圧縮されたアルファメトリクス及び前記圧縮されたベータメトリクスに基づき、復号データ及び次段の事前確率とを求める復号方法。
【図面の簡単な説明】
【００９９】
【図１】ターボエンコーダの一般的な構成を示すブロック図である。
【図２】トレリス状態遷移の一例を示す図である。
【図３】αメトリクス状態遷移の一例を示す図である。
【図４】βメトリクス状態遷移の一例を示す図である。
【図５】ターボデコーダ単体の一般的な構成を示すブロック図である。
【図６】ターボデコーダ全体の一般的な構成を示すブロック図である。
【図７】αメトリクスの算出方法を示す図である。
【図８】λの算出方法（前半）を示す図である。
【図９】λの算出方法（後半）を示す図である。
【図１０】Ｌｅの算出方法を示す図である。
【図１１】Ｌｅの更新のタイミングを示す図である。
【図１２】βメトリクスを降順で書き込んでから昇順で読み出す場合を説明するための図である。
【図１３】αメトリクスの計算において２回分の処理を一度に実施する構成を説明するための図である。
【図１４】図１３に示した構成を並び替えた図である。
【図１５】図１４に示した構成をさらに並び替えた図である。
【図１６】一実施形態による、αメトリクスの２回分の処理を一度に実施する回路構成を示すブロック図である。
【図１７】従来のβメトリクス用メモリとその周辺回路を示すブロック図である。
【図１８】一実施形態によるβメトリクス用メモリとその周辺回路を示すブロック図である。
【図１９】αメトリクスを昇順で書き込んでから降順で読み出す場合を説明するための図である。
【図２０】従来のαメトリクス用メモリとその周辺回路を示すブロック図である。
【図２１】一実施形態によるαメトリクス用メモリとその周辺回路を示すブロック図である。
【図２２】一実施形態による、αβ圧縮とβ用メモリとその周辺回路を示すブロック図である。
【図２３】一実施形態による、αβ圧縮をした場合の事前確率Ｌｅの演算回路を示す図である。
【図２４】ターボデコーダの実施例１を示すブロック図である。
【図２５】実施例１の書き込み制御を示すタイムチャートである。
【図２６】実施例１の読み出し制御を示すタイムチャートである。
【図２７】実施例１のインターリーブ変換表である。
【図２８】実施例１の標準処理とインターリーブ処理との切替を示す図である。
【図２９】実施例１のγ計算を示すγ計算対応表である。
【図３０】実施例１のα／β回路を詳細に示すブロック図である。
【図３１】実施例１のαβ切り替え処理を示すタイムチャートである。
【図３２】ターボデコーダの実施例２を示すブロック図である。
【図３３】本実施形態によるターボデコーダを用いた基地局装置を示すブロック図である。
【符号の説明】
【０１００】
１０  ターボエンコーダ
１１  分配機
１２、１４  畳み込み符号器
１３  インターリーバー
５０  ターボデコーダ単体
５１  状態遷移確率計算部
５２  λ正規化部
５３  アルファメトリクス計算部
５４  ベータメトリクス計算部
６０  ターボデコーダ全体
６１、６４  ターボデコーダ単体
６２、６３  インターリーバー
６５  デインターリーバー
１６０  回路構成
１６２  保持回路
１６３  加算回路
１６４Ａ〜Ｄ  αβ算出部
１８００、２１１０、２２００  ターボデコーダ
１８１０、２１１０、２２１０  Ａ，Ｂ，Ｗ，Ｙ用メモリ
１８２０、２１２０、２２２０  Ｌｅ用メモリ
１８３０、２１３０、２２３０  状態遷移確率計算部
１８４０、２１４０、２２４０  α／β回路
１８５０、２２５０  βメモリ
１８６０、２１６０、２２６０  λ正規化部
１８７０、２１７０、２２７０  αβ切り替え制御回路
１８８１、２１８１、２２８１  λ最大値部
１８８２、２１８２  累積加算部
１８８３、２２８３  減算β圧縮部
１８８４  加算β復元部
１８８５、２１８５  累積減算部
２１５０  αメモリ
２１８３、２２９３  減算α圧縮部
２１８４  加算α復元部
２２８２  β累積加算部
２２９２  α累積加算部
２２８５  β累積減算部
２３００  Ｌｅ演算回路
２３１０  最大値選択部
２３２０  減算回路
【図１】
2009246474.tif 000020
【図２】
2009246474.tif 000021
【図３】
2009246474.tif 000022
【図４】
2009246474.tif 000023
【図５】
2009246474.tif 000024
【図６】
2009246474.tif 000025
【図７】
2009246474.tif 000026
【図８】
2009246474.tif 000027
【図９】
2009246474.tif 000028
【図１０】
2009246474.tif 000029
【図１１】
2009246474.tif 000030
【図１２】
2009246474.tif 000031
【図１３】
2009246474.tif 000032
【図１４】
2009246474.tif 000033
【図１５】
2009246474.tif 000034
【図１６】
2009246474.tif 000035
【図１７】
2009246474.tif 000036
【図１８】
2009246474.tif 000037
【図１９】
2009246474.tif 000038
【図２０】
2009246474.tif 000039
【図２１】
2009246474.tif 000040
【図２２】
2009246474.tif 000041
【図２３】
2009246474.tif 000042
【図２４】
2009246474.tif 000043
【図２５】
2009246474.tif 000044
【図２６】
2009246474.tif 000045
【図２７】
2009246474.tif 000046
【図２８】
2009246474.tif 000047
【図２９】
2009246474.tif 000048
【図３０】
2009246474.tif 000049
【図３１】
2009246474.tif 000050
【図３２】
2009246474.tif 000051
【図３３】
2009246474.tif 000052