Sequence Compaction to Preserve Transition Frequencies Page: 4 of 16
This report is part of the collection entitled: Office of Scientific & Technical Information Technical Reports and was provided to Digital Library by the UNT Libraries Government Documents Department.
The following text was automatically extracted from the image on this page using optical character recognition software:
Accuracy of compaction requires preserving the transition probabilities of all
transitions. In , Marculescu et al. prove that satisfying the condition
p(t) - p'(t)I < E (1)
for all transitions, limits the error in estimation to O(E), where c is an infinitesimal
quantity and p(t) and p'(t) denote the transition probabilities of transition t in the
original and compacted sequences, respectively. Here we use a slightly different
objective function. Formally, an input sequence S= (si, s2, ..., sZ, sj, ...s") is a
sequence of binary n-vectors. A transition t = (si, s) is an ordered pair of distinct
n-vectors. We will use S(t) to denote the number of transitions t, and T(S) to
denote the set of transitions in sequence S. Based on these definitions, we define
the sequence compaction problem as follows.
Given a compaction factor c, and an input sequence S= (s, s2, ..., Sm); construct
a new sequence S' to minimize cost C(S, S', c), where
C(S S C) _ S(t ) - c * S' (t) I2
t ET (S) St
This formula aims at preserving frequencies of all transitions individually, as advised
in Eq. 1, and gives a more tractable function for a combinatorial problem. Ideally,
the cost of the compacted sequence will be zero (i.e., if a transition t appears S(t)
times in the original sequence it will appear S'(t)=S(t)/c times in the compacted
sequence), however this is not always possible, and the cost function punishes any
deviation in preserving the frequency of a transition. We normalize the difference in
estimation to preserve frequency of each transition, since the power dissipation for
transitions can be quite diverse. It is worth noting that techniques to be described
can be used with alternative cost functions, as discussed in @ 3.3.
Accuracy A(S, S', c) of a solution S' can be defined as A(S, S', c) = IT(S)I -
C(S, S', c), where IT(S)I denotes the cardinality of set T(S). We will use the cost
metric for most of our discussions, and refer to accuracy occasionally for simplicity
of presentation. Notice that minimizing cost is equivalent to maximizing accuracy,
since IT(S) is a constant.
Our formulation does not involve an explicit constraint on the length of the
compacted sequence. Compaction factor provides an inherent constraint on length,
and we would expect the compacted sequence to be c times shorter than the original.
This formulation gives flexibility on the length of the compacted sequence for more
Example 1: Let S = (ABCABCABCABC) and c=4. Here, A, B and C rep-
resent binary primary input vectors of the circuit. (A, B), (B, C) and (C, A) are
transitions in this sequence. S((A, B)) = 4, because there are four (A, B) transi-
tions in S. Similarly, S((B, C)) = 4, and S((C, A)) = 3. Let S' = (ABCA) be a
compacted sequence. The cost C(S, S', c) of this sequence is: IS((A,B))-c*S'((A,B))I+
IS((B,C))-c*S'((B,C))I +S((C,A))-c*S'((C,A))I _ 14-4*11 +4-4*11 +3-4*1I - 1
S((B,C)) S((C,A)) 4 4 3 - '
One way to estimate power for a sequence is to measure the power dissipation
for each distinct transition, which is impractical due to the enormous number of
measurements. If the simulator reports cycle-by-cycle power dissipation however, all
Here’s what’s next.
This report can be searched. Note: Results may vary based on the legibility of text within the document.
Tools / Downloads
Get a copy of this page or view the extracted text.
Citing and Sharing
Basic information for referencing this web page. We also provide extended guidance on usage rights, references, copying or embedding.
Reference the current page of this Report.
Pinar, Ali & Liu, C.L. Sequence Compaction to Preserve Transition Frequencies, report, December 12, 2002; Berkeley, California. (digital.library.unt.edu/ark:/67531/metadc740885/m1/4/: accessed November 18, 2018), University of North Texas Libraries, Digital Library, digital.library.unt.edu; crediting UNT Libraries Government Documents Department.