JP3720258B2

JP3720258B2 - 複雑性を低減した系列推定技術のクリティカルパスを短縮する方法および装置

Info

Publication number: JP3720258B2
Application number: JP2000389807A
Authority: JP
Inventors: アザデットカメラン; フランツハーラッチェエリック
Original assignee: ルーセントテクノロジーズインコーポレーテッド
Priority date: 1999-12-23
Filing date: 2000-12-22
Publication date: 2005-11-24
Anticipated expiration: 2020-12-22
Also published as: JP2001230682A; KR100783852B1; CA2327910A1; AU7237100A; US20060039492A1; KR100785410B1; KR20070080246A; TW507431B; EP1111863B1; US6999521B1; US7499498B2; KR20010062638A; EP1111863A3; EP1111863A2

Description

【０００１】
【発明の属する技術分野】
本発明は、概して、チャネル等化および復号化技術に関し、特に、クリティカルパスの短い系列推定技術に関する。
【０００２】
【従来の技術】
ツイストペア導体を使用するローカルエリアネットワーク（ＬＡＮ）のための伝送速度は、１０メガビット／秒（Ｍｂｐｓ）から１ギガビット／秒（Ｇｂｐｓ）まで累進的に増大してきた。例えば、ギガビットイーサネット１０００Ｂａｓｅ−Ｔ規格は、１２５ＭＨｚのクロック速度で動作し、１Ｇｂｐｓを送信するために４つの銅対を備えたカテゴリ５ケーブルを使用する。コーディングゲインに達するために、送信機により、周知の方法でトレリス符号化変調（ＴＣＭ）が使用される。受信機に到着する信号は、一般に、シンボル間干渉（ＩＳＩ）、クロストーク、エコーおよびノイズにより破損される。ジョイント（ｊｏｉｎｔ）等化および復号化のためのアルゴリズムが、パイプライン化することができない非線形フィードバックループを組込んでいるため、１０００Ｂａｓｅ−Ｔ受信機に対する主な挑戦は、チャネルの等化と、１２５ＭＨｚの要求されたクロック速度での破損されたトレリス符号化信号の復号化と、を連帯的に行うということである。
【０００３】
データ検出は、しばしば、出力シンボルまたはビットを生成するために最尤系列推定（ＭＬＳＥ）を使用することによって実行される。最尤系列推定器（ＭＬＳＥ）は、周知の方法で、あり得るすべての系列を考慮し、いずれの系列が実際に送信されたかを決定する。最尤系列推定器（ＭＬＳＥ）は、最適復号器であり、ジョイント等化および復号化を実行するために周知のビタビアルゴリズムを適用する。最尤系列推定器（ＭＬＳＥ）のビタビを用いる実現のより詳細な説明については、参照をもってその開示内容がすべて本明細書内に援用されたものとする、Gerhard FettweisおよびHeinrich Meyrによる「High-Speed Parallel Viterbi Decoding Algorithm and VLSI-Architecture」IEEE Communication Magazine
(May 1991)を参照のこと。
【０００４】
ビタビアルゴリズムを採用する最尤系列推定器（ＭＬＳＥ）のハードウェア複雑性を低減するために、「状態数限定型系列推定（ＲＳＳＥ）」アルゴリズム等の最適には及ばない多数の方式が提案または提唱されてきた。判定帰還型系列推定（ＤＦＳＥ）および並列判定帰還型等化（ＰＤＦＥ）技術の特別な場合と同様、状態数限定型系列推定（ＲＳＳＥ）技術の説明については、例えば、それぞれ参照をもってそれらの開示内容がすべて本明細書内に援用されたものとする、P. R. ChevillatおよびE. Eleftheriouによる「Decoding of Trellis-Encoded Signals in the Presence of Intersymbol Interference and Noise」IEEE Trans. Commun., vol. 37, 669-76, (July 1989)、M. V. EyubogluおよびS.U.H.Qureshiによる「Reduced-State Sequence Estimation For Coded Modulation On Intersymbol Interferece Channels」IEEE JSAC, vol.7, 989-95 (Aug.1989)またはA.Duel-HallenおよびC.Heegardによる「Delayed decision-feedback sequence estimation」IEEE Trans. Commun., vol.37, pp.428-436, May 1989を参照のこと。Ｍアルゴリズムの説明については、例えば、参照をもってその開示内容がすべて本明細書内に援用されたものとする、E. F. Haratschによる「High-Speed VLSI Implementation of Reduced Complexity Sequence Estimation Algorithms With Application to Gigabit Ethernet 1000 Base-T」Int’l Symposium on VLSI Technology, Systems,and Applications, Taipei (Jun.1999)を参照のこと。
【０００５】
概して、状態数限定型系列推定（ＲＳＳＥ）技術は、いくつかの状態をマージすることにより最尤系列推定器（ＭＬＳＥ）の複雑性を低減する。ＲＳＳＥ技術は、パイプライン化することができない非線形フィードバックループを組込んでいる。これらフィードバックループに関連するクリティカルパスは、高速実現のための制限要因である。
【０００６】
【発明が解決しようとする課題】
参照をもってその開示内容がすべて本明細書内に援用されたものとする、１９９９年６月４日に出願され「Method and Apparatus for Reducing the Computational Complexity and Relaxing the Critical Path of Reduced State Sequence Estimation (RSSE) Techniques」と題された米国特許出願第０９／３２６，７８５号は、所定数の状態に対しＲＳＳＥ技術のハードウェア複雑性を低減すると共にクリティカルパス問題を緩和する状態数限定型系列推定（ＲＳＳＥ）アルゴリズムを開示している。開示されたＲＳＳＥアルゴリズムは、処理時間が大幅に改良されたことを示しているが、多くの高速アプリケーションに対して追加の処理ゲインが必要である。従って、処理時間が改善された状態数限定型系列推定（ＲＳＳＥ）アルゴリズムが必要とされている。更に、超大規模集積（ＶＬＳＩ）技術を用いる高速実現により適した状態数限定型系列推定（ＲＳＳＥ）アルゴリズムが必要とされている。
【０００７】
【課題を解決するための手段】
概して、所定の数の状態に対し、ＲＳＳＥ技術等の複雑性が低減された系列推定技術の処理時間を改良する方法および装置が開示されている。本発明の１つの特徴に従って、状態数限定型系列推定（ＲＳＳＥ）技術におけるブランチメトリクスに対する可能な値が、先取り方式で事前計算されることにより、パイプライン化およびクリティカルパスの短縮化が可能となる。これにより、本発明は、従来からの最適ビタビ復号器と同様の遅延を提供する。本発明に従ってチャネルメモリにおけるあり得るすべてのシンボルの組合せに対しブランチメトリクスを事前計算することにより、フィードバックループからブランチメトリクスユニット（ＢＭＵ）および判定帰還ユニット（ＤＦＵ）を除去することが可能となり、それによってクリティカルパスが低減される。例示的な実現において、ブランチメトリクスユニット（ＢＭＵ）および判定帰還ユニット（ＤＦＵ）の機能は、クリティカルパスから除去されている先取りブランチメトリクスユニット（ＬＡＢＭＵ）およびシンボル間干渉キャンセラ（ＩＳＩＣ）によって実行される。
【０００８】
チャネルメモリに対するあり得るすべての値に対しブランチメトリクスを事前計算するために先取りブランチメトリクスユニット（ＬＡＢＭＵ）を提供する状態数限定型推定器（ＲＳＳＥ）が開示されている。各復号化サイクルの開始時に、１組のマルチプレクサ（ＭＵＸ）は、対応する生残りパスセル（ＳＰＣ）における生残りシンボルに基づいて適当なブランチメトリクスを選択し、その後それらは加算比較選択ユニット（ＡＣＳＵ）に送信される。この時、クリティカルパスは、１つのＭＵＸ、ＡＣＳＣおよびＳＰＣからなる。開示されたＲＳＳＥは、１次元と多次元のトレリス符号両方に対して利用することができる。
【０００９】
多次元ブランチメトリクスの事前計算が計算上非常に費用がかかる多次元トレリス符号に対し、計算上の負荷を低減する修正されたＲＳＳＥが開示されている。多次元トレリス符号の各次元に対するメトリクスは、別々に事前計算される。そして、適当な１次元ブランチメトリクスが、その次元の対応する生残りパスセル（ＳＰＣ）における対応する生残りシンボルに基づいて選択される。そして、多次元ブランチメトリクスユニットが、その選択された１次元ブランチメトリクスを結合して、多次元ブランチメトリクスを形成する。本発明の他の態様によれば、チャネルメモリを短縮することにより計算上の複雑性を低減するために、プレフィルタリング技術が使用される。ポストカーソルチャネルメモリ長を切捨てて１にする１０００Ｂａｓｅ−Ｔギガビットイーサネット実現のために、特定の実現の例が提供されている。
【００１０】
生残りパスセル内の生残りメモリユニットに対する新規なメモリ分割された生残りメモリアーキテクチャもまた、開示されている。ゼロレイテンシの判定帰還ユニット（ＤＦＵ）またはマルチプレクサユニット（ＭＵＸＵ）において必要とされる生残りシンボルの記憶のためのレイテンシを防止するために、状態数限定型系列推定（ＲＳＳＥ）に対しハイブリッド生残りメモリ構成が開示されている。長さＬのチャネルメモリに対するＲＳＳＥ実現において、（ｉ）従来からのＲＳＳＥの判定帰還ユニット（ＤＦＵ）におけるシンボル間干渉キャンセルのため、および（ｉｉ）本発明によるＲＳＳＥのマルチプレクサ（ＭＵＳＵ）におけるブランチメトリクスの選択のために、Ｌまでの復号化サイクルに対応する生残りシンボルが利用される。本発明は、Ｌまでの復号化サイクルに対応する生残りをレジスタ交換アーキテクチャ（ＲＥＡ）に格納し、後の復号化サイクルに対応する生残りがトレースバックアーキテクチャ（ＴＢＡ）かまたはレジスタ交換アーキテクチャ（ＲＥＡ）に格納される。シンボルは、レジスタ交換アーキテクチャ（ＲＥＡ）からトレースバックアーキテクチャ（ＴＢＡ）まで移動される前に、ワードサイズを低減するために情報ビットにマップされる。１０００Ｂａｓｅ−Ｔ実現において、第２メモリ区分のトレースバックアーキテクチャ（ＴＢＡ）によってもたらされるレイテンシにより、１０００Ｂａｓｅ−Ｔ規格において受信機に対して指定される密なひとまとまりのレイテンシの侵害がもたらされるため、レジスタ交換アーキテクチャ（ＲＥＡ）が生残りメモリ全体に対して使用される。
【００１１】
【発明の実施の形態】
上述したように、状態数限定型系列推定（ＲＳＳＥ）等の複雑性が低減された系列推定技術の処理スピードは、再帰的なフィードバックループによって制限される。本発明の１つの特徴によれば、かかる状態数限定型系列推定（ＲＳＳＥ）技術の処理スピードは、先取り方式でブランチメトリクスを事前計算することによって向上される。ブランチメトリクスの事前計算は、遅延が従来からのビタビ復号器におけるのと同じ程度であるように、クリティカルパスを短縮する。本発明の他の特徴によれば、事前計算の計算上の負荷が、多次元トレリス符号に対して大幅に低減される。チャネルメモリを短縮することにより、プレフィルタリングは計算上の複雑性を低減することができる。本発明のＲＳＳＥ技術により、ギガビットイーサネット１０００Ｂａｓｅ−Ｔ規格等、高速通信システムに対するＲＳＳＥの実現が可能となる。
【００１２】
トレリス符号化変調
上述したように、ＲＳＳＥ技術は、符号化されていない信号を等化するか、またはトレリス符号化変調（ＴＣＭ）を用いて符号化されている信号を連帯的に復号化および等化するために使用される場合、ビタビアルゴリズムの計算上の複雑性を低減する。本発明は、本明細書において、トレリス符号化信号の復号化および等化を用いて示されているが、当業者には明らかとなるように、符号化されていない信号の等化にも適用される。ＴＣＭは、帯域限定チャネルに対する結合された符号化および変調方式である。ＴＣＭのより詳細な説明については、図１は、トレリス符号化通信システムの等価離散時間型モデルを示す。
【００１３】
図１に示すように、ｍビットからなる情報シンボルＸ_nが、ＴＣＭ符号器１１０に供給される。レートｍ’／（ｍ’＋１）の符号器であるＴＣＭ符号器１１０は、ｍ’入力ビットに対して動作し、ｍ’＋１符号化ビットを生成する。それらは、採用されたサイズ２^m+1の信号コンステレーションから２^m'⁺¹部分集合（各々のサイズが２^m-m'）の１つを選択するために使用され、符号化されていないビットは、選択された部分集合内の１つのシンボルａ_nを選択するために使用される。例示的な実現では、シンボルａ_nに対する変調方式として、Ｚレベルパルス振幅変調（Ｚ−ＰＡＭ）が使用される。しかしながら、本発明の技術は、当業者には明らかとなるように、ＰＳＫまたはＱＡＭ等の他の変調方式に適用することも可能である。選択されたシンボルａ_nは、等価離散時間型チャネルに送信される。１次元チャネルとすると、時刻ｎにおけるチャネル出力ｚ_nは、次のように与えられる。
【数１】

ここで、ｑ_nはＩＳＩによって破損された信号であり、｛ｆ_i｝，ｉ∈［０，．．，Ｌ］は、等価離散時間型チャネルインパルス応答の係数であり（ｆ₀＝１は、一般性を失わずに仮定されている）、Ｌはチャネルメモリの長さであり、｛ｗ_n｝はゼロ平均および分散σ²を含むホワイトガウスノイズを表す。
【００１４】
トレリス符号器およびチャネルの連結は、結合された符号およびチャネル状態を定義する。それは、次の式で得られる。
【数２】

ここで、μ_nは符号状態であり、α_n＝（ａ_n-L，．．，ａ_n-1）は時刻ｎにおけるチャネル状態である。受信信号に対する最適な復号器は、結合された符号およびチャネル状態によって定義されるスーパトレリスに対しビタビアルゴリズムを適用する最尤系列推定器（ＭＬＳＥ）である。ビタビアルゴリズムの計算および記憶要件は、状態の数に比例する。スーパトレリスの状態の数は、以下の式で与えられる。
【数３】

ここで、Ｓは符号状態の数である。
【００１５】
ビタビアルゴリズムは、すべての状態に対し効率よくパスメトリクスを累積することにより、最尤データ系列を探索する。入力ａ_nにおける状態ξ_nからの遷移に対するブランチメトリックは、以下の式で与えられる。
【数４】

【００１６】
一般に加算比較選択（ＡＣＳ）計算と呼ばれる以下のパスメトリック計算に従って、先行状態｛ξ_n｝から状態｛ξ_n+1｝に入るすべてのパスから、最尤パスが選択される。
【数５】

【００１７】
ビタビアルゴリズムの実現を、図２に示す。図２に示すビタビ実現２００は、主成分ブランチメトリックユニット（ＢＭＵ）２１０と、加算比較選択ユニット（ＡＣＳＵ）２２０と、生残りメモリユニット（ＳＭＵ）２３０と、から構成されている。ブランチメトリックユニット（ＢＭＵ）２１０は、式（４）に従って状態遷移に対しメトリクスを計算する。ＡＣＳユニット（ＡＣＳＵ）２２０は、各状態に対し式（５）を計算し、生残りメモリユニット（ＳＭＵ）２３０は、生き残っているパスを追跡する。ＢＭＵ２１０およびＳＭＵ２３０におけるデータフローは、厳密に正方向送りされ、スループットを向上させるためにいかなるレベルでもパイプライン化することができる。式（５）におけるＡＣＳ演算の再帰に、トレリスの次のステップが復号化される前に判断が行われることが必要であるため、高速処理に対するボトルネックはＡＣＳＵ２２０である。
【００１８】
ＲＳＳＥ技術は、トレリスのためにＬチャネル係数｛ｆ_i｝，ｉ∈［０，．．，Ｌ］の最初のＫのみが考慮されるようにチャネルメモリを切捨てることにより、最尤系列推定器（ＭＬＳＥ）の複雑性を低減する。低減された結合チャネルおよび符号状態は、ＲＳＳＥにおいて次の式で与えられる。
【数２】

ここで、Ｊ_ｎ−ｉはデータシンボルａ_ｎ−ｉが属している部分集合である。異なる部分集合Ｊ_ｎ−ｉの数は、２^ｍｉによって与えられる。ここで、ｍ_ｉは時刻ｎ−ｉにおける部分集合分割の深さを定義する。
【数３】

であることが必要である。
【００１９】
低減されたスーパトレリスにおける状態の数は、以下のように与えられる。
【数８】

【００２０】
ＲＳＳＥにおいて、入力ａ_nにおける低減された状態ρ_nに対するブランチメトリックは、以下の修正された形態をとる。
【外６】

式（１０）において、仮の判定として状態ρ_nのパス履歴と関連するデータシンボルをとることにより、状態ρ_nに対しＩＳＩ推定値ｕ（ρ_n）が計算される。状態ρ_n+1に対する最適パスメトリックは、次の式を計算することによって得られる。
【数９】

【００２１】
ＲＳＳＥは、各状態が、低減されたトレリスでは考慮されないＩＳＩを説明するためにそれ自体の生残りパスからの判定帰還を使用する、最適状態には及ばないトレリス復号化アルゴリズムとして見ることができる。
【００２２】
図３は、ＲＳＳＥの実現のためのアーキテクチャを示す。図３に示すように、判定帰還ユニット（ＤＦＵ）３４０の判定帰還セル（ＤＦＣ）は、式（１０）に従ってＳＭＵ３３０の対応する生残りパスセル（ＳＰＣ）における生残りを考慮することにより、Ｒ個のＩＳＩ推定値を計算する。ＢＭＵ３１０における各ブランチメトリックセル（ＢＭＣ）は、１つの状態を離れるｂ＝２^m'の遷移に対するメトリクスを計算する。各状態に対し、最適パス選択は、式（１１）に従ってＡＣＳセル（ＡＣＳＣ）において実行される。ビタビ復号化とは対照的に、ＡＣＳＣセルだけでなく、ＤＦＣ、ＢＭＣおよびＳＰＣセルがクリティカルループ内にある。ビタビアルゴリズムの並列処理のための技術は、式（４）におけるブランチメトリック計算が式（５）におけるＡＣＳ機能の判定に依存しない、という事実を利用する。このように、スループットのｋ倍の増大を得るために、先取り方式でｋのトレリスステップに対してブランチメトリクスを計算することができる。しかしながら、ＳＭＵ３３０のＳＰＣにおいて生残っているシンボルが式（１０）における判定帰還計算に必要であるため、ＲＳＳＥ技術に対し、式（９）のブランチメトリック計算は、ＡＣＳＵ３２０のＡＣＳＣの判定に依存する。このように、ブロック処理技術は、ＲＳＳＥの処理をスピードアップするために採用することができない。
【００２３】
ブランチメトリクスの事前計算
ＲＳＳＥにおけるクリティカルパスは、ビタビアルゴリズムにおけるよりも多くの演算を含む。特に、ＢＭＣにおけるブランチメトリック計算は、処理時間という意味で非常に費用がかかる可能性がある。それは、適切なコーディングゲイン性能を達成するために、テーブルルックアップを求めるかまたは実行することにより、ユークリッド距離を求めなければならないためである。また、ＤＦＣ３４０−ｎにおける式（１０）の計算は、クリティカルパスに対し重大な負担をかける可能性がある。本発明に従ってチャネルメモリにおける可能なシンボルの組合せすべてに対しすべてのブランチメトリクスを事前計算することにより、フィードバックループからＢＭＵ３１０およびＤＦＵ３４０を除去することが可能となる。これにより、可能性として、ＲＳＳＥにおけるクリティカルパスの大幅な低減が可能となる。
【００２４】
原則として、チャネル状態α_n＝（ａ_n-L，．．，ａ_n-1）は、Ｕ＝（２^m+1）^Lの異なる値をとることができる。
【外７】

【００２５】

【００２６】
【外９】

図１に示すトレリス符号器は、チャネルメモリα_nにおけるすべてのシンボルの組合せすべてが可能でない場合があった。従って、事前計算されなければならないブランチメトリクスの数は、Ｍ未満である場合があった。事前計算されなければならないブランチメトリクスの実際の数は、低減されたスーパトレリスから決定されなければならない。
【００２７】
【外１０】

【００２８】
【外１１】

式（１４）における選択関数は、２^mLから１のマルチプレクサを用いて実現することができる。
【００２９】
なお、式（１２）および（１３）は共に、式（１１）における再帰的ＡＣ関数における判定から独立している。これにより、式（１２）および（１３）における事前計算は、厳密に正方向送りされ、いかなるレベルでもパイプライン化することができる。加算比較選択セル（ＡＣＳＣ）および生残りパスセル（ＳＰＣ）に加えて、式（１４）における選択関数のみがクリティカルパル内にある。
【００３０】
本発明によるブランチメトリクスの事前計算を伴うＲＳＳＥ４００のアーキテクチャを、図４に示す。
【外１２】

そして、先取りＢＭＵ（ＬＡＢＭＵ）４１０において事前計算されたＭ＝２ｂＵのブランチメトリクスはすべて、ＭＵＸユニット（ＭＵＸＵ）４３０に送信される。そして、各復号化サイクルの開始時に、ＭＵＸユニット（ＭＵＸＵ）４３０における各マルチプレクサ（ＭＵＸ）４３０−ｎが、対応するＳＰＣ４５０−ｎにおける生残りシンボルに基づいて適当なブランチメトリクスを選択し、その後それらはＡＣＳＵ４４０に送信される。ＭＵＸユニット（ＭＵＸＵ）４３０における各マルチプレクサ（ＭＵＸ）４３０−ｎは、対応する生き残りパスセル（ＳＰＣ）４５０−ｎからＬまでのシンボルをとる。ＡＣＳＵ４４０およびＳＭＵ４５０は、図３の従来からのＲＳＳＥ３００におけるものと同様に具体化されてもよい。ＬＡＢＭＵ４１０の出力は、パイプラインレジスタ４６０に配置される。この時、クリティカルパスは、ＭＵＸ４３０と、ＡＣＳＣ４４０−ｎと、ＳＰＣ４５０−ｎとから構成されている。ＭＵＸ４３０は、ＳＰＣ４５０−ｎにおけるシンボルに依存する式（１４）に従ってブランチメトリックを選択する。事前計算されるブランチメトリクスの数が、チャネルメモリＬおよび情報ビットｍの数によって指数関数的に増大するが、この技術は、小さいｍ（小さいシンボルコンステレーションサイズに対応する）および短いＬに対して適している。
【００３１】
多次元トレリス符号に対する事前計算
大きい信号コンステレーションのための有意なコーディングゲインは、多次元ＴＣＭを用いて達成することができる。図５は、多次元チャネルに対する多次元トレリス符号化変調の使用を示す。

ここで、｛ｗ_n,j｝，ｊ∈［０，．．，Ｂ］は、非相関独立ホワイトガウスノイズ源である。各チャネルに対する送信方式として、Ｚ−ＰＡＭが考慮される。以下の結果は、他の変調方式に対しても同様に有効である。かかる等価離散時間型チャネルは、例えば、Ｂ＝４、ｍ＝８、ｍ’＝２、Ｓ＝８、Ｚ＝５の場合の、銅によるギガビットイーサネット１０００Ｂａｓｅ−Ｔにおいて見ることができる。
【００３２】
情報ビットｍの数によって、ブランチメトリクスの事前計算の複雑性が指数関数的に増大するため、図４に示すような多次元ブランチメトリクスの事前計算が、大きい信号コンステレーションサイズに対して計算上費用がかかり過ぎる場合がある。しかしながら、符号の１次元成分に対してのみブランチメトリクスの事前計算を実行することにより、複雑性を大幅に低減することができる。
【００３３】
次元ｊにおける１次元ブランチメトリックは、以下の式を計算することによって事前計算される。
【外１４】

【００３４】
【外１５】

これらＣの入力ａ_n,jの各々は、式（１６）および（１７）に従うシンボル間干渉のキャンセル後に（ｚ_n,j）がスライスされる対応する部分集合の点に対応する。従って、Ｂ次元すべてを考慮すると、合計Ｎ＝Ｂ×Ｃ×Ｖの１次元ブランチメトリクスが事前計算されなければならない。これは、「ブランチメトリクスの事前計算」と題されたセクションで上述したような、多次元事前計算に必要な事前計算の数より大幅に少なくすることができる。Ｃ＝２、Ｌ＝１およびＺ＝５のギガビットイーサネット１０００Ｂａｓｅ−Ｔの場合、１次元事前計算により、合計４×２×５＝４０の１次元ブランチメトリック事前計算が生じるのに対し、多次元事前計算の結果は、２³×２⁹＝４０９６の４次元ブランチメトリック計算となる。
【００３５】
ＲＳＳＥにおける更なる処理に対する適当な１次元ブランチメトリクスの選択は、次の式で与えられる。
【外１６】

これは、多次元事前計算に必要な２^mLから１のＭＵＸに比較されるＶから１のＭＵＸを使用することによって実現することができる（例えば、上記１０００Ｂａｓｅ−Ｔの例では、５から１のＭＵＸが２５６から１のＭＵＸと比較される必要がある）。適当な１次元ブランチメトリクスが選択された後、多次元ブランチメトリックは次の式で与えられる。
【数１０】

【００３６】
図６は、多次元ＲＳＳＥに対する１次元事前計算のためのアーキテクチャ６００を示す。
【外１７】

ＭＵＸＵ６３０は、各状態に対し、ＳＰＣ６６０−ｎにおける生残りシンボルに依存する適当な１次元ブランチメトリクスを選択する。各多次元ＢＭＣ（ＭＤ−ＢＭＣ）６４０−ｎは、選択された１次元ブランチメトリクスを使用することによって多次元ブランチメトリクスを計算する。この時、クリティカルパスは、１つのＭＵＸ６３０、ＭＤ−ＢＭＣ６４０、ＡＣＳＣ６５０およびＳＰＣ６６０からなる。ＭＤ−ＢＭＣ６４０は、Ｂ−１の加算を実行し、その結果、次元Ｂの数が一般に低いためクリティカルパス全体に対し負担が小さい。
【００３７】
プレフィルタリング
ブランチメトリクスの事前計算に対する複雑性がチャネルメモリＬと共に指数関数的に増大することを示した。しかしながら、図７に示すプレフィルタ７１０を使用することにより、チャネルメモリを短縮することができる。ホワイトマッチドフィルタの後の等価離散時間型チャネルが最小フェーズであるため、チャネルメモリは、判定帰還型プレフィルタ（ＤＦＰ）によりＲＳＳＥに対する大幅な性能損失無しに低い値のＬに切捨てることができる。代替的に、プレフィルタ７１０は、線形フィルタとして実現することができる。
【００３８】
このように、ブランチメトリクスの事前計算が非常に費用がかかる大きいチャネルメモリを備えたチャネルに対し、その事前計算が可能であるようにチャネルメモリを切捨てるために、プレフィルタを使用することができる。
【００３９】
１０００Ｂａｓｅ−Ｔギガビットイーサネット例
以下は、１０００Ｂａｓｅ−Ｔギガビットイーサネット受信機に対する特定の実現の一例である。
【００４０】
１０００Ｂａｓｅ−Ｔギガビットイーサネット実現のための判定帰還型プレフィルタを、図８に示す。１０００Ｂａｓｅ−Ｔギガビットイーサネット実現のための図６の１Ｄ−ＬＡＢＭＵユニットの１つによる１次元ブランチメトリクスの先取り計算を、図９に示す。図１０は、１０００Ｂａｓｅ−Ｔギガビットイーサネット実現のための図６のマルチプレクサによる１次元ブランチメトリクスの選択を示す。最後に、図１１は、ＳＭＵに対して例示的な１４のマージ深さが利用される、１０００Ｂａｓｅ−Ｔギガビットイーサネット実現に対する状態１のレジスタ交換ネットワーク（ＳＰＣｎ）を示す。
【００４１】
判定帰還型プレフィルタ
ワイヤ対ｊのポストカーソルメモリ長を１４から１に切捨てる判定帰還型プレイフィルタ８００を図８に示す。判定帰還型プレフィルタ８００は、ポストカーソルチャネルインパルス応答のテイルを除去するためにそれ自体のスライサによって得られる仮の判定を使用するため、判定帰還等化器（ＤＦＥ）の構成に似ている。
【００４２】
１次元ブランチメトリクスの事前計算
有効なポストカーソルチャネルメモリが判定帰還型プレフィルタ８００の後のものである場合、各ワイヤ対における１次元ブランチメトリクスの先取り事前計算に対する計算上の複雑性は大したものではない。
【外１８】

これを、図９に示す。図９では、スライサ９１０−ｎが、１次元部分集合ＡまたはＢにおける最も近接した点に対する差を計算する。１つの加算、スライシングおよび平方に対し１クロックサイクル時間がある。なお、ブランチメトリクスを事前計算する計算上の複雑性は、チャネルメモリと共に指数関数的に増大する。チャネルメモリが２であった場合、１次元ブランチメトリクスはワイヤ対毎に事前計算されなければならず、チャネルメモリが３であった場合、この数は２５０に増大する。
【００４３】
１次元ブランチメトリクスの選択
【外１９】

これは、図１０に示すように５：１ＭＵＸ１０１０によって行われる。合計で、６４のかかるマルチプレクサが必要である。
【００４４】
４次元ブランチメトリクスの計算
４Ｄ−ＢＭＵ６４０は、１次元ブランチメトリクスを合計することにより、トレリスにおける状態遷移に対応する４次元ブランチメトリクスを計算する。４Ｄ−ＢＭＵ６４０は、クリティカルループ内にある。「多次元トレリス符号の事前計算」と題されたセクションで上述した例に示すように、４次元ブランチメトリクスの先取り事前計算によりクリティカルループから４Ｄ−ＢＭＵ６４０を取出すことは、計算上の複雑性という意味で実際的でない。考慮しなければならない可能性が多すぎるということが容易に分かる。
【００４５】
加算比較選択
各状態に対し、４方向ＡＣＳが実行されなければならない。ここでは、並列な６つの比較により、４つの候補の中で最小パスメトリックが選択される。状態メトリック正規化は、モジュロ演算を用いて行われる。
【００４６】
生残りメモリ
ビタビ符号化において、通常、トレースバックアーキテクチャ（ＴＢＡ）は、レジスタ交換アーキテクチャ（ＲＥＡ）より電力消費が大幅に少ないため、生残りメモリに対して好ましいアーキテクチャである。しかしながら、トレースバックアーキテクチャ（ＴＢＡ）はレイテンシをもたらすため、ゼロレイテンシのＤＦＵまたはＭＵＸＵに必要な生残りシンボルを格納するためには使用することができない。このように、ハイブリッド生残りメモリ配置は、メモリ長Ｌのチャネルに対する状態数限定型系列推定（ＲＳＳＥ）実現に対して有利であるように見える。Ｌまでの符号化サイクルに対応する生残りは、レジスタ交換アーキテクチャ（ＲＥＡ）に格納され、後の復号化サイクルに対応する生残りは、トレースバックアーキテクチャ（ＴＢＡ）に格納される。シンボルは、レジスタ交換アーキテクチャ（ＲＥＡ）からトレースバックアーキテクチャ（ＴＢＡ）に移動される前に、ワードサイズを低減するために情報ビットにマップされる。しかしながら、１０００Ｂａｓｅ−Ｔにおいて、生残りメモリ全体に対してレジスタ交換アーキテクチャ（ＲＥＡ）が使用されなければならない。それは、トレースバックアーキテクチャ（ＴＢＡ）によってもたらされるレイテンシが、１０００Ｂａｓｅ−Ｔ規格における受信機に対して指定された密なひとまとまりのレイテンシの侵害をもたらすためである。同様に、第１のレジスタ交換アーキテクチャ（ＲＥＡ）から第２のレジスタ交換アーキテクチャ（ＲＥＡ）に移動されたシンボルは、ワードサイズを低減するために情報ビットにマップされる。
【００４７】
生残りメモリアーキテクチャを図１１に示す。この図には、状態１に対応する第１行のみが示されている。
【外２０】

状態数限定型系列推定（ＲＳＳＥ）によって見られるチャネルメモリは１つであるため、第１列のみが、１２ビットで表されＭＵＸＵに供給される４次元シンボルを格納する。この第１列の後、生残りシンボルは情報ビットにマップされ、その後８ビットとして格納される。マージ深さが１４である場合、このアーキテクチャは、ハイブリッドメモリ分割を採用しないＳＭＵにおける１３４４のレジスタに比較して９２８のレジスタが必要であり、その場合すべての判定が１２ビットの４次元シンボルとして格納される。
【００４８】
本明細書で示し述べた実施の形態および変形態様は、単に本発明の原理を例示するものであり、本発明の範囲および精神を逸脱することなく種々の変更態様が当業者によって実現され得る、ということは理解されなければならない。
【図面の簡単な説明】
【図１】従来からのトレリス符号化通信システムの等価離散時間型モデルを示す図である。
【図２】ビタビアルゴリズムの従来からの実現を示す図である。
【図３】状態数限定型推定器（ＲＳＳＥ）の従来からの実現に対するアーキテクチャを示す。
【図４】本発明によるブランチメトリクスの事前計算を伴う状態数限定型推定器（ＲＳＳＥ）のアーキテクチャを示す図である。
【図５】多次元チャネルのために多次元トレリス符号化変調の使用を示す図である。
【図６】本発明による多次元状態数限定型系列推定器（ＲＳＳＥ）の１次元事前計算のためのアーキテクチャを示す図である。
【図７】本発明によるチャネルメモリを短縮するためにプレフィルタリング技術を利用する、状態数限定型系列推定器（ＲＳＳＥ）のアーキテクチャを示す図である。
【図８】ポストカーソルチャネルメモリ長を１４から１に切捨てる１０００Ｂａｓｅ−Ｔギガビットイーサネット実現のための判定帰還型プレフィルタを示す図である。
【図９】１０００Ｂａｓｅ−Ｔギガビットイーサネット実現のための図６の１Ｄ−ＬＡＢＭＵユニットのうちの１つによる１Ｄブランチメトリクスの先取り事前計算を示す図である。
【図１０】１０００Ｂａｓｅ−Ｔギガビットイーサネット実現のための図６のマルチプレクサによる１Ｄブランチメトリクスの選択を示す図である。
【図１１】１０００Ｂａｓｅ−Ｔギガビットイーサネット実現のための状態１に対する新規なメモリ分割されたレジスタ交換ネットワーク（ＳＰＣ−ｎ）を示す図である。

Claims

受信した信号を処理する方法であって、
１つ又は複数のチャネルシンボルの推定系列に対して該受信した信号を使用してブランチメトリクスを事前計算するステップと、
該事前計算したブランチメトリクスを少なくとも１つのパイプラインレジスタに格納するステップと、
対応する１つの状態からの少なくとも１つの生き残りシンボルに基づいて、該少なくとも１つのパイプラインレジスタのうちの１つから該事前計算されたブランチメトリクスの１つを選択するステップと、
該選択された事前計算したブランチメトリックを使用して１つのパスメトリックを計算するステップと、
所定の状態に対する最適のパスメトリックを有する１つのパスを選択するステップとを含む方法。
請求項１に記載の方法において、信号の処理は、状態数限定型系列推定技術を使用して実行される方法。
受信した１つの多次元信号を処理する方法であって、
１つ又は複数のチャネルシンボルの推定系列に対して、該受信した１つの多次元信号の各次元に対し複数の１次元ブランチメトリックスを事前計算するステップと、
該事前計算した複数の１次元ブランチメトリックスを少なくとも１つのパイプラインレジスタに格納するステップと、
１つの対応する状態からの少なくとも１つの生き残りシンボルに基づいて、該少なくとも１つのパイプラインレジスタのうちの１つから該事前計算された複数の１次元ブランチメトリックスの１つを選択するステップと、
該選択した１次元ブランチメトリクスを結合することにより１つの多次元ブランチメトリックを取得するステップとを含む方法。
受信した多次元信号を処理する方法であって、
１つ又は複数のチャネルシンボルの推定系列に対して、該受信した多次元信号の各次元に対して複数の１次元ブランチメトリックスを事前計算するステップと、
該複数の１次元ブランチメトリックスを結合して少なくとも２次元のブランチメトリクスにするステップと、
該１次元ブランチメトリックスを結合した少なくとも２次元のブランチメトリックスを少なくとも１つのパイプラインレジスタに格納するステップと、
１つの対応する状態からの少なくとも１つの生き残りシンボルに基づいて該少なくとも１つのパイプラインレジスタのうちの１つから該少なくとも２次元のブランチメトリクスの１つを選択するステップとを含む方法。
１つのチャネルから受信した信号を処理する方法であって、
該受信した信号をプレフィルタリングすることにより該チャネルのメモリを短縮するステップと、
該短縮されたチャネルメモリに対応する複数のシンボルの推定系列に対し該受信した信号を使用して複数のブランチメトリクスを事前計算するステップと、
該事前計算した複数のブランチメトリックスを少なくとも１つのパイプラインレジスタに格納するステップと、
１つの対応する状態からの少なくとも１つの生き残りシンボルに基づいて、該少なくとも１つのパイプランインレジスタのうちの１つから該事前計算された複数のブランチメトリクスの１つを選択するステップと、
該選択した１つの事前計算されたブランチメトリックを使用して１つのパスメトリックを計算するステップと、
所定の状態に対する最適パスメトリックを有する１つのパスを選択するステップとを含む方法。
１つのチャネルから受信した信号を処理する方法であって、
該受信した信号をプレフィルタリングすることにより該１つのチャネルのメモリを短縮するステップと、
該短縮されたチャネルメモリに対し及び多次元信号の各次元に対し、複数のチャネルシンボルの推定系列について該受信した信号を使用して１次元ブランチメトリックを事前計算するステップと、
該１次元ブランチメトリックを結合して少なくとも２次元のブランチメトリクスにするステップと、
該１次元ブランチメトリックを結合した少なくとも２次元のブランチメトリクスを少なくとも１つのパイプラインレジスタに格納するステップと、
１つの対応する状態からの少なくとも１つの生き残りシンボルに基づいて、該少なくとも１つのパイプラインレジスタのうちの１つから該少なくとも２次元のブランチメトリクスの１つを選択するステップとを含む方法。
受信した信号を処理する信号処理器であって、
１つ又は複数のチャネルシンボルの推定系列に対して該受信した信号を使用して複数のブランチメトリクスを事前計算するブランチメトリクスユニットと、
該事前計算した複数のブランチメトリックスを格納する少なくとも１つのパイプラインレジスタと、
１つの対応する状態からの少なくとも１つの生き残りシンボルに基づいて、該少なくとも１つのパイプラインレジスタのうちの１つから該事前計算された複数のブランチメトリクスの１つを選択するマルチプレクサと、
該選択した事前計算されたブランチメトリックを使用して１つのパスメトリックを計算し、所定の状態に対し最適パスメトリックを有する１つのパスを選択する加算比較選択ユニットとを含む信号処理器。