Pseudo-Boolean Constraint Formulation of Symmetry Boolean Encoding for Multi-Valued Function
Date Issued
2011
Date
2011
Author(s)
Li, Meng-Yen
Abstract
In high level designs, variables are often represented
in the form of symbolic multi-values. The realization of
multi-valued logic in bit level is called encoding and
selecting the appropriate encoding would be a challenging
and difficult problem. Prior literatures showed that it is
hard to foresee the effect of chosen encoding after powerful
logic optimization.
To the best of our knowledge, choosing encoding biased
for some special functional property is never studied
before except minimizing area. Since symmetry is the most studied and applied functional property, we would like
weave this property into encoding when implement
multi-valued function. Symmetric Boolean functions have
many useful applications in various aspects. In cryptography, they have special cryptographic parameters.
It is easier to optimize symmetric functions in physical
design domain. They also applied in fault testability in
BDD based synthesis.
In this work, we define and study the Symmetry Encoding
Problem (SEP) as a problem to maximize the symmetries of
encoded function when realizing multi-valued function. We
also propose a systematic method to model the SEP into Pseudo-Boolean Constraint (PBC). Using existing constraint
optimizer like IBM ILOG CPLEX Optimizer(TM) we can solve
and generate the solution of SEP. Besides totally symmetric
function, the method can also target for partially
symmetric function.
Experiments show that by PBC solving, the symmetric
encoding generated will encode multi-valued function with
more symmetries in a large portion of test cases while
compared with naive encoding (encode multi-value in binary
representation directly). This method has promising result
for small size circuits, which has less than 6 of inputs
after encoding (up to 64 multi-values). However it has critical weaknesses, i.e. scalability. This method is also
not available for multiple outputs. We would like overcome
these weaknesses in future work.
Subjects
symmetry
encoding
Pseudo-Boolean Constraint
Type
thesis
File(s)![Thumbnail Image]()
Loading...
Name
ntu-100-R97943160-1.pdf
Size
23.32 KB
Format
Adobe PDF
Checksum
(MD5):8cb84f9bb56b08f7598e2a8ef2a152e2