JPH04365139A - 誤り訂正処理用シンドローム演算回路 - Google Patents

誤り訂正処理用シンドローム演算回路

Info

Publication number
JPH04365139A
JPH04365139A JP3141537A JP14153791A JPH04365139A JP H04365139 A JPH04365139 A JP H04365139A JP 3141537 A JP3141537 A JP 3141537A JP 14153791 A JP14153791 A JP 14153791A JP H04365139 A JPH04365139 A JP H04365139A
Authority
JP
Japan
Prior art keywords
data
error correction
correction processing
row
natural number
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
Application number
JP3141537A
Other languages
English (en)
Other versions
JP2662472B2 (ja
Inventor
Toshihisa Tanaka
稔久 田中
Tetsuo Iwaki
哲男 岩木
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Sharp Corp
Original Assignee
Sharp Corp
Priority date (The priority date 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 date listed.)
Filing date
Publication date
Application filed by Sharp Corp filed Critical Sharp Corp
Priority to JP3141537A priority Critical patent/JP2662472B2/ja
Publication of JPH04365139A publication Critical patent/JPH04365139A/ja
Application granted granted Critical
Publication of JP2662472B2 publication Critical patent/JP2662472B2/ja
Anticipated expiration legal-status Critical
Expired - Fee Related legal-status Critical Current

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
    • 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
    • H03M13/157—Polynomial evaluation, i.e. determination of a polynomial sum at a given value

Landscapes

  • Physics & Mathematics (AREA)
  • Mathematical Physics (AREA)
  • Algebra (AREA)
  • General Physics & Mathematics (AREA)
  • Pure & Applied Mathematics (AREA)
  • Probability & Statistics with Applications (AREA)
  • Engineering & Computer Science (AREA)
  • Theoretical Computer Science (AREA)
  • Detection And Correction Of Errors (AREA)
  • Error Detection And Correction (AREA)

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】
【０００１】
【産業上の利用分野】本発明は、デジタルデータ等の記
録、再生時に用いる誤り訂正符号装置に関するものであ
る。
【０００２】
【従来の技術】以下に従来の技術を示す。
【０００３】対象となるデータ列を、｛Ｄ０，Ｄ１，Ｄ
２，・・・Ｄ（ｎ−２｝，Ｄ（ｎ−１）｝とする。これ
がまず、メモリに記憶される。例えばリードソロモン符
号で誤り訂正処理を行う場合、その最小距離をｄとすれ
ばｉｎｔ（（ｄ−１）／２）ワードまでの誤り訂正及び
、ｉｎｔ（ｄ−１）ワードまでの誤り検出が可能である
が、その演算を実行するためには次式で表されるシンド
ロームＳｉにおいて、 ｉ＝ｔ〜（ｔ＋ｄ−２）までの（ｄ−１）個のシンドロ
ームが必要である事が知られている。ここでｔは０か任
意の自然数である。
【０００４】これらのシンドロームの演算法として、メ
モリに記憶されたｎ個のデータをＤ（ｎ−１）より順次
１個ずつ図２に示す多項式（ｘ−αｉ）による割算回路
に入力し、全データ入力後にその出力として得る方法が
行われている。
【０００５】
【発明が解決しようとする課題】誤り訂正処理時間は、
復号の訂正能力が低い場合や符号化時にはその処理中の
シンドローム演算時間が支配的となる事が知られている
。ここで従来の技術によればデータを１個ずつメモリよ
り読み出すため、アクセスタイムの遅いメモリを使用す
ると処理時間の大幅な増加を招くと言う問題点がある。 特にデータ長の長いときなどその影響が大きい。
【０００６】
【課題を解決するための手段】デジタルデータ等の記録
、再生に用いる誤り訂正装置において、αをガロア体Ｇ
Ｆ（ｑｍ）ｋ原始元とし、ｋを、ｎを割り切る自然数と
したとき、メモリに入力されたｎ個の情報ワードＤ０，
Ｄ１，・・・Ｄ（ｎ−２），Ｄ（ｎ−１）をｋワードご
とにまとめ下記のごとくｋ行、ｎ／ｋ列のマトリックス
を生成し、 Ｄ０　　　　　　　　　　Ｄｋ　　　　　　　　　　・
・・　　Ｄ（ｎ−ｋ）Ｄ１　　　　　　　　　　Ｄ（ｋ
＋１）　　　　　　・・・　　Ｄ（ｎ−ｋ＋１）・　　
　　　　　　　　　・　　　　　　　　　　　　　　　
　　　　・・　　　　　　　　　　　・　　　　　　　
　　　　　　　　　　　　・・　　　　　　　　　　　
・　　　　　　　　　　　　　　　　　　　・Ｄ（ｋ−
１）　　　　　　Ｄ（２ｋ−１）　　　　　・・・　　
Ｄ（ｎ−１）それぞれの行を（ｎ／ｋ）列のデータより
順次、また同一列上のデータは同時にｋ本のバスライン
を通じてｋ個の多項式（ｘ−αｋｉ）による割算回路に
入力する。
【０００７】そのｋ個の出力は以下のようになるから、
第１行：α（ｎ−ｋ）ｉＤ（ｎ−ｋ）　　＋α（ｎ−２
ｋ）ｉＤ（ｎ−２ｋ）　　＋・・・＋αｋｉＤｋ　　　
　＋Ｄ０第２行：α（ｎ−ｋ）ｉＤ（ｎ−ｋ＋１）＋α
（ｎ−２ｋ）ｉＤ（ｎ−２ｋ＋１）＋・・・＋αｋｉＤ
（ｋ＋１）＋Ｄ１　　　　　　　　　　　　　　・　　
　　　　　　　　　　　　　　・　　　　　　　　　　
　　　　　　　　・　　　　　　　　　　・　　　　　
　　　　　　　　　・　　　　　　　　　　　　　　　
　・　　　　　　　　　　　　　　　　　　・　　　　
　　　　　　・　　　　　　　　　　　　　　・　　　
　　　　　　　　　　　　　・　　　　　　　　　　　
　　　　　　　・　　　　　　　　　　・第ｋ行：α（
ｎ−ｋ）ｉＤ（ｎ−１）＋α（ｎ−２ｋ）ｉＤ（ｎ−ｋ
−１）＋・・・＋αｋｉＤ（２ｋ−１）＋Ｄ（ｋ−１） それぞれα０（＝１）、αｉ、・・・α（ｋ−１）ｉの
掛算器を通した後に加算する事によりシンドロームＳｉ
を求める。
【０００８】また、ｋを、ｎを割り切らない自然数とし
た場合は、データの不足分にｈ個の零を用いて下記のご
とくｋ行、（（ｎ＋ｈ／ｋ）列のマトリックスを生成し
、同様に求める。
【０００９】 Ｄ０　　　　　　　　　　Ｄｋ　　　　　　　　・・・
　　Ｄ（ｎ−２｝Ｄ１　　　　　　　　　　Ｄ（ｋ＋１
）　　　　・・・　　Ｄ（ｎ−１）Ｄ２　　　　　　　
　　　Ｄ（ｋ＋２）　　　　・・・　　０・　　　　　
　　　　　　　・　　　　　　　　　　　　　　　　・
・　　　　　　　　　　　　・　　　　　　　　　　　
　　　　　・・　　　　　　　　　　　　・　　　　　
　　　　　　　　　　　・Ｄ（ｋ−１）　　　　　　Ｄ
（２ｋ−１）　　　・・・　　０
【００１０】
【作用】上記手段により、メモリからのデータ転送レー
トを従来の１／ｋに低下させてのシンドローム演算が可
能となり、つまりはメモリからのデータ読み出し回数が
従来の１／ｋに減少するので、アクセスタイムの遅いメ
モリを用いても訂正処理時間の増加を防止することがで
きる。
【００１１】
【実施例】以下、本発明に係る実施例について、図１を
用いて詳細に説明する。
【００１２】図１は本発明の実施例を示す誤り訂正処理
用シンドローム演算回路であって、ｋ＝３，ｎ＝１２と
した場合の一つの実施例を示す。
【００１３】図１において、１はデータ記憶用メモリ、
２はフリップフロップ、３はα３ｉの掛算器、４はαｉ
の掛算器、５はα２ｉの掛算器、６は多項式（ｘ−α３
ｉ）による割算回路、７は加算器である。
【００１４】まず、メモリ１に記憶された１２個の情報
ワードＤ０，Ｄ１，・・・Ｄ１０，Ｄ１１を３ワードご
とにまとめ、下記のごとく３は行、４列のマトリックス
を生成する。
【００１５】Ｄ０　　　　Ｄ３　　Ｄ６　　Ｄ９Ｄ１　
　　　Ｄ４　　Ｄ７　　Ｄ１０ Ｄ２　　　　Ｄ５　　Ｄ８　　Ｄ１１ このマトリックスにおいて［Ｄ０　　Ｄ３　　Ｄ６　　
Ｄ９］を第１行、［Ｄ１　　Ｄ４　　Ｄ７Ｄ１０］を第
２行、［Ｄ２　　Ｄ５　　Ｄ８　　Ｄ１１］を第３行と
し、それぞれの行をＤ９、Ｄ１０、Ｄ１１から順次１個
ずつ同一列上のデータは同時に、３個の多項式（ｘ−α
３ｉ）による割算回路６に入力する。全データ入力後そ
の出力は、 第１行：α９ｉＤ９　＋α６ｉＤ６＋α３ｉＤ３＋Ｄ０
第２行：α９ｉＤ１０＋α６ｉＤ７＋α３ｉＤ４＋Ｄ１
第３行：α９ｉＤ１１＋α６ｉＤ８＋α３ｉＤ５＋Ｄ２
となる。これを、第１行はそのまま、第２行はαｉの掛
算器４を通し、第３行はα２ｉの掛算器５を通した後に
加算すればシンドロームＳｉとして Ｓｉ＝第３行×α２ｉ＋第２行×αｉ＋第１行　　　＝
α１１ｉＤ１１＋α１０ｉＤ１０＋α９ｉＤ９＋α８ｉ
Ｄ８＋α７ｉＤ７＋α６ｉＤ６　　　　　　　　　　　
　　＋α５ｉＤ５＋α４ｉＤ４＋α３ｉＤ３＋α２ｉＤ
２＋αｉＤ１＋Ｄ０ が得られる。第１行、第２行、第３行の同一列上のデー
タはメモリ１より各１個ずつ同時に読み出されるから、
読み出し回数は１２個のデータに対して４回で済む。
【００１６】また、この際ｎが３（＝ｋ）で割り切れな
い場合には、以下の例のように不足分に零を追加して３
行のマトリックスとなし、同様の手順で行えば良い。
【００１７】 　　Ｄ０　　Ｄ３　　・・・Ｄ（ｎ−２）　　　　　　
Ｄ０　　Ｄ３　　・・・Ｄ（ｎ−１）　　Ｄ１　　Ｄ４
　　・・・Ｄ（ｎ−１）　　　　　　Ｄ１　　Ｄ４　　
・・・０　　Ｄ２　　Ｄ５　　・・・０　　　　　　　
　　　　Ｄ２　　Ｄ５　　・・・０
【００１８】
【発明の効果】以上の説明より明らかなように、本発明
のシンドローム演算回路によれば、メモリからのデータ
転送レートを従来の１／ｋに低下させた状態におけるシ
ンドローム演算が可能となり、データ記憶用メモリのア
クセスタイムが遅い場合でも高速で動作させることがで
きるため、訂正処理時間の高速化に寄与することができ
る。
【図面の簡単な説明】
【図１】本発明に係る誤り訂正処理用シンドローム演算
回路の一実施例である。
【図２】シンドローム演算に使用する多項式（ｘ−αｉ
）による割算回路である。
【符号の説明】
１　　データ記憶用メモリ ２　　フリップフロップ ３　　α３ｉの掛算器 ４　　αｉの掛算器 ５　　α２ｉの掛算器 ６　　多項式（ｘ−α３ｉ）による割算回路７　　加算
器

Claims (2)

    【特許請求の範囲】
  1. 【請求項１】　　デジタルデータ等の記録、再生に用い
    る誤り訂正装置において、αをガロア体ＧＦ（ｑｍ）（
    ｑ：素数，ｍ：自然数）の原始元とし、ｋを、ｎを割り
    切る自然数としたとき、メモリに入力されたｎ個の情報
    ワードＤ０，Ｄ１，・・・Ｄ（ｎ−２），Ｄ（ｎ−１）
    をｋワードごとにまとめ下記のごとくｋ行、（ｎ／ｋ）
    列のマトリックスを生成し、 Ｄ０　　　　　　　　　　Ｄｋ　　　　　　　　・・・
    　　Ｄ（ｎ−ｋ）Ｄ１　　　　　　　　　　Ｄ（ｋ＋１
    ）　　　　・・・　　Ｄ（ｎ−ｋ＋１）・　　　　　　
    　　　　　　・　　　　　　　　　　　　　　　　・・
    　　　　　　　　　　　　・　　　　　　　　　　　　
    　　　　・・　　　　　　　　　　　　・　　　　　　
    　　　　　　　　　　・Ｄ（ｋ−１）　　　　　　Ｄ（
    ２ｋ−１）　　　・・・　　Ｄ（ｎ−１）それぞれの行
    を（ｎ／ｋ）列のデータより順次、また同一列上のデー
    タは同時にｋ本のバスラインを通じてｋ個の多項式（ｘ
    −αｋｉ）による割算回路に入力し、そのｋ個の出力を
    それぞれα０（＝１）、αｉ、・・・α（ｋ−１）ｉの
    掛算器を通した後に加算する事を特徴とする誤り訂正処
    理用シンドローム演算回路。
  2. 【請求項２】　　デジタルデータ等の記録、再生に用い
    る誤り訂正装置において、αをガロア体ＧＦ（ｑｍ）（
    ｑ：整数，ｍ：自然数）の原始元とし、ｋを、ｎを割り
    切らない自然数としたとき、メモリに入力されたｎ個の
    情報ワードＤ０，Ｄ１，・・・Ｄ（ｎ−２），Ｄ（ｎ−
    １）をワードごとにまとめ、データの不足分にはｈ個の
    零を用いて下記のごとくｋ行、（（ｎ＋ｈ）／ｋ）列の
    マトリックスを生成し、 Ｄ０　　　　　　　　Ｄｋ　　　　　　　　　　・・・
    　　Ｄ（ｎ−２）Ｄ１　　　　　　　　Ｄ（ｋ＋１）　
    　　　　　・・・　　Ｄ（ｎ−１）Ｄ２　　　　　　　
    　Ｄ（ｋ＋２）　　　　　　・・・　　０・　　　　　
    　　　　　・　　　　　　　　　　　　　　　　　　・
    ・　　　　　　　　　　・　　　　　　　　　　　　　
    　　　　　・・　　　　　　　　　　・　　　　　　　
    　　　　　　　　　　　・Ｄ（ｋ−１）　　　　Ｄ（２
    ｋ−１）　　　　　・・・　　０それぞれの行を（（ｎ
    ＋ｈ）／ｋ）列のデータより順次、また同一列上のデー
    タは同時にｋ本のバスラインを通じてｋ個の多項式（ｘ
    −αｋｉ）による割算回路に入力し、そのｋ個の出力を
    それぞれα０（＝１）、αｉ、・・・α（ｋ−１）ｉの
    掛算器を通した後に加算する事を特徴とする誤り訂正処
    理用シンドローム演算回路。
JP3141537A 1991-06-13 1991-06-13 誤り訂正処理用シンドローム演算回路 Expired - Fee Related JP2662472B2 (ja)

Priority Applications (1)

Application Number Priority Date Filing Date Title
JP3141537A JP2662472B2 (ja) 1991-06-13 1991-06-13 誤り訂正処理用シンドローム演算回路

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
JP3141537A JP2662472B2 (ja) 1991-06-13 1991-06-13 誤り訂正処理用シンドローム演算回路

Publications (2)

Publication Number Publication Date
JPH04365139A true JPH04365139A (ja) 1992-12-17
JP2662472B2 JP2662472B2 (ja) 1997-10-15

Family

ID=15294277

Family Applications (1)

Application Number Title Priority Date Filing Date
JP3141537A Expired - Fee Related JP2662472B2 (ja) 1991-06-13 1991-06-13 誤り訂正処理用シンドローム演算回路

Country Status (1)

Country Link
JP (1) JP2662472B2 (ja)

Cited By (6)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
EP0720759A4 (en) * 1993-09-21 1997-01-22 Cirrus Logic Inc PROGRAMMABLE REDUNDANCY GENERATOR / SYNDROME
WO1997013328A1 (en) * 1995-10-03 1997-04-10 Matsushita Electric Industrial Co., Ltd Device and method for error correcting coding, and device and method for error correcting decoding
WO2004036759A1 (en) * 2002-10-16 2004-04-29 Telefonaktiebolaget L M Ericsson (Publ) Method and device for determining a polynomial sum
JP2005293557A (ja) * 2004-02-19 2005-10-20 Quantum Corp 復号器、データ記憶装置およびデータの誤り訂正の方法
US7644342B2 (en) 2001-11-21 2010-01-05 Kabushiki Kaisha Toshiba Semiconductor memory device
JP2012070434A (ja) * 2011-12-09 2012-04-05 Fujitsu Ltd Ｒａｉｄ装置及びガロア体の積演算処理方法

Cited By (7)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
EP0720759A4 (en) * 1993-09-21 1997-01-22 Cirrus Logic Inc PROGRAMMABLE REDUNDANCY GENERATOR / SYNDROME
US5822337A (en) * 1993-09-21 1998-10-13 Cirrus Logic, Inc. Programmable redundancy/syndrome generator
WO1997013328A1 (en) * 1995-10-03 1997-04-10 Matsushita Electric Industrial Co., Ltd Device and method for error correcting coding, and device and method for error correcting decoding
US7644342B2 (en) 2001-11-21 2010-01-05 Kabushiki Kaisha Toshiba Semiconductor memory device
WO2004036759A1 (en) * 2002-10-16 2004-04-29 Telefonaktiebolaget L M Ericsson (Publ) Method and device for determining a polynomial sum
JP2005293557A (ja) * 2004-02-19 2005-10-20 Quantum Corp 復号器、データ記憶装置およびデータの誤り訂正の方法
JP2012070434A (ja) * 2011-12-09 2012-04-05 Fujitsu Ltd Ｒａｉｄ装置及びガロア体の積演算処理方法

Also Published As

Publication number Publication date
JP2662472B2 (ja) 1997-10-15

Similar Documents

Publication Publication Date Title
US6141786A (en) Method and apparatus for performing arithmetic operations on Galois fields and their extensions
US4637021A (en) Multiple pass error correction
EP0167627B1 (en) Method and apparatus for decoding error correction code
JP3863252B2 (ja) 誤り訂正方法、誤り訂正装置、データ読み出し装置、及び、データマッピング方法
US5715262A (en) Errors and erasures correcting reed-solomon decoder
US5680340A (en) Low order first bit serial finite field multiplier
US7404134B2 (en) Encoding/decoding device using a reed-solomon encoder/decoder
US4856003A (en) Error correction code encoder
US7600177B2 (en) Delta syndrome based iterative Reed-Solomon product code decoder
US6725416B2 (en) Forward error correction apparatus and methods
US8201061B2 (en) Decoding error correction codes using a modular single recursion implementation
JPS6037833A (ja) 符号語の複号装置及び読み取り装置
JP3502583B2 (ja) 誤り訂正方法および誤り訂正装置
US5555516A (en) Multipurpose error correction calculation circuit
JP2004206798A (ja) 光ディスク装置のエンコードデータ符号回路
JP2662472B2 (ja) 誤り訂正処理用シンドローム演算回路
JP4733403B2 (ja) 復号器、データ記憶装置およびデータの誤り訂正の方法
JP2553565B2 (ja) ガロア体演算装置
JP3281938B2 (ja) 誤り訂正装置
JPH07226687A (ja) 誤り訂正処理装置
JP3252515B2 (ja) 誤り訂正装置
JP2001044853A (ja) チェンサーチ回路、誤り訂正装置及びディスクドライブ装置
JP3139499B2 (ja) 誤り訂正処理装置
JP2002118471A (ja) 記録再生装置及び誤り訂正符号化方法並びに情報記録方法
JP3702694B2 (ja) ディジタル信号処理回路

Legal Events

Date Code Title Description
LAPS Cancellation because of no payment of annual fees