JP2018019401A - リード・ソロモン復号器及び復号方法 - Google Patents

Abstract

【課題】光通信およびストレージに適した高速・低レイテンシ・レート設定可能な軟判定および硬判定に基づくパイプライン型のリード・ソロモン（ＲＳ）復号器アーキテクチャを提供する。【解決手段】ＲＳ復号器は、チャネルを監視し、チャネル容量に基づいて符号パラメータを調整する。軟判定復号器（ＳＤＤ）を実装するために補間および因数分解なしの低複雑度チェイス（ＬＣＣ）復号を含む。テストベクトルを生成し、これらをパイプライン型の２段硬判定復号器（ＨＤＤ）に供給する。並列性なしで正確に２ｔ回のクロックサイクル内に誤りロケータ多項式を計算し、高スループットをサポートし、正確にｔ回のサイクル内に誤り評価多項式をさらに計算する。低いレイテンシおよび縮小されたサイズのデータバッファで動作する２段パイプライン型とする。【選択図】図１１

Description

本開示は、誤り訂正符号の分野に関する。詳しくは、本開示は、高速ストレージおよび通信システムのための復号器および復号方法に関する。

背景技術の説明は、本発明を理解するのに役立つことがある情報を含む。このことは、本書に記載された情報のうちのいずれかが先行技術であること、もしくは、本願請求項に係る発明に関連していること、または、具体的もしくは明示的に参照された刊行物が先行技術であることを自認するものではない。

たとえば、光ファイバネットワーキングシステムなどを通じて得られる高速データ伝送と、高速ストレージ装置のため必要とされる高速データ処理とは、より高いデータレートという継続的な要望を満たすために高スループットをサポートすることができる効率的な誤り訂正符号を必要とする。リード・ソロモン（ＲＳ）符号は、これらのバースト誤り訂正機能が保証されているので様々なストレージおよび通信用途において広く用いられている。しかしながら、高速であり、かつ、面積効率の良いＲＳ復号器アーキテクチャを実装することは、いつでも重要な課題である。適切なＲＳ復号器アーキテクチャを開発することは、スループット、面積、およびレイテンシの間のトレードオフをいつでも必要とする。

ＦＧＰＡに実装された最新式の硬判定（ＨＤ）ＲＳ復号器は、とても２Ｇｂｐｓという最大スループットに到達しない。最近公表されたＸｉｌｉｎｘのＲＳ復号器ＩＰは、ＲＳ（２５５，２３９）符号に対して３．２Ｇｂｐｓという最大スループットをサポートする。ＡｌｔｅｒａのＲＳ ＩＰコアは、同様に、ＲＳ（２０４，１８８）符号に対して３Ｇｂｐｓという最大スループットをサポートする。

承知の通り、復号には主に２つのカテゴリー：代数的軟判定復号器（ＳＤＤ）および硬判定復号器（ＨＤＤ）が存在し、ここで、ＳＤＤは、ＨＤＤより高い複雑度でＨＤＤより優れた誤り性能を提供する。しかしながら、ＳＤＤは、実装のため広い面積を必要とする。Ｋｏｅｔｔｅｒ−Ｖａｒｄｙ（ＫＶ）アルゴリズムに基づく最初の、よく知られているＳＳＤは、３つの主要なステップ：多重（ｍ）割当、補間および因数分解を含む。ＫＶのようなアーキテクチャの１つの主要な問題は、ＫＶアルゴリズムに基づくＳＤＤが補間ステップおよび因数分解ステップの複雑度のため、より大きい面積を必要とすることである。

既存のＲＳ復号器に関する別の問題は、この復号器が誤り訂正機能の点において柔軟性をもたらさないことである。既存のＲＳ復号器の多くは、固定誤り訂正機能を用いて構成され、チャネル特性および性能とは無関係に復号を行う。

従って、チャネル特性および性能に依存して誤り訂正機能を選択することができる設定可能なＲＳ復号器およびその復号方法が当該技術において必要である。ＲＳ復号器およびその実装／実施の方法も高速ストレージシステムおよび高速伝送システムのための高スループットおよび低レイテンシを達成するために必要である。

本書においてあらゆる刊行物は、参照によって、個別の刊行物または特許出願が具体的かつ個別に参照によって援用されることが示されるのと同じ程度まで援用される。援用文献における用語の定義または使用が本書において示された用語の定義に矛盾する、もしくは、反する場合、本書において示された用語の定義が適用され、参照における用語の定義は適用されない。

一部の実施形態では、発明のある特定の実施形態を記述し、権利を主張するために用いられた成分の量、濃度のような特性、反応条件などを表現する数は、場合によっては、用語「およそ」によって修正されているとして理解されるべきである。その結果、一部の実施形態では、明細書および特許請求の範囲に記載された数値パラメータは、特有の実施形態によって得られようとしている所望の特性に依存して変化し得る近似値である。一部の実施形態では、数値パラメータは、報告された有効数字を考慮して、かつ、通常の丸め技術を適用することによって解釈されるべきである。広範囲にわたる発明の一部の実施形態を明記する数値範囲およびパラメータは、近似値であるにもかかわらず、具体的な実施例において明記された数値は、実行可能な限り正確に報告されている。発明の一部の実施形態において示された数値は、それぞれの検査測定値に見られる標準偏差によって必然的に生じるある一定の誤差を含むことがある。

本書における説明中で、かつ、続く特許請求の範囲の全体を通じて用いられるように、単数形「ａ（単数形不定冠詞）」、「ａｎ（単数形不定冠詞）」、および「ｔｈｅ（定冠詞）」の意味は、文脈上明白に他の指示がない限り複数形への言及を含む。同様に、本書における説明中で用いられるように、「ｉｎ（〜の中に）」の意味は、文脈上明白に他の指示がない限り「ｉｎ（〜の中に）」および「ｏｎ（〜に接して）」を含む。

本書における値の範囲の列挙は、この範囲に含まれる個別の値を個別に参照する簡単な方法としての役割を果たすように意図されているに過ぎない。本書において他の指示がない限り、個別の値は、本書において個別に挙げられているかのように明細書に組み込まれる。本書において記載されたあらゆる方法は、本書において他の指示がない限り、または、そうでなければ、文脈上明白に矛盾しない限り、何らかの適切な順序で行われ得る。本書においてある特定の実施形態に関連して示されたありとあらゆる実施例、または、例示的な言葉（たとえば、「ｓｕｃｈ ａｓ（たとえば、〜など）」）の使用は、例を使って発明をより良く説明することが意図されているだけであり、他の主張がなければ、発明の範囲に制限を課すものではない。明細書中の言葉は、請求項に記載がなく、発明の実施に不可欠である何らかの要素を指示するものとして解釈されるべきではない。

本書に開示された発明の代替的な要素または実施形態のグループ分けは、限定として解釈されるべきではない。各グループメンバーは、個別に、または、グループの他のメンバーもしくは本書において見られる他の要素と組み合わせて、参照されるまたは請求項に記載されることが可能である。グループの中の１つ以上のメンバーは、利便性および／または特許性の理由のため、グループに包含、または、グループから削除される可能性がある。このような包含または削除が行われたとき、明細書は、本書では、特許請求の範囲で用いられたあらゆるグループについての書面記載を満たすように修正された通りのグループを含んでいると見なされる。

本開示の全般的な目的は、高速ストレージおよび高速通信システムのためのＲＳ復号器および復号方法を提供することである。

本開示の目的は、チャネル特性および性能に依存して設定可能な誤り訂正機能を有効にすることができる設定可能なＲＳ復号器およびその復号方法を提供することである。

本開示の別の目的は、特定のスループットのため高速ストレージおよび高速通信システムで用いられた従来型のＲＳ復号器より小さい面積を必要とするＲＳ復号器を提供することである。

本開示のさらに別の目的は、高速ストレージおよび高速通信アプリケーションのための高スループットおよび低レイテンシを達成することができるＲＳ復号器を提供することである。

本開示の態様は、誤り訂正符号の分野に関する。より詳しくは、本開示は、高速ストレージシステムおよび高速通信システムのための復号器および復号方法に関する。

本開示の態様は、リード・ソロモン復号器アーキテクチャおよびその方法を提供する。実施形態では、高速・低レイテンシ・レート設定可能な軟判定および硬判定に基づく２段パイプライン型のリード・ソロモン（ＲＳ）復号器アーキテクチャが提供される。

本開示の実施形態は、テストベクトルを処理し、シンドロームを生成するように構成され、２ｔ個のシンドロームを計算するために２ｔサイクルを要するシンドローム計算（ＳＣ）モジュールと、誤りロケータ多項式を計算するように構成されているキー方程式ソルバー（ＫＥＳ）と、誤り位置および対応する誤りマグニチュードを見つけるように構成されているチェン探索および誤りマグニチュード計算（ＣＳＥＭＣ）モジュールとを含み、ＳＣモジュール、ＫＥＳおよびＣＳＥＭＣモジュールが２段パイプライン方式で配置されているリード・ソロモン（ＲＳ）復号器を提供する。

ある態様では、ＲＳ復号器は、補間および因数分解のない低複雑度チェイス（ＬＣＣ）復号を使用するように構成されている軟判定復号器（ＳＤＤ）として構成され得る。

別の態様では、ＲＳ復号器は、誤りロケータ多項式を取得するために２ｔ回の反復を要するバーレカンプ・マッシー（ＢＭ）アルゴリズムに基づくｔシンボル訂正復号器である２段硬判定復号器（ＨＤＤ）として構成され得る。

ある態様では、ＲＳ復号器は、チャネル容量を監視し、監視されたチャネル容量に基づいて符号パラメータを調整するように構成されている。

ある態様では、ＫＥＳは、バーレカンプ・マッシー（ＢＭ）アルゴリズムまたは修正ユークリッド（ＭＥ）アルゴリズムを使用して誤りロケータ多項式を計算する。

ある態様では、テストベクトル生成器モジュールは、ＳＣモジュールへの入力として与えられる２^η個のテストベクトルを生成する。ある態様では、遅延バッファは、テストベクトルを一時記憶するように構成されている。ある態様では、ＳＣモジュールは、低レイテンシを達成し、遅延バッファのサイズを縮小するためにＫＥＳと統合される。

ある態様では、誤りロケータ多項式は、ＲＳ復号器の高スループットを達成するために、並列性なしで２ｔ回のクロックサイクル内で取得される。

ある態様では、ＣＳＥＭＣモジュールは、並列度Ｊのチェン探索アーキテクチャを備える。

ある態様では、本開示は、シンドローム計算（ＳＣ）モジュールによって、テストベクトルを処理することによりシンドロームＳ_ｊを計算するステップと、キー方程式ソルバー（ＫＥＳ）によって、計算されたシンドロームＳ_ｊから誤りロケータ多項式σ_ｉを計算するステップと、チェン探索および誤りマグニチュード計算（ＣＳＥＭＣ）モジュールによって、計算された誤り位置多項式σ_ｉから誤り位置Ｘ_ｉと、対応する誤りマグニチュードＹ_ｉとを計算するステップとを含む、リード・ソロモン（ＲＳ）復号器のための復号方法を提供する。

ある態様では、誤りロケータ多項式σ_ｉは、バーレカンプ・マッシー・アルゴリズムを使用して、計算されたシンドロームＳ_ｊから計算され、誤りマグニチュードＹ_ｉは、Ｆｏｒｎｅｙの公式を使用して計算される。

ある態様では、この方法は、テストベクトル生成モジュールによって、２^η個のテストベクトルを生成するステップをさらに含み、２^η個のテストベクトルのうちの各テストペクトルは、ＳＣモジュールに渡される。

例示的な実装では、ＨＤＤおよびＳＤＤは、レート設定可能であり、様々なチャネル条件で用いるため構成され得る。ＲＳ復号器は、チャネル条件を監視するように構成することができ、その結果、ＨＤＤおよびＳＤＤを設定することができる。

発明の主題の様々な目的、特徴、態様および利点は、類似した符号が同様の構成要素を表している添付図面と併せて、以下の好ましい実施形態の詳細な説明からより一層明白になるであろう。

添付図面は、本開示についてさらに理解を深めるために含まれ、本明細書に援用され、本明細書の一部を構成する。図面は、本開示の例示的な実施形態を例として説明するものであり、詳細な説明と共に、本開示の原理を説明するために役立つ。

本開示の実施形態に従ってＲＳ復号器のため使用され得る例示的なＬＣＣ軟復号器アーキテクチャを例として説明する図である。 本開示の実施形態に従って最低シンボル信頼度位置をソートするため使用され得るソーティングアーキテクチャを例として説明する図である。 本開示の実施形態に従って「Ｃｈレジスタ」を使用する最低シンボル信頼度位置のソーティングを例として説明する図である。 最も信頼できないη個の位置をカウントするｌｏｃレジスタを例として説明する図である。 η個の位置において２番目に信頼できるシンボルを含む例示的なｒ^{［２ＨＤ］}レジスタを例として説明する図である。 本開示の実施形態に従ってテストベクトルを生成するため使用され得る例示的なアーキテクチャを例として説明する図である。 ３段パイプライン型のＲＳ復号器の例示的なブロック図を例として説明する図である。 本開示の実施形態に従って２ｔ個のシンドロームを計算し得るシンドローム計算のための例示的な並列アーキテクチャを例として説明する図である。 本開示の実施形態に従ってバーレカンプ反復法に基づいて誤りロケータ多項式σ（ｘ）を計算するように構成されている例示的なキー方程式ソルバーアーキテクチャを例として説明する図である。 本開示の実施形態に従ってＺ（ｘ）を決定するために使用され得る例示的な誤り評価アーキテクチャを例として説明する図である。 本開示の好ましい実施形態に従ってシンドローム計算およびＫＥＳ計算が単一段に統合される例示的な２段パイプライン型の低レイテンシ復号器を例として説明する図である。 チップセット上に設計されたＲＳ（２５５，２３９）復号器の結果を示す図である。 本開示の実施形態により設計されたＨＤＤ復号器とη＝３およびη＝４に対するＬＣＣ復号器とのＦＥＲ性能を例として説明する図である。 本開示の実施形態に従って提案されたＲＳ復号器による復号の方法を表現する例示的なプロセスを例として説明する図である。

以下は、添付図面に描かれた開示の実施形態の詳細な説明である。実施形態は、開示を明確に伝える程度に詳細である。しかしながら、提示された詳細の程度は、予想される実施形態の変形を制限することが意図されることなく、それどころか、意図は、特許請求の範囲によって規定された通りの本開示の趣旨および範囲内にあるあらゆる改変物、均等物、および代替物を網羅することにある。

特許請求の範囲の各請求項は、侵害目的のため、請求項に明記された様々な要素または制限の均等物を含むものと認識されている別々の発明を規定する。文脈に依存して、「発明」への以下のあらゆる言及は、一部の事例では、ある具体的な実施形態だけに言及することがある。他の事例では、「発明」への言及は、請求項のうち、必ずしも全部ではないが、１つ以上に記載された主題に言及することがある、と認識されるであろう。

本書において使用された様々な用語を以下に示す。請求項において使用された用語が以下に規定されていない限り、出願の時に印刷された刊行物および発行された特許にある通り、関連技術における当業者がこの用語に与えた最広義の定義が与えられるべきである。

本開示の態様は、誤り訂正符号の分野に関する。より詳しくは、本開示は、高速ストレージシステムおよび高速通信システムのための復号器および復号方法に関する。

本開示の態様は、リード・ソロモン復号器アーキテクチャおよびその復号方法を提供する。ある実施形態では、高速・低レイテンシ・レート設定可能な軟判定および硬判定に基づく２段パイプライン型のリード・ソロモン（ＲＳ）復号器アーキテクチャが提供される。

本開示の実施形態は、テストベクトルを処理し、シンドロームを生成するように構成され、シンドローム計算段が２ｔ個のシンドロームを計算するために２ｔサイクルを要するシンドローム計算（ＳＣ）モジュールと、誤りロケータ多項式を計算するように構成されているキー方程式ソルバー（ＫＥＳ）と、誤り位置および対応する誤りマグニチュードを見つけるように構成されているチェン探索および誤りマグニチュード計算（ＣＳＥＭＣ）モジュールとを含み、ＳＣモジュール、ＫＥＳおよびＣＳＥＭＣモジュールが２段パイプライン方式で配置されているリード・ソロモン（ＲＳ）復号器を提供する。

ある態様では、ＲＳ復号器は、補間および因数分解のない低複雑度チェイス（ＬＣＣ）復号を使用するように構成されている軟判定復号器（ＳＤＤ）として構成され得る。

ある態様では、ＲＳ復号器は、誤りロケータ多項式を取得するために２ｔ回の反復を要するバーレカンプ・マッシー（ＢＭ）アルゴリズムに基づくｔシンボル訂正復号器である２段硬判定復号器（ＨＤＤ）として構成され得る。

ある態様では、ＲＳ復号器は、チャネル容量を監視し、監視されたチャネル容量に基づいて符号パラメータを調整するように構成されている。

ある態様では、ＫＥＳは、バーレカンプ・マッシー（ＢＭ）アルゴリズムまたは修正ユークリッド（ＭＥ）アルゴリズムを使用して誤りロケータ多項式を計算する。

ある態様では、テストベクトル生成器モジュールは、ＳＣモジュールへの入力として与えられる２^η個のテストベクトルを生成する。ある態様では、遅延バッファは、テストベクトルを一時記憶するように構成されている。ある態様では、ＳＣモジュールは、低レイテンシを達成し、遅延バッファのサイズを縮小するためにＫＥＳと統合される。

ある態様では、誤りロケータ多項式は、ＲＳ復号器の高スループットを達成するために、並列性なしで２ｔ回のクロックサイクル内で取得される。

ある態様では、ＣＳＥＭＣモジュールは、並列度Ｊのチェン探索アーキテクチャを備える。

ある態様では、本開示は、シンドローム計算（ＳＣ）モジュールによって、テストベクトルを処理することによりシンドロームＳ_ｊを計算するステップと、キー方程式ソルバー（ＫＥＳ）によって、計算されたシンドロームＳ_ｊから誤りロケータ多項式σ_ｉを計算するステップと、チェン探索および誤りマグニチュード計算（ＣＳＥＭＣ）モジュールによって、計算された誤り位置多項式σ_ｉから誤り位置Ｘ_ｉと、対応する誤りマグニチュードＹ_ｉとを計算するステップとを含む、リード・ソロモン（ＲＳ）復号器のための復号方法を提供する。

ある態様では、誤りロケータ多項式σ_ｉは、バーレカンプ・マッシー・アルゴリズムを使用して、計算されたシンドロームＳ_ｊから計算され、誤りマグニチュードＹ_ｉは、Ｆｏｒｎｅｙの公式を使用して計算される。

ある態様では、この方法は、テストベクトル生成モジュールによって、２^η個のテストベクトルを生成するステップをさらに含み、２^η個のテストベクトルのうちの各テストベクトルは、ＳＣモジュールに渡される。

例示的な実装では、ＨＤＤおよびＳＤＤは、レート設定可能であり、様々なチャネル条件で用いるため構成され得る。ＲＳ復号器は、チャネル条件を監視するように構成することができ、その結果、ＨＤＤおよびＳＤＤを設定することができる。

軟判定復号器（ＳＤＤ）
例示的な実装では、チェイス復号アルゴリズムは、他の復号手法と比べると低複雑度を提供するので、チェイス復号アルゴリズムは、提案されたＳＳＤを実装するため使用され得る。承知の通り、たとえば、ＲＳ復号器の代数的軟判定復号（ＡＳＤ）などの他の復号手法は、従来型のＨＤＤより高い符号化利得を提供するが、高い計算複雑度を伴う。ＡＳＤ復号は、チャネル信頼度情報を使用することにより、限界距離復号を超えて誤りの訂正を容易にするが、ＡＳＤ法の間で、グルスワミ・スーダン（ＧＳ）アルゴリズムおよびＫＶアルゴリズムは、より高い複雑度と引き換えにより優れた性能をもたらす。その一方で、チェイス復号は、同等な性能で複雑度の低い解決策を提供する。

低複雑度チェイスアルゴリズム
本開示のＳＤＤは、テストベクトルの組を生成するためにＨＤＤ復号器と共に実装されるように構成することができ、性能パラメータに関して妥協することなく実装が容易であるチェイス復号器を使用し得る。提案されたＳＤＤは、復号半径ｔ＞ｄ_ｍｉｎ／２の範囲内で符号語を補正することができ、ここで、ｄ_ｍｉｎは、符号の最小距離である。低複雑度チェイス（ＬＣＣ）復号器は、シンボル信頼度情報に基づいて、２^η個のテストベクトルを生成するように構成することができ、ここで、「η」個のシンボルがｎ個のシンボルの中から最低信頼度シンボルとして選択され、硬判定または２番目に信頼できる判定が採用される。テストベクトルを作成するために、硬判定シンボルの確率と２番目に良い判定の確率との間で、硬判定がどの程度良好であるかを示し得る比が確定され得る。受信メッセージ多項式ｒ（ｘ）に対する所望の確率比は、式１を使用して推定することができる。

式中、ｒ_ｉ＿ＨＤは、シンボルの硬判定であり、ｒ_{ｉ＿２ＨＤ}は、２番目に信頼できる判定である。（硬判定と２番目に良い判定との間の）確率比が最も悪いη個の点に対応して、テストベクトルと呼ばれる２^ηの組み合わせの組がη個のより信頼性の低い点において硬判定シンボル（ｒ_ｉ＿ＨＤ）または２番目に良い判定（ｒ_{ｉ＿２ＨＤ}）を選択することにより作成され得る。２番目に良い判定は、メッセージシンボル確率の情報に基づいて取得され得る。

実装のために、２番目に良い判定およびテストベクトルを生成する妥当であり、簡単な方法が使用できる。たとえば、ＡＷＧＮチャネル上でのＢＰＳＫ変調は、シンボル信頼度および２番目に信頼できる判定を生成するために使用され得る。ｃ_ｉ＝［ｃ_ｉ１ｃ_ｉ２．．．ｃ_ｉｍ］がｍビットベクトルであるとして符号語ｃ＝［ｃ_１ｃ_２．．．ｃ_ｎ］とすると、ｃ_ｉｊは、ｘ_ｉｊおよびｘ_ｉｊ＝１−２ｃ_ｉｊに変調される。ｎ_ｉｊがガウスランダム雑音サンプルであるとして、ｒ_ｉｊがｃ_ｉｊ・ｒ_ｉｊ＝ｃ_ｉｊ＋ｎ_ｉｊに対応する実数値チャネル観測を表すことにする。

ある態様では、受信機において、ハードスライシングが行われ、このようにして形成された受信ベクトルは、ｙ_ｉ ^［ＨＤ］として表すことができる。ある態様では、シンボル判定ｙ_ｉ ^［ＨＤ］は、（観測ｒ_ｉ１，．．．．ｒ_ｉｍからの）各送信シンボルｃ_ｉに関して行われる。チャネルは、受信された各ビットの信頼度を与える。シンボル内のｍビットの間で、最低信頼度ビットは、このシンボルの最悪の信頼度を定義する。ｉ番目のシンボルのシンボル信頼度λ_ｉは、

を使用して計算できる。値λ_ｉは、シンボル判定ｙ_ｉ ^［ＨＤ］に関する確信度を示し、λ_ｉの値が高いほど、信頼度が大きくなり、逆もまた同様である。２番目に信頼できる判定ｙ_ｉ ^{［２ＨＤ］}は、上記式において最小値を実現するビットを補う、または、判定することによりｙ_ｉ ^［ＨＤ］から取得される。

例示的な実装では、ＬＣＣアルゴリズムは、ｎシンボル信頼度λ_１，λ_２．．．．λ_ｎを昇順に、すなわち、λ_ｉ１≦λ_ｉ２≦・・・≦λ_ｉｎにソートするステップと、低い方からη個の信頼度値を表すインデックスＩ＝｛ｉ_１，ｉ_２，．．．ｉ_η｝を形成するステップと、を含み得る。さらに、２^η個のテストベクトルの組が以下の関係

を使用して生成される。

さらに、各テストベクトルは、ＨＤＤ段に順次に渡され、復号失敗が起こらないベクトルは、受信機で推定符号語として見なされ得る。例示的な実装では、ＨＤＤ段は、バーレカンプ・マッシー・アルゴリズムに基づいて実装され得る。

硬判定誤り訂正法
例示的な実装では、ＲＳ復号器は、誤り訂正を実行できる。誤り訂正法は、以下のように例を用いて説明され得る。たとえば、符号ｃ（ｘ）が加法的誤りｅ（ｘ）によって破損され、ｒ（ｘ）を生じることにする。υは、誤りの個数を表すことにする。このとき、ｅ（ｘ）は、以下の形

を有し、式中、ｙ_ｉは、誤り位置での誤りマグニチュードである。シンドロームは、

として計算することができ、式中、Ｙ_ｉ＝ｙ_ｉおよびＸ_ｉ＝α^ｊである。目的は、ペア（Ｘ_ｉ，Ｙ_ｉ）を取得するために上記２ｔ個の方程式を解法することである。例示的な実装では、誤りロケータ多項式σ（ｘ）として知られている多項式は、

として定義できる。Ｘ_ｉ値は、上記方程式の逆の根を使用して評価され得る。値Ｘ_ｉが与えられると、Ｙ_ｉに関して線形である式５が解法され得る。

ある実施形態では、復号方法が提供される。より詳しくは、シンドロームＳ_ｊを計算するステップと、Ｓ_ｊから誤り位置多項式σ_ｉ、σ_ｉから誤り位置Ｘ_ｉ、および誤りマグニチュードＹ_ｉを計算するステップとを含む、復号のための誤り訂正方法について記載される。例示的な実装では、復号された符号語多項式ｃ（ｘ）は、Ｘ_ｉおよびＹ_ｉから取得されたｅ（ｘ）を加算することにより取得される。各ステップの詳細は、以下の通り示される。
ステップ１：シンドロームＳ_ｊの計算：
シンドロームは、メッセージ多項式ｒ（ｘ）から式５を使用して評価され得る。
ステップ２：Ｓ_ｊからの誤り位置多項式σ_ｉの計算。例示的な実装では、誤りロケータ多項式σ_ｉは、バーレカンプ・マッシー・アルゴリズムを使用してＳ_ｊから計算され得る。例示的な実装では、σ（ｘ）は、２ｔ回のステップにおいて反復的に計算され得る。σ^μ（ｘ）が反復のμ番目のステップでの誤りロケータ多項式を表すことにする。σ（ｘ）を反復的に見つけるために、論理表１を埋めることができる。ｌ_μがσ^（μ）（ｘ）の次数であるとする。表１のμ番目の行が埋められたとき、反復ステップは、以下に示された手順を使用して（μ＋１）番目の行を見つけることができる。

ｄ_μ≠０である場合、μ番目の行より前に別の行ρが探索され、ここで、ｄ_ρ≠０であり、表１の最後の列における数ρ−ｌ_ρは、最大値をとる。
σ^{（μ＋１）}（ｘ）およびｌ_μ＋１は、それぞれ式７および式８を使用して繰り返し計算される。

ステップ３：誤り位置多項式σ_ｉからの誤り位置Ｘ_ｉの計算。例示的な実装では、誤り位置Ｘ_ｉは、チェン探索を使用して誤り位置多項式σ_ｉから計算され得る。例示的な実装では、α^−１が誤りロケータ多項式σ（ｘ）の根である場合、誤りが位置ｉに存在していると結論付けられる。
ステップ４：誤りマグニチュードＹ_ｉの計算。例示的な実装では、誤りマグニチュードＹ_ｉは、以下の式９として与えられたＦｏｒｎｅｙの公式を使用して計算され得る。

式中、

例示的な実装では、復号された符号語多項式ｃ（ｘ）は、Ｘ_ｉおよびＹ_ｉから取得されたｅ（ｘ）を加算することにより取得され得る。

図１は、本開示の実施形態に従ってＲＳ復号器のために使用され得る例示的なＬＣＣ軟復号器アーキテクチャ１００を例として説明する。図１に示された通り、ＬＬＣ復号の主要なステップは、（ｉ）多重割当モジュール１０２によって実行される多重割当と、（ｉｉ）テストベクトル生成器１０４によって実行されるテストベクトルの作成と、（ｉｉｉ）２段パイプライン型のＨＤＤ１０６によって実行されるテストベクトルのＨＤＤとを含む。ある態様では、ＬＣＣ復号プロセスは、η＜２ｔである場合に、受信点から信頼度情報を使用して、２^η個の異なるテストベクトルを作成する。η＞２ｔに対して、既存の復号器の複雑度は非常に高いので、これの実装は実現困難であることが実証されている。２^η個のテストベクトルのうちの１つがｔ＋１個より少ない誤りを有する場合、復号器は、いかなる場合でもこれらの誤りを訂正し得るであろう。提案されたＲＳ復号器のアーキテクチャは、バーレカンプ・マッシー・アルゴリズム（ＢＭＡ）に基づく２段パイプライン型のＨＤＤを使用する。ＢＭＡベースのＲＳ符号器に対して、受信メッセージがチェン探索法の間に取得された根の個数より高い次数の誤りロケータ多項式σ（ｘ）を生成した場合、復号器障害が起こる。このような場合、誤りの個数がｔより多い場合、復号器は、メッセージを正確に復元できない。例示的な実装では、ＬＣＣ復号器は、以下の仕様に配慮して設計され得る。
−η＝３として、ＧＦ（２^８）上のＲＳ（２５５，２３９）復号器
−チャネル信頼度情報のビット数が４ビットである。
−復号器への入力：ｙ^［ＨＤ］、各シンボルｙ_ｉ ^［ＨＤ］の信頼度情報λ_ｉ、シンボル内で反転させる必要があるビットに関する情報。
−ＢＭアルゴリズムに基づく２段パイプライン型のＨＤ復号器。
多重割当
例示的な実装では、多重割当モジュール１０２は、多重割当を実行することができ、モジュール１０２は、低い方からη個のシンボル信頼度を受信するように構成され得る。最低シンボル信頼度値をソートする過程で、モジュール１０２は、昇順に低い方からη個のシンボル信頼度を得る。これらの低い方からη個のシンボル信頼度をソートする過程で、モジュール１０２は、η個の位置および対応するｒ^{［２ＨＤ］}値を得る。例示的な実装では、「ｌｏｃレジスタ」および「ｒ^{［２ＨＤ］}レジスタ」は、低い方からη個のシンボル信頼度位置および対応する２番目の判定値をそれぞれ記憶するために使用され得る。「Ｃｈレジスタ」は、シンボル信頼度をソートするために役立つ。

図２は、本開示の実施形態に従って最低シンボル信頼度位置をソートするため使用され得るソーティングアーキテクチャ２００を例として説明する。図３は、本開示の実施形態に従って「Ｃｈレジスタ」を使用する最低シンボル信頼度位置のソーティングを例として説明する。図２および図３は、シンボル信頼度のソーティングを示す。ｃｈレジスタ内の各位置は、２^ｑ−１を用いて初期化され、ここで、ｑは、各シンボル信頼度を表現するために使用されるビット数である。シンボル信頼度λ（ｉ）は、ｉ＝０から２５５に対して順次に送信され得る。例示的な実装では、η個の比較器と、表２に示された符号器論理とがＥＮ_ｋ信号およびＥＮ_ｊ信号を生成するために使用され得る。これらのＥＮ_ｋ信号およびＥＮ_ｊ信号は、ｌｏｃレジスタおよびｒ^{［２ＨＤ］}レジスタが低い方からη個のシンボル信頼度位置および対応する２番目の判定値をそれぞれ得るために使用され得る。ソーティングを理解するために、ｑ＝３ビットおよび入力ストリーム｛５，４，６｝を用いて実施例を試行することができる。ｃｈレジスタ内の各位置は、７を用いて初期化され得る。所与のアーキテクチャを用いて、３クロックサイクル内で所要のソート順｛４，５，６｝を得ることができる。０からｎ−１までの値をとるカウンタ「ｃｎｔ（ｉ）」は、図４に示される通りｌｏｃレジスタのため入力される。ｒ_ｉ ^{［２ＨＤ］}は、図５に示される通りｒ^{［２ＨＤ］}に順次に供給され得る。

例示的な実装では、「Ｃｈレジスタ」内の各シンボルは、全て「１」を用いて初期化され得る。シンボル信頼度λ（ｉ）は、ｉ＝０から２５５に対して順次に送信される。例示的な実装では、η個の比較器と表２に示された符号器論理とは、ＥＮ_ｋ信号およびＥＮ_ｊ信号を生成するために使用され得る。これらのＥＮ_ｋ信号およびＥＮ_ｊ信号は、ｌｏｃレジスタおよびｒ^{［２ＨＤ］}レジスタが低い方からη個のシンボル信頼度位置および対応する２番目の判定値をそれぞれ得るために使用され得る。

図４は、低い方から信頼できないη個の場所をカウントするｌｏｃレジスタを例として説明する。例示的な実装では、０から２５５までの値をとるカウンタ「ｃｎｔ（ｉ）」は、図４に示された通りｌｏｃレジスタのための入力として構成され得る。図５は、η個の位置において２番目に信頼できるシンボルを含んでいる例示的なｒ^{［２ＨＤ］}レジスタを例として説明する。例示的な実装では、ｒ_ｉ ^{［２ＨＤ］}は、図５に示された通りｒ^{［２ＨＤ］}レジスタに順次に供給され得る。

テストベクトル生成
図６は、本開示の実施形態に従ってテストベクトルを生成するため使用され得る例示的なアーキテクチャを例として説明する。図６に示された通り、２^η個のテストベクトルが生成され得る。例示的な実装では、状態機械は、ＥＮ_１，ＥＮ_２，．．． ．ＥＮ_ηを制御し、２^η個のテストベクトルを得るために使用され得る。２^η個のテストベクトルのうちの各テストベクトルは、２段パイプライン型のＨＤＤ１０６に渡され得る。

図７は、３段パイプライン型のＲＳ復号器の例示的なブロック図を例として説明する。図７に示された通り、ＲＳ復号器７００は、シンドロームを計算するように構成されているシンドローム計算モジュール７０２と、キー方程式ソルバー７０４と、チェン探索および誤りマグニチュード計算モジュール７０６とを含む。硬判定ＲＳ復号器のキー方程式ソルバー７０４は、誤りロケータ多項式を計算することを目的としてキー方程式を解法するためにバーレカンプ・マッシー（ＢＭ）アルゴリズムまたは修正ユークリッド（ＭＥ）アルゴリズムを使用して実装され得る。ＭＥアルゴリズムは、理解および実装することがより容易であるが、ＢＭアルゴリズムは、計算複雑度および実装の観点から効率的である。好ましい実装では、ＢＭアルゴリズムは、ＦＰＧＡ上に復号器回路を実装するために使用され得る。誤り値は、誤り評価多項式を使用して計算され得る。例示的な実装では、パイプライン方式は、より高いスループットを達成するためにＲＳ復号器に採用され得る。パイプライン型のアーキテクチャでは、全体的なスループットは、最も遅いパイプライン段およびこれの計算時間によって決定される。その結果、効率的な面積利用率でスループットを増加させるために、各パイプライン段は、おおよそ同じ時間内にこれの計算を完了すべきである。ＢＭアルゴリズムを使用して誤りロケータ多項式を計算するキー方程式ソルバー（ＫＥＳ）７０４は、２ｔ回の反復を要する。シンドロームおよび誤りロケータ多項式を所与として、チェン探索および誤りマグニチュード計算モジュール７０６は、誤り評価多項式を計算するため使用され得る。

例示的な実装では、誤りロケータ多項式および誤り評価多項式が誤り位置および対応する誤りマグニチュードを見つけるために使用され得る。並列性は、シンドローム計算（ＳＣ）段とチェン探索および誤りマグニチュード計算段とのため必要とされるクロックサイクルの数を調整するために採用され得る。例示的な実装では、遅延バッファ７０８は、受信シンボルを一時記憶するために使用することができ、遅延バッファのサイズは、復号器のレイテンシに依存する。本開示のＲＳ復号器を使用して復号するため使用される各機能ブロックが次に詳述される。

承知の通り、ほとんどの事例において、ＫＥＳ７０４は、他のブロックが様々なフィールド要素で多項式を評価する並列性を採用し得るので、スループットを決定する、この並列性は、スループットと面積との間のトレードオフを行う。遅延バッファ７０８のサイズは、パイプライン型の復号器のレイテンシによって決定され得るものであり、このことは、レイテンシを減少させる理由の１つである。

シンドローム計算（ＳＣ）
例示的な実装では、シンドローム計算（ＳＣ）は、シンドローム計算モジュール７０２によって実行され得る。シンドロームは、Ｓ_ｊ＝ｒ（α^ｊ）、１≦ｊ≦２ｔとして計算される。図８は、本開示の実施形態に従って２ｔ個のシンドロームを計算することができるシンドローム計算のための例示的な並列アーキテクチャを例として説明する。図８に示された通りシンドローム計算のための並列アーキテクチャ８００は、メッセージ多項式ｒ（ｘ）からシンドロームを決定するため使用され得る。最初に、あらゆるレジスタ「ＲＥＧ」は、零にリセットされ得る。受信ベクトルが準備できると、値ｒ（ｉ）α^ｉをレジスタＲＥＧにロードするために、１クロックサイクルの間、「ロードイニシャル＝１」をマークすることができ、その結果、加算器ブロックが「シンドロームレジスタ」にロードされた後に、Ｓ_１＝ｒ（α）になる。シンドロームレジスタは、イネーブル信号として「シンドロームロード」を用いるシフトレジスタとして働く。次の２ｔ−１サイクルの間に、残りのシンドロームをシンドロームレジスタに取り込むためにロードイニシャル＝０をマークすることができる。全体で、ＳＣ段は、２ｔ個のシンドロームを計算するために２ｔサイクルを要する。

キー方程式ソルバー（ＫＥＳ）
図９は、本開示の典型例に従ってバーレカンプの反復法に基づいて誤りロケータ多項式σ（ｘ）を計算するように構成されている例示的なキー方程式ソルバーアーキテクチャを例として説明する。ある実施形態では、低複雑度キー方程式ソルバーアーキテクチャ９００は、正確に２ｔサイクル内にバーレカンプ反復法に基づいて誤りロケータ多項式σ（ｘ）を計算するために使用され得る。例示的な実装では、１≦μ≦２ｔに対してμ番目の反復でσ^{（μ＋１）}（ｘ）を更新するために、不一致ファクタｄ_μを計算することができ、訂正ファクタ

を計算することができる。承知の通り、レジスタと多項式とは、同じ実体に言及するために明細書全体を通じて区別しないで用いられる。例示的な実装では、レジスタは、同じ名前である多項式の係数を記憶することができる。例示的な実装では、レジスタσ^μおよびσ^ρは、図９に示された通り、それぞれσ^μ（ｘ）およびσ^ρ（ｘ）の係数を記憶するために使用され得る。ｄ_ρとｌ_ρとｌ_μとに対するレジスタも使用され得る。最初に、σ^μ，ｄ_ρ，ｌ_ρがμ＝−１に対応する値と共にロードされ得る。σ^μおよびｌ_μは、表１の通りμ＝０に対応する値と共にロードされ得る。復号反復が進むとき、σ^μおよびｌ_μは、それぞれ式７および式８の通りの値を用いて、ｄ_μ≠０のときに更新される。σ^ρ，ｄ_ρ，ｌ_ρは、その結果、ｄ_μ≠０かつμ−ｌ_μ≧ρ−ｌ_ρであるとき、σ^μとｄ_μとｌ_μとを用いて更新される。例示的な実装では、不一致ファクタｄ_μは、図９に示された通りＳ_２，Ｓ_１，０，．．０を用いて初期化された、サイズｔ＋１である一時レジスタを使用して反復毎に特定され得る。

例示的な実装では、一時レジスタは、加算器ブロックΣ１の後にｄ_μを生じさせるシフトレジスタとしての機能を果たし得る。気付く通り、加算器ブロックΣ２の出力は、

となり得る。σ^μレジスタは、マルチプレクサＭ_２を使用してｄ_μに基づいて更新され得る。バーレカンプ反復法において、シンドロームレジスタは、次のパイプライン段のため使用され得る初期シンドローム値を保持するために回数２ｔだけ回転させられる。シンドロームレジスタを回数２ｔだけ回転させるアイデアは、キー方程式ソルバーがシンドロームを記憶するため別のレジスタの組を必要とはしないので、かなりの数のレジスタを節約する。

例示的な実装では、訂正ファクタ

は、σ^μレジスタを更新するために計算され得る。例示的な実装では、ｄ_μおよびｄ_ρは、評価することができるが、μ−ρは、いずれかの整数値であればよい。ｘ^μ−ρσ^ρを計算するために、バレルシフタがμ−ρだけσ^ρをシフトするために使用され得る。バレルシフタは、大規模な面積を必要とし、最大動作周波数に影響を与え、次に、スループットに影響を与える複雑な組み合わせ論理回路である。ｘ^μ−ρσ^ρ（ｘ）がσ^ρ（ｘ）の代わりに、σ^ρレジスタ内に記憶され得る場合、バレルシフタを回避することができ、これは、図９に示された通りσ^ρにロードする前に、単純な「左へ１つシフト」によってまたはｘ倍することによって達成され得る。このアプローチを用いると、σ^ρレジスタの初期値は、反復復号を開始する前に「１」の代わりにｘであるべきである。ｄ_μ≠０かつμ−ｌ_μ≧ρ−ｌ_ρであるとき、σ^ρレジスタは、ｘσ^μになる。例示的な実装では、図９に示された「ＬＯＡＤシグマ」は、σ^ρを更新するために使用され得る。２ｔ回の反復の後、σ^ρレジスタおよびｌ_μは、それぞれ誤りロケータ多項式σ（ｘ）およびυを収容し、これらは、パイプラインアーキテクチャの次の段に送信され得る。

チェン探索および誤りマグニチュード計算
誤り評価Ｚ（ｘ）は、図９に示された通り、ｄ_μ計算と同様に計算され得る。図１０は、本開示の実施形態に従ってＺ（ｘ）を決定するために使用され得る例示的な誤り評価アーキテクチャを例として説明する。アーキテクチャ１０００は、エラー評価

を計算するために使用され得る。承知の通り、Ｚ（ｘ）は、ｌ_μ個の係数を含み、Ｚ_ｉは、ｘ^ｉの係数である。各係数は、アーキテクチャ１０００を使用して１つずつ得られる。例示的な実装では、「シンドロームレジスタ」は、図１０に示された通り、左回転するために使用される。Ｓ_１，０，０，．．．０を用いて初期化されることがあるシフトレジスタ「中間レジスタ」が使用され得る。計算が進むのにつれて、中間レジスタは、図１０に示された通り、シンドロームの第２のインデックスからロードされ得る。シフトレジスタは、ＫＥＳから取得された「σ（ｘ）レジスタ」とインデックス方向に乗じられ、Ｚ（ｘ）の各係数を与えるために加算され得る。例示的な実装では、全て零を用いて初期化された、サイズｉの「Ｚ（ｘ）レジスタ」は、Ｚ（ｘ）の係数を記憶するために使用され得る。このレジスタは、係数全部をＺ（ｘ）レジスタに取り込むために、ｌ_μ回のサイクルにわたってハイに留まるイネーブル信号ｌｏａｄを用いるシフトレジスタである。ｔ−ｌ_μ回のサイクルにわたって、Ｚ（ｘ）レジスタは、最も右（最下位）位置にＺ_０を有するために右回転させられる。Ｚ（ｘ）の全ての係数を計算するためにｔ回のサイクルを要する。

例示的な実装では、並列度Ｊのチェン探索は、ＧＦ（２^ｍ）上で多項式ｆ（ｘ）＝ｆ_０＋ｆ_１ｘ＋ｆ_２ｘ^２＋・・・＋ｆ_ｎｘ^ｎの根を計算するために使用され得る。分かる通り、ｊ個のフィールド要素が１サイクル内でテストされ得る。本開示のＲＳ復号器は、１≦ｊ≦ｎに対してσ（α^−ｉ）およびＺ（α^−ｉ）を評価するためにこのアーキテクチャを使用し得る。例示的な実装では、アーキテクチャの各々の一定の被乗数は、これの逆数に変更が可能である。

例示的な実装では、σ’（α^−ｉ）は、Ｆｏｒｎｅｙの式９により誤りマグニチュードを計算するために使用され得る。誤りマグニチュードを計算するために、誤りロケータおよびマグニチュード計算アーキテクチャが使用され得る。この誤りロケータおよびマグニチュードアーキテクチャは、σ（ｘ）の偶数係数および奇数係数をそれぞれ使用して構築されたσ_ｅｖｅｎ（ｘ）およびσ_ｏｄｄ（ｘ）を含み得る。標数２の有限体上で

であることが分かる。

例示的な実装では、並列度Ｊのチェン探索は、別々にσ（α^−ｉ）およびσ’（α^−ｉ）を評価することを回避するために別々にσ_ｅｖｅｎ（ｘ）およびσ_ｏｄｄ（ｘ）の計算のため使用され得る。例示的な実装では、並列度Ｊのチェン探索アーキテクチャは、対応する誤り値で同時に誤りマグニチュードを見つけるためにＺ（α^−ｉ）を評価するようにＺ（ｘ）に対しても使用され得る。並列度Ｊのチェン探索アーキテクチャを用いると、あらゆるクロックサイクル内に生成されたｊ個の誤りマグニチュードは、推定符号語を得るために対応する受信シンボルに加算され得る。誤りベクトル全体を計算するために、ｎ／ｊサイクルが必要とされることがある。

以下の表３は、ＲＳ復号器の各段に必要であるクロックサイクルを例として説明する。

分かる通り、誤り訂正能力の関数としての復号器のスループットは、以下の通り式１０を使用して計算され得る。

式中、ｎ、ｍ、ｔおよびｆ_ｍａｘは、符号長、シンボル幅、誤り訂正能力および最大動作周波数をそれぞれ表している。Ｊがｎ／ｊ＝ｔとなるように選択されると、スループットが最大化される。分かる通り、Ｊの選択は、スループットとハードウェア複雑度との間のトレードオフを判定する。同様に、設計されたリード・ソロモン復号器の合計レイテンシは、表３の通り各段に必要であるサイクルの和によって与えられる。

気付く通り、誤り評価計算および誤りマグニチュード計算が独立したパイプライン段として分割されるとき、スループットは、より一層改善される。

２段パイプライン型の低レイテンシ復号器
例示的な実装では、ＨＤＤ復号器のレイテンシは、ＳＣとＫＥＳの両方が図４に示された通り単一パイプライン段に統合された場合、スループットにあまり影響を与えることなく著しく低下され得る。図１１は、シンドローム計算１１０２およびＫＥＳ計算１１０４が本開示の好ましい実施形態に従って単一段に統合された例示的な２段の低レイテンシパイプライン型の復号器を例として説明する。ＳＣ１１０２およびＫＥＳ段１１０４の統合は、ＳＣ段１１０２がクロックサイクル毎に１個のシンドロームを出力し、ＫＥＳ段１１０４は、シンドロームのアレイから「一時レジスタ」の中へあらゆるクロックサイクルの間に入力として１個のシンドロームを必要とするので、実行できる。しかしながら、ＫＥＳ段１１０４は、図９に示された通り、「一時レジスタ」がＳ_２，Ｓ_１，０，．．０を用いて初期化される必要があるので、ＳＣ段と一緒に開始することができない。その結果、ＫＥＳ段は、付加的な２クロックサイクルを待機する必要がある。これに伴って、スループットは、ほとんど同一であり、遅延バッファのサイズも著しく縮小する。本実装では、図９に示されたシンドロームレジスタを回転させることは、必要とされないことがある。例示的な実装では、図８に示されたシンドロームレジスタは、クロックサイクル毎に１個のシンドロームを一時レジスタにロードするため使用され得る。この復号器のレイテンシは、
ＳＣとチェンおよび誤りマグニチュード計算段１１０６とのため必要であるクロックサイクルの合計によって式１２を使用して計算され得る。

所与の関心符号に対して、ＳＣとチェン探索および誤りマグニチュード計算とがほとんど２ｔ回のクロックサイクルを要するとき、復号器が並列性を利用可能にできない場合、提案された低レイテンシ２段パイプライン型のアーキテクチャは、シンドローム計算段とチェン探索および誤り計算段とが両方ともにほとんど同数のクロックサイクルを要するので、何ら問題なしに使用され得る。提案されたシンドローム計算段１１０２とキー方程式ソルバー段１１０４との組み合わせを用いると、復号器は、パイプラインストールを減らすためによく知られた３段パイプライン型のアーキテクチャにおいて必要とされる通りＫＥＳアーキテクチャを多数のＳＣならびにチェン探索および誤りマグニチュード計算ブロックと時間多重化する必要がない。例示的な実装では、並行して多数のＫＥＳが多数の受信ベクトルを操作し、より高いスループットを達成するために使用され得る。

分かる通り、ＬＣＣ復号器のスループットおよびレイテンシは、以前の復号器より優れている。要するに、多重割当ユニットは、η個の信頼できない位置および対応するｒ
_ｉ ^{［２ＨＤ］}個の値を得るためにｎ＝２５５サイクルを要する。例示的な実装では、状態機械は、ＥＮ_１，ＥＮ_２，．．． ，ＥＮ_ηを制御し、２^η個のテストベクトルの全てを得るために使用され得る。

例示的な実装では、２^η個のテストベクトルのうちの各テストベクトルは、提案された２段パイプライン型のＨＤＤを通過させることが可能であり、２段パイプライン型のＨＤＤにおける最も遅い段は、チェン探索および誤りマグニチュード計算ブロックであり、これは、Ｊ＝１０に対して、ｔ＋ｎ／Ｊ＝３６サイクルを要する。多重割当は、η＝３に対して、ＥＮ_３＝０；ＥＮ_２＝０；ＥＮ_１＝１であるときに開始される。これが実行可能であるのは、

であるからである。従って、長期的には、各受信ベクトルｒ^［ＨＤ］は、訂正されるためにｎ＝２５５サイクルを要する。その結果、軟ＬＣＣ復号器のスループットおよびレイテンシは、それぞれ式１３および式１４によって以下の通り与えられる。

以下の表４は、ブロック長ｎ＝４１０である２段パイプライン型のＨＤＤを使用するＲＳ復号器の要約を例として説明する。

本開示のＲＳ復号器を文字通り他の設計と比較するために、ＲＳ（２５５，２３９）復号器がＧＦ（２^８）上に設計された。

であるようなＪ＝３０を選択すると、スループット２４Ｇｂｐｓを生じる。面積とスループットとの間にトレードオフが存在する。Ｊ＝１０を選択することによって面積を節約できるが、Ｊの縮小に伴って、スループットが１２Ｇｂｐｓに低下する。以下の表５は、本開示に従って設計されたＪ＝１０であるＲＳ復号器とＫｉｎｔｅｘ−７ ＦＰＧＡ上のＲＳ（２５５，２３９）に対するザイリンクスＩＰのＲＳ復号器ｖ９．０との間の比較を示す。

分かる通り、提案ＲＳ復号器では、全ての必要とされるガロア体算術がＬＵＴおよびＦＦを使用して実装されるのでＢＲＡＭが使用されない。これに対して、ザイリンクスＩＰは、２つの１８ｋ ＢＲＡＭおよび１つの３６ｋ ＢＲＡＭという点で巨大なメモリを利用し、このことが本開示のＲＳ復号器と比べてＬＵＴおよびＦＦの利用を節約する。ＢＲＡＭ、ＬＵＴおよびＦＦを全体で考慮すると、本開示およびザイリンクスＩＰのＲＳ復号器は、ほとんど同じハードウェア資源を利用することが分かる。しかしながら、本開示のＲＳ復号器によってスループットの観点で達成される利得はほとんど５倍であり、これは、著しい改善である。Ｊ＝１０として誤り評価計算および誤りマグニチュード計算が独立したパイプライン段として分割される場合、スループットは、１６Ｇｂｐｓになるであろう。Ｋｉｎｔｅｘ−７ ＦＰＧＡ上に実装された設計は、図５に示される通りチップスコープを使用して検証される。

図１２は、チップセット上に設計されたＲＳ（２５５，２３９）復号器の結果を示す。

ある態様では、テクノロジー・スケールド・ノーマライズド・スループット（ＴＳＮＴ）指標が異なる製造技術を使った異なる設計性能を評価するために使用される。分かる通り、ＴＳＮＴは、以下の式１５を使用して計算され得る。

表６は、競合する復号器実装に関してＪ＝１０である提案ＲＳ復号器の比較を示す。提案１８０−ｎｍＲＳ（２５５，２３９）復号器のＴＳＮＴ値は、既存の設計より少なくとも１．８倍良好であり、このことは、提案復号器が所与のスループットに対してはるかに面積効率が良いことを表す。表６は、提案１８０−ｎｍ復号器のレイテンシが既存の１８０−ｎｍ設計と比べてほとんど８０％低下されていることをさらに例として示す。さらに、提案ＲＳ（２５５，２３９）復号器は、ＲＳ（２５５，２４５）デュアルラインアーキテクチャにおけるＥＣＣ能力が提案ＲＳ（２５５，２３９）復号器のＥＣＣ能力より低いにもかかわらず、ＲＳ（２５５，２４５）デュアルラインアーキテクチャよりレイテンシが５倍を超えて優れている。

以下の表７は、既存のＬＣＣ復号器と本開示のＬＣＣ復号器との間の比較を示す。本開示のＬＣＣ復号器は、２段パイプライン型のＨＤＤを使用して実装され、既存のＬＣＣ復号器より多くのハードウェア資源を消費する。しかしながら、本開示のＬＣＣ復号器は、より高いスループットおよびより低いレイテンシで動作する。ＨＤＤにおける誤り評価計算および誤りマグニチュード計算が独立したパイプライン段として分割される場合、本開示のＬＣＣ復号器は、

ではなく、

を満たすことができる。従って、本開示のＬＣＣ復号器は、低下した複雑度で同じスループットを達成する。

図１３は、ＨＤＤと、本開示の実施形態に従って設計されたη＝３およびη＝４に対するＬＣＣ復号器とのＦＥＲ性能を例として説明する。

例示的な実装では、ＧＦ（２^８）上に実装されたＲＳ（２５５，２３９）復号器は、ＶＨＤＬを使用してＫｉｎｔｅｘ−７ ＦＰＧＡ上に実装され得る。分かる通り、パイプライン型のＨＤ ＲＳ復号器のスループットは、同じハードウェア資源利用を行い、最大スループット２４Ｇｂｐｓで動作する既存の復号器と比べるとほとんど５倍である。ＳＤＤのスループットは、既存の設計と比べるとほとんど２倍である。本開示のＳＤＤおよびＨＤＤの全体的な処理レイテンシは、既存の設計と比べるとそれぞれほとんど５８％および８０％低下している。

本開示のＲＳ復号器は、補間および因数分解のないハイブリッド型低複雑度チェイスアルゴリズムを使用し、所望のフレーム誤り率（ＦＥＲ）を達成する。本開示のＲＳ復号器は、低下した複雑度で、ｍ＝４であるＫＶアルゴリズムの場合と同じフレーム誤り率（ＦＥＲ）性能を達成し得る。

図１４は、本開示の実施形態による提案ＲＳ復号器による復号化の方法を表す例示的なプロセスを例として説明する。例示的な態様では、本開示は、リード・ソロモン（ＲＳ）復号器のための復号方法１４００を提供し、この方法は、ステップ１４０２において、シンドローム計算（ＳＣ）モジュールによって、１つ以上の受信シンボルを処理することによりシンドロームＳ_ｊを計算するステップと、ステップ１４０４において、キー方程式ソルバー（ＫＥＳ）によって、計算されたシンドロームＳ_ｊから誤りロケータ多項式σ_ｉを計算するステップと、ステップ１４０６において、チェン探索および誤りマグニチュード計算モジュールによって、計算された誤り位置多項式σ_ｉから誤り位置Ｘ_ｉ、および、誤りマグニチュードＹ_ｉを計算するステップと、を含む。

例示的な態様では、誤りロケータ多項式σ_ｉは、バーレカンプ・マッシー・アルゴリズムを使用して、計算されたシンドロームＳ_ｊから計算され、誤りマグニチュードＹ_ｉは、Ｆｏｒｎｅｙの公式を使用して計算される。

例示的な態様では、この方法は、テストベクトル生成モジュールによって２^η個のテストベクトルを生成するステップをさらに含み、２^η個のテストベクトルのうちの各テストベクトルは、ＳＣモジュールに渡される。

上記は発明の様々な実施形態を説明するが、発明のその他およびさらなる実施形態は、発明の基本的な範囲から逸脱することなく考え出されることがある。発明の範囲は、続く特許請求の範囲によって決定される。発明は、記載された実施形態、バージョンまたは実施例に限定されることがなく、これらは、当業者が利用できる情報および知識と組み合わされたとき、当業者が発明を行えるように、および、使用できるようにするために含まれている。

発明の効果
本開示は、高速ストレージおよび通信システムのためのＲＳ復号器と方法とを提供する。

本開示は、チャネル特性および性能に依存して設定可能な誤り訂正能力を有効にすることができる設定可能なＲＳ復号器とその方法とを提供する。

本開示は、必要な面積がより小さく、かつ、高スループットおよび低レイテンシを達成する、高速ストレージおよび通信システムのためのＲＳ復号器を提供する。

本開示は、高スループットおよび低レイテンシを達成することができる、高速ストレージおよび通信用途のためのＲＳ復号器を提供する。

Claims (16)

1. テストベクトルを処理し、シンドロームを生成するように構成されているシンドローム計算（ＳＣ）モジュールであって、前記ＳＣモジュールのシンドローム計算段が２ｔ個のシンドロームを計算するために２ｔサイクルを要する、前記シンドローム計算（ＳＣ）モジュールと、
   誤りロケータ多項式を計算するように構成されているキー方程式ソルバー（ＫＥＳ）と、
   誤り位置および対応する誤りマグニチュードを見つけるように構成されているチェン探索および誤りマグニチュード計算（ＣＳＥＭＣ）モジュールと、
   を備え、前記ＳＣモジュール、前記ＫＥＳおよび前記ＣＳＥＭＣモジュールが２段パイプライン方式で配置されている、リード・ソロモン（ＲＳ）復号器。
2. 前記ＲＳ復号器は、軟判定復号器（ＳＤＤ）である、請求項１に記載の復号器。
3. 前記ＳＤＤは、補間および因数分解なしの低複雑度チェイス（ＬＣＣ）復号を使用するように構成されている、請求項２に記載の復号器。
4. 前記ＲＳ復号器は、２段硬判定復号器（ＨＤＤ）である、請求項１に記載の復号器。
5. 前記ＨＤＤは、誤りロケータ多項式を取得するために２ｔ回の反復を要するバーレカンプ・マッシー（ＢＭ）アルゴリズムに基づくｔシンボル訂正復号器である、請求項４に記載の復号器。
6. 前記ＲＳ復号器は、チャネル容量を監視し、前記監視されたチャネル容量に基づいて符号パラメータを調整するように構成されている、請求項１に記載の復号器。
7. 前記ＫＥＳは、バーレカンプ・マッシー（ＢＭ）アルゴリズムまたは修正ユークリッド（ＭＥ）アルゴリズムを使用して誤りロケータ多項式を計算する、請求項１に記載の復号器。
8. テストベクトル生成モジュールは、前記ＳＣモジュールへの入力として供給された２^η個のテストベクトルを生成する、請求項１に記載の復号器。
9. 遅延バッファが前記テストベクトルを一時記憶するように構成されている、請求項１に記載の復号器。
10. 前記ＳＣモジュールは、低レイテンシを達成し、遅延バッファのサイズを縮小するために前記ＫＥＳと統合される、請求項１に記載の復号器。
11. 前記誤りロケータ多項式は、前記ＲＳ復号器の高スループットを達成するために並列性なしで２ｔ回のクロックサイクル内で取得される、請求項１に記載の復号器。
12. 前記ＣＳＥＭＣモジュールは、並列度Ｊのチェン探索アーキテクチャを備える、請求項１に記載の復号器。
13. シンドローム計算（ＳＣ）モジュールによって、テストベクトルを処理することによりシンドロームＳ_ｊを計算するステップと、
    キー方程式ソルバー（ＫＥＳ）によって、前記計算されたシンドロームＳ_ｊから誤りロケータ多項式σ_ｉを計算するステップと、
    チェン探索および誤りマグニチュード計算（ＣＳＥＭＣ）モジュールによって、前記計算された誤り位置多項式σ_ｉから誤り位置Ｘ_ｉ、および、対応する誤りマグニチュードＹ_ｉを計算するステップと、
    を含む、リード・ソロモン（ＲＳ）復号器のための復号方法。
14. 前記誤りロケータ多項式σ_ｉは、バーレカンプ・マッシー・アルゴリズムを使用して、前記計算されたシンドロームＳ_ｊから計算される、請求項１３に記載の方法。
15. 前記誤りマグニチュードＹ_ｉは、Ｆｏｒｎｅｙの公式を使用して計算される、請求項１３に記載の方法。
16. 前記方法は、テストベクトル生成モジュールによって、２^η個のテストベクトルを生成するステップをさらに含み、２^η個のテストベクトルのうちの各テストベクトルは、前記ＳＣモジュールに渡される、請求項１３に記載の方法。

Images