JP4595055B2 - ガロア体のα乗算回路および演算回路 - Google Patents

Description

本発明はガロア体のα乗算回路および演算回路に関するものであり、特に複数の演算機能を実現可能なガロア体のα乗算回路および演算回路に関するものである。

従来、デジタル通信装置等に使用されるリードソロモン復号回路等のデジタル信号処理回路を実現するためには、ガロア体上の乗算回路等が必要である。下記の特許文献１には、ガロア体上の乗算回路の例が開示されている。このような回路を実現する手段としては、プログラマブルな論理デバイスであるＦＰＧＡを使用することが考えられる。しかし、ＦＰＧＡは汎用性を目的としているために回路に対して配線の負荷が重く演算速度が遅いので、超高速処理を必要とする分野においては使用できないという問題点があった。そこで超高速処理を必要とする分野においては従来は必要な機能毎にハードウェア回路を設計してＬＳＩ化していた。
特開平１１−９６０３０号公報

上記したような従来の個別のハードウェア回路を使用して例えばリードソロモン復号回路を実現するためには、ガロア体乗算回路の他にα^n（^はべき乗を表す。以下同じ、nは整数）演算や逆元演算等の機能も必要となり、リードソロモン復号回路の回路規模が大きくなると共に設計に手間がかかってしまうという問題点があった。
本発明の目的は、前記のような従来技術の問題点を解決し、複数の演算機能を実現可能なガロア体のα乗算回路および演算回路を提供することにある。

本発明のローテーション機能を有するガロア体のα乗算回路は、複数ビットの並列入力端子、複数ビットの並列出力端子および制御信号入力端子を有し、前記制御信号に関わらず、最下位ビットの前記出力端子には最上位ビットの前記入力端子の信号が出力され、最下位ビット以外の前記出力端子には、当該ビット位置と対応する前記制御信号と最上位ビット入力端子の信号との論理積信号と、当該ビット位置よりも１つ下位のビット位置の前記入力端子の信号との排他的論理和信号が出力されることをことを主要な特徴とする。
また、前記したローテーション機能を有するガロア体のα乗算回路において、前記制御信号入力端子には、所望の生成多項式に対応する制御信号が入力される点にも特徴がある。

また、前記したローテーション機能を有するガロア体のα乗算回路において、ビット幅がビット０からビット７までの８ビットであり、前記制御信号に関わらず、ビット０出力端子にはビット７入力端子の信号が出力され、ビット１出力端子にはビット０入力端子の信号が出力され、ビット５出力端子にはビット４入力端子の信号が出力され、ビット６出力端子にはビット５入力端子の信号が出力され、ビット７出力端子にはビット６入力端子の信号が出力され、ビット１、５、６、７以外の前記出力端子には、当該ビット位置と対応する前記制御信号とビット７入力端子の信号との論理積信号と、当該ビット位置よりも１つ下位のビット位置の前記入力端子の信号との排他的論理和信号が出力される点にも特徴がある。

本発明のガロア体の演算回路は、前段のα乗算回路からの出力信号を入力し、制御信号に基づいてα乗算または左１ビットローテーション処理を行うガロア体のα乗算回路と、制御信号に基づいて入力信号の１つのビット位置の信号およびレジスタ回路からの出力信号のいずれかを選択して出力するセレクタ回路と、前記α乗算回路の出力信号と前記セレクタ回路の出力信号とを乗算するＡＮＤゲートと、前記ＡＮＤゲートの出力および前段のＥＯＲゲートの出力とを加算するＥＯＲゲートと、前記セレクタ回路の一方の入力に接続されたレジスタ回路とからなる演算回路を複数段縦続接続したことを主要な特徴とする。

また、前記したガロア体の演算回路において、前記α乗算回路は上記したローテーション機能を有するガロア体のα乗算回路である点にも特徴がある。
また、前記したガロア体の演算回路において、前記α乗算回路、前記セレクタ回路に制御信号を印加することにより、演算回路を任意の生成多項式に対応するベクトル乗算回路あるいは任意のべき乗に対応する指数演算回路として機能させる点にも特徴がある。
また、前記したガロア体の演算回路において、更に、前記レジスタ回路の出力信号が一方の入力端子に接続され、出力が前段の前記レジスタ回路の入力端子に接続された第２のＡＮＤゲート回路を備えた点にも特徴がある。

本発明の演算回路のセルを設計すれば、複数種類の機能回路としてこのセルを貼り付け、配線するだけで設計が完了するので、設計が容易となり、期間も短縮できるという効果がある。
また、本発明のガロア体上の演算回路は、任意の生成多項式に対応するベクトル乗算回路あるいは任意のべき乗に対応する指数演算回路など、複数の演算機能を実現可能である。また、機能を動的に切り替えることにより、同一の回路で例えばリードソロモン復号回路を実現するために必要な複数の演算機能を実現可能であるので、回路規模を減少させることができるという効果がある。

以下に、図面を参照して本発明の実施の形態を詳細に説明する。

実施例としては、リードソロモン復号回路を構成するために必要な下記の演算回路を実現可能な演算回路について説明する。リードソロモン復号回路を構成するためには、以下のようなガロア体の演算回路が必要である。
（１）バーレカンプ−マッシィ（Berlekamp-Massey）アルゴリズムで使用するガロア体乗算回路と逆元演算
（２）逆元演算で使用する入力データの１６乗演算回路
（３）シンドローム演算とチェン探索で使用するα^n（n=0,1…7）乗算回路

以下、本発明の第１実施例のガロア体上の演算回路について説明する。図１は、本発明のガロア体（ＧＦ（256））上の演算回路の構成を示すブロック図である。演算回路は、左ローテーション機能を有するα乗算回路１１、セレクタ回路１２、法（モジュロ）２の乗算を行うためのＡＮＤゲート１３、法（モジュロ）２での加算を行うためのＥＯＲゲート１４、レジスタ回路１５、シフトレジスタ動作を制御するＡＮＤゲート１６からなる単位回路を図示するように８段縦続接続した回路である。なお、α乗算回路１１は第１段（図１の最上段）目には存在せず、第２段目以降に設けられている。

一方の信号入力端子から入力された８ビットパラレル信号ａは第１段目のＡＮＤゲート１３に入力されると共に、第２段目のα乗算回路１１（詳細は後述する）にも入力される。ＧＦ（256）の場合、入力信号は8ビットなので、ＡＮＤゲート１３は８個からなる。８個のＡＮＤゲート回路１３の一方の入力端子には入力信号ａが入力され、他方の入力端子にはセレクタ回路１２の８ビット出力信号が入力される。

セレクタ回路１２は、セレクタ制御信号mat_mal_setが１である場合には他方の信号入力端子から入力された８ビットパラレル信号ｂの内の１ビット（例えばｂ0）を全てのビットに出力し、セレクタ制御信号mat_mal_setが０である場合にはレジスタ１５の８ビット出力信号を出力する。

ＧＦ（256）の場合、入力信号は8ビットなので、ＥＯＲゲート１４は８個からなる。第１段の８個のＥＯＲゲート回路の一方の入力端子には入力信号ｓが入力され、他方の入力端子にはＡＮＤゲート１３の８ビット出力信号が入力される。そして、ＥＯＲゲート１４の出力は次段のＥＯＲゲートに入力される。α乗算回路１１の出力はＡＮＤゲート１３に入力されると共に、次段のα乗算回路１１にも入力される。

レジスタ回路１５は８ビットのパラレル入出力レジスタである。そして各レジスタ回路の８ビットパラレル出力信号はシフトレジスタ動作を制御するＡＮＤゲート１６を介して前段のレジスタ回路に入力されている。従って、制御信号intを１にすることにより、複数のレジスタ回路１５を８ビットパラレル信号単位でシフトするシフトレジスタとして機能させることができる。

図２は、本発明のガロア体のα乗算回路１１の構成を示す回路図である。図２（ａ）に示すα乗算回路１１は、複数の生成多項式に対応できるように、入力信号をそのまま出力する１個のバッファ回路３０、７個のＡＮＤゲート回路３１および７個のＥＯＲゲート回路３２が図示されているように接続されている。従って、制御信号ctl_nが全て０の場合には左１ビットローテーション回路として機能し、それ以外の場合は制御信号ctl_nの状態に基づいた任意の生成多項式に対するガロア体のα乗算回路として機能する。

図２（ｂ）の回路は生成多項式がx^8+x^4+x^3+x^2+1である場合のみに特化したものである。生成多項式を上記した式に特化した場合には、図２（ｂ）に示すように、入力信号をそのまま出力する５個のバッファ回路３０、３個のＡＮＤゲート回路３１および３個のＥＯＲゲート回路３２が図示されているように接続された回路となる。従って、制御信号ctl_nが０の場合には左１ビットローテーション回路として機能し、制御信号ctl_nが１の場合には上記生成多項式に対するガロア体のα乗算回路として機能する。

即ち、制御信号ctl_nが０の場合には出力ａo[0]＝ａ[7]、ａo[1]＝ａ[0]、ａo[2]＝ａ[1]、ａo[3]＝ａ[2]、ａo[4]＝ａ[3]、ａo[5]＝ａ[4]、ａo[6]＝ａ[5]、ａo[7]＝ａ[6]となる。また、制御信号ctl_nが１の場合には出力ａo[0]＝ａ[7]、ａo[1]＝ａ[0]、ａo[2]＝ａ[1]＋ａ[7]、ａo[3]＝ａ[2]＋ａ[7]、ａo[4]＝ａ[3]＋ａ[7]、ａo[5]＝ａ[4]、ａo[6]＝ａ[5]、ａo[7]＝ａ[6]となる。この出力信号は、生成多項式x^8+x^4+x^3+x^2+1に対するα乗算結果である。なお「＋」は法２での加算、即ち排他的論理和である。

ここで、α乗算回路について説明する。ガロア体ＧＦ（２５６）の原始元をα、生成多項式Ｆ（ｘ）を、Ｆ（ｘ）＝Ｘ^8＋Ｘ^4＋Ｘ^3＋Ｘ^2＋１（式１）とする。

また、ＧＦ（２５６）の任意の元ａを次式で表す。
ａ＝a7α^7＋a6α^6＋a5α^5＋a4α^4＋a3α^3＋a2α^2＋a1α＋a0（式２）
上記式２にαを乗算すると、
ａ×α＝a7α^8＋a6α^7＋a5α^6＋a4α^5＋a3α^4＋a2α^3＋a1α^2＋a0α（式３）
となる。一方、αは原始元であるからＦ（α）＝０であり、結果として、
α^8＝α^4＋α^3＋α^2＋１（式４）
となる。

式４を式３に代入すれば、
ａ×α＝a6α^7＋a5α^6＋a4α^5＋(a3+a7)α^4＋(a2+a7)α^3＋(a1+a7)α^2＋a0α＋a7（式５）
となる。図２（ｂ）に示されたα乗算回路１１において、制御信号ctl_nが１の場合には、上記式２に示す係数a0〜a7を入力すると、出力ａoとして上記式５の係数が得られる。
任意の生成多項式についても、上記したものと同様の方法にて上記式（５）に相当する式が得られ、この式の係数を制御信号ctl_n[0..6]として設定することにより、任意の生成多項式に対応するα乗算回路が得られる。

図４は、本発明の演算回路を使用してベクトル乗算回路を構成した場合のブロック図である。ここで、まずベクトル乗算回路について説明する。ガロア体ＧＦ（２５６）の原始元をαとする。また、ＧＦ（２５６）の任意の元ａ、ｂを次式で表す。

ａ＝a7α^7＋a6α^6＋a5α^5＋a4α^4＋a3α^3＋a2α^2＋a1α＋a0（式６）
ｂ＝b7α^7＋b6α^6＋b5α^5＋b4α^4＋b3α^3＋b2α^2＋b1α＋b0（式７）

この時、ａとｂの積は、
ａ×ｂ＝ａ×（b7α^7＋b6α^6＋b5α^5＋b4α^4＋b3α^3＋b2α^2＋b1α＋b0）
＝b7ａ×α^7＋b6ａ×α^6＋b5ａ×α^5＋b4ａ×α^4＋b3ａ×α^3＋b2ａ×α^2＋b1ａ×α＋b0ａ（式８）
となる。

図４の回路は、上記式８の計算を実行するための回路であり、図１の回路において、図２（ｂ）のα乗算回路を使用し、制御信号ctl_nを１、セレクタ制御信号mat_mal_setを１にした場合の回路を示している。

入力信号ａはＡＮＤゲート１３に入力されると共にα乗算回路１１にも入力され、各段のα乗算回路の出力は各段のＡＮＤゲート１３および次段のα乗算回路１１に入力される。従って、各段のＡＮＤゲート１３の一方の入力にはａ×α^n（ｎ=0,…7）が入力される。また、各段のＡＮＤゲート１３の他方の入力にはｂn（ｎ=0,…7）が入力される。そして、各ＡＮＤゲート１３の出力はＥＯＲゲート１４によって全て加算され、出力信号s_oにはａとｂの積が出力される。

図４の構成においては、ベクトル乗算回路としてはレジスタ回路１５は必要ないので使用されない。そこで、制御信号intを１とすると、全てのレジスタが各ビット毎にそれぞれ直列に接続され、シフトレジスタとして機能させることができる。従って、ベクトル乗算の演算中にデータ入力端子m_iから各レジスタに設定する８ビットデータを順次入力してシフトさせることにより、全てのレジスタ１５に所望の値を設定、保存することができる。この機能を利用して、例えば、乗算演算結果をこのシフトレジスタに入力することで、乗算演算結果の一時的な保存が可能となる。

図５は、本発明の演算回路を使用して指数乗算回路を構成した場合のブロック図である。指数演算回路、特に入力データの１６乗演算はＧＦ（256）の元の逆元算出のときに必要となる演算回路である。

ＧＦ（２５６）の原始元をα、ＧＦ（２５６）の任意の元ａを次式で表す。
ａ＝a7α^7＋a6α^6＋a5α^5＋a4α^4＋a3α^3＋a2α^2＋a1α＋a0（式９）
ａnはＧＦ（２）の元であるので、ａn^2＝ａnであり、また、２×ａmａn＝０となる。

従って、ａ^2は、
ａ^2＝a7α^14＋a6α^12＋a5α^10＋a4α^8＋a3α^6＋a2α^4＋a1α^2＋a0（式１０）
となる。同様にしてａ^16は、
ａ^16＝a7α^112＋a6α^96＋a5α^80＋a4α^64＋a3α^48＋a2α^32＋a1α^16＋a0（式１０）
となる。これを行列で表すと、下記の式１１となる。

図５の回路は、上記式１１の計算を実行するための回路であり、図１の回路において、制御信号ctl_nを０、セレクタ制御信号mat_mal_setを０、制御信号intを０にした場合の回路を示している。なお、各レジスタ１５には予めマスクデータＭ0〜Ｍ7をセットしておく。図５の回路において式１１の演算を行うためには、係数αに相当する行列からレジスタ１５にセットするマスクデータを生成する必要がある。

図６は、マスクデータの生成方法を示す説明図である。上記式１１の係数αに相当する行列を図６（ａ）に示す。対角線上の数値を点線で囲ってある。この行列の各行（１〜８行）を（行数−１）ビットだけ左ローテートすると図６（ｂ）の行列が得られる。（ａ）において点線で囲った数値が縦１列に整列している。この行列の各列のデータをマスクデータＭ0〜Ｍ7とする。そして、図５に示されているように、レジスタ７〜レジスタ０にＭ0〜Ｍ7をセットする。

入力データａは直列に接続された左ローテート回路１１によって順次１ビットづつ左ローテートされ、それぞれＡＮＤゲート１３（ＡＮＤゲート回路）の一方に入力される。ＡＮＤゲート１３の他方の入力にはマスクデータＭ0〜Ｍ7のいずれかが入力され、論理積が取られる。即ちマスクデータが１のビットに対応するデータのみが出力される。ＡＮＤゲート１３の出力はＥＯＲゲート１４によってビット位置毎に全て加算（ＥＯＲ）され、出力s_oにはａ^16が得られる。

シンドローム演算とチェン探索で使用するα^n（n=0,1…7）乗算も、入力データａの線形変換によって求めることができる。従って、前記した行列演算と同じ方法によって算出可能である。

図３は、本発明のガロア体上の演算回路を使用した逆元演算回路の構成を示すブロック図である。逆元演算を変換テーブルを用いて行った場合、ＧＦ（２５６）の元の個数である２５５通りのテーブルを用意する必要がある。この変換テーブルの数を減らすために、逆元演算回路を図３に示す構成とする。

入力データａは前述した指数演算回路４０により１６乗され、更にガロア体乗算回路４１によって入力データａと乗算を行い、ａ^17を生成する。このａ^17の逆元ａ^-17を変換テーブル４２を参照して求める。最後に先の演算結果ａ^16との乗算を行い、ａの逆元であるａ^-1を求める。

実施例におけるリードソロモン符号の生成多項式Ｆ（ｘ）＝Ｘ^8＋Ｘ^4＋Ｘ^3＋Ｘ^2＋１（式１）で、位数は２５５＝１５×１７である。従って入力信号の元ａ^n（n=0,1,…,255）の１７乗、（ａ^n）^17＝ａ^17n(mod255)の元の個数は１５個となり、変換テーブルは１５種類で済む。

以上、実施例を開示したが、下記に示すような変形例も考えられる。実施例においてはビット数が８ビットの信号に対応する実施例を開示したが、α乗算回路１１として、図２（ａ）のＡＮＤゲートとＥＯＲゲートのセットをビット数−１だけ用意し、図１の演算回路としてビット数分の単位回路を縦続接続すれば、本発明は任意のビット数に対応可能である。

本発明のガロア体上の演算回路の構成を示すブロック図である。 本発明のα乗算回路１１の構成を示す回路図である。 本発明のガロア体上の演算回路を使用した逆元演算回路の構成を示すブロック図である。 本発明の演算回路を使用してベクトル乗算回路を構成した場合のブロック図である。 本発明の演算回路を使用して指数乗算回路を構成した場合のブロック図である。 マスクデータの生成方法を示す説明図である。

符号の説明

１１…α乗算回路
１２…セレクタ回路
１３…ＡＮＤゲート
１４…ＥＯＲゲート
１５…レジスタ回路
１６…ＡＮＤゲート

Claims (7)

1. 複数ビットの並列入力端子、複数ビットの並列出力端子および制御信号入力端子を有し、
   前記制御信号に関わらず、最下位ビットの前記出力端子には最上位ビットの前記入力端子の信号が出力され、
   最下位ビット以外の前記出力端子には、当該ビット位置と対応する前記制御信号と最上位ビット入力端子の信号との論理積信号と、当該ビット位置よりも１つ下位のビット位置の前記入力端子の信号との排他的論理和信号が出力される
   ことを特徴とするローテーション機能を有するガロア体のα乗算回路。
2. 更に、前記制御信号入力端子には、所望の生成多項式に対応する制御信号が入力されることを特徴とする請求項１に記載のローテーション機能を有するガロア体のα乗算回路。
3. ビット幅がビット０からビット７までの８ビットであり、
   前記制御信号に関わらず、ビット０出力端子にはビット７入力端子の信号が出力され、
   ビット１出力端子にはビット０入力端子の信号が出力され、
   ビット５出力端子にはビット４入力端子の信号が出力され、
   ビット６出力端子にはビット５入力端子の信号が出力され、
   ビット７出力端子にはビット６入力端子の信号が出力され、
   ビット１、５、６、７以外の前記出力端子には、当該ビット位置と対応する前記制御信号とビット７入力端子の信号との論理積信号と、当該ビット位置よりも１つ下位のビット位置の前記入力端子の信号との排他的論理和信号が出力される
   ことを特徴とする請求項１に記載のローテーション機能を有するガロア体のα乗算回路。
4. 前段のα乗算回路からの出力信号を入力し、制御信号に基づいてα乗算または左１ビットローテーション処理を行うガロア体のα乗算回路と、
   制御信号に基づいて第２の入力信号の１つのビット位置の信号およびレジスタ回路からの出力信号のいずれかを選択して出力するセレクタ回路と、
   前記α乗算回路の出力信号と前記セレクタ回路の出力信号とを乗算するＡＮＤゲートと、
   前記ＡＮＤゲートの出力および前段のＥＯＲゲートの出力とを加算するＥＯＲゲートと、
   前記セレクタ回路の一方の入力に接続されたレジスタ回路と
   からなる単位回路を複数段縦続接続したものであり、
   第１段目の前記単位回路のみは前記α乗算回路を備えず、前記α乗算回路の出力信号の代わりに第１の入力信号が前記ＡＮＤゲートに入力されると共に第２段目の前記α乗算回路に出力され、かつ第１段目の前記単位回路のＥＯＲゲートには第３の入力信号が入力される
   ことを特徴とするガロア体の演算回路。
5. 前記α乗算回路は請求項１乃至３のいずれかに記載したα乗算回路であることを特徴とする請求項４に記載のガロア体の演算回路。
6. 前記α乗算回路、前記セレクタ回路に制御信号を印加することにより、演算回路を任意の生成多項式に対応するベクトル乗算回路あるいは任意のべき乗に対応する指数演算回路として機能させることを特徴とする請求項４に記載のガロア体の演算回路。
7. 更に、前記レジスタ回路の出力信号が一方の入力端子に接続され、出力が前段の前記レジスタ回路の入力端子に接続された第２のＡＮＤゲート回路を備えたことを特徴とする請求項４に記載のガロア体の演算回路。

Images