JPH01130628A - 加算回路 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 （産業上の利用分野） 本発明は、誤り訂正符号にリード・ソロモン符号を使用
した誤り訂正回路等において、ガロア休の積算等を行う
際に必要な２−１（但し、ｎは２以上の複数、例えば８
）を法とする加非回路に関するものである。

（従来の技術） 従来、光デイスク装置のような情報記録装置等における
ディジタル信号の誤り訂正回路に用いられるガロア体演
算器（有限体演緯器）の加算回路に関する技術としては
、■テレビ技術、３４　［３］（昭６１−３−１＞電子
技術出版（株）、「誤り訂正符号の仕組みＪ　Ｐ、１９
−３５、■テレビ技術、３４　［４］　　（［１Ｈ６１
−４−１＞電子技術出版（株）、［誤り訂正符号の仕組
みＪ　Ｐ、３４−５３、■テレビ技術、且［５］　（昭
６ｌ−５−１）電子技術出版（株）、［誤り訂正符号の
仕組みＪ　Ｐ、３６−５８、■今井秀樹監修「誤り訂正
符号化技術の要点」１．えＱ（昭６１−３−２０＞日本
工業技術センター、Ｐ、１７２−１９２、及び本願出願
人が先に出願した■特願昭６２−１４６３２５号明細書
に記載されるものがあった。

以下、その構成を図を用いて説明する。

ディジタル信号伝送における誤り訂正符号化については
、前記文献■〜■に記載されており、その誤り訂正符号
化に用いられるガロア休演算器については前記文献■の
１９０頁に記載されている。

第２図は８ビツト用のシフトレジスタの構成ブロック図
であり、この図を参照しつつガロア体演算器の原理につ
いて説明する。

ガロア体は、有限体ともいわれ、有限個の元からなる体
をいい、その元の総数がｎ元の場合にＧＦ（ｎ）と略記
される。ここでは、ｎが２８（＝２５６）の場合、すな
わちＧＦ　（２８＞について述べる。

第２図の８ビツト用シフトレジスタは、８個の１ビツト
用のレジスタ１−１〜１−８と、３個の１ビット用排他
論理和回路２−１〜２−３とで構成されている。

レジスタ１−１〜１−８に順に論理“０，０゜０、Ｏ，
Ｏ，Ｏ，０，１”をセットした状態を初期状態とする。

レジスタ１−１〜１−８の内容を１−１の側を上位ビッ
ト、１−８の側を下位ビットとし、２進数とみなすと、
シフトレジスタの内部状態はＯ〜２５５までの数に対応
する。このように、シフトレジスタの内部状態を２進数
とみなしたものを、以後ガロア体のベクトル表現と呼ぶ
。

シフトレジスタを初期状態によりシフトさせる回路が１
以上、２５４以下であれば、そのシフトレジスタの内部
状態はベクトル表現の２〜２５５までと１対１で対応す
る。また、初期状態より２５５回のシフトを行うと、シ
フトレジスタの内容は初期状態と同一になる。つまり、
初期状態から０以上、２５４以下の回数だけシフトした
結果は、シフト回数と１対１に対応する。ここで、初期
状態により０回シフトした結果をα　と表現することに
し、以下これをガロア体の指数表現と呼ぶ。シフトレジ
スタの内容がすべてＯの場合も含めて、ガロア体ＧＦ　
（２８＞は次式のように表わせる。

ＧＦ（２８）　＝　（０，１、２，・・・、　２５５　
）・・・（１） ＧＦ（２８）　＝　（Ｚｅｒｏ、　ａＯ，ａ’　、　・
、　ａ２５４）・・・（２） 但し、２ｅｒｏ　；零 （１）式はベクトル表現によるものであり、（２）式は
指数表現によるものである。

ガロア体の中で次のような関係式が成立することが知ら
れている。

αｍ十αｎ＝αｎ十αｍ　　　　　　　　・・・（３）
α１・α０＝α１・α１　　　　　　　・・・（４）α
　・（α０＋α１）＝α１・α０＋α１・αｇ・・・（
５） ａ　ｎｌ　　、　　ａ　ｎ　　＋＝＝　ａ　（ｍａｎ）
ｍｏｄ２５５　　　　　　　　　　　　　、、、　（６
）αｎ＋　７ａｎ　＝ａ（ｍ−ｎ）ｍｏｄ２５５　　　
　　　、、、（７）ｌｅｒｏ　−ａｍ＝Ｚｅｒｏ　　　
　　　　　　　　−（８）（６）式、（７）式において
、ｍｏｄは除余（ｍｏｄｕｌｏ）すなわち排他論理和を
意味し、ｍｏｄｎはｎを法として合同であるという意味
である。

そして（６）式において（ｍａｎ）ｍｏｄ２５５は、（
ｍａｎ＞＞２５５の場合、例えば（ｍａｎ＞＝２５６の
ときは２５６−２５５＝１’　という数値になる。

また、加算はベクトル表現における排他論理和によって
算出される。

従来、この種の加算を行うガロア休演算器の加机１回路
としては、前記文献■に記載されるものがあり、その構
成例を第３図に示す。

この加算回路は、ｎを８ビツトにとり２°−１（＝２５
５）を法として２つの８ビツトデータＸｅとＹｅを加算
して８ビツトのデータＺｅ＠得る回路であり、８ビツト
用加算器１０と論理回路２０を備えている。

８ビツト用加輝器２０は、８ごットデータＸｅ。

Ｙｅをそれぞれ入力する入力端子Ａ、Ｂ、１ビットデー
タを入力する入力端子Ｃｉｎ、８ビットデータを出力す
る出力端子Ｓ、及びキャリーを出力する出力端子Ｃｏｕ
ｔを有している。論理回路２０は、加算器１０の出力端
子Ｓに接続された８人力のナントゲート（以下、ＮＡＮ
Ｄゲートという）２１と、加算器１０の出力端子Ｓ及び
ＮＡＮＤゲート２１の出力側に接続された８個のアント
ゲート（以下、ＡＮＤゲートという）２２−１〜２２−
８とで構成されている。

−このような加算回路の動作を説明する。

８ビツトのデータＸｅ、！：Ｙｅが加算器１０の各入力
端子Ａ、Ｂに供給されると、この加算器１０は８ビット
データｘｅ、’ｙ’ｅと入力端子Ｃｉｎに入力される１
ビツトデータの和を計算し、その加算結果における下位
８ビツトのデータを出力端子Ｓから出力してＮＡＮＤゲ
ート２１及びＡＮＤゲート２２−１〜２２−８に与える
。ＮＡＮＤゲート２１は、入力される８ビツトデータに
対して論理積をとった後にそれを反転してＡＮＤゲート
２２−１〜２２−８に与える。すると各ＡＮＤゲート２
２−１〜２２−８は、出力端子Ｓからの各ビットのデー
タとＮＡＮＤゲート２１から出力されるデータとの論理
積をとってその結果を８ビットデータ７−ｅとして出力
づる。

ここで、８ごットデータＸｅとＹｅの和がＯ〜２５４の
場合、加算器１０はデータＸｅとＹｅを単純加算した値
を出力し、その値がＡＮＤゲート２２−１〜２２−８を
通してそのまま８ビツトデータＺｅとして出力される。

８ビツトデータＸｅとＹｅの和が２５６〜５０．９の場
合、加算器１０は２つの８ビツトデータＸｅとＹｅを単
純加算した値から２５５を引いた値を出力し、その値が
ＡＮＤゲート２２−１〜２２−８を通してそのまま８ビ
ツトデータｚｅとして出力される。さらに、８ビツトデ
ータｘｅとＹｅの和が２５５の時には、ＮＡＮＤゲート
２１によってすべてのＡＮＤゲート２２−１〜２２−８
がオフ状態となり、出力データ７−ｅがＯとなる。

この加算回路では、１個の８ビツト用加算器１０と、１
個のＮＡＮＤゲート２１と、ｎ個のＡＮＤゲート２０と
で構成したので、回路素子数の減少と、それに伴なう回
路規模の小型化が可能になるという利点を有している。

（発明が解決しようとする問題点） しかしながら、上記構成の加算回路では、入力の８ビッ
トデータＸｅ、Ｙｅの値として、指数表現すなわち（２
）式におけるα０〜α２５４までの数が入力された場合
には正しく計算できるが、”１ｅｒｏはαのべき乗数で
表現不可能なために計Ｃン−ができない。そのため、２
個の被演算数のうちのいずれかにｚｅｒｏを含む演算は
、他の手段により演算を行わなければならないという問
題点があった。

本発明は、前記従来技術が持っていた問題点として、被
演算数にｚｅｒｏを含む場合には正しく計算ができない
点について解決した加算回路を提供するものである。

（問題点を解決するための手段） 本発明は前記問題点を解決するために、２つのｎビット
データ（但し、ｎは２以上）を加算してその加惇結果を
出力すると共に桁あふれ信号を自身の下位桁あふれ入力
信号として再入力するｎビット用の加算器と、この加算
器の出力の否定論理積を求めその否定論理積と前記加算
器の出力との各ビット毎の論理積を求めて２−１を法と
して前記２つのｎビットデータの和を出力する論理回路
とを備えた加算回路において、前記２つのｎビットデー
タの各論理積を求めその各論理積の論理和を求める第１
の論理回路と、この第１の論理回路の出力と前記論理回
路の、ｎビット出力との各ビット毎の論理和を求める第
２の論理回路とを、設けたものである。

（作　用） 本発明によれば、以上のように加算回路を構成したので
、第１および第２の論理回路は、２つのｎごットデータ
のうち少くとも１つのデータが２ｎ−１の値であれば、
論理回路の出力を無効にしてその２°−１の値を出力し
、そうでない場合には、論理回路の出力を有効にして２
−１を法として２つのｎビットデータの和を出力させる
。

すなわち、入力及び出力のｎビットデータは例えばガロ
ア体ＧＦ（２＞の指数表現を使用し、７ｅｒｎＬｔ？　
　−１に割り当てる。そして、例えばｎ＝８　（ＧＦ　
（２８））の場合には、８ビツトで表現可能なＯ〜２５
５の数のうち、０〜２５４までをα０〜α２５４に割り
当てて加算器及び論理回路で計算させ、２５５をｚｅｒ
ｏに割り当てて第１および第２の論理回路から出力させ
る。これにより、ｚｅｒｏを含む演算も正確に行える。

従つ°て、前記問題点を除去できるのである。

（実施例） 第１図は本発明の実施例を示すガロア休演算器における
加算回路の構成ブロック図である。

この加算回路は、ｎを８ビツトにとり、２つの８ビット
データＸｅ、ＹｅをそのＸｅもしくはＹｅが２°−１（
＝２５５＞でない時には、２５５を法として加算し、ｘ
ｅかＹｅの少くとも一方が２５５の場合には２５５を８
ビツトのデータｚｅとして得る回路であり、第３図と同
様の８ビツト用加算器３０及び論理回路４０に、第１お
よび第２の論理回路５０．６０を付加した構成である。

ここで、８ビツト用加算器３０は、８ビットデータＸｅ
、Ｙｅをそれぞれ入力する入力端子Ａ。

Ｂ、１ビツトデータを入力する入力端子Ｃｉ’ｎ、８ビ
ツトデータを出力する出力端子Ｓ、及びキャリーを出力
する出力端子ｃｏｕｔを備え、入力端子Ａ、Ｂから入力
される８ビツトデータＸｅ。

Ｙｅと入力端子Ｃｉｎに入力される１ビットデータの和
を計算し、その加算結果における下位８ビツトのデータ
を出力端子Ｓから出力し、ざらにキャリーを出力端子Ｃ
ｏｕｔから出力して自己の入力端子Ｃｉｎへ再入力する
機能を有している。この加算器３０の出力端子Ｓに接続
される論理回路４０は、出力端子Ｓからの８ビツトデー
タの否定論理積をとる８人力のＮＡＮＤゲート４１と、
出力端子Ｓからの各ビットのデータとＮＡＮＤゲート４
１から出力されるデータとの論理積をとる８個のＡＮＤ
ゲート４２−１〜４２−８より構成されている。

また、第１．第２の論理回路５０．６０のうち、第１の
論理回路５０は、２つの８ビットデータＸｅ、Ｙｅの各
論理積をとる２個の８人力ＡＮＤゲート５１−１．５１
−２と、この２つのＡＮＤゲート５１−１．５１−２の
出力の論理和をとるオアゲート（以下、ＯＲゲートとい
う）５２とで構成されている。ざらに、この第１の論理
回路５０の出力側に接続される第２の論理回路６０は、
ＯＲゲート５２の出力と８個のＡＮＤゲート４−２−１
〜４２−８の出力との各論理和をとりその結果を８ビッ
トデータ７−ｅとして出力する８個の２人力ＯＲゲート
６１−１〜６１−８で構成されている。

以上のように構成される加算回路の動作を、演算対象と
なる２個の８ビットデータＸｅ、　’ｙ’ｅについて、
（１）Ｘｅ≠１ｅｒｏかつＹｅ≠Ｚｅｒｏ　（Ｚｅｒｏ
三２５５＞の場合と、（２）Ｘｅ＝７−ｅｒａあるいは
Ｙｅ＝ＺｅｒＯの場合とに分けて説明する。

（１）Ｘｅ：＃Ｚｅ　ｒｏか”）Ｙｅｆ−ＺｅｒＯの場
合（Ｚｅｒｏ＝２５５＞ この場合、２個の８人力ＡＮＤゲート５１−１゜５１−
２の入力データＸｅ、Ｙｅは両方共Ｏ〜２５４の値であ
り、そのＡＮＤゲート５１−１゜５１−２の出力が両方
共Ｏとなる。そのため、ＯＲゲート５２の出力はＯとな
り、ＡＮＤゲート４２−１〜４２−８の出力データがぞ
のままＯＲゲート６１−１〜６１−８を介して出力され
ることに、なる。

ここで、加算器３０．ＮＡＮＤゲート４１、及びＡＮＤ
ゲート４２−１〜４２−８は、次のように動作する。

加算器３０の各入力端子Ａ、Ｂへそれぞれ供給される８
ビツトのデータＸｅとＹｅの和が０以上２５４以下の場
合、加算器３０における出力端子Ｃｏｕｔ上の直前のキ
ャリーがＯあるいは１のいずれのときでも、その加算器
３０の演算結果は２５５以下となる。そのため、加算器
３０の出力端子Ｃｏｕｔ上のキャリーはＯにクリアされ
、加算結果（Ｘｅ＋Ｙｅ）が出力端子Ｓから出力される
。このとき、出力端子Ｓの出力データはＯから２５４ま
での値でおるので、ＮＡＮＤゲート４１の出力が１とな
る。従ってＡＮＤゲート４２−１〜４２−８からはＯＲ
ゲート６１−１〜６１−８を介して（Ｘｅ＋Ｙｅ）のデ
ータ７−ｅが出力される。

また、加算器３０への入力データｘｅとＹｅの和が２５
６以上５０８以下の場合、出力端子Ｃ０ｕｔ上の直前の
キャリーがＯあるいは１のいず−れのときでも、加算器
３０の演鈴結果は２５６以上となるので、出力端子Ｃｏ
ｕｔ上のキャリーが１にセットされ、出力端子Ｓから（
ｘｅ十Ｙｅ＋１＞−２５６、つまり（Ｘｅ＋ｙｅ−２５
５）の値が出力される。このとぎ出力端子Ｓの出力デー
タは１から２５３までの値であるので、ＮＡＮＤゲート
４１の出力が１となる。従ってＡＮＤゲート４２−１〜
４２−８からはＯＲゲート６１−１〜６１−８を介して
０（ｅ＋ｙｅ−２５５）のデータｚｅが出力される。

ざらに、加算器３０への入力データＸｅとＹｅの和が２
５５のときには、出力端子Ｃｏｕｔ上の直前のキャリー
の状態により、次の２通りの場合が考えられる。

第１に、出力端子Ｃｏｕｔ上の直前のキャリーがＯの場
合、加算器３０の演算結果は２５５となり、出力端子Ｓ
のデータが２５５、出力端子Ｃ０ｕｔのキャリーがＯと
なる状態で安定する。

このとき、ＮＡＮＤゲート４１の出力はＯとなるので、
８個のＡＮＤゲート４２−１〜４２−８の出力はすべて
Ｏとなり、それによってＯＲゲート６１−１〜６１−８
を介して出力される出力データＺｅがＯとなる。

第２に、出力端子Ｃ０ｕｔ上の直前のキャリーが１の場
合、加算器３０の演算結果は２５６となるので、出力端
子ＳがＯ１出力端子Ｃｏｕｔ上のキャリーが１となる状
態で安定する。このとき、８個のＡＮＤゲート４２−１
〜４２−８の出力はすへてＯとなり、それによって出力
データ７−ｅがＯとなる。

このように、第１と第２の場合において、出力端子Ｃ０
１１↑上のキャリーの状態にかかわらず、入力データＸ
ｅとＹｅの和が２５５のときには、出力データ７ｅとし
てＯが保証される。

従ってこの（１）の場合、ＡＮＤゲート４２−１〜４２
−８から、入力データ＞（ｅとＹｅの２５５を法として
加算した８ビット出力データ７−ｅがそのままＯＲゲー
ト６１−１〜６１−８を通して出力されることになる。

（２）Ｘｅ＝Ｚｅｒｏあるいはｙｅ＝ｚｅｒｏの場査 ２個の８人力ＡＮＤゲート５１−１．５１−２の少くと
も一方の入力データは、２５５の値であるので、そのＡ
ＮＤゲート５１−１または５１−２のいずれか一方の出
力が１となり、ＯＲゲート５２の出力が１となる。これ
により、８個のＯＲゲート６１−１〜６１−８の出力が
すべて１になるため、加締回路の８ビツト出力データＺ
ｅは２５５、すなわちＺｅｒｏになる。

従って、従来のように他の手段を併用することなく、ｚ
ｅｒｏを含むガロア体の演算を正確に行うことができる
。

なお、本発明は図示の実施例に限定されず、種々の変形
が可能である。例えば、上記実施例では、データ数ｎを
８ビツト、法２−１を２５５として説明したが、ｎは２
のべぎ乗数であれば、他の数でもよく、それに応じて加
算器３０、及び論理回路４０，５０．６０のビット容量
を変えればよい。また、これらの論理回路４０，５０．
６０は図示以外のゲート回路等で構成することもできる
。

ざらに、上記実施例の加算回路は、ガロア体演算器以外
のものにも適用可能である。

（発明の効果） 以上詳細に説明したように、本発明によれば、第１と第
２の論理回路を設けたので、２つのｎビットデータのう
ち少くとも１つのデータが２８−１の値（Ｚｅｒｏ）で
あれば、その２°−１の値が出力され、そうでない場合
には２−１を法として２つのｎビットデータの和が出力
される。従って、従来のように他の手段を併用プること
なく、ｚｅｒｏを含むガロア体の演算等を正確に行うこ
とができる。

【図面の簡単な説明】

第′１図は本発明の実施例を示すガロア体演算器にお（
プる加算回路の構成ブロック図、第２図はガロア休演算
器の原理を説明するだめの８ビツト用レフトレジスタの
構成ブロック図、第３図は従来のガロア休演算器におけ
る加算回路の構成ブロック図である。 −３０・・・・・・加算器、４０・・・・・・論理回路
、４１・・・・・・ＮＡＮＤゲート、４２−１〜４２−
８・・・・・・ＡＮＤゲート、５０．６０・・・・・・
第１．第２の論理回路、５１−１．５１−２・・・・・
・ＡＮＤゲート、５２゜６１−１〜６１−８・・・・・
・ＯＲゲート。 出願人代理人　　柿　　本　　恭　　成木発明のＤ日算
回路 第１図 ８ビツト用シフトレジスタ 第２図

Claims (1)

【特許請求の範囲】
1. １．２つのｎビットデータ（但し、ｎは２以上）を加算
   してその加算結果を出力すると共に桁あふれ信号を自身
   の下位桁あふれ入力信号として再入力するｎビット用の
   加算器と、この加算器の出力の否定論理積を求めその否
   定論理積と前記加算器の出力との各ビット毎の論理積を
   求めて２＾ｎ−１を法として前記２つのｎビットデータ
   の和を出力する論理回路とを備えた加算回路において、
   前記２つのｎビットデータの各論理積を求めその各論理
   積の論理和を求める第１の論理回路と、この第１の論理
   回路の出力と前記論理回路のｎビット出力との各ビット
   毎の論理和を求める第２の論理回路とを、 設けたことを特徴とする加算回路。 ２、前記第１の論理回路は、前記２つのｎビットデータ
   の各論理積を求める２つのアンドゲートと、この２つの
   アンドゲートの出力の論理和を求める第１のオアゲート
   とで構成し、 前記第２の論理回路は、前記第１のオアゲートの出力と
   前記論理回路のｎビット出力との各ビット毎の論理和を
   求めるｎ個の第２のオアゲートで構成した特許請求の範
   囲第１項記載の加算回路。 ３、前記ｎビットは８ビットである特許請求の範囲第１
   項記載の加算回路。