特許

J-GLOBAL ID：200903009349970700

リードソロモン復号化器

発明者： ズーク,クリストファー ピー.
出願人/特許権者： シーラス ロジック,インコーポレイテッド
代理人 (1件)： 山本 秀策
公報種別：公表公報
出願番号（国際出願番号）：特願平7-513257
公開番号（公開出願番号）：特表平9-507117
出願日： 1994年10月18日
公開日（公表日）： 1997年07月15日
要約：

【要約】リードソロモン復号化器(199)は、n個のmビットシンボルを含む符号語を処理することによって、誤り位置多項式σ(x)の係数を決定し、その後誤り評価多項式ω(x)を生成する。復号化器は、シンドローム値を格納するシンドロームレジスタ(103)のバンク(B103)と、誤り位置多項式σ(x)の係数を蓄積する誤り位置レジスタ(101)のバンク(B101)と、中間多項式τ(x)の係数を蓄積する中間レジスタ(102)のバンク(B102)とを有している。復号化器(199)は更に、所与の符号語に対して、2フェーズの誤り位置反復を行うことによって誤り位置レジスタおよび中間レジスタ中の値を更新するレジスタ更新回路(50)を有している。先行技術とは対照的に、本発明のレジスタ更新回路(50)は、中間多項式τ(x)の係数を各誤り位置反復の第1フェーズ中に更新し、誤り位置多項式σ(x)の係数を各誤り位置反復の第2フェーズ中に更新する。更に対照的に、本発明の復号化器(199)は、誤り位置レジスタ(101)のバンクおよび中間レジスタ(102)のバンクを一つずつしか必要としなく、パラレルデータ転送よりもシリアルデータシフトを容易にし、その結果、回路実体を減少させる。

請求項（抜粋）：

排他的な所有権または特権を請求する本発明の実施態様を以下に定義する。1.複数の誤り位置反復を行うことによって符号語に対する誤り位置多項式の係数を示す電気信号を生成する復号化器であって、該各誤り位置反復は2つのフェーズを含み、該復号化器は、 中間レジスタのバンクに格納された電気信号を該各反復の第1フェーズ中に更新する第1回路手段であって、該中間レジスタのバンクに格納された電気信号は、中間多項式τn(x)の更新された係数の値を表し、該第1回路手段は、 直前の誤り位置反復中に生成される前の不一致d(n-1)-1の逆元を表す電気信号と、 第1誤り位置反復後のすべての誤り位置反復に対して該直前の誤り位置反復中に更新された場合に、該誤り位置多項式σn(x)の更新された係数の値を表す電気信号とを利用する、第1回路手段と、 現在の不一致dnを表す電気信号を該各誤り位置反復の該第1フェーズ中に生成する第2回路手段であって、該第1誤り位置反復後のすべての誤り位置反復に対して該直前の誤り位置反復中に更新された場合に、該誤り位置多項式σn(x)の係数を表す電気信号を利用する、第2回路手段と、 誤り位置反復中に該現在の不一致の逆元dn-1を表す電気信号を生成する反転回路であって、該逆元dn-1が直後の誤り位置反復中に該前の不一致dn-1-1の逆元となる、反転回路と、 該誤り位置多項式σn+1(x)の係数を表す電気信号を各誤り位置反復の第2フェーズ中に生成する、該第1および該第2回路手段に接続された第3回路手段であって、該第3回路手段は、 該直前の誤り位置反復中に更新された場合に、該誤り位置多項式σn(x)の係数を表す電気信号と、 該現在の不一致dnを表す電気信号と、 該第1フェーズ中に更新された場合に、該中間多項式τn(x)の係数を表す電気信号とを利用する、第3回路手段と備えており、 これによって、該符号語の最終誤り位置反復の完了時に、該誤り位置多項式の該係数の最終値を示す電気信号が誤り位置レジスタの該バンクに格納される、復号化器。2.リードソロモン復号化手順の少なくとも第1反復および第2反復を含む複数の反復を実行し、誤り位置多項式の係数を得る誤り復号化器であって、各反復が、第1フェーズおよび第2フェーズを含み、該復号化器は、 少なくとも各反復の該第1フェーズ中にシンドローム値を格納するシンドロームレジスタのバンクと、 該誤り位置多項式の係数の更新値を該第2反復の該第2フェーズ中に蓄積する誤り位置レジスタのバンクであって、該誤り位置レジスタのバンクは、該第1反復の該第2フェーズ中に得られる係数の値を該第2反復の該第1フェーズ中に格納している、誤り位置レジスタのバンクと、 中間多項式の係数の更新値を該第2反復の該第1フェーズ中に蓄積し、該第2反復の該第2フェーズ中に該中間多項式の該係数の該更新値を格納する、中間レジスタのバンクと、 該中間多項式の該係数の該更新値を該第2反復の該第1フェーズ中に該中間レジスタのバンクに蓄積し、該誤り位置多項式の該係数の該更新値を該第2反復の該第2フェーズ中に該誤り位置レジスタのバンクに蓄積する、レジスタ更新回路と を備えた誤り復号化器。3.前記シンドローム値は、アルファ基底表現で前記シンドロームレジスタのバンクに格納され、前記誤り位置多項式の前記係数は、ベータ基底表現で前記誤り位置レジスタのバンクに蓄積/格納され、前記中間多項式の前記係数は、ベータ基底表現で前記中間レジスタのバンクに蓄積/格納される、請求項2に記載の復号化器。4.前記シンドロームレジスタのバンクは複数のシンドロームレジスタを備えており、前記誤り位置レジスタのバンクは複数の誤り位置レジスタを備えており、前記中間レジスタのバンクは複数の中間レジスタを備えており、各シンドロームレジスタは該誤り位置レジスタの1つと対になってシンドローム/位置レジスタ対を形成し、各中間レジスタは該誤り位置レジスタの1つと対になって中間/位置レジスタ対を形成し、前記レジスタ更新回路は、 乗数積を加算してn-1番目の反復の第1フェーズ中に不一致値dn-1を得、n番目の反復の第1フェーズ中に不一致値dnを得る不一致決定回路であって、該各乗数積は対応するシンドローム/位置レジスタ対における値から導かれる、不一致決定回路と、 該n-1番目の反復中にdn-1-1を決定する不一致反転回路とをさらに備えている、請求項2に記載の復号化器。5.dn-1を決定する前記不一致反転回路は、前記アルファ基底表現でdn-1-1を決定し、前記レジスタ更新回路は、 dnをベータ基底表現からアルファ基底表現に変換する変換回路と、 該アルファ基底表現のdnおよび該アルファ基底表現のdn-1-1の一方を選択的に格納する不一致レジスタと、 該不一致レジスタに接続された乗算フィードバック回路であって、該不一致レジスタ中の値に定数を繰り返し乗算する乗算フィードバック回路とをさらに備えている、請求項4に記載の復号化器。6.前記n番目の反復の前記第1フェーズにおいて、前記レジスタ更新回路は、dn-1-1および前記中間レジスタの前記更新値を蓄積する誤り位置レジスタの前記バンクにその時格納されている値をオプションとして利用する、請求項4に記載の復号化器。7.前記n番目の反復の前記第2フェーズにおいて、前記レジスタ更新回路は、不一致値dnおよび前記中間レジスタの前記バンクにその時格納されている値を用いることにより、前記誤り位置多項式の前記係数の前記更新値を蓄積する、請求項4に記載の復号化器。8.前記不一致レジスタは、消去ポインタ値に対応する電気信号を格納する、請求項5に記載の復号化器。9.各乗数積は、前記シンドローム/位置レジスタ対における前記レジスタの第1番目中の値と、該シンドローム/位置レジスタ対における前記レジスタの第2番目中の値の倍数との積である、請求項4に記載の復号化器。10.前記レジスタの前記第1番目は誤り位置レジスタであり、前記レジスタの前記第2番目は前記シンドローム/位置レジスタ対のシンドロームレジスタである、請求項9に記載の復号化器。11.前記シンドロームレジスタのバンクにおける対応するシンドロームレジスタに対の関係で接続された複数のシンドロームレジスタを備えた改変シンドロームレジスタのバンクであって、各改変シンドロームレジスタは、該改変シンドロームレジスタと対の関係にある該対応するシンドロームレジスタからシンドローム値を受け取るように接続されている、改変シンドロームレジスタのバンクと、 各改変シンドロームレジスタに接続された乗算器フィードバック回路であって、該改変シンドロームレジスタ中の値に前記乗数積を得る際に使用される定数を繰り返し乗算する乗算器フィードバック回路と をさらに備えている、請求項10に記載の復号化器。12.各乗数積は、前記シンドローム/位置レジスタ対における前記レジスタの第1番目中の値と、該シンドローム/位置レジスタ対における前記レジスタの第2番目中の値のα倍数との積である、請求項9に記載の復号化器。13.前記誤り位置多項式の前記係数を格納する誤り位置レジスタのバンクが1つだけであり、前記中間多項式の前記係数を格納する中間レジスタのバンクが1つだけである、請求項2に記載の復号化器。14.前記シンドローム値は、アルファ基底表現で前記シンドロームレジスタの前記バンクに格納され、前記誤り位置多項式の前記係数は、ベータ基底表現で前記誤り位置レジスタの前記バンクに蓄積/格納され、前記中間多項式の前記係数は、ベータ基底表現で前記中間レジスタの前記バンクに蓄積/格納される、請求項4に記載の復号化器。15.シンドローム値を格納するシンドロームレジスタのバンクと、 誤り位置多項式の係数を蓄積する誤り位置レジスタのバンクと、 中間多項式の係数を蓄積する中間レジスタのバンクと、 反復レジスタ更新回路であって、 乗数積を加算して第n反復中に現在の不一致dnを得る不一致決定回路であって、各乗数積は、該シンドロームレジスタおよび該誤り位置レジスタの対に格納された値から導かれる不一致決定回路と、 該不一致の逆元dn-1を決定する不一致反転回路と、 該第n反復中に、前回の第n-1反復における不一致の逆元dn-1-1から導かれる値に該誤り位置レジスタ中の該係数を選択的に乗算することによって、該中間レジスタに格納された該係数を更新する際に使用される値を得、該中間レジスタが更新された後に、該現在の不一致dnから導かれた値に該中間レジスタ中の該係数を乗算することによって、該誤り位置レジスタに格納された該係数を更新するための値を得る更新乗算回路とを備えた反復レジスタ更新回路と を備えたリードソロモン復号化器。16.前記シンドローム値は、アルファ基底表現で前記シンドロームレジスタの前記バンクに格納され、前記誤り位置多項式の前記係数は、ベータ基底表現で前記誤り位置レジスタの前記バンクに蓄積/格納され、前記中間多項式の前記係数は、ベータ基底表現で前記中間レジスタの前記バンクに蓄積/格納される、請求項15に記載の復号化器。17.前記不一致の前記逆元を決定する前記不一致反転回路は、アルファ基底表現で前記不一致の前記逆元を決定する、請求項15に記載の復号化器。18.前記レジスタ更新回路は、dnをベータ基底表現からアルファ基底表現に変換する変換回路をさらに備えている、請求項15に記載の復号化器。19.前記レジスタ更新回路は、 前記アルファ基底表現の前記不一致および前記アルファ表現の前記不一致の前記逆元の一方を選択的に格納する不一致レジスタと、 該不一致レジスタに接続された乗算器フィードバック回路であって、該不一致レジスタ中の値に定数を繰り返し乗算する乗算器フィードバック回路と をさらに備えている、請求項18に記載の復号化器。20.各乗数積は、前記シンドローム/位置レジスタ対における前記レジスタの第1番目中の値と、該シンドローム/位置レジスタ対における前記レジスタの第2番目中の値の倍数との積である、請求項15に記載の復号化器。21.前記レジスタの前記第1番目は、前記シンドローム/位置レジスタ対の誤り位置レジスタであり、前記レジスタの前記第2番目は、前記シンドローム/位置レジスタ対のシンドロームレジスタである、請求項20に記載の復号化器。22.前記シンドロームレジスタのバンクにおける対応するシンドロームレジスタに対の関係で接続された複数のシンドロームレジスタを備えた改変シンドロームレジスタのバンクであって、各改変シンドロームレジスタは、該改変シンドロームレジスタが対の関係で接続された該対応するシンドロームレジスタからシンドローム値を受け取るように接続されている、改変シンドロームレジスタのバンクと、 各改変シンドロームレジスタに接続された乗算器フィードバック回路であって、該改変シンドロームレジスタ中の値に前記乗数積を得る際に使用される定数を繰り返し乗算する乗算器フィードバック回路と をさらに備えている、請求項21に記載の復号化器。23.各乗数積は、前記シンドローム/位置レジスタ対における前記レジスタの第1番目中の値と、該シンドローム/位置レジスタ対における前記レジスタの第2番目中の値のα倍数との積である、請求項15に記載の復号化器。24.前記誤り位置多項式の前記係数を格納する誤り位置レジスタのバンクが1つだけであり、前記中間多項式の前記係数を格納する中間レジスタのバンクが1つだけである、請求項15に記載の復号化器。25.前記乗算器は、前記誤り位置レジスタ中の前記係数または前記中間レジスタ中の前記係数のいずれかに前記不一致または該不一致の前記逆元のうち選択された一方を選択的に乗算する、請求項15に記載の復号化器。26.リードソロモン復号化器のための誤り訂正回路のスライスであって、該スライスは、 誤り位置多項式の係数を格納する誤り位置レジスタと、 中間多項式の係数を格納する中間レジスタと、 該誤り位置レジスタ中の該係数に第1の入力値を選択的に乗算することによって、第1の隣接するスライスに入力する係数を得、該中間レジスタが第2の隣接するスライスからの係数によって更新された後に、第2の入力値に該中間レジスタ中の該係数を乗算することによって、該誤り位置レジスタに格納された該係数を更新するための値を得る更新乗算回路と を備えたスライス。27.前記誤り位置多項式の前記係数は、ベータ基底表現で前記誤り位置レジスタに格納され、前記中間多項式の前記係数は、ベータ基底表現で前記中間レジスタに格納される、請求項26に記載のスライス。28.シンドロームレジスタと、 該シンドロームレジスタおよび前記誤り位置レジスタに格納された値から導かれる項を乗算する、不一致産出乗算器と をさらに備えている、請求項26に記載のスライス。29.前記不一致産出乗算器は、前記誤り位置レジスタ中の値と前記シンドロームレジスタ中の値の倍数とを乗算する、請求項28に記載のスライス。30.前記シンドロームレジスタからのシンドローム値を受け取るように接続された改変シンドロームレジスタと、 該改変シンドロームレジスタに接続された乗算器フィードバック回路であって、該改変シンドロームレジスタ中の値に定数を繰り返し乗算する乗算器フィードバック回路と をさらに備えており、該改変シンドロームレジスタの出力は前記不一致産出乗算器に接続されている、請求項29に記載のスライス。31.前記不一致産出乗算器の出力は、前記スライスにおける前記レジスタの第1番目中の値と該スライスにおける前記レジスタの第2番目中の値のα倍数との積である、請求項28に記載のスライス。32.前記第2の入力値は不一致値であり、前記第1の値は該不一致値の逆元である、請求項26に記載のスライス。33.前記不一致値および前記不一致値の前記逆元は、アルファ基底表現である、請求項32に記載のスライス。34.前記誤り位置多項式の前記係数を格納する誤り位置レジスタが、前記スライス中に1つだけあり、前記中間多項式の前記係数を格納する中間レジスタが、該スライス中に1つだけある、請求項26に記載のスライス。35.前記更新乗算器は、前記誤り位置レジスタ中の前記係数または前記中間レジスタ中の前記係数のいずれか一方に不一致値または該不一致値の逆元のうち選択された一方を選択的に乗算する、請求項26に記載のスライス。36.復号化回路の複数の反復中にリードソロモン符号語の復号化の一部として誤り位置多項式を得る方法であって、該複数の反復は少なくとも前回の反復と現在の反復を含み、各反復は第1フェーズおよび第2フェーズを含み、該方法は、 少なくとも各反復の第1フェーズ中に、シンドローム値をシンドロームレジスタのバンクにロードし、該シンドローム値を該シンドロームレジスタに格納することと、 現在の反復の第1フェーズ中に、前回の反復中に蓄積された該誤り位置多項式の係数の値を誤り位置レジスタのバンクに格納することと、 現在の反復の第1フェーズ中に、該現在の反復の第1フェーズ中に該誤り位置レジスタの該バンクに格納された該誤り位置多項式の該係数の該値を用いて、中間多項式の係数の更新値を蓄積することであって、該中間多項式の該係数は、中間レジスタのバンクに格納されることと、 該現在の反復の第2フェーズ中に、該中間レジスタの該バンクにその時格納されている該中間多項式の該係数を用いて、該誤り位置レジスタ中の該誤り位置多項式の該係数の更新値を蓄積することと を包含する方法。37.復号化回路のm回の反復中に、mビットのリードソロモン符号語の復号化の一部として誤り位置多項式を得る方法であって、該m回の反復は少なくとも前回の反復と現在の反復を含み、各反復は第1フェーズおよび第2フェーズを含み、該方法は、 少なくとも各反復の第1フェーズ中に、シンドローム値を示すmビットの電気信号をシンドロームレジスタのバンクにロードし、該シンドローム値を示す該電気信号を該シンドロームレジスタに格納することと、 現在の反復の第1フェーズ中に、前回の反復中に蓄積された該誤り位置多項式の係数の値に対応する電気信号を誤り位置レジスタのバンク中に格納することと、 現在の反復の第1フェーズ中に、該現在の反復の第1フェーズ中に該誤り位置レジスタの該バンクに格納された該誤り位置多項式の該係数の値に対応する該電気信号を用いて、中間多項式の係数の蓄積された更新値に対応する電気信号を生成することであって、該中間多項式の該係数に対応する該電気信号は、中間レジスタのバンクに格納されることと、 該現在の反復の第2フェーズ中に、該中間レジスタのバンクにその時格納されている該中間多項式の該係数に対応する該電気信号を用いて、該誤り位置レジスタ中の該誤り位置多項式の該係数の蓄積された更新値に対応する電気信号を生成することと、 該誤り位置レジスタ中の該誤り位置多項式の該係数の蓄積された更新値に対応する該電気信号を用いて、該符号語を訂正することと を包含する方法。

IPC (2件)：

H03M 13/00 ,  G06F 11/10 330

FI (2件)：

H03M 13/00 ,  G06F 11/10 330 P