(57)【特許請求の範囲】
【請求項１】
ＢＣＨ符号の誤り位置多項式を用いてｔワード（ｔは予め定められた整数）の誤り訂正を行うエラー訂正復号回路における該誤り位置多項式を求めるための演算ユニットであって、
第０乃至第２ｔの記憶領域を有し、シンドローム多項式の係数が第１乃至第２ｔの記憶領域に予め記憶される第１のレジスタと、
第０乃至第２ｔの記憶領域を有する第２のレジスタと、
前記第２のレジスタの第２ｔの記憶領域に記憶された係数を、前記第１のレジスタの第２ｔの記憶領域に記憶された係数でガロア体除算するガロア体除算器と、
前記ガロア体除算器の除算結果と、前記第１のレジスタの第０乃至第２ｔ−１の各係数をそれぞれガロア体乗算するガロア体乗算器群と、
前記ガロア体乗算器群で求められた各係数と、前記第２のレジスタの第０乃至第２ｔ−１の各係数とをそれぞれガロア体加算するガロア体加算器群と、
前記ガロア体加算器群からの出力又は前記第１のレジスタに記憶された各係数のいずれかを選択し、前記第１又は第２のレジスタに記憶された各係数のいずれかを選択する第１のセレクタと
前記第１のセレクタからの出力を、第１又は前記第２のレジスタの所定の記憶領域に記憶するためのシフターと、
前記第１のセレクタからの出力された各係数のひとつをゼロに置き換え又は削除する挿入ユニットと、
前記シフターからの出力を前記第１のレジスタ及び前記第２のレジスタの一方に記憶し、前記挿入ユニットからの出力を、前記第１のレジスタ及び前記第２のレジスタの他方に記憶するための第２のセレクタと
を備え、
前記ガロア体除算器と、前記ガロア体乗算器群と、前記ガロア体加算器群とによる演算を含むステップを繰り返し、誤り位置多項式の各係数を求める前記演算ユニット。
【請求項２】
前記シフターは、前記ガロア体加算器群における前記第２のレジスタの第０乃至第２ｔ−１の各係数との加算結果又は前記第１のレジスタの第０乃至第２ｔ−１の各係数を、前記第１のレジスタ又は前記第２のレジスタの第１乃至第２ｔの記憶領域に記憶されるようシフトする請求項１に記載の演算ユニット。
【請求項３】
前記挿入ユニットは、第ｉステップ（ｉは１乃至２ｔの整数）において、前記第１又は第２のレジスタからの各係数を入力し、第ｉの記憶領域の係数をゼロに変更し、変更された係数を前記第１のレジスタ又は前記第２のレジスタに記憶する請求項１に記載の演算ユニット。
【請求項４】
前記ガロア体除算器と、前記ガロア体乗算器群と、前記ガロア体加算器群とによる演算を含むステップを２ｔ回繰り返し、
２ｔステップの後前記ガロア体加算器群から出力される係数のうち、又は、２ｔステップの後前記第１のレジスタに記憶された係数のうち、誤り位置多項式の次数に応じた個数を、誤り位置多項式の係数として出力する請求項１に記載の演算ユニット。
【請求項５】
２ｔステップの後前記第１のレジスタに記憶された係数のうち、第２ｔ乃至第ｔの記憶領域に記憶された係数を、誤り位置多項式の係数として出力する請求項４に記載の演算ユニット。
【請求項６】
前記第１と第２のセレクタを制御する制御部
をさらに備え、
前記制御部は、
現ステップでの剰余多項式を次のステップにて被除数多項式に置き換えたい場合に、前記第１のレジスタの各係数を前記挿入ユニットに出力し、該挿入部からの出力を前記第１のレジスタに記憶し、前記ガロア体加算器群からの出力を前記シフターに出力し、該シフターからの出力を前記第２のレジスタに記憶するように第１と第２のセレクタを制御し、
現ステップでの剰余多項式と除数多項式を次のステップにて除数多項式と被除数多項式に置き換えたい場合に、前記第１のレジスタの各係数を前記挿入ユニットに出力し、該挿入部からの出力を前記第２のレジスタに記憶し、前記ガロア体加算器群からの出力を前記シフターに出力し、該シフターからの出力を前記第１のレジスタに記憶するように前記第１と第２のセレクタを制御する請求項１に記載の演算ユニット。
【請求項７】
前記制御部は、前記第１のレジスタの第２ｔの記憶領域の係数がゼロの場合に、前記第１のレジスタの各係数を前記シフターに出力し、該シフターからの出力を前記第１のレジスタに記憶し、前記第２のレジスタの各係数を前記挿入ユニットに出力し、該挿入ユニットからの出力を前記第２のレジスタに記憶するように前記セレクタを制御し、
前記シフターは、前記第１のレジスタの第０乃至第２ｔ−１の記憶領域からの各係数を、前記第１のレジスタ第１乃至第２ｔの記憶領域に記憶されるようシフトする請求項６に記載の演算ユニット。
【請求項８】
前記ガロア体除算器は、
係数とその逆元が対応して記憶された逆元メモリと
前記第１のレジスタの第２ｔの記憶領域から入力される係数に基づき前記逆元メモリから読み出された逆元と、前記第２のレジスタの第２ｔの記憶領域から入力される係数とを乗算するガロア体乗算器と
を有する請求項１に記載の演算ユニット。
【請求項９】
ＢＣＨ符号の誤り位置多項式を用いてｔワード（ｔは予め定められた整数）の誤り訂正を行うエラー訂正復号回路であって、
入力信号からシンドローム多項式を求めるシンドローム演算ユニットと、
誤り位置多項式を求めるための演算ユニットと、
前記演算ユニットから出力される誤り位置多項式の係数に基づき、入力信号の誤りを訂正する誤り訂正ユニットと
を備え、
前記演算ユニットは、
第０乃至第２ｔの記憶領域を有し、前記シンドローム演算ユニットで求められたシンドローム多項式の係数が第１乃至第２ｔの記憶領域に記憶される第１のレジスタと、
第０乃至第２ｔの記憶領域を有する第２のレジスタと、
前記第２のレジスタの第２ｔの記憶領域に記憶された係数を、前記第１のレジスタの第２ｔの記憶領域に記憶された係数でガロア体除算するガロア体除算器と、
前記ガロア体除算器の除算結果と、前記第１のレジスタの第０乃至第２ｔ−１の各係数をそれぞれガロア体乗算するガロア体乗算器群と、
前記ガロア体乗算器群で求められた各係数と、前記第２のレジスタの第０乃至第２ｔ−１の各係数とをそれぞれガロア体加算するガロア体加算器群と、
前記ガロア体加算器群からの出力又は前記第１のレジスタに記憶された各係数のいずれかを選択し、前記第１又は第２のレジスタに記憶された各係数のいずれかを選択する第１のセレクタと
前記第１のセレクタからの出力を、第１又は前記第２のレジスタの所定の記憶領域に記憶するためのシフターと、
前記第１のセレクタからの出力された各係数のひとつをゼロに置き換え又は削除する挿入ユニットと、
前記シフターからの出力を前記第１のレジスタ及び前記第２のレジスタの一方に記憶し、前記挿入ユニットからの出力を、前記第１のレジスタ及び前記第２のレジスタの他方に記憶するための第２のセレクタと
を有し、前記ガロア体除算器と、前記ガロア体乗算器群と、前記ガロア体加算器群とによる演算を含むステップを繰り返し、誤り位置多項式の各係数を求め、前記誤り訂正ユニットに出力する前記エラー訂正復号回路。
【請求項１０】
前記シンドローム演算ユニットと誤り訂正ユニットとをそれぞれ複数備え、
前記演算ユニットは、
複数の前記シンドローム演算ユニットからシンドローム多項式を入力し、
求められた誤り位置多項式を、該シンドローム演算ユニットに対応する前記誤り訂正ユニットに出力する請求項９に記載のエラー訂正復号回路。
【請求項１１】
ＢＣＨ符号の誤り位置多項式を用いてｔワード（ｔは予め定められた整数）の誤り訂正を行うための該誤り位置多項式の演算方法であって、
第０乃至第２ｔの記憶領域を有する第２のレジスタから第２ｔの記憶領域に記憶された第１の係数を入力し、第０乃至第２ｔの記憶領域を有し、シンドローム多項式の係数が該第１乃至第２ｔの記憶領域に予め記憶された第１のレジスタから第２ｔの記憶領域に記憶された第２の係数を入力し、第１の係数を第２の係数でガロア体除算するガロア体除算処理と、
前記ガロア体除算処理の除算結果と、第１のレジスタの第０乃至第２ｔ−１の各係数をそれぞれガロア体乗算するガロア体乗算処理と、
前記ガロア体乗算処理で求められた各係数と、第２のレジスタの第０乃至第２ｔ−１の各係数とをそれぞれガロア体加算するガロア体加算処理と、
前記ガロア体加算処理の処理結果又は前記第１のレジスタの第０乃至第２ｔ−１の各係数を、第１又は第２のレジスタの所定の記憶領域に記憶するためにシフトするシフト処理と、
第１又は第２のレジスタに記憶された各係数のひとつをゼロに置き換え又は削除する挿入処理と、
前記シフト処理の処理結果を第１のレジスタ及び第２のレジスタの一方に記憶し、前記挿入処理の処理結果を、第１のレジスタ及び第２のレジスタの他方に記憶する記憶処理と
を含み、
前記ガロア体除算処理と、前記ガロア体乗算器処理と、前記ガロア体加算器処理を含むステップを繰り返し、誤り位置多項式の各係数を求める前記誤り位置多項式の演算方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、演算ユニット、エラー訂正復号回路及び誤り位置多項式の演算方法に係り、特に、二元ＢＣＨ符号に特化したユークリッド・アルゴリズムを改良し、エラー訂正復号回路（デコーダ）内部のユークリッド互除演算を行う演算ユニット、エラー訂正復号回路及び誤り位置多項式の演算方法に関する。
【背景技術】
【０００２】
光通信におけるエラー訂正復号回路は、例えば図５ように光ファイバ上で伝送劣化に伴って混入したエラーを訂正し、元のデータに戻すために使用される。
【０００３】
エラー訂正回路は、一般に通信、コンピュータ、オーディオ・ビデオ等の分野に用いられている。エラー訂正を行うにはデータを符号化する必要があり、その代表的なものがＢＣＨ（Ｂｏｓｅ−Ｃｈａｕｄｈｕｒｉ−Ｈｏｃｑｕｅｎｇｈｅｍ）符号である。ＢＣＨ符号では、例えば図６のように復号回路に１符号長という単位で入力し訂正処理を行う。
【０００４】
１符号長は幾つかのワードから構成されており、例えば図７のように１ワードが１ビットのものを二元ＢＣＨ符号、あるいは単にＢＣＨ符号という。また、例えば図８のように１ワードが１ビットでないもの（複数ビットからなるもの）を非二元ＢＣＨ符号、あるいはＲＳ（Ｒｅｅｄ−Ｓｏｌｏｍｏｎ、リードソロモン）符号と呼ぶ。
【０００５】
ＢＣＨ符号もＲＳ符号もガロア体上での演算規則に従っている。例えばガロア体ＧＦ（１６）の場合は、０、１、α１、・・α１４の計１６個の元をもっている。これらの元は加算、乗算の結果も、例えば図９に示すＧＦ（１６）の加算（又は減算）テーブル、図１０に示すＧＦ（１６）の乗算テーブルのように、０、１、α１、・・α１４の１６個の元うちのいずれかになる。例をあげると、
α１４ ＋  α８ ＝α６ ∈  ＧＦ（１６）・・（１）
α１４ ×  α８ ＝α５ ∈  ＧＦ（１６）・・（２）
となりＧＦ（１６）の場合、加算、乗算の表は１６行×１６列＝２５６要素のテーブルとなる。なお、ガロア体の元０をα∞と表し、元１をα０と表す場合もある。また、ガロア体の減算は以下のように加算と同様の演算になる。
α１４ −  α８ ＝ α１４ ＋  α８ ∈  ＧＦ（１６）・・（３）
【０００６】
光ネットワークの分野では、２００３年に国際電気通信連合（以下、ＩＴＵ−Ｔと称する）が勧告Ｇ．７０９（非特許文献１）において情報伝送フレームに対してエラー訂正機能を追加することを正式に定めている。勧告Ｇ．７０９では、当初、表１に示すようなＲＳ符号が用いられた。このＲＳ符号はＧＦ（２５６）上の演算規則に従っている。つまり、２５６個の元を持ち、加算、乗算の表は２５６行×２５６列＝６５５３６要素のテーブルになる。
【表１】
0004767266.tif 000002
【０００７】
しかしながら、近年、インターネット通信の普及と光ファイバ通信技術の向上により伝送容量が飛躍的に増加し、それに伴う信号品質の劣化が深刻になり、このＲＳ符号よりも高い訂正率を持つエラー訂正符号が求められるようになった。
【０００８】
ＩＴＵ−Ｔの勧告Ｇ．９７５．１（非特許文献２）には、２つの異なるＢＣＨ符号から構成される連接符号についての記述があり、この連接符号は先に示したＧＦ（２５６）のＲＳ符号より高い訂正能力を持つ。ここで２つのＢＣＨ符号を便宜上、それぞれＢＣＨ＿１、ＢＣＨ＿２と記す。ＢＣＨ＿１は、例えば表２のように符号化されている。
【表２】
0004767266.tif 000003
【０００９】
また、ＢＣＨ＿２は、表３のように符号化されている。
【表３】
0004767266.tif 000004
【００１０】
この連接符号で効率的な訂正を行うには、アルゴリズムと伝送データの特性上、同じ復号回路を複数個使用する必要がある。勧告Ｇ．９７５．１の例では、連接符号の復号回路はＢＣＨ＿１の復号回路が８×３＝２４個、ＢＣＨ＿２の復号回路が１６×３＝４８個で紹介されている。図１２にその構成例を示す。この回路の論理規模は、例えば数メガゲート規模となり、搭載されるメモリは数メガビットとなる。表１に示したＲＳ符号の復号回路の論理規模が数十キロゲート、メモリが数十キロビットであることを考えると、表２、表３の連接符号の復号回路の論理規模は非常に巨大である。
【００１１】
更に、連接符号の復号回路をＬＳＩに実装する際には、論理規模とメモリの他に動作周波数というパラメータも考慮する必要がある。この値が低いとＬＳＩを高速で動かしたときに配線遅延を引き起こし回路が正常動作しなくなるためである。
【００１２】
これらを鑑みて現実的なレベルまでに連接符号の復号回路を設計するためは、ＢＣＨ符号の復合回路の最適化が極めて重要な課題となる。しかしながら、これまでのＢＣＨ符号の大半がＧＦ（１６）かＧＦ（３２）程度の少ない元数で符号化され、復号回路の訂正ワード数も１〜３ワード程度であった。これに対し、上述の表２、表３のような場合は、ＧＦ（２０４８）、ＧＦ（４０９６）と元数が多く、更に１０ワードもの訂正を行う。一般にガロア体が多元化し、訂正できるワード数が増えるほど復号回路は複雑になり、その論理規模も増える。このようなＢＣＨ符号の復号回路の最適化は、ＲＳ符号に比べ殆ど進歩していないのが現状である。
【特許文献１】特開５−１６５６６２号公報
【特許文献２】特開平７−２４０６９２号公報
【非特許文献１】ＩＴＵ−Ｔ  勧告Ｇ．７０９
【非特許文献２】ＩＴＵ−Ｔ  勧告Ｇ．９７５．１
【発明の開示】
【発明が解決しようとする課題】
【００１３】
本発明は、以上の点に鑑み、最小の又は小さいレイテンシで、動作周波数を上げるために制御するための回路構成を簡略化し、論理規模を縮小のためにリソース量を削減することを目的のひとつとする。また、本発明は、多項式の入れ替え制御と、次数差が１より大きい場合の保護制御を行うことを目的のひとつとする。
本発明は、誤り評価多項式の候補Ｒｉ（ｚ）の演算の一部を行わなくても、必要な誤り位置多項式の候補Ｂｉ（ｚ）を算出できる、該誤り位置多項式を求めるための演算ユニット、エラー訂正復号回路及び演算方法を提供することを目的のひとつとする。また、本発明は、ステップ数に応じて不要なＲｉ（ｚ）の演算をやめ、この部分のガロア体の乗算と加算を、Ｂｉ（ｚ）の演算にまわす演算ユニット等を提供することを目的のひとつとする。本発明は、予め定められた記憶領域を有するメモリにおいて、Ｒｉ（ｚ）の係数が記憶される領域をステップ数に応じて削減し、その削減分を、Ｂｉ（ｚ）の係数が記憶される領域に割り当てることを目的のひとつとする。また、本発明は、ユークリッド互除法において、Ｒｉ（ｚ）の低次元項の計算をせずにＢｉ（ｚ）を導き出すことを目的のひとつとする。
【課題を解決するための手段】
【００１４】
本発明の第１の解決手段によると、
ＢＣＨ符号の誤り位置多項式を用いてｔワード（ｔは予め定められた整数）の誤り訂正を行うエラー訂正復号回路における該誤り位置多項式を求めるための演算ユニットであって、
第０乃至第２ｔの記憶領域を有し、シンドローム多項式の係数が第１乃至第２ｔの記憶領域に予め記憶される第１のレジスタと、
第０乃至第２ｔの記憶領域を有する第２のレジスタと、
前記第２のレジスタの第２ｔの記憶領域に記憶された係数を、前記第１のレジスタの第２ｔの記憶領域に記憶された係数でガロア体除算するガロア体除算器と、
前記ガロア体除算器の除算結果と、前記第１のレジスタの第０乃至第２ｔ−１の各係数をそれぞれガロア体乗算するガロア体乗算器群と、
前記ガロア体乗算器群で求められた各係数と、前記第２のレジスタの第０乃至第２ｔ−１の各係数とをそれぞれガロア体加算するガロア体加算器群と、
前記ガロア体加算器群からの出力又は前記第１のレジスタに記憶された各係数のいずれかを選択し、前記第１又は第２のレジスタに記憶された各係数のいずれかを選択する第１のセレクタと
前記第１のセレクタからの出力を、第１又は前記第２のレジスタの所定の記憶領域に記憶するためのシフターと、
前記第１のセレクタからの出力された各係数のひとつをゼロに置き換え又は削除する挿入ユニットと、
前記シフターからの出力を前記第１のレジスタ及び前記第２のレジスタの一方に記憶し、前記挿入ユニットからの出力を、前記第１のレジスタ及び前記第２のレジスタの他方に記憶するための第２のセレクタと
を備え、
前記ガロア体除算器と、前記ガロア体乗算器群と、前記ガロア体加算器群とによる演算を含むステップを繰り返し、誤り位置多項式の各係数を求める前記演算ユニットが提供される。
【００１５】
本発明の第２の解決手段によると、
ＢＣＨ符号の誤り位置多項式を用いてｔワード（ｔは予め定められた整数）の誤り訂正を行うエラー訂正復号回路であって、
入力信号からシンドローム多項式を求めるシンドローム演算ユニットと、
誤り位置多項式を求めるための演算ユニットと、
前記演算ユニットから出力される誤り位置多項式の係数に基づき、入力信号の誤りを訂正する誤り訂正ユニットと
を備え、
前記演算ユニットは、
第０乃至第２ｔの記憶領域を有し、前記シンドローム演算ユニットで求められたシンドローム多項式の係数が第１乃至第２ｔの記憶領域に記憶される第１のレジスタと、
第０乃至第２ｔの記憶領域を有する第２のレジスタと、
前記第２のレジスタの第２ｔの記憶領域に記憶された係数を、前記第１のレジスタの第２ｔの記憶領域に記憶された係数でガロア体除算するガロア体除算器と、
前記ガロア体除算器の除算結果と、前記第１のレジスタの第０乃至第２ｔ−１の各係数をそれぞれガロア体乗算するガロア体乗算器群と、
前記ガロア体乗算器群で求められた各係数と、前記第２のレジスタの第０乃至第２ｔ−１の各係数とをそれぞれガロア体加算するガロア体加算器群と、
前記ガロア体加算器群からの出力又は前記第１のレジスタに記憶された各係数のいずれかを選択し、前記第１又は第２のレジスタに記憶された各係数のいずれかを選択する第１のセレクタと
前記第１のセレクタからの出力を、第１又は前記第２のレジスタの所定の記憶領域に記憶するためのシフターと、
前記第１のセレクタからの出力された各係数のひとつをゼロに置き換え又は削除する挿入ユニットと、
前記シフターからの出力を前記第１のレジスタ及び前記第２のレジスタの一方に記憶し、前記挿入ユニットからの出力を、前記第１のレジスタ及び前記第２のレジスタの他方に記憶するための第２のセレクタと
を有し、前記ガロア体除算器と、前記ガロア体乗算器群と、前記ガロア体加算器群とによる演算を含むステップを繰り返し、誤り位置多項式の各係数を求め、前記誤り訂正ユニットに出力する前記エラー訂正復号回路が提供される。
【００１６】
本発明の第３の解決手段によると、
ＢＣＨ符号の誤り位置多項式を用いてｔワード（ｔは予め定められた整数）の誤り訂正を行うための該誤り位置多項式の演算方法であって、
第０乃至第２ｔの記憶領域を有する第２のレジスタから第２ｔの記憶領域に記憶された第１の係数を入力し、第０乃至第２ｔの記憶領域を有し、シンドローム多項式の係数が該第１乃至第２ｔの記憶領域に予め記憶された第１のレジスタから第２ｔの記憶領域に記憶された第２の係数を入力し、第１の係数を第２の係数でガロア体除算するガロア体除算処理と、
前記ガロア体除算処理の除算結果と、第１のレジスタの第０乃至第２ｔ−１の各係数をそれぞれガロア体乗算するガロア体乗算処理と、
前記ガロア体乗算処理で求められた各係数と、第２のレジスタの第０乃至第２ｔ−１の各係数とをそれぞれガロア体加算するガロア体加算処理と、
前記ガロア体加算処理の処理結果又は前記第１のレジスタの第０乃至第２ｔ−１の各係数を、第１又は第２のレジスタの所定の記憶領域に記憶するためにシフトするシフト処理と、
第１又は第２のレジスタに記憶された各係数のひとつをゼロに置き換え又は削除する挿入処理と、
前記シフト処理の処理結果を第１のレジスタ及び第２のレジスタの一方に記憶し、前記挿入処理の処理結果を、第１のレジスタ及び第２のレジスタの他方に記憶する記憶処理と
を備え、
前記ガロア体除算処理と、前記ガロア体乗算器処理と、前記ガロア体加算器処理を含むステップを繰り返し、誤り位置多項式の各係数を求める前記誤り位置多項式の演算方法が提供される。
【発明の効果】
【００１７】
本発明によると、最小の又は小さいレイテンシで、動作周波数を上げるために制御するための回路構成を簡略化し、論理規模を縮小のためにリソース量を削減することができる。また、本発明によると、多項式の入れ替え制御と、次数差が１より大きい場合の保護制御を行うことができる。
本発明によると、誤り評価多項式の候補Ｒｉ（ｚ）の演算の一部を行わなくても、必要な誤り位置多項式の候補Ｂｉ（ｚ）を算出できる、該誤り位置多項式を求めるための演算ユニット、エラー訂正復号回路及び演算方法を提供することができる。また、本発明によると、ステップ数に応じて不要なＲｉ（ｚ）の演算をやめ、この部分のガロア体の乗算と加算を、Ｂｉ（ｚ）の演算にまわす演算ユニット等を提供することができる。本発明によると、予め定められた記憶領域を有するメモリにおいて、Ｒｉ（ｚ）の係数が記憶される領域をステップ数に応じて削減し、その削減分を、Ｂｉ（ｚ）の係数が記憶される領域に割り当てることができる。また、本発明によると、ユークリッド互除法において、Ｒｉ（ｚ）の低次元項の計算をせずにＢｉ（ｚ）を導き出すことができる。
【００１８】
また、本発明によると、後述する３つの制御（１）〜（３）を行うにもかかわらず、構成が簡略化されているため従来のものより動作周波数は高く、リソース量は例えば以下のようになり、後に詳述する基本リソース量、特開５−１６５６６２、特開平７−２４０６９２のいずれと比べても少ない。
・レジスタの容量・・４ｔ＋２係数個分
・ガロア体除算器・・１個
・ガロア体乗算器・・２ｔ個、更に改良を加え論理規模を縮小可能
・ガロア体乗算（排他的論理和）器・・２ｔ個
【発明を実施するための最良の形態】
【００１９】
１．誤り訂正及び課題の具体例
図１３は、エラー訂正復号回路の構成例である。
ＢＣＨ符号の復号回路内のユークリッド演算ユニットａ２２（図１３参照）に着眼し改良を行った。ユークリッド演算ユニットは、シンドローム多項式から誤り位置多項式と誤り評価多項式を算出するユニットであり、他のユニットに比べ遥かに複雑な回路構成をもっている。このため、構成によっては復号回路の大半を占めるほど巨大になるか、あるいは、動作周波数が大幅に低くなり復号回路全体のパフォーマンスを落とす等の原因を作り易い。
【００２０】
ユークリッド演算ユニットの回路構成は、目的に合わせて最適なものを選ぶことができる。例えば、１度に四つの復号回路が動作している場合、例えば図１５のようにそのままユークリッド演算ユニットを４つ使う方法と、例えば図１７のようにレイテンシの長さを１／４倍にすることによって、同じ期間内に１つのユークリッド演算ユニットに４回分の処理をさせる方法がある。図１５のように構成するとタイムチャートは図１４のようになり、１つのユークリッド演算ユニットのレイテンシは図１７の場合に比べて長くてもよいものになる。一方、図１７のように構成するとタイムチャートは図１６のようになり、１つのユークリッド演算ユニットのレイテンシは図１６の場合に比べて短くなければならない。
【００２１】
一般に論理規模とレイテンシにはトレード・オフの関係があり、論理規模を小さくすればレイテンシは長くなり、論理規模を大きくすればレイテンシは短くなる。ただし、今回の場合は多少論理規模が大きくなったとしてもレイテンシを短くするようにしてもよい。この理由は、例えば図１３に示すようにユークリッド演算ユニットが、逆元ＲＯＭというガロア体除算器用のメモリを搭載しているからである。
【００２２】
ＢＣＨ＿２のユークリッド演算ユニットの場合、このメモリは約２２．５キロビットである。連接符号の例では、全部で４８個のＢＣＨ＿２の復号回路が搭載されるので全部で２２．５×４８＝１０８０．０キロビットものメモリがあることになる。そこで、図１７のようにＲＯＭの個数を減らすほうが連接符号の復号回路全体からみると効率的である。このため、レイテンシを最小（又は小さく）にすることを目的のひとつとしている。
【００２３】
ユークリッド演算は、シンドローム多項式Ｓ（ｚ）から以下のように誤り位置多項式σ（ｚ）、及び誤り評価多項式ω（ｚ）を求める方法である。ｔワードの誤り訂正を行う場合を例に挙げると、シンドローム多項式Ｓ（ｚ）は、以下の式で表せる。なお、シンドローム多項式は、１符号長の入力信号ａ１に基づき、シンドローム演算ユニットａ２１で求めることができる。
Ｓ（ｚ）＝ｓ２ｔｚ２ｔ−１＋ｓ２ｔ−１ｚ２ｔ−２＋  ・・  ＋ｓ２ｚ＋ｓ１  ・・（４）
誤り位置多項式σ（ｚ）は、ｊＬを誤り位置（Ｌ＝１〜ｔ）とすると、
σ（ｚ）＝（１−αｊ１）（１−αｊ２）・・（１−αｊＬ）  ・・（５）
誤り評価多項式ω（ｚ）は、
【数１】
0004767266.tif 000005
となり、それぞれの次数には以下の制限が付く。
ｄｅｇ  σ（ｚ）≦ｔ・・（７）
ｄｅｇ  ω（ｚ）≦ｔ−１・・（８）
【００２４】
誤り位置多項式σ（ｚ）、誤り評価多項式ω（ｚ）は、以下のように既知ｚ２ｔ、シンドローム多項式Ｓ（ｚ）の最大公約数を求める過程で得ることが出来る。ここでＲｉ（ｚ）を誤り評価多項式ω（ｚ）の候補、Ｂｉ（ｚ）を誤り位置多項式σ（ｚ）の候補となる多項式と定義し、添え字ｉは多項式の次数を示すものとする。
【００２５】
Ｒｉ（ｚ）は初期値として
Ｒ２ｔ（ｚ）＝ｚ２ｔ、Ｒ２ｔ−１（ｚ）＝Ｓ（ｚ）  ・・（９）
とおき、Ｒｉ（ｚ）の次数≦ｔ−１となるまで以下の計算を行う。
Ｒ２ｔ（ｚ）÷ｇ  Ｒ２ｔ−１（ｚ）＝Ｑ０（ｚ）  あまり  Ｒ２ｔ−２（ｚ）  ・・（１０）
Ｒ２ｔ−１（ｚ）÷ｇ  Ｒ２ｔ−２（ｚ）＝Ｑ１（ｚ）  あまり  Ｒ２ｔ−３（ｚ）  ・・（１１）
：
Ｒｔ＋２（ｚ）÷ｇ  Ｒｔ＋１（ｚ）＝Ｑｔ−２（ｚ）  あまり  Ｒｔ（ｚ）  ・・（１２）
Ｒｔ＋１（ｚ）÷ｇ  Ｒｔ（ｚ）＝Ｑｔ−１（ｚ）  あまり  Ｒｔ−１（ｚ）    ・・（１３）
ここで÷ｇはガウス・アルゴリズムの除算を示し、Ｑｉ（ｚ）は商となる多項式を示している。なお、ガウス・アルゴリズムの除算の場合、余剰多項式の次数は必ず被除数多項式の次数よりも低い。
【００２６】
上述の式１３の除算で、
ｄｅｇ  Ｒｔ−１（ｚ）  ≦  ｔ−１  ・・（１４）
となりＲｔ−１（ｚ）が誤り評価多項式ω（ｚ）になる。また、Ｒｉ（ｚ）の多項式の除算÷ｇはｔ回行われている。
【００２７】
一方、Ｂｉ（ｚ）は初期値として
Ｂ−１（ｚ）＝０、Ｂ０（ｚ）＝１  ・・（１５）
とおかれる。Ｂｉ（ｚ）の計算はＲｉ（ｚ）の次数≦ｔ−１になるまで以下のように行われる。つまりＢｉ（ｚ）の計算回数はＲｉ（ｚ）に依存していることになる。
Ｂ１（ｚ）＝Ｂ−１（ｚ）＋Ｑ０（ｚ）Ｂ０（ｚ）  ・・（１６）
Ｂ２（ｚ）＝Ｂ０（ｚ）＋Ｑ１（ｚ）Ｂ１（ｚ）  ・・（１７）
：
Ｂｔ−１（ｚ）＝Ｂｔ−３（ｚ）＋Ｑｔ−２（ｚ）Ｂｔ−２（ｚ）  ・・（１８）
Ｂｔ（ｚ）＝Ｂｔ−２（ｚ）＋Ｑｔ−１（ｚ）Ｂｔ−１（ｚ）  ・・（１９）
上記式１６〜式１９のＱｉ（ｚ）はＲｉ（ｚ）の式１０〜式１３で導き出された多項式である。式１９の計算で得られたＢｔ（ｚ）が誤り位置多項式σ（ｚ）となり、このときの次数は
ｄｅｇ  Ｂｔ（ｚ）≦ｔ  ・・（２０）
となり、Ｂｉ（ｚ）の計算もｔ回行われている。
【００２８】
ここで、Ｂｉ（ｚ）を計算するにはＱｉ（ｚ）を計算する必要があり、Ｑｉ（ｚ）を計算するには、Ｒｉ（ｚ）を計算する必要があることに注意されたい。つまり誤り位置多項式σ（ｚ）を計算するには、誤り評価多項式ω（ｚ）の計算が必要となる。
【００２９】
以下の表４の条件で具体例を説明する。
【表４】
0004767266.tif 000006
シンドローム多項式として、例えば、
Ｓ（ｚ）＝α２ｚ５＋α１０ｚ４＋α２ｚ３＋α１ｚ２＋α１ｚ＋α８  ・・（２１）
を用いる。初期値として
Ｒ６（ｚ）＝ｚ６、Ｒ５（ｚ）＝Ｓ（ｚ）、Ｂ−１（ｚ）＝０、Ｂ０（ｚ）＝α０＝１  ・・（２２）
とおく。するとＲｉ（ｚ）の計算は、図１８に示すように
Ｒ６（ｚ）÷ｇ  Ｒ５（ｚ）＝Ｑ０（ｚ）  あまり  Ｒ４（ｚ）  ・・（２３）
Ｒ５（ｚ）÷ｇ  Ｒ４（ｚ）＝Ｑ１（ｚ）  あまり  Ｒ３（ｚ）  ・・（２４）
Ｒ４（ｚ）÷ｇ  Ｒ３（ｚ）＝Ｑ２（ｚ）  あまり  Ｒ２（ｚ）  ・・（２５）
の計３回のガウス・アルゴリズムの除算が行われ、Ｒ２（ｚ）が誤り評価多項式ω（ｚ）となる。
【００３０】
このときＢｉ（ｚ）の計算は、図１９に示すように
Ｂ１（ｚ）＝Ｂ−１（ｚ）＋Ｑ０（ｚ）Ｂ０（ｚ）  ・・（２６）
Ｂ２（ｚ）＝Ｂ０（ｚ）＋Ｑ１（ｚ）Ｂ１（ｚ）  ・・（２７）
Ｂ３（ｚ）＝Ｂ１（ｚ）＋Ｑ２（ｚ）Ｂ２（ｚ）  ・・（２８）
の計３回の計算が行われ、Ｂ３（ｚ）が誤り位置多項式σ（ｚ）となる。
【００３１】
数学的には上記に示した通りＢｉ（ｚ）、Ｒｉ（ｚ）の計算を３回（一般にはｔ回）行うことにより求める誤り位置多項式σ（ｚ）、誤り評価多項式ω（ｚ）を得ることができるが、実際にＬＳＩへの実装を意識した場合、例えば、以下に述べるような方法で上記の計算を噛み砕く。
【００３２】
まず、Ｒｉ（ｚ）の計算から説明する。式２３はＴｅｍｐ＿Ｒ５（ｚ）を新たに定義することにより以下の２つの式、
Ｒ６（ｚ）÷ Ｒ５（ｚ）＝α１３ｚ  あまり  Ｔｅｍｐ＿Ｒ５（ｚ）  ・・（２９）
Ｔｅｍｐ＿Ｒ５（ｚ）÷ Ｒ５（ｚ）＝α６  あまり  Ｒ４（ｚ）  ・・（３０）
にわけることができる。ここで、Ｑ０（ｚ）は、式２９、式３０の商より、以下のように求めることができる。
Ｑ０（ｚ）＝α１３ｚ  ＋  α６  ・・（３１）
なお、ここでの除算では、剰余多項式の次数が必ずしも被除数多項式の次数よりも低いとは限らないので÷ｇではなく÷の記号を用いる。
【００３３】
このように、回路で式２３のような除算を１回ステップで行わず、式２９と式３０に分けて２回のステップで演算させている。今回のｔ＝３の場合は、図２０に示すように２×３＝６ステップによってＲｉ（ｚ）の計算を終える。ここでは、図２０の６ステップ目のＲ２（ｚ）が求める誤り評価多項式ω（ｚ）となる。
【００３４】
このとき、Ｂｉ（ｚ）でも、Ｔｅｍｐ＿Ｂ０（ｚ）を定義することにより、式２６を以下ように２つの式、
Ｔｅｍｐ＿Ｂ１（ｚ）＝Ｂ−１（ｚ）  ＋  α１３ｚＢ０（ｚ）  ・・（３２）
Ｂ１（ｚ）＝Ｔｅｍｐ＿Ｂ１（ｚ）  ＋  α６Ｂ０（ｚ）  ・・（３３）
にわけることができ、２回のステップで式２６の演算を行う。今回のｔ＝３の場合、図２１に示すように６ステップ後にＢｉ（ｚ）の計算を終える。ここでは、Ｂ３（ｚ）が求める誤り位置多項式σ（ｚ）となる。
【００３５】
本発明は、最小のレイテンシで行うことを目的のひとつとしているが、上記の方法で回路を構成するため、最小のレイテンシはこの６ステップ（一般に２ｔステップ）となる。
【００３６】
次に１回のステップに行われる係数毎の演算数についてＲｉ（ｚ）から述べる。まず、係数を削減せずに演算する場合について説明する。図２０に示すようにまずは、被除数多項式と除数多項式それぞれの次数と最高次係数を合わせるためのガロア体除算を１回行う。例えば、図２０の１ステップ目では、
α１３ｚ＝ｚ６  ／  α２ｚ５    ・・（３４）
行う。
【００３７】
次に、求められた係数（商）α１３ｚとＲ５（ｚ）の間で係数毎に６回のガロア体の乗算が行われる。これは、Ｒ５（ｚ）の係数が６個あるためである。次にガロア体の加算（排他的論理和）を係数毎に行う（Ｔｅｍｐ＿Ｒ５（ｚ）が求まる）。Ｒ６（ｚ）の係数はｚ６のみの１個にみえるが、実際には、ｚ５〜ｚ１までの係数をゼロとして扱い計６回（一般には２ｔ回）の加算が行われる。
【００３８】
Ｂｉ（ｚ）の演算回数も係数の個数分だけ必要なる。ｔ＝３の場合、ガロア体の加算と乗算の回数はいずれも４回（一般にはｔ＋１回）である。本来は図２１に示す通り、各ステップでＢｉ（ｚ）の係数の個数は異なる。このため、一番多い２ｔステップ目に合わせて演算回数を設定している。
【００３９】
ユークリッド演算ユニットには、ガロア体の除算、加算、乗算の他に、これらの演算を制御するための回路構成が必要となる。主なものとしては、例えば、（１）多項式の入れ替え制御と、（２）次数差＞１の保護制御の２つである。
【００４０】
まず、（１）多項式の入れ替えから説明する。図２０の２ステップ目では、Ｒ５（ｚ）は除数多項式である。しかし、３ステップ目ではＲ５（ｚ）は被除数多項式に入れ替わっている。また、Ｒ４（ｚ）は２ステップ目で剰余多項式であったが、３ステップ目ではＲ４（ｚ）は除数多項式に入れ替わっている。このように除数多項式、被除数多項式、剰余多項式は、常にその値を入れ替えるため、これらを制御する回路構成が必要となる。
【００４１】
次に、（２）次数差＞１の保護制御とは、被除数多項式と除数多項式の次数差が２以上になった時のための制御である。ユークリッドの演算では殆どの場合、図２０のように第１〜第６のどのステップでも、被除数多項式と除数多項式の次数差が１以下である。しかし、稀に図２２のように剰余多項式と被除数多項式の次数差が２次以上になることがある。この場合、次の計算で被除数多項式と除数多項式の次数差が２以上となる。この状態は回路からみると非常に特殊な状態であり、特別な制御を行わないと回路が対応できなくなる。例えば、係数０で除算する状態になる場合がある。
【００４２】
これら２つの制御を行う方法としては被除数多項式と除数多項式の次数を随時カウントしながら制御を行うことも考えられるが、この方法では動作周波数を著しく下げてしまう場合がある。このため、なんらかの工夫を行いこれらの制御を単純な回路構成で実現し動作周波数を上げることが、本発明のユークリッド演算ユニット改良の課題の１つである。
【００４３】
本発明のユークリッド演算ユニット改良には、論理規模の削減というもう１つの課題がある。ユークリッド演算ユニットをＬＳＩに実装するためには、Ｒｉ（ｚ）、Ｂｉ（ｚ）の係数用のレジスタを被除数多項式と除数多項式用に２種類もうけ、相互にカスケード接続を行う方法が考えられる。この手法に基づくＢｉ（ｚ）とＲｉ（ｚ）の両方の演算に必要なリソース量、つまりレジスタ、及び、演算器の個数は、ｔワードの誤り訂正を行う場合、Ｒｉ（ｚ）側で
・レジスタの容量・・（２ｔ＋１）×２＝４ｔ＋２係数個分
・ガロア体除算器・・１個
・ガロア体乗算器・・２ｔ個
・ガロア体加算（排他的論理和）器・・２ｔ個
となる。また、Ｂｉ（ｚ）側で
・レジスタの容量・・（ｔ＋１）×２＝２ｔ＋２係数個分
・ガロア体除算器・・０個
・ガロア体乗算器・・ｔ＋１個
・ガロア体加算（排他的論理和）器・・ｔ＋１個
となる。両方を合わせると
・レジスタの容量・・（３ｔ＋１）×２＝６ｔ＋４係数個分
・ガロア体除算器・・１個
・ガロア体乗算器・・３ｔ＋１個
・ガロア体加算（排他的論理和）器・・３ｔ＋１個
となる。リソースを削減することは論理規模の削減につながる。以後、本実施の形態の説明にあたり、上記のリソース量を基本リソース量とし、比較対照のために用いる。
【００４４】
纏めると、今回のユークリッド演算ユニットの改良は、例えば最小のレイテンシ（２ｔステップ）で、動作周波数を上げるために制御するための回路構成を簡略化し、論理規模を縮小のためにリソース量を削減することを目的のひとつとしている。
【００４５】
これまでにもユークリッド演算ユニットは、数多くの回路構成が考案されている。しかしながら、ユークリッド演算ユニットはＲＳ符号用に作成すれば、回路変更を必要とせずに、そのままＢＣＨ符号用に適用できるため、殆どの発明がＲＳ符号用である。このため、これらの発明はＢＣＨ符号専用として見ると未だ最適化の余地を残した回路構成となっている。この点を説明するため、特開５−１６５６６２号公報（特許文献１）、特開平７−２４０６９２号公報（特許文献２）の２つを例に用いる。
【００４６】
先に特開５−１６５６６２号公報の技術について述べる。この特許文献１では多重化させない場合（レイテンシ短い）と、多重化した場合（レイテンシ長い）に関する記述がある。しかし、本実施の形態ではレイテンシを短くする（最小の２ｔステップで済ませる）ことを目標とするため、多重化させない場合を説明する。
【００４７】
特開５−１６５６６２号公報の技術は、例えば、以下のように少ないリソースでユークリッド演算を実現している。
・レジスタの容量・・４ｔ＋３係数個分
・ガロア体除算器・・１個
・ガロア体乗算器・・２ｔ＋１個
・ガロア体乗算（排他的論理和）器・・２ｔ＋１個
【００４８】
しかしながら、少ないリソースを有効に使うため、制御回路では表５のように複雑な処理を行い各切替器（セレクタ）に信号を送る必要がある。
【表５】
0004767266.tif 000007
ここで、添え字ｊは、演算ユニットの番号であり１≦ｊ≦２ｔ−１である。この技術は、２ｔ−１個の演算ユニットから構成され、１個の演算ユニットが３種類のセレクタを有する。このため合計（２ｔ−１）×３種類のセレクタが６つの演算モードで制御されていることになる。このように不等号を多用して制御回路を複雑にしていくと、動作周波数が低くなる。加えて、この手法では２ｔ−１個の演算ユニットに対して別々に制御する。このため、ガロア体演算ほどにではないにしろ回路規模が増加することになる。
【００４９】
もう一つの例である特開平７−２４０６９２号公報の技術は、シントリック・アルゴリズム（電子通信学会論文誌’８６  １号ＶｏＬ．Ｊ６９−Ａ  Ｎｏ．３の第４２０〜４２８ページの「シストリックアルゴリズムに基づくＲｅｅｄ−Ｓｏｌｏｍｏｎ符号の復号器の構成法」）を改良したものであり、次数差＞１の保護を考慮しており、制御をおこなう回路が簡略化されている。このため、動作周波数も比較的高く、この技術であれば単価が安く性能が低いデバイスでも遅延問題は起き難いと想定される。
【００５０】
しかしながら、特開平７−２４０６９２号公報の技術は、以下のように多くのリソースを必要とする。
・レジスタの容量・・１１ｔ−３係数個分
・ガロア体除算器・・０個
・ガロア体乗算器・・４ｔ−２個
・ガロア体乗算（排他的論理和）器・・２ｔ−１個
さらに、この技術は誤り評価多項式ω（ｚ）算出後に、誤り位置多項式σ（ｚ）の演算を始めるため、レイテンシが長くなる。なお、この技術でレイテンシを２ｔステップにするよう改良を加えると、そのリソース量は以下のように増加する。
・レジスタの容量・・２２ｔ−６係数個分
・ガロア体除算器・・０個
・ガロア体乗算器・・８ｔ−４個
・ガロア体乗算（排他的論理和）器・・４ｔ−２個
このリソース量では、連接符号へ適用した場合の回路規模は巨大過ぎて実現性は乏しい。
【００５１】
ＲＳ符号用のユークリッド演算ユニットは、その機能として誤り位置多項式σ（ｚ）と誤り評価多項式ω（ｚ）を算出する回路構成となっている。ただし、図２３のように誤り位置多項式σ（ｚ）は何ワード目が誤りかを算出するためのものであるのに対し、誤り評価多項式ω（ｚ）は何ビット目が誤りかを算出するものである。このため、二元（１ワード＝１ビット）であるＢＣＨ符号にとっては、誤り位置多項式σ（ｚ）のみが必要であり、誤り評価多項式ω（ｚ）は不要という特性がある。つまり、上述の技術では、ＢＣＨ符号にとっては不要な誤り評価多項式ω（ｚ）の全係数を算出する算出回路をもち、これが回路規模の増加や動作周波数の低下を引き起こし、連接符号への適応を困難にする原因のひとつとなっている。
【００５２】
しかしながら、ＲＳ符号専用であれ、ＢＣＨ符号専用であれ、ユークリッド演算ユニットから、むやみに誤り評価多項式ω（ｚ）の演算回路を取り外すことは出来ない。重ねて説明することになるが、これは、誤り位置多項式σ（ｚ）の候補となるＢｉ（ｚ）を算出するには、誤り評価多項式ω（ｚ）の候補となるＲｉ（ｚ）の計算過程で算出される商多項式Ｑｉ（ｚ）が必要なためである。
【００５３】
このため、何らかの手法により必要な誤り位置多項式σ（ｚ）のみ演算するような回路構成にできれば、ＢＣＨ符号にとっては本来余分なリソースを削減することが出来る。
【００５４】
この要求に答えるため、本発明は、Ｒｉ（ｚ）の演算の一部を行わなくても必要なＢｉ（ｚ）を算出できる装置、方法、アルゴリズムを提供することを目的のひとつとしている。
【００５５】
２．本実施の形態の演算
図２４は、必要なＲｉ（ｚ）の計算と不必要なＲｉ（ｚ）の計算の説明図である。
多項式同士の計算においては、確かに必要なＢｉ（ｚ）を求めるためにはＲｉ（ｚ）の計算が必要である。しかし、実は係数ごとの演算で見ていくと全てのＲｉ（ｚ）の係数の演算が必要でないことがわかる。説明を簡単にするため、上術のｔ＝３のＲｉ（ｚ）とＢｉ（ｚ）の計算例を参考にしながら今度は逆に６ステップ目から図２４、図２１を用いて説明する。
【００５６】
Ｂｉ（ｚ）の演算にとって商Ｑｉ（ｚ）が必要なことは前述した通りである。逆を言えば必要な商Ｑｉ（ｚ）の値さえわかれば、全てのＲｉ（ｚ）演算をしなくても良い。
この例の６ステップ目においてＢｉ（ｚ）側では以下の演算が行われる（図２１参照）。
Ｂ３（ｚ）＝Ｔｅｍｐ＿Ｂ３（ｚ）  ＋α０１Ｂ２（ｚ）  ・・（３５）
Ｒｉ（ｚ）側では、Ｂｉ（ｚ）にとって必要な商α０１＝α１２／α１１は既にガロア体除算で算出されているため、６ステップ目ではＲｉ（ｚ）側ではガロア体の乗算と加算を行う必要がない。６ステップ目の演算が不要な部分に二重線をひくと図２４のようになる。
【００５７】
５ステップ目においてはＢｉ（ｚ）側では以下の演算が行われる。
Ｔｅｍｐ＿Ｂ３（ｚ）＝Ｂ１（ｚ）  ＋α８Ｂ２（ｚ）  ・・（３６）
Ｒｉ（ｚ）側では、商α８＝α４／α１１は既にガロア体除算で算出されている。また、次の６ステップのガロア体除算でα１２を使用するため、３次のガロア体の乗算と加算だけは行う必要がある。しかし、３次以外の演算は必要とされない。このため図２４の５ステップ目では、３次以外には二重線がひかれる。
【００５８】
同様に、４ステップ目の説明をする。ここでは３次と２次の演算のみが必要となる。３次の演算結果α１１は５ステップ目のガロア体除算α４／α１１の分母となり、２次の演算結果α１１は５ステップ目の３次の計算α１２＝α６＋α８×α１１で使われるためである。同様にして、ここで１ステップ目までステップ数を戻すと、やはりどのステップでも演算が不要な係数がある。図２４は、各ステップでの不要な演算を二重線で示している。
【００５９】
結果Ｂｉ（ｚ）にとって必要なＲｉ（ｚ）のガロア体の乗算と加算の演算回数は、１ステップ時に５回づつ、２ステップ時に４回づつ、・・・・、５ステップ時に１回づつ、６ステップ時に０回となる。
【００６０】
一方、Ｂｉ（ｚ）のガロア体の乗算と加算の演算回数は図２１に示す通り、ステップ数が増える度にガロア体の乗算と加算の演算回数は増えていく。つまり、ステップ数に応じて不要なＲｉ（ｚ）の演算をやめ、この部分のガロア体の乗算と加算をＢｉ（ｚ）の演算にまわす制御方法を実現すれば、ＢＣＨ用にユークリッド演算ユニットを最適化することができる。以後、この制御をＲｉ（ｚ）とＢｉ（ｚ）の演算器の調整と呼ぶことにする。また、係数を記憶するレジスタも、Ｒｉ（ｚ）の係数が減る分をＢｉ（ｚ）の係数が増える分に割り当てれば、レジスタの有効利用ができる。
【００６１】
しかしながら、これまでの２つの制御である（１）多項式の入れ替えと（２）次数差＞１の保護に加え、新しく（３）Ｒｉ（ｚ）とＢｉ（ｚ）の演算器の調整が追加されたため、回路構成が複雑になり、逆に最適化を妨げる可能性も当然出てくる。ところが、本実施の形態では、以下具体的に示す手法により、この制御を簡単な構成で実現でき、更にリソースを低減する回路を提供できる。
【００６２】
３．ハードウェア構成
本実施の形態のエラー訂正復号回路ａ３は、例えば、図３に示す構成を備える。例えば、エラー訂正復号回路ａ３は、シンドローム演算ユニットａ２１と、ユークリッド演算ユニットａ２２と、チェーンサーチユニットａ２３と、誤り訂正ユニットａ２４と、遅延回路ａ２０と、逆元ＲＯＭａ２５とを備える。なお、逆元ＲＯＭａ２５は、ユークリッド演算ユニットａ２２内に備えられても良い。
エラー訂正復号回路は、例えば、図１５や図１７に示す構成であってもよい。図１７の構成において、エラー訂正復号回路は、ユークリッド演算ユニットａ４０に対して、シンドローム演算ユニットａ２１と誤り訂正ユニットａ２４とをそれぞれ複数備える。ユークリッド演算ユニットａ４０は、複数のシンドローム演算ユニットａ２１からシンドローム多項式を入力し、誤り位置多項式を求める。また、ユークリッド演算ユニットａ４０は、求められた誤り位置多項式を、該シンドローム演算ユニットに対応するチェーンサーチユニットａ２３を介して、誤り訂正ユニットａ２４に出力する。
【００６３】
図１は、本実施の形態のユークリッド演算ユニットａ２２、ａ４０の構成図である。アルゴリズムを実現する回路構成について図１を参照しながら述べていく。
ユークリッド演算ユニットは、レジスタ１０（第１のレジスタ）と、レジスタ２０（第２のレジスタ）と、演算ユニット３０と、シーケンサー（制御部）４０と、シフター５０と、ゼロ挿入ユニット６０と、セレクタ７０、８０とを備える。
図２５は、レジスタ１０とレジスタ２０の説明図である。
まず、レジスタ１０とレジスタ２０について説明する。実際にはＲｉ（ｚ）とＢｉ（ｚ）の係数を一つにまとめ扱うほうが便利であるため、これらをまとめた仮想的な多項式の係数で議論する。まず、図２５の初期値のようにレジスタ１０とレジスタ２０に代入される。ここでは、式２１のシンドローム多項式の係数を初期値の例とする。このとき、レジスタ１０の＃６〜＃１がＲ５（ｚ）の係数、＃０がＢ０（ｚ）の係数であり、レジスタ２０の＃６〜＃１がＲ６（ｚ）の係数、＃０がＢ−１（ｚ）の係数である。
【００６４】
このようにＲｉ（ｚ）とＢｉ（ｚ）の係数を纏めることで、必要なレジスタの容量は基本リソース量と比べると６ｔ＋４から４ｔ＋２まで削減され、ガロア体の乗算と加算の回数も３ｔ＋１回から２ｔ＋１回となる。ただし、実際には図２４のように多項式の最高次＃２ｔの係数の乗算、加算は不要であるため、これらの演算回数は２ｔ回となり、結局、ガロア体の乗算器と加算器の数はそれぞれ２ｔ個となる。
【００６５】
図２は、演算ユニット３０の構成図である。
次に図１の演算ユニット３０の回路構成を図２を参照して説明する。図２４と図２１の１ステップ目の演算を例とすると、演算ユニット３０では、
α１３ｚ＝ｚ６  ／  α２ｚ５    ・・（３７）
Ｔｅｍｐ＿Ｒ５（ｚ）＝Ｒ６（ｚ）＋α１３ｚＲ５（ｚ）  ・・（３８）
Ｔｅｍｐ＿Ｂ１（ｚ）＝Ｂ−１（ｚ）＋α１３ｚＢ０（ｚ）  ・・（３９）
といったガロア体の演算が行われる。
【００６６】
演算ユニット３０は図２で示す通り、ガロア体の逆元ＲＯＭ３１０、乗算器３４０、３２０、加算器３３０を具備している。なお、図２の逆元ＲＯＭ３１０、ガロア体乗算器３４０が、上述のガロア体除算器に相当する。最初に行われる式３７の係数のガロア体除算は、
α０  ×  （１／α２）   ・・（４０）
として、逆元値との乗算に直す。ここでは１／α２がα２の逆元値である。逆元値は図１１のテーブルのようにあらかじめ値をメモリに登録したものを使うことができる。以後、このため、このメモリは逆元ＲＯＭと呼ばれている。図１１のようにα２の逆元値はα１３となる。
【００６７】
次に式３８と式３７の乗算部分である
α１３ｚ×  Ｒ５（ｚ）  ・・（４１）
α１３ｚ×  Ｂ０（ｚ）  ・・（４２）
が図２ガロア体乗算器群で行われる。この乗算器は今回の場合、例えば２ｔ個存在する。
【００６８】
最後にガロア体乗算器群３２０から出力されたα１３ｚＲ５（ｚ）とα１３ｚＢ０（ｚ）に対し図２のガロア体加算器群３３０でＲ６（ｚ）とＢ−１（ｚ）を加算し、Ｔｅｍｐ＿Ｒ５（ｚ）とＴｅｍｐ＿Ｂ１（ｚ）を出力する。このガロア体加算器数も、例えば２ｔ個存在する。回路としてはＲｉ（ｚ）とＢｉ（ｚ）の係数を纏めているので表６のように出力される。
【表６】
0004767266.tif 000008
ここで、表６の＃５〜＃１がＴｅｍｐ＿Ｒ５（ｚ）を示し、＃０がＴｅｍｐ＿Ｂ１（ｚ）を示している。
【００６９】
図３は、演算モードの説明図である。
次にシーケンサー４０とそれらに制御されるセレクタ７０とセレクタ８０の説明を行う。シーケンサー４０は、内部変数として仮想的な被除数多項式の次数、除数多項式の次数、を持っており（あくまで仮想的な次数であり、実際の値とは異なる）、入力信号としてレジスタ１０の＃２ｔの値を受ける。ここで、以下のように変数（パラメータ）を定義する。
ｄＶ＝仮想的な被除数多項式の次数（初期値は０）；    ・・（４３）
ｄＷ＝仮想的な除数多項式の次数（初期値は０）；    ・・（４４）
Ｒ１０２ｔ＝レジスタ１０の＃２ｔの値；        ・・（４５）
シーケンサー４０は、ｄＶ、ｄＷ、Ｒ１０２ｔから以下の３つの演算モードを作り、演算モードの応じてセレクタ７０とセレクタ８０を表７のように制御する。
【表７】
0004767266.tif 000009
ここでＳＥＬ＿１はセレクタ７０、ＳＥＬ＿２はセレクタ８０の制御信号を示している。表５に示した特開５−１６５６６２の制御回路は、６つの演算モードを持ち、（２ｔ−１）×３種類のセレクタを制御していた。これに対して本実施の形態の制御回路は、演算モード数は３つであり、しかも制御しているセレクタはわずか２種類である。この点でも本実施の形態の制御回路は大幅に簡略化されている。
【００７０】
なお、ｄＶとｄＷはモード毎に以下のように値が変化する。
・演算モード１の時  ｄＶ＝ｄＶ＋１；  ・・（４６）
・演算モード２の時  ｄＶ＝ｄＷ；  ・・（４７）
・演算モード３の時  ｄＷ＝ｄＷ＋１；  ・・（４８）
【００７１】
図３にシーケンサー４０によって制御されたデータの流れを示す。図２４と図２１の１ステップ目の例では、Ｒ１０２ｔ、つまりレジスタ１０の＃６の値はα２≠０であり、ｄＶ、ｄＷは互いに初期値０であるため、演算モード３になる。動作モード３では、シーケンサー４０は、ＳＥＬ＿１＝０を出力してセレクタ７０の「０」を有効にし、ＳＥＬ＿２＝０を出力してセレクタ８０の「０」を有効にする。このため、演算ユニット３０からの出力はシフター５０を通ってレジスタ２０に格納され、レジスタ１０の値はゼロ挿入ユニット６０を通って再び、レジスタ１０に格納される。
動作モード２では、シーケンサー４０は、ＳＥＬ＿１＝０を出力してセレクタ７０の「０」を有効にし、ＳＥＬ＿２＝１を出力してセレクタ８０の「１」を有効にする。このため、演算ユニット３０からの出力はシフター５０を通ってレジスタ１０に格納され、レジスタ１０の値はゼロ挿入ユニット６０を通って、レジスタ２０に格納される。
動作モード１では、シーケンサー４０は、ＳＥＬ＿１＝１を出力してセレクタ７０の「１」を有効にし、ＳＥＬ＿２＝１を出力してセレクタ８０の「１」を有効にする。このため、レジスタ１０の値はシフター５０を通ってレジスタ１０に再び格納され、レジスタ２０の値はゼロ挿入ユニット６０を通って再びレジスタ２０に格納される。
【００７２】
次に、図１のシフター５０の説明を行う。シフター５０は表８のような係数を表９のように左に１つシフトさせる。上述のステップ１の例では、演算ユニット３０からの出力をシフトさせたことになる。この処理は、Ｒｉ（ｚ）の最高次係数を常にレジスタの＃６（一般に＃２ｔ）おき、更に被除数多項式と除数多項式が持つ各々の次数の係数を合わせて演算ユニット３０でのガロア体演算を行わせるための制御である。
【表８】
0004767266.tif 000010
【表９】
0004767266.tif 000011
【００７３】
次に、図１のゼロ挿入ユニット６０の説明を行う。ゼロ挿入ユニット６０はステップ数番目の値を消去する仕組みになっている。例えば、ステップ数が１のときは表１０の係数は表１１のように＃１の係数値が消去される。同様にステップ数がｎのときは、＃ｎ番目の係数が消去される。この仕組みが、ステップ数に応じて不要なＲｉ（ｚ）の演算をやめ、この部分のガロア体の乗算と加算をＢｉ（ｚ）の演算にまわす制御である。今回のステップ１の例では、Ｒ５（ｚ）のα８が消去されている。図２４を用いた説明で明らかにしたように、このα８は次のステップ２ではもはや使われなくなる。このため、メモリの＃１を０にして、ステップ２でＢｉ（ｚ）の係数が入力できるようにしている。
【表１０】
0004767266.tif 000012
【表１１】
0004767266.tif 000013
【００７４】
このように演算モード２と演算モード３によって被除数多項式、除数多項式、剰余多項式の入れ替え制御が行われる。被除数多項式と除数多項式の次数差が２以上の制御場合は演算モード１の制御が行われる。次数差が２以上になった場合、回路から見るとあたかも被除数多項式の最高次係数が０のように見える（Ｒ１０２ｔ＝０となる）。演算モード１を行うことで、被除数多項式の最高次係数≠０となるまでシフトを行い、レジスタ１０とレジスタ２０に格納されている各々の多項式の次数差を制御している。
【００７５】
図４は、本実施の形態の一連の動作を説明するためのフローチャートである。
図４のフローチャート、及び、図２１、図２４、図２５等の例を参照して、本実施の形態の動作の具体例を説明する。なお、本実施の形態では、σ(ｚ)＝Ｂｔ(ｚ)/Ｂｔ(０)の規格化は省略している。また、図４でのカウンタは０からスタートしているので、カウンタの値（ｃｎｔ）は、図２０と図２１のステップ数から１引いた値となっている。また、図２５の例においては、誤り訂正のワード数ｔはｔ＝３である。
まず、ユークリッド演算ユニットａ２２は、初期設定を行う（処理Ｓ１１）。例えば、シーケンサー４０（又はゼロ挿入部６０）は、カウンタを０に設定する（ｃｎｔ＝０）。また、シーケンサー４０は、パラメータｄＶ、ｄＷを０に設定する（ｄＶ＝０、ｄＷ＝０）。また、レジスタ１０の記憶領域＃１〜＃２ｔ（以下、＃ｉのように記す）に、入力したシンドローム多項式の係数ＳＤｉを記憶する（Ｒ１０ｉ＝ＳＤｉ−１（ｉ＝１、‥、２ｔ））。レジスタ１０の＃０には、初期値１（α００）を記憶する（Ｒ１００＝１）。また、レジスタ２０の最高次の＃２ｔに初期値１（α００）を記憶する（Ｒ２０２ｔ＝１）。レジスタ２０の＃０〜＃２ｔ−１には、初期値０を記憶する（Ｒ２０ｉ＝０（ｉ＝０、‥、２ｔ−１））。以上の処理により、レジスタ１０及びレジスタ２０は、例えば、図２５の初期値のように設定される。
次に、例えばシーケンサー４０により、レジスタ１０の最高次＃２ｔの係数が０でないか判断する（処理Ｓ１３）。０でなければ処理Ｓ１５に移り、０であれば処理Ｓ２９に移る。
処理Ｓ１５では、演算ユニット３０は、レジスタ２０の最高次＃２ｔに記憶された係数を、レジスタ１０の最高次＃２ｔに記憶された係数でガロア体除算して、商Ｑ２ｔを求める（Ｑ２ｔ＝Ｒ２０２ｔ／Ｒ１０２ｔ）。例えば、図２の逆元ＲＯＭ３１０、ガロア体乗算器３４０によりガロア体除算される。例えば、１ステップ目においては、演算ユニット３０は、レジスタ２０の＃６の係数１（α００）をレジスタ１０の＃６の係数α０２でガロア体除算して、商α１３ｚを求める（図２４の１ステップ目、図２５の初期値参照）。
また、演算ユニット３０は、レジスタ１０の＃０〜＃２ｔ−１の各係数と、求められた商Ｑ２ｔをガロア体乗算し、乗算結果とレジスタ２０の＃０〜＃２ｔ−１の各係数とをガロア体加算して出力する（Ｍ３０ｉ＝Ｒ２０ｉ＋Ｑ２ｔ・Ｒ１０ｉ（ｉ＝０、‥、２ｔ−１））。例えば、図２のガロア体乗算器群３２０及びガロア体加算器群３３０により、ガロア体乗算及び加算される。なお、加算結果に対し、最高位＃２ｔに０をつけて出力してもよい（Ｍ３０２ｔ＝０）。例えば、１ステップ目においては、レジスタ１０の＃１〜＃５の各係数と、商α１３ｚを乗算し、レジスタ２０の＃１〜＃５の各係数に加算されて剰余多項式Ｔｅｍｐ＿Ｒ５（ｚ）の各係数が求められる（図２４、２５参照）。また、レジスタ１０の＃０の係数と商α１３ｚを乗算し、レジスタ２０の＃０の係数に加算されてＴｅｍｐ＿Ｂ１（ｚ）の係数が求められる（図２１、２５参照）。なお、Ｒｉ（ｚ）側の処理と、Ｂｉ（ｚ）側の処理は、ガロア体乗算器群３２０及びガロア体加算器群３３０でまとめて行うことができる。
処理Ｓ１７では、例えば、シーケンサー４０により、パラメータｄＶがパラメータｄｗ以上かを判断する。ｄＶがｄＷ以上であれば動作モード３に対応する処理Ｓ１９に移り、一方、ｄＶがｄＷ以上でなければ動作モード２に対応する処理Ｓ２５に移る。なお、１ステップ目では、処理Ｓ１９へ移る。
処理Ｓ１９では、シーケンサー４０は、パラメータｄＷを１増加する（ｄＷ＝ｄＷ＋１
）。また、レジスタ１０の記憶領域のうち、カウンタの値＋１（ｃｎｔ＋１）に対応する領域を０に書き換える（Ｒ１０ｉ＝０（ｉ＝ｃｎｔ＋１））。例えば、ゼロ挿入部６０により、レジスタ１０からの各係数のうち、カウンタの値＋１に対応する領域の係数をゼロにし、他の係数はそのままにして再度レジスタ１０に書き込む。図２５の例では、レジスタ１０の＃１の係数α０８が０に書き換えられる。なお、上述の通り、カウンタの値＋１は図２１及び図２４等のステップ数に対応する。なお、カウンタの初期値、カウント手法に応じて、ステップ数に応じた係数を削除するよう適宜変更してもよい。
また、演算ユニット３０の出力をレジスタ２０に記憶する。例えば、演算ユニット３０の出力Ｍ３０ｉ−１（ｉ＝１、‥、２ｔ）を、レジスタ２０の＃１〜＃２ｔに記憶し、レジスタ２０の＃０に０を記憶する（Ｒ２０ｉ＝Ｍ３０ｉ−１（ｉ＝１、‥、２ｔ）、Ｒ２００＝０）。例えば、シフター５０は、ガロア体加算器群３３０におけるレジスタ２０の＃０乃至＃２ｔ−１の各係数との加算結果を、レジスタ１０又はレジスタ２０の＃１乃至＃２ｔの記憶領域に記憶されるようシフトする。これにより、レジスタ２０に、Ｔｅｍｐ＿Ｒ５（ｚ）の各係数と、Ｔｅｍｐ＿Ｂ１（ｚ）の係数が記憶される（図２５、１ステップ後参照）。
処理Ｓ２１では、例えば、カウンタの値が予め定められた回数２ｔ−１になったか判断する。すなわち、２ｔ回のステップを繰り返したか判断する。２ｔ回のステップを繰り返していれば、処理Ｓ２７に進む。一方、２ｔ回のステップを繰り返していなければ、処理Ｓ２３でカウンタを１増加して（ｃｎｔ＝ｃｎｔ＋１）、処理Ｓ１３以降のステップを繰り返す。
２ステップ目でも、上述の処理Ｓ１３、Ｓ１５と同様に演算される（図２１、図２４の２ステップ目参照）。例えば、２ステップ目において処理Ｓ１５では、演算ユニット３０は、レジスタ２０の＃６の係数α０８をレジスタ１０の＃６の係数α０２でガロア体除算して、商α０６を求める（図２４の２ステップ目、図２５の１ステップ後参照）。また、例えば、２ステップ目においては、レジスタ１０の＃２〜＃５の各係数と、商α０６が乗算され、レジスタ２０の＃２〜＃５の各係数に加算されることで剰余多項式Ｒ４（ｚ）の各係数が求められる（図２４、２５参照）。また、レジスタ１０の＃０の係数と商α１３ｚを乗算し、レジスタ２０の＃０〜＃１の係数に加算されることでＢ１（ｚ）の係数が求められる（図２１、２５参照）。また、２ステップ目（偶数ステップ）では、処理Ｓ１７において、ｄＶがｄｗ以上ではないと判断され、処理Ｓ２５が実行される。
処理Ｓ２５では、シーケンサー４０は、パラメータｄＶにパラメータｄＷの値を代入する（ｄＶ＝ｄＷ）。また、レジスタ１０の係数のうち、カウンタの値＋１（ｃｎｔ＋１）に対応する領域を０に書き換え、レジスタ２０に記憶する（Ｒ２０ｉ＝Ｒ１０ｉ（ｉ＝０、‥、ｃｎｔ、ｃｎｔ＋２、‥、２ｔ）、Ｒ２０ｉ＝０（ｉ＝ｃｎｔ＋１））。例えば、ゼロ挿入部６０により、レジスタ１０からの各係数のうち、カウンタの値＋１に対応する領域の係数をゼロにし、他の係数はそのままにしてレジスタ２０に書き込む。図２５の例では、レジスタ１０の＃２の係数α０１が０に書き換えられ、各係数がレジスタ２０に記憶される（図２５の１ステップ後及び２ステップ後参照）。
また、演算ユニット３０の出力をレジスタ１０に記憶する。例えば、演算ユニット３０の出力Ｍ３０ｉ−１（ｉ＝１、‥、２ｔ）を、レジスタ１０の＃１〜＃２ｔに記憶し、レジスタ１０の＃０に０を記憶する（Ｒ１０ｉ＝Ｍ３０ｉ−１（ｉ＝１、‥、２ｔ）、Ｒ１００＝０）。これにより、２ステップ目では、レジスタ１０に、求められたＲ４（ｚ）の各係数とＢ１（ｚ）の各係数が記憶される（図２５、２ステップ後参照）。
３ステップ目以降の各奇数ステップにおいても、上述の１ステップ目と同様に処理が実行され、４ステップ目以降の各偶数ステップにおいても、上述の２ステップ目と同様に処理が実行される。
なお、各ステップにおいて、処理Ｓ１３でレジスタ１０の最高次＃２ｔの係数が０のとき、動作モード１に対応する処理Ｓ２９に移る。処理Ｓ２９では、シーケンサー４０は、パラメータｄＶを１増加する（ｄＶ＝ｄＶ＋１）。また、レジスタ１０の係数の記憶領域をシフトし（Ｒ１０ｉ＝Ｒ１０ｉ−１（ｉ＝１、‥、２ｔ））、レジスタ１０の＃０に０を記憶する（Ｒ１００＝０）。また、レジスタ２０の記憶領域のうち、カウンタの値＋１（ｃｎｔ＋１）に対応する領域を０に書き換え、レジスタ２０に記憶する（Ｒ２０ｉ＝Ｒ２０ｉ（ｉ＝０、‥、ｃｎｔ、ｃｎｔ＋２、‥、２ｔ）、Ｒ２０ｉ＝０（ｉ＝ｃｎｔ＋１））。
以上の処理が２ｔステップ繰り返されると処理Ｓ２７に移り、レジスタ１０に記憶された係数のうち、誤り多項式の係数を出力する。例えば、誤り位置多項式の次数ｄσにパラメータｄＷを代入する。また、ｉ＝０〜ｄσについて、パラメータｊをｊ＝２ｔ−ｄσ＋ｉにより求め、レジスタ１０の＃ｊの係数を、誤り多項式のｚｉの係数として出力する。例えば、図２５の例では、レジスタ１０の＃６〜＃３に記憶された係数（図２１のＢ３（ｚ）に対応）が出力される。なお、最後のステップでは、レジスタ１０に記憶せずに演算結果（図２１の例ではＢ３（ｚ））をそのまま出力してもよい。
【００７６】
ここで、初期値から６ステップまでの演算結果を具体例として図２５に示す。図２５において１ステップ後では＃１〜＃０の値、２ステップ後では＃２〜＃０の値、・・・・、６ステップ目では＃６〜＃３の値がＢｉ（ｚ）の係数となっている。今回の例では、図２５の６ステップ目の＃６〜＃３の値が求める誤り位置多項式σ（ｚ）である。一般にはレジスタ１０と求める誤り位置多項式σ（ｚ）の係数の関係は図２６のようになる。
例えば、ユークリッド演算ユニットａ２２は、２ｔステップの後ガロア体加算器群３３０から出力される係数のうち、又は、２ｔステップの後レジスタ１０に記憶された係数のうち、誤り位置多項式の次数に応じた個数を、誤り位置多項式の係数として出力する。また、例えば、２ｔステップの後第１のレジスタに記憶された係数のうち、＃２ｔ乃至＃ｔの記憶領域に記憶されたｔ＋１個の係数を、誤り位置多項式の係数として出力する。
【００７７】
本実施の形態により、３つの制御、つまり（１）多項式の入れ替え、（２）次数差＞１の保護、（３）Ｒｉ（ｚ）とＢｉ（ｚ）の演算器の調整を単純化な回路構成で実現し動作周波数を上げると同時に、ガロア体演算とレジスタの削減を実現することができる。
【００７８】
４．性能比較
ここで、冒頭で述べたＩＴＵ−Ｔの勧告Ｇ．９７５．１の連接符号の復号回路に対して、本実施の形態のユークリッド演算ユニットの改良がどれだけ寄与したかを見ていく。ただし、全体を述べると話が複雑になるので、比較はＢＣＨ＿２の復号回路が４８個使われた部分のみにとどめる。
【００７９】
下の表１２は、改良前と改良後のユークリッド演算ユニット１個をＬＳＩに実装した後の回路規模、メモリ、動作周波数を示している。実際の論理規模と動作周波数の値は、搭載するＬＳＩによって異なってしまうため、ここでは大体の比率の比較のみにとどめる。目安として改良前のレイテンシが長いユニットの論理規模を１００とする。なお、実装結果であるため、レイテンシの単位はステップからクロックに変わっているが同じ意味である。
【表１２】
0004767266.tif 000014
【００８０】
勧告の仕様ではＢＣＨ＿２のユークリッド演算ユニットは２５５クロック以内で演算を終えなくてはいけない。ユークリッド演算ユニットのレイテンシを２５５クロック以内に収めるには、そりなりに工夫が必要になるが、ここではその方法についてまでは述べない。
【００８１】
次に、これらのユークリッド演算ユニットが図１７で見たように１度に四つの復号回路が動作している場合を考える。すると表１３のようになる。ここでレイテンシが短いほうのユークリッド演算ユニットは、前後のシンドローム演算ユニットとチェーンサーチユニットとの間で入出データのタイミングを調整するための回路が加わっている。本出願人が設計したものでは、この回路の論理規模は例えば１５となった。表１２からもわかる通り改良後のものは、改良前のものより、全の項目において勝っている。
【表１３】
0004767266.tif 000015
【００８２】
表１４にＢＣＨ＿２の復号回路が４８個使われた部分での比較を示す。ユークリッドの演算処理は２５５クロックを越えない限り繰り返して使うことができるため、今度はレイテンシが短いものを８回処理させた場合の効果を示した。表１４の中で、他ユニットとはユークリッド演算ユニット以外のユニットを全て足し合わせたものである。その他のメモリも同様にユークリッド演算ユニット以外に使用されたメモリを足し合わせた結果である。なお、本出願人の設計では、１つの復号回路あたり、他ユニット論理の論理規模が１２５、メモリが約２２．３キロビットとなっている。
【表１４】
0004767266.tif 000016
【００８３】
このように４８個のＢＣＨ＿２復号回路が使われている部分では、全体として論理規模が約３０％、メモリは約６０％だけ削減できていることがわかる。しかし、この値はデバイスによって多少は異なるため、実際は論理規模の削減率は２０％〜３０％の場合もある。
【００８４】
また、前述の通りユークリッド演算ユニットは他ユニットに比べると複雑であるため、回路全体の動作周波数を下げる要因になり易い。このため、今回のユークリッド演算ユニットの改良により、４８個のＢＣＨ＿２復号回路全体のパフォーマンスも改善されている。
【００８５】
このように、本発明によるＢＣＨ符号装置の改良は光ファイバ通信の支流になりつつある連接符号の実用化において非常に有用であり、今後更に重要になると考えられる。もちろん、通信に限らずＢＣＨ符号の多元化、誤り訂正ワード数の増加は今後も進んでいくと思われる。このため、本発明は誤り訂正技術を用いる全ての分野においても有効に利用されることが期待される。
【産業上の利用可能性】
【００８６】
本発明は、例えば、光通信におけるエラー訂正復号に利用可能である。本発明は、ＢＣＨ符号を用いてエラー訂正復号する分野に利用可能である。また、通信、コンピュータ、オーディオ・ビデオ等の分野におけるエラー訂正に利用可能である。
【図面の簡単な説明】
【００８７】
【図１】本発明の回路構成図。
【図２】演算ユニット３０の回路構成図。
【図３】演算モード毎のデータの流れを示す図。
【図４】本発明のフローチャート。
【図５】光通信におけるエラー訂正復号回路の概要図。
【図６】復号回路の処理単位を示した図。
【図７】二元ＢＣＨ符号（ＢＣＨ符号）の１符号長の構成を示す図。
【図８】非二元ＢＣＨ符号（ＲＳ符号）の１符号長の構成を示す図。
【図９】ＧＦ（１６）の加算（減算）テーブルを示す図。
【図１０】ＧＦ（１６）の乗算テーブルを示す図。
【図１１】ＧＦ（１６）の逆元テーブルを示す図。
【図１２】ＩＴＵ−Ｔ勧告Ｇ．９７５．１に記載されている連接符号の復号回路の説明図。
【図１３】ＢＣＨ符号の復号回路の構成図。
【図１４】レイテンシが長いユークリッド演算ユニットのタイムチャート。
【図１５】４つの処理を４つのユニットで行う回路構成図。
【図１６】レイテンシが短いユークリッド演算ユニットのタイムチャート。
【図１７】４つの処理を１つのユニットで行う回路構成図。
【図１８】Ｒｉ（ｚ）の計算例。
【図１９】Ｂｉ（ｚ）の計算例。
【図２０】２つのステップにわけたＲｉ（ｚ）の計算例。
【図２１】２つのステップにわけたＢｉ（ｚ）の計算例。
【図２２】剰余多項式と被除数多項式の次数差が２次以上になる例。
【図２３】誤り位置多項式と誤り評価多項式の役割を示す図。
【図２４】必要なＲｉ（ｚ）の計算と不必要なＲｉ（ｚ）の計算を示した例。
【図２５】レジスタ１０とレジスタ２０の値の具体例。
【図２６】レジスタ１０と誤り位置多項式σ（ｚ）の係数の関係を示す図。
【符号の説明】
【００８８】
１０  レジスタ
２０  レジスタ
３０  演算ユニット
４０  シーケンサー
５０  シフター
６０  ゼロ挿入ユニット
７０  セレクタ
８０  セレクタ
３１０  逆元ＲＯＭ
３２０  ガロア体乗算器群
３３０  ガロア体加算器（排他的論理和器）群
３４０  ガロア体乗算器
３５０  ガロア体除算器
ａ１  送信されたデータ
ａ２  エラーが混入したデータ
ａ３  エラー訂正復号回路（デコーダ）
ａ４  エラーが訂正されたデータ
ａ１０  勧告Ｇ．９７５．１に記載されている連接符号の復号回路
ａ１１  １６個のＢＣＨ＿２の復号回路
ａ１２  インターリーバー（データの並び替え回路）
ａ１３  ８個のＢＣＨ＿１の復号回路
ａ１４  デインターリーバー（データの並び替え回路）
ａ２０  遅延回路（内部にメモリを持つ）
ａ２１  シンドローム演算ユニット
ａ２２  ユークリッド演算ユニット
ａ２３  チェーンサーチユニット
ａ２４  誤り訂正ユニット
ａ２５  ユークリッド演算ユニット用の逆元ＲＯＭ
ａ３０  レイテンシが長いユークリッド演算ユニット
ａ４０  レイテンシが短いユークリッド演算ユニット
【図１】
0004767266.tif 000017
【図２】
0004767266.tif 000018
【図３】
0004767266.tif 000019
【図４】
0004767266.tif 000020
【図５】
0004767266.tif 000021
【図６】
0004767266.tif 000022
【図７】
0004767266.tif 000023
【図８】
0004767266.tif 000024
【図９】
0004767266.tif 000025
【図１０】
0004767266.tif 000026
【図１１】
0004767266.tif 000027
【図１２】
0004767266.tif 000028
【図１３】
0004767266.tif 000029
【図１４】
0004767266.tif 000030
【図１５】
0004767266.tif 000031
【図１６】
0004767266.tif 000032
【図１７】
0004767266.tif 000033
【図１８】
0004767266.tif 000034
【図１９】
0004767266.tif 000035
【図２０】
0004767266.tif 000036
【図２１】
0004767266.tif 000037
【図２２】
0004767266.tif 000038
【図２３】
0004767266.tif 000039
【図２４】
0004767266.tif 000040
【図２５】
0004767266.tif 000041
【図２６】
0004767266.tif 000042