【手続補正書】
【提出日】平成16年6月4日(2004.6.4)
【手続補正１】
【補正対象書類名】明細書
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【書類名】      明細書
【発明の名称】  データを符号化する方法
【特許請求の範囲】
【請求項１】  符号化直交周波数分割多重化(ＣＯＦＤＭ)方式のようなマルチキャリア周波数分割多重化方式を使用してデータを伝送するために、データワードを、それぞれが実現可能なq個の異なる値(qは１より大きい偶数)を有する2m のシンボル(m≧3)のコードワードとして符号化する方法であって、
上記データワードは、上記伝送のピーク対平均包絡線電力比が、任意の固定の整数p(1≦p≦m-2)について所定の閾値2P+1 より大きくならないように、それらの値および、
【数１】
1999163826.tif 000001
の生成マトリクスをもつコードの線形サブコードのコセットの１つまたは複数の組から完全なコセットの単位で選択されるコードワードに従って符号化され、上式で、zは、0ないし2m-1の整数値であり、yは、mないし0の整数値であり、xは、(m+1)ビット２進数として表される要素のビットに関する乗算を示し、除算の結果は、１ディジットとして表され、
上記コセット組の中のコセットの全てのコセット標本は、
【数２】
1999163826.tif 000002
の形、または上式から項X1ないしXmの添え字の置換によって導かれる形であり、上式で、X1ないしXmは、上記生成マトリクスの中の最初のm行の行ラベルであり、形式vp,m-p(Xm-p*Xm)の項は、Xm-pおよびXmのような行のシンボルに関する乗算の後、そのワードとvp,m-pのようなそれぞれの係数をシンボルに関してモジューロq乗算することによって導かれる１ワードを示し、＋を○で囲んだ記号は、ワードのシンボルに関するモジューロq加算を示し、係数vi,j(1≦i≦pおよび1≦j≦m-p)および係数wi,j(1≦i＜j≦p)は、0からq-1までの範囲から選択された整数値である方法。
【請求項２】  上記mは、少なくとも４である、請求項１に記載の方法。
【請求項３】  上記qは、４で割り切れ、上記係数vi,j(1≦i≦pおよび1≦j≦m-p)および上記係数wi,j(1≦i＜j≦p)は、偶数であるように選択される、請求項１に記載の方法。
【請求項４】  p=1であり、上記コセットの組の中のコセットのすべてのコセット標本は、
【数３】
1999163826.tif 000003
の形であり、上式でv1=v1,1,v2=v1,2,...,vm-1=v1,m-1 である、請求項１に記載の方法。
【請求項５】  q=2である、請求項４に記載の方法。
【請求項６】  p=1であり、上記コセットの組の中のコセットのすべてのコセット標本は、
【数４】
1999163826.tif 000004
の形であり、上式で、v1=v1,1/2,v2=v1,2/2,...,vm-1=v1,m-1/2は、0ないし(q/2)-1の範囲の値をもつ、請求項３に記載の方法。
【請求項７】  q=4である、請求項６に記載の方法。
【請求項８】  m≧5であり、
係数v1,v2,...vm-1 の値の組合わせは、形式v1v2...vm-2vm-1 の２進ワードのそれぞれが、少なくとも４のハミング重みをもつという特性を有するような組合わせに制限され、
項X1 ないしXm の添え字の上記置換は、添え字m-1が置換される値よりも小さい値に添え字1が置換されるという条件を満足する、請求項５に記載の方法。
【請求項９】  m≧5であり、
係数v1,v2,...vm-1 の値の組合わせは、形式v1v2...vm-2vm-1 の２進ワードのそれぞれが、少なくとも４のハミング重みをもつという特性を有するような組合わせに制限され、
項X1 ないしXm の添え字の上記置換は、添え字m-1が置換される値よりも小さい値に添え字1が置換されるという条件を満足する、請求項７に記載の方法。
【請求項１０】  m≧6であり、係数v1,v2,...vm-1の値の組合わせは、形式v1v2...vm-2vm-1 の２進ワードが、２つの特性すなわち、
それぞれのワードv1v2...vm-2vm-1 は、少なくとも４のハミング重みをもち、
【数５】
1999163826.tif 000005
であるような組合わせに制限される、請求項５に記載の方法。
【請求項１１】  m≧6であり、係数v1,v2,...vm-1 の値の組合わせは、形式v1v2...vm-2vm-1 の２進ワードが、２つの特性すなわち、
それぞれのワードv1v2...vm-2vm-1 は、少なくとも４のハミング重みをもち、
【数６】
1999163826.tif 000006
であるような組合わせに制限される、請求項７に記載の方法。
【請求項１２】  q≧4であり、
係数v1,v2,...vm-1 の値の組合わせは、上記係数の少なくとも２つが0およびq/2以外の値をもつような組合わせに制限され、
項X1 ないしXm の添え字の上記置換は、添え字m-1が置換される値よりも小さい値に添え字1が置換されるという条件を満たす、請求項４に記載の方法。
【請求項１３】  q≧4であり、
係数v1,v2...vm-1 の値の組合わせは、係数v1およびvm-1のどちらも、0またはq/2の値をもたないような組合わせに制限され、
係数v1 は、常に係数vm-1 より小さくなるように選ばれる、請求項４に記載の方法。
【請求項１４】  q≧8であり、
係数v1,v2...vm-1 の値の組合わせは、上記係数の少なくとも２つが0およびq/4以外の値をもつような組合わせに制限され、
項X1 ないしXm の添え字の上記置換は、添え字m-1が置換される値よりも小さい値に添え字1が置換されるという条件を満たす、請求項６に記載の方法。
【請求項１５】  q≧8であり、
係数v1,v2,...vm-1 の値の組合わせは、係数v1およびvm-1 のどちらも0またはq/4の値をもたないような組合わせに制限され、
係数v1 は、常に係数vm-1 より小さくなるように選ばれる、請求項６に記載の方法。
【請求項１６】  p≦m-4であり、
【数７】
1999163826.tif 000007
が成り立ち、
それぞれのワードvi,1vi,2...vi,m-p-1vi,m-p は、少なくとも４のハミング重みをもち、
1≦i＜j≦pである係数wi,jは、値q/2をもち、
項X1 ないしXm の添え字の上記置換は、添え字m-pが置換される値よりも小さい値に添え字1が置換されるという条件を満たす、請求項１に記載の方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
この発明は、データを符号化する方法および装置、並びにそのような方法および装置を取り入れた通信システムに関連する。この発明は特に、符号化直交周波数分割多重化方式(ＣＯＦＤＭ)のようなマルチキャリア(複数搬送波)周波数分割多重化方式を使用してデータを伝送する方法、装置およびシステムに関連する。
【０００２】
【従来の技術】
高性能のコンピュータに基づく装置および機器の一層の普及により、有線および無線技法の両方に基づく高速かつ高容量の通信の必要性がますます高まっている。この必要性の増加に対処する１つの方法は、一層高いシンボル・レートで動作する通信システムを設計することである。しかしシンボル・レートの増加は、典型的に、シンボル間間隔の対応する低減を伴い、これは、一層大きいシンボル間干渉(ISI)および受信されるシンボル内の重大なエラーを引き起こすことがある。有線リンクの場合、シンボル間干渉は、例えば通信リンクの異なった部分間で不完全につながれたインタフェースにおける信号反射から生じることがある。無線リンクの場合、シンボル間干渉の大きな原因は、信号が伝わる空間内の(建物のような)物体からの信号反射を含む多重経路(マルチパス)伝搬である。リンクを使用する移動ユニットの移動は、移動ユニットに到達する複数の伝搬経路の連続的かつ複雑な変化を引き起こすので、特に移動無線通信は、この原因によるシンボル間干渉の影響を受けやすい。
【０００３】
通信システム容量を増加させ、シンボル間干渉を抑えるために積極的に研究開発されている技法は、ＣＯＦＤＭ操作のようなマルチキャリア(または多重トーン)周波数分割多重化操作である。ＣＯＦＤＭシステムでは、同時に複数のシンボルが伝送され、それぞれのシンボルは、近接した間隔のそれぞれの周波数をもつマルチキャリア信号の個々の変調を(例えば位相シフトキーイングによって)制御する。それぞれのキャリアによってシンボルが伝送されるレートと適切な関係をもつようにキャリア周波数間隔を選ぶことによって、個々のキャリアを、(キャリアが互いに直交すると仮定されるところで)それに近接するキャリアからの干渉なく復調することができるように保証することができる。データ・シンボル(１つのデータワード)の１群を符号化するために、１シンボル期間(１つのコードワード)に個々のキャリアによって同時に伝送されるシンボルの１組が選択される。そのシンボルの組は、冗長性を含む(すなわちコードワードはデータワードより多くのシンボルをもつ)。この冗長性は、受信の際、受信されるシンボル内のエラーの検出のため、および必要であればそれらのエラーの訂正のために使用される。
【０００４】
複数シンボルの並列の伝送は、直列システムを使用して連続的に個々のシンボルを伝送する場合に必要とされるより低いシンボル・レートで所望のデータ・レートを達成することができるので、ＣＯＦＤＭシステムは、シンボル間干渉の影響をある程度抑制する。低いシンボル・レートは、それぞれのシンボルの長い持続時間およびシンボル遷移間の長い期間を意味し、従ってシンボル間干渉の影響を低減させる。冗長性の包含によって与えられるエラー検出および訂正能力は、信号のフェージングおよび他の原因のために受信されたシンボル内に生じるエラーを検出し、訂正することを可能にし、データ腐敗に対する抵抗力を高める。
【０００５】
しかし、実際の伝送信号が得られる複素数値信号の典型的なピーク対平均値包絡線電力比(PMEPR)から生じる制限のため、現在のＣＯＦＤＭシステムは、特定の伝送信号の電力について最大限の潜在的利益を得ることの困難さに直面している。この伝送される信号は実質的に、近接した間隔の周波数にある、それぞれのシンボル遷移で変化する個々の位相をもついくつかの信号の合計であるので、信号全体は、低レベルであるが変化する振幅のかなり長い間隔によって区分される過渡的な目立ったピークを示す傾向がある。伝送装置は、クリッピングまたは他の歪みのないピークを再生するように調整されなければならないので、ピーク間の間隔の相当長い時間の間、装置は、その最大能力よりも相当低い信号レベルで動作する。その結果、装置の地理的(geographical)レンジは、その公称電力定格について期待されるより非常に低い。あるいは、所望のレンジを含み、非効率的に操作される一層高性能の装置を用意しなければならない。
【０００６】
この問題は、基本的に、起こりうるデータワードを符号化するコードワードの慎重な選択によって軽減することができることが知られている(例えばA.E.Jones、T.A.WilkinsonおよびS.K.Bartonによる「Block coding scheme for reduction of peak to mean envelope power ratio of multicarrier transmission schemes」(Electronics Letters,1994年12月8日,vol.30,no.25,pp.2098-2099)に示されている)。しかし、コードワードを選択してPMEPRを低減させるとき、コードが良好なエラー訂正特性をもつように保証することも重要である。また高スループット通信システムの実現は、長いコードワードおよび迅速な符号化および復号化プロシージャの使用を含むことが望まれる。一般に複数の長いコードワード(例えば約16シンボル以上)の場合のように、チェックされようとする有効なコードワードの数が多い場合、単純なルック・アップ・テーブルの使用は、容易に実現されるが、特に復号する間のコンパクトな(および低電力、安価な)回路を使用した迅速な処理には向かない。従って符号化および復号化操作は、例えばデータワードまたはコードワードシンボルについて組合わせ論理を実施して一方から他方に変換し、または少なくとも使用される任意のルックアップ・テーブルのサイズを強制する解析的プロシージャに関して規定することができることが好ましい。
【０００７】
別の困難さは、一般的なシステム内で使用するコードを規定するために選択が行われる、起こりうるコードワードの純粋な(sheer)量によって提示される。コードワード内のシンボル数が増加するに従って、可能なコードワードの数は、たとえ２進シンボルの場合であっても急速に増加する。可能な３個(３進)または４個(４進)の値をもつシンボルについて、利用可能なコードの数は、非常に短いコードワードについても非常に大きくなり、それゆえ実現可能な全てのコードワードの単純な包括的なサーチは、単にPMEPRを最小限にするための現実的な時間内に実現できない。特にPMEPR、エラー検出または訂正に関連する好ましい基準、並びに符号化および復号化の容易さを同時に満たし、所望のサイズをもつコードワード組が、実際に存在するかどうか分からないとき、エラー訂正および実現要求を満たそうとする試みは、そのようなサーチの困難さを増大するだけである。多数の異なるデータワード(すなわち比較的多くのシンボルを含むデータワード)を符号化し、許容できる高さのデータ転送レートを達成することができるように、選ばれるコード内に利用可能な多数のコードワードをもつことが望まれるとき、この難しさはさらに悪化する。
【０００８】
ある種のコードは、いくつかの望ましい特性をもつことができることが知られている。B.M.Popovicによる「Synthesis of Power Efficient Multitone Signals with Flat Amplitude Spectrum」(IEEE Transactions on Communications,vol.39,no.7,1991年7月,pp.1031-1033)は、任意の２進または多相の相補シーケンスを使用して、実数値信号の波高要素が(複素数値信号の3dBより低いまたはそれに等しいPMEPRに対応する)6dBVより低いまたはそれに等しいような多重トーン信号を構築することができることを示している。これらのシーケンスの例は、２進Golay相補シーケンス対(M.J.E.Golayによる「Complementary series」(IRE Transactions on Information Theory,vol.IT-7,1961年4月,pp.82-87)の場合のように記述されている。しかしPopovicの文献は、多重経路のフェージングの測定および多重トーンの妨害(jamming)のような状況に注意が向けられており、その中で、要求される信号を生成するとき、１つのコードワードを連続的に使用することができる。従ってPopovicは、どのように複数のそのようなシーケンスを識別し、情報を運ぶ実際のコードの中のPMEPRについて6dBVの制限を達成することができるか指示していない。また、実際の具体化に適したコードに関する上述の要求について何も述べられていない。実際にPopovicは、「最小のピーク-ピーク振幅をもつ多重トーン信号の構築は、今もなお解析的な解決方法がない従来からの問題である。」と述べている。
【０００９】
Golay相補シーケンス対およびそれらを使用して規定されるコードは、いわゆるGolayコードとは異なるものであり、混同してはならないことに注意すべきである。Golay相補シーケンス対およびGolayコードは、同じ研究者によってそれぞれ別個に規定されており、従って両方とも彼の名前が引用されている。
【００１０】
符号化および復号化するための方法および装置は、国際特許出願第PCT/GB 97/02 464号明細書に記述されており、その中で、可能なコードワードの潜在的に非常に大きなサーチ空間にもかかわらず、異なるコードワードの相当数が、実際に識別可能であり、それらは、PMEPRについて予測可能な低い制限を与え、特定されるエラー検出および訂正特性を有し、高速な回路内で実現することができる。その中で記述される、関連するPMEPRに従ってコードワードのコセット(剰余類、coset)を順番に並べるための技法のいくつかは、計算の相当な量を含むことがある。
【００１１】
【発明が解決しようとする課題】
この発明の目的は、それぞれのコセットについてピーク包絡線電力の大規模な計算を必要とせずに、多くとも所定の閾値であるPMEPRをもたらすコードワードの多数のコセットの識別を可能にすることである。
【００１２】
【課題を解決するための手段】
この発明の上記目的は次の方法によって解決される。
【００１３】
符号化直交周波数分割多重化(ＣＯＦＤＭ)方式のようなマルチキャリア周波数分割多重化方式を使用してデータを伝送するため、データワードを、実現可能な異なるq個の値(qは１より大きい偶数)をそれぞれがもつ2mシンボル(m≧3)のコードワードとして符号化する方法であって、上記データワードは、該データワードの値および、
【００１４】
【数８】
1999163826.tif 000008
【００１５】
の生成マトリクスをもつコードの線形サブコードの１つまたは複数のコセット組から完全なコセットの形で選択されるコードワードに従って符号化され、上記選択されるコードワードは、上記伝送のピーク対平均値包絡線電力比が、任意の固定の整数p(1≦p≦m-2)について所定の閾値2P+1より大きくならないように選択され、上式で、zは、0から2m-1までの整数値であり、yは、mから0までの整数値であり、xは、(m+1)ビットの２進数として表される要素のビットに関する乗算を示し、除算の結果は、１ディジットとして表され、
上記コセット組の中のコセットのすべてのコセット標本は、
【００１６】
【数９】
1999163826.tif 000009
【００１７】
の形、または上式から項X1ないしXmの添え字の置換によって得られる形であり、上式で、X1ないしXmは、上記生成マトリクスの中の最初のm行の行ラベルであり、項vp,m-p(Xm-p*Xm)は、Xm-pおよびXmのような行をシンボルに関して乗算し、その結果とvp,m-pのようなそれぞれの係数をシンボルに関してモジューロq乗算することによって得られる１ワードを示し、＋を○で囲んだ記号は、上記ワードのシンボルに関するモジューロq加算を示し、係数vi,j(1≦i≦pおよび1≦j≦m-p)および係数wi,j(1≦i＜j≦p)は、0からq-1までの範囲から選択される整数値である、データを符号化する方法。
【００１８】
【発明の実施の形態】
この発明に従って、符号化直交周波数分割多重化方式(ＣＯＦＤＭ)を使用してデータを伝送する通信システムの中でデータを符号化する方法および装置を、添付の図面を参照して説明する。
【００１９】
図1ないし図3は、都市環境における移動通信の背景にある多重経路伝搬の問題を概略で示している。基地局10は、例えばマイクロ波波長の無線によって、移動電話機12のような移動通信装置と通信する。基地局10と電話機12の間の見通し信号経路14があり、建物および他の構造物の形の(マイクロ波信号に関する)複数の反射体の存在のため、さらに複数の反射信号経路16もある。これらの経路は典型的に長さが異なるので、それらの宛先への到達時に異なる伝播遅延を含む。例えば移動電話機12で受信される信号全体は、異なる経路を通って電話機に到達する多様な信号の合計である。
【００２０】
伝送される信号は、(例えば位相シフトキーイングによって)搬送波(carrier wave)を変調するシンボルの連続を含むと考えることができる。図2に示されるように、異なる伝播遅延をもつ複数の経路を通る信号の結果として、１つのシンボルについて受信される合成信号18は、そのシンボルについて伝送される信号20の正確な複製でなくなる。具体的に言えば、受信される合成信号は、一般に伝送された信号より持続時間が長く、伝送された信号の正確な複製が終了する点の後に、重要な振幅をもつ裾部分をもつ。この裾部分が、シンボル期間の重要な部分に及ぶ場合、図３に示されるように、時刻Ｔで終了するはずのパルスについて、裾部分は、上に重なり、後に続くシンボルの受信を妨害する。その結果、後に続くシンボルは、不正確に受信されることがあり、すなわちそのシンボルについて受信器内で検出される値は、他のノイズ原因がなくても、伝送された値を正確に表すことができない。この種の信号劣化は、シンボル間干渉(ISI)として知られている。
【００２１】
シンボル間干渉の影響は、図4aに示されるように伝送されるシンボルの持続時間を引き延ばすことによって軽減することができ、受信されるそれぞれのシンボルは、複数の経路の伝搬遅延から生じる裾部分を越える。後に続くシンボル・レートの低減の影響を抑えるため、それぞれがマルチキャリアの１つ１つを変調する複数のシンボルを同時に伝送することが提案されている。従って図4aないし図4hに示されるように、８つのキャリアが使用される場合、それぞれのキャリア上のシンボル期間は、(図３に示されるような)１つのキャリアの場合に必要とされる期間の８倍であるが、同じ全体のシンボル・レートを維持する。複数のキャリア間の周波数間隔が、シンボル期間の逆数の整数倍である場合、他のキャリアからの干渉なく、キャリアのそれぞれを変調する個々のシンボル・ストリームを回復することが可能である。この技法は、直交周波数分割多重化方式(ＯＦＤＭ)として知られている。
【００２２】
複数のキャリアの使用に加えて、ブロック符号化の使用により追加のエラー検出および訂正能力を提供することも提案されている。図5に示されるように、データ・シンボル(この例では２進シンボル)の直列ストリームは、概念的に、各々が５つのシンボルを含む連続する群またはワードに分割される。５つのシンボルの１群は、対応する８ビットのコードワードを出力する５ビット-８ビット(5B/8B)符号器30に入力される。このコードワードは、間隔がΔf離れた８つの連続する周波数でキャリア信号を生成する８つの発振器34のバンクを制御する８位相シフトコントローラ32のバンクに加えられる。コードワードの個々のビットは、それぞれの位相シフトコントローラに、正または負のいずれかの位相シフトΔφを生成させ、個々の発振器によって生成されるキャリア信号を、そのビットの現在値に依存して変調する。
【００２３】
複数の発振器34の変調された出力は、加算機36で結合され、伝送される信号を生成する。実際に、発振器34および加算機36の機能は、破線の枠38で示されるように、逆高速フーリエ変換(IFFT)を実現する１つのデジタル信号プロセッサに統合されることが好都合である。図６に概略で示されるように、伝送されようとするデータは、ブロック40で受信され、直列-並列変換器42で並列形式に変換される。並列データは、上述したように符号器30で符号化され、符号化されたデータは、変調器32/IFFT38でマルチキャリア信号の生成を制御する。このマルチキャリア信号は、Ｄ/Ａ変換器44でアナログ形式に変換され、送信器46によって増幅され、伝送される。
【００２４】
受信は、本質的にこのプロセスの逆である。すなわち信号は、受信器48によって受信され、増幅され、Ａ-Ｄ変換器50によってデジタル形式に変換される。デジタル信号は、高速フーリエ変換(FFT)を実現するデジタル信号プロセッサを含む復調器52に供給され、復調器52は、合成マルチキャリア信号の中の成分信号を分離し、復調する。復調されたデータは復号器54に渡され、復号器54は、符号器30によって行われた符号化の逆を行い、典型的にはエラー検出および訂正機能も実施する。その後、並列-直列変換器56が、ブロック58で出力される直列形式にデータを変換する。
【００２５】
符号器30によって実現されるコードの選択は、送信器46の効率的な操作に重要な意味をもつ。マルチキャリア信号は、等しい振幅および等間隔の周波数をもついくつかの正弦波の合計を含む。その結果、合成信号の最大絶対値は、成分正弦波の相対的な位相に非常に影響されやすい。これらの相対的な位相は、次のシンボル期間に伝送されようとするコードワードの値に従って、位相シフトコントローラ32によってそれぞれのシンボル期間の終わりに変更される。相対的な位相の特定の組および現在のコードワードの値に依存して、伝送される信号の振幅は、図7に示されるように、低レベルであるが変化する値の間隔と共に、時々はっきりと目立ったピークをもつ。従って、伝送される信号のピーク対平均値包絡線電力比は比較的高い。
【００２６】
そのような信号が歪みなしで伝送されようとする場合、送信器46は、線形増幅器を使用して、比較的非効率な方法でそれを操作しなければならず、そのダイナミックレンジの大部分は、伝送された信号の振幅がまれにそのピーク値に達するときを除いて使用されない。
【００２７】
伝送するデータを符号化するために実際に使用されるコードワードの組の適当な選択によって、この問題を軽減することが提示されている。PMEPRの極端な値を生成するコードワードの使用を避けるためのブロック符号化の使用は、T.A.WilkinsonおよびA.E.Jonesの「Minimisation of the peak to mean envelope power ratio of multicarrier transmission schemes by block coding」(1995 IEEE 45th Vehicular Technology Conference,1995年7月,pp.825-829)で示唆されている。この提示は、PMEPRの低減が可能であることを示すが、符号化および復号化の効率的な実現を可能にし、復調される信号内のエラーを検出し、訂正する望ましい能力を提供するコードワードの１組を選択することの困難さも示している。この問題に対処する方法が記述されているが、実際的な解決方法は提示されていない。この方法に対する修正が、同じ著者の「Combined coding for error control and increased robustness to system nonlinearities in OFDM」(1996 IEEE 46th Vehicular Technology Conference,1996年4月,pp.904-908)に開示されている。この修正の中で、線形ブロック・コードは、エラー訂正および検出の望ましい特性を与えるように選ばれる。具体的には、コード内の線形性および冗長性を利用して、PMEPRを低減させるが同等のエラー検出および訂正特性をもつ新しい値に、コード値を体系的に変形させることを提示している。4B/7B、4B/8Bおよび11B/15Bコードについていくつかの例が示されており、その中で、必要とされる変形は、可能な全てのコードワード値を、それぞれのコードワードに従って変調されるマルチキャリア信号のPMEPRの順に並べることを含むプロシージャによって識別される。このような包括的なサーチ方法は、(例えば15ビットのオーダーの)比較的短いコードワードについては実現可能であるが、調べられようとするコードワードの数は、コードワード長と共に急速に増大する。従って32ビットのコードワードの場合、40億を超えるコードワードが並べられなければならない可能性があり、これは、どうみても極端な時間がかかり、実際上非常に高価になりうる。この要求によって現れる障害は、調べられる組の中にコードワードの適当な部分組が実際に存在する保証がないことにより増大することがある。
【００２８】
Popovicは、上で参照した文献の中で、１つの２進または多相の相補シーケンスの使用を提示している。しかし上述した1996年発表の文献は、そのようなシーケンスが、それらのエラー訂正/検出能力に関連して簡単には適用できないことを示している。
【００２９】
上で参照した特許出願明細書は、多くの異なるコードワードを含む組を識別する方法を記述しており、それらのコードワードは全て、エラー訂正および検出特性に関連する所望の基準、それらコードワードに従って変調されるマルチキャリア信号の最大PMEPR、並びに実際の(例えば組合わせ論理の使用を含む)符号器および復号器の実現の容易さおよび効率を満たす。
【００３０】
上で参照した特許出願明細書に記述されるように、コードワードの１組は、「生成マトリクス」から導かれる「基本」コードを、複数の「コセット標本(coset representatives)」と結合することによって構築される。例えば16ビット(２進)のコードワードの場合、生成マトリクスは次のように与えられる。
【００３１】
【数１０】
(0000 0000 1111 1111)            (X1)
(0000 1111 0000 1111)            (X2)
(0011 0011 0011 0011)            (X3)
(0101 0101 0101 0101)            (X4)
(1111 1111 1111 1111)            (X')
【００３２】
16ビットの基本コードは、この生成マトリクスの行の32の線形結合の全てを含み、以下の形で表される。
【００３３】
【数１１】
1999163826.tif 000010
【００３４】
上式で、行係数a1,a2,a3,a4およびa'のそれぞれは、0または1の値をとる。この基本コードは、線形である。すなわち、そのコードワードの任意の２つについて、ビットに関する(bitwise)排他的論理和演算(モジューロ２の加算)の結果は、コード内の別のコードワードである。
【００３５】
対応するジェネレータ・アレイは、16ビットの生成マトリクスを、行X1,X2,X3およびX4の可能な全ての対のビットに関する乗算によって得られる以下の追加の行(この場合６つ)と結合することによって生成される。
【００３６】
【数１２】
(0000 0000 0000 1111)           (X1*X2)
(0000 0000 0011 0011)           (X1*X3)
(0000 0000 0101 0101)           (X1*X4)
(0000 0011 0000 0011)           (X2*X3)
(0000 0101 0000 0101)           (X2*X4)
(0001 0001 0001 0001)           (X3*X4)
【００３７】
これら追加の行から特定の方法で構築される12の特定のコセット標本(例えば0001 0010 0001 1101)はそれぞれ、ビットに関する排他的論理和演算によって、16ビットの基本コード内の全てのコードワードと結合され、基本コードのコセットの１組を構成する、最終的な所望のコードワードの組を生成する。
【００３８】
それらのコードワードは、行X1,X2,X3,X4およびX'を含む生成マトリクスをもつ線形サブコード(コード全体でもよい)のコセットの１組を構成する。この種の基本コードの使用は、所望のエラー検出および訂正特性を提供する。線形サブコードの選択は、例えば組合わせ論理を使用して、それぞれのコセットの中の符号化および復号化を簡潔に実現することができることを保証する。一般にコセットは、基本コードから実現可能なコードワードの空間全体のそれぞれの部分への体系的な移行または変換であると考えることができる。線形サブコードのコセットの使用は、PMEPRの特に高い値をもたらす望ましくない(全てゼロおよび全て１のような)コードワードの回避を可能にするが、ある程度基本コードのエラー制御特性も維持することができる。基本コードのそれぞれのコセットは、ほぼ同じような関連するPMEPRをもつコードワードを含む傾向があるので、そのようなコセットの１組からのコードワードの選択は、PMEPRの良好な制御を与える。コセット標本が、以前に参照した特許出願明細書に記述される形をとる特定のケースで、PMEPRは、3dBを越えないことが分かる。最小ハミング(Hamming)距離(すなわち、2mの２進シンボルを含む有効なコードワードを、他の有効なコードワードに変形するために、例えば干渉によって値が変更されるシンボルの最小数)は、2m-2である。
【００３９】
より一般的に言えば、特定のコードワード長2mに関する生成マトリクスは、以下のように与えられる。
【００４０】
【数１３】
1999163826.tif 000011
【００４１】
上式で、zは、0から2m-1までの整数値であり、yは、mから0までの整数値であり、xは、共に(m＋1)ビットの２進数として表される２つの要素((2・z+1)および2y)のビットに関する乗算(ビットに関する論理積)を示し、除算の結果は、１ディジットで表される。このマトリクスの第１のライン(y=m)は、行X1を与え、第２のライン(y=m-1)は、行X2を与え、最後から２番目のライン(y=1)は、行Xmを与え、最後のライン(y=0)は、行X'を与える。
【００４２】
従って、例えば64ビット(m=6)のコードワード長の場合、第２の行X2(y=m-1=5)上の第１のシンボル(z=0)は、((2・0+1)x2m-1)/2m-1、すなわち(1x32)/32である。ビットに関する乗算に含まれる要素を(m＋1)ビットの２進数として表現すると、(0000001x0100000)/32になり、これは、(0000000)/32すなわち(１ディジットとして表すと)0をもたらす。
【００４３】
第２の行の第２のシンボル(z=1)は、((2・1＋1)x2m-1)/2m-1、すなわち(3x32)/32であり、(0000011x0100000)/32すなわち再び0を与える。この行の16番目のシンボル(z=15)は、((2・15+1)x2m-1)/2m-1、つまり(31x32)/32であり、(0011111x0100000)/32すなわち0をもたらす。
【００４４】
17番目のシンボル(z=16)は、((2・16+1)x2m-1)/2m-1、すなわち(33x32)/32である。これは、(0100001x0100000)/32、すなわち(0100000)/32または1をもたらす。同じ結果が、18番目から32番目のシンボルについて得られる。
【００４５】
33番目のシンボル(z=32)のについて、マトリクスは、((2・32+1)x2m-1)/2m-1、つまり(65x32)/32を与え、これは、(1000001x0100000)/32すなわち0を与える。0の結果が、同様に次の15シンボルについて得られる。
【００４６】
49番目のシンボル(z=48)は、式((2・48+1)x2m-1)/2m-1、すなわち(97x32)/32によって与えられ、(1100001x0100000)/32すなわち1を与え、最後の15シンボルについても同様の結果である。従って第２の行全体は、(0000 0000 0000 0000 1111 1111 1111 1111 0000 0000 0000 0000 1111 1111 1111 1111)である。
【００４７】
第３の行X3(y=m-2=4)の場合、第１のシンボルは、((2・0+1)x2m-2)/2m-2、すなわち(1x16)16であり、(0000001x0010000)/16すなわち0を与える。同じ結果が、次の７つのシンボルについて生成される。9番目のシンボルに場合、式は、((2・8+1)x2m-2)/2m-2すなわち(17x16)/16であり、これは、(0010001x0010000)/16すなわち1をもたらし、10番目から16番目のシンボルについても同様である。その後シンボルは、行の残りについて、0が8個のブロックと1が8個のブロックを交互に置くことを続ける。(0000 0000 1111 1111 0000 0000 1111 1111 0000 0000 1111 1111 0000 0000 1111 1111)。64ビットのコードワードのための生成マトリクスの他の行も、同様の方法で導かれる。
【００４８】
2mビットの基本コードは、生成マトリクスの行の全ての線形結合を含み、以下の形で示される。
【００４９】
【数１４】
1999163826.tif 000012
【００５０】
上式で、行係数a1,a2,a3,...amおよびa'のそれぞれは、0または1の値をとる。対応するジェネレータ・アレイは、2mビット・生成マトリクスを、行X1,X2,X3,...Xmの可能な全ての対のビットに関する乗算によって得られる追加の行と結合することによって生成される。これら追加の行から特定の方法で導かれる特定のコセット標本はそれぞれ、ビットに関する排他的論理和演算によって2mビットの基本コード内の全てのコードワードと結合されて、基本コードのコセットの１組を構成する、必要とされるコードワードを生成する。
【００５１】
この技法は、シンボル値の一層高い任意の位数qの場合の符号化にも適用することができる。qは、例えば４進(quarternary)(q=4)、６進(hexary)(q=6)、８進(octary)(q=8)および一層高い位数のような２の整数倍である。そのような場合も、上述と同じ生成マトリクスが使用され、例えば8個のシンボル(m=3の場合2m=8)を含むコードワードの場合は次のように与えられる。
【００５２】
【数１５】
(0000 1111)         (X1)
(0011 0011)         (X2)
(0101 0101)         (X3)
(1111 1111)         (X')
【００５３】
８シンボル４進基本コード(可能な4個のシンボル値)は、この生成マトリクスの行の256の線形結合の全てを含み、以下の形で与えられる。
【００５４】
【数１６】
1999163826.tif 000013
【００５５】
上式で、＋を○で囲んだ記号は、シンボルに関する(symbol-wise)モジューロq(４進の場合はモジューロ４)加算を示し、行係数a1,a2,a3およびa'はそれぞれ、0ないしq-1(４進の場合、0ないし3)の全ての整数値をとる。この基本コードは線形である。すなわち、そのコードワードの任意の２つについて、シンボルに関するモジューロ４加算の結果は、コード内の別のコードワードである。対応するジェネレータ・アレイは、生成マトリクスを追加の行と結合することによって生成される。これら追加の行は、行X1、X2およびX3の可能な全ての対のシンボルに関するモジューロ４乗算によって得られ、すなわちX1*X2、X1*X3およびX2*X3である。従って、８シンボル４進の符号化の場合、追加の行は以下のように与えられる。
【００５６】
【数１７】
(0000 0011)          (X1*X2)
(0000 0101)          (X1*X3)
(0001 0001)          (X2*X3)
【００５７】
同様に、2mシンボル４進基本コードは、生成マトリクスの行の全ての線形結合を含み、以下の形で与えられる
【００５８】
【数１８】
1999163826.tif 000014
【００５９】
上式で、行係数a1,a2,a3,...amおよびa'は、0、1、2または3の値をとる。対応するジェネレータ・アレイは、2mシンボルの生成マトリクスを、行X1,X2,X3,...Xmの可能な全ての対のシンボルに関するモジューロ４乗算によって得られる追加の行と結合することによって生成される。これらの追加の行から特定の方法で導かれる特定のコセット標本は、シンボルに関するモジューロ４乗算によって、2mシンボル基本コード内の全てのコードワードとそれぞれ結合され、必要とされるコードワードを生成する。
【００６０】
シンボル値の数がqである場合、基本コードは、生成マトリクスの行の線形結合の全てを含み、以下の形で与えられる。
【００６１】
【数１９】
1999163826.tif 000015
【００６２】
上式で、行係数a1,a2,a3,...amおよびa'はそれぞれ、0、1、...q-1の値をとり、＋を○で囲んだ記号は、シンボルに関するモジューロq加算を示す。この基本コードは線形であり、すなわちそのコードワードの任意の２つについて、シンボルに関するモジューロq加算の結果は、コード内の別のコードワードである。対応するジェネレータ・アレイは、2mシンボルの生成マトリクスを、行X1,X2,X3,...Xmの可能な全ての対のシンボルに関するモジューロq乗算によって得られる追加の行と結合することによって生成される。これら追加の行から特定の方法で導かれる特定のコセット標本はそれぞれ、シンボルに関するモジューロq加算によって、2mシンボル基本コード内の全てのコードワードと結合され、必要とされるコードワードを生成する。
【００６３】
４進、８進および一層高い位数のコードのエラー検出およびエラー訂正特性を述べるとき、最小ハミング距離だけでは、コードワードに影響を及ぼしうるエラーの範囲を十分に表さない。これは、１シンボル内のエラーが、q/2の隣接するシンボル値までの遷移(transition)を伴うことがあるからである(値q-1と0は隣り合う考えられる)。実際の影響は、それぞれが隣のシンボル値への１つの遷移のみを含む異なるシンボル中の２つまたはそれ以上のエラーと同じくらいまたはそれ以上に深刻である。例えば、１つの８進シンボルの値6から値1までの変化(3つ隣の値への遷移)は、１つは6から7まで、もう１つは7から0まで(両方とも隣の値への遷移)という2つの８進シンボルの変化よりも深刻でありうる。従って、追加の有用な測定は、有効なコードワードをある他の有効なコードワードに変形するために必要とされるシンボル値遷移の最小数として定義される最小リー(Lee)距離である。２進の場合、ハミング距離およびリー距離は、同一である。
【００６４】
上で参照した特許出願明細書に記述されるようなＣＯＦＤＭ信号を符号化するおよび復号化する方法および装置は、エラー検出および訂正特性、低いPMEPR、実現の利便性並びに有用なデータ転送レートの非常に有利な組み合わせを提供する。その中に記述されるように、ある状況において、これらの異なる特性の間のトレードオフを変更するように、コードワードの選択を修正することが望ましい。
【００６５】
例えば、PMEPRの高い最大値を許容する代わりに、データ転送レートを高めるように、コードワードの利用可能な数を増やすことが望ましい。例えば、基本コードの追加のコセットを構築し、コセット内のコードワードの使用に起因する最大ピーク包絡線電力(PEP)を導き出すことが可能である。これは、コセットが、それぞれのコセットに関する最大ピーク包絡線電力を昇順に並べられること可能にし、それによって、ある所望の閾値を越えるPMEPRを与えることなくコードワードの望ましい数を提供するように、コセットを選択することができる。しかし、上で参照した特許出願明細書に記述されたように、それぞれのコセットに関する最大ピーク包絡線電力によって並べられるコセット標本のリストを構築することにより、データ転送レートとPMEPRの間の起こりうるトレードオフを識別することは、特に大規模な計算を必要とする長いコードワードおよび/または一層高い位数のコードの場合に不利である。
【００６６】
(この技法は、組の中のコセットについてPMEPRによる順位付けを与えないが、)この発明は、それぞれのコセット上の最大ピーク包絡線電力を計算することなく、基本コードと結合されて、多くとも既知の値であるPMEPRに関連するコードワードを生成することができるコセット標本の１組を識別する。便宜上、この発明は、以下で２進、４進および８進コード(それぞれq=2、4および8)に関して記述されるが、実現可能なシンボルの数qが偶数である任意のコードに適用することができる。
【００６７】
最初に、この技法を以下のジェネレータ・アレイをもつ長さ16(m=4)の２進コードのケースで説明する。
【００６８】
【数２０】
(0000 0000 1111 1111)            (X1)
(0000 1111 0000 1111)            (X2)
(0011 0011 0011 0011)            (X3)
(0101 0101 0101 0101)            (X4)
(1111 1111 1111 1111)            (X')
(0000 0000 0000 1111)         (X1*X2)
(0000 0000 0011 0011)         (X1*X3)
(0000 0000 0101 0101)         (X1*X4)
(0000 0011 0000 0011)         (X2*X3)
(0000 0101 0000 0101)         (X2*X4)
(0001 0001 0001 0001)         (X3*X4)
【００６９】
コセット標本の組を生成する第１のステップとして、各々が以下の形である８つ(2m-1)の式の最初の組が構築される。
【００７０】
【数２１】
1999163826.tif 000016
【００７１】
上式で、v1、v2およびv3は、0または1の値をもつ係数であり、＋を○で囲んだ記号(以下イメージ表示によらない箇所ではワープロの制約により、◎で表記する)は、ビットに関するモジューロ２加算を示す。従って、最初の組は、以下の通りである。
【００７２】
【数２２】
1999163826.tif 000017
【００７３】
この最初の組は、それぞれの式の中の行識別子X1,X2,X3およびX4の添え字の可能な全ての置換を利用することによって拡張される。従って、例えばπ(1)=2,π(2)=3,π(3)=4,π(4)=1によって規定される置換πを、式(X1*X2)◎(X2*X3)の中の行識別子の添え字に当てはめると、式(X2*X3)◎(X3*X4)が得られる。
【００７４】
最終的な組は、拡張された組の中の異なる式を識別することによって生成される。この目的のため、同じ添え字の対であるが逆の順序である(X1*X2とX2*X1のような)項は、同一であると考えられ、式の中のそのような項の順序付けは、無視される。例えば、π'(1)=4,π'(2)=3,π'(3)=2,π'(4)=1によって規定される置換πを同じ式(X1*X2)◎(X2*X3)に適用すると、式(X4*X3)◎(X3*X2)が得られるが、これは、(X2*X3)◎(X3*X4)と異なるとは考えられない。
【００７５】
必要とされるコセット標本の組を規定する全部で49の式の最終的な組は、表１に与えられており、これは、対応するコセット標本を生成するためにモジューロ２加算される、コードのジェネレータ・アレイのそれぞれの追加の行に対する乗数を構成する6個の係数に関して示される。従って、例えば表題「12」の下の１は、コセット標本の中に包含するために、追加の行(X1*X2)が１で乗算されることを示し、０は、それが０で乗算されることを示す(すなわち有利に省かれる)。
【００７６】
【表１】
1999163826.tif 000018
【００７７】
これらのコセット標本の任意のものを基本コードと結合することによってコードワードが得られるコードは、以下の特性をもつ。
−コードの最小ハミング距離は、4(2m-2)である。
−これらのコードワードに従って変調されるマルチキャリア信号は、わずか6dBのPMEPRをもつ。
−そのようなコードのためのハミング距離に基づく復号器は、解析的手法を使用して演算することができ、例えば組合わせ論理を少なくとも一部で使用して実現することができる。
−許容できるデータ転送レートを達成できるようにする利用可能なコードワードがある。
【００７８】
図8は、10ビットのデータワードを、この発明に従って選択される16ビットのコードワードとして符号化するための10B/16B符号器100を示している。この符号器は、(行係数a1,a2,a3,a4およびa'として処理される)入力データワードの最下位の５ビットに、16ビットの生成マトリクス行X4,X3,X2,X1およびX'のそれぞれを乗じる５つの２進乗算器102ないし110を含む。入力データワードの最上位５ビットは、選択器112に供給され、選択器112は、それらの５ビットの結合された値に従って、可能な32のコセット標本値の１つを選択する。図8に示される例で、表１に挙げられる可能な49個のコセット標本のうちの最初の32個が、選択器112で使用するために(任意に)選ばれている。従って、例えば第１のコセット標本は、追加の行(X1*X2)と(X2*X3)のモジューロ２加算すなわち(0000 0000 0000 1111)◎(0000 0011 0000 0011)=(0000 0011 0000 1100)を含み、５ビット選択器の入力値00000に任意に割り当てられる。入力値11111に任意に割り当てられる選択器112内の最後のコセット標本は、追加の行(X1*X3),(X1*X4),(X2*X4)および(X3*X4)のモジューロ２加算、すなわち(0000 0000 0011 0011)◎(0000 0000 0101 0101)◎(0000 0101 0000 0101)◎(0001 0001 0001 0001)=(0001 0100 0111 0010)を含む。
【００７９】
５つの２進乗算器102ないし110および選択器112の出力は、ビットに関する排他的論理和回路114によって結合され、16ビットのコードワードを生成する。
【００８０】
このコードワードは、受信後、多様な方法で復号することができる。例えばそれは、長さ16、RM(2,4)、２次のReed-Mullerコードの中のコードワードとして処理され、そのようなコードワードのための既知の手法を使用して復号されることができる。あるいは、J.H.ConwayおよびN.J.A.Sloaneによる「Soft decoding techniques for codes and lattices, including the Golay code and the Leech lattice」(IEEE Trans.Inform.Theory,1986年,vol.IT-32,no.1,pp.41-50)に記述される「Supercode」復号方法を使用してもよい。上で参照した特許出願明細書の中に、その他の復号器が記述されている。
【００８１】
m≧3である長さ2mビットの２進コードの一般的なケースで、2m-1の式の最初の組は、以下の形で構築される。
【００８２】
【数２３】
1999163826.tif 000019
【００８３】
上式で、v1,v2,...vm-1は、0または1の値をもつ係数であり、添え字の置換および異なる式の識別が、先に述べたように実施され、(例えば図8に示すものと同様の符号器の選択器内にコセット標本のいくつかまたは全部を取り入れるとにより、)符号化するときに使用することができるコセット標本の１組を規定する。多様なコードワード長について(パラメータmに関して)、このプロシージャによって識別されるコセットの数およびコードワードの総数は、以下の通りである。
【００８４】
【表２】
1999163826.tif 000020
【００８５】
32またはそれ以上のビットのワード長(m≧5)に適用できるこの手法の修正は、異ならない式を見つけて捨てるために式の拡張された組を調べる必要なく、これらのコセットの大きい部分組を識別することを可能にする。言い換えると、この修正される手法は、本質的に異なる式の拡張された組を生成するように保証することができる。このために、
−係数v1,v2,...vm-1の値の組合わせは、形式v1v2v3...vm-2vm-1の２進ワードが、少なくとも４のハミング重みをもつような組合わせに制限される。
−項X1ないしXmの添え字の置換は、添え字m-1が置換される値より小さい値に添え字1が置換される(すなわちπ(1)＜π(m-1))という条件を満足する。
【００８６】
上記で与えられた形であるが、係数の組合わせのこの制限された組をもつ式の最初の組の構築、およびそれぞれの式の中の行識別子の添え字の置換の制限された組の利用は、直接的に、必要とされるコセット標本の部分組を規定する異なる式の最終的な組を与える。基本コードを、この部分組の中の任意のコセット標本と結合することによって生成されるコードワードは、多くとも6dBのPMEPRしかもたない。以下の数のコセット標本が、このプロシージャによって識別される。
【００８７】
【数２４】
1999163826.tif 000021
【００８８】
具体的には、m≧8のとき、少なくともm!・2m-3のコセット標本が、このプロシージャによって識別される。
【００８９】
64ビットまたはそれ以上ののワード長(m≧6)について適用できる代替の修正によって、再び異ならない式を見つけて捨てるために式の拡張された組を調べる必要なく、また置換πについての制約もなく、コセットの一層小さい部分組を識別することができる。このために、係数v1,v2...vm-1の値の組合わせは、v1v2v3...vm-2vm-1の形の２進ワードが次の２つの特性をもつような組合わせに制限される。特性の１つは、それぞれのワードv1v2v3...vm-2vm-1が、少なくとも４のハミング重みをもつことであり、もう１つは、以下の通りである。
【００９０】
【数２５】
1999163826.tif 000022
【００９１】
上記で与えられる形であるが、この制限された係数の組合わせの組をもつ式から最初の組を構築し、それぞれの式の中の行識別子の添え字の可能な全ての置換を利用することによって、必要とされるコセット標本の部分組を規定する異なる式の最終的な組を直接に与える。基本コードをこの部分組の中の任意のコセット標本と結合することによって生成されるコードワードは、多くとも6dBのPMEPRしかもらさない。m≧7のとき、少なくともm!・2m-4のコセット標本が、このプロシージャによって識別される。
【００９２】
同様の手法を使用して、４進コセット、および既知の最大PMEPRをもたらす一層高い位数のコードワードを識別することができる。m≧3で長さ2mの４進コードについて、2m-1個の式の最初の組は、以下の形から構築される。
【００９３】
【数２６】
1999163826.tif 000023
【００９４】
上式で、v1,v2,...vm-1は、0または1の値をもつ係数であり、＋を○で囲んだ記号は、シンボルに関するモジューロ４加算を示す。この最初の組は、それぞれの式の中の行識別子X1,X2,X3,...Xmの添え字の可能な全ての置換を利用することによって拡張される。必要とされるコセット標本の組を規定する式の最終的な組は、２進のケースで上述したように、拡張される組の中の異なる式を識別することによって生成される。コセット標本のこの組の要素は、図8に示されるような符号器の選択器の中で使用することができるが、４進の値を用いた操作のために修正される。従って、コセット標本は、0または2の可能な値をもつシンボルを含む。それぞれの生成マトリクス行X1,X2,X3...XmおよびX'に、(例えば入力２進ワードのそれぞれのビット対の値を表す)４進の値を乗じる。乗算器によって与えられる積は、シンボルに関するモジューロ４加算によって、コセット標本と結合される。
【００９５】
これらコセット標本の任意のものを４進基本コードと結合することによってコードワードが得られる４進コードは、以下の特性をもつ。
−コードの最小ハミング距離は2m-2であり、その最小リー距離は2m-1である。
−これらのコードワードに従って変調されるマルチキャリア信号は、わずか6dBのPMEPRをもつ。
−そのようなコードのために使用する復号器は、解析的手法を使用して演算することができ、例えば組合わせ論理を少なくとも一部に使用して実現することができる。
−許容できるデータ転送レートが達成されるようにするために利用可能なコードワードがある。
【００９６】
多様なコードワード長について(パラメータmに関して)、このプロシージャによって識別されるコセットの数および４進コードワードの総数は、以下の通りである。
【００９７】
【表３】
1999163826.tif 000024
【００９８】
２進のケースのように、32またはそれ以上のシンボルのワード長(m≧5)の場合、異ならない式を見つけて捨てるために式の拡張された組を調べる必要なく、これらのコセットの大きい部分組を識別することができる。これは、２進のケースで上述したのと同様に、係数v1,v2,...vm-1の値および添え字の置換の組合わせを制限することによって達成される。以下に示される数のコセット標本が、このプロシージャによって識別される。
【００９９】
【数２７】
1999163826.tif 000025
【０１００】
具体的には、m≧8のとき、少なくともm!・2m-3のコセット標本が、このプロシージャによって識別される。４進基本コードを、部分組の中の任意のコセット標本と結合することによって生成されるコードワードは、多くとも6dBのPMEPRしかもたらさない。
【０１０１】
64またはそれより多いシンボルのワード長(m≧6)の場合、再び異なる式を見つけて捨てるために式の拡張された組を調べる必要なく、置換πについての制約もなく、コセットの一層小さい部分組を識別することができる。これは、v1v2v3...vm-2vm-1の形の２進ワードが、係数v1,v2,...vm-1の値の組合わせを、上述した２進のケースの代替の修正について指定された２つの特性をもつような組合わせに制限することによって達成される。m≧7の場合、少なくともm!・2m-4の異なるコセット標本が、このプロシージャによって識別され、４進基本コードを部分組の中の任意のコセット標本と結合することによって生成されるコードワードは、多くとも6dBのPMEPRしか与えない。
【０１０２】
m≧3の場合の長さ2mの４進コードワードについて、更なる修正が可能である。その修正は、係数v1,v2,...vm-1に４つの値0,1,2または3のいずれかの値をもたせ、(それぞれの係数の前の２の乗数を用いずに)最初の組の中の式の形を次のように修正することによって実現される。
【０１０３】
【数２８】
1999163826.tif 000026
【０１０４】
この最初の組は、それぞれの式の中の行識別子X1,X2,X3,...Xmの添え字の可能な全ての置換を利用することによって拡張される。必要とされるコセット標本の組を規定する式の最終的な組は、２進のケースで上述したように、拡張された組の中の異なる式を識別することによって生成される。多様なコードワード長について(パラメータmに関する)、この修正を用いて得られるコセットの数および４進コードワードの総数は、次の通りである。
【０１０５】
【表４】
1999163826.tif 000027
【０１０６】
この場合、一層多くのコセットが利用可能であり、従って一層高いデータ転送レートのための潜在能力があることが分かる。４進基本コードを、この修正されたプロシージャによって識別される任意のコセット標本と結合することによって生成されるコードワードは、多くとも6dBのPMEPRしかもたらさない。しかし、この修正の場合の最小リー距離は、2m-2に低減される。
【０１０７】
追加の修正は、行識別子の添え字を置換した後に異なることが保証される式の拡張された組を生成する。追加の修正は、以下によって実現される。
−係数v1,v2,...vm-1の値について、それらの少なくとも２つが０および２以外の値をもつように制限する。
−項X1からXmまでの添え字の置換について、添え字m-1が置換される値よりも小さい値に添え字1が置換されるという条件(すなわちπ(1)＜π(m-1))を満足するように制限する。
【０１０８】
m≧3の場合、少なくともm!・22m-5の異なるコセット標本が、この方法を用いて得られる。
【０１０９】
代替の修正は、係数v1およびvm-1の値をそれぞれ1および3に固定し、他の係数を0ないし3の任意の値にすることにより、行識別子の添え字を置換πについて制約なく置換した後に異なることが保証される式の一層小さい拡張された組を生成する。m≧3の場合、少なくともm!・22m-6の異なるコセット標本が、この方法を用いて得られる。
【０１１０】
m≧3の長さ2mの８進コードの場合、4m-1の式の最初の組は、以下の形式から構築される。
【０１１１】
【数２９】
1999163826.tif 000028
【０１１２】
上式で、v1,v2...vm-1は、0、1、2または3の値をもつ係数であり、＋を○で囲んだ記号は、シンボルに関するモジューロ８加算を示す。この最初の組は、それぞれの式の中の行識別子X1,X2,X3,...Xmの添え字の可能な全ての置換を適用することによって拡張される。必要とされるコセット標本の組を規定する、式の最終的な組は、２進のケースで上述したように、拡張された組の中の異なる式を識別することによって生成される。コセット標本のこの組の要素は、図８に示されるような符号器の選択器内で使用されるが、８進の値を使って演算するために修正することができる。従ってコセット標本は、0、2、4または6の可能な値をもつシンボルを含む。それぞれの生成マトリクス行X1,X2,X3...XmおよびX'に、(例えば入力２進ワードのビットの個々のトリプレットの値を表す)８進の値を乗ずる。乗算器によって与えられる積は、シンボルに関するモジューロ８加算によって、選択されたコセット標本と結合される。
【０１１３】
これらコセット標本を基本コードと結合することによって得られる８進コードワードは、以下の特性をもつ。
−コードの最小ハミング距離は2m-2であり、その最小リー距離は2m-1である。
−これらコードワードに従って変調されるマルチキャリア信号は、わずか6dBのPMEPRしかもたない。
−そのようなコードの使用に供される復号器は、解析的手法を使用して演算することができ、例えば、組合わせ論理を少なくとも一部に使用して実現することができる。
−許容できるデータ転送レートの達成を可能にする利用可能なコードワードがある。一般に、m≧3のとき、このプロシージャは、少なくともm!・22m-5の異なるコセット標本を識別する。
【０１１４】
多様なコードワード長について(パラメータmに関する)、コセットの数および８進コードワードの総数は、以下の通りである。
【０１１５】
【表５】
1999163826.tif 000029
【０１１６】
修正は、以下の制限によって、行識別子の添え字を置換した後に異なることが保証される式の拡張された組を生成する。
−係数v1,v2,...vm-1の値の少なくとも２つが、0および2以外の値をもつように、それら係数の値を制限する。
−添え字m-1が置換される値よりも小さい値に添え字1が置換されるという条件(すなわちπ(1)＜π(m-1))を満足するように、項X1ないしXmの添え字の置換を制限する。
【０１１７】
m≧3の場合、少なくともm!・22m-5の異なるコセット標本が、この方法を用いて得られる。
【０１１８】
代替の修正は、係数v1およびvm-1の値をそれぞれ1および3に固定し、他の係数に0から3までの任意の値をもたせることによって、行識別子の添え字を置換πの制約なく置換した後に異なることが保証される式の拡張された一層小さい組を生成する。m≧3の場合、少なくともm!・22m-6の異なるコセット標本が、この方法を用いて得られる。
【０１１９】
m≧3で長さ2mの８進コードワードについて、別の修正は、係数v1,v2,...vm-1に0ないし7の８つの値の任意の値をもたせ、最初の組の中の式の形を以下のように(すなわちそれぞれの係数の前に２の乗数を用いずに)修正することによって実現することができる。
【０１２０】
【数３０】
1999163826.tif 000030
【０１２１】
この最初の組は、それぞれの式の中の行識別子X1,X2,X3,...Xmの添え字の可能な全ての置換を適用することによって拡張される。必要とされるコセット標本の組を規定する式の最終的な組は、２進のケースで上述したように、拡張された組の中の異なる式を識別することによって生成される。多様なコードワード長について(パラメータmに関して)、この修正によって得られるコセットの数および８進コードワードの総数は、以下の通りである。
【０１２２】
【表６】
1999163826.tif 000031
【０１２３】
この場合一層多くのコセットが利用可能であり、それゆえ一層高いデータ転送レートの潜在能力があることが分かる。８進基本コードを、この修正されたプロシージャによって識別される任意のコセット標本と結合することによって生成されるコードワードは、多くとも6dBのPMEPRしかもたらさない。しかし、この修正による最小リー距離は、2m-2に低減される。
【０１２４】
追加の修正は、以下の制限によって、行識別子の添え字を置換した後に異なることが保証される式の拡張された組を生成する。
−係数v1,v2,...vm-1の値の少なくとも2つが、0および4以外の値をもつように、それら係数の値を制限する。
−添え字m-1が置換される値よりも小さい値に添え字1が置換されるという条件(すなわちπ(1)＜π(m-1))を満たすように、項X1ないしXmの添え字の置換を制限する。
【０１２５】
m≧3の場合、少なくとも18・m!・8m-3の異なるコセット標本が、この方法によって得られる。
【０１２６】
代替の修正は、係数v1およびvm-1の値を、以下の値の順序対の任意の１つになるように選ぶことにより、行識別子の添え字を置換πの制約なく置換した後に異なることが保証される式の拡張された組を生成する。v1の値が、最初に与えらている。
【０１２７】
【数３１】
1,2; 1,3; 1,5; 1,6; 1,7; 2,3; 2,5; 2,6; 2,7; 3,5; 3,6; 3,7; 5,6; 5,7; 6,7
【０１２８】
他の係数は、0から7までの任意の値をもつことができる。m≧3の場合、少なくとも15・m!・8m-3の異なるコセット標本が、この方法によって得られる。
【０１２９】
わずか6dBのPMEPRしかもたらさないコードワードを規定するコセットを識別するためのこれらの技法は、qが偶数である一層高い位数のコードに拡張することができる。最初の組の中の式が以下の形をもつ場合、コードの最小リー距離は2m-2であり、qの任意の偶数の値が使用可能である。
【０１３０】
【数３２】
1999163826.tif 000032
【０１３１】
上式で、v1,v2...vm-1は、0ないしq-1の値をもつ係数であり、＋を○で囲んだ記号は、シンボルに関するモジューロq加算を示す。式が以下の形をもつ場合、コードの最小リー距離は、2m-1に増大されるが、４で割り切れるqの値のみが、使用可能である。
【０１３２】
【数３３】
1999163826.tif 000033
上式で、v1,v2...vm-1は、0から(q/2)-1までの値をもつ係数である。
【０１３３】
より一般的に、コセット標本の大きい組は、m≧3のとき、それぞれのシンボルが実現可能なqの値をもつ2m個のシンボルを含むコードについて識別することができ、そのコードに関するPMEPRは、1≦p≦m-2である任意の固定の整数pについて多くとも2P+1であることが保証される。このために、係数のp組は次のように規定される。
【０１３４】
【数３４】
(v1,1,v1,2,...v1,m-p)
(v2,1,v2,2,...v2,m-p)
...
(vp,1,vp,2,...vp,m-p)
【０１３５】
上式で、それぞれの係数は、0からq-1までの整数値でありうる。1≦i＜j≦pのときの更なるp(p-1)/2の係数wi,jは、それぞれのwi,jが、0からq-1までの整数値をもつことができるところで規定される。係数vi,jおよびwi,jの最初の選択について、式は、以下の形から構築される。
【０１３６】
【数３５】
1999163826.tif 000034
【０１３７】
上式で、＋を○で囲んだ記号は、シンボルに関するモジューロq加算を示す。この形の更なる式は、係数vi,jおよびwi,jの選択の残りの可能な組み合わせについて構築され、qP(m-P)+P(P-1)/2の式の最初の組を得る。この最初の組は、それぞれの式の中の行識別子X1,X2,X3,...Xmの添え字の可能な全ての置換を適用することによって拡張される。必要とされるコセット標本の組を規定する最終的な組は、２進のケースについて上述したように、拡張される組の中の異なる式を識別することによって生成される。位数qの基本コードを、このプロシージャによって識別される任意のコセット標本と結合することによって生成されるコードワードの組は、2m-2の最小リー距離および2m-2の最小ハミング距離もつ。q≧4であって、qが４で割り切れる場合、更なる修正が実現可能であり、その中で、係数vi,jおよびwi,jは、上で指定された範囲の偶数の値をもつように制限される。この場合一層小さいコセットが識別されるが、結果として生ずるコードは、2m-1の最小リー距離をもつ。
【０１３８】
p≦m-4の場合の別の修正は、以下の制限によって、行識別子の添え字を置換した後に異なることが保証される式の拡張された組を生成する。
−次式のように、およびそれぞれのワードvi,1vi,2...vi,m-p-1vi,m-pが少なくとも４のハミング重みをもつように、係数vi,jの値を制限する。
【０１３９】
【数３６】
1999163826.tif 000035
【０１４０】
−係数wi,j(1≦i＜j≦p)が値q/2をもつように制限する。
−添え字m-pが置換される値よりも小さい値に添え字1が置換される(すなわちπ(1)＜π(m-p))という条件を満足するように、項X1ないしXmの添え字の置換を制限する。
【０１４１】
q≧4で、qが４で割り切れる場合、さらに係数vi,jおよびwi,jを、上で指定される範囲内の偶数の値をもつように制限することもできる。この場合、一層少ないコセットが識別されるが、結果として生ずるコードは、2m-1の最小リー距離をもつ。
【０１４２】
４進コードの上記の説明は、0、1、2および3の可能な値をもつ４進シンボルについて記述された。例えば直交位相シフトキーイング(QPSK)変調による実際の伝送の場合、これらの値は、位相シフトの４つの異なる値に対応する。１つの可能性は、0°、90°、180°および270°(i=√-1であるところで、それぞれ複素ベクトル1,i,-1および-iに等しい)の位相シフトである。しかし、位相シフトが、例えば45°、135°,225°および315°(それぞれ複素ベクトル(1+i)/√2,(-1+i)/√2,(-1-i)/√2および(1-i)/√2に等しい)である他の変形も可能である。この原則は、一層多くのシンボル値(q＞4,任意の偶数)をもつコードにも適用され、実際に他のアプリケーションの中で、シンボル値は、任意のq個の識別可能な信号変調によって表すことができる。それらの振幅は、等しい必要はなく、位相シフトキーイングの場合、隣り合う対の間の位相の違いは、全て等しい必要はない。
【０１４３】
上で定められたコードの中のコードワードは、受信された信号を用いて回路操作のタイミングの同期化を確立するための有用な特性も有する。従って、上述したようなこれらのコードを復号するための回路を使用して、受信されたデータの中の同期化シーケンスを識別することもでき、それによって回路の実現の経済性を提供する。またこれらのコードは、ＣＯＦＤＭ以外の手法による通信について有利な特性をもつことも考えられる。従って、例えばそれらは、コード分割多重アクセス(CDMA)方法のためまたはアナログ通信経路上のデジタル・データのモデム伝送のためのコードとして使用することができる。
【０１４４】
本発明は例として次の実施態様を含む。
【０１４５】
（１）符号化直交周波数分割多重化(ＣＯＦＤＭ)方式のようなマルチキャリア周波数分割多重化方式を使用してデータを伝送するために、データワードを、それぞれが実現可能なq個の異なる値(qは１より大きい偶数)を有する2mシンボル(m≧3)のコードワードとして符号化する方法であって、
上記データワードは、上記伝送のピーク対平均値包絡線電力比が、任意の固定の整数p(1≦p≦m-2)について所定の閾値2P+1より大きくならないように、それらの値および、
【数３７】
1999163826.tif 000036
の生成マトリクスをもつコードの線形サブコードのコセットの１つまたは複数の組から完全なコセットの単位で選択されるコードワードに従って符号化され、上式で、zは、0ないし2m-1の整数値であり、yは、mないし0の整数値であり、xは、(m+1)ビット２進数として表される要素のビットに関する乗算を示し、除算の結果は、１ディジットとして表され、
上記コセット組の中のコセットの全てのコセット標本は、
【数３８】
1999163826.tif 000037
の形、または上式から項X1ないしXmの添え字の置換によって導かれる形であり、上式で、X1ないしXmは、上記生成マトリクスの中の最初のm行の行ラベルであり、形式vp,m-p(Xm-p*Xm)の項は、Xm-pおよびXmのような行のシンボルに関する乗算の後、そのワードとvp,m-pのようなそれぞれの係数をシンボルに関してモジューロq乗算することによって導かれる１ワードを示し、＋を○で囲んだ記号は、ワードのシンボルに関するモジューロq加算を示し、係数vi,j(1≦i≦pおよび1≦j≦m-p)および係数wi,j(1≦i＜j≦p)は、0からq-1までの範囲から選択された整数値である方法。
【０１４６】
（２）mは、少なくとも４である、上記(1)に記載の方法。
【０１４７】
（３）上記qは、４で割り切れ、上記係数vi,j(1≦i≦pおよび1≦j≦m-p)および上記係数wi,j(1≦i＜j≦p)は、偶数であるように選択される、上記(1)または(2)に記載の方法。
【０１４８】
（４）p=1であり、上記コセットの組の中のコセットのすべてのコセット標本は、
【数３９】
1999163826.tif 000038
の形である、上記(1)ないし(3)のいずれかに記載の方法。
【０１４９】
（５）q=2である、上記(4)に記載の方法。
【０１５０】
（６）p=1であり、上記コセットの組の中のコセットのすべてのコセット標本は、
【数４０】
1999163826.tif 000039
の形であり、上式で、v1=v1,1/2,v2=v1,2,...,vm-1=v1,m-1/2は、0ないし(q/2)-1の範囲の値をもつ、上記(3)に記載の方法。
【０１５１】
（７）q=4である、上記(6)に記載の方法。
【０１５２】
（８）m≧5であり、
係数v1,v2,...vm-1の値の組合わせは、形式v1v2...vm-2vm-1の２進ワードのそれぞれが、少なくとも４のハミング重みをもつという特性を有するような組合わせに制限され、
項X1ないしXmの添え字の上記置換は、添え字m-1が置換される値よりも小さい値に添え字1が置換されるという条件を満足する、上記(5)または(7)に記載の方法。
【０１５３】
（９）m≧6であり、係数v1,v2,...vm-1の値の組合わせは、形式v1v2...vm-2vm-1の２進ワードが、２つの特性すなわち、
それぞれのワードv1v2...vm-2vm-1は、少なくとも４のハミング重みをもち、
【数４１】
1999163826.tif 000040
であるような組合わせに制限される、上記(5)または(7)に記載の方法。
【０１５４】
（１０）q≧4であり、
係数v1,v2,...vm-1の値の組合わせは、上記係数の少なくとも２つが0およびq/2以外の値をもつような組合わせに制限され、
項X1ないしXmの添え字の上記置換は、添え字m-1が置換される値よりも小さい値に添え字1が置換されるという条件を満たす、上記(4)に記載の方法。
【０１５５】
（１１）q≧4であり、
係数v1,v2...vm-1の値の組合わせは、係数v1およびvm-1のどちらも、0またはq/2の値をもたないような組合わせに制限され、
係数v1は、常に係数vm-1より小さくなるように選ばれる、上記(4)に記載の方法。
【０１５６】
（１２）q≧8であり、
係数v1,v2...vm-1の値の組合わせは、上記係数の少なくとも２つが0およびq/4以外の値をもつような組合わせに制限され、
項X1ないしXmの添え字の上記置換は、添え字m-1が置換される値よりも小さい値に添え字1が置換されるという条件を満たす、上記(6)に記載の方法。
【０１５７】
（１３）q≧8であり、
係数v1,v2,...vm-1の値の組合わせは、係数v1およびvm-1のどちらも0またはq/4の値をもたないような組合わせに制限され、
係数v1は、常に係数vm-1より小さくなるように選ばれる、上記(6)に記載の方法。
【０１５８】
（１４）p≦m-4であり、
【数４２】
1999163826.tif 000041
が成り立ち、
それぞれのワードvi,1vi,2...vi,m-p-1vi,m-pは、少なくとも４のハミング重みをもち、
1≦i＜j≦pである係数wi,jは、値q/2をもち、
項X1ないしXmの添え字の上記置換は、添え字m-pが置換される値よりも小さい値に添え字1が置換されるという条件を満たす、上記(1)、(2)または(3)のいずれかに記載の方法。
【０１５９】
【発明の効果】
本発明によると、マルチキャリア周波数分割多重化方式でデータを伝送するために、PMEPRに関する大規模な計算を必要とすることなく、所定の閾値より小さいPMEPRを与えるコードワードを生成することができる。
【図面の簡単な説明】
【図１】基地局と移動通信装置の間の多重経路伝搬を示す図。
【図２】１つのシンボルの伝搬について多重経路伝搬の影響を示す概略図。
【図３】多重経路伝搬から生じるシンボル間干渉を示す概略図。
【図４】マルチキャリア周波数分割多重化の使用による、シンボル間干渉の低減を示す概略図。
【図５】ＣＯＦＤＭシステム内で使用するための符号器および変調器を示す図。
【図６】図５の符号器および変調器を取り入れたＣＯＦＤＭシステムのブロック概略図。
【図７】PMEPRの制限をもたない、ＣＯＦＤＭ信号波形の一般的な形を示す図。
【図８】10ビットのデータワードを16ビットのコードワードとして符号化するための符号器を示す図。
【符号の説明】
３０      符号器
３２      変調器
３８      IFFT
４２      直列-並列変換器
４４      デジタル-アナログ変換器
５０      アナログ-デジタル変換器
５２      復調器/FFT
５４      復号器
５６      並列-直列変換器
１０２,１０４,１０６,１０８,１１０    乗算器
１１２    選択器