Intended UDP behavior not clear to me.

[Chris F Clark]

I'm trying to understand how don't care works in edge-sensitive
sequential UDPs. My naive impression is that a ? does not map to a
transition (i.e. it only applies to steady-state signals and not ones
in transition). However, I'm trying to find some text in the spec
that supports that interpretation.

I'm reading a draft copy of the Verilog Spec and looking at the UDP
semantics. I find the following statements and examples:

8.1.4 UDP State table

It is is illegal to have the same combination of
inputs, including edges, specified for different outputs.

8.1.6 summary of symbols
? Iteration of 0, 1, x
- No change
(vw) Value change from v to w

8.4 Edge-sensitive sequential UDPs

Teh following describes a rising edge D flip-flop:

// clock data q q+
// obtain output on rising edge of clock
(01) 0 : ? : 0 ;
(01) 1 : ? : 1 ;
(0?) 1 : 1 : 1 ;
(0?) 0 : 0 : 0 ;
// ignore negative edge of clock
(?0) ? : ? : - ;
// ignore data changes on steady clock
? (??) : ? : - ;

My interpretation of the last line is that it does not apply to any
edges of the clock (only when the clock is "steady" at 0, 1, or x).
If the ? applied to transitions, then this line would apply to
transitions and in some cases violate the rule quoted from 8.1.4 about
two lines woith different outputs applying to the same combination of
inputs.

Along the same line, would the table have the same meaning if the last
line was written as below?

// ignore data changes on steady clock
? ? : ? : - ;

Thank you,
-Chris Clark

 

[Paul Johnson]

On 30 Jan 2006 17:57:43 -0500, Chris F Clark
<cfc@shell01.TheWorld.com> wrote:

I'm trying to understand how don't care works in edge-sensitive
sequential UDPs. My naive impression is that a ? does not map to a
transition (i.e. it only applies to steady-state signals and not ones
in transition). However, I'm trying to find some text in the spec
that supports that interpretation.

I can't find a definition of 'iteration' but, in this context, it
appears to mean 'one of', or 'iterated over'. In any event, the
sequential UDP sections wouldn't make any sense at all if a '?' could
also cover a transition. I'm afraid that that's as good as it gets in
the LRM. So, you're right.

// ignore data changes on steady clock
? (??) : ? : - ;

My interpretation of the last line is that it does not apply to any
edges of the clock (only when the clock is "steady" at 0, 1, or x).

Yes

Along the same line, would the table have the same meaning if the last
line was written as below?

// ignore data changes on steady clock
? ? : ? : - ;

Logically, yes, but the UDP would be illegal; see 8.4: "if the
behaviour of the UDP is sensitive to the edges of any input, the
desired output state shall be specified for all edges of all inputs".
So, you have to specifiy what happens on edges of 'data', as well as
'clock', hence this line. The comment might be better stated as
'ignore edges on data'.

Paul

 

[Chris F Clark]

Paul responded to my query:

Logically, yes, but the UDP would be illegal; see 8.4: "if the
behaviour of the UDP is sensitive to the edges of any input, the
desired output state shall be specified for all edges of all inputs".
So, you have to specifiy what happens on edges of 'data', as well as
'clock', hence this line. The comment might be better stated as
'ignore edges on data'.

Thanks, Paul.

I had wondered what that statement meant, particularly given the next
(srff) example in the standard, copied below.

// s r q q+
1 0 : ? : 1 ;
f 0 : 1 : - ;
0 r : ? : 0 ;
0 f : 0 : - ;
1 1 : ? : 0 ;

It doesn't cover the rising edge of "s" under any conditions nor any
edges of r when s is 1, etc. Is this table legal? Does it have lots
of bizarre conditions where the output goes to "x" due to nothing
being specified and thus applying the rule from 8.1.4 (e.g. when s = 0
and r = 1).

from the standard:

It is not necessary to explicitly specify every possible input
combination. All combinations of input values that are not explicitly
specified result in a default output state of x.

Hmm, the more I look at this ff, the less sure I am of what it is
intended to do. I remember from my Cadence days, Steve Sharp
explaining that due to the rules, writing UDPs was very hard. And,
I'm not interested in writing UDPs per se, but in getting a correct
implementation so that our simulator doesn't produce wrong results,
i.e. it is consistent with other simulators (within its limits).
I'm not sure what to make the table above do.

If I take the rules of the standard seriously (especially the one you
just highlighted about specifying all edges of all inputs), it seems
like describing an (edge sensitive) srff would have to look like more
this:

Here is one with s priority:
// s r q q+
* 0 : ? : 1 ; // if r is low, edges on s, set q
r 1 : ? : 1 ; // pulling up s, sets q (s has priority)
f 1 : ? : 0 ; // releasing s when r is high, resets q
0 * : ? : 0 ; // if s is low, edges on r, reset q
1 * : ? : 1 ; // if s is high, ignore r edges, q stays set (s has priority)
? ? : ? : - ; // when no edges occur, q keeps the state from the last edge

Here is one with meta-stability represented by an x:
// s r q q+
* 0 : ? : 1 ; // s edge without r high, sets q
r 1 : ? : x ; // s rising with r high, goes metastable
f 1 : ? : 0 ; // s falling with r high, resets q
0 * : ? : 0 ;
1 r : ? : x ;
1 f : ? : 1 ;
? ? : ? : - ;

Anyway, I'm still glad to capture some sense of the intent of the
standard in this area. So, again, thanks, Paul.

-Chris

 

Chris F Clark wrote:

I'm trying to understand how don't care works in edge-sensitive
sequential UDPs. My naive impression is that a ? does not map to a
transition (i.e. it only applies to steady-state signals and not ones
in transition).

If the UDP has transitioned to a state that matches a completely
level-sensitive line in the table, then that line matches. In fact, it
takes precedence over any edge-sensitive line that also matches, as the
LRM says. It doesn't matter that one of the inputs transitioned to get
there; the line matches as long as the input levels match it. Since a
UDP will only evaluate when an input changes, a level-sensitive line
would be useless if it didn't match when one of the inputs had to
transition to reach those levels.

(vw) Value change from v to w

Note the word "change" there. I believe it is important.

// ignore data changes on steady clock
? (??) : ? : - ;

My interpretation of the last line is that it does not apply to any
edges of the clock (only when the clock is "steady" at 0, 1, or x).

It does not apply to any edges of the clock, but that isn't because ?
doesn't match transitions. It is because the line already has a
transition on data (??). Since a UDP evaluates for one input
transition at a time, and that line only matches if there is a
transition on data, then it inherently doesn't match a transition on
clock. Note that clock and data could transition at the same time, but
the UDP will evaluate for one transition and then the other.

Along the same line, would the table have the same meaning if the last
line was written as below?

// ignore data changes on steady clock
? ? : ? : - ;

No, for a couple of reasons. First, it is a level-sensitive entry,
which means that it takes precedence over all edge-sensitive entries.
And since that line matches any input combination, it has just
overridden every other line in your table, and is the only line that
will ever apply. You have a flip-flop that never changes state.

Second, (??) is not the same thing as ?. I think you are assuming that
(??) will match every possible expansion of the ? symbols, including
(00) and (11). But (00) is not a value "change", and this is not a
transition. If you explicitly tried to specify (00) in a UDP table, it
would be an error. So when (??) is expanded, the expansion apparently
only includes legal transitions. The naive expansions into illegal
transitions like (00), (11) and (xx) are apparently discarded. If not
for this, ? would be useless in specifying transitions, since it would
always produce illegal ones.

The intent of the original line is to say that changes on data don't
cause a change on the output. And since it specifies a transition on
data, it does not match when the UDP is evaluated for a change on clock
(because it is not being evaluated for a transition on data, and
therefore does not match the line). With the changed line, it matches
a transition on clock (more properly, it matches the input state after
the transition on clock).

 

Paul Johnson wrote:

Logically, yes, but the UDP would be illegal; see 8.4: "if the
behaviour of the UDP is sensitive to the edges of any input, the
desired output state shall be specified for all edges of all inputs".

Regardless of how it appears, that statement is more a warning to the
user of what they need to do, not a check to be enforced by the tools.
The enforcement by the tools comes in the form of producing unexpected
x outputs, which is why you need to specify the output for all those
edges unless an x output is the desired result.

This is illustrated by the last sentence in 8.4. It describes an input
combination that is not present in the table, but does not say that
this makes the table illegal. Instead, it says that the output will go
to x (which is actually the correct result in this particular case).

So, you have to specifiy what happens on edges of 'data', as well as
'clock', hence this line. The comment might be better stated as
'ignore edges on data'.

Well, the table would be legal, but you do need to specify this if you
want a working model. Otherwise the output will go to x every time the
data input changes, since it doesn't match any line in the table.

And yes, that would be a better comment.

 

[Paul Johnson]

On 1 Feb 2006 19:51:48 -0800, sharp@cadence.com wrote:

Chris F Clark wrote:
I'm trying to understand how don't care works in edge-sensitive
sequential UDPs. My naive impression is that a ? does not map to a
transition (i.e. it only applies to steady-state signals and not ones
in transition).

If the UDP has transitioned to a state that matches a completely
level-sensitive line in the table, then that line matches. In fact, it
takes precedence over any edge-sensitive line that also matches, as the
LRM says. It doesn't matter that one of the inputs transitioned to get
there; the line matches as long as the input levels match it. Since a
UDP will only evaluate when an input changes, a level-sensitive line
would be useless if it didn't match when one of the inputs had to
transition to reach those levels.

I'm not sure that I understand you. Are you saying that '?' does match
transitions? Or that transitions don't matter?

I can't immediately see from the '95 LRM that level-sensitive lines
take precedence over transitions. Is this new, or have I missed it?

<ducks>

There seems to me to be a fundamental problem in UDP definition, at
least in '95. It's summed up in the opening paragraph of 8.4:

"In level-sensitive behavior, the values of the inputs and the current
state are sufficient to determine the output value. Edge-sensitive
behavior differs in that changes in the output are triggered by
specific transitions of the inputs. This makes the state table a
transition table".

Err, no. Very Wrong; this isn't how hardware works. The authors should
perhaps have tried to design a latch or a flip-flop before writing
this. There is nothing fundamental about a 'transition'. Which is, I
think, what you appear to have written in the rest of your post.

</ducks>

 

[Chris F Clark]

Thank you, Steve. I must have missed sections 8.7 and 8.8, duh. I
think I have a better understanding.

One looks at the inputs and current state.

1) If the inputs and state match a level-sensitive entry in the table,
then the output specifications for all the level-sensitive matches
in the table are checked. All the matching entries must specify
the same output value (see below). If they do not, the table is
erroneous (and I presume the simulator can do whatever it feels
like). If they do specify the same output value, then the output
is set to the output specification and this set of inputs have been
processed. This way level-sensitive entries dominate.

2) If the inputs and state do not match a level-sensitive entry, but
do match an edge-sensitive entry, then the output specifications
for all the edge-sensitive matches are checked. Again, all the
matching entries must have the same output value, and we set the
output accordingly.

3) If no level-sensitive or edge-sensitive entries in the table match,
the output is set to x.

below: by matching output value, a - output specification where the
current state is 0 matches an explicit output specification of 0 but
not an explicit output of 1 or x. Similarly, a - with current state 1
matches an explicit 1 and a - with a current state of x matches an
explicit x.

Now, as to that standard itself, if I may, I have a couple of little
quibbles with the wording.

A simulator cannot "process" (unless you mean different semantics than
I think you do) edge-sensitive entries before level-sensitive
ones, because if the edge-sensitive one caused a change of state, the
output would be in a different state at the point of processing the
level-sensitive entry. That is, if O understand correctly and reverse
the output lines in 8.8, the state does not change from 0 to 1 due to
the edge-sensitive entry being processed first, but remains 0 due to
the level-sensitive dominance, since you make the edge-sensitive
changes and then see if any level-sensitive entries apply (to the
changed state).

Well, unless you mean explicitly that you process the edge-sensitive
entries make the changes specified and then process the
level-sensitive entries with the changed state entry (when relevant).
That is a different set of semantics and I would describe that as
edge-sensitive dominance.

Hmm, or perhaps you separate the prev state from the output values, so
you can change the output without having the prev state updated (sort
of like there was an nba without the scheduling implied). Then, you
could change the output value, but since the prev state is still
holding the previous output value, the other entries would continue to
match against it, and you could do the processing in the order stated
and get level sensitive dominance (as long as you didn't update any of
the fan-out until the value was completely determined).

I would also fixup the wording in 8.1.4 to lead readers to the later
section.

It is illegal to have the same combination of inputs, including edges,
specified for different outputs. However, see sections 8.7 and 8.8
for the interaction of level and edge-sensitive inputs that specify
different outputs, where the edge-sensitive entry describes a
transition to a set of inputs and previous state covered by the
level-sensitive entry--this is not an error and the level-sensitive
entry dominates.

-Chris

 

The only way I can make sense of the description is if "process" means
only "check for a match". Then they seem to be suggesting an algorithm
of checking all entries and keeping track of the latest one to match.
At the end, you use that last matching entry. So whichever kind of
entries you check last will win.

This might be based on an actual software algorithm where "process"
means "check for a match and update the state", but where checking
continues, using a copy of the original state so that it is not
affected by the state change partway through the checking. Since the
checking would presumably use some kind of index computed from the
inputs and state, rather than the input and state themselves, it
wouldn't be affected by a change to the state partway through. It
isn't going to recompute the index at that point. This is pretty much
what you describe in your paragraph starting with "Hmm".

Of course, most of us would write the algorithm to stop when it found a
match. In that case, you would want to reverse the order and check the
level-sensitive entries first.

 

Paul Johnson wrote:

I'm not sure that I understand you. Are you saying that '?' does match
transitions? Or that transitions don't matter?

Not either one, precisely.

'?' will match when there has been a transition on that input, but it
is not because of the "match anything" aspect of '?'. A '0' will match
transitions also, as long as the level ended up 0. So '?' doesn't
match transitions any more or less than any other level in the table.
And transitions don't matter when matching against a level specified in
the table. They only matter when matching against a transition
specified in the table. An input can match a line either because the
line specifies the transition that it made, or just the level that it
is currently at (in which case it doesn't matter whether the input made
a transition to get there).

If you have a table line that reads:

? 0 : 0 : 0;

That is equivalent to three table lines that read:

0 0 : 0 : 0;
1 0 : 0 : 0;
x 0 : 0 : 0;

It is just a short-hand. And a table entry that reads

0 0 : 0 : 0;

will be matched after any transition that leads to that state, which
you could list exhaustively:

(10) 0 : 0 : 0;
(x0) 0 : 0 : 0;
0 (10) : 0 : 0;
0 (x0) : 0 : 0;

In fact, making such an expansion of all purely level-sensitive inputs
of the table into every set of single-transitions that could lead to
that set of levels is one possible way of combining level-sensitive and
edge-sensitive table entries into a single kind of evaluation.

But a table entry that reads

0 (10) : 0 : 0;

can never be matched by a transition on the first input. That entry
only matches when there is a transition on the second input, and the
evaluation will never see two simultaneous transitions on inputs,
because it always evaluates for one at a time, even if they change in
the same time slice. This serialization is artificial, but so are
idealized flip-flops with zero setup and hold time.

I can't immediately see from the '95 LRM that level-sensitive lines
take precedence over transitions. Is this new, or have I missed it?

See section 8.8.

ducks

There seems to me to be a fundamental problem in UDP definition, at
least in '95. It's summed up in the opening paragraph of 8.4:

"In level-sensitive behavior, the values of the inputs and the current
state are sufficient to determine the output value. Edge-sensitive
behavior differs in that changes in the output are triggered by
specific transitions of the inputs. This makes the state table a
transition table".

Err, no. Very Wrong; this isn't how hardware works. The authors should
perhaps have tried to design a latch or a flip-flop before writing
this. There is nothing fundamental about a 'transition'. Which is, I
think, what you appear to have written in the rest of your post.

/ducks

I don't understand the issue you are raising, and I have built latches
and flip-flops. If I build a positive edge triggered flip-flop out of
master-slave latches, I get a device whose behavior cannot be described
in terms of just the levels of the inputs. If I tell you the data
input is 0 and the current state is 1 and the clock is 1, and ask you
what the state and output will be moments later, you can't tell me.
You have to know whether the inputs have been stable, or the data input
just transitioned from 1 to 0, or the clock just transitioned from 0 to
1, because only in that last case is the state and output going to
change.

Now you could avoid this by decomposing the flip-flop into individual
transistors and wires, and use the knowledge of the analog state of
those internal nodes, and dispense with these abstract transitions.
But the whole point was to simplify our model of what is happening by
using abstractions. Boolean algebra and truth tables are useful
abstractions. Do you want to give those up because they aren't how
hardware actually works? This extension of truth tables into
transition tables allows us to continue using a simplifying abstraction
on sequential logic.

And in this abstraction, sometimes transitions matter and sometimes
they don't. So the model lets you account for both situations
conveniently.

 

[Chris F Clark]

Not to flog a dead horse, but . . . .

I've been reading the standard on UDP's a bit more and thinking about
the fact that level sensitive entries trump edge sensitive entries.

I've come to the following conclussion, which I can't find anywhere in
the standard, if one has a UDP with edge sensitive entries, then
missing level sensitive entries do not cause the output to go to x.

It's about the only thing that makes sense. Otherwise, you need a
complete set of level sensitive entries to keep the output from going
to x while the conditions (inputs and previous state) stay at that
level and those level sensitive entries trump the edge sensitive
entries, so that the edge sensitive entries have "no effect".

Does that make sense to anyone else?

-Chris

 

Yes. I would only expect the default result of setting the output to x
if no table entry matched. If an edge-sensitive entry matches, but no
level sensitive entry matches, then the edge-sensitive entry would be
used.