JPS59125437A - ハツシユ回路 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 〔技術分野〕 本発明は、ディジタル計算機にお（・て「・・ランス」
演算を行なうハードウェア装置に関する。

〔背景技術〕

ハツシュ関数の基本的な目的は、未知のそしておそらく
歪んだ分布の数値をより一様な分布の、しばしばより小
さな範囲内の数値に変換する事である。・・ツシュ関数
の１つの応用は連想記憶の分野にある。そこでは人物の
名前又は口座番号等の識別子がハツシュ関数によって計
算機のメモリのアドレスに変換される。このアドレスは
、その識別子に関係するデータを操索するための開始点
として用いられる。連想記憶が効率的に働くためには、
例え識別子が高度の相関を有する時でも、・・ツシュ関
数によって与えられるアドレスが可能なアドレス上に比
較的均一に拡がる事が重要である。

ハツシュ関数には、オペレーティング−システム、コン
パイラ、インタープリタ、データ・ベース管理、暗号方
式、単語綴り検査、誤り訂正検出方式等の他の多くの用
途が存在する。

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

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

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

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

前述のように、メモリ・アドレスを生成す全目的で・・
ノ７ング演算を行なう事は従来周知である。

同様にガロア体の乗算も周知の数学的手続きである。下
記の文献はその代表的な先行技術である。

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

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

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

〔発明の開示〕

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

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

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

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

この回路の重要な特徴は、ノ・ツシング動作の終了時に
、（ｉ−１，２・・・Ｋ−１に関して）レジスタＦＳＲ
ｉの最終内容をレジスタＦＳＲ（ｉ−ｌ−１）にコピー
しハツシュ定数レジスタの内容をレジスタＦＳＲ１にコ
ピーする事によってハツシュ定数の種々のシフト結果が
フィードバック・シフトレジスタに再ロードされる事で
ある。

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

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

本発明の技術思想によれば、ノ・−ドウエア的に実現さ
れた・・７７１回路の前記の欠点は、本明細書中で「選
択」動作と呼ぶ動作によってプログラムがその・・ツン
ユ関数（従って分布特性）を変化させる事を可能にする
役割により回避される。選択動作において、新しいハツ
シュ定数が容易且つ迅速に供給される。この事は、出力
従ってハツシュされた数値の分布を変化させる効果を有
する。

この４１はどの従来技術のノ・−ドウエア・ハツシュ回
路にも存在する事が知られていない。入力値にかかわり
なく、ノ・ツシュ関数によって形成された数値の分布が
均等に分布する高い確率を持つ事を保証するために、本
発明はユニノ（−サル・）・ツシングの技術ヲ用（・る
。ユニバーサル・７１ツシングの基本的な考えは、どの
よりな）・ツシュすべき値の集合に関しても、選択動作
で用いた特定のノ・ツシング定数によって指定されるノ
・ツシュ関数の可能な選択の殆んど全てが比較的均等な
出力値の分布を生じる事である。従って任意のランダム
に選ばれた・・ツシュ関数又はノ・ツシュ定数が良く働
く可能性は非常に高い。ユニバーサル・ノ・ツシングの
基礎概念につし・てのより深い説明については、Ｊ、Ｌ
、Ｃａｒｔｅｒ　　ａｎｄ　　Ｍ、Ｎ、Ｗｅｇｍａｎ。

”　Ｕｎｉｖｅｒｓａｌ　　Ｃ１ａｓｈｅｓ　　ｏｆ　
　ＨａｓｈＦｕｎｃｔｉｏｎｓ”、Ｊｏｕｒｎａｌ　ｏ
ｆ　Ｃｏｍｐｕｔｅｒａｎｄ　　Ｓｙｓｔｅｍ　５ｃｉ
ｅｎｃｅｓ、Ｖｏｌ、１Ｂ、ｐｐ。

１４６〜１５４（ａｐｒｉｌ　　１９７９）を参照され
たい。

ここで開示されるノ・ツシュ回路は集積回路チップ技術
に適合し、少量の制御・・−トウエアを用いて２つの動
作を実行するように設割される。

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

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

本発明のハツシュ回路はガロア体ＧＦ（２）における乗
算の動作を実行する。第１図を参照すると、［選択」動
作が装置のＡレジスタ２に乗数をセットし、ある予備計
算の行なわれる事を可能にする。Ｂレジスタ４にロード
されたハツシュ動作の対象は被乗数として用いられる。

ガロア体の演算を行なうハードウェア自体は新規ではな
い。

しかし予備計算によって乗算動作の高速化をはかり且つ
乗数即ちハツシュ定数が変化する事を可能にする方法は
従来知られて（・なし・。

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

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

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

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

以下の説明中で次の用語が用いられる。Ｎは機械ワード
のビット数を表わす。従ってそれはハツシュ定数（被乗
数）を保持するＡレジスタ及び・・ツシュ対象゛（乗数
）を保持するＢレジスタ中のビット数と同じで゛ある。

同様にフィードバック・シフトレジスタ１〜ＫＡび結果
レジスタも全てＮビット幅である。第１図に示したＡＮ
Ｄゲート１０〜１６は、第１の入力としてフィートバッ
ク・／フトレジスタからのＮビット及び第２の入力とし
てＡＮＤ機能を制御するＢレジスタからの適当なビット
を有するＮ個のＡＮＤゲートである。パリティ回路１８
は回路の入力端子に奇数個の１１」　゛が生じた時には
論理１１」を発生し、回路入力端子に偶数個の「１」が
生じた時は論理［−〇」を発生するＮ個のパリティ回路
の集合体である。Ｎ個のパリティ回路の各々は、Ｋ個の
フィードバック・シフトレジスタの各々及び結果レジス
タ６かも入力を受は取る。従って１番目のパリティ回路
はに個のフィードバック・／フトレジスタの各々から１
番目のビット及び結果レジスタか、ら１番目のビットを
受は取る。パリティ回路１８の出力は、Ｎビットから成
り、結果レジスタ乙に人力さ」ｌその以前の内容を置き
換える。

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

第１図に示した実施例の全てのレジスタはＮビット・レ
ジスタである。ハツシュ定数を記憶するＡレジスタ２並
びにハツシュ演算の中間結果及び最終結果を受は取る結
果レジスタ６は、並列式にアクセスできる単純なレジス
タである。Ｂレジスタ４は、Ｋ本の出力線を有しシフト
信号の制御の下に左から右ヘシフトするシフトレジスタ
である。

フィードバック参ノットレジスタＦＳＲ１〜ＦＳＲＫ（
８ａ〜８ｄ）はその名の通り、シフト信号が与えられた
時に右から左ヘシフトす−るシフトレジスタである。さ
らに、フィードバック・シフトレジスタは左端ビットを
右端ビットに戻し、そしである他のビット位置を変化さ
せる。そのような７フトレジスタの設計は公知であり、
特にＢｅｒｌｅｋａｍｐ著の前掲書中に詳細に説明され
て℃・る。

大きさＮの適当なフィードバック・シフトレジスタを設
計するために、最初に、ガロア体ＧＦ（２）上のＮ次の
既約多項式を選択する。Ｗ、　Ｗ。

Ｐｅｔｅｒｓｏｎ　　ａｎｄ　　Ｅ、Ｊ、Ｗｅｌｄｏｎ
ＳＪｒ。

”　Ｅｒｒｏｒ　　Ｃｏｒｒｅｃｔｉｎｇ　　Ｃｏｄｅ
ｓ”、ＭＩＴＰｒｅｓｓ、　Ｃａｍｂｒ　ｉｄｇｅ、　
Ｍａｓｓ、　（１９７１）には種々のＮにつ（・てその
ような多項式の表が示されて℃・る。与えられたＮの値
に付き多項式をどのように選択してもよし・が、下記の
説明から明らかなように非０の係数の数が最小のものが
最も実用的である。

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

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

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

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

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

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

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

ハツシュ動作においてＮビットの対象オペランドがＢレ
ジスタ４にロードされる。動作が開始する前に、Ａレジ
スタ２及びＦＳＲｌ（８ａ）の両者は（先行する選択動
作によってセットされた）ハツンユ定数Ａを含み、残り
のＦＳＲの各々はその直前のレジスタ中の値にＮ／にフ
ィードバック・シフトを行なった結果を含んでし・る。

ハツシュ（Ｂ）動作が開始されると、Ｎビットの対象Ｂ
がＢレジスタ４に入力され、結果レジスタ６は全０にセ
ットされる。結果レジスタ及びＦＳＲの内容はパリティ
回路１日で選択的に組み合される。但シ各Ｆ　Ｓ　Ｒの
内容は、対応するＢレジスタのビットが論理「１」であ
る場合にのみパリティ回路１８にゲートされる。次にシ
フト信号がシステムに加えられ、ＦＳＲは（フィードバ
ックを伴なって）その内容を１ビツト、シフトさせ同様
にＢレジスタも１ビツトのシフトを行なう。Ｂレジスタ
、ＦＳＲレジスタ及び結果レジスタの内容はＡＮＤゲー
ト１０〜１６及びパリティ回路１８によって組　　−み
合され、結果レジスタに新しい値を与える。ＦＳＲ及び
結果レジスタの内容をＢレジスタの内容の制御の下に論
理的に組み合せる工程の後には、合計Ｎ／に回のＢレジ
スタ及びＦＳＲの１ビツト・シフトが続き、この時Ｂレ
ジスタ中の対象全体が評価される。この時、結果レジス
タはノ・ツシュ動作の所望の結果Ａ％Ｂを含む。

この時、次のハツシュ動作を実行できるように、ハツシ
ュ定数Ａを適当にシフトした値を有する初期設定状態に
全部のＦＳＲをリセットする必要が□　　ある。これは
、ＦＳＲｌが非回転のノ・ツシュ定数Ａを含みＦＳＲ２
がＦＳＲｌの以前の値を含むように全部のＦＳＲ及びＡ
レジスタを下向きに１ピツ１ト・シフトする事によって
行なわれる。ＦＳＲＫの以前の内容は単に拾てられる。

ノ・ツシュ動作の間、ハツシュ定数であるＡレジスタの
内容は変化しない事に注意されたい。

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

（１）Ｂレジスタにハツシュ対象データを、結果レジス
タに全０をロードする。

（２）Ｎ／に回、反復するニ ーＢレジスタの適当なビットによっ てされたＦＳＲ′ｆｆ：結果レジスタと共にＸ０ＲＬ、
結果レジスタに記憶する。

−Ｂレジスタ及びＦＳＲを１ビツト ・ソフトする。

（６）全部のＦＳＲ及びＡレジスタをルジスタ位置下に
移動させる。

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

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

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

（１）　　Ａレジスタにノ・ツンユ定数Ａをロードする
。

（２）ＡレジスタからＦＳＲｌにロードする。

（λ）下記の動作をＫ　−１１６１反復する。

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

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

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

第４Ａ図及び第４Ｂ図において、全ての非機能的な、従
って不必要な回路は図面から省略し、その代りにＡレジ
スタ及びＦＳＲを接続する２本のＮビットのケーブル４
０及び４２を示している。

この経路によってＡレジスタ及びＦＳＲの内容は、・・
ツシュ回路の選択動作中に各・・ツシュ動作の最終ステ
ップが行なわれる時に、順に下向きに転送される。第４
Ａ図はＡレジスタ２にハツシュ定数をロードし、その値
をＦＳＲｌ（８ａ）にコピーした後の状態を示す。レジ
スタの内容が空欄になって℃・るのは、任意の値を意味
する。第４Ｂ図は最初のハツシュ動作を行なった後の状
態を示す。

この場合に＝２なので、選択動作を完ｒするのに１回の
ハツシュ動作しか必要でない。

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

さらに、他の細部のハードウェアの変更、例えばシフト
の相対的方向並びに上位ビット及び下位ビットの指定等
は任意であり設計的事項である。

但し完全なガロア体の乗算が行なわれるようにしなけれ
ばならない。

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

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

【図面の簡単な説明】

第１図は、本発明のノ・ツシュ回路の図、第２図は、フ
ィードバック・シフトし／ジスタの一部分の図、 第３Ａ図乃至第６Ｆ図は、単純化した・・ツシュ回路を
用いてノ・ツシュ動作を説明する図、第４Ａ図及び第４
Ｂ図は、単純化したノ・ツシュ回路を用いて選択動作を
説明する図である。 ２・・・・Ａレジスタ、４・・・・Ｂレジスタ、６・・
・・結果レジスタ、８ａ〜８ｄ・・・・フィードバック
・シフトレジスタ（ＦＳＲ）、１８・・・・パリティ回
路。 出願人　　インターナショナル・ビジネス・マシーンズ
・コーポレーションＦＩＧ、２ ＦＩＧ、３Ａ ＦＩＧ、３Ｃ ＦＩＧ、３Ｅ ＦＩＧ、４Ａ

Claims (1)

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