VHDL Design for running sorter

Hi.

I am working on inmplementation of order statistics CFAR, where sorting of a continuous stream of data is required.

Exactly problem is as under: I am getting a continuous stream of 16-bit data. In every clock cyle I have to sort 32-size array. When I have sorted the array in ascending order, I want to choose 24th number only. In the next clock cycle, I get a new no added to my array while the first number gets out of the array. The new array that I get is to be sorted again and he 24th position number is to be taken out. So, in every clock cycle, I get a new data (in an array of 32 16-bit numbers) (with the oldest data getting deleted from this array) and in the same clock cycle, I need to have the 24th-position data available to me for further processing.

Can anybody help me in this? Plus if someone can direct me to any useful link on VHDL designs of sorting, since I am new to FPGA and VHDL.

Thanx in advance.

Reply to
Kumar Vijay Mishra
Loading thread data ...

Your problem may be simpler than you imagine. If you need a result at

*every* clock and start from an empty array, you can insert the new values one at a time until you have the 32-bit population, then begin the removal and replacement. If you have 31 comparators for the new value (you can ignore the 24th), your results will look like a thermometer when comparing the new value to the pre-ordered array. The elements 1-23 can shift up 0 or 1 depending on the local comparison bit. The elements 25 to 32 can shift down by 0 or 1 based on the same results. The one caveat is that the initial values before bringing in the first set of 32 numbers need to shift completely off one end with an out-of-range number rather than shifting out position 24.

If you want a full sort of 32 unsorted values, I can give you a technique - the bitonic sort - to perform the sort in 15 clock cycles; it's one of the fastest ways to do a full sort but requires time and resources. The one-at-a-time method I outlined above would give you better results.

Reply to
John_H

If it really works that way there is just about only one way to do it, because you must do everything in one clock cycle.

You need to compare the number coming in against all the others in the list, except the one going out, and arrange the new data ready to clock in on the next cycle. Startup is a little complicated, as you must make sure that it fills up the right way. 32 16 bit registers, appropriate comparators and such should fit easily in a medium sized FPGA.

-- glen

Reply to
glen herrmannsfeldt

Say, your clock cycles aren't something very slow like 4MHz, is it? Your speed needs would help drive an "ideal" solution since you could perform all the compares with one comparator over 32 cycles.

Reply to
John_H

Hi,

You can use an odd-even transposition sort. This is a parallel version of the bubble sort that works well in hardware. I have a version of it written in Verilog on my site,

formatting link
in Lecture Module 6. You can adapt it to your application and then remove the pipeline registers if you want to trade frequency of operation for lower latency.

Eric

glen herrmannsfeldt wrote:

Reply to
Eric Crabill

ElectronDepot website is not affiliated with any of the manufacturers or service providers discussed here. All logos and trade names are the property of their respective owners.