(57)【特許請求の範囲】
【請求項１】
所望のガロア体上の最大ｔ個の誤りを有する大規模データ・ブロックの誤り位置および大きさを計算するためのリード・ソロモン・デコーダで使用される誤り計算プロセッサであって、
誤り位置多項式および誤り評価多項式を計算するための第１の計算手段と、
誤りであると決定された位置の誤りの値を計算するための第２の計算手段と、
を備え、
前記第１および第２の計算手段は、第１の多項式記憶レジスタと、第２の多項式記憶レジスタと、第１の要素記憶レジスタと、第２の要素記憶レジスタと、選択された乗算および除算を実行するための１つの乗算器と、選択された加算および減算を実行するための１つの加算器と、誤り位置スタックと、誤り値スタックと、前記大規模データ・ブロックのシンドロームを記憶するためのシンドローム・レジスタと、だけを必要とするものである、
プロセッサ。
【請求項２】
前記第２の多項式記憶レジスタは、バールカンプ−マッシー・アルゴリズムの実行中にＢ（ｘ）の係数を記憶するものである、
請求の範囲第１項に記載のプロセッサ。
【請求項３】
前記第１の要素記憶レジスタは、相違の正規化された値を記憶するものである、
請求の範囲第１項または第２項に記載のプロセッサ。
【請求項４】
前記第１の要素記憶レジスタは、前記誤り評価多項式の個々の係数の計算中に中間値を記憶するものである、
請求の範囲第１項、第２項または第３項に記載のプロセッサ。
【請求項５】
前記第１の要素記憶レジスタが、前記誤り評価多項式の評価の結果を記憶するものである、
請求の範囲第４項に記載のプロセッサ。
【請求項６】
前記誤り値スタックは、チエン探索中に前記誤り位置多項式の導関数を記憶するものである、
請求の範囲第１項から第５項のいずれか１項に記載のプロセッサ。
【請求項７】
前記乗算器は、前記選択された除算を実行するためのインバータを含んでいる、
請求の範囲第１項から第６項のいずれか１項に記載のプロセッサ。
【請求項８】
ガロア体（２５６）におけるデータ・ブロックの最後の位置の最初のｔ個の累乗の初期値を記憶するための多項式引数レジスタを含む、
請求の範囲第１項から第７項のいずれか１項に記載のプロセッサ。
【請求項９】
前記第１または第２の一方または双方の多項式記憶レジスタは、複数の多項式レジスタ記憶素子を備え、
前記多項式レジスタ記憶素子のそれぞれが、マルチプレクサと直列に接続されたフリップ・フロップを含み、それにより前記多項式レジスタの長さが調整可能である、
請求の範囲第１項から第８項のいずれか１項に記載のプロセッサ。
【請求項１０】
前置計算されたＧＦ要素を記憶するための多項式引数記憶手段を含み、
前記乗算器は、前記前置計算されたＧＦ要素を、前記誤り位置多項式および誤り評価多項式の適切な多項式係数と乗算して、リード・ソロモン・ブロックを逆転する必要なく前記多項式の初期値を提供するものである、
請求の範囲第１項から第９項のいずれか１項に記載のプロセッサ。
【請求項１１】
ソース・レジスタとデスティネーション・レジスタとの間で２つまでの同時データ転送を許容する手段を含む、
請求の範囲第１項に記載のプロセッサ。
【請求項１２】
前記第１の多項式記憶レジスタは、ｔ＋１バイトまでの前記誤り位置多項式の係数を記憶するものであり、
前記第２の多項式記憶レジスタは、２ｔバイトまでの前記誤り評価多項式の係数を記憶するものであり、
前記第１の要素記憶レジスタは、前記相違の計算のためのものであり、
前記第２の要素記憶レジスタは、先のゼロでない相違の値を記憶するためのものであり、
前記誤り位置スタックは、前記誤り位置多項式の根を記憶するものであり、
前記誤り値スタックは、各誤りの大きさを記憶するものである、
請求の範囲第１項から第１１項のいずれかに記載のプロセッサ。
【請求項１３】
最大ｔ個の誤りを有する大規模データ・ブロックを受信し、前記大規模データ・ブロックのシンドロームを計算するためのシンドローム計算手段と、
前記大規模データ・ブロックの誤り位置および大きさを計算するための誤り計算プロセッサであって、
ｔ＋１バイトまでの前記誤り位置多項式の係数を記憶するための第１の多項式記憶レジスタを含み、誤り位置多項式および誤り評価多項式を計算するための第１の計算手段と、
ｔ＋１バイトまでの前記誤り位置多項式の係数を記憶するための第１の多項式記憶レジスタを含み、誤りにあると決定された位置の誤り値を計算するための第２の計算手段と、
２ｔバイトまでの前記誤り評価多項式の係数を記憶するための第２の多項式記憶レジスタと、
相違の計算をするための第１の要素記憶レジスタと、
先のゼロでない相違の値を記憶するための第２の要素記憶レジスタと、
選択された乗算および除算を実行するための１つの乗算器と、
選択された加算および減算を実行するための１つの加算器と、
前記誤り位置多項式の根を記憶するための誤り位置スタックと、
各誤りの大きさを記憶するための誤り値スタックと、
前記シンドローム計算手段によって計算されたシンドロームを記憶するためのシンドローム・レジスタと、を備えている、そのようなプロセッサと、
前記大規模データ・ブロックの前記誤りを訂正するための誤り訂正手段と、
前記誤り訂正手段への前記データ・ブロックの送信を遅延させるためのデータ遅延手段と、
を備えているリード・ソロモン・デコーダ。
【請求項１４】
請求の範囲第１３項に記載のリード・ソロモン・デコーダとビデオ・ソース・デコーダの組み合わせを備えているＴＶ受信機。
【発明の詳細な説明】
１．発明の分野
本発明は、一般に、リード・ソロモン・デコーダに関し、特に、大規模データ・ブロックにおける誤りの位置およびその大きさを計算するための改良された誤り計算プロセッサに関する。
２．関連技術の説明
デジタル・データ伝送および記憶システムにおける誤り検出および訂正の主な方法の１つは、リード・ソロモン符号として知られている誤り訂正符号の部類のものを使用する。このような２つのリード・ソロモン・システムは、S.LinとD.J.Costello,Jr.による「誤り制御符号：基礎と応用（Error Control Coding:Fun damentals and Applications）」（プレンティスホール出版社、Englewood Cliffs,N.J.1983年）（以下「誤り制御符号」という。）の第６章と、R.E.Blahutによる「誤り制御符号の理論と実践」（アディソン・ウェスリー出版社、リーディング、マス、1983年）（以下「誤り制御符号の理論と実践」という。）の第７章とに示されている。従来システムにおける符号化および復号方法の背後にある理論は、当業者には周知であり、受信データまたは検索データの誤りの検出および訂正のためのいくつかの復号アルゴリズムとして知られている。一般的には、復号プロセスは、符号化プロセスよりも複雑である。
公知のリード・ソロモン・デコーダのこのような１つの応用は、地上放送、ケーブルまたは衛生チャネル上のデジタル圧縮ビデオの伝送に見られる。たとえば、グランド・アライアンス（ＧＡ）は、このようなチャネル上をデジタルＨＤＴＶ伝送のための標準を発表した。ＧＡのＨＤＴＶ伝送システムは、順方向誤り訂正のために規定された（２０７，１８７）リード・ソロモン（以下「Ｒ−Ｓ」ともいう。）符号を使用する。この符号では、１８７バイトの「ペイロード」データと付加的な２０バイトの誤りチェック・データとが、２０７バイトのリード・ソロモン・ブロックを構成する。
上記例では、Ｒ−Ｓブロックの約１０パーセントが、誤りチェック・データから構成される。これは、ブロック・データの中では比較的小さな比率である。一般に、ブロック・サイズが大きくなればなるほど、所与の性能要求を満たすために必要となる誤りチェック・データのブロック比率は小さくなる。復号プロセスの実行時間は誤りチェック・データの量にのみ依存するので、ブロック・サイズが大きくなるほど、より小さな比率のブロック処理時間を、所与の処理速度で誤り検出および訂正のために使用することが可能となる。逆に言えば、遅い速度で処理を実行することができる。その結果、これは、集積回路上で効率的に実現される、より簡単で、より経済的なハードウェアの見返りに、処理速度の妥協を可能にする。
典型的な放送通信または永久保存データ記憶システムでは、各受信機または検索装置は、このようなデコーダを必要とし、また、これらは、民生品として市場で販売することができるので、デコーダの設計は、可能な限り単純、効率的で、かつ、経済的であることが望ましい。
したがって、従来技術のリード・ソロモン・デコーダは、ある程度は満足のいくものではあるが、ＧＡ標準において行うように、Ｒ−Ｓデータ・ブロックがある長さを超える状況に対して、従来技術に見られるよりもハードウェア効率がよく、かつ、より汎用のアーキテクチャを使用する、一層単純で効率的なリード・ソロモン・デコーダが望まれている。
発明の概要
リード・ソロモン復号の一般的な方法では、所与のＲ−Ｓブロック内のデータの一組の累積「合計」が計算される。これらは、「シンドローム」と呼ばれ、そのブロックの誤りチェック・バイトと数において等しい。ブロック内のすべての誤りの位置および大きさは、このシンドロームのみを使用して決定され、誤り状態にあるバイトの数が誤りチェック・バイト数の半分を超えないすべてのブロックについては正しい。この知識によって、誤り状態にあるバイトを、ブロック内に発見することができ、それぞれは識別されるので、オリジナルの値を復元するために、誤りの大きさを不正データに加えることができる。シンドローム計算は、各データ・ブロックに対して実行されなければならず、デコーダにデータが入力される際に、標準的な方法を使用して実行することができる。最終的な訂正も、全体のブロックに対して実行されなければならず、また、誤り位置および大きさが決定された後、データがデコーダから出力される際に、実行することができる。一方、これらの計算は、リード・ソロモン復号プロセスの最も難しい部分を構成し、典型的には、実行するために複雑なハードウェアを必要とする。
したがって、本発明によると、そのブロックに対するシンドロームを与えると、非常にハードウェア効率のよい方法でデータ誤り位置および大きさの計算を実現するリード・ソロモン・デコーダのアーキテクチャが提供される。このアーキテクチャは、ガロア体（ＧＦ）演算として知られているものであって、リード・ソロモン復号に必要とされる、広いクラスの数学的処理を実行するように示されている。このアーキテクチャは、シンドローム計算手段とは独立であり、少なくとも２つの周知の誤り訂正方法とともに使用されてもよい。
好ましい実施例において、誤り計算プロセッサは、２つの多項式記憶レジスタと、２つの要素記憶レジスタと、選択された乗算および除算を実行する１つの乗算器と、選択された加算および減算を実行する１つの加算器と、１つの誤り位置スタックと、１つの誤り値スタックと、大規模データ・ブロックのシンドロームを記憶するシンドローム・レジスタとを利用して、誤り位置多項式と、誤り評価多項式と、誤り状態にあると決定された位置の誤り値とを計算することができる。
特に、第１の多項式記憶レジスタは、ｔ＋１バイトまでの誤り位置多項式の係数を記憶するために利用することができる。第２の多項式記憶レジスタは、２ｔバイトまでの誤り評価多項式の係数を記憶するためと、バールカンプ−マッシー・アルゴリズムの実行中にＢ（ｘ）の係数を記憶するためとに利用することができる。第１の要素記憶レジスタは、相違の計算のためと、相違の正規化された値を記憶するためと、誤り評価多項式の個々の係数の計算中に中間値を記憶するためと、誤り評価多項式の評価の結果を記憶するためとに利用することができる。第２の要素記憶レジスタは、前のゼロでない相違の値を記憶するために利用することができる。誤り位置スタックは、誤り位置多項式の根を記憶するために利用することができる。誤り値スタックは、各誤りの大きさを記憶するためと、チエン探索中誤り位置多項式の導関数を記憶するためとに利用することができる。
したがって、本発明の目的は、最小のハードウェア量で最大数の処理機能を実行する改良されたリード・ソロモン・デコーダを提供することにある。
本発明の他の目的は、集積回路に容易に集積できる改良されたリード・ソロモン・デコーダのアーキテクチャを提供することにある。
本発明のさらに他の目的は、処理速度の向上を達成する改良されたリード・ソロモン・デコーダを提供することにある。
本発明のまたさらに他の目的は、部分的に明細書から明らかになる。
したがって、本発明は、以下に説明する構成で例示される構成上の特徴、要素の結合上の特徴および部品の配置を備えている。また、本発明の範囲は、請求の範囲に示される。
【図面の簡単な説明】
本発明をより十分に理解するために、添付図面とあわせて以下の説明が参照される。
ここで、図１は、グランド・アライアンス（ＧＡ）標準で規定されたリード・ソロモン符号を示す。
図２は、本発明により構成されたリード・ソロモン・デコーダのブロック図である。
図３は、本発明により構成されたリード・ソロモン・デコーダのタイムチャートである。
図４Ａは、本発明により構成されたガロア体（ＧＦ）多項式プロセッサを示す。
図４Ｂは、相違（Δ）の計算のための本発明の構成を示す。
図４Ｃは、相違（Δ）の正規化のための本発明の構成を示す。
図４Ｄは、誤り位置多項式Λ（ｘ）の計算のための本発明の構成を示す。
図４Ｅは、誤り評価多項式Ω（ｘ）の計算のための本発明の構成を示す。
図４Ｆは、誤り評価多項式Ω（ｘ）の評価のための本発明の構成を示す。
図４Ｇは、検出された誤りの大きさの評価のための本発明の構成を示す。
図４Ｈは、本発明により構成された多項式レジスタ記憶要素（すなわち、１（１）ビット）を示す。
図５ＡおよびＢは、多項式の根の位置のための公知のチエン探索回路を示す。
図５Ｃは、本発明により構成されたプロセッサとチエン探索アーキテクチャとの相互関係を示す。
図６は、本発明と組み合わせて使用される訂正回路のブロック図である。
図７は、誤りがその出力において計算される公知の訂正回路を示す。
好ましい実施例の詳細な説明
グランド・アライアンス（ＧＡ）標準で規定されたリード・ソロモン符号が、図１に示されている。この符号は、２０７バイトのブロック長を使用する。そのうちの１８７バイトは、「ペイロード」データを構成するＭＰＥＧ搬送パケットからなる。残りの２０バイトは、送信機（図示せず）の符号化回路によって生成される。この符号化回路は、本質的には、ガロア体ＧＦ（２５６）上の２０６次多項式として処理されるデータ・ブロックの、ブロックの最後に２０バイトの誤りチェック・バイトを形成する「残余」多項式を生成する（所与のＲ−Ｓ符号用に特定された）「ジェネレータ」多項式による「分割」を実行する。この回路は、ＧＡ標準で使用されるＲ−Ｓ符号に特定のものであるが、公知のリード・ソロモン・エンコーダの一般的な構造および処理を示しており、ブロック長、チェック・バイト数およびジェネレータ多項式のみが異なっている。
次に、図２を参照する。図２は、リード・ソロモン・デコーダの全体を符号２０で示している。図２に示すように、デコーダ２０へのデータは、シンドローム・コンピュータ２２とリード・ソロモン・ブロック・データ遅延素子２４とに入力される。計算結果のシンドロームは、シンドローム・コンピュータ２２から誤りコンピュータ２６に入力される。誤りコンピュータ２６は、後に詳述するように、誤り位置および大きさを決定する。誤り訂正器２８が設けられている。誤り訂正器２８は、誤りコンピュータ２６からの誤り位置および大きさと、リード・ソロモン・ブロック・データ遅延素子２４からの遅延データとの双方を入力として受信する。
復号プロセスの第１ステップは、シンドローム計算である。これは、ブロック・サイズまたはチェック・バイト数とは独立に、Ｒ−Ｓブロック全体の処理を必要とする。一方、シンドローム数はチェック・バイト数に等しく、したがって、シンドローム数は、ブロック・サイズとともに増加するが、これが生じるブロック・サイズの比率は小さくなる。続いて、その結果のシンドロームは、ブロック内の誤り位置および大きさを決定するために使用される。シンドローム計算を実行する標準的な周知の回路は、「誤り制御符号」の第６章の特に第１７４頁に示されており、この文献は参照によりこの明細書に組み込まれる。ｔ個の誤り（ＧＡ標準ではｔ＝１０）まで訂正することができるＲ−Ｓ符号用デコーダは、このような回路を２ｔ個必要とし、各シンドロームに対して１つとなる。
シンドロームの値は、それを説明するためには、ブロック全体がデコーダ２０に入力され、入力データがリード・ソロモン・ブロック・データ遅延素子２４によって１ブロックの間隔分だけ遅延させられるまでは分からない。続いて、誤り計算が、誤りコンピュータ２６によって実行され、デコーダからのデータ出力が訂正される。誤り訂正は、完全なブロック間隔を必要とする。誤り計算が１ブロック間隔内で完了するならば、Ｒ−Ｓブロックの「パイプライン」処理を達成することができ、そのデータは、第２の間隔分だけ再度遅延させられる。デコーダ２０のシステムのタイムチャートが図３に示されている。
前述したように、誤りコンピュータ２６は、送信されるデータに適合したガロア体（８ビットのバイトの場合にはＧＦ（２５６））上の多項式演算処理を使用する計算によって誤り位置および大きさを決定する。まず、誤り位置多項式が生成されなければならない。その多項式のＧＦ（２５６）上の根は、それぞれＲ−Ｓブロック内の各検出された誤りの位置に対応する。これは、多数の標準的なアルゴリズムのいずれを用いても行うことができる。そのアルゴリズムの中でも、ユークリッドおよびバールカンプ−マッシーのものが最も良く知られている。高速リード・ソロモン・デコーダの従来技術の多くのものは、ユークリッド・アルゴリズムを使用している。これは、必要となる多項式の計算をより高速にできるからである。一方、ユークリッド・アルゴリズムは、実現により多くのハードウェア量を必要とするという欠点を有する。他方、バールカンプ−マッシー・アルゴリズムは、高速ではないが、ずっと少ないハードウェア量で実現できる。これは、ユークリッド・アルゴリズムで必要とされるものよりも少ない計算論理およびデータ記憶で足りるからである。したがって、バールカンプ−マッシー・アルゴリズムを利用することにより、より効率的な設計が達成される。バールカンプ−マッシー・アルゴリズムを実現するためのアーキテクチャは、アーキテクチャーを最適化し、このアルゴリズムの実行時間を減少させる手段となるように、後に詳述される。
誤り評価多項式は、誤り位置多項式に関係し、誤り位置多項式およびＲ−Ｓブロックのシンドローム値を用いて計算される。この２つの多項式は、誤り位置が決定されると、それに続いて、誤りの大きさを計算するために使用される。これは、誤り位置多項式の根（すなわち、多項式の変数に代入されると、ゼロの結果を与えるＧＦ（２５６）の基本値）を見つけることにより行われる。根のそれぞれは、ブロックの誤りの位置に対応する。根の発見は、チエン探索として知られている徹底的な探索方法を使用して実行される。チエン探索では、すべての可能なブロック位置の値が、多項式に代入され、どの値がゼロの結果をもたらすかが決定される。続いて、多項式の根は、以下に述べるように記憶され、周知のフォニー・アルゴリズムが、誤り位置多項式および誤り評価多項式を用いて各根につていの誤りの大きさを計算するために使用される。上述した処理のすべては、専用ハードウェアを必要とするチエン探索を除いて、後に詳述する本発明によって構成されたアーキテクチャを使用して実行することができる。
誤り位置多項式を計算するバールカンプ−マッシー・アルゴリズムのフローチャートは、「誤り制御符号の理論と実践」第７章の特に第１８６頁に示されており、この文献は参照によりこの明細書に組み込まれる。
一般的に、バールカンプ−マッシー・アルゴリズムでは、このアルゴリズムの所与の繰り返し期間中における２つの多項式Λ（ｘ）とＢ（ｘ）の最大長は、その繰り返し期間中におけるレジスタ長パラメータＬの値に対応し、必ずしもレジスタの最大長ｔ＋１に対応しない。一方、実際の設計では、このアルゴリズムを実現するために使用される多項式シフト・レジスタは、常に最大長を有する。これは、任意の繰り返し期間中に、多項式処理を実行するのに必要となるクロック・サイクル数が、その繰り返しにおける多項式の実際の長さに関わらず、常にｔ＋１になることを意味する。アルゴリズムの各繰り返し期間中にこのような２つの処理があるので、結果として、実際にはずっと少ないクロック・サイクルで足りるかもしれないが、２（ｔ＋１）のクロック・サイクルが使用される。これは、クロック・レートがハードウェアにより制限されるならば、復号速度をかなり減少させるか、そうでなければ、所望の復号レートを達成するためにより高速のクロックを必要とする。
多項式プロセッサ６０は、レジスタ長パラメータＬを使用して、２つのレジスタの長さを設定し、続いて、Ｌより高い次数の係数を記憶するすべてのレジスタ素子の入力から出力に「短絡回路」を生成することにより、この制限を克服することができる。定数長レジスタを使用すると、アルゴリズムの２ｔ回の通過に必要なクロック・サイクル数は、４ｔ（ｔ＋１）である。一方、可変長レジスタを使用すると、Ｌは現在の繰り返し数の半分を超えることはない。所与の通過に対する最大サイクル数は２（Ｌ＋１）となり、アルゴリズムの全サイクル数は演算列の合計であり、２ｔ（ｔ＋３）に等しい。２つの因子のほとんどの実行時間の削減は、このようして達成される。これは、ＧＡ標準にとって２６０クロック・サイクルに等しい。
誤り評価多項式Ω（ｘ）は、前記計算された誤り位置多項式とシンドローム多項式のモジュロ２ｔ積である。特に、誤り位置多項式は、以下に述べる（図４Ａ参照）ように２つの記憶レジスタ６１および６２の１つにすでに存在し、誤り評価多項式は、第２のレジスタ６２（２ｔの長さを有する）に書き込み可能であるので、多項式プロセッサはこの計算を実行することができる。各積の係数は、誤り位置多項式のすべての項を使用しており、したがって、計算にはｔ＋１のクロック・サイクルを必要とする。このように、誤り評価多項式は、２ｔ（ｔ＋１）のクロック・サイクルで計算され、これは、ＧＡ標準にとって２２０に等しい。
当業者には理解されるように、バールカンプ−マッシー・アルゴリズムは、２つの多項式Λ（ｘ）およびＢ（ｘ）（Ｔ（ｘ）が一時的な記憶として利用されるので、実際の実現では必要とされない）を必要とし、２ｔ回の繰り返しを実行する。「誤り制御符号の理論と実践」の第１８６頁に記載されているアルゴリズムを実行するシフトレジスタ・アーキテクチャは、その第１８９頁にも示されている。完全なリード・ソロモン復号プロセスのフローチャートも、前記テキストの第１９０頁に示されている。前述したように、これらのすべては、参照によりこの明細書に組み込まれる。
次に、図４Ａを参照する。この図は、本発明によるリード・ソロモン復号のための誤り計算プロセッサ６０を示している。好ましい実施例において、プロセッサ６０は、最大長ｔ＋１および２ｔをそれぞれ有する多項式上でガロア体演算を実行する。ここで説明され、当業者には明らかなように、本発明によって構成されるプロセッサ６０は、最小のハードウェアと最小の計算時間の双方のために最適化されている。特に、プロセッサ６０は、ガロア体上の多項式だけでなく、ガロア体の演算要素に記憶し、またその数学的処理を実行するように設計されている。このような要素は、標準的な２進数（ビット）を使用して表現することができる。たとえば、ＧＦ（２５６）の要素は、８ビット、すなわち１バイトを使用して表現することができる。ＧＦ上の多項式はその係数によって表現することができる。その結果、係数のそれぞれはＧＦの要素である。したがって、第ｎ次の多項式は、ｎ＋１個のこのような要素によって表現することができる。２進表現を使用するＧＦ（２５６）の場合には、これはｎ＋１バイトに等しくなる。
これにより、ＧＦの要素を標準的なデジタル・データ・レジスタに記憶すること、多項式をレジスタ群に記憶すること、ならびに要素と多項式の評価および演算処理を従来のデジタル論理を使用して実行することが可能となる。
図４Ａを参照して、リード・ソロモン・ブロックの２ｔ個のシンドロームは、シンドローム・コンピュータ２２で計算され、シンドローム・レジスタ７４に置かれる。これら２ｔ個のレジスタ７４のそれぞれは、１つのシンドロームを記憶する。このシンドロームは、まさにＧＦの要素である。このように、ＧＦ（２５６）のシンドローム・レジスタは、２ｔバイトのレジスタからなる。Ｒ−Ｓブロック間のタイミング・ギャップが認められないならば、これらのレジスタは、同時に２ｔ個のシンドローム計算の結果を受信しなければならない。この場合に、２ｔ個の個別のレジスタが必要となる。この理由は、図３のタイムチャートからも分かるように、Ｒ−Ｓブロックｎに対して誤り計算が実行されているのと同時刻に、Ｒ−Ｓブロックｎ＋１のシンドロームが計算されており、そのシンドローム値は、誤り計算がブロック全体（すなわちブロックの終わり）に対して実行されるまで利用可能でないからである。さらに、シンドローム値は、シンドローム計算の新たなセットを開始するために、後に続くブロックの開始時にクリアされなければならない。これは、シンドローム値をその記憶レジスタに転送するのに、２ｔ個のクロック・サイクルよりも少ないクロック・サイクルが利用可能であることを意味し、したがって、シンドローム値は、同時に転送されなければならないことを意味する。これは、２ｔ個のシンドロームの２ｔ個のレジスタへの同時書き込みを必要とする。一方、誤り計算にとって、所与の時間に１つのレジスタの内容を読み出すことだけが必要である。ギャップがそのタイミングにおいて認められるならば、２ｔ個のシンドローム計算の最終結果を、このギャップの期間中に連続して転送することができ、シンドローム・レジスタは、２ｔバイトの位置を有するレジスタ・ファイル、すなわちさらに小さなメモリを用いて実現することができる。シンドローム計算は、「誤り制御符号」の第６章に示されるように、多数の周知の方法のいずれを使用しても実行することができる。
プロセッサ６０によって実行される３つのＧＦアルゴリズムは、誤り位置多項式を計算するためのバールカンプ−マッシー（Ｂ−Ｍ）アルゴリズムと、誤り評価多項式の計算と、誤り値を計算するためのフォニー・アルゴリズムである（誤り位置を計算するチエン探索は、図５Ａ〜Ｃに示す方法および構成によって実行されることが好ましい）。これらのアルゴリズムが実行されるシーケンスは、「誤り制御符号の理論と実践」の第１９０頁に示されている。３つのアルゴリズムは、すべてＧＦの要素および多項式の数値計算を含む。アルゴリズムの検査は、評価および演算処理の制限されたセットのみが実行されること、および要素の最大数と多項式の最大数が、これら３つのアルゴリズムのいずれに対しても任意の所与の時間に記憶される必要があることを示している。これにより、図４Ａ〜Ｇに示す斬新でより効率的なアーキテクチャ構成が達成される。
図４Ａに示すように、プロセッサ６０は、ＧＦ多項式を記憶するための２つの記憶レジスタ６１および６２（以下「レジスタＡおよびＢ」ともいう。）、ＧＦの要素を記憶するための２つのレジスタ７１および７２（以下「レジスタＸおよびＹ」ともいう。）、出力側にＧＦ加算器８０が接続されたＧＦ乗算器７８、ならびに任意のデータのソースとデスティネーションを相互接続するデータ・バスを含んでいる。このアーキテクチャの１つの特徴は、データ・バスの２つの完全な組が存在することである。これは、ソースとデスティネーションとの間の２つの同時データ転送を行うことを可能とする。これにより、以下に示すように、あるアルゴリズムを、より少ない時間、すなわちより少ないクロック・サイクルで完了させることができる。
ＧＦの各要素が８ビットの２進数で表現されているＧＦ（２５６）の場合に、２つの要素レジスタ７１、７２のそれぞれは、バイト記憶レジスタを使用して実現することができる。２つの多項式レジスタ６１、６２は、記憶された多項式の各係数ごとに１バイトを有する複数バイト記憶を使用して実現することができる。
ｔバイトの誤りを訂正する能力を有するＲ−Ｓ符号について、誤り計算プロセッサによって実行される３つのアルゴリズムに必要となる最小の多項式記憶は、次数ｔの１つの多項式（ｔ＋１バイトのレジスタ記憶を必要とする）と、次数２ｔ−１の１つの多項式（２ｔバイトの記憶を必要とする）とからなる。好ましい実施例におけるデータ・バスは８ビット・バスである。乗算器７８および加算器８０は、それぞれ２つの８ビット入力と１つの８ビット出力を有し、ＧＦ（２５６）演算におけるそれらの各処理を実現する標準的な結合論理を使用して実現される。
ＧＦ演算処理（加算、乗算および除算）およびデータ転送は、最終結果が要素または別の多項式を問わず、多項式の各個々の要素に実行されなければならないので、個々の多項式の係数バイト・レジスタへの高速連続アクセスを行うメカニズムが必要となる。これは、最上位の係数がレジスタの前部（出力）に位置し、最下位の係数がレジスタの後部（入力）に位置する、係数バイトのシフト・レジスタとして多項式記憶レジスタを実現することによって達成される。そして、多項式の処理は、記憶レジスタ内で係数が「循環」されることを要求する。これにより、新しい係数が、すべてのクロック・サイクルで（多項式レジスタがソースまたはデスティネーションの一方または双方であるかに依存して）出力され、レジスタに入力され、または双方が行われ、多数のクロック・サイクルがレジスタの長さに等しくなった後に、係数はレジスタ内のそれらの最初に位置にあることとなる。
記憶レジスタ間のデータ転送に加えて、記憶されたデータに実行される処理は、乗算、除算および加算である。最初の２つの処理は、ＧＦ乗算器７８によって実行される（除算は、除数をＧＦ上の逆数にし、その結果と被除数との乗算を単純に実行することにより、乗算器７８によって達成されることが分かる）。加算器８０によって実行される加算は、ＧＦ（２５６）または考察の対象となる他の任意のＧＦについて、加算数と被加算数を表す２つのバイト要素のビット単位での排他的論理和からなる。プロセッサ６０の構成は、上記個々の処理に加えて、第３の要素の加算を後に続けることにより、２つの要素の乗算または除算を可能にする。これらの組み合わせは、このアーキテクチャによって実行される３つのアルゴリズムのいずれにも必要とされるＧＦの要素の演算処理のすべてを構成する。
次に、前記アルゴリズムのさまざまな部分がどのように計算されるかを理解するために、図４Ｂ〜４Ｇを参照しながら、以下の説明を行う。
バールカンプ−マッシー・アルゴリズムは、３つの分離した処理からなる。これらの処理は、このアルゴリズムの２ｔ回の繰り返しのそれぞれについて実行される。これらの第１のものは、いわゆる相違（Δで示す）の計算である（図４Ｂ参照）。これは、現在の繰り返しにおける誤り位置多項式（Λ（ｘ）で示す）（この多項式は、最後の繰り返しにおいてはアルゴリズムの最終結果を構成し、Ｂ−Ｍアルゴリズムの過程において連続的に「ビルド・アップ」される）の値と、２ｔ個のシンドロームの値とによって決定される。シンドロームは２ｔ個のシンドローム記憶レジスタ７４に記憶され、Λ（ｘ）の係数は多項式記憶レジスタ６１に記憶される。所与の繰り返しにおけるΔの値は、個々のΛ（ｘ）の係数（レジスタ６１に記憶）とシンドローム（レジスタ７４に記憶）の積の蓄積された合計を生成することにより形成され、要素レジスタ７０に記憶される。Λ（ｘ）の値はこの処理によって変更されないので、その係数は、レジスタ６１から読み出され、続いて、レジスタ６１に書き込まれる、すなわち「循環」される。これにより、個々の係数のすべてをアクセスし、適切なシンドロームと乗算し、かつ、その最終値が循環の終了時に所望のΔの値を構成する、蓄積された合計に加算することが連続的に可能となる。この処理では、多項式レジスタの循環技術が、所望の結果を達成するために使用される。この好ましい方法では、レジスタ６１は、ソースの多項式レジスタおよびデスティネーションの多項式レジスタの双方に使用される。一方、レジスタ７０は、ソースの要素レジスタおよびデスティネーションの要素レジスタの双方に利用される。
上記相違Δがゼロでないときに、Ｂ−Ｍアルゴリズムの繰り返しにおいて生じる第２のステップは、その正規化、すなわちレジスタ７２に記憶された、その前の非ゼロの値による除算である（図４Ｃ参照）。この新たに正規化された値は、レジスタ７０に記憶され、古い正規化前の値は、次の正規化に使用するためにレジスタ７２に記憶される。
Ｂ−Ｍアルゴリズムの繰り返しの第３の最終ステップは、相違Δがゼロでないときにのみ生じる。このステップは、レジスタ６１にまだ記憶されている多項式Λ（ｘ）（図４Ｄ参照）の更新された値を、その現在の値とΔ（レジスタ７０に記憶）の新しい値に基づいて計算することと、レジスタ６２に記憶されているＢ（ｘ）で示される補助多項式の更新された値を計算することである。ある条件下において、多項式Ｂ（ｘ）は、Λ（ｘ）の現在の（更新されていない）値になるように更新される。（バールカンプ−マッシー・アルゴリズムで規定された）他の条件下では、多項式Ｂ（ｘ）は更新されず、レジスタ６２に再循環される。いずれの場合にも、２つの多項式は、それらの各レジスタ（６１および６２）に循環され、それぞれの個々の係数は、１つのクロック・サイクルで読み出され、書き込まれる。更新されたΛ（ｘ）の計算は、補助多項式Ｂ（ｘ）の各係数を、正規化されたΔ（レジスタ７０）と乗算し、そして現在のΛ（ｘ）（レジスタ６１）の対応する係数（すなわちｘの同じ累乗）を加算することから構成される。これは、Λ（ｘ）の全係数に対してなされ、結果の更新された係数は、レジスタ６１に循環され戻される。
図４Ｅを参照して、誤り評価多項式Ω（ｘ）の計算が、Ｂ−Ｍアルゴリズムによって先に計算され、レジスタ６１にまだ存在する誤り位置多項式Λ（ｘ）と、シンドローム・レジスタ７４にまだ存在する２ｔ個のシンドロームを使用して実行される。先の多項式と同様に、誤り評価は、Λ（ｘ）の選択された係数と選択されたシンドロームとの積の累積された合計からなるΩ（ｘ）の各係数により、２ｔ個の繰り返しの過程で連続的に「ビルド・アップ」される。最終結果は、２ｔ個の係数を有する２ｔ−１の次数の多項式であり、レジスタ６２に記憶される。この点で、レジスタ６１（ｔ＋１個の要素レジスタからなる）は、誤り位置多項式Λ（ｘ）を記憶し、レジスタ６２（２ｔ個の要素レジスタからなる）は、誤り評価多項式Ω（ｘ）を記憶する。
Ｒ−Ｓブロックのデータ誤りの実際の位置決定は、誤り位置多項式Λ（ｘ）の根を発見することにより実行される。根のそれぞれは、誤り位置に直接対応する。これは、誤り計算プロセッサ６０によって実行されないが、その代わりに、チエン探索によって実行される。チエン探索は、Ｒ−Ｓブロックのすべての可能なデータ位置の値で多項式Λ（ｘ）を評価し、ゼロの結果となるすべて（すなわち多項式の根）は、ブロックの誤りに対応し、そして誤り位置スタック６６に記憶、すなわち「プッシュ」される。続いて、この根はＧＦの要素であり、ＧＦ（２５６）では、データ・バイトとして表現される。Ｒ−Ｓ符号は、多くともｔ個の誤りを訂正することができるので、誤り位置スタックは、ｔの深さと８ビット（１バイト）の幅を有する。
一般的に言えば、誤り位置多項式の根のチエン探索は、そのｎ個の値の評価から構成され、ここで、ｎはＲ−Ｓブロックの長さ（ＧＦ標準では２０７）に等しい。これは、各評価が非常に高速に実行されなければならないことを意味する。このため、以下に述べるようにホーナー法を使用すると、１つの値当たりｔ＋１のクロック・サイクルを必要とするので、多項式プロセッサを使用することはできない。探索をｎサイクルで完了できるように、１サイクルで各評価を行うハードウェアが必要とされる。図５ＡおよびＢに詳細に示す回路は、誤り位置多項式の係数が初期化のためにロードされた一組のレジスタから構成され、各連続クロック・サイクルで、ｉ番目の係数レジスタの内容は、ｉ次のＧＦ（２５６）のプリミティブαと乗算される。チエン探索の詳細も、「誤り制御符号」の第１５９頁から１６０頁に見出すことができる。続いて、すべてのｔ個のレジスタのＧＦ（２５６）の合計が生成され、根が発見されたかどうかが決定される。この場合に、根は、次の使用のためにスタック・メモリの最上位にプッシュされる。誤り評価多項式の計算は、これらの根を使用せず、したがって、バールカンプ−マッシー・アルゴリズムの完了後、チエン探索と同時に実行可能である。ＧＡ標準にとって、必要とされるクロック・サイクルのそれぞれの数はほぼ等しい（２２０対２０７）。発見された根の数が多項式の次数と等しくないならば、訂正不可能な誤り状態が存在する。これは、ブロックの誤りの数がｔを超えていることを意味し、そのブロックを訂正することはできない。このような状況の存在は、ブロックが正しくないことを示す。探索は、Ｒ−Ｓブロックの最後の位置に対応するＧＦの要素から開始されるので、誤り位置スタック６６が必要とされる。その結果、ブロック・データが最初から最後の順番で処理（および訂正）されるならば、多項式の根の順序を、それらが探索中に評価された順序と逆にする必要がある。
最後に実行されるアルゴリズムは、フォニー・アルゴリズムである。このアルゴリズムは、誤り評価多項式だけでなく、誤り位置多項式の一次導関数（ＧＦの意味での）を使用する。両者は、チエン探索によって発見され、誤り位置スタック６６に記憶されている各誤り位置の根において評価される。
一般的に、フォニー・アルゴリズムは、前記根と２つの多項式が与えられると、誤りの大きさを計算するために使用される。このアルゴリズムは、「誤り制御符号の理論と実践」の第１９０頁に示された式によって与えられる。Ω（ｘ）は、チエン探索中に発見されたそれぞれの根ｘについて評価されなければならない。一方、ＧＦ（２５６）演算では、Λ（ｘ）の導関数は、ｘで評価される多項式の奇数の累乗項の合計を取り、それをｘで除算することにより発見される。Λ（ｘ）のすべての項は探索中に評価されるので、根が１つ発見されるごとに、奇数の累乗項のみの合計を生成し、それを第２のスタック・メモリに同時に根とともに記憶することは非常に簡単なことである。これは、導関数を評価するのに必要となる時間をなくし、この第２のスタックは、誤りの大きさを続いて記憶するのに必要とされるので、ほとんど追加のハードウェアを必要とせず、追加の記憶メモリを必要としない。スタックの各根について、そのポインタがアルゴリズムの開始時にリセットされ、Ω（ｘ）は、以下に示すホーナー法を用いて評価される。これは、２ｔのクロック・サイクルを必要とし、ｘΛ’（ｘ）が、必要とされる除算のために第２のスタック・メモリから取り出される。これには、１サイクルを要する。一般的な場合では、根の累乗による除算が必要とされるが、ＧＡ標準では、この累乗は１であり、したがって、先に実行されなかったｘΛ’（ｘ）のｘによる除算は省略される。その結果として、チエン探索および誤り評価多項式の計算の双方が完了すると開始するこのアルゴリズムは、ｔ個の根について最悪の場合にｔ（２ｔ＋１）のクロック・サイクルを必要とし、これは、ＧＡ標準については２１０に等しい。ＧＦ上の多項式の一次導関数は、その多項式の奇数項の合計である。チエン探索は、奇数および偶数のすべての多項式の項の評価を必要とするので、すべての位置の根に対する所望の奇数項は、その根についての完全な多項式から選択され、それらの合計が計算され（根を発見するためにすべての項の合計と同様に）、前記第２のスタック６８にプッシュされる。このスタックは、誤り値スタックと呼ばれ、ｔ個の位置の深さを有する。続いて、位置の根およびそれらの関連した多項式の導関数の双方が２つのスタックに記憶され、各位置に対応する誤りの実際の値を計算するために使用される。
次に、図４Ｆを参照する。この図は、チエン探索によって発見された値のそれぞれにおいて誤り評価多項式Ω（ｘ）の評価を行うための構成を示している。この評価は、レジスタ６２に記憶された多項式の係数と誤り位置スタック６６に記憶された位置の根とを使用して、誤り計算プロセッサ６０によって実行される。これは、各根に対して実行され、レジスタ７０に記憶された累積された積を、スタックに記憶された根の値と乗算し、その結果をレジスタ６２に記憶された現在の多項式の係数に加算し、そして新しく累積された結果の積をレジスタ７０に戻すことを連続的に行うことによりなされる。これは、Ω（ｘ）の２ｔ個の係数のすべてに対して繰り返され、最後の繰り返しの最終的な結果は、位置の根に対して評価されたΩ（ｘ）の値であり、レジスタ７０に記憶される。多項式評価のためのこのアルゴリズムは、ホーナー法として知られている。
次に、誤りの大きさの評価を説明するために、図４Ｇを特に参照する。特に、フォニー・アルゴリズムは、所与の根に対するΩ（ｘ）の前記値が、その同じ根において評価されたΛ（ｘ）の導関数によって除算されることを必要とする。一方、Λ（ｘ）の導関数は、チエン探索の副産物として得られたものであり、根の傍らの誤り値スタック６８に格納された。したがって、その根において評価された両方の多項式の値は、直ちに利用でき、所望の誤り値を得るためにＧＦ乗算器／除算器７８によって除算可能である。この結果は、根の値の傍らにある誤り値スタック６６に記憶され、Λ（ｘ）の一次導関数を置き換える。この手続は、ホーナー法によるΩ（ｘ）多項式の評価を含み、チエン探索によって発見されたΛ（ｘ）のすべての根に対して繰り返される。そして、２つのスタックは、ｔ個の誤り値とそれらの位置を含み、これらの双方は、実際の誤り訂正を実行する誤り訂正器２８によって必要とされる。
実際の誤り訂正は、すべての誤り位置および大きさが決定された後に行われ、図６に示すものと同様の回路によって実行される。この回路は、前述したように、入力されたＲ−Ｓブロック・データを２つのブロック間隔だけ遅延させ、そして、誤り計算部で発見され、２つのスタック・メモリに記憶された誤りおよび大きさを使用して訂正を実行する。チエン探索が実行されると、チエン探索の初期化は、データが到着した順序とは逆のブロック位置の順序で探索が実行されることを必要とする。したがって、スタック・メモリが誤り情報を記憶するために使用され、そのスタックは、Ｒ−Ｓデコーダの誤り計算部および誤り訂正部の双方において誤り位置および値の双方の記憶のために必要とされる（データは、誤り計算ステップではスタックに「プッシュ」され、誤り訂正ステップではスタックから「ポップ」されなければならない）。それぞれの部がＲ−Ｓブロックに対してそれらの処理を完了すると、誤り計算の結果は、誤り訂正部に直ちに転送される。誤り訂正部は、ブロック全体の訂正が終了すると、もはや誤りスタックの内容を必要としないので、２つの部は、それらのそれぞれの誤り位置と値のスタックを「ピンポン」形式で交換することができ、これにより、誤り訂正器２８は、最も最近の誤り計算の結果を受信し、続いて、新しいブロックの訂正を開始することができ、そして、誤り計算プロセッサ６０は、廃棄される誤りデータを受信する。この誤りデータは、新たなデータに場所を空けるために除去可能である。
データ・ブロックの最初の位置から開始する各Ｒ−Ｓブロック・データ位置に対応するＧＦの要素は、カウンタによって生成される。このカウンタは、ブロックの開始に対応する値に初期化され、ブロック位置のすべてにわたって正順序（すなわち、逆ではない）でカウントを行う。これは、各位置の値を、誤り位置スタック６６の最上位の内容と比較することによりなされる。２つの値が等しいときは、スタックの最上位におけるΛ（ｘ）の根は、Ｒ−Ｓブロックの現在のデータ・バイトの位置に対応する。続いて、データ値スタックの最上位の内容は、このブロック位置のデータ・バイトに加えられ、ＧＦ（２５６）演算において、これは、誤り値の８ビットとデータ・バイトの８ビットとのビット演算による排他的論理和からなる。それから、次の誤り位置および値の対が最上位になるように、２つのスタックはポップされ、手続が繰り返される。これが、スタックが空になるまで、スタックに記憶された誤り位置および値の対のすべてに対して実行される。この時点で、Ｒ−Ｓブロックの検出された誤りのすべては訂正されてしまう。
最後に、前述した開示は、すべてを網羅しておらず、本発明の範囲内においてプロセッサ６０にさまざまな変形を加えることが可能であると理解すべきである。たとえば、多項式記憶レジスタの長さは、Λ（ｘ）と補助多項式Ｂ（ｘ）の双方についてはｔ＋１の長さを有するものとして、Ω（ｘ）については２ｔの長さを有するものとして開示されている。これは、Λ（ｘ）を記憶する多項式記憶レジスタ６１が、Λ（ｘ）のｔ＋１個の係数用にｔ＋１個の要素レジスタからなることを意味する。一方、レジスタ６２は、補助多項式Ｂ（ｘ）を記憶するために使用されるときはｔ＋１個の要素レジスタの長さを有するが、Ω（ｘ）を記憶するためには２ｔ個の要素を必要とする。したがって、レジスタ６２は、いずれの長さにも構成される能力を有しなければならない。これは、マルチプレクサを使用することにより達成することができる。マルチプレクサは、所望の長さの多項式次数を有する係数に対応する要素レジスタを選択する。
多項式記憶レジスタの長さを変更する機能は、第３のレジスタ（すなわち、Λ（ｘ）とＢ（ｘ）についての長さｔ＋１の２つと、Ω（ｘ）についての第３のもの）を設ける必要性をなくすためと、任意の所望の長さに多項式記憶レジスタを構成することを可能にする必要性をなくすために必要とされる。これは、Ｂ−Ｍアルゴリズムにおいて役に立つ。このアルゴリズムは、その過程において、変化するパラメータとしてレジスタ長を指定するからである。これは、一般的には、Ｒ−Ｓデコーダのソフトウェアによる実現のために実際に使用されるが、アルゴリズムをより少ないマシン・サイクルで完了させるために、公知のハードウェアによる実現は、固定長シフト・レジスタを使用する。
図４Ａの誤り計算プロセッサ・アーキテクチャにおいて多項式記憶レジスタ長を変更するこのような一般化された方法の使用は、すでに最小のハードウェアと最大のデータ転送機能の双方について最適化されてきており（すなわち、任意の２つの所望のデータ転送は同時に発生することができる）、これにより、要求された誤り計算は、前述したものよりもさらに少ないクロック・サイクルで実行可能である。この理由は、多項式を含む任意の処理が、そのレジスタを介して完全な多項式の循環を必要とし、実際の多項式に長さがそれぞれｔ＋１または２ｔよりもずっと小さいときでさえも、これが、ｔ＋１個または２ｔ個のいずれかの係数からなり、したがって、これらの係数の多くのものはゼロでないということによる。これは、実際の多項式の長さに関わらず、すべての多項式処理に対して同じクロック・サイクル数（ｔ＋１または２ｔ）が必要とされることを意味する。
図４Ｈを参照する。この図は、そのユニークな回路配置により、多項式記憶レジスタ長の調整が可能な、好ましい多項式レジスタ記憶素子を示している。特に、この回路は、好ましくは、フリップ・フロップ９１およびマルチプレクサを含んでいる。マルチプレクサは、インバータ９２、２つのＡＮＤゲート９３、９４およびＯＲゲート９５を含んでいる。この構成により、多項式レジスタの任意の記憶素子を効率的に「短絡回路」にすることができ、これにより、レジスタの実際の長さを減少させることができる。Ｂ−Ｍアルゴリズムの実行が進むにしたがい、これらの素子の「短絡回路」にされるものが減少し、これにより、Ｂ−Ｍアルゴリズムのレジスタ長パラメータの値は増加するので、多項式レジスタの長さは「成長」する。レジスタ長の制御は、誤り計算プロセッサ６０の制御回路（図示せず）によって実行される。この制御回路は、さまざまなアルゴリズムを実現するために実行されなければならない、記憶レジスタ、演算ユニット（乗算器／除算器および加算器）ならびにデータ路のすべての制御機能を実現する。Ｂ−Ｍアルゴリズムについて、多項式記憶レジスタの長さを変更する能力は、必要とされるクロック・サイクル数をほぼ２分の１に減少させることになる。また、この能力は、誤り評価多項式Ω（ｘ）の計算に必要なクロック・サイクル数を約３分の１まで減少させる。一方、この能力のために支払われるペナルティは、データ路に追加される複雑さと伝播遅延のために、プロセッサが処理される最大クロック周波数が減少するかもしれないということである。
使用される誤り訂正を実行する選択的な方法が、図７に示される。この方式では、誤り計算は、Ｂ−Ｍアルゴリズムまたはいくつかの他の手段（たとえばユークリッド・アルゴリズム）のいずれかを使用する誤り位置および誤り評価多項式の計算のみからなり、チエン探索は、図５Ａおよび５Ｂに示すものと同様のハードウェアを使用して、実際の誤り訂正中に実行される。また、この回路は、Λ（ｘ）およびその導関数ｘΛ’（ｘ）の双方を同時に評価するために使用することができる。２ｔ−１個のレジスタとＧＦ定数乗算器からなる同様の回路は、Ω（ｘ）を並行に評価するために使用される。Λ（ｘ）の根が発見されると、その根に対応するｘΛ’（ｘ）およびΩ（ｘ）の値がＧＦ除算器に入力される。このＧＦ除算器は、フォニー・アルゴリズムを実現し、誤りの大きさを出力する。そして、この大きさは、前述したのと同じ方法で、誤りのあるデータ・バイトに加えられ、訂正が実行される。この技術の１つの主な欠点は、チエン探索が最後のＲ−Ｓブロック位置の値から開始されなければならないので、探索および評価が逆のブロック順序で実行されるということである。これは、訂正を実行するためにＲ−Ｓブロックを逆順序にすることを必要とし、さらに、後に続くデータ処理が、ブロックのその本来の順序であることを必要とするならば、その後、もう一度逆順序にすることを必要とする。
一方、図７の方法は、誤り訂正段階において実時間で、誤り位置多項式および誤り評価多項式の生成に続くすべての誤り計算を実行するという利点を有する。これは、誤り評価多項式の評価およびフォニー・アルゴリズムが誤り計算部でもはや実行されないので、誤り計算段階が、より少ない時間（すなわち、より少ないクロック・サイクル）で実行できることを意味する。
プロセッサ６０は、必要な多項式の双方を、最小のハードウェアおよびクロック・サイクルを使用して、前述した方法で計算するために使用可能である。一方、広範囲のＧＦ処理を実行するこのアーキテクチャの能力のために、プロセッサ６０は、ブロックの開始に対応するＲ−Ｓブロック位置の値について双方の多項式の個々の項のすべてを評価するためにも使用可能であり、チエン探索は、この位置で開始可能であり、逆順序にすることを必要とせず、実際のブロックの順序で実行可能である。多項式の項の計算は、多項式変数の対応する、すなわち、この場合には、Ｒ−Ｓブロックの最初の位置に対応する累乗のものによる各係数のＧＦ乗算からなる。ブロック・サイズは固定されているので、この最初の位置の値の最初の２ｔ個の累乗は、デコーダの設計中に計算し、記憶７６（図４Ａ）に多項式の引数として記憶することができる。これらの値は、好ましくは、「ハードワイヤード」であり、したがって、小さな（２ｔバイト）の読出専用メモリに記憶することができる。前述したように、多項式係数は、それらの各記憶レジスタ（６１および６２）に記憶され、これにより、Λ（ｘ）多項式のｔ＋１個の項およびΩ（ｘ）多項式の２ｔ個の項は、各係数を記憶７６の対応する多項式引数と乗じることにより計算されてもよい。これらの２つの多項式について、これは、３ｔ−１個のクロック・サイクルを必要とする。これは、この方法を使用することにより省かれるｔ（２ｔ＋１）個の誤り計算クロック・サイクルよりもかなり少ない。結果の多項式の項は、続いて、チエン探索および評価を初期化するために使用される。この配置では、チエン探索および評価は、前述したように、誤りの実際の探索と訂正の双方を同時に実行する。この初期化は、初期多項式の項を図７のチエン探索／誤り訂正ハードウェアに転送することにより実行される。
誤り計算部における多項式プロセッサ・アーキテクチャの使用は、特に、ある特定のＲ−Ｓ符号（たとえばＧＡ標準）用に設計されたデコーダの場合には、Ｒ−Ｓブロックの逆転の必要性をなくす手段を提供する。これは、このアーキテクチャの柔軟性および汎用性を示すものとしても働く。
この方法の利点は、フォニー・アルゴリズムが、誤り計算の部分として実行されないので、より少ないクロック・サイクルが必要とされることである。これは、Ｒ−Ｓブロック間のタイミング・ギャップが認められていないときだけでなく、Ｒ−Ｓブロックがあまり大きくない場合にも価値があるものとなる。不利な点は、フォニー・アルゴリズム用の第２のＧＦ除算器に加えて、Ω（ｘ）多項式の高速評価ならびにΛ（ｘ）およびΩ（ｘ）の初期化のための追加ハードウェアを必要とすることである。したがって、この方法は、限られた状況下でのみ価値を有するが、いくつかの場合には、性能の改善は、追加ハードウェアを正当化するのに十分なものとなる。
この発明は、集積回路上に効率よく実現するのに向いており、大規模データ・ブロックの場合については、リード・ソロモン・デコーダの技術状態の進歩を代表することができる。
【図１】
0003970337.tif 000002
【図２】
0003970337.tif 000003
【図３】
0003970337.tif 000004
【図４Ａ】
0003970337.tif 000005
【図４Ｂ】
0003970337.tif 000006
【図４Ｃ】
0003970337.tif 000007
【図４Ｄ】
0003970337.tif 000008
【図４Ｅ】
0003970337.tif 000009
【図４Ｆ】
0003970337.tif 000010
【図４Ｇ】
0003970337.tif 000011
【図４Ｈ】
0003970337.tif 000012
【図５Ａ】
0003970337.tif 000013
【図５Ｂ】
0003970337.tif 000014
【図５Ｃ】
0003970337.tif 000015
【図６】
0003970337.tif 000016
【図７】
0003970337.tif 000017