# 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.

#### Extracted Text

The following text was automatically extracted from the image on this page using optical character recognition software:

- 4

Accuracy of compaction requires preserving the transition probabilities of all

transitions. In [13], 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

accurate solutions.

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+

S((A,B)) +

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

## Upcoming Pages

Here’s what’s next.

## Search Inside

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.