JPH04205434A - リードソロモン符号誤り訂正装置とガロア体乗算装置 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 産業上の利用分野 本発明は、コンピュータの外部記憶装置などにデータの
信頼性向上のため用いられるリードソロモン符号の誤り
訂正装置と、そのガロア体上の乗算装置に関するもので
ある。

従来の技術 近年、ハードディスクのバックアップ用途などのために
、磁気テープによるディジタルデータ記録装置の大容量
化が進んでいる。これらの装置では大容量化に伴い、記
録再生するデータの信頼性を向上させるためリードソロ
モン符号による誤す訂正装置が採用されるようになって
きた。

以下に、従来のリートソロモン符号誤り訂正装置と、そ
れに用いられるガロア体乗算装置とについて説明する。

第８図は、この従来のリードソロモン符号誤り訂正装置
とガロア体乗算装置の構成を示すブロック図である。

第８図において、４０１は磁気テープ再生部、４０２は
磁気テープ再生部４−０１の出力である再生データを受
信リードソロモン符号として受信し、その誤り位置を検
出する誤り位置検出部、４ｏ３は誤り位置検出部４０２
から受信リードソロモン符号を受は記憶する受信符号メ
モリ、４０４は誤り位置検出部４０２が検出した誤り位
置情報を入力する誤り位置情報入力部、４０５は受信メ
モリ４０３に記憶された受信リードソロモン符号に対し
符号生成多項式を法とする剰余を算出する剰余算出部、
４０６は算出された剰余を記憶する剰余記憶メモリであ
る。４０７は誤り位置情報入力部４０４から与えられる
誤り位置情報から符号訂正行列を算出するＣＰＵ１４０
８はＣＰＵ４０７のプログラムとガロア体指数変換テー
ブルと対数変換テーブルとを記憶したり一ドオンリメモ
リ（以下ＲＯＭと略す）、４０９はＣＰＵ４０７から与
えられる符号訂正行列と剰余記憶メモリ４０６に記憶さ
れた前記剰余に基づき受信符号メモリ４０３に記憶され
た前記受信リードソロモン符号の誤りを訂正する誤り訂
正部である。

以上のように構成された従来のリードソロモン符号誤り
訂正装置とガロア体乗算装置とについて、以下その動作
を説明する。ます、磁気テープ再生部４０１は磁気テー
プからデータを再生し、受信リードソロモン符号として
誤り位置検出部４０２に転送する。第９図は受信リード
ソロモン符号の構成を示す構造図である。第９図で、受
信リードソロモン符号の符号長は３８シンボル、パリテ
ィ長しは６シンボル、符号間距離Ｌ＋１は７であり、ま
たこの例では第８番シンボルと第す番／ンボルに誤りが
あることを示している。誤り位置検出部４０２は受信リ
ードソロモン符号を検査して、第８番シンボルと第す番
シンボルに誤りがあることを検出した後、検査済みの受
信リードソロモン符号を受信符号メモリ４０３に転送し
、検出した２個の誤り位置を誤り位置情報入力部４０４
に転送する。誤り位置情報入力部４０４では、２個の誤
り位置ａｔ　　ｂに対し、誤り位置情報のガロア体表現
であるＸＩ Ｘ　＋　＝α・　　　　　　　　　　　　　　・・・（
１）Ｘ　２”α５　　　　　　　　　　　　　　・・・
（２）を求め、ＣＰＵ４０７に伝達する。一方、剰余算
出部４０５は第９図に示す受信リードソロモン符号の多
項式表現であるＩ　（ｘ）は Ｉ（Ｘ）＝Ｗ３ｓＸ”＋ＷａｔＸ”＋−＋Ｗ＋ＸＩＩ　
・・・（３）を符号生成多項式Ｇ　（ｘ）で除算した余
り、即ち剰余多項式Ｒ（ｘ）は Ｒ（ｘ）＝Ｒｓｘ６＋Ｒ６ｘ’十−＋Ｒ＋ｘ’　　　　
・−・（４）の各項の係数である剰余Ｒ，を求め、剰余
記憶メモリ４０６に記憶させる。ＣＰＵ４０７は誤り位
置情報入力部４０４から得た誤り位置情報Ｘ１がら符号
訂正行列Ｈを演算し、誤り訂正部４０９に訂正行列Ｈと
誤り位置情報Ｘ１とを転送するとともに、誤り訂正処理
の開始を指示する。誤り訂正部４゜９は訂正行列Ｈと誤
り位置情報Ｘ１とに基づき、誤りパターンＹ１を（５）
式に従って算出し、Ｙｉと誤り位置情報Ｘ１が示す位置
の符号シンボルｗ１゜、×１とのガロア体上での加算を
求めることにより誤りを訂正する。第９図の例では誤り
を含む符号シンボルＷ、とＷ、とか、それぞれ誤りパタ
ーンＹ、とＹ２とによって訂正される。

し ただし、（５）式においてｈｌｌは符号訂正行列Ｈの第
ｉ行第ｊ列要素である。

次にＣＰＵ４０７の前記符号訂正行列Ｈの算出動作につ
いて以下に説明する。ＣＰＵ４０７は（６）式、（７）
式および（８ン式にしたがって符号訂正行列Ｈの要素ｈ
ｌ、を算出する。

ｈ＋＋＝Ａ（ｊ−１）／　（（α」−＋　＋　Ｘ　＋　
）Ｅ　（＋））・・・（６）に Ａ（ｋ）＝　　ｒＩ　（α’＋Ｘ１）　　　　　　　　
　−（７）ｉ＝１ Ｅ（１）＝　ＩＴ　（Ｘ、＋Ｘ、）　　　　　　　　・
・・（８）ｋ≠１ 一方、受信符号Ｗ１に於けるシンドロームＳ１と誤り位
置情報Ｘ１と誤りパターンＹ、との関係は、ＳＩ＝Σ　
Ｘ　ｈ　’　−’　Ｙ　ｋ　　　　　　　　　　・・・
（９）ｋ＝ま ただし、１　：Ｌ　　２ｒ　　・・・、Ｌで与えられ、
またシンドロームｓＩと剰余Ｒ１との関係は、 Ｓ＋＝　　Σ　α〔１−１１ｆｋ−１１Ｒ，、、、（Ｉ
Ｑ）ｋ＝１ で与えられるが、（９）式と（１０）式からシンドロー
ムＳ＋を消去し、（６）式を用いて整理すれば（５）式
が導かれる。即ち、ＣＰＵ４０７が（６）式で算出する
ｈ＋１は符号訂正行列Ｈの要素であり、誤り訂正部４０
９に（５）式を実行させることにより受信リードソロモ
ン符号の誤り訂正を実現することとなる。

ＣＰＵ４０７は（６）式、（７）式、（８）式の演算を
実行するためにガロア体上での乗算演算をソフト的に実
行するが、以下にそのガロア体乗算アルゴリズムについ
て説明する。

第１０図は（６）式、（７）式の演算に用いられる多変
数乗算のアルゴリズムを示すフローチャートであり、第
１表はＲＯＭ４０８に記憶されているガロア体上の対数
変換テーブルを、第２表は同じ＜ＲＯＭ４０８に記憶さ
れているガロア体上の指数変換テーブルをそれぞれ示す
。

（以下、余白） 第１表　ガロア体上の対数変換テーブル第２表　ガロア
体上の指数変換テーブル第１０図では変数ＺＩに対し、
ＺＩからＺＮの乗算結果を変数Ｑに代入する動作を、す
なわち、Ｑ”　ＩＴ　ＺＩ　　　　　　　　　　　　　
・・・（１１）１＝１ を示している。ＣＰＵ４０７はステップ４０１で指標変
数ｉとＣＰＵ４０７内蔵の演算レジスタＡＣＣとを初期
化し、ステップ４０２で第１表に示す対数変換テーブル
を検索してＺｌのガロア体上の対数変換を実行し指数ｎ
を求め、ステップ４０３で演算レジスタＡｃｅに指数ｎ
を加算する。Ｚｌと指数ｎとの関係は Ｚ＋＝ａ’ｔ　　ｎ＝　ｌ　ｏ　ｇＺ＋　　　　　　　
・（１２）である。ＣＰＵ４０７はステップ４０５で指
標ｉを増加させながらステップ４０２とステップ４０３
を繰り返し、被乗算数Ｚ、からＺＨの指数部の総和を求
める。ステップ４０４でｉ＝Ｎとなったことを検知する
とステップ４０６で演算レジスタＡＣＣの整数２５５を
法とするモジュロ演算を求め、ステップ４０７で第２表
に示す指数変換テーブルを検索して演算レジスタＡｃｃ
の示す値のガロア体上の指数変換を実行し、その結果で
あるαＡｏａを変数Ｑに代入し乗算処理を終了する。以
上の動作によって、被乗算数Ｚ＋からＺＮの指数部の総
和をガロア体上のべき乗に変換することとなり、（１１
）式のガロア体乗算が実現されている。

第１１図は（８）式の演算を実現する多変数乗算のアル
ゴリズムを示すフローチャートである。第１１図のアル
ゴリズムでは指標ｉは初期値として与えられている。Ｃ
ＰＵ４０７はステップ４１１で指標にと演算レジスタＡ
ｃｃを初期化し、ステップ４１２でに≠ｉであると判断
するとステップ４１３でＸｋとＸｉのガロア体上の和の
指数部ｎをステップ４０２と同様の対数変換で求め、ス
テップ４１４で演算レジスタＡｃｃに指数ｎを加算する
。ＣＰＵ４０７はステップ４１５で繰り返しループが未
完了であると判断するとステップ４１６で指標ｋを増加
させステップ４１２からステップ４１４を繰り返す。ス
テップ４１５で繰り返しループが完了したと判断すると
ステップ４１７．ステップ４１８でステップ４０６．ス
テップ４０７と同様の指数変換を求め、その結果を乗算
結果として変数Ｅ（１）に代入し乗算処理を終了する。

ここで、ステップ４１２でに＝ｉの場合の乗算が除外さ
れているから第１１図のアルゴリズムで（８）式のガロ
ア休演算が実現されている。

以上のように従来例では、誤り位置検出部４０２が検出
した誤り位置情報を基にＣＰＵ４０７が符号訂正行列Ｈ
を演算することにより受信リードソロモン符号の誤り訂
正を実現している。また、符号訂正行列Ｈの演算はガロ
ア体乗算アルゴリズムを用いることにより実現されてい
る。

発明が解決しようとする課題 しかしながら上記従来の構成では、誤り位置検出部４０
２が受信リードソロモン符号の正確な誤り位置検出に失
敗し、１つでも正しい誤り位置情報が不足した場合、Ｃ
ＰＵ４０７は不足した誤り位置情報を求めることができ
ないため、訂正不能に陥ってしまうという問題点を有し
ていた。また、ＣＰＵ４０７の訂正行列演算に用いるガ
ロア体乗算においてはステップ４０６．ステップ４１７
の２５５を法とするモジュロ演算や、処理ループ中にあ
るため繰り返し実行されるステップ４１２の条件判別を
有する指標処理など、ＣＰＵに多大の処理時間が掛かる
という問題点も有していた。

本発明は上記従来の問題点を解決するもので、誤り位置
情報入力部が誤った誤り位置情報を入力した場合にも正
しい誤り位置情報を１つ演算することができるリードソ
ロモン符号誤り訂正装置と、ＣＰＵのガロア体乗算処理
を短時間で実現するガロア体乗算装置とを提供すること
を目的とする。

課題を解決するための手段 この目的を達成するために本発明のリードソロモン符号
誤り訂正装置は、誤り位置情報入力手段と、剰余算出手
段またはシンドローム算出手段と、剰余またはシンドロ
ーム記憶メモリと、中間変数算出手段と、中間変数記憶
手段と、誤り位置算出手段とを具備してなる構成である
。

また、この目的を達成するために本発明のガロア体乗算
装置は、桁上げフラグを含−めたの整数加算機能を有す
るＣＰＵと、指数変換テーブルと対数変換テーブルを記
憶するメモリと、指数変換手段と対数変換手段とを具備
してなる構成である。

作用 本発明のリードソロモン符号訂正装置は上記した構成に
より、誤り位置情報入力部が入力した受信リードソロモ
ン符号の誤り位置情報に不足がある場合にも、訂正行列
算出中に発生した中間変数と、剰余算出手段またはシン
ドローム算出手段が算出した受信リードソロモン符号の
剰余またはシンドロームとから、ＣＰＵが新たな正しい
誤り位置情報を１つ算出するものである。

また、本発明のガロア体乗算装置は上記した構成により
、被乗算数の指数部加算を桁上げフラグを含めた整数加
算で実行するから逐次等価的に２５５を法とする加算を
実現することとなり、多大な処理時間を要するモジュロ
演算を不要とするとともに、指標処理を単純化し、ガロ
ア体乗算処理を短時間で実現するものである。

実施例 以下、本発明の実施例について、図面を参照しながら説
明する。

第１図は発明の第１の実施例におけるリードソロモン符
号誤り訂正装置とガロア体乗算装置の構成を示すブロッ
ク図である。

第１図において、１０１は磁気テープ再生部、１０２は
磁気テープ再生部１０１の出力である再生データを受信
リードソロモン符号として受信し、その誤り位置を検出
する誤り位置検出部、１０３は誤り位置検出部１０２か
ら受信リードソロモン符号を受は記憶する受信符号メモ
ＩＪ、１０４は誤り位置検出部１０２が検出した誤り位
置情報を入力する誤り位置情報入力部、１０５は受信符
号メモリ１０３に記憶された受信リードソロモン符号に
対し符号生成多項式を法とする剰余を算出する剰余算出
部、１０６は算出された剰余を記憶する剰余記憶メモリ
である。１０７は誤り位置情報入力部１０４から与えら
れる誤り位置情報から符号訂正行列を算出するＣＰＵ１
１０８はＣＰＵ　１０７のプログラムとガロア対指数変
換テーブルと対数変換テーブルとを記憶したＲＯＭ１１
０９はＣＰＵ１０７の演算処理中に発生した中間変数を
記憶スるランダムアクセスメモリ（以下ＲＡＭと略す）
、１１０はＣＰＵ１０７から与えられる符号訂正行列と
剰余記憶メモリ１０６に記憶された剰余に基づき受信符
号メモリ１０３に記憶された受信リードソロモン符号の
誤りを訂正する誤り訂正部、１１１は誤り訂正部１１０
の訂正処理に於いて誤訂正があったことを検出する誤訂
正検出部である。

以上のように構成された本発明のリードソロモン符号誤
り訂正装置とガロア体乗算装置とについて、以下その動
作を説明する。ます、磁気テープ再生部１０１は磁気テ
ープからデータを再生し、受信リードソロモン符号とし
て誤り位置検出部１０２に転送する。第２図は受信リー
ドソロモン符号の構成を示す構造図である。第２図で受
信リードソロモン符号は上述した従来例と同じく符号長
は３８シンボル、パリティ長りは６シンボル、符号間距
離Ｌ＋１は７であり、またこの例では第８番シンボルと
第す番シンボルと第０番シンボルとに誤りがあることを
示している。誤り位置検出部１０２は受信リードソロモ
ン符号を検査して、前記第８番シンボルと第す番シンボ
ルに誤りがあることを検出したが、何らかの原因によっ
て第０番シンボルの検出に失敗したとする。誤り位置検
出部１０２は検査後の受信リードソロモン符号を受信符
号メモリ１０３に転送し、検出できた２個の誤り位置を
誤り位置情報入力部１０４に転送する。

誤り位置情報入力部１０４では、２個の誤り位置ａ、　
　ｂに対し、誤り位置情報のガロア体表現であるＸ＋（
１）式、（２）式を求め、ＣＰＵ１０７に伝達する。一
方、剰余算出部１０５は受信リードソロモン符号の符号
生成多項式Ｇ（ｘ）を法とする剰余Ｒｉを求め、剰余記
憶メモリ１０６に記憶させる。

ＣＰＵ１０７は誤り位置情報入力部１０４から得た誤り
位置情報Ｘ１から（６）式、（７）式、（８）式に基づ
き符号訂正行列Ｈを演算し、中間変数Ａ（ｋ）をＲＡＭ
１０９に記憶させ、誤り訂正部１１０に符号訂正行列Ｈ
と誤り位置情報Ｘ１とを転送するとともに、誤り訂正処
理の開始を指示する。

誤り訂正部１１０は符号訂正行列Ｈと誤り位置情報Ｘ、
とに基づき、受信リードソロモン符号の誤り訂正を実行
することは上記従来例と同じである。

しかしながら、この例では符号シンボルの３つの誤りに
対して、Ｌ、Ｘ２の２つの誤り位置情報のみによる訂正
を実行しているから誤訂正が発生する。誤訂正検出部１
１１は、この誤訂正を検出するとＣＰＵ１０７に誤訂正
発生を報告する。ＣＰＵ１０７は誤訂正検出部１１１か
らの誤訂正報告を受けると誤り位置算出処理を実行し、
第０番シンボルを意味する新たな１つの誤り位置情報Ｘ
３を求め、既知の誤り位置情報Ｘ＋、Ｘａと合わせて再
度前記符号訂正行列Ｈの算出から再試行することによっ
て、第８番シンボル、第す番シンボル、第０番シンボル
を正しく訂正することとなる。

次に、ＣＰＵ１０７の誤り位置算出処理の動作について
以下に説明する。ＣＰＵ１０７は（１３）式。

（１４）式にしたがって新たな誤り位置情報ＸＭ４１を
算出する。

ｊ＝Ｉ　　　　　　　　Ｊ＝ま ただし、Ｂ　（ｊ）＝　Ａ　（Ｌ−ｊ）Ｒｔ−＋−＋　
　　　・・・（１４）Ａ　（ｋ）はＲＡＭ１０θに既に
記憶されている中間変数であり、その定義は（７）式に
示されている。

一方、受信符号Ｗ１においてシンドロームｓＩと誤り位
置情報Ｘ１と誤りパターンＹ、との関係は、ｋ＝１ である。ここで、誤り位置情報Ｘ、からＸＮまでのＭ個
の変数は既知であり、誤り位置情報Ｘｎ。１と誤りパタ
ーンＹＩからＹ　Ｎ４１までのＭ＋２個の変数が未知で
ある。ＳｉからＳｎ＋２までのＭ＋２個の方程式からＹ
、を消去し、更にシンドロームＳ１と剰余Ｒ１との関係
式（ｌＯ）式を代入して（１３）式、　　（１４）式が
導かれる。即ち、ＣＰＵ１０７が（１３）式で算出する
Ｘ　Ｎ　４１は誤り位置検出部１０２が検出に失敗した
誤り位置情報であり、このＸｉ、、と既知のＸ、からＸ
ｎとを用いて符号訂正行列Ｈを再度求めることにより受
信リードソロモン符号の正確な誤り訂正を実現すること
となる。

ＣＰＵ１０７は（６）式、（７）式、（８）式更に（１
３）式、　　（１４）式の演算を実行するためにガロア
体上での乗算演算をソフト的に実行するが、以下にその
ガロア体乗算アルゴリズムについて説明する。

第３図は（６）式、（７）式、　　（１３）式、　　（
１４）式の演算に用いられる多変数乗算やアルゴリズム
を示すフローチャートであり、第３表はＲＯＭ１０８に
記憶されているガロア体上の対数変換テーブルを、第４
表は同じ＜　ＲＯＭ　１０８に記憶されているガロア体
上の指数変換テーブルをそれぞれ示す。

第３表　ガロア体上の対数変換テーブル第４表　ガロア
体上の指数変換テーブル第３図では変数２１に対し、Ｚ
、からＺＮの乗算結果を変数Ｑに代入する動作を、（１
１，）式で示している。ＣＰＵ１０７はステップ１０１
で指標変数ｉとＣＰＵ１０７内蔵の８ピツト演算レジス
タＡｃＣと桁上げフラグＣＹを初期化し、ステップ１０
２で表３に示す対数変換テーブルを検索してＺｌのガロ
ア体上の対数変換を実行し指数ｎを求め、ステップ１０
３で演算レジスタＡｃｃに指数ｎと桁上げフラグＣＹと
を加算する。ＣＰＵ１０７はステップ１０５で指標ｉを
増加させながらステップ１０２とステップ１０３を繰り
返し、被乗算数Ｚ、からＺＨの指数部の総和を求める。

演算レジスタＡｃｅが８ビツトレジスタであるから２つ
の指数部の加算結果にその桁上げ結果を加算すると、２
５５を法とする剰余を求めたことと等価になる。

ステップ１０３では各加算処理毎に前回の加算結果の桁
上げフラグが加算されるから、前回の加算結果を２５５
を法とする剰余に修正したものに対して今回の加算を実
行することとになり、即ち、逐次モジュロ２５５補正を
実行していることとなる。ＣＰＵ１０７はステップ１０
４でｉ＝Ｎとなったことを検知するとステップ１０６で
演算レジスタＡｃｃに桁上げフラグＣＹを加算で最後の
モジュロ２５６補正を行い、ステップ１０７で表４に示
す指数変換テーブルを検索して演算レジスタＡｃｅの示
す値のガロア体上の指数変換を実行する。ステップ１０
６終了時点で、演算レジスタＡｃｃのとり得る値はＯか
ら２５５であり、２５５に関してのみモジュロ２５５補
正が成されていないが、表４の指数変換テーブルでは指
数２５５に対するガロア体の元を０、すなわちαのゼロ
乗と定義しているからステップ１０７の指数変換時点で
モジュロ２５５補正が成されることとなる。以上の動作
によって、被乗算数Ｚ、からＺＮの指数部の総和をモジ
ュロ２５５で求め、その結果をガロア体上のべき乗に変
換することとなり、（ＩＩ）式のガロア体乗算が実現さ
れることとなる。

第４図は（８）式の演算を実現する多変数乗算のアルゴ
リズムを示すフローチャートである。第４図のアルゴリ
ズムでは指標ｉは初期値として与えられている。ＣＰＵ
１０７はステップ１１１で指標にと演算レジスタＡｃｅ
と、桁上げフラグＣＹとを初期化し、ステップ１１２で
ＸｋとＸＩのガロア体上の和の指数部ｎを表３の対数変
換テーブルにより求め、ステップ１１３でステップ１０
３と同様に演算レジスタＡｃｃに指数ｎと桁上げフラグ
ＣＹとを加算する。ＣＰＵ１０７はステップ１１４で繰
り返しループ未完了であると判断するとステップ１１５
で指標ｋを増加させステップ１１２、ステップ１１３を
繰り返す。ステップ１１４で、繰り返しループが完了し
たと判断するとステップ１１６．ステップ１１７でステ
ップ１０６゜ステップ１０７と同様の指数変換を求め、
その結果を乗算結果として変数Ｅ　（１）に代入し乗算
処理を終了する。ここで、ステップ１１２でに＝ｉの場
合、 Ｘ＋＋Ｘｂ＝Ｘ＊＋Ｘ　ｋ＝　Ｏ・・・（Ｉ６）となる
が、第４表の対数変換テーブルでガロア体の元ゼロに対
する指数部をゼロと定義しているからガロア体上で１の
乗算と等価である。即ち、ｋ＝ｉの場合の乗算が除外さ
れたことなるから第４図のアルゴリズムで（８）式のガ
ロア休演算が実現されることとなる。

以上のように本実施例では、誤り位置検出部１０２が受
信リードソロモン符号の誤り位置検出を１つ失敗した場
合においても、ＣＰＵ１０７が（１３）式、　　（１４
）式に示す誤り位置情報算出処理によって正しい誤り位
置情報を算出するから訂正不能に陥らず受信リードソロ
モン符号を正しく訂正することができる。また、前記誤
り位置情報算出処理はガロア体上の線形演算であり、更
に演算に使用する変数Ａ　（ｋ）は既に訂正行列算出時
の中間変数として求められＲＡＭ１０９に保存されてい
るから僅かの簡単な演算で完了することができるもので
ある。また、これらの演算に用いられるガロア体乗算ア
ルゴリズムでは、指数変換テーブルと対数変換テーブル
に特殊な変換を定義し桁上げフラグを含めた指数部加算
を実行することにより、多大な演算時間を要するモジュ
ロ演算を排除でき、また指標処理を極めて単純化できる
ため、高速処理を実現することができるものである。

なお、第１の実施例において誤り位置情報入力部１０４
は前記誤り位置情報に対し、誤り位置情報のガロア体表
現であるＸｉを求めるとしたが、誤り位置情報入力部１
０４は前記誤り位置情報を入力し記憶するのみとし、Ｃ
ＰＵ１０７が誤り位置情報のガロア体表現であるＸ＋を
求める構成としてもよい。

また、第１の実施例において第３表の対数変換テーブル
と第４表の指数変換テーブルはＲＯＭＩｏ８に記憶され
ている構成としたが、ＲＡＭｌ０θ上にＣＰＵ１０７が
生成する構成としても良い。

更に、第１の実施例において第３図のガロア体乗算アル
ゴリズムは８ビツト演算レジスタを使用するものとした
が、第５図に示すように１６ビツト演算レジスタを用い
、２つの乗算数の指数部をそれぞれ演算レジスタの上位
バイトと下位バイトに代入して加算処理し最後に上位バ
イトと下位バイトを加算する構成としても良い。

第６図は、本発明の第２の実施例におけるリードソロモ
ン符号誤り訂正装置の構成を示すブロック図である。

第６図において、１０１は磁気テープ再生部、１０２は
磁気テープ再生部１０１の出力である再生データを受信
リードソロモン符号として受信し、その誤り位置を検出
する誤り位置検出部、１０３は誤り位置検出部１０２か
ら受信リードソロモン符号を受は記憶する受信符号メモ
ＩＪ、１０４は誤り位置検出部１０２が検出した誤り位
置情報を入力する誤り位置情報入力部、１０７は誤り位
置情報入力部１０４から与えられる誤り位置情報から符
号訂正行列を算出するＣＰＵ１１０８はＣＰＵ１０７の
プログラムとガロア対指数変換テーブルと対数変換テー
ブルとを記憶したＲＯＭ１１０９はＣＰＵ１０７の演算
処理中に発生した中間変数を記憶するＲＡＭ、１１０は
ＣＰＵ１０７から与えられる符号訂正行列に基づき受信
符号メモリ１０３に記憶された前記受信リードソロモン
符号の誤りを訂正する誤り訂正部、１１１は誤訂正検出
部であり、以上は第１図の構成と同様なものである。第
１図と異なるのは剰余算出部１０５に代えて受信リード
ソロモン符号に対するシンドロームを算出するシンドロ
ーム算出部２０５を剰余記憶メモリ１０６に代えて前記
シンドロームを記憶するシンドローム記憶メモリ２０６
を設けた点である。

以上のように構成された本発明のリードソロモン符号誤
り訂正装置について、以下その動作を説明する。まず、
磁気テープ再生部１０１は磁気テープからデータを再生
し、受信リードソロモン符号として誤り位置検出部１０
２に転送する。受信リードソロモン符号の構成は第１の
実施例と同様に符号長は３８シンボル、パリティ長しは
６シンボル、符号間距離Ｌ＋１は７であり、また第２図
の例では第３番シンボルと第す番シンボルと第０番シン
ボルとに誤りがあることを示している。誤り位置検出部
１０２は受信リードソロモン符号を検査して、第３番シ
ンボルと第す番シンボルに誤りがあることを検出したが
、何らかの原因により第０番シンボルの検出に失敗した
とする。誤り位置検出部１０２は検査後の受信リードソ
ロモン符号を受信符号メモリ１０３に転送し、検出でき
た２個の誤り位置を誤り位置情報入力部１０４に転送す
る。誤り位置情報入力部１０４では、２個の誤り位置ａ
、　　ｂに対し、誤り位置情報のガロア体表現であるＸ
ｉを求め、ＣＰＵ１０７に伝達する。

一方、シンドローム算出部２０５は受信リードソロモン
符号のシンドロームＳ＋を求め、シンドローム記憶メモ
リ２０６に記憶させる。ＣＰＵ１０７は誤り位置情報入
力部１０４から得た誤り位置情報Ｘｉから（１７）式、
　　（１８）式、　　（１９）式、（８）式に基づき符
号訂正行列Ｈを演算し、中間変数Ｃ（ｋ）をＲＡＭ１０
９に記憶させ、誤り訂正部１１０に符号訂正行列Ｈと誤
り位置情報ＸＩとを転送するとともに、誤り訂正処理の
開始を指示する。

ｈ　＋、＝　Ｆ　（Ｍ−ｊ”ｌ、ｉ）／　Ｅ　（１）　
　　　　　　・・・（１７）Ｆ　（ｋ、ｔ）＝　Ｃ（ｋ
−ｔ）十Ｘ　ＩＦ　（ｋ−ｔ、ｔ）　　　　・・・（１
８）Ｃ（ｋ）＝　　　Σ　　　　■　ＸｐＩ　　　　・
・・（１９）ｐｌ）ｐ２〉・・・）ｐｋ　　ｉ：ま ただし、Ｆ　（０，ｉ）＝　Ｏ・・・（２０）Ｃ（０）
＝１　　　　　　　　　　　・・・（２１）誤り訂正部
１１０は符号訂正行列Ｈと誤り位置情報Ｘ１とに基づき
、受信リードソロモン符号の誤り訂正を実行することは
上記従来例と同じである。

しかしながら、この例では符号シンボルの３つの誤りに
対して、Ｘ２．Ｘ２の２つの誤り位置情報のみによる訂
正を実行しているから誤訂正が発生する。誤訂正検出部
１１１は、この誤訂正を検出するとＣＰＵ１０７に異常
発生を報告する。ＣＰＵ１０７は誤訂正検出部１１１か
らの誤訂正報告を受けると誤り位置算出処理を実行し、
第０番シンボルを意味する新たな１つの誤り位置情報Ｘ
３を求める。既知の誤り位置情報Ｘ、、Ｘ２に新たなＸ
３を合わせて再度前記符号訂正行列の算出から再試行す
ることによって、第８番シンボル、第す番シンボル、第
０番シンボルを正しく訂正することとなる。

次に、ＣＰＵ１０７の誤り位置算出処理の動作について
以下に説明する。ＣＰＵ１０７は（２２）式にしたがっ
て新たな誤り位置情報Ｘ　ｎ　４１を算出する。

Ｊ＝Ｑ 一方、受信符号Ｗ１に於いてシンドロームＳ１と誤り位
置情報Ｘ＋と誤りパターンＹ１との関係は、ｋ＝１ である。ここで、誤り位置情報Ｘ、からＸｏまでのＭ個
の変数は既知であり、誤り位置情報Ｘ　Ｎ　４１と誤り
パターンＹ、からＹｌ、１４．までのＭ＋２個の変数が
未知である。ＳｉからＳＮ＋２までのＭ＋２個の方程式
からＹｋを消去して（２２）式が導かれる。即ちＣＰＵ
１０７が（２２）式で算出するＸＭ４１は誤り位置検出
部１０２が検出に失敗した誤り位置情報であり、このＸ
　ｎ　＋　＋と既知のＸ、からＸ、とを用いて符号訂正
行列Ｈを求めることにより受信リードソロモン符号の正
確な誤り訂正を実現することとなる。

以上のように本実施例では、誤り位置検出部１０２が受
信リードソロモン符号の誤り位置検出を１つ失敗した場
合においても、ＣＰＵ１０７が（２２）式に示す誤り位
置情報算出処理によって正しい誤り位置情報を算出する
から訂正不能に陥らず受信リードソロモン符号を正しく
訂正することができる。また、誤り位置情報算出処理は
ガロア体上の線形演算であり、更に演算に使用する変数
Ｃ（ｋ）は既に訂正行列算出時の中間変数として求めら
れＲＡＭ　１０９に保存されているから僅がの簡単な演
算で完了することができるものであり、高速に誤り位置
算出を実現することができるものである。

なお、第２の実施例においても第１の実施例と同様に誤
り位置情報入力部１０４は、誤り位置情報に対し、誤り
位置情報のガロア体表現であるＸｉを求めるとしたが、
誤り位置情報入力部１０４は誤り位置情報を入力し記憶
するのみとし、ＣＰＵ１０７が誤り位置情報のガロア体
表現であるＸｉを求める構成としてもよい。

第７図は本発明の第３の実施例におけるリードソロモン
符号誤り訂正装置の構成を示すブロック図である。

第７図において、１０１は磁気テープ再生部、１０２は
磁気テープ再生部１０１の出力である再生データを受信
リードソロモン符号として受信し、その誤り位置を検出
する誤り位置検出部、１０３は誤り位置検出部１０２か
ら受信リードソロモン符号を受は記憶する受信符号メモ
ＩＪ、１０４は誤り位置検出部１０２が検出した誤り位
置情報を入力する誤り位置情報入力部、１０７はＣＰＵ
１１０８はＣＰＵ１０７のプログラムとガロア対指数変
換テーブルと対数変換テーブルとを記憶したＲ０Ｍ、１
０９はＣＰＵ１０７の作業変数を記憶するＲＡＭ、２０
５は受信リードソロモン符号に対するシンドロームを算
出するシンドローム算出部、２０６はシンドローム記憶
メモリ、１１１は誤訂正検出部であり、以上は第６図の
構成と同様なものである。第６図と異なるのは誤り訂正
部１１０の代わりに、ＣＰＵ１０７から符号訂正行列を
与えられずとも、シンドローム記憶メモリ２０Ｂから与
えられるシンドロームと誤り位置情報入力部１０４から
与えられる誤り位置情報とから受信符号メモリ１０３に
記憶された受信リードソロモン符号の誤りを直接訂正す
る誤り訂正部３１０を設けたことである。

以上のように構成された本発明のリードソロモン符号誤
り訂正装置について、以下その動作を説明する。まず、
磁気テープ再生部１０１は磁気テープからデータを再生
し、受信リードソロモン符号として誤り位置検出部１０
２に転送する。受信リードソロモン符号の構成は第１．
第２の実施例と同様に符号長は３８シンボル、パリティ
長しは６シンボル、符号間距離Ｌ＋１は７であり、また
、同じく第２図の例では第８番シンボルと第す番シンボ
ルと第０番シンボルとに誤りがあることを示している。

誤り位置検出部１０２は受信リードソロモン符号を検査
して、第８番シンボルと第す番シンボルに誤りがあるこ
とを検出したが、何らかの原因によって第０番シンボル
の検出に失敗したとする。誤り位置検出部１０２は前記
検査後の受信リードソロモン符号を受信符号メモリ１０
３に転送し、検出できた２個の誤り位置を誤り位置情報
入力部１０４に転送する。誤り位置情報入力部１０４で
は、２個の誤り位置ａｌ　　ｂに対し、誤り位置情報の
ガロア体表現であるＸｉを求め、誤り訂正部３１０とＣ
ＰＵ１０７に伝達する。一方、シンドローム算出部２０
５は受信リードソロモン符号のシンドロームＳ１を求め
、シンドローム記憶メモリ２０６に記憶させる。誤り訂
正部３１０は誤り位置情報入力部１０４から得た誤り位
置情報Ｘ１と、シンドローム記憶メモリ２０６に記憶さ
れたシンドロームＳｉとから受信符号メモリ１０３に記
憶された受信符号を直接訂正処理しようとする。

しかしながら、この例では符号シンボルの３つの誤りに
対して、ＸＩ、Ｘ２の２つの誤り位置情報のみによる訂
正を実行しているから誤訂正が発生する。誤訂正検出部
１１１は、この誤訂正を検出するとＣＰＵ１０７に誤訂
正発生を報告する。ＣＰＵ１０７は誤訂正検出部１１１
からの誤訂正報告を受けると誤り位置算出処理を実行し
、第０番シンボルを意味する新たな１つの誤り位置情報
Ｘ３を求め、誤り位置情報入力部１０４に転送した後、
誤り訂正部３１０に再度訂正処理のやり直しを指示する
。誤り訂正部３１０は既知の誤り位置情報Ｘ＋＋　　Ｘ
２に新たなＸ３を合わせて再試行することによって、第
８番シンボル、第す番シンボル、第０番シンボルを正し
く訂正することとなる。

次に、ＣＰＵ１０７の前記誤り位置算出処理の動作につ
いて以下に説明する。ＣＰＵ１０７は（２４）式を初期
値とする（２３）式にしたがってＤＮ。、（Ｍ）とＤＭ
−２（Ｍ）とを算出する。

Ｄ　＋　（Ｊ）＝　Ｄ　＋　（ｊ−１）十Ｘ　＋　Ｄ　
＋−＋　（ｊ−１）　　　　・・・（２３）Ｄ　＋　（
０）＝　Ｓ　＋　　　　　　　　　　　　　　　　　　
　・・・（２４）さらに、求めたＤＭ４Ｉ（Ｍ）とＤＮ
。２（Ｍ）とを用いて（２５）式により新たな誤り位置
情報Ｘ９４．を算出する。

ＸＮ−１＝　　Ｄｎ、２（Ｍ）／Ｄｎ−＋（Ｍ）　　　
　　−（２５）ところで受信符号Ｗ１においてシンドロ
ームＳｉと誤り位置情報ＸＩと誤りパターンＹ１との関
係は、（１５）式に示す通りである。ここで、誤り位置
情報Ｘ、からＸＭまでのＭ個の変数は既知であり、誤り
位置情報Ｘ　ｒｌ＋　＋と誤りパターンＹ、からＹ　Ｍ
　４１までのＭ＋２個の変数が未知である。Ｓ、からＳ
ｒ１．２までのＭ＋２個の方程式からＹ、を１つずつ消
去する操作を（１５）式の左辺、つまりシンドロームＳ
１の処理として整理したものが（２３）式、　　（２４
）式であり、最後にＹ、、を消去してＸ　Ｎ　４１を求
める操作が（２５）式にあたる。すなわちＣＰＵ１０７
が（２５）式で算出するＸｆｉ４１は誤り位置検出部１
０２が検出に失敗した誤り位置情報であり、このＸＮ。

、と既知のＸ、からＸ６とを用いることより受信リード
ソロモン符号の正確な誤り訂正を実現することとなる。

以上のように本実施例では、誤り位ｌｔ検出部１０２が
受信リードソロモン符号の誤り位置検出を１つ失敗した
場合に於いても、ＣＰＵ１０７が（２３）式、　　（２
４）式、　　（２５）式に示す誤り位置情報算出処理に
よって正しい誤り位置情報を１つ算出するから、訂正不
能に陥らず受信リードソロモン符号を正しく訂正するこ
きができる。また、前記誤り位置情報算出処理はガロア
体上の線形演算であり、繰り返し回数の少ない新船式で
あるから僅かの簡単な演算で完了することができるもの
である。更に、誤り訂正処理は誤り訂正処理部３１０で
ハードウェア的に処理されるから極めて高速な誤り訂正
を実現することができるものである。

発明の効果 以上のように本発明のリードソロモン符号誤り訂正装置
は、誤り位置情報入力手段と、剰余算出手段またはシン
ドローム算出手段と、剰余またはシンドローム記憶メモ
リと、中間変数算出手段と、中間変数記憶手段と、誤り
位置算出手段とを設けることにより、誤り位置情報入力
部が入力した受信リードソロモン符号の誤り位置情報に
不足がある場合にも、訂正行列算出中に発生した前記中
間変数と、剰余算出手段またはシンドローム算出手段が
算出した受信リードソロモン符号の剰余またハシンドロ
ームとから、ＣＰＵが新たな正しい誤り位置情報を１つ
算出するものであるから、訂正不能に陥らず受信リード
ソロモン符号を正しく訂正することができ、極めて高い
受信データの信頼性を実現できるものである。しかもＣ
ＰＵの誤り位置情報算出はガロア体上の線形演算であり
、既に演算済みの中間変数を用いるかまたは簡単な新船
式で求められるから、極めて高速に演算することができ
る。

また、本発明のガロア体乗算装置は、桁上げフラグを含
めた整数加算機能を有するＣＰＵと、指数変換テーブル
と対数変換テーブルを記憶するメモリと、指数変換手段
と対数変換手段とを設けたことにより、被乗算数の指数
部加算を桁上げフラグを含めた整数加算で実行するから
逐次等価的に２５５を法とする加算を実現することとな
り、多大な処理時間を要するモジュロ演算を不要とする
とともに、指標処理を単純化し、ガロア体乗算処理を短
時間で実現ならしめるものである。

さらに、本発明のリードソロモン符号誤り訂正装置、ガ
ロア体乗算装置は共に汎用のＣＰＵに用いて適するもの
であるから、応用範囲が広く且つ開発効率が高く、産業
上その効果は大なるものである。

【図面の簡単な説明】

第１図は本発明の第１の実施例におけるリードソロモン
符号誤り訂正装置とガロア体乗算装置の構成を示すブロ
ック図、第２図は受信リードソロモン符号の構成を示す
構成図、第３図、第４図。 第５図は同実施例のガロア体乗算アルゴリズムのフロー
チャート、第６図は本発明の第２の実施例おけるリード
ソロモン符号誤り訂正装置の構成を示すブロック図、第
７図は本発明の第３の実施例おけるリードソロモン符号
誤り訂正装置の構成を示スフロック図、第８図は従来の
リードソロモン符号誤り訂正装置とガロア体乗算装置の
構成を示スフロック図、第９図は受信リードソロモン符
号の構成を示す構成図、第１０図、第１１図は同従来例
のガロア体乗算アルゴリズムのフローチャートである。 １０１・・・磁気テープ再生部、　　１０２・・・誤り
位置検出部、　　１０３・・・受信符号メモ１ハ１０４
・・・誤り位置情報入力部、　　１０５・・・剰余算出
部、　　１０６・・・剰余記憶メモ！Ｊ、　　１０７・
・・ＣＰＵ、　　　１０８・・・ＲＯＭ１　１０９・・
・ＲＡ　Ｍｌｌｌｏ・・・誤り訂正部、　　１１１・・
・誤訂正検出部、２０５・・・シンドローム算出部、　
　２０６・・・シンドローム記憶メモリ、　　３１０・
・・誤り訂正部。 代理人の氏名　弁理士　小鍜治　明　ほか２名昧 第３図 第４図 第９図 第１０　図 第１１図

Claims (9)

【特許請求の範囲】
1. （１）符号間距離Ｌ＋１の受信リードソロモン符号のＭ
   個のシンボルの誤り位置情報を入力する誤り位置情報入
   力手段と、 前記受信リードソロモン符号の生成多項式を法とする剰
   余を算出する剰余算出手段と、 前記剰余を記憶する剰余記憶メモリと、 前期Ｍ個の誤り位置情報のガロア体表現であるＸ＿１と
   、ガロア体の元αに対して ▲数式、化学式、表等があります▼ ただし、ｋ＝０、１、２、・・・、Ｌ−１ で定義する最大Ｌ個のガロア体上の元である中間変数Ａ
   （ｋ）を算出する中間変数算出手段と、前記中間変数Ａ
   （ｋ）を記憶する中間変数記憶手段と、 前記中間変数Ａ（ｋ）と、Ｌ個の前記剰余のガロア体表
   現であるＲ＿１に対して ▲数式、化学式、表等があります▼ ただし、Ｂ（ｊ）＝Ａ（Ｌ−ｊ）Ｒ＿Ｌ＿＋＿１＿−＿
   ｊで定義する第Ｍ＋１番目の誤り位置情報Ｘ＿Ｍ＿＋＿
   １を算出する誤り位置算出手段とを備えたリードソロモ
   ン符号誤り訂正装置。
2. （２）符号間距離Ｌ＋１の受信リードソロモン符号のＭ
   個のシンボルの誤り位置情報を入力する誤り位置情報入
   力手段と、 前記受信リードソロモン符号のＬ個のシンドロームであ
   るＳ＿１を算出するシンドローム算出手段と、前記シン
   ドロームを記憶するシンドローム記憶メモリと、 前記Ｍ個の誤り位置情報のガロア体表現であるＸ＿１と
   、ガロア体の元αに対して、 ▲数式、化学式、表等があります▼ ただし、ｋ＝１、２、・・・、Ｍ、 Ｃ（０）＝１ で定義する最大Ｍ＋１個のガロア体上の元である中間変
   数Ｃ（ｋ）を算出する中間変数算出手段と、前記中間変
   数Ｃ（ｋ）を記憶する中間変数記憶手段と、 前記中間変数Ｃ（ｋ）と、前記シンドロームＳ＿ｉに対
   して、 ▲数式、化学式、表等があります▼ で定義する第Ｍ＋１番目の誤り位置情報Ｘ＿Ｍ＿＋＿１
   を算出する誤り位置算出手段とを備えたリードソロモン
   符号誤り訂正装置。
3. （３）符号間距離Ｌ＋１の受信リードソロモン符号のＭ
   個のシンボルの誤り位置情報を入力する誤り位置情報入
   力手段と、 前記受信リードソロモン符号のＬ個のシンドロームであ
   るＳ＿ｉを算出するシンドローム算出手段と、前記シン
   ドロームを記憶するシンドローム記憶メモリと、 前記Ｍ個の誤り位置情報のガロア体表現であるＸ＿ｉと
   、前記Ｌ個のシンドロームＳ＿ｉに対して、Ｄ＿ｉ（０
   ）＝Ｓ＿ｉ Ｄ＿ｉ（ｊ）＝Ｄ＿ｉ（ｊ−１）＋Ｘ＿ｉＤ＿ｉ＿−＿
   １（ｊ−１）で定義する漸加式を演算し、 Ｘ＿Ｍ＿＋＿１＝Ｄ＿Ｍ＿＋＿２（Ｍ）／Ｄ＿Ｍ＿＋＿
   １（Ｍ）で定義する第Ｍ＋１番目の誤り位置情報Ｘ＿Ｍ
   ＿＋＿１を算出する誤り位置算出手段とを備えたリード
   ソロモン符号誤り訂正装置。
4. （４）被加算整数と加算整数と桁上げフラグとの加算結
   果と、前記加算結果に応じた桁上げフラグを出力する整
   数加算機能を有するＣＰＵと、ガロア体の元αのｎ乗の
   値の一覧表であり、αの２５５乗に対応する値を１とす
   る指数変換テーブルを記憶するメモリと、 前記ｎの値から対応するαのｎ乗の値を前記指数変換テ
   ーブルから読み出す指数変換手段とを備えたガロア体乗
   算装置。
5. （５）指数変換テーブルはリードオンリメモリに記憶さ
   れている請求項４記載のガロア体乗算装置。
6. （６）ＣＰＵに指数変換テーブルを演算させ、ランダム
   アクセスメモリに記憶させる指数変換テーブル生成プロ
   グラムを備えた請求項４記載のガロア体乗算装置。
7. （７）ガロア体の元の対数に対応する値の一覧表であり
   、ガロア体の元ゼロの対数に対応する値をゼロとする対
   数変換テーブルを記憶するメモリとガロア体の元の値か
   ら対応する対数の値を前記対数変換テーブルから読み出
   す対数変換手段とを具備するガロア体乗算装置。
8. （８）対数変換テーブルはリードオンリメモリに記憶さ
   れている請求項７記載のガロア体乗算装置。
9. （９）ＣＰＵに対数変換テーブルを演算させ、ランダム
   アクセスメモリに記憶させる対数変換テーブル生成プロ
   グラムを備えた請求項７記載のガロア体乗算装置。