(57)【要約】サイズおよび拘束Ｋならびに生成多項式が変化する１つまたは複数の再帰形および／または非再帰形の組織トレリス符号に従って、コアにより受信された１つまたは複数のベクトルを復号する際に使用するためのチップ・アーキテクチャ・コアについて述べる。このコアは、コアによって受信されたベクトルの符号化に使用された各符号のサイズおよび拘束Ｋならびに生成多項式に応じて回路内で正確な数の回路要素が連続して再構成され相互接続され得るように構成された、（ａ）再帰形と非再帰形の両方の組織型についてのＡＣＳブロック（１１４）、ＢＭＵ発生器（１１０）およびトレース・バック機構（１１６）の再構成可能回路と、（ｂ）ＡＣＳブロック、ＢＭＵ発生器およびトレース・バック機構の間の再構成可能接続とを含む。
2008511266.tif 000002
【特許請求の範囲】
【請求項１】
サイズ、拘束Ｋ及び生成多項式が変化する複数の再帰形および／または非再帰形の組織トレリス符号のうちのいずれか１つに従って、コアにより受信された１つまたは複数のベクトルを復号する際に使用する再構成可能アーキテクチャであって、
前記アーキテクチャよって受信された前記ベクトルの符号化に使用された各符号のサイズおよび前記拘束Ｋならびに生成多項式に応じて回路内で正確な数の回路要素が適応可能に再構成され相互接続され得るように構成された、（ａ）再帰形と非再帰形の両方の組織型についてのＡＣＳブロック、ＢＭＵ発生器およびトレース・バック機構の再構成可能回路と、（ｂ）前記ＡＣＳブロック、ＢＭＵ発生器およびトレース・バック機構の間の再構成可能接続とを含む復号器を備える再構成可能アーキテクチャ。
【請求項２】
前記コアによって受信された前記ベクトルが硬判定および／または軟判定ベクトルを含む請求項１に記載の再構成可能アーキテクチャ。
【請求項３】
前記コアによって受信された前記ベクトルが畳込み符号を含む請求項１に記載の再構成可能アーキテクチャ。
【請求項４】
前記コアによって受信された前記ベクトルがトレリス符号変調〔ＴＣＭ〕を含む請求項１に記載の再構成可能アーキテクチャ。
【請求項５】
前記コアによって受信された前記ベクトルが畳込みターボ符号〔ＣＴＣ〕を含む請求項１に記載の再構成可能アーキテクチャ。
【請求項６】
前記コアによって受信されたベクトルがショート・ブロック符号を含む請求項１に記載の再構成可能アーキテクチャ。
【請求項７】
前記コアによって受信された前記ベクトルがブロック／積ターボ符号を含む請求項１に記載の再構成可能アーキテクチャ。
【請求項８】
前記復号器が、等化、フィルタリング、ＭＩＭＯ＆時空間復号計算のうちの１つまたは複数を含む工程を実施するように構成可能である請求項１に記載の再構成可能アーキテクチャ。
【請求項９】
前記復号器が、可変サイズの軟値ビット・サイズ・シンボル、および様々なサイズの符号のＫ値を伴うＨＩＨＯ（硬入力硬出力）、ＳＩＨＯ（軟入力硬出力）またはＳＩＳＯ（軟入力軟出力）としての硬判定と軟判定の任意の組合せの復号および／またはフィルタリングを実施するように再構成可能である請求項１に記載の再構成可能アーキテクチャ。
【請求項１０】
前記ベクトルのそれぞれを復号する諸工程のうちの少なくとも一部を実施するように構成されたアクセラレータを含むようにさらに構成される請求項１に記載の再構成可能アーキテクチャ。
【請求項１１】
再帰形と非再帰形の両方の組織型についてのＡＣＳブロック、ＢＭＵ発生器およびトレース・バック機構の前記再構成可能回路が、硬判定〔ＨＤ〕または軟判定〔ＳＤ〕の両方のベクトルを含む可変サイズのベクトルに対して作用するアルゴリズム、畳込み符号復号、トレリス符号変調復号〔ＴＣＭ〕、畳込みターボ符号〔ＣＴＣ〕復号、ＢＣＨハミングを含む小ブロック符号復号、ブロック／積ターボ符号復号（ＢＴＣ／ＰＴＣ）およびＭＬＳＥ／ＲＳＳＤ／ＲＳＳＥ／Ｐｅｒ  Ｓｕｒｖｉｖｏｒ  Ｐｒｏｃｅｓｓｉｎｇ（ＰＳＰ）タイプの等化／フィルタ／ターボ・ライクの時空間符号を形成するための畳込み／トレリス・ブロックまたは連接符号に基づくＭＩＭＯ＆時空間復号計算、可変サイズの軟値、ビット・サイズ・シンボル、および前記符号の様々なサイズのＫ値を伴うＨＩＨＯ（硬入力硬出力）、ＳＩＨＯ（軟入力硬出力）またはＳＩＳＯ（軟入力軟出力）としてのＨＤとＳＤの任意の組合せのいずれかを備えるトレリス復号を実施するように再構成可能である請求項１に記載の再構成可能アーキテクチャ。
【請求項１２】
前記再構成可能アーキテクチャ・リソースの少なくとも一部が、前記アルゴリズムのいずれかのトレリス復号を実施するためにパラメータ化される請求項１１に記載の再構成可能アーキテクチャ。
【請求項１３】
前記アルゴリズムのいずれかのトレリス復号に専用のリソースを含む請求項１１に記載の再構成可能アーキテクチャ。
【請求項１４】
前記ベクトルのそれぞれを復号する諸工程のうちの少なくとも一部を実施するように構成されたアクセラレータを含むようにさらに構成される請求項１１に記載の再構成可能アーキテクチャ。
【請求項１５】
ＤＳＰプロセッサの一部である請求項１に記載の再構成可能アーキテクチャ。
【請求項１６】
再構成可能論理アーキテクチャの形である請求項１に記載の再構成可能アーキテクチャ。
【請求項１７】
プログラマブル処理の形である請求項１に記載の再構成可能アーキテクチャ。
【請求項１８】
（ａ）ＤＳＰプロセッサの一部、
（ｂ）再構成可能論理アーキテクチャの形、および
（ｃ）プログラマブル処理の形のうちの２つまたは３つの形である請求項１に記載の再構成可能アーキテクチャ。
【請求項１９】
再構成可能モデム内で使用するための構成可能アクセラレータである請求項１に記載の再構成可能アーキテクチャ。
【請求項２０】
ＡＣＳブロックの前記再構成可能回路がＡＣＳバタフライを含む請求項１に記載の再構成可能アーキテクチャ。
【請求項２１】
ＡＣＳブロックの前記再構成可能回路がＲａｄｉｘアーキテクチャに基づく請求項１に記載の再構成可能アーキテクチャ。
【請求項２２】
ＡＣＳブロックの前記再構成可能回路がＲａｄｉｘ２、Ｒａｄｉｘ４およびＲａｄｉｘ８アーキテクチャとして再構成可能である請求項１に記載の再構成可能アーキテクチャ。
【請求項２３】
パワー・スペクトル解析、等化、同期、ＭＩＨＯ処理および相関に関するアルゴリズムを実行するための再構成可能なハードウェアを含む請求項１に記載の再構成可能アーキテクチャ。
【請求項２４】
前記ベクトルの送信のために使用される通信プロトコルの物理層およびＭＡＣ層のうちの１つまたは両方で使用されるチャネルおよびパラメータを推定するためのＭＬＳＥ、ＲＳＳＥおよびＰＳＰ技術のうちの１つまたは複数を実施するためのトレリス・ブロックを含むように再構成可能である請求項１に記載の再構成可能アーキテクチャ。
【請求項２５】
前記復号器が、前記再構成可能アーキテクチャによって受信されたベクトルを処理するのに使用されるアルゴリズムに応じて動的に変更され得るバスを含む請求項１に記載の再構成可能アーキテクチャ。
【請求項２６】
前記復号器が、メモリおよびパラメータ化された少なくとも１つのブロックをさらに含み、前記パラメータ化されたブロックのパラメータの値がメモリ内に格納され、前記パラメータの前記値を設定するために使用される請求項１に記載の再構成可能アーキテクチャ。
【請求項２７】
前記復号器が、パラメータ設定の値およびパラメータ化された少なくとも１つのブロックを受信するための入力をさらに含み、前記パラメータ化されたブロックのパラメータの値が前記入力で受信され、前記パラメータの前記値を設定するために使用される請求項１に記載の再構成可能アーキテクチャ。
【請求項２８】
メモリをさらに含み、制御信号が前記回路を再構成するために使用され、前記制御信号が前記メモリ内に格納される請求項１に記載の再構成可能アーキテクチャ。
【請求項２９】
再帰形と非再帰形の両方の組織型についてのＡＣＳブロック、ＢＭＵ発生器およびトレース・バック機構の前記可能な構成可能回路、ならびに前記ＡＣＳブロック、ＢＭＵ発生器およびトレース・バック機構の間の構成可能な接続のすべてを表す１組の構成信号を表現するさらなるデータを格納するためのメモリをさらに含み、（ａ）前記再構成可能回路および（ｂ）再構成可能接続が、前記構成信号にすぐに応答するように構成される請求項１に記載の再構成可能アーキテクチャ。
【請求項３０】
前記１組の構成信号を表現する前記データが、前記再構成可能アーキテクチャによって受信されたベクトルを復号するのに使用されるパラメータおよびアルゴリズムに関する情報を含む請求項２９に記載の再構成可能アーキテクチャ。
【請求項３１】
前記再構成可能アーキテクチャによって受信された前記ベクトルを符号化するのに使用される前記組織トレリス符号を決定するように構成されるアナライザをさらに含み、前記再構成回路および再構成可能接続が、こうした組織トレリス符号についての前記決定に応じて構成される請求項２９に記載の再構成可能アーキテクチャ。
【請求項３２】
サイズおよび拘束Ｋならびに生成多項式が変化し得る１つまたは複数の再帰形および／または非再帰形の組織トレリス符号に従って、再構成可能アーキテクチャによって受信されたベクトルを復号する際に使用するための前記再構成可能アーキテクチャであって、
複数の復号アルゴリズムに従って前記ベクトルを復号するために回路内で正確な数の回路要素が適応可能に再構成され相互接続され得るように構成された、（ａ）再構成可能回路ブロックと、（ｂ）前記ブロック間の再構成可能接続とを含む復号器を備える再構成可能アーキテクチャ。
【請求項３３】
サイズおよび拘束長Ｋならびに生成多項式が変化し得る１つまたは複数の再帰形および／または非再帰形の組織トレリス符号に従って、再構成可能アーキテクチャよって受信されたベクトルを復号する際に使用するための前記再構成可能アーキテクチャであって、
１つまたは複数の復号アルゴリズム、ならびに（１）等化および（２）フィルタリングの機能のうちの１つまたは複数に従って前記ベクトルを同時に復号するために回路内で正確な数の回路要素が適応可能に再構成され相互接続され得るように構成された、（ａ）再構成可能回路ブロックと、（ｂ）前記ブロック間の再構成可能接続とを含む復号器を備える再構成可能アーキテクチャ。
【請求項３４】
前記等化およびフィルタリング機能が様々なＭＬＳＥ／ＲＳＳＤ／ＲＳＳＥ／ＰＳＰ処理を含む請求項３３に記載の再構成可能アーキテクチャ。
【請求項３５】
前記等化およびフィルタリング機能が、畳込み／トレリス、ブロックまたはターボ符号に基づくＭＩＭＯおよび時空間復号を含めて、ＰＳＰ等化／フィルタリング復号を含む請求項３３に記載の再構成可能アーキテクチャ。
【請求項３６】
前記等化およびフィルタリング機能が、ビタビ・アルゴリズムを使用した処理を含む請求項３３に記載の再構成可能アーキテクチャ。
【請求項３７】
サイズおよび拘束Ｋならびに生成多項式が変化する複数の再帰形および／または非再帰形の組織トレリス符号に従って、コアよって受信された１つまたは複数のベクトルを同時に復号する際に使用するための前記再構成可能アーキテクチャであって、
前記アーキテクチャによって受信された前記ベクトルを符号化するために使用された各符号のサイズ、前記拘束Ｋおよび生成多項式に応じて回路内で正確な数の回路要素が適応可能に再構成され相互接続され得るように構成された、（ａ）再帰形と非再帰形の両方の組織型についてのＡＣＳブロック、ＢＭＵ発生器およびトレース・バック機構の再構成可能回路と、（ｂ）前記ＡＣＳブロック、ＢＭＵ発生器およびトレース・バック機構の間の再構成可能接続とを含む復号器を備える再構成可能アーキテクチャ。
【請求項３８】
サイズおよび拘束Ｋならびに生成多項式が変化する複数の再帰形および／または非再帰形の組織トレリス符号のいずれか１つに従って、コアよって受信された１つまたは複数のベクトルを復号する際に使用するための再構成可能アーキテクチャを備える集積チップであって、
前記チップによって受信された前記ベクトルを符号化するために使用される各符号のサイズ、前記拘束Ｋおよび生成多項式に応じて回路内で正確な数の回路要素が適応可能に再構成され相互接続され得るように構成された、（ａ）再帰形と非再帰形の両方の組織型についてのＡＣＳブロック、ＢＭＵ発生器およびトレース・バック機構の再構成可能回路と、（ｂ）前記ＡＣＳブロック、ＢＭＵ発生器およびトレース・バック機構の間の再構成可能接続とを含む復号器を備えるチップ。
【請求項３９】
請求項３８に記載の集積チップを含む通信システム。
【請求項４０】
サイズおよび拘束Ｋならびに生成多項式が変化する複数の再帰形および／または非再帰形の組織トレリス符号のいずれか１つに従って、符号化されたベクトルを復号する方法であって、
チップによって受信された前記ベクトルを符号化するために使用された各符号のサイズ、前記拘束Ｋおよび生成多項式に応じて回路内で正確な数の回路要素が適応可能に再構成され相互接続され得るように、（ａ）再帰形と非再帰形の両方の組織型についてのＡＣＳブロック、ＢＭＵ発生器およびトレース・バック機構の回路と、（ｂ）前記ＡＣＳブロック、ＢＭＵ発生器およびトレース・バック機構の間の接続を再構成することを備える方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本開示は、様々な拘束長Ｋ、多項式発生器、また任意選択で再帰形および／または非再帰形組織符号のためのビタビ復号アルゴリズムのオンライン再構成可能ハードウェア復号器を実装するシステムおよびその方法に関する。このシステムおよび方法は、こうしたアルゴリズムを使用する通信デバイスにおいて特に有用である。
【背景技術】
【０００２】
本出願は、２００４年８月２５日に出願した第６０／６０４２５８号、「Ｍｅｔｈｏｄ  ａｎｄ  Ｄｅｖｉｃｅ  ｆｏｒ  Ｏｎ−ｌｉｎｅ  Ｒｅｃｏｎｆｉｇｕｒａｂｌｅ  Ｖｉｔｅｒｂｉ  Ｄｅｃｏｄｉｎｇ  ｏｆ  Ｒｅｃｕｒｓｉｖｅ  ａｎｄ  Ｎｏｎ−ｒｅｃｕｒｓｉｖｅ  Ｓｙｓｔｅｍａｔｉｃ  Ｃｏｎｖｏｌｕｔｉｏｎ  Ｃｏｄｅｓ  ｗｉｔｈ  Ｖａｒｙｉｎｇ  Ｐａｒａｍｅｔｅｒｓ」（整理番号６６９４０−０２０）、ならびに２００５年３月３日に出願した第１１／０７１３４０号、「Ｌｏｗ−Ｐｏｗｅｒ  Ｒｅｃｏｎｆｉｇｕｒａｂｌｅ  Ａｒｃｈｉｔｅｃｔｕｒｅ  Ｆｏｒ  Ｓｉｍｕｌｔａｎｅｏｕｓ  Ｉｍｐｌｅｍｅｎｔａｔｉｏｎ  Ｏｆ  Ｄｉｓｔｉｎｃｔ  Ｃｏｍｍｕｎｉｃａｔｉｏｎ  Ｓｔａｎｄａｒｄｓ」（整理番号６６９４０−０２１）、および２００５年７月７日に出願した第１１／１７６１４９号、「Ａ  Ｍｅｔｈｏｄ  ｏｆ  ａｎｄ  Ａｐｐａｒａｔｕｓ  ｆｏｒ  Ｉｍｐｌｅｍｅｎｔｉｎｇ  Ｆａｓｔ  Ｏｒｔｈｏｇｏｎａｌ  Ｔｒａｎｓｆｏｒｍｓ  ｏｆ  Ｖａｒｉａｂｌｅ  Ｓｉｚｅ」（整理番号６６９４０−０２４）の優先権を主張するものである。
【０００３】
雑音のあるチャネルを介したバイナリ・データ伝送は、こうした伝送に起因し得るエラーを最小限に抑えるための様々な手法をもたらしてきた。たとえば、チャネルを介して信号を送信する前にそれを符号化するために様々な前方誤り訂正（ＦＥＣ：ｆｏｒｗａｒｄ  ｅｒｒｏｒ  ｃｏｒｒｅｃｔｉｏｎ）技術が、全体的な誤り率を減少させるための受信側での互換性のある復号技術と共に開発されてきた。チャネルの容量を向上させるための１つのＦＥＣ技術は、慎重に設計されたいくらかの冗長情報を、チャネルを介して送信されるデータに付加することを含む。この冗長情報の付加のプロセスは、チャネル符号化として知られている。畳込みおよびブロック符号化は現在、チャネル符号化の主要な２つの形である。畳込み符号化は一般に、一度に１つまたは数ビットのシリアル・データに作用する。ブロック符号は、比較的に大きい（一般に最大２〜３百バイトの）メッセージ・ブロックに作用する。様々な有用な畳込みおよびブロック符号、ならびに元のデータを回復するため受信された符号化情報系列を復号する様々なアルゴリズムが存在する。互換復号を伴う畳込み符号化は、無線伝送、たとえば携帯電話およびラジオなど、送信信号が主に加法性白色ガウス雑音（ＡＷＧＮ：ａｄｄｉｔｉｖｅ  ｗｈｉｔｅ  Ｇａｕｓｓｉａｎ  ｎｏｉｓｅ）によって損なわれるチャネルに特に適したＦＥＣ技術である。
【０００４】
畳込み符号は通常、２つのパラメータ、すなわち符号レートおよび拘束レート（ｃｏｎｓｔｒａｉｎｔ  ｒａｔｅ）を使用して記述される。符号レートｋ／ｎは、所与の符号器サイクルにおける畳込み符号器に入るビット数（ｋ）と、畳込み符号器によって出力されるチャネル・シンボルの数（ｎ）の比である。拘束長のパラメータＫは、畳込み符号器の「長さ」、すなわち出力シンボルを生成する組合せ論理を与えるのに、いくつのｋビット段階が使用可能であるかを表す。Ｋに密接に関連するのがパラメータｍであり、このパラメータは、入力ビットが畳込み符号器への入力に最初に現れた後、いくつの符号器サイクルにおいてその入力ビットが保持され、符号化のために使用されるかを示す。パラメータｍは、符号器のメモリ長と考えられ得る。
【０００５】
ビタビ復号は、畳込み符号化で使用される２つのタイプの復号アルゴリズムのうちの１つであり、もう一方のタイプは逐次復号である。逐次復号は、それが長い拘束長の畳込み符号で非常によく機能し得るという利点を有するが、それは可変の復号時間を有する。ビタビ復号には、それが固定の復号時間を有するという利点がある。それはハードウェア復号器の実装に大変適しているが、その計算要件は、拘束長に応じて指数的に増大し、したがって、実際にはそれは通常、Ｋ＝９以下の拘束長に制限される。ビタビ復号アルゴリズムは一般に、帯域幅が制限されたチャネル上で高い秒当たりビット数比率を圧縮する技術であるトレリス符号化変調を復号するのに使用される。一般に、ビタビ・アルゴリズムは元来、雑音のあるデジタル通信リンクのための誤り訂正手法と考えられていた。しかし、それは現在、情報理論、音声認識、キーワード・スポッティング、計算言語バイオインフォマティクス、ならびに他の適用例においても使用されている。
【０００６】
ビタビ復号は、トレリス上の最小の経路メトリックを有する経路を決定し、該経路メトリックが経路に沿った枝メトリックの和と定義される。１組の状態メトリックを時間の順方向に、トレリス上を段階ごとに処理することによって段階的に行われる。
【０００７】
ビタビ・アルゴリズムの複雑さは、時間段階ごとに拘束Ｋの復号器について、２ｋ−１個の経路メトリックを計算することにある。ビタビ復号器を実装するプロセッサは一般に３つの主要ブロック、すなわち枝メトリック計算ユニット（ＢＭＵ：ｂｒａｎｃｈ  ｍｅｔｒｉｃｓ  ｃａｌｃｕｌａｔｉｏｎ  ｕｎｉｔ）と、加算比較選択ユニット（ＡＣＳ：ａｄｄ−ｃｏｍｐａｒｅ−ｓｅｌｅｃｔ  ｕｎｉｔ）と、残存経路復号ユニットとを含む。枝メトリック・ユニットは一般に、ＡＷＧＮの場合にはユークリッド型である、サンプリングされた信号の目標からの距離の計算を実施する。新しい枝メトリックは、クロック・サイクルごとに、入ってくる各サンプルについて計算される。
【０００８】
同様に、状態メトリックの新しい値は、各時刻（ｔｉｍｅ  ｉｎｓｔａｎｔ）で計算されなければならない。換言すると、状態メトリックは、クロック・サイクルごとに更新されなければならない。結果として、再帰形およびパイプライン処理の一般的な手法は、システムのスループット増加のためには適用することができない。したがって、（チップで実装される場合）ＡＣＳユニットは、最大の電力および領域を消費するモジュールである。
【０００９】
残存管理ユニット（ＳＭＵ：ｓｕｒｖｉｖｏｒ  ｍａｎａｇｅｍｅｎｔ  ｕｎｉｔ）、すなわちトレース・バック・ブロックまたは機構は、残存ビットを使用してトレリス上をさかのぼり、元の入力ビットを再生する役割を担う。さかのぼる際に、トレリス上の最短経路がたどられなければならない。ＡＣＳ出力からの選択された最小メトリック経路は、各状態からその直前の状態への経路を指し示す。理論上は、最短経路の復号には、入力系列全体の処理を必要とする。しかし、実際には、残存経路は、何回か繰返した後に合流する。それらが互いに合流する点から、復号は一意のものである。すべての残存経路が高い確率で合流するトレリスの深さは、残存経路長と称される。
【００１０】
したがって、ビタビ・アルゴリズムは、耐雑音を達成するのに有効であるが、メモリ、計算リソースおよび電力消費のコストは、指数関数的に増加する。適応ビタビ・アルゴリズム（Ｔｅｓｓｉｅｒ，Ｒ．他、「Ａ  Ｒｅｃｏｎｆｉｇｕｒａｂｌｅ，Ｐｏｗｅｒ−Ｅｆｆｉｃｉｅｎｔ  Ａｄａｐｔｉｖｅ  Ｖｉｔｅｒｂｉ  Ｄｅｃｏｄｅｒ」、発行日不明など）、および動的再構成可能な適応ビタビ復号器（Ｓ．Ｓｗａｍｉｎａｔｈａｎ外の「Ａ  Ｄｙｎａｍｉｃａｌｌｙ  Ｒｅｃｏｎｆｉｇｕｒａｂｌｅ  Ａｄａｐｔｉｖｅ  Ｖｉｔｅｒｂｉ  Ｄｅｃｏｄｅｒ」、Ｃｈａｄｈａ，Ｋ．外の「Ａ  Ｒｅｃｏｎｆｉｇｕｒａｂｌｅ  Ｖｉｔｅｒｂｉ  Ｄｅｃｏｄｅｒ  Ａｒｃｈｉｔｅｃｔｕｒｅ」（ＩＥＥＥ  Ｐｕｂｌｉｃａｔｉｏｎ  Ｎｕｍｂｅｒ  ０−７８０３−７１４７−Ｘ／０１、６６〜７１頁（２００１））、「ＦＰＧＡ  ’０２」（２００２年２月２４〜２６日、Ｍｏｎｔｅｒｅｙ  Ｃａｌｉｆｏｒｎｉａ、ＡＣＭ  １−５８１１３−４５２−５／０２／０００２、２２７−２３６頁（２００２））、Ｌｉａｎｇ外の「Ａ  Ｄｙｎａｍｉｃａｌｌｙ−Ｒｅｃｏｎｆｉｇｕｒａｂｌｅ，  Ｐｏｗｅｒ−Ｅｆｆｉｃｉｅｎｔ  Ｔｕｒｂｏ  Ｄｅｃｏｄｅｒ」（Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  １２ｔｈ  Ａｎｎｕａｌ  ＩＥＥＥ  Ｓｙｍｐｏｓｉｕｍ  ｏｎ  Ｆｉｅｌｄ−Ｐｒｏｇｒａｍｍａｂｌｅ  Ｃｕｓｔｏｍ  Ｃｏｍｐｕｔｉｎｇ  Ｍａｃｈｉｎｅｓ  （ＦＣＣＭ’０４）（正確な発行日不明））、Ｃｈａｄｈａ，Ｋ，の「Ａ  Ｒｅｃｏｎｆｉｇｕｒａｂｌｅ  Ｄｅｃｏｄｅｒ  Ａｒｃｈｉｔｅｃｔｕｒｅ  ｆｏｒ  Ｗｉｒｅｌｅｓｓ  ＬＡＮ  ａｎｄ  Ｃｅｌｌｕｌａｒ  Ｓｙｓｔｅｍｓ」（Ｍａｓｔｅｒ  Ｔｈｅｓｉｓ、Ｒｉｃｅ  Ｕｎｉｖｅｒｓｉｔｙ、２００１年４月）Ｚｈｕ外の「Ｒｅｃｏｎｆｉｇｕｒａｂｌｅ  Ｖｉｔｅｒｂｉ  Ｄｅｃｏｄｉｎｇ  Ｕｓｉｎｇ  ａ  Ｎｅｗ  ＡＣＳ  Ｐｉｐｅｌｉｎｉｎｇ  Ｔｅｃｈｎｉｑｕｅ」（Ｐｒｏｃｅｅｄｉｎｇ  ｏｆ  ｔｈｅ  Ａｐｐｌｉｃａｔｉｏｎ−Ｓｐｅｃｉｆｉｃ  Ｓｙｓｔｅｍｓ  Ａｒｃｈｉｔｅｃｔｕｒｅｓ  ａｎｄ  Ｐｒｏｃｅｓｓｏｒｓ  （ＡＳＡＰ’０３）（正確な発行日不明））、Ｙｅｈ外の「ＲＡＣＥＲ：Ａ  Ｒｅｃｏｎｆｉｇｕｒａｂｌｅ  Ｃｏｎｓｔｒａｉｎｔ−Ｌｅｎｇｔｈ  １４  Ｖｉｔｅｒｂｉ  Ｄｅｃｏｄｅｒ」（０−８１８６−７５４８−９／９６、６０〜６９頁（１９９６））およびＺｈａｎ外の「Ｄｏｍａｉｎ  Ｓｐｅｃｉｆｉｃ  Ｒｅｃｏｎｆｉｇｕｒａｂｌｅ  Ｆａｂｒｉｃ  Ｔａｒｇｅｔｉｎｇ  Ｖｉｔｅｒｂｉ  Ａｌｇｏｒｉｔｈｍ」（ＩＣＦＰＴ  ２００４  ０−７８０３−８６５２−３／０４  ＩＥＥＥ  （２００４）、３６３〜３６６頁など））を含めて、この問題に対処するための様々な手法が提案されてきた。
【００１１】
再帰形と非再帰形の両方の組織符号のビタビ復号アルゴリズムのシフト・レジスタ畳込み復号器は、たとえばモデムおよび他の通信デバイスにおいて極めて重要な計算ブロックである。それらは、いくつか例を挙げると、チャネル復号器、ＭＬ（Ｍａｘｉｍｕｍ  Ｌｉｋｅｌｉｈｏｏｄ：最大尤度）等化器、ＭＩＭＯ  ＲＦアンテナ用の空間時間符号のＭＬ復号器およびＭＬフィルタリングにおいて使用される。再帰形組織符号および非再帰形組織符号のビタビ復号アルゴリズムのシフト・レジスタ畳込み復号器の興味深い特徴は、ＡＣＳブロックの調整可能な再構成可能回路、ＡＣＳ回路への調整可能な再構成可能接続を備えたＢＭＵ発生器、および再帰形組織型と非再帰形組織型形のための調整可能な再構成可能トレース・バック機構を使用することによって、それらが並列、直列またはハイブリッド（直列−並列）の形で動作し得ることである。したがって、同じハードウェアが、様々な拘束長Ｋおよび生成多項式を伴う再帰形組織符号と非再帰形組織符号の両方のために使用され得る。図１は、拘束長Ｋ＝７の非再帰形組織ビタビ復号器の一例を示しており、図２は、ＷＣＤＭＡターボ符号内部で使用される拘束長Ｋ＝４の再帰形組織ビタビ符号器の一例を示している。
【特許文献１】米国特許仮出願第６０／６０４２５８号明細書
【特許文献２】米国特許出願第１１／０７１３４０号明細書
【特許文献３】米国特許出願第１１／１７６１４９号明細書
【非特許文献１】Ｒ．Ｔｅｓｓｉｅｒ外、「Ａ  Ｒｅｃｏｎｆｉｇｕｒａｂｌｅ，  Ｐｏｗｅｒ−Ｅｆｆｉｃｉｅｎｔ  Ａｄａｐｔｉｖｅ  Ｖｉｔｅｒｂｉ  Ｄｅｃｏｄｅｒ」
【非特許文献２】Ｓ．Ｓｗａｍｉｎａｔｈａｎ外、「Ａ  Ｄｙｎａｍｉｃａｌｌｙ  Ｒｅｃｏｎｆｉｇｕｒａｂｌｅ  Ａｄａｐｔｉｖｅ  Ｖｉｔｅｒｂｉ  Ｄｅｃｏｄｅｒ」
【非特許文献３】Ｋ．Ｃｈａｄｈａ外、「Ａ  Ｒｅｃｏｎｆｉｇｕｒａｂｌｅ  Ｖｉｔｅｒｂｉ  Ｄｅｃｏｄｅｒ  Ａｒｃｈｉｔｅｃｔｕｒｅ」（ＩＥＥＥ  Ｐｕｂｌｉｃａｔｉｏｎ  Ｎｕｍｂｅｒ  ０−７８０３−７１４７−Ｘ／０１、６６〜７１頁、（２００１））
【非特許文献４】「ＦＰＧＡ  ’０２」（２００２年２月２４〜２６日、Ｍｏｎｔｅｒｅｙ  Ｃａｌｉｆｏｒｎｉａ、ＡＣＭ  １−５８１１３−４５２−５／０２／０００２、２２７−２３６頁（２００２））
【非特許文献５】Ｌｉａｎｇ外、「Ａ  Ｄｙｎａｍｉｃａｌｌｙ−Ｒｅｃｏｎｆｉｇｕｒａｂｌｅ，  Ｐｏｗｅｒ−Ｅｆｆｉｃｉｅｎｔ  Ｔｕｒｂｏ  Ｄｅｃｏｄｅｒ」（Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  １２ｔｈ  Ａｎｎｕａｌ  ＩＥＥＥ  Ｓｙｍｐｏｓｉｕｍ  ｏｎ  Ｆｉｅｌｄ−Ｐｒｏｇｒａｍｍａｂｌｅ  Ｃｕｓｔｏｍ  Ｃｏｍｐｕｔｉｎｇ  Ｍａｃｈｉｎｅｓ  （ＦＣＣＭ’０４））
【非特許文献６】Ｋ．Ｃｈａｄｈａ、「Ａ  Ｒｅｃｏｎｆｉｇｕｒａｂｌｅ  Ｄｅｃｏｄｅｒ  Ａｒｃｈｉｔｅｃｔｕｒｅ  ｆｏｒ  Ｗｉｒｅｌｅｓｓ  ＬＡＮ  ａｎｄ  Ｃｅｌｌｕｌａｒ  Ｓｙｓｔｅｍｓ」（Ｍａｓｔｅｒ  Ｔｈｅｓｉｓ、Ｒｉｃｅ  Ｕｎｉｖｅｒｓｉｔｙ、２００１年４月等）
【非特許文献７】Ｚｈｕ外、「Ｒｅｃｏｎｆｉｇｕｒａｂｌｅ  Ｖｉｔｅｒｂｉ  Ｄｅｃｏｄｉｎｇ  Ｕｓｉｎｇ  ａ  Ｎｅｗ  ＡＣＳ  Ｐｉｐｅｌｉｎｉｎｇ  Ｔｅｃｈｎｉｑｕｅ」（Ｐｒｏｃｅｅｄｉｎｇ  ｏｆ  ｔｈｅ  Ａｐｐｌｉｃａｔｉｏｎ−Ｓｐｅｃｉｆｉｃ  Ｓｙｓｔｅｍｓ  Ａｒｃｈｉｔｅｃｔｕｒｅｓ  ａｎｄ  Ｐｒｏｃｅｓｓｏｒｓ  （ＡＳＡＰ’０３））
【非特許文献８】Ｙｅｈ他、「ＲＡＣＥＲ：  Ａ  Ｒｅｃｏｎｆｉｇｕｒａｂｌｅ  Ｃｏｎｓｔｒａｉｎｔ−Ｌｅｎｇｔｈ  １４  Ｖｉｔｅｒｂｉ  Ｄｅｃｏｄｅｒ」（０−８１８６−７５４８−９／９６、６０〜６９頁（１９９６））
【非特許文献９】Ｚｈａｎ他、「Ｄｏｍａｉｎ  Ｓｐｅｃｉｆｉｃ  Ｒｅｃｏｎｆｉｇｕｒａｂｌｅ  Ｆａｂｒｉｃ  Ｔａｒｇｅｔｉｎｇ  Ｖｉｔｅｒｂｉ  Ａｌｇｏｒｉｔｈｍ」（ＩＣＦＰＴ  ２００４  ０−７８０３−８６５２−３／０４  ＩＥＥＥ  （２００４）、３６３〜３６６頁）
【発明の開示】
【発明が解決しようとする課題】
【００１２】
標準の実装では、機能固有の再構成可能性を提供するために、計算構造を解析することがまず必要である。一般にビタビ復号器はＡＣＳブロックのシャッフル交換相互接続構造を有し、この構造は、拘束長Ｋのサイズ、再帰形組織符号および／または非再帰形組織符号のタイプによって、また後者については選択されたフィードバック生成多項式によって変化する。さらに、ＡＣＳ回路内のＢＭＵ値をもつ出力の接続は、符号生成多項式（互いに異なる多項式の数、すなわち符号レート、たとえばレート１／２は２つ生成多項式を有し、レート１／４の符号は４つ生成多項式を有するなど）によって決まる。したがって、最もエネルギー効率のよい完全に並列の実装に柔軟性を与えることは困難であり、実装は一般に、実装がそれを対象にして設計されている符号レートによって制約される。
【００１３】
完全に並列の実装では、信号フローのグラフは、ハードウェアに直接にマップされる。一般に、拘束長Ｋの符号復号器は、２ｋ−１個のＡＣＳバタフライ・ユニットを必要とする。たとえば、拘束長Ｋ＝５の非再帰形組織符号、すなわち１６状態のビタビ復号器では、各段階に合計１６個のＡＣＳバタフライが存在し、それらは図３に示すようなやり方で相互接続される（図中、時間は左から右へと進行する）。この最大の並列アーキテクチャは、高性能および低電力消費実装の潜在性を有するが、しかし、それは、とりわけ大きい拘束長の復号器の場合には、大きいシリコン領域の高いコストを伴う。
【００１４】
実装が不動点演算で行われる場合、スケーリングおよびオーバーフローの処理は、変換器の正確な振舞いに不可欠である。復号器の各段階のＡＣＳバラフライ操作は、「２の補数の加算」を使用するので、状態メトリックが十分なビット（所与の拘束長Ｋについてメトリック間の最大差を表すのに必要なビット数より１ビット多い）を有する場合、２の補数の加算の特性によって、追加のハードウェアなしに再スケーリングが達成される。したがって、再構成可能な復号器の設計では、それは、必要とされる最大差に対応するメトリックのビット表現を有するのに十分である。したがって、再構成可能な実装の設計は、（１）シフト・レジスタ畳込み復号器の再構成可能な実装が対処することができる最大の拘束長Ｋ、および（２）予想される最大ＢＭＵ生成レートに依存する。こうした設計は、予想される最大の拘束長Ｋおよびレート以下のすべての拘束長について再スケーリングする必要性をもたらす。再構成可能アーキテクチャの基準の従来技術は、基準の復号器がそれぞれ、１つのタイプのビタビ・アルゴリズムだけを処理するように再構成可能でありまたは適応されるので、完全には満足できないものであり、したがって復号器の適用が制限される。こうした設計は、復号されるビタビ・アルゴリズムに応じて並列レベルが変化し得る場合でも並列レベルを固定し、すなわち並列−直列構造の柔軟性を許容しないので、さらなる制限が結果として生じる。最後に、より簡単な符号（ｋ＝３の符号など）が実装される場合、現在の設計では単純に、未使用のハードウェアがオフにされる。
【発明を実施するための最良の形態】
【００１５】
本明細書で開示するシステムおよび方法による、可変の拘束長Ｋおよび生成多項式の様々なタイプのビタビ復号アルゴリズムに従って再帰形と非再帰形の両方の組織符号を復号するように構成されたアーキテクチャを含む再構成可能な復号器。このシステムおよび方法の一実施形態では、このシステムおよび方法は、ハードウェアの高速（すなわち実質上リアルタイムの）のオンライン再構成（すなわち顕著な遅延を生じさせない）によって、幅広いパラメータを用いた複数のタイプのビタビ復号アルゴリズムによる再帰形および非再帰形組織符号のシフト・レジスタ畳込み復号器の実装を可能にする。このシステムおよび方法は、多くのタイプのうちのビタビ復号アルゴリズムのうちのいずれか１つを収容するように再構成可能であり、実質上リアルタイムに同時に複数の異なるタイプのビタビ復号アルゴリズムを収容することができる。このシステムおよび方法はさらに、複数のシフト・レジスタ畳込みビタビ復号器を備えるタイプの並列または直列の実装を対象としたハードウェア量の著しい減少を可能にする。このシステムおよび方法は、拘束長Ｋおよび生成多項式のサイズが変化する適応ＭＬ（Ｍａｘｉｍｕｍ  Ｌｉｋｅｌｉｈｏｏｄ：最大尤度）アルゴリズムの実装にも有効であり、オンラインで、またアルゴリズムへの入力に応じて決定される。
【００１６】
パイプライン化された再構成可能アーキテクチャが、標準の低複雑度のビタビ復号器と比較しても非常に低いエネルギー・オーバヘッドを伴ってビタビ・アルゴリズム復号器を実装するために、この開示に従って設計され得る。
【００１７】
ｒａｄｉｘ２  ＡＣＳバタフライを使用した復号器は、このタイプのアーキテクチャによって乗算の複雑さを最小限に抑えるので、特に興味深いものである。この空間的規則性は、ＶＬＳＩ実装の他のアルゴリズムのベースに比べて構造上の大きい利点である。ｒａｄｉｘ−２  ＡＣＳバタフライを使用した再構成可能アーキテクチャの背後にある単純さにつながる１つの態様は、接続回路が最小限の切換え点を使用するように再構成され得ることである。非再帰形組織符号では、シャッフルされたトレリスの構造は、最良の切換え構造を示し得る。たとえば、図４に示すシャッフル済みＫ＝５トレリス構造は、２つのシャッフル済みＫ＝４トレリスの構造に分割されることができ、このトレリス構造はさらに分割されることができ、８つのシャッフル済みＫ＝２トレリスの構造が生じるまで、以下同様に続く。図５で、それぞれのボックスは、各ステップでトレリスを分割するクロス乗算器（ＭＵＸ）である。それぞれのボックスが異なる制御関数によって制御される場合、基礎のシャッフル済みＫ＝５トレリスは、完全に並列のトレリスにおいて最大Ｋ個のＡＣＳ状態を占める任意のＫについて、非再帰形組織符号のトレリスの任意の組合せに分けられ得る。
【００１８】
シャッフルされたトレリスのアーキテクチャは、大きいＫが必要とされる直列実装についても役に立ち得るが、これは復号速度レートを減少させる。Ｋがより大きいＫであり、Ｔｒｅｌｌｉｓ  Ｋが、並列構成で提供され得る最大のＫであるならば、速度レートの減少は２Ｋ−ＴｒｅｌｌｉｓＫ倍である（したがって、２ＴｒｅｌｌｉｓＫ−１が、設計内に組み込まれたＡＣＳバタフライ・ユニットの数である）。
【００１９】
たとえば、並列設計におけるシャッフルされたＫ＝５は、１６個のＡＣＳバタフライ・ユニットを備え（図６の左側）、同じＫ＝５が、シャッフル済みＫ＝３トレリス（図６の右側）を４回使用して達成される。たとえば、追加のハードウェアは二重バッファ内の１６メトリックのためのＲＡＭであり、各ＡＣＳに対応するデータは二重バッファ内に４メトリックとして保存される必要がある。この方法は、完全並列アーキテクチャ、完全直列アーキテクチャ、または並列と直列の任意の組合せのアーキテクチャとして再構成可能ビタビ復号器を組み込むために使用されることができ、それによって、使用されるＡＣＳバタフライ・ユニットの数が決定される。上記内容から見て分かるように、それぞれの拘束長Ｋは、最大の並列能力が提供される再構成可能ビタビ復号器で実装され、提案されるアーキテクチャにより最大の効率がもたらされる。
【００２０】
再構成可能ハードウェアの利点を達成するための他のハードウェアは、トレース・バック・ブロックである。トレース・バック・ブロックは、低電力消費を可能にし、（シフト・レジスタ機構が比較的に大量のハードウェアを必要とし、また大量の電力を必要とする）大きい拘束長Ｋにも適している。トレース・バック・ブロックは、以下で分かるように、再構成にも適している。その再構成可能の場合では、メモリ長は、ハードウェア要件において、保存できるほど十分に大きく、すなわち最大拘束長の１０倍大きい必要がある。このような場合、完全パイプライン・アーキテクチャのために２つのトレース・バック・ブロックだけが並列に働く必要がある。
【００２１】
図７は、並列に働く２つのトレース・バック・ブロックの一例のウィンドウ操作（ｗｉｎｄｏｗ  ｏｐｅｒａｔｉｏｎ）を示している。こうした場合では、最適な性能および遅延に必要などんな数のトレース可能な長さにも、書込みおよび読出しアドレスに対する制御だけで足りる。非回帰組織符号の最大拘束長Ｋ＝４についてのＡＣＳシャッフル済みトレリス回路内のトレース・バック機構内のメモリを分割するための実装の一例が、図８に示されている。このハードウェアは、複数のシフト・レジスタ（ここでは、ＦＦ８２はフリップ・フロップである）によって管理される、対応する復号済みビットを拾い上げるために使用される複数のＭＵＸ  ８０を備える。図８の実施形態は、４つの出力を含む。４つの出力は、複数のビタビ復号器を並列に使用する可能性に対応する。図８の実施形態は、パラメータの１つの可能な集まりの実装を示している。出力０は、Ｋ＝４ビタビ・アルゴリズムの復号結果を出力するために使用される（またこの場合、１つだけの復号器を実装する必要がある）。２つの復号器がある場合（たとえばＫ＝３およびＫ＝１）、２つの復号器の出力は、それぞれ０および１に現れる。
【００２２】
一般に、出力は複数の並列復号器間で分離される。出力０は、Ｋ＝４復号器（１つのみ）、またはＫ＝３（複数の復号器のうちの第１および最大の出力）、またはＫ＝２（ここでも第１の出力）のために使用され得る。Ｋ＝２の第２の復号器（これは番号２でマーク付けされている）などの出力も使用され得るなどである。したがって、出力０、１、２および３はそれぞれ、４つの並列復号器の可能な出力の例である。したがって、ハードウェア構成は、同時に動作し得る１つから４つの復号器を提供し得る。
【００２３】
出力数は、並列復号器の可能な出力の数を示す。したがって、出力０はＫ＝４またはＫ＝３またはＫ＝２（１つだけの復号器が使用される場合）のときの出力を提供し、出力１はＫ＝２（２つの復号器が使用される場合）のときの追加の出力を提供し、出力２はＫ＝３（２つの復号器が使用される場合）またはＫ＝２（３つの復号器が使用される場合）のときの追加の出力を提供し、出力３は、４つの復号器が使用される場合にＫ＝４についての追加の出力を提供する。
【００２４】
この方法は、図８に示されるように、フリップ・フロップ８０ａ、８０ｂ、８０ｃおよび８０ｄ、ならびにシフト・レジスタ８２ａ、８２ｂおよび８２ｃを追加することによって、ハードウェアの完全な使用を可能にする。したがって、シリコンの最大の使用を可能にするのに、再構成可能な設計のためのごく少ない量のハードウェアだけが必要である。
【００２５】
図８で、入力０〜７は好ましくは、トレリス図中の互いに異なる経路の信頼度数値に対応するメモリからの出力である。ＭＵＸ８０ｄ、８０ｅ、８０ｆ、８０ｇ、８０ｈ、８０ｉおよび８０ｊは、復号結果がトレース・バック出力０、１、２および３（最大４）のうちの１つまたは複数で提供されるように作用する。ＭＵＸ８０ａ、８０ｂおよび８０ｃは、それらが所与のサイズの事前定義された数の復号器に合わせて回路を構成するために信号を渡すように再構成される。次いで、フリップ・フロップの８２ａ、８２ｂ、８２ｃ、８２ｄ、８２ｅ、８２ｆ、８２ｇは、トレース・バック出力０が第１の４つの入力（Ｋ＝３）のうちの最大の入力に対応し、トレース・バック出力２が最後の４つの入力（同様にＫ＝３）のうちの最大の入力に対応するなどとなるように回路を再構成するためのものである。一般に、このアーキテクチャは、（上記で説明したように）Ｋ＝２の最大４つの復号器の任意の組合せが並列に実行されることを可能にする。図８の実施形態は、フィードバック多項式の要件のため、再帰形組織符号を収容するのには必ずしも有効でない。
【００２６】
この障害の克服のため再帰形と非再帰形の両方の組織符号を収容するのに同じ再構成可能アーキテクチャを使用するために、再帰形組織符号が非再帰形組織符号のように表れ処理されるように、再帰形組織符号の特性を使用することが必要である。これは、好ましくは、非再帰形組織符号を収容するための図８のアーキテクチャを含むブロックを、図９で見られるようなシフト・レジスタおよびフィードバック多項式から構築されるスクランブラと組み合わせることによって達成される。図９は、たとえば、再帰形組織符号ではＫ＝４を有するＷＣＤＭＡターボ符号で使用されるような非再帰形組織符号復号器９０と連接されたスクランブラ９２を含む再帰形組織符号ビタビ復号器の一例を示している。図９で、上部分は、図２から複製された、ＵＭＴＳ規格内に現れるＫ＝４の再帰形組織畳込み符号の符号器２０を表している。この設計は、左側部分に組織的部分のための直接出力接続と、（図式の右側に現れる）レート１畳込み符号の符号器に接続されたシフト・レジスタ（スクランブラ）とを含む下部の設計に等価のものである。したがって、非再帰形組織符号の復号は完遂され得る。トレース・バック・ブロックの後に、再構成可能デスクランブラが追加され得る。別の問題は、ＡＣＳ回路トレリスへのＢＭＵ接続は、軟シンボルの一部がスクランブラの出力で提供されるので、適切に事前構成される必要があることである。しかし、それは限定的であり、したがって、計算されるとアーキテクチャの事前構成は時間的に固定され、ＢＭＵとＡＣＳトレリス回路の間の接続は、修正なしに再構成され得る。したがって、アーキテクチャの唯一の変化はトレース・バック・ブロックの最後に再構成可能スクランブリングを提供するために構成要素を追加することであり、それも取るに足らないシリコン・オーバヘッドである。このオーバヘッドは、トレース・バック再構成可能制御シフト・レジスタ（図８に示すフリップ・フロップ８０ａ、８０ｂ、８０ｃ、８０ｄ、８０ｅ、８０ｆ、８０ｇおよびシフト・レジスタ８２ａ、８２ｂおよび８２ｃ）を使用する場合、最小限に低減される。これを示すために、図９のスクランブリングの実施形態は、図８に示すフリップ・フロップからなるシフト・レジスタの出力でＸＯＲゲートを追加することによって容易に実施され得る。再構成可能スクランブラは、図１０で最もよく見られるように、それら間でＸＯＲされるＡＮＤゲートのアレイを含み得る。図１０は従来の表記を用いており、ｇ０１、ｇ０２およびｇ０３がスクランブラの定義多項式の係数であり、円がビットに関するＡＮＤ操作を意味し、＋を含む円はＸＯＲ操作を表す。係数の値は、変化し、外部制御信号によって設定され得る。
【００２７】
図１１は、開示する手法に従って設計されたデバイスの全体的アーキテクチャの一例である。このアーキテクチャは、可変の拘束長Ｋおよび生成多項式のビタビ復号アルゴリズムに従って再帰形と非再帰形の両方の組織符号を復号するための再構成可能畳込み復号器を実装することができる。このデバイスは好ましくは、再構成可能枝メトリック生成ブロックを備え、この再構成可能枝メトリック生成ブロックは、再構成可能バス・ネット１１２に送信される信号を生成する。後者は、並列分割、およびあらゆる可能な組合せで直列に結合する能力を備えた選択的に相互接続可能な複数のＡＣＳ  ２コンポーネントを好ましくは備える再構成可能シャッフル済みＡＣＳトレリス・ブロック１１４に信号を供給する。再構成可能ＡＣＳトレリス・ブロック１１４の出力は、並列分割機能および二重のウィンドウ操作を好ましくは伴う再構成可能トレース・バック機構ブロック１１６に適用される。制御機構ブロック１１８は好ましくは、再帰形組織符号が受信されるか、それとも非再帰形組織符号が受信されるかに拘らず、また変化する拘束長Ｋおよび生成多項式に応じてビタビ・アルゴリズムに従って信号を復号するように、ブロック１１０、１１２、１１４および１１６を再構成するためにブロック１１０、１１２、１１４および１１６に結合される。この点で、この実施形態を使用するいずれのシステムも、処理される符号化された信号を復号するのに必要なビタビ復号アルゴリズムの特性を必ずしも感知する必要はない。上記内容の具体的な適用例については、参照により本明細書に組み込まれている、２００５年３月３日に出願された同時係属出願第１１／０７１３４０号「Ｌｏｗｅｒ−Ｐｏｗｅｒ  Ｒｅｃｏｎｆｉｇｕｒａｂｌｅ  Ａｒｃｈｉｔｅｃｔｕｒｅ  Ｆｏｒ  Ｓｉｍｕｌｔａｎｅｏｕｓ  Ｉｍｐｌｅｍｅｎｔａｔｉｏｎ  Ｏｆ  Ｄｉｓｔｉｎｃｔ  Ｃｏｍｍｕｎｉｃａｔｉｏｎ  Ｓｔａｎｄａｒｄｓ」（整理番号６６９４０−０２１号）に記載されている。図１２は、この同時係属出願に記載され、特許請求されたシステムのブロック図を示している。
【００２８】
したがって、図１２に示すように、上記のチップ・アーキテクチャ要件に適合するようにされた集積チップの一実施形態は、以下の基本の機能構成要素を備える。
【００２９】
ＣＰＵ１２０は好ましくは、（ａ）デバイスのコンフィグウェア部分、すなわちネット・バス１２２、Ｉ／Ｏブロック１２４、ＲＡＭブロック１２６、メガファンクション・ブロック１２８、相互接続ブロック１３０、フラッシュ・メモリ・ブロック１３２およびクロック１３４を制御し、（ｂ）チップによって処理される信号のプロトコルに応じて、メガファンクション・ブロック１２８、ならびにバス１２２、Ｉ／Ｏブロック１２４、ＲＡＭブロック１２６、相互接続ブロック１３０、フラッシュ・メモリ・ブロック１３２およびクロック１３４の構成を固定するのに必要な比較的に小さいコンピュータ処理装置である。ＣＰＵ１２０は、ミラーおよび単純な割当ておよびタスクを計算し、またメガファンクションとＩ／Ｏブロックを相互接続するために使用されるバスを構成することによって役立つこともできる。
【００３０】
ネット・バス１２２は、プロトコルに応じて再構成可能である。Ｉ／Ｏブロック１２４は好ましくは、チップを外部と接続する構成可能なＩ／Ｏブロックである。そのタスクは、アプリケーション・アルゴリズムの「コンパイルされたソフトウェア」を受信すること、および入力データを受信し、出力された処理済みデータを引き渡すことを含む。ＲＡＭ１２６は、「コンパイルされたソフトウェア命令」を格納し、データをキャッシュおよびバッファするように好ましくは構成されるランダム・アクセス・メモリである。メガファンクション・ブロック１２８は好ましくは、アプリケーション機能の各ドメインを１つの機能として非常に効率的に計算することによって処理される、２つ以上のアプリケーションすなわちプロトコルの主なアプリケーション機能を含むように構成される。この場合には、メガファンクション・ブロック１２８は、本明細書で述べるトレリス型復号器のうちの１つまたは複数、またはその任意の組合せを含むように構成される。相互接続ブロック１３０は好ましくは再構成可能ネット・バスを含み、このネット・バスは、ＣＰＵ１２０、Ｉ／Ｏブロック１２４、ＲＡＭ１２６、メガファンクション・ブロック１２８、フラッシュ・メモリ１３２およびクロック・ブロック１３４を含めて、チップのすべての構成要素を相互接続する。相互接続ブロックは、好ましくは追加のメモリ内で、ミラーおよび単純な割当てまたはタスクを実施するように構成されることもできる。最後に、フラッシュ・メモリ１３０は好ましくは、チップがそのプログラムによって実行されるときにデータを格納する助けとなる。フラッシュ・メモリは好ましくは、複数のメモリ位置が１つのプログラミング操作で消去されまたは書き込まれることを可能にするＥＥＰＲＯＭの形であり、したがってそれを使用するシステムがそれぞれ異なる位置に対して同時に読み書きするときにより高い有効な速度で動作することができる。あまり複雑でない操作では、他のタイプのメモリが使用され得ることを理解されたい。情報は好ましくは、情報をチップ内に維持するのに電力を必要としないやり方でシリコン・チップ上に情報を格納することによってフラッシュ・メモリ内に格納される。したがって、チップへの電力は取り除かれることができ、情報は電力を消費することなくフラッシュ・メモリ内に保持される。さらに、フラッシュ・メモリは高速読出しアクセス時間およびソリッド・ステート耐衝撃性を提供し、携帯電話やＰＤＡのような電池式デバイス上のデータ格納などの適用例において、フラッシュ・メモリは特に望ましいものとなる。
【００３１】
したがって、このように述べたアーキテクチャは、集積回路として実装されることができる。このアーキテクチャは、再帰形と再帰形の両方の組織符号について拘束Ｋのサイズが変化し得る、任意のタイプのトレリス復号に適応可能であると考えられる。こうしたトレリス復号は、それだけに限らないが、（タイプ硬判定〔ＨＤ：ｈａｒｄ  ｄｅｃｉｓｉｏｎ）〕または軟判定〔ＳＤ：ｓｏｆｔ  ｄｅｃｉｓｉｏｎ）〕ベクトルの）可変サイズを有するベクトルに対して作用するアルゴリズム：畳込み符号復号、トレリス符号変調復号〔ＴＣＭ：Ｔｒｅｌｌｉｓ  ｃｏｄｅ  ｍｏｄｕｌａｔｉｏｎ  ｄｅｃｏｄｉｎｇ〕、畳込みターボ符号〔ＣＴＣ：Ｃｏｎｖｏｌｕｔｉｏｎ  Ｔｕｒｂｏ  Ｃｏｄｅ〕復号、（ＢＣＨ、ハミングなどのような）小ブロック符号復号、ブロック／積ターボ符号復号（ＢＴＣ／ＰＴＣ：Ｂｌｏｃｋ／Ｐｒｏｄｕｃｔ  ｔｕｒｂｏ  ｃｏｄｅ  ｄｅｃｏｄｉｎｇ）およびＭＬＳＥ／ＲＳＳＤ／ＲＳＳＥ／Ｐｅｒ  Ｓｕｒｖｉｖｏｒ  Ｐｒｏｃｅｓｓｉｎｇ（ＰＳＰ）タイプの等化／フィルタ／（畳込み／トレリスまたはブロックに基づく、あるいはターボ・ライクの時空間符号の形成のための連接符号の）ＭＩＭＯ＆時空間復号計算を含み得る。上記符号／フィルタの復号手順は、可変サイズの軟値ビット・サイズ・シンボル、および符号の様々なサイズのＫ値を伴うＨＩＨＯ（Ｈａｒｄ  Ｉｎ  Ｈａｒｄ  Ｏｕｔ：硬入力硬出力）、ＳＩＨＯ（Ｓｏｆｔ  Ｉｎ  Ｈａｒｄ  Ｏｕｔ：軟入力硬出力）またはＳＩＳＯ（Ｓｏｆｔ  Ｉｎ  Ｓｏｆｔ  Ｏｕｔ：軟入力軟出力）としてのＨＤとＳＤの任意の組合せであり得る。
【００３２】
上記内容に加えて、このアーキテクチャは、アルゴリズムのうちのいずれかのトレリス復号を実施するためにパラメータ化される再構成可能なアーキテクチャ・リソースを提供し得る。さらに、再構成可能アーキテクチャは、図１２のＲＡＭ１２６の使用など、アルゴリズムのうちのいずれかのトレリス復号に専用のリソースを含み得る。この再構成可能アーキテクチャは、ＤＳＰプロセッサの一部、再構成可能論理アーキテクチャ、プログラマブル処理（ソフトウェアまたはファームウェア）、あるいはこれらの手法のうちの２つ以上の手法の組合せとして実装され得る。上述したように、再構成可能アーキテクチャは、再構成可能モデムで使用されるための構成可能アクセラレータであり得る。この再構成可能回路は、ＡＣＳバタフライの形のＡＣＳブロックを含み得る。ＡＣＳブロックの再構成可能回路は、Ｒａｄｉｘ２、Ｒａｄｉｘ４およびＲａｄｉｘ８アーキテクチャなど、Ｒａｄｉｘアーキテクチャに基づき得る。さらに、図１２に示すようなアーキテクチャは、パワー・スペクトル解析、等化、同期、ＭＩＨＯ処理および相関に関するアルゴリズムを実行するための再構成可能なハードウェアを含み得る。図１２の実施形態で使用されるアーキテクチャなど、再構成可能アーキテクチャは、以下のうちの１つまたは複数を実施するためにトレリス・ブロックを含むように再構成可能とすることもできる：ベクトル送信のために使用される通信プロトコルの物理層とＭＡＣ層の両方のうちの１つまたは両方で使用されるチャネルおよびパラメータを推定するためのＭＬＳＥ、ＲＳＳＥおよびＰＳＰ技術。さらに、復号器は、再構成可能アーキテクチャによって受信されたベクトルを処理するために使用されるアルゴリズムに応じて動的に変更され得るバスを含み得る。再構成可能アーキテクチャは、それぞれ異なるトレリス型復号アルゴリズムの同時復号を可能にする。再構成可能アーキテクチャは、述べられているように、受信されたベクトルの性質、および行う必要がある必要な復号を決定するための必要なハードウェアおよびソフトウェアを含み得ることが明らかなはずである。決定されるとアーキテクチャは、参照により本明細書に組み込まれている、２００５年３月３日に出願された同時係属出願第１１／０７１３４０号「Ｌｏｗ−Ｐｏｗｅｒ  Ｒｅｃｏｎｆｉｇｕｒａｂｌｅ  Ａｒｃｈｉｔｅｃｔｕｒｅ  Ｆｏｒ  Ｓｉｍｕｌｔａｎｅｏｕｓ  Ｉｍｐｌｅｍｅｎｔａｔｉｏｎ  Ｏｆ  Ｄｉｓｔｉｎｃｔ  Ｃｏｍｍｕｎｉｃａｔｉｏｎ  Ｓｔａｎｄａｒｄｓ」（整理番号６６９４０−０２１）に全く記載されているように再構成される。
【００３３】
復号器は、メモリと、パラメータ化された少なくとも１つのブロックとをさらに含み、パラメータ化されたブロックについてのパラメータ値が、図１２の実施形態のＲＡＭ１２６などのメモリ内に格納され、パラメータの値を設定するために使用される。復号器はさらに、図１２に示すアーキテクチャにこうした入力を設けるなど、アーキテクチャの外部からパラメータ設定の値を受信するための入力を含み、または必要なパラメータをメモリ（ＲＡＭ１２６など）内に、またパラメータ化された少なくとも１つのブロックを格納することもでき、パラメータ化されたブロックについてのパラメータ値が入力で受信され、パラメータの値の設定のために使用される。
【００３４】
システム・アーキテクチャによって受信されたベクトルを復号するのに使用される復号器アルゴリズムに応答して回路を再構成するために、制御信号が格納され、またはシステム・アーキテクチャへの入力を介して外部から提供される。再帰形と非再帰形の両方の組織型についてのＡＣＳブロック、ＢＭＵ発生器およびトレース・バック機構の可能な構成可能回路、ならびにＡＣＳブロック、ＢＭＵ発生器およびトレース・バック機構の間の構成可能な接続のすべてを表す１組の構成信号を表現するさらなるデータは、（ａ）再構成可能回路および（ｂ）再構成可能接続が構成信号にすぐに応答するように構成されるようにメモリ内に格納され得る（または構成信号はシステム・アーキテクチャへの入力を介して外部から提供され得る）。１組の構成信号を表現するデータは、再構成可能アーキテクチャによって受信されたベクトルの復号に使用されるパラメータおよびアーキテクチャに関する情報を含み得る。
【００３５】
上述したように、このアーキテクチャは、再構成可能アーキテクチャによって受信されたベクトルを符号化するのに使用される組織トレリス符号を決定するように構成されたアナライザを含むことができ、再構成可能回路および再構成可能接続がこうした組織的トレリス符号についての決定に応じて構成される。
【００３６】
本明細書で開示した本開示のアーキテクチャ、およびそのすべての要素は、諸請求項のうちの少なくとも１つの範囲内に含まれる。ここで開示したチップ・アーキテクチャのいかなる要素も権利放棄されるものではなく、また意図されていない。
【図面の簡単な説明】
【００３７】
【図１】拘束長Ｋ＝７の非再帰形組織ビタビ復号器を示す図である。
【図２】ＷＣＤＭＡターボ符号内で使用される拘束長Ｋ＝４の再帰形組織ビタビ符号器を示す図である。
【図３】拘束長Ｋ＝５の非再帰形組織ビタビ復号器を示す図である。
【図４】拘束長Ｋ＝５のビタビ復号器のトレリス・シャッフリングの一例を示す図である。
【図５】最大拘束長がＫ＝５である場合の並列ビタビ復号器のトレリス・シャッフリング分割の一例を示す図である。
【図６】拘束長Ｋ＝３のシャッフル済みトレリスに基づくビタビ復号器の拘束長Ｋ＝５の直列実装と比較した、最大拘束長Ｋ＝５である場合のビタビ復号器の並列トレリス・シャッフリングの一例を示す図である。
【図７】トレース・バック操作のウィンドウィング描写の図である。
【図８】最大Ｋ＝４の拘束についてトレース・バック操作を実施するための再構成可能コントローラのブロック図である。
【図９】再帰形組織符号を、再帰形組織符号についてＫ＝４の場合にＷＣＤＭＡターボ符号で使用されるような非再帰形組織符号と共にスクランブルするための連接システムの一例のブロック図である。
【図１０】Ｋ≦５、ｇ０ｉが、ＡＮＤゲートを制御することによって実装されるフィードバック多項式を表し、＋がＸＯＲゲートを表す、再構成可能スクランブラの一例のブロック図である。
【図１１】本開示の方法およびシステムの一態様による、ＭＦ−Ｉコア・プロセッサを使用した再構成可能ビタビ復号器を提供するためのアーキテクチャの好ましい一実施形態のブロック図である。
【図１２】本明細書で述べるタイプのいずれかの再構成可能ビタビ復号器を備えるように構成された通信システムのブロック図である。
【図１】
2008511266.tif 000003
【図２】
2008511266.tif 000004
【図３】
2008511266.tif 000005
【図４】
2008511266.tif 000006
【図５】
2008511266.tif 000007
【図６】
2008511266.tif 000008
【図７】
2008511266.tif 000009
【図８】
2008511266.tif 000010
【図９】
2008511266.tif 000011
【図１０】
2008511266.tif 000012
【図１１】
2008511266.tif 000013
【図１２】
2008511266.tif 000014
【国際調査報告】
2008511266.tif 000015