JPH01150930A - データ並べ替え回路 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 ［産業上の利用分野］ 本発明はデータの並べ替え回路、特に時々刻々と入力さ
れるデータを小規模なハードウェアにより実時間で並べ
替えを行なう回路に関するものである。

［従来の技術］ 従来多くのデータをある一定の順序に並べ替えるソータ
は、並べ替える必要のある全データを並列に一括して処
理するもので、−膜内にはパイトニック（双単調）ソー
タと呼ばれている。

バイトニックソータは一方が上昇順で他方が下降順の２
つの単調な数列をつないで１つの単調な数列を得るのに
効率良く実行する手法である。

いまｎｓｗ　２　Ｎ個のランダムに並んだ数列を単調に
するためには、次の様な手順で行なう。先ず２個の数を
それぞれのグループとしてまとめ、この２個の数値間で
はいずれも昇順あるいは降順に並べかえた数を出力する
ようにする。するとｎ／２個の出力の数が得られる。こ
のｎ　／　２個の数を２個づつまとめて新たなｎ　／　
４個の組を作る。この各組の入力は前段で昇順又は降順
に整列された数が入力される。この入力がパイトニック
である。

こうして得られたｎ　／　４組の昇順又は降順の出力を
さらに２個づつまとめてｎ　／　８個の組を作るという
手順を繰返すことによって最終的に２組の数列が得られ
る。これがパイトニックであり、これをマージして一つ
の単調な数列を得ることができる。

バイトニックソータとしてはバチャー（Ｂａｔｃｈｅｒ
１９Ｂｇ）のソータ網が有名であり、例えば１９８６年
１月共立出井守行のｂｔｔ別冊「並列ソート算法の分類
」第９６頁に詳細が記載されている。

入力数ｎに対してはｌｏｇ　２ｎ個のステージで大小比
較と交換を必要とするからｎが大きくなると急激にハー
ドウェアは大規模となっている。

［発明が解決しようとする問題点］ しかしながら従来のバイトニックソータは対象とする全
データに対して並列に演算を行なうので、データ数が多
くなると入出力端子数が増大し、またハードウェアが大
規模となり、実用的な機器になりにくいという問題点が
あった。

本発明は以上述べた入出力端子数の増大とハードウェア
の大規模化を抑圧した実用的な機器となりうるデータ並
べ替え回路を提供することを目的とする。

［問題点を解決するための手段］ この発明は先ず直交シフトレジスタを設けて、入力され
るフレームに多重化されたデータから直交シフトレジス
タの一装置に相当する数のデータを順次採り出し、この
−列置のデータをソータにより昇順もしくは降順に並べ
替える。即ち列方向にあらかじめ整列した数列を作る。

この列方向に整列された数列データを前記直交シフトレ
ジスタの列データとして逐次入力し、この直交シフトレ
ジスタがデータで満ちたときに、次は各列データの一方
の縁にある行方向のデータを相互に比較しその中の最小
値又は最大値のデータを選択するという、２段階の並べ
替えと選択手段とを設けたものである。

［作　用］ この発明は対象とする全データを並列に処理するのでは
なく、直交シフトレジスタを利用したことにより、列方
向にあらかじめ昇順又は降順に整列した数列を作り、こ
の列方向に整列されたデータを今度は行方向に比較選択
するという２段階の演算処理を経てデータの並べ替えが
可能となった。

したがって前記問題点を除去することができる。

［実施例］ 第１図はこの発明の実施例を示すブロック図であり、１
は入力バッファで例えばシフトレジスタより構成される
。２は入力用ソータで例えば従来技術であるバイトニッ
クソータである。３は直交シフトレジスタで横方向（行
）と縦方向（列）の両方向へのデータシフトが可能であ
る。この直交シフトレジスタ３は特に縦方向のシフトは
指定した列のみをシフトさせる選択性のシフトが可能で
ある。４は出力選択回路であり、この出力選択回路４−
は直交シフトレジスタ３の最下端の行から最大値又は最
小値のデータを選択取り出し出力バッファ５に出力し、
同時に直交シフトレジスタ３にデー夕を取り出した列を
通知する。５は出力バッファであり、例えばシフトレジ
スタより構成される。この出力バッファ５より昇順又は
降順のデータが出力される。

第２図はこの発明に使用するデータの入出カフオーマッ
ト説明図であり、１フレームにＤｏ〜Ｄ８−１の８個の
固定長データが多重化されており、各多重化されたデー
タはヘッダ部分として１ビツトの使用もしくは不使用の
表示ビットと、ｎビットから成るソートキーデータを含
み、さらにｍビットから成る付加データを有する。この
発明の説明を容易にするために、最初は１フレーム内の
データ数Ｓは直交シフトレジスタ３の記憶容量（即ち行
数と列数の積）と等しい場合を考える。

一般に、この直交シフトレジスタ３の行数と列数は２の
零敗から選定される場合が多い。この例ではこの行数を
列数の積をデータ数Ｓとした。

第３図はこの１フレーム内のデータ数Ｓと直交シフトレ
ジスタ３の行数及び列数の対応図を示す。

例えばデータ数Ｓが２５６の場合は行数及び列数ともに
１６である。ここでＩＫは１０２４である。

また直交シフトレジスタ３は２面構造となっており、現
在のフレーム周期のデータをその一面に書込み中に、並
列して他の一面から１つ前のフレーム周期のデータが読
み出せるようになっている。入力バッファ１は直交シフ
トレジスタ３の１列分のデータの記憶容量をもつ。この
人力バッファ１へのデータ入力形式は任意である。例え
ば、ビットシリアル、バイトシリアル、全データパラレ
ル等のいずれの形式でも入力バッファ１にデータを入力
することができる。

人力用ソータ２は人カバッファエから入力されたデータ
のソーティングを行なう。即ち入力されたデータを昇順
もしくは降順に並べ替えるのであるが、この並べ替えの
演算処理は各データのヘッダ部に含まれるデータである
使用又は不使用の表示ビットとソートキーの値を判断基
準として行われる。入力用ソータ２がバイトニックソー
タの場合、ソーティング素子は２人力２出力のβ素子で
例えばデータ入力線Ａ、Ｂをもち、入力データを比較し
て出力線りから小さい方のデータを、出力線Ｈから大き
い方のデータを出力する比較交換器である。そしてこの
データ入出力間の通路をヘッダ部のデータだけではな°
く、付加データも通過するようにすると、１個分のデー
タ数がｎ＋１＋ｍビットである固定長データはｎ＋１ビ
ットのヘッダ部のデータの並べ替えたとほぼ同時に１個
分のデータ全部の並べ替えも終了する。

いま直交シフトレジスタ３のデータ記憶容量（即ち１フ
レーム内のデータ数Ｓ）を２５６として第１図の回路動
作を説明する。第３図を参照してデータ数Ｓが２５６の
場合の１列分のデータは１６個なので入力バッファ１は
データ１６個分の容量でよい。いま人力バッファ１が入
力データを順次シフトインして１６個のデータを入力し
終えると、直ちにこのデータを入力用ソータ２に送出し
、１７番目のデータが入力される前にデータ送出を完了
する。

入力用ソータ２は次の１６個のデータが入力バッファ１
に蓄えられるまでにソーティングを終了し、ソーティン
グ後のデータを直交シフトレジスタ３に出力すればよい
。入力用ソータ２が入力バッファ１からデータを受理す
る最も簡単な方法は、入力ソータ２の入口に入カバッフ
ァエのデータをそのままコピーできるレジスタを設けれ
ばよい。

入力用ソータ２が入カバッファエより入力された１６個
のデータを昇順もしくは降順のいずれかに並べ替えるデ
ータの演算動作は一般のバイトニックソータで実現する
ことが容易である。またこのバイトニックソータでは直
列データあるいは並列データのいずれでもソーティング
が可能であり、入力されたデータ（本例の場合１６個の
データ）を並列に処理できるので並べ替えは短時間で終
了する。入力用ソータ２はソーティングを終了すると直
交レジスタ３の最左端の一列にデータを送出する。直交
シフトレジスタ３はこのようにあらかじめ列方向に整列
されたデータを最左端の列から入力し、このデータを順
次右側にシフトインし、本例の場合１６回入力すると、
２５６個データが蓄積され、片面はデータで満ちた状態
となる。この状態において各列のデータは、使用又は不
使用ビットを含むソートキーの値即ちヘッダの値を基準
にして昇順か降順かに並んでいるわけである。昇順か降
順かは入力用ソータの作り方で決まる。もし入力用ソー
タ２が昇順であれば、直交シフトレジスタ３の最下段の
行は各入力列のうちヘッダ値の最小のデータが集まって
いる。当然２５６個の全データのうち最小のヘッダ値も
この１６列のなかのいずれかの列に含まれているはずで
ある。

出力選択回路４は直交マトリック３の最下段の行のデー
タのヘッダ値を読み出し最小値のデータを選択する。出
力選択回路４は最少値のデータを選択すると出力バッフ
ァ５が空いているかをチエツクし、もし空いていればこ
のデータを出力バッファ５に送出する。同時に直交シフ
トレジスタ３に選択した列の情報を通知する。この通知
は選択されなかった列にアウトプットサプレス信号を送
出し、このアウトプットサプレス信号を受信しなかった
列のみが１データ分下方に列シフトする。

出力バッファ５は最小１個分のデータ容量があればよい
が、複数個のデータ容量をもち順次シフトしてデータを
出力してもよい。当然出力バッファ５から最初に出力さ
れるデータは２５８個のデータのうちヘッダ値の最小の
データとなる。

第４図は前記アウトプットサプレス信号の伝達説明図で
ある。同図において、ＩＯは４個のデータ（０，２，１
，３）の出力部、ｌｌａ、ｌｌｂは第１ステージ最小値
選択用素子（例えばβ素子）　、ｌｉｅは第２ステージ
最小値選択用素子である。そして４人力のデータから最
小値のデータを選択し、選択されないデータにアウトプ
ットサプレス信号を伝達する通路（バス）を示している
。第１ステージでは２組の入力データ＜０．２＞と（１
、３）を各々比較し、それぞれ小さい方のデータ（０，
２）では０、（１，３）では１が選択され、選択されな
かった方に記号Ｓ１で示されるアウトプットサプレス信
号が返送される。第２ステージでは入力された２つの信
号（０，１）のうち小さい方のデータ０が選択され、選
択されなかった方に記号Ｓ２で示されるアウトプットサ
プレス信号が、それまでデータが通ってきたバスを通じ
て、反対方向に返送される。従ってすべての処理が終了
した一定時間経過後に、アウトプットサプレス信号の返
送されない列は１データ分だけ下方にシストし、この時
上部よりこの系の最大値である無効情報を入力する。こ
の１列分の下方シフトが終了した状態で出力選択回路４
は再び最下段の行のデータのヘッダの値を比較し、次の
最小の値をもったヘッダ値を選択する。この選択された
ヘッダ値は２５６個のデータの中で２番目に最も小さな
ヘッダ値のはずである。以下この動作を繰返せば１フレ
ーム内に入力された固定長データはヘッダ値の小さなも
のから順次出力することができる。直交シフトレジスタ
３が２面構造となっているので、このようにして１面の
データの読出し出力を行なっている間に、他の１面へデ
ータの書込みを並列的に行なうことができる。

従って一つの面へのデータの書込みが完了するまでに、
他の面からデータの読出し出力が完了していればよい。

また最初説明を容易にするため直交シフトレジスタ３の
容量（行数をｍ列数をｎとすると積ｍｎ）と１フレーム
内のデータ数Ｓとを等しくするとしたが、必ずしも等し
くなくてＳ≦ｍｘｎでもよい。

但しＳ＜ｍＸｎの場合は、最後のデータは入カバッファ
エのなかでは無効なｋ　（ｋ−ｍＸｎ−８）個のデータ
と同居することになる。従って本例の場合はこのに個の
データを無効データとするため、その系の扱う最大値に
設定する必要がある。そのため人力バッファ１に最大値
または最小値の初期設定機能を設ける必要がある。

ヘッダ部に含まれる１ビツトの使用又は不使用情報の使
い方は、例えば直交シフトレジスタ３が１個分のデータ
を出力し、このデータが存在する列を下方にシフトする
ときに、該当月の上部より挿入する無効情報にこのビッ
ト情報を付加して識別用に使用する。またフレーム内に
多重化されているデータは全部が有効情報とは限ず無効
情報も含まれるので、この無効情報の識別符号として利
用する等の使用法がある。

なお、本回路は昇順のソータとしても、降順のソータと
しても用いつる。昇順ソータの場合は、入力用ソータ２
を昇順として、出力選択回路４は最小値を選択する。そ
して直交シフトレジスタ３の列方向シフト時に上から系
の最大値又は無効データを入力する。降順ソータの場合
は、入力用ソータ２は降順として、出力選択回路４は最
大値を選択する。そして直交シフトレジスタ３の列方向
シフト時に上から系の最小値又は無効データを入力する
。

第５図は本発明の他の実施例を示すブロック図である。

同図において、２０は入力分配回路、２１、・・・２１
　　．２１Ｎはソータ、２２は出力用ソータ、２３は出
力用バッファである。入力分配回路２０は入力信号をソ
ータ２１　〜２１Ｎにそれぞれ分配して送出する。ソー
タ２１　〜２１Ｎは第１図のデータ並べ替え回路の全部
を含むものである。即ち入力バッファ１、入力用ソータ
２、直交シフトレジスタ３、出力選択回路４、出力バッ
ファ５を含むものである。従ってソータ２１　〜２１Ｎ
は入力分配回路２０より入力されたデータを逐次昇順又
は降順に並べ替え、内蔵する出力バッファ５にデータを
準備する。

出力用ソータ２２はソータ２１１〜２゛ＩＮのそれぞれ
に内蔵された出力バッファ５のデータを比較し、この中
から最大値又は最小値のデータを選択して、このデータ
を出力用バッファ２３に送出する。同時に出力用ソータ
２２は選択されなかったデータを出力したソータに対し
てアウトプットサプレス信号を返送する。アウトプット
サプレス信号を返送されたソータはその内蔵する出力バ
ッファ５のデータを保持し、返送されなかったソータは
次の整列されたデータを出力バッファ５に出力する。以
下同様の動作を繰り返して多量のデータの並べ替えを並
列的に処理することができる。この回路への入力信号は
ビットシリアル、バイトシリアル、ワードシリアル等の
いずれでも可能な回路とすることができる。第５図にお
いてソータ２１　〜２１Ｎを並列に使用する特徴は、１
フレーム内のデータ数が非常に多くなった場合に、第１
図の回路では直交シフトレジスタ３の容量が過大となり
、直交シフトレジスタ３のＬＳＩ化が困難となる。その
ためこの直交シフトレジスタ３の容量を分割して、それ
ぞれのソータ内に含まれるようにすれば容易にＬＳＩ化
が可能となり、回路設計並びに機器実装上の利点が大き
い。

［発明の効果］ 以上説明したように本発明によれば、対象とするデータ
を先ず直交シフトレジスタの列方向に整列したデータと
して入力し、次にこの列方向に整列されたデータを行方
向に比較選択するという２段階の演算処理を行なうこと
により、従来装置に比較し、少い端子数と小規模な回路
でデータ並べ替え回路を実現することができ、回路のＬ
ＳＩ化も可能となり、装置の小形化と経済性に貢献でき
る。

【図面の簡単な説明】

第１図は本発明に係るデータ並べ替え回路ブロック図、
第２図はデータ入出カフオーマット説明図、第３図はデ
ータ数と行数及び列数との対応図、第４図はアウトプッ
トサプレス信号の伝達説明図、第５図は本発明に係る他
の実施例のブロック図である。 図において、１は入力バッファ、２は入力用ソータ、３
は直交シフトレジスタ、４は出力選択回路、５は出力バ
ッファ、ｌＯはデータ出力部、１１ａ、ｌｌｂは第１ス
テージ最小値選択用素子、ｌｉｅは第２ステージ最小値
選択用素子、２０は入力分配回路、２１□〜２１Ｎはソ
ータ、２２は出力用ソータ、２３は出力用バッファであ
る。 第４囚 第５図

Claims (1)

1. 【特許請求の範囲】 フレーム内に多重化され一定形式のヘッダ部を有する固
   定長データを連続入力し、前記ヘッダ部のデータによっ
   て昇順あるいは降順に並べ替えて出力する装置において
   、 １フレーム内のデータ数かもしくはそれ以上のデータ記
   憶容量を２面分有し、１列分のデータ毎にデータを順次
   シフトインし、選択された列の縁から１データ分をシフ
   トアウトする直交シフトレジスタと、 前記直交シフトレジスタの一列分に相当する数のデータ
   を順次入力し、この入力されたデータをそのヘッダ部の
   データにより昇順もしくは降順に並べ替えて出力し、前
   記直交シフトレジスタへ１列づつデータをシフトインす
   る入力用ソータ部と、前記直交シフトレジスタへ入力さ
   れた各列の一方の縁に位置するデータをそのヘッダ部の
   データにより比較し、その中の最小値もしくは最大値の
   データを有する列を選択し、この直交シフトレジスタの
   選択された列のデータを前記一方の縁方向に１データ分
   シフトし、前記最小値もしくは最大値のデータを採り出
   し出力すると同時に、他方の縁から無効データをシフト
   インするデータ選択出力部とを備えたことを特徴とする
   データ並べ替え回路。