(57)【要約】      （修正有）【課題】ユークリッド復号に適した多項式除算回路の提供。【解決手段】生成多項式の連続根の個数を２ｔとした時、シンドローム多項式とｘ２ｔとの最大公約多項式を求める除算回路５０であり、２ｔ個の第１レジスタを有するシフトレジスタ３０と、前段の値と、最上位段と前段の第１レジスタの値の乗算結果と、のＸＯＲが各々入力する２ｔ−１個の第２レジスタを有する線形帰還シフトレジスタ１０と、最下位段の第２レジスタに出力する第３レジスタと、最初の除算前に、最上位段の第２レジスタに１、他段の第２レジスタ及び第３レジスタに０を入力し、２回目以降の除算前に、第２及び第３レジスタに前回の除算後の第１レジスタの値を被除数多項式の係数として入力し、最初の除算前に、第１レジスタにシンドローム多項式の係数を入力し、２回目以降の除算前に、第１レジスタに前回除算後の第２及び第３レジスタを除数多項式の係数として入力する回路と、を備える。【選択図】図６
2020098994.tif 000002
【特許請求の範囲】
【請求項１】
生成多項式の連続根の個数を２ｔとしたとき、シンドローム多項式とｘ２ｔとの最大公約多項式を求める多項式除算回路であって、
２ｔ個の複数の第１レジスタを有するワーキングシフトレジスタと、
前段の値と、最上位段の値と前段の第１レジスタの値との乗算結果と、のＸＯＲが各々入力する２ｔ−１個の複数の第２レジスタを有する線形帰還シフトレジスタと、
０を入力し、最下位段の第２レジスタに出力し、前記最上位段の第２レジスタの値が帰還しない第３レジスタと、
最初の除算前に、前記最上位段の第２レジスタに１、他段の第２レジスタおよび前記第３レジスタに０を被除数多項式の係数としてそれぞれ入力し、２回目以降の除算前に、前記複数の第２レジスタおよび前記第３レジスタに前回の除算後の前記複数の第１レジスタの値を前記被除数多項式の係数として入力し、最初の除算前に、前記複数の第１レジスタに前記シンドローム多項式の係数を除数多項式の係数としてそれぞれ入力し、２回目以降の除算前に、前記複数の第１レジスタに前回除算後の前記複数の第２レジスタおよび前記第３レジスタを前記除数多項式の係数として入力する入力回路と、
を備える多項式除算回路。
【請求項２】
前記被除数多項式の次数をｎとし、前記除数多項式の次数をｍとしたとき、前記線形帰還シフトレジスタは、ｎ−ｍ＋１回シフトすることで、前記被除数多項式を前記除数多項式で除算する請求項１に記載の多項式除算回路。
【請求項３】
前記ワーキングシフトレジスタは、前記除算前にｎ−ｍ−１回シフトする請求項２に記載の多項式除算回路。
【請求項４】
前記線形帰還シフトレジスタは、
前記複数の第２レジスタに対応して設けられ、前記前段の第１レジスタの値がそれぞれ入力する複数の第４レジスタと、
前記複数の第４レジスタに対応し設けられ、対応する第４レジスタの値と、最上位段の第１レジスタの値の逆元と、を乗算した結果を前記対応する第４レジスタに格納し、その後前記乗算した結果と前記最上位段の第２レジスタの値とを乗算する、複数の乗算器と、
前記複数の第２レジスタは、前段の第２レジスタの値と、前記乗算した結果と前記最上位の第２レジスタの値との乗算結果と、のＸＯＲを各々保持する請求項１から３のいずれか一項に記載の多項式除算回路。
【請求項５】
請求項１から４のいずれか一項に記載の多項式除算回路と、
前記多項式除算回路の算出結果から誤り位置多項式および誤り評価多項式を算出する演算部と、
を備えるユークリッド復号回路。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、多項式除算回路およびユークリッド復号回路に関する。
【背景技術】
【０００２】
光通信や無線通信においては、誤り訂正技術が用いられている。リードソロモン符号およびＢＣＨ符号等の誤り訂正符号の復号のために拡張ユークリッド互除法を用いることが知られている（例えば、特許文献１）。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開平１０−２８５０５２号公報
【発明の概要】
【発明が解決しようとする課題】
【０００４】
ユークリッド復号における多項式除算に適した多項式除算回路が求められている。
【０００５】
本発明の一実施形態は、ユークリッド復号における多項式除算に適した多項式除算回路およびユークリッド復号回路を提供することを目的とする。
【課題を解決するための手段】
【０００６】
本願発明の一実施形態は、生成多項式の連続根の個数を２ｔとしたとき、シンドローム多項式とｘ２ｔとの最大公約多項式を求める多項式除算回路であって、２ｔ個の複数の第１レジスタを有するワーキングシフトレジスタと、前段の値と、最上位段の値と前段の第１レジスタの値との乗算結果と、のＸＯＲが各々入力する２ｔ−１個の複数の第２レジスタを有する線形帰還シフトレジスタと、０を入力し、最下位段の第２レジスタに出力し、前記最上位段の第２レジスタの値が帰還しない第３レジスタと、最初の除算前に、前記最上位段の第２レジスタに１、他段の第２レジスタおよび前記第３レジスタに０を被除数多項式の係数としてそれぞれ入力し、２回目以降の除算前に、前記複数の第２レジスタおよび前記第３レジスタに前回の除算後の前記複数の第１レジスタの値を前記被除数多項式の係数として入力し、最初の除算前に、前記複数の第１レジスタに前記シンドローム多項式の係数を除数多項式の係数としてそれぞれ入力し、２回目以降の除算前に、前記複数の第１レジスタに前回除算後の前記複数の第２レジスタおよび前記第３レジスタを前記除数多項式の係数として入力する入力回路と、を備える多項式除算回路である。
【発明の効果】
【０００７】
本発明の一実施形態によれば、ユークリッド復号における多項式除算に適した多項式除算回路およびユークリッド復号回路を提供することができる。
【図面の簡単な説明】
【０００８】
【図１】図１は、実施例１を用いる復号回路のブロック図である。
【図２】図２は、実施例１を用いる復号回路の動作を示すフローチャートである。
【図３】図３は、実施例１における多項式算出部の処理を示す機能ブロック図である。
【図４】図４は、実施例１における除算ループごとの被除数、除数、剰余、商および多項式ａを示す図である。
【図５】図５は、実施例１におけるユークリッド復号回路周辺のブロック図である。
【図６】図６は、実施例１における多項式除算回路を示すブロック図である。
【図７】図７は、実施例１における多項式除算回路のステージを示すブロック図である。
【図８】図８は、実施例１における制御部の制御を示すフローチャートである。
【図９】図９は、実施例１におけるレジスタの値の例を示す図である。
【図１０】図１０は、実施例１におけるレジスタの例を示す図である。
【図１１】図１１は、実施例１における算出回路のブロック図である。
【図１２】図１２は、実施例１におけるプライオリティエンコーダの動作を示す図である。
【図１３】図１３は、実施例１における算出回路の一部を示すブロック図およびタイミングチャートである。
【図１４】図１４は、実施例１における算出回路の一部を示すブロック図およびタイミングチャートである。
【図１５】図１５は、実施例１の変形例１における多項式除算回路の一部を示すブロック図である。
【図１６】図１６は、比較例１における多項式除算回路を示す図である。
【発明を実施するための形態】
【０００９】
［本願発明の実施形態の説明］
最初に本願発明の実施形態の内容を列記して説明する。
（１）本願発明の一実施形態は、生成多項式の連続根の個数を２ｔとしたとき、シンドローム多項式とｘ２ｔとの最大公約多項式を求める多項式除算回路であって、２ｔ個の複数の第１レジスタを有するワーキングシフトレジスタと、前段の値と、最上位段の値と前段の第１レジスタの値との乗算結果と、のＸＯＲが各々入力する２ｔ−１個の複数の第２レジスタを有する線形帰還シフトレジスタと、０を入力し、最下位段の第２レジスタに出力し、前記最上位段の第２レジスタの値が帰還しない第３レジスタと、最初の除算前に、前記最上位段の第２レジスタに１、他段の第２レジスタおよび前記第３レジスタに０を被除数多項式の係数としてそれぞれ入力し、２回目以降の除算前に、前記複数の第２レジスタおよび前記第３レジスタに前回の除算後の前記複数の第１レジスタの値を前記被除数多項式の係数として入力し、最初の除算前に、前記複数の第１レジスタに前記シンドローム多項式の係数を除数多項式の係数としてそれぞれ入力し、２回目以降の除算前に、前記複数の第１レジスタに前回除算後の前記複数の第２レジスタおよび前記第３レジスタを前記除数多項式の係数として入力する入力回路と、を備える多項式除算回路である。これにより、ユークリッド復号における多項式除算に適した多項式除算回路を提供することができる。
（２）前記被除数多項式の次数をｎとし、前記除数多項式の次数をｍとしたとき、前記線形帰還シフトレジスタは、ｎ−ｍ＋１回シフトすることで、前記被除数多項式を前記除数多項式で除算することが好ましい。これにより、適切に除算を行うことができる。
（３）前記ワーキングシフトレジスタは、前記除算前にｎ−ｍ−１回シフトすることが好ましい。適切に除算を行うことができる。
（４）前記線形帰還シフトレジスタは、前記複数の第２レジスタに対応して設けられ、前記前段の第１レジスタの値がそれぞれ入力する複数の第４レジスタと、前記複数の第４レジスタに対応し設けられ、対応する第４レジスタの値と、最上位段の第１レジスタの値の逆元と、を乗算した結果を前記対応する第４レジスタに格納し、その後前記乗算した結果と前記最上位段の第２レジスタの値とを乗算する、複数の乗算器と、前記複数の第２レジスタは、前段の第２レジスタの値と、前記乗算した結果と前記最上位の第２レジスタの値との乗算結果と、のＸＯＲを各々保持することが好ましい。
（５）本願発明の一実施形態は、上記多項式除算回路と、前記多項式除算回路の算出結果から誤り位置多項式および誤り評価多項式を算出する演算部と、を備えるユークリッド復号回路である。
【００１０】
［本願発明の実施形態の詳細］
本発明の実施形態にかかる多項式除算回路の具体例を、以下に図面を参照しつつ説明する。なお、本発明はこれらの例示に限定されるものではなく、特許請求の範囲によって示され、特許請求の範囲と均等の意味および範囲内でのすべての変更が含まれることが意図される。
【実施例１】
【００１１】
[誤り訂正の説明]
実施例１が用いられるリードソロモン符号またはＢＣＨ符号における復号処理について説明する。なお符号に対する四則演算はガロア体（拡大体）演算を用いるがガロア体を省略して記載する。図１は、実施例１を用いる復号回路のブロック図である。復号回路９０は、シンドローム算出部９１、多項式算出部９２、誤り位置算出部９３、誤り値算出部９４、バッファ９５および誤り訂正部９６を備えている。シンドローム算出部９１、多項式算出部９２、誤り位置算出部９３、誤り値算出部９４、バッファ９５および誤り訂正部９６は、専用回路により、またはプロセッサがソフトウェアと協働することにより実現できる。以下の説明では、原始元αとする生成多項式Ｇ（ｘ）はα、α２、…、αｉ、…、α２ｔの２ｔ個の連続根を有するとする。
【００１２】
図２は、実施例１を用いる復号回路の動作を示すフローチャートである。図１および図２を参照し、シンドローム算出部９１は受信符号からシンドローム多項式Ｓ（ｘ）を算出する（ステップＳ９０）。シンドローム算出部９１は、Ｓ（ｘ）の全ての係数が０か判定する（ステップＳ９１）。Ｙｅｓのとき、シンドローム算出部９１は誤り訂正不要と判定し（ステップＳ９９）、誤り訂正を行わず終了する。
【００１３】
ステップＳ９１においてＮｏのとき、多項式算出部９２は、誤り位置多項式σ（ｘ）および誤り評価多項式η（ｘ）を算出する（ステップＳ９２）。σ（ｘ）およびη（ｘ）の算出は、式１の方程式を解くことにより行う。
σ（ｘ）・Ｓ（ｘ）＋φ（ｘ）・ｘ２ｔ＝η（ｘ）      （式１）
ここでφ（ｘ）は任意の多項式であり、Ｓ（ｘ）の次数が２ｔ−１以下なら、拡張ユークリッド互除法を用いて、σ（ｘ）とη（ｘ）が求まる。
【００１４】
多項式算出部９２はσ（ｘ）の０次の係数σ０は０か判定する（ステップＳ９３）。Ｙｅｓのとき、多項式算出部９２は、誤り訂正が不能と判定し（ステップＳ９８）、誤り訂正を行わず終了する。ステップＳ９３においてＮｏのとき、多項式算出部９２は、０次係数σ０で１次以上の係数を規格化する。
【００１５】
誤り位置算出部９３は、誤り位置を算出する（ステップＳ９４）。誤り位置は、誤り位置多項式σ（ｘ）に元α…α２ｔを順次代入し、σ（ｘ）＝０となるαｉのiである。誤り位置算出部９３は、誤り位置多項式σ（ｘ）の次数ｄｅｇ（σ（ｘ））と誤り位置の個数ｎとが一致しているか判定する（ステップＳ９５）。Ｎｏのとき、誤り位置算出部９３は、誤り訂正が不能と判定し（ステップＳ９８）、誤り訂正を行わず終了する。
【００１６】
ステップＳ９５においてＹｅｓのとき、誤り値算出部９４は誤り値を算出する（ステップＳ９６）。なお、ＢＣＨ符号の場合にはステップＳ９６は行わない。誤り訂正部９６は、誤り値を用いてバッファ９５により遅延した受信信号の誤りを訂正し訂正後符号を出力する（ステップＳ９７）。例えば誤り訂正部９６は受信符号の誤り位置に誤り値を加算する。ＢＣＨ符号の場合、誤り訂正部９６は、受信符号の誤り位置のビットを反転させる。以上により、誤り訂正が終了する。
【００１７】
[ユークリッド復号の説明]
誤り訂正のうち多項式算出部９２が行う誤り位置多項式σ（ｘ）および誤り評価多項式η（ｘ）の算出にユークリッド復号が用いられる。式１は、除算１回目の被除数および除数をそれぞれｘ２ｔおよびＳ（ｘ）とし、拡張ユークリッド互除法を用いることで、解くことができる。
【００１８】
図３は、実施例１における多項式算出部の処理を示す機能ブロック図である。図３に示すように、多項式算出部９２は、多項式除算部８０、遅延部８１ａから８１ｄ、判定部８２、多項式乗算部８３、多項式積算部８４、逆元算出部８５および乗算器８６ａおよび８６ｂを備えている。遅延部８１ａから８１ｄ、判定部８２、多項式乗算部８３、多項式積算部８４、逆元算出部８５および乗算器８６ａおよび８６ｂは、専用回路により、またはプロセッサがソフトウェアと協働することにより実現できる。
【００１９】
除算の回数をｉとしたとき、多項式ｒｉはｉ番目の除算の剰余である。遅延部８１ａから８１ｄは入力した多項式を除算一回遅延させて出力する。多項式除算部８０には、被除数および除数として多項式ｒｉ−２および多項式ｒｉ−１を入力する。多項式除算部８０は剰余の多項式ｒｉおよび商の多項式ｑｉを出力する。剰余の多項式ｒｉは遅延部８１ａに入力し、次の除算の除数の多項式ｒｉ−１となる。除数の多項式ｒｉ−１は遅延部８１ｂに入力し、次の除算の被除数の多項式ｒｉ−２となる。
【００２０】
判定部８２は剰余ｒｉの次数ｄｅｇ（ｒｉ）がｔ−１以下の場合、除算ループを完了する。
【００２１】
多項式乗算部８３は、多項式ａｉ−１と多項式除算部８０の商の多項式ｑｉとを乗算する。多項式積算部８４は、多項式乗算部８３が出力する多項式と多項式ａｉ−２とをＸＯＲし、多項式ａｉとして出力する。遅延部８１ｃは、多項式ａｉを除算一回遅延させ多項式ａｉ−１とする。遅延部８１ｄは、多項式ａｉ−１を除算一回遅延させ多項式ａｉ−２とする。
【００２２】
逆元算出部８５は、多項式ａｉの０次係数ａｉ（０）の逆元１／ａｉ（０）を出力する。乗算器８６ａは多項式ａｉに１／ａｉ（０）を乗算し出力する。除算が終了するｄｅｇ（ｒｉ）≦ｔ−１となるｉ＝ＮにおけるａＮ／ａＮ（０）が誤り位置多項式σ（ｘ）となる。乗算器８６ｂは多項式ｒｉに１／ａｉ（０）を乗算し出力する。ｉ＝ＮにおけるｒＮ／ａＮ（０）が誤り評価多項式η（ｘ）となる。
【００２３】
図４は、実施例１における除算ループごとの被除数、除数、剰余、商および多項式ａを示す図である。図４に示すように、最初の除算（すなわちｉ＝１）において，被除数の多項式をｒ−１＝ｘ２ｔとし、除数の多項式をｒ０＝Ｓ（ｘ）とし、ａ−１およびａ０をそれぞれ０および１とする。多項式除算部８０は、剰余の多項式ｒ１および商の多項式ｑ１を出力する。多項式積算部８４が出力する多項式ａ１は１・ｑ１である。
【００２４】
２回目の除算の被除数および除数はそれぞれ１回目の除数の多項式ｒ０および剰余の多項式ｒ１となる。多項式ａ２はａ１・ｑ２＋１となる。３回目の除算の被除数の多項式および除数の多項式はそれぞれ２回目の除数の多項式ｒ１および除数の多項式ｒ２となる。多項式ａ３はａ２・ｑ３＋ａ１となる。
【００２５】
ｉ＝Ｎにおいて除算ループが完了すると、被除数、除数、剰余および商の多項式は、それぞれｒＮ−２、ｒＮ−１、ＮおよびａＮである。ａＮ＝ａＮ−１・ｑＮ＋ａＮ−２である。誤り評価多項式η（ｘ）は、多項式ｒＮをａＮの０次の係数ａＮ（０）で規格化したｒＮ／ａＮ（０）である。誤り位置多項式σ（ｘ）は、多項式ａＮをａＮ（０）で規格化したａＮ／ａＮ（０）である。
【００２６】
［ユークリッド復号回路の説明］
図５は、実施例１におけるユークリッド復号回路周辺のブロック図である。ユークリッド復号回路６０は、図１および図３の多項式算出部９２に相当する。多項式除算回路５０は、図３の多項式除算部８０に相当する。
【００２７】
図５に示すように、ユークリッド復号回路６０は、多項式除算回路５０、算出回路５２、制御部５６、メモリ５４および積和演算部５８を備えている。多項式除算回路５０にはシンドローム算出部９１より２ｔワードのシンドローム多項式Ｓ（ｘ）の係数が入力する。多項式除算回路５０は、除算ごとに商の多項式の係数をメモリ５４に出力し、除算完了時に剰余の多項式の係数をメモリ５４に出力し、除算ごとに２ｔワードのＳＲの値を算出回路５２に出力する。
【００２８】
算出回路５２は、除算ごとに２ｔワードのＳＲの値から、ａｌｌ０、ｎ、ｍ、ｓ１およびｓ２を制御部５６に出力する。ａｌｌ０はシンドローム多項式Ｓ（ｘ）の係数が全て０かを示すフラグであり、Ｓ（ｘ）の係数が全て０のとき１である。ｎは被除数多項式の次数、ｍは除数多項式の次数、ｓ１は次の除算のＬＦＳＲ１０のシフト数、ｓ２は次の除算の設定前のＷＳＲ２０のシフト数である。ｓ１＝ｎ−ｍ＋１であり、ｓ２＝ｎ−ｍ−１である。詳細は後述する。制御部５６は、算出回路５２ｂの出力に基づき、多項式除算回路５０およびメモリ５４を制御する。
【００２９】
メモリ５４は、レジスタ等のメモリ群であり、商ＦＩＦＯ（First In First Out）６１および商項数ＦＩＦＯ６２を記憶する。メモリ５４は、除算回数（ｌｐ＿ｃｎｔ）６３、完了ステータス６４および完了時の剰余６５を記憶する。完了ステータス６４は、図３の判定部８２が除算ループの完了を判定するとイネーブルとなる。積和演算部５８は、図３の多項式乗算部８３、多項式積算部８４、遅延部８１ｃ、８１ｄ、逆元算出部８５、乗算器８６ａおよび８６ｂを含み、σ（ｘ）およびη（ｘ）を算出する。σ（ｘ）は誤り位置算出部９３、η（ｘ）は誤り位置算出部に出力される。
【００３０】
［多項式除算回路のブロックの説明］
図６は、実施例１における多項式除算回路を示すブロック図である。図６に示すように、多項式除算回路５０は、ＬＦＳＲ（線形帰還シフトレジスタ）１０、ＷＳＲ（ワーキングシフトレジスタ）２０、ＳＲ（シフトレジスタ）３０、選択回路４０、４２、４４、逆元算出部４６および乗算器４８を備えている。
【００３１】
ＬＦＳＲ１０は２ｔ−１段のステージ１１を有する。ＳＲ３０はＬＦＳＲ１０の前段に設けられている。ＷＳＲ２０は２ｔ段のステージ２１を有している。ＬＦＳＲ１０およびＷＳＲ２０は上位側（すなわち後段側）が高次側となる。
【００３２】
選択回路４０は、除算実行回数をカウントするカウンタ変数ｌｐ＿ｃｎｔが非０（非０なら真）かを選択信号とし選択信号が０のとき、ｘ２ｔ−１の各次の係数をＬＦＳＲ１０およびＳＲ３０にｐｉｎとして出力する。ｘ２ｔ−１の最上位の係数は１であり、その他の係数は０である。選択回路４０は、ｌｐ＿ｃｎｔが非０のとき、ＷＳＲ２０の各ステージ２１の値をＬＦＳＲ１０の各段およびＳＲ３０にｐｉｎとして出力する。ＷＳＲ２０の各ステージ２１の下位２ｔ−１の値はｇｘｉｎとしてＬＦＳＲ１０に出力される。
【００３３】
選択回路４２は、ｌｐ＿ｃｎｔが０のとき、シンドローム多項式Ｓ（ｘ）の各次の係数をＷＳＲ２０にｐｉｎとして出力する。選択回路４２は、ｌｐ＿ｃｎｔが非０のとき、ＬＦＳＲ１０およびＳＲ３０の値をＰｉｎとしてＷＳＲ２０に出力する。
【００３４】
逆元算出部４６は、ＷＳＲ２０の最上位のステージ２１の値の逆元を算出する。選択回路４４は、選択信号Ｓｅｌ［１］が０のとき、ＬＦＳＲ１０の最上位のステージ１１の値を帰還値ｆｂｏｕｔとしてＬＦＳＲ１０の各ステージ１１に出力する。選択回路４４は、選択信号Ｓｅｌ［１］が１のとき、逆元算出部４６の出力を帰還値ｆｂｏｕｔとしてＬＦＳＲ１０の各ステージ１１に出力する。乗算器４８は、除算ループごとに、ＬＦＳＲ１０の最上位のステージ１１の値を商多項式の係数として、メモリ５４の商ＦＩＦＯ６１として出力する。除算ループが完了したとき、ＷＳＲ２０は、各ステージ２１の値を剰余多項式の係数として出力する。
【００３５】
図７は、実施例１における多項式除算回路のステージを示すブロック図である。図７では、ＬＦＳＲ１０の最上位のステージ１１、ＷＳＲ２０の最上位および最下位のステージ２１、並びにＳＲ３０を図示している。ＬＦＳＲ１０およびＷＳＲ２０の他のステージ１１および２１は最上位と同様である。
【００３６】
ＬＦＳＲ１０の各ステージ１１は、レジスタ１２、１６、選択回路１３、１７、加算器１４および乗算器１５を備えている。ＷＳＲ２０の各ステージ２１は、レジスタ２２および選択回路２３を備えている。ＳＲ３０は、レジスタ３２および選択回路３３を備えている。
【００３７】
最上位段のステージ１１において、選択回路１３は、信号ｌｏａｄ／ｓｈｉｆｔ＿ｅｎ１に基づき、レジスタ１２の出力、加算器１４の出力および選択回路４０の出力の１つをレジスタ１２に出力する。ｌｏａｄ／ｓｈｉｆｔ＿ｅｎ１は２ビットの信号であり、上位ビットがｌｏａｄ信号、下位ビットがｓｈｉｆｔ＿ｅｎ１信号である。レジスタ１２の出力はＬＦＳＲ（２ｔ−１）＿ｏｕｔである。
【００３８】
加算器１４は、前段のステージ１１のレジスタ１２の値ＬＦＳＲ（２ｔ−２）＿ｏｕｔと乗算器１５の出力とを加算（ＸＯＲ）し選択回路１３に出力する。乗算器１５は、選択回路４４の帰還値ｆｂｏｕｔとレジスタ１６の値を乗算する。選択回路１７は、選択信号ｓｅｌ［１：０］に基づきレジスタ１６の出力、前段のＷＳＲ２０のステージ２１のレジスタ２２の値および乗算器１５の出力の１つをレジスタ１６に出力する。選択信号Ｓｅｌ[１：０]は２ビットの信号であり、１ビット目（上位ビット）は選択信号Ｓｅｌ［１］に相当する。
【００３９】
最上位のステージ２１において、選択回路２３は、信号ｌｏａｄ／ｓｈｉｆｔ＿ｅｎ２に基づき、レジスタ２２の値、前段のステージ２１のレジスタ２２の値ＳＲ（２ｔ−２）＿ｏｕｔおよび選択回路４２の出力の１つをレジスタ２２に出力する。ｌｏａｄ／ｓｈｉｆｔ＿ｅｎ２は２ビットの信号であり、上位ビットがｌｏａｄ信号、下位ビットがｓｈｉｆｔ＿ｅｎ２信号である。最上位のレジスタ２２の値はＳＲ（２ｔ−１）＿ｏｕｔである。最下位のステージ２１においては、選択回路２３に０が入力する。レジスタ２２の値はＳＲ（０）である。
【００４０】
ＳＲ３０において、選択回路３３は、信号ｌｏａｄ／ｓｈｉｆｔ＿ｅｎ１に基づき、レジスタ３２の値、０および選択回路４０の出力の１つをレジスタ３２に出力する。レジスタ３２の値はＬＦＳＲの最下位のステージ１１の加算器１４に入力する。
【００４１】
［多項式除算回路の制御の説明］
図８は、実施例１における制御部の制御を示すフローチャートである。
【００４２】
最初はｌｐ＿ｃｎｔ＝０となっている。制御部５６は、シンドローム算出部９１からシンドローム多項式Ｓ（ｚ）の算出終了を示すトリガを受信すると、ロードイネーブルとする（ステップＳ１０）。制御部５６は、ｌｏａｄ信号を１とする。ｓｈｉｆｔ＿ｅｎ１信号およびｓｈｉｆｔ＿ｅｎ２信号は０である。よって、ｌｏａｄ／ｓｈｉｆｔ＿ｅｎ１＝２およびｌｏａｄ／ｓｈｉｆｔ＿ｅｎ２＝２となる。
【００４３】
図７の選択回路１３および３３は、選択回路４０の出力を選択する。ｌｐ＿ｃｎｔ＝０のため、ＬＦＳＲ１０の最上位の選択回路４０は１を選択し、ＬＦＳＲ１０の他の選択回路４０は０を選択する。よって、ＬＦＳＲ１０の最上位のレジスタ１２に１、その他のレジスタ１２に０が入力される。ＳＲ３０のレジスタ３２に０が入力される。選択回路２３はＳ（ｘ）を選択する。よって、ＷＳＲ２０のレジスタ２２にＳ（ｘ）の係数が入力される。
【００４４】
図９は、実施例１におけるレジスタの値の例を示す図であり、ＬＦＳＲ１０の各ステージ１１のレジスタ１２、ＷＳＲ２０の各ステージ２１のレジスタ２２およびＳＲ３０のレジスタ３２を示している。説明を簡略化するため、ｔ＝３とする。このとき、ＬＦＳＲ１０は２ｔ−１＝５段、ＷＳＲ２０は２ｔ＝６段である。
【００４５】
図９のＡにおいて、除算１回目では、被除数はｘ２ｔ＝ｘ６であり、被除数の次数は６であり、被除数多項式の係数は１００００００（左が上位）である。最初の除数はシンドローム多項式Ｓ（ｘ）であり、ここでは除数の次数は５であり、除数多項式の係数は、Ｓ５、Ｓ４、Ｓ３、Ｓ２、Ｓ１、Ｓ０である。被除数のうち上位２ｔ−１の係数はＬＦＳＲ１０のレジスタ１２に入力し、Ｓ５からＳ０がＷＳＲ２０のレジスタ２２に入力する。
【００４６】
図８に戻り、算出回路５２は、ＷＳＲ２０のレジスタ２２の値からａｌｌ０、ｎ、ｍ、ｓ１およびｓ２を算出する。制御部５６はａｌｌ０が１か判定する（ステップＳ１２）。ａｌｌ０が１のときＳ（ｘ）の全ての係数が０であり、誤りがないことを示している。Ｙｅｓのとき、制御部５６は、完了処理１として誤り処理が不要との完了処理１を行なう（ステップＳ３２）。制御部５６は、ｌｐ＿ｃｎｔ＝０とし（ステップＳ３４）、除算ループを終了する。
【００４７】
ステップＳ１２においてＮｏのとき、誤りがあるためステップＳ１４に進む。制御部５６は、ｍ≦ｔ−１か判定する（ステップＳ１４）。ｍ≦ｔ−１のとき、除算ループを終了する。通常は除算１回目実行前はＮｏである。Ｎｏのとき、制御部５６は除数の最上位係数を非０とするためのシフト回数ｓ２を算出する（ステップＳ１６）。シフト回数は、ｓ２＝ｎ−ｍ−１である。除算１回目は、被除数ｘ２ｔの次数ｎは２ｔであり、除数Ｓ（ｘ）の次数ｍは、Ｓ（ｘ）の最上位の係数が非０であれば２ｔ−１である。これにより、図９の例ではｓ２＝０である。Ｓ（ｘ）の最上位の係数が０のとき、ｓ２は＞０となる。
【００４８】
ステップＳ１６においてＮｏのとき、制御部５６は、ＷＳＲ２０をｓ２回シフトする（ステップＳ１８）。制御部５６は、ｓｈｉｆｔ＿ｅｎ２信号を１とすることでＷＳＲ２０をシフトできる。ステップＳ１８により、ＷＳＲ２０の最上位のステージ２１のレジスタ２２は非０となる。ステップＳ１６においてＹｅｓのとき、ＷＳＲ２０の最上位は非０のためステップＳ１８を行わない。
【００４９】
次に制御部５６は、ｓｅｌ信号を２、３および０とトグルする（ステップＳ２０）。
【００５０】
ステップＳ２０について説明する。図１０は、実施例１におけるレジスタの例を示す図であり、ＬＦＳＲ１０の各ステージ１１のレジスタ１６を示している。制御部５６は、ｓｅｌ［１：０］を２進法表現で１０ｂすなわち１０進法表現で２とする。図７の選択回路４４は逆元算出部４６の出力を選択する。これにより、帰還値ｆｂｏｕｔはＷＳＲ２０の最上位のレジスタ２２の値Ｓ５の逆元１／Ｓ５となる。選択回路１７は、前段のＷＳＲ２０のレジスタ２２の値を選択する。これにより、レジスタ１６には上位からＳ４、Ｓ３、Ｓ２、Ｓ１およびＳ０が保持される。乗算器１５は帰還値ｆｂｏｕｔとレジスタ１６の値を積算する。これにより、乗算器１５の出力は、上位からＳ４／Ｓ５、Ｓ３／Ｓ５、Ｓ２／Ｓ５、Ｓ１／Ｓ５およびＳ０／Ｓ５となる。
【００５１】
次のクロックで、制御部５６は、ｓｅｌ［１：０］を１１ｂすなわち３とする。これにより、選択回路１７は乗算器１５の出力を選択する。よって、レジスタ１６には、上位からＳ４／Ｓ５、Ｓ３／Ｓ５、Ｓ２／Ｓ５、Ｓ１／Ｓ５およびＳ０／Ｓ５が保持される。
【００５２】
次に、制御部５６は、ｓｅｌ［１：０］を００ｂすなわち０とする。選択回路４４は最上位のレジスタ１２の出力ｆｂｏを選択する。除算１回目ではｆｂｏ＝１である。選択回路１７はレジスタ１６の値を選択する。よって、レジスタ１６は、Ｓ４／Ｓ５、Ｓ３／Ｓ５、Ｓ２／Ｓ５、Ｓ１／Ｓ５およびＳ０／Ｓ５を保持する。乗算器１５の出力は、上位からＳ４／Ｓ５×ｆｂｏ、Ｓ３／Ｓ５×ｆｂｏ、Ｓ２／Ｓ５×ｆｂｏ、Ｓ１／Ｓ５×ｆｂｏおよびＳ０／Ｓ５×ｆｂｏとなる。
【００５３】
以上のようにステップＳ２０の後、図９のＢに示すように、ＬＦＳＲ１０のレジスタ１６には上位からＳ４／Ｓ５、Ｓ３／Ｓ５、Ｓ２／Ｓ５、Ｓ１／Ｓ５およびＳ０／Ｓ５が保持される。これにより、除算１回目の準備が整う。
【００５４】
図８に戻り、制御部５６は、ＬＦＳＲ１０をｓ１回シフトする（ステップＳ２２）。制御部５６は、ｓｈｉｆｔ＿ｅｎ１信号を１とすることでＬＦＳＲ１０をシフトできる。除算１回目は、被除数の次数ｎ＝２ｔ、除数の次数ｍ＝２ｔ−１であり、ｓ１＝ｎ−ｍ＋１＝２であり、ＬＦＳＲ１０を２回シフトする。図９のＢの例では、被除数の１００００００のうち下位の２つはＬＦＳＲ１０からはみ出しているので、この分２回シフトすることに相当する。
【００５５】
図９のＣに示すように、ＬＦＳＲ１０のレジスタ１２は上位からｒ４、ｒ３、ｒ２、ｒ１およびｒ０となる。ＳＲ３０のレジスタ３２には０が入力される。ｒ４からｒ０は剰余の係数である。被除数の次数が２ｔ＝６、除数の次数が２ｔ−１＝５のとき、剰余の次数は２ｔ−２＝４である。よって、剰余多項式の係数の数は最大で２ｔ−１＝５であり、ＬＦＳＲ１０の段数は２ｔ−１＝５段あればよい。
【００５６】
図８に戻り、制御部５６は、ＬＦＳＲ１０のシフトと同じイネーブル信号で、商多項式の係数（商ＦＩＦＯ６１）をメモリ５４に書き込む（ステップＳ２３）。商ＦＩＦＯ６１は、乗算器４８がＬＦＳＲ１０の最上位のレジスタ１２の値に逆元算出部４６の出力を乗算した値である。図９のＣの例では、商ＦＩＦＯ６１はｒ４／Ｓ５となる。
【００５７】
制御部５６は、ｓ１を商項数ＦＩＦＯ６２としてメモリ５４に書き込む（ステップＳ２４）。制御部５６は、ｌｐ＿ｃｎｔ（ループ回数カウンタ）をカウントアップする（ステップＳ２６）。以上により、除算１回目の処理が終了する。
【００５８】
除算２回目において、制御部５６は、ロードイネーブルとする（ステップＳ１０）。制御部５６は、ｌｏａｄ信号を１とする。ｌｏａｄ／ｓｈｉｆｔ＿ｅｎ１＝２およびｌｏａｄ／ｓｈｉｆｔ＿ｅｎ１＝２となる。
【００５９】
図７の選択回路１３および３３は、選択回路４０の出力を選択する。ｌｐ＿ｃｎｔが非０のため、選択回路４０はＷＳＲ２０の同じステージのレジスタ２２を選択し、選択回路２３はＬＦＳＲ１０およびＳＲ３０の同じステージのレジスタ１２および３２を選択する。これにより、ＬＦＳＲ１０およびＳＲ３０とＷＳＲ２０の値が入れ替わる。
【００６０】
図９のＤに示すように、ＬＦＳＲ１０のレジスタ１２には上位からＳ５、Ｓ４、Ｓ３、Ｓ２およびＳ１が保持され、レジスタ３２にはＳ０が保持される。ＷＳＲ２０のレジスタ２２には上位からｒ４、ｒ３、ｒ２、ｒ１、ｒ０および０が保持される。
【００６１】
除算１回目と同様に制御部５６はステップＳ１２からＳ２０を行なう。図９のＥに示すように、ＬＦＳＲ１０のレジスタ１６には上位からｒ３／ｒ４、ｒ２／ｒ４、ｒ１／ｒ４、ｒ０／ｒ４および０が保持される。これにより、除算２回目の準備が整う。なお、ｒ４は非０としている。
【００６２】
制御部５６はステップＳ２２を行なう。図９のＦに示すように、ＬＦＳＲ１０のレジスタ１２は上位からｒ３´、ｒ２´、ｒ１´、ｒ０´および０となる。ＳＲ３０のレジスタ３２には０が入力されるため、ＬＦＳＲ１０は下位のレジスタ１２は０となる。
【００６３】
ステップＳ２３において、制御部５６は、商ＦＩＦＯ６１としてｒ３´／ｒ４を出力する。ステップＳ２４において、制御部５６は、商項数ＦＩＦＯ６２としてｓ１を出力する。その後、ステップＳ１０に戻る。
【００６４】
ステップＳ１４においてＹｅｓのとき、ｍはｔ−１以下となり除算が終了する。制御部５６は、ｓｈｉｆｔ＿ｅｎ２をｎ回（すなわちＷＳＲ２０に格納された剰余多項式の次数）シフトする（ステップＳ２８）。これにより、メモリ５４に剰余多項式の係数が剰余６５として出力される。この剰余多項式は後段の誤り値計算に用いられる。制御部５６は、完了処理２を行う（ステップＳ３０）。完了処理２により後段の積和演算部で必要となる除算回数ｌｐ＿ｃｎｔを図５のメモリ５４に除算回数６３として保存した後、次の除算に備えｌｐ＿ｃｎｔ＝０とする（ステップＳ３４）。
【００６５】
［算出回路の説明］
図１１は、実施例１における算出回路のブロック図である。図１１に示すように、算出回路５２は、ＯＲ回路７０、プライオリティエンコーダ７１、ＮＯＲ回路７２、整数加算器７３、レジスタ７４、７５、遅延器７６、選択回路７７および整数加減算器７８を備えている。
【００６６】
多項式除算回路５０のＷＳＲ２０の各レジスタ２２から２ｔワードのデータがＯＲ回路７０に入力する。ＯＲ回路７０は上位ｔ−１のＯＲ回路７０ａと下位ｔ＋１ワードのＯＲ回路７０ｂとを有する。ＯＲ回路７０ａは上位ｔ−１ワードの各ワードのＯＲを行なう。ＯＲ回路７０ｂは下位ｔ＋１ワードの全てのＯＲを行なう。ＮＯＲ回路７２は、ＯＲ回路７０ａのｔ−１ビットとＯＲ回路７０ｂの出力をＮＯＲし結果をａｌｌ０として出力する。これにより、ＷＳＲ２０の全レジスタ１２が０のときａｌｌ０は１となり、その他のときａｌｌ０は０となる。
【００６７】
図１２は、実施例１におけるプライオリティエンコーダの動作を示す図である。図１２に示すように、ＷＳＲ２０の上位ｔ−１ワードが各々ＯＲ回路７０ａによりＯＲされプライオリティエンコーダ７１に入力する。ＷＳＲ２０のレジスタ２２が非０のとき、プライオリティエンコーダ７１の対応する入力は１となり、ＷＳＲ２０のレジスタ２２が０のとき、プライオリティエンコーダ７１の対応する入力は０となる。
【００６８】
図１２の下図は、プライオリティエンコーダ７１の入力と出力を示している。最上位の入力が１のとき、他の位の入力によらず出力ｅｎｃは−１（２の補数の２進数表示で１１１…１１１）となる。最上位の入力が０、次の位の入力が１のとき、他の位の入力によらず出力ｅｎｃは−２（１１１…１１０）となる。同様に最初に１となる位が３番目および４番目の位のときに出力ｅｎｃはそれぞれ−３（１１１…１０１）および−４（１１１…１００）となる。図１２の上図では、ＷＳＲ２０の最上位は非０であるため、ｅｎｃは−１となる。ｍ≦ｔ−１のときに除算ループが完了するため、プライオリティエンコーダ７１は上位ｔ−１ワードについてエンコードすれば十分である。
【００６９】
図１１では、選択回路７７は、ｌｐ＿ｃｎｔが０のとき２ｔを選択し、非０のときレジスタ７５を選択する。そこで、ｌｐ＿ｃｎｔが非０と０のときとで分けて整数加算器７３、レジスタ７４、７５および遅延器７６の動作を説明する。
【００７０】
図１３は、実施例１における算出回路の一部を示すブロック図およびタイミングチャートであり、ｌｐ＿ｃｎｔが非０のときを示している。図１３の上図がブロック図であり、下図がタイミングチャートである。図１３に示すように、時刻ｔ０において、ｌｏａｄ信号が１となる（図８のステップＳ１０に相当する）と、ＬＦＳＲ１０に今回の被除数がロードされ、ＷＳＲ２０に今回の除数がロードされる。時刻ｔ１において、レジスタ７５は前回の除算の除数の次数ｍを今回の被除数の次数ｎとして出力する。時刻ｔ２において、プライオリティエンコーダ７１はＷＳＲ２０のロードされた今回の除数のｅｎｃを出力する。時刻ｔ３において整数加算器７３はｎ＋ｅｎｃを出力する。時刻ｔ４において遅延器７６がＬｏａｄ信号を遅延して出力すると、時刻ｔ５において、レジスタ７４はｎ＋ｅｎｃを今回の除数の次数ｍとして出力する。
【００７１】
以上により、前回の被除数の次数が今回の除数の次数ｎとなる。ＷＳＲ２０のロードされた除数の最上位が非０の場合、ｅｎｃ＝−１であり、除数の次数ｍはｎ−１となる。除数の最上位が０の場合、最大の非０の位に応じｍ＝ｎ＋ｅｎｃとなる。
【００７２】
図１４は、実施例１における算出回路の一部を示すブロック図およびタイミングチャートであり、ｌｐ＿ｃｎｔ＝０のときを示している。図１４の上図がブロック図であり、下図がタイミングチャートである。図１４に示すように、ｌｐ＿ｃｎｔ＝０では、ｎ＝２ｔである。時刻ｔ０において、Ｌｏａｄ信号が１となると、時刻ｔ２において、プライオリティエンコーダ７１はｅｎｃを出力する。ｅｎｃはシンドローム多項式Ｓ（ｘ）の非０の最大の位に対応する。時刻ｔ３において整数加算器７３は２ｔ＋ｅｎｃを出力する。時刻ｔ４において遅延器７６がＬｏａｄ信号を遅延して出力すると、時刻ｔ５においてレジスタ７４は２ｔ＋ｅｎｃを今回の除数の次数ｍとして出力する。
【００７３】
図１１に戻り、整数加減算器７８はｓ１＝ｎ−ｍ＋１およびｓ２＝ｎ−ｍ−１を出力する。
【００７４】
［実施例１の変形例１］
図１５は、実施例１の変形例１における多項式除算回路の一部を示すブロック図である。図１５に示すように、ＬＦＳＲ１０を高次側ＬＦＳＲ１０ａと低次側ＬＦＳＲ１０ｂとに分割する。遅延器４９は帰還値ｆｂｏｕｔ、ｌｏａｄおよびｓｈｉｆｔ＿ｅｎ１を１クロック遅延させ低次側ＬＦＳＲ１０ｂに出力する。ｓｈｉｆｔ＿ｅｎ１は２クロックで１回イネーブルする。
【００７５】
実施例１の変形例１では、帰還の負荷を軽くでき、遅延時間が小さくなる。負荷の大きい多項式除算回路５０ａを２クロック動作できるため、ユークリッド復号回路の動作周波数を向上させることができる。よって、光通信用途のように高ビットレートが要求されるアプリケーションにおいて効果が大きい。
【００７６】
［比較例１］
図１６は、比較例１における多項式除算回路を示す図である。図１６に示すように、比較例１では、多項式除算回路５０ａは、ＬＦＳＲ１０ｃを備えている。ＬＦＳＲ１０ｃの各ステージ１１は、レジスタ１２、加算器１４および乗算器１５を有している。除数の係数は上位からｇｍ、ｇｍ−１、…、ｇ２、ｇ１およびｇ０である。乗算器４８は最上位のレジスタ１２の値と除数の最上位の係数の逆元１／ｇｍを除算する。各ステージ１１では、乗算器１５が１／ｇｍと除数の各係数とを乗算する。加算器１４は、前段のレジスタ１２の値と乗算器１５の出力とを加算しレジスタ１２に出力する。
【００７７】
比較例１の除算の方法は、まず、各ステージ１１のレジスタ１２を０とする。被除数の係数を順次が最下位のステージ１１から入力する。最上位のレジスタ１２は０であるため、乗算器１５の出力は全てのステージ１１で０である。最上位のレジスタ１２の値が非０となるまで、シフトインを繰り返す。被除算の最下位の係数が最下位のレジスタ１２に入力されると除算が終了する。乗算器４８の出力が商多項式の係数として出力される。レジスタ１２の値が剰余の係数となる。
【００７８】
ユークリッド復号の場合には、除数を次回の被除数とし、剰余を次回の除数として、剰余の次数がｔ−１以下となるまで除算を繰り返す。
【００７９】
比較例１では、被除数をＬＦＳＲ１０ｃに順次シフトインする。また、除算ごとに剰余をバッファ等のメモリに格納し、前回の除算の除数を被除数としてＬＦＳＲ１０ｃに入力し、前回の除算の剰余を乗算器１５に入力する。このため、高速な除算を行うことができない。さらに、ＬＦＳＲ１０ｃのシフトごとに乗算器４８が１／ｇｍと最上位のレジスタ１２の値とを乗算し、乗算器１５が１／ｇｍとｇｍ−１からｇ０を乗算する。このため、乗算器４８および１５の負荷が重くなる。
【００８０】
ユークリッド復号回路では、多項式除算回路は、シンドローム多項式Ｓ（ｘ）とｘ２ｔとの最大公約多項式を求める。この場合、被除数と除数の次数の差はほとんどの場合１である。このため、比較例１のように、被除数を順次シフトインする方法は無駄が多い。
【００８１】
［実施例１およびその変形例の効果］
実施例１およびその変形例によれば、ＷＳＲ２０は、２ｔ個の複数のレジスタ２２（第１レジスタ）を有する。ＬＦＳＲ１０は、前段のレジスタ１２の値と、最上位段のレジスタ１２の値と前段のレジスタ２２の値との乗算結果と、のＸＯＲが各々入力する２ｔ−１個の複数のレジスタ１２（第２レジスタ）を有する。ＳＲ３０のレジスタ３２は、０が入力し、最下位段のレジスタ１２に出力し、最上位段のレジスタ２２の値が帰還しない。
【００８２】
選択回路４０（入力回路）は、最初の除算前に、最上位段のレジスタ１２に１、他段のレジスタ１２およびレジスタ３２に０を被除数多項式の係数としてそれぞれ入力する。選択回路４０は、２回目以降の除算前に、複数のレジスタ１２およびレジスタ３２に前回除算後の複数のレジスタ２２の値を被除数多項式の係数として入力する。選択回路４２（入力回路）は、最初の除算前に、複数のレジスタ２２にシンドローム多項式Ｓ（ｘ）の係数を除数多項式の係数としてそれぞれ入力し、２回目以降の除算前に、複数のレジスタ２２に前回除算後の複数のレジスタ１２およびレジスタ３２の値を除数多項式の係数として入力する。
【００８３】
最初の除算では被除数の次数は２ｔであり、除数の次数は２ｔ−１である。このため、最初の除算後の剰余の次数は最大でも２ｔ−２である。よって、図９のＢのように、ＬＦＳＲ１０は２ｔ−１段あれば十分である。そこで、ＷＳＲ２０の段数を２ｔとし、ＬＦＳＲ１０の段数を２ｔ−１とする。最初の除算の被除数の次数は２ｔであるが、最上位以外は０である。このため、ＬＦＳＲ１０の前段にＳＲ３０を設け、レジスタ３２に０を入力するようにする。これにより、比較例１の一般的な多項式除算回路を用いるのに比べ、ＷＳＲ２０およびＬＦＳＲ１０の段数を小さくできる。よって、多項式除算回路を小型化できる。
【００８４】
さらに、選択回路４０および４２は最初の除算の前にＬＦＳＲ１０およびＷＳＲ２０にｘ２ｔおよびＳ（ｘ）の係数を入力する。これにより、最初の除算の被除数をｘ２ｔとし、除数をＳ（ｘ）にセットできる。選択回路４０および４２は２回目以降の除算の前にＬＦＳＲ１０およびＳＲ３０の値とＷＳＲ２０の値を入れ替える。これにより、前回の除数を被除数とし、前回の剰余を除数にセットすることができる。ユークリッド復号における多項式除算では、ほとんどの場合、被除数の次数ｎは除数の次数ｍより１大きい。よって、少ないシフト回数で除算できる。このため、比較例１のように、被除数多項式の係数をシフトインするのに比べ、多項式の除算を高速化できる。また、比較例１のように、除算結果をバッファに格納するのに比べ、多項式の除算を高速化できる。以上により、ユークリッド復号における多項式除算に適した多項式除算回路を提供できる。
【００８５】
被除数多項式の次数をｎとし、除数多項式の次数をｍとしたとき、ＬＦＳＲ１０は、ｎ−ｍ＋１回シフトすることで、被除算多項式を除算多項式で除算する。これにより、被除数多項式の次数と被除数多項式の次数の差が１以外の場合でも適切に除算を行うことができる。
【００８６】
ＷＳＲ２０は、除算前にｎ−ｍ−１回シフトする。これにより、除数の最上位が１の場合も適切に除算を行うことができる。
【００８７】
ＬＦＳＲ１０は、レジスタ１２に対応して設けられたレジスタ１６とレジスタ１６に対応して設けられた乗算器１５を備える。複数のレジスタ１６（第４レジスタ）は前段のレジスタ２２の値がそれぞれ入力する。複数の乗算器１５は、対応するレジスタ１６の値と、最上位段のレジスタ２２の値の逆元と、を乗算した結果を対応するレジスタ１６に格納する。その後、乗算した結果と最上位段のレジスタ２２の値とを乗算する。複数のレジスタ１２は、前段のレジスタ１２の値と、乗算器１５の乗算結果と、のＸＯＲを各々保持する。これにより、比較例１のように、乗算器１５および４８がシフトごとに逆元を算出するのに比べ乗算回数を削減できる。
【００８８】
図５のように、ユークリッド復号回路６０が実施例１の多項式除算回路５０と、多項式除算回路５０の算出結果から誤り位置多項式σ（ｘ）を算出する積和演算部５８（演算部）と、を備える。このように、ユークリッド復号回路６０に適した多項式除算回路を用いることができる。
【００８９】
今回開示された実施の形態はすべての点で例示であって制限的なものではないと考えられるべきである。本発明の範囲は、上記した意味ではなく、特許請求の範囲によって示され、特許請求の範囲と均等の意味および範囲内でのすべての変更が含まれることが意図される。
【符号の説明】
【００９０】
１０、１０ｃ  ＬＦＳＲ
１１、２１  ステージ
１２、１６、２２、３２、７４、７５  レジスタ
１３、１７、２３、３３、４０、４２、４４、７７  選択回路
１４  加算器
１５、４８、８６ａ、８６ｂ  乗算器
２０  ＷＳＲ
３０  ＳＲ
４６  逆元算出部
４９、７６  遅延器
５０、５０ａ  多項式除算回路
５２  算出回路
５４  メモリ
５６  制御部
５８  積和演算部
６０  ユークリッド復号回路
６１  商ＦＩＦＯ
６２  商項数ＦＩＦＯ
６３  除算回数
６４  完了ステータス
６５  剰余
７０、７０ａ、７０ｂ  ＯＲ回路
７１  プライオリティエンコーダ
７２  ＮＯＲ回路
７３  整数加算器
７８  整数加減算器
８０  多項式除算部
８１ａ、８１ｂ、８１ｃ、８１ｄ  遅延部
８２  判定部
８３  多項式乗算部
８４  多項式積算部
８５  逆元算出部
９０  復号回路
９１  シンドローム算出部
９２  多項式算出部
９３  誤り位置算出部
９４  誤り値算出部
９５  バッファ
９６  誤り訂正部
【図１】
2020098994.tif 000003
【図２】
2020098994.tif 000004
【図３】
2020098994.tif 000005
【図４】
2020098994.tif 000006
【図５】
2020098994.tif 000007
【図６】
2020098994.tif 000008
【図７】
2020098994.tif 000009
【図８】
2020098994.tif 000010
【図９】
2020098994.tif 000011
【図１０】
2020098994.tif 000012
【図１１】
2020098994.tif 000013
【図１２】
2020098994.tif 000014
【図１３】
2020098994.tif 000015
【図１４】
2020098994.tif 000016
【図１５】
2020098994.tif 000017
【図１６】
2020098994.tif 000018