JPH06208767A - 多重エラー訂正方法 - Google Patents

多重エラー訂正方法

Info

Publication number
JPH06208767A
JPH06208767A JP5251988A JP25198893A JPH06208767A JP H06208767 A JPH06208767 A JP H06208767A JP 5251988 A JP5251988 A JP 5251988A JP 25198893 A JP25198893 A JP 25198893A JP H06208767 A JPH06208767 A JP H06208767A
Authority
JP
Japan
Prior art keywords
error
group
calculating
code
error correction
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
Application number
JP5251988A
Other languages
English (en)
Inventor
Tae-Sik Joo
泰植 朱
Suk-Jung Lee
錫政 李
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.)
Samsung Electronics Co Ltd
Original Assignee
Samsung Electronics Co Ltd
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 Samsung Electronics Co Ltd filed Critical Samsung Electronics Co Ltd
Publication of JPH06208767A publication Critical patent/JPH06208767A/ja
Pending 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
    • G—PHYSICS
    • G11—INFORMATION STORAGE
    • G11B—INFORMATION STORAGE BASED ON RELATIVE MOVEMENT BETWEEN RECORD CARRIER AND TRANSDUCER
    • G11B20/00—Signal processing not specific to the method of recording or reproducing; Circuits therefor
    • G11B20/10—Digital recording or reproducing
    • G11B20/18—Error detection or correction; Testing, e.g. of drop-outs
    • G11B20/1806—Pulse code modulation systems for audio signals
    • G11B20/1809—Pulse code modulation systems for audio signals by interleaving
    • 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
    • G—PHYSICS
    • G11—INFORMATION STORAGE
    • G11B—INFORMATION STORAGE BASED ON RELATIVE MOVEMENT BETWEEN RECORD CARRIER AND TRANSDUCER
    • G11B20/00—Signal processing not specific to the method of recording or reproducing; Circuits therefor
    • G11B20/10—Digital recording or reproducing
    • G11B20/14—Digital recording or reproducing using self-clocking codes
    • G11B20/1403—Digital recording or reproducing using self-clocking codes characterised by the use of two levels
    • G11B20/1423—Code representation depending on subsequent bits, e.g. delay modulation, double density code, Miller code
    • G11B20/1426—Code representation depending on subsequent bits, e.g. delay modulation, double density code, Miller code conversion to or from block codes or representations thereof

Landscapes

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

Abstract

(57)【要約】 【目的】エラー訂正コードに基づき符号化した後、変調
コードに基づき変調されたデータに含まれたエラーシン
ボルを訂正する多重エラー訂正方法を提供する。 【構成】ＥＦＭまたはＥＴＭのような変調コードに基づ
く復調が可能か否かを示す復調フラグを算出し、復調フ
ラグはエラー訂正コードに基づきデータを復号化するに
使われる。リードソロモンコードにより復号化を行う
時、エラー位置を算出する方法は、σ1,σ2,σ3 がエラ
ー位置多項式の係数を示し、k1はσ1 2+σ2であり、k2は
σ1σ2+σ3とする時、式θ＝k2/(k1)3/2によりインデッ
クスを算出し、インデックスに関連した所定メモリから
仮想根を読み出し、式ｘj1＝(k1)1/2・Z1＋σ1,ｘj2＝
(k1)1/2・Z2＋σ1,ｘj3＝(k1)1/2・Z3＋σ1 により仮想
根Z1、Z2、Z3をエラー位置ｘj1，ｘj2，ｘj3に変換する
各過程を備える。 【効果】これにより、さらに多くのエラーシンボルを訂
正し、実用的な大きさを有するメモリを以て三重エラー
訂正を実時問に実現することを可能にする。

Description

【発明の詳細な説明】
【０００１】
【産業上の利用分野】本発明はエラー訂正方法及び装置
に係り、特にエラー訂正コードに基づき符号化された後
ＥＦＭ(Eight-to-Fourteen Modu1ation)及びＥＴＭ(Eig
ht-to-ten Modu1ation) などの変調コードに基づき変調
されたデータに含まれた、エラー的なシンボル群(error
neous symbols)を訂正する多重エラー訂正方法に関す
る。
【０００２】
【従来の技術】ＤＡＴ(Digita1 Audio Tape recoder)ま
たはＣＤ(Compact Disk)のような従来のディジタルオー
ディオ機器において、オーディオデータはＣ１／Ｃ２ク
ロスインタリーブプロダクトコードに基づき符号化され
る。さらに詳しくは、複数のシンボルを有するオーディ
オデータは三重エラーが訂正できる第２リードソロモン
コード（Ｃ２コード）に基づき先に符号化された後、所
定順序に従ってインタリーブされてから二重エラーが訂
正できる第１リードソロモンコード（Ｃ１コード）によ
り符号化される。
【０００３】実時間処理の制限を有する従来の復号シス
テムにおいて、第１リードソロモンコードに基づき符号
化されたデータを復号するために二重エラー訂正方法ま
たは４重エレージャ訂正方法が行われ、第２リードソロ
モンコードに基づき符号化されたデータを復号するため
に二重エラー訂正方法または６重エレージャ訂正方法が
行われる。
【０００４】ここで、エレージャはその位置が知られて
いるエラー的なシンボルを示す。シンボルは一つの単位
に取り扱う隣接した二進ディジット列であって、ワード
を構成する要素である。
【０００５】本願と関連のある従来の技術はソニー社に
よる米国特許第４，４７６，５６２号及び松下による米
国特許第４，８７５，２１１号に開示されている。
【０００６】松下の特許を参照すれば、二つまたはその
以上の多重エラーの位置はチェーンサーチアルゴリズム
により検索され得る。しかし、チェーンサーチアルゴリ
ズムに対する演算は一つのワードに含まれるシンボル群
の数ほど反復的に行われるべきである。
【０００７】一方、ソニー社の特許において、二重エラ
ー訂正及び４重エレージャ訂正は容易に行えるが、３重
（またはそれ以上）エラー訂正は行えない。
【０００８】
【発明が解決しようとする課題】本発明の目的は多重エ
ラー的なシンボル群が訂正できる多重エラー訂正方法を
提供することである。
【０００９】本発明の他の目的は３またはその以上のエ
ラー的なシンボル群のエラー位置が算出でき、ガロア(G
alois)フィールド演算器で実時間で容易に行える多重エ
ラー訂正方法を提供することである。
【００１０】
【課題を解決するための手段】前述した本発明の目的を
達成するため、エラー訂正コードにより符号化された後
変調コードに基づき変調されたデータに含まれるエラー
的なシンボルを訂正する方法において、変調コードに基
づきデータを復調して復調が可能か否かを示す復調フラ
グと共に復調されたデータを出力する過程と、前記エラ
ー訂正コードに基づき前記多数の復調されたデータ群に
より構成される受信ワードを用いてシンドローム群を算
出する過程と、前記シンドローム群により前記受信ワー
ドに含まれるエラーシンボル群の数を算出し、前記復調
フラグに基づき前記受信ワードに含まれるエレージャの
数を算出する過程と、前記エラー的なシンボル群の数に
基づきエラー形態を定める過程と、前記エラー訂正コー
ド及び前記エラー形態により受信ワードを訂正する過程
を備えることを特徴とする多重エラー訂正方法が提供さ
れる。
【００１１】本発明の他の目的を達成するため、第２エ
ラー訂正コード及び第１エラー訂正コードに基づき順次
に符号化された後変調コードに基づき変調されたデータ
に含まれたエラー的なシンボル群を訂正する方法におい
て、前記変調コードに基づきデータを復調して復調が可
能かを示す復調フラグと共に復調されたシンボルを出力
する過程と、前記第１エラー訂正コードに基づき前記複
数の復調されたシンボル群より構成される第１受信ワー
ドを用いて第１シンドローム群を算出する過程と、前記
第１シンドローム群及び前記復調フラグ群に基づき第１
受信ワードの第１エラー形態を定める過程と、前記第１
エラー訂正コード及び第１エラー形態に基づき前記第１
受信ワードを訂正した後、多数のエラー訂正されたシン
ボル群とそのシンボルが訂正されたか否かを示すエラー
フラグ群を含む復号化されたデータを出力する過程と、
前記第２エラー訂正コードに基づき前記多数のエラー訂
正されたシンボル群を含む第２受信ワードを用いて第２
シンドローム群を算出する過程と、前記第２シンドロー
ム群及びその中に存するエラーフラグ群に基づき第２受
信ワードの第２エラー形態を定める過程と、前記第２エ
ラー訂正コード及び前記第２エラー形態に基づき前記第
２受信ワードを訂正する第２エラー訂正過程を備えるこ
とを特徴とする多重エラー訂正方法が提供される。
【００１２】また本発明の他の目的を達成するため、エ
ラー訂正コードに基づき符号化されたデータに含まれる
エラー的なシンボル群を訂正する方法において、データ
を用いてシンドロームを算出する過程と、前記シンドロ
ーム群に基づきエラー位置多項式の係数群を算出する過
程と、前記係数に基づきインデックスを算出する過程
と、前記インデックスに関連する所定のメモリから前記
エラー位置多項式の複数の仮想根群を読み出す過程と、
所定関係式に基づき前記仮想根群をエラー位置群に変換
する過程と、前記シンドローム群及び前記エラー位置群
に基づきエラー値群を算出する過程と、前記エラー位置
群及び前記エラー値群に基づき前記データをエラー訂正
されたデータに変換する過程を備えることを特徴とする
多重エラー訂正方法が提供される。
【００１３】本発明の他の目的を達成するため、多重エ
ラー訂正方法の一態様は前記エラー訂正コードが三重エ
ラー的なシンボル群が訂正できるリードソロモンコード
とする時、次の式によりインデックスを算出する過程 θ＝ｋ2 ／［（ｋ1 ）3/2 ］ （但し、ｋ1 はσ1 2＋σ2 であり、ｋ2 はσ1σ2＋σ3
であり、σ1 、σ2 、σ3 は前記エラー位置を示す。） 式ｆ（Ｚ）＝Ｚ3 ＋Ｚ＋θ＝０の根を貯蔵してある所定
メモリから前記インデックスを用いて仮想根を読み出す
段階と、前記仮想根を次の式によりエラー位置に変換さ
せる過程を備える。
【００１４】ｘj1＝（ｋ1 ）1/2 ・Ｚ1 ＋σ1 ｘj2＝（ｋ1 ）1/2 ・Ｚ2 ＋σ1 ｘj3＝（ｋ1 ）1/2 ・Ｚ3 ＋σ1 （但し、Ｚ1 ，Ｚ2 ，Ｚ3 は前記仮想根を示し、ｘj1、
ｘj2、ｘj3は前記エラー位置を示す。）
【００１５】
【作用】エラー訂正されたか否かを示すフラグは次の段
階でエラー位置に関する情報として用いられる。また、
本発明によるエラー位置を算出する方法はインデックス
概念を導入して小規模のメモリを以て具現が可能であ
る。
【００１６】
【実施例】以下、添付した図面に基づき本発明を詳細に
説明する。
【００１７】図１はディジタルオーディオ記録システム
の概要ブロック図である。ティジタルオーディオ記録シ
ステムはアナログ−ディジタルコンバータ１０１、ソー
スコード器１０２、エラー訂正コード器１０３、変調器
１０４、信号コード器１０５及び記録媒体１０６を含
む。
【００１８】オーディオ信号はアナログ−ディジタルコ
ンバータ１０１を通じてディジタルデータに変換され
る。このディジタルデータはソースコード器１０２に印
加され所定アルゴリズムにより圧縮される。圧縮された
データはエラー訂正コード器１０３に印加されＣ１／Ｃ
２クロスインタリーブプロダクトコードのようなエラー
訂正コード体系に基づき符号化される。
【００１９】変調器１０４はエラー訂正コード器１０３
の出力を受信してＥＦＭまたはＦＴＭ符号化のような変
調コードに基づきその出力を変調する。
【００２０】また、変調コードはランレングス(run len
gth)制限コードと呼ばれるもので、二進列で１及び０の
ランレングスを所定数に限定する。ＥＦＭは８ビットデ
ータをランレングス制限を有する１４ビットデータに変
換するものであり、ＥＴＭは８ビットデータをランレン
グス制限を有する１０ビットデータに変換するものであ
る。
【００２１】変調器１０４から印加される二進情報は磁
気テープ及び磁気ディスクのような記録媒体１０６に符
号化された二進波形に記録される。この符号化された二
進波形はＮＲＺ(Non-Return-to-Zero)符号化された波形
及びＮＲＺＩ(modified-return-to-zero) 符号化された
波形を含む。ＮＲＺ符号化において、下進データのロジ
ッグ“１”及び“０”はそれぞれ二進波形で遷移のある
ものとないものと表現できる。信号コード器１０５はＮ
ＲＺ符号化及びＮＲＺＩ符号化のような信号符号化を行
う。
【００２２】図２は図１に示したエラー訂正コード器の
動作を説明するための流れ図である。
【００２３】第２０１段階において、Ｃ２符号化が行わ
れるが、これはソースコード器１０２から供給されたデ
ータを二重エラーが訂正できる第２リードソロモンコー
ドに基づき符号化して複数のシンボル群を含むＣ２コー
ド語を算出する。その後、Ｃ２コード語に含まれる複数
のシンボル群は第２０２段階で所定順序に従ってインタ
リーブされる。第２０３段階において、Ｃ１符号化が行
われるが、これはインタリーブされたデータを三重エラ
ーが訂正できる第１リードソロモンコードに基づき符号
化するものである。
【００２４】図３はＣ１／Ｃ２クロスインタリーブプロ
ダクトコードに対するメモリマップを説明するが、水平
的に整列されたシンボル群はＣ２コードに関連する第２
コード語を構成し、垂直に整列されたシンボル群はＣ１
コードに関連する第１コード語を構成する。Ｃ２コード
は三重エラーが訂正できるもので、ＲＳ３２、２６、７
と記すリードソロモンコードであり、Ｃ１コードは二重
エラー的なシンボル群が訂正できるもので、ＲＳ２４、
２０、５と記すリードソロモンコードである。図３に示
した通り、各Ｃ１コード語は２４個のシンボルを含み、
各Ｃ２コード語は３２個のシンボルを含む。さらに具体
的には、各Ｃ１コード語は２０個の情報シンボルと４個
のパリティーシンボル（Ｐパリティーシンボルとする）
を含み、各Ｃ２コード語は２６個の情報シンボルと６個
のパリティーシンボル（Ｑパリティーシンボルとする）
を含む。ここでＣ２符号化はＱパリティーシンボル群を
算出するが、Ｑパリティーシンボル群はＣ２コード語に
対する情報シンボルと共にＣ１コード語に対する情報シ
ンボルを構成する。また、ＰパリティーシンボルはＣ１
符号化で算出される。
【００２５】各シンボルは８ビットより構成される。メ
モリマップにおいて、Ｄ# 、# はソースコード器１０２
から供給されるデータに含まれるシンボル群を示し、Ｐ
# 、# はＰパリティーシンボルを示し、Ｑ# 、# はＱパ
リティーシンボルを示す。
【００２６】図４は本発明の実施例による多重エラー訂
正方法を説明する流れ図である。図４を参照すれば、第
４０１段階において、エラー訂正コードに基づき符号化
された後、変調コードに基づき変調されたデータは先に
変調コードに基づき復調される。例えば、１４ビットデ
ータはＦＦＭ復調に基づき８ビットデータに復調され、
一方１０ビットデータはＥＴＭ復調に基づき８ビットデ
ータに復調される。ここで、もし１４ビットデータ（Ｅ
ＦＭを通じて復調されるべき）及び１０ビットデータ
（ＥＴＭを通じて復調されるべき）が許容されないパタ
ーンを含む場合は、復調された８ビットデータ（即ち、
復調されたシンボル）は珍しいビットパターン（例え
ば、“００００００００”または“１１１１１１１
１”）にセットされうる。第４０２段階において、復調
フラグが算出されるが、これは各シンボルの復調が可能
かどうかを示す。従って、第４０２段階後、各シンボル
は基本的な８ビットのほか復調フラグの役割を果たす１
ビットを有する。復調フラグビットは復調の不可能な場
合に“１”にセットされ、復調の可能な場合は“０”に
セットされうる。第４０３段階において、復調されたデ
ータはエラー訂正コードに基づき復調フラグを用いて復
調される。復調フラグはエラー位置多項式のエラー位置
を算出する際大事な役割を果たす。
【００２７】図５はエラー訂正コードがリードソロモン
コードの条件において図４の第４０３段階を説明するた
めの流れ図である。
【００２８】図５を参照すれば、シンドロームはエラー
訂正コード及び復調された８ビットデータに基づき算出
される。さらに具体的には、シンドロームＳk は次の式
により算出される。
【００２９】Ｓk ＝ｒ（αk+1 ） 但し、ｋ＝１、２、３・・・であり、αはガロアフィー
ルド２8 でリードソロモンコードの原始多項式であり、
ｒ（ｘ）は複数の復調されたシンボルよりなる受信多項
式を示す。
【００３０】例えば、リードソロモンコードがＲＳ（２
４、２０、５）の場合に受信多項式は２４シンボルであ
り、リードソロモンコードがＲＳ（３２、２６、７）の
場合、受信多項式は３２シンボルである。リードソロモ
ンコードがｔ重（ｔは自然数）エラー訂正コードの場合
はエラーシンボルの総数が２ｔなので、求めるべきシン
ドロームの数は４ｔまたはそれ以上となる。ここで、エ
ラー的なシンボルはエラー及びエレージャなどを含む。
【００３１】第５０２段階において、受信多項式のエラ
ー形態はシンドローム及びエレージャの数に基づき定め
られるが、エレージャは“１”の復調フラグを有するシ
ンボルを示す。第５０３段階では復調フラグを用いてエ
ラー位置多項式のエラー位置を算出する。エラー位置は
受信多項式でエラー的なシンボルの位置を示す。従っ
て、受信多項式においてｎ番目シンボルが“１”にセッ
トされた復調フラグを有すれば、エラー位置が“ｎ”に
なる。第５０４段階ではリードソロモンコードに基づき
エラー位置を用いてエラー値を算出し、第５０５段階で
はエラー位置及びエラー値により受信多項式を訂正す
る。即ち、エラー値をｅ1 ，ｅ2 ，・・・，ｅv とし、
エラー推定多項式Ω（ｘ）＝σv ＋（σv Ｓ0 ＋
σv-1 ）ｘ＋（σvＳ1 ＋σv-1 Ｓ0 ＋σv-2 ）ｘ2 ・
・・＋（σv Ｓv-1 Ｓv-2 ＋σv-1 ＋・・・＋１）ｘv
とすれば、エラー値は次の式により算出される。
【００３２】
【数３】 それから受信多項式の訂正は次に基づき行われる。
【００３３】ｃ（ｘ）＝ｒ（ｘ）＋ｅ（ｘ） ここで、ｅ（ｘ）は式ｅ（ｘ）＝ｅ1 ｘj1＋ｅ2 ｘj2＋
・・・ｅv ｘjvを満たし、ｃ（ｘ）は訂正された多項
式、即ち訂正語を示し、ｒ（ｘ）は受信多項式、即ち受
信語を示す。
【００３４】図６は図５の第５０２段階を説明するため
の図面である。
【００３５】図６を参照すれば、第６０１段階は受信多
項式で“１”にセットされた復調フラグを有するシンボ
ルの数を計数することにより、エレージャの数を算出す
る。第６０２段階で、受信多項式に含まれるエラー的な
シンボルの数はシンドロームにより算出される。
【００３６】エラー的なシンボルの数を定めるためにマ
トリックスＭが用いられるが、これは次の式のように表
現される。
【００３７】
【数４】 ここで、ｖは２ｔ＋１、２ｔ、２ｔ−１、・・・１に変
わる変数を示す。
【００３８】変数ｖの値のうち、マトリックスＭの決定
値(determinant value) が“０”でない（即ち、ｄｅｔ
［Ｍ］≠０）最大値が受信多項式のエラー的なシンボル
の数となる。ここで、もし最大値即ちエラー的なシンボ
ルの数が２ｔ＋１であればエラー訂正は不可能である。
【００３９】第６０３段階ではリードソロモンコードが
ｔのうちエラーが訂正できる場合、エラーシンボルの数
Ｎが２ｔ以上か否かを定める。もし、エラー的なシンボ
ルの数が２ｔ以上ならエラー形態は第６０９段階で訂正
できないエラー形態に定められる。第６０４段階におい
て、純粋エラーの数Ｎerror はエラー的なシンボルの数
Ｎからエレージャの数Ｎerasure を減算することにより
算出する。ここで、純粋エラーはその位置が知られてい
ないエラー的なシンボルである。
【００４０】第６０５段階ではリードソロモンコードが
ｔのうちエラーが訂正できる場合に純粋エラーの数Ｎ
error がｔより大きいか否かを定める。もし純粋エラー
のＮer ror がｔより大きければ、エラー形態は第６０９
段階で訂正不可能なエラー形態に定められる。第６０６
段階ではエラー的なシンボルの数Ｎが“０”か否かを定
める。もし、エラー的なシンボルの数が“０”ならエラ
ー形態は第６１０段階でば“エラー無し”形態に定めら
れる。第６０７段階では純粋エラーの数Ｎerrorが
“０”か否かを定め、もしそうならエラー形態は第６１
１段階で純粋エレージャ形態に定められる。第６０８段
階ではエレージャの数Ｎerasure が“０”か否かが定め
られる。もしエレージャ数Ｎerasure が“０”なら、エ
ラー形態は第６１２段階で“純粋エラー”形態に定めら
れ、もしそうでなければエラー形態は第６１３段階で
“合成エラー”形態に定められる。合成エラー形態は少
なくとも一つの純粋エラー及び少なくとも一つのエレー
ジャを含む受信多項式となる。
【００４１】図７はエラー形態が受信多項式で位置が知
られていないエラー的なシンボルのみを含む純粋エラー
形態の場合、図５で第５０３段階を説明するための図面
である。
【００４２】図７を参照すれば、第７０１段階ではｖ次
エラー位置多項式、σ（ｘ）の計数を算出する。ここ
で、次数（ｖ）はエラーシンボルの数と同一である。さ
らに具体的には純粋エラーの数と同一である。ｖ次エラ
ー位置多項式はσ（ｘ）＝σv＋σv-1 ｘ＋σv-2 ｘ2
・・・＋ｘv と示す。ここでσ1 ないしσv は係数であ
る。
【００４３】エラー位置多項式の係数は次の通り算出さ
れる。
【００４４】
【数５】 例えば、もしｖが２（２次）ならエラー位置多項式はσ
（ｘ）＝ｘ2 ＋σ1 ｘ＋σ2 と表現できる。このエラー
位置多項式の係数σ1 、σ2 は次の式を用いて算出され
る。
【００４５】
【数６】 第７０２段階ではｖ次エラー位置多項式の根のエラー位
置を算出する。エラー位置多項式のような方程式の根を
求める際、方程式の次数が高くなるほどその根を算出し
にくくなる。正常的に５次以上の方程式は殆どの場合解
けない。しかし、リードソロモンコードのためのガロア
フィールドでは根が有限個の要素を含むガロアフィール
ドに含まれる要素なので、理諭的に根が求められない。
即ち、根はエラー位置多項式でＸにガロアフィールドに
含まれる全ての要素を代入した後方程式を満たす要素を
捜し出すことにより算出される。
【００４６】しかし、実時間処理の制限とハードウェー
アの具現を鑑みれば、方程式の根はさらに効率的な方法
で得るべきである。これに関連したアルゴリズムは先行
技術の実施例に開示されているが、三重またはそれ以上
のエラー訂正には不充分である。
【００４７】本発明の目的は既に述べたように、三重エ
ラー訂正のためのエラー位置多項式のエラー位置を効率
的に算出する方法を提供することである。この方法は図
１１を参照して説明される。
【００４８】図８はエラー形態が受信多項式に位置がわ
かるエラーシンボルのみを含む純粋エレージャ形態の場
合に図５の第５０３段階を説明する図面である。
【００４９】図８を参照すれば、第８０１段階でｖがエ
ラー的なシンボル、即ちエレージャの数の場合、エラー
位置ｘj1，ｘj2，・・・ｘjvの代わりにエレージャの位
置を代入することによりエラー位置が算出される。
【００５０】第８０２段階ではエラー位置多項式σ
（ｘ）、即ちσv ＋σv-1 ｘ＋σv-2 ｘ2 ＋・・・＋ｘ
v の係数を算出する。ここで、エラー位置多項式の
“ｘ”はエラー位置ｘj1，ｘj2，・・・ｘjvにより代置
され、それにより連立方程式が構成される。ｖ連立方程
式の解はエラー位置多項式の係数である。従って、係数
はエラー位置により算出される。
【００５１】図９はエラー形態が受信多項式に純粋エラ
ーとエレージャの全てを含む合成エラー形態の場合に図
５に示した第５０３段階を説明する。
【００５２】図９を参照すれば、第９０１段階ではエラ
ー位置多項式σ（ｘ）、即ちσv ＋σv-1 ｘ＋σv-2 ｘ
2 ＋・・・＋ｘv （但し、ｖはエラーシンボルの数、即
ちＮerror とＮerasure 和である）の係数を算出する。
係数（σ1 ないしσv ）は前記式（２）により算出され
る。
【００５３】第９０２段階において、Ｎerasure エラー
位置は受信多項式のエレージャ位置に代置される。第９
０３段階ではエラー位置と係数の所定関係、即ち方程式
で根と係数との関係によりＮerror エラー位置を算出す
る。第９０３段階に関連するさらに詳しい説明はソニー
社による米国特許第４，４７６，５６２号を参照された
い。
【００５４】図１０は本発明の他の実施例による多重エ
ラー訂正方法を説明する流れ図である。
【００５５】図１０を参照すれば、第１００１段階にお
いて順次に第２エラー訂正コード及び第１エラー訂正コ
ードに基づき符号化された後変調コードにより変調され
たデータは先に変調コードにより復調される（この段階
は図４の第４０１段階と同様である）。
【００５６】第１００２段階で復調フラグが算出される
が、これは各シンボルの復調が可能か否かを意味する。
第１００３段階では二重エラーが訂正できるリードソロ
モンコードＲＳ２４、２０、５のような第１エラー訂正
コードに基づき第１受信多項式を復号化する。ここで、
第１リードソロモンコードがＲＳ２４、２０、５なら第
１受信多項式は複数の復調されたシンボル（例えば、２
４シンボル）を含む。また、第１００３段階では各シン
ボルが訂正されたか否かを示すエラーフラグを算出する
（第１００３段階において第１受信多項式の復号化は図
５ないし図９により説明され得る）。
【００５７】第１００４段階において、復調されたシン
ボルはインタリービング順の逆となる所定順序に従って
ディインタリーブされる。第１００５段階では三重エラ
ーが訂正できるリードソロモンコードＲＳ３２、２６、
７のような第２エラー訂正コードに基づき第２受信多項
式を復号化する。第２エラー訂正コードがＲＳ３２、２
５、７なら第２受信多項式は第１００３段階で復調され
た複数のシンボル（例えば、３２シンボル）より構成さ
れる（第１００５段階もやはり図５ないし図９により説
明され得る）。
【００５８】図１１は本発明の実施例によるエラー位置
を算出する方法を説明する。
【００５９】図１１を参照すれば、第１１０１段階では
エラー位置多項式の係数を用いてインデックス０を算出
する。第１１０２段階において仮想根はインデックスθ
に関連した特定化したメモリから読み出される。また、
この特定化したメモリはルックアップテーブルＬＵＴと
呼ばれるもので、Ｚ3 ＋Ｚ＋θ＝０のような所定方程式
に関する複数の根を含む。第１１０３段階では所定関係
により仮想根をエラー位置に変換する。
【００６０】以下、高次方程式及びそれらの解の特性を
説明する。
【００６１】３次（またはそれ以上）方程式の一殻の形
態は次の通り表現できる。
【００６２】３次：ｆ（ｘ）＝ｘ3 ＋ｃｘ2 ＋ｂｘ＋ａ ４次：ｆ（ｘ）＝ｘ4 ＋ｄｘ3 ＋ｃｘ2 ＋ｂｘ＋ａ ５次：ｆ（ｘ）＝ｘ5 ＋ｅｘ4 ＋ｄｘ3 ＋ｃｘ2 ＋ｂｘ
＋ａ 前記方程式に置いて、根はＧＦ（２8 ）のような有限体
の要素なので、一応係数が定められればそれらの根は求
められる。即ち、有限体に含まれる全ての要素をｘ値に
順次に代入し、方程式を満たす要素を捜し出す。しか
し、この方法は長時間を要して非実用的である。
【００６３】根を算出するためのさらに他の方法は根そ
れ自体を貯蔵する膨大なＬＵＴにより行われる。膨大な
ＬＵＴに含まれる根は事前処理段階で計算され、膨大な
ＬＵＴのアドレスは方程式の係数と一対一対応となる。
従って、膨大なＬＵＴは多過ぎるメモリを要してやはり
非実用的になる。
【００６４】ここで、３次方程式を考えて見る。前記３
次方程式はｆ（ｚ）＝Ｚ3 ＋Ｚ＋θ＝０のように再び書
かれることができる。
【００６５】まず、式ｘ3 ＋ｃｘ2 ＋ｂｘ＋ａ＝０にお
いて変数ｘにｍＺ＋ｎを代人すれば、（ｍＺ＋ｎ）3 ＋
ｃ（ｍＺ＋ｎ）2 ＋ｂ（ｍＺ＋ｎ）＋ａ＝０が得られ、
これを展開すれば、（ｍ3 Ｚ3 ＋３ｍ2 Ｚ2 ｎ＋３ｍＺ
ｎ2 ＋ｎ3 ）＋ｃ（ｍ2 Ｚ2 ＋２ｍＺＮ＋ｎ2 ）＋ｂ
（ｍＺ＋ｎ）＋ａ＝０となる。
【００６６】前記式で同類項を結ぶと、その結果式は次
の通り表現される。
【００６７】Ｚ3(ｍ3)＋Ｚ2(３ｍ2 ｎ＋ｃｍ2)＋Ｚ（３
ｍｎ2 ＋２ｃｍｎ＋ｂｍ）＋（ｎ3＋ｃｎ2 ＋ｂｎ＋
ａ）＝０ その後、最高次項のＺ3 の係数を１にするため、前記式
をｍ3 で割ると、
【数７】 のようになる。
【００６８】ここで、前記式と式Ｚ3 ＋Ｚ＋θ＝０の係
数を比較すれば、３ｍ2 ｎ＋ｃｍ2 ＝０であり、３ｍｎ
2 ＋２ｃｍｎ＋ｂｍ＝ｍ3 であることが分かる。
【００６９】ここで、前記多項式の根を求める演算がＧ
Ｆ（ｑ）の有限体上でなされれば前記式は次のように等
価変換される。
【００７０】ｍ2 ｎ＋ｃｍ2 ＝ｍ2 （ｎ＋ｃ）＝０ ｍｎ2 ＋ｂｍ＝ｍ3 従って、ａ，ｂ，ｃと示すと、ｍは（ｃ2 ＋ｂ)1/2にな
り、ｎはｃとなる。
【００７１】同様に、θは次のように示せる。
【００７２】θ＝｛（ｎ3＋ｃｎ2＋ｂｎ＋ａ）｝／ｍ3
＝（ｂｃ＋ａ）／（ｃ2 ＋ｂ)3/2 ここで可能なθ値により前記ｆ（Ｚ）＝Ｚ3 ＋Ｚ＋θ＝
０を満たす根Ｚ1 、Ｚ2 、Ｚ3 を事前段階で求めてＲＯ
Ｍテーブル（即ち、ＬＵＴ）に貯蔵する。その後、遂行
段階でアドレス、即ちインデックスθのみを指定させ
る。
【００７３】図１２は３次エラー多項式のエラー位置を
算出する方法を説明する。
【００７４】図１２を参照すれば、第１２０１段階で次
に式によりインデックスθを算出する。
【００７５】 θ＝ｋ2 ／［（ｋ1 ）3/2 ］ ・・・・・・・・（３） （但し、ｋ1 ＝（σ1 2＋σ2 ）3/2 ，ｋ2 ＝（σ1σ2＋
σ3 ）であり、σ1 、σ2 、σ3 は３次エラー位置多項
式の係数を示す） 第１２０２段階では式ｆ（Ｚ）＝Ｚ3 ＋Ｚ＋θ＝０の根
を貯蔵してある所定メモリから仮想根Ｚ1 、Ｚ2 、Ｚ3
を読み出す。
【００７６】第１２０３段階では仮想根Ｚ1 、Ｚ2 、Ｚ
3 を次によりエラー位置に変換させる。
【００７７】 ｘj1＝（ｋ1 ）1/2 ・Ｚ1 ＋σ1 ｘj2＝（ｋ1 ）1/2 ・Ｚ2 ＋σ1 ｘj3＝（ｋ1 ）1/2 ・Ｚ3 ＋σ1 ・・・・・（４） 具体的な例を挙げて前述した三重エラー訂正方法を説明
する。
【００７８】ＲＳ３６、２６、７コードを用いて符号化
されたコード語ｃ（ｘ）＝０を所定の記録媒体に記録し
てから再生したとしよう。それから受信コード語ｒ
（ｘ）＝α3 ｘ5 ＋α15ｘ12＋α21ｘ17となる。ここで
エラー多項式ｅ（ｘ）＝ｃ（ｘ）＋ｒ（ｘ）の形態を有
するので、ｅ（ｘ）＝α3 ｘ5 ＋α15ｘ12＋α21ｘ17と
なることが分かる。ここで、前記α3 、α15、α21はエ
ラー値ｅ1 、ｅ2 ，ｅ3 に当たり、ｘ5 、ｘ12、ｘ17は
エラー位置ｘj1，ｘj2，ｘj3となる。このような受信多
項式を人力するＲＳ復号化部では受信多項式に基づき６
個のシンドロームＳ0 −Ｓ5 を算出する。
【００７９】これらは次の通りである。
【００８０】Ｓ0 ＝ｒ（α0 ）＝α92 Ｓ1 ＝ｒ（α1 ）＝α128 Ｓ2 ＝ｒ（α2 ）＝α224 Ｓ3 ＝ｒ（α3 ）＝α139 Ｓ4 ＝ｒ（α4 ）＝α74 Ｓ5 ＝ｒ（α5 ）＝α47 それから三つの係数σ1 、σ2 、σ3 を前記シンドロー
ムに基づき算出すれば次のような結果が得られる。
【００８１】σ1 ＝α21 σ2 ＝α139 σ3 ＝α34 エラー位置多項式の係数を求めた後、所定のメモリ（Ｒ
ＯＭテーブル、即ちＬＵＴ）にアクセスするためにイン
デックスθを次の通り算出する。
【００８２】θ＝ｋ2 ／［（ｋ1 ）3/2 ］＝（σ1 σ2
＋σ3 ）／（σ1 2＋σ2)3/2＝α51であり、 ｋ1 ＝σ1 2＋σ2 ＝σ232 ｋ2 ＝σ1 σ2 ＋σ3 ＝α144 である。
【００８３】インデックス（θ＝α51）を参照して所定
メモリから仮想根を読み出す。仮想根は Ｚ1 ＝α1 Ｚ2 ＝α16 Ｚ3 ＝α34となる。
【００８４】これらをエラー位置に変換すれば次のよう
な結果が得られる。
【００８５】ｘj1＝（α232 ）1/2 ・（α1 ）＋α21 ＝α17 ｘj2＝（α232 ）1/2 ・（α16）＋α21 ＝α12 ｘj3＝（α232 ）1/2 ・（α34）＋α21 ＝α5 それから、このように算出されたエラー位置によりエラ
ー値を算出し、それによりエラー多項式が形成され受信
多項式が訂正される。
【００８６】表１〜表６は三重エラー訂正時使われたＲ
ＯＭテーブルを示したもので、θはＲＯＭのアドレスに
対応し、Ｚ1、Ｚ2、Ｚ3 はＲＯＭに貯蔵される式ｆ
（Ｚ）＝Ｚ3 ＋Ｚ＋θ＝０の根となる。さらに、各要素
において、左側に上付を有するα値は指数表現であり、
右側にへキサデシマルデータは二進データ表現である。
【００８７】
【表１】
【表２】
【表３】
【表４】
【表５】
【表６】
【００８８】
【発明の効果】前述したとおり、本発明はより多くのエ
ラーシンボルを訂正し、実用的な大きさを有するメモリ
を以て三重エラー訂正を実時間に実現することを可能に
する。
【図面の簡単な説明】
【図１】 ディジタルオーディオ記録システムの概要ブ
ロック図である。
【図２】 図１に示したエラー訂正コード器の動作を説
明するための流れ図である。
【図３】 Ｃ１／Ｃ２クロスインタリーブプロダクトコ
ードに対するメモリマップである。
【図４】 本発明の実施例による多重エラー訂正方法を
説明する流れ図である。
【図５】 エラー訂正コードがリードソロモンコードの
条件で図４の第４０３段階を説明するための流れ図であ
る。
【図６】 図５の第５０２段階を説明する流れ図であ
る。
【図７】 エラー形態が受信多項式で位置が知られてい
ないエラー的なシンボルのみを含む純粋エラー形態の場
合の図５における第５０３段階を説明する流れ図であ
る。
【図８】 エラー形態が受信多項式で位置が分かるエラ
ー的なシンボルのみを含む純粋エレージャ形態の場合の
図５における第５０３段階を説明する流れ図である。
【図９】 エラー形態が受信多項式に純粋エラーとエレ
ージャの全てを含む合成エラー形態の場合に図５に示し
た第５０３段階を説明する流れ図である。
【図１０】 本発明の他の実施例による多重エラー訂正
方法を説明する流れ図である。
【図１１】 本発明の実施例によるエラー位置を算出す
る方法を説明する流れ図である。
【図１２】 ３次エラー多項式のエラー位置を算出する
方法を説明する流れ図である。
【符号の説明】
１０１ アナログ−ディジタル変換器、１０２ ソース
コード器、１０３ エラー訂正コード器、１０４ 変調
器、１０５ 信号コード器、１０６ 記録媒体

Claims (29)

    【特許請求の範囲】
  1. 【請求項１】 エラー訂正コードにより符号化された後
    変調コードに基づき変調されたデータに含まれるエラー
    シンボルを訂正する方法において、 変調コードに基づきデータを復調して復調が可能かを示
    す復調フラグと共に復調されたデータを出力する過程
    と、 前記エラー訂正コードに基づき前記多数の復調されたデ
    ータ群により構成される受信ワードを用いてシンドロー
    ム群を算出する過程と、 前記シンドローム群により前記受信ワードに含まれるエ
    ラー的な一シンボル群の数を算出し、前記復調フラグに
    基づき前記受信ワードに含まれるエレージャの数を算出
    する過程と、 前記エラー的なシンボル群の数及びエレージャの数に基
    づきエラー形態を定める過程と、 前記エラー訂正コード及び前記エラー形態により受信ワ
    ードを訂正する過程を備えることを特徴とする多重エラ
    ー訂正方法。
  2. 【請求項２】 前記エラー訂正コードはｔ個のエラー的
    なシンボル群が訂正できるリードソロモンコードである
    ことを特徴とする請求項１項記載の多重エラー訂正方
    法。
  3. 【請求項３】 前記シンドローム群を算出する過程は次
    の式を用いてシンドロームＳk を算出することを特徴と
    する請求項１項記載の多重エラー訂正方法。 Ｓk ＝ｒ（αk+1 ） ここで、ｋは４ｔ−１以下となる全ての自然数になり、
    ｒ（ｘ）は受信ワードに対応し、αは前記リードソロモ
    ンコードに基づいた原始多項式である。
  4. 【請求項４】 前記エラー形態を定める過程はＮerror
    が位置を知っているエラー的なシンボル群の数を示し、
    Ｎerasure がエレージャの数を示すとする時、 Ｎerror がｔより大きいか、あるいはＮerror とＮ
    erasure の和が２ｔより大きい場合は訂正不可能なエラ
    ー形態に分類し、 Ｎerasure が“０”であり、Ｎerror が“０”でない場
    合は少なくとも一つの位置が分からないエラー的なシン
    ボル群を有する純粋エラー形態に分類し、 Ｎerasure が“０”でなくＮerror が“０”の場合は、
    少なくとも一つのエレージャを有する純粋エレージャ形
    態に分類し、 Ｎerasure が“０”でなくＮerror も“０”でない場合
    は、少なくとも一つの位置が分からないエラー的なシン
    ボル群と少なくとも一つのエレージャを有する合成エラ
    ー形態に分類することを特徴とする請求項２項記載の多
    重エラー訂正方法。
  5. 【請求項５】 前記受信ワードを訂正する過程は、 前記シンドローム群を用いて前記エラー的なシンボルの
    数と等しい次数を有するエラー位置多項式の係数群を算
    出する過程と、 エラー位置を算出するため、前記エラー形態により前記
    シンドローム及び前記エレージャの位置を用いて前記エ
    ラー位置多項式の根を算出する過程と、 前記リードソロモンコードに基づき前記シンドローム群
    及び前記エラー位置を用いて前記エラー位置に関連する
    エラー値を算出する過程と、 前記受信ワードを前記エラー位置及びエラー値により変
    換させる過程を備えることを特徴とする請求項４項記載
    の多重エラー訂正方法。
  6. 【請求項６】 前記エラー位置多項式の根を算出する過
    程は、 前記エラー位置多項式の係数を用いてインデックスを算
    出する過程と、 前記インデックスを用いて所定メモリからエラー位置多
    項式の仮想根を読み出す過程と、 所定関係式に基づき前記仮想根をエラー位置多項式の実
    際の根に変換させる過程を備えることを特徴とする請求
    項５項記載の多重エラー訂正方法。
  7. 【請求項７】 前記変調コードはＥＦＭ変調コードであ
    ることを特徴とする請求項１項記載の多重エラー訂正方
    法。
  8. 【請求項８】 前記変調コードはＥＴＭ変調コードであ
    ることを特徴とする請求項１項記載の多重エラー訂正方
    法。
  9. 【請求項９】 第２エラー訂正コード及び第１エラー訂
    正コードに基づき順次に符号化された後変調コードに基
    づき変調されたデータに含まれたエラーシンボル群を訂
    正する方法において、 前記変調コードに基づきデータを復調して復調が可能か
    を示す復調フラグと共に復調されたシンボルを出力する
    過程と、 前記第１エラー訂正コードに基づき前記複数の復調され
    たシンボル群より構成される第１受信ワードを用いて第
    １シンドローム群を算出する過程と、 前記第１シンドローム群及び前記復調フラグ群に基づき
    第１受信ワードの第１エラー形態を定める過程と、 前記第１エラー訂正コード及び第１エラー形態に基づき
    前記第１受信ワードを訂正した後、多数のエラー訂正さ
    れたシンボル群とそのシンボルが訂正されたかを示すエ
    ラーフラグ群を含む復号化されたデータを出力する過程
    と、 前記第２エラー訂正コードに基づき前記多数のエラー訂
    正されたシンボル群を含む第２受信ワードを用いて第２
    シンドローム群を算出する過程と、 前記第２シンドローム群及びその中に存するエラーフラ
    グ群に基づき第２受信ワードの第２エラー形態を定める
    過程と、 前記第２エラー訂正コード及び前記第２エラー形態に基
    づき前記第２受信ワードを訂正する第２エラー訂正過程
    を備えることを特徴とする多重エラー訂正方法。
  10. 【請求項１０】 前記変調コードはＥＦＭ変調コードで
    あることを特徴とする請求項９項記載の多重エラー訂正
    万法。
  11. 【請求項１１】 前記変調コードはＥＴＭ変調コードで
    あることを特徴とする請求項９項記載の多重エラー訂正
    方法。
  12. 【請求項１２】 前記第１エラー訂正コードはｔ1 個の
    エラー的なシンボルが訂正できる第１リードソロモンコ
    ードであり、第２エラー訂正コードはｔ2 個のエラーシ
    ンボルが訂正できる第２リードソロモンコードであるこ
    とを特徴とする請求項９項記載の多重エラー訂正方法。
  13. 【請求項１３】 前記第１シンドローム群を算出する過
    程は次の式を用いてシンドローム群Ｓk を算出すること
    を特徴とする請求項１２項記載の多重エラー訂正方法。 Ｓk ＝ｒ（αk+1 ） ここで、ｋは４ｔ1 −１以下となる全ての自然数にな
    り、ｒ（ｘ）は受信ワードに対応し、αは前記第１リー
    ドソロモンコードに基づいた原始多項式である。
  14. 【請求項１４】 前記第２シンドローム群を算出する過
    程は次の式を用いてシンドローム群Ｓk を算出すること
    を特徴とする請求項１２項記載の多重エラー訂正方法ｏ Ｓk ＝ｒ（αk+1 ） ここで、ｋは４ｔ2 −１以下となる全ての自然数にな
    り、ｒ（ｘ）は受信ワードに対応し、αは前記第２リー
    ドソロモンコードに基づいた原始多項式である。
  15. 【請求項１５】 前記第１エラー形態を定める過程は、 Ｎerror-1 が第１受信ワードに含まれ、その位置を知っ
    ているエラー的なシンボルの数を示し、Ｎerasure-1 が
    第１受信ワードに含まれるエレージャの数を示すとする
    時、 Ｎerror-1 がｔ1 より大きいか、あるいはＮerror-1 と
    Ｎerasure-1 の和が２ｔ1 より大きい場合は訂正不可能
    なエラー形態に分類し、 Ｎerasure-1 が“０”でありＮerror-1 が“０”でない
    場合は少なくとも一つの位置が分からないエラー的なシ
    ンボル群を有する純粋エラー形態に分類し、 Ｎerasure-1 が“０”でなくＮerror-1 が“０”の場合
    は、少なくとも一つのエレージャを有する純粋エレージ
    ャ形態に分類し、 Ｎerasure-1 が“０”でなくＮerror-1 も“０”でない
    場合は、少なくとも一つの位置が分からないエラーシン
    ボル群と少なくとも一つのエレージャを有する合成エラ
    ー形態に分類することを特徴とする請求項１２項記載の
    多重エラー訂正方法。
  16. 【請求項１６】 前記第１受信ワードを訂正する過程
    は、 前記第１シンドローム群を用いて、前記第１受信ワード
    に含まれている前記エラー的なシンボル群の数と等しい
    次数を有する第１エラー位置多項式の係数群を算出する
    過程と、 前記第１エラー形態により前記第１シンドローム群及び
    前記第１受信ワードに含まれる前記エレージャの位置を
    用いて前記第１エラー位置群を算出する過程と、 前記第１リードソロモンコードに基づき前記第１シンド
    ローム群及び前記第１エラー位置を用いて前記第１エラ
    ー位置群に関連する第１エラー値を算出ずる過程と、 前記第１受信ワードを前記第１エラー位置群及び第１エ
    ラー値群により変換させる過程を備えることを特徴とす
    る請求項１５項記載の多重エラー訂正方法。
  17. 【請求項１７】 前記第１エラー位置を算出する過程
    は、 前記第１エラー位置多項式の係数群を用いて第１インデ
    ックスを算出する過程と、 前記第１インデックスを用いて所定メモリから第１エラ
    ー位置多項式の仮想根を読み出す過程と、 所定関係式に基づき前記仮想根を第１エラー位置に変換
    させる過程を備えることを特徴とする請求項１６項記載
    の多重エラー訂正方法。
  18. 【請求項１８】 前記エラー形態を定める過程は、 Ｎerror-2 が第２受信ワードに含まれ、その位置を知っ
    ているエラー的なシンボルの数を示し、Ｎerasure-2 が
    第２受信ワードに含まれるエレージャの数を示すとする
    時、 Ｎerror-2 がｔ2 より大きいか、あるいはＮerror-2 と
    Ｎerasure-2 の和が２ｔ2 より大きい場合は訂正不可能
    なエラー形態に分類し、 Ｎerasure-2 が“０”でありＮerror-2 が“０”でない
    場合は少なくとも一つの位置が分からないエラー的なシ
    ンボル群を有する純粋エラー形態に分類し、 Ｎerasure-2 が“０”でなくＮerror-2 が“０”の場合
    は、少なくとも一つのエレージャを有する純粋エレージ
    ャ形態に分類し、 Ｎerasure-2 が“０”でなくＮerror-2 も“０”でない
    場合は、少なくとも一つの位置が分からないエラー的な
    シンボル群と少なくとも一つのエレージャを有する合成
    エラー形態に分類することを特徴とする請求項１２項記
    載の多重エラー訂正方法。
  19. 【請求項１９】 前記第２受信ワードを訂正する過程
    は、 前記第２シンドローム群を用いて、前記第２受信ワード
    に含まれている前記エラー的なシンボル群の数と等しい
    次数を有する第２エラー位置多項式の係数群を算出する
    過程と、 前記第２エラー形態により前記第２シンドローム群及び
    前記第２受信ワードに含まれる前記エレージャの位置を
    用いて前記第２エラー位置群を算出する過程と、 前記第２リードソロモンコードに基づき前記第２シンド
    ローム群及び前記第２エラー位置を用いて前記第２エラ
    ー位置群に関連した第２エラー値群を算出する過程と、 前記第２受信ワードを前記第２エラー位置群及び第２エ
    ラー値群により変換させる過程を備えることを特徴とす
    る請求項１８項記載の多重エラー訂正方法。
  20. 【請求項２０】 前記前記第２エラー位置多項式の根を
    算出する過程は、 前記第２エラー位置多項式の係数を用いて第２インデッ
    クスを算出する過程と、 前記第２インデックスを用いて所定メモリから第２エラ
    ー位置多項式の仮想根を読み出す過程と、 所定関係式に基づき前記仮想根を第２エラー位置群に変
    換させる過程を備えることを特徴とする請求項１９項記
    載の多重エラー訂正方法。
  21. 【請求項２１】 エラー訂正コードに基づき符号化され
    たデータに含まれるエラー的なシンボル群を訂正する方
    法において、 データを用いてシンドロームを算出する過程と、 前記シンドローム群に基づきエラー位置多項式の係数群
    を算出する過程と、前記係数群に基づきインデックスを
    算出する過程と、 前記インデックスに関連する所定のメモリから前記エラ
    ー位置多項式の複数の仮想根群を読み出す過程と、 所定関係式に基づき前記仮想根群をエラー位置群に変換
    する過程と、 前記シンドローム群及び前記エラー位置群に基づきエラ
    ー値群を算出する過程と、 前記エラー位置群及び前記エラー値群に基づき前記デー
    タをエラー訂正されたデータに変換する過程を備えるこ
    とを特徴とする多重エラー訂正方法。
  22. 【請求項２２】 前記エラー訂正コードは三重エラー的
    なシンボル群が訂正できるリードソロモンコードである
    ことを特徴とする請求項２１項記載の多重エラー訂正方
    法。
  23. 【請求項２３】 前記インデックスを算出する過程は次
    の式によりなることを特徴とする請求項２２項記載の多
    重エラー訂正方法。 θ：ｋ2 ／［（ｋ1 ）3/2 ］ 但し、ｋ1 はσ1 2＋σ2 であり、ｋ2 はσ1 σ2 ＋σ3
    であり、σ1 、σ2 、σ3 は前記エラー位置を示す。
  24. 【請求項２４】 前記仮想根をエラー位置に変換する過
    程は次の式によりなることを特徴とする請求項２３項記
    載の多重エラー訂正方法。 ｘj1＝（ｋ1 ）1/2 ・ｚ1 ＋σ1 ｘj2＝（ｋ1 ）1/2 ・ｚ2 ＋σ1 ｘj3＝（ｋ1 ）1/2 ・ｚ3 ＋σ1 但し、ｚ1 ，ｚ2 ，ｚ3 は前記仮想根を示し、ｘj1、ｘ
    j2、ｘj3は前記エラー位置を示す。
  25. 【請求項２５】 ｔ個のエラー的なシンボル群が訂正で
    きるリードソロモンコードに基づき符号化されたデータ
    に含まれるエラー的なシンボル群を訂正する方法におい
    て、 次の式によりシンドローム群Ｓ0、Ｓ1、・・・、Ｓ2t-1
    を算出する過程と、 データを用いてシンドロームを算出する過程と、 Ｓk ＝ｒ（αk+1 ） ここで、ｋは２ｔ2 −１以下となる全ての自然数にな
    り、ｒ（ｘ）は前記データにより構成される受信多項式
    を示し、αは前記リードソロモンコードの原始多項式で
    ある。前記シンドローム群に基づきデータに含まれたエ
    ラー的なシンボル群の数を算出する過程と、 前記エラー的なシンボルの数ｖをｔ以下とする時、次の
    式によりエラー位置多項式σv ＋σv-1 ｘ＋σv-2 ｘ2
    ＋・・・＋ｘv の係数群σ1 、σ2 、σ3 を算出する過
    程と、 【数１】 前記係数群σ1，σ2，・・・、σv に基づきイデックス
    を算出する過程と、 前記インデックスに関連する所定メモリから前記エラー
    位置多項式の複数の仮想根群を読み出す過程と、 所定関係式に基づき前記仮想根群をエラー位置群ｘj1，
    ｘj2，・・・ｘjvに変換する過程と、 次の式によりエラー値を算出する過程と、 【数２】 但し、ｊはｖ以下の自然数であり、前記Ω（ｘ）はσv
    ＋（σv Ｓ0 ＋σv-1）ｘ＋（σv Ｓ1 ＋σv-1 Ｓ0 ＋
    σv-2 ）ｘ2 ＋・・・＋（σv Ｓv-1 ＋σv-1Ｓv-2 ＋
    ・・・＋１）ｘv であり、ｅ1 ないしｅv はエラー値を
    示す。前記エラー位置群及びエラー値群に基づき前記デ
    ータをエラー訂正されたデータに変換する過程を備える
    ことを特徴とする多重エラー訂正方法。
  26. 【請求項２６】 前記ｔは３であることを特徴とする請
    求項２５項記載の多重エラー訂正方法。
  27. 【請求項２７】 前記インデックスを算出する過程は次
    の式を用いてインデックスを算出することを特徴とする
    請求項２６項記載の多重エラー訂正方法。 θ＝ｋ2 ／［（ｋ1 ）3/2 ］ 但し、ｋ1 はσ1 2＋σ2 であり、ｋ2 はσ1 σ2 ＋σ3
    であり、σ1 、σ2 、σ3 は前記エラー位置を示す。
  28. 【請求項２８】 前記仮想根群Ｚ1 、Ｚ2 、Ｚ3 をエラ
    ー位置群ｘj1，ｘj2，ｘj3に変換させる過程は次の式に
    よりなることを特徴とする請求項２７項記載の多重エラ
    ー訂正方法。 ｘj1＝（ｋ1 ）1/2 ・Ｚ1 ＋σ1 ｘj2＝（ｋ1 ）1/2 ・Ｚ2 ＋σ1 ｘj3＝（ｋ1 ）1/2 ・Ｚ3 ＋σ1 但し、Ｚ1 ，Ｚ2 ，Ｚ3 は前記仮想根を示し、ｘj1，ｘ
    j2，ｘj3は前記エラー位置を示す。
  29. 【請求項２９】 前記所定メモリに貯蔵されている仮想
    根はｆ（Ｚ）＝Ｚ3＋Ｚ＋θ＝０（但し、θはインデッ
    クスを示す）の根であることを特徴とする請求項２８項
    記載の多重エラー訂正方法。
JP5251988A 1992-10-07 1993-10-07 多重エラー訂正方法 Pending JPH06208767A (ja)

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
KR1019920018409A KR950002304B1 (ko) 1992-10-07 1992-10-07 다중 오류정정 방법
KR1992-018409 1992-10-07

Publications (1)

Publication Number Publication Date
JPH06208767A true JPH06208767A (ja) 1994-07-26

Family

ID=19340772

Family Applications (1)

Application Number Title Priority Date Filing Date
JP5251988A Pending JPH06208767A (ja) 1992-10-07 1993-10-07 多重エラー訂正方法

Country Status (5)

Country Link
US (1) US5450421A (ja)
EP (1) EP0592229B1 (ja)
JP (1) JPH06208767A (ja)
KR (1) KR950002304B1 (ja)
DE (1) DE69332556T2 (ja)

Families Citing this family (21)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP3071828B2 (ja) * 1995-04-12 2000-07-31 株式会社 東芝 誤り訂正積符号ブロックを生成するためのデータ処理方法と該データを記録媒体に記録するためのデータ処理方法及び該データの処理装置
TW311189B (en) * 1996-09-30 1997-07-21 United Microelectronics Corp The error-corrected decoding method and its apparatus for Reed-Soloman code
NL1006174C2 (nl) * 1997-04-17 1998-12-01 United Microelectronics Corp Foutdecoderingswerkwijze alsmede apparaat voor het decoderen.
JP3502559B2 (ja) * 1999-02-05 2004-03-02 松下電器産業株式会社 消失訂正方法、及び消失訂正回路
US6625774B1 (en) * 1999-10-29 2003-09-23 Stmicroelectronics, Inc. Redundancy system and method for locating errors in interleaved code words
KR100378181B1 (ko) * 2000-06-09 2003-03-29 삼성전자주식회사 Ｅｆｍ/ｅｆｍ+ 디코딩에 의해 검출된 에러위치를 이용한ｃ1/ｐｉ 워드의 에러정정 방법 및 장치
FR2817418B1 (fr) * 2000-11-27 2003-02-21 Matra Nortel Communications Procede de decodage d'un bloc de symboles et dispositif mettant en oeuvre un tel procede
US6748567B1 (en) * 2001-05-01 2004-06-08 Zettacom, Inc. Method and system for error correction over serial link
US7389463B2 (en) * 2001-05-29 2008-06-17 Thomson Licensing Hierarchical block coding for a packet-based communications system
US20030061558A1 (en) * 2001-09-25 2003-03-27 Fackenthal Richard E. Double error correcting code system
EP1537674A4 (en) * 2002-06-21 2007-04-04 Thomson Licensing PROCEDURE FOR FORWARD FAULT CORRECTION
CN1628351A (zh) * 2003-06-02 2005-06-15 松下电器产业株式会社 交错数据纠错方法及纠错装置
KR100519771B1 (ko) * 2003-07-10 2005-10-07 삼성전자주식회사 에러 정정 디코딩 방법 및 그 장치
FR2861517B1 (fr) * 2003-10-23 2006-01-27 Thomson Licensing Sa Methode de reconstruction de paquets perdus et appareils implementant la methode
US7543218B2 (en) * 2004-01-31 2009-06-02 Samsung Electronics Co., Ltd. DVD decoding method and apparatus using selective po-correction
US7328395B1 (en) 2004-04-13 2008-02-05 Marvell International Ltd. Iterative Reed-Solomon error-correction decoding
US7444582B1 (en) 2004-10-27 2008-10-28 Marvell International Ltd. Architecture and control of reed-solomon error-correction decoding
US7404133B2 (en) 2004-12-12 2008-07-22 Hewlett-Packard Development Company, L.P. Error detection and correction employing modulation symbols satisfying predetermined criteria
WO2007026848A1 (ja) * 2005-09-01 2007-03-08 Matsushita Electric Industrial Co., Ltd. 誤り訂正方法
US8468431B2 (en) * 2010-07-01 2013-06-18 Densbits Technologies Ltd. System and method for multi-dimensional encoding and decoding
US9312886B2 (en) * 2013-09-20 2016-04-12 Seagate Technology Llc Storage device with multiple coding redundancies

Family Cites Families (17)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CA1170776A (en) * 1980-07-18 1984-07-10 Yoichiro Sako Method of error correction of blocks of data
JPS58111539A (ja) * 1981-12-25 1983-07-02 Sony Corp エラ−訂正方法
JPS5961332A (ja) * 1982-09-30 1984-04-07 Nec Corp 誤り訂正回路
JPS6055564A (ja) * 1983-09-06 1985-03-30 Toshiba Corp エラ−訂正回路
US4653051A (en) * 1983-09-14 1987-03-24 Matsushita Electric Industrial Co., Ltd. Apparatus for detecting and correcting errors on product codes
JPH0812612B2 (ja) * 1983-10-31 1996-02-07 株式会社日立製作所 誤り訂正方法及び装置
NL8400630A (nl) * 1984-02-29 1985-09-16 Philips Nv Decodeerinrichting voor een stroom van codesymbolen die woordsgewijze beschermd zijn door een dubbele reed-solomon-code met een minimum hamming-afstand van 5 over de codesymbolen en een verbladeringsmechanisme tussen de beide codes, alsmede speler voorzien van zo een decodeerinrichting.
NL8400629A (nl) * 1984-02-29 1985-09-16 Philips Nv Snelle decodeur voor reed-solomon-codes, welke mede als encodeur te gebruiken is, alsmede opname/reproduktie-apparaat voorzien van zo een encodeur/decodeur.
JPS6116629A (ja) * 1984-07-02 1986-01-24 Nec Home Electronics Ltd リ−ドソロモン符号・復号方式における訂正実行方式
NL8403818A (nl) * 1984-12-17 1986-07-16 Philips Nv Werkwijze en inrichting voor het decoderen van door een reed-solomon-code beschermde informatiestroom.
JPS62246180A (ja) * 1986-04-18 1987-10-27 Olympus Optical Co Ltd 誤り訂正方式
US4875211A (en) * 1986-12-10 1989-10-17 Matsushita Electric Industrial Co., Ltd. Galois field arithmetic logic unit
JPS63193723A (ja) * 1987-02-06 1988-08-11 Sony Corp リ−ドソロモン符号の復号方法
JP2605269B2 (ja) * 1987-02-06 1997-04-30 ソニー株式会社 エラー訂正方法
AU622626B2 (en) * 1987-06-03 1992-04-16 Sony Corporation Method of processing data
US4821268A (en) * 1987-10-26 1989-04-11 Cyclotomics, Inc. Soft decision Reed-Solomon decoder
US4890286A (en) * 1987-12-11 1989-12-26 Sanyo Electric Co., Ltd. Method and apparatus for decoding error correcting code

Also Published As

Publication number Publication date
DE69332556T2 (de) 2003-11-20
EP0592229B1 (en) 2002-12-11
DE69332556D1 (de) 2003-01-23
KR950002304B1 (ko) 1995-03-16
EP0592229A3 (en) 1995-06-14
EP0592229A2 (en) 1994-04-13
KR940010545A (ko) 1994-05-26
US5450421A (en) 1995-09-12

Similar Documents

Publication Publication Date Title
EP0592229A2 (en) Multiple error correcting method
JP4194850B2 (ja) 部分的に演繹的に分かる情報の符号化及び復号
US6963296B2 (en) Recording method, recording apparatus, transmitting apparatus, reproducing method, reproducing apparatus, receiving apparatus, recording medium, and transmission medium
JPH0652621B2 (ja) デイスクの誤り訂正コード付与方法
JP4290881B2 (ja) エラー訂正コードを含む磁気媒体上へのデータの格納のための方法及び装置
CN101849361B (zh) 用于调制编码及解码的方法和系统
US6229458B1 (en) Rate 32/34 (D=0, G=9/I=9) modulation code with parity for a recording channel
JP2002509331A5 (ja)
US4989211A (en) Sector mis-synchronization detection method
JP2000503513A (ja) 変形リードソロモン符号選択および符号化システム
CN100380495C (zh) 使用降低复杂度的码表的解调装置和方法
US5574448A (en) Method and apparatus for encoding data with variable block lengths
JP4135497B2 (ja) データ再生方法及びデータ再生装置
JP3768149B2 (ja) 光記録媒体、データ記録装置及びデータ記録方法
JPH082028B2 (ja) 符号訂正装置
US7159165B2 (en) Optical recording medium, data recording or reproducing apparatus and data recording or reproducing method used by the data recording or reproducing apparatus
JPH04365139A (ja) 誤り訂正処理用シンドローム演算回路
JP2000067532A (ja) 誤り訂正符号化／復号化方式及び誤り訂正符号化／復号化装置
US6694473B1 (en) Parallel signal decoding method
JP2002118471A (ja) 記録再生装置及び誤り訂正符号化方法並びに情報記録方法
JP2000187948A (ja) 誤り訂正符号化／復号化方式及び誤り訂正符号化／復号化装置
US20020157057A1 (en) Optical information recording medium and data recording apparatus thereon
CN1153209C (zh) 记录载体及其阅读装置
JP2660970B2 (ja) 符号誤り訂正回路
JPH08287618A (ja) 記録再生装置

Legal Events

Date Code Title Description
A601 Written request for extension of time

Free format text: JAPANESE INTERMEDIATE CODE: A601

Effective date: 20070419

A602 Written permission of extension of time

Free format text: JAPANESE INTERMEDIATE CODE: A602

Effective date: 20070424

A521 Written amendment

Free format text: JAPANESE INTERMEDIATE CODE: A523

Effective date: 20070517