Accession Number:

ADA608078

Title:

On the Design of Cost-Tables for Realizing Multiple-Valued Circuits

Descriptive Note:

Journal article

Corporate Author:

NAVAL POSTGRADUATE SCHOOL MONTEREY CA DEPT OF ELECTRICAL AND COMPUTER ENGINEERING

Personal Author(s):

Report Date:

1992-02-01

Pagination or Media Count:

14.0

Abstract:

We propose a heuristic for finding minimal cost-tables for use in the design of multiple-valued logic circuits. It is an iterative approach, in which a good table of size t is composed of a good table of size tau - 1, etc. We analyze its performance, comparing it with three other heuristics. The importance of finding good cost-tables is demonstrated by an analysis that shows there is a wide variation in both cost-table performance and in the performance of heuristics for generating cost-tables. We study linear cost, a general cost function of which two previously studied cost functions are special cases. It is shown that the minimal cost-table using one of the infinitely many linear cost functions is identical to a minimal cost-table using any other linear cost function. Thus, a heuristic for finding the minimal cost-table using the linear cost function is independent of the specific cost function parameters. This result and our observation of well-studied nonlinear cost functions indicate that cost-table design is only marginally dependent on the cost function. We show two additional results on cost-table design. First, it is demonstrated that a search for minimal cost-tables cannot exclude certain seemingly useless functions called composite functions. Second, while the complexity of cost-table design appears to preclude a computationally efficient general algorithm for finding the minimal cost-table, a special case allows efficient design. For the case of a small cost-table, we show how to find the minimal cost-table.

Subject Categories:

  • Economics and Cost Analysis
  • Electrical and Electronic Equipment
  • Computer Programming and Software

Distribution Statement:

APPROVED FOR PUBLIC RELEASE