Linearity of Word-Level Representations of Multiple-Valued Networks
S.N. Yanushkevich, V.P. Shmerko, V.D. Malyugin, P. Dzirzanski and A.M. Tomaszewska
We study a boundary case of combinational Multiple-Valued Logic (MVL) network representations, namely, the linear word-level expressions and Linear word-level Decision Diagrams (LDDs). The latter models have a number of useful properties: linearity and planarity, while they need less memory compared to other circuit formats; besides, they are compatible with the traditional word-level Decision Diagrams (DDs). The essential point of our approach is to represent every level of MVL network by a linear word-level expression that is mapped to an LDD. Hence, an arbitrary MVL network is represented by a set of LDDs. We prove that the word-level DD model upon the condition of linearity, lost the ability to optimize the initial form. Two types of linear word-level expressions are studied. The first type of word-level description is based on an arithmetic (spectral) transform of the integer-valued equivalent of the initial multi-output function. In the second type we obtain the word-level description with digit-wise operations by mapping of the initial functions to integer-valued equivalent. For both approaches, we successfully simulate MVL networks with about 250 levels and 8000 ternary gates. We test both models and show that the LDD representation of an MVL circuit consumes ten times less memory compared to standard formats.