JPH07273671A - データ復号方法 - Google Patents

データ復号方法

Info

Publication number
JPH07273671A
JPH07273671A JP7074727A JP7472795A JPH07273671A JP H07273671 A JPH07273671 A JP H07273671A JP 7074727 A JP7074727 A JP 7074727A JP 7472795 A JP7472795 A JP 7472795A JP H07273671 A JPH07273671 A JP H07273671A
Authority
JP
Japan
Prior art keywords
code
metric
path metric
processing element
slot
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.)
Pending
Application number
JP7074727A
Other languages
English (en)
Inventor
Horng-Dar Lin
リン ホーング−ダー
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 Corp
Original Assignee
American Telephone and Telegraph Co Inc
AT&T Corp
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 Corp filed Critical American Telephone and Telegraph Co Inc
Publication of JPH07273671A publication Critical patent/JPH07273671A/ja
Pending 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/63—Joint error correction and other techniques
    • H03M13/6325—Error control coding in combination with demodulation
    • 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
    • H03M13/4107—Sequence estimation, i.e. using statistical methods for the reconstruction of the original codes using the Viterbi algorithm or Viterbi processors implementing add, compare, select [ACS] operations
    • 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/47—Error detection, forward error correction or error protection, not provided for in groups H03M13/01 - H03M13/37

Landscapes

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

Abstract

(57)【要約】 【目的】 高レートトレリス符号の面積効率の良い復号
を実現する。 【構成】 各処理要素に符号状態を割り当てる。次に、
符号化データごとに異なる計算済みパスメトリックおよ
びブランチメトリックを用いて処理要素内での新たなパ
スメトリックの計算をスケジューリングする。また、一
部の計算済みパスメトリックが順次アクセスされるよう
に各処理要素から計算済みパスメトリックへのアクセス
をスケジューリングする。以上のスケジューリングに従
って計算したパスメトリックの生き残りシーケンスを使
用して符号化前のデータを評価する。また、パスメトリ
ックは、後の計算におけるアクセスを容易にするため
に、計算後に再配列される。その方法は、パスメトリッ
クに対応するデータ点をいくつかのスロットに分割し、
正しくないスロット位置を占めるデータ点を別のスロッ
ト位置に移動するようにデータ点を置換することにより
行われる。

Description

【発明の詳細な説明】
【０００１】
【産業上の利用分野】本発明は、符号化データの復号に
おける改良に関し、特に、レートｋ／ｎ畳込み符号など
の高いレートのトレリス符号を用いて符号化されたデー
タの復号における改良に関する。
【０００２】
【従来の技術】多くのデータ処理アプリケーションで
は、トレリス符号などのデータ符号化技術を用いてデー
タストリームを符号化するのが好ましいことが多い。例
えば、ディジタル通信システムでは、変調データのトレ
リス符号化は、符号化したデータの適当なマッピングと
組み合わせれば、伝送信号パワーまたは帯域幅を増大さ
せずに、受信される信号の信号対雑音比を改善すること
ができる。（ジー．ウンガーベック(G. Ungerboeck)、
「マルチレベル／位相信号によるチャネル符号化(Chann
el Coding with Multilevel/Phase Signals)」、IEEE T
ransactions on Information Theory、第ＩＴ−２８巻
第５５〜６７ページ（１９８２年１月）参照。）データ
符号化に帰することができる信号対雑音比の改善を符号
化利得といい、これは帯域幅効率を増大させる。上記の
ウンガーベックの論文によれば、レートｎ／（ｎ＋１）
トレリス符号を２n+1点信号セットにマッピングしたも
のは、符号化しない２n点信号セットと比べて大幅な符
号化利得を得ることができる。与えられたアプリケーシ
ョンで達成される符号化利得の量はいくつかの要因、例
えば、符号レートおよび符号の状態数などに依存する。
一般に、符号レートは、符号ビットの各シーケンスを生
成するために使用される非符号化データビットの数の関
数であり、符号の状態数は例えば符号器メモリ内の記憶
要素の数の関数である。
【０００３】レートｋ／ｎ畳込み符号は高レートトレリ
ス符号の一種である。レートｋ／ｎ畳込み符号において
は、ｋ個の非符号化データビットからなるグループ（デ
ータシンボルともいう）が、ｎ個の符号ビットを用いて
符号化される。これをまとめて符号シンボルという。レ
ートｋ／ｎ符号器は、シフトレジスタとして作用する符
号器メモリを含む。トレリス符号は、状態遷移をトレリ
スの形に図式化することが可能な符号の一般的なクラス
であるが、その状態遷移は必ずしもシフトレジスタのよ
うな特性を示す必要はない。低レート符号としてはレー
ト１／ｎ畳込み符号がある。これは、各１ビットデータ
シンボルがｎビット符号シンボルを使用して符号化され
る。高レートおよび低レートのいずれの符号の場合も、
符号化されたデータは、周知のビタビ最尤アルゴリズム
を実装したハードウェアを使用して復号されることが多
い。このアルゴリズムは、例えば、ジー．ディ．フォー
ニー、ジュニア(G. D. Forney, Jr.)、「ビタビアルゴ
リズム(The Viterbi Algorithm)」、Proceedings of th
e IEEE、第２６８〜２７８ページ（１９７３年３月）に
記載されている。ビタビアルゴリズムは、有限状態マル
コフ過程の状態シーケンスを評価する問題の再帰的解法
である。畳込み符号を使用してデータを符号化する過程
のようなマルコフ過程では、時刻ｔ＋１に与えられた状
態ｘt+1にある確率は、時刻ｔにおける状態ｘt（先行状
態ということにする）のみに依存する。ビタビアルゴリ
ズムは、与えられた符号化データのセットに対して、可
能な状態遷移のトレリスを通る最尤パスを見つけるとい
う意味で、最適な復号を行う。
【０００４】与えられた処理速度でビタビ復号アルゴリ
ズムを実装するのに要する回路面積を最小にすることを
企図した、いくつかの面積効率の良い復号器設計が、低
レート符号に対して開発されている。（例えば、ピー．
ジー．グラク(P. G. Gulak)、ティ．カイラス(T. Kaila
th)、「ビタビアルゴリズムのための局所連結ＶＬＳＩ
アーキテクチャ(Locally Connected VLSI Architecture
for the Viterbi Algorithm)」、IEEE Journal on Sel
ected Areas in Communications、第６巻第３号第５２
７〜５３７ページ（１９８８年４月）、および、エイチ
−ディ．リン(H-D. Lin)他、「畳込み符号に対する折返
しビタビ復号器(Folded Viterbi Decoders for Convolu
tional Codes)」、IEEE VLSI Signal Processing、第Ｉ
Ｖ巻、IEEE Press（１９９０年）参照。）しかし、高レ
ート符号は一般に、例えばビタビアルゴリズムを用いて
最大の符号化利得を与えるためにはずっと複雑なハード
ウェアのセットを必要とする。その結果、レートｋ／ｎ
畳込み符号などの高レートトレリス符号に対して現在利
用可能な復号器は一般に、復号器の複雑さおよびコスト
を縮小するために、次善の復号を利用している。次善の
復号アルゴリズムの例は、例えば、アール．イー．ブラ
フット(R. E. Blahut)、「誤り制御符号の理論と実際(T
heory and Practice of Error Control Codes)」、Addi
son-Wesley,Reading、米国マサチューセッツ州（１９８
４年）の第３８２〜３８８ページに記載されている。残
念ながら、次善の復号アルゴリズムを使用することによ
り復号器ハードウェアの複雑さを縮小することは通常、
符号化利得を犠牲にしてしまう。
【０００５】過度にハードウェアが複雑になる１つの理
由として、最適高レートビタビ復号器は一般に、先行状
態の可能なシーケンスの尤度を測るパスメトリックを並
列にアクセスし更新する処理要素を利用することがあ
る。その後、更新したパスメトリックを比較して、与え
られた符号化データのセットに対応する最尤状態シーケ
ンスを選択する。一般に、レートｋ／ｎ復号器における
各処理要素は２k個の並列メトリック入力を必要とす
る。さらに、復号器処理要素の総数は一般に、所望され
る符号化利得の関数として増大するため、高レート符号
の復号器は非常に多数の処理要素を含むことが多い。そ
の結果、レートｋ／ｎ復号器は一般に、レート１／ｎ復
号器よりも、多くの相互接続を含み、ずっと大きい回路
面積を占めることになる。しかし、低レート符号に対し
て開発されている面積効率の良い技術は、一般に、多数
の並列入力処理要素の使用に伴って増大する回路面積の
問題を軽減しない。従って、現状では、費用効率の良い
方法で高レート符号の利点を達成するのは困難である。
【０００６】
【発明が解決しようとする課題】上記のことから明らか
なように、高レートトレリス符号に対して、面積効率を
改良した復号器が必要とされている。この改良した復号
器は、次善の復号アルゴリズムに頼らずに、ハードウェ
アの複雑さを縮小すべきである。
【０００７】
【課題を解決するための手段】本発明は、レートｋ／ｎ
畳込み符号のような高レートトレリス符号を使用して符
号化されたデータを復号する方法および装置を実現する
ものである。本発明の第１の特徴によれば、符号化され
たデータのストリームを復号する方法は、複数の復号器
処理要素のそれぞれに符号状態を割り当てるステップ
と、符号化されたデータごとに異なる計算済みのパスメ
トリックおよびブランチメトリックを使用して処理要素
内での複数の新たなパスメトリックの計算をスケジュー
リングするステップと、新たなパスメトリックを計算す
るために、計算済みパスメトリックの適当なセット内の
各計算済みパスメトリックが、与えられた処理要素によ
って順次アクセスされるように、各処理要素から計算済
みパスメトリックの当該適当なセットへのアクセスをス
ケジューリングするステップと、以上のスケジューリン
グステップに従って計算したパスメトリックの生き残り
シーケンスを使用して符号化前のデータを評価するステ
ップとからなる。本発明は特に、ビタビ最尤復号アルゴ
リズムとともに用いるのに適しているが、他の復号アル
ゴリズムとともに使用することも可能である。
【０００８】本発明の第２の特徴によれば、２i個の処
理要素のそれぞれに符号状態を割り当てる方法は、符号
状態のグループを、その２進表示におけるｉ個のビット
の共通セットに基づいて分割し、各処理要素に、ｉビッ
トの共通セットを有する符号状態の分割されたグループ
を割り当てることによって行われる。本発明の一実施例
では、ｉビットのセットは、符号状態の２進表示のｉ個
の上位ビットのセットを表す。
【０００９】本発明の第３の特徴によれば、パスメトリ
ック計算およびアクセススケジュールは、各処理要素が
計算済みパスメトリックの適当なセットに順次アクセス
をするために、２i個の処理要素のそれぞれによるメト
リックの計算およびメトリックへのアクセスを、ｉ個の
復号器クロックサイクルだけずらす。
【００１０】本発明の第４の特徴によれば、パスメトリ
ックは、後の計算におけるアクセスを容易にするため
に、計算後に再配列される。実施例のメトリック再配列
方法は、パスメトリックに対応するデータ点をいくつか
のスロットに分割するステップ（各スロット内のスロッ
ト位置の数をスロットサイズという）と、正しくないス
ロット位置を占めるデータ点を別のスロット位置に移動
するようにデータ点を置換するステップと、データ点を
いくつかのスロットに分割するステップと、置換するス
テップとを、所望のデータ点の配列が得られるまで繰り
返すステップとからなる。この方法の一実施例では、あ
るスロット内の正しくない位置のデータ点は、他のスロ
ット内の別々の位置に直接移動される。別の実施例で
は、データ点はまずあるスロット内のスロット境界付近
に収集された後、他のスロット内の別々の位置へ境界を
横切って移動される。
【００１１】本発明の特徴的な効果として、高レートト
レリス符号の最尤復号が実現される。従って、与えられ
た符号化方式によって、大幅に符号化利得が改善され、
その結果、多くの高レート復号器で現在利用されている
次善の復号に比べて帯域幅効率が改善される。
【００１２】本発明のもう１つの特徴的な効果として、
復号器の複雑さが大幅に縮小され、その結果、復号器を
実装するのに必要な回路面積が大幅に減少する。従っ
て、本発明は、実用的かつ費用効率の良い方法で、高レ
ート符号による帯域幅効率の利点を達成することができ
る。
【００１３】
【実施例】本発明は、例えばレートｋ／ｎ畳込み符号の
ような高いレートのトレリス符号を用いて符号化された
データを復号する方法および装置を提供する。ここで、
「トレリス符号」という用語は、トレリス線図の形でモ
デル化されるような状態遷移を有する任意の種類の符号
を指す。畳込み符号はトレリス符号の一種である。「高
レート（高いレート）」という用語は、レート１／ｎよ
り大きい符号レートを指す。「面積効率の良い復号器」
という用語は、与えられた処理速度において、従来の復
号器と比べて、占有する回路面積が小さい復号器の実装
を指す。以下の説明では、２進ストリングを表すのに括
弧の対を使用する。例えば、符号状態「７」は（００１
１１）と書き、処理要素「２」を処理要素（１０）と書
く。同様に、（ａｂｃ）という形の表現では、変数ａ、
ｂおよびｃが２進値のみをとることを意味する。
【００１４】以下の説明は主にレートｋ／ｎ畳込み符号
のビタビ復号について行うが、これは単に例示のためで
あることは理解されるべきである。本発明は、他の多く
の高レートトレリス符号に容易に適用可能である。ここ
で開示するデータ再配列技術は、例えば交錯符号のよう
な非トレリス符号にも適用可能である。さらに、本発明
は、いくつもの異なる復号アルゴリズムのうちの任意の
ものを利用可能である。さらに、本発明は、例えば、マ
ルチレベル／位相信号の符号化変調の復号、シンボル間
干渉のある通信チャネルでの最尤信号シーケンス評価、
磁気記憶装置に対するディジタルシーケンス検出、光学
的に走査した文字またはパターンの検出、および音声認
識などを含む、多くの異なる復号アプリケーションにも
効果がある。
【００１５】図１の（ａ）に、ｋ個の非符号化データビ
ットの各グループ（すなわちデータシンボル）がｎビッ
トの符号シンボルによって表現されるようにデータのス
トリームを符号化するのに適した、レートｋ／ｎ畳込み
符号器１０の例を示す。一実施例では、符号器１０は、
２個の非符号化データ入力ｂ０、ｂ１、記憶要素１２、
１４、１６、符号化ロジック１８、ならびに３個の符号
化データ出力ｃ０、ｃ１、およびｃ２を有する。例示し
た符号器１０は、２個の非符号化入力ビットの各グルー
プに対して、３個の符号化出力ビット（まとめて符号シ
ンボルという）を生成するので、レート２／３符号器と
いう。記憶要素１２、１４、１６はまとめて符号器メモ
リという。各記憶要素は一般に２進情報を１ビット記憶
し、例えば、Ｄ型フリップフロップである。符号器メモ
リの内容は、以下で詳細に説明するように、符号器の状
態を決定する。
【００１６】符号器１０の各記憶要素１２、１４、１６
を通る非符号化データをクロックするために、共通の符
号器クロック信号を使用する。符号器クロック信号周期
は、符号器シンボルレートの逆数であり、符号器状態
は、符号器クロック信号の各サイクル中に２個の新しい
入力ｂ０、ｂ１を使用して更新される。符号化出力ｃ
０、ｃ１およびｃ２は、記憶要素１２、１４、１６から
クロック出力されたデータの論理関数であり、従って、
符号化状態を反映する。符号化ロジック１８内で実行さ
れる論理関数のタイプは一般に符号器ごとに異なる。符
号器１０の記憶要素１２、１４、１６は、ともに、２k
を基数とするシフトレジスタとして作用し、任意の与え
られた時刻に２k個の非符号化データビットを含む。こ
れに対して、レート１／ｎ符号器の符号器記憶要素は２
進シフトレジスタとして作用する。上記のように、この
シフトレジスタのような挙動は、より一般的なクラスの
トレリス符号から畳込み符号を区別するものである。
【００１７】図１の（ａ）の実線で示された記憶要素１
２、１４、１６は、８状態レート２／３符号器を実装す
るために必要な要素に対応する。８個の状態は、（ｍ2
ｍ1ｍ 0）の形のすべての可能なシーケンスによって２進
形式で表現される。ただし、ｍ0、ｍ1、およびｍ2はそ
れぞれ記憶要素１２、１４および１６の２進値の内容で
ある。一般に、符号器状態の数は２jである。ただし、
ｊは符号器メモリ内の記憶要素の数に対応する。符号器
１０では実線の３個の記憶要素１２、１４、１６がある
ため、符号器１０の実線バージョンは８個の可能な符号
状態を有する。さらに、符号器１０の破線で示された記
憶要素２０、２２を含めることによって、記憶要素の総
数ｊは５になり、その場合、符号器１０は３２状態レー
ト２／３符号器として作用する。３２個の状態は、（ｍ
4ｍ3ｍ2ｍ1ｍ0）の形のすべての可能な２進シーケンス
によって表現される。ただし、ｍ3およびｍ4はそれぞれ
追加した記憶要素２０および２２の内容である。
【００１８】図１の（ｂ）に、図１の（ａ）の符号器１
０の８状態３記憶要素バージョンに対応するトレリス線
図３０を示す。一般に、トレリス線図は、有限状態機械
における可能な状態遷移を時間の関数として重みつきグ
ラフ表示したものである。トレリス３０は、ブランチ３
６によって相互接続された複数のノード３２、３４を含
む。トレリスノード３２、３４は、符号化過程中の特定
の時刻における可能な符号状態に対応し、ブランチ３６
は符号状態間の可能な遷移を示す。第１列のノード３２
は、８状態符号化過程に対する８個の可能な初期状態を
表し、状態の２進表現に従って０〜７とラベルされてい
る。符号化過程は、離散時間周期（ステージという）に
分割される。初期ステージは図１の（ｂ）ではステージ
０とラベルされている。過程の各ステージは１符号化ク
ロックサイクルに対応し、そのサイクル中に新しいデー
タ入力ｂ０、ｂ１を受信し、新しい符号化データ出力ｃ
０、ｃ１、ｃ２を生成する。受信したデータ入力に基づ
いて、符号器状態は、トレリス線図３０のステージ１で
ノード３４によって表される次のステージのいくつかの
ノードのうちの１つに遷移する。例えば、記憶要素１
２、１４、１６がそれぞれ最初は２進値０を含む場合、
符号器１０は最初は状態（０００）にある。次の符号化
クロックサイクルで受信する入力データビットｂ０、ｂ
１が（１１）である場合、記憶要素１２、１４、１６の
内容はそれぞれ１、１および０となり、符号器は状態
（０１１）に移る。入力ビットｂ０、ｂ１には４個の可
能な組合せがあるため、符号化過程がステージ０の状態
（０００）から遷移することができるステージ１の状態
には、４個の可能な状態（０００）、（００１）、（０
１０）および（０１１）がある。各ブランチ３６は、ス
テージ０の状態（０００）からの可能な遷移のうちの１
つを表す。同様のブランチは、符号化過程におけるその
他のすべての可能な状態遷移を示す。理解されるよう
に、ステージ０の状態（０００）からは４個のブランチ
が出ており、これは、受信データに依存して、この過程
がこの状態からステージ１の状態（０００）、（００
１）、（０１０）または（０１１）のうちの１つに遷移
することが可能であることを示している。
【００１９】トレリス線図３０は静的タイプのものであ
り、後のステージも時間の関数として同じものが反復す
るため、過程を完全に図示するには最初の２個のステー
ジのみを示せばよい。これは、トレリス線図３０が、与
えられた時刻ｔ＋１における状態が前の時刻ｔにおける
過程の状態にのみ依存するというマルコフ過程畳込み符
号化をモデル化しているという事実によるものである。
トレリス内の状態の総数は、入力データシーケンスの長
さに対応するが、これは多くのアプリケーションでは無
限である。注意すべき点であるが、トレリス線図は動的
タイプのものも可能である。この場合のトレリス符号で
は、異なるステージは異なるセットの可能な状態遷移を
有する。一般に、静的トレリスは、各ステージに２j個
のノードを含み、各ノードはマルコフ過程の２j個の可
能な各状態に対応する。ただし、ｊは符号器メモリ内の
記憶要素の数である。レートｋ／ｎ符号に対するトレリ
スは、各ノードからの２k個のブランチを有する。これ
は、対応する状態からの可能な遷移を示す。これに対し
て、レート１／ｎ符号は、各ノードからのブランチが２
個だけのトレリスを有する。従って理解されるように、
トレリスの複雑さは、符号状態の数および符号レートの
関数である。トレリスが複雑になると、対応する復号プ
ロセスを実装する回路のハードウェアの複雑さが増大す
ることになる。
【００２０】符号器１０からの符号化されたデータは、
多くのアプリケーションのうちの任意のものにおいて使
用可能である。通常のアプリケーションはディジタルデ
ータ伝送である。この場合、符号化データは例えば、高
周波キャリア信号を変調するために使用される。受信機
では、受信したキャリア信号を復調した後、復元した符
号化データを復号する。
【００２１】符号化したデータは、復号アルゴリズムを
使用して復号される。上記のビタビアルゴリズムは、特
に、通信チャネルを通じて伝送される符号化データに一
般的に生じるような、記憶のない雑音の存在下での復号
に適した最尤復号アルゴリズムである。ビタビアルゴリ
ズムは、最初は、畳込み符号化されたデータを検出する
技術として開発されたものであるが、その後に、より一
般的に、重みつきグラフを通る最短パスを見つける問題
に対する動的計画法の解を表すことが示されている。ビ
タビアルゴリズムは、符号器のトレリス線図を使用し
て、対応する符号化動作を再構成することによって、符
号シンボルのストリームを復号する。ステージｔ＋１で
受信した符号シンボルを現符号シンボルといい、ステー
ジｔで受信した符号シンボルを前符号シンボルというこ
とにする。尤度の測度（パスメトリックという）は、ト
レリスにおける与えられたステージにおいてノードごと
に計算される。ステージｔ＋１のノードのパスメトリッ
クは、まず、ある重みつき値（ブランチメトリックとい
う）を、ステージｔ内のすべての可能な先行状態に対す
る各計算済みパスメトリックに加算することによって、
再帰的に計算される。この操作を、与えられたノードに
対してパスメトリックを更新するということが多い。ブ
ランチメトリックは、対応する状態遷移が起きた尤度を
示し、従って、与えられたステージで受信された符号シ
ンボルに依存して異なる。例えば、非符号化データシン
ボル（ｂ１ ｂ０）が（１１）であることに対応する符
号シンボル（ｃ２ ｃ１ ｃ０）を、図１の（ｂ）のト
レリス３０のステージ１における状態（０００）で受信
したと仮定する。トレリス３０によれば、先行状態は
（０００）、（０１０）、（１００）または（１１０）
のいずれかである。これらの４個の可能な遷移のそれぞ
れに対するブランチメトリックは一般に、現状態および
現符号シンボルが与えられた場合に、先行状態のうちの
１つが他の状態より尤度が高くなるように変化する。各
符号状態および可能な各符号シンボルごとに異なるブラ
ンチメトリックのセットがある。これらのブランチメト
リックの値は、事前に計算して例えばブランチメトリッ
クテーブルに記憶しておくことが可能である（詳細は後
述）。
【００２２】与えられたトレリス符号に対して、ステー
ジｔの可能な各先行状態に対する計算済みパスメトリッ
クからなる適当なパスメトリックのセットにブランチメ
トリックを加算した後、各入力ブランチに対するその結
果の和を比較する。最小の和は、ステージｔ＋１におけ
る与えられたノードへの最も尤度の高い遷移に対応す
る。この和が、そのノードに対する新たなパスメトリッ
クとして選択される。このように、受信した符号語ごと
に新たなパスメトリックを計算する過程は一般に、計算
済みパスメトリックのセットにブランチメトリックを加
算し、更新したパスメトリックを比較し、最尤状態遷移
に対応する更新パスメトリックを新たなパスメトリック
として選択することを含む。このパスメトリック計算は
一般に復号器処理要素で実行される。
【００２３】与えられたノードにおいて計算された新た
なパスメトリックを生じる、トレリスを通る最尤状態遷
移に対応する符号化データシンボルのシーケンスを、生
き残りシーケンスという。生き残りシーケンスは、与え
られた符号シンボルのシーケンスに対してトレリスを通
る最尤パスをたどるので、受信符号シンボルに対応する
非符号化データシンボルのシーケンスを評価するために
使用することができる。トレリスの与えられたステージ
におけるノードごとに、新たなパスメトリックとそれに
対応する生き残りシーケンスの両方を計算し記憶する。
現符号シンボルに対して計算した新たなパスメトリック
は、そのシーケンス中の次の符号シンボルに対する新た
なパスメトリックを計算する際に計算済みパスメトリッ
クつぃてしようするまで一時的に記憶するだけでよい。
生き残りシーケンスを記憶するためのメモリは、いくつ
かの既知の技術のうちの任意のものを用いて実装可能で
ある。そのような技術のうちの１つに、メモリトレース
バックがあり、例えば、アール．サイファ（R. Cyphe
r)、シー．ビー．シュン(C. B. Shung)、「ビタビアル
ゴリズムにおける生き残りメモリ管理のための一般化さ
れたトレースバック技術(Generalized Trace Back Tech
niques for Survivor Memory Management in the Viter
bi Algorithm)」、Proceedings of GlobeCom（１９９０
年１２月）IEEEPress、第１３１８〜１３２２ページ、
および、オー．コリンズ(O. Collins)、エフ．ポララ
(F. Pollara)、「トレースバックビタビ復号器における
メモリ管理(Memory Management in Traceback Viterbi
Decoders)」、TDA Progress Report42-99, Jet Propuls
ion Laboratory、第９８〜１０４ページ（１９８９年１
１月１５日）、に記載されている。
【００２４】ビタビアルゴリズムがステージからステー
ジへと進行し、受信符号シンボルに対してパスメトリッ
クを計算していくにつれて、前のステージのノードに対
する生き残りシーケンスは最尤パスに収束していく。生
き残りシーケンスは、復号過程が進行するとともに無限
に長くのびることになるため、シーケンスは、最も前に
評価したデータシンボルを取り出して復号器出力として
使用するために、定期的に打ち切られる。アルゴリズム
は、ステージｔ＋１の各ノードに対する新たなパスメト
リックが、そのノードの可能な各先行状態に対する計算
済みパスメトリックと、受信符号化データシンボルに対
応するブランチメトリックのセットとに基づいて計算さ
れ記憶されるという意味で、再帰的に動作する。アルゴ
リズムは、例えば、図１の（ｂ）のトレリスのステージ
０のノード３２のような、トレリスの初期ステージの各
ノードに対してパスメトリック値を０と仮定することに
よって初期化される。ビタビアルゴリズムに関してさら
に詳細には、例えば、ジー．ディ．フォーニーの前掲論
文、および、ピー．ジー．グラク(P. G. Gulak)、イ
ー．シュウェディク(E. Shwedyk)、「ビタビ受信機のＶ
ＬＳＩ構造：第１部−総論と応用(VLSI Structures for
Viterbi Receivers: Part I - General Theory and Ap
plications)」、第ＳＡＣ−４巻第１号第１４２〜１５
４ページ（１９８６年１月）、に記載されている。
【００２５】上記のビタビ復号アルゴリズムを実装する
ために使用するハードウェアの複雑さは、符号状態の数
および符号状態間の可能な遷移の数の関数である。例え
ば、レートｋ／ｎビタビ復号器における代表的な復号器
処理要素は、与えられたトレリスノードとその２k個の
可能な先行ノードとの間の最尤パスを決定するために２
k個の異なるパスメトリックにアクセスし、それらを更
新し、比較し、それらからの選択を行わなければならな
い。各パスメトリックのアクセス、更新および比較に１
単位のコストを仮定すると、レートｋ／ｎ符号の場合の
各復号器処理要素は、レート１／ｎ符号の場合の対応す
る処理要素よりも約０．６×２k倍高価になる。全体の
復号器のコストおよび複雑さを比較するためには、各処
理要素の追加コストを、復号器内の処理要素の総数倍し
なければならない。処理要素の数は一般に符号状態の
数、従って、所望される符号化利得の関数であるため、
復号器のコストおよび複雑さは、高い符号化利得のアプ
リケーションでは大幅に増大する。
【００２６】処理要素の時分割を利用することによっ
て、符号状態の数を減少させることなく、処理要素の総
数を縮小することができる。しかし、時分割は一般的に
復号器全体の処理速度を減少させる。このようにして一
般に、復号器の設計は、少数の時分割処理要素を使用し
た低速処理と、例えば符号状態ごとに別々の処理要素を
使用した高速並列処理との間の速度−複雑さトレードオ
フを示す。時分割の程度は、通常、折返し係数Ｆによっ
て指定される。これは、処理要素の数に対する符号状態
の数の比である。折返し係数は、与えられた処理要素に
対して時分割方式でパスメトリックを計算することが必
要な、受信符号シンボルあたりの状態数を示す。例え
ば、４個の処理要素を使用する５１２状態の符号に対す
る復号器ではＦは１２８である。５１２個の処理要素が
５１２状態符号に使用される場合は、折返しすなわち時
分割はなく、Ｆは１となる。後者の場合、復号器は状態
並列復号器であるという。
【００２７】折返し係数は、もう１つの重要な復号器の
パラメータに関係している。このパラメータは通常、パ
イプライン深度と呼ばれるものである。ビタビ復号に必
要な計算の多くはパイプライン化される。すなわち、別
個の関数演算の中間結果を一時的に記憶するためにラッ
チなどの記憶要素を使用して実行される。例えば、パイ
プライン化された処理要素は、パスメトリック計算に関
係する加算、比較および選択演算の中間結果を一時的に
記憶するためのラッチの直列配置を含む。パイプライン
深度とは、処理要素パイプライン中の記憶要素の数のこ
とをいう。復号器ハードウェアが１００％利用されるよ
うな理想的復号器では、処理要素パイプライン深度は折
返し係数Ｆに等しい。しかし、多くの実際の復号器で
は、パイプラインを通じてのデータ処理のフローにおけ
る遅延やギャップによるハードウェアの非効率を補償す
るために、パイプライン深度はＦより大きく設計され
る。従って、パイプラインクロックレートは一般に、符
号シンボルレートのＦ倍より大きく動作するように設計
される。ここで符号シンボルレートは、ｎビット符号シ
ンボルが符号器で発生されるレートに対応する。
【００２８】従来技術による面積効率の良い復号器の設
計は一般に３つの基本的ステップを含む。第１に、各符
号状態を、復号器処理要素のうちの１つにマッピングす
る（すなわち、割り当てる）。第２に、各処理要素およ
びそれに割り当てられた符号状態に対するパスメトリッ
ク計算をスケジューリングする。最後に、符号状態マッ
ピングおよび計算スケジュールを実装するために適当な
回路構造を定義する。最初の２つのステップは、処理要
素ごとに、いずれのパスメトリックをどのような順序で
アクセスし更新するかを指定する。この情報と、符号ト
レリス構造に定義された状態遷移とに基づいて、処理要
素間に必要な通信を分析し、ハードウェア効率を決定す
ることができる。符号状態が少数である簡単な符号で
は、最も面積効率の良いマッピングおよびスケジューリ
ングを見つけるために全数探索を実行することも可能で
ある。しかし、このようなアプローチは複雑な符号に対
しては一般に実際的ではないため、他のタイプの復号器
設計技術が開発されている。
【００２９】レート１／ｎ符号に対して開発された従来
技術の例としては、例えば、その場スケジューリング、
メトリック再配列、およびカスケードマッピングがあ
る。レート１／ｎ符号に対するその場スケジューリング
は、例えば、エイチ−ディ．リン(H-D. Lin)ほか、「畳
込み符号のための折返しビタビ復号器(Folded ViterbiD
ecoders for Convolutional Codes)」、IEEE VLSI Sign
al Processing、第ＩＶ巻、IEEE Press（１９９０
年）、エム．ビヴァ(M. Biver)ほか、「ビタビ復号器に
おけるパスメトリックのその場更新(In-Place Updating
of Path Metrics inViterbi Decoders)」、IEEE Journ
al of Solid-State Circuits、第２４巻第４号第１１５
８〜１１６０ページ（１９８９年８月）、および、エイ
チ−ディ．リン(H-D. Lin)、シー．ビー．シュン(C. B.
Shung)、「ビタビアルゴリズムに対する一般的その場
スケジューリング(General In-Place Scheduling for t
he Viterbi Algorithm)」、Proceedings of ICASSP-91,
Toronto, Canada（１９９１年５月１４〜１７日）、に
記載されている。レート１／ｎ符号に対するメトリック
再配列は、例えば、シー．ビー．シュン(C. B. Shung)
ほか、「ビタビアルゴリズムのための面積効率の良いア
ーキテクチャ(Area-Efficient Architectures for the
Viterbi Algorithm)」、Proceedings of GlobeCom 199
0、IEEE Press、第１７８７〜１７９３ページ、に記載
されている。レート１／ｎ符号に対するカスケードマッ
ピングは、例えば、ピー．ジー．グラク(P. G. Gula
k)、ティ．カイラス(T. Kailath)、「ビタビアルゴリズ
ムのための局所連結ＶＬＳＩアーキテクチャ(Locally C
onnected VLSI Architecture for the Viterbi Algorit
hm)」、IEEE Journal on Selected Areas in Communica
tions、第６巻第３号第５２７〜５３７ページ（１９８
８年４月）、に記載されている。レートｋ／ｎ畳込み符
号に対するその場スケジューリングは、エイチ−ディ．
リンとシー．ビー．シュンの前掲論文に記載されてい
る。上記のように、これらの従来技術のいずれも、高レ
ート符号に対する十分に良い面積効率を実現していな
い。
【００３０】本発明の一実施例では、２i個のパイプラ
イン化した処理要素を使用して２j状態レートｋ／ｎ畳
込み符号に対する面積効率の良いビタビ復号器を構成す
る（ただし０＜ｉ＜ｊ）という復号器設計技術を提供す
る。得られる復号器の複雑さは非常に小さいため、従来
技術を使用して開発された復号器に比べて面積効率が改
善される。
【００３１】本発明の１つの特徴には、符号状態を復号
器処理要素に割り当てるステップが含まれる。各処理要
素は、それに割り当てられた符号状態に対する新たなパ
スメトリックを計算する。一実施例では、この割当てス
テップには、分割（詳細は後述）に基づく最上位ビット
（ＭＳＢ）が関係する。これにより一般に処理要素間の
一様な通信が得られる。既に図１の（ａ）に関して述べ
たように、２j状態レートｋ／ｎ畳込み符号の符号器メ
モリは、基数２kのシフトレジスタとして作用する。一
般性を失うことなく、以下の説明では、符号器メモリ内
の記憶要素は、長い方の符号器記憶要素の列中の左端の
記憶要素が符号の最下位ビット（ＬＳＢ）に割り当てら
れるように配置されると仮定する。例えば、図１の
（ａ）の符号器１０では、ＬＳＢｍ0は記憶要素１２に
割り当てられる。図１の（ａ）に示されているように、
基数２kのシフトレジスタの内容は、ｊビットの２進ス
トリング（ｍj-1...ｍ1ｍ0）として書くことができる。
ここで、ビットは、ＭＳＢｍj- 1がレジスタ内の最も古
いビットであり、ＬＳＢｍ0がレジスタ内の最も新しい
ビットであるように順序づけられる。２進ストリングの
ビットは、図１の（ａ）のラベルｍ4、ｍ3、ｍ2、ｍ1お
よびｍ0によって識別され、符号器状態の２進表示に対
応する。符号器へのｋビット入力が（ｂk-1...ｂ1ｂ0）
によって与えられる場合、符号器の次状態は（ｍj-k-1
ｍj-k-2...ｍ1ｍ0ｂk-1...ｂ1ｂ0）によって与えられ
る。例えば、符号器１０の３２状態レート２／３バージ
ョンの符号器メモリ内容が（ａｂｃｄｅ）によって与え
られ、（ｆｇ）の入力（ｂ1ｂ0）を受信した場合、符号
器の次状態は（ｃｄｅｆｇ）である。処理要素への符号
状態の割当ては、復号器内の処理要素網に対する配置も
定義する。
【００３２】図２〜図５に、本発明によるいくつかの３
２状態レート２／３復号器の例およびそれらに対応する
トレリス線図を示す。図２は、１６個の処理要素４２を
含む復号器４０を示す。各処理要素４２の出力は、相互
接続ライン４６を通じて１６個のパスメトリック出力分
配ノード４４のうちの１つに接続される。各分配ノード
４４はまた、４個の相異なる処理要素４２の入力に接続
される。パスメトリック分配ノードは、パスメトリック
の計算およびアクセスのスケジュール（後述）に従っ
て、各処理要素からの出力を他の処理要素に分配する。
図３の対応するトレリス線図５０は１６個のステージ０
トレリスノード５２を含み、このトレリスノード５２は
それぞれブランチ５６によって１６個のステージ１トレ
リスノード５４のうちの４つと相互接続されている。図
２の復号器４０は、１６個の処理要素を含むので、３２
状態符号に対して使用するときには折返し係数は２であ
る。従って、トレリス５０内の各ノードは２個の異なる
符号状態を表す。注意すべき点であるが、符号器４０
は、より複雑さの少ない１６状態レート３／２符号に対
する状態並列復号器も表す。上記のように、状態並列復
号器とは、各符号状態が１個の処理要素に割り当てられ
復号器折返し係数を１とした復号器である。
【００３３】図４の（ａ）に示した復号器６０は８個の
処理要素６２を含み、各処理要素６２の出力は、相互接
続ライン６６を通じて８個のパスメトリック分配ノード
のうちの１つに接続される。復号器６０は、３２状態符
号に対して使用するときには折返し係数は４であり、従
って、８状態レート２／３符号に対する状態並列復号器
に対応する。対応するトレリス線図７０は８個のステー
ジ０ノード７２を含み、各ノード７２はブランチ７６を
通じて４個のステージ１ノード７４に接続される。図５
の（ａ）に示した復号器８０は２個の処理要素８２を含
み、各処理要素８２の出力は、相互接続ライン８６を通
じて２個のパスメトリック分配ノードのうちの１つに接
続されるので、復号器８０は、３２状態符号に対して使
用するときには折返し係数は１６である。従って、復号
器８０は完全に相互接続され、対応する２状態レート２
／３符号はない。完全相互接続復号器では、各処理要素
は各パスメトリック分配ノードに接続される。注意すべ
き点であるが、図５の（ａ）の復号器８０は、各メトリ
ック分配ノード８４と処理要素８２の間に二重ラインの
対を含む。復号器８０における二重ラインの各対は、２
つのメトリックが各分配ノードから各処理要素に分配さ
れることを示す。実際の復号器の実装では、単一の相互
接続を使用して両方のメトリックを転送することも可能
である。対応するトレリス線図９０は２個のステージ０
ノード９２を含み、各ノード９２は二重ライン９６の対
を通じて２個のステージ１ノード９４に接続される。
【００３４】一般に、２j状態レートｋ／ｎ符号に対し
て、本発明による、２i個（ただしｉ≧ｋ）の処理要素
を有する面積効率の良い復号器は、２i状態レートｋ／
ｎ符号に対する状態並列復号器に対応する配置を有す
る。ｉ＜ｋの場合、復号器の配置は、２i個の処理要素
の完全相互接続網のものに対応する。従って、本発明の
復号器は、異なる数の符号状態を有する他のレートｋ／
ｎ符号に対しても利用可能である。
【００３５】上記のように、本発明による、符号状態の
復号器処理要素への割当ては、例えば、符号状態のＭＳ
Ｂ分割に基づく。ＭＳＢ分割では、２i個の処理要素は
２j状態レートｋ／ｎ畳込み符号を復号するために使用
され、ｉ個のＭＳＢの共通セットを有する符号状態のグ
ループが同じ処理要素に割り当てられる。例として、４
個の処理要素（すなわちｉ＝２）を有する復号器を使用
して３２状態レートｋ／ｎ符号を復号すると仮定する。
この場合、本発明による符号状態割当ては、与えられた
状態の２個のＭＳＢに基づくことになる。従って、符号
状態の２進表示は、４個のグループ、すなわち、（００
ｘｘｘ）、（０１ｘｘｘ）、（１０ｘｘｘ）および（１
１ｘｘｘ）、に分割される。ただし、ｘは「ドントケ
ア」値を表す。すると、各グループの符号状態は、４個
の復号器処理要素のうちの１つに割り当てられることに
なる。注意すべき点であるが、符号状態の割当ては、ｉ
個のＭＳＢ以外のｉ個の共通セットに基づくことも可能
である。さらに、各グループは同数の符号状態を含む必
要はないが、少なくとも１つの異なる符号状態が一般に
各処理要素に割り当てられる。簡単のため、以下の説明
では、個々の処理要素は、それに割り当てられる状態の
ｉ個のＭＳＢによって識別されるとする。例えば、処理
要素（００）、すなわちＰＥ（００）は、符号状態０〜
７を処理し、ＰＥ（０１）は符号状態８〜１５を処理
し、などとなる。
【００３６】上記のような符号状態の処理要素への割当
ての下では、処理要素間の通信はほとんど一様である。
例えば、図１の（ａ）の符号器１０の３２状態レート２
／３バージョンに対する４個の処理要素の復号器では、
状態（ａｂｃｄｅ）の先行状態は状態（００ａｂｃ）、
（０１ａｂｃ）、（１０ａｂｃ）および（１１ａｂｃ）
である。状態（ａｂｃｄｅ）はＰＥ（ａｂ）によって計
算され、その先行状態はそれぞれＰＥ（００）、ＰＥ
（０１）、ＰＥ（１０）およびＰＥ（１１）によって計
算される。こうしてＰＥ（ａｂ）は常に、割り当てられ
た状態に対するパスメトリックを計算する前に、復号器
内の４個の処理要素のそれぞれによって生成されるパス
メトリックにアクセスする。４個の処理要素間の同様に
一様な通信が、（ｃｄｅ）の値に関わらず（ａｂ）のす
べての値に対して得られる。より一般的にいえば、２i
個の処理要素を使用して２j状態レートｋ／ｎ畳込み符
号を復号する場合、状態（ｍj-1...ｍ1ｍ0）の先行状態
は、ｚ0，ｚ1，...，ｚk-1のすべての可能な値に対して
（ｚk-1...ｚ1ｚ0ｍj-1...ｍ1ｍ0）となる。処理要素通
信パターンはｉおよびｋの相対的な値に依存する。ｉ＜
ｋの場合、ＰＥ（ｄi-1...ｄ1ｄ0）は２i個の処理要素
のそれぞれからの２k-1個のパスメトリックにアクセス
する。ｉ≧ｋの場合、ＰＥ（ｄi-1...ｄ1ｄ0）は、
ｚ0，ｚ1，...，ｚk-1のすべての可能な値に対して２i
個の処理要素ＰＥ（ｚk-1...ｚ1ｚ0ｄi-1...ｄk+1ｄk）
のそれぞれからの１個のパスメトリックにアクセスす
る。いずれの場合にも、各処理要素に対する通信パター
ンは、特定のＰＥ（ｄi-1...ｄ1ｄ0）に割り当てられる
符号状態の特定のグループとは独立である。
【００３７】本発明のもう１つの特徴には、符号器内の
各処理要素に対するパスメトリックのアクセスおよび計
算のスケジュールを決定することが含まれる。上記のよ
うに、２jの符号状態は、例えばｉ個のＭＳＢの共通セ
ットに基づいて、分割され復号器処理要素に割り当てら
れる。２i個の処理要素はそれぞれ、時分割方式でＦ個
の状態に対するパスメトリックを計算するために使用さ
れる。ただしＦは折返し係数であり、２j-1に等しい。
特に、ＰＥ（ｄi-1...ｄ1ｄ0）は、ｚ0，ｚ1，...，ｚ
k-1のすべての可能な値に対して符号状態（ｄi-1...ｄ1
ｄ0ｚj-i-1...ｚ1ｚ0）に対するパスメトリックを計算
する。１つの可能なパスメトリック計算スケジュール
は、符号状態の昇順に従うことである。次の表１に、３
２状態レート２／３符号および４個の処理要素復号器に
対して、昇順符号状態に基づいた、パスメトリック計算
スケジュールの例を示す。
【００３８】
【表１】
【００３９】表１では、時刻ｔ０〜ｔ７は復号器におけ
るクロックサイクルを表す。各処理要素は、各復号器ク
ロックサイクル中に１個の符号状態に対する新たなパス
メトリックを計算する。復号器クロックサイクルｔ０〜
ｔ７は、受信符号シンボルごとに繰り返す。各行の番号
は、与えられた復号器クロックサイクル中に特定の処理
要素で新たなパスメトリックが計算される符号状態を表
す。例えば、ＰＥ（００）は、状態分割において符号状
態（００ｘｘｘ）に割り当てられており、８個の復号器
クロックサイクルにわたって符号状態０、１、２、３、
４、５、６および７に対する新たなパスメトリックを昇
順に計算する。この例の３２状態４処理要素復号器に対
する折返し係数Ｆは８である。Ｆが８であり、従って各
処理要素が受信符号シンボルごとに時分割方式で８個の
異なる符号状態に対する新たなパスメトリックを計算す
るので、表１には８個の復号器クロックサイクルｔ０〜
ｔ７が示されている。
【００４０】表１で指定される符号状態に対するパスメ
トリックを計算するため、各処理要素は、その処理要素
に割り当てられた計算済みパスメトリックを含む、計算
済みパスメトリックの適当なセットにアクセスしなけれ
ばならない。計算済みパスメトリックとは、復号器で受
信した符号シンボルのストリーム中で前の符号シンボル
に対して計算されたパスメトリックである。このよう
に、現符号シンボルに対して計算される新たなパスメト
リックは、ストリーム中の次の符号シンボルに対する計
算済みパスメトリックとして使用される。上記のよう
に、状態（ａｂｃｄｅ）に対する新たなパスメトリック
を計算するために、処理要素ＰＥ（ａｂ）は先行状態
（００ａｂｃ）、（０１ａｂｃ）、（１０ａｂｃ）およ
び（１１ａｂｃ）に付随するパスメトリックにアクセス
する必要がある。次の表２に、４個の処理要素を有する
３２状態レート２／３復号器の場合のアクセススケジュ
ールの例を示す。明確にするために、与えられた処理要
素がアクセスする必要がある計算済みパスメトリックの
セットは、以下の説明では各括弧で囲むことにする。一
般に、次の表２は、ＰＥ（ａｂ）は、（ｃｄｅ）の昇順
に、計算済みパスメトリック［（００ａｂｃ），（０１
ａｂｃ），（１０ａｂｃ），（１１ａｂｃ）］にアクセ
スすることを必要とすることを示している。従って、Ｐ
Ｅ（ａｂ）は、復号器クロックサイクルｔ０〜ｔ３中に
パスメトリックのセット［（００ａｂ０），（０１ａｂ
０），（１０ａｂ０），（１１ａｂ０）］にアクセス
し、復号器クロックサイクルｔ４〜ｔ７中にパスメトリ
ックのセット［（００ａｂ１），（０１ａｂ１），（１
０ａｂ１），（１１ａｂ１）］にアクセスする。例え
ば、ＰＥ（００）は、状態０、１、２および３に対する
パスメトリックを計算するために、復号器クロックサイ
クルｔ０〜ｔ３中に、パスメトリック［（００００
０），（０１０００），（１００００），（１１００
０）］、すなわち［０，８，１６，２４］にアクセスす
る。状態０、８、１６、および２４は、３２状態レート
２／３トレリスにおいて状態０、１、２および３の先行
状態である。同様に、状態１、９、１７および２５は、
状態４、５、６および７の先行状態である。表２のアク
セススケジュールは、表１においてパスメトリックが計
算される３２個の符号状態のそれぞれに対する先行状態
の適当なセットを示す。復号器クロックサイクルのセッ
トｔ０〜ｔ８は、受信符号シンボルごとに反復されるの
で、符号シンボル周期ともいう。
【００４１】
【表２】
【００４２】注意すべき点であるが、表１および表２で
は、パスメトリック計算スケジュールとパスメトリック
アクセススケジュールの間には不一致がある。表２で
は、与えられた処理要素によってアクセスされる計算済
みパスメトリックは、前符号シンボル周期における同じ
復号器クロックサイクル中にそれぞれ計算された。例え
ば、ＰＥ（１１）は、現符号シンボル周期のクロックサ
イクルｔ０においてメトリック［６，１４，２２，３
０］にアクセスするが、これらのメトリックはすべて、
前符号シンボル周期のクロックサイクルｔ６中に計算さ
れたものである。その結果、符号状態値の昇順に基づく
この実施例では、前符号シンボルに対するパスメトリッ
クを計算して適当な処理要素に送るにはクロックサイク
ルが少なすぎるため、次の符号シンボルに対する新たな
パスメトリックを計算することができない可能性があ
る。ＰＥ（１１）の場合には、ＰＥ（１１）は次の符号
シンボル周期のクロックサイクルｔ０において状態２４
に対する新たなパスメトリックを計算するのに、２個の
クロックサイクルｔ６およびｔ７のみが、４個のパスメ
トリック［６，１４，２２，３０］のすべてを計算し送
信するために利用可能である。
【００４３】本発明のもう１つの実施例は、符号状態の
昇順に基づくメトリック計算スケジューリングに固有の
潜在的なタイミング制限を軽減する。この実施例では、
各処理要素に対するメトリックの計算およびアクセスの
スケジュールは時間的にずらされる（オフセットされ
る）。その時間オフセットは、例えば、ＰＥ（ａｂ）の
計算およびアクセスのスケジュールを（ａｂ）復号器ク
ロックサイクルだけずらすことによって実現される。従
って、２i個の処理要素を有する復号器では、各処理要
素の計算およびアクセスのスケジュールはｉ個の復号器
クロックサイクルだけずらされる。３２状態レート２／
３復号器に対する時間オフセット設定の例をそれぞれ表
３および表４のメトリックの計算およびアクセスのスケ
ジュールに示す。この例では、ＰＥ（００）のスケジュ
ールは不変であり、ＰＥ（０１）、ＰＥ（１０）および
ＰＥ（１１）のスケジュールはそれぞれ１、２および３
個の復号器クロックサイクルだけずらされる。
【００４４】
【表３】
【００４５】
【表４】
【００４６】表３および表４のパスメトリックの計算お
よびアクセスのスケジュールは、各処理要素に対して、
計算済みメトリックの適当なセットへの順アクセスを提
供しており、これによって、表１および表に２の並列ア
クセススケジュールよりも改善されている。表２におけ
るＰＥ（００）の動作は並列パスメトリックアクセスの
例を提供する。例えば、表２は、ＰＥ（００）が、クロ
ックサイクルｔ０、ｔ１、ｔ２およびｔ３中に状態０、
１、２および３に対する新たなパスメトリックを計算す
るために、クロックサイクルｔ０から開始して並列にパ
スメトリック［０，８，１６，２４］にアクセスしなけ
ればならないことを示している。この理由は、新たなパ
スメトリックを計算する第１の状態すなわち状態０が、
状態０、８、１６および２４からの計算済みパスメトリ
ックを必要とするためである。これに対して、表４によ
れば、状態０、８、１６、２４に対する計算済みパスメ
トリックはクロックサイクルｔ０、ｔ１、ｔ２およびｔ
３中に順次アクセスされるが、新たなパスメトリックは
状態０、１、２および３に対して同時に計算される。同
様に、復号器内の各処理要素は、そのセット内の計算済
みパスメトリックに順にアクセスする。本発明のこの順
アクセス実施例で使用するのに適した処理要素設計の例
については後述する。上記の復号器クロックサイクルオ
フセットおよび同時メトリック計算の利点は、処理要素
間の通信のバースト性をなめらかにすることにつながる
ため、ハードウェア効率を改善することである。
【００４７】表１および表２のスケジュールに伴う潜在
的なタイミング制限は表３および表４のスケジュールに
示したタイミングオフセットを使用することによって軽
減されるが、理解されるように、本発明による面積効率
の良い高符号レート復号器は、表１および表２のスケジ
ュールに基づいても構成することができる。例えば、本
発明のパイプライン化した処理要素およびメトリック再
配列技術（いずれも詳細は後述）は、復号器クロックサ
イクルをずらさずに、計算済みパスメトリックへの順ア
クセスを提供する。このような実施例は、他の処理要素
でパスメトリックを計算しながら、与えられた処理要素
のパイプラインに計算済みまたは部分的に計算済みのパ
スメトリックを一時的に記憶することによって、復号器
のタイミングを改善する。
【００４８】本発明のもう１つの特徴には、メトリック
アクセススケジュールを実装するためのメトリック再配
列技術が含まれる。表３および表４のスケジュールはメ
トリック再配列の概念を例示している。例えば、ＰＥ
（００）は、０、１、２、３、４、５、６、７の順序で
パスメトリックを計算するが、これらのメトリックはＰ
Ｅ（００）および他の３個の処理要素によって、０、
２、４、６、１、３、５、７の順序でアクセスされる。
このように、メトリックアクセスシーケンスはメトリッ
ク計算シーケンスの４ウェイ交錯である。表３および表
４の他の処理要素もまた、それらの計算スケジュールの
４ウェイ交錯バージョンであるようなアクセススケジュ
ールを示す。ハードウェア効率をさらに改善するために
は、新たなパスメトリックは、所望のアクセススケジュ
ールに従って順にアクセスされるように、計算後に再配
列することができる。このように再配列は、後のパスメ
トリック計算に対するスケジューリングされたアクセス
を容易にする。表４の例では、計算されたメトリックは
４ウェイ交錯によって再配列されるべきである。４ウェ
イ交錯を実行するための従来技術の例では、計算したメ
トリックのシーケンスを４×２メモリアレイに行の順序
で記憶した後、列の順序で読み出すことによって所望の
シーケンスでメトリックにアクセスする。
【００４９】一般に、レートｋ／ｎ畳込み符号では、所
望のメトリック再配列は代表的には２p個のメトリック
の２qウェイ交錯によるものである。ただしｐおよびｑ
はアプリケーションに依存する。ｉ≧ｋの復号器では、
ｐ＝ｊ−ｉであり、ｑ＝ｋである。ｉ＜ｋの復号器で
は、時分割の結果として、メトリック再配列は一般に追
加の分割および反復を含む。上記の例における４×２メ
モリアレイのような転置メモリなどのメモリまたはレジ
スタに基づく技術は、２qウェイ交錯を実現するために
使用可能である。他の交錯技術には、シフト交換ユニッ
ト（ＳＥＵ）と呼ばれる超大規模集積（ＶＬＳＩ）構造
の使用がある。ＳＥＵは一般的に、いくつかのパイプラ
イン化されたラッチを有し、パイプラインデータの固定
サイズ置換を実装する（詳細は図１１について後述）。
ＳＥＵの詳細は、例えば、上記のシー．ビー．シュンほ
かによる論文に記載されている。本発明のアクセススケ
ジュールを提供するためにメトリックを再配列するに
は、他の交錯技術を使用することも可能である。
【００５０】これから、ＳＥＵなどの回路構造を使用し
てデータ点の２qウェイ交錯を実装するのに適した、本
発明によるメトリック再配列技術について説明する。例
示的な再配列技術について説明するために、４個の処理
要素を有する６４状態レート２／３畳込み符号に対する
復号器の例を用いる。この例では、ｊ＝６、ｋ＝２およ
びｉ＝２である。状態（ａｂｃｄｅｆ）に対するパスメ
トリックはＰＥ（ａｂ）によって（ｃｄｅｆ）の昇順に
計算され、状態（ｘｘａｂｃｄ）、すなわち、状態（ａ
ｂｃｄｅｆ）の先行状態に対するパスメトリックは、時
間オフセット（ａｂ）で、（ｃｄｅｆ）の昇順にアクセ
スされる。時間オフセット（ａｂ）の量は（ｅｆ）の昇
順に同期するため、メトリックは（ｘｘｅｆｃｄ）と同
期してアクセスされる。このようにして、理解されるよ
うに、パスメトリック計算とアクセスシーケンスを同期
させるためには、ＰＥ（ａｂ）は、計算するパスメトリ
ックを、計算シーケンス（ａｂｃｄｅｆ）からアクセス
シーケンス（ａｂｅｆｃｄ）に再配列すべきである。こ
れは、１６個のデータ点の４ウェイ交錯と同等である。
４ウェイメトリック交錯が必要であることはＰＥ（０
０）の作用において理解される。ＰＥ（００）は、０、
１、２、３、４、５、６、７、８、９、１０、１１、１
２、１３、１４、１５の順でメトリックを計算するが、
これらのメトリックは、０、４、８、１２、１、５、
９、１３、２、６、１０、１４、３、７、１１、１５の
順でＰＥ（００）、および復号器内のその他の処理要素
によってアクセスされる。
【００５１】図６および図７に、本発明によるメトリッ
ク再配列技術の２つの例を示す。メトリック再配列は、
例示的な、４個の処理要素を有する６４状態レート２／
３復号器内のＰＥ（００）によって計算される１６個の
パスメトリックの昇順シーケンスを使用して示される。
一般的には、本発明の再配列技術は以下の３つのステッ
プを含む。第１に、与えられた処理要素によって計算さ
れるパスメトリックのセット、あるいはさらに一般的に
は、再配列を必要とするデータ点の任意のセットを、少
なくとも２つのグループに分割し、各グループが相異な
るスロットに対応するようにする。ここでスロットとは
一般にデータ点のグループの順列をいう。例えばスロッ
トは、復号器処理要素内のラッチなどの一時記憶要素の
順序グループを表す。各スロットはいくつかのスロット
位置を含み、各スロット位置は一般に、例えば単一のパ
スメトリックのような単一のデータ点によって占められ
る。従って各スロット位置は復号器内の単一の一時記憶
要素に対応する。スロットサイズとは、与えられたスロ
ット内のスロット位置の数をいう。以下で説明する例
は、再配列プロセス中の各ステップで同一のスロットサ
イズを有するスロットを使用するが、データ点は、与え
られた再配列ステップでいくつかの異なるサイズのスロ
ットに分割することも可能である。第２に、１スロット
内のあるスロット位置に記憶されるデータ点は、与えら
れたステップサイズの置換をデータ点に適用することに
よって、他のスロット内の異なるスロット位置に移動さ
れる。移動されるデータ点は、現在のスロット内で正し
くないスロット位置を占めるものであることもあり、ま
た、各データ点に対する現在のスロット位置を所望のス
ロット位置と比較することによって識別されるものであ
ることもある。置換ステップサイズは、与えられたデー
タ点が移動の結果としてシフトされるスロット位置の総
数である。最後に、データ点をスロットに分割するステ
ップおよび置換を適用するステップは、データ点の所望
の順列が得られるまで、異なるスロットサイズを用いて
再帰的に反復される。スロットサイズは一般に再配列ス
テップの反復とともに減少する。また、ステップサイズ
は一般に新たなスロットサイズとともに変化し、データ
点配列における所望の置換を提供するために、与えられ
たスロットサイズに対していくつかの異なるステップサ
イズを使用することも可能である。
【００５２】図６は、本発明による直接移動メトリック
再配列を示す。再配列プロセスの各ステップに示されて
いるデータ点のセットは、例えば、与えられた符号シン
ボルに対して復号器処理要素によって計算されたパスメ
トリックのセットを表す。データ点の列は、例えば、一
時記憶要素のグループに記憶される。破線が、データ点
のセットを２つのグループすなわちスロットに分割し、
各スロットは８個のスロット位置を含む。ステップ１
で、現在のデータ点のスロット位置を所望のスロット位
置と比較する。第１および第２のスロットにおいてそれ
ぞれ円および四角によって示されるような正しくないス
ロット位置のいくつかのデータ点を、他のスロット内の
異なるスロット位置に直接移動する。ステップ１は、ス
テップサイズが６の固定ステップ置換を使用し、移動さ
れる各データ点はスロット位置６個分だけシフトされ
る。この手続きは、図６のステップ２に示すように、よ
り小さいスロットサイズを使用して反復される。ステッ
プ２では、データ点を含む記憶要素は、破線によって分
割して示してあるように、４個のスロットに再分割され
る。再び、第１および第３のスロットの円ならびに第２
および第４のスロットの四角によって示される正しくな
いスロット位置のいくつかのデータ点を、他のスロット
の異なる位置に直接移動する。ステップ２では、ステッ
プサイズが３の固定ステップ置換が使用される。ステッ
プ３に示されるように、ステップ２におけるデータ点の
移動は各データ点を正しい位置に配置し、さらに分割お
よび移動を行う必要はない。こうして、図６のステップ
１および２は１６個のデータ点の４ウェイ交錯を実行し
た。上記の例では、１６個のデータ点は６４状態復号器
内のＰＥ（００）によって計算されるパスメトリックで
あるが、このパスメトリックは、一時記憶要素からまた
はメモリから単に順に読み出すことによって所望の順序
でアクセスすることができるようになった。上記の直接
移動法では、置換ステップサイズは単調減少である。し
かし、データ点が多数の場合、ステップサイズすなわち
データ点が移動しなければならないスロット位置の数
は、最初は非常に大きい。大きい初期ステップサイズ
は、例えばＳＥＵを使用してこの技術をハードウェア実
装する際には長い配線長が必要となるため、好ましくな
いことがある。
【００５３】図７は、直接移動法の長い初期ステップサ
イズの制限を解決するもう１つのメトリック再配列技術
（収集移動法と呼ぶ）の図である。図７の例では、収集
移動法は、図６のステップ１および２における長いほう
の各移動を２つの短い移動に分割する。短いほうの移動
の第１のものは、ステップ１ａに示したように、スロッ
トサイズは８、ステップサイズは２を用いて、正しくな
いデータ点を２つの記憶スロットの隣接する端部に収集
する。例えば、ステップ１ａにおけるパスメトリック
２、３は、これらの正しくないパスメトリックを２つの
記憶スロットの間の境界付近に収集するためにパスメト
リック４、５と交換され、パスメトリック１２、１３
は、パスメトリック１０、１１と交換される。データ点
が隣接するスロットの隣接する端部の境界付近に収集さ
れた後、ステップ１ｂに示したように、第２の短い移動
が、正しくないデータ点を、スロット境界を越えて隣接
するスロットの別の位置に移動させる。その後このプロ
セスは、ステップ２ａおよび２ｂに示したように、スロ
ットサイズを４として反復される。ステップ３までに、
すべてのデータ点は所望のスロット位置に入り、この収
集移動再配列プロセスは完了する。この再配列技術は、
高レートビタビ復号器で計算されたパスメトリックの再
配列に特に適しているが、複数のデータ点を交錯するこ
とを含む他のアプリケーションにも有用であることが理
解されるべきである。
【００５４】上記の直接移動法および収集移動法による
メトリック再配列は、例えば、固定ステップ置換を行う
いくつかのＳＥＵを縦続することによって実装される。
このような実装は、レート１／ｎ畳込み符号の場合に
は、例えば、エイチ−ディ．リン(H-D. Lin)他、「畳込
み符号に対する折返しビタビ復号器(Folded Viterbi De
coders for Convolutional Codes)」、IEEE VLSI Signa
l Processing、第ＩＶ巻、IEEE Press（１９９０年）、
および、シー．ビー．シュンほかの前掲論文に記載され
ている。各ＳＥＵは、与えられたステップサイズの固定
ステップ置換を行う。例えば、図６のメトリック再配列
は、ステップサイズ６の固定ステップ置換を行うＳＥＵ
と、ステップサイズ３の固定置換を行うもう１つのＳＥ
Ｕからなる２個のＳＥＵを縦続することによって実装可
能である。縦続したＳＥＵの出力は、図６のステップ３
に示したような所望の順序のデータ点となる。従って、
注意すべき点であるが、各ＳＥＵは本来的に上記のデー
タ点をスロットに分割するステップと置換を行うステッ
プとの両方を備えている。スロットサイズは、ＳＥＵの
置換ステップサイズに依存する。スロットに分割するス
テップおよび置換を行うステップは、異なる置換ステッ
プサイズを有するＳＥＵにデータ点を通すことにより異
なるスロットサイズを使用して反復される。
【００５５】一般に、ＳＥＵで使用されるパイプライン
ラッチの数は、置換ステップサイズに対応する。従っ
て、ハードウェアの複雑さは、置換ステップサイズの最
小和を与える再配列方法を選択することによって縮小さ
れる。図６および図７の６４状態レート２／３復号器の
例では、直接移動法によるステップサイズの和は６＋３
＝９である一方で、収集移動法によるステップサイズの
和も２＋４＋１＋２＝９となる。しかし、理解されるべ
き点であるが、他の多くのアプリケーションでは、各方
法におけるステップサイズ和は異なる。例えば、８個の
データ点の４ウェイ交錯の場合、直接移動法を使用した
ときのステップサイズ和は３＋１＝４であるが、収集移
動法を使用したときのステップサイズ和は１＋２＝３で
ある。
【００５６】上記の再配列方法はいずれも、例えば従来
技術の転置メモリ法よりも効率的である。６４状態レー
ト２／３の例では、直接移動法および収集移動法のいず
れも、ステップサイズ和は９であり、全部で９個のみの
パイプラインラッチを有する縦続ＳＥＵを使用して１６
個のデータ点の４ウェイ交錯を実行することができる。
これに対して、転置メモリ法は、例えば、４×４メモリ
アレイ、すなわち、全部で１６個の記憶要素を必要とす
る。さらに、本発明の再配列技術は、パスメトリック計
算を中断せずに、６４状態レート２／３の場合には９個
の復号器クロックサイクル以内にパスメトリックを再配
列することができ、シンボル周期中の全部で１６個の復
号器クロックサイクルのうちの７個を、パスメトリック
計算および分配のパイプライン化のために残すことがで
きる。
【００５７】要約すれば、面積効率の良い復号器アーキ
テクチャは、図２〜図５とともに上記で定義したとおり
である。本発明の面積効率の良い復号器は、処理要素を
使用して、例えば、上記の表１および表３に示したよう
な計算スケジュールに従ってメトリックを計算する。ま
た、処理要素は、例えば表２および表４に示したような
アクセススケジュールに従ってメトリックを再配列する
ＳＥＵのようなメトリック再配列ハードウェアも含む。
メトリック再配列は、図６および図７に示した再配列方
式のうちの１つを使用して実現される。図２、図４の
（ａ）および図５の（ａ）のそれぞれの処理要素４２、
６２および８２は、メトリックの計算および再配列の両
方の機能を行うように設計することが可能であり、対応
するメトリック出力分配ノード４４、６４、８４は、再
配列したメトリックを適当な処理要素に分配する。
【００５８】上記のように、従来の復号器処理要素は一
般に並列に計算済みパスメトリックにアクセスしそれを
更新した後、更新したメトリックのうち最小のものを現
在のトレリスノードの新しいパスメトリックとして選択
する。図８に、並列メトリックアクセスを使用する従来
の処理要素１０５を示す。処理要素１０５は、レートｋ
／ｎ畳込み符号の復号器で使用可能である。一般に、レ
ートｋ／ｎ畳込み符号では、並列アクセス処理要素は、
２k個の並列メトリック入力と、２k個の加算器と、２k
−１個の比較／選択ユニットを必要とする。従って、処
理要素１０５は、４個のメトリック入力（図８では
ΓA、ΓB、ΓCおよびΓDで示す）と、４個の加算器１１
２と、３個の比較／選択ユニット１２０を有する。各比
較／選択ユニット１２０は、比較器１２２および選択器
１２４を有する。選択器１２４は、例えば、２：１マル
チプレクサである。加算器１１２および比較／選択ユニ
ット１２０は、まとめて、加算比較選択（ＡＣＳ）ユニ
ットと呼ばれることが多い。各加算器１１２は入力とし
て４個のパスメトリックのうちの１つを受信する。例え
ば、処理要素１０５が表２のアクセススケジュールを有
するＰＥ（００）として使用される場合、ΓA、ΓB、Γ
CおよびΓDはそれぞれ状態０、８、１６および２４に対
する計算済みパスメトリックに対応する。処理要素１０
５はまた、与えられた受信符号シンボルに対して、特定
の状態遷移の尤度を示すブランチメトリックを含むブラ
ンチメトリックテーブル１１０も有する。テーブル１１
０からのブランチメトリックは計算済みパスメトリック
と加算器１１２で加算され、隣接する加算器の結果は比
較／選択ユニット１２０で比較され、最小の和が新たな
パスメトリックとして選択される。このように、処理要
素１０５の出力は、パスメトリックΓA、ΓB、ΓCおよ
びΓDの先行状態を有する符号状態に対応して、新たな
パスメトリックΓEとなる。再び処理要素１０５を表２
のＰＥ（００）とすると、ΓA、ΓB、ΓCおよびΓDがそ
れぞれ状態０、８、１６および２４である場合、新たな
パスメトリックΓEは状態０に対する新たなパスメトリ
ックとなる。従来の処理要素１０５は、既に詳細に説明
したように、一般に高レート符号に対する面積効率の良
い復号器アーキテクチャを提供することができない。
【００５９】図９に、本発明による順アクセス処理要素
１３５を示す。処理要素１３５は、ブランチメトリック
テーブル１４０およびいくつかの加算器１４２を有す
る。単一の計算済みパスメトリックΓAが、直列メトリ
ック入力を通じて同時に各加算器１４２に供給され、テ
ーブル１４０からの適当なブランチメトリックと加算さ
れる。テーブル１４０は、適当なタイプのメモリを使用
して実現され、他の実装での処理要素１０５の外部に記
憶されることが可能である。比較／選択ユニット１５０
は、各加算器１４２の出力をラッチ１４６の内容と比較
する。ラッチ１４６は一部計算パスメトリックを記憶
し、すべての可能な先行状態に対する計算済みパスメト
リックは順に更新される。ここで、一部計算パスメトリ
ックとは、まだすべての可能な計算済みパスメトリック
を更新し、比較し、選択していないようなパスメトリッ
クをいう。例えば、上記の表３および表４を参照する
と、ＰＥ０は、復号器クロックサイクルｔ０、ｔ１、ｔ
２およびｔ３にわたって状態０、１、２、および３に対
するパスメトリックを同時に計算し、一方、状態０、
８、１６、および２４に対する計算済みパスメトリック
に順次アクセスする。例えば復号器クロックサイクルｔ
０中には、状態０に対する計算済みパスメトリックのみ
がアクセスされる。ただ１つの計算済みパスメトリック
のみがアクセスされるため、状態０に対する新たなパス
メトリックを完全に計算することはできない。従って、
この一部計算メトリックは、次の復号器クロックサイク
ルｔ１（このｔ１中に状態８に対する計算済みパスメト
リックがアクセスされる）までラッチ１４６に記憶され
る。その後、ラッチ１４６に記憶された状態０に対する
一部計算パスメトリックは、加算器１４２からの、状態
８に対する計算済みパスメトリックと適当なブランチメ
トリックとの和とともに、比較／選択ユニット１５０で
処理される。その結果は再び、状態０に対する一部計算
パスメトリックとしてラッチ１４６に記憶される。復号
器クロックサイクルｔ３の後、状態０、８、１６および
２４に対する計算済みパスメトリックがすべてアクセス
されると、状態０、１、２および３に対する新たなパス
メトリックはすべて完全に計算される。
【００６０】処理要素１３５で計算されたパスメトリッ
クはΓH、ΓG、ΓFおよびΓEとラベルされ、表３および
表４のＰＥ０の例では状態０、１、２、および３に対す
る新たなパスメトリックに対応する。これらの新たなパ
スメトリックが計算されている間、入力パスメトリック
ΓAは、復号器クロックサイクルｔ０、ｔ１、ｔ２およ
びｔ３にわたって、符号状態０、８、１６および２４に
対する計算済みパスメトリックを表す。完全に計算され
ると、これらの新たなパスメトリックはそれぞれ、いく
つかのＳＥＵ１５６を含むメトリック再配列手段にロー
ドされ、そこでメトリック再配列が上記のようにして実
行される。メトリック再配列手段は、処理要素１３５に
よって計算されたメトリックが復号器内の他の処理要素
によって正しくアクセスされることを保証する。順アク
セス処理要素１３５は、１個だけのメトリック入力と、
２k個の加算器と、２k個の比較／選択ユニットを使用す
る。さらに、一度に１個の計算済みパスメトリックへの
順アクセスを使用して４個のメトリックを計算するた
め、一部計算パスメトリックの記憶のために２k個のラ
ッチを使用する。ＳＥＵ１５６への新たなパスメトリッ
クΓH、ΓG、ΓFおよびΓEのロードは、さらに適当な初
期順序にメトリックを配列することによって、符号構造
に依存して、あるアプリケーションではメトリック再配
列を容易にするために使用することができる。
【００６１】図１０に、本発明による順アクセス処理要
素のもう１つの実施例を示す。処理要素１６０は、ブラ
ンチメトリックテーブル１６１と、計算済みパスメトリ
ックΓAを処理要素１６０に順次提供する直列メトリッ
ク入力と、単一の加算器１６２を有する。処理要素１６
０は、パイプライン化したラッチを使用して、図９の復
号器実施例における複数の加算器と比較／選択ユニット
の機能を結合する。加算器１６２は、計算済みパスメト
リックΓAをテーブル１６１からの適当なブランチメト
リックに加算する。パイプライン化された処理要素１６
０は、例えば一部計算メトリックΓEを記憶するパイプ
ラインラッチ１６６と、比較器１６８と、比較器１６８
の出力を記憶するパイプラインラッチ１７０と、新たな
パスメトリックを計算する際にラッチ１７０の出力のう
ちの１つを選択する２：１選択器１７２を有する。この
実施例の処理要素１６０にはさらにパイプラインラッチ
の対１７４、１７６が含まれる。ラッチ１７４、１７６
もまた一部計算パスメトリックを記憶する。これらは後
でラッチ１６６にフィードバックされ、新たなパスメト
リックを計算する際に使用される。ラッチ１６６、１７
０、１７４および１７６の直列配置はともにいくつかの
復号器クロックサイクルにわたって一部計算パスメトリ
ックを記憶する。例えば、処理要素１６０が表３および
表４のＰＥ０として使用される場合、クロックサイクル
ｔ０、ｔ１、ｔ２およびｔ３にわたって、ΓAはそれぞ
れ状態０、８、１６および２４に対する計算済みパスメ
トリックを表す。４個のラッチ１６６、１７０、１７４
および１７６は、状態０、８、１６および２４に対する
計算済みパスメトリックがすべてアクセスされるまで、
４個の復号器クロックサイクルｔ０、ｔ１、ｔ２および
ｔ３にわたって加算、比較および選択の演算結果を一時
的に記憶する。比較器１６８および選択器１７２はラッ
チの直列配置の内部に配置され、いくつかの復号器クロ
ックサイクルにわたって、一時的に記憶されている値を
使用して、新たなパスメトリックのセットを計算する。
もちろん、処理要素１６０内のラッチの配置は例示のみ
のものであって、ラッチは、いくつかの別法のうちの任
意のものによって配置可能である。例えば、ラッチ１７
０および１７４はいずれも、比較器１６８の前または選
択器１７２の後に配置することが可能である。
【００６２】新たなパスメトリックは、完全に計算され
ると、少なくとも１つのＳＥＵ１７８を含むメトリック
再配列手段１８０に供給される。メトリック再配列手段
１８０は、与えられたアプリケーションの要求に応じ
て、他のタイプの記憶要素とともに、追加のＳＥＵを含
むことも可能である。処理要素１６０は、図８に示した
従来のレートｋ／ｎ処理要素１０５よりもかなり複雑さ
が少ない。実際、処理要素１６０の複雑さは、レート１
／ｎ復号器に対する従来の処理要素の複雑さのオーダー
である。
【００６３】図１１の（ａ）〜（ｃ）に、図９および図
１０の処理要素で使用するのに適したＳＥＵの例を示
す。図１１の（ａ）は、パスメトリック入力２０１と、
選択器２０２、２０４と、一対のパイプラインラッチ２
０６、２０８と、選択器２０２、２０４へのもう１つの
入力を提供するパイプライン出力２０９を有するＳＥＵ
２００を示す。各選択器２０２、２０４は、選択器に送
られる外部制御信号に応じて、２つの入力のうちのいず
れを出力へと通過させるかを選択するように設計され
る。例えば、選択器２０２は、ライン２０１またはライ
ン２０９のいずれかからのデータを出力へと通過させる
ように構成される。この出力はラッチ２０６を駆動す
る。これらの選択器は、選択器Ｓ１が上の入力を選択す
るように作用した場合に、対応する選択器Ｓ１´が下の
入力を選択するように作用し、逆の場合も同様となるよ
うに、相補的に動作する。実施例のＳＥＵ２００への入
力はメトリックのシーケンス［ｘ，ｙ，ｚ］である。ラ
ッチ２０８はメトリックｘを含み、ラッチ２０６はメト
リックｙを含み、メトリックｚはＳＥＵ入力２０１にあ
る。選択器に適当な外部制御信号を加えることによっ
て、実施例のＳＥＵ２００は、例えば、メトリックの相
対的な順序［ｘ，ｙ，ｚ］を保存するか、または、その
順序を［ｚ，ｘ，ｙ］に変更するように作用する。図１
１の（ｂ）に、選択器２２４がラッチ出力２２９を選択
し、その結果、メトリックｘがＳＥＵ２２０の出力に供
給され、一方メトリックｙはラッチ２２８にラッチさ
れ、メトリックｚはラッチ２２６にラッチされるという
ＳＥＵ２２０の状態を示す。この場合、ＳＥＵ２２０
は、メトリックの順序を保存する状態にある。図１１の
（ｃ）には、選択器２４２がラッチ出力２４９を選択す
るというＳＥＵ２４０を示す。その結果、メトリックｚ
はライン２４１を通じて選択器２４４に送られ、そこか
らＳＥＵ２４０の出力に送られる。同時に、メトリック
ｘはラッチ２４６に記憶され、メトリックｙはラッチ２
４８にシフトされる。この場合、ＳＥＵ２４０は、入力
メトリックの順序を［ｘ，ｙ，ｚ］から［ｚ，ｘ，ｙ］
に変換するように作用し、従って、ステップサイズ２の
固定ステップ置換を行うことになる。
【００６４】メトリック再配列を実装するためのパイプ
ライン化ＳＥＵの代替例には、例えばケー．パーリ(K.
Parhi)、「寿命解析および前方−後方レジスタ配置を用
いたＤＳＰデータフォーマット変換器の組織的合成(Sys
tematic Synthesis of DSP Data Format Converters Us
ing Life-Time Analysis and Forward-Backward Regist
er Allocation)」、IEEE Trans. on Circuits and Syst
ems、第３９巻第７号第４２３〜４４０ページ（１９９
２年７月）、および、ケー．パーリ(K. Parhi)、「最小
数のレジスタを用いたビデオデータフォーマット変換器
(Video Data Format Converters Using Minimum Number
of Registers)」、IEEE Trans. on Circuits and Syst
ems for Video Technology、第２巻第２号第２５５〜２
６７ページ（１９９２年６月）、に記載されているデー
タフォーマット変換器がある。
【００６５】ここまでの詳細な説明は、主にレートｋ／
ｎ畳込み符号の場合の本発明の説明であるが、トレリス
型の状態遷移を有する他のタイプの符号も使用可能であ
ることは理解されるべきである。説明した構成にはさま
ざまな変形が可能である。例えば、符号状態を処理要素
に割り当てるのに別の方式を使用すること、パスメトリ
ックの計算およびアクセスのスケジュールに別の時間オ
フセット量を適用すること、他のメトリック再配列方式
を使用すること、復号器処理要素の構造および相互接続
を変更することが可能である。さらに、ここで開示した
メトリック再配列方式は、交錯符号化において使用する
のに好適であり、処理要素の構造は、他の復号アプリケ
ーションでも使用可能である。
【００６６】
【発明の効果】以上述べたごとく、本発明によれば、高
レートトレリス符号の最尤復号が実現される。従って、
与えられた符号化方式によって、大幅に符号化利得が改
善され、その結果、多くの高レート復号器で現在利用さ
れている次善の復号に比べて帯域幅効率が改善される。
本発明のもう１つの特徴的な効果として、復号器の複雑
さが大幅に縮小され、その結果、復号器を実装するのに
必要な回路面積が大幅に減少する。従って、本発明は、
実用的かつ費用効率の良い方法で、高レート符号による
帯域幅効率の利点を達成することができる。
【図面の簡単な説明】
【図１】（ａ）は、従来技術による通常のレートｋ／ｎ
畳込み符号器のブロック図である。（ｂ）は、（ａ）の
従来技術の畳込み符号器に対応するトレリス線図であ
る。
【図２】折返し係数２の、本発明による３２状態レート
２／３復号器の例のブロック図である。
【図３】図２の復号器に対応するトレリス線図である。
【図４】（ａ）は、折返し係数４の、本発明による３２
状態レート２／３復号器の例のブロック図である。
（ｂ）は、（ａ）の復号器に対応するトレリス線図であ
る。
【図５】（ａ）は、折返し係数１６の、本発明による３
２状態レート２／３復号器の例のブロック図である。
（ｂ）は、（ａ）の復号器に対応するトレリス線図であ
る。
【図６】本発明による直接移動法を用いた１６個のデー
タ点の４ウェイ交錯のための再配列ステップのセットの
例の図である。
【図７】本発明による収集移動法を用いた１６個のデー
タ点の４ウェイ交錯のための再配列ステップのセットの
例の図である。
【図８】従来技術による通常の並列アクセス復号器処理
要素のブロック図である。
【図９】図２〜図５の復号器で使用するのに適した、本
発明による直列アクセス処理要素の実施例のブロック図
である。
【図１０】図２〜図５の復号器で使用するのに適した、
本発明による直列アクセス処理要素のもう１つの実施例
のブロック図である。
【図１１】図９および図１０の処理要素で使用するのに
適した、ステップサイズ２の置換を行うシフト交換ユニ
ット（ＳＥＵ）の例の図である。
【符号の説明】
１０ レートｋ／ｎ畳込み符号器 １２ 記憶要素 １４ 記憶要素 １６ 記憶要素 １８ 符号化ロジック ２０ 記憶要素 ２２ 記憶要素 ３０ トレリス線図 ３２ ノード ３４ ノード ４０ 復号器 ４２ 処理要素 ４４ 分配ノード ４６ 相互接続ライン ５０ トレリス線図 ５２ ノード ５４ ノード ５６ ブランチ ６０ 復号器 ６２ 処理要素 ６６ 相互接続ライン ７０ トレリス線図 ７２ ノード ７４ ノード ７６ ブランチ ８０ 復号器 ８２ 処理要素 ８４ ノード ８６ 相互接続ライン ９０ トレリス線図 ９２ ノード ９４ ノード ９６ 二重ライン １０５ 処理要素 １１０ ブランチメトリックテーブル １１２ 加算器 １２０ 比較／選択ユニット １２２ 比較器 １２４ 選択器 １３５ 処理要素 １４０ ブランチメトリックテーブル １４２ 加算器 １４６ ラッチ １５０ 比較／選択ユニット １５４ メトリック再配列手段 １５６ ＳＥＵ １６０ 処理要素 １６１ ブランチメトリックテーブル １６２ 加算器 １６６ ラッチ １６８ 比較器 １７０ ラッチ １７２ 選択器 １７６ ＳＥＵ １８０ メトリック再配列手段 ２００ ＳＥＵ ２０１ パスメトリック入力 ２０２ 選択器 ２０４ 選択器 ２０６ ラッチ ２０８ ラッチ ２０９ パイプライン出力 ２２０ ＳＥＵ ２２１ パスメトリック入力 ２２２ 選択器 ２２４ 選択器 ２２６ ラッチ ２２８ ラッチ ２２９ パイプライン出力 ２４０ ＳＥＵ ２４１ パスメトリック入力 ２４２ 選択器 ２４４ 選択器 ２４６ ラッチ ２４８ ラッチ ２４９ パイプライン出力

Claims (20)

    【特許請求の範囲】
  1. 【請求項１】 高レートトレリス符号を使用して符号化
    された符号シンボルのストリームを復号する方法におい
    て、 複数の処理要素を有する復号器を設けるステップと、 各処理要素が割り当てられた符号状態に対する新たなパ
    スメトリックを計算するように、前記高レートトレリス
    符号の少なくとも１つの相異なる符号状態を各処理要素
    に割り当てるステップと、 現在の符号シンボルとともに変化するブランチメトリッ
    クを使用して、先行する符号シンボルに対して計算され
    た計算済みパスメトリックの更新に基づいて各処理要素
    内で現在の符号シンボルに対して行われる新たなパスメ
    トリックの計算をスケジューリングするステップと、 与えられた処理要素がセット内の各計算済みパスメトリ
    ックに順次アクセスするように処理要素に割り当てられ
    た前記符号状態の先行符号状態に対する計算済みパスメ
    トリックを含むセットのうちの１つへの各処理要素のア
    クセスをスケジューリングするステップと、 先行する符号シンボルに対して計算される新たなパスメ
    トリックが現在の符号シンボルに対する新たなパスメト
    リックを計算する際に計算済みパスメトリックとして用
    いられるように、前記計算をスケジューリングするステ
    ップおよび前記アクセスをスケジューリングするステッ
    プにおいてそれぞれ決定された計算スケジュールおよび
    アクセススケジュールを使用して、前記復号器において
    各符号シンボルが受信されるごとに、各符号状態に対す
    る新たなパスメトリックを計算するステップと、 前記パスメトリックの生き残りシーケンスを使用して、
    前記符号シンボルに対応する非符号化データシンボルを
    評価するステップとからなることを特徴とするデータ復
    号方法。
  2. 【請求項２】 後のパスメトリック計算のためのアクセ
    スのスケジューリングを容易にするために、新たなパス
    メトリックを再配列するステップをさらに有することを
    特徴とする請求項１の方法。
  3. 【請求項３】 前記復号器は２i個の処理要素を有し、
    前記割り当てるステップは、２進表示でｉビットの共通
    セットを有する符号状態のグループを各処理要素に割り
    当てるステップを含むことを特徴とする請求項１の方
    法。
  4. 【請求項４】 前記高レートトレリス符号がレートｋ／
    ｎ畳込み符号であることを特徴とする請求項１の方法。
  5. 【請求項５】 前記復号器は２i個の処理要素を有し、
    前記計算をスケジューリングするステップおよび前記ア
    クセスをスケジューリングするステップは、各処理要素
    が前記計算済みパスメトリックのセットに順次アクセス
    するために、２i個の処理要素のそれぞれによるパスメ
    トリックの計算およびパスメトリックへのアクセスをｉ
    個の復号器クロックサイクルだけずらすステップを含む
    ことを特徴とする請求項１の方法。
  6. 【請求項６】 前記計算をスケジューリングするステッ
    プは、前記符号状態の昇順に新たなパスメトリックの計
    算をスケジューリングするステップを含むことを特徴と
    する請求項１の方法。
  7. 【請求項７】 前記再配列するステップは、 パスメトリックに対応するデータ点のセットを、各スロ
    ット内のスロット位置の数に対応するスロットサイズを
    それぞれ有するいくつかのスロットに分割するステップ
    と、 正しくないスロット位置を示すデータ点が別のスロット
    位置に移動するようにデータ点を置換するステップと、 異なるスロットサイズを使用して、データ点の所望の順
    列が得られるまで、前記分割するステップおよび前記置
    換するステップを反復するステップとをさらに有するこ
    とを特徴とする請求項２の方法。
  8. 【請求項８】 前記置換するステップは、あるスロット
    内の正しくないスロット位置を占めるデータ点を、別の
    スロット内の別のスロット位置へ直接移動するステップ
    を含むことを特徴とする請求項７の方法。
  9. 【請求項９】 前記置換するステップは、 正しくないスロット位置のデータ点を、２つのスロット
    を分ける境界付近の一時的スロット位置のデータ点と交
    換することによって、正しくないスロット位置を占める
    データ点を２つのスロットを分ける境界付近の一時的ス
    ロット位置に収集するステップと、 一方のスロット内の一時的スロット位置のデータ点を、
    他方のスロット内の別のスロット位置に移動するステッ
    プとを含むことを特徴とする請求項７の方法。
  10. 【請求項１０】 高レートトレリス符号を使用して符号
    化された符号シンボルのストリームを復号する装置にお
    いて、 符号シンボルとともに変化するブランチメトリックを使
    用して計算済みパスメトリックを更新することによっ
    て、割り当てられた各符号状態に対して新たなパスメト
    リックを計算するように、少なくとも１つの符号状態が
    それぞれ割り当てられた複数の処理要素と、 処理要素に割り当てられた前記符号状態の先行符号状態
    に対する計算済みパスメトリックを含むセットに各処理
    要素が順次アクセスするように、パスメトリックの計算
    およびアクセスのスケジュールに従って、各処理要素の
    出力を他の処理要素に分配する複数のパスメトリック分
    配ノードとからなることを特徴とするデータ復号装置。
  11. 【請求項１１】 前記複数の処理要素は２i個の処理要
    素を含み、２進表示でｉビットの共通セットを有する符
    号状態のグループが２i個の処理要素のそれぞれに割り
    当てられることを特徴とする請求項１０の装置。
  12. 【請求項１２】 前記符号がレートｋ／ｎ畳込み符号で
    あることを特徴とする請求項１０の装置。
  13. 【請求項１３】 前記複数の処理要素は２i個の処理要
    素を含み、その２i個の処理要素のそれぞれによるパス
    メトリックの計算および計算済みパスメトリックへのア
    クセスをｉ個の復号器クロックサイクルだけずらすこと
    により、各処理要素の順次アクセスを可能にしたことを
    特徴とする請求項１０の装置。
  14. 【請求項１４】 前記処理要素は、 計算済みパスメトリックを当該処理要素に順に提供する
    直列メトリック入力と、 計算済みパスメトリックのうちの１つを複数のブランチ
    メトリックのうちの１つに加算する複数の加算器と、 当該処理要素内に一部計算パスメトリックを記憶する複
    数のラッチと、 前記加算器のうちの少なくとも１つの出力と前記ラッチ
    のうちの１つの出力を比較し、一方の出力を新たなパス
    メトリックとして選択する複数の比較／選択ユニットと
    を有することを特徴とする請求項１０の装置。
  15. 【請求項１５】 前記処理要素は、当該処理要素内で計
    算した新たなパスメトリックを再配列するためにいくつ
    かのシフト交換ユニットを有するメトリック再配列手段
    をさらに有することを特徴とする請求項１４の装置。
  16. 【請求項１６】 前記処理要素は、 計算済みパスメトリックを当該処理要素に順に提供する
    直列メトリック入力と、 計算済みパスメトリックのうちの１つを前記ブランチメ
    トリックのうちの１つに加算する１個の加算器と、 複数の復号器クロックサイクルの間、一部計算パスメト
    リックを一時的に記憶する、直列に配置された複数のラ
    ッチと、 前記ラッチに記憶されている値を使用して前記複数の復
    号器クロックサイクルにわたって新たなパスメトリック
    が計算されるように、前記ラッチの直列配置内に配置さ
    れた比較器および選択器とを有することを特徴とする請
    求項１０の装置。
  17. 【請求項１７】 前記処理要素は、当該処理要素内で計
    算したパスメトリックを再配列するためにいくつかのシ
    フト交換ユニットを有するメトリック再配列手段をさら
    に有することを特徴とする請求項１６の装置。
  18. 【請求項１８】 データ点のセットを再配列する方法に
    おいて、 前記データ点のセットを、各スロット内のスロット位置
    の数に対応するスロットサイズをそれぞれ有するいくつ
    かのスロットに分割するステップと、 正しくないスロット位置を示す少なくとも１つのデータ
    点が別のスロット位置に移動するようにデータ点を置換
    するステップと、 異なるスロットサイズを使用して、データ点の所望の順
    列が得られるまで、前記分割するステップおよび前記置
    換するステップを反復するステップとからなることを特
    徴とするデータ点再配列方法。
  19. 【請求項１９】 前記置換するステップは、あるスロッ
    ト内の正しくないスロット位置を占めるデータ点を、別
    のスロット内の別のスロット位置へ直接移動するステッ
    プを含むことを特徴とする請求項１８の方法。
  20. 【請求項２０】 前記置換するステップは、 正しくないスロット位置のデータ点を、２つのスロット
    を分ける境界付近の一時的スロット位置のデータ点と交
    換することによって、正しくないスロット位置を占める
    データ点を２つのスロットを分ける境界付近の一時的ス
    ロット位置に収集するステップと、 一方のスロット内の一時的スロット位置のデータ点を、
    他方のスロット内の別のスロット位置に移動するステッ
    プとを含むことを特徴とする請求項１８の方法。
JP7074727A 1994-03-09 1995-03-08 データ復号方法 Pending JPH07273671A (ja)

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
US208542 1994-03-09
US08/208,542 US5530707A (en) 1994-03-09 1994-03-09 Area-efficient decoders for rate-k/n convolutional codes and other high rate trellis codes

Publications (1)

Publication Number Publication Date
JPH07273671A true JPH07273671A (ja) 1995-10-20

Family

ID=22774972

Family Applications (1)

Application Number Title Priority Date Filing Date
JP7074727A Pending JPH07273671A (ja) 1994-03-09 1995-03-08 データ復号方法

Country Status (4)

Country Link
US (2) US5530707A (ja)
EP (1) EP0674396A3 (ja)
JP (1) JPH07273671A (ja)
CA (1) CA2141014A1 (ja)

Cited By (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP2020522924A (ja) * 2017-06-08 2020-07-30 インターナショナル・ビジネス・マシーンズ・コーポレーションＩｎｔｅｒｎａｔｉｏｎａｌ Ｂｕｓｉｎｅｓｓ Ｍａｃｈｉｎｅｓ Ｃｏｒｐｏｒａｔｉｏｎ アナログ信号から生成されるシーケンスに対応するシンボル値を検出する方法、及びシーケンス検出器

Families Citing this family (36)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
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
JPH08278957A (ja) * 1995-04-04 1996-10-22 Fujitsu Ltd 実行不可能解及び無限解の解析支援装置
FR2738427B1 (fr) * 1995-08-31 1997-11-21 Sgs Thomson Microelectronics Decodeur convolutif utilisant l'algorithme de viterbi
KR100195745B1 (ko) * 1996-08-23 1999-06-15 전주범 비터비 복호화기의 가산 비교 선택 장치
EP0851591B1 (en) * 1996-12-24 2001-09-12 Matsushita Electric Industrial Co., Ltd. Data processor and data processing method
FI102335B1 (fi) 1997-02-28 1998-11-13 Nokia Telecommunications Oy Vastaanottomenetelmä ja vastaanotin
US5938790A (en) * 1997-03-04 1999-08-17 Silicon Systems Research Ltd. Sequence error event detection and correction using fixed block digital sum codes
EP0901234A3 (en) * 1997-09-08 2004-06-16 Lucent Technologies Inc. Viterbi compare-select operation for two-bit traceback coding
US6094739A (en) * 1997-09-24 2000-07-25 Lucent Technologies, Inc. Trellis decoder for real-time video rate decoding and de-interleaving
WO1999023760A1 (en) * 1997-11-03 1999-05-14 Harris Corporation Receiver for a reconfigurable radio system and method therefor
US6256764B1 (en) * 1997-11-26 2001-07-03 Nortel Networks Limited Method and system for decoding tailbiting convolution codes
US6381728B1 (en) * 1998-08-14 2002-04-30 Qualcomm Incorporated Partitioned interleaver memory for map decoder
WO2000024173A2 (en) 1998-10-16 2000-04-27 Analog Devices, Inc. Apparatus and method for determining the closest coset points in a trellis decoder
US6680986B1 (en) * 1999-11-22 2004-01-20 Intelsat Global Service Corporation Method for implementing shared channel decoder for onboard processing satellites
JP3515720B2 (ja) * 1999-11-22 2004-04-05 松下電器産業株式会社 ビタビ復号器
US7116710B1 (en) 2000-05-18 2006-10-03 California Institute Of Technology Serial concatenation of interleaved convolutional codes forming turbo-like codes
KR100340222B1 (ko) * 2000-05-22 2002-06-12 주민 다수준 격자부호변조방식의 복호화방법 및 장치
US6944607B1 (en) * 2000-10-04 2005-09-13 Hewlett-Packard Development Compnay, L.P. Aggregated clustering method and system
KR100605359B1 (ko) * 2000-11-01 2006-07-28 삼성전자주식회사 광디스크용 고배속 비터비 검출기
EP1220455A1 (en) * 2000-12-29 2002-07-03 Motorola, Inc. Viterbi decoder, method and unit therefor
US7522678B2 (en) * 2002-04-18 2009-04-21 Infineon Technologies Ag Method and apparatus for a data-dependent noise predictive viterbi
EP1413937A1 (en) * 2002-10-21 2004-04-28 ABB Schweiz AG Finite state machine display for operator guidance
US7213196B2 (en) * 2003-02-04 2007-05-01 International Business Machines Corporation Method and system for indexing a decoder
US20080109709A1 (en) * 2003-08-19 2008-05-08 Chao Cheng Hardware-Efficient, Low-Latency Architectures for High Throughput Viterbi Decoders
US7308640B2 (en) * 2003-08-19 2007-12-11 Leanics Corporation Low-latency architectures for high-throughput Viterbi decoders
GB0414793D0 (en) * 2004-07-01 2004-08-04 Ttp Communications Ltd Determining characteristics of communications signals
US7603613B2 (en) * 2005-02-17 2009-10-13 Samsung Electronics Co., Ltd. Viterbi decoder architecture for use in software-defined radio systems
US20070011557A1 (en) * 2005-07-07 2007-01-11 Highdimension Ltd. Inter-sequence permutation turbo code system and operation methods thereof
US7797615B2 (en) * 2005-07-07 2010-09-14 Acer Incorporated Utilizing variable-length inputs in an inter-sequence permutation turbo code system
US7856579B2 (en) * 2006-04-28 2010-12-21 Industrial Technology Research Institute Network for permutation or de-permutation utilized by channel coding algorithm
US7698624B2 (en) * 2006-03-31 2010-04-13 Trellisware Technologies, Inc. Scheduling pipelined state update for high-speed trellis processing
US20070266303A1 (en) * 2006-04-27 2007-11-15 Qualcomm Incorporated Viterbi decoding apparatus and techniques
KR20080012434A (ko) * 2006-08-03 2008-02-12 삼성전자주식회사 입력 메시지의 특성을 고려한 복호 장치 및 방법
WO2011121578A2 (en) * 2010-04-01 2011-10-06 Telefonaktiebolaget L M Ericsson (Publ) System and method for signaling control information in a mobile communication network
CN106294285B (zh) 2015-06-09 2018-11-30 华邦电子股份有限公司 数据分配装置、信号处理装置及其数据分配方法
US10243591B2 (en) * 2016-08-30 2019-03-26 International Business Machines Corporation Sequence detectors

Family Cites Families (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US4730322A (en) * 1985-09-27 1988-03-08 California Institute Of Technology Method and apparatus for implementing a maximum-likelihood decoder in a hypercube network
US5068859A (en) * 1989-06-19 1991-11-26 California Institute Of Technology Large constraint length high speed viterbi decoder based on a modular hierarchial decomposition of the deBruijn graph
US5216694A (en) * 1991-09-12 1993-06-01 At&T Bell Laboratories Trellis coding for fractional bits
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

Cited By (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP2020522924A (ja) * 2017-06-08 2020-07-30 インターナショナル・ビジネス・マシーンズ・コーポレーションＩｎｔｅｒｎａｔｉｏｎａｌ Ｂｕｓｉｎｅｓｓ Ｍａｃｈｉｎｅｓ Ｃｏｒｐｏｒａｔｉｏｎ アナログ信号から生成されるシーケンスに対応するシンボル値を検出する方法、及びシーケンス検出器

Also Published As

Publication number Publication date
US5935270A (en) 1999-08-10
CA2141014A1 (en) 1995-09-10
EP0674396A3 (en) 1996-04-10
EP0674396A2 (en) 1995-09-27
US5530707A (en) 1996-06-25

Similar Documents

Publication Publication Date Title
JPH07273671A (ja) データ復号方法
JP3677257B2 (ja) 畳込み復号装置
US4606027A (en) Error correction apparatus using a Viterbi decoder
US6088404A (en) Method and apparatus for decoding trellis code data
JP3280183B2 (ja) 通信システムおよび情報処理方法
US5537424A (en) Matched spectral null codes with partitioned systolic trellis structures
Lin et al. Algorithms and architectures for concurrent Viterbi decoding
US5901182A (en) Metric sifting in breadth-first decoding of convolutional coded data
KR19980015791A (ko) 비터비 복호화기의 가산 비교 선택 장치
US5878092A (en) Trace-back method and apparatus for use in a viterbi decoder
US5548600A (en) Method and means for generating and detecting spectrally constrained coded partial response waveforms using a time varying trellis modified by selective output state splitting
US6272661B1 (en) Minimum memory implementation of high speed viterbi decoder
JP3837023B2 (ja) ターボ符号のためのハイブリッドインタリーバー
US20040243916A1 (en) Method and apparatus for decoding multi-level trellis coded modulation
US7308640B2 (en) Low-latency architectures for high-throughput Viterbi decoders
Kong et al. Low-latency architectures for high-throughput rate Viterbi decoders
US7035356B1 (en) Efficient method for traceback decoding of trellis (Viterbi) codes
Lin et al. Parallel Viterbi decoding methods for uncontrollable and controllable sources
US7020831B2 (en) Pipelined add-compare-select circuits and methods, and applications thereof
KR0169680B1 (ko) 비터비 복호기
Arun et al. Design and VLSI architecture of nonpolynomial based low probability of error (Pb) Viterbi decoder
Meier A Viterbi decoder architecture based on parallel processing elements
KR0169678B1 (ko) 비터비 복호기
KR0169679B1 (ko) 비터비 복호기
Lee et al. The radix-2/sup k/Viterbi decoding with transpose path metric processor