(57)【要約】【課題】除算の代わりに列挙並列乗算を使用し、汎用乗算を定数乗算に置き換える短縮レイテンシ・シンボル誤り訂正復号器を使用する短縮レイテンシ誤り復号を実行するための、システム、方法およびコンピュータ可読媒体を開示する。【解決手段】除算の代わりに並列乗算を使用することで、短縮されたレイテンシを実現し、汎用乗算を定数乗算に置き換えることで、論理圧縮を可能にする。さらに、短縮シンボル誤り訂正復号器は、復号器論理のさらなる圧縮とさらなるレイテンシ改善とをもたらすことができる復号項共用を使用することができる。【選択図】図２
2020524930.tif 000002
【特許請求の範囲】
【請求項１】
１組の入力シンボルを含む受信コードワードの短縮レイテンシ誤り復号を実行するコンピュータ実装方法であって、
前記受信コードワードに付随する第１のシンドロームと第２のシンドロームと第３のシンドロームとを判断することと、
前記第１のシンドロームと前記第２のシンドロームと前記第３のシンドロームとのうちの少なくとも１つが非ゼロであると判断することと、
１組の定乗数を判断することと、
前記１組の定乗数における各定乗数によって前記第１のシンドロームの乗算を行って１組の積を生成することと、
前記１組の積に少なくとも部分的に基づいて、前記第２のシンドロームに関して第１の条件が満たされると判断することと、
前記第３のシンドロームに関して第２の条件が満たされると判断することと、
前記第１の条件と前記第２の条件とが満たされることに少なくとも部分的に基づいて、前記受信コードワードにおいて１つまたは複数のビット誤りを含む単一の入力シンボルを特定することと、
前記単一の入力シンボルにおける前記１つまたは複数のビット誤りを訂正して元のコードワードを得ることと
を含むコンピュータ実装方法。
【請求項２】
前記第２のシンドロームに関して前記第１の条件が満たされると判断することは、前記積の組における第１の積が前記第２のシンドロームと等しいと判断することを含み、前記第１の積は、前記定乗数の組のうちの特定の定乗数による前記第１のシンドロームの乗算を含む、請求項１に記載のコンピュータ実装方法。
【請求項３】
前記第３のシンドロームに関して前記第２の条件が満たされると判断することは、前記特定の定乗数と前記第２のシンドロームとの積が前記第３のシンドロームと等しいと判断することを含む、請求項２に記載のコンピュータ実装方法。
【請求項４】
前記特定の定乗数は第１の定乗数であり、前記第３のシンドロームに関して前記第２の条件が満たされると判断することは、前記積の組における第２の積が前記第３のシンドロームと等しいと判断することを含み、前記第２の積は前記定乗数の組にすでに含まれている第２の定乗数による前記第１のシンドロームの乗算を含む、請求項２に記載のコンピュータ実装方法。
【請求項５】
前記入力シンボルの組を係数として含む多項式を生成することをさらに含み、前記第１のシンドロームを判断することは値１における前記多項式の第１の値を計算することを含み、前記第２のシンドロームを判断することは、値αにおける前記多項式の第２の値を計算することを含み、前記第３のシンドロームを判断することは、値α２における前記多項式の第３の値を計算することを含み、前記特定の定乗数は、前記値αのｐ乗であり、前記ｐは前記受信コードワードにおける前記単一の入力シンボルの位置を示す、請求項１に記載のコンピュータ実装方法。
【請求項６】
前記単一の入力シンボルにおける前記１つまたは複数のビット誤りを訂正することは、前記単一の入力シンボルと前記第１のシンドロームとのＸＯＲをとることを含む、請求項１に記載のコンピュータ実装方法。
【請求項７】
前記定乗数の組を判断することは、候補位置のシーケンスを判断することを含み、前記シーケンスにおける各候補位置のそれぞれの２倍が前記シーケンスに含まれる、請求項１に記載のコンピュータ実装方法。
【請求項８】
１組の入力シンボルを含む受信コードワードの短縮レイテンシ誤り復号を実行するためのシステムであって、
コンピュータ実行可能命令を記憶する少なくとも１つのメモリと、
少なくとも１つのプロセッサとを含み、前記少なくとも１つのプロセッサは、前記少なくとも１つのメモリにアクセスし、前記コンピュータ実行可能命令を実行して、
前記受信コードワードに付随する第１のシンドロームと第２のシンドロームと第３のシンドロームとを判断し、
前記第１のシンドロームと前記第２のシンドロームと前記第３のシンドロームとのうちの少なくとも１つが非ゼロであると判断することと、
１組の定乗数を判断し、
前記１組の定乗数における各定乗数によって前記第１のシンドロームの乗算を行って１組の積を生成し、
前記１組の積に少なくとも部分的に基づいて、前記第２のシンドロームに関して第１の条件が満たされると判断し、
前記第３のシンドロームに関して第２の条件が満たされると判断し、
前記第１の条件と前記第２の条件とが満たされることに少なくとも部分的に基づいて、前記受信コードワードにおいて１つまたは複数のビット誤りを含む単一の入力シンボルを特定し、
前記単一の入力シンボルにおける前記１つまたは複数のビット誤りを訂正して元のコードワードを得る
ように構成された、システム。
【請求項９】
前記少なくとも１つのプロセッサは、前記コンピュータ実行可能命令を実行して前記積の組のうちの第１の積が前記第２のシンドロームと等しいと判断することによって、前記第２のシンドロームに関して前記第１の条件が満たされると判断するように構成され、前記第１の積は前記定乗数の組における特定の定乗数による前記第１のシンドロームの乗算を含む、請求項８に記載のシステム。
【請求項１０】
前記少なくとも１つのプロセッサは、前記コンピュータ実行可能命令を実行して前記特定の定乗数と前記第２のシンドロームとの積が前記第３のシンドロームと等しいと判断することによって前記第３のシンドロームに関して前記第２の条件が満たされると判断するように構成された、請求項９に記載のシステム。
【請求項１１】
前記特定の定乗数は第１の定乗数であり、前記少なくとも１つのプロセッサは、前記コンピュータ実行可能命令を実行して前記積の組における第２の積が前記第３のシンドロームと等しいと判断することによって前記第３のシンドロームに関して前記第２の条件が満たされると判断するように構成され、前記第２の積は前記定乗数の組にすでに含まれている第２の定乗数による前記第１のシンドロームの乗算を含む、請求項９に記載のシステム。
【請求項１２】
前記少なくとも１つのプロセッサは、前記コンピュータ実行可能命令を実行して前記入力シンボルの組を係数として含む多項式を生成するようにさらに構成され、前記第１のシンドロームを判断することは、値１における前記多項式の第１の値を計算することを含み、前記第２のシンドロームを判断することは、値αにおける前記多項式の第２の値を計算することを含み、前記第３のシンドロームを判断することは値α２における前記多項式の第３の値を計算することを含み、前記特定の定乗数は前記値αのｐ乗であり、ｐは前記受信コードワードにおける前記単一の入力シンボルの位置を示す、請求項８に記載のシステム。
【請求項１３】
前記少なくとも１つのプロセッサは、前記コンピュータ実行可能命令を実行して前記単一の入力シンボルと前記第１のシンドロームとのＸＯＲを実行することによって、前記単一の入力シンボルにおける前記１つまたは複数のビット誤りを訂正するように構成された、請求項８に記載のシステム。
【請求項１４】
前記少なくとも１つのプロセッサは、前記コンピュータ実行可能命令を実行して候補位置のシーケンスを判断することによって前記定乗数の組を判断するように構成され、前記シーケンスにおける各候補位置のそれぞれの２倍が前記シーケンスに含まれる、請求項８に記載のシステム。
【請求項１５】
１組の入力シンボルを含む受信コードワードについて短縮レイテンシ誤り復号を実行するためのコンピュータ・プログラム製品であって、前記コンピュータ・プログラム製品は処理回路によって読取り可能な記憶媒体を含み、前記記憶媒体は、方法が実行されるように前記処理回路によって実行可能な命令を記憶し、前記方法は、
前記受信コードワードに付随する第１のシンドロームと第２のシンドロームと第３のシンドロームとを判断することと、
前記第１のシンドロームと前記第２のシンドロームと前記第３のシンドロームとのうちの少なくとも１つが非ゼロであると判断することと、
１組の定乗数を判断することと、
前記１組の定乗数における各定乗数によって前記第１のシンドロームの乗算を行って１組の積を生成することと、
前記１組の積に少なくとも部分的に基づいて、前記第２のシンドロームに関して第１の条件が満たされると判断することと、
前記第３のシンドロームに関して第２の条件が満たされると判断することと、
前記第１の条件と前記第２の条件とが満たされることに少なくとも部分的に基づいて、前記受信コードワードにおいて１つまたは複数のビット誤りを含む単一の入力シンボルを特定することと、
前記単一の入力シンボルにおける前記１つまたは複数のビット誤りを訂正して元のコードワードを得ることと
を含むコンピュータ・プログラム製品。
【請求項１６】
前記第２のシンドロームに関して前記第１の条件が満たされると判断することは、前記積の組における第１の積が前記第２のシンドロームと等しいと判断することを含み、前記第１の積は、前記定乗数の組における特定の定乗数による前記第１のシンドロームの乗算を含む、請求項１５に記載のコンピュータ・プログラム製品。
【請求項１７】
前記第３のシンドロームに関して前記第２の条件が満たされると判断することは、前記特定の定乗数と前記第２のシンドロームとの積が前記第３のシンドロームと等しいと判断することを含む、請求項１６に記載のコンピュータ・プログラム製品。
【請求項１８】
前記特定の定乗数は第１の定乗数であり、前記第３のシンドロームに関して前記第２の条件が満たされると判断することは、前記積の組における第２の積が前記第３のシンドロームと等しいと判断することを含み、前記第２の積は前記定乗数の組にすでに含まれている第２の定乗数による前記第１のシンドロームの乗算を含む、請求項１６に記載のコンピュータ・プログラム製品。
【請求項１９】
前記方法が、前記入力シンボルの組を係数として含む多項式を生成することをさらに含み、前記第１のシンドロームを判断することは値１における前記多項式の第１の値を計算することを含み、前記第２のシンドロームを判断することは、値αにおける前記多項式の第２の値を計算することを含み、前記第３のシンドロームを判断することは、値α２における前記多項式の第３の値を計算することを含み、前記特定の定乗数は、前記値αのｐ乗であり、前記ｐは前記受信コードワードにおける前記単一の入力シンボルの位置を示す、請求項１５に記載のコンピュータ・プログラム製品。
【請求項２０】
前記単一の入力シンボルにおける前記１つまたは複数のビット誤りを訂正することは、前記単一の入力シンボルと前記第１のシンドロームとのＸＯＲをとることを含む、請求項１５に記載のコンピュータ・プログラム製品。
【請求項２１】
前記定乗数の組を判断することは、候補位置のシーケンスを判断することを含み、前記シーケンスにおける各候補位置のそれぞれの２倍が前記シーケンスに含まれる、請求項１５に記載のコンピュータ・プログラム製品。
【発明の詳細な説明】
【技術分野】
【０００１】
短縮レイテンシ誤り復号を実行するためのコンピュータ実装方法、システムおよびコンピュータ・プログラムに関する。
【背景技術】
【０００２】
信頼性がないかまたは雑音の多い通信チャネルでのデータ送信における誤りを制御するようにメッセージを冗長方式で符号化するために、誤り訂正符号（ＥＣＣ）が使用される。コンピュータ・システムがますます高密度化し、複雑になるにつれて、コストと、パフォーマンスと、密度と、信頼性・可用性・保守容易性（ｒｅｌｉａｂｉｌｉｔｙ，  ａｖａｉｌａｂｉｌｉｔｙ  ａｎｄ  ｓｅｒｖｉｃｅａｂｉｌｉｔｙ：ＲＡＳ）との間でトレードオフが行われることが多い。使用される誤り訂正符号の種類は、行われるトレードオフの種類に影響を与えることがある。例えば、大規模なキャッシュ設計の場合、高密度化は、誤り訂正に伴う高レイテンシという犠牲を払って実現されることがある。
【発明の概要】
【発明が解決しようとする課題】
【０００３】
除算の代わりに列挙並列乗算を使用し、汎用乗算を定数乗算に置き換える短縮レイテンシ・シンボル誤り訂正復号器を使用する短縮レイテンシ誤り復号を実行するためのシステム、方法およびコンピュータ可読媒体を提供する。
【課題を解決するための手段】
【０００４】
本開示の１つまたは複数の例示の実施形態では、１組の入力シンボルを含む受信コードワードの短縮レイテンシ誤り復号を行うコンピュータ実装方法が開示される。この方法は、受信コードワードに付随する第１のシンドロームと第２のシンドロームと第３のシンドロームとを判断することと、第１のシンドローム、第２のシンドロームまたは第３のシンドロームのうちの少なくとも１つが非ゼロであると判断することとを含む。この方法は、１組の定乗数（constant multiplier）を判断することと、前記１組の定乗数のうちの各定乗数による第１のシンドロームの乗算を行って１組の積を生成することとをさらに含む。この方法は、前記１組の積に少なくとも部分的に基づいて、第２のシンドロームに関して第１の条件が満たされると判断することと、第３のシンドロームに関して第２の条件が満たされると判断することとをさらに含む。次に、第１の条件と第２の条件とが満たされることに少なくとも部分的に基づいて、１つまたは複数のビット誤りを含む受信コードワード中の単一の入力シンボルが特定され、単一の入力シンボル中の１つまたは複数のビット誤りが訂正されて元のコードワードが得られる。
【０００５】
本開示の１つまたは複数の例示の実施形態では、１組の入力シンボルを含む受信コードワードの短縮レイテンシ誤り復号を行うためのシステムが開示される。このシスステムは、コンピュータ実行可能命令を記憶する少なくとも１つのメモリと、少なくとも１つのメモリにアクセスし、コンピュータ実行可能命令を実行して１組の動作を行うように構成された少なくとも１つのプロセッサとを含む。動作は、受信コードワードに付随する第１のシンドロームと第２のシンドロームと第３のシンドロームとを判断することと、第１のシンドローム、第２のシンドローム、または第３のシンドロームとのうちの少なくとも１つが非ゼロであると判断することとを含む。動作は、１組の定乗数を判断することと、１組の定乗数のうちの各定乗数によって第１のシンドロームの乗算を行って１組の積を生成することとをさらに含む。動作は、１組の積に少なくとも部分的に基づいて、第２のシンドロームに関して第１の条件が満たされると判断することと、第３のシンドロームに関して第２の条件が満たされると判断することとをさらに含む。次に、第１の条件と第２の条件とが満たされることに少なくとも部分的に基づいて、１つまたは複数のビット誤りを含む受信コードワード中の単一の入力シンボルが特定され、単一の入力シンボル中の１つまたは複数のビット誤りが訂正されて元のコードワードが得られる。
【０００６】
本開示の１つまたは複数の例示の実施形態では、１組の入力シンボルを含む受信コードワードの短縮レイテンシ誤り復号を行うためのコンピュータ・プログラム製品が開示される。このコンピュータ・プログラム製品は、処理回路によって読取り可能な記憶媒体を含む。記憶媒体は、方法が実行されるようにするために処理回路によって実行可能な命令を記憶する。この方法は、受信コードワードに付随する第１のシンドロームと第２のシンドロームと第３のシンドロームとを判断することと、第１のシンドローム、第２のシンドロームまたは第３のシンドロームのうちの少なくとも１つが非ゼロであると判断することとを含む。この方法は、１組の定乗数を判断することと、１組の定乗数のうちの各定乗数による第１のシンドロームの乗算を行って１組の積を生成することとをさらに含む。この方法は、前記１組の積に少なくとも部分的に基づいて、第２のシンドロームに関して第１の条件が満たされると判断することと、第３のシンドロームに関して第２の条件が満たされると判断することとをさらに含む。次に、第１の条件と第２の条件とが満たされることに少なくとも部分的に基づいて、１つまたは複数のビット誤りを含む受信コードワード中の単一の入力シンボルが特定され、単一の入力シンボル中の１つまたは複数のビット誤りが訂正されて元のコードワードが得られる。
【０００７】
添付図面を参照しながら詳細な説明を記載する。図面は、例示のみを目的として示され、本開示の例示の実施形態を図示するに過ぎない。図面は、本開示を理解しやすくするために示すものであり、本開示の広さ、範囲または適用可能性を限定するものとみなされるべきではない。同じ参照番号の使用は、類似しているが必ずしも同じまたは完全に同一ではない構成要素を示す。ただし、類似の構成要素を識別するために異なる参照番号が使用されることもある。様々な実施形態が、図面に示されているものとは異なる要素または構成要素を使用してもよく、一部の要素または構成要素あるいはその両方が様々な実施形態に存在しなくてもよい。構成要素または要素について説明するための単数の用語の使用は、文脈によっては、複数のそのような構成要素または要素を包含する場合があり、その逆の場合もあり得る。
【図面の簡単な説明】
【０００８】
【図１】従来のリード・ソロモン復号プロセスを示す概略ブロック図である。
【図２】本開示の１つまたは複数の例示の実施形態による短縮レイテンシ誤り復号プロセスを示す概略ブロック図である。
【図３】本開示の１つまたは複数の例示の実施形態による短縮レイテンシ誤り復号プロセスを実装するための論理を示す概略図である。
【図４】本開示の１つまたは複数の例示の実施形態による復号項共用を実装するために図３の論理をどのように使用することができるかを示す別の概略図である。
【図５】本開示の１つまたは複数の例示の実施形態による短縮レイテンシ誤り復号プロセスを実装するように構成された構成要素を示す概略ブロック図である。
【図６】本開示の１つまたは複数の例示の実施形態による例示のＬ４キャッシュ機構を示す概略ブロック図である。
【図７】本開示の１つまたは複数の例示の実施形態による例示のＬ３キャッシュ機構を示す概略ブロック図である。
【図８】本開示の１つまたは複数の例示の実施形態による例示の短縮レイテンシ誤り復号プロセスを示すプロセス流れ図である。
【図９】本開示の１つまたは複数の例示の実施形態を実装するように構成された例示のネットワーク化アーキテクチャを示す概略図である。
【発明を実施するための形態】
【０００９】
本開示の例示の実施形態は、特に、改良型短縮レイテンシ・シンボル誤り訂正復号器を使用してシンボル誤り復号および訂正を行うための、システム、方法、コンピュータ可読媒体、技術および方法論などを含む。特定の例示の実施形態では、短縮レイテンシ・シンボル誤り訂正復号器は、除算の代わりに列挙並列乗算を使用し、汎用乗算を定数乗算に置き換える改良型リード・ソロモン（ＲＳ）復号器とすることができる。除算の代わりに並列乗算を使用することによって、特に、少ない数のシンボルの場合の短縮レイテンシを実現することができる。また、汎用乗算を定数乗算に置き換えることで、論理圧縮および短縮レイテンシが可能になる。さらに、特定の例示の実施形態では、短縮シンボル誤り訂正復号器は、復号器論理の大幅なさらなる圧縮とレイテンシのさらなる改善とをもたらすことができる、復号項共用を使用することができる。
【００１０】
ＲＳ符号は、非２進巡回誤り訂正符号のクラスに属する誤り訂正符号のグループである。ＲＳ符号は、有限体上の単変量多項式に基づく。ＲＳ符号のクラスは、例えば、１つまたは複数のビット誤りを有する単一のシンボルの検出と訂正を行うことができ、それぞれが１つまたは複数のビット誤りを有する２つのシンボルを検出することができるが訂正することはできない、単一誤り訂正（ＳＥＣ）／二重誤り検出（ＤＥＤ）符号を含み得る。ｎビット・シンボルを使用するＲＳ符号を、２ｎ−１シンボルの最大符号長を有するガロア体（ＧＦ）（２ｎ）上で定義することができる。例えば、５１２−１＝５１１シンボルの最大符号長を有するＧＦ（２９）上で９ビットのシンボルを使用するＲＳ符号を定義することができる。各有限体は、べき乗がすべての非ゼロの体の元を表す原始元αを有する。具体的には、ＳＥＣ／ＤＥＣ  ＲＳ符号中の各コードワードＣは、多項式Ｃ（ｘ）とみなした場合、Ｃ（１）＝０、Ｃ（α）＝０、Ｃ（α２）＝０を満たす。
【００１１】
より詳細には、コードワードＣの各シンボルは、多項式Ｃ（ｘ）の係数とみなすことができる。例えば、本開示の例示の実施形態では、コードワードＣが１５個のデータ・シンボルと３個のチェック／パリティ・シンボルとを含むことができる。この場合、多項式Ｃ（ｘ）は、Ｃ（ｘ）＝［シンボル１］＋［シンボル２］ｘ＋［シンボル３］ｘ２＋．．．＋［シンボル１８］ｘ１７のように与えられることになる。ＲＳ符号の１つの特性は、コードワードＣに誤りが存在しないと仮定して、多項式Ｃ（ｘ）についてそれぞれがゼロ値となる値１、αおよびα２が存在することである。値１、α、およびα２における多項式Ｃ（ｘ）の値をシンドロームと呼ぶことがあり、Ｓ０＝Ｃ（１）、Ｓ１＝Ｃ（α）、Ｓ２＝Ｃ（α２）のように与えられる。シンドロームは、コードワードＣのシンボルと同じビット長を有することができる。
【００１２】
Ｓ０＝Ｓ１＝Ｓ２＝０の場合、コードワードＣには誤りが存在しないとみなされる。しかし、コードワードＣに１つまたは複数のシンボル誤りが紛れ込んでいた場合、値１、αまたはα２のうちの１つまたは複数が、多項式Ｃ（ｘ）についてゼロ値とならなくなることがある。すなわち、Ｒが元のコードワードＣと送信中にＣに紛れ込んだ誤りとの和である場合、それぞれＲ（１）、Ｒ（α）およびＲ（α２）によって与えられるシンドロームＳ１、Ｓ２またはＳ３のうちの１つまたは複数が非ゼロとなることがある。非限定的な例として、Ｓ０＝［００００１０１００］、Ｓ１＝［１０１０１１１１０］、およびＳ２＝［１０１０１１０１１］であるとする。大きさβを有する受信コードワードＲ内の位置ｐに１つのシンボル誤りがある場合、Ｓ０＝β、Ｓ１＝βαｐ、Ｓ２＝βα２ｐとなる。したがって、単一シンボル誤りの場合、Ｓ０は誤りのある単一シンボル内のどのビットが誤りであるかを示す。例えば、この例では、Ｓ０は、誤りのあるシンボル内のビット４および６が誤りであることを示す。Ｓ０は、コードワードＣにおける元のデータを得るために誤りのあるシンボル中のどのビットをフリップする必要があるかを示すため、ビット・フリップ・ベクトルと呼ぶことがある。
【００１３】
Ｓ０は誤りのある単一シンボル中でどのビットをフリップする必要があるかを示し、Ｓ１とＳ２は受信コードワードＲ中の当該シンボルの位置ｐを判断するために使用することができる。前述のように、シンドロームＳ１はビット・フリップ・ベクトルＳ０と値αのｐ乗との積であり、ここでｐは誤りのある単一シンボルの位置を示す。従来のＲＳ符号は、まず、Ｓ０とＳ２との積がＳ１２に等しいか否かを判断するための検査を行うことによって作用する。Ｓ１２に等しい場合、単一シンボルに誤りがあると判断することができる。従来のＲＳ符号は、次に、Ｓ１をＳ０で割ってαｐを得て、次にこれをαのべき乗（例えば、α０、α１、．．．α（シンボル数−１））のそれぞれと比較して、αのどのべき乗が一致するかを判断し、そのべき乗が誤りのある単一シンボルの位置ｐを示す。従来のＲＳ符号は、まず逆元のテーブルの参照を行ってＳ０の逆元（Ｓ０−１）を判断し、次にＳ１に逆元Ｓ０−１を乗じることによって、Ｓ１割るＳ０の除算を実施することができる。
【００１４】
それに対し、本開示の例示の実施形態による改良型ＲＳ符号は、除算の代わりに列挙並列乗算を行う。また、列挙並列乗算は、従来のＲＳ符号に付随する汎用乗算（例えばＳ０Ｓ２＝Ｓ１２であるか否かの検査）の代わりに定数（例えばαのべき乗）による乗算を含む。したがって、本開示の例示の実施形態による改良型ＲＳ符号は、汎用乗算の代わりに定数乗算を使用することによって、従来のＲＳ符号と比較してレイテンシの短縮を実現する。また、本開示の例示の実施形態による改良型ＲＳ符号は、除算の代わりに列挙並列乗算を行うことにより従来のＲＳ符号と比較してレイテンシのさらなる短縮を実現する。
【００１５】
より具体的には、Ｓ１をＳ０で割るのではなく、本開示の例示の実施形態による改良型ＲＳ符号は、αの各べき乗（例えば、α０、α１、．．．α（シンボル数−１））によるＳ０の乗算を行って、結果の積のうちのいずれかがＳ１と一致するかを判断する。さらに、本開示の例示の実施形態による改良型ＲＳ符号は、αの各べき乗（例えば、α０、α１、．．．α（シンボル数−１））によるＳ１の乗算を行って、結果の積のいずれかがＳ２と一致するかも判断する。特定の例示の実施形態では、これらの検査の両方を並列して行うことができる。これらの条件の両方がαの同じべき乗（ｐ）によって満たされる場合、単一の訂正可能なシンボル誤りが存在すると判断することができる。この定数による列挙並列乗算は、従来のＲＳ符号によって行われる汎用乗算および除算に優るレイテンシ短縮を実現する。
【００１６】
上述の列挙並列乗算を行った後、一致するものがない場合、コードワードＣに複数の誤りがあると判断することができる。一致するものが１つある場合、すなわち、所与のｐについてＳ０とαｐとの積がＳ１と一致し（Ｓ０＊αｐ＝Ｓ１）、同じｐについてＳ１とαｐとの積がＳ２と一致する（Ｓ１＊αｐ＝Ｓ２）場合、単一のシンボル誤りがあると判断することができ、一致する積のうちのαのべき乗が、誤りのあるその単一のシンボルの位置を示す。単一の誤りが検出された場合、位置ｐにある受信コードワードＲにおけるシンボルについてＳ０＝βを加え（ＸＯＲをとって）そのシンボルの誤りを訂正し、元のコードワードＣを得ることができる。上記で示した例では、ビット・フリップ・ベクトルＳ０と位置ｐのシンボルとのＸＯＲがとられることになる。一方、これらの条件の両方が満たされない場合、すなわち、Ｓ０＊αｐ＝Ｓ１およびＳ１＊αｐ＝Ｓ２となるｐの値がない場合、受信コードワードＲには複数のシンボル誤りがあり、それらの複数のシンボル誤りを訂正することができない。
【００１７】
図１は、従来のＲＳ復号プロセスを示す概略ブロック図である。図１は逆元Ｓ０−１を得るための復号および参照プロセスとその後の汎用乗算および比較演算を示しているが、従来のＲＳ復号は、逆元による乗算よりもさらに大きいレイテンシを伴う除算（例えばＳ１／Ｓ０）を使用する場合もあることに留意されたい。しかし、除算を実装するために逆元による乗算を使用する図１に示す従来のプロセスであっても、本開示の例示の実施形態によるシンボル誤り訂正復号プロセスよりも大幅に大きいレイテンシを伴う。
【００１８】
例えば、逆（ＩＮＶ）演算、ＡＮＤ／ＯＲ演算、およびＸＯＲ演算に、ＩＮＶ＝０、ＡＮＤ／ＯＲ＝１、ＸＯＲ＝２のようにレイテンシ値を割り当てるとする。これらのレイテンシ値に基づくと、図１に示す従来のＲＳ復号プロセスの結果として２６のレイテンシ・レベルとなる。具体的には、図１のプロセスは、復号器（ＤＣＤ）１０２が、ＩＮＶ演算と３レベルのＡＮＤ演算とに相当する９ウェイＡＮＤを行う復号ステップを含む。この結果、レイテンシ値３となる。次に、２５６ウェイＯＲ（８レベルのＯＲ演算）を含む定数参照１０４を行ってＳ０−１を求める。この結果としてレイテンシ値８となる。これに続いて、ＩＮＶ演算と、ＡＮＤ演算と５レベルのＸＯＲ演算とを含む汎用乗算１０６を行って、レイテンシ値０＋１＋２（５）＝１１となる。最後に、ＡＮＤと８ウェイＯＲ演算とを含む比較演算１０８が行われる。これは、ＡＮＤと３レベルのＯＲ演算に相当し、その結果としてレイテンシ値１＋３＝４となる。したがって、図１に示すプロセスは、総レイテンシが３＋８＋１１＋４＝２６となる。なお、図１は、Ｓ０とＳ２との積がＳ１２に等しいか否かを判断するために従来のＲＳ復号で行われる汎用乗算ステップを示していないことに留意されたい。しかし、従来のＲＳ復号器は一般に、このステップを逆元Ｓ０−１を求めるステップ（または、場合によってはＳ０をＳ１で割る除算を行うステップ）と並列して実行する。逆元Ｓ０−１を求める（またはＳ０割るＳ１の除算を行う）レイテンシは、汎用乗算ステップのレイテンシよりも長いため、限定ステップであり、汎用乗算は総レイテンシを増加させない。
【００１９】
図２は、本開示の１つまたは複数の例示の実施形態による短縮レイテンシ誤り復号プロセスを示す概略ブロック図である。図５は、本開示の１つまたは複数の例示の実施形態による短縮レイテンシ誤り復号プロセスを実装するように構成された構成要素を示す概略ブロック図である。図８は、本開示の１つまたは複数の例示の実施形態による、例示の短縮レイテンシ誤り復号方法７００を示すプロセス流れ図である。以下、図２、図５および図８について互いに関連づけて説明する。
【００２０】
本開示の例示の実施形態による短縮レイテンシ誤り復号プロセスは、誤り訂正符号が短いことと、レイテンシを最小限にすることが望ましいこととを前提とすることができる。具体的には、本開示の例示の実施形態による短縮レイテンシ誤り復号プロセスは、単一シンボル訂正／二重シンボル検出（ＳＳＣ／ＤＳＤ）により、キャッシュ設計のＥＣＣ保護を提供する。また、前述のように、本開示の例示の実施形態による短縮レイテンシ誤り復号プロセスは、除算を列挙並列乗算に置き換え、さらに、汎用乗算を定数乗算に置き換える。こうすることにより、従来の復号プロセスに優る論理圧縮と短縮レイテンシが実現される。
【００２１】
まず、方法７００のブロック７０２を参照すると、本開示の例示の実施形態による短縮レイテンシ誤り復号プロセスは、少なくとも１つのデータ・シンボルと少なくとも１つのチェック・シンボルとを含むコードワードＲの受信から開始することができる。コードワードＲは、例えば、ＧＦ（５１２）上で定義された９ビットのシンボルを含むことができる。非限定的な例として、受信コードワードＲは１５個のデータ・シンボルと３個のチェック・シンボルを含んでもよい。
【００２２】
方法７００のブロック７０４で、受信コードワードＲのシンボルを係数として有する多項式Ｒ（ｘ）を生成することができる。例えば、Ｒが１５個のデータ・シンボルと３個のチェック・シンボル（したがって合計１８個のシンボル）を有する上記の例では、多項式Ｒ（ｘ）＝［シンボル１］＋［シンボル２］ｘ＋［シンボル３］ｘ２＋．．．＋［シンボル１８］ｘ１７となる。次に、方法７００のブロック７０６で、シンドローム生成器４０２（図５）のコンピュータ実行可能命令を実行して、多項式Ｒ（ｘ）についてシンドロームＳ０、Ｓ１およびＳ２を計算することができる。前述のように、シンドロームＳ０、Ｓ１およびＳ２は、それぞれ点１、αおよびα２における多項式Ｒ（ｘ）の値を表す。
【００２３】
より詳細には、再び前述の例を参照すると、原始多項式α９＋α４＋１の乗根によってＧＦ（２）上でＧＦ（５１２）符号を生成することができる。この符号の符号生成多項式は、Ｇ（ｘ）＝（ｘ−１）（ｘ−α）（ｘ−α２）とすることができる。１５個のデータ・シンボルを多項式Ｄ（ｘ）の係数とみなすと、３個のチェック・シンボルはｘ３Ｄ（ｘ）をＧ（ｘ）で割った後の剰余の係数である。これは、符号器ＸＯＲ回路が１３５ビットのデータに対して演算を行って２７チェック・ビットを生成するように、１５個のデータ・シンボル（９＊１５＝１３５ビット）を入力とし、３個のチェック・シンボル（９＊３＝２７ビット）を生成するＸＯＲ回路によって並列して実行することができる。また、前述のように、この例における１８個のシンボルを多項式Ｒ（ｘ）の係数とみなすと、シンドロームＳ０、Ｓ１およびＳ２は、それぞれ、点１、αおよびα２における多項式Ｒ（ｘ）の値を求めることによって計算される。これは、１８個の受信シンボルを受け取り３個のシンドロームを生成するＸＯＲ回路によって並列して行うことができる。
【００２４】
具体的には、図５に示すシンドローム生成回路４０２が、１８＊９＝１６２ビットを入力として取り、２７ビットを出力として生成することができる。具体的には、９ビットの偶数シンボル符号を仮定すると、シンドローム生成回路４０２によって出力される２７ビットは、それぞれが９ビット長の部分Ｓ０、Ｓ１およびＳ２を含むことができる。Ｓ０は、訂正可能なシンボル中のどのビットをフリップする必要があるかを示す誤りの９ビット・ベクトルとすることができる。Ｓ１は、誤りのあるシンボルを指す９ビット・ベクトルとすることができる。より詳細には、前述の例では、Ｓ１は、１５＋３＝１８個のシンボルのうちのシンボルに誤りがある特別な符号化とすることができる。Ｓ２は、訂正可能誤り（ＣＥ）／訂正不能誤り（ＵＥ）検査として使用される９ビット・ベクトルとすることができる。例えば、Ｓ１＝Ｓ０αｐおよびＳ２＝Ｓ１αｐであるような位置ｐが存在する場合、誤りは訂正可能である。
【００２５】
特定の例示の実施形態では、訂正シンボル中の９ビットのうちのいずれを訂正する必要があるかを示すビット・フリップ・ベクトルのためにＳ０項を生成することができる。次に、Ｓ０をすべてのシンボルに対して使用して、すべてのシンボルを前訂正することができる（各シンボルが暫定的訂正を有し得る）。以下で詳述するように、次にＳ０、Ｓ１およびＳ２の２次検査といくつかの定数を使用して、シンボルのうちのどのシンボルが訂正の必要があるか（もしある場合）を判断することができる。
【００２６】
具体的には、方法７００のブロック７０８で、復号器４０４（図５）が、シンドロームＳ０、Ｓ１、またはＳ２のいずれかが非ゼロであるか否かを判断することができる。すべてのシンドロームがゼロであることを示すブロック７０８での否定判断に応答して、受信コードワードＲは誤りを含まないと判断することができるため、方法７００は終了することができる。一方、シンドロームＳ０、Ｓ１およびＳ２のうちの１つまたは複数のシンドロームが非ゼロであることを示すブロック７０８での肯定判断に応答して、方法７００はブロック７１０に進むことができ、復号回路４０４は、Ｓ０と、０から［（コードワードＲ中のシンボル数）−１］までの範囲のαの各べき乗との列挙並列乗算を実行することができる。
【００２７】
方法７００のブロック７１２で、復号回路４０４は、ブロック７１０で実行された列挙並列乗算の結果の積をＳ１と比較して、Ｓ１＝Ｓ０αｐであるべき乗ｐが存在するか否かを判断することができる。ブロック７１２での否定判断に応答して、方法７００はブロック７２２に進むことができ、受信コードワードＲ中に複数の訂正不能シンボル誤りが存在すると判断することができる。一方、ブロック７１２での肯定判断に応答して、方法７００はブロック７１４に進むことができ、復号回路４０４は、Ｓ１と、０から［（コードワードＲ中のシンボル数）−１］までの範囲のαの各べき乗との列挙並列乗算を実行することができる。
【００２８】
方法７００のブロック７１６で、復号回路４０４は、ブロック７１４で実行された列挙並列乗算の結果の積をＳ２と比較して、Ｓ１＝Ｓ０αｐである同じべき乗ｐについてＳ２＝Ｓ１αｐであるか否かを判断することができる。ブロック７１６での否定判断に応答して、方法７００はブロック７２２に進むことができ、受信コードワードＲ中に複数の訂正不能シンボル誤りがあると判断することができる。一方、ブロック７１６での肯定判断に応答して、復号回路４０４は、ブロック７１８で、ブロック７１２とブロック７１６の両方の条件が満たされることに基づいて、コードワードＲ中の位置ｐに１つまたは複数のビット誤りを有する単一シンボルがあると判断することができる。次に、方法７００のブロック７２０で、受信コードワードＲ中の位置ｐにおける単一シンボルのビット誤りが、Ｓ０と位置ｐにおけるシンボルとのＸＯＲをとることによって訂正される。
【００２９】
本開示の特定の例示の実施形態では、ブロック７１０で実行されるαのべき乗とＳ０との列挙並列乗算およびブロック７１４で実行されるαのべき乗とＳ１との列挙並列乗算と、ブロック７１２および７１６での検査とは、少なくとも部分的に並列して実行することができる。例えば、コードワードＲが合計１８個のシンボル（１５個のデータ・シンボルと３個のチェック・シンボル）を含む前述の例では、候補誤り位置の範囲［０，１７］にわたる候補誤り位置ｐごとに、Ｓ１＝Ｓ０αｐであるか否かの検査と、Ｓ２＝Ｓ１αｐであるか否かの検査とを並列して実行することができる。これらの検査の両方に合格する位置ｐが特定された場合、ブロック７１８での判断を行うことができ、位置ｐにおけるコードワードＲ中のシンボルのデータとＳ０とのＸＯＲをとってその単一シンボル誤りを訂正することができる。
【００３０】
具体的には、誤りのあるシンボルが１つのみの場合、シンドロームＳ０は誤り値である（例えば、Ｓ０中の非ゼロのビットは、シンボルを訂正するために誤りのあるシンボルにおいてフリップする必要があるビットを示す）。図８の短縮レイテンシ誤り復号プロセスは、受信コードワードＲ中の誤りのある単一シンボルの場所を検出しようとするか、または複数のシンボル誤りが発生したと判断しようとするものである。コードワードＲ中の位置ｐに単一シンボル誤りがある場合、シンドロームは式Ｓ１＝Ｓ０ＹおよびＳ２＝Ｓ１Ｙを満たし、ここで、候補ｐ値の範囲（例えば前述の例では０から１７）にわたる特定のｐについてＹ＝αｐである。従来のＲＳ符号のようにＳ１をＳ０で割ってＹを計算する（これにより前述のように大きなレイテンシが発生する）のではなく、１７対の定乗数を使用して、０から１７までにＳ１＝Ｓ０αｐおよびＳ２＝Ｓ１αｐである位置ｐがあるか否かを判断する検査を並列して実行することができる。なお、この例ではコードワードＲ中に１８個のシンボルがあるが、ｐが０の場合、αｐ＝１であり、したがって定数乗算を必要とせずにＳ１をＳ０と直接比較することができ、Ｓ２をＳ１と直接比較することができるため、１７対の定乗数だけで済むことに留意されたい。したがって、（以下で詳述する）復号項共用を行わないこの手法を使用する場合、必要な定乗数は３４個とすることができる。両方の式を満たす位置ｐが特定された場合、ｐは受信コードワードＲ中の誤りのあるシンボルの場所を示す。一方、そのような位置ｐが両方の式を満たさない場合、複数のシンボル誤りが発生している。各定乗数は、９ビットを入力として９ビットの出力を生成するＸＯＲ回路とすることができる。
【００３１】
より詳細には、方法７００のブロック７０６で９ビットのＳ０項が生成された後、図２に示すようにＳ０を９×９の定数行列によって乗算２０２して、例えば、９ビットのＳ０×Ａｐを得ることができる。次に、Ｓ０×ＡｐをＳ１と比較２０４することができる。さらに、図２には示されていないが、Ｓ１×ＡｐとＳ２とのさらなる比較も行うことができる。このようにして、どのシンボルが（ある場合）訂正を必要としているかを判断することができる。具体的には、定数行列Ａｐは、定数乗算においてＳ０とＳ１の両方に適用することができる。長さ１８＊９の２つの２つの積ベクトルを生成することができる。次に、これらのベクトルを、前述の例のコードワードＲ中の１８個のシンボルに対応する１８個の連続した９ビット・シンボルに分割することができる。Ｓ０×Ａｐの積をＳ１と比較し、Ｓ１×Ａｐの積をＳ２と比較することができる。両方の比較が積シンボルの所与の対について一致する場合、値がＳ０である誤りの位置を特定することができる。積が一致する位置がない場合は、受信コードワードＲ中に複数の訂正不能シンボル誤りが存在する。
【００３２】
前述のように、上述の二重条件を検査するには３４個の定乗数が必要となり得る。しかし、復号項共用を使用する本開示の例示の実施形態では、必要な定乗数の数を減らすことができる。具体的には、位置０（αのゼロ乗に対応する）は１倍であり、したがって使用されない。位置１から８については、Ｓ２をＳ１αｐと比較する代わりに、それと同等にＳ２をＳ０α２ｐと比較することができる。しかし、ｐが１から１７までの範囲である場合、１から８までの範囲のｐの場合の位置２ｐは単に偶数位置に過ぎないため、それらの積はすでにＳ１に関する比較のために計算済みである。したがって、１７個の定乗数（位置１から１７）をＳ１との比較のために使用することができるが、９から１７の範囲のｐについてＳ１αｐを計算するのに必要な定乗数は９個のみであり、誤りのあるシンボルの位置を特定するための定乗数は合計１７＋９＝２６個となる。この復号項共用手法は、本開示の例示の実施形態によるいずれの短縮レイテンシＲＳ符号にも使用することができ、各９×９定数行列にほぼ同数あると仮定すれば、復号器論理のサイズを従来の復号プロセスより約２５％圧縮することができる。
【００３３】
上記をより形式的に述べると、長さｋの符号の場合、復号項共用がないと、０＜ｐ＜ｋのときのＳ０αｐおよびＳ１αｐの計算には２ｋ−２個の定乗数が必要となる。しかし、本開示の例示の実施形態による復号項共用を使用した場合、０＜ｐ＜ｋのときにＳ１＝Ｓ０αｐであるか否かに関する検査は行ってもよいが、０＜ｐ＜ｋのときにＳ２＝Ｓ１αｐであるか否かの検査を行う代わりに０＜ｐ＜ｋのときにＳ２＝Ｓ０α２ｐであるかの検査を行うことができる。２ｐ＜ｋの場合、Ｓ０α２ｐの値は、０＜ｐ＜ｋのときにＳ１＝Ｓ０αｐであるか否かの検査のためにすでに計算済みである。したがって、０＜ｐ＜ｋのときのＳ０αｐは計算するが、Ｓ０α２ｐはｋ≦２ｐ＜２ｋについてのみ計算すればよい。これに必要な定乗数はｋ−１＋（ｋ／２）個であり、従来の復号プロセスと比較して約２５％の必要ハードウェア復号器論理の削減に相当する。コードワードＲが合計１８個のシンボルを有する前述の例では、必要な定乗数は２（１８）−２＝３４個ではなく１８−１＋（１８／２）＝２６となる。
【００３４】
図３は、本開示の１つまたは複数の例示の実施形態による短縮レイテンシ誤り復号プロセスを実装するための例示の復号器論理３００を示す概略図である。図４は、本開示の１つまたは複数の例示の実施形態による復号項共用により、図３の論理３００が定数項をどのように再使用することができるかを示す別の概略図である。図４からわかるように、Ｓ０が使用されない場合、計算されるＳ２、Ｓ４、．．．、Ｓ１６のための項を再使用することによってＳ１からＳ８に対応することができる。この結果、例えば復号器３００における主要ＸＯＲ論理の２５％を削減することができる。
【００３５】
論理３００は、Ｌ３ダブル・データ・ワード・ラッパ出力に含まれるｅＤＲＡＭの１８パックを含むことができ、ラッパの各ｅＤＲＡＭは９ビットのシンボルを出力する。シンボルＥＣＣは、単一シンボル内の任意の数の誤りビットの訂正と、任意の２つの同時誤りシンボルの検出とをサポートすることができる。データの２つのダブルワードがビット０：１２７に格納され、その後のビット位置１３５：１６１に７ビットの特殊訂正不能誤り（ＳＰＵＥ）スタンプと３個のチェックビット・シンボルが続く。７ビットのＳＰＵＥスタンプは、ｅＤＲＡＭに記憶されるストア・データ上に、検出された（訂正不能誤り）ＵＥまたはＳＰＵＥを記録するために使用することができる。
【００３６】
前述のように、本開示の例示の実施形態による短縮レイテンシ誤り復号プロセスは、条件Ｓ１＝Ｓ０αｐとＳ２＝Ｓ０α２ｐの両方が満たされる位置ｐを探索することによって復号を行うことができる。コードワードＲがコード長１８（例えば、１５個のデータ・シンボル＋３個のチェック・シンボル）を有し、ｐが０から１７までの範囲である前述の短縮符号の例の場合、復号項共用の結果として、ｐの偶数値のためのＳ０αｐの計算が、Ｓ２の比較でも使用することができる積に対応するため、復号項共用のない場合に必要となる３４個の定乗数のうちの８個の定乗数が削減される。
【００３７】
しかし、特定の例示の実施形態では、受信コードワードＲのために非標準符号位置を選定することによってさらなる論理圧縮を実現することができる。例えば、１８個のシンボルを含む例示の短縮ＲＳコードワードに関して、短縮符号のために非標準の１組の位置を選定することによって、必要な定乗数の数を２６から１８にさらに減らすことが可能である。非標準の１組の位置を選択することによって必要定乗数の数をどのようにさらに減らすことができるかを例示するために、短縮ＲＳ符号の代わりに短縮されていないＲＳ符号を考えてみる。例えば、ＧＦ（５１２）上で定義された短縮されていない符号の場合、シンドロームＳ１に関する比較は、有限体におけるすべての非ゼロ元に対応する０から５１０までの範囲のｐのすべての値についてＳ０αｐを計算する必要がある。しかし、０から５１０の範囲のｐについてのα２ｐの値は、単にαｐの値の順列に過ぎない。したがって、短縮ＲＳ符号の上記の特性を利用するように元が適切に選択される限り、最初の積を計算した後はそれ以上の積を計算する必要がない。
【００３８】
１８個のシンボルを含む例示の短縮ＲＳ符号を再び参照すると、位置０から１７を使用する代わりに、１組の位置を、その組の中の位置の２倍もすべてその組に含まれるように選定することができる。例えば、｛１，２，４，８，１６，３２，６４，１２８，２５６｝のような位置の組が選定されるとする。この組は、組の中の位置の２倍をすべて含む。具体的には、符号が５１１個の非ゼロ元を有するＧＦ（５１２）上で定義されているため、（元αの指数を表す）選定される位置はモジュロ５１１とみなすことができる。したがって、２＊２５６＝５１２は１ｍｏｄ５１１に相当し、１はモジュロ５１１における２５６の２倍とみなすことができる。
【００３９】
上記の位置の組は長さ９を有する。しかし、１８個のシンボルを含む例示の短縮ＲＳ符号は１７個の非ゼロ位置を必要とする。したがって、組内の位置の２倍をすべて含む非標準位置のもう１つの組を選定する必要がある。最初の組に含まれていない任意の始点を選択することができる。使用される定乗数の数に加えて使用される定乗数のサイズを最小にすることが望ましいため、第２の組の始点として位置９を選択することができ、これによって組｛９，１８，３６，７２，１４４，２８８，５７６＝６５ｍｏｄ５１１，１３０，２６０｝となる。なお、２＊２６０＝５２０であり、これは９ｍｏｄ５１１に等しく、したがって９は２６０の２倍とみなすことができることを理解されたい。したがって、非標準位置のこの第２の組もその２倍をすべて含む。
【００４０】
５１２＝２９であるため、最大２倍組モジュロ５１１は長さ９を有することがわかる。したがって、ＲＳ符号のために１８個の位置｛０，１，２，４，８，９，１６，１８，３２，３６，６４，６５，７２，１２８，１３０，１４４，２５６，２６０｝を選定することができる。すると、対応する２倍モジュロ５１１は、｛０，２，４，８，１６，３２，３６，６４，７２，１２８，１３０，１４４，２５６，２６０，２８８，１，９｝となる。元の組には含まれていない２倍の組に含まれる唯一のべき乗は、２８８である。したがって、１８個の定乗数を得るために、２倍の組の位置２８８とともに元の組から１７個の非ゼロ位置を選択することができる。したがって、元の組の１７個の非ゼロ位置に加えて１つの追加の定乗数のみが必要である。したがって、組内の要素のすべての２倍を含む非標準位置の組を選択することによって、定乗数の数を２６から１８にさらに減らすことができる。
【００４１】
本開示の例示の実施形態による復号プロセスに付随するレイテンシを考えると、レイテンシは従来の復号プロセスよりも大幅に低いことがわかる。具体的には、前述のものと同じレイテンシ値の代入が適用されるとすると、定数行列ＡｐによるＳ０の乗算は、３レベルのＸＯＲ演算を含む。この結果、レイテンシ値は３（２）＝６となる。比較演算２０４は、パターン比較と最終比較の両方を含む。パターン比較は、１つのＸＯＲと、１つのＸＯＲおよび３つのＯＲ演算に相当する９ウェイＯＲとを含む。この結果、レイテンシ値は２＋３（１）＝５となる。最終比較は、単一のＡＮＤ演算であり、その結果、レイテンシ値は１となる。したがって、本開示の例示の実施形態による図２および図８の復号プロセスに付随する合計レイテンシは、６＋５＋１＝１２となり、これは図１に示す従来の復号プロセスに付随するレイテンシ２４よりも大幅に低い。本開示の他の例示の実施形態では、比較演算は１つのＡＮＤ演算と、１つのＡＮＤ演算および３つのＯＲ演算に相当する８ウェイＯＲとを含み、レイテンシ値は上記の６ではなく４となる。
【００４２】
本開示の例示の実施形態により実現されるレイテンシのこの大幅な削減をさらに例示するために、図１の復号ステップと、定数参照１０４と、汎用乗算１０６とに付随するレイテンシ値２２について考えてみる。本開示の例示の実施形態による復号プロセスでは、これらのステップが、３レベルのＸＯＲ演算により、レイテンシ６を有する定数乗算Ｓ０×Ａｐに置き換えられる。例えば、０１１００００１０、００１１００００１、０００１１００００、１０００１１０００、００１００１１１０、０００１００１１１、００００１００１１、１００００１００１、および１１００００１００という行を有する９×９定数行列があるとする。行列のこれらの行は、行１：３＋１＝４ウェイ、行２：３＋１＝４ウェイ、行３：２＋１＝３ウェイ、行４：３＋１＝４ウェイ、行５：４＋１＝５ウェイ、行６：４＋１＝５ウェイ、行７：３＋１＝４ウェイ、行８：３＋１＝４ウェイ、行９：３＋１＝４ウェイというＸＯＲ演算に関連づけられる。したがって、乗算領域は２８のＸＯＲを含むが、３レベルのＸＯＲのみである（最大５ウェイＸＯＲ）。３レベルのＸＯＲの結果、レイテンシは３（２）＝６となる。
【００４３】
上述のように、厳密にデータ／ＸＯＲではなく乗算に定数を使用することによってレイテンシが短縮される。さらに、シンドロームに定数を乗じ、次に除算回路の代わりに比較演算を行うことによっても、レイテンシ短縮が得られる。比較により一致が検出された場合、除算回路（使用する場合）はその値を出しているはずである。定数乗算と比較に必要な回路は、除算回路の場合に必要になる回路よりも小規模である。さらに、復号項共用によりレイテンシをさらに改善することができる。
【００４４】
チェック・ビット生成のための例示の行列を以下に示す。１８個の９ビット入力シンボルを仮定すると、以下の表によって、チェック・ビット生成のための行列が、対応するビット位置とともに与えられる。最初の列は、最初の列で縦に０から２６までの番号が振られた出力（チェック・ビットの２７ビット、３シンボル×９）である。Ｈｍａｔｒｉｘでは、ゼロ（０）はビットが計算の一部ではないことを意味し、１は特定の入力がチェック・ビットの計算の一部であることを意味する。例えば、最初の列の（０）は、入力１、４、５、１０、１１、１２、１４、１５、１６、１９、２０、２１、２２、２３、２４、２５、２６、３０、３１、３２、３３、３５、３９、４１、４２、４３、４５、４６、４８、４９、５０、５２、５３、５６、５８、６０、６１、６３、６４、６６、６８、７１、７２、７３、７６、７８、８１、８２、８４、８５、８６、８８、９３、９８、９９、１００、１０１、１０４、１０５、１０６、１０７、１０８、１１１、１１２、１１７、１２２、１２３、１２５、１２６、１３３、および１３４のＸＯＲによって生成されるチェック・ビット０の列である。これを別の観点から見ると、（行０に示す）入力ビット０を使用してチェック・ビット３、４、５、８、１０、１１、１２、１３、１５、１６、１７、１８、１９、２０、２３、２４、および２５を算出することとなる。同様に、この表に基づいて入力から他の２６個の出力／チェック・ビットを生成することができる。
【００４５】
【表１】
2020524930.tif 000003
【００４６】
【表２】
2020524930.tif 000004
【００４７】
【表３】
2020524930.tif 000005
【００４８】
【表４】
2020524930.tif 000006
【００４９】
場合によっては、ＥＣＣの一形態から別の形態に変換する必要があることがある。例えば、本明細書に記載の例示の実施形態は、キャッシュ設計のための低レイテンシとすることができるが、このレイテンシは、例えば、１ビット訂正／２ビット検出だけのためのハミング符号を有し得るある種のバス転送またはより高速なキャッシュ・レベルには高すぎることがある。データの保護を維持しながら、１つのＥＣＣ符号から別のＥＣＣ符号に変換するために様々な技法を使用することができる。そのような一手法は、データが１つの符号によって訂正／処理された後、第２のコードに符号化される前に、データに対してパリティを生成することである。別の技法は、第２の符号の生成を並列して開始しながら１つの符号を訂正することによってより低いレイテンシを実現する、以下で説明するＥＣＣ変換である。再び図５を参照すると、生データについて第２のＥＣＣ符号（例えばハミング符号）へのチェック・ビット生成を行いながら、それと並列して、Ｓ０に別の定数行列を乗じることに基づいて訂正ベクトルを生成することができるＥＣＣ生成器４０６が示されている。この定数行列は、９ビット・シンボル符号において分散している９ビット・シンボルに相当する、変換される符号（６４７２符号）のためのＥＣＣ行列の９ビットの区分を取ることに基づくことができる。Ｓ０に行列のこれらの区分を乗じて、誤りを含んでいる可能性のある各９ビット・シンボルについて、フリップする必要がある場合があるＥＣＣビットを並列して生成する。訂正すべきシンボルが特定された後は、データと６４７２チェック・ビットの両方に対する後選択を行って訂正されたデータとチェック・ビットの両方を生成する。
【００５０】
図５は、本開示の１つまたは複数の例示の実施形態による例示の誤り訂正フロー５０２を示す概略ブロック図である。誤り訂正フロー５０２は、コードワードからのシンドローム生成と、生成されたシンドロームを使用した誤り復号と、その訂正の受信コードワードのデータへの適用とを含む。次に、訂正されたデータから新たな誤り訂正符号が生成されることになる。図６の「シンドローム復号−＞フリップ」ブロックは、図５に示す復号器４０４と同じ機能を備えることができる。図７は、本開示の１つまたは複数の例示の実施形態による、例示の誤り訂正フロー６０２を示す概略ブロック図である。図６および図７にそれぞれ示す例示の誤り訂正フロー５０２および６０２は、例えば、図３から図５の例示の復号器論理を使用して実装することができる。
【００５１】
基礎となるハードウェア論理を実装するように構成されたプログラム・モジュールのうちの１つまたは複数によって少なくとも部分的に、本開示の例示の実施形態による短縮レイテンシ誤り復号プロセスの１つまたは複数の動作を行うことができる。これらのプログラム・モジュールは、ハードウェア、ソフトウェア、またはファームウェアの任意の組合せで実装することができる。特定の例示の実施形態では、これらのプログラム・モジュールのうちの１つまたは複数は、処理回路によって実行されると１つまたは複数の動作が行われるようにするコンピュータ実行可能命令を含むソフトウェアまたはファームウェアあるいはその両方のモジュールとして少なくとも部分的に実装可能である。本開示の例示の実施形態を実装するように構成されるものとして本明細書に記載されているシステムまたはデバイスは、１つまたは複数の処理回路を含むことができ、そのそれぞれが１つまたは複数の処理ユニットまたはノードを含むことができる。コンピュータ実行可能命令は、処理ユニットによって実行されると、コンピュータ実行可能プログラム・コードに含まれるかまたはコンピュータ実行可能コードによって参照される入力データがアクセスされ、処理されて出力データを提供するようにする、コンピュータ実行可能プログラム・コードを含むことができる。
【００５２】
本明細書では、本開示の１つまたは複数の例示の実施形態について説明している。このような実施形態は本開示の範囲の例示に過ぎず、決して限定的であることを意図したものではない。したがって、本明細書で開示されている実施形態の変形、変更および均等物も本開示の範囲に含まれる。
【００５３】
図９は、本開示の１つまたは複数の例示の実施形態を実装するように構成された例示のネットワーク化アーキテクチャ８００を示す概略図である。このアーキテクチャは、１つまたは複数の復号サーバ８０２と、１つまたは複数のネットワーク８０４と、復号サーバ８０２により場合によって、直接、またはネットワーク８０４のうちの１つまたは複数のネットワークを介してアクセス可能な１つまたは複数のデータ・ストアとを含むことができる。復号サーバ８０２は、本明細書では単数形で記載されていることがあるが、復号サーバ８０２を複数設けてもよく、復号サーバ８０２に関して記載されている機能は複数のそのような復号サーバ８０２に分散させることも可能であることを理解されたい。
【００５４】
例示の構成では、復号サーバ８０２は、１つまたは複数のプロセッサ８０８と、１つまたは複数のメモリ・デバイス８１０（本明細書ではメモリ８１０と総称する）と、１つまたは複数の入出力（「Ｉ／Ｏ」）インターフェース８１２と、１つまたは複数のネットワーク・インターフェース８１４と、データ・ストレージ８１６とを含む。復号サーバ８０２は、復号サーバ８０２の様々な構成要素を機能的に結合する１つまたは複数のバス８１８をさらに含むことができる。
【００５５】
バス８１８は、システム・バスと、メモリ・バスと、アドレス・バスと、メッセージ・バスとのうちの１つを少なくとも含むことができ、復号サーバ８０２の様々な構成要素間で情報（例えば、データ（コンピュータ実行可能コードを含む）、信号など）のやり取りを可能にすることができる。バス８１８は、メモリ・バスまたはメモリ・コントローラ、ペリフェラル・バス、アクセラレーテッド・グラフィックス・ポートなどを含み得るが、これらには限定されない。バス８１８は、業界標準アーキテクチャ（Ｉｎｄｕｓｔｒｙ  Ｓｔａｎｄａｒｄ  Ａｒｃｈｉｔｅｃｔｕｒｅ（ＩＳＡ））、マイクロ・チャネル・アーキテクチャ（Ｍｉｃｒｏ  Ｃｈａｎｎｅｌ  Ａｒｃｈｉｔｅｃｔｕｒｅ：ＭＣＡ）、拡張（Ｅｎｈａｎｃｅｄ）ＩＳＡ（ＥＩＳＡ）、ビデオ・エレクトロニクス・スタンダーズ・アソシエーション（Ｖｉｄｅｏ  Ｅｌｅｃｔｒｏｎｉｃｓ  Ｓｔａｎｄａｒｄｓ  Ａｓｓｏｃｉａｔｉｏｎ：ＶＥＳＡ）アーキテクチャ、アクセラレーテッド・グラフィックス・ポート（Ａｃｃｅｌｅｒａｔｅｄ  Ｇｒａｐｈｉｃｓ  Ｐｏｒｔ（ＡＧＰ））アーキテクチャ、ペリフェラル・コンポーネント・インターコネクツ（Ｐｅｒｉｐｈｅｒａｌ  Ｃｏｍｐｏｎｅｎｔ  Ｉｎｔｅｒｃｏｎｎｅｃｔｓ（ＰＣＩ））アーキテクチャ、ＰＣＩエクスプレス・アーキテクチャ、パーソナル・コンピュータ・メモリ・カード・インターナショナル・アソシエーション（Ｐｅｒｓｏｎａｌ  Ｃｏｍｐｕｔｅｒ  Ｍｅｍｏｒｙ  Ｃａｒｄ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ａｓｓｏｃｉａｔｉｏｎ（ＰＣＭＣＩＡ））アーキテクチャ、ユニバーサル・シリアル・バス（Ｕｎｉｖｅｒｓａｌ  Ｓｅｒｉａｌ  Ｂｕｓ（ＵＳＢ））アーキテクチャなどを含むがこれらには限定されない、任意の適合するバス・アーキテクチャに対応づけられることができる。
【００５６】
メモリ８１０は、ランダム・アクセス・メモリ（ＲＡＭ）などの揮発性メモリ（電力が供給されているときにその状態を維持するメモリ）、または読取り専用メモリ（ＲＯＭ）、フラッシュ・メモリ、強誘電体ＲＡＭ（ＦＲＡＭ）などの不揮発性メモリ（電力が供給されていないときでもその状態を維持するメモリ）、あるいはその両方を含むことができる。本明細書で使用する永続的データ・ストレージという用語は、不揮発性メモリを含み得る。特定の例示の実施形態では、揮発性メモリは不揮発性メモリよりも高速な読取り／書き込みアクセスを可能にすることができる。しかし、特定の他の例示の実施形態では、特定の種類の不揮発性メモリ（例えばＦＲＡＭ）が特定の種類の揮発性メモリよりも高速な読取り／書き込みアクセスを可能とし得る。
【００５７】
様々な実装形態において、メモリ８１０は、様々な種類のスタティック・ランダム・アクセス・メモリ（ＳＲＡＭ）、様々な種類のダイナミック・ランダム・アクセス・メモリ（ＤＲＡＭ）、エンベデッドＤＲＡＭ（ｅＤＲＡＭ）、様々な種類の改変不能ＲＯＭ、または電気的消去可能プログラマブル読取り専用メモリ（ＥＥＰＲＯＭ）、フラッシュ・メモリなどの書き込み可能な種類のＲＯＭあるいはその組合せなど、複数の異なる種類のメモリを含むことができる。メモリ８１０は、メイン・メモリと、命令キャッシュ、データ・キャッシュ、変換索引バッファ（ＴＬＢ）などの様々な形態のキャッシュ・メモリとを含むことができる。また、データ・キャッシュなどのキャッシュ・メモリは、１つまたは複数のキャッシュ・レベル（Ｌ１、Ｌ２など）の階層として編成された多層キャッシュとすることもできる。
【００５８】
データ・ストレージ８１６は、磁気ストレージ、光ディスク・ストレージまたはテープ・ストレージあるいはその組合せなどを含むがこれらには限定されない、取り外し可能ストレージまたは取り外し不能ストレージあるいはその両方を含むことができる。データ・ストレージ８１６は、コンピュータ実行可能命令およびその他のデータの不揮発性記憶を提供することができる。メモリ８１０および取り外し可能または取り外し不能あるいはその両方のデータ・ストレージ８１６は、本明細書で使用する用語であるコンピュータ可読記憶媒体（ＣＲＳＭ）の例である。
【００５９】
データ・ストレージ８１６は、様々な動作をプロセッサ８０８に実行または開始させるために、メモリ８１０にロード可能であって、プロセッサ８０８により実行可能な、コンピュータ実行可能コード、命令などを記憶することができる。データ・ストレージ８１６は、さらに、コンピュータ実行可能命令の実行中にプロセッサ８０８が使用するためにメモリ８１０にコピーすることができるデータを記憶することができる。また、プロセッサ８０８によるコンピュータ実行可能命令の実行の結果として生成された出力データを、まずメモリ８１０に記憶し、最終的に不揮発性記憶のためにデータ・ストレージ８１６にコピーしてもよい。
【００６０】
より詳細には、データ・ストレージ８１６は、１つまたは複数のオペレーティング・システム（Ｏ／Ｓ）８２０と、メモリ８１０または１つまたは複数の外部データ・ストア８０６あるいはその両方にアクセスするように構成された１つまたは複数のデータベース管理システム（ＤＢＭＳ）８２２と、例えばシンドローム生成器８２４、復号器８２６、およびＥＣＣ生成器８２８などの１つまたは複数のプログラム・モジュール、アプリケーション、エンジン、コンピュータ実行可能コード、スクリプトなどとを記憶することができる。データ・ストレージ８１６に記憶されるものとして図示されている構成要素のいずれも、ソフトウェア、ファームウェア、またはハードウェアあるいはこれらの任意の組合せを含むことができる。ソフトウェアまたはファームウェアあるいはその両方は、対応する名称の構成要素に関連して前述した動作のいずれかを実行するように、プロセッサ８０８のうちの１つまたは複数のプロセッサによる実行のためにメモリ８１０にロードすることができるコンピュータ実行可能命令（例えば、コンピュータ実行可能プログラム・コード）を含むことができる。
【００６１】
図９には示されていないが、データ・ストレージ８１６は、復号サーバ８０２の構成要素によって使用される様々な種類のデータ（例えば、入力メッセージ・データ、ポインタ・データ、入力メッセージの入力メッセージ・ブロックの処理からの出力データ、パディング・シグネチャ・データ、メッセージ・ダイジェスト・データなど）をさらに記憶することができる。データ・ストレージ８１６に記憶されているいずれのデータも、コンピュータ実行可能命令を実行する際にプロセッサ８０８が使用するために、メモリ８１０にロードすることができる。さらに、データ・ストレージ８１６に記憶されているいずれのデータも、場合によっては外部データ・ストア８０６に記憶することができ、ＤＢＭＳ８２２を介してアクセスすることができ、コンピュータ実行可能命令を実行する際にプロセッサ８０８が使用するためにメモリ８１０にロードすることができる。
【００６２】
プロセッサ８０８は、メモリ８１０にアクセスし、メモリにロードされているコンピュータ実行可能命令を実行するように構成することができる。例えば、プロセッサ８０８は、本開示の１つまたは複数の実施形態による様々な動作を実行させ、または容易にするために、復号サーバ８０２の様々なプログラム・モジュール、アプリケーション、エンジンなどのコンピュータ実行可能命令を実行するように構成することができる。プロセッサ８０８は、データを入力として受け付け、記憶されているコンピュータ実行可能命令に従って入力データを処理し、出力データを生成することができる、任意の適合する処理ユニットを含むことができる。プロセッサ８０８は、中央演算処理装置、マイクロプロセッサ、冗長命令セット・コンピュータ（ＲＩＳＣ）マイクロプロセッサ、複合命令セット・コンピュータ（ＣＩＳＣ）マイクロプロセッサ、マイクロコントローラ、特定用途向け集積回路（ＡＳＩＣ）、フィールド・プログラマブル・ゲート・アレイ（ＦＰＧＡ）、システム・オン・ア・チップ（ＳｏＣ）、デジタル・シグナル・プロセッサ（ＤＳＰ）などを含むがこれらには限定されない、任意の種類の適合する処理ユニットを含むことができる。また、プロセッサ８０８は、例えば、レジスタ、マルチプレクサ、演算論理ユニット、キャッシュ・メモリに対する読取り／書き込み動作を制御するキャッシュ・コントローラ、分岐予測器など、任意の数の構成要素を含む任意の適合するマイクロアーキテクチャ設計を有することができる。プロセッサ８０８のマイクロアーキテクチャ設計は、様々な命令セットのいずれにも対応可能とすることができる。
【００６３】
次に、データ・ストレージ８１６に記憶されているものとして図示されている他の例示の構成要素を参照すると、Ｏ／Ｓ８２０は、データ・ストレージ８１６からメモリ８１０にロードすることができ、復号サーバ８０２上で実行される他のアプリケーション・ソフトウェアと復号サーバ８０２のハードウェア資源との間のインターフェースを提供することができる。より詳細には、Ｏ／Ｓ８２０は、復号サーバ８０２のハードウェア資源を管理するためと、他のアプリケーション・プログラムに共通サービスを提供するための、１組のコンピュータ実行可能命令を含むことができる。特定の例示の実施形態では、Ｏ／Ｓ８２０は、データ・ストレージ８１６に記憶されているものとして図示されているプログラム・モジュールのうちの１つまたは複数を含むかまたはその他の方法でその実行を制御することができる。Ｏ／Ｓ８２０は、任意のサーバ・オペレーティング・システム、任意のメインフレーム・オペレーティング・システム、または任意の他のプロプライエタリまたは非プロプライエタリ・オペレーティング・システムを含むがこれらには限定されない、現在知られているかまたは将来開発される可能性のある任意のオペレーティング・システムを含むことができる。
【００６４】
ＤＢＭＳ８２２は、メモリ８１０にロードすることができ、メモリ８１０に記憶されているデータ、データ・ストレージ８１６に記憶されているデータ、または外部データ・ストア８０６に記憶されているデータあるいはその組合せの、アクセス、取り出し、記憶または操作あるいはその組合せを行うための機能をサポートすることができる。ＤＢＭＳ８２２は、様々なデータベース・モデル（例えばリレーショナル・モデル、オブジェクト・モデルなど）のいずれでも使用することができ、様々な照会言語のいずれにも対応することができる。ＤＢＭＳ８２２は、１つまたは複数のデータ・スキームで表現されて任意の適合するデータ・リポジトリに記憶されているデータにアクセスすることができる。ＤＢＭＳ８２２を介して復号サーバ８０２がアクセス可能とすることができる外部データ・ストア８０６は、データベース（例えばリレーショナル・データベース、オブジェクト指向データベースなど）、ファイル・システム、フラット・ファイル、データがコンピュータ・ネットワークの複数のノードに記憶される分散データ・ストア、ピア・ツー・ピア・ネットワーク・データストアなどを含むことができるが、これらには限定されない。
【００６５】
次に、復号サーバ８０２の他の例示の構成要素を参照すると、入出力（Ｉ／Ｏ）インターフェース８１２は、復号サーバ８０２による１つまたは複数のＩ／Ｏ装置からの入力情報の受信と、復号サーバ８０２からの１つまたは複数のＩ／Ｏ装置への情報の出力とを容易にすることができる。Ｉ／Ｏ装置は、ディスプレイまたは、タッチ面またはタッチスクリーンを有する表示画面、スピーカなどの音声を出力する音声出力装置、マイクロフォンなどの音声取り込み装置、カメラなどの画像またはビデオあるいはその両方の取り込み装置、触覚ユニットなどの様々な構成要素のうちのいずれでも含むことができる。これらの構成要素のいずれも復号サーバ８０２に組み込まれてよく、または別個の要素であってもよい。Ｉ／Ｏ装置は、例えば、データ・ストレージ・デバイス、印刷装置などの任意の数の周辺装置をさらに含むことができる。
【００６６】
Ｉ／Ｏインターフェース８１２は、ユニバーサル・シリアル・バス（ＵＳＢ）、ＦｉｒｅＷｉｒｅ、Ｔｈｕｎｄｅｒｂｏｌｔ、Ｅｔｈｅｒｎｅｔポート、または１つまたは複数のネットワークに接続可能なその他の接続プロトコルなどの、外部周辺装置接続のためのインターフェースも含むことができる。Ｉ／Ｏインターフェース８１２は、無線ローカル・エリア・ネットワーク（ＷＬＡＮ）（Ｗｉ−Ｆｉなど）無線通信、Ｂｌｕｅｔｏｏｔｈ、または、ロングターム・エボリューション（ＬＴＥ）ネットワーク、ＷｉＭＡＸネットワーク、３Ｇネットワークなどの無線通信ネットワークとの通信が可能な無線通信などの無線ネットワーク無線通信、あるいはその組合せを介して、１つまたは複数のネットワークに接続するための１つまたは複数のアンテナとの接続部も含むことができる。
【００６７】
復号サーバ８０２は、復号サーバ８０２がそれを介して様々な他のシステム、プラットフォーム、ネットワーク、装置などのうちのいずれかと通信することができる、１つまたは複数のネットワーク・インターフェース８１４をさらに含むことができる。ネットワーク・インターフェース８１４は、例えば、ネットワーク８０４のうちの１つまたは複数のネットワーク８０４を介した１つまたは複数の他の装置との通信を可能にすることができる。ネットワーク８０４は、例えば、ケーブル・ネットワーク、パブリック・ネットワーク（例えばインターネット）、プライベート・ネットワーク（例えばフレームリレー・ネットワーク）、無線ネットワーク、セルラ・ネットワーク、電話網（例えば公衆交換電話網）、または任意のその他の適合するプライベートまたは公衆パケット交換または回線交換ネットワークなど、任意の１つまたは複数の異なる種類の通信ネットワークを含み得るが、これらには限定されない。ネットワーク８０４は、ネットワーク８０４に付随する任意の適合する通信範囲を有することができ、例えば、世界規模ネットワーク（例えばインターネット）、都市規模ネットワーク（ＭＡＮ）、広域ネットワーク（ＷＡＮ）、ローカル・エリア・ネットワーク（ＬＡＮ）、またはパーソナル・エリア・ネットワーク（ＰＡＮ）を含むことができる。さらに、このようなネットワークは、同軸ケーブル、ツイスト・ペア線（例えば、ツイスト・ペア銅線）、光ファイバ、ハイブリッド・ファイバ同軸（ＨＦＣ）媒体、マイクロ波媒体、無線周波数通信媒体、衛星通信媒体、またはこれらの任意の組合せを含むがこれらには限定されない任意の適合する種類の媒体を介してネットワーク・トラフィックを送信するための、通信リンクおよび付随するネットワーク装置（例えばリンク層スイッチ、ルータなど）を含むことができる。
【００６８】
データ・ストレージ８１６に記憶されているものとして図９に図示されているプログラム・モジュールは例示に過ぎず、網羅的ではないことと、任意の特定のモジュールによってサポートされているものとして記載されている処理は、代わりに複数のモジュール、エンジンなどに分散させることもでき、または異なるモジュール、エンジンなどによって実行されることもできるものと理解されたい。さらに、復号サーバ８０２上でローカルに稼働するかまたは１つまたは複数のネットワークを介してアクセス可能な他のコンピューティング装置上で稼働するかあるいはその両方の、様々なプログラム・モジュール、スクリプト、プラグイン、アプリケーション・プログラミング・インターフェース（ＡＰＩ）、または任意のその他の適合するコンピュータ実行可能コードを、図９に示すモジュールによって提供される機能または追加または代替の機能あるいはその両方をサポートするために設けることができる。また、特定のモジュールによって実行されるものとして記載されている処理を任意の数のプログラム・モジュールの集合によって実行することができるように、機能を任意の適合する方式でモジュール化することができ、またはいずれかの特定のモジュールによってサポートされているものとして記載されている機能が少なくとも部分的に別のモジュールによってサポートされてもよい。さらに、本明細書に記載の機能をサポートするプログラム・モジュールは、例えばクライアント−サーバ・モデル、ピア・ツー・ピア・モデルなどの任意の適合するコンピューティング・モデルに応じて任意の数のサーバ８０２にわたって実行可能とすることができる。さらに、図９に示すモジュールのいずれかによってサポートされているものとして記載されている機能のいずれも、少なくとも部分的に、任意の数の装置にわたるハードウェアまたはファームウェアあるいはその両方で実装可能である。
【００６９】
また、本開示の範囲から逸脱することなく、復号サーバ８０２は、記載または図示されている構成要素の他に代替または追加あるいはその両方のハードウェア、ソフトウェアまたはファームウェア構成要素を含むことができることを理解されたい。より詳細には、復号サーバ８０２の一部をなすものとして図示されているソフトウェア、ファームウェアまたはハードウェア構成要素は例示に過ぎないことと、様々な実施形態において、一部の構成要素が存在しなくてもよいか、または追加の構成要素を設けてもよいものと理解されたい。様々な例示のモジュールをデータ・ストレージ８１６に記憶されているソフトウェア・モジュールとして図示し、説明したが、モジュールによってサポートされているものとして記載されている機能は、ハードウェア、ソフトウェア、またはファームウェアあるいはこれらの任意の組合せによって可能にすることもできることを理解されたい。さらに、上記のモジュールのそれぞれは、様々な実施形態において、サポートされる機能の論理分割を表すものと理解されたい。さらに、この論理分割は、機能の説明を容易にするために図示されており、機能を実装するためのソフトウェア、ハードウェアまたはファームウェアあるいはその組合せの構造を表すものではない場合があることを理解されたい。したがって、特定のモジュールによって提供されるものとして記載されている機能は、様々な実施形態において、１つまたは複数の他のモジュールによって少なくとも部分的に提供されてもよいものと理解されたい。また、ある実施形態においては１つまたは複数の図示されているモジュールが存在しなくてもよく、一方、他の実施形態においては、図示されていない追加のプログラム・モジュールまたはエンジンあるいはその両方が存在してもよく、記載されている機能または追加の機能あるいはその両方の少なくとも一部をサポートしてもよい。
【００７０】
本開示の例示の実施形態による復号プロセスは、図９に示す例示の構成を有する復号サーバ８０２によって、または、より詳細には、ハードウェア・ロジック、ハードウェア・デバイス、そのようなデバイス上で実行可能なプログラム・モジュール、エンジン、アプリケーションなどによって実行可能である。ただし、このような動作は、多くの他の装置構成とともに実装することもできるものと理解されたい。
【００７１】
本明細書に記載のいずれの動作も、本開示の様々な例示の実施形態において必要に応じた任意の適合する順序で実施または実行することができる。さらに、特定の例示の実施形態では、動作の少なくとも一部を並列して行うことができる。また、特定の例示の実施形態では、記載されている動作より少ないかまたはより多くの動作、または異なる動作が実行されてもよい。
【００７２】
本開示の特定の実施形態について説明したが、当業者は、多くの他の変更および代替実施形態も本開示の範囲に含まれることがわかるであろう。例えば、特定のシステム、システム構成要素、デバイスまたはデバイス構成要素に関して記載されている機能または処理能力あるいはその両方のいずれも、任意の他のシステム、デバイスまたは構成要素によって実行することができる。また、本開示の実施形態による様々な例示の実装形態およびアーキテクチャについて説明したが、当業者は、本明細書に記載されている例示の実装形態およびアーキテクチャに対する多くの他の変更も、本開示の範囲に含まれることがわかるであろう。さらに、別の動作、要素、構成要素、データなどに基づくものとして本明細書に記載されているいずれの動作、要素、構成要素、データなども、１つまたは複数の他の動作、要素、構成要素、データなどにさらに基づくことができるものと理解されたい。したがって、「基づく」という語句またはその変形は、「少なくとも部分的に基づく」と解釈すべきである。
【００７３】
本開示は、システム、方法またはコンピュータ・プログラム製品あるいはその組合せとすることができる。コンピュータ・プログラム製品は、プロセッサに本開示の態様を実施させるためのコンピュータ可読プログラム命令を有するコンピュータ可読記憶媒体（または複数の媒体）を含むことができる。
【００７４】
コンピュータ可読記憶媒体は、命令実行デバイスによって使用されるための命令を保持し、記憶することができる有形デバイスとすることができる。コンピュータ可読記憶媒体は、例えば、電子ストレージ・デバイス、磁気ストレージ・デバイス、光学式ストレージ・デバイス、電磁気ストレージ・デバイス、半導体ストレージ・デバイス、またはこれらの任意の適合する組合せであってよいが、これらには限定されない。コンピュータ可読記憶媒体のより具体的な例の非網羅的なリストには以下のものが含まれる。すなわち、可搬コンピュータ・ディスケット、ハード・ディスク、ランダム・アクセス・メモリ（ＲＡＭ）、読取り専用メモリ（ＲＯＭ）、消去可能プログラマブル読取り専用メモリ（ＥＰＲＯＭまたはフラッシュ・メモリ）、スタティック・ランダム・アクセス・メモリ（ＳＲＡＭ）、可搬コンパクト・ディスク読取り専用メモリ（ＣＤ−ＲＯＭ）、デジタル多用途ディスク（ＤＶＤ）、メモリ・スティック、フロッピィ・ディスク、パンチカードまたは命令が記録された溝内の隆起構造などの機械的に符号化されたデバイス、およびこれらの任意の適合する組合せが含まれる。本明細書で使用されるコンピュータ可読記憶媒体とは、電波またはその他の自由に伝播する電磁波、導波路またはその他の伝送媒体を伝播する電磁波（例えば光ファイバ・ケーブルを通る光パルス）、または電線を介して伝送される電気信号などの、一過性の信号自体であると解釈すべきではない。
【００７５】
本明細書に記載のコンピュータ可読プログラム命令は、コンピュータ可読記憶媒体からそれぞれのコンピューティング／処理デバイスに、または、ネットワーク、例えばインターネット、ローカル・エリア・ネットワーク、ワイド・エリア・ネットワーク、または無線ネットワークあるいはこれらの組合せを介して外部コンピュータまたは外部記憶デバイスにダウンロードすることができる。ネットワークは、銅伝送ケーブル、光伝送ファイバ、無線伝送、ルータ、ファイアウォール、交換機、ゲートウェイ・コンピュータ、またはエッジ・サーバあるいはこれらの組合せを含むことができる。各コンピューティング／処理デバイスにおけるネットワーク・アダプタ・カードまたはネットワーク・インターフェースが、ネットワークからコンピュータ可読プログラム命令を受信し、それらのコンピュータ可読プログラム命令を、それぞれのコンピューティング／処理デバイス内のコンピュータ可読記憶媒体への記憶のために転送する。
【００７６】
本開示の動作を実行するためのコンピュータ可読プログラム命令は、アセンブラ命令、インストラクション・セット・アーキテクチャ（ＩＳＡ）命令、機械命令、機械依存命令、マイクロコード、ファームウェア命令、状態設定データ、または、Ｓｍａｌｌｔａｌｋ（Ｒ）、Ｃ＋＋などのオブジェクト指向プログラミング言語、および「Ｃ」プログラミング言語または同様のプログラム言語などの従来の手続き型プログラミング言語を含む１つまたは複数のプログラミング言語の任意の組合せで書かれたソース・コードまたはオブジェクト・コードとすることができる。コンピュータ可読プログラム命令は、スタンドアロン・ソフトウェア・パッケージとして全体がユーザのコンピュータ上で、または一部がユーザのコンピュータ上で、または一部がユーザのコンピュータ上で一部がリモート・コンピュータ上で、または全体がリモート・コンピュータまたはサーバ上で実行されてよい。後者の場合、リモート・コンピュータは、ローカル・エリア・ネットワーク（ＬＡＮ）またはワイド・エリア・ネットワーク（ＷＡＮ）を含む任意の種類のネットワークを介してユーザのコンピュータに接続することができ、または接続は外部コンピュータ（例えば、インターネット・サービス・プロバイダを使用してインターネットを介して）に対して行ってもよい。実施形態によっては、本開示の態様を実行するために、例えばプログラマブル・ロジック回路、フィールド・プログラマブル・ゲート・アレイ（ＦＰＧＡ）、またはプログラマブル・ロジック・アレイ（ＰＬＡ）を含む電子回路が、コンピュータ可読プログラム命令の状態情報を使用して電子回路をパーソナライズすることにより、コンピュータ可読プログラム命令を実行することができる。
【００７７】
本開示の態様について、本発明の実施形態による方法、装置（システム）、およびコンピュータ・プログラム製品を示すフローチャート図またはブロック図あるいはその両方を参照しながら説明している。フローチャート図またはブロック図あるいはその両方の図の各ブロックおよび、フローチャート図またはブロック図あるいはその両方の図のブロックの組合せは、コンピュータ可読プログラム命令によって実装可能であることはわかるであろう。
【００７８】
これらのコンピュータ可読プログラム命令は、コンピュータまたはその他のプログラマブル・データ処理装置のプロセッサを介して実行される命令が、フローチャートまたはブロック図あるいはその両方の１つまたは複数のブロックで規定されている機能／動作を実装する手段を形成するように、汎用コンピュータ、特殊目的コンピュータ、またはその他のプログラマブル・データ処理装置のプロセッサに供給されてマシンを作り出すものであってよい。これらのコンピュータ可読プログラム命令は、命令が記憶されたコンピュータ可読記憶媒体が、フローチャートまたはブロック図あるいはその両方の１つまたは複数のブロックで規定されている機能／動作の態様を実装する命令を含む製造品を含むように、コンピュータ可読記憶媒体に記憶され、コンピュータ、プログラマブル・データ処理装置、またはその他の装置あるいはこれらの組合せに対して特定の方式で機能するように指示することができるものであってもよい。
【００７９】
コンピュータ可読プログラム命令は、コンピュータ、その他のプログラマブル装置またはその他のデバイス上で実行される命令がフローチャートまたはブロック図あるいはその両方の１つまたは複数のブロックで規定されている機能／動作を実装するように、コンピュータ実装プロセスを作り出すべく、コンピュータ、その他のプログラマブル・データ処理装置、またはその他のデバイスにロードされ、コンピュータ、その他のプログラマブル装置、またはその他のデバイス上で一連の動作ステップを実行されるものであってもよい。
【００８０】
図面中のフローチャートおよびブロック図は、本開示の様々な実施形態によるシステム、方法およびコンピュータ・プログラム製品の可能な実装形態のアーキテクチャ、機能および動作を示す。なお、フローチャートまたはブロック図の各ブロックは、規定されている論理機能を実装するための１つまたは複数の実行可能命令を含む、命令のモジュール、セグメント、または部分を表すことがある。別の実装形態では、ブロックに記載されている機能は、図に記載されている順序とは異なる順序で行われてもよい。例えば、連続して示されている２つのブロックは、関係する機能に応じて、実際には実質的に並行して実行されてよく、またはそれらのブロックは場合によっては逆の順序で実行されてもよい。また、ブロック図またはフローチャート図あるいはその両方の図の各ブロック、およびブロック図またはフローチャート図あるいはその両方の図のブロックの組合せは、規定されている機能または動作を実行する特殊目的ハードウェア・ベースのシステムによって実装されるか、または特殊目的ハードウェアとコンピュータ命令との組合せを実施することができることもわかるであろう。
【００８１】
関連出願の相互参照
本出願は、２０１７年６月１６日に出願された米国仮特許出願第６２／５２１，１２８号の利益を主張し、参照によりその内容が本明細書に組み込まれる。
【図１】
2020524930.tif 000007
【図２】
2020524930.tif 000008
【図３】
2020524930.tif 000009
【図４】
2020524930.tif 000010
【図５】
2020524930.tif 000011
【図６】
2020524930.tif 000012
【図７】
2020524930.tif 000013
【図８】
2020524930.tif 000014
【図９】
2020524930.tif 000015
【手続補正書】
【提出日】令和2年6月26日(2020.6.26)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
１組の入力シンボルを含む受信コードワードの短縮レイテンシ誤り復号を実行するコンピュータ実装方法であって、
前記受信コードワードに付随する第１のシンドロームと第２のシンドロームと第３のシンドロームとを判断することと、
前記第１のシンドロームと前記第２のシンドロームと前記第３のシンドロームとのうちの少なくとも１つが非ゼロであると判断することと、
１組の定乗数を判断することと、
前記１組の定乗数における各定乗数によって前記第１のシンドロームの乗算を行って１組の積を生成することと、
前記１組の積に少なくとも部分的に基づいて、前記第２のシンドロームに関して第１の条件が満たされると判断することと、
前記第３のシンドロームに関して第２の条件が満たされると判断することと、
前記第１の条件と前記第２の条件とが満たされることに少なくとも部分的に基づいて、前記受信コードワードにおいて１つまたは複数のビット誤りを含む単一の入力シンボルを特定することと、
前記単一の入力シンボルにおける前記１つまたは複数のビット誤りを訂正して元のコードワードを得ることと
を含むコンピュータ実装方法。
【請求項２】
前記第２のシンドロームに関して前記第１の条件が満たされると判断することは、前記積の組における第１の積が前記第２のシンドロームと等しいと判断することを含み、前記第１の積は、前記定乗数の組のうちの特定の定乗数による前記第１のシンドロームの乗算を含む、請求項１に記載のコンピュータ実装方法。
【請求項３】
前記第３のシンドロームに関して前記第２の条件が満たされると判断することは、前記特定の定乗数と前記第２のシンドロームとの積が前記第３のシンドロームと等しいと判断することを含む、請求項２に記載のコンピュータ実装方法。
【請求項４】
前記特定の定乗数は第１の定乗数であり、前記第３のシンドロームに関して前記第２の条件が満たされると判断することは、前記積の組における第２の積が前記第３のシンドロームと等しいと判断することを含み、前記第２の積は前記定乗数の組にすでに含まれている第２の定乗数による前記第１のシンドロームの乗算を含む、請求項２に記載のコンピュータ実装方法。
【請求項５】
前記入力シンボルの組を係数として含む多項式を生成することをさらに含み、前記第１のシンドロームを判断することは値１における前記多項式の第１の値を計算することを含み、前記第２のシンドロームを判断することは、値αにおける前記多項式の第２の値を計算することを含み、前記第３のシンドロームを判断することは、値α２における前記多項式の第３の値を計算することを含み、前記特定の定乗数は、前記値αのｐ乗であり、前記ｐは前記受信コードワードにおける前記単一の入力シンボルの位置を示す、請求項１に記載のコンピュータ実装方法。
【請求項６】
前記単一の入力シンボルにおける前記１つまたは複数のビット誤りを訂正することは、前記単一の入力シンボルと前記第１のシンドロームとのＸＯＲをとることを含む、請求項１に記載のコンピュータ実装方法。
【請求項７】
前記定乗数の組を判断することは、候補位置のシーケンスを判断することを含み、前記シーケンスにおける各候補位置のそれぞれの２倍が前記シーケンスに含まれる、請求項１に記載のコンピュータ実装方法。
【請求項８】
１組の入力シンボルを含む受信コードワードの短縮レイテンシ誤り復号を実行するためのシステムであって、
コンピュータ実行可能命令を記憶する少なくとも１つのメモリと、
少なくとも１つのプロセッサとを含み、前記少なくとも１つのプロセッサは、前記少なくとも１つのメモリにアクセスし、前記コンピュータ実行可能命令を実行して、
前記受信コードワードに付随する第１のシンドロームと第２のシンドロームと第３のシンドロームとを判断し、
前記第１のシンドロームと前記第２のシンドロームと前記第３のシンドロームとのうちの少なくとも１つが非ゼロであると判断することと、
１組の定乗数を判断し、
前記１組の定乗数における各定乗数によって前記第１のシンドロームの乗算を行って１組の積を生成し、
前記１組の積に少なくとも部分的に基づいて、前記第２のシンドロームに関して第１の条件が満たされると判断し、
前記第３のシンドロームに関して第２の条件が満たされると判断し、
前記第１の条件と前記第２の条件とが満たされることに少なくとも部分的に基づいて、前記受信コードワードにおいて１つまたは複数のビット誤りを含む単一の入力シンボルを特定し、
前記単一の入力シンボルにおける前記１つまたは複数のビット誤りを訂正して元のコードワードを得る
ように構成された、システム。
【請求項９】
１組の入力シンボルを含む受信コードワードについて短縮レイテンシ誤り復号を実行するためのコンピュータ・プログラムであって、
プロセッサに、
前記受信コードワードに付随する第１のシンドロームと第２のシンドロームと第３のシンドロームとを判断することと、
前記第１のシンドロームと前記第２のシンドロームと前記第３のシンドロームとのうちの少なくとも１つが非ゼロであると判断することと、
１組の定乗数を判断することと、
前記１組の定乗数における各定乗数によって前記第１のシンドロームの乗算を行って１組の積を生成することと、
前記１組の積に少なくとも部分的に基づいて、前記第２のシンドロームに関して第１の条件が満たされると判断することと、
前記第３のシンドロームに関して第２の条件が満たされると判断することと、
前記第１の条件と前記第２の条件とが満たされることに少なくとも部分的に基づいて、前記受信コードワードにおいて１つまたは複数のビット誤りを含む単一の入力シンボルを特定することと、
前記単一の入力シンボルにおける前記１つまたは複数のビット誤りを訂正して元のコードワードを得ることと
を実行させるためのコンピュータ・プログラム。
【国際調査報告】
2020524930.tif 000016
2020524930.tif 000017