More digital logic simulation (by alaric)
Playing around with my digital logic simulator, I've found a few cases it doesn't handle well... but, luckily, I've found easy fixes for them 🙂
The first was that if a change to the inputs of a gate occurred that needn't change the output (eg, the inputs of an AND gate changing from 10 to 00), then the change would cause the gate to compute a new value (the same as the previous value) and schedule that the output should change to this value after one gate delay.
However, the code that schedules an output change handles gate delay by scheduling a change of the output driver to an indeterminate state a very small time in the future, then a change to the final value after the specified gate delay. This means that changing the inputs of an AND gate from 00 to 01 cause the output to be indeterminate for one gate delay, which is wrong.
The obvious solution is to make the gate smarter. Make it figure out if the input change it's being notified of will actually affect the output, by tracking the states of inputs or outputs, and forbid it from scheduling a change to a new state unless it really is a new state. However, this adds complexity to the gates, and I wanted to add a lot of devices to the system beyond simple gates without needing to give them all their own change-elimination logic.
So I wanted something built into the simulation core. And, luckily, a simple answer presented itself.
Now, as I mentioned before, a line has three states: 0, 1, and floating. But since many device outputs ('drivers') may be connected to the same line, a driver may actually be in one of four states: 0, 1, floating (?), or high impedance (Z). The latter state means the driver isn't driving, and so has no effect on the line, either way.
I'd since added support for "weak logic"; if two drivers on the same line are driving 0 and 1, then the system signals an error, since that situation would cause damage in a real circuit. However, weak drivers, as the name suggests, exert a "weak" pull on the line. If no drivers on the line are exerting 0 or 1, but one or more drivers exert a weak 1 (which I assigned the symbol '+'), then the resulting line state is 1. However, if another dirver exerts 0 or 1 then that is the resulting line state, with no error due to the conflicting weak 1. If there are weak 1s and weak 0s both being driver, then unless a strong 1 or 0 overrides it, the resulting line state is still ?. I assigned the weak 1 and weak 0 states the symbols '+' and '-' respectively.
In order to remove the problem of a temporarily floating line when the inputs of a gate change in ways that wouldn't change the output, I altered the code that scheduled a transition. Rather than going to the ? state for the gate delay then going to the output state, I made it instead schedule the driver to go into a 'rising' or 'falling' state if the final state was to be a 1 or a 0, respectively. To cover the weak logic, I also defined 'weakly rising' and 'weakly falling' states for when the output is shifting towards a weak 1 or 0. I gave the rising and falling states the symbols '>' and '< ', and the weak versions '}' and '{'.
Now, when the scheduler actually makes the change to the driver into a rising or falling state, I made it check the previous state of the driver. If the driver was 1 when a rising change occured, then it's just leave the driver in the 1 state; otherwise, it'd put it into the floating state. Likewise, if the driver was 0 when it was scheduled to start falling, it'd just stay at 0, otherwise it'd go float. That way, changes from 1 to 1, from 0 to 0, and from + (weak 1) to + and - (weak 0) to - don't cause any actual change in the driver's state, and thus have no effect on the driven line.
But as my free time ran out, I was still faced with another problem; imagine an XOR gate with two inputs, A and B, and an output, X. Imagine the XOR gate has a gate delay of one nanosecond. Now, imagine A and B are both 0; therefore, X is 0. Also, imagine that the lines feeding A and B have a transition time of 0.01 nanoseconds.
Now, if A starts to change to 1, this will appear as A entering the ? state, then 0.01 nanoseconds later, becoming 1. This will cause X to become ?, then 1.01 ns later, becoming 1 too, after the transition time of A plus the gate delay.
But if A changes, then B changes 0.1 nanoseconds later, we have an interesting situation. The timetable looks like this:
- 0ns: A becomes ?, X becomes ?
- 0.01ns: A becomes 1, and X is scheduled to become 1 at time 1.01ns
- 0.1ns: B becomes ?, and X becomes ?
- 0.11ns: B becomes 1, and X is scheduled to become 0 at time 1.11ns
- 1.01ns: X becomes 1
- 1.11ns: X becomes 0
This is clearly wrong. For a start, we have an instant transition from 1 to 0 on X at 1.11ns, which is physically impossible. What SHOULD happen is that X should remain in the ? state until 1.11ns, then become 0, never actually settling on a stable 1 output.
Anyway, I ran out of time while thinking about that and had to return to work, but while thinking about it today it's occurred to me that the solution for the past problem can be adapted to solve this one, too. As it stands, my solution to the past problem was to make the code that actually applies a scheduled change to the state of a driver handle requests to change to the < , >, {, or } states - which represent the 'rising' or 'falling' before settling at a final logic level - by checking to see if the driver is already in the 'target' state and, if so, leaving it be, otherwise going to the ? state.
I realised that I could fix this second problem by making this code actually set the state of the driver to < , >, {, or } rather than ?, and have the code that checks the states of all the drivers on a line to compute the final line state treat them all as ?. However, when the scheduler requests that a driver's state change to a final logic level, the code should at that point check the existing state of the line is indeed the appropriate rising/falling state. If it is, then no other state changes are overlapping with this one, so the change can go ahead. If not - for example, if the driver's output is rising, when the scheduler tells the driver to enter the 0 state - then we know that transitions have overlapped, and to ignore the change to 0.
Now all I need is some more free time to implement this...
But it's interesting just how complex a good simulator of digital logic can be. There's now eleven states a driver can be in! The original 0, 1, or ?, then the high-impedance state Z, then the weak versions -.+. ~, then the rising/falling states < , >, {, and } - all just to generate the three possible resulting states of the line once all the drivers have been taken into account, 0, 1, or ?...
Electronics | alaric | 
Tue 27th Jun 2006 9:24 pm
Subscribe