JPH01158828A - 誤り検出・訂正装置 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 産業上の利用分野 本発明は誤り検出・訂正装置に係り、ＰＣＭ録音再生機
、ディジタル・オーディオ・テープレコーダ（ＤＡＴ）
、ディジタル・オーディオ・ディスフ等において、信頼
性確保のために所定の方法で生成されたパリティ（検査
符号）を付加され、符号化されたブロックとして記録さ
れたディジタル信号を再生する場合に、符号誤りを検出
し、元の正しい信号に訂正する誤り検出・訂正装置に関
する。

従来の技術 従来より、記録されたディジタルデータを再生する場合
、或いは何らかの方法により伝送されてきたディジタル
データを受信する場合に行なわれるデータの誤り検出・
訂正の方式としては数種類のものが知られ、実際の装置
においても実用化されている。その中でもリード・ソロ
モン符号による誤り検出・訂正方式は、符号の冗長度（
符号語における検査ワードとデータとの割合）、誤り訂
正能力の点で優れており、ディジタル・オーディオ・デ
ィスク等に於いて用いられている。

８ビツトからなる信号を１シンボルとするディジタルデ
ータをＤｆｌ（ｅ＝０．１．・・・５８）とし、５９シ
ンボルよりなるデータを考える。但し、この中には５シ
ンボルからなる検査ワード（以下単にパリティという）
を有し、これを含めてデータＤ２とする。この５９シン
ボルのデータ中に含まれる５シンボルのパリティは真の
ディジタルデータと共に次式を満たすよう定められてい
る。

但し、ここでの総和記号Σは排他的論理和を示し、これ
は夫々のデータの対応するビット同志について行なわれ
る（以下同様）。（１）式において、Ｄ２（乏＝０．１
．２．・・・、５８）の係数α−２ｆ１等は２５６個の
元よりなる周知のガロア体ＧＦ（２８）に属する８ビツ
トの元であり、これらの元は原始元αを用いて、０．１
（−α°）、α１．α２゜・・・、α　　と表わぜる。

又ガロア体ＧＦ　（２８）の中のある元の逆数も必ずガ
ロア体ＧＦ　（２８）の元となるよう定義することが可
能である。

記録されたディジタルデータＤ、が再生されたときのデ
ータ（或いは何らかの方法により伝送され、受信された
データでもよい）がそのシンボル中のどこかに誤った符
号を含み、Ｄ之′に変化したとして、以下の量ｓ−２，
ｓ、、ｓｏ、ｓ１゜Ｓ２が定義できる。

ここでＳ　　・・・、Ｓ２はシンドロームと呼ばれ、リ
ード・ソロモン符号によるディジタルデータの誤り検出
・訂正を行なう際に中心的な役割を果す。

再生データＤ　　’　　（Ｉｌ＝０．１．２．・・・、
５８）之 に全く誤りがないとすれば（１）式よりＳ−２，・・・
。

Ｓ２はすべてゼロとなる。

ここでＤｆｌ（之−０，１，２，・・・、５８）中１つ
のシンボル（Ｄ・とづる）だけが、再生される際に誤り
を含み、真のデータＤ・からＤｉ′へ変化したとすると
、 Ｄ、’　−Ｄ・＋ｅ−■ ｌ　　　　　　　　　１１ と現わせる。但し、ここで記号子は排他的論理和演算を
示しく以下同様）、ｅｉは誤差を示す。この時０式は となり、更に（４）式より次の関係を満たす。

したがって６）式を満足することがわかれば、Ｄ’（之
−０，１，２・・・５８）は、その中のただ１シンボル
のみに誤りを含んでいることがわかる。また（４）式よ
りＳ／Ｓｏ＝α　であることから ｉ　＝　ｌｏｇ　　　ＳＬ−（６） α　ＳＯ によって、誤りを含んだシンボルを特定することができ
、（４）第３式Ｓ。−ｅｉ　と０式からＤ・−Ｄ・′十
Ｓ。　　　　　　　　（７）となる。このＤ・を再生さ
れたデータ中のＤｉ′■ と入れ替えることにより誤りを含んだシンボルを訂正す
ることができる。

６）式が満足されない場合には、再生されたデータＤｆ
ｌ′は２つ以上のシンボルに誤りを含むこととなる。こ
の場合にｏ、（ｅ−０，１，・・・。

５８）中２つのシンボル（Ｄ・、Ｄｊとする）が■ 再生される際に誤りを含み真のディジタルデータＤ・、
Ｄ・から夫々Ｄ・１．Ｄ、ｌへ変化したとＩＪ　　　　
　　　　　　　Ｉ　　　　　　　Ｊすると、 Ｄ・’　−Ｄ・＋ｅｉ　　　　　　　　　■Ｄ、’＝Ｄ
・十〇・　　　　　　　　Ｇ）Ｊ　　　　ＪＪ と表わせる。ここでｅ・、ｅ・は夫々Ｄ・、ＤｊＩＪ　
　　　　　　　　ｌ についての誤差を示す。この時２式は となり、 と置くことにより、（１０）式は次の関係を満たす。

（１２）、　（１３）式より となり（１５）、　（１６）式を（１４）式に代入して
成立するとすれば、Ｄｊ２．（之−０，１，２，・・・
、５８）中２つのシンボルに誤差を含むこととなり、成
立しなければ３つ以上のシンボルに誤と差を含むことと
なる。ここで（１５）、　（１６）式の代入によって（
１４）式が成立した（２シンボルだけに誤差を含む）と
仮定すると、（１１）式より ＜ａ　　＞　　十Ｘ１ａ　　＋Ｘ２＝０　　　　　（１
７）となり、 ｙ−α’　　　　　　　　　　（１８）とおくことによ
り、 Ｖ　　十ＸＩ　Ｖ＋Ｘ２　＝Ｏ（１９）又、　Ｚ　＝　
ｙ／Ｘ　１（２０） とおくことにより、 となる。ここでＸ２　／Ｘ１　をパラメータとするＲＯ
Ｍテーブル等を用意すればＺを求めることが可能となる
。従って（１８）、　（２０）式よりαｉが次のように
求まり、 ｙ−Ｘｌ・Ｚ−α’　　　　　　（２２）（１１）式よ
りαｊが次のようになる。

α　−Ｘ１＋Ｘ１Ｚ　　　　　　　　（２３）これより
ｉ、ｊは となり、誤りを含む２つのシンボルが特定される。

更に（１０）式より であるから、（２６）、　（２７）式よりｅ・、ｅｊが
のように求まる。この（２８）、　（２９）式を（８）
、（９）式と比較すれば、真のディジタルデータＤ・、
Ｄ・をＪ 求めることができ、２つのシンボルＤ、ｌ　。

Ｄ・′をり、、Ｄｊに入れ替えることによって誤りを訂
正することが可能となる。

上記（６）、　（２４）、　（２５）、　（２８）、　
（２９）の各式の左辺は、いずれも最終的にシンドロー
ムＳ２．Ｓｌ。

Ｓｏ、Ｓ−１，Ｓ−２によって表わされることとなり、
このシンドロームのガロア休ＧＦ　（２”　）上での演
算を行なうことによって、求めることができる。

なお（１２）、　（１３）、　（１４）式が成り立たな
い場合には３シンボル以上に誤りを含むこととなるが、
５シンボルのパリティを有するデータでは、誤りを検出
し、かつ訂正できるのは２シンボルまでであり、３シン
ボル以上の誤りがある場合は検出のみができるというの
が周知の事実である。

第４図はこれまで述べてき１ｃようなシンドロームの算
出及び誤り検出・訂正を行うための従来装置の主要部の
一例のブロック図を示す。同図において１はシンドロー
ム生成部であり、メモリ（図示せず）に−旦記憶された
再生ディジタル信号がら０式に示すシンドロームＳ−２
，・・・Ｓ２を生成する。シンドローム生成部１で生成
されたシンドロームはデータバスを介してレジスタ部２
ａ及び２ｂへ供給され、−時的に記憶される。次にレジ
スタ部２ａ及び２ｂのうちから必要に応じてシンドロー
ムが呼び出され、乗算部３以降での操作が行なわれる。

例えば（５）第１式の計算を行う場合にレジスタ２ａ、
２ｂから共にＳ−４が読み出され、対数変換部（対数Ｒ
ＯＭ）３ａ、３ｄへ夫々供給される。

この対数ＲＯＭ３ａ、３ｄはリード・オンリ・メモリ（
ＲＯＭ）により構成され、その内部に、入内部へ供給さ
れた数値の原始元αを底とする対数を出力するような対
数テーブルが記憶されている（以下単に対数といった場
合にはαを底とするものとする。）。したがって、対数
ＲＯＭ３ａ。

３ｄの出力は共にＳ−１の対数に当たるものであり、こ
れらは算術演算部（ＡＬ　Ｕ　）　３　ｂに供給される
。

このＡＬＵ３ｂでＳ−１の対数同志が加算（通常の加算
）され、次の指数変換器（指数ＲＯＭ）３ｃに供給され
る。指数ＲＯＭ３ｃは対数ＲＯＭ３ａ。

３ｄと同様にＲＯＭにより描成されるが、対数ＲＯＭ３
ａ、３ｄとは逆に入力された数値を上記αのベキ乗に変
換する。したがって指数ＲＯＭ３Ｃは、対数ＲＯＭ３ａ
、３ｄに供給される２つの値の積を出力する。指数ＲＯ
Ｍ３Ｃの出力は加算部４へ供給され加算回路４ａを介し
てレジスタ４ｂに一時的に蓄えられる。

その後、レジスタ２ａからはＳ−２が読み出され、対数
ＲＯＭ３ａによって対数に変換されたあと、ＡＬＵ３ｂ
に供給される。同時にＳ。がレジスタ２ｂより読み出さ
れ、対数ＲＯＭ３ｄにより対数に変換されＡＬＵ３ｂに
供給され、Ｓ−２の対数との加算が行なわれる。この結
果は指数ＲＯＭ３ｃにおいてαのベキ乗に変換され、Ｓ
−２と８３の乗算結果が出力される。

この指数ＲＯＭ３Ｃの出力は加算回路４ａにおいてレジ
スタ４ｂに記憶されている内容（Ｓ、、、１　）との排
他的論理和演算が行なわれ、その結果が新しいデータと
してレジスタ４ｂに蓄えられる。

以下同様に（５）第２式、第３式が順次計算され、６）
式が成り立つこととなれば、再生されたディジタルデー
タの１シンボルのみに誤りがあると判断され、そのシン
ボルを特定するために（６）式の計算を行なう。この計
算は、レジスタ部２ａ、２ｂより夫々Ｓ１．Ｓ（、が読
み出され乗算部３へ供給されるが、対数ＲＯＭ３ｄでは
Ｓ。を対数に変換すると同時にその符号を反転する操作
を行なわゼることかでき、乗算部の出力としてＳ１／Ｓ
ｏを取り出すことができる。この結果をレジスタ部１６
ａ。

１６ｂを介して再び乗算部３へ供給し、その前段部にお
いて対数計算を行い、誤りを含んだシンボルが特定され
る。誤り訂正の操作（（７）式の計算）はこれに引き続
いて行なわれる。又６）式が成り立たないとすれば、誤
りは２シンボル以上に及ぶものと判断され（１１）式以
降の計算が行なわれる。

このような誤り検出・訂正の計算も上記乗算部３と加算
部４に於て行なわれ、ここでの計算の速度が誤り検出・
訂正機能に大きく影響する。

第５図は従来装置の第２例の主要部の一例のブロック図
を示す。同図において、シンドローム生成部１は第４図
の従来装置と同じものであり、対数ＲＯＭ１０ａ、１０
ｂ、指数ＲＯＭ１４．１５、ＡＬＵｌｌ、加算回路１６
も夫々第４図の対応するものと同等のものである。

第５図の装置では、まずシンドローム生成部１で生成さ
れたシンドロームはレジスタ部９ａ。

９ｂへ供給され、−時的に記憶される。ここで例えば６
）第１式の４算をする場合には以下の手順で行なわれる
。まずレジスタ部９ａからＳ−１が読み出され、対数Ｒ
ＯＭ１０ａにおいて対数に変換ざれ、ＡＩＵｌｌへ供給
される。同時にレジスタ部９ｂからＳ−１が読み出され
、対数ＲＯＭ１０ｂにおいて対数に変換され、ＡＬＵｌ
ｌへ供給されると、２つのＳ−１の対数はこのＡＬ−Ｕ
ｌｌで加算され、Ｓ−１の対数となる、１この結果は、
レジスタ部１２へ一時的に記憶される。

次にレジスタ部９ａからＳ−２が読み出され、対数ＲＯ
Ｍ１０ａにおいて対数に変換され、ＡＬＵｌｌへ供給さ
れる。これと同時にレジスタ部９ｂからＳｏが読み出さ
れ、対数ＲＯＭ１０ｂにおいて対数に変換され、ＡＬＵ
ｌｌへ供給される。

ＡＬＵｌｌではＳ−２の対数とＳ。の対数とが加算され
、Ｓ−２・Ｓｏの対数とされる。この結果はレジスタ部
１３に一時的に記憶される。この時点でレジスタ部１２
に記憶された内容（Ｓｏ　の対数）は指数ＲＯＭ１４に
供給され、原始元αのベキ乗に変換され、同時にレジス
タ部１３に記憶された内容（Ｓ−２・Ｓｏの対数）は指
数ＲＯＭ１５に供給され、αのベキ乗に変換される。こ
の指数ＲＯＭ１４及び１５の出力は、加算回路１６にお
いて加算（排他的論理和）され、６）第１式の別箇が実
行されたことになる。

以上の結果第４図と第５図の従来装置を比較すると、第
４図の装置では、６）第１式の計算を例にとれば、まず
Ｓ−１がレジスタ部２ａ、２ｂから読み出され、対数Ｒ
ＯＭ３ａ、対数ＲＯＭ３ｄ、Ａ１、　Ｕ　３　ｂ、指数
ＲＯＭ３ｃ、加算回路４ａを経てＳ−１という値にもど
され、レジスタ４ｂに到ってから初めてＳ−２，Ｓｏの
読み出しが開始され、Ｓ−２・Ｓｏの計算が行なわれる
。そしてＳ−１・ＳｏとＳ−１の朗弛的論理和演算が終
了した時点で６）第２式の第１項の演算が開始される。

これに対し、第５図の装置ではレジスタ部１２、レジス
タ部１３に夫々Ｓ　　の対数、＄−２・Ｓ。

の対数が一時的に蓄えられ、そのあとで夫々の対数が指
数ＲＯＭ１４、指数ＲＯＭ１５に同時に供給され、それ
らの出力が加算回路１６において加算（排他的論理和演
算）される。しかも、この排他的論理和演算が実行され
るのと併行して、６）第２式の第１項の乗算を開始する
ことが可能となる。

従って、第５図の装置では第４図の装置に比べて多数の
演算を繰り返し行う場合に高速に処理することが可能と
なる。

発明が解決しようとする問題点 上述したように第４図の従来装置では、乗算部３に与え
られたデータが、乗算部３．加算部４を経て夫々の演算
が完了した時点で、始めて次のデータを乗算部３に供給
することができることとなり、乗算部３において乗算が
行なわれている間の加算部４或いは加算が行なわれてい
る間の乗算部３は、いずれも演算が行なわれていない状
態にあり、誤り検出・訂正という膨大なデータの処理が
必要で、かつ短時間で行なわな【プればならない装置に
おいて、この演算部の空き時間は非常に不利なものとな
っていた。又第４図の装置で演算速度を向上させようと
すると、回路を構成する各素子に高速なものを使用しな
【プればならず、このことはコスト面での負担となると
共に高集積化という面においても障害となっていた。

又第５図の従来装置では第４図の場合とは異な＝　　１
９　− リ、レジスタ部１２．レジスタ部１３に共にデータが蓄
えられ、対数ＲＯＭ１４．対数ＲＯＭ１５及び加算回路
１６での演算が行なわれている際には、対数ＲＯＭ１０
ａ、１０ｂ、ＡＬＵｌ　１においては既に次の演算が開
始されており、第４図の従来装置に比べて、演算が常に
行なわれているという点では時間的不利益は改善される
。しかしながら第５図の装置は第４図の装置に比べて、
回路構成が複雑であり、使用する素子の数も多くなって
いる。従って各素子間のデータの流れを制御するコント
ロール手段も勢い複雑なものとならざるを得ず、演算回
路、コントロール回路を構成する素子数の増加によって
回路規模が人ぎくなるという問題点があった。

本発明は上記の点に鑑みて創作されたものであり、演算
を高速に行なうことができ、かつ回路構成が複雑になら
ず、データを］ントロールする回路も小規模に抑えるこ
とが可能な誤り検出・訂正装置を提供することを目的と
する。

問題点を解決するための手段 本発明では演算部を、所定の性質を有するガロア体の原
始元を底とする対数を求めるための対数変換部と、 対数変換部の２つの出力データ同志を加算するための算
術演算部と、 算術演算部の出力を一時的に記憶するための第１のレジ
スタと、 該第１のレジスタの出力データを指数として、該ガロア
体の原始元のベキ乗を求めるための指数変換部と、 排他的論理和演算を行う加算回路及び加算回路の演算結
果のデータを一時的に記憶する第２のレジスタを有し、
加算回路において指数変換部の出力データと第２のレジ
スタに記憶されたデータとの排他的論理和演算を行い、
その結果を新たに第２のレジスタに一時的に記憶する加
算部とによって構成し、 対数変換部から第１のレジスタまでの第１の演算処理と
第１のレジスタから第２のレジスタまでの第２の演算処
理とを同時に実行可能とする。

作用 シンドローム生成部において生成された２つのシンドロ
ームは、対数変換部においてガロア体の原始元を底とす
る対数に変換され、算術演算部において上記２つのシン
ドロームの対数は互いに加算され、第１のレジスタに−
ｍ的に記憶される。

第１のレジスタに記憶されたデータは、指数変換部にお
いて第１のレジスタに記憶されたデータを指数とする原
始元のベキ乗に変換され、対数変換部に供給された２つ
のシンドロームの積となって加算部に供給される。

加算部では、加算回路において第２のレジスタに記憶さ
れたデータと前記指数変換部の出力データとの排他的論
理和演算を行い、その結果のデータは新たに第２のレジ
スタヘー時的に記憶される。

この排他的論理和演算及び第２のレジスタへの記憶操作
と併行して、前記対数変換部、算術演算部では上記２つ
のシンドロームとは別のく同じ値である場合も含む）新
たなシンドロームに対する演算が行なわれ、その結果の
データが第１のレジスタに一時的に記憶される。

実施例 第１図は本発明になる誤り検出・訂正装置の一実施例の
回路図を示す。まず同図の回路の主要部について簡単に
説明する１゜ メモリ３０はディジタル・オーディオ・ディスク（ＤＡ
Ｄ＞等より再生された１フイ一ルド分のディジタル音声
信号（リード・ソ［１モン符号）を記憶するためのメモ
リであり、そのメモリマツプの具体的な説明は後述する
。

シンドローム生成部３４は２式のシンドロームＳ−２，
・・・、Ｓ２を生成するための回路であり、具体的な演
算の実行については後述する。

乗算部４５はガロア体ＧＦ　（２８）に属する２つの値
の乗算を行うための回路であり、更に、この回路は対数
変換部（対数ＲＯＭ）４６．４７、算術演算部（ＡＬＵ
）４Ｂ、対数Ｕ０検出回路４９、Ａ　ｉ　Ｕレジスタ５
０、及び指数変換部（指数ＲＯＭ）５１とより構成され
る。

対数ＲＯＭ４６．４７は共に第４図、第５図の従来装置
に用いられていた対数変換器と同様にＲＯＭによって構
成され、その内部にはガロア体上の原始元αを底とする
対数テーブルが記憶されている。したがっである値α　
、α　が夫々対数ＲＯＭ４６．４７に供給されると、そ
のαを底とする対数ｍ、ｎが出力されることとなる。Ａ
ＬＵ４８では対数ＲＯＭ４６と４７によって対数に変換
された夫々の値ｍとｎの加算を行う。ここでの加算は本
明細書の他の部分において排他的論理和演算を一括して
加算と称しているのとは異なり、通常の加算が行なわれ
る。

Ａ　Ｌ　Ｕ　＜８において行なわれた演算は第１のレジ
スタであるＡＬＵレジスタ５０に一時的に蓄えられる。

このＡＬＵレジスタ５０をこの位置に設けたことにより
、後述するように乗算と加算とをパイプライン方式で実
行することが可能となる。

ＡＬＵレジスタ５０の出力データｍ＋ｎは指数ＲＯＭ５
１においてα　　に変換される。１この指数ＲＯＭは対
数ＲＯＭ４６．４７などと同様にＲＯＭによって構成さ
れ、その内部には入力された値ｍ＋ｎを指数として、α
　　に変換する指数テーブルが記憶されている。又対数
り０検出回路４９は、対数ＲＯＭ４６．４７にゼ［１が
入力された場合にデータセレクタ５２がＵ口を出力する
よう構成した回路である。

以上の説明より明らかなように、乗算部４５全体として
考えると、入力された２つの値（α　。

α　）の積（αＩｌｌ＋ｎ　）を出力することとなる。

加算部５３は加算回路５３ａと第２のレジスタであるＡ
レジスタ５３ｂとより構成され、データセレクタ５２よ
り供給される値とＡレジスタ５３ｂに記憶された値を加
算回路５３ａにおいて加算（排他的論理和、以下同様）
し、その値を新たにＡレジスタ５３ｂに記憶するという
操作を行う。

本出願人は特願昭６１−６８５１３号（名称「ディジタ
ル信号の伝送方式」）において、１ノイ一ルド分のディ
ジタル音声信号に対して簡単なインターリーブをかけて
も、高い誤り検出能力。

誤り訂正能力を有するディジタル信舅の伝送方式を提案
した。メモリ３０内にはこの方式によって伝送された（
記録媒体より再生されたものも含む）ディジタル音声信
号が記憶される。第２図はメモリ３０の記憶内容の要部
のメモリマツプを示し、又第３図は第２図のメモリンツ
ブの記憶領域を示す。メモリ３０は、第２図に示すよう
に５９行×６１列−３５９９シンボル（１シンボルは８
ビツト）分の記憶容量を有する。以下第２図のメモリマ
ツプについて簡単に説明する。

第２図において、ＬＵ、Ｌ之は左ヂャンネル音声信号を
パルス符号変調（ＰＣＭ）して得られた左チヤンネルＰ
ＣＭ音声データの上位８ビツト及び下位８ビツトを夫々
示し、同様にＲＵ、Ｒｆｌは右チヤンネルＰＣＭ音声デ
ータの上位８ビツト及び下位８ビツトを夫々示す。また
、Ｄは未定義のデータを示す。更に、Ｌ、Ｒの前の数値
は再生されるべき順番を示しており、またＩＤは音声情
報やプリエンファシスその他に関する識別信号（ＩＤ信
号）を示す。これらのＰＣＭ音声データ、識別信号の一
部は横方向の１〜５６シンボル、及び縦方向の６〜５８
シンボルの範囲内の第３図に２０で示すデータ領域に配
置される。

縦方向の５９番目のシンボルにおいて、横方向の１〜２
９番目のシンボルの第３図に示す領域には第２図に示す
如くすべて“′０″が記憶され、これはパリティＣ１，
０２の生成のためには使用するが、記録されないデータ
である。また、第３図に２４８，２４ｂで示す縦方向の
５９番目のシンボルの領域において、横方向の３０〜６
１番目の削３２シンボルの領域には識別信号（ＩＤ信号
）が配され、５７〜６１番目のシンボルの領域１９ｂに
はＩＤ信号のパリティ（第２図ではこれもＩＤと記す）
が配置される。すなわち、２４ａ、２４ｂはＩＤ信号領
域を示す。

パリティは有限体（ガ［１ア休）ＧＦ（２８）上で定義
したリード・ソロモン符号におけるパリティで、１符号
語の語調が６１シンボルで、そのうちデータが５６シン
ボル、パリティが５シンボルである（６１．５６）リー
ド・ソロモン符号によるＣ１パリティ（第１のパリティ
）は第２図ではＰで示され、第３図のＣ１パリティ領域
２１に記憶される。またデータが５４シンボル、パリテ
ィが５シンボルである（５９．５４＞リード・ソロモン
符号によるＣ２パリティ（第２のパリティ）は第２図で
はＱで示され、第３図のＣ２パリティ領域２２に記憶さ
れる。

第３図のパリティ領域２３には、Ｃ２パリティ領域２２
（又はＣ１パリティ領域２１〉のパリティを生成要素と
する（６１．５６）リード・ソロモン符号（又は（５９
，５４）リード・ソロモン符号）によるＣＩ（又はＣ２
）パリティが記憶されるがこのパリティはＣ１パリティ
でもＣ２パリティでも同一の値となり、第２図にはＰＱ
で示しである。このように、パリティはＣ１と０２によ
る二重符号化（積符号化）されている。

このように、上記のメモリマツプには、横方向の１〜５
６シンボルのデータ（Ｃ２パリティ含む）と横方向の５
７〜６１シンボルの０１パリテイとからなる（６１．５
６）リード・ソロモン符号（第１のディジタル信号）と
縦方向の６〜５９シ＝　　２８　− ンボルのデータ（Ｃ１パリティ含む）と縦方向の１〜５
シンボルの０２パリテイとからなる（５９゜５４）リー
ド・ソロモン符号（第２のディジタル信号）とが記憶さ
れる、１ 次に本発明の一実施例である第１図の回路の動作につい
て詳しく説明する。

ここではメモリ３０に記憶された第３図のメモリマツプ
上のある列（１・−６１まである列の中のどれか１つの
列）に沿ったＣ２方向のデータの誤り検出・訂正を行う
場合を考え、このＣ２方向に沿ったデータをＶ　′、・
・・、■５８′　とする。

まず０式に対応して、シンドロームＳ、、Ｓ、。

Ｓｏ、Ｓｌ、Ｓ２を求めるための操作を行う。シンドロ
ームの生成は、メモリ３０に記憶されたデータが読み出
され、データバスを通過して、バッファ３１．データセ
レクタ３２．メモリリードレジスタ（ＭＲレジスタ）３
３を介してシンドローム生成部３４に供給され、このシ
ンドローム生成部３４において、上記シンドロームＳ−
２，・・・。

Ｓ２が生成される。

ここでは−例として、シンドロームＳ１を求める操作に
ついて説明する。まず０８−２レジスタ３５ａ、Ｃ８−
ルジスタ３６ａ、−、Ｃ８２レジスタ３９ａがすべてク
リアされ、φ（８ヒツトすべてがゼロの状態を総称して
φとする）の状態となる。

■　Ｖ５８′がメモリ３０から読み出され、上述の経路
を経て加算回路３８ｃに入力される。一方ＣＳルジスタ
３８ａの内容φと、α　の値が記憶されたデータ発生器
３８ｂの出力との乗算が行なわれ、この結果も同時に加
算回路３８Ｃに供給される。加算回路３８ｃでは２つの
入ツノの排他的論理和演算が行なわれ（３５Ｃ〜３９ｃ
も同様である）、その結果を新しくＣＳルジスタ３８ａ
にセラ１−する。この一連の操作を式で表せば次のよう
になる。

φ×α　＋Ｖ′−■５８′工今Ｃ８１ ■　ＣＳルジスタ３８ａの内容（Ｖ５８′）とＣ１との
＠算が行なわれ、その結果が加算回路３８ｃに供給され
る。加算回路３８Ｇでは、これとメモリ３０から読み出
されたＶ５７′　との加算（排他的論理和演算、以下同
様）が行なわれ、その結果はＣＳルジスタ３８ａに新し
くセットされる。

■　ＣＳルジスタ３８ａの内容（α　・Ｖ５８’　＋Ｖ
５７’　）とＣ１との乗算が行われ、その結果が加算回
路３８ｃに供給される。加算回路３８ｃでは、これとメ
モリ３０から読み出されたＶ　′との加締が行われ、そ
の結果はＣＳルジスタ３８ａに新しくセットされる。

（Ｃ１・Ｖ５ｇ’　＋Ｖ５７’　）　Ｘα１＋Ｖ５６′
”（Ｘ　　・Ｖ５ｇ’　＠αＶ５７’　＋Ｖ５６’−＝
＝＝＞Ｃ８１以下同様の操作が繰り返され、最後にメモ
リ３０よりＶＯ２が読み出され上記の演算が行なわれる
と、最終的には次の値がＣＳルジスタ３８ａにセットさ
れる。

α・ｖ１′　」−α　・ＶＯ２ 但し、ここでＣ０−１（第１ピッ１−のみが１で他はす
べてゼロ）である。この式は０第４式に対応し、シンド
ロームＳ１となる。

イ也のシンドロームＳ−２，Ｓ−１，Ｓｏ、Ｓ２も同様
に、シンドローム生成部３４の夫々に対応する演算回路
において、メモリ３０から読み出されるデータＶ　′・
・・、■５８′より生成され、夫々Ｃ８−２レジスタ３
５ａ等にセットされる。

Ｃ８−２レジスタ３５　ａ　、　−、ＣＳ　２レジスタ
３９ａにセットされたシンドロームＳ−２，・・・。

Ｓ２はデータセレクタ４０．データセレクタ３２を介し
てシンドロームレジスタ（Ｓ−２レジスタ）４１ａ、・
・・、シンドロームレジスタ（Ｓ２レジスタ）４１ｅへ
夫々転送され、セットされる。ここでＳ　レジスタ４１
ａ、・・・、Ｓ２レジスタ４１ｅにセットされたシンド
ロームは、ゼロ検出器４２に供給される。シンドローム
Ｓ−２，・・・、Ｓ２の値が全てゼロであり、ゼロ検出
器４２がこれを検出すると、Ｖ　′、・・・、Ｖ５ｇ’
　には誤りが無いと判断され、次の列の一連のデータに
ついてのシンドローム生成演算に移行する。

ゼロ検出器４２においてＳ　　・・・、Ｓ２の中に−２
・ ゼロでないものがあることが検出されると、Ｖ　′、・
・・、■５８′のシンボルの中に誤りを含むものがある
と判断され、そのシンボルを特定し、正しいデータに訂
正するための演算を行う。この演算の内容自体は「従来
の技術、１の項で述べたちのと全く同一であり、第１図
の本発明の回路は後述するように、この演算を効率よく
、しかも高速に実行することを可能とする。以下この演
算の手続きについて説明する。

以下の（１）乃至（３０）は夫々第１図の回路の制御を
行なうコントロール部（図示せず）によって指令される
１インストラクシヨンステツプに対応する。

（１）誤りを含むシンボルの数によって、所定の値を出
力するフラッグ部４３をクリアする。

（２）Ａレジスタ５３ｂをクリアするど共に、６）第１
式の左辺に対応する値を求めるための計算をするために
、データセレクタ４７１及び４７はＳ−ルジスタ４．１
ｂよりＳ−１を読み出して乗算部４５に供給する。ここ
ではまずＳ−１を夫々対数ＲＯＭ４６及び４７において
対数に変換し、ＡＬＬＩ４８においてそれらを互いに加
算（通常の加算）した結果をＡ　１．、　Ｕレジスタ５
０にセットする。

ＩＱ（］　　Ｓ　　＋　　１ｏｐ（ｘＳ−Ｉ　　　ＡＬ
Ｕレジスタα　−１ ■　ＡＬＵレジスタ５０にセットされた内容を指数ＲＯ
Ｍ５１によってＳ−１の２乗に変換し、加算回路５３ａ
においてＡレジスタ５３ｂにセットされた内容（φ）と
の加算（排他的論理和）を実行し、その結果を新たにＡ
レジスタ５３ｂにセットする。

これと同時に乗算部４５では、Ｓ−２レジスタ４１ａ、
Ｓｏレジスタ４１　ｃより夫々読み出されたＳ−２，Ｓ
Ｏの乗算操作の萌段階（ＡＬＵ４８で両者の対数の加算
が行なわれるまでの段階）での結果をＡ　ｌ−ｕレジス
タ５０ヘセットする。

ｌ　ＯＱ　ａ　Ｓ　−２＋　　Ｉ　ＯＱ　ａ　Ｓ　（）
　　　Ａ　Ｌ　ＬＪレジスタ（４）ＡＬＵレジスタ５０
に記憶された内容を指数ＲＯＭ５１を通過させ、αのベ
キ乗に変換し、加算回路５３ａにおいて、この指数ＲＯ
Ｍ５１の出力とＡレジスタ５３ｂに記憶された内容と−
３５＝ を加算すると共に、この結果を新たにＡレジスタ５３ｂ
にセットする。

（５）　　Ａレジスタ５３ｂの内容をそのままＢレジス
タ５４に転送する。

Ｓ−１＋Ｓ−１・Ｓｏ　　Ｂレジスタ （６）　　フラッグ部４３の第１のフラッグに、Ｓ−１
＋Ｓ−１・Ｓｏの値がゼロであるか、ゼロ以外の値であ
るかによって所定の値をセットする。

ω〜（１１）上記■〜（６）と同様の過程を経て、６）
第２式の左辺に対応する値を求める演算を行い、その結
果をＣレジスタ５５へ転送し、フラッグ部４３の第２の
フラッグに所定の値をセットする。

（１２）〜（１６）上記の・〜（６）及びの・〜（１１
）と同様の過程を経て、（５）第３式の左辺に対応する
値を求める演算を行い、その結果をＤレジスタ５６へ転
送し、フラッグ部４３の第３のフラッグに所定の値をセ
ットする。

（１７）　　フラッグ部４３において、第１乃至第３の
フラッグの値が全てゼロであればｖｏ’、・・・。

■５８′のうちただ１つのシンボルのみが誤りを含むと
判定され、そうではない場合には２以上のシンボルにお
いて誤りを含むと判定される。

この結果はレジスタ４３よりコントロール部へ送られる
。

以下１シンボルにのみ誤りがある（すなわち６）式が成
立つ）と判定されたと仮定して、その誤りを含むシンボ
ルを特定するための演算を行う。

（１８）フラッグ部４３をクリアする。

（１９）　　Ａレジスタ５３ｂをクリアし、（６）式に
対応する演算を行うために８ルジスタ４１ｄ。

Ｓｏレジスタ４１Ｇより夫々読み出されたデータＳ　を
データセレクタ４４を介して、又Ｓ０をデータセレクタ
５７を介して夫々対数ＲＯＭ４６、対数ＲＯＭ　４７　
ニ供給ｔル。対数ＲＯＭ４７では、その出力の符号を反
転し、それらをＡ１．Ｕ４８において加算した結果をＡ
　Ｉ−Ｕレジスタ５０にセットする。

１０ｇ５　−　１ｏ（ｌ　　Ｓ　　　　ＡＬＵレジスタ
α　１　　　α　０ （２０）　　Ａ　Ｌ　Ｕレジスタ５０に記憶された（１
９）の内容を指数ＲＯＭ５１を介してαのベキ乗（Ｓ１
／Ｓｏとなる）に変換し、これとＡレジスタ５３ｂに記
憶されたφとを加算回路５３ａにおいて加算し、この結
果を新たにＡレジスタ５３ｂにセットする。

Ｓ　／Ｓｏ＋φ＝＝Ｓ１／Ｓｏ　　Ａレジスタ（２１）
　　Ａレジスタ５３ｂの内容をそのままＣレジスタ５５
へ転送する。

（２２）　　Ｃレジスタ５５の内容をデータセレクタ５
９、データセレクタ４４を介して対数ＲＯＭ４６へ供給
すると共に、データセレクタ５７からデフォルトで出力
された値１を対数ＲＯＭル４７へ供給し、夫々の対数に
変換し、ＡＬＵ４８で互いに加算し、その結果をＡＬＵ
レジスタ５０を介してアドレスレジスタ（ＡＤＲレジス
タ）５８ヘセツトする。

ＡＤＲレジスタ （６）式より、この値が誤りを含んだシンボルｉを示す
ことがわかる。

（２３）　　ｉがゼロから５８までの値であれば、誤り
を含んだシンボルｖｉ′が特定されたこととな＝　　３
９　− り、ｉが５９以上の値であるときは、（１７）において
誤りを含んだシンボルが１つだけとした判断が誤まって
いたとして、３シンボル以上に誤りを含む場合の処理に
移行する。ここではｉがゼロから５８の値であるとして
以下の誤り訂正操作を行う。

（２４）　　Ａ　Ｄ　Ｒレジスタ５８にセットされた値
を第１図に示す回路のコントロール部（図示せず）へ出
ツノする。

（２５）　　Ａ　Ｄ　Ｒレジスタ５８から出力された値
に対応するアドレスのシンボルｖｉ′をメモリ３０より
読み出し、ＭＲレジスタ３３にセットする。

（２６）　　Ａレジスタ５３ｂをクリアすると共に、Ｓ
ｏレジスタ４１ｃより読み出された値ｓｏをデータセレ
クタ４４を介して対数ＲＯＭ４６に供給し、データセレ
クタ５７よりデフォルトで出力された値１を対数ＲＯＭ
４７に供給する。

対数ＲＯＭ４６．４７の出力をＡ１．Ｕ４８において加
算し、ＡＬＵレジスタ５０にセットする。

１０Ｑ（ｘＳｏ＋１０ｇ（Ｚｌ−１０９（ｘＳ。

ＡＬＬＪレジスタ （２７）　　Ａ　Ｉ　Ｕレジスタ５０の内容を指数ＲＯ
Ｍ５１においてαのベキ乗に変換し、加算回路５３ａを
介してＡレジスタ５３ｂにセットすると同時に、ＭＲレ
ジスタにセットされた内容（Ｖ　ｉ　）を（２６）と同
様なπ１算を行ってＡＬＵレジスタ５０にセットする。

。 Ｓ□＋０−＝Ｓｏ　　Ａレジスタ ｌｏｏ、Ｖｉ’　＋　１ｏ−１＝　ｔｏｏ（ｘＶｉ’△
ｌ−Ｕレジスタ （２８）　　Ａ　Ｌ　Ｕレジスタ５０にセットされた内
容（ＩＱ（＋（ｘＶ　ｉ　’　）を指数ＲＯＭ５１にお
いてαのベキ乗に変換するとともに、加算回路５３ａに
おいてＡレジスタ５３ｂにゼットされた内容（Ｓｏ）と
加算し、新たにＡレジスタ５３ｂにセットする、。

Ｖｉ’＋Ｓ　　　　Δレジスタ （３）、Ｃｒ）式に対応して叩解されるようにＶ　ｉ　
’　＋　３０　＝　Ｖｉ となる。ここでＶｉは誤りを含むシンボル■ｉ′のデー
タが訂正されたシンボル（真のデータよりなるシンボル
）である。

（２９）　　Ａレジスタ５３ｂの内容（Ｖｉ）をデータ
セレクタ６６を介してメモリライトレジスタ（ＭＷレジ
スタ）６１にセットする。

（３０）　　ＭＷレジスタ６１にセットされた、誤りを
訂正されたデータｖｉをバッファ６２を介してメモリ３
０の対応するアドレスに書き込み、誤りＪ正操作が完了
する。

以上の一連の操作によって１つの誤りシンボルを含む場
合の誤り検出・訂正が行なわれる。（１）乃至（３０）
の各インストラクシ］ン・ステップのうら■、　（８）
、　（１３）、　（２７）における操作は、ＡＬｔＪレ
ジスタ５０を設はパイプライン方式としたことにより、
ＡＬＵレジスタ５０以前の演算（乗算の前段部）とＡ　
Ｉ　Ｕ　５０以降の演算（乗算の後段部と加算）を同時
に実行することが可能となり、誤り検出・訂正操作全体
の演算処理速度を大きく向上させることとなる。

２シンボル以上において誤りを含む場合の誤り検出・Ｊ
正操作についても、従来の技術の項において述べたよう
に、最終的にはシンドロームｓ−２゜・・・、Ｓ２につ
いての演算を行うことに帰着し、第１図の回路において
実行可能なことは言うまでもない。Ｆレジスタ６３．．
７ＲＯＭ６４．Ｆレジスタ６５などは２シンボル以上の
誤りを含む場合に用いられる。したがってより複雑な演
算が必要となる２シンボル以上の誤りを含む場合も、上
記のように乗算と加算とをパイプライン方式で同時に実
行し得ることとしたため、高速に誤り検出・訂正操作を
行うことが可能となる。

なお、本実施例では第３図における（２方向のデータ列
についての誤り検出・訂正操作を説明しだが、同様の操
作によって０１方向のデータについても誤り・訂正操作
が行なえることは言うまでもない。

更に、本発明は上記実施例に限るものではなく、リード
・ソロモン符号によるパリティを含むディジタル・デー
タであれば、容易に誤り検出・訂正操作を実行すること
が可能である。

発明の効果 上述の如く、本発明によれば、乗算を行う部分の後段に
第１のレジスタを設けるという比較的簡単な構成によっ
て、誤り検出・訂正を行う場合のシンドロームの乗算及
びυｌ：　（ｌ！！的論理和演算を、排他的論理和演算
が行なわれている期間中であっても次のデータの乗算の
実行が可能なパイプライン方式とし、膨大な量のデータ
の演算処理が必要な誤り検出・訂正操作の実行にかかる
時間を短縮することができ、したがって回路を構成する
素子としては特に高速のものを必要とぜず、高集積化が
容易であり、又上記のように回路構成が比較的筒中なこ
とにより、］スト的に有利であり、本発明装置を制御す
るコントロール手段の操作の複雑化を軽減し、本発明装
置とともに小規模化を図ることができ、小型化に適して
いる舌の特長を有する。

【図面の簡単な説明】

第１図は本発明の一実施例の回路図、第２図は本実施例
におけるメモリのメモリマツプ、第３図は第２図のメモ
リマツプのデータ領域を示す図、第４図及び第５図は従
来装置の回路の主要部の一例を示すブロック図である。 １．３４・・・シンドローム生成部、３・・・乗算部、
３ａ、３ｄ、１０ａ、１０ｂ、、４６．４７−・・対数
変換部（対数ＲＯＭ）　、３ｂ、１１．４８・・・算術
演算部（ＡＬＵ）、３ｅ、１４．１５．５１・・・指数
変換部（指数ＲＯＭ）、４ａ、１６．３５ｃ　〜３９ｃ
、５３ｃ・・・加算回路、４．５３・・・加算部、３０
・・・メモリ、４５・・・乗算部、４９・・・対数ゼロ
検出回路、５０　・Ａ　Ｌ　Ｕレジスタ（ＡＩ−１Ｊｒ
ｅｃ））、５３ｂ・・・Ａレジスタ（Ａｒｅｇ＞　、５
４・ＢＬ／ジスタ（Ｂｒｅｇ）、５５・Ｃレジスタ（Ｃ
ｒｅｏ）、５６　・Ｄレジスタ（Ｄｒｅｇ）。

Claims (1)

1. 【特許請求の範囲】 リード・ソロモン符号による検査ワードを付加されたデ
   ータを所定のメモリマップに従って記憶するメモリと、 該メモリより読み出された該データを用いてシンドロー
   ムを生成するシンドローム生成部と、該シンドローム生
   成部において生成された該シンドロームに対して所定の
   ガロア体上の演算を行い、誤りを含むデータを検出する
   と共に、検出された該誤りを含むデータに対する真のデ
   ータを算出する演算部とを有するリード・ソロモン符号
   による誤り検出・訂正装置において、 該演算部を、該ガロア体の原始元を底とする対数を求め
   るための対数変換部と、 該対数変換部の２つの出力データ同志を加算するための
   算術演算部と、 該算術演算部の出力を一時的に記憶するための第１のレ
   ジスタと、 該第１のレジスタの出力データを指数として、該ガロア
   体の原始元のベキ乗を求めるための指数変換部と、 排他的論理和演算を行う加算回路及び該加算回路の演算
   結果のデータを一時的に記憶する第２のレジスタを有し
   、該加算回路において該指数変換部の出力データと該第
   ２のレジスタに記憶されたデータとの排他的論理和演算
   を行い、その結果を新たに該第２のレジスタに一時的に
   記憶する加算部とによって構成し、 該対数変換部から該第１のレジスタまでの第１の演算処
   理と該第１のレジスタから該第２のレジスタまでの第２
   の演算処理とを同時に実行可能としたことを特徴とする
   誤り検出・訂正装置。