A real-time radix-2-based median filtering algorithm

The author presents a real-time radix-2-based median filtering algorithm that computes the median bit by bit by successively using the majority rule and the previously computed bits. It determines the k th bit of the median by finding the Kth bit majority of the samples. In addition to the O(n) average computational complexity for n samples, the algorithm offers a simple real-time implementation using hardware that grows gradually with n. The radix-2-based median filter can be designed to find the approximate median with a maximum error of 2^k-q-1 by determining only q most significant bits of the median. The approximate median filter has an increase of speed by a factor of 1-q/k, where k is the word length