JPH0764810A - ガロア体演算器 - Google Patents
ガロア体演算器Info
- Publication number
- JPH0764810A JPH0764810A JP5214357A JP21435793A JPH0764810A JP H0764810 A JPH0764810 A JP H0764810A JP 5214357 A JP5214357 A JP 5214357A JP 21435793 A JP21435793 A JP 21435793A JP H0764810 A JPH0764810 A JP H0764810A
- Authority
- JP
- Japan
- Prior art keywords
- partial product
- multiplication
- galois field
- registers
- adder
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Pending
Links
Landscapes
- Detection And Correction Of Errors (AREA)
- Complex Calculations (AREA)
Abstract
(57)【要約】
【目的】乗算器及びシンドローム演算器の回路規模を縮
小する。 【構成】部分積レジスタ71乃至78の出力は係数器81及び
加算器82乃至88に与える。また、切換え器92，93，94，
96は、乗算動作時には加算器82乃至88に係数器81乃至10
8 の出力を与える。これにより、加算器88からは乗算結
果が得られる。切換え器92，93，94，96はシンドローム
演算時にはレジスタ112 ，113 ，115 ，118 の出力を与
える。また、部分積レジスタ71，74，76，77の内容を０
にする。これにより、各レジスタ112 ，113 ，115 ，11
8 にはシンドロームＳ0 乃至Ｓ4が保持される。乗算と
シンドローム演算とを共通の回路を用いて実現してお
り、回路規模を著しく縮小することができる。
小する。 【構成】部分積レジスタ71乃至78の出力は係数器81及び
加算器82乃至88に与える。また、切換え器92，93，94，
96は、乗算動作時には加算器82乃至88に係数器81乃至10
8 の出力を与える。これにより、加算器88からは乗算結
果が得られる。切換え器92，93，94，96はシンドローム
演算時にはレジスタ112 ，113 ，115 ，118 の出力を与
える。また、部分積レジスタ71，74，76，77の内容を０
にする。これにより、各レジスタ112 ，113 ，115 ，11
8 にはシンドロームＳ0 乃至Ｓ4が保持される。乗算と
シンドローム演算とを共通の回路を用いて実現してお
り、回路規模を著しく縮小することができる。
Description
【０００１】 ［発明の目的］
【産業上の利用分野】本発明は、ディジタルオーディオ
機器等のエラー訂正回路として好適のガロア体演算器に
関する。
機器等のエラー訂正回路として好適のガロア体演算器に
関する。
【０００２】
【従来の技術】近年、各種ディジタルシステムの信頼性
を向上させるために、誤り訂正符号が適用されるように
なった。誤り訂正符号としては、システムに応じて種々
のものが採用されている。特に、ガロア体上のReed sol
omon符号（以下、ＲＳ符号という）は、冗長度が低く、
ＣＤ（コンパクトディスク）、ＤＡＴ（ディジタルオー
ディオテープ）及び衛星通信の分野等において広く用い
られている重要な符号である。
を向上させるために、誤り訂正符号が適用されるように
なった。誤り訂正符号としては、システムに応じて種々
のものが採用されている。特に、ガロア体上のReed sol
omon符号（以下、ＲＳ符号という）は、冗長度が低く、
ＣＤ（コンパクトディスク）、ＤＡＴ（ディジタルオー
ディオテープ）及び衛星通信の分野等において広く用い
られている重要な符号である。
【０００３】ところで、ディジタル化された情報系列に
おいては一般に多項式表現での演算が便利である。例え
ば、ガロア体の乗算Ａ×Ｂ＝Ｃは、下記式（１）に示す
多項式表現で表わすことができる。
おいては一般に多項式表現での演算が便利である。例え
ば、ガロア体の乗算Ａ×Ｂ＝Ｃは、下記式（１）に示す
多項式表現で表わすことができる。
【０００４】 Ｃ＝（（（（（（（Ｂ・Ａ7 ）・α＋Ｂ・Ａ6 ）・α＋Ｂ・Ａ5 ）・α＋Ｂ・Ａ 4 ）・α＋Ｂ・Ａ3 ）・α＋Ｂ・Ａ2 ）・α＋Ｂ・Ａ1 ）・α＋Ｂ・Ａ0 …（１） 多項式の計算回路は、基本的には加算回路としての排他
的論理和回路及びゲート回路を用いており、レジスタに
よってＡとＢの各係数の時間合わせを行って計算を行
う。図３は上記式（１）に示す演算を実現する乗算器の
動作を説明するためのブロック図である。
的論理和回路及びゲート回路を用いており、レジスタに
よってＡとＢの各係数の時間合わせを行って計算を行
う。図３は上記式（１）に示す演算を実現する乗算器の
動作を説明するためのブロック図である。
【０００５】入力レジスタ21乃至28には夫々多項式Ａの
各係数Ａ7 乃至Ａ0 を与える。入力レジスタ21からの係
数Ａ7 と多項式Ｂとの積は係数器１に与えてαを掛けた
後、加算器12において入力レジスタ22からの係数Ａ6 と
多項式Ｂとの積の結果と加算する。この加算結果にαを
掛けて加算器13に与え、係数Ａ5 と多項式Ｂとの積と加
算する。以後同様に、多項式ＡとＢとの積と前段の加算
器出力のα倍とを加算する。加算器18からの加算結果を
多項式表現によるガロア体の乗算結果としてレジスタ８
に格納する。こうして、上記式（１）が実現される。
各係数Ａ7 乃至Ａ0 を与える。入力レジスタ21からの係
数Ａ7 と多項式Ｂとの積は係数器１に与えてαを掛けた
後、加算器12において入力レジスタ22からの係数Ａ6 と
多項式Ｂとの積の結果と加算する。この加算結果にαを
掛けて加算器13に与え、係数Ａ5 と多項式Ｂとの積と加
算する。以後同様に、多項式ＡとＢとの積と前段の加算
器出力のα倍とを加算する。加算器18からの加算結果を
多項式表現によるガロア体の乗算結果としてレジスタ８
に格納する。こうして、上記式（１）が実現される。
【０００６】ところで、誤りの位置及び値は、受信符号
多項式Ｕを生成多項式で割った剰余、即ち、シンドロー
ム多項式を求めることによって得られる。ＢＣＨ符号で
は、シンドロームは、生成多項式の根である拡大体の元
を受信符号多項式に代入することによって求めることが
でき、例えば、データ数２８でパリティ数４であるもの
とすると、下記式（２）乃至（５）によって与えられ
る。なお、Ｕi はデータのシンボルを示し、αは拡大体
の元である。
多項式Ｕを生成多項式で割った剰余、即ち、シンドロー
ム多項式を求めることによって得られる。ＢＣＨ符号で
は、シンドロームは、生成多項式の根である拡大体の元
を受信符号多項式に代入することによって求めることが
でき、例えば、データ数２８でパリティ数４であるもの
とすると、下記式（２）乃至（５）によって与えられ
る。なお、Ｕi はデータのシンボルを示し、αは拡大体
の元である。
【０００７】 図４は上記式（２）乃至（５）に示す演算を実現するシ
ンドローム演算器の動作を説明するためのブロック図で
ある。
ンドローム演算器の動作を説明するためのブロック図で
ある。
【０００８】先ず、入力データのシンボルＵ0 は入力レ
ジスタ61乃至67に入力する。入力レジスタ61，62，64，
67の出力は夫々加算器31，32，34，37に一方の入力とし
て与える。初期状態ではレジスタ41乃至44の内容は０で
あるので、加算器31，32，34，37の他方の入力は０であ
り、レジスタ41乃至44には夫々シンボルＵ0 が格納され
る。
ジスタ61乃至67に入力する。入力レジスタ61，62，64，
67の出力は夫々加算器31，32，34，37に一方の入力とし
て与える。初期状態ではレジスタ41乃至44の内容は０で
あるので、加算器31，32，34，37の他方の入力は０であ
り、レジスタ41乃至44には夫々シンボルＵ0 が格納され
る。
【０００９】次に、シンボルＵ1 を入力レジスタ61乃至
67に入力して、加算器31，32，34，37に与える。レジス
タ42の出力は係数器51を介して加算器32に与え、レジス
タ43の出力は係数器52，53を介して加算器34に与え、レ
ジスタ44の出力は係数器54乃至56を介して加算器37に与
える。従って、加算器31，32，34，37の他方の入力は夫
々Ｕ0 ，α×Ｕ0 ，α×α×Ｕ0 ，α×α×α×Ｕ0 と
なる。加算器31，32，34，37は夫々２入力を加算してレ
ジスタ41，42，43，44に格納する。この時点におけるレ
ジスタ41，42，43，44の内容は夫々下記式（６）乃至
（９）に示すものとなる。
67に入力して、加算器31，32，34，37に与える。レジス
タ42の出力は係数器51を介して加算器32に与え、レジス
タ43の出力は係数器52，53を介して加算器34に与え、レ
ジスタ44の出力は係数器54乃至56を介して加算器37に与
える。従って、加算器31，32，34，37の他方の入力は夫
々Ｕ0 ，α×Ｕ0 ，α×α×Ｕ0 ，α×α×α×Ｕ0 と
なる。加算器31，32，34，37は夫々２入力を加算してレ
ジスタ41，42，43，44に格納する。この時点におけるレ
ジスタ41，42，43，44の内容は夫々下記式（６）乃至
（９）に示すものとなる。
【００１０】 以後同様にして、順次シンボルＵ2 乃至Ｕ28を入力レジ
スタ61乃至67に入力する。レジスタ41乃至44の内容は逐
次更新され、結局レジスタ41乃至44には夫々上記式
（２）乃至（５）のシンドローム係数Ｓ0 乃至Ｓ3 が得
られる。
スタ61乃至67に入力する。レジスタ41乃至44の内容は逐
次更新され、結局レジスタ41乃至44には夫々上記式
（２）乃至（５）のシンドローム係数Ｓ0 乃至Ｓ3 が得
られる。
【００１１】ところで、ガロア体上の演算を用いたこの
種のエラー訂正回路はＬＳＩ化されている。ＬＳＩ化の
初期においては動作周波数が低いことから、高速演算を
可能にするために、回路を並列に動作させたパイプライ
ン処理が有効であった。しかし、現在はＬＳＩ製造プロ
セスの進歩から回路動作は高速化されており、むしろ微
細パターンを採用して１チップのＬＳＩ上で多くの機能
を実現可能にすることが重要となっている。スタンダー
ドセル等の手法によって回路設計を行う場合には、１ブ
ロックにできるだけ多くの機能を持たせ、そのブロック
のパターンを最適化した設計を行うことが回路面積削減
の最も有効な手段となっている。ところが、図３及び図
４の構成は回路規模が大きく、ガロア体の乗算器及びシ
ンドローム演算器を搭載したエラー訂正回路のＬＳＩ化
に不利であるという欠点があった。
種のエラー訂正回路はＬＳＩ化されている。ＬＳＩ化の
初期においては動作周波数が低いことから、高速演算を
可能にするために、回路を並列に動作させたパイプライ
ン処理が有効であった。しかし、現在はＬＳＩ製造プロ
セスの進歩から回路動作は高速化されており、むしろ微
細パターンを採用して１チップのＬＳＩ上で多くの機能
を実現可能にすることが重要となっている。スタンダー
ドセル等の手法によって回路設計を行う場合には、１ブ
ロックにできるだけ多くの機能を持たせ、そのブロック
のパターンを最適化した設計を行うことが回路面積削減
の最も有効な手段となっている。ところが、図３及び図
４の構成は回路規模が大きく、ガロア体の乗算器及びシ
ンドローム演算器を搭載したエラー訂正回路のＬＳＩ化
に不利であるという欠点があった。
【００１２】
【発明が解決しようとする課題】このように、上述した
従来のガロア体演算器においては、回路規模が大きくＬ
ＳＩ化した場合に基板面積占有率が高くＬＳＩ化に不利
であるという問題点があった。
従来のガロア体演算器においては、回路規模が大きくＬ
ＳＩ化した場合に基板面積占有率が高くＬＳＩ化に不利
であるという問題点があった。
【００１３】本発明は、ガロア体の乗算器とシンドロー
ム演算器との回路ブロックを共用化することにより、Ｌ
ＳＩ上の回路面積を削減することができるガロア体演算
器を提供することを目的とする。
ム演算器との回路ブロックを共用化することにより、Ｌ
ＳＩ上の回路面積を削減することができるガロア体演算
器を提供することを目的とする。
【００１４】 ［発明の構成］
【課題を解決するための手段】本発明に係るガロア体演
算器は、ガロア体の拡大体の元αを乗算する複数のα倍
手段と、被乗数データのビット幅に対応する数のガロア
体の加算手段と、乗数データと被乗数データの各ビット
との積である部分積を保持する複数の部分積保持手段
と、前記部分積保持手段に格納されている前記被乗数デ
ータの所定ビットに対応する部分積を前記α倍手段に与
えて前記拡大体の元αを乗算し、乗算結果を前記加算手
段に与えて次のビットに対応する部分積と加算すること
によりガロア体の乗算を行わせる乗算制御手段と、前記
複数の部分積保持手段のうちの所定の複数の部分積保持
手段の内容を０にすることにより、前記乗算制御手段に
よってガロア体の拡大体の元αのｎ乗を乗算するべき乗
手段と、前記部分積保持手段のうちの所定の複数の部分
積保持手段にデータのシンボルを与えると共に前記乗算
制御手段を制御して前記α倍手段の出力に代えて前記べ
き乗手段の出力を前記加算手段に与えることにより、前
記加算手段からシンドロームを得る切換手段とを具備し
たものである。
算器は、ガロア体の拡大体の元αを乗算する複数のα倍
手段と、被乗数データのビット幅に対応する数のガロア
体の加算手段と、乗数データと被乗数データの各ビット
との積である部分積を保持する複数の部分積保持手段
と、前記部分積保持手段に格納されている前記被乗数デ
ータの所定ビットに対応する部分積を前記α倍手段に与
えて前記拡大体の元αを乗算し、乗算結果を前記加算手
段に与えて次のビットに対応する部分積と加算すること
によりガロア体の乗算を行わせる乗算制御手段と、前記
複数の部分積保持手段のうちの所定の複数の部分積保持
手段の内容を０にすることにより、前記乗算制御手段に
よってガロア体の拡大体の元αのｎ乗を乗算するべき乗
手段と、前記部分積保持手段のうちの所定の複数の部分
積保持手段にデータのシンボルを与えると共に前記乗算
制御手段を制御して前記α倍手段の出力に代えて前記べ
き乗手段の出力を前記加算手段に与えることにより、前
記加算手段からシンドロームを得る切換手段とを具備し
たものである。
【００１５】
【作用】本発明において、乗算制御手段は、部分積保持
手段、α倍手段及び加算手段を用いてガロア体の乗算を
行う。べき乗手段は複数の部分積保持手段の内容を０に
することにより、α倍手段の出力をそのままα倍手段に
入力させることよりαのｎ乗の乗算を可能にする。切換
手段はべき乗手段の出力を加算手段に与えることによ
り、加算手段からシンドロームを得る。即ち、べき乗手
段及び切換手段によって部分積保持手段、α倍手段及び
加算手段を共用化して、乗算とシンドローム演算とを行
っており、乗算及びシンドローム演算機能を有する回路
の規模を低減する。
手段、α倍手段及び加算手段を用いてガロア体の乗算を
行う。べき乗手段は複数の部分積保持手段の内容を０に
することにより、α倍手段の出力をそのままα倍手段に
入力させることよりαのｎ乗の乗算を可能にする。切換
手段はべき乗手段の出力を加算手段に与えることによ
り、加算手段からシンドロームを得る。即ち、べき乗手
段及び切換手段によって部分積保持手段、α倍手段及び
加算手段を共用化して、乗算とシンドローム演算とを行
っており、乗算及びシンドローム演算機能を有する回路
の規模を低減する。
【００１６】
【実施例】以下、図面を参照して本発明の実施例につい
て説明する。図１は本発明に係るガロア体演算器の一実
施例を示すブロック図である。
て説明する。図１は本発明に係るガロア体演算器の一実
施例を示すブロック図である。
【００１７】最上位乃至最下位の部分積レジスタ71乃至
78には夫々被乗数である多項式Ａ又は受信符号多項式Ｕ
i を入力する。即ち、ガロア体の乗算器として用いる場
合には、部分積レジスタ71乃至78には夫々多項式Ａの各
係数Ａ1 乃至Ａ8 と乗数である多項式Ｂとの積が格納さ
れる。また、シンドローム演算器として用いる場合に
は、乗数Ｂとして受信符号多項式Ｕi を順次入力する。
なお、この場合には、被乗数Ａは“６９”Ｈｅｘ（０１
１０１００１）に固定して、部分積レジスタ71，74，7
6，77の内容を０にするようになっている。
78には夫々被乗数である多項式Ａ又は受信符号多項式Ｕ
i を入力する。即ち、ガロア体の乗算器として用いる場
合には、部分積レジスタ71乃至78には夫々多項式Ａの各
係数Ａ1 乃至Ａ8 と乗数である多項式Ｂとの積が格納さ
れる。また、シンドローム演算器として用いる場合に
は、乗数Ｂとして受信符号多項式Ｕi を順次入力する。
なお、この場合には、被乗数Ａは“６９”Ｈｅｘ（０１
１０１００１）に固定して、部分積レジスタ71，74，7
6，77の内容を０にするようになっている。
【００１８】部分積レジスタ71乃至78の出力は夫々係数
器81及び加算器82乃至88に与える。加算器82乃至88は２
入力を加算して出力する。係数器81は部分積レジスタ71
の出力をα倍して切換え器92の入力端ａを介して加算器
82に与える。加算器82，83，85，88の出力は夫々レジス
タ112 ，113 ，115 ，118 に与え、レジスタ112 ，113
，115 ，118 の出力は夫々切換え器92，93，94，96の
入力端ｂに与える。切換え器93，94，96の入力端ａには
加算器82，83，85の出力を与える。切換え器92，93，9
4，96は切換え信号によって制御され、乗算動作を行う
場合には入力端ａを選択し、シンドローム演算を行う場
合には入力端ｂを選択して、選択した入力端からの信号
を夫々加算器82，係数器103 ，104 ，106 に与える。
器81及び加算器82乃至88に与える。加算器82乃至88は２
入力を加算して出力する。係数器81は部分積レジスタ71
の出力をα倍して切換え器92の入力端ａを介して加算器
82に与える。加算器82，83，85，88の出力は夫々レジス
タ112 ，113 ，115 ，118 に与え、レジスタ112 ，113
，115 ，118 の出力は夫々切換え器92，93，94，96の
入力端ｂに与える。切換え器93，94，96の入力端ａには
加算器82，83，85の出力を与える。切換え器92，93，9
4，96は切換え信号によって制御され、乗算動作を行う
場合には入力端ａを選択し、シンドローム演算を行う場
合には入力端ｂを選択して、選択した入力端からの信号
を夫々加算器82，係数器103 ，104 ，106 に与える。
【００１９】係数器103 ，104 ，106 は入力された信号
をα倍して夫々加算器83，84，86に与える。加算器84，
86は夫々出力を係数器105 ，107 に出力する。係数器10
5 ，107 は入力された信号をα倍して夫々加算器85，87
に出力し、加算器87は出力を係数器108 に与える。係数
器108 は入力された信号をα倍して加算器88に与えるよ
うになっている。なお、レジスタ112 ，113 ，115 ，11
8 はクリア信号によってクリアされるようになってい
る。また、シンドローム演算時には、最上位の部分積レ
ジスタ71の内容は０又は不定であり使用しない。
をα倍して夫々加算器83，84，86に与える。加算器84，
86は夫々出力を係数器105 ，107 に出力する。係数器10
5 ，107 は入力された信号をα倍して夫々加算器85，87
に出力し、加算器87は出力を係数器108 に与える。係数
器108 は入力された信号をα倍して加算器88に与えるよ
うになっている。なお、レジスタ112 ，113 ，115 ，11
8 はクリア信号によってクリアされるようになってい
る。また、シンドローム演算時には、最上位の部分積レ
ジスタ71の内容は０又は不定であり使用しない。
【００２０】次に、このように構成された実施例の動作
について図２を参照して説明する。図２はシンドローム
演算動作時の等価回路を示すブロック図である。
について図２を参照して説明する。図２はシンドローム
演算動作時の等価回路を示すブロック図である。
【００２１】先ず、ガロア体の乗算器として動作させる
ものとする。この場合には、切換え器92，93，94，96は
入力端ａを選択する。被乗数の係数Ａ7 乃至Ａ0 は夫々
部分積レジスタ71乃至78に与え、部分積レジスタ71乃至
78には夫々部分積であるＡ7・Ｂ，Ａ6 ・Ｂ，Ａ5 ・
Ｂ，Ａ4 ・Ｂ，Ａ3 ・Ｂ，Ａ2 ・Ｂ，Ａ1 ・Ｂ，Ａ0 ・
Ｂが格納される。最上位の部分積Ａ7 ・Ｂは係数器81に
与えてα倍し、切換え器92を介して加算器82に与える。
加算器82は部分積レジスタ72からの部分積Ａ6 ・Ｂと係
数器81の出力とを加算して切換え器93に出力する。
ものとする。この場合には、切換え器92，93，94，96は
入力端ａを選択する。被乗数の係数Ａ7 乃至Ａ0 は夫々
部分積レジスタ71乃至78に与え、部分積レジスタ71乃至
78には夫々部分積であるＡ7・Ｂ，Ａ6 ・Ｂ，Ａ5 ・
Ｂ，Ａ4 ・Ｂ，Ａ3 ・Ｂ，Ａ2 ・Ｂ，Ａ1 ・Ｂ，Ａ0 ・
Ｂが格納される。最上位の部分積Ａ7 ・Ｂは係数器81に
与えてα倍し、切換え器92を介して加算器82に与える。
加算器82は部分積レジスタ72からの部分積Ａ6 ・Ｂと係
数器81の出力とを加算して切換え器93に出力する。
【００２２】切換え器92，93，94，96は入力端ａを選択
しているので、加算器82乃至87の出力は夫々係数器103
乃至108 を介して加算器83乃至88に与えられることにな
る。加算器82の出力（（Ｂ・Ａ7 ）・α＋Ｂ・Ａ6 ）は
係数器103 によってα倍して加算器83に与える。以後同
様に、加算器83乃至87の出力をα倍して次の加算器84乃
至88に与える。結局、この場合には、図３と等価の回路
が構成されて、レジスタ118 に上記式（１）の乗算結果
が格納される。
しているので、加算器82乃至87の出力は夫々係数器103
乃至108 を介して加算器83乃至88に与えられることにな
る。加算器82の出力（（Ｂ・Ａ7 ）・α＋Ｂ・Ａ6 ）は
係数器103 によってα倍して加算器83に与える。以後同
様に、加算器83乃至87の出力をα倍して次の加算器84乃
至88に与える。結局、この場合には、図３と等価の回路
が構成されて、レジスタ118 に上記式（１）の乗算結果
が格納される。
【００２３】次に、シンドローム演算器として動作させ
るものとする。この場合には、部分積レジスタ71乃至78
には乗数Ｂとして受信符号多項式Ｕi を順次入力する。
また、被乗数Ａとして各レジスタ71乃至78に夫々０１１
０１００１（＝“６９”）を与える。従って、部分積レ
ジスタ71，74，76，77に保持される部分積は０となり、
シンボルは部分積レジスタ72，73，75，78のみから出力
されることになる。また、シンドローム演算開始時には
クリア信号によってレジスタ112 ，113 ，115，118 を
クリアする。
るものとする。この場合には、部分積レジスタ71乃至78
には乗数Ｂとして受信符号多項式Ｕi を順次入力する。
また、被乗数Ａとして各レジスタ71乃至78に夫々０１１
０１００１（＝“６９”）を与える。従って、部分積レ
ジスタ71，74，76，77に保持される部分積は０となり、
シンボルは部分積レジスタ72，73，75，78のみから出力
されることになる。また、シンドローム演算開始時には
クリア信号によってレジスタ112 ，113 ，115，118 を
クリアする。
【００２４】シンドローム演算が指示されると、切換え
器92，93，94，96は入力端ｂを選択して、レジスタ112
，113 ，115 ，118 の出力を夫々加算器82及び係数器1
03 ，104 ，106 に与える。係数器103 ，104 ，106 は
レジスタ113 ，115 ，118 の出力をα倍して加算器83，
84，86に与える。加算器84，86，87は部分積レジスタ7
4，76，77の内容が０であるので、係数器104 ，106 ，1
07 の出力をそのまま係数器105 ，107 ，108 に出力す
る。更に、係数器105 ，107 ，108 は入力された信号α
倍して加算器85，87，88に出力する。
器92，93，94，96は入力端ｂを選択して、レジスタ112
，113 ，115 ，118 の出力を夫々加算器82及び係数器1
03 ，104 ，106 に与える。係数器103 ，104 ，106 は
レジスタ113 ，115 ，118 の出力をα倍して加算器83，
84，86に与える。加算器84，86，87は部分積レジスタ7
4，76，77の内容が０であるので、係数器104 ，106 ，1
07 の出力をそのまま係数器105 ，107 ，108 に出力す
る。更に、係数器105 ，107 ，108 は入力された信号α
倍して加算器85，87，88に出力する。
【００２５】即ち、部分積レジスタ71，74，76，77の出
力を０にすると共に、切換え器92，93，94，96が入力端
ｂを選択することにより、レジスタ112 の出力はそのま
ま加算器82に与えられ、レジスタ113 の出力はα倍され
て加算器83に与えられ、レジスタ115 の出力はαの２乗
倍されて加算器85に与えられ、レジスタ118 の出力はα
の３乗倍されて加算器88に与えられることになる。従っ
て、この場合には、図２に示す等価回路が構成される。
力を０にすると共に、切換え器92，93，94，96が入力端
ｂを選択することにより、レジスタ112 の出力はそのま
ま加算器82に与えられ、レジスタ113 の出力はα倍され
て加算器83に与えられ、レジスタ115 の出力はαの２乗
倍されて加算器85に与えられ、レジスタ118 の出力はα
の３乗倍されて加算器88に与えられることになる。従っ
て、この場合には、図２に示す等価回路が構成される。
【００２６】演算開始時にはレジスタ112 ，113 ，115
，118 の内容はクリアされているので、切換え器92，
係数器103 ，105 ，108 からは０が加算器82，83，85，
88に与えられる。部分積レジスタ72，73，75，78に入力
されたシンボルＵ0 は、夫々加算器82，83，85，88を介
してそのままレジスタ112 ，113 ，115 ，118 に与える
ことになる。次に、シンボルＵ1 を部分積レジスタ72，
73，75，78に入力する。レジスタ112 ，113 ，115 ，11
8 の出力は、図２に示すように、夫々１倍，α倍，αの
２乗倍，αの３乗倍して加算器82，83，85，88に与えて
おり、加算器82，83，85，88は夫々レジスタ112 の出力
及び係数器103 ，105 ，108 の出力と部分積レジスタ7
2，73，75，78からのシンボルＵi とを加算して出力す
る。
，118 の内容はクリアされているので、切換え器92，
係数器103 ，105 ，108 からは０が加算器82，83，85，
88に与えられる。部分積レジスタ72，73，75，78に入力
されたシンボルＵ0 は、夫々加算器82，83，85，88を介
してそのままレジスタ112 ，113 ，115 ，118 に与える
ことになる。次に、シンボルＵ1 を部分積レジスタ72，
73，75，78に入力する。レジスタ112 ，113 ，115 ，11
8 の出力は、図２に示すように、夫々１倍，α倍，αの
２乗倍，αの３乗倍して加算器82，83，85，88に与えて
おり、加算器82，83，85，88は夫々レジスタ112 の出力
及び係数器103 ，105 ，108 の出力と部分積レジスタ7
2，73，75，78からのシンボルＵi とを加算して出力す
る。
【００２７】即ち、部分積レジスタ72の出力は、加算器
82、レジスタ112 及び切換え器92を介して加算器82に与
えることにより累積加算する。シンボルＵ0 乃至Ｕ27を
順次入力することにより、レジスタ112 には上記式
（２）に示すシンドロームＳ0 が得られる。
82、レジスタ112 及び切換え器92を介して加算器82に与
えることにより累積加算する。シンボルＵ0 乃至Ｕ27を
順次入力することにより、レジスタ112 には上記式
（２）に示すシンドロームＳ0 が得られる。
【００２８】また、部分積レジスタ72の出力は、加算器
83，レジスタ113 、切換え器93及び係数器103 を介して
加算器83に与えることにより、α倍しながら累積加算す
る。従って、シンボルＵ0 乃至Ｕ27を順次入力すること
により、レジスタ113 には上記式（３）に示すシンドロ
ームＳ1 が格納される。
83，レジスタ113 、切換え器93及び係数器103 を介して
加算器83に与えることにより、α倍しながら累積加算す
る。従って、シンボルＵ0 乃至Ｕ27を順次入力すること
により、レジスタ113 には上記式（３）に示すシンドロ
ームＳ1 が格納される。
【００２９】また、部分積レジスタ75の出力は、加算器
85，レジスタ115 、切換え器94、係数器104 、加算器84
及び係数器105 を介して加算器85に与えることにより、
αの２乗倍しながら累積加算する。従って、シンボルＵ
0 乃至Ｕ27を順次入力することにより、レジスタ115 に
は上記式（４）に示すシンドロームＳ2 が格納される。
85，レジスタ115 、切換え器94、係数器104 、加算器84
及び係数器105 を介して加算器85に与えることにより、
αの２乗倍しながら累積加算する。従って、シンボルＵ
0 乃至Ｕ27を順次入力することにより、レジスタ115 に
は上記式（４）に示すシンドロームＳ2 が格納される。
【００３０】同様に、部分積レジスタ78の出力は、加算
器88，レジスタ118 、切換え器96、係数器106 、加算器
86、係数器107 、加算器87及び係数器108 を介して加算
器88に与えることにより、αの３乗倍しながら累積加算
する。従って、シンボルＵ0乃至Ｕ27を順次入力するこ
とにより、レジスタ118 には上記式（５）に示すシンド
ロームＳ3 が格納される。
器88，レジスタ118 、切換え器96、係数器106 、加算器
86、係数器107 、加算器87及び係数器108 を介して加算
器88に与えることにより、αの３乗倍しながら累積加算
する。従って、シンボルＵ0乃至Ｕ27を順次入力するこ
とにより、レジスタ118 には上記式（５）に示すシンド
ロームＳ3 が格納される。
【００３１】このように、本実施例においては、切換え
器92，93，94，96を乗算動作時とシンドローム演算時と
で切換えることにより、回路を共用化してガロア体の乗
算とシンドローム演算とを行っている。回路を共用化し
ているので、ガロア体の乗算器とシンドローム演算器と
を別々に構成する場合よりも、回路規模を縮小すること
ができ、ＬＳＩ化する場合において、基板占有面積を削
減することができる。これにより、略乗算器の構成に必
要な面積を占有するのみで、ガロア体の乗算器とシンド
ローム演算器とを構成することができる。
器92，93，94，96を乗算動作時とシンドローム演算時と
で切換えることにより、回路を共用化してガロア体の乗
算とシンドローム演算とを行っている。回路を共用化し
ているので、ガロア体の乗算器とシンドローム演算器と
を別々に構成する場合よりも、回路規模を縮小すること
ができ、ＬＳＩ化する場合において、基板占有面積を削
減することができる。これにより、略乗算器の構成に必
要な面積を占有するのみで、ガロア体の乗算器とシンド
ローム演算器とを構成することができる。
【００３２】なお、本実施例においては、シンドローム
演算時は、切換え器92，93，94，96の出力はαの０乗
倍，α倍，αの２乗倍，αの３乗倍するようにに固定さ
れているが、任意の倍数αのｎ乗を乗算する係数器を用
いて、外部信号によってｎの値を切換えるようにするこ
ともできる。そうすると、パリティ数の増加及びエラー
ロケーション演算に容易に対応することができるという
利点がある。
演算時は、切換え器92，93，94，96の出力はαの０乗
倍，α倍，αの２乗倍，αの３乗倍するようにに固定さ
れているが、任意の倍数αのｎ乗を乗算する係数器を用
いて、外部信号によってｎの値を切換えるようにするこ
ともできる。そうすると、パリティ数の増加及びエラー
ロケーション演算に容易に対応することができるという
利点がある。
【００３３】
【発明の効果】以上説明したように本発明によれば、ガ
ロア体の乗算器とシンドローム演算器との回路ブロック
を共用化することにより、ＬＳＩ上の回路面積を削減す
ることができるという効果を有する。
ロア体の乗算器とシンドローム演算器との回路ブロック
を共用化することにより、ＬＳＩ上の回路面積を削減す
ることができるという効果を有する。
【図１】本発明に係るガロア体演算器の一実施例を示す
ブロック図。
ブロック図。
【図２】実施例を説明するための説明図。
【図３】ガロア体の乗算器の動作を説明するためのブロ
ック図。
ック図。
【図４】シンドローム演算動作を説明するためのブロッ
ク図。
ク図。
71〜78…部分積レジスタ、81，103 〜108 …係数器、82
〜88…加算器、92〜96…切換え器、112 〜118 …レジス
タ
〜88…加算器、92〜96…切換え器、112 〜118 …レジス
タ
Claims (2)
- 【請求項１】 ガロア体の拡大体の元αを乗算する複数
のα倍手段と、 被乗数データのビット幅に対応する数のガロア体の加算
手段と、 乗数データと被乗数データの各ビットとの積である部分
積を保持する複数の部分積保持手段と、 前記部分積保持手段に格納されている前記被乗数データ
の所定ビットに対応する部分積を前記α倍手段に与えて
前記拡大体の元αを乗算し、乗算結果を前記加算手段に
与えて次のビットに対応する部分積と加算することによ
りガロア体の乗算を行わせる乗算制御手段と、 前記複数の部分積保持手段のうちの所定の複数の部分積
保持手段の内容を０にすることにより、前記乗算制御手
段によってガロア体の拡大体の元αのｎ乗を乗算するべ
き乗手段と、 前記部分積保持手段のうちの所定の複数の部分積保持手
段にデータのシンボルを与えると共に前記乗算制御手段
を制御して前記α倍手段の出力に代えて前記べき乗手段
の出力を前記加算手段に与えることにより、前記加算手
段からシンドロームを得る切換手段とを具備したことを
特徴とするガロア体演算器。 - 【請求項２】 前記べき乗手段のｎを外部信号によって
制御するべき乗制御手段を付加したことを特徴とする請
求項１に記載のガロア体演算器。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP5214357A JPH0764810A (ja) | 1993-08-30 | 1993-08-30 | ガロア体演算器 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP5214357A JPH0764810A (ja) | 1993-08-30 | 1993-08-30 | ガロア体演算器 |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| JPH0764810A true JPH0764810A (ja) | 1995-03-10 |
Family
ID=16654447
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP5214357A Pending JPH0764810A (ja) | 1993-08-30 | 1993-08-30 | ガロア体演算器 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JPH0764810A (ja) |
Cited By (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP2001056640A (ja) * | 1999-08-19 | 2001-02-27 | Toyo Commun Equip Co Ltd | 積和演算装置及びこれを用いた暗号・復号装置 |
| JP2001109376A (ja) * | 1999-10-04 | 2001-04-20 | Toyo Commun Equip Co Ltd | 演算回路および演算プロセッサ |
| JP2007129618A (ja) * | 2005-11-07 | 2007-05-24 | Renesas Technology Corp | ガロア体のα乗算回路および演算回路 |
-
1993
- 1993-08-30 JP JP5214357A patent/JPH0764810A/ja active Pending
Cited By (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP2001056640A (ja) * | 1999-08-19 | 2001-02-27 | Toyo Commun Equip Co Ltd | 積和演算装置及びこれを用いた暗号・復号装置 |
| JP2001109376A (ja) * | 1999-10-04 | 2001-04-20 | Toyo Commun Equip Co Ltd | 演算回路および演算プロセッサ |
| JP2007129618A (ja) * | 2005-11-07 | 2007-05-24 | Renesas Technology Corp | ガロア体のα乗算回路および演算回路 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US4649541A (en) | Reed-Solomon decoder | |
| US6119262A (en) | Method and apparatus for solving key equation polynomials in decoding error correction codes | |
| US5442578A (en) | Calculating circuit for error correction | |
| US5805617A (en) | Apparatus for computing error correction syndromes | |
| EP0621698B1 (en) | Error correction method including erasure correction, and apparatus therefore | |
| US7089276B2 (en) | Modular Galois-field subfield-power integrated inverter-multiplier circuit for Galois-field division over GF(256) | |
| EP0836285B1 (en) | Reed-Solomon decoder with general-purpose processing unit and dedicated circuits | |
| US5537426A (en) | Operation apparatus for deriving erasure position Γ(x) and Forney syndrome T(x) polynomials of a Galois field employing a single multiplier | |
| KR100258951B1 (ko) | 리드-솔로몬(rs) 복호기와 그 복호방법 | |
| US6341297B1 (en) | Parallel processing syndrome calculating circuit and Reed-Solomon decoding circuit | |
| JPH0764810A (ja) | ガロア体演算器 | |
| EP1175015B1 (en) | Decoding circuit and decoding method thereof | |
| KR100336234B1 (ko) | 데이터 오류 정정 장치 | |
| JP3614978B2 (ja) | ガロア体の除算方法および除算装置 | |
| JPH0476540B2 (ja) | ||
| JPH0750595A (ja) | 復号化装置 | |
| EP1037148B1 (en) | Error coding method | |
| JP2907138B2 (ja) | 誤り訂正の演算処理方法及び処理回路 | |
| KR940011659B1 (ko) | 유클리드 알고리즘 연산장치 | |
| JP2603244B2 (ja) | 誤り訂正装置 | |
| JP2603243B2 (ja) | 誤り訂正装置 | |
| JP3131969B2 (ja) | 演算装置 | |
| JPH08139612A (ja) | リード・ソロモン誤り訂正符号復号化回路 | |
| KR0167390B1 (ko) | 복호화 장치 | |
| JP2943255B2 (ja) | 逆数算出回路 |