© The Institution of Engineering and Technology
New fast linearly independent arithmetic (LIA) transforms are introduced here which can be used to represent any functions of binary variables. The transforms are grouped into classes where consistent formulas relating forward and inverse transform matrices are obtained. All the presented transforms have the same computational cost, which is lower than the computational cost of the well-known fixed polarity arithmetic transforms. General classifications and fast forward and inverse transform definitions for all the fast LIA transforms are given. Various properties and mutual relations that exist for the different transforms and their corresponding spectra are also shown. The presented relations and properties reduce the computational cost of finding the best LIA polynomial expansion based on the new transforms.
References
-
-
1)
-
S.N. Yanushkevich
.
(1998)
Logic differential calculus in multi-valued logic design.
-
2)
-
R.S. Stankovic ,
J.T. Astola
.
(2003)
Spectral interpretation of decision diagrams.
-
3)
-
G.A. Kukharev ,
V.P. Shmerko ,
E.N. Zaitseva
.
(1990)
Multiple-valued data processing algorithms and systolic processors.
-
4)
-
Falkowski, B.J., Lozano, C.C.: `Properties of fastest LIA transform matrices and their spectra', Proc. 36th IEEE Int. Symp. Circuits Syst., May 2003, Bangkok, Thailand, p. 556–559.
-
5)
-
K.D. Heidtmann
.
Arithmetic spectrum applied to fault detection for combinational networks.
IEEE Trans. Comput.
,
3 ,
320 -
324
-
6)
-
T.H. Chen
.
(1992)
Fault diagnosis and fault tolerance: systematic approach to special topics.
-
7)
-
S.K. Kumar ,
M.A. Breuer
.
Probabilistic aspects of Boolean switching functions via a new transform.
J. ACM
,
3 ,
502 -
520
-
8)
-
S. Agaian ,
J. Astola ,
K. Egiazarian
.
(1995)
Binary polynomial transforms and non-linear digital filters.
-
9)
-
J. Jain ,
T. Sasao ,
M. Fujita
.
(1996)
Arithmetic transform of Boolean functions, Representations of discrete functions.
-
10)
-
Falkowski, B.J., Rahardja, S.: `Boolean verification with fastest LIA transforms', Proc. 35th IEEE Int. Symp. Circuits Syst., May 2002, Phoenix, AZ, p. 321–324.
-
11)
-
B.J. Falkowski
.
A note on the polynomial form of Boolean functions and related topics.
IEEE Trans. Comput.
,
8 ,
860 -
864
-
12)
-
V.D. Malyugin
.
(1997)
Parallel calculations by means of arithmetical polynomials.
-
13)
-
Falkowski, B.J., Lozano, C.C., Rahardja, S.: `Generalised fastest linearly independent arithmetic transforms', Proc. 38th IEEE Int. Symp. Circuits Syst., May 2005, Kobe, Japan, p. 480–483.
-
14)
-
B.J. Falkowski ,
S. Rahardja
.
Classification and properties of fast linearly independent logic transformations.
IEEE Trans. Circuits Syst. II, Analog Digit. Signal Process.
,
8 ,
646 -
655
-
15)
-
G.A. Kukharev ,
V.P. Shmerko ,
S.N. Yanushkevich
.
(1991)
Technique of binary data parallel processing forVLSI.
-
16)
-
R.S. Stankovic ,
T. Sasao ,
C. Moraga ,
T. Sasao ,
M. Fujita
.
(1996)
Spectral transform decision diagrams, Representations of discrete functions.
-
17)
-
S. Rahardja ,
B.J. Falkowski
.
Application of linearly independent arithmetic transform in testing of digital circuits.
Electron. Lett.
,
5 ,
363 -
364
-
18)
-
S. Rahardja ,
B.J. Falkowski
.
Fast linearly independent arithmetic expansions.
IEEE Trans. Comput.
,
9 ,
991 -
999
-
19)
-
A.M. Morozov
.
Orthogonal transformation of logic functions.
Cybernetics
,
3 ,
340 -
351
-
20)
-
K.P. Parker ,
E.J. McCluskey
.
Analysis of logic circuits with faults using input signal probabilities.
IEEE Trans. Comput.
,
5 ,
573 -
578
-
21)
-
P.S. Moharir
.
(1992)
Pattern-recognition transforms.
-
22)
-
K. Radecka ,
Z. Zilic
.
Design verification by test vectors and arithmetic transform universal test set.
IEEE Trans. Comput.
,
5 ,
628 -
640
http://iet.metastore.ingenta.com/content/journals/10.1049/iet-spr_20060099
Related content
content/journals/10.1049/iet-spr_20060099
pub_keyword,iet_inspecKeyword,pub_concept
6
6