A multiple-valued Reed-Muller transform for incompletely specified functions

Author

Zilic, Zeljko ; Vranesic, Zvonko G.

Author_Institution

Dept. of Electr. & Comput. Eng., Toronto Univ., Ont., Canada

Volume

44

Issue

8

fYear

1995

fDate

8/1/1995 12:00:00 AM

Firstpage

1012

Lastpage

1020

Abstract

This paper considers the Reed-Muller transform for incompletely specified multiple-valued logic functions, which is obtained as the finite field polynomial representation. A new algorithm for dealing with single-variable functions is presented. It is applicable to finite fields of small sizes (two to four), which is of interest because only these fields are readily implementable with today´s MVL technology. It is shown how such or any similar single-variable algorithm can be used to obtain a fast n-variable Reed-Muller transform based on this transform, a heuristic scheme is derived for dealing with incompletely specified functions. It has better computational properties than other methods and achieves the best results when applied to functions with a large number of unspecified points

Keywords

Reed-Muller codes; logic design; multivalued logic; computational properties; finite field polynomial representation; heuristic scheme; incompletely specified functions; multiple-valued Reed-Muller transform; multiple-valued logic functions; single-variable algorithm; single-variable functions; Arithmetic; Circuit testing; Cryptography; Field programmable gate arrays; Galois fields; Logic devices; Logic functions; Polynomials; Programmable logic arrays; Programmable logic devices;

fLanguage

English

Journal_Title

Computers, IEEE Transactions on

Publisher

ieee

ISSN

0018-9340

Type

jour

DOI

10.1109/12.403717

Filename

403717