JP3834122B2 - 誤り位置検出多項式計算装置 - Google Patents

Description

【０００１】
【発明の属する技術分野】
本発明は、格納または伝送されたデータ内に存在するエラーを訂正するための誤り訂正装置に関し、特に、リードソロモンコード（Reed-Solomon Code）により符号化されたデータ内の誤りを訂正するのに用いられる誤り位置検出多項式の係数を決定する誤り位置検出多項式計算装置に関する。
【０００２】
【従来の技術】
データの伝送、格納または取出しの過程の際発生する雑音は、対応する各過程でエラーをもたらし得る。従って、そのようなエラーまたは誤りを訂正するために、多様な符号化方法が提案されてきた。
【０００３】
そのような符号化方法においては、１組のチェックビットが１群のメッセージビットや情報ビットに付加されて符号語を形成する。このチェックビットは、エンコーダにより定められ、誤りの検出及び訂正に用いられる。ここで、エンコーダは基本的にメッセージビットを含むビットを２進メッセージ多項式の係数として取り扱うと共に、メッセージ多項式ｉ（Ｘ）と符号発生多項式ｇ（Ｘ）との間の乗算または除算を通じてチェックビットを求めることによって、符号語多項式ｃ（Ｘ）を求める。符号語発生多項式ｇ（Ｘ）は符号語に所望の特性を付加して、符号語が誤り訂正２進群コードの特定のクラスには属するようにする（例えば、Ｓ．Ｌｉｎらの論文“Error Comtrol Coding: Fundamentals and Applications」, Prentice-Hall,1983”参照）。
【０００４】
誤り訂正コードの１つのクラスとして、ＢＣＨ（Bose-Chaughuri-Hocquenghen）コードクラスが周知となっており、このＢＣＨコードはリードソロモンコード（以下、「ＲＳコード」と称す）を備える。このＲＳコードの数学的基板は、例えば、Ｌｉｎらによる上記論文及びＢｅｒｌｅｋａｍｐに許与された米国特許第４，１６２，４８０号明細書に開示されている。
【０００５】
ＲＳコードの符号発生多項式ｇ（Ｘ）の根がαの連続した２ｔ個のべき乗（ｔは正整数）であるならば、αを有限体ＧＦ（２^m）の基本要素とし、ｆ（１）・（ｆ２）・．．．・ｆ（ｎ）＝П［ｋ＝ｌ，ｎ］ｆ（ｋ）と表すものとすると、下記式（１）のようにしてｔ個の誤りを訂正し得る。
【０００６】
【数１】
ｇ（Ｘ）＝П［ｉ＝１，２ｔ］（Ｘ−αⁱ） 式（１）
【０００７】
伝送符号語を受け取るかまたは格納符号語を取り出す際に付随する雑音は符号語の誤りパターンに表され得る。ＲＳコードから発生した誤りパターンを取り扱うためには一般に４段階の過程が用いられる。この誤り訂正過程を説明するために、１つのＲＳコードが、Ｎ個のＭビットシンボルよりなるを有する符号語を備えるものと仮定する。ここで、Ｎ及びＭは正の整数であり、Ｋ個のシンボルは情報シンボルを、（Ｎ−Ｋ）個のシンボルはチェックシンボルを表し、ＫはＮより小さい正の整数である。この場合、符号語多項式ｃ（Ｘ）は（Ｎ−１）次多項式であり、２ｔは（Ｎ−Ｋ）と等しい。
【０００８】
第１の誤り訂正段階では、シンドロームＳ₀，Ｓ₁，．．．Ｓ_2t-1が受信符号語を表す（Ｎ−１）次の受信符号語多項式ｒ（Ｘ）を用いて求められる。この受信符号語多項式ｒ（Ｘ） は、ｒ_N-1Ｘ^N-1＋ｒ_N-2Ｘ^N-2＋．．．＋ｒ_iＸⁱ＋ｒ₀として表現され、ｒ_jは、符号語の（Ｎ−ｊ）番目の受信シンボルを表す。ｊは１〜Ｎの正の整数である。
【０００９】
第２段階においては、上記のシンドロームを用いて誤り位置検出多項式σ（Ｘ）の係数が求められる。第３段階においては、誤り位置検出多項式σ（Ｘ）の根を求めるられ、その根は受信符号語における誤りの位置を表す。詳述すれば、基本要素の乗数α^-jを誤り位置検出多項式σ（Ｘ）の変数Ｘに代入すると該式は０になる。つまり、α^-jが誤り位置検出多項式σ（Ｘ）の根となる。これは、ｒ_j（即ち、符号語の（Ｎ−ｊ）番目のシンボル）に誤りが発生したことを意味する。
【００１０】
最後に、第４段階においては、誤り値が誤り位置とシンドロームとを用いて計算される。シンドロームと誤り位置検出多項式の係数に対する数学的表現は、前述したＢｅｒｌｅｋａｍｐによる米国特許出願第４，１６２，４８０号に記載されている。
【００１１】
第4段階の詳細は、以下のようなものである。
【００１２】
まず、誤り評価多項式Ω（ｘ）が以下の式（２）のように求められる。
【００１３】
【数２】
Ω（ｘ）＝σ（Ｘ）ｓ（ｘ） 式（２）
【００１４】
ここで、σ（Ｘ）は誤り位置検出多項式であり、（ｘ）はシンドロームをその係数とするシンドローム多項式である。
【００１５】
【数３】
ｅ_j＝α^j・Ω（α^-j）／σ′（α^-j） 式（３）
【００１６】
ここで、σ′（Ｘ）は誤り位置検出多項式σ（Ｘ）の一次導関数、α^-jは第３段階で求めた誤り位置検出多項式σ（Ｘ）の根であり、誤り値ｅ_jは第３段階で、シンボルを有する誤りとして定められる（Ｎ−ｊ）番目のシンボルに対応する。
【００１７】
誤り値を決定した後、下記式のようにその誤り値を該当シンボルに加えて、元の符号語を復元し得る。
【００１８】
【数４】

【００１９】
ここで、ｃ′（Ｘ）は誤り訂正符号語多項式である。
【００２０】
リードソロモン（ＲＳ）符号化語に用いられる誤り位置検出多項式計算装置の動作を説明するため、Ｂｅｒｌｅｋａｍｐ循環アルゴリズム（ＲＢＡ）を下記に紹介する。
【００２１】
ＲＢＡとは、誤り位置検出多項式σ（Ｘ）を計算するアルゴリズムである。ｔ個の誤り訂正能力を有するＲＳコードがｔ個の根を有するため、誤り位置検出多項式σ（Ｘ）は下記式のようにｔ次の多項式から構成される。
【００２２】
【数５】

【００２３】
誤り位置検出多項式σ（Ｘ）は、下記の４つの段階からなるＲＢＡを用いて計算する。
【００２４】
第１段階として、初期化を行う。
【００２５】
σ０（Ｘ）＝１、Ｂ₀（Ｘ）＝１、ｋ₀＝０、Ｌ₀＝０、ｂ₀＝１なる初期値を設定する。即ち、誤り位置検出多項式の初期値σ（Ｘ）は「１」、中間値の初期値Ｂ₀は「１」、誤り位置検出多項式の実際の次数の初期値Ｌ₀は「０」、Ｘ次関数の初期値ｋ₀は「０」、遅延ディスクレパンシの初期値ｂ₀は「１」である。
【００２６】
誤り位置検出多項式σ（Ｘ）の次数がｔであるため、定数項「１」を含んで誤り位置検出多項式の係数を格納するには、全てｔ＋１個のレジスタが必要である。誤り位置検出多項式の実際次数Ｌ_Nは必要な場合のみに１ずつ増加する。各値Ｂ_N（Ｘ）、ｋ_N、ｂ_Nは誤り位置検出多項式σ（Ｘ）を更新するのに用いられる値を表す。
【００２７】
第２段階として、ディスクレパンシ（discrepancy）の計算を行う。
【００２８】
ディスクレパンシの初期値はシンドロームＳ₀と等しく、他のディスクレパンシは、ｆ（１）＋ｆ（２）＋．．．＋ｆ（ｎ）＝Σ［ｋ＝１，ｎ］ｆ（ｎ）と表すものとすると、下記式のように計算される。
【００２９】
【数６】
Ｓ_N＋Σ［ｉ＝１，Ｌ］σｉ・Ｓ_N-1（Ｎ≧１） 式（６）
【００３０】
ここで、Ｄ_Nはディスクレパンシ、σ_iはσ（Ｘ）の係数、Ｓ_N，Ｓ_N-1はシンドローム、Ｎは反復回数を表す０〜１５の正の整数である。
【００３１】
第３段階として、ディスクレパンシの更新を行う。ディスクレパンシは以下のように更新される。
【００３２】
ケース（１）、即ちＤ_Ｎ＝０の場合、
Ｋ_Ｎ＋１＝Ｋ_Ｎ＋１、
と更新され、
ケース（２）、即ちＤ_Ｎ≠０，２Ｌ_Ｎ≦Ｎの場合、
σ_Ｎ＋１（Ｘ）＝σ_Ｎ（Ｘ）−Ｄ_Ｎ、ｂ_Ｎ ^−１ ・Ｘ^ｋ ・Ｂ_Ｎ（Ｘ）
Ｌ_Ｎ＋１＝Ｎ＋１−Ｌ_Ｎ
Ｋ_Ｎ＋１＝１
Ｂ_Ｎ＋１（Ｘ）＝σ_Ｎ（Ｘ）
ｂ_Ｎ＋１＝Ｄ_Ｎ
と更新され、
ケース（３）、即ちＤ_Ｎ≠０、２Ｌ_Ｎ＞Ｎの場合、
σ_Ｎ＋１（Ｘ）＝σ_Ｎ（Ｘ）−Ｄ_Ｎ、ｂ_Ｎ ^−１ ・Ｘ^ｋ、Ｂ_Ｎ（Ｘ）
Ｋ_Ｎ＋１＝Ｋ_Ｎ＋１
と更新される。
【００３３】
第４段階として、第２段階を実行する。即ち、Ｎが２ｔ−１となるまで第２段階を反復して行う。
【００３４】
図１には、誤り位置検出多項式σ（Ｘ）の係数を決定する、従来の誤り位置検出多項式計算装置１００のブロック図が示されている。
【００３５】
従来の誤り位置検出多項式計算装置１００は、ｔ個の計算セル１０−１〜１０−ｔ、ディスクレパンシ及び逆遅延ディスクレパンシ（Ｄ及びｂ^-1）計算部１８を備える。ここで、遅延ディスクレパンシは遅延されたディスクレパンシを、逆遅延ディスクレパンシは遅延されたディスクレパンシの逆を各々表す。各計算セル１０−ｉ（ｉは１〜ｔ）は３つのレジスタ（即ち、第１レジスタ（ＦＲｉ）１１−ｉ、第２レジスタ（ＳＲｉ）１４−ｉ、第３レジスタ（ＴＲｉ）１７−ｉ）と、この２つのガロア体（ＧＦ）乗算器１２−ｉ及び１６−ｉと、１つのＧＦ加算器１３−ｉと、マルチプレクサ（ＭＵＸ）とから構成される。
【００３６】
第１の計算セル１０−１においてＦＲ＿Ｎは制御部（図示せず）から入力される。この制御部はディスクレパンシＤ値及び反復回数Ｎに応じて「０」または「１」を供給する。また、第１の計算セル１０−１で、ＴＲ１は外部シフトレジスタ（図示せず）に接続されており、このシフトレジスタにはシンドロームＳ_j（ｊは０〜２ｔ−１） が格納されている。
【００３７】
レジスタシフトクロツクＳＨＩＦＴ＿ＣＬＫの立ち上がりエッジにてＳ₀から始める外部シンドロームに新たなシンドロームシンボルが入力される。同時に、各ＴＲｉの内容は１つのシンドローム位置ずつ右側にシフトされ、外部のシフトレジスタの内容は第１計算セル１０−１のＴＲ１にシフトされる。
【００３８】
各計算セル１０−ｉのＳＲＩ及びＴＲｉの各内容はセル単位で乗ぜられ、その乗算結果をＤ及びｂ^-1計算部において加算してＤを発生する。計算されたＤはＤ及びｂ^-1計算部１８にてｂ^-1と乗じられる。ここで、ｂはＤを遅らせたディスクレパンシであり、ｂ^-1はｂの逆数である。
【００３９】
その後、乗算結果Ｄ、ｂ^-1は、各計算セル１０−ｉのＦＲｉの内容と乗じられ、その結果は各計算セル１０−ｉのＳＲｉの内容と加えられて、ＳＲｉにフィードバックされる。シンボルクロックＳＹＭ＿ＣＬＫの立ち上がりエッジでは、ＦＲｉ及びＳＲｉに新たな内容が入力されると共に、ＳＨＩＦＴ＿ＣＬＫも新たなシンドロームを入力する。
【００４０】
Ｄ_N＝０である場合、Ｄ、ｂ^-1も同様に０になる。よって、各計算セル１０−ｉのＳＲｉの内容は、ＳＹＭ＿ＣＬＫによって変化しない。各計算セル１０−ｉのＭＵＸ１５−ｉは、選択信号ＳＥＬによってＦＲｉの出力を選択する。従って、ＳＹＭ＿ＣＬＫの立ち上がりエッジにおいて、各計算セル１０−ｉの各ＦＲｉの内容は１つのシンボル位置だけ右側にシフトされ、第１の計算セル１０−１のＦＲｉには「０」が入力される。
【００４１】
ＤＮ≠０であり、２Ｌ_N≦Ｎである場合、ＳＹＭ＿ＣＬＫの立ち上がりエッジにてＧＦ加算器１３−ｉの結果はＳＲｉに入力される。ＭＵＸ１５−ｉは選択信号ＳＥＬに応じてＳＲｉの出力を選択する。結果として、ＳＹＭ＿ＣＬＫの立ち上がりエッジにて１つのシンボル位置だけ右側にシフトされたＳＲｉの内容がＦＲｉに入力されると共に、第１の計算セル１０−１のＦＲ１には「１」が入力される。
【００４２】
ＤＮ≠０であり、２Ｌ_N＞Ｎである場合、ＳＹＭ＿ＣＬＫの立ち上がりエッジにてＧＦ加算器１３−ｉの出力がＳＲｉに入力される。ＦＲｉの内容はＤＮ≠０である場合と同様に決定される。
【００４３】
Ｄ及びｂ^-1計算部１８は、各計算セル１０−ｉの第２ＧＦ加算器１６−ｉの各出力を全て逆遅延ディスクレパンシｂ^-1計算する。その後、加えてディスクレパンシＤを計算する。また、Ｄを遅らせて遅延ディスクレパンシｂを発生し、Ｄとｂ^-1とを通じて第１ＧＦ乗算器１２−ｉに出力する。
【００４４】
この動作はＮが２ｔになるまで反復する。動作が終了された後、ＳＲｉの内容が誤り位置検出多項式σ（Ｘ）の係数となる。
【００４５】
上述した従来の誤り位置検出多項式計算装置１００によれば、各計算セル１０−１〜１０−ｔが２つのＧＦ乗算器及び１つのＧＦ加算器を要するため、装置の構造がより複雑になり、よってＶＬＳＩ技術を用いてこれを具現し難いという不都合がある。
【００４６】
【発明が解決しようとする課題】
従って本発明の主な目的は、ベーレカムプ循環アルゴリズムを用いて組み込まれるべきＧＦ乗算器及びＧＦ加算器の数を減らした、リードソロモン復号化器に用いられ誤り位置検出多項式を計算する高効率性の誤り位置検出多項式計算装置を提供することにある。
【００４７】
【課題を解決するための手段】
上記の目的を達成するために、本発明によれば、リードソロモン復号化器に用いられ、ベーレカムプ循環アルゴリズム（recursive Berlekamp algorithm）を用いてｔ次の多項式（ｔは予め定められた正整数）である誤り位置検出多項式σ（Ｘ）を計算する誤り位置検出多項式計算装置であって、
状態がどのケースであるかを判断して遅延ディスクレパンシ（discrepancy）、反復の回数、誤り位置検出多項式σ（Ｘ）の実際の次数を含む各変数を更新し、制御信号ＣＡＳＥ３＿ＦＬＡＧ及び遅延ディスクレパンシを発生する変数発生部と、
前記変数発生部からの遅延ディスクレパンシの逆数を発生する逆ルックアップテーブルと、
シンドローム及び更新済みのエラー位置多項式を用いてディスクレパンシを計算し、制御信号Ｄ−ＺＥＲＯを発生し、更新済みの誤り位置検出多項式を遅延出力し、最後に更新済みの誤り位置検出多項式を完全誤り位置検出多項式として出力するディスクレパンシ計算部と、
前記ディスクレパンシ計算部からの前記ディスクレパンシと前記逆ルックアップテーブルからの逆遅延ディスクレパンシとを乗じる第１ガロア体（ＧＦ）乗算器と、
定数、または前記ディスクレパンシ計算部からの前記更新済みの誤り位置検出多項式またはフィードバック値を選択的に出力する選択部と、
前記選択部からの出力をシフトさせ、該シフト値を出力し、該シフト値を前記選択部へフィードバックさせる第１シフトレジスタ部と、
前記第１ＧＦ乗算器からの出力と前記第１シフトレジスタ部からの出力とを乗じる第２ＧＦ乗算器と、
前記第２ＧＦ乗算器からの出力と前記ディスクレパンシ計算部からの更新済みの誤り位置検出多項式とを加えて、その結果を前記ディスクレパンシ計算部へフィードバックさせる第１ＧＦ加算器と、
制御信号を前記第１ＧＦ加算器、前記第１シフトレジスタ部及び前記ディスクレパンシ計算部に供給する第１信号発生部とを含むことを特徴とする誤り位置検出多項式計算装置が提供される。
【００４８】
【発明の実施の形態】
以下、本発明の好適実施例について図面を参照しながらより詳しく説明する。図２には、本発明による誤り位置検出多項式計算装置２００のブロック図が示されている。ｔ個の係数を決定し得る誤り位置検出多項式計算装置２００は、従来の誤り位置検出多項式計算装置１００とは異なり、ｔ個の計算セルからなっていない。図２、３、４及び５における実施例では便宜上ｔを８と仮定する。
【００４９】
誤り位置検出多項式計算装置２００は、遅延ディスクレパンシｂ_N、反転回数Ｎ、誤り位置検出多項式の実際次数などの各変数を更新し、制御信号ＣＡＳＥ３＿ＦＬＡＧ及び遅延ディスクレパンシｂ_Nを出力する変数発生部２１０と、レジスタディスクレパンシの逆数ｂ_N ^-1を求する逆ルックアップテーブル２２０と、ディスクレパンシＤを計算し、制御信号Ｄ＿ＺＥＲＯを出力し、更新された誤り位置検出多項式σ＿ＩＮを遅延させ、最後に更新済みの誤り位置検出多項式σ＿ＯＵＴを完全誤り多項式として出力するディスクレパンシ計算部２３０と、ディスクレパンシ計算部からの逆遅延ディスクレパンシｂ_N ^-1とＤ_Nとを乗じる第１ＧＦ乗算器２４０と、定数、またはディスクレパンシ計算部２３０からの更新済みの誤り位置検出多項式σ＿ＯＵＴまたはフィードバック値を選択的に出力する選択部２５０と、８個のレジスタが直列に接続されている第１シフトレジスタ部２６０と、第１ＧＦ乗算器２４０からの出力と第１シフトレジスタ部２６０からの出力とを乗じる第２ＧＦ乗算器２７０と、第２ＧＦ乗算器２７０からの出力と更新済みの誤り位置検出多項式σ＿ＯＵＴとを加える第１ＧＦ加算器２８０と、制御信号を選択部２５０、第１シフトレジスタ部２６０及びディスクレパンシ計算部２３０へ出力する第１信号発生部２９０とを含む。
【００５０】
また.図３によれば、ディスクレパンシ計算部２３０は９個のレジスタが直列に接続され、第１ＧＦ加算器２８０から出力されたσ＿ＩＮをシフトさせ、最後に更新済みの誤り位置検出多項式σ＿ＯＵＴを完全誤り位置検出多項式として出力する第２シフトレジスタ部２３１と、第１ＧＦ加算器２８０からの出力または第２シフトレジスタ部２３１からの出力を選択的に出力する第３ＭＵＸ２３２と、第３ＭＵＸ２３２からの出力とシンドロームとを乗じる第３ＧＦ乗算器２３３と、第３ＧＦ乗算器２３３からの出力とフィードバック値とを加える第２ＧＦ加算器２３４と、第２ＧＦ加算器２３４からの出力をビットクロックＢＩＴ＿ＣＬＫによってラッチして、これを第２ＧＦ加算器２３４にフィードバックさせるフイードバックレジスタ２３５と、第２ＧＦ加算器２３４からの出力をラッチして、これをディスクレパンシＤ_Nとして出力する出力レジスタ２３６と、ディスクレパンシが「０」である場合、ハイレベルのＤ＿ＺＥＲＯを出力するディスクレパンシ確認部２３７と、各制御信号を第２シフトレジスタ部２３１及び出力レジスタ２３６に出力する第２信号発生部２３８と係数選択部２３９とを含む。
【００５１】
図２に示した誤り位置検出多項式計算装置２００の動作を以下に詳しく説明する。
【００５２】
０番目の反復を始める前に、図４に示した第１シフトレジスタ部２８０におけるレジスタＸＢ₀〜ＸＢ₇が中間値の初期値に初期化される。即ち、ＸＢ₀は「１」に、ＸＢ₁〜ＸＢ₇は「0」に各々初期化される。また、図５に示した第２シフトレジスタ部２３１におけるレジスタσ₀〜σ₈が誤り位置検出多項式の初期値として初期化される。即ち、σ₀は「１」に、σ₁〜σ₈は「０」に各々初期化される。
【００５３】
図３を再び参照すれば、各シンドロームは、下記表１に表れている順次のとおりディスクレパンシ計算部２３０に順に入力されてＤ_Nを計算するのに用いられる、各反復は９個のＢＩＴ＿ＣＬＫからなっており、全ての動作はＢＩＴ＿ＣＬＫによって行われる。
【００５４】
【表１】

【００５５】
制御信号Ｄ０＿ＦＬＡＧは、０番目の反復の間ハイレベルになって、第３ＭＵＸ２３２に第２シフトレジスタ部２３１からの出力を選択させて第３ＧＦ乗算器２３３に出力させるように作用する。Ｄ０＿ＦＬＡＧは、０番目を除いた残りの反復の間ローレベルになって、第３ＭＵＸ２３２に第１ＧＦ加算器２８０からの更新済みの誤り位置検出多項式を選択させるように作用する。
【００５６】
第３ＧＦ乗算器２３３において、シンドロームは第３ＭＵＸ２３２からの出力と乗じられ、乗算結果は第２ＧＦ加算器２３４に入力される。
【００５７】
第２ＧＦ加算器２３４においては、第３ＧＦ乗算器２３３からの出力はフィードバックレジスタ２３５からの出力と加える。その加算結果はフィードバックレジスタ２３５及び出力レジスタ２３６へ各々入力される。
【００５８】
フィードバックレジスタ２３５は、第２ＧＦ加算器２３４からの出力をＢＩＴ＿ＣＬＫによってラッチし、これを第２ＧＦ加算器２３４にフィードバックさせる。
【００５９】
制御信号Ｄ＿ＥＮＤは各反復のＢＩＴ＿ＣＬＫにおいてハイレベルとなって出力レジスタ２３６をイネーブル状態にさせる。出力レジスタ２３６は第２ＧＦ加算器２３４からの出力をラッチし、Ｄ＿ＥＮＤによってこれをディスクレパンシＤ_Nとして第１ＧＦ乗算器２４０に出力する。ディスクレパンシ確認部２３７は出力レジスタ２３６からの出力されたディスクレパンシＤ_Nを調べる。もし、Ｄ_Nが「０」である場合、ディスクレパンシ確認部２３７はＤ＿ＺＥＲＯをハイレベルにして変数発生部２１０及び第１信号発生部２９０に出力する。
【００６０】
図２を参照すれば、ディスクレパンシＤ_Nはディスクレパンシ計算部２３０から第１ＧＦ乗算器２４０に出力される。第１信号発生部２９０の第１ＯＲゲート２９２はＣＡＳＥ３＿ＦＬＡＧとＤ０＿ＦＬＡＧとを論理和の計算をして選択信号ＳＥＬ１を出力する。第２ＯＲゲート２９４は第１ＯＲゲート２９２からのＳＥＬ１とＤ＿ＺＥＲＯとを論理和の計算をして選択信号ＳＥＬ２を出力する。
【００６１】
選択部２５０内において、第１ＭＵＸ２５４は第１信号発生部２９０における第２ＯＲゲート２９４からのＳＥＬ２がハイレベルである場合、ＲＯＭ２５２から入力ポート１に入力された定数を選択し、ＳＥＬ２がローレベルである場合、ディスクレパンシ計算部２３０から入力ポート０に入力されたσ＿ＯＵＴを選択する。第２ＭＵＸ２５６は第１信号発生部２９０における第１ＯＲゲート２９２からのＳＥＬ１がローレベルである場合、第１ＭＵＸ２５４から入力ポート０に入力される値を選択し、ＳＥＬ１がハイレベルである場合、第１シフトレジスタ部２６０から入力ポート１にフィードバック値を選択する。
【００６２】
第１シフトレジスタ部２６０は、第２ＭＵＸ２５６からの出力をＢＩＴ＿ＣＬＫによってシフトさせ、これを第２ＭＵＸ２５６にフィードバックさせると共に、第２ＧＦ乗算器２７０に出力する。
【００６３】
一方、変数発生部２１０はディスクレパンシＤ_N、反復回数Ｎ及び誤り位置検出多項式の実際次数Ｌ_Nを用いて、どのケースに該当するかを決定する。そのように決定されたケースによって、Ｄ_N、Ｎ、Ｌ_Nが更新され、ＣＡＳＥ３＿ＦＬＡＧ及び遅延ディスクレパンシｂ_Nが出力される。
【００６４】
ディスクレパンシＤ_Nが「０」である場合には、ケース１に該当し、よって、ＣＡＳＥ３＿ＦＬＡＧはローレベルであり、Ｄ＿ＺＥＲＯはハイレベルである。ディスクレパンシＤ_Nが「０」でなく２Ｌ_NがＮ以下である場合は、ケース２に該当し、ＣＡＳＥ３＿ＦＬＡＧはローレベルとなり、Ｄ＿ＺＥＲＯはローレベルとなる。ディスクレパンシＤ_Nが「０」でなく、２Ｌ_NがＮより大きい場合は、ケース３に該当し、ＣＡＳＥ３＿ＦＬＡＧはハイレベルとなり、Ｄ＿ＺＥＲＯはローレベルとなる。
【００６５】
逆ルックアップテーブル２２０は遅延ディスクレパンシの逆数ｂ_N ^-1を計算して、これを第１ＧＦ乗算器２４０に出力する。第１ＧＦ乗算器２４０にてディスクレパンシＤ_Nは逆遅延ディスクレパンシｂ_N ^-1と乗じられる。
【００６６】
第２ＧＦ乗算器２７０は、第１ＧＦ乗算器２４０からの出力と第１シフトレジスタ部２６０からの出力とを乗じて第１ＧＦ加算器２８０に出力する。
【００６７】
第１ＧＦ加算器２８０においては、第２ＧＦ乗算器２７０からの出力と第２シフトレジスタ部２３１からの出力（即ち、更新済みの誤り位置検出多項式σ＿ＯＵＴ）とが加算される。その後、その結果はディスクレパンシ計算部２３０にフィードバックされる。
【００６８】
以下、Ｂｅｒｌｅｋａｍｐ循環アルゴリズムと比較して本発明の実施例を説明する。
【００６９】
ケース１において、ＣＡＳＥ３＿ＦＬＡＧはローレベル、Ｄ０＿ＦＬＡＧはローレベル、Ｄ＿ＺＥＲＯはハイレベルである。ＳＥＬ２はハイレベル、ＳＥＬ１はローレベルであり、ここでは第１ＭＵＸ２５４が入力ポート１の定数を、第２ＭＵＸ２５６が入力ポート０の定数を各々選択するようにする役割を果たしている。定数「０」が第１シフトレジスタ部２６０に入力される、即ち、ＸＢｉの内容は右側にシフトされ、ＸＢ０の内容は「０」になる。
【００７０】
ケース２においては、ＣＡＳＥ３＿ＦＬＡＧはローレベル、Ｄ０＿ＦＬＡＧはローレベル、Ｄ＿ＺＥＲＯはローレベルである。ＳＥＬ２はローレベル、ＳＥＬ１はハイレベルであり、ここでは第１ＭＵＸ２５４が入力ポート０のσ＿ＯＵＴを、第２ＭＵＸ２５６が入力ポート０のσ＿ＯＵＴを各々選択するようにしている。従って、σ＿ＯＵＴが第１シフトレジスタ部２６０に入力され、σ（Ｘ）、ＸＢ（Ｘ）、Ｌ_N、ｂ_Nが全て更新される。
【００７１】
ケース３においては、ＣＡＳＥ３＿ＦＬＡＧはハイレベル、Ｄ０＿ＦＬＡＧはローレベル、Ｄ＿ＺＥＲＯはローレベルである。ＳＥＬ２はハイレベル、ＳＥＬ１はハイレベルであり、ここでは第１ＭＵＸ２５４が入力ポート１の定数を、第２ＭＵＸ２５６が入力ポート１のフィードバック値を各々選択するようにする役目を果たしている。結果として、フィードバック値が更に第１シフトレジスタ部２６０に入力され、ＸＢｉの内容は右側にシフトされＸＢ７の内容はＸＢ０に入力される。
【００７２】
第１信号発生部２９０内においては、第１インバータ２９６は符号語終了信号ＣＷ＿ＥＮＤを反転させ、第１ＡＮＤゲートに入力する。また、リセット信号ＲＳＴも第１ＡＮＤゲートに入力される。第１ＡＮＤゲートからの出力ＲＳＴ１は第１シフトレジスタ部２６０及び第２シフトレジスタ部２３１にリセット信号として入力される。
【００７３】
第１シフトレジスタ部２６０及び第２シフトレジスタ部２３１における各レジスタは、ＣＷ＿ＥＮＤがハイレベルであるか、またはＲＳＴがローレベルであればリセットされる。つまり、符号語が終了しさえすれば、ＲＳＴ値に係わらずリセットされ、または、リセット信号が受取られるとＣＷ＿ＥＮＤ値に係わらずリセットされる。
【００７４】
第２信号発生部２３８内において、第２インバータ２３８−１はディスクレパンシ終了信号Ｄ＿ＥＮＤを反転させ第２ＡＮＤゲート２３８−２に出力する。また、ＲＳＴも第２ＡＮＤゲート２３８−２及び出力レジスタ２３６に入力される。第２ＡＮＤゲート２３８−２の出力はフィードバックレジスタ２３５に入力される。
【００７５】
ＲＳＴがローレベルであるかまたはＤ＿ＥＮＤがハイレベルである場合、フィードバックレジスタ２３５はリセットされ、ＲＳＴがローレベルである場合、出力レジスタ２３６がリセットされる。詳述すると、フィードバックレジスタ２３５は各反復が終了するとＲＳＴ値に関係なくリセットされ、またはリセット信号を受信するとＤ＿ＥＮＤ値に関係なくリセットされる。そして、出力レジスタ２３６はリセット信号を受信するとリセットされる。
【００７６】
表２乃至表７には、各ケースによる第１シフトレジスタ部２６０及び第２シフトレジスタ部２３１の内容が表されている。
【００７７】
【表２】

【００７８】
【表３】

【００７９】
【表４】

【００８０】
【表５】

【００８１】
【表６】

【００８２】
【表７】

【００８３】
このような方法によって、誤り位置検出多項式計算装置２００は、Ｎが１５になるまで、動作を行い、完全誤り位置検出多項式σ（Ｘ）を出力する。
【００８４】
便宜上、図２の変数発生部２１０、逆ルックアップテーブル２２０及び図３の係数選択部２３９に対する詳細は省略する。変数発生部２１０及び逆ルックアップテーブル２２０の役割は前述のとおりである。そして、係数選択部２３９の役割は制御信号σ＿ＣＯＥＦ＿ＳＥＬによって係数を選択して、誤り位置検出多項式Ω（Ｘ）を計算するΩ計算部（図示せず）に出力する。当業者において、変数発生部２１０、逆ルックアップテーブル２２０及び係数選択部２３９の詳細構造及び機能は周知のことであるので省略する。
【００８５】
本発明の装置では、所定数の誤り、例えば、８個が用いられているが、その他の数の誤りが誤り位置検出多項式σ（Ｘ）の係数を計算するのに用いられ得ることは勿論である。
【００８６】
上記において、本発明の好適な実施の形態について説明したが、本発明の請求範囲を逸脱することなく、当業者は種々の改変をなし得るであろう。
【００８７】
【発明の効果】
従って、本発明によれば、従来の装置とは異なり組み込まれるべきＧＦ乗算器及び加算器の個数を減らすことによって、低コストでサイズが小さく、より一層効果的な誤り位置検出多項式計算装置を具現することができる。
【図面の簡単な説明】
【図１】従来の誤り位置検出多項式計算装置を示したブロック図である。
【図２】本発明の好適実施例によって、Ｂｅｒｌｅｋａｍｐ循環アルゴリズムを用いて、誤り位置検出多項式計算装置を示したブロック図である。
【図３】図２のディスクレパンシ計算部の詳細なブロック図である。
【図４】図２の第１シフトレジスタ部の詳細なブロック図である。
【図５】図３の第２シフトレジスタ部の詳細なブロック図である。
【符号の説明】
１７ Ｄ及びｂ^-1計算部
１００ 従来の誤り位置検出多項式計算装置
２００ 本発明の誤り位置検出多項式計算装置
２１０ 変数発生部
２２０ 逆ルックアップテーブル
２３０ ディスクレパンシ計算部
２３１ 第２シフトレジスタ部
２３２ 第３ＭＵＸ
２３３ 第３ＧＦ乗算器
２３４ 第２ＧＦ加算器
２３５ フィードバックレジスタ
２３６ 出力レジスタ
２３７ ディスクレパンシ確認部
２３８ 第２信号発生部
２３８−１ 第２インバータ
２３９ 係数選択部
２４０ 第１ＧＦ乗算器
２５０ 選択部
２５２ ＲＯＭ
２５４ 第１ＭＵＸ
２５６ 第２ＭＵＸ
２６０ 第１シフトレジスタ部
２７０ 第２ＧＦ乗算器
２８０ 第１ＧＦ加算器
２９０ 第１信号発生部
２９２ 第１ＯＲゲート
２９４ 第２ＯＲゲート
２９６ 第１インバータ

Claims (7)

1. リードソロモン復号化器に用いられ、ベーレカムプ循環アルゴリズム（recursive Berlekamp algorithm）を用いてｔ次の多項式（ｔは予め定められた正整数）である誤り位置検出多項式σ（Ｘ）を計算する誤り位置検出多項式計算装置であって、
   前記ベーレカムプ循環アルゴリズムは、以下の４段階、即ち
   （１）誤り位置検出多項式の初期値σ _０ （Ｘ）、中間値の初期値Ｂ _０ （Ｘ）、誤り位置検出多項式の実際の次数の初期値Ｌ _０ （Ｘ）、及び遅延ディスクレパンシｂ _０ の初期化を行う段階と、
   （２）Ｄ _Ｎ をディスクレパンシ、σｉをσ（Ｘ）の係数、Ｓ _Ｎ をＳ _Ｎ−１ のシンドロームとし、σｉ・Ｓ _Ｎ−１ の整数ｉを１から１ずつ増加させてｉ＝Ｌになるまでの総和をΣ［ｉ＝１，Ｌ］σｉ・Ｓ _Ｎ−１ と表すものとしたとき、式
   Ｄ _Ｎ ＝Ｓ _Ｎ ＋Σ［ｉ＝１，Ｌ］σｉ・Ｓ _Ｎ−１ （Ｎ≧１）
   を用いてディスクレパンシの計算を行う段階と、
   （３）下記の３つのケースによってディスクレパンシを更新する段階であって、
   ケース１、即ちＤ _Ｎ ＝０の場合、
   Ｋ _Ｎ＋１ ＝Ｋ _Ｎ ＋１、
   と更新され、
   ケース２、即ちＤ _Ｎ ≠０，２Ｌ _Ｎ ≦Ｎの場合、
   σ _Ｎ＋１ （Ｘ）＝σ _Ｎ （Ｘ）−Ｄ _Ｎ ・ｂ _Ｎ ^−１ ・Ｘ ^ｋ ・Ｂ _Ｎ （Ｘ）、
   Ｌ _Ｎ＋１ ＝Ｎ＋１−Ｌ _Ｎ 、
   Ｋ _Ｎ＋１ ＝１、
   Ｂ _Ｎ＋１ （Ｘ）＝σ _Ｎ （Ｘ）、
   ｂ _Ｎ＋１ ＝Ｄ _Ｎ
   と更新され、
   ケース３、即ちＤ _Ｎ ≠０、２Ｌ _Ｎ ＞Ｎの場合、
   σ _Ｎ＋１ （Ｘ）＝σ _Ｎ （Ｘ）−Ｄ _Ｎ ・ｂ _Ｎ ^−１ ・Ｘ ^ｋ ・Ｂ _Ｎ （Ｘ）、
   Ｋ _Ｎ＋１ ＝Ｋ _Ｎ ＋１
   と更新される、該段階と、
   （４）Ｎが２ｔ−１となるまで段階（２）を反復する段階からなることを特徴とし、
   前記誤り位置検出多項式計算装置は、
   状態が前記ケース１乃至ケース３の何れであるかを判断して遅延ディスクレパンシ（discrepancy）、反復の回数、誤り位置検出多項式σ（Ｘ）の実際の次数を含む各変数を更新し、制御信号ＣＡＳＥ３−ＦＬＡＧ及び遅延ディスクレパンシを発生する変数発生部と、
   前記変数発生部からの遅延ディスクレパンシの逆数を発生する逆ルックアップテーブルと、
   シンドローム及び更新済みのエラー位置多項式を用いてディスクレパンシを計算し、制御信号Ｄ−ＺＥＲＯを発生し、更新済みの誤り位置検出多項式を遅延出力し、最後に更新済みの誤り位置検出多項式を完全誤り位置検出多項式として出力するディスクレパンシ計算部と、
   前記ディスクレパンシ計算部からの前記ディスクレパンシと前記逆ルックアップテーブルからの逆遅延ディスクレパンシとを乗じる第１ガロア体（ＧＦ）乗算器と、
   定数、または前記ディスクレパンシ計算部からの前記更新済みの誤り位置検出多項式またはフィードバック値を選択的に出力する選択部と、
   前記選択部からの出力をシフトさせ、該シフト値を出力し、該シフト値を前記選択部へフィードバックさせる第１シフトレジスタ部と、
   前記第１ＧＦ乗算器からの出力と前記第１シフトレジスタ部からの出力とを乗じる第２ＧＦ乗算器と、
   前記第２ＧＦ乗算器からの出力と前記ディスクレパンシ計算部からの更新済みの誤り位置検出多項式とを加えて、その結果を前記ディスクレパンシ計算部へフィードバックさせる第１ＧＦ加算器と、
   制御信号を前記第１ＧＦ加算器、前記第１シフトレジスタ部及び前記ディスクレパンシ計算部に供給する第１信号発生部とを含むことを特徴とし、
   誤り位置検出多項式の更新は前記逆ルックアップテーブル、前記第１ＧＦ乗算器、前記第１シフトレジスタ部、前記第１ＧＦ加算器により行われ、状態が前記ケース１乃至ケース３の何れであるかは、制御信号である前記ＣＡＳＥ３−ＦＬＡＧ及び前記Ｄ−ＺＥＲＯの組合せによって示され、ケース１の場合は、ＣＡＳＥ３−ＦＬＡＧがローレベルでＤ−ＺＥＲＯはハイレベルとなり、ケース２の場合は、ＣＡＳＥ３−ＦＬＡＧがローレベルとＤ−ＺＥＲＯがローレベルとなり、ケース３の場合は、ＣＡＳＥ３−ＦＬＡＧはハイレベルでＤ−ＺＥＲＯがローレベルとなることを特徴とし、
   前記第１信号発生部が、
   前記制御信号ＣＡＳＥ３−ＦＬＡＧと前記制御信号Ｄ−ＺＥＲＯとの論理和を計算して、選択信号ＳＥＬ１を出力する第１ＯＲゲートと、
   前記Ｄ−ＺＥＲＯと前記第１ＯＲゲートからの出力ＳＥＬ１との論理和を計算して、選択信号ＳＥＬ２を出力する第２ＯＲゲートと、
   符号語終了信号ＣＷ−ＥＮＤを反転させる第１インバータと、
   第１インバータからの反転ＣＷ−ＥＮＤとリセット信号ＲＳＴとの論理積を計算し、リセット信号ＲＳＴ１を発生して前記第１シフトレジスタ部及び前記ディスクレパンシ計算部に供給する第１ＡＮＤゲートを有することを特徴とする誤り位置検出多項式計算装置。
2. 前記選択部が、
   定数を格納するＲＯＭと、
   前記第２ＯＲゲートからのＳＥＬ２がハイレベルである場合、前記ＲＯＭからの定数を選択出力し、前記ＳＥＬ２がローレベルである場合には、前記ディスクレパンシ計算部からの更新済みの誤り位置検出多項式を選択出力する第１ＭＵＸと、
   前記第１ＯＲゲートからのＳＥＬ１がローレベルである場合、前記第１ＭＵＸからの出力を選択出力し、前記ＳＥＬ１がハイレベルである場合には、前記第１シフトレジスタ部からのフィードバック値を選択供給する第２ＭＵＸを有することを特徴とする請求項１に記載の誤り位置検出多項式計算装置。
3. 前記定数が、「０」であることを特徴とする請求項１若しくは２に記載の誤り位置検出多項式計算装置。
4. 前記第１シフトレジスタ部が、ｔ個のレジスタが直列に接続されたものであり、前記選択部からの出力をシフトさせ出力することを特徴とする請求項１乃至３に記載の誤り位置検出多項式計算装置。
5. 前記ディスクレパンシ計算部が、
   前記第１ＧＦ加算器からの更新済みの誤り位置検出多項式をシフトさせ、最後に更新済みの誤り位置検出多項式を完全誤り位置検出多項式として出力する第２シフトレジスタ部と、
   前記第１ＧＦ加算器からの出力または前記第２シフトレジスタ部からのシフトされた誤り位置検出多項式を選択出力する第３ＭＵＸと、
   前記第３ＭＵＸからの出力とシンドロームとを乗じる第３ＧＦ乗算器と、
   前記第３ＧＦ乗算器からの出力とフィードバック値とを加算する第２ＧＦ加算器と、
   ビットクロックＢＩＴ−ＣＬＫによって前記第２ＧＦ加算器からの出力をラッチして、前記第２ＧＦ加算器にフィードバックさせるフィードバックレジスタと、
   前記第２ＧＦ加算器からの出力をラッチしてディスクレパンシとして出力する出力レジスタと、
   前記ディスクレパンシを判断して前記Ｄ−ＺＥＲＯを出力するディスクレパンシ確認部と、
   制御信号を前記出力レジスタ及び前記第２シフトレジスタ部に出力する第２信号発生部と、
   前記第２シフトレジスタ部からの出力を前記更新済みの誤り位置検出多項式の係数として選択して出力する係数選択部とを有することを特徴とする請求項１乃至４に記載の誤り位置検出多項式計算装置。
6. 前記第２信号発生部が、
   前記ディスクレパンシ終了信号Ｄ−ＥＮＤを反転させる第２インバー夕と、
   前記第２インバータからの反転Ｄ−ＥＮＤと前記ＲＳＴとを論理積を計算して、前記フィードバックレジスタに出力する第２ＡＮＤゲートとを有することを特徴とする請求項５に記載の誤り位置検出多項式計算装置。
7. 前記第２シフトレジスタ部が、ｔ＋１個のレジスタが直列に接続されたものであり、前記第１ＧＦ加算器からの出力をシフトさせ出力することを特徴とする請求項５若しくは６に記載の誤り位置検出多項式計算装置。

Images