VHDL Design for running sorter

Discussion in 'VHDL' started by Kumar Vijay Mishra, Sep 16, 2004.

  1. 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.
    Kumar Vijay Mishra, Sep 16, 2004
    #1
    1. Advertising

  2. Kumar Vijay Mishra

    John_H Guest

    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" <> wrote in message
    news:...
    > 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, Sep 16, 2004
    #2
    1. Advertising

  3. 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
    glen herrmannsfeldt, Sep 17, 2004
    #3
  4. Kumar Vijay Mishra

    John_H Guest

    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" <> wrote in message
    news:...
    > 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, Sep 17, 2004
    #4
  5. Kumar Vijay Mishra

    Eric Crabill Guest

    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.
    Eric Crabill, Sep 17, 2004
    #5
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. walala
    Replies:
    3
    Views:
    4,796
    walala
    Sep 18, 2003
  2. ZackS
    Replies:
    5
    Views:
    6,791
    Just an Illusion
    Jul 9, 2004
  3. Replies:
    2
    Views:
    8,649
    Jim Lewis
    Mar 21, 2006
  4. afd
    Replies:
    1
    Views:
    8,292
    Colin Paul Gloster
    Mar 23, 2007
  5. Randy Shipp
    Replies:
    1
    Views:
    113
    SonOfLilit
    Feb 19, 2007
Loading...

Share This Page