# 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.

# Descriptors:

# Subject Categories:

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