ABSTRACTS
- koda-sasao-92
An AND-EXOR expression (exclusive-or sum-of-products expression: ESOP)
is obtained by EXORing arbitrary product terms. First, some properties
are shown of minimum ESOPs which are useful for the minimization of
ESOPs. Second, a catalog of minimum ESOPs for the representative
functions of 4-variable NP-equivalence classes is presented. Minimality
is defined as first minimizing the number of the product terms and then
the number of the literals in the ESOP. Minimum ESOPs are obtained by
an exhaustive method. The average number of products to realize the 4-
variable functions by AND-OR sum-of-products expressions is 4.13 and
3.66 by ESOPs. Minimum ESOPs with four variables or less are obtained
easily by the table look-up of the catalog. The catalog is useful for
the minimization and the complexity analysis of ESOPs with five or more variables.
- toida-rao92
Single output logic circuits composed of AND and EXOR gates are
studied. It is shown that for two level single output logic circuits
composed of AND and EXOR gates, tests that detect all detectable stuck-
at faults can be generated in polynomial time. In this method no extra
input variables nor extra circuits are required. This contrasts with
the fact that for AND, OR circuits the test generation problem is not
polynomial time solvable even for two level circuits. Since AND-EXOR
circuits can represent any switching function, this suggests that these
circuits might be easier to test than AND, OR circuits.
- habib93
Presents a new, very fast, algorithm to generate the minimal Reed-
Muller exclusive OR (ExOR) expansion with mixed polarity for any
arbitrary, completely and incompletely specified switching function.
The major consideration of this algorithm is to obtain a minimum number
of product terms in the ExOR function. The algorithm is based on the
use of Boolean matrix representation and an efficient technique called
minterm separation operation developed by the author. The proposed
algorithm consists of three procedures: removing the variables on which
a given switching function does not depend; generating the positive
polarity Reed-Muller expansion coefficients; and then generating the
final Reed-Muller ExOR expansion with mixed polarity in the canonical
product form directly. The proposed algorithm can deal with functions
of a large number of variables. Based on the proposed approach, a fast
and efficient computer program is developed. This program accepts an
arbitrary switching function in terms of minterms and returns a mixed-
polarity Reed-Muller expansion as an output in its canonical product
form. The realization of the developed algorithm and the computer
implementation were tested on many examples as well as on many
arithmetic functions.
- koda-sasao93
The authors present properties of exclusive-or sum-of-products
expressions (ESOPs) and their minimization algorithm. First, lower
bounds on the number of products in minimum ESOPs (MESOPs) are shown.
Then, an algorithm to simplify ESOPs is presented. The algorithm can
often prove their minimality for functions of up to five variables. The
authors utilise a table of MESOPs for all the functions of four
variables, and (1) find a lower bound on the number of products in the
MESOP, (2) obtain an initial solution for the given function, (3)
simplify the ESOP by an iterative improvement method, and (4) stop the
iterative improvement when the solution is proved to be minimum.
Experimental results show that this algorithm proves the minimality of
about 98% of the five-variable functions.
- kouchi92
The structure of a simple neural network is optimized by the use of a
genetic-algorithm. The neural network is a perceptron, which has three
outputs; the logical AND, OR and XOR of two inputs The evaluation
function for optimization is a linear combination of the correctness,
the network sizes, and an auxiliary term inducing the optimum solution
The chromosome is a vector of the link weights of the network. The
genetic operators used are crossing-over and point-mutation on the
parent chromosomes Two genetic rules were tested. In the haploidy rule,
each individual has single chromosome, and the offspring is generated
by crossing-over the parents' chromosomes at a randomly chosen locus
and taking one of those crossed-over chromosomes. In the diploidy rule,
each individual has a pair of chromosomes, and the offspring's
chromosomes are generated by combining the gamete produced through the
meiosis of the parents' chromosomes. The other model used in the
genetic algorithm is the geographical isolation model, where the entire
population is divided into four sub-populations, in which the local
selection and reproduction are carried out, though, in some time
interval, randomly sampled individuals are exchanged among sub-
populations. Comparison was made among four combinations of haploid or
diploid, and single-population or multiple sub-populations. Diploidy
together with the sub-population model was proved to be the best for
this optimization problem. Thus, the optimum structure of network was found.
- sasao92
The author presents an optimization method for pseudo-Kronecker
expressions of p-valued-input, two-valued-output functions using
multiplace decision diagrams for p=2 and p=4. A conventional method
using extended truth tables requires memory of O(3/sup n/) to simplify
an n-variable expression, and is only practical for functions of up to
n=14 variables when p=2. The method presented utilizes and can optimize
considerably larger problems. Experimental results for up to n=39 variables are shown.
- perkowski92
The fundamental concept of generalized orthonormal expansion, which
generalizes the ring forms of the Shannon expansion to logic with
multivalued (MV) inputs and standard trivial functions of an arbitrary
number of variables, is introduced. Some applications of the
generalized orthonormal expansion are presented, including several
generalizations of canonical forms both known from the literature and
new. These include a family of canonical tree circuits, which are
considered for binary and multivalued input cases. They can be
multilevel or flattened to two-level AND-EXOR circuits.
- habib92a
This paper presents a new and efficient algorithm to format the
minterms of an n variable arbitrary switching function in a Boolean
matrix and to compute its minimal Reed-Muller ExOR (Exclusive-OR)
expansion in fixed polarity. The algorithm is based on a technique,
called 'minterm separation operation', developed by the author. The
proposed minimization criteria of the presented algorithm is, to
generate a fixed polarity ExOR expansion that has minimum number of
terms (inputs to ExOR gates), and the minimum number of gate inputs.
The presented algorithm has the advantage that it is able to treat
functions with a large number of variables, and is also applicable to
incompletely specified functions because the algorithm through its
constitution can deduce the suitable values for the 'Don't care' terms
with the minimal solution. Based on this approach, a fast and efficient
computer method is developed for the generation of all possible Reed-Muller
ExOR expansions in fixed polarity, from which the minimal
solution may then be selected. Demonstration examples with results
analysis are illustrated and a comparison with other algorithms is introduced.
- latypov92
A combinational circuit structure is proposed, which allows detection
of simple stuck-at faults in ring testing. The combinational circuit
has a two-level realization using AND and EXCLUSIVE OR elements with
supplementary EXCLUSIVE OR control elements and conjunctions. The ring
testing system combines the functions of a test pattern generator and a
signature analyzer and reproduces a standard test using the (n+1)
patterns 11. . .11, 11. . .10, . . ., 01. . .11.
- davidheiser92
Summary form only given: Superconducting digital gates promise high
speed performance at exceedingly low power. Thus, if this technology
meets acceptance in packing density, integration levels, margins, and
ease of design, it will be extremely competitive. TRW has recently
reported the first digital gates in the new high temperature
superconducting material YBaCuO. The gates are embedded in a novel
architecture that achieves an ease of design and resembles the
circuitry employed by the CMOS community. The author reports the
Boolean functions of AND, EXOR, EXNOR, inversion and buffer gates
developed at low speed and reduced temperature. Modelling of newer
devices already available predicts operation at up to a 1 GHz clock and
at 50 K. The additional functions of NAND, NOR, and OR are
modifications of the final wiring layer on the basic gate design.
- koda-sasao92a
An upper bound on the number of product terms required for representing
any switching function as a minimum AND-EXOR expression (MESOP) is
presented. First, an LP equivalence relation which is useful for
classifing AND-EXOR two-level circuits is introduced. Then by using the
properties of MESOPs and the LP equivalence relation, the followings
are shown: (1) 5-variable functions are divided into 6936 LP
equivalence classes; (2) an arbitrary 6-variable function can be
realized by a MESOP with at most 16 products; and (3) an arbitrary
function of n-variable (n>or=6) can be realized by a MESOP with at most
2/sup n-2/ products.
- koda-sasao91
AND-EXOR expressions (exclusive-or-sum-of-products expressions: ESOP's)
are considered. Some properties of minimum ESOP's which are useful for
the minimization of ESOP's are shown. A catalog of minimum ESOP's for
the representative functions of 4-variable NP-equivalence classes is
presented. Minimality is defined as minimizing first the number of
product terms and then the total number of literals in the expression.
Minimum ESOP's are obtained by an exhaustive method. It is shown that
the average number of products to realize an arbitrary 4-variable
function by an AND-OR expression (sum-of-products expression) is 4.13,
and 3.66 by an ESOP. These results confirm the conjecture for the base
of n=4. Minimum ESOP's of four or less variable functions are easily
obtained by the table look up of the catalog, and the catalog is useful
for the minimization and the analysis of the complexity of five or more variable ESOP's.
- deLustrac91
A Josephson 2-b full adder and a 4-b parallel multiplier are designed
using an advanced design with speed optimization of functional direct
coupled logic. Wide margins EXOR, majority 2/3, and delay gates
implemented with picosecond junctions (R/sub C/C=2 ps) are presented
and their performances are analyzed. The adder consists of 10 gates
with 90 Josephson junctions and dissipates 30 mu W. The propagation
time along the critical path is 10 ps/b near threshold bias. It rises
only at 20 ps/b in the adder at 80% of the maximum bias. The multiplier
consists of 60 gates and dissipates 180 mu W. The propagation times
along the critical path near threshold bias, and at 80% of maximum bias
are respectively 60 ps/b and 100 ps/b.
- hongBokSong90
An optimization problem of AND-EXOR PLA's with input decoders can be
regarded as a minimization problem of Exclusive-Or Sum-Of-Products
expressions (ESOP's) for multiple-valued input two-valued output
functions. The authors propose a minimization algorithm for ESOP's. The
algorithm is based on an iterative improvement. Five rules are used to
replace a pair of products with another one. The authors minimized many
ESOP's for arithmetic circuits. In most cases, ESOP's required fewer
products than SOP's to realize the same functions.
- huang-li90
A collection of eight different CMOS EXOR (exclusive OR) gates is
presented. The circuit implementations of these EXOR gates range from
three to a dozen transistors. A circuit diagram, layout size, and
simulation results from LSIM, SPICE, and IRSIM are given for each of the circuits.
- sasao-besslich
Consideration is given to the realization of logic functions by using
PLAs with an exclusive-OR (EXOR) array, where a function is represented
by mod-2 (EXOR) sum-of-products (ESOPs) and both true and complemented
variables are used. The authors propose a new PLA structure using an
EXOR array. They derive upper bounds on the number of products of this
type of PLA that are useful for estimating the size of a PLA as well as
for assessing the minimality of the solutions obtained by heuristic
ESOP minimization algorithms. Computer simulation using randomly
generated functions shows that PLAs with the EXOR array require, on the
average, fewer products than conventional PLAs. For symmetric
functions, the authors conjecture that the PLAs with an EXOR array
require, at most, as many products as the conventional PLAs. The
proposed PLAs can be made easily testable by adding a small amount of hardware.
- okada89
CMOS, BiCMOS and ECL devices are discussed. NAND, NOR OR and exclusive OR-NOR gates are presented.
- helliwell-perkowski88
The concept of a mixed-radix multiple-valued input exclusive sum of
products (MRESP) is presented, and some possible circuit realizations
for the concept are discussed. The algorithm starts from a Boolean
function and generates an approximate MRESP form and the appropriate
multioutput circuit. Such circuits can have smaller complexity than the
EXOR forms with mixed polarity, the PLAs with decoders, and the
networks with two-variable function generators. They are also easily testable.
- becker88
PLAs (Programmable Logic Arrays) are arrays of AND- and OR-gates in
which each output is a Boolean function of the inputs. The paper deals
with PLAs on the basis of AND- and EXOR (Exclusive Or)-nodes. Two test
strategies are presented: a self test on the chip and an off-chip test.
- svensson88
The nonrestoring pass transistor EXOR gate is investigated by switch-
level simulation. It is shown that the logical function of the EXOR
gate depends on the driving conductance on the inputs to the gate. It
is also shown why switch-level simulators are unsuccessful in
simulating the pass transistor EXOR gate, and how a switch-level
simulator can be designed to produce a correct simulation result.
- pyo-yazdani88
A CMOS NOR-NOR testable PLA (CTPLA) which has a universal test set is
discussed. Berkeley VLSI tools were used to implement and verify the
design. The PLA contains an extra row and a column, along with a shift
register and two cascades of exclusive-OR (EXOR) gates, to make it
testable. The layout of the CTPLA was implemented such that the
inherent regularity of the PLA can be maintained without undue
compromise. A procedure which automatically generates the layout
according to a given personalization was written. The test set detects
all single stuck-at faults as well as crosspoint faults.
- areitio88
After a brief explanation of the EXOR operator, the authors demonstrate
a procedure for transforming an initial combinatorial system defined in
canonical minterms into its EXOR-AND or EXOR-OR equivalent, defining
the steps of the transformation in each case. In order to further
elucidate the procedure, they illustrate it with a number of examples
of its application, showing the implementation of logical structures
including EXOR-AND and EXOR-OR gates.
- ladjadj86
The authors introduce the concept of the transparency cube in the
extraction and testing of an embedded logic submodule. The algorithm
presented can establish control of a submodule in a very small amount
of CPU time, and it has been found to perform extremely well when
tested on cellular array topologies such as those which occur in
systolic architectures. The program described detects if parts of a
circuit are untestable and notifies the user as to where additional
logic is necessary to make the circuit more transparent or testable. It
also introduces controllability numbers for flexible signals (or
subscripted Ds) and a method by which an exclusive OR gate (EXOR) is
handled as a single gate in the controllability calculations. This is
useful since controllability numbers do not represent well the
difficulties encountered with reconvergent fanout.
- matheron85
A Josephson 4-bit full adder circuit using functional direct coupled
gates has been designed and studied through computer simulations. The
circuit consists of only 27 gates taken from a complete logic family
composed of OR, AND, EXOR and MAJORITY gates. The proposed adder scheme
needs 180 Josephson junctions and 150 thin film resistors. The computed
critical path delay was found to be 180 ps/4 bits for carry
propagation, with a power dissipation estimated to be less than 100 mu
W on the basis of Nb/Pb-In technology with 4 mu m minimum linewidth and
with a Josephson current density of 1000 A/cm/sup 2/. The worst case
total add time for the 4 bits has been found to be less than 300 ps.
- aoki84
The circuit realizes six logical operations, i.e. A Pass, B Pass, AND,
OR, Exclusive OR, (EXOR), and Multiplexing (MUX) by means of a single
circuit comprising only nine gates per bit position.
- bhattacharya84
The detection problem of bridging faults in AND-EXOR arrays is
considered in this paper in a new framework. These AND-EXOR arrays are
different from the arrays based on the so-called Reed-Muller canonic
(RMC) expansion of functions. The multiple stuck-at fault detection
test set in such arrays as already derived by Pradhan (1978) has been
utilized to detect bridging faults. One most important advantage of
this test set is that it is independent of the function realized and it
has a simple algebraic structure and hence can be generated easily. As
this conventional test set is insufficient to detect all bridging
faults, the authors propose a technique of augmenting the network with
some additional observation points which take care of otherwise
undetectable bridging faults.
- besslich83
Application of exclusive-OR logic design suffers from a lack of
straightforward design methods. Recently a procedure using generalised
Reed-Muller (GRM) coefficient maps has been proposed. Based on this
approach, an efficient computer method is developed for the generation
of all 2/sup n/ sets of GRM coefficients of an n-variable Boolean
function. Along with the coefficients a metric may be calculated from
which the minimum cost set according to some criterion may be selected.
The method requires a storage of 2/sup n/ bits and an average of 2/sup
n-1/+n/2 ExOR single-bit operations per set of GRM coefficients.
- rao81
The arithmetic operations in finite fields and their implementation are
important to the construction of error detecting and correcting codes.
The addition, multiplication and division in the field GF(2/sup m/) are
implemented as polynomial operations using binary logic of flip-flops
and EXOR's. For fields of non-binary characteristic, modular arithmetic
(with modulus p, a prime) becomes important. The author focuses on
problems relating to the arithmetic of GF(p), and some recent results
and new ideas on this topic are presented.
- coy79
A design procedure is shown which allows the construction of one-
dimensional iterative systems of combinational cells with good single
stuck-at fault test complexity. Let S be a system where one of the M
input words and two of the N states are defined for test purposes and
the cells are realized as AND-EXOR normal form circuits, then S is
testable with at most (log/sub 2/ (M*N)+6) tests for all single faults
and for any number of cells. A weaker restriction is shown, where no
normal form realization is necessary, and which gives good testabilit
for single or multiple stuck-at faults of the input/output and
interconnection lines of cells.
- kodandapani78
Fan-out-free networks of AND, OR, NOT, EXOR, and MAJORITY gates are
considered. Boolean functions for which such networks exist are defined
to be fan-out free. The paper solves the following problems regarding
the fan-out-free networks and functions. (1) Characterization of the
class of fan-out-free functions: the characterization given is
constructive in the sense that if a given function is fan-out free one
obtains a fan-out-free network to realize it. (2) Counting the class of
fan-out-free functions: after establishing a correspondence between a
fan-out-free function and a normalized network realizing it, a series
of formulas are developed to count distinct normal networks for any
subset of the five gates mentioned above. (3) Fault diagnosis: methods
are developed to detect multiple faults and to locate single faults in
arbitrary fan-out-free networks.
- kodandapani78
- pradhan78
The fault-detection problem in AND-EXOR arrays is formulated in a new
framework. The arrays considered are more general compared to those by
the previous researchers. Designs of fault detecting test sets to
detect all multiple faults in these networks are presented. The designs
are independent of the function realized and hence can be generated easily.
- kodandapani78
- monteiro72
The paper establishes that residue codes can be very effectively used
to check logical operations (AND, OR, EXOR). The mathematical theory
and logic presented enables one to design a residue checker
organization to detect errors in all arithmetic and logical operations
of a processor. Mathematical expressions characterizing the operations
of processor and checker are derived and are used to obtain a hardware
implementation schematic.
- garcia68
The correction of any errors originated by a single component failure
in the circuitry associated with logical operations (such as AND, OR,
EXOR, NOT, and MASK) of a processor is considered. As a basis for
discussion we select a specific nonredundant configuration which
includes two operand registers and associated logic circuitry. The two
methods of checking analyzed are: (1) application of an error
correcting code, and (2) triplication. An important constraint in these
approaches is that no single component failure should affect more than
one digit. Three different levels of system complexity are considered
to determine the relative effectiveness of the checking methods. It is
concluded that a coding scheme capable of error correction has definite
advantages over triplication when applied to the proper level of
complexity of the processor.
- tsai93
Each Boolean function with fixed polarity of variables can be
represented uniquely in a two-level AND/XOR form, called the
generalized Reed-Muller (GRM) form. The minimization problem is to find
the optimal polarity that requires the least number of product terms in
the GRM representation. An efficient algorithm was developed to extract
product terms of Boolean function, given a polarity of variables. It
achieves the lower bound complexity. A heuristic algorithm targeting
the minimization problem is proposed. It derives the polarity for every
variable and extracts all product terms simultaneously. It is based on
the concept of a Boolean center for minterms, which emulates the center
of gravity concept in geometry. The experimental results are very encouraging.
- xu-almaini93
Reed-Muller universal logic modules (RM-ULMs) and the development of
prototype modules using full-custom techniques are discussed. The
design of two-to-one and four-to-one RM-ULMs using 1.5 mu m CMOS
technology is described. Design procedures using CHIPWISE and the SPICE
simulation results of the modules are outlined.
- tsai-sadowska93
Each Boolean function with fixed polarity of variables can
be represented uniquely in a two-level AND/XOR form, called the
generalized Reed-Muller (GRM) form. The minimization problem is to find
the optimal polarity that requires the least number of product terms in
the GRM representation. An efficient algorithm was developed to extract
product terms of Boolean function, given a polarity of variables. It
achieves the lower bound complexity. A heuristic algorithm targeting
the minimization problem is proposed. It derives the polarity for every
variable and extracts all product terms simultaneously. It is based on
the concept of a Boolean center for minterms, which emulates the center
of gravity concept in geometry. The experimental results are very encouraging.
- schubert92
Functional decision diagrams (FDD) are shown to be a very efficient
alternative to binary decision diagrams (BDD). FDDs are a
representation in the functional domain, since they are based on the
Reed-Muller Expansion and not on the sum-of-products form, which is
suited to the operational domain. This paper introduces a technology
mapping algorithm based on the FDDs and performing a direct mapping to
look-up table FPGA. One can keep the main property of FDDs-their
compactness-to obtain good results in very short CPU times.
- habib93
Presents a new, very fast, algorithm to generate the minimal Reed-
Muller exclusive OR (ExOR) expansion with mixed polarity for any
arbitrary, completely and incompletely specified switching function.
The major consideration of this algorithm is to obtain a minimum number
of product terms in the ExOR function. The algorithm is based on the
use of Boolean matrix representation and an efficient technique called
minterm separation operation developed by the author. The proposed
algorithm consists of three procedures: removing the variables on which
a given switching function does not depend; generating the positive
polarity Reed-Muller expansion coefficients; and then generating the
final Reed-Muller ExOR expansion with mixed polarity in the canonical
product form directly. The proposed algorithm can deal with functions
of a large number of variables. Based on the proposed approach, a fast
and efficient computer program is developed. This program accepts an
arbitrary switching function in terms of minterms and returns a mixed-
polarity Reed-Muller expansion as an output in its canonical product
form. The realization of the developed algorithm and the computer
implementation were tested on many examples as well as on many arithmetic functions.
- csanky-perkowski-schaefer92
The concept of canonical restricted mixed polarity (CRMP) exclusive sum
of products (ESOP) forms is introduced. It includes the inconsistent
canonical Reed-Muller and generalized Reed-Muller forms as special
cases. The set of CRMP forms is included in the set of ESOP
expressions. An attempt to characterize minimal CRMP forms for
completely specified Boolean functions is presented, as well as an
attempt to gain insight into the complexity of computation needed to
find such a form. Some fundamental properties unique to CRMPs are
proved. It is also proved that the upper bound on the number of terms
in the CRMP form is smaller than that in the conventional normal forms
and is equal to that of the ESOPs. A theorem providing a lower bound on
the number of CRMP terms is also given. These results prove the
validity of the CRMP concept. An efficient generic heuristic algorithm
to find the CRMP form is presented.
- xu-almaini93
Describes Reed-Muller universal logic modules (RM-ULMs) and their use
for the implementation of logic functions given in Reed-Muller (RM)
form. A programmed algorithm is presented for the synthesis and
optimisation of RM-ULM networks. The level-by-level minimisation
procedure is based on the selection of control variables at different
levels with the aim of maximising the number of discontinued branches
and hence minimising the number of modules required to implement a
given function. The algorithm is programmed in Fortran and can be used
to realise fixed-polarity generalised Reed-Muller (GRM) expansions of
any polarity and any number of variables.
- besslich91
Resurrected interest in mod-2 sum logic requires efficient algorithms
for synthesis of incompletely specified multiple-output functions. The
authors report on a program based on new algorithms: Quasi-minimum
covering is obtained in a polarized Reed-Muller domain using a modified
disjoint sharp operator. Since a new algorithm for cubewise RMT is
applied, and since no iterative procedures are employed, the program
performs about an order of magnitude faster than other algorithms. The
new program can handle functions of hundreds of variables on a personal
computer. Solutions are (on average) superior to those of other methods.
- csanky93
The concept of canonical restricted mixed polarity (CRMP) exclusive-OR
sum of products forms is introduced. The CRMP forms include the
inconsistent canonical Reed-Muller forms and the fixed-polarity Reed-Muller
(FPRM) forms as special cases. The set of CRMP forms is included
in the set of exclusive-OR sum-of-product (ESOP) expressions. An
attempt to characterise minimal CRMP forms for completely specified
Boolean functions is presented as well as an insight into the
complexity of computation needed to find such a form. Some fundamental
properties unique to CRMPs are proven. It is also proven that the upper
bound on the number of terms in the CRMP form is smaller than that in
the conventional normal forms and equal to that of the ESOPs. A theorem
providing a lower bound on the number of CRMP terms is given. Finally,
based on these theoretical results, a heuristic algorithm and its
implementation to obtain a quasiminimal CRMP form for a multioutput
function are presented.
- tran-wang93
A minimisation method for Reed-Muller polynomials in mixed polarity
known as the decomposition method is developed. The method adopts the
top-down approach in which the products of a Reed-Muller polynomial are
decomposed from a 1-term list one by one. It can be implemented on
computers. Tristate maps can also be used if the number of variables is
equal to, or less than, six.
- tran-lee93
The concept of tri-state map that is used to represent and to minimise
the Reed-Muller polynomials for functions of six or fewer variables is
generalised to functions of any number of variables. A minimisation
method for Reed-Muller polynomials in mixed polarity known as the
composition method is developed. It can be implemented by a tabular
method as well as on computers.
- schafer-perkowskiIEE
The concept of canonical multiple valued input generalised Reed-Muller
(MIGRM) forms is introduced. The MIGRM is a direct extension of the
well known generalised Reed-Muller (GRM) forms to the logic with
multiple valued inputs. The concept of the polarity of a GRM form is
generalised to the polarity matrix of a MIGRM form. A tabular pattern-
matching method is presented for the calculation of a MIGRM form. The
MIGRM transform has been implemented for further investigations of such
forms and their comparison with other circuit realisations.
- green-khuwaja92
The simplification of switching functions expressed as modulo-2 sums of
products is investigated. It is demonstrated that the apparently
different approaches of general simplification and the location of the
optimum canonical representation of a given function are ultimately
equivalent providing the complete range of possible canonical forms is
considered. An extended form of function vector is introduced and it is
shown that the set of all possible vectors can be partitioned into
equal-sized cosets each of which corresponds to different truth vector.
Some properties of these cosets are given and a number of
simplification procedures based on this extended function vector are outlined.
- saul92
A procedure for multi-level Reed-Muller minimization has been developed
which introduces a Reed-Muller factored form, and uses algebraic
algorithms for factorization, decomposition, resubstitution,
collapsing, and extraction of common cubes and subexpressions. The
procedure has been used to design some arithmetic circuits using a gate
library containing a wide range of gates, and the resulting circuits
were compared with some designed using MisII. The circuits designed
using the Reed-Muller system were over 20 percent smaller and between
25 and 50 percent faster.
- kebschull92
The authors introduce an efficient data structure for Boolean function
representation and present a new algorithm for the synthesis of
multilevel logic. Other algorithms represent Boolean functions in the
operational domain using Sum-of-Products representations. The authors
prefer the synthesis in the functional domain using the less complex
Reed-Muller Expansion. The algorithm bases on a new efficient
representation, the so-called functional decision diagrams, which are
herewith presented. The authors implemented this algorithm, the results
are encouraging.
- harking-moraga92
A method for computing Reed-Muller expansions for multivalued logic
functions is presented. All coefficients are constructed directly
without the use of matrix multiplication. Due to the high degree of
parallelism, the complexity of the algorithm in terms of the area-time
tradeoff (AT/sup 2/) yields a better result than a butterfly algorithm does.
- fei-zhuang92
A fast algorithm for logic synthesis based on U/sub f/ (a ternary Reed-
Muller universal logic module) is presented. Using this algorithm, the
optimum or suboptimum synthesis scheme for n-variable logic functions
can be located using pseudoexhaustive search of time (n+2)(n-1)/2.
- habib92b
This paper presents a new and efficient algorithm to format the
minterms of an n variable arbitrary switching function in a Boolean
matrix and to compute its minimal Reed-Muller ExOR (Exclusive-OR)
expansion in fixed polarity. The algorithm is based on a technique,
called 'minterm separation operation', developed by the author. The
proposed minimization criteria of the presented algorithm is, to
generate a fixed polarity ExOR expansion that has minimum number of
terms (inputs to ExOR gates), and the minimum number of gate inputs.
The presented algorithm has the advantage that it is able to treat
functions with a large number of variables, and is also applicable to
incompletely specified functions because the algorithm through its
constitution can deduce the suitable values for the 'Don't care' terms
with the minimal solution. Based on this approach, a fast and efficient
computer method is developed for the generation of all possible Reed-Muller
ExOR expansions in fixed polarity, from which the minimal
solution may then be selected. Demonstration examples with results
analysis are illustrated and a comparison with other algorithms is introduced.
- perkowski-sarabi-schafer91
There are several applications in PSUBOT robotized wheelchair,
including image and speech processing that require fast one- and multi-
dimensional signal processing. The well-known Fast Fourier Transform
(FFT) is used for these. However, there are other discrete orthogonal
transforms, which are also used for such applications, and which have
certain advantages over FFT. Some of these transforms are the Walsh-type
transforms (Hadamard, Paley, Kaczmarz, Rademacher), cosine, sine,
Haar, slant, Karhunen-Loeve, Reed-Muller, and Chrestenson. Because of
the non-sinusoidal shape of basic orthogonal functions of some of them,
most of the waveform energy is represented by relatively few spectral
coefficients of these transforms. This makes an efficient signal coding
possible. Some transforms make it possible to recognize certain
features in an image, e.g. edge detection.
- ortega91
This paper presents an extended hopfield neural network which has been
applied to design the extra circuitry for testing a digital circuit
during its normal operation, a problem which the authors have shown to
be equivalent to the problem of selecting an optimal set of Reed-Muller
spectral coefficients. It has been suggested that neural networks, in
particular the Hopfield neural network, may be used to solve linear
programming problems. The authors show how a modification of the
Hopfield network structure also allows to solve non-linear programming
problems.
- haddad-rosenberg92
The concept of a generating set of boolean functions was introduced by
S. Kundu recently (1988). Its treatment depends heavily on the choice
of basis for boolean functions (e.g. the familiar basis consisting of
disjunction, conjunction, negation, and the two constants, or the Reed-Muller
basis consisting of the sum mod 2, conjunction, and the two
constants). The authors make the basic ideas more precise and expand
them. The essence is the study of self-maps of (0,1)/sup n/, which is
completely basis independent. Without any additional effort the authors
get the same results for the function of k-valued logic for all
integers k>1. They therefore present it directly in this setting.
- XXX
A new method for (quasi) minimisation of incompletely specified
multiple-output mod-2 sum expressions is presented. It uses a new low-complexity
algorithm for the Reed-Muller transform (RMT). Heuristically
choosing a (quasi-)optimal polarity of the transform, its coefficients
are combined so as to form a locally disjoint RM coefficient cover.
Inverse RMT yields a (quasi)minimal exclusive-OR sum of products. To
exploit common product terms, multiple-output functions are combined to
form a single-output hyperfunction. 'don't cares' are (quasi-)optimally
allotted during the procedure. Since throughout the algorithm only
cubes are to be handled, the method is fast and requires only moderate
storage. It compares favourably with other algorithms both in the
average number of products required and in its computational
complexity. The program HEALEX can handle functions of hundreds of
variables on an AT personal computer.
- kundu92
The synthesis of switching function f(x/sub 1/, x/sub 2/, . . ., x/sub
n/) from a given family of functions g/sub i/(x/sub 1/, x/sub 2/, . .
., x/sub n/), 1 falkowski-perkowski91
An algorithm that converts disjoint cube representation of Boolean
functions into fixed-polarity generalized Reed-Muller expansions (GRME)
is presented. Since the known fast algorithm that generates the GRME
based on the factorization of the Reed-Muller transform matrix always
start from the truth table (minterm) of Boolean function, then the
described method has an advantage due to smaller required computer
memory. Moreover, for the Boolean functions described by only a few
disjoint cubes the method is much more efficient than the fast algorithm.
- saul91
There is interest currently in using Reed-Muller equations as a way of
representing and manipulating switching functions, and as a means of
designing circuits based on exclusive-OR gates. There are only two-level
Reed-Muller minimizers in use, although the need for a multi-level
minimizer has been identified. A procedure for multi-level Reed-Muller
minimization has been developed. It introduces a Reed-Muller
factored form and uses algebraic algorithms for factorization
decomposition, resubstitution, collapsing, and extraction of common
cubes and sub-expressions. The procedure has been implemented in C as a
series of packages which have been added to MISII, and benchmark
comparisons with minimal two-level representations are favorable.
- froessl-eschermann91
Combinational functions involving XOR-operations, e.g. Reed-Muller
forms (RMFs) or parity functions, often yield area-inefficient
realizations when standard synthesis algorithms are used. A specialized
module generator targeted towards such functions was implemented.
XPLAs, the resulting novel PLA-like structures for mixed polarity RMFs,
are compared with conventional PLAs in order to assess whether the
theoretical advantages of RMFs over sum-of-products representations can
be transformed into practical benefits. It is shown that although
testability is a definite plus of these structures, area considerations
will probably restrict the use of RMF minimizers to special applications.
- purwar91
An efficient method for the generation of all the 2/sup n/ sets of
generalized Reed-Muller (GRM) coefficients for a Boolean function f(X)
of n variables using the binary decision diagram (BDD) is presented.
The author describes the generation of RM coefficients from minterm
values and relates them to the associated subfunctions. Examples are
included to illustrate the procedure.
- saul90
The use of the Reed-Muller representation to represent and manipulate
switching functions in logic synthesis systems is discussed. An
algorithm for the minimization of mixed-polarity Reed-Muller
representations to multiple-output incompletely specified switching
functions is presented, in which heuristics are used to determine the
best application of previously known rules for minimizing single-output
equations; rules are used to link multiple-output functions and to
minimize incompletely specified functions. This algorithm has been
implemented, and benchmark comparisons with the best previous
minimization method known shows that the method is faster and results
in smaller representations.
- schaefer-perkowski91
The concept of canonical multiple-valued input generalized Reed-Muller
forms (MIGRM), a direct extension of the well-known generalized Reed-Muller
(GRM) forms for the logic with multiple-valued inputs, is
introduced. Code normalization of single multiple-valued literals (MV-literal)
to perform a final transformation is developed. The code
normalization is used to make the transformation of the complete
function independent on the polarity chosen. This simplifies and speeds
up the main transformation step to the final restricted MIGRM form for
the transformed single MV-literal. A computer program to realize the
MIGRM transform for Boolean functions has been implemented. The direct
circuit realization of MIGRMs as AND- EXOR programmable logic arrays
with input decoders has excellent testability properties; they have
applications to synthesis of other kinds of circuits with EXOR gates,
such as the exclusive sums of products (ESOP), and they have image
processing capabilities.
- falkowski-perkowski91
A new algorithm is given that converts disjoint cube representation of
Boolean functions into fixed-polarity generalized Reed-Muller
expansions (GRME). Since the known fast algorithm that generates the
GRME based on the factorization of the Reed-Muller transform matrix
always starts from the truth table (minterms) of a Boolean function,
the method described has the advantages that come from requiring a
smaller computer memory. Moreover, for the Boolean functions described
by only a few disjoint cubes, the method is much more efficient than
the fast algorithm. The algorithm allows either the calculation of only
selected Reed-Muller coefficients, or all the coefficients can be
calculated in parallel.
- roth-benedek91
A function f:(0, 1)/sup n/ to (0, 1) is called t-sparse if the n-variable
polynomial representation of f over GF(2) contains at most t
monomials. Such functions are uniquely determined by their values at
the so-called critical set of all binary n-tuples of Hamming weight
>or=n-(log/sub 2/t)-1. An algorithm is presented for interpolating any
t-sparse function f, given the values of f at the critical set. The
time complexity of the proposed algorithm is proportional to n, t, and
the size of the critical set. Then, the more general problem of
approximating t-sparse functions is considered, in which case the
approximating function may differ from f at a fraction in of the space
(0, 1)/sup n/. It is shown that O((t/ in ).n) evaluation points are
sufficient for the (deterministic) in -approximation of any t-sparse
function, and that an order of (t/ in )/sup alpha (t, in /).log n
points are necessary for this purpose, where alpha (t, in )>or=0.694
for a large range of t and in . Similar bounds hold for the t-term DNF
case as well. Finally, a probabilistic polynomial-time algorithm is
presented for the in -approximation of any t-sparse function.
- varma-trachtenberg91
Reed-Muller canonical networks are known to be easily testable
implementations of logical functions. The authors present a procedure
to synthesise minimal 0th polarity Reed-Muller networks for
incompletely specified Boolean functions. They also present a procedure
that uses reduced representations of Boolean functions in the form of
logical covers to synthesise Reed-Muller networks. The latter procedure
avoids exponentially long minterm representations, and hence alleviates
some of the difficulties in applying spectral synthesis procedures to
large Boolean functions. Both of these procedures are suitable for automation.
- green91
The existence of a large number of Reed-Muller canonical forms for
switching functions is demonstrated and it is shown that these can be
arranged in a nested hierarchy of families with increasing size and
decreasing general structure. Many of these forms can be derived, and
their weights evaluated for particular functions, by employing
recursively defined incidence matrices operating on an extended form of
truth vector. The more useful forms are also characterized by their
being realizable using a modular circuit tree involving combinations of
1-variable sub-modules.
- almaini91
Tabular techniques are described for the conversion between Boolean
expressions and Reed-Muller polynomials, and for the derivation of
fixed polarities. The techniques are simple, systematic, and can be
used manually or programmed on a computer. Further, they can be used
for any number of variables and hence overcome map limitations.
Computer programs have been developed to implement the algorithms.
- karkouri-aboulhamid90
The principles of test vector generation and fault simulation are
explained with reference to well-chosen examples. Models of stuck-at
and stuck-open faults are compared. Complexity of calculation is
discussed from the aspect of order, polynomial reducibility and NP-completeness.
The generation of the test vectors is considered with
regard to complexity at the switch level. Deductive and concurrent
simulations of faults are compared with other algorithms. Easily
testable circuits are classified including Reed-Muller networks and
augmented programmable logic arrays in particular.
- **
The representation of quaternary switching functions by means of Reed-Muller
algebraic expansions described over the Galois field GF(4) is
discussed. An evaluation of the cost, in terms of basic field
operations, is given for performing the fundamental transforms and for
searching the optimum fixed polarity expansion. The existence of a very
large number of consistent mixed polarity canonical forms is
demonstrated and their basis vectors are listed.
- harking90
The paper presents a new method for computing all 2/sup n/ canonical
Reed-Muller forms (RMC forms) of a Boolean function. The method
constructs the coefficients directly and no matrix-multiplication is
needed. It is also usable for incompletely specified functions and for
calculating a single RMC form. The method exhibits a high degree of
parallelism.
- suman90
A method for defining the Reed-Muller (RM) coefficients of the AND, OR,
exclusive-OR and complementary boolean functions directly from the
individual RM coefficients is presented. Some logical operations on RM
coefficients are also discussed. These results may be useful for
detecting faults in the RM expansion.
- zhang90
An efficient computer algorithm for the minimisation of exclusive-OR
logic functions is presented. The algorithm is n/(1+(n-1)2/sup -n/)
times faster than fast Reed-Muller transform algorithm for minimizing
an exclusive-OR function with n input variables.
- gnativ89
A recurrent representation of matrices of the Reed-Muller transform is
described, which can be used for Hamming and Reed-Muller codes. Coding
and decoding algorithms based on the fast Reed-Muller transform are
proposed. A gain in computational and hardware requirements is
exhibited as compared with the traditional direct methods of coding.
- habib90
Two new efficient algorithms are proposed to convert the minterms of a
switching function to the coefficients of its Reed-Muller polynomial
with fixed polarities. The conversion procedure is based on the use of
Boolean matrix representation. The first algorithm is applied to
generate all the generalized Reed-Muller expansions of the related
switching function and select the optimum solution from them. The
second algorithm is applied to generate directly the minimal
generalized Reed-Muller expansion for a given switching function
without undertaking all possible fixed polarity realizations. The two
algorithms can also be applied to generate the minimal Exclusive-OR
realization in fixed polarity for the incompletely specified functions.
Two fast and efficient computer simulations for the proposed algorithms
have been developed using BASIC programming language, these computer
programs accept the number of the function variables and the minterms
of a switching function and return the minimal Reed-Muller expansion in
fixed polarity. Both algorithms are suitable for large variable
functions for hand and computer simulations. This paper contains
demonstration examples based on the proposed algorithms.
- stankovic-tosic89
A modification is proposed to a 1-out-of-2 multiplexer to yield a logic
module which may be programmed to realize specific requirements in
logic design of switching functions. This programmable universal logic
module is directly applicable for realization of any function f(x) by
sum-of-minimum-terms expression or by Reed-Muller exclusive-OR expansion.
- green90
The set of 3/sup n/ consistent mixed-polarity Reed-Muller canonical
forms of an n-variable switching function is described and the means
whereby each form may be derived by a transform on the zero-polarity
form is investigated. The computational cost of deducing the optimum
polarity expansion is evaluated for various strategies. A ternary map-based
method is introduced which enables this search and other
operations to be performed in a compact and efficient manner.
- green89
The representation of ternary switching functions by means of Reed-
Muller algebraic expansions described over the Galois field GF(3) is
considered. An investigation of the structure of the various fixed
polarity transforms leads to an evaluation of the computational cost of
performing these manipulations. The existence of a large number of
consistent mixed polarity canonical forms is demonstrated and their
basis vectors and transforms are isolated.
- habib89
A new, simple and computationally effective algorithm attempted to
obtain the minimal Reed-Muller exclusive-OR expansion with mixed
polarity of a given switching function, i.e., each product term may
contain variables in complemented and uncomplemented forms. The major
consideration of this algorithm is to obtain a minimum number of
product terms in the exclusive-OR function. The suggested method is
based on the use of Boolean matrix representation, and it is suitable
for completely and incompletely specified functions, large variable
functions and for computer and manual simulation. The author also
describes the computer simulation of the introduced algorithm, which
helps in the detection of the final decomposition of the given
function. Such realizations are described using both manual and
computer simulations.
- damaria-karpovsky
Boolean function realisations by Reed-Muller networks have many
desirable properties in terms of testability. In the paper it is shown
that there exists a single set of test patterns which would detect all
single stuck-at and all single bridging (short-circuit) faults in Reed-Muller
networks, and the number of test patterns is shown to be at most
3n+5, where n is the number of input variables in the function. In the
case of networks with k outputs, where kdamarla89
It is shown that there exists a set of test patterns which can detect
all single stuck-at and all single-bridging (short circuit) faults in
Reed-Muller networks. The number of test patterns is shown to be at
most 3n+5, where n is the number of input variables in the function.
- damarla-karpovsky89
A new approach for fault detection in combinational networks based on
Reed-Muller (RM) transforms is presented. An upper bound on the number
of RM spectral coefficients required to be verified for detection of
multiple stuck-at-faults and single bridging faults at the input lines
of an n-input network is shown to be n. The time complexity (time
required to test a network) for detection of multiple terminal faults
and the storage required for storing the test are determined. An upper
bound is found for the minimum number of test patterns required to
detect a fault. The authors present standard tests based on this
result, with a simple test generation procedure and upper bounds on
minimal numbers of test patterns.
- tran89
A tri-state map is developed as a general format for Karnaugh maps,
Reed-Muller coefficient maps and transition (partially polarised) maps.
The polarisation statuses of the variables in transition maps and Reed-Muller
coefficient maps are indicated by the labels on the tri-state
maps. A variable in a tri-state map can exist in two of three different
states: true, complemented or nonexistent. Karnaugh maps and positive-
polarity or negative-polarity Reed-Muller coefficient maps are special
cases, in which there are only two states. Minimisation of exclusive-OR
switching functions can be carried out, not only on Reed-Muller
coefficient maps, but also on Karnaugh maps or any of the transition maps.
- hu88
The author discusses a map synthesis of ternary functions based upon
Reed-Muller expansion using the ternary b/sub j/ coefficient map.
- reddy-pai88
A new technique using the Reed-Muller transform has been applied for
image data bandwidth compression. The basic concept is derived from the
Reed-Muller canonical expansion of Boolean functions (1954). A fast
algorithm is developed for the computation of the Reed-Muller
transform. Simulation results indicate that the Reed-Muller transform
provides good quality reconstructed images with approximately 2.5 bits
per pixel for monochrome images. The computational efficiency and
simple hardware realization of this transform might make it a viable
candidate for certain real time image data compression applications.
- pitty-salmon88
Mixed-polarity Reed-Muller equations are an alternative to the
traditional sum-of-products form for the representation of switching
functions. The reduction of mixed-polarity Reed-Muller equations is
considered with respect to ensuring input irredundancy.
- hu87
The author proposes two new methods for evaluating the coefficients of
the canonical Reed-Muller expansion for a given multivalued function.
These methods are simple in operation and convenient for memory.
- green87
The structure of Reed-Muller and generalised Reed-Muller transform
matrices is discussed and in particular their description in terms of
the Kronecker matrix product of basic forms is explained. The use of
map-entered variables to enable function maps to be folded into smaller-dimension
structures, thereby easing the transform process, is
investigated. Methods for term-by-term transformation which are
particularly suited to sparse functions are presented and it is shown
that these can be incorporated into the procedures for handling
incompletely specified operational-domain descriptions. The more
general problem of deducing the optimum-polarity expansion of such
functions is also considered.
- latypov86
A method is proposed for modifying the output sequence from a device
being tested by using sequences from a first-order Reed-Muller code,
which allows the number of undetected errors in the output sequence to be lowered.
- hu-Wu87
Synthesis of ternary functions using the proposed ternary universal
logic module U/sub h/s is proposed. A geometric map construction, on
which the b/sub j/ coefficients of the canonical Reed-Muller expansion
for a given ternary function may be plotted, is introduced. It is shown
that such a ternary b/sub j/ coefficient map provides an intuitive
graphic tool for the logic synthesis using U/sub h/. A simple
recurrence formula to derive the transformation matrix evaluating the
3/sup n/ coefficients for a given function is proposed.
- tran87
A graphical method extended from a folding technique developed by X. Wu, X. Chen and S.L. Hurst
(see ibid., vol.129, no.1, p.15-20, 1982) is
used to convert the minterms of a switching function to the
coefficients of its Reed-Muller polynomial with fixed polarity. The
conversion starts from a Karnaugh map and results in a Reed-Muller
coefficient map. An algorithm which attempts to find a minimal
exclusive-OR realisation for the switching function in mixed polarity
by grouping the Reed-Muller coefficient map is presented. The graphical
method of converting minterms to Reed-Muller coefficients and the
minimisation algorithms are also applied to incompletely specified functions.
- fleisher-tavel-yeager87
The algorithm takes as a starting point a function expressed in Reed-
Muller positive canonical form (having no complemented variables),
called the ENF (exclusive normal form). The function is successively
acted on by three operations that have interesting geometrical
significance; unit distance-pair merge, two-distance-pair merge, and
mixed-unit distance-pair merge. This sequence of three operations is
applied to the function n times in succession, where n is the number of
variables. After the nth application, the function will have a minimal
number of terms and a maximal number of complemented variables.
- muzio-Wesselkamper86
The opening chapter of this book sketches the algebraic background to
the subject, defining rings, fields and finite lattices. Later chapters
demonstrate how Boolean algebras may be generalised to befit them for
multiple-values spaces, though only for those whose size is a multiple
of 2, and how Post algebras fulfil the conditions for spaces of other
cardinality. An alternative approach, of Reed and Muller, is discussed,
which employs difference methods on a finite field. A chapter on
functional decomposition explores how large switching functions can be
derived from several subfunctions, and the entire range of techniques
built up through the book is applied in the final chapter to a number
of case studies. Throughout, the book tries to avoid material which is
device- or technology-dependence; but the emphasis is on the
achievement of switching circuits to accomplish required tasks.
- bhattacharya85
The authors investigate whether the function-independent test set for
detecting single stuck-at faults in networks realising Reed-Muller
canonic (RMC) expansions of switching functions is sufficient to detect
all bridging faults in such networks. The investigation, however,
reveals its insufficiency, and to circumvent this propose a technique
of augmenting the network with some additional observation point, so
that a universal test set can be designed for detecting bridging faults
as well.
- zhang-Rayner84
An efficient algorithm for minimisation of Reed-Muller polynomials with
fixed polarities is presented. The common terms of multiple-output
polynomials are considered by applying a number of logical operations
on their coefficients. The minimisation of the polynomials over
extension Galois fields GF(2/sup M/) is considered. The average number
of field multiplications for mapping a set of coefficients is reduced
to less than M.2/sup M-2/.
- wu-Xu84
An expression of switching functions and various transformations in
terms of Kronecker product is discussed. Particularly, the minimization
of functions based upon Reed-Muller expansion under fixed polarities is
considered and the corresponding computer program is derived. The
discussion shows that this algorithm using Kronecker product has
advantages over previous ones. And this together with together with
minimization by means of b/sub j/ map currently proposed by the author
provides a new method for studying Reed-Muller expansion of functions
and their minimization.
- bhattacharya84
The detection problem of bridging faults in AND-EXOR arrays is
considered in this paper in a new framework. These AND-EXOR arrays are
different from the arrays based on the so-called Reed-Muller canonic
(RMC) expansion of functions. The multiple stuck-at fault detection
test set in such arrays as already derived by Pradhan (1978) has been
utilized to detect bridging faults. One most important advantage of
this test set is that it is independent of the function realized and it
has a simple algebraic structure and hence can be generated easily. As
this conventional test set is insufficient to detect all bridging
faults, the authors propose a technique of augmenting the network with
some additional observation points which take care of otherwise
undetectable bridging faults.
- ma84
The logical feature of Searle operations is discussed, an intricate
truth table is given, and by using an analytic method of Boolean logic,
a series of EXCLUSIVE-OR logical transforming formulas of Searle
operations is presented. A logical network design for Searle operations
is worked out, which facilitates further applications of Searle
operations in sequency theory, such as the Fast Walsh Fourier
Transform, and Reed-Muller signal checking, etc. The importance of the
four fundamental carryfree operations for binary numbers and signals is
also briefly discussed.
- besslich83
.
- besslich83
Besslich, P.W.,
"Efficient computer method for ExOR logic design,"
- IEE Proc. E
(GB), vol.130, no.6, 203-6, Nov. 1983.
Application of exclusive-OR logic design suffers from a lack of
straightforward design methods. Recently a procedure using generalised
Reed-Muller (GRM) coefficient maps has been proposed. Based on this
approach, an efficient computer method is developed for the generation
of all 2/sup n/ sets of GRM coefficients of an n-variable Boolean
function. Along with the coefficients a metric may be calculated from
which the minimum cost set according to some criterion may be selected.
The method requires a storage of 2/sup n/ bits and an average of 2/sup
n-1/+n/2 ExOR single-bit operations per set of GRM coefficients.
- mlynarovic83
.
- mlynarovic83
Mlynarovic, M., "Utilization of universal ULM-2 logic modules for logic networks synthesis,"
- Elektrotech. Cas.
(Czechoslovakia), vol.34, no.6, 385-97, 1983.
The paper suggests two methods for designing single output logic
networks with universal logic modules (ULM-2) characterized by the
equation y=y/sub 1/y /sub 3/+y/sub 1/y /sub 2/+y /sub 1/y/sub 2/y/sub
3/. Both the methods are based on the generalized Reed-Muller canonic
forms of the logic function. In the first method, a balanced tree of
ULMs is applied to the realization of the logic function. In the second
method, an algorithm for minimization of the balanced tree of ULMs has
been developed. This algorithm generates a minimum network of ULMs. An
example to illustrate the algorithm features is given.
- mlynarovic83a
Reed-Muller (R-M) expansions of Boolean functions have found extensive
applications in the field of easily diagnosed logic circuits. The
author describes an algorithm for the minimisation of a canonic form of
the expansion which is suitable for high level programming languages.
In comparison with previously described algorithms, the algorithm
presented minimises the capacity of the operational storage required
and is realisable by means of a minimal number of logic operations. The
algorithm has been realised on the SM3/20 computer using the DOS-RV
operating system and its use is demonstrated on a Boolean function with
four variables.
- fujiware83
.
- fujiware83
Fujiware, E.,
"A self-testing group-parity prediction checker and its use for built-in testing,"
- FTCS 13th Annual International Symposium. Fault-Tolerant Computing.
Digest of Papers, 146-53, xxxv+490, 1983, IEEE, New York, USA.
This paper demonstrates a new kind of error checking scheme for
multioutput combinational circuits, and its use for built-in testing
method. In the error checking logic employed, the output from the
circuits being checked is partitioned into several groups. The
predicted group-parity, calculated from the input, is compared with
that produced from the output in each group. This checker, called a
group-parity prediction (GPP) checker, can detect most errors, and can
be implemented by the method which is systematic and uses the Reed-
Muller canonical form in the derivation of the checking conditions and
equations. To ensure that the GPP checker is self-testing, several
conditions are clarified. The self-testing GPP checkers are also
implemented for some concrete examples of multioutput combinational
circuits. With respect to these examples, the self-testing GPP checker
shows, in comparison with simple duplication, almost equally high error
detection ability, fault detection ability, and a lesser hardware gate
amount.
- sarkar-choudhury82
.
- sarkar-choudhury82
Sarkar, S., Choudhury, A.K.,
"An algorithm for finding the minimal Reed-Muller canonic expansion of switching functions,"
- J. Inst. Electron. & Telecommun. Eng.
(India), vol.28, no.9, 462-6, Sept. 1982.
A straightforward method for finding the minimal Reed-Muller Canonic
(RMC) expansion of single output switching functions is suggested. The
method utilizes the concept of Hamming distance to get the minimal
solution(s) according to the established criterion of minimality. An
algorithm has been suggested which is easily amenable to computer
implementation.
- pingDong83
.
- pingDong83
Ping Dong, "The optimization of GMC over GF(p),"
- Proceedings of the Thirteenth International Symposium on Multiple-Valued Logic,
342-7, xii+431, 1983, IEEE, New York, USA.
Deals with the obtaining and optimization of the generalized Reed-
Muller canonical form (GMC) of p-valued logical functions. The basic
ideas involved are the linear transforms of logical functions over
GF(p) and the processing of the spectra thus obtained. The basic
concern is with the convenience of the calculation rather than the
analyticity of the process, so that they can be easily implemented
using a digital computer.
- yamada83
.
- yamada83
Yamada, T.,
"Easily testable AND-EOR combinational logic circuits,"
- Trans. Inst. Electron. & Commun. Eng. Jpn. Part D
(Japan), vol.J66D,
no.1, 105-10, Jan. 1983.
Easily testable combinational circuits, based on AND-EOR (EXCLUSIVE-OR)
realizations for logic functions are presented. Let C/sub n,m//sup 1/
be an n-input and m-output AND-EOR circuit, realizing so-called Reed-
Muller canonic expansions, with a cascade of 2-input EOR gates and an
extra observable output as an additional logic. Then, (n+m+5) tests,
independent of the functions to be realized, are given to detect all of
single stuck-at faults and single bridging faults in C/sub n,m//sup 1/.
Moreover, in an identical circuit C/sub n,m//sup 2/, where EOR sum of
products expressions with both variables and their complements can be
realized, all of the above mentioned faults are detectable by function-
independent (2n+2m+7) tets.
- stankovic82
.
- stankovic82
Stankovic, R.S.,
"A note of the relation between Reed-Muller expansions and Walsh transforms,"
- IEEE Trans. Electromagn. Compat.
(USA), vol.EMC-24, no.1, 68-70, Feb. 1982.
In this note the author shows that there is a direct relation between
the Reed-Muller expansions and orthogonal expansions for Boolean
functions which, from the mathematical point of view, rest upon
completely different bases.
-
.
- wu-Hurst81
Wu, X., Hurst, S.L.,
"A new universal logic gate (ULG3) based on the Reed-Muller canonic
expansion,"
- Int. J. Electron.
(GB), vol.51, no.6, 747-62, Dec. 1981.
Proposes a new and efficient universal logic gate module, the
formulation of which is based upon the Exclusive-OR Reed-Muller
algebraic expansion. In the development of this module, use is made of
a recently proposed geometric construction, whereby the coefficients of
a Reed-Muller expansion may be plotted and manipulated. It is shown
that the new module has a structure which is closely related to a
previously determined universal logic gate, the development of which
was based upon a sum-of-products algebraic basis. Together these two
modules form the most satisfactory general-purpose ULG3 modules which
can be proposed.
- wu-Chen-Hurst82
.
- wu-Chen-Hurst82
Wu, X., Chen, X., Hurst, S.L.,
"Mapping of Reed-Muller coefficients and the minimisation of exclusive-OR-switching functions,"
- IEE Proc. E
(GB), vol.129, no.1, 15-20, Jan. 1982.
A new geometric format, the b/sub j/ coefficient map, is introduced,
the entries in which are the (0, 1) coefficient values of the Reed-
Muller Exclusive-OR expansions by which any given combinatorial
function may be expressed. Although similar in format to the classic
Karnaugh map, the b/sub j/ map entries do not represent the function
output in the same matter as do the minterm entries plotted on a
Karnaugh map. It is shown that this coefficient map structure may
readily be used to generate any required Exclusive-OR realisation of a
given function, and provides a deeper insight into the coefficient
relationships which arise when input variables are complemented in any
Exclusive-OR expansion.
- chul-chong81
.
- chul-chong81
Chul Hwa Paik, Chong Sang Kim,
"RMC forms determination with minimal literals and test sets,"
- J. Korea Inst. Electron. Eng.,
vol.18, no.3, 9-14, June 1981.
A nonexhaustive procedure for obtaining minimally testable Reed-Muller
canonical (RMC) forms with minimal literals of switching functions is
presented. It is shown that this procedure allows nonexhaustive and
near-optimal handling of functions with don't care conditions.
- venkatraman80
.
- venkatraman80
Venkatraman, C.S.,
"Complexity of tree realization of switching functions,"
- Proceedings of the IEEE International Conference on Circuits and Computers ICCC 80
831-3, 612, 1980, IEEE.
This paper briefly investigates the problem of determining complexities
of tree structures for digital switching functions. Applications of
tree structures for the design of fault tolerant, easily testable
switching circuits is gaining importance in recent days, however, a
priori knowledge of its complexity in terms of number of spanning trees
would considerably give an impetus to the most optimal design, which
otherwise could be elusive. An approach based on algebraic graph theory
has been studied. The complexity of a tree structure as a function of
its number of vertices is given. The resulting technique is then
applied to a specific case of tree realization of Reed-Muller expansion.
- page80
.
- page80
Page, E.W.,
"Minimally testable Reed-Muller canonical forms,"
- IEEE Trans. Comput.
(USA), vol.C-29, no.8, 746-50, Aug. 1980.
Arbitrary switching function realizations based upon Reed-Muller
canonical (RMC) expansions have been shown to possess many of the
desirable properties of easily testable networks. While realizations
based upon each of the 2/sup n/ possible RMC expansions of a given
switching function can be tested for permanent stuck-at-0 and stuck-at-
1 faults with a small set of input vectors, certain expansions lead to
an even small test set because of the resulting network topology. In
particular, the selection of an RMC expansion that has a minimal number
of literals appearing in an even number of production terms will give
rise to switching function realization requiring still fewer tests.
This correspondence presents a solution to the problem of selecting the
RMC expansion of a given switching function possessing the smallest
test set.
- lotfi-Tosser79
.
- lotfi-Tosser79
Lotfi, Z.M., Tosser, A.J.,
"Overlapping loops for Reed-Muller expansions in Karnaugh maps,"
- Int. J. Electron.
(GB), vol.46, no.6, 563-7, June 1979.
Symmetries of working states on a Karnaugh map of a logical function
facilitate the choice of overlapping loops, which allows an easy
analysis of the minimum Reed-Muller expressions of the function.
-
.
- lotfi-Tosser79a
Lotfi, Z.M., Tosser, A.J.,
"Systematic method of searching for minimum generalised Reed-Muller
forms using a variable state function,"
- IEE J. Comput. & Digital Tech.
(GB), vol.2, no.5, 210-2, Oct. 1979
A binary function of the state of any variable is introduced to
calculate the number of terms obtained by a generalised Reed-Muller
expansion of a sum of minterms. A systematic method of searching for
the minimum Reed-Muller form is thus available.
- saluja-Ong79
.
- saluja-Ong79
Saluja, K.K., Ong, E.H.,
"Minimization of Reed-Muller canonic expansion,"
- IEEE Trans. Comput.
(USA), vol.C-28, no.7, 535-7, July 1979.
It is shown that Swamy's (1972) approach to generate generalized Reed-
Muller canonic expansion is in error. A different algorithm is
presented which uses a single Boolean matrix and successive
modifications in function vector to generate all the solutions
sequentially.
-
.
- tokmen-Hurst79
Tokmen, V.H., Hurst, S.L.,
"A consideration of universal-logic-modules for ternary synthesis, based
upon Reed-Muller coefficients,"
- Proceedings of the Ninth International Symposium on Multiple-Valued Logic,
248-56, 304, 1979, IEEE, New York, USA.
Ternary switching functions may be realized by the use of universal-
logic-modules ('ULMs'), the specification and use of such modules being
based upon the canonic Reed-Muller ternary expansion. Function
realisation, however, requires computation of the Reed-Muller
coefficients for the particular function being realised. In this paper
a straightforward matrix method of solving the coefficients for any
given ternary function is disclosed. The method does not require the
lengthy solution of 3/sup n/ simultaneous equations, but instead
involves the multiplication of three matrices of order 3/sup m/*3/sup
m/ to determine the 3/sup n/ unknown coefficients, where m=/sup n///sub
2/. The method may be shown to be extendable to any q-ary system, where
q is a power of a prime.
- hlavicka-Klikar78
.
- hlavicka-Klikar78
Hlavicka, J., Klikar, J.,
"Easily tested tree realization of Reed-Muller expansion,"
- FTCS-8. The Eighth Annual International Conference on Fault-Tolerant Computing,
217, xvii+226, 1978, IEEE, New York, USA.
The paper describes a design method which is based on the Reed-Muller
expansion of the given switching function.
- levendel-Breuer78
.
- levendel-Breuer78
Levendel, Y., Breuer, M.A.,
"Mathematical properties of Boolean transformations,"
- Proceedings of the Eighth International Symposium on Multiple-Valued Logic,
163-70, v+298, 1978, IEEE, New York, USA.
This paper is concerned with the study of special aspects of a
transformation which occurs as the 'next state function' in the study
of sequential circuits. To study this function the authors employ three
models, namely a Boolean equation form, a Boolean matrix form, and a
linear matrix form. The latter is based upon the Reed-Muller expansion
of a Boolean function. The major results deal with the study of the
interrelationships between these models as well as the computation of
path and cycle lengths associated with state transitions.
- pradhan78
.
- pradhan78
Pradhan, D.K.,
"A theory of Galois switching functions,"
- IEEE Trans. Comput.
(USA), vol.C-27, no.3, 239-48, March 1978.
Galois switching functions (GSFs) are generalizations of binary
functions in that the input and output variables can assume values over
any finite field. The concepts of minterms, k-cubes and minimal
complexity realizations as related to GSF are introduced. Certain new
mathematical results are presented for determining the coefficients of
generalized Reed Muller expansion of GSF. A partial ordering
relationship between the vectors over a finite field is introduced.
Through this, it is shown that certain known results for binary
functions can be generalized for GSF. Several quasi-exhaustive
algorithms for minimization of binary Reed Muller expansion have been
reported in the literature. Using the results of this paper, these
algorithms can be easily adapted for GSF.
- green-Edkins78
.
- green-Edkins78
Green, D.H., Edkins, M.,
"Synthesis procedures for switching circuits represented in generalised
Reed-Muller form over a finite field,"
- IEE J. Comput. & Digital Tech.
(GB), vol.1, no.1, 27-35, Feb. 1978.
The synthesis of economical multilevel circuits for binary and multiple-
valued switching circuits is described. The mode of function
description is that provided by the algebra of finite fields and this
leads to a highly modular form of circuit representation. A universal-
logic tree composed of GF(q) adders and multipliers is used as a
template on which to construct specific multilevel circuits. The paper
describes methods of assigning the input variables to the network so as
to reduce the complexity of the general tree by removing the redundant
circuit elements. The resulting networks are invariably less costly
than those from the direct synthesis of two-level sum-of-products
expressions and they use only a restricted set of circuit elements.
- pradhan77
.
- pradhan77
"Error control in array processors,"
- 1977 IEEE International Symposium on Information Theory
(papers in
summary form only received), 94, iv+143, 1977, IEEE, New York, USA.
In single-instruction-multiple-data stream operation, each processing
element computes a single function which is identical for all
processors operating in the array. The error-control technique proposed
uses in a novel way generalized Reed-Muller Code for designing fault-
tolerant array processors. It is shown that the resulting output vector
forms a codeword in a higher order code. The output vector is then
decoded for error-correction/detection.
- kodandapani77
.
- kodandapani77
Kodandapani, K.L.,
"Fault location in Reed-Muller canonic networks,"
- Proc. Inst. Electr. Eng. (GB),
vol.124, no.4, 345-8, April 1977.
In the paper, single and multiple-fault locating test sets for Reed-
Miller canonic networks are derived. The fault model assumes stuck-at
faults at the I/O leads of AND gates, and that an EOR gate under a
fault can produce any other function of two inputs other than
equivalence. The results in the paper give an insight into the
complexity of testing of a class of logic networks.
- kodandapani-Setlur77
.
- kodandapani-Setlur77
Kodandapani, K.L., Setlur, R.V.,
"A note on minimal Reed-Muller canonical forms of switching functions,"
- IEEE Trans. Comput.
(USA), vol.C-26, no.3, 310-13, March 1977.
A nonexhaustive procedure for obtaining minimal Reed-Muller canonical
(RMC) forms of switching functions is presented. This procedure is a
modification of a procedure presented earlier in the literature and
enables derivation of an upper bound on the number of RMC forms to be
derived to choose a minimal one. It is shown that the task of obtaining
minimal RMC forms is simplified in the case of symmetric functions and
self-dual functions.
- kodandapani-Pradhan76
.
- kodandapani-Pradhan76
Kodandapani, K.L., Pradhan, D.K.,
"Further results on m-RMC expansions for m-valued functions,"
- 6th International Symposium on Multi-Valued Logic,
88-92, vii+272, 1976, IEEE, New York, USA.
Reed-Muller like canonic (m-RMC) expansions for multivalued functions
have been proposed earlier. For a n-variable m-valued function there
are m/sup n/ expansions. This paper is related to the problem of
finding minimal m-RMC expansions. Each of the expansions are determined
by m/sup n/ unknown coefficients in them. Thus there are altogether
m/sup 2n/ coefficients. It is shown that only (m(m+1))/(2)/sup n/
coefficients are distinct and hence by computing these coefficients one
can determine all the m/sup n/ expansions.
- green-Taylor76
.
- green-Taylor76
Green, D.H., Taylor, I.S.,
"Multiple-valued switching circuit design by means of Generalised Reed-Muller expansions,"
- Digital Processes
(Switzerland), vol.2, no.1, 63-81, Spring 1976.
The theory of Generalised Reed-Muller (GRM) expansions of binary
switching circuits is extended to include multiple valued logics.
Techniques are presented for the construction of the transformation
matrices required in the derivation of the various GRM forms. The
problem of deducing the optimum modifiers for the variables in these
multiple-valued functions is discussed and an example of a computer
search technique for the minimum cost expansion is given.
- edwards75
.
- edwards75
Edwards, C.R.,
"Novel digital integrated-circuit configurations based upon spectral techniques,"
- 1st European Solid State Circuits Conference-ESSCIRC
(Extended abstracts only), 82-3, x+130, 1975, IEE, London, England.
Research into the application of the Rademacher-Walsh transform to
Boolean function classification has shown that the exclusive-OR
operator has a fundamental role to play in the concise definition of
Boolean functions. This result is in accordance with the fact that some
functions may be more elegantly described by the Reed-Muller expansion
than by other means. The author considers the implementation of such
definitions in terms of integrated circuit configurations using EX-OR
gate functions mixed with other gate functions resulting in complex
mixed function gates. Gate circuits are shown.
- benjauthrit-Reed76
.
- benjauthrit-Reed76
Benjauthrit, B., Reed, I.S.,
"Galois switching functions and their applications,"
- IEEE Trans. Comput.
(USA), vol.C-25, no.1, 78-86, Jan. 1976.
The Boolean difference expansion of Boolean algebra is generalized to
finite (Galois) fields. A systematic method is provided for calculating
the coefficients of this type of multivariable polynomial expansion. It
is applied then to the synthesis functions. Applications include
multivalued logics as well as binary valued logics.
- saluja-Reddy75
.
- saluja-Reddy75
Saluja, K.K., Reddy, S.M.,
"Fault detecting test sets for Reed-Muller canonic networks,"
- IEEE Trans. Comput.
(USA), vol.C-24, no.10, 995-8, Oct. 1975.
Fault detecting test sets to detect multiple stuck-at-faults (s-a-
faults) in certain networks, realizing Reed-Muller (RM) canonic
expressions called RM canonic (RMC) networks, are given. The number of
tests which need to be applied to detect t faults, t>or=1, in a network
realising an arbitrary n-variable logic function is determined, these
tests being independent of the function being realised.
- kodandapani-Setlur75
.
- kodandapani-Setlur75
Kodandapani, K.L., Setlur, R.V.,
"Reed-Muller canonical forms in multivalued logic,"
- IEEE Trans. Comput.
(USA), vol.C-24, no.6, 628-36, June 1975.
Canonical forms for m-valued functions referred to as m-Reed-Muller
canonical (m-RMC) forms are a generalization of RMC forms of two-valued
functions are proposed. m-RMC forms are based on the operations
addition mod m and multiplication mod m and do not, as in the cases of
the generalizations proposed in the literature, require an m-valued
function for m not a power of a prime, to be expressed by a canonical
form for M-valued functions, where M>m is a power of a prime. Methods
of obtaining the m-RMC forms the truth vector or the sum of products
representation of an m-valued function are discussed. Using a
generalization of the Boolean difference to m-valued logic, series
expansions for m-valued functions are derived.
- benjauthrit??
.
- benjauthrit??
Benjauthrit, B.,
"Design and diagnosis of Galois logic networks,"
The technology of integrated circuits has raised a great deal of
interest in designing logic networks at the chip or module level. These
types of networks are usually comprised of complex modules instead of
single gates. One interesting approach in designing such networks is to
use generalizations of Boolean logic, namely, finite (or Galois) field
theory. A result of this present study shows how to utilize in logic
design an extended concept of a well-known concept of Boolean
differences, the Reed-Muller expansion. This generalization of the Reed-
Muller expansion is found in a closed-form expression over the Galois
field GF(2/sup n/). Examples are provided to illustrate this type of
logic design, which, for purposes of this study, is designated Galois
logic design.
- pradhan-Patel??
.
- pradhan-Patel??
Pradhan, D.K., Patel, A.M.,
"Reed-Muller like canonic forms for multivalued functions,"
- IEEE Trans. Comput.
(USA), vol.C-24 no.2, 206-10.
In this correspondence the existence of a Reed-Muller like expansion
for multivalued functions is shown. The authors establish that any m-
variable, N-valued function f(x/sub m/,x/sub m-1/,...x/sub 1/) can be
expressed as C/sub 0/+C/sub 1/x/sub 1/+...+...+C/sub N/m/sub -1/x/sub
m//sup N-1/x/sub m-1//sup N-1/x/sub 1//sup N-1/. A matrix method for
determining the coefficients of these expansions is presented. The
problem of finding minimal expression for a given function is
discussed. Finally, a new technique for realizing multiple output
functions is presented.
- pradhan74
.
- pradhan74
Pradhan, D.K.,
"Fault-tolerant carry-save adders,"
- IEEE Trans. Comput.
(USA), vol.C-23 no.12, 1320-2, Dec. 1974.
A design of fault-tolerant carry-save adders is presented. The design
of fault-tolerant carry-save adders is of practical interest since in
most of the modern day computers a carry-save adder is an essential
circuit. The author also indicates how carry-save adders can be well
used as a logic unit and thus some broader application of the design is
illustrated.
- pradham74a
.
- pradham74
Pradham, D.K.,
"A multivalued switching algebra based on finite fields,"
- Proceedings of the 1974 International Symposium on Multi-Valued Logic,
95-112, iv+551, 1974, IEEE, New York, USA.
It is shown that for N a power of a prime number there is an N-valued
algebra where the defined operations are that of finite fields.
Therefore the modular algebra which is complete for N a prime number is
included in this. Furthermore it is established that N-valued switching
functions for N power of a prime number can be expressed in a form
similar to Reed-Muller expansion for binary functions. A minimisation
technique for these functions is discussed. It is also indicated how
certain multiple output switching functions either binary or N-nary,
can be realized as a multi-rail cascade. An expansion technique for
decomposition of these functions is also given.
- kodandapani-Setlur74
.
- kodandapani-Setlur74
Kodandapani, K.L., Setlur, R.V.,
"Multi-valued algebraic generalizations of Reed-Muller canonical forms,"
- Proceedings of the 1974 International Symposium on Multi-Valued Logic,
505-27, iv+551, 1974, IEEE, New York, USA.
A few generalizations of Reed-Muller Canonical forms of switching
functions to multi-valued logic are known. This paper presents another
generalization and computer-oriented algorithms to determine minimal
multi-valued Reed-Muller Canonical forms.
- kodandapani74
.
- kodandapani74
Kodandapani, K.L.,
"A note on easily testable realizations for logic functions,"
- IEEE Trans. Comput. (USA), vol.C-23, no.3, 332-3, March 1974.
It is shown that at most, n+3 tests are required to detect any single
stuck-at fault in an AND gate or a single faulty EXCLUSIVE OR (EOR)
gate in a Reed-Muller canonical form realization of a switching
function.
- fisher74
.
- fisher74
Fisher, L.T.,
"Unateness properties of AND-EXCLUSIVE-OR logic circuits,"
- IEEE Trans. Comput.
(USA), vol.C-23, no.2, 166-72, Feb. 1974.
Reordering the terms of a Reed-Muller or ring sum expansion of a
switching function expressed in terms of the Boolean ring operations
AND and EXCLUSIVE OR in a more natural way exploits the similarities
between these expressions and unate functions and displays mathematical
structure which apparently has not been noted before. McNaughton's n
orderings on the n cube appear in a new setting and lead quickly to
simple but geometrically satisfying theorems dealing with a matrix of
coefficients of all 2/sup n/ ring sum expressions for various
polarities of inputs. The structure of these matrices for minterms,
implicants, and functions are shown to have simple and attractive
forms. An algorithm is presented which allows simple determination of a
ring sum realization using logic array notation, and which can also be
used to find minimum cost polarities. A second algorithm allows
nonexhaustive and near-optimal handling of functions with DON'T CARE
conditions.
- kodandapani73
.
- kodandapani73
Kodandapani, K.K.,
"Rectangular universal cellular array,"
- Electron. Lett.
(GB), vol.9, no.13, 286-7, 28 June 1973.
A rectangular universal array consisting of cells having three inputs
and one output is described. This array is based on the Reed-Muller
canonical expansion of a switching function. Although the total number
of external input pins required in this array is the same as that of a
rectangular array proposed in the literature, the number of cells is
very much less.
- pradhan-Reddy72
.
- pradhan-Reddy72
D.K. Pradhan, Reddy,
"Error-control techniques for logic processors,"
- IEEE Trans. Comput.
(USA), vol. C-21, no. 12, 1331-6, Dec. 1972.
A new error-control technique for logic processors is given. The
proposed technique uses Reed-Muller codes (RMC's). The design scheme
given has better efficiency than the schemes proposed earlier. The
improved efficiency is obtained by relaxing a basic assumption
originally made by Elias. Furthermore, it is shown that the efficiency
of the proposed scheme asymptotically approaches the maximum efficiency
achievable by a practical though restricted class of error-control
schemes. Reliability of the proposed scheme is studied.
- reddy72
.
- reddy72
Reddy, S.M., "Easily testable realizations for logic functions,"
- IEEE Trans. Comput.
(USA), vol. G-21, no.11, 1183-8, Nov. 1972.
Desirable properties of 'easily testable networks' are given. A
realization for arbitrary logic function, using AND and EXCLUSIVE-OR
gates, based on Reed-Muller canonic expansion is given that has many of
these desirable properties. If only permanent stuck-at-0 (s-a-0) or
stuck-at-1 (s-a-1) faults occur in a single AND gate or only a single
EXCLUSIVE-OR gate is faulty, the following results are derived on fault
detecting test sets for the proposed networks: (1) only (n/4) tests,
independent of the function being realized, are required if the primary
inputs are fault-free: (2) only 2n/sub e/ additional inputs (which
depend on the function realized) are required if the primary inputs can
be faulty, where n/sub e/ is the number of variables appearing in even
number of product terms in the Reed-Muller canonical expansion of the
function; and (3) the additional 2n/sub e/ inputs are not required if
the network is provided with an observable point at the output of an
extra AND gate. It is further shown that the networks to generate the
test sets and to interpret the results of testing are simple and easy
to design.
- reddy72
.
- reddy72
Reddy, S.M.,
"Easily testable realizations for logic functions,"
- Digest of Papers from the 1972 International Symposium on
Fault-Tolerant Computing,
126-30, 215, 1972, IEEE, New York, USA.
This paper proposes a canonical form of easily testable logic networks
which requires (n+4) tests, for any arbitrary function of n variables,
to detect any single s-a-0 or s-a-1 fault, under the assumption that
the primary input terminals are fault free. If the primary input
terminals are faulty, at most, 2n/sub e/ additional test inputs are
required where n/sub e/ is the number of variables which appear in even
number of product terms of the Reed-Muller expansion of the function.
It is further shown that these additional tests are unnecessary if the
network is provided with an observable point at the output of an extra
AND gate.
- pradhan-Reddy72
.
- pradhan-Reddy72
Pradhan, D.K., Reddy, S.M.,
"A design technique for synthesis of fault-tolerant adders,"
- Digest of Papers from the 1972 International Symposium on
Fault-Tolerant Computing,
20-4, 215, 1972, IEEE, New York, USA.
A technique for the design of fault tolerant adders using Reed-Muller
codes is presented. In an earlier paper the author (1971) has shown
that Reed-Muller codes are also applicable for correcting faults in
memory of the computers. With the proposed application of Reed-Muller
codes to the design of fault tolerant adders one has one class of codes
applicable to all parts of computers which should prove useful in the
design of fault tolerant computers.
- swamy72
.
- swamy72
Swamy, S.,
"On generalized Reed-Muller expansions,"
- IEEE Trans. Comput.
(USA), C-21, no.9, 1008-9, Sept. 1972.
The generalized Reed-Muller expansions of a switching function are
generated using a single Boolean matrix and step-by-step shifting of
the principal column.
- reed-Chiang70
.
- reed-Chiang70
Reed, I.S., Chiang, A.C.L.,
"Coding techniques for failure-tolerant counters,"
- IEEE Trans. Comput.
(USA), vol.C-19, no.11, 1035-8, Nov. 1970.
This paper delineates an application of two classes of parity-check
codes to the design for failure-tolerant counters. They are (1) a
modified first-order Reed-Muller code and (2) the perfect Hamming code.
The first code employs a majority element for implementing the error-
correcting scheme while the second one makes use of a variable 2/sup j-
2/+1-out-of-2/sup j-1/+1 majority element. These coding techniques can
be applied in principle to other logic hardware to increase its
reliability.
- mukhopadhyay-Schmitz70
.
- mukhopadhyay-Schmitz70
Mukhopadhyay, A., Schmitz, G.,
"Minimization of EXCLUSIVE OR and LOGICAL EQUIVALENCE switching circuits,"
- IEEE Trans. Comput.
(USA), vol.C-19, no.2, 132-40, Feb. 1970.
Attempts to develop minimization algorithms for switching circuits
based on Reed-Muller canonic forms. In particular, algorithms are
presented for obtaining minimal modulo 2 or complement modulo 2 sum-of-
products (or sums) expressions of any arbitrary single-output or
multiple-output switching function with fixed polarities of the input
variables.
- matsuda-Shibata91
.
- matsuda-Shibata91
Matsuda, K., Shibata, J.,
"Optoelectronic approach to optical parallel processing based on the
photonic parallel memory (PPM),"
- Proc. SPIE - Int. Soc. Opt. Eng.
(USA), vol.1562, 21-9, 1991.
A photonic parallel memory (PPM), an array of optoelectronic bistable
switches, was proposed for application to optical parallel processing.
Each of the switches consists of a heterojunction phototransistor (HPT)
and a light-emitting diode (LED). In addition to the electrically
erased PPM having only switches, an optically erasable PPM (OE-PPM)
with functions of optical write-in, read-out and erasing was
fabricated. The optical reset function was attained by an additional
HPT connected to the switch electrically in parallel. The PPM can be
used not only as a memory but as a logic gate. An optical parallel
logic gate executing exclusive OR (EOR) was proposed as an application
of the OE-PPM. The EOR operation with optical input and output was
implemented.
****************************************8
- robinson89
.
- robinson89
Robinson, J.P.,
"Circular built-in self-test,"
- Northcon/89 Conference Record,
290-4, iii+460, 1989,
Electron. Conventions Manage, Ventura, CA, USA.
Describes work in progress which seems to have practical importance.
The boundary scan register is modified to a circular shift register
where the the lower register stages are the inputs to the unit and each
logic output is exclusive-ored between two higher register stages. The
ordering of EOR gates and flip-flops is as suggested by boundary scan
structures.
*****************************8
- kundu-Reddy90
.
- kundu-Reddy90
Kundu, S., Reddy, S.M.,
"Robust tests for parity trees,"
- J. Electron. Test., Theory Appl.
(Netherlands), vol.1, no.3, 191-200, Oct. 1990.
Linear logic circuits are used extensively in digital computing and
signal processing systems. They are constructed as regular arrays (for
example as cascade or tree circuits), employing linear gates such as
Exclusive OR (EOR) and Exclusive NOR (ENOR) gates. Earlier studies on
fault diagnosis in linear logic circuits were based on the classical
fault model of line stuck-at faults. Transistor stuck-open (SOP) and
stuck-on (SON) faults in linear circuits were studied recently, but the
effect of signal transients due to circuit delays and time skews in
input changes were not considered in the derivation of test sequences.
These latter factors are known to cause invalidation of two pattern
tests for stuck-open faults. This article considers the problem of
generating robust tests for linear logic circuits. These tests are not
affected by circuit transients caused by delays. A major finding in
this paper is that, if the test invalidation problem is redressed by
introducing robust tests, the test length becomes a linear function of
the depth of the circuit as opposed to the constant number of tests
derived in previous studies, by neglecting circuit transients. A lower
bound on minimum number of distinct test patterns needed for a tree of
EOR gates of depth d is derived. This number depends on the specific
implementation of the gate. Robust test-generation procedures are
proposed for both single and multiple fault models and their
optimalities are argued. Given that every gate in a parity tree is
robustly testable, a test sequence that can test for all faults in the
circuit, regardless of the nature of gate implementation, is called
universal robust test sequence for a parity tree. Finally the authors
propose an optimal universal robust test sequence.
*******************************8
- kamiyama90
.
- kamiyama90
Kamiyama, H., Shouno, A., Umemoto, Y., Kamiya, T.,
"Very fast integrated optoelectronic logic for parallel computation using photodiode gates,"
- Jpn. J. Appl. Phys. 2, Lett.
(Japan), vol.29, no.7, 1248-51, July 1990.
A new configuration of an integrated optoelectronic logic unit using
GaAs photodiode gates is proposed. Implementation of AND and EOR logic
units are performed monolithically using GaAs/AlGaAs multilayer
structures. Discussions are made on the realization of the full adder
by means of optical feedback between the photodiode logic array and the
surface emitting diode laser array.
**********************************
- itoh-Tsujii89
.
- itoh-Tsujii89
Itoh, T., Tsujii, S.,
"Structure of parallel multipliers for a class of fields GF(2/sup m/),"
- Inf. Comput.
(USA), vol.83, no.1, 21-40, Oct. 1989
Presents a configuration of parallel multipliers for GF(2/sup m/) based
on canonical bases. The possible parallel multipliers by the proposed
configuration are limited to a class of fields GF(2/sup m/). However
they can be constructed by O(m/sup 2/) AND-gates and O(m/sup 2/) EOR-
gates with the structural modularity (this is a desirable feature for
the hardware implementation), and their operation time is about (log m)
T, where m is the dimension of GF(2/sup m/) and T is the delay time of
an EOR-gate. In order to construct such parallel multipliers, the
authors define two types of polynomials of special form over GF(2), one
is called all one polynomial (denoted by AOP) and the other is called
equally space polynomial (denoted by ESP). Furthermore, they show a
necessary and sufficient condition for ESPs to be irreducible over
GF(2) and the uniqueness of the irreducible ESPs over GF(2). Finally,
they propose the configuration of parallel multipliers for a class of
fields GF(2/sup m/) based on irreducible AOPs and ESPs over GF(2).
*****************************8
- wen-Wang89
.
- wen-Wang89
Wen, K.A., Wang, J.F.,
"Efficient computing methods for parallel processing: an implementation
of the Viterbi algorithm,"
- Comput. Math. Appl.
(UK), vol.17, no.12, 1511-21, 1989.
Efficient computing methods are exploited for parallel processing of
the most important trellis search algorithm, i.e. the Viterbi decoding
algorithm (VA). The complicated data transfer scheme and the rather
time-consuming computations caused by dynamic trellis search procedures
are reorganized into matrix operations. The well-developed systolic
processors for matrix operations can be well adapted to implement the
whole decoding procedures of VA. A certain amount of AND/EOR operations
for maximum likelihood estimation are saved. Flexible time/area
performances are provided and T times speedup can be obtained with T
consecutive stages being parallelized.
************************************
- IBM
.
- IBM
"Cross-coupled FET exclusive-OR/compare circuit,"
- IBM Tech. Disclosure Bull.
(USA), vol.28, no.4, 1572-3, Sept. 1985.
The circuit described, which offers substantial improvement over the
conventional EOR circuit, consists of two cross-coupled FET switch
devices with a load device.
- yamada83
.
- yamada83
Yamada, T.,
"Easily testable AND-EOR combinational logic circuits,"
- Trans. Inst. Electron. & Commun. Eng. Jpn.
Part D (Japan), vol.J66D,
no.1, 105-10, Jan. 1983
Easily testable combinational circuits, based on AND-EOR (EXCLUSIVE-OR)
realizations for logic functions are presented. Let C/sub n,m//sup 1/
be an n-input and m-output AND-EOR circuit, realizing so-called Reed-
Muller canonic expansions, with a cascade of 2-input EOR gates and an
extra observable output as an additional logic. Then, (n+m+5) tests,
independent of the functions to be realized, are given to detect all of
single stuck-at faults and single bridging faults in C/sub n,m//sup 1/.
Moreover, in an identical circuit C/sub n,m//sup 2/, where EOR sum of
products expressions with both variables and their complements can be
realized, all of the above mentioned faults are detectable by function-
independent (2n+2m+7) tets.
*****************************
- krauss81
.
- krauss81
Krauss, K.-H.,
"Microcomputer produce code words without shift register,"
- Siemens Components
(Engl. Ed.) (Germany), vol.16, no.1, 16-20, March 1981.
Shows the possibility of generating linear codes by summing up so-
called generator words using Exclusive-OR links. For this purpose the
generator words must be available as a table in a ROM. This coding
method is very flexible and can easily be programmed using simple
instructions of a processor. The cyclic Hamming Code with a code length
of 63 bits (57 information positions and 6 control positions) is taken
as an example to demonstrate this method with microprocessor S A B 8085.
***************8
- saluja80
.
- saluja80
Saluja, K.K.,
"Synchronous sequential machines: a modular and testable design,"
- IEEE Trans. Comput.
(USA), vol.C-29, no.11, 1020-5, Nov. 1980.
It is shown that a single-input n-definite machine realized by a
universal modular tree, in which each module consists of AND-EXCLUSIVE-
OR-DELAY (AND-EOR-DELAY) as a basic element, can be tested for single
stuck-type-faults by tests of length 2n+3 only. This is a marked
improvement over the previous results for trees consisting of AND-OR-
DELAYS, which are known to have test lengths of exponential growth. The
author also shows that the test sequences are obtainable from the
combinational trees and are easy to construct. The results derived for
n-definite machines are extended to derive tests of length 2(k+1)n+2
for single- and multiple-input arbitrary sequential machines realized
as single-feedback loop trees, when k is the number of inputs. The
problem of reduction of control inputs is also considered.
****************
- kumamoto-Henley78
.
- kumamoto-Henley78
Kumamoto, H., Henley, E.J.,
"Top-down algorithm for obtaining prime implicant sets of non-coherent fault trees,"
- IEEE Trans. Reliab.
(USA), vol.R-27, no.4, 242-9, Oct. 1978.
An algorithm for finding all the prime implicant sets is given for non-
coherent fault trees involving gates other than simple AND and OR,
e.g., EOR and NOT. The sets are a generalization of min cut sets and
can be used in quantitative and/or qualitative system reliability
analysis. The algorithm is a top-down analysis and avoids sum of
product expressions of top event, which usually involve a large number
of terms. Each step of the algorithm is clearly defined and it is
proven that all prime implicant sets can be obtained. The algorithm is
efficient, and rather complicated trees can be handled manually.
******************
- kodandapani77
.
- kodandapani77
Kodandapani, K.L.,
"Fault location in Reed-Muller canonic networks,"
- Proc. Inst. Electr. Eng.
(GB), vol.124, no.4, 345-8, APRIL 1977.
In the paper, single and multiple-fault locating test sets for Reed-
Miller canonic networks are derived. The fault model assumes stuck-at
faults at the I/O leads of AND gates, and that an EOR gate under a
fault can produce any other function of two inputs other than
equivalence. The results in the paper give an insight into the
complexity of testing of a class of logic networks.
**********
- seth-Kodandapani77
.
- seth-Kodandapani77
Seth, S.C., Kodandapani, K.L.,
"Diagnosis of faults in linear tree networks,"
- IEEE Trans. Comput.
(USA), vol.C-26, no.1, 29-33, Jan. 1977
The problem of fault detection and location in tree networks of two
input EXCLUSIVE-OR (EOR) gates is considered. The fault model assumes
that an EOR gate can change to any other function of its two inputs
except the equivalence function. An efficient procedure for single
fault location is presented. In the worst case the number of tests
necessary to locate single faults is bounded by a linear function of
the number of input variables. Constructive upper bounds are obtained
for the number of tests to detect multiple faults. Optimality of these
bounds is argued and extension of results to other types of networks is
considered.
**************
- yamamoto75
.
- yamamoto75
Yamamoto, M.,
"Some considerations on the identification of combinational cellular logic arrays,"
- Syst. Comput. Control
(USA), vol.6, no.4, 56-62, July-Aug. 1975.
Investigates the identification problems of Maitra cascades and
nonredundant tree-type networks which are formed of two-input, one-
output AND cells, OR cells, and exclusive-OR (EOR) cells. First, if the
structural graph of a Maitra cascade (or nonredundant tree-type
network) that describes the connections of each cell and the input
variables is known, then Algorithm I (or Algorithm II) is derived for
identifying each cell of the network uniquely by the truth table of the
logical function realized by the network. Second, if the structural
graph of a network is known, the author presents a subset of its truth
table that can identify the network uniquely. The paper also gives an
upper bound on the number of input patterns in the subset.
************
- saluja-Reddy74
.
- saluja-Reddy74
Saluja, K.K., Reddy, S.M.,
"Easily testable two-dimensional cellular logic arrays,"
- IEEE Trans. Comput.
(USA), vol.C-23, no.11, 1204-7, Nov. 1974.
An algorithm to synthesize two dimensional AND-EOR arrays is given. The
design criterion chosen is to minimize the number of columns in the two
dimensional cellular arrays. It is also shown that AND-EOR arrays,
synthesized using the algorithm presented, can be modified such that
2n+5 test vectors will detect any single fault in the array realizing
an n-variable function with only one observable output. Furthermore,
this test set is shown to be independent of the function being realized
by the cellular array under test.
********************************8
- kodandapani74
.
- kodandapani74
Kodandapani, K.L.,
"A note on easily testable realizations for logic functions,"
- IEEE Trans. Comput.
(USA), vol.C-23, no.3, 332-3, March 1974.
It is shown that at most, n+3 tests are required to detect any single
stuck-at fault in an AND gate or a single faulty EXCLUSIVE OR (EOR)
gate in a Reed-Muller canonical form realization of a switching
function.
- xx
Besslich, Ph.W.: "Efficient Computer Method for EXOR Logic Design",
Proc. IEE,
Vol. 130, Part E, CDT, No. 6., pp. 203-206, 1983.
- xx
Besslich P.: "Heuristic minimization of multiple-valued logic functions:
a direct cover approach",
IEEE Trans. on Comp., February 1986, pp. 134-144.
- xx
Bhavsar, D., and R.W. Heckelman:
"Self-testing by polynomial division",
Proc. 1981 IEEE Test Conference,
pp. 208-216, 1981.
- xx
Bioul, G., Davio, D., and J.P. Deschamps:
"Minimization of ring-sum expansions of Boolean functions",
Philips Research Report,
Vol. 28, pp. 17-36, 1973.
- xx
Brayton, R.K. Hachtel, G.D. McMullen, C.T. and
A.L. Sangiovanni-Vincentelli:
Logic Minimization Algorithms for VLSI Synthesis,
Boston, MA, Kluwer, 1984.
- xx
Brayton, R.K., Camposano, R., De Micheli, G., Otten, R.H.J.M.,
and J. Van Eijndhoven:
"The Yorktown Silicon Compiler System",
Chapter 7 in Gajski, D., (ed),
Silicon Compilation,
1987.
- xx
Calingaert, P.:
"Switching function canonical forms based on commutative and
associative binary operations",
AIEE Trans.
Vol. 79, pp. 808-814,
January 1961.
- xx
Carter, W.C., Wadia, A.B., and D.C. Jessep, Jr.:
"Implementation of Checkable Acyclic Automata by Morphic Boolean Functions",
Proc. of the Symp. on Computers and Automata,
Polytechnic Institute of Brooklyn, p. 645, 1971.
- xx
Chan, A.H.:
"Using decision trees to derive the complement of a binary
function with multiple-valued inputs,"
IEEE Trans. on Comp.,
Vol. C-36, pp. 212 - 214, Febr. 1987.
- xx
Ciesielski, M.J. Perkowski, M.J., and S. Yang: "PALMINI-MV:
An Approach to Multiple-Valued Logic
Minimization Based on Graph Coloring".
Technical Report. Univ. of Massachusetts.
.
- xx
Cohn, M.:
"Inconsistent canonical forms of switching functions",
IRE Trans. Electron. Comput.,
Vol. EC-11, p. 284, April 1962.
.
- xx
Davio, M.: "Ring-Sum Expansions of Boolean Functions",
Proc. of the Symp. on Computers and Automata,
Polytechnic Institute of Brooklyn, April 13-15, pp. 411-418, 1971.
.
- xx
Davio, M., Deschamps, J.P., and A. Thayse:
"Discrete and Switching Functions",
McGraw-Hill Book Co.,
Inc., New York, 1978.
.
- xx
DeMicheli, G., Brayton, R.K. and A. Sangiovanni-Vincentelli:
"Optimal State Assignment for
Finite State Machines",
IEEE Trans. on CAD,
Vol. CAD-4, No. 3,
July 1985, pp. 268-284.
.
- xx
DeMicheli, G.: "Symbolic Design of Combinational
and Sequential Logic Circuits Implemented
by Two-Level Logic Macros",
IEEE Trans. on CAD,
Vol. CAD-5, No. 4., Oct. 1986, pp. 597-616.
.
- xx
Dueck, G., and D. Miller: "A 4-valued PLA using a Modsum",
Proc. of ISMVL-86.
.
- xx
Dueck, G., and D. Miller: "A direct cover multiple-valued minimization using
the truncated sum",
Proc. of ISMVL-87.
.
- xx
Even, S., Kohavi, I., and A. Paz:
"On minimal modulo-2 sum of products for switching functions",
IEEE Trans. on Electron. Computers,
pp. 671-674, October 1967.
.
- xx
Fleisher, H., Tavel, M., and J. Yeager:
"Exclusive-OR representations of Boolean functions",
IBM J. Res. Develop.,
Vol. 27, pp. 412-416, July 1983.
.
- xx
Fleisher, H., Tavel, M., and J. Yeager:
"A Computer Algorithm for Minimizing Reed-Muller Canonical Forms",
IEEE Trans. on Computers,
Vol. C-36, No. 2, February 1987.
.
- xx
Fujiwara, H.:
"Logic Testing and Design for Testability",
Computer System Series, The MIT Press, 1986.
.
- xx
Hayes, J.P.: "On modifying logic networks to improve
their diagnosability",
IEEE Trans. Comput.
Vol. C-23, No. 1, pp. 56-62, 1974.
.
- xx
Kodandapani, K.L., and R.V. Setlur:
"A note on minimum Reed-Muller canonic forms of switching functions",
IEEE Trans. Comp.,
Vol. C-26, pp. 310-313, 1977.
.
- xx
Mukhophadhyay, A., and G. Schmitz:
"Minimisation of exclusive-OR and logical equivalence switching
circuits",
IEEE Trans. Comp.,
Vol. C-19, No. 2. , pp. 132-140, February 1970.
.
- xx
Papakonstantinou, G.:
"Minimization of modulo-2 sum of products",
IEEE Trans. on Computers.,
Vol. C-28, pp. 163-167, February 1979.
.
- xx
Pradhan, D.K.:
"Universal test sets for multiple fault detection in AND-EXOR arrays",
IEEE Trans. on Comput.,
Vol. C-27, No.2., pp. 181-187, 1978.
.
- xx
Pomper, G., and J. Armstrong: "Representation of multivalued functions
using the direct cover approach",
IEEE Trans. on Comp., Sept. 1981, pp. 674-679.
.
- xx
Pradhan, D.K.: "Fault-Tolerant Computing. Theory and Techniques. Vol. I." Prentice-Hall, 1987.
.
- xx
Ramamoorthy, C.V.:
"Procedures for minimization of "exclusive or" and "logical equivalence"
switching circuits",
IEEE Symp. on Switching Circuit Theory and Logical Design,
pp. 143-149, October 1965.
.
- xx
Robinson, J.P., and C.L. Yeh:
"A Method for modulo-2 Minimization",
IEEE Trans. on Computers,
Vol. C-31, pp. 800-801, August 1982.
.
- xx
Roth, P.: "Computer Logic, Testing and Verification",
Rockville, MD: Computer Science, 1980.
.
- xx
Rudell, R.L., and A.L. Sangiovanni-Vincentelli:
"ESPRESSO-MV: algorithms for multiple-valued logic minimization,
Proc. IEEE Custom Integrated Circuits Conf., 1985.
.
- xx
Rudell, R.:
"Multiple-Valued Logic Minimization for PLA Synthesis",
M.S. Report, June 5, 1986. University of California, Berkeley
California 94720.
.
- xx
R.L. Rudell, and A.L. Sangiovanni-Vincentelli,
"Multiple-valued minimization for PLA optimization,"
Proc. Intern. Symp. on Multiple-Valued Logic,
pp. 198-208, May 26-28, Boston, MA, 1987.
.
- xx
Saluja, K.K., and S.M. Reddy:
"Fault detecting test sets for Reed-Muller canonic networks",
IEEE Trans. Comput.,
Vol. C-24, No. 10., pp. 995-998, 1975.
.
- xx
Sasao, T.: "An application of multiple-valued
logic to a design of Programmable Logic Arrays",
Proc. 8th Intern. Symp. on Multiple-Valued Logic (ISMVL), 1978.
.
- xx
Sasao, T.:
"Multiple-valued decomposition of generalized boolean
functions and the complexity of programmable logic arrays,"
IEEE Trans. Comput.,
Vol. C-30, pp. 635-643, Sept. 1981.
.
- xx
Sasao, T.:
"Input variable assignment and output phase optimization
of PLA's,"
IEEE Trans. Comput.,
Vol. C-33, pp. 879 - 984, Oct. 1984.
.
- xx
Sasao, T.:
"Bounds on the average number of products in the minimal Sum-of-Products
expressions for multiple-valued input two-valued output functions,"
Proc. Intern. Symp. on Multiple-Valued Logic,
pp. 260-267, May 26-28, Boston, MA, 1987.
.
- xx
A. Mukhopadhyay,
Recent Developments in Switching Theory
(Academic Press, New York, London, 1971).
.
- xx
Brayton, R. K. Rudell, R. Sangiovanni-Vincentelli, A.,
and A.R. Wang,
MIS: Multi-Level Interactive Logic Optimization System
IEEE Trans. on CAD,
6 (6) (1989) 1062-1082.
.
- pan1
Fujiwara, H.
``Logic Testing and Design for Testability''
- MIT Press
, 1985.
.
- pan2
Pradhan, D. K.
``Universal Test Sets for Multiple Fault Detection in AND-EXOR Arrays''
- IEEE Transactions on Computers
, V. C-27, No. 2, February 1978.
.
- pan3
A Davio, M., Deschamps, J. P., and Thayse, A.
``Discrete and Switching Functions''
- Mc-Graw-Hill
, 1978.
.
- pan4
Reed, I. S.
``A Class of Multiple-Error-Correcting Codes and Their Decoding Scheme''
- IRE Transactions on Information Theory
, V. PGIT-4, pp. 38-49, 1954.
.
- pan5
Muller, D. E.
``Application of Boolean Algebra to Switching Circuit Design and to Error Detection''
- IRE Transactions on Electronic Computers
, V. EC-3, pp. 6-12, September 1954.
.
- pan6
Perkowski, M. A.
``The Generalized Orthonormal Expansion of Functions With Multiple-Valued''
Inputs and Some of its Applications
- ISMVL'92
, pp. 442- 450, June 1992.
.
- pan7
Reddy, S. M.
``Easily Testable Realization for Logic Functions''
- IEEE Transactions on Computers
, V. C-21, No. 11, pp. 1183-1188, November 1972.
.
- pan8
Kodandapani, K. L.
``A Note on Easily Testable Realizations for Logic Functions''
- IEEE Transactions on Computers
, V. C-23, pp. 332-333, 1974.
.
- pan9
Saluja, K. K. and Reddy, S. M.
``Fault Detecting Test Set for Reed-Muller Canonic Networks''
- IEEE Transactions on Computers
, V. C-24, No. 10, pp. 995-998, 1975.
.
- pan10
Saluja, K. K.
``A Study of Combinational Networks Based on Reed-Muller Canonic Forms''
- Ph.D. Dissertation, University of Iowa, Iowa City
, 1973.
.
- pan11
Bhattacharya, B. B., Gupta, B., Sarkar, S., and Choudhury, A. K.
``Testable Design of RMC Networks with Universal Tests for Detecting Stuck-at and Bridging Faults''
- IEE Proceedings
, V. 132, Part E, No. 3, pp. 155-161, May 1985.
.
- pan12
Damarla, T., Karpovsky, M.
``Detection of Stuck-at and Bridging Faults and Bridging Faults in Reed-Muller Canonical (RMC) Networks''
- IEE Proceedings
, V. 136, Part E, No. 5, pp. 430-433, September 1989.
.
- pan13
Perkowski, M. A., Csanky, L., Sarabi, A., and Sch\*:afer, I.
``Fast Minimization of Mixed-Polarity AND/XOR Canonical Networks''
- Proceedings of ICCD'92
, pp. 33-36, Cambridge, MA, October 1992.
.
- pan14
Hayes, J. P.
``On Realization of Boolean Functions Requiring a Minimal or Near-Minimal Number of Tests''
- IEEE Transactions on Computers
, V. C-20, No. 12, pp. 1506-1513, December 1971.
.
- pan15
A Seth, S. C. and Kodandapani, K. L.
``Diagnosis of Faults in Linear Tree Networks''
- IEEE Transactions on Computers
, V. C-26, No. 1, pp. 29-33, anuary 1977.