(57)【特許請求の範囲】
【請求項１】
２進ワードの少なくとも１つのビット誤りを用いて訂正信号を決定するための回路構成であって、
複数の部分回路（ＳＴ）を備え、それぞれ１つの部分回路が、２進ワードの訂正対象ビット位置に関して提供され、
前記部分回路がそれぞれ、少なくとも２つのロケータ多項式値を提供し、
回路構成がさらに選択ユニットを備え、前記選択ユニットが、前記ロケータ多項式値に応じて、および誤り信号（ｅｒｒ、Ｅ）に応じて訂正信号を決定する
回路構成。
【請求項２】
前記２進ワードのＴ個のビット位置の数が訂正可能であり、ここで、前記数Ｔが、ｔビット誤りの数よりも大きく、前記ｔビット誤りが、誤り符号によって訂正可能である請求項１に記載の回路構成。
【請求項３】
訂正可能なビット誤りのｔビット誤りの前記数が、４以上であり、特に４よりも大きい請求項２に記載の回路構成。
【請求項４】
各部分回路が、少なくとも２つの内部部分回路を有し、各内部部分回路が、ロケータ多項式値を提供する請求項１〜３のいずれか一項に記載の回路構成。
【請求項５】
前記訂正信号によって、前記少なくとも１つのビット誤りが訂正される請求項１〜４のいずれか一項に記載の回路構成。
【請求項６】
少なくとも１つの訂正対象ビット位置と訂正信号とを組み合わせるための論理組み合わせ回路を用いて、それぞれ訂正対象ビットを対応する訂正値と組み合わせて、可逆にかつ一意に、訂正されたビットにすることによって、前記少なくとも１つのビット誤りが訂正される請求項５に記載の回路構成。
【請求項７】
前記訂正信号が、少なくとも２つの部分回路によって並列にまたは実質的に並列に決定される請求項１〜６のいずれか一項に記載の回路構成。
【請求項８】
前記誤り信号が、
誤りのあるビットの数（τ）を表す第１の成分（ｅｒｒ）と、
第２の成分（Ｅ）とを含み、前記第２の成分（Ｅ）が、誤りが認識されたときには第１の値を取り、誤りが認識されなかったときには第２の値を取る
請求項１〜７のいずれか一項に記載の回路構成。
【請求項９】
前記部分回路がそれぞれ、最大でｔ−２個のロケータ多項式値を提供し、ここで、ｔが、誤り符号によって訂正可能なビット誤りの数を表す請求項１〜８のいずれか一項に記載の回路構成。
【請求項１０】
前記部分回路がそれぞれ、前記ビット誤りの数が偶数であるときには、ｔ／２個のロケータ多項式値を提供し、前記ビット誤りの数が奇数であるときには、（ｔ＋１）／２個のロケータ多項式値を提供し、ここで、ｔが、誤り符号によって訂正可能なビット誤りの数を表す請求項１〜８のいずれか一項に記載の回路構成。
【請求項１１】
前記誤り符号が、ガロア域ＧＦ（２ｍ）にわたるｔビット誤り訂正ＢＣＨ符号であり、前記ロケータ多項式値が、ｍ桁の２進値であり、ｍが４以上である請求項９または１０に記載の回路構成。
【請求項１２】
前記誤り信号が、出現した前記ビット誤りの数を含み、ここで、前記数が、前記ＢＣＨ符号の誤りシンドロームを用いて決定される請求項１１に記載の回路構成。
【請求項１３】
前記ＢＣＨ符号が、少なくとも１つのパリティビットを補足される請求項１１または１２に記載の回路構成。
【請求項１４】
前記ＢＣＨ符号の符号語が、
データビット、アドレスビット、および検査ビット、
データビット、アドレスビットから導出されるビット、および検査ビット、または
データビットおよび検査ビット
を含む請求項１１〜１３のいずれか一項に記載の回路構成。
【請求項１５】
前記選択ユニットが、前記ロケータ多項式値を使用して、部分回路毎に、
前記部分回路に関連付けられるビット位置に誤りが出現していないときに第１の訂正信号を決定し、
部分回路に関連付けられるビット位置に少なくとも１つの誤りが出現したときに第２の訂正信号を決定し、
ここで、前記第１の訂正信号および前記第２の訂正信号を用いて、部分回路毎に前記訂正信号が決定される
請求項１〜１４のいずれか一項に記載の回路構成。
【請求項１６】
４つよりも多い部分回路、特に５つの部分回路が提供される請求項１〜１５のいずれか一項に記載の回路構成。
【請求項１７】
前記部分回路のそれぞれに、少なくとも１つのシンドローム成分が提供される請求項１〜１６のいずれか一項に記載の回路構成。
【請求項１８】
前記少なくとも２つのロケータ多項式値が、コンセントレータユニットによって１ビットに集中される請求項１〜１７のいずれか一項に記載の回路構成。
【請求項１９】
前記コンセントレータユニットが、少なくとも１つのゲート、特にＯＲゲートまたはＮＯＲゲートを含む請求項１８に記載の回路構成。
【請求項２０】
前記コンセントレータユニットが、前記選択ユニットの前または前記選択ユニットの後に配置されている請求項１８または１９に記載の回路構成。
【請求項２１】
前記選択ユニットが、
部分回路毎に前記ロケータ多項式値の１つを選択するためのマルチプレクサと、
部分回路毎に前記ロケータ多項式値をマスキングするためのマスキングユニットと
を含む請求項１〜２０のいずれか一項に記載の回路構成。
【請求項２２】
前記部分回路および／または前記選択ユニットが、少なくとも１つの集積回路の一部、特に処理ユニットの一部である請求項１〜２１のいずれか一項に記載の回路構成。
【請求項２３】
前記誤り信号が、誤り認識機能によって提供される請求項１〜２２のいずれか一項に記載の回路構成。
【請求項２４】
少なくとも一部共通に実現された回路部分を含む請求項１〜２３のいずれか一項に記載の回路構成。
【請求項２５】
合成ツールによって最適化された請求項１〜２４のいずれか一項に記載の回路構成。
【請求項２６】
少なくとも１つの訂正対象ビット位置と訂正信号とを組み合わせるための論理組み合わせ回路を用いて、訂正対象ビットに関する訂正値が並列にまたは実質的に並列に提供され、ｔ個までの誤りのあるビットを訂正する、請求項７に記載の回路構成。
【請求項２７】
Ｔ個のビット位置に関する訂正値が、並列または実質的に並列に提供されるように構成され、Ｔがｔよりも大きい請求項２６に記載の回路構成。
【請求項２８】
前記ｔ個の誤りのあるビットを訂正するために、ｔビット誤り訂正符号が使用される請求項２６または２７に記載の回路構成。
【請求項２９】
前記ｔビット誤り訂正符号がＢＣＨ符号である請求項２８に記載の回路構成。
【請求項３０】
２進ワードの少なくとも１つのビット誤りに基づいて訂正信号を決定するための方法であって、
前記２進ワードの訂正対象ビット位置に関して部分回路によって少なくとも２つのロケータ多項式値を決定するステップと、
前記ロケータ多項式値に応じて、および誤り信号（ｅｒｒ、Ｅ）に応じて訂正信号を決定するステップと
を含む方法。
【請求項３１】
前記訂正信号が、少なくとも２つの部分回路によって並列にまたは実質的に並列に決定される請求項３０に記載の方法。
【発明の詳細な説明】
【背景技術】
【０００１】
特定の長さｎの２進シーケンスまたは２進ワードにおいて、任意の１ビット誤り、２ビット誤り、および３ビット誤りを、ＢＣＨ符号を使用して複合型誤り訂正回路によって並列に訂正することが知られている。これは、例えば、（特許文献１）に記載されている。ここで、３以下のビット誤りしか訂正することができないことが欠点である。
【０００２】
（特許文献２）において、４ビット誤りを訂正するための方法が述べられている。ここで、４次の方程式を解くことが２つの２次方程式を解くことに複雑に基づいていることが欠点である；これにより、復号化が遅くなり、高い回路コストを必要とする。依然として、ｔ＞４を有するｔビット誤りを訂正することができないことが欠点である。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】米国特許出願公開第２０１５／００３９９７６Ａ１号明細書
【特許文献２】米国特許第８，２９１，３０３Ｂ２号明細書
【０００４】
【非特許文献１】Ｌｉｎ，  Ｓ．，  Ｃｏｓｔｅｌｌｏ，  Ｄ．：“Ｅｒｒｏｒ  Ｃｏｎｔｒｏｌ  Ｃｏｄｉｎｇ“，  Ｐｒｅｎｔｉｃｅ  Ｈａｌｌ，  １９８３（例えば１４３〜１６０頁および例えば１５５〜１６０頁参照）
【非特許文献２】Ｗｉｃｋｅｒ，  Ｓ．：“Ｅｒｒｏｒ  Ｃｏｎｔｒｏｌ  Ｓｙｓｔｅｍｓ  ｆｏｒ  ｄｉｇｉｔａｌ  Ｃｏｍｍｕｎｉｃａｔｉｏｎ  ａｎｄ  Ｓｔｏｒａｇｅ“，  Ｐｒｅｎｔｉｃｅ  Ｈａｌｌ，  １９９５，  ２０８頁
【発明の概要】
【発明が解決しようとする課題】
【０００５】
本発明の目的は、前述の欠点を改良し、特に、４ビット誤り以上のビット誤りを効率的に訂正することができる可能性を提供することである。
【課題を解決するための手段】
【０００６】
この目的は、独立請求項の特徴に従って解決される。好ましい実施形態は、特に従属請求項から理解できる。
【０００７】
この目的を解決するために、２進ワードの少なくとも１つのビット誤りに基づいて訂正信号を決定するための回路構成であって、
−複数の部分回路（ＳＴ）を備え、それぞれ１つの部分回路が、２進ワードの訂正対象ビット位置に関して提供され、
−部分回路がそれぞれ、少なくとも２つのロケータ多項式値を提供し、
−回路構成がさらに選択ユニットを備え、選択ユニットが、ロケータ多項式値に応じて、および誤り信号（ｅｒｒ、Ｅ）に応じて訂正信号を決定する回路構成が提示される。
【０００８】
一改良形態では、２進ワードのＴ個のビット位置の数が訂正可能であり、ここで、数Ｔが、ｔビット誤りの数よりも大きく、ｔビット誤りが、誤り符号によって訂正可能である。
【０００９】
誤り符号とは、誤り認識符号および／または誤り訂正符号である。
【００１０】
別の改良形態では、訂正可能なビット誤りのｔビット誤りの数は、４以上、特に４よりも大きい。
【００１１】
また、一改良形態では、各部分回路が、少なくとも２つの内部部分回路を有し、各内部部分回路が、ロケータ多項式値を提供する。
【００１２】
さらに、一改良形態では、訂正信号によって少なくとも１つのビット誤りが訂正される。
【００１３】
一実施形態では、少なくとも１つの訂正対象ビット位置と訂正信号とを演算するための演算回路に基づいて、それぞれ訂正対象ビットを対応する訂正値と演算して、可逆にかつ一意に、訂正されたビットにすることによって、少なくとも１つのビット誤りが訂正される。
【００１４】
別の実施形態では、訂正信号が、少なくとも２つの部分回路によって並列にまたは実質的に並列に決定される。
【００１５】
さらに、一実施形態では、誤り信号が、
−誤りのあるビットの数（τ）を表す第１の成分（ｅｒｒ）と、
−第２の成分（Ｅ）とを含み、第２の成分（Ｅ）が、誤りが認識されたときには第１の値を取り、誤りが認識されなかったときには第２の値を取る。
【００１６】
誤りは、例えば誤り符号によって認識される。さらに、場合により、誤りのあるビットの数τが、１よりも大きく、ｔビット誤りの数以下である。
【００１７】
また、一実施形態では、部分回路がそれぞれ、最大でｔ−２個のロケータ多項式値を提供し、ここで、ｔが、誤り符号によって訂正可能なビット誤りの数を表す。
【００１８】
別の改良形態では、部分回路がそれぞれ、ビット誤りの数が偶数であるときには、ｔ／２個のロケータ多項式値を提供し、ビット誤りの数が奇数であるときには、（ｔ＋１）／２個のロケータ多項式値を提供し、ここで、ｔは、誤り符号によって訂正可能なビット誤りの数を表す。
【００１９】
さらに、一改良形態では、誤り符号が、ガロア域ＧＦ（２ｍ）を通るｔビット誤り訂正ＢＣＨ符号であり、ロケータ多項式値が、ｍ桁の２進値であり、ｍが４以上である。
【００２０】
また、一改良形態では、誤り信号が、出現したビット誤りの数を含み、ここで、この数が、ＢＣＨ符号の誤りシンドロームに基づいて決定される。
【００２１】
一実施形態では、ＢＣＨ符号が、少なくとも１つのパリティビットを補足される。
【００２２】
さらなる実施形態では、ＢＣＨ符号の符号語が、
−データビット、アドレスビット、および検査ビット、
−データビット、アドレスビットから導出されるビット、および検査ビット、または
−データビットおよび検査ビット
を含む。
【００２３】
さらに、一実施形態では、選択ユニットが、ロケータ多項式値を使用して、部分回路毎に、
−部分回路に関連付けられるビット位置に誤りが出現していないときに第１の訂正信号を決定し、
−部分回路に関連付けられるビット位置に少なくとも１つの誤りが出現したときに第２の訂正信号を決定し、
ここで、第１の訂正信号および第２の訂正信号に基づいて、部分回路毎に訂正信号が決定される。
【００２４】
一改良形態では、４つよりも多い部分回路、特に５つの部分回路が提供される。
【００２５】
また、一改良形態では、各部分回路に、少なくとも１つのシンドローム成分が提供される。
【００２６】
例えば、部分回路毎に、提供された少なくとも１つのシンドローム成分に基づいて、少なくとも２つのｍ桁のロケータ多項式値が決定される。特に、シンドロームは、多数のシンドローム成分を含むことができる。したがって、ｔビット誤りに対応して、ｔ個のシンドローム成分ｓ１、ｓ３、…、ｓ２ｔ−１を提供することができる。
【００２７】
一実施形態では、少なくとも２つのロケータ多項式値が、コンセントレータユニットによって１ビットに集中される。
【００２８】
例えば、コンセントレータユニットは、複数の入力および１つの出力を有するゲートである。したがって、例えば、全ての入力にわたってＯＲ演算、ＮＯＲ演算を行って、例えば全ての入力が論理（２進）０または１であるかどうかを出力で示すことができる。一般に、例えば、ｍ次元信号（すなわちｍビットを含む信号）を１次元信号に集中させることができ、この１次元信号は、それに対応してより少ないコストでさらに処理することができる。
【００２９】
一改良形態では、コンセントレータユニットが、少なくとも１つのゲート、特にＯＲゲートまたはＮＯＲゲートを含む。
【００３０】
さらに、一改良形態では、コンセントレータユニットが、選択ユニットの前または選択ユニットの後に配置される。
【００３１】
また、一改良形態では、選択ユニットが、
−部分回路毎にロケータ多項式値の１つを選択するためのマルチプレクサと、
−部分回路毎にロケータ多項式値をマスキングするためのマスキングユニットと
を含む。
【００３２】
例えば、誤り信号の部分ｅｒｒによってマルチプレクサの選択を行うことができ、この部分ｅｒｒは、出現したビット誤りの数を示す。誤り信号の部分Ｅによってマスキングを行うことができ、この部分Ｅは、ビット誤りが出現した（またはしていない）かどうかを示す。
【００３３】
一実施形態では、部分回路および／または選択ユニットが、少なくとも１つの集積回路の一部、特に処理ユニットの一部である。
【００３４】
別の実施形態では、誤り信号が、誤り認識機能によって提供される。
【００３５】
誤り認識機能は、回路またはプログラムを含むことができ、または回路および／またはプログラムによって実現することができる。プログラムとは、ソフトウェアまたはファームウェアの形態でのプログラムコードである。
【００３６】
さらに、一実施形態では、回路構成は、少なくとも一部共通に実現された回路部分を含む。
【００３７】
個々の回路部分、例えば、場合によって異なる、類似の、または同一のいくつかのハードウェア構成要素をまとめて実装することができる（「一体実装」）。例えば、回路部分は、共通のキャリアまたはチップに実装することができる。
【００３８】
別の改良形態では、回路構成が、合成ツールによって最適化可能である、または最適化される。
【００３９】
また、上記の目的を解決するために、ｔ個までの誤りのあるビットを訂正するための回路構成であって、ｔが５以上であり、回路構成が、第１と第２の訂正対象ビットに関する訂正値が並列にまたは実質的に並列に提供されるように構成される、回路構成が提示される。
【００４０】
一改良形態では、Ｔ個のビット位置に関する訂正値が、並列または実質的に並列に提供されるように構成され、Ｔがｔよりも大きい。
【００４１】
さらなる改良形態では、ｔ個の誤りのあるビットを訂正するために、ｔビット誤り訂正符号が使用される。
【００４２】
さらに、一実施形態では、ｔビット誤り訂正符号がＢＣＨ符号である。
【００４３】
上記の目的を解決するために、さらに、２進ワードの少なくとも１つのビット誤りに基づいて訂正信号を決定するための方法であって、
−２進ワードの訂正対象ビット位置に関して部分回路によって少なくとも２つのロケータ多項式値を決定するステップと、
−ロケータ多項式値に応じて、および誤り信号（ｅｒｒ、Ｅ）に応じて訂正信号を決定するステップと
を含む方法が提案される。
【００４４】
一改良形態では、訂正信号が、少なくとも２つの部分回路によって並列にまたは実質的に並列に決定される。
【００４５】
本発明の上記の特性、特徴、および利点、ならびにこれらが達成される様式を、例示的実施形態の概略的な説明に関連付けて以下に述べる。例示的実施形態は、図面に関連付けてより詳細に説明される。ここで、分かりやすくするために、同一または同一作用の要素には、同一の参照符号を付すことができる。
【図面の簡単な説明】
【００４６】
【図１】４ビット誤り訂正ＢＣＨ符号を使用する回路構成の例示的実施形態である。
【図２】５ビット誤り訂正ＢＣＨ符号を使用する回路構成の例示的実施形態を示す図である。
【図３】図１の回路構成の部分回路の例示的実施形態を示す図である。
【図４】図１の回路構成の部分回路の例示的実施形態を示す図である。
【図５】ｔが偶数であるときの、ｔビット誤り訂正符号を使用してビットｖ’ｉを訂正するための部分回路の可能な実装形態を示す図である。
【図６】ｔが奇数であるときの、ｔビット誤り訂正符号を使用してビットｖ’ｉを訂正するための部分回路の可能な実装形態を示す図である。
【図７】ｔが奇数であるときの、ｔビット誤り訂正符号を使用してビットｖ’ｉを訂正するための部分回路のさらなる可能な実装形態を示す図である。
【図８】図８ａは、訂正対象の、場合によっては誤りのあるビットおよびアドレスビットから誤りシンドロームを決定するシンドローム発生器を示す図である。図８ｂは、訂正対象の、場合によっては誤りのあるビットから、およびアドレスビットを導出するビットから誤りシンドロームを決定するシンドローム発生器を示す図である。
【図９】ガロア域乗算器、加算器、および反転器をガロア域で使用してロケータ多項式の係数を決定するための回路構成の例示的実施形態を示す図である。
【図１０】ｍ＝５でのガロア域ＧＦ（２ｍ）の要素の様々な表現形態を示す表を示す図である。
【図１１】ガロア域ＧＦ（２５）での反転器に関する表を示す図である。
【発明を実施するための形態】
【００４７】
ランダムに分散された複数ビット誤りの誤り訂正のために、ＢＣＨ符号を使用することができる。これは、例えば、（非特許文献１）で述べられている。
【００４８】
ＢＣＨ符号は、パリティ検査行列Ｈおよび生成行列Ｇによって記述することができる線形符号である。生成行列Ｇは、例えば、パリティ検査行列から導出することができる。
【００４９】
符号が長さＮを有し、ｋの情報ビットを有する場合、パリティ検査行列Ｈは、Ｍ行およびＮ列を有する（Ｍ，Ｎ）行列であり、ここで、Ｍ＝Ｎ−ｋである。このとき、生成行列Ｇは、ｋ行およびＮ列を有する（ｋ，Ｎ）行列であり、符号は、Ｍの検査ビットを有する。
【００５０】
短縮されていないｔビット誤り訂正ＢＣＨ符号は、Ｈ行列
【数１】
0006336547.tif 000002
によって記述することができ、ここで、Ｈ行列は、分離された形態で表されている。通常、符号が短縮されていないとき、Ｈ行列の成分Ｈ１、Ｈ３、…、Ｈ２ｔ−１は、
【数２】
0006336547.tif 000003
として選択される。
【００５１】
ここで、αは、ガロア域と呼ばれる有限体ＧＦ（２ｍ）の原始元でよい。この場合、Ｎ＝２ｍ−１が成り立つ。
【００５２】
αｊ、α３ｊ、…、α（２ｔ−１）ｊの冪指数は、ｍｏｄｕｌｏ２ｍ−１で決定される。αが、使用されるガロア域の原始元である場合、対応するＢＣＨ符号は、原始ＢＣＨ符号と呼ぶことができる。
【００５３】
Ｈ１、Ｈ３、…、Ｈ２ｔ−１は、一般に、それぞれ、
−ｍ行、および
−Ｎ＝２ｍ−１列
を有する（ｍ，Ｎ）行列である。
【００５４】
特別な使用例では、１つの行列Ｈｉのｍ行のいくつかが線形に依存する。この場合、行列Ｈｉの全ての行が線形に独立するまで、行列Ｈｉの行を消去することができる。このとき、行列Ｈｉの行の数は、ｍよりも小さくなり得る。
【００５５】
ガロア域ＧＦ（２ｍ）の要素αｉは、それらのベクトル表現で、例えばｍ桁の２進列ベクトルである。
【００５６】
短縮されていないＢＣＨ符号のＨ行列のＬ列が削除される場合、そこから、長さｎ＝Ｎ−Ｌの短縮ＢＣＨ符号のＨ行列が得られる。ここで、短縮符号に関して、ｎ＝Ｎ−Ｌ＜２ｍ−１が成り立つ。
【００５７】
Ｈ行列に、全て「１」からなる行を補足することも可能である。Ｈ行列における「１」からなる追加の行には、全パリティの追加の考慮が対応する。全パリティを考慮すると、Ｈ行列は形式
【数３】
0006336547.tif 000004
を有することができ、ここで、Ｐは、「１」からなる行を表す。
【００５８】
例えば、ここで長さｎの短縮ＢＣＨ符号を考える。ここで、ｎ＝Ｎ−Ｌ＜２ｍ−１が成り立つ。この符号の符号語ｖ＝ｖ１，…，ｖｎ（符号ベクトルとも呼ぶことができる）は、ｎ個の成分ｖ１、ｖ２、…、ｖｎからなる。ここで、符号ベクトルは、行ベクトルまたは列ベクトルでよい。
【００５９】
行列にベクトルが右から乗算される場合、そのベクトルは列ベクトルと解釈することができ、乗算の結果は列ベクトルである。行列にベクトルが左から乗算される場合、そのベクトルは行ベクトルであり、乗算の結果は行ベクトルである。列ベクトルであるか行ベクトルであるかはそれぞれの文脈から明らかなので、対応するベクトルを列ベクトルまたは行ベクトルとして明示的に強調する必要はない。ベクトルｗが列ベクトルであることが特に強調される場合には、書込み様式ｗＴが使用される。
【００６０】
符号語ｖ＝ｖ１，…，ｖｎが語ｖ’＝ｖ’１，…，ｖ’ｎに破壊されている場合、符号語ｖと破壊されている符号語ｖ’との相違は、
【数４】
0006336547.tif 000005
での誤りベクトルｅによって記述することができる。
【００６１】
符号語ｖｉの成分と、破壊されている符号語ｖ’ｉの成分とが異なり、
【数５】
0006336547.tif 000006
が成り立つとき、誤りベクトルｅの成分ｅｉは１である。符号語ｖｊの成分と、破壊されている符号語ｖ’ｊの成分とが等しく、ｖｊ＝ｖ’ｊが成り立つとき、誤りベクトルｅの成分ｅｊは０である。
【００６２】
誤り訂正回路によって誤りを訂正することが可能である場合、誤り訂正回路が出力する訂正値は、誤りベクトルの成分に等しいことがある。この場合、訂正回路は、そのｎ個の出力のうちの第ｉの出力で、訂正値ｅｉを出力する。ここで、訂正値ｅｉを訂正対象成分ｖ’ｉと排他的論理和演算（ＸＯＲ演算）して、
【数６】
0006336547.tif 000007
とすることができる。
【００６３】
訂正値ｅｉは、訂正ベクトルに集約することができる。符号によって誤りを訂正することができ、訂正ベクトルと訂正対象ベクトルとの成分が成分毎にＸＯＲ演算されるとき、訂正ベクトルは、誤りベクトルと同じである。
【００６４】
誤り訂正回路によって誤りを訂正することができる場合、誤り訂正回路が出力する訂正値は、誤りベクトルの反転成分となり得る。この場合、訂正回路は、そのｎ個の出力のうち第ｉの出力で、反転訂正値
【数７】
0006336547.tif 000008
を提供する。それに対応して、反転訂正値
【数８】
0006336547.tif 000009
は、訂正対象成分ｖ’ｉと演算して、
【数９】
0006336547.tif 000010
とすることができる。また、訂正値の部分集合を反転することも可能である。
【００６５】
場合によっては誤りのあるｎ桁の２進ワードｖ＝ｖ’１，…，ｖ’ｎのｎビット全てが訂正される必要はない。例えば、これらｎビットのうちのＴビットを訂正することが可能であり、ここで、Ｔ≦ｎが成り立つ。ｔビット誤りを訂正する符号を使用して訂正が行われる場合、例えば、Ｔ＞ｔが成り立つ。例えば、ｔビット誤り訂正符号を使用して２進ワードｖのデータビットのみを訂正することができる。また、Ｔ＝ｎが成り立って、全てのビットを訂正することもできる。
【００６６】
ここで述べる例示的実施形態では、特に、ｔ＜Ｔ≦ｎが成り立つ場合を述べる。
【００６７】
ベクトルｖが、分離可能な符号の符号ベクトルであり、符号ベクトルｖ内でデータビットと検査ビットとが分けられている場合、ベクトルｖ’のデータビットのみまたはデータビットの一部のみを訂正することが可能である。それに対応して、データビットと検査ビットとの組合せを訂正する場合もある。
【００６８】
２進ワードｖ’の誤りシンドロームｓ＝（ｓ１，ｓ３，…，ｓ２ｔ−１，ｓＰ）が、
ｓ＝Ｈ・ｖ’      （１）
によって決定され、ここで、誤りシンドロームｓの成分ｓｉに関して以下が成り立つ：
【数１０】
0006336547.tif 000011
【００６９】
（破壊されていない）符号語ｖの誤りシンドロームは０であり、したがって以下が成り立つ：
ｓ＝Ｈ・ｖ＝０      （６）
【００７０】
それに対応して、破壊されている符号語
【数１１】
0006336547.tif 000012
（すなわち、符号語でない２進ワード（「非符号語」とも呼ばれる））に関して、以下が成り立つ：
【数１２】
0006336547.tif 000013
【００７１】
誤りシンドロームｓは、誤りベクトルｅによって決定される。
【００７２】
誤りのある非符号語ｖ’から関連の正しい符号語を決定するために、破壊されている符号語中の、誤りベクトルｅの関連の成分ｅｊについて
ｅｊ＝１
が成り立つような成分ｖ’ｊを反転させることができる。
【００７３】
したがって、成分ｅｊは、誤り訂正回路が使用することができる訂正値に対応する。
【００７４】
考察中の短縮ＢＣＨ符号に関して、誤りベクトルｅは、Ｈ行列
【数１３】
0006336547.tif 000014
を用いて、誤りシンドローム
ｓ＝ｓ１，ｓ３，…，ｓ２ｔ−１，ｓＰ
から決定することができる。行列Ｈ１、Ｈ３、…、Ｈ２ｔ−１は、それらの列によって、以下のように記述することができる：
【数１４】
0006336547.tif 000015
【００７５】
αの冪指数は、前述したように、ｍｏｄｕｌｏ２ｍ−１で決定され、冪指数ｉ１、ｉ２、…、ｉｎは、対毎に異なる。その際、ｊ＝１、…、ｎに関してｉｊ＝ｊが成り立つ必要はない。
【００７６】
ここで、第ｊのビットに１ビット誤りがある場合、以下が成り立つ：
【数１５】
0006336547.tif 000016
および
【数１６】
0006336547.tif 000017
【００７７】
ビット位置ｊおよびｌに２ビット誤りがある場合、以下が成り立つ：
【数１７】
0006336547.tif 000018
および
【数１８】
0006336547.tif 000019
【００７８】
ビット位置ｊ、ｌ、およびｋに３ビット誤りがある場合、以下が成り立つ：
【数１９】
0006336547.tif 000020
および
【数２０】
0006336547.tif 000021
【００７９】
ビット位置ｊ、ｋ、ｌ、およびｑに４ビット誤りがある場合、以下が成り立つ：
【数２１】
0006336547.tif 000022
【００８０】
ここで、誤りの場所を、ロケータ多項式のゼロ点として決定することが可能である。μビット誤りがある場合、
【数２２】
0006336547.tif 000023
でのμ次のロケータ多項式Ｌμ（ｘ）のμ個のゼロ点によって誤り箇所を決定することができる。
【００８１】
μ次のロケータ多項式のゼロ点によって、μ−１ビット誤りのμ−１個の誤り箇所を決定することが可能である。μ−１ビット誤りの場合、μ次のロケータ多項式の第１のゼロ点は０であり、さらなるμ−１個のゼロ点はμ−１個の誤り箇所に対応する。
【００８２】
Ｂｅｒｌｅｋａｍｐ−Ｍａｓｓｅｙのアルゴリズムに従って、誤りの数に対応するロケータ多項式を繰り返し決定することが知られている（例えば、（非特許文献１）。ここで、対応するアルゴリズムが、ハードウェアに高いコストをかけないと実装可能でないことが欠点である。
【００８３】
さらに、対応するロケータ多項式の係数は、シンドローム成分からの線型方程式を解くことによって決定することができる。これは後述する。
【００８４】
まず、例えばμ＝１、２、３、４、５に関するロケータ多項式を示す。
【００８５】
μ＝１に関しては、ロケータ多項式は、形式
【数２３】
0006336547.tif 000024
を有し、μ＝２に関しては、ロケータ多項式は、形式
【数２４】
0006336547.tif 000025
を有し、μ＝３に関しては、ロケータ多項式は、形式
【数２５】
0006336547.tif 000026
を有し、μ＝４に関しては、ロケータ多項式は、形式
【数２６】
0006336547.tif 000027
を有し、μ＝５に関しては、ロケータ多項式は、形式
【数２７】
0006336547.tif 000028
を有する。
【００８６】
μビット誤りがある場合、μ個の誤り箇所ｉ１、ｉ２、ｉ３、…、ｉμが、ロケータ多項式Ｌμ（ｘ）のゼロ点
【数２８】
0006336547.tif 000029
の冪指数である。
【００８７】
ロケータ多項式Ｌμ（ｘ）において、変数ｘが
【数２９】
0006336547.tif 000030
によって置換され、さらに、
【数３０】
0006336547.tif 000031
が定められる場合、
【数３１】
0006336547.tif 000032
が成り立つ。
【００８８】
多項式
【数３２】
0006336547.tif 000033
も同様にロケータ多項式として使用することができる。このとき、μ個の誤り箇所ｊ１、ｊ２、ｊ３、…、ｊμは、ロケータ多項式
【数３３】
0006336547.tif 000034
のゼロ点
【数３４】
0006336547.tif 000035
の負の冪指数であり、ここで、冪指数は、使用されるガロア域がＧＦ（２ｍ）である限り、それぞれｍｏｄｕｌｏ２ｍ−１とみなされる。
【００８９】
以下、例として、ロケータ多項式Ｌμ（ｘ）を使用する。
【００９０】
ロケータ多項式の係数は、以下の線型方程式系の解として決定することができる。
【００９１】
μ＝２に関して、
【数３５】
0006336547.tif 000036
が成り立ち、解は、
【数３６】
0006336547.tif 000037
である。
【００９２】
ここで、ガロア域ＧＦ（２ｍ）で、
【数３７】
0006336547.tif 000038
が成り立つことが考慮に入れられる。
【００９３】
μ＝３に関しては、
【数３８】
0006336547.tif 000039
が成り立ち、ここで、線型方程式を解くことによって、
【数３９】
0006336547.tif 000040
が、
【数４０】
0006336547.tif 000041
と決定され、ここで、この解において、ガロア域ＧＦ（２ｍ）で、
【数４１】
0006336547.tif 000042
が成り立つことが考慮に入れられる。
【００９４】
μ＝４に関しては、
【数４２】
0006336547.tif 000043
が成り立ち、ここで、
【数４３】
0006336547.tif 000044
が、線型方程式を解くことによって、
【数４４】
0006336547.tif 000045
が決定され、ここで、この解において、ガロア域ＧＦ（２ｍ）で、
【数４５】
0006336547.tif 000046
が成り立つことが考慮に入れられる。
【００９５】
μ＝５に関しては、
【数４６】
0006336547.tif 000047
が成り立ち、ここで、
【数４７】
0006336547.tif 000048
に関する具体的な値は、線型方程式（３６）を解くことによって決定され、例えば、（非特許文献２）に提示されている。
【００９６】
一般に、行列Ｍ（ｔ）は、
【数４８】
0006336547.tif 000049
として決定され、５よりも多いビット誤り（ｔ＞５）に関しては以下が成り立つ：
【数４９】
0006336547.tif 000050
【００９７】
【数５０】
0006336547.tif 000051
に関する値は、やはり線型方程式を解くことによって、ここでは線型方程式（３７）を解くことによって決定される。ここで、ガロア域ＧＦ（２ｍ）において、ｌ＝１、２、３、…に関して、
【数５１】
0006336547.tif 000052
が成り立つことが考慮に入れられる。
【００９８】
誤り訂正回路の目的は、任意の１ビット誤り、任意の２ビット誤り、または任意の３ビット誤り、…、または任意のｒビット誤り（１≦ｒ≦ｔ）の誤り位置を、ＢＣＨ符号の誤りシンドロームから、すなわちシンドローム成分ｓ１、ｓ３、…、ｓ２ｔ−１から効率的に決定し、データワードの特定のビット位置で、訂正値によって、誤りのあるものと認識された少なくとも１つのビットの訂正を行うことである。
【００９９】
最大で１つのｔビット誤りがあると仮定される場合、
Ｄｅｔ（Ｍ（ｔ））≠０
から、ｔビット誤りまたは（ｔ−１）ビット誤りがあると結論付けることができる。ｔビット誤りがある場合、誤り箇所は、ｔ次のロケータ多項式Ｌｔ（ｘ）のｔ個のゼロ点によって決定される。ｔ−１ビット誤りがある場合、やはり、ロケータ多項式Ｌｔ（ｘ）のｔ個のゼロ点があり、これらのゼロ点のうちのｔ−１個が誤り箇所を決定し、残りの（１つの）ゼロ点は０であり、誤り箇所を決定しない。
【０１００】
Ｄｅｔ（Ｍ（ｔ））＝０
が成り立つ場合、ｔビット誤りも（ｔ−１）ビット誤りもない。この場合、多くとも１つのｔ−２ビット誤りがある。
【０１０１】
Ｄｅｔ（Ｍ（ｔ−２））≠０の場合、（ｔ−２）ビット誤りまたは（ｔ−３）ビット誤りがあると結論付けることができる：
−ｔ−２ビット誤りがある場合、ｔ−２個の誤り箇所が、ｔ−２次のロケータ多項式Ｌｔ−２（ｘ）のｔ−２個のゼロ点によって決定される。
−ｔ−３ビット誤りがある場合、ｔ−３個の誤り箇所が、ｔ−２次のロケータ多項式Ｌｔ−２（ｘ）のｔ−３個のゼロ点≠０によって決定される。ｔ−２次のロケータ多項式のさらなるゼロ点は、この場合には０である。
【０１０２】
Ｄｅｔ（Ｍ（ｔ−２））＝０である場合、最大で１つの（ｔ−４）ビット誤りがあると帰結することができる。
【０１０３】
誤りの数を決定するために、行列式≠０が見つかるまで、行列式
Ｄｅｔ（Ｍ（ｔ））、Ｄｅｔ（Ｍ（ｔ−２））、Ｄｅｔ（Ｍ（ｔ−４））、…
を考察することができる。
【０１０４】
４ビット誤り訂正ＢＣＨ符号に関して、および追加の全パリティを有する４ビット誤り訂正ＢＣＨ符号に関して、以下に手順を説明する：
【０１０５】
まず、全パリティを考慮に入れない４ビット誤り訂正符号を考察する。行列Ｍ（４）の行列式Ｄｅｔ（Ｍ（４））が決定される。さらに、ｓ＝（ｓ１，ｓ３，ｓ５，ｓ７）≠０が仮定される。
【０１０６】
行列式Ｄｅｔ（Ｍ（４））は、最初の行の要素に従って生成され、残りの３ｘ３行列の行列式は直接計算される。その結果、
【数５２】
0006336547.tif 000053
では、以下が得られる：
【数５３】
0006336547.tif 000054
【０１０７】
そのようにして得られる算術的表現は、シンドローム成分の値から、既知のガロア域乗算器を使用して実装することができ、合成ツールによって最適化することができる。
【０１０８】
Ｄｅｔ（Ｍ（４））≠０が成り立つ場合、４ビット誤りまたは３ビット誤りがある。Ｄｅｔ（Ｍ（４））＝０が成り立つ場合、２ビット誤りまたは１ビット誤りがある。
【０１０９】
以下、全パリティＰを考慮に入れた４ビット誤り訂正符号を考察する。ｓ＝（ｓ１，ｓ３，ｓ５，ｓ７，Ｐ）≠０が仮定される。行列式は、それぞれ最初の行の要素に従って生成され、３ｘ３行列の行列式は直接計算される。
【数５４】
0006336547.tif 000055
で、以下が得られる：
【数５５】
0006336547.tif 000056
【０１１０】
得られる算術的表現は、シンドローム成分の値から、既知のガロア域乗算器を使用して実装することができ、合成ツールによって最適化することができる。
【０１１１】
Ｄｅｔ（Ｍ（５））≠０が成り立つ場合、５ビット誤りまたは４ビット誤りがある。パリティＰ＝１の場合、５ビット誤りであり、パリティＰ＝０の場合、４ビット誤りである。
【０１１２】
Ｄｅｔ（Ｍ（５））＝０が成り立つ場合、ｓ＝（ｓ１，ｓ３，ｓ５，ｓ７）≠０であるときには、３ビット誤り、２ビット誤り、または１ビット誤りがある。パリティＰ＝０の場合、２ビット誤りがあり、パリティＰ＝１の場合、１ビット誤りまたは３ビット誤りがある。
【０１１３】
行列式Ｄｅｔ（Ｍ（３））を決定することが可能である。Ｄｅｔ（Ｍ（３））＝１の場合、３ビット誤りがあり、Ｄｅｔ（Ｍ（３））＝０の場合、１ビット誤りがある。
【０１１４】
１ビット誤りと３ビット誤りを区別するために、
【数５６】
0006336547.tif 000057
が成り立つか、それとも
【数５７】
0006336547.tif 000058
が成り立つかを検査することもできる：
【数５８】
0006336547.tif 000059
の場合、１ビット誤りがあり、
【数５９】
0006336547.tif 000060
の場合、３ビット誤りがある。
【０１１５】
例えば、１つの誤り信号が２つの成分Ｅおよびｅｒｒを含む。誤りがあり、ｓ≠０の場合、誤り信号の成分Ｅは１である。誤りがなく、ｓ＝０である場合、誤り信号の成分Ｅは０である。
【０１１６】
出現する誤りの数は、誤り信号の成分ｅｒｒによって示すことができ、この成分ｅｒｒは、例えば、１ビット誤り、２ビット誤り、…、ｔビット誤りの場合に、対応する２進符号化値１、２、…、ｔを取る。
【０１１７】
図１は、ガロア域ＧＦ（２ｍ）にわたる４ビット誤り訂正ＢＣＨ符号を使用して、場合によっては誤りのある２進ワードｖ’＝ｖ’１，…，ｖ’ｎを訂正するための例示的な回路構成を示す。４ビット誤り訂正ＢＣＨ符号は、１ビット誤り、２ビット誤り、３ビット誤り、または４ビット誤りの訂正を可能にする。
【０１１８】
図１は、シンドローム発生器１０１を含み、シンドローム発生器１０１に、場合によっては誤りのある２進ワードｖ’が提供される。さらに、図１は、ｎ個の部分回路ＳＴｊを含み、そのうち、例として、ｊ＝１およびｊ＝ｎに関する２つの部分回路１０２および１０３が示されている。
【０１１９】
部分回路１０２は、第１の部分回路ＳＴ１に対応し、部分回路１０３は、第ｎの部分回路ＳＴｎを示す。すなわち、部分回路ＳＴｊの出力値を生成するために、ｊ＝１、…、ｎを有するｎ個の部分回路ＳＴｊがある。各部分回路ＳＴｊは、２進ワードｖ’の訂正対象ビット位置に関して提供される。
【０１２０】
部分回路１０２は、２つの内部部分回路１０４、１０５を含み、部分回路１０３は、２つの内部部分回路１０６、１０７を含む。一般に、図１で、第ｊの部分回路ＳＴｊは、例として２つの内部部分回路を含む。
【０１２１】
内部部分回路はそれぞれ、ロケータ多項式値を提供する。内部部分回路１０４は、ｊ＝１を有する
【数６０】
0006336547.tif 000061
に従うロケータ多項式値を提供し、内部部分回路１０５は、ｊ＝１を有する
【数６１】
0006336547.tif 000062
に従うロケータ多項式値を提供し、内部部分回路１０６は、ｊ＝ｎを有する
【数６２】
0006336547.tif 000063
に従うロケータ多項式値を提供し、内部部分回路１０７は、ｊ＝ｎを有する
【数６３】
0006336547.tif 000064
に従うロケータ多項式値を提供する。
【０１２２】
部分回路１０２および１０３はそれぞれ、内部部分回路１０４〜１０７毎にさらに否定論理和ゲート（ＮＯＲゲート）１０８〜１１１を有する。ＮＯＲゲート１０８〜１１１はそれぞれ、ｍ個の入力および１つの出力を有する。ここで、ＮＯＲゲートのｍ個の入力全てが論理０であるとき、出力は常に論理１である。
【０１２３】
以下、例として、部分回路１０２をより詳細に説明する。これらの実施形態は、部分回路１０３にも当て嵌まり、一般に他の各部分回路ＳＴｊにも同様に当てはまる。
【０１２４】
部分回路１０２は、シンドローム発生器１０１によって提供されるシンドローム成分ｓ１、ｓ３、ｓ５、ｓ７を入力するための４・ｍ個の入力を有する。ここで、シンドローム成分ｓ１、ｓ３、ｓ５、ｓ７が、内部部分回路１０４の４・ｍビット幅の入力に入力され、シンドローム成分ｓ１、ｓ３が、内部部分回路１０５の２・ｍビット幅の入力に入力される。
【０１２５】
内部部分回路１０４は、ｍビット幅の出力を有し、この出力は、ＮＯＲゲート１０８の入力と接続されている。ＮＯＲゲート１０８の出力は、選択ユニット１１２の第１の入力（「０」入力）と接続されている。
【０１２６】
内部部分回路１０５は、ｍビット幅の出力を有し、この出力は、ＮＯＲゲート１０９の入力と接続されている。ＮＯＲゲート１０９の出力は、選択ユニット１１２の第２の入力（「１」入力）と接続されている。
【０１２７】
部分回路１０３の構成も上記と同様である。さらに、ビット位置ｊ毎に１つずつ、合計ｎ個の部分回路ＳＴｊが提供される。図１は、例として、ビット位置ｊ＝１に関する部分回路１０２と、ビット位置ｊ＝ｎに関する部分回路１０３とを示す。残りのｎ−２個の部分回路ＳＴ２、ＳＴ３、…、ＳＴｎ−１は、図１では、部分回路１０２と１０３との間の点線で示唆されている。
【０１２８】
２進ワードｖ’のビット位置ｊが誤りを含み、異なるビット位置に全体として４ビット誤りまたは３ビット誤りがある場合、
【数６４】
0006336547.tif 000065
に従うロケータ多項式値を決定する内部部分回路のｍ個の出力に、ｍ桁のロケータ多項式値
【数６５】
0006336547.tif 000066
（このロケータ多項式値は短縮して｛０｝ｍとも表される）が提供される。
【０１２９】
ビット位置ｊが誤りを含まず、ｊとは異なるビット位置に全体として４ビット誤りまたは３ビット誤りがある場合、
【数６６】
0006336547.tif 000067
に従うロケータ多項式値を決定する内部部分回路によって、第１のロケータ多項式値とは異なる値、すなわち｛０｝ｍでない値が提供される。
【０１３０】
ビット位置ｊが誤りを含み、異なるビット位置に２ビット誤りまたは１ビット誤りがある場合、
【数６７】
0006336547.tif 000068
に従うロケータ多項式値を決定する内部部分回路によって、ｍ桁のロケータ多項式値｛０｝ｍが提供される。
【０１３１】
ビット位置ｊが誤りを含まず、異なるビット位置に２ビット誤りまたは１ビット誤りがある場合、
【数６８】
0006336547.tif 000069
に従うロケータ多項式値を決定する内部部分回路によって、ロケータ多項式値｛０｝ｍとは異なる値が提供される。
【０１３２】
既述のように、各ＮＯＲゲート１０８〜１１１は、その入力にｍビットが値０を有するとき、すなわちロケータ多項式値｛０｝ｍが入力されるとき、その出力でそれぞれ値１を生成する。そうでない場合、各ＮＯＲゲート１０８〜１１１の出力で、値０である。
【０１３３】
選択ユニット１１２は、マルチプレクサとみなすこともできる。誤り信号の成分ｅｒｒに応じて、選択ユニット１１２は、その第１の入力またはその第２の入力がその出力に接続されるように制御される。部分回路１０２に関して、これは、ＮＯＲゲート１０８の出力またはＮＯＲゲート１０９の出力が選択ユニット１１２の出力と接続されることを意味する。
【０１３４】
選択ユニット１１２の出力は、ＡＮＤゲート１１４の第１の入力と接続されている。ＡＮＤゲート１１４の第２の入力に、誤り信号の第２の成分Ｅが入力される。ＡＮＤゲート１１４の出力は、演算回路１１７と接続されている。
【０１３５】
誤り信号の２つの成分ｅｒｒ、Ｅは、誤り認識ユニット１１６によって提供される。
【０１３６】
様々な出力に関して同一の誤り認識ユニット１１６が使用され、したがって誤り認識ユニット１１６が１つしか必要とされないようにすることも可能である。
【０１３７】
シンドローム発生器１０１が提供する誤りシンドロームが｛０｝ｌであるとき、および誤りがないときには、誤り信号の成分Ｅは、Ｅ＝０である。誤りシンドロームが｛０｝ｌでなく、誤りがあるときには、誤り信号の成分Ｅは、Ｅ＝１である。ここで、｛０｝ｌは、ｌ個の成分を有する０ベクトルを示し、ここでは、ｌ＝４ｍである。
【０１３８】
誤り信号の成分ｅｒｒは、誤りのあるビットの数に関する情報を提供する。
【０１３９】
ＡＮＤゲート１１４の出力で、訂正信号Δｖ１が生成される。ＡＮＤゲート１１４の出力はＸＯＲゲート１１８の第１の入力に接続され、ＸＯＲゲート１１８の第２の入力に、訂正対象ビットｖ’１が入力される。ＸＯＲゲート１１８の出力には、訂正値
【数６９】
0006336547.tif 000070
が提供される。ここで、演算「＋」は、モジュロ２加算を意味し、これは、ＸＯＲゲート１１８によって実現される。
【０１４０】
これらの実施形態は、別の部分回路ＳＴ２、…、ＳＴｎの演算にも同様に当てはまる。
【０１４１】
例えば、部分回路ＳＴｎとも呼ばれる部分回路１０３に関して以下のことが成り立つ：部分回路１０３の第１の出力（ＮＯＲゲート１１０の１ビット出力）が、選択ユニット１１３の第１の入力（「０」入力）と接続されている。部分回路１０３の第２の出力（ＮＯＲゲート１１１の１ビット出力）が、選択ユニット１１３の第２の入力（「１」入力）と接続されている。誤り信号の成分ｅｒｒに応じて、選択ユニット１１３は、その第１の入力またはその第２の入力がその出力に接続されるように制御される。部分回路１０３に関して、これは、ＮＯＲゲート１１０の出力またはＮＯＲゲート１１１の出力が選択ユニット１１３の出力と接続されることを意味する。
【０１４２】
選択ユニット１１３の出力は、ＡＮＤゲート１１５の第１の入力と接続されている。ＡＮＤゲート１１５の第２の入力に、誤り信号の第２の成分Ｅが入力される。ＡＮＤゲート１１５の出力は、演算回路１１７と接続されている。
【０１４３】
ＡＮＤゲート１１５の出力で、訂正信号Δｖｎが生成される。ＡＮＤゲート１１５の出力はＸＯＲゲート１１９の第１の入力に接続され、ＸＯＲゲート１１９の第２の入力に、訂正対象ビットｖ’ｎが入力される。ＸＯＲゲート１１９の出力には、訂正値
【数７０】
0006336547.tif 000071
が提供される。
【０１４４】
それに対応して、ビット位置ｊ毎に（２つの内部部分回路を有する）１つの部分回路ＳＴｊが提供される。各部分回路の出力は、誤り信号の成分ｅｒｒによって選択され、誤り信号の成分Ｅによってマスキングされる（すなわち、演算回路１１７に中継されるか、または中継されない）。ここで、ビット位置ｊ毎に、選択ユニット、ＡＮＤゲート、およびＸＯＲゲートからなる前述の構成が提供されて、訂正値
【数７１】
0006336547.tif 000072
を提供することができる。
【０１４５】
それぞれのＸＯＲゲート１１８、１１９を含む演算回路１１７は、訂正回路と呼ぶこともできる。
【０１４６】
例えば、図１は、シンドローム発生器１０１が、ｎ本のストリングに関する信号を提供するものとみなすことができ、図１には、例として、ｊ＝１およびｊ＝ｎに関する２つのストリングが示されている。ｎ本のストリングはそれぞれ、例として示されているこれらのストリングと同様に構成され、すなわち、選択ユニットおよびその下流に接続されたＡＮＤゲートを有する部分回路ＳＴｊを含み、ここで、選択ユニットおよびＡＮＤゲートは、（誤り信号の２つの成分ｅｒｒ、Ｅによって）誤り認識ユニット１１６によって制御される。さらに、各ストリングは、演算回路１１７の一部としてＸＯＲゲートを含み、ＸＯＲゲートは、ＡＮＤゲートの出力（そこで、ストリングｊに関して信号Δｖｊが提供される）を訂正対象ビットｖ’ｊと演算し、したがって、そのストリングに関して訂正値
【数７２】
0006336547.tif 000073
を提供する。既述のように、ビット位置毎に１本のストリングが提供される。
【０１４７】
４ビット誤りまたは３ビット誤りが出現したことを誤り信号の成分ｅｒｒが示す場合、それぞれの選択ユニット１１２、１１３の「０」入力が、その出力と接続され、訂正信号Δｖ１，…，Δｖｎ（すなわちΔｖｊ）が、ロケータ多項式値のｍ個の成分から決定され、それらの成分は、それぞれの内部部分回路
【数７３】
0006336547.tif 000074
のｍ個の出力に提供される。
【０１４８】
２ビット誤りまたは１ビット誤りが出現したことを誤り信号の成分ｅｒｒが示す場合、それぞれの選択ユニット１１２、１１３の「１」入力が、その出力と接続され、訂正信号Δｖｊが、ロケータ多項式値のｍ個の成分から決定され、それらの成分は、内部部分回路
【数７４】
0006336547.tif 000075
のｍ個の出力に提供される。
【０１４９】
誤りがない場合、成分ｅｒｒの値は任意である。
【０１５０】
誤り認識回路１１６によって提供される誤り信号の成分ｅｒｒは、選択ユニット１１２、１１３のそれぞれの制御入力に入力され、その値は、選択ユニットのどの入力がそれぞれの出力と接続されるかを決定する。
【０１５１】
４ビット誤りが出現したか３ビット誤りが出現したかに関係なく、４ビット誤りの場合も３ビット誤りの場合も、選択ユニット１１２、１１３の「０」入力がそれぞれの出力と接続されるので、誤り認識回路１１６が４ビット誤りと３ビット誤りとを区別することができる必要はない。
【０１５２】
２ビット誤りが出現したか１ビット誤りが出現したかに関係なく、２ビット誤りの場合も１ビット誤りの場合も、選択ユニット１１２、１１３の「１」入力がそれぞれの出力と接続されるので、誤り認識回路１１６が２ビット誤りと１ビット誤りとを区別することができる必要はない。
【０１５３】
シンドローム発生器１０１は、その４・ｍビット幅の出力で、ワード幅４・ｍの誤りシンドロームｓ＝ｓ１，ｓ３，ｓ５，ｓ７を出力する。ここで、シンドローム発生器１０１は、
【数７５】
0006336547.tif 000076
が成り立つように誤りシンドロームの成分を決定するように構成され、ここで、４ビット誤り訂正ＢＣＨ符号のＨ行列は、
【数７６】
0006336547.tif 000077
である。
【０１５４】
演算回路１１７のＸＯＲゲート（例として、図１には、ストリングｊ＝１およびｊ＝ｎに関するＸＯＲゲート１１８および１１９が示されている）が、訂正対象ビットｖ’１、…、ｖ’ｎを訂正値Δｖ１、…、Δｖｎと演算して、
【数７７】
0006336547.tif 000078
とする。
【０１５５】
誤りシンドロームｓは、シンドローム発生器１０１によって部分回路１０２、１０３の入力に提供される。ＡＮＤゲート１１４、１１５の出力で、訂正値Δｖ１、…、Δｖｎが、好ましくは並列にまたは実質的に並列に出力される。シンドローム発生器１０１は、共通の回路部分として、部分回路１０２、１０３の上流に接続することができる。したがって、訂正値Δｖ１、…、Δｖｎを並列にまたは実質的に並列に決定することが可能である。
【０１５６】
図２は、ガロア域ＧＦ（２ｍ）に関して５ビット誤り訂正ＢＣＨ符号を使用して、場合によっては誤りのある２進ワードｖ’＝ｖ’１，…，ｖ’ｎを訂正するための回路構成を示す。５ビット誤り訂正ＢＣＨ符号は、１ビット誤り、２ビット誤り、３ビット誤り、４ビット誤り、および５ビット誤りの訂正を可能にする。
【０１５７】
図１の前述の実施形態に対応して、図２も、複数（ｎ）本のストリングを有し、ここで、２進ワードｖ’の１つのビット位置の訂正のためにそれぞれ１本のストリングｊが提供される。
【０１５８】
以下、一般に、ストリングｊを述べる：ストリングｊは部分回路ＳＴｊを有し、部分回路ＳＴｊは、図２では例として３つの内部部分回路を含み、ここで、内部部分回路は、ロケータ多項式値
【数７８】
0006336547.tif 000079
を提供する。内部部分回路の出力は、誤り信号の成分ｅｒｒによって制御される選択ユニットによって、ｍ個の入力および１つの１ビット出力を有するＯＲゲートを介してさらなるＯＲゲートの第１の入力と選択的に接続され、そのＯＲゲートの第２の入力は、誤り信号の成分Ｅにつながっている。さらなるＯＲゲートの出力に、ストリングの訂正信号Δｖｊが提供され、この訂正信号Δｖｊは、さらにＸＮＯＲゲートを介して関連の訂正対象ビットｖ’ｊと演算されて、訂正値
【数７９】
0006336547.tif 000080
となる。個々のストリングのＸＮＯＲゲートは、演算回路（訂正回路とも呼ばれる）に集約することができる。それぞれの選択ユニットは、部分回路ＳＴｊの一部でよく、または部分回路ＳＴｊとは別個に構成することもできる。図２において、部分回路ＳＴｊは、例として、ロケータ多項式値を決定するための内部部分回路と、それらの出力に接続する選択ユニットとを含む。基本的には、各部分回路ＳＴｊは、ストリングｊの多少の要素を含むこともできる。
【０１５９】
図２は、例として、ビット位置ｊ＝１およびｊ＝ｎに関する２本のストリングを示す。ｊ＝２、…、ｎ−１に関する残りのストリングは、図２では点線によって示唆されている。
【０１６０】
図２に示される第１のストリングは、部分回路２０２を含み、部分回路２０２は、ロケータ多項式値
【数８０】
0006336547.tif 000081
を決定するための内部部分回路２０４と、ロケータ多項式値
【数８１】
0006336547.tif 000082
を決定するための内部部分回路２０５と、ロケータ多項式値
【数８２】
0006336547.tif 000083
を決定するための内部部分回路２０６とを備える。内部部分回路２０４の出力は、ｍ次元信号を、選択ユニット２１０の「０」入力に提供する。内部部分回路２０５の出力は、ｍ次元信号を、選択ユニット２１０の「１」入力に提供する。内部部分回路２０６の出力は、ｍ次元信号を、選択ユニット２１０の「２」入力に提供する。選択ユニット２１０の対応する入力は、誤り信号の成分ｅｒｒによって選択される。選択ユニット２１０は、ｍ次元信号をＯＲゲート２１２に送り、ＯＲゲート２１２は、ｍ個の入力および１つの出力を有する。ＯＲゲート２１２は、その入力でｍビット全てが２進数０であるときにのみ、その出力で値０を生成する。そうでない場合、ＯＲゲート２１２の出力に、２進値１が現れる。ＯＲゲート２１２の出力は、ＯＲゲート２１４の第１の入力と接続されている。ＯＲゲート２１４の第２の入力に、誤り信号の成分Ｅが入力される。誤り信号、すなわち誤り信号の成分ｅｒｒ、Ｅは、誤り認識ユニット２１６によって提供される。誤り信号は、全てのストリングｊに関して使用することができる。
【０１６１】
ＯＲゲート２１４の出力で、訂正信号Δｖ１が、ＸＮＯＲゲート２１８の第１の入力に提供される。ＸＮＯＲゲート２１８の第２の入力に、訂正対象ビットｖ’１が入力される。ＸＮＯＲゲート２１８の出力に、ビット位置１のための訂正値
【数８３】
0006336547.tif 000084
が提供される。
【０１６２】
前述の実施形態は、ストリングｊ＝ｎに関しても同様に当てはまる：ここでは、選択ユニット２１１と接続された内部部分回路２０７〜２０９を有する部分回路２０３が示されている。内部部分回路２０７〜２０９は、ロケータ多項式値
【数８４】
0006336547.tif 000085
を提供する。選択ユニット２１１の出力は、２つのＯＲゲート２１３および２１５を介してＸＮＯＲゲート２１９と接続され、ＸＮＯＲゲート２１９は、この場合、ビット位置ｎに関する訂正値
【数８５】
0006336547.tif 000086
を提供する。選択ユニット２１１の選択は、誤り信号の成分ｅｒｒによって行われ、ＯＲゲート２１５の第２の入力は、（前述のＯＲゲート２１４の第２の入力と同様に）誤り信号の成分Ｅとつながっている。
【０１６３】
各部分回路ＳＴｊは、シンドローム発生器２０１によって提供されるシンドローム成分ｓ１、ｓ３、ｓ５、ｓ７、ｓ９を入力するための５・ｍ個の入力を有する。
【０１６４】
シンドローム成分ｓ１、ｓ３、ｓ５、ｓ７、ｓ９は、ロケータ多項式値
【数８６】
0006336547.tif 000087
を決定する内部部分回路の５・ｍビット幅の入力に供給される。シンドローム成分ｓ１、ｓ３、ｓ５は、ロケータ多項式値
【数８７】
0006336547.tif 000088
を決定する内部部分回路の３・ｍビット幅の入力に供給される。ｍビット幅のシンドローム成分ｓ１は、ロケータ多項式値
【数８８】
0006336547.tif 000089
を決定する内部部分回路のｍビット幅の入力に供給される。
【０１６５】
２進ワードｖ’のビット位置ｊが誤りを含み、５ビット誤りまたは４ビット誤りがある場合、ロケータ多項式値
【数８９】
0006336547.tif 000090
を決定する内部部分回路のｍ個の出力に、ｍ桁のロケータ多項式値
【数９０】
0006336547.tif 000091
（このロケータ多項式値は短縮して｛０｝ｍとも表される）が提供される。
【０１６６】
ビット位置ｊが誤りを含まず、ｊとは異なるビット位置に５ビット誤りまたは４ビット誤りがある場合、
【数９１】
0006336547.tif 000092
に従うロケータ多項式値を決定する内部部分回路のｍ個の出力に、ロケータ多項式値とは異なる値、すなわち｛０｝ｍでない値が提供される。
【０１６７】
ビット位置ｊが誤りを含み、異なるビット位置に３ビット誤りまたは２ビット誤りがある場合、
【数９２】
0006336547.tif 000093
に従うロケータ多項式値を決定する内部部分回路のｍ個の出力に、ｍ桁のロケータ多項式値｛０｝ｍが提供される。
【０１６８】
ビット位置ｊが誤りを含まず、異なるビット位置に３ビット誤りまたは２ビット誤りがある場合、
【数９３】
0006336547.tif 000094
に従うロケータ多項式値を決定する内部部分回路のｍ個の出力に、ロケータ多項式値｛０｝ｍとは異なる値が提供される。
【０１６９】
ビット位置ｊが誤りを含み、１ビット誤りがある場合、
【数９４】
0006336547.tif 000095
に従うロケータ多項式値を決定する内部部分回路のｍ個の出力に、ｍ桁のロケータ多項式値｛０｝ｍが提供される。
【０１７０】
ビット位置ｊが誤りを含まず、ｊとは異なるビット位置に１ビット誤りがある場合、
【数９５】
0006336547.tif 000096
に従うロケータ多項式値を決定する内部部分回路のｍ個の出力に、ロケータ多項式値｛０｝ｍとは異なる値が提供される。
【０１７１】
それぞれの選択ユニット（例えば、選択ユニット２１０、２１１）は、以下のように構成される：
−誤り信号の成分ｅｒｒが４ビット誤りまたは５ビット誤りを示すとき（すなわちｅｒｒ＝０）、選択ユニットの「０」入力がその出力と接続され、
−誤り信号の成分ｅｒｒが２ビット誤りまたは３ビット誤りを示すとき（すなわちｅｒｒ＝１）、選択ユニットの「１」入力がその出力と接続され、
−誤り信号の成分ｅｒｒが１ビット誤りを示すとき（すなわちｅｒｒ＝２）、選択ユニットの「２」入力がその出力と接続される。
【０１７２】
誤りがない場合、誤り信号の成分ｅｒｒの値は、例えば任意である。
【０１７３】
ビット位置ｊに誤りがある場合、部分回路ＳＴｊは、このストリングのために提供される選択ユニットの出力でもあるそのｍ次元の出力で、５ビット誤り、４ビット誤り、３ビット誤り、２ビット誤り、または１ビット誤りの場合に、ｍ次元ロケータ多項式値｛０｝ｍを出力する。
【０１７４】
ビット位置ｊに誤りがない場合、部分回路ＳＴｊは、このストリングのために提供される選択ユニットの出力でもあるそのｍ次元の出力で、５ビット誤り、４ビット誤り、３ビット誤り、２ビット誤り、または１ビット誤りの場合に、ｍ次元ロケータ多項式値｛０｝ｍとは異なる値を出力する。
【０１７５】
以下、例として、ストリングｊ＝１に関して訂正値
【数９６】
0006336547.tif 000097
の決定を説明する。個々のストリングが同様に構成されているので、これらの実施形態は、任意のビット位置ｊに関して同様に当てはまる。
【０１７６】
選択ユニット２１０のｍ次元の出力は、ＯＲゲート２１２のｍ次元の入力と接続される。ＯＲゲート２１２の１次元の出力では、その入力にロケータ多項式値｛０｝ｍが入力される（すなわちｍビット全てが値０を有する）ときに、２進値０が出力される。それとは異なるロケータ多項式値がＯＲゲート２１２の入力に入る場合には、その出力には２進値１が現れる。
【０１７７】
誤りが出現していないとき、および誤りシンドロームが０のとき、誤り信号の成分Ｅは２進数１である。それに対応して、誤りが出現しているとき、および誤りシンドロームが０でないとき、誤り信号の成分Ｅは２進数０である。
【０１７８】
ＯＲゲート２１４の１ビット幅の出力で、訂正信号Δｖｊ（ｊ＝１を有する）が出力され、ＸＮＯＲゲート２１８で、場合によっては誤りのあるビットｖ’ｊと演算されて、
【数９７】
0006336547.tif 000098
となる。
【０１７９】
この場合、第１のビット位置のストリングを考察した。それに対応して、ｊ＝１が成り立つ。前述したように、これらの実施形態は、ビット位置ｊ＝２、…、ｊ＝ｎに関しても同様に当てはまる。
【０１８０】
それぞれのＸＮＯＲゲート２１８、２１９は、演算回路２１７の一部でよい。この演算回路２１７は、訂正回路とみなすこともできる。
【０１８１】
ここで、ＸＮＯＲゲートが、その機能（排他的否定論理和）を引き受けることに留意されたい；両方の入力に１が入力されるとき、または両方の入力に０が入力されるときに、その出力に論理１が現れる。ＸＮＯＲ演算は、等価演算とも呼ばれる。
【０１８２】
シンドローム発生器２０１は、５・ｍ次元誤りシンドローム
ｓ＝ｓ１，ｓ３，ｓ５，ｓ７，ｓ９
を提供し、この５・ｍ次元誤りシンドロームは、それぞれの部分回路ＳＴｊの５・ｍ次元の入力に入力される。その際、シンドローム発生器２０１によって提供される誤りシンドロームは、
【数９８】
0006336547.tif 000099
が成り立つように決定され、ここで、５ビット誤り訂正ＢＣＨ符号のＨ行列は、
【数９９】
0006336547.tif 000100
である。
【０１８３】
１ビット誤り、２ビット誤り、３ビット誤り、４ビット誤り、または５ビット誤りがあり、第ｊのビットに誤りがある場合、図２の回路構成において、訂正信号の値はΔｖｊ＝０である。第ｊのビットに誤りがない場合、訂正信号は、それに対応して、Δｖｊ＝１である。
【０１８４】
出現する誤りの数に応じて、第１の内部部分回路、第２の内部部分回路、または第３の内部部分回路のどれを使用して訂正値Δｖｊが決定されるかが決定され、ここで、各内部部分回路の下流に第１のＯＲゲート（２１２、２１３）が接続されている。したがって、第１のＯＲゲート（２１２、２１３）は、それぞれの内部部分回路の構成要素として、または内部部分回路とは別個に実現することができる。選択ユニット（２１０、２１１）によって、複数の内部部分回路に関して共通に第１のＯＲゲート（２１２、２１３）を使用することが可能であり、ここで、選択ユニットによって、誤り信号の成分ｅｒｒを用いて内部部分回路の１つを選択可能である。
【０１８５】
特に、シンドローム発生器２０１が共通で部分回路２０２、２０３の上流に接続されているので、訂正信号Δｖ１、…、Δｖｎを並列にまたは実質的に並列に決定することができる。例えば、訂正信号Δｖ１、…、Δｖｎは、同じクロックサイクルで、すなわち実質的に同時に提供することが可能である。
【０１８６】
内部部分回路２０４、２０７の複雑さは、内部部分回路２０６、２０９の複雑さに比べて高いので、５ビット誤りの訂正は、１ビット誤りの訂正よりも長い時間を必要とすることがある。例えば、１ビット誤りの訂正が１クロックサイクル中に行われるが、５ビット誤りの訂正は数クロックサイクルを必要とする場合がある。
【０１８７】
図３は、図１からの内部部分回路１０４および１０６の例示的な実装の図を示す。内部部分回路１０４は、ロケータ多項式値
【数１００】
0006336547.tif 000101
を提供し、内部部分回路１０６は、ロケータ多項式値
【数１０１】
0006336547.tif 000102
を提供する。図１に示されるように、内部部分回路１０４の下流にＮＯＲゲート１０８が接続され、内部部分回路１０６の下流にＮＯＲゲート１１０が接続されている。
【０１８８】
図３で、内部部分回路１０４は、中央回路部分３０２とローカル回路部分３０３とに分割されている。それに対応して、内部部分回路１０６は、中央回路部分３０２とローカル回路部分３０４とに細分化されている。中央回路部分３０２は、全ての内部部分回路に関してロケータ多項式値
【数１０２】
0006336547.tif 000103
を決定するために使用され、ここで、各内部部分回路は、さらに１つの独自のローカル回路部分（図３に、内部部分回路３０３および３０４に関して例として示されている）を有する。
【０１８９】
図１の図に対応して、図３では、ビット位置ｊ＝１およびｊ＝ｎに関する２つのストリングのみが示されている。それらの間に、ビット位置ｊ＝２、…、ｎ−１に関するストリングが配置されており、それらは、同様に構成されており、見やすくするために図３には示されていない。
【０１９０】
中央回路部分３０２は、その４・ｍビット幅の入力に入力される部分シンドロームｓ１、ｓ３、ｓ５、ｓ７に基づいて、４次のロケータ多項式の係数
【数１０３】
0006336547.tif 000104
の値をユニット３０５で決定し、係数
【数１０４】
0006336547.tif 000105
の値をユニット３０６で決定し、係数
【数１０５】
0006336547.tif 000106
の値をユニット３０７で決定し、係数
【数１０６】
0006336547.tif 000107
の値をユニット３０８で決定する。図１に示されるように、シンドローム発生器１０１によって部分シンドロームが提供される。各ユニット３０５〜３０８はそれぞれ、１つの４・ｍビット幅の入力および１つのｍビット幅の出力を有する。
【０１９１】
さらに、ｎ個のローカル回路部分（例えば、ビット位置ｊ＝１に関してはローカル回路部分３０３として示され、ビット位置ｊ＝ｎに関してはローカル回路部分３０４として示されている）があり、それらのローカル回路部分は、ユニット３０５〜３０８によって提供される係数
【数１０７】
0006336547.tif 000108
から、
【数１０８】
0006336547.tif 000109
のロケータ多項式値を決定する。
【０１９２】
以下、例として、ビット位置ｊ＝１に関するローカル回路部分３０３を説明する：
−ユニット３０５の出力は、乗算器３０９の第１の入力と接続されている。乗算器３０９の第２の入力に、一定値
【数１０９】
0006336547.tif 000110
が入力される。乗算器３０９の出力は、ＸＯＲゲート３１２の第１のｍビット幅の入力と接続されている。ＸＯＲゲート３１２は、特に、５ｍビット幅の入力およびｍビット幅の出力を有するＸＯＲ回路として実現される。
−ユニット３０６の出力は、乗算器３１０の第１の入力と接続されている。乗算器３１０の第２の入力に、一定値
【数１１０】
0006336547.tif 000111
が入力される。乗算器３１０の出力は、ＸＯＲゲート３１２の第２のｍビット幅の入力と接続されている。
−ユニット３０７の出力は、乗算器３１１の第１の入力と接続されている。乗算器３１１の第２の入力に、一定値
【数１１１】
0006336547.tif 000112
が入力される。乗算器３１１の出力は、ＸＯＲゲート３１２の第３のｍビット幅の入力と接続されている。
−ユニット３０８の出力は、ＸＯＲゲート３１２の第４のｍビット幅の入力と接続されている。
−ＸＯＲゲート３１２の第５のｍビット幅の入力に、一定値
【数１１２】
0006336547.tif 000113
が入力される。
−ＸＯＲゲート３１２は、その出力で、値
【数１１３】
0006336547.tif 000114
を提供する。
【０１９３】
乗算器は、ガロア域ＧＦ（２ｍ）で乗算を行う。そのような乗算器は、ガロア域乗算器と呼ぶこともできる。２つのｍビット幅の入力を有し、入力の一方に一定値が入力される乗算器は、定数乗算器とも呼ばれる。
【０１９４】
これらの実施形態は、ビット位置ｊ＝ｎに関するローカル回路部分３０４にも同様に当てはまる。それぞれのローカル回路部分３０３、３０４の出力は、それぞれのＮＯＲゲート１０８、１１０と接続されている（これについては図１も参照されたい）。図３には、それに対応して、回路部分３０４に関して、乗算器３１３〜３１５およびＸＯＲゲート３１６が示されている。
【０１９５】
一般に以下のことが成り立つ：ユニット３０５〜３０８を有する中央回路部分３０２は、全てのストリングまたはビット位置ｊに関して共通に使用される。ストリングまたはビット位置ｊ毎に、３つの乗算器Ｍ１ｊ、Ｍ２ｊ、およびＭ３ｊならびに１つのＸＯＲゲートＸＯＲｊを有する独自のローカル回路部分ＬＳＴｊがある。
【０１９６】
ビット位置ｊ＝１、…、ｎに関して、以下のことが成り立つ：
−ユニット３０５の出力は、乗算器Ｍ１ｊのｍビット幅の第１の入力と接続され、乗算器Ｍ１ｊの第２の入力に、一定値
【数１１４】
0006336547.tif 000115
が入力される。乗算器Ｍ１ｊの出力は、ＸＯＲゲートＸＯＲｊのｍビット幅の第１の入力と接続され、値
【数１１５】
0006336547.tif 000116
をＸＯＲゲートＸＯＲｊに送る。
−ユニット３０６の出力は、乗算器Ｍ２ｊのｍビット幅の第１の入力と接続され、乗算器Ｍ２ｊの第２の入力に、一定値
【数１１６】
0006336547.tif 000117
が入力される。乗算器Ｍ２ｊの出力は、ＸＯＲゲートＸＯＲｊのｍビット幅の第２の入力と接続され、値
【数１１７】
0006336547.tif 000118
をＸＯＲゲートＸＯＲｊに送る。
−ユニット３０７の出力は、乗算器Ｍ３ｊのｍビット幅の第１の入力と接続され、乗算器Ｍ３ｊの第２の入力に、一定値
【数１１８】
0006336547.tif 000119
が入力される。乗算器Ｍ３ｊの出力は、ＸＯＲゲートＸＯＲｊのｍビット幅の第３の入力と接続され、値
【数１１９】
0006336547.tif 000120
をＸＯＲゲートＸＯＲｊに送る。
−ユニット３０８の出力は、ＸＯＲゲートＸＯＲｊのｍビット幅の第４の入力と接続され、値
【数１２０】
0006336547.tif 000121
をＸＯＲゲートＸＯＲｊに送る。
−ＸＯＲゲートＸＯＲｊのｍビット幅の第５の入力に、値
【数１２１】
0006336547.tif 000122
が入力される。したがって、ＸＯＲゲートＸＯＲｊは、そのｍビット幅の出力で、値
【数１２２】
0006336547.tif 000123
を生成し、ここで、「＋」によって、ここでは成分毎のモジュロ２加算または成分毎のＸＯＲ演算が表される。
−ＸＯＲゲートＸＯＲｊの出力は、下流に配置されたＮＯＲゲートのｍビット幅の入力（ビット位置ｊにつき１つのＮＯＲゲートが提供される）と接続されている。それぞれのＮＯＲゲートは、ｍビット幅の入力および１ビット幅の出力を有する。
【０１９７】
ユニット３０５は、その入力に入力される部分シンドロームｓ１に依存して、値
【数１２３】
0006336547.tif 000124
が生成され、その出力に提供されるように構成される。
【０１９８】
ユニット３０６は、その入力に入力される部分シンドロームｓ１、ｓ３、ｓ５、ｓ７に依存して、値
【数１２４】
0006336547.tif 000125
が生成され、その出力に提供されるように構成される。
【０１９９】
ユニット３０７は、その入力に入力される部分シンドロームｓ１、ｓ３、ｓ５、ｓ７に依存して、値
【数１２５】
0006336547.tif 000126
が生成され、その出力に提供されるように構成される。
【０２００】
ユニット３０８は、その入力に入力される部分シンドロームｓ１、ｓ３、ｓ５、ｓ７に依存して、値
【数１２６】
0006336547.tif 000127
が生成され、その出力に提供されるように構成される。
【０２０１】
値
【数１２７】
0006336547.tif 000128
を決定するためのユニット３０５〜３０８の実装は、提示された関係に対応して、既知のガロア域乗算器、成分毎のＸＯＲ演算、および、部分シンドロームからのガロア域での既知の分割を使用して行うことができる。
【０２０２】
乗算器Ｍ１ｊ、Ｍ２ｊ、およびＭ３ｊ（またはｊ＝１に関しては３０９〜３１１およびｊ＝ｎに関しては３１３〜３１５）をＸＯＲ演算として実現することができる。
【０２０３】
中央回路部分３０２は、全ての部分回路に関して、ｊ＝１、…、ｎを有するロケータ多項式値
【数１２８】
0006336547.tif 000129
を決定するために使用される。したがって、中央回路部分３０２は、ローカル回路部分３０３、３０４の上流に接続されている。好ましくは、ロケータ多項式値
【数１２９】
0006336547.tif 000130
は、図３の表現に従って、並列にまたは実質的に並列に（例えば共通のタイミングで）提供することができる。したがって、ロケータ多項式値、したがって訂正信号を、並列にまたは実質的に並列に決定することができる。
【０２０４】
図４は、図１の図示に対する補完として、２ビット誤りまたは１ビット誤りが出現した場合に関して、ｊ＝１、…、ｎに関するロケータ多項式値
【数１３０】
0006336547.tif 000131
を提供する内部部分回路１０５および１０７の例示的な実装を示す。ここでは、例として、内部部分回路１０５および１０７は、中央回路部分４０１とローカル回路部分４０２とに分割されており、ここで、中央回路部分４０１は、両方の内部部分回路１０５および１０７に使用され、さらに、各内部部分回路１０５および１０７に関して、もう１つの個別のローカル回路部分が提供される。図４による例では、個々のローカル回路部分が、回路部分４０２に集約されている。実装形態によっては、ローカル回路部分を互いに別個に実現することもできる（これは、例として図３で説明した）。
【０２０５】
中央回路部分４０１は、
【数１３１】
0006336547.tif 000132
を決定するためのユニット４０３と、
【数１３２】
0006336547.tif 000133
を決定するためのユニット４０４とを含む。ユニット４０３もユニット４０４も、２・ｍ幅の入力を有し、その入力に、シンドローム発生器（図４には図示せず）によって提供される部分シンドロームｓ１、ｓ３が入力される。ユニット４０３および４０４はそれぞれ、ｍビット幅の出力を有し、その出力で、値
【数１３３】
0006336547.tif 000134
がローカル回路部分４０２に利用可能にされる。
【０２０６】
ローカル回路部分４０２は、各ビット位置ｊ毎に１つのローカル回路部分を含む（図４では、ローカル回路部分は、例としてブロック４０２にまとめられている）；したがって、係数
【数１３４】
0006336547.tif 000135
の値からロケータ多項式値
【数１３５】
0006336547.tif 000136
を決定するｎ個のそのようなローカル回路部分がある。
【０２０７】
ユニット４０３および４０４を有する中央回路部分４０１は、この例示的実施形態では、全てのストリングまたはビット位置ｊに関して共通に使用される。ストリングまたはビット位置ｊ毎に、１つの乗算器ＭＰｊおよび１つのＸＯＲゲートＥＸｊを有する独自のローカル回路部分ＳＴＬｊがある。
【０２０８】
一般に、ビット位置ｊ＝１、…、ｎに関して：
−ユニット４０３の出力は、乗算器ＭＰｊのｍビット幅の第１の入力と接続され、乗算器ＭＰｊの第２の入力に、一定値
【数１３６】
0006336547.tif 000137
が入力される。乗算器ＭＰｊの出力は、ＸＯＲゲートＥＸｊのｍビット幅の入力と接続され、値
【数１３７】
0006336547.tif 000138
をＸＯＲゲートＥＸｊに送る。
−ユニット４０４の出力は、ＸＯＲゲートＥＸｊのｍビット幅の第２の入力と接続されている。
−ＸＯＲゲートＥＸｊのｍビット幅の第３の入力に、値
【数１３８】
0006336547.tif 000139
が入力される。したがって、ＸＯＲゲートＥＸｊは、そのｍビット幅の出力で、値
【数１３９】
0006336547.tif 000140
を生成する。
【０２０９】
ＸＯＲゲートＥＸｊの出力は、それぞれのストリング（図１参照）に関するＮＯＲゲートのｍビット幅の入力と接続されている。
【０２１０】
図４は、例として、ビット位置ｊ＝１およびｊ＝ｎに関する２つのストリングのみを示す。それらの間に、ビット位置ｊ＝２、…、ｎ−１に関するストリングが配置されており、それらは、同様に構成されており、見やすくするために図４には示されていない。
【０２１１】
ストリングｊ＝１に関して、そのローカル回路部分について以下の参照符号を使用する：乗算器ＭＰ１には参照符号４０５を付し、ＸＯＲゲートＥＸ１には参照符号４０７を付す。さらに、図１からのＮＯＲゲート１０９が示されており、ＮＯＲゲート１０９は、ＸＯＲゲート４０７の出力と接続されている。
【０２１２】
ストリングｊ＝ｎに関して、そのローカル回路部分について以下の参照符号を使用する：乗算器ＭＰｎには参照符号４０６を付し、ＸＯＲゲートＥＸｎには参照符号４０８を付す。さらに、図１からのＮＯＲゲート１１１が示されており、ＮＯＲゲート１１１は、ＸＯＲゲート４０８の出力と接続されている。
【０２１３】
ユニット４０３は、その入力に入力される部分シンドロームｓ１に依存して、値
【数１４０】
0006336547.tif 000141
が生成され、その出力に提供されるように構成される。
【０２１４】
ユニット４０４は、その入力に入力される部分シンドロームｓ１、ｓ３に依存して、値
【数１４１】
0006336547.tif 000142
が生成され、その出力に提供されるように構成される。
【０２１５】
図５は、ｔビット誤り訂正ＢＣＨ符号を用いた訂正が行われるときの、訂正値Δｖｊを決定するための例示的な回路構成を示す。ここで、ｔは、例として偶数である。
【０２１６】
図５は、内部部分回路５０２〜５０４を有する部分回路５０１（ビット位置ｊまたはストリングｊに関する部分回路ＳＴｊとも呼ぶ）を示す。部分回路５０１は、ｔ・ｍビット幅の入力を有し、その入力に、ｔ個の成分ｓ１、ｓ３、…、ｓ２ｔ−１を有する誤りシンドロームｓが入力される。
【０２１７】
内部部分回路５０２は、ロケータ多項式値
【数１４２】
0006336547.tif 000143
を提供し、そのｍ次元の出力で、ｍ次元の値ｚｊ［ｔ，ｔ−１］を出力する。内部部分回路５０２の出力は、ＮＯＲゲート５０５のｍ次元の入力と接続され、ＮＯＲゲート５０５は、１ビット幅の出力を有し、この出力は、選択ユニット５０８の第１の入力と接続されている。
【０２１８】
内部部分回路５０３は、ロケータ多項式値
【数１４３】
0006336547.tif 000144
を提供し、そのｍ次元の出力で、ｍ次元の値ｚｊ［ｔ−２，ｔ−３］を出力する。内部部分回路５０３の出力は、ＮＯＲゲート５０６のｍ次元の入力と接続され、ＮＯＲゲート５０６は、１ビット幅の出力を有し、この出力は、選択ユニット５０８の第２の入力と接続されている。
【０２１９】
内部部分回路５０４は、ロケータ多項式値
【数１４４】
0006336547.tif 000145
を提供し、そのｍ次元の出力で、ｍ次元の値ｚｊ［２，１］を出力する。内部部分回路５０４の出力は、ＮＯＲゲート５０７のｍ次元の入力と接続され、ＮＯＲゲート５０７は、１ビット幅の出力を有し、この出力は、選択ユニット５０８の第ｔ／２の入力と接続されている。
【０２２０】
したがって、選択ユニット５０８は、ビット誤り訂正符号が訂正することができる数の半分の入力を有する。
【０２２１】
ビットｖ’ｊが誤りである場合、以下のことが成り立つ：
−ｔビット誤りまたは（ｔ−１）ビット誤りがある場合、部分回路ＳＴｊのｍ個の第１の出力（これらは、ここでは内部部分回路５０２の出力に対応し、内部部分回路５０２に基づいてロケータ多項式値
【数１４５】
0006336547.tif 000146
が提供される）で、ロケータ多項式値
ｚｊ［ｔ，ｔ−１］＝｛０｝ｍ
が出力される。
−（ｔ−２）ビット誤りまたは（ｔ−３）ビット誤りがある場合、部分回路ＳＴｊのｍ個の第２の出力（これらは、ここでは内部部分回路５０３の出力に対応し、内部部分回路５０３に基づいてロケータ多項式値
【数１４６】
0006336547.tif 000147
が提供される）で、ロケータ多項式値
ｚｊ［ｔ−２，ｔ−３］＝｛０｝ｍ
が出力される。
−これらの実施形態は、ビット誤りｔ−ｑおよびｔ−ｑ−１（ｑ＝４、６、８…）に関して、最終的に２ビット誤りおよび１ビット誤りに達するまで同様に続けることができる（以下の点を参照）。
−２ビット誤りまたは１ビット誤りがある場合、部分回路ＳＴｊのｍ個の第ｔ／２の出力（これらは、ここでは内部部分回路５０４の出力に対応し、内部部分回路５０４に基づいてロケータ多項式値
【数１４７】
0006336547.tif 000148
が提供される）で、ロケータ多項式値
ｚｊ［２，１］＝｛０｝ｍ
が出力される。
【０２２２】
ビットｖ’ｊが誤りを含まない場合、以下のことが成り立つ：
−ｔビット誤りまたは（ｔ−１）ビット誤りがある場合、部分回路ＳＴｊのｍ個の第１の出力（これは、ここでは内部部分回路５０２の出力に対応し、それらに基づいて、ロケータ多項式値
【数１４８】
0006336547.tif 000149
が提供される）で、ロケータ多項式値
ｚｊ［ｔ，ｔ−１］≠｛０｝ｍ
が出力される。
−（ｔ−２）ビット誤りまたは（ｔ−３）ビット誤りがある場合、部分回路ＳＴｊのｍ個の第２の出力（これらは、ここでは内部部分回路５０３の出力に対応し、内部部分回路５０３に基づいてロケータ多項式値
【数１４９】
0006336547.tif 000150
が提供される）で、ロケータ多項式値
ｚｊ［ｔ−２，ｔ−３］≠｛０｝ｍ
が出力される。
−これらの実施形態は、ビット誤りｔ−ｑおよびｔ−ｑ−１（ｑ＝４、６、８…）に関して、最終的に２ビット誤りおよび１ビット誤りに達するまで同様に続けることができる（以下の点を参照）。
−２ビット誤りまたは１ビット誤りがある場合、部分回路ＳＴｊのｍ個の第ｔ／２の出力（これらは、ここでは内部部分回路５０４の出力に対応し、内部部分回路５０４に基づいてロケータ多項式値
【数１５０】
0006336547.tif 000151
が提供される）で、ロケータ多項式値
ｚｊ［２，１］≠｛０｝ｍ
が出力される。
【０２２３】
出現する誤りの数に応じて、選択ユニット５０８の誤り認識機能５０９によって提供される誤り信号の成分ｅｒｒの値が、選択ユニット５０８のどの入力がその出力と接続されるかを決定する。選択ユニット５０８の出力は、ＡＮＤゲート５１０の第１の入力と接続されている。ＡＮＤゲート５１０の第２の入力に、同様に誤り認識機能５０９によって提供される誤り信号の成分Ｅが入る。ＡＮＤゲート５１０の出力は、場合によっては誤りのあるビットｖ’ｊに関する訂正値Δｖｊを提供する。
【０２２４】
ｔビット誤りまたは（ｔ−１）ビット誤りがある場合、選択ユニットは、その第１の入力をその出力と接続し、内部部分回路５０２の出力に提供される値ｚｊ＝ｚｊ［ｔ，ｔ−１］が、Δｖｊ＝１であるかΔｖｊ＝０であるかを決定する：
−ｚｊ［ｔ，ｔ−１］＝｛０｝ｍの場合、Δｖｊ＝１である。
−ｚｊ［ｔ，ｔ−１］≠｛０｝ｍの場合、Δｖｊ＝０である。
【０２２５】
（ｔ−２）ビット誤りまたは（ｔ−３）ビット誤りがある場合、選択ユニット５０８は、その第２の入力をその出力と接続し、内部部分回路５０３の出力に提供される値ｚｊ＝ｚｊ［ｔ−２，ｔ−３］が、Δｖｊ＝１であるかΔｖｊ＝０であるかを決定する：
−ｚｊ［ｔ−２，ｔ−３］＝｛０｝ｍの場合、Δｖｊ＝１である。
−ｚｊ［ｔ−２，ｔ−３］≠｛０｝ｍの場合、Δｖｊ＝０である。
【０２２６】
同様に、その後のビット誤りの対
｛（ｔ−５）；（ｔ−４）｝、｛（ｔ−７）；（ｔ−６）｝、…
に関しても、以下に述べる２ビット誤りと１ビット誤りとの対まで、この考察を続けることができる。
【０２２７】
最終的に２ビット誤りまたは１ビット誤りがある場合、選択ユニット５０８は、その第ｔ／２の入力をその出力と接続し、内部部分回路５０４の出力に提供される値ｚｊ＝ｚｊ［２，１］が、Δｖｊ＝１であるかΔｖｊ＝０であるかを決定する。
−ｚｊ［２，１］＝｛０｝ｍの場合、Δｖｊ＝１である。
−ｚｊ［２，１］≠｛０｝ｍの場合、Δｖｊ＝０である。
【０２２８】
誤りがない場合、誤り信号の成分Ｅの値はゼロ（Ｅ＝０）であり、Δｖｊ＝０が成り立つ。
【０２２９】
図６は、ｔビット誤り訂正ＢＣＨ符号を用いた訂正が行われるときの、訂正値Δｖｊを決定するための例示的な回路構成を示す。ここで、ｔは、例として奇数である。
【０２３０】
図６は、内部部分回路６０２〜６０４を有する部分回路６０１（ビット位置ｊまたはストリングｊに関する部分回路ＳＴｊとも呼ぶ）を示す。部分回路６０１は、ｔ・ｍビット幅の入力を有し、その入力に、ｔ個の成分ｓ１、ｓ３、…、ｓ２ｔ−１を有する誤りシンドロームｓが入力される。
【０２３１】
内部部分回路６０２は、ロケータ多項式値
【数１５１】
0006336547.tif 000152
を提供し、そのｍ次元の出力で、ｍ次元値
ｚｊ［ｔ，ｔ−１］
を出力する。内部部分回路６０２の出力は、ＮＯＲゲート６０５のｍ次元の入力と接続され、ＮＯＲゲート６０５は、１ビット幅の出力を有し、この出力は、選択ユニット６０８の第１の入力と接続されている。
【０２３２】
内部部分回路６０３は、ロケータ多項式値
【数１５２】
0006336547.tif 000153
を提供し、そのｍ次元の出力で、ｍ次元の値
ｚｊ［ｔ−２，ｔ−３］
を出力する。内部部分回路６０３の出力は、ＮＯＲゲート６０６のｍ次元の入力と接続され、ＮＯＲゲート６０６は、１ビット幅の出力を有し、この出力は、選択ユニット６０８の第２の入力と接続されている。
【０２３３】
内部部分回路６０４は、ロケータ多項式値
【数１５３】
0006336547.tif 000154
を提供し、そのｍ次元の出力で、ｍ次元の値
ｚｊ［１］
を出力する。内部部分回路６０４の出力は、ＮＯＲゲート６０７のｍ次元の入力と接続され、ＮＯＲゲート６０７は、１ビット幅の出力を有し、この出力は、選択ユニット６０８の第（ｔ＋１）／２の入力と接続されている。
【０２３４】
ビットｖ’ｊに誤りがある場合、以下のことが成り立つ：
−ｔビット誤りまたは（ｔ−１）ビット誤りがある場合、部分回路ＳＴｊのｍ個の第１の出力（これは、ここでは内部部分回路６０２の出力に対応し、それに基づいて、ロケータ多項式値
【数１５４】
0006336547.tif 000155
が提供される）で、ロケータ多項式値
ｚｊ＝ｚｊ［ｔ，ｔ−１］＝｛０｝ｍ
が出力される。
−（ｔ−２）ビット誤りまたは（ｔ−３）ビット誤りがある場合、部分回路ＳＴｊのｍ個の第２の出力（これらは、ここでは内部部分回路６０３の出力に対応し、内部部分回路６０３に基づいてロケータ多項式値
【数１５５】
0006336547.tif 000156
が提供される）で、ロケータ多項式値
ｚｊ［ｔ−２，ｔ−３］＝｛０｝ｍ
が出力される。
−これらの実施形態は、ビット誤りｔ−ｑおよびｔ−ｑ−１（ｑ＝４、６、８…）に関して、最終的に１ビット誤りに達するまで同様に続けることができる（以下の点を参照）。
−１ビット誤りがある場合、部分回路ＳＴｊのｍ個の第（ｔ＋１）／２の出力（これらは、ここでは内部部分回路６０４の出力に対応し、内部部分回路６０４に基づいてロケータ多項式値
【数１５６】
0006336547.tif 000157
が提供される）で、ロケータ多項式値
ｚｊ＝ｚｊ［１］＝｛０｝ｍ
が出力される。
【０２３５】
ビットｖ’が誤りを含まない場合、以下が成り立つ：
−ｔビット誤りまたは（ｔ−１）ビット誤りがある場合、部分回路ＳＴｊのｍ個の第１の出力（これらは、ここでは内部部分回路６０２の出力に対応し、内部部分回路６０２に基づいてロケータ多項式値
【数１５７】
0006336547.tif 000158
が提供される）で、ロケータ多項式値
ｚｊ＝ｚｊ［ｔ，ｔ−１］≠｛０｝ｍ
が出力される。
−（ｔ−２）ビット誤りまたは（ｔ−３）ビット誤りがある場合、部分回路ＳＴｊのｍ個の第２の出力（これらは、ここでは内部部分回路６０３の出力に対応し、内部部分回路６０３に基づいてロケータ多項式値
【数１５８】
0006336547.tif 000159
が提供される）で、ロケータ多項式値
ｚｊ＝ｚｊ［ｔ−２，ｔ−３］≠｛０｝ｍ
が出力される。
−これらの実施形態は、ビット誤りｔ−ｑおよびｔ−ｑ−１（ｑ＝４、６、８…）に関して、最終的に１ビット誤りに達するまで同様に続けることができる（以下の点を参照）。
−１ビット誤りがある場合、部分回路ＳＴｊのｍ個の第（ｔ＋１）／２の出力（これらは、ここでは内部部分回路６０４の出力に対応し、内部部分回路６０４に基づいてロケータ多項式値
【数１５９】
0006336547.tif 000160
が提供される）で、ロケータ多項式値
ｚｊ＝ｚｊ［１］≠｛０｝ｍ
が出力される。
【０２３６】
出現する誤りの数に応じて、選択ユニット６０８の誤り認識機能６０９によって提供される誤り信号の成分ｅｒｒの値が、選択ユニット６０８のどの入力がその出力と接続されるかを決定する。選択ユニット６０８の出力は、ＡＮＤゲート６１０の第１の入力と接続されている。ＡＮＤゲート６１０の第２の入力に、同様に誤り認識機能６０９によって提供される誤り信号の成分Ｅがある。ＡＮＤゲート６１０の出力は、場合によっては誤りのあるビットｖ’ｊに関する訂正値Δｖｊを提供する。
【０２３７】
ｔビット誤りまたは（ｔ−１）ビット誤りがある場合、選択ユニット６０８は、その第１の入力をその出力と接続し、内部部分回路６０２の出力に提供される値ｚｊ＝ｚｊ［ｔ，ｔ−１］が、Δｖｊ＝１であるかΔｖｊ＝０であるかを決定する：
−ｚｊ［ｔ，ｔ−１］＝｛０｝ｍの場合、Δｖｊ＝１である。
−ｚｊ［ｔ，ｔ−１］≠｛０｝ｍの場合、Δｖｊ＝０である。
【０２３８】
（ｔ−２）ビット誤りまたは（ｔ−３）ビット誤りがある場合、選択ユニット６０８は、その第２の入力をその出力と接続し、内部部分回路６０３の出力に提供される値ｚｊ＝ｚｊ［ｔ−２，ｔ−３］が、Δｖｊ＝１であるかΔｖｊ＝０であるかを決定する：
−ｚｊ［ｔ−２，ｔ−３］＝｛０｝ｍの場合、Δｖｊ＝１である。
−ｚｊ［ｔ−２，ｔ−３］≠｛０｝ｍの場合、Δｖｊ＝０である。
【０２３９】
同様に、後に続くビット誤りの対
｛（ｔ−５）；（ｔ−４）｝、｛（ｔ−７）；（ｔ−６）｝、…
に関しても、以下に述べる１ビット誤りまで、この考察を続けることができる。
【０２４０】
最終的に１ビット誤りがある場合、選択ユニット６０８は、その第（ｔ＋１）／２の入力をその出力と接続し、内部部分回路６０４の出力に提供される値ｚｊ＝ｚｊ［１］が、Δｖｊ＝１であるかΔｖｊ＝０であるかを決定する：
−ｚｊ［１］＝｛０｝ｍの場合、Δｖｊ＝１である。
−ｚｊ［１］≠｛０｝ｍの場合、Δｖｊ＝０である。
【０２４１】
誤りがない場合、誤り信号の成分Ｅの値はゼロ（Ｅ＝０）であり、Δｖｊ＝０が成り立つ。
【０２４２】
図７は、ｔビット誤り訂正ＢＣＨ符号を用いた訂正が行われるときの、訂正値Δｖｊを決定するためのさらなる例示的な回路構成を示す。ここで、ｔは、例として奇数である。
【０２４３】
図７は、内部部分回路７０２〜７０４を有する部分回路７０１（ビット位置ｊまたはストリングｊに関する部分回路ＳＴｊとも呼ぶ）を示す。部分回路７０１は、ｔ・ｍビット幅の入力を有し、その入力に、ｔ個の成分ｓ１、ｓ３、…、ｓ２ｔ−１を有する誤りシンドロームｓが入力される。
【０２４４】
内部部分回路７０２は、ロケータ多項式値
【数１６０】
0006336547.tif 000161
を提供し、そのｍ次元の出力で、ｍ次元の値
ｚｊ［ｔ］
を出力する。内部部分回路７０２の出力は、ＮＯＲゲート７０５のｍ次元の入力と接続され、ＮＯＲゲート７０５は、１ビット幅の出力を有し、この出力は、選択ユニット７０８の第１の入力と接続されている。
【０２４５】
内部部分回路７０３は、ロケータ多項式値
【数１６１】
0006336547.tif 000162
を提供し、そのｍ次元の出力で、ｍ次元の値
ｚｊ［ｔ−１，ｔ−２］
を出力する。内部部分回路７０３の出力は、ＮＯＲゲート７０６のｍ次元の入力と接続され、ＮＯＲゲート７０６は、１ビット幅の出力を有し、この出力は、選択ユニット７０８の第２の入力と接続されている。
【０２４６】
内部部分回路７０４は、ロケータ多項式値
【数１６２】
0006336547.tif 000163
を提供し、そのｍ次元の出力で、ｍ次元の値
ｚｊ［２，１］
を出力する。内部部分回路７０４の出力は、ＮＯＲゲート７０７のｍ次元の入力と接続され、ＮＯＲゲート７０７は、１ビット幅の出力を有し、この出力は、選択ユニット７０８の第（ｔ＋１）／２の入力と接続されている。
【０２４７】
出現する誤りの数に応じて、選択ユニット７０８の誤り認識機能７０９によって提供される誤り信号の成分ｅｒｒの値が、選択ユニット７０８のどの入力がその出力と接続されるかを決定する。選択ユニット７０８の出力は、ＡＮＤゲート７１０の第１の入力と接続されている。ＡＮＤゲート７１０の第２の入力に、同様に誤り認識機能７０９によって提供される誤り信号の成分Ｅがある。ＡＮＤゲート７１０の出力は、場合によっては誤りのあるビットｖ’ｊに関する訂正値Δｖｊを提供する。
【０２４８】
ｔビット誤りがある場合、選択ユニット７０８は、その第１の入力をその出力と接続し、内部部分回路７０２の出力に提供される値ｚｊ＝ｚｊ［ｔ］が、Δｖｊ＝１であるかΔｖｊ＝０であるかを決定する：
−ｚｊ［ｔ］＝｛０｝ｍの場合、Δｖｊ＝１である。
−ｚｊ［ｔ］≠｛０｝ｍの場合、Δｖｊ＝０である。
【０２４９】
（ｔ−１）ビット誤りまたは（ｔ−２）ビット誤りがある場合、選択ユニット７０８は、その第２の入力をその出力と接続し、内部部分回路７０３の出力に提供される値ｚｊ＝ｚｊ［ｔ−１，ｔ−２］が、Δｖｊ＝１であるかΔｖｊ＝０であるかを決定する：
−ｚｊ［ｔ−１，ｔ−２］＝｛０｝ｍの場合、Δｖｊ＝１である。
−ｚｊ［ｔ−１，ｔ−２］≠｛０｝ｍの場合、Δｖｊ＝０である。
【０２５０】
同様に、後に続くビット誤りの対
｛（ｔ−４）；（ｔ−３）｝、｛（ｔ−６）；（ｔ−５）｝、…
に関しても、以下に述べる２ビット誤りと１ビット誤りとの対まで、この考察を続けることができる。
【０２５１】
最終的に２ビット誤りまたは１ビット誤りがある場合、選択ユニット６０８は、その第（ｔ＋１）／２の入力をその出力と接続し、内部部分回路７０４の出力に提供される値ｚｊ＝ｚｊ［２，１］が、Δｖｊ＝１であるかΔｖｊ＝０であるかを決定する：
−ｚｊ［２，１］＝｛０｝ｍの場合、Δｖｊ＝１である。
−ｚｊ［２，１］≠｛０｝ｍの場合、Δｖｊ＝０である。
【０２５２】
誤りがない場合、誤り信号の成分Ｅの値はゼロ（Ｅ＝０）であり、Δｖｊ＝０が成り立つ。
【０２５３】
内部部分回路によってロケータ多項式値
【数１６３】
0006336547.tif 000164
（ｒ＝ｔ−１、ｔ−３、…）に関して出力された値は、ｒビット誤りおよび（ｒ−１）ビット誤りに関して、Δｖｊ＝１であるかΔｖｊ＝０であるかを決定するが、例えば、内部部分回路によってロケータ多項式値
【数１６４】
0006336547.tif 000165
に関して出力された値は、ｔビット誤りの場合にのみ、Δｖｊ＝１であるかΔｖｊ＝０であるかを決定する。
【０２５４】
図８ａは、ｐビット幅の入力８０２およびｎビット幅の入力８０３を有するシンドローム発生器８０１を示す。入力８０２には、場合によっては誤りのある読出しアドレスａ’（アドレスビット）が入り、入力８０３には、場合によって誤りのあるデータビットおよび検査ビットｖ’１、…、ｖ’ｎが入る。さらに、シンドローム発生器８０１は出力８０４を有し、出力８０４には、ｔ個の成分ｓ１、ｓ３、…、ｓ２ｔ−１を有する誤りシンドロームｓが提供される。
【０２５５】
ここで、アドレスビット、データビット、および検査ビットは、誤りを含まない場合には、ｔビット誤り訂正符号の符号語を生成する。
【０２５６】
図８ｂは、ｇビット幅の入力８１２およびｎビット幅の入力８１３を有するシンドローム発生器８１１を示す。
【０２５７】
場合によっては誤りのある読出しアドレスのビットａ’（アドレスビット）は、ユニット８１５によって、アドレスビットから導出されたビットＡ’＝Ａ’１、…、Ａ’ｇに変換され、ここで、ユニット８１５は、関係Ａ’＝ｆ（ａ’）を提供する。
【０２５８】
入力８１３に、場合によっては誤りのあるデータビットおよび検査ビットｖ’１、…、ｖ’ｎが入る。さらに、シンドローム発生器８１１は出力８１４を有し、出力８１４に、ｔ個の成分ｓ１、ｓ３、…、ｓ２ｔ−１を有する誤りシンドロームｓが提供される。
【０２５９】
その際、アドレスビットａ’から導出されたビットＡ’、ならびにデータビットおよび検査ビットは、誤りを含まない場合には、考察中のｔビット誤り訂正符号の符号語を生成する。
【０２６０】
ユニット８１５によって提供される関数ｆが、ｐビット幅の、場合によっては誤りのある読出しアドレスのｐビットａ’１、…、ａ’ｐを生成して、読出しアドレスから導出されるｇ個のビットＡ’１、…、Ａ’ｇとする。ここで、ｐは、読出しアドレスのワード幅であり、ｇ≧１が成り立つ。
【０２６１】
例えばｇ＝１の場合、読出しアドレスのｐビットから、導出されたビットとしてこれらのビットのパリティを決定することが可能であり、それにより
Ａ’１＝ｆ（ａ’１，…，ａ’ｐ）＝ａ’１＋ａ’２＋…＋ａ’ｐ
が成り立つ。
【０２６２】
以下、例として、ここで提示した解決策の回路部分を述べる。この例では、ｍ＝５が選択され、したがって、根底にあるガロア域ＧＦ（２ｍ）＝ＧＦ（２５）＝ＧＦ（３２）である。
【０２６３】
図１０に、ガロア域ＧＦ（３２）の要素が、その様々な表現形態で表されている。ガロア域ＧＦ（３２）のモジュラ多項式は、多項式
ｍ（ｘ）＝１＋ｘ２＋ｘ５
である。
【０２６４】
図１０に示される表の第１の列に、ガロア域の３２個の要素が、ｉ＝０、…、３０に関してそれらの冪表現αｉで含まれている。冪表現は、冪指数表現または指数表現と呼ぶこともできる。
【０２６５】
第１の列の第１の行での要素０は、冪表現を有さない。ここで、αは、ガロア域の原始元である。この表の第２の列には、ガロア域の３２個の要素が、モジュラ多項式ｍ（ｘ）＝１＋ｘ２＋ｘ５に関してそれらの多項式表現で表されており、第３の列には、タプルまたはベクトル表現が表されている。ベクトル表現の５つの成分は、多項式表現の冪の５つの係数ｘ０、ｘ１、ｘ２、ｘ３、ｘ４に対応する。したがって、例えば、テーブルの第９の行での多項式ｘ２＋ｘ４がベクトル表現００１０１に対応する。
【０２６６】
対応する多項式表現は、
ｘｊｍｏｄｕｌｏ（１＋ｘ２＋ｘ５）
を決定することによって、冪表現αｊから得られる。
【０２６７】
したがって、
ｘ５ｍｏｄｕｌｏ（１＋ｘ２＋ｘ５）＝１＋ｘ２
が成り立つので、α５の多項式表現は、１＋ｘ２である。それに対応して、図１０に示される表に示されるように、多項式表現は、
−α６については、ｘ＋ｘ３、
−α７については、ｘ２＋ｘ４、および
−α８については、（ｘ３＋ｘ５）ｍｏｄｕｌｏ（１＋ｘ２＋ｘ５）＝１＋ｘ２＋ｘ３
である。
【０２６８】
ガロア域の２つの要素の乗算は、冪指数表現または多項式表現で行うことができる。
【０２６９】
冪指数表現でのガロア域ＧＦ（２５）の２つの要素αｉおよびαｊが与えられる場合、その積
αｉ・αｊ＝αｋ（ｋ＝（ｉ＋ｊ））ｍｏｄｕｌｏ（２ｍ−１）＝（ｉ＋ｊ）ｍｏｄｕｌｏ（３１）である。
【０２７０】
ガロア域の乗算対象の要素がそれらのベクトル表現またはそれらの多項式表現である場合、ガロア域乗算器を用いてその乗算を行うことができ、ここで、ガロア域乗算器は、乗算器とも呼ばれる。
【０２７１】
以下、２つの要素の乗算を多項式表現で説明する。
【０２７２】
２つの要素を互いに乗算するために、ガロア域ＧＦ（２ｍ）＝ＧＦ（２５）の要素がそれらの多項式表現で与えられる場合、多項式を直接互いに乗算すべきであり、結果は、モジュラ多項式の剰余演算で求めることができる：例えば、多項式１＋ｘ２＋ｘ３およびｘ＋ｘ３が与えられる場合、その直接の乗算
（１＋ｘ２＋ｘ３）（ｘ＋ｘ３）＝ｘ＋ｘ４＋ｘ５＋ｘ６
が得られる。
【０２７３】
ｘ５＝１＋ｘ２ｍｏｄｕｌｏ（１＋ｘ２＋ｘ５）
および
ｘ６＝ｘ＋ｘ３ｍｏｄｕｌｏ（１＋ｘ２＋ｘ５）
により、
ｘ＋ｘ４＋ｘ５＋ｘ６＝ｘ＋ｘ４＋１＋ｘ２＋ｘ＋ｘ３＝１＋ｘ２＋ｘ３＋ｘ４
が得られる。
【０２７４】
したがって、結果として以下が成り立つ：
（１＋ｘ２＋ｘ３）・（ｘ＋ｘ３）＝１＋ｘ２＋ｘ３＋ｘ４
【０２７５】
以下、
ａ（ｘ）＝ａ４ｘ４＋ａ３ｘ３＋ａ２ｘ２＋ａ１ｘ＋ａ０
での第１の要素ａ（ｘ）と、
ｂ（ｘ）＝ｂ４ｘ４＋ｂ３ｘ３＋ｂ２ｘ２＋ｂ１ｘ＋ｂ０
での第２の要素ｂ（ｘ）とが、モジュラ多項式
ｍ（ｘ）＝ｘ５＋ｘ２＋１
を有するガロア域ＧＦ（２５）で乗算される場合を述べる。まず、多項式ａ（ｘ）とｂ（ｘ）との直接の乗算により、８次の多項式が得られる。
ｘ５ｍｏｄｕｌｏ（１＋ｘ２＋ｘ５）＝１＋ｘ２、
ｘ６ｍｏｄｕｌｏ（１＋ｘ２＋ｘ５）＝ｘ＋ｘ３、
ｘ７ｍｏｄｕｌｏ（１＋ｘ２＋ｘ５）＝ｘ２＋ｘ４、
ｘ８ｍｏｄｕｌｏ（１＋ｘ２＋ｘ５）＝１＋ｘ２＋ｘ３
により、４次の多項式が以下のように得られる：
ｃ４ｘ４＋ｃ３ｘ３＋ｃ２ｘ２＋ｃ１ｘ１＋ｃ０＝ａ（ｘ）・ｂ（ｘ）  ｍｏｄ  ｍ（ｘ）＝
＝（ａ０ｂ４＋ａ１ｂ３＋ａ２ｂ２＋ａ３ｂ１＋ａ３ｂ４＋ａ４ｂ０＋ａ４ｂ３）・ｘ４＋
＋（ａ０ｂ３＋ａ１ｂ２＋ａ２ｂ１＋ａ２ｂ４＋ａ３ｂ０＋ａ３ｂ３＋ａ４ｂ２＋ａ４ｂ４）・ｘ３＋
＋（ａ０ｂ２＋ａ１ｂ１＋ａ１ｂ４＋ａ２ｂ０＋ａ２ｂ３＋ａ３ｂ２＋ａ３ｂ４＋ａ４ｂ１＋ａ４ｂ３＋ａ４ｂ４）・ｘ２＋
＋（ａ０ｂ１＋ａ１ｂ０＋ａ２ｂ４＋ａ３ｂ３＋ａ４ｂ２）・ｘ１＋
＋（ａ０ｂ０＋ａ１ｂ４＋ａ２ｂ３＋ａ３ｂ２＋ａ４ｂ１＋ａ４ｂ４）
【０２７６】
この関係は、５つの第１の２進入力、５つの第２の２進入力、および５つの２進出力を有するガロア域乗算器によって実現される。これは、以下により詳細に説明する。
【０２７７】
ガロア域乗算器の第１の５つの入力に、２進値ａ０、ａ１、ａ２、ａ３、ａ４が入力され、第２の５つの入力に、２進値ｂ０、ｂ１、ｂ２、ｂ３、ｂ４が入力され、一方、５つの２進出力では、値ｃ０、ｃ１、ｃ２、ｃ３、ｃ４が、
（ａ０ｂ０＋ａ１ｂ４＋ａ２ｂ３＋ａ３ｂ２＋ａ４ｂ１＋ａ４ｂ４）＝ｃ０      （４４）
（ａ０ｂ１＋ａ１ｂ０＋ａ２ｂ４＋ａ３ｂ３＋ａ４ｂ２）＝ｃ１      （４５）
（ａ０ｂ２＋ａ１ｂ１＋ａ１ｂ４＋ａ２ｂ０＋ａ２ｂ３＋ａ３ｂ２＋ａ３ｂ４＋ａ４ｂ１＋ａ４ｂ３＋ａ４ｂ４）＝ｃ２      （４６）
（ａ０ｂ３＋ａ１ｂ２＋ａ２ｂ１＋ａ２ｂ４＋ａ３ｂ０＋ａ３ｂ３＋ａ４ｂ２＋ａ４ｂ４）＝ｃ３      （４７）
（ａ０ｂ４＋ａ１ｂ３＋ａ２ｂ２＋ａ３ｂ１＋ａ３ｂ４＋ａ４ｂ０＋ａ４ｂ３）＝ｃ４      （４８）
として出力される。ここで、シンボル「＋」は、モジュロ２加算（ＸＯＲ演算）を示す。
【０２７８】
方程式（４４）〜（４８）の実装は、ガロア域乗算器によって行うことができる。例えば、実装の枠組みで合成ツールを使用することもできる。
【０２７９】
ガロア域の要素が２乗される場合、その要素をそれ自体と乗算することができる。多項式表現で、要素が、多項式
ａ（ｘ）＝ａ０＋ａ１ｘ１＋ａ２ｘ２＋ａ３ｘ３＋ａ４ｘ４
として与えられる場合、
（ａ（ｘ））２  ｍｏｄ  ｍ（ｘ）＝
＝［ａ０＋ａ１ｘ２＋ａ２ｘ４＋ａ３ｘ６＋ａ４ｘ８］ｍｏｄ（１＋ｘ２＋ｘ５）＝
＝（ａ２）ｘ４＋（ａ３＋ａ４）ｘ３＋（ａ１＋ａ４）ｘ２＋ａ３ｘ１＋（ａ０＋ａ４）
が成り立つ。
【０２８０】
ガロア域ＧＦ（２５）での要素の２乗は、それに対応して、５つの２進入力および５つの２進出力を有する２乗器によって実現することができる。５つの２進入力に、２進値ａ０、ａ１、ａ２、ａ３、ａ４が供給され、５つの２進出力に、２進値ｄ０、ｄ１、ｄ２、ｄ３、ｄ４が提供される。ここで、
ａ０＋ａ４＝ｄ０      （４９）
ａ３＝ｄ１      （５０）
ａ１＋ａ４＝ｄ２      （５１）
ａ３＋ａ４＝ｄ３      （５２）
ａ２＝ｄ４      （５３）
が成り立ち、ここで、シンボル「＋」は、やはりモジュロ２加算（ＸＯＲ演算）を表す。
【０２８１】
モジュラ多項式ｍ（ｘ）＝１＋ｘ２＋ｘ５を有するガロア域ＧＦ（２５）で２乗器を実現するために、例えばＸＯＲゲートによって方程式（４９）〜（５３）を実装することができる。
【０２８２】
ガロア域ＧＦ（２５）の例で、多項式表現で表される要素の３次の冪をどのように決定することができるかを述べる。
【０２８３】
多項式
ａ（ｘ）＝ａ０＋ａ１ｘ１＋ａ２ｘ２＋ａ３ｘ３＋ａ４ｘ４
の３次の冪（ａ（ｘ））３が、モジュラ多項式ｍ（ｘ）＝１＋ｘ２＋ｘ５の剰余演算で求められる場合、以下が成り立つ。
（ａ（ｘ））３  ｍｏｄ  ｍ（ｘ）＝
＝（ａ０ａ２＋ａ０ａ４＋ａ１ａ２＋ａ１ａ３＋ａ１ａ４＋ａ２ａ３＋ａ２ａ４＋ａ３＋ａ３ａ４）・ｘ４＋
＋（ａ０ａ４＋ａ１＋ａ２＋ａ２ａ３＋ａ２ａ４＋ａ３＋ａ４）・ｘ３＋
＋（ａ０ａ１＋ａ０ａ２＋ａ０ａ４＋ａ１ａ２＋ａ２ａ４＋ａ３ａ４＋ａ４）・ｘ２＋
＋（ａ０ａ１＋ａ０ａ３＋ａ２＋ａ３＋ａ３ａ４＋ａ４）・ｘ１＋
＋（ａ０＋ａ０ａ４＋ａ１ａ２＋ａ１ａ３＋ａ２ａ３）
【０２８４】
ガロア域ＧＦ（２５）での要素の３次の冪の生成は、それに対応して、５つの２進入力および５つの２進出力を有する３乗冪生成器によって実現することができる。５つの２進入力に、２進値ａ０、ａ１、ａ２、ａ３、ａ４が供給され、５つの２進出力に、２進値ｆ０、ｆ１、ｆ２、ｆ３、ｆ４が提供される。以下が成り立つ：
ｆ０＝ａ０＋ａ０ａ４＋ａ１ａ２＋ａ１ａ３＋ａ２ａ３      （５４）
ｆ１＝ａ０ａ１＋ａ０ａ３＋ａ２＋ａ３＋ａ３ａ４＋ａ４      （５５）
ｆ２＝ａ０ａ１＋ａ０ａ２＋ａ０ａ４＋ａ１ａ２＋ａ２ａ４＋ａ３ａ４＋ａ４      （５６）
ｆ３＝ａ０ａ４＋ａ１＋ａ２＋ａ２ａ３＋ａ２ａ４＋ａ３＋ａ４      （５７）
ｆ４＝ａ０ａ２＋ａ０ａ４＋ａ１ａ２＋ａ１ａ３＋ａ１ａ４＋ａ２ａ３＋ａ２ａ４＋ａ３＋ａ３ａ４      （５８）
【０２８５】
例として、モジュラ多項式ｍ（ｘ）＝１＋ｘ２＋ｘ５を有するガロア域ＧＦ（２５）でのこの例では、単に方程式（５４）〜（５８）が実装されることによって、３乗冪生成器を実現することができる。
【０２８６】
代替として、３乗冪生成器は、２乗器およびその下流に接続されたガロア域乗算器から実現することができる。また、要素ａ（ｘ）のより高次の冪も、それに対応する様式で、適切な構成要素を使用して実現される。
【０２８７】
また、反転器が使用される例示的実施形態も提供することができる。図１１は、ガロア域ＧＦ（２５）に関する反転器の値表を有する例示的な表を示す。
【０２８８】
図１１に示される表の第１の列には、冪指数表現でのガロア域ＧＦ（２５）の２５−１個の値αｉ（ｉ＝０、…、３０）全てが示されている。ガロア域の「０」要素は記載されていない。これは反転要素を有さない。
【０２８９】
第２の列は、第１の列に表される要素を、そのタプル表現で、２進５タプルとして含む。このタプル表現は、図１０に示される表にも含まれている。
【０２９０】
第３の列は、第１の列に表される要素の反転要素をその冪指数表現で含み、第４の列は、第３の列に表される反転要素を、２進５タプルの形態でのそのタプル表現で含む。
【０２９１】
第１の列に表される要素と、それに対応する第３の列の反転要素とを乗算する場合、α０＝１が得られる。要素および関連の反転要素の冪指数の和に関して、そのモジュロ３１演算が０であることが成り立つ。それに対応して、反転要素の冪指数は、図１１に示される表の第１の列の要素と第３の列の要素の冪指数からの和が３１である、または表の第１の行に従って０であるように決定することができる。
【０２９２】
例えば、図１１に示される表の第１０の行に関して以下が成り立つ。要素α９に、反転要素α２２が割り当てられる；２つの要素の冪指数に関して、２２＋９＝３１が成り立つ。
【０２９３】
例えば、図１１に示される表の第１の行に関して以下が成り立つ。要素α０に、反転要素α０が割り当てられる；２つの要素の冪指数に関して、０＋０＝０が成り立つ。
【０２９４】
反転器の入力値および出力値が、それぞれのタプル表現で５タプルとして表される場合、第２の列の５タプルが、それに対応する第４の列の５タプルに割り当てられることによって、反転器の２進的実現のための値表が得られる。ここで、第２の列の５タプルが反転器の入力値であり、第４の列の５タプルが出力値である。
【０２９５】
したがって、例えば、図１１に示される表の第１０の行での入力タプル０１０１１に、出力タプル１０１０１が割り当てられる。
【０２９６】
以下、ガロア域ＧＦ（２ｍ）での（定数）乗算器の実装を、例としてｍ＝５に関して述べる。モジュラ多項式は、
ｍ（ｘ）＝１＋ｘ２＋ｘ５
である。
【０２９７】
ａ∈ＧＦ（２５）は、以下の多項式表現
ａ（ｘ）＝ａ０＋ａ１ｘ＋ａ２ｘ２＋ａ３ｘ３＋ａ４ｘ４      （５９）
を有するガロア域の任意の要素であるものとする。
【０２９８】
乗算すべき定数として例えばα９が選択され、その多項式表現は、図１０に示される表に従って、
α９（ｘ）＝ｘ＋ｘ３＋ｘ４      （６０）
によって与えられる。乗算として、
ａ（ｘ）・α９（ｘ）ｍｏｄｕｌｏ（１＋ｘ２＋ｘ５）＝ｂ０＋ｂ１ｘ＋ｂ２ｘ２＋ｂ３ｘ３＋ｂ４ｘ４      （６１）
が得られ、ここで、
ｂ０＝ａ１＋ａ２          （６２）
ｂ１＝ａ０＋ａ２＋ａ３      （６３）
ｂ２＝ａ２＋ａ３＋ａ４      （６４）
ｂ３＝ａ０＋ａ３＋ａ４      （６５）
ｂ４＝ａ０＋ａ１＋ａ４      （６６）
である。
【０２９９】
出力値ｂ０、…、ｂ４が、入力値ａ０、…、ａ４から、方程式（６２）〜（６６）で表される関係に対応して導出され、それにより、出力値は、ＸＯＲ演算によって入力値から決定される。ここで、シンボル「＋」は、モジュロ２加算（ＸＯＲ演算）を示す。それに対応して、乗算器は、ＸＯＲゲートによって実現することができる。
【０３００】
図９は、図３からのユニット３０６の例示的な実現を示し、ユニット３０６は、その４つのｍビット幅の入力に入力される部分シンドロームｓ１、ｓ３、ｓ５、およびｓ７に依存して、４次のロケータ多項式Ｌ４（ｘ）の係数σ２４を
【数１６５】
0006336547.tif 000166
として決定し、そのｍビット幅の出力に提供する。
【０３０１】
図９に示される回路構成は、ガロア域ＧＦ（２ｍ）の要素の加算、２乗、乗算、および反転のために使用される構成要素を有する。したがって、ユニット３０６は、それぞれ１つのｍビット幅の入力および１つのｍビット幅の出力を有する（ガロア域）２乗器９０１および９０３と、それぞれ２つのｍビット幅の入力および１つのｍビット幅の出力を有する（ガロア域）乗算器９０２、９０４、９０５、９０９、９１０、９１１、９１２、および９１６と、それぞれ２つのｍビット幅の入力および１つのｍビット幅の出力を有する（ガロア域）加算器（例えば、それぞれ２つの入力および１つの出力を有するｍ個のＸＯＲゲートから実現することができる）９０６、９０７、９０８、９１３、９１４と、１つのｍビット幅の入力および１つのｍビット幅の出力を有する（ガロア域）反転器９１５とを含む。
【０３０２】
回路構成は、４つのｍビット幅の入力９３１〜９３４を有し、ここで、入力９３１に部分シンドロームｓ１が入力され、入力９３２に部分シンドロームｓ３が入力され、入力９３３に部分シンドロームｓ５が入力され、入力９３４に部分シンドロームｓ７が入力される。これらは、（図９に示されていない）シンドローム発生器１０１によって提供される。
【０３０３】
入力９３１は、部分シンドロームｓ１の値を、２乗器９０１の入力、乗算器９１２の第１の入力、乗算器９０２の第１の入力、乗算器９０４の第１の入力、および乗算器９０９の第１の入力に提供する。
２乗器９０１の出力は、値
【数１６６】
0006336547.tif 000167
を提供し、２乗器９０３の入力および乗算器９０２の第２の入力と接続される。
【０３０４】
乗算器９０２の出力は、値
【数１６７】
0006336547.tif 000168
を乗算器９０５の第１の入力およびＸＯＲゲート９０７の第１の入力に提供する。
【０３０５】
２乗器９０３の出力は、乗算器９０５の第２の入力および乗算器９０４の第２の入力と接続され、それらに値
【数１６８】
0006336547.tif 000169
を提供する。
【０３０６】
乗算器９０４の出力は、ＸＯＲゲート９０６の第１の入力と接続され、そこに値
【数１６９】
0006336547.tif 000170
を供給する。ＸＯＲゲート９０６の第２の入力は、入力９３３と接続され、入力９３３に部分シンドロームｓ５が入力される。
【０３０７】
乗算器９０５の出力は、値
【数１７０】
0006336547.tif 000171
をＸＯＲゲート９０８の第１の入力に伝送する。ＸＯＲゲート９０８の第２の入力が、入力９３４と接続され、入力９３４に部分シンドローム７が入力される。
【０３０８】
ＸＯＲゲート９０８の出力は、値
【数１７１】
0006336547.tif 000172
を乗算器９１２の第２の入力に送る。乗算器９１２の出力は、
【数１７２】
0006336547.tif 000173
をＸＯＲゲート９１４の第１の入力に伝送する。
【０３０９】
入力９３２は、部分シンドロームｓ３を提供し、ＸＯＲゲート９０７の第２の入力、乗算器９１１の第１の入力、および乗算器９１０の第１の入力と接続されている。
【０３１０】
ＸＯＲゲート９０６の出力が、値
【数１７３】
0006336547.tif 000174
を有し、乗算器９１０の第２の入力および乗算器９０９の第２の入力と接続されている。
【０３１１】
乗算器９１０の出力は、ＸＯＲゲート９１４の第２の入力と接続されている。ＸＯＲゲート９１４の出力は、信号
【数１７４】
0006336547.tif 000175
を有し、乗算器９１６の第１の入力と接続されている。
【０３１２】
ＸＯＲゲート９０７の出力は、値
【数１７５】
0006336547.tif 000176
を乗算器９１１の第２の入力に伝送する。乗算器９１１の出力は、ＸＯＲゲート９１３の第１の入力と接続されている。
【０３１３】
乗算器９０９の出力は、値
【数１７６】
0006336547.tif 000177
をＸＯＲゲート９１３の第２の入力に伝送する。ＸＯＲゲート９１３の出力は、値
【数１７７】
0006336547.tif 000178
を送り、反転器９１５の入力と接続されている。
【０３１４】
反転器は、ここで、原始元αを有するガロア域ＧＦ（２ｍ）に関して、その入力に入力される要素αｉ（ｉ＝｛０，１，…，２ｍ−２｝）に関して、反転要素α−ｉをその出力に提供するように構成され、したがって、αｉ・α−ｉ＝α０＝１が成り立つ。
【０３１５】
値
【数１７８】
0006336547.tif 000179
を有する反転器の出力は、乗算器９１６の第２の入力と接続されている。乗算器９１６の出力で、係数
【数１７９】
0006336547.tif 000180
が出力される。
【符号の説明】
【０３１６】
１０１  シンドローム発生器
１０２、１０３  部分回路
１０４〜１０７  内部部分回路
１０８〜１１１  ＮＯＲゲート
１１２、１１３  選択ユニット
１１４、１１５  ＡＮＤゲート
１１６  誤り認識ユニット
１１７  演算回路
１１８、１１９  ＸＯＲゲート
２０１  シンドローム発生器
２０２、２０３  部分回路
２０４〜２０９  内部部分回路
２１０、２１１  選択ユニット
２１２〜２１５  ＯＲゲート
２１６  誤り認識ユニット
２１７  演算回路
２１８、２１９  ＸＮＯＲゲート
３０２  中央回路部分
３０３、３０４  ローカル回路部分
３０５〜３０８  ユニット
３０９〜３１１  乗算器
３１２  ＸＯＲゲート
３１３〜３１５  乗算器
３１６  ＸＯＲゲート
４０１  中央回路部分
４０２  ローカル回路部分
４０３、４０４  ユニット
４０５、４０６  乗算器
４０７、４０８  ＸＯＲゲート
５０１  部分回路
５０２〜５０４  内部部分回路
５０５〜５０７  ＮＯＲゲート
５０８  選択ユニット
５０９  誤り認識機能
５１０  ＡＮＤゲート
６０１  部分回路
６０２〜６０４  内部部分回路
６０５〜６０７  ＮＯＲゲート
６０８  選択ユニット
６０９  誤り認識機能
６１０  ＡＮＤゲート
７０１  部分回路
７０２〜７０４  内部部分回路
７０５〜７０７  ＮＯＲゲート
７０８  選択ユニット
７０９  誤り認識機能
７１０  ＡＮＤゲート
８０１、８１１  シンドローム発生器
８０２、８０３、８１２、８１３  入力
８０４、８１４  出力
８１５  ユニット
９３１〜９３４  入力
９０１、９０３  ２乗器
９０２、９０４、９０５、９０９〜９１２、９１６  乗算器
９０６〜９０８、９１３、９１４  ＸＯＲゲート
９１５  反転器
ＳＴ  部分回路
ｅｒｒ、Ｅ  誤り信号
【図１】
0006336547.tif 000181
【図２】
0006336547.tif 000182
【図３】
0006336547.tif 000183
【図４】
0006336547.tif 000184
【図５】
0006336547.tif 000185
【図６】
0006336547.tif 000186
【図７】
0006336547.tif 000187
【図８】
0006336547.tif 000188
【図９】
0006336547.tif 000189
【図１０】
0006336547.tif 000190
【図１１】
0006336547.tif 000191