Compared to binary switching functions, the multiple-valued functions (MV) offer more compact representations of the information content of signals modeled by logic functions and, therefore, their use fits very well in the general settings of data compression attempts and approaches. The first task in dealing with such signals is to provide mathematical methods for their representation in a way that will make their application in practice feasible. Representation of Multiple-Valued Logic Functions is aimed at providing an accessible introduction to these mathematical techniques that are necessary for application of related implementation methods and tools. This book presents in a uniform way different representations of multiple-valued logic functions, including functional expressions, spectral representations on finite Abelian groups, and their graphical counterparts (various related decision diagrams). Three-valued, or ternary functions, are traditionally used as the first extension from the binary case. They have a good feature that the ratio between the number of bits and the number of different values that can be encoded with the specified number of bits is favourable for ternary functions. Four-valued functions, also called quaternary functions, are particularly attractive, since in practical realization within today prevalent binary circuits environment, they may be easy coded by binary values and realized with two-stable state circuits. At the same time, there is much more considerable advent in design of four-valued logic circuits than for other p-valued functions. Therefore, this book is written using a hands-on approach such that after introducing the general and necessarily abstract background theory, the presentation is based on a large number of examples for ternary and quaternary functions that should provide an intuitive understanding of various representation methods and the interconnections among them. Table of Contents: Multiple-Valued Logic Functions / Functional Expressions for Multiple-Valued Functions / Spectral Representations of Multiple-Valued Functions / Decision Diagrams for Multiple-Valued Functions / Fast Calculation Algorithms
Author(s): Radomir S. Stankovic, Jaako T. Astola, Claudio Moraga
Series: Synthesis Lectures on Digital Circuits and Systems
Publisher: Morgan & Claypool Publishers
Year: 2012
Language: English
Pages: 170
Acknowledgments......Page 15
Multiple-Valued Logic Functions......Page 17
Tabular Representations......Page 18
Cubes......Page 20
Other Representations......Page 23
Algebraic Structures for Multiple-Valued Functions......Page 24
Functions with Various Properties......Page 28
Functional Expressions......Page 31
Generalizations to Multiple-Valued Functions......Page 33
Sum-of-Product Expressions......Page 35
Galois Field Expressions......Page 37
Galois Field Expressions for Ternary Functions......Page 39
Galois Field Expressions for Quaternary Functions......Page 40
Fixed-Polarity GF-expressions......Page 42
Reed-Muller-Fourier Transform......Page 44
RMF expressions for p=3.......Page 46
RMF expressions for p=4.......Page 48
Computational Efficiency......Page 51
Realization Efficiency......Page 53
Arithmetic Expressions for Multiple-Valued Functions......Page 56
Arithmetic Expressions for Multiple-Valued Functions derived from the GF-expressions......Page 58
Arithmetic Expressions derived from the RMF-expressions......Page 60
Structure of the Arithmetic RMF-transform matrices......Page 62
Haar-like Expressions for Multiple-Valued Functions......Page 65
Sparse Representations from Covering Codes......Page 69
Covering Codes......Page 70
Functional Expressions Determined from Covering Codes......Page 72
Ternary Golay Code......Page 76
Octacode—a quaternary code......Page 77
Sparse Representations Obtained from Algebraic Codes......Page 78
Extensions to Functions of Arbitrary Length......Page 81
Very Large Functions—the Asymptotic Case......Page 82
Fourier Representations of Logic Functions......Page 85
Construction of Group Characters......Page 87
Haar Series for Multiple-Valued Logic Functions......Page 91
Decision Diagrams for Multiple-Valued Functions......Page 93
Reduction rules......Page 95
Multiple-Place Decision Diagrams......Page 96
Reduction of Decision Trees......Page 97
Functional Decision Diagrams for MV Functions......Page 100
Galois field functional decision diagrams......Page 101
Kronecker Galois Field Decision Diagrams......Page 102
Reed-Muller-Fourier Decision Diagrams......Page 104
Vilenkin-Chrestenson decision diagrams for p=3......Page 105
Vilenkin-Chrestenson decision diagrams for p=4......Page 107
Haar Spectral Transform Decision Diagrams......Page 109
HSTDD related to the RMF-transform......Page 113
Edge-valued Decision Diagrams......Page 115
Partial Reed-Muller-Fourier Transforms......Page 117
Edge-valued Reed-Muller-Fourier Decision Diagrams......Page 118
Construction of EVDDs......Page 120
Efficiency of EVDDs......Page 121
Illustrative Examples......Page 122
Construction of Transforms from Decision Diagrams......Page 124
Vilenkin-Chrestenson Haar transform......Page 125
Galois field Haar transforms......Page 127
Recurrence Relations for Haar Functions......Page 129
Fast Calculation Algorithms......Page 133
Illustrative Examples of FFT-like Algorithms......Page 134
Bibliography......Page 143
Authors' Biographies......Page 167
Index......Page 169
