1. Field of the Invention
The invention relates to methods and apparatus for the transfer of binary data among digital devices. More particularly, the invention relates to self-timed data communications systems and methods.
2. State of the Art
Known communications bus techniques are all based on a clock pulse data scheme. These techniques may provide clock and data signals on separate lines or provide a data signal which is encoded with clock information. Alternatively, data may be transmitted asynchronously with a clock signal being generated locally by the receiver. All techniques, however, require that the receiver view data at a specific instant in time, i.e. at the clock edge.
Many microprocessors are provided with integral (dedicated) serial data ports. However, in many applications, additional serial ports are required. The additional ports can be effected through additional external circuitry or the logic of the port can be implemented in the processor using software and any free I/O pin(s) of the processor. While the reading of serial data at specific instances is not a significant problem for dedicated devices, it poses difficult problems for software implementation in the logic of a microprocessor.
Virtually all microprocessors are required to service a number of independent tasks in an apparently concurrent manner. This is sometimes referred to as multi-tasking or multi-threading. In reality, a microprocessor can only operate on one task at a time and multi-tasking is accomplished by programming the microprocessor to switch between or among different tasks very rapidly so that there is an appearance of concurrent task processing. The switching among different tasks is most often in response to external events (e.g. the press of a key on a keyboard) which are random in nature. Therefore, it is problematic to program the microprocessor so that it is always available at the instance of a clock transition to read serially transmitted data. This problem is usually solved in one of two ways: through the use of polling, or through the use of interrupts.
In polling, the microprocessor repeatedly reads an I/O pin through which the clock signal is received to determine if it has changed state. Since the data must be read at an exact instance of clock signal transition, the microprocessor must poll the I/O pin at a rate which is significantly faster than the frequency of the clock signal. If the microprocessor misses a clock transition data will be lost. Serial communications clock signals are typically in the tens or hundreds of kilohertz. Therefore, the microprocessor must devote a significant number of its cycles to the task of polling the clock signal.
The use of interrupts is similar to polling but utilizes additional hardware (e.g. a separate interrupt pin, internal timers, etc.) in order to enable more efficient software. While the use of interrupts relieves the processor of some of the time wasted during polling, it still interferes with the fundamental operation of the processor, and considerable time must be spent by programmers ensuring that the scheduling of interrupts does not cause other parts of the software to malfunction. As the rate of serial data transfer increases, the challenge in scheduling interrupts becomes progressively more difficult.
Therefore, while soft implementation of a serial port in a microprocessor is known and is widely used, the hard timing of serial data communications complicates the design of system software and places unwanted constraints on the processor.
Parent application Ser. No. 08/545,881 discloses a self-timed point-to-point serial data link and a self-timed multi-user serial data bus. The point-to-point link allows two processors to communicate via one, two, or three lines in which data and timing information are transmitted simultaneously. In the two line embodiment, the link has four possible states: 11, 10, 00, and 01. The idle state of the bus is 11 which is shown at t0 in FIG. 1. When a first processor transmits a binary ZERO at t1, the first processor pulls the ZERO line low and the state of the bus is changed to 10. Sensing the change in the bus state the second processor acknowledges by pulling the ONE line low at t2. The state of the bus is thus changed to 00. Sensing the change in the bus indicating acknowledgement by the second processor, the first processor releases the ZERO line at t3 which changes the state of the bus to 01. Upon sensing the change in the bus, the second processor ceases acknowledgement at t4, releases the ONE line, and returns the bust the state 11. The transmission of a binary ONE follows a similar procedure, but the states of the bus cycle in the opposite direction, i.e. from 11 to 01 to 00 to 10 and back to 11. As shown in FIG. 1, one of the processors transmits a binary ONE at t5 and the other processor acknowledges by asserting the ZERO line at t6. The transmitting processor ceases transmitting at t7 and the acknowledging processor ceases acknowledgment at t8.
The multi-user bus described in the parent application allows an unlimited number of processors to communicate via three lines coupled to any three I/O pins of each processor. Since the multi-user bus uses three lines, the bus has eight possible states. FIG. 2 is timing diagram of the multi-user bus and FIG. 3 is a state diagram of the bus. The initial state of the bus is illustrated at time t0 in FIG. 2 where line 0 functions as the ZERO data line (D0), line 1 functions as the ONE data line (D1), and line 2 functions as the acknowledge line (ACK). In this initial state, the data lines D0 and D1 are pulled high (unasserted) and the acknowledge line ACK is pulled low by all the bus users.
The transmission of a Binary ZERO by a bus user is effected by asserting the D0 line and the transmission of a Binary ONE is effected by asserting the D1 line. In the initial state of the bus, therefore, the transmission of a Binary ZERO by a transmitting bus user is effected by asserting line 0 as shown at time t1 in FIG. 2. In response to the transmission of a Binary ZERO, all receiving bus users also assert the D0 line and also release the ACK line. It will be understood, however, that since the ACK line is initially pulled low by all of the bus users, it will not go high until all receiving bus users have released the ACK line. The transmitting bus user releases the ACK line at the start of transmission. When acknowledgement has been noted by all of the bus users, the ACK line goes high as shown at time t2 in FIG. 2. After releasing the ACK line, the function of each of the physical lines line 0, line 1, and line 2 rotates so that the lines which are now high (line 2 and line 3) become the data lines (D0 and D1 respectively) and the line which is now low (line 0) becomes the acknowledgement line (ACK). This state of the bus is shown in FIG. 2 during the time between t2 and t3. A next Binary ZERO transmission, will therefore be effected by asserting line 1, as shown in FIG. 2 at time t3, since line 1 now functions as the D0 line. Acknowledgement by all bus users will result in line 0 going high, as shown in FIG. 2 at time t4, since line 0 now functions as the ACK line. Following the acknowledgement at time t4, the function of each of the physical lines line 0, line 1, and line 2 rotates so that the lines which are now high (line 2 and line 0) become the data lines (D0 and D1 respectively) and the line which is now low (line 1) becomes the acknowledgement line (ACK). This state of the bus is shown in FIG. 2 during the time between t4 and t5. As described thus far, following each Binary ZERO transmission and acknowledgement, the function of each physical line is rotated clockwise or in a positive direction. For example, following the acknowledgment at t2 in FIG. 2, the function D0 is rotated from line 0 to line 1, the function D1 is rotated from line 1 to line 2, etc.
As mentioned above, the transmission of a Binary ONE is effected by asserting the D1 line, which, as described above, may be any of the physical lines depending on the state of the bus. For example, from the bus state shown between times t4 and t5, a Binary ONE is transmitted by asserting physical line 0 (which in this state has the function D1 ) as shown in FIG. 2 at time t5. The transmission of a Binary ONE is followed by each of the receiving bus users asserting the D1 line and releasing the ACK line. When all bus users have released the ACK line, as shown in FIG. 2 at time t6, the function of the physical lines is rotated so that the lines which are now high (line 1 and line 2) become the data lines (D0 and D1 respectively) and the line which is now low (line 0) becomes the acknowledgement line (ACK). It will be appreciated that the rotation of physical line functions following the acknowledgement of a Binary ONE transmission is counterclockwise or negative. For example, in the function rotation following the acknowledgement at t6 in FIG. 2, the function D0 is rotated from line 1 to line 0, the function D1 is rotated from line 2 to line 1, etc.
During the times between data transmission and full acknowledgment, e.g., between times t1 and t2, between times t3 and t4, and between times t5 and t6, the bus may be said to be "meta-stable". Bus users are prevented from transmitting new data during these meta-stable bus states. It will be understood that the meta-stable states are indicated when any two or more lines are low and at least one line is high.
It will be appreciated that each bus user in the multi-user embodiment of the invention must track the state of the bus so that each bus user knows which physical line has which function. Also, it will be appreciated that under some circumstances it will be necessary to reset the bus to its initial state where line 0 is the D0 line, line 1 is the D1 line, and where line 2 is the ACK line. The bus is reset by taking all three lines low as shown at time t7 in FIG. 2. While it is possible that any bus user could be permitted to reset the bus, it is more typical that the decision to reset the bus will be the province of a master bus user. When the bus users sense that all lines have been taken low, the functionality of the physical lines is restored to the initial state as shown at time t8 in FIG. 2.
Turning now to FIG. 3, the initial state of the bus is shown at the oval numbered 3 where the SB0 line has the D0 function, the SB1 line has the D1 function and the SBA line has the ACK function. Upon transmitting a binary ONE, the bus enters a meta-stable state shown at the hexagon numbered 1. Upon acknowledgement of the transmitted ONE by all bus users, the bus enters the stable state shown at the oval numbered 5 wherein the SB0 line has the D1 function, the SB1 line has the ACK function and the SBA line has the D0 function. From the state 5, the transmission of a binary ONE causes the bus to a meta-stable state shown at the hexagon numbered 4. Upon acknowledgement of the transmitted ONE by all bus users, the bus enters the stable state shown at the oval numbered 6 wherein the SB0 line has the ACK function, the SB1 line has the D0 function and the SBA line has the D1 function. Further transmissions of binary ONE change the state of the bus in the counterclockwise direction through the states shown in FIG. 3. From the initial state of the bus at the oval numbered 3, the transmission of a binary ZERO places the bus in a meta-stable state shown at the hexagon numbered 2. Upon acknowledgement of the transmitted ZERO by all bus users, the bus enters the stable state shown at the oval numbered 6 wherein the SB0 line has the ACK function, the SB1 line has the D0 function and the SEA line has the D1 function. Further transmissions of binary ZERO change the state of the bus in the clockwise direction through the states shown in FIG. 3.
There is a possibility that the meta-stable states of the bus may give rise to ambiguities among bus users reading the bus. In particular, during the meta-stable bus states, it is possible that some bus users could have recognized the next stable state sooner than other bus users. In a multi-user system, it is not uncommon that some users will read the bus more frequently than others. Some users may read the bus continuously. Other users may only sample the bus at regular or irregular intervals. If the state of the bus is meta-stable when a slow sampling users reads the bus, it can be ambiguous whether the state of the bus is in the same meta-stable state as the last time it was sampled or whether the bus has reached a stable state and returned to the meta-stable state during the time between the slow sampling user's samples of the bus. For example, if a slow sampling bus user recognizes a change in the bus state from state 6 to state 2 (FIG. 3), that user will release the ACK line and assume that other bus users will do the same so that the bus will move to stable state 3. Upon rereading the bus, and finding it in meta-stable state 2, once again, there is an ambiguity as to whether the bus has remained in that state rather than returned to that state (because of a transmitted zero) after achieving stable state 3.
The parent application also discloses several hardware implementations for point-to-point and multi-user buses, for example, using one, two, or three wire connections. While it is well known in the art to provide wireless data communication, or data communication which is based on a carrier where different keying methods are used to signal binary data, these carrier based communications methods also usually require a local clock or an encoded transmitted clock signal.
USPTO Backgrounds
USPTO Backgrounds