Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

Pipelined Median Generation

IP.com Disclosure Number: IPCOM000050546D
Original Publication Date: 1982-Nov-01
Included in the Prior Art Database: 2005-Feb-10
Document File: 4 page(s) / 27K

Publishing Venue

IBM

Related People

Chen, TC: AUTHOR [+2]

Abstract

A method for the pipeline generation of running medians for binary numbers of fixed length is disclosed.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 47% of the total text.

Page 1 of 4

Pipelined Median Generation

A method for the pipeline generation of running medians for binary numbers of fixed length is disclosed.

At every time cycle, the mechanism accepts an input number, and generates a median together with an indicator of its position within a fixed window. More particularly, a running median can be obtained over a large collection of fixed-length binary integers by way of a bit column processing step. These can be pipelined if the input numbers are made to enter an appropriate mechanism diagonally, that is, the leftmost bit first. The following paragraphs explain the generation of running medians and the concomitant method.
1. The generation of running medians

Consider the inputs as shown below,

.<---3 5 2 1 9 1 4 3 9 8 9 7 8 2 4
. . . . v

+-+

WINDOW RUNNING MEDIAN GENERATION

+-+

V

Medians entering a median-finder with window size 5 (say); then the successive medians are calculated as follows: for (3 5 2 1 9), median value = 3, position vector = 10000

for (5 2 1 9 1), median value = 2, position vector = 01000

for (2 1 9 1 4), median value = 2, position vector = 10000

for (1 9 1 4 3), median value = 3, position vector = 00001

for (9 1 4 3 9), median value = 4, position vector = 00100

for (1 4 3 9 8), median value = 4, position vector = 00010

for (4 3 9 8 9), median value = 8, position vector = 00010

for (3 9 8 9 7), median value = 8, position vector = 00100

for (9 8 9 7 8), median value = 8, position vector = 01001

for (8 9 7 8 2), median value = 8, position vector = 10010

for (9 7 8 2 4), median value = 7, position vector = 01000.

Incidentally, the 'glitch' 9 is removed, yet the plateau '98978' remains a plateau after the processing. Within a collection of numbers, there is only the median value, yet there could be two or more equal-size candidates. The relative position of each candidate is indicated by a 1 in the position vector. The user may select, say, the leftmost member as the correct median. The position becomes important when each input quantity is associated with extra information fields (e.g., pointers to a record in a master file), and the median value alone will not suffice. 2. The Method:

Given a collection of binary integers of fixed word length, by virtue of the leading bit, the collection falls naturally into two sets: a superior set (with leading 1 bit) and an inferior set (with leading 0 bit). The median resides in only one of these. The set not containing the median can be rejected. If one of the sets has no members, then nothing is rejected, of course.

1

Page 2 of 4

As members of the superior set are all greater than members of the inferior set, it is easy to select the set housing the median for survival. Members of this set have all leading bits equal, and the bit immediately to the right can now be used for the next round of dichotomizing. This process can continue until there is only one survivor; it is the median. Or, after all bit positions have been examined from left to right,...