JPH0243218B2

JPH0243218B2 -

Info

Publication number: JPH0243218B2
Application number: JP58172346A
Authority: JP
Priority date: 1982-12-30
Filing date: 1983-09-20
Publication date: 1990-09-27
Also published as: US4538240A; EP0113032A2; EP0113032B1; JPS59125437A; DE3377389D1; EP0113032A3

Description

【発明の詳細な説明】〔技術分野〕本発明は、デイジタル計算機において「ハツシ
ユ」演算を行なうハードウエア装置に関する。

〔背景技術〕

ハツシユ関数の基本的な目的は、未知のそして
おそらく歪んだ分布の数値をより一様な分布の、
しばしばより小さな範囲内の数値に変換する事で
ある。ハツシユ関数の１つの応用は連想記憶の分
野にある。そこでは人物の名前又は口座番号等の
識別子がハツシユ関数によつて計算機のメモリの
アドレスに変換される。このアドレスは、その識
別子に関係するデータを探索するための開始点と
して用いられる。連想記憶が効率的に働くために
は、例え識別子が高度の相関を有する時でも、ハ
ツシユ関数によつて与えられるアドレスが可能な
アドレス上に比較的均一に拡がる事が重要であ
る。ハツシユ関数には、オペレーテイング・シス
テム、コンパイラ、インタープリタ、データ・ベ
ース管理、暗号方式、単語綴り検査、誤り訂正検
出方式等の他の多くの用途が存在する。

ハツシユ関数の上記の用途に加えて、もう１つ
の非常に重要な用途は、主記憶アドレスを含むハ
ツシユ・インデツクス表によつて、仮想アドレス
を主記憶の実アドレスに効率的に変換する事に関
するものである。ハツシユ関数は、データ処理シ
ステム中の不均一な分布の仮想アドレスから一様
な分布のハツシユ・インデツクス表のエントリ・
アドレスを生成するために与えられる。但し、ハ
ツシユ・インデツクス表の大きさは可変であり、
主記憶の大きさに基づいている。もし、適当なハ
ツシユ関数が選ばれるならば、ハツシユ・インデ
ツクス表は最小限の大きさに保たれ、非常に効率
的に使用されるであろう。

ハツシユ関数は普通、ソフトウエア（即ち計算
機プログラム）で実現されるが、本発明によれば
ハツシユ演算を実行する非常に用途の広い回路が
提供される。ハツシングを実行するハードウエア
を製作する２つの重要な利点が存在する。第１に
ハツシユ演算が相当スピード・アツプできる。第
２に非常に巧妙なハツシング手続即ちアルゴリズ
ムを経済的に使用できる。

ハツシングをハードウエアで実行する事の潜在
的欠点は、選択された特定の関数は特定のデータ
の集合に対してはうまく働かない可能性がある事
である。

即ちハツシユすべき目的物が特定の分布を有す
る時、できの悪い分布のハツシユ出力が生じるこ
とである。従つて、多くの従来技術のシステムで
は、ハードウエア又は固定式のハツシングは入力
データが多少は既知の固定された特性を有する場
合にのみ用いられてきた。逆により精巧なハツシ
ングが必要な時は、より複雑で時間のかかるハツ
シング・アルゴリズムが、ソフトウエアの形で実
施されてきた。その場合ハツシング演算の実行に
必要な時間は大幅に増加する。

前述のように、メモリ・アドレスを生成する目
的でハツシング演算を行なう事は従来周知であ
る。同様にガロア体の乗算も周知の数学的手続き
である。下記の文献はその代表的な先行技術であ
る。

米国特許第4215402号は、あるアドレス指定動
作が種々の型のハツシング動作を経て行なわれる
大規模な計算機メモリ・システムを開示してい
る。しかしながら、ハツシングを行なうのにガロ
ア体の乗算を用いる事は、なされていない。

米国特許第4162480号はガロア体計算機を開示
している。しかしながらこの文献は本発明の回路
にいかなる類似性を有する回路構造も開示してい
ない。またこの文献は、ハツシユ定数の種々のシ
フトの予備計算と組み合せた別個のローデイング
動作は開示していない。

米国特許第4037093号及び同第3805037号は共に
特殊なガロア体回路を開示しているが、それらは
ハツシング動作に関係もなければ、又本発明と類
似した回路構成を開示しているわけでもない。

〔発明の開示〕

本発明の目的は、理論的限界に近い優秀な結果
を与え且つ多くの応用に関してソフトウエアによ
つては実用上実現不可能な非常に効率的なハツシ
ユ手続のハードウエア的実現を提供する事であ
る。

本発明の１態様によれば、ハツシユ定数を変化
させる事によつて容易に変更可能なハツシユ機構
が提供される。従つて大幅に異なつた分布特性を
有する数（ハツシユすべき対象）の入力ストリー
ムのために非常に小さな遅延でシステムを調整し
て回路の性能を大幅に変更する事ができる。

また本発明の１態様によれば、大規模集積回路
の形に容易に実現でき且つ非常に小さな遅延で動
作するハツシング回路が提供される。

本発明の目的は、Ｎビツトのハツシユ定数の制
御の下でハツシユすべきＮビツトの対象（オペラ
ンド）に高度に並列的なガロア体乗算を行なう事
のできるハツシユ回路によつて達成される。この
回路は、ハツシユすべきＮビツトの対象を記憶す
るためのＮビツトの標準的なシフトレジスタ及び
ハツシユ定数を記憶するためのＮビツトのレジス
タを備えている。また、ハツシユ動作の結果を累
算するために通常のＮビツトの出力レジスタが用
いられる。さらにハツシユ定数を巡回させたもの
を記憶するためにＫ個のＮビツト・フイードバツ
ク・シフトレジスタ（FSR）が用いられる。上
記シフトレジスタの内容は上記対象レジスタの選
択されたビツトの制御の下に排他的論理和を取ら
れ、中間的部分積を形成する。この動作はＮ／Ｋ
回継続し、この時そのハツシング対象は完全に評
価され、結果レジスタ中に置かれる。

この回路の重要な特徴は、ハツシング動作の終
了時に、（ｉ＝１、２…Ｋ−１に関して）レジス
タFSRiの最終内容をレジスタFSR（ｉ＋１）にコ
ピーしハツシユ定数レジスタの内容をレジスタ
FSR１にコピーする事によつてハツシユ定数の
種々のシフト結果がフイードバツク・シフトレジ
スタに再ロードされる事である。

このハツシユ回路のもう１つの重要な特徴は、
ローデイング動作の間にハツシユ定数の種々のシ
フトが事実上事前に計算され、フイードバツク・
シフトレジスタの動作に関する限りは実際のハツ
シユ動作と殆んど同一の動作系列によつてフイー
ドバツク・レジスタにロードされる事である。こ
の事前の計算を行なう事によつてハツシユ定数は
事実上部分的に乗算され、後続する高度に並列的
なハツシング動作のための適当な形式でフイード
バツク・シフトレジスタにロードされる。

〔発明を実施するための最良の形態〕

本発明を技術思想によれば、ハードウエア的に
実現されたハツシユ回路の前記の欠点は、本明細
書中で「選択」動作と呼ぶ動作によつてプログラ
ムがそのハツシユ関数（従つて分布特性）を変化
させる事を可能にする設計により回避される。選
択動作において、新しいハツシユ定数が容易且つ
迅速に供給される。この事は、出力従つてハツシ
ユされた数値の分布を変化させる効果を有する。
この特徴はどの従来技術のハードウエア・ハツシ
ユ回路にも存在する事が知られていない。入力値
にかかわりなく、ハツシユ関数によつて形成され
た数値の分布が均等に分布する高い確率を持つ事
を保証するために、本発明はユニバーサル・ハツ
シングの技術を用いる。ユニバーサル・ハツシン
グの基本的な考えは、どのようなハツシユすべき
値の集合に関しても、選択動作で用いた特定のハ
ツシング定数によつて指定されるハツシユ関数の
可能な選択の殆んど全てが比較的均等な出力値の
分布を生じる事である。従つて任意のランダムに
選ばれたハツシユ関数又はハツシユ定数が良く働
く可能性は非常に高い。ユニバーサル・ハツシン
グの基礎概念についてのより深い説明について
は、J.L.Carter and M.N.Weaman、“Universal
Clashes of Hash Functions”、Journal of
Computer and System Sciences、Vol.18、
pp.143〜154（april1979）を参照されたい。

ここで開示されるハツシユ回路は集積回路チツ
プ技術に適合し、少量の制御ハードウエアを用い
て２つの動作を実行するように設計される。

その２つの動作は「選択(A)」及び「ハツシユ
(B)」である。但し引数Ａ及びＢは第１図のＡレジ
スタ２に記憶されているハツシユ定数及びＢレジ
スタ４に記憶されているハツシング対象を意味す
る。「選択(A)」は引数Ａによつて指定された関数
（ハツシユ関数）が、次のハツシユ定数がシステ
ムに導入され適当な「選択」機能が実行されるま
で後続する全てのハツシユ動作のために使われる
べき事を指定する。「選択」機能はどのような計
算結果も与えないが、同じハツシユ定数を用いる
全ての後続するハツシユ動作をスピード・アツプ
するための、ハードウエアによつて実行される予
備計算を行なう事を可能にする。「ハツシユ(B)」
動作は、最も最近の「選択」動作によつて指定さ
れたハツシユ関数Ａによつて引数Ｂをハツシング
する手続きである。

以下の説明中で、Ｎはワード当りのビツト数を
表わし、ハツシユ定数Ａ、ハツシユ対象Ｂ及びハ
ツシユ動作によつて得られた数値は全て同様にＮ
ビツトである。この実施例ではＮビツトの結果が
ある応用にとつて非常に有用であるとして望まれ
ていると仮定する。しかしながら他の用途特にア
ドレス・ハツシングについては、ハツシユ動作に
よつて得られる値は０、１、２…2^M−１の範囲内
にある事が望ましいかもしれない。但しＭはＮよ
りも小さい。もしそうであれば、所望の目的のた
めに所望のＭビツトが利用可能となるように、結
果をＮ−Ｍビツト右又は左にシフトする事ができ
る。Ｍビツトの任意の他の連続的な又は不連続な
部分集合を等しい信頼性で同様に選択できる事に
注意されたい。任意の入力について良好な分布の
結果が期待されるユニバーサル・ハツシングの利
点は、シフト動作又は他の向うかのビツト選択手
続きの後にも保持される。

本発明のハツシユ回路はガロア体GF（2^N）にお
ける乗算の動作を実行する。第１図を参照する
と、「選択」動作が装置のＡレジスタ２に乗数を
セツトし、ある予備計算の行なわれる事を可能に
する。Ｂレジスタ４にロードされたハツシユ動作
の対象は被乗数として用いられる。ガロア体の演
算を行なうハードウエア自体は新規ではない。し
かし予備計算によつて乗算動作の高速化をはかり
且つ乗数即ちハツシユ定数が変化する事を可能に
する方法は従来知られていない。

ここで開示されたハツシユ回路において、体の
要素の乗算の通常の２進数の乗算によく似た方式
で行なわれる。乗算は一時に１ビツトづつ左にシ
フトされ、現在評価されている被乗数のビツトが
１か０かに依存して、上記乗数の値が中間合計に
加算されたり又は加算されなかつたりする。ガロ
ア体の演算と通常の演算との間の相違は第１に加
算が排他的OR（XOR）動作によつて行なわれる
事、第２に動作の進行と共に被乗算のビツト値を
事実上変化させる適切に選択されたフイードバツ
ク・シフトレジスタによつてシフト動作が行なわ
れなければならない事である。当然にこのシフト
レジスタは通常のシフトレジスタとは大幅に異な
つている。

このハツシユ回路の重要な特徴は、被乗数のい
くつかのビツトの評価を並列的に行なう事によつ
てガロア体の乗算が高速化される事である。上記
ビツトの数は、フイードバツク・シフトレジスタ
（FSR）の数によつて決定される。

この動作を効率化するため、被乗数の選択され
たビツトと乗数との適当な整合を得るために乗数
の予備計算を行なう必要がある。

以前に述べたように、ここで開示するハツシユ
回路はLSI又はVLSIの形で実現できる。従つて
レジスタ、データ経路、組み合せ論理等の全ては
数個のLSI又は１個のVLSIチツプ上に容易に配
置できる。

以下の説明中で次の用語が用いられる。Ｎは機
械ワードのビツト数を表わす。従つてそれはハツ
シユ定数（被乗数）を保持するＡレジスタ及びハ
ツシユ対象（乗数）を保持するＢレジスタ中のビ
ツト数と同じである。同様にフイードバツク・シ
フトレジスタ１〜Ｋ及び結果レジスタも全てＮビ
ツト幅である。第１図に示したANDゲート１０
〜１６は、第１の入力としてフイードバツク・シ
フトレジスタからのＮビツト及び第２の入力とし
てAND機能を制御するＢレジスタからの適当な
ビツトを有するＮ個のANDゲートである。パリ
テイ回路１８は回路の入力端子に奇数個の「１」
が生じた時には論理「１」が発生し、回路入力端
子に偶数個の「１」が生じた時は論理「０」を発
生するＮ個のパリテイ回路の集合体である。Ｎ個
のパリテイ回路の各々は、Ｋ個のフイードバツ
ク・シフトレジスタの各々及び結果レジスタ６か
ら入力を受け取る。従つてｉ番目のパリテイ回路
はＫ個のフイードバツク・シフトレジスタの各々
からｉ番目のビツト及び結果レジスタからｉ番目
のビツトを受け取る。パリテイ回路１８の出力
は、Ｎビツトから成り、結果レジスタ６に入力さ
れその以前の内容を置き換える。

数Ｋは設計の大きさ及び速度に影響を与えるパ
ラメータである。Ｋの値がより大きくなるにつれ
てより多くの部品がチツプ上に必要になるが、乗
算動作における並行処理の程度が大きくなるため
ハツシユ動作はより速くなる。特に第１図を参照
すると、数Ｋは設計で用いられているフイードバ
ツク・シフトレジスタの数によつて決定される事
が容易にわかる。各シフトレジスタはハツシユ対
象のＮ／Ｋビツトを評価するので、１実施例では
ＫはＮの約数であるべきである。言い換えると、
Ｎ＝32であれば、Ｋは２、４、６、８又は16の値
を取り得る。

第１図に示した実施例の全てのレジスタはＮビ
ツト・レジスタである。ハツシユ定数を記憶する
Ａレジスタ２並びにハツシユ演算の中間結果及び
最終結果を受け取る結果レジスタ６は、並列式に
アクセスできる単純なレジスタである。Ｂレジス
タ４は、Ｋ本の出力線を有しシフト信号の制御の
下に左から右へシフトするシフトレジスタであ
る。フイードバツク・シフトレジスタFSR１〜
FSRK（８ａ〜８ｄ）はその名の通り、シフト信
号が与えられた時に右から左へシフトするシフト
レジスタである。さらに、フイードバツク・シフ
トレジスタは左端ビツトを右端ビツトに戻し、そ
してある他のビツト位置を変化させる。そのよう
なシフトレジスタの設計は公知であり、特に
Berlekamp著の前掲書中に詳細に説明されてい
る。

大きさＮの適当なフイードバツク・シフトレジ
スタを設計するために、最初に、ガロア体GF(2)
上のＮ次の既約多項式を選択する。w.w.
Peterson and E.J.Weldon、Jr.“Error
Correcting Codes”、MIT Press、Cambridge
Mass.（1971）には種々のＮについてそのような
多項式の表が示されている。与えられたＮの値に
付き多項式をどのように選択してもよいが、下記
の説明から明らかなように非０の係数の数が最小
のものが最も実用的である。

FSRはＮビツトのシフトレジスタで構成され、
その位置は右から左へ０、１、２…Ｎ−１と番号
付けられている。シフト動作はｉ番目のビツトを
（ｉ＋１）番目のビツトに移動させ且つ（Ｎ−１）
番目の位置のビツトをFSRの他のビツトに排他
的論理和する事から成る。排他的論理和の行なわ
れるビツト位置は、（最高次の係数を除いて）非
０の係数を持つ（選ばれた既約多項式の）項の指
数に相当するビツト位置である。例えば多項式が
X⁶＋X³＋１の場合、ビツト位置５がビツト位置
３及び０にフイードバツクされる。ビツト位置３
の新しい値は上述のようにビツト位置２及び５か
ら導き出される。これらの２つの値は排他的OR
動作によつて組み合される。しかしながらビツト
位置０は、その位置に来る他のビツトが存在しな
いので、排他的ORは不要である。

第２図は、フイードバツク・ビツトを受け取る
FSRのビツト位置の１つを示す図である。２つ
の隣接ビツト位置も示されている。（排他的OR
の起きない０番目のビツト位置以外の）ビツト位
置に入力されたフイードバツク・ビツトは、フイ
ードバツク位置の右隣のビツトとの排他的ORを
取られ、その結果の値は排他的OR回路の出力に
接続されたラツチに記憶される。そのような回路
の動作は周知のものである。

Ｂレジスタにおいて、その出力は０番目、
（Ｎ／Ｋ）番目、（2N／Ｋ）番目…のビツト位置
から取り出される事に注意されたい。Ｎ＝６及び
Ｋ＝２の場合を示す第３Ａ図〜第３Ｆ図及び第４
Ａ図、第４Ｂ図では、Ｂレジスタ４からの出力は
上述のように０番目及び３番目のビツト位置から
取り出されている。

Ａレジスタ２及び全てのフイードバツク・シフ
トレジスタ８ａ〜８ｄは並列にロード及びアンロ
ードできる事にも注意されたい。その回路は第１
図に示されていないが、後述の「選択」動作の例
を示す第４Ａ図及び第４Ｂ図のデータ・フロー図
に機械的に示されている。そのようなレジスタは
周知のものである。この機能により、Ａレジスタ
２からFSR１（８ａ）へ、FSR１（８ａ）から
FSR２（８ｂ）へ等、完全なＮビツトを迅速に
転送できる。

第１図において、太い線はＮビツトのバスを表
わし、ANDゲート１０〜１６の各々は実際は並
列に配置されたANDゲートの集合体である。そ
れらはRSRの各ビツト毎に設けられている。

第１図の論理回路の機能を簡潔に説明するため
に、シフト動作がちようど完了し、その結果Ｂレ
ジスタ４が右に１ビツトシフトされフイードバツ
ク・シフトレジスタの全てが左へ１ビツトシフト
され、Ｎビツト・ケーブル３０〜３６に現われて
いる値は現在のFSR１〜FSRKの内容を表わして
いると仮定する。信号線２０〜２６に接続された
Ｂレジスタの４ビツト位置の２進値が論理「１」
の場合、対応するANDゲート１０〜１６が活性
化され、対応するFSRの内容がバス３０〜３６
に出力される。逆にＢレジスタのビツト位置が論
理「０」を含む場合、信号線２０〜２６に出力さ
れたその値は、対応するANDゲート１０〜１６
を禁止し、バス３０〜３６の出力を全「０」にす
る。パリテイ回路１８内のＮ個の論理回路の各々
には付加的な即ち（Ｋ＋１）番目の入力が加えら
れ、結果レジスタ６に新しい結果が与えられる。

次に、この基本的な回路動作を反復的に用いて
ハツシユ動作を行なう方法を説明する。

ハツシユ動作においてＮビツトの対象オペラン
ドがＢレジスタ４にロードされる。動作が開始す
る前に、Ａレジスタ２及びFSR１（８ａ）の両
者は（先行する選択動作によつてセツトされた）
ハツシユ定数Ａを含み、残りのFSRの各々はそ
の直前のレジスタ中の値にＮ／Ｋフイードバツ
ク・シフトを行なつた結果を含んでいる。ハツシ
ユ(B)動作が開始されると、Ｎビツトの対象ＢがＢ
レジスタ４に入力され、結果レジスタ６は全０に
セツトされる。結果レジスタ及びFSRの内容は
パリテイ回路１８で選択的に組み合される。但し
各FSRの内容は、対応するＢレジスタのビツト
が論理「１」である場合にのみパリテイ回路１８
にゲートされる。次にシフト信号がシステムに加
えられ、FSRは（フイードバツクを伴なつて）
その内容を１ビツト、シフトさせ同様にＢレジス
タも１ビツトのシフトを行なう。Ｂレジスタ、
FSRレジスタ及び結果レジスタの内容はANDゲ
ート１０〜１６及びパリテイ回路１８によつて組
み合され、結果レジスタに新しい値を与える。
FSR及び結果レジスタの内容をＢレジスタの内
容の制御の下に論理的に組み合せる工程の後に
は、合計Ｎ／Ｋ回のＢレジスタ及びFSRの１ビ
ツト・シフトが続き、この時Ｂレジスタ中の対象
全体が評価される。この時、結果レジスタはハツ
シユ動作の所望の結果Ａ＊Ｂを含む。

この時、次のハツシユ動作を実行できるよう
に、ハツシユ定数Ａを適当にシフトした値を有す
る初期設定状態に全部のFSRをリセツトする必
要がある。これは、FSR１が非回転のハツシユ
定数Ａを含みFSR２がFSR１の以前の値を含む
ように全部のFSR及びＡレジスタを下向きに１
ビツト・シフトする事によつて行なわれる。
FSRKの以前の内容は単に拾てられる。ハツシユ
動作の間、ハツシユ定数であるＡレジスタの内容
は変化しない事に注意されたい。

下記のプログラム様の動作の記述は、上述のハ
ツシユ動作を要約するものである。この動作は３
つの基本的なステツプを含み、ステツプ２はステ
ツプ３に進む前にＮ／Ｋ回反復されるループであ
る。このチヤートの意味は明白であり特に説明は
要しないであろう。

(1) Ｂレジスタにハツシユ対象データを、結果レ
ジスタに全０をロードする。

(2) Ｎ／Ｋ回、反復する： −Ｂレジスタの適当なビツトによつてされた
FSRを結果レジスタと共にXORし、結果レジ
スタに記憶する。

−Ｂレジスタ及びFSRを１ビツト・シフト
する。

(3) 全部のFSR及びＡレジスタを１レジスタ位
置下に移動させる。

次に選択動作について説明する。選択動作にお
いては、後続するハツシユ動作が最小限の遅延及
び最大限の並列性で実行されるように、Ａレジス
タに新しいハツシユ定数Ａをロードし、ハツシユ
定数Ａの種々のシフト値を事実上予備計算して
種々のFSRにロードする。ハツシユ定数ＡはＡ
レジスタにロードされ、次に完全なハツシユ動作
がＫ−１回実行される。各ハツシユ動作はＮ／Ｋ
回のシフト動作及びそれに続くFSR及びＡレジ
スタの下向きの完全なシフトから成る事を想起さ
れたい。従つて、選択動作の終了時には、全ての
FSRに正しい回数だけ巡回したハツシユ定数の
正しい変形がロードされており、具体的はハツシ
ユ対象に対してハツシユ動作を行なう事が可能と
なる。

選択動作はFSRレジスタ及びＡレジスタの内
容に対してだけ作用する。Ｂレジスタ及び結果レ
ジスタの内容は選択動作では何の重要な役割りも
演じない。ANDゲート１０〜１６及びパリテイ
回路１８も同様である。事実、それらは機能的に
は省略してもよく、第４Ａ図及び第４Ｂ図では説
明を簡単にするため省略されている。

下記に示すのは、前記のハツシユ動作のプログ
ラム様のリストに類似した選択動作の動作シーケ
ンスの簡単なリストである。明らかに選択動作に
は３つの基本的なステツプがあり、３番目のステ
ツプはＫ−１回反復されるループを含む。このル
ープの内容は「ハツシユ動作」と呼ばれている事
に注意されたい。この場合、プログラミング技術
において通常そうであるように、この記述は前記
の完全なハツシユ動作を呼び出してその完全なハ
ツシユ動作を合計Ｋ−１回反復させる。

(1) Ａレジスタにハツシユ定数Ａをロードする。

(2) ＡレジスタからFSR１にロードする。

(3) 下記の動作をＫ−１回反復する。

−ハツシユ動作本発明の範囲から逸脱する事なく、これらの動
作に種々の変更を加える事ができる。例えばハツ
シユ手続中でステツプ３は再配置可能であり、ス
テツプ２とステツプ３を交換する事ができる。同
様に選択動作のステツプ２は完全に末消する事が
できる。その他にも同様の変更を加える事が可能
である。

第３Ａ図〜第３Ｆ図及び第４Ａ図、第４Ｂ図に
は、実際に具体的な２進数値を用いて本発明の動
作が説明されている。

第３Ａ図には、Ｂレジスタ４にバツシユ対象を
ロードし、結果レジスタ６を初期設定した後の状
態が示されている。Ａレジスタ２には既にハツシ
ユ定数がロードされている。第３Ｂ図は最初の中
間結果を得た後の状態を示す。第３Ｃ図は最初の
シフト動作を行なつた後の状態を示す。第３Ｄ図
は、２番目の中間結果を累算し、２番目のシフト
を行なつた後の状態を示す。第３Ｅ図は３番目の
中間結果を累算し、３番目のシフトを行なつた後
の状態を示す。第３Ｆ図は最終状態を示し、各
FSRはその上側のレジスタの内容をロードされ、
第３Ａ図のFSRの内容と同一になつている。こ
の状態では、Ｂレジスタに新しいハツシユ対象を
ロードし次のハツシユ動作を行なう事ができる。

第４Ａ図及び第４Ｂ図において、全ての排機能
的な、従つて不必要な回路は図面から省略し、そ
の代りにＡレジスタ及びFSRを接続する２本の
Ｎビツトのケーブル４０及び４２を示している。
この経路によつてＡレジスタ及びFSRの内容は、
ハツシユ回路の選択動作中に各ハツシユ動作の最
終ステツプが行なわれる時に、順に下向きに転送
される。第４Ａ図はＡレジスタ２にハツシユ定数
をロードし、その値をFSR１（８ａ）にコピー
した後の状態を示す。レジスタの内容が空欄にな
つているのは、任意の値を意味する。第４Ｂ図は
最初のハツシユ動作を行なつた後の状態を示す。
この場合Ｋ＝２なので、選択動作を完了するのに
１回のハツシユ動作しか必要でない。

第３Ａ図〜第３Ｆ図及び第４Ａ図、第４Ｂ図に
示した単純なシステムは説明のためのものであつ
て、実際は32程度のＮの値が普通であり、Ｋの典
型的な値はおそらく４又は８であろう。さらに、
所定の値のＮに関して２以上の既約多項式がおそ
らく存在し、どのシフトレジスタの構成を用いて
もよいが、最適の構成は（回路のコストを下げる
ように）フイードバツク点が最小のものであろ
う。

さらに、他の細部のハードウエアの変更、例え
ばシフトの相対的方向並びに上位ビツト及び下位
ビツトの指定等は任意であり設計的事項である。
但し完全なガロア体の乗算が行なわれるようにし
なければならない。

第２の変更は、ＫをＮの約数以外の数に選ぶ事
であろう。その場合、Ｎ／Ｋよりも大きな最小の
整数をＬとすると、１回のハツシユ演算を行なう
ためにＬ回のシフトが行なわれる。Ｂレジスタか
らはＬビツト毎にANDゲートへの制御入力が取
り出される。この時、Ｂレジスタをシフトする際
にその上位ビツトに対して０が入力される。

第３の変更は、選択動作の実行中にハツシユ動
作が行なわれた回数をカウントするためにＢレジ
スタを使う事である。

【図面の簡単な説明】

第１図は、本発明のハツシユ回路の図、第２図
は、フイードバツク・シフトレジスタの一部分の
図、第３Ａ図乃至第３Ｆ図は、単純化したハツシ
ユ回路を用いてハツシユ動作を説明する図、第４
Ａ図及び第４Ｂ図は、単純化したハツシユ回路を
用いて選択動作を説明する図である。２……Ａレジスタ、４……Ｂレジスタ、６……
結果レジスタ、８ａ〜８ｄ……フイードバツク・
シフトレジスタ（FSR）、１８……パリテイ回
路。

Claims

【特許請求の範囲】

１Ｎビツトのハツシユ定数の関数としてＮビツ
トのオペランドにハツシユ演算を行なうハツシユ
回路であつて、ハツシユすべきオペランドを受け
取るシフトレジスタと、ハツシユ定数を受け取り
記憶するレジスタと、ハツシユ演算の結果を累算
する結果レジスタと、複数個のフイードバツク・
シフトレジスタと、上記フイードバツク・シフト
レジスタの隣接したものに関して所定の数のビツ
ト位置だけ上記ハツシユ定数をシフトさせたもの
を上記フイードバツク・シフトレジスタの各々に
ロードする手段と、上記フイードバツク・シフト
レジスタの内容を上記オペランド・シフトレジス
タ中の対応するビツトの２進状態及び直前の累算
結果の関数として累算する手段と、上記フイード
バツク・シフトレジスタ全部及び上記オペラン
ド・シフトレジスタをシフトさせ中間結果を上記
所定の回数累算する手段とを含むハツシユ回路。