> John Payson wrote in an earlier message to the Piclist that he has a > 3-wire communication protocol for connecting an arbitrary number of > devices that may be arbitrarily busy. However, to the best of my > knowledge, he has not given any further details of his protocol. Sorry 'bout that. :-) > I think this idea is very interesting. Among the potential advantages > of such a protocol is that it wouldn't require guaranteed response > times from the bus nodes. It would run faster with faster technology, > without a redefinition of the protocol. No problems with skew. Less > problems with noise, cable capacitance, etc. I think most of you who > have experienced interfacing an I2C device to a PC have felt the need > for something like this, Well, there are skew and such requirements to be dealt with if cable lengths are significant, but in most cases uniformity of signal arrival should not be a problem; the biggest limitation on speed will likely come from the CPU speeds since the protocol is intended for non-hardware-assisted applications. > Here is my version of the bit layer for such a self-timed serial bus > protocol (S2P?). I don't think it can be done in too many ways, and > several of you have probably come to the same conclusions. I'm > interested in your opinions and solutions. > > The bus uses three wires A, B, and C, conceptually pulled-up > open-collector connected like I2C. (It could be an optical bus or > a combinatorial circuit, of course.) An idle state is when exactly > one of the bus lines is asserted, A, B, or C. > > Suppose the current idle bus state is A. A bus master sends a one by > asserting B and releasing A. When the slaves see the transition A->AB > they also assert B and release A. The slaves play "follow the leader." > When A goes high, the master knows that everybody has received the > bit, and the bus is in the new idle state B. If the master had wanted > to send a zero, it asserts C and causes a bus transition sequence > A->AC->C. So far, everything is rather simple. Only two transitions is > necessary for sending one bit. The bandwidth is 1/3 bits/wire/time > unit, where a time unit is four times the propagation delay of the bus. Nice scheme. Unfortunately, I think it breaks if master sends a 1 followed by a 0. Specifically: XYZ are the devices [X master]; for each state the devices following the name in uppercase are those that are asserting the line, those in lowercase are those that have last sampled the line as asserted, and those in lowercase preceded by "!" are those that have last sampled the line unasserted: A=xYZ B=X A=xyZ B=XY A=y B=XYZ ; Z has released A; X and Z have polled it and seen it high; Y hasn't polled it yet. A=XZ B=Y ; B is still waiting for A to be de-asserted. It looks like you account for this in your change-of-master handling (which you IMHO overcomplicate) but you don't account for it in the bit-sending protocol. My protocol for three wires or four-wires low-overhead is as follows: [wire names: "0", "1", "K", and "A" for zero, one, acK, and Attention; the Attention wire is optional] [in four-wire state description "-" means wire asserted by nobody; "M" means asserted by master only; "S" by slave only; "X" by "everyone"; "*" by master and [maybe] slaves] Idle State: 01KA = --XX Send Zero : 01KA = M-SX X--X S-MX --XX Send One : 01KA = -MSX -X-X -SMX --XX Clobber : 01KA = M-SX XmSM SX-M -X-X -SMX --XX [see below] Signal Attention: 01KA = ***S MMX- --SM ---X If a device is trying to send a "0" when clobber state occurs [either XXXX or XX-X], it should forfeit to the device sending the "1". Similarly, a "0" should not be registered by a receiver until the "--XX" state has been reached. If a device doesn't think it will need any communication for a while, [and other devices know this] it may go into hybernation [all lines floating except "A", which is asserted] unless/until it sees all lines are asserted. In this case, it should assert K and float A. If A rises before "0" or "1" does, the device should assume an attention sequence and start watching for possibly useful data. If "0" or "1" rises, the device should float "K", assert "A", and go back to sleep. > Suppose again that the current idle state is A. In order to transfer > control to a new master, the old master asserts B, releases A, and > converts to a slave. With a protocol like the above, there is no such complex requirement for a master/slave handoff. Since everyone [including the old and new master] explicitly acknowleges everything they see, no one except the master needs to know who's master. > The really tricky thing is arbitration in a multi-master system. This > is impossible in a pure self-timed system, so there are two > possibilities: Why is arbitration impossible in a self-timed system if devices have unique addresses? > [Nerd warning] A five-wire protocol can be constructed in the same way > as the three-wire scheme. Then we get 2/5 = 0.4 bits/wire/time unit. It can > be further generalized to n wires, of which k are asserted in an idle > state. I spent saturday night proving that the maximum bandwidth/wire > 2 > is log Phi bits/wire/time unit = 0.694, where Phi is the golden ratio = > 1.618... . I hadn't expected this ratio to go over 0.5, but one can get > arbitrarily close to it for large n (it is a tight bound). > Some interesting pairs (n, bits) are > (3, 1), (5, 2), (7, 3), (9, 4), (15, 8), (62, 40). > For 3 < bits < 39, 2*n = 3*(bits+2). In practice, it is rather complicated > to decode the signals for large n, so a more practical way would be to use > the five-wire scheme replicated. This would produce (10, 4) and (20, 8) > solutions which are not all that bad. Well, I think for a 10/4 solution an easier approach is to have two control wires and eight data wires. In the idle state, the wires are X- lastbyte To send two bytes of data, the transitions should be SM -byte 1- -X -byte 1- MS -byte 2- X- -byte 2- Not as mathematically elegant as an arithmetic code, but easier I suspect. BTW, does your formula consider deadlock avoidance as a requirement?