JPH0588848A - データの並べ変え装置 - Google Patents
データの並べ変え装置Info
- Publication number
- JPH0588848A JPH0588848A JP8318191A JP8318191A JPH0588848A JP H0588848 A JPH0588848 A JP H0588848A JP 8318191 A JP8318191 A JP 8318191A JP 8318191 A JP8318191 A JP 8318191A JP H0588848 A JPH0588848 A JP H0588848A
- Authority
- JP
- Japan
- Prior art keywords
- data
- registers
- register
- order
- circuit
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Withdrawn
Links
Landscapes
- Compression, Expansion, Code Conversion, And Decoders (AREA)
- Error Detection And Correction (AREA)
Abstract
(57)【要約】
【目的】 高速にデータのソーティングを行うことがで
き、全体の処理速度を向上させるデータソーティング装
置を提供すること。 【構成】 入力するｎビットのデータをデコードしてデ
ータに対応する信号を出力し、この信号を受けて対応す
るレジスタの値を１づつインクリメントする順序付けが
なされた２n 個のレジスタを備えｎビットの入力データ
を２n 個のレジスタの順序に対応するよう並べ変える。
き、全体の処理速度を向上させるデータソーティング装
置を提供すること。 【構成】 入力するｎビットのデータをデコードしてデ
ータに対応する信号を出力し、この信号を受けて対応す
るレジスタの値を１づつインクリメントする順序付けが
なされた２n 個のレジスタを備えｎビットの入力データ
を２n 個のレジスタの順序に対応するよう並べ変える。
Description
【０００１】
【産業上の利用分野】本発明は、例えば中央処理装置
（ＣＰＵ）から送られて来る情報（データ）を降順若し
くは昇順、又はその他の希望する順序に並べ変えるため
の装置に関するものである。
（ＣＰＵ）から送られて来る情報（データ）を降順若し
くは昇順、又はその他の希望する順序に並べ変えるため
の装置に関するものである。
【０００２】
【従来の技術】図３は従来のディジタル信号処理回路に
おいてデータの並べ変え処理を行う回路の概念を簡単に
示したブロック図である。ここで汎用メモリ３２に記憶
されたデータの並べ変え（ソーティング）を行う場合に
は、まずＣＰＵ３０によってメモリ３２からデータを読
み出す。ＣＰＵ３０は内部の演算回路によってこれらの
データに対し大小比較の演算を行った後、再びメモリ３
２の対応するアドレスに記憶する。このようにして記憶
し直したデータはメモリ３２のアドレスの順番に沿っ
て、例えば降順や昇順などの所定の順序となっている。
したがって、このメモリ３２からアドレス順にデータを
読み出せば、上記所定順序の一連のデータが得られる。
おいてデータの並べ変え処理を行う回路の概念を簡単に
示したブロック図である。ここで汎用メモリ３２に記憶
されたデータの並べ変え（ソーティング）を行う場合に
は、まずＣＰＵ３０によってメモリ３２からデータを読
み出す。ＣＰＵ３０は内部の演算回路によってこれらの
データに対し大小比較の演算を行った後、再びメモリ３
２の対応するアドレスに記憶する。このようにして記憶
し直したデータはメモリ３２のアドレスの順番に沿っ
て、例えば降順や昇順などの所定の順序となっている。
したがって、このメモリ３２からアドレス順にデータを
読み出せば、上記所定順序の一連のデータが得られる。
【０００３】
【発明が解決しようとする課題】従来の方式によるデー
タの並べ変え処理は、ＣＰＵ内の演算回路を用いてソフ
トウエア的に行うので、ハードウエア的な処理に較べて
処理速度が遅い。更に、並べ変え処理の際にＣＰＵを使
用する必要があるので、この処理を行っている期間中は
ＣＰＵを他の処理に使用することができず、全体の処理
時間が遅延するという問題があった。
タの並べ変え処理は、ＣＰＵ内の演算回路を用いてソフ
トウエア的に行うので、ハードウエア的な処理に較べて
処理速度が遅い。更に、並べ変え処理の際にＣＰＵを使
用する必要があるので、この処理を行っている期間中は
ＣＰＵを他の処理に使用することができず、全体の処理
時間が遅延するという問題があった。
【０００４】本発明は上記事情に基づいてなされたもの
であり、ＣＰＵを用いずに、しかも高速にデータの並べ
変えを行うことができ、これにより全体の処理速度を向
上させることができるデータの並べ変え装置を提供する
ことを目的とするものである。
であり、ＣＰＵを用いずに、しかも高速にデータの並べ
変えを行うことができ、これにより全体の処理速度を向
上させることができるデータの並べ変え装置を提供する
ことを目的とするものである。
【０００５】
【課題を解決するための手段】上記の目的を達成するた
めの本発明は、コード化された状態で受けたｎビット
（ｎは正の整数）の情報のコードをデコードするための
デコード手段と、このデコード手段からの信号を受ける
ことにより、対応する値を１づつ増加するための順序付
けがなされた２n 個のレジスタ手段とを具備し、前記ｎ
ビットの入力データを前記２n 個のレジスタの順序に対
応するよう並べ変えることを特徴とするものである。
めの本発明は、コード化された状態で受けたｎビット
（ｎは正の整数）の情報のコードをデコードするための
デコード手段と、このデコード手段からの信号を受ける
ことにより、対応する値を１づつ増加するための順序付
けがなされた２n 個のレジスタ手段とを具備し、前記ｎ
ビットの入力データを前記２n 個のレジスタの順序に対
応するよう並べ変えることを特徴とするものである。
【０００６】
【作用】本発明は前記の構成によって次のような作用を
奏する。例えばＣＰＵからデータを供給する場合、その
データがｎビットであるとすればデータの種類は２n 個
に限られる。このデータをデコード手段に与えるとデコ
ード手段はデータをデコードしてその値に応じた信号を
２n 個のレジスタに供する。この２n 個のレジスタは、
データをソーティングすべき順序にレジスタを予め配列
してあり、デコード手段からの信号がこの中の対応する
レジスタに与えられるとそのレジスタは対応する値を１
づつ増加する。このような動作を、連続的に供給される
データに対して逐次行うことにより、結果的に２n 個の
レジスタはそれぞれの値が入力された回数を計数しこの
回数を格納する。このような動作が終了したときの上記
２n 個のレジスタの順序及びこれらに記憶された回数の
値はソーティングされた一連のデータに対応する。上記
のように本発明ではデータのソーティングに関してＣＰ
Ｕは関与しないため、データのソーティングを行ってい
る期間中であってもＣＰＵを別の処理に使用することが
できる。
奏する。例えばＣＰＵからデータを供給する場合、その
データがｎビットであるとすればデータの種類は２n 個
に限られる。このデータをデコード手段に与えるとデコ
ード手段はデータをデコードしてその値に応じた信号を
２n 個のレジスタに供する。この２n 個のレジスタは、
データをソーティングすべき順序にレジスタを予め配列
してあり、デコード手段からの信号がこの中の対応する
レジスタに与えられるとそのレジスタは対応する値を１
づつ増加する。このような動作を、連続的に供給される
データに対して逐次行うことにより、結果的に２n 個の
レジスタはそれぞれの値が入力された回数を計数しこの
回数を格納する。このような動作が終了したときの上記
２n 個のレジスタの順序及びこれらに記憶された回数の
値はソーティングされた一連のデータに対応する。上記
のように本発明ではデータのソーティングに関してＣＰ
Ｕは関与しないため、データのソーティングを行ってい
る期間中であってもＣＰＵを別の処理に使用することが
できる。
【０００７】
【実施例】以下に図面を参照しつつ本発明の一実施例に
ついて説明する。図１は本発明の一実施例であるデータ
ソーティング装置の概略ブロック図である。同図におい
て、デコード回路デコード手段１０には、図示しないＣ
ＰＵからｎビットのコード化されたデータが供給され
る。データがｎビットの場合にはそのデータの値は２n
種類あるので、これに対応させてデコード回路１０の後
段には２n 個のクロック発生回路１２が設けてありデコ
ード回路１０に入力されるデータの値に対応させてあ
る。更に、クロック発生回路１２の後段には２n 個のレ
ジスタ（レジスタ手段）１４が設けられ、このレジスタ
１４内の各レジスタのそれぞれは２n 個のクロック発生
回路１２のそれぞれと対応させてある。そして、レジス
タ１４内の各レジスタの順番は、あらかじめ例えば昇順
（小さい値から順に並べる）又は降順（大きい値から順
に並べる）に順序付けがなされて配置されている。
ついて説明する。図１は本発明の一実施例であるデータ
ソーティング装置の概略ブロック図である。同図におい
て、デコード回路デコード手段１０には、図示しないＣ
ＰＵからｎビットのコード化されたデータが供給され
る。データがｎビットの場合にはそのデータの値は２n
種類あるので、これに対応させてデコード回路１０の後
段には２n 個のクロック発生回路１２が設けてありデコ
ード回路１０に入力されるデータの値に対応させてあ
る。更に、クロック発生回路１２の後段には２n 個のレ
ジスタ（レジスタ手段）１４が設けられ、このレジスタ
１４内の各レジスタのそれぞれは２n 個のクロック発生
回路１２のそれぞれと対応させてある。そして、レジス
タ１４内の各レジスタの順番は、あらかじめ例えば昇順
（小さい値から順に並べる）又は降順（大きい値から順
に並べる）に順序付けがなされて配置されている。
【０００８】デコード回路１０にデータが供給されその
値がデコードされると、デコード回路１０はそのデコー
ドされたデータ値に対応するクロック発生回路１２から
クロックパルスを発生させる。そのクロックパルスは２
n 個のレジスタ１４の中の対応するレジスタに与えら
れ、このレジスタの値を１だけインクリメント（増加）
する。このような動作をデコード回路１０に供給される
全てのデータに対して逐次行うことにより、２n 個のレ
ジスタ回路１４には全てのデータのうちそれぞれの値が
何回現れたかという回数が格納されることになる。した
がって、この２n 個のレジスタを順番にそこに格納され
た値の回数だけ読み出すことにより、所定の順序に並べ
変えられた一連のデータが得られる。
値がデコードされると、デコード回路１０はそのデコー
ドされたデータ値に対応するクロック発生回路１２から
クロックパルスを発生させる。そのクロックパルスは２
n 個のレジスタ１４の中の対応するレジスタに与えら
れ、このレジスタの値を１だけインクリメント（増加）
する。このような動作をデコード回路１０に供給される
全てのデータに対して逐次行うことにより、２n 個のレ
ジスタ回路１４には全てのデータのうちそれぞれの値が
何回現れたかという回数が格納されることになる。した
がって、この２n 個のレジスタを順番にそこに格納され
た値の回数だけ読み出すことにより、所定の順序に並べ
変えられた一連のデータが得られる。
【０００９】上記の説明から分かるように、２n 個のレ
ジスタ全体で必要とされる記憶容量は、データの数が多
くなるに従って、データそのものを記憶するために必要
とされる記憶容量よりも小さくなり、メモリを節約でき
る。
ジスタ全体で必要とされる記憶容量は、データの数が多
くなるに従って、データそのものを記憶するために必要
とされる記憶容量よりも小さくなり、メモリを節約でき
る。
【００１０】具体的な例として図２に示すように８ビッ
トのデータを昇順に並べ変えする場合を考える。この場
合データの値は全部で２8 ＝２５６種類なので、デコー
ド回路１０の後段には２５６個のクロック発生回路が設
けられる。また、これに対応して設けられるレジスタも
２５６個であり、それぞれのレジスタは８ビットである
とする。すなわち、各レジスタはクロックパルスを２５
５個までカウントできる。例えばデコード回路１０に入
力されたデータが（００００１１１１）であったとする
と、この値はデコード回路１０によりデコードされて１
６番目のクロック発生回路からレジスタ回路１４に向け
てクロックパルスが発生する。このクロックパルスは対
応する１６番目のレジスタに入力され、その値を１だけ
インクリメント（増加）する。以下同様の動作が全ての
データに対して繰り返される。
トのデータを昇順に並べ変えする場合を考える。この場
合データの値は全部で２8 ＝２５６種類なので、デコー
ド回路１０の後段には２５６個のクロック発生回路が設
けられる。また、これに対応して設けられるレジスタも
２５６個であり、それぞれのレジスタは８ビットである
とする。すなわち、各レジスタはクロックパルスを２５
５個までカウントできる。例えばデコード回路１０に入
力されたデータが（００００１１１１）であったとする
と、この値はデコード回路１０によりデコードされて１
６番目のクロック発生回路からレジスタ回路１４に向け
てクロックパルスが発生する。このクロックパルスは対
応する１６番目のレジスタに入力され、その値を１だけ
インクリメント（増加）する。以下同様の動作が全ての
データに対して繰り返される。
【００１１】それぞれのデータの出現回数が格納された
２n 個のレジスタから並べ変えされたデータを読み出す
具体的な方法としては、ＣＰＵからの指令によって逐次
データを読み出すようにしてもよいし、または回路的に
次々とデータを読み出すような構成としてもよい。後者
の場合には、それぞれのデータの値を格納しておく別の
レジスタが必要となるが、読み出しの速度はＣＰＵを用
いてソフトウエア的に読み出す場合よりも一段と高速に
なる。このとき、昇順にソーティングしたデータを逆の
順番で読み出せば、降順とされた一連のデータも簡単に
得ることができる。
２n 個のレジスタから並べ変えされたデータを読み出す
具体的な方法としては、ＣＰＵからの指令によって逐次
データを読み出すようにしてもよいし、または回路的に
次々とデータを読み出すような構成としてもよい。後者
の場合には、それぞれのデータの値を格納しておく別の
レジスタが必要となるが、読み出しの速度はＣＰＵを用
いてソフトウエア的に読み出す場合よりも一段と高速に
なる。このとき、昇順にソーティングしたデータを逆の
順番で読み出せば、降順とされた一連のデータも簡単に
得ることができる。
【００１２】通常のディジタルデータは、データそのも
のの部分とデータの属性などを示すキーなどと呼ばれる
部分からなっていることが多い。この場合このキー部分
を対象にしてソーティングを行う場合にも本発明のデー
タソーティング装置を適用することができる。
のの部分とデータの属性などを示すキーなどと呼ばれる
部分からなっていることが多い。この場合このキー部分
を対象にしてソーティングを行う場合にも本発明のデー
タソーティング装置を適用することができる。
【００１３】図１に示す本実施例の回路を図３に示す従
来の回路に対応させると、デコーダ１０から２n 個のク
ロック発生回路１２及びレジスタ回路１４が汎用メモリ
３０に該当する。しかし、本実施例の回路の場合には実
際のメモリを使用している訳ではないのでアドレス信号
は必要としない。しいて言えばＣＰＵから与えられるデ
ータそのものがアドレス信号の役割も果たすと見ること
ができる。したがって、回路全体の動作が簡単になる。
またＣＰＵ３０から一旦データをデコード回路１０へ送
ると、比較演算を行うために再びデータを読み出してＣ
ＰＵに戻すような操作は必要でないので、従来、比較演
算を行うためにＣＰＵが占有されていた時間を別の処理
に使うことができるとともに、比較を行う演算回路も不
要となる。また実施例で示したようにデータのソーティ
ング処理は純粋にハードウエア的に行われるので、処理
速度が向上する。このようなことからソーティング処理
を含めた全体の処理時間を短縮することができる。
来の回路に対応させると、デコーダ１０から２n 個のク
ロック発生回路１２及びレジスタ回路１４が汎用メモリ
３０に該当する。しかし、本実施例の回路の場合には実
際のメモリを使用している訳ではないのでアドレス信号
は必要としない。しいて言えばＣＰＵから与えられるデ
ータそのものがアドレス信号の役割も果たすと見ること
ができる。したがって、回路全体の動作が簡単になる。
またＣＰＵ３０から一旦データをデコード回路１０へ送
ると、比較演算を行うために再びデータを読み出してＣ
ＰＵに戻すような操作は必要でないので、従来、比較演
算を行うためにＣＰＵが占有されていた時間を別の処理
に使うことができるとともに、比較を行う演算回路も不
要となる。また実施例で示したようにデータのソーティ
ング処理は純粋にハードウエア的に行われるので、処理
速度が向上する。このようなことからソーティング処理
を含めた全体の処理時間を短縮することができる。
【００１４】
【発明の効果】以上説明したように本発明によれば、Ｃ
ＰＵなどからメモリにデータを送った後、再びデータを
メモリから読み出してＣＰＵ内で比較処理を行うという
手続は不要となり、一旦ＣＰＵから送出されたデータは
自動的に所定順序にソーティングされて格納される。し
たがって従来、比較演算のためにＣＰＵを占有せざるを
えなかった時間を他の処理に振り向けることができ、し
かもデコード手段とレジスタとの組合せによってハード
ウエア的な処理を行うことにより、全体の処理速度が大
幅に向上するデータの並べ変え装置を提供することがで
きる。
ＰＵなどからメモリにデータを送った後、再びデータを
メモリから読み出してＣＰＵ内で比較処理を行うという
手続は不要となり、一旦ＣＰＵから送出されたデータは
自動的に所定順序にソーティングされて格納される。し
たがって従来、比較演算のためにＣＰＵを占有せざるを
えなかった時間を他の処理に振り向けることができ、し
かもデコード手段とレジスタとの組合せによってハード
ウエア的な処理を行うことにより、全体の処理速度が大
幅に向上するデータの並べ変え装置を提供することがで
きる。
【図１】本発明の一実施例である装置のブロック図。
【図２】図１の実施例を８ビットのデータに対応させた
場合のブロック図。
場合のブロック図。
【図３】従来の装置を説明するためのブロック図。
１０ デコード手段 １２ クロック発生回路 １４ レジスタ手段
Claims (1)
- 【請求項１】 コード化された状態で受けたｎビット
（ｎは正の整数）の情報のコードをデコードするための
デコード手段と、 このデコード手段からの信号を受けることにより、対応
する値を１づつ増加するための順序付けがなされて配置
されてなる２n 個のレジスタ手段とを具備し、 前記ｎビットの入力データを前記２n 個のレジスタによ
ってそのレジスタの順序配置に対応して並べ変えること
を特徴とするデータの並べ変え装置。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP8318191A JPH0588848A (ja) | 1991-03-20 | 1991-03-20 | データの並べ変え装置 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP8318191A JPH0588848A (ja) | 1991-03-20 | 1991-03-20 | データの並べ変え装置 |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| JPH0588848A true JPH0588848A (ja) | 1993-04-09 |
Family
ID=13795137
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP8318191A Withdrawn JPH0588848A (ja) | 1991-03-20 | 1991-03-20 | データの並べ変え装置 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JPH0588848A (ja) |
-
1991
- 1991-03-20 JP JP8318191A patent/JPH0588848A/ja not_active Withdrawn
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US3675211A (en) | Data compaction using modified variable-length coding | |
| RU2117388C1 (ru) | Способ и устройство кодирования и декодирования данных | |
| US8166278B2 (en) | Hashing and serial decoding techniques | |
| JPS5958558A (ja) | 並列周期的冗長チエツク回路 | |
| JP3188467B2 (ja) | 最小値・最大値検索装置 | |
| US6332152B1 (en) | Arithmetic unit and data processing unit | |
| US4595995A (en) | Sort circuit and method using multiple parallel sorts of the sorted items | |
| JPH05276052A (ja) | ハフマンコードワードをデコードする方法及び装置 | |
| US4760461A (en) | Binary data compression and expansion processing apparatus | |
| JPH0479421A (ja) | 可変長符号化装置および可変長復号化装置 | |
| JP2000261674A (ja) | 画像伸長装置 | |
| JPS603657B2 (ja) | フアーストイン・フアーストアウト記憶装置 | |
| JP2752634B2 (ja) | ソート処理装置 | |
| JPH0666050B2 (ja) | ソート処理方法 | |
| JPH0588848A (ja) | データの並べ変え装置 | |
| JPH09246990A (ja) | 可変長符号復号化器 | |
| JP2003174365A (ja) | 復号化装置及びその方法 | |
| US5822770A (en) | Memory interfacing method and circuit of variable length decoder for accessing external memory when empty portion of internal memory exceeds a predetermined level | |
| JP3229690B2 (ja) | 可変長符号復号器 | |
| JP3087488B2 (ja) | データ復元回路 | |
| US5479165A (en) | Two-dimensional coding apparatus | |
| JPH0779247B2 (ja) | デコ−ド回路 | |
| JP3088785B2 (ja) | 可変長符号の復号装置 | |
| JPH0918352A (ja) | 並列入力／直列出力装置および並列入力／直列出力方法 | |
| KR100247062B1 (ko) | 링구조를 갖는 선입선출 방식 및 회로 |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| A300 | Withdrawal of application because of no request for examination |
Free format text: JAPANESE INTERMEDIATE CODE: A300 Effective date: 19980514 |