JPS63233613A - 誤り訂正装置 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】 〔産業上の利用分野〕 近年、メモリーシステムを始めとする、各種ディジタル
システムの信頼性向上の対策として誤り訂正符号の適用
が浸透してきている。

なかでも、リード・ソロモン符号（以下Ｒ５符号）は同
一の符号長と訂正能力を持つ線形符号の中で、最も冗長
度を低く出来るという特徴を持つ実用上非常に重要な符
号であり、衛星通信。

磁気ディスク、コンパクトディスク等に広く利用されて
いる。

本発明は、上記誤り訂正技術の分野に属し、特にシスト
リック・アレイを用いた並列演算器に関する。

（従来の技術） Ｒ５符号の符号化・復号法には種々の物があるが、次に
示す（１）〜（７）の演算を実現することが必要である
。

１）シンドローム多項式の生成 受信語系列（ｒｎ−凰ｕｒｎ−２・°°°・　ｒ皿・ｒ
ｅ）からシンドローム多項式５（ｘ）＝ΣＳｔ、＊ｘ’
を生成する。

ただし、 ３１−１！Σｒｎ−１＊　（（！’　）、’　　　（１
）２）誤り位置多項式と誤り数値多項式の生成Ａ、＝Ｘ
”、Ｂｏ＝Ｓ　（Ｘ）の最大公約多項式 ％式％（２） を求める。その途中で次式を満たす多項式りが誤り位置
多項式〇（ｘ）、Ｗが誤り数値多項式ω（ｘ）を表す。

ｄｅｇＷ＜ｔ、ｄｅｇＤ≦ｔ Ｃ＊　Ａ　６　＋　Ｄ　＊　Ｂ　ｏ　＝Ｗ３）誤り位置
と誤り数値の生成 多項式σ（Ｘ）、σ’　　（ｘ）、（ｘ）、ω（Ｘ）に
ついて ｆ　（ｘ）　＝Σｆｎ−１＊ｘｎ−１（３）の値をＸ；
α−ｎ←（ｉ−１，・・・、ｎ）について求める。

ただし、ｆ　（ｘ）の演算はσ（Ｘ）、σ。

（Ｘ）、ω（Ｘ）のために３回必要である。

４）誤り訂正の実行 ｒ’ｎ−＋＝ｒｎ−ｒ＋ｅｎ−＋（４）ただしσ（α−
ｎ＋１）≠０のときｅｎ−皿＝０゜σ（α−ｎｉｌ　）
　ｘ　Ｏのときｅｎ−１−ω（α−ｎ＋１）／σ゛　（
α−ｎ＋１） また、消失誤り訂正に対しては上記の１）〜４）の他に
次の５）、６）の演算が必要である。

５）消失位置多項式の生成 ８個の消失位置ｊ１．ｊ２．・・・、ｊＳに対しＹ　、
　ｘα”（ｉ＝１．２．・・・、ｓ）とし、消失位置多
項式 ％式％ ６）消失位置多項式とシンドローム多項式の乗算 Ｓ　（ｘ）　−５（ｘ）　＊λ（ｘ）　　　（６）この
Ｓ　（ｘ）を２）においてＢＯとして用いる。

また符号化に関しては次の演算が必要である。

７）符号化 情報系列Ｉ　（Ｘ）　”　（Ｉｋ−＋　、　　Ｉｋ−ｚ
　、　”・。

ＩＯ）及び、生成多項式ｇ　（ｘ）＝ｇ＋＋＋　＊ｘ”
＋ｇ、−＋　＊ｘ”−’　＋・　＋ｇ、からパリティＰ
（Ｘ）を生成する。（ｍ＝２ｔ）ただし、Ｐ”　（ｘ）
＝Ｉ　　（ｘ）＊ｘ”　　　ｎｏｄｇ　　（ｘ）　　　
　（７） 以上のような演算を実現する上で大きな訂正能力を持つ
Ｒ５符号化・復号処理の装置化は、装置の規模及び制御
が非常に複雑かつ大規模になるため非常に困難であった
。

しかし、近年の半導体技術の進歩によフて複雑かつ大規
模な装置のＶＬＳ　Ｉ化が可能となった。

このときＶＬＳ　Ｉの特徴を生かしたアルゴリズムを考
えることは重要である。シストリック・アルゴリズムは
Ｋｕｎｇらによって提案されたＶＬＳＩ向きアルゴリズ
ムである。今まで、１）〜７）のいくつかの処理につい
てシストリック・アルゴリズムによるＩＣセルの構成が
示されてきた。しかしそれらは１つの機能について独立
なセルとして設計されてきた。そのために１）〜７）の
処理毎に別々のセルを設計する必要があった。

〔発明が解決しようとしている問題点）本出願人が先に
出願した特願昭６１−３０５８９８号（以下、先願とい
う）においてＲ５符号化・復号において必要な次の１）
〜７）の処理を同−処理単位（プロセッシング・エレメ
ント。

Ｕ下ＰＥという）を用いてシストリックに実現した。

先願に示したアーキテクチャではＩＰＥＱ位にＩＣセル
化した場合、１）〜７）の処理毎にＩＣセルを設計する
必要はない。その点において先願に示したアーキテクチ
ャは汎用性を持つアーキテクチャであると言える。しか
し先願に示したアーキテクチャはｌ）〜７）の処理を同
−ＰＥを用いてシストリックに実現しているが、処理毎
にＰＨの接続と制御を変えなければならない。ＩＰＥＪ
ＩＬ位にＩＣ化し、接続を外部的に与えたとしても処理
に対して接続は固有であるので１つのＰＥは他の処理を
行うことができない。

従って先願に示したアーキテクチャは、真に汎用性を持
つアーキテクチャとは言えなかった。

そのために、消失誤り訂正５）、６）を行おうとする場
合、５）、６）の処理用のＰＥが必要となり、通常のＲ
Ｓ符号復号器で消失誤り訂正を処理することができなか
った。

また、先願のようにＰＥ内のレジスタ段数を増して、回
路の小型を図る場合、レジスタ段数ｍは２ｔ（ｔは訂正
能力）を上限とするため、限界があった。

〔問題点を解決するための手段（及び作用）〕図１のよ
うにＰＥを構成することによって、１）〜フ）の処理を
区別することなく行えるようにした。これによって、Ｐ
Ｅを処理によって多重に用゛いることによる回路の小型
化が行える。

また、先願と同様に図１に示すＰＥを図２のようにする
ことによっても回路規模の小型化が行える。

〔実施例〕

第１図に本発明による基本ＰＥを示す、第１図において
は、１は多入力多出力のセレクタ（ＭＵＸ）であり、２
．３は（ガロア体上の）乗算器であり、４は（ガロア体
上の）加算器である。

ガロア体ＧＦ　（２”）上の原始多項式Ｐ　（ｘ）”Ｘ
’　＋Ｘ’　＋Ｘ３＋ｘ”−４−１による乗算器を考え
た場合、２．３は第１３図のように実現され、４はＥＸ
ＯＲ回路（８個）によって実現される。

５〜１１はクロックＣＫによって動作するレジスタであ
る。

第１１図は回路の小型化のため、レジスタ段１２〜１４
を挿入した拡張ＰＥである。１２〜１４のレジスタ段数
をｍ−１とした時、全体の処理は１／ｍに分解され、冗
長なＰＥの数も第３図〜′Ｍ９図に示す。

１）まず、各ＰＥにα’　　（ｊツ１．・・−，２ｔ）
をｓｅｔするために、ＣＫの転送レートで＃１のＰＥの
へ入力にα１をα〜α２ｔの順に入力する。

各ＰＥはＳｌ、、５禦０２（以下、セレクタ選択信号Ｓ
１．．５の値はＭＥＸで表わす）に制御され、Ｗ出力か
らＡ入力のα’　　（ｊ−１゜・・・、２ｔ）が１クロ
ック遅れで出力される。

各ＰＥに設定すべきα１の値が来た時、Ｓｌ、、５＝０
３とすることによって、レジスタ５゜１１にαｊ及び１
が設定される。α４設定後はＳｌ、、５＝０２に戻す。

次に演算中は受信語ｒ　ｎ−２を１周期（レジスタ段数
をｍとした時ｍｘｃｋ倍）毎に転送し、制御も１周期毎
に行うｏｒｌｌ−息　（ｉ冨１．・・・、ｎ）において
、ｉｗｌの時、Ｓｌ、、５−００とし、Ｘから初期値ｚ
ｏ−０が出力され、ｚ、ｘｚｉ−。

・α’　＋　ｒ　ｎ−ｓ　＝　ｒｎ−ｓ　　（■）が計
算される。

ｉ＃２．・・・、ｎまでは通常ｓ１．．５−０１として
、前演算結果Ｚ　Ｉ−１をＤ入力からＸ出力にフィード
バックすることによりて■の演算を行う。

ｉ＝ｎの時、＃ｊのＰＥのレジスタ８にシンドローム係
数ｓＪが構成される。次の符号語を処理するためにその
Ｓ　Ｊ−１を次のクロックｉｘｌでレジスタ９に移す、
各ＰＥを順次Ｓ１．．５＝０２とすることによってレジ
スタ９のＳ　Ｊ−１がＺ出力から出力され最後のＰＥか
らシンドローム多項式Ｓ　（ｘ）の係数が順次出力され
る。

ただし、受信１１１ｒ１１−ｊはレジスタ１０＆びレジ
スタ列１４によって、１周期遅れで次のＰＥへ転送され
ている。

２）まず＃０のＰＥをＳｌ、、５冨０４として、Ａ、Ｂ
入力からＡ（λ）、Ｂ（Ｘ）を入力する。

ｉｗｌの時入力される多項式Ａ　（ｘ）及びＢ（Ｘ）の
最高次数係数β、αを、各々レジスタ１１．５に設定す
る（ｉ冨１）、ｌ−２，−・・。

２ｔの時Ｓ１．．５−０８として、演算Ｃ（ｘ）冨α・
Ａ　（ｘ）＋β・Ｂ　（ｘ）をレジスタ８及びレジスタ
列１３を通してｘｙから出力する。その時レジスタ６．
１０及びレジスタ列１２．１４の値をフィードバックし
て、Ｗ、ｚ出力から出力することによって、Ｃ（ｘ）と
最高次数をそろえてＡ　（Ｘ）　、　Ｂ　（ｘ）が次の
ＰＨに入力される。

以下、＃ｉのＰＥを前Ａ　（ｘ）、　Ｂ　（ｘ）。

Ｃ（ｘ）の次数から適当なモード（ｎｏｐ。

ｒｅｄｕｃｅＡ、ｒｅｄｕｃｅＢ）で制御し、上記の演
算を繰り返す（アルゴリズムの詳細は先願に示す）。

以上の演算を第１０図のように全体的にフィードバック
して２ｔ＋２回繰り返すことによりて、Ａ　（ｘ）とＢ
　（ｘ）の最大公約多項式が求められる。ただし、２ｔ
＋２回目の処理はｄｅｇＡ＜ｔかｄａｇＢ＜ｔの判定の
みのために必要であり、ｄａｇＡ＜ｔの時ｎｏｐ、ｄｅ
ｇＢ＜ｔの時ｎｏｐ’　　とする。

３）３）ではレジスタ列！３は省略される。

ｉ＝１．ｊ冨１の時Ｓｔ、、５−ＩＣとしてＡ人力のｆ
　ｔ−ＪをＸに出力し、レジスタ６に人力する。その時
Ｃ入力ｌはＺ。−０，Ｂ入力からはａ””’　（ｉ　ｘ
　１　）が入力され、Ｚｌ　−Ｚｏ　−ａ　”’　＋　
ｆ　ｔ−ｊが演算される。ｊ＝２〜ｔはＳｌ、、５＝Ｉ
ＤとしてＺ　Ｉ−１をＤ入力からフィードバックするこ
とによつて演算を行う。

ｉ　ｚ　２−ｎ、　ｊ　ｗ　１の時、通常３１．．５＝
１゜ｊ　＝＝　２・−１の時Ｓ１．．５−ＩＦとするこ
とによッテＺ　Ｉ＝　Ｚ　＋−＋　Ｃｘ−”’＋　ｆ　
ｔ−Ｊ　ｃ７）演算を行い、ｊ＝ｔの時最後のＰＥから
ｆ（α−ｎ＋１）の値が出力される。

４）通常Ｓｔ、、５＝１１とし、ｒ’ｎ−１＝ｒｎ−１
＋Ｏを演算し、出力する。

誤り位置の時、ｓｉ、、５−１０とすることによって、
ｒ’　Ｂ−１””　ｒｎ−１＋　（ｔ）　（（！−”’
）　／α′　（α−００１）を演算し、誤り訂正を行う
。

誤り位置の検出はａ　（ａ−”’）　＝０　（ｉ　＝　
１　。

・・・、ｎ）の時に行われ、これによって５１を制御す
る。

ここではレジスタ列は遅延させるだけで、演算には関与
しない。

５）まず、ＹＪ　　（ｊ＝１．　・・・２ｔ）の設定の
ため＃１のＰＥの大入力にＹＪをＹ１〜Ｙ２ｔの順に人
力する。ｉ＝１の時Ｓ１．．５＝１４とすることによっ
て、Ａ入力からのＹＪ　　（ｊ＝１・・・２ｔ）がレジ
スタ５に設定される。Ｃ人力かｉはＺ　Ｊ−１が入力さ
れ、セレクタのＺ出力を通してレジスタ９に入力される
。レジスタ９の出力は次のクロックでＹ（セレクタ）に
出力されＺｌ”Ｚｌ−１・Ｙ　Ｊ　　−Ｘ　＋　Ｚ　　
Ｉ−１が演算される。その出力はレジスタ８及びレジス
タ列１３に入力され、１周期遅れで次のＰＥに入力され
る。ただし、レジスタ５，１１の設定値は２ｔクロック
間保持される。以上の動作を８回繰り返すことによって
消失位置多項式λ（１）が求まる。ただし、ＰＥが８以
下の時は、第１０図のように全体的にフィード・パック
することによって演算等が行われる。

６）＃１のＰＥのＢ入力にシンドローム多項式Ｓ　（ｘ
）の係数がＳ　２ｔ−ＩＦ−Ｓ　Ｏの順に人力され、同
時に、Ｅ入力からはえ（Ｘ）の係数がλ２ｔ〜λ。の順
に入力されるとする。Ｃ入力からはＺ　ｌ−１の入力が
入力されるが＃１のＰＥでは２０＝０であるのでＯが入
力される。

ｉ＝１の時Ｓ１．．５−１２とし、レジスタ５．１１に
各々設定値、１及びＳ　２ｔ−」のＰＥについて設定さ
れる。。ｉ＝２以降、Ｓｌ、、５＝１３とすることによ
りて１及びＳ　２ｔ−Ｊの順に保持される。

Ｘは常にＣ入力Ｚ　ｌ−１を出力する。Ｙはｉｚｌの時
０．ｉ−２以降、Ｅ入力λ（ｘ）をレジスタ９で１クロ
ック遅らせたものを出力することによつて多項式Ｚ　　
ｌ−１に対し、１次低い形のλ（Ｘ）となる。

これによって、Ｚ、＝Ｚ、−，・Ｘ＋λ（Ｘ）・Ｓ　２
ｔ−Ｊが順次演算され、最後のＰＥから演算結果である
λ（Ｘ）　・Ｓ　（ｘ）が出力される。

以上の演算を第１０図のように全体的にフィードバック
することによって必要回数演算する。

７）情報１　（Ｘ）　”　（■に−＋　１　　Ｉ　Ｈ−
２＋　・・・。

１ｏ）をＡ（ｘ）、生成多項式　ｇ（ｘ）＝Ｘ”　＋　
ｇｓ−１’　Ｘ”−’　＋＝・ｇ　１・Ｘ＋　ｇｏをＢ
　（ｘ）と考える。パリティＰ　（ｘ）はＡ　（ｘ）を
Ｂ　（ｘ）で割った余りであるので、その動作は２）に
おけるｒｅｄｕｃｓＡの動作に同様になる。

ただし、簡単のために入出力はＣＫの転送レートで行わ
れるとし、第１０図のように、フィードバックによって
必要回数計算を行う。

〔他の実施例〕

このアーキテクチャにおいてレジスタ列をＲＡＭとして
図１２のようにすることによって回路構成だけでなく処
理速度においても固定的でないアーキテクチャとするこ
とができる。図１１においてレジスタ列で構成した場合
、１度ＰＥが設計されるとレジスタ段数ｍは固定となっ
て処理速度が定まってしまう。

そこでＲＡＭアドレスのＯＮｍ−１を任意に用いること
により真に汎用性のあるガロア体上の演算ＰＥとなる。

第１１図及び第１２図のＰＥによるシステム構成を第１
０図に示す。コントロール回路でＰＨの制御を切替名だ
けで汎用性のある演算機が構成できる。

〔発明の効果〕

以上、説明したようにこれによって、次のような効果を
持つ。

Ｉ）３章のアプローチでは各処理毎にＰＥが必要であり
、ｍ−２を以上の小型化はできなかった。

このアーキテクチャによってＰＥを多重に用いることに
より更なる回路の小型化が行える。ただし全体の処理速
度は更に低下する。

ＩＩ）２）、５）、６）の処理に対してＰＥを多重に用
いることによって回路規模を増大させずに消失誤り訂正
が行える。ｎ＞＞ｔのとき処理速度は低下しない。

ＩＩＩ　）ある定まった個数のＰＥに対してそれ以上の
訂正能力を処理させる場合、ＲＡＭを多段的にまたはＰ
Ｅを多重的に用いることによって対処できる。

■）ある定まった個数のＰＥに対してそれ以下の訂正能
力を処理させる場合、ＲＡＭを用いないことによってレ
ジスタ段数による遅延をなくし処理終了までの遅延時間
を短縮することができる。

【図面の簡単な説明】

第１図は本発明の基本ＰＥの説明図、 第２図は本発明の図１１のＰＥの接続図、第３図は本発
明の図１１のＰＥによるシンドローム生成用入出力図、 第４図は本発明の図１１のＰＥによるＧＣＤ生成用入出
力図、 第５図は本発明の図１１のＰＨによる多項式の値生成用
人出力図、 第６図は本発明の図１１のＰＥによる誤り訂正用入出力
図、 第７図は本発明の図１１のＰＨによる消失位置多項式生
成用入出力図、 第８図は本発明の図１１のＰＨによる乗算用入出力図、 第９図は本発明の図１１のＰＥによる符号化用入出力図
、 第１０図はシステム構成図、 第１１図は本発明のレジスタ段を示す図、第１２図は本
発明のＲＡＭによる拡張ＰＥ説明図、 Ｎ１３図はガロア体上の乗算器の例を示す図である。 １・・・セレクタ、 ２．３・・・乗算器、 ４・・・加算器、 ５〜１１・・・レジスタ、 １２〜１４・・・レジスタ列、 １５〜１７・・・ＲＡＭ。

Claims (1)

【特許請求の範囲】
1. （１）セレクタとレジスタと論理回路を１つの単位とす
   る回路を複数用いて規則的に構成し、各単位回路のセレ
   クタ制御を演算に応じて変更することによって種々の演
   算を行う回路において、レジスタ段数を増加させること
   によって用いる単位回路の数を減じることを特徴とする
   リード・ソロモン符号化・復号方式。