JPH07191868A - 現状態／次状態レジスタの効率的利用 - Google Patents

現状態／次状態レジスタの効率的利用

Info

Publication number
JPH07191868A
JPH07191868A JP6279635A JP27963594A JPH07191868A JP H07191868 A JPH07191868 A JP H07191868A JP 6279635 A JP6279635 A JP 6279635A JP 27963594 A JP27963594 A JP 27963594A JP H07191868 A JPH07191868 A JP H07191868A
Authority
JP
Japan
Prior art keywords
cost
array
state
accumulated cost
cumulative
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Granted
Application number
JP6279635A
Other languages
English (en)
Other versions
JP3262250B2 (ja
Inventor
David M Blaker
マーク ブレイカー ディヴィッド
Marc S Diamondstein
スチーヴン ダイアモンドスティン マーク
Gregory S Ellard
スチーヴン エラード グレゴリー
Mohammad Shafiul Mobin
シャフィウル モビン モハメッド
Homayoon Sam
サム ホマヨーン
Mark Ernest Thierbach
アーネスト ゼアバッハ マーク
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
AT&T Inc
Original Assignee
American Telephone and Telegraph Co Inc
AT&T Inc
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by American Telephone and Telegraph Co Inc, AT&T Inc filed Critical American Telephone and Telegraph Co Inc
Publication of JPH07191868A publication Critical patent/JPH07191868A/ja
Application granted granted Critical
Publication of JP3262250B2 publication Critical patent/JP3262250B2/ja
Anticipated expiration legal-status Critical
Expired - Fee Related legal-status Critical Current

Links

Classifications

    • H—ELECTRICITY
    • H03—ELECTRONIC CIRCUITRY
    • H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
    • H03M13/00—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes
    • H03M13/37—Decoding methods or techniques, not specific to the particular type of coding provided for in groups H03M13/03 - H03M13/35
    • H03M13/39—Sequence estimation, i.e. using statistical methods for the reconstruction of the original codes
    • H03M13/41—Sequence estimation, i.e. using statistical methods for the reconstruction of the original codes using the Viterbi algorithm or Viterbi processors
    • H03M13/4138—Sequence estimation, i.e. using statistical methods for the reconstruction of the original codes using the Viterbi algorithm or Viterbi processors soft-output Viterbi algorithm based decoding, i.e. Viterbi decoding with weighted decisions
    • H03M13/4146—Sequence estimation, i.e. using statistical methods for the reconstruction of the original codes using the Viterbi algorithm or Viterbi processors soft-output Viterbi algorithm based decoding, i.e. Viterbi decoding with weighted decisions soft-output Viterbi decoding according to Battail and Hagenauer in which the soft-output is determined using path metric differences along the maximum-likelihood path, i.e. "SOVA" decoding
    • H—ELECTRICITY
    • H03—ELECTRONIC CIRCUITRY
    • H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
    • H03M13/00—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes
    • H03M13/65—Purpose and implementation aspects
    • H03M13/6502—Reduction of hardware complexity or efficient processing
    • H—ELECTRICITY
    • H03—ELECTRONIC CIRCUITRY
    • H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
    • H03M13/00—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes
    • H03M13/37—Decoding methods or techniques, not specific to the particular type of coding provided for in groups H03M13/03 - H03M13/35
    • H03M13/39—Sequence estimation, i.e. using statistical methods for the reconstruction of the original codes
    • H03M13/3961—Arrangements of methods for branch or transition metric calculation
    • H—ELECTRICITY
    • H03—ELECTRONIC CIRCUITRY
    • H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
    • H03M13/00—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes
    • H03M13/37—Decoding methods or techniques, not specific to the particular type of coding provided for in groups H03M13/03 - H03M13/35
    • H03M13/39—Sequence estimation, i.e. using statistical methods for the reconstruction of the original codes
    • H03M13/41—Sequence estimation, i.e. using statistical methods for the reconstruction of the original codes using the Viterbi algorithm or Viterbi processors
    • H—ELECTRICITY
    • H03—ELECTRONIC CIRCUITRY
    • H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
    • H03M13/00—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes
    • H03M13/65—Purpose and implementation aspects
    • H03M13/6502—Reduction of hardware complexity or efficient processing
    • H03M13/6505—Memory efficient implementations

Landscapes

  • Physics & Mathematics (AREA)
  • Probability & Statistics with Applications (AREA)
  • Engineering & Computer Science (AREA)
  • Theoretical Computer Science (AREA)
  • Error Detection And Correction (AREA)
  • Detection And Correction Of Errors (AREA)
  • Dc Digital Transmission (AREA)

Abstract

(57)【要約】 【目的】 例えば通信システムまたはビタビ デコーダ
において、どの次状態累積コストを保持すべきかを決定
するときにメモリを効率的に利用するための方法を提供
する。 【構成】 本システムは、第１のアレイ（１００）に割
り当てられたレジスタ部分と第２のアレイ（１２０）に
割り当てられたレジスタ部分を有するメモリ（１１０）
を含む。本方法は、第１のアレイ（１００）の記憶レジ
スタから現状態累積コストを読み出し、この現状態累積
コストに基づいて次状態累積コストを計算することを含
む。次状態累積コストは第２のアレイ（１２０）の記憶
レジスタに記憶される。第２のアレイ（１２０）は現状
態累積コストを含むものとして指定される。現状態累積
コストは第２のアレイ（１２０）の記憶レジスタから読
み出され、後続の次状態累積コストの計算に用いられ
る。後続の次状態累積コストは第１のアレイ（１００）
の記憶レジスタに記憶される。

Description

【発明の詳細な説明】
【０００１】
【産業上の利用分野】本発明は一般にデコーダに関す
る。
【０００２】
【従来の技術及び発明が解決しようとする課題】ビタビ
デコーダ(Viterbi decoder) はフォワードエラー訂正
を提供する見込みが最もあるデコーダである。ビタビ
デコーダは、エンコードされた一連のシンボル例えばビ
ットストリームをデコードするのに用いられる。ビット
ストリームは通信システムのエンコード情報を表わすこ
とができる。前記エンコード情報は、各ビット（または
ビット群）がシンボル瞬時を表わす種々の媒体を介して
送信することができる。デコード処理において、ビタビ
デコーダは、各シンボル瞬時にあり得る一連のビット
列に戻って働きかけ、どのビット列を伝達するのが最適
かを決定する。あるシンボル瞬時すなわち状態のビット
から新たな後続のシンボル瞬時すなわち状態のビットま
でに起こり得る遷移は限られている。ある状態から次の
状態までに起こり得る各遷移は線図で示すことができ、
ブランチとして定義される。相互接続された一連のブラ
ンチは進路として定義される。各状態は、ビットストリ
ームの次のビット（またはビット群）の受け取りに基づ
く限られた数の次状態にのみ遷移することができる。し
たがって、進路のうちにはデコード処理の間残るものと
残らないものとがある。許されないそれらの遷移を除去
することにより、残すべき最適の進路を決定するときの
計算効率を達成することができる。ビタビ デコーダ
は、典型的に、各ブランチと関連するブランチメトリッ
クを定義して計算し、このブランチメトリックを用いて
どの進路を残しどの進路を残さないかを決定する。
【０００３】ブランチメトリックは各シンボル瞬時にお
いて起こり得る各ブランチについて計算される。各進路
は、各シンボル瞬時で更新される関連メトリック累積コ
ストを有する。起こり得る各遷移について、次状態の累
積コストは、起こり得る遷移のブランチメトリックとそ
れぞれの前状態の進路累積コストの和のうちの小さい方
として計算される。
【０００４】従来のデコーダは、ランダムアクセスメモ
リ内の予め定められたメモリ位置群にある２つのレジス
タアレイを用いて、現状態累積コストと次状態累積コス
トを記憶していた。第１のアレイのレジスタは現状態累
積コストを記憶するために用いられた。次のシンボル瞬
時の累積コストを計算する時に、現状態累積コストを第
１のアレイのレジスタから読み出して前記計算に用いて
いた。計算された次のシンボル瞬時すなわち次状態の累
積コストは第２のアレイのレジスタに書き込まれた。全
ての次状態累積コストの計算後、次状態累積コストは第
２のアレイのレジスタすなわち位置から読み出され、第
１のアレイの対応するレジスタすなわち位置に書き込ま
れた。この転送は、ビットストリームの次のシンボルの
デコードに備えて、次状態の累積コストを更新するため
の後続の一連の計算の間じゅう行われた。このように、
現状態累積コストは第１のアレイのレジスタに記憶され
ていた。次状態累積コストは計算されて第２のアレイの
レジスタに記憶されていた。その結果、各シンボル瞬時
において、第２のアレイのレジスタの内容を読み出して
第１のアレイの対応するレジスタに書き込む作業工程が
必要であった。ブランチ数に依存して、これは多数の読
み出し／書き込み作業工程を要した。これらのデータ転
送作業工程は、非生産的な作業工程で失われる時間に関
して、また自動車電話のようなバッテリ式装置における
エネルギー消費に関して、デコーダの性能を劣化させ
る。
【０００５】一方のアレイのレジスタから他方のアレイ
のレジスタに累積コストを転送する不要な読み出し及び
書き込み作業工程をなくして累積コストを効率的に計算
記憶するための方法の必要性が技術上残っている。
【０００６】
【課題を解決するための手段】本発明の一態様は、例え
ば通信システムまたはビタビ デコーダにおいて、どの
次状態累積コストを保持すべきかを決定するときにメモ
リを効率的に利用するための方法である。この方法は、
第１のアレイに割り当てられた第１のレジスタ群と第２
のアレイに割り当てられた第２のレジスタ群を有するメ
モリを含む。この方法は、第１のアレイのレジスタから
現状態累積コストを読み出し、この現状態累積コストに
基づいて次状態累積コストを計算することを含む。次状
態累積コストは第２のアレイのレジスタに記憶される。
次いで、第２のアレイは現状態累積コストを含むものと
して指定される。現状態累積コストは第２のアレイのレ
ジスタから読み出され、後続の次状態累積コストの計算
に用いられる。後続の次状態累積コストは第１のアレイ
のレジスタに記憶される。本発明の利点は、このような
方法がより効率的な処理を提供すると同時に電力消費を
減らし、それによりバッテリ式装置のバッテリ寿命を延
ばすことである。
【０００７】
【実施例】図１は、デジタルセルラー電話、モデム、衛
星通信システムまたはデジタル映像通信システムのよう
な通信システムにおける本発明の実施例を示す。本発明
の実施例では、エラー訂正相互処理器１０はデジタル
シグナル プロセッサ（ＤＳＰ）２０で制御される。エ
ラー訂正相互処理器１０はＤＳＰ２０に埋め込むことが
できる。相互処理器のランダムアクセスメモリ（ＲＡ
Ｍ）１１０のレジスタ部分は２つのアレイ１００及び１
２０に分割される。各々のアレイのレジスタからのデー
タはそのアレイから読み出され、加算器１５０、レジス
タ１６０及び１７０、加算器１８０で処理され、その結
果生じたデータが他のアレイのレジスタに書き込まれ
る。アドレス発生器１０２は、フリップフロップ１４４
と協動して、データが書き込まれるアレイばかりでなく
データが読み出されるアレイも決定する。
【０００８】エラー訂正相互処理器からのデータ書き込
み及びデータ読み出しのために、間接アドレス指定方法
が用いられる。相互処理器１０のアドレスのレジスタに
データを書き込むために、アドレスはＤＳＰ２０のアド
レスレジスタ２４に書き込まれ、データはＤＳＰ２０の
データレジスタ２６に書き込まれる。アドレスは、アド
レスバス８０によりＤＳＰ２０から相互処理器１０のア
ドレス発生器１０２に転送され、フリップフロップ１４
４の出力によって決まる相互処理器の対応するレジスタ
の変換アドレスに変換される。アドレス発生器１０２は
フリップフロップ１４４の状態によって決まるビットを
連結する。最上位ビットまたは最下位ビットのどちらか
を連結してアドレス変換を得る方法は周知である。デー
タレジスタ２６に書き込まれたデータは、ＤＳＰ２０か
ら、変換アドレスで識別される相互処理器メモリ位置に
転送される。
【０００９】相互処理器１０のあるアドレスのレジスタ
からデータを読み出すために、アドレスはＤＳＰ２０の
アドレスレジスタ２４に書き込まれる。このアドレスは
アドレス発生器１０２に転送され、上述のように変換さ
れる。アドレス指定されたレジスタのデータはデータレ
ジスタ２６を読むことにより読み出される。
【００１０】共通相互処理器制御装置１２は、相互処理
器の動作の一態様であるデコード機能を制御するための
予め決められた信号烈を発生する。実施例の開示された
動作から、当業者は相互処理器制御装置１２で生じる信
号を容易に構築することができる。制御装置の動作は、
上述のようにＤＳＰから制御レジスタ１４に転送される
信号指令で開始される。
【００１１】２つのメモリアレイ１００及び１２０は、
現状態及び次状態累積コストを記憶するためにランダム
アクセスメモリ内で区別される。現状態及び次状態累積
コストのバイナリ表現は多くの形式のうちの１つを採用
することができる。この形式は、広範囲の符号になり得
る２の補数、符号の大きさ、浮動点、または簡単なバイ
ナリ表現を含むがそれらに限らない。各アレイは、複数
のアドレス指定可能なメモリレジスタまたは位置からな
る。各アレイのメモリレジスタの数は、少なくとも計算
に必要な現状態または次状態の最大数を適応させるのに
十分なものにする。各アレイに用いられるメモリレジス
タの数はアレイに割り当てられたメモリレジスタの数よ
り少なくても良い。制約長Ｃに対して、各アレイに用い
られるメモリレジスタの数は２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)} 表１ 次状態累積コスト式
【００１９】表の上半分と下半分のブランチメトリック
について同一シンボルが用いられているが、異なる数量
が表わされていることがわかる。模範的な例では、表１
の上半分のブランチメトリックは０の入力に起因してい
るのに対して、表１の下半分のブランチメトリックは１
の入力に起因している。
【００２０】個別状態０００の次状態累積コストＮＳＡ
Ｃ（０００）は、個別状態０００の現状態累積コストＰ
ＳＡＣ（０００）及びブランチ０００のブランチメトリ
ックＢＭ（０００）、または状態００１の現状態累積コ
ストＰＳＡＣ（００１）及びブランチ００１のブランチ
メトリックＢＭ（００１）のうちの小さい方になる。同
様に、状態００１の次状態累積コストＮＳＡＣ（００
１）は、状態０１０の現状態累積コストＰＳＡＣ（０１
０）及びブランチ０１０のブランチメトリックＢＭ（０
１０）、または状態０１１の現状態累積コストＰＳＡＣ
（０１１）及びブランチ０１１のブランチメトリックＢ
Ｍ（０１１）のうちの小さい方になる。この計算は、全
ての次状態コストが所定のシンボル瞬時で計算されるま
で、個別状態の全てについて繰り返される。次状態累積
コストの計算は図１の回路を用いて達成される。現状態
累積コストは、例えばその中の第１のメモリ位置（例え
ばアドレス０００）から始まるアレイ１００に記憶さ
れ、０の値を持つ第１のメモリ位置と非常に大きな負の
値を持つ後続のメモリ位置で初期化される。レジスタ１
４８で決定される状態にある反転フリップフロップ１４
４の出力１４２に従って、反転フリップフロップ１４４
の出力１４２は、現状態累積コストがアレイ１００から
読み出されることになるのを決定する。
【００２１】アドレス発生器１０２はアドレスを発生
し、このアドレスで確認されたレジスタを読み出し可能
にする。読み出し動作は、状態０００の累積コストをア
レイ１００のメモリレジスタからデータバス１４６に転
送する。データバス１４６は加算器１５０への１つの演
算数入力を提供する。加算器１５０の他方の入力は、ブ
ランチメトリック装置１５４で計算されたものとしての
ブランチ０００のブランチメトリックである。加算器１
５０からの和出力はデマルチプレクサ１５８への入力を
提供する。現状態累積コストのアドレスの最下位ビット
は０なので、デマルチプレクサ１５８は出力１６２を選
択し、加算器１５０からの出力１５６をレジスタ１６０
の入力として提供する。出力１６２はレジスタ１６０に
転送されて一時的に記憶される。この和はＣＯＳＴ
（ｉ）と呼ばれる。
【００２２】次いで、アドレス発生器１０２は状態００
１の累積コストのアドレス（例えばアドレス００１）を
発生し、そのメモリレジスタを読み出し可能にする。典
型的には、累積コストは逐次メモリレジスタに記憶され
る。状態００１の累積コストの値はデータバス１４６に
よりアレイ１００のそのメモリレジスタから読み出さ
れ、加算器１５０の入力として供給される。ブランチメ
トリック装置１５４で与えられる他方の入力は、状態０
０１の計算されたブランチメトリックである。加算器１
５０からの和出力はデマルチプレクサ１５８への入力を
提供する。現状態累積コストのアドレスの最下位ビット
は１なので、デマルチプレクサ１５８は出力１７２を選
択し、加算器１５０からの出力１５６をレジスタ１７０
の入力として提供する。出力１６４は、レジスタ１７０
に転送されて一時的に記憶され、ＣＯＳＴ（ｉ＋１）と
呼ばれる。
【００２３】これらの２つの和ＣＯＳＴ（ｉ）及びＣＯ
ＳＴ（ｉ＋１）のうちの小さい方が選択されて状態００
０の現状態累積コストに取って代わり、次状態の累積コ
ストを表わす。ＣＯＳＴ（ｉ）及びＣＯＳＴ（ｉ＋１）
のうちの小さい方は、２つの和を比較して小さい方を選
択することによって決定される。ＣＯＳＴ（ｉ）は加算
器１８０の一方の入力演算数を提供し、他方の入力演算
数はＣＯＳＴ（ｉ＋１）である。加算器１８０はＣＯＳ
Ｔ（ｉ＋１）からＣＯＳＴ（ｉ）を減算し、それらの差
として出力１８２を提供する。ＣＯＳＴ（ｉ＋１）がＣ
ＯＳＴ（ｉ）より大きい場合は、出力１８２の最上位ビ
ットはマイナス記号を意味する１になる。さもなけれ
ば、最上位ビットは０になる。最上位ビットセレクタ１
８４は出力１８２の最上位ビットを選択し、その最上位
ビットを出力１９２として提供する。出力１９２はマル
チプレクサ１９０への選択入力になる。選択入力は、マ
ルチプレクサ１９０への入力として入力１６８または入
力１７２のどちらの累積コストを小さい方のコストとし
てしてデータバス１４６に供給するかを決定する。ＣＯ
ＳＴ（ｉ＋１）がＣＯＳＴ（ｉ）より大きい場合は、最
上位ビットは１となり、マルチプレクサ１９０に加算器
１８０への小さい方の入力になる入力１６８を選択せし
め、データバス１４６にのせる。さもなければ、最上位
ビットは０になり、マルチプレクサ１９０にＣＯＳＴ
（ｉ）の入力１６８を選択せしめ、データバス１４６に
のせる。このように、加算器１８０と最上位ビットセレ
クタ１８４は比較器として機能し、小さい方の累積コス
トＣＯＳＴ（ｉ）またはＣＯＳＴ（ｉ＋１）を選択し、
その小さい方の累積コストをデータバス１４６に供給す
る。アドレス発生器１０２は次状態アレイとして指定さ
れたアレイのレジスタを機能付与する。アレイ１００が
現状態アレイに指定された場合、データバス１４６上の
データは、アドレス発生器１０２で識別されたアレイ１
２０のメモリレジスタへ読み出される。典型的には、ア
レイ１２０のレジスタに記憶された次状態累積コスト
は、アレイ１００の同じ個別状態の現状態累積コストの
レジスタに対応するレジスタに記憶される。現状態アレ
イの各レジスタは、次状態アレイに記憶される次状態累
積コストを計算するときに２度アクセスされる。
【００２４】続いて、個別状態００１の次状態累積コス
トが計算される。読み出し動作は、個別状態００１の累
積コストをアドレス発生器１０２で機能付与されたアレ
イ１００のメモリレジスタ（例えばアドレス０１０）か
らデータバス１４６に転送する。データバス１４６は加
算器１５０への一方の入力演算数を提供する。ブランチ
メトリック装置１５４はブランチ０１０のブランチメト
リックを計算し、加算器１５０の他方の入力演算数とし
て供給する。加算器１５０からの和出力はデマルチプレ
クサ１５８の入力を供給する。現状態累積コストのアド
レスの最下位ビットは１なので、デマルチプレクサ１５
８は出力１６２を選択し、加算器１５０からの出力１５
６をレジスタ１６０の入力として提供する。出力１６２
はＣＯＳＴ（ｉ）としてレジスタ１６０に転送されて一
時的に記憶される。
【００２５】個別状態０１１の累積コストを含むレジス
タのアドレスはアドレス発生器１０２で発生し（例えば
アドレス０１１）、機能付与される。個別状態０１１の
累積コストの値はアレイ１００のそのメモリレジスタか
ら読み出され、加算器１５０の入力として供給される。
加算器１５０の他方の入力は、ブランチメトリック装置
１５４で与えられる状態０１１の計算されたブランチメ
トリックである。加算器１５０からの和出力はデマルチ
プレクサ１５８への入力を提供する。現状態累積コスト
のアドレスの最下位ビットは１なので、デマルチプレク
サ１５８は出力１９２を選択し、加算器１５０からの出
力１５６をレジスタ１７０の入力として提供する。出力
１６４はＣＯＳＴ（ｉ＋１）としてレジスタ１７０に転
送されて一時的に記憶される。
【００２６】ＣＯＳＴ（ｉ）とＣＯＳＴ（ｉ＋１）のう
ちの小さい方が選択され、状態００１の現状態累積コス
トに取って代わる。加算器１８０はＣＯＳＴ（ｉ）から
ＣＯＳＴ（ｉ＋１）を減算し、最上位ビットセレクタ１
８４はその最上位ビットを選択入力としてマルチプレク
サ１９０に供給する。マルチプレクサ１９０はＣＯＳＴ
（ｉ）及びＣＯＳＴ（ｉ＋１）のうちの小さい方を選択
し、その小さい方のコストをデータバス１４６に供給す
る。上述のように、アレイ１２０のメモリレジスタはア
ドレス発生器１０２で機能付与され、次状態累積コスト
はこのレジスタに書き込まれる。次状態累積コストが書
き込まれるアレイ１２０のメモリレジスタは、典型的に
は、個別状態００１の現状態コストが記憶されたアレイ
１００のレジスタ位置に対応する。この工程は、全ての
累積コストが個別状態について計算され、アレイ１００
のレジスタに記憶された各現状態累積コストについての
アレイ１２０のレジスタに記憶された次状態累積コスト
が存在するようになるまで繰り返される。
【００２７】レジスタ１４８の状態が変化すると、フリ
ップフロップ１４４の出力が反転する。この点で、デバ
ッギング能力を、次状態累積コストが正確であるかどう
かをアクセスするために引き出すことができる。データ
はデータレジスタ２４によりＤＳＰ２０と相互処理器１
０間で転送される。ＤＳＰ２０は相互処理器１０のメモ
リレジスタのどれにも読み出しまたは書き込みを行なう
ことができる。相互処理器のメモリレジスタは、ＤＳＰ
１０のアドレスレジスタ２４にメモリレジスタアドレス
を置くことにより間接的にアドレス指定される。アドレ
ス発生器１０２はアドレスバス８０を介してアドレスレ
ジスタ２４からアドレスを受け取る。読み出し動作時、
相互処理器１０は、アドレス指定された相互処理器メモ
リレジスタの内容を、ＤＳＰ２０で読み出すことができ
る受信データレジスタに転送する。一連の前記動作によ
り、一連の次状態累積コスト全体ばかりでなく一連の現
状態累積コスト全体とレジスタ１４８の状態とを、ＤＳ
Ｐ２０に転送することができる。
【００２８】デバッギングツールとして、ＤＳＰ２０
は、ブランチメトリック値と次状態累積コストを独立し
て計算することができる。ＤＳＰ２０は、ＤＳＰで計算
された次状態累積コストを相互処理器で計算された次状
態累積コストと比較し、次状態累積コストが相互処理器
で正確に計算されたかどうかを独立して確かめることが
できる。次状態累積コストが正確な場合、相互処理器は
ビットストリームの次のシンボルのデコードに進む。Ｄ
ＳＰと相互処理器で計算された次状態累積コストが不一
致の場合は、レジスタ１４８の状態はＤＳＰで反転さ
れ、データレジスタ２６に新しい状態を書き込むと共に
アドレスレジスタ２６にレジスタ１４８のアドレスを入
力する。これはフリップフロップ１４４を反転させる。
次いで、相互処理器は上述のように各個別状態の次状態
累積コストを再計算する。次状態累積コストの再計算
時、相互処理器はアレイ１００のレジスタから現状態累
積コストを読み出し、アレイ１２０のレジスタに次状態
累積コストを書き込む。新たに計算された次状態累積コ
ストは正確さについてチェックしてもしなくても良い。
【００２９】次いで、デコーダは次のシンボルをデコー
ドする準備をする。アレイ１２０のレジスタの内容は、
連続的に読み出されてアレイ１００の対応するレジスタ
に書き込まれ、現状態累積コストアレイとして指定され
るアレイ１００と次状態累積コストアレイとして指定さ
れるアレイ１２０を常に持つことを可能にする。しか
し、本発明によれば、次状態累積コストが計算されれ
ば、２つのアレイの指定は逆になる。シンボル瞬時毎に
２つのアレイの指定が逆になり、それにより、一方のア
レイのレジスタから他方のアレイのレジスタに次状態累
積コストを写す必要性がなくなり、累積コストの計算効
率が増大する。アレイの指定の逆転は後続値を持たない
データのオーバーライティングを可能にする。
【００３０】指定の逆転したがって２つのアレイの機能
の逆転はレジスタ１４８の状態の変化によって達成され
る。レジスタ１４８の状態の変化はフリップフロップ１
４４を反転させ、フリップフロップ１４４は各アドレス
に連結されたビットを反対にする。
【００３１】次状態累積コストを計算するために、アド
レス発生器１２２はアドレス（例えばアドレス０００）
を発生し、アドレス指定されたメモリレジスタを読み出
し可能にする。この読み出し動作は、状態０００の累積
コストをアレイ１２０のアドレス指定されたメモリレジ
スタからデータバス１４６に転送する。データバス１４
６は加算器１５０への一方の入力を提供する。加算器１
５０の他方の入力はブランチメトリック装置１５４で計
算されたものとしてのブランチ０００のブランチメトリ
ックである。加算器１５０からの和出力はデマルチプレ
クサ１５８への入力を提供する。現状態累積コストのア
ドレスの最下位ビットは０なので、デマルチプレクサ１
５８は出力１６２を選択し、加算器１５０からの出力１
５６をレジスタ１６０の入力として提供する。出力１６
２はＣＯＳＴ（ｉ）としてレジスタ１６０に転送されて
一時的に記憶される。
【００３２】次いで、アドレス発生器１０２は状態００
１の累積コストのアドレス（例えばアドレス００１）を
発生し、そのメモリレジスタを読み出し可能にする。状
態００１の累積コストの値は、アレイ１２０のそのメモ
リレジスタから読み出され、加算器１５０の一方の入力
として供給される。ブランチメトリック装置１５４で与
えられる他方の入力は、個別状態００１の計算されたブ
ランチメトリックである。加算器１５０からの和出力は
デマルチプレクサ１５８への入力を提供する。現状態累
積コストのアドレスの最下位ビットは１なので、デマル
チプレクサ１５８は出力１７２を選択し、加算器１５０
からの出力１５６をレジスタ１７０の入力として提供す
る。出力１６４はＣＯＳＴ（ｉ＋１）としてレジスタ１
７０に転送されて一時的に記憶される。
【００３３】これらの和ＣＯＳＴ（ｉ）またはＣＯＳＴ
（ｉ＋１）のうちの小さい方が選択され、上述のように
状態０００の現状態累積コストに取って代わる。ＣＯＳ
Ｔ（ｉ）またはＣＯＳＴ（ｉ＋１）のうちの小さい方は
マルチプレクサ１９０でデータバス１４６に供給され
る。計算された次状態累積コストは、次状態アレイとし
て指定されたアレイのメモリレジスタに書き込まれる。
現状態アレイとしてアレイ１２０が指定されている場合
は、計算された次状態累積コストは、アドレス発生器１
０２で機能付与されたアレイ１００のメモリ位置に書き
込まれる。典型的に、アレイ１００に記憶される次状態
累積コストは、同じ個別状態の累積コストを含むアレイ
１２０のレジスタ位置に対応するレジスタに記憶され
る。アドレス発生器が漸増し、個別状態００１の次状態
累積コストが計算される。次状態累積コスト計算は、全
ての次状態累積コストが各個別状態について計算される
まで継続する。レジスタ１４８の状態が変化すると、フ
リップフロップ１４４の出力が反転する。デバッギング
能力はこのシンボル瞬時に引き出され、現状態累積コス
トはアレイ１２０からＤＳＰ２０のデータレジスタ２６
に転送され、次状態累積コストはアレイ１００からＤＳ
Ｐに転送される。
【００３４】デコーダは次のシンボルをデコードする準
備をする。２つの相互処理器メモリアレイの指定は前の
シンボル瞬時に対して逆になる。これは、レジスタ１４
８の状態を変更して上述のようにフリップフロップ１４
４を反転させることにより達成される。これは、個別状
態の現状態累積コストを再びアレイ１００のレジスタか
ら読み出させ、それに対応して次状態累積コストを再び
アレイ１２０のレジスタに書き込ませる。全ての個別状
態の次状態累積コストの計算後、フリップフロップ１４
４は再び反転する。したがって、各シンボル瞬時におけ
る次状態累積コストを計算した結果、累積コストのどの
アレイを現状態アレイとみなしかつどのアレイを次状態
アレイとみなすかは、ビットストリームの全シンボルが
デコードされるまで逆になる。このように、第１のアレ
イのレジスタは初めは現状態累積コストを含む。次状態
累積コストが計算され、第２のアレイのレジスタに書き
込まれる。次のシンボル瞬時において、次状態は現状態
になり、第２のアレイの前の次状態累積コストは、次の
シンボル瞬時で計算する目的のために現状態コストにな
る。第１のアレイの前の現状態コストは、計算された次
状態累積コストを記憶するために第１のアレイを用いて
オーバーライトされる。このように、２つのアレイのう
ちのどちらかを現状態累積コストを含む現状態アレイと
し、どちらかのアレイを次状態累積コストを含む次状態
アレイとする指定が重要となり、第１のアレイから第２
のアレイに代わり、次に第１のアレイに戻る。このアレ
イ指定は、ビットストリームの全シンボルがデコードさ
れるまで交互する。
【００３５】本発明は、この方法を含む集積回路を用い
る通信システム及び機器に特に有効である。前記通信シ
ステム及び機器は電力消費の減少と時間の節約という利
点を有する。一態様において、これらの利点は、一方の
アレイのレジスタの内容を不必要に読み出して第２のア
レイのレジスタに書き込むことなく達成される。
【００３６】本発明の実施例は情報入手経路指示を含む
ものとして説明されていないが、当業者は、設計におい
て情報入手経路指示を用いることにより利用できる増大
した計算効率を認めるだろう。情報入手経路指示は、前
のデータ群を用いた計算の終了前に次のデータ群を用い
た計算を始めることによって得られる。情報入手経路指
示で用いられるラッチが多くなるほど、情報入手経路指
示の深さは大きくなる。情報入手経路指示は、情報ルー
トを満たすのに必要な計算時間の初期潜伏を生じるが、
加算器や減算器のような供給源の使用法を最大限に活用
する。
【図面の簡単な説明】
【図１】相互処理器としてのデジタル シグナル プロ
セッサにおける本発明の実施例の概略図である。
【図２】制約長４の状態遷移図である。
───────────────────────────────────────────────────── フロントページの続き (72)発明者 マーク スチーヴン ダイアモンドスティ ン アメリカ合衆国 18104 ペンシルヴァニ ア，アレンタウン，ノース フォーティス ストリート 1491 (72)発明者 グレゴリー スチーヴン エラード イギリス国 アールジー12 ５ユーエー, バークシャー，ビンフィールド，ボルトン ズ レーン 29 (72)発明者 モハメッド シャフィウル モビン アメリカ合衆国 18052 ペンシルヴァニ ア，ホワイトホール，コーナーストーン プレイス 112 (72)発明者 ホマヨーン サム アメリカ合衆国 18106 ペンシルヴァニ ア，ウェスコスヴィル，クラブ ハウス レーン 6073 (72)発明者 マーク アーネスト ゼアバッハ アメリカ合衆国 18104 ペンシルヴァニ ア，アレンタウン，ウィアー ミル ロー ド 2282

Claims (22)

    【特許請求の範囲】
  1. 【請求項１】 第１のアレイに割り当てられたメモリ部
    分と、第２のアレイに割り当てられたメモリ部分とを有
    する通信装置においてどの次状態累積コストを保持すべ
    きかを決定するときのメモリの効率的利用方法であっ
    て、 第１のアレイ（１００）の記憶レジスタから現状態累積
    コストを読み出す工程と、 前記現状態累積コストに基づいて次状態累積コストを計
    算する工程と、 前記次状態累積コストを第２のアレイ（１２０）の記憶
    レジスタに記憶する工程と、 前記第２のアレイ（１２０）を現状態累積コストを含む
    ものとして指定する工程とからなることを特徴とする方
    法。
  2. 【請求項２】 請求項１記載のどの次状態累積コストを
    保持すべきかを決定するときのメモリの効率的利用方法
    において、さらに、 第２のアレイ（１２０）の記憶レジスタから現状態累積
    コストを読み出す工程と、 後続の次状態累積コストを計算する工程と、 前記後続の次状態累積コストを第１のアレイ（１００）
    の記憶レジスタに記憶する工程とを含む方法。
  3. 【請求項３】 請求項２記載のどの次状態累積コストを
    保持すべきかを決定するときのメモリの効率的利用方法
    において、さらに、 再び現状態累積コストを含むものとして第１のアレイ
    （１００）を指定する工程と、 前記第１のアレイの記憶レジスタ（１００）から現状態
    累積コストを読み出す工程と、 後続のシンボル瞬時の次状態累積コストを計算する工程
    と、 後続のシンボル瞬時の次状態累積コストを第２のアレイ
    （１２０）の記憶レジスタに記憶する工程とを含む方
    法。
  4. 【請求項４】 請求項１記載のどの次状態累積コストを
    保持すべきかを決定するときのメモリの効率的利用方法
    において、さらに、 前記第２のアレイ（１２０）の記憶レジスタから現状態
    累積コストを読み出す工程と、 前記現状態累積コストが正確かどうかを評価する工程と
    を含む方法。
  5. 【請求項５】 請求項４記載のどの次状態累積コストを
    保持すべきかを決定するときのメモリの効率的利用方法
    において、さらに、 再び現状態累積コストを含むものとして第１のアレイ
    （１００）を指定する工程と、 前記第１のアレイの記憶レジスタ（１００）から現状態
    累積コストを読み出す工程と、 次状態累積コストを計算する工程と、 前記次状態累積コストを第２のアレイ（１２０）の記憶
    レジスタに記憶する工程とを含み、次状態累積コストが
    再計算される方法。
  6. 【請求項６】 請求項５記載のどの次状態累積コストを
    保持すべきかを決定するときのメモリの効率的利用方法
    において、再び現状態累積コストを含むものとして第１
    のアレイ（１００）を指定する工程は、フリップフロッ
    プ（１４４）の状態を変更する工程からなる方法。
  7. 【請求項７】 請求項１記載のどの次状態累積コストを
    保持すべきかを決定するときのメモリの効率的利用方法
    において、現状態累積コストを含むものとして第２のア
    レイ（１２０）を指定する工程は、フリップフロップ
    （１４４）の状態を変更する工程からなる方法。
  8. 【請求項８】 請求項１記載のどの次状態累積コストを
    保持すべきかを決定するときのメモリの効率的利用方法
    において、前記次状態累積コストを第２のアレイ（１２
    ０）の記憶レジスタに記憶する工程は、現状態累積コス
    トが読み出された第１のアレイ（１００）のメモリ位置
    に対応する第２のアレイ（２０）のメモリ位置に次状態
    累積コストを記憶する工程からなる方法。
  9. 【請求項９】 請求項１記載のどの次状態累積コストを
    保持すべきかを決定するときのメモリの効率的利用方法
    において、第１のアレイ（１００）の記憶レジスタから
    現状態累積コストを読み出す工程は、 第１のアレイ（１００）の記憶レジスタから第１の現状
    態と関連する累積コストを読み出す工程と、 第１のアレイ（１００）の記憶レジスタから第２の現状
    態と関連する累積コストを読み出す工程とからなり、 次状態累積コストを計算する工程は、 前記第１の現状態と関連する累積コストを第１のブラン
    チメトリックに加算して第１の潜在的累積コストを生じ
    せしめる程と、 前記第２の現状態と関連する累積コストを第２のブラン
    チメトリックに加算して第２の潜在的累積コストを生じ
    せしめる工程と、 前記第１及び第２の潜在的累積コストのうちの小さい方
    を次状態累積コストとして選択する工程とからなる方
    法。
  10. 【請求項１０】 請求項９記載のどの次状態累積コスト
    を保持すべきかを決定するときのメモリの効率的利用方
    法において、前記第１及び第２の潜在的累積コストのう
    ちの小さい方を次状態累積コストとして選択する工程
    は、 第１及び第２の累積コスト候補の一方から他方を引いて
    その差を生じせしめる工程と、 前記差のバイナリ表現の最上位ビットを識別する工程
    と、 前記差のバイナリ表現の最上位ビット（１８４）により
    前記第１及び第２の累積コスト候補のうちの小さい方を
    次状態累積コストとして決定する工程とからなる方法。
  11. 【請求項１１】 請求項９記載のどの次状態累積コスト
    を保持すべきかを決定するときのメモリの効率的利用方
    法において、前記第１及び第２の累積コスト候補のうち
    の小さい方を次状態累積コストとして決定する工程は、
    どちらが小さいかを決定するために前記第１及び第２の
    累積コスト候補を比較する工程からなる方法。
  12. 【請求項１２】 請求項１１記載のどの次状態累積コス
    トを保持すべきかを決定するときのメモリの効率的利用
    方法において、どちらが小さいかを決定するために前記
    第１及び第２の累積コスト候補を比較する工程は、 第１の累積コスト候補（１６８）及び第２の累積コスト
    候補（１７２）の一方から他方を引いてその差（１８
    ２）を生じせしめる工程と、 前記差のバイナリ表現の最上位ビットを識別する工程
    （１８４）と、 前記差のバイナリ表現の最上位ビット（１８４）により
    前記第１の累積コスト候補（１６８）及び第２の累積コ
    スト候補（１７２）のうちの小さい方を次状態累積コス
    トとして決定する工程とからなる方法。
  13. 【請求項１３】 第１のアレイに割り当てられたメモリ
    部分と、第２のアレイに割り当てられたメモリ部分を有
    するビタビ デコーダにどの次状態累積コストを保持す
    べきかを決定するときの記憶装置の効率的利用方法であ
    って、 ａ）第１のアレイ（１００）の記憶レジスタから現状態
    累積コストを読み出す工程と、 ｂ）前記現状態累積コストに基づいて次状態累積コスト
    を計算する工程と、 ｃ）前記次状態累積コストを第２のアレイ（１２０）の
    記憶レジスタに記憶する工程と、 ｄ）次状態累積コストが、第１のシンボル瞬時における
    各状態について第２のアレイ（１２０）の各記憶レジス
    タに記憶されるまで、前記工程ａ），ｂ）及びｃ）を繰
    り返す工程と、 ｅ）前記第２のアレイ（１２０）を現状態累積コストを
    含むものとして指定する工程と、 ｆ）第２のアレイ（１２０）の記憶レジスタから現状態
    累積コストを読み出す工程と、 ｇ）第２のアレイ（１２０）から読み出された現状態累
    積コストに基づいて後続の次状態累積コストを計算する
    工程と、 ｈ）第１のアレイ（１００）の記憶レジスタに後続の次
    状態累積コストを記憶する工程と、 後続の次状態累積コストが、各状態について第１のアレ
    イ（１００）の記憶レジスタに記憶されるまで、前記工
    程ｆ），ｇ）及びｈ）を繰り返す工程とからなることを
    特徴とする方法。
  14. 【請求項１４】 第１のアレイに割り当てられた部分と
    第２のアレイに割り当てられた部分を有するメモリを含
    み、一連のシンボル瞬時において起こり得る各遷移につ
    いてより低い次状態累積コストを決定するためのビタビ
    デコーダにおいて、どの次状態コストを保持すべきか
    を決定する方法であって、 第１のアレイ（１００）の記憶レジスタから第１の現状
    態と関連する累積コストを読み出す工程と、 第１の現状態と関連する累積コストを第１のブランチメ
    トリック（１５２）に加算して第１の累積コスト候補
    （１６２または１６８）を生じせしめる工程と、 第１のアレイ（１００）の記憶レジスタから第２の現状
    態と関連する累積コストを読み出す工程と、 第２の現状態と関連する累積コストを第２のブランチメ
    トリック（１５２）に加算して第２の累積コスト候補
    （１６４または１７２）を生じせしめる工程と、 次状態累積コスト（１４６）として第１及び第２の累積
    コスト候補のうちの小さい方を選択する工程と、 前記次状態累積コスト（１４６）を前記第２のアレイ
    （１２０）の記憶レジスタに記憶する工程と、 前記第２のアレイ（１２０）を現状態累積コストを含む
    ものとして指定する工程と、 後続の次状態累積コストを計算する工程と、 前記後続の次状態累積コストを前記第１のアレイ（１０
    ０）の記憶レジスタに記憶する工程とからなることを特
    徴とする方法。
  15. 【請求項１５】 請求項１４記載のより低い次状態累積
    コストを確認する方法において、前記第１及び第２の累
    積コスト候補のうちの小さい方を次状態累積コストとし
    て選択する工程は、 第１の累積コスト候補（１６２または１６８）及び第２
    の累積コスト候補（１６４または１７２）の一方から他
    方を引いてその差（１８２）を生じせしめる工程と、 前記差のバイナリ表現の最上位ビット（１８４）を識別
    する工程と、 前記差のバイナリ表現の最上位ビット（１８４）により
    前記第１の累積コスト候補（１６８）及び第２の累積コ
    スト候補（１７２）のうちの小さい方を次状態累積コス
    トとして決定する工程とからなる方法。
  16. 【請求項１６】 請求項１４記載のより低い次状態累積
    コストを確認する方法において、さらに、現状態から次
    状態への遷移に対応するブランチメトリックを計算する
    工程を含む方法。
  17. 【請求項１７】 第１のレジスタアレイ（１００）と第
    ２のレジスタアレイ（１２０）を限定する記憶手段（１
    １０）と、 第１のアレイ（１００）のレジスタから現状態累積コス
    トを読み出すための手段（１４４，１０２，１９０）
    と、 次状態累積コストを計算するための手段（１５４，１５
    ０，１８０，１８４）と、 前記次状態累積コストを第２のアレイ（１２０）のレジ
    スタに記憶するための手段（１９０，２６，１４４，１
    ０２，１９０）と、 第１のアレイ（１００）のレジスタからの累積コストの
    後続の読み出しが次状態累積コストを読み出すように、
    第１のレジスタアレイ（１００）を前の第２のレジスタ
    アレイ（１２０）として指定し、第２のレジスタアレイ
    を前の第１のレジスタアレイとして指定するための手段
    （１４４）とからなることを特徴とする信号処理用集積
    回路。
  18. 【請求項１８】 請求項１７記載の集積回路において、
    記憶手段（１１０）はランダムアクセスメモリからなる
    集積回路。
  19. 【請求項１９】 請求項１７記載の集積回路において、
    計算手段（１５０または１８０）は加算器を含む集積回
    路。
  20. 【請求項２０】 請求項１７記載の集積回路において、
    計算手段（１８０，１８４，１９０）は比較器を構成す
    る集積回路。
  21. 【請求項２１】 請求項１７記載の集積回路において、
    指定手段はフリップフロップ８１４４）からなる集積回
    路。
  22. 【請求項２２】 通信システムのデジタル信号のデコー
    ド工程を含む前記信号の変換方法であって、どの次状態
    累積コストを保持すべきかを決定するときにメモリを効
    率的に利用する工程を含み、前記メモリは第１のアレイ
    に割り当てられた第１のレジスタ群と第２のアレイに割
    り当てられた第２のレジスタ群を有する変換方法におい
    て、 第１のアレイ（１００）から現状態累積コストを読み出
    す工程と、 前記現状態累積コストに基づいて次状態累積コストを計
    算する工程と、 前記次状態累積コストを第２のアレイ（１２０）の記憶
    レジスタに記憶する工程と、 前記第２のアレイ（１２０）を現状態累積コストを含む
    ものとして指定する工程とからなることを特徴とする変
    換方法。
JP27963594A 1993-11-16 1994-11-15 現状態／次状態レジスタの効率的利用 Expired - Fee Related JP3262250B2 (ja)

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
US153334 1993-11-16
US08/153,334 US5465275A (en) 1993-11-16 1993-11-16 Efficient utilization of present state/next state registers

Publications (2)

Publication Number Publication Date
JPH07191868A true JPH07191868A (ja) 1995-07-28
JP3262250B2 JP3262250B2 (ja) 2002-03-04

Family

ID=22546761

Family Applications (1)

Application Number Title Priority Date Filing Date
JP27963594A Expired - Fee Related JP3262250B2 (ja) 1993-11-16 1994-11-15 現状態／次状態レジスタの効率的利用

Country Status (5)

Country Link
US (2) US5465275A (ja)
EP (1) EP0653849A3 (ja)
JP (1) JP3262250B2 (ja)
KR (1) KR950016018A (ja)
TW (1) TW271518B (ja)

Cited By (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JPH08237144A (ja) * 1994-09-05 1996-09-13 Sgs Thomson Microelectron Sa ビタビアルゴリズムを実施するための信号処理回路

Families Citing this family (20)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
FR2718865B1 (fr) * 1994-04-15 1996-07-19 Texas Instruments France Procédé et dispositif à processeur de signaux numériques pour la mise en Óoeuvre d'un algorithme de Viterbi.
US5619514A (en) * 1994-12-29 1997-04-08 Lucent Technologies Inc. In-place present state/next state registers
JP3171772B2 (ja) * 1995-08-23 2001-06-04 沖電気工業株式会社 ビタビ復号方法及びビタビ復号装置
EP0782358A3 (en) 1995-12-29 1999-07-21 Lucent Technologies Inc. Mobile communicator
JPH09232973A (ja) * 1996-02-28 1997-09-05 Sony Corp ビタビ復号器
US5742622A (en) * 1996-03-12 1998-04-21 Discovision Associates Error detection and correction system for a stream of encoded data
US5802116A (en) * 1996-04-04 1998-09-01 Lucent Technologies Inc. Soft decision Viterbi decoding with large constraint lengths
GB9622540D0 (en) * 1996-10-30 1997-01-08 Discovision Ass Trackback for viterbi decoder
US6522696B1 (en) 1997-04-11 2003-02-18 Agere Systems Inc. Adaptive frequency correction in a wireless communications system, such as for GSM and IS54
KR100484127B1 (ko) * 1997-08-07 2005-06-16 삼성전자주식회사 비터비디코더
US6009128A (en) * 1997-09-08 1999-12-28 Lucent Technologies, Inc. Metric acceleration on dual MAC processor
EP0963049B1 (en) * 1998-06-01 2007-08-01 Her Majesty The Queen In Right Of Canada as represented by the Minister of Industry Interleaving with golden section increments
JP4071879B2 (ja) * 1998-12-09 2008-04-02 富士通株式会社 誤り検出器、この誤り検出器を備えた通信システム、および誤り検出方法
KR100331562B1 (ko) 1999-11-29 2002-04-06 윤종용 지연 동기 루프 회로 및 내부 클럭 신호 발생 방법
US6591395B1 (en) * 2000-06-18 2003-07-08 Silicon Integrated Systems Corporation Memory reduction techniques in a viterbi decoder
US7020830B2 (en) * 2001-12-24 2006-03-28 Agere Systems Inc. High speed add-compare-select operations for use in viterbi decoders
TWI228654B (en) * 2003-07-11 2005-03-01 Mediatek Inc Non-binary Viterbi data processing system and method
US20080152044A1 (en) * 2006-12-20 2008-06-26 Media Tek Inc. Veterbi decoding method for convolutionally encoded signal
DE102020120488A1 (de) 2019-12-20 2021-06-24 Taiwan Semiconductor Manufacturing Co. Ltd. Verfahren zur nachschlagtabellenfreien speicherreperatur
US11367500B2 (en) 2019-12-20 2022-06-21 Taiwan Semiconductor Manufacturing Company, Ltd. Method for LUT-free memory repair

Family Cites Families (11)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
NZ198844A (en) * 1980-11-14 1984-05-31 Plessey Overseas Digital information transmission: two dimensional code
GB8315363D0 (en) * 1983-06-03 1983-07-06 Gordon J A Decoding errorcorrecting codes
US4583078A (en) * 1984-11-13 1986-04-15 Communications Satellite Corporation Serial Viterbi decoder
US4868830A (en) * 1985-09-27 1989-09-19 California Institute Of Technology Method and apparatus for implementing a traceback maximum-likelihood decoder in a hypercube network
US4748626A (en) * 1987-01-28 1988-05-31 Racal Data Communications Inc. Viterbi decoder with reduced number of data move operations
US4979175A (en) * 1988-07-05 1990-12-18 Motorola, Inc. State metric memory arrangement for a viterbi decoder
FR2669445B1 (fr) * 1990-11-15 1993-01-08 Alcatel Radiotelephone Dispositif prevu pour le traitement de l'algorithme de viterbi comprenant un processeur et un operateur specialise.
KR930004862B1 (ko) * 1990-12-17 1993-06-09 삼성전자 주식회사 상태 평가량 기억장치
BE1004814A3 (nl) * 1991-05-08 1993-02-02 Bell Telephone Mfg Decodeerinrichting.
JP2917577B2 (ja) * 1991-05-30 1999-07-12 松下電器産業株式会社 演算装置
JP3120511B2 (ja) * 1991-11-21 2000-12-25 ソニー株式会社 ビタビ復号装置

Cited By (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JPH08237144A (ja) * 1994-09-05 1996-09-13 Sgs Thomson Microelectron Sa ビタビアルゴリズムを実施するための信号処理回路

Also Published As

Publication number Publication date
JP3262250B2 (ja) 2002-03-04
US5559837A (en) 1996-09-24
KR950016018A (ko) 1995-06-17
EP0653849A3 (en) 1997-01-29
EP0653849A2 (en) 1995-05-17
TW271518B (ja) 1996-03-01
US5465275A (en) 1995-11-07

Similar Documents

Publication Publication Date Title
JP3262250B2 (ja) 現状態／次状態レジスタの効率的利用
KR100426712B1 (ko) 비터비 복호기
US4979175A (en) State metric memory arrangement for a viterbi decoder
US5619514A (en) In-place present state/next state registers
JPH088762A (ja) ビタビ復号方法及びビタビ復号回路
JPH07212336A (ja) 減少長トレースバック
KR100371950B1 (ko) 비터비디코더용논리블록
JPS63161731A (ja) 逐次誤り訂正復号化装置
JP2798123B2 (ja) ビタビ復号装置
CN100550657C (zh) 维特比译码装置
HK1005007A (en) Efficient utilization of present state/next state registers
JP3260714B2 (ja) ビタビ復号化装置およびビタビ復号化方法
HK1006378A (en) In-place present state/next state registers
JPH04421B2 (ja)
JPH11186915A (ja) ビタビ復号装置
US6954155B2 (en) Data compression method and processor
KR19990076528A (ko) 비터비 알고리즘 처리를 위한 가산 비교 선택 고속화 장치 및방법
KR0183115B1 (ko) 비터비 디코더의 패스 메모리의 제어회로
JP3548949B2 (ja) ビタビ復号器
JP4144601B2 (ja) 演算処理回路、データ格納回路、演算処理装置、演算処理方法、データ格納方法、および、演算結果格納読み出し方法
JP3253906B2 (ja) データ処理装置及びデータ処理方法
JP2571384B2 (ja) シ−ケンシャル復号器
JPH10136212A (ja) 復号化装置
JPH08181869A (ja) 符号化装置及び復号化装置
KR100277467B1 (ko) 비터비 디코더

Legal Events

Date Code Title Description
A01 Written decision to grant a patent or to grant a registration (utility model)

Free format text: JAPANESE INTERMEDIATE CODE: A01

Effective date: 20011114

LAPS Cancellation because of no payment of annual fees