VHDL Design for running sorter

[Kumar Vijay Mishra]

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.

 

[John_H]

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.

"Kumar Vijay Mishra" <vizziee@yahoo.com> wrote in message
news:889cd7c9.0409152205.35aeb3c@posting.google.com...

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.

 

[glen herrmannsfeldt]

Kumar Vijay Mishra wrote:

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.

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

 

[John_H]

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.

"Kumar Vijay Mishra" <vizziee@yahoo.com> wrote in message
news:889cd7c9.0409152205.35aeb3c@posting.google.com...

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.

 

[Eric Crabill]

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, http://www.engr.sjsu.edu/crabill 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:

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.