JP2019525638A

JP2019525638A - ２のべき乗でない長さに拡張されたポーラ符号の符号化および復号化

Info

Publication number: JP2019525638A
Application number: JP2019507136A
Authority: JP
Inventors: オレーク・フィートエヴィッチ・クルマエフ; ペトル・ウラジーミロヴィッチ・トリフォノフ; アレクサイ・ミハイロヴィッチ・ラジンキン; アレクセイ・エドアルドヴィッチ・マエフスキー
Original assignee: ホアウェイ・テクノロジーズ・カンパニー・リミテッド
Priority date: 2016-08-12
Filing date: 2016-08-12
Publication date: 2019-09-05
Anticipated expiration: 2036-08-12
Also published as: JP6817414B2; KR20190032465A; US10848185B2; WO2018030910A1; US20190173496A1; CN109644006A; EP3476052B1; EP3476052A1; KR102118328B1; CN109644006B

Abstract

本発明は、データの符号化およびデータの復号化のための装置および方法に関する。例えば、本発明は、次元kのデータxを長さnの符号語cに符号化するための符号化装置（102）であって、符号化装置（102）は、式c＝uAに基づいて、C（n，k，d）符号を使用してデータxを符号化するように構成されたプロセッサ（102a）であって、符号C（n，k，d）は、長さnおよび最小距離dを有し、であり、mh（h＝1，．．．，s）は整数であり、ただし、、0≦ji＜k−1、（Fは、符号C（n，k，d）のn−k個の凍結ビットインデックスの集合である）である場合、であり、i∈Fである場合、は、式の解によって与えられる制約行列であり、ただし、φiは、列iに最後の非ゼロ要素を有する、行列の行のインデックスであり、は、プリコーディング行列であり、Aは、に基づいて定義される行列であり、は、行列Qとそれ自体とのm倍クロネッカー積を表す、プロセッサ（102a）を備える、符号化装置（102）に関する。

Description

一般に、本発明は、通信システムにおけるデータの符号化および復号化に関する。特に、本発明は、ポーラ符号またはポーラサブ符号に基づく符号を使用したデータの符号化およびデータの復号化のための装置および方法に関する。

ノイズの多い通信チャネルを介した信頼できるデータ送信には、通常、ある種の誤り訂正符号化を使用することが必要とされる。多くのチャネルのシャノン容量を達成するためのポーラ符号が示されている（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＝2^m，k）ポーラサブ符号Cは、ベクトルc＝xWA_mの集合として定義することができ、ただし、Wは、k×nのプリコーディング行列を表し、
は、ポーラ変換を表し、
は、行列Qとそれ自体のm倍クロネッカー積を表す。Wの各列が最大で1の重みを持ち、各行が重み1を持つように行列Wを得ることによって、古典ポーラ符号を得ることができる。ポーラサブ符号は、ベクトルcが、十分に高い最小距離を有する（すなわち、H^T＝0（Hは親符号の検査行列）である）ある親符号の符号語でもあるようにWを得ることによって得ることができる。例えば、拡張Bose−Chaudhuri−Hocquenghem（BCH：Bose−Chaudhuri−Hocquenghem）が優れた親符号になり得ることが示されている。

ポーラサブ符号を定義する別の同等の方法は、それをベクトルc＝uAの集合と見なすことであり、ただし、uV^T＝0であり、Vは（n−k）×nの制約行列であり、このためWV^T＝0である。ガウス消去法によって、行列Vは、最大で1つの行が各列で終わるように構成することができる。その後、ポーラ変換A_mの入力シンボルu_iに対する以下の制約の集合を得ることができる。
ただし、j_iは、Vのi番目の行の最後の非ゼロエントリの位置である。シンボルj_iは、動的凍結シンボルとも呼ばれる。これらの動的凍結シンボルは、古典ポーラ符号の構成に使用される（静的）凍結シンボルの概念の一般化と見なすことができる。ポーラサブ符号を構成する標準的な方法は、行列V＝HA^T（Hは親符号の検査行列）を構成し、次に、最も高い誤り確率
を有するシンボルに対して追加の制約
（静的凍結制約）を導入することであり、ただし、P_iは、ポーラ変換A_mによって導出される合成ビットサブチャネルのビット誤り確率を表し、遷移確率関数は、以下のように記述することができ、
ただし、W（y｜c）は、基礎となる2進入力メモリレス出力対称チャネルの遷移確率関数であり、
である。

ポーラサブ符号を記述するための別の手法は、
が固定されるかまたは前のシンボルに依存するように凍結ビットインデックスj_iの集合Fを定義し、親符号の生成行列Gを考慮することである。その後、行列
を計算することができ、異なる行が異なる列で始まる（すなわち、最初の非ゼロエントリを有する）ようにするために、この行列にガウス消去法を適用することができ、次に、最も高い
（s_iは、i番目の行が始まる位置）を、得られた行列から消去することができる。

上で説明したすべての手法は、長さ2^mの符号を提供する。しかしながら、実際の用途のためには、任意の符号長を有する符号の構成が望まれる。

2^mとは異なる長さを有する符号を得るために、いくつかの技術、例えばいわゆる短縮技術およびパンクチャリング技術を適用することができる。短縮技術によれば、C（N，K，D）線形ブロック符号が与えられると、（n＝N−v，k＝K−v，d≧D）短縮符号を、符号Cからベクトルの集合
（Sは短縮シンボルの集合を表す）として得ることができる。パンクチャリング技術によれば、（N，K，D）線形ブロック符号Cが与えられると、（n＝N−v，k≦K，d≧D−v）パンクチャード符号を、符号Cからベクトルの集合
（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構成によって与えられる。この構成は、C₀⊂C₁、C₂⊂C₃、k₁−k₀＝k₃−k₂であるような線形符号C₀（n₀，k₀，d₀）、C₁（n₀，k₁，d₁）、C₂（n₂，k₂，d₂）、C₃（n₂，k₃，d₃）に基づき、C_iは、生成行列G_i（ただし
）を有すると仮定される。このようにして、以下の式によって与えられる生成行列Gを有する（n₀＋n₂，k₀＋k₃，min（d₀，d₂，d₁＋d₃））符号を得ることができる。
連結技術の別の例は、W．Alltopによる著作「A Method for Extending Binary Linear Codes」（IEEE Transactions on Information Theory，30（6），November 1984）に記載されている、C_i（n_i，k_i，d_i）（i＝1，．．．，6）符号（ただし、C₁＝C₂＋C₃、C₄＝C₂∩C₃、すなわち
、
、k₅＝k₂−k₄、k₆＝k₃−k₄）に基づくいわゆるXX構成によって与えられる。これらの符号により、以下の式で与えられる生成行列Gを有する（n₁＋n₅＋n₆，k₁，min（d₄，d₂＋d₅，d₃＋d₆，d₁＋d₅＋d₆））符号を得ることができる
しかしながら、連結技術によって得られる符号のパフォーマンスは依然として大幅に改善することができる。

したがって、ポーラ符号またはポーラサブ符号に基づく符号を使用したデータの符号化およびデータの復号化のための改善された装置および方法が必要とされる。

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を有し、
であり、m_h（h＝1，．．．，s）は整数であり、
c＝uA
ただし、
、0≦j_i＜k−1、
（Fは、符号C（n，k，d）のn−k個の凍結ビットインデックスの集合である）である場合、
であり、i∈Fである場合、
は、以下の式の解によって与えられる制約行列であり、
ただし、φ_iは、列iに最後の非ゼロ要素を有する、行列
の行のインデックスであり、
は、プリコーディング行列であり、Aは、以下のように定義され、
ただし、
であり、
は、行列Qとそれ自体とのm倍クロネッカー積を表す、プロセッサを備える。

上記のような第1の態様による符号化装置の第1の可能な実施態様の形態では、プロセッサは、複数の入れ子線形ブロック符号
に基づいて符号C（n，k，d）を構成し、τ_iは正の整数であり、
の生成行列は、以下の式によって与えられ、
ただし、G^（i，j）は、
の行列であり、
であり、G^（i，j）のプリコーディング行列は、
によって定義され、
のプリコーディング行列は、
によって定義され、行列
のp番目の行が始まる列のインデックスl_i，pは、式
によって定義される、ように、および、プリコーディング行列
をブロック行列として構成し、プリコーディング行列
のブロックは、行列
の選択された行からなる、ようにさらに構成される。

第1の態様の第1の実施態様の形態による符号化装置の第2の可能な実施態様の形態では、複数の入れ子線形ブロック符号
は、拡張Bose−Chaudhuri−Hocquenghem（e−BCH：extended Bose−Chaudhuri−Hocquenghem）符号である。

上記のような第1の態様またはその第1〜第2の実施態様の形態のうちのいずれか1つによる符号化装置の第3の可能な実施態様の形態では、プロセッサは、以下のように符号C（n，k，d）のプリコーディング行列
を構成するようにさらに構成され、
ただし、
は、少なくともdの最小距離を有する長さ
の最大のe−BCH符号のインデックスであり、
は、行列
に基づいて定義される行列である。

第1の態様の第1〜第3の実施態様の形態のうちのいずれか1つによる符号化装置の第4の可能な実施態様の形態では、プロセッサは、
の最小値を有する行列
の行によって行列
を構成し、P_m，iはビットサブチャネルの誤り確率
であり、
は通信チャネルを介した送信の後の符号語cの2^m−1のノイズの多いシンボルを表す、ようにさらに構成される。

上記のような第1の態様またはその第1〜第4の実施態様の形態のうちのいずれか1つによる符号化装置の第5の可能な実施態様の形態では、プロセッサは、行列
の最初の複数のt行の最後の非ゼロ要素が、ある整数j₀についてj≧j₀である異なる位置jに配置されるように最初の複数のt行を構成し、整数jの2進展開における非ゼロビットの数がw₀に等しく設定され、擬似乱数発生器によってインデックスz＜jを有する列に配置される最初の複数のt行の要素を構成し、行列
の第2の複数のn−k−t行を異なる重み1の行として構成するようにさらに構成される。

第1の態様の第5の実施態様の形態による符号化装置の第6の可能な実施態様の形態では、擬似乱数生成器は、線形フィードバックシフトレジスタである。

第1の態様の第1〜第6の実施態様の形態のうちのいずれか1つによる符号化装置の第7の可能な実施態様の形態では、プロセッサは、行列
または
の行を、それぞれ値l_i，pおよび値l_j，pの昇順に並べ替えるようにさらに構成される。

第1の態様の第1〜第7の実施態様の形態のうちのいずれか1つによる符号化装置の第8の可能な実施態様の形態では、プロセッサは、l_i，pの最小値を有する行列
のk個の行に基づいて行列
を構成するように構成される。

第2の態様によれば、本発明は、次元kのデータxを長さnの符号語cに符号化するための方法に関する。本方法は、
以下の式に基づいて、C（n，k，d）符号を使用してデータxを符号化するステップであって、符号C（n，k，d）は、長さnおよび最小距離dを有し、
であり、m_h（h＝1，．．．，s）は整数であり、
c＝uA
ただし、
、0≦j_i＜k−1、
（Fは、符号C（n，k，d）のn−k個の凍結ビットインデックスの集合である）である場合、
であり、i∈Fである場合、
は、以下の式の解によって与えられる制約行列であり、
ただし、φ_iは、列iに最後の非ゼロ要素を有する、行列
の行のインデックスであり、
は、プリコーディング行列であり、Aは、以下のように定義され、
ただし、
であり、
は、行列Qとそれ自体とのm倍クロネッカー積を表す、ステップを含む。

本発明の第2の態様による方法は、本発明の第1の態様による符号化装置によって実行され得る。本発明の第2の態様による方法のさらなる特徴は、本発明の第1の態様およびその異なる実施態様の形態による符号化装置の機能から直接得られる。

第3の態様によれば、本発明は、長さnの符号語cを復号化するための復号化装置に関する。復号化装置は、C（n，k，d）符号を使用して符号語cを復号化するように構成されたプロセッサであって、符号C（n，k，d）は、長さnおよび最小距離dを有し、
であり、m_h（h＝1，．．．，s）は整数であり、
c＝uA
であり、ただし、
、0≦j_i＜k−1、xは、次元kのデータであり、
（Fは、符号C（n，k，d）のn−k個の凍結ビットインデックスの集合である）である場合、
であり、i∈Fである場合、
は、以下の式の解によって与えられる制約行列であり、
ただし、φ_iは、列iに最後の非ゼロ要素を有する、行列
の行のインデックスであり、
は、プリコーディング行列であり、Aは、以下のように定義され、
ただし、
であり、
は、行列Qとそれ自体とのm倍クロネッカー積を表す、プロセッサを備える。

上記のような第3の態様による復号化装置の第1の可能な実施態様の形態では、プロセッサは、逐次キャンセルアルゴリズムの一般化によって符号語cを復号化するようにさらに構成される。

第3の態様の第1の実施態様の形態による復号化装置の第2の可能な実施態様の形態では、プロセッサ、以下の式によってuを計算し、
i∈Fの場合は
および
の場合は
ただし、φ_iは、列iに最後の非ゼロ要素を有する、行列
の行のインデックスであり、
は、通信チャネルを介した復号化装置への送信の後の符号語cのn個のノイズの多いシンボルを表し、
であり、
である、ようにさらに構成される。

第3の態様の第2の実施態様の形態による復号化装置の第3の可能な実施態様の形態では、プロセッサは、
かつi₁＜i₂である場合、
の前に
を計算し、i∈Fである場合、
の前に
を計算するようにさらに構成される。

第4の態様によれば、本発明は、長さnの符号語cを復号化するための方法であって、該方法は、
C（n，k，d）符号を使用して符号語cを復号化するステップであって、符号C（n，k，d）は、長さnおよび最小距離dを有し、
であり、m_h（h＝1，．．．，s）は整数であり、
c＝uA
であり、ただし、u_i＝x_j、0≦j＜k−1、xは、次元kのデータであり、
（Fは、符号C（n，k，d）のn−k個の凍結ビットインデックスの集合である）である場合、
であり、i∈Fである場合、
は、以下の式の解によって与えられる制約行列であり、
ただし、φ_iは、列iに最後の非ゼロ要素を有する、行列
の行のインデックスであり、
は、プリコーディング行列であり、Aは、以下のように定義され、
ただし、
であり、
は、行列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を有し、
であり、m_hが＞m_h＋1であり（h＝1，．．．，s）、かつ整数である。
c＝uA
ただし、
、0≦j_i＜k−1、
（Fは、符号C（n，k，d）のn−k個の凍結ビットインデックスの集合である）である場合、
であり、i∈Fである場合、
は制約行列である。

制約行列
は、以下の式の解によって与えられる。
ただし、φ_iは、列iに最後の非ゼロ要素を有する、行列
の行のインデックスであり、
は、プリコーディング行列であり、Aは、以下のように定義される。
ただし、
であり、
は、行列Qとそれ自体とのm倍クロネッカー積を表す。

一実施形態では、プロセッサ102aと同様に、復号化装置104のプロセッサ104aは、C（n，k，d）符号を使用して符号語cを復号化するように構成され、符号C（n，k，d）は、長さnおよび最小距離dを有し、
であり、m_hが＞m_h＋1であり（h＝1，．．．，s）、かつ整数であり、
c＝uA
であり、ただし、u_i＝x_j、0≦j＜k−1、xは、次元kのデータであり、
（Fは、符号C（n，k，d）のn−k個の凍結ビットインデックスの集合である）である場合、
であり、i∈Fである場合、
は、以下の式の解によって与えられる制約行列である。
ただし、φ_iは、列iに最後の非ゼロ要素を有する、行列
の行のインデックスであり、
は、プリコーディング行列であり、Aは、以下のように定義される。
ただし、
であり、
は、行列Qとそれ自体とのm倍クロネッカー積を表す。

通信チャネル110は、有線または無線の通信チャネルとすることができる。

一実施形態では、プロセッサ102aは、以下のステップに基づいて制約行列
を生成するように構成され得る。
第1のステップ：入れ子の拡張プリミティブ狭義BCH符号
（0≦j＜τ_i）の生成行列
を構成する、ただし、G^（i，j）は、
の行列（
）であり、以下のようにG^（i，j）の対応するプリコーディング行列を定義する。
および
ただし、行列
のp番目の行が始まる列のインデックスは、以下によって定義される。

一実施形態では、任意のiについて、すべてのl_i，pは異なり、一般に、整数τ_iは、次数Mの既約多項式の数に等しく、Mは、m_iの約数を表すと仮定され得る。

第2のステップ：行列
の入れ子構造を保ちながら、すべての行が異なる列で始まるようにするために、基本行操作を
に適用する。

第3のステップ：行列
の行を選択し、それらをプリコーディング行列
のi番目の列に入れる、ただし、プリコーディング行列
はブロック行列である。

第4のステップ：行列
（あるε＞0について）の行を選択し、それらをプリコーディング行列
のi番目の列に入れる。このような行ごとに、前のステップで選択されていない行列
の行を選択し、それを列i’の行列
の同じ行に入れる。要約すると、構成されたプリコーディング行列
は、以下によって与えられる。
ただし、
は、最小距離dを有する長さ
の最大のe−BCH符号のインデックスであり、
は、次に大きいe−BCH符号の最小距離差である。行列
は、行列
（ただし、
）のいくつかの行およびゼロ行からなり、このため、任意のsについて、非ゼロ行を有する最大で1つのブロックi
がある。

第5のステップ：最小の
を有するブロックiの列l_i，pから始まる行列
のk個の行を保持する、ただし、P_m，iは、ビットサブチャネルの誤り確率
であり、
は、通信チャネル110を介した送信後の符号語cの2^m−1個のノイズの多いシンボルを表す。
を得られた行列とする。

第6のステップ：
を得て、
の行が異なる列j_i（0≦i＜n−k）で終わるようにするためにガウス消去法を使用し、（動的）凍結ビットインデックスの集合をF＝｛j_i，0≦i＜n−k｝と定義する。

制約行列
を生成するための上で説明したステップについて説明するために、連鎖ポーラサブ符号に基づく例示的な（24，11，6）符号の構成が検討される。この場合、符号は、次元n＝24を有し、これは24＝2⁴＋2³と書くこともできるため、m₀＝4、m₁＝3となる。図1aおよび図1bには、対応する拡張BCH符号C_ijの入れ子の生成行列G^（i，j）（i＝0、1およびj＝1、2、3）が示されており、d_0，0＝16、d_0，1＝8、d_0，2＝6、d_0，3＝4、d_1，0＝8、d_1，1＝4、d_1，2＝2である。図1aおよび図1bに示す行列G^（i，j）と行列
とを乗算し、基本行操作を適用することによって、図1cおよび図1dに示すように、対応するプリコーディング行列W^（i，j）を得ることができる。プリコーディング行列W^（i，j）とε＝2とを組み合わせることで、図1eに示すように、親符号のプリコーディング行列
を得ることができる。消去確率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である。

行列
の6番目の行は、列3から始まり、これは、最も高い誤り確率0．386を有するサブチャネルに対応するため、それは除去され得る。したがって、図1fに示すように、連鎖ポーラサブ符号に基づく（24，11，6）符号に関するプリコーディング行列
を得ることができる。最後に、図1gに示すように、対応する制約行列
を得ることができる。

別の実施形態では、プロセッサ102aは、以下のステップに従って、（n−k）×nの行列
を構成するように構成され得る。
第1のステップ：
の行を、最も高い
を有するブロックiの列l_i，pに1を含む、重み1の異なるベクトルに設定する。
第2のステップ：
の最後のρ行のそれぞれについて、最大で2つのブロックiの列j＜l_i，pに任意の2進値を入れる。

一実施形態では、この2進値は、線形フィードバックシフトレジスタなどの擬似乱数発生器（PRNG：pseudo−random number generator）によって得ることができる。これには、PRNGのパラメータおよびシード値だけを与えることで符号をコンパクトに指定することができるという利点がある。さらに、上で言及したステップに従って構成された行列
には、高パフォーマンスを有する連鎖ポーラサブ符号を提供するという利点がある。

行列
および
が利用可能になったら、別の実施形態では、プロセッサ102aは、以下の式に従って次元kのデータxを符号語cに符号化するようにさらに構成され得る。

さらに、符号語cが符号化されたら、それは、通信チャネル110を介して復号化装置104に送信され得る。しかしながら、通信チャネル110を介した送信の後、符号語cのn個のシンボルは、ノイズの影響を受け、ノイズの多いシンボル
をもたらす。したがって、符号語cの正しいシンボルを復元するための方法が必要とされる。

一実施形態では、復号化装置104のプロセッサ104aは、以下の式に基づいて、一般化された逐次キャンセルアルゴリズムおよびそのリストまたは順次拡張を使用して符号語cを復元するように構成され得る。
および
ただし、
および
。

この復号化方法はまた、TalおよびVardyならびにMiloslavskayaおよびTrifonovによる先に言及した著作に提示されたものと同様の、リストおよび順次逐次キャンセル方法を得るように拡張されてもよい。

一実施形態では、シンボル
を得る順序は、以下の規則に基づいて並べ替えられ得る。
a．
かつi₁＜i₂の場合、
の前に
が計算される。
b．i∈Fの場合、
の前に
が計算される。

シンボル
の検出順序を並べ替えることには、これによりリストおよび順次逐次キャンセルアルゴリズムのパフォーマンスが改善され得るという利点がある。

図2は、一実施形態に従って、連鎖ポーラサブ符号に基づく符号に関する符号化装置102の構造の概略図を示す。この実施形態では、符号は長さn＝12＝2³＋2²を有し、それは2つのポーラ変換、すなわち、
（m₁＝3、サイズ8の（ポーラ変換1））および
（m₂＝2、サイズ4の（ポーラ変換2））を含む。符号化されるべき次元4のデータxは、シンボルu₃、u₅、u₇、u₉にマッピングされる4つのシンボルx₀、x₁、x₂、x₃によって表されている。凍結ビットシンボルの集合は、u₀、u₁、u₂、u₄、u₆、u₈、u₁₀、u₁₁によって表されている。一実施形態では、符号化装置102のプロセッサ102aは、図2に示すように、対応するポーラ変換の他の入力シンボルのいくつかの線形結合の関数としてシンボルu₆およびu₁₀を計算するように構成され得る。さらに、プロセッサ102aは、ポーラ変換1の入力シンボルの関数としてポーラ変換2の入力シンボルu₁₁を計算するように構成され得る。さらに、凍結およびクロス符号化制約の構造は、得られた符号が十分に高い最小距離を有し、逐次キャンセルアルゴリズムの可能な一般化または修正によって効率的な方法で復号化され得るように実現され得る。

図3は、一実施形態に従って、信号対ノイズ比（E_b／N₀）の関数として異なる符号のフレーム誤り率（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を有し、
であり、m_h（h＝1，．．．，s）は整数であり、
c＝uA
ただし、
、0≦j_i＜k−1、
（Fは、符号C（n，k，d）のn−k個の凍結ビットインデックスの集合である）である場合、
であり、i∈Fである場合、
は、以下の式の解によって与えられる制約行列であり、
ただし、φ_iは、列iに最後の非ゼロ要素を有する、行列
の行のインデックスであり、
は、プリコーディング行列であり、Aは、以下のように定義され、
ただし、
であり、
は、行列Qとそれ自体とのm倍クロネッカー積を表す、ステップ502
を含む。

図6は、一実施形態による、長さnの符号語cを復号化するための方法600の概略図を示す。方法600は、
C（n，k，d）符号を使用して符号語cを復号化するステップ602であって、符号C（n，k，d）は、長さnおよび最小距離dを有し、
であり、m_h（h＝1，．．．，s）は整数であり、
c＝uA
であり、ただし、
、0≦j_i＜k−1、xは、次元kのデータであり、
（Fは、符号C（n，k，d）のn−k個の凍結ビットインデックスの集合である）である場合、
であり、i∈Fである場合、
は、以下の式の解によって与えられる制約行列であり、
ただし、φ_iは、列iに最後の非ゼロ要素を有する、行列
の行のインデックスであり、
は、プリコーディング行列であり、Aは、以下のように定義され、
ただし、
であり、
は、行列Qとそれ自体とのm倍クロネッカー積を表す、ステップ602
を含む。

本開示の特定の特徴または態様は、いくつかの実施態様または実施形態のうちの1つのみに関して開示されているが、このような特徴または態様は、所与のまたは特定の用途にとって望ましく好適となり得るように、他の実施態様または実施形態の1つ以上の他の特徴または態様と組み合わされてもよい。さらに、用語「含む」、「有する」、「伴う」、またはこれらの他の変種が発明を実施するための形態または特許請求の範囲のいずれかで使用される限りにおいて、このような用語は、用語「備える」と同様に包括的であることを意図されている。また、用語「例示的」、「例えば（for example）」、および「例えば（e．g．）」は、最良または最適なものとしてではなく、単に例として意図されている。派生語と共に用語「結合された」および「接続された」が使用されている場合がある。これらの用語は、2つの要素が、物理的または電気的に直接接触しているかどうかにかかわらず、または互いに直接接触していないにもかかわらず、互いに協働または相互作用することを示すために使用されている場合があることを理解されたい。

本明細書では特定の態様を示し説明したが、本開示の範囲から逸脱することなく、様々な代替および／または同等の実施態様が、図示および説明した特定の態様の代わりになり得ることが、当業者によって理解される。本出願は、本明細書に述べられている特定の態様の適合例または変形例を含むことを意図されている。

以下の特許請求の範囲の要素は、対応するラベルを付けて特定の順序で記載されているが、特許請求の範囲の記載が、これらの要素のいくつかまたはすべてを実施するために特定の順序を含意していない限り、これらの要素が特定の順序で実施されることに必ずしも限定されると意図されてはいない。

上記の教示を踏まえれば、多くの代替例、修正例、および変形例が当業者に明らかとなる。言うまでもなく、当業者であれば、本明細書で説明された用途以外にも本発明の多くの用途があることを容易に認めるであろう。本発明について、1つ以上の特定の実施形態を参照して説明したが、当業者であれば、本発明の範囲から逸脱することなくそれに多くの変更を加えることができることを理解するであろう。したがって、添付の特許請求の範囲およびその均等物の範囲内で、本明細書で具体的に説明されているのとは別の方法で本発明を実施することができることを理解されたい。

100 通信システム
102 符号化装置
102a、104a プロセッサ
104 復号化装置
110 通信チャネル

Claims

次元kのデータxを長さnの符号語cに符号化するための符号化装置（102）であって、前記符号化装置（102）は、
以下の式に基づいて、C（n，k，d）符号を使用して前記データxを符号化するように構成されたプロセッサ（102a）であって、前記符号C（n，k，d）は、長さnおよび最小距離dを有し、
であり、m_h（h＝1，．．．，s）は整数であり、
c＝uA
ただし、
、0≦j_i＜k−1、
（Fは、前記符号C（n，k，d）のn−k個の凍結ビットインデックスの集合である）である場合、
であり、i∈Fである場合、
は、以下の式の解によって与えられる制約行列であり、
ただし、φ_iは、列iに最後の非ゼロ要素を有する、行列
の行のインデックスであり、
は、プリコーディング行列であり、Aは、以下のように定義され、
ただし、
であり、
は、行列Qとそれ自体とのm倍クロネッカー積を表す、プロセッサ（102a）
を備える、符号化装置（102）。
前記プロセッサ（102a）は、複数の入れ子線形ブロック符号
に基づいて前記符号C（n，k，d）を構成し、τ_iは正の整数であり、
の生成行列は、以下の式によって与えられ、
ただし、G^（i，j）は、
の行列であり、
であり、G^（i，j）のプリコーディング行列は、
によって定義され、
のプリコーディング行列は、
によって定義され、行列
のp番目の行が始まる列のインデックスl_i，pは、式
によって定義される、ように、および、前記プリコーディング行列
をブロック行列として構成し、前記プリコーディング行列
のブロックは、前記行列
の選択された行からなる、ようにさらに構成される、請求項1に記載の符号化装置（102）。
前記複数の入れ子線形ブロック符号
は、拡張Bose−Chaudhuri−Hocquenghem（e−BCH）符号である、請求項2に記載の符号化装置（102）。
前記プロセッサ（102a）は、以下のように前記符号C（n，k，d）のプリコーディング行列
を構成するようにさらに構成され、
ただし、
は、少なくともdの最小距離を有する長さ
の最大のe−BCH符号のインデックスであり、
は、前記行列
に基づいて定義される行列である、請求項1から3のいずれか一項に記載の符号化装置（102）。
前記プロセッサ（102a）は、
の最小値を有する前記行列
の行によって前記行列
を構成し、P_m，iはビットサブチャネルの誤り確率
であり、
は通信チャネル（110）を介した送信の後の前記符号語cの2^m−1のノイズの多いシンボルを表す、ようにさらに構成される、請求項2から4のいずれか一項に記載の符号化装置（102）。
前記プロセッサ（102a）は、前記行列
の最初の複数のt行の最後の非ゼロ要素が、ある整数j₀についてj≧j₀である異なる位置jに配置されるように前記最初の複数のt行を構成し、擬似乱数発生器によってインデックスz＜jを有する列に配置される前記最初の複数のt行の要素を構成し、行列
の第2の複数のn−k−t行を異なる重み1の行として構成するようにさらに構成される、請求項1から5のいずれか一項に記載の符号化装置（102）。
前記擬似乱数発生器は線形フィードバックシフトレジスタである、請求項6に記載の符号化装置（102）。
前記プロセッサ（102a）は、前記行列
または
の行を、それぞれ値l_i，pおよび値l_j，pの昇順に並べ替えるようにさらに構成される、請求項2から7のいずれか一項に記載の符号化装置（102）。
前記プロセッサ（102a）は、l_i，pの最小値を有する前記行列
のk個の行に基づいて前記行列
を構成するように構成される、請求項2から8のいずれか一項に記載の符号化装置（102）。
次元kのデータxを長さnの符号語cに符号化するための方法（500）であって、前記方法は、
以下の式に基づいて、C（n，k，d）符号を使用して前記データxを符号化するステップ（502）であって、前記符号C（n，k，d）は、長さnおよび最小距離dを有し、
であり、m_h（h＝1，．．．，s）は整数であり、
c＝uA
ただし、
、0≦j_i＜k−1、
（Fは、前記符号C（n，k，d）のn−k個の凍結ビットインデックスの集合である）である場合、
であり、i∈Fである場合、
は、以下の式の解によって与えられる制約行列であり、
ただし、φ_iは、列iに最後の非ゼロ要素を有する、行列
の行のインデックスであり、
は、プリコーディング行列であり、Aは、以下のように定義され、
ただし、
であり、
は、行列Qとそれ自体とのm倍クロネッカー積を表す、ステップ（502）
を含む、方法（500）。
長さnの符号語cを復号化するための復号化装置（104）であって、前記復号化装置（104）は、
C（n，k，d）符号を使用して前記符号語cを復号化するように構成されたプロセッサ（104a）であって、前記符号C（n，k，d）は、長さnおよび最小距離dを有し、
であり、m_h（h＝1，．．．，s）は整数であり、
c＝uA
であり、ただし、
、0≦j_i＜k−1、xは、次元kのデータであり、
（Fは、前記符号C（n，k，d）のn−k個の凍結ビットインデックスの集合である）である場合、
であり、i∈Fである場合、
は、以下の式の解によって与えられる制約行列であり、
ただし、φ_iは、列iに最後の非ゼロ要素を有する、行列
の行のインデックスであり、
は、プリコーディング行列であり、Aは、以下のように定義され、
ただし、
であり、
は、行列Qとそれ自体とのm倍クロネッカー積を表す、プロセッサ（104a）
を備える、復号化装置（104）。
前記プロセッサ（104a）は、逐次キャンセルアルゴリズムの一般化によって前記符号語cを復号化するようにさらに構成される、請求項11に記載の復号化装置（104）。
前記プロセッサ（104a）は、以下の式によってuを計算し、
i∈Fの場合は
および
の場合は
ただし、φ_iは、列iに最後の非ゼロ要素を有する、前記行列
の行のインデックスであり、
は、通信チャネル110を介した前記復号化装置への送信の後の前記符号語cのn個のノイズの多いシンボルを表し、
であり、
である、ようにさらに構成される、請求項12に記載の復号化装置（104）。
前記プロセッサ（104a）は、
かつi₁＜i₂である場合、
の前に
を計算し、i∈Fである場合、
の前に
を計算するようにさらに構成される、請求項13に記載の復号化装置（104）。
長さnの符号語cを復号化するための方法（600）であって、前記方法は、
C（n，k，d）符号を使用して前記符号語cを復号化するステップ（602）であって、前記符号C（n，k，d）は、長さnおよび最小距離dを有し、
であり、m_h（h＝1，．．．，s）は整数であり、
c＝uA
であり、ただし、
、0≦j_i＜k−1、xは、次元kのデータであり、
（Fは、前記符号C（n，k，d）のn−k個の凍結ビットインデックスの集合である）である場合、
であり、i∈Fである場合、
は、以下の式の解によって与えられる制約行列であり、
ただし、φ_iは、列iに最後の非ゼロ要素を有する、行列
の行のインデックスであり、
は、プリコーディング行列であり、Aは、以下のように定義され、
ただし、
であり、
は、行列Qとそれ自体とのm倍クロネッカー積を表す、ステップ（602）
を含む、方法（600）。
コンピュータ上で実行されたときに請求項10に記載の方法（500）および請求項15に記載の方法（600）を実行するためのプログラムコードを含むコンピュータプログラム。