JPH0258432A - ビット・シリアル型乗算器を用いた誤り位置多項式導出回路 - Google Patents
ビット・シリアル型乗算器を用いた誤り位置多項式導出回路Info
- Publication number
- JPH0258432A JPH0258432A JP20828488A JP20828488A JPH0258432A JP H0258432 A JPH0258432 A JP H0258432A JP 20828488 A JP20828488 A JP 20828488A JP 20828488 A JP20828488 A JP 20828488A JP H0258432 A JPH0258432 A JP H0258432A
- Authority
- JP
- Japan
- Prior art keywords
- multiplier
- bit
- error locator
- circuit
- locator polynomial
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Pending
Links
Landscapes
- Error Detection And Correction (AREA)
Abstract
(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。
め要約のデータは記録されません。
Description
【発明の詳細な説明】
〔産業上の利用分野〕
リード・ソロモン符号やＢＣＨ符号などの誤り訂正符号
を用いて１ブロツク内の多数ワードの誤り訂正を行う誤
り訂正方式が光ディスク、磁気ディスク、光磁気ディス
ク、通信などの分野で広く採用されている。
を用いて１ブロツク内の多数ワードの誤り訂正を行う誤
り訂正方式が光ディスク、磁気ディスク、光磁気ディス
ク、通信などの分野で広く採用されている。
本発明は、このようなリードソロモン符号やＢＣＨ符号
などの１つの訂正系列内で多数ワードの誤りを訂正可能
な誤り訂正符号（ロング・デイスタンス・コード：ＬＤ
Ｃ）を用いた誤り訂正回路に関し、より詳しくは、ロン
グ・デイスタンス・コードの復号に際して誤り位置多項
式をユークリッド互除法により求めるようにした誤り位
置導出回路に関する。
などの１つの訂正系列内で多数ワードの誤りを訂正可能
な誤り訂正符号（ロング・デイスタンス・コード：ＬＤ
Ｃ）を用いた誤り訂正回路に関し、より詳しくは、ロン
グ・デイスタンス・コードの復号に際して誤り位置多項
式をユークリッド互除法により求めるようにした誤り位
置導出回路に関する。
リードソロモン符号やＢＣＨ符号などのロング・ディス
クンス・コード（以下ＬＤＣ）を用いて多数ワードの誤
り訂正を行うには、受信データからシンドロームを生成
して誤り位置多項式の係数を求める必要がある。一般に
、ＬＤＣの復号手順は次の通りである。
クンス・コード（以下ＬＤＣ）を用いて多数ワードの誤
り訂正を行うには、受信データからシンドロームを生成
して誤り位置多項式の係数を求める必要がある。一般に
、ＬＤＣの復号手順は次の通りである。
■ 受信データＸからシンドロームＳ １（ｘ）を求め
る。
る。
■ シンドロームＳ ｒ （ｘ）から誤り位置多項式σ
（Ｘ）を求める。
（Ｘ）を求める。
■ 誤り位置多項式σ（ｘ）から誤り位置を求める。
■ 誤りパターンを求める。
■ Ｊｌｌり位置と誤りパターンから受信データＸを訂
正する。
正する。
上記一連の処理ステップにおいて最も処理が複雑で時間
を要するのは■の誤り位置多項式σ（ｘ）を求める部分
である。誤り位置多項式の係数を求める手法の１つとし
てユークリッド互除法が知られている。このユークリッ
ド互除法は与えられた２つの数（多項式）の最大公約数
（多項式）を求めるためのアルゴリズムであり、２つの
多項式Ｒ−＋ （ｘ） とＲｏ（ｘ）を与え、下記の（
Ｌｌ 〜（Ｊ Ｒ”：、の演算をＲｔ（ｘ）＝Ｏとなる
まで繰り返し実行し、Ｒｔ （ｘ） ＝０となった時の
Ｒ； −１（ｘ）を与えられた２つの多項式Ｒ−、（ｘ
）とＲｏ（ｘ）の最大公約多項式として決定するもので
ある。
を要するのは■の誤り位置多項式σ（ｘ）を求める部分
である。誤り位置多項式の係数を求める手法の１つとし
てユークリッド互除法が知られている。このユークリッ
ド互除法は与えられた２つの数（多項式）の最大公約数
（多項式）を求めるためのアルゴリズムであり、２つの
多項式Ｒ−＋ （ｘ） とＲｏ（ｘ）を与え、下記の（
Ｌｌ 〜（Ｊ Ｒ”：、の演算をＲｔ（ｘ）＝Ｏとなる
まで繰り返し実行し、Ｒｔ （ｘ） ＝０となった時の
Ｒ； −１（ｘ）を与えられた２つの多項式Ｒ−、（ｘ
）とＲｏ（ｘ）の最大公約多項式として決定するもので
ある。
Ｑ＋（ｘ）＝（Ｒ，−ｚ（ｘ）／Ｒｔ−＋（ｘ））
−１１）Ｒ＝（Ｘ）＝Ｒｉ−ｚ（ｘ）−Ｑ＋（ｘ）Ｒ
；−＋（ｘ） −１２１Ｌ；（ｘ） ＝ Ｌｔ−ｚ（
ｘ） Ｑｉ（ｘ） Ｌ＝−＋（ｘ） −１３１Ｕ１
（ｘ）＝Ｕ、−ｚ（ｘ）−Ｑ；（ｘ）Ｕ；−＋（ｘ）
−（４１但し、（）は商多項弐を表す。
−１１）Ｒ＝（Ｘ）＝Ｒｉ−ｚ（ｘ）−Ｑ＋（ｘ）Ｒ
；−＋（ｘ） −１２１Ｌ；（ｘ） ＝ Ｌｔ−ｚ（
ｘ） Ｑｉ（ｘ） Ｌ＝−＋（ｘ） −１３１Ｕ１
（ｘ）＝Ｕ、−ｚ（ｘ）−Ｑ；（ｘ）Ｕ；−＋（ｘ）
−（４１但し、（）は商多項弐を表す。
Ｌ−、（ｘ） ＝ Ｏ、ＬＯ（Ｘ） ＝ １Ｕ−１（に
）＝−１，Ｕ、（に）＝０ このユークリッド互除法の演算過程においては次の性質
が成り立つ。
）＝−１，Ｕ、（に）＝０ このユークリッド互除法の演算過程においては次の性質
が成り立つ。
Ｒ１（ｘ） ＝ Ｌ ；（ｘ） Ｒｏ（ｘ） −［１（
ｘ） ｒｌ！−＋（ｚ）ｄｅｇ、 Ｒ；（ｘ） ＜ｄｅ
ｇ、 Ｒ；−＋（ｘ） −−［６１ｄｅｇ、Ｌ
ｉ（ｘ）＝ｄｅｇ、Ｒ−＋（ｘ）−ｄｅｇ、Ｒ；−＋（
ｘ）・−一−・−（７） Ｌ 、 （ｘ）≠０ −
・−・・・・・−・（８）ｇｒ、ｄ （Ｕ ｒ 、 Ｌ
ｒ ） ＝ １ −−一−−−
−−（９１ここに、ｇｃｄ（）は最大公約多項式を示す
。
ｘ） ｒｌ！−＋（ｚ）ｄｅｇ、 Ｒ；（ｘ） ＜ｄｅ
ｇ、 Ｒ；−＋（ｘ） −−［６１ｄｅｇ、Ｌ
ｉ（ｘ）＝ｄｅｇ、Ｒ−＋（ｘ）−ｄｅｇ、Ｒ；−＋（
ｘ）・−一−・−（７） Ｌ 、 （ｘ）≠０ −
・−・・・・・−・（８）ｇｒ、ｄ （Ｕ ｒ 、 Ｌ
ｒ ） ＝ １ −−一−−−
−−（９１ここに、ｇｃｄ（）は最大公約多項式を示す
。
いま問題とする誤り位置多項式σ（ｘ）は、上記ユーク
リッド互除法の演算過程においてＲｒ （ｘ）の次故が
１次未満（Ｌは誤り訂正可能なワード数）となった時の
Ｌ Ｈ（ｘ）として得られる。
リッド互除法の演算過程においてＲｒ （ｘ）の次故が
１次未満（Ｌは誤り訂正可能なワード数）となった時の
Ｌ Ｈ（ｘ）として得られる。
すなわち、シンドロームＳ、は、
で表される。ここに、αはガロア体ＧＦ（２″）上の原
始元であり、Ｘ、は受信語を表す。
始元であり、Ｘ、は受信語を表す。
前記シンドロームＳ、を基にシンドローム多項式Ｓ （
ｘ）を次の通り定義する。
ｘ）を次の通り定義する。
５（Ｘ）＝Ｓ、＋Ｓ、Ｘ＋Ｓ２Ｘ”＋・＋Ｓ？Ｘ’・・
−・ ０υ また、誤りが１個発生した時の誤り位置多項式σ（ｘ）
を次の通り定義する。
−・ ０υ また、誤りが１個発生した時の誤り位置多項式σ（ｘ）
を次の通り定義する。
ｆ （ｘ） ＝ （Ｘ ＋ ＶＩ）（Ｘ ＋ Ｖｚ）−
（Ｘ ＋ Ｖｔ）＝ Ｘ ｌ＋σ、−、’Ｘ’−’＋・
・・十σ、Ｘ＋σ。
（Ｘ ＋ Ｖｔ）＝ Ｘ ｌ＋σ、−、’Ｘ’−’＋・
・・十σ、Ｘ＋σ。
・−（１乃
ここに、■、〜■１ は誤り位置を示す。
上記シンドローム多項式Ｓ （ｘ）と誤り位置多項式σ
（ｘ）との間には次の関係がある。
（ｘ）との間には次の関係がある。
Ａ （ｘ） Ｘ ２Ｌ＋ ｔｙ （ｘ） Ｓ （ｘ）
＝ ｔｉ Ｃｘ） −−−−０３１ｄｅｇ、 （
１１（ｘ） ＜ｄｅｇ、 ｔｔ （ｘ） ≦ｔ
−−−−−ａＩＯ但し Ａ （ｘ）コ任意の多項式 ω（Ｘ）：誤り評価多項式 Ｌ 二訂正可能な誤りワード数 ｄｅｇ、ω（Ｘ）：多項式〇（ｘ）の次数ｄｅｇ、σ（
×）：多項式σ（ｘ）の次数このＱ３）、０４１式を満
たすσ（ｘ）と０パＸ）は、Ｘ２ｔとＳ （ｘ）の最大
公約多項式を求めるユークリッドの互除法の演算過程に
おいて、Ｒｉ（ｘ）の次数がｔ次未満（ｔは誤り訂正可
能なワード数）となった時のＬ 、 （ｘ）とＲ＝ （
ｘ）に他ならない。
＝ ｔｉ Ｃｘ） −−−−０３１ｄｅｇ、 （
１１（ｘ） ＜ｄｅｇ、 ｔｔ （ｘ） ≦ｔ
−−−−−ａＩＯ但し Ａ （ｘ）コ任意の多項式 ω（Ｘ）：誤り評価多項式 Ｌ 二訂正可能な誤りワード数 ｄｅｇ、ω（Ｘ）：多項式〇（ｘ）の次数ｄｅｇ、σ（
×）：多項式σ（ｘ）の次数このＱ３）、０４１式を満
たすσ（ｘ）と０パＸ）は、Ｘ２ｔとＳ （ｘ）の最大
公約多項式を求めるユークリッドの互除法の演算過程に
おいて、Ｒｉ（ｘ）の次数がｔ次未満（ｔは誤り訂正可
能なワード数）となった時のＬ 、 （ｘ）とＲ＝ （
ｘ）に他ならない。
第５図は上記のユークリッド互除法を用いて誤り位置多
項式σ（×）と誤り評価多項式ω（ｘ）を求めるＫｕｎ
ｎｇ らによって［されたシストリック・アルゴリズム
を示す。このシストリック・アルゴリズムでは、前記し
たＲ ｒ （ｘ）をＡ （ｘ）とＢ（に）で交互に表し
、またＬ ； （ｘ）をＬ （ｘ）とＭ （ｘ）で交互
に表している。
項式σ（×）と誤り評価多項式ω（ｘ）を求めるＫｕｎ
ｎｇ らによって［されたシストリック・アルゴリズム
を示す。このシストリック・アルゴリズムでは、前記し
たＲ ｒ （ｘ）をＡ （ｘ）とＢ（に）で交互に表し
、またＬ ； （ｘ）をＬ （ｘ）とＭ （ｘ）で交互
に表している。
ここでＡ （ｘ）とＢ （ｘ）を次のように表す。
Ａ（ｘ）＝ａ、ｘ’＋ａ、−、ｘト１＋−°−ａ 、
ｘ ＋ａ 。−−−−Ｏ５ Ｂ （ｘ）＝ ｂｌＩｘ’＋ ｂｌＩ−、Ｘ’−’＋・
＋・ｂ 、 ｘ ＋ ｂ ０−−−〇６） この時、ユークリッド互除法における前記（］）。
ｘ ＋ａ 。−−−−Ｏ５ Ｂ （ｘ）＝ ｂｌＩｘ’＋ ｂｌＩ−、Ｘ’−’＋・
＋・ｂ 、 ｘ ＋ ｂ ０−−−〇６） この時、ユークリッド互除法における前記（］）。
（２）式の演算は次式のようになる。
Ｑ、（ｘ）＝ （Ｒ，−ｚ（ｘ）／Ｒ；−＋（ｘ）１＝
ＱｂＸｋ＋ｑｋ−、ｘｈ−１・・・＋ｑ＋Ｘ”ｑ。
ＱｂＸｋ＋ｑｋ−、ｘｈ−１・・・＋ｑ＋Ｘ”ｑ。
・−−−−−−−・−０η
Ａ （ｘ） ＝ Ａ （ｘ） −Ｑ （Ｘ） Ｂ （Ｘ
） −−−−θ（至）０匂式の代わりに次式
の演算をに＋１回繰り返して行う。
） −−−−θ（至）０匂式の代わりに次式
の演算をに＋１回繰り返して行う。
Ａ （ｘ） ＝ Ａ （ｘ） −ｑ ｕｘ ’ Ｂ （
ｘ） ・−−−一−−・−（１９）（ｕ ＝
に、に−１，・・・、０） ａ９，００式の各演算時のＡ （ｘ）とＢ （ｘ）の最
高次数の係数をそれぞれβ、αと置くと ｑｕ＝β／α −−−一・・−
・（２Ｉとなり、ｕ ＝ｄｅｇ、 Ａ −ｄｅｇ、 Ｂ
であることを利用すると、０９１式は次のように書き直
せる。
ｘ） ・−−−一−−・−（１９）（ｕ ＝
に、に−１，・・・、０） ａ９，００式の各演算時のＡ （ｘ）とＢ （ｘ）の最
高次数の係数をそれぞれβ、αと置くと ｑｕ＝β／α −−−一・・−
・（２Ｉとなり、ｕ ＝ｄｅｇ、 Ａ −ｄｅｇ、 Ｂ
であることを利用すると、０９１式は次のように書き直
せる。
ａ Ａ （ｘ） ＝ ｅｘ Ａ （ｘ）−βｘ （ｄ
ａ’ｌ −Ａ −ｄ Ｉ！ ９ °” ’ Ｂ（ｘ）・
・−・・−・（２１） したがって、αＡ（ｘ）、を再びＡ （ｘ）に置き換え
れば、掛は算だけで誤り位置多項式の定係数倍の結果を
得ることができる。すなわち、Ａ （ｘ）またはＢ （
ｘ）のどちらかがｔ次未満になった時点のしく×）また
はＭ （ｘ）が定数倍された誤り位置多項式を表してい
る。また、この時のＡ （Ｘ）またはＢ （ｘ）が定数
倍された誤り評価多項式を表している。
ａ’ｌ −Ａ −ｄ Ｉ！ ９ °” ’ Ｂ（ｘ）・
・−・・−・（２１） したがって、αＡ（ｘ）、を再びＡ （ｘ）に置き換え
れば、掛は算だけで誤り位置多項式の定係数倍の結果を
得ることができる。すなわち、Ａ （ｘ）またはＢ （
ｘ）のどちらかがｔ次未満になった時点のしく×）また
はＭ （ｘ）が定数倍された誤り位置多項式を表してい
る。また、この時のＡ （Ｘ）またはＢ （ｘ）が定数
倍された誤り評価多項式を表している。
第６図に」；記ユークリッド互除法を用いて構成した３
重誤り訂正可能（ｔ＝３）な誤り位置多項式４出回路の
例を示す。図示回路は第５図のシストリック・アルゴリ
ズム中のＡ （ｘ）とＢ （ｘ）の演算部分のみを示し
ており、Ａ （ｘ）とＢ （ｘ）の演算をパラレル処理
するものである。なお、Ｌ （ｘ）とＭ （ｘ）の演算
部分については同様の回路構成で行うことができるので
図示を略した。
重誤り訂正可能（ｔ＝３）な誤り位置多項式４出回路の
例を示す。図示回路は第５図のシストリック・アルゴリ
ズム中のＡ （ｘ）とＢ （ｘ）の演算部分のみを示し
ており、Ａ （ｘ）とＢ （ｘ）の演算をパラレル処理
するものである。なお、Ｌ （ｘ）とＭ （ｘ）の演算
部分については同様の回路構成で行うことができるので
図示を略した。
図中、符号１，２はＡ（ｘ） 、 Ｂ（ｘ）の係数デ
ータを格納するためのビット・シリアル・シフトレジス
タであり、パラレルロードの機能を有している。３，４
はそれぞれビット・シリアル・シフトレジスタ１，２か
ら与えられるＡ（ｘ） 、Ｂ（ｘ）の係数データを保
持するためのバッファ、５，６はビット・シリアル・シ
フトレジスタ１，２０入力を選択するセレクタである。
ータを格納するためのビット・シリアル・シフトレジス
タであり、パラレルロードの機能を有している。３，４
はそれぞれビット・シリアル・シフトレジスタ１，２か
ら与えられるＡ（ｘ） 、Ｂ（ｘ）の係数データを保
持するためのバッファ、５，６はビット・シリアル・シ
フトレジスタ１，２０入力を選択するセレクタである。
７．８はバッファ３，４から与えられるＡ （ｘ）Ｂ（
×）の係数データとビット・シリアル・レジスタ１６．
２６から与えられる最高次数α、βとの乗算αＡ（Ｘ）
、βＢ （ｘ）を行うためのガロア体乗算器である
。
×）の係数データとビット・シリアル・レジスタ１６．
２６から与えられる最高次数α、βとの乗算αＡ（Ｘ）
、βＢ （ｘ）を行うためのガロア体乗算器である
。
９は加算器、１０〜１２はセレクタであり、セレクタ１
１．１２は初期データの設定時以外は“０”を入力する
。なお、ビット・シリアル・シフトレジスタ１６と２６
はそれぞれＡ（ｘ） 、Ｂ（ｘ）の最高次数係数、す
なわちβとαを表している。
１．１２は初期データの設定時以外は“０”を入力する
。なお、ビット・シリアル・シフトレジスタ１６と２６
はそれぞれＡ（ｘ） 、Ｂ（ｘ）の最高次数係数、す
なわちβとαを表している。
また、次数に関する処理はフラグを用いて独立に行って
いるが、このフラグ関係は図示を略した。
いるが、このフラグ関係は図示を略した。
上記回路の動作を第７図のフローチャートを参照して説
明する。
明する。
先ず、セレクタ１１．１２を通じて初期データを設定す
る。すなわち、ｔ＝３であるから２ｔ＝６となるので、
ビット・シリアル・シフトレジスタ１゜〜１６にＡ（ｘ
）＝Ｘ’を設定するとともに、ビット・シリアル・シフ
トレジスタ２゜〜２６にＢ （ｘ）としてシンドローム
多項式Ｓ （ｘ）を設定する。また、図示にない他のＬ
（ｘ） とＭ （ｘ）の演算回路のしく×）に０を、
Ｍ （ｘ）に１をそれぞれセットする（ステップ［１コ
）。同時に、図示を略した次数計算用のフラグなどもセ
ットする。
る。すなわち、ｔ＝３であるから２ｔ＝６となるので、
ビット・シリアル・シフトレジスタ１゜〜１６にＡ（ｘ
）＝Ｘ’を設定するとともに、ビット・シリアル・シフ
トレジスタ２゜〜２６にＢ （ｘ）としてシンドローム
多項式Ｓ （ｘ）を設定する。また、図示にない他のＬ
（ｘ） とＭ （ｘ）の演算回路のしく×）に０を、
Ｍ （ｘ）に１をそれぞれセットする（ステップ［１コ
）。同時に、図示を略した次数計算用のフラグなどもセ
ットする。
次いで、ビット・シリアル・シフトレジスタ１゜〜１．
に設定されたＡ （ｘ）の値をバッファ３゜〜３．にロ
ート′するとともに、ビット・シリアル・シフトレジス
タ２゜〜２．に設定されたＢ （ｘ）−Ｓ （ｘ）の値
をバッファ４゜〜４．にそれぞれロードする（ステップ
［２］）。また、ガロア体乗算器７，８の演算結果を次
段のビット・シリアル・シフトレジスタへ転送するため
に、各セレクタ５゜〜５．および６゜〜６．をセレクタ
１０ｏ〜１０ｓ側へ切り替える（ステ７プ「３Ｊ）。
に設定されたＡ （ｘ）の値をバッファ３゜〜３．にロ
ート′するとともに、ビット・シリアル・シフトレジス
タ２゜〜２．に設定されたＢ （ｘ）−Ｓ （ｘ）の値
をバッファ４゜〜４．にそれぞれロードする（ステップ
［２］）。また、ガロア体乗算器７，８の演算結果を次
段のビット・シリアル・シフトレジスタへ転送するため
に、各セレクタ５゜〜５．および６゜〜６．をセレクタ
１０ｏ〜１０ｓ側へ切り替える（ステ７プ「３Ｊ）。
ガロア体乗算器７゜〜７．はビット・シリアル・シフト
レジスタＩ、の最高次数係数αと各バッファ３゜〜３．
の値との乗算αＡ （ｘ）を行い、またガロア体乗算器
８゜〜８．はビット・シリアル・シフトレジスタ２６の
最高次数係数βと各バッファ４゜〜４５の値との乗算β
Ｂ （ｘ）を行い（ステップ［４］ ）、それぞれの乗
算結果を１ビツトづつ各加算器９゜〜９Ｓに送って加算
する（ステップ［５］）。
レジスタＩ、の最高次数係数αと各バッファ３゜〜３．
の値との乗算αＡ （ｘ）を行い、またガロア体乗算器
８゜〜８．はビット・シリアル・シフトレジスタ２６の
最高次数係数βと各バッファ４゜〜４５の値との乗算β
Ｂ （ｘ）を行い（ステップ［４］ ）、それぞれの乗
算結果を１ビツトづつ各加算器９゜〜９Ｓに送って加算
する（ステップ［５］）。
上記加算結果は、図示を略した次数フラグの制御の下に
セレクタ１０゜〜１０．を通じて次段のビット・シリア
ル・シフトレジスタ１，２へ転送される（ステップ［６
］）。
セレクタ１０゜〜１０．を通じて次段のビット・シリア
ル・シフトレジスタ１，２へ転送される（ステップ［６
］）。
セレクタ５゜〜５Ｓと６゜〜６５をビット・シリアル・
シフトレジスタ側へ切り替えた後（ステップ［７］）、
図示にない０検定回路によりビット・シリアル・シフト
レジスタ１６，２．に格納されているＡ （ｘ）とＢ
（ｘ）の最高次数係数βとαの何れかがＯであるか否か
が判定され（ステップ［８］）、何れかが０である場合
には、対応する側のビット・シリアル・シフトレジスタ
１または２を】ワードシフトする（ステップ［９，］）
。ビット・シリアル・シフトレジスタｌ側がシフトされ
るとＡ （ｘ）の次数が１つ減り、ビット・シリアル・
シフトレジスタ２側がシフトされるとＢ （ｘ）の次数
が１つ減る。
シフトレジスタ側へ切り替えた後（ステップ［７］）、
図示にない０検定回路によりビット・シリアル・シフト
レジスタ１６，２．に格納されているＡ （ｘ）とＢ
（ｘ）の最高次数係数βとαの何れかがＯであるか否か
が判定され（ステップ［８］）、何れかが０である場合
には、対応する側のビット・シリアル・シフトレジスタ
１または２を】ワードシフトする（ステップ［９，］）
。ビット・シリアル・シフトレジスタｌ側がシフトされ
るとＡ （ｘ）の次数が１つ減り、ビット・シリアル・
シフトレジスタ２側がシフトされるとＢ （ｘ）の次数
が１つ減る。
β、αの何れもがＯでない場合には、ステップ［１０］
へ移行し、図示にない終了チエツク回路においてビット
・シリアル・シフトレジスタｌ。
へ移行し、図示にない終了チエツク回路においてビット
・シリアル・シフトレジスタｌ。
２に格納されているＡ（Ｘ） 、 １３（ｘ）のｄｅ
ｇ、 Ａまたはｄｅｇ、 Ｂが判定され、ｔ＝３以上の
場合にはステ７プ［２］へ復帰して上記処理を繰り返し
実行する。他方、ｄｅｇ、Ａまたはｄｅｇ、 Ｂが（＝
３よりも小さい場合には該時点でユークリッド互除法に
よる演算処理を終了しくステップ［１０］ ） 、ビッ
ト・シリアル・シフトレジスタに格納されているデータ
を出力する（ステップ［１１］）。
ｇ、 Ａまたはｄｅｇ、 Ｂが判定され、ｔ＝３以上の
場合にはステ７プ［２］へ復帰して上記処理を繰り返し
実行する。他方、ｄｅｇ、Ａまたはｄｅｇ、 Ｂが（＝
３よりも小さい場合には該時点でユークリッド互除法に
よる演算処理を終了しくステップ［１０］ ） 、ビッ
ト・シリアル・シフトレジスタに格納されているデータ
を出力する（ステップ［１１］）。
すなわち、上記終了時にビット・シリアル・シフトレジ
スタ側または２に格納されてるするＡ （ｘ）またはＢ
（×）がその時の受信データに対する誤り評価多項式ω
（ｘ）を与え、また図示を略した他のＬ （ｘ）とＭ
（ｘ）の演算回路に格納されているしく×）またはＭ（
ｘ）が誤り位置多項式σ（ｘ）を与えるものである。
スタ側または２に格納されてるするＡ （ｘ）またはＢ
（×）がその時の受信データに対する誤り評価多項式ω
（ｘ）を与え、また図示を略した他のＬ （ｘ）とＭ
（ｘ）の演算回路に格納されているしく×）またはＭ（
ｘ）が誤り位置多項式σ（ｘ）を与えるものである。
（発明が解決しようとする課題〕
上記誤り位置多１項弐導出回路におけるガロア体乗算器
は、Ａ （ｘ）とＢ （ｘ）用に４を個、またｆ、（ｘ
）とＭ （ｘ）用に２Ｌ個必要となり、合計６を個が必
要となる。従来用いられているガロア体乗算器としては
、例えばビット・パラレル型のもので１個当たり３００
ゲ一ト程度を必要とし、上記例のむ＝３の場合には全体
で約５４００ゲート程度必要となる。したがって、ｔ＝
８の周知の光ディスクなどのＬＤＣの場合には全体で約
２万ゲート程度を必要とし、回路のハードウェア量が大
きくなって装置の小型化の障害となる。
は、Ａ （ｘ）とＢ （ｘ）用に４を個、またｆ、（ｘ
）とＭ （ｘ）用に２Ｌ個必要となり、合計６を個が必
要となる。従来用いられているガロア体乗算器としては
、例えばビット・パラレル型のもので１個当たり３００
ゲ一ト程度を必要とし、上記例のむ＝３の場合には全体
で約５４００ゲート程度必要となる。したがって、ｔ＝
８の周知の光ディスクなどのＬＤＣの場合には全体で約
２万ゲート程度を必要とし、回路のハードウェア量が大
きくなって装置の小型化の障害となる。
また、シストリック・アルゴリズムに基づいたバイブラ
イン処理による高速化とＶＬＳＩ化に通したリード・ソ
ロモン符号の符号化・復号化のためのプロセッシングユ
ニン） （ＰＥ）が岩村らにより提案されている（電子
情報通信学会論文誌’８８／３ Ｖｏｌ、Ｊ７１−Ａ
Ｎｏ、３ ｐｐ７５１〜７５９ ） 、しかし、このＩ
Ｈになるプロセッシングユニットでも、１個のユニット
当たり１０００ゲート程度を必要とし、回路全体でこれ
が（７ｔ＋４）個必要となる。
イン処理による高速化とＶＬＳＩ化に通したリード・ソ
ロモン符号の符号化・復号化のためのプロセッシングユ
ニン） （ＰＥ）が岩村らにより提案されている（電子
情報通信学会論文誌’８８／３ Ｖｏｌ、Ｊ７１−Ａ
Ｎｏ、３ ｐｐ７５１〜７５９ ） 、しかし、このＩ
Ｈになるプロセッシングユニットでも、１個のユニット
当たり１０００ゲート程度を必要とし、回路全体でこれ
が（７ｔ＋４）個必要となる。
したがって、光ディスクなどで採用しているｔ＝８の場
合には合計で約６万ゲート必要となり、高価なシステム
となってしまう。
合には合計で約６万ゲート必要となり、高価なシステム
となってしまう。
本発明は上記事情に鑑み、この種の誤り位置多項式導出
回路におけるハードウェアの大部分を占めるガロア体乗
算器の回路構成を検討することにより、ガロア体乗算器
のハードウェア量を従来よりも低減し、演算の高速化と
同時に装置の小型化を図った誤り位置多項式導出回路を
提供するものである。
回路におけるハードウェアの大部分を占めるガロア体乗
算器の回路構成を検討することにより、ガロア体乗算器
のハードウェア量を従来よりも低減し、演算の高速化と
同時に装置の小型化を図った誤り位置多項式導出回路を
提供するものである。
本発明は上記目的を実現するめに、ロングデイスタンス
コートの復号に際し、ユークリッド互除法を用いてシン
ドロームから誤り位置多項式を求める誤り位置多項式導
出回路において、２つの元の乗算を行うガロア体乗算器
として、ハンケル行列で一次変換した元と変換を施しで
いない元とにより乗算を行うようにしたＩｈｅｎｅｒ−
Ｈｏｐｆ方程式に基づいて構成したピント・シリアル型
乗算器を用いるとともに、該ビット・シリアル型乗算２
ｇ内に一方の元を逆変換Ｋ −１する逆変換回路を付設
し、該ビット・シリアル型乗算器に入出力されるすべて
の元をそれぞれハンケル行列Ｋによって一次変換した表
現形式に統一したものである。
コートの復号に際し、ユークリッド互除法を用いてシン
ドロームから誤り位置多項式を求める誤り位置多項式導
出回路において、２つの元の乗算を行うガロア体乗算器
として、ハンケル行列で一次変換した元と変換を施しで
いない元とにより乗算を行うようにしたＩｈｅｎｅｒ−
Ｈｏｐｆ方程式に基づいて構成したピント・シリアル型
乗算器を用いるとともに、該ビット・シリアル型乗算２
ｇ内に一方の元を逆変換Ｋ −１する逆変換回路を付設
し、該ビット・シリアル型乗算器に入出力されるすべて
の元をそれぞれハンケル行列Ｋによって一次変換した表
現形式に統一したものである。
Ｗｉｅｎｅｒ−Ｈｏｐｆ方程式に基づいて構成したビッ
ト・シリアル型乗算器に入出力するすべての元をハンケ
ル行列により一次変換した表現形式に統一しするととも
に、乗算すべき２つの元の一方の元を逆変換して乗算す
るように構成したので、演算が高速化されると同時に回
路の構成が簡潔化される。
ト・シリアル型乗算器に入出力するすべての元をハンケ
ル行列により一次変換した表現形式に統一しするととも
に、乗算すべき２つの元の一方の元を逆変換して乗算す
るように構成したので、演算が高速化されると同時に回
路の構成が簡潔化される。
以下、本発明の実施例につき説明する。
本発明は、第６図に示した誤り位置多項式導出回路にお
けるガロア体乗算器７゜〜７．および８０〜８．として
、以下に詳述するようなＷｉｅｎｅｒＨｏｐｉ方程式に
基づいて構成されたビット・シリアル型乗算器を用いた
ものである。
けるガロア体乗算器７゜〜７．および８０〜８．として
、以下に詳述するようなＷｉｅｎｅｒＨｏｐｉ方程式に
基づいて構成されたビット・シリアル型乗算器を用いた
ものである。
ビット・シリアル型巣′ｎ器としては、正規基底に基づ
く方法によって構成されたものやＢｅｒｌｋａｍｍｐの
方法によって構成されたものなどがあるが、これらの方
法に基づいて構成されたビット・シリアル型乗算器は基
底変換が複雑になる。そこで、本発明は、森井らの提案
になるＷｉｅｎｅｒ−Ｈｏｐｆ方程式に基づいて構成さ
れたビット・シリアル型乗算器（電子情報通信学会論文
誌’８８／３ Ｖｏｌ、Ｊ７１−Ａ Ｎｏ。
く方法によって構成されたものやＢｅｒｌｋａｍｍｐの
方法によって構成されたものなどがあるが、これらの方
法に基づいて構成されたビット・シリアル型乗算器は基
底変換が複雑になる。そこで、本発明は、森井らの提案
になるＷｉｅｎｅｒ−Ｈｏｐｆ方程式に基づいて構成さ
れたビット・シリアル型乗算器（電子情報通信学会論文
誌’８８／３ Ｖｏｌ、Ｊ７１−Ａ Ｎｏ。
３ ｐｐ８４５〜８５３）をガロア体乗算器として採用
した。先ず、このＷｉｅｎｅｒ−Ｈｏｐｆ方程式に基づ
いて構成されたビット・シリアル型乗算器について説明
する。
した。先ず、このＷｉｅｎｅｒ−Ｈｏｐｆ方程式に基づ
いて構成されたビット・シリアル型乗算器について説明
する。
いまベクトル表現されたガロア体ＧＦ（２”）上の２元
ＵおよびＳから Ｖ ” ＩＪ ’ Ｓ −・−−一・・
−−一−−−・−（２２）を満足するＳを求めることを
考える。これはｖ （ｚ） ＝ ｕ （ｚ） −ｓ （
ｚ） ｍｏｄ ｆ（ｚ） −−（２３）但し、ｆ （
ｚ）は原始多項式 を満足するｖ （ｚ）を求めることに等しい。この時、
次式が成立する。
ＵおよびＳから Ｖ ” ＩＪ ’ Ｓ −・−−一・・
−−一−−−・−（２２）を満足するＳを求めることを
考える。これはｖ （ｚ） ＝ ｕ （ｚ） −ｓ （
ｚ） ｍｏｄ ｆ（ｚ） −−（２３）但し、ｆ （
ｚ）は原始多項式 を満足するｖ （ｚ）を求めることに等しい。この時、
次式が成立する。
ている。このハンケル行列ＫによりＵ、Ｖを基底変換す
ると次のようになる。
ると次のようになる。
・−−（２４）
こごで、αはガロア体ＧＦ（２ｆｆｉ）の原始元、βは
任意の元であり、 但し、ｘｅＧＦ（：：’） とする。ここで、 と置く。
任意の元であり、 但し、ｘｅＧＦ（：：’） とする。ここで、 と置く。
一般に、上記にはハンケル行列と呼ばれこの上うなＵと
Ｖを用いると、（２４）式に基づいて第４図に示す一般
的なビット・シリアル型乗算器を構成することができる
。すなわち、シフ１−レジスタＲ９−Ｒ７−１の初期値
として、ＲＨ−ＩＪｔ 、 （ｉ ＝ ０． Ｉ
、 −ｍ −１） −−−−−−（２９）を与える
ことにより、ｍ回のシフト演算でＶｉ（ｉ ＝０．１．
・・・ｍ−１）を出力して生成することができる。
Ｖを用いると、（２４）式に基づいて第４図に示す一般
的なビット・シリアル型乗算器を構成することができる
。すなわち、シフ１−レジスタＲ９−Ｒ７−１の初期値
として、ＲＨ−ＩＪｔ 、 （ｉ ＝ ０． Ｉ
、 −ｍ −１） −−−−−−（２９）を与える
ことにより、ｍ回のシフト演算でＶｉ（ｉ ＝０．１．
・・・ｍ−１）を出力して生成することができる。
ここに、原始多項式「（２）は
ｆ（ｚ）＝ｚ″＋ｆｆｆｉ−、ｚ＋・・・トｆ、ｚ−−
−−−−−（３０）とする。
−−−−−（３０）とする。
しかしながら、第・１図のビット・シリアル型乗算器は
乗する元の表現形式が異なるために汎用性がなく、その
ためにこれまでは一方の乗数が定数である符Ｂ化やシン
ドロームの生成時にしか使用できなかった。
乗する元の表現形式が異なるために汎用性がなく、その
ためにこれまでは一方の乗数が定数である符Ｂ化やシン
ドロームの生成時にしか使用できなかった。
上述したユークリッド互除法における演算では、Ａ（ｘ
） 、 Ｂ（ｘ）の係数と各多項式の最高次数との乗
算を行うため、ガロア体の表現形式は同一でなければな
らない。そこで、本発明はこの第４図に示すＷｉｅｎｅ
ｒ−Ｈｏｐｆ方程式に基づくビット・シリアル型乗算器
を汎用化してユークリッド互除法による誤り位置多項式
導出回路に利用できるようにするために、第２図に示す
ような回路構成として拡張を行い、乗算する２つの元を
同一の表現形式で表示できるようにした。
） 、 Ｂ（ｘ）の係数と各多項式の最高次数との乗
算を行うため、ガロア体の表現形式は同一でなければな
らない。そこで、本発明はこの第４図に示すＷｉｅｎｅ
ｒ−Ｈｏｐｆ方程式に基づくビット・シリアル型乗算器
を汎用化してユークリッド互除法による誤り位置多項式
導出回路に利用できるようにするために、第２図に示す
ような回路構成として拡張を行い、乗算する２つの元を
同一の表現形式で表示できるようにした。
すなわち、第４図ではＵとＶをハンケル行列Ｋによって
一次変換した表現形式とし、Ｓについては多項式基底の
ままであったが、本発明では第２図にその一例をしめす
ように残るＳについても、ハンケル行列にで一次変換し
たＳを用いるように汎用化し、すべての元をハンケル行
列で一次変換した統一した表現形式とする。そして、こ
のハンケル行列にで一次変換したτをもとの基底表現形
式に戻すために、乗算器内に逆変ｌ！ＡＫ −’を行う
逆変換回路を付設した。
一次変換した表現形式とし、Ｓについては多項式基底の
ままであったが、本発明では第２図にその一例をしめす
ように残るＳについても、ハンケル行列にで一次変換し
たＳを用いるように汎用化し、すべての元をハンケル行
列で一次変換した統一した表現形式とする。そして、こ
のハンケル行列にで一次変換したτをもとの基底表現形
式に戻すために、乗算器内に逆変ｌ！ＡＫ −’を行う
逆変換回路を付設した。
これにより、すべての元の表現形式が統一され、したが
ってレジスタの表現形式を変えることなく演算処理を行
うことができる。ここで（２４）式中のβは任意に選べ
るため、ハンケル行列にしたがって逆行列に−１は２１
１−１個あり、最も有利な行列を選ぶことにより逆変換
に必要な回路を最小にすることができる。
ってレジスタの表現形式を変えることなく演算処理を行
うことができる。ここで（２４）式中のβは任意に選べ
るため、ハンケル行列にしたがって逆行列に−１は２１
１−１個あり、最も有利な行列を選ぶことにより逆変換
に必要な回路を最小にすることができる。
上記結論に基づき、−例として、原始多項式がＸ” ＋
Ｘ’ ＋Ｘ’ ＋Ｘ” ＋ １であるｃにうなガｏ７体
ＧＦ（２’）上における上記Ｗｉｅｎｅｒ−Ｈｏｐｆ方
程式に法づくビット・シリアル型乗算器の具体的な構成
例を第３図に示す。ここでβ−α２５０とすると、（２
６）式で与えられる逆行列Ｋ −１はとなる。
Ｘ’ ＋Ｘ’ ＋Ｘ” ＋ １であるｃにうなガｏ７体
ＧＦ（２’）上における上記Ｗｉｅｎｅｒ−Ｈｏｐｆ方
程式に法づくビット・シリアル型乗算器の具体的な構成
例を第３図に示す。ここでβ−α２５０とすると、（２
６）式で与えられる逆行列Ｋ −１はとなる。
この場合、第３図に示すようにこの逆変換は２個のＸＯ
Ｒゲート３１，３２だけで構成することができる。した
がって、ガロア体乗算器１個に必要な回路素子はＡＮＤ
ゲートが８個、ＸＯＲゲートが１１個、被乗数を記憶す
るためのバッファが１ワードである。これは従来のビッ
ト・パラレル型乗算器に比べて約１／３以下のハードウ
ェア量となる。
Ｒゲート３１，３２だけで構成することができる。した
がって、ガロア体乗算器１個に必要な回路素子はＡＮＤ
ゲートが８個、ＸＯＲゲートが１１個、被乗数を記憶す
るためのバッファが１ワードである。これは従来のビッ
ト・パラレル型乗算器に比べて約１／３以下のハードウ
ェア量となる。
第１図は上記の汎用化したＷｉｅｎｅｒ−Ｈｏｐｆ方程
式に基づくビット・シリアル型乗算器を用いて構成した
本発明になる誤り位置多項式導出回路の例である。図示
の回路は、第６図中のαＡ （ｘ）の演算を行うバッフ
ァ３゜〜３１、ガロア体乗算器７゜〜７．の部分に対応
する回路である。
式に基づくビット・シリアル型乗算器を用いて構成した
本発明になる誤り位置多項式導出回路の例である。図示
の回路は、第６図中のαＡ （ｘ）の演算を行うバッフ
ァ３゜〜３１、ガロア体乗算器７゜〜７．の部分に対応
する回路である。
第１図中、Ｂ （ｘ）の最高次数係数を与えるαはハン
ケル行列Ｋにより一次変換された形でシフトレジスタ２
１に入力され、また、Ａ （ｘ）の係数データはハンケ
ル行列Ｋにより一次変換された形でバッファ２２１〜２
２□い、に記憶される。
ケル行列Ｋにより一次変換された形でシフトレジスタ２
１に入力され、また、Ａ （ｘ）の係数データはハンケ
ル行列Ｋにより一次変換された形でバッファ２２１〜２
２□い、に記憶される。
乗算αＡ （ｘ）の実行は、バッファ２２．〜２２ｚｔ
−＋の各係数データを逆変換回路２３においてそれぞれ
逆変換した後、Ａ’Ｎ Ｄプレーン２４に１ピントづつ
送られてシフトレジスタ２１からのαと乗算され、該乗
算結果はＸＯＲプレーン２５により１ピントづつ出力さ
れる。したがって、ユークリッド互除法における（２１
）式を演算するには、第１図の回路を２つ並べてαＡ
（ｘ）とβＢ （ｘ）を計算し、各出力のＸＯＲをとれ
ばよい。 上記構成の場合、ガロア体乗算器が従来の乗
算器よりもかなり小型化でき、ＬＳＩでチップ化が可能
である。
−＋の各係数データを逆変換回路２３においてそれぞれ
逆変換した後、Ａ’Ｎ Ｄプレーン２４に１ピントづつ
送られてシフトレジスタ２１からのαと乗算され、該乗
算結果はＸＯＲプレーン２５により１ピントづつ出力さ
れる。したがって、ユークリッド互除法における（２１
）式を演算するには、第１図の回路を２つ並べてαＡ
（ｘ）とβＢ （ｘ）を計算し、各出力のＸＯＲをとれ
ばよい。 上記構成の場合、ガロア体乗算器が従来の乗
算器よりもかなり小型化でき、ＬＳＩでチップ化が可能
である。
また、α、βをｍ回シフトするだけですべての係数に対
する演算を行うことができるため、誤り訂正可能なワー
ド数が増えても処理時間は１次のオーダーで増えるだけ
で済む。
する演算を行うことができるため、誤り訂正可能なワー
ド数が増えても処理時間は１次のオーダーで増えるだけ
で済む。
本発明によれば、入出力する元の表現形式をハンケル行
列で一次変換した形式に統一するとともに、ガロア体乗
算器として汎用化したＷｉｅｎｅｒ−１１ｏρｆ方程式
に基づいたビット・シリアル型乗算器を用い、該乗算器
内にハンケル行列の逆変換を行う逆変換回路を付設した
ので、処理の高速化と同時にハードウェア量を減らして
装置を小型化することができる。
列で一次変換した形式に統一するとともに、ガロア体乗
算器として汎用化したＷｉｅｎｅｒ−１１ｏρｆ方程式
に基づいたビット・シリアル型乗算器を用い、該乗算器
内にハンケル行列の逆変換を行う逆変換回路を付設した
ので、処理の高速化と同時にハードウェア量を減らして
装置を小型化することができる。
第１図は本発明になる誤り位置多項式導出回路の１実施
例の要部構成を示すブロック図、第２図は本発明に用い
る汎用化したＷｉｅｎｅｒ−Ｈｏｐｆ方程式に基づいて
構成したビット・シリアル型乗算器の構成原理を示す図
、 第３図は上記汎用化した一１ｅｎｅｒ−Ｈｏｐｆ方程弐
に基づいて構成したビット・シリアル型乗算器の具体例
を示す図、 第４図はＷｉｅｎｅｒ−Ｈｏｐｆ方程式に基づいて構成
した汎用化されていない従来の一般的なビット・シリア
ル型乗算器の構成を示す図、第５図はユークリッド互除
法を用いて誤り位置多項式を求めるためのシストリック
・アルゴリズムのフローチャート、 第６図は誤り位置多項式導出回路の構成を示す図、 第７図は誤り位置多項式導出回路の動作のフローチャー
トである。 ２１・・・シフトレジスタ、２２・・・バッファ、２３
・・・逆変換回路、 ５・・・ＸＯＲブレーン、 Ｋ・・・パン ケル行列、 Ｋ−１・・・逆行列。
例の要部構成を示すブロック図、第２図は本発明に用い
る汎用化したＷｉｅｎｅｒ−Ｈｏｐｆ方程式に基づいて
構成したビット・シリアル型乗算器の構成原理を示す図
、 第３図は上記汎用化した一１ｅｎｅｒ−Ｈｏｐｆ方程弐
に基づいて構成したビット・シリアル型乗算器の具体例
を示す図、 第４図はＷｉｅｎｅｒ−Ｈｏｐｆ方程式に基づいて構成
した汎用化されていない従来の一般的なビット・シリア
ル型乗算器の構成を示す図、第５図はユークリッド互除
法を用いて誤り位置多項式を求めるためのシストリック
・アルゴリズムのフローチャート、 第６図は誤り位置多項式導出回路の構成を示す図、 第７図は誤り位置多項式導出回路の動作のフローチャー
トである。 ２１・・・シフトレジスタ、２２・・・バッファ、２３
・・・逆変換回路、 ５・・・ＸＯＲブレーン、 Ｋ・・・パン ケル行列、 Ｋ−１・・・逆行列。
Claims (1)
- 【特許請求の範囲】 ロングディスタンスコードの復号に際し、ユークリッド
互除法を用いてシンドロームから誤り位置多項式を求め
る誤り位置多項式導出回路において、 ２つの元の乗算を行うガロア体乗算器として、ハンケル
行列で一次変換した元と変換を施していない元とにより
乗算を行うようにしたＷｉｅｎｅｒ−Ｈｏｐｉ方程式に
基づいて構成したビット・シリアル型乗算器を用いると
ともに、該ビット・シリアル型乗算器内に一方の元を逆
変換Ｋ＾−＾１する逆変換回路を付設し、 該ビット・シリアル型体乗算器に入出力されるすべての
元をそれぞれハンケル行列Ｋによって一次変換した表現
形式に統一したことを特徴とするビット・シリアル型乗
算器を用いた誤り位置多項式導出回路。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP20828488A JPH0258432A (ja) | 1988-08-24 | 1988-08-24 | ビット・シリアル型乗算器を用いた誤り位置多項式導出回路 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP20828488A JPH0258432A (ja) | 1988-08-24 | 1988-08-24 | ビット・シリアル型乗算器を用いた誤り位置多項式導出回路 |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| JPH0258432A true JPH0258432A (ja) | 1990-02-27 |
Family
ID=16553697
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP20828488A Pending JPH0258432A (ja) | 1988-08-24 | 1988-08-24 | ビット・シリアル型乗算器を用いた誤り位置多項式導出回路 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JPH0258432A (ja) |
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP2007309785A (ja) * | 2006-05-18 | 2007-11-29 | Takenaka Komuten Co Ltd | 固有振動モード抽出方法、固有振動モード抽出装置、および固有振動モード抽出用プログラム |
-
1988
- 1988-08-24 JP JP20828488A patent/JPH0258432A/ja active Pending
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP2007309785A (ja) * | 2006-05-18 | 2007-11-29 | Takenaka Komuten Co Ltd | 固有振動モード抽出方法、固有振動モード抽出装置、および固有振動モード抽出用プログラム |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US4873688A (en) | High-speed real-time Reed-Solomon decoder | |
| US6347389B1 (en) | Pipelined high speed reed-solomon error/erasure decoder | |
| Fitzpatrick | On the key equation | |
| EP0114938B1 (en) | On-the-fly multibyte error correction | |
| US6571368B1 (en) | Systolic Reed-Solomon decoder | |
| US5905740A (en) | Apparatus and method for error correction | |
| EP0621698B1 (en) | Error correction method including erasure correction, and apparatus therefore | |
| CN1095122C (zh) | 差错定位多项式高速计算电路 | |
| JPH07202715A (ja) | 時間定義域代数エンコーダ／デコーダ | |
| US6687725B1 (en) | Arithmetic circuit for finite field GF (2m) | |
| KR100322739B1 (ko) | 유한체연산방법및그장치 | |
| JP2694792B2 (ja) | 誤り位置多項式演算回路 | |
| US8335808B2 (en) | Method and apparatus for processing multiple decomposed data for calculating key equation polynomials in decoding error correction code | |
| JP3343857B2 (ja) | 復号装置、演算装置およびこれらの方法 | |
| US20030126543A1 (en) | Method and apparatus for solving key equation polynomials in decoding error correction codes | |
| JPH11136136A (ja) | リードソロモン符号化装置及び方法 | |
| JP3239522B2 (ja) | データ消失訂正方法とその回路 | |
| JP3614978B2 (ja) | ガロア体の除算方法および除算装置 | |
| KR100552694B1 (ko) | 유한 체에서 곱셈 연산 방법 및 장치 | |
| JPH0258432A (ja) | ビット・シリアル型乗算器を用いた誤り位置多項式導出回路 | |
| JP3233502B2 (ja) | 復号化装置 | |
| JP2907138B2 (ja) | 誤り訂正の演算処理方法及び処理回路 | |
| JP3230888B2 (ja) | ユークリッド互除回路 | |
| US20070011592A1 (en) | Decoder architecture for Reed Solomon codes | |
| JPH08139612A (ja) | リード・ソロモン誤り訂正符号復号化回路 |