JPH06223096A - 多項式系導出装置及びその方法 - Google Patents

Abstract

(57)【要約】 【目的】 代数幾何符号の復号のための多次元配列を生
成する最小多項式の導出を高速に実行する。 【構成】 与えられた多次元配列を生成する最小多項式
系Ｆを求めるために、多項式系Ｆを更新する際に、ｄf_n
⁽ⁱ⁾ を直接計算せず、新たに導入した多項式系Ｂに属す
る多項式の最高次係数ｄ_i を用いて、ステップＳ３４に
おいて多項式系Ｂを更新し、ステップＳ３５において多
項式系Ｆを更新する。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、ディジタル通信系及び
ディジタル記憶系において通信路または記憶媒体で受け
た誤りを、誤り訂正符号を用いて受信側で自動的に訂正
する誤り訂正に関し、特に誤り訂正符号として代数幾何
符号を用いる場合の復号において、与えられた多次元配
列を生成する最小多項式系を求める多項式系導出装置及
びその方法に関する。

【０００２】

【従来の技術】従来、ディジタル通信系及びディジタル
記憶系において通信路または記憶媒体で受けた誤りを、
受信側で自動的に訂正する誤り訂正符号として、リード
・ソロモン（ＲＳ）符号やＢＣＨ符号がよく知られ、コ
ンパクト・ディスクや衛星通信等において実際に装置化
され使用されている（参考文献[1] 参照）。

【０００３】しかし、最近は、代数曲線論を駆使した代
数幾何符号（参考文献[1]-[4] 参照）と呼ばれる符号の
研究が盛んに行われている。代数幾何符号は、前述のＲ
Ｓ符号やＢＣＨ符号をその１クラスとして含む非常に適
用範囲の広い符号系であり、従来の符号よりもよい性質
を持つ新符号が存在することが徐々に明らかになってき
ている（参考文献[5][6]参照）。

【０００４】このように優れた符号が発見される中で、
恒に問題となっていたのは復号法の問題であり、その効
率的な復号アルゴリズムの開発が急がれたが、１９８９
年にJustesenらのグループが一般化Peterson algorithm
（参考文献[7] 参照）を提案するまで、長い間有効な復
号アルゴリズムは全く得られなかった。また、Justesen
らは、与えられた有限の大きさを持つ２次元配列を生成
する、記憶素子数最小の２次元線形帰還シフトレジスタ
を求める効率的なアルゴリズムとして、阪田によって提
案された阪田アルゴリズム（参考文献[8] 参照）を、彼
らの一般化 Peterson algorithm に応用することで、少
ない計算量で高速に誤り位置関数を導出できることを示
した。

【０００５】しかし、一般化Peterson algorithmは、そ
の訂正能力に制約があったために、Skorobogatovらはよ
り高い訂正能力を保証する Modified decoding algorit
hm（参考文献[9] 参照）を提案した。また、阪田アルゴ
リズムには Modified decoding algorithmに対しては直
接関係のない無駄な演算が多く存在したために、神谷ら
は、阪田アルゴリズムを Modified decoding algorithm
に沿った形（参考文献[11][12]参照）に修正したアルゴ
リズムを１９９２年に提案した。

【０００６】一方、従来用いられているＲＳ符号やＢＣ
Ｈ符号の復号法として、Peterson法と、バーレカンプ・
マッセイ（ＢＭ）法及びユークリッド（Ｅｕ）法がよく
知られている。前述の一般化 Peterson algorithm はＲ
Ｓ符号の復号に用いられるPeterson法の拡張になってい
る。また阪田アルゴリズムは２次元ＢＭ法とも呼ばれ、
ＲＳ符号の復号に用いられるＢＭ法（以後、１次元ＢＭ
法と呼ぶ）の拡張になっていることが知られている。

【０００７】

【発明が解決しようとしている課題】しかしながら、Ｒ
Ｓ符号の復号に用いられるＥｕ法（以後、１次元Ｅｕ法
と呼ぶ）の拡張に相当するアルゴリズムは、これまでに
考えられていなかった。

【０００８】また、阪田は、２次元ＢＭ法の拡張として
多次元ＢＭ法（参考文献[13]参照）も提案したが、それ
に対応する多次元Ｅｕ法もまた、考案されていなかっ
た。

【０００９】そこで、本発明では、１次元Ｅｕ法の拡張
に相当する２次元Ｅｕ法を提案し、更に、この２次元Ｅ
ｕ法を拡張して、多次元ＢＭ法に対応する多次元Ｅｕ法
を提案することを目的とする。

【００１０】

【課題を解決するための手段】上記課題を解決するため
に、本発明では、与えられた多次元配列を生成する最小
多項式系を求める多項式系導出装置に、求める第１の多
項式系を記憶するための第１多項式記憶手段と、当該第
１の多項式系と異なる第２の多項式系を記憶するための
第２多項式記憶手段と、前記第１及び第２の多項式記憶
手段に初期値を設定する設定手段と、前記第２多項式記
憶手段に記憶された第２の多項式系の所定の次数の係数
から得られる値を用いて、前記第１多項式記憶手段に記
憶された第１の多項式系を更新する第１更新手段と、前
記第２多項式記憶手段に記憶された第２の多項式系を更
新する第２更新手段とを具える。

【００１１】

【作用】設定手段により、求める第１の多項式系を記憶
するための第１多項式記憶手段及び当該第１の多項式系
と異なる第２の多項式系を記憶するための第２多項式記
憶手段に初期値を設定し、前記第２多項式記憶手段に記
憶された第２の多項式系の所定の次数の係数から得られ
る値を用いて、第１更新手段によって前記第１多項式記
憶手段に記憶された第１の多項式系を更新し、第２更新
手段によって前記第２多項式記憶手段に記憶された第２
の多項式系を更新する。

【００１２】［参考文献］ [1] 今井：“符号理論”，電子情報通信学会 [2]V.D.Goppa: “Codes on algebraic curves ”, Sovi
et Math.Dokl., 24,pp.170-172, 1981. [3]V.D.Goppa: “Algebraico-geometric codes”, Mat
h. U.S.S.R. Izvestiya,vol.21, no.1, pp.75-91, 198
3. [4]V.D.Goppa: “Geometry and Codes”, Kluwer Acade
mic Publishers, 1988. [5]M.A.Tsfasman and S.G.Vladut: “Algebraic-geomet
ric codes ”, KluwerAcademic Publishers, 1991. [6] 三浦：“ある平面曲線上の代数曲線符号”, Prepri
nt. [7]J.Justesen, K.J.Larsen, E.Jensen, A.Havemose an
d T.Hoholdt:“Construction and decoding of a class
of algebraic geometry codes”,IEEE Trans.Inform.T
heory, vol.35, no.4, pp.811-821, July 1989. [8] 阪田：“与えられた２次元配列を生成する２次元線
形帰還シフトレジスタの合成”，信学論（Ａ），vol.J-
70A, pp.903-910, 1987. [9]A.N.Skorobogatov and S.G.Vladut: “On the decod
ing of algebraicgeometric codes”, IEEE Trans.Info
rm.Theory, vol.36, no.5, pp.1051-1060, Sep. 1990. [10]三浦：“代数曲線符号の一般的な復号法(1),(2)
”，信学技法，vol.IT89,no.452, IT89-91,92, pp.61-
70, pp.71-80, 1990. [11]神谷，三浦：“ある種の代数曲線符号に関する Mod
ified decodingalgorithmへの Sakata algorithm の応
用について”，信学技法， vol.IT91, no.435, IT91-9
6, pp.47-54, 1992. [12]神谷，三浦：“ある種の代数曲線符号に関する再帰
的な復号アルゴリズム”，信学技法， vol.IT91, no.50
5, IT91-116, pp.89-96, 1992. [13]S.Sakata: “Extension of the Berlekamp-Massey
algorithm to Ndimensions”,Information and Computa
tion, vol.84, pp.207-239, 1990

【００１３】

【実施例】

［説明の概要］以下では、まず１次元Ｅｕ法の拡張に相
当する２次元Ｅｕ法を提案する。

【００１４】そして、この２次元Ｅｕ法が、２次元ＢＭ
法である阪田アルゴリズムやその修正アルゴリズムであ
る神谷アルゴリズムと等価な結果を出力することを示
す。更に、２次元Ｅｕ法を拡張し、多次元ＢＭ法に対応
する多次元Ｅｕ法を提案する。そして、本発明による多
次元Ｅｕ法が、装置化や高速化において、従来の多次元
ＢＭ法と異なる効果をもつアルゴリズムであることも示
し、その違いを明らかにする。

【００１５】従来知られた多次元ＢＭ法のアルゴリズム
は、図２に示す構造を持つ。一方、本発明による多次元
Ｅｕ法のアルゴリズムは、図３に示す構造を持つ。多次
元ＢＭ法と多次元Ｅｕ法の違いは、前者がステップＳ２
２においてｄf_n ⁽ⁱ⁾ を直接計算し、ステップＳ２５にお
いてその値を用いて多項式系Ｆを更新するのに対し、後
者では、ｄf_n ⁽ⁱ⁾ を直接計算せず、新たに導入した多項
式系Ｂに属する多項式の最高次係数ｄ_i を用いて、ステ
ップＳ３４において多項式系Ｂを更新し、ステップＳ３
５において多項式系Ｆを更新する点である。

【００１６】上記従来の多次元ＢＭ法が、与えられた多
次元配列ｕを生成する最小多項式系Ｆを導くことは、前
記文献[8] ，[13]に証明されている。よって、ここでは
本発明による多次元Ｅｕ法が、多次元ＢＭ法と同じ多項
式系Ｆを導くことを以下に示す定理１〜定理３により証
明することによって、図３の多次元Ｅｕ法から得られる
多項式系Ｆも、与えられた多次元配列ｕを生成する最小
多項式系であることを示す。以下、従来知られた２次元
ＢＭ法及び多次元ＢＭ法を例にとり、本発明による多次
元Ｅｕ法を具体的に説明する。

【００１７】［実施例１］まず、以下の準備（用語の説
明）の後に、阪田アルゴリズムを示す。このアルゴリズ
ムが、与えられた有限２次元配列ｕを生成する、記憶素
子数最小の２次元線形帰還シフトレジスタを合成する多
項式系Ｆを導出することの証明は、前記文献[8] になさ
れているので省略する。

【００１８】準備１（詳細は文献[8] 参考）： Σ：あらゆる非負整数ｎ1 ，ｎ2 の対ｎ＝（ｎ1 ，ｎ2
）の集合。

【００１９】ｎ：点と呼ばれ、Ｘ−Ｙ平面上の座標（ｎ
1 ，ｎ2 ）を持つ点と同一視される。

【００２０】＜_T ：全順序と呼ばれ、Σ上の点ｎの大小
関係を定める。ここでは、点ｎ＝（ｎ1 ，ｎ2 ）に対
し、＜_T に関する次の点を以下のように定める。

【００２１】 ｎ＋１：＝（ｎ1 −１，ｎ2 ＋１） （ｎ1 ＞０のとき） ：＝（ｎ2 ＋１，０） （ｎ1 ＝０のとき） ＜_p ：半順序と呼ばれ、次のように定義される。

【００２２】ｍ1 ≦ｎ1 ，ｍ2 ≦ｎ2 のとき、かつその
ときに限ってｍ≦_p ｎ。

【００２３】ｍ＜_p ｎはｍ≦_p ｎかつｍ≠ｎを意味す
る。

【００２４】Σ_t ^p：＝｛ｍ∈Σ｜ｔ≦_p ｍ，ｍ＜_T ｐ｝ ｕ：ｕは大きさｑの有限部分２次元配列であり、Σ₀ ^qか
ら体Ｋへの写像として定義される。

【００２５】Ｆ：体Ｋ上の２変数多項式を

【００２６】

【外１】

【００２７】とする。

【００２８】ただし、ｚ^m ＝ｘ^m1・ ｙ^m2，Γf ＝｛ｍ∈
Σ｜ｆm ≠０｝，ｓ＝ＬＰ（ｆ) ＝max ｛ｍ｜ｍ∈Γf
｝ 多項式の組をＦ＝｛ｆ⁽⁰⁾,…, ｆ^(l-1) ｝と表す。

【００２９】ｄf_n ⁽ⁱ⁾ ：Σ上の点ｎから体Ｋへの写像を
ｕn とすると、ＬＰ( ｆ(i))＝ｓ(i) なる多項式ｆ(i)
に対し、

【００３０】

【外２】

【００３１】とする。

【００３２】Ｖ（ｕ) ：ｐ≦_T ｑに対するｕn の集合を
ｕ^p ＝｛ｕn ｜ｎ∈Σ₀ ^p｝とするとき、ｕ^p に対してｄ
f_n ⁽ⁱ⁾ ＝０（０≦ｎ＜ｐ）であれば、ｆ[ ｕp]＝０と表
す。このとき、Ｖ( ｕp)＝｛ｆは多項式｜ｆ[ ｕ^p]＝
０｝とする。

【００３３】定義点：多項式の組Ｆが与えられた２次元
配列を生成することができる極小な多項式系であると
き、ＬＰ( ｆ(i))＝ｓ(i) を定義点と呼ぶ。ただし、極
小な多項式系とは次の条件を満たすものである。

【００３４】ｉ）Ｆ⊆Ｖ( ｕ^p) ii）１≦ｉ，ｊ≦ｌかつｉ≠ｊかつＬＰ( ｆ⁽ⁱ⁾)≧_p Ｌ
Ｐ( ｆ^(j))となるｉ，ｊは存在しない。

【００３５】iii)ｇ∈Ｖ( ｕ) かつＬＰ( ｇ) ∈△_Fと
なる多項式ｇは存在しない。

【００３６】ただし、

【００３７】

【外３】

【００３８】△：上の条件を満たすときの△_F。次のよ
うにして求められる。

【００３９】△＝∪△q-s。， q,s ∈Σ₀ ^p ただし、ｄf_q≠０かつＬＰ( ｆ) ＝ｓとなるｆ∈Ｖ( ｕ
^q)が存在するとき △^q-s ＝｛ｍ∈Σ｜ｍ≦_p ｑ−ｓ｝、そうでなければ△
^q-s ＝¢。

【００４０】ｈ1 ：型＜ｉ，ｊ＞のｈ1 を次のように定
義する。

【００４１】ｈ1 ＝ｚ^r-s(i)・ ｆ⁽ⁱ⁾ −( ｄ_i/ｄ_j)・ ｚ
^r-n+m-t(j)・ ｇ(j) ただし、ｒ＝（ｒ1 ，ｒ2 ），ｒ1 ＝max ｛ｓ1⁽ⁱ⁾，ｎ
1 −ｓ1^(j)＋１｝，ｒ2 ＝max ｛ｓ2⁽ⁱ⁾，ｎ2 −ｓ2
^(j+1)＋１｝，ｔ^(j) ＝ＬＰ(g^(j))，f⁽ⁱ⁾∈Ｖ( ｕⁿ)，g
^(j)∈Ｖ( ｕ^m)，ｄ_i ＝ｄf_n ⁽ⁱ⁾ ，ｄ_j ＝ｄg_m ^(j) 。 Ｇ：Ｆの補助多項式系と呼ばれ、Ｇ＝｛ｇ⁽⁰⁾,…, ｇ
^(l-2) ｝なる多項式の組。

【００４２】補題１：で定まる型のｊは、ＬＰ( ｆ
^(j))＝ｓ^(j) かつｐ−ｓ⁽ⁱ⁾ ≦_p （ｓ1^{( j)}−１，ｓ2
^(j+1)−１）となるｊである。

【００４３】補題２：で定まる型のｋは、ＬＰ( ｆ
^(k))＜_p ｔとなるｋである。

【００４４】阪田アルゴリズム １）ｎ＝（０，０），Ｆ＝｛１｝，Ｇ＝¢ ２）Ｆの全ての多項式に対してｄf_n ⁽ⁱ⁾ を計算する。

【００４５】３）もしｄf_n ⁽ⁱ⁾ ≠０ となるｆ⁽ⁱ⁾ があ
れば、新しい△と定義点ｔを定める。 ４）そのあらゆる定義点ｔにおいて以下の手続きを実行
する。

【００４６】ｔ＝（ｓ1⁽ⁱ⁾，ｓ2⁽ⁱ⁾）→補題１の多項
式ｈ1 を作る。

【００４７】ｔ＝（ｎ1 −ｓ1⁽ⁱ⁾＋１，ｎ2 −ｓ2
⁽ⁱ⁺¹⁾＋１）→補題２の型＜ｋ, ｉ＞のｈ1 を作る。

【００４８】ｔ＝（ｎ1 −ｓ1⁽ⁱ⁾＋１，ｓ2^(j)）, １
≦ｉ≦ｌ- １→型＜ｊ, ｉ＞のｈ1 を作る。

【００４９】ｔ＝（ｓ1⁽ⁱ⁾，ｎ2 −ｓ2^(j)＋１）, ２
≦ｊ≦ｌ→型＜ｉ, ｊ- １＞のｈ1 を作る。

【００５０】ｔ＝（ｎ1 ＋１，ｓ2^(j)）→ｈ1 ＝ｘ
^n1-s1(j)+1・ ｆ^(j) ｔ＝（ｓ1⁽ⁱ⁾，ｎ2 ＋１）→ｈ1 ＝ｙ^n2-s2(i)+1・ ｆ
⁽ⁱ⁾ Ｆからｄf_n ⁽ⁱ⁾ ≠０の全ての多項式を除去し、新しく求
めたｈ1 を全てＦに挿入する。

【００５１】５）△が変化した場合、新しいＦの補助多
項式系Ｇの多項式を旧のＧと除去したＦの多項式の中か
ら選び出す。

【００５２】６）ｎ＝ｎ＋１；ｎ＝ｐならば終了；さも
なければ２）へ 以下に、阪田アルゴリズムと同じ出力を導出する、本発
明による新しいアルゴリズムを示す。

【００５３】アルゴリズム１ １）ｎ＝（０，０），Ｆ＝｛１｝，Ｇ＝¢，Ａ＝｛ｘ-
1｝，Ｂ＝｛ｕ｝ ２）Ｂの全ての多項式の最高次係数が０でなければ、新
しい△と定義点ｔを定める。

【００５４】３）そのあらゆる定義点ｔにおいて以下の
手続きを実行する。

【００５５】ｔ＝（ｓ1⁽ⁱ⁾，ｓ2⁽ⁱ⁾）→補題１の型を
もつ多項式ｈ2 を作る。

【００５６】ｔ＝（ｎ1 −ｓ1⁽ⁱ⁾＋１，ｎ2 −ｓ2
⁽ⁱ⁺¹⁾＋１）→補題２の型＜ｋ, ｉ＞のｈ2 を作る。

【００５７】ｔ＝（ｎ1 −ｓ1⁽ⁱ⁾＋１，ｓ2^(j)）, １
≦ｉ≦ｌ- １→型＜ｊ, ｉ＞のｈ2 を作る。

【００５８】ｔ＝（ｓ1⁽ⁱ⁾，ｎ2 −ｓ2^(j)＋１）, ２
≦ｊ≦ｌ→型＜ｉ, ｊ- １＞のｈ2 を作る。

【００５９】ｔ＝（ｎ1 ＋１，ｓ2^(j)）→ｈ2 ＝ｘ
^{-(n1-s1(j)+1)}・ｂ^(j) ｔ＝（ｓ1⁽ⁱ⁾，ｎ2 ＋１）→ｈ2 ＝ｙ^n2-s2(i)+1・ ｂ
⁽ⁱ⁾ Ｂから最高次係数が０でない全ての多項式を除去し、新
しく求めたｈ2 を全てＢに挿入する。

【００６０】４）３）で決定された型の多項式ｈ1 を作
る。また、ＦからＢの除去した多項式に対応する多項式
を除去し、新しく求めたｈ1 をＦに挿入する。

【００６１】５）△が変化した場合、新しいＦの補助多
項式系Ｇの多項式を旧のＧと除去したＦの多項式の中か
ら選び出す。また、新しいＢの補助多項式系Ａの多項式
を旧のＡと除去したＢの多項式の中から選び出す。

【００６２】６）ｎ＝ｎ＋１；ｎ＝ｐならば終了；さも
なければ２）へ ただし、 Ａ，Ｂ：Ａ＝｛ａ⁽⁰⁾,…, ａ^(l-2) ｝，Ｂ＝｛ｂ⁽⁰⁾,
…, ｂ^(l-1) ｝となる多項式の組。

【００６３】ｈ2 ：型＜ｉ，ｊ＞のｈ2 を次のように定
義する。

【００６４】ｈ2 ＝ｚ^r-s(i)・ ｂ(i) −( ｄ_i/ｄ_j)・ ｚ
^r-n+m-t(j)・ ａ(j) アルゴリズム１と阪田アルゴリズムの大きな違いは、阪
田アルゴリズムがｄf_n ⁽ⁱ⁾ を直接計算し、それが全て０
であるかどうかを検査するのに対し、アルゴリズム１は
ｄf_n ⁽ⁱ⁾ を直接計算せず、Ｂに属す多項式ｂ⁽ⁱ⁾ の最高
次係数が０であるかどうかを検査することであり、その
ためにアルゴリズム１は阪田アルゴリズムにない多項式
の組Ａ，Ｂを導入している。

【００６５】アルゴリズム１によって得られるＦと阪田
アルゴリズムによって得られるＦが同じ多項式系である
ことは次のようにして証明できる。

【００６６】定理１ 式（１）のように定義したｕn （ｎ∈Σ0p）を係数とす
る多項式ｕとＬＰ( )＝ｓである多項式ｆの積多項式を
ｂとするとき、多項式ｂのｚ^v-n+s 次の係数ｂv-n+s は
式（２）のようになる。ただし、ｖは任意の整数。

【００６７】 証明：式（１）から

【００６８】

【外４】

【００６９】である。

【００７０】よって、多項式ｂのｚ^v-n+s の係数ｂv-n+
s はｖ−ｉ＋ｍ＝ｖ−ｎ＋ｓよりｉ＝ｍ＋ｎ−ｓとなる
ので、式（２）のようになる。

【００７１】（証明終了）この定理からｆ(i) ∈Ｆに対
応するｂ(i) ＝ｆ⁽ⁱ⁾・ｕのｚ^v-n+s の係数は阪田アルゴ
リズムのｄf_n ⁽ⁱ⁾ となっていることがわかる。

【００７２】また、Ｖ( ｕⁿ)である多項式ｆ⁽ⁱ⁾ をｆ_n
⁽ⁱ⁾と表すと次の定理が成り立つ。

【００７３】定理２：式（３），（４）によって更新さ
れる多項式をｌ_q ^(k)，ｃ_q ^(k)とする（ｑ＞_Tｎ＞_T
ｍ）。また、多項式ｗ_q ^(k)を式（５）のように定義する
と、ｗ_q ^(k)は式（６）によって更新できる。ただし、ｒ
ｓ，ｒｔは任意の整数。また、ｌ_n ⁽ⁱ⁾，ｌ_m ^(j)及びｃ_n
⁽ⁱ⁾，ｃ_m ^(j)の初期値は任意の多項式。

【００７４】 ｌ_q ^(k)＝ｚ^rs・ ｌ_n ⁽ⁱ⁾−( ｄ_i ／ｄ_j)・ ｚ^rt・ ｌ_m ^(j) （３） ｃ_q ^(k)＝ｚ^rs・ ｃ_n ⁽ⁱ⁾−( ｄ_i ／ｄ_j)・ ｚ^rt・ ｃ_m ^(j) （４） ｗ_q ^(k)＝ｌ_q ^(k)・ ｅ−ｃ_q ^(k)・ ｄ （ｄ，ｅは任意の多項式） （５） ｗ_q ^(k)＝ｚ^rs・ ｗ_n ⁽ⁱ⁾−( ｄ_i ／ｄ_j)・ ｚ^rt・ ｗ_m ^(j) （６） 証明：式（６）は任意のｑ及びｋに対して成り立つの
で、次が成り立つ。

【００７５】ｗ_n ⁽ⁱ⁾＝ｌ_n ⁽ⁱ⁾・ ｅ−ｃ_n ⁽ⁱ⁾・ ｄ ｗ_m ^(j)＝ｌ_m ^(j)・ ｅ−ｃ_m ^(j)・ ｄ 従って、次が言える。

【００７６】ｗ_q ^(k)＝ｌ_q ^(k)・ ｅ−ｃ_q ^(k)・ ｄ ＝（ｚ^rs・ ｌ_n ⁽ⁱ⁾−( ｄ_i ／ｄ_j)・ ｚ^rt・ ｌ_m ^(j)）・ ｅ −（ｚ^rs・ ｃn(j)−( ｄ_i ／ｄ_j)・ ｚ^rt・ ｃ_m ^(j)）・ ｄ ＝ ｚ^rs・ ｗ_n ⁽ⁱ⁾−( ｄ_i ／ｄ_j)・ ｚ^rt・ ｗ_m ^(j) （証明終了）阪田アルゴリズムにおいて、Ｖ( ｕ^q)とな
るｆ^(k) ＝ｆ_q ^(k)∈Ｆはｈ1 によって更新され、ｇ^(j)
はＶ( ｕ^m)となるｆ^(j) ＝ｆ_m ^(j)であるので、ｈ1 は式
（３）の形式で表現できる。

【００７７】また、次の定理が成立する。

【００７８】定理３：式（５）において、ｌ_q ^(k)＝ｆ_q
^(k)，ｅ＝ｕ，ｄ＝ｚ^v・ｘ、及びｃ_-1 ^(j) ＝１，ｃ₀ ⁽ⁱ⁾
＝０とすると、deg ｗ_q ^(k)≦ｖにおいてｗ_q ^(k)＝ｂ_q ^(k)
である。このとき、ｂ_q ^(k)はｖ−ｑ＋ｓ^(k) 次の多項式
である。

【００７９】証明：ｌ_q ^(k)＝ｆ_q ^(k)，ｅ＝ｕより、式
（５）はｗ_q ^(k)＝ｂ_q ^(k)−ｃ_q ^(k)・ ｄとなる。また、de
g ｃ_-1 ^(j) ≦０，deg ｃ₀ ⁽ⁱ⁾≦０であれば式（４）より
ｃ_q ^(k)は正の次数の多項式であり、ｄ＝ｚ^v・ｘであるの
でdeg ｃ_q ^(k)・ ｄ＞ｖである。よって、deg ｗ_q ^(k)≦ｖ
においてｗ_q ^(k)＝ｂ_q ^(k)である。

【００８０】また、定義からｂ_q ^(k)＝ｕ・ ｆ_q ^(k)の最高
次数はｖ＋ｓ^(k) であるが、このときのｆ_q ^(k)はｆ_q ^(k)
∈Ｖ（ｕq ）であるのでｄf_i ^(k) ＝０(i=0, …,q-1) で
ある。定理１からｄf_i ^(k) はｂ_q ^(k)のｚ^v-i+s(k)の係数
であるので、ｂ_q ^(k)のｖ−ｉ＋ｓ^(k) 次(i=0, …,q-1)
の係数は０になり、ｂ_q ^(k)の最高次数はｖ−ｑ＋ｓ^(k)
になる。

【００８１】（証明終了）従って、ｂ_q ^(k)＝ｗ_q ^(k)は式
（６）によって更新できる。即ち、ｂ_q ^(k)はｈ2によっ
て更新できる。この場合、定理１，定理３からｄ_i ，ｄ
_j は各々多項式ｂ_n ⁽ⁱ⁾，ｂ_m ^(k)のｚ^v-n+s(i)，ｚ
^v-m+s(j)の係数、即ち、最高次係数である。

【００８２】以上から、アルゴリズム１によって得られ
るＦと阪田アルゴリズムによって得られるＦが同じ多項
式系であることが証明された。阪田アルゴリズムによっ
て得られる多項式系Ｆは与えられた２次元配列ｕを生成
する最小多項式系であることが文献[8] によって証明さ
れているので、アルゴリズム１から得られる多項式系Ｆ
も与えられた２次元配列ｕを生成する最小多項式系であ
ることがいえる。

【００８３】よって、このアルゴリズムは例えば図１の
ような装置によって実現できる。まず、アルゴリズム１
の１）で設定されている初期値及びその更新値を記憶す
るメモリと、そこに格納されたＢの多項式の最高次係数
が０であるかどうかを判断し、０であれば６）を実行
し、０でなければ新しい定義点を計算し型を判断する
２）を実行する制御回路１１と、その型に従って３），
４）に示されたｈ2 ，ｈ1の演算を行う処理回路１２に
よって実現できる。また、制御回路１１は定義点が更新
されていればメモリ１３中のＡ，Ｇの多項式を５）に示
されるように新しく選択・更新する。

【００８４】ただし、制御回路１１と処理回路１２は、
各種制御手順及び前記アルゴリズムに対応するプログラ
ムをＣＰＵに実行させることによりソフトウェア的に実
現することもできるので、分離してある必要はない。ま
た、制御・処理において必要な演算は簡単な整数の乗除
算と加減算であるので、特殊な回路・処理は必要としな
い。また、制御における型の判定及び手順の流れは、予
めプログラミングしておいたりＲＯＭに焼き付けておい
て、必要なときに検索（テーブル・ルックアップ）すれ
ば簡単である。

【００８５】また、ｈ1 とｈ2 は同時に実行することが
できるので処理回路をｈ1 とｈ2 独立に持つこともでき
る。また、ｈ1 とｈ2 は同様の処理であるので１つの回
路によって実行することしてもよい。また、効果の所で
後述するように本アルゴリズムの特徴は並列処理のしや
すさであるので、処理回路は１つである必要はない。以
上から、アルゴリズム１を実行する回路は簡単に実現す
ることができることがわかる。

【００８６】［実施例２］次に神谷らに示された Modif
ied decoding algorithm に適したアルゴリズムと等価
なアルゴリズムを考える。まず、以下の準備の後に、神
谷らによって示されたアルゴリズムを示す。ただし、以
下の準備において述べられていない部分は実施例１の場
合と同じである。

【００８７】準備２（詳細は文献[12]参照）： ＜_T ：ここでは全順序は次のように定める。

【００８８】Ｑ（ｉ）＝ａ・ ｉ1 ＋ｂ・ ｉ2 （ａ，ｂ
は互いに素な自然数，ｉ＝（ｉ1 ，ｉ2 ）） Ｑ（ｍ）＜Ｑ（ｎ）が満たされるか、Ｑ（ｍ）＝Ｑ
（ｎ）かつｍ2 ≦ｎ2 の時に限って、ｍ≦_T ｎとし、こ
の全順序＜_T に関してｍの次の点をｍ＋１と表す。

【００８９】Σ_t ^p(n) ：＝｛ｍ∈Σ｜ｍ2 ≦ｎ，ｔ≦_p
ｍ，ｍ＜_T ｐ｝ ｕ ：ｕは大きさｑの有限部分２次元配列であり、Σ₀ ^q
(2・(a-1)) から体Ｋへの写像として定義される。

【００９０】Ｆ ：体Ｋ上の２変数多項式を

【００９１】

【外５】

【００９２】とする。

【００９３】ただし、ｚ^m ＝ｘ^m1・ ｙ^m2，Γf ＝｛ｍ∈
Σ(a-1) ｜ｆm ≠０｝，ｓ＝ＬＰ( ｆ) ＝max ｛ｍ｜ｍ
∈Γf ｝ 多項式の組をＦ＝｛ｆ⁽⁰⁾,…, ｆ^(a-1) ｝と表す。

【００９４】Ｖ( ｕ) ：Ｑ( ｐ) ＜ｑに対するｕn の集
合をｕ^p ＝｛ｕn ｜ｎ∈Σ₀ ^p(2・(a-1)) ｝とするとき、
ｕ^p に対してｄf_n ⁽ⁱ⁾ ＝０（ｎ∈Σ_s ^p(a-1+s2)）であれ
ば、ｆ[ ｕ^p]＝０と表す。このとき、Ｖ( ｕ^p)＝｛ｆは
多項式｜ｆ[ ｕp]＝０｝とする。

【００９５】△ ：△は次のようにして求められる。

【００９６】△＝∪△^q-s q,s∈Σ₀ ^p(2・(a-1)) ただし、ｄf_q≠０かつＬＰ( ｆ) ＝ｓとなるｆ∈Ｖ( ｕ
^q)が存在するとき△^q-s ＝｛ｍ∈Σ(a-1) ｜ｍ1 ≦ｑ1
−ｓ1 ，ｍ2 ＝ｑ2 −ｓ2 ｝、そうでなければ△^q-s ＝
¢。

【００９７】ｈ3 ：型＜ｉ，ｊ＞のｈ3 を次のよう
に定義する。

【００９８】ｈ3 ＝ｘ^r1-s1(i)・ ｆ⁽ⁱ⁾ −( ｄ_i/ｄ_j)・
ｘ^{r1-n1+m1-t1(j)}・ ｇ^（ｊ） Ｇ：Ｆの補助多項式系と呼ばれ、Ｇ＝｛ｇ^（０），…,
ｇ^(a-1) ｝なる多項式の組。 神谷アルゴリズム １）ｎ＝（０，０），Ｆ＝｛１，ｙ，ｙ² ，…，ｙ
^a-1 ｝，Ｇ＝¢ ２）Ｆの全ての多項式に対してｄf_n ⁽ⁱ⁾ を計算する。

【００９９】３）もしｄf_n ⁽ⁱ⁾ ≠０ となるｆ⁽ⁱ⁾ があ
れば、新しい△と定義点ｔを定める。 ４）そのあらゆる定義点ｔにおいて以下の手続きを実行
する。

【０１００】ｔ＝（ｓ1⁽ⁱ⁾，ｓ2⁽ⁱ⁾）→型＜ｉ，ｎ2 −
ｉ＞のｈ3 を作る。

【０１０１】ｔ＝（ｎ1 −ｓ1⁽ⁱ⁾＋１，ｎ2 −ｓ2⁽ⁱ⁾）
→型＜ｎ2 −ｉ，ｉ＞のｈ3 を作る。

【０１０２】ｔ＝（ｎ1 ＋１，ｎ2 −ｓ2⁽ⁱ⁾）→ｈ3 ＝
ｘ^{n1-s1(n2-i)+1}・ｆ^(n2-i) Ｆからｄf_n ⁽ⁱ⁾ ≠０の全ての多項式を除去し、新しく求
めたｈ3 を全てＦに挿入する。

【０１０３】５）△が変化した場合、新しいＦの補助多
項式系Ｇの多項式を旧のＧと除去したＦの多項式の中か
ら選び出す。

【０１０４】６）ｎ＝ｎ＋１；ｎ＝ｐならば終了；さも
なければ２）へ 神谷アルゴリズムと等価なアルゴリズムを以下に示す。

【０１０５】アルゴリズム２ １）ｎ＝（０，０），Ｆ＝｛１，ｙ，…，ｙ^a-1 ｝，Ｇ
＝¢，Ａ＝｛ｘ-1｝，Ｂ＝｛ｕ｝ ２）Ｂの全ての多項式の最高次係数が０でなければ、新
しい△と定義点ｔを定める。

【０１０６】３）そのあらゆる定義点ｔにおいて以下の
手続きを実行する。

【０１０７】ｔ＝（ｓ1⁽ⁱ⁾，ｓ2⁽ⁱ⁾）→型＜ｉ，ｎ2
−ｉ＞のｈ4 を作る。

【０１０８】ｔ＝（ｎ1 −ｓ1⁽ⁱ⁾＋１，ｎ2 −ｓ
2⁽ⁱ⁾）→型＜ｎ2 −ｉ，ｉ＞のｈ4 を作る。

【０１０９】ｔ＝（ｎ1 ＋１，ｎ2 −ｓ2⁽ⁱ⁾）→ｈ4
＝ｘ^{s1(n2-i)-n1-1}・ｆ^(n2-i)Ｂから最高次係数が０でな
い全ての多項式を除去し、新しく求めたｈ4 を全てＢに
挿入する。

【０１１０】４）３）で決定された型の多項式ｈ3 を作
る。また、ＦからＢの除去した多項式に対応する多項式
を除去し、新しく求めたｈ3 をＦに挿入する。

【０１１１】５）△が変化した場合、新しいＦの補助多
項式系Ｇの多項式を旧のＧと除去したＦの多項式の中か
ら選び出す。また、新しいＢの補助多項式系Ａの多項式
を旧のＡと除去したＢの多項式の中から選び出す。

【０１１２】６）ｎ＝ｎ＋１；ｎ＝ｐならば終了；さも
なければ２）へ ただし、 ｈ4 ：型＜ｉ，ｊ＞のｈ4 を次のように定義する。

【０１１３】ｈ4 ＝ｘ^r1-s1(i)・ ｂ⁽ⁱ⁾ −( ｄ_i/ｄ_j)・
ｘ^{r1-n1+m1-t1(j)}・ ａ^(j) アルゴリズム２と神谷アルゴリズムの違いも、アルゴリ
ズム１と阪田アルゴリズムの違いと同様にｄf_n ⁽ⁱ⁾ を直
接計算するか、Ｂに属す多項式ｂ(i) の最高次係数とす
るかである。従って、アルゴリズム１と阪田アルゴリズ
ムの間で成り立った関係が、アルゴリズム２と神谷アル
ゴリズムの間で成立すればアルゴリズム２によって得ら
れるＦと神谷アルゴリズムによって得られるＦが同じ多
項式系であることが証明できる。よって、次のようにな
る。

【０１１４】定理１のｆ⁽ⁱ⁾ ∈Ｆを神谷アルゴリズムの
ｆ⁽ⁱ⁾ とすれば、それに対応する多項式ｂ⁽ⁱ⁾ ＝ｆ⁽ⁱ⁾・
ｕのｚ^v-n+s の係数は神谷アルゴリズムのｄf_n ⁽ⁱ⁾ とな
っていることがいえる。よって、定理１はこの実施例に
おいても成立する。

【０１１５】定理２は一般的に成立する。

【０１１６】定理３のｆ_q ^(k)は神谷アルゴリズムのｆ
⁽ⁱ⁾ であるので、定理３も同様に成立する。

【０１１７】従って、阪田アルゴリズムの場合と同様に
ｗ_q ^(k)＝ｂ_q ^(k)であることがいえるので、ｂ_q ^(k)はｈ4
によって更新できる。この場合も、定理１からｄ_i ，ｄ
_j は各々多項式ｂ_n ⁽ⁱ⁾，ｂ_m ^(k)の最高次数の係数であ
る。

【０１１８】以上から、アルゴリズム２によって得られ
るＦと神谷アルゴリズムによって得られるＦが同じ多項
式系であることが証明された。

【０１１９】よって、アルゴリズム２も図１のような装
置によって実現できる。ただし、制御及び処理はアルゴ
リズム１と異なる。（処理はｈ3 ，ｈ4 の演算を行い、
制御は型の判定が簡単化されている。また、メモリ部も
Ａ，Ｂ，Ｆ，Ｇの初期値も１）に示された多項式が設定
される。）また、アルゴリズム２も並列処理に適してい
るので、処理回路は１つである必要はない。以上から、
アルゴリズム２を実行する回路も簡単に実現することが
できることがわかる。

【０１２０】［実施例３］多次元配列を生成する記憶素
子数最小の多次元シフトレジスタを合成する多項式系Ｆ
を導出するアルゴリズムもまた、阪田によって示されて
いる[13]。このアルゴリズムは多次元ＢＭ法と呼ばれて
おり、ここでは、多次元ＢＭ法に対応する新しいアルゴ
リズムを考える。

【０１２１】詳細なアルゴリズムは煩雑であるので、Ｂ
Ｍ法と呼ばれるアルゴリズムの特徴を図で示す。１次元
のＢＭ法を含め、その拡張である阪田によって提案され
たアルゴリズム（多次元ＢＭ法）は図２のような構成を
持っている。それに対応するアルゴリズムは図３のよう
になる。図２と図３の違いも前述の２つの実施例と同様
に、ｄf_n ⁽ⁱ⁾ を直接計算するか、Ｂに属す多項式ｂ⁽ⁱ⁾
の最高次係数とするかである。従って、定理１〜３が多
次元配列においても成立すれば、図２の多次元ＢＭ法に
よって得られるＦと図３のアルゴリズムによって得られ
るＦが同じ多項式系であることが証明できる。

【０１２２】前述の実施例において点はｎ＝（ｎ1 ，ｎ
2 ）となる２次元空間上で定義され、配列及び多項式の
各係数はその点における写像である。これをＮ次元空間
に拡張した場合、点はｎ＝（ｎ1 ，ｎ2 ，…，ｎN ）と
定義され、配列及び多項式もその点における写像にな
り、その関係は次元を問わず同じである。従って、Ｎ次
元空間においても定理１〜３は同様に成り立つことは明
らかである。

【０１２３】従って、図３のアルゴリズムから生成され
るＦは図２のアルゴリズムから生成されるＦと同じであ
ることがいえる。よって、図３のアルゴリズムも図１の
ような装置によって簡単に実現できる。

【０１２４】ただし、図３のアルゴリズムは１次元の場
合、前述のＲＳ符号やＢＣＨ符号の復号において用いら
れるＥｕ法と呼ばれるアルゴリズムになる。また、効果
の所で述べるように図３のアルゴリズムは１次元Ｅｕ法
の特徴を失うことなく、多次元へとＥｕ法を拡張してい
る。従って、アルゴリズム１，２を含む図３の構成を持
つアルゴリズムを多次元ＢＭ法に対応して多次元Ｅｕ法
と呼ぶことにする。

【０１２５】［その他の実施例］前述したように１次元
のＢＭ法や１次元のＥｕ法はＲＳ符号やＢＣＨ符号にお
いてよく用いられているので、種々の変形アルゴリズム
が提案されている。よく知られた１次元Ｅｕ法の変形ア
ルゴリズムとして連分数法(L.R.Welch and R.A.Scholt
z: “Continued fractions and Berlekamp's algorith
m,”IEEE Trans.Inf.Theory, IT-25,pp.19-27, Jan.197
9)がある。これは、式（６）の演算を最後まで行わず、
最終結果に関係のない演算を省いた手法である。しか
し、式（６）の形式の演算によってＢを更新しｄf_n ⁽ⁱ⁾
を直接計算しないという点では同じであるので、本方式
は連分数法を含む種々のアルゴリズムの変形に対しても
有効であることは明かである。

【０１２６】また、本方式はアルゴリズム１，２の例か
らもわかるように型の分類の方法に依存しない。従っ
て、本方式は多次元配列に対してＢＭ法のように直接ｄ
f_n ⁽ⁱ⁾を計算せず、式（６）の形式の演算によってＢを
更新し、ｄf_n ⁽ⁱ⁾ をＢの多項式の最高次係数として演算
する手法に対して全て有効である。

【０１２７】また、点や各パラメータ（ｒｓ，ｒｔ等）
は整数とし、ｆ_n ⁽ⁱ⁾及びｂ_n ⁽ⁱ⁾は多項式としているが、
点や各パラメータを任意の複素数、多項式を有理関数等
に拡張しても本方式が有効であることは明かである。

【０１２８】また、多項式ｕやｆの次数を逆（双対多項
式）にすれば、多項式ｂ＝ｆ・ ｕも次数が逆になりｄ_i
を多項式ｂの最低次係数とすることもできる。

【０１２９】また、定理３においてｄ＝ｚ^v・ｘとしてい
るが、ｄ＝ｚ^v+1 またはｄ＝０としてもｗ_q ^(k)＝ｂ_q ^(k)
となり図３の構造を持つアルゴリズムの結果は変わらな
いことは明かである。

【０１３０】また、以上の実施例ではＢの更新のために
次の式（７）のような演算を用いているが、式（８）の
ような演算によっても定数項の違いを除いて同じ結果が
得られる。ただし、ａ_n ^(j)＝ｂ_m ^(j)。

【０１３１】 ｂ_n+1 ^(k)＝ｚ^rs・ ｂ_n ⁽ⁱ⁾−( ｄ_i ／ｄ_j)・ ｚ^rt・ ａ_n ^(j) （７） ｂ_n+1 ^(k)＝ｄ_j・ｚ^rs・ ｂ_n ⁽ⁱ⁾−ｄ_i・ｚ^rt・ ａ_n ^(j) （８） 以上からわかるように、Ｅｕ法とＢＭ法の違いを次のよ
うに表せる。

【０１３２】ＢＭ法：ｄf_n ⁽ⁱ⁾ を直接計算して、その値
を用いてf_n+1 ^(k) を求める。

【０１３３】Ｅｕ法：ｄf_n ⁽ⁱ⁾ を直接計算せず、多項式
ｂ_n ⁽ⁱ⁾とｂ_n ^(j)の最高次の係数ｄ_i,ｄ_j を用いて式
（７）のようにｂ_n+1 ^(k)を求める。また、同じｄ_i,ｄ_j
を用いてf_n+1 ^(k) を計算する。ただし、ａ_n ^(j)＝
ｂ_m ^(j)。

【０１３４】 ｂ_n+1 ^(k)＝ｚ^rs・ｂ_n ⁽ⁱ⁾−（ｄ_i ／ｄ_j ）・ｚ^rt・ａ_n ^(j) （７） この違いから次のような相違点がＢＭ法とＥｕ法の装置
化及び高速化に対して生じる。

【０１３５】ＢＭ法： ＢＭ法はｆ_n ⁽ⁱ⁾とｆ_n+1 ^(k)を並
列に計算することは困難である。なぜならば、ｆ_n+1 ^(k)
を計算するためにはｄf_n ⁽ⁱ⁾ ＝ｄ_i が必要であり、ｄf_n
⁽ⁱ⁾はｆ_n ⁽ⁱ⁾の全ての係数を用いて計算される。従っ
て、ｄf_n ⁽ⁱ⁾ が得られるのはｆ_n ⁽ⁱ⁾の計算が終わった後
であるので、ｆ_n+1 ^(k)の計算はｆ_n ⁽ⁱ⁾の計算が終わった
後でしか始まらない。従って、図４(a) に示すようにＢ
Ｍ法では点ｎとｎ＋１における多項式ｆ_n ⁽ⁱ⁾とｆ_n+1 ^(k)
は逐次的に計算される。さらに、ＢＭ法はｆ_n ⁽ⁱ⁾とｆ
_n+1 ^(k)及びｄf_n ⁽ⁱ⁾ の演算を１クロックで計算したとし
ても、それらが並列に実行されないため図４(b) に示す
ように２ｐクロック程度の計算時間が必要である。これ
は、１次元ＢＭ法から図２に示される多次元ＢＭ法に対
して共通する特徴である。

【０１３６】Ｅｕ法： Ｅｕ法はｆ_n ⁽ⁱ⁾とｆ_n+1 ^(k)を並
列に計算することができる。なぜならば、Ｅｕ法におい
てｄ_i はｂ_n ⁽ⁱ⁾∈Ｂの最高次係数となっており、Ｂに属
す多項式は式（７）によってＢに属す多項式のみによっ
て計算される。ｂ_n ⁽ⁱ⁾とａ_n ^{( j)}を用いて式（７）が最高
次数から下位次数の方へ順次計算されているとすると、
出力ｂ_n+1 ^(k)は最高次係数から下位次係数の方へ順次得
られる。よって、点ｎ＋２における多項式ｂ_n+2 ^(k)はｂ
_n+1 ⁽ⁱ⁾の最高次係数が得られた時点から計算を始めるこ
とができる（ａ_n+1 ^(j)は既に得られている多項式であ
る。）。これは点ｎ＋１とｎ＋２における多項式が並列
に計算できることを示しているが、点ｎとｎ＋１におい
ても同様であることは明かである。従って、Ｂの更新の
ための演算は各点において並列に実行することができ
る。また、ｆ_n+2 ^(k)とｆ_n+1 ^(k)の計算もｂ_n+1 ⁽ⁱ⁾とｂ_n
⁽ⁱ⁾の最高次係数がわかった時点で始めることができる
ので、図５の(a) に示すようにｆ_n+1 ^(k)の演算も各点に
おいて並列に実行できる。よって、Ｅｕ法は式（７）の
演算を行う処理回路を複数用意すれば、その数に比例し
た高速化が容易に行える。これは、よく知られた１次元
Ｅｕ法から図３の多次元Ｅｕ法に対して共通の特徴であ
り、上記のＢＭ法にはない特徴である。また、ｂ_n ⁽ⁱ⁾，
ｂ_n+1 ^(k)及びｆ_n ⁽ⁱ⁾，ｆ_n+1 ^(k)の演算を１クロックで計
算した場合、図５の(b) に示すようにｐクロック程度の
計算時間で良く、ＢＭ法より高速な演算が行える（ただ
し、図５は点ｎにおけるｄ_i をｄ_n と表す。）。

【０１３７】一般的に、高速なアルゴリズムとは計算量
の少ないアルゴリズムを指す場合が多い。しかし、高速
化を実現する場合、アルゴリズムの計算量を減少させる
アプローチとアルゴリズムの並列度を高めるアプローチ
が考えられる。それは並列処理によって複数の処理を同
時に実行すれば処理時間が短縮できるためである。最近
はＶＬＳＩ技術の進歩により大規模な並列処理チップを
容易に実現することができる。よって、並列度の高いア
ルゴリズムの方が高速処理向きである場合も多い。

【０１３８】

【発明の効果】以上説明したように、本発明によるＥｕ
法は、ＢＭ法よりも並列度が高く、高速処理に向いてい
ると言える。また、ＢＭ法が多項式ｆ_n ⁽ⁱ⁾とスカラ量ｄ
f_n ⁽ⁱ⁾という２種類の演算を必要とするのに対して、Ｅ
ｕ法はｆ_n ⁽ⁱ⁾，ｂ_n ⁽ⁱ⁾に対して式（７）に示される同一
形式の演算のみでよいので、処理回路をユニット化しや
すくより並列処理に向いていると言える。

【０１３９】従って、並列処理を用いて装置化する場
合、本発明によれば、簡単に高速な処理装置を構成でき
るという効果がある。

【図面の簡単な説明】

【図１】本発明による多次元配列生成回路である。

【図２】従来のＢＭ法による多次元配列生成アルゴリズ
ムである。

【図３】本発明によるＥｕ法による多次元配列生成アル
ゴリズムである。

【図４】従来のＢＭ法の動作説明図である。

【図５】本発明によるＥｕ法の動作説明図である。

【符号の説明】

１１ 制御回路 １２ 処理回路 １３ メモリ

Claims (7)

【特許請求の範囲】
1. 【請求項１】 与えられた多次元配列を生成する最小多
   項式系を求める多項式系導出装置において、 求める第１の多項式系を記憶するための第１多項式記憶
   手段と、 当該第１の多項式系と異なる第２の多項式系を記憶する
   ための第２多項式記憶手段と、 前記第１及び第２の多項式記憶手段に初期値を設定する
   設定手段と、 前記第２多項式記憶手段に記憶された第２の多項式系の
   所定の次数の係数から得られる値を用いて、前記第１多
   項式記憶手段に記憶された第１の多項式系を更新する第
   １更新手段と、 前記第２多項式記憶手段に記憶された第２の多項式系を
   更新する第２更新手段とを有することを特徴とする多項
   式系導出装置。
2. 【請求項２】 前記第１更新手段による更新動作と前記
   第２更新手段による更新動作とを並列に実行することを
   特徴とする請求項１に記載の多項式系導出装置。
3. 【請求項３】 前記第１更新手段と前記第２更新手段と
   を共通の回路手段によって実現すること特徴とする請求
   項１に記載の多項式系導出装置。
4. 【請求項４】 前記第２更新手段が、ｂ_n ⁽ⁱ⁾、ｂ_m ^(j)を
   前記第２多項式系に属する多項式とし、ｄ_i 、ｄ_j を、
   それぞれ当該多項式ｂ_n ⁽ⁱ⁾，ｂ_m ^(j)の最高または最低次
   の係数として、演算 ｂ_q ^(k)＝ｚ^rs・ ｂ_n ⁽ⁱ⁾−( ｄ_i ／ｄ_j)・ ｚ^rt・ ｂ_m ^(j) を行うことを特徴とする請求項１に記載の多項式系導出
   装置。
5. 【請求項５】 前記第２更新手段が、ｂ_n ⁽ⁱ⁾、ｂ_m ^(j)を
   前記第２多項式系に属する多項式とし、ｄ_i 、ｄ_j を、
   それぞれ当該多項式ｂ_n ⁽ⁱ⁾，ｂ_m ^(j)の最高または最低次
   の係数として、演算 ｂ_q ^(k)＝ｄ_j・ｚ^rs・ ｂ_n ⁽ⁱ⁾−ｄ_i・ｚ^rt・ ｂ_m ^(j) を行うことを特徴とする請求項１に記載の多項式系導出
   装置。
6. 【請求項６】 与えられた多次元配列を生成する最小多
   項式系を求める多項式系導出方法において、 求める第１の多項式系を記憶するための第１メモリと、
   当該第１の多項式系と異なる第２の多項式系を記憶する
   ための第２メモリとに初期値を設定し、 前記第２メモリに記憶された第２の多項式系の所定の次
   数の係数から得られる値を用いて、前記第１メモリに記
   憶された第１の多項式系を更新し、 前記第２メモリに記憶された第２の多項式系を更新する
   ことを特徴とする多項式系導出方法。
7. 【請求項７】 前記第１の多項式系の更新動作と前記第
   ２の多項式系の更新動作とを並列に実行することを特徴
   とする請求項６に記載の多項式系導出方法。