cancel
Showing results for 
Show  only  | Search instead for 
Did you mean: 
5,079 Views
Registered: ‎06-10-2008

Implementing a pipelined binary search tree for FPGA

I use the Logicore FFT engine to generate a 16K bit-reversed FFT sequence in real-time. As the FFT engine outputs the results in the bit-reversed order, I first reverse the bits to get to the actual index, and simultaneously I compute the amplitude of each point and check it against a predetermined threshold value. I expect it that 1024 of those points will actually pass the threshold. The problem is that I need to sort these points (in ascending order wrt their natural-order frequency), and any sorting algorithm will take O(nlgn), which is at least 10000 clock cycles, and that is too long for this application. So I am thinking about building a pipelined balanced binary search tree (like a red-black tree) or more conveniently a simple linked list. In either case, I need to pipeline this sorting structure so that I can insert the 1024 numbers into the tree as soon as they become available without needing to wait for the the completing of the sorting of the previous number. My problem is that the memory blocks in FPGA (single or dual port) do let me to execute one or two memory operations at a time. However, for the pipelining to work, consequtive numbers that will be inserted into the search tree will need to concurrently access different cells of the same memory array (the binary tree structure) as they travel down the search tree (or the linked list). Do you know how I should implement a memory structure in FPGA that is suitable for this purpose?

Thanks

0 Kudos
0 Replies