(57)【要約】【課題】ガロア拡大体ＧＦ（２ｍ）のサイズが大きくとも回路規模及び実装面積がさほど大規模化せず、且つ低消費電力で逆元を演算することができる逆元演算装置及び方法、当該装置を備える復号化装置、並びに逆元演算プログラムを提供する。【解決手段】ガロア拡大体ＧＦ（２ｍ）（ｍは任意の自然数）の任意の元βの逆元β−１を求める逆元演算装置であって、初期値として前記元βを取り込み、乗算結果をフィードバックさせつつ前記元βを２ｍ−２回乗算する乗算部（１５，２０）を備える。【選択図】　図１
2004094597.tif 000002
【特許請求の範囲】
【請求項１】
ガロア拡大体ＧＦ（２ｍ）（ｍは任意の自然数）の任意の元βの逆元β−１を求める逆元演算装置であって、
初期値として前記元βを取り込み、乗算結果をフィードバックさせつつ前記元βを２ｍ−２回乗算する乗算部を備えることを特徴とする逆元演算装置。
【請求項２】
前記乗算部は、前記初期値としての前記元を取り込み、乗算結果をフィードバックさせつつ前記元βの２のべき乗を求める第１の乗算器と、
前記第１の乗算器の乗算結果とフィードバックした自らの乗算結果とを乗算する第２の乗算器と
を備えることを特徴とする請求項１記載の逆元演算装置。
【請求項３】
ガロア拡大体ＧＦ（２ｍ）（ｍは任意の自然数）の任意の元βの逆元β−１をｋ乗（ｋは任意の自然数）したｋ乗逆元β−ｋを求める逆元演算装置であって、
初期値として前記元βを取り込み、乗算結果をフィードバックさせつつ前記元βを２ｍ−１−ｋ回乗算する乗算部を備えることを特徴とする逆元演算装置。
【請求項４】
前記乗算部は、前記初期値としての前記元を取り込み、乗算結果をフィードバックさせつつ前記元βの２のべき乗を求める第１の乗算器と、
前記第１の乗算器の乗算結果とフィードバックした自らの乗算結果とを乗算する第２の乗算器と、
前記ｋの値に応じて前記第１の乗算器から前記第２の乗算器への、前記第１の乗算器の演算結果の入力を制御する制御部と
を備えることを特徴とする請求項３記載の逆元演算装置。
【請求項５】
ガロア拡大体ＧＦ（２ｍ）（ｍは任意の自然数）の任意の元βの逆元β−１を求める逆元演算方法であって、
初期値として前記元βを取り込む初期値取り込みステップと、
以前の乗算結果をフィードバックさせつつ前記元βを２ｍ−２回乗算する乗算ステップと
を含むことを特徴とする逆元演算方法。
【請求項６】
ガロア拡大体ＧＦ（２ｍ）（ｍは任意の自然数）の任意の元βの逆元β−１をｋ乗（ｋは任意の自然数）したｋ乗逆元β−ｋを求める逆元演算方法であって、
初期値として前記元βを取り込む初期値取り込みステップと、
以前の乗算結果をフィードバックさせつつ前記元βを２ｍ−１−ｋ回乗算する乗算ステップと
を含むことを特徴とする逆元演算方法。
【請求項７】
請求項１から請求項４の何れか一項に記載の逆元演算装置によって、入力されたデータのシンドローム演算を行うシンドローム演算部を備えることを特徴とする復号化装置。
【請求項８】
ガロア拡大体ＧＦ（２ｍ）（ｍは任意の自然数）の任意の元βの逆元β−１を求める逆元演算プログラムであって、
初期値として前記元βを取り込む初期値取り込みステップと、
以前の乗算結果をフィードバックさせつつ前記元βを２ｍ−２回乗算する乗算ステップと
を含むことを特徴とする逆元演算プログラム。
【請求項９】
ガロア拡大体ＧＦ（２ｍ）（ｍは任意の自然数）の任意の元βの逆元β−１をｋ乗（ｋは任意の自然数）したｋ乗逆元β−ｋを求める逆元演算プログラムであって、
初期値として前記元βを取り込む初期値取り込みステップと、
以前の乗算結果をフィードバックさせつつ前記元βを２ｍ−１−ｋ回乗算する乗算ステップと
を含むことを特徴とする逆元演算プログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、ガロア拡大体ＧＦ（２ｍ）（ｍは任意の自然数）の逆元を演算により求める逆元演算装置及び方法、当該装置を備える復号化装置、並びに逆元演算プログラムに関する。
【０００２】
【従来の技術】
ディジタル記録装置及びディジタル通信機器等のディジタル機器においては、符号誤り訂正のためにＲＳ符号（リードソロモン符号）が用いられることが多い。ＲＳ符号の復号化装置は、符号化されたデータを復号化する際に、復号化するデータを生成多項式の各因数で除算した余り値（シンドローム）から誤り位置多項式を導出し、導出した誤り位置多項式に基づいて誤り位置及び誤り元の情報を求めた後で誤り訂正の処理を行う。
【０００３】
このように、データの復号化時には誤り訂正処理を行う過程で除算が必要になるが、演算回路の小規模化及び演算処理時間の短縮のために、除算を乗算に置き換えることが一般的に行われる。かかる置き換えによって、ある元で除算すべき演算が、その元に対応する逆元で乗算する演算に置き換えられる。ここで、元とその逆元とは、その積がガロア拡大体ＧＦ（２ｍ）上の“１”となる関係を有する。除算を乗算に置き換えた演算回路においては、演算に用いる逆元を記憶するための逆元ＲＯＭ（Ｒｅａｄ　Ｏｎｌｙ　Ｍｅｍｏｒｙ）が用いられる。この逆元ＲＯＭは、回路の小規模化のため、１つのチップ内に上述した処理を行う演算回路とともに設けられることが多い。
【０００４】
ガロア拡大体では任意の元に対してその逆元が一義的に定義できる。このため、この逆元定義を“０”以外のガロア拡大体の元全てに対して行い、求めた逆元を逆元ＲＯＭのアドレス毎に記憶させておく。そして、誤り訂正の処理を行う場合には、入力された元をアドレスとして逆元ＲＯＭをアクセスし、その元に対応する逆元を読み出して、復号化するデータに対して乗算を行うことで、上述した除算と等価な演算処理が行われる。
【０００５】
【発明が解決しようとする課題】
ところで、ガロア拡大体ＧＦ（２ｍ）のサイズが大きいＲＳ符号に対して、上述した逆元ＲＯＭを用いて除算と等価な演算を乗算により行う場合には、演算を行う上で必要となる逆元の数も増加する。このため、逆元を記憶するために必要となる逆元ＲＯＭの容量が２の乗数ｍに比例して大きくなり、チップ内に形成する回路の規模が増大して実装領域が大面積になり、消費電力も大きくなるという問題がある。
【０００６】
また、ガロア拡大体ＧＦ（２ｍ）のサイズがより大きくなると、必要となる逆元ＲＯＭの容量が、例えばメガバイトオーダー程度の容量になることもある。かかる場合には、１チップ内に上述した演算を行う回路と逆元ＲＯＭを形成することは困難になる。逆元ＲＯＭを単体のフラッシュメモリ等の不揮発性メモリで代替すれば、上述の容量を確保することは難しくないが、ＤＲＡＭを別に実装する必要があるため実装領域が更に大面積になり、消費電力もより大きくなるという問題が生ずる。
【０００７】
一方、逆元ＲＯＭを用いずに上述した除算と等価な逆元を用いた乗算を行う回路を設計することも可能であるが、この回路を単純なデコーダ等の論理回路で構成すると、回路規模、部品の実装面積、及び消費電力が逆元ＲＯＭを用いた場合よりも更に大きくなるという問題がある。
【０００８】
本発明は上記事情に鑑みてなされたものであり、ガロア拡大体ＧＦ（２ｍ）のサイズが大きくとも回路規模及び実装面積がさほど大規模化せず、且つ低消費電力で逆元を演算することができる逆元演算装置及び方法、当該装置を備える復号化装置、並びに逆元演算プログラムを提供することを目的とする。
【０００９】
【課題を解決するための手段】
上記課題を解決するために、本発明の第１の観点による逆元演算装置は、ガロア拡大体ＧＦ（２ｍ）（ｍは任意の自然数）の任意の元βの逆元β−１を求める逆元演算装置であって、初期値として前記元βを取り込み、乗算結果をフィードバックさせつつ前記元βを２ｍ−２回乗算する乗算部（１５、２０）を備えることを特徴としている。
ここで、この発明の原理について説明する。いま、上記ガロア拡大体ＧＦ（２ｍ）の元βに関して以下の（１）式〜（３）式が成り立つとする。
【数１】
2004094597.tif 000003
【数２】
2004094597.tif 000004
【数３】
2004094597.tif 000005
ただし、上記変数ｐは０≦ｐ≦２ｍ−１を満たす自然数であり、αはガロア拡大体ＧＦ（２ｍ）の原始元であって、“０”はガロア拡大体ＧＦ（２ｍ）の０元である。
上記元βを２ｍ−２回乗算すると以下の（４）式となるが、
【数４】
2004094597.tif 000006
この（４）式は以下の（５）式に分解することができる。
【数５】
2004094597.tif 000007
ここで、上記の（１）式及び（２）式を用いると、以下の（６）式が求められる。
【数６】
2004094597.tif 000008
ゆえに、以下の（７）式が求められ、この（７）式から元βを２ｍ−２回乗算することで、元βの逆元β−１が求められることが分かる。
【数７】
2004094597.tif 000009
以上の原理に基づいて、元βを２ｍ−２回乗算すれば、元βの逆元β−１を求めることはできるが、本発明においては、乗算部が初期値として元βを取り込むとともに、乗算結果をフィードバックさせつつ元βを２ｍ−２回乗算するようにしている。このため、回路規模を縮小することができ、その結果としてガロア拡大体ＧＦ（２ｍ）のサイズが大きくとも回路規模及び実装面積がさほど大規模化せず、且つ低消費電力で逆元を演算することができる。
また、本発明の第１の観点による逆元演算装置は、前記乗算部が、前記初期値としての前記元を取り込み、乗算結果をフィードバックさせつつ前記元βの２のべき乗を求める第１の乗算器（１５）と、前記第１の乗算器の乗算結果とフィードバックした自らの乗算結果とを乗算する第２の乗算器（２０）とを備えることを特徴としている。
この発明によれば、第１の乗算器が演算結果をフィードバックさせつつ元βの２のべき乗を求め、第２の乗算器が第１の乗算器の演算結果とフィードバックした自らの乗算結果とを乗算するようにして、複数の乗算器を用いて並列的に元βを２ｍ−２回乗算するようにしている。このため、見かけ上の演算回数を減らすことができ、演算時間を短縮することができる。
また、本発明の第２の観点による逆元演算装置は、ガロア拡大体ＧＦ（２ｍ）（ｍは任意の自然数）の任意の元βの逆元β−１をｋ乗（ｋは任意の自然数）したｋ乗逆元β−ｋを求める逆元演算装置であって、初期値として前記元βを取り込み、乗算結果をフィードバックさせつつ前記元βを２ｍ−１−ｋ回乗算する乗算部（１５、２０）を備えることを特徴としている。
ここで、この発明の原理について説明する。いま、上記ガロア拡大体ＧＦ（２ｍ）の元βが上記の（１）式〜（３）式を満たす場合、元βを２ｍ−１−ｋ回乗算すると、以下の（８）式となる。また、この（８）式は以下の（９）式の通り分解することができる。
【数８】
2004094597.tif 000010
【数９】
2004094597.tif 000011
ここで、上記の（６）式を用いると、以下の（１０）式が求められ、この（１０）式から元βを２ｍ−１−ｋ回乗算することで、元βの逆元β−ｋが求められることが分かる。
【数１０】
2004094597.tif 000012
以上の原理に基づいて、元βを２ｍ−１−ｋ回乗算すれば、元βのｋ乗逆元β−ｋを求めることはできるが、本発明においても、乗算部が初期値として元βを取り込むとともに、乗算結果をフィードバックさせつつ元βを２ｍ−１−ｋ回乗算するようにしている。このため、回路規模を縮小することができ、その結果としてガロア拡大体ＧＦ（２ｍ）のサイズが大きくとも回路規模及び実装面積がさほど大規模化せず、且つ低消費電力で逆元を演算することができる。
また、本発明の第２の観点による逆元演算装置は、前記乗算部が、前記初期値としての前記元を取り込み、乗算結果をフィードバックさせつつ前記元βの２のべき乗を求める第１の乗算器（１５）と、前記第１の乗算器の乗算結果とフィードバックした自らの乗算結果とを乗算する第２の乗算器（２０）と、前記ｋの値に応じて前記第１の乗算器から前記第２の乗算器への、前記第１の乗算器の演算結果の入力を制御する制御部（１６、４５）とを備えることを特徴としている。この発明によれば、第１の乗算器が演算結果をフィードバックさせつつ元βの２のべき乗を求め、第２の乗算器が第１の乗算器の演算結果とフィードバックした自らの乗算結果とを乗算するように構成するとともに、第１の乗算器から第２の乗算器への第１の乗算器の乗算結果の入力を制御部が制御するようにしている。このため、任意のｋに対して演算を行うことができるとともに、見かけ上の演算回数を減らすして演算時間を短縮することができる。
本発明の第１の観点による逆元演算方法は、ガロア拡大体ＧＦ（２ｍ）（ｍは任意の自然数）の任意の元βの逆元β−１を求める逆元演算方法であって、初期値として前記元βを取り込む初期値取り込みステップと、以前の乗算結果をフィードバックさせつつ前記元βを２ｍ−２回乗算する乗算ステップとを含むことを特徴としている。
また、本発明の第２の観点による逆元演算方法は、ガロア拡大体ＧＦ（２ｍ）（ｍは任意の自然数）の任意の元βの逆元β−１をｋ乗（ｋは任意の自然数）したｋ乗逆元β−ｋを求める逆元演算方法であって、初期値として前記元βを取り込む初期値取り込みステップと、以前の乗算結果をフィードバックさせつつ前記元βを２ｍ−１−ｋ回乗算する乗算ステップとを含むことを特徴としている。
本発明の復号化装置は、上記の何れかに記載の逆元演算装置によって、入力されたデータのシンドローム演算を行うシンドローム演算部を備えることを特徴としている。
本発明の第１の観点による逆元演算プログラムは、ガロア拡大体ＧＦ（２ｍ）（ｍは任意の自然数）の任意の元βの逆元β−１を求める逆元演算プログラムであって、初期値として前記元βを取り込む初期値取り込みステップと、以前の乗算結果をフィードバックさせつつ前記元βを２ｍ−２回乗算する乗算ステップとを含むことを特徴としている。
また、本発明の第２の観点による逆元演算プログラムは、ガロア拡大体ＧＦ（２ｍ）（ｍは任意の自然数）の任意の元βの逆元β−１をｋ乗（ｋは任意の自然数）したｋ乗逆元β−ｋを求める逆元演算プログラムであって、初期値として前記元βを取り込む初期値取り込みステップと、以前の乗算結果をフィードバックさせつつ前記元βを２ｍ−１−ｋ回乗算する乗算ステップとを含むことを特徴としている。
【００１０】
【発明の実施の形態】
以下、図面を参照して本発明の実施形態による逆元演算装置及び方法、復号化装置、並びに逆元演算プログラムについて詳細に説明する。
【００１１】
〔第１実施形態〕
図１は、本発明の第１実施形態による逆元演算装置の構成を示すブロック図である。尚、図１に示す逆元演算装置は、ＲＳ符号を復元する装置であって、ｍ＝３であるガロア拡大体ＧＦ（２３）における逆元を演算により求める装置である。
【００１２】
図１において、データ比較器１０は、一方の入力端に演算対象となる元が入力データＤｉｎとして入力されるとともに、他方の入力端にフリップフロップ（以下、ＦＦという）１１の出力が入力され、新たな入力データＤｉｎとＦＦ１１から出力される以前の入力データ（基準クロックＣＬＫの１周期分前の入力データ）とを比較し、入力データの変化を検出したときに検出信号Ｓ０を出力する。尚、上記のＦＦ１１にも入力データＤｉｎが入力されており、データ比較器１０から出力される検出信号はＦＦ１２に入力される。これらのＦＦ１１，１２は、不図示の基準クロックに同期して動作する。
【００１３】
ＦＦ１１の出力端はスイッチ１３の入力端Ｐ１に接続されている。スイッチは２つの入力端Ｐ０，Ｐ１を有し、ＦＦ１２から出力される検出信号Ｓ１に応じて出力端に接続する入力端を切り替える。具多的には、ＦＦ１２からの検出信号Ｓ１が「Ｌ（ロー）」の場合には入力端Ｐ０と出力端とを接続し、検出信号Ｓ１が「Ｈ（ハイ）」の場合には入力端Ｐ１と出力端とを接続する。スイッチ１３の出力端は、基準クロックＣＬＫに同期して動作するＦＦ１４の入力端に接続され、ＦＦ１４の出力端は乗算器（本発明にいう第１の乗算器）の入力端に接続されている。
【００１４】
乗算器１５は２つの入力端を有し、各々の入力端から入力されるデータを乗算して出力する。本実施形態では、ＦＦ１４の出力は乗算器１５の両入力端に接続されているため、乗算器１４は入力されるデータＤ３の２乗を演算する。乗算器１５の出力端は上述したスイッチ１３の入力端Ｐ０に接続されており、スイッチ１３が入力端ＰＯと出力端とを接続している状態においては、乗算器１５から出力される乗算データＭ１が乗算器１５の入力にフィードバックされるよう構成されている。また、乗算器１５の出力端は基準クロックに同期して動作するＦＦ１６の入力端に接続されている。
【００１５】
ＦＦ１６は、後述するセット・リセット・フリップフロップ（以下、Ｓ／Ｒ　ＦＦという）１７から出力される制御信号Ｓ４が「Ｈ」である場合（Ｓ／Ｒ　ＦＦ１７がセット状態である場合）には、乗算器１５から出力される乗算データＭ１を通過させ、制御信号Ｓ４が「Ｌ」である場合（Ｓ／Ｒ　ＦＦ１７がリセット状態である場合）には、乗算器１５からの乗算データＭ１を遮断して「１」を出力する。
【００１６】
ここで、Ｓ／Ｒ　ＦＦ１７はのＳ入力端には、上述したＦＦ１２から出力される検出信号Ｓ１が入力され、Ｒ入力端にはＦＦ１９から出力される制御信号Ｓ２が入力されており、基準クロックＣＬＫに同期して動作する。ＦＦ１８及びＦＦ１９は縦続接続されて基準クロックＣＬＫに同期して動作し、ＦＦ１８の入力端にはＦＦ１２から出力される検出信号Ｓ１が入力されている。よって、ＦＦ１２から検出信号Ｓ１が出力されてから、基準クロックＣＬＫの２周期分の時間が経過した後に、制御信号Ｓ２が出力されるよう構成されている。
【００１７】
このＦＦ１８，１９からなる回路は、本実施形態の逆元演算装置が入力データＤｉｎに対して行う乗算回数に応じて設定されている。本実施形態の逆元演算装置は、ｍ＝３の場合における逆元を演算する装置であるが、この場合には２つのＦＦ１８，１９を設けることで、乗算器１５から乗算器２０への乗算データＭ１の出力の制御及び出力データＤｏｕｔの出力制御を行っている。
【００１８】
乗算器２０は２つの入力端を有し、各々の入力端から入力されるデータを乗算して出力する。本実施形態では、一方の入力端にＦＦ１６から出力されるデータＤ４が入力されている。この乗算器Ｍ２の出力端は基準クロックＣＬＫに同期して動作するＦＦ２１の入力端に接続されており、ＦＦ２１の出力端は乗算器２０の他方の入力端に接続されている。つまり、ＦＦ２１を介して乗算器２０の乗算データＭ２がフードバックされるよう構成されている。尚、乗算器２０は、本発明にいう第２の乗算器に相当する。
【００１９】
ＦＦ２１には反転回路２２を介して検出信号Ｓ１が反転された信号が入力されている。ＦＦ２１は、反転回路２２から「Ｌ」の信号が出力された場合（検出信号Ｓ１が「Ｈ」になった場合）には、出力端から「１」が出力されるよう初期化し、反転回路２２からの信号が「Ｈ」の場合（検出信号Ｓ１が「Ｌ」の場合）には、入力端に入力される信号を通過させる。
【００２０】
また、乗算器２０の出力端は基準クロックＣＬＫに同期して動作するＦＦ２３の入力端に接続されている。このＦＦ２３には、ＦＦ２４からの制御信号Ｓ３が入力されており、制御信号Ｓ３が入力されると基準クロックＣＬＫに同期してデータを取り込み、出力データＤｏｕｔとして出力する。尚、ＦＦ２４の入力端にはＦＦ１９から出力される制御信号Ｓ２が入力されており、ＦＦ１９から制御信号Ｓ２が出力されてから基準クロックＣＬＫの１周期分の時間が経過した後にＦＦ２４から制御信号Ｓ３が出力されるよう構成されている。
【００２１】
次に、以上説明した構成の本発明の第１実施形態による逆元演算装置の動作、つまり本発明の第１実施形態による逆元演算方法について説明する。図２は、本発明の第１実施形態による逆元演算装置の動作を説明するための逆元演算装置の各部から出力される信号及びデータのタイミングチャートである。尚、図２においては、元としての入力データＤｉｎとしてデータα５が入力される場合を例に挙げて図示している。
【００２２】
図２中の時刻ｔ１が僅かに経過した後に、入力データＤｉｎとしてデータα５が入力されたとする。尚、時刻ｔ１以前においては、入力データＤｉｎとしてデータα５以外の値が入力されていたとする。入力データＤｉｎがとしてデータα５が入力されると、データ比較器１０において、入力された入力データＤｉｎ（α５）とＦＦ１１から出力される時刻ｔ１以前のデータとが比較され、データ比較器１０からレベルが「Ｈ」の検出信号Ｓ０が出力される。
【００２３】
データ比較器１０から検出信号Ｓ０が出力されると、検出信号Ｓ０はＦＦ１２に入力され、時刻ｔ２においてレベルが「Ｈ」となった検出信号Ｓ１がＦＦ１２から出力される。この検出信号Ｓ１はスイッチ１３、Ｓ／Ｒ　ＦＦ１７、ＦＦ１８、及び反転回路２２を介してＦＦ２１に入力される。これにより、スイッチ１３は入力端Ｐ１と出力端とが接続された状態となる。また、Ｓ／Ｒ　ＦＦ１７はセット状態となって時刻ｔ３においてＳ／Ｒ　ＦＦ１７からレベルが「Ｈ」の制御信号Ｓ４が出力され、これにより時刻ｔ３においてＦＦ１６が入力されるデータを通過させる状態になる。更に、時刻ｔ３においてＦＦ２１が初期化されて、データＤ５として「１」を出力する状態になる。
【００２４】
また、時刻ｔ２において、ＦＦ１１からデータＤ１としてデータα５が出力され、スイッチ１３を介してデータＤ２としてＦＦ１４に入力される。そして、時刻ｔ３において、データＤ３としてＦＦ１４から出力されて乗算器１５に入力される。尚、時刻ｔ３経過後に、検出信号Ｓ１が「Ｌ」になるため、スイッチ１３は入力端Ｐ０と出力端とが接続された状態となる。
【００２５】
データＤ３（α５）が乗算器１５に入力されると乗算されて乗算データＭ１（α１０）が出力される。この乗算データＭ１はスイッチ１３を介してＦＦ１４に入力され、時刻ｔ４経過後に乗算器１５にフィードバックされる。このようにして、乗算器１５においては、データα１０の２のべき乗が演算される。また、上記の乗算器１５から出力される乗算データＭ１（α１０）は、ＦＦ１６へ入力され、時刻ｔ４経過後に乗算器２０に入力される。この時点においては、ＦＦ２１から出力されるデータＤ５は「１」であるため乗算器２０は、乗算データＭ２としてデータα１０を出力する。
【００２６】
時刻ｔ５が経過すると、乗算器１５から出力された乗算データＭ１（α２０）がＦＦ１６を介して乗算器２０の一方の入力端に入力されるとともに、乗算器２０の前回の乗算データＭ２（α１０）が他方の入力端にフィードバックされ、これらの乗算が行われ、乗算データＭ２としてデータ（α３０）が出力される。ここで、時刻ｔ２において検出信号Ｓ１が出力されてから基準クロックＣＬＫの２周期分の時間が経過した時刻ｔ４になると、ＦＦ１９からレベルが「Ｈ」の制御信号Ｓ２が出力される。この制御信号Ｓ２はＳ／Ｒ　ＦＦ１７及びＦＦ２４に入力され、時刻ｔ５においてＳ／Ｒ　ＦＦ１７から出力される制御信号Ｓ４が「Ｌ」になるとともに、時刻ｔ５経過後にＦＦ２４から制御信号Ｓ３が出力される。
【００２７】
このため、時刻ｔ６においてＦＦ１６が乗算データＭ１を遮断するように作用するとともに、ＦＦ２３が制御信号Ｓ３に基づいて乗算器２０から出力された乗算データＭ２を出力データＤｏｕｔとして出力する。このようにして、出力データＤｏｕｔ（α３０）が得られる。
【００２８】
ここで、本実施形態においては、ｍ＝３の場合を想定しており、本発明の原理では元としての入力データＤｉｎ（α５）に対して２３−２＝６回の乗算を行えば逆元が得られることになる。上記の実施形態では、入力データＤｉｎとしてデータα５を入力したときに、出力データＤｏｕｔとしてデータα３０が得られた。データα３０は、データα５を６回乗算したものであるため、本実施形態の逆元演算装置により、逆元が得られることが分かる。
【００２９】
以上説明したように、本発明の第１実施形態による逆元演算装置においては、乗算器１５が乗算データＭ１をフィードバックさせつつ入力データＤｉｎ（α５）２のべき乗を求め、乗算器２０が乗算器１５の乗算データＭ１とフィードバックした自らの乗算データＭ２とを乗算するようにして、２つの乗算器１５，２０を用いて並列的に入力データＤｉｎを２ｍ−２回乗算するようにしている。このため、見かけ上の演算回数を減らすことができ、演算時間を短縮することができる。
【００３０】
〔第２実施形態〕
図３は、本発明の第２実施形態による逆元演算装置の構成を示すブロック図である。図３に示す本発明の第２実施形態による逆元演算装置は、ＲＳ符号を復元する装置であって、ｍを任意の自然数としたときにガロア拡大体ＧＦ（２ｍ）における逆元を演算により求める装置である。
【００３１】
図１に示す逆元演算装置はｍ＝３の場合に適用したものであったが、本実施形態においてはより一般化している。図３と図１とを比較するとデータが介する信号線のビット幅がｍの値に応じて設定されるとともに、図１中のＦＦ１８，１９に代えてＦＦ群３０を設けた点が相違する。前述したように、ＦＦ１８，１９からなる回路は、逆元演算装置が入力データＤｉｎに対して行う乗算回数を規定するために設けられるものである。逆元を求めるために入力される元に対して行う乗算回数は２ｍ−２回であり、ｍの値に応じて変化する。このため、本実施形態においては、任意の自然数ｍに対して適用可能になっている。具体的にＦＦ群３０を構成するＦＦの数は、ｍ−１である。
【００３２】
〔第３実施形態〕
図４は、本発明の第３実施形態による逆元演算装置の構成を示すブロック図である。図４に示す本発明の第３実施形態による逆元演算装置は、ＲＳ符号を復元する装置であって、ｍを任意の自然数としたときにガロア拡大体ＧＦ（２ｍ）におけるｋ乗逆元（ｋは任意の自然数）を演算により求める装置である。本実施形態の逆元演算装置の基本的な構成は図３に示す第２実施形態による逆元演算装置と同様であるが、ＦＦ１４に代えてＦＦ４１，４２を設けるとともに、反転回路４３、論理積演算回路４４、及びデータシフト部４５を設けた点が相違する。
【００３３】
ＦＦ４１，４２は、それぞれの入力端がスイッチ１３の出力端に接続され、それぞれの出力端が乗算器１５の入力端にそれぞれ接続されている。また、ＦＦ４２のみに反転回路４３が接続されている。この反転回路４３は検出信号Ｓ１を反転した信号をＦＦ４２に入力することによって、検出信号Ｓ１が「Ｈ」の状態にあるときに、ＦＦ４２を非動作状態にするために設けられる。かかる制御をするのは、乗算器１５による入力データＤｉｎの２のべき乗の計算を基準クロックＣＬＫの１周期分遅らせるためである。
【００３４】
また、論理積演算回路４４は、その入力端がＳ／Ｒ　ＦＦ１７の出力端とデータシフト部４５の出力端の最下位ビット（ＬＳＢ）に接続されており、データシフト部４５の最下位ビットの値に応じて開閉状態を制御することで、ＦＦ１６に対する制御信号Ｓ４１の出力を制御する。データシフト部４５の入力には、ｋ乗逆元を求めるための演算回数データｋが入力されている。また、出力端のうち最下位ビットを除くビットが入力側にフィードバックされている。このデータシフト部４５は、基準クロックＣＬＫに同期して基準クロックＣＬＫが入力される度に演算回数データｋ又は２回目以降はフィードバックされるデータを最下位ビット側にシフトした制御信号を出力する。
【００３５】
かかる構成とすることで、乗算器１５の乗算データＭ１（入力データＤｉｎの２のべき乗）が基準クロックＣＬＫの１周期分だけ遅れて発生し、データシフト部４５に入力される演算回数データｋに基づいて、乗算器１５から乗算器２０への、乗算器１５の乗算データＭ１の出力が制御される。かかる制御を行うことで、出力データＤｏｕｔとして出力されるデータが入力データＤｉｎを２ｍ−１−ｋ回乗算したものになる。
【００３６】
〔その他の実施形態〕
以上説明した第１実施形態〜第３実施形態による逆元演算装置においては、２つの乗算器１５，２０を設け、これらをいわば並列的に動作させることにより、演算に要する時間を短縮していた。しかしながら、演算時間に余裕がある場合には、１つの乗算器のみを用いて必要回数乗算を行うようにしても良い。
【００３７】
また、以上説明した逆元演算装置を、ディジタル記録装置及びディジタル通信機器等のディジタル機器の復号化装置に設け、入力されるＲＳ符号データを生成多項式の各因数で除算した余り値（シンドローム）から誤り位置多項式を導出し、導出した誤り位置多項式に基づいて誤り位置及び誤り元の情報を求めた後で誤り訂正の処理を行えば、誤り訂正を行いつつ符号化されたＲＳ符号を復号化することができる。
【００３８】
更に、以上説明した実施形態においては、装置に適用した場合を例に挙げて説明した。しかしながら、本発明はプログラムによるソフトウェア処理により誤り訂正を行う用途にも適用することができる。この場合におけるプログラムにおいて、元βの逆元β−１を求める場合には、少なくとも初期値として前記元βを取り込む初期値取り込みステップと、以前の乗算結果をフィードバックさせつつ前記元βを２ｍ−２回乗算する乗算ステップとが含まれる。また、元βのｋ乗逆元β−ｋを求める場合には、少なくとも初期値として前記元βを取り込む初期値取り込みステップと、以前の乗算結果をフィードバックさせつつ前記元βを２ｍ−１−ｋ回乗算する乗算ステップとが含まれる。
【００３９】
コンピュータは比較的ＲＯＭ、ＲＡＭ（Ｒａｎｄｏｍ　Ａｃｃｅｓｓ　Ｍｅｍｏｒｙ）等の記憶装置に容量的な余裕がある場合が多い。しかしながら、使用可能な記憶容量が制限される場合又はガロア拡大体ＧＦ（２ｍ）のサイズがより大きくなる場合等に用いると好適である。
【００４０】
【発明の効果】
以上説明したように、本発明によれば、乗算部が初期値として元βを取り込むとともに、乗算結果をフィードバックさせつつ元βを２ｍ−２回乗算するようにしている。このため、回路規模を縮小することができ、その結果としてガロア拡大体ＧＦ（２ｍ）のサイズが大きくとも回路規模及び実装面積がさほど大規模化せず、且つ低消費電力で逆元を演算することができるという効果がある。
また、本発明によれば、第１の乗算器が演算結果をフィードバックさせつつ元βの２のべき乗を求め、第２の乗算器が第１の乗算器の演算結果とフィードバックした自らの乗算結果とを乗算するようにして、複数の乗算器を用いて並列的に元βを２ｍ−２回乗算するようにしている。このため、見かけ上の演算回数を減らすことができ、演算時間を短縮することができるという効果がある。
また、本発明におれば、乗算部が初期値として元βを取り込むとともに、乗算結果をフィードバックさせつつ元βを２ｍ−１−ｋ回乗算するようにしている。このため、回路規模を縮小することができ、その結果としてガロア拡大体ＧＦ（２ｍ）のサイズが大きくとも回路規模及び実装面積がさほど大規模化せず、且つ低消費電力で逆元を演算することができるという効果がある。
また、本発明によれば、第１の乗算器が演算結果をフィードバックさせつつ元βの２のべき乗を求め、第２の乗算器が第１の乗算器の演算結果とフィードバックした自らの乗算結果とを乗算するように構成するとともに、第１の乗算器から第２の乗算器への第１の乗算器の乗算結果の入力を制御部が制御するようにしている。このため、任意のｋに対して演算を行うことができるとともに、見かけ上の演算回数を減らすして演算時間を短縮することができるという効果がある。
【図面の簡単な説明】
【図１】本発明の第１実施形態による逆元演算装置の構成を示すブロック図である。
【図２】本発明の第１実施形態による逆元演算装置の動作を説明するための逆元演算装置の各部から出力される信号及びデータのタイミングチャートである。
【図３】本発明の第２実施形態による逆元演算装置の構成を示すブロック図である。
【図４】本発明の第３実施形態による逆元演算装置の構成を示すブロック図である。
【符号の説明】
１５　　乗算器（乗算部、第１の乗算器）
１６　　フリップフロップ（制御部）
２０　　乗算器（乗算部、第２の乗算器）
４５　　データシフト部（制御部）
【図１】
2004094597.tif 000013
【図２】
2004094597.tif 000014
【図３】
2004094597.tif 000015
【図４】
2004094597.tif 000016