Jean on #NetBSD (by alaric)

 "This is how it looks if you port NetBSD to a cute baby and make a screenshot:"...

#NetBSD Community Blog

CMOS transmission gates (by alaric)

As I mentioned before, I plan to implement CMOS transmission gates in my digital logic simulator.

However, while driving back from dropping Jean off at the nursery this morning, it struck me that they wouldn't be as trivial as I'd naively thought, for an obvious reason; if a change occurs on one data line, then the gate will cause a corresponding change to its driver on the other data line, after a small gate delay. However, the gate will also be bound as an output on that line, meaning that it will then be told of its own change when the scheduler performs it, so it'll end up making the same change on the output driver of the original input line, meaning it locks the line in that state; when any other drivers try to assert another logical state, there'll be a driver conflict.

Duh.

I see four possible solutions.

A third type of device < -> line connection

Right now, devices have a number of input pins and a number of output pins, each of which can be individually bound to a single line. Anything bidirectional has to be handled as a pair of pins, one input and one output, connected to the same line. For example, my SRAM device has data inputs and separate data outputs; and they can be joined to the same bus for a bidirectional interface, or wired independently. But perhaps I could introduce a third class of pin, bidirectional pins, which are handled specially; bidirectional pins would not be notified of changes to the line they cause. That way, a transmission gate could have two bidirectional pins, and whenever it receives a change on one, it copies the change to the other bidirectional pin. It'd keep track of which side was being driven and make sure the driver on that side was in the HI-Z state so as not to cause a collision.

Line bridging support

Perhaps I should make it possible to 'bridge' two lines. Pick one arbitrarily as the master, and the other as the slave, and inform them both of this fact. Then when the simulation loop has applied changes to one or more drivers of either line, the master is told to compute the line's new state; it asks the slave to compute the state of its drivers, then merges this with the state of its own drivers to deduce a shared state, which it then tells the slave to inform its connected devices of, before informing its own. The transmission gate would then work by, when the control input was asserted, bridging its two lines together, and unbridging them when the control input drops.

Not bothering

Perhaps I can get by without transmission gates. They're quite low level things, mainly useful in designing flip-flops and multiplexers, so I can probably just define higher-level devices that use them and be done with it. However, I did see high-level use for them in routing signals on bidirectional busses, which would otherwise have to be done with pairs of tristate buffers that listen to the read/write control signals on the bus and configure themselves appropriately, requiring extra logic, and being slower when implemented in silicon.

Using weak logic

As I sit writing this, I realise there's probably a simpler solution; I'll need to think longer to see if there are any showstopping gotchas. That's to use my weak logic system I designed, avoiding the need for any infrastructure changes at all. Under this system, the transmission gate would have (apart from the control input) two input pins and two output pins, designed such that each bidirectional interface is made by joining an input pin and an output pin to the same line. Any line state change notification from either input pin would be ignored if it matched the last state notified, to prevent changes bouncing back and forth between the two lines, but if not then the input line state would be weakly driven onto the opposite output pin. That way, if side A was in the 1 state, the transmission gate would output a weak 1 to side B; and if nothing else was driving side B (as should be the case in a bus), B would then end up in state 1. When the notification of B's resulting state change came back to the B input, it would be seen to be the same as the last state change sent through the gate, and ignored.

Likewise with state 0, and likewise if the sides are reversed.

It gets interesting if something on A drives a 1 and something on B drives a 0 (or vice versa), in which case, the transmission gate will be weakly driving a 1 onto B and a 0 onto A, which will have no effect and not raise an error, even though in a real circuit this would be shorting Vdd and Vss. So the transmission gate itself will need to notice that state and make an error message, I think.

Hmmm, that may be the correct solution... The only downside is that one cannot use weak logic for anything else on those lines, but I suspect one shouldn't be using weak logic around transmission gates anyway, due to the extra line resistance they cause.

Although I still think I'll introduce a weak notion of a bidirectional pin, even if just for neatness; as syntactic sugar, binding a bidirectional pin number N to a line will just bind input pin N and output pin N to the same line (input and output pins have separate numbering schemes).

Blog Sections (by alaric)

For those of you who read this blog to see how the family's doing, my computing / electronics posts are probably a bit irrelevant. And for tecchies, all the personal family stuff probably gets in the way of the bits you find interesting.

So I just thought I'd make sure everybody realised that the 'Categories' section on the right has links to separate sections of the site for Alaric (and my subtopics), Jean, Sarah, and The Family (which is about things that affect us as a whole, such as our domestic arrangements). Clicking on a section link takes you to what's basically a sub-blog only showing things in that section, with its own RSS feed and everything.

Enjoy!

Digital logic progress (by alaric)

Yay! The core of the logic simulator is getting pretty near completion now. I've been working on a project that involves glacial compilation times, which give me 5-10 minute blocks every 30 minutes or so, so I've been typing in the list of logic simulator changes I had written in my notepad. Read more »

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:

1. 0ns: A becomes ?, X becomes ?
2. 0.01ns: A becomes 1, and X is scheduled to become 1 at time 1.01ns
3. 0.1ns: B becomes ?, and X becomes ?
4. 0.11ns: B becomes 1, and X is scheduled to become 0 at time 1.11ns
5. 1.01ns: X becomes 1
6. 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 ?...