VLSI Digital Signal Processing Systems: Design and Implementation

9.4    PARALLEL ARCHITECTURES FOR RANK-ORDER FILTERS

Rank-order filters are widely used in image processing for applications such as smoothing, noise reduction, edge detection, etc. They are nonlinear filters that sort the input sequence and choose an output based on its rank. The input output relationship of a rank-order filter is given by (9.74):

Fig. 9.17    Eight-point fast DCT flowgraph.

where r = 1, 2, …2N + 1. The window size of the filter is W = 2N + 1. A corresponding system diagram for W = 5 case is shown in Fig. 9.18. This section is mostly concerned with programmable rank-order filters where outputs for all values of r are available. The set of all outputs {y_r(n)} for all values of r is denoted simply as y(n).

This section addresses the parallel architectures of the rank-order filters designed based on the Batcher’s odd-even merge-sort algorithm [17] and algorithmic strength reduction. By sharing some of the merge units in different parallel blocks, the hardware complexity of the parallel rank-order filters can be reduced.

9.4.1    Odd-Even Merge-Sort Architecture

The rank-order filters sort the inputs with respect to their magnitudes based on merge-sort operations. This subsection introduces the odd-even merge-sort algorithm that can be used to efficiently realize the ...