(57)【要約】最尤シーケンス推定（MLSE）デコーダ（たとえばビタビ・デコーダ）のようなプログラム可能なデコーダが、複数のプログラム可能なトレリス・パラメータのためのプログラミング入力と、前記プログラミング入力に接続され、前記複数のプログラム可能なトレリス・パラメータに基づいて定義される少なくとも一つのトレリス構造を有するトレリス・デコーダを実装する、FPGAのようなプログラム可能なデバイスとを含みうる。前記複数のプログラム可能なトレリス・パラメータは、各トレリス段についてアクティブまたは非アクティブ状態となるトレリス段のためのトレリス接続性情報、トレリス枝遷移データ値およびトレリス枝遷移についてのメトリック・インデックスを含みうる。また、トレリス構造は逆状態（reverse-state）トレリス構造を含んでいてもよい。本プログラム可能型トレリス・デコーダは、畳み込み符号、トレリス符号化変調（TCM）、ISIチャネルおよびCPM波形をデコードできる。
2010503351.tif 000002
【特許請求の範囲】
【請求項１】
プログラム可能なデコーダであって：
各トレリス段についてアクティブまたは非アクティブ状態となるトレリス段のためのトレリス接続性情報、トレリス枝遷移データ値およびトレリス枝遷移についてのメトリック・インデックスを含む複数のプログラム可能なトレリス・パラメータのための少なくとも一つのプログラミング入力と、
前記プログラミング入力に接続され、前記複数のプログラム可能なトレリス・パラメータに基づいて定義される少なくとも一つのトレリス構造を含むプログラム可能なトレリス・デコーダを実装するプログラム可能なデバイスとを有する、
デコーダ。
【請求項２】
前記プログラム可能なデバイスが現場プログラム可能なゲート・アレイ（FPGA）を含む、請求項１記載のプログラム可能なデコーダ。
【請求項３】
請求項１記載のプログラム可能なデコーダであって、前記複数のプログラム可能なトレリス・パラメータがさらに：
いくつかのトレリス構造；
各トレリス構造についてのいくつかのトレリス状態；および
各トレリス状態についていくつかの枝を含む、
デコーダ。
【請求項４】
請求項１記載のプログラム可能なデコーダであって、さらに、出力当たり複数ビットをもつデコードされたビットおよびある最良経路についてデコードされた全ビットの完全なトレースバックを出力する、前記プログラム可能なデバイスに接続された少なくとも一つの出力をさらに有する、デコーダ。
【請求項５】
請求項１記載のプログラム可能なデコーダであって、さらに、最良の経路メトリックと最悪の経路メトリックの差を出力する、前記プログラム可能なデバイスに接続された少なくとも一つの出力をさらに有する、デコーダ。
【請求項６】
請求項１記載のプログラム可能なデコーダであって、さらに、現在の最良経路についての勝ち状態を出力する、前記プログラム可能なデバイスに接続された少なくとも一つの出力をさらに有する、デコーダ。
【請求項７】
プログラム可能なトレリス・デコーダを実装する方法であって：
各トレリス段についてアクティブまたは非アクティブ状態となるトレリス段のためのトレリス接続性情報、トレリス枝遷移データ値およびトレリス枝遷移についてのメトリック・インデックスを含む複数のプログラム可能なトレリス・パラメータに基づいて定義される少なくとも一つのトレリス構造を有する、前記プログラム可能なトレリス・デコーダを実装するプログラム可能なデバイスを提供する段階と；
前記プログラム可能なデバイスに接続された少なくとも一つのプログラミング入力を介して前記複数のプログラム可能なトレリス・パラメータをプログラムする段階とを有する、
方法。
【請求項８】
前記プログラム可能なデバイスが現場プログラム可能なゲート・アレイ（FPGA）を含む、請求項７記載の方法。
【請求項９】
請求項７記載の方法であって、前記複数のプログラム可能なトレリス・パラメータをプログラムする段階がさらに：
いくつかのトレリス構造をプログラムすること；
各トレリス構造についていくつかのトレリス状態をプログラムすること；および
各トレリス状態についていくつかの枝をプログラムすることを含む、
方法。
【請求項１０】
請求項７記載の方法であって、さらに：前記プログラム可能なデバイスに接続された少なくとも一つの出力であって：
出力当たり複数ビットをもつデコードされたビットおよびある最良経路についてデコードされた全ビットの完全なトレースバック；
最良の経路メトリックと最悪の経路メトリックの間の差；および
現在の最良経路についての勝ち状態、
のうちの少なくとも一つを出力するための出力を提供する段階を有する、
方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、デジタル通信の分野に、より詳細にはトレリス復号および関係する方法に関する。
【背景技術】
【０００２】
新世代のUHF衛星通信規格（MIL-STD-188-181C、MIS-STD-188-182B、MIL-STD-188-183B）は（最大で）54の異なるモデムがSATCOM端末内に同時に存在することを要求する。これらの規格は、既存の衛星通信スループットを２倍に高めるよう意図されたDAMA/IW（demand-Assigned  Multiple  Access/Integrated  Waveform［デマンド割り当てされる多重アクセス／統合波形］）を含む。DAMA/IW規格のためのモデムの設計は、ソフトウェアの複雑さを軽減し、開発および統合の時間を短縮するためにモデムの諸サブ機能を組み合わせるための新しい技法を要求する。実際、さまざまな衛星通信システムが限られたプログラム・スペース、CPU計算速度およびバッテリー・パワーをもつ。
【０００３】
前方誤り訂正（FEC:  Forward  Error  Correction）および最尤デコーダ（Maximum  Likelihood  Decoder）（たとえばビタビ（Viterbi）・アルゴリズム）の使用は、非特許文献１を含むたいていの標準的な通信テキストに記載されている。連続位相変調（Continuous  Phase  Modulation）は非特許文献２および非特許文献１のような書物に詳細に記載されている。
【０００４】
セルラーおよびPCS（personal  communications  system［パーソナル通信システム］）、コンピュータ通信システムおよびSATCOM（satellite  communications［衛星通信］）システムのようなデジタル通信システムでは、デジタル・データはモデムによって、通信チャネルを通じて送信されるべき信号に変調される。データは典型的には、該データをノイズのある通信チャネルまたは記憶媒体の欠陥から帰結しうる誤りから保護するために、受信器または記憶装置への送信に先立ってエンコードされる。エンコーダは誤り訂正符号に従ってデータ・シンボルを操作し、誤り訂正シンボルまたは構造化された冗長出力シーケンスを生成する。符号語がのちに受信または取得されるとき、該符号語はデコードされてデータ・シンボルを再現し、データ・シンボル中の誤りは可能であれば誤り訂正シンボルまたは符号の構造化された冗長性を使って訂正される。
【０００５】
以下の議論のために、畳み込み符号語（convolutional  codeword）は、k個の入力ビットの入力に基づいて生成されるn個の出力ビットとして定義される（すなわち、符号化率k/nの符号）。畳み込み符号を使ってエンコードされる符号語をデコードする一つの方法は、一般に最尤復号（maximum  likelihood  decoding）と称される。最尤復号の一つの種類は一般にビタビ・デコーダと称される。概念としては、ビタビ・デコーダは復号トレリスを使用する。復号トレリスは、可能な各符号語について枝〔ブランチ〕をもち、符号語の可能な各ストリームまたはシーケンスについて枝からなる接続された経路〔パス〕をもつ。このデコーダは、本質的には、トレリスを通る経路であって、受信された符号語のストリームに「最も近い」、あるいは最も似ているものを見出す。このデコーダはその際、この「最も確からしい」トレリス経路上の符号語を受信された符号語として扱い、それらにデータ値を割り当てることによって、送信されたデータの最良推定値を生成する。
【０００６】
最も確からしい経路を決定するため、前記デコーダは、受信された各符号語について、一組の枝メトリックを計算する。枝メトリックは、受信時に誤りを含んでいる可能性のある送信された符号語が実際にある特定の枝に対応する符号語である確からしさの数値的な表現である。そのようなデコーダの一つでは、枝メトリックは、受信された符号語とさまざまな枝に関連付けられた符号語との間のハミング距離である。
【０００７】
復号トレリス内の各枝は、その枝に関連付けられた符号語の形成に先立つレジスタの状態を表す初期状態から出て、符号語の形成後のレジスタの状態を表す終状態まで行く。バイナリー符号については、Kを符号の拘束長として、各デコード・レベルに関連付けられている2K-1個の可能な状態がある。たとえば、符号は拘束長3をもちうる。すなわち、2つのレジスタがあり、各デコード・レベルには４つの可能なレジスタ状態、すなわち00、01、10、11がある。符号化率1/nの符号については、各初期状態から出る二つの可能な枝、すなわち、0のデータ・ビットに関連付けられた枝および1のデータ・ビットに関連付けられた枝がある。これらの枝のそれぞれは必然的に異なる終状態につながる。よって、所与のデコード・レベルにおける2K-1個の状態のそれぞれについて、これらの状態のそれぞれにつながる二つの枝があり、各枝が送信された符号語を表しうる。したがって、符号語をデコードするためには、デコーダは2K-1個の可能な終状態のそれぞれについて二つの枝メトリックを、すなわち全部で2(2K-1)個の枝メトリックを決定しなければならない。
【０００８】
ひとたびデコーダがこれらの枝メトリックを計算すると、デコーダは次いで諸終状態につながるさまざまな経路のメトリックを決定する。したがって、デコーダは前記枝メトリックに、適切な経路メトリックを加える。経路メトリックは、初期状態につながる枝の和である。次いでデコーダは、終状態のそれぞれにつながる最も確からしい経路を選択し、のちの使用のために経路メトリックおよびこれらの最も確からしい経路を同定する情報を記憶する。これらの最も確からしい経路は「生き残り経路（surviving  path）」とも称される。デコーダは、それほど確からしくない、すなわち生き残っていない経路に関係する情報は保持しない。このように、デコーダはトレリスからこれらの経路を「枝払いし（prune）」、それにより次のレベルのデコードのために、経路メトリック計算の一部をなくす。
【０００９】
トレリス経路中に十分な数の符号語が含められているときは、最も確からしい符号語経路が、終状態に関連付けられている生き残り経路から選ばれる。デコーダは最も確からしい経路として、受信されたデータに「最も近い」符号語経路、すなわち最小のハミング距離メトリックをもつ経路を選択する。次いでデコーダはその最も確からしい経路に基づいてデコードする、すなわち該経路に沿って「トレースバックして（trace  back）」関連付けられたデータ・ビットを決定する。
【００１０】
ビタビ・アルゴリズムは、畳み込み符号をデコードするために使用されるのみならず、シンボル間干渉（ISI:  intersymbol  interference）をもつチャネルを通じて送信されたシーケンスの最尤推定値を生成するためにも使用される。ビタビ・デコーダは三つの機能部分に分けられる。第一の部分は、経路メトリックを計算するために使用される加算‐比較‐選択（ACS:  add-compare-select）ユニットである。第二の部分は、生き残りメモリ管理（survivor  memory  management）のための生き残りメモリ制御ユニットである。生き残りシーケンスを記憶するために使用される生き残りメモリ（survivor  memory）がビタビ・デコーダの最後の部分である。
【００１１】
連続位相変調（CPM）は、その帯域幅効率および一定のエンベロープ特性のため通信において適用されている。CPMでは、変調された信号位相遷移はなめらかにされる。たとえば、二相位相偏移符号化（BPSK:  binary  phase  shift  keying）では、論理的な1が変調された信号の一つの位相として伝送され、論理的な0は位相の鋭い遷移をもって、180度シフトした位相として伝送される。この鋭い位相遷移は伝送されるスペクトルの広がりを生む。CPMでは、伝送される信号の位相は、変調デジタル信号の諸ビットにわたってなめらかな位相変化をする。CPMの一例は最小偏移符号化（MSK:  minimum  shift  keying）変調である。
【００１２】
マルチh連続位相変調（マルチh型CPM）はそれ自身、変調された波形の幅広いクラスである。このクラスは一定振幅だが変動する位相をもつ信号を含む。マルチh型CPMは、単一h型フォーマットとは、一組のH変調インデックスを巡回的な仕方で使用することによって異なっている。これは、近傍の位相トレリス経路の遅延されたマージにつながり、究極的には改善されたエラー性能につながる。マルチh型CPM波形の詳細な記述は非特許文献２に含まれる。
【００１３】
米国カリフォルニア州サンノゼのザイリンクス社（Xilinx,  Inc.）は、非特許文献３に記載されるようなパラメータ化可能な拘束長、畳み込み符号およびトレースバック長（traceback  length）をもつFPGAビタビ・デコーダを提供する。しかしながら、そのようなFPGAビタビ・デコーダは、CPM信号とともに使うためにプログラム可能ではない。
【００１４】
前方誤り訂正（FEC:  Forward  Error  Correction）符号は、通信産業において普通に使用されている。FEC符号の復調および復号のために使用されるデジタル信号処理技術は当技術分野ではよく知られている。しかしながら、CPM（たとえばマルチh型CPM）とFEC符号の使用との組み合わせは新しいプログラム可能なデコーダを要求する。業界では、たとえば畳み込み符号、トレリス符号化された変調波形、ISIチャネル、単一hおよびマルチh型CPMをデコードするために使用できる一般トレリス・デコーダの必要性がある。
【先行技術文献】
【非特許文献】
【００１５】
【非特許文献１】ジョン・G・プローキス（John  G.  Proakis）、「デジタル通信（Digital  Communications）」
【非特許文献２】アンダーソン（Anderson）、オーリン（Aulin）、サンドバーグ（Sundberg）、「デジタル位相変調（Digital  Phase  Modulation）」、プリーナム・プレス（Plenum  Press）、ニューヨーク、1986年
【非特許文献３】ザイリンクス社、データ・シートDS247(v1.0)、2003年3月28日
【発明の概要】
【発明が解決しようとする課題】
【００１６】
したがって、上記の背景に鑑み、畳み込み符号、トレリス符号化変調（TCM:  trellis  coded  modulation）、ISIチャネルおよびCPM波形をデコードできるプログラム可能なトレリス・デコーダを提供することが本発明の一つの目的である。
【課題を解決するための手段】
【００１７】
本発明に基づくこのおよびその他の目的、特徴および利点は、最尤シーケンス推定（MLSE:  Maximum  Likelihood  Sequence  Estimation）デコーダ（たとえばビタビ・デコーダ）のようなプログラム可能なデコーダであって、各トレリス段についてアクティブまたは非アクティブ状態となるトレリス段のためのトレリス接続性情報、トレリス枝遷移データ値およびトレリス枝遷移についてのメトリック・インデックスを含む複数のプログラム可能なトレリス・パラメータのための少なくとも一つのプログラミング入力を含むデコーダによって提供される。プログラム可能なデバイスが前記プログラミング入力に接続され、プログラム可能なデコーダおよび畳み込み符号、TCM、ISIチャネルおよびCPMといった多くの異なるトレリス・ベースの復号スキームを実装し、前記複数のプログラム可能なトレリス・パラメータに基づいて定義される少なくとも一つのトレリス構造を含む。
【００１８】
前記プログラム可能なデバイスは、現場プログラム可能なゲート・アレイ（FPGA:  field  programmable  gate  array）を有していてもよい。前記複数のプログラム可能なトレリス・パラメータは、いくつかのトレリス構造、各トレリス構造についてのいくつかのトレリス状態、および各トレリス状態についていくつかの枝を含んでいてもよい。また、トレリス構造は逆状態（reverse-state）トレリス構造を含んでいてもよい。
【００１９】
前記プログラム可能なデバイスに、出力が接続されていてもよい。該出力は、出力当たり複数ビットをもつデコードされたビットおよびある最良経路についてデコードされた全ビットの完全なトレースバックを出力するため、最良の経路メトリックと最悪の経路メトリックの間の差を出力するため、および／または現在の最良経路についての勝ち状態（winning  state）を出力するためである。
【００２０】
本発明の方法側面は、プログラム可能なトレリス・デコーダを実装する方法に向けられており、各トレリス段についてアクティブまたは非アクティブ状態となるトレリス段のためのトレリス接続性情報、トレリス枝遷移データ値およびトレリス枝遷移についてのメトリック・インデックスを含む複数のプログラム可能なトレリス・パラメータに基づいて定義される少なくとも一つのトレリス構造を有する（連続位相変調（CPM）デコーダのような）トレリス・デコーダを実装するプログラム可能なデバイス（FPGAのような）を提供することを含む。本方法はさらに、前記トレリス・デコーダに接続された少なくとも一つのプログラミング入力を介して前記複数のプログラム可能なトレリス・パラメータをプログラムすることを含む。
【００２１】
前記複数のプログラム可能なトレリス・パラメータをプログラムすることはいくつかのトレリス構造をプログラムすること、各トレリス構造についていくつかのトレリス状態をプログラムすること、各トレリス状態についていくつかの枝をプログラムすることを含んでいてもよい。前記方法は、前記プログラム可能なデバイスに接続された少なくとも一つの出力であって、出力当たり複数ビットをもつデコードされたビットおよびある最良経路についてデコードされた全ビットの完全なトレースバックを出力するため、最良の経路メトリックと最悪の経路メトリックの間の差を出力するため、および／または現在の最良経路についての勝ち状態（winning  state）を出力するための出力を提供することを含んでいてもよい。
【００２２】
さまざまな要件を満たすため、プログラム可能であり、任意のFEC符号をもつCPM、SOQPSK、BPSKおよびQPSKの復調をサポートする、FPGAベースの最尤デコーダが設計されている。それは、バイナリーh、4値（4-ary）、CPMをサポートするよう設計されている。入力のプログラム可能性は、各トレリス中の状態の数、状態当たりの枝の数、トレリス構造の数（たとえばバイナリーh型CPMは二つの異なるトレリスをもつ）、ならびに、各状態を前の状態のリストおよび現在状態に分岐してくるシンボルに付随するデータ・ビット（単数または複数）と接続する逆状態トレリス構造自身を含む。デコーダの出力は、出力当たり複数ビットをもつデコードされたビットおよびその経路についてデコードされた全ビットの完全なトレースバック、最良の経路メトリックと最悪の経路メトリックの間の差、および現在の最良経路についての勝ち状態（winning  state）を含む。
【図面の簡単な説明】
【００２３】
【図１】本発明に基づくプログラム可能型トレリス・デコーダを含む受信器のブロック図である。
【図２】図１の受信器におけるプログラム可能型トレリス・デコーダのより詳細なブロック図である。
【図３】本発明のプログラム可能型トレリス・デコーダを実装する方法におけるステップを示すフローチャートである。
【発明を実施するための形態】
【００２４】
ここで本発明について、以下で付属の図面を参照しつつより十全に記載する。図面には本発明の好ましい実施形態が示されている。しかしながら、本発明は、多くの異なる形で具現されてもよく、本稿に記載される実施形態に限定されると解釈されるべきではない。むしろ、これらの実施形態は、本開示が十全かつ完備であり、当業者に本発明の範囲を十分に伝達するよう提供されるものである。同様の参照符号は全体を通じて同様の要素を指し、プライム記号は代替的な実施形態における類似の要素を示す。
【００２５】
まず図１および図２を参照しつつ、一般プログラム可能型トレリス・デコーダ（generic  programmable  trellis  decoder）３０（たとえば、連続位相変調（CPM）プログラム可能型デコーダ）を含むUHF衛星通信受信器のようなデータ通信受信器１０の実施形態について述べる。通信チャネル１２を通じて送られるエンコードされ変調された信号が受信器１０によって受信される。復調器２０がはいってくる信号を処理し、次いでベースバンドの復調された信号をプログラム可能型トレリス・デコーダ３０に送る。プログラム可能型トレリス・デコーダ３０はその信号を処理し、次いでデコードされたデータおよびその他の関係する情報を、チャネル１４を通じて目的地に送る。受信器のコンポーネント、たとえば復調器２０およびプログラム可能型トレリス・デコーダ３０は、プロセッサ５０によって制御される。
【００２６】
最尤シーケンス推定（MLSE）デコーダ（たとえばビタビ・デコーダ）のようなプログラム可能型トレリス・デコーダ３０は、複数のプログラム可能なトレリス・パラメータのための少なくとも一つのプログラミング入力３４、３６を含む。前記複数のプログラム可能なトレリス・パラメータは好ましくは、各トレリス段（trellis  stage）についてアクティブまたは非アクティブ状態となるトレリス段のためのトレリス接続性情報、トレリス枝遷移データ値およびトレリス枝遷移についてのメトリック・インデックスを含み、いくつかのトレリス構造、各トレリス構造についてのいくつかのトレリス状態および各トレリス状態についてのいくつかの枝を含んでいてもよい。また、トレリス構造は逆状態トレリス構造および／または前方状態（forward-state）トレリス構造を含んでいてもよい。
【００２７】
プログラム可能な最尤デコーダは、典型的には、畳み込みでエンコードされたビットのシーケンスを受領し、トレリス状態図の各枝に関連付けられた枝メトリックに基づいて経路メトリックおよび出力シーケンスを計算する加算‐比較‐選択（ACS）ユニットと、出力シーケンスを記憶する生き残りメモリと、前記生き残りメモリを制御し、記憶された出力シーケンスのデコードされたビットを出力する生き残りメモリ制御ユニットとを含む。当業者はこれを理解するであろう。
【００２８】
プログラム可能なデバイス３２が前記プログラミング入力に接続され、前記複数のプログラム可能なトレリス・パラメータに基づいて定義される少なくとも一つのトレリス構造をもつプログラム可能型トレリス・デコーダ（たとえば、連続位相変調（CPM）デコーダ）を実装する。プログラム可能なデバイス３２は、たとえば現場プログラム可能なゲート・アレイ（FPGA）であってもよい。
【００２９】
FPGAは、プログラム可能な論理コンポーネントおよびプログラム可能な相互接続を含む半導体デバイスである。プログラム可能な論理コンポーネントは、基本的な論理ゲートの機能性（AND、OR、XOR、NOTのような）またはデコーダもしくは簡単な数学機能といったより複雑な組み合わせ機能を複製するようプログラムされることができる。たいていのFPGAでは、これらのプログラム可能な論理コンポーネント（または論理ブロック）はメモリ要素をも含む。メモリ要素は簡単なフリップフロップであってもよいし、あるいはより完全なメモリ・ブロックであってもよい。
【００３０】
プログラム可能な相互接続の階層構造が、FPGAの論理ブロックを、システム設計者の必要に応じて相互接続されることを許容する。ワンチップのプログラム可能なブレッドボードに似ていなくもない。これらの論理ブロックおよび相互接続は、そのFPGAが必要とされるどんな論理機能でも実行できるよう顧客／設計者によって製造工程後にプログラムされることができる（すなわち、「現場プログラム可能」）。
【００３１】
FPGAは一般に、特定用途向け集積回路（ASIC:  application-specific  integrated  circuit）の対応物より遅く、それほど複雑な設計を扱えず、より多くの電力を食う。しかしながら、FPGAは、市場投入までの時間がより短い、バグを直すために現場でプログラムし直せる、あるいは非反復エンジニアリングのコストがより低いといったいくつかの利点がある。
【００３２】
FPGAの振る舞いを定義するため、ユーザーはハードウェア記述言語（HDL:  hardware  description  language）または概略的設計を提供する。一般的なHDLはVHDLおよびVerilogである。その際、電子的な設計自動化ツールを使って、技術マップされたネットリスト（technology-mapped  netlist）が生成される。そのネットリストは次いで、通例プレース・アンド・ルート・ソフトウェアによって実行されるプレース・アンド・ルート（配置と配線［place-and-route］）というプロセスを使って、実際のFPGAアーキテクチャに当てはめることができる。次いでユーザーが、タイミング解析、シミュレーションおよび他の検証方法を介して、マップ、プレース・アンド・ルート結果を検証する。ひとたび設計および検証プロセスが完了したら、生成されたバイナリ・ファイルが、FPGAデバイスを（再）構成するために使用される。そのようなバイナリ・ファイルは、制御入力ブロック３４を介してプログラム可能なデバイス３２に記憶され、および／または入力されてもよい。
【００３３】
一例として、プログラム可能型トレリス・デコーダ３０は、CPMおよび好ましくはマルチh型CPMを実装してもよい。CPMでは、伝送される信号の位相は、変調デジタル信号の諸ビットにわたってなめらかな位相変化をする。CMPの例は、最小偏移符号化（MSK）変調である。マルチh連続位相変調（マルチh型CPM）はそれ自身が変調された波形の幅広いクラスである。このクラスは一定振幅だが変動する位相をもつ信号を含む。マルチh型CPMは単一h型フォーマットとは、一組のH変調インデックスを巡回的な仕方で使用することによって異なっている。これは、近傍の位相トレリス経路の遅延されたマージにつながり、究極的には改善されたエラー性能につながる。
【００３４】
プログラム可能なデバイス３２の一つまたは複数の出力３８、４０、４２が、出力当たり複数ビットをもつデコードされたビットおよびある最良経路についてデコードされた全ビットの完全なトレースバックを出力するため、最良の経路メトリックと最悪の経路メトリックの間の差を出力するため、および／または現在の最良経路についての勝ち状態（winning  state）を出力するために設けられる。
【００３５】
一般プログラム可能型トレリス・デコーダ３０は、上述したトレリス方式すべてを扱うために、該デコーダ中に適切な構造および柔軟性を提供する。トレリス段当たりのアクティブおよび非アクティブ状態は、開始状態および状態間のデルタ増分またはアクティブ／非アクティブ・フラグを有することによってできる。現在および次のアクティブ状態の間に良好なデルタ増分のない場合がありうるので、アクティブ／非アクティブのほうがより多くの柔軟性を提供する。追加的な計算を避けるために各トレリス段のための異なる開始状態が提供されてもよいが、ここでもアクティブ／非アクティブ状態は機能する。枝メトリックとして使用されるべきメトリックは、要求されるトレリス段、ノード識別および枝接続に基づいてユーザーによって提供される。アクティブな状態のためのメトリックのみが計算される必要がある。加算／比較／選択点における逆ルックアップ・テーブルを介して、各トレリス段について枝接続の異なるセットが含められる。
【００３６】
段（stage）0についての例（トレリスが16個の状態をもつ場合、各トレリス段について16の状態があることになる）。反復構造は４トレリス段の長さであってもよく、各段について、アクティブおよび非アクティブな段および逆ルックアップ・テーブルがある。この型の構造はマルチh型CPMには必須だが、この同じ構造はより複雑でないトレリス方式についても、単にトレリス逆ルックアップ・テーブルの接続性およびアクティブ／非アクティブ状態の選択を変えることにより、使用できる。こうして、このアプローチは、現在利用可能な単純な畳み込み／TCMデコーダ以外の多くのさらなるトレリス方式を扱うことができる一般トレリス・デコーダに導く。
【００３７】
一例として、マルチh型CPM波形が一般プログラム可能型トレリス・デコーダ３０で復調されうる。マルチhは、各CPMシンボルについて異なる変調インデックスhを含意する。2hの場合、シンボル一つおきに変化する二つの異なるhの値がある。たとえば、h0＝4/16、h1＝5/16をもつバイナリーCPM。偶数シンボルは変調インデックスh0を使い、奇数シンボルは変調インデックスh1を使う。h0＝4/16については、トレリス逆接続性（trellis  backward  connectivity）は次のようになる（データ０＝負の周波数（すなわち、データ＝−1）；データ１＝正の周波数）。
【００３８】
フォーマット：状態番号：前のデータ＝０  前のデータ＝１
状態0:  4  12
状態1:  5  13
状態2:  6  14
状態3:  7  15
状態4:  8  0
状態5:  9  1
状態6:  10  2
状態7:  11  3
状態8:  12  4
状態9:  13  5
状態10:  14  6
状態11:  15  7
状態12:  0  8
状態13:  1  9
状態14:  2  10
状態15:  3  11
h1=5/16については、トレリス逆接続性は次のようになる。
【００３９】
状態0:  5  11
状態1:  6  12
状態2:  7  13
状態3:  8  14
状態4:  9  15
状態5:  10  0
状態6:  11  1
状態7:  12  2
状態8:  13  3
状態9:  14  4
状態10:  15  5
状態11:  0  6
状態12:  1  7
状態13:  2  8
状態14:  3  9
状態15:  4  10
シンボル（段）1、2、…、8についてトレリス構造を解析すると：
フォーマット：H#  開始状態  デルタ状態
段1  H0  0  2
段2  H1  0  2
段3  H0  1  2
段4  H1  1  2
段5  H0  0  2
段6  H1  0  2
段7  H0  1  2
段8  H1  1  2
段１をデコードするためには、状態0で開始し、次の状態については状態を２だけインクリメントする（すなわち、偶状態だけがアクティブ）。段２については、やはり偶状態だけをデコードする。段３については奇状態だけをデコードし、段４については奇状態だけをデコードし、パターンを繰り返していく。
【００４０】
一般プログラム可能型トレリス・デコーダ３０がアクティブ状態および非アクティブ状態（最も一般的な場合について）または開始状態およびデルタ状態（代替的な実施形態として）をもつ能力を提供するのはこのためである。また、逆トレリス構造（backward  trellis  structure）がCPMを適正にデコードする必要があることがありうる。
【００４１】
よって、一般プログラム可能型トレリス・デコーダ３０の、波形の復調における使用に先立つ初期化プロセスをここで要約しておく。トレリス構造は：段N；トレリス接続性；アクティブ／非アクティブ状態；遷移を引き起こすデータ値（すなわち、枝遷移データ値）；および所与のトレリス枝遷移についてのメトリック・インデックスを含む。
【００４２】
まず、トレリス構造（たとえば、CPMまたはその他についての）が解析されて、アクティブ／非アクティブ状態および接続性を決定する。接続性情報は、パターンが繰り返す前に必要なだけの数のトレリス段についてデコーダに書き込まれる（典型的には、畳み込み符号についてはただ一つの段、1h  CPMについては２段、上記の2h  CPMの例については４段）。アクティブ／非アクティブ状態（または開始状態およびデルタ状態）が、トレリス・デコーダの各トレリス段について書き込まれる（パターンが繰り返す前）。トレリス枝遷移を引き起こすデータ値はトレリス・デコーダ構造に書き込まれる。トレリス枝遷移のために使われるメトリック・インデックスはトレリス・デコーダに書き込まれる。
【００４３】
例：トレリス枝構造状態０。逆トレリス構造は：枝メトリック・インデックス0を使う、0のビットを介した状態４から状態０；枝メトリック・インデックス1を使う、1のビットを介した状態１２から状態０；枝メトリック・インデックス2を使う、0のビットを介した状態５から状態１；枝メトリック・インデックス3を使う、1のビットを介した状態１３から状態１、などを含む。
【００４４】
データの復調を開始するため、枝メトリック・アレイがトレリス・デコーダに書き込まれ（これはメトリック・インデックスを使うデコーダによって使われることになる）；加算／比較／選択機能が各アクティブ状態について実行され；トレースバック機能がデコードされた情報を抽出するために実行され；出力データがユーザーに提供される。
【００４５】
本発明の方法側面は、一般プログラム可能型トレリス・デコーダ３０（連続位相変調（CPM）デコーダのような）を実装する方法に向けられており、図３のフローチャートを参照して論じる。本方法はブロック１００で始まり、ブロック１０２において、プログラム可能型トレリス・デコーダ３０を実装するための、複数のプログラム可能なトレリス・パラメータに基づいて定義される少なくとも一つのトレリス構造を含むプログラム可能なデバイス３２（FPGAのような）を提供することを含む。前記複数のプログラム可能なトレリス・パラメータは、好ましくは、諸トレリス段のためのトレリス接続性情報、各トレリス段についてのアクティブおよび非アクティブ状態、トレリス枝遷移データ値およびトレリス枝遷移についてのメトリック・インデックスを含む。本方法はさらに、少なくとも一つのプログラミング入力を介して前記複数のプログラム可能なトレリス・パラメータをプログラムすることを含む（ブロック１０４）。
【００４６】
上で論じたように、前記複数のプログラム可能なトレリス・パラメータをプログラムすることは、いくつかのトレリス構造をプログラムすること、各トレリス構造についていくつかのトレリス状態をプログラムすること、および各トレリス状態についていくつかの枝をプログラムすることを含んでいてもよい。本方法は、ブロック１０６において、前記プログラム可能なデバイス３２に接続された少なくとも一つの出力であって、デコードされたビットを、出力当たり複数ビットをもって、最良経路についてデコードされた全ビットの完全なトレースバックをもって出力するため、最良の経路メトリックと最悪の経路メトリックの間の差を出力するため、および／または現在の最良経路についての勝ち状態（winning  state）を出力するための出力を提供することを含んでいてもよい。
【００４７】
さまざまな要件を満たすため、プログラム可能であり、任意のFEC符号をもつCPM、SOQPSK、BPSKおよびQPSKの復調をサポートする、FPGAベースの最尤デコーダが設計されている。それは、バイナリーh、4値（4-ary）、CPMをサポートするよう設計されている。入力のプログラム可能性は、各トレリス中の状態の数、状態当たりの枝の数、トレリス構造の数（マルチh型CPMは二つの異なるトレリスをもつ）、ならびに、各状態を前の状態のリストおよび現在状態に分岐するシンボルに付随するデータ・ビット（単数または複数）と接続する逆状態トレリス構造自身を含む。デコーダの出力は、出力当たり複数ビットをもち、その経路についてデコードされた全ビットの完全なトレースバックをもつデコードされたビット、最良の経路メトリックと最悪の経路メトリックの間の差、および現在の最良経路についての勝ち状態（winning  state）を含む。逆状態（reverse-state）トレリス構造の代わりに順状態（forward-state）トレリス構造を使うことによって、やや複雑になるが等価な装置を作成することもできることを注意しておく。さらに、デコードされたビットの完全なトレースバックの代わりに、関心のあるビットのみ（たとえばトレースバックの深さだけ離れたビット（単数または複数）（最も古い最も信頼できるビット（単数または複数）））が提供されることができる。
【００４８】
畳み込み符号について、枝メトリックがエンコーダからのビット数によって決定されることを注意しておくべきであろう。たとえば、符号化率1/2の符号については、４つのメトリックしかない（22）（トレリス状態の数とは独立）。CPMについては、メトリックの数はずっと多くなる。というのも、トレリスを通じた各経路が一意的なCPM波形となるからである。各トレリス枝経路メトリックに関連付けられたインデックスをもつことによって、両方の場合がカバーされる（そしてTCMおよびISIチャネルのような他の場合も）。
【００４９】
完全なトレースバックは、必須ではない追加的特徴である。完全なトレースバックをもつことにより、データについてはデコーダによって出力される最も古いビットを使いながら、デコーダによるより新しいデータ出力が位相追跡（phase  tracking）および／またはシンボル・タイミング・ループのために使用されることができる（より小さな遅延）（データがより古い、すなわちトレースバックがより大きいとは、データがより信頼できることになるがより大きな遅延がある）。キャリア追跡（carrier  tracking）およびシンボル・タイミング・ループは長い遅延をもちたがらないので、より遅延の少ないビットを使う。しかしながら、追跡ループのために使用される、より遅延の少ないビットさえ、トレリスのいくらかの符号化利得から裨益することになる（追跡ループのための遅延なしの決定を使うことに比べたとき）。
【図１】
2010503351.tif 000003
【図２】
2010503351.tif 000004
【図３】
2010503351.tif 000005
【手続補正書】
【提出日】平成20年7月21日(2008.7.21)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
プログラム可能なデコーダであって：
各トレリス段についてアクティブまたは非アクティブ状態となるトレリス段のためのトレリス接続性情報、トレリス枝遷移データ値およびトレリス枝遷移についてのメトリック・インデックスを含む複数のプログラム可能なトレリス・パラメータのための少なくとも一つのプログラミング入力と、
前記複数のプログラム可能なトレリス・パラメータに基づいて定義される少なくとも一つのトレリス構造を含み、畳み込み符号、トレリス符号化変調（TCM）、ISIチャネルおよびCPM波形を復号するプログラム可能なトレリス・デコーダを実装する、前記プログラミング入力に接続されたプログラム可能なデバイスとを有する、
デコーダ。
【請求項２】
前記プログラム可能なデバイスが現場プログラム可能なゲート・アレイ（FPGA）を含む、請求項１記載のプログラム可能なデコーダ。
【請求項３】
請求項１記載のプログラム可能なデコーダであって、前記複数のプログラム可能なトレリス・パラメータがさらに：
いくつかのトレリス構造；
各トレリス構造についてのいくつかのトレリス状態；および
各トレリス状態についていくつかの枝を含む、
デコーダ。
【請求項４】
請求項１記載のプログラム可能なデコーダであって、さらに、出力当たり複数ビットをもつデコードされたビットおよびある最良経路についてデコードされた全ビットの完全なトレースバックを出力する、前記プログラム可能なデバイスに接続された少なくとも一つの出力をさらに有する、デコーダ。
【請求項５】
請求項１記載のプログラム可能なデコーダであって、さらに、最良の経路メトリックと最悪の経路メトリックの差を出力する、前記プログラム可能なデバイスに接続された少なくとも一つの出力をさらに有する、デコーダ。
【請求項６】
請求項１記載のプログラム可能なデコーダであって、さらに、現在の最良経路についての勝ち状態を出力する、前記プログラム可能なデバイスに接続された少なくとも一つの出力をさらに有する、デコーダ。
【請求項７】
プログラム可能なトレリス・デコーダを実装する方法であって：
各トレリス段についてアクティブまたは非アクティブ状態となるトレリス段のためのトレリス接続性情報、トレリス枝遷移データ値およびトレリス枝遷移についてのメトリック・インデックスを含む複数のプログラム可能なトレリス・パラメータに基づいて定義される少なくとも一つのトレリス構造を有する、畳み込み符号、トレリス符号化変調（TCM）、ISIチャネルおよびCPM波形を復号する前記プログラム可能なトレリス・デコーダを実装するプログラム可能なデバイスを提供する段階と；
前記プログラム可能なデバイスに接続された少なくとも一つのプログラミング入力を介して前記複数のプログラム可能なトレリス・パラメータをプログラムする段階とを有する、
方法。
【請求項８】
前記プログラム可能なデバイスが現場プログラム可能なゲート・アレイ（FPGA）を含む、請求項７記載の方法。
【請求項９】
請求項７記載の方法であって、前記複数のプログラム可能なトレリス・パラメータをプログラムする段階がさらに：
いくつかのトレリス構造をプログラムすること；
各トレリス構造についていくつかのトレリス状態をプログラムすること；および
各トレリス状態についていくつかの枝をプログラムすることを含む、
方法。
【請求項１０】
請求項７記載の方法であって、さらに：前記プログラム可能なデバイスに接続された少なくとも一つの出力であって：
出力当たり複数ビットをもつデコードされたビットおよびある最良経路についてデコードされた全ビットの完全なトレースバック；
最良の経路メトリックと最悪の経路メトリックの間の差；および
現在の最良経路についての勝ち状態、
のうちの少なくとも一つを出力するための出力を提供する段階を有する、
方法。
【国際調査報告】
2010503351.tif 000006
2010503351.tif 000007
2010503351.tif 000008