Abstract
In this work, we propose a new median-finding algorithm which computes the median value in an input list of integers on-the-fly, without any data-sorting operations. We present a complete digital CMOS implementation, associated timing diagrams, and a formal mathematical proof, which show the overall average number of clock cycles for median-finding to be linearly proportional to the input length, that is, O(N) average-time complexity, when N is less than about 100. Hence, our proposed sorting-free median algorithm is suitable for practical applications on 3 x 3 and 5 x 5 image scan matrices, which are in common use for hand-held devices and entertainment graphics applications. Our proposed hardware precludes the need for SRAM memory or complex circuitry, such as pipelining structures, but rather uses simple registers to hold the input values, performing comparison-swapping on 3 values, along with counting, to derive the median value. There is no restriction on the input sequence with regard to having repeated elements. We evaluate an ASIC design of our sorting-free median algorithm using 90 nm TSMC technology, with 1 V supply voltage and a clock frequency of 2 GHz, on example cases of 3 x 3 (9 values) and 5 x 5 (25 values) image-scan matrices. The resulting designs have a minimum transistor-count ranging from 3202 to 5203. Results show that our sorting-free median algorithm, when used on 512 x 512 images with 8-bit pixels, takes 0.364 and 1.394 ms to scan the complete image using 3 x 3 and 5 x 5 scan matrices, respectively, with the associated power consumption ranging from 3.24 to 1.66 mW.