Browse Prior Art Database

# Recursive Algorithm for More-Than-One-On Checker

IP.com Disclosure Number: IPCOM000040396D
Original Publication Date: 1987-Nov-01
Included in the Prior Art Database: 2005-Feb-02
Document File: 2 page(s) / 35K

IBM

## Abstract

A tester or decoder generates a MTOO (more-than-one-on) checker of N signals by recursively applying the function to subsets of K signals. Specifically, for each three (K=3) signals, two functions are generated: MTOO (corresponds to a carry of a full adder), and OOMO (one-or-more-on, which corresponds to an OR of the three inputs). The OOMO signals are treated as single signals to be further combined three at a time. All the MTOO signals are ORed to comprise the MTOO final signal. Other values of K can be used recursively for improved efficiency (fewer components and/or fewer levels of gating). For example, the multiple selection circuit described in the IBMTechnical Disclosure Bulletin 17, 2432 (January 1975), generates a MTOO of 8 (=K) signals (ignoring the "no selection signal").

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

Page 1 of 2

Recursive Algorithm for More-Than-One-On Checker

A tester or decoder generates a MTOO (more-than-one-on) checker of N signals by recursively applying the function to subsets of K signals. Specifically, for each three (K=3) signals, two functions are generated: MTOO (corresponds to a carry of a full adder), and OOMO (one-or-more-on, which corresponds to an OR of the three inputs). The OOMO signals are treated as single signals to be further combined three at a time. All the MTOO signals are ORed to comprise the MTOO final signal. Other values of K can be used recursively for improved efficiency (fewer components and/or fewer levels of gating). For example, the multiple selection circuit described in the IBMTechnical Disclosure Bulletin 17, 2432 (January 1975), generates a MTOO of 8 (=K) signals (ignoring the "no selection signal"). Adding an 8-way OR of inputs BIT1 through BIT8 to represent the OOMO condition, the two signals can be used recursively for a larger number of inputs than the recursion of K=3. The principal idea of the earlier article is to implement the MTOO function of N signals without recursion by performing two- way ANDs of different OR combinations of the inputs, so as to detect every pair- wise AND of the inputs. The OR of these ANDs represents the desired output. If 2-way ANDs of up to 7-way ORs are available as macros, only four such macros plus a 4-way OR would be needed to implement the function. For CMOS-I logic, which illustrates the subject disclosure, the choice of K=3 is more efficient than other values of K, because a special macro is available to implement the MTOO function of three...