JPH0721048A

JPH0721048A - 線形代数コード復号のためのキー方程式を解く装置及び方法

Info

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

Abstract

(57)【要約】【目的】線形代数コードを復号するのに必要なキー方程
式の解法及び装置の提供。【構成】解法アルゴリズムにおいては計算ループが一つ
の分岐条件により２つのループに分岐される。乗算動作
回数は第一のループで３回、第二のループでは５回であ
り、エラーの数ｔを復号するためにこれらループに対し
て２ｔ回の繰返しが行われる。各連続する２ｔ回の繰返
しの間、４回の乗算動作が対になって同時に実行される
ようにこれらのループは結合される。この第二のループ
の５番目の乗算動作は第一のループの次の反復における
乗算動作と対になる。一部の乗算動作は反転テーブルが
ルック・アップされ、他の乗算動作の間中には追加的な
動作が実行される。

Description

【発明の詳細な説明】

【０００１】

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

【０００２】

【従来の技術】本発明に最も関係があると考えられる従
来技術の参照文献を以下に示す。［Ａ］Ｅ．Ｒ．バーレカンプ（Ｂｅｒｌｅｋａｍｐ）、
“ＡｌｇｅｂｒａｉｃＣｏｄｉｎｇＴｈｅｏｒｙ”，
ＭｃＧｒａｗＨｉｌｌ，１７８−１９９頁，１９６８
年。［Ｂ］Ｊ．Ｌ．マッセイ（Ｍａｓｓｅｙ），“Ｓｈｉｆ
ｔ−ＲｅｇｉｓｔｅｒＳｙｎｔｈｅｓｉｓａｎｄＢ
ＣＨＤｅｃｏｄｉｎｇ”，ＩＥＥＥＴｒａｎｓ．
ｏｎＩＴ，ＩＴ−１５，１９６９年１月。［Ｃ］Ｋ．Ｙ．リュー（Ｌｉｕ），“Ａｒｃｈｉｔｅｃ
ｔｕｒｅｆｏｒＶＬＳＩＤｅｓｉｇｎｏｆＲ
ｅｅｄ−ＳｏｌｏｍｏｎＤｅｃｏｄｅｒｓ”，ＩＥＥ
ＥＴｒａｎｓ．ｏｎＣｏｍｐｕｔｅｒｓ，１９８
４年２月，１７８−１８９頁。［Ｄ］Ｄ．Ｌ．ホワイティング（Ｗｈｉｔｉｎｇ），
“Ｂｉｔ−ＳｅｒｉａｌＲｅｅｄ−ＳｏｌｏｍｏｎＤ
ｅｃｏｄｅｒｓｉｎＶＬＳＩ”，ＰｈＤｔｈｅｓｉ
ｓ，ＣａｌｉｆｏｒｎｉａＩｎｓｔｉｔｕｔｅｏ
ｆＴｅｃｈｎｏｌｏｇｙ，１９８４年［Ｅ］Ｒ．Ｔ．チェン（Ｃｈｉｅｎ），“Ｃｙｃｌｉｃ
ＤｅｃｏｄｉｎｇＰｒｏｃｅｄｕｒｅｓｆｏｒＢ
ＣＨＣｏｄｅｓ”，ＩＥＥＥＴｒａｎｓ．ｏｎ
ＩＴ−１０，３５７ー３６３頁、１９６４年１０月。

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

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

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

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

【０００７】

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

【０００８】

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

【０００９】

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

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

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

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

【数１】（ｚ）の係数と見なすことができる。キー方程式の分母
多項式ｖ（ｚ）の根はエラー所在位置であり、これらの
根におけるｒ（ｚ）の剰余はエラー値である。

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

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

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

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

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

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

【００１９】図２は本発明者等のアルゴリズムの流れ図
である。計算は以下のように５つのステップに分かれ
る。

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

【数２】

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

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

【００２３】ｅ＝０である場合は、そのように重み付け
されたシンドロームは線形従属である。その場合は、図
２に示すようにステップ２が繰り返される。ｅ≠０の場
合は、アルゴリズムはステップ３に進む。

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

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

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

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

【数３】

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

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

【数４】

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

【００３１】バーレカンプと本発明者等のアルゴリズム
の比較バーレカンプのアルゴリズムと本発明者等の改善された
アルゴリズムの違いは、図３Ａ及び図３Ｂに並べて示
す、要約した比較を見るとわかる。図３Ａ及び図３Ｂで
は、本発明者等のアルゴリズムの計算レイアウトは、参
照文献［Ｄ］に開示された、簡略化した形で与えられる
バーレカンプの形式と等価な形式に分解してある。本発
明者等のアルゴリズムは、図３Ａ及び図３Ｂの比較から
明らかなように、（１）初期設定ステップ、（２）「不
一致」ｅの計算、及び（３）ループ分岐条件の点で、バ
ーレカンプのアルゴリズムとは異なる。

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

【００３３】本発明の重要な特徴によれば、バーレカン
プのアルゴリズムとは異なり、本発明者等のアルゴリズ
ムのステップ３は反復できない。

【００３４】この違いを示すため、バーレカンプのアル
ゴリズム及び本発明者等のアルゴリズムのループを、ル
ープ本体内の条件付き分岐の種類に応じて、２種類に分
けた。表２で、“Ｉｆ”分岐をＡループと呼び、“Ｅｌ
ｓｅ”分岐をＢループと呼ぶ。表２

【数５】

【００３５】図３からわかるように、本発明者等のルー
プ構造では、条件付き分岐制御条件が“Ｉｆｅ＝０
ｏｒ２ｒ≧ｉ＋１ｔｈｅｎ”に変更されている。こ
の変更は、“Ｅｌｓｅ”条件が連続して繰り返されるの
を防ぎ、したがってＢ−Ｂループ（表２）が実行される
のを防ぐ。言い換えると、図２からわかるように、ステ
ップ３は反復できない。

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

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

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

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

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

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

【００４２】図５Ａ及び図５Ｂから、上述の全ての組合
せが、有効なスケジュールをもたらすことが明らかであ
る。最後の繰返しがタイプＢである場合は、ｕ及びｐの
更新は冗長になることに留意されたい。したがって、本
発明者等のアルゴリズムは、４ｔ＋１回の乗算サイクル
で実行することができ、２ｔ個の乗算器が必要となる。
実際には、データ・ベクトルの初期条件を利用する場合
は、乗算サイクルの数を２だけ減らすことが可能であ
る。

【００４３】ハードウェアの実施態様簡単で均質なハードウェア実施態様を実現するため、タ
イプＢ−Ａ及びタイプＡまたはＡ−Ａのループに共通の
スケジュールが生成される。このスケジュールを図６に
示す。このスケジュールを使って、本発明者等のキー方
程式解法回路１４の訂正装置全体についてモジュール式
設計が導き出された。訂正装置は図２１に示され、以下
に説明する基本的論理装置及びモジュールを使って構成
される。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

【図面の簡単な説明】

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

【図２】線形代数コード復号のためのキー方程式を解く
ための本発明者等のアルゴリズムを実施する際に従うべ
きステップのシーケンスを示す流れ図である。

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

【図３Ｂ】本発明者等の修正されたアルゴリズムを図３
Ａのバーレカンプの従来技術のキー方程式解法アルゴリ
ズムとの比較のために要約して示す図表である。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

【符号の説明】

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

───────────────────────────────────────────────────── フロントページの続き (72)発明者ユー・シュヴィーゲルスホーンアメリカ合衆国10547、ニューヨーク州モヒガン・レーク、クロムウェル・プレース 19番地Ｂ (72)発明者サミュエル・ヴィノグラードアメリカ合衆国10583、ニューヨーク州スカースデール、グレンデール・ロード 235番地

Claims

【特許請求の範囲】

【請求項１】線形代数コードを復号するのに必要なキー
方程式を解くための並列化アルゴリズムを実現する装置
であって、２つの繰返しループを実現して、２回の繰返し毎に一方
のループが３回の乗算動作を実行し、他方のループが５
回の乗算動作を実行するようにする回路手段と、上記ループを結合して、該結合されたループが１回の繰
返し毎に４回の乗算動作を実行するようにする結合手段
と、上記ループの各々をその乗算動作が当該ループまたは他
のループの所定の乗算動作と並列に実行されるように選
択的にスケジューリングする手段とを備える上記装置。
【請求項２】複数のラッチを有し、該ラッチの各々はそ
れぞれの値が予め選択されたフィールドにおける記号で
あり且つ上記アルゴリズムで使用されるような、複数の
ベクトル変数の各々の１ビットを上記記号内の同じ相対
位置においてそれぞれ記憶するように配設され、さらに上記アルゴリズムを実現するのに必要な、上記変
数に対する複数の動作を多重化するための複数のスイッ
チとを有する、ビット・スライス回路を備える、請求項
１の装置。
【請求項３】複数のラッチを有し、該ラッチの各々はそ
れぞれの値がバイトであり且つ上記アルゴリズムで使用
されるような、複数のベクトル変数の各々の１ビットを
上記バイト内の同じ相対位置においてそれぞれ記憶する
ように配設され、さらに上記アルゴリズムへの入力バイトを生成するため
のシンドローム発生手段と、クロック信号を発生する手段と、上記入力バイト及び上記クロック信号に応答して制御信
号を発生する手段と、各スイッチが、上記アルゴリズムを実行するため、上記
入力バイトからの１ビットと上記クロック信号及び上記
制御信号を受け取る、複数のスイッチとを有する、ビッ
ト・スライス回路を備える、請求項１の装置。
【請求項４】ｎ個のビット・スライス回路（ｎは予め選
択されたフィールドからの記号のディジット数）から成
る記号スライス回路を有し、該ビット・スライス回路の
各々は複数のラッチを含み、該ラッチの各々はそれぞれ
の値が予め選択されたフィールドにおける記号であり且
つ上記アルゴリズムで使用されるような、複数のベクト
ル変数の各々の１ビットを上記記号内の同じ相対位置に
おいてそれぞれ記憶するように配設され、さらに上記アルゴリズムを実現するのに必要な上記複数
の変数に対する複数の動作を多重化するための複数のス
イッチとを有する、請求項１の装置。
【請求項５】上記記号スライス回路が、上記予め選択さ
れたフィールド内の記号を乗算するための一対の乗算器
を備える、請求項４の装置。
【請求項６】線形代数コードを復号するのに必要なキー
方程式を解くための並列化アルゴリズムを実現する装置
であって、２つの直線ループに分岐する１つの分岐条件を持つ計算
ループを含む手段を有し、上記ループの一方は３回の乗
算動作を実行し、上記ループの他方は５回の乗算動作を
実行し、エラー状態のｔ個の記号を復号するためにこれ
ら２つのループを２ｔ回繰り返すことが必要であり、さらに連続した２ｔ回の各繰返しの間に４回の乗算動作
が対になって同時に実行され、上記他方のループでの５
回目の乗算動作が上記一方のループの次の繰返しでの乗
算動作と対になるように、上記２つのループを結合する
手段とを有する、上記装置。
【請求項７】上記結合手段が、上記の対になった一方の
乗算動作中に反転テーブル・ルックアップ動作を実行
し、上記のもう一方の乗算動作中に加算動作を実行する
ように動作する手段を含む、請求項６の装置。
【請求項８】上記結合手段がモジュール構造を有してい
て、ｔ＋１個のモジュールから構成される、請求項６の
装置。
【請求項９】下記ステップ（ａ）ないし（ｃ）を含む、
線形代数コードを復号するのに必要なキー方程式を解く
ための並列化アルゴリズムを実現する方法。（ａ）２つの繰返しループを与えて、２回の繰返し毎に
一方のループが３回の乗算動作を実行し、他方のループ
が５回の乗算動作を実行するようにするステップ。（ｂ）上記２つのループを結合して、該結合されたルー
プが１回の繰返し毎に４回の乗算動作を実行するように
するステップ。（ｃ）上記ループの各々を、その乗算動作が当該ループ
または他のループの所定の乗算動作と並列に実行される
ように選択的にスケジューリングするステップ。
【請求項１０】下記ステップ（ａ）及び（ｂ）を含む、
線形代数コードを復号するのに必要なキー方程式を解く
ための並列化アルゴリズムを実現する方法。（ａ）２つの直線ループに分岐する１つの分岐条件を有
する計算ループを与えるステップ。上記ループの一方は
３回の乗算動作を実行し、上記ループの他方が５回の乗
算動作を実行し、エラー状態のｔ個の記号を復号するた
めにこれら２つのループを２ｔ回繰返すことが必要であ
る。（ｂ）連続した２ｔ回の各繰返しの間に４回の乗算動作
が対になって同時に実行され、上記他方のループでの５
回目の乗算動作が上記一方のループの次の繰返しでの乗
算動作と対になるように、上記ループを結合するステッ
プ。
【請求項１１】上記の対になった一方の乗算動作中に反
転テーブル・ルックアップ動作を実行し、上記のもう一
方の乗算動作中に加算動作を実行するステップを含む、
請求項１０の方法。