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

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!

VoIP (by alaric)

Well, while I still don't know where my CD-ROM drive is, at least I now have Asterisk working.

Since I work from home, we have two phone lines, work and home. What I hope to set up is to have the phone lines from BT terminate in "FXO ports" on a little box, which then has an Ethernet interface it uses to connect to my Asterisk server with SIP. The Asterisk server will then answer incoming calls, as well as being able to route outgoing calls to BT.

Also, the Asterisk server will be connected to from SIP and IAX telephones on my LAN, and software telephones on our desktop and laptop machines - even when the laptops AREN'T on the LAN, but out on the Internet.

Given this, Asterisk can then function as a PBX. It'll be possible to call extensions from each other by dialling the extension number, or to dial out via the work or home line by prefixing the number with a 9 or an 8. Also, when I dial friends of mine with known VoIP addresses, the system will notice that their number is listed in a local database or any of a number of global ENUM databases, and route the call over VoIP for free.

When people dial in on the home line, all the connected extensions will ring, and the first to answer gets the call. The same will happen for work calls, except that I'll send a different caller ID string so the phones will show what line the call is from, and if I don't answer in four rings it'll go to voicemail. Similarly with incoming VoIP calls.

The voicemail won't be one of those horrible systems where I have to ring in to get my voicemail, either.The server will record the message to the file, and email it to me.

Since I hate my mobile phone's voicemail system, I'll reconfigure it to route calls to my work number when I don't answer, so all my voicemails will end up in one place.

NetBSD upgrade (by alaric)

Bah!

I've upgraded my main home server from NetBSD 1.6.1 (ancient) to 3.0 (current), for two reasons.

1. There was a bug in the VIA Rhine network driver, causing it to drop packets and/or stop working (drop ALL packets until brought down and back up again) under load
2. I need to install Asterisk, and 1.6.1 wasn't up to it - Asterisk requires a native pthreads implementation.

So I bravely reinstalled. NetBSD's upgrade process is a bit ropey, so I had to hack around a bit to get it all up and running.

But now I've lost my CD-ROM drive!

Read more »