(57)【特許請求の範囲】
【請求項１】
３重以下エラー／６重以下消し痕を訂正するエラー訂正方法において、
受信符号語からシンドロームＳ０〜Ｓ５を計算するシンドローム計算段階と、
前記計算されたシンドロームＳ０〜Ｓ５が全て０であるかを判断する第１判断段階と、
前記計算されたシンドロームＳ０〜Ｓ５が全て０なら前記エラーのないものと決める第１エラー決定段階と、
前記計算されたシンドロームＳ０〜Ｓ５が全て０でない場合、前記計算されたシンドロームＳ０〜Ｓ２が全て０であり、前記計算されたシンドロームＳ３〜Ｓ５のうち少なくとも１つは０でないかを判断する第２判断段階と、
前記計算されたシンドロームＳ０〜Ｓ２が全て０であり、前記計算されたシンドロームＳ３〜Ｓ５のうち少なくとも１つが０でなければ、エラー訂正不能と決定する第２エラー決定段階と、
前記計算されたシンドロームＳ０〜Ｓ２が全て０でなくても、前記計算されたシンドロームＳ３〜Ｓ５が全て０なら、前記計算されたシンドロームＳ０〜Ｓ２のうち何れか２つが０であり、残り１つが０でないかに応じて前記エラー位置多項式の係数σ１、σ２及びσ３を別に計算し、計算された前記係数から求めたエラー位置が符号語内に入るかによりエラー形態及びエラー訂正の可否を判別し、エラー値を計算する第１エラー判別及び計算段階と、
前記第１エラー判別及び計算段階から前記計算されたシンドロームＳ０〜Ｓ２のうち２つが０でなければ、前記Ｓ０及びＳ１の値に相応して計算されたシンドロームＳ０〜Ｓ３を利用して求めた第１及び第２シンドローム式が０であることにより計算したエラー位置多項式の前記係数及び前記シンドロームＳ０〜Ｓ５を用いてエラー形態及びエラー訂正の可否を判別し、エラー位置及びエラー値を計算する第２エラー判別及び計算段階とを具備することを特徴とするエラー訂正方法。
【請求項２】
前記第１エラー判別及び計算段階は、
前記計算されたシンドロームＳ0〜Ｓ2が全て０でないか、または前記計算されたシンドロームＳ3〜Ｓ5が全て０ならば、前記計算されたシンドロームＳ1及びＳ2が全て０であり、Ｓ0が０でないかを判断する第３判断段階と、
前記Ｓ1及びＳ2が０であり、前記Ｓ0が０でなければ、下記の式により前記エラー位置多項式係数σ1、σ2、σ3を計算する第１係数計算段階と、
【数１】
0004022293.tif 000031
前記計算されたシンドロームＳ1及びＳ2が全て０でないか、またはＳ0が０ならば、前記Ｓ0及びＳ2が全て０であり、前記Ｓ1が０でないかを判断する第４判断段階と、
前記Ｓ0及びＳ2が０であり、前記Ｓ1が０でなければ、下記の式により前記エラー位置多項式の係数σ1、σ2、σ3を計算する第２係数計算段階と、
【数２】
0004022293.tif 000032
前記Ｓ0及びＳ2が全て０でないか、または前記Ｓ1が０なら、前記Ｓ0及びＳ1が全て０であり、前記Ｓ2が０でないかを判断する第５判断段階と、
前記Ｓ0及びＳ1が全て０であり、前記Ｓ2が０でなければ、下記の式により前記エラー位置多項式の係数σ1、σ2、σ3を計算する第３係数計算段階と、
【数３】
0004022293.tif 000033
前記第１、２及び３係数計算段階後に、エラーが少なくとも３つ以上発生したことと仮定する第１エラー数仮定段階と、
前記第１エラー数仮定段階後に、前記第１、２及び３係数計算段階から計算された前記σ1、σ2、σ3を用いて前記エラー位置を計算する第１計算段階と、
前記エラー位置が符号語内にあるかを判断する第６判断段階と、
前記エラー位置が前記符号語内にあると、エラーが３つ発生したと決定する第３エラー決定段階と、
前記エラー位置が前記符号語内になければ、エラー訂正不能と決定する第４エラー決定段階とを具備し、
前記Ｓ0〜Ｓ2のうち２つが０でなければ、前記第２エラー判別及び計算段階に進行することを特徴とする請求項１に記載のエラー訂正方法。
【請求項３】
前記エラー訂正方法は、前記第３エラー決定段階後に、前記エラー値を計算する第２計算段階をさらに具備することを特徴とする請求項２に記載のエラー訂正方法。
【請求項４】
前記第２エラー判別及び計算段階は、
前記計算されたシンドロームＳ０〜Ｓ２のうち２つが０でなければ、前記計算されたシンドロームＳ０が０であり、Ｓ１が０でないかを判断する第７判断段階と、
前記Ｓ０でないか、またはＳ１が０なら、前記Ｓ０が０でないかを判断する第８判断段階と、
前記Ｓ０が０でなければ、下記の式により前記第１シンドローム式Ａ及び前記第２シンドローム式Ｂを計算する第３計算段階と、
【数４】
0004022293.tif 000034
（ここで、σはＳ１／Ｓ０である。）
前記Ａと前記Ｂとが全て０でないかを判断する第９判断段階と、
前記Ａ及び前記Ｂが全て０でないか、または前記Ｓ０が０であり、Ｓ１が０でないと、下記の式により前記エラー位置多項式の係数σ１’とσ２’及びＤを計算する第４計算段階と、
【数５】
0004022293.tif 000035
（ここで、Δ＝Ｓ１２＋Ｓ０・Ｓ２≠０である。）
前記Ａと前記Ｂのうち少なくとも１つが０なら、前記Ａと前記Ｂが全て０であるかを判断する第１０判断段階と、
前記Ａと前記Ｂが全て０なら、エラーが１つ発生したと決定し、エラー位置を前記σとし、エラー値を前記シンドロームＳ０に決定する第５エラー決定段階と、
前記Ａと前記Ｂのうち一つが０なら、エラー訂正不能と決定する第６エラー決定段階と、
前記第３計算段階で求めた前記Ｄが０であるかを判断する第１１判断段階と、
前記Ｄが０なら、エラーが２つ発生したと決定する第７エラー決定段階と、
前記Ｄが０でなければ、エラーが３つ発生したと仮定する第２エラー数仮定段階と、
前記第２エラー数仮定段階後に下記の式により前記エラー位置多項式の係数Σ１、Σ２及びΣ３を計算する第５計算段階と、
【数６】
0004022293.tif 000036
前記Σ１、Σ２及びΣ３から前記エラー位置を計算する第６計算段階と、
前記第６計算段階から計算された前記エラー位置が前記符号語内にあるかを判断する第１２判断段階と、
前記エラー位置が前記符号語内にあると前記エラーが３つ発生したと決定する第８エラー決定段階とを具備し、
前記エラー位置が前記符号語内になければ、第６エラー決定段階に進行することを特徴とする請求項１乃至３のうち何れか１項に記載のエラー訂正方法。
【請求項５】
前記エラー訂正方法は前記第７エラー決定段階後に、前記σ1’及びσ2’から前記エラー位置及び前記エラー値を計算する第７計算段階をさらに具備することを特徴とする請求項４に記載のエラー訂正方法。
【請求項６】
前記エラー訂正方法は前記第８エラー決定段階後に、前記エラー値を求める段階をさらに具備することを特徴とする請求項４に記載のエラー訂正方法。
【請求項７】
前記第８判断段階において、前記Ｓ0が０なら、エラー訂正不能と決定する段階をさらに具備することを特徴とする請求項４に記載のエラー訂正方法。
【請求項８】
３重以下エラー／６重以下消し痕を訂正するエラー訂正装置において、
受信符号語を貯蔵する受信符号語貯蔵手段と、
前記受信符号語貯蔵手段に貯蔵された前記受信符号語を入力してシンドロームＳ０〜Ｓ５を発生するためのシンドローム発生手段と、
第１制御信号に応答して下記の式のようなエラー位置多項式係数σ１、σ２、σ３を計算し、
【数７】
0004022293.tif 000037
第２制御信号に応答して下記の式のような前記エラー位置多項式の係数σ１、σ２、σ３を計算し、
【数８】
0004022293.tif 000038
第３制御信号に応答して下記の式のような前記エラー位置多項式の係数σ１、σ２、σ３を計算し、
【数９】
0004022293.tif 000039
第４制御信号に応答して下記の式のように第１シンドローム式Ａ及び第２シンドローム式Ｂを計算し、
【数１０】
0004022293.tif 000040
（ここで、σはＳ１／Ｓ０である。）
第５制御信号に応答して下記の式のように前記エラー位置多項式の係数σ１’、σ２’及びＤを計算し、
【数１１】
0004022293.tif 000041
（ここで、Δ＝Ｓ１２＋Ｓ０・Ｓ２≠０である。）
第６制御信号に応答して前記σ１’及びσ２’からエラー位置及びエラー値を計算し、
第７制御信号に応答して下記の式のようにエラー位置多項式の係数Σ１、Σ２及びΣ３を計算し、
【数１２】
0004022293.tif 000042
前記Σ１、Σ２及びΣ３からエラー位置及びエラー値を計算する演算手段と、
前記シンドロームのうちＳ１及びＳ２が０であり、Ｓ０は０でなければ第１制御信号を、前記Ｓ０及びＳ２が０であり、前記Ｓ１が０でなければ第２制御信号を、前記Ｓ０及びＳ１が全て０であり、前記Ｓ２が０でなければ第３制御信号を、前記シンドロームＳ０〜Ｓ２のうち２つが０でなく、前記Ｓ０が０でないか、またはＳ１が０なら第４制御信号を、前記Ａ及び前記Ｂが全て０でなければ第５制御信号を、前記Ｄが０なら第６制御信号を、前記Ｄが０でなければ第７制御信号を各々発生する演算制御手段と、
前記シンドロームＳ０〜Ｓ５が全て０ならエラー無しと判断し、前記シンドロームＳ０〜Ｓ２が全て０であり、前記シンドロームＳ３〜Ｓ５が全て０でなければエラー訂正不能と判断し、前記σ１、σ２及びσ３から求めた前記エラー位置が全て符号語内にあるとエラーが３つ発生したと判断し、符号語内にないと、エラー訂正不能と判断し、前記Ａ及び前記Ｂが全て０なら前記エラーが１つ発生したと判断し、前記Ｄが０なら前記エラーが２つ発生したと判断し、前記Ｄが０でなければ前記エラーが３つ発生したと判断する判断制御手段と、前記判断制御手段の判断結果により１、２、３重エラー訂正動作を行うためのエラー訂正手段とを具備することを特徴とするエラー訂正回路。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明はエラー訂正方法及び装置に係り、特にさらに高速で安定に３重エラー／６重消し痕を訂正するエラー訂正方法及び装置に関する。
【０００２】
【従来の技術】
米国特許番号第４，１４２，１７４と韓国特許公開第９２−１８５４５号（出願人：三星電子（株））を見ると、２重エラー／３重エラー／４重エラーのエラー位置を探すためにエラー位置多項式上の係数を求めるべきであるが、その古典的な方式としてバーレカンプ−メッセイ（Berlekamp-Messay）方式を使用したり、またはニュートン（Newton）恒等式の関係式を用いて連立方程式を解かなければならない。即ち、２重エラー発生時エラー位置多項式σ（ｘ）は次の式１のようである。
【０００３】
【数１３】
0004022293.tif 000002
ここで、σ（ｘ）の係数σ1、σ2を求めるためにはニュートン恒等式から導かれた次の式２の２次行列式を解くべきである。
【０００４】
【数１４】
0004022293.tif 000003
ここで、Ｓ0〜Ｓ3はシンドローム（syndrom）を各々示す。
【０００５】
また、３重エラー発生時エラー位置多項式σ（ｘ）は次の式３のようである。
【０００６】
【数１５】
0004022293.tif 000004
ここで、エラー位置多項式ａ（ｘ）の係数σ1、σ2、σ3を求めるためにはニュートン恒等式から導かれた次の式４の３次行列式を解くべきである。
【０００７】
【数１６】
0004022293.tif 000005
ここで、Ｓ0〜Ｓ5は受信符号語から求めたシンドロームを示す。
【０００８】
この際、下記の式５のようなエラー位置多項式σ（ｘ）の係数σ1、σ2、σ3は次の式６のようである。
【０００９】
【数１７】
0004022293.tif 000006
前記式５からエラー数を判定するために既知の技術を使用する。特に、韓国特許公開第９４−４９８０号、９５−３４２０２号及び９６−１１６８９号から説明された方法を使用すれば、最も確実であるが、エラー数判定式を立てるために非常に多くの演算時間を必要とする問題点がある。
【００１０】
例えば、韓国特許公開第９６−１１６８９号では２重エラー訂正時に求めたσ1、σ2係数値を用いて３重エラー訂正時のσ1、σ2、σ3係数値を求め、かつこれを用いて４重エラー訂正時のエラー位置多項式の係数σ1、σ2、σ3、σ4を求める方法を使用して演算回数を減らした。しかし、これは位置多項式の係数σ1、σ2を求めるため、依然として複雑な演算を行う問題点を有している。
【００１１】
一方、ソースデジタルオーディオデータをそのままＥＣＣエンコーディング／デコーディングして使用したＣＤＰ（compact disc player）、ＤＡＴ（digital audio tape）においては実際に２重エラー訂正／４消去または６消去訂正のみでエラー訂正を終え、以降訂正できなかったデータは補間処理を通いて使用者には高音質のオーディオデータが提供できた。しかし、ＤＣＣ（digital compact cassette）、ＭＤ（mini disc）、ビデオ−ＣＤ（compact disc）等限定された記録媒体にオーディオデータだけでなくグラフィックデータ、映像データまたは文字まで記録、再生するためにはデータ圧縮アルゴリズムが必要となった。このような圧縮されたデータはソースデジタルオーディオデータのような実時間データでなく周波数領域から処理されたデータなので、エラーが発生して訂正できない場合に実際の使用者に提供される音声／映像データにはその影響が非常に大きかった。このような問題点を克服するためにＤＣＣ／ＭＤでは実際的に３重エラー訂正を使用したことがあり、このようなエラー訂正能力の補強はさらに切実である。
【００１２】
以下、従来のＣＤ−ＲＯＭまたはＤＶＤ−ＲＯＭシステムにおいてエラー訂正符号化によりデータ伝送速度が減少されることを添付した図面に基づき次のように説明する。
【００１３】
図１はＣＤ−ＲＯＭまたはＤＶＤ−ＲＯＭの全体システムのブロック図であって、ディスク１０、ＣＤＰ−ＤＳＰ（ＣＤＰ：Compact Disk Player−ＤＳＰ：Digital Signal Processor）またはＤＶＤ−デコーダ１２、ＣＤ−ＲＯＭデコーダまたはＤＶＤ−ＲＯＭホストインターフェース（Ｉ／Ｆ：Interface）１４、Ａ／Ｖ（Audio/Video）デコーダ１６及びホスト（host）１８で構成される。
【００１４】
図１に示されたＣＤ−ＤＳＰまたはＤＶＤ−デコーダ１２はディスク１０から読出したデータをＣＤ−ＲＯＭデコーダまたはＤＶＤ−ＲＯＭホストＩ／Ｆ１４またはＡ／Ｖデコーダ１６に伝送する際に、ＣＤＰ−ＤＳＰまたはＤＶＤ−デコーダ１２の内部機能の中データバッファリングやデータの伝送は高速処理が可能であるが、ＣＤ−ＲＯＭデコーダまたはＤＶＤ−ＲＯＭホストＩ／Ｆ１６からデータを復号化するに時間が多くかかるため、データ伝送速度が減少される問題点がある。
【００１５】
【発明が解決しよううとする課題】
本発明が解決しようとする技術的課題は、シンドローム値に応じてエラー位置多項式の係数を簡単に求めることにより、高速で安定にエラーを訂正するエラー訂正方法を提供するにある。
【００１６】
本発明の他の技術的課題は、前記エラー訂正方法を行うエラー訂正装置を提供するにある。
【００１７】
【課題を解決するための手段】
前記課題を解決するために本発明による３重以下エラー／６重以下消し痕を訂正するエラー訂正方法は、受信符号語からシンドロームＳ０〜Ｓ５を計算するシンドローム計算段階と、前記計算されたシンドロームＳ０〜Ｓ５が全て０であるかを判断する第１判断段階と、前記計算されたシンドロームＳ０〜Ｓ５が全て０なら前記エラーのないものと決める第１エラー決定段階と、前記計算されたシンドロームＳ０〜Ｓ５が全て０でない場合、前記計算されたシンドロームＳ０〜Ｓ２が全て０であり、前記計算されたシンドロームＳ３〜Ｓ５のうち少なくとも１つは０でないかを判断する第２判断段階と、前記計算されたシンドロームＳ０〜Ｓ２が全て０であり、前記計算されたシンドロームＳ３〜Ｓ５のうち少なくとも１つが０でなければ、エラー訂正不能と決定する第２エラー決定段階と、前記計算されたシンドロームＳ０〜Ｓ２が全て０でなくても、前記計算されたシンドロームＳ３〜Ｓ５が全て０なら、前記計算されたシンドロームＳ０〜Ｓ２のうち何れか２つが０であり、残り１つが０でないかに応じて前記エラー位置多項式の係数σ１、σ２及びσ３を別に計算し、計算された前記係数から求めたエラー位置が符号語内に入るかによりエラー形態及びエラー訂正の可否を判別し、エラー値を計算する第１エラー判別及び計算段階と、前記第１エラー判別及び計算段階から前記計算されたシンドロームＳ０〜Ｓ２のうち２つが０でなければ、前記Ｓ０及びＳ１の値に相応して計算されたシンドロームＳ０〜Ｓ３を利用して求めた第１及び第２シンドローム式が０であることにより計算したエラー位置多項式の前記係数及び前記シンドロームＳ０〜Ｓ５を用いてエラー形態及びエラー訂正の可否を判別し、エラー位置及びエラー値を計算する第２エラー判別及び計算段階よりなることが望ましい。
【００１８】
前記他の課題を解決するために、３重以下エラー／６重以下消し痕を訂正するエラー訂正装置は、受信符号語を貯蔵する受信符号語貯蔵手段と、前記受信符号語貯蔵手段に貯蔵された前記受信符号語を入力してシンドロームＳ０〜Ｓ５を発生するためのシンドローム発生手段と、第１制御信号に応答して下記の式のようなエラー位置多項式係数σ１、σ２、σ３を計算し、
【数１８】
0004022293.tif 000007
第２制御信号に応答して下記の式のような前記エラー位置多項式の係数σ１、σ２、σ３を計算し、
【数１９】
0004022293.tif 000008
第３制御信号に応答して下記の式のような前記エラー位置多項式の係数σ１、σ２、σ３を計算し、
【数２０】
0004022293.tif 000009
第４制御信号に応答して下記の式のように第１シンドローム式Ａ及び第２シンドローム式Ｂを計算し、
【数２１】
0004022293.tif 000010
（ここで、σはＳ１／Ｓ０である。）
第５制御信号に応答して下記の式のように前記エラー位置多項式の係数σ１’、σ２’及びＤを計算し、
【数２２】
0004022293.tif 000011
（ここで、Δ＝Ｓ１２＋Ｓ０・Ｓ２≠０である。）
第６制御信号に応答して前記σ１’及びσ２’からエラー位置及びエラー値を計算し、第７制御信号に応答して下記の式のようにエラー位置多項式の係数Σ１、Σ２及びΣ３を計算し、
【数２３】
0004022293.tif 000012
前記Σ１、Σ２及びΣ３からエラー位置及びエラー値を計算する演算手段と、前記シンドロームのうちＳ１及びＳ２が０であり、Ｓ０は０でなければ第１制御信号を、前記Ｓ０及びＳ２が０であり、前記Ｓ１が０でなければ第２制御信号を、前記Ｓ０及びＳ１が全て０であり、前記Ｓ２が０でなければ第３制御信号を、前記シンドロームＳ０〜Ｓ２のうち２つが０でなく、前記Ｓ０が０でないか、またはＳ１が０なら第４制御信号を、前記Ａ及び前記Ｂが全て０でなければ第５制御信号を、前記Ｄが０なら第６制御信号を、前記Ｄが０でなければ第７制御信号を各々発生する演算制御手段と、前記シンドロームＳ０〜Ｓ５が全て０ならエラー無しと判断し、前記シンドロームＳ０〜Ｓ２が全て０であり、前記シンドロームＳ３〜Ｓ５が全て０でなければエラー訂正不能と判断し、前記σ１、σ２及びσ３から求めた前記エラー位置が全て符号語内にあるとエラーが３つ発生したと判断し、符号語内にないと、エラー訂正不能と判断し、前記Ａ及び前記Ｂが全て０なら前記エラーが１つ発生したと判断し、前記Ｄが０なら前記エラーが２つ発生したと判断し、前記Ｄが０でなければ前記エラーが３つ発生したと判断する判断制御手段と、前記判断制御手段の判断結果により１、２、３重エラー訂正動作を行うためのエラー訂正手段とで構成されることが望ましい。
【００１９】
【発明の実施の形態】
以下、本発明によるエラー訂正方法及び装置の構成及び動作を添付した図面に基づき次のように説明する。
【００２０】
図２は本発明によるエラー訂正方法を説明するための流れ図である。
【００２１】
図２において、本発明によるエラー訂正方法はシンドロームを計算する段階（第３０段階）と、計算されたシンドロームが０か否かよりエラー形態及びエラー訂正の可否を判断する段階（第３２段階〜第４２段階）で行われる。
【００２２】
ＲＳ（リードソロモン）−コードが３重エラー／６重消し痕（erasure：エラー位置のみ知り、そのエラー値は知らない形のエラーを意味する）訂正能力を有する時（ｔ＝３）、受信符号語Ｒ（ｘ）から次の式７のように６つのシンドロームＳ0〜Ｓ5を求める（第３０段階）。
【００２３】
【数２４】
0004022293.tif 000013
第３０段階後、シンドロームＳ0〜Ｓ5が全て０であるかを判断し（第３２段階）、全て０なら、エラーのないのを決定し（第３４段階）、全て０でなければ、Ｓ0、Ｓ1及びＳ2が０であり、Ｓ3〜Ｓ5のうち少なくとも１つ以上が０でないかを判断する（第３６段階）。
【００２４】
もし、Ｓ0〜Ｓ2が全て０であり、Ｓ3〜Ｓ5のうち少なくとも１つ以上が０でなければ、エラー訂正が不能であると決定する。即ち、エラーが３つより多く発生したので、エラーが訂正出来ないと決定する（第３８段階）。
【００２５】
しかし、Ｓ0、Ｓ1及びＳ2が０でないか、またはＳ3〜Ｓ5が全て０なら（即ち、第３６段階が満足できないと）、シンドロームＳ0〜Ｓ2のうち０のものが２つか否かに応じてエラー位置多項式のエラー係数を別に計算し、別に計算されたエラー係数からエラー位置を求め、エラー位置の範囲からエラー形態及びエラー訂正の可否を判別し、エラー値を計算する（第４０段階）。
【００２６】
第４０段階を添付した図面に基づき次のように細部的に詳しく説明する。
【００２７】
図３は図２に示された第４０段階を細部的に説明するための本発明による流れ図である。
【００２８】
図３において、第４０段階はＳ0〜Ｓ2のうち何れか２つが０であるかを判断する段階（第６０、６４、６８段階）と、各場合に相応してエラー多項式係数σ1、σ2、σ3を計算する段階（第６２、６６、７０段階）及びエラーの発生数のエラー形態とエラー訂正の可否を決定する段階（第７２〜第８０段階）よりなる。
【００２９】
第３６段階を満たさないと、即ちシンドローム（Ｓ0、Ｓ1、Ｓ2）が全て０でないか、またはＳ3〜Ｓ5が全て０なら、シンドロームＳ1とＳ2が全て０であり、Ｓ0が０でないかを判断する（第６０段階）。Ｓ1及びＳ2が全て０であり、Ｓ0が０でなければ、次の式８のようにエラー位置多項式の係数σ1、σ2、σ3を計算する（第６２段階）。
【００３０】
【数２５】
0004022293.tif 000014
しかし、Ｓ1及びＳ2が全て０でないか、またはＳ0が０なら、Ｓ0とＳ2が全て０であり、Ｓ1が０でないかを判断する（第６４段階）。第６４段階において、Ｓ0及びＳ2が全て０であり、Ｓ1が０でなければ、次の式９のようにエラー位置多項式の係数σ1、σ2、σ3を計算する（第６６段階）。
【００３１】
【数２６】
0004022293.tif 000015
しかし、Ｓ0及びＳ2が全て０でないか、またはＳ1が０なら、Ｓ0とＳ1が全て０であり、Ｓ2が０でないかを判断する（第６８段階）。第６８段階において、Ｓ0及びＳ1が全て０であり、Ｓ2が０でなければ、次の式１０のようにエラー位置多項式の係数σ1、σ2、σ3を計算する（第７０段階）。
【００３２】
【数２７】
0004022293.tif 000016
第６２、６６及び７０段階後に、Ｓ0〜Ｓ2のうち任意の２つが０であり、残り１つが０でない場合、エラーが３つ発生したと仮定する（第７２段階）。一方、第６２、６６及び７０段階から計算したエラー位置多項式の係数を利用し、エラー位置、αi、αj、αkを計算する（第７４段階）。エラー位置多項式の係数を用いてエラー位置を計算するために、従来の一般的な方法が利用でき、特に韓国特許公開第９４−１０５４５号に提示された方法が利用されうる。
【００３３】
即ち、韓国特許出願番号９２−１８４０９に提示された方法においては次のような概念をエラー位置多項式に適用して３重エラー訂正を行った。
【００３４】
その概念に対して説明すれば、次の通りである。
【００３５】
下記の式１１のように３次方程式は次の式１２の形態に変換されうる。
【００３６】
【数２８】
0004022293.tif 000017
ここで、θは定数である。
【００３７】
次いで、式１１にｘの代わりにｍＺ＋ｎを代入すると下記の式１３とになり、これを展開すると式１４のようになり、同類項を組み分けると、下記の式１５のようになり、これを最高差項のＺ３の係数を１にするためｍ3に分けると下記の式１６のようになる。
【００３８】
【数２９】
0004022293.tif 000018
ここで、式１６の係数を式１２の係数と比較すると、下記の式１７のような結果を得る。
【００３９】
【数３０】
0004022293.tif 000019
ここで、多項式の根を求める演算がＧＦ（ｑ）の有限体上で行われると式１７は下記の式１８のように等価変換される。
【００４０】
【数３１】
0004022293.tif 000020
従って、ｍ、ｎをａ、ｂ、ｃに対して示すと下記の式１９のようになり、
【数３２】
0004022293.tif 000021
θは次下記の式２０のように示される。
【００４１】
【数３３】
0004022293.tif 000022
ここで、可能なθ値に応じて式１２を満たす根Ｚ１、Ｚ２、Ｚ３を前段階（preprocessing）で求めてＲＯＭテーブルに貯蔵した後、実行段階（processing）でアドレスのみを指定させて容易に根、即ちエラー位置を求めるようにする。
【００４２】
このような概念を用いて韓国特許出願番号９２−１８４０９ではシンドローム、エラー数及びエラー値を次の通り求めた。
【００４３】
まず、式１２において可能な全ての値に対してその根Ｚ１、Ｚ２、Ｚ３を求め、これをアドレスとして指定されるメモリ、即ちＲＯＭテーブルに貯蔵する。ここで、式１２は３重エラー位置多項式の式３の変換された形態となる。
【００４４】
根はＲＯＭテーブルに貯蔵した後に、受信多項式からシンドロームを計算し、計算されたシンドロームを利用してＭマトリックスを構成した後、ｄｅｔ［Ｍ］≠０の最大数を求めることによりエラー数を求める。３重エラー訂正の場合には３×３マトリックスとなるＭからｄｅｔ［Ｍ］≠０であるかを判定することによりエラー数を求めることになる。これを示すと次の式２１のようである。
【００４５】
【数３４】
0004022293.tif 000023
エラー数を求めた後に、ニュートン多項式から導かれた式４を用いてエラー位置多項式の係数σ1、σ2、σ3を求める。
【００４６】
エラー位置多項式の係数を求めた後に、下記の式２２と式２３によりｋ1、ｋ2の値を求めた後、さらに下記の式２４によるθ値を求める。
【００４７】
【数３５】
0004022293.tif 000024
次いで、前記式から得られた値を用いてこれに対応されるアドレスを前記メモリに印加し、それに貯蔵されている式１２の根Ｚ1、Ｚ2、Ｚ3を求める。この際、式１２の根Ｚ1、Ｚ2、Ｚ3を下記の式２５を用いてエラー位置多項式の３つの根ｘj1、ｘj2、ｘj3に変換する。
【００４８】
【数３６】
0004022293.tif 000025
３つの根を変換した後に、エラー値（ｅj）を下記の式２６のように求める。
【００４９】
【数３７】
0004022293.tif 000026
ここで、３つのエラー位置に該当するエラー値はｅ1、ｅ2、ｅ3であり、エラー推定多項式［Ω（ｘ）］は下記の式２７のようになる。
【００５０】
【数３８】
0004022293.tif 000027
一方、第７４段階からエラー位置を計算した後に、エラー位置が符号語内にあるかを判断する（第７６段階）。即ち、α0≦αi、αj、αk≦αn-1であるかを判断する（ここで、ｎは符号の長さを示す）。
【００５１】
もし、エラー位置が符号語内にあれば、エラーが３つ発生したものと、第７２段階の過程を確認し、従来の一般的な方法を使用してエラー値を計算し、特に前述した韓国特許公開第９４−１０５４５号に提示された方式を使用してエラー値を計算する（第７８段階）。しかし、エラー位置が符号語内にないか、またはαi≠αj、αj≠αk、αk≠αiの条件を満さないと、エラー訂正不能と決定する（第８０段階）。即ち、エラーが３つより多く発生して訂正出来ないと決定する。
【００５２】
第４０段階後に、Ｓ0及びＳ1の値により計算した第１及び第２シンドローム式（Ａ及びＢ）が０かに応じてエラー位置多項式の係数を求め、このエラー位置多項式の係数とシンドロームＳ0〜Ｓ4を利用してエラーの形態及びエラー訂正の可否を判別し、エラー位置及びエラー値を計算する（第４２段階）。
【００５３】
第４２段階を添付した図面に基づき次のように細部的に詳しく説明する。
【００５４】
図４は図２に示された第４２段階を細部的に説明するための本発明による流れ図である。
【００５５】
図４において、第４２段階はＳ0及びＳ1の値により第１及び第２シンドローム式を求める段階（第９０、９１、９２段階）。第１及び第２シンドローム式が０か否かに応じてエラー位置多項式の係数を別に求め、係数及びシンドロームＳ0〜Ｓ4を利用してエラーの形態及びエラー訂正の可否を判断する段階（第９４〜１１８段階）よりなる。
【００５６】
第６８段階を満さないと、即ちＳ0、Ｓ1、Ｓ2のうち何れか２つが０でないと、Ｓ0は０であり、Ｓ1は０でないかを判断する（第９０段階）。もし、Ｓ0が０でないか、またはＳ1が０なら、Ｓ0が０でないかを判断する（第９１段階）。第９１段階から、Ｓ0が０ならばエラー訂正不能と決定し、Ｓ0が０でないと、第１シンドローム式Ａ及び第２シンドローム式Ｂを次の式２８のように計算する。
【００５７】
【数３９】
0004022293.tif 000028
ここで、σはＳ1／Ｓ0である。
【００５８】
第９２段階後に、計算されたＡ及びＢが全て０でないかを判断する（第９４段階）。もし、ＡとＢが全て０でなかったり（第９４段階を満たしたり）、Ｓ0は０であり、Ｓ1は０でなければ（第９０段階を満すと）、次の式２９のようにエラー位置多項式の係数σ1’及びσ2’と変数Ｄを計算する（第１００段階）。
【００５９】
【数４０】
0004022293.tif 000029
ここで、Δ＝Ｓ１２＋Ｓ０・Ｓ２≠０である。
【００６０】
しかし、Ａ及びＢが全て０の場合、即ち第９４段階を満たさない場合、Ａ及びＢが全て０かを判断する（第９６段階）。もし、Ａ及びＢが全て０なら、エラーが１つ発生したことと決定し、エラー位置をσ（＝Ｓ1／Ｓ2）にし、エラー値をＳ0に決定する（第９８段階）。しかし、Ａ及びＢが全て０でなければ、ＡまたはＢのうち１つが０であるため、エラー訂正不能と決定する（第１１８段階）。
【００６１】
一方、Ｓ0が０であり、Ｓ1が０でないか、Ａ及びＢが全て０でなければ、エラーが２つ以上発生したと判断し、第１００段階後に、エラーの形態、即ちエラー発生数を決定するために、変数Ｄが０かを判断する（第１０２段階）。もし、Ｄが０なら、エラーが２つ発生したと決定する（第１０４段階）。第１０４段階後に、従来の一般的な方法によりエラー位置及びエラー値を計算する（第１０６段階）。
【００６２】
しかし、Ｄが０でない場合、エラーが３つ発生したものと仮定する（第１０８段階）。これを確認するため、まず下記の式３０のように位置多項式の係数Σ1、Σ2、Σ３を計算する（第１１０段階）。
【００６３】
【数４１】
0004022293.tif 000030
第１１０段階後に、従来の一般的な方法、特に上述した韓国特許公開９第４−１０５４５号に提示された方法を用いて計算されたエラー位置多項式の係数Σ1、Σ２、Σ３からエラー位置を計算する（第１１２段階）。第１１２段階後に、計算されたエラー位置が符号語内にあるかを判断する（第１１４段階）。もし、計算されたエラー位置が符号語内にないと、エラー訂正の不能なものと決定する（第１１８段階）。
【００６４】
しかし、エラー位置が符号語内にあれば、エラーが３つ発生したと決定し、エラー値を計算する（第１１６段階）。
【００６５】
次いで、前述したエラー訂正方法を行う本発明によるエラー訂正装置の構成及び動作を次のように添付した図面に基づき説明する。
【００６６】
図５は本発明によるエラー訂正装置のブロック図である。
図５において、エラー訂正装置は受信符号語貯蔵部１４０、シンドローム発生部１４２、内部演算用記憶部１４４、演算部１４６、演算制御部１４８、判断制御部１５０、エラー訂正部１６０を構成する２エラー訂正エラー位置計算用ＲＯＭテーブル１５４、３エラー訂正エラー位置計算用ＲＯＭテーブル１５６、訂正符号語貯蔵部１５８及び加算器１５２で構成される。
【００６７】
図５に示されたエラー訂正装置の受信符号語貯蔵部１４０は入力端子ＩＮを通して貯蔵媒体（図示せず）または他のエラー訂正装置（図示せず）のような所から入力した１コードワード分のデータを貯蔵してラッチする。シンドローム発生部１４２は受信符号語貯蔵部１４０にラッチされているデータを入力し、発生したシンドロームＳ0〜Ｓ5を内部演算用記憶部１４４に出力する。
【００６８】
内部演算用記憶部１４４はシンドローム発生部１４６から出力されるシンドローム及び演算部１４６から演算中に発生する中間演算値を臨時貯蔵する機能を行う。
【００６９】
演算制御部１４８は内部演算用記憶部１４４に貯蔵されているシンドロームを入力し、Ｓ1及びＳ2が０であり、Ｓ0が０でなければ第１制御信号を、Ｓ0及びＳ2が０でＳ1が０でなければ第２制御信号を、Ｓ0及びＳ1が全て０でＳ2が０でなければ第３制御信号を、シンドロームＳ0〜Ｓ2のうち２つ及びＳ0が０でないか、またはＳ1が０なら第４制御信号を、Ａ及びＢが全て０でなければ第５制御信号を、Ｄが０なら第６制御信号を、Ｄが０でなければ第７制御信号を各々発生して演算部１４６に出力する。
【００７０】
演算部１４６は内部演算用記憶部１４４から入力したシンドロームを以って、演算制御部１４８から発生される第１制御信号に応答して式８のようなσ1、σ2、σ3を計算し、第２制御信号に応答して式９のようなσ1、σ2、σ3を計算し、第３制御信号に応答して式１０のようなσ1、σ2、σ3を計算する。また、第４制御信号に応答して式２８のようなＡ及びＢを計算し、第５制御信号に応答して式２９のようなσ1’、σ2’、Ｄを計算し、第６制御信号に応答してσ1’、σ2’からエラー位置及びエラー値を計算し、第７制御信号に応答して式３０のようなエラー位置多項式の係数Σ1、Σ２、Σ３を計算する。そして、Σ1、Σ２、Σ３からエラー位置及びエラー値を計算する。演算部１４６から計算された最終演算値は内部演算用記憶部１４４に臨時貯蔵される。
【００７１】
演算制御部１４８及び演算部１４６の動作を例として説明すれば、演算制御部１４８は内部演算用記憶部１４４から出力され、演算部１４６を通して入力された各シンドロームＳ1及びＳ2が０であり、Ｓ0が０でなければ第１制御信号を、演算部１４６に出力し、演算部１４６は第１制御信号に応答して反復動作を行った後、式８のようなσ1、σ2、σ3を計算する。この際、演算部１４６は算術論理演算部（図示せず）とエラー訂正コード（ＥＣＣ：Error Correction Code）制御部で構成されており、ＥＣＣ制御部はインバース回路等を用いて割算動作を行い、その結果を再び算術論理演算部に反復的に出力して係数を計算する。
【００７２】
図５に示された判断制御部１５０はシンドロームＳ0〜Ｓ5が全て０ならエラー無しと判断し、受信符号語貯蔵部１４０を制御し、データはそのまま加算器１６０に出力される。しかし、シンドロームＳ0〜Ｓ2が全て０の反面、シンドロームＳ3〜Ｓ5が全て０でなければエラー訂正不能と判断し、エラー訂正不能に該当するメッセージを出力端子ＯＵＴ２を通して出力する。
【００７３】
判断制御部１５０はσ1、σ2、σ3で演算部１４６から獲得されたエラー位置が全て符号語内にあるかを判断し、符号語内にあればエラーが３つ発生したと判断し、符号語内にないとエラー訂正不能と判断して該当する信号及びメッセージをエラー訂正部１６０及び出力端子ＯＵＴ２に各々出力する。
【００７４】
一方、シンドロームＳ0が０でないか、またはＳ1が０なら、内部演算用記憶部１４４に貯蔵されたＡとＢを読出し、全て０ならエラーが１つ発生したと判断して該当するエラー訂正動作を行うようにエラー訂正部１６０を制御する。しかし、Ａ及びＢが全て０でなければ、Ｄが０かを判断し、Ｄが０ならエラーが２つ発生したと判断し、Ｄが０でなければエラーが３つ発生したと判断して該当する制御信号を同様にエラー訂正部１６０に出力する。
【００７５】
エラー訂正部１６０の２エラー訂正エラー位置計算用ＲＯＭテーブル１５４は２つのエラー位置の指数値の差を入力し、入力した指数値の差値にマッチングされるパターンを出力し、同様に３エラー訂正位置計算用ＲＯＭテーブル１５６は３つのエラー位置の指数値の差値を入力し、入力した指数値の差値にマッチングされるパターンを出力する。
【００７６】
加算器１５２は２または３エラー訂正エラー位置計算用のＲＯＭテーブル１５４または１５６から出力されるパターンと受信符号語貯蔵部１４０から出力されるデータを加算してエラーが訂正されたデータとして訂正符号語貯蔵部１５８に出力する。訂正符号語貯蔵部１５８は判断制御部１５０の制御下に、貯蔵されたエラー訂正されたデータを出力端子ＯＵＴ１を通して出力する。
【００７７】
【発明の効果】
前述したように、本発明によるエラー訂正方法及び装置はシンドローム値を分析してエラー位置多項式の係数を求めるため、従来の係数計算方式より演算時間が大幅に短縮され、韓国特許公開９４−４９８０号、９４−１０５４５号及び９５−３４２０２号（出願人：三星電子（株））で提示したエラー数判定式のみを使用した時とは異なり、エラー数を予め判定してエラー訂正不能と処理するため、エラー訂正率が向上され、エラー訂正遂行時間が早く、かつ安定的にエラーを訂正できる。
【図面の簡単な説明】
【図１】  ＣＤ−ＲＯＭまたはＤＶＤ−ＲＯＭの全体システムのブロック図である。
【図２】  本発明によるエラー訂正方法を説明するための流れ図である。
【図３】  図２に示された第４０段階を細部的に説明するための本発明による流れ図である。
【図４】  図２に示された第４２段階を細部的に説明するための本発明による流れ図である。
【図５】  本発明によるエラー訂正装置のブロック図である。
【符号の説明】
１０  ディスク、１２  ＣＤＰ−ＤＳＰ或いはＤＶＤ−デコーダ、１４  ＣＤ−ＲＯＭデコーダ或いはＤＶＤ−ＲＯＭホストインターフェース、１６  Ａ／Ｖデコーダ、１８  ホスト、１４０  受信符号語貯蔵部、１４２  シンドローム発生部、１４４  内部演算用記憶部、１４６  演算部、１４８  演算制御部、１５０判断制御部、１５２  加算器、１５２  ２エラー訂正エラー位置計算用ＲＯＭテーブル、１５６  ３エラー訂正エラー位置計算用ＲＯＭテーブル、１５８  訂正符号語貯蔵部、１６０  エラー訂正部１６０
【図１】
0004022293.tif 000043
【図２】
0004022293.tif 000044
【図３】
0004022293.tif 000045
【図４】
0004022293.tif 000046
【図５】
0004022293.tif 000047