30 ms·

Cool, thanks javcasas for that intro to Karnaugh maps. I haven't looked at them closely enough to fully understand how they capture "race conditions", but I'll

Cool, thanks javcasas for that intro to Karnaugh maps. I haven't looked at them closely enough to fully understand how they capture "race conditions", but I'll do so on the weekend. I wonder if any specialists in combinatorial design theory have studied these objects. There could be some neat mathematics that has yet to be applied to circuit design!

javcasas 11y ago
The race conditions are not really apparent on Karnaugh maps. They appear once you understand there are no single pair of logic gates in the world that are exactly equal. Every logic gate is slightly slower or faster than the others, even in the same chip. This leads to every level change to be discrete in time, and never exactly aligned with others, which leads to glitches. Silly example: Let's imagine we are implementing the logic operation A OR (NOT A), which should be 1 always. We implement it as an OR gate with two inputs. On the first input we put A through a buffer. On the second input we put A through a NOT gate. Now let's switch A from 0 to 1. One of these two sequences of events will happen: Sequence 1: 0. Nothing has happened yet. The OR gate has 0,1 on its inputs. Output=1. 1. The buffer sets its output to 1. The OR gate has 1,1 on its inputs. Output=1. 2. The NOT gate sets its output to 0. The OR gate has 1,0 on its inputs. Output=1 During all the sequence the output has been 1, so everything is fine. Sequence 2: 0. Nothing has happened yet. The OR gate has 0,1 on its inputs. Output=1. 1. The NOT gate sets its output to 0. The OR gate has 0,0 on its inputs. Output=0 2. The buffer sets its output to 1. The OR gate has 1,0 on its inputs. Output=1. Did you see it? During a split-second the output was 0, even though theoretically it should have been 1 all the time. That's your glitch. If your system is synchronous, it means it has a clock, which means the system ignores everything that happens between clock ticks. If your ticks are sufficiently large (as it should be), the glitches will happen before the next tick. So your system will "stabilize" into the right output before the next tick, and everything is fine. But if your system doesn't use a clock, these glitches will be propagated to other parts, causing trouble all over the place.
- throwaway000002 11y ago
  I understand what you're saying, it's just that in your example (Law of Excluded Middle FTW!) the boolean function is the constant 1 function (on one input). Even I know how to implement that, at least I think so, in a glitch free way. In general though, you're trying to implement some function, and it's not necessarily true that some arbitrary gate setup you make is glitch free, as you have illustrated with the constant 1 function. I assume Karnaugh maps solve this problem, at the cost of perhaps extra gates?
  - rdc12 11y ago
    Karnaugh maps can identify hazards and then also illustrate what the additional logic gates can be inserted to correct the problem. Having a different number of gates on different paths throu a circuit can cause the same problems (say (A & B) | C). This is the easier case to correct.

javcasas 11y ago

The race conditions are not really apparent on Karnaugh maps. They appear once you understand there are no single pair of logic gates in the world that are exactly equal. Every logic gate is slightly slower or faster than the others, even in the same chip. This leads to every level change to be discrete in time, and never exactly aligned with others, which leads to glitches. Silly example: Let's imagine we are implementing the logic operation A OR (NOT A), which should be 1 always. We implement it as an OR gate with two inputs. On the first input we put A through a buffer. On the second input we put A through a NOT gate. Now let's switch A from 0 to 1. One of these two sequences of events will happen: Sequence 1: 0. Nothing has happened yet. The OR gate has 0,1 on its inputs. Output=1. 1. The buffer sets its output to 1. The OR gate has 1,1 on its inputs. Output=1. 2. The NOT gate sets its output to 0. The OR gate has 1,0 on its inputs. Output=1 During all the sequence the output has been 1, so everything is fine. Sequence 2: 0. Nothing has happened yet. The OR gate has 0,1 on its inputs. Output=1. 1. The NOT gate sets its output to 0. The OR gate has 0,0 on its inputs. Output=0 2. The buffer sets its output to 1. The OR gate has 1,0 on its inputs. Output=1. Did you see it? During a split-second the output was 0, even though theoretically it should have been 1 all the time. That's your glitch. If your system is synchronous, it means it has a clock, which means the system ignores everything that happens between clock ticks. If your ticks are sufficiently large (as it should be), the glitches will happen before the next tick. So your system will "stabilize" into the right output before the next tick, and everything is fine. But if your system doesn't use a clock, these glitches will be propagated to other parts, causing trouble all over the place.

throwaway000002 11y ago
I understand what you're saying, it's just that in your example (Law of Excluded Middle FTW!) the boolean function is the constant 1 function (on one input). Even I know how to implement that, at least I think so, in a glitch free way. In general though, you're trying to implement some function, and it's not necessarily true that some arbitrary gate setup you make is glitch free, as you have illustrated with the constant 1 function. I assume Karnaugh maps solve this problem, at the cost of perhaps extra gates?
- rdc12 11y ago
  Karnaugh maps can identify hazards and then also illustrate what the additional logic gates can be inserted to correct the problem. Having a different number of gates on different paths throu a circuit can cause the same problems (say (A & B) | C). This is the easier case to correct.