Honored ContributorDoes anyone have any experience with doing sorting on FPGAs?
Anything else to consider other than a simple bubble sort? Im going to need to sort up to 25 values (fixed at 10 or 25) to find the median. Unfortunatly I dont have a lot of spare resources, and it has to be done on a Stratix 1 EP1S25. Isnt it great when the algorithms guys come up with a "simple" solution!
Honored Contributorthis noodle-scratcher is going to be a distraction all day :)
Honored ContributorNo great solution.
But you might want to take a look at heapsort.Honored ContributorIf the calculation time is not a priority, then I would go for brute force simplicity;
1. Create a design containing; - median value register - median count register - current value register - current count register 2. Create a control FSM that; a) Loads the 'current value' register with the first value in RAM b) Loops over all RAM locations, incrementing the 'current count' register when the RAM value matches the 'current value' register c) At the end of RAM, compare the 'current count' with the 'median count', and if 'current count' is greater, load the median registers from the current registers. d) Repeat for all RAM locations. At the end of this loop, the median registers will contain the median value and the number of times it occurs. Cheers, DaveHonored ContributorIn 2006 I spent a couple of evenings to do a median of up to 9 elements. It comes down to what Dave says: you compare every element to every other element and you tally the comparisons for every element. The element whose tally equals the median index is the result. I did the work in AHDL, so it is fairly cumbersome to expand to 25 elements. Comparing only the 4 upper bits for 9 elements uses 287 LC in a Stratix EP1S25 and fully pipelined (3 stages) achieves 175 MHz. I estimate 25 elements to use about 2400 LC : ((e * (e - 1)) / 2 ) * (cw * 2)
