Browse Prior Art Database

Pipelinable Data Tripartitioner by Means of the Median

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

Publishing Venue

IBM

Related People

Chen, TC: AUTHOR

Abstract

A method for the pipelined generation of running medians for binary numbers of fixed length are extended not only to generate the median, but also to partition the input data into three classes, namely the classes of numbers larger than, equal to, and smaller than the median. In the pipelined implementation, the mechanism accepts an input binary number at every cycle and generates a median together with bit maps pointing to the three classes within the sample domain.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 61% of the total text.

Page 1 of 4

Pipelinable Data Tripartitioner by Means of the Median

A method for the pipelined generation of running medians for binary numbers of fixed length are extended not only to generate the median, but also to partition the input data into three classes, namely the classes of numbers larger than, equal to, and smaller than the median. In the pipelined implementation, the mechanism accepts an input binary number at every cycle and generates a median together with bit maps pointing to the three classes within the sample domain.

The median is important as a means to partition sampled data into three classes, namely - the 'upper' class, U, with numbers greater than the median; - the 'middle' class, V, of numbers equal in value to the median; - and the 'lower' class, W, with members smaller than the median. Example: Consider the inputs 69266

The median has the value 6; and

the position for the upper class is indicated by U=01000,

the position for the median values are found via V=10011,

the position for the lower class is indicated by W=00100.

The multiple occurrence of the median value in the sample is by no means rare. Any tie-breaking procedure could be invoked, if needed, by using the V-vector as a guide.

Often one desires the running median and associated information, through a window of fixed size. For example in processing the sequence. j= 123456789

Data(j)= 219133986 using a window of size N=5, we have successively Window(1) 11111

Sample 21913

Median 2

U 00101

V 10000

W 01010

Window(2) 11111

Sample 19133

Median 33

U 01000

V 00011

W 10100

Window(3) 11111

Sample 91339

Median 33

U 10001

V 00110

W 01000

Window(4) 11111

Sample 13398

1

Page 2 of 4

Median 33

U 00011

V 01100

W 10011

Window(5) 11111

Sample 33986

Median 6

U 00110

V 00001

W 11000.

Next, algorithms to yield the medians, also position vectors V and U, are described.

Let K be the bit matrix K of N rows and L columns formed by N unsigned binary numbers each of L bits. K(k) designates the kth column (NOT row) of K, counting from left to right.

The relative magnitude of the numbers can be found by examining the columns one at a time, from left to right. The list of candidates for the median is successively narrowed, such that after k columns are processed, all surviving median candidates have the same leading k bits.

Let U(k)=the bit map of the known members of the upper class, V(k)=the bit map of the surviving candidates for being the median , W(k)=the bit map of the known members of the lower class, and X(k)=the number of quantities expected to be greater than the median.

Clearly, if there are N=2n+l numbers within the processing window, then before any processing, we have U(O)=an N-bit vector of all 0's
V(0)=an N-bit vector of all 1's
X(0)=n.

As K(k)=the kth 'Column' of the bit matrix is introduced, the survivors are further partitioned into two sets: The superior set showing a 1-bit in K(k); bit map=V(k-1) AND K(k); the inferior set showing a 0-bit in K(k); bit map=V(k-1)

AND K(...