Accession Number : AD0883164

Title :   A New Approach to Functional Decomposition.

Descriptive Note : Special rept.,

Corporate Author : AIR FORCE CAMBRIDGE RESEARCH LABS HANSCOM AFB MA

Personal Author(s) : Small, Albert W.

Report Date : 28 DEC 1970

Pagination or Media Count : 92

Abstract : Digital logic circuits are the heart of all signal-processing and information-handling systems in the Air Force. Therefore, the efficient synthesis of digital logic circuits is important to the Air Force. Functional decomposition provides a basic approach to the problem of synthesizing digital logic circuits. The purpose of this study is to provide new insight into the decomposition of combinational logic functions. First, intuitive characterizations are developed that classify logic-functions according to the information they pass. Then, a decomposition problem is presented in which one must synthesize a logic-function using information from the outputs of several given logic-circuits. The goal is to minimize interconnections in the resulting network by appropriate processing at the outputs of the given circuits. To attack this problem the author introduces a partition-quotient operation that can be used to specify the unique information which each of the given circuits must supply. If the collection of given circuits is logically independent, then supplying the unique information guarantees the supply of all necessary information. If the collection is not logically independent, its circuits can be grouped so that the collection of groups is logically independent. The problem is thereby divided into smaller independent problems. (Author)

Descriptors :   *MATHEMATICAL LOGIC, *LOGIC CIRCUITS, ALGEBRA, SYNTHESIS, INFORMATION THEORY, SET THEORY, COMPUTER LOGIC, DIGITAL SYSTEMS, CIRCUIT INTERCONNECTIONS, GRAPHICS, THEOREMS, THESES.

Subject Categories : Theoretical Mathematics

Distribution Statement : APPROVED FOR PUBLIC RELEASE