Browse Prior Art Database

Circuit for Finding the Minimum or Maximum of a set of Binary Numbers

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

Publishing Venue

IBM

Related People

Gourlay, AR: AUTHOR [+3]

Abstract

This article concerns a hardware circuit for finding the maximum or minimum value of a set of unordered binary numbers, which may represent a cluster of image points (pixels) of a digital TV picture held in a frame store.

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 54% of the total text.

Page 1 of 3

Circuit for Finding the Minimum or Maximum of a set of Binary Numbers

This article concerns a hardware circuit for finding the maximum or minimum value of a set of unordered binary numbers, which may represent a cluster of image points (pixels) of a digital TV picture held in a frame store.

The usual method of finding a minimum or maximum of a cluster of image points is based on a sequence of comparisons, performed serially. This requires a relatively long execution time, typically 30 seconds on dedicated computer for processing an entire 1 megapixel image using lusters of sixteen 8-bit pixels.

The present hardware circuit performs the operation of finding a maximum or minimum in a 16-pixel cluster in about 150 nsec, and therefore the processing of an entire 1 megapixel image takes 150 msec.

The circuit is built from a 4-level hierarchical network of fifteen look-up tables (LUTs) (Fig. 1) provided as input with sixteen pixels in parallel from a frame store and providing as output a single pixel which is the maximum or minimum of the set as determined by a control signal C applied to each LUT (C=1 for maximum and C=0 for minimum). The input pixels are temporarily held in registers R while processing takes place.

Each LUT in the network is built of two PROM (programmable read-only memory) modules I and II, as shown in Fig. 2. This arrangement is optimal in respect of LUT memory, size and practical PROM modules. Without the division into two modules the required size of each LUT would be 2/16/ x 8=512 Kbits; with the division, the total size is (512 x 6) + (1024 x 4)=7 Kbits.

The contents of the PROMs I and II are determined by the formula: Module I: Outputs 0-3=C. Maxx (A,B) + C. Min (A,B) where A=most significant 4 bits of a first of the 8-bit input binary num...