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 ?...

Father’s Day! (by alaric)

Yesterday was Father's Day in the United Kingdom.

Now, Jean doesn't know this since she only just approaching ten month's old, but (perhaps due to recovering from illness) she was very affectionate today and always seemed to want me to pick her up and hold her, then was all fun and happy when I did. So I felt very loved 😉

Laryngotracheobronchitis (by alaric)

Poor little Jean! She was well recovered from her past viral infection, but a few days ago she started to drool excessively, went off her food, and became generally unhappy. We thought at first that she was just having more teeth break through her gums, which would have those effects, but she then started coughing, sleeping lots, she'd lost her voice, was hardly drinking any milk or water, and some spots that had begun to appear on her lower lip (where all the drool was running down) turned into nasty big red ones.

So today we phoned NHS Direct, who said that she sounded like she had croup, so we should expose her to steamy atmospheres. They also said they would contact the local out of hours doctor (our local surgery not being open today), who would ring us back soon.

So they rang back, and said they'd like us to bring her down to them to be looked at, if we could; after all, various other things have similar symptoms to croup, that can be a lot worse.

After a short wait, she was seen by a doctor, who summoned a colleague who specialised in children, and they said that it did indeed appear to be croup, but the one thing they couldn't safely check for was Epiglottitis since, if it was that, poking around in her airway to take a look might cause it to spasm, choking her. So they sent us off to the children's unit at a bigger hospital.

After some form-filling with a nurse, having Jean weighed and her vital signs checked, we were seen by a specialist who gave her a thorough examination, and pronounced that she almost certainly just had croup. He then had to go because of a shift changeover, so after a bit more waiting, another specialist came and said that he agreed, and that the nasty spots were probably Herpes. Sarah panicked a bit at this since she'd only heard of herpes as a sexually transmitted disease, and didn't realise it was the common coldsore, but that was soon cleared up!

So after even more waiting, they gave her some steroids to help reduce the swelling in her throat, and packed us off home.

Phew.

The NHS doctors and nurses we spoke to were lovely; noticeably different from the experiences we'd had in London! From the NHS direct phone people to the out of hours doctors at Stroud Hospital (which, alas, is currently fighting potential cutbacks), and the Children's Centre at Gloucester Royal Hospital, even though we did have to wait a long time for the senior doctor to come and see us!

Digital logic simulation (by alaric)

For a while, I've been considering moving into the soft IP market - designing logic circuits that can be used as modular black boxes in designing circuits for use in FPGAs or ASICs.

However, developing such soft IP blocks can be a challenge; they need testing and debugging. You can get an FPGA development board and put your designs into a chip along with test logic to run them through their paces, but it can be hard to inspect the internal signals that way. Or you can simulate them in software.

So, obviously, I'm going down the software route. Thing is, most digital logic design software has you specify the logic in Verilog or VHDL, neither of which I fancy, for many reasons.

So I've taken to writing my own; one where the design is input as a hierarchial netlist, an actual description of how a circuit would be wired rather than an abstract description of its behaviour. It's designed for purely digital logic, and optimised for speed and ease of debugging.

Currently, since I've yet to write an input driver, circuits and test inputs are set up in C++ source code, but before long there'll be a mini language for setting up circuits and test inputs. For debugging, I've defined a logic probe device that can examine a number of named input lines, or a bus; whenever one of the lines changes the change is detailled, and the new state of the entire bus displayed. Next, I'll define a trap capability, where logic probes can be told to suspend simulation in specified circumstances and give a command prompt, from which the states of lines, busses, and devices can be examined, and test signals injected.

The data model of the system is quite simple; a line is connected to any number of device outputs and inputs. Each device output has a state - 1, 0, ? (undefined), or Z (high impedance). The overall state of the line is ? if any output driving it is ?, or there are outputs driving it with 1s while others are driving it with 0s (in this situation it outputs an error message, too, since that condition can damage devices). If all the outputs driving it are Z, then the overall state is also ?; and if the outputs driving it are a mixture of 1s and Zs, or 0s and Zs, then the overall state is 1 or 0, respectively.

Whenever the overall state of a line changes, it notifies all the devices that have inputs connected to the line.

The system is driven by a scheduler. Devices schedule changes to their outputs at specified times in the future. A device cannot just change an output from 0,1,or Z to any other state - when a device asks to chane its output, what actually happens is that at the specified time the output changes to ? then, a little later, it changes to the desired value, modelling transmission line effects in the line. The delay consists of a small basic delay, plus a second delay factor times the number of device inputs driven by that line, to model the capacitance of all those transistors.

When a device's inputs change, it is notified - if lots of inputs change at the same point in time, it is notified just once, for efficiency (think about 64-bit data busses). The device then figures out if any of its outputs need to change, and if so, schedules changes at suitable times in the future, thus allowing for gate delays.

So far I've implemented an AND-gate device, as the quick and simple test, then I went on and implemented a static RAM. This is much more complex, especially when one considers the effect of timing and inputs having undefined states. The RAM device signals an error if the write line goes high while any address or data lines are undefined, so you need to make sure the address and data busses have stabilised before asserting that write, then when you drop the write line, you need to make sure it's had time to become 0 before removing the address and data signals, since when the write input is ? the RAM device considers that it might be writing.

Likewise, when reading, if the read line or address inputs are undefined, the data outputs are, too.

The point of all this is to make the simulator handle the messy details of logic being pushed with high clock rates. If you try and run things too fast, then you get undefined signals appearing in the wrong places because lines haven't had time to settle before they're needed, and you get errors flagged. With it, I'll hopefully be able to do quite accurate timing models of digital logic - a prerequisite for things like asynchronous microprocessors!

And, yes, when I've finished implementing the simulator (with the circuit input file parser, test input signal parser, VCD file output from the logic probes so the results can be viewed in nice graphical signal viewers, the interactive command line, and a wide range of devices - all the usual logic gates, every type of flip-flop, multiplexers, demultiplexers, and logic blocks like ALUs) - I'll make it open source!

Disturbing dream (by alaric)

Last night, I dreampt I was having a heart attack - horrid pains in my left arm, then I was taken to a hospital and wired into monitors and had a drip inserted, again into my left arm - then I woke up to find that I'd fallen asleep with my left arm bent into an uncomfortable position and it was in agony!

It always fascinates me, how the human mind manages to weave external stimuli into our dreams like that. The classic case is when somebody is shouting at you to wake up or an alarm clock goes off, and your brain weaves it into your dream for a few seconds before you come round...