JPH08340263A

JPH08340263A - イン・プレイス現状態／次状態レジスタ

Info

Publication number: JPH08340263A
Application number: JP7342078A
Authority: JP
Inventors: David L Smith; エル．スミスディヴィッド
Original assignee: AT&T Corp
Current assignee: AT&T Corp
Priority date: 1994-12-29
Filing date: 1995-12-28
Publication date: 1996-12-24
Also published as: EP0720303A3; KR960027369A; US5619514A; SG34347A1; EP0720303A2

Abstract

(57)【要約】【課題】本発明は、通信システムまたはビタビデコー
ダで、次状態累積コストを決定する際にメモリを有効に
利用する技術を提供するものである。【解決手段】本システムは、レジスタの配列を持つメ
モリを含む。第１現状態累積コストは、配列の第１記憶
レジスタから検索される。第２現状態累積コストは、配
列の第２記憶レジスタから検索される。第１次状態累積
コストは、第１現状態累積コストに基づいて計算され
る。第１次状態累積コストは、配列の第１記憶レジスタ
に保存される。本発明の利点は、累積コストを計算し保
存するために必要なメモリが少ないことである。必要と
されるメモリ・ロケーションの数は、各個別状態につい
て１つで、これは従来必要とされたメモリ・ロケーショ
ンの実質上半分である。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は、一般にデコーダに
関し、特に、イン・プレイス・ビタビ・デコーダにおけ
る場合のような、現状態／次状態レジスタの有効な利用
に関する。

【０００２】

【従来の技術】ビタビ・デコーダは、順方向エラー訂正
を供給する最尤デコーダである。ビタビ・デコーダは、
ビット・ストリームのようなコード化されたシンボルの
シーケンスを復号化するために使用される。ビット・ス
トリームは、電気通信システムにおいて記号化された情
報を表すことが出来る。こうした記号化された情報は、
シンボル・インスタントを示す各ビット（またはビット
の組み合わせ）と共に、多様な媒体によって転送出来
る。復号化のプロセスで、ビタビ・デコーダは、各シン
ボル・インスタントの一連のビット・シーケンスを通じ
て、どのビット・シーケンスが最も転送されやすかった
かを決定する。あるシンボル・インスタント、すなわ
ち、状態から、次の連続する、シンボル・インスタン
ト、すなわち、状態への可能な遷移は限られている。あ
る状態から次状態への可能な遷移は、図示出来、ブラン
チとして定義される。一連の相互に連結されたブランチ
は、パスとして定義される。各状態は、ビット・ストリ
ーム中の次のビット（またはビットの組み合わせ）を受
け取る際に、限られた数の次状態にしか変換出来ない。
従って、復号化プロセスの間に、あるパスは残り、別の
パスは残らない。許容されない遷移を除去することによ
って、最も残りそうなパスを決定する計算能力が達成さ
れる。ビタビ・デコーダは、通常各ブランチに関連する
ブランチ・メトリックを規定・計算し、このブランチ・
メトリックを使って、どのパスが残り、どのパスが残ら
ないかを決定する。

【０００３】ブランチ・メトリックは、可能な各ブラン
チに対する各シンボル・インスタント毎に計算される。
各パスは関連するメトリックと累積コストを持ち、これ
は各シンボル・インスタント毎にアップデートされる。
各可能な遷移について、次状態の累積コストは、可能な
遷移のためのブランチ・メトリックと、個々の前状態の
パスの累積コストの総計の小さい方として計算される。

【０００４】従来の技術のデコーダは、ランダムアクセ
ス・メモリ内のメモリ・ロケーションの前もって決定さ
れたグループのレジスタの２つの配列を使用して、現状
態累積コストと、次状態累積コストを保存した。第１配
列のレジスタは、現状態累積コストを保存するために使
用された。累積コストが、次のシンボル・インスタント
のために計算される時、現状態累積コストは、第１配列
のレジスタから読み出され、計算のために使用された。
次のシンボル・インスタント、すなわち次状態のために
計算された累積コストは、第２配列のレジスタに書き込
まれた。次状態のための累積コストが全て計算された後
で、次状態の累積コストは第２配列のレジスタすなわち
ロケーションから読み出され、第１配列の対応するレジ
スタすなわちロケーションに書き込まれた。この転送
は、次状態の累積コストをアップデートするための続く
一連の計算を通じてビット・ストリーム内の次のシンボ
ルを復号化する準備としてなされた。こうして、現状の
累積コストは第１配列のレジスタに保存された。次状態
累積コストは計算され、第２配列のレジスタに保存され
た。

【０００５】

【発明が解決しようとする課題】その結果、各シンボル
・インスタント毎に、第２配列のレジスタの内容を読み
取って、第１配列の対応するレジスタに書き込む操作が
要求された。ブランチの数によって、このことは、多数
の読み書き操作を必要とした。こうしたデータ転送操作
は、非生産的な操作のための時間の浪費という意味で
も、特に、自動車電話のような、電池を電源とする機器
の場合、エネルギー消費という意味でも、デコーダの性
能を低下させる。

【０００６】２つの配列のレジスタを使用する従来の他
のデコーダは、データ転送操作を除去するためにポイン
タを使用してきた。ポインタは、２つの配列の中の１つ
を指定する。次状態累積コストが、配列の中の１つのレ
ジスタに保存された、その時の状態の累積コストに基づ
いて計算される時、新しく計算された次状態の累積コス
トは、ポインタが指定する別の配列のレジスタに保存さ
れる。全ての累積コストがアップデートされる時、ポイ
ンタは第１配列を指定するように変更され、累積コスト
がアップデートされる。このことはデータ転送操作を除
去するが、やはり累積コストの２倍のレジスタを必要と
する。

【０００７】１つの配列のレジスタから別の配列のレジ
スタに累積コストを転送する、不必要な読み書き操作
と、累積コストの２倍のレジスタの必要を除去する、累
積コストの計算と保存の有効な方法が、技術上必要とさ
れる。

【０００８】

【課題を解決するための手段】本発明に従って、通信シ
ステムまたはビタビ・デコーダの、次状態累積コストを
決定する技術において、メモリが有効に利用される。本
システムは、レジスタの配列を持つメモリを含む。第１
現状態累積コストは、配列の第１記憶レジスタから検索
される。第２現状態累積コストは、配列の第２記憶レジ
スタから検索される。第１次状態累積コストは第１現状
態累積コストに基づいて計算される。第１次状態累積コ
ストは、配列の第１記憶レジスタに保存される。本発明
の長所は、この技術では、累積コストの計算と保存のた
めに必要とされるメモリが少ないことである。必要とさ
れるメモリ・ロケーションの数は、各個別の状態毎に１
つであり、これは従来必要とされたメモリ・ロケーショ
ンの実質上半分である。

【０００９】

【発明の実施の形態】図１は、デジタル・セルラー電
話、モデム、衛星通信システム、デジタル・ビデオ通信
システムといった通信システムにおける、本発明の説明
される実施例を示す。本発明の説明される実施例では、
誤差訂正コプロセッサ１０は、デジタル信号プロセッサ
（ＤＳＰ）２０によって制御される。誤差訂正コプロセ
ッサ１０は、ＤＳＰ２０内に組み込み可能である。コプ
ロセッサのランダム・アクセス・メモリ（ＲＡＭ）１１
０のレジスタの一部は、配列１００を形成する。配列１
００のレジスタのデータは、配列から読み出され、加算
器１５０、レジスタ１６０、１７０、加算器１８０によ
って処理され、その結果生じたデータは、配列１００の
レジスタに書き込まれる。アドレス・ゼネレータ１０２
は、どのレジスタまたは配列のレジスタ１００からデー
タが読み取られ、どのレジスタまたは配列１００のレジ
スタにデータが書き込まれるかを決定する。

【００１０】誤差訂正コプロセッサ１０にデータを書き
込み、そこからデータを読み取るために、間接アクセス
技術が使用される。コプロセッサ１０のアドレスにデー
タを書き込むために、アドレスはアドレス・レジスタ２
４に書き込まれ、データはデータ・レジスタ２６に書き
込まれるが、これはどちらもＤＳＰ２０内にある。アド
レスは、ＤＳＰ２０から、コプロセッサ１０内のアドレ
ス・ゼネレータ１０２に、アドレス・バス８０を通って
転送され、フリップフロップ１４４の出力に依存する、
コプロセッサ内の対応するレジスタの変換されたアドレ
スに変換される。アドレス・ゼネレータ１０２は、フリ
ップフロップ１４４の状態に依存するビットを連結す
る。最上位のビットや、最も重要でないビットを連結し
てアドレス変換を達成する方法は良く知られている。デ
ータ・レジスタ２６に書き込まれたデータは、ＤＳＰ２
０から変換されたアドレスによって識別される、コプロ
セッサ・メモリ・ロケーションに転送される。

【００１１】コプロセッサ１０のアドレスのレジスタか
らデータを読み取るために、アドレスは、ＤＳＰ２０の
アドレス・レジスタ２４に書き込まれる。アドレスはア
ドレス・ゼネレータ１０２に転送され、上記のように変
換される。アドレス・レジスタのデータはデータ読み取
りレジスタ２６によって読み取られる。

【００１２】コプロセッサ制御ユニット１２は、あらか
じめ決定された信号のシーケンスを発生し、コプロセッ
サの機能の一面である、復号化機能を制御する。説明さ
れた実施例の開示された動作から、本技術に普通に熟練
した人は、コプロセッサ制御ユニット１２によって作ら
れる信号をたやすく組み立てることが出来る。制御ユニ
ットの動作は、ＤＳＰから制御レジスタ１４に上記のよ
うに転送される１つのインストラクションによって開始
される。

【００１３】メモリ１００の配列は、ランダム・アクセ
ス・メモリの中で、現状態と次状態の累積コストの保存
のために識別される。現状態と次状態の累積コストのバ
イナリ表示は、多くの形式の中の１つをとることが出来
る。この形式とは、サイン・エクステンデッドであり得
る２の補数、サイン・マグニチュード、浮動少数点また
は単純なバイナリ表示を含むが、それに限定されない。
配列１００は、複数のアドレス可能なメモリ・レジスタ
またはロケーションから成る。配列１００中のメモリ・
レジスタの数は、少なくとも、計算されることが必要な
現状態または次状態のコストの最大の数に適応するのに
充分である。配列１００の中で使用されるメモリ・レジ
スタの数は、配列のために配分されたメモリ・レジスタ
の数以下で良い。制約長さＣについて、配列の中で利用
されるメモリ・レジスタの数は２^C-1である。

【００１４】配列１００は、連合するアドレス・ゼネレ
ータ１０２を持つ。アドレス・ゼネレータ１０２は、読
み取り操作の間に、そこからデータが読み取られるメモ
リ・レジスタを可能にし、また、書き込み操作の間に、
データが書き込まれるメモリ・ロケーションを可能にす
る。２つの次状態累積コストの値を計算するために利用
される、配列１００に保存された２つの現状態累積コス
トの値は、配列１００から読み取られる。第１現状態累
積コストは、データ・バス１４６を通って、第１レジス
タ１４２に転送される。第２現状態累積コストは、デー
タ・バス１４６を通って、第２レジスタ１４４に転送さ
れる。どの現状態累積コストの値が転送されるかは、ど
の次状態累積コストの値が計算されるかに依存する。表
１の式を参照すること。現状態累積コストの値は、ルッ
クアップ・テーブルから取られたアドレスによって、ま
たは現状態累積コストのアドレスを発生するアドレス・
ゼネレータ１０２によって転送され、データは配列１０
０のレジスタに保存され、アドレスは読み取られ、デー
タ・バス１４６を通ってレジスタ１４２または１４４に
転送される。レジスタ１４２・１４４は、第１・第２入
力をマルチプレクサ１４８に供給する。入力選択１４７
は、マルチプレクサ１４８へのどちらの入力がその出力
１４９として供給されるかを決定する。出力１４９は、
加算器１５０への入力の１つを、マルチプレクサ１４８
を通じて接続されたレジスタ１４２または１４４に供給
する。加算器１５０への第２入力である入力１５２は、
ブランチ・メトリック・ユニット１５４によって供給さ
れるブランチ・メトリックである。各ブランチ・メトリ
ックは１度だけ必要とされ、これまで知られた方法で必
要とされるように計算される。加算器１５０の出力１５
６はデマルチプレクサ１５８に接続され、入力を供給す
る。コストが読み出されるアドレスの最も重要でないビ
ットはデマルチプレクサ１５８への入力選択１６６を供
給する。例えば、偶数のアドレスに対しては、デマルチ
プレクサ１５８は、入力１５６を出力１６２として供給
する。奇数のアドレスに対しては、デマルチプレクサ
は、入力１５６を出力１６４として供給する。出力１６
２は、レジスタ１６０に接続され、入力を供給する。出
力１６４は、レジスタ１７０に接続され、入力を供給す
る。

【００１５】レジスタ１６０の出力１６８は、加算器１
８０と接続され、入力の１つを供給する。レジスタ１７
０の出力１７２は、加算器１８０に接続され、別の入力
を供給する。加算器１８０は、入力１６８から入力１７
２を引く。レジスタ１６０からの出力１６８と、レジス
タ１７０からの出力１７２は、結合され、マルチプレク
サ１９０の入力を供給する。出力１８２の最上位のビッ
トが最重要ビット・セレクタ１８４によって決定され、
マルチプレクサ１９０への入力選択１９２として供給さ
れる。入力選択１９２は、マルチプレクサ１９０への入
力１６８または１７２の中の１つを、データ・バス１４
６に置く出力として選択する。デコーダで受け取られた
一連のバイナリ・データから、ビタビ・デコーダを使用
して記号化されたデータを複合化する時、デコーダは、
最も伝送されやすいデータのシーケンスを再構築する。
受け取ったデータは誤差を含む。エンコーダの初期状態
が知られているので、デコーダはスタート地点を持つ。
エンコーダの終了状態も知ることが出来るので、デコー
ダもあらかじめ決定された終了地点を持つ。デコーダ
は、受け取った一連のバイナリ・データのための、最も
良い状態の遷移のシーケンスを決定しなければならな
い。個々のこうした状態が、シンボル・インスタントを
示す。各状態またはシンボル・インスタントで、ゼロか
ら、Ｃが抑制長さである時、２^C-1−１までの、多数の
状態がある。これらの２^C-1の状態は個別状態と呼ばれ
る。制限された数の遷移が可能である。各シンボル・イ
ンスタントで、累積コストは計算され、各可能な遷移の
ために保存される。

【００１６】各シンボル・インスタントで、本発明の説
明される実施例の各個別状態は、２つの可能な次の個別
状態にだけ遷移出来るが、発明はそう制限されない。そ
れに伴って、各次の個別状態は、そこから遷移が発生す
る２つの可能な以前の個別状態しか持たない。別のデコ
ーダは、次状態への遷移を２つ以上持ち得る。

【００１７】ブランチ・メトリックは、ある個別状態か
ら、次の個別状態への可能な遷移毎に各シンボル・イン
スタントで計算される。ブランチ・メトリックを計算す
る様々な方法が、技術上知られている。所与の次の個別
状態に遷移する両ブランチのブランチ・メトリックは計
算され、対応して発生する累積コストに加算され、２つ
の可能な累積コストの合計になる。２つの可能な累積コ
ストの合計が比較される。極値の合計が、次状態累積コ
ストとして選択される。説明される実施例では、２つの
合計の小さい方の極値の合計が説明されるが、発明はそ
う制限されない。少ない方の合計に対応する遷移は、２
つの可能な初めの個別状態から、所与の次の個別状態に
より遷移しやすい。より適当な遷移の初めの個別状態
は、所与の次の個別状態のための起源として保存され
る。少ない方の合計は、次の個別状態の累積コストであ
り、その個別状態の累積コストに取って代わる。このプ
ロセスは、ビット・ストリーム中の全てのシンボルが復
号化されるまで、各個別状態毎に繰り返され、各シンボ
ル・インスタント毎にも繰り返される。

【００１８】一例として、抑制長さが４の時、２^4-1ま
たは８の個別状態がある。状態遷移図を図２に示す。実
線は、シリーズの中の次のビットが０の時の、次状態へ
の遷移を示し、破線は、シリーズの中の次のビットが１
の時の、次状態への遷移を示す。図２の８つの個別状態
の各々の次状態累積コストを計算する式を表１に示す。 NSAC(000) = Lesser{PSAC(000) + BM(000), PSAC(001) + BM(001)} NSAC(001) = Lesser{PSAC(010) + BM(010), PSAC(011) + BM(011)} NSAC(010) = Lesser{PSAC(100) + BM(100), PSAC(101) + BM(101)} NSAC(011) = Lesser{PSAC(110) + BM(110), PSAC(111) + BM(111)} NSAC(100) = Lesser{PSAC(000) + BM(000), PSAC(001) + BM(001)} NSAC(101) = Lesser{PSAC(010) + BM(010), PSAC(011) + BM(011)} NSAC(110) = Lesser{PSAC(100) + BM(100), PSAC(101) + BM(101)} NSAC(111) = Lesser{PSAC(110) + BM(110), PSAC(111) + BM(111)} 表１次状態累積コストの式表の上半分と下半分のブランチ・メトリックについて、
同じシンボルが使われているが、違う数量が示されてい
ることが理解される。説明される実施例では、表１の上
半分のブランチ・メトリックは０の受け取りに起因し、
表１の下半分のブランチ・メトリックは１の受け取りに
起因する。

【００１９】次状態累積コストの式の組み合わせが、同
じ２つの現状態累積コストの値を含むことを認識するこ
とは、次状態累積コストの値の計算と保存をある程度有
効にする。ＮＳＡＣ（０００）とＮＳＡＣ（１００）
は、ＰＳＡＣ（０００）とＰＳＡＣ（００１）の関数で
ある。ＮＳＡＣ（００１）とＮＳＡＣ（１０１）は、Ｐ
ＳＡＣ（０１０）とＰＳＡＣ（０１１）の関数である、
等。より詳細には、個別状態０００の次状態累積コスト
である、ＮＳＡＣ（０００）は、個別状態０００の現状
態累積コストである、ＰＳＡＣ（０００）と、ブランチ
０００のブランチ・メトリックである、ＢＭ（０００）
か、個別状態００１の現状態累積コストである、ＰＳＡ
Ｃ（００１）と、ブランチ００１のブランチ・メトリッ
クであるＢＭ（００１）の、小さい方である。同じ現状
態累積コストと、違うブランチ・メトリックは、個別状
態１００の次状態累積コストを計算するのに使用され
る。個別状態１００の次状態累積コストである、ＮＳＡ
Ｃ（１００）は、個別状態０００の現状態累積コストで
ある、ＰＳＡＣ（０００）と、ブランチ０００のブラン
チ・メトリックである、ＢＭ（０００）か、状態００１
の現状態累積コストであるＰＳＡＣ（００１）と、ブラ
ンチ００１のブランチ・メトリックである、ＢＭ（００
１）の小さい方である。この計算は、全ての次状態コス
トが、所与のシンボル・インスタントについて計算され
るまで、全ての個別状態について繰り返される。次状態
累積コストの計算は、図１の回路を利用して達成され
る。現状態累積コストは、例えば、第１メモリ・ロケー
ション（例えば、アドレス０００）に始まり、０の値を
持つ第１メモリ・ロケーションと、非常に大きな負の値
を持つ、続くメモリ・ロケーションで開始される、配列
１００に保存される。最初、累積コストは、通常、順次
式メモリ・レジスタに保存される。

【００２０】アドレス・ゼネレータ１０２は、アドレス
を発生し、アドレスによって識別されるレジスタを読み
取れるようにする。読み取り操作は、個別状態０００の
累積コストを、配列１００のメモリ・レジスタからデー
タ・バス１４６に転送する。データ・バス１４６は、個
別状態０００の累積コストを、デマルチプレクサ１４０
を通じて、入力選択１４１に決定されるとおりに、２つ
のレジスタ１４２または１４４の１つに供給する。例え
ば、個別状態０００の累積コストがレジスタ１４２に転
送されたと仮定する。アドレス・ゼネレータ１０２は、
個別状態００１の累積コストのアドレスを発生し、配列
１００のメモリ・レジスタから累積コストを読み取っ
て、データ・バス１４６に転送する。データ・バス１４
６は、個別状態００１の累積コストを、入力選択１４１
によって決定された通りに、２つのレジスタ１４２また
は１４４の別の方（ここでは、１４４）に供給する。レ
ジスタ１４２または１４４に保存された２つの累積コス
トの値は、個別状態０００と１００の次状態累積コスト
の計算に使用される。

【００２１】マルチプレクサ１４８は、入力選択１４７
によって決定された通りに、レジスタ１４２に保存され
た累積コストをその出力１４９として供給する。出力１
４９は、加算器１５０への１つのオペランド入力を供給
する。加算器１５０への他の入力は、ブランチ・メトリ
ック・ユニット１５４によって計算されるように、ブラ
ンチ０００のブランチ・メトリックである。加算器１５
０からの合計の出力は、デマルチプレクサ１５８の入力
を供給する。現状態累積コストのアドレスの最も重要で
ないビットは、デマルチプレクサ１５８への入力選択と
して使用され、デマルチプレクサ１５８に出力１６２を
選択させ、加算器１５０からの出力１５６をレジスタ１
６０への入力として供給させる。出力１６２は、転送さ
れ、一時的にレジスタ１６０に保存される。この合計
を、ＣＯＳＴ（ｉ）と呼ぶ。

【００２２】入力選択１４７は、別のレジスタであるレ
ジスタ１４４を選択し、マルチプレクサ１４８を通じて
加算器１５０と接続する。出力１４９は、加算器１５０
への入力を供給する。ブランチ・メトリック・ユニット
１５４によって供給される加算器１５０への別の入力
は、状態００１の計算されたブランチ・メトリックであ
る。加算器１５０からの合計の出力はデマルチプレクサ
１５８への入力を供給する。現状態累積コストのアドレ
スの最も重要でないビットは、デマルチプレクサ１５８
への入力選択として使用され、デマルチプレクサ１５８
に、出力１７２を選択させ、加算器１５０からの出力１
５６をレジスタ１７０への入力として供給させる。出力
１６４は転送され、一時的にレジスタ１７０に保存さ
れ、ＣＯＳＴ（ｉ＋１）と呼ばれる。

【００２３】２つの合計ＣＯＳＴ（ｉ）とＣＯＳＴ（ｉ
＋１）の少ない方が選択され、状態０００の現状態累積
コストに代わって次状態の累積コストまたは次のシンボ
ル・インスタントを示す。ＣＯＳＴ（ｉ）とＣＯＳＴ
（ｉ＋１）の小さい方は、２つの合計を比較し、小さい
方を選択することによって決定される。ＣＯＳＴ（ｉ）
は、加算器１８０への１つの入力オペランドを供給す
る。もう一方の入力オペランドはＣＯＳＴ（ｉ＋１）で
ある。加算器１８０は、ＣＯＳＴ（ｉ＋１）からＣＯＳ
Ｔ（ｉ）を引き、その差を出力１８２として供給する。
ＣＯＳＴ（ｉ＋１）がＣＯＳＴ（ｉ）より大きければ、
出力１８２の最上位のビットは、負の符号を持つ１であ
る。さもなければ、最上位のビットは０である。最重要
ビット・セレクタ１８４は、出力１８２の最上位のビッ
トを選択し、最上位のビットを出力１９２として供給す
る。出力１９２は、マルチプレクサ１９０への入力選択
である。入力選択は、マルチプレクサへの入力１６８ま
たは入力１７２のどちらの累積コスト入力が、少ない方
のコストとして選択され、データ・バス１４６に供給さ
れるかを決定する。ＣＯＳＴ（ｉ＋１）が、ＣＯＳＴ
（ｉ）より大きい時、最上位のビットは１であり、マル
チプレクサ１９０に加算器１８０への小さい方の入力で
ある入力１６８を選択させ、データ・バス１４６に置
く。さもなければ、最上位のビットは０であり、マルチ
プレクサ１９０に、ＣＯＳＴ（ｉ）である入力１６８を
選択させ、データ・バス１４６に置く。こうして、加算
器１８０と、最重要ビット・セレクタ１８４は、ＣＯＳ
Ｔ（ｉ）またはＣＯＳＴ（ｉ＋１）の中の小さい方の累
積コストを選択するコンパレータとして機能し、小さい
方の累積コストをデータ・バス１４６に供給する。アド
レス・ゼネレータ１０２は、個別状態０００の累積コス
トがそこから読み取られる配列１００のレジスタを可能
にする。これは、それ以上の値を持たない配列１００の
レジスタにデータを上書きする。通常、次状態累積コス
トは、配列１００のレジスタに保存され、そこから、現
状態累積コストが、次状態累積コストの計算に使用され
るために読み出される。現状態配列の各レジスタは、次
状態累積コスト計算の過程で一度読み出される。

【００２４】個別状態１００の次状態累積コストが計算
される。個別状態０００と００１の現状態累積コストは
レジスタ１４２と１４４にそれぞれ保存され続けてい
る。配列１００の同じコストの１つは上書きされた。上
記で説明したように、レジスタ１４２に保存された累積
コストは、マルチプレクサ１４８を通じて加算器１５０
への１つの入力オペランドとして供給される。ブランチ
・メトリック・ユニット１５４は、ブランチ０００のブ
ランチ・メトリックを計算し、加算器１５０の別の入力
オペランドとして供給する。加算器１５０の合計の出力
は、デマルチプレクサ１５８の入力を供給する。現状態
累積コストのアドレスの最も重要でないビットは、デマ
ルチプレクサ１５８の入力選択として使用され、デマル
チプレクサ１５８に出力１６２を選択させ、加算器１５
０からの出力１５６を、レジスタ１６０への入力として
供給させる。出力１６２は転送され、レジスタ１６０
に、ＣＯＳＴ（ｉ）として、一時的に保存される。

【００２５】入力選択１４７は、個別状態００１の現状
態累積コストを含み、マルチプレクサ１４８を通じて加
算器１５０と接続する、別のレジスタである、レジスタ
１４４を選択する。出力１４９は、加算器１５０の入力
を供給する。加算器１５０のもう１つの入力は、ブラン
チ・メトリック・ユニット１５４によって供給される、
状態００１の計算されたブランチ・メトリックである。
加算器１５０からの合計の出力は、デマルチプレクサ１
５８の入力を形成する。現状態累積コストのアドレスの
最も重要でないビットは、デマルチプレクサ１５８への
入力選択として使用され、デマルチプレクサ１５８に出
力１９２を選択させ、加算器１５０からの出力１５６を
レジスタ１７０への入力として供給させる。出力１６４
は転送され、レジスタ１７０にＣＯＳＴ（ｉ＋１）とし
て保存される。

【００２６】ＣＯＳＴ（ｉ）とＣＯＳＴ（ｉ＋１）の小
さい方が選択され、状態００１の現状態累積コストに取
って代わる。加算器１８０は、ＣＯＳＴ（ｉ）からＣＯ
ＳＴ（ｉ＋１）を引き、最重要ビット・セレクタ１８４
は、マルチプレクサ１９０への入力選択として最上位の
ビットを供給する。マルチプレクサ１９０は、ＣＯＳＴ
（ｉ）とＣＯＳＴ（ｉ＋１）の小さい方を選択し、小さ
い方のコストをデータ・バス１６４に供給する。状態１
００の現状態累積コストが保存されている配列１００の
メモリ・レジスタは、アドレス・ゼネレータ１０２によ
って可能となり、次状態累積コストは、レジスタに書き
込まれる。その時デコーダは、次のシンボルを復号化す
る用意が出来ている。このプロセスは、各個別状態につ
いて、配列１００のレジスタに保存された次状態累積コ
ストがあるように、個別状態の全ての次状態累積コスト
が計算されるまで、繰り返される。

【００２７】こうして、累積コストを保存する、配列１
００のレジスタの各２^C-1の累積コストは、現状態累積
コストから次状態累積コストにアップデートされる。ア
ップデートが完了すると、次状態は現状態となり、この
プロセスが繰り返される。このサイクルは、シンボル・
インスタントまたは復号化されるデータの状態の数だけ
続く。

【００２８】図３は、Ｃ＝４とする、説明される実施例
について、現状態累積コストに取って代わる次状態累積
コストを示す。８つの個別状態がある。

【００２９】データは、データ・レジスタ２４によって
ＤＳＰ２０とコプロセッサ１０の間で転送される。ＤＳ
Ｐ２０は、コプロセッサ１０のどのメモリ・レジスタか
らも読み取り・書き込みが出来る。コプロセッサのメモ
リ・レジスタは、メモリ・レジスタのアドレスをＤＳＰ
１０のアドレス・レジスタ２４に置くことによって、間
接的にアドレスされる。アドレス・ゼネレータ１０２
は、アドレス・レジスタ２４から、アドレス・バス８０
を通じてアドレスを受け取る。読み取り操作において、
コプロセッサ１０は、アドレスされたコプロセッサ・メ
モリ・レジスタの内容を、受け取りデータ・レジスタに
転送し、そこで、ＤＳＰ２０によって読み取られる。こ
うした操作のシーケンスを通じて、累積コストの全ての
配列はＤＳＰ２０に転送される。

【００３０】図３から、現状態累積コストが、最初にバ
イナリ０からバイナリ７までの番号順にあっても、次状
態累積コストは同じ番号順にないことが分かる。ベース
１０で、Ｃ＝４の場合の、説明される実施例の次状態累
積コストは、０；４；１；５；２；６；３；７の順序に
なる。図３ａでアップデートされた全ての累積コストに
ついて、図３ａで、次状態累積コストとされた累積コス
トは、図３ｂで示される次状態では、現状態累積コスト
とされる。次状態累積コストが計算されると、順序はま
た変化する。新しい順序は、０；２；４；６；１；３；
５；７である。全ての累積コストがアップデートされる
と、図３ｂの累積コストの新しい状態は、図３ｃの現状
態累積コストとされる。図３ｃで、次状態累積コストが
求められると、次状態累積コストはもとの番号順に戻
る。各Ｃ−１状態の累積コストは、続いた番号順にある
と一般化出来る。復号化がＣ−１の倍数で停止するな
ら、累積コストを並べ直す必要はない。しかし、伝送さ
れるビット、またはビットの組み合わせが、Ｃ−１の倍
数でないなら、一連のビットまたはビットの組み合わせ
の復号化が終わった時に、累積コストを並べ直す必要が
ある。または、累積コストを計算結果の非連続的な順序
のままにしておき、ユーザーがアクセスの際にアドレス
を補正しても良い。

【００３１】復号化が、図３ａに示す次状態で終了する
と、累積コストは、２つの通路を上昇する個別状態の順
序の配列から読み取り出来る。個別状態０００から始ま
る第１の通路では、交互に起こるレジスタを読み取り出
来る。第２の通路では、交互に起こるレジスタは、個別
状態０００に続くレジスタに始まる。

【００３２】復号化が、図３ｂに示す次状態で終了する
と、累積コストは、４つの通路を上昇する個別状態の順
序の配列から読み取り出来る。個別状態０００から始ま
る第１の通路では、各４つめのレジスタが読まれる。第
２の通路では、個別状態０００より１つ高くインデック
スを付けられたレジスタから始まる、各４つめのレジス
タが読まれる。第２の通路の開始点より１高いレジスタ
である開始点からインデックスを付けられた、第３の通
路では、各４つめのレジスタが読まれる。第３の通路の
開始点より１高いインデックスを付けられたレジスタか
ら始まる第４の通路では、各４つめのレジスタが読まれ
る。

【００３３】復号化が、図３ｃに示す次状態で終了する
と、累積コストは、１つの通路を上昇する個別状態の順
序から読み取り出来る。これは、説明される実施例の場
合Ｃが４である時、Ｃ−１の整数倍である３に依存す
る。配列中の次状態累積コストの順序は、パラメーター
Ｃと、いくつの状態またはシンボル・インスタントが、
Ｃ−１の整数倍以外に復号化されたかによってあらかじ
め決定されている。

【００３４】本発明は、この技術を含む集積回路を利用
する通信システム及び機器において特に有益である。こ
うした通信システム及び機器は、メモリの必要を減らせ
る利点を持つ。ある点で、この利点は１つの配列のレジ
スタの内容を不必要に読み取り、第２の配列のレジスタ
に書き込むことによらずに達成出来る。

【００３５】本発明の説明される実施例は、結合するパ
イプライン方式として説明されていないが、本技術に熟
練した人は、設計にパイプライン方式を利用することに
よって計算効率が拡大することを認識するだろう。パイ
プライン方式は、前にセットしたデータの計算を完了す
る前にセットされた新しいデータの計算を開始すること
によって達成される。パイプライン方式で使用されるラ
ッチが多いほど、パイプラインの深さも大きくなる。パ
イプライン方式はパイプラインを満たすために必要とさ
れる計算時間に初めの待ち時間を発生するが、加算器や
減算器といったリソースの利用を最大化する。

【図面の簡単な説明】

【図１】コプロセッサの付いたデジタル信号プロセッサ
における本発明の説明される実施例の、簡略図である。

【図２】制約長さが４の時の、状態遷移図である。

【図３】現状態累積コストの内容のシーケンスを示す図
である。

【符号の説明】

１２コプロセッサ制御ユニット１４制御レジスタ２２インストラクション・レジスタ２４アドレス・レジスタ２６データ・アドレス１０２アドレス・ゼネレータ１４２レジスタ１４４レジスタ１４８マルチプレクサ１５０加算器１５４ブランチ・メトリック・ユニット１８０加算器１８４最重要ビット・セレクタ１９０マルチプレクサ

Claims

【特許請求の範囲】

【請求項１】どの次状態累積コストを、レジスタの配
列をもつ通信システムの中に保持するかを決定する際
に、メモリを有効に利用する方法であって、配列（例えば、１００）の第１記憶レジスタから第１現
状態累積コストを検索するステップと、配列（例えば、１００）の第２記憶レジスタから第２現
状態累積コストを検索するステップと、第１現状態累積コストに基づいて第１次状態累積コスト
を計算するステップと、第１次状態累積コストを配列（例えば、１００）の前記
第１記憶レジスタに保存するステップとを含む方法。
【請求項２】どの次状態累積コストを保持するかを決
定する際にメモリを有効に利用する方法であって、第１現状態累積コストを第１一時レジスタ（例えば、１
４２または１４４）に保存するステップを含む、請求項
１に記載の方法。
【請求項３】どの次状態累積コストを保持するかを決
定する際にメモリを有効に利用する方法であって、第２現状態累積コストを第２一時レジスタ（例えば、１
４４または１４２）に保存するステップを含む、請求項
１に記載の方法。
【請求項４】どの次状態累積コストを保持するかを決
定する際にメモリを有効に利用する方法であって、第２現状態累積コストに基づいて第２次状態累積コスト
を計算するステップと、第２次状態累積コストを配列（例えば、１００）の前記
第２記憶レジスタに保存するステップとを含む、請求項
１に記載の方法。
【請求項５】どの次状態累積コストを保持するかを決
定する際にメモリを有効に利用する方法であって、配列（例えば、１００）の第３記憶レジスタから第３現
状態累積コストを検索するステップと、配列（例えば、１００）の第４記憶レジスタから第４現
状態累積コストを検索するステップと、第３現状態累積コストに基づいて、第３次状態累積コス
トを計算するステップと、第３次状態累積コストを、配列（例えば、１００）の前
記第３記憶レジスタに保存するステップとを含む、請求
項１に記載の方法。
【請求項６】信号処理のための集積回路であって、レジスタの配列（例えば、１００）と、配列（例えば、１００）の第１レジスタから第１現状態
累積コストを検索する手段と、配列（例えば、１００）の第２レジスタから第２現状態
累積コストを検索する手段と、前記第１または第２現状態累積コストの中の１つに基づ
いて、第１次状態累積コストを計算する手段と、配列（例えば、１００）の前記第１レジスタに第１次状
態累積コストを保存する手段とを含む、集積回路。
【請求項７】保存手段がランダム・アクセス・メモリ
（例えば、１１０）を含む、請求項６に記載の集積回
路。
【請求項８】計算手段が加算器（例えば、１５０）を
含む、請求項６に記載の集積回路。
【請求項９】計算手段がコンパレータ（例えば、１８
０、１８４）を含む、請求項６に記載の集積回路。
【請求項１０】記憶レジスタから成るメモリを含み、
一連のシンボル・インスタントの各可能な遷移毎に次状
態累積コストの極値を決定するビタビ・デコーダにおい
て、どの次状態が保持されるかを決定する方法であっ
て、第１現状態に関連する第１累積コストを第１記憶レジス
タから検索するステップと、第１現状態に関連する第１累積コストを、第１ブランチ
・メトリックに加算して第１の可能な累積コストを得る
ステップと、第２現状態に関連する第２累積コストを第２記憶レジス
タから検索するステップと、第２累積コストを、第２ブランチ・メトリックに加算し
て第２の可能な累積コストを得るステップと、第１・第２の可能な累積コストの極値を、次状態累積コ
ストとして選択するステップと、次状態累積コストを第１記憶レジスタに保存するステッ
プとを含む方法。
【請求項１１】次状態累積コストの極値を決定する方
法であって、第１・第２の可能な累積コストの中の小さ
い方を次状態累積コストとして選択し、第１・第２の可能な累積コストの中の１つを、もう一方
から引き算して差を求めるステップと、差のバイナリ表示の最上位のビットを識別するステップ
と、差のバイナリ表示の最上位のビットによって、第１・第
２の可能な累積コストを次状態累積コストとして決定す
るステップとを含む、請求項１０に記載の方法。
【請求項１２】次状態累積コストの極値を決定する方
法であって、現状態から次状態への遷移に対応するブランチ・メトリ
ックを計算するステップを含む、請求項１０に記載の方
法。
【請求項１３】状態累積コストの極値を決定する方法
であって、極値が第１・第２の可能な累積コストの小さ
い方の値である、請求項１０に記載の方法。