3.2 Counting Function Points 45
3.2.3 Variables of Condition
Variables of condition are also time-variant, but because they are by defi-
nition persistent, it is useful to consider the valid tuples of values of condi-
tion to get a grasp on the multiplicity of function points corresponding to
the many ways in which the system can be made to operate.
Variables of condition are separated into two categories, variables of in-
ternal condition and variables of external condition. Just as with variables
of connectivity, for a given tuple of values of internal condition there may
be many valid tuples of external condition. Determining the number of
combinations of persistent internal and external conditions can be accom-
plished algorithmically using nested for loops, just as is done for determin-
ing the number of valid systems. A complete analysis of the conditional
subspace includes not only direct conditions established during initializa-
tion, but must also include indirect conditions that arise during the applica-
tion of stimuli.
3.2.4 Variables of Stimulus
Continuing to variables of stimulus we recognize that they can also be
separated into two categories, variables of composition and variables of
time. Values of these variables are quintessentially time-variant, and
counting the function points corresponding to variables of stimulus is ex-
tremely challenging, but not impossible. This procedure will be highly de-
pendent on the design being verified, but is generally a “two-dimensional”
problem along the axes of composition and time.
3.2.5 Variables of Response
3.2.6 Variables of Error
Variables of error are also separated into two categories, variables of error
in composition of stimulus and variables of error in time of stimulus. In
The analysis of the size of the response subspace is identical to that for
stimulus. Responses are values produced by the target and have values that
vary in their composition as well as in their appearance in time, particu-

larly in concert with values of variables of stimulus. Arriving at an actual
count of the function points in this subspace requires creation of value
transition graphs, just as for stimulus and other time-variant variables.
46 Chapter 3 – Exploring Functional Space
fact, their similarity to variables of stimulus permits us to regard them as
extensions of stimuli, and counting the function points corresponding to
values of these variables proceeds in the same manner as for stimuli.
3.2.7 Special Cases
What about all those special cases? As discussed earlier in the previous
chapter, there are special cases corresponding to scenarios and there are
special cases corresponding to properties. Until we develop a few addi-
tional concepts related to the functional space, we will defer our considera-
tion of this important category. For the purposes of advancing our discus-
sion here, we will simply assume that there are some number of function
points associated with these special cases.
3.2.8 An Approximate U pper Bound
Earlier in this chapter it was stated that it is possible to arrive at an exact
count of the number of function points in the overall functional space of a
design. The discussion of variables of connectivity leaned in the direction
of closed-form algebraic expressions (Eqs. 3.1 and 3.2), but this direction
leads soon enough into a blind alley. Nevertheless, the analyses of each
category of variable do provide an approximation for some upper bound on
the count of function points.
Actual counts of valid tuples of values of variables can be made algo-
rithmically with nested for loops as discussed earlier. Applying this concept
in a very general fashion to each category of variable can yield an approxi-
mate upper bound on the number of function points. The verification of a
design can be modeled along these lines with the following pseudo-code:

for each system { /* an instance in a context */

for each activation { /* and de-activation */
for each condition { /* internal and external */
apply stimuli; /* extended with errors */
observe responses;
}
}
}
A greatly over-simplified computation of the number of function points
yields an upper bound of:
P ≤ P
k
⋅
P
a
⋅
P
c
⋅
P
s
⋅
P
r
+
P
y
,
(3.3)
3.3 Condensation in the Functional Space 47
where


• P
k
= number of systems,
• P
a
= number of activations and de-activations,
• P
c
= number of conditions (internal with external),
• P
s
= number of stimuli (extended with errors),
• P
r
= number of responses, and
• P
y
= number of special cases.
There may be little practical usefulness in performing such a computa-
tion (and it may be utterly impractical to do so), but it does serve to illus-
trate just how large the functional space of a design can be. It is possible to
know the exact count of functional points, however, and we shall see even-
tually how to determine the value of P exactly.
3.3 Condensation in the Functional Space
From the standpoint of functional verification, some values of variables are
just not as equal as others. Values at upper and lower boundaries enter into
logical computations frequently while inter-boundary values usually do
not. If we permit the inter-boundary values to condense into a single
“meta-value”, we discover that the number of function points shrinks

greatly.
The size of the condensed function space comprising only boundary
values and these meta-values will be a rather small fraction of the size of
the entire function space. Focusing on this smaller condensed space is a
highly effective strategy for achieving a low-risk outcome with minimal
time and resources. A simple example illustrates this principle.
Consider the operation of a queue of 1024 entries. The number of func-
tion points corresponding to the number of items present in the queue is
1025 (including the value when the queue is empty). However, the associ-
ated control logic which handles filling and emptying of the queue is de-
termined by whether the queue might be:

• empty
• nearly empty
• nearly full
• full
• every other degree of fullness

48 Chapter 3 – Exploring Functional Space
Having recognized (and applied good judgment) that the first 4 of these 5
values constitute boundaries we can condense the 1025 function points into 4
actual values (0, 1, 1023, and 1024) and one condensed value corresponding
to the range [2 1022]. This results in a range of [0, 1, CONVAL, 1023, 1024].
This is, in fact, quite typical in verification code where weights for se-
lection of a particular value are assigned both to individual values and to
ranges.
1
Additionally, existing testbenches typically contain code for col-
lection of coverage data on ranges of values (as a single condensed value)
as well as on individual values.

That which is traditionally referred to as a corner case is simply the in-
tersection of one or more value boundaries.
2
By adjusting the weights as-
sociated with the values in the ranges of variables to select boundary val-
ues preferentially, corner cases will be generated much more frequently,
and the bugs associated with them will be exposed more readily.
Consider the example of our multi-processor system in Fig. 2.2 that was
analyzed in Table 3.1. The analysis showed that a total of 288 distinct sys-
tems (target in context) could be assembled. However, engineering judg-
ment tells us that condensing the in-between values of this subspace of
connectivity will give us more bang for the verification buck.
With this in mind, the range of values for proc_agents condenses from 8
possible values to the following 3 values: [1, PROC_CONVAL, 8], where
the condensed value PROC_CONVAL will assume an actual value from
the range [2 7] during random value assignment. Similarly, the range of
values for mem_agents condenses to [1, MEM_CONVAL, 4] and the
range of values for io_agents condenses to [1, IO_CONVAL, 16 -
proc_agents - mem_agents]. Table 3.2 shows how many possible systems
can be assembled within the condensed space of connectivity.
There are two things worth noting in Table 3.2. First, we note that the
number of possible contexts has shrunk dramatically from 288 to 27, rec-
ognizing, of course, that we have judged the contexts built with all possi-
ble values for x_CONVAL (where x is PROC or MEM or IO) to be
equivalent from the standpoint of verification. Second, we note that the ac-
tual value assigned for any of the condensed values x_CONVAL is de-
pendent on previously assigned values for other condensed values. Modern
verification languages with their powerful constraint solvers handle this
random value assignment with ease.



1
Commercial CRV tools already make use of this concept. For example, the e
language includes an eventually operator. This effectively represents a
condensation in time.
2
More precisely, it is a function arc in the condensed space as will be seen in the
discussion of value transition graphs later in this chapter.
3.3 Condensation in the Functional Space 49
If this notion of condensation within the functional space seems famil-
iar, that is because the reader has already encountered this concept in Boo-
lean algebra and especially while working with Karnaugh maps.
When the value of a particular Boolean variable is “don’t care”, this is
equivalent to condensing the individual values in the variable’s range (the
binary values 0 and 1) into the single condensed point [0 1]. In other
words, the entire range of this Boolean variable has been condensed into a
single value. For notational convenience we represent the value of this
condensed point as X. We will extend this convenience to our notation for
condensation to represent the value at any condensed function point that
comprises all values within its range.
It is not just the numerically valued variables that can undergo conden-
sation. Many enumerated variables are likewise condensable.
Table 3.2. Number of possible systems in condensed space of external connec-
tivity based on example in Fig. 2.2
proc_agents mem_agents io_agents Possible
systems
1 [1, IO_CONVAL, 14] 3

MEM_CONVAL [1, IO_CONVAL, 15-
mem_agents]

3

1
4 [1, IO_CONVAL, 11] 3

1 [1, IO_CONVAL, 15-
proc_agents]
3

MEM_CONVAL [1, IO_CONVAL, 16-
proc_agents-mem_agents]
3

PROC_CONVAL
4 [1, IO_CONVAL, 12-
proc_agents]
3

1 [1, IO_CONVAL, 7] 3

MEM_CONVAL [1, IO_CONVAL, 8-
mem_agents]
3

8
4 [1, IO_CONVAL, 4] 3

Total: 27
50 Chapter 3 – Exploring Functional Space
Consider variables of composition of stimulus as applied to the instruction

set for a processor. There may be many flavors of branch instructions (un-
conditional branch, conditional branch, branch and save return value some-
where, etc.), but for certain coverage measurements these might all condense
to “branch” only. Similarly, memory access instructions might be condensed
based on width of access (byte, half-word, word, etc.) or addressing mode
(register-based vs. immediate address) and so on. General register files often
have a small number of registers that perform unique functions. For exam-
ple, general register zero could be defined to return a value of 0 for all read
accesses and to discard the value written for all write accesses. A second
register might be designed to receive the return address of a branch instruc-
tion automatically. The remaining registers might then be condensed into a
single value representing truly general general registers.
It is not inconceivable that future verification tools will be able to scan
RTL for boundary values and reflect them back to the verification engineer.
3.4 Connecting the Dots
A moment’s reflection reveals that the functional space is characterized
not only by this large number of function points, but also by directed arcs
interconnecting those whose values can vary with time, in particular the
function points in the subspace of condition and of stimulus and response.
Their values can vary with time, and the value state of the target advances
from one functional point to the next with each successive clock cycle. A
given sequence of arcs can be said to constitute a functional trajectory
through a subspace of variables.
The concept of an arc representing a transition in time from one value to
another is probably already familiar to the reader, because they are very
similar to the arcs in state transition diagrams for state machines.
The values of variables of connectivity typically do not change during
the operation of a target in its context. There are notable exceptions such
as, for example, the attachment or detachment of a USB cable.
Variables of activation do undergo changes in value, but there are typi-

cally relatively few variables with fewer values than those of condition or
of stimulus and response. In fact, CRV is usually focused on driving the
variables of stimulus and, to a lesser extent, of condition from value to
value to value, traversing vast numbers of arcs in its attempts to visit
(cover) as many function points as possible before tape-out.
Clearly, the size of the functional space is more than just the count of
points. It must also account for the many arcs connecting them.
3.4 Connecting the Dots 51
State-of-the-art verification tools are not yet capable of counting these
arcs, so for now we can only say that the actual size S of the functional
space is some function of the number of function points P and the number
of arcs A connecting them. It will be seen shortly how the size of the func-
tional space can be determined precisely.
We can summarize the relations among the many values of variables in
the functional space as follows:

• Instantiation of a target in a context (i.e. a system) chooses a particular
function point in the subspace of connectivity.
• Activation of a system is a particular functional trajectory from inactive
to active through the subspace of activation, arriving at some (usually)
persistent region of the subspace within which all subsequent activity
takes place. Deactivation is a trajectory from active to inactive.
• Initialization of a system is a particular functional trajectory through the
subspace of condition, also arriving at some (usually) persistent region
of the subspace within which all subsequent activity takes place.
• Excitation drives the functional trajectory of the target’s responses.

We also observe that activation and initialization are sometimes interde-
pendent, the dependencies being mediated by one or more variables of re-
sponse. Mediation means that progress of some process, such as initializa-

tion, is suspended somehow pending the value of some variable of
response indicating that the process may be resumed. This process may be
activation or initialization or even excitation.
For example, plugging some device into a USB port may suspend some
activity in the host until the device signals that it is ready for excitation.
Mathematically, these relations can be loosely formalized by recogniz-
ing that any given response is a function of values of all standard variables:

response
=
f
(errors,stimuli,initializatio
n
,activation,syste
m
).
(3.4)

It will be useful in later discussions to refer to the set of responses de-
fined for a target. These responses, as well as each argument to the func-
tion f, are themselves each a function of time as measured in clock cycles
n. These functions are denoted as follows:

• r(n): response
• e(n): error
52 Chapter 3 – Exploring Functional Space
• s(n): stimulus
• c(n): condition
• a(n): activation
• k(n): connectivity (systems of instantiated target and context)


We recognize that k(n) could very well be constant for all n, but hot-
swap peripherals can bring time into the equation now and then. In addi-
tion, the response at clock cycle n+1 might also be dependent on the re-
sponse at the previous clock cycle n. We can now state that

r
(n +1) =
f
(
r
(n),e(n),s(n),c(n),a(n),k(n)),
(3.5)

which is just a restatement of Eq. 3.4 except that it accounts for feed-
back within the target with the argument r(n). Feedback in the target sim-
ply recognizes the fact that the response at cycle n+1 may often depend on
the value of some response variable during cycle n during which the com-
putations for values at cycle n+1 are made.
Eq. 3.5 can be regarded as the transfer function that maps the space of
excitation onto the space of responses, given an instantiation of a system
and its subsequent activation and initialization.

R
=
{
p
|
p
=

f
(
r
(n),e(n),s(n),c(n),a(n),k(n))},
for some n ≥ 0.

(3.6)

We now know the coordinates of every function point in the functional
space of the design. The set F of these function points is given by

F
= {p | p ∈ (
r
(n),e(n),s(n),c(n),a(n),
k
(n))}.
(3.7)

Similarly we can define the set of arcs between members of the set of
function points. An arc is represented as the ordered pair (p(n),p(n+1)).
The response (tuple of values of variables of response) at clock cycle n
We now define the set of responses (where p represents a single point) as
3.5 Analyzing an 8-entry Queue 53
leads to the response at clock cycle n+1. We can now define the set A of
arcs among points in the functional space as

A ={(
p
(n),

p
(n
+
1)) |
p(n) ∈ F,
p(n +1) ∈ F, and
r(n +1) = f (r(n),e(n),s(n),c(n),a(n),k(n))}.

(3.8)

Visualizing this complex space can be accomplished using the value
transition graph (VTG). Points (tuples of values of variables) in the func-
tional space are represented as nodes in the graph, and transitions from one
point to another are represented by directed arcs (arrows).
For each clock domain in each instance in each context there exists a
separate VTG containing all possible functional trajectories of that clock
domain. This important observation will be revisited later in this chapter in
a discussion of mathematical graph theory.
The example in the next section will illustrate the use of value transition
graphs to analyze the functional space. This will give us insights into how
a functional space is structured and how it might be condensed to facilitate
more efficient functional verification.
3.5 Analyzing an 8-entry Queue
Consider a basic FIFO queue of 8 entries. Items can be added to the queue
until it becomes full, and items can be removed from the queue until it be-
comes empty. The queue need not be filled before items are removed and
it need not be empty before items can be added again. The response of this
queue to excitation that adds items or removes items or does neither can be
represented by a variable corresponding to the number of items present in
the queue. Call this variable ITEMS_IN_QUEUE.

The VTG in Fig. 3.1 illustrates the functional space of this queue in
terms of the changes in value of the response variable
ITEMS_IN_QUEUE. The value of this variable is shown within the ovals
representing the function points of this space.
This response variable ITEMS_IN_QUEUE has a range of [0 8]. That
is, it can be empty or contain anywhere between 1 and 8 items. From any
value except 8 an item can be added to the queue. Once the queue has 8
items, nothing more can be added. Likewise, from any value except 0 an
54 Chapter 3 – Exploring Functional Space
item can be removed from the queue. At any point in time (that is to say, at
any clock cycle) an item can be added to the queue (if it is not already
full), removed from the queue (if it is not already empty), or nothing can
happen (nothing is either added or removed).
This queue has 9 function points. It has 8 arcs representing the addition
of an item to the queue, 8 arcs for the removal of an item from the queue,
and 9 hold arcs for when nothing is added or removed. Therefore, this
queue has a total of 25 arcs connecting the 9 function points in its func-
tional space.
Of these 9 function points we can observe that 7 values are condensable
into the condensed function point [1 7], because every adjacent point in
this range has congruent arrival and departure arcs. Fig. 3.2 illustrates the
condensed functional space of this 8-entry queue. It has only 3 function
points and only 7 arcs connecting them. For this particular target, conden-
sation greatly simplifies the functional space.
Now, we can add a mechanism to this queue so that priority is given to
draining the queue (removing items) when the number of items in the
queue reaches some high-water mark. For our example, the high-water
mark is set to the constant value of 6.
An indirect condition is established on the following clock cycle when
the number of the items in the queue reaches the high-water mark. This in-

direct condition persists until the queue has been emptied. Even though the
priority has been given to draining the queue, we still permit items to be
added to the queue. Of course, it could be designed with a much stricter
drain policy that prevents the addition of items to the queue until it has
been emptied. Our example is not so strict, so even though priority has
shifted to draining the queue, items can still be added (until it becomes
full, of course).
Fig. 3.3 illustrates the uncondensed functional space of such a queue.
The pair of values in each oval represents the value of the response vari-
able ITEMS_IN_QUEUE and the indirect condition variable we shall call
DRAIN_PRIORITY.
Items can be added to the queue (and removed) in normal operation up
until the number of items reaches 6. Then the indirect condition is estab-
lished (DRAIN_PRIORITY == 1) on the next clock cycle, whether an
item is added during that same clock cycle or removed or neither added
nor removed. This shifted operation appears on the right-hand side of the
figure in which the pair of values shows that drain priority has been estab-
lished. Items can be removed (preferably) or added to the queue, but when
it eventually becomes empty the indirect condition reverts back to normal
on the next clock cycle.