Abstract: Structural representation and technology mapping of
a Boolean function is an important problem in the design of nonregenerative
digital logic circuits (also called combinational logic
circuits). Library aware function manipulation offers a solution to
this problem. Compact multi-level representation of binary networks,
based on simple circuit structures, such as AND-Inverter Graphs
(AIG) [1] [5], NAND Graphs, OR-Inverter Graphs (OIG), AND-OR
Graphs (AOG), AND-OR-Inverter Graphs (AOIG), AND-XORInverter
Graphs, Reduced Boolean Circuits [8] does exist in
literature. In this work, we discuss a novel and efficient graph
realization for combinational logic circuits, represented using a
NAND-NOR-Inverter Graph (NNIG), which is composed of only
two-input NAND (NAND2), NOR (NOR2) and inverter (INV) cells.
The networks are constructed on the basis of irredundant disjunctive
and conjunctive normal forms, after factoring, comprising terms with
minimum support. Construction of a NNIG for a non-regenerative
function in normal form would be straightforward, whereas for the
complementary phase, it would be developed by considering a virtual
instance of the function. However, the choice of best NNIG for a
given function would be based upon literal count, cell count and
DAG node count of the implementation at the technology
independent stage. In case of a tie, the final decision would be made
after extracting the physical design parameters.
We have considered AIG representation for reduced disjunctive
normal form and the best of OIG/AOG/AOIG for the minimized
conjunctive normal forms. This is necessitated due to the nature of
certain functions, such as Achilles- heel functions. NNIGs are found
to exhibit 3.97% lesser node count compared to AIGs and
OIG/AOG/AOIGs; consume 23.74% and 10.79% lesser library cells
than AIGs and OIG/AOG/AOIGs for the various samples considered.
We compare the power efficiency and delay improvement achieved
by optimal NNIGs over minimal AIGs and OIG/AOG/AOIGs for
various case studies. In comparison with functionally equivalent,
irredundant and compact AIGs, NNIGs report mean savings in power
and delay of 43.71% and 25.85% respectively, after technology
mapping with a 0.35 micron TSMC CMOS process. For a
comparison with OIG/AOG/AOIGs, NNIGs demonstrate average
savings in power and delay by 47.51% and 24.83%. With respect to
device count needed for implementation with static CMOS logic
style, NNIGs utilize 37.85% and 33.95% lesser transistors than their
AIG and OIG/AOG/AOIG counterparts.
Abstract: The human friendly interaction is the key function of a human-centered system. Over the years, it has received much attention to develop the convenient interaction through intention recognition. Intention recognition processes multimodal inputs including speech, face images, and body gestures. In this paper, we suggest a novel approach of intention recognition using a graph representation called Intention Graph. A concept of valid intention is proposed, as a target of intention recognition. Our approach has two phases: goal recognition phase and intention recognition phase. In the goal recognition phase, we generate an action graph based on the observed actions, and then the candidate goals and their plans are recognized. In the intention recognition phase, the intention is recognized with relevant goals and user profile. We show that the algorithm has polynomial time complexity. The intention graph is applied to a simple briefcase domain to test our model.
Abstract: This paper presents an improved variable ordering method to obtain the minimum number of nodes in Reduced Ordered Binary Decision Diagrams (ROBDD). The proposed method uses the graph topology to find the best variable ordering. Therefore the input Boolean function is converted to a unidirectional graph. Three levels of graph parameters are used to increase the probability of having a good variable ordering. The initial level uses the total number of nodes (NN) in all the paths, the total number of paths (NP) and the maximum number of nodes among all paths (MNNAP). The second and third levels use two extra parameters: The shortest path among two variables (SP) and the sum of shortest path from one variable to all the other variables (SSP). A permutation of the graph parameters is performed at each level for each variable order and the number of nodes is recorded. Experimental results are promising; the proposed method is found to be more effective in finding the variable ordering for the majority of benchmark circuits.
Abstract: This paper reviews various approaches that have been
used for the modeling and simulation of large-scale engineering
systems and determines their appropriateness in the development of a
RICS modeling and simulation tool. Bond graphs, linear graphs,
block diagrams, differential and difference equations, modeling
languages, cellular automata and agents are reviewed. This tool
should be based on linear graph representation and supports symbolic
programming, functional programming, the development of noncausal
models and the incorporation of decentralized approaches.