JPS60695B2 - 三入出力分類装置 - Google Patents

Description

【発明の詳細な説明】 本発明は３つの数値を値の大きさの順に並べ替えて出力
する二進数値分類装置に関するものである。

大量の情報を分類処理することは、ディジタルコンピュ
ーターの最も得意とし、取分けファイル操作等には欠か
せない重要な処理の一つである。

なかでも、複数個の数値を大きさの順（大きい順または
小さい順）に並べ替える操作は、最も単純で基本的な分
類処理の一例であり、簡単な数値比較を繰返すことによ
って実施される。ここで問題とされるのは分類処理に費
される時間である。

特に分類すべき情報が多量である場合、上述の如き単純
な繰返し操作が適用されれば、データ量に比例した膨大
な処理時間を要することとなる。このため種々に工夫さ
れた分類アルゴリズムを適用することによって処理時間
の短縮が図られている。さらに斯かる問題を解決する方
法の一例として、冨永、平山による「ファイルメモリに
おけるコンテントアドレスの一手法」を電子通信学会電
子計算機研究会資料１９７２年１月２１日資料番号ＥＣ
７１一６１（１９７２−０１）（以下文献１とする）に
並列分類処理の方法が提案されている。

この方法によれば、２つの二進数値をビット毎に比較し
て大小の順位を判定し出力する分類回路を基本のセルと
し、これらの分類セルを配列状に並べ規則的な組合せに
より結合して並列分類処理装置を構成し、処理の高速化
を達成している。この場合には、装置を構成する個々の
分類セルが簡単な構造であることが利点とされるが、大
量の情報を同時に分類するには、データ量に応じた個数
の分類セルを設置する必要があり、装置が大型化ととも
に処理時間が増大することが最大の欠点である。一方、
集積化技術の進歩により、１個のけ１チップ上に複雑で
大規模な回路を収容することが可能となった。この事実
と、前述の装置構成方法とを合せて考えれば、分類セル
の機能を適度に増し、装置を構成する要素の数を減少さ
せることが、装置を小型化し、処理の高速化を達成する
手段と成り得るが処理時間の増大は避けることが出来な
い。本発明の目的は、上記事情に鑑み、並列分類処理装
置の構成要素としてより高度な機能を果すとともに高速
処理可能とし、かつ集積化に通した構造の三入出力分類
装置を提供することにある。

本発明によれば３つの二進数値を上位ビットから順次入
力し、前記３つの二進数値を大きさの順に並べ替える装
置において、初期状態と第一のレベルの６つの状態と第
二のレベルの６つの状態とから成る１針圏の内部状態を
区別して表わす記憶回路と、３本の入力信号線を有す駆
動回路と、３本の出力信号線を有す出力回路とを備え、
前記駆動回路は前記３つの二進数値の上位ビットから順
次入力される３つの入力信号の組合せを遂次判定して前
記記憶回路を駆動し、その内部状態を、前記逐次判定さ
れる結果により前記３つの二進数値のいずれも順序が決
まらないときは初期状態に留め、さらに逐次判定される
結果により、前記３つの二進数値のいずれか１つの順位
が決まったとき前記初期状態から第一のレベルの６つの
状態のうちいずれか決められた１つの状態へ遷移させ、
さらに逐次判定される結果により、まだ順序の決まらな
い残り２つの二進数値の順序が決まるまで第一のレベル
の前記遷移された状態へ留め、また前記残り２つの二進
数値の順序が決ったとき第一のレベルの前記遷移された
状態から第二のレベルの６つの状態のうちいずれか決め
られた状態へ遷移させて、前記逐次判定された結果に従
い前記３つの二進数値の順序関係を順次分類し、前記分
類された順序関係を前記記憶回路の１３個の内部状態の
それぞれで区別して記憶し、前記出力回路は前記分類さ
れた順序関係に従って前記３つの入力信号を並べ替えて
それぞれ前記３本の出力信号線へ出力する三入出力分類
装置が得られる。次に図面を参照して本発明を詳細に説
明する。

第１図は従来技術により実施された三入出力分類装置の
構成を示すブロック図であり、その欠点を指摘するため
の図である。１１，１２，１３はシフトレジスタであり
、それぞれには分類すべき二進数値が記憶されている。

２０は従来技術により構成された三入出力分類装置であ
る。

２１，２２，２３は二入出力分類セルであり、前記文献
１に記載された２つの二進数値を上位ビットより日項次
入力して、それらの組合せを判定することにより大小の
順序付けをし、二本の出力信号線の一方へ小さい数値を
、他方へ大きい数値を上位ビットより順次出力する回路
である。

即ち、従来技術によれば三入出力分類装置２０‘ま３つ
の二入出力分類セルを三段に組合せて構成することがで
きる。１０１，１０２，１０３はそれぞれシフトレジス
タ１１，１２，１３の出力信号線であると同時に、三入
出力分類装置２０の入力信号線でもある。

２０１，２０２，２０３は三入出力分類装置２０の出力
信号線であると同時に、それぞれシフトレジスター１，
１２，１３の入力信号線でもある。

Ｘ，，Ｘ２，Ｘ３はそれぞれシフトレジスタ１１，１２
，１３から出力される１ビットずつの出力信号即ら三入
出力分類装置２０の入力信号を表わす。Ｚ，，Ｚ，Ｚ３
は三入出力分類装置２０から出力される１ビットずつの
出力信号を表わす。１００は同期信号Ｃを供給する信号
線である。この同期信号Ｃによって、各シフトレジスタ
１１，１２，１３から記憶された数値が上位ビットより
順次出力され、三入出力分類装置２０へ入力信号Ｘ，，
Ｘ２，Ｘ３として供給される。

入力信号Ｘ，，Ｘ２，Ｘ３は各二入出力分類セル２１，
２２，２３を通過し、順序付けられた出力信号Ｚ，乙，
Ｚ３が得られる。出力信号乙，Ｚ２，Ｚ３は再びシフト
レジスタ１１，１２，１３へ順次シフトィンされて記憶
される。この動作が一巡即ちシフトレジスタのビット長
分だけ完了すると、シフトレジス夕１１，１２，１３へ
記憶された数値は大きさの順に並べ替えられたものとな
る。さらに斯かる動作を正確に行なわせるため、次の措
置が必要となる。

２４，２５は遅延回路であり、それぞれ二入出力分類セ
ル２２，２３へ同期信号Ｃを適当なタイミングで供給す
る。

これは回路動作を同期化することによって、各二入出力
分類セルの順序的動作と、伝搬する信号の遅延による誤
動作を防ぐためである。しかしながらこの措置は回路動
作を遅くする原因となり、さらにこの三入出力分類装置
でより大きな分類装置を構成する場合その影響はさらに
顕著となり、従来技術の欠点である。次に三入出力分類
装置２０を別の手段で実施する本発明について説明する
。

第２図は本発明の原理を説明するための図であり、本発
明による三入出力分類装置の動作を規定する状態遷移図
である。

第１図と対応させて、入出力信号はＸ，，Ｘ２，Ｘ３お
よびＺ，，Ｚ，Ｚ３と表し、特に各入出力信号に対応す
る数値は数値Ｘ，、数値Ｘ２、数値Ｘ３等と表わす。本
状態遷移図の意味するところは、３つの二進数値Ｘ，，
Ｘ２，Ｘ３を上位ビットより日頃次取出して得られる入
力信号Ｘ，，Ｘ２，Ｘ３の組合せを逐次分類して、数値
Ｚ，ミ数値Ｚミ数値Ｚとなるように出力信号Ｚ，，Ｚ，
Ｚ３を得るための手順を明確に示すことにある。

同図において、Ｓｏ，Ｓ，，…………，Ｓ，２は内部状
態名であり、特にＳｏを初期状態、Ｓ．，・・・・・・
・・・…，Ｓ６を第一のレベルの状態、Ｓ７，…………
Ｓ．２を第二のレベルの状態と呼ぶ。

４０１，４０２等は各内部状態間の遷移を示す矢印であ
り、それぞれに付けられたＸ，Ｘ２×３，Ｘ，Ｘ２等の
記号はその矢印で示される遷移の起る条件則ち入力信号
の組合せを表わす。

一例として、矢印４０１は初期状態Ｓｏにおいて、入力
信号の組合せがＸ，Ｘ２×３となるとき、第一のレベル
の状態Ｓ，への状態遷移が起ることを示す。ここでＸ，
Ｘ２×３は（Ｘ，，Ｘ２，Ｘ３）＝（０、０、１）であ
ること、またＸ，Ｘ２は（Ｘ，，Ｘ２）＝（０、１）で
かつＸ３は０または１のいずれでもよいことを意味する
。なお図面を簡単にするため省略されたが、記教された
以外の入力信号の組合せが生じた場合は、同じ状態に留
まるものとする。また別に入力されるリセット信号Ｒに
より、全ての状態から初期状態Ｓｏへの状態遷移が起る
ものとする。さらに省略された出力信号の記載は後の説
明の中で行なわれる。初期状態Ｓ。は動作を始める最初
の状態であり、数値Ｘ，，Ｘ２，Ｘ３のいずれの大きさ
の順も決定されない状態である。初期状態Ｓｏにおいて
は、入力信号Ｘ，，Ｘ２，Ｘ３の全ての組合せが調べら
れ、数値Ｘ，，Ｘ２，Ｘ３のいずれか１つだけの順位が
決定されると、第一のレベルの状態Ｓ，，…・・・・・
・・・・，Ｓ６のいずれか決められた状態へ遷移する。
第一のレベルの状態Ｓ，，・・・・・・・・・…，Ｓ６
は、数値Ｘ，，Ｘ２，Ｘ３のうち１つだけの順位が決定
された（６つの場合に分類される）状態のそれぞれに相
当する。一例として初期状態Ｓｏにおいては「入力信号
の組合せがＸ，Ｘ２ ×３ あるいはＸ・Ｘ２×３のと
き数値Ｘ，，Ｘ２，Ｘ３の大小関係は決まらないのでそ
のまま同じ状態Ｓｏに留まるが、Ｘ，Ｘ２×３のとき状
態Ｓ，へ、またＸ，Ｘ２×３のとき状態Ｓ２への状態遷
移が起る。即ち状態Ｓ，は数値Ｘ３が最大、また状態Ｓ
２は数値Ｘ．が最小と決定された状態を表わす等である
。第一のレベルの状態Ｓ，，…・・・・・・…，Ｓ６の
いずれかの状態にあると封こは、順序の決定されていな
い残る２つの数値に対する入力信号の組合せが調べられ
、その順序が決まるまで同一の状態に留まり、順序が決
定されると第二のレベルの状態Ｓ７，……・・・…，Ｓ
，２のいずれか決められた状態へ遷移する。

第二のレベルの状態Ｓ７，・・・・・・・…・・，ＳＩ
２は、数値Ｘ，，Ｘ２，Ｘ３の全ての順序が決定された
（６つの場合に分類される）状態のそれぞれに相当する
。

一例として、数値Ｘ３が最大と判定された状態Ｓ，にお
いては残りの２つの数値Ｘ，，Ｘ２が比較されて、入力
信号の組合せが×，Ｘ２あるいはＸ，Ｘ２のとき数値Ｘ
．，Ｘ２の順序は決まらないので同じ状態Ｓ，に留まる
が、又、Ｘ２のとき状態Ｓ７へ，Ｘ，Ｘ２ のとき状態
Ｓ，２へとそれぞれ第二のレベルの遷移が起る。また数
値Ｘ，が最小と判定された状態Ｓ２においてＸ２×３の
ときに状態Ｓ？への遷移が起る。即ち状態Ｓ７は数値Ｘ
．ミ数値Ｘ２ミ数値Ｘ３の順であると決定された状態を
表わす等である。以上説明された谷内部枕態の意味する
３つの−進数値の順序関係から、出力信号Ｚ，Ｚ２，Ｚ
は次のように決められる。

初期状態Ｓｏにおいては、出力信号乙，Ｚ２，Ｚ３へは
入力信号Ｘ，，Ｘ２，Ｘ３のいずれを出力してもよい。

第一のレベルの各状態では、一例として状態Ｓ，におい
ては、数値Ｘ３が最大と判定されたのであるから、出力
信号Ｚへ入力信号Ｘ３を出力し、出力信号乙，Ｚへは入
力信号Ｘ，，Ｘ２のいずれを出力してもよく、また状態
Ｓ４においては、数値Ｘ３が最小と判定されたのである
から、出力信号Ｚ，へ入力信号Ｘ３を出力し、出力信号
Ｚ２，Ｚへは入力信号Ｘ，，Ｘ２のいずれを出力しても
よい。第二のレベルの各状態では、一例として状態Ｓ７
においては数値Ｘ，ミＸ２ミＸ３と判定されたのである
から出力信号Ｚ，Ｚ，Ｚ３へは入力信号Ｘ，，Ｘ２，Ｘ
３の順にそれぞれ出力する等である。以上の説明から本
状態遷移表の全ての規則性は容易に判明できる。

以上説明を要約すれば、本発明の原理は３つの二進数値
の上位ビットから順次入力される３つの入力信号の組合
せを逐次判定し、先ず３つの二進数値のうち１つの二進
数値の順序を決定し、引続き残る２つの二進数値の順序
を決定するように予じめ順序だてた分類手順を与えてお
き、このように分類された３つの二進数値の順序関係を
内部状態のそれぞれに対応させることと、それぞれの内
部状態の意味する順序関係に従って入力信号を並べ替え
て出力することである。

第３図により本発明による三入出力分類装置の一実施例
を示す。

なお第１図と同一の信号線および信号には同一の参照番
号が使用されている。第３図ａは駆動回路および記憶回
路の具体的構成を示す回路図である。３０−１，・・・
・・・・・…・，３０−６は駆動回路および記憶回路の
一部であり、全て同一の回路構成で成り、かつ、それぞ
れの入出力信号線は同じ順序に並べられている。

ブロック３０−１の内部にその回路構成の詳細が示され
ている。３１，３２，・・・・・・・・・・・・，３
９はＮＡＮＤゲートである。

ＮＡＮＤゲート３６と３７および３８と３９はそれぞれ
セットＩＪセットフリップフロップ則ち記憶回路の一部
を構成する。ＮＡＮＤゲート３１，・・・……・・・，
３５は駆動回路の一部を構成する。４川まＮＯＲゲ−ト
であり、４１，４２，４３はインバータである。１０４
はリセット信号Ｒを供給する信号線である。

３００はＮＯＲゲート４０の出力信号線であり、初期状
態Ｓ。

に対応する状態信号Ｙ。を伝える。３０１，…………，
３０６はそれぞれブロック３０一１，・・・・……・・
，３０−６の出力信号線の一部であり「第一のレベルの
状態Ｓ，，・・・・・・・…・・Ｓ６に対応する状態信
号Ｙ，，・・・・・・……，Ｙ８を伝える。

３０７，…………，３１２はそれぞれブロック３０−１
，・・・・・・・・・・・・，３０一６の出力信号の他
の一部であり、第二のレベルの状態Ｓ７，・・・・・・
・・・・・・，Ｓ，２に対応する状態信号Ｙ７，・・…
・・・・・・・，Ｙ，２を伝える。

状態信号Ｙｏ，Ｙ，，・・・・・・・・・・・・，Ｙ，
２はいずれか１つだけが１となり、対応する内部状態Ｓ
ｏ，Ｓ，，・…・・・・・・”，Ｓ，２のいずれかの状
態にあることを表わす。リセット信号Ｒが０にされると
、ＮＡＮＤゲート３６と３７、３８と３９等の構成する
フリップフロップが全てオフとなる。

即ち状態信号Ｙ，，……・・・・・・，Ｙ，２の全ては
ＮＯＲゲート４０‘こ入力されその出力である状態信号
Ｙｏは１となる。これにて初期状態Ｓｏが設定され、続
いてリセット信号Ｒを１として動作は開始される。ＮＡ
ＮＤゲート３３は状態信号Ｙｏが１のとき入力信号の組
合せＸ，×２×３を検知してＮＡＮＤゲート３６，３７
の構成するフリップフロップをオン即ち状態信号Ｙ，を
１とする。また状態信号Ｙ，が１となれば、ＮＯＲゲー
ト４川こより状態信号Ｙｏは０となる。これにて初期状
態Ｓ。から状態Ｓ，への状態遷移が起ったことになる。
ＮＡＮＤゲート３２，３５は状態信号Ｙ，が１のとき入
力信号の組合せＸ，Ｘ２を検知して状態信号Ｙ，を０と
すると共に状態信号Ｙ７を１とする。同様にＮＡＮＤゲ
ート３１，３４は状態信号Ｙ．が１のとき入力信号の組
合せＸ，×２ を検知して状態信号Ｙ，を０とすると共
に状態信号Ｙ，２を１とする。他のブロック３０−２，
…………，３０−６の回路動作もこれと全く同機であり
、本回路構成によって第２図に示された状態遷移が正確
に行なわれる。第３図ｂは出力回路の具体的構成を示す
回路図である。

５０−１，５０一２，５０一３は出力回路の一部を示す
ブロックであり、全て同一の回路構成より成る。各ブロ
ック５０−１，５０−２，５０−３の入力出力信号線の
並び順序も同一である。回路構成の詳細はブロック５０
ーーの内部に示される。５１，５５，５６，…………，
５９はＡＮＤゲートである。

５２，５３，５４はＯＲゲートである。

６川まＡＮＤゲートである。

出力信号線２０１はＡＮＤゲート６０およびＡＮＤゲー
ト５５，５６と他のブロック５０−２，５０−３のこれ
に対応するＡＮＤゲートの各出力信号線のワイヤードＯ
Ｒである。出力信号線２０２はＡＮＤゲート５７，５８
と他のブロック５０一２，５０一３のこれに対応するＡ
ＮＤゲートの各出力信号線のワイヤードＯＲである。出
力信号線２０３はＡＮＤゲート５９と他のブロック５０
一２，５０−３のこれに対応するＡＮＤゲートの各出力
信号線のワイヤードＯＲである。本出力回路の動作を説
明するために、同回路図より導出される論理式を次に示
す。Ｚ，＝Ｘ，Ｘ２×３Ｙ。

十×，Ｘ２Ｙ，十Ｘ２Ｘ３Ｙ５十Ｘ，Ｘ３Ｙ３十×，（
Ｙ２十Ｙ７十Ｙ８）十×２（Ｙ６十Ｙ，．十Ｙ，２）十
×３（Ｙ４十Ｙ９十Ｙ，。）．・・．・・．・・（１−
１） Ｚ２＝×，Ｘ２（Ｙ。

十Ｙ４）十×２×３（Ｙ。十Ｙ２）十×，Ｘ２（Ｙ。十
Ｙ６）十×，（Ｙ，十Ｙ３十Ｙ９十Ｙ，２）十Ｘ２（Ｙ
Ｉ＋Ｙ５十Ｙつ十ＹＩ。）十×３（Ｙ３十Ｙ５十Ｙ８十
Ｙ，，） ………（１−２）Ｚ３＝×，（Ｙ２十Ｙ
７十Ｙ８）（Ｙ，十Ｙ３十Ｙ９十Ｙ，２）十×２（Ｙ６
十Ｙ，，十Ｙ，２）（Ｙ，十Ｙ５十Ｙ７十Ｙ，。）十×
３（Ｙ４十Ｙ９十Ｙ，。）（Ｙ３十Ｙ５十Ｙ８十Ｙ，，
）＝×，（Ｙ。

十Ｙ４十Ｙ５十Ｙ６十Ｙ，。十Ｙ，．）十×２（Ｙ。十
Ｙ２十Ｙ３十Ｙ４十Ｙ６十Ｙ９）十×３（Ｙ。十Ｙ，十
Ｙ２十Ｙ６十Ｙ７十Ｙ，２）…．・．．・・（１−３） これらの論理式は次のようにしてさらに詳細に確めるこ
とができる。

初期状態Ｓｏの場合、即ちＹｏ＝１であり、上記論理式
は、ＺＩ＝ＸＩＸ２×３ Ｚ２＝ＸＩＸ２十×２×３十ＸＩＸ３ Ｚ３：ＸＩ＋Ｘ２十×３ となる。

この関係は出力信号Ｚ，，Ｚ，Ｚ３へは入力信号Ｘ，，
Ｘ２，Ｘ３のいずれかがそれぞれに出力されることを示
している。一例として（Ｘ，，Ｘ２，Ｘ３）＝（０、０
、０）、（１、１、１）であればそれぞれ（Ｚ，，Ｚ２
，Ｚ３）＝（０、０、０）、（１、１、１）となる等で
ある。第一のレベルについて一例として状態Ｓ，の場合
、即ちＹ，＝１であり、上記論理式（１−１、２、３）
はＺＩニＸＩＸ２ Ｚ２ニＸＩ十×２ Ｚ３；Ｘ３ となる。

この関係は出力信号Ｚへ入力信号Ｘ３が出力され、出力
信号Ｚ，，Ｚのいずれかがそれぞれに出力されることを
示している。第二のレベルについて、一例として状態Ｓ
７の場合、即ちＹ７；１であり上記論理式（１−１、２
・３）はＺ，：Ｘ， Ｚ２＝Ｘ２ Ｚ３＝Ｘ３ となる。

この関係は出力信号Ｚ，，Ｚ，Ｚ３へ入力信号Ｘ，，Ｘ
２，Ｘ３がこの順に出力されることを示している。以上
説明された如く、本出力回路は前述の本発明の原理によ
る出力信号Ｚ，Ｚ２，Ｚ３に係わる説明の通り、第３図
ａの記憶回路の表わす各内部状態それぞれに応じて、入
力信号Ｘ，，Ｘ２，Ｘ３の並べ替えを行ない出力する動
きをするほのである。

また、上記論理式から容易に推察できるが、本出力回路
は、初期状態あるいは第一のレベルの各状態における出
力規則が、次の遷移先となる各状態での出力規則とも適
合するようにさらに条件を厳密にして構成されており、
高速動作を可能にしている。第４図は駆動回路および記
憶回路の別の実施例を示す回路図である。７０−１，・
・・・・・・・・・・・，７０一６は駆動回路および記
憶回路の一部を示すブロックであり、各ブロック共に同
一の回路構成よりなる。

ブロック７０一１，・・…・・・・・・・，７０−２の
それぞれの入出力信号線の並びは同じであり、特に各ブ
ロックの入力信号が反転されて入力される場合には、各
ブロックの入力端に丸印を付け、図面を簡略化してある
。各ブロックの回路構成の詳細はブロック７０−１の内
部に示されている。７１，…………，７５はＮＡＮＤゲ
ートである。

ＮＡＮＤゲートＴ４と７５とでセットリセットフＩＪッ
ブフロップ則ち記憶回路の一部を構成する。ＮＡＮＤゲ
ート７ １，７２，７３は駆動回路の一部であり、入力
信号Ｘ，，Ｘ２，Ｘ３の組合せを検知して、前記フリッ
プフロップを駆動する。Ｆ，，・……・・・・・，Ｆ６
は各ブロックに含まれるフリツプフロツプの出力信号で
あり、この組合せにより内部状態Ｓｏ，Ｓ，，・・・・
・・……，Ｓ，２を表わす。信号Ｆ，，・・・・・・…
・・・，Ｆ６のそれぞれは１つだけ１となるとき、それ
ぞれ第一のしベルの状態Ｓ，，・・・・・・・・・・・
・，Ｓ６に相当し、信号Ｆ，とＦ２，Ｆ２とＦ３，・・
・・・・・・・・・・，Ｆ６とＦ，のように２つの信号
の粗のみが１となるとき、第二のレベルの状態Ｓ７，…
………，Ｓ，２に相当する。８１，８２，８３，８４等
はＡＮＤゲ−トであり、上記のような信号Ｆ，，………
…，Ｆ６の組合せを検知し、内部状態Ｓ，，・・…・・
・・・・・，Ｓ，２を表わす状態信号Ｙ，，・・・・…
・・・・・，Ｙ，２を生成する。

７０１，７０６はブロック７０−１，７０一６の出力信
号線であり、信号線の援続関係を明示するために特に付
してある。

その他説明を省略した参照番号あるいは記号は第３図ａ
におけると同一のものである。本実施例の出力回路は第
３図ｂのものと全く同一である。一般に第２図で示した
ような状態遷移図から論理回路を導出する方法は幾通り
もあり、第３図および第４図の実施例はその一例を示す
ものである。

例えば上記実施例ではセットリセットフリップフロップ
が使用されているが「 これに同期信号を供給すること
あるいはこれをＯ型又はＪＫ型等のフリップフロップに
瞳替えること等は良く知られた技術で容易に実施できる
。

第５図は本発明による三入出力分類装置の動作をより分
り易く説明するための図である。

シフトレジスタ１１，１２，１３には３つの分類すべき
数値“６”、“５”、“３”が一例として記憶されてい
るものとする。

各数値は二進表示で右が上位ビットである。２０′は本
発明にある三入由力分類装置で、内部状態と３つの出力
信号が表示されている。

１１′，１２′，１３′はそれぞれシフトレジスタ１１
，１２，１３と同一のものであり、順序付けられて得ら
れた数値を明示するために特に分けて揺かれている。

したがって、１３′が一番大きな値として、次に１２′
，１１′の順に順序付けられ出力される。ａ，ｂ，……
…・．・，ｅ図の順で、各数値が上位から１ビットずつ
処理される様子が示されている。ａ図は動作の始めの状
態を示し、初期状態Ｓｏにある。

このとき入力信号（Ｘ，，Ｘ２，Ｘ３）＝（０、０、０
）を判定してその順序関係が決まらないためｂ図ではな
お初期状態Ｓｏにある。このとき次の入力信号（Ｘ，．
Ｘ２，Ｘ３）＝（１、１、０）により数値Ｘ３が最小と
判定されｃ図の状態Ｓ４へ移る。さらに次の入力信号（
Ｘ，，Ｘ２）＝（１、０）により数値Ｘ，とＸ２が判定
されｄ図の状態Ｓ，。へ移る。ここで数値Ｘ３＜Ｘ２＜
×，なる順序関係の全てが決定できた。なお出力信号は
以上の順序関係に応じて出力されている。以後はこの順
序関係が保たれたままシフトレジスタ１１，１２，１３
から残る全てのビットが出力されるまで動作が続けられ
る。結果はｅ図となる。ａ図とｅ図を対比して参照すれ
ば、その目的が正しく実行されたことが分かる。

以上の説明によれば、本発明による三入出力分類装置は
、複数個のセルの組合せによらず、単一のセルにて構成
されたことにより、内部での信号の遅延は問題でなく、
高速処理に通しその効果は大である。

また規則的に回路を構成することが可能で、集集化に薄
すことにおいてもその効果は大である。

【図面の簡単な説明】

第１図は三入出力分類装置および従来技術を説明するた
めのブロック図、第２図は本発明の原理を説明するため
の状態遷移図、第３図は本発明による三入出力分類装置
の一実施例を示す回路図で、ａはその駆動回路および記
憶回路の具体的構成を示す回路図、ｂはその出力回路の
具体的構成を示す回路図、第４図は駆動回路および記憶
回路の別の実施例を示す回路図、第５図は本発明の三入
出力分類装置の動作を説明するための図である。 図において、１１，１２，１３……シフトレジスタ、２
１，２２，２３・・・・・・二入出力分類セル、２４，
２５・・・・・・遅延回路、３０−１，・・・…．・・
…３０−６・・・・・・同一構成による駆動回路および
記憶回路の一部、３１，３２，・・・・・・・・・・・
・，３９・・…・ＮＡＮＤゲート、４ ０・・・…ＮＯ
Ｒゲート、４ １，４２，４３……インバ−夕、５０−
１，…………５０−３・・…・出力回路の一部、５１，
５５，５６，・・・・・・・・・・・・，６０・・・・
・・ＡＮＤゲート、５２，５３，５４……ＯＲゲート、
７０−１，…………７０−６・・…・駆動回路および記
憶回路の一部、７１，・・・・・・・・・・・・，７
５・・・・・・ＮＡＮＤゲート、８ １，８２，８３，
８４等・・・…ＡＮＤゲートである。 オー図才２図 才３図（ｏ） 才３図（ｂ） 才４図 汁５図

Claims (1)

【特許請求の範囲】
1. １ ３つの二進数値を上位ビツトから順次入力し、前記
   ３つの二進数値を大きさの順に並べ替えて出力する装置
   において、初期状態と第一のレベルの６つの状態と第二
   のレベルの６つの状態とから成る１３個の内部状態を区
   別して表わす記憶回路と、３本の入力信号線を有す駆動
   回路と、３本の出力信号線を有す出力回路とを備え、前
   記駆動回路は前記３本の入力信号線へ前記３つの二進数
   値の上位ビツトから順次入力される３つの入力信号の組
   合せを遂次判定し、前記記憶回路を駆動してその内部状
   態を、前記遂次判定の結果で前記３つの二進数値のいず
   れも順序が決まらないときは初期状態に留め、前記３つ
   の二進数値のいずれか１つの順位が決つたとき前記初期
   状態から第一のレベルの６つの状態のうちいずれか決め
   られた１つの状態へ遷移させ、さらにまだ順序の決まら
   ない残り２つの二進数値の順序が決まるまで第一のレベ
   ルの前記遷移された状態へ留め、前記残り２つの二進数
   値の順序が決つたとき第一のレベルの前記遷移された状
   態から第二のレベルの６つの状態のうちいずれか決めら
   れた状態へ遷移させて、前記記憶回路は前記遂次判定さ
   れた結果に従い順次分類される前記二進数値の順序関係
   を前記１３個の内部状態のそれぞれで区別して記憶し、
   前記出力回路は前記分類された順序関係に従つて前記３
   つの入力信号を並べ替えてそれぞれ予じめ決められた順
   序に対応する前記３本の出力信号線へ出力することを特
   徴とする三入出力分類装置。