Facta Univ. Ser.: Elec. Energ., vol. 20, No. 3, December 2007, pp.
i-v.
Guest Editors Preface
This special issue of the journal Facta Universitatis, series
Electronics and Energetics, celebrates the 20
th anniversary of the
journal. It is devoted to recent developments in Binary and
Multiple-Valued Switching Theory in Circuit Design such as those
presented at the Workshop on Applications of the Reed-Muller
Expansions in Circuit Design and Representations and Methodology of
Future Computing Technology (The Reed-Muller Workshop) held on May
16, 2007 in Oslo, Norway. In that respect, the selection of papers
was aimed at reflecting the main topics within the scope of that
Workshop, starting from classical ones, such as representation
methodologies for discrete functions, to the topics of more recent
research interest related to quantum logic.
This issue includes 16
papers, six of which are extended versions
of papers that were presented at the Reed-Muller Workshop. An
additional ten papers were selected later and based on their
contribution and view to areas of interest related to the Workshop.
The papers can be classified into four broad groups: representation
of functions and spectral transforms (five papers); verification and
Boolean satisfiability (four papers); circuit design (four papers) ;
quantum circuits (three papers). Brief synopses of the papers are
given below with reference to the papers as ordered in the table of
contents.
Exclusive-Or Sum-of-Product expressions (ESOP) require on average a
smaller number of terms than the corresponding Sum-of-Product (SOP)
expressions which are widely used to represent Boolean functions.
For a given function ``the number of terms in the minimum ESOP is
often accepted as a measure of the complexity of the function". In
this setting, it is interesting to detect all functions of a given
number of variables that are most complex with respect to this
complexity measure. With this motivation, B. Steinbach proposes in
[1] a unique (canonical) ESOP representation, called the
Specialized Normal Form (SNF) as a tool to efficiently determine
most complex Boolean functions and study their properties.
Symmetric Boolean functions form a class of Boolean functions
consisting of 
out of the total of 
functions
for a given number of variables
n, which is very important in
engineering practice, since many computing, control, and
communications circuits are described by symmetric functions. When
different symmetry and co-symmetry properties are detected in a
given function, it can be more compactly represented and implemented
in software or hardware. Therefore, characterization of symmetry
properties is an important task. It can be efficiently performed in
the spectral domain since symmetry properties can be expressed in
terms of a relatively small number of relationships among certain
spectral coefficients. The paper by C. Moraga, and R.S. Stanković
[2]
discusses characterization of symmetries in Boolean functions in
terms of relationships between the Reed-Muller coefficients. It has
been shown that certain classes of partial symmetry of Boolean
functions may be efficiently characterized in the Reed Muller
spectral domain, as earlier was done in the Walsh domain. In this
way, both the functions to be analysed and the relationships
expressing their symmetry properties remain within the same
(Boolean) domain, unlike in the characterization of symmetries and
co-symmetries by relations of integer-valued Walsh coefficients.
Hardware implementation of elementary mathematical functions such
as trigonometric, logarithmic, square root, sigmoid, Gaussian
functions, etc., is an important task in many applications. Due to
the numeric nature of the functions, Boolean expressions for such
functions are usually very complex. The arithmetic transform, which
is a hybrid transform defined in terms of basis functions described
by elementary products of binary-valued variables, but with integer
valued coefficients, permits a compact representation of such
functions. In the paper
[3]
by R.S. Stanković and J.T. Astola, it
is shown that further reductions in related representations can be
achieved if fixed-polarity arithmetic expressions are used. The same
applies to the representations of elementary mathematical functions
by word-level decision diagrams.
Reversible coding is an image encoding method that allows
reconstruction of the original image without distortion. However,
application of classical transforms such as the Discrete Cosine
transform, Walsh-Hadamard transform , Haar transform, etc., requires
a large number of levels of transform coefficients. To overcome this
problem, the paper
[4]
by H. Sarukhanyan, S. Agaian, K. Egiazarian
and J.T. Astola proposes a reversible Hadamard transform. In order
to ensure its applicability in practice, a recursion method for the
generation of reversible Hadamard matrices of higher orders and fast
calculation algorithms are defined.
Spectral methods usually require specific kinds of mathematical
foundations for their proper understanding and versatile
applications. These mathematical backgrounds are usually out of the
scope of classical curricula in engineering education. This makes
teaching of spectral methods for particular applications a
challenging task. For this reason, the paper
[5]
by S.N.
Yanushkevich, and V.P. Shmerko, presents an approach, (deduced from
many years of experience) to teaching the Reed-Muller expressions in
introductory courses on Logic Design, from a pedagogical and
methodological point of view.
Verification becomes a critical step in digital circuit design due
to the large number of basic components in contemporary circuits.
Formal verification and symbolic manipulation methods often involve
Boolean satisfiability (SAT) and Binary decision diagrams (BDDs) as
tools to speed up the proof process. However, these methods operate
on the Boolean level description of circuits and do not exploit the
high-level information that is available at the Register Transfer
Level (RTL) which is often what is initially provided. The authors
of paper
[6]
D. Große and R. Drechsler, offer a solution to
overcome this deficiency. The high-level information is exploited to
determine a sufficiently good ordering of variables in BDDs used as
the underlying data structure in the verification of scalable
designs. This approach results in considerable speed up of the
verification process as demonstrated by the experimental results
that are presented.
Free BDDs (FBDDs) are a generalization of BDDs derived by allowing
different orders of variables along paths from the root node to the
constant nodes in the diagram. Due to this feature, FBDDs often
permit more compact representations than do BDDs, but they still
preserve many of the more useful properties of BDDs. However,
construction of FBDDs and determination of labels on the edges is a
rather complex task. The authors of paper
[7]
R. Wille, G. Fey,
and R. Drechsler, propose to record steps in a SAT solver during the
search process for an assignment of initial variables in a function
f to be represented which leads to the function value 1. This
information is used to construct the FBDD for f. The resulting
diagram can be further minimized, if there are isomorphic
subdiagrams, in the same manner as the minimization of BDDs is
performed.
The 3-SAT
problem is the problem of Boolean satisfiability
restricted to the Boolean expressions written as conjunctive normal
form in three variables. It is an important problem, since each
SAT-problem can be transformed to a 3-SAT problem. By Cook's
theorem, this is also an NP-complete problem. Ternary vectors whose
entries are 0,1
, and a symbol 
, which can be either 0
or 
,
are an efficient tool in solving this problem when combined with
set-theoretic operation of intersection. In paper
[8]
by B.
Steinbach and Ch. Posthoff, it is shown that by a suitable binary
encoding of entries of these ternary vectors, the operations over
them can be reduced to operations over binary vectors. These
operations can be efficiently implemented on the level of registers
with 
, 
, or 
bits in parallel.
The paper
[9]
by R. Drechsler, G. Fey, and S. Kinder, presents an
integrated approach to the verification problem by combining BDDs
and SAT solvers over the same data structure although these methods
usually express the opposite performances for a given class of
problems. The integrated approach produces multiple solutions, as in
BDDs, with small memory requirements comparable to that in SAT
solvers which typically produce a single solution. Experimental
results confirming the quality of this hybrid approach are presented
in the paper.
The paper
[10]
by M. Rawski, J.B. Falkowski, and T. Luba,
discusses implementation of several digital signal processing (DSP)
algorithms using Field Programmable Gate Arrays (FPGA) with embedded
DSP blocks. These blocks allow one to implement DSP algorithms by
methodologies that have already been well developed for their
implementation on specialized DSP processors. However, the
flexibility of programmable technologies allows for improved
performances of the resulting devices by better exploiting the
parallelism inherent in many DSP algorithms, as well as supporting
the use of advanced logic synthesis methods such as functional
decomposition and distributed arithmetic algorithms for
implementation of sum-of-product expressions on FPGAs.
The paper
[11]
by I. Levin, O. Keren, and V. Ostrovsky, considers
the design of sequential circuits by exploiting the linearization of
Boolean functions for the combinational part of the circuit.
Sequential circuits produced after the linearization are called
linearized sequential circuits. Impact of the linearization on the
overall complexity of the produced sequential circuits is examined
with special attention paid to the case of the 1-hot encoding of
states.
The linearization of multiple-output switching functions is the
subject of paper
[12]
by O. Keren and I. Levin. The authors
present a linearization method exploiting reordering of
autocorrelation coefficients. The linearized functions have a
smaller implementation complexity than the original functions.
Increasing density of VLSI circuits implies placement of
interconnections even closer, which causes many effects that
influence chip performances and should be properly considered. In
this settings, an important problem is channel routing of a VLSI
circuit, which is a process of connecting pins inside a channel
subject to a set of horizontal and vertical routing constraints
which usually arise in the physical design of a circuit. Typically,
the constrains are the number of layers, the minimal spacing between
wires, minimum wire width, number of vias, cross talk effects, etc.
Minimizing the amount of cross talk while using minimal area is a
design criterion that should be met in practice. Since the channel
routing and cross talk minimization are NP-complete problems, their
efficient solution is a challenging task. The paper
[13]
by I.
Karapetyan considers the problem of channel routing in VLSI circuits
by assuming the classical (Manhattan model) of the channel with a
rectangular space between two parallel rows of pins and two layers
available for routing. The paper develops an estimate on the
channel thickness under these restrictions.
Systems built from reversible logic circuits are attractive from the
power dissipation point of view. Quantum technologies are an option
in hardware implementation of reversible logic. The paper
[14]
by A. Al-Rabadi presents a comprehensive review of synthesis techniques
in reversible and quantum logic circuits design for binary and
multiple-valued functions. In particular, this paper reviews recent
developments in theory and applications of spectral methods,
functional expressions, group-theoretic approach, and cellular
automata in reversible logic synthesis.
In the paper
[15]
by I. Hänninen, J. Takala, an approach to the
design of ultra-low-power multipliers on quantum dot cellular
automata (QCA) nanotechnology is described. This approach promises
very dense circuits and high operating frequencies, using a single
homogeneous layer of basic cells. A pipelined array multiplier
structure is proposed and its performance-area efficiency is shown
to compare well with a previously proposed serial-parallel
structure.
Logic synthesis methods dealing with efficient assignments of
unspecified function values are useful as a basis for various
machine learning approaches, since in this area highly unspecified
functions are widely used. The basic criterion in these logic
synthesis methods, which appears useful in machine learning, is to
produce the simplest possible circuits by suitable assignment of the
unspecified values.
In the paper
[16]
by M. Lukac, and M.A. Perkowski, the same
logic synthesis methods are applied to quantum circuits intended for
realization of robot controllers. Such circuits are capable of
realizing controllers performing both deterministic and quantum
probabilistic behavior.
As the Guest Editors of this issue, we would like to thank all the
authors for their valuable contributions and reviewers for their
hard work under a tight schedule. The constructive comments of the
reviewers were vital in selecting the papers and also very valuable
to the authors.
| Jaakko T. Astola |
|
|
D. Michael Miller |
|
|
Radomir S. Stanković, |
| Tampere, Finland |
|
|
Victoria, Canada |
|
|
Niš, Serbia |
This special issue has been prepared as an answer to the proposal by
Professor Vidosav Stojanovic, the Editor-in-Chief of Facta
Univeristatis,
series: Electronics and Energetics, to mark the 20th anniversary of
publishing this journal and an explicit invitation to the Guest Editors to
cover the area of binary and multiple-valued logic and circuit design, the
recent advent in which is illustrated by subjects presented in the papers
selected.