(57)【要約】  方法は、ノイジ通信チャネルについてのチャネル復号器における凍結ビットのｎ個の最良の位置を判定する。復号方法及び復号プロセシングユニットは、ｎ個の最悪の位置において凍結ビットを有するチャネルを実装する。方法及びシステムは、ｎ個のビットからビットｉごとに、反復的に、特定の値に簡易化された収縮アイデンティティを使用して論理グラフをトラバースすることによって、ビットｉについての確率ベクトルを判定し、対応する収縮アイデンティティに基づいて、後の反復の間に、後続の参照についての確率ベクトルの判定の間に新たに計算された収縮アイデンティティから特定の値をインデックス付けし、確率ベクトルからビットｉを固定し、全てのｎ個のビットが固定されるまで、ビットｉ＋１に移動する。【選択図】図２４
2020515117.tif 000002
【特許請求の範囲】
【請求項１】
ノイジ通信チャネルについてのチャネル復号器における凍結ビットのｎ個の最良の位置を判定する方法であって、
ポーラ符号符号化スキームを選択することと、
前記ポーラ符号符号化スキームに対応するポーラ符号復号器スキームを取得することと、
チャネルビットの数を定義するチャネル帯域幅を判定することと、
メッセージビットの数を定義するメッセージ長、凍結ビットｎの数を定義するチャネルビットの数及びメッセージビットの数を判定することと、
ノイジ通信チャネルの性質に関わらず、消去確率ｐにより通信チャネルを特徴付けることと、
前記確率ｐを考慮して、ｎ個の最悪の位置を計算することと
を備えた方法。
【請求項２】
前記ポーラ符号符号化スキームは、ＣＮＯＴゲートの少なくとも２レベルを使用してモデル化された畳み込みポーラ符号である、請求項１に記載の方法。
【請求項３】
前記ポーラ符号符号化スキームは、２の累乗としてビットの数ｋを有し、ｋは、チャネルビットの数以上であるように選択される、請求項１又は２に記載の方法。
【請求項４】
前記ポーラ符号符号化スキームは、各々が２の累乗として表現されるいくつかのコーディングビットを含む、１つよりも多いサブポーラ符号を含み、サブポーラ符号の各々におけるコーディングビットの数は、その合計がチャネルビットの数以上であるように選択される、請求項１又は２に記載の方法。
【請求項５】
前記ノイジ通信チャネルは、消去ｐ２のｇｏｏｄ状態によって特徴付けられる相関付けられたノイズ特性を提示し、消去の確率ｐは、ｂａｄ状態の確率ｐ１≧ｐ２に対応し、前記チャネルは、ｇｏｏｄ状態とｂａｄ状態との間の遷移の確率Ｐｇｂ及びｇｏｏｄ状態とｂａｄ状態との間の遷移の確率Ｐｂｇを提供し、前記ｎ個の最悪の位置を計算することは更に、確率ｐ２、Ｐｇｂ、及びＰｂｇを考慮する、請求項１乃至４のいずれか一項に記載の方法。
【請求項６】
そこで選択されたポーラ符号復号器スキームを実装し、それによって判定された前記ｎ個の最悪の位置において凍結ビットを有する、請求項１乃至５のいずれか一項による復号方法。
【請求項７】
請求項１乃至５のいずれか一項により前記ポーラ符号復号器スキームをサポートし、請求項１乃至５のいずれか一項に記載の同一の１つとして判定された前記ｎ個の最悪の位置において凍結ビットを有する復号プロセシングユニット。
【請求項８】
ｍ＜ｎビットのメッセージを取得するためにｎ個のビットのメッセージを反復的に復号する方法であって、前記メッセージは、消去ｐ１のｂａｄ状態の確率、消去ｐ２のｇｏｏｄ状態、ｐ２≦ｐ１の確率によって特徴付けられる相関付けられたノイズを示すノイジ通信チャネルを通じて受信され、前記チャネルは、ｇｏｏｄ状態とｂａｄ状態との間の遷移の確率Ｐｇｂ及びｇｏｏｄ状態とｂａｄ状態との間の遷移の確率Ｐｂｇを提供し、
ｎ個のビットからビットｉごとに、反復的に、
特定の値に簡易化された収縮アイデンティティを使用して論理グラフをトラバースすることによって、ビットｉについての確率ベクトルを判定することと、
対応する収縮アイデンティティに基づいて、後の反復の間に、後続の参照についての確率ベクトルの判定の間に新たに計算された前記収縮アイデンティティから特定の値をインデックス付けすることと、
前記確率ベクトルから前記ビットｉを固定することと、
全てのｎ個のビットが固定されるまで、ビットｉ＋１に移動することと
を備えた方法。
【請求項９】
前記新たに計算された収縮アイデンティティは、前記確率ベクトルの前記判定の間に前記特定の値に置き換えられた前記論理グラフの１つ以上のセクションに対応する、請求項８に記載の方法。
【請求項１０】
前記メッセージは、ネットワークインタフェースを通じて受信される、請求項８又は９に記載の方法。
【請求項１１】
前記固定されたビットは、ネットワークスタックの上位の処理レイヤに提供される、請求項８乃至１０のいずれか一項に記載の方法。
【請求項１２】
ｍ＜ｎビットのメッセージを取得するためにｎ個のビットのメッセージを反復的に復号するシステムであって、前記メッセージは、ｂａｄ状態の確率ｐ１、消去ｐ２のｇｏｏｄ状態、ｐ２≦ｐ１の確率によって特徴付けられる相関付けられたノイズを示すノイジ通信チャネルを通じて受信され、前記チャネルは、ｇｏｏｄ状態とｂａｄ状態との間の遷移の確率Ｐｇｂ及びｇｏｏｄ状態とｂａｄ状態との間の遷移の確率Ｐｂｇを提供し、
ｎ個のビットからビットｉごとに、反復的に、
特定の値に簡易化された収縮アイデンティティを使用して論理グラフをトラバースすることによって、ビットｉについての確率ベクトルを判定し、
対応する収縮アイデンティティに基づいて、後の反復の間に、後続の参照についての確率ベクトルの判定の間に新たに計算された前記収縮アイデンティティから特定の値をインデックス付けし、
前記確率ベクトルから前記ビットｉを固定し、
全てのｎ個のビットが固定されるまで、ビットｉ＋１に移動する、
処理モジュールを備えたシステム。
【請求項１３】
前記新たに計算された収縮アイデンティティは、前記確率ベクトルの判定の間に前記特定の値に置き換えられた前記論理グラフの１つ以上のセクションに対応する、請求項１２に記載のシステム。
【請求項１４】
前記メッセージを受信するネットワークインタフェースを更に備えた、請求項１２又は１３に記載のシステム。
【請求項１５】
前記固定されたビットは、ネットワークスタックに関連付けられたネットワークスタックの上位の処理レイヤに提供される、請求項１２乃至１４のいずれか一項に記載のシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
３５Ｕ．Ｓ．Ｃ．１１９（ｅ）及び３７Ｃ．Ｆ．Ｒ．１．７８の下の優先権主張
この特許出願は、本明細書でその全体が組み込まれる、ＳＯＣＰＲＡ  Ｓｃｉｅｎｃｅｓ  ｅｔ  Ｇｅｎｉｅ  ｓ．ｅ．ｃの名義で、２０１７年３月３日に出願された、「ＣＯＮＶＯＬＵＴＩＯＮＡＬ  ＰＯＬＡＲ  ＣＯＤＥＳ」と題する先の米国仮特許出願第６２／４６６，４１４に基づく優先権を主張する。
【０００２】
本発明は、チャネルコーディング、より具体的には、チャネルコーディングにおける特定のタイプのポーラ符号の使用に関する。
【背景技術】
【０００３】
ノイズ、干渉、及び不良な信号強度によって生じる通信誤りを訂正するためのチャネルコーディングがセルラ通信システムにおいて使用される。チャネルコーディングは非常に複雑であると同時に、セルラ通信システムの性能の中心である。
【０００４】
３Ｇ及び４Ｇセルラシステムでは、主要なチャネルコーディング機構としてターボ符号が使用されてきた。５Ｇについて、無線インタフェースは、最大で２０Ｇｂｐｓのダウンリンクスループットに到達することが予想されると共に、超低待ち時間を維持する。５Ｇはまた、消費者の多様性（例えば、モノのインターネット（ＩｏＴ）、ブロードバンド通信、輸送通信など）を考慮して、はるかに高い柔軟性を必要とする。他の通信プロトコル（例えば、サテライト通信のための）も、改善されたチャネルコーディング技術から利益を得る。現在のチャネルコーディングは、その点で改善されることができる。
【０００５】
本発明は、この課題に少なくとも部分的に対処する。
【発明の概要】
【０００６】
この概要は、発明の詳細な説明において以下で更に説明される簡易化された形式にある概念の選択を導入するために提供される。この発明の概要は、特許請求される主題の主要な特徴又は必須の特徴を特定することを意図しておらず、特許請求される主題の範囲を判定する際の支援として使用されることも意図していない。
【０００７】
本発明の第１の態様は、ノイジ通信チャネルについてのチャネル復号器における凍結ビットのｎ個の最良の位置を判定する方法に向けられる。方法は、
・ポーラ符号符号化スキームを選択することと、
・ポーラ符号符号化スキームに対応するポーラ符号復号器スキームを取得することと、
・チャネルビットの数を定義するチャネル帯域幅を判定することと、
・メッセージビットの数を定義するメッセージ長、凍結ビットｎの数を定義するチャネルビットの数及びメッセージビットの数を判定することと、
・ノイジ通信チャネルの性質に関わらず、消去確率ｐにより通信チャネルを特徴付けることと、
・確率ｐを考慮して、ｎ個の最悪の位置を計算することと
を含む。
【０００８】
方法の任意選択の特徴として、ポーラ符号符号化スキームは、ＣＮＯＴゲートの少なくとも２レベルを使用してモデル化された畳み込みポーラ符号であってもよい。
【０００９】
任意選択で、ポーラ符号符号化スキームはまた、代わりに又は加えて、２の累乗としてビットの数ｋを有し、ｋは、チャネルビットの数以上であるように選択される。代替的なオプションとして、ポーラ符号符号化スキームは、各々が２の累乗として表現されるいくつかのコーディングビットを含む、１つよりも多いサブポーラ符号を含み、サブポーラ符号の各々におけるコーディングビットの数は、その合計がチャネルビットの数以上であるように選択される。
【００１０】
一部の実施形態では、ノイジ通信チャネルは、消去ｐ２のｇｏｏｄ状態によって特徴付けられる相関付けられたノイズ特性を提示してもよく、消去の確率ｐは、ｂａｄ状態の確率ｐ１≧ｐ２に対応する。チャネルはまた、ｇｏｏｄ状態とｂａｄ状態との間の遷移の確率Ｐｇｂ及びｇｏｏｄ状態とｂａｄ状態との間の遷移の確率Ｐｂｇを提供してもよく、したがって、ｎ個の最悪の位置を計算することは更に、確率ｐ２、Ｐｇｂ、及びＰｂｇを考慮する。
【００１１】
本発明の第２の態様に従って、第１の態様に従って選択されたポーラ符号復号器スキームを実装し、また、それによって判定されたｎ個の最悪の位置において凍結ビットを有する、復号方法が提供されてもよい。同様に、第１の態様に従って選択されたポーラ符号復号器スキームを実装し、それによって判定されたｎ個の最悪の位置において凍結ビットを有する、復号プロセシングユニットが提供されてもよい。
【００１２】
本発明の第３の態様に従って、ｍ＜ｎビットのメッセージを取得するためにｎ個のビットのメッセージを反復的に復号する方法が提供される。メッセージは、消去ｐ１のｂａｄ状態の確率、消去ｐ２のｇｏｏｄ状態、ｐ２≦ｐ１の確率によって特徴付けられる相関付けられたノイズを示すノイジ通信チャネルを通じて受信される。チャネルはまた、ｇｏｏｄ状態とｂａｄ状態との間の遷移の確率Ｐｇｂ及びｇｏｏｄ状態とｂａｄ状態との間の遷移の確率Ｐｂｇを提供する。方法は、
・ｎ個のビットからビットｉごとに、反復的に、
・特定の値に簡易化された収縮アイデンティティを使用して論理グラフをトラバースすることによって、ビットｉについての確率ベクトルを判定することと、
・対応する収縮アイデンティティに基づいて、後の反復の間に、後続の参照についての確率ベクトルの判定の間に新たに計算された収縮アイデンティティから特定の値をインデックス付けすることと、
・確率ベクトルからビットｉを固定することと、
・全てのｎ個のビットが固定されるまで、ビットｉ＋１に移動することと
を含む。
【００１３】
特定の実施形態では、新たに計算された収縮アイデンティティは、確率ベクトルの判定の間に特定の値に置き換えられた論理グラフの１つ以上のセクションに対応してもよい。メッセージは典型的には、必ずしもではないが、ネットワークインタフェースを通じて受信される。同様に、固定されたビットは典型的には、必ずしもではないが、ネットワークスタックの上位の処理レイヤに提供される。
【００１４】
本発明の第４の態様は、ｍ＜ｎビットのメッセージを取得するためにｎ個のビットのメッセージを反復的に復号するシステムに向けられ、メッセージは、ｂａｄ状態の確率ｐ１、消去ｐ２のｇｏｏｄ状態、ｐ２≦ｐ１の確率によって特徴付けられる相関付けられたノイズを示すノイジ通信チャネルを通じて受信される。チャネルは、ｇｏｏｄ状態とｂａｄ状態との間の遷移の確率Ｐｇｂ及びｇｏｏｄ状態とｂａｄ状態との間の遷移の確率Ｐｂｇを提供する。システムは、ｎ個のビットからビットｉごとに、反復的に、
・特定の値に簡易化された収縮アイデンティティを使用して論理グラフをトラバースすることによって、ビットｉについての確率ベクトルを判定し、
・対応する収縮アイデンティティに基づいて、後の反復の間に、後続の参照についての確率ベクトルの判定の間に新たに計算された収縮アイデンティティから特定の値をインデックス付けし、
・確率ベクトルからビットｉを固定し、
・全てのｎ個のビットが固定されるまで、ビットｉ＋１に移動する、
処理モジュールを含む。
【００１５】
新たに計算された収縮アイデンティティは、確率ベクトルの判定の間に特定の値に置き換えられた論理グラフの１つ以上のセクションに対応してもよい。システムは更に、メッセージを受信するネットワークインタフェースを含んでもよく、固定されたビットは、ネットワークインタフェースに関連付けられたネットワークスタックの上位の処理レイヤに提供されてもよい。
【００１６】
本発明の更なる特徴及び例示的な利点は、添付図面と併用して、以下の詳細な説明から明らかになるであろう。
【図面の簡単な説明】
【００１７】
【図１−１】図１Ａ、図１Ｂ、図１Ｃ、図１Ｃ’、図１Ｄ、図１Ｅ、図１Ｆ、及び図１Ｇは、本発明の教示に従った、一般化符号化回路を形成する例示的なレベルの論理図であり、本明細書で同時に図１と称される。
【図１−２】図１Ａ、図１Ｂ、図１Ｃ、図１Ｃ’、図１Ｄ、図１Ｅ、図１Ｆ、及び図１Ｇは、本発明の教示に従った、一般化符号化回路を形成する例示的なレベルの論理図であり、本明細書で同時に図１と称される。
【図１−３】図１Ａ、図１Ｂ、図１Ｃ、図１Ｃ’、図１Ｄ、図１Ｅ、図１Ｆ、及び図１Ｇは、本発明の教示に従った、一般化符号化回路を形成する例示的なレベルの論理図であり、本明細書で同時に図１と称される。
【図１−４】図１Ａ、図１Ｂ、図１Ｃ、図１Ｃ’、図１Ｄ、図１Ｅ、図１Ｆ、及び図１Ｇは、本発明の教示に従った、一般化符号化回路を形成する例示的なレベルの論理図であり、本明細書で同時に図１と称される。
【図１−５】図１Ａ、図１Ｂ、図１Ｃ、図１Ｃ’、図１Ｄ、図１Ｅ、図１Ｆ、及び図１Ｇは、本発明の教示に従った、一般化符号化回路を形成する例示的なレベルの論理図であり、本明細書で同時に図１と称される。
【図１−６】図１Ａ、図１Ｂ、図１Ｃ、図１Ｃ’、図１Ｄ、図１Ｅ、図１Ｆ、及び図１Ｇは、本発明の教示に従った、一般化符号化回路を形成する例示的なレベルの論理図であり、本明細書で同時に図１と称される。
【図１−７】図１Ａ、図１Ｂ、図１Ｃ、図１Ｃ’、図１Ｄ、図１Ｅ、図１Ｆ、及び図１Ｇは、本発明の教示に従った、一般化符号化回路を形成する例示的なレベルの論理図であり、本明細書で同時に図１と称される。
【図１−８】図１Ａ、図１Ｂ、図１Ｃ、図１Ｃ’、図１Ｄ、図１Ｅ、図１Ｆ、及び図１Ｇは、本発明の教示に従った、一般化符号化回路を形成する例示的なレベルの論理図であり、本明細書で同時に図１と称される。
【図１−９】図１Ａ、図１Ｂ、図１Ｃ、図１Ｃ’、図１Ｄ、図１Ｅ、図１Ｆ、及び図１Ｇは、本発明の教示に従った、一般化符号化回路を形成する例示的なレベルの論理図であり、本明細書で同時に図１と称される。
【図２】本発明の教示に従った、例示的な開境界畳み込みポーラ符号符号化回路の論理図である。
【図３】図３Ａ、図３Ｂ、及び図３Ｃは、本発明の教示に従った、例示的なノイジ伝送チャネルの論理図であり、本明細書で同時に図３と称される。
【図４】図４Ａ、図４Ｂ、及び図４Ｃは、本発明の教示に従った、アイデンティティとも称される、例示的な復号計算シンプリファイアの論理図であり、本明細書で同時に図４と称される。
【図５】本発明の教示に従った、判定された特定のビットにより、復号計算シンプリファイアが適用される復号する例の論理図である。
【図６】図６Ａ及び図６Ｂは、本発明の教示に従った、２つのオープンビットをもたらす例示的なテンソル回路の論理図であり、本明細書で同時に図６と称される。
【図７】図７Ａ、図７Ｂ、及び図７Ｃは、本発明の教示に従った、３つのオープンビットをもたらす例示的なテンソル回路の論理図であり、本明細書で同時に図７と称される。
【図８】本発明の教示に従った、４つのオープンビットをもたらす例示的なテンソル回路の論理図である。
【図９】図９Ａ及び図９Ｂは、本発明の教示に従った、５つのオープンビットをもたらす例示的なテンソル回路の論理図であり、本明細書で同時に図９と称される。図９Ａ、図９Ｂ、図９Ｃ、図９Ｄ、図９Ｅ、図９Ｆ、図９Ｇ、図９Ｈ、図９Ｉ、及び図９Ｊは、本発明の教示に従った論理図であり、本明細書で同時に図９と称される。
【図１０】本発明の教示に従った、例示的な相関付けられたノイズテンソルの論理図である。
【図１１】本発明の教示に従った、相関付けられたノイズが存在するときの１６ビット文字列の８番目のビットについての例示的な復号問題の論理図である。
【図１２】図１２Ａ、図１２Ｂ、図１２Ｃ、及び図１２Ｄは、本発明の教示に従った、相関付けられたノイズが存在するときの論理復号表現であり、本明細書で同時に図１２と称される。
【図１３】図１３Ａ、図１３Ｂ、図１３Ｃ、図１３Ｄ、図１３Ｅ、及び図１３Ｆは、本発明の教示に従った、相関付けられたノイズが存在するときの復号するための例示的な順次簡易化手順を表し、本明細書で同時に図１３と称される。
【図１４】本発明の教示に従った、例示的な相関付けられたノイズモデルの論理図である。
【図１５−１】図１５Ａ、図１５Ｂ、図１５Ｃ、及び図１５Ｄは、連続キャンセレーション復号の下、論理チャネルの実効消去レートによってパラメータ化された、各々のチャネルの精度を提示するグラフであり、本明細書で同時に図１５と称される。
【図１５−２】図１５Ａ、図１５Ｂ、図１５Ｃ、及び図１５Ｄは、連続キャンセレーション復号の下、論理チャネルの実効消去レートによってパラメータ化された、各々のチャネルの精度を提示するグラフであり、本明細書で同時に図１５と称される。
【図１６】ポーラ及び畳み込みポーラ符号についての誤り指数の推定を比較して示すグラフである。
【図１７−１】図１７Ａ、図１７Ｂ、図１７Ｃ、図１７Ｄ、図１７Ｅ、及び図１７Ｆは、二値消去チャネルについての様々なサイズのレート１／２ポーラ及び畳み込みポーラ符号の性能の比較を示すグラフであり、本明細書で同時に図１７と称される。
【図１７−２】図１７Ａ、図１７Ｂ、図１７Ｃ、図１７Ｄ、図１７Ｅ、及び図１７Ｆは、二値消去チャネルについての様々なサイズのレート１／２ポーラ及び畳み込みポーラ符号の性能の比較を示すグラフであり、本明細書で同時に図１７と称される。
【図１８−１】図１８Ａ、図１８Ｂ、図１８Ｃ、図１８Ｄ、図１８Ｅ、及び図１８Ｆは、ビット反転チャネルについての様々なサイズのレート１／２ポーラ及び畳み込みポーラ符号の性能の比較を示すグラフであり、本明細書で同時に図１８と称される。
【図１８−２】図１８Ａ、図１８Ｂ、図１８Ｃ、図１８Ｄ、図１８Ｅ、及び図１８Ｆは、ビット反転チャネルについての様々なサイズのレート１／２ポーラ及び畳み込みポーラ符号の性能の比較を示すグラフであり、本明細書で同時に図１８と称される。
【図１９−１】図１９Ａ、図１９Ｂ、図１９Ｃ、図１９Ｄ、図１９Ｅ、及び図１９Ｆは、付加的ガウスホワイトノイズチャネルについての様々なサイズのレート１／２ポーラ及び畳み込みポーラ符号の性能の比較を示すグラフであり、本明細書で同時に図１９と称される。
【図１９−２】図１９Ａ、図１９Ｂ、図１９Ｃ、図１９Ｄ、図１９Ｅ、及び図１９Ｆは、付加的ガウスホワイトノイズチャネルについての様々なサイズのレート１／２ポーラ及び畳み込みポーラ符号の性能の比較を示すグラフであり、本明細書で同時に図１９と称される。
【図２０】図２０Ａ〜図２０Ｂは、３つのタイプの復号技術についての２１０（１０２４）ビットの符号サイズについての相関付けられたノイズが存在するときの性能曲線を提示する。
【図２１】図２１Ａ〜図２１Ｂは、３つのタイプの復号技術についての２１０（１０２４）ビットの符号サイズについての相関付けられたノイズが存在するときの性能曲線を提示する。
【図２２】図２２Ａ〜図２２Ｂは、３つのタイプの復号技術についての２１０（１０２４）ビットの符号サイズについての相関付けられたノイズが存在するときの性能曲線を提示する。
【図２３】図２３Ａ〜図２３Ｂは、３つのタイプの復号技術についての２１０（１０２４）ビットの符号サイズについての相関付けられたノイズが存在するときの性能曲線を提示する。
【図２４】本発明の教示に従った、例示的な通信システムの論理モジュール図である。
【図２５】本発明の教示に従った、例示的な方法のフローチャートである。
【図２６−１】図２６Ａ及び図２６Ｂは、本発明の教示に従った、例示的な方法のフローチャートであり、本明細書で同時に図３と称される。
【発明を実施するための形態】
【００１８】
Ａｒｉｋａｎによって発見されたチャネルポーラリゼーションの現象は、ｃｏｎｔｒｏｌｌｅｄ−ｎｏｔ（ＣＮＯＴ）ゲートによって生成することができる。制御ビットがターゲットビットに追加されることを理由に、それは、冗長的に符号化され、よって、ノイズに対してよりロバストになる。一方で、ターゲットビットの情報は、その値が場合によっては未知の制御ビットの値に依存する方式で修正されることを理由に、部分的に流失される。よって、チャネルは、より良好なチャネル及びより不良なチャネルに部分的にポーラライズされていると言われている。ポーラ符号の符号化回路は、このポーラリゼーション手順を反復することによって取得され、完璧なポーラリゼーションを漸近的に生成し、チャネルの一部は、誤りがなく、補間が完全にランダム化している。
【００１９】
この再帰的な性質を理由に、符号化回路は、スペクトル変換の幾何学的形式をとり、スペクトル変換では、ＣＮＯＴゲートは、異なる長さのスケール上の階層的配置に従い、（高速）フーリエ変換と同様に、線形符号化マトリックスが小さいマトリックスのクロネッカ積に分解されることができる。このケースでは、連続キャンセレーション復号器についてポーラリゼーションが定義され、そこでは、入力ビットの周辺確率がビット１，…，ｉ−１の前の知識により計算される。
【００２０】
量子多体物理の分野において開発された強力なグラフィカル計算に関する符号構築の幅広いファミリが前に開発されてきた。この分野では、ポーラ符号に関連付けられた符号化回路は、制限された形式の分岐ｍｕｌｔｉ−ｓｃａｌｅ  ｅｎｔａｎｇｌｅｍｅｎｔ  ｒｅｎｏｒｍａｌｉｚａｔｉｏｎ  ａｎｓａｔｚ（分岐ＭＥＲＡ）テンソルネットワークである。より正確には、それらは、「分岐ツリー」と呼ばれるオブジェクトをもたらす、自明なアイデンティティゲートであるテンソルの半分を有する分岐ＭＥＲＡネットワークに対応する。本開示では、焦点は、分岐ＭＥＲＡ符号ファミリに置かれ、分岐ＭＥＲＡ符号ファミリは、分岐ＭＥＲＡのトポロジにより符号化回路から取得された全ての符号を含み、多くの自明なゲートと共に特殊なケースとしてポーラ符号を含む。ポーラ符号は一連のポーラリゼーションステップを使用し、その各々が交差しない、有限サイズブロック上で動作するゲートの積から構成されるが、ここで考慮される一般化は、あらゆるポーラリゼーションステップにおいて畳み込み構造を使用することによってこのスキームの範囲を超える（畳み込みポーラ符号に積まれる）。
【００２１】
ポーラ符号により、Ａｒｉｋａｎは、非常に興味があり、改善及び一般化に対する更なる研究を促進する、対称チャネルについての実証可能な効率的且つ容量を達成する符号の最初の具体的な例を与えることができた。特に、ポーラ符号の制限が調査され、その注目に値する結果は、クロネッカ積への分解可能性を維持しながら、ポーラ符号の漸近ブロック誤り性能が小さい次元を有する下位のマトリックスを考慮して最適である、というものであった。実際に、次元は、漸近誤り指数を改善するために少なくとも１５に高まる必要がある。畳み込みポーラ符号は、より一般的なポーラリゼーション構造を支持して、ブロック構造制限ポーラリゼーションを放棄することによって、最適な振る舞いの調査を再開する。
【００２２】
畳み込みポーラ符号は、ポーラ符号の生成の１つの例を形成し、対数線形時間において収縮可能なテンソルを生成する連続キャンセレーション復号器を含むそれらの特性の多くを引き継ぐ。復号アルゴリズムが、小さい、定数倍だけ低速であり、チャネルポーラリゼーション及び誤り訂正性能の両方における著しい改善が達成可能であることが観察されている。ポーラ符号の重要な実用的な制限がそれらの重要な有限サイズ効果であり、畳み込みポーラ符号がより急峻なウォータフォール領域を示し、よって、そのような有限サイズ効果を抑制することが観察されている。
【００２３】
抽象的に、ＣＮＯＴなどのゲートは、α、β、γ、…と表される、特定の数のインデックスを有するテンソル
【数１】
2020515117.tif 000003
として見ることができ、α、β、γ、…の各々は、これ以降で、
【数２】
2020515117.tif 000004
であると推定される、有限セットにおける値をとる。インデックスの数は、テンソルのランクである。例えば、ＣＮＯＴゲートは、２つの入力ビットを表すインデックスα及びβ、並びに２つの出力ビットを表すδ及びγを有するランク４テンソルＮαβδγである。テンソルの値は、γ＝αであり、
【数３】
2020515117.tif 000005
のとき、Ｎαβδγ＝０、その他の場合は、Ｎαβδγ＝１によって与えられる。テンソルは、テンソルのランクに等しい頂点の程度を有する、頂点として、及びエッジとしてのそのインデックスとしてグラフィカルに表されることができる。その設定では、２つの頂点をつなぐエッジは、以下の式によって定義されたテンソル収縮を表す：
【数４】
2020515117.tif 000006
【００２４】
テンソル収縮は、マトリックス乗算の一般化である。（閉）グラフは、収縮された全てのエッジ、よって、スカラを有するテンソルネットワーク（ＴＮ）を表す。１つの開エッジ（頂点に接続されていない１つの端を有するエッジ）を有するグラフは、１つの収縮されていないインデックス、よって、ベクトルなどを有するテンソルネットワークを表す。そのようなオブジェクト、特に、それらのグラフィカル表現は、因子グラフとも呼ばれ、そこでは、いくつかの頂点は、変数として識別されてもよい。標準因子グラフは、開テンソルネットワークとのより良好な類似性をもたらす。
【００２５】
ここで、１６ビットについての一般化符号化回路を提供する、図１への参照が行われる。図１Ａ〜１Ｇの例では、論理ビットの入力が回路の最上部に入り、符号化されたメッセージが、底部に現れる。より容易に提示するために、入力信号の異なるビットにわたってＣＮＯＴゲートを「引き伸ばす」代わりに、入力信号の論理ビットが符号化回路の異なるレベルのＣＮＯＴゲートに搬送されるとして示される。当業者は、相互に交差する信号線が、それらの間の物理接続を示さないことを理解するであろう。明確化のために、図１は、一般化符号化回路についての異なるレベルのＣＮＯＴゲートを示す、図１Ａ〜１Ｇに分割されている。そこで使用されているレベルの選択に応じて、異なるより単純な符号化回路が提供されることができる。図１Ｂは、あらゆる符号化回路の一部である第１のレベルのＣＮＯＴゲート１０を提示する。第１のレベルのゲート１０が全ての符号化回路において使用されることを理由に、それは、全ての図１Ｃ〜１Ｇにおいて繰り返される。しかしながら、当業者は、レベルが共に使用されるとき、それらが過度に繰り返されないことを理解するであろう。
【００２６】
図１Ｂ〜１Ｆにおいて記述されるレベルから異なる符号化回路が構築されることができる。例えば、一般化ポーラ符号符号化回路は、図１Ｃに示され、第１のレベルのゲート１０及び第２のレベルのＣＮＯＴゲート２０を含む。図１Ｃ’は、異なる論理表現における図１Ｃと同一の回路を表す。図１Ｄは、第３のレベルのＣＮＯＴゲート３０を示す。一般化畳み込みポーラ符号符号化回路は、ＣＮＯＴゲート１０、２０、及び３０のレベルから構成される。図１Ｄ’は、本明細書で周期的畳み込みポーラ符号又は単純にポーラ符号とも称される一般化畳み込みポーラ符号符号化回路の異なる論理表現を表す。図１Ｅは、第４のレベルのＣＮＯＴゲート４０を示す。「１−２符号」符号化回路は、ＣＮＯＴゲート１０、３０、及び４０のレベルから構成されることができる。「１−２−１符号」符号化回路は、ＣＮＯＴゲート１０、２０、３０、及び４０のレベルから構成されることができる。図１Ｆは、第５のレベルのＣＮＯＴゲート５０を示す。「２−１−２符号」符号化回路は、ＣＮＯＴゲート１０、３０、４０、及び５０のレベルから構成されることができる。「２−１−２−１符号」符号化回路は、ＣＮＯＴゲート１０、２０、３０、４０、及び５０のレベルから構成されることができる。図１Ｇは、第６のレベルのＣＮＯＴゲート６０を示す。「１−２−１−２符号」符号化回路は、ＣＮＯＴゲート１０、３０、４０、５０、及び６０のレベルから構成されることができる。図２は、開境界を有する畳み込みポーラ符号の符号化回路のグラフィカル表現を示す。ポーラ符号は、周期的畳み込みポーラ符号のゲートの半分を含む。
【００２７】
提示される一般化は、より高い次元フィールド及びより大きな分岐率を有する符号に拡張する。それらのケースの多くでは、これは、カーネルについての非線形ゲートを使用する可能性を広げる。効率的なコーディング及び復号は、それらの拡張の全てに対して予期される。上記定義に従って、全ての分岐ＭＥＲＡ符号が、使用されるゲートの選択に応じたチャネルポーラリゼーションを示すわけではないことに留意されるべきである。
【００２８】
図１Ｄ’において示された畳み込みポーラ符号符号化回路など、符号の符号化回路を見ることは、復号問題をテンソルネットワーク（ＴＮ）収縮問題として計算し直すことを可能にする。図３Ａは、包括的な復号問題のＴＮ図（又は、因子グラフ）を表す。Ｎ個の入力ビットｘｉは、符号化回路Ｇを通る、ｋ個のデータビット及びＮ−ｋ個の凍結ビットの組み合わせである。受信される出力ビットｙｉ及び対称ノイズモデルＷを仮定すると、復号する目的は、データビットの最も可能性のある構成を判定することになる、非正規化確率
【数５】
2020515117.tif 000007
は、図３ＡのＴＮを収縮することによって与えられるが、これは、ｋの指数関数である計算複雑度を有する。図３Ｂでは、連続キャンセレーション復号器は、右から左への順序で入力ビットを反復的に判定する。ビットｉの相対的確率を判定するために、右へのビットは、設計によって、又は前の知識を使用することによって凍結され、左への状態に関する無知が完全に残り、「ｅ」は、均一な混合（１，１）を表す。図３Ｃでは、テンソルグラフは、相関付けられたノイズ（ビットのとの間で相関があるノイズモデルＷによって示されるような）の存在するときの順次復号を表す。
【００２９】
符号化回路Ｇは、Ｎ個の入力ビットを表すＮ個のインデックス及びＮ個の出力ビットを表すＮ個のインデックスを有する、ランク２Ｎテンソルであり、入力ビットのいくつかは０に固定（凍結）される。ビットを１に凍結しても機能し、ビットを０又は１に凍結することを決定することは、チャネルにわたる非対称ノイズが存在するとき、又は非対称ノイズを予期して正当化されてもよいことに留意されたい。最後に、単一のビットの値にわたる確率分布は、ビット値０を表すテンソル「０」＝（１，０）及びビット値１を表すテンソル「１」＝（１，０）を有する、ランク１テンソルとして表されることができる。それらのテンソルを仮定すると、観察された出力ｙ＝（ｙ１，…，ｙＮ）を仮定して、入力ビット文字列ｘ＝（ｘ１，…，ｘＮ）の確率が、図３に示されたＴＮとして表されることができる。
【００３０】
概して、全てのＴＮが効率的に収縮されることができるわけではない。テンソルＡがランク６を有し、テンソルＢがランク５を有する式（１）を参照して、それらの収縮から生じたテンソルＣは、ランク６＋５−２＝９を有する。よって、テンソルＡが２６個のエントリによって指定され、テンソルＢが２５個のエントリによって指定され、テンソルＣが２９＞＞２６＋２５個のエントリを含む。境界ランクテンソルから構成されたＴＮ（２つのビットゲートのみを有する回路）は、効率的に指定されることができる。しかしながら、ＴＮ収縮スケジュールの中間ステップにおいて取得されるテンソルは、非常に高いランクｒのテンソルであり得、よって、その収縮は、解決困難な量のデータ２ｒを生成する。中間テンソルランクを最小化する収縮スケジュールは、グラフのツリー幅を定義し、よって、ＴＮを収縮するコストは全体的に、そのツリー幅の指数関数である。
【００３１】
したがって、有限ツリー幅を有するＴＮを生成する符号化回路は、効率的に復号されることができる。これは、例えば、その対応するＴＮが単純なチェーンであり、したがって、定数ツリー幅を有する畳み込みポーラ符号のケースである。しかしながら、それは時に、図４に記述される、ＴＮを単純化する特殊回路アイデンティティを活用することによって、符号化回路がより大きなツリー幅を有するときでさえ、効率的に復号することが可能である。例えば、図４Ａは、制御ビット上で０エントリを有するＣＮＯＴゲートがアイデンティティに等しいことを示す。図４Ｂは、制御ビット上で１エントリを有するＣＮＯＴゲートがターゲットビット上でのＮＯＴゲートに等しいことを示す。そのような回路アイデンティティの組み合わせは、非常に複雑なＴＮを収縮するために使用されることができる強力なグラフィカル計算をもたらす。特に、順次キャンセレーション復号は、アイデンティティに正確に依存する効率的なＴＮ収縮としてこのグラフィカル計算において再計算されることができる。
【００３２】
量子多体物理、及び様々な古典的且つ量子誤り訂正符号のコンテキストにおいて開発されたいくつかのＴＮファミリの間での等価性が存在する。特に、関心の量を評価するための物理及びコーディング理論（例えば、物理における磁化、コーディング理論におけるビット尤度）において適用可能な計算技術は、同一であることが多い。ここで、特に興味があるのは、分岐ＭＥＲＡと呼ばれるＴＮであり、分岐ＭＥＲＡは、低エネルギーにおいて自由度の分離を示す、潜在的に高度に巻き込まれた物理システムの特性を理解する概念的及び数字上のツールの両方として物理において適用される。このＴＮを表すグラフは、ポーラ符号の符号化回路よりも豊富な構造を有するが、それはなお、効率的に収縮可能である。これは、ポーラ符号の一般化を可能にする主要な観察である。
【００３３】
分岐ＭＥＲＡ符号の定義は、符号化回路のトポロジに純粋に依存する。２つのサブレイヤ（又は、レベル）を有するポーラ及び畳み込みポーラ符号の特殊ケースについて、それらの定義は、以下の通りである。
【００３４】
定義１：以下のルールを使用してその符号化回路が再帰的に構築されることができる場合、及び再帰的に構築されることができる場合のみ、符号は、Ｎ＝２ｎビット（１…Ｎとラベル付けされる）にわたるポーラ又は畳み込みポーラ符号であると考えられる。Ｎ＝１の場合、自明な符号により開始する。サイズＮ＝２ｎの符号についての符号化回路は、論理チャネルをインタリーブし、以下の２つのビットゲートを回路の始めに追加することによって、サイズ２ｎ−１の２つの符号の符号化回路から構築されることができる。
【００３５】
図１Ｃにおいて前に言及されたように、図１Ｃは、ポーラ符号の符号化回路を提示し、図１Ｄ’は、２４＝１６サイトについての周期的境界を有する畳み込みポーラ符号の符号化回路を提示する。論理ビットは、回路の最上位に入り、符号化されたメッセージが、底部に現れる。
【００３６】
畳み込みポーラ符号について、２ｎ−１ＣＮＯＴゲートのサブレイヤ（又は、レベル）により開始し、ｉ番目のゲートは、ビット２ｉを２ｉ＋ｌ（ｉ≠２ｎ−１について）に接続する。最終ゲートは、ビットＮをビット１と接続する。このゲートが非自明である場合、畳み込みポーラ符号は周期的であると考えられる（そうでない場合、非周期的として、又は開境界を有するとして説明される）。ポーラ又は畳み込みポーラ符号のいずれかについて、次に、２ｎ−１ＣＮＯＴゲートを適用し、ｉ番目のゲートは、ビット２ｉ−１を２ｉに接続する。更なるサブレイヤ（又は、レベル）を追加することは、畳み込みポーラ符号の更なる一般化につながる。
【００３７】
簡易化を目的に、２つのレベル（又は、サブレイヤ）畳み込みポーラ符号の例のみが、符号化及び復号の観点で更に議論される、示されるように、効率的な復号は、テンソルネットワークを収縮することによって実行され、畳み込みポーラ符号についての例が提供される。当業者にとって、対応するテンソルネットワークを収縮することによって、一般化符号化回路が効率的に復号されることができることが明白である。一般化符号化回路についての収縮ルールは、畳み込みポーラ符号に対して適用可能な１つの直線的な一般化によって取得される。
【００３８】
Ｎビットにわたる畳み込みポーラ符号についての符号化回路は、Ｎｌｏｇ２Ｎとしての計算コストスケーリングにより適用されることができ、並列処理が考慮されるとき、ｌｏｇ２Ｎとしての時間スケーリングを要するにすぎない。ポーラ符号を使用して符号化する２ビットゲートの総数は、単純にＮ／２ｌｏｇ２Ｎである。周期的畳み込みポーラ符号は、Ｎ  ｌｏｇ２Ｎの総数に対してなされる、各々のレイヤにおいて導入される多くのゲートと比べて正確に２倍を有する。構築から、ゲートの１つのみの（ポーラ）又は２つの（畳み込みポーラ）レイヤが、符号サイズが２倍になる都度適用され、よって、回路深さが対数的であり、ポーラ符号に対してｌｏｇ２Ｎ及び畳み込みポーラ符号に対して２ｌｏｇ２Ｎであることが明らかである。
【００３９】
畳み込みポーラ符号は、周期的又は開境界条件により定義されることができる。開境界符号は、ｎ番目のレベルのポーラリゼーションにおいてビット２ｎをビット１に接続するゲートを単純に取り除くことによって、周期的境界符号から取得される。そのような境界条件は２つの別個の符号化回路につながり、連続キャンセレーション復号の下、周期的及び開境界畳み込みポーラ符号は、ほぼ同一になることが述べられている。当業者は、周期的畳み込みポーラ符号と比較されるとき、開境界畳み込みポーラ符号に対して小さな修正が適用される必要があることを認識するであろう。
【００４０】
復号問題は、その解決手法を著しく簡易化するために、連続キャンセレーションスキームを必要とする。連続キャンセレーション復号器では、目標は、左への入力ビットの完全な無知、及び右への入力ビットの値にける総信頼度を推定することによって（それらが符号に凍結されることを理由に、又はそれらが前に復号されていることを理由にのいずれか）、右から左へ移動する、その時点での単一のビットを判定することである。包括的な、最適な復号器は、最大尤度を有するコードワードを特定し、すなわち、観察された出力ｙ＝（ｙ１，…，ｙＮ）、誤りモデルＷ、及び凍結ビットのセットＡｃを仮定すると、最も可能性のある入力ｘ＝（ｘ１，…，ＸＮ）を特定する。
【００４１】
しかしながら、多くの符号について、最も可能性のあるコードワードを正確に判定することは困難な問題であり、近似の範囲（通常、反復的な）が使用される。連続キャンセレーション復号器は、位置ｉにおいて最も右の非凍結ビットにより開始し、確率を最大化することによってその値を判定する：
【数６】
2020515117.tif 000008
【００４２】
上記計算を目的として、ｉの左へのビット（すなわち、ｉ＋ｌ，ｉ＋２，…Ｎ）は、それらが凍結ビットである場合でさえ、未知であると考えられる。ｉの右へのビット（すなわち、ｉ−ｌ，ｉ−２，…Ｎ）は、それらが凍結されることを理由に、又はそれらが前のステップで復号されたことを理由にのいずれかにより既知である。この点で、連続キャンセレーション復号器は、あらゆるステップにおいて全ての利用可能な情報を利用しないことを理由に、最適な復号器ではない。ビットが判定されると、連続キャンセレーション復号器は、完全なメッセージが判定されるまで、次の非凍結ビットに進む、などである。
【００４３】
ＣＮＯＴゲートは、いくつかの状態において非常に単純なアクションを有し、その結果、結合分散へのいずれのも相関を導入しない。回路アイデンティティは、図４において前に導入されており、分散「０」、「１」、及びｅにおいてＣＮＯＴゲートのアクションを定義する。概して、同様のアイデンティティは、全ての反転可能（すなわち、決定論的な、１つごとの）ゲート、更には非線形ゲートに対して保持する。それらのアイデンティティをポーラ符号及び畳み込みポーラ符号に適用することが、莫大な簡易化をもたらす。実際に、畳み込みポーラ符号について図５において例示されるように、ＣＮＯＴゲートのほとんどが除去される。図５の例では、特定のビットが判定され、復号計算シンプリファイアが、グラフを簡易化するために適用される。認識することができるように、簡易化の効果は、実際に、値（４番目のビットを参照）を変更するために、前に判定されたビットにつながることがある。残りのゲートの数は、Ｎｌｏｇ２ＮからＮに減少する。
【００４４】
ポーラ符号について、符号における単一のビットを証明することは、２つのより小さい符号、下の１つのレイヤにおける単一のビットを効率的に証明することをもたらす。これは、畳み込みポーラ符号についてのケースではないが、更なるビットが考慮されるときに現れる同様の構造についてのケースであり、１つのレイヤにおける３つのビットの分散を証明することが、下の２つのより小さい符号における３つのビットの分散を証明することにマッピングされることができる。Ｎ個のビットの畳み込みポーラ符号上で連続キャンセレーションを使用してビットｉ、ｉ＋１、及びｉ＋２を復号するために、厳格に５Ｎゲート未満がテンソルネットワーク図に残る。
【００４５】
畳み込みポーラ符号の構築に起因して、奇数及び偶数サイトは、２つの効果的な畳み込みポーラ符号に分割されることができ、その各々は、上のＣＮＯＴに接続された３つのビットを有する。左へのビットは未知であり、右へのビットは、全て判定され、よって、処理が反復する。別の５ゲートは、「奇数」及び「偶数」下位符号の両方に残る。底の２つのレイヤについて、各々の符号におけるビットの数は、６よりも少なくなり、よって、反復が終了する。第２の底レイヤにおいて、全部で４つのゲートのみが存在し、最低のレイヤにおいて、まさに２つが存在し、両方のケースでは、５未満である。ゲートの総数は、５（Ｎ−１）だけ上限が定められる。
【００４６】
ここで、テンソルネットワーク図が簡易化されており、それは、効率的に収縮されることができることを示されたままでいる。ゲートキャンセレーションは、上から下に行われるが、テンソルネットワーク収縮は、下から上に行われる。これがどのように行われるかを確認するために、図６Ａ、６Ｂ、７Ａ、７Ｂ、８、及び９（本明細書で図６〜図９と称される）に記述される、いくつかの収縮アイデンティティを強調することが有益である。図４の回路アイデンティティとは対照的に、図６〜図９の収縮アイデンティティは、それらが収縮されているゲートの性質に依存しないが、下位のグラフ構造にのみ依存するという点で、グラフィカルである。例えば、それらの収縮アイデンティティにおいて使用されるＣＮＯＴゲートは、いずれかの他のランク４テンソルによって置き換えられてもよく、アイデンティティを保存してもよい。図５の図の底から開始して、上方に作用するそれらのグラフィカルアイデンティティを繰り返して適用することが、効率的な収縮スケジュールを得る。記述される収縮アイデンティティは、任意のテンソルに適用される。テンソルｑは、考慮されている特定のテンソルネットワークに依存する。図６〜図９では、テンソルｑは、それが減少することができるオープンビットの数を搬送する。
【００４７】
畳み込みポーラ符号は典型的には、最低レイヤにおいて２ビットを組み合わせる。分散は次いで、３ビットの分散に組み合わされることができる。３ビットごとの変換は、分岐ＭＥＲＡの自然な固定点である。入力ビットが境界に近いとき、下位レイヤは、３ビットを１つに移動する前に、いくつかの２ビットごとの変換を行う。Ｎ個のビット畳み込みポーラ符号における連続キャンセレーション復号の単一のステップは、Ｎにおいて線形的な計算コストを有する。したがって、連続キャンセレーション復号の完全な実行は、ポーラ及び畳み込みポーラ符号の両方に対し、計算コストＮ２ｌｏｇ２により実行される。
【００４８】
連続キャンセレーション復号の全ての勾配は、連続キャンセレーション復号器につながる収縮ステップをメモリに記憶することによって、減少したコストＮｌｏｇ２Ｎにおいて実行されることができる。実際に、ビットｉ及びビットｉ−１の連続キャンセレーション復号を表すＴＮは、ｌｏｇ２Ｎ位置においてのみ異なる。よって、ビット
【数７】
2020515117.tif 000009
の復号につながる計算の結果は、メモリに記憶される場合、ビットｉを復号する複雑度は、単にｌｏｇ２Ｎであり、全てのＮビットを復号する総複雑度Ｎｌｏｇ２Ｎにつながる。
【００４９】
ポーラリゼーションステップにおいて使用されるＣＮＯＴゲートが、（左及び右それぞれの）消去レート
【数８】
2020515117.tif 000010
を有する２つの消去チャネルを、消去レート
【数９】
2020515117.tif 000011
を有する２つの新たな実効消去チャネルに変換することが示されてきた。変換は、畳み込みポーラに対してはわずかに複雑であるが、にもかかわらず、効率的に実行されることができる。
【００５０】
消去チャネルの下、ビットの値は、既知であるか又はそうでないかのいずれかである。わずかに複雑な状況が考慮されることになる。例えば、２つのビット値の合計は、既知であってもよく、既知でないかのいずれかである、概して、知識の状態は、線形的な制約によって要約されることができる。上記例では、制約は、（１，１）・（ｘ１，ｘ２）＝ａとして表現される。概して、ｎ個のビットの補正について、知識の状態は、Ｃｘ＝ａと記述されることができ、Ｃは、ａｋｘｎマトリックスである、ｋ≦ｎであり、ａは、ｋビットベクトルである。ベクトルａの実際の値は、目的が、量が既知であり、又はそうでないかを判定することであり、その実際の値を判定することではないので、分析において重要ではないことに留意されたい。
【００５１】
図７Ｃに例示される畳み込まれたポーラ変換を考える。それらは、入力として、２つの３ビットの確率分布ｐａ及びｐｂをとり、それらは、６ビットの分散
【数１０】
2020515117.tif 000012
に組み合わされることができ、３つのＣＮＯＴゲートからの線形的な反転可能変換Ｍを実行する。Ｍの適用の前に、６つの入力ビットの知識の状態が式Ｃｘ＝ａによって説明されたことを仮定する。次いで、出力ｙ＝Ｍｒの知識の状態は、Ｃ’ｙ＝ａによって説明され、Ｃ＝ＣＭ−１である。図７Ｃの左の変換に焦点を当てると、線形的な変換の後、最初の２つのビットは、既知の値ｘ１及びｘ２に固定され、最後のビットが無視される。知識の状態に関するこの効果を理解するために、マトリックスＣは、以下の行操作を使用して、標準的な形式に入れられることができる：
【数１１】
2020515117.tif 000013
【００５２】
それらの行操作では、下付き文字は、マトリックスのサイズを示し、ｕ＝０又は１であり、１ｕは、ｕ×ｕアイデンティティマトリックスを表す。マトリックスＢは、ビットｙｉ、ｙ４、及びｙｓについての知識の新たな状態を表す。同様の理由付けは、図７Ｃの右への変換に適用され、差異は、最初のビットのみが固定され、最後の２つのビットが無視されることである。そのケースでは、ｕは、値０、１、又は２をとることができ、次元は、Ａ（ｋ−ｕ）ｘ１及びＤｕｘｉに調節される。
【００５３】
行操作の下で別個の、ｋ≦３についての次元ｋ×３の１６個のマトリックスＣが存在する。消去チャネルの学習は、上記説明されたように、確率を知識のそれらの１６個の考えられる状態に割り当てること、及び畳み込みポーラ変換を通じてそれらの分散を進化させることに基づいている。最初に、各々のビットは、確立ｐにより消去され、よって、３ビットの補正は、知識の状態の以下の分散を有する：
【数１２】
2020515117.tif 000014
【００５４】
他の９つ全てのｐｊ＝０である。知識Ｂａ及びＢｂのペアを、確率ｐａｐｂを有する知識
【数１３】
2020515117.tif 000015
の６ビットの状態に組み合わせ、図７Ｃの右又は左に対応する手順のいずれかを適用して、知識Ｂの新たな状態を作り出すことによって技術が進歩する。次いで、知識の状態に関する結果として生じる変換が判定されることができる。より具体的には、消去チャネルの下での単一のビットｘ１について、知識の２つの状態のみが存在し、Ｘｉの値が既知又は未知のいずれかである。２つのビットｘ１、ｘ２（線形回路が消去チャネルに続く下で）について、知識の５個の考えられる状態が存在し、両方の値｛ｘ１，ｘ２｝が既知であり、単一の値｛ｘ１｝又は｛ｘ２｝が既知であり、それらの合計｛ｘ１＋ｘ２｝が既知であり、又は既知であるものがない。５個の異なる状態の各々は、発生するその自身の確率を有する。線形回路（ＣＮＯＴなど）の適用は、単一ビットの知識状態ｘ１、ｘ２、及びｘ１＋ｘ２、並びにそれらの関連する確率の順序を変える。概して、知識のそれらの状態は、消去チャネルが自明的に量子化する事実に対応する。
【００５５】
連続キャンセレーションの下での畳み込みポーラ符号の例では、復号は、３に等しいツリー幅を有するテンソルネットワークとして表されることができる。したがって、３ビットを上回る知識の状態が扱われることになる。便宜のために、全ての１５個の状態が以下で列挙される：
【数１４】
2020515117.tif 000016
【００５６】
まとまった畳み込みポーラ符号の各々のレイヤの下での、状態ｓｉと関連付けられた確立ｐｉの変換が判定されることができる（例えば、図６Ａに続いて）。ポーラ符号と同様に、畳み込みポーラ符号の各々のレイヤは、２つの同一のチャネルを組み合わせるが、このケースでは、それらは、３ビットのチャネルである。復号されている３つの論理ビットの位置によって与えられる２つの別個の変換が存在する。それらは、図６Ａの左及び右に例示される。それらの変換は、
【数１５】
2020515117.tif 000017
2020515117.tif 000018
である。
【００５７】
消去確率の評価は、符号に関連付けられたテンソルネットワークの収縮スケジュールに従うそれらの変換を反復する。
【００５８】
そのようにして、同様の手順が図６〜図９に示された他の組み合わせに対して導出されることができる。この手順を使用して、独立した消去確率ｐが入力として与えられると、出力ビットｘｉが消去される確率ｐｉは、ビットｘｉｉ＜ｊが消去されていない事実を条件に、正確に計算されることができ、すなわち、連続キャンセレーション復号がされると、ビットｊが最初に消去されることになる確率が正確に計算されることができる。
【００５９】
相関付けられた誤りが存在するとき、畳み込みポーラ符号についての復号手順も提供されることができる。示唆される技術は、ポーラ符号、畳み込みポーラ符号、及び分岐ＭＥＲＡテンソルネットワークに基づくそれらの一般化に適用可能である。いずれの有限状態メモリチャネルにも技術が適用されることができる。同等に、それは、チェーンのトポロジを有するテンソルネットワークによって説明されることができるいずれかのノイズモデルに適用可能である。モデルは、２つのタイプの異なるテンソルを伴う。遷移確率（確率論的マトリックス）、ランク２テンソルを表す１つ、及びマルコフ過程の状態を表す１つは、ランク３テンソル（境界についてのランク２）によって説明する。図１０は、テンソルネットワークとしてのノイズの論理表現を提供する。２つのタイプのボンド、すなわち、物理ボンド及び論理ボンドは、テンソルネットワークにおいて表される。状態テンソルごとに物理ボンドが存在する。また、物理ボンドの次元は、アルファベットの次元に等しい。符号のサイズは、物理ボンドの数を与える。論理ボンドは、遷移マトリックス（円）を状態テンソル（正方形）とリンクさせる。論理ボンドの次元は、チャネルのメモリ状態の数を表す。
【００６０】
いくつかのノイズモデルが相関付けられ、所与のビットが影響されるとき、隣接ビットも影響される（例えば、バーストノイズチャネル）可能性が高いことを意味する。相関付けられたノイズの下での提案される復号技術は、ノイズモデルテンソルネットワークの収縮によって概略的に表されるテンソルネットワーク収縮アルゴリズム及び連続キャンセレーションスキームを使用した符号符号化回路に基づいている。例として、図１１は、サイズＮ＝１６ビットの畳み込みポーラ符号について位置８にあるビットの復号に関与するテンソルネットワークを提示する。
【００６１】
技術における第１のステップは、回路の最上部におけるビットの状態の伝播である（ツリーテンソルネットワークがノイズモデルに伴う）。第２のステップでは、図１２に詳述される単純な収縮が、下から上に適用される。第２のステップでは、目的は、単一の確率ベクトルを取得するために、グラフを簡易化することである（図１２Ｄ）。第３のステップでは、完全なメッセージが復号されるまで、連続キャンセレーション復号器に従って反復が実行される。
【００６２】
復号技術の例は、位置５にあるビットが復号されることになる、サイズＮ＝８ビットのポーラ符号についての図１３Ａ〜図１３Ｆに例示される。図１３Ｆでは、結果は、位置５にあるビットの値が０である確率及び位置５にあるビットの値が１である確率を示す確率ベクトルである。位置５におけるビットの値を判定するために最高確率が使用され、位置６にあるビットにより復号が反復され、ビット１から５までの知識を適用する。
【００６３】
相関付けられたノイズが存在するときの復号戦略は、いずれかの有限状態メモリ誤りモデルに対して適合される。具体性のため、２つの状態モデルが図１４に例示される。記述されるモデルは、Ｇｉｌｂｅｒｔ−Ｅｌｌｉｏｔチャネルに基づいている。このノイズは、一定遷移確率を有する２状態モデルマルコフチェーンである。モデルは、右パラメータを使用するときに、バーストノイズをシミュレートすることを可能にする。このマルコフチェーンは、Ｇｏｏｄに対して状態Ｇであり、Ｂａｄに対して状態Ｂである２つの状態に基づいている。チャネルに沿ってメモリの２つの内部状態として、２つの状態Ｇ及びＢを考えることができる。チャネルが状態Ｇにあるとき、伝送されるビットは、低誤り率を有する二値対称チャネルＢＳＣ（ｈＧ）によって影響される。チャネルが状態Ｂにあるとき、伝送されるビットは、よりノイズが高い、すなわち、ｈＧ＜ｈＢであるＢＳＣ（ｈＢ）によって影響される。チャネルのメモリは、時間ステップごとに確率ＰＧ→ＢによりＧｏｏｄからＢａｄに遷移し、確率ＰＢＢ→ＧとよりＢａｄからＧｏｏｄに遷移する。
【００６４】
遷移確率を仮定すると、確率論的マトリックスが定義されることができ、それは、状態Ｇ及びＢにおいて費やされた時間の一部を発見することが可能になる。それを行うために、処理の定常分布が必要である。それは、固有値λ＝１と関連付けられた固有ベクトルに対応する。Ｐ（Ｂ）が平均して状態Ｂにおいて費やされた時間の割合であるとする。次いで、チャネルの平均誤り確率は、ｈＰ（Ｂ）によって単純に与えられる。次いで、Ｐ（Ｂ）＝ＰＧ→Ｂ／（ＰＧ→Ｂ＋ＰＢ→Ｇ）であり、その結果、平均誤り確率が、Ｐｅ＝ｈＰＧ→Ｂ／（ＰＧ→Ｂ＋ＰＢ→Ｇ）によって与えられる。
【００６５】
相関強度を量子化するために、いくつかのメトリックが使用されてもよい。このノイズモデルでは、ｌＢが、本明細書でバースト長と称される状態Ｂにある連続滞在の長さを測定するランダム変数として定義される。ランダム変数は、幾何分布により定義され、その結果、
【数１６】
2020515117.tif 000019
を有する。
【００６６】
有益となることができる別のメトリックは、状態ＧとＢとの間の遷移Ｎｔの平均数である。この数は、＜Ｎｔ＞＝２ＮＰＧ→ＢＰＢ→Ｇ／（Ｐ０Ｇ→Ｂ＋ＰＢ→Ｇ）によって与えられる。
【表１】
2020515117.tif 000020
【００６７】
数値シミュレーションの間、低ノイズ型及び高ノイズ型の両方におけるバーストノイズモデルが測定されている。低ノイズ型では、Ｂａｄのｐ確率は、ｈ＝０．１に設定される。高ノイズ型では、ｐ確率は、状態Ｂａｄに対してｈ＝０．５に設定される。両方の型では、本明細書で提案される復号技術は、標準的なポーラ符号構築と共に、インタリーブ構築よりもはるかに優れている。加えて、観察されるフレーム誤り率（ＦＥＲ）及びビット誤り率（ＢＥＲ）は常に、本明細書で提示される復号技術を使用するときよりもはるかに低い。
【００６８】
図２０Ａ〜２０Ｂ、図２１Ａ〜２１Ｂ、図２２Ａ〜２２Ｂ、及び図２３Ａ〜２３Ｂは、３つのタイプの復号技術についてのチャネルのバースト長さ及び遷移に従った、２１０（１０２４）ビットの符号サイズについての相関付けられたノイズが存在するときの性能曲線を提示する。図２０Ａ〜２０Ｂ及び図２１Ａ〜２１Ｂ上のグラフについて、ｂａｄ状態における誤りの確率ｈ＝０．５であり、ｇｏｏｄ状態における誤りの確率ｈ＝０である。図２２Ａ〜２２Ｂ及び図２３Ａ〜２３Ｂ上のグラフについて、ｂａｄ状態における誤りの確率ｈ＝０．１であり、ｇｏｏｄ状態における誤りの確率ｈ＝０である。全てのグラフについて、３つのタイプの復号技術は、１）相関付けられたポーラ符号（相関付けられたノイズに適合され、相関付けられたノイズが存在するときの）、２）相関付けられたノイズが存在するときのポーラ符号（ｐｃ）、及び３）ランダムインタリーバが追加されるときのポーラ符号、である。
【００６９】
図１Ｄ’の例において記述された１つに類似するが（ＣＮＯＴゲート１０、２０、及び３０のレベルから構成される）、１０２４ビットに一般化される畳み込みポーラ符号がここで議論される。上記議論から当業者が理解するように、チャネルの特性が予測され、又は既知であると、上記技術を使用して、凍結ビットの各々の最も効率的な位置を判定することが可能である。例えば、次の表は、ビットごとに０．５に等しい対称的な誤りの確率を有するチャネルにわたって、１０２４ビットから５１２ビットのメッセージをコーディングするときの最悪の位置を提供する。言い換えると、以下の表は、５１２個の凍結ビットの位置を提供する。参照を容易にするために、位置番号が順序付けられており、複数の列にわたって提示される。
【表２】
2020515117.tif 000021
【００７０】
また、おそらく、本明細書で記載された特定のビットは、凍結されていないとして示されるビットのいくつかに非常に近い誤りの確率を有すること、及びそれらのビットを相互変更するそれらを変更することが、全体的な性能に関してほとんど無視できる影響を有することに留意することが重要である。これを例示するために、上記提供されたような同一の位置番号が再度提供されるが、今度は、最悪の位置番号から最良の位置番号の順である。再度、参照を容易にするために、それらは、複数の列にわたって提示される。
【表３】
2020515117.tif 000022
【００７１】
最初の１７８ビット（ビット番号１７８まで）及び最後の１２６ビット（ビット番号８９９以降）は、０に凍結され、残りの凍結ビットは、それらの間で散在することに留意することができる。しかしながら、最初の１７８ビットは、他の残りの凍結されていないビットと比較して区別することが困難である誤りの確率を有し、したがって、誤りの変化する確率ではなく数値順で選択されている。
【００７２】
１０２４ビットにわたって一般化された、前に議論された「２−１−２符号」（ＣＮＯＴゲート１０、３０、４０、及び５０のレベルから構成される）についての以下の表において２つ目の例が提供される。再度、ビットごとに０．５に等しい対称的な誤りの確率を有するチャネルにわたって一般化される「２−１−２符号」について１０２４ビットから５１２ビットのメッセージをコーディングするときの最悪の位置が提供される。再度、参照を容易にするために、位置番号が順序付けられており、複数の列にわたって提示される。
【表４】
2020515117.tif 000023
【００７３】
図１Ｃ及び１Ｃ’に記述された、前に議論されたポーラ符号（ＣＮＯＴゲート１０、２０のレベルから構成される）についての３つ目の例が以下の表に提供される。再度、５１２ビットのメッセージを、１０２４ビットからであるが、今度は、遷移の確率Ｐｇｂ＝０．０１（ｇｏｏｄからｂａｄに）及びＰｂｇ＝０．０４（ｂａｄからｇｏｏｄに）によりビットごとにｂａｄ状態における誤りの確率が０．５であり、ｇｏｏｄ状態における誤りの確率が０である、メモリ効果（相関付けられたノイズ）を示すチャネルにわたってコーディングするときの最悪の位置が提供される。再度、参照を容易にするために、位置番号が順序付けられており、複数の列にわたって提示される。
【表５】
2020515117.tif 000024
【００７４】
もちろん、当業者は、それらの３つの表が何千もの確率から選択されたいくつかを表すにすぎないことを容易に理解するであろう。しかしながら、凍結ビットの位置を判定する方法は、一般化されることができる。最初に、チャネル帯域幅が判定される必要がある。本明細書で例示される一般化された畳み込みポーラ符号は、２ｎの数のビットを上回って最良に搬送されるが、適応される符号器及び復号器は、いずれかの特定の数のビットに対して設計される。例えば、一般化された畳み込みポーラ符号のビットロスの許容度を仮定すると、１つは、チャネル帯域幅よりも「広い」符号器を設計し、続いて、伝送の間に損失したものとしての「追加」ビットを考慮する（例えば、６５００ビット幅のチャネルについての１０２４ビット符号器又はｌ０００ビット幅チャネル又は８１９２ビット符号器）。２つ目に、チャネル帯域幅とは離れて、メッセージについてのビットの数が判定される必要がある（すなわち、メッセージビットがいくつかであるか）。チャネル帯域幅を考慮すると、凍結ビットの数が計算されることができる。チャネルについての消去の確率を提供する判定が必要とされる（例えば、任意とすることができるが、実際のチャネルの振る舞いにできるだけ近くであるべきである）。いくつかのケースでは、実際のチャネルは、メモリ効果を使用して最良に表され、メモリ効果は次いで、状態（ｇｏｏｄ又はｂａｄ）に応じて、並びにｇｏｏｄ状態とｂａｄ状態との間、及びｂａｄ状態とｇｏｏｄ状態との間の遷移の確率に応じて、チャネルについての消去の異なる確率を提供する。実際のチャネルは、消去チャネルとして最良に特徴付けられてもよく、又は特徴付けられなくてもよいが、それにも関わらず、本実施形態の目的のためにそのように特徴付けられてもよい。３つ目に、（一般化された）ポーラ符号化回路及び同等の復号器がチャネルについての消去特性により共に判定されると、最悪の位置は、所与の数のメッセージビットに対して規則的に判定されることができる。
【００７５】
ポーラ符号及びより一般的に、一般化された畳み込みポーラ符号は、制御チャネルについてのチャネルコーディング機構として特に適合されてもよい（例えば、５Ｇ標準において）。異なる（一般化された）ポーラ符号符号化及び復号スキームがサポートされてもよく、並びに／又はモバイルデバイスとコアネットワークとの間の通信に対して利用可能にされてもよいことが考えられる。アップリンク及びダウンリンク伝送に対して単一の（対称的な）コーディング及び復号スキームが使用されてもよく、又は例えば、コアネットワークと比較してモバイルノードの異なる物理能力を仮定すると、異なる方向において異なるスキームが使用されてもよい。モバイルデバイス及びコアネットワークはまた、適切なスキーム（例えば、より良好に適合したスキームを更新する能力により補完されたデフォルトのスキーム）の選択をネゴシエートすることが可能であってもよい。代わりに又は加えて、スキームは、コアネットワークによって課されてもよく、又はモバイルデバイスによって課されてもよい（例えば、コーディング／復号能力についての物理的制限）。スキームはまた、コアネットワーク及び／又はモバイルデバイスによる測定された特性（例えば、無線特性及び／又は応答性メトリックなど）に基づいて選択されてもよい。すなわち、コアネットワークは、特定のモバイルノード、又は一般的に、所与の基地局を囲むモバイルノード、又は更に一般的に、１つ以上の基地局コントローラについての基地局を囲むモバイルノードによる測定された性能に基づいて最良のスキームを動的に判定する責任をおってもよい。
【００７６】
図２４は、本発明の教示に従った、１つ以上の電気通信（２つの電話の間の会話、測定装置によるテレメトリデータ収集、クラウドサーバからダウンロードされたデータ、２つの地上局の間又はリモートスペースクラフトとのサテライト通信など）を可能にする例示的なコンピュータ電気通信システム１０００の論理モジュール表現を示す。コンピュータ電気通信システム１０００は、相互作用コンピュータシミュレーションの１つ以上に関与してもよい、接続されたデバイス１１００を含む。
【００７７】
図１の記述される例では、接続されたデバイス１１００は、メモリモジュール１１２０、プロセッサモジュール１１３０、及びネットワークインタフェースモジュール１１４０を含む。プロセッサモジュール１１３０は、各々が１つ以上のプロセッサコアを含む、１つ以上のプロセッサコア又はプロセッサのアレイを有する単一のプロセッサを表してもよい。一部の実施形態では、プロセッサモジュール１１３０はまた、専用コーディングユニット１１３２を含んでもよい。例えば、コンピュータ電気通信システム１０００が、予想されるネットワーク性能（例えば、５Ｇ要件を参照）を維持するために広範囲のコーディング能力（すなわち、品質及びスループット）を必要とする、符号集中通信標準を実装するとき、専用コーディングユニット１１３２が必要とされることがある。一部の実施形態では、複数の接続されたデバイス１１００、１６００、及び／又はネットワークノード１２００の各々は、専用コーディングユニット１１３２と同様の専用コーディングユニットを有するプロセッサモジュールを含む。専用コーディングユニット１１３２は、例えば、コーディングプロセッサ又はコーディングのために予約された別のプロセッサの予約された部分であってもよい。専用コーディングユニット１１３２はまた、ランタイムにおいて選択可能な、１つよりも多いコーディングスキームを選択的にサポートしてもよい。メモリモジュール１１２０は、様々なタイプのメモリ（異なる標準化された又は異なる種類のランダムアクセスメモリ（ＲＡＭ）モジュール、メモリカード、リードオンリメモリ（ＲＯＭ）モジュール、プログラム可能ＲＯＭなど）を含んでもよい。ネットワークインタフェースモジュール１１４０は、他のネットワークノードと通信するために使用されることができる少なくとも１つの物理インタフェースを表す。ネットワークインタフェースモジュール１１４０は、１つ以上の論理インタフェースを通じて、接続されたデバイス１１００の他のモジュールに視認可能にされてもよい。ネットワークインタフェースモジュール１１４０の物理ネットワークインタフェース（複数可）及び／又は論理ネットワークインタフェース（複数可）１１４２、１１４４、１１４６、１１４８によって使用されるプロトコルの実際のスタックは、本発明の教示に影響を与えない。本発明のコンテキストにおいて使用可能なプロセッサモジュール１１３０、メモリモジュール１１２０、及びネットワークインタフェースモジュール１１４０の変形が、当業者によって容易に明らかである。
【００７８】
接続されたデバイス１１００の異なるモジュールの間でデータを交換する手段の例として、バス１１７０が記述される。本発明は、それらの間で情報を交換する異なるモジュールによって影響されない。例えば、メモリモジュール１１２０及びプロセッサモジュール１１３０は、本発明の教示に影響を与えることなく、並列バスによって接続されてもよいが、直列接続によっても接続されてもよく、又は中間モジュール（図示せず）を含んでもよい。
【００７９】
同様に、メモリモジュール１１２０及び／又はプロセッサモジュール１１３０の明確な言及が様々な実施形態の説明を通じて行われていないが、当業者は、そのようなモジュールが本発明に関連してルーチンと共に革新的ステップを実行するために接続されたデバイス１１００の他のモジュールと共に使用されることを容易に認識するであろう。
【００８０】
接続されたデバイス１１００はまた、１つ以上のディスプレイスクリーン（複数可）を含むグラフィカルユーザインタフェース（ＧＵＩ）モジュール１１５０を含んでもよい。ＧＵＩモジュール１１５０のディスプレイスクリーンは、１つ以上のタッチ又はパッシブスクリーンに分割されてもよいが、ユーザ位置にアクセス可能とされた平面及び／又は湾曲タッチ又はパッシブスクリーンのいずれかの組み合わせであってもよい。
【００８１】
コンピュータ電気通信システム１０００は、様々なシステム及びシステム１０００のサブシステムに関連するデータを含み、更に、１つ以上の通信が処理されている間に動的データを記録してもよい、記憶システム１５００を含む。図２４は、接続されたデバイス１１００の別個のデータベースシステム１５００Ａ、別個のモジュール１５００Ｂ、又は接続されたデバイス１１００のメモリモジュール１１２０のサブモジュール１５００Ｃとしての記憶システム１５００の例を示す。記憶システム１５００はまた、接続されたデバイス１６００／ネットワークノード１２０上で記憶モジュール（図示せず）を含んでもよい。記憶システム１５００は、異なるシステムＡ、Ｂ、Ｃ及び／若しくはデバイス１１００、１６００、１２００にわたって分散されてもよく、又は単一のシステムにあってもよい。記憶システム１５００は、１つ以上の論理又は物理であると共に、ローカル又はリモートのハードディスクドライブ（ＨＤＤ）（又は、それらのアレイ）を含んでもよい。記憶システム１５００は更に、標準化されたインタフェース若しくはプロプライアタリインタフェースによって、又はネットワークインタフェースモジュール１１４０を介して接続されたデバイス１１００にアクセス可能とされたローカル又はリモートデータベースを含んでもよい。本発明のコンテキストにおいて使用可能な記憶システム１５００の変形が、当業者にとって容易に明らかである。
【００８２】
図１の記述された例では、コンピュータ電気通信システム１０００は、ネットワーク１４００を通じて接続されたデバイス１１００と通信してもよい、ネットワークノード１２００及び任意選択の接続されたデバイス１６００を示す。ネットワークノード１２００は、ネットワーク１４００への接続されたデバイスの接続性の異なる態様の責任を負うネットワーク１４００のコアネットワークの一部である。接続されたデバイス１１００は、接続されたデバイス１６００又は別のデバイス及び／若しくはサーバ（図示せず）との進行中の通信に関連付けられてもよい。接続されたデバイス１１００はまた、ネットワーク１４００への接続（例えば、制御関連データ）を維持する目的でネットワークノード１２００と通信してもよく、ユーザ−コンテンツデータ通信に関与するとき、別のネットワークノード（図示せず）と通信してもよい。そのようにして、他のコンピューティングデバイス（複数可）（図示せず）が関与してもよく、更に、本明細書で示唆されるコーディングスキームを使用してもよい。異なるデバイスはまた、本発明の教示に影響を与えることなく、１つ又は複数の実際のユーザと関連付けられてもよい。
【００８３】
記述された実施形態のコンテキストでは、ランタイム実行、リアルタイム実行、又はリアルタイム優先度処理実行は、システム又はユーザの観点から通信の実際の品質及び／又は感知される品質に影響することがある、接続されたデバイス１１００とネットワーク１２００との間の通信の間に実行される動作に対応する。よって、ランタイムにおいて、リアルタイムで、又はリアルタイム優先度処理を使用して実行される動作は典型的には、例えば、最大時間、フレームの最大数、及び／又は処理リサイクルの最大数の点で表現されてもよい、特定の性能制約を満たす必要がある。例えば、異なる電気通信標準は、異なる性能要件を提供する。当業者は、リアルタイム処理が実際には、それが最良となる全ての環境において絶対的に達成可能とはならないことがあることを容易に認識するであろう。開示される実施形態の目的に対して必要とされるリアルタイム優先度処理は、ネットワーク内で体系化されるように、及び／又は接続されたデバイスのユーザによって感知されるように、サービスの事項及び／又は品質に設定された接続されたデバイスに関連し、絶対的なリアルタイム処理を必要としない。
【００８４】
制御関連情報を交換するために、制御ネットワーク（例えば、ネットワーク１４００自体又はネットワーク１４００上に置かれた別のネットワーク）が使用されてもよい。例えば、ハンドオフ手順、アドレス管理、接続されたデバイス１１００のユーザの相互作用（例えば、データ使用量など）に関連する接続されたデバイス１１００及びイベントについてのセル及び／又はチャネル属性は、制御ネットワークを通じて共有されてもよい。同様に、ネットワーク全体イベント（例えば、ネットワークの状態に関連するなど）は、１つ以上の集中コンピュータシステム（図示せず）から制御ネットワークを通じて共有されてもよい。加えて、記憶モジュール１５００（例えば、ネットワーク化されたデータベースシステム）は、コンピュータ電気通信システム１０００の異なる構成要素に対してアクセス可能であってもよい。
【００８５】
図２５は、ノイジ通信チャネルについてのチャネル復号器における凍結ビットのｎ個の最良の位置を判定する例示的な方法２０００のフローチャートを示す。方法は、ポーラ符号符号化スキームを選択すること（２０１０）と、ポーラ符号符号化スキームに対応するポーラ符号復号器スキームを取得すること（２０２０）と、チャネルビットの数を定義するチャネル帯域幅を判定すること（２０３０）と、メッセージビットの数を定義するメッセージ長、並びに凍結ビットの数ｎを定義するチャネルビットの数及びメッセージビットの数を判定すること（２０４０）と、を含む。方法はまた、ノイジ通信チャネルの性質に関わらず、消去確率ｐにより通信チャネルを特徴付けること（２０５０）と、確率ｐを考慮したｎ個の最悪の位置を計算すること（２０６０）と、を含む。ポーラ符号符号化スキームは、例えば、ＣＮＯＴゲートの少なくとも２レベルを使用してモデル化された畳み込みポーラ符号（畳み込みポーラ符号、１−２符号、２−１−２符号、１−２−１符号、２−１−２−１符号、１−２−１−２符号などとして前に議論された）であってもよい。
【００８６】
ポーラ符号符号化スキームは、２の累乗としてビットｋの数を有してもよく、したがって、ｋは、チャネルビットの数以上であると選択されてもよい（チャネルにわたって消去へのポーラ符号の復元を考慮して）。
【００８７】
代わりに、ポーラ符号符号化スキームは、各々が２の累乗として表現されるいくつかのコーディングビットを含む、１つよりも多いサブポーラ符号を含んでもよい（例えば、合計で６４＋１２８＝１９２ビットとなる２６符号及び２７符号）。次いで、サブポーラ符号の各々におけるコーディングビットの数は、その合計がチャネルビットの数以上となるように選択されてもよい。
【００８８】
前に議論されたように、ノイジ通信チャネルは、消去ｐ２のｇｏｏｄ状態、ｂａｄ状態の確率ｐ１≧ｐ２に対応する消去確率ｐにより特徴付けられた相関付けられたノイズ特性を提示してもよい。チャネルはまた、ｇｏｏｄ状態とｂａｄ状態との間の遷移の確率Ｐｇｂ及びｇｏｏｄ状態とｂａｄ状態との間の遷移の確率Ｐｂｇを提供し、ｎ個の最悪の位置を計算し、更に、確率ｐ２、Ｐｇｂ、及びＰｂｇを考慮する。
【００８９】
この例示的な実施形態の別の態様は、そこで選択されポーラ符号復号器スキームを実装し、それによって判定されたｎ個の最悪の位置において凍結ビットを有する、例示された方法２０００において構築する復号方法を含んでもよい。同様に、方法２０００のようにポーラ符号復号器スキームをサポートし、それによって判定されたｎ個の最悪の位置において凍結ビットを有する復号プロセシングユニットが提供されてもよい。
【００９０】
図２６は、アップリンク（２６Ａ）及びダウンリンク（２６Ｂ）符号化及び復号フローチャートを記述する。１つの実施形態では、ｍ＜ｎビットのメッセージを取得するようにｎ個のビットのメッセージを反復的に復号する方法３０００が提供される。メッセージは、ｐ２≦ｐ１となるｂａｄ状態の消去の確率ｐ１、消去ｐ２のｇｏｏｄ状態によって特徴付けられた相関付けられたノイズを示すノイジ通信チャネルを通じて受信される。チャネルは更に、ｇｏｏｄ状態とｂａｄ状態Ｐとの間の遷移の確率Ｐｇｂ及びｇｏｏｄ状態とｂａｄ状態との間の遷移の確率Ｐｂｇを提供する。方法３０００は、ｎビットからのビットｉごとに反復して、
・特定の値に簡易化された収縮アイデンティティを使用して論理グラフをトラバースすることによってビットｉについての確率ベクトルを判定し（３０１０）、
・対応する収縮アイデンティティに基づいて、後の反復の間に後続の参照についての確率ベクトルの判定の間に新たに計算された収縮アイデンティティから特定の値をインデックス付けし（３０２０）、
・確率ベクトルからビットｉを固定し（３０３０）、
・全てのｎ個のビットが固定されるまで、ビット＋１に移動する（３０４０）。
【００９１】
新たに計算された収縮アイデンティティは、確率ベクトルの判定の間に特定の値に置き換えられた論理グラフ（例えば、図１３の例を参照）の１つ以上のセクションに対応する。同一のセクションを置き換えるために、後続の反復の間にインデックス付けされた値が使用される（例えば、ｎ個のビットの処理の間に複数回多くのセクションが繰り返されるように）。そのような解決策は、実際の計算ステップの数を制限し、効率性が増加することを保証する。メッセージは典型的には、ネットワークインタフェースを通じて受信され、固定されたビットは典型的には、ネットワークスタックの上位の処理レイヤに提供される。専用コーディングプロセッサ１１３２は有利に、復号方法３０００をサポートすることができる。
【００９２】
本発明のコンテキストにおいて、様々なネットワークリンクが黙示的又は明示的に使用されてもよい。リンクが無線リンクとして記述されてもよく、それはまた、同軸ケーブル、光ファイバ、及びカテゴリ５ケーブルなどを使用した有線リンクとして具体化されてもよい。それらの間のリンク上に有線又は無線アクセスポイント（図示せず）が存在してもよい。同様に、いずれかの数のルータ（図示せず）が存在してもよく、インターネットを更に通ることができるリンクの一部であってもよい。
【００９３】
本発明は、異なるモジュールがそれらの間でどのように情報を交換するかによっては影響されない。例えば、メモリモジュール及びプロセッサモジュールは、本発明の教示に影響を与えることなく、並列バスによって接続されてもよいが、また、直列接続によって接続されてもよく、又は中間モジュール（図示せず）を含んでもよい。
【００９４】
方法は概して、所望の結果につながる、一貫した一連のステップであるとして認知される。それらのステップは、物理量の物理操作を必要とする。通常、必ずしもではないが、それらの量は、記憶され、転送され、組み合わされ、比較され、他に操作されることが可能な電気又は磁気／電磁気信号の形式をとる。時に、一般的な使用を主な理由として、それらの信号を、ビット、値、パラメータ、項目、要素、オブジェクト、シンボル、文字、用語、又は数などと称することが便利である。しかしながら、それらの用語及び同様の用語の全ては、適切な物理量と関連付けられることになり、それらの量に適用される便利なラベルに過ぎないことに留意されるべきである。本発明の説明は、例示を目的に提示されてきたが、包括的であることを意図しておらず、又は開示される実施形態に限定されない。当業者にとって多くの修正及び変形が明らかである。他の熟考された使用に適合するように、様々な修正と共に様々な実施形態を実装するために、実施形態は、発明の原理及びその実用的な適用を説明し、他の当業者が発明を理解することを可能にするために選択されてきた。
【００９５】
それらの相対的な性能のより良好な理解を得るために、ポーラ及び畳み込みポーラコーディングの下での消去チャネルのチャネルポーラリゼーションを調査することが興味深い。図１５では、５０％の消去チャネルと共に、１０２４ビットのポーラ及び畳み込みポーラ符号の下での論理チャネルのポーラリゼーションに関する結果が提示される。より具体的には、図１５Ａ及び１５Ｂでは、連続キャンセレーション復号の下での論理チャネルの実効消去レートによりパラメータ化された、各々のチャネルの精度は、ポーラ符号（図１５Ａ）及び畳み込みポーラ符号（図１５Ｂ）に対して記述される。図１５Ｃでは、ポーラ及び畳み込みポーラ符号について降順で同一のデータがプロットされる。垂直の点線は、５０％における容量に対応する。図１５Ｄは、指定された数のデータビットについてのフレーム誤り率（ＦＥＲ）への単純な上限を提供する、累積合計を示す。
【００９６】
図１５Ａ、１５Ｂ、及び１５Ｃでは、畳み込みポーラ符号が完全な制限と無用な制限との間の中間領域内でいくらか少ないチャネルを含み、更に、良好なチャネルが左でもう少し強くローカライズされる（逆に不良のチャネルは右でローカライズされる）ことが観察されることができる。データビットを判定するとき、凍結ビットに関する更なる情報が復号器に対して利用可能であり、最大尤度と連続キャンセレーション復号との間の性能におけるギャップを減少させることを意味することを理由に、この後者の事実は、連続キャンセレーション復号に対して特に顕著である。
【００９７】
それらの結果から、ブロックにおける少なくとも１つの誤り、又はフレーム誤り率（ＦＥＲ）の確率に対する単純な上限を推論することができる。ｋ個のデータチャネルにわたって消去の確率を単純に合計することによって、及び誤りの機会がほとんど、所与のデータビットが不正確に最初に復号されることになる確率の合計であることに留意することによって、ＦＥＲの（過度な）推定が取得される。図１５Ｄでは、この合計は、データレートの範囲について示される。同様に、非凍結ビットが不正確に最初に復号されることになる最大確率は、ＦＥＲについての下限を提供する。下限のみがここで示されるが、それは、当業者が把握するように、提供されたグラフのほとんどにおける上限から区別不能である。よって、それらの境界は、畳み込みポーラ符号が固定された誤り率について（特に、小さい目標の誤り率について）送信されたデータの量における著しい増大を遂行することができることを示唆する。図１６は、ポーラ及び畳み込みポーラ符号の誤り指数を推定するために上記導出された上限（区別不能である下限）を使用する。前に議論されたように、固定された符号化率ｋ／ｎ（容量未満の）について、両方の符号は、ポーラ符号についてβ≦１／２及び畳み込みポーラ符号について
【数１７】
2020515117.tif 000025
を有する
【数１８】
2020515117.tif 000026
としての漸近のフレーム−誤り率スケーリングを有する。それらのスケーリングは漸近的であり、図１６において観察された有限サイズスケーリングは、ポーラ符号についての誤り指数
【数１９】
2020515117.tif 000027
及び畳み込みポーラ符号についての誤り指数
【数２０】
2020515117.tif 000028
を明らかにし、強化ポーラリゼーションが相対的に小さいブロックサイズにおいて著しく公平であることの良好な証拠を提供する。
【００９８】
図１６では、ＦＥＲが
【数２１】
2020515117.tif 000029
としてスケーリングし、ビットＮ＝２ｎの数がポーラリゼーションステップの数ｎに依存することを想定して、
【数２２】
2020515117.tif 000030
であると判定される。Ｐｅについての上限を使用して、グラフは、ポーラ符号及び畳み込みポーラ符号についてｎに応じてｌｏｇ２［ｌｏｇ２（Ｐｅ）］をプロットする。また、示されるのは、ポーラ符号についての
【数２３】
2020515117.tif 000031
並びに畳み込みポーラ符号についての
【数２４】
2020515117.tif 000032
及び
【数２５】
2020515117.tif 000033
を使用した線形適合である。符号化率は、１／１６である。
【００９９】
様々なチャネルからデータを保護する際、ポーラ及び畳み込みポーラ符号の性能は、２５６ビットと８１９２ビットとの間の符号に対する有限符号長の効果への特定の焦点と数値的に比較されてきた。実行された全てのシミュレーションについて、誤りモデルの詳細と独立した簡易化されたチャネル選択スキームが使用されてきた。選択されたスキームは、確率ｐを有する対称ビット反転チャネルを使用し、位置ｊごとに、ビットｘｊが不正確に最初に復号されることになる確率を評価する。それは、各々のビットが、１である独立した確率ｐ及び０である独立した確率１−ｐを有することを復号器が確信する、全てのゼロ入力及び出力を使用することによって作用する。ビットｘｊごとに、対応するテンソルネットワーク図が、ｉ＜ｊについてｘｉ＝０及びｉ＞ｊについてランダムなｘｉにより収縮される。ポーラ符号及び畳み込みポーラ符号の両方についての論理チャネル誤り率の更に正確な推定は、サンプリングすることによって、すなわち、それらを０に固定する代わりに、ｉ＜０による考えられるビット値ｘｉにわたってサンプリングすることによって取得されてもよい。代わりに、畳み込みポーラ符号について、更に洗練された技術も使用されてもよい。しかしながら、この簡易化された手順は、全ての調査されたチャネルにわたって適切な結果を与える（例えば、消去チャネルから導出する、図１５に提示されたデータよりもビット反転チャネルに対して良好に実行する）。性能におけるわずかな改善は、問題の特定の誤りモデルに適合されたチャネル選択を使用して観察されることができるが、ポーラ符号と畳み込みポーラ符号との間の比較可能な性能が非常に類似したままであり、その結果、この手順は、比較を目的に適切である。
【０１００】
符号レート１／２による二値消去チャネルについての結果が図１７に与えられる。より具体的に、図１７では、二値消去チャネルについての様々なサイズのレート１／２ポーラ符号及び畳み込みポーラ符号の性能が記述される。符号化されたメッセージは、図１７Ａ及び図１７Ｂの例において２５６ビットを含み、図１７Ｃ及び図１７Ｄの例において１０２４ビットを含み、図１７Ｅ及び図１７Ｆの例において８１９２ビットを含む。消去確率０．５を有する容量は、符号レート１／２に対応する。異なる観察が行われることができる。有限サイズの効果は、消去チャネルの容量をやや下回る「完璧な」及び「無用な」振る舞いを分離するウォータフォール領域により、両方の符号において顕著である（それは、最大で０．５の消去レートが符号化レートに対して許容可能であることを示唆する）。それにも関わらず、畳み込みポーラ符号の閾値は、ポーラ符号よりもこの値に著しく近い。対数尺度上では、低誤り領域における性能は、例えば、畳み込みポーラ符号について著しく大きい、図１７Ｆにおける傾斜を見ることによって著しく良好である。いずれの符号も、誤りフロアのいずれの証拠も示さない（予想もされない）。最後に、両方の符号は、いずれの誤りも、多くのビットに関する誤りを伴い、壊滅的である傾向を示す。実際に、ビット誤り率（ＢＥＲ）とフレーム誤り率（ＦＥＲ）との間の比率が、ポーラ符号について非常に大きく、畳み込みポーラ符号について更に高い（０．５に近い）。これは、完璧に復号されたメッセージ又は完全にスクランブルされたもののいずれかに対応する。興味深いのは、これはシャノンが想定したように、最も可能性のあるメッセージが完全に相関付けられていない、「完璧な」ランダム符号の予想される振る舞いである。
【０１０１】
図１８では、ビット反転チャネルについて同様の振る舞いが観察される。より具体的には、図１８は、ビット反転チャネルについての様々なサイズのレート１／２ポーラ及び畳み込みポーラ符号の性能の比較を示す。復号されたメッセージは、図１８Ａ及び図１８Ｂの例において２５６ビットを含み、図１８Ｃ及び図１８Ｄの例において１０２４ビットを含み、図１８Ｅ及び図１８Ｆの例において８１９２ビットを含む。約０．１１のビット反転確率を有する容量は、符号レート１／２に対応する。図１８に記述される例では、ほとんどのビットが約０．１１のビット反転レートにおいて予想される閾値を下回って観察されたウォータフォール領域と共に、更に大きな有限サイズ効果が観察されることができる。畳み込みポーラ符号は、誤りについてのより高い許容度、良好な性能と不良な性能との間のより急峻な遷移、及び低誤り率領域におけるより良好なスケーリングにより、全てのケースにおいて良好に実行する。
【０１０２】
最後に、より現実的な付加的ガウスホワイトノイズチャネルの下での性能が図１９に記述される。より具体的には、図１９では、付加的ガウスホワイトノイズチャネルについての様々なサイズのレート１／２ポーラ及び畳み込みポーラ符号の性能の比較が記述される。符号化されたメッセージは、図１９Ａ及び図１９Ｂの例において２５６ビットを含み、図１９Ｃ及び図１９Ｄの例において１０２４ビットを含み、図１９Ｅ及び図１９Ｆの例において８１９２ビットを含む。再度、同様の振る舞いが観察されることができると、畳み込みポーラ符号は、より大きなノイズレートについての許容度及び低ノイズ領域におけるより良好なスケーリングを含む、ポーラ符号よりも良好な誤り性能を有する。それらの結果に基づいて、畳み込みポーラ符号は、有限の、相対的に小さいブロックサイズによる誤り補正能力に関して言えば、ポーラ符号に対する著しい改善であるように見える。更に、数値（又は、計算的）コストは著しく影響され、同一のスケーリングで、事例的には、復号する計算努力を約二倍にする。
【図１−１】
2020515117.tif 000034
【図１−２】
2020515117.tif 000035
【図１−３】
2020515117.tif 000036
【図１−４】
2020515117.tif 000037
【図１−５】
2020515117.tif 000038
【図１−６】
2020515117.tif 000039
【図１−７】
2020515117.tif 000040
【図１−８】
2020515117.tif 000041
【図１−９】
2020515117.tif 000042
【図２】
2020515117.tif 000043
【図３】
2020515117.tif 000044
【図４】
2020515117.tif 000045
【図５】
2020515117.tif 000046
【図６】
2020515117.tif 000047
【図７】
2020515117.tif 000048
【図８】
2020515117.tif 000049
【図９】
2020515117.tif 000050
【図１０】
2020515117.tif 000051
【図１１】
2020515117.tif 000052
【図１２】
2020515117.tif 000053
【図１３】
2020515117.tif 000054
【図１４】
2020515117.tif 000055
【図１５−１】
2020515117.tif 000056
【図１５−２】
2020515117.tif 000057
【図１６】
2020515117.tif 000058
【図１７−１】
2020515117.tif 000059
【図１７−２】
2020515117.tif 000060
【図１８−１】
2020515117.tif 000061
【図１８−２】
2020515117.tif 000062
【図１９−１】
2020515117.tif 000063
【図１９−２】
2020515117.tif 000064
【図２０】
2020515117.tif 000065
【図２１】
2020515117.tif 000066
【図２２】
2020515117.tif 000067
【図２３】
2020515117.tif 000068
【図２４】
2020515117.tif 000069
【図２５】
2020515117.tif 000070
【図２６−１】
2020515117.tif 000071
【図２６−２】
2020515117.tif 000072
【国際調査報告】
2020515117.tif 000073
2020515117.tif 000074
2020515117.tif 000075