Multipoint data communication system with collision detection

• US 4,063,220 A
• Filed: 03/31/1975
• Issued: 12/13/1977
• Est. Priority Date: 03/31/1975
• Status: Expired due to Term

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Thacker, Charles P., Lampson, Butler W., Boggs, David R., Metcalfe, Robert M.
• Primary Examiner(s): Caldwell, Sr., John W.
• Assistant Examiner(s): Groody, James J.
• Application Number:
  US05/563,741
• Time in Patent Office: 988 Days
• Field of Search: 340/147 R, 340/147 LP, 340/163, 340/151, 340/152 R, 340/152 T, 340/346, 325/22, 325/57, 178/58 A, 179/2 DP, 179/15 AS, 179/17 B, 179/30, 343/177, 343/180
• US Class Current: 370/462
• CPC Class Codes: G06F 13/376 using a contention resolving method, e.g. collision detection, collision avoidance
• CPC Class Codes: H04L 12/413 with random access, e.g. carrier-sense multiple-access with collision detection [CSMA-CD]
• CPC Class Codes: H04L 25/4904 using self-synchronising codes, e.g. split-phase codes

Abstract

Apparatus for enabling communications between two or more data processing stations comprising a communication cable arranged in branched segments including taps distributed thereover. Tied to each tap is a transceiver which on the other side connects to an associated interface stage. Each transceiver includes, in addition to the usual transmitter and receiver sections, a gate which compares the data from the interface stage with the data on the cable and indicates whether such are equal. Should such be unequal, an interference between the transceiver and the cable is indicated, disabling the associated transmitter section. Each interface stage tied to such transceiver also includes an input and an output buffer on the other end thereof interfacing with a using device, such input and output buffers storing both the incoming and outgoing data. The output buffer is connected to a clock-driven shift register which converts the buffered data to a serial stream, feeds such data to a phase encoder, which then connects to the transmitter or driver section of the transceiver. The input buffer is loaded by an input shift register which derives its clock from a phase decoder, the shift register and the phase decoder both connecting to the receiver section. When the station is to start transmitting, the phase decoder detects the presence of other transmissions on the cable and detains the output shift register until no other transmissions are sensed. Once a transmission has begun, if interference is detected and the transmitter section is disabled, a random number generator is used to select an interval of time at the completion of which the next attempted transmission will take place. Concurrently, a counter counts the number of interferences, or collisions, which recur in the attempted transmissions of one data packet and weights the mean of the random number generator accordingly. The input shift register is also connected to an address decoder which enables data transfer to the input buffer only during those times when the data is preceded by an appropriate address.

Claims

1. A data communication system comprising:

a communicating medium;

a plurality of transceivers connected to said medium, each transceiver including transmitting means for transmitting a signal onto said medium, and receiving means for receiving a signal communicated on said medium by another transceiver;

collision detecting means coupled to the transmitting means and the receiving means of each transceiver for generating a collision signal whenever a signal communicated on said medium by another transceiver is received by said receiving means during the time said transmitting means is transmitting a signal onto said communicating medium; and

means connected to each transceiver and responsive to the presence of said collision signal for interrupting the transmission of a signal onto said medium by said transmitting means.

2. The data communication system of claim 1, wherein said collision detecting means is included in each transceiver.

3. The data communication system of claim 1, further comprising:

interface means connected to each transceiver, said interface means including said means for interrupting therein, and also including means responsive to the absence of said collision signal for transmitting an output signal to said transmitting means, and means responsive to the receipt of a signal by said receiving means for generating an input signal; and

using means connected to said interface means for supplying data thereto and receiving data therefrom.

4. The data communication system of claim 3, wherein said interface means further includes buffer means for generating said output signal and for receiving said input signal.

5. The data communication system of claim 1, further comprising:

signal detecting means coupled to said receiving means for generating a carrier signal whenever a signal communicated on said medium by another transceiver is received by said receiving means prior to said transmitting means transmitting a signal onto said communicating medium; and

means connected to each transceiver and responsive to the presence of said carrier signal for preventing the transmission of a signal by said transmitting means.

6. The data communication system of claim 5, further comprising:

interface means connected to each transceiver, said interface means including said means for interrupting and said means for preventing therein, and also including means responsive to the absence of said collision and carrier signals for transmitting an output signal to said transmitting means, and means responsive to the receipt of a signal by said receiving means for generating an input signal; and

using means connected to said interface means for supplying data thereto and receiving data therefrom.

7. The data communication system of claim 6, wherein said interface means further includes buffer means for generating said output signal and for receiving said input signal.

8. A system according to claim 4, wherein:

said medium is a bit-serial medium; and

said interface means includes a first shift register connected for bit-serial receipt of said input signal from said receiving means and for parallel output of said input signal to said buffer means, an address filter connected to selected parallel outputs of said first shift register for enabling the transfer of said input signal upon a preselected combination thereof, a second shift register connected for parallel receipt of said output signal for converting said output signal to a bit-serial output signal, and a transmitter clock connected to said second shift register for controlling the rate of said bit-serial output signal.

9. A system according to claim 8, wherein:

said collision detecting means includes an exclusive OR gate means connected at one input thereof to the output side of said receiving means and at the other input thereof across delay means to the input side of said transmitting means, said delay means providing a signal delay substantially equal to the signal propagation delays through said transmitting and receiving means, the output of said OR gate means providing said collision signal.

10. A system according to claim 7, wherein:

said medium is a bit-serial medium; and

said interface means includes a first shift register connected for bit-serial receipt of said input signal from said receiving means and for parallel output of said input signal to said buffer means, an address filter connected to selected parallel outputs of said first shift register for enabling the transfer of said input signal upon a preselected combination thereof, a second shift reigster connected for parallel receipt of said output signal for converting said output signal to a bit-serial output signal, and a transmitter clock connected to said second shift reigster for controlling the rate of said bit-serial output signal.

11. A system according to claim 10, wherein:

said collision detecting means includes an exclusive OR gate means connected at one input thereof to the output side of said receiving means and at the other input thereof across delay means to the input side of said transmitting means, said delay means providing a signal delay substantially equal to the signal propagation delays through said transmitting and receiving means, the output of said OR gate means providing said collision signal.

12. A data communicating system comprising:

a bit serial communicating medium;

a plurality of transceivers connected to said medium, each transceiver including transmitting means and receiving means;

collision detecting means connected to said transmitting and receiving means for producing a collision signal when a signal produced by said transmitting means and a signal received by said receiving means are unequal;

interface means connected to said transmitting and receiving means to receive said collision signal and for transmitting an output signal to said transmitting means in the absence of said collision signal and for receiving signals from said receiving means to produce an input signal, said interface means including buffer means for producing said output signal and for receiving said input signal, a first shift register connected for bit-serial receipt of said input signal from said receiving means and for parallel output of said input signal to said buffer means, an address filter connected to selected parallel outputs of said first shift register for enabling the transfer of said input signal upon a preselected combination thereof, a second shift register connected for parallel receipt of said output signal for converting said output signal to a bit-serial output signal, and a transmitter clock connected to said second shift register for controlling the rate of said bit-serial output signal;

random number generating means operatively connected to said transmitter clock and including a fast clock for producing a random number signal according to the asynchronous relationship between said fast clock and said transmitter clock;

collision counting means connected to receive said collision signal for accumulating the repetition of said collision signal and for producing a count signal indicative thereof;

weighting means connected to receive said random number signal and said count signal for adjusting the mean value of said random number signal according to said count signal to produce an enabling signal to said second shift register; and

using means connected to transmit data to and receive data from said buffer means.

13. A system according to claim 12, further including:

overflow detecting means connected to receive said count signal for producing an error signal when said count signal exceeds a predetermined count.

14. A system according to claim 13, wherein:

said random number generating means includes a first counter connected to said fast clock;

said collision counting means includes a third shift register enabled by said buffer means and shifting out said collision signals;

said weighting means includes a plurality of first AND gates each receiving a selected signal from said first counter and said third shift register, an up-down counter loaded in parallel by the outputs of said AND gates and gated to count down by said collision signal; and

said overflow detecting means includes means connected to receive predetermined ones of the signals from said third shift register to produce said error signal.

15. A system according to claim 14, further comprising:

signal detecting means connected to the output of said receiving means for producing a carrier signal indicative of the presence of a signal on said medium; and

control means connected to receive said carrier, said collision and said weighting means output signals for preventing the transmission of said output signal in the presence of said carrier signal, for interrupting the transmission of said output signal upon the occurrence of said collision signal and for enabling said second shift register upon the occurrence of said weighting means output signal.

16. A system according to claim 15, further comprising:

isolation means included in said transceiver for isolating said interface means from said medium.

17. A data communication system comprising:

a bit-serial cummunicating medium;

a plurality of transceivers connected to said medium, each transceiver including transmitting means and receiving means;

collision detecting means connected to said transmitting and receiving means for producing a collision signal when a signal produced by said transmitting means and a signal received by said receiving means are unequal;

interface means connected to said transmitting and receiving means to receive said collision signal and for transmitting an output signal to said transmitting means in the absence of said collision signal and for receiving signals from said receiving means to produce an input signal;

said interface means includes a first shift register connected for bit-serial receipt of signals from said receiving means and for parallel output of said input signal to said buffer means, an address filter connected to selected parallel outputs of said first shift register for enabling the transfer of said input signal upon a preselected combination thereof, a second shift register connected for parallel receipt of said output signal for converting said output signal to a bit-serial output signal, and a transmitter clock connected to said second shift register for controlling the rate of said bit-serial output signal;

said interface means including buffer means for producing said output signal and for receiving said input signal;

random number generating means operatively connected to said transmitter clock and including a fast clock for producing a random number signal according to the asynchronous relationship between said fast clock and said transmitter clock;

collision counting means connected to receive said collision signal for accumulating the repetition of said collision signal and producing a count signal indicative thereof;

weighting means connected to receive said random number signal and said count signal for adjusting the mean value of said random number signal according to said count signal to produce an enabling signal to said second shift register;

overflow detecting means connected to receive said count signal for producing an error signal when said count signal exceeds a predetermined count; and

using means connected to transmit data to and receive data from said buffer means.

18. A system according to claim 17, wherein:

said collision means includes an exclusive OR gate means connected at one input thereof to the output side of said receiving means and at the other input thereof across delay means to the input side of said transmitting means, said delay means providing a signal delay substantially equal to the signal propagation delays through said transmitting and receiving means, the output of said OR gate means providing said collision signal.

19. A system according to claim 18, wherein:

said random number generating means includes a first counter connected to said fast clock;

said collision counting means includes a third shift register enabled by said buffer means and shifting out said collision signals;

said weighting means includes a plurality of first AND gates each receiving a selected signal from said first counter and said third shift register, an up-down counter loaded in parallel by the outputs of said AND gates and gated to count down by said collision signal; and

said overflow detecting means includes means connected to receive predetermined ones of the signals from said third shift register to produce said error signal.

20. A system according to claim 19, further comprising:

signal detecting means connected to the output of said receiving means for producing a carrier signal indicative of the presence of a signal on said medium; and

control means connected to receive said carrier, said collision and said weighting means output signals for preventing the transmission of said output signal in the presence of said carrier signal, for interrupting the transmission of said output signal upon the occurrence of said collision signal and for enabling said second shift register upon the occurrence of said weighting means output signal.

21. A system according to claim 18, further comprising:

filtering means connected to said OR gate for smoothing the output thereof.

22. A data communication system comprising:

a bit-serial data communication system;

a plurality of transceivers connected for communication with said medium, each transceiver including transmitting means and receiving means communicating with said medium;

communication sensing means operatively connected to said receiving means for detecting the presence of communications on said medium and for preventing transmissions from said transmitting means to said medium upon detecting the presence of other communications on said medium;

collision detecting means connected to said transmitting and receiving means for producing a collision signal when a signal produced by said transmitting means and a signal received by said receiving means are unequal;

interface means connected to said transmitting and receiving means to receive said collision signal and for transmitting an output signal to said transmitting means in the absence of said collision signal and for receiving signals from said receiving means to produce an input signal, said interface means including buffer means for producing said output signal and for receiving said input signal, a first shift register connected for bit-serial receipt of said input signal from said receiving means and for parallel output of said input signal to said buffer means, an address filter connected to selected parallel outputs of said first shift register for enabling the transfer of said input signal upon a preselected combination thereof, a second shift register connected for parallel receipt of said output signal for converting said output signal to a bit-serial output signal, and a transmitter clock connected to said second shift register for controlling the rate of said bit-serial output signal;

random number generating means operatively connected to said transmitter clock and including a fast clock for producing a random number signal according to the asynchronous relationship between said fast clock and said transmitter clock;

collision counting means connected to receive said collision signal for accumulating the repetition of said collision signal and producing a count signal indicative thereof; and

weighting means connected to receive said random number signal and said count signal for adjusting the mean value of said random number signal according to said count signal to produce an enabling signal to said second shift register; and

using means connected to transmit data to and receive data from said buffer means.