JPH0834440B2 - ガロア体演算方法 - Google Patents
ガロア体演算方法Info
- Publication number
- JPH0834440B2 JPH0834440B2 JP62151863A JP15186387A JPH0834440B2 JP H0834440 B2 JPH0834440 B2 JP H0834440B2 JP 62151863 A JP62151863 A JP 62151863A JP 15186387 A JP15186387 A JP 15186387A JP H0834440 B2 JPH0834440 B2 JP H0834440B2
- Authority
- JP
- Japan
- Prior art keywords
- group
- symbol
- fixed
- error
- multiplier
- 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.)
- Expired - Fee Related
Links
Landscapes
- Detection And Correction Of Errors (AREA)
- Error Detection And Correction (AREA)
Description
【発明の詳細な説明】 産業上の利用分野 本発明は光ディスク等の媒体にデータを記録再生する
場合に使用する符号誤り検査訂正装置に使用するガロア
体演算装置に関するものである。
場合に使用する符号誤り検査訂正装置に使用するガロア
体演算装置に関するものである。
従来の技術 近年光ディスクを用いたデータ記録再生装置の開発が
盛んである。光ディスクメモリは磁気ディスクに比べ大
容量のデータが記録可能である反面、記録媒体の生のエ
ラー率が高いという欠点を持つ。このため記録時にはデ
ータに誤り検査訂正符号を付加して光ディスクにはデー
タと誤り検査訂正符号の両方を記録し、再生時には前記
誤り検査訂正符号を用いてデータの誤りを検査訂正する
方法が一般に用いられる。この様名誤り検査訂正符号と
して近年注目されているものに最小距離ｄ＝17程度のリ
ードソロモン符号がある。通常リードソロモン符号の復
号は、まず受信語よりシンドロームを計算し、次にシン
ドロームから誤り個数と誤り位置多項式σ（ｘ）および
誤り量多項式ω（ｘ）を求め、最後に各多項式より誤り
位置と誤り量を推定して訂正を実行するのであるが、最
小距離が大きいため復号過程が複雑で復号に長時間かか
りまたハードウエアで実現するためには大きな回路が必
要である。このうちシンドロームの計算は復号速度に非
常に影響するため並列演算ハードウエアが使われる場合
が多いが、特に高速性が要求される場合には他の訂正処
理も純粋なハードウエアでなくマイクロプログラミング
手法によってハードウエアに近い速度で処理を行う場合
がある。このとき、誤り位置多項式と誤り量多項式の導
出計算にはユークリッドの互除法等の高速解法アルゴリ
ズムが知られており、誤り位置多項式から誤り位置を求
めるにはChienのアルゴリズムが用いられる。また誤り
量は誤り位置多項式をガロア体上で形式微分した多項式
と誤り量多項式の計算により求められる。このうちChie
nのアルゴリズムと誤り位置多項式を微分した多項式の
計算と誤り量多項式の計算は、大部分が多項式にる変数
を代入してその多項式の値を求める計算である。多項式
の値をある程度高速に求める方法として一般化したHorn
erの方法と呼ばれる繰り返し積和計算に帰着させる方法
が従来用いられてきた。（例えば電子通信学会技術報告
IT84−43、シストリックアルゴリズムに基ずくRerd−So
lomon符号の復号器の構成法、木村他、page5） 以下図面を参照しながら、従来のガロア体演算方法に
ついて説明する。第３図、第４図は従来の訂正処理で用
いられているガロア体演算回路の一部を示すものであ
る。第３図において11は０元判定回路、12、13、34は入
力パイプラインレジスタ、28はメモリー、29はガロア体
乗算回路、30はガロア体加算回路（排他的論理和演算回
路）、31、32はスイッチ論理ゲート回路、33は原始元α
の累乗発生回路（位置数発生回路）である。この演算は
GF（28）上で行なわれる。
盛んである。光ディスクメモリは磁気ディスクに比べ大
容量のデータが記録可能である反面、記録媒体の生のエ
ラー率が高いという欠点を持つ。このため記録時にはデ
ータに誤り検査訂正符号を付加して光ディスクにはデー
タと誤り検査訂正符号の両方を記録し、再生時には前記
誤り検査訂正符号を用いてデータの誤りを検査訂正する
方法が一般に用いられる。この様名誤り検査訂正符号と
して近年注目されているものに最小距離ｄ＝17程度のリ
ードソロモン符号がある。通常リードソロモン符号の復
号は、まず受信語よりシンドロームを計算し、次にシン
ドロームから誤り個数と誤り位置多項式σ（ｘ）および
誤り量多項式ω（ｘ）を求め、最後に各多項式より誤り
位置と誤り量を推定して訂正を実行するのであるが、最
小距離が大きいため復号過程が複雑で復号に長時間かか
りまたハードウエアで実現するためには大きな回路が必
要である。このうちシンドロームの計算は復号速度に非
常に影響するため並列演算ハードウエアが使われる場合
が多いが、特に高速性が要求される場合には他の訂正処
理も純粋なハードウエアでなくマイクロプログラミング
手法によってハードウエアに近い速度で処理を行う場合
がある。このとき、誤り位置多項式と誤り量多項式の導
出計算にはユークリッドの互除法等の高速解法アルゴリ
ズムが知られており、誤り位置多項式から誤り位置を求
めるにはChienのアルゴリズムが用いられる。また誤り
量は誤り位置多項式をガロア体上で形式微分した多項式
と誤り量多項式の計算により求められる。このうちChie
nのアルゴリズムと誤り位置多項式を微分した多項式の
計算と誤り量多項式の計算は、大部分が多項式にる変数
を代入してその多項式の値を求める計算である。多項式
の値をある程度高速に求める方法として一般化したHorn
erの方法と呼ばれる繰り返し積和計算に帰着させる方法
が従来用いられてきた。（例えば電子通信学会技術報告
IT84−43、シストリックアルゴリズムに基ずくRerd−So
lomon符号の復号器の構成法、木村他、page5） 以下図面を参照しながら、従来のガロア体演算方法に
ついて説明する。第３図、第４図は従来の訂正処理で用
いられているガロア体演算回路の一部を示すものであ
る。第３図において11は０元判定回路、12、13、34は入
力パイプラインレジスタ、28はメモリー、29はガロア体
乗算回路、30はガロア体加算回路（排他的論理和演算回
路）、31、32はスイッチ論理ゲート回路、33は原始元α
の累乗発生回路（位置数発生回路）である。この演算は
GF（28）上で行なわれる。
以下に従来のガロア体演算装置による多項式の計算に
ついて以下その動作を説明する。まず光ディスクより読
み出された受信語は、デインターリーブ後シンドローム
計算回路に入力される。得られたシンドロームが全て０
でない場合には誤りがあったと判定され、このシンドロ
ームをガロア体演算装置に送出し、誤り個数の計算およ
び誤り位置、誤り量の推定を行うのである。28のメモリ
ーには符号の最小距離をｄとしたとき（ｄ−１）個のシ
ンドロームがシンドローム演算回路から送られ、29の乗
算器および30の加算器、あるいは図には記していないが
マイクロプログラムによる制御論理回路、逆元メモリー
等によって誤りの個数ｔおよび（ｔ＋１）個の誤り位置
多項式の各次数の係数（０次を含む）が算出格納され
る。いま、誤り位置多項式の根αＮがすでに求まってい
て、同じガロア体演算回路を用いて誤り位置多項式を微
分した多項式にαＮを代入した値を求める動作を説明す
る。今簡略化のため３個の誤りがあったとすると誤り位
置多項式は k3X3＋k2X2＋k1Ｘ＋k0であり、この誤り位置多項式を微
分した多項式はk3X2＋k1である。したがって31のスイッ
チ論理ゲート回路を33のαのガロア体加算回路側に、32
のスイッチ論理ゲート回路を28のメモリー側に倒し14の
Rcにはk3、０、k1、と係数を、12のRaにはαＮを代入す
る。13のRbの内容は計算実行に先立ち０にクリアされて
いるものとする。この時の30の加算器の出力はパイプラ
イン後αＮ＊０＋k3、αＮ＊k3＋０、αＮ＊（αＮ＊
k3）＋k1となり、３ステップめで誤り位置多項式を微分
した多項式に誤り位置を代入計算した値が計算される。
なお上式は全てガロア体上の演算であり、演算子＋は加
算、＊は乗算をしめす。一般に計算に必要なステップ数
は初期設定を除いて多項式の次数とおなじだけ必要であ
る。また０元判定回路11、αの累乗発生回路33は誤り位
置の計算において誤り位置多項式に誤り位置数を代入し
て根であるか否かを判定するのに用いる。この計算は、
前述の多項式の計算方法と同一手順で行い得るので省略
する。第４図は29の乗算回路の内部を示したものであ
る。第４図において１、２、３、４、５、６、７、８は
ガロア体の固定係数乗算器、９は12のパイプラインレジ
スタの各ビットが０のとき対応して各固定係数乗算器出
力に直列に０元を乗算する論理積回路であり各固定係数
乗算器出力に対して各ビット毎にそれぞれ設けられてい
る。また10はパリディジェネレータ回路であり乗算結果
の全シンボルについて各ビットごとの排他的論理和を出
力する。
ついて以下その動作を説明する。まず光ディスクより読
み出された受信語は、デインターリーブ後シンドローム
計算回路に入力される。得られたシンドロームが全て０
でない場合には誤りがあったと判定され、このシンドロ
ームをガロア体演算装置に送出し、誤り個数の計算およ
び誤り位置、誤り量の推定を行うのである。28のメモリ
ーには符号の最小距離をｄとしたとき（ｄ−１）個のシ
ンドロームがシンドローム演算回路から送られ、29の乗
算器および30の加算器、あるいは図には記していないが
マイクロプログラムによる制御論理回路、逆元メモリー
等によって誤りの個数ｔおよび（ｔ＋１）個の誤り位置
多項式の各次数の係数（０次を含む）が算出格納され
る。いま、誤り位置多項式の根αＮがすでに求まってい
て、同じガロア体演算回路を用いて誤り位置多項式を微
分した多項式にαＮを代入した値を求める動作を説明す
る。今簡略化のため３個の誤りがあったとすると誤り位
置多項式は k3X3＋k2X2＋k1Ｘ＋k0であり、この誤り位置多項式を微
分した多項式はk3X2＋k1である。したがって31のスイッ
チ論理ゲート回路を33のαのガロア体加算回路側に、32
のスイッチ論理ゲート回路を28のメモリー側に倒し14の
Rcにはk3、０、k1、と係数を、12のRaにはαＮを代入す
る。13のRbの内容は計算実行に先立ち０にクリアされて
いるものとする。この時の30の加算器の出力はパイプラ
イン後αＮ＊０＋k3、αＮ＊k3＋０、αＮ＊（αＮ＊
k3）＋k1となり、３ステップめで誤り位置多項式を微分
した多項式に誤り位置を代入計算した値が計算される。
なお上式は全てガロア体上の演算であり、演算子＋は加
算、＊は乗算をしめす。一般に計算に必要なステップ数
は初期設定を除いて多項式の次数とおなじだけ必要であ
る。また０元判定回路11、αの累乗発生回路33は誤り位
置の計算において誤り位置多項式に誤り位置数を代入し
て根であるか否かを判定するのに用いる。この計算は、
前述の多項式の計算方法と同一手順で行い得るので省略
する。第４図は29の乗算回路の内部を示したものであ
る。第４図において１、２、３、４、５、６、７、８は
ガロア体の固定係数乗算器、９は12のパイプラインレジ
スタの各ビットが０のとき対応して各固定係数乗算器出
力に直列に０元を乗算する論理積回路であり各固定係数
乗算器出力に対して各ビット毎にそれぞれ設けられてい
る。また10はパリディジェネレータ回路であり乗算結果
の全シンボルについて各ビットごとの排他的論理和を出
力する。
発明が解決しようとする問題点 しかしながら上記のような方法では、誤りの発生個数
が多くなるほど誤り位置多項式と誤り位置多項式の次数
が大きくなり多項式の値を求めるための積和計算の量が
増加し復号時間が長くなるという問題点を有していた。
たとえば、誤り位置αｉが求まっているとき、その誤り
位置に対応する誤り量eiは、誤り位置多項式をσ
（ｘ）、誤り量多項式をω（ｘ）としたとき ei＝−αｉ・ω（αｉ）・σ′（αｉ）−１で計算でき
るが、多項式の計算としてω（αｉ）の計算とσ′（α
ｉ）の計算をおこなわなければならず、誤りの発生個数
が多い場合ほど積和計算の計算量が多くなってしまう。
通常光ディスク等の記録再生にリードソロモン符号を使
する場合にはリアルタイムでデータを転送する必要上復
号時間が制限されているため、高能力の符号を実用的に
使用するためには、復号時間すなわち復号に要する計算
量を低減することが必要である。本発明は上記問題点に
鑑み高速性と小さなハードウエア量を両立させるガロア
体演算装置を提供するものである。
が多くなるほど誤り位置多項式と誤り位置多項式の次数
が大きくなり多項式の値を求めるための積和計算の量が
増加し復号時間が長くなるという問題点を有していた。
たとえば、誤り位置αｉが求まっているとき、その誤り
位置に対応する誤り量eiは、誤り位置多項式をσ
（ｘ）、誤り量多項式をω（ｘ）としたとき ei＝−αｉ・ω（αｉ）・σ′（αｉ）−１で計算でき
るが、多項式の計算としてω（αｉ）の計算とσ′（α
ｉ）の計算をおこなわなければならず、誤りの発生個数
が多い場合ほど積和計算の計算量が多くなってしまう。
通常光ディスク等の記録再生にリードソロモン符号を使
する場合にはリアルタイムでデータを転送する必要上復
号時間が制限されているため、高能力の符号を実用的に
使用するためには、復号時間すなわち復号に要する計算
量を低減することが必要である。本発明は上記問題点に
鑑み高速性と小さなハードウエア量を両立させるガロア
体演算装置を提供するものである。
問題点を解決するための手段 上記問題点に鑑み本発明は、符号語がガロア体GF
（2r）の元から構成されるリードソロモン符号のｔ次の
誤り位置多項式の各次数の係数値及び誤り位置多項式に
位置数を代入して計算した各次数における（ｔ＋１）シ
ンボル以上の中間計算結果を記憶する記憶素子群と、前
記記憶素子に係数値を格納する手段と、第一の任意の１
シンボル入力に対して共通に前記ガロア体GF（2r）の原
始元αの０から（ｒ−１）累乗すなわちα０からαr-1
までのｒ個の固定係数を乗ずるかあるいはまた前記ｒ個
以内である（ｔ＋１）シンボルの記憶素子群に対してα
０からαｔまでの固定係数を乗ずるｒ個の乗算器群と、
GF（2r）の下位０番目ビットから始めて偶数番目のビッ
トが０、奇数番目のビットが１となるシンボルを発生す
る固定係数発生回路と、前記とは別の第二の任意の１シ
ンボル入力の２進表現の下位０番目ビットからｒ−１番
目ビットに対応して前記α０からαr-1までのｒ個の固
定係数を前記ガロア体GF（2r）上の０元の固定係数に切
り換える手段と、前記第二の１シンボル入力を前記固定
係数発生回路の出力する固定係数に切り換える手段と、
前記第一の任意のシンボルと前記記憶素子群の出力の値
を入力として切り換えた選択された結果を前記乗算器群
の入力に供給する手段と、前記乗算器群によって得られ
た結果のｒ個のシンボルの２元ベクトル各成分毎の排他
論理和をとり１シンボルの結果を得るｒ個の奇偶判定器
群と、前記奇偶判定器群の出力シンボルが０元であるか
を検出する手段と、前記乗算器群によって得られた（ｔ
＋１）シンボルの出力を前記記憶素子群に帰還格納する
手段とを備えたガロア体演算装置において、ガロア体の
乗算を行う場合には第一の任意の１シンボル入力にα０
からαr-1までのｒ個の固定係数を乗じかつ第二の任意
の１シンボル入力の２進表現の０番目ビットからｒ−１
番目ビットに対応して各ビットが０ならば前記α０から
αr-1までのｒ個の固定係数を前記ガロア体GF（2r）上
の０元の固定係数に切り換えて乗算結果を前記奇遇判定
器群野出力シンボルに得て、誤り位置数および誤り位置
多項式の微分を求める場合には前記固定係数乗算器のα
ｔに対応する前記記憶素子群に誤り位置多項式の第ｔ次
の係数を各々格納した後、前記の第二の１シンボル入力
として少なくとも下位からｔビット目まで１を与えかつ
前記乗算器の各入力として対応する前記記憶素子の各々
を選択して前記乗算器による（ｔ＋１）シンボルの乗算
結果を各々の前記記憶素子に帰還して前記の奇遇判定器
群の出力が０元となったとき帰還を一旦停止して帰還回
数を計測し誤り位置数を得た後、更に前記第二の１シン
ボル入力として前記の固定係数発生回路の出力を与え前
記奇遇判定器群の出力に誤り位置多項式の微分演算結果
を得た後、再び帰還を継続して帰還回数が符号長−１回
に至るまで上記の操作を繰り返す。また本発明のガロア
体演算方法はｒ次以上の誤り位置数を求める場合誤り位
置多項式の各次粕の係数値及び誤り位置多項式に誤り位
置数を代入して計算した各次数における中間結果を記憶
する記憶素子群と前記ｒ次以上の誤り位置数に対応する
記憶素子群の出力に前記αｒ以上の固定係数乗算器群と
前記αｒ以上の固定係数乗算器群の固定係数を０元に切
り替える手段とα０からαr-1までの固定乗算器群によ
って得られた乗算結果と前記αｒ以上の固定係数乗算器
群によって得られた乗算結果の合計ｒ＋１個以上である
（ｔ＋１）個のシンボルの２元ベクトル各成分毎の排他
論理和をとって１シンボルの結果を得るｒ個の奇偶判定
器群を設け、ガロア体の乗算を行う場合には前記第一の
任意の１シンボル入力にα０からαr-1までのｒ個の固
定係数を乗じかつ第二の任意の１シンボル入力の２進表
現の下位０番目ビットからｒ−１番目ビットの各ビット
が０ならば対応する前記α０からαr-1までのｒ個の固
定係数乗算器群の固定係数を前記ガロア体GF（2r）上の
０元の固定係数に切り換えるとともに前記奇偶判定器群
の入力に前記αｒ以上の固定係数乗算器群の出力が０元
を供給させるような手段を有して乗算結果を前記奇偶判
定器群の出力に得て、ｒ以上の誤り位置数を求める場合
には前記の第二の１シンボル入力として各ビットに１を
与えるとともに前記奇偶判定器群の入力に前記αｒ以上
の固定係数乗算器群の出力が入力されるようにし、誤り
位置多項式の微分を求める場合には第二の任意の１シン
ボル入力として前記固定係数発生回路の出力を与えると
ともに前記αｒ以上の固定係数乗算器群のｒ番目から始
めて偶数番目の固定係数乗算器出力が０元を出力して前
記奇偶判定器群の入力に供給するようにして誤り位置多
項式の最高次数がｒ次以上の場合においても前記と同様
の操作を繰り返すのである。
（2r）の元から構成されるリードソロモン符号のｔ次の
誤り位置多項式の各次数の係数値及び誤り位置多項式に
位置数を代入して計算した各次数における（ｔ＋１）シ
ンボル以上の中間計算結果を記憶する記憶素子群と、前
記記憶素子に係数値を格納する手段と、第一の任意の１
シンボル入力に対して共通に前記ガロア体GF（2r）の原
始元αの０から（ｒ−１）累乗すなわちα０からαr-1
までのｒ個の固定係数を乗ずるかあるいはまた前記ｒ個
以内である（ｔ＋１）シンボルの記憶素子群に対してα
０からαｔまでの固定係数を乗ずるｒ個の乗算器群と、
GF（2r）の下位０番目ビットから始めて偶数番目のビッ
トが０、奇数番目のビットが１となるシンボルを発生す
る固定係数発生回路と、前記とは別の第二の任意の１シ
ンボル入力の２進表現の下位０番目ビットからｒ−１番
目ビットに対応して前記α０からαr-1までのｒ個の固
定係数を前記ガロア体GF（2r）上の０元の固定係数に切
り換える手段と、前記第二の１シンボル入力を前記固定
係数発生回路の出力する固定係数に切り換える手段と、
前記第一の任意のシンボルと前記記憶素子群の出力の値
を入力として切り換えた選択された結果を前記乗算器群
の入力に供給する手段と、前記乗算器群によって得られ
た結果のｒ個のシンボルの２元ベクトル各成分毎の排他
論理和をとり１シンボルの結果を得るｒ個の奇偶判定器
群と、前記奇偶判定器群の出力シンボルが０元であるか
を検出する手段と、前記乗算器群によって得られた（ｔ
＋１）シンボルの出力を前記記憶素子群に帰還格納する
手段とを備えたガロア体演算装置において、ガロア体の
乗算を行う場合には第一の任意の１シンボル入力にα０
からαr-1までのｒ個の固定係数を乗じかつ第二の任意
の１シンボル入力の２進表現の０番目ビットからｒ−１
番目ビットに対応して各ビットが０ならば前記α０から
αr-1までのｒ個の固定係数を前記ガロア体GF（2r）上
の０元の固定係数に切り換えて乗算結果を前記奇遇判定
器群野出力シンボルに得て、誤り位置数および誤り位置
多項式の微分を求める場合には前記固定係数乗算器のα
ｔに対応する前記記憶素子群に誤り位置多項式の第ｔ次
の係数を各々格納した後、前記の第二の１シンボル入力
として少なくとも下位からｔビット目まで１を与えかつ
前記乗算器の各入力として対応する前記記憶素子の各々
を選択して前記乗算器による（ｔ＋１）シンボルの乗算
結果を各々の前記記憶素子に帰還して前記の奇遇判定器
群の出力が０元となったとき帰還を一旦停止して帰還回
数を計測し誤り位置数を得た後、更に前記第二の１シン
ボル入力として前記の固定係数発生回路の出力を与え前
記奇遇判定器群の出力に誤り位置多項式の微分演算結果
を得た後、再び帰還を継続して帰還回数が符号長−１回
に至るまで上記の操作を繰り返す。また本発明のガロア
体演算方法はｒ次以上の誤り位置数を求める場合誤り位
置多項式の各次粕の係数値及び誤り位置多項式に誤り位
置数を代入して計算した各次数における中間結果を記憶
する記憶素子群と前記ｒ次以上の誤り位置数に対応する
記憶素子群の出力に前記αｒ以上の固定係数乗算器群と
前記αｒ以上の固定係数乗算器群の固定係数を０元に切
り替える手段とα０からαr-1までの固定乗算器群によ
って得られた乗算結果と前記αｒ以上の固定係数乗算器
群によって得られた乗算結果の合計ｒ＋１個以上である
（ｔ＋１）個のシンボルの２元ベクトル各成分毎の排他
論理和をとって１シンボルの結果を得るｒ個の奇偶判定
器群を設け、ガロア体の乗算を行う場合には前記第一の
任意の１シンボル入力にα０からαr-1までのｒ個の固
定係数を乗じかつ第二の任意の１シンボル入力の２進表
現の下位０番目ビットからｒ−１番目ビットの各ビット
が０ならば対応する前記α０からαr-1までのｒ個の固
定係数乗算器群の固定係数を前記ガロア体GF（2r）上の
０元の固定係数に切り換えるとともに前記奇偶判定器群
の入力に前記αｒ以上の固定係数乗算器群の出力が０元
を供給させるような手段を有して乗算結果を前記奇偶判
定器群の出力に得て、ｒ以上の誤り位置数を求める場合
には前記の第二の１シンボル入力として各ビットに１を
与えるとともに前記奇偶判定器群の入力に前記αｒ以上
の固定係数乗算器群の出力が入力されるようにし、誤り
位置多項式の微分を求める場合には第二の任意の１シン
ボル入力として前記固定係数発生回路の出力を与えると
ともに前記αｒ以上の固定係数乗算器群のｒ番目から始
めて偶数番目の固定係数乗算器出力が０元を出力して前
記奇偶判定器群の入力に供給するようにして誤り位置多
項式の最高次数がｒ次以上の場合においても前記と同様
の操作を繰り返すのである。
作用 ガロア体GF（2r）の乗算は共通の１シンボルの乗数に
対してα０からαｒ−１までの固定係数を掛けたｒ個の
結果をまず求め、被乗数シンボルの２元ベクトルのｒ次
成分が０ならばｒ次成分に対応した前記固定乗数乗算結
果を０とし、得られたｒ個のシンボルの排他的論理をと
るという手順で実行することができる。また同じ固定乗
数回路を使用して誤り位置多項式の０次からｔ次まで係
数値計算結果を格納したメモリー出力を固定乗数回路の
入力とし、メモリー出力にα０からαｔまでの固定係数
をそれぞれ乗じかつ乗算結果を各次数毎にメモリーに帰
還しながら固定係数乗算器群によって得られた結果のｔ
個のシンボルの排他的論理和を取り１シンボルの結果を
得て誤り位置多項式に誤り位置を代入した計算結果を求
めることができる。
対してα０からαｒ−１までの固定係数を掛けたｒ個の
結果をまず求め、被乗数シンボルの２元ベクトルのｒ次
成分が０ならばｒ次成分に対応した前記固定乗数乗算結
果を０とし、得られたｒ個のシンボルの排他的論理をと
るという手順で実行することができる。また同じ固定乗
数回路を使用して誤り位置多項式の０次からｔ次まで係
数値計算結果を格納したメモリー出力を固定乗数回路の
入力とし、メモリー出力にα０からαｔまでの固定係数
をそれぞれ乗じかつ乗算結果を各次数毎にメモリーに帰
還しながら固定係数乗算器群によって得られた結果のｔ
個のシンボルの排他的論理和を取り１シンボルの結果を
得て誤り位置多項式に誤り位置を代入した計算結果を求
めることができる。
このとき被乗数はその２進ベクトルがすべて１となる
ようにレジスタに設定すればよい。そして誤り個数ｔが
（ｒ−１）より大きい場合には、誤り位置多項式に位置
を代入して計算した各次数における中間結果を記憶する
記憶素子群の出力シンボルにさらにｒ次以上の固定係数
乗算器群を設ければよい。また前記誤り位置多項式に誤
り位置を代入した計算結果が０元であった時、その誤り
位置は誤り位置多項式の解である。ここで次の誤り位置
の計算にはいる前に誤り位置多項式の各次成分が求まっ
ていることを利用して誤り位置多項式を微分した多項式
に誤り位置を代入した多項式の値を求めることができ
る。ガロア体での多項式の微分は、微分前の偶数次の項
は微分後は０、微分前の奇数次の項の係数はそのまま微
分後に１次低次の項の係数となる。すなわち σ（Ｘ）＝k8X8＋k7X7＋k6X6＋k5X5＋k4X4＋k3X3＋k2X2
＋k1Ｘ＋k0の微分は、 σ′（Ｘ）＝k7X6＋k5X4＋k3X2＋k1という関係である
が、このとき Ｘ・σ（Ｘ）＝k7X7＋k5X5＋k3X3＋k1X1であることを利
用してＸ・σ（Ｘ）を同じハードウエアを使用して容易
にもとめることができる。
ようにレジスタに設定すればよい。そして誤り個数ｔが
（ｒ−１）より大きい場合には、誤り位置多項式に位置
を代入して計算した各次数における中間結果を記憶する
記憶素子群の出力シンボルにさらにｒ次以上の固定係数
乗算器群を設ければよい。また前記誤り位置多項式に誤
り位置を代入した計算結果が０元であった時、その誤り
位置は誤り位置多項式の解である。ここで次の誤り位置
の計算にはいる前に誤り位置多項式の各次成分が求まっ
ていることを利用して誤り位置多項式を微分した多項式
に誤り位置を代入した多項式の値を求めることができ
る。ガロア体での多項式の微分は、微分前の偶数次の項
は微分後は０、微分前の奇数次の項の係数はそのまま微
分後に１次低次の項の係数となる。すなわち σ（Ｘ）＝k8X8＋k7X7＋k6X6＋k5X5＋k4X4＋k3X3＋k2X2
＋k1Ｘ＋k0の微分は、 σ′（Ｘ）＝k7X6＋k5X4＋k3X2＋k1という関係である
が、このとき Ｘ・σ（Ｘ）＝k7X7＋k5X5＋k3X3＋k1X1であることを利
用してＸ・σ（Ｘ）を同じハードウエアを使用して容易
にもとめることができる。
すなわち誤り位置多項式の０次からｔ次まで各次数計算
結果を格納したメモリー出力にα０からαｔまでの固定
係数をそれぞれ乗じた結果に対して、被乗数として２進
ベクトルが下位から偶数番目のビットが０、下位から奇
数番目のビットが１となるようなシンボルを用いれば、
固定係数乗算器群の出力のうちαの偶数乗に対応するビ
ット成分が０となり、αの奇数乗のみの固定乗数乗算結
果の排他的論理和をとることになり、誤り位置多項式を
微分した多項式に誤り位置を代入した結果Ｘ・σ（Ｘ）
を特別な計算をすることなく容易に求めることが可能で
ある。このようにして求めた微分した多項式の値は微分
時に多項式変数の次数を１次下げるという計算がはいっ
ていないため、実際に微分した多項式の値に比較して誤
り位置が１次余分に掛かった値が求まるが、これは誤り
量を求める過程において例えば誤り量に誤り位置を１回
余分に掛けるという方法で解決可能である。
結果を格納したメモリー出力にα０からαｔまでの固定
係数をそれぞれ乗じた結果に対して、被乗数として２進
ベクトルが下位から偶数番目のビットが０、下位から奇
数番目のビットが１となるようなシンボルを用いれば、
固定係数乗算器群の出力のうちαの偶数乗に対応するビ
ット成分が０となり、αの奇数乗のみの固定乗数乗算結
果の排他的論理和をとることになり、誤り位置多項式を
微分した多項式に誤り位置を代入した結果Ｘ・σ（Ｘ）
を特別な計算をすることなく容易に求めることが可能で
ある。このようにして求めた微分した多項式の値は微分
時に多項式変数の次数を１次下げるという計算がはいっ
ていないため、実際に微分した多項式の値に比較して誤
り位置が１次余分に掛かった値が求まるが、これは誤り
量を求める過程において例えば誤り量に誤り位置を１回
余分に掛けるという方法で解決可能である。
実施例 以下本発明の一実施例のガロア体演算方法について図
面を参照しながら説明する。第１図ａ−１および第１図
ａ−２は本発明の第１の実施例の流れ図を示すものであ
り第１図ｂは本発明の第一の実施例に適用する装置のブ
ロック図を示すものである。第１図ｂにおいて、１、
２、３、４、５、６、７、８はガロア体の固定係数乗算
器、９は論理積回路、10はパリティジェネレータ回路、
12、13はパイプラインレジスタで以上は第４図と同じで
ある。11は０元判定回路、14、15、36はスイッチ論理ゲ
ート回路、16、17、18は誤り位置多項式の係数入力値及
び各次数の誤り位置多項式の位置数を乗じた中間値を記
憶するレジスタである。35は８ビット固定シンボル発生
回路で２進00000010の定数を発生する。37はパイプライ
ンレジスタである。これらの演算はGF（28）上で行なわ
れ、第一の実施例では誤りの個数ｔは２以下の場合を扱
っている。以上のように構成されたガロア体演算装置に
適用する演算方法ついて、以下第１図を用いてその流れ
を説明する。シンドロームのガロア体上での乗除算、加
算処理により誤り個数と誤り位置多項式の各次数の係数
値を求める時、乗算はある１シンボル乗数入力に対して
共通にGF（2r）の原始元αの０から（ｒ−１）累乗すな
わちα０からαｒ−１までのｒ個の固定係数を乗じ被乗
数シンボルの２元ベクトルの各ｒ次成分に対応して０元
の固定係数を直列に更に乗じて得たｒ個の乗算結果のシ
ンボルの排他論理和をとり１シンボルの乗算結果を得る
のであり、第１図の15のスイッチ論理ゲート回路を13の
入力パイプラインレジスタ側に切り換えることにより本
実施例のガロア体演算装置は第４図の乗算回路と同様の
働きをする。除算、加算は本実施例には記入していない
別のブロックの機能を含めて実行するのであるが、例え
ば除算は逆元ROMと本実施例の乗算器により構成するこ
とができる。この後誤り位置多項式の各次数の係数の値
をスイッチ論理ゲート回路14を帰還側でない入力側にセ
ットして16、17、18のレジスタに格納する。スイッチ論
理ゲート回路15は乗算回路機能時の被乗算シンボルを格
納する13のパイプラインレジスタ出力とα０からα２ま
での固定係数をそれぞれ乗じて誤り位置多項式の各次数
の誤り位置多項式の位置数を代入した中間値の帰還値を
格納する16、17、18のレジスタ出力とを切り換えるもの
であり、スイッチ論理ゲート回路14を帰還側にして符号
長ｎに相当するステップ数だけ帰還を繰り返す。この時
13の入力パイプラインレジスタには０元を入力してお
き、12の入力パイプラインレシジスタにはすべてのビッ
トに１を立てておいてα３次以上の項が影響しないよう
にする。この処理は並列処理であるため非常に高速に行
なわれ、パリティジェネレータ回路37の出力シンボルが
０元であるかを０元判定回路11により確認することによ
り根の判定を行ない、求める誤り位置は帰還回数によっ
て得ることが出来る。なお、本実施例では０元判定回路
11は固定係数乗算器のあとにあるため、誤り位置多項式
の根がα０である場合には０元判定回路11では根の判定
が行えないが、このときは誤り位置多項式の各次の係数
の排他的論理和が０であることと根がα０であることと
が同じであることを利用して、例えば、レジスタ16、1
7、18に係数値を格納する際などに並行して排他論理和
をとりα０の根を持つことを確認可能である。ここで帰
還ステップ中に０元判定回路11により誤り位置多項式の
根が求まったとき、次の帰還ステップに移る前にスイッ
チ論理ゲート36を固定パターン発生器35側に切り替え
る。帰還値レジスタ16、17、18には誤り位置多項式に誤
り位置を代入した式の各係数値が格納されている状態で
あり固定パターン発生器36は２進00000010のシンボルを
発生しているのでパリティジェネレータ回路10にはα１
次の項のみが出力され、パイプラインレジスタ37には、
誤り位置多項式を微分した多項式に誤り位置を代入した
場合の式の値を格納する。この式の値を後の誤り量の計
算に用いることにより、誤り位置の計算に際し多項式の
計算量を減らすことができる。説明を簡単にするため本
例では誤りの個数は２個以下の場合をしめしているが、
特に誤りの発生個数が多く誤り位置多項式の次数が高く
なったとき、すなわち従来の方法では計算時間が多くか
かる場合ほど計算量の低減効果が大きい。以上のように
本実施例では第４図の乗算回路にα０からαｒ−１まで
のｒ個の固定係数乗算器による部分積を帰還し各スイッ
チ毎の中間結果を記憶するレジスタを設け、更にビット
方向のパリテイをとった出力シンボルが０元であること
を検出する論理回路、被乗数のかわりに10固定シンボル
を発生する論理回路、一般的な乗算と誤り位置多項式の
根の計算と誤り位置多項式を微分した多項式の値の計算
の機能を切り換える論理回路を付け加えてハードウェア
資産の有効利用と高速化を同時に実現している。
面を参照しながら説明する。第１図ａ−１および第１図
ａ−２は本発明の第１の実施例の流れ図を示すものであ
り第１図ｂは本発明の第一の実施例に適用する装置のブ
ロック図を示すものである。第１図ｂにおいて、１、
２、３、４、５、６、７、８はガロア体の固定係数乗算
器、９は論理積回路、10はパリティジェネレータ回路、
12、13はパイプラインレジスタで以上は第４図と同じで
ある。11は０元判定回路、14、15、36はスイッチ論理ゲ
ート回路、16、17、18は誤り位置多項式の係数入力値及
び各次数の誤り位置多項式の位置数を乗じた中間値を記
憶するレジスタである。35は８ビット固定シンボル発生
回路で２進00000010の定数を発生する。37はパイプライ
ンレジスタである。これらの演算はGF（28）上で行なわ
れ、第一の実施例では誤りの個数ｔは２以下の場合を扱
っている。以上のように構成されたガロア体演算装置に
適用する演算方法ついて、以下第１図を用いてその流れ
を説明する。シンドロームのガロア体上での乗除算、加
算処理により誤り個数と誤り位置多項式の各次数の係数
値を求める時、乗算はある１シンボル乗数入力に対して
共通にGF（2r）の原始元αの０から（ｒ−１）累乗すな
わちα０からαｒ−１までのｒ個の固定係数を乗じ被乗
数シンボルの２元ベクトルの各ｒ次成分に対応して０元
の固定係数を直列に更に乗じて得たｒ個の乗算結果のシ
ンボルの排他論理和をとり１シンボルの乗算結果を得る
のであり、第１図の15のスイッチ論理ゲート回路を13の
入力パイプラインレジスタ側に切り換えることにより本
実施例のガロア体演算装置は第４図の乗算回路と同様の
働きをする。除算、加算は本実施例には記入していない
別のブロックの機能を含めて実行するのであるが、例え
ば除算は逆元ROMと本実施例の乗算器により構成するこ
とができる。この後誤り位置多項式の各次数の係数の値
をスイッチ論理ゲート回路14を帰還側でない入力側にセ
ットして16、17、18のレジスタに格納する。スイッチ論
理ゲート回路15は乗算回路機能時の被乗算シンボルを格
納する13のパイプラインレジスタ出力とα０からα２ま
での固定係数をそれぞれ乗じて誤り位置多項式の各次数
の誤り位置多項式の位置数を代入した中間値の帰還値を
格納する16、17、18のレジスタ出力とを切り換えるもの
であり、スイッチ論理ゲート回路14を帰還側にして符号
長ｎに相当するステップ数だけ帰還を繰り返す。この時
13の入力パイプラインレジスタには０元を入力してお
き、12の入力パイプラインレシジスタにはすべてのビッ
トに１を立てておいてα３次以上の項が影響しないよう
にする。この処理は並列処理であるため非常に高速に行
なわれ、パリティジェネレータ回路37の出力シンボルが
０元であるかを０元判定回路11により確認することによ
り根の判定を行ない、求める誤り位置は帰還回数によっ
て得ることが出来る。なお、本実施例では０元判定回路
11は固定係数乗算器のあとにあるため、誤り位置多項式
の根がα０である場合には０元判定回路11では根の判定
が行えないが、このときは誤り位置多項式の各次の係数
の排他的論理和が０であることと根がα０であることと
が同じであることを利用して、例えば、レジスタ16、1
7、18に係数値を格納する際などに並行して排他論理和
をとりα０の根を持つことを確認可能である。ここで帰
還ステップ中に０元判定回路11により誤り位置多項式の
根が求まったとき、次の帰還ステップに移る前にスイッ
チ論理ゲート36を固定パターン発生器35側に切り替え
る。帰還値レジスタ16、17、18には誤り位置多項式に誤
り位置を代入した式の各係数値が格納されている状態で
あり固定パターン発生器36は２進00000010のシンボルを
発生しているのでパリティジェネレータ回路10にはα１
次の項のみが出力され、パイプラインレジスタ37には、
誤り位置多項式を微分した多項式に誤り位置を代入した
場合の式の値を格納する。この式の値を後の誤り量の計
算に用いることにより、誤り位置の計算に際し多項式の
計算量を減らすことができる。説明を簡単にするため本
例では誤りの個数は２個以下の場合をしめしているが、
特に誤りの発生個数が多く誤り位置多項式の次数が高く
なったとき、すなわち従来の方法では計算時間が多くか
かる場合ほど計算量の低減効果が大きい。以上のように
本実施例では第４図の乗算回路にα０からαｒ−１まで
のｒ個の固定係数乗算器による部分積を帰還し各スイッ
チ毎の中間結果を記憶するレジスタを設け、更にビット
方向のパリテイをとった出力シンボルが０元であること
を検出する論理回路、被乗数のかわりに10固定シンボル
を発生する論理回路、一般的な乗算と誤り位置多項式の
根の計算と誤り位置多項式を微分した多項式の値の計算
の機能を切り換える論理回路を付け加えてハードウェア
資産の有効利用と高速化を同時に実現している。
なお、本発明の第一の実施例において16、17、18の記
憶素子であるレジスタは専用のものを設ける必要はな
く、誤り位置多項式の係数を算出する過程において使用
するメモリーでもよく、しかも誤り位置多項式の根を求
める過程においていつも同じ領域に帰還されなければな
らないものでもない。また14のスイッチ論理ゲート回路
を使用せずに論理和ゲート回路を使用して同様な処理を
行ってもよい。次に本発明の第二の実施例について図面
を参照しながら説明する。第２図ａ−１および第２図ａ
−２は本発明の第２の実施例の流れ図を示すものであ
り、第２図ｂは本発明の第二の実施例に適用するガロア
体演算装置に於けるブロック図である。第２図ｂにおい
て１、２、３、４、５、６、７、８はガロア体の固定係
数乗算器、９は論理積回路、10はパリティジェネレータ
回路、12、13はパイプラインレジスタであって以上は第
４図と同じものである。11は０元判定回路、14、15、36
はスイッチ論理ゲート回路、16、17、18は誤り位置多項
式の係数入力値及び各次数の誤り位置多項式の位置数を
乗じた中間値を記憶するレジスタでこれらは第１図と同
じものである。また19、20、21、22、23、24は誤り位置
多項式の係数入力値及び各次数の誤り位置多項式の位置
数を乗じた中間値を記憶するレジスタ、25はα８の固定
係数乗算器である、26は１系統の論理スイッチ回路であ
り、27は論理積回路である。35は８ビット固定シンボル
発生回路で２進10101010の定数を発生する。37はパイプ
ラインレジスタである。これらの演算はGF（28）上で行
なわれ、第二の実施例では誤りの個数ｔは８以下の場合
を扱うため、記憶素子の数を増やすと共に誤りの個数ｔ
がｒを超過した分、固定係数乗算器を誤り位置多項式の
ｒ以上の次数の計算専用に追加している。以上のように
構成されたガロア体演算装置について、以下第２図ｂを
用いてその動作を説明する。誤り個数と誤り位置多項式
の各次数の係数の値を求める時、ガロア体での乗算は第
１図ａ−１、第１図ａ−２あるいは第４図における場合
と同様に行なうが、α８の乗算器の項の影響を除くため
論理スイッチ回路26はＬレベルにする。このとき論理積
回路27の出力はすべてＬレベルになりα８の乗算器25の
出力が乗算結果に影響することはない。誤り位置多項式
の計算は第１図ａ−１、第１図ａ−２と同様にして行な
うが誤り位置多項式の各次数は誤りの個数に応じて最大
８次の項まで初期設定される。また誤りの個数が７個以
下の場合に誤り位置多項式の根の計算及び誤り位置多項
式の微分した値の計算をする場合には使用しない次数に
対応するレジスタに０元を初期設定すれば問題無く計算
出来る。この様にしてChienの方法によって誤り位置が
確定した後、再び乗算回路を使用して誤り位置を微分し
た式の値を求めることができる。なお通常のガロア体乗
算器として働かすときには26の論理スイッチのかわりに
24のレジスタに０元を代入しておいてもよい。
憶素子であるレジスタは専用のものを設ける必要はな
く、誤り位置多項式の係数を算出する過程において使用
するメモリーでもよく、しかも誤り位置多項式の根を求
める過程においていつも同じ領域に帰還されなければな
らないものでもない。また14のスイッチ論理ゲート回路
を使用せずに論理和ゲート回路を使用して同様な処理を
行ってもよい。次に本発明の第二の実施例について図面
を参照しながら説明する。第２図ａ−１および第２図ａ
−２は本発明の第２の実施例の流れ図を示すものであ
り、第２図ｂは本発明の第二の実施例に適用するガロア
体演算装置に於けるブロック図である。第２図ｂにおい
て１、２、３、４、５、６、７、８はガロア体の固定係
数乗算器、９は論理積回路、10はパリティジェネレータ
回路、12、13はパイプラインレジスタであって以上は第
４図と同じものである。11は０元判定回路、14、15、36
はスイッチ論理ゲート回路、16、17、18は誤り位置多項
式の係数入力値及び各次数の誤り位置多項式の位置数を
乗じた中間値を記憶するレジスタでこれらは第１図と同
じものである。また19、20、21、22、23、24は誤り位置
多項式の係数入力値及び各次数の誤り位置多項式の位置
数を乗じた中間値を記憶するレジスタ、25はα８の固定
係数乗算器である、26は１系統の論理スイッチ回路であ
り、27は論理積回路である。35は８ビット固定シンボル
発生回路で２進10101010の定数を発生する。37はパイプ
ラインレジスタである。これらの演算はGF（28）上で行
なわれ、第二の実施例では誤りの個数ｔは８以下の場合
を扱うため、記憶素子の数を増やすと共に誤りの個数ｔ
がｒを超過した分、固定係数乗算器を誤り位置多項式の
ｒ以上の次数の計算専用に追加している。以上のように
構成されたガロア体演算装置について、以下第２図ｂを
用いてその動作を説明する。誤り個数と誤り位置多項式
の各次数の係数の値を求める時、ガロア体での乗算は第
１図ａ−１、第１図ａ−２あるいは第４図における場合
と同様に行なうが、α８の乗算器の項の影響を除くため
論理スイッチ回路26はＬレベルにする。このとき論理積
回路27の出力はすべてＬレベルになりα８の乗算器25の
出力が乗算結果に影響することはない。誤り位置多項式
の計算は第１図ａ−１、第１図ａ−２と同様にして行な
うが誤り位置多項式の各次数は誤りの個数に応じて最大
８次の項まで初期設定される。また誤りの個数が７個以
下の場合に誤り位置多項式の根の計算及び誤り位置多項
式の微分した値の計算をする場合には使用しない次数に
対応するレジスタに０元を初期設定すれば問題無く計算
出来る。この様にしてChienの方法によって誤り位置が
確定した後、再び乗算回路を使用して誤り位置を微分し
た式の値を求めることができる。なお通常のガロア体乗
算器として働かすときには26の論理スイッチのかわりに
24のレジスタに０元を代入しておいてもよい。
発明の効果 以上述べてきたように本発明の方式によれば、符号誤
り検査訂正装置のガロア体演算装置の一部分である乗算
器の多くの部分を誤り位置多項式の微分式の値を求める
計算に使用することができ、かつこの計算を高速容易に
行なうことができる。特に誤りの発生個数が多く誤り位
置多項式の次式が高くなったとき、すなわち従来の方法
では計算時間が多くかかる場合ほど計算量の低減効果が
大きい。このようにしてハードウエア資産の共用により
高速復号と小さなハードウエアが同時に実現することに
より、高速かつ高機能要求される光ディスク装置等にお
いて、高い生誤り率を有する記録媒体の復号を実用的に
実行出来るためその効果は大なるものがある。
り検査訂正装置のガロア体演算装置の一部分である乗算
器の多くの部分を誤り位置多項式の微分式の値を求める
計算に使用することができ、かつこの計算を高速容易に
行なうことができる。特に誤りの発生個数が多く誤り位
置多項式の次式が高くなったとき、すなわち従来の方法
では計算時間が多くかかる場合ほど計算量の低減効果が
大きい。このようにしてハードウエア資産の共用により
高速復号と小さなハードウエアが同時に実現することに
より、高速かつ高機能要求される光ディスク装置等にお
いて、高い生誤り率を有する記録媒体の復号を実用的に
実行出来るためその効果は大なるものがある。
第１図ａは本発明の第一の実施例の流れ図、第１図ｂは
本発明の第一の実施例に適用するガロア体演算装置に於
けるブロック図、第２図ａは本発明の第２の実施例の流
れ図、第２図ｂは本発明の第二の実施例に適用するガロ
ア体演算装置に於けるブロック図、第３図は従来例にお
けるガロア体演算装置のブロック図、第４図は従来例に
おけるガロア体乗算回路のブロック図である。 １……α０ガロア体固定係数乗算器、２……α１ガロア
体固定係数乗算器、３……α２ガロア体固定係数乗算
器、４……α３ガロア体固定係数乗算器、５……α４ガ
ロア体固定係数乗算器、６……α５ガロア体固定係数乗
算器、７……α６ガロア体固定係数乗算器、８……α７
ガロア体固定係数乗算器、９……論理積回路、10……パ
リティジェネレータ回路、11……０元判定回路、12……
パイプラインレジスタ回路、13……パイプラインレジス
タ回路、14……スイッチ論理ゲート回路、15……スイッ
チ論理ゲート回路、16……レジスタ回路、17……レジス
タ回路、18……レジスタ回路、35……固定パターン発生
回路、37……パイプラインレジスタ回路。
本発明の第一の実施例に適用するガロア体演算装置に於
けるブロック図、第２図ａは本発明の第２の実施例の流
れ図、第２図ｂは本発明の第二の実施例に適用するガロ
ア体演算装置に於けるブロック図、第３図は従来例にお
けるガロア体演算装置のブロック図、第４図は従来例に
おけるガロア体乗算回路のブロック図である。 １……α０ガロア体固定係数乗算器、２……α１ガロア
体固定係数乗算器、３……α２ガロア体固定係数乗算
器、４……α３ガロア体固定係数乗算器、５……α４ガ
ロア体固定係数乗算器、６……α５ガロア体固定係数乗
算器、７……α６ガロア体固定係数乗算器、８……α７
ガロア体固定係数乗算器、９……論理積回路、10……パ
リティジェネレータ回路、11……０元判定回路、12……
パイプラインレジスタ回路、13……パイプラインレジス
タ回路、14……スイッチ論理ゲート回路、15……スイッ
チ論理ゲート回路、16……レジスタ回路、17……レジス
タ回路、18……レジスタ回路、35……固定パターン発生
回路、37……パイプラインレジスタ回路。
Claims (2)
- 【請求項１】符号語がガロア体GF（2r）の元から構成さ
れるリードソロモン符号のｔ次の誤り位置多項式の各次
数の係数値及び誤り位置多項式に位置数を代入して計算
した各次数における（ｔ＋１）シンボル以上の中間計算
結果を記憶する記憶素子群と、前記記憶素子に係数値を
格納する手段と、第一の任意の１シンボル入力に対して
共通に前記ガロア体GF（2r）の原始元αの０から（ｒ−
１）累乗すなわちα０からαr-1までのｒ個の固定係数
を乗ずるかあるいはまた前記ｒ個以内である（ｔ＋１）
シンボルの記憶素子群に対してα０からαｔまでの固定
係数を乗ずるｒ個の乗算器群と、GF（2r）の下位０番目
ビットから始めて偶数番目のビットが０、奇数番目のビ
ットが１となるシンボルを発生する固定係数発生回路
と、第二の任意の１シンボル入力の２進表現の下位０番
目ビットからｒ−１番目ビットに対応して前記α０から
αr-1までのｒ個の固定係数を前記ガロア体GF（2r）上
の０元の固定係数に切り換える手段と、前記第二の１シ
ンボル入力を前記固定係数発生回路の出力する固定係数
に切り換える手段と、前記第一の任意のシンボルと前記
記憶素子群の出力の値を入力として切り換え選択された
結果を前記乗算器群の入力に供給する手段と、前記乗算
器群によって得られた結果のｒ個のシンボルの２元ベク
トル各成分毎の排他論理和をとり１シンボルの結果を得
るｒ個の奇偶判定器群と、前記奇偶判定器群の出力シン
ボルが０元であるかを検出する手段と、前記乗算器群に
よって得られた（ｔ＋１）シンボルの出力を前記記憶素
子群に帰還格納する手段とを備えたガロア体演算装置に
おいて、ガロア体の乗算を行う場合には前記第一の任意
の１シンボル入力にα０からαr-1までのｒ個の固定係
数を乗じかつ第二の任意の１シンボル入力の２進表現の
０番目ビットからｒ−１番目ビットに対応して各ビット
が０ならば前記α０からαr-1までのｒ個の固定係数を
前記ガロア体GF（2r）上の０元の固定係数に切り換えて
乗算結果を前記奇遇判定器群の出力シンボルに得て、誤
り位置数および誤り位置多項式の微分を求める場合には
前記固定係数乗算器のαｔに対応する前記記憶素子群に
誤り位置多項式の第ｔ次の係数を各々格納した後、前記
の第二の１シンボル入力として少なくとも下位からｔビ
ット目まで１を与えかつ前記乗算器の各入力として対応
する前記記憶素子の各々を選択して前記乗算器による
（ｔ＋１）シンボルの乗算結果を各々の前記記憶素子に
帰還して前記の奇遇判定器群の出力が０元となったとき
帰還を一旦停止して帰還回数を計測し誤り位置数を得た
後、更に前記第二の１シンボル入力として前記の固定係
数発生回路の出力を与え前記奇遇判定器群の出力に誤り
位置多項式の微分演算結果を得た後、再び帰還を継続し
て帰還回数が符号長−１回に至るまで上記の操作を繰り
返すことを特徴とするガロア体演算方法。 - 【請求項２】ｒ次以上の誤り位置多項式の各次数の係数
値及び誤り位置多項式に誤り位置数を代入して計算した
各次数における中間結果を記憶する記憶素子群と前記ｒ
次以上の誤り位置数に対応する記憶素子群の出力にαｒ
以上の固定係数乗算器群と前記αｒ以上の固定係数乗算
器群の固定係数を０元に切り替える手段とを設け前記α
０からαr-1までの固定乗算器群によって得られた乗算
結果と前記αｒ以上の固定乗数乗算器群によって得られ
た乗算結果の合計ｒ＋１個以上である（ｔ＋１）個のシ
ンボルの２元ベクトル各成分毎の排他論理和をとって１
シンボルの結果を得るｒ個の奇偶判定器群を設け、ガロ
ア体の乗算を行う場合には前記第一の任意の１シンボル
入力にα０からαr-1までのｒ個の固定係数を乗じかつ
第二の任意の１シンボル入力の２進表現の下位０番目の
ビットからｒ−１番目ビットの各ビットが０ならば対応
するα０からαr-1までのｒ個の前記固定係数乗算器群
の固定係数を前記ガロア体GF（2r）上の０元の固定係数
に切り換えるとともに前記奇偶判定器群の入力に前記α
ｒ以上の固定係数乗算器群の出力が０元を供給させるよ
うな手段を有して乗算結果を前記奇偶判定器群の出力に
得て、ｒ次以上の誤り位置数を求める場合には前記の第
二の１シンボル入力として各ビットに１を与えるととも
に前記奇偶判定器群の入力に前記αｒ以上の固定係数乗
算器群の出力が入力されるようにし、誤り位置多項式の
微分を求める場合には第二の任意の１シンボル入力とし
て前記固定係数発生回路の出力を与えるとともに前記α
ｒ以上の固定係数乗算器群のｒ番目から始めて偶数番目
の固定係数乗算器出力が０元を出力して前記奇偶判定器
群の入力に供給するようにして同様な手順の操作を行う
ところの特許請求の範囲第１項記載のガロア体演算方
法。
Priority Applications (6)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP62151863A JPH0834440B2 (ja) | 1987-06-18 | 1987-06-18 | ガロア体演算方法 |
| US07/130,159 US4875211A (en) | 1986-12-10 | 1987-12-08 | Galois field arithmetic logic unit |
| CA000553939A CA1276043C (en) | 1986-12-10 | 1987-12-09 | Galois field arithmetic logic unit |
| DE8787118248T DE3784459T2 (de) | 1986-12-10 | 1987-12-09 | Arithmetische und logische einheit fuer elemente von galois-feldern. |
| EP87118248A EP0271082B1 (en) | 1986-12-10 | 1987-12-09 | Galois field arithmetic logic unit |
| KR1019870014116A KR920000828B1 (ko) | 1986-12-10 | 1987-12-10 | 가로아체(Galois field)연산장치 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP62151863A JPH0834440B2 (ja) | 1987-06-18 | 1987-06-18 | ガロア体演算方法 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPS63314920A JPS63314920A (ja) | 1988-12-22 |
| JPH0834440B2 true JPH0834440B2 (ja) | 1996-03-29 |
Family
ID=15527885
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP62151863A Expired - Fee Related JPH0834440B2 (ja) | 1986-12-10 | 1987-06-18 | ガロア体演算方法 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JPH0834440B2 (ja) |
Families Citing this family (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPH03179924A (ja) * | 1989-12-08 | 1991-08-05 | Sony Corp | 有限体の乗算回路 |
| JPH03182122A (ja) * | 1989-12-11 | 1991-08-08 | Sony Corp | 有限体の除算回路 |
| JP2606647B2 (ja) * | 1993-02-18 | 1997-05-07 | 日本電気株式会社 | 誤り訂正方法 |
-
1987
- 1987-06-18 JP JP62151863A patent/JPH0834440B2/ja not_active Expired - Fee Related
Also Published As
| Publication number | Publication date |
|---|---|
| JPS63314920A (ja) | 1988-12-22 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| EP0271082B1 (en) | Galois field arithmetic logic unit | |
| US5715262A (en) | Errors and erasures correcting reed-solomon decoder | |
| US4037093A (en) | Matrix multiplier in GF(2m) | |
| US6374383B1 (en) | Determining error locations using error correction codes | |
| EP0329789B1 (en) | Galois field arithmetic unit | |
| US5442578A (en) | Calculating circuit for error correction | |
| JP3232602B2 (ja) | ユークリッドの互除回路 | |
| US6026420A (en) | High-speed evaluation of polynomials | |
| EP0096109A2 (en) | Error correcting system | |
| US5778009A (en) | Dedicated ALU architecture for 10-bit Reed-Solomon error correction module | |
| JP2001502153A (ja) | 大規模データ・ブロックのためのハードウェア最適化リード・ソロモン・デコーダ | |
| US4994995A (en) | Bit-serial division method and apparatus | |
| US7089276B2 (en) | Modular Galois-field subfield-power integrated inverter-multiplier circuit for Galois-field division over GF(256) | |
| US5694330A (en) | Error correction method including erasure correction, and apparatus therefor | |
| EP0169908B1 (en) | Method and circuit for decoding error coded data | |
| KR100258951B1 (ko) | 리드-솔로몬(rs) 복호기와 그 복호방법 | |
| JP2800723B2 (ja) | リードソロモン復号器の誤り位置検出回路 | |
| US20100174970A1 (en) | Efficient implementation of a key-equation solver for bch codes | |
| US6405339B1 (en) | Parallelized programmable encoder/syndrome generator | |
| JPH0834440B2 (ja) | ガロア体演算方法 | |
| JPH0834439B2 (ja) | ガロア体演算装置 | |
| JP3614978B2 (ja) | ガロア体の除算方法および除算装置 | |
| JP2553565B2 (ja) | ガロア体演算装置 | |
| JPS63146619A (ja) | ガロア体演算装置 | |
| JPH0750595A (ja) | 復号化装置 |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| LAPS | Cancellation because of no payment of annual fees |