JPH04248630A - エラー訂正方法及び装置 - Google Patents
エラー訂正方法及び装置Info
- Publication number
- JPH04248630A JPH04248630A JP3123532A JP12353291A JPH04248630A JP H04248630 A JPH04248630 A JP H04248630A JP 3123532 A JP3123532 A JP 3123532A JP 12353291 A JP12353291 A JP 12353291A JP H04248630 A JPH04248630 A JP H04248630A
- Authority
- JP
- Japan
- Prior art keywords
- error
- value
- coefficient
- calculating
- calculation unit
- 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.)
- Granted
Links
Classifications
-
- H—ELECTRICITY
- H03—ELECTRONIC CIRCUITRY
- H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
- H03M13/00—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes
- H03M13/03—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words
- H03M13/05—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words using block codes, i.e. a predetermined number of check bits joined to a predetermined number of information bits
- H03M13/13—Linear codes
- H03M13/15—Cyclic codes, i.e. cyclic shifts of codewords produce other codewords, e.g. codes defined by a generator polynomial, Bose-Chaudhuri-Hocquenghem [BCH] codes
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F11/00—Error detection; Error correction; Monitoring
- G06F11/07—Responding to the occurrence of a fault, e.g. fault tolerance
- G06F11/08—Error detection or correction by redundancy in data representation, e.g. by using checking codes
- G06F11/10—Adding special bits or symbols to the coded information, e.g. parity check, casting out 9's or 11's
-
- H—ELECTRICITY
- H03—ELECTRONIC CIRCUITRY
- H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
- H03M13/00—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes
- H03M13/03—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words
- H03M13/05—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words using block codes, i.e. a predetermined number of check bits joined to a predetermined number of information bits
- H03M13/13—Linear codes
- H03M13/15—Cyclic codes, i.e. cyclic shifts of codewords produce other codewords, e.g. codes defined by a generator polynomial, Bose-Chaudhuri-Hocquenghem [BCH] codes
- H03M13/151—Cyclic codes, i.e. cyclic shifts of codewords produce other codewords, e.g. codes defined by a generator polynomial, Bose-Chaudhuri-Hocquenghem [BCH] codes using error location or error correction polynomials
Landscapes
- Engineering & Computer Science (AREA)
- Physics & Mathematics (AREA)
- Theoretical Computer Science (AREA)
- General Physics & Mathematics (AREA)
- Mathematical Physics (AREA)
- Algebra (AREA)
- Pure & Applied Mathematics (AREA)
- Probability & Statistics with Applications (AREA)
- Quality & Reliability (AREA)
- General Engineering & Computer Science (AREA)
- Error Detection And Correction (AREA)
- Detection And Correction Of Errors (AREA)
Abstract
(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。
め要約のデータは記録されません。
Description
【０００１】
【産業上の利用分野】本発明は、ディジタルデータを保
護するためのエラー訂正技術に関するもので、特に２ワ
ードエラーまで訂正可能なエラー訂正符号によりエラー
を訂正することのできる方法及び装置に関する。
護するためのエラー訂正技術に関するもので、特に２ワ
ードエラーまで訂正可能なエラー訂正符号によりエラー
を訂正することのできる方法及び装置に関する。
【０００２】
【従来の技術】一般に、エラー訂正装置は、ディジタル
通信システムやディジタル貯蔵システムに適用され、受
信又は再生されるデータ中に発生されたエラーを訂正す
るようにする。
通信システムやディジタル貯蔵システムに適用され、受
信又は再生されるデータ中に発生されたエラーを訂正す
るようにする。
【０００３】従来のエラー訂正技術の例を挙げれば、１
９８２年２月９日、日本国のソニー社による特開昭５７
−２５０４７号がある。この発明によれば、ｍビットよ
りなるｎワードを有する１ブロックデータで２ワードエ
ラーまで訂正できる方法が開示されている。これを詳細
に説明すれば次の通りである。
９８２年２月９日、日本国のソニー社による特開昭５７
−２５０４７号がある。この発明によれば、ｍビットよ
りなるｎワードを有する１ブロックデータで２ワードエ
ラーまで訂正できる方法が開示されている。これを詳細
に説明すれば次の通りである。
【０００４】受信されたｎワードとパリティーチェック
行列Ｈよりなる１ブロックデータＶＴ の下の演算によ
りＫ 個のシンドロームＳ０、Ｓ１ ・・・Ｓｋ−１
を求める。
行列Ｈよりなる１ブロックデータＶＴ の下の演算によ
りＫ 個のシンドロームＳ０、Ｓ１ ・・・Ｓｋ−１
を求める。
【０００５】
【数３】
【０００６】ここで、パリティーチェック行列Ｈはｎ列
及びＫ行を有する一定行の各要素は、α０（＝１） 〜
α２ｍ−２で選択され、要素αはＦ（Ｘ） ＝０を満た
す平方根であり、従って、同一値は前記所定行内に二度
ど現れず、その他の行の要素は各行内のすべの要素に対
して所定行内の対応要素の累乗で選択されるようになっ
ている。
及びＫ行を有する一定行の各要素は、α０（＝１） 〜
α２ｍ−２で選択され、要素αはＦ（Ｘ） ＝０を満た
す平方根であり、従って、同一値は前記所定行内に二度
ど現れず、その他の行の要素は各行内のすべの要素に対
して所定行内の対応要素の累乗で選択されるようになっ
ている。
【０００７】このパリティーチェック行列Ｈを表現すれ
ば、
ば、
【０００８】
【数４】
【０００９】のようになる。
【００１０】２重エラーｅｉ，ｅｊの場合のシンドロー
ムＳ０ 、Ｓ１ 、Ｓ２ 、Ｓ３ に関する式は次の通
りである。
ムＳ０ 、Ｓ１ 、Ｓ２ 、Ｓ３ に関する式は次の通
りである。
【００１１】Ｓ０ ＝ｅｉ＋ｅｊ
Ｓ１ ＝αｉｅｉ＋αｊｅｊ
Ｓ２ ＝α２ｉｅｉ＋α２ｊｅｊ
Ｓ３ ＝α３ｉｅｉ＋α３ｊｅｊ
この式を変形すれば下の通りである。
【００１２】
（αｉＳ０＋Ｓ１）（αｉＳ２＋Ｓ３）＝（αｉＳ１＋
Ｓ２）２再び変形させて下記のエラー位置多項式を求め
る。
Ｓ２）２再び変形させて下記のエラー位置多項式を求め
る。
【００１３】（Ｓ０Ｓ２＋Ｓ１２）α２ｉ＋（Ｓ１Ｓ２
＋Ｓ０Ｓ３）αｉ＋（Ｓ１Ｓ３＋Ｓ２２）＝０ ここで、前記各多項式の係数を下のように仮定する。
＋Ｓ０Ｓ３）αｉ＋（Ｓ１Ｓ３＋Ｓ２２）＝０ ここで、前記各多項式の係数を下のように仮定する。
【００１４】Ｓ０Ｓ２＋Ｓ１２＝Ａ
Ｓ１Ｓ２＋Ｓ０Ｓ３＝Ｂ
Ｓ１Ｓ３＋Ｓ２＝Ｃ
上記の多項式の各係数Ａ，Ｂ，Ｃを用いて２ワードエラ
ーの場合のエラー位置を下のように求める。
ーの場合のエラー位置を下のように求める。
【００１５】〔１〕エラーのない場合：Ａ＝Ｂ＝Ｃ＝０
、Ｓ０＝０、Ｓ３＝０ 〔２〕１ワードエラーの場合： Ａ＝Ｂ＝Ｃ＝０、Ｓ０≠０、Ｓ３≠０のとき、１ワード
エラーより判定される。
、Ｓ０＝０、Ｓ３＝０ 〔２〕１ワードエラーの場合： Ａ＝Ｂ＝Ｃ＝０、Ｓ０≠０、Ｓ３≠０のとき、１ワード
エラーより判定される。
【００１６】この場合、エラー位置ｉは下の演算により
求められ、 αｉ＝Ｓ１／Ｓ０ また、エラー形態ｅｉ＝Ｓ０を用いてエラー訂正がなさ
れる。
求められ、 αｉ＝Ｓ１／Ｓ０ また、エラー形態ｅｉ＝Ｓ０を用いてエラー訂正がなさ
れる。
【００１７】〔３〕２ワードエラーの場合：２ワード以
上のエラーの場合はＡ≠０、Ｂ≠０、Ｃ≠０が成立し、
この際、下の関係が成立する。
上のエラーの場合はＡ≠０、Ｂ≠０、Ｃ≠０が成立し、
この際、下の関係が成立する。
【００１８】Ａα２ｉ＋Ｂαｉ＋Ｃ＝０ ｛ｉ＝０〜
（ｎ−１）｝ ここでＢ／Ａ＝Ｄ、Ｃ／Ａ＝Ｅと仮定して下のような式
を求める。
（ｎ−１）｝ ここでＢ／Ａ＝Ｄ、Ｃ／Ａ＝Ｅと仮定して下のような式
を求める。
【００１９】Ｄ＝αｉ＋αｊ
Ｅ＝αｉ・αｊ
また、上記係数Ｄ，Ｅにより表現される変形されたエラ
ー位置多項式は次のようになる。
ー位置多項式は次のようになる。
【００２０】α２ｉ＋Ｄαｉ＋Ｅ＝０
ここで、２つのエラー位置の差がｔ、すなわち、ｊ＝ｉ
＋ｔの場合、下記のような式が求められる。
＋ｔの場合、下記のような式が求められる。
【００２１】Ｄ＝αｉ（１＋αｔ ）
Ｅ＝α２ｉ＋ｔ
従って、下記の式が導出される。
【００２２】Ｄ２ ／Ｅ＝（１＋αｔ）２／αｔ ＝α
−ｔ＋αｔ ｔ＝１〜（ｎ−１）の各値のα−ｔ＋αｔ の値をＲＯ
Ｍに予め書き込んでおき、ＲＯＭの出力と受信ワードか
ら演算されたＤ２ ／Ｅの値との一致を検出することで
ｔが求められる。もし、この一致関係が成立しなければ
、３ワード以上のエラーと判定する。
−ｔ＋αｔ ｔ＝１〜（ｎ−１）の各値のα−ｔ＋αｔ の値をＲＯ
Ｍに予め書き込んでおき、ＲＯＭの出力と受信ワードか
ら演算されたＤ２ ／Ｅの値との一致を検出することで
ｔが求められる。もし、この一致関係が成立しなければ
、３ワード以上のエラーと判定する。
【００２３】従って、次のように仮定する。
【００２４】Ｘ＝１＋αｔ
Ｙ＝１＋α−ｔ＝Ｄ２ ／Ｅ＋ｘ
下記の式からエラー位置ｉ及びｊを求める。
【００２５】αｉ＝Ｄ／Ｘ
αｊ＝Ｄ／Ｙ
次にはエラー形態ｅｉ及びｅｊが下のように表現される
式が求められる。
式が求められる。
【００２６】
ｅｉ＝（αｉＳ０＋Ｓ１）／Ｄ＝Ｓ０／Ｙ ＋Ｓ１／Ｄ
ｅｊ＝（αｉＳ０＋Ｓ１）／Ｄ＝Ｓ０／Ｘ ＋Ｓ１／Ｄ
こうしてエラー位置及びエラー形態を求めた後、当該エ
ラー位置に受信ワードのエラーを上記エラー形態により
訂正できる。
ｅｊ＝（αｉＳ０＋Ｓ１）／Ｄ＝Ｓ０／Ｘ ＋Ｓ１／Ｄ
こうしてエラー位置及びエラー形態を求めた後、当該エ
ラー位置に受信ワードのエラーを上記エラー形態により
訂正できる。
【００２７】
【発明が解決しようとする課題】しかし、特開昭５７−
２５０４７号公報に記載された方法は、エラー位置を求
めるためにエラー位置多項式（α２ｉ＋Ｄαｉ＋Ｅ＝０
）を解いて二根であるαｉ及びαｊ を求めた後、演算
されたエラー位置多項式の二根αｉ 及びαｊ からα
ｉ 及びαｊ を求めるものであるため、演算に要する
回路が複雑で、演算に要する時間による遅延時間が大き
かった。
２５０４７号公報に記載された方法は、エラー位置を求
めるためにエラー位置多項式（α２ｉ＋Ｄαｉ＋Ｅ＝０
）を解いて二根であるαｉ及びαｊ を求めた後、演算
されたエラー位置多項式の二根αｉ 及びαｊ からα
ｉ 及びαｊ を求めるものであるため、演算に要する
回路が複雑で、演算に要する時間による遅延時間が大き
かった。
【００２８】従って、本発明の目的はエラー位置多項式
を計算する過程なしにエラー値が求められるエラー訂正
方法を提供することである。
を計算する過程なしにエラー値が求められるエラー訂正
方法を提供することである。
【００２９】本発明の他の目的は、遅延時間が少なく回
路が簡単なエラー訂正装置を提供することである。
路が簡単なエラー訂正装置を提供することである。
【００３０】
【課題を解決するための手段】本発明の目的を達成する
ために、本発明のエラー訂正方法は受信ｎワード及びパ
リティーチェック行列Ｈよりなる１ブロックデータＶＴ
の下の演算によって４個のシンドロームＳ０ 、Ｓ１
、Ｓ２ 、Ｓ３ を求めるステップと、
ために、本発明のエラー訂正方法は受信ｎワード及びパ
リティーチェック行列Ｈよりなる１ブロックデータＶＴ
の下の演算によって４個のシンドロームＳ０ 、Ｓ１
、Ｓ２ 、Ｓ３ を求めるステップと、
【００３１】
【数５】
【００３２】前記シンドロームＳ０ 、Ｓ１ 、Ｓ２
、Ｓ３ がＳ０ ＝Ｓ１ ＝Ｓ２ ＝Ｓ３ ＝０の場合
、エラーのないと判断するステップと、前記シンドロー
ムＳ０ 、Ｓ１ 、Ｓ２ 、Ｓ３ からＤ＝Ｓ０Ｓ２
＋Ｓ１２ を計算し、Ｄ＝０であるかを判断するステッ
プと、前記Ｄ≠０の場合、下記の係数σ１、σ２を計算
するステップと、σ１＝（Ｓ０Ｓ３＋Ｓ１Ｓ２）／Ｄ σ２＝（Ｓ１Ｓ３＋Ｓ１Ｓ２２）／Ｄ 前記係数σ１≠０、σ２≠０の場合、下の係数Ｋ 値と
Ｔｒ（Ｋ） 値を求めるステップと、 Ｋ ＝σ２／σ１２ ＝Ｋ０＋Ｋ１α＋Ｋ２α２＋Ｋ３α３＋Ｋ４α４＋Ｋ５
α５＋Ｋ６α６＋Ｋ７α７ Ｔｒ（Ｋ） ＝Ｋ０Ｔｒ（１）＋Ｋ１Ｔｒ（α） ＋Ｋ
２Ｔｒ（α２）＋Ｋ３Ｔｒ（α３）＋Ｋ４Ｔｒ（α４）
＋Ｋ５Ｔｒ（α５）＋Ｋ６Ｔｒ（α６）＋Ｋ７Ｔｒ（α
７） 前記係数Ｋ から下のエラー位置Ｘ１ 、Ｘ２ を求め
るステップと、 Ｘ１ ＝Ｘ１・σ１ Ｘ２ ＝（１＋Ｘ１）・σ１ ここで、Ｔｒ（α５）＝１から、
、Ｓ３ がＳ０ ＝Ｓ１ ＝Ｓ２ ＝Ｓ３ ＝０の場合
、エラーのないと判断するステップと、前記シンドロー
ムＳ０ 、Ｓ１ 、Ｓ２ 、Ｓ３ からＤ＝Ｓ０Ｓ２
＋Ｓ１２ を計算し、Ｄ＝０であるかを判断するステッ
プと、前記Ｄ≠０の場合、下記の係数σ１、σ２を計算
するステップと、σ１＝（Ｓ０Ｓ３＋Ｓ１Ｓ２）／Ｄ σ２＝（Ｓ１Ｓ３＋Ｓ１Ｓ２２）／Ｄ 前記係数σ１≠０、σ２≠０の場合、下の係数Ｋ 値と
Ｔｒ（Ｋ） 値を求めるステップと、 Ｋ ＝σ２／σ１２ ＝Ｋ０＋Ｋ１α＋Ｋ２α２＋Ｋ３α３＋Ｋ４α４＋Ｋ５
α５＋Ｋ６α６＋Ｋ７α７ Ｔｒ（Ｋ） ＝Ｋ０Ｔｒ（１）＋Ｋ１Ｔｒ（α） ＋Ｋ
２Ｔｒ（α２）＋Ｋ３Ｔｒ（α３）＋Ｋ４Ｔｒ（α４）
＋Ｋ５Ｔｒ（α５）＋Ｋ６Ｔｒ（α６）＋Ｋ７Ｔｒ（α
７） 前記係数Ｋ から下のエラー位置Ｘ１ 、Ｘ２ を求め
るステップと、 Ｘ１ ＝Ｘ１・σ１ Ｘ２ ＝（１＋Ｘ１）・σ１ ここで、Ｔｒ（α５）＝１から、
【００３３】
【数６】
【００３４】前記エラー位置Ｘ１、Ｘ２から次のエラー
値Ｙ１、Ｙ２を求めるステップと、 Ｙ１＝（Ｓ０Ｘ２＋Ｓ１）／（Ｘ１＋Ｘ２）Ｙ２＝（Ｓ
０Ｘ１＋Ｓ１）／（Ｘ１＋Ｘ２）よりなっている Ｋ∈
ＧＦ（２８）の場合に二つのエラーを訂正することを特
徴とする。本発明の他の目的を達成するために、本発明
のエラー訂正装置は、受信ｎワードからシンドロームＳ
０ 、Ｓ１ 、Ｓ２ 、Ｓ３ を計算するシンドローム
演算部と、前記シンドロームから次の係数σ１、σ２を
計算する第１係数演算部と、 σ１＝（Ｓ０Ｓ３＋Ｓ１Ｓ２）／Ｄ σ２＝（Ｓ１Ｓ３＋Ｓ２２）／Ｄ 前記係数σ１、σ２から次の係数Ｋ を計算する第２係
数演算部と、 Ｋ ＝σ２／σ１２ 前記係数Ｋ からＸ１値を演算するＸ１値演算部と、前
記Ｘ１値から次のエラー位置Ｘ１、Ｘ２を計算するエラ
ー位置値演算部と、 Ｘ１＝Ｘ１・σ１ Ｘ２＝（１＋Ｘ１）・σ１ 前記エラー位置Ｘ１、Ｘ２値を入力して次のエラー値Ｙ
１、Ｙ２を計算するエラー値演算部及び Ｙ１＝（Ｓ０Ｘ２＋Ｓ１）／（Ｘ１＋Ｘ２）Ｙ２＝（Ｓ
０Ｘ１＋Ｓ１）／（Ｘ１＋Ｘ２）エラーが何個発生した
か否かを判定するためのエラー判別部を具備したエラー
訂正装置において、前記Ｘ１値演算部は次の式 ｘ０ ＝Ｋ３＋Ｋ５＋Ｋ６ ｘ１ ＝Ｋ０＋Ｋ２＋Ｋ４ ｘ２ ＝Ｋ０＋Ｋ３＋Ｋ４＋Ｋ６ ｘ３ ＝Ｋ１＋Ｋ２＋Ｋ３＋Ｋ４ ｘ４ ＝Ｋ０＋Ｋ７ ｘ５ ＝Ｋ１＋Ｋ２＋Ｋ３＋Ｋ４＋Ｋ６ｘ６ ＝Ｋ０＋
Ｋ１＋Ｋ２＋Ｋ４＋Ｋ７ｘ７ ＝Ｋ０＋Ｋ１＋Ｋ２＋Ｋ
４ を満たすＥＸＯＲ論理ゲートを用いて構成したことを特
徴とする。
値Ｙ１、Ｙ２を求めるステップと、 Ｙ１＝（Ｓ０Ｘ２＋Ｓ１）／（Ｘ１＋Ｘ２）Ｙ２＝（Ｓ
０Ｘ１＋Ｓ１）／（Ｘ１＋Ｘ２）よりなっている Ｋ∈
ＧＦ（２８）の場合に二つのエラーを訂正することを特
徴とする。本発明の他の目的を達成するために、本発明
のエラー訂正装置は、受信ｎワードからシンドロームＳ
０ 、Ｓ１ 、Ｓ２ 、Ｓ３ を計算するシンドローム
演算部と、前記シンドロームから次の係数σ１、σ２を
計算する第１係数演算部と、 σ１＝（Ｓ０Ｓ３＋Ｓ１Ｓ２）／Ｄ σ２＝（Ｓ１Ｓ３＋Ｓ２２）／Ｄ 前記係数σ１、σ２から次の係数Ｋ を計算する第２係
数演算部と、 Ｋ ＝σ２／σ１２ 前記係数Ｋ からＸ１値を演算するＸ１値演算部と、前
記Ｘ１値から次のエラー位置Ｘ１、Ｘ２を計算するエラ
ー位置値演算部と、 Ｘ１＝Ｘ１・σ１ Ｘ２＝（１＋Ｘ１）・σ１ 前記エラー位置Ｘ１、Ｘ２値を入力して次のエラー値Ｙ
１、Ｙ２を計算するエラー値演算部及び Ｙ１＝（Ｓ０Ｘ２＋Ｓ１）／（Ｘ１＋Ｘ２）Ｙ２＝（Ｓ
０Ｘ１＋Ｓ１）／（Ｘ１＋Ｘ２）エラーが何個発生した
か否かを判定するためのエラー判別部を具備したエラー
訂正装置において、前記Ｘ１値演算部は次の式 ｘ０ ＝Ｋ３＋Ｋ５＋Ｋ６ ｘ１ ＝Ｋ０＋Ｋ２＋Ｋ４ ｘ２ ＝Ｋ０＋Ｋ３＋Ｋ４＋Ｋ６ ｘ３ ＝Ｋ１＋Ｋ２＋Ｋ３＋Ｋ４ ｘ４ ＝Ｋ０＋Ｋ７ ｘ５ ＝Ｋ１＋Ｋ２＋Ｋ３＋Ｋ４＋Ｋ６ｘ６ ＝Ｋ０＋
Ｋ１＋Ｋ２＋Ｋ４＋Ｋ７ｘ７ ＝Ｋ０＋Ｋ１＋Ｋ２＋Ｋ
４ を満たすＥＸＯＲ論理ゲートを用いて構成したことを特
徴とする。
【００３５】
【作用】本発明によるＧＦ（２８）上の二重エラー訂正
に用いられる方法と装置は、第２係数値演算部からの値
を入力して図１に図示されたＥＸＯＲゲートを用いてデ
ータを出力する。
に用いられる方法と装置は、第２係数値演算部からの値
を入力して図１に図示されたＥＸＯＲゲートを用いてデ
ータを出力する。
【００３６】
【実施例】以下、添付した図面を参照して本発明を詳細
に説明する。
に説明する。
【００３７】まず、本発明に使われたエラー訂正符号に
対して説明する。
対して説明する。
【００３８】θ＝λ−λｑ になる一要素λ〔λ∈ＧＦ
（ｑｍ）〕が存するとすれば次の命題、
（ｑｍ）〕が存するとすれば次の命題、
【００３９】
【数７】
【００４０】から、Ｔｒ（θ）＝０になる。
【００４１】もし、γ∈ＧＦ（ｑｍ）であり、θ∈ＧＦ
（ｑｍ）とすれば、
（ｑｍ）とすれば、
【００４２】
【数８】
【００４３】になる。
【００４４】従って、Ｔｒ（γ）＝１になるＧＦ（ｑｍ
）の一要素を選択するとき、Ｔｒ（θ）＝０になれば式
（１）で定義された要素λは式（２）によりθ＝λ−λ
ｑ を満たす。そこで、エラー位置多項式σ（ｘ）＝ｘ
２＋ｘ＋Ｋ からｘ２＋ｘ＝Ｋ を類推し、ｘは命題か
らＴｒ（θ）＝０の場合のみエラー位置多項式σ（ｘ）
の根が求められ、そのときのｘ値は式（１）のように
表現し得る。
）の一要素を選択するとき、Ｔｒ（θ）＝０になれば式
（１）で定義された要素λは式（２）によりθ＝λ−λ
ｑ を満たす。そこで、エラー位置多項式σ（ｘ）＝ｘ
２＋ｘ＋Ｋ からｘ２＋ｘ＝Ｋ を類推し、ｘは命題か
らＴｒ（θ）＝０の場合のみエラー位置多項式σ（ｘ）
の根が求められ、そのときのｘ値は式（１）のように
表現し得る。
【００４５】また、Ｋ ＝Ｋ０＋Ｋ１α＋Ｋ２α２ ＋
Ｋ３α３ ＋Ｋ４α４ ＋Ｋ５α５ ＋Ｋ６α６ ＋Ｋ
７α７ と表現でき、ここで、 Ｋ∈ＧＦ（２ｍ）両辺
にトレースを取って値を求めれば、Ｔｒ（Ｋ） ＝Ｋ０
Ｔｒ（１） ＋Ｋ１Ｔｒ（α）＋Ｋ２Ｔｒ（α２）＋Ｋ
３Ｔｒ（α３）＋Ｋ４Ｔｒ（α４）＋Ｋ５Ｔｒ（α５）
＋Ｋ６Ｔｒ（α６）＋Ｋ７Ｔｒ（α７）・・（３） 上記命題からＴｒ（β）＝Σβｑ ，β∈ＧＦ（ｑｍ）
により式（３）の右辺のトレース値を求めれば、Ｔｒ（
１） ＝Ｔｒ（α）＝Ｔｒ（α２）＝Ｔｒ（α３）＝Ｔ
ｒ（α４）＝Ｔｒ（α６）＝Ｔｒ（α７）＝０，Ｔｒ（
α５）＝１になる。
Ｋ３α３ ＋Ｋ４α４ ＋Ｋ５α５ ＋Ｋ６α６ ＋Ｋ
７α７ と表現でき、ここで、 Ｋ∈ＧＦ（２ｍ）両辺
にトレースを取って値を求めれば、Ｔｒ（Ｋ） ＝Ｋ０
Ｔｒ（１） ＋Ｋ１Ｔｒ（α）＋Ｋ２Ｔｒ（α２）＋Ｋ
３Ｔｒ（α３）＋Ｋ４Ｔｒ（α４）＋Ｋ５Ｔｒ（α５）
＋Ｋ６Ｔｒ（α６）＋Ｋ７Ｔｒ（α７）・・（３） 上記命題からＴｒ（β）＝Σβｑ ，β∈ＧＦ（ｑｍ）
により式（３）の右辺のトレース値を求めれば、Ｔｒ（
１） ＝Ｔｒ（α）＝Ｔｒ（α２）＝Ｔｒ（α３）＝Ｔ
ｒ（α４）＝Ｔｒ（α６）＝Ｔｒ（α７）＝０，Ｔｒ（
α５）＝１になる。
【００４６】結局、Ｋ２の値が“０”の場合のみＴｒ（
Ｋ） ＝０になってエラー位置多項式σ（ｘ）の根が存
する。 すなわち、命題によりＴｒ（Ｋ） ＝０になればｘ２
＋ｘ＝Ｋ を満たすＧＦ（ｑｍ）上のｘ値が存する。
Ｋ） ＝０になってエラー位置多項式σ（ｘ）の根が存
する。 すなわち、命題によりＴｒ（Ｋ） ＝０になればｘ２
＋ｘ＝Ｋ を満たすＧＦ（ｑｍ）上のｘ値が存する。
【００４７】ここで、 Ｋ∈ＧＦ（２８）の場合、Ｔｒ
（Ｋ）＝Ｋ５＝０であれば次のような方法で根を求める
。
（Ｋ）＝Ｋ５＝０であれば次のような方法で根を求める
。
【００４８】ｉ）Ｔｒ（Ｋ） ＝１である要素γを選択
する。
する。
【００４９】
【数９】
【００５０】になるので、γ＝α５ になる。
【００５１】ｉｉ）Ｔｒ（Ｋ） ＝０の場合、ｘを式（
１）のように求めれば、 ｘ＝θγ２＋（θ＋θ２）γ４＋（θ＋θ２＋θ４）γ
８＋（θ＋θ２＋θ４＋θ８）γ１６＋（θ＋θ２＋θ
４＋θ８ ＋θ１６）γ３２ ＋（θ＋θ２＋θ４＋θ８＋θ１６＋θ３２）γ６４＋
（θ＋θ２＋θ４＋θ８＋θ１６＋θ３２＋θ６４）γ
１２８ ・・・（４） 式（４）をθに関して再び整理すれば、ｘ＝（γ２＋γ
４＋γ８＋γ１６＋γ３２＋γ６４＋γ１２８）θ＋（
γ４＋γ８＋γ１６＋γ３２＋γ６４＋γ１２８）θ２
＋（γ８＋γ１６＋γ３２＋γ６４＋γ１２８）θ４
＋（γ１６＋γ３２＋γ６４＋γ１２８）θ８ ＋（γ
３２＋γ６４＋γ１２８）θ１６＋（γ６４＋γ１２８
）θ３２＋γ１２８θ６４
・・・（５） になる。
１）のように求めれば、 ｘ＝θγ２＋（θ＋θ２）γ４＋（θ＋θ２＋θ４）γ
８＋（θ＋θ２＋θ４＋θ８）γ１６＋（θ＋θ２＋θ
４＋θ８ ＋θ１６）γ３２ ＋（θ＋θ２＋θ４＋θ８＋θ１６＋θ３２）γ６４＋
（θ＋θ２＋θ４＋θ８＋θ１６＋θ３２＋θ６４）γ
１２８ ・・・（４） 式（４）をθに関して再び整理すれば、ｘ＝（γ２＋γ
４＋γ８＋γ１６＋γ３２＋γ６４＋γ１２８）θ＋（
γ４＋γ８＋γ１６＋γ３２＋γ６４＋γ１２８）θ２
＋（γ８＋γ１６＋γ３２＋γ６４＋γ１２８）θ４
＋（γ１６＋γ３２＋γ６４＋γ１２８）θ８ ＋（γ
３２＋γ６４＋γ１２８）θ１６＋（γ６４＋γ１２８
）θ３２＋γ１２８θ６４
・・・（５） になる。
【００５２】ｉｉｉ）γ＝α５ を式（５）に代入して
各係数を求めれば、 ｘ＝（１＋α５）θ＋（１＋α２＋α４＋α６）θ２＋
（１＋α５＋α６＋α７）θ３＋ （１＋α＋α３＋α７）θ４＋（α＋α２＋α４＋α５
＋α６）θ５＋ （α４＋α７）θ３２＋（α＋α２＋α３＋α５）θ６
４ ・・・（６） になる。
各係数を求めれば、 ｘ＝（１＋α５）θ＋（１＋α２＋α４＋α６）θ２＋
（１＋α５＋α６＋α７）θ３＋ （１＋α＋α３＋α７）θ４＋（α＋α２＋α４＋α５
＋α６）θ５＋ （α４＋α７）θ３２＋（α＋α２＋α３＋α５）θ６
４ ・・・（６） になる。
【００５３】ｉｖ）θ＝１〜α７ の各場合のｘ値を求
めれば、 １）θ＝１； ｘ＝α＋α２＋α４＋α６＋α７＝（０１１０１０１１
）２）θ＝α； ｘ＝α３＋α５＋α６＋α７＝（０００１０１１１）３
）θ＝α２； ｘ＝α＋α３＋α５＋α６＋α７＝（０１０１０１１１
）４）θ＝α３； ｘ＝１＋α２＋α３＋α５＝（１０１１０１００）５）
θ＝α４； ｘ＝α＋α２＋α３＋α５＋α６＋α７＝（０１１１０
１１１） ６）θ＝α５； ｘ＝１＝（１０００００００） ７）θ＝α６； ｘ＝１＋α２＋α５＝（１０１００１００）８）θ＝α
７； ｘ＝α４＋α６＝（００００１０１０）ｖ）Ｋ ＝σ２
／σ１２＝（Ｋ０、Ｋ１、Ｋ２、Ｋ３、Ｋ４、Ｋ５、Ｋ
６、Ｋ７） ・・・（７） が与えられると、ｉｖ）から求められた行列式から、
めれば、 １）θ＝１； ｘ＝α＋α２＋α４＋α６＋α７＝（０１１０１０１１
）２）θ＝α； ｘ＝α３＋α５＋α６＋α７＝（０００１０１１１）３
）θ＝α２； ｘ＝α＋α３＋α５＋α６＋α７＝（０１０１０１１１
）４）θ＝α３； ｘ＝１＋α２＋α３＋α５＝（１０１１０１００）５）
θ＝α４； ｘ＝α＋α２＋α３＋α５＋α６＋α７＝（０１１１０
１１１） ６）θ＝α５； ｘ＝１＝（１０００００００） ７）θ＝α６； ｘ＝１＋α２＋α５＝（１０１００１００）８）θ＝α
７； ｘ＝α４＋α６＝（００００１０１０）ｖ）Ｋ ＝σ２
／σ１２＝（Ｋ０、Ｋ１、Ｋ２、Ｋ３、Ｋ４、Ｋ５、Ｋ
６、Ｋ７） ・・・（７） が与えられると、ｉｖ）から求められた行列式から、
【
００５４】
００５４】
【数１０】
【００５５】になる。
【００５６】上記式（６）をｘ１＝ Ｋ×Ｍと再び表現
するとき ｘ１＝（ｘ０、ｘ１、ｘ２、ｘ３、ｘ４、ｘ５、ｘ６、
ｘ７） Ｋ ＝（Ｋ０ 、Ｋ１ 、Ｋ２ 、Ｋ３ 、Ｋ
４ 、Ｋ５ 、Ｋ６ 、Ｋ７）
するとき ｘ１＝（ｘ０、ｘ１、ｘ２、ｘ３、ｘ４、ｘ５、ｘ６、
ｘ７） Ｋ ＝（Ｋ０ 、Ｋ１ 、Ｋ２ 、Ｋ３ 、Ｋ
４ 、Ｋ５ 、Ｋ６ 、Ｋ７）
【００５７】
【数１１】
【００５８】こうしてｘ２ ＋ｘ＝Ｋ の一根であるＸ
１ が求められる。
１ が求められる。
【００５９】このとき、Ｘ１ の各成分要素がｘ０ 〜
ｘ７ の値は式（８）から、
ｘ７ の値は式（８）から、
【００６０】
【数１２】
【００６１】になる。
【００６２】ここで、Ｋ５は前述したＴｒ（Ｋ） ＝Ｋ
５＝０のために”０”になるべきである。
５＝０のために”０”になるべきである。
【００６３】また、他の一根Ｘ２＝Ｘ１＋１で求められ
る。
る。
【００６４】ところで、実際のエラー位置はＸ１ 、Ｘ
２ のそれぞれにσ１ を掛けるべきなので、
２ のそれぞれにσ１ を掛けるべきなので、
【００６
５】
５】
【数１３】
【００６６】ここで、σ１ ＝Ｓ０Ｓ３＋Ｓ１Ｓ２／Ｓ
０Ｓ２＋Ｓ１２ になる。
０Ｓ２＋Ｓ１２ になる。
【００６７】また、エラー値ｙ１ 、ｙ２ は、
【００
６８】
６８】
【数１４】
【００６９】で決定される。
【００７０】図１は上記式（９）をＥＸＯＲゲートに用
いて構成したものを示した。
いて構成したものを示した。
【００７１】また、上記式（７）は二重エラー位置多項
式σ（ｘ）＝ｘ２＋σ１ｘ＋σ２ からｘ＝σ１ｘ’と
置き換えれば、 σ（ｘ’）＝ｘ’２＋ｘ’＋Ｋ ここで、Ｋ ＝σ２／σ１２ が求められる。
式σ（ｘ）＝ｘ２＋σ１ｘ＋σ２ からｘ＝σ１ｘ’と
置き換えれば、 σ（ｘ’）＝ｘ’２＋ｘ’＋Ｋ ここで、Ｋ ＝σ２／σ１２ が求められる。
【００７２】図２は本発明による実施例のエラー訂正装
置のブロック図である。
置のブロック図である。
【００７３】同図において、入力端子１０５は受信デー
タを流入するための入力通路を表示する。入力端子１０
５は緩衝記憶装置１００の入力端子及びシンドローム演
算部１２０の入力端子と結合されている。緩衝記憶装置
１００の出力端子は第１加算器１１０の第１入力端子に
接続されている。シンドローム演算部１２０の出力端子
はエラー値演算部１８０の第３入力端子、第１係数演算
部１３０の入力端子及びエラー判別部１６０の第１入力
端子と結合されている。
タを流入するための入力通路を表示する。入力端子１０
５は緩衝記憶装置１００の入力端子及びシンドローム演
算部１２０の入力端子と結合されている。緩衝記憶装置
１００の出力端子は第１加算器１１０の第１入力端子に
接続されている。シンドローム演算部１２０の出力端子
はエラー値演算部１８０の第３入力端子、第１係数演算
部１３０の入力端子及びエラー判別部１６０の第１入力
端子と結合されている。
【００７４】第１係数演算部１３０の第１出力端子は第
２係数演算部１４０の入力端子、第１加算器１１０の第
１入力端子及び第２乗算器１７１の第１入力端子と結合
されている。第１係数演算部１３０の第２出力端子はエ
ラー判別部１６０の第２入力端子に接続されている。第
２係数演算部１４０の第２出力端子は、エラー判別部１
６０の第３入力端子に接続されている。エラー判別部１
６０の出力端子は制御部１９０の第１入力端子に接続さ
れている。エラー位置演算部１５０の出力端子は第２加
算器１１１の第１入力端子及び第１乗算器１７０の第２
入力端子と結合されている。
２係数演算部１４０の入力端子、第１加算器１１０の第
１入力端子及び第２乗算器１７１の第１入力端子と結合
されている。第１係数演算部１３０の第２出力端子はエ
ラー判別部１６０の第２入力端子に接続されている。第
２係数演算部１４０の第２出力端子は、エラー判別部１
６０の第３入力端子に接続されている。エラー判別部１
６０の出力端子は制御部１９０の第１入力端子に接続さ
れている。エラー位置演算部１５０の出力端子は第２加
算器１１１の第１入力端子及び第１乗算器１７０の第２
入力端子と結合されている。
【００７５】第２加算器１１１の出力端子は第２乗算器
１７１の第２入力端子に接続されている。第１乗算器１
７０の出力端子はエラー値演算部１８０の第２入力端子
及び制御部１９０の第２入力端子と結合されている。第
２乗算器１７１の出力端子はエラー値演算部１８０の第
３入力端子及び制御部１９０の第３入力端子と結合され
ている。エラー値演算部１８０の出力端子は緩衝記録器
１０１の入力端子に接続されている。緩衝記録器１０１
の出力端子は第１加算器１１０の第２入力端子に接続さ
れている。
１７１の第２入力端子に接続されている。第１乗算器１
７０の出力端子はエラー値演算部１８０の第２入力端子
及び制御部１９０の第２入力端子と結合されている。第
２乗算器１７１の出力端子はエラー値演算部１８０の第
３入力端子及び制御部１９０の第３入力端子と結合され
ている。エラー値演算部１８０の出力端子は緩衝記録器
１０１の入力端子に接続されている。緩衝記録器１０１
の出力端子は第１加算器１１０の第２入力端子に接続さ
れている。
【００７６】第１加算器１１０の出力端子は出力端子１
１５に接続されている。制御部１９０の第１ないし第８
出力端子はそれぞれ緩衝記憶装置１００の制御端子、シ
ンドローム演算部１２０の制御端子、第１係数演算部１
３０の制御端子、第２係数演算部１４０の制御端子、エ
ラー位置演算部１５０の制御端子、エラー判別部１６０
の制御端子、エラー値演算部１８０の制御端子及び緩衝
記録器１０１の制御端子にそれぞれ接続されている。
１５に接続されている。制御部１９０の第１ないし第８
出力端子はそれぞれ緩衝記憶装置１００の制御端子、シ
ンドローム演算部１２０の制御端子、第１係数演算部１
３０の制御端子、第２係数演算部１４０の制御端子、エ
ラー位置演算部１５０の制御端子、エラー判別部１６０
の制御端子、エラー値演算部１８０の制御端子及び緩衝
記録器１０１の制御端子にそれぞれ接続されている。
【００７７】図２に図示されたエラー訂正装置の作動を
図１を参照して説明する。
図１を参照して説明する。
【００７８】入力端子１０５を通じて流入される受信デ
ータは緩衝記憶装置１００及びシンドローム演算部１２
０に供給される。
ータは緩衝記憶装置１００及びシンドローム演算部１２
０に供給される。
【００７９】緩衝記憶装置１００は入力端子１０５を通
じて流入される受信データをシンドローム演算部１２０
、第１，第２係数演算部１３０，１４０、エラー位置演
算部１５０、第２換算器１１１、第１，第２乗算器１７
０，１７１、エラー値演算部１８０及び緩衝記録器１０
１を通過する時間ほど遅延させて第１加算器１１０の第
１入力端子に供給する。
じて流入される受信データをシンドローム演算部１２０
、第１，第２係数演算部１３０，１４０、エラー位置演
算部１５０、第２換算器１１１、第１，第２乗算器１７
０，１７１、エラー値演算部１８０及び緩衝記録器１０
１を通過する時間ほど遅延させて第１加算器１１０の第
１入力端子に供給する。
【００８０】シンドローム演算部１２０は入力端子１０
５を通じて流入される受信データを自体内に内蔵された
記憶素子に順次に貯蔵し、１ブロックに該当する受信デ
ータが入力されたとき、下の演算によりシンドロームＳ
０ 〜Ｓ３ を算出する。
５を通じて流入される受信データを自体内に内蔵された
記憶素子に順次に貯蔵し、１ブロックに該当する受信デ
ータが入力されたとき、下の演算によりシンドロームＳ
０ 〜Ｓ３ を算出する。
【００８１】
【数１５】
【００８２】第１係数演算部１３０は、シンドローム演
算部１２０から流入されるシンドロームＳ０ 〜Ｓ３
の下のような演算によりσ１ 、σ２ 及びＤを算出す
る。
算部１２０から流入されるシンドロームＳ０ 〜Ｓ３
の下のような演算によりσ１ 、σ２ 及びＤを算出す
る。
【００８３】
σ１＝Ｓ０Ｓ３＋Ｓ１Ｓ２／Ｓ１２＋Ｓ０Ｓ２σ２＝Ｓ
１Ｓ３＋Ｓ２２／Ｓ１２＋Ｓ０Ｓ２Ｄ＝Ｓ１２＋Ｓ０Ｓ
２また、第１係数演算部１３０は、二つの係数σ１ 及
びσ２ は第１出力端子を通じて第２係数演算部１４０
及び第１，第２乗算器１７０，１７１に供給し、係数Ｄ
は第２出力端子を通じてエラー判別部１６０に供給する
。ここで、二つの係数σ１ 及びσ２ は、２次エラー
位置多項式σ（ｙ）＝ｙ２ ＋σ１ ｙ＋σ２ ＝０の
係数である。
１Ｓ３＋Ｓ２２／Ｓ１２＋Ｓ０Ｓ２Ｄ＝Ｓ１２＋Ｓ０Ｓ
２また、第１係数演算部１３０は、二つの係数σ１ 及
びσ２ は第１出力端子を通じて第２係数演算部１４０
及び第１，第２乗算器１７０，１７１に供給し、係数Ｄ
は第２出力端子を通じてエラー判別部１６０に供給する
。ここで、二つの係数σ１ 及びσ２ は、２次エラー
位置多項式σ（ｙ）＝ｙ２ ＋σ１ ｙ＋σ２ ＝０の
係数である。
【００８４】第２係数演算部１４０は第１係数演算部１
３０から流入される二つの係数σ１ 及びσ２ の値の
下のような演算により第３係数Ｋ を算出し、Ｋ ＝σ
２／σ１２ 算出された係数Ｋ の値を第１出力端子を
通じてエラー位置演算部１５０の入力端子に供給する。
３０から流入される二つの係数σ１ 及びσ２ の値の
下のような演算により第３係数Ｋ を算出し、Ｋ ＝σ
２／σ１２ 算出された係数Ｋ の値を第１出力端子を
通じてエラー位置演算部１５０の入力端子に供給する。
【００８５】エラー位置演算部１５０は図１に示された
回路により第１エラー位置値Ｘ１を第２加算器１１１及
び第２乗算器１７１に供給する。第２加算器１１１は第
１エラー位置値Ｘ１と１を足して第２エラー位置値Ｘ２
を第１乗算器１７０に供給する。第１乗算器１７０は第
２エラー位置値Ｘ２と第１係数σ１ を掛けてエラー値
演算部１８０に供給する。第２乗算器１７１は第１エラ
ー位置値Ｘ１と第２係数σ２ を掛けてエラー値演算部
１８０に供給する。エラー値演算部１８０は第１エラー
位置値Ｘ１ と第２エラー位置値Ｘ２ をもってエラー
値Ｙ１，Ｙ２を計算する。
回路により第１エラー位置値Ｘ１を第２加算器１１１及
び第２乗算器１７１に供給する。第２加算器１１１は第
１エラー位置値Ｘ１と１を足して第２エラー位置値Ｘ２
を第１乗算器１７０に供給する。第１乗算器１７０は第
２エラー位置値Ｘ２と第１係数σ１ を掛けてエラー値
演算部１８０に供給する。第２乗算器１７１は第１エラ
ー位置値Ｘ１と第２係数σ２ を掛けてエラー値演算部
１８０に供給する。エラー値演算部１８０は第１エラー
位置値Ｘ１ と第２エラー位置値Ｘ２ をもってエラー
値Ｙ１，Ｙ２を計算する。
【００８６】
Ｙ１＝（Ｓ０Ｘ２＋Ｓ１）／（Ｘ１＋Ｘ２）Ｙ２＝（Ｓ
０Ｘ１＋Ｓ１）／（Ｘ１＋Ｘ２）また、エラー値ｙ１
、ｙ２ を緩衝記録器１０１に供給する。
０Ｘ１＋Ｓ１）／（Ｘ１＋Ｘ２）また、エラー値ｙ１
、ｙ２ を緩衝記録器１０１に供給する。
【００８７】緩衝記録器１０１はエラー値演算部１８０
から流入しされる二つのエラー値Ｙ１，Ｙ２を貯蔵した
後、エラーの発生された受信ワードが第１加算器１１０
の第１入力端子に印加されたごろ、エラー値Ｙ１，Ｙ２
を第１加算器１１０の第２入力端子に供給する。
から流入しされる二つのエラー値Ｙ１，Ｙ２を貯蔵した
後、エラーの発生された受信ワードが第１加算器１１０
の第１入力端子に印加されたごろ、エラー値Ｙ１，Ｙ２
を第１加算器１１０の第２入力端子に供給する。
【００８８】第１加算器１１０は緩衝記憶装置１００か
ら第１入力端子に流入される受信データに緩衝記録器１
０１から第２入力端子に流入されるエラー値Ｙ１，Ｙ２
を加算して受信データに発生されたエラーを訂正する。
ら第１入力端子に流入される受信データに緩衝記録器１
０１から第２入力端子に流入されるエラー値Ｙ１，Ｙ２
を加算して受信データに発生されたエラーを訂正する。
【００８９】エラー判別部１６０は、シンドローム演算
部１２０から流入されるシンドロームＳ０ 〜Ｓ３ 、
第１係数演算部１３０から流入される係数Ｄ及び第２係
数演算部１４０から流入される値をチェックしてエラー
発生有無、ワードエラー発生、二重ワードエラー発生及
び三重ワード以上のエラー発生を判別する。
部１２０から流入されるシンドロームＳ０ 〜Ｓ３ 、
第１係数演算部１３０から流入される係数Ｄ及び第２係
数演算部１４０から流入される値をチェックしてエラー
発生有無、ワードエラー発生、二重ワードエラー発生及
び三重ワード以上のエラー発生を判別する。
【００９０】制御部１９０は、規定タイミング関係に制
限されているクロックパルス又は制御信号を緩衝記憶装
置１００、シンドローム演算部１２０、第１，第２係数
演算部１３０，１４０、 Ｋ値演算部１５０、エラー判
別部１６０、エラー値演算部１８０及び緩衝記録器１０
１にそれぞれ供給する役割を果たす。
限されているクロックパルス又は制御信号を緩衝記憶装
置１００、シンドローム演算部１２０、第１，第２係数
演算部１３０，１４０、 Ｋ値演算部１５０、エラー判
別部１６０、エラー値演算部１８０及び緩衝記録器１０
１にそれぞれ供給する役割を果たす。
【００９１】図２の作動を図３に図示された動作流れ図
に基づいて説明する。
に基づいて説明する。
【００９２】制御部１９０はシンドローム演算部１２０
にシンドローム演算制御信号を印加してシンドローム演
算部１２０にしてシンドローム演算するように制御する
（第２００ステップ）。
にシンドローム演算制御信号を印加してシンドローム演
算部１２０にしてシンドローム演算するように制御する
（第２００ステップ）。
【００９３】第２００ステップ後、制御部１９０はエラ
ー判別制御信号をエラー判別部１６０に印加してエラー
判別部１６０をしてシンドロームがみんな“０”である
かを判別せしめ、エラー判別部１６０により判別された
結果を受け入れる。このとき、制御部１９０はエラー判
別部１６０から流入される判別結果信号がＳ０ ＝Ｓ１
＝Ｓ２ ＝Ｓ３ ＝０を示す信号の場合はエラーのな
いことを認識してエラー訂正作動を終了する（第２０１
ステップ）。
ー判別制御信号をエラー判別部１６０に印加してエラー
判別部１６０をしてシンドロームがみんな“０”である
かを判別せしめ、エラー判別部１６０により判別された
結果を受け入れる。このとき、制御部１９０はエラー判
別部１６０から流入される判別結果信号がＳ０ ＝Ｓ１
＝Ｓ２ ＝Ｓ３ ＝０を示す信号の場合はエラーのな
いことを認識してエラー訂正作動を終了する（第２０１
ステップ）。
【００９４】第２０１ステップでエラー判別部１６０に
流入された判別信号がＳ０ ＝Ｓ１ ＝Ｓ２＝Ｓ３≠０
であることを示すとき、制御部１９０は係数演算制御信
号を第１係数演算部１３０に印加して第１係数演算部を
してＤを演算せしめ（第２０２ステップ）、またエラー
判別部１６０にエラー判別部制御信号を再び印加して、
エラー判別部１６０をしてＤ＝０であるかを判別せしめ
る（第２０３ステップ）。
流入された判別信号がＳ０ ＝Ｓ１ ＝Ｓ２＝Ｓ３≠０
であることを示すとき、制御部１９０は係数演算制御信
号を第１係数演算部１３０に印加して第１係数演算部を
してＤを演算せしめ（第２０２ステップ）、またエラー
判別部１６０にエラー判別部制御信号を再び印加して、
エラー判別部１６０をしてＤ＝０であるかを判別せしめ
る（第２０３ステップ）。
【００９５】制御部１９０はエラー判別部１６０から流
入される判別結果信号がＤ＝０であることを示すとき、
エラー値演算部１８０及び緩衝記録器１０１を制御して
１ワードエラーが訂正されるようにする（第２０４ステ
ップ）。
入される判別結果信号がＤ＝０であることを示すとき、
エラー値演算部１８０及び緩衝記録器１０１を制御して
１ワードエラーが訂正されるようにする（第２０４ステ
ップ）。
【００９６】また、制御部１９０はエラー判別部１６０
に流入される判別結果信号がＤ≠０であることを示すと
き、係数演算制御信号を第１係数演算部１３０に印加し
て、第１係数演算部１３０をして２次エラー位置多項式
σ（ｙ） ＝ｙ２ ＋σ１ ｙ＋σ２ ＝０の二係数σ
１ 及びσ２ を算出せしめる（第２０５ステップ）。
に流入される判別結果信号がＤ≠０であることを示すと
き、係数演算制御信号を第１係数演算部１３０に印加し
て、第１係数演算部１３０をして２次エラー位置多項式
σ（ｙ） ＝ｙ２ ＋σ１ ｙ＋σ２ ＝０の二係数σ
１ 及びσ２ を算出せしめる（第２０５ステップ）。
【００９７】第２０５ステップでエラー判別部１６０に
流入された判別結果信号が、σ１ ＝０、σ２ ＝０で
あるかを判別される（第２０６ステップ）。
流入された判別結果信号が、σ１ ＝０、σ２ ＝０で
あるかを判別される（第２０６ステップ）。
【００９８】エラー判別部１６０に流入された判別結果
信号がσ１＝０、σ２＝０であることを示す場合は三つ
以上のエラーが発生したことである（第２０９ステップ
）。
信号がσ１＝０、σ２＝０であることを示す場合は三つ
以上のエラーが発生したことである（第２０９ステップ
）。
【００９９】第２０５ステップでエラー判別部１６０に
流入された判別結果信号が、σ１ ≠０、σ２ ≠０で
あることを示す場合、制御部１９０は第２係数演算制御
信号を印加して第２係数演算部１４０をしてＴｒ（Ｋ）
を演算せしめる（第２０７ステップ）。
流入された判別結果信号が、σ１ ≠０、σ２ ≠０で
あることを示す場合、制御部１９０は第２係数演算制御
信号を印加して第２係数演算部１４０をしてＴｒ（Ｋ）
を演算せしめる（第２０７ステップ）。
【０１００】第２０７ステップ後、エラー判別部１６０
に流入される判別結果信号がＴｒ（Ｋ） ＝０であるか
を判別せしめる（第２０８ステップ）。
に流入される判別結果信号がＴｒ（Ｋ） ＝０であるか
を判別せしめる（第２０８ステップ）。
【０１０１】制御部１９０はエラー判別部１６０に流入
された判別結果信号がＴｒ（Ｋ） ≠０を示す場合は、
三つ以上のエラーが発生したと判る（第２０９ステップ
）。
された判別結果信号がＴｒ（Ｋ） ≠０を示す場合は、
三つ以上のエラーが発生したと判る（第２０９ステップ
）。
【０１０２】制御部１９０はエラー判別部１６０に流入
された判別結果信号がＴｒ（Ｋ） ＝０であることを示
す場合はＸ１値演算部１５０をしてＸ１値を計算せしめ
、第１乗算器１７０はＸ１の値にσ１ の値を乗算して
Ｘ１ 値を算出し、第２乗算器１７１はＸ２の値にσ２
の値を乗算してＸ２ 値を算出する（第２１０ステッ
プ）。
された判別結果信号がＴｒ（Ｋ） ＝０であることを示
す場合はＸ１値演算部１５０をしてＸ１値を計算せしめ
、第１乗算器１７０はＸ１の値にσ１ の値を乗算して
Ｘ１ 値を算出し、第２乗算器１７１はＸ２の値にσ２
の値を乗算してＸ２ 値を算出する（第２１０ステッ
プ）。
【０１０３】第２１０ステップ後制御部１９０はエラー
値演算制御信号をエラー値演算部１８０に印加して、エ
ラー値演算部１８０をしてエラー値Ｙ１及びＹ２を算出
せしめる（第２１１ステップ）。
値演算制御信号をエラー値演算部１８０に印加して、エ
ラー値演算部１８０をしてエラー値Ｙ１及びＹ２を算出
せしめる（第２１１ステップ）。
【０１０４】第２１１ステップ後、制御部１９０は、第
２１０ステップで第１，第１乗算器１７０，１７１から
流入されたエラー位置値Ｘ１ 及びＸ２ に応じて緩衝
記録器１０１を制御して、緩衝記録器１０１をしてエラ
ー値演算部１８０から入力して貯蔵したエラー値Ｙ１及
びＹ２を第１加算器１１０に供給せしめる。このとき、
第１加算器１１０は緩衝記録１０１から流入されるエラ
ー値を緩衝記録装置１００から流入されるエラーの発生
された受信ワードに加算して受信ワードの二重ワードエ
ラーを訂正するようになる（第２１２ステップ）。
２１０ステップで第１，第１乗算器１７０，１７１から
流入されたエラー位置値Ｘ１ 及びＸ２ に応じて緩衝
記録器１０１を制御して、緩衝記録器１０１をしてエラ
ー値演算部１８０から入力して貯蔵したエラー値Ｙ１及
びＹ２を第１加算器１１０に供給せしめる。このとき、
第１加算器１１０は緩衝記録１０１から流入されるエラ
ー値を緩衝記録装置１００から流入されるエラーの発生
された受信ワードに加算して受信ワードの二重ワードエ
ラーを訂正するようになる（第２１２ステップ）。
【０１０５】
【発明の効果】本発明によるＧＦ（２８）上の二重エラ
ー訂正に用いられる方法と装置は、第２係数値演算部１
４０からの値を入力して図１に図示されたＥＸＯＲゲー
トを使用してデータを出力することにより、簡単，迅速
で従来のＲＯＭテーブルを使用するときよりチップサイ
ズをはるかに縮められる効果がある。
ー訂正に用いられる方法と装置は、第２係数値演算部１
４０からの値を入力して図１に図示されたＥＸＯＲゲー
トを使用してデータを出力することにより、簡単，迅速
で従来のＲＯＭテーブルを使用するときよりチップサイ
ズをはるかに縮められる効果がある。
【図１】本発明によるエラー訂正装置に適用される実施
例の回路図である。
例の回路図である。
【図２】本発明による実施例のエラー訂正装置のブロッ
ク図である。
ク図である。
【図３】図２に図示された装置の動作流れ図である。
Claims (3)
- 【請求項１】 受信ｎワード及びパリティー検査行列
Ｈよりなる１ブロックデータＶの下の演算によって４個
のシンドロームＳ０ 、Ｓ１ 、Ｓ２ 、Ｓ３ を求め
るステップと、 【数１】 前記シンドロームＳ０ 、Ｓ１ 、Ｓ２ 、Ｓ３ がＳ
０ ＝Ｓ１ ＝Ｓ２ ＝Ｓ３ ＝０の場合、エラーがな
いと判断するステップと、前記シンドロームＳ０ 、Ｓ
１ 、Ｓ２ 、Ｓ３ からＤ＝Ｓ０Ｓ２ ＋Ｓ１２ を
計算し、Ｄ＝０であるかを判断するステップと、前記Ｄ
＝０でない場合、下記の係数σ１、σ２を計算するステ
ップと、 σ１＝（Ｓ０Ｓ３＋Ｓ１Ｓ２）／Ｄ σ２＝（Ｓ１Ｓ３＋Ｓ１Ｓ２２）／Ｄ 前記係数σ１≠０、σ２≠０の場合、下の係数Ｋ 値と
Ｔｒ（Ｋ） 値を求めるステップと、 Ｋ ＝σ２／σ１２ ＝Ｋ０＋Ｋ１α＋Ｋ２α２＋Ｋ３α３＋Ｋ４α４＋Ｋ５
α５＋Ｋ６α６＋Ｋ７α７ Ｔｒ（Ｋ） ＝Ｋ０Ｔｒ（１）＋Ｋ１Ｔｒ（α）＋Ｋ２
Ｔｒ（α２）＋Ｋ３Ｔｒ（α３）＋Ｋ４Ｔｒ（α４）＋
Ｋ５Ｔｒ（α５）＋Ｋ６Ｔｒ（α６）＋Ｋ７Ｔｒ（α７
） 前記係数Ｋ から下のエラー位置Ｘ１、Ｘ２を求めるス
テップと、 Ｘ１＝Ｘ１・σ１ Ｘ２＝（１＋Ｘ１） ・σ１ ここで、Ｔｒ（α５）＝１から、 【数２】 前記エラー位置Ｘ１、Ｘ２から次のエラー値Ｙ１、Ｙ２
を求めるステップと、 Ｙ１＝（Ｓ０Ｘ２＋Ｓ１）／（Ｘ１＋Ｘ２）Ｙ２＝（Ｓ
０Ｘ１＋Ｓ１）／（Ｘ１＋Ｘ２）よりなり、 Ｋ∈ＧＦ
（２８）の場合に二つのエラーを訂正することを特徴と
するエラー訂正方法。 - 【請求項２】 受信ｎワードからシンドロームＳ０
、Ｓ１ 、Ｓ２ 、Ｓ３ を計算するシンドローム演算
部と、前記シンドロームから次の係数σ１、σ２を計算
する第１係数演算部と、 σ１＝（Ｓ０Ｓ３＋Ｓ１Ｓ２）／Ｄ σ２＝（Ｓ１Ｓ３＋Ｓ１Ｓ２２ ）／Ｄ前記係数σ１、
σ２から次の係数Ｋを計算する第２係数演算部と、 Ｋ＝σ２／σ１２ 前記係数ＫからＸ１値を演算するＸ１値演算部と、前記
Ｘ１値から次のエラー位置Ｘ１、Ｘ２を計算するエラー
位置値演算部と、 Ｘ１＝Ｘ１・σ１ Ｘ２＝（１＋Ｘ１）・σ１ 前記エラー位置Ｘ１、Ｘ２値を入力して次のエラー値Ｙ
１、Ｙ２を計算するエラー値演算部及び Ｙ１＝（Ｓ０Ｘ２＋Ｓ１）／（Ｘ１＋Ｘ２）Ｙ２＝（Ｓ
０Ｘ１＋Ｓ１）／（Ｘ１＋Ｘ２）エラーが何個発生した
か否かを判定するためのエラー判別部を具備したシステ
ムにおいて、 前記Ｘ１値演算部は次の式 ｘ０ ＝Ｋ３＋Ｋ５＋Ｋ６ ｘ１ ＝Ｋ０＋Ｋ２＋Ｋ４ ｘ２ ＝Ｋ０＋Ｋ３＋Ｋ４＋Ｋ６ ｘ３ ＝Ｋ１＋Ｋ２＋Ｋ３＋Ｋ４ ｘ４ ＝Ｋ０＋Ｋ７ ｘ５ ＝Ｋ１＋Ｋ２＋Ｋ３＋Ｋ４＋Ｋ６ｘ６ ＝Ｋ０＋
Ｋ１＋Ｋ２＋Ｋ４＋Ｋ７ｘ７ ＝Ｋ０＋Ｋ１＋Ｋ２＋Ｋ
４ を満たす論理ゲートを用いて構成したことを特徴とする
エラー訂正装置。 - 【請求項３】 前記論理ゲートはＥＸＯＲゲートであ
ることを特徴とする請求項２記載のエラー訂正装置。
Applications Claiming Priority (2)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| KR1019910001859A KR930007928B1 (ko) | 1991-01-31 | 1991-01-31 | 오류정정방법 및 장치 |
| KR1991-001859 | 1991-01-31 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPH04248630A true JPH04248630A (ja) | 1992-09-04 |
| JP2644639B2 JP2644639B2 (ja) | 1997-08-25 |
Family
ID=19310703
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP3123532A Expired - Fee Related JP2644639B2 (ja) | 1991-01-31 | 1991-05-28 | エラー訂正方法及び装置 |
Country Status (7)
| Country | Link |
|---|---|
| US (1) | US5315601A (ja) |
| JP (1) | JP2644639B2 (ja) |
| KR (1) | KR930007928B1 (ja) |
| DE (1) | DE4117726C2 (ja) |
| FR (1) | FR2672403B1 (ja) |
| GB (1) | GB2252431B (ja) |
| IT (1) | IT1250495B (ja) |
Families Citing this family (10)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| RU2127943C1 (ru) * | 1998-02-18 | 1999-03-20 | Военная академия связи | Устройство защиты от ошибок |
| US6772390B2 (en) * | 2000-11-30 | 2004-08-03 | Quantum Corporation | Erasure correction for ECC entities |
| JP4836608B2 (ja) * | 2006-02-27 | 2011-12-14 | 株式会社東芝 | 半導体記憶装置 |
| KR101502895B1 (ko) | 2010-12-22 | 2015-03-17 | 주식회사 케이티 | 복수의 오류 복제본으로부터 오류를 복구하는 방법 및 상기 방법을 이용하는 스토리지 시스템 |
| KR101585146B1 (ko) | 2010-12-24 | 2016-01-14 | 주식회사 케이티 | 오브젝트를 복수 개의 데이터 노드들의 위치에 기반하여 분산 저장하는 분산 저장 시스템 및 그 위치 기반 분산 저장 방법 및 컴퓨터에 의하여 독출 가능한 저장 매체 |
| KR101544480B1 (ko) | 2010-12-24 | 2015-08-13 | 주식회사 케이티 | 복수 개의 프락시 서버를 포함하는 분산 저장 시스템 및 그 오브젝트 관리 방법 및 컴퓨터에 의하여 독출가능한 저장 매체 |
| KR101483127B1 (ko) | 2011-03-31 | 2015-01-22 | 주식회사 케이티 | 클라우드 스토리지 시스템에서 리소스를 고려한 자료분배방법 및 장치 |
| KR101544483B1 (ko) | 2011-04-13 | 2015-08-17 | 주식회사 케이티 | 분산 저장 시스템의 복제 서버 장치 및 복제본 생성 방법 |
| KR101544485B1 (ko) | 2011-04-25 | 2015-08-17 | 주식회사 케이티 | 클라우드 스토리지 시스템에서 복수개의 복제본을 분산 저장하는 방법 및 장치 |
| KR20210138241A (ko) | 2020-05-12 | 2021-11-19 | 삼성전자주식회사 | 메모리 컨트롤러, 메모리 시스템 및 메모리 모듈 |
Citations (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPS5725047A (en) * | 1980-07-23 | 1982-02-09 | Sony Corp | Error correcting method |
| JPS641333A (en) * | 1987-06-24 | 1989-01-05 | Matsushita Electric Ind Co Ltd | Quadratic equation factorization device |
Family Cites Families (7)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US4099160A (en) * | 1976-07-15 | 1978-07-04 | International Business Machines Corporation | Error location apparatus and methods |
| CA1161565A (en) * | 1980-06-20 | 1984-01-31 | Yoichiro Sako | Method of error correction |
| CA1170776A (en) * | 1980-07-18 | 1984-07-10 | Yoichiro Sako | Method of error correction of blocks of data |
| JPS5961332A (ja) * | 1982-09-30 | 1984-04-07 | Nec Corp | 誤り訂正回路 |
| USRE33332E (en) * | 1983-03-12 | 1990-09-11 | Sony Corporation | Apparatus for correcting errors |
| DE3484455D1 (de) * | 1983-09-06 | 1991-05-23 | Toshiba Kawasaki Kk | Fehlerkorrekturschaltung. |
| JP2532917B2 (ja) * | 1988-04-20 | 1996-09-11 | 三洋電機株式会社 | デ―タ誤り検出回路 |
-
1991
- 1991-01-31 KR KR1019910001859A patent/KR930007928B1/ko not_active Expired - Lifetime
- 1991-05-15 GB GB9110490A patent/GB2252431B/en not_active Expired - Lifetime
- 1991-05-28 FR FR9106389A patent/FR2672403B1/fr not_active Expired - Lifetime
- 1991-05-28 JP JP3123532A patent/JP2644639B2/ja not_active Expired - Fee Related
- 1991-05-29 IT ITMI911471A patent/IT1250495B/it active IP Right Grant
- 1991-05-30 US US07/707,811 patent/US5315601A/en not_active Expired - Lifetime
- 1991-05-30 DE DE4117726A patent/DE4117726C2/de not_active Expired - Lifetime
Patent Citations (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPS5725047A (en) * | 1980-07-23 | 1982-02-09 | Sony Corp | Error correcting method |
| JPS641333A (en) * | 1987-06-24 | 1989-01-05 | Matsushita Electric Ind Co Ltd | Quadratic equation factorization device |
Also Published As
| Publication number | Publication date |
|---|---|
| FR2672403B1 (fr) | 1995-03-17 |
| FR2672403A1 (fr) | 1992-08-07 |
| ITMI911471A1 (it) | 1992-11-29 |
| DE4117726C2 (de) | 1994-11-10 |
| KR920015197A (ko) | 1992-08-26 |
| GB2252431B (en) | 1994-11-16 |
| US5315601A (en) | 1994-05-24 |
| JP2644639B2 (ja) | 1997-08-25 |
| ITMI911471A0 (it) | 1991-05-29 |
| IT1250495B (it) | 1995-04-08 |
| DE4117726A1 (de) | 1992-08-06 |
| KR930007928B1 (ko) | 1993-08-21 |
| GB9110490D0 (en) | 1991-07-03 |
| GB2252431A (en) | 1992-08-05 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| EP0387924B1 (en) | Method and apparatus for decoding error correction code | |
| US3668632A (en) | Fast decode character error detection and correction system | |
| US5805799A (en) | Data integrity and cross-check code with logical block address | |
| US3668631A (en) | Error detection and correction system with statistically optimized data recovery | |
| US8930786B2 (en) | Self-timed error correcting code evaluation system and method | |
| EP0567148A2 (en) | Operating circuit for galois field | |
| EP0373764B1 (en) | Correction of random and burst errors | |
| JP2644639B2 (ja) | エラー訂正方法及び装置 | |
| EP0105499A2 (en) | Method capable of simultaneously decoding two reproduced sequences | |
| JP2696212B2 (ja) | 誤り訂正装置 | |
| JPH10508988A (ja) | Ｃｒｃ／ｅｄｃチェッカシステム | |
| JPH04315332A (ja) | 誤り訂正装置 | |
| EP0629052B1 (en) | Method of and circuit for correcting errors | |
| JP2810397B2 (ja) | 誤り訂正装置 | |
| JP3252515B2 (ja) | 誤り訂正装置 | |
| JPH1117557A (ja) | 誤り訂正方法及び誤り訂正装置 | |
| JP2578739B2 (ja) | イレ−ジャ訂正方法 | |
| KR100246342B1 (ko) | 리드솔로몬오류수정장치 | |
| US12633946B2 (en) | Error correction circuit | |
| JP2684031B2 (ja) | データの復号化方法 | |
| KR100239798B1 (ko) | 디지털 신호의 재생에 있어 에러정정방법 및 그에 적용되는 장치 | |
| US20250293710A1 (en) | Error correction circuit | |
| JP3595271B2 (ja) | 誤り訂正復号方法および装置 | |
| JP3135552B2 (ja) | リードソロモン符号の誤り検出及び訂正装置 | |
| JP2561236B2 (ja) | 誤り訂正装置 |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| R250 | Receipt of annual fees |
Free format text: JAPANESE INTERMEDIATE CODE: R250 |
|
| R250 | Receipt of annual fees |
Free format text: JAPANESE INTERMEDIATE CODE: R250 |
|
| R250 | Receipt of annual fees |
Free format text: JAPANESE INTERMEDIATE CODE: R250 |
|
| R250 | Receipt of annual fees |
Free format text: JAPANESE INTERMEDIATE CODE: R250 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20090502 Year of fee payment: 12 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20100502 Year of fee payment: 13 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20110502 Year of fee payment: 14 |
|
| LAPS | Cancellation because of no payment of annual fees |