(57)【要約】プログラム可能復号器は、複数のプログラム可能な削減状態数トレリス・パラメータのための少なくとも一つのプログラミング入力を含む。プログラム可能デバイスが前記少なくとも一つのプログラミング入力に接続され、前記複数のプログラム可能な削減状態数トレリス・パラメータに基づく少なくとも一つの削減状態数トレリス構造を有する削減状態数シーケンス推定（RSSE）復号器を実装する。前記複数のプログラム可能な削減状態数トレリス・パラメータは、少なくとも超状態の数、完全状態の数、超状態当たりの枝の数、逆超状態トレリス・テーブル、完全状態としての復号器超状態生き残り者、前方完全状態テーブル、完全状態から超状態へのマッピング・テーブル、復号器超状態経路メトリックおよび復号器超状態逆行トレース配列のうちの一つを含む。
2010517373.tif 000002
【特許請求の範囲】
【請求項１】
プログラム可能復号器であって、
複数のプログラム可能な削減状態トレリス・パラメータのための少なくとも一つのプログラミング入力と；
前記少なくとも一つのプログラミング入力に接続され、前記複数のプログラム可能な削減状態トレリス・パラメータに基づく少なくとも一つの削減状態トレリス構造を有する削減状態シーケンス推定（RSSE）復号器を実装するプログラム可能デバイスとを有し、前記複数のプログラム可能な削減状態トレリス・パラメータは、少なくとも超状態の数、完全状態の数、超状態当たりの枝の数、逆超状態トレリス・テーブル、完全状態としての復号器超状態生き残り者、前方完全状態テーブル、完全状態から超状態へのマッピング・テーブル、復号器超状態経路メトリックおよび復号器超状態トレースバック配列のうちの一つからなる、
プログラム可能復号器。
【請求項２】
すべてのプログラム可能なパラメータが整数である、請求項１記載のプログラム可能復号器。
【請求項３】
前記復号器状態構造が、超状態当たりの経路メトリック、超状態当たりのトレースバックおよび超状態当たりの生き残り完全状態からなる、請求項１記載のプログラム可能復号器。
【請求項４】
当該復号器がメモリーをもつ波形および／または前方誤り訂正（FEC）符号を有する波形の復調をサポートする、請求項１記載のプログラム可能復号器。
【請求項５】
当該復号器が、連続位相変調（CPM）、ISIチャネルおよびトレリス符号化変調（TCM）の復調をサポートする、請求項１記載のプログラム可能復号器。
【請求項６】
前記RSSE復号器が、経路メトリック、判定帰還のために使われる完全復号器状態およびトレースバック配列を含む復号器状態構造を有する、請求項１記載のプログラム可能復号器。
【請求項７】
プログラム可能復号器を実装する方法であって：
複数のプログラム可能な削減状態トレリス・パラメータに基づく少なくとも一つの削減状態トレリス構造を有する削減状態シーケンス推定（RSSE）復号器を実装するプログラミング・デバイスを用意する段階であって、前記複数のプログラム可能な削減状態トレリス・パラメータは、少なくとも超状態の数、完全状態の数、超状態当たりの枝の数、逆超状態トレリス・テーブル、完全状態としての復号器超状態生き残り者、前方完全状態テーブル、完全状態から超状態へのマッピング・テーブル、復号器超状態経路メトリックおよび復号器超状態トレースバック配列のうちの一つからなる、段階と、前記複数のプログラム可能な削減状態トレリス・パラメータを、前記プログラム可能デバイスに結合された少なくとも一つのプログラミング入力を介してプログラムする段階とを有する、方法。
【請求項８】
メモリーをもつ波形および／または前方誤り訂正（FEC）符号を有する波形を前記プログラミング・デバイス内で復調する段階をさらに有する、請求項７記載の方法。
【請求項９】
連続位相変調（CPM）、ISIチャネルおよびトレリス符号化変調（TCM）を前記プログラミング・デバイス内で復調する段階をさらに有する、請求項７記載の方法。
【請求項１０】
経路メトリックおよび判定帰還のために使われる完全復号器状態を含む復号器状態構造を形成する段階をさらに有する、請求項７記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は通信システムに関し、より詳細には、本発明は通信システムにおいて使用されるトレリス復号に関する。
【背景技術】
【０００２】
通信システムにおいて使用される誤り訂正および検出システムは、ノイズに起因する誤りまたは伝送中の他の信号損傷を検出し、誤りの局在化および誤り訂正を可能にする。前方誤り訂正（FEC:  forward  error  correction）はデータ伝送のための誤り制御を許容するものであるが、受信機がデータの再送信を要求することなく誤りを訂正できるので標準的な誤り検出および訂正システムとは異なる。どんなFECシステムにおいても、使用される符号の設計が前もって訂正されることができる誤りの最大割合を決定する。結果として、異なる条件のためには異なるFEC符号が好適となりうる。
【０００３】
たとえば、多くのFEC方式では、所定のアルゴリズムを使って冗長性が送信されるデータに加えられる。冗長ビットのそれぞれは、もとの情報ビットの複雑な関数である。結果として、エンコードされた出力はもとの情報を含んでいてもいなくてもよい。出力における未修正の入力は組織符号（systematic  codes）であり、未修正でない入力は非組織符号である。
【０００４】
FEC方式は、各データ・ビットが多くの伝送されるシンボルに影響するので、ノイズを平均化すると考えることができる。いくつかのシンボルは他のシンボルよりもノイズによってより崩されるので、このことは、もとのデータが、同じユーザー・データに依存する他のそれほど崩されていない受信信号から抽出されることを許容する。FEC符号が理論的なシャノン限界に近づき、より強力な符号が使われるにつれ、FEC方式は最小の信号対雑音比よりかなり上では機能するが、典型的には、信号がその最小比より小さいときは失敗する。
【０００５】
高めのモデム・データ・レート、たとえば1Mbpsを超えるモデム・データ・レートについては、FEC方式の計算量は、商業的に入手可能なデジタル信号プロセッサ（DSP）および現場プログラム可能なゲートアレイ（FPGA）技術の現状のもとでは禁止的となりうる。
【０００６】
前方誤り訂正（FEC）および最尤復号器（Maximum  Likelihood  Decoder）（たとえばビタビ・アルゴリズム）の使用は、非特許文献１を含むたいていの標準的な通信の教科書に網羅的に記載されている。連続位相変調は非特許文献２および非特許文献１のような書籍において詳細に記載されている。
【０００７】
デジタル通信システム、たとえば携帯電話およびPCS（personal  communications  systems）、コンピュータ通信システムおよびSATCOM（satellite  communications）システムでは、デジタル・データはモデムによって、通信チャネルを通じて伝送される信号上に変調される。データは典型的には受信機または記憶装置への送信の前に、ノイズのある通信チャネルまたは記憶媒体の欠陥から帰結しうる誤りからデータを保護するためにエンコードされる。エンコーダは、誤り訂正符号に従ってデータ・シンボルを操作し、誤り訂正シンボルまたは構造化された冗長出力シーケンスを生成する。符号語がのちに受信されるか取り出されるかするとき、該符号語は復号されて、データ・シンボルを再現し、データ・シンボル中の誤りは可能であれば、誤り訂正シンボルまたは符号の構造化された冗長性を使って訂正される。
【０００８】
以下の議論のため、畳み込み符号語は、k個の入力ビットの入力に基づいて生成されるn個の出力ビットとして定義される（すなわち、符号化率k/nの符号）。畳み込み符号を使ってエンコードされた符号語を復号する一つの方法は、最尤復号である。最尤復号器の一つの種類は、一般にビタビ復号器と称される。概念的には、ビタビ復号器は復号トレリスを使う。これは、可能な各符号語について枝を有し、複数の符号語の可能な各ストリームまたはシーケンスについて複数の枝の接続された経路を有する。この復号器は本質的には、トレリスを通じた経路であって、符号語の受信されたストリームに「最も近い」または最も似ているものを見出す。この「最も確からしい」トレリス経路上の符号語を受信された符号語として扱い、それらにデータ値を割り当てて送信されたデータの最良の推定を生成する。
【０００９】
最も確からしい経路を決定するため、復号器は受信された各符号語について、受信時に誤りを含んでいるかもしれない送信された符号語が実際にはある特定の枝に対応する符号語である確からしさの数値的な表現としての枝メトリックの組を計算する。そのような復号器では、枝メトリックは、受信された符号語とさまざまな枝に関連付けられた符号語との間のハミング距離である。
【００１０】
復号トレリス内の各枝は、その枝に関連付けられた符号語の形成に先立つレジスタの状態を表す初期状態から出て、その符号語の形成後のレジスタの状態を表す終状態にはいる。二値符号については、各復号レベルに関連付けられた2K-1個の可能な状態がある。ここで、Kは符号の拘束長である。たとえば、符号は拘束長3をもちうる。すなわち、2つのレジスタがある。よって、各復号レベルにおいて4つの可能なレジスタ状態、すなわち00、01、10、11がある。符号は符号化率1/nの符号である、すなわち二値符号でk＝1なので、各初期状態から出る二つの可能な枝がある。つまり、データ・ビット0に関連付けられた枝とデータ・ビット1に関連付けられた枝である。これらの枝のそれぞれは、必ず異なる終状態につながる。よって、所与の復号段における2K-1個の状態のそれぞれについて、これらの状態のそれぞれにつながる二つの枝があり、各枝が送信された符号語を表しうる。したがって、符号語を復号するためには、復号器は2K-1個の可能な終状態のそれぞれについて二つの枝メトリックを、あるいは全部で2(2K-1)個の枝メトリックを決定しなければならない。畳み込み符号については、2n個の一意的な枝計量の値しかない。
【００１１】
ひとたび復号器がこれらの枝メトリックを計算すると、復号器は次に諸終状態につながるさまざまな経路のメトリックを決定する。したがって、復号器は前記枝メトリックに適切な経路メトリックを加える。該経路メトリックは、現在の開始状態につながる枝の和である。復号器は次いで、終状態のそれぞれにつながる最も確からしい経路を選択し、該経路メトリックおよびこれらの最も確からしい経路を同定する情報をのちの使用のために記憶する。これらの最も確からしい経路は、「生き残り経路（surviving  paths）」とも称される。復号器はそれほど確からしくない経路、すなわち非生き残り経路に関する情報は保持しない。このようにして、復号器はこれらの経路をトレリスから「枝刈りし（prune）」、それにより復号の次のレベルのために、経路メトリック計算の一部をなくす。
【００１２】
十分な数の符号語が諸トレリス経路に含められたとき、終状態に関連付けられている生き残り経路から最も確からしい符号語経路が選ばれる。復号器は、受信データに「最も近い」符号語経路、すなわちハミング距離メトリックが最小の経路を最も確からしい経路として選択する。復号器は次いで、最も確からしい経路上の符号語を復号する、あるいはその経路に沿って「逆行トレースする」ことにより関連付けられた一連のデータ・ビットを決定する。
【００１３】
ビタビ・アルゴリズムは畳み込み符号を復号するために使われるのみならず、シンボル間干渉（ISI:  intersymbol  interference）のあるチャネルを通じての伝送されたシーケンスの最尤推定を生成し、トレリス符号化変調（TCM:  trellis-coded  modulation）およびメモリーをもつ他の変調をデコードするためにも使われる。ビタビ復号器は典型的には三つの機能部分に分割される。第一の部分は経路メトリックを計算するために使われる追加・比較・選択（ACS:  add-compare-select）ユニットである。第二の部分は生き残り経路メモリ管理のための生き残り経路メモリ制御（survivor  memory  control）ユニットである。生き残り経路メモリ（survivor  memory）は、ビタビ復号器の最後の部分として生き残りシーケンスを記憶しうる
連続位相変調（CPM:  continuous  phase  modulation）は、そのバンド幅効率および一定エンベロープ特性のため、通信において応用されている。CPMでは、変調信号位相遷移がなめらかにされる。たとえば、二状態位相偏移符号化（BPSK:  Binary  Phase-Shift  Keying）では、論理的な1は変調信号の一つの位相として送信され、論理的な0は位相の鋭い遷移（つまり瞬間的）をもって180度位相偏移されて送信される。この鋭い位相遷移は送信されるスペクトルの広帯域化につながる。CPMでは、送信される信号の位相は、変調するデジタル信号の諸ビットを通じてなめらかな位相変化をする。CPMの一例は最小偏移符号化（MSK:  Minimum  Shift  Keying）変調である。
【００１４】
多h型連続位相変調（multi-h  CPM）はそれ自身、変調された波形の幅広いクラスである。このクラスには、一定振幅だが位相が変化する信号が含まれる。多h型CPMは、単一h型とは、H個の変調指数を巡回的な仕方で使うことによって異なっている。これは、隣り合う位相のトレリス経路の遅延されたマージにつながり、最終的には改善されたエラー・パフォーマンスにつながる。多h型CPM波形の詳細な記述は非特許文献２の書籍に含まれている。
【先行技術文献】
【非特許文献】
【００１５】
【非特許文献１】ジョン・G・プロアキス（John  G.  Proakis）、「デジタル通信（Digital  Communications）」
【非特許文献２】アンダーソン、オーリン、サンドバーグ（Anderson,  Aulin  and  Sundberg）、『デジタル位相変調（Digital  Phase  Modulation）』、プリーナム・プレス（Plenum  Press）、ニューヨーク、1986年
【非特許文献３】スヴェンソン（Svensson）、「完全応答連続位相変調の削減状態数シーケンス検出（Reduced  State  Sequence  Detection  of  Full  Response  Continuous  Phase  Modulation）」、エレクトロニクス・レター（Electronics  Letter）、1990年5月10日、第26巻第10号
【非特許文献４】エユボグル（Eyuboglu）ら、「集合分割および判定帰還のある削減状態シーケンス推定（Reduced  State  Sequence  Estimation  With  Set  Partitioning  and  Decision  Feedback）」、IEEEトランザクションズ・オン・コミュニケーションズ（IEEE  Transactions  on  Communications）、1998年、第36巻第1号
【発明の概要】
【発明が解決しようとする課題】
【００１６】
スヴェンソン（非特許文献３）およびエユボグルら（非特許文献４）（およびその他）の論文によって記載されているように、いくつかの技術は標準的なMLSE（Maximum  Likelihood  Sequence  Estimator［最尤シーケンス推定器］）復号器の計算量を軽減する。たとえば、エユボグル論文では、線形シンボル間干渉（ISI）チャネル用の削減状態数シーケンス推定器が、通常のビタビ・アルゴリズム（VI）に、集合分割の原理を使って構築される削減状態数の（reduced-state）「部分集合トレリス」内で検索するために判定帰還をもたせたものを使う。チャネル・メモリの長さおよび信号集合の大きさに起因する最尤シーケンス推定（MLSE）の計算量は系統的に低下させられる。誤り確率解析は、良好なパフォーマンス／計算量の兼ね合いが得られることを示している。スヴェンソン論文では、削減状態数シーケンス検出器（RSSD:  reduced  state  sequence  detector）がM値（M-ary）完全応答（full  response）連続位相変調のために判定帰還をビタビ復号と組み合わせる。検出器は、最小ユークリッド距離をもって、シンボル誤り確率のシミュレーションによって解析される。M値完全応答CPM方式の復号は、変調指数が比較的小さい（＜1/M）ときは二状態のみの復号器によってでき、より大きな1より小さい変調指数についてはM個の状態でできる。削減状態数MLSE復号器のいくつかの変形があるが、同じ（低下された）計算量やモデム・ビット誤り率パフォーマンスは提供しない。
【００１７】
前方誤り訂正（FEC）および最尤復号器（ビタビ・アルゴリズム）の使用は、たいていの標準的な通信の教科書に記載されている。削減状態数シーケンス推定（RSSE:  reduced  state  sequence  estimation）は1980年代におけるMLSE復号器における重要な発展であった。開発者および製造業者ザイリンクス（XILINX）およびアルテラ（Altera）は、ユーザーに若干のプログラム可能ビタビ（MLSE）オプションを許容するFPGAおよびVHSICハードウェア記述言語（VHDL）ツールを生産する。これらは通例、軟判定メトリックを提供できる畳み込み符号として形成される。現行のツールはいずれも、削減状態数シーケンス推定のために要求される所望される判定帰還またはトレリス構造操作を提供しはしない。現行のツールはまた、CPM信号およびメモリーをもつ信号とともに使うためにプログラム可能ではない。また、業界においては、削減状態数の汎用かつプログラム可能な最尤復号器に対する必要性がある。
【課題を解決するための手段】
【００１８】
プログラム可能復号器は、複数のプログラム可能な削減状態数トレリス・パラメータのための少なくとも一つのプログラミング入力を含む。プログラム可能デバイスが前記少なくとも一つのプログラミング入力に接続され、前記複数のプログラム可能な削減状態数トレリス・パラメータに基づく少なくとも一つの削減状態数トレリス構造を有する削減状態数シーケンス推定（RSSE）復号器を実装する。
【００１９】
ある側面では、復号器はメモリーをもつおよび／または前方誤り訂正（FEC）符号を有する波形の復調をサポートするための復調器を含む。この復調器は、連続位相変調（CPM）、TCM、ISIチャネルなどの復調をサポートできる。削減状態数トレリス構造（reduced-state  trellis  structure）は、ウンガーベック（Ungerboeck）集合分割構造または二状態の（またはより大きな）スヴェンソン様構造として形成されることができる。
【００２０】
さらにもう一つの側面では、前記複数のプログラム可能な削減状態数トレリス・パラメータは、各トレリス内の超状態（super-states）の数；何らかの超状態を形成するために組み合わされた完全状態（full-states）の数；超状態当たりの枝の数；トレリス構造の数；超状態当たりの枝の数；逆超状態トレリス・テーブル；完全状態としての復号器超状態生き残り者（super-state  survivor）；前方完全状態テーブル；完全状態から超状態へのマッピング・テーブル；復号器超状態経路メトリックおよび復号器超状態逆行トレース配列のうちの少なくとも一つを含む。復号器は、経路メトリックおよび判定帰還のために使われる完全な復号器状態を含む復号器状態構造として形成されることができる。RSSE復号器は、任意の所与のビットについて判定帰還からのどの完全復号器状態が次の完全復号器状態に接続されるかを示すよう動作する前方トレリス構造として形成されることができる。前記プログラム可能デバイスも現場プログラム可能なゲートアレイ（FPGA）として形成される。前記少なくとも一つのトレリス構造は、少なくとも一つの逆状態トレリス構造として形成されることができる。
【００２１】
さらにもう一つの側面では、出力当たり複数ビットをもって復号されたビットを出力するために、少なくと一つの出力が前記プログラム可能デバイスに接続される。前記少なくとも一つの出力は、最良経路についてのすべての復号されたビットの完全な逆行トレースを出力するよう動作する。現在の最良経路についての勝ち残り状態（winning  state）を出力するために、少なくとも一つの出力が前記プログラム可能デバイスに接続されることができる。
【００２２】
方法側面も記載される。
【００２３】
本発明の他の目的、特徴および利点は、以下の本発明の詳細な記述を付属の図面に照らして参酌することから明白となるであろう。
【図面の簡単な説明】
【００２４】
【図１】本発明の一つの限定しない例に基づく、削減状態数トレリス構造の高レベルの図である。
【図２】本発明の一つの限定しない例に基づく、二状態削減状態数トレリス構造の高レベルの図である。
【図３】本発明に基づく復号器を含むことができるさまざまな無線機を含む通信システムの例のブロック図である。
【図４】本発明に基づいて削減状態数汎用プログラム可能最尤復号器として使うために修正されることができるプログラム可能トレリス復号器をトレリス復号器として含む受信機のブロック図である。
【図５】図４に示した削減状態数汎用プログラム可能トレリス復号器の、より詳細なブロック図である。
【図６】本発明の限定しない例に基づく、削減状態数汎用プログラム可能トレリス復号器を実装する方法における諸ステップを例解するフローチャートである。
【図７】シンボル当たり16サンプルのための位相パルス形状を示すグラフである。
【図８】h＝1/4二値（binary）CPFSKにおける８つの状態をもつ完全状態トレリス構造を示すブロック図である。
【図９】h＝1/4  CPFSK配位図（constellation）を示すブロック図である。
【図１０】MIL-STD-188-181C、H=(4/16,  5/16)４値（4-ary）CPFSKの、集合分割削減状態数モデルとのBER比較を示すグラフである。
【図１１】四状態トレリス構造を示す図である。
【図１２】MIL-STD-188-181C、H=(4/16,  5/16)４値（4-ary）CPFSKの、傾斜位相削減状態数モデルとのBER比較を示すグラフである。
【図１３】ハイブリッドAMパルス・スペクトルを示すグラフである。
【図１４】ハイブリッド位相パルス・スペクトルを示すグラフである。
【図１５】AMパルス形状パフォーマンスを示すグラフである。
【図１６】PMパルス形状パフォーマンスを示すグラフである。
【図１７】本発明の限定しない例に基づく、削減状態のh＝1/3型の振幅整形された（amplitude  shaped）HCPMのビット誤り率を示すグラフである。
【図１８】本発明の限定しない例に基づく、削減状態のh＝1/3型の位相整形された（phase  shaped）HCPMのビット誤り率を示すグラフである。
【発明を実施するための形態】
【００２５】
ここで、種々の実施形態について以下に、好ましい実施形態を示す付属の図面を参照しつつ、より十全に記載する。多くの異なる形が述べられることがあるが、本願に記載される実施形態は本稿で述べられる実施形態に限定されると解釈されるべきではない。むしろ、これらの実施形態は、この開示が十全となり、当業者に本発明の範囲を十全に伝達するよう提供されるものである。全体を通じて同様の番号は同様の要素を指す。
【００２６】
本発明の限定しない例に基づくシステムおよび方法は、削減状態数シーケンス推定（RSSE）汎用プログラム可能復号器であって、各トレリス内の超状態の数についての入力プログラム可能性をもつものを提供する。完全状態は組み合わされて超状態を形成する。超状態当たりいくつかの枝があり、いくつかのトレリス構造がある。複数のプログラム可能な超状態トレリス・パラメータは好ましくは、諸トレリス段についてのトレリス接続性情報、各トレリス段についての有効および無効超状態、トレリス枝遷移データ値およびトレリス枝遷移についてのメトリック指数を含み、トレリス構造の数、各トレリス構造についてのトレリス超状態の数および各トレリス超状態についての枝の数を含んでいてもよい。逆状態トレリス構造（reverse  state  trellis  structure）は、各超状態を以前の超状態のリストと接続する。復号器超状態構造は、経路メトリックおよび判定帰還のために使われる「勝ち残り（winning）」完全状態を含む。順状態トレリス（forward  state  trellis）は、判定帰還からのどの完全状態が次の完全状態に接続されるかを任意の所与のビットについて定義できる。復号器の出力は、出力当たり複数ビットの復号されたビットと、その経路についてのすべての復号されたビットの完全な逆行トレースとを含む。最良経路メトリックと最悪の経路メトリックの間の差が提供されることができ、「勝ち残り」状態が現在の最良経路のために選ばれることができる。また、トレリス構造は逆状態トレリス構造および／または順状態トレリス構造を含みうる。
【００２７】
いくつかの既存の通信装置は限られたプログラム・スペース、CPU計算速度およびバッテリー・パワーをもつ。これらの要件を満たすため、本発明の限定しない諸例に基づくソフトウェア・ベースまたはFPGAベースの削減状態数最尤復号器は、メモリーをもつ波形の復調をサポートする。該復号器はまたプログラム可能であり、連続位相変調（CPM）の復調およびたいていのFECトレリス符号の復号をサポートする。本発明の限定しない諸例に基づく削減状態数復号器は、次のことを含む限定しない特徴のため、大半の標準的なトレリス復号器とは変わっている：
１）「勝ち残り」経路メトリックを維持することに加えて、復号器状態テーブルが「勝ち残り完全状態」メモリを有すること；
２）本復号器は、復号器における各完全状態がどのように次の完全状態に接続されるかを示す前方トレリス構造（forward  trellis  structure）（リンクされたリスト）を有する。
【００２８】
削減状態数復号器（reduced  state  decoder）は多くの刊行物に記載されているが、限定しない例に基づく本復号器は、復号器状態テーブルおよびトレリス構造の設計についての「フリーサイズ」アプローチを含む。単一の実装されたFPGA/DSP（デジタル信号プロセッサ）アーキテクチャが、大半のトレリス符号またはメモリー・ベースの（すなわちCPM）変調方式を復号できる。
【００２９】
削減状態数ビタビ検出器は、ハードウェアの複雑さが低下しており、削減状態数トレリスを使う。いくつかの限定しない例では、検出器は、短縮されたインパルス応答を考慮し、過去の生き残りシンボルを使うことによって各状態についてのインパルス応答のテールに起因するシンボル間干渉を打ち消すことができる。あるRSSEアルゴリズムでは、状態数の削減は、状態ベクトル中の各要素を所与の数の部分集合に分割し、部分集合ベクトルを削減状態数トレリスとして表すことによってできる。削減状態は、ビタビ・アルゴリズムを介して最尤シーケンス推定（MLSE）法に従ってインパルス応答データが推定されるよう、ウンガーベックの集合分割の原理に基づいて、なされることができる。送信シーケンスは、可能なデータ・シーケンスのうちから、受信されたシーケンスおよび伝送システムの推定されたインパルス応答を考慮に入れて推定されることができる。RSSEは、チャネル・メモリを打ち切るまたは信号アルファベットに集合分割を適用することによって、MLSEの複雑さを低下させることができる。RSSEアルゴリズムは、削減されたトレリスにおける最も確からしいデータ・シーケンスを、各削減状態について最良の生き残りまたは勝ち残り経路のみを保持することによって、検索できる。いくつかの状態はマージされることができ、それによりMLSEの複雑さが低下する。削減状態数トレリスにおける各超状態は、ウンガーベックの集合分割の原理を使ってもとの最尤トレリスの状態を組み合わせることによって形成されることができる。二値伝送が使われるとき、RSSEアルゴリズムは、削減状態数トレリスにおける各超状態が最尤状態ベクトルを好適な長さで打ち切ることによって形成される、状態打ち切り技法となることができる。
【００３０】
上記したように、h＝1/4（８状態）連続位相周波数偏移符号化（CPFSK:  Continuous  Phase  Frequency  Shift  Keying）変調のためのウンガーベック様（集合分割）削減状態数トレリス構造が図１に示されている。完全状態のラベルは角括弧内に記されており、新しい超状態のラベルは角括弧内の各対の上に挙げられている。この削減状態数トレリス構造は、ビット誤り率（BER:  Bit  Error  Rate）パフォーマンスの低下は全くなく、もとのトレリス構造の半分の複雑さである。
【００３１】
二値h＝1/4  CPFSK変調についてのスヴェンソン様（二状態）アプローチが図２に示されている。これは任意の（h値の）CPFSK変調について使われるのと同様のトレリス構造をもち、トレリスの複雑さを４分の１にする（h＝1/4について）。参照によって組み込まれたスヴェンソン論文において定義されるような最尤シーケンス推定器は二つの状態のみをもち（二値完全応答CPMについて）、そのトレリス構造が図２に示されている。
【００３２】
図示されるように、値が1のビットは状態遷移を引き起こし、値が0のビットは引き起こさない。これはほとんど困難なく実装でき、任意の単一h型二値CPFSK変調に適応できる。集合分割アプローチの場合と同様、二つの超状態のそれぞれの勝ち残り位相状態を維持するために、判定帰還が使われる。復号器は、選ばれた勝ち残り位相から二つの有効な経路について経路メトリックを計算し、新しい勝ち残り経路メトリックを選び出す。新しい勝ち残り経路メトリックは次いで、当該シンボルの間に採られた枝に基づいて超状態に保存される。枝が値が0のビットに対応する場合、新しい超状態は古い超状態と同じである。しかしながら、遷移が値が1のビットに対応するならば、経路メトリックは他方の超状態に遷移する。
【００３３】
ここで図３〜図６を参照し、本発明とともに用いられる復号器をもつさまざまな無線機を含むことができる通信システムの例をこれから図３に関連して記載する。削減状態数の汎用かつプログラム可能なトレリス復号器の高レベルの記述（図４および図５）ならびに復号器を説明するフローチャート（図６）がそれに続く。
【００３４】
本発明の限定しない例に基づくそのようなシステムおよび方法とともに使われることができる無線機の例が、米国フロリダ州メルバーンのハリス・コーポレイションによって製造・販売されるファルコン（Falcon（商標））III無線機である。典型的には比較的標準的なプロセッサおよびハードウェア・コンポーネントを用いて実装されることができるソフトウェア定義された無線機およびメッシュ・ネットワーク無線機を含め、異なる無線機が使われることができることは理解しておくべきである。ソフトウェア無線機の一つの個別的なクラスは、統合戦術無線機（JTR:  Joint  Tactical  Radio）である。これは比較的標準的な無線機および処理ハードウェアを、無線機が使う通信波形を実装するための任意の適切な波形ソフトウェアとともに含む。JTR無線機はまた、ソフトウェア通信アーキテクチャ（SCA:  software  communications  architecture）規格（www.jtrs.saalt.mil参照）に準拠するオペレーティング・システム・ソフトウェアも使用する。この規格は、ここに参照によりその全体において組み込まれる。SCAは、ハードウェア・コンポーネントおよびソフトウェア・コンポーネントがどのように相互動作するかを規定し、それにより異なる製造業者および開発者がそれぞれのコンポーネントを単一の装置に容易に統合できるようにするオープン・アーキテクチャの枠組みである。
【００３５】
統合戦術無線システム（JTRS:  Joint  Tactical  Radio  System）ソフトウェア・コンポーネント・アーキテクチャ（SCA）は、ソフトウェア定義無線機（SDR:  Software  Defined  Radio）を実装するための一組のインターフェースおよびプロトコルを、しばしば共通オブジェクト要求仲介アーキテクチャ（CORBA:  Common  Object  Request  Broker  Architecture）に基づいて定義する。部分的には、JTRSおよびそのSCAは、ソフトウェア再プログラム可能な無線機の族とともに用いられる。よって、SCAは、ソフトウェア再プログラム可能なデジタル無線機を実装するための規則、方法および設計の基準の特定の集合である。
【００３６】
JTRS  SCA規格は、JTRS統合プログラム庁（JPO:  Joint  Program  Office）によって刊行されている。JTRS  SCAは、異なるJTRS  SCA実装の間でのアプリケーション・ソフトウェアの移植性を提供し、商用規格にてこ入れして開発コストを下げ、設計モジュールの再利用可能性を通じて新しい波形の開発時間を短縮し、進化する商用の枠組みおよびアーキテクチャを土台とするよう構築された。
【００３７】
JTRS  SCAは、実装に依存しないように意図されているので、システム仕様ではなく、所望されるJTRS目的を達成するためにシステムの設計を制約する規則の集合である。JTRS  SCAのソフトウェア枠組みは、オペレーティング環境（OE:  Operating  Environment）を定義し、その環境から諸アプリケーションが用いるサービスおよびインターフェースを規定する。SCA  OEは、コア枠組み（CF:  Core  Framework）、CORBAミドルウェアおよび関連するボード・サポート・パッケージをもつポータブル・オペレーティング・システム・インターフェース（POSIX:  Portable  Operating  System  Interface）に基づくオペレーティング・システム（OS:  Operating  System）を有する。JTRS  SCAはまた、アプリケーション・ソフトウェア・コンポーネント間のアプリケーション・プログラミング・インターフェース（API:  application  programming  interfaces）を定義する構成ブロック構造（API補遺にて定義されている）をも提供する。
【００３８】
JTRS  SCAコア枠組み（CF）は、組み込み型分散コンピューティング通信システムにおいてソフトウェア・アプリケーション・コンポーネントの展開、管理、相互接続および相互通信を提供するオープン・ソフトウェアのインターフェースおよびプロファイルからなる本質的かつ「コア」となるセットを定義するアーキテクチャ概念である。インターフェースは、JTRS  SCA規格において定義されてよい。しかしながら、インターフェースのいくつかは開発者が実装してもよいし、いくつかはコアでないアプリケーションによって実装されてもよいし（すなわち波形など）、いくつかはハードウェア装置提供者によって実装されてもよい。
【００３９】
説明のみの目的で、本発明から裨益するであろう通信システムの一例の簡単な記述が、図３に示される限定しない例との関連で記載される。通信システム５０のこの高レベルのブロック図は、基地局セグメント５２と、本発明での使用のために修正されうる無線メッセージ端末とを含む。基地局セグメント５２は、無線リンクを通じて音声またはデータをVHFネット６４またはHFネット６６に通信および送信するVHF無線機６０およびHF無線機６２を含み、VHFネット６４またはHFネット６６はそれぞれいくつかのVHF無線機６８およびHF無線機７０と、該無線機６８、７０に接続されたパーソナル・コンピュータまたはワークステーション７２とを含む。アドホック通信ネットワーク７３は、図示されるようなさまざまな構成要素と相互動作する。このように、HFネットワークまたはVHFネットワークにはインフラストラクチャーがなく、アドホック通信ネットワークとして動作するHFネット・セグメントおよびVHFネット・セグメントを含むことを理解しておくべきである。図示していないが、UHF無線機およびUFHネット・セグメントも含まれてもよい。
【００４０】
HF無線機は、復調器回路６２ａおよび適切な畳み込みエンコーダ回路６２ｂと、ブロック・インターリーブ器６２ｃと、データ・ランダム化回路６２ｄと、データおよびフレーミング回路６２ｅと、変調回路６２ｆと、整合フィルタ回路６２ｇと、適切なクランピング装置をもつブロックもしくはシンボル等化器回路６２ｈと、インターリーブ解除および復号回路６２ｉと、モデム６２ｊと、電力適応回路６２ｋとを、限定しない例として含むことができる。ボコーダ回路６２ｌは、復号機能およびエンコード機能ならびに変換ユニットを組み込むことができ、それは、記載されるようにさまざまな回路の組み合わせであっても、別個の回路であってもよい。これらおよび他の回路は、本発明のために必要な任意の機能ならびに当業者によって提案される他の機能を実行するよう動作する。すべてのVHF移動無線機ならびに送信局および受信局を含む他の例示される無線機が同様の機能回路をもつことができる。
【００４１】
基地局セグメント５２は、公衆電話交換網（PSTN:  public  switched  telephone  network）８０への陸線接続を含み、PSTN８０は、PABX８２に接続する。衛星地上局のような衛星インターフェース８４は、PABX８２に接続し、PABX８２は、無線ゲートウェイ８６ａ、８６ｂを形成するプロセッサに接続する。これらの無線ゲートウェイは、それぞれVHF無線機６０またはHF無線機６２に相互接続する。前記プロセッサは、ローカル・エリア・ネットワークを通じてPABX８２および電子メール・クライアント９０に接続される。無線機は、適切な信号発生器および変調器を含む。
【００４２】
イーサネット（登録商標）／TCP-IPのローカル・エリア・ネットワークは、「無線」メール・サーバーとして動作できる。電子メール・メッセージは、第二世代のプロトコル／波形としてのSTANAG-5066を使って、無線リンクおよびローカル・エア・ネットワークを通じて送られることができる。STANAG-5066の開示は、参照によりここにその全体において組み込まれる。もちろん、好ましくは、電子メール・メッセージは、第三世代の相互運用性標準であるSTANAG-4538を用いて送られることができる。STANAG-4538の開示は、参照によりここにその全体において組み込まれる。相互運用性標準FED-STD-1052は、従来式の無線装置とともに使用でき、その開示は、参照によりここにその全体において組み込まれる。本発明で使用できる機器の例は、限定しない例として、米国フロリダ州メルバーンのハリス・コーポレイションによって製造される種々の無線ゲートウェイおよび無線機を含む。こうした機器は、RF5800、5022、7210、5710、5285ならびにPRC117および138シリーズの機器および装置を含むことができる。
【００４３】
これらのシステムは、RF-5710A高周波（HF）モデムおよびSTANAG4539として知られるNATO標準とともに動作可能でありうる。STANAG4539は、長距離HF無線機回路の最高9600bpsまでのレートでの伝送を提供するものであり、その開示は、参照によりここにその全体において組み込まれる。モデム技術に加え、それらのシステムは、STANAG4538またはSTANAG5066のような負荷のかかった戦術チャネル用に設計、完成された一組のデータ・リンク・プロトコルを使う無線電子メール製品を使うことができる。STANAG4538およびSTANAG5066の開示は、参照によりここにその全体において組み込まれる。また、無線機をISBモードに設定し、HFモデムを固定データ速度に設定して、19200bpsほど高い固定の非適応データ速度を使うことも可能である。符号合成（code  combining）技術および自動反復要求（ARQ:  Automatic  Repeat  Request）を使うことも可能である。
【００４４】
以下は、本発明の限定しない例に基づく、削減状態数の汎用かつプログラム可能なトレリス復号器の記述である。まず図４および図５を参照すると、削減状態汎用プログラム可能トレリス復号器１３０を含む、UHF衛星通信受信機のようなデータ通信受信機１１０のある実施形態が記載される。通信チャネル１１２を通じて送られるエンコードされ変調された信号が受信機１１０によって受信される。これらの変調された信号は、CPM、ISIチャネルまたはトレリス符号化変調（TCM）のようなメモリーをもついかなる信号であることもできる。復調器１２０がはいってくる信号を処理し、ベースバンドの復調された信号をプログラム可能トレリス復号器１３０に送る。プログラム可能トレリス復号器１３０は信号を処理し、次いで復号されたデータおよび他の関係する情報をチャネル１１４を通じて宛先に送る。受信機の構成要素、たとえば復調器１２０およびプログラム可能トレリス復号器１３０は、プロセッサ１５０によって制御される。
【００４５】
削減状態汎用プログラム可能トレリス復号器１３０は、先に説明したRSSEアルゴリズムおよび方法論を使い、複数のプログラム可能トレリス・パラメータのための少なくとも一つのプログラミング入力１３４、１３６を含む。本発明の限定しない例に基づく削減状態復号器は、復号器状態テーブルが「勝ち残り」経路メトリックを維持することに加えて「勝ち残り完全状態メモリ」を有するので、標準的なトレリス復号器からは変わっていることを理解しておくべきである。デコーダは、デコーダ中の各完全状態が次の完全状態にどのように接続されるかを示すリンクされたリストとして前方トレリス構造をもつ。こうして、単一の実装される現場プログラム可能なゲートアレイおよびデジタル信号処理アーキテクチャが、いかなるトレリス符号、ISIチャネルまたはメモリー・ベースの変調すなわちCPMをも復号できる。
【００４６】
削減状態数シーケンス推定プログラム可能復号器は入力のプログラム可能性をもつことができる。プログラム可能性は、各トレリス段における超状態の数、トレリス段の数およびどの完全状態が組み合わされて超状態を形成するかを含む。それはまた、超状態当たりの枝の数、トレリス構造の数、各超状態を以前の超状態のリストと接続する逆状態トレリス構造、各トレリス段についての有効および無効状態、トレリス枝遷移データ値およびトレリス枝遷移についてのメトリック指数をも含むことができる。復号器超状態構造は、経路メトリックと、判定帰還のために使用される「勝ち残り」完全状態とを含むことができる。順状態トレリスは、任意の所与のビットについて判定帰還からのどの完全状態（すなわち生き残り経路）が次の完全状態に接続されるかを定義できる。
【００４７】
復号器の出力は、出力当たり複数ビットで復号されたビットを含むことができる。その経路についてのすべての復号されたビットの完全な逆行トレースが含められることができる。出力は、最良経路と最悪経路との間の差および現在の最良経路についての「勝ち残り」状態を含むことができる。
【００４８】
復号器は、トレリス符号化されたビットのシーケンスを受信し、トレリス状態図の各枝に関連付けられた枝メトリックに基づいて経路メトリックおよび出力シーケンスを計算する追加・比較・選択（ACS）ユニットと、前記出力シーケンスを記憶する生き残りメモリと、生き残りメモリを制御して、記憶された出力シーケンスの復号されたビットを出力する生き残りメモリ制御ユニットとを含むことができる。このことは当業者には認識されるであろう。
【００４９】
プログラム可能デバイス１３２がプログラミング入力に接続され、複数のプログラム可能なトレリス・パラメータに基づいて定義される少なくとも一つのトレリス構造をもつプログラム可能トレリス復号器（たとえば、連続位相変調（CPM）復号器）を実装する。プログラム可能デバイス１３２は、たとえば現場プログラム可能なゲートアレイ（FPGA）であってもよい。
【００５０】
FPGAは、プログラム可能な論理コンポーネントおよびプログラム可能な相互接続を含む半導体デバイスである。プログラム可能な論理コンポーネントは、基本論理ゲート（AND、OR、XOR、NOTのような）または復号器もしくは簡単な数学機能といったより複雑な組み合わせ機能の機能性を複製するようプログラムされることができる。たいていのFPGAでは、これらのプログラム可能論理コンポーネント（または論理ブロック）は、メモリ要素をも含む。メモリ要素は単純なフリップフロップでもより複雑なメモリのブロックでもよい。
【００５１】
プログラム可能な相互接続の階層構造により、FPGAの論理ブロックが必要に応じてシステム設計者によって相互接続されることが許容される。ワンチップのプログラム可能ブレッドボードに似ていなくもない。これらの論理ブロックおよび相互接続は、製造工程後に顧客／設計者によってプログラムされることができ（すなわち「現場プログラム可能（field-programmable）」）、それによりFPGAは必要とされるどんな論理機能でも実行できる。
【００５２】
しかしながら、FPGAは一般に、対応する特定用途向け集積回路（ASIC）より遅く、それほど複雑な設計を扱えず、より多くの電力を消費する。しかしながら、市場投入までの時間が短い、バグを直すために現場で再プログラム可能、非反復エンジニアリングのコストが低くなるといったいくつかの利点がある。もう一つの代替は、複合プログラム可能論理デバイス（CPLD:  complex  programmable  logic  device）である。
【００５３】
FPGAの振る舞いを定義するため、ユーザーは、いくつかの限定しない例では、ハードウェア記述言語（HDL）または概略的設計（schematic  design）を提供してもよい。一般的なHDLはVHDLおよびVerilogである。次いで、電子設計自動化ツールを使って、技術マッピングされたネットリスト（technology-mapped  netlist）が生成される。そのネットリストは次いで、通例配置配線ソフトウェアによって実行される配置配線（place-and-route）と呼ばれるプロセスを使って実際のFPGAアーキテクチャにあてはめられる。ユーザーはマップ、配置配線結果をタイミング解析、シミュレーションまたは他の検証方法を介して有効確認できる。ひとたび設計および有効確認プロセスが完了すると、生成されたバイナリー・ファイルがFPGAデバイスを構成し直すために使用されることができる。そのようなバイナリー・ファイルは、制御入力ブロック１３４を介してプログラム可能デバイス１３２に記憶され、および／または入力されてもよい。
【００５４】
限定しない例として、プログラム可能トレリス復号器１３０は、CPMを、好ましくは多h型CPMを実装してもよい。CPMでは、送信される信号の位相が、変調するデジタル信号の諸ビットにわたってなめらかな位相変化をする。CPMの一例は最小偏移符号化（MSK:  minimum  shift  keying）である。多h型連続位相変調（多h型CPM）はそれ自身、変調される波形の幅広いクラスである。そのクラスには一定振幅だが変化する位相の信号が含まれる。多h型CPMは、単一h型とは、H個の変調インデックスを巡回的な仕方で使うことによって異なっている。これは、隣接位相トレリス経路の遅延されたマージにつながり、最終的には改善されたエラー・パフォーマンスにつながる。
【００５５】
プログラム可能デバイス１３２の一つまたは複数の出力１３８、１４０、１４２は、出力当たり複数ビットでの復号されたビットならびに最良経路についてのすべての復号されたビットの完全な逆行トレースを出力するため、最良経路メトリックと最悪経路メトリックとの間の差を出力するため、および／または現在の最良経路についての勝ち残り状態を出力するために、設けられる。
【００５６】
削減状態汎用プログラム可能トレリス復号器１３０は、上述したトレリス方式すべてを扱うために、復号器における適切な構造および柔軟性を提供する。トレリス段当たりの有効および無効状態は、状態間のデルタ増分および／または有効／無効フラグをもつことによってなすことができる。有効／無効は、現在と次の有効状態との間に良好なデルタ増分がない場合がありうるので、柔軟性を提供する。追加的な計算を回避するために各トレリス段についての異なる開始状態が提供されてもよいが、ここでも有効／無効状態が機能する。枝メトリックとして使用されるべきメトリックは、要求されるトレリス段、ノード識別および枝接続に基づいて、ユーザーによって提供される。計算する必要があるのは有効な超状態についてのメトリックのみである。追加／比較／選択点における逆ルックアップ・テーブルを介して、各トレリス段について、枝接続の異なる組が含められる。
【００５７】
ノード0についての例（トレリスが16個の状態をもつなら、各トレリス段について16個の状態があることになる）。反復構造は4トレリス段の長さであってもよく、各段について有効および無効段ならびに逆ルックアップ・テーブルがある。この型の構造は、多h型CPMについて要求されるが、この同じ構造が、単にトレリス逆ルックアップ・テーブルの接続性および有効／無効状態の選択を変更することによって、それほど複雑でないトレリス方式について使用されることもできる。このように、本アプローチは、現在利用可能な単純な畳み込み／TCM復号器よりずっと多くのトレリス方式を扱うことができる汎用（generic）トレリス復号器につながる。
【００５８】
一例として、多h型CPM波形が汎用プログラム可能トレリス復号器１３０を用いて復号されうる。多h型（multi-h）とは、各CPMシンボルについての異なる変調指数hを含意する。2hの場合、シンボル一つおきに変化する二つの異なるhの値がある。たとえば、h0＝4/16、h1＝5/16の二値CPMである。偶数番号シンボルは変調指数h0を使い、奇数番号シンボルは変調指数h1を使う。h0＝4/16について、トレリス逆行接続性は次のようになる（データ0＝負の周波数（すなわちデータ＝−1）；データ1＝正の周波数）。
【００５９】
書式：状態番号：前のデータ＝0  前のデータ＝1
状態0:    4    28
状態1:    5    29
状態2:    6    30
状態3:    7    31
状態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:    16    8
状態13:    17    9
状態14:    18    10
状態15:    19    11
状態16:    20    12
状態17:    21    13
状態18:    22    14
状態19:    23    15
状態20:    24    16
状態21:    25    17
状態22:    26    18
状態23:    27    19
状態24:    28    20
状態25:    29    21
状態26:    30    22
状態27:    31    23
状態28:    0    24
状態29:    1    25
状態30:    2    26
状態31:    3    27。
【００６０】
h1＝5/16については、トレリス逆行接続性は次のようになる。
【００６１】
状態0:    5    27
状態1:    6    28
状態2:    7    29
状態3:    8    30
状態4:    9    31
状態5:    10    0
状態6:    11    1
状態7:    12    2
状態8:    13    3
状態9:    14    4
状態10:    15    5
状態11:    16    6
状態12:    17    7
状態13:    18    8
状態14:    19    9
状態15:    20    10
状態16:    21    11
状態17:    22    12
状態18:    23    13
状態19:    24    14
状態20:    25    15
状態21:    26    16
状態22:    27    17
状態23:    28    18
状態24:    29    19
状態25:    30    20
状態26:    31    21
状態27:    0    22
状態28:    1    23
状態29:    2    24
状態30:    3    25
状態31:    4    26。
【００６２】
シンボル（段）1,2,…,8についてトレリス構造を解析すると：
書式：H#    開始状態  デルタ状態
段1  H0    0    2
段2  H1    1    2
段3  H0    1    2
段4  H1    0    2
段5  H0    0    2
段6  H1    1    2
段7  H0    1    2
段8  H1    0    2
段１を復号するには、状態0で始まり、次の状態のために状態を2だけインクリメントする（すなわち、偶数状態のみが有効である）。段２については、奇数状態のみを復号する。段３については奇数状態のみを復号し、段４については偶数状態のみを復号し、その後はパターンが繰り返される。
【００６３】
これが、汎用プログラム可能トレリス復号器１３０が有効状態および無効状態（たいていの一般的な場合について）または開始状態およびデルタ状態（代替的な実施例として）をもつ能力を提供する理由である。また、CPMを適正に復号するためには逆行トレリス構造が必要とされる。
【００６４】
よって、波形の復調における使用に先立つ、汎用プログラム可能トレリス復号器１３０の初期化プロセスについてここでまとめておく。トレリス構造は：段N；トレリス接続性；有効／無効状態；遷移を引き起こすデータ値（すなわち枝遷移データ値）；および所与のトレリス枝遷移についてのメトリック指数を含む。
【００６５】
まず、有効／無効状態および接続性を決定するためにトレリス構造（たとえばCPMまたはその他についての）が解析される。接続性情報は、パターンが繰り返す前に必要なだけ多くのトレリス段（典型的には畳み込み符号については一段だけ、1hCPMについては二段、上記の2hCPMの例については四段）について、復号器に書き込まれる。有効／無効状態（または開始状態およびデルタ状態）はトレリス復号器の各トレリス段について（パターンが繰り返すまで）書き込まれる。トレリス枝遷移を引き起こすデータ値はトレリス復号器構造に書き込まれる。トレリス枝遷移について使用されるメトリック指数がトレリス復号器に書き込まれる。
【００６６】
例：トレリス枝構造段0。逆行トレリス構造は次のものを含む：状態4から0のビットを介して状態0に、枝メトリック指数0を使う；状態12から1のビットを介して状態0に、枝メトリック指数1を使う；状態5から0のビットを介して状態1に、枝メトリック指数2を使う；状態13から1のビットを介して状態1に、枝メトリック指数3を使う、等。
【００６７】
データ復調の開始：枝メトリック配列がトレリス復号器に書き込まれる（これはメトリック指数を使う復号器によって使用されることになる）；追加／比較／選択機能が各有効状態について実行される；トレースバック機能が実行されて復号された情報を抽出する；ユーザーに出力データが提供される。
【００６８】
本発明の方法側面は、削減状態汎用プログラム可能トレリス復号器１３０（連続位相変調（CPM）復号器のような）を実装する方法に向けられるもので、図６のフローチャートを参照して論じていく。本方法はブロック２００で始まり、ブロック２０２において、プログラム可能トレリス復号器１３０を実装するためのプログラム可能デバイス１３２（FPGAのような）を用意することを含み、複数のプログラム可能なトレリス・パラメータに基づいて定義される少なくとも一つのトレリス構造を含む。本方法はさらに、少なくとも一つのプログラム可能入力を介して前記複数のプログラム可能なトレリス・パラメータをプログラムすることを含む（ブロック２０４）。
【００６９】
上で論じたように、前記複数のプログラム可能なトレリス・パラメータをプログラミングすることは、トレリス構造の数をプログラムすること、各トレリス構造についてのトレリス状態の数をプログラムすることおよび各トレリス状態についての枝の数をプログラムすることを含んでもよい。本方法は、ブロック２０６において、プログラム可能デバイス１３２に接続された、出力当たり複数ビットで復号されたビットを出力するための少なくとも一つの出力において、最良経路についてのすべての復号されたビットの完全なトレースバック、最良経路メトリックと最悪経路メトリックとの間の差および／または現在の最良経路についての勝ち残り状態を与える。
【００７０】
さまざまな要件を満たすため、FPGAベースの最尤復号器であって、削減状態数であり、プログラム可能であり、CPM、TCMおよび任意のFECトレリス符号の復調をサポートするものが設計されている。それは二値h（binary-h）、４値（4-ary）のCPMをサポートするよう設計された。
【００７１】
以下では、削減状態数復号器および動作の理論を述べる。
【００７２】
MIL-STD-188-181C衛星通信規格において定義される連続位相変調（CPM）波形は32状態のトレリス構造をもつ。この信号を復調するために使われる最尤シーケンス推定器の計算量は、CPM信号が二つの変調指数（h値）をもち、そのため復号器は各h値について一組で二組の経路メトリックを記憶することを要求されるため、さらに増加される。UHF衛星通信規格によって要求される信号対雑音比の値についての復調パフォーマンスを有意に低下させることなくCPM信号のトレリス構造の計算量を低下させるアプローチが取られる。先述したように、第一の状態数削減方法はウンガーベック様の集合分割を使う。別のアプローチは、完全に異なる４状態のトレリス構造であって、CPM変調の微分特性（differential  properties）を利用する枝遷移が定義されたものを利用する。
【００７３】
連続位相変調は、次の時間領域表現をもつ一定エンベロープ変調である：
【００７４】
【数１】
2010517373.tif 000003
ここで、Tはシンボル期間、Eはシンボル当たりのエネルギー、fは搬送波周波数、aはデータ・シンボル、hは変調指数、qは位相パルス形状である。
【００７５】
UHF  SATCOM規格は、完全応答、四元多h型CPM変調方式の、受信計算量および送信周波数スペクトルを制御するためのシンボル・レートおよび変調指数（h値）が異なる（最高）12個の異なる変形を提供する。それらの変形のすべては32個の位相状態を与える。ここで、任意の所与のシンボル期間においては、状態のうち半分だけが有効である。すべての場合において、比p/qとして定義された二つのh値がある。ここで、qは常に16であり、pは偶数値と奇数値との間で交替する。
【００７６】
状態数および対応する受信機計算量を削減するための二つの文書化された方法がある。第一の方法は、エユボグルによって記載されたもので、ユークリッド距離をメトリックとして使って状態を組み合わせる（集合分割）。第二の方法は、スヴェンソンによって記載されたもので、CPM復調に対して傾斜位相（tilted-phase）アプローチを使う。これはトレリス内の無効な状態を自動的に消去する。スヴェンソンはさらに、トレリス内の各枝の差分位相（differential  phase）に基づいて状態を削減する。
【００７７】
集合分割アプローチの例解として、h＝1/4の二元CPFSK（1REC  CPM）トレリス構造が図８に描かれている。
【００７８】
h＝1/4CPFSK変調は８個の完全状態をもつ。位相位置に各状態でラベル付けして位相配位図を描くと（図９）、完全状態０と４、１と５、２と６ならびに３と７を組み合わせることによって超状態を生成するトレリス構造が、削減状態数トレリスのための最良の距離を与えることが明白になる。
【００７９】
このCPMトレリス構造はすでに二つの特殊な属性をもつ。第一は、最初の開始状態が０状態であるとの想定のもと、各シンボルにおいて、有効な開始状態が奇数または偶数のいずれかでなければならないということである。これは、送信器において、位相値0度で送信を開始することによって達成される。この完全状態トレリスの第二の属性は、復号器が、一つおきのシンボルの復号において、奇数または偶数状態についての経路メトリックの計算をスキップできるということである。こうして、最適なCPM復号器はすでに、各復号器サイクルの間に状態の半分について経路メトリックを計算（更新）するのみという点まで「削減」されている。
【００８０】
再び図１を参照すると、削減状態数トレリス構造が示されている。完全状態のラベルは角括弧内に記されており、新しい超状態のラベルは角括弧内の各対の上に挙げられている。
【００８１】
削減状態数トレリスを構築するとき、各完全状態はもとのトレリスにおいてそうであったのと同じように接続されたままである。この特定のトレリスについて、各シンボル復号サイクルにおいて開始状態を交替させる特性属性は、復号器の重要なパラメータのままである。復号サイクルとは、入力シンボルから枝メトリックの完全状態を計算し、トレリス構造内の有効状態すべてについて経路メトリックを更新することとして定義される。
【００８２】
削減状態数シーケンス検出のために要求されるもう一つの向上は、復号器における判定帰還段階である。経路メトリックおよびトレースバック・ビットとともに、復号器は各超状態における勝ち残り完全状態を保持するべきである。最初は復号器は超状態0から始まると想定されるので、復号器状態も開始完全状態は0であり、4ではないと想定する。一般に、経路メトリックを適正に初期化することによって、復号器超状態は、削減された状態（reduced  states）（すなわち0、1、2および3）のそれぞれについてリスト内の最初の完全状態に初期化されることができる。
【００８３】
復号器が超状態1について経路メトリックを計算するとき、0から1への遷移を（対応する計算された枝メトリックを使って）状態2から状態1への遷移についてのメトリックと比較する。次いで復号器は完全状態の値1を次の復号器サイクルのための勝ち残り状態として保存する（換言すれば、生き残り経路の位相を保持する）。この復号器サイクルにおいて計算される次の超状態は7である（偶数の無効の超状態は飛ばす）。ここでもまた、0が初期復号器サイクルからの勝ち残り完全状態であるので、0から7（唯一の有効な完全状態）への遷移対2から3への遷移（前の復号器サイクルにおいて2が初期化されたので）。最良の経路メトリックが選ばれ、勝ち残り完全状態が計算された経路メトリックおよびトレースバック・ビットとともに、デコーダ状態に保存される。
【００８４】
図１０に示されるように、ビット誤り率パフォーマンスは、超状態の数が完全状態の値である32状態から8超状態に削減されるとともに急速に劣化する。シンボル当たり四つの状態が有効である。
【００８５】
スヴェンソン論文で定義される削減状態数最尤シーケンス推定器は四つの状態しかもたない。トレリス構造は図１１に示されている。
【００８６】
この図に示されるように、値が1、2または3のビットは状態遷移を引き起こし、値が0のビットは引き起こさない。図解を簡略化するため図には示されていないが、すべての状態がすべての他の状態に接続されることを注意されたい。
【００８７】
この方法を使うと、無効状態は経路メトリックの計算から自動的に削除される。これは実装するのが簡単な構造であり、いかなるCPFSK変調にも適応できる。集合分割アプローチの場合と同様、超状態のそれぞれについて勝ち残り位相状態を維持するために判定帰還が使われる。復号器は次いで、選ばれた勝ち残り位相から四つの有効な経路についての経路メトリックを計算し、新しい勝ち残り経路メトリックを選び出す。次いでそれが、当該シンボルの間に取られた枝に基づいて超状態に保存される。枝が値0のビットに対応する場合、新しい超状態は古い超状態と同じである。しかしながら、遷移が値が1、2または3のビットに対応するならば、累積された経路は該他の超状態に保存される。
【００８８】
結果として得られるビット誤り率パフォーマンスが図１２に示されている。BERは削減状態技法の使用によってやや劣化している。
【００８９】
MILSTD-188-181Cにおける連続位相変調方式は複雑な最尤復号器を必要とする。これは上で論じた二つのアルゴリズムのいずれかを使って計算量を削減することができる。傾斜位相アプローチは、最も計算効率がよいことが立証される一方、最良のビット誤り率パフォーマンスをもつことが示されている。現在のMIL-STDは3dBの実装損を許容する（h＝4/16、5/16のオプションについて）。これは受信機が低下した計算量方式を実装し、それでも規格を満たすことを許容することができる。
【００９０】
以下では、本発明の限定しない例に基づく、先に記述され、ハイブリッドCPM変調のために使用されるプログラム可能なトレリスまたは最尤復号器とともに動作できる削減状態数技法の例のより詳細な記述が続く。
【００９１】
ハイブリッド連続位相変調（HCPM:  Hybrid  Continuous  Phase  Modulation）は、より高次の変調を生成するために追加的な振幅または位相パルスを使用する連続位相変調の変形である。標準的なCPMについては、変調次数の増加はシンボル・アルファベットの増大につながり、送信バンド幅の対応する増大および復号器トレリス構造の複雑さの指数関数的な増大につながる。しかしながら、ハイブリッドCPMは、基礎となるCPMトレリス構造に平行な枝を加えることによってより高次の変調を達成し、それにより受信機の複雑さを軽減する。以下の文章の目的は、TCMおよびCPMのような標準的な変調型の復調器の複雑さを軽減するために考案された技法がハイブリッドCPMにもうまく適用できることを実証することである。一例として、以下の文章は二つのハイブリッドCPM波形の電力およびスペクトル効率の解析を提供し、削減状態数技法の適用の個別的な例を与える。集合分割と、判定帰還技法をもつ削減状態数シーケンス推定との両方が解析され、比較される。結果は、削減状態数シーケンス推定が、ビット誤り率パフォーマンスにおける損失なしに、ハイブリッドCPM復調と結合されることができることを実証するであろう。
【００９２】
ハイブリッド連続位相変調は次の時間領域表現で表せる：
【００９３】
【数２】
2010517373.tif 000004
ここで、Tはシンボル期間、Eはシンボル当たりのエネルギー、fは搬送波周波数、Ai(t)、qi(t)およびaiはみな送信されるデータに依存し、hiは変調指数である。古典的なCPM変調と異なり、ハイブリッドCPMはαiに含まれるシンボル・アルファベットを追加的な振幅または位相（Ai(t)またはqi(t)）パルスのセットで拡張する。一定エンベロープHCPMについては、qi(t)が変調されるビットの一部を含む位相パルス形状である。そして一定でないエンベロープのハイブリッドCPMについては、Ai(t)が変調されるビットの一部を含む振幅パルス形状である。いずれの場合にも、正味の結果はシンボル当たりのより多いビットである。
【００９４】
長方形の（rectangular）（線形）パルス整形（shaping）を用いると、CPM波形は1REC  CPMまたはCPFSKとして表される。この完全応答信号に対しては、各CPM位相軌跡に異なる振幅パルス形状が適用され、非一定のエンベロープを生成することができる。最適パフォーマンスのため、各振幅パルスは良好な相互相関属性をもつべきであり、理想的には直交となる。直交する対蹠（antipodal）信号のサンプル集合は、表１に示されるような正弦波信号の倍数を含む。
【００９５】
【表１】
2010517373.tif 000005
送信信号のバンド幅を削減する方法として、他のCPMベースの振幅パルス方式が文献に記載されてきた。多振幅CPMが、同じ位相の配位図点が二つ以上の振幅位置をもつことを許容することによってCPM信号の変調次数を上げる方法として定義されている。多振幅CPMは、隣接するCPM配位図点の間の距離を短縮し、狭い送信スペクトルをもつ。減少したユークリッド距離の結果として、多振幅CPMの電力効率は、配位図密度の上昇によって損なわれる。多振幅CPM変調と異なり、ハイブリッドCPMは、もとのCPM信号と同じ送信配位図をもち、変調された信号に加えられる各追加的なビットの関数としてバンド幅の対応する増大をもつ。多振幅CPMに比べ、電力効率は変調次数の増加によって影響されない。多振幅CPMは、PSKまたはQAM変調方式のほうと比べられるべきものである（HCPMには似ていない）。それらの変調タイプも、変調次数の関数として配位図密度を上昇させ、電力効率の対応する損失を被るからである。
【００９６】
一定エンベロープ・ハイブリッドCPM変調は、より高いレベルの変調を生成するために、CPM信号位相パルスを利用する。他の一定エンベロープ・パルス・ベース変調方式が文献に記載されてきた。たとえば多パルスCPMは、所与のスペクトル・マスクについてよりよいユークリッド距離を提供するよう設計された、各送信されるビットについて異なる位相パルス形状を記述する一般化された方法である。多パルスCPMと異なり、一定エンベロープ・ハイブリッドCPMは、送られるシンボル当たりのビットの残りについて、標準的な基本的CPMαi（変調指数）および異なる位相パルスqi(t)の両方を使って変調次数を上げる。結果として得られる信号は、基本的CPM波形と同じ復号器トレリス構造をもつ。HCPMによって生成される追加的な平行枝は、トレリスの複雑さの増大を意図的に妨げる（枝メトリック計算のみが影響される）仕方で設計される。
【００９７】
一定エンベロープ・ハイブリッドCPMについては、位相パルス形状qi(t)は、スペクトルまたは電力効率の要件を満たすよう調整され、各パルスは、復号器における枝メトリック計算の距離属性を向上させるよう、（送信アルファベット内の他のシンボルに）できるだけ直交する送信シンボルを生成するよう設計される。可能な位相パルス形状組み合わせの一例は、図とともに最もよく例証できる（図７）。
【００９８】
可能な各形状は、シンボルの継続期間にわたって区分線形である。位相パルス形状のこの族はCPM変調に２ビットを加える。h＝1/4の二値CPFSK（1REC  CPM）は図８に示されるような完全状態トレリス構造をもつ。
【００９９】
削減状態数シーケンス検出アルゴリズムは、上記のような、そして参照によって組み込まれるスヴェンソン論文およびエユボグル論文に記載されるような最適な最尤復号器の修正に向けて二つのステップを定義する。第一のステップは、状態組み合わせの選択に対する集合分割アプローチである。h＝1/4CPFSK配位図を示す図９に示されるように、位相配位図を位相位置に各状態でラベル付けして描くと、完全状態０と４、１と５、２と６ならびに３と７を組み合わせることによって超状態を生成するトレリス構造が、削減状態数トレリスのための最良の距離を与えることが明白になる。
【０１００】
このCPMトレリス構造はすでに二つの特殊な属性をもつ。第一に、最初の開始状態が０状態であるとの想定のもと、各シンボルにおいて、有効な開始状態が奇数または偶数のいずれかでありうる。これは、送信器において、位相値0度で送信を開始することによって達成される。第二に、復号器が、一つおきのシンボルの復号において、奇数または偶数状態についての経路メトリックの計算をスキップできる。最適なCPM復号器はすでに、各復号器サイクルの間に状態の半分について経路メトリックを計算（更新）するのみという点まで「削減」されている。
【０１０１】
再び図１を参照すると、削減状態数トレリス構造が示されている。先述したように、完全状態のラベルは角括弧内に記されており、新しい超状態のラベルは角括弧内の各対の上に挙げられている。
【０１０２】
削減状態数トレリスを構築するとき、各完全状態は初期トレリスにおいてそうであったのと同じように接続されたままである。この特定のトレリスについて、各シンボル復号サイクルにおいて開始状態を交替させる特性属性は、復号器の重要なパラメータのままである。復号サイクルとは、入力シンボルから枝メトリックの完全状態を計算し、トレリス構造内の有効状態すべてについて経路メトリックを更新することとして定義される。
【０１０３】
削減状態数シーケンス検出のために要求される第二の重要な向上は、復号器における判定帰還段階である。経路メトリックおよびトレースバック・ビットとともに、復号器は各超状態における勝ち残り完全状態を保持する。最初は復号器は超状態0から始まると想定されるので、復号器状態も開始完全状態は0であり、4ではないと想定する。一般に、経路メトリックを適正に初期化することによって、復号器超状態は、削減された状態（すなわち0、1、2および3）のそれぞれについてリスト内の最初の完全状態に初期化されることができる。
【０１０４】
復号器が超状態1について経路メトリックを計算するとき、0から1への遷移を（対応する計算された枝メトリックを使って）状態２から状態１への遷移についてのメトリックと比較する。復号器は完全状態の値1を次の復号器サイクルのための勝ち残り状態として保存する。この復号器サイクルにおいて計算される次の超状態は7である（偶数の無効の超状態は飛ばす）。ここでもまた、0が初期復号器サイクルからの勝ち残り完全状態であるので、0から7（唯一の有効な完全状態）へ2へ3への遷移（前の復号器サイクルにおいて2が初期化されたので）そして勝ち残り完全状態が、計算された経路メトリックおよびデコーダ状態におけるトレースバック・ビットとともに保存される。
【０１０５】
ハイブリッドCPM変調は、トレリス構造内の各遷移に平行な枝を加える。最尤復号器は、各シンボルにおいて、どの平行枝が最良の距離（最良の数値的な枝メトリック値）をもつかを判定しなければならず、その値を現在の状態から状態への遷移のために使う。標準的なCPM計算量は、変調レベルおよびh値とともに増す。ハイブリッドCPMはトレリス構造に状態や遷移枝を追加しない。ハイブリッドCPM変調の計算量は、変調レベルに追加される各ビットについて要求される枝メトリックの数に基づく比例的な増大をもつ。
【０１０６】
ハイブリッドCPMのもう一つの特徴的な機能は、チャネル要件を満たすよう送信スペクトルを調整できることである。上記の表１の例に示されるように、1/2正弦波振幅形状を使って単一のビットがCPFSK変調に追加されることができる。二ビットが追加されるなら、完全な正弦波振幅パルスが既存の正弦波に加えられて四つの対蹠パルス形状を形成する。結果として得られるスペクトルが図１３に示されている。
【０１０７】
CPFSK信号の特徴的なバンド幅が保存されることを例証するために、各スペクトルは、シンボル・レートではなくビット・レートに規格化されている。実際には、バンド幅はハイブリッドCPM波形におけるシンボル当たりのビット数により増大される。結果として得られる90%バンド幅値は、CPFSK、1AMビットのハイブリッドCPMおよび2AMビットのハイブリッドCPMについてそれぞれシンボル・レートの0.68、2.1および3.4倍である。
【０１０８】
振幅パルス整形されたハイブリッドCPMは、図１４に示されるようなスペクトル属性をもつ。位相パルス整形の場合と同様、振幅パルス形状は信号にスペクトル成分を加える。図１１に示される各スペクトルは、変調のビット・レートに規格化されている。規格化なしでは、結果として得られる90%バンド幅はシンボル・レートの0.68、1.5および3.4倍である。
【０１０９】
バンド幅を変調レベルの関数として増加させる波形の直観的な期待は、信号の距離属性が増加的でなければならないというもので、対応する電力効率が改善される。これは、直交符号によって拡散されたPSK信号と等価である。結果として得られる信号バンド幅は、符号化率により増加し、電力効率は標準的なPSK変調と同じである。例として選ばれたパルス形状の場合、いくつかは多少のバンド幅拡張および対応する多少のEb/No改善を提供する。図１５に示されるように、振幅パルス整形されたハイブリッドCPMは各パルス形状について異なるパフォーマンス・レベルをもつ。
【０１１０】
略語「RS」は、ハイブリッドCPMの各例の削減状態バージョンを表すために使われる。図１５に示されるように、より高いスループット、3ビット毎シンボルでは、ハイブリッドCPM変調は2ビット毎シンボル・バージョンよりもよい電力効率をもつ。より広いバンド幅、すなわち完全な正弦波振幅パルス形状を選択することによって、Eb/Noパフォーマンスが2ビット毎シンボルのハイブリッドCPMについて改善されたことが検証された。
【０１１１】
3ビット毎シンボルのハイブリッドCPM信号の電力効率は標準的なh＝1/4  CPFSK変調に一致する。当業者は、CPFSK信号の変調レベルを増加させることが可能であることを理解する。復調器計算量は変調レベルとともに増大しうる。CPMトレリス内の状態数は、多レベルについても二値変調についてと同じであることができるが、各状態は、変調次数が増すにつれて多くなる数の枝をもつ。復調器はこれらの遷移枝のそれぞれについてのメトリックを、枝メトリックとその関連付けられた状態の経路メトリックとの和として計算する。その遷移枝が選ばれない場合、これは無駄な動作である。ハイブリッドCPMによって使用される平行枝の場合、復号器は、経路メトリックの加算なしに、単に二つの平行な経路の枝メトリックを比較する。状態の数および変調次数に依存して、経路メトリックのさらなる加算が、ハイブリッドCPM変調に対して、標準的なCPM変調の相対的な計算量を増す。
【０１１２】
位相パルス整形されたハイブリッドCPM変調ビット誤り率曲線が図１６に示されている。振幅パルス整形の場合と同様、位相パルス整形パフォーマンスは可変である。3ビット毎シンボル変調は2ビット毎シンボル・バージョンよりもパフォーマンスがよい。さらに、差は位相パルス形状の選択にある。2ビット毎シンボルのハイブリッドCPMについては、より大きな値のパルス整形が選ばれた場合、電力効率が改善される。
【０１１３】
振幅整形のある2状態の削減状態h＝1/3CPFSKおよびHCPMについての結果として得られるビット誤り率曲線が図１７に示されている。
【０１１４】
位相整形のある2状態の削減状態h＝1/3CPFSKおよびHCPMについてのビット誤り率曲線が図１８に示されている。
【０１１５】
増加した変調次数（４値（4-ary）、８値（8-ary）など）について。削減状態トレリス構造は比例的に増大する。しかしながら、HCPMについては、もとのCPM信号のトレリス構造が維持される。トレリス構造は平行な枝をもち、これは判定帰還や経路メトリック記憶を修正しない。最良の平行経路が各枝について選ばれ、次いでその超状態についての枝メトリックとして使われる。
【０１１６】
電力効率パフォーマンス曲線から、削減状態シーケンス検出をハイブリッドCPM変調と対にすることは、波形の有用性の範囲を効果的に拡張することが明らかである。直交振幅または位相変調の追加を用いてCPM信号のスループットを増すことは、各ノードにより多くの遷移枝を追加することほどは、復号器計算量を増加させない。削減状態シーケンス検出の追加を用いることで、より多数の完全状態をもつ基本CPMトレリス構造の使用による復号器計算量の対応する増大なしで、追加的な電力効率パフォーマンスが得られる。
【０１１７】
可能な各パルス形状は、シンボルの継続時間にわたって区分線形である。位相パルス形状のこの族は、CPM変調に2ビットを追加する。
【０１１８】
両方のタイプのハイブリッドCPM変調の例解として、一般的な基本トレリス構造が選択された。h＝1/4二値CPFSK（1REC  CPM）は、h＝1/4のCPFSKトレリスを示す図５に示されるように８つの状態をもつ完全状態トレリス構造をもつ。
【図１】
2010517373.tif 000006
【図２】
2010517373.tif 000007
【図３】
2010517373.tif 000008
【図４】
2010517373.tif 000009
【図５】
2010517373.tif 000010
【図６】
2010517373.tif 000011
【図７】
2010517373.tif 000012
【図８】
2010517373.tif 000013
【図９】
2010517373.tif 000014
【図１０】
2010517373.tif 000015
【図１１】
2010517373.tif 000016
【図１２】
2010517373.tif 000017
【図１３】
2010517373.tif 000018
【図１４】
2010517373.tif 000019
【図１５】
2010517373.tif 000020
【図１６】
2010517373.tif 000021
【図１７】
2010517373.tif 000022
【図１８】
2010517373.tif 000023
【国際調査報告】
2010517373.tif 000024
2010517373.tif 000025
2010517373.tif 000026
2010517373.tif 000027
2010517373.tif 000028