Re: Median filter in Verilog
- From: glen herrmannsfeldt <gah@xxxxxxxxxxxxxxxx>
- Date: Tue, 24 Jun 2008 11:05:34 -0800
john wrote:
I am trying to design a median filter in Verilog. There are plenty of
papers on median filter designs for image/audio applications. However,
I cannot find any starting point for a median filter which needs to
sort 100 numbers (14bit wide each).
My favorite architecture for such processors is the
systolic array, which may or may not be useful in this case.
First thought is that, given an already sorted array you
remove one point and add the new one in the appropriate position.
(Note that http://en.wikipedia.org/wiki/Median_filter says
you should have an odd number, and 100 isn't odd.)
The sort/insert should be done in a fixed number of clock
cycles, like one or two. That would seem to require N
comparators, and N bit priority encoder, and N multiplexers
to shift and insert as appropriate. That sounds like a lot
of logic, but it shouldn't be hard in a reasonable sized
ASIC or FPGA to fit it in. It requires signals going
long distances across the array, which might slow it
down too much.
My first thought on seeing Median was an algorithm
in Knuth, "The Art of Computer Programming," vol. 3,
on an O(n) algorithm for median that doesn't sort
the whole array.
A systolic array solution isn't immediately obvious,
but that might work better for high speed processing.
It might be that the algorithm in Knuth could be
implemented in some type of parallel array not
requiring long distance communication.
-- glen
.
- Follow-Ups:
- Re: Median filter in Verilog
- From: Jonathan Bromley
- Re: Median filter in Verilog
- References:
- Median filter in Verilog
- From: john
- Median filter in Verilog
- Prev by Date: Re: Median filter in Verilog
- Next by Date: Verilog 2001 Port Declaration
- Previous by thread: Re: Median filter in Verilog
- Next by thread: Re: Median filter in Verilog
- Index(es):
Relevant Pages
|
Loading
