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.

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,

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.

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. When the new master sees that B is asserted, it
asserts C and releases A. The new master waits until only C is asserted.
Then it asserts A and releases C. The sequence of bus states is
A->AB->ABC->BC->C->AC->A.
A slave will see one of the following subsequences:
A->AB->ABC->BC->C->AC->A.
A->AB->BC->C->AC->A.
A->ABC->BC->C->AC->A.
and it should assert B, C, and A in sequence. This control transfer
can't be done in many ways without risking deadlock. For instance,
a sequence
A->AC->ABC->BC->C->CA->A
could be seen by a slave as
A->AC->BC->...
and could be mistaken for the sequence
A->AC->C->BC->B...
which would cause deadlock.

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:

1) Require that a new master always receives control from an
old master, in a round-robin or similar manner (ie. no arbitration).
2) Allow a non-self-timed procedure for arbitration.

The disadvantage with the first alternative is that the procedure of
transfering control may take some time to find the node that wants to
become master. However, it isn't very easy to come up with a practical
procedure for the second alternative. For instance, the simple
arbitration procedure where each node tries to send a 1 first in John
Payson's 2-wire scheme will deadlock the bus if both nodes contend
simultaneously. Ideas?

Slaves can attract the attention of a master in an idle state A by
pretending to be masters, and letting the master resume control
with the control transfer procedure above.

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

Cheers,

Martin Nilsson
Swedish Institute of Computer Science    E-mail: mn@sics.se
Box 1263, S-164 28 Kista                 Fax: +46-8-751-7230
Sweden                                   Tel: +46-8-752-1574