JP3343217B2 - ２ビットトレースバック符号化に対するビタビ比較・選択動作 - Google Patents
２ビットトレースバック符号化に対するビタビ比較・選択動作Info
- Publication number
- JP3343217B2 JP3343217B2 JP25315098A JP25315098A JP3343217B2 JP 3343217 B2 JP3343217 B2 JP 3343217B2 JP 25315098 A JP25315098 A JP 25315098A JP 25315098 A JP25315098 A JP 25315098A JP 3343217 B2 JP3343217 B2 JP 3343217B2
- Authority
- JP
- Japan
- Prior art keywords
- metric
- pns
- bit
- extremum
- traceback
- 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.)
- Expired - Fee Related
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/4161—Sequence estimation, i.e. using statistical methods for the reconstruction of the original codes using the Viterbi algorithm or Viterbi processors implementing path management
- H03M13/4169—Sequence estimation, i.e. using statistical methods for the reconstruction of the original codes using the Viterbi algorithm or Viterbi processors implementing path management using traceback
Landscapes
- Physics & Mathematics (AREA)
- Probability & Statistics with Applications (AREA)
- Engineering & Computer Science (AREA)
- Theoretical Computer Science (AREA)
- Error Detection And Correction (AREA)
Description
【０００１】
【発明の分野】本発明は、一般的にはビタビ復号、より
詳細には、２ビットトレースバック符号化を行なうため
の比較・選択動作に関する。
詳細には、２ビットトレースバック符号化を行なうため
の比較・選択動作に関する。
【０００２】
【従来の技術】ビタビ復号器は、フォワードエラー修正
を行なう最尤復号器である。ビタビ復号は、符号化され
たシンボルのシーケンス、例えば、ビット流の復号に用
いられる。ビット流は、システム内の様々な媒体を通じ
て伝送される符号化された情報を表わし、セットのビッ
トは、各々一つのシンボル瞬間(symbol instant)を表
す。ビタビ復号は、任意の通信チャネルを通じてのデジ
タル通信、例えば、衛星から地上、セルラ電話、コンピ
ュータからディスク、モデムからモデム、その他のデジ
タル通信において採用されている。ビタビ復号器は、ハ
ードウエアとしてのマイクロプロセッサ、マイクロコン
トローラ、あるいは、デジタル信号プロセッサ上に実現
されている。ビテビ復号は周知であり、この用途につい
ては、合衆国第5,490,178 号、5,454,014 号、5,559,83
7 号、5,465,275 号、5,471,500 号において開示されて
いるため、これらを参照されたい。
を行なう最尤復号器である。ビタビ復号は、符号化され
たシンボルのシーケンス、例えば、ビット流の復号に用
いられる。ビット流は、システム内の様々な媒体を通じ
て伝送される符号化された情報を表わし、セットのビッ
トは、各々一つのシンボル瞬間(symbol instant)を表
す。ビタビ復号は、任意の通信チャネルを通じてのデジ
タル通信、例えば、衛星から地上、セルラ電話、コンピ
ュータからディスク、モデムからモデム、その他のデジ
タル通信において採用されている。ビタビ復号器は、ハ
ードウエアとしてのマイクロプロセッサ、マイクロコン
トローラ、あるいは、デジタル信号プロセッサ上に実現
されている。ビテビ復号は周知であり、この用途につい
ては、合衆国第5,490,178 号、5,454,014 号、5,559,83
7 号、5,465,275 号、5,471,500 号において開示されて
いるため、これらを参照されたい。
【０００３】ビタビ復号器の復号動作は、４つのステッ
プ、つまり（１）ブランチメトリック(branch metric)
および経路メトリック(path metric) の計算、（２）比
較・選択動作、（３）最小あるいは最大の状態コストの
決定、および（４）トレースバック動作、からなる。復
号プロセスにおいて、ビタビ復号器は、各シンボル瞬間
において、可能なビットシーケンスのシーケンスを遡る
方向に動作し、伝送された可能性の最も高い１ビットシ
ーケンスを決定する。１つのシンボル瞬間における状
態、つまり、現在の状態から、次の後続のシンボル瞬間
における状態、つまり、次の状態への可能な遷移には限
度がある。現在の状態から次の状態への可能な各遷移
は、グラフ的に示すことができ、ブランチと定義され
る。相互接続されたブランチのシーケンスは経路と定義
される。各状態は、ビット流内の次の一つあるいは複数
のビットを受信したとき、ある限られた個数の次の状態
にしか遷移できない。このため、幾つかのブランチは、
生き残ってある経路の一部となるが、他の幾つかのブラ
ンチは、ある経路の一部となることはできず、生き残る
ことはできない。生き残ることが許されない遷移あるい
はブランチを排除することで、残すべき最尤経路を決定
する計算の効率が改善される。これを達成するために、
ビタビ復号器は、典型的には、各ブランチと関連するブ
ランチメトリックを計算し、このブランチメトリックを
用いて、どの経路を残し、どの経路を排除すべきを決定
する。
プ、つまり（１）ブランチメトリック(branch metric)
および経路メトリック(path metric) の計算、（２）比
較・選択動作、（３）最小あるいは最大の状態コストの
決定、および（４）トレースバック動作、からなる。復
号プロセスにおいて、ビタビ復号器は、各シンボル瞬間
において、可能なビットシーケンスのシーケンスを遡る
方向に動作し、伝送された可能性の最も高い１ビットシ
ーケンスを決定する。１つのシンボル瞬間における状
態、つまり、現在の状態から、次の後続のシンボル瞬間
における状態、つまり、次の状態への可能な遷移には限
度がある。現在の状態から次の状態への可能な各遷移
は、グラフ的に示すことができ、ブランチと定義され
る。相互接続されたブランチのシーケンスは経路と定義
される。各状態は、ビット流内の次の一つあるいは複数
のビットを受信したとき、ある限られた個数の次の状態
にしか遷移できない。このため、幾つかのブランチは、
生き残ってある経路の一部となるが、他の幾つかのブラ
ンチは、ある経路の一部となることはできず、生き残る
ことはできない。生き残ることが許されない遷移あるい
はブランチを排除することで、残すべき最尤経路を決定
する計算の効率が改善される。これを達成するために、
ビタビ復号器は、典型的には、各ブランチと関連するブ
ランチメトリックを計算し、このブランチメトリックを
用いて、どの経路を残し、どの経路を排除すべきを決定
する。
【０００４】ブランチメトリックが、各シンボル瞬間に
おいて、可能な各ブランチに対して計算される。各経路
は、関連するメトリック、つまり、累積コストを持ち、
この累積コストが、各シンボル瞬間において更新され
る。可能な各遷移に対して、次の状態に対する累積コス
トが、あるブランチメトリックとそのブランチメトリッ
クの現在の状態のオリジンにおける経路累積コストとの
総和として計算される。最大あるいは最小の極値が選択
される。
おいて、可能な各ブランチに対して計算される。各経路
は、関連するメトリック、つまり、累積コストを持ち、
この累積コストが、各シンボル瞬間において更新され
る。可能な各遷移に対して、次の状態に対する累積コス
トが、あるブランチメトリックとそのブランチメトリッ
クの現在の状態のオリジンにおける経路累積コストとの
総和として計算される。最大あるいは最小の極値が選択
される。
【０００５】一つのシンボル瞬間から次のシンボル瞬間
への遷移において、いくつかのブランチ、従って、いく
つかの経路が生き残り、このため、これら生き残った経
路を遡るトレースバック動作を採用することで、伝送さ
れた可能性の最も高い一つあるいは複数のビットシーケ
ンスが選択される。シーケンスのシンボル瞬間は、トレ
リス(trellis) と呼ばれる配列にて表される。ある与え
られたシンボル瞬間から開始する極値累積コストを持つ
経路を識別する動作は、トレースバック動作と呼ばれ
る。極値累積コストを持つ経路がトレリスを遡って延び
るシンボル瞬間の数によって、トレースバック動作の長
さ、あるいは、深さが定まる。トレースバック動作の終
端において、極値累積コストから開始する生き残った経
路と関連するトレリス内の個々の状態が、一つあるいは
複数のビットに翻訳され、これらが、そのシンボル瞬間
において伝送された可能性が最も高いものとみなされ
る。これらビットあるいはグループのビットから、復号
されたシンボルが形成される。
への遷移において、いくつかのブランチ、従って、いく
つかの経路が生き残り、このため、これら生き残った経
路を遡るトレースバック動作を採用することで、伝送さ
れた可能性の最も高い一つあるいは複数のビットシーケ
ンスが選択される。シーケンスのシンボル瞬間は、トレ
リス(trellis) と呼ばれる配列にて表される。ある与え
られたシンボル瞬間から開始する極値累積コストを持つ
経路を識別する動作は、トレースバック動作と呼ばれ
る。極値累積コストを持つ経路がトレリスを遡って延び
るシンボル瞬間の数によって、トレースバック動作の長
さ、あるいは、深さが定まる。トレースバック動作の終
端において、極値累積コストから開始する生き残った経
路と関連するトレリス内の個々の状態が、一つあるいは
複数のビットに翻訳され、これらが、そのシンボル瞬間
において伝送された可能性が最も高いものとみなされ
る。これらビットあるいはグループのビットから、復号
されたシンボルが形成される。
【０００６】各シンボル瞬間において単一のビットが送
信されるビタビ復号の用途においては、２個の可能な現
在の状態が単一の次の状態に遷移、即ちブランチする。
この２個の可能なブランチのどちらがある与えられた次
の状態に遷移したかは、単一のビットのみで一意に決定
でき、単一のビットで十分である。各シンボル瞬間にお
いて２個のビットが送信されるビタビ復号の用途に対し
ては、単一の次の状態に遷移することができる４個の可
能な現在の状態が存在する。この場合は、単一の次の状
態に遷移可能な４個の現在の状態が存在し、これら４個
の可能なブランチのどれがある与えられた次の状態に遷
移したかを一意に決定するためには、２個のビットが必
要となる。各シンボル瞬間において２個のビットが送信
される用途としては、これに限られるものではないが、
ｖ．３４モデム技術、時分割マルチアクセス（TDMA）標
準ＩＳ−５４、ＩＳ−１３６等が含まれる。
信されるビタビ復号の用途においては、２個の可能な現
在の状態が単一の次の状態に遷移、即ちブランチする。
この２個の可能なブランチのどちらがある与えられた次
の状態に遷移したかは、単一のビットのみで一意に決定
でき、単一のビットで十分である。各シンボル瞬間にお
いて２個のビットが送信されるビタビ復号の用途に対し
ては、単一の次の状態に遷移することができる４個の可
能な現在の状態が存在する。この場合は、単一の次の状
態に遷移可能な４個の現在の状態が存在し、これら４個
の可能なブランチのどれがある与えられた次の状態に遷
移したかを一意に決定するためには、２個のビットが必
要となる。各シンボル瞬間において２個のビットが送信
される用途としては、これに限られるものではないが、
ｖ．３４モデム技術、時分割マルチアクセス（TDMA）標
準ＩＳ−５４、ＩＳ−１３６等が含まれる。
【０００７】当分野においては、４個のメトリックを比
較し、極値メトリックを選択することに加えて、現在の
状態から次の状態に遷移した生き残ったブランチを一意
に識別するペアのトレースバックビットを生成および格
納するための効率的な方法が必要とされている。
較し、極値メトリックを選択することに加えて、現在の
状態から次の状態に遷移した生き残ったブランチを一意
に識別するペアのトレースバックビットを生成および格
納するための効率的な方法が必要とされている。
【０００８】
【発明の概要】本発明によるデジタル通信システムを動
作する方法は、第１、第２、第３、および第４のメトリ
ックを生成する。第１の中間極値がこれら２個のメトリ
ックから選択され、第２の中間極値が他の２個のメトリ
ックから選択される。そして、これら第１と第２の中間
極値から極値が選択される。加えて、生き残ったブラン
チに対応するペアのトレースバックビットが生成および
格納される。
作する方法は、第１、第２、第３、および第４のメトリ
ックを生成する。第１の中間極値がこれら２個のメトリ
ックから選択され、第２の中間極値が他の２個のメトリ
ックから選択される。そして、これら第１と第２の中間
極値から極値が選択される。加えて、生き残ったブラン
チに対応するペアのトレースバックビットが生成および
格納される。
【０００９】
【発明の詳細な記述】図２は、４個の可能な現在の状態
が単一の次の状態に遷移できる一例としての１６状態ビ
タビバタフライにおける現在の状態と次の状態の図の一
部分を示す。２ビット入力００を右にシフトしたとき、
第１の４個の現在の状態Ｓ0 、００００、Ｓ1 、０００
１、Ｓ2 、００１０、Ｓ3 、００１１のいずれも、現在
の状態の最後の２個のビットがシフトアウトされると
き、次の状態ＮＳ0 、００００に遷移する可能性を持
つ。図面には全ての可能な遷移は示されないが、１６個
の次の状態は、各々、２ビット入力の全ての組合せを受
信したとき、各々、次の状態に遷移することができる４
個の可能な現在の状態を持つ。換言すれば、１６個の次
の状態は、各々、２ビット入力の全ての組合せを受信し
たとに、それへの現在の状態の４個の遷移を持つ。こう
して、１６状態の実施例においては、図２に示すよう
に、現在の状態から次の状態への６４個の可能なブラン
チ遷移が存在するが、ここには、これら６４個の可能な
ブランチの内の１２個のブランチのみが示される。
が単一の次の状態に遷移できる一例としての１６状態ビ
タビバタフライにおける現在の状態と次の状態の図の一
部分を示す。２ビット入力００を右にシフトしたとき、
第１の４個の現在の状態Ｓ0 、００００、Ｓ1 、０００
１、Ｓ2 、００１０、Ｓ3 、００１１のいずれも、現在
の状態の最後の２個のビットがシフトアウトされると
き、次の状態ＮＳ0 、００００に遷移する可能性を持
つ。図面には全ての可能な遷移は示されないが、１６個
の次の状態は、各々、２ビット入力の全ての組合せを受
信したとき、各々、次の状態に遷移することができる４
個の可能な現在の状態を持つ。換言すれば、１６個の次
の状態は、各々、２ビット入力の全ての組合せを受信し
たとに、それへの現在の状態の４個の遷移を持つ。こう
して、１６状態の実施例においては、図２に示すよう
に、現在の状態から次の状態への６４個の可能なブラン
チ遷移が存在するが、ここには、これら６４個の可能な
ブランチの内の１２個のブランチのみが示される。
【００１０】各ブランチは、ｍijと呼ばれる関連するブ
ランチメトリックを持つ。ここで、ｉは、現在の状態を
表し、ｊは、各ブランチの終端における次の状態を表
す。現在の状態は、各々、ｉ番目の現在の状態と関連す
る累積コストＰＳi を持つ（ここで、ｉ＝０、１、
２、．．．１５）。累積コストＰＳi は、その現在の状
態に至るまでのある経路内の全てのブランチの内の生き
残ったブランチと関連するブランチメトリックの総和で
ある。次の状態に対する累積コストメトリックＮＳ
ｊは、ｉ番目の現在の状態と関連する現在の状態の累積
コストＰＳｉ と、ブランチメトリックｍijの一つとの
総和であるが、これは、例えば、ユークリッド距離ある
いはハミング距離（しばしば、マンハッタン距離として
も知られている）に基づく。
ランチメトリックを持つ。ここで、ｉは、現在の状態を
表し、ｊは、各ブランチの終端における次の状態を表
す。現在の状態は、各々、ｉ番目の現在の状態と関連す
る累積コストＰＳi を持つ（ここで、ｉ＝０、１、
２、．．．１５）。累積コストＰＳi は、その現在の状
態に至るまでのある経路内の全てのブランチの内の生き
残ったブランチと関連するブランチメトリックの総和で
ある。次の状態に対する累積コストメトリックＮＳ
ｊは、ｉ番目の現在の状態と関連する現在の状態の累積
コストＰＳｉ と、ブランチメトリックｍijの一つとの
総和であるが、これは、例えば、ユークリッド距離ある
いはハミング距離（しばしば、マンハッタン距離として
も知られている）に基づく。
【００１１】ある与えられた次の状態、例えば、次の状
態００００に終端する４個のブランチメトリックｍijを
計算し、これを、現在の状態の累積コストに加算するこ
とで、４個の潜在的な次の状態のコストが生成され、こ
れらが比較される。極値（最大あるいは最小）を示す潜
在的な次の状態のコストが、この比較動作において、極
値を示す潜在的な次の状態のコストメトリックが終端す
る次の状態と関連する次の状態のコストとして選択され
る。極値メトリックと関連する現在の状態から次の状態
への遷移によって、ある生き残った経路内のあるブラン
チが構成される。極値メトリックが、生き残ったブラン
チの終端における次の状態と関連する次の状態のコスト
となる。現在の状態からの２ビットがシフトアウトさ
れ、トレースバックビットとして格納され、生き残った
ブランチのトレースバック経路を再構成するために用い
られる。全ての現在の状態に対して、類似の計算が遂行
され、これに基づいて全ての次の状態の累積コストが更
新され、次の各状態と関連して２個のトレースバックビ
ットが格納される。こうして、メトリックｍ00が極値の
部分を構成する場合は、００が、２ビットトレースバッ
ク対のビットとして格納され、ｍ10が極値の部分を構成
する場合は、０１が、２ビットトレースバック対のビッ
トとして格納され、ｍ20が極値の部分を構成する場合
は、１０が、２ビットトレースバック対のビットして格
納され、ｍ30が極値の部分を構成する場合は、１１が、
２ビットトレースバック対のビットとして格納される。
態００００に終端する４個のブランチメトリックｍijを
計算し、これを、現在の状態の累積コストに加算するこ
とで、４個の潜在的な次の状態のコストが生成され、こ
れらが比較される。極値（最大あるいは最小）を示す潜
在的な次の状態のコストが、この比較動作において、極
値を示す潜在的な次の状態のコストメトリックが終端す
る次の状態と関連する次の状態のコストとして選択され
る。極値メトリックと関連する現在の状態から次の状態
への遷移によって、ある生き残った経路内のあるブラン
チが構成される。極値メトリックが、生き残ったブラン
チの終端における次の状態と関連する次の状態のコスト
となる。現在の状態からの２ビットがシフトアウトさ
れ、トレースバックビットとして格納され、生き残った
ブランチのトレースバック経路を再構成するために用い
られる。全ての現在の状態に対して、類似の計算が遂行
され、これに基づいて全ての次の状態の累積コストが更
新され、次の各状態と関連して２個のトレースバックビ
ットが格納される。こうして、メトリックｍ00が極値の
部分を構成する場合は、００が、２ビットトレースバッ
ク対のビットとして格納され、ｍ10が極値の部分を構成
する場合は、０１が、２ビットトレースバック対のビッ
トとして格納され、ｍ20が極値の部分を構成する場合
は、１０が、２ビットトレースバック対のビットして格
納され、ｍ30が極値の部分を構成する場合は、１１が、
２ビットトレースバック対のビットとして格納される。
【００１２】ある与えられた次の状態と関連する４個の
ブランチメトリックを計算し、これを、そのブランチメ
トリックの原点(origin)と関連する各現在の状態のコス
トに加算することで、４個の潜在的な次の状態のコスト
ＰＮＳ00、ＰＮＳ01、ＰＮＳ02、ＰＮＳ03が生成され
る。これら４個の潜在的な次の状態のコストメトリック
が、図１に示すデータ演算ユニット２０、例えば、マイ
クロプロセッサ、マイクロコントローラあるいはデジタ
ル信号プロセッサ内で系統的に比較され、これによっ
て、これら４個の潜在的な次の状態のコストから極値が
選択される。メトリックＰＮＳ00、ＰＮＳ01、ＰＮ
Ｓ02、ＰＮＳ03が当分野において周知の方法にて計算さ
れ、レジスタファイル２４の、それぞれ、レジスタａ
０、ａ１、ａ２、ａ３として示される４個のレジスタ２
２内に格納される。
ブランチメトリックを計算し、これを、そのブランチメ
トリックの原点(origin)と関連する各現在の状態のコス
トに加算することで、４個の潜在的な次の状態のコスト
ＰＮＳ00、ＰＮＳ01、ＰＮＳ02、ＰＮＳ03が生成され
る。これら４個の潜在的な次の状態のコストメトリック
が、図１に示すデータ演算ユニット２０、例えば、マイ
クロプロセッサ、マイクロコントローラあるいはデジタ
ル信号プロセッサ内で系統的に比較され、これによっ
て、これら４個の潜在的な次の状態のコストから極値が
選択される。メトリックＰＮＳ00、ＰＮＳ01、ＰＮ
Ｓ02、ＰＮＳ03が当分野において周知の方法にて計算さ
れ、レジスタファイル２４の、それぞれ、レジスタａ
０、ａ１、ａ２、ａ３として示される４個のレジスタ２
２内に格納される。
【００１３】レジスタａ０からのメトリックＰＮＳ
00が、第１の入力として、ライン２８を介して、演算論
理ユニット（Ａrithmetic Ｌogic Ｕnit：ＡＬＵ）２６
に供給され、レジスタａ１からのメトリックＰＮＳ
01が、第２の入力として、ライン３０を介して、ＡＬＵ
２６に供給される。ＡＬＵ２６は、この２個の入力を比
較する。例えば、差を計算する。そして、ＡＬＵ２６か
らの差の符号の標識が、ライン３２を通じて、排他的論
理和ゲート３４への第１の入力として供給される。排他
的論理和ゲート３４への第２の入力は、１ビット入力セ
レクタ３３に接続される。セレクタ３３は、第１と第２
の状態の一つを取り、ＡＬＵ２６内で比較されている２
個の入力の内の小さな方か大きな方のいずれかを選択す
る。ＡＬＵ２６への入力の小さな方の選択は、最小メト
リックの選択に対応し、ＡＬＵ２６への入力の大きな方
の選択は、最大メトリックの選択に対応する。数が表現
される方法に依存して、最小／最大セレクタは、第１の
状態、例えば、論理１において、ＡＬＵ２６への入力の
小さな方を選択し、第２の状態、例えば、論理０におい
て、ＡＬＵ２６への入力の大きな方を選択する。排他的
ＲＯゲート３４の出力は、選択入力３６として、マルチ
プレクサ３８に供給される。マルチプレクサ３８は、Ａ
ＬＵ２６と同一の入力を受信し、２個のメトリックＰＮ
Ｓ00あるいはＰＮＳ01の一つを、第１の中間極値として
選択し、選択された第１の中間極値をレジスタａ０内に
格納する。このようにして、第１と第２のメトリックが
互いに比較され、第１の中間極値メトリックが選択され
る。
00が、第１の入力として、ライン２８を介して、演算論
理ユニット（Ａrithmetic Ｌogic Ｕnit：ＡＬＵ）２６
に供給され、レジスタａ１からのメトリックＰＮＳ
01が、第２の入力として、ライン３０を介して、ＡＬＵ
２６に供給される。ＡＬＵ２６は、この２個の入力を比
較する。例えば、差を計算する。そして、ＡＬＵ２６か
らの差の符号の標識が、ライン３２を通じて、排他的論
理和ゲート３４への第１の入力として供給される。排他
的論理和ゲート３４への第２の入力は、１ビット入力セ
レクタ３３に接続される。セレクタ３３は、第１と第２
の状態の一つを取り、ＡＬＵ２６内で比較されている２
個の入力の内の小さな方か大きな方のいずれかを選択す
る。ＡＬＵ２６への入力の小さな方の選択は、最小メト
リックの選択に対応し、ＡＬＵ２６への入力の大きな方
の選択は、最大メトリックの選択に対応する。数が表現
される方法に依存して、最小／最大セレクタは、第１の
状態、例えば、論理１において、ＡＬＵ２６への入力の
小さな方を選択し、第２の状態、例えば、論理０におい
て、ＡＬＵ２６への入力の大きな方を選択する。排他的
ＲＯゲート３４の出力は、選択入力３６として、マルチ
プレクサ３８に供給される。マルチプレクサ３８は、Ａ
ＬＵ２６と同一の入力を受信し、２個のメトリックＰＮ
Ｓ00あるいはＰＮＳ01の一つを、第１の中間極値として
選択し、選択された第１の中間極値をレジスタａ０内に
格納する。このようにして、第１と第２のメトリックが
互いに比較され、第１の中間極値メトリックが選択され
る。
【００１４】同様にして、レジスタａ２からのメトリッ
クＰＮＳ02が、第１の入力として、ライン２８を介し
て、ＡＬＵ２６に供給され、レジスタａ３からのメトリ
ックＰＮＳ03が、第２の入力として、ライン３０を介し
て、ＡＬＵ２６に供給される。ＡＬＵ２６は、この２個
の入力を比較する。例えば、差を計算する。マルチプレ
クサ３８は、これら２個のメトリックＰＮＳ02あるいは
ＰＮＳ03の一つを、第２の中間極値として選択し、第２
の中間極値をライン４０を通じて、レジスタファイル２
４に供給し、これが、レジスタａ２内に格納される。こ
のようにして、第３と第４のメトリックが互いに比較さ
れ、第２の中間極値メトリックが選択される。
クＰＮＳ02が、第１の入力として、ライン２８を介し
て、ＡＬＵ２６に供給され、レジスタａ３からのメトリ
ックＰＮＳ03が、第２の入力として、ライン３０を介し
て、ＡＬＵ２６に供給される。ＡＬＵ２６は、この２個
の入力を比較する。例えば、差を計算する。マルチプレ
クサ３８は、これら２個のメトリックＰＮＳ02あるいは
ＰＮＳ03の一つを、第２の中間極値として選択し、第２
の中間極値をライン４０を通じて、レジスタファイル２
４に供給し、これが、レジスタａ２内に格納される。こ
のようにして、第３と第４のメトリックが互いに比較さ
れ、第２の中間極値メトリックが選択される。
【００１５】レジスタａ０からの第１の中間極値は、第
１の入力として、ライン２８を通じて、ＡＬＵ２６に供
給され、レジスタａ２からの第２の中間極値は、第２の
入力として、ライン３０を通じて、ＡＬＵ２６に供給さ
れる。ＡＬＵ２６は、この２個の中間極値を比較する。
例えば、差を計算する。ＡＬＵ２６からの符号標識が、
ライン３２を通じて、排他的論理和ゲート３４への一つ
の入力として供給される。そして、上述と同一の状態を
持つ最小／最大セレクタを用いて選択された排他的論理
和ゲート３４からの出力が、マルチプレクサ３８に選択
入力として供給される。マルチプレクサ３８は、第１と
第２の中間極値の一つを極値として選択し、この極値
を、ライン４０を通じて、レジスタファイル２４に供給
し、これは、レジスタａ０内に格納される。こうして、
第１と第２の中間極値が比較され、極値が選択される。
１の入力として、ライン２８を通じて、ＡＬＵ２６に供
給され、レジスタａ２からの第２の中間極値は、第２の
入力として、ライン３０を通じて、ＡＬＵ２６に供給さ
れる。ＡＬＵ２６は、この２個の中間極値を比較する。
例えば、差を計算する。ＡＬＵ２６からの符号標識が、
ライン３２を通じて、排他的論理和ゲート３４への一つ
の入力として供給される。そして、上述と同一の状態を
持つ最小／最大セレクタを用いて選択された排他的論理
和ゲート３４からの出力が、マルチプレクサ３８に選択
入力として供給される。マルチプレクサ３８は、第１と
第２の中間極値の一つを極値として選択し、この極値
を、ライン４０を通じて、レジスタファイル２４に供給
し、これは、レジスタａ０内に格納される。こうして、
第１と第２の中間極値が比較され、極値が選択される。
【００１６】２ビットトレースバック対のビットも中間
極値として構成され、これら中間極値が比較され、極値
が選択される。２ビットトレースバック対を構成および
格納する回路を図３に示す。
極値として構成され、これら中間極値が比較され、極値
が選択される。２ビットトレースバック対を構成および
格納する回路を図３に示す。
【００１７】ＡＬＵ２６内で第１と第２の潜在的な次の
状態のコストメトリックが比較されるとき、第１と第２
の潜在的な次の状態のコストメトリックと関連する各ブ
ランチのオリジンの現在の状態の最下位ビット（ＬＳ
Ｂ）は互いに異なる。このため、このＬＳＢは、第１の
中間極値の現在の状態のオリジンを一意に決定する。こ
のＬＳＢは、第１の潜在的な第１のビット位置のトレー
スバックビットであり、これが図３に示すマルチビット
レジスタ５０のＬＢＳ内に格納される。このようにし
て、対応する第１の潜在的な第１のビット位置のトレー
スバックビットが２個の潜在的な次の状態のコストメト
リックのどちらが第１の中間極値として選択されたを識
別するために選択される。
状態のコストメトリックが比較されるとき、第１と第２
の潜在的な次の状態のコストメトリックと関連する各ブ
ランチのオリジンの現在の状態の最下位ビット（ＬＳ
Ｂ）は互いに異なる。このため、このＬＳＢは、第１の
中間極値の現在の状態のオリジンを一意に決定する。こ
のＬＳＢは、第１の潜在的な第１のビット位置のトレー
スバックビットであり、これが図３に示すマルチビット
レジスタ５０のＬＢＳ内に格納される。このようにし
て、対応する第１の潜在的な第１のビット位置のトレー
スバックビットが２個の潜在的な次の状態のコストメト
リックのどちらが第１の中間極値として選択されたを識
別するために選択される。
【００１８】ＡＬＵ２６内で第３と第４の潜在的な次の
状態のコストメトリックが比較されるとき、第３と第４
の潜在的な次の状態のコストメトリックと関連する各ブ
ランチのオリジンの現在の状態のＬＳＢは互いに異な
る。上述と同様に、第３と第４の潜在的な次の状態のコ
ストメトリックと関連する各ブランチのオリジンの現在
の状態のＬＳＢは、第２の中間極値の現在の状態のオリ
ジンを一意に決定する。このＬＳＢは、第２の潜在的な
第１のビット位置のトレースバックビットであり、これ
が図３に示すマルチビットレジスタ５０のＬＢＳ内に格
納され、前に格納されているＬＳＢは、レジスタ５０の
第２のビット位置にシフトされる。こうして、対応する
第２の潜在的な第１のビット位置のトレースバックビッ
トが２個の潜在的な次の状態のコストメトリックのどち
らが第２の中間極値として選択されたかを識別するため
に選択される。
状態のコストメトリックが比較されるとき、第３と第４
の潜在的な次の状態のコストメトリックと関連する各ブ
ランチのオリジンの現在の状態のＬＳＢは互いに異な
る。上述と同様に、第３と第４の潜在的な次の状態のコ
ストメトリックと関連する各ブランチのオリジンの現在
の状態のＬＳＢは、第２の中間極値の現在の状態のオリ
ジンを一意に決定する。このＬＳＢは、第２の潜在的な
第１のビット位置のトレースバックビットであり、これ
が図３に示すマルチビットレジスタ５０のＬＢＳ内に格
納され、前に格納されているＬＳＢは、レジスタ５０の
第２のビット位置にシフトされる。こうして、対応する
第２の潜在的な第１のビット位置のトレースバックビッ
トが２個の潜在的な次の状態のコストメトリックのどち
らが第２の中間極値として選択されたかを識別するため
に選択される。
【００１９】ＡＬＵ２６内で第１と第２の中間極値が比
較されるとき、第１と第２の中間極値と関連する各ブラ
ンチのオリジンの現在の状態のＬＳＢに隣接するビット
（現在の状態の第２のビット）は互いに異なる。このた
め、この現在の状態の第２のビットは、極値として選択
された中間極値が、第１と第２の潜在的な次の状態のコ
ストメトリックから選択されたのか、あるいは、第３と
第４の潜在的な次の状態のコストメトリックから選択さ
れたのかを一意に決定することができる。このビット
は、２ビットトレースバック対の構成においては、第２
のビット位置のトレースバックビットと呼ばれ、レジス
タ５２の第２のビットに供給される。こうして、対応す
る第２のビット位置のトレースバックビットが、２個の
中間極値のどちらが極値として選択されたかを識別する
ために選択される。この第２のビット位置のトレースバ
ックビットは、以下に説明するように、トレースバック
ビット対の最上位ビットとして供給される。
較されるとき、第１と第２の中間極値と関連する各ブラ
ンチのオリジンの現在の状態のＬＳＢに隣接するビット
（現在の状態の第２のビット）は互いに異なる。このた
め、この現在の状態の第２のビットは、極値として選択
された中間極値が、第１と第２の潜在的な次の状態のコ
ストメトリックから選択されたのか、あるいは、第３と
第４の潜在的な次の状態のコストメトリックから選択さ
れたのかを一意に決定することができる。このビット
は、２ビットトレースバック対の構成においては、第２
のビット位置のトレースバックビットと呼ばれ、レジス
タ５２の第２のビットに供給される。こうして、対応す
る第２のビット位置のトレースバックビットが、２個の
中間極値のどちらが極値として選択されたかを識別する
ために選択される。この第２のビット位置のトレースバ
ックビットは、以下に説明するように、トレースバック
ビット対の最上位ビットとして供給される。
【００２０】レジスタ５２は、マルチビットシフトレジ
スタであり、複数のトレースバックビットを格納する。
マルチプレクサ５４への選択入力が第１の論理状態、例
えば、０に設定されているときは、単一のトレースバッ
クビットがレジスタ５２のＬＳＢに格納される。新たな
トレースバックビットが生成される度に、シフトレジス
タ５２は、前に格納されているビットを１位置だけ（図
３の左方向に）シフトし、新たなトレースバックビット
をＬＳＢ内に格納する。この１ビットトレースバックの
動作モードは、現在の状態から次の状態への２個の可能
な遷移が存在するときに有用である。ユーザによって決
定される十分なレジスタ位置が満たされると、シフトレ
ジスタ５２内に格納されたこれらトレースバックビット
は、当分野において周知の方法にてメモリ内に書込まれ
る。
スタであり、複数のトレースバックビットを格納する。
マルチプレクサ５４への選択入力が第１の論理状態、例
えば、０に設定されているときは、単一のトレースバッ
クビットがレジスタ５２のＬＳＢに格納される。新たな
トレースバックビットが生成される度に、シフトレジス
タ５２は、前に格納されているビットを１位置だけ（図
３の左方向に）シフトし、新たなトレースバックビット
をＬＳＢ内に格納する。この１ビットトレースバックの
動作モードは、現在の状態から次の状態への２個の可能
な遷移が存在するときに有用である。ユーザによって決
定される十分なレジスタ位置が満たされると、シフトレ
ジスタ５２内に格納されたこれらトレースバックビット
は、当分野において周知の方法にてメモリ内に書込まれ
る。
【００２１】マルチプレクサ５４への選択入力が第２の
論理状態、例えば、１に設定されているときは、対のト
レースバックビットがシフトレジスタ５２の２個の最下
位ビットに格納される。２ビットトレースバック対は、
各々、最初は、シフトレジスタ５２の２個の最下位ビッ
トに格納される。もう１個の２ビットトレースバック対
が生成されると、現存の２ビットトレースバック対は、
別の前に格納されている２ビットトレースバック対と共
に、シフトレジスタ５２内において、２つのレジスタだ
け左にシフトされ、最も最近の２ビットトレースバック
対がシフトレジスタ５２の２つの最下位ビット位置に格
納される。この２ビットトレースバックの動作モード
は、現在の状態から次の状態への４個の可能な遷移が存
在するときに有用である。十分なレジスタ位置が満たさ
れると、シフトレジスタ５２内のこれらトレースバック
ビットの対はメモリ内に書込まれる。
論理状態、例えば、１に設定されているときは、対のト
レースバックビットがシフトレジスタ５２の２個の最下
位ビットに格納される。２ビットトレースバック対は、
各々、最初は、シフトレジスタ５２の２個の最下位ビッ
トに格納される。もう１個の２ビットトレースバック対
が生成されると、現存の２ビットトレースバック対は、
別の前に格納されている２ビットトレースバック対と共
に、シフトレジスタ５２内において、２つのレジスタだ
け左にシフトされ、最も最近の２ビットトレースバック
対がシフトレジスタ５２の２つの最下位ビット位置に格
納される。この２ビットトレースバックの動作モード
は、現在の状態から次の状態への４個の可能な遷移が存
在するときに有用である。十分なレジスタ位置が満たさ
れると、シフトレジスタ５２内のこれらトレースバック
ビットの対はメモリ内に書込まれる。
【００２２】マルチプレクサ５６の第１の入力５８は、
レジスタ５０のＬＳＢに結合され、第２の入力６０は、
レジスタ５０の第２のビット位置用のレジスタに結合さ
れ、選択入力６２は、ＡＬＵの符号標識を受信するため
にライン３２に接続される。１ビットトレースバックモ
ードにて動作する場合は、極値が選択される際に生成さ
れるＡＬＵの符号標識がシフトレジスタ５２のＬＳＢへ
の入力として供給される。２ビットトレースバックモー
ドにて動作する場合は、マルチプレクサ５６は、レジス
タ５０のＬＳＢレジスタ内に格納されているビットか、
あるいは、第２のビット位置用のレジスタ内に格納され
ているビットのいずれかを、２ビットトレースバック対
のＬＳＢとして選択し、極値が選択される際の、つま
り、第１と第２の中間極値を比較する際の、ＡＬＵから
の符号標識を、２ビットトレースバック対のより上位の
ビットとして供給する。２ビットトレースバック対のこ
のより上位のビットが、シフトレジスタ５２の第２のビ
ット位置用のレジスタに格納される。
レジスタ５０のＬＳＢに結合され、第２の入力６０は、
レジスタ５０の第２のビット位置用のレジスタに結合さ
れ、選択入力６２は、ＡＬＵの符号標識を受信するため
にライン３２に接続される。１ビットトレースバックモ
ードにて動作する場合は、極値が選択される際に生成さ
れるＡＬＵの符号標識がシフトレジスタ５２のＬＳＢへ
の入力として供給される。２ビットトレースバックモー
ドにて動作する場合は、マルチプレクサ５６は、レジス
タ５０のＬＳＢレジスタ内に格納されているビットか、
あるいは、第２のビット位置用のレジスタ内に格納され
ているビットのいずれかを、２ビットトレースバック対
のＬＳＢとして選択し、極値が選択される際の、つま
り、第１と第２の中間極値を比較する際の、ＡＬＵから
の符号標識を、２ビットトレースバック対のより上位の
ビットとして供給する。２ビットトレースバック対のこ
のより上位のビットが、シフトレジスタ５２の第２のビ
ット位置用のレジスタに格納される。
【００２３】極値として選択される中間極値が第１と第
２の潜在的な次の状態のコストメトリックから選択され
るときは、２ビットトレースバック対の最下位ビット
は、第１の潜在的な第１のビット位置のトレースバック
ビットとして選択され、レジスタ５０の第２のビット位
置用のレジスタ内に一時的に格納される。極値として選
択される中間極値が第３と第４の潜在的な次の状態のコ
ストメトリックから選択されるときは、２ビットトレー
スバック対の最下位ビットは、第２の潜在的な第１のビ
ット位置のトレースバックビットとして選択され、レジ
スタ５０の最下位ビット位置に一時的に格納される。レ
ジスタ５０内にこうして格納されるビットは、その後、
比較動作が遂行されると、その結果にて上書きされる。
２の潜在的な次の状態のコストメトリックから選択され
るときは、２ビットトレースバック対の最下位ビット
は、第１の潜在的な第１のビット位置のトレースバック
ビットとして選択され、レジスタ５０の第２のビット位
置用のレジスタ内に一時的に格納される。極値として選
択される中間極値が第３と第４の潜在的な次の状態のコ
ストメトリックから選択されるときは、２ビットトレー
スバック対の最下位ビットは、第２の潜在的な第１のビ
ット位置のトレースバックビットとして選択され、レジ
スタ５０の最下位ビット位置に一時的に格納される。レ
ジスタ５０内にこうして格納されるビットは、その後、
比較動作が遂行されると、その結果にて上書きされる。
【００２４】本発明が、４個の潜在的な次の状態のコス
トを比較するものとして説明された。ただし、本発明
は、これに制限されるものではない。例えば、本発明に
従って、４個のブランチメトリックを比較し、１個の極
値ブランチメトリックを選択することもできる。この場
合、極値ブランチメトリックと、極値ブランチメトリッ
クのオリジンにおける現在の状態と関連する累積コトス
とを加算することで、その極値ブランチメトリックの終
端における次の状態と関連する次の状態のコストが生成
される。この場合、上述のようにして生成および格納さ
れるトレースバックビットは、４個のブランチメトリッ
クの内のどれが極値ブランチメトリックとして選択され
たかを示すこととなる。
トを比較するものとして説明された。ただし、本発明
は、これに制限されるものではない。例えば、本発明に
従って、４個のブランチメトリックを比較し、１個の極
値ブランチメトリックを選択することもできる。この場
合、極値ブランチメトリックと、極値ブランチメトリッ
クのオリジンにおける現在の状態と関連する累積コトス
とを加算することで、その極値ブランチメトリックの終
端における次の状態と関連する次の状態のコストが生成
される。この場合、上述のようにして生成および格納さ
れるトレースバックビットは、４個のブランチメトリッ
クの内のどれが極値ブランチメトリックとして選択され
たかを示すこととなる。
【００２５】上では、トレースバックビットのパッキン
グ（packing)は、最も最近の一つあるいは複数のビット
を、一つあるいは複数の最下位ビット位置に格納するも
のとして説明されたが、当業者においては理解できるよ
うに、最も最近の一つあるいは複数のビットを、一つあ
るいは複数の最上位レジスタに格納するような設計も可
能である。
グ（packing)は、最も最近の一つあるいは複数のビット
を、一つあるいは複数の最下位ビット位置に格納するも
のとして説明されたが、当業者においては理解できるよ
うに、最も最近の一つあるいは複数のビットを、一つあ
るいは複数の最上位レジスタに格納するような設計も可
能である。
【００２６】説明の実施例においては、パイプライン構
成を組み込むようには説明されなかった。ただし、当業
者においては理解できるように、パイプライン構成を利
用するように設計することにより、計算の効率を向上す
ることもできる。パイプライン化は、新たなデータセッ
トの計算を、前のデータセットの計算を終える前に開始
するようにすることで達成される。パイプライン構成に
おいて用いられるラッチの数が多ければ多いほど、パイ
プライン構成の深さは深くなる。パイプライン構成で
は、パイプラインを満たすために計算時間に幾分の初期
遅延が発生するが、ただし、加算器などの資源の利用効
率は最大となる。
成を組み込むようには説明されなかった。ただし、当業
者においては理解できるように、パイプライン構成を利
用するように設計することにより、計算の効率を向上す
ることもできる。パイプライン化は、新たなデータセッ
トの計算を、前のデータセットの計算を終える前に開始
するようにすることで達成される。パイプライン構成に
おいて用いられるラッチの数が多ければ多いほど、パイ
プライン構成の深さは深くなる。パイプライン構成で
は、パイプラインを満たすために計算時間に幾分の初期
遅延が発生するが、ただし、加算器などの資源の利用効
率は最大となる。
【図１】本発明によるデータ演算ユニットの一部分を簡
略的に示す図である。
略的に示す図である。
【図２】４個の可能な現在の状態が単一の次の状態に遷
移できる一例としての１６状態ビタビバタフライにおけ
る現在の状態と次の状態の図の一部分を示す図である。
移できる一例としての１６状態ビタビバタフライにおけ
る現在の状態と次の状態の図の一部分を示す図である。
【図３】図１のデータ演算ユニットの一部分をより詳細
に示す図である。
に示す図である。
２０ データ演算ユニット ２２ ４個のレジスタ ２４ レジスタファイル ２６ 演算論理ユニット（ＡＬＵ） ３３ １ビット入力セレクタ ３４ 排他的論理和ゲート ３６ 選択入力 ３８ マルチプレクサ ５０ マルチビットレジスタ ５２ レジスタ ５６ マルチプレクサ ５８ マルチプレクサ５６の第１の入力 ６０ 第２の入力 ６２ 選択入力
フロントページの続き (72)発明者 シヴァナンド シマナパリ アメリカ合衆国 18104 ペンシルヴァ ニア，アレンタウン，ベナー ロード 638−201 (72)発明者 ラリー アール．テイト アメリカ合衆国 60010 イリノイズ, サウス バーリントン，チップング キ ャンプデン ドライヴ 12 (56)参考文献 特開 平５−3437（ＪＰ，Ａ) 特開 平５−3439（ＪＰ，Ａ) 特開 平10−200419（ＪＰ，Ａ) 特開 平10−322229（ＪＰ，Ａ) (58)調査した分野(Int.Cl.7，ＤＢ名) H03M 13/00
Claims (22)
- 【請求項１】 第１のＰＮＳ００メトリック、第２のＰ
ＮＳ０１メトリック、第３のＰＮＳ０２メトリック及び
第４のＰＮＳ０３メトリックを生成する段階と、 該第１のＰＮＳ００メトリック及び第２のＰＮＳ０１メ
トリックから２つの値の内の小さな方または大きな方が
選択されるべきであるかどうかを示す状態に従って第１
の中間極値を選択する段階と、 前記状態に従って、該第３のＰＮＳ０２メトリック及び
第４のＰＮＳ０３メトリックから第２の中間極値を選択
する段階と、 前記状態に従って、該第１及び第２の中間極値から極値
を選択する段階とからなることを特徴とするデジタル通
信システムを動作する方法。 - 【請求項２】 請求項１に記載の方法において、該メト
リックが潜在的な次の状態のコストであることを特徴と
する方法。 - 【請求項３】 請求項１に記載の方法において、該メト
リックがブランチメトリックであることを特徴とする方
法。 - 【請求項４】 請求項１に記載の方法においてさらに、
極値として第１のＰＮＳ００メトリック、第２のＰＮＳ
０１メトリック、第３のＰＮＳ０２メトリック及び第４
のＰＮＳ０３メトリックのどれが選択されたかを示すト
レースバックビットを格納する段階からなることを特徴
とする方法。 - 【請求項５】 請求項４に記載の方法において、該トレ
ースバックビットを格納する段階が、 中間極値の選択を示す中間ビットを格納する段階と、 中間極値の選択の際に生成されたビットと中間極値から
の極値の選択と関連するビットとから、トレースバック
ビットを構成する段階とからなることを特徴とする方
法。 - 【請求項６】 第１のＰＮＳ００メトリック、第２の
ＰＮＳ０１メトリック、第３のＰＮＳ０２メトリック及
び第４のＰＮＳ０３メトリックを生成する段階と、 該第１のＰＮＳ００及び第２のＰＮＳ０１のメトリック
から第１の中間極値メトリックを選択する段階と、 該第１及び第２のメトリック（ＰＮＳ００、ＰＮ
Ｓ０１）のどちらが第１の中間極値メトリックとして選
択されたかに対応する第１の潜在的な第１のビット位置
のトレースバックビットを生成する段階と、 該第３のＰＮＳ０２メトリック及び第４のＰＮＳ０３メ
トリックから第２の中間極値を選択する段階と、 該第３及び第４のメトリック（ＰＮＳ０２、ＰＮ
Ｓ０３）のどちらが第２の中間極値メトリックとして選
択されたかに対応する第２の潜在的な第１のビット位置
のトレースバックビットを生成する段階と、 該第１及び第２の中間極値から極値を選択する段階と、 該第１及び第２の中間極値のどちらが極値として選択さ
れたかに対応する第２のビット位置のトレースバックビ
ットを生成する段階とからなることを特徴とする方法。 - 【請求項７】 請求項６に記載の方法において、該メト
リックが潜在的な次の状態のコストであることを特徴と
する方法。 - 【請求項８】 請求項６に記載の方法において、該メト
リックがブランチメトリックであることを特徴とする方
法。 - 【請求項９】 請求項６に記載の方法においてさらに、
極値として第１のＰＮＳ００メトリック、第２のＰＮＳ
０１メトリック、第３のＰＮＳ０２メトリック及び第４
のＰＮＳ０３メトリックのどれが選択されたかを示すト
レースバックビットを格納する段階からなることを特徴
とする方法。 - 【請求項１０】 請求項９に記載の方法において、該ト
レースバックビットを格納する段階が、 中間極値の選択を示す中間ビットを格納する段階と、 中間極値の選択の際に生成されたビットと中間極値から
の極値の選択と関連するビットとから、トレースバック
ビットを構成する段階とからなることを特徴とする方
法。 - 【請求項１１】 請求項６に記載の方法においてさら
に、第１の潜在的な最下位ビットのトレースバックビッ
トと第２の潜在的な最下位ビットのトレースバックビッ
トとのどちらか一つを、該第１及び第２の中間極値メト
リックのどちらが極値メトリックとして選択されたかに
基づいて選択する段階からなることを特徴とする方法。 - 【請求項１２】 請求項６に記載の方法において、該第
１の潜在的な第１のビット位置のトレースバックビット
を生成する段階が、最下位ビットのトレースバックビッ
トを生成することを特徴とする方法。 - 【請求項１３】 請求項６に記載の方法において、該第
２のビット位置のトレースバックビットを生成する段階
が、最上位ビットのトレースバックビットを生成するこ
とを特徴とする方法。 - 【請求項１４】 請求項６に記載の方法において、該第
１の中間極値を選択する段階が、該第１及び第２のメト
リックを比較することを特徴とする方法。 - 【請求項１５】 請求項６に記載の方法において、該第
１の中間極値を選択する段階が、該第１及び第２のメト
リックの内の大きな方を選択することを特徴とする方
法。 - 【請求項１６】 請求項６に記載の方法において、該第
１の中間極値を選択する段階が、該第１のＰＮＳ００メ
トリックと該第２のＰＮＳ０１メトリックとの内の小さ
な方を選択することを特徴とする方法。 - 【請求項１７】 請求項６に記載の方法において、該選
択段階が、該第１のＰＮＳ００メトリックと該第２のＰ
ＮＳ０１メトリックとの内の大きな方を第１の中間極値
として選択し、該第３のＰＮＳ０２メトリックと該第４
のＰＮＳ０３メトリックとの内の大きな方を第２の中間
極値として選択し、該第１及び第２の中間極値の内の大
きな方を極値として選択することを特徴とする方法。 - 【請求項１８】 請求項６に記載の方法において、該選
択段階が、該第１及び第２のメトリックの内の小さな方
を該第１の中間極値として選択し、該第３及び第４のメ
トリックの内の小さな方を該第２の中間極値として選択
し、該第１及び第２の中間極値の内の小さな方を極値と
して選択することを特徴とする方法。 - 【請求項１９】 第１のメトリック、第２のメトリッ
ク、第３のメトリック、及び第４のメトリックを生成及
び格納する回路と、 該第１のメトリックと該第２のメトリック（ＰＮ
Ｓ００、ＰＮＳ０１）とを比較して、これから、２つの
値の内の小さな方または大きな方が選択されるべきであ
るかどうかを示す状態に従って、第１の中間極値を選択
するデータ演算ユニット２０とからなり、該データ演算
ユニット２０がさらに、該第３のＰＮＳ０２メトリック
と該第４のＰＮＳ０３メトリックとを比較して、これか
ら、前記状態に従って第２の中間極値を選択し、該デー
タ演算ユニット２０がさらに、該第１及び第２の中間極
値を比較し、これから前記状態に従って極値を選択する
ことを特徴とする集積回路。 - 【請求項２０】 請求項１９に記載の集積回路において
さらに、該第１及び第２のメトリックのどちらが選択さ
れたかに対応するトレースビットを格納するシフトレジ
スタ５２からなることを特徴とする集積回路。 - 【請求項２１】 請求項２０に記載の集積回路におい
て、該シフトレジスタ５２が、選択可能な数に相当する
メモリ位置だけシフトできることを特徴とする集積回
路。 - 【請求項２２】 請求項１９に記載の集積回路におい
て、前記データ演算ユニット２０は、２つのメトリック
を比較する演算論理ユニット２６と、前記状態及び該演
算論理ユニット２６の符号標識３２に従って、２つのメ
トリックのうちの１つを選択するマルチプレクサ３８
と、マルチプレクサ３８の出力及びマルチプレクサ３８
の入力と演算論理ユニット２６とに結合しかつメトリッ
クを格納するレジスタファイル２４とからなることを特
徴とする集積回路。
Applications Claiming Priority (2)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| US92551797A | 1997-09-08 | 1997-09-08 | |
| US08/925517 | 1997-09-08 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPH11186916A JPH11186916A (ja) | 1999-07-09 |
| JP3343217B2 true JP3343217B2 (ja) | 2002-11-11 |
Family
ID=25451843
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP25315098A Expired - Fee Related JP3343217B2 (ja) | 1997-09-08 | 1998-09-08 | ２ビットトレースバック符号化に対するビタビ比較・選択動作 |
Country Status (2)
| Country | Link |
|---|---|
| EP (1) | EP0901234A3 (ja) |
| JP (1) | JP3343217B2 (ja) |
Families Citing this family (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN116455405A (zh) * | 2023-04-20 | 2023-07-18 | 四川创智联恒科技有限公司 | 一种基于全相关概率计算的ldpc校验节点计算装置及方法 |
Family Cites Families (5)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US4823346A (en) * | 1986-04-16 | 1989-04-18 | Hitachi, Ltd. | Maximum likelihood decoder |
| US5327440A (en) * | 1991-10-15 | 1994-07-05 | International Business Machines Corporation | Viterbi trellis coding methods and apparatus for a direct access storage device |
| US5530707A (en) * | 1994-03-09 | 1996-06-25 | At&T Corp. | Area-efficient decoders for rate-k/n convolutional codes and other high rate trellis codes |
| EP0786872A2 (en) * | 1995-12-29 | 1997-07-30 | Lucent Technologies Inc. | Viterbi decoder with reduced metric computation |
| US6141384A (en) * | 1997-02-14 | 2000-10-31 | Philips Electronics North America Corporation | Decoder for trellis encoded interleaved data stream and HDTV receiver including such a decoder |
-
1998
- 1998-09-01 EP EP98306986A patent/EP0901234A3/en not_active Withdrawn
- 1998-09-08 JP JP25315098A patent/JP3343217B2/ja not_active Expired - Fee Related
Also Published As
| Publication number | Publication date |
|---|---|
| JPH11186916A (ja) | 1999-07-09 |
| EP0901234A3 (en) | 2004-06-16 |
| EP0901234A2 (en) | 1999-03-10 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US5471500A (en) | Soft symbol decoding | |
| JP3256504B2 (ja) | ソフトシンボル確信レベルの生成方法 | |
| CN101432972A (zh) | 基数-4维特比解码 | |
| US6333954B1 (en) | High-speed ACS for Viterbi decoder implementations | |
| US7127667B2 (en) | ACS circuit and viterbi decoder with the circuit | |
| JP3266182B2 (ja) | ビタビ復号器 | |
| EP2339757B1 (en) | Power-reduced preliminary decoded bits in viterbi decoder | |
| US6272188B1 (en) | Single-cycle accelerator for extremun state search | |
| US11165446B1 (en) | Parallel backtracking in Viterbi decoder | |
| US6009128A (en) | Metric acceleration on dual MAC processor | |
| JP3343217B2 (ja) | ２ビットトレースバック符号化に対するビタビ比較・選択動作 | |
| US6910177B2 (en) | Viterbi decoder using restructured trellis | |
| JP4149674B2 (ja) | ビタビ復号器のための高速メトリック計算 | |
| EP1542370A1 (en) | Method and system for branch label calculation in a Viterbi decoder | |
| JP3269845B2 (ja) | ヴィタビ復号器 | |
| JP3256505B2 (ja) | インデックスを識別する方法 | |
| JP3530451B2 (ja) | ビタビ復号装置 | |
| JP2002198827A (ja) | 最尤復号方法及び最尤復号器 | |
| JP2002076924A (ja) | ビタビ復号器 | |
| Jamal et al. | Design and FPGA Implementation of Low Power Punctured Soft Decision Viterbi Decoder | |
| JP2001186026A (ja) | ビタビ復号化装置およびビタビ復号化方法 | |
| WO2007000708A1 (en) | Viterbi decoder and decoding method thereof |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| R250 | Receipt of annual fees |
Free format text: JAPANESE INTERMEDIATE CODE: R250 |
|
| R250 | Receipt of annual fees |
Free format text: JAPANESE INTERMEDIATE CODE: R250 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20080823 Year of fee payment: 6 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20080823 Year of fee payment: 6 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20090823 Year of fee payment: 7 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20090823 Year of fee payment: 7 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20100823 Year of fee payment: 8 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20110823 Year of fee payment: 9 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20120823 Year of fee payment: 10 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20130823 Year of fee payment: 11 |
|
| R250 | Receipt of annual fees |
Free format text: JAPANESE INTERMEDIATE CODE: R250 |
|
| R250 | Receipt of annual fees |
Free format text: JAPANESE INTERMEDIATE CODE: R250 |
|
| LAPS | Cancellation because of no payment of annual fees |