(57)【要約】      （修正有）【課題】光通信およびストレージに適した高速・低レイテンシ・レート設定可能な軟判定および硬判定に基づくパイプライン型のリード・ソロモン（ＲＳ）復号器アーキテクチャを提供する。【解決手段】ＲＳ復号器は、チャネルを監視し、チャネル容量に基づいて符号パラメータを調整する。軟判定復号器（ＳＤＤ）を実装するために補間および因数分解なしの低複雑度チェイス（ＬＣＣ）復号を含む。テストベクトルを生成し、これらをパイプライン型の２段硬判定復号器（ＨＤＤ）に供給する。並列性なしで正確に２ｔ回のクロックサイクル内に誤りロケータ多項式を計算し、高スループットをサポートし、正確にｔ回のサイクル内に誤り評価多項式をさらに計算する。低いレイテンシおよび縮小されたサイズのデータバッファで動作する２段パイプライン型とする。【選択図】図１１
2018019401.tif 000002
【特許請求の範囲】
【請求項１】
テストベクトルを処理し、シンドロームを生成するように構成されているシンドローム計算（ＳＣ）モジュールであって、前記ＳＣモジュールのシンドローム計算段が２ｔ個のシンドロームを計算するために２ｔサイクルを要する、前記シンドローム計算（ＳＣ）モジュールと、
誤りロケータ多項式を計算するように構成されているキー方程式ソルバー（ＫＥＳ）と、
誤り位置および対応する誤りマグニチュードを見つけるように構成されているチェン探索および誤りマグニチュード計算（ＣＳＥＭＣ）モジュールと、
を備え、前記ＳＣモジュール、前記ＫＥＳおよび前記ＣＳＥＭＣモジュールが２段パイプライン方式で配置されている、リード・ソロモン（ＲＳ）復号器。
【請求項２】
前記ＲＳ復号器は、軟判定復号器（ＳＤＤ）である、請求項１に記載の復号器。
【請求項３】
前記ＳＤＤは、補間および因数分解なしの低複雑度チェイス（ＬＣＣ）復号を使用するように構成されている、請求項２に記載の復号器。
【請求項４】
前記ＲＳ復号器は、２段硬判定復号器（ＨＤＤ）である、請求項１に記載の復号器。
【請求項５】
前記ＨＤＤは、誤りロケータ多項式を取得するために２ｔ回の反復を要するバーレカンプ・マッシー（ＢＭ）アルゴリズムに基づくｔシンボル訂正復号器である、請求項４に記載の復号器。
【請求項６】
前記ＲＳ復号器は、チャネル容量を監視し、前記監視されたチャネル容量に基づいて符号パラメータを調整するように構成されている、請求項１に記載の復号器。
【請求項７】
前記ＫＥＳは、バーレカンプ・マッシー（ＢＭ）アルゴリズムまたは修正ユークリッド（ＭＥ）アルゴリズムを使用して誤りロケータ多項式を計算する、請求項１に記載の復号器。
【請求項８】
テストベクトル生成モジュールは、前記ＳＣモジュールへの入力として供給された２η個のテストベクトルを生成する、請求項１に記載の復号器。
【請求項９】
遅延バッファが前記テストベクトルを一時記憶するように構成されている、請求項１に記載の復号器。
【請求項１０】
前記ＳＣモジュールは、低レイテンシを達成し、遅延バッファのサイズを縮小するために前記ＫＥＳと統合される、請求項１に記載の復号器。
【請求項１１】
前記誤りロケータ多項式は、前記ＲＳ復号器の高スループットを達成するために並列性なしで２ｔ回のクロックサイクル内で取得される、請求項１に記載の復号器。
【請求項１２】
前記ＣＳＥＭＣモジュールは、並列度Ｊのチェン探索アーキテクチャを備える、請求項１に記載の復号器。
【請求項１３】
シンドローム計算（ＳＣ）モジュールによって、テストベクトルを処理することによりシンドロームＳｊを計算するステップと、
キー方程式ソルバー（ＫＥＳ）によって、前記計算されたシンドロームＳｊから誤りロケータ多項式σｉを計算するステップと、
チェン探索および誤りマグニチュード計算（ＣＳＥＭＣ）モジュールによって、前記計算された誤り位置多項式σｉから誤り位置Ｘｉ、および、対応する誤りマグニチュードＹｉを計算するステップと、
を含む、リード・ソロモン（ＲＳ）復号器のための復号方法。
【請求項１４】
前記誤りロケータ多項式σｉは、バーレカンプ・マッシー・アルゴリズムを使用して、前記計算されたシンドロームＳｊから計算される、請求項１３に記載の方法。
【請求項１５】
前記誤りマグニチュードＹｉは、Ｆｏｒｎｅｙの公式を使用して計算される、請求項１３に記載の方法。
【請求項１６】
前記方法は、テストベクトル生成モジュールによって、２η個のテストベクトルを生成するステップをさらに含み、２η個のテストベクトルのうちの各テストベクトルは、前記ＳＣモジュールに渡される、請求項１３に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本開示は、誤り訂正符号の分野に関する。詳しくは、本開示は、高速ストレージおよび通信システムのための復号器および復号方法に関する。
【背景技術】
【０００２】
背景技術の説明は、本発明を理解するのに役立つことがある情報を含む。このことは、本書に記載された情報のうちのいずれかが先行技術であること、もしくは、本願請求項に係る発明に関連していること、または、具体的もしくは明示的に参照された刊行物が先行技術であることを自認するものではない。
【０００３】
たとえば、光ファイバネットワーキングシステムなどを通じて得られる高速データ伝送と、高速ストレージ装置のため必要とされる高速データ処理とは、より高いデータレートという継続的な要望を満たすために高スループットをサポートすることができる効率的な誤り訂正符号を必要とする。リード・ソロモン（ＲＳ）符号は、これらのバースト誤り訂正機能が保証されているので様々なストレージおよび通信用途において広く用いられている。しかしながら、高速であり、かつ、面積効率の良いＲＳ復号器アーキテクチャを実装することは、いつでも重要な課題である。適切なＲＳ復号器アーキテクチャを開発することは、スループット、面積、およびレイテンシの間のトレードオフをいつでも必要とする。
【０００４】
ＦＧＰＡに実装された最新式の硬判定（ＨＤ）ＲＳ復号器は、とても２Ｇｂｐｓという最大スループットに到達しない。最近公表されたＸｉｌｉｎｘのＲＳ復号器ＩＰは、ＲＳ（２５５，２３９）符号に対して３．２Ｇｂｐｓという最大スループットをサポートする。ＡｌｔｅｒａのＲＳ  ＩＰコアは、同様に、ＲＳ（２０４，１８８）符号に対して３Ｇｂｐｓという最大スループットをサポートする。
【０００５】
承知の通り、復号には主に２つのカテゴリー：代数的軟判定復号器（ＳＤＤ）および硬判定復号器（ＨＤＤ）が存在し、ここで、ＳＤＤは、ＨＤＤより高い複雑度でＨＤＤより優れた誤り性能を提供する。しかしながら、ＳＤＤは、実装のため広い面積を必要とする。Ｋｏｅｔｔｅｒ−Ｖａｒｄｙ（ＫＶ）アルゴリズムに基づく最初の、よく知られているＳＳＤは、３つの主要なステップ：多重（ｍ）割当、補間および因数分解を含む。ＫＶのようなアーキテクチャの１つの主要な問題は、ＫＶアルゴリズムに基づくＳＤＤが補間ステップおよび因数分解ステップの複雑度のため、より大きい面積を必要とすることである。
【０００６】
既存のＲＳ復号器に関する別の問題は、この復号器が誤り訂正機能の点において柔軟性をもたらさないことである。既存のＲＳ復号器の多くは、固定誤り訂正機能を用いて構成され、チャネル特性および性能とは無関係に復号を行う。
【０００７】
従って、チャネル特性および性能に依存して誤り訂正機能を選択することができる設定可能なＲＳ復号器およびその復号方法が当該技術において必要である。ＲＳ復号器およびその実装／実施の方法も高速ストレージシステムおよび高速伝送システムのための高スループットおよび低レイテンシを達成するために必要である。
【０００８】
本書においてあらゆる刊行物は、参照によって、個別の刊行物または特許出願が具体的かつ個別に参照によって援用されることが示されるのと同じ程度まで援用される。援用文献における用語の定義または使用が本書において示された用語の定義に矛盾する、もしくは、反する場合、本書において示された用語の定義が適用され、参照における用語の定義は適用されない。
【０００９】
一部の実施形態では、発明のある特定の実施形態を記述し、権利を主張するために用いられた成分の量、濃度のような特性、反応条件などを表現する数は、場合によっては、用語「およそ」によって修正されているとして理解されるべきである。その結果、一部の実施形態では、明細書および特許請求の範囲に記載された数値パラメータは、特有の実施形態によって得られようとしている所望の特性に依存して変化し得る近似値である。一部の実施形態では、数値パラメータは、報告された有効数字を考慮して、かつ、通常の丸め技術を適用することによって解釈されるべきである。広範囲にわたる発明の一部の実施形態を明記する数値範囲およびパラメータは、近似値であるにもかかわらず、具体的な実施例において明記された数値は、実行可能な限り正確に報告されている。発明の一部の実施形態において示された数値は、それぞれの検査測定値に見られる標準偏差によって必然的に生じるある一定の誤差を含むことがある。
【００１０】
本書における説明中で、かつ、続く特許請求の範囲の全体を通じて用いられるように、単数形「ａ（単数形不定冠詞）」、「ａｎ（単数形不定冠詞）」、および「ｔｈｅ（定冠詞）」の意味は、文脈上明白に他の指示がない限り複数形への言及を含む。同様に、本書における説明中で用いられるように、「ｉｎ（〜の中に）」の意味は、文脈上明白に他の指示がない限り「ｉｎ（〜の中に）」および「ｏｎ（〜に接して）」を含む。
【００１１】
本書における値の範囲の列挙は、この範囲に含まれる個別の値を個別に参照する簡単な方法としての役割を果たすように意図されているに過ぎない。本書において他の指示がない限り、個別の値は、本書において個別に挙げられているかのように明細書に組み込まれる。本書において記載されたあらゆる方法は、本書において他の指示がない限り、または、そうでなければ、文脈上明白に矛盾しない限り、何らかの適切な順序で行われ得る。本書においてある特定の実施形態に関連して示されたありとあらゆる実施例、または、例示的な言葉（たとえば、「ｓｕｃｈ  ａｓ（たとえば、〜など）」）の使用は、例を使って発明をより良く説明することが意図されているだけであり、他の主張がなければ、発明の範囲に制限を課すものではない。明細書中の言葉は、請求項に記載がなく、発明の実施に不可欠である何らかの要素を指示するものとして解釈されるべきではない。
【００１２】
本書に開示された発明の代替的な要素または実施形態のグループ分けは、限定として解釈されるべきではない。各グループメンバーは、個別に、または、グループの他のメンバーもしくは本書において見られる他の要素と組み合わせて、参照されるまたは請求項に記載されることが可能である。グループの中の１つ以上のメンバーは、利便性および／または特許性の理由のため、グループに包含、または、グループから削除される可能性がある。このような包含または削除が行われたとき、明細書は、本書では、特許請求の範囲で用いられたあらゆるグループについての書面記載を満たすように修正された通りのグループを含んでいると見なされる。
【発明の概要】
【発明が解決しようとする課題】
【００１３】
本開示の全般的な目的は、高速ストレージおよび高速通信システムのためのＲＳ復号器および復号方法を提供することである。
【００１４】
本開示の目的は、チャネル特性および性能に依存して設定可能な誤り訂正機能を有効にすることができる設定可能なＲＳ復号器およびその復号方法を提供することである。
【００１５】
本開示の別の目的は、特定のスループットのため高速ストレージおよび高速通信システムで用いられた従来型のＲＳ復号器より小さい面積を必要とするＲＳ復号器を提供することである。
【００１６】
本開示のさらに別の目的は、高速ストレージおよび高速通信アプリケーションのための高スループットおよび低レイテンシを達成することができるＲＳ復号器を提供することである。
【課題を解決するための手段】
【００１７】
本開示の態様は、誤り訂正符号の分野に関する。より詳しくは、本開示は、高速ストレージシステムおよび高速通信システムのための復号器および復号方法に関する。
【００１８】
本開示の態様は、リード・ソロモン復号器アーキテクチャおよびその方法を提供する。実施形態では、高速・低レイテンシ・レート設定可能な軟判定および硬判定に基づく２段パイプライン型のリード・ソロモン（ＲＳ）復号器アーキテクチャが提供される。
【００１９】
本開示の実施形態は、テストベクトルを処理し、シンドロームを生成するように構成され、２ｔ個のシンドロームを計算するために２ｔサイクルを要するシンドローム計算（ＳＣ）モジュールと、誤りロケータ多項式を計算するように構成されているキー方程式ソルバー（ＫＥＳ）と、誤り位置および対応する誤りマグニチュードを見つけるように構成されているチェン探索および誤りマグニチュード計算（ＣＳＥＭＣ）モジュールとを含み、ＳＣモジュール、ＫＥＳおよびＣＳＥＭＣモジュールが２段パイプライン方式で配置されているリード・ソロモン（ＲＳ）復号器を提供する。
【００２０】
ある態様では、ＲＳ復号器は、補間および因数分解のない低複雑度チェイス（ＬＣＣ）復号を使用するように構成されている軟判定復号器（ＳＤＤ）として構成され得る。
【００２１】
別の態様では、ＲＳ復号器は、誤りロケータ多項式を取得するために２ｔ回の反復を要するバーレカンプ・マッシー（ＢＭ）アルゴリズムに基づくｔシンボル訂正復号器である２段硬判定復号器（ＨＤＤ）として構成され得る。
【００２２】
ある態様では、ＲＳ復号器は、チャネル容量を監視し、監視されたチャネル容量に基づいて符号パラメータを調整するように構成されている。
【００２３】
ある態様では、ＫＥＳは、バーレカンプ・マッシー（ＢＭ）アルゴリズムまたは修正ユークリッド（ＭＥ）アルゴリズムを使用して誤りロケータ多項式を計算する。
【００２４】
ある態様では、テストベクトル生成器モジュールは、ＳＣモジュールへの入力として与えられる２η個のテストベクトルを生成する。ある態様では、遅延バッファは、テストベクトルを一時記憶するように構成されている。ある態様では、ＳＣモジュールは、低レイテンシを達成し、遅延バッファのサイズを縮小するためにＫＥＳと統合される。
【００２５】
ある態様では、誤りロケータ多項式は、ＲＳ復号器の高スループットを達成するために、並列性なしで２ｔ回のクロックサイクル内で取得される。
【００２６】
ある態様では、ＣＳＥＭＣモジュールは、並列度Ｊのチェン探索アーキテクチャを備える。
【００２７】
ある態様では、本開示は、シンドローム計算（ＳＣ）モジュールによって、テストベクトルを処理することによりシンドロームＳｊを計算するステップと、キー方程式ソルバー（ＫＥＳ）によって、計算されたシンドロームＳｊから誤りロケータ多項式σｉを計算するステップと、チェン探索および誤りマグニチュード計算（ＣＳＥＭＣ）モジュールによって、計算された誤り位置多項式σｉから誤り位置Ｘｉと、対応する誤りマグニチュードＹｉとを計算するステップとを含む、リード・ソロモン（ＲＳ）復号器のための復号方法を提供する。
【００２８】
ある態様では、誤りロケータ多項式σｉは、バーレカンプ・マッシー・アルゴリズムを使用して、計算されたシンドロームＳｊから計算され、誤りマグニチュードＹｉは、Ｆｏｒｎｅｙの公式を使用して計算される。
【００２９】
ある態様では、この方法は、テストベクトル生成モジュールによって、２η個のテストベクトルを生成するステップをさらに含み、２η個のテストベクトルのうちの各テストペクトルは、ＳＣモジュールに渡される。
【００３０】
例示的な実装では、ＨＤＤおよびＳＤＤは、レート設定可能であり、様々なチャネル条件で用いるため構成され得る。ＲＳ復号器は、チャネル条件を監視するように構成することができ、その結果、ＨＤＤおよびＳＤＤを設定することができる。
【００３１】
発明の主題の様々な目的、特徴、態様および利点は、類似した符号が同様の構成要素を表している添付図面と併せて、以下の好ましい実施形態の詳細な説明からより一層明白になるであろう。
【図面の簡単な説明】
【００３２】
添付図面は、本開示についてさらに理解を深めるために含まれ、本明細書に援用され、本明細書の一部を構成する。図面は、本開示の例示的な実施形態を例として説明するものであり、詳細な説明と共に、本開示の原理を説明するために役立つ。
【００３３】
【図１】本開示の実施形態に従ってＲＳ復号器のため使用され得る例示的なＬＣＣ軟復号器アーキテクチャを例として説明する図である。
【図２】本開示の実施形態に従って最低シンボル信頼度位置をソートするため使用され得るソーティングアーキテクチャを例として説明する図である。
【図３】本開示の実施形態に従って「Ｃｈレジスタ」を使用する最低シンボル信頼度位置のソーティングを例として説明する図である。
【図４】最も信頼できないη個の位置をカウントするｌｏｃレジスタを例として説明する図である。
【図５】η個の位置において２番目に信頼できるシンボルを含む例示的なｒ［２ＨＤ］レジスタを例として説明する図である。
【図６】本開示の実施形態に従ってテストベクトルを生成するため使用され得る例示的なアーキテクチャを例として説明する図である。
【図７】３段パイプライン型のＲＳ復号器の例示的なブロック図を例として説明する図である。
【図８】本開示の実施形態に従って２ｔ個のシンドロームを計算し得るシンドローム計算のための例示的な並列アーキテクチャを例として説明する図である。
【図９】本開示の実施形態に従ってバーレカンプ反復法に基づいて誤りロケータ多項式σ（ｘ）を計算するように構成されている例示的なキー方程式ソルバーアーキテクチャを例として説明する図である。
【図１０】本開示の実施形態に従ってＺ（ｘ）を決定するために使用され得る例示的な誤り評価アーキテクチャを例として説明する図である。
【図１１】本開示の好ましい実施形態に従ってシンドローム計算およびＫＥＳ計算が単一段に統合される例示的な２段パイプライン型の低レイテンシ復号器を例として説明する図である。
【図１２】チップセット上に設計されたＲＳ（２５５，２３９）復号器の結果を示す図である。
【図１３】本開示の実施形態により設計されたＨＤＤ復号器とη＝３およびη＝４に対するＬＣＣ復号器とのＦＥＲ性能を例として説明する図である。
【図１４】本開示の実施形態に従って提案されたＲＳ復号器による復号の方法を表現する例示的なプロセスを例として説明する図である。
【発明を実施するための形態】
【００３４】
以下は、添付図面に描かれた開示の実施形態の詳細な説明である。実施形態は、開示を明確に伝える程度に詳細である。しかしながら、提示された詳細の程度は、予想される実施形態の変形を制限することが意図されることなく、それどころか、意図は、特許請求の範囲によって規定された通りの本開示の趣旨および範囲内にあるあらゆる改変物、均等物、および代替物を網羅することにある。
【００３５】
特許請求の範囲の各請求項は、侵害目的のため、請求項に明記された様々な要素または制限の均等物を含むものと認識されている別々の発明を規定する。文脈に依存して、「発明」への以下のあらゆる言及は、一部の事例では、ある具体的な実施形態だけに言及することがある。他の事例では、「発明」への言及は、請求項のうち、必ずしも全部ではないが、１つ以上に記載された主題に言及することがある、と認識されるであろう。
【００３６】
本書において使用された様々な用語を以下に示す。請求項において使用された用語が以下に規定されていない限り、出願の時に印刷された刊行物および発行された特許にある通り、関連技術における当業者がこの用語に与えた最広義の定義が与えられるべきである。
【００３７】
本開示の態様は、誤り訂正符号の分野に関する。より詳しくは、本開示は、高速ストレージシステムおよび高速通信システムのための復号器および復号方法に関する。
【００３８】
本開示の態様は、リード・ソロモン復号器アーキテクチャおよびその復号方法を提供する。ある実施形態では、高速・低レイテンシ・レート設定可能な軟判定および硬判定に基づく２段パイプライン型のリード・ソロモン（ＲＳ）復号器アーキテクチャが提供される。
【００３９】
本開示の実施形態は、テストベクトルを処理し、シンドロームを生成するように構成され、シンドローム計算段が２ｔ個のシンドロームを計算するために２ｔサイクルを要するシンドローム計算（ＳＣ）モジュールと、誤りロケータ多項式を計算するように構成されているキー方程式ソルバー（ＫＥＳ）と、誤り位置および対応する誤りマグニチュードを見つけるように構成されているチェン探索および誤りマグニチュード計算（ＣＳＥＭＣ）モジュールとを含み、ＳＣモジュール、ＫＥＳおよびＣＳＥＭＣモジュールが２段パイプライン方式で配置されているリード・ソロモン（ＲＳ）復号器を提供する。
【００４０】
ある態様では、ＲＳ復号器は、補間および因数分解のない低複雑度チェイス（ＬＣＣ）復号を使用するように構成されている軟判定復号器（ＳＤＤ）として構成され得る。
【００４１】
ある態様では、ＲＳ復号器は、誤りロケータ多項式を取得するために２ｔ回の反復を要するバーレカンプ・マッシー（ＢＭ）アルゴリズムに基づくｔシンボル訂正復号器である２段硬判定復号器（ＨＤＤ）として構成され得る。
【００４２】
ある態様では、ＲＳ復号器は、チャネル容量を監視し、監視されたチャネル容量に基づいて符号パラメータを調整するように構成されている。
【００４３】
ある態様では、ＫＥＳは、バーレカンプ・マッシー（ＢＭ）アルゴリズムまたは修正ユークリッド（ＭＥ）アルゴリズムを使用して誤りロケータ多項式を計算する。
【００４４】
ある態様では、テストベクトル生成器モジュールは、ＳＣモジュールへの入力として与えられる２η個のテストベクトルを生成する。ある態様では、遅延バッファは、テストベクトルを一時記憶するように構成されている。ある態様では、ＳＣモジュールは、低レイテンシを達成し、遅延バッファのサイズを縮小するためにＫＥＳと統合される。
【００４５】
ある態様では、誤りロケータ多項式は、ＲＳ復号器の高スループットを達成するために、並列性なしで２ｔ回のクロックサイクル内で取得される。
【００４６】
ある態様では、ＣＳＥＭＣモジュールは、並列度Ｊのチェン探索アーキテクチャを備える。
【００４７】
ある態様では、本開示は、シンドローム計算（ＳＣ）モジュールによって、テストベクトルを処理することによりシンドロームＳｊを計算するステップと、キー方程式ソルバー（ＫＥＳ）によって、計算されたシンドロームＳｊから誤りロケータ多項式σｉを計算するステップと、チェン探索および誤りマグニチュード計算（ＣＳＥＭＣ）モジュールによって、計算された誤り位置多項式σｉから誤り位置Ｘｉと、対応する誤りマグニチュードＹｉとを計算するステップとを含む、リード・ソロモン（ＲＳ）復号器のための復号方法を提供する。
【００４８】
ある態様では、誤りロケータ多項式σｉは、バーレカンプ・マッシー・アルゴリズムを使用して、計算されたシンドロームＳｊから計算され、誤りマグニチュードＹｉは、Ｆｏｒｎｅｙの公式を使用して計算される。
【００４９】
ある態様では、この方法は、テストベクトル生成モジュールによって、２η個のテストベクトルを生成するステップをさらに含み、２η個のテストベクトルのうちの各テストベクトルは、ＳＣモジュールに渡される。
【００５０】
例示的な実装では、ＨＤＤおよびＳＤＤは、レート設定可能であり、様々なチャネル条件で用いるため構成され得る。ＲＳ復号器は、チャネル条件を監視するように構成することができ、その結果、ＨＤＤおよびＳＤＤを設定することができる。
【００５１】
軟判定復号器（ＳＤＤ）
例示的な実装では、チェイス復号アルゴリズムは、他の復号手法と比べると低複雑度を提供するので、チェイス復号アルゴリズムは、提案されたＳＳＤを実装するため使用され得る。承知の通り、たとえば、ＲＳ復号器の代数的軟判定復号（ＡＳＤ）などの他の復号手法は、従来型のＨＤＤより高い符号化利得を提供するが、高い計算複雑度を伴う。ＡＳＤ復号は、チャネル信頼度情報を使用することにより、限界距離復号を超えて誤りの訂正を容易にするが、ＡＳＤ法の間で、グルスワミ・スーダン（ＧＳ）アルゴリズムおよびＫＶアルゴリズムは、より高い複雑度と引き換えにより優れた性能をもたらす。その一方で、チェイス復号は、同等な性能で複雑度の低い解決策を提供する。
【００５２】
低複雑度チェイスアルゴリズム
本開示のＳＤＤは、テストベクトルの組を生成するためにＨＤＤ復号器と共に実装されるように構成することができ、性能パラメータに関して妥協することなく実装が容易であるチェイス復号器を使用し得る。提案されたＳＤＤは、復号半径ｔ＞ｄｍｉｎ／２の範囲内で符号語を補正することができ、ここで、ｄｍｉｎは、符号の最小距離である。低複雑度チェイス（ＬＣＣ）復号器は、シンボル信頼度情報に基づいて、２η個のテストベクトルを生成するように構成することができ、ここで、「η」個のシンボルがｎ個のシンボルの中から最低信頼度シンボルとして選択され、硬判定または２番目に信頼できる判定が採用される。テストベクトルを作成するために、硬判定シンボルの確率と２番目に良い判定の確率との間で、硬判定がどの程度良好であるかを示し得る比が確定され得る。受信メッセージ多項式ｒ（ｘ）に対する所望の確率比は、式１を使用して推定することができる。
【数１】
2018019401.tif 000003
式中、ｒｉ＿ＨＤは、シンボルの硬判定であり、ｒｉ＿２ＨＤは、２番目に信頼できる判定である。（硬判定と２番目に良い判定との間の）確率比が最も悪いη個の点に対応して、テストベクトルと呼ばれる２ηの組み合わせの組がη個のより信頼性の低い点において硬判定シンボル（ｒｉ＿ＨＤ）または２番目に良い判定（ｒｉ＿２ＨＤ）を選択することにより作成され得る。２番目に良い判定は、メッセージシンボル確率の情報に基づいて取得され得る。
【００５３】
実装のために、２番目に良い判定およびテストベクトルを生成する妥当であり、簡単な方法が使用できる。たとえば、ＡＷＧＮチャネル上でのＢＰＳＫ変調は、シンボル信頼度および２番目に信頼できる判定を生成するために使用され得る。ｃｉ＝［ｃｉ１ｃｉ２．．．ｃｉｍ］がｍビットベクトルであるとして符号語ｃ＝［ｃ１ｃ２．．．ｃｎ］とすると、ｃｉｊは、ｘｉｊおよびｘｉｊ＝１−２ｃｉｊに変調される。ｎｉｊがガウスランダム雑音サンプルであるとして、ｒｉｊがｃｉｊ・ｒｉｊ＝ｃｉｊ＋ｎｉｊに対応する実数値チャネル観測を表すことにする。
【００５４】
ある態様では、受信機において、ハードスライシングが行われ、このようにして形成された受信ベクトルは、ｙｉ［ＨＤ］として表すことができる。ある態様では、シンボル判定ｙｉ［ＨＤ］は、（観測ｒｉ１，．．．．ｒｉｍからの）各送信シンボルｃｉに関して行われる。チャネルは、受信された各ビットの信頼度を与える。シンボル内のｍビットの間で、最低信頼度ビットは、このシンボルの最悪の信頼度を定義する。ｉ番目のシンボルのシンボル信頼度λｉは、
【数２】
2018019401.tif 000004
を使用して計算できる。値λｉは、シンボル判定ｙｉ［ＨＤ］に関する確信度を示し、λｉの値が高いほど、信頼度が大きくなり、逆もまた同様である。２番目に信頼できる判定ｙｉ［２ＨＤ］は、上記式において最小値を実現するビットを補う、または、判定することによりｙｉ［ＨＤ］から取得される。
【００５５】
例示的な実装では、ＬＣＣアルゴリズムは、ｎシンボル信頼度λ１，λ２．．．．λｎを昇順に、すなわち、λｉ１≦λｉ２≦・・・≦λｉｎにソートするステップと、低い方からη個の信頼度値を表すインデックスＩ＝｛ｉ１，ｉ２，．．．ｉη｝を形成するステップと、を含み得る。さらに、２η個のテストベクトルの組が以下の関係
【数３】
2018019401.tif 000005
を使用して生成される。
【００５６】
さらに、各テストベクトルは、ＨＤＤ段に順次に渡され、復号失敗が起こらないベクトルは、受信機で推定符号語として見なされ得る。例示的な実装では、ＨＤＤ段は、バーレカンプ・マッシー・アルゴリズムに基づいて実装され得る。
【００５７】
硬判定誤り訂正法
例示的な実装では、ＲＳ復号器は、誤り訂正を実行できる。誤り訂正法は、以下のように例を用いて説明され得る。たとえば、符号ｃ（ｘ）が加法的誤りｅ（ｘ）によって破損され、ｒ（ｘ）を生じることにする。υは、誤りの個数を表すことにする。このとき、ｅ（ｘ）は、以下の形
【数４】
2018019401.tif 000006
を有し、式中、ｙｉは、誤り位置での誤りマグニチュードである。シンドロームは、
【数５】
2018019401.tif 000007
として計算することができ、式中、Ｙｉ＝ｙｉおよびＸｉ＝αｊである。目的は、ペア（Ｘｉ，Ｙｉ）を取得するために上記２ｔ個の方程式を解法することである。例示的な実装では、誤りロケータ多項式σ（ｘ）として知られている多項式は、
【数６】
2018019401.tif 000008
として定義できる。Ｘｉ値は、上記方程式の逆の根を使用して評価され得る。値Ｘｉが与えられると、Ｙｉに関して線形である式５が解法され得る。
【００５８】
ある実施形態では、復号方法が提供される。より詳しくは、シンドロームＳｊを計算するステップと、Ｓｊから誤り位置多項式σｉ、σｉから誤り位置Ｘｉ、および誤りマグニチュードＹｉを計算するステップとを含む、復号のための誤り訂正方法について記載される。例示的な実装では、復号された符号語多項式ｃ（ｘ）は、ＸｉおよびＹｉから取得されたｅ（ｘ）を加算することにより取得される。各ステップの詳細は、以下の通り示される。
ステップ１：シンドロームＳｊの計算：
シンドロームは、メッセージ多項式ｒ（ｘ）から式５を使用して評価され得る。
ステップ２：Ｓｊからの誤り位置多項式σｉの計算。例示的な実装では、誤りロケータ多項式σｉは、バーレカンプ・マッシー・アルゴリズムを使用してＳｊから計算され得る。例示的な実装では、σ（ｘ）は、２ｔ回のステップにおいて反復的に計算され得る。σμ（ｘ）が反復のμ番目のステップでの誤りロケータ多項式を表すことにする。σ（ｘ）を反復的に見つけるために、論理表１を埋めることができる。ｌμがσ（μ）（ｘ）の次数であるとする。表１のμ番目の行が埋められたとき、反復ステップは、以下に示された手順を使用して（μ＋１）番目の行を見つけることができる。
【数７】
2018019401.tif 000009
ｄμ≠０である場合、μ番目の行より前に別の行ρが探索され、ここで、ｄρ≠０であり、表１の最後の列における数ρ−ｌρは、最大値をとる。
σ（μ＋１）（ｘ）およびｌμ＋１は、それぞれ式７および式８を使用して繰り返し計算される。
【数８】
2018019401.tif 000010
【表１】
2018019401.tif 000011
ステップ３：誤り位置多項式σｉからの誤り位置Ｘｉの計算。例示的な実装では、誤り位置Ｘｉは、チェン探索を使用して誤り位置多項式σｉから計算され得る。例示的な実装では、α−１が誤りロケータ多項式σ（ｘ）の根である場合、誤りが位置ｉに存在していると結論付けられる。
ステップ４：誤りマグニチュードＹｉの計算。例示的な実装では、誤りマグニチュードＹｉは、以下の式９として与えられたＦｏｒｎｅｙの公式を使用して計算され得る。
【数９】
2018019401.tif 000012
式中、
【数１０】
2018019401.tif 000013
【００５９】
例示的な実装では、復号された符号語多項式ｃ（ｘ）は、ＸｉおよびＹｉから取得されたｅ（ｘ）を加算することにより取得され得る。
【００６０】
図１は、本開示の実施形態に従ってＲＳ復号器のために使用され得る例示的なＬＣＣ軟復号器アーキテクチャ１００を例として説明する。図１に示された通り、ＬＬＣ復号の主要なステップは、（ｉ）多重割当モジュール１０２によって実行される多重割当と、（ｉｉ）テストベクトル生成器１０４によって実行されるテストベクトルの作成と、（ｉｉｉ）２段パイプライン型のＨＤＤ１０６によって実行されるテストベクトルのＨＤＤとを含む。ある態様では、ＬＣＣ復号プロセスは、η＜２ｔである場合に、受信点から信頼度情報を使用して、２η個の異なるテストベクトルを作成する。η＞２ｔに対して、既存の復号器の複雑度は非常に高いので、これの実装は実現困難であることが実証されている。２η個のテストベクトルのうちの１つがｔ＋１個より少ない誤りを有する場合、復号器は、いかなる場合でもこれらの誤りを訂正し得るであろう。提案されたＲＳ復号器のアーキテクチャは、バーレカンプ・マッシー・アルゴリズム（ＢＭＡ）に基づく２段パイプライン型のＨＤＤを使用する。ＢＭＡベースのＲＳ符号器に対して、受信メッセージがチェン探索法の間に取得された根の個数より高い次数の誤りロケータ多項式σ（ｘ）を生成した場合、復号器障害が起こる。このような場合、誤りの個数がｔより多い場合、復号器は、メッセージを正確に復元できない。例示的な実装では、ＬＣＣ復号器は、以下の仕様に配慮して設計され得る。
−η＝３として、ＧＦ（２８）上のＲＳ（２５５，２３９）復号器
−チャネル信頼度情報のビット数が４ビットである。
−復号器への入力：ｙ［ＨＤ］、各シンボルｙｉ［ＨＤ］の信頼度情報λｉ、シンボル内で反転させる必要があるビットに関する情報。
−ＢＭアルゴリズムに基づく２段パイプライン型のＨＤ復号器。
多重割当
例示的な実装では、多重割当モジュール１０２は、多重割当を実行することができ、モジュール１０２は、低い方からη個のシンボル信頼度を受信するように構成され得る。最低シンボル信頼度値をソートする過程で、モジュール１０２は、昇順に低い方からη個のシンボル信頼度を得る。これらの低い方からη個のシンボル信頼度をソートする過程で、モジュール１０２は、η個の位置および対応するｒ［２ＨＤ］値を得る。例示的な実装では、「ｌｏｃレジスタ」および「ｒ［２ＨＤ］レジスタ」は、低い方からη個のシンボル信頼度位置および対応する２番目の判定値をそれぞれ記憶するために使用され得る。「Ｃｈレジスタ」は、シンボル信頼度をソートするために役立つ。
【００６１】
図２は、本開示の実施形態に従って最低シンボル信頼度位置をソートするため使用され得るソーティングアーキテクチャ２００を例として説明する。図３は、本開示の実施形態に従って「Ｃｈレジスタ」を使用する最低シンボル信頼度位置のソーティングを例として説明する。図２および図３は、シンボル信頼度のソーティングを示す。ｃｈレジスタ内の各位置は、２ｑ−１を用いて初期化され、ここで、ｑは、各シンボル信頼度を表現するために使用されるビット数である。シンボル信頼度λ（ｉ）は、ｉ＝０から２５５に対して順次に送信され得る。例示的な実装では、η個の比較器と、表２に示された符号器論理とがＥＮｋ信号およびＥＮｊ信号を生成するために使用され得る。これらのＥＮｋ信号およびＥＮｊ信号は、ｌｏｃレジスタおよびｒ［２ＨＤ］レジスタが低い方からη個のシンボル信頼度位置および対応する２番目の判定値をそれぞれ得るために使用され得る。ソーティングを理解するために、ｑ＝３ビットおよび入力ストリーム｛５，４，６｝を用いて実施例を試行することができる。ｃｈレジスタ内の各位置は、７を用いて初期化され得る。所与のアーキテクチャを用いて、３クロックサイクル内で所要のソート順｛４，５，６｝を得ることができる。０からｎ−１までの値をとるカウンタ「ｃｎｔ（ｉ）」は、図４に示される通りｌｏｃレジスタのため入力される。ｒｉ［２ＨＤ］は、図５に示される通りｒ［２ＨＤ］に順次に供給され得る。
【００６２】
例示的な実装では、「Ｃｈレジスタ」内の各シンボルは、全て「１」を用いて初期化され得る。シンボル信頼度λ（ｉ）は、ｉ＝０から２５５に対して順次に送信される。例示的な実装では、η個の比較器と表２に示された符号器論理とは、ＥＮｋ信号およびＥＮｊ信号を生成するために使用され得る。これらのＥＮｋ信号およびＥＮｊ信号は、ｌｏｃレジスタおよびｒ［２ＨＤ］レジスタが低い方からη個のシンボル信頼度位置および対応する２番目の判定値をそれぞれ得るために使用され得る。
【表２】
2018019401.tif 000014
【００６３】
図４は、低い方から信頼できないη個の場所をカウントするｌｏｃレジスタを例として説明する。例示的な実装では、０から２５５までの値をとるカウンタ「ｃｎｔ（ｉ）」は、図４に示された通りｌｏｃレジスタのための入力として構成され得る。図５は、η個の位置において２番目に信頼できるシンボルを含んでいる例示的なｒ［２ＨＤ］レジスタを例として説明する。例示的な実装では、ｒｉ［２ＨＤ］は、図５に示された通りｒ［２ＨＤ］レジスタに順次に供給され得る。
【００６４】
テストベクトル生成
図６は、本開示の実施形態に従ってテストベクトルを生成するため使用され得る例示的なアーキテクチャを例として説明する。図６に示された通り、２η個のテストベクトルが生成され得る。例示的な実装では、状態機械は、ＥＮ１，ＥＮ２，．．． ．ＥＮηを制御し、２η個のテストベクトルを得るために使用され得る。２η個のテストベクトルのうちの各テストベクトルは、２段パイプライン型のＨＤＤ１０６に渡され得る。
【００６５】
図７は、３段パイプライン型のＲＳ復号器の例示的なブロック図を例として説明する。図７に示された通り、ＲＳ復号器７００は、シンドロームを計算するように構成されているシンドローム計算モジュール７０２と、キー方程式ソルバー７０４と、チェン探索および誤りマグニチュード計算モジュール７０６とを含む。硬判定ＲＳ復号器のキー方程式ソルバー７０４は、誤りロケータ多項式を計算することを目的としてキー方程式を解法するためにバーレカンプ・マッシー（ＢＭ）アルゴリズムまたは修正ユークリッド（ＭＥ）アルゴリズムを使用して実装され得る。ＭＥアルゴリズムは、理解および実装することがより容易であるが、ＢＭアルゴリズムは、計算複雑度および実装の観点から効率的である。好ましい実装では、ＢＭアルゴリズムは、ＦＰＧＡ上に復号器回路を実装するために使用され得る。誤り値は、誤り評価多項式を使用して計算され得る。例示的な実装では、パイプライン方式は、より高いスループットを達成するためにＲＳ復号器に採用され得る。パイプライン型のアーキテクチャでは、全体的なスループットは、最も遅いパイプライン段およびこれの計算時間によって決定される。その結果、効率的な面積利用率でスループットを増加させるために、各パイプライン段は、おおよそ同じ時間内にこれの計算を完了すべきである。ＢＭアルゴリズムを使用して誤りロケータ多項式を計算するキー方程式ソルバー（ＫＥＳ）７０４は、２ｔ回の反復を要する。シンドロームおよび誤りロケータ多項式を所与として、チェン探索および誤りマグニチュード計算モジュール７０６は、誤り評価多項式を計算するため使用され得る。
【００６６】
例示的な実装では、誤りロケータ多項式および誤り評価多項式が誤り位置および対応する誤りマグニチュードを見つけるために使用され得る。並列性は、シンドローム計算（ＳＣ）段とチェン探索および誤りマグニチュード計算段とのため必要とされるクロックサイクルの数を調整するために採用され得る。例示的な実装では、遅延バッファ７０８は、受信シンボルを一時記憶するために使用することができ、遅延バッファのサイズは、復号器のレイテンシに依存する。本開示のＲＳ復号器を使用して復号するため使用される各機能ブロックが次に詳述される。
【００６７】
承知の通り、ほとんどの事例において、ＫＥＳ７０４は、他のブロックが様々なフィールド要素で多項式を評価する並列性を採用し得るので、スループットを決定する、この並列性は、スループットと面積との間のトレードオフを行う。遅延バッファ７０８のサイズは、パイプライン型の復号器のレイテンシによって決定され得るものであり、このことは、レイテンシを減少させる理由の１つである。
【００６８】
シンドローム計算（ＳＣ）
例示的な実装では、シンドローム計算（ＳＣ）は、シンドローム計算モジュール７０２によって実行され得る。シンドロームは、Ｓｊ＝ｒ（αｊ）、１≦ｊ≦２ｔとして計算される。図８は、本開示の実施形態に従って２ｔ個のシンドロームを計算することができるシンドローム計算のための例示的な並列アーキテクチャを例として説明する。図８に示された通りシンドローム計算のための並列アーキテクチャ８００は、メッセージ多項式ｒ（ｘ）からシンドロームを決定するため使用され得る。最初に、あらゆるレジスタ「ＲＥＧ」は、零にリセットされ得る。受信ベクトルが準備できると、値ｒ（ｉ）αｉをレジスタＲＥＧにロードするために、１クロックサイクルの間、「ロードイニシャル＝１」をマークすることができ、その結果、加算器ブロックが「シンドロームレジスタ」にロードされた後に、Ｓ１＝ｒ（α）になる。シンドロームレジスタは、イネーブル信号として「シンドロームロード」を用いるシフトレジスタとして働く。次の２ｔ−１サイクルの間に、残りのシンドロームをシンドロームレジスタに取り込むためにロードイニシャル＝０をマークすることができる。全体で、ＳＣ段は、２ｔ個のシンドロームを計算するために２ｔサイクルを要する。
【００６９】
キー方程式ソルバー（ＫＥＳ）
図９は、本開示の典型例に従ってバーレカンプの反復法に基づいて誤りロケータ多項式σ（ｘ）を計算するように構成されている例示的なキー方程式ソルバーアーキテクチャを例として説明する。ある実施形態では、低複雑度キー方程式ソルバーアーキテクチャ９００は、正確に２ｔサイクル内にバーレカンプ反復法に基づいて誤りロケータ多項式σ（ｘ）を計算するために使用され得る。例示的な実装では、１≦μ≦２ｔに対してμ番目の反復でσ（μ＋１）（ｘ）を更新するために、不一致ファクタｄμを計算することができ、訂正ファクタ
【数１１】
2018019401.tif 000015
を計算することができる。承知の通り、レジスタと多項式とは、同じ実体に言及するために明細書全体を通じて区別しないで用いられる。例示的な実装では、レジスタは、同じ名前である多項式の係数を記憶することができる。例示的な実装では、レジスタσμおよびσρは、図９に示された通り、それぞれσμ（ｘ）およびσρ（ｘ）の係数を記憶するために使用され得る。ｄρとｌρとｌμとに対するレジスタも使用され得る。最初に、σμ，ｄρ，ｌρがμ＝−１に対応する値と共にロードされ得る。σμおよびｌμは、表１の通りμ＝０に対応する値と共にロードされ得る。復号反復が進むとき、σμおよびｌμは、それぞれ式７および式８の通りの値を用いて、ｄμ≠０のときに更新される。σρ，ｄρ，ｌρは、その結果、ｄμ≠０かつμ−ｌμ≧ρ−ｌρであるとき、σμとｄμとｌμとを用いて更新される。例示的な実装では、不一致ファクタｄμは、図９に示された通りＳ２，Ｓ１，０，．．０を用いて初期化された、サイズｔ＋１である一時レジスタを使用して反復毎に特定され得る。
【００７０】
例示的な実装では、一時レジスタは、加算器ブロックΣ１の後にｄμを生じさせるシフトレジスタとしての機能を果たし得る。気付く通り、加算器ブロックΣ２の出力は、
【数１２】
2018019401.tif 000016
となり得る。σμレジスタは、マルチプレクサＭ２を使用してｄμに基づいて更新され得る。バーレカンプ反復法において、シンドロームレジスタは、次のパイプライン段のため使用され得る初期シンドローム値を保持するために回数２ｔだけ回転させられる。シンドロームレジスタを回数２ｔだけ回転させるアイデアは、キー方程式ソルバーがシンドロームを記憶するため別のレジスタの組を必要とはしないので、かなりの数のレジスタを節約する。
【００７１】
例示的な実装では、訂正ファクタ
【数１３】
2018019401.tif 000017
は、σμレジスタを更新するために計算され得る。例示的な実装では、ｄμおよびｄρは、評価することができるが、μ−ρは、いずれかの整数値であればよい。ｘμ−ρσρを計算するために、バレルシフタがμ−ρだけσρをシフトするために使用され得る。バレルシフタは、大規模な面積を必要とし、最大動作周波数に影響を与え、次に、スループットに影響を与える複雑な組み合わせ論理回路である。ｘμ−ρσρ（ｘ）がσρ（ｘ）の代わりに、σρレジスタ内に記憶され得る場合、バレルシフタを回避することができ、これは、図９に示された通りσρにロードする前に、単純な「左へ１つシフト」によってまたはｘ倍することによって達成され得る。このアプローチを用いると、σρレジスタの初期値は、反復復号を開始する前に「１」の代わりにｘであるべきである。ｄμ≠０かつμ−ｌμ≧ρ−ｌρであるとき、σρレジスタは、ｘσμになる。例示的な実装では、図９に示された「ＬＯＡＤシグマ」は、σρを更新するために使用され得る。２ｔ回の反復の後、σρレジスタおよびｌμは、それぞれ誤りロケータ多項式σ（ｘ）およびυを収容し、これらは、パイプラインアーキテクチャの次の段に送信され得る。
【００７２】
チェン探索および誤りマグニチュード計算
誤り評価Ｚ（ｘ）は、図９に示された通り、ｄμ計算と同様に計算され得る。図１０は、本開示の実施形態に従ってＺ（ｘ）を決定するために使用され得る例示的な誤り評価アーキテクチャを例として説明する。アーキテクチャ１０００は、エラー評価
【数１４】
2018019401.tif 000018
を計算するために使用され得る。承知の通り、Ｚ（ｘ）は、ｌμ個の係数を含み、Ｚｉは、ｘｉの係数である。各係数は、アーキテクチャ１０００を使用して１つずつ得られる。例示的な実装では、「シンドロームレジスタ」は、図１０に示された通り、左回転するために使用される。Ｓ１，０，０，．．．０を用いて初期化されることがあるシフトレジスタ「中間レジスタ」が使用され得る。計算が進むのにつれて、中間レジスタは、図１０に示された通り、シンドロームの第２のインデックスからロードされ得る。シフトレジスタは、ＫＥＳから取得された「σ（ｘ）レジスタ」とインデックス方向に乗じられ、Ｚ（ｘ）の各係数を与えるために加算され得る。例示的な実装では、全て零を用いて初期化された、サイズｉの「Ｚ（ｘ）レジスタ」は、Ｚ（ｘ）の係数を記憶するために使用され得る。このレジスタは、係数全部をＺ（ｘ）レジスタに取り込むために、ｌμ回のサイクルにわたってハイに留まるイネーブル信号ｌｏａｄを用いるシフトレジスタである。ｔ−ｌμ回のサイクルにわたって、Ｚ（ｘ）レジスタは、最も右（最下位）位置にＺ０を有するために右回転させられる。Ｚ（ｘ）の全ての係数を計算するためにｔ回のサイクルを要する。
【００７３】
例示的な実装では、並列度Ｊのチェン探索は、ＧＦ（２ｍ）上で多項式ｆ（ｘ）＝ｆ０＋ｆ１ｘ＋ｆ２ｘ２＋・・・＋ｆｎｘｎの根を計算するために使用され得る。分かる通り、ｊ個のフィールド要素が１サイクル内でテストされ得る。本開示のＲＳ復号器は、１≦ｊ≦ｎに対してσ（α−ｉ）およびＺ（α−ｉ）を評価するためにこのアーキテクチャを使用し得る。例示的な実装では、アーキテクチャの各々の一定の被乗数は、これの逆数に変更が可能である。
【００７４】
例示的な実装では、σ’（α−ｉ）は、Ｆｏｒｎｅｙの式９により誤りマグニチュードを計算するために使用され得る。誤りマグニチュードを計算するために、誤りロケータおよびマグニチュード計算アーキテクチャが使用され得る。この誤りロケータおよびマグニチュードアーキテクチャは、σ（ｘ）の偶数係数および奇数係数をそれぞれ使用して構築されたσｅｖｅｎ（ｘ）およびσｏｄｄ（ｘ）を含み得る。標数２の有限体上で
【数１５】
2018019401.tif 000019
であることが分かる。
【００７５】
例示的な実装では、並列度Ｊのチェン探索は、別々にσ（α−ｉ）およびσ’（α−ｉ）を評価することを回避するために別々にσｅｖｅｎ（ｘ）およびσｏｄｄ（ｘ）の計算のため使用され得る。例示的な実装では、並列度Ｊのチェン探索アーキテクチャは、対応する誤り値で同時に誤りマグニチュードを見つけるためにＺ（α−ｉ）を評価するようにＺ（ｘ）に対しても使用され得る。並列度Ｊのチェン探索アーキテクチャを用いると、あらゆるクロックサイクル内に生成されたｊ個の誤りマグニチュードは、推定符号語を得るために対応する受信シンボルに加算され得る。誤りベクトル全体を計算するために、ｎ／ｊサイクルが必要とされることがある。
【００７６】
以下の表３は、ＲＳ復号器の各段に必要であるクロックサイクルを例として説明する。
【表３】
2018019401.tif 000020
【００７７】
分かる通り、誤り訂正能力の関数としての復号器のスループットは、以下の通り式１０を使用して計算され得る。
【数１６】
2018019401.tif 000021
式中、ｎ、ｍ、ｔおよびｆｍａｘは、符号長、シンボル幅、誤り訂正能力および最大動作周波数をそれぞれ表している。Ｊがｎ／ｊ＝ｔとなるように選択されると、スループットが最大化される。分かる通り、Ｊの選択は、スループットとハードウェア複雑度との間のトレードオフを判定する。同様に、設計されたリード・ソロモン復号器の合計レイテンシは、表３の通り各段に必要であるサイクルの和によって与えられる。
【数１７】
2018019401.tif 000022
【００７８】
気付く通り、誤り評価計算および誤りマグニチュード計算が独立したパイプライン段として分割されるとき、スループットは、より一層改善される。
【００７９】
２段パイプライン型の低レイテンシ復号器
例示的な実装では、ＨＤＤ復号器のレイテンシは、ＳＣとＫＥＳの両方が図４に示された通り単一パイプライン段に統合された場合、スループットにあまり影響を与えることなく著しく低下され得る。図１１は、シンドローム計算１１０２およびＫＥＳ計算１１０４が本開示の好ましい実施形態に従って単一段に統合された例示的な２段の低レイテンシパイプライン型の復号器を例として説明する。ＳＣ１１０２およびＫＥＳ段１１０４の統合は、ＳＣ段１１０２がクロックサイクル毎に１個のシンドロームを出力し、ＫＥＳ段１１０４は、シンドロームのアレイから「一時レジスタ」の中へあらゆるクロックサイクルの間に入力として１個のシンドロームを必要とするので、実行できる。しかしながら、ＫＥＳ段１１０４は、図９に示された通り、「一時レジスタ」がＳ２，Ｓ１，０，．．０を用いて初期化される必要があるので、ＳＣ段と一緒に開始することができない。その結果、ＫＥＳ段は、付加的な２クロックサイクルを待機する必要がある。これに伴って、スループットは、ほとんど同一であり、遅延バッファのサイズも著しく縮小する。本実装では、図９に示されたシンドロームレジスタを回転させることは、必要とされないことがある。例示的な実装では、図８に示されたシンドロームレジスタは、クロックサイクル毎に１個のシンドロームを一時レジスタにロードするため使用され得る。この復号器のレイテンシは、
ＳＣとチェンおよび誤りマグニチュード計算段１１０６とのため必要であるクロックサイクルの合計によって式１２を使用して計算され得る。
【数１８】
2018019401.tif 000023
【００８０】
所与の関心符号に対して、ＳＣとチェン探索および誤りマグニチュード計算とがほとんど２ｔ回のクロックサイクルを要するとき、復号器が並列性を利用可能にできない場合、提案された低レイテンシ２段パイプライン型のアーキテクチャは、シンドローム計算段とチェン探索および誤り計算段とが両方ともにほとんど同数のクロックサイクルを要するので、何ら問題なしに使用され得る。提案されたシンドローム計算段１１０２とキー方程式ソルバー段１１０４との組み合わせを用いると、復号器は、パイプラインストールを減らすためによく知られた３段パイプライン型のアーキテクチャにおいて必要とされる通りＫＥＳアーキテクチャを多数のＳＣならびにチェン探索および誤りマグニチュード計算ブロックと時間多重化する必要がない。例示的な実装では、並行して多数のＫＥＳが多数の受信ベクトルを操作し、より高いスループットを達成するために使用され得る。
【００８１】
分かる通り、ＬＣＣ復号器のスループットおよびレイテンシは、以前の復号器より優れている。要するに、多重割当ユニットは、η個の信頼できない位置および対応するｒ
ｉ［２ＨＤ］個の値を得るためにｎ＝２５５サイクルを要する。例示的な実装では、状態機械は、ＥＮ１，ＥＮ２，．．． ，ＥＮηを制御し、２η個のテストベクトルの全てを得るために使用され得る。
【００８２】
例示的な実装では、２η個のテストベクトルのうちの各テストベクトルは、提案された２段パイプライン型のＨＤＤを通過させることが可能であり、２段パイプライン型のＨＤＤにおける最も遅い段は、チェン探索および誤りマグニチュード計算ブロックであり、これは、Ｊ＝１０に対して、ｔ＋ｎ／Ｊ＝３６サイクルを要する。多重割当は、η＝３に対して、ＥＮ３＝０；ＥＮ２＝０；ＥＮ１＝１であるときに開始される。これが実行可能であるのは、
【数１９】
2018019401.tif 000024
であるからである。従って、長期的には、各受信ベクトルｒ［ＨＤ］は、訂正されるためにｎ＝２５５サイクルを要する。その結果、軟ＬＣＣ復号器のスループットおよびレイテンシは、それぞれ式１３および式１４によって以下の通り与えられる。
【数２０】
2018019401.tif 000025
【００８３】
以下の表４は、ブロック長ｎ＝４１０である２段パイプライン型のＨＤＤを使用するＲＳ復号器の要約を例として説明する。
【表４】
2018019401.tif 000026
【００８４】
本開示のＲＳ復号器を文字通り他の設計と比較するために、ＲＳ（２５５，２３９）復号器がＧＦ（２８）上に設計された。
【数２１】
2018019401.tif 000027
であるようなＪ＝３０を選択すると、スループット２４Ｇｂｐｓを生じる。面積とスループットとの間にトレードオフが存在する。Ｊ＝１０を選択することによって面積を節約できるが、Ｊの縮小に伴って、スループットが１２Ｇｂｐｓに低下する。以下の表５は、本開示に従って設計されたＪ＝１０であるＲＳ復号器とＫｉｎｔｅｘ−７  ＦＰＧＡ上のＲＳ（２５５，２３９）に対するザイリンクスＩＰのＲＳ復号器ｖ９．０との間の比較を示す。
【表５】
2018019401.tif 000028
【００８５】
分かる通り、提案ＲＳ復号器では、全ての必要とされるガロア体算術がＬＵＴおよびＦＦを使用して実装されるのでＢＲＡＭが使用されない。これに対して、ザイリンクスＩＰは、２つの１８ｋ  ＢＲＡＭおよび１つの３６ｋ  ＢＲＡＭという点で巨大なメモリを利用し、このことが本開示のＲＳ復号器と比べてＬＵＴおよびＦＦの利用を節約する。ＢＲＡＭ、ＬＵＴおよびＦＦを全体で考慮すると、本開示およびザイリンクスＩＰのＲＳ復号器は、ほとんど同じハードウェア資源を利用することが分かる。しかしながら、本開示のＲＳ復号器によってスループットの観点で達成される利得はほとんど５倍であり、これは、著しい改善である。Ｊ＝１０として誤り評価計算および誤りマグニチュード計算が独立したパイプライン段として分割される場合、スループットは、１６Ｇｂｐｓになるであろう。Ｋｉｎｔｅｘ−７  ＦＰＧＡ上に実装された設計は、図５に示される通りチップスコープを使用して検証される。
【００８６】
図１２は、チップセット上に設計されたＲＳ（２５５，２３９）復号器の結果を示す。
【００８７】
ある態様では、テクノロジー・スケールド・ノーマライズド・スループット（ＴＳＮＴ）指標が異なる製造技術を使った異なる設計性能を評価するために使用される。分かる通り、ＴＳＮＴは、以下の式１５を使用して計算され得る。
【数２２】
2018019401.tif 000029
【００８８】
表６は、競合する復号器実装に関してＪ＝１０である提案ＲＳ復号器の比較を示す。提案１８０−ｎｍＲＳ（２５５，２３９）復号器のＴＳＮＴ値は、既存の設計より少なくとも１．８倍良好であり、このことは、提案復号器が所与のスループットに対してはるかに面積効率が良いことを表す。表６は、提案１８０−ｎｍ復号器のレイテンシが既存の１８０−ｎｍ設計と比べてほとんど８０％低下されていることをさらに例として示す。さらに、提案ＲＳ（２５５，２３９）復号器は、ＲＳ（２５５，２４５）デュアルラインアーキテクチャにおけるＥＣＣ能力が提案ＲＳ（２５５，２３９）復号器のＥＣＣ能力より低いにもかかわらず、ＲＳ（２５５，２４５）デュアルラインアーキテクチャよりレイテンシが５倍を超えて優れている。
【表６】
2018019401.tif 000030
【００８９】
以下の表７は、既存のＬＣＣ復号器と本開示のＬＣＣ復号器との間の比較を示す。本開示のＬＣＣ復号器は、２段パイプライン型のＨＤＤを使用して実装され、既存のＬＣＣ復号器より多くのハードウェア資源を消費する。しかしながら、本開示のＬＣＣ復号器は、より高いスループットおよびより低いレイテンシで動作する。ＨＤＤにおける誤り評価計算および誤りマグニチュード計算が独立したパイプライン段として分割される場合、本開示のＬＣＣ復号器は、
【数２３】
2018019401.tif 000031
ではなく、
【数２４】
2018019401.tif 000032
を満たすことができる。従って、本開示のＬＣＣ復号器は、低下した複雑度で同じスループットを達成する。
【表７】
2018019401.tif 000033
【００９０】
図１３は、ＨＤＤと、本開示の実施形態に従って設計されたη＝３およびη＝４に対するＬＣＣ復号器とのＦＥＲ性能を例として説明する。
【００９１】
例示的な実装では、ＧＦ（２８）上に実装されたＲＳ（２５５，２３９）復号器は、ＶＨＤＬを使用してＫｉｎｔｅｘ−７  ＦＰＧＡ上に実装され得る。分かる通り、パイプライン型のＨＤ  ＲＳ復号器のスループットは、同じハードウェア資源利用を行い、最大スループット２４Ｇｂｐｓで動作する既存の復号器と比べるとほとんど５倍である。ＳＤＤのスループットは、既存の設計と比べるとほとんど２倍である。本開示のＳＤＤおよびＨＤＤの全体的な処理レイテンシは、既存の設計と比べるとそれぞれほとんど５８％および８０％低下している。
【００９２】
本開示のＲＳ復号器は、補間および因数分解のないハイブリッド型低複雑度チェイスアルゴリズムを使用し、所望のフレーム誤り率（ＦＥＲ）を達成する。本開示のＲＳ復号器は、低下した複雑度で、ｍ＝４であるＫＶアルゴリズムの場合と同じフレーム誤り率（ＦＥＲ）性能を達成し得る。
【００９３】
図１４は、本開示の実施形態による提案ＲＳ復号器による復号化の方法を表す例示的なプロセスを例として説明する。例示的な態様では、本開示は、リード・ソロモン（ＲＳ）復号器のための復号方法１４００を提供し、この方法は、ステップ１４０２において、シンドローム計算（ＳＣ）モジュールによって、１つ以上の受信シンボルを処理することによりシンドロームＳｊを計算するステップと、ステップ１４０４において、キー方程式ソルバー（ＫＥＳ）によって、計算されたシンドロームＳｊから誤りロケータ多項式σｉを計算するステップと、ステップ１４０６において、チェン探索および誤りマグニチュード計算モジュールによって、計算された誤り位置多項式σｉから誤り位置Ｘｉ、および、誤りマグニチュードＹｉを計算するステップと、を含む。
【００９４】
例示的な態様では、誤りロケータ多項式σｉは、バーレカンプ・マッシー・アルゴリズムを使用して、計算されたシンドロームＳｊから計算され、誤りマグニチュードＹｉは、Ｆｏｒｎｅｙの公式を使用して計算される。
【００９５】
例示的な態様では、この方法は、テストベクトル生成モジュールによって２η個のテストベクトルを生成するステップをさらに含み、２η個のテストベクトルのうちの各テストベクトルは、ＳＣモジュールに渡される。
【００９６】
上記は発明の様々な実施形態を説明するが、発明のその他およびさらなる実施形態は、発明の基本的な範囲から逸脱することなく考え出されることがある。発明の範囲は、続く特許請求の範囲によって決定される。発明は、記載された実施形態、バージョンまたは実施例に限定されることがなく、これらは、当業者が利用できる情報および知識と組み合わされたとき、当業者が発明を行えるように、および、使用できるようにするために含まれている。
【００９７】
発明の効果
本開示は、高速ストレージおよび通信システムのためのＲＳ復号器と方法とを提供する。
【００９８】
本開示は、チャネル特性および性能に依存して設定可能な誤り訂正能力を有効にすることができる設定可能なＲＳ復号器とその方法とを提供する。
【００９９】
本開示は、必要な面積がより小さく、かつ、高スループットおよび低レイテンシを達成する、高速ストレージおよび通信システムのためのＲＳ復号器を提供する。
【０１００】
本開示は、高スループットおよび低レイテンシを達成することができる、高速ストレージおよび通信用途のためのＲＳ復号器を提供する。
【図１】
2018019401.tif 000034
【図２】
2018019401.tif 000035
【図３】
2018019401.tif 000036
【図４】
2018019401.tif 000037
【図５】
2018019401.tif 000038
【図６】
2018019401.tif 000039
【図７】
2018019401.tif 000040
【図８】
2018019401.tif 000041
【図９】
2018019401.tif 000042
【図１０】
2018019401.tif 000043
【図１１】
2018019401.tif 000044
【図１２】
2018019401.tif 000045
【図１３】
2018019401.tif 000046
【図１４】
2018019401.tif 000047
【外国語明細書】
2018019401000001.pdf