(57)【要約】インバースフリーバーレカンプ・マッシィアルゴリズムの改善版について開示される。この方法においては、不一致（Δ）の計算は共通のインデックス（ｊ）を有する係数を用いて遂行され、このため要求される乗算器の数が低減される。エラータの大きさも、共通のインデックス（ｊ）を有する係数を用いて計算され、これによっても要求される乗算器の数が低減される。共通の乗算器（６０）を、両方の計算に用いることができ、これによって要求される乗算器の数が更に低減される。
2005506794.tif 000002
【特許請求の範囲】
【請求項１】
リード・ソロモン符号化されたデータを復号する方法であって、
不一致の計算が第一の積の項を総和するステップを含み、前記第一の積の項のそれぞれが第一の共通のインデックスを有する係数の第一の積からなることを特徴とする方法。
【請求項２】
前記第一の積の項の総和が
【数１】
2005506794.tif 000023
として表され、前記第一の共通のインデックスを有する係数の第一の積が
【数２】
2005506794.tif 000024
として表され、前記第一の共通のインデックスはｊにて表され、ｋは反復カウンタを表し、Ｎは前記符号化されたデータ内のシンボルの数を表し、Ｋは前記符号化されたデータ内の情報シンボルの数を表し、ｓは前記符号化されたデータ内の消失の数を表し、Ｓｎは前記符号化されたデータのシンドロームを表し、ｎは１からＮ−Ｋまでの整数を表し、
【数３】
2005506794.tif 000025
と定義されることを特徴とする請求項１記載のリード・ソロモン符号化されたデータを復号する方法。
【請求項３】
リード・ソロモン符号化されたデータを復号する方法であって、
エラータの大きさの計算が第二の積の項を総和するステップを含み、前記第二の積の項のそれぞれが第二の共通のインデックスを有する係数の第二の積からなることを特徴とする方法。
【請求項４】
前記第二の積の項の総和が
【数４】
2005506794.tif 000026
として表され、前記共通のインデックスを有する係数の第二の積が
【数５】
2005506794.tif 000027
として表され、前記第二の共通のインデックスはｊにて表され、ｉはエラータ規模のインデックスを表し、Ｎは前記符号化されたデータ内のシンボルの数を表し、Ｋは前記符号化されたデータ内の情報シンボルの数を表し、ｓは前記符号化されたデータ内の消失の数を表し、Ｓｎは前記符号化されたデータのシンドロームを表し、ｎは１からＮ−Ｋまでの整数を表し、
【数６】
2005506794.tif 000028
と定義されることを特徴とする請求項３記載のリード・ソロモン符号化されたデータを復号する方法。
【請求項５】
請求項１乃至４のいずれかに記載の方法に従って動作するための手段を備えることを特徴とするリード・ソロモン符号化されたデータを復号するための復号器。
【請求項６】
請求項１或いは２記載の方法と請求項３或いは４記載の方法の結合に従って動作する手段を備え、更に、
前記第一の積の項を生成することに加え、前記第二の積の項を生成するためにも用いられる乗算手段を備えることを特徴とするリード・ソロモン符号化されたデータを復号するための復号器。
【請求項７】
請求項５或いは６記載の復号器を備える電子デバイス。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はリード・ソロモン符号化されたデータ（Reed Solomon encoded data）を復号する方法、このための復号器、及びリード・ソロモン符号化されたデータを復号するための復号器を備える電子デバイスに係る。
【背景技術】
【０００２】
リード・ソロモン（ＲＳ(Reed Solomon）)符号は、コンパクトディスク(ＣＤ（compact disc）、デジタルバーサタイルディスク(ＤＶＤ（digital versatile disk）)、デジタルビデオブロードキャスト(ＤＶＢ（digital video broadcast)）及びハードディスクドライブ(ＨＤＤ（hard disk drives)）を含む、広範なレンジのシステム内において、誤り（errors）及び消失（erasures）を訂正するために用いられる。ある符号語（code word）内にN個のシンボルを有し、これらN個のシンボルの内のＫ個のシンボルは情報シンボルから成る、（Ｎ，Ｋ）リード・ソロモン符号は、ある符号語内のｓ個のシンボル消失（symbol erasure）及びν個のシンボル誤り(symbol error）を訂正するために用いることができ、ここで、訂正可能な消失或いは誤りの数は、ｓ＋  ２ν  ≦  Ｎ−Ｋによって与えられる。誤りと消失を含むが、消失の位置は既知である、あるリード・ソロモン符号語の復号においては、第一に、その符号語のシンドローム（syndrome）が計算され、第二に、これらシンドローム及び消失の位置からエラータ（誤り及び消失）ロケータ多項式（errata locator polynomial）が計算され、第三に、このエラータ多項式の根（root）を計算することで誤り及び消失の位置が得られ、第四に、エラータ評価多項式（errata evaluator polynomial）が計算され、第五に、このエラータ評価多項式の根を計算することで誤り及び消失の大きさ（magnitude）が得られる。当分野において周知のように、エラータロケータ多項式及びエラータ評価多項式を決定するためにはバーレカンプ・マッシィ(ＢＭ（Berlekamp-Massey)）アルゴリズム或いはユークリッド（Euclidean）アルゴリズムを用いることができ、これら多項式の根を計算するためにはチェン探索（Chien search）を用いることができる。Blahutは、" Theory and practice of error control codes（誤り制御符号の理論及び実際） ", R.E. Blahut, Addison-Wesley,1984において、エラータロケータ多項式は、バーレカンプ・マッシィ（ＢＭ）アルゴリズムを消失ロケータ多項式及びシンドローム多項式にて初期化することで直接に計算することができ、こうすることで、" On decoding BCH codes （BCH符号の復号）", Forney, Jr., IEEE Trans. Inform. Theory, vol.IT-11, pp 549-557, Oct. 1965において定義されているような、フォーニィシンドローム（Forney syndrome）を計算する必要性を回避できることを示唆している。
【０００３】
このアイデアに基づいて、Jyh-HorngとTrieu-Kien Troungは、" On decoding of both errors and erasures of a Reed-Solomon code using an inverse-free Berlekamp-Massey algorithm（インバースフリーバーレカンプ・マッシィアルゴリズムを用いての誤り及び消失の両方の復号）", IEEE Trans. Commun., vol. 47, pp. 1488-1494, Oct. 1999において、誤り及び消失を訂正するためのＲＳ復号器内においてエラータロケータ多項式を直接見つけるためのインバースフリーＢＭアルゴリズム（Inverse-Free BM Algorithm）を提唱しているが、これは、以下のような議論に基づく：
ガロア体ＧＦ（２ｍ）上のある（Ｎ，Ｋ）ＲＳ符号の符号生成多項式（code generator polynomial）をｇ（ｘ）として表すものとする。ここで、ｇ（ｘ）は、最も一般的な形式においては、以下のように定義される：
【数１】
2005506794.tif 000003
【０００４】
ここで、αは、ガロア体ＧＦ（２ｍ）を構築する原始多項式ｐ（ｘ）の根を表し、ｑ及びｍは、上記符号を定義するパラメータを表す。受信されたＲＳ符号語ベクトルをｒ＝［ｒ０，ｒ１，．．．，ｒＮ−１］として表すものとすると、周知のように、
【数２】
2005506794.tif 000004
として定義されるシンドローム多項式Ｓ(x)の係数は：
【数３】
2005506794.tif 000005
として計算される。
【０００５】
ＺｉがＲＳ符号語ベクトルｒ内のｉ番目の既知の消失の位置を表し、Ｘｉがｉ番目の誤りの位置を表すものとすると、消失ロケータ多項式は以下のように定義される：
【数４】
2005506794.tif 000006
【０００６】
ここで、Λ0＝１であり、Λ（ｘ）は、上記消失位置の逆数の位置（以下、インバース消失位置ともいう）で零となる多項式を表す。インバース誤り位置とインバース消失位置で零となるエラータロケータ多項式は以下のように定義される：
【数５】
2005506794.tif 000007
【０００７】
これらシンドローム多項式Ｓ(x）と消失ロケータ多項式Λ（ｘ）からエラータロケータ多項式π（ｘ）を計算するために用いられるインバースフリーＢＭアルゴリズムは、以下のように定義される：
【０００８】
ステップ１
最初に以下のように定義する：
【数６】
2005506794.tif 000008
ここで、ｋは反復カウンタ（iteration counter）を表す。
【０００９】
ステップ２
ｋ＝ｋ＋１にセットする。ｋがその符号によって訂正可能な誤りの最大数を超えた場合つまり、ｋ≧Ｎ−Ｋ−ｓとなった場合は停止する。さもなければ、以下のように定義する。
【数７】
2005506794.tif 000009
ここで、δ（ｋ）は不一致（discrepancy）と呼ばれる。
【００１０】
ステップ３
以下を計算する：
【数８】
2005506794.tif 000010
【００１１】
ステップ４．  ステップ２に戻る。
エラータロケータ多項式π（ｘ）は、
π（ｘ）＝μ（ｘ）  /  μ０
としてμ（ｘ）を正規化することで得られる。
【００１２】
ここで、μ０ は、μ（ｘ）内のｘ０の係数を表し、その後、チェン探索を用いてエラータの位置が見つけられる。エラータ評価多項式Ａ（ｘ）は以下のように定義される：
【数９】
2005506794.tif 000011
その後、これは、エラータの大きさを計算するために用いられる。
【００１３】
JengとTroungによって説明されているように、エラータの大きさは以下の式によって与えられる：
【数１０】
2005506794.tif 000012
ここで、Zｒウェーブはｒ番目のエラータの位置を表し、π'（Zｒウェーブの逆数）は、ｘがZｒウェーブの逆数であるときのｘに関するπ（ｘ）の微分係数を表す。
【００１４】
インバースフリーＢＭアルゴリズム（Inverse-Free BM Algorithm）の長所として、フォーニィシンドローム（Forney syndrome）とエラータロケータ多項式を別個に計算する必要性を回避することができる。ただし、この方法では、短所として、不一致の計算に必要とされる乗算器の数は、パリティシンボルの数の二乗に比例し、このため復号器を集積回路内に実現する際に要求される面積の観点からコストが非常に高くなる。
【発明の開示】
【００１５】
本発明の一つの目的は、リード・ソロモン符号化されたデータを復号するための改善された復号方法及び復号器を提供することにある。
【００１６】
本発明の第一の態様によると、リード・ソロモン符号化されたデータを復号するための方法であって、不一致の計算が第一の積の項を総和するステップを含み、各第一の積の項が第一の共通のインデックスを有する係数の第一の積から成る、ことを特徴とする方法が開示される。
【００１７】
この方法によると、不一致δの計算は、多項式μ（ｘ）、Ｆ（ｘ）、及びＥ(ｘ）の係数を用いて行なわれるが、この計算においては、共通のインデックスを有する係数のみが乗算されるために、エラータロケータ多項式τ（ｘ）の計算に必要とされるガロア体(GF）乗算器の数はパリティシンボルの数の線形関数となる。このため、復号器の実現の複雑さを低減できる上に、復号のために要求されるクロックサイクルの数も低減される。
【００１８】
本発明の第二の態様によると、リード・ソロモン符号化されたデータを復号するための方法であって、エラータの大きさの計算が第二の積の項を総和するステップを含み、各第二の積の項が第二の共通のインデックスを有する係数の第二の積から成る、ことを特徴とする方法が開示される。
【００１９】
この方法によると、エラータの大きさの計算は、多項式μ（ｘ）、Ｆ（ｘ）、及びＥ(ｘ）の係数を用いて行なわれるが、この計算においては、共通のインデックスを有する係数のみが乗算されるために、エラータの大きさの計算に必要とされるガロア体（ＧＦ）乗算器の数は、パリティシンボルの数の線形関数となる。このため、復号器の実現の複雑さを低減できる上に、復号のために要求されるクロックサイクルの数も低減される。
【００２０】
更に、第一及び第二の積の項のいずれかの計算においては循環構造が用いられ、この計算自体がこのアルゴリズムによって必要とされる反復の数に依存することはなくなる。
【００２１】
本発明の第三の態様によると、本発明の第一或いは第二の態様に従って動作するための手段を備えることを特徴とするリード・ソロモン符号化されたデータを復号するための復号器が提供される。
【００２２】
本発明の第四の態様によると、請求項６に記載されるようなリード・ソロモン符号化されたデータを復号するための復号器が提供される。
【００２３】
本発明の第五の態様によると、本発明の第三或いは第四の態様による復号器を備える電子デバイスが提供される。この電子デバイスは、復号器を備える集積回路として実現することも、光記憶ディスク（optical storage disk）或いは磁気記憶ディスク（magnetic storage disc）等の記憶媒体からデータを読み出すための装置として実現することも、或いは、無線信号等の伝送された信号を受信するための装置として実現することも考えられる。
【００２４】
不一致及びエラータ（消失及び誤り）の大きさの計算において、共通のインデックスを有する係数の積が用いられるために、不一致の計算のために用いられる乗算器を、誤りの大きさの計算のためにも用いることができ、復号器の複雑さが更に低減される。
【００２５】
この新たな多項式Ｆ（ｋ）（ｘ）は：
【数１１】
2005506794.tif 000013
として定義され、生成係数Ｆj(k)は：
【数１２】
2005506794.tif 000014
として定義される。
【００２６】
Ｆ（ｋ）（ｘ）に対する式（１３）は、Ｆ(k‐l）（ｘ）の循環シフトから成る。イネーブル多項式Ｅ(k)(x)は：
【数１３】
2005506794.tif 000015
として定義され、この生成係数Ｅ(k)jは：
【数１４】
2005506794.tif 000016
として定義される。
【００２７】
Ｅ（ｋ）（ｘ）に対する式（１６）は、Ｅ(k‐l）（ｘ）の循環シフトから成る。復号器内では、これら２つの変数Ｆ（ｋ）（ｘ）とＥ（ｋ）（ｘ）は、２つの循環レジスタ（circular register）として実現され、これらレジスタは、それぞれ、式（１２）と（１５）にて定義されるように初期化された後、各クロックサイクルにおいて、それぞれ、式（１３）と（１６）に従ってシフトされる。式（８）として定義される不一致δ（ｋ）はＦ（ｋ）（ｘ）とＥ（ｋ）（ｘ）の関数として以下のように計算される：
【数１５】
2005506794.tif 000017
【００２８】
不一致δ（ｋ）の計算においては、ガロア体（ＧＦ）乗算器は常に同一インデックスの係数、つまりｊ番目の係数を含み、このためガロア体（ＧＦ）乗算器の数はＮ−Ｋとなる。従来の技術による不一致δ（ｋ）の（８）式に従っての計算においては、ガロア体（ＧＦ）乗算器は異なるインデックス、つまり、ｊ番目と（ｋ＋ｓ−ｊ）番目を含み、この後者のインデックスは反復回数に依存し；その結果、従来の技術によると、要求されるガロア体（ＧＦ）乗算器の数は（Ｎ−Ｋ）２となる。
【００２９】
エラータの大きさを計算するためには、式（１０）に定義されるＡ（ｘ）の代りに、新たな変数Ｂ(x)が以下のように定義される：
【数１６】
2005506794.tif 000018
ここで、Ｂ(ｘ）の生成係数Ｂiは：
【数１７】
2005506794.tif 000019
と定義される：
【００３０】
Ｆ（ｋ）（ｘ）とＥ（ｋ）（ｘ）を以下のように、つまり、
【数１８】
2005506794.tif 000020
として初期化することで、Ｂ(x)の各生成係数Ｂiは以下のように計算される：
【数１９】
2005506794.tif 000021
【００３１】
復号器内において、Ｂ(x)の各係数Ｂiに対して、それぞれ、式（１３）と式（１６）として定義されるＦ（ｋ）（ｘ）とＥ（ｋ）（ｘ）に循環シフトが適用される。
【００３２】
Ｂiの計算においては、ガロア体（ＧＦ）乗算器は、常に同一インデックスの係数、つまり、ｊ番目の係数を含み、このためハードウェア実現において必要とされるガロア体（ＧＦ）乗算器の数はＮ−Ｋとなる。従来の技術によるエラータ評価多項式Ａ（ｘ）の式（１０）に従っての計算においては、ガロア体（ＧＦ）乗算器は異なるインデックス、つまり、ｊ番目と（ｋ＋ｓ−ｊ）番目の係数を含み、この後者のインデックスは反復回数に依存し；この結果、従来の技術によると、ガロア体（GF)乗算器の数は（Ｎ−Ｋ）２となる。更に、本発明によると、不一致δ（ｋ）の計算のために用いられるのと同一の資源を、別の時間において、Ｂ(x)の計算にも用いることが可能となる。
【００３３】
Ｂ(x)から、エラータの大きさは以下のように計算される：
【数２０】
2005506794.tif 000022
ここで、Zｒウェーブはｒ番目のエラータ位置を表し、μ'（Zｒウェーブの逆数）は、ｘ＝がZｒウェーブの逆数であるときのｘに関するμ（ｘ）の微分係数を表す。
【００３４】
以下に、本発明を、単に例示として、添付の図面を参照しながら説明する。
【発明を実施するための最良の形態】
【００３５】
図１に示すように、この復号回路は、それぞれ、Ｆ(k)（ｘ）とＥ（ｋ）（ｘ）を格納するための循環シフトレジスタ（circular shift register）１０、２０を備え、Ｅ（ｋ）（ｘ）レジスタ２０は、その帰還路内にインバータ３０を備える。μ（ｘ）を格納するためのレジスタ４０も設けられる。Ｆ(k)（ｘ）レジスタの各段からの出力は、各々のマルチプレクサ５０内で、論理零に設定された制御線５５と多重化される。Ｅ（ｋ）（ｘ）レジスタ２０の各段からの出力は、各マルチプレクサ５０に対する制御線として機能する。各マルチプレクサ５０からの出力は、各乗算器６０内で、μ（ｘ）レジスタ４０の各段からの出力と乗算される。各乗算の積は、加算器７０内で総和され、マルチプレクサ５１を介してＢ(x)を格納するレジスタ９０に供給されるとともに、マルチプレクサ５２を介して不一致δを格納するレジスタ８０に供給される。マルチプレクサ５１、５２を制御するための制御手段５６が設けられ、これによって、加算器７０の出力が、不一致δを格納するレジスタ８０に供給されるべきか、或いはＢ(x)を格納するレジスタ９０に供給されるべきか決定される。
【００３６】
次に、図２の流れ図との関連で、本発明による改善されたＢＭアルゴリズム（Ｒ−ＢＭ）について説明する。各Ｒ−ＢＭステップは、単一のクロックサイクルにて実行される。ブロック１１０は、このアルゴリズムの開始を表す。ブロック１１２において、ｓの値、すなわち、消失の数がテストされる。ｓがこの符号の訂正能力を超える場合は、誤りも、消失も訂正することはできず、このアルゴリズムは、ブロック１１４において終了し、超えない場合は、ブロック１２０に進む。
【００３７】
ブロック１２０において、Ｒ−ＢＭステップ１が遂行される。このステップ１において、ステップ２において用いられるべき変数ｋ、ｌ、γ及びλ（ｘ）が、式（６）と（７）に従って初期化される。これら変数は図１には示されていない。μ（ｘ）は、レジスタ４０内で、式（７）に従って初期化される。Ｆ(k)（ｘ）とＥ（ｋ）（ｘ）は、それぞれ、レジスタ１０と２０内で、式（１２）と（１５）に従って初期化される。
【００３８】
次に、ブロック１３０において、ｓの値、すなわち、消失の数が再びテストされる。ｓの値が大きすぎて、誤りを訂正することはできないが、消失は訂正できる場合は、このR-BMアルゴリズムは、消失の訂正のためには、消失ロケータ多項式Λ（ｘ）のみで十分であり、エラータロケータ多項式π（ｘ）の計算は必要とされないために、後で説明するＲ−ＢＭステップ３に進む。他方、ｓが十分に小さく、誤りを訂正することができる場合は、ブロック１４０において、Ｒ−ＢＭステップ２を遂行することで、エラータ（消失及び誤り）ロケータ多項式π（ｘ）が計算される。Ｒ−ＢＭステップ２において、反復カウンタｋが増分される。ディスクレパンシィδが式（１７）に従って計算され、レジスタ８０内に格納される。変数μ（ｘ）、λ（ｘ）、ｌ及びγが、式（９）に従って更新される。それぞれ、レジスタ１０と２０内の変数Ｆ(k)（ｘ）とＥ（ｋ）（ｘ）の右シフトが、式（１３）と式（１６）に従って適用される。
【００３９】
Ｒ−ＢＭステップ２は、ｋの各値に対して反復的に繰返され、各反復の後に、ブロック１５０においてｋの値がテストされる。ｋが、消失ｓの既知の値を考慮して、その符号の誤り訂正能力を超える場合は、ブロック１６０においてステップ３が遂行され、超えない場合は、Ｒ−ＢＭステップ２の次の反復が遂行される。Ｒ−ＢＭステップ２の反復の結果としての多項式μ（ｘ）がレジスタ４０内に格納される。Ｒ−ＢＭステップ３において、ダウンカウンタｂｃｎｔが、Ｎ−Ｋ−１に初期化される。それぞれ、Ｆ（ｋ）（ｘ）とＥ（ｋ）（ｘ）が、レジスタ１０と２０内において、式（２０）と（２１）に従って初期化される。このアルゴリズムは、次に、ブロック１７０におけるＲ−ＢＭステップ４に進む。
【００４０】
Ｒ−ＢＭステップ４において、Ｂ（ｘ）の係数Ｂｔがレジスタ９０内で式（２２）に従って計算され、それぞれ、Ｆ(k)（ｘ）とＥ（ｋ）（ｘ）が、レジスタ１０と２０内で、式（１３）と（１６）に従ってシフトされ、ダウンカウンタｂｃｎｔの値が減分される。Ｒ−ＢＭステップ４は、ダウンカウンタｂｃｎｔの各値に対して反復的に繰返され、各反復の後に、ダウンカウンタｂｃｎｔの値がブロック１８０においてテストされる。ダウンカウンタｂｃｎｔの値が零に達した場合、これはＢ（ｘ）の全ての係数が計算されたことを意味し、このアルゴリズムはブロック１９０において終了するが、零に達してない場合は、Ｒ−ＢＭステップ４の次の反復が遂行される。
【００４１】
図１の回路は、図３に示すように、リード・ソロモン復号器２１０、２個のデュアルポートＲＡＭ２２０、２２５、及び復号器２１０とこれらＲＡＭとの間をインタフェースする制御ブロック２３０を備える符号化／復号化を行う装置２００内に実現される。第一のＲＡＭ２２０は、データ２のフレームを保持する容量を有し、第二のＲＡＭ２２５は、データの１フレームを保持する。ここで、データの１フレームは１つのリード・ソロモン符号語に等しい。第二のＲＡＭ２２５は、データを保持する一方、復号器２１０は、シンドローム及びＲ−ＢＭアルゴリズムの計算を実行する。第二のＲＡＭ２２５は、２つの目的を果たす。これは、第一に、ユーザによって（ここでは図示されてないシリアルプログラミングインタフェースを介して）復号されたデータのフレームが復号器２００から出力される順番、つまり、バイト０からＮー１の順番にて出力されるべきか、或いはバイトＮ−１から０の順番にて出力されるべきか、をプログラムするために用いられる。これは、第二に、データのフレームをそれが伝送される前に遅延するために用いられ、これによってそのデータのフレームと共にその受信された符号語が正常に復号されたか否かを示すコレクト信号を送ることが可能となる。
【００４２】
この符号化／復号化を行う装置２００は、図４に示すに、３つの主要な段を有するパイプライン構造として実現される。ある受信された符号語内に存在する消失の数ｓは、復号過程の開始の時点において知られている。第一の段においては、シンドローム多項式Ｓ(ｘ）と消失ロケータ多項式Λ（ｘ）が周知の方法を用いて計算される。第一の段は、Ｎクロックサイクルにて実行される。第二の段は、図２との関連で上で説明したＲ−ＢＭアルゴリズムから成る。第二の段の処理時間は、受信された符号語内に存在する消失の数によって変動し、消失は存在せず、誤りの訂正のみが必要とされる場合は、２・（Ｎ−Ｋ）＋２なる最大値を有し、誤りは存在せず、消失の訂正のみが必要とされる場合は、（Ｎ−Ｋ）＋２なる最小値を有する。第三の段は、周知のチェン探索から成る。ここでは、エラータロケータ多項式τ（ｘ）の根と同一であるμ（ｘ）の根が計算されると共に、エラータの大きさが計算される。第三の段の処理時間はＮクロックサイクルである。
【００４３】
この３段コーデック２００は、３つの受信された符号語がコーデック２００によって任意の時間に処理できるようなパイプライン構造を有するように設計される。このパイプライン構造のタイミングが図５に示される。第一の段がｎ番目のフレームに関して動作している間に、それぞれ、第二の段と第三の段は、（ｎ−１）番目のフレームと（ｎ−２）番目のフレームに関して動作する。
【００４４】
符号化／復号化を行う装置２００を通過する際の時間は、符号語のサイズ、パリティビットの数、及びある受信された符号語内の消失及び誤りの数に依存する。クロックサイクルに換算しての上記時間の値は、２Ｎ＋２・（Ｎ−Ｋ）−ｓによって与えられる。一例として、ＤＶＢ標準ＲＳ符号（２０４、１８８）の場合、最大時間は４４０クロックサイクル、最小時間は４２４クロックサイクルとなる。
【００４５】
図６には、光データ記録ディスクからリード・ソロモン符号化されたオーディオ及びビデオデータを抽出し、こうして抽出されたデータをオーディオ及びビデオ信号に変換するための電子デバイス３００が示される。このデバイス３００は、光データ記録ディスクからリード・ソロモン符号化されたデータを読み出すための読出手段３１０を備える。この読出手段３１０の出力には、本発明の第三の態様による、読出手段３１０によって読み出されたリード・ソロモン符号化されたデータを復号するためのリード・ソロモン復号器３２０が接続される。このリード・ソロモン復号器３２０の出力には、こうして復号されたデータからオーディオ及びビデオデータを抽出するためのデフォーマッティング手段（deformating means）３３０が接続される。このデフォーマッティング手段３３０の出力には、このオーディオ及びビデオデータをアナログのオーディオ及びビデオ信号に変換し、このアナログのオーディオ及びビデオ信号を出力３５０に供給するためのアナログ・デジタル変換手段３４０が接続される。これら読出手段３１０、リード・ソロモン復号器３２０、デフォーマッティング手段３３０、及びアナログ・デジタル変換手段３４０の動作は処理手段３６０によって制御されるが、これはユーザインタフェース（図示せず）も制御する。
【産業上の利用分野】
【００４６】
リード・ソロモン符号を用いるデジタル記憶及び通信装置。
【図面の簡単な説明】
【００４７】
【図１】δ（ｋ）とＢ（ｘ）を計算するための回路の略ブロック図である。
【図２】本発明による改善されたＢＭ復号アルゴリズムに対する流れ図である。
【図３】コーデックデバイスの略ブロック図である。
【図４】リード・ソロモン符号の復号過程の３つの主要な段を解説する流れ図である。
【図５】改善されたＢＭ復号アルゴリズムを備えるリード・ソロモン復号器のパイプライン動作を示す図である。
【図６】リード・ソロモン復号器を備える電子デバイスの略ブロック図である。
【符号の説明】
【００４８】
１０  Ｆ(k)（ｘ）循環シフトレジスタ
２０  Ｅ（ｋ）（ｘ）レジスタ
３０  インバータ
４０  μ（ｘ）レジスタ
５０  マルチプレクサ
５２  マルチプレクサ
５５  制御線
５６  制御手段
６０  乗算器
７０  加算器
８０  不一致δレジスタ
９０  Ｂ(x)レジスタ
２００  符号化／復号化を行う装置
２１０  リード・ソロモン復号器
２２０  第一のＲＡＭ
２２５  第二のＲＡＭ
２３０  制御ブロック
３００  電子デバイス
３１０  読出手段
３２０  リード・ソロモン復号器
３３０  デフォーマッティング手段
３４０  アナログ・デジタル変換手段
３６０  処理手段
【図２】
2005506794.tif 000029
【図４】
2005506794.tif 000030
【図５】
2005506794.tif 000031
【国際公開パンフレット】
2005506794.tif 000032
2005506794.tif 000033
2005506794.tif 000034
2005506794.tif 000035
2005506794.tif 000036
2005506794.tif 000037
2005506794.tif 000038
2005506794.tif 000039
2005506794.tif 000040
2005506794.tif 000041
2005506794.tif 000042
2005506794.tif 000043
2005506794.tif 000044
2005506794.tif 000045
2005506794.tif 000046
2005506794.tif 000047
2005506794.tif 000048
2005506794.tif 000049
2005506794.tif 000050
【国際公開パンフレット（コレクトバージョン）】
2005506794.tif 000051
【国際調査報告】
2005506794.tif 000052