Can a glitch-free mux be designed in an FPGA?

Hi:

The simplest incarnation of a 2-to-1 multiplexer can be described by the
equation:

y = ~s & a | s & b

where 'y' is the output, 's' is the select input, with 'a' and 'b' the
data inputs.

Of course, this multiplexer is broken because a practical implementation
 glitches in a if 'a' and 'b' are true, and the select line toggles.
Such as this example from the book (1):
-----------------------------------------
module mux21g (
    input wire a,
    input wire b,
    input wire s,
    output wire y
);

wire _s;
wire c, d;

assign #10 _s = ~s;
assign #10 c = _s & a;
assign #10 d = s & b;
assign #10 y = c | d;
------------------------------------

The fix for the glitching is of course to implement an extra term
(Verilog not shown, but I think we can all handle it):

y = ~s & a | s & b | a & b


So the big questions are:

1.  What happens (ie., synthesizes) when you implement these equations
in an FPGA?

1a.  What synthesizes if you do:

assign y = ~s & a | s & b; // ???

1b.  What synthesizes if you code the corrected mux equation:

assign y = ~s & a | s & b | a & b; // ???

1c.  Is there any difference in the synthesis if you code it one bitwise
operation at a time, like the module above, vs. all in one equation?

1d. If you "infer" a mux using the code shown in the vendor's device
library, then do you get a good mux, or a glitchy mux?


In the case of a CPLD, I would expect that I could implement the fixed
mux if I selected suitable synthesis properties, such as "mux
extraction" (which I think recognizes my intent to create a mux, perhaps
whether I code it glitch free or not, and implements a correct mux--can
any tool experts clarify?) and/or "wysiwyg" which will probably even
implement the bad mux if I so choose.

But the FPGA with its LUTs is a different ball of wax.

I will be extremely interested to hear what the experts make of these
questions.


I think that it is possible, though I don't yet know how, to see the
"RTL" output by the synth?  Are the answers to my questions to be found
there?

Then there are pre-synthesis and post-synthesis (or is it pre and post
fitting?) simulation models, etc., and whew!  There are quite a few
things I haven't delved into yet.


Have a nice weekend!


(1) "Learning by Example using Verilog ..." Richard Haskell, et.al. pg. 78.


Disclaimer -- none of the above is intended to imply that one should
ever route a clock through logic such as a mux!


-- 
_____________________
Mr.CRC
crobcBOGUS@REMOVETHISsbcglobal.net
SuSE 10.3 Linux 2.6.22.17

Mr.CRC <crobcBOGUS@removethissbcglobal.net> wrote:
 
> The simplest incarnation of a 2-to-1 multiplexer can be 
> described by the equation:
 
> y = ~s & a | s & b
 
> where 'y' is the output, 's' is the select input, with 'a' and 'b' the
> data inputs.
 
> Of course, this multiplexer is broken because a practical implementation
> glitches in a if 'a' and 'b' are true, and the select line toggles.

(snip)
> The fix for the glitching is of course to implement an extra term
> (Verilog not shown, but I think we can all handle it):
 
> y = ~s & a | s & b | a & b

As I understand it, the FPGA LUTs are designed not to glitch
in just this condition.  The exact implementation I don't know,
but they should not glitch in the cases where a combination of
gates that the LUT represents would not glitch.

-- glen

"Mr.CRC" <crobcBOGUS@REMOVETHISsbcglobal.net> wrote in message 
news:ir7ee102lrc@news6.newsguy.com...
> 1a.  What synthesizes if you do:
> assign y = ~s & a | s & b; // ???
> 1b.  What synthesizes if you code the corrected mux equation:
> assign y = ~s & a | s & b | a & b; // ???

They both synthesize to the same thing: a function of 3 inputs, which is 
implemented as a single LUT.

According to Peter Alfke, Xilinx LUTs do not glitch if only a single input 
changes at a time.

> I think that it is possible, though I don't yet know how, to see the
> "RTL" output by the synth?  Are the answers to my questions to be found
> there?

You can view a post-synthesis schematic and you can examine the final output 
using FPGA Editor.

On May 21, 12:18=A0am, "Mr.CRC" <crobcBO...@REMOVETHISsbcglobal.net>
wrote:
>
> The fix for the glitching is of course to implement an extra term
> (Verilog not shown, but I think we can all handle it):
>
> y =3D ~s & a | s & b | a & b
>
> So the big questions are:
>
> 1. =A0What happens (ie., synthesizes) when you implement these equations
> in an FPGA?
>

Redundant logic terms do not get synthesized.  If you add them to the
source, they will get stripped out of the result.

Kevin Jennings

On May 21, 12:18=A0am, "Mr.CRC" <crobcBO...@REMOVETHISsbcglobal.net>
wrote:

> 1c. =A0Is there any difference in the synthesis if you code it one bitwis=
e
> operation at a time, like the module above, vs. all in one equation?
>

No, because logically they are all representing the same thing.  The
Boolean equation for the implementation of 'y' will be the same.  You
can play games with non-portable synthesis directives to attempt to
prevent any optomizations if you'd like...but that requires you to
then manually check each and every build to make sure that it honored
your request.  There will likely be no warning or error produced if
the request gets chucked out.

> 1d. If you "infer" a mux using the code shown in the vendor's device
> library, then do you get a good mux, or a glitchy mux?
>

You're assuming that the vendor's device has some non-glitching 'mux'
primitive...typically they do not.  If it did have a mux primitive
then it would likely be able to pick it out from the source
code...just like it can pick out to use the appropriate hardware
primitives from the source code in the following situations
- multiplication:  y <=3D a * b;
- memory

> In the case of a CPLD, I would expect that I could implement the fixed
> mux if I selected suitable synthesis properties, such as "mux
> extraction" (which I think recognizes my intent to create a mux,

Nope...again it comes down to whether or not there is a 'mux'
primitive in the target device.  CPLDs typically have and/or arrays to
implement logic rather than memory, but that does not imply anything
about what logic gets synthesized which depends on what optomizations
the synthesis tool applies.  Synthesis tools live to create the
smallest, fastest logic that they can.  Implementing redundant logic
has a resource cost that the tools will not pay willingly (i.e.
without special directive otherwise).

>
> But the FPGA with its LUTs is a different ball of wax.
>

Different, but many of the same principles still apply.  CPLD with
their and/or arrays are not immune to what you're seeing with FPGAs.
One problem that I was brought into fix years ago had to do with a
CPLD implementing a transparent latch.  The basic equation for the
latch is identical to the mux, just that in the usage the output of
the mux happens to connect to one of the data inputs.  Implementing a
redundant logic term provides a fix, but again you have to explicitly
disable optomization for that signal...and check with each build that
it gets implemented as you require.

>
> I think that it is possible, though I don't yet know how, to see the
> "RTL" output by the synth? =A0Are the answers to my questions to be found
> there?
>

Viewing the resulting logic is a very good way to see what is going
on.  It is also a good way to see that writing different forms of
source code results in identical logic.

Kevin Jennings

On May 21, 3:52=A0am, glen herrmannsfeldt <g...@ugcs.caltech.edu> wrote:
>
> As I understand it, the FPGA LUTs are designed not to glitch
> in just this condition. =A0The exact implementation I don't know,
> but they should not glitch in the cases where a combination of
> gates that the LUT represents would not glitch.
>

If this were true, then building a transparent latch out of LUTs would
be reliable...but typically it's not.

Kevin Jennings

On May 21, 3:52=A0am, glen herrmannsfeldt <g...@ugcs.caltech.edu> wrote:
> Mr.CRC <crobcBO...@removethissbcglobal.net> wrote:
> > The simplest incarnation of a 2-to-1 multiplexer can be
> > described by the equation:
> > y =3D ~s & a | s & b
> > where 'y' is the output, 's' is the select input, with 'a' and 'b' the
> > data inputs.
> > Of course, this multiplexer is broken because a practical implementatio=
n
> > glitches in a if 'a' and 'b' are true, and the select line toggles.
>
> (snip)
>
> > The fix for the glitching is of course to implement an extra term
> > (Verilog not shown, but I think we can all handle it):
> > y =3D ~s & a | s & b | a & b
>
> As I understand it, the FPGA LUTs are designed not to glitch
> in just this condition. =A0The exact implementation I don't know,
> but they should not glitch in the cases where a combination of
> gates that the LUT represents would not glitch.
>
> -- glen

Actually, there is no reason for a LUT to glitch where logic wouldn't
since they work like logic, a mux in fact.  But a logic glitch depends
on the details of the logic in question.  What the LUTs are designed
to avoid is a glitch in some cases where logic WOULD glitch.  This mux
is such an example.

y =3D ~s & a | s & b

If the inputs a and b are both 1 and s changes, logic has the
potential to glitch since one and gate can turn off before the other
turns on, outputting a 0 momentarily.  One LUT pass transistor will
turn off, but the driven node will not change state until the next
pass transistor turns on to change the stored value.

On May 21, 12:18=A0am, "Mr.CRC" <crobcBO...@REMOVETHISsbcglobal.net>
wrote:
> Hi:
>
> The simplest incarnation of a 2-to-1 multiplexer can be described by the
> equation:
>

> y =3D ~s & a | s & b
>
> where 'y' is the output, 's' is the select input, with 'a' and 'b' the
> data inputs.
>
> Of course, this multiplexer is broken because a practical implementation
> =A0glitches in a if 'a' and 'b' are true, and the select line toggles.

Who says this logic equation glitches in an FPGA, the book cited
below?  I don't think that is correct.  It will definitely glitch if
constructed in discrete gates because of the difference in delays of
the two paths.  But only because an intermediate state is driven to a
value.  In a pass transistor implementation the intermediate state is
undriven and does not change value.


> Such as this example from the book (1):
> -----------------------------------------
> module mux21g (
> =A0 =A0 input wire a,
> =A0 =A0 input wire b,
> =A0 =A0 input wire s,
> =A0 =A0 output wire y
> );
>
> wire _s;
> wire c, d;
>
> assign #10 _s =3D ~s;
> assign #10 c =3D _s & a;
> assign #10 d =3D s & b;
> assign #10 y =3D c | d;
> ------------------------------------

Yes, this will glitch in simulation because of the delay in generating
_s from s.  I'm not as familiar with Verilog, so I'm not sure it will
be apparent.  In VHDL they use delta delays (zero time, but provides
sequencing to intermediate values) which will create an intermediate
value.  It may not be visible on the simulation display, but in
ActiveHDL it will be "touchable" by selecting the signal in the
waveform display and scrolling the cursor from event to event.  It
will stop on what looks like a constant value showing the delta delay
glitch.


> The fix for the glitching is of course to implement an extra term
> (Verilog not shown, but I think we can all handle it):
>
> y =3D ~s & a | s & b | a & b
>
> So the big questions are:
>
> 1. =A0What happens (ie., synthesizes) when you implement these equations
> in an FPGA?

Give some thought to the LUT structure.  For this purpose it is just a
memory.  You have four inputs, sixteen states of those inputs and
sixteen stored bits for the outputs for each input state.  A mux
selects the output based on the input state.  In essence the Karnaugh
map is directly implemented.  It doesn't matter how you write the
equation, you get the same map and the same implementation.


> 1a. =A0What synthesizes if you do:
>
> assign y =3D ~s & a | s & b; // ???
>
> 1b. =A0What synthesizes if you code the corrected mux equation:
>
> assign y =3D ~s & a | s & b | a & b; // ???
>
> 1c. =A0Is there any difference in the synthesis if you code it one bitwis=
e
> operation at a time, like the module above, vs. all in one equation?
>
> 1d. If you "infer" a mux using the code shown in the vendor's device
> library, then do you get a good mux, or a glitchy mux?

What would be a "good mux"?  You mean does it glitch when s changes, I
don't think so.


> In the case of a CPLD, I would expect that I could implement the fixed
> mux if I selected suitable synthesis properties, such as "mux
> extraction" (which I think recognizes my intent to create a mux, perhaps
> whether I code it glitch free or not, and implements a correct mux--can
> any tool experts clarify?) and/or "wysiwyg" which will probably even
> implement the bad mux if I so choose.

Yes, most CPLDs use product terms and fixed or arrays.  So you get a
straight forward sum of products.  I can't say if they glitch or not
without adding the "non-glitch" product term.


> But the FPGA with its LUTs is a different ball of wax.
>
> I will be extremely interested to hear what the experts make of these
> questions.
>
> I think that it is possible, though I don't yet know how, to see the
> "RTL" output by the synth? =A0Are the answers to my questions to be found
> there?

I use Synplify and it has buttons to see either the RTL or the
"technology" which is the inferred LUTs, counters, etc.


> Then there are pre-synthesis and post-synthesis (or is it pre and post
> fitting?) simulation models, etc., and whew! =A0There are quite a few
> things I haven't delved into yet.
>
> Have a nice weekend!

Already did!  I was out kayaking both days.


> (1) "Learning by Example using Verilog ..." Richard Haskell, et.al. pg. 7=
8.
>
> Disclaimer -- none of the above is intended to imply that one should
> ever route a clock through logic such as a mux!

Maybe I missed this thread the other day when I was responding to
other posts.

Rick

> Actually, there is no reason for a LUT to glitch where logic wouldn't

I agree, based on the structure of the N-input LUT (2^N flops feeding N levels of glitchless muxes).  But Xilinx won't admit it.  The official line from Xilinx is that a single input change won't glitch the output (which covers the 2-input mux case in question), but multiple inputs changing might glitch.  After looking into the LUT structure I have concluded that any collection of inputs that cannot change the output cannot glitch the output, but again, Xilinx won't confirm this.

On Saturday, May 21, 2011 at 12:18:07 AM UTC-4, Mr.CRC wrote:
> Hi:
> 
> The simplest incarnation of a 2-to-1 multiplexer can be described by the
> equation:
> 
> y = ~s & a | s & b
> 
> where 'y' is the output, 's' is the select input, with 'a' and 'b' the
> data inputs.
> 
> Of course, this multiplexer is broken because a practical implementation
>  glitches in a if 'a' and 'b' are true, and the select line toggles.
> Such as this example from the book (1):
> -----------------------------------------
> module mux21g (
>     input wire a,
>     input wire b,
>     input wire s,
>     output wire y
> );
> 
> wire _s;
> wire c, d;
> 
> assign #10 _s = ~s;
> assign #10 c = _s & a;
> assign #10 d = s & b;
> assign #10 y = c | d;
> ------------------------------------
> 
> The fix for the glitching is of course to implement an extra term
> (Verilog not shown, but I think we can all handle it):
> 
> y = ~s & a | s & b | a & b
> 
> 
> So the big questions are:
> 
> 1.  What happens (ie., synthesizes) when you implement these equations
> in an FPGA?

I can't say for all FPGA brands, but for Xilinx and most Lattice devices the design of the LUTs use transmission gates with the turn off faster than the turn on time.  There is also a small amount of capacitance on the switching node resulting in the previous value being held until the new value is forced onto the switching node.  In other words, no glitch. 


> 1a.  What synthesizes if you do:
> 
> assign y = ~s & a | s & b; // ???
> 
> 1b.  What synthesizes if you code the corrected mux equation:
> 
> assign y = ~s & a | s & b | a & b; // ???

Both cases result in a LUT being filled in the same way.  There are no gates at this level in most FPGAs, just a table being set to the output values for the various minterms of a set of input signals.  So in both cases it would set the appropriate table values to ones to implement, a & ~b & ~s | a & b & ~s | ~a & b & s | a & b & s.  


> 1c.  Is there any difference in the synthesis if you code it one bitwise
> operation at a time, like the module above, vs. all in one equation?

No. 


> 1d. If you "infer" a mux using the code shown in the vendor's device
> library, then do you get a good mux, or a glitchy mux?

Every vendor I am aware of will give you a "good" mux. 


> In the case of a CPLD, I would expect that I could implement the fixed
> mux if I selected suitable synthesis properties, such as "mux
> extraction" (which I think recognizes my intent to create a mux, perhaps
> whether I code it glitch free or not, and implements a correct mux--can
> any tool experts clarify?) and/or "wysiwyg" which will probably even
> implement the bad mux if I so choose.

Huh?  Tools can only implement what you describe using the HDL logic.  How can they possibly know your "intent"? 


> But the FPGA with its LUTs is a different ball of wax.

Huh? 


> I will be extremely interested to hear what the experts make of these
> questions.

I would too. 


> I think that it is possible, though I don't yet know how, to see the
> "RTL" output by the synth?  Are the answers to my questions to be found
> there?

Most synthesis tools I have used can produce an RTL logic diagram for you to look at.  


> Then there are pre-synthesis and post-synthesis (or is it pre and post
> fitting?) simulation models, etc., and whew!  There are quite a few
> things I haven't delved into yet.

Pre and post synthesis *simulation*.  That is simply the synthesis tool providing delay information for use in simulation or not.  

Rick C.