(57)【要約】【課題】回路規模を抑えつつ検出可能なエラービット数を増加させる。【解決手段】入力ビット列に対して第１の誤り訂正符号演算を行う第１の演算部と、第１の誤り訂正符号演算の演算結果を含む第１のビット列のパリティビットを取得するパリティ演算部と、第１のビット列に対して、第２の誤り訂正符号演算を行う第２の演算部と、第２の誤り訂正符号演算の演算結果と、多くともＮ（Ｎ＞０の整数）のエラービット数及びエラー位置と、の対応付けに基づいて、第１のビット列における多くともＮのエラービット数及びエラー位置を特定する特定部と、第１のビット列に対してパリティチェックを行うパリティチェック部と、特定された第１のビット列におけるエラービット数がＮビットであり、且つ、パリティチェックの結果がエラー有りである場合に、第１のビット列においてＮ＋１ビットのエラーを検出する制御部と、を備えるデータ処理システムである。【選択図】図４
2018074545.tif 000002
【特許請求の範囲】
【請求項１】
入力ビット列に対して第１の誤り訂正符号演算を行う第１の演算部と、
前記第１の誤り訂正符号演算の結果を含む第１のビット列のパリティビットを取得するパリティ演算部と、
前記第１のビット列に対して、第２の誤り訂正符号演算を行う第２の演算部と、
前記第２の誤り訂正符号演算の演算結果と、多くともＮ（Ｎ＞０の整数）のエラービット数及びエラー位置と、の対応付けに基づいて、前記第１のビット列に対する前記第２の誤り訂正符号演算の演算結果から、前記第１のビット列における多くともＮのエラービット数及びエラー位置を特定する特定部と、
前記第１のビット列に付加されている前記パリティビットを用いて、前記第１のビット列に対してパリティチェックを行うパリティチェック部と、
前記特定部によって特定された前記第１のビット列におけるエラービット数がＮビットであり、且つ、前記パリティチェックの結果がエラー有りである場合に、前記第１のビット列においてＮ＋１ビットのエラーを検出する制御部と、
を備えるデータ処理システム。
【請求項２】
前記制御部は、前記特定部によって特定された前記第１のビット列におけるエラービット数がＮビットであり、且つ、前記パリティチェックの結果がエラーなしである場合に、前記第１のビット列においてＮビットのエラーを検出する、
請求項１に記載のデータ処理システム。
【請求項３】
所定のビット列に対する第１の誤り訂正符号演算の演算結果を含む第１のビット列に対して、第２の誤り訂正符号演算を行う演算部と、
前記第２の誤り訂正符号演算の演算結果と、多くともＮ（Ｎ＞０の整数）のエラービット数及びエラー位置と、の対応付けに基づいて、前記第１のビット列に対する前記第２の誤り訂正符号演算の演算結果から、前記第１のビット列における多くともＮのエラービット数及びエラー位置を特定する特定部と、
前記第１のビット列に付加されているパリティビットを用いて、前記第１のビット列に対してパリティチェックを行うパリティチェック部と、
前記特定部によって特定された前記第１のビット列におけるエラービット数がＮビットであり、且つ、前記パリティチェックの結果がエラー有りである場合に、前記第１のビット列においてＮ＋１ビットのエラーを検出する制御部と、
を備えるデータ処理装置。
【請求項４】
入力ビット列に対して、第１の多項式を用いる第１の誤り訂正符号演算を行う第１の演算部と、
前記入力ビット列に前記第１の誤り訂正符号演算の結果が付加された第１のビット列のパリティビットを取得するパリティ演算部と、
前記第１のビット列が書き込まれるメモリと、
前記メモリから読み出された前記第１のビット列に対して、第２の多項式及び第３の多項式を用いた第２の誤り訂正符号演算を行う第２の演算部と、
前記第２の誤り訂正符号演算の演算結果に基づいて、前記メモリから読み出された前記第１のビット列におけるエラービット数及びエラー位置を特定する特定部と、
前記メモリから読み出された前記第１のビット列に付加されている前記パリティビットを用いて、前記メモリから読み出された前記第１のビット列に対してパリティチェックを行うパリティチェック部と、
前記エラービット数がＮビットであり、且つ、前記パリティチェックの結果がエラー有りである場合に、前記第１のビット列においてＮ＋１ビットのエラーを検出する制御部と、
を備えるデータ処理装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ビットエラーの検出を行うデータ処理システム及びデータ処理装置に関する。
【背景技術】
【０００２】
インターネットトラフィックの増加により、ネットワーク伝送装置の伝送速度の高速化及び伝送データ量の大容量化が進んでいる。一方で、保守及び運用の面では、伝送装置の小型化及び低電圧化が求められる。そのため、ネットワーク伝送装置に搭載されるＬＳＩ（Large-Scale Integration）、ＦＰＧＡ（Field-Programmable Gate Array）の開発においては、プロセスの微細化が進められている。プロセスの微細化とは、ＬＳＩ、ＦＰＧＡに搭載されるトランジスタのゲートの幅又は間隔、又は、配線の幅又は間隔等を小さくすることをいう。
【０００３】
プロセスの微細化が進むことによって、ＬＳＩ、ＦＰＧＡの内部に実装されるＲＡＭ（Random Access Memory）に関して、ビットエラー等のソフトエラーの発生確率が上昇する。ＲＡＭにおけるソフトエラーが原因で、システムの動作不良等が引き起こされることがある。また、ビットエラーは、信号の伝送途中でも雑音等の影響により発生する。ビットエラーの検出及び訂正には、例えば、誤り訂正符号が用いられる。ビットエラーの検出及び訂正に用いられる誤り訂正符号の一例には、ハミング符号、ＢＣＨ符号がある。
【０００４】
誤り訂正符号を用いたエラー検出及びエラー訂正では、誤り符号を生成する符号生成処理、誤り符号によりエラー検出及び訂正を行う符号チェック処理が行われる。例えば、ハミング符号やＢＣＨ符号が用いられる符号生成処理では、入力されたデジタル信号のデータ（ビット列）に対して、所定の多項式を使用した演算が行われる。本明細書において、所定の多項式を使用した演算の演算結果として得られるデータを、符号語と称する。入力ビット列と符号語とが、例えば、一次記憶メモリ（ＲＡＭ）に格納されたり、ネットワークに送信されたりした場合に、ビットエラーが発生することがある。
【０００５】
ハミング符号やＢＣＨ符号を用いた符号チェック処理では、一時記憶メモリ（ＲＡＭ）から読み出された又はネットワークから受信した入力ビット列と符号語に対して、再び所定の多項式を使用した演算が行われる。このとき使用される多項式は、入力ビット列に対して用いられる多項式と所定の関係にある多項式である。演算結果として得られるデータはシンドロームと呼ばれる。シンドロームによって、エラーの有無、及び、エラーの位置が示される。
【０００６】
ハミング符号演算、ＢＣＨ符号演算によって特定された位置のビットを反転させてエラーを訂正することで、ＲＡＭにおいて発生するソフトエラーや伝送の雑音による影響を低減することができる。ハミング符号演算では、１ビットのエラーを検出でき、当該１ビットのエラーを訂正することができる。ＢＣＨ符号演算では、２ビット以上のエラーを検出でき、当該２ビット以上のエラーを訂正することができる。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】特開昭６１−１３９８４６号公報
【特許文献２】国際公開第１９９６／０３８９２２号
【発明の概要】
【発明が解決しようとする課題】
【０００８】
しかしながら、エラー検出可能なビット数が増えると、多項式の数、シンドロームからエラー位置を特定するために用いられるテーブルの数等が増え、回路規模が増大してしまう、という問題がある。
【０００９】
本発明は、回路規模を抑えつつ検出可能なエラービット数を増加可能なデータ処理システム及びデータ処理装置を提供することを目的とする。
【課題を解決するための手段】
【００１０】
本発明の態様の一つは、第１の演算部、パリティ演算部、第２の演算部、特定部、パリティチェック部、及び、制御部を備えるデータ処理システムである。第１の演算部は、入力ビット列に対して第１の誤り訂正符号演算を行う。パリティ演算部は、第１の誤り訂正符号演算の結果を含む第１のビット列のパリティビットを取得する。第２の演算部は、第１のビット列に対して、第２の誤り訂正符号演算を行う。特定部は、第２の誤り訂正符号演算の演算結果と、多くともＮ（Ｎ＞０の整数）のエラービット数及びエラー位置と、の対応付けに基づいて、第１のビット列に対する第２の誤り訂正符号演算の演算結果から、第１のビット列における多くともＮのエラービット数及びエラー位置を特定する。パリティチェック部は、第１のビット列に付加されているパリティビットを用いて、第１のビット列に対してパリティチェックを行う。制御部は、特定部によって特定された第１のビット列におけるエラービット数がＮビットであり、且つ、パリティチェックの結果がエラー有りである場合に、第１のビット列においてＮ＋１ビットのエラーを検出する。
【００１１】
また、本発明の他の態様の一つは、演算部と、パリティ演算部とを備えるデータ処理装置である。演算部は、入力ビット列に対して第１の誤り訂正符号演算を行う。パリティ演算部は、第１の誤り訂正符号演算の結果についてのパリティビットを取得する。
【００１２】
また、本発明の他の態様の一つは、演算部と、特定部と、パリティチェック部と、制御部とを備えるデータ処理装置である。演算部は、所定のビット列に対する第１の誤り訂正符号演算の結果を含む第１のビット列に対して、第２の誤り訂正符号演算を行う。特定部は、第２の誤り訂正符号演算の演算結果と、多くともＮ（Ｎ＞０の整数）のエラービット数及びエラー位置と、の対応付けに基づいて、第１のビット列に対する第２の誤り訂正符号演算の演算結果から、第１のビット列における多くともＮのエラービット数及びエラー位置を特定する。パリティチェック部は、第１のビット列に付加されているパリティビットを用いて、第１のビット列に対してパリティチェックを行う。制御部は、特定部によって特定された第１のビット列におけるエラービット数がＮビットであり、且つ、パリティチェックの結果がエラー有りである場合に、第１のビット列においてＮ＋１ビットのエラーを検出する。
【発明の効果】
【００１３】
開示のデータ処理システム及びデータ処理装置によれば、回路規模を抑えつつ検出可能なエラービット数を増加させることができる。
【図面の簡単な説明】
【００１４】
【図１】図１は、ハミング符号演算を用いるエラー検出及び訂正処理の一例を示す図である。
【図２】図２は、ＢＣＨ符号演算を用いる、２ビットエラーの検出及び２ビットエラーの訂正を行うエラー訂正処理の一例を示す図である。
【図３】図３は、ＢＣＨ符号演算を用いる、３ビットエラーの検出及び３ビットエラーの訂正を行うエラー訂正処理の一例を示す図である。
【図４】図４は、第１実施形態に係るエラー検出及び訂正処理を実行するエラーチェック部の一例である。
【図５Ａ】図５Ａは、第１実施形態に係るエラーチェック部の処理の流れの一例を示す図である。
【図５Ｂ】図５Ｂは、第１実施形態に係るエラーチェック部の処理の流れの一例を示す図である。
【図６】図６は、エラー判定テーブルの一例である。
【図７】図７は、２ビットエラー検出及び２ビットエラー訂正可能なＢＣＨ符号演算を用いたエラー検出及び訂正において、最大で２ビットのエラーが発生する前提での、Ａ、Ｂ、Ｃ、及び、Ｄの関係を示す図である。
【図８】図８は、２ビットエラー検出及び２ビットエラー訂正可能なＢＣＨ符号演算を用いたエラー検出及び訂正において、最大で３ビットのエラーが発生する前提での、Ａ、Ｂ、Ｃ、及び、Ｄの関係を示す図である。
【図９】図９は、第１実施形態に係るエラーチェック部によるエラー検出及び訂正において、最大で３ビットのエラーが発生する前提での、Ａ、Ｂ、Ｃ、及び、Ｄの関係を示す図である。
【図１０】図１０は、第１実施形態に係るエラーチェック部によるエラー検出及び訂正において、最大で３ビットのエラーが発生する前提での、Ａ、Ｂ、Ｃ、及び、Ｅの関係を示す図である。
【図１１】図１１は、第１実施形態に係るエラーチェック部の制御部の処理のフローチャートの一例である。
【図１２】図１２は、具体例における多項式及び多項式演算部の回路構成の一例を示す図である。
【図１３Ａ】図１３Ａは、具体例に係るエラーチェック部のＲＡＭにおいて２ビットのソフトエラーが発生した場合の処理の例を示す図である。
【図１３Ｂ】図１３Ｂは、具体例に係るエラーチェック部のＲＡＭにおいて２ビットのソフトエラーが発生した場合の処理の例を示す図である。
【図１４Ａ】図１４Ａは、具体例に係るエラーチェック部のＲＡＭにおいて３ビットのソフトエラーが発生した場合の処理の例を示す図である。
【図１４Ｂ】図１４Ｂは、具体例に係るエラーチェック部のＲＡＭにおいて３ビットのソフトエラーが発生した場合の処理の例を示す図である。
【図１５】図１５は、具体例に係るエラーチェック部のＲＡＭにおいて３ビットのソフトエラーが発生した場合の処理の例を示す図である。
【図１６】図１６は、誤り訂正符号の各種アルゴリズムとルックアップテーブルの使用数との関係を示すテーブルの一例である。
【図１７】図１７は、第１実施形態に係るエラーチェック部を搭載するネットワーク装置のハードウェア構成の一例を示す図である。
【図１８】図１８は、ネットワーク装置内のＦＰＧＡのブロック図の一例である。
【図１９】図１９は、フレーム受信部のブロック図の一例である。
【発明を実施するための形態】
【００１５】
以下、図面に基づいて、本発明の実施の形態を説明する。以下の実施形態の構成は例示であり、本発明は実施形態の構成に限定されない。
【００１６】
＜第１実施形態＞
図１は、ハミング符号演算を用いるエラー検出及び訂正処理の一例を示す図である。エラーチェック部Ｐ１は、ハミング符号演算を用いるエラー検出及び訂正処理を実行する回路の一例である。エラーチェック部Ｐ１は、例えばＦＰＧＡ内の、ＲＡＭ、フリップフロップ、ルックアップテーブル、四則演算又は積和演算等を実行するゲート等の演算回路の組合せによって形成されている。
【００１７】
エラーチェック部Ｐ１は、ハミング符号生成部Ｐ１１、ＲＡＭ  Ｐ１２、ハミング符号チェック部Ｐ１３を含む。ハミング符号生成部Ｐ１１は、入力データに対して、ハミング演算を行い、符号化する。ハミング符号生成部Ｐ１１は、多項式演算部Ｐ１４、マルチプレクサ（図中、ｍｕｘ）Ｐ１５を含む。ハミング符号チェック部Ｐ１３は、ＲＡＭ  Ｐ１２から読み出された符号化データに対して、ハミング符号演算を行い、エラー検出及びエラー訂正を行う。ハミング符号チェック部Ｐ１３は、多項式演算部Ｐ１６とビットエラー位置特定部Ｐ１７とビットエラー訂正部Ｐ１８とを含む。
【００１８】
エラーチェック部Ｐ１によるハミング符号演算を用いたエラー検出及び訂正処理は、例えば、以下の通りである。入力ビット列は、通報値、と称される。
【００１９】
（１）通報値は、多項式演算部Ｐ１４に入力される。多項式演算部Ｐ１４は、多項式１を用いたハミング符号演算を通報値に対して実施する。多項式１は、ハミング符号の符号長に応じて予め決められている。例えば、符号長７ビット、通報値４ビットのハミング符号演算に対応している場合、多項式演算部Ｐ１４では、通報値の末尾に０を３ビット分追加して７ビットのビット列とし、当該ビット列を係数とする多項式を多項式１で除算し、その剰余を演算結果とする演算が行われる。以降、多項式演算部Ｐ１４の演算結果は、符号語と称される。
【００２０】
（２）マルチプレクサＰ１５に通報値と符号語とが入力される。マルチプレクサＰ１５は、通報値の末尾に符号語を付加してセットとし、ＲＡＭ  Ｐ１２に書き込む。以降、符号生成部から出力されるビット列を、送信語、と称する。図１では、送信語は、通報値と符号語とのセットである。
【００２１】
（３）ＲＡＭ  Ｐ１２においてソフトエラーによるビットエラーが発生したことを想定する。ビットエラーによって、通報値と符号語とのセットに、１ビットのビットエラーが発生したことを想定する。
【００２２】
（４）通報値と符号語とのセットがＲＡＭ  Ｐ１２から読み出され、ハミング符号チェック部Ｐ１３に入力される。以降、符号チェック部に入力されるビット列を、受信語、と称する。図１では、受信語は、ＲＡＭ  Ｐ１２から読み出された通報値と符号語とのセットである。
【００２３】
（５）受信語は多項式演算部Ｐ１６に入力される。多項式演算部Ｐ１６は、受信語に対して多項式１を用いてハミング符号演算を行う。多項式演算部Ｐ１６で用いられる多項式１は、多項式演算部Ｐ１４で用いられる多項式１と同じである。具体的には、多項式演算部Ｐ１６では、受信語を係数とする多項式を多項式１で除算し、その剰余を演算結果とする演算が行われる。多項式演算部Ｐ１６によって得られる演算結果を、シンドロームと称する。
【００２４】
（６）シンドロームはビットエラー位置特定部Ｐ１７に入力される。シンドロームの値と１ビットのビットエラーの位置との対応付けを格納するエラー判定テーブル（図示せず）はルックアップテーブルに記憶されている。ビットエラー位置特定部Ｐ１７は、入力されたシンドロームの値とエラー判定テーブルとに基づいて、受信語の１ビットのビットエラーの位置を特定する。受信語の特定されたビットエラーの位置は、ビットエラー訂正部Ｐ１８に入力される。
【００２５】
（７）ビットエラー訂正部Ｐ１８には、受信語と、受信語のビットエラーの位置とが入力される。ビットエラー訂正部Ｐ１８は、受信語のうちのビットエラーの位置のビットを反転させて、ビットエラーを訂正する。
【００２６】
（８）エラー訂正後のビット列が出力される。エラー訂正部から出力されるビット列を、以降、復号語と称する。
【００２７】
図２は、ＢＣＨ符号演算を用いる、２ビットエラーの検出及び２ビットエラーの訂正を行うエラー訂正処理の一例を示す図である。エラーチェック部Ｐ２は、ＢＣＨ符号演算を用いるエラー検出及び訂正処理を実行する回路の一例である。エラーチェック部Ｐ２は、例えばＦＰＧＡ内の、ＲＡＭ、フリップフロップ、ルックアップテーブル、四則演算又は積和演算等を実行するゲート等の演算回路の組合せによって形成されている。
【００２８】
エラーチェック部Ｐ２は、ＢＣＨ符号生成部Ｐ２１、ＲＡＭ  Ｐ２２、ＢＣＨ符号チェック部Ｐ２３を含む。ＢＣＨ符号生成部Ｐ２１は、入力データに対して、ＢＣＨ演算を行い、符号化する。ＢＣＨ符号生成部Ｐ２１は、多項式演算部Ｐ２４、マルチプレクサ（図中、ｍｕｘ）Ｐ２５を含む。ＢＣＨ符号チェック部Ｐ２３は、ＲＡＭ  Ｐ２２から読み出された符号化データに対して、ＢＣＨ符号演算を行い、エラー検出及びエラー訂正を行う。ＢＣＨ符号チェック部Ｐ２３は、多項式演算部Ｐ２６、多項式演算部Ｐ２７、ビットエラー位置特定部Ｐ２８、及び、ビットエラー訂正部Ｐ２９を含む。
【００２９】
エラーチェック部Ｐ２によるＢＣＨ符号演算を用いたエラー検出及び訂正処理は、例えば、以下の通りである。
【００３０】
（１）通報値は、多項式演算部Ｐ２４に入力される。多項式演算部Ｐ２４は、多項式１を用いたＢＣＨ符号演算を通報値に対して実施する。多項式１は、ＢＣＨ符号の符号長に応じて予め決められている。例えば、符号長１５ビット、通報値７ビットのＢＣＨ符号演算に対応している場合、多項式演算部Ｐ２４では、通報値の末尾に０を８ビット分追加して１５ビットのビット列とし、当該ビット列を係数とする多項式を多項式１で除算し、その剰余を演算結果とする演算が行われる。なお、多項式１は、図１のハミング符号を用いるエラーチェック部Ｐ１で用いられた多項式１とは異なる多項式である。
【００３１】
（２）マルチプレクサＰ２５に通報値と符号語とが入力される。マルチプレクサＰ２５は、通報値の末尾に符号語を付加してセットとし、ＲＡＭ  Ｐ２２に書き込む。図２では、送信語は、通報値と符号語とのセットである。
【００３２】
（３）ＲＡＭ  Ｐ２２においてソフトエラーによるビットエラーが発生したことを想定する。ビットエラーによって、通報値と符号語とのセットに、２ビット又は１ビットのビットエラーが発生したことを想定する。
【００３３】
（４）通報値と符号語とのセットがＲＡＭ  Ｐ２２から読み出され、ＢＣＨ符号チェック部Ｐ２３に入力される。図２では、受信語は、ＲＡＭ  Ｐ２２から読み出された通報値と符号語である。
【００３４】
（５）受信語は、多項式演算部Ｐ２６、Ｐ２７のそれぞれに入力される。多項式演算部Ｐ２６は、受信語に対して多項式２を用いてＢＣＨ符号演算を行う。多項式演算部Ｐ２７は、受信語に対して多項式３を用いてＢＣＨ符号演算を行う。多項式２及び多項式３は、多項式演算部Ｐ２４で用いられる多項式１と、多項式１＝多項式２×多項式３の関係にある多項式である。具体的には、多項式演算部Ｐ２６、Ｐ２７では、それぞれ、受信語を係数とする多項式を多項式２、多項式３で除算し、その剰余をシンドロームＳ１、Ｓ２とする演算が行われる。
【００３５】
（６）シンドロームＳ１、Ｓ２はビットエラー位置特定部Ｐ２８に入力される。シンド
ロームＳ１、Ｓ２の値の組合せとビットエラーの位置との対応付けを格納するエラー判定テーブルはルックアップテーブルに記憶されている。ビットエラー位置特定部Ｐ２８は、入力されたシンドロームＳ１、Ｓ２の値とエラー判定テーブルとに基づいて、受信語の１ビット又は２ビットのビットエラーの位置を特定する。受信語の特定されたビットエラーの位置は、ビットエラー訂正部Ｐ２９に入力される。
【００３６】
（７）ビットエラー訂正部Ｐ２９には、受信語と、受信語のビットエラーの位置とが入力される。ビットエラー訂正部Ｐ２９は、受信語のうちのビットエラーの位置のビットを反転させて、ビットエラーを訂正する。（８）エラー訂正後のビット列が、復号語として出力される。
【００３７】
図２に示される２ビットエラー検出及びエラー訂正を行うエラーチェック部Ｐ２において用いられるエラー判定テーブルの、シンドロームＳ１、Ｓ２の組合せとビットエラーの位置との対応付けは、ＢＣＨ符号のアルゴリズムによって予め判明している。
【００３８】
シンドロームＳ１、Ｓ２の組合せの中には、１ビットのエラーとビットエラーの位置とを示す組合せ、２ビットのエラーとビットエラーの位置とを示す組合せ、エラーなしを示す組合せ、該当なしを示す組合せがある。例えば、３ビットのエラーが発生した場合には、シンドロームＳ１、Ｓ２の組合せは、該当なし又は２ビットエラーのいずれかを示す。そのため、シンドロームＳ１、Ｓ２の組合せが２ビットエラーを示した場合、２ビットエラーが発生しているのか、３ビットエラーが発生しているのかを識別することは困難である。すなわち、シンドロームＳ１、Ｓ２の組合せが２ビットエラーを示す場合、３ビットエラーが発生しているにもかかわらず、２ビットエラーであると誤判断されている可能性がある。この場合、シンドロームＳ１、Ｓ２の組合せが２ビットエラーを示す場合、本当は３ビットエラーが発生しているにもかかわらず、誤った２ビットエラー訂正を行ってしまうため、後段の回路又は装置に影響を及ぼす可能性がある。
【００３９】
図３は、ＢＣＨ符号演算を用いる、３ビットエラーの検出及び３ビットエラーの訂正を行うエラー訂正処理の一例を示す図である。エラーチェック部Ｐ３は、ＢＣＨ符号演算を用いるエラー検出及び訂正処理を実行する回路の一例である。エラーチェック部Ｐ３は、例えばＦＰＧＡ内の、ＲＡＭ、フリップフロップ、ルックアップテーブル、四則演算又は積和演算等を実行するゲート等の演算回路の組合せによって形成されている。
【００４０】
エラーチェック部Ｐ３は、ＢＣＨ符号生成部Ｐ３１、ＲＡＭ  Ｐ３２、ＢＣＨ符号チェック部Ｐ３３を含む。ＢＣＨ符号生成部Ｐ３１は、多項式演算部Ｐ３４、マルチプレクサ（図中、ｍｕｘ）Ｐ３５を含む。ＢＣＨ符号チェック部Ｐ３３は、多項式演算部Ｐ３６Ａ、多項式演算部Ｐ３６Ｂ、多項式演算部Ｐ３６Ｃ、ビットエラー位置特定部Ｐ３７、ビットエラー訂正部Ｐ３９を含む。
【００４１】
エラーチェック部Ｐ３によるＢＣＨ符号演算を用いたエラー検出及び訂正処理の（１）〜（４）では、例えば、図２のエラーチェック部Ｐ２によるＢＣＨ符号演算を用いたエラー訂正処理の（１）〜（４）とほぼ同様にして、送信語がＲＡＭ  Ｐ２２に書き込まれ、受信語が読み出される。
【００４２】
エラーチェック部Ｐ３によるＢＣＨ符号演算を用いたエラー検出及び訂正処理の（５）では、受信語に対して、多項式２、多項式３、多項式４それぞれを用いて、ＢＣＨ符号演算が行われる。多項式２、多項式３、多項式４は、多項式演算部Ｐ３４で用いられる多項式１と、多項式１＝多項式２×多項式３×多項式４の関係にある多項式である。多項式演算部Ｐ３６Ａ、多項式演算部Ｐ３６Ｂ、多項式演算部Ｐ３６Ｃによって、シンドロームＳ１、Ｓ２、Ｓ３が取得される。
【００４３】
（６）ビットエラー位置特定部Ｐ３７には、シンドロームＳ１、Ｓ２、Ｓ３が入力される。ビットエラー位置特定部Ｐ３７が保持するエラー判定テーブルは、シンドロームＳ１、Ｓ２、Ｓ３の組合せについて用意されるため、図２に示される２ビットエラー検出及び２ビットエラー訂正可能なエラーチェック部Ｐ２のエラー判定テーブルよりも大きなサイズとなる。
【００４４】
例えば、符号長が１５ビット、通報値が７ビットの、２ビットエラー検出及び訂正可能なＢＣＨ符号演算を用いたエラーチェック部Ｐ２では、エラー判定テーブルは、１６（シンドロームＳ１）×１６（シンドロームＳ２）＝２５６通りの組合せである。一方、符号長が１５ビット、通報値が５ビットの３ビットエラー検出及び訂正可能なＢＣＨ符号演算を用いたエラーチェック部Ｐ３では、エラー判定テーブルは、１６（シンドロームＳ１）×１６（シンドロームＳ２）×４（シンドロームＳ３）＝１２０４通りの組合せである。
【００４５】
３ビットエラー検出及び３ビットエラー訂正可能なＢＣＨ符号演算を用いたエラーチェック部Ｐ３では、エラー判定テーブルはサイズが大きくなる。しかしながら、シンドロームをキーにして該当するフィールドの値を導きだすテーブル処理にＲＡＭを適用することを仮定した場合、当該ＲＡＭが更なるビットエラーを誘発する可能性がある。一方、エラー判定テーブルをフリップフロップやルックアップテーブルを用いて論理的に構成することを仮定した場合、３ビットエラー検出及び訂正可能なＢＣＨ符号演算を用いたエラー訂正処理では、回路規模が肥大化する。
【００４６】
図４は、第１実施形態に係るエラー検出及び訂正処理を実行するエラーチェック部の一例である。エラーチェック部１は、例えばＦＰＧＡ内の、ＲＡＭ、フリップフロップ、ルックアップテーブル、四則演算又は積和演算等を実行するゲート等の演算回路等の素子の組合せによって形成されている。エラーチェック部１、エラーチェック部１を搭載するＦＰＧＡは、「データ処理システム」、「データ処理装置」の一例である。
【００４７】
エラーチェック部１は、ＢＣＨ符号生成部１１、ＲＡＭ  １２、ＢＣＨ符号チェック部１３を含む。ＢＣＨ符号生成部１１は、通報値に対してＢＣＨ符号演算を行い、ＢＣＨ符号化を行う。ＢＣＨ符号生成部１１は、多項式演算部１１１、マルチプレクサ（図中、ｍｕｘ）１１２、パリティ演算部１１３を含む。ＢＣＨ符号チェック部１３は、ＢＣＨ符号生成部１１によって符号化された通報値に対してＢＣＨ符号演算を行い、エラーの検出及び訂正を行う。ＢＣＨ符号チェック部１３は、多項式演算部１３１、多項式演算部１３２、パリティチェック部１３３、ビットエラー位置特定部１３４、制御部１３５、ビットエラー訂正部１３６を含む。
【００４８】
第１実施形態に係るエラーチェック部１は、２ビットエラー検出及び２ビットエラー訂正を行うＢＣＨ符号演算を用いるエラーチェック部Ｐ２の構成（図２参照）に、パリティ演算部１１３、パリティチェック部１３３、制御部１３５を追加した構成である。第１実施形態に係るエラーチェック部１は、ＲＡＭ  １２への書き込み前及び読み出し後の通報値と符号語とのセットについてパリティチェックを行う。パリティチェックは、ＲＡＭ  １２への書き込み前及びＲＡＭ  １２からの読み出し後それぞれにおける通報値と符号語とのセットのパリティビットが一致するか否かを判定する処理である。
【００４９】
パリティビットは、対象のビット列中に含まれる１の数が偶数個であるか奇数個であるかを示すビットである。偶数パリティである場合には、パリティビットは、対象のビット列中に含まれる１の数が偶数個であれば「０」、奇数個であれば「１」となる。奇数パリティである場合には、パリティビットは、対象のビット列中に含まれる１の数が奇数個であれば「０」、偶数個であれば「１」となる。第１実施形態では、偶数パリティ、奇数パ
リティのいずれが用いられてもよい。偶数パリティの場合には、バリティビットは対象ビット列中の全ビットの排他的論理和（ＸＯＲ）として得られる。奇数パリティの場合には、バリティビットは対象ビット列中の全ビットの否定排他的論理和（ＸＮＯＲ）として得られる。
【００５０】
ＲＡＭ  １２への書込み前の及びＲＡＭ  １２からの読み出し後それぞれにおける通報値と符号語とのセットについてのパリティビットが一致している場合には、ビットエラーがない、又は、偶数個のビットエラーが発生したことが示される。ＲＡＭ  １２への書込み前の及びＲＡＭ  １２からの読み出し後それぞれにおける通報値と符号語とのセットについてのパリティビットが一致していない場合には、奇数個のビットエラーが発生したことが示される。
【００５１】
すなわち、第１実施形態に係るエラーチェック部１では、パリティチェックを行うことで、エラー判定テーブルによる２ビットエラーの判定結果に基づいて２ビットエラーであるか３ビットエラーであるかを検証することができる。これによって、２ビットエラー及び３ビットエラーの検出の精度を向上させることができる。すなわち、第１実施形態に係るエラーチェック部１は、３ビットまでのビットエラーを検出可能であり、２ビットまでのビットエラーを訂正可能である。
【００５２】
図５Ａ及び図５Ｂは、第１実施形態に係るエラーチェック部１の処理の流れの一例を示す図である。（１）通報値は、多項式演算部１１１に入力される。多項式演算部１１１は、多項式１を用いたＢＣＨ符号演算を通報値に対して実施し、演算結果としての符号語を出力する。具体的な演算内容は、図２の多項式演算部Ｐ２４と同様である。
【００５３】
（２）マルチプレクサ１１２に通報値と符号語とが入力される。マルチプレクサ１１２は、通報値の末尾に符号語を付加して出力する。多項式演算部１１１又は多項式演算部１１１とマルチプレクサ１１２とは、「第１の演算部」の一例である。多項式演算部１１１又は多項式演算部１１１とマルチプレクサ１１２とにおいて行われる処理は、「第１の誤り訂正符号演算」の一例である。マルチプレクサ１１２から出力された通報値と符号語とのセットは、「第１のビット列」の一例である。
【００５４】
（３）マルチプレクサ１１２から出力された通報値と符号語とのセットは、パリティ演算部１１３に入力される。パリティ演算部１１３は、通報値と符号語とのセットのパリティビットを求める。パリティ演算部１１３からは、通報値と符号語とのセットについてのパリティビットが出力される。ＢＣＨ符号生成部１１では、パリティ演算部１１３から出力されたパリティビットが、通報値と符号語とのセットとの先頭に付加されるような回路構成となっている。パリティビット、通報値、符号語のセットは、ＲＡＭ  １２に書き込まれる。第１実施形態において、ＢＣＨ符号生成部１１から出力される送信語は、パリティビット、通報値、符号語のセットである。パリティ演算部１１３は、「パリティ演算部」の一例である。
【００５５】
（４）ＲＡＭ  １２においてソフトエラーによるビットエラーが発生する可能性がある。ビットエラーによって、ＲＡＭ  １２に書き込まれたパリティビット、通報値、符号語のセットの値に変化が生じる。
【００５６】
（５）ＲＡＭ  １２から読み出されたパリティビット、通報値、符号語のセットは、ＢＣＨ符号チェック部１３に入力される。第１実施形態では、受信語は、ＲＡＭ  １２から読み出されたパリティビット、通報値、符号語のセットである。
【００５７】
次に、図５Ｂの（６）では、受信語は、多項式演算部１３１、多項式演算部１３２のそ
れぞれに入力される。多項式演算部１３１は、受信語のうち、通報値と符号語に相当するビット列に対して多項式２を用いてＢＣＨ符号演算を行う。多項式演算部１３２は、受信語のうち、通報値と符号語に相当するビット列に対して多項式３を用いてＢＣＨ符号演算を行う。多項式２及び多項式３は、多項式演算部１１１で用いられる多項式１と、多項式１＝多項式２×多項式３の関係にある多項式である。具体的には、多項式演算部１３１、１３２では、それぞれ、受信語を係数とする多項式を多項式２、多項式３で除算し、その剰余をシンドロームＳ１、Ｓ２とする演算が行われる。多項式演算部１３１、多項式演算部１３２は、「第２の演算部」の一例である。多項式演算部１３１、多項式演算部１３２において行われる多項式２、３を用いた演算は、「第２の誤り訂正符号演算」の一例である。シンドロームＳ１、Ｓ２は、「第２の誤り訂正符号演算の演算結果」の一例である。
【００５８】
（７）シンドロームＳ１、Ｓ２はビットエラー位置特定部１３４に入力される。ビットエラー位置特定部１３４は、エラー判定テーブルをルックアップテーブルに記憶している。ビットエラー位置特定部１３４は、入力されたシンドロームＳ１、Ｓ２の値をエラー判定テーブルにキーとして入力し、シンドロームＳ１、Ｓ２に該当するエラー判定テーブルのフィールドの値を判定結果として取得する。エラー判定テーブルによる判定結果は、エラーなし、１ビットエラーとそのエラー位置、２ビットエラーとそのエラー位置、該当なしのいずれかである（後述）。エラー判定テーブルによる判定結果は、制御部１３５に出力される。ビットエラー特定部１３４は、「特定部」の一例である。
【００５９】
（８）受信語は、パリティチェック部１３３にも入力される。パリティチェック部１３３は、受信語に対してパリティチェックを行う。具体的には、パリティチェック部１３３では、受信語のパリティビットが求める演算が行われる。パリティチェックでは、受信語に含まれるパリティビットと、受信語に含まれる通報値と符号語とのセットのパリティビットと、が一致するか否かが判定されればよい。そのため、パリティチェックでは、受信語に含まれるパリティビットと、受信語に含まれる通報値と符号語とのセットのパリティビットと、の排他的論理和又は否定排他的論理和が求められればよい。パリティビットは対象のビット列に含まれる全ビットの排他的論理和又は否定排他的論理和である。したがって、パリティチェック部１３３におけるパリティチェックでは、受信語に含まれる全ビットのパリティビットが求められればよい。
【００６０】
偶数パリティでは、受信語のパリティビットが０である場合には、パリティエラーがないことが示される。受信語のパリティビットが１である場合には、パリティエラーがあることが示される。奇数パリティでは、受信語のパリティビットが１である場合には、パリティエラーがないことが示される。受信語のパリティビットが０である場合には、パリティエラーがあることが示される。パリティチェック部１３３によって取得されるパリティチェック結果（実際には、受信語のパリティビット）は、制御部１３５に出力される。パリティチェック部１３３は、「パリティチェック部」の一例である。
【００６１】
（９）制御部１３５には、ビットエラー位置特定部１３４からエラー判定テーブルによる判定結果と、パリティチェック部１３３からのパリティチェック結果とが入力される。エラー判定テーブルによる判定結果が、エラーなし、１ビットエラーとそのエラー位置である場合には、制御部１３５は、エラー判定テーブルによる判定結果をビットエラー訂正部１３６に出力する。エラー判定テーブルによる判定結果が、該当なし、である場合には、制御部１３５は、３ビット以上のエラーを検出し、エラーチェック部１が搭載されている装置のＣＰＵ（Central Processing Unit）に３ビットエラーを通知する。なお、第１
実施形態では、３ビット以上のエラーも３ビットエラーと同列に扱うため、３ビット以上のエラーが検出された場合には、３ビットエラーが通知される。
【００６２】
エラー判定テーブルによる判定結果が２ビットエラーとそのエラー位置である場合には
、制御部１３５は、パリティチェック結果を用いて、２ビットエラーであるか３ビットエラーであるかを検証する。パリティチェック結果がパリティエラーなしである場合には、制御部１３５は、エラー判定テーブルによる判定結果である２ビットエラーを確定し、エラー判定テーブルによる判定結果をビットエラー訂正部１３６に出力する。パリティチェック結果がパリティエラー有りである場合には、制御部１３５は、３ビットエラーを検出し、エラーチェック部１が搭載されている装置のＣＰＵに３ビットエラーを通知する。制御部１３５は、「制御部」の一例である。
【００６３】
（１０）ビットエラー訂正部１３６には、受信語と、エラー判定テーブルによる判定結果とが入力される。エラー判定テーブルによる判定結果が１ビットエラー又は２ビットエラーである場合には、ビットエラー訂正部１３６は、受信語のうちのビットエラーの位置のビットを反転させて、ビットエラーを訂正する。その後、ビットエラー訂正部１３６は、エラー訂正後の受信語のうちの通報値に相当するビット列を復号語として出力する。なお、３ビット以上のエラーが検出されている場合には、ビットエラー訂正部１３６は、ビットエラーを訂正せず、受信語のうち通報値に相当するビット列を復号語として出力する。
【００６４】
図６は、エラー判定テーブルの一例である。図６に示されるエラー判定テーブルは、通報値７ビット、符号長が１５ビットとなるＢＣＨ符号演算のエラー判定テーブルである。エラー判定テーブルのシンドロームＳ１、Ｓ２の組合せに対する値は、ＢＣＨ符号演算のアルゴリズムにより、既知である。
【００６５】
例えば、シンドロームＳ１（００００）とシンドロームＳ２（００００）との組合せに該当するエラー判定テーブルのフィールドの値は、エラー無し、である。例えば、シンドロームＳ１（１０００）とシンドロームＳ２（００１１）との組合せに該当するエラー判定テーブルのフィールドの値は、２ビットエラー（２，８）、である。エラー判定テーブルのフィールドの値である、２ビットエラー（２，８）は、ＲＡＭ  １２から読み出された通報値と符号語とのセットに２ビットのエラーが含まれており、ビットエラーの位置は、Ｄ２、Ｄ８の位置であることが示される。ビットエラーの位置Ｄ（ｘ−１）は、下位ｘビット目であることを示す。すなわち、ビットエラーの位置がＤ２であることは、下位から３ビット目のビットにエラーがあることが示される。シンドロームＳ１、Ｓ２の組合せに該当するエラー判定テーブルのフィールドの値が空欄である場合には、該当なし、として値が返される。エラー判定テーブルは、「第２の誤り訂正符号演算の演算結果と、多くともＮのエラービット数及びエラー位置と、の対応付け」の一例である。
【００６６】
図７、図８、及び、図９を用いて、第１実施形態に係るエラーチェック部１によって、エラー判定テーブルの判定結果が２ビットエラーである場合に、２ビットエラー又は３ビットエラーが特定可能であることを説明する。
【００６７】
図７、図８、及び、図９は、それぞれがいずれの２ビットを反転させても他の２つの値にはならない３つの値の符号間距離を示す図である。例えば、Ａは、１１０００１１１である。Ｂは、００００００００である。Ｃは、１１１１１０００である。これらは、いずれの２ビットを反転させても、他の２つの値、及び、他の値がいずれかの２ビットを反転させた値にはならない。そのため、Ａ、Ｂ、Ｃそれぞれの間の符号間距離は少なくとも５離れている。
【００６８】
図７、図８、及び、図９中の、Ａ、Ｂ、Ｃそれぞれを中心とし、点線で示される円は、２ビットエラー検出及び２ビットエラー訂正可能なＢＣＨ符号演算を用いて、エラー訂正可能な範囲を示す。以降、Ａ、Ｂ、Ｃはビットエラー発生前の値とする。図７、図８、及び、図９に示されるＤは、ビットエラー発生後の値であるとする。Ｄは、例えば、１１０
０００００である。Ｄは、Ｂの先頭２ビットを反転させた値であり、Ｂとの距離が２である。また、Ｄは、Ｃを３ビット反転させた値であり、Ｃとの距離が３である。
【００６９】
図７は、２ビットエラー検出及び２ビットエラー訂正可能なＢＣＨ符号演算を用いたエラー検出及び訂正において、最大で２ビットのエラーが発生する前提での、Ａ、Ｂ、Ｃ、及び、Ｄの関係を示す図である。図７中のＤを中心とする円７０１は、Ｄがビットエラー発生前の値としてとり得る範囲を示す。図７では最大で２ビットのエラーが発生することが前提であるので、円７０１は、Ｄを中心として半径が２目盛りの円である。ＢはＤの２目盛り以内である円７０１内に存在するので、Ｄの元の値はＢであることが特定される。また、ＤはＢを中心とする円内に存在するので、エラー訂正可能である。
【００７０】
図８は、２ビットエラー検出及び２ビットエラー訂正可能なＢＣＨ符号演算を用いたエラー検出及び訂正において、最大で３ビットのエラーが発生する前提での、Ａ、Ｂ、Ｃ、及び、Ｄの関係を示す図である。図８中のＤを中心とする円７０２は、Ｄがビットエラー発生前の値としてとり得る範囲を示す。図８では最大で３ビットのエラーが発生することが前提であるので、円７０２は、Ｄを中心として半径が３目盛りの円である。図８では、Ｂ及びＣがＤを中心とする円７０２内に存在する。そのため、２ビットエラー検出可能及び２ビットエラー訂正可能なＢＣＨ符号演算を用いて２ビットエラーが検出された場合でも、Ｄの元の値がＢ又はＣのいずれであるかを特定することができない。
【００７１】
図９は、第１実施形態に係るエラーチェック部１によるエラー検出及び訂正において、最大で３ビットのエラーが発生する前提での、Ａ、Ｂ、Ｃ、及び、Ｄの関係を示す図である。図９中のＤを中心とする円７０３は、Ｄがビットエラー発生前の値としてとり得る範囲を示す。図９では最大で３ビットのエラーが発生することが前提であるので、円７０３は、Ｄを中心として半径が３目盛りの円である。図９では、Ｂ及びＣがＤを中心とする円７０３内に存在する。
【００７２】
第１実施形態に係るエラーチェック部１では、パリティチェック部１３３によってパリティチェックが行われる。パリティエラーがある場合には、エラービット数が奇数であることが特定される。パリティエラーがない場合にはエラービット数が偶数であることが特定される。
【００７３】
したがって、図９に示される状態で、パリティエラーが検出される場合には、エラービット数が奇数であるため、Ｄの元の値は、ＢではなくＣであることが特定される。ただし、Ｄは、Ｃを中心とする円内に存在していないため、エラーを訂正することはできない。そのため、第１実施形態に係るエラーチェック部１は、３ビットまでのビットエラーを検出可能であるが、２ビットまでのビットエラーを訂正可能であり、３ビットエラーは訂正できない。
【００７４】
図１０は、第１実施形態に係るエラーチェック部１によるエラー検出及び訂正において、最大で３ビットのエラーが発生する前提での、Ａ、Ｂ、Ｃ、及び、Ｅの関係を示す図である。Ｅは、１ビットエラーによって発生した値である。Ｅは、例えば、１０００００００であり、Ｂの先頭１ビットを反転させた値である。
【００７５】
図１０中の円７０４は、Ｅがビットエラー発生前の値としてとり得る範囲を示す。図１０では最大で３ビットのエラーが発生することが前提であるので、円７０４は、Ｅを中心として半径が３目盛りの円である。図１０では、ＢがＥを中心とする円７０４内に存在し、Ａ、Ｃは円７０４外に存在するので、元の値がＢであることが特定可能である。また、Ｅは、Ｂを中心とする円内に存在するため、エラー訂正可能である。
【００７６】
したがって、第１実施形態に係るエラーチェック部１によるエラー訂正において、１ビットのエラーが発生した場合には、ＢＣＨ符号演算のエラー判定テーブルを用いて検出及び訂正可能である。
【００７７】
図１１は、第１実施形態に係るエラーチェック部１の制御部１３５の処理のフローチャートの一例である。図１１に示されるエラーチェック部１の制御部１３５の処理のフローチャートは、ＦＰＧＡではＤ型フリップフロップとルックアップテーブルとの組み合わせにより実現される。
【００７８】
ＯＰ１では、制御部１３５は、ビットエラー位置特定部１３４からエラー判定テーブルによる判定結果、パリティチェック部１３３からパリティチェック結果の入力を受ける。
【００７９】
ＯＰ２では、制御部１３５は、エラー判定テーブルによる判定結果がエラー無しであるか否かを判定する。エラー判定テーブルによる判定結果がエラー無しである場合には（ＯＰ２：ＹＥＳ）、処理がＯＰ３に進む。エラー判定テーブルによる判定結果がエラー無しでない場合には（ＯＰ２：ＮＯ）、処理がＯＰ４に進む。
【００８０】
ＯＰ３では、制御部１３５は、ビットエラー訂正部１３６にエラー無しを通知する。その後、図１１に示される処理が終了する。
【００８１】
ＯＰ４では、制御部１３５は、エラー判定テーブルによる判定結果が１ビットエラー検出を示すか否かを判定する。エラー判定テーブルによる判定結果が１ビットエラー検出を示す場合には（ＯＰ４：ＹＥＳ）、処理がＯＰ５に進む。エラー判定テーブルによる判定結果が１ビットエラー検出を示さない場合には（ＯＰ４：ＮＯ）、処理がＯＰ６に進む。
【００８２】
ＯＰ５では、制御部１３５は、１ビットエラーとビットエラー位置を示すエラー判定テーブルによる判定結果を、エラーチェック部１を搭載する装置のＣＰＵとビットエラー訂正部１３６に出力する。その後、図１１に示される処理が終了する。
【００８３】
ＯＰ６では、制御部１３５は、エラー判定テーブルによる判定結果が２ビットエラー検出を示すか否かを判定する。エラー判定テーブルによる判定結果が２ビットエラー検出を示す場合には（ＯＰ６：ＹＥＳ）、処理がＯＰ７に進む。エラー判定テーブルによる判定結果が２ビットエラー検出を示さない、すなわち、該当なしである場合には（ＯＰ６：ＮＯ）、処理がＯＰ９に進む。
【００８４】
ＯＰ７では、制御部１３５は、パリティチェック結果がエラー有りであるか否かを判定する。制御部１３５には、パリティチェック結果として、パリティチェック部１３３から受信語のパリティビットが入力される。例えば、偶数パリティでは、受信語のパリティビットが１である場合には、パリティエラーがあることが示される。例えば、偶数パリティでは、受信語のパリティビットが０である場合には、パリティエラーがないことが示される。
【００８５】
パリティチェック結果がエラー有りである場合には（ＯＰ７：ＹＥＳ）、処理がＯＰ９に進む。パリティチェック結果がエラー無しである場合には（ＯＰ７：ＮＯ）、処理がＯＰ８に進む。
【００８６】
ＯＰ８では、パリティチェック結果がエラー無しであるので、２ビットエラーの検出結果が確定し、制御部１３５は、２ビットエラーとビットエラー位置を示すエラー判定テーブルによる判定結果を、エラーチェック部１を搭載する装置のＣＰＵとビットエラー訂正部１３６とに出力する。その後、図１１に示される処理が終了する。
【００８７】
ＯＰ９では、３ビットエラーが検出され、制御部１３５は、３ビットエラーを、エラーチェック部１を搭載する装置のＣＰＵとビットエラー訂正部１３６に出力する。その後、図１１に示される処理が終了する。
【００８８】
１ビットエラー又は２ビットエラーの場合には、エラー位置が特定され、ビットエラー訂正部１３６によってエラー訂正が行われる。３ビットエラーの場合には、エラー位置は特定されないため、エラー訂正は行われず、ビットエラーを含んだままの復号語が出力される。ただし、エラーチェック部１を搭載する装置のＣＰＵに３ビットエラーが通知されるので、ＣＰＵによる再送処理によって、ＲＡＭ  １２におけるソフトエラーによって失われたデータを補てんすることができる。また、３ビットエラーが発生した場合には、ＲＡＭ  １２をＣＰＵが初期状態に書き換えて、ソフトエラーを修復してもよい。
【００８９】
＜具体例＞
図１２は、具体例における多項式及び多項式演算部の回路構成の一例を示す図である。具体例では、多項式演算部１１１において用いられる多項式１は、Ｘ８＋Ｘ７＋Ｘ６＋Ｘ４＋１である。多項式演算部１３１において用いられる多項式２は、Ｘ４＋Ｘ＋１である。多項式演算部１３２において用いられる多項式３は、Ｘ４＋Ｘ３＋Ｘ２＋Ｘ＋１である。多項式１〜３の回路構成は、例えば、Ｄ型フリップフロップを用いて、図１２に示される通りである。また、具体例では、パリティ演算部１１３及びパリティチェック部１３３は、受信語の全ビットの偶数パリティを求めることとする。そのため、パリティ演算部１１３及びパリティチェック部１３３は、受信語の全ビットの排他的論理和を求めるので、回路構成は、排他的論理和回路となる。
【００９０】
図１３Ａ及び図１３Ｂは、具体例に係るエラーチェック部１のＲＡＭ  １２において２ビットのソフトエラーが発生した場合の処理の例を示す図である。図１３Ａでの通報値は、０１０１０１１であるとする。
【００９１】
（１）多項式演算部１１１に通報値０１０１０１１が入力され、多項式１（Ｘ８＋Ｘ７＋Ｘ６＋Ｘ４＋１）が用いられて符号語１１００１０１１が生成される。
【００９２】
（２）パリティ演算部１１３に通報値と符号語のセット０１０１０１１＿１１００１０１１が入力され、偶数パリティビット１が求められる。
【００９３】
（３）パリティビット、通報値、符号語が送信語１＿０１０１０１１＿１１００１０１１としてＢＣＨ符号生成部１１から出力されて、ＲＡＭ  １２に書き込まれる。
【００９４】
（４）ＲＡＭ  １２に格納されたパリティビット、通報値、符号語にソフトエラーによるビットエラーが発生したとする。このとき発生したビットエラーは２ビットで、下位から３ビット目、９ビット目（Ｄ２、Ｄ８）のビットが反転したことを想定する。
【００９５】
（５）ＲＡＭ  １２から読み出されたパリティビット、通報値、符号語が受信語としてＢＣＨ符号演算部１３に入力される。受信語は、１＿０１０１０１０＿１１００１１１１である。
【００９６】
図１３Ｂの（６）多項式演算部１３１、１３２に受信語が入力され、多項式２（Ｘ４＋Ｘ＋１）、多項式３（Ｘ４＋Ｘ３＋Ｘ２＋Ｘ＋１）を用いてシンドロームＳ１：１０００、シンドロームＳ２：００１１が生成される。
【００９７】
（７）ビットエラー位置特定部１３４は、エラー判定テーブル（図６）にシンドローム
Ｓ１：１０００、シンドロームＳ２：００１１をキーとして入力し、キーに該当する値として、２ビットエラー（Ｄ２、Ｄ８）を取得する。
【００９８】
（８）パリティチェック部１３３は、受信語に対してパリティチェックを行う。受信語（１＿０１０１０１０＿１１００１１１１）の偶数パリティビットは０であるので、受信語に対するパリティチェックの結果は、パリティエラー無しとなる。
【００９９】
（９）制御部１３５には、エラー判定テーブルによる判定結果：２ビットエラー（Ｄ２、Ｄ８）と、パリティエラー無しが入力される。制御部１３５は、パリティエラー無しであることから２ビットエラーを確定し（図１１、ＯＰ６：ＹＥＳ、ＯＰ７：ＮＯ）、エラーチェック部１を搭載する装置のＣＰＵに２ビットエラーを通知する（図１１、ＯＰ８）。
【０１００】
（１０）ビットエラー訂正部１３６は、エラー判定テーブルによる判定結果：２ビットエラー（Ｄ２、Ｄ８）に基づいて、受信語のビットエラーを訂正する。具体的には、受信語１＿０１０１０１０＿１１００１１１１の下位から３ビット目（Ｄ２）と９ビット目（Ｄ８）とを反転させ、１＿０１０１０１１＿１１００１０１１に訂正する。
【０１０１】
復号語は、エラー訂正後の受信語の通報値に相当するビット列０１０１０１１となる。この復号語は、通報値０１０１０１１と同じ値である。したがって、図１３Ａ、図１３Ｂに示されるように、エラーチェック部１は、２ビットエラーを検出可能であり、２ビットのエラーを訂正可能である。
【０１０２】
図１４Ａ及び図１４Ｂは、具体例に係るエラーチェック部１のＲＡＭ  １２において３ビットのソフトエラーが発生した場合の処理の例を示す図である。図１４Ａでの通報値は、０１０１０１１であるとする。
【０１０３】
（１）多項式演算部１１１に通報値０１０１０１１が入力され、多項式１（Ｘ８＋Ｘ７＋Ｘ６＋Ｘ４＋１）が用いられて符号語１１００１０１１が生成される。
【０１０４】
（２）パリティ演算部１１３に通報値と符号語のセット０１０１０１１＿１１００１０１１が入力され、偶数パリティビット１が求められる。
【０１０５】
（３）パリティビット、通報値、符号語が送信語１＿０１０１０１１＿１１００１０１１としてＲＡＭ  １２に書き込まれる。
【０１０６】
（４）ＲＡＭ  １２に格納されたデータにソフトエラーによるビットエラーが発生したとする。このとき発生したビットエラーは３ビットで、下位から６ビット目、１２ビット目、１５ビット目（Ｄ５、Ｄ１１、Ｄ１４）のビットが反転したことを想定する。
【０１０７】
（５）ＲＡＭ  １２から読み出されたデータが受信語としてＢＣＨ符号演算部１３に入力される。受信語は、１＿１１０００１１＿１１１０１０１１である。
【０１０８】
図１４Ｂの（６）多項式演算部１３１、１３２に受信語が入力され、多項式２（Ｘ４＋Ｘ＋１）、多項式３（Ｘ４＋Ｘ３＋Ｘ２＋Ｘ＋１）を用いてシンドロームＳ１：１０００、シンドロームＳ２：００１１が生成される。
【０１０９】
（７）ビットエラー位置特定部１３４は、エラー判定テーブル（図６）にシンドロームＳ１：１０００、シンドロームＳ２：００１１をキーとして入力し、キーに該当する値として、２ビットエラー（Ｄ２、Ｄ８）を取得する。
【０１１０】
（８）パリティチェック部１３３は、受信語に対してパリティチェックを行う。受信語（１＿１１０００１１＿１１１０１０１１）の偶数パリティビットは１であるので、受信語に対するパリティチェックの結果は、パリティエラー有りとなる。
【０１１１】
（９）制御部１３５には、エラー判定テーブルの判定結果：２ビットエラー（Ｄ２、Ｄ８）と、パリティエラー有りが入力される。制御部１３５は、２ビットエラーが検出されており（図１１、ＯＰ６：ＹＥＳ）、パリティエラー有りであることから（図１１、ＯＰ７：ＹＥＳ）、３ビットエラーを確定し、エラーチェック部１を搭載する装置のＣＰＵに３ビットエラーを通知する（図１１、ＯＰ９）。
【０１１２】
（１０）ビットエラー訂正部１３６は、３ビットエラーであるのでエラー訂正せずに、受信語から復号語を取得して出力する。受信語１＿１１０００１１＿１１１０１０１１であるので、復号語は１１０００１１となる。復号語には、ビットエラーが含まれたままとなる。なお、ＣＰＵに３ビットエラーが通知されるので、ＣＰＵによって通報値０１０１０１１が再送され、ＲＡＭ  １２には再送された通報値０１０１０１１と符号語とパリティビットとが上書きされる。
【０１１３】
図１４Ａ及び図１４Ｂでは、３ビットエラーが発生し、エラー判定テーブルによる判定結果が２ビットエラーであり、２ビットエラーと誤判定されている場合でも、エラーチェック部１は、３ビットエラーを検出することができることが示される。
【０１１４】
図１５は、具体例に係るエラーチェック部１のＲＡＭ  １２において３ビットのソフトエラーが発生した場合の処理の例を示す図である。図１５は、図１４Ａの続きである。すなわち、図１５では、通報値０１０１０１１に対して、送信語１＿０１０１０１１＿１１００１０１１がＲＡＭ  １２に書き込まれ、ＲＡＭ  １２において３ビットエラー（Ｄ６、Ｄ１１、Ｄ１４）が発生したことが想定される。ＲＡＭ  １２から読み出された受信語は、１＿１１０００１１＿１０００１０１１である。
【０１１５】
（６）多項式演算部１３１、１３２に受信語が入力され、多項式２（Ｘ４＋Ｘ＋１）、多項式３（Ｘ４＋Ｘ３＋Ｘ２＋Ｘ＋１）を用いてシンドロームＳ１：１１０１、シンドロームＳ２：１１１１が生成される。
【０１１６】
（７）ビットエラー位置特定部１３４は、エラー判定テーブル（図６）にシンドロームＳ１：１１０１、シンドロームＳ２：１１１１をキーとして入力し、キーに該当する値として、該当なし、を取得する。
【０１１７】
（８）パリティチェック部１３３は、受信語に対してパリティチェックを行う。受信語（１＿１１０００１１＿１０００１０１１）の偶数パリティビットは１であるので、受信語に対するパリティチェックの結果は、パリティエラー有りとなる。
【０１１８】
（９）制御部１３５には、エラー判定テーブルによる判定結果：該当なしと、パリティエラー有りが入力される。制御部１３５は、エラー判定テーブルによる判定結果が該当無しであることから（図１１、ＯＰ６：ＮＯ）、３ビットエラーを検出し、エラーチェック部１を搭載する装置のＣＰＵに３ビットエラーを通知する（図１１、ＯＰ９）。
【０１１９】
（１０）ビットエラー訂正部１３６は、３ビットエラーであるのでエラー訂正せずに、受信語から復号語を取得して出力する。受信語１＿１１０００１１＿１０００１０１１であるので、復号語は１１０００１１となる。復号語には、ビットエラーが含まれたままとなる。なお、この場合にも、ＣＰＵに３ビットエラーが通知されるので、ＣＰＵによって
通報値０１０１０１１が再送され、ＲＡＭ  １２には再送された通報値０１０１０１１と符号語とパリティビットとが上書きされる。
【０１２０】
図１５では、３ビットエラーが発生し、エラー判定テーブルによる判定結果が該当無しである場合に、エラーチェック部１は、３ビットエラーを検出することができることが示される。
【０１２１】
＜第１実施形態の作用効果＞
図１６は、誤り訂正符号の各種アルゴリズムとルックアップテーブルの使用数との関係を示すテーブルの一例である。例えば、通報値のビット数が７ビットである場合、ＢＣＨ符号を用いる２ビットエラー検出及び２ビットエラー訂正可能なエラーチェック部（図２）では、ルックアップテーブルの使用数は、９７である。第１実施形態に係る、ＢＣＨ符号を用いる３ビットエラー検出及び２ビットエラー訂正可能なエラーチェック部１では、ルックアップテーブルの使用数は、１０４である。ＢＣＨ符号を用いる３ビットエラー検出及び３ビットエラー訂正可能なエラーチェック部（図３）では、ルックアップテーブルの使用数は、３９６である。
【０１２２】
第１実施形態に係るエラーチェック部１のルックアップテーブルの使用数は、ＢＣＨ符号を用いる３ビットエラー検出及び３ビットエラー訂正可能なエラーチェック部に比べると、およそ４分の１である。図１５ではルックアップテーブルの使用数が示されているが、ＦＰＧＡ内の他の要素（フリップフロップ等）についても、使用数は、第１実施形態に係るエラーチェック部１の方が、ＢＣＨ符号を用いる３ビットエラー検出及び３ビットエラー訂正可能なエラーチェック部よりも少なくなる。
【０１２３】
第１実施形態に係るエラーチェック部１は、ＢＣＨ符号を用いる２ビットエラー検出及び２ビットエラー訂正可能なエラーチェック部の回路に、簡易なパリティ演算の回路を追加した回路である。したがって、第１実施形態に係るエラーチェック部１によれば、ＢＣＨ符号を用いる２ビットエラー検出及び２ビットエラー訂正可能なエラーチェック部に近い回路規模で、３ビットエラーまで検出することができる。また、エラー判定テーブルによって２ビットエラーが検出された場合に、パリティチェック結果によって、２ビットエラーか３ビットエラーかを特定することができ、２ビットエラー及び３ビットエラーの検出精度が向上する。
【０１２４】
第１実施形態では、３ビットエラー検出及び２ビットエラー訂正可能なエラーチェック部について説明されたが、第１実施形態で説明された技術は、３ビットエラー検出及び２ビットエラー訂正に限定されない。Ｎビットエラー検出及びＮビットエラー訂正可能な誤り符号演算に対応するエラー判定テーブルを備えるエラーチェック部に対して、パリティ演算部１１３、パリティチェック部１３３、制御部１３５を追加することで、Ｎ＋１ビットエラー検出及びＮビットエラー訂正可能なエラーチェック部を達成することも可能である。
【０１２５】
＜適用例＞
図１７は、第１実施形態に係るエラーチェック部１を搭載するネットワーク装置のハードウェア構成の一例を示す図である。第１実施形態に係るエラーチェック部１は、例えば、ネットワーク装置に搭載される。ネットワーク装置は、例えば、スイッチ、ルータ、ゲートウェイ、コントローラ等である。ネットワーク装置１００は、例えば、ＣＰＵ、ＰＣＩ（Peripheral Component Interconnect）スイッチ、ＬＡＮ  ＰＨＹ（Local Area Network PHYsical layer）、１０Ｇイーサネット（登録商標）スイッチモジュール、ＡＳＳＰ(Application Specific Standard Produce)、ＳＰＦ＋（Small Form-factor Pluggable＋）モジュール、ＣＰＬＤ（Complex Programmable Logic Device）、光モジュール、ＦＰ
ＧＡ  １０１を備える。第１実施形態に係るエラーチェック部１は、ＦＰＧＡ  １０１内に形成される。
【０１２６】
図１８は、ネットワーク装置１００内のＦＰＧＡ  １０１のブロック図の一例である。ネットワーク装置１００内のＦＰＧＡ  １０１は、例えば、ＱｏＳ（Quality of Service）、ルーティング等の処理を行う。ＦＰＧＡ  １０１は、機能構成として、外部デバイスインタフェース（ＩＦ）部１０、フレーム受信部２０、フレーム送信部３０、ＣＰＵインタフェース（ＩＦ）部４０を備える。
【０１２７】
外部デバイスインタフェース部１０は、ＣＰＵ以外の他のデバイスとのインタフェースである。ＣＰＵ  ＩＦ部４０は、ＣＰＵとのインタフェースである。フレーム受信部２０は、ネットワーク装置１００が受信したフレームを解析し、アラーム情報をＣＰＵへ通知する処理を行う。フレーム送信部３０は、ＣＰＵからの設定情報を受け取り、フレームとして組み立て、出力処理を行う。
【０１２８】
エラーチェック部１は、例えば、フレーム受信部２０、フレーム送信部３０それぞれに備えられる。
【０１２９】
図１９は、フレーム受信部２０のブロック図の一例である。フレーム受信部２０は、例えば、受付処理部２１、比較処理部２２、エラー通知部２３を含む。受付処理部２１、比較処理部２２、エラー通知部２３それぞれについて、エラーチェック部１が備えられる。
【０１３０】
受付処理部２１は、入力されたフレームが処理の対象であるか否かを判定し、処理の対象のフレームを抽出するフィルタリング処理を行う。受付処理部２１にはエラーチェック部１Ａが接続される。エラーチェック部１Ａ内のＲＡＭ  １２Ａには、処理の対象となるフレームの情報がＣＰＵによって書き込まれる。受付処理部２１は、フレームが入力されると、エラーチェック部１ＡのＲＡＭ  １２Ａから処理の対象の情報を読み出し、入力されたフレームと比較して、フィルタリング処理を行う。
【０１３１】
比較格納処理部２２は、入力されたフレームと過去のフレームとを比較し、例えば、変化がある場合に入力されたフレームを格納する。比較格納処理部２２には、エラーチェック部１Ｂが接続されている。比較格納処理部２２は、エラーチェック部１ＢのＲＡＭ  １２Ｂを、フレームを格納するバッファとして用いる。比較格納処理部２２は、フレームが入力されるとエラーチェック部１ＢのＲＡＭ  １２Ｂから過去のフレームを読み出し、入力されたフレームに変化がある場合に入力されたフレームをエラーチェック部１ＢのＲＡＭ  １２Ｂに書き込む。
【０１３２】
エラー通知部２３は、比較格納処理部２２による比較結果を通知する。エラー通知部２３には、エラーチェック部１Ｃが接続されている。エラーチェック部１ＣのＲＡＭ  １２Ｃは、例えば、比較結果のバッファとして用いられる。エラー通知部２３は、比較格納処理部２２から比較結果が入力されると、エラーチェック部１ＣのＲＡＭ  １２Ｃに比較結果を書き込む。ＣＰＵは、例えば、所定の周期でエラーチェック部１ＣのＲＡＭ  １２Ｃから比較結果を読み出す。
【０１３３】
なお、図１７、図１８、図１９に示される第１実施形態に係るエラーチェック部１の適用例は一例であって、エラーチェック部１の適用先はネットワーク装置に限定されない。ＲＡＭに対するデータの書き込み及び読み出しを伴う処理を実行する装置に、第１実施形態に係るエラーチェック部１を適用可能である。また、エラーチェック部１を実現するハードウェアは、ＦＰＧＡに限定されない。エラーチェック部１は、例えば、ＬＳＩ（large-scale integration）、ＣＰＬＤ等によって実現されてもよい。
【０１３４】
＜その他＞
第１実施形態では、３ビットエラー検出及び２ビットエラー訂正可能なエラーチェック部について説明されたが、第１実施形態で説明された技術は、３ビットエラー検出及び２ビットエラー訂正に限定されない。Ｎビットエラー検出及びＮビットエラー訂正可能な誤り符号演算に対応するエラー判定テーブルを備えるエラーチェック部に対して、パリティ演算部１１３、パリティチェック部１３３、制御部１３５を追加することで、Ｎ＋１ビットエラー検出及びＮビットエラー訂正可能なエラーチェック部を達成することも可能である。
【０１３５】
また、第１実施形態では、誤り訂正符号として、ＢＣＨ符号を例として説明されたが、第１実施形態で説明された技術には、ＢＣＨ符号以外の誤り訂正符号も適用可能である。第１実施形態で説明された技術に適用可能な誤り訂正符号には、例えば、ハミング符号、リード・ソロモン符号（ＲＳ符号）、ゴレイ符号、畳み込み符号等がある。
【０１３６】
第１実施形態では、ＲＡＭにおけるソフトエラーによってビットエラーが発生する場合について説明されたが、第１実施形態で説明された技術は、ビットエラーの発生要因に依らず、ビットエラーの検出及び訂正に適用可能である。例えば、第１実施形態で説明された技術は、通信の伝送中の雑音によってビットエラーが発生する場合に適用可能である。通信の伝送中の雑音によるビットエラーに適用する場合には、例えば、ＢＣＨ符号生成部１１は、送信側の装置の送信処理を行うＦＰＧＡに搭載される。ＢＣＨ符号チェック部１３は、受信側の装置の受信処理を行うＦＰＧＡに搭載される。
【符号の説明】
【０１３７】
１      エラーチェック部
１１    ＢＣＨ符号生成部
１２    ＲＡＭ
１３    ＢＣＨ符号チェック部
１０１  ＦＰＧＡ
１１１、１３１、１３２  多項式演算部
１１２  マルチプレクサ
１１３  パリティ演算部
１３３  パリティチェック部
１３４  ビットエラー位置特定部
１３５  制御部
１３６  ビットエラー訂正部
【図１】
2018074545.tif 000003
【図２】
2018074545.tif 000004
【図３】
2018074545.tif 000005
【図４】
2018074545.tif 000006
【図５Ａ】
2018074545.tif 000007
【図５Ｂ】
2018074545.tif 000008
【図６】
2018074545.tif 000009
【図７】
2018074545.tif 000010
【図８】
2018074545.tif 000011
【図９】
2018074545.tif 000012
【図１０】
2018074545.tif 000013
【図１１】
2018074545.tif 000014
【図１２】
2018074545.tif 000015
【図１３Ａ】
2018074545.tif 000016
【図１３Ｂ】
2018074545.tif 000017
【図１４Ａ】
2018074545.tif 000018
【図１４Ｂ】
2018074545.tif 000019
【図１５】
2018074545.tif 000020
【図１６】
2018074545.tif 000021
【図１７】
2018074545.tif 000022
【図１８】
2018074545.tif 000023
【図１９】
2018074545.tif 000024