(57)【要約】  ビタビ復号中にトレースバックメモリにおける列アクセスを提供するために、シフトレジスタリングを使用する。【選択図】図５
2008514158.tif 000002
【特許請求の範囲】
【請求項１】
ビタビ復号器で使用されるトレースバックメモリであって、
生き残り遷移情報を格納する行及び列を有するメモリチップと、
書込みシフトレジスタリングであって、書込み動作中に、該書込みシフトレジスタリングを通して所定データ値を逐次シフトさせることにより、前記メモリチップの列をイネーブルにする書込みシフトレジスタリングと
を具備する、トレースバックメモリ。
【請求項２】
トレースバックシフトレジスタリングであって、トレースバック読出し動作中に、該トレースバックシフトレジスタリングを通して所定データ値を逐次シフトさせることにより、前記メモリチップの列をイネーブルにし、前記所定データ値は、該トレースバックシフトレジスタリングを通して前記書込みシフトレジスタリングにおける前記所定データ値と反対方向にシフトされる、トレースバックシフトレジスタリングをさらに具備する、請求項１に記載のトレースバックメモリ。
【請求項３】
復号シフトレジスタリングであって、復号動作中に、該復号シフトレジスタリングを通して所定データ値を逐次シフトさせることにより、前記メモリチップの列をイネーブルにし、前記所定データ値は、該復号シフトレジスタリングを通して前記書込みシフトレジスタリングにおける前記所定データ値とは反対方向にシフトされる、復号シフトレジスタリングをさらに具備する、請求項２に記載のトレースバックメモリ。
【請求項４】
前記書込みシフトレジスタリング及び前記復号シフトレジスタリングは、同じクロック速度で動作し、前記トレースバックシフトレジスタリングは、異なるより高いクロック速度で動作する、請求項３に記載のトレースバックメモリ。
【請求項５】
前記書込みシフトレジスタリング及び前記トレースバックシフトレジスタリングに接続され、書込みポインタに対するトレースバックポインタの近接性に基づいて新たなトレースバック動作を開始する第１の論理回路をさらに具備する、請求項３に記載のトレースバックメモリ。
【請求項６】
前記第１の論理回路は、前記書込みシフトレジスタリングにおいて各位置にＡＮＤゲートを有する、請求項５に記載のトレースバックメモリ。
【請求項７】
前記書込みシフトレジスタリング及び前記復号シフトレジスタリングに接続され、前記書込みポインタに対する復号ポインタの近接性に基づいて復号ポインタを再配置する第２の論理回路をさらに具備する、請求項５に記載のトレースバックメモリ。
【請求項８】
前記第２の論理回路は、前記書込みシフトレジスタリングにおいて各位置にＡＮＤゲートを有する、請求項７に記載のトレースバックメモリ。
【請求項９】
前記所定データ値は論理１である、請求項１に記載のトレースバックメモリ。
【請求項１０】
前記書込みシフトレジスタリングは、リング構成で接続される複数のフリップフロップを有する、請求項１に記載のトレースバックメモリ。
【請求項１１】
前記書込みシフトレジスタリングは、リング構成で接続される複数のデータラッチを有する、請求項１に記載のトレースバックメモリ。
【請求項１２】
状態アドレスに応じて前記メモリチップの選択された行をイネーブルにする行デコーダ
をさらに具備する、請求項１に記載のトレースバックメモリ。
【請求項１３】
ビタビ復号器においてシフトレジスタリングを通して所定データ値をシフトさせることであって、それにより、トレースバックメモリの列を逐次イネーブルにしてトレリス生き残り遷移データを該列の記憶位置に書き込む、所定データ値をシフトさせること
を含む方法。
【請求項１４】
前記シフトレジスタリングは第１のシフトレジスタリングであり、
前記ビタビ復号器において第２のシフトレジスタリングを通して所定データ値をシフトさせることであって、それにより前記トレースバックメモリの列を逐次イネーブルにして前記ビタビ復号器に対するトレースバック読出し機能を実行し、前記所定値は、前記第２のシフトレジスタリングを通して前記第１のシフトレジスタリングにおける前記所定値とは反対方向にシフトされる、所定データ値をシフトさせることをさらに含む、請求項１３に記載の方法。
【請求項１５】
前記ビタビ復号器において第３のシフトレジスタリングを通して所定データ値をシフトさせることであって、それにより前記トレースバックメモリの列を逐次イネーブルにして前記ビタビ復号器に対する復号読出し機能を実行し、前記所定値は、前記第３のシフトレジスタリングを通して前記第１のシフトレジスタリングにおける前記所定値とは反対方向にシフトされる、所定データ値をシフトさせることをさらに含む、請求項１４に記載の方法。
【請求項１６】
前記第１のシフトレジスタリングを通して所定データ値をシフトさせること、及び前記第３のシフトレジスタリングを通して所定データ値をシフトさせることは、同じクロック速度で実行され、前記第２のシフトレジスタリングを通して所定データ値をシフトさせることは、異なるより高速なクロック速度で実行される、請求項１５に記載の方法。
【請求項１７】
前記第２のシフトレジスタリング内のトレースバックポインタが前記第１のシフトレジスタリング内の書込みポインタに近接している時に、新たなトレースバック動作を開始することをさらに含む、請求項１５に記載の方法。
【請求項１８】
新たなトレースバック動作を開始することは、前記第２のシフトレジスタリング内の前記トレースバックポインタが前記第１のシフトレジスタリング内の前記書込みポインタと同じ位置にある時に、前記新たなトレースバック動作を開始することを含む、請求項１７に記載の方法。
【請求項１９】
前記復号ポインタが前記第１のシフトレジスタリング内の書込みポインタに近接している時に、前記第３のシフトレジスタリング内の復号ポインタを再配置することをさらに含む、請求項１５に記載の方法。
【請求項２０】
前記所定データ値は論理１である、請求項１３に記載の方法。
【請求項２１】
生き残り遷移情報を格納する行及び列を有するメモリチップと、
書込みシフトレジスタリングであって、書込み動作中に、該書込みシフトレジスタリングを通して所定データ値を逐次シフトさせることにより、前記メモリチップの列をイネーブルにする書込みシフトレジスタリングと
を有するトレースバックメモリと、
該トレースバックメモリへの生き残り遷移情報の書込みを制御するデジタル信号プロセッサ（ＤＳＰ）と
を具備する、ビタビ復号器。
【請求項２２】
前記トレースバックメモリは、
トレースバックシフトレジスタリングであって、トレースバック読出し動作中に、該トレースバックシフトレジスタリングを通して所定データ値を逐次シフトさせることにより、前記メモリチップの列をイネーブルにし、前記所定データ値は、該トレースバックシフトレジスタリングを通して前記書込みシフトレジスタリングにおける前記所定データ値と反対方向にシフトされる、トレースバックシフトレジスタリングをさらに具備する、請求項２１に記載のビタビ復号器。
【請求項２３】
前記ＤＳＰは、前記トレースバックメモリに格納された情報を使用して前記ビタビ復号器におけるトレースバック動作の実行を制御するようにプログラムされる、請求項２２に記載のビタビ復号器。
【請求項２４】
前記トレースバックメモリは、
復号シフトレジスタリングであって、復号動作中に、該復号シフトレジスタリングを通して所定データ値を逐次シフトさせることにより、前記メモリチップの列をイネーブルにし、前記所定データ値は、該復号シフトレジスタリングを通して前記書込みシフトレジスタリングにおける前記所定データ値と反対方向にシフトされる、復号シフトレジスタリングをさらに具備する、請求項２２に記載のビタビ復号器。
【請求項２５】
前記ＤＳＰは、前記トレースバックメモリに格納された情報を使用して前記ビタビ復号器における復号動作の実行を制御するようにプログラムされる、請求項２４に記載のビタビ復号器。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、包括的にはビタビ復号に関し、特に、ビタビ復号中に使用されるトレースバックメモリに関する。
【背景技術】
【０００２】
ビタビ復号は、畳み込み符号を復号するために使用することができる復号技法である。ますます多くの有線プロトコル及び無線通信プロトコルが、通信アクティビティ中のビタビ復号の使用を必要としている。通信装置及びビタビ復号を利用する他の装置の設計中に通常扱われる問題の１つは、電力損失である。一般に、こうした装置において、回路性能が所望のレベルで又はそれを超えるように維持される一方で、電力損失は低く維持されることが望まれる。
【発明の開示】
【発明が解決しようとする課題】
【０００３】
したがって、ビタビ復号を実行するエネルギー効率のよい方法及び構造が必要とされている。
【発明を実施するための最良の形態】
【０００４】
以下の詳細な説明において、本発明が実施されるであろう特定の実施形態を例として示す添付図面を参照する。これら実施形態は、当業者が本発明を実施することができるようにするために十分詳細に説明されている。本発明のさまざまな実施形態は、異なるが、必ずしも互いに排他的ではない、ということが理解されるべきである。たとえば、本明細書において一実施形態に関連して説明する特定の特徴、構造又は特性を、本発明の精神及び範囲から逸脱することなく他の実施形態内で実現してもよい。さらに、開示された実施形態の各々における個々の要素の位置又は配置を、本発明の精神及び範囲から逸脱することなく変更してもよい、ということが理解されるべきである。したがって、以下の詳細な説明は、限定する意味で取られるべきではなく、本発明の範囲は、適当に解釈される添付の特許請求の範囲と、その特許請求の範囲に権利が与えられる均等物の完全な範囲とによってのみ定義される。図面において、同様の符号は各図を通して同じか又は同様の機能を指す。
【０００５】
ビタビ復号器には多くの用途がある。たとえば通信システムでは、ビタビ復号器を受信機で使用することにより、受信されたシンボルストリームに基づいて、遠隔送信機によって送信された可能性が最も高いシンボルストリームを確定することができる。他の用途もある（たとえばデータ記憶システム、ディスクドライブ等における）。ビタビ復号器の動作を、トレリス図を使用して表すことができる。図１は、特定のビタビ復号器のトレリス図１０の一部を示す図である。図示するように、トレリス図１０は、複数のシンボル１２、１４、１６、１８、２０を含む。シンボル１２、１４、１６、１８、２０の各々は、復号プロセス中の特定の処理段階に対応する（たとえば、シンボル１２は、段階ｉに対応し、シンボル１４は段階ｉ＋１に対応し、シンボル１６は段階ｉ＋２に対応し、等であってもよい）。シンボル１２、１４、１６、１８、２０の各々は、所定数の状態（図１において破線によって表される）を有する。たとえば、図示する実施形態では、各シンボルに対して４つの状態、すなわち第１の状態２２、第２の状態２４、第３の状態２６及び第４の状態２８がある。他のビタビ復号器は、シンボル毎に異なる数の状態を有してもよい。
【０００６】
シンボル１２、１４、１６、１８、２０内の任意の状態２２、２４、２６、２８に対し、その状態に至る複数のブランチ（又は遷移）があってもよい。たとえば、シンボル１４内の第１の状態２２に対し、（先の状態２２から）状態２２に至る第１のブランチ３０と、（先の状態２４から）状態２２に至る第２のブランチ３２とがある。同様に、シンボル１４の状態２４に対し、（先の状態２６から）状態２４に至る第１のブランチ３４と、（先の状態２８から）状態２４に至る第２のブランチ３６とがあり、以下同様に続く。このブランチパターンは、通常、トレリス１０の連続したシンボルの各々に対して繰り返す。ビタビ復号器のタイプが異なると、各状態に至るブランチの数が異なってもよい。図示するトレリスは、各状態に至るブランチが２つあるため、基数２トレリスとして知られる。
【０００７】
受信データに基づき、２つの連続するシンボル間のトレリス１０の各ブランチに対し、ブランチメトリックが計算される。たとえば、処理がシンボル１２からシンボル１４まで進んでいる場合、ブランチ３０に対してブランチメトリックが確定され、ブランチ３２に対して別のブランチメトリックが確定され、以下同様である。ブランチメトリックは、実際に受信されたデータシンボルと、そのブランチに対応するデータシンボルとの間の「距離」を表す。処理がトレリス１０を通してシンボルからシンボルに進む際、パスメトリックは、トレリスを通して複数のパスに対し、先のパスメトリックを対応するブランチメトリックに加算することにより更新される。パスメトリックは、関連するパスに対し累積される誤差の合計を表す。このように、シンボル１２からシンボル１４に遷移している時、シンボル１２の状態２２に関連するパスメトリックがブランチ３０に関連するブランチメトリックに加算されることにより、シンボル１４の状態２２に対する新たなパスメトリックが得られる。同様に、シンボル１２の状態２４に関連するパスメトリックがブランチ３２に関連するブランチメトリックに加算されることにより、シンボル１４の状態２２に対する別の新たなパスメトリックが得られる。しかしながら、これら新たなパスメトリックのうちの１つのみが、トレリス１０内を継続することが許可される。２つのパスメトリックのうちの低い方が、累積された誤差が低いため、継続するように選択される。選択されたパスメトリックに関連するブランチは、生き残りブランチ又は生き残り遷移として知られる。シンボル１４に関連する状態の各々に対し、同様のプロセスが完了する。このプロセスは、加算−比較−選択（ＡＣＳ）演算として知られる。処理がトレリス１０を通して進むに従い、新たなシンボルの各々における各状態の生き残り遷移が選択される。この生き残り遷移情報は、後に使用されるためにトレースバックメモリ内に保存される。各シンボル内の各状態に対する選択されたパスメトリックを、パスメトリックメモリ内に格納してもよい。ビタビ復号器は、さまざまなトレリスシンボルを処理するために繰返し使用される可能性のあるＡＣＳユニットの１セットを含むことが多い。
【０００８】
トレリスの少なくとも一部に対して生き残り遷移情報が収集された後、そのトレリスに対してトレースバック動作を開始してもよい。トレースバック動作は、トレリスを通して逆方向に実行される。トレースバック動作中、特定のシンボルの状態のうちの１つを、開始位置として選択してもよい。そして、プロセスは、トレースバックメモリにおける生き残りブランチ情報に従ってトレリスを通して逆方向に進む。１つのあり得る手法では、開始点として、パスメトリック（すなわち累積される誤差合計）が最低である、選択されたシンボル内の状態が選択される。しかしながら、これは必要条件ではない。それは、トレースバック動作は、トレリスを通して所定数を超えるシンボルを戻る限り（すなわちトレースバック長）、略常に適当な最も可能性の高いパス上にあるものだからである。
【０００９】
トレースバック動作が要求された数のシンボルを横切ると、同じパスを使用して「復号」プロセスを開始してもよい。復号プロセスは、本質的に元の符号化プロセスの逆である。関連するパスにおける状態から状態への各生き残り遷移に対し、復号された値である対応するデータ値がある。復号プロセスは、トレリスを通して後方に進むに従い、発生した各生き残り遷移を（トレースバックメモリ内のデータを使用して）確定し、対応するデータ値を出力する。そして、これらデータ値の方向を逆にすることにより、実際に送信された可能性が最も高いデータに達することができる。トレースバックメモリにさらなるデータが書き込まれるに従い、トレリス内の新たな開始点において、追加のトレースバック動作及び復号動作を開始してもよい。対応するトレリス内より列が少ないトレースバックメモリを使用してもよい。こうした場合、処理中にメモリに対し、何度も繰り返して再書込みしてもよい。
【００１０】
図２は、本発明の一実施形態による一例としてのトレースバックメモリ５０を示す図である。図示するように、トレースバックメモリ５０は、メモリチップ５２、行デコーダ５４及び列デコーダ５６を有してもよい。メモリチップ５２は、メモリロケーションの列及び行を含む半導体メモリである。メモリチップ５２の列は、トレリスのシンボルに対応してもよい。メモリチップ５２の行は、トレリスの状態に対応してもよい。メモリロケーションは、各行及び列の交差点に位置決めされる。このメモリロケーションを使用して、対応する状態／シンボルに対する生き残り遷移情報が格納される。メモリロケーションのサイズは、実行されている特定のトレリスによって決まる。たとえば、基数２トレリスでは、各状態に入るブランチ又は遷移は最大２である。したがって、生き残り遷移を、単一の２値ビット（すなわち、論理１か又は論理０）を使用して記述してもよい。或る状態に入る遷移が最大３つである場合、２つの２値ビットが必要とされ、以下同様である。
【００１１】
行デコーダ５４は、状態アドレスに基づいて、対象となっているトレリス状態に対応するメモリチップ５２の行を選択する（イネーブルにする）。列デコーダ５６は、シンボルアドレスに基づいて、対象となっているトレリスシンボルに対応するメモリチップ５２の列を選択する（イネーブルにする）。書込み動作中、行デコーダ５４及び列デコーダ５６によって選択されるメモリロケーションに、生き残り遷移情報を書き込んでもよい。読出し動作中（たとえばトレースバック又は復号中）、行デコーダ５４及び列デコーダ５６によって選択されるメモリロケーションから、生き残り遷移情報を読み出してもよい。処理がトレリスを通して前方に（図１では左から右へ）進むに従い、生き残り遷移情報がメモリチップ５２のさまざまな記憶位置に書き込まれる。メモリチップ５２の最後に達すると（すなわち最右列）、書込みは、メモリチップ５２の開始（すなわち最左列）において続けてもよい。
【００１２】
トレースバック動作及び復号動作中、データがメモリチップ５２から読み出されることにより、対応する機能が実行される。これは、書込みとは反対方向に実行される。列デコーダ５６及び行デコーダ５４によって列及び行がイネーブルとされると、対応する１つのトレースバックビット（又は複数のビット）を読み出して処理してもよい。そして、行デコーダ５４及び列デコーダ５６は、トレースバックビット（複数可）によって特定された先のシンボル内の状態に戻ってもよく、以下同様である。
【００１３】
図３は、図２のメモリチップ５２を実装するために使用してもよい一例としてのメモリアーキテクチャ６０を示す回路図である。メモリアーキテクチャ６０は、各行／列の組合せに対し単一ビットを格納する。ビット線６２は、対応する記憶位置からトレースバックビットを搬送するように動作可能である。ビット線６２を、読出し動作の前にプリチャージしてもよい。アーキテクチャ６０は、複数の列選択線（たとえばＣＳ０６４等）と、複数の行選択線（たとえばＲＳ０６６等）とを有する。行選択線ＲＳ０６６が論理ハイにされる場合、メモリの対応する行が、その行に対する行トランジスタ６８をオンにすることによってイネーブルにされる。同様に、列選択線ＣＳ０６４が論理ハイとされる場合、メモリの対応する列が、その列に対する列トランジスタ７０をオンにすることによってイネーブルにされる。格納されたデータビット７４に応じて、対応する記憶トランジスタ７２は「オン」か又は「オフ」のいずれかとなる。記憶トランジスタ７２が「オン」である場合、ビット線６２はディスチャージされ、第１のデータビット値が出力される。「オフ」である場合、ビット線６２はチャージされたままであり、第２の異なるデータビット値が出力される。別法として他のメモリアーキテクチャを使用してもよい。
【００１４】
本発明の少なくとも１つの実施形態では、図２の列デコーダ５６の代りに複数のシフトレジスタリングを使用する。図４は、使用してもよい一例としてのシフトレジスタリング８０を示すブロック図である。図示するように、シフトレジスタリング８０は、リング構成で直列に接続される複数のフリップフロップ８２、８４、８６、８８、９０、９２、…を含む。シフトレジスタリング８０のフリップフロップ８２、８４、８６、８８、９０、９２、…のうちの１つを、最初に論理１値に設定してもよく、その後その論理１値が、リングを通してフリップフロップからフリップフロップに同期して渡されることにより、対応するメモリチップに対する列イネーブル信号として作用するようにしてもよい。フリップフロップの代りに、他の１ビットクロック制御可能メモリデバイス（たとえばデータラッチ等）を使用してもよい。列デコーダと異なり、シフトレジスタリングは、トレースバックメモリの所望の列にアクセスするために集中化アドレスを必要としない。代りに、シフトレジスタリングは単純に、通常、トレースバックメモリにおいて必要とされるように、列から列に線形式に進行する。列デコーダではなくシフトレジスタリングを使用することにより、電力を大幅に節約することができる。たとえば、各デコーダサイクル中のスイッチング容量を、２つのフリップフロップのみのスイッチング容量まで低減することができる。一方のフリップフロップは論理０から論理１に変化し、他方は論理１から論理０に変化する。
【００１５】
図５は、本発明の一実施形態による一例としてのトレースバックメモリ１００を示すブロック図である。図５に示すように、トレースバックメモリ１００は、メモリチップ１０２、行デコーダ１０４、書込みシフトレジスタリング１０６、復号シフトレジスタリング１０８及びトレースバックシフトレジスタリング１１０を含んでもよい。メモリチップ１０２及び行デコーダ１０４は、上述したように、図２における対応する要素と同様に動作してもよい。シフトレジスタリング１０６、１０８、１１０は、メモリチップ１０２に対する列イネーブル信号として作用するように関連するリングを通して逐次論理１値（又は他の何らかの値）を各々シフトさせることによって動作してもよい。書込みシフトレジスタリング１０６は、メモリチップ１０２に生き残り遷移情報を格納するために書込み動作中に使用されるものである。復号シフトレジスタリング１０８及びトレースバックシフトレジスタリング１１０は、それぞれ復号動作及びトレースバック動作中に使用される。図示するように、書込みシフトレジスタリング１０６のシフト方向は、復号シフトレジスタリング１０８及びトレースバックシフトレジスタリング１１０のシフト方向とは反対である。さらに、トレースバックシフトレジスタリング１１０は、図示する実施形態では書込みシフトレジスタリング１０６及び復号シフトレジスタリング１０８より高いクロック速度で動作する（ただし、これが当てはまらない他の実施形態もある）。トレースバック及び書込み／復号クロックの周波数は、通常、対応するＡＣＳユニットにおいてＡＣＳブロックがいくつ使用されるかによって決まる。言い換えれば、それは、１サイクルにおいてトレースバックにビットがいくつ書き込まれているかによって決まる。これは、特定の実施態様によって決まる。トレースバッククロックは、通常、書込み／復号クロックに等しいか又は整数倍となる。
【００１６】
トレースバックメモリ１００を、対応するシステムに対してビタビ復号を実行する１つ又は複数のデジタル処理装置に結合してもよい。デジタル処理装置(複数可）には、たとえば、汎用マイクロプロセッサ、デジタル信号プロセッサ（ＤＳＰ）、縮小命令セットコンピュータ（ＲＩＳＣ）、複雑命令セットコンピュータ（ＣＩＳＣ）、フィールドプログラマブルゲートアレイ（ＦＰＧＡ）、特定用途向け集積回路（ＡＳＩＣ）、及び／又は上記の組合せを含む他のものが含まれてもよい。デジタル処理装置（複数可）は、たとえば、生き残り遷移情報のトレースバックメモリへの書込み、トレースバックメモリ内に格納されたデータを使用するトレースバック動作の実行、トレースバックメモリ内に格納されたデータを使用する復号動作の実行及び／又は他の機能を制御してもよい。
【００１７】
本発明の少なくとも１つの実施形態では、書込みシフトレジスタリング１０６、復号シフトレジスタリング１０８及びトレースバックシフトレジスタリング１１０内の論理１ビットの位置を制御するために、分散論理回路が使用される。トレースバックポインタ（すなわち、図５のトレースバックシフトレジスタリング１１０内の論理１）が現在の書込みポインタ（すなわち、図５の書込みシフトレジスタリング１０６内の論理１）に合致する場合、トレースバック動作が完了したとみなしてもよい。これが発生すると、書込みポインタの反対側において新たなトレースバック動作を開始してもよい。分散制御回路を、特にこのタスクを実行するように構成してもよい。
【００１８】
図６は、本発明の一実施形態によるトレースバックメモリ内で使用される論理回路を含む一例としての回路構成１２０を示す概略図である。図６の論理回路は、１つのリング位置のみに対して示されている。しかしながら、トレースバックメモリにおける各リング位置に対して同じか又は同様の回路構成を繰り返してもよい、ということが理解されるべきである。図６に示すように、トレースバックメモリの特定の列１２２に対し、１つの書込みフリップフロップ（又はデータラッチ）１２４、１つの復号フリップフロップ（又はデータラッチ）１２６及び１つのトレースバックフリップフロップ（又はデータラッチ）１２８がある。書込みフリップフロップを通して第１の方向１３０に論理１（又は他のデータ値）が伝播し、復号フリップフロップ及びトレースバックフリップフロップを通して反対方向１３２に（ただし異なる速度で）論理１が伝播する。書込みフリップフロップ１２４のデータ出力に接続された１つの入力と、トレースバックフリップフロップ１２８のデータ出力に接続された１つの入力とを有する、第１のＡＮＤゲート１３４が設けられる。ＡＮＤゲート１３４の出力は、トレースバックフリップフロップ１２８の左側のトレースバックフリップフロップ１３６のＳＥＴ入力に結合される。トレースバックフリップフロップ１３６は、必ずしもトレースバックフリップフロップ１２８に隣接していない。すなわち、２つの間の１つ又は複数のフリップフロップがあってもよい。この分離は、通常、実装に固有である。フリップフロップ１２４、１２８が異なる値を格納しているか又はともに論理０を格納している場合、フリップフロップ１３６に格納された値は変化しない。一方、フリップフロップ１２４、１２８がともに論理１を格納している場合、フリップフロップ１３６は論理１に設定され、そのため書込みポインタの反対側において新たなトレースバック動作が開始する。フリップフロップ１２８はまた、この時点で（論理０に）リセットされ、それにより、トレースバックシフトレジスタリングには１つの論理１しかない。
【００１９】
回路構成１２０はまた、第２のＡＮＤゲート１３８を有してもよい。第２のＡＮＤゲート１３８は、書込みフリップフロップ１２４のデータ出力に接続された１つの入力と、復号フリップフロップ１２６のデータ出力に接続された１つの入力とを有してもよい。第２のＡＮＤゲート１３８の出力を、復号フリップフロップ１２６の右側の復号フリップフロップ１４０のＳＥＴ入力に接続してもよい。このため、復号フリップフロップ１２６及び書込みフリップフロップ１２４の両方に論理１が格納されている場合、復号フリップフロップ１４０は論理１に設定される。略同時に、復号フリップフロップ１２６を論理０にリセットしてもよい。復号フリップフロップ１４０は、通常、フリップフロップ１２６から複数フリップフロップ分だけ離れている（たとえば、一実施形態では１６フリップフロップ）。このように、復号ポインタは、書込みポインタに向かって連続して移動した後、復号処理中に再び戻される。図６に示す特定の分散制御回路は、シフトレジスタリングを使用するトレースバックメモリ内で分散制御回路を実装する単なる１つの方法であることが理解されるべきである。別法として他の制御回路構成を使用してもよい。
【００２０】
本発明の一態様では、シフトレジスタリングを使用することにより、トレースバックメモリにおいてたとえば異なる符号化規格で動作するように或るレベルの再構成可能性を達成することができる。再構成可能性では、たとえば、トレースバックメモリが異なる数の状態、異なる数の遷移及び／又は異なるトレースバック長をサポートする必要がある場合がある。最大のあり得る適用に対して十分なメモリを含めることにより、たとえばさまざまなリング間でクロック周波数及びクロック率を変更することによって異なる規格に対処することができる。トレースバック長を、機能を変更することなく変更することができる。トレースバック長を増大させることは、信号対雑音比に関して改善が低下することであるが、エネルギ及びレイテンシにおいては最小の増大しか示さないため、通常、エネルギ効率のよい再構成可能トレースバックメモリを実装するためにはいくつかの異なるリングサイズのみがあればよい。
【００２１】
図７は、本発明の一実施形態による一例としての再構成可能トレースバックメモリ１５０を示すブロック図である。図示するように、再構成可能トレースバックメモリ１５０は、第１のメモリチップ１５２、第２のメモリチップ１５４、第３のメモリチップ１５６及び第４のメモリチップ１５８と、第１の行デコーダ１６０及び第２の行デコーダ１６２と、第１の４８列シフトレジスタ部１６４、第１の３２列シフトレジスタ部１６８、第２の４８列シフトレジスタ部１７０、第２の３２列シフトレジスタ部１７２と、第１のマルチプレクサ（ＭＵＸ）１７４及び第２のマルチプレクサ１７６とを有してもよい。第１の行デコーダ１６０は、メモリチップ１５２及び１５４内の選択された行をイネーブルにするように動作可能である。同様に、第２の行デコーダ１６２は、メモリチップ１５６及び１５８内の選択された行をイネーブルにするように動作可能である。第１のＭＵＸ１７４及び第２のＭＵＸ１７６により、トレースバックメモリ１５０に対し異なる規格をサポートするように可変サイズのシフトレジスタリングを達成することができる。たとえば、１つの実装では、ＭＵＸ１７４、１７６を、９６位置リングを形成するように単に２つの４８位置シフトレジスタ部１６４、１７０からリングを形成するように制御してもよい。別の実装では、シフトレジスタ部１６４、１６８、１７０、１７２のすべてを結合することにより１６０位置リングを形成してもよい。別法として他の組合せを行ってもよい。再構成可能トレースバックメモリ内で任意の数のシフトレジスタ部及びＭＵＸを使用してもよい。同様に、任意のサイズのシフトレジスタ部を使用してもよい。１つのみを図示するが、通常、トレースバックメモリ内に３つの再構成可能シフトレジスタ構成がある。また、再構成可能トレースバックメモリ内で任意の数のメモリチップを使用してもよい。別法として他の再構成可能トレースバックメモリアーキテクチャを使用してもよい。
【００２２】
本発明の技法及び構造を、種々の異なる形態のうちの任意のもので実装することができる。たとえば、本発明の特徴を、携帯電話及び他のハンドヘルド無線通信装置、無線機能を有する携帯情報端末、無線機能を有するラップトップ、パームトップ、デスクトップ及びタブレットコンピュータ、ページャ、衛星通信装置、ネットワークインタフェースカード（ＮＩＣ）及び他のネットワークインタフェース構造、集積回路、有線通信システム及び装置、たとえばハードディスクドライブを有するデジタルデータ記憶装置内で、機械可読媒体に格納された命令及び／データ構造として、且つ／又は他の形式で実装してもよい。
【００２３】
上述した詳細な説明では、本発明のさまざまな特徴を、開示を簡素化する目的で１つ又は複数の個々の実施形態にグループ化している。この開示の方法は、請求される発明が各請求項において明示的に列挙される特徴より多くの特徴を必要とするという意図を反映するものとして解釈されるべきではない。むしろ、添付の特許請求の範囲が反映するように、開示された各実施形態の特徴をすべては含まない場合にも発明の態様があり得る。
【００２４】
本発明を、いくつかの実施形態に関連して説明したが、当業者は容易に理解するように、本発明の精神及び範囲から逸脱することなく変更及び変形を用いてもよい、ということが理解されるべきである。こうした変更及び変形は、本発明及び添付の請求項の範囲内にあるものとみなされる。
【図面の簡単な説明】
【００２５】
【図１】ビタビ復号器に関連するトレリス図の一部を示す図である。
【図２】本発明の一実施形態による一例としてのトレースバックメモリを示すブロック図である。
【図３】図２のトレースバックメモリ内で使用してもよい一例としてのメモリアーキテクチャを示す回路図である。
【図４】本発明の一実施形態による一例としてのシフトレジスタリングを示すブロック図である。
【図５】本発明の一実施形態による一例としてのトレースバックメモリを示すブロック図である。
【図６】本発明の一実施形態によるトレースバックメモリで使用してもよい一例としての論理回路を示す概略図である。
【図７】本発明の一実施形態による一例としての再構成可能トレースバックメモリを示すブロック図である。
【図１】
2008514158.tif 000003
【図２】
2008514158.tif 000004
【図３】
2008514158.tif 000005
【図４】
2008514158.tif 000006
【図５】
2008514158.tif 000007
【図６】
2008514158.tif 000008
【図７】
2008514158.tif 000009
【国際調査報告】
2008514158.tif 000010