JPS60178717A - リ−ド・ソロモン符号生成回路 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 産業上の利用分野 本発明はリード・ソロモン符号生成回路に係り、特にデ
ータ通信、ＰＣＭ録音器、ディジタル・オーディオ・デ
ィスク等でのデータ伝送における伝送データの符号誤り
を訂正するための誤り訂正符号として用いられるリード
・ソロモン符号を、大規模集積回路（ＬＳＩ）化に適し
た回路栴成で生成するリード・ソロモン符号生成回路に
関する。

従来技術 データ通信、ＰＣＭ録音器、ディージタル・オーディオ
・ディスク等でのデータ伝送において、伝送すべきデー
タに所定の方法で生成した検査ベクトルを付加して符号
化されたブロックとし、このブロック単位で伝送又は記
録をし、受信又は再生した信号中から上記の伝送すべき
データの符号誤りを検出し、検査ベクトルを用いて伝送
データの符号誤りを訂正してもとの正しいデータに復元
する誤り訂正方法は従来よりよく知られている。上記の
検査ベクトル並びにその生成要素である伝送すべきデー
タとからなる誤り訂正符号は従来より各種知られている
が、そのうち誤り訂正能力と伝送情報の冗長度（検査ベ
クトルと検査ベクトル及びもとのデータの割合）におい
てリード・ソロモン符号が優れている。

まず、従来のリード・ソロモン符号の生成原理について
説明する。リード・ソロモン符号の符号語（ブロック）
は行マトリクス （ｄ＋　ｃｌｚ　−ｄｍ　Ｐａ　ＰＩ−Ｐｔ＋　）　（
１）で表わされる。ただし、ｄ１〜ｄ１ｎは夫々２ビツ
トのｍ個の伝送すべきデータ・ベクトル、Ｐｏ〜Ｐηは
夫々２ビツトのｎ個の検査ベクトルを示す（なお、２．
Ｐ　、ｎは夫々自然数）。有限体（ガ０７体）ＧＦ　（
２’　）上で定義したリード・ソロモン符号では、上記
の各ベクトルはＧＦ　（２”　）の元であり、乏、ｍ、
ｎの間には ２克−１≧ｉ＋ｎ＋１　０ なる条件が必要であることが知られている。伝送時（記
録時も含む）にはデータ・ベクトルｄ１〜ｄＴｎに対し
検査ベクトルＰｏ〜ＰＴＩを付加するが、検査ベクトル
ＰＧ〜ＰＴ＋は次式を満たすように生成される。

である。

上式を占き改めると の加算１乗算を示す（以下同じ）。この符号において、
検査マトリクスＨＯは０式の左沼のｎ＋１行ｉ＋ｎ＋１
列のマトリクスであり、次式で表わされる。

６）式のマトリクスの成る行に成る定数を乗じて、他の
成る行に成る定数を乗じたものと加算することを何度か
行なうと、次式の検査７１ヘリクスＨＯ’　が得られる
。

ＨＤ’　も検査マトリクスであるから となるから、Ｐａ”−ＰＴｌは（６）、Ｃｒ）式から次
のようにめられる。

個のβ０　（Ｔｌ１１１　’）〜βＴｌ　（？ｌ＋１　
）は定数ベクトルである。

そこで、従来は上記の生成原理に基づき、第１図に示す
如き回路でリード・ソロモン符号を生成していた。第１
図において、入力端子１にはデータ・ベクトルｄ１〜ｄ
ｍが順次にシリアルに入来し、ｎ＋１個のリード・オン
リ・メモリ（ＲＯＭ）２０〜２ηに夫々並列に供給され
る。ＲＯＭ　２０はデータ・ベクトル（Ｌ　”　ｄＴｎ
の夫々に対して前記βＱ（Ｔｌ１１１）〜β０（η＋１
）を乗じた値（ベクトル）がテーブルとして予め記憶さ
れている。同様に、ＲＯＭ２ｋにはβｋ（欝）○ｄ１〜
βｋ（η＋＋）Ｏｄｍなるｍ個−のベクトルがテーブル
として予め記憶されている（ただし、ｋは１，２．・・
・、ｎ）。

ＲＯ’Ｍ２ｏ〜２ｎは入力端子３よりの列制御信号によ
り上記のテーブルのｍ個のベクトルを順次に切換出力さ
れる構成とされている。ＲＯＭ　２　ｏ〜２ηの各出力
信号は、対応する加算回路４０〜４ηを通してレジスタ
５０〜５ηに供給される。

加算回路４０〜４Ｔｌとレジスタ５０〜５１１とよりな
る夫々の回路部は、より詳細には第２図に示す如き回路
構成とされている（ただし、２が４の場合）。レジスタ
５０〜５Ｔｌは最初のデータ・ベクトルｄ１の入力に先
立って入力端子６よりのクリア信号によりクリアされ、
次に直前のレジスタ５０〜５Ｔｌの値（最初はクリアに
より０である）と、ＲＯＭ　２　ｏ〜２Ｔｌの出力信号
の値とを夫々加算回路４０〜４ηで加算して得られた信
号（ベクトル）を記憶することを、入力端子７よりのク
ロック信号に基づいて繰り返す。このようにして、最終
的にはレジスタ５ｏより出力端子８０へ前記（８−１＞
式で表わされる検査ベクトルＰＯが取り出され、またレ
ジスタ５１より出力端子８１には（８−２）式で表わさ
れる検査ベクトルＰ１が取り出され、以下同様にしてレ
ジスタ５Ｔｌより出力端子８Ｔｌには（８−ｎ　＋１　
＞式で表わされる検査ベクトルＰＴＩが取り出される。

出力端子８０〜８ηより取り出された検査ベクトルＰＯ
〜Ｐηは、入力端子１よりのデータ・ベクトルｄ１〜ｄ
ｔｎと共に、公知のインターリーブ処理をされて（しな
くてもよい）、シかる後に順次時系列的に合成されて前
記（１）式の行マトリクスで表わされたリード・ソロモ
ン符号が生成される。

第３図はインターリーブされたリード・ソロモン符号と
その頭初位置に付加された５ＹＮＣで示す同期信号とよ
りなるディジタル信号の信号フォーマットを示す。なお
、第３図中、Ｄは遅延演算子で、インターリーブされた
ベクトルであることを示す。

発明が解決しようとする問題点 しかるに、上記の従来回路はＲＯＭが第１図に２０〜２
Ｔｌで示す如くｎ＋１個必要であり、大容量のメモリが
必要となる。例えば、ｅ＝Ｂ、ｍ　＝２８、ｎ　＝３の
場合、すなわち有限体ＧＦ　（２８）での（３２，２８
）リード・ソロモン符号を考えると、この検査マトリク
ス］」０′は（１Ｂ）式かられかるように、４行３２列
で、ＲＯＭは４個必要となる。またＧＦ　（２ｇ　）の
元である各ベクトルは８ビツトであるから、これら４個
のＲＯＭの夫々は８ビツトのベクトル入力と、３２列を
識別するために必要な５ビツトの列制御信号の入力とが
供給され、８ビツトのベクトルを出力する構成であるか
ら、 ８（ビット）　ｘ　２＋３＝　６５５３６　（ビット）
のメモリ容量を必要とする。しかして、このような大メ
モリ容量のＲＯＭを４個まとめてＬＳＩ化するのは、現
在のしＳｌ技術では困難で極めて高価となってしまう。

一方、上記のＲＯＭをＬＳＩとは別チップで１個ずつ計
４個接続するようにした場合は、全体の回路の形状が大
きくなりスペースファクタの点で不利であり、また極め
て高価であるという問題点があった。

そこで、本発明は検査マトリクスよりも元の数が少ない
マトリクスを新たに定義し、そのマトリクスとデータ・
ベクトルとを用いて中間演算値（ベクトル）をまず算出
し、しかる後にそ−の中間演算値に所定の定数を＠算し
たりそれらの結果を加算したりして所望の検査ベクトル
ＰＯ〜Ｐｎを生成することにより、上記の問題点を解決
したリード・ソロモン符号生成回路を提供することを目
的とする。

問題点を解決するための手段 本発明は、一方の入力端子がｍ個の各２ビツトのデータ
・ベクトルｄ１〜ｄＴＩ＋が順次に入力される入力端子
に接続されたｎ十ｉ個の第１の加算回路と、第１の加算
回路に対応してｎ＋１個設けられており第１の＋＋０算
回路の出力信号を記憶するクリア可能な各２ビツトの記
憶回路と、口＋１個の記憶回路のうち−の記憶回路の出
力信号は直接に該−の記憶回路の入力側に設けられたー
の該第１の加算回路の他方の入力端子に供給すると共に
、残りの１１個のうちｋｌ目（ただし、ｋ　＝１．２゜
・・・、ｎ）の該記憶回路の出力信号はその記憶回路の
入力側に設けられたに番目の該第１の加算回路の他方の
入力端子にαＫ　（ただしαは有限体ＧＦ（２ｉ）の原
始元）を乗する第１の乗算回路を介して供給することに
より、ｎ＋１＠の該記憶回路より次式 せる手段と、前記検査ベタ１〜ルＰＧ〜Ｐ１に関する（
ｎ＋１＞元連立方程式 における（ｎ＋１）２個の定数ベクトルａＯＯ〜ａＴ＋
ｎのうちｎ＋１個の定数ベクトル６ｏ　Ｖ　。

へ＋Ｖ、へ２Ｖ、・・・、へＴｌｙ　（ただし、■−〇
。

１．２．・・・、０）と上記ベクトルＱ’／どの有限体
ＧＦ　（２ｋ）上の乗算を別々行なう０＋１個の乗算回
路が該ベクトルＱｏ〜Ｑ毛の夫々に対して設けられた全
部で（ｎ＋１）２個の第２の乗算回路と、該第２の乗算
回路のうち該定数ベクトルａｙＯ〜ａｙηを乗するｎ＋
１個の乗算回路の出力信号に対して夫々有限体ｃ、Ｆ（
２１＞上の加算を行ない検査ベクトルＰｙを生成出力す
る加算回路がｎ＋１組からなる第２の加算回路とより構
成したものであり、又は上記の第＼２の乗算回路及び第
２の加算回路に代えて、データセレクタと２個の縦続接
続された乗算定数が夫々１又はα２　（ただし、Ｚ　＝
２（ｒ−’）、　ｒ　＝１．２．　＝・、　ｆｌ＞　に
切換制御される第３の乗算回路と、第３の乗算回路の出
力信号と第２の記憶回路の出ツノ信号とのＧＦ　（２’
　）上の加算を行なう第３の加算回路と、前記定数ベク
トルへＶｏ−こｙｌｌの値が第３の乗算回路全体により
順次に得られるように上記乗算定数の切換制御を行なう
ことにより該第２の記憶回路より（ＱＶ　Ｄ　ａＶ　＋
　・、、ａｙ　’ｎ　）○（ＱｏＱ＋・・・ＱＴＩ）” （Ｔは転置行列を示す） なる式により表わされる検査ベクトルＰｙを生成出力す
ることを、ｙ−０〜ｎの夫々についてｎ＋１回行なって
該第２の記憶回路より検査ベクトルＰｏ〜Ｐηを順次に
出力せしめるデータセレクタ及び第３の乗算回路制御手
段とより構成したものであり、以下その各実施例につい
て第４図乃至第７図と共に説明する。

実施例 本発明になるリード・ソロモン符号生成回路について説
明するに先立ち、まず本発明回路によるリード・ソロモ
ン符号の生成原理について説明する。本発明ではまずマ
トリクスＨ１を次式で示す如くに定義し、しかる後にＨ
ｌとデータ・ベクトルｄ１〜（１ｍとを用いて中間演算
１直（ベクトル〉Ｑｏ”□Ｑｖ＋を算出する。ここに、 原始元であることはａ〜６）式と同一である。中間演算
ベクトルＱＯ〜Ｑηは上記のｎ＋１行１列マトリクスＨ
１とデータ・ベクトルｄ１〜ｄｍとを用いて （１０）式を書き改めると（９）式よりは（４）式の一
部の演算（ｄ＋　”−ｄｍのみの演算）を行ない、かつ
、第１行〜第ｎ行を夫々１〜α１°（ｎ＋１〉で除算し
たものとなっている。従って、次式が成立する。

（１２）式は検査ベクトルＰｏ”Ｐηに関する（ｎ＋１
）元連立方程式となっており、これを整理すると次式が
得られる。

α（η音１）○Ｑ＋、、＝−、−α１−（η＋”０ＱＴ
ｌユαη”　”　）ＯＱＴ＋である。

（１３）式を解くと、検査ベクトルＰｏ〜ＰＴＩは中間
演算ムク１〜ルＱＯ〜ＱＴＩの一次結合で表わされて次
式に示す如くになる。

この（１４−１）弐〜（ｉ４−ｎ　＋　１＞式によって
検査ベクトルＰＧ〜Ｐηを算出するのが、本発明回路で
ある。

次に本発明回路の回路構成並びに動作について説明する
。第４図は本発明回路の第１実施例のブロック系統図を
示す。同図中、入力端子１０にはデータ・ベクトルｄ１
〜（１，がシリアルに入来する。従って、まず入力端子
１０にはデータ・ベクトルｄｌが入来し、ｎ＋１個の加
算回路１１ｏ〜１１ηを経て対応するｎ−＋−ｉ個の各
２ビツトのレジスタ１２０〜１２ｎに夫々供給される。

加算回路１１ｏ　は入力データ・ベクトルとレジスタ１
２゜の出力ベクトルとの夫々有限体ＧＦ　（２”　）上
の加算を行なう。同様に、加算回路１１ｋ　（ただし、
ｋは１，２．・・・、ｎ）は入力データ・ベクトルとレ
ジスタ１２にの出力信号を乗算回路１５にで乗算して得
たベクトルとの夫々有限体ＧＦ　（２Ｌ）上の加算を行
なう。乗算回路１５にの乗算係数はαＫに選定されてい
る。加算回路１１０〜１１ηの夫々は第２図に示した従
来回路と同様に、２個の２人力排他的論理和回路（以下
ＥＯＲ回路と記す）で構成されており、２個の各ＥＯＲ
回路の一方の入力端子には入力端子１０よりのデータ・
ベクトルの対応する１ビツトが入力され、他方の入力端
子にはレジスタ１２０又は乗算回路１５１〜１５Ｔｌの
対応する１ビツトの出力信号が入力される構成とされて
いる。

レジスタ１２０〜１２１は入力端子１３より入来するク
リア信号により、データ・ベクトルｄ１が入来する直前
に夫々クリアされており、以後入力端子１４よりのクロ
ック信号が入来する毎に加算回路１１０〜１１Ｔｌの出
力ベクトルを一時記憶する。入力端子１０よりの各デー
タ・べ、クトルｄ１〜ｄＴｎのシリアルな入力周期と入
力端子１４よりのクロック信号周期とは同期しており、
最後のデータ・ベクトルｄＴｎが入力端子１０に入来し
た後、レジスタ１２ｏ〜１２ＴＩの各２ビツトの出力端
子には（１１）式に示される中間演算ベクトルＱＯ〜Ｑ
１が夫々取り出される。この演算の流れをレジスタ１２
＋を例にとって説明すると次表で示す如くになる。

表　ル ラスタ１２０より取り出された上記中間演算ベクトルＱ
Ｏは、（１４−１）〜（１４−ｎ＋１＞（７）各式に示
したｎ＋ｉ個の定数ベクトルａＯＯ＋ａｚｏ　Ｔ　２１
２ｏ　＊　−＊　ａｎｏのうちの−の定数べクトルを乗
するｎ＋１個の乗算回路１６ｏ　、　１７ｅ　。

・・・、１８ｏに夫々供給される。同様にレジスタ１２
により取り出された中間演算ベクトルＱｋは、０＋１個
の定数ベクトルａｏ　ｋ、ａｒｋ、ａ２ｋ。

・・・、ａＴｌｋを別々に乗するｎ＋１個の乗算回路に
供給される。なお、第４図中、乗算回路１６Ｉ。

１６Ｔ１．１７１　、１７η、１８＋、及び１８ηは夫
々定数ベクトルａｏ　＋　、ａｏη、　ａｔ　＋　。

ａｎ＋、ａη１及びａｎｎを乗する乗算回路である。上
記の（ｎ＋１）２個の各定数ベクトルａＯＯ〜へηηの
６値は、０．α０　（＝１）〜αト２のうちのどれかで
ある（ただし、１−２１；、以下同じ）。

乗算回路１６ｏ　、１６＋　、・・・、１６ηにより定
数ベクトルａｏ　ｎ　＊　ａｏ　＋　、・・・、ａｏη
を乗じられたベクトルＱｏ　、Ｑ＋　、・・・Ｑηは加
算回路１９゜に供給され、ここで有限体ＦＧ　（２’　
）上の加算を行なわれる。これにより、加算回路１９ｏ
は（１４−１）式で表わされた検査ベクトルＰｏを生成
して出力端子２０ｏへ出力する。また乗算回路１７ｏ　
、１７ｔ　、・・・、１７Ｔｌにより定数ベクトルａ＋
Ｏ，ａ＋＋、・・・＊　ａ　＋　Ｔｌを乗じられたベク
トルＱＯ，Ｑｌ、・・・、Ｑηは加算回路１９１に供給
され、他方、乗算回路１８０　、１８＋　、　−、１８
Ｔｌにより定数ベクトルａｔ＋ｏ、ａη１．・・・、ａ
Ｔｌｙ＋を乗じられたベクトルＱＯ、Ｑ＋　、・・・、
Ｑｎは加算回路１９１に供給される。このようにして、
加算回路１９＋、１９４＋からは（１４−２＞式、（１
４−ｎ＋１＞式で表わされる検査ベクトルＰ＋。

ＰＴＩが生成されて取り出され出〕〕端子２０１゜２０
ηへ出力される。同様に、第４図では図示を省略した加
算回路１９２〜１９　ｎ−＋からは検査ベクトルＰ２〜
Ｐ　Ｔｌ−１が取り出されることは明らかである。出力
端子２００〜２０Ｔｌより取り出された検査ベクトルＰ
ｏ〜Ｐ　１１は従来回路と同様にして（１）式で表わさ
れるリード・ソロモン符号の符号語を生成させる。

次に本実施例に必要なＦＯＲ回路の数について説明する
。一般に有限体ＧＦ　（２’　）上の乗算はスで表わさ
れる（ＧＦ　（２Ｌ）の元はＧＦ■の２次元ベクトルで
ある。）。ここで、上記の１１１１〜ｂＬ　Ｒ，は各１
ビツトでＯ″又は′１″の値である。上記の乗算に必要
なＥＯＲ回路の数は（１５）式の各行毎に（゛１″の個
数）−１個必要であり、また（１５）式は正則マトリク
スであるから、各行とも１個以上の１″があるため、様
々な乗算定数の平均的な数を考えると、１行あたり＋＋
　１　＋＋の値の要素は（之／２＞＋０．５個あるから
、ＥＯＲ回路は１行当り（之／２）−０，５個必要とな
る。

従って、ＧＦ　（２”　）上の乗算に必要なＦＯＲ回路
の数は、平均的には９　（１／２　＞　−０，５）個必
要となる。しかし、これは平均値であって、有限体ＧＦ
（２１）上の乗算に必要なＦＯＲ回路の数は、最小１個
から最大Ｉｌ（之−１）個までの範囲のいずれかである
。

例えば、之を４とし、有限体ＧＦ　（２４）上で原始多
項式ｘ４＋ｘ＋１を法とする乗算に必要なＦＯＲ回路の
数について説明する。この場合α４十α＋１＝Ｏとする
原始元αと４ビツト　ｂｌ　。

ｂｌ、ｂ３．　ｂ、の６値（ｂｌがＭＳＢ、ｂ４がしＳ
Ｂ）との関係をまとめると次表に示す如くになる 表　２ なお、α１５は１である。いま有限体ＧＦ　（２４）の
ベクトルａ、ｂと原始元αとの間の乗算の一例として、 α□ａ＝ｂ　（１６） を行なうものとする。ただし、上式中、ａＱ（ａ＋、ａ
２１　ａｓ、ａ４）、ｂＭ（ｔｚ、ｂｚ。

ｂ３．ｂ４）であるものとする（へは定義を示す）。（
１６）式の乗算はマトリクスを用いて次のように表わさ
れる。

となる。従って、（１６）式の乗算を行なうための乗算
回路は、第５図に示す如く１個のＦＯＲ回路２１のみを
用いて構成することができる。

次に本実施例と第１図に示した従来回路とを、有限体Ｇ
Ｆ　（２８）上の（３２，２８）リード・ソロモン符号
生成の場合（ｅ＝８．ｒａ　＝２８．ｎ−３）を例にと
って比較すると、従来回路では前記した如く各メモリ容
ｆｆｌ　６５５３６ビツトのＲＯＭが４個必要となるの
に対し、本実施例では有限体ＧＦ　（２８＞上の乗算を
行なう乗算回路は１５１〜１５３と、４つの加算回路１
９ｏ〜１９３の入力側に夫々４個ずつ設けられる乗算回
路とよりなる計１９個と、加算回路が１９ｏ〜１９３の
計４個必要となる。それらに必要なＥＯＲ回路数は、乗
算回路１個当り２８　（＝　３．５ｘ８）個（平均値）
、４人力加算回路１個当り２４　（＝　（４−１）Ｘ８
）個であるから、結局本実施例においてＲＯＭ４個の代
りに必要なＥＯＲ回路の総数は ２８　Ｘ　１９　＋　２４　Ｘ　４　＝　６２８　（個
’）　（１９）となる。この６２８個というＥＯＲ回路
数は現在のＬＳＩ技術で充分ＬＳＩ化できる程度の数で
あり、よって本実施例は従来回路に比しＬＳＩ化に適し
た回路構成であるといえる。

ところで、第４図に示した実施例では検査ベクトルの数
が多くなると、乗算回路が極めて多く必要となる。例え
ば、検査ベクトルの数が１６であるものとすると、その
ときに必要な乗算回路は１６ｘ１６＋　（１６−１＞＝
　２７Ｈ個）　（２０）となる。そこで、（１４−１）
〜（１４−ｎ＋１）式における（ｎ＋１）２個の定数ベ
クトルａＯＯ〜ａｎＴ＋との有限体ＧＦ　（２’　）上
の乗算と、（ｎ＋１）項の有限体ＧＦ　（２１＞上の加
算について改善した回路構成の第２実施例について第６
図及び第７図と共に説明する。

第６図は本発明回路の第２実施例のブロック系統図を示
す。同図中、第４図と同一構成部分には同一符号を付し
、その説明を省略する。本実施例は中間演算ベクトルＣ
Ｌ〜Ｑηの算出は第１実施例と同一であるが、（１４−
１）〜（’１４−ｎ＋１）式の演算の回路構成が第１実
施例と異なる。

すなわち、レジスタ１２ｏ〜１２Ｔｌより取り出された
ｎ＋１個の中間演算ベクトルＱｏ〜ＱＴＩはデータセレ
クタ２２に供給される。データセレクタ２２はセレクト
端子ＳＬとストローブ端子５ＴＲＢを有しており、ＲＯ
Ｍ２３よりの１又は２以上のビット数の選択信号により
Ｑｏ＝Ｑηを順次巡回的に切換出力する。ＲＯＭ２３は
入力端子２４よりの制御信号に基づいて、後述する乗算
回路２６＋〜２６Ｌへ出力する２ビツトの制御信号の値
が変更せしめられている。入力端子２４よりの制御信号
は、後述する出力端子２９より取り出される−の検査ベ
クトルがＰｏ〜ＰＴのうちのいずれかであるかを定める
ための信号である。また、ＲＯＭ２３より取り出される
２ビツトの制御信号は２人力ＮＡＮＤ回路２５を通して
データセレクタ２２のストローブ端子５ＴＲＢに印加さ
れ、２ビツトの値がオールＬＬ　１　＋＋のときにのみ
、データセレクタ２２の出力信号の値を強制的にｉｔ　
Ｏ＋＋とする。

データセレクタ２２より中間演算ベクトルＱＯ〜Ｑηが
順次選択出力されるが、データセレクタ２２よりいま−
の中間演算ベクトルＱｊ　（ただし、ｊＬｔｏ、１．２
．・・・、ｎ）が出力されているものとする。この出力
ベクトルＱｊは互いに縦続接続されている２個の乗算回
路２６＋〜２６Ｌに順次に供給される。乗算回路２６＋
〜２６Ｌは夫々同様の構成とされており、そのうち１番
目（ただし、ｒ−１，２，・・・、２）の乗算回路２６
ｒは第７図に示す如き回路構成とされている。第７図に
おいて、入力端子２６１ｒに入来した信号（ベクトル）
は、データセレクタ２６２ｒに直接に供給される一方、
αＺ　（ただし、ｚ　＝　２　（ｒ−１）　）を乗する
乗算器２６３ｒを介してデータセレクタ２６２ｒに供給
される。

データセレクタ２６２ｒは入力端子２６４ｒに入来する
ＲＯ’Ｍ２３よりの２ビツトの制御信号のうち予め割当
てられたｒビット目の１ビット信号か供給され、例えば
その値がＯ″のとぎ入力端子２６１ｒの入力信号を選択
出力し、“１″のときは乗算器２６３ｒの出力信号を選
択出力するよう構成されている。従って、出力端子２６
５ｒには入力端子２６４ｒよりの１ビツトの制御信号に
応じて、入力端子２６１ｒの入力信号に対してα２°（
ｒ−＋　）を乗じた信号と、１′″を乗じた信号（すな
わち乗算を行なわない信号）のいずれか一方が選択出力
されることになる。

ここで、有限体ＧＦ　（２児）の元はｏ、　ｉ　＜＝α
０）、α、α２．α３．・・・、αト２で表わずことが
できるから、ＧＦ（・２え）上の乗算は０．αＯ〜αト
２のいずれかとの乗算となり、２トＩ（これは１である
）を乗することは不要となる。乗算回路２６＋〜２６ｔ
を制御信号により制御することにより、乗算回路２６１
〜２６Ｌよりなる縦続接続回路はデータセレクタ２２の
出力ベクトルＱｊに対して、１．α、α２．・・・、α
１−１のうちの任意の乗算係数（ａＯａ〜ａｎｎのうち
の任意の−の定数ベクトル）との乗算を行なうことがで
きる。更に、上記の如く２ト１を乗することは不要なの
で、２１−１を乗するような制御信号（２ピツトすべて
が１″の値の信号）がＲＯＭ２３より出力される場合は
、データセレクタ２２のストローブ端子５ＴＲＢに供給
される２人カＮＡＮＤ回路２５の出力がローレベルとな
り、これによりデータセレクタ２２の出力信号を強制的
に０とすることにより、上記縦続接続回路はＯとの乗算
を行なうことができる。

なお、Ｏを乗する制御は、乗算回路２６１〜２６ｔのう
ちいずれか一回路に、データセレクタ２２と同様のスト
ローブ端子５ＴＲＢを設けてその制御を行ない、その出
力信号を強制的にＯにすることにより行なうこともでき
る。

上記縦続接続回路の最終段の乗算回路２６克より取り出
された出力信号は加算回路２７に供給され、ここでレジ
スタ２８の出力信号と有限体ＧＦ（２兇）上の加算が行
なわれた後レジスタ２８に供給される。レジスタ２８は
加算回路２７より最初の信号が出力される前に、そのク
リア端子ＣＬＲに入力されるクリア信号によりクリアさ
れ、しかる後にそのクロック端子ＣＫにクロック信号が
入力される毎に、レジスタ２８のその時の記憶内容を出
力端子２９へ出力する一方、加算回路２７ヘフイードバ
ツクし、これと乗算回路２６Ｌの出力信号との加算値を
新たに記憶することを繰り返す。

一方、レジスタ２８のクロック信号の入力周期に対応し
てデータセレクタ２２の出力ベクトルがＱｏ−Ｑｎのう
ち次のベクトルに順次に切換えられると共に、乗算回路
２６１〜２６Ｌによる全体の乗算定数が前記定数ベクト
ルａｏｏ”□ｃｌηｎのうち所定の−の定数ベクトルの
値へ切換制御されることがｎ＋１回繰り返される。これ
によりレジスタ２８より出力端子２９へは （ａｙ　Ｏａｙ　＋　−−−ａｙ　ｎ　）、ＯＣＱｔｒ
　Ｑ＋・・・ＱＴＩ）”　（２１） （ただし、王は転置行列を示す） なる式で表わされる検査ベクトルＰｙが生成出力される
ことになる（ただし、ｙ−〇、１，２．・・・。

ｎ）。

このようにして、上記と同様の動作がｎ＋１回繰り返さ
れることにより、（１４−１）〜（１４−ｎ＋１）式で
示される検査ベクトルＰＯ〜Ｐηが出力端子２９に順次
時系列的に取り出される。

この出力端子２９より取り出された検査ベクトルＰＯ〜
Ｐｎｌｉ第１実施例と略同様にしてリード・ソロモン符
号の符号語を生成させる。

本実施例によれば、（１４−１）〜（１４−ｎ＋１）式
で示した（ｎ＋１）２個の定数ベクトルａｏｏ−ａＴＩ
Ｔｌを乗する制御は、２ビツトのメモリを（ｎ→−１）
２個持ったＲＯＭ２３と２個の乗算回路２６１〜２６Ｌ
とを用いて行なうようにしている。一方、第４図に示し
た第１実施例では、上記の乗算制御は１６ｏ〜１６Ｔ１
．１７０〜１７η。

１’８ｏ〜１８１等よりなる全部で（ｎ＋１＞２個の乗
算回路で行なっている。従って、定数ベクトルａＯＯ〜
ａηηを乗する制御のための回路部を、本実施例と第１
実施例について回路素子数で比較すると、本実施例では
２ビツトのメモリが（ｎ＋１）２個とＥＯＲ回路が之（
１／２＞　−０，５，）×２個とよりなるのに対し、第
１実施例では２（（［／２）　０．５）ｘ（ｎ＋１）２
個のＦＯＲ回路とよりなる。

ここで、通常ＬＳＩでは概略１ビツトのメモリは１ゲー
トで構成でき、ＥＯＲ回路は４ゲートで構成することが
できるから、本実施例では上記の回路部は（乏（ｎ＋１
）２＋４２２　（（乏／２）−０，５）　）ゲートで構
成でき、第１実施例のこれに相当する回路部の４４　（
（ｅ／２）−０，５）ｘ＜ｎ＋１）２ゲートに比し、前
記した有限体ＧＦ（２８）上の（３２，２８）リード・
ソロモン符号生成の場合（ｅ＝８．ｍ　＝２８．ｎ　＝
３＞を例にとると、本実施例の方が７６８グー１〜少な
く構成することができる。検査ベクトルの数が増えるほ
ど上記の０の値は人となるから、本実施例のゲート数は
第１実施例のゲート数に比べてより一図低減することが
できろくゲート数の差を大にすることができる）。

また、第４図、第６図における中間演算ベクトル算出部
を変形して、第８図に示す如く、第１の乗算回路１５１
′〜１５１′を第１の加算回路１１１〜１１ηとレジス
タ１２１〜１２ηの伝送路の中間に夫々置き、レジスタ
１２１〜１２Ｔｌの出力は直接第１の加算回路１１１〜
１１ηの一方の入力端子に接続する様にしてもよい。こ
のときレジスタ１２０〜１２Ｔｌの出力から得られる中
間演算ベクトルをＱＯ″〜Ｑπ″とすると、このとき、
これら中間演算ベクトルＱＯ″〜ＱＴｌ″とめる検査ベ
クトルＰＯ−ＰＴｌとの間には 求めた場合と同様に、Ｐｃ”−ＰＴｌは上記連立方程式
の解として、 ける第２の乗算回路で乗ずべき係数をａＯＯの代りにａ
ｏｏ″、ａｏ＋の代りにａｏ　＋　”　、　−−ａ’ｎ
ｔ＋の代りにｄＴＩＴ１″と夫々対応させれば、前述と
同様にして検査ベクトルＰＤ〜Ｐａｌが算出できる。な
お、演算の流れをレジスタ１２＋を例にとると表３に示
すようになる。

表３ 次に第４図及び第７図に示す各実施例は、検査ベクトル
の位置が０）式に示したようなデータ・ベクトルｄ１〜
ｄＴＩＩの後ではなく、データ・ベクトルｄ＋　”　ｄ
ｍの中間位置に混在してリード・ソロモン符号の符号語
を構成する場合にも、適用することができることについ
て説明する。いま、符号語を （ｄ＋　−ｄＡＩＰＧ　’　ｄＡ２−・＝ｄａ＋　Ｐ＋
’　ｄａ２・＝Ｐｔ＋’　ｄｃ＋−ｄｔｎ）（２６） とする。ここに、ＰＧ　’〜Ｐη′は検査ベクトル、ｄ
Ａｌ、　ｄＡ２　、　ｄｓ　＋　、　ｄａ２　、　ｄａ
　＋はｄ２〜ｄＴｌ＋−１のうちいずれかのデータ・ベ
クトルである。検査マトリクスＨＤ　は０式である。こ
のとき、入力端子１０に（２２）式の順序に従ってデー
タ・ベクトルをｄｌより順次に入力していき、検査ベク
トルＰｏ′〜ＰＴｌ′の入力順番のときにはＯを入力す
るようにすると、中間演算ベクトルＱｏ’〜ＱＴ＋’　
は次式で算出される。

置を夫々（Ｉｎ　Ｉｎ　Ｓｏ　＋１）〜（ｍ　＋Ｌ　Ｓ
ｏｌ＋１）番目とすると、（１２）式と同様にして次式
が成立する。

従って、検査ベクトルｐｏｌ〜ＰＴｌ′は（１４−１）
　〜（１４−ｎ　＋１　）式と同様にしてＱｏ′〜０１
１′の一次結合としてめられ、次式が成立する。

同様の式となっており、従って第４図及び第６図の実施
例のどちらでも検査ベクトルの算出ができる。

効果 上述の如く、本発明によれば、検査マトリクスよりも元
の数が少ないマトリクスを定義し、そのマトリクスとデ
ータ・ベクトルとを用いて中間演算ベクトルを算出し、
しかる後にその中間演算ベクトルに所定の定数を乗算し
たりそれらの結果を加算したすして所望の検査ベクトル
を生成し、この検査ベクトルとデータ・ベクトルとから
リード・ソロモン符号を生成するようにしたから、従来
より極めて少ない数のＥＯＲ回路を用いて構成すること
ができるのでＬＳＩ化に適した回路構成とすることがで
き、現在のし８１技術で十分にＬＳ■化することができ
、更に前記中間演算ベクトルに定数ベクトルを乗する回
路として、中間演算ベクトルを時系列的に選択出力する
データセレクタの出力側に、２個の乗算回路を縦続接続
し、かつ、その乗算回路の各々をＲＯＭの出力信号で制
御できる溝底とした場合はＬＳＩ化した場合に検査ベク
トルの数が増えても極めて少ないゲート数で構成するこ
とができ、またＬＳＩ化が実現可能となったことにより
、リード・ソロモン符号生成回路を有する装置（データ
送信装置、ＰＣＭ録音器。

ＰＣＭ記録再生装置の記録系、ディジタル・オーディオ
・ディスクのカッティング系等々）の形状を小型化でき
ると共に量産により更に安価に構成することもできる等
の特長を有するものである。

【図面の簡単な説明】

第１図は従来回路の一例を示すブロック系統図、第２図
は第１図の要部の一例の回路図、第３図は伝送されるリ
ード・ソロモン符号の信号フォーマットの一例を示す図
、第４図及び第６図は夫々本発明回路の各実施例を示す
ブロック系統図、第５図は乗算回路の一例を示す回路図
、第７図は第６図図示ブロック系統中の乗算回路の一実
施例を示すブロック系統図、第８図は本発明回路の要部
の一変形例を示すブロック系統図である。 １．１０・・・データ・ベタ１〜ル入力端子、２０〜２
η、２３・・・リード・オンリ・メモリ（ＲＯＭ）、３
・・・列制御信号へカ端子、４０〜４η、２７・・・加
算回路、５０〜５ｎ・・・レジスタ、８０〜８Ｔｌ・・
・検査ベクトル出力端子、１１０〜１１ｎ、１９ｏ〜１
９７Ｉ・・・加算回路、１２０〜１２Ｔｌ　、　２８−
レジスタ、１５１〜１５Ｔ１．１５＋’　〜１５ＴＩ’
。 １６０〜１６ｎ、１７ｏ　〜１７Ｔ１．１８０〜１８η
。 ２６１〜２６η川乗算回路、２００〜２０η・・・検査
ベクトル出力端子、２２，２６２ｒ・・・データセレク
タ、２９・・・検査ベクトル出力端子、２６３ｒ・・・
乗算器。

Claims (2)

【特許請求の範囲】
1. （１）ｍ個の８乏ごットのデータ・ベクトルｄ１〜ｄｔ
   ｎとｎ＋１個の各２ビツトの検査ベクトルｐＨ−ＰＴＩ
   （ただし、２．ｍ　、ｎは自然数）とよりなる、有限体
   ＧＦ　（２”　）の元であるｌ＋ｎ千１個のベクトルが
   、 （ただし、○は有限体ＧＦ　（２”　’）上の乗算を示
   し、またαは有限体ＧＦ　（２’　）の原始元。 ２応−１≧ｍ＋ｎ＋１） なる関係を満足し、ベク［・ルｄ１〜ｄＴｎとＰ０〜Ｐ
   ＴＩとよりなる行マトリクスで表わされる符号語のリー
   ド・ソロモン符号を生成する回路において、一方の入力
   端子が上記データ・ベクトルが順次に入力される入力端
   子に接続された１）＋１個の第１の加算回路と、該第１
   の加算回路に対応してｎ＋１個設けられており該第１の
   加算回路の出力信号を記憶するクリア可能な各乏ビット
   の記憶回路と、ｎ＋１個の該記憶回路のうち−の記憶回
   路の出力信号は直接に該−の記憶回路の入力側に設けら
   れたーの該第１の加算回路の他方の入力端子に供給する
   と共に、残りのｎ個のうちに番目くただし、ｋ＝１．２
   ．・・・。 口）の該記憶回路の出力信号はその記憶回路の入力側に
   設けられたに番目の該第１の加算回路の他方の入力端子
   にαＫを乗する第１の乗算回路を介して供給することに
   より、ｎ＋１個の該記憶回路より次式 させる手段と、前記検査ベクトルＰＯ〜ＰＴＩに関する
   （ｎ＋１）元連立方程式 における（ｎ＋１）２個の定数ベクトルａＯＯ〜ａηη
   のうちｎ＋１個の定数ベクトルａｏＶ。 ａ＋Ｖ、’ａ２Ｖ、　・＝、ａｎＶ　（ただし、ｙ　＝
   ｏ。 １．２．・・・、ｎ）と上記ベクトルＱＶとの有限体Ｇ
   Ｆ　（２”　）上の乗算を別々に行なうｎ＋１個の乗算
   回路が該ベクトルＱｏ−Ｑηの夫々に対して設けられた
   全部で（ｎ＋１）２個の第２の乗算回路と、該第２の乗
   算回路のうち該定数ベクトルａＶｏ”ａＶηを乗するｎ
   ＋１個の乗算回路の出力信号に対して夫々有限体ＧＦ（
   ２乏）上の加算を行ない検査ベクトルＰｙを生成出力す
   る加算回路が口＋１組からなる第２の加算回路とより溝
   底したことを特徴とするり−ド・ソロモン符号生成回路
   。
2. （２）　ｍ個の各２ビツトのデータ・ベクトルｄｌ〜ｄ
   Ｔｌｌとｎ＋１個の各之ビットの検査ベクトルＰｃ”−
   Ｐｎ＜ただし、ｅ、ｍ　、ｎは自然数）とよりなる、有
   限体ＧＦ　（２”　）の元であるｍ＋ｎ＋ｉ個のベクト
   ルが、 （ただし、○は有限体ＧＦ　（２Ｌ）上の乗算を示し、
   またαは有限体ＧＦ　（２Ｌ＞の原始元。 ２党−１≧ｍ＋ｎ＋１） なる関係を満足し、ベクトルｄ１〜ｃｈｎとＰＯ〜ＰＴ
   とよりなる行マトリクスで表わされる符号語のリード・
   ソロモン符号を生成する回路において、一方の入力端子
   が上記データ・ベクトルが順次に入力される入力端子に
   接続されたｎ＋１個の第１の加算回路と、該第１の加算
   回路に対応してｎ＋１個設けられており該第１の加算回
   路の出力信号を記憶するクリア可能な各８ビツトの第１
   の記憶回路と、ｎ＋１個の該第１の記憶回路のうち−の
   記憶回路の出力信号は直接に該−の記憶回路の入力側に
   設けられたーの該第１の加算回路の他方の入力端子に供
   給すると共に、残りのｎ個のうちに番目（ただし、ｋ＝
   １．２．・・・、ｎ）の該記憶回路の出力信号はその記
   憶回路の入力側に設けられたに番目の該第１の加算回路
   の他方の入力端子にαＫを乗する第１の乗算回路を介し
   て供給することにより、ｎ＋１個の該第１の記憶回路よ
   り次式 させる手段と、該ベクトルＱｏ”−Ｑηが夫々供給され
   これらのうちの−のベクトルを選択出力するデータセレ
   クタと、該データセレクタの出り段に２個縦続接続され
   ており外部制御信号によりＧＦ　（２”　）上の２個の
   乗算定数が夫々１又はαｚ　（ただし、Ｚ＝２（’−’
   ）、ｒ＝１．２゜・・・、２）に互いに独立して切換制
   御される第２の乗算回路と、該第２の乗算回路の出力信
   号が一方の入力端子に供給される第２の加算回路と、該
   第２の加算回路の出力信号を記憶しその記憶出力信号を
   該第２の加算回路の他方の入力端子に供給してＧＦ　（
   ２”　）上の加算を行なわせる第２の記憶回路と、該デ
   ータセレクタをしてベクトルＱＯ〜ＱＴＩを順次に選択
   出力せしめると共に、前記検査ベクトルＰＯ〜Ｐ１に関
   する（ｎ＋１）元連立方程式 における（ｎ＋１）２個の定数ベクトルａＯＯ〜ｄＴＩ
   ＴＩのうち０＋１個の定数ベクトルａＶ。 〜ａｌ／ｌ＋（ただし、Ｖ　＝０．１，２．−、ｎ　）
   の値が該第２の乗算回路全体により順次に得られるよう
   に該乗算定数の切換制御を行なうことにより該第２の記
   憶回路より 〔ａｙ　ｏ　＆Ｖ　１＝・ａＶ　Ｔｌ　）■（ＱＱ　Ｑ
   ｌ・・・ＱＴＩ）” ＜Ｔは転置行列を示す） なる式により表わされる検査ベクトルＰｙ登生成出力Ｊ
   −ることを、ｙ＝Ｏ〜０の夫々についてｎ＋１回行なっ
   て該第２の記憶回路より前記検査ベクトルＰｏ”−ＰＴ
   ｌを順次に出力せしめるデータセレクタ及び第２の乗算
   回路制御手段とより構成したことを特徴とするリード・
   ソロモン符号生成回路。