JPH0827732B2

JPH0827732B2 - 線形代数コード復号のためのキー方程式を解く方法

Info

Publication number: JPH0827732B2
Application number: JP3348390A
Authority: JP
Inventors: マーティン・ハスナー; ユー・シュヴィーゲルスホーン; サミュエル・ヴィノグラード
Original assignee: International Business Machines Corp
Current assignee: International Business Machines Corp
Priority date: 1991-01-22
Filing date: 1991-12-05
Publication date: 1996-03-21
Anticipated expiration: 2011-03-21
Also published as: EP0496157A2; JPH0721048A; EP0496157A3; US5428628A; CA2057666A1

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、線形代数コードを復号
するための装置及び方法に関し、さらに具体的には、リ
ード＝ソロモン（ＲＳ）コード復号のためのキー方程式
を解くために従来技術の装置で使用されていた以上の追
加のハードウェアを必要とせずに待ち時間を改善するア
ルゴリズムを使って、上記のキー方程式を解く装置及び
並列計算法に関するものである。

【０００２】

【従来の技術】本発明に最も関係があると考えられる従
来技術の参照文献を以下に示す。［Ａ］Ｅ．Ｒ．バーレカンプ(Berlekamp)、“Algebraic
Coding Theory",McGraw Hill,１７８−１９９頁，１９
６８年。［Ｂ］Ｊ．Ｌ．マッセイ(Massey),“Shift-Register Sy
nthesis and BCH Decoding",IEEE Trans. on IT, IT-1
5, １９６９年１月。［Ｃ］Ｋ．Ｙ．リュー(Liu),“Architecture for VLSI
Design of Reed-Solomon Decoders",IEEE Trans. on Co
mputers,１９８４年２月，１７８−１８９頁。［Ｄ］Ｄ．Ｌ．ホワイティング(Whiting),“Bit-Serial
Reed-Solomon Decoders in VLSI",PhD thesis, Califo
rnia Institute of Technology,１９８４年［Ｅ］Ｒ．Ｔ．チェン(Chien),“Cyclic Decoding Proc
edures for BCH Codes",IEEE Trans. on IT-10,３５７
ー３６３頁、１９６４年１０月。

【０００３】参照文献［Ａ］の１８４頁で、バーレカン
プは、ＲＳコードを復号する際の主要ステップである
「キー方程式」を解くためのアルゴリズムを開示してい
る。本明細書及び特許請求の範囲で使用する場合、「キ
ー方程式」という用語は、所与の一組のエラー・シンド
ロームに関するエラー位置検出多項式及びエラー評価多
項式の係数を決定するために解かなければならない方程
式であると定義される。バーレカンプのアルゴリズム
は、エラー位置検出多項式及びエラー評価多項式の両方
の係数を同時に計算するためのもので、１つの条件付き
分岐条件を有する計算シーケンスから成り、この条件付
き分岐条件は、シーケンスを、以下でＡシーケンス及び
Ｂシーケンスと呼ぶ２つの直線シーケンスに分割する。
エラー状態のｔ個の記号を復号するには、このシーケン
スの２ｔ回の繰返しまたは循環が必要となる。Ａシーケ
ンスは３回の乗算を実行し、Ｂシーケンスは５回の乗算
を実行する。

【０００４】参照文献［Ｂ］で、マッセイは、バーレカ
ンプのアルゴリズムを分割して、最初にエラー位置検出
係数を計算することを提案した。これらの係数は、次に
エラー評価多項式の計算で使用される。

【０００５】参照文献［Ｃ］は、参照文献［Ｂ］で開示
された「バーレカンプ−マッセイ」・アルゴリズムの実
施態様を記載している。しかし、この実施態様では、４
ｔ＋１個の乗算器、６ｔ個のレジスタ、及び残りのシン
ドローム用のｔ個のレジスタを必要とし、エラー位置検
出多項式及びエラー評価多項式の計算のために合計６ｔ
個の乗算遅延を必要とする。さらに、この参照文献は、
ビット・スライス回路を使った実施態様を開示も示唆も
していない。

【０００６】参照文献［Ｄ］の６５頁及び１０４頁で、
ホワイティングは、バーレカンプのアルゴリズムの条件
付き分岐の記述におけるある任意性（ａｒｂｉｔｒａｒ
ｉｎｅｓｓ）を指摘した。ホワイティングはまた、バー
レカンプのアルゴリズムの並列実施態様は、参照文献
［Ｂ］で変更されたアルゴリズムの並列化に必要なハー
ドウェア資源と比較して、２倍の数の多項式係数を記憶
すること、及び乗算器を１つ追加するか、または１つの
乗算器を時間多重化することが必要であることを指摘し
た。

【０００７】

【発明が解決しようとする課題】本発明の目的は、分岐
条件における任意性を有効に取り除くことにより、参照
文献［Ｂ］で必要とされる以上のハードウェアの追加を
必要とせずに、復号動作のためのキー方程式を並列化す
ることにある。

【０００８】

【課題を解決するための手段】本発明者等のアルゴリズ
ムは、５回の乗算を実行するシーケンスを直接繰り返す
ことができないようにして、分岐条件の任意性を除去す
る。このシーケンスは、３回の乗算のみを実行する次の
シーケンスと結合されて、２回の繰返しで８回の乗算が
必要となり、その結果、１回のシーケンス繰返しにつき
平均４回の乗算が行なわれるようにされる。この結合さ
れたシーケンス構造は、ＶＬＳＩ（超大規模集積回路）
での実施を容易にするため、モジュール形式のハードウ
ェアで示される。

【０００９】

【実施例】本発明の実施例を説明する前に、以下ではそ
の理解に必要な事項を概説する。８ビットのバイトに対
応する２５６個の要素から成るガロア体ＧＦ（２⁸）を
想定する。したがって、本発明によるアルゴリズム及び
そのハードウェア実施態様は、モジュロ２ガロア体算術
を使ってバイトに作用する。入力データは２ｔバイトで
あり、ここでは説明の便宜上入力データがＲＳコードに
対するシンドロームであると想定する。但し、ｔは訂正
すべきエラーの数である。

【００１０】本明細書及び特許請求の範囲で使用する場
合、「バイト」という用語は理解しやすいように使用し
たもので、単に例示的なものと考えるべきである。本発
明は、他の分野に関係した記号で実施することもできる
からである。

【００１１】本発明によれば、キー方程式解法回路は、
ＲＳコード等の線形代数コードの復号のためにキー方程
式を解くための並列化アルゴリズム及びモジュール式ハ
ードウェア実施態様をもたらすように修正される。

【００１２】上記のように、ｔ＝訂正すべきエラーの
数、ｖ，ｕ，ｐ，ｑ及びＳは単一変数多項式であると仮
定する。キー方程式は合同式ｖ（ｚ）・Ｓ（ｚ）≡ ｑ（ｚ）ｍｏｄ（ｚ^2t）であ
り、その解（存在する場合）は有理関数となる。

【数４】２ｔ−１線形代数コードに関する所与の一組のシンドローム｛Ｓ
ｉ｝を多項式Ｓｉ＝０（ｚ）の係数と見なすことができる。キー方程式の分母
多項式ｖ（ｚ）の根はエラー所在位置であり、これらの
根におけるｒ（ｚ）の剰余はエラー値である。

【００１３】次に、図面を参照して本発明の実施例を説
明する。図１に示すように、本発明を具体化した装置
は、リード＝ソロモン（ＲＳ）コード等の線形代数コー
ドの復号用のデコーダ１０を備える。任意のエラー・パ
ターンｅ（ｘ）を含む雑音を伴なったコードワードｃ
（ｘ）が、線１１を介してシンドローム生成機構１２及
びバッファ１３に供給される。生成機構１２からのシン
ドローム出力Ｓ（ｘ）は、キー方程式解法回路１４に送
られる。

【００１４】本発明によれば、解法回路１４は特定の組
のエラー・シンドロームＳ（ｘ）に関するエラー位置検
出多項式ｖ（ｘ）及びエラー評価多項式ｑ（ｘ）をそれ
ぞれ「チェン」（Ｃｈｉｅｎ）探索回路１５及びエラー
値計算回路１６に出力する。回路１５は、参照文献
［Ｅ］に開示された種類のものであることが好ましい。
回路１５及び１６の出力は１７でゲートされて、推定エ
ラー・パターンを表す出力ｅ’（ｘ）を発生する。出力
ｅ’（ｘ）は１８でバッファ１３からの出力（線１１か
らバッファへのコードワード＋エラー・パターンの入力
に相当する）と加算され、線１９に訂正済みのコードワ
ードｃ（ｘ）を発生する。

【００１５】したがって、Ｓ（シンドローム多項式）及
びｔ（訂正すべきエラーの数）が与えられると、方程式
解法回路１４は、ｖ及びｑ（それぞれエラー位置検出多
項式及びエラー評価多項式）を導き出す。

【００１６】参照文献［Ｄ］で、ホワイティングは、参
照文献［Ａ］及び［Ｂ］の直列のキー方程式解法アルゴ
リズムが並列化された場合に必要となるハードウェア及
び待ち時間を考察した。表１は、参照文献［Ａ］に記載
されたバーレカンプのアルゴリズムを並列化するための
ホワイティングのバージョン１と２、及び参照文献
［Ｂ］に記載されたいわゆるバーレカンプ−マッセイ
（ＢＭ）アルゴリズムを、本発明者等のアルゴリズムと
性能を比較したものである。

【００１７】

【表１】乗算器記憶域待ち時間Ｂバージョン１３ｔ６ｔ４ｔＢバージョン２２ｔ６ｔ６ｔＢＭ２ｔ６ｔ６ｔ本発明者等２ｔ６ｔ４ｔ

【００１８】本発明者等のアルゴリズムの詳細本発明者等のアルゴリズムは、２ｔ個の体要素
［Ｓ₀，．．．．，Ｓ_2t-1］のデータ・ベクトルを入力
として受け取り、［ｖ₀，．．．，ｖ_t-1］及び
［ｑ₁，．．．ｑ_t-1］を出力として発生する。これら
は、一般に体要素｛Ｓｉ｝を係数とするべき級数と見な
すことができる、Ｓ（ｚ）の有理近似値の分母と分子で
ある。２ｔ個の体要素の入力ベクトルでは、生成された
有理近似値の分母次数はｔを越えることができない。分
子多項式の次数は分母多項式の次数よりも完全に小さ
い。このアルゴリズムは、２ｔ回の繰返しの後終了す
る。

【００１９】図３において左側にバーレカンプが参照文
献［Ａ］で示したアルゴリズムが示されており、右側に
これと対比した形で本発明のアルゴリズムが示されてい
る。本発明者等のアルゴリズムの流れ図はより具体的に
は図２Ｂに示される。計算は以下のように５つのステッ
プに分かれる。ステップ１（初期設定）

【数５】

【００２０】ステップ１では、ベクトル変数ｖ，ｕ，ｐ
及びｑが初期設定される。これらのベクトルの各々はそ
れぞれｔ個の構成要素を有する。上で使用した規約は、
ｕ及びｑに「オール・ゼロ」ベクトルを割り当て、ｖ及
びｐの両方の最下位の係数に値１を割り当て、その他の
係数は０とするものである。繰返しの回数をカウントす
るために使用されるスカラ変数ｉには、最初に値−１を
割り当てる。スカラ変数Ｒは、アルゴリズムのステップ
２が実行される回数をカウントし、スカラ変数ｒは，ス
テップ２及びステップ４が実行される回数の差をカウン
トする。アルゴリズムの終了を判定するために使用され
るスカラ変数ｔ’は、訂正可能なエラーの数であるｔか
ら始まる。ステップ２（線形従属性テスト）

【数６】

【００２１】ステップ２では、ｉ及びＲが１だけ増分さ
れ、ｕ及びｐが１位置だけ右にシフトされる（上記規約
では、ベクトルの内容を右に０を付加したベクトルで置
換するものとして示す）。

【００２２】ステップ２で実行される主な計算は、Ｓベ
クトルの内容とｖベクトルの内容とのたたみ込みであ
り、その結果、一般に「不一致（ｄｉｓｃｒｅｐａｎｃ
ｙ）」と呼ばれる値ｅが得られる。（参照文献［Ａ］参
照）。実際には、この計算は、ｖの現在値で重み付けし
たシンドロームが線形独立であるかどうかを検査する。

【００２３】ｅ＝０である場合は、そのように重み付け
されたシンドロームは線形従属である。その場合は、図
２Ｂに示すようにステップ２が繰り返される。図２Ｂに
おいてステップ２に続くＲ＝ｔ’の判定は２ｒ≧ｉ＋１
の判定と等価である。ｅ≠０の場合は、アルゴリズムは
ステップ３に進む。ステップ３（更新）

【数７】

【００２４】ステップ３では、スカラ変数ｒ及びｔ’
が、ステップ２が実行された回数であるＲだけそれぞれ
増分及び減分される。ｖの内容は、ｖの現在値から、ｕ
の前の値にステップ２で計算された非ゼロの不一致ｅを
乗じた積を差し引くことにより更新される。

【００２５】ｖの現在（未更新）値は同時に、ｖの現在
値を非ゼロの不一致ｅで割った商を一時的に記憶する中
間変数Ｔを用いてｕの値を更新するために使われる。

【００２６】すなわち、ステップ３では、ｖ及びｕが共
に、それらの前の値と不一致ｅを使って更新される。

【００２７】全く同様にして、中間変数Ｔ’を使ってｑ
及びｐが更新される。更新ステップ３は反復されず、無
条件にステップ４に進む。ステップ４（多項式反復）

【数８】

【００２８】ステップ４で、反復カウント変数ｉが増分
され、同時にＲの値が減少される。Ｒが０よりも大きい
限り、Ｒが０になるまでステップ４が繰り返され、Ｒが
０になると、図２Ｂ及び図３に示すように、プログラム
制御ステートメントによって、計算はステップ２に戻
る。

【００２９】ステップ２の開始時に、アルゴリズムは、
Ｒの値としきい値ｔ’を比較することにより、ステップ
２が何回実行されたかを調べる。Ｒ＝ｔ’の場合、アル
ゴリズムは、「出口テスト」であるステップ５に進む。ステップ５（出口テスト）

【数９】

【００３０】ステップ５に入ると、ステップ５は「デコ
ード失敗」出口を生成するか、またはエラー位置検出多
項式係数及びエラー評価多項式係数、すなわちそれぞれ
ベクトルｖ及びｑを発生する。

【００３１】バーレカンプと本発明者等のアルゴリズム
の比較バーレカンプのアルゴリズムは、図２Ａに要約して示さ
れる。バーレカンプのアルゴリズムと本発明者等のアル
ゴリズムとの主な違いは実行される乗算の回数にある。
不一致”ｅ”がゼロでない場合にはバーレカンプのアル
ゴリズムはｅの計算毎に５回の乗算を必要とするが、本
発明のアルゴリズムでは４対の乗算が行われ、各対の乗
算は２つの並列乗算として行われる。本発明者等のアル
ゴリズムは、図２Ａ及び図２Ｂの比較から明らかなよう
に、（１）初期設定ステップ、（２）「不一致」ｅの計
算、及び（３）シーケンス分岐条件の点で、バーレカン
プのアルゴリズムとは異なる。

【００３２】バーレカンプのアルゴリズムと本発明者等
のアルゴリズムにおけるｅの計算は、バーレカンプの変
数加算の代わりに、本発明者等のアルゴリズムでは、入
力ベクトル［Ｓ_o，Ｓ₁，．．．，Ｓ_2t-1］を処理するた
めに循環シフト・レジスタ２０（図４）に移されるよう
な固定加算が用いられる点で異なる。シフト・レジスタ
２０は２つの「レベル」、すなわち、上位レベルＳ１と
下位レベルＳ２を有する。シフト・レジスタ２０の全て
のラッチは、最初に図４に示す位置に並列にロードされ
る。この機能は、キー方程式を解くための並列化アルゴ
リズムを実施するために不可欠である。

【００３３】本発明の重要な特徴によれば、バーレカン
プのアルゴリズムとは異なり、本発明者等のアルゴリズ
ムのステップ３は反復できない。より具体的にいうと、
ステップ３の２つの相続く実行の間に、ステップ４の少
なくとも１回の実行及びステップ２の１回の実行があ
る。

【００３４】図２Ｂに示される本発明のアルゴリズムは
表２に示されるＡシーケンス及びＢシーケンスのシーケ
ンスに変換される。本発明のアルゴリズムのステップ２
及びステップ３は図２Ｂに示されるように組み合わされ
てＢシーケンスとなる。これと同様にステップ４は同じ
く図２Ｂに示されるようにＡシーケンスとなる。更に、
冗長な乗算、たとえばゼロを乗ずる乗算、を導入するこ
とにより、ステップ５及びステップ２は同様にＡシーケ
ンスの形に変換される。このようにして本発明のアルゴ
リズム全体がＡ及びＢのシーケンスを実行する。

【表２】

【００３５】図２Ｂからわかるように、本発明者等のシ
ーケンス構造では、ステップ３は直接ループしないよう
になっている。これに対し、バーレカンプの従来のシー
ケンスは図２Ａに示されるように条件付き分岐制御条件
（ｅ＝０ｏｒ２ｒ＞ｉ＋１）が満たされるまで続
けてループする。したがって本発明においてはＢ−Ｂシ
ーケンス（表２）が実行されるのを防ぐ。言い換える
と、図２Ｂからわかるように、ステップ３は直ちには反
復できない。

【００３６】バーレカンプ及び本発明者等のアルゴリズ
ムに関して並列化によって実現可能な最適高速度化は、
動作依存関係グラフを考察することによって導き出され
る。ハードウェア実施態様で、考えられる時間のかかる
算術演算は乗算だけであり、これらの乗算は依存関係グ
ラフでは辺の形で表される。図５Ａ及び図５Ｂは、それ
ぞれタイプＡのシーケンス及びタイプＢのシーケンスの
乗算依存関係グラフを示す。辺で結合されたノードは、
乗算されている変数が記される。

【００３７】アルゴリズムの始めに、それらの変数はそ
れぞれ初期値を有する。図５Ａ及び図５Ｂに示すよう
に、矢の尾ノードにおける変数は矢の頭ノードにおける
変数の因数である。この（乗算）依存関係グラフでは、
ノードｅを除く全てのノードは２つの因数を表す２つの
項目を有し、ノードｅでは１つの因数は常にシンドロー
ム・ベクトルである。実線の矢はすべて同じ繰返し内の
依存関係を表し、破線の矢は現在の繰返しと直前の繰返
しの間の依存関係を表す。点線の矢は現在の繰返しと任
意の前の繰返しの間の依存関係を示す。

【００３８】全ての矢は、乗算時間を表す単位重みを有
するから、最大（サイクル長／当該サイクル中の破線の
矢の数）＝△を決定することにより臨界サイクルが確立
される。どちらのアルゴリズムでも、△＝２である場
合、臨界サイクルはｅ―ｖ―ｅ（次の繰返し）である。
したがって、待ち時間の下限は２つの乗算時間／繰返し
である。

【００３９】かくて、この最小時間を実現するために必
要な乗算器の数を決定しなければならない。待ち時間は
最適であることが必要なので、繰返しの最悪の場合を考
慮しなければならない。したがって、シンドローム入力
は、初期の繰返しではどんな乗算器の節約をも許さない
値を有するものと想定される。依存関係グラフからのノ
ード変数はスカラと考えられる。各ベクトルはｔ個の自
明でない記号を含み、ベクトルの場合の乗算器の数は、
スカラの場合の乗算器の数のｔ倍である。

【００４０】本発明のアルゴリズムによれば、タイプＢ
のシーケンスは５回の乗算を必要とし、一方、タイプＡ
のシーケンスでは３回の乗算で十分である。バーレカン
プのアルゴリズムでは、全アルゴリズム中ｅ≠０の場
合、Ｂシーケンスのみのシーケンスが実行される。した
がって、２乗算サイクル／繰返しの待ち時間を実現する
ために必要な乗算器の最小数は、バーレカンプのアルゴ
リズムでは３である。

【００４１】本発明によれば、本発明者等のアルゴリズ
ムは、タイプＢのシーケンスをそれに続くタイプＡのシ
ーケンスと組み合わせたもので、その結果、２回の繰返
しのために８回の乗算が必要となる。次の２つのシーケ
ンスＡ及びＢ−Ａとそれらの全ての組合せＡ−Ａ、Ａ−
Ｂ−Ａ、Ｂ−Ａ−Ａ及びＢ−Ａ−Ｂ−Ａを考えれば十分
である。本発明者等のアルゴリズムでは、前述のよう
に、シーケンスＢ−Ｂは可能でない（図２Ｂ参照）。

【００４２】図５Ａ及び図５Ｂから、上述の全ての組合
せが、有効なスケジュールをもたらすことが明らかであ
る。最後の繰返しがタイプＢである場合は、ｕ及びｐの
更新は冗長になることに留意されたい。したがって、本
発明者等のアルゴリズムは、４ｔ＋１回の乗算サイクル
で実行することができ、２ｔ個の乗算器が必要となる。
実際には、データ・ベクトルの初期条件を利用する場合
は、乗算サイクルの数を２だけ減らすことが可能であ
る。要約すると、図２Ｂから判るように、ステップ２に
おいてｅを計算し、ステップ３においてｕ，ｖ，ｐ，ｑ
を計算し、ステップ４においてｅ，ｖ，ｑを計算するた
めに別々の乗算が必要とされる。Ａシーケンスは合計３
回の乗算のためにステップ４だけを含む。Ｂシーケンス
は合計５回の乗算のためにステップ２及びステップ３を
含む。Ａシーケンスにおけるｖ及びｑのための２回の乗
算は図５Ａの動作依存関係に従って並列に実行されう
る。図６はＡシーケンスにおいてｖが偶数サイクルで計
算され、ｑが奇数サイクルで後に計算されることを示し
ている。Ｂシーケンスにおけるｕ、ｖ、ｐ、ｑのための
４回の乗算は図５Ｂの動作依存関係に従って互いに並列
に行われ得る。ｅの計算を含めるとシーケンスＡが３回
の乗算、シーケンスＢが５回の乗算を含むことが示され
ている。図６はＢシーケンスにおいてｖが偶数サイクル
に計算され、ｑが奇数サイクルに計算されることを示し
ている。これらは４対の乗算で各対が並列に計算される
ことを表している。つまり、図６の最初の計算シーケン
スを見ると、奇数サイクルでは１つのＢシーケンスの乗
算が行われように示されているが、偶数サイクルでは２
つのシーケンスＢ乗算が行われ、２回目の計算シーケン
スでは奇数、偶数サイクルそれぞれにシーケンスＡ及び
Ｂの乗算が行われる。図６の最後のシーケンスＡ乗算は
次の最初の計算シーケンスに繰り越されてシーケンスＢ
の乗算と対になる。本発明のアルゴリズムはバイト・ス
ライス当たり、かつ合計ｔバイト・スライスに対して２
つの乗算器Ｍ１及びＭ２（図１０）を必要とするだけで
ある。

【００４３】ハードウェアの実施態様簡単で均質なハードウェア実施態様を実現するため、タ
イプＢ−Ａ及びタイプＡまたはＡ−Ａのシーケンスに共
通のスケジュールが生成される。このスケジュールを図
６に示す。図６はアルゴリズムの動作シーケンスを変え
ることにより本発明がどのようにして並列化を達成する
かを示している。不一致値の全てのシーケンス（単に幾
つかの不一致値ではなく）に対して多くても４対の乗算
が行われるだけであり、各乗算対が並列乗算として行わ
れることに注目されたい。このスケジュールを使って、
本発明者等のキー方程式解法回路１４の訂正装置全体に
ついてモジュール式設計が導き出された。訂正装置は図
２１に示され、以下に説明する基本的論理装置及びモジ
ュールを使って構成される。

【００４４】図７Ａはラッチ２５を、図７Ｂは様々な入
力条件に対応するラッチ出力を概略的に示す。図８Ａ
は、図８Ｃに表にした出力を発生するためのマルチプレ
クサ回路２６を概略的に示し、図８Ｂにそれをさらに完
全に示す。

【００４５】本発明の特徴によれば、図９に示すよう
に、Ａ回路と記した訂正装置のビット・スライス回路３
０が設けられる。回路３０は、それぞれ指定された変数
の１ビットを記憶する、Ｓ１、Ｓ２、ｑ、ｐ、ｕ、ｖと
記した６個の１ビット・ラッチ２５ａ〜２５ｆを備え
る。回路３０はまた、９個のマルチプレクサ回路２６ａ
〜２６ｉ及び１個の排他的ＯＲ（ＸＯＲ）ゲート２７を
含む。マルチプレクサ回路２６ａ及び２６ｂは、シンド
ローム入力をロード及びシフトするために使用される。
マルチプレクサ２６ｄ、２６ｅ、２６ｇは、乗算器Ｍ１
及びＭ２（図１０）に入力する因数を切り替えるために
使用される。マルチプレクサ２６ｉはＸＯＲゲート２７
への入力を切替える。マルチプレクサ２６ｃは、ｐラッ
チ２５ｄを、ラッチ２５ｃ中の前のｑ値用の中間記憶域
として働くように切り換える。マルチプレクサ２６ｆ及
び２６ｈは、それぞれｐラッチ２５ｄ及びｕラッチ２５
ｅからのデータを修正またはシフトする。ＸＯＲゲート
２７は、加算ｖ＋ｅ・ｕまたはｑ＋ｅ・ｐを実施するた
めに使用される。

【００４６】回路３０は、キー方程式解法アルゴリズム
用の完全に動作する１ビット装置の実施態様を構成す
る。

【００４７】図１０に示すように、Ａ０〜Ａ７と記した
８個のビット・スライスＡ回路３０と、２つの乗算器Ｍ
１及びＭ２が、バイト・スライスＢ回路４０を構成す
る。様々なビット位置間の相互作用のみが乗算動作中に
生じるので、回路４０をこれら８個のビット・スライス
Ａ回路３０に分割することができる。８入力ＯＲゲート
４１及び後続のラッチ２５ｇは、エラー所在位置の範囲
の決定、及び繰返しチェン探索回路１５（図１）に関す
るエラー位置検出ベクトルの適切な位置決めの際に必要
となる。

【００４８】クロック・制御回路完全な制御・クロック回路を図１１ないし図１６に示
す。

【００４９】図１１に示すクロック発生回路４９は、主
ＣＬＯＣＫから４つのクロック信号ＣＬＫ１〜ＣＬＫ４
を発生する。クロック発生回路を制御する入力信号は、
ＩＮＰＵＴ、ＥＮＤ及びＣＵである。ＩＮＰＵＴ信号
は、計算の開始前にのみ活動化される。ＩＮＰＵＴ＝１
の間は、シンドローム・ラッチ２５ａ、２５ｂの内容の
みが修正できる。ＥＮＤ信号は、計算の完了後に全ての
クロックを使用禁止にし、したがって、ラッチ５１（そ
の出力はＯＤＤ信号である）を除く全てのラッチの内容
を凍結する。ＩＮＰＵＴ信号及びＥＮＤ信号は、実際の
計算中は共に０である。

【００５０】４つのクロック信号全てを制御する主エネ
ーブル信号はＯＤＤである。これは、図６に示すよう
に、１つの繰返しを構成する２つの異なる動作サイク
ル、すなわち奇数サイクルと偶数サイクルの区別を可能
にする交番信号である。

【００５１】ＯＤＤ信号は、主システムＣＬＯＣＫによ
ってエネーブルされるラッチ５１の出力として発生され
る。ラッチ５１への入力は、ＩＮＰＵＴの反転値及びＯ
ＤＤ出力からＡＮＤゲート５０を介して得られる。奇数
動作サイクル（ＯＤＤ＝１）では、ＣＬＫ２＝１の間に
ラッチｐ、ｑ、Ｓ１、Ｓ２の内容が修正される。ＣＬＫ
２信号はＡＮＤゲート５４の出力として得られる。ＯＲ
ゲート５３の出力として得られるエネーブル・クロック
信号ＣＬＫ１は、計算中はＣＬＫ２と同じであるが、ま
たＳ１シンドローム・ラッチ２５ａ及びＳ２シンドロー
ム・ラッチ２５ｂの内容をロードするためにＩＮＰＵＴ
によってエネーブルされる。ＩＮＰＵＴはまた、各計算
が、ＡＮＤゲート５０によって実施される、奇数動作サ
イクルから開始することを保証する。

【００５２】偶数動作サイクル（ＯＤＤ＝０）では、Ｃ
ＬＫ４＝１の間にｕラッチ２５ｅ及びｖラッチ２５ｆの
内容が修正される。ＣＬＫ４はＡＮＤゲート５７の出力
として得られる。ｐラッチ２５ｄは、奇数サイクル中は
ｐ多項式の係数を記憶するのに使用され、また（偶数サ
イクル中に行われる）ステップ２からステップ４への切
換え中にはｑ多項式の係数の最後の値を一時的に記憶す
るのに使用されるので、別々のエネーブル・クロックＣ
ＬＫ３が発生される。ＣＬＫ３は、制御信号ＣＵによっ
てエネーブルされたＣＬＫ４またはＣＬＫ２からＯＲゲ
ート５５の出力として発生される。

【００５３】制御信号回路５９を図１２に示す。ラッチ
６１の出力ＶＡＬＩＤは、スカラ変数Ｒ用のカウンタ６
５が昇順にカウントするのか、すなわちアルゴリズムが
ステップ２を実行するのか（ＶＡＬＩＤ＝１）、それと
も降順にカウントするのか（ステップ４、ＶＡＬＩＤ＝
０）を制御する。このラッチ６１はＣＬＫ２によってエ
ネーブルされ、その入力はＯＲゲート６４の出力として
発生される。このゲートは、ｅ＝０かつＶＡＬＩＤ＝１
のとき（すなわち、アルゴリズムがステップ２を実行し
ている間）、またはＲ＝０かつＶＡＬＩＤ＝０のときに
活動化される。ＶＡＬＩＤは、ｅ≠０の場合に１から０
に切り変わり、Ｒ＝０の場合に０から１に戻る。ＶＡＬ
ＩＤは、ＣＬＫ２＝１のときに生じる奇数動作サイクル
中にのみ変更することができる。

【００５４】制御信号ＣＵ＝１は、最新のｅ値は０に等
しくないが、ＶＡＬＩＤラッチの状況は依然として１で
あることを、すなわちアルゴリズムがステップ３（Ｂシ
ーケンス）を実行していることを示す。ＣＵ＝１の間、
及びＶＡＬＩＤが０に切り換わり戻るまでは、Ｂシーケ
ンスは開始できない。これは、連続したＢ−Ｂシーケン
スの実行を、したがってステップ３の繰返しを禁止する
分岐条件を有効にする。

【００５５】ＡＮＤゲート６０の出力として発生される
ＣＵ信号は、１つの奇数動作サイクルと後続の偶数動作
サイクルの間活動状態になり、ｕラッチ２５ｅの内容の
修正を制御するために使用される。ＣＵ（＝１）が計算
の終りに活動状態である（ステップ３）か、またはＶＡ
ＬＩＤ＝０である（ステップ４）場合は、エラーは訂正
不能であり、ＯＲゲート６７の出力として発生される信
号ＷＲＯＮＧ＝１によってそれが示される。

【００５６】ラッチ６６の出力は、信号ＣＵが２動作サ
イクル遅延されたものに等しい。信号ＣＰ１は、ラッチ
６６の出力が活動状態である間は、偶数動作サイクルで
活動状態である。この信号は、ｐラッチ２５ｄが、ｐ多
項式の係数を記憶するために使用されるのか（ＣＰ１＝
０）、それともｑ多項式の最後の係数を一時的に記憶す
るために使用される（ＣＰ１＝１）のかを制御する。Ｃ
Ｐ１はＡＮＤゲート６２の出力として発生される。信号
ＣＰ２は、ＣＵが活動状態である間、奇数動作サイクル
中のみ活動状態である。ＣＰ２はＡＮＤゲート６３の出
力として発生される。ＣＰ２は、ｐラッチ２５ｄ及び第
１の乗算器Ｍ１Ｆ１（図１０）の係数の１つ、すなわち
ＣＰ２＝０の場合はｖ、ＣＰ２＝１の場合はｑ多項式の
最後の係数を記憶する間、ｐの変更を制御する。

【００５７】図１３は、不一致値ｅの逆数を計算する回
路７０を示す。この回路７０は、マルチプレクサ７１及
びＲＯＭルックアップ反転テーブル７２から成る。マル
チプレクサ７１は、テーブル７２の共用を可能にする。
ＲＯＭ反転テーブル７２の出力ｄＲＥＳは、８個のラッ
チから成る８ビット・レジスタ７５（図１４）に記憶さ
れる。レジスタ７５は、ＣＰ２により８個のマルチプレ
クサ７６を介して制御される。ＣＰ２は、値ｄＲＥＳが
ｕラッチ２５ｅの修正のために直ちに使用されるのか、
それともｐラッチ２５ｄの修正のために後で使用される
のかを決定する。

【００５８】図１５に示すように、終了回路８０は、Ｃ
ＬＫ２信号をカウントし、２ｔ＋１回の繰返しの後に計
算を停止させるカウンタ８１を含む。

【００５９】図１６Ａは、図１１に示した前述の回路４
９によって発生される４つのクロック信号ＣＬＫ１〜Ｃ
ＬＫ４に関するブール方程式を表にしたものである。図
１６Ｂはマトリックスであり、その列は個々のラッチ・
ラベルＳ、ｕ、ｖ、ｑ、ｐであり、その行は、アルゴリ
ズムの実行中にそれらのラッチ・ラベルに対して実行さ
れる個々の算術演算に対応する。マトリックスの項目
は、特定のレジスタに関して実行される特定の演算中に
活動化される制御信号またはクロック信号を示す。図１
６Ａ及び図１６Ｂは、既に詳細に説明した制御動作及び
クロッキング動作を要約して示したものである。

【００６０】本発明者等の発明を実施するには、図９に
記載したビット・スライスＡ回路３０及び図１０に記載
したバイト・スライスＢ回路４０で十分であると考えら
れることに留意されたい。しかし、完璧を期すため、か
つハードウェアの複雑さを減少させるため、図１７Ａ、
図１７Ｂ及び図１８に、それぞれ最初の列及び最後の列
用のビット・スライスＡ回路がどのようにして簡略化で
きるかを示す。８ビット・バイトの場合、図１７Ａにお
けるような１つの回路、及び図１７Ｂにおけるような７
個の回路があることに留意されたい。図１９及び図２０
は、それぞれ最初のＢ０バイト・スライスＢ回路及び最
後のＢｔバイト・スライスＢ回路を示す。これらのハー
ドウェアの簡略化が実現できるのは、最初のステップで
は計算は簡単であり、乗算を必要とせず、また最後のス
テップではアルゴリズムは全ての演算を必要としないか
らである。

【００６１】最後に、図２１に、ｔ＝８（エラー訂正）
用の訂正装置８４を概略的に示す。前述のように、クロ
ック発生回路４９及び制御信号回路と組み合わされた訂
正装置８４は、最初のバイト・スライスＢ０回路、７個
の通常のＢ回路、及び最後のＢ８回路から成る。ｅレジ
スタ８５及び（ｔ＋１）入力加算器８６はこの装置の一
部である。

【図面の簡単な説明】

【図１】線形代数コードを復号するための、本発明を具
体化した装置のブロック図である。

【図２Ａ】バーレカンプの従来技術のキー方程式解法ア
ルゴリズムを要約して示す図表である。

【図２Ｂ】本発明の修正されたアルゴリズムをバーレカ
ンプの従来技術のキー方程式解法アルゴリズムと対比し
た形で示す図表である。

【図３】バーレカンプのアルゴリズムと本発明者等の修
正されたキー方程式解法アルゴリズムとを対比して示す
図表である。

【図４】本発明者等の並列化アルゴリズムの実施態様で
使用される２「レベル」循環シフト・レジスタの図であ
る。

【図５Ａ】キー方程式解法アルゴリズムによって実行さ
れるＡシーケンスの乗算依存関係図である。

【図５Ｂ】キー方程式解法アルゴリズムによって実行さ
れるＢシーケンスの乗算依存関係図である。

【図６】それぞれ奇数サイクル及び偶数サイクルから成
る２つの連続した繰返しの間のＡシーケンスとＢシーケ
ンスの結合を示す、本発明による並列化アルゴリズムの
スケジュール図表である。

【図７Ａ】ラッチのブロック図である。

【図７Ｂ】ラッチの状態図表である。

【図８Ａ】マルチプレクサのブロック図である。

【図８Ｂ】マルチプレクサの回路図である。

【図８Ｃ】マルチプレクサの状態図表である。

【図９】本発明者等の訂正装置のビット・スライス回路
の概略図である。

【図１０】訂正装置のモジュール式バイト・スライス回
路の概略図である。

【図１１】クロック発生回路の概略図である。

【図１２】制御信号回路の概略図である。

【図１３】反転回路の概略図である。

【図１４】図１３の回路による反転の結果を示す概略回
路図である。

【図１５】２ｔ回の繰返しの後で計算を終了させるため
の終了回路の概略図である。

【図１６Ａ】各クロックが活動状態になる条件を示す表
である。

【図１６Ｂ】異なる変数を含むシフト・レジスタとそれ
らのレジスタに対して実行される異なる動作との関係を
示すマトリックス図である。

【図１７Ａ】シンドローム・ラッチに対する最初の入力
データ・ビット用の初期設定ビット・スライス回路の概
略図である。

【図１７Ｂ】図１７Ａの残りの７個のビット用の初期設
定ビット・スライス回路の概略図である。

【図１８】末端列ビット・スライス回路の概略図であ
る。

【図１９】エラー訂正装置の先頭のバイト・スライス回
路の概略図である。

【図２０】エラー訂正装置の末端のバイト・スライス回
路の概略図である。

【図２１Ａ】ｔ＝８の場合の完全な訂正装置の概略図で
ある。

【図２１Ｂ】ｔ＝８の場合の完全な訂正装置の概略図で
ある。

【符号の説明】

１２シンドローム発生機構１３バッファ１４キー方程式解法回路１５「チェン」探索回路１６エラー値計算回路１７ゲート３０ビット・スライス回路４０バイト・スライス回路４９クロック発生回路８０終了回路

───────────────────────────────────────────────────── フロントページの続き (72)発明者ユー・シュヴィーゲルスホーンアメリカ合衆国10547、ニューヨーク州モヒガン・レーク、クロムウェル・プレース 19番地Ｂ (72)発明者サミュエル・ヴィノグラードアメリカ合衆国10583、ニューヨーク州スカースデール、グレンデール・ロード 235番地 (56)参考文献特開昭61−273018（ＪＰ，Ａ) 特開平２−20123（ＪＰ，Ａ) 特開平２−303221（ＪＰ，Ａ) 特開平２−16637（ＪＰ，Ａ)

Claims

【特許請求の範囲】

【請求項１】ｔ＝訂正すべきエラーの数、エラー位置検
出多項式をｖ、エラー評価多項式をｑ、ｕ及びｐを補助
多項式であるとし、Ｓをエラー・シンドロームとして線
形代数コードを復号するのに必要なキー方程式ｖ（ｚ）・Ｓ（ｚ）≡ ｑ（ｚ）ｍｏｄ（ｚ^2t）を解くためのアルゴリズムを実現する方法であって、（ａ）前記多項式ｖ，ｕ，ｐ及びｑを初期設定し、変数ｒ，ｔ’，Ｒ，ｉをｒ＝０ｔ’＝ｔＲ＝０ｉ＝−１に初期設定するステップと、（ｂ）ｉ＝ｉ＋１，Ｒ＝Ｒ＋１によりｉ及びＲを増分し
て前記多項式ｕ及びｐを１位置シフトするステップと、（ｃ）【数１】により不一致値ｅを計算するステップと、（ｄ）ｅ＝０又は２ｒ≧ｉ＋１でなくなるまでステップ
（ｂ）ないし（ｃ）を繰り返すステップと、（ｅ）ｅ＝０又は２ｒ≧ｉ＋１でなければｒ＝ｒ＋Ｒｔ’＝ｔ’−Ｒによりｒ及びｔ’を更新してｖ＝ｖ−ｅ・ｕｕ＝ｖ／ｅｑ＝ｑ−ｅ・ｐｐ＝ｑ／ｅに従ってｖ，ｕ，ｑ，及びｐを更新するステップと、（ｆ）ｉ＝ｉ＋１としてｕ及びｐを１位置シフトして、【数２】により不一致値ｅを計算するステップと、（ｇ）ｖ＝ｖ−ｅ・ｕｑ＝ｑ−ｅ・ｐに従ってｖ及びｑを更新してＲ＝Ｒ−１とするステップ
と、（ｈ）Ｒ＞０である間（ｆ）及び（ｇ）を繰り返すステ
ップと、（ｉ）Ｒ＝ｔ’でなければ（ｂ）に戻り、（ｊ）Ｒ＝ｔ’であるならばｉ＝ｉ＋１として【数３】により不一致値ｅを計算するステップと、（ｋ）ｅ≠０であるならばｉ＝２ｔ−１となるまで（ｊ）を繰り返しこのときのｖ及びｑをエラー位置検出多項式ｖ及びエラ
ー評価多項式ｑとするステップと、を含む方法。
【請求項２】ステップ（ｂ）ないしステップ（ｅ）から
成るＢシーケンスが５つの乗算を含み、ステップ（ｆ）
ないしステップ（ｇ）から成るＡシーケンスが３つの乗
算を含み、エラー状態のｔ個の記号を復号するためにこ
れら２つのシーケンスを２ｔ回繰返すことが必要であ
り、連続した２ｔ回の前記２つのシーケンスの各繰返し
の間に、乗算動作を２つの並列乗算の対として４回実行
し、上記Ｂシーケンスでの５回目の乗算動作が上記Ａシ
ーケンスの次の繰返での乗算動作の１つと対に組み合わ
され、て成る請求項１の方法。