(57)【要約】  本発明は、データの符号化およびデータの復号化のための装置および方法に関する。例えば、本発明は、次元kのデータxを長さnの符号語cに符号化するための符号化装置（102）であって、符号化装置（102）は、式c＝uAに基づいて、C（n，k，d）符号を使用してデータxを符号化するように構成されたプロセッサ（102a）であって、符号C（n，k，d）は、長さnおよび最小距離dを有し、2019525638.tif 000299  であり、mh（h＝1，．．．，s）は整数であり、ただし、2019525638.tif 000300  、0≦ji＜k−1、2019525638.tif 000301（Fは、符号C（n，k，d）のn−k個の凍結ビットインデックスの集合である）である場合、2019525638.tif 000302  であり、i∈Fである場合、2019525638.tif 000303  は、式2019525638.tif 000304  の解によって与えられる制約行列であり、ただし、φiは、列iに最後の非ゼロ要素を有する、行列2019525638.tif 000305  の行のインデックスであり、2019525638.tif 000306  は、プリコーディング行列であり、Aは、2019525638.tif 000307  に基づいて定義される行列であり、2019525638.tif 000308  は、行列Qとそれ自体とのm倍クロネッカー積を表す、プロセッサ（102a）を備える、符号化装置（102）に関する。
2019525638.tif 000002
【特許請求の範囲】
【請求項１】
次元kのデータxを長さnの符号語cに符号化するための符号化装置（102）であって、前記符号化装置（102）は、
以下の式に基づいて、C（n，k，d）符号を使用して前記データxを符号化するように構成されたプロセッサ（102a）であって、前記符号C（n，k，d）は、長さnおよび最小距離dを有し、
【数１】
2019525638.tif 000212
であり、mh（h＝1，．．．，s）は整数であり、
c＝uA
ただし、
【数２】
2019525638.tif 000213
、0≦ji＜k−1、
【数３】
2019525638.tif 000214
（Fは、前記符号C（n，k，d）のn−k個の凍結ビットインデックスの集合である）である場合、
【数４】
2019525638.tif 000215
であり、i∈Fである場合、
【数５】
2019525638.tif 000216
は、以下の式の解によって与えられる制約行列であり、
【数６】
2019525638.tif 000217
ただし、φiは、列iに最後の非ゼロ要素を有する、行列
【数７】
2019525638.tif 000218
の行のインデックスであり、
【数８】
2019525638.tif 000219
は、プリコーディング行列であり、Aは、以下のように定義され、
【数９】
2019525638.tif 000220
ただし、
【数１０】
2019525638.tif 000221
であり、
【数１１】
2019525638.tif 000222
は、行列Qとそれ自体とのm倍クロネッカー積を表す、プロセッサ（102a）
を備える、符号化装置（102）。
【請求項２】
前記プロセッサ（102a）は、複数の入れ子線形ブロック符号
【数１２】
2019525638.tif 000223
に基づいて前記符号C（n，k，d）を構成し、τiは正の整数であり、
【数１３】
2019525638.tif 000224
の生成行列は、以下の式によって与えられ、
【数１４】
2019525638.tif 000225
ただし、G（i，j）は、
【数１５】
2019525638.tif 000226
の行列であり、
【数１６】
2019525638.tif 000227
であり、G（i，j）のプリコーディング行列は、
【数１７】
2019525638.tif 000228
によって定義され、
【数１８】
2019525638.tif 000229
のプリコーディング行列は、
【数１９】
2019525638.tif 000230
によって定義され、行列
【数２０】
2019525638.tif 000231
のp番目の行が始まる列のインデックスli，pは、式
【数２１】
2019525638.tif 000232
によって定義される、ように、および、前記プリコーディング行列
【数２２】
2019525638.tif 000233
をブロック行列として構成し、前記プリコーディング行列
【数２３】
2019525638.tif 000234
のブロックは、前記行列
【数２４】
2019525638.tif 000235
の選択された行からなる、ようにさらに構成される、請求項1に記載の符号化装置（102）。
【請求項３】
前記複数の入れ子線形ブロック符号
【数２５】
2019525638.tif 000236
は、拡張Bose−Chaudhuri−Hocquenghem（e−BCH）符号である、請求項2に記載の符号化装置（102）。
【請求項４】
前記プロセッサ（102a）は、以下のように前記符号C（n，k，d）のプリコーディング行列
【数２６】
2019525638.tif 000237
を構成するようにさらに構成され、
【数２７】
2019525638.tif 000238
ただし、
【数２８】
2019525638.tif 000239
は、少なくともdの最小距離を有する長さ
【数２９】
2019525638.tif 000240
の最大のe−BCH符号のインデックスであり、
【数３０】
2019525638.tif 000241
は、前記行列
【数３１】
2019525638.tif 000242
に基づいて定義される行列である、請求項1から3のいずれか一項に記載の符号化装置（102）。
【請求項５】
前記プロセッサ（102a）は、
【数３２】
2019525638.tif 000243
の最小値を有する前記行列
【数３３】
2019525638.tif 000244
の行によって前記行列
【数３４】
2019525638.tif 000245
を構成し、Pm，iはビットサブチャネルの誤り確率
【数３５】
2019525638.tif 000246
であり、
【数３６】
2019525638.tif 000247
は通信チャネル（110）を介した送信の後の前記符号語cの2m−1のノイズの多いシンボルを表す、ようにさらに構成される、請求項2から4のいずれか一項に記載の符号化装置（102）。
【請求項６】
前記プロセッサ（102a）は、前記行列
【数３７】
2019525638.tif 000248
の最初の複数のt行の最後の非ゼロ要素が、ある整数j0についてj≧j0である異なる位置jに配置されるように前記最初の複数のt行を構成し、擬似乱数発生器によってインデックスz＜jを有する列に配置される前記最初の複数のt行の要素を構成し、行列
【数３８】
2019525638.tif 000249
の第2の複数のn−k−t行を異なる重み1の行として構成するようにさらに構成される、請求項1から5のいずれか一項に記載の符号化装置（102）。
【請求項７】
前記擬似乱数発生器は線形フィードバックシフトレジスタである、請求項6に記載の符号化装置（102）。
【請求項８】
前記プロセッサ（102a）は、前記行列
【数３９】
2019525638.tif 000250
または
【数４０】
2019525638.tif 000251
の行を、それぞれ値li，pおよび値lj，pの昇順に並べ替えるようにさらに構成される、請求項2から7のいずれか一項に記載の符号化装置（102）。
【請求項９】
前記プロセッサ（102a）は、li，pの最小値を有する前記行列
【数４１】
2019525638.tif 000252
のk個の行に基づいて前記行列
【数４２】
2019525638.tif 000253
を構成するように構成される、請求項2から8のいずれか一項に記載の符号化装置（102）。
【請求項１０】
次元kのデータxを長さnの符号語cに符号化するための方法（500）であって、前記方法は、
以下の式に基づいて、C（n，k，d）符号を使用して前記データxを符号化するステップ（502）であって、前記符号C（n，k，d）は、長さnおよび最小距離dを有し、
【数４３】
2019525638.tif 000254
であり、mh（h＝1，．．．，s）は整数であり、
c＝uA
ただし、
【数４４】
2019525638.tif 000255
、0≦ji＜k−1、
【数４５】
2019525638.tif 000256
（Fは、前記符号C（n，k，d）のn−k個の凍結ビットインデックスの集合である）である場合、
【数４６】
2019525638.tif 000257
であり、i∈Fである場合、
【数４７】
2019525638.tif 000258
は、以下の式の解によって与えられる制約行列であり、
【数４８】
2019525638.tif 000259
ただし、φiは、列iに最後の非ゼロ要素を有する、行列
【数４９】
2019525638.tif 000260
の行のインデックスであり、
【数５０】
2019525638.tif 000261
は、プリコーディング行列であり、Aは、以下のように定義され、
【数５１】
2019525638.tif 000262
ただし、
【数５２】
2019525638.tif 000263
であり、
【数５３】
2019525638.tif 000264
は、行列Qとそれ自体とのm倍クロネッカー積を表す、ステップ（502）
を含む、方法（500）。
【請求項１１】
長さnの符号語cを復号化するための復号化装置（104）であって、前記復号化装置（104）は、
C（n，k，d）符号を使用して前記符号語cを復号化するように構成されたプロセッサ（104a）であって、前記符号C（n，k，d）は、長さnおよび最小距離dを有し、
【数５４】
2019525638.tif 000265
であり、mh（h＝1，．．．，s）は整数であり、
c＝uA
であり、ただし、
【数５５】
2019525638.tif 000266
、0≦ji＜k−1、xは、次元kのデータであり、
【数５６】
2019525638.tif 000267
（Fは、前記符号C（n，k，d）のn−k個の凍結ビットインデックスの集合である）である場合、
【数５７】
2019525638.tif 000268
であり、i∈Fである場合、
【数５８】
2019525638.tif 000269
は、以下の式の解によって与えられる制約行列であり、
【数５９】
2019525638.tif 000270
ただし、φiは、列iに最後の非ゼロ要素を有する、行列
【数６０】
2019525638.tif 000271
の行のインデックスであり、
【数６１】
2019525638.tif 000272
は、プリコーディング行列であり、Aは、以下のように定義され、
【数６２】
2019525638.tif 000273
ただし、
【数６３】
2019525638.tif 000274
であり、
【数６４】
2019525638.tif 000275
は、行列Qとそれ自体とのm倍クロネッカー積を表す、プロセッサ（104a）
を備える、復号化装置（104）。
【請求項１２】
前記プロセッサ（104a）は、逐次キャンセルアルゴリズムの一般化によって前記符号語cを復号化するようにさらに構成される、請求項11に記載の復号化装置（104）。
【請求項１３】
前記プロセッサ（104a）は、以下の式によってuを計算し、
i∈Fの場合は
【数６５】
2019525638.tif 000276
および
【数６６】
2019525638.tif 000277
の場合は
【数６７】
2019525638.tif 000278
ただし、φiは、列iに最後の非ゼロ要素を有する、前記行列
【数６８】
2019525638.tif 000279
の行のインデックスであり、
【数６９】
2019525638.tif 000280
は、通信チャネル110を介した前記復号化装置への送信の後の前記符号語cのn個のノイズの多いシンボルを表し、
【数７０】
2019525638.tif 000281
であり、
【数７１】
2019525638.tif 000282
である、ようにさらに構成される、請求項12に記載の復号化装置（104）。
【請求項１４】
前記プロセッサ（104a）は、
【数７２】
2019525638.tif 000283
かつi1＜i2である場合、
【数７３】
2019525638.tif 000284
の前に
【数７４】
2019525638.tif 000285
を計算し、i∈Fである場合、
【数７５】
2019525638.tif 000286
の前に
【数７６】
2019525638.tif 000287
を計算するようにさらに構成される、請求項13に記載の復号化装置（104）。
【請求項１５】
長さnの符号語cを復号化するための方法（600）であって、前記方法は、
C（n，k，d）符号を使用して前記符号語cを復号化するステップ（602）であって、前記符号C（n，k，d）は、長さnおよび最小距離dを有し、
【数７７】
2019525638.tif 000288
であり、mh（h＝1，．．．，s）は整数であり、
c＝uA
であり、ただし、
【数７８】
2019525638.tif 000289
、0≦ji＜k−1、xは、次元kのデータであり、
【数７９】
2019525638.tif 000290
（Fは、前記符号C（n，k，d）のn−k個の凍結ビットインデックスの集合である）である場合、
【数８０】
2019525638.tif 000291
であり、i∈Fである場合、
【数８１】
2019525638.tif 000292
は、以下の式の解によって与えられる制約行列であり、
【数８２】
2019525638.tif 000293
ただし、φiは、列iに最後の非ゼロ要素を有する、行列
【数８３】
2019525638.tif 000294
の行のインデックスであり、
【数８４】
2019525638.tif 000295
は、プリコーディング行列であり、Aは、以下のように定義され、
【数８５】
2019525638.tif 000296
ただし、
【数８６】
2019525638.tif 000297
であり、
【数８７】
2019525638.tif 000298
は、行列Qとそれ自体とのm倍クロネッカー積を表す、ステップ（602）
を含む、方法（600）。
【請求項１６】
コンピュータ上で実行されたときに請求項10に記載の方法（500）および請求項15に記載の方法（600）を実行するためのプログラムコードを含むコンピュータプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
一般に、本発明は、通信システムにおけるデータの符号化および復号化に関する。特に、本発明は、ポーラ符号またはポーラサブ符号に基づく符号を使用したデータの符号化およびデータの復号化のための装置および方法に関する。
【背景技術】
【０００２】
ノイズの多い通信チャネルを介した信頼できるデータ送信には、通常、ある種の誤り訂正符号化を使用することが必要とされる。多くのチャネルのシャノン容量を達成するためのポーラ符号が示されている（E．Arikanの「Channel polarization：A method for constructing capacity achieving codes for symmetric binary−input memoryless channels」（IEEE Trans．on Inf．Theory，vol．55，no．7，pp．3051−3073，July 2009）」参照）。しかしながら、実際のパラメータを用いたポーラ符号のパフォーマンスはしばしば不十分である。
【０００３】
ポーラサブ符号（P．TrifonovおよびV．Miloslavskayaの「Polar subcodes」（IEEE Journal on Selected Areas in Communications，34（2）：254−266，February 2016）参照）は、古典ポーラ符号よりも高い最小距離を有するものとして示されており、リスト、順次、およびブロック順次復号化（I．TalおよびA．Vardyの「List decoding of polar codes」（Proc．IEEE Int．Symp．Inf．Theory，Jul．2011，pp．1−5）ならびにV．MiloslavskayaおよびP．Trifonovの「Sequential decoding of polar codes」（IEEE Commun．Lett．，vol．18，no．7，pp．1127−1130，Jul．2014）参照）の下でかなり良好なパフォーマンスを提供している。しかしながら、ポーラサブ符号のパフォーマンスは依然として改善することができる。
【０００４】
一般に、GF（2）上の（n＝2m，k）ポーラサブ符号Cは、ベクトルc＝xWAmの集合として定義することができ、ただし、Wは、k×nのプリコーディング行列を表し、
【数１】
2019525638.tif 000003
は、ポーラ変換を表し、
【数２】
2019525638.tif 000004
は、行列Qとそれ自体のm倍クロネッカー積を表す。Wの各列が最大で1の重みを持ち、各行が重み1を持つように行列Wを得ることによって、古典ポーラ符号を得ることができる。ポーラサブ符号は、ベクトルcが、十分に高い最小距離を有する（すなわち、HT＝0（Hは親符号の検査行列）である）ある親符号の符号語でもあるようにWを得ることによって得ることができる。例えば、拡張Bose−Chaudhuri−Hocquenghem（BCH：Bose−Chaudhuri−Hocquenghem）が優れた親符号になり得ることが示されている。
【０００５】
ポーラサブ符号を定義する別の同等の方法は、それをベクトルc＝uAの集合と見なすことであり、ただし、uVT＝0であり、Vは（n−k）×nの制約行列であり、このためWVT＝0である。ガウス消去法によって、行列Vは、最大で1つの行が各列で終わるように構成することができる。その後、ポーラ変換Amの入力シンボルuiに対する以下の制約の集合を得ることができる。
【数３】
2019525638.tif 000005
ただし、jiは、Vのi番目の行の最後の非ゼロエントリの位置である。シンボルjiは、動的凍結シンボルとも呼ばれる。これらの動的凍結シンボルは、古典ポーラ符号の構成に使用される（静的）凍結シンボルの概念の一般化と見なすことができる。ポーラサブ符号を構成する標準的な方法は、行列V＝HAT（Hは親符号の検査行列）を構成し、次に、最も高い誤り確率
【数４】
2019525638.tif 000006
を有するシンボルに対して追加の制約
【数５】
2019525638.tif 000007
（静的凍結制約）を導入することであり、ただし、Piは、ポーラ変換Amによって導出される合成ビットサブチャネルのビット誤り確率を表し、遷移確率関数は、以下のように記述することができ、
【数６】
2019525638.tif 000008
ただし、W（y｜c）は、基礎となる2進入力メモリレス出力対称チャネルの遷移確率関数であり、
【数７】
2019525638.tif 000009
である。
【０００６】
ポーラサブ符号を記述するための別の手法は、
【数８】
2019525638.tif 000010
が固定されるかまたは前のシンボルに依存するように凍結ビットインデックスjiの集合Fを定義し、親符号の生成行列Gを考慮することである。その後、行列
【数９】
2019525638.tif 000011
を計算することができ、異なる行が異なる列で始まる（すなわち、最初の非ゼロエントリを有する）ようにするために、この行列にガウス消去法を適用することができ、次に、最も高い
【数１０】
2019525638.tif 000012
（siは、i番目の行が始まる位置）を、得られた行列から消去することができる。
【０００７】
上で説明したすべての手法は、長さ2mの符号を提供する。しかしながら、実際の用途のためには、任意の符号長を有する符号の構成が望まれる。
【０００８】
2mとは異なる長さを有する符号を得るために、いくつかの技術、例えばいわゆる短縮技術およびパンクチャリング技術を適用することができる。短縮技術によれば、C（N，K，D）線形ブロック符号が与えられると、（n＝N−v，k＝K−v，d≧D）短縮符号を、符号Cからベクトルの集合
【数１１】
2019525638.tif 000013
（Sは短縮シンボルの集合を表す）として得ることができる。パンクチャリング技術によれば、（N，K，D）線形ブロック符号Cが与えられると、（n＝N−v，k≦K，d≧D−v）パンクチャード符号を、符号Cからベクトルの集合
【数１２】
2019525638.tif 000014
（Pはパンクチャードシンボルの集合を表す）として得ることができる。一般に、符号の満足のいくパフォーマンスを得るために、パンクチャードシンボルの集合Pおよび短縮シンボルの集合Sは最適化する必要があり、集合PおよびSの選択は、集合Fの最適な選択に影響を及ぼす。集合F、P、およびSを一緒に最適化しなければならないため、符号の構成は非常に複雑になる。さらに、大幅に短縮されたまたはパンクチャリングされた符号は満足のいくパフォーマンスを有さない。
【０００９】
異なる長さの符号を得る別の方法は、連結技術を使用することである。このような技術の例は、N．J．A．Sloaneらによる著作「New binary codes」（IEEE Trans．On Inform．Theory，vol．IT−18，pp．503−510，July 1972）に記載されているいわゆるX4構成によって与えられる。この構成は、C0⊂C1、C2⊂C3、k1−k0＝k3−k2であるような線形符号C0（n0，k0，d0）、C1（n0，k1，d1）、C2（n2，k2，d2）、C3（n2，k3，d3）に基づき、Ciは、生成行列Gi（ただし
【数１３】
2019525638.tif 000015
）を有すると仮定される。このようにして、以下の式によって与えられる生成行列Gを有する（n0＋n2，k0＋k3，min（d0，d2，d1＋d3））符号を得ることができる。
【数１４】
2019525638.tif 000016
連結技術の別の例は、W．Alltopによる著作「A Method for Extending Binary Linear Codes」（IEEE Transactions on Information Theory，30（6），November 1984）に記載されている、Ci（ni，ki，di）（i＝1，．．．，6）符号（ただし、C1＝C2＋C3、C4＝C2∩C3、すなわち
【数１５】
2019525638.tif 000017
、
【数１６】
2019525638.tif 000018
、k5＝k2−k4、k6＝k3−k4）に基づくいわゆるXX構成によって与えられる。これらの符号により、以下の式で与えられる生成行列Gを有する（n1＋n5＋n6，k1，min（d4，d2＋d5，d3＋d6，d1＋d5＋d6））符号を得ることができる
【数１７】
2019525638.tif 000019
しかしながら、連結技術によって得られる符号のパフォーマンスは依然として大幅に改善することができる。
【００１０】
したがって、ポーラ符号またはポーラサブ符号に基づく符号を使用したデータの符号化およびデータの復号化のための改善された装置および方法が必要とされる。
【先行技術文献】
【非特許文献】
【００１１】
【非特許文献１】E．Arikan，“Channel polarization：A method for）constructing capacity achieving codes for symmetric binary−input memoryless channels”，IEEE Trans．on Inf．Theory，vol．55，no．7，pp．3051−3073，July 2009
【非特許文献２】P．Trifonov and V．Miloslavskaya，“Polar subcodes”，IEEE Journal on Selected Areas in Communications，34（2）：254−266，February 2016
【非特許文献３】I．Tal and A．Vardy，“List decoding of polar codes，”in Proc．IEEE Int．Symp．Inf．Theory，Jul．2011，pp．1−5
【非特許文献４】N．J．A．Sloane et al．，“New binary codes，”IEEE Trans．On Inform．Theory，vol．IT−18，pp．503−510，July 1972
【非特許文献５】W．Alltop，“A Method for Extending Binary Linear Codes”，IEEE Transactions on Information Theory，30（6），November 1984
【発明の概要】
【００１２】
本発明の目的は、ポーラ符号またはポーラサブ符号に基づく符号を使用したデータの符号化およびデータの復号化のための改善された装置および方法を提供すること、ならびにこれらの符号を効率的な方法で指定することである。
【００１３】
前述のおよび他の目的は、独立請求項の主題によって達成される。さらなる実施態様の形態は、従属請求項、明細書、および図から明らかになる。
【課題を解決するための手段】
【００１４】
第1の態様によれば、本発明は、次元kのデータxを長さnの符号語cに符号化するための符号化装置に関する。符号化装置は、以下の式に基づいて、C（n，k，d）符号を使用してデータxを符号化するように構成されたプロセッサであって、符号C（n，k，d）は、長さnおよび最小距離dを有し、
【数１８】
2019525638.tif 000020
であり、mh（h＝1，．．．，s）は整数であり、
c＝uA
ただし、
【数１９】
2019525638.tif 000021
、0≦ji＜k−1、
【数２０】
2019525638.tif 000022
（Fは、符号C（n，k，d）のn−k個の凍結ビットインデックスの集合である）である場合、
【数２１】
2019525638.tif 000023
であり、i∈Fである場合、
【数２２】
2019525638.tif 000024
は、以下の式の解によって与えられる制約行列であり、
【数２３】
2019525638.tif 000025
ただし、φiは、列iに最後の非ゼロ要素を有する、行列
【数２４】
2019525638.tif 000026
の行のインデックスであり、
【数２５】
2019525638.tif 000027
は、プリコーディング行列であり、Aは、以下のように定義され、
【数２６】
2019525638.tif 000028
ただし、
【数２７】
2019525638.tif 000029
であり、
【数２８】
2019525638.tif 000030
は、行列Qとそれ自体とのm倍クロネッカー積を表す、プロセッサを備える。
【００１５】
上記のような第1の態様による符号化装置の第1の可能な実施態様の形態では、プロセッサは、複数の入れ子線形ブロック符号
【数２９】
2019525638.tif 000031
に基づいて符号C（n，k，d）を構成し、τiは正の整数であり、
【数３０】
2019525638.tif 000032
の生成行列は、以下の式によって与えられ、
【数３１】
2019525638.tif 000033
ただし、G（i，j）は、
【数３２】
2019525638.tif 000034
の行列であり、
【数３３】
2019525638.tif 000035
であり、G（i，j）のプリコーディング行列は、
【数３４】
2019525638.tif 000036
によって定義され、
【数３５】
2019525638.tif 000037
のプリコーディング行列は、
【数３６】
2019525638.tif 000038
によって定義され、行列
【数３７】
2019525638.tif 000039
のp番目の行が始まる列のインデックスli，pは、式
【数３８】
2019525638.tif 000040
によって定義される、ように、および、プリコーディング行列
【数３９】
2019525638.tif 000041
をブロック行列として構成し、プリコーディング行列
【数４０】
2019525638.tif 000042
のブロックは、行列
【数４１】
2019525638.tif 000043
の選択された行からなる、ようにさらに構成される。
【００１６】
第1の態様の第1の実施態様の形態による符号化装置の第2の可能な実施態様の形態では、複数の入れ子線形ブロック符号
【数４２】
2019525638.tif 000044
は、拡張Bose−Chaudhuri−Hocquenghem（e−BCH：extended Bose−Chaudhuri−Hocquenghem）符号である。
【００１７】
上記のような第1の態様またはその第1〜第2の実施態様の形態のうちのいずれか1つによる符号化装置の第3の可能な実施態様の形態では、プロセッサは、以下のように符号C（n，k，d）のプリコーディング行列
【数４３】
2019525638.tif 000045
を構成するようにさらに構成され、
【数４４】
2019525638.tif 000046
ただし、
【数４５】
2019525638.tif 000047
は、少なくともdの最小距離を有する長さ
【数４６】
2019525638.tif 000048
の最大のe−BCH符号のインデックスであり、
【数４７】
2019525638.tif 000049
は、行列
【数４８】
2019525638.tif 000050
に基づいて定義される行列である。
【００１８】
第1の態様の第1〜第3の実施態様の形態のうちのいずれか1つによる符号化装置の第4の可能な実施態様の形態では、プロセッサは、
【数４９】
2019525638.tif 000051
の最小値を有する行列
【数５０】
2019525638.tif 000052
の行によって行列
【数５１】
2019525638.tif 000053
を構成し、Pm，iはビットサブチャネルの誤り確率
【数５２】
2019525638.tif 000054
であり、
【数５３】
2019525638.tif 000055
は通信チャネルを介した送信の後の符号語cの2m−1のノイズの多いシンボルを表す、ようにさらに構成される。
【００１９】
上記のような第1の態様またはその第1〜第4の実施態様の形態のうちのいずれか1つによる符号化装置の第5の可能な実施態様の形態では、プロセッサは、行列
【数５４】
2019525638.tif 000056
の最初の複数のt行の最後の非ゼロ要素が、ある整数j0についてj≧j0である異なる位置jに配置されるように最初の複数のt行を構成し、整数jの2進展開における非ゼロビットの数がw0に等しく設定され、擬似乱数発生器によってインデックスz＜jを有する列に配置される最初の複数のt行の要素を構成し、行列
【数５５】
2019525638.tif 000057
の第2の複数のn−k−t行を異なる重み1の行として構成するようにさらに構成される。
【００２０】
第1の態様の第5の実施態様の形態による符号化装置の第6の可能な実施態様の形態では、擬似乱数生成器は、線形フィードバックシフトレジスタである。
【００２１】
第1の態様の第1〜第6の実施態様の形態のうちのいずれか1つによる符号化装置の第7の可能な実施態様の形態では、プロセッサは、行列
【数５６】
2019525638.tif 000058
または
【数５７】
2019525638.tif 000059
の行を、それぞれ値li，pおよび値lj，pの昇順に並べ替えるようにさらに構成される。
【００２２】
第1の態様の第1〜第7の実施態様の形態のうちのいずれか1つによる符号化装置の第8の可能な実施態様の形態では、プロセッサは、li，pの最小値を有する行列
【数５８】
2019525638.tif 000060
のk個の行に基づいて行列
【数５９】
2019525638.tif 000061
を構成するように構成される。
【００２３】
第2の態様によれば、本発明は、次元kのデータxを長さnの符号語cに符号化するための方法に関する。本方法は、
以下の式に基づいて、C（n，k，d）符号を使用してデータxを符号化するステップであって、符号C（n，k，d）は、長さnおよび最小距離dを有し、
【数６０】
2019525638.tif 000062
であり、mh（h＝1，．．．，s）は整数であり、
c＝uA
ただし、
【数６１】
2019525638.tif 000063
、0≦ji＜k−1、
【数６２】
2019525638.tif 000064
（Fは、符号C（n，k，d）のn−k個の凍結ビットインデックスの集合である）である場合、
【数６３】
2019525638.tif 000065
であり、i∈Fである場合、
【数６４】
2019525638.tif 000066
は、以下の式の解によって与えられる制約行列であり、
【数６５】
2019525638.tif 000067
ただし、φiは、列iに最後の非ゼロ要素を有する、行列
【数６６】
2019525638.tif 000068
の行のインデックスであり、
【数６７】
2019525638.tif 000069
は、プリコーディング行列であり、Aは、以下のように定義され、
【数６８】
2019525638.tif 000070
ただし、
【数６９】
2019525638.tif 000071
であり、
【数７０】
2019525638.tif 000072
は、行列Qとそれ自体とのm倍クロネッカー積を表す、ステップを含む。
【００２４】
本発明の第2の態様による方法は、本発明の第1の態様による符号化装置によって実行され得る。本発明の第2の態様による方法のさらなる特徴は、本発明の第1の態様およびその異なる実施態様の形態による符号化装置の機能から直接得られる。
【００２５】
第3の態様によれば、本発明は、長さnの符号語cを復号化するための復号化装置に関する。復号化装置は、C（n，k，d）符号を使用して符号語cを復号化するように構成されたプロセッサであって、符号C（n，k，d）は、長さnおよび最小距離dを有し、
【数７１】
2019525638.tif 000073
であり、mh（h＝1，．．．，s）は整数であり、
c＝uA
であり、ただし、
【数７２】
2019525638.tif 000074
、0≦ji＜k−1、xは、次元kのデータであり、
【数７３】
2019525638.tif 000075
（Fは、符号C（n，k，d）のn−k個の凍結ビットインデックスの集合である）である場合、
【数７４】
2019525638.tif 000076
であり、i∈Fである場合、
【数７５】
2019525638.tif 000077
は、以下の式の解によって与えられる制約行列であり、
【数７６】
2019525638.tif 000078
ただし、φiは、列iに最後の非ゼロ要素を有する、行列
【数７７】
2019525638.tif 000079
の行のインデックスであり、
【数７８】
2019525638.tif 000080
は、プリコーディング行列であり、Aは、以下のように定義され、
【数７９】
2019525638.tif 000081
ただし、
【数８０】
2019525638.tif 000082
であり、
【数８１】
2019525638.tif 000083
は、行列Qとそれ自体とのm倍クロネッカー積を表す、プロセッサを備える。
【００２６】
上記のような第3の態様による復号化装置の第1の可能な実施態様の形態では、プロセッサは、逐次キャンセルアルゴリズムの一般化によって符号語cを復号化するようにさらに構成される。
【００２７】
第3の態様の第1の実施態様の形態による復号化装置の第2の可能な実施態様の形態では、プロセッサ、以下の式によってuを計算し、
i∈Fの場合は
【数８２】
2019525638.tif 000084
および
【数８３】
2019525638.tif 000085
の場合は
【数８４】
2019525638.tif 000086
ただし、φiは、列iに最後の非ゼロ要素を有する、行列
【数８５】
2019525638.tif 000087
の行のインデックスであり、
【数８６】
2019525638.tif 000088
は、通信チャネルを介した復号化装置への送信の後の符号語cのn個のノイズの多いシンボルを表し、
【数８７】
2019525638.tif 000089
であり、
【数８８】
2019525638.tif 000090
である、ようにさらに構成される。
【００２８】
第3の態様の第2の実施態様の形態による復号化装置の第3の可能な実施態様の形態では、プロセッサは、
【数８９】
2019525638.tif 000091
かつi1＜i2である場合、
【数９０】
2019525638.tif 000092
の前に
【数９１】
2019525638.tif 000093
を計算し、i∈Fである場合、
【数９２】
2019525638.tif 000094
の前に
【数９３】
2019525638.tif 000095
を計算するようにさらに構成される。
【００２９】
第4の態様によれば、本発明は、長さnの符号語cを復号化するための方法であって、該方法は、
C（n，k，d）符号を使用して符号語cを復号化するステップであって、符号C（n，k，d）は、長さnおよび最小距離dを有し、
【数９４】
2019525638.tif 000096
であり、mh（h＝1，．．．，s）は整数であり、
c＝uA
であり、ただし、ui＝xj、0≦j＜k−1、xは、次元kのデータであり、
【数９５】
2019525638.tif 000097
（Fは、符号C（n，k，d）のn−k個の凍結ビットインデックスの集合である）である場合、
【数９６】
2019525638.tif 000098
であり、i∈Fである場合、
【数９７】
2019525638.tif 000099
は、以下の式の解によって与えられる制約行列であり、
【数９８】
2019525638.tif 000100
ただし、φiは、列iに最後の非ゼロ要素を有する、行列
【数９９】
2019525638.tif 000101
の行のインデックスであり、
【数１００】
2019525638.tif 000102
は、プリコーディング行列であり、Aは、以下のように定義され、
【数１０１】
2019525638.tif 000103
ただし、
【数１０２】
2019525638.tif 000104
であり、
【数１０３】
2019525638.tif 000105
は、行列Qとそれ自体とのm倍クロネッカー積を表す、ステップを含む。
【００３０】
本発明の第4の態様による方法は、本発明の第3の態様による復号化装置によって実行され得る。本発明の第4の態様による方法のさらなる特徴は、本発明の第3の態様およびその異なる実施態様の形態による復号化装置の機能から直接得られる。
【００３１】
第5の態様によれば、本発明は、コンピュータ上で実行されたときに、本発明の第2の態様による方法および本発明の第4の態様による方法を実行するためのプログラムコードを含むコンピュータプログラムに関する。
【００３２】
本発明は、ハードウェアおよび／またはソフトウェアで実施され得る。
【００３３】
本発明のさらなる実施形態は、以下の図に関して説明される。
【図面の簡単な説明】
【００３４】
【図１】一実施形態による符号化装置および一実施形態による復号化装置を備える通信システムを示す概略図を示す。
【図１ａ】一実施形態に従って符号を構成するために使用される拡張BHC符号の4つの例示的な生成行列を示す。
【図１ｂ】一実施形態に従って符号を構成するために使用される拡張BHC符号の3つの例示的な生成行列を示す。
【図１ｃ】一実施形態に従って符号を構成するために使用される拡張BHC符号の生成行列の4つの例示的なプリコーディング行列を示す。
【図１ｄ】一実施形態に従って符号を構成するために使用される拡張BHC符号の生成行列の3つの例示的なプリコーディング行列を示す。
【図１ｅ】一実施形態に従って親符号の例示的なプリコーディング行列を示す。
【図１ｆ】一実施形態に従って符号の例示的なプリコーディング行列を示す。
【図１ｇ】一実施形態に従って符号の例示的な制約行列を示す。
【図２】一実施形態に従って、連鎖ポーラサブ符号に基づく符号に関する符号化装置の構造の概略図を示す。
【図３】一実施形態に従って、信号対ノイズ比（Eb／N0）の関数として異なる符号のフレーム誤り率（FER：frame error rate）をdBで示す。
【図４】一実施形態に従って、信号対ノイズ比（Eb／N0）の関数として異なる符号のフレーム誤り率（FER）をdBで示す。
【図５】一実施形態による、次元kのデータxを長さnの符号語cに符号化するための方法の概略図を示す。
【図６】一実施形態による、長さnの符号語cを復号化するための方法の概略図を示す。
【発明を実施するための形態】
【００３５】
図において、同一の参照符号は、同一のまたは機能的に同等の特徴に対して使用される。
【００３６】
以下の説明では、本開示の一部を形成する添付の図面を参照するが、添付の図面には、本発明が提示され得る特定の態様が例示として示されている。本発明が他の態様で提示され得ること、および本発明の範囲から逸脱することなく構造的または論理的な変更を加えることができることを理解されよう。したがって、以下の詳細な説明は、限定的な意味で解釈されるべきではない。なぜなら、本発明の範囲は、添付の特許請求の範囲によって規定されるからである。
【００３７】
例えば、説明されている方法に関する開示は、一般に、この方法を実行するように構成された対応するデバイスまたはシステムにも当てはまり、その逆もまた同様であることが理解されよう。例えば、特定の方法ステップが説明されている場合、対応するデバイスは、説明されている方法ステップを実行するユニットを、このようなユニットが明示的に説明されていなくてもまたは図に示されていなくても、含み得る。
【００３８】
さらに、以下の詳細な説明および特許請求の範囲では、互いに接続されるまたは信号を交換する機能ブロックまたは処理ユニットを有する実施形態が説明される。本発明は、以下で説明される実施形態の機能ブロックまたは処理ユニットの間に配置される追加の機能ブロックまたは処理ユニットを含む実施形態も含むことが理解されよう。
【００３９】
最後に、特に明記しない限り、本明細書で説明されている様々な例示的な態様の特徴は互いに組み合わせることができることが理解される。
【００４０】
図1は、通信チャネル110を介して通信することができる符号化装置102および復号化装置104を備える通信システム100を示す概略図を示す。
【００４１】
符号化装置102は、プロセッサ102aを備え、データを符号化するように構成される。同様に、復号化装置104は、プロセッサ104aを備え、データ、特に符号化装置102によって符号化されたデータを復号化するように構成される。符号化装置102および／または復号化装置104は、携帯電話またはセルラー通信ネットワークの基地局などの通信デバイスの一部として実施され得る。
【００４２】
一実施形態では、プロセッサ102aは、以下の式に基づいて、C（n，k，d）符号を使用して次元kのデータxを長さnの符号語cに符号化するように構成され、ただし、符号C（n，k，d）は、長さnおよび最小距離dを有し、
【数１０４】
2019525638.tif 000106
であり、mhが＞mh＋1であり（h＝1，．．．，s）、かつ整数である。
c＝uA
ただし、
【数１０５】
2019525638.tif 000107
、0≦ji＜k−1、
【数１０６】
2019525638.tif 000108
（Fは、符号C（n，k，d）のn−k個の凍結ビットインデックスの集合である）である場合、
【数１０７】
2019525638.tif 000109
であり、i∈Fである場合、
【数１０８】
2019525638.tif 000110
は制約行列である。
【００４３】
制約行列
【数１０９】
2019525638.tif 000111
は、以下の式の解によって与えられる。
【数１１０】
2019525638.tif 000112
ただし、φiは、列iに最後の非ゼロ要素を有する、行列
【数１１１】
2019525638.tif 000113
の行のインデックスであり、
【数１１２】
2019525638.tif 000114
は、プリコーディング行列であり、Aは、以下のように定義される。
【数１１３】
2019525638.tif 000115
ただし、
【数１１４】
2019525638.tif 000116
であり、
【数１１５】
2019525638.tif 000117
は、行列Qとそれ自体とのm倍クロネッカー積を表す。
【００４４】
一実施形態では、プロセッサ102aと同様に、復号化装置104のプロセッサ104aは、C（n，k，d）符号を使用して符号語cを復号化するように構成され、符号C（n，k，d）は、長さnおよび最小距離dを有し、
【数１１６】
2019525638.tif 000118
であり、mhが＞mh＋1であり（h＝1，．．．，s）、かつ整数であり、
c＝uA
であり、ただし、ui＝xj、0≦j＜k−1、xは、次元kのデータであり、
【数１１７】
2019525638.tif 000119
（Fは、符号C（n，k，d）のn−k個の凍結ビットインデックスの集合である）である場合、
【数１１８】
2019525638.tif 000120
であり、i∈Fである場合、
【数１１９】
2019525638.tif 000121
は、以下の式の解によって与えられる制約行列である。
【数１２０】
2019525638.tif 000122
ただし、φiは、列iに最後の非ゼロ要素を有する、行列
【数１２１】
2019525638.tif 000123
の行のインデックスであり、
【数１２２】
2019525638.tif 000124
は、プリコーディング行列であり、Aは、以下のように定義される。
【数１２３】
2019525638.tif 000125
ただし、
【数１２４】
2019525638.tif 000126
であり、
【数１２５】
2019525638.tif 000127
は、行列Qとそれ自体とのm倍クロネッカー積を表す。
【００４５】
通信チャネル110は、有線または無線の通信チャネルとすることができる。
【００４６】
一実施形態では、プロセッサ102aは、以下のステップに基づいて制約行列
【数１２６】
2019525638.tif 000128
を生成するように構成され得る。
第1のステップ：入れ子の拡張プリミティブ狭義BCH符号
【数１２７】
2019525638.tif 000129
（0≦j＜τi）の生成行列
【数１２８】
2019525638.tif 000130
を構成する、ただし、G（i，j）は、
【数１２９】
2019525638.tif 000131
の行列（
【数１３０】
2019525638.tif 000132
）であり、以下のようにG（i，j）の対応するプリコーディング行列を定義する。
【数１３１】
2019525638.tif 000133
および
【数１３２】
2019525638.tif 000134
ただし、行列
【数１３３】
2019525638.tif 000135
のp番目の行が始まる列のインデックスは、以下によって定義される。
【数１３４】
2019525638.tif 000136
【００４７】
一実施形態では、任意のiについて、すべてのli，pは異なり、一般に、整数τiは、次数Mの既約多項式の数に等しく、Mは、miの約数を表すと仮定され得る。
【００４８】
第2のステップ：行列
【数１３５】
2019525638.tif 000137
の入れ子構造を保ちながら、すべての行が異なる列で始まるようにするために、基本行操作を
【数１３６】
2019525638.tif 000138
に適用する。
【００４９】
第3のステップ：行列
【数１３７】
2019525638.tif 000139
の行を選択し、それらをプリコーディング行列
【数１３８】
2019525638.tif 000140
のi番目の列に入れる、ただし、プリコーディング行列
【数１３９】
2019525638.tif 000141
はブロック行列である。
【００５０】
第4のステップ：行列
【数１４０】
2019525638.tif 000142
（あるε＞0について）の行を選択し、それらをプリコーディング行列
【数１４１】
2019525638.tif 000143
のi番目の列に入れる。このような行ごとに、前のステップで選択されていない行列
【数１４２】
2019525638.tif 000144
の行を選択し、それを列i’の行列
【数１４３】
2019525638.tif 000145
の同じ行に入れる。要約すると、構成されたプリコーディング行列
【数１４４】
2019525638.tif 000146
は、以下によって与えられる。
【数１４５】
2019525638.tif 000147
ただし、
【数１４６】
2019525638.tif 000148
は、最小距離dを有する長さ
【数１４７】
2019525638.tif 000149
の最大のe−BCH符号のインデックスであり、
【数１４８】
2019525638.tif 000150
は、次に大きいe−BCH符号の最小距離差である。行列
【数１４９】
2019525638.tif 000151
は、行列
【数１５０】
2019525638.tif 000152
（ただし、
【数１５１】
2019525638.tif 000153
）のいくつかの行およびゼロ行からなり、このため、任意のsについて、非ゼロ行を有する最大で1つのブロックi
【数１５２】
2019525638.tif 000154
がある。
【００５１】
第5のステップ：最小の
【数１５３】
2019525638.tif 000155
を有するブロックiの列li，pから始まる行列
【数１５４】
2019525638.tif 000156
のk個の行を保持する、ただし、Pm，iは、ビットサブチャネルの誤り確率
【数１５５】
2019525638.tif 000157
であり、
【数１５６】
2019525638.tif 000158
は、通信チャネル110を介した送信後の符号語cの2m−1個のノイズの多いシンボルを表す。
【数１５７】
2019525638.tif 000159
を得られた行列とする。
【００５２】
第6のステップ：
【数１５８】
2019525638.tif 000160
を得て、
【数１５９】
2019525638.tif 000161
の行が異なる列ji（0≦i＜n−k）で終わるようにするためにガウス消去法を使用し、（動的）凍結ビットインデックスの集合をF＝｛ji，0≦i＜n−k｝と定義する。
【００５３】
制約行列
【数１６０】
2019525638.tif 000162
を生成するための上で説明したステップについて説明するために、連鎖ポーラサブ符号に基づく例示的な（24，11，6）符号の構成が検討される。この場合、符号は、次元n＝24を有し、これは24＝24＋23と書くこともできるため、m0＝4、m1＝3となる。図1aおよび図1bには、対応する拡張BCH符号Cijの入れ子の生成行列G（i，j）（i＝0、1およびj＝1、2、3）が示されており、d0，0＝16、d0，1＝8、d0，2＝6、d0，3＝4、d1，0＝8、d1，1＝4、d1，2＝2である。図1aおよび図1bに示す行列G（i，j）と行列
【数１６１】
2019525638.tif 000163
とを乗算し、基本行操作を適用することによって、図1cおよび図1dに示すように、対応するプリコーディング行列W（i，j）を得ることができる。プリコーディング行列W（i，j）とε＝2とを組み合わせることで、図1eに示すように、親符号のプリコーディング行列
【数１６２】
2019525638.tif 000164
を得ることができる。消去確率0．5を有する2進消去チャネルの場合、ビットサブチャネルの誤り確率は、例えば、
0．499、0．496、0．492、0．386、0．48、0．32、0．26、0．5e−1、0．44、0．23、0．17、0．18e−1、0．11、0．7e−2、0．38e−2、0．76e−5、0．498、0．44、0．40、0．15、0．34、0．09、0．06、0．0019である。
【００５４】
行列
【数１６３】
2019525638.tif 000165
の6番目の行は、列3から始まり、これは、最も高い誤り確率0．386を有するサブチャネルに対応するため、それは除去され得る。したがって、図1fに示すように、連鎖ポーラサブ符号に基づく（24，11，6）符号に関するプリコーディング行列
【数１６４】
2019525638.tif 000166
を得ることができる。最後に、図1gに示すように、対応する制約行列
【数１６５】
2019525638.tif 000167
を得ることができる。
【００５５】
別の実施形態では、プロセッサ102aは、以下のステップに従って、（n−k）×nの行列
【数１６６】
2019525638.tif 000168
を構成するように構成され得る。
第1のステップ：
【数１６７】
2019525638.tif 000169
の行を、最も高い
【数１６８】
2019525638.tif 000170
を有するブロックiの列li，pに1を含む、重み1の異なるベクトルに設定する。
第2のステップ：
【数１６９】
2019525638.tif 000171
の最後のρ行のそれぞれについて、最大で2つのブロックiの列j＜li，pに任意の2進値を入れる。
【００５６】
一実施形態では、この2進値は、線形フィードバックシフトレジスタなどの擬似乱数発生器（PRNG：pseudo−random number generator）によって得ることができる。これには、PRNGのパラメータおよびシード値だけを与えることで符号をコンパクトに指定することができるという利点がある。さらに、上で言及したステップに従って構成された行列
【数１７０】
2019525638.tif 000172
には、高パフォーマンスを有する連鎖ポーラサブ符号を提供するという利点がある。
【００５７】
行列
【数１７１】
2019525638.tif 000173
および
【数１７２】
2019525638.tif 000174
が利用可能になったら、別の実施形態では、プロセッサ102aは、以下の式に従って次元kのデータxを符号語cに符号化するようにさらに構成され得る。
【数１７３】
2019525638.tif 000175
【００５８】
さらに、符号語cが符号化されたら、それは、通信チャネル110を介して復号化装置104に送信され得る。しかしながら、通信チャネル110を介した送信の後、符号語cのn個のシンボルは、ノイズの影響を受け、ノイズの多いシンボル
【数１７４】
2019525638.tif 000176
をもたらす。したがって、符号語cの正しいシンボルを復元するための方法が必要とされる。
【００５９】
一実施形態では、復号化装置104のプロセッサ104aは、以下の式に基づいて、一般化された逐次キャンセルアルゴリズムおよびそのリストまたは順次拡張を使用して符号語cを復元するように構成され得る。
【数１７５】
2019525638.tif 000177
および
【数１７６】
2019525638.tif 000178
ただし、
【数１７７】
2019525638.tif 000179
および
【数１７８】
2019525638.tif 000180
。
【００６０】
この復号化方法はまた、TalおよびVardyならびにMiloslavskayaおよびTrifonovによる先に言及した著作に提示されたものと同様の、リストおよび順次逐次キャンセル方法を得るように拡張されてもよい。
【００６１】
一実施形態では、シンボル
【数１７９】
2019525638.tif 000181
を得る順序は、以下の規則に基づいて並べ替えられ得る。
a．
【数１８０】
2019525638.tif 000182
かつi1＜i2の場合、
【数１８１】
2019525638.tif 000183
の前に
【数１８２】
2019525638.tif 000184
が計算される。
b．i∈Fの場合、
【数１８３】
2019525638.tif 000185
の前に
【数１８４】
2019525638.tif 000186
が計算される。
【００６２】
シンボル
【数１８５】
2019525638.tif 000187
の検出順序を並べ替えることには、これによりリストおよび順次逐次キャンセルアルゴリズムのパフォーマンスが改善され得るという利点がある。
【００６３】
図2は、一実施形態に従って、連鎖ポーラサブ符号に基づく符号に関する符号化装置102の構造の概略図を示す。この実施形態では、符号は長さn＝12＝23＋22を有し、それは2つのポーラ変換、すなわち、
【数１８６】
2019525638.tif 000188
（m1＝3、サイズ8の（ポーラ変換1））および
【数１８７】
2019525638.tif 000189
（m2＝2、サイズ4の（ポーラ変換2））を含む。符号化されるべき次元4のデータxは、シンボルu3、u5、u7、u9にマッピングされる4つのシンボルx0、x1、x2、x3によって表されている。凍結ビットシンボルの集合は、u0、u1、u2、u4、u6、u8、u10、u11によって表されている。一実施形態では、符号化装置102のプロセッサ102aは、図2に示すように、対応するポーラ変換の他の入力シンボルのいくつかの線形結合の関数としてシンボルu6およびu10を計算するように構成され得る。さらに、プロセッサ102aは、ポーラ変換1の入力シンボルの関数としてポーラ変換2の入力シンボルu11を計算するように構成され得る。さらに、凍結およびクロス符号化制約の構造は、得られた符号が十分に高い最小距離を有し、逐次キャンセルアルゴリズムの可能な一般化または修正によって効率的な方法で復号化され得るように実現され得る。
【００６４】
図3は、一実施形態に従って、信号対ノイズ比（Eb／N0）の関数として異なる符号のフレーム誤り率（FER）をdBで示す。図3に示されているように、順次復号化アルゴリズムにおける連鎖ポーラサブ符号に基づく符号のパフォーマンスは、短縮ポーラサブ符号、ターボ符号、および畳み込みLTEテールビット符号のパフォーマンスと比較して著しく改善され得る。特に、連鎖ポーラサブ符号に基づく符号は、短縮ポーラサブ符号と比較して、最大で0．3〜0．7dBの電力利得をもたらすことができる。
【００６５】
図4は、一実施形態に従って、信号対ノイズ比（Eb／N0）の関数として異なる符号のフレーム誤り率（FER）をdBで示す。図3と同様に、この場合も、連鎖ポーラサブ符号に基づく符号のパフォーマンスは、短縮ポーラサブ符号およびターボ符号のパフォーマンスと比較して著しく改善されている。
【００６６】
図5は、一実施形態による、次元kのデータxを長さnの符号語cに符号化するための方法500の概略図を示す。方法500は、
以下の式に基づいて、C（n，k，d）符号を使用してデータxを符号化するステップ502であって、符号C（n，k，d）は、長さnおよび最小距離dを有し、
【数１８８】
2019525638.tif 000190
であり、mh（h＝1，．．．，s）は整数であり、
c＝uA
ただし、
【数１８９】
2019525638.tif 000191
、0≦ji＜k−1、
【数１９０】
2019525638.tif 000192
（Fは、符号C（n，k，d）のn−k個の凍結ビットインデックスの集合である）である場合、
【数１９１】
2019525638.tif 000193
であり、i∈Fである場合、
【数１９２】
2019525638.tif 000194
は、以下の式の解によって与えられる制約行列であり、
【数１９３】
2019525638.tif 000195
ただし、φiは、列iに最後の非ゼロ要素を有する、行列
【数１９４】
2019525638.tif 000196
の行のインデックスであり、
【数１９５】
2019525638.tif 000197
は、プリコーディング行列であり、Aは、以下のように定義され、
【数１９６】
2019525638.tif 000198
ただし、
【数１９７】
2019525638.tif 000199
であり、
【数１９８】
2019525638.tif 000200
は、行列Qとそれ自体とのm倍クロネッカー積を表す、ステップ502
を含む。
【００６７】
図6は、一実施形態による、長さnの符号語cを復号化するための方法600の概略図を示す。方法600は、
C（n，k，d）符号を使用して符号語cを復号化するステップ602であって、符号C（n，k，d）は、長さnおよび最小距離dを有し、
【数１９９】
2019525638.tif 000201
であり、mh（h＝1，．．．，s）は整数であり、
c＝uA
であり、ただし、
【数２００】
2019525638.tif 000202
、0≦ji＜k−1、xは、次元kのデータであり、
【数２０１】
2019525638.tif 000203
（Fは、符号C（n，k，d）のn−k個の凍結ビットインデックスの集合である）である場合、
【数２０２】
2019525638.tif 000204
であり、i∈Fである場合、
【数２０３】
2019525638.tif 000205
は、以下の式の解によって与えられる制約行列であり、
【数２０４】
2019525638.tif 000206
ただし、φiは、列iに最後の非ゼロ要素を有する、行列
【数２０５】
2019525638.tif 000207
の行のインデックスであり、
【数２０６】
2019525638.tif 000208
は、プリコーディング行列であり、Aは、以下のように定義され、
【数２０７】
2019525638.tif 000209
ただし、
【数２０８】
2019525638.tif 000210
であり、
【数２０９】
2019525638.tif 000211
は、行列Qとそれ自体とのm倍クロネッカー積を表す、ステップ602
を含む。
【００６８】
本開示の特定の特徴または態様は、いくつかの実施態様または実施形態のうちの1つのみに関して開示されているが、このような特徴または態様は、所与のまたは特定の用途にとって望ましく好適となり得るように、他の実施態様または実施形態の1つ以上の他の特徴または態様と組み合わされてもよい。さらに、用語「含む」、「有する」、「伴う」、またはこれらの他の変種が発明を実施するための形態または特許請求の範囲のいずれかで使用される限りにおいて、このような用語は、用語「備える」と同様に包括的であることを意図されている。また、用語「例示的」、「例えば（for example）」、および「例えば（e．g．）」は、最良または最適なものとしてではなく、単に例として意図されている。派生語と共に用語「結合された」および「接続された」が使用されている場合がある。これらの用語は、2つの要素が、物理的または電気的に直接接触しているかどうかにかかわらず、または互いに直接接触していないにもかかわらず、互いに協働または相互作用することを示すために使用されている場合があることを理解されたい。
【００６９】
本明細書では特定の態様を示し説明したが、本開示の範囲から逸脱することなく、様々な代替および／または同等の実施態様が、図示および説明した特定の態様の代わりになり得ることが、当業者によって理解される。本出願は、本明細書に述べられている特定の態様の適合例または変形例を含むことを意図されている。
【００７０】
以下の特許請求の範囲の要素は、対応するラベルを付けて特定の順序で記載されているが、特許請求の範囲の記載が、これらの要素のいくつかまたはすべてを実施するために特定の順序を含意していない限り、これらの要素が特定の順序で実施されることに必ずしも限定されると意図されてはいない。
【００７１】
上記の教示を踏まえれば、多くの代替例、修正例、および変形例が当業者に明らかとなる。言うまでもなく、当業者であれば、本明細書で説明された用途以外にも本発明の多くの用途があることを容易に認めるであろう。本発明について、1つ以上の特定の実施形態を参照して説明したが、当業者であれば、本発明の範囲から逸脱することなくそれに多くの変更を加えることができることを理解するであろう。したがって、添付の特許請求の範囲およびその均等物の範囲内で、本明細書で具体的に説明されているのとは別の方法で本発明を実施することができることを理解されたい。
【符号の説明】
【００７２】
100  通信システム
102  符号化装置
102a、104a  プロセッサ
104  復号化装置
110  通信チャネル
【図１】
2019525638.tif 000309
【図１ａ】
2019525638.tif 000310
【図１ｂ】
2019525638.tif 000311
【図１ｃ】
2019525638.tif 000312
【図１ｄ】
2019525638.tif 000313
【図１ｅ】
2019525638.tif 000314
【図１ｆ】
2019525638.tif 000315
【図１ｇ】
2019525638.tif 000316
【図２】
2019525638.tif 000317
【図３】
2019525638.tif 000318
【図４】
2019525638.tif 000319
【図５】
2019525638.tif 000320
【図６】
2019525638.tif 000321
【手続補正書】
【提出日】平成31年3月19日(2019.3.19)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
次元kのデータxを長さnの符号語cに符号化するための符号化装置（102）であって、前記符号化装置（102）は、
以下の式に基づいて、C（n，k，d）符号を使用して前記データxを符号化するように構成されたプロセッサ（102a）であって、前記符号C（n，k，d）は、長さnおよび最小距離dを有し、
【数１】
2019525638.tif 000322
であり、mh（h＝1，．．．，s）は整数であり、
c＝uA
ただし、
【数２】
2019525638.tif 000323
、0≦ji＜k−1、
【数３】
2019525638.tif 000324
（Fは、前記符号C（n，k，d）のn−k個の凍結ビットインデックスの集合である）である場合、
【数４】
2019525638.tif 000325
であり、i∈Fである場合、
【数５】
2019525638.tif 000326
は、以下の式の解によって与えられる制約行列であり、
【数６】
2019525638.tif 000327
ただし、φiは、列iに最後の非ゼロ要素を有する、行列
【数７】
2019525638.tif 000328
の行のインデックスであり、
【数８】
2019525638.tif 000329
は、プリコーディング行列であり、Aは、以下のように定義され、
【数９】
2019525638.tif 000330
ただし、
【数１０】
2019525638.tif 000331
であり、
【数１１】
2019525638.tif 000332
は、行列Qとそれ自体とのm倍クロネッカー積を表す、プロセッサ（102a）
を備える、符号化装置（102）。
【請求項２】
前記プロセッサ（102a）は、複数の入れ子線形ブロック符号
【数１２】
2019525638.tif 000333
に基づいて前記符号C（n，k，d）を構成し、τiは正の整数であり、
【数１３】
2019525638.tif 000334
の生成行列は、以下の式によって与えられ、
【数１４】
2019525638.tif 000335
ただし、G（i，j）は、
【数１５】
2019525638.tif 000336
の行列であり、
【数１６】
2019525638.tif 000337
であり、G（i，j）のプリコーディング行列は、
【数１７】
2019525638.tif 000338
によって定義され、
【数１８】
2019525638.tif 000339
のプリコーディング行列は、
【数１９】
2019525638.tif 000340
によって定義され、行列
【数２０】
2019525638.tif 000341
のp番目の行が始まる列のインデックスli，pは、式
【数２１】
2019525638.tif 000342
によって定義される、ように、および、前記プリコーディング行列
【数２２】
2019525638.tif 000343
をブロック行列として構成し、前記プリコーディング行列
【数２３】
2019525638.tif 000344
のブロックは、前記行列
【数２４】
2019525638.tif 000345
の選択された行からなる、ようにさらに構成される、請求項1に記載の符号化装置（102）。
【請求項３】
前記複数の入れ子線形ブロック符号
【数２５】
2019525638.tif 000346
は、拡張Bose−Chaudhuri−Hocquenghem（e−BCH）符号である、請求項2に記載の符号化装置（102）。
【請求項４】
前記プロセッサ（102a）は、以下のように前記符号C（n，k，d）のプリコーディング行列
【数２６】
2019525638.tif 000347
を構成するようにさらに構成され、
【数２７】
2019525638.tif 000348
ただし、
【数２８】
2019525638.tif 000349
は、少なくともdの最小距離を有する長さ
【数２９】
2019525638.tif 000350
の最大のe−BCH符号のインデックスであり、
【数３０】
2019525638.tif 000351
は、前記行列
【数３１】
2019525638.tif 000352
に基づいて定義される行列である、請求項1に記載の符号化装置（102）。
【請求項５】
前記プロセッサ（102a）は、
【数３２】
2019525638.tif 000353
の最小値を有する前記行列
【数３３】
2019525638.tif 000354
の行によって前記行列
【数３４】
2019525638.tif 000355
を構成し、Pm，iはビットサブチャネルの誤り確率
【数３５】
2019525638.tif 000356
であり、
【数３６】
2019525638.tif 000357
は通信チャネル（110）を介した送信の後の前記符号語cの2m−1のノイズの多いシンボルを表す、ようにさらに構成される、請求項2から4のいずれか一項に記載の符号化装置（102）。
【請求項６】
前記プロセッサ（102a）は、前記行列
【数３７】
2019525638.tif 000358
の最初の複数のt行の最後の非ゼロ要素が、ある整数j0についてj≧j0である異なる位置jに配置されるように前記最初の複数のt行を構成し、擬似乱数発生器によってインデックスz＜jを有する列に配置される前記最初の複数のt行の要素を構成し、行列
【数３８】
2019525638.tif 000359
の第2の複数のn−k−t行を異なる重み1の行として構成するようにさらに構成される、請求項1に記載の符号化装置（102）。
【請求項７】
前記擬似乱数発生器は線形フィードバックシフトレジスタである、請求項6に記載の符号化装置（102）。
【請求項８】
前記プロセッサ（102a）は、前記行列
【数３９】
2019525638.tif 000360
または
【数４０】
2019525638.tif 000361
の行を、それぞれ値li，pおよび値lj，pの昇順に並べ替えるようにさらに構成される、請求項2から7のいずれか一項に記載の符号化装置（102）。
【請求項９】
前記プロセッサ（102a）は、li，pの最小値を有する前記行列
【数４１】
2019525638.tif 000362
のk個の行に基づいて前記行列
【数４２】
2019525638.tif 000363
を構成するように構成される、請求項2から8のいずれか一項に記載の符号化装置（102）。
【請求項１０】
次元kのデータxを長さnの符号語cに符号化するための方法（500）であって、前記方法は、
以下の式に基づいて、C（n，k，d）符号を使用して前記データxを符号化するステップ（502）であって、前記符号C（n，k，d）は、長さnおよび最小距離dを有し、
【数４３】
2019525638.tif 000364
であり、mh（h＝1，．．．，s）は整数であり、
c＝uA
ただし、
【数４４】
2019525638.tif 000365
、0≦ji＜k−1、
【数４５】
2019525638.tif 000366
（Fは、前記符号C（n，k，d）のn−k個の凍結ビットインデックスの集合である）である場合、
【数４６】
2019525638.tif 000367
であり、i∈Fである場合、
【数４７】
2019525638.tif 000368
は、以下の式の解によって与えられる制約行列であり、
【数４８】
2019525638.tif 000369
ただし、φiは、列iに最後の非ゼロ要素を有する、行列
【数４９】
2019525638.tif 000370
の行のインデックスであり、
【数５０】
2019525638.tif 000371
は、プリコーディング行列であり、Aは、以下のように定義され、
【数５１】
2019525638.tif 000372
ただし、
【数５２】
2019525638.tif 000373
であり、
【数５３】
2019525638.tif 000374
は、行列Qとそれ自体とのm倍クロネッカー積を表す、ステップ（502）
を含む、方法（500）。
【請求項１１】
複数の入れ子線形ブロック符号
【数５４】
2019525638.tif 000375
に基づいて前記符号C（n，k，d）を構成するステップであって、τiは正の整数であり、
【数５５】
2019525638.tif 000376
の生成行列は、以下の式によって与えられ、
【数５６】
2019525638.tif 000377
ただし、G（i，j）は、
【数５７】
2019525638.tif 000378
の行列であり、
【数５８】
2019525638.tif 000379
であり、G（i，j）のプリコーディング行列は、
【数５９】
2019525638.tif 000380
によって定義され、
【数６０】
2019525638.tif 000381
のプリコーディング行列は、
【数６１】
2019525638.tif 000382
によって定義され、行列
【数６２】
2019525638.tif 000383
のp番目の行が始まる列のインデックスli，pは、式
【数６３】
2019525638.tif 000384
によって定義される、ステップと、前記プリコーディング行列
【数６４】
2019525638.tif 000385
をブロック行列として構成するステップであって、前記プリコーディング行列
【数６５】
2019525638.tif 000386
のブロックは、前記行列
【数６６】
2019525638.tif 000387
の選択された行からなる、ステップと
を含む、請求項10に記載の方法（500）。
【請求項１２】
前記複数の入れ子線形ブロック符号
【数６７】
2019525638.tif 000388
は、拡張Bose−Chaudhuri−Hocquenghem（e−BCH）符号である、請求項11に記載の方法（500）。
【請求項１３】
以下のように前記符号C（n，k，d）のプリコーディング行列
【数６８】
2019525638.tif 000389
を構成するステップであって、
【数６９】
2019525638.tif 000390
ただし、
【数７０】
2019525638.tif 000391
は、少なくともdの最小距離を有する長さ
【数７１】
2019525638.tif 000392
の最大のe−BCH符号のインデックスであり、
【数７２】
2019525638.tif 000393
は、前記行列
【数７３】
2019525638.tif 000394
に基づいて定義される行列である、ステップ
を含む、請求項10に記載の方法（500）。
【請求項１４】
【数７４】
2019525638.tif 000395
の最小値を有する前記行列
【数７５】
2019525638.tif 000396
の行によって前記行列
【数７６】
2019525638.tif 000397
を構成するステップであって、Pm，iはビットサブチャネルの誤り確率
【数７７】
2019525638.tif 000398
であり、
【数７８】
2019525638.tif 000399
は通信チャネルを介した送信の後の前記符号語cの2m−１のノイズの多いシンボルを表す、ステップ
を含む、請求項11から13のいずれか一項に記載の方法（500）。
【請求項１５】
前記行列
【数７９】
2019525638.tif 000400
の最初の複数のt行の最後の非ゼロ要素が、ある整数j0についてj≧j0である異なる位置jに配置されるように前記最初の複数のt行を構成するステップと、擬似乱数発生器によってインデックスz＜jを有する列に配置される前記最初の複数のt行の要素を構成するステップと、行列
【数８０】
2019525638.tif 000401
の第2の複数のn−k−t行を異なる重み1の行として構成するステップと
を含む、請求項11に記載の方法（500）。
【請求項１６】
長さnの符号語cを復号化するための復号化装置（104）であって、前記復号化装置（104）は、
C（n，k，d）符号を使用して前記符号語cを復号化するように構成されたプロセッサ（104a）であって、前記符号C（n，k，d）は、長さnおよび最小距離dを有し、
【数８１】
2019525638.tif 000402
であり、mh（h＝1，．．．，s）は整数であり、
c＝uA
であり、ただし、
【数８２】
2019525638.tif 000403
、0≦ji＜k−1、xは、次元kのデータであり、
【数８３】
2019525638.tif 000404
（Fは、前記符号C（n，k，d）のn−k個の凍結ビットインデックスの集合である）である場合、
【数８４】
2019525638.tif 000405
であり、i∈Fである場合、
【数８５】
2019525638.tif 000406
は、以下の式の解によって与えられる制約行列であり、
【数８６】
2019525638.tif 000407
ただし、φiは、列iに最後の非ゼロ要素を有する、行列
【数８７】
2019525638.tif 000408
の行のインデックスであり、
【数８８】
2019525638.tif 000409
は、プリコーディング行列であり、Aは、以下のように定義され、
【数８９】
2019525638.tif 000410
ただし、
【数９０】
2019525638.tif 000411
であり、
【数９１】
2019525638.tif 000412
は、行列Qとそれ自体とのm倍クロネッカー積を表す、プロセッサ（104a）
を備える、復号化装置（104）。
【請求項１７】
前記プロセッサ（104a）は、逐次キャンセルアルゴリズムの一般化によって前記符号語cを復号化するようにさらに構成される、請求項16に記載の復号化装置（104）。
【請求項１８】
前記プロセッサ（104a）は、以下の式によってuを計算し、
i∈Fの場合は
【数９２】
2019525638.tif 000413
および
【数９３】
2019525638.tif 000414
の場合は
【数９４】
2019525638.tif 000415
ただし、φiは、列iに最後の非ゼロ要素を有する、前記行列
【数９５】
2019525638.tif 000416
の行のインデックスであり、
【数９６】
2019525638.tif 000417
は、通信チャネル110を介した前記復号化装置への送信の後の前記符号語cのn個のノイズの多いシンボルを表し、
【数９７】
2019525638.tif 000418
であり、
【数９８】
2019525638.tif 000419
である、ようにさらに構成される、請求項17に記載の復号化装置（104）。
【請求項１９】
前記プロセッサ（104a）は、
【数９９】
2019525638.tif 000420
かつi1＜i2である場合、
【数１００】
2019525638.tif 000421
の前に
【数１０１】
2019525638.tif 000422
を計算し、i∈Fである場合、
【数１０２】
2019525638.tif 000423
の前に
【数１０３】
2019525638.tif 000424
を計算するようにさらに構成される、請求項18に記載の復号化装置（104）。
【請求項２０】
長さnの符号語cを復号化するための方法（600）であって、前記方法は、
C（n，k，d）符号を使用して前記符号語cを復号化するステップ（602）であって、前記符号C（n，k，d）は、長さnおよび最小距離dを有し、
【数１０４】
2019525638.tif 000425
であり、mh（h＝1，．．．，s）は整数であり、
c＝uA
であり、ただし、
【数１０５】
2019525638.tif 000426
、0≦ji＜k−1、xは、次元kのデータであり、
【数１０６】
2019525638.tif 000427
（Fは、前記符号C（n，k，d）のn−k個の凍結ビットインデックスの集合である）である場合、
【数１０７】
2019525638.tif 000428
であり、i∈Fである場合、
【数１０８】
2019525638.tif 000429
は、以下の式の解によって与えられる制約行列であり、
【数１０９】
2019525638.tif 000430
ただし、φiは、列iに最後の非ゼロ要素を有する、行列
【数１１０】
2019525638.tif 000431
の行のインデックスであり、
【数１１１】
2019525638.tif 000432
は、プリコーディング行列であり、Aは、以下のように定義され、
【数１１２】
2019525638.tif 000433
ただし、
【数１１３】
2019525638.tif 000434
であり、
【数１１４】
2019525638.tif 000435
は、行列Qとそれ自体とのm倍クロネッカー積を表す、ステップ（602）
を含む、方法（600）。
【国際調査報告】
2019525638.tif 000436
2019525638.tif 000437
2019525638.tif 000438