Abstract:
A CITO communication block transmitter which provides for increased data compression by sorting the entire global data of senders which share a CITO communication channel is disclosed. With this technique, a sender transmits a full block of its data in a single data bucket instead of having to utilize many separate data buckets. The CITO block transmitter comprises a next-data register, a next-bit position register, a data-ready register a FIFO buffer and a block transmitter in addition to the basic CITO registers.

Description:
BACKGROUND OF THE INVENTION 
     Field of the Invention 
     The present invention is related to the field of computer communications and more particularly to a Content Induced Transaction Overlap (CITO) driver which transmits a block of data. 
     Description of the Prior Art 
     Various types of multiple-access channel communication systems are known in the art. These communication systems may conveniently be divided into two distinct types, the Time Division Multiple Access (TDMA) systems, and the Carrier Sensed Multiple Access (CSMA) systems. In Time Division Multiple Access systems as disclosed by Hopkins et al in U.S. Pat. No. 4,161,786; Lowe, Jr. In U.S. Pat. No. 4,199,662 or White et al in U.S. Pat. No. 4,199,661 the transmission channel capacity is divided into time slots during which identified transmitters are allowed to transmit their information over the communication network. Each transmitter is assigned a specific time slot so that each transmitter in turn will have an opportunity to transmit its information. In Carrier Sensed Multiple Access systems, such as disclosed by Eswaran et al in U.S. Pat. No. 4,292,623, Herzog, U.S. Pat. No. 4,199,663, or Spracklen et al in U.S. Pat No. 4,337,465, each transmitter detects when the communication channel is idle, then after a predetermined period of time, attempts to transmit its information. Typically, the waiting period depends on the assigned priority of the transmitter. 
     The problem with the Time Division Multiple Access system is that often a particular transmitter may not have any information to transmit during its allotted time slot, while other transmitters may generate two or more messages in the period between their allotted time slots. Therefore some transmission time slots are wasted while other messages are delayed while awaiting access to the common transmission line. This problem is partially overcome by the Carrier Sensed Multiple Access system under light or moderate loads. However under high message traffic conditions, the probability of simultaneous access to the common transmission line rises sharply, and excessive amounts of time are wasted resolving priority differences of the involved transmitters. A Content Induced Transaction Overlap Communication System (CITO) as disclosed by Walter et al in U.S. Pat. No. 4,493,074, and assigned to the same assignee as the present invention, is hereby incorporated by reference and is designed to overcome these problems. The present invention is an improvement of the CITO communication channel because the present invention allows the transmission of a block of data of a processor within a bucket in lexicographical order. 
     A CITO communication system is designed for transmitting data from a plurality of senders to a receiver over a single communication channel. Each sender has a data register which stores the multiple bit data word to be transmitted, a word boundary register which stores the number of bits in the data word and a bit position register. The transmission begins with each sender transmitting the highest order bit stored in the data register. Bits are transmitted on the channel in an overlapped manner such that the channel state is the logical sum or product of the transmitted bits. Using single phase representation, where a zero bit is transmitted as a finite signal level and a one bit is transmitted as a null signal level, the composite channel states are accordingly 0 or 1. 
     The senders each then compare the state of the communication channel with their transmitted bit to determine if they are the same. If the state of the communication channel is the same as the transmitted bit, the sender transmits its next highest bit and decrements its word boundary and bit position registers. However, if the state of the communication channel is different from its transmitted bit, the sender terminates the transmission of its remaining bits but continues to monitor the communication channel and decrement its word boundary register for each bit transmitted on the communication channel. At the end of the transmission of the data word, indicated by the word boundary register being decremented to zero, each sender enters into bit competition with all of the senders based on the content of its bit position register when it stopped transmitting to determine if it has lexicographically the next smallest data word. If it has, it initiates the sending of its remaining data bits. However, if it doesn&#39;t have lexicographically the next smallest data word, the sender waits until the end of the transmission of the current data word and re-enters the bit competition. This cycle repeats until all of the senders have completed the transmission of all the bits in their data words. At this point, all the bit position registers are at zero and no sender performs in the bit competition. The senders recognize the termination of the current data bucket (collection of data bits in the different senders) and the transmission of the next data bucket can begin after sYnchronization. 
     One of the major advantages of CITO over other communication methods is that it provides for the sorting of data as a by-product of the communication protocol. CITO, however, only provides for the sorting of data in the currently transmitted data bucket. The prior art CITO driver allows each Sender to transmit, at most, a single data item in the data bucket. This restriction severely limits the usefulness of the sorting capability of CITO because each Sender may have many data items. Another advantage of CITO is its data compression capability, however, a transmission method of at most, one data item per data bucket, also reduces the data compression capability. If a Sender has n data items to transmit and no other Senders want to transmit, then the Sender must transmit each data item one by one as a separate independent data bucket. Thus, there is no data compression. 
     The known solution for providing CITO data compression for a block of data within a single Sender is to incorporate a content addressable memory (CAM) into a CITO driver. If a Sender writes a block of its data into the CAM, the CITO driver can transmit the entire data of the CAM within the same bucket because CAM provides various associative functions such as the calculation of the next minimum value. However, CAM has a high pin/circuit ratio and a high power dissipation. Thus, it is not only expensive, but the fabrication of a large size CAM may not be feasible because of the status of current technology. Also, CITO needs only the one operation, calculation of the next minimum value, not the many associative operations of CAM, therefore, the implementation of CAM for CITO wastes most of CAM&#39;s capability. 
     A variety of other techniques exist for the transmission of data with data reduction. One such technique is a Data Exchange Processor For Distributed Computing System invented by Kober and disclosed in U.S. Pat. No. 4,181,936. This patent describes a distributed computing system which has a data exchange processor that is especially adapted to control operations involving the transfer of data among components of the distributed computing system. This system differs from the present invention because the distributed computing system does not provide for the transmission of distributed messages in lexicographical order. U.S. Pat. No. 4,698,628 by Herkert et al, discloses A Method And Apparatus For Transmission Of Data With Data Reduction. In this patent the data which is transmitted between the several network levels is reduced by deleting data which corresponds to a predetermined information content. This disclosure differs from the present invention because this disclosure does not provide for the transmission of distributed messages in lexicographical order. U.S. Pat. No. 4,598,411 issued to Berkovich et al and assigned to the same assignee as the present invention is hereby incorporated by reference and discloses an On-The-Fly Data Compression System. This system compresses the data transmitted between the data source and ultimate utilization device. The data compression modules compress the data using a word representation by associative processing buffer and a content induced transaction overlap (CITO) transmission protocol which results in an interleaved transmission of data bits and bit position bits, the latter being indicative of the number of data bits that will be transmitted during the subsequent data transmission. This disclosure, however, differs from the present invention because it does not provide for the transmission of a block of data of a Sender within a data bucket in lexicographical order. 
     SUMMARY OF THE INVENTION 
     This invention represents a CITO communication block transmitter which provides for increased data compression by sorting the entire global data of Senders which share a CITO communication channel. This technique is performed by allowing a Sender to transmit a full block of its data in a single data bucket instead of having to utilize many separate data buckets. For the block transmission of data, a CITO device needs a next-data register (NDR), a next-bit position register (NBPR), a data-ready register (DRR) a FIFO buffer and a block transmitter in addition to the basic CITO registers which are a data register (DR), a bit position register (BPR), and a word boundary register (WBR). 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     FIG. 1 is a block diagram of a multiple access communications system. 
     FIG. 2 is a block diagram illustrating the interface elements of a prior art Sender in a content induced transaction overlap (CITO) communication system. 
     FIG. 3 is a block diagram illustrating the interface elements of a Sender having a CITO block transmitter. 
     FIG. 4 is a flow diagram of the transmitter of the CITO block communication system. 
     FIG. 5 is a flow diagram of the block transmitter of the CITO block communication system. 
    
    
     DETAILED DESCRIPTION OF THE INVENTION 
     The content induced transaction overlap communication system is intended to solve many of the problems that exist when many transmitters require multiple access to a single communication channel to a common receiver. FIG. 1 is a block diagram of a typical system having multiple Senders 10, 12, 14, 16 and 18 transmitting information to a Receiver 20 over a common communication channel or Bus 30. Each Sender 10, 12, 14, 16 and 18 is capable of randomly sending information which is required by the Receiver 20. The Senders 10, 12, 14, 16 and 18 may represent individual sensors, controls, or other types of inputs, or may be individual microprocessors in a multiple computer system or individual computers in a fault tolerant computer network or any combination of the above. The Receiver may be a utilization device, or master in a multiple computer system, or any other similar device. 
     From the prior art, as shown in FIG. 2, the interface portion 11 of each Sender 10, 12, 14, 16 and 18 embodies a data register (DR) 32, a bit position register (BPR) 34, a channel status register (CSR) (receiver) 36, a word boundary register (WBR) 38 and a transmitter 5. The data register 32 holds the data word to be transmitted to the CITO communication channel 30. The data word is shifted out of the data register 32 to the CITO communication channel 30 one bit at a time in serial fashion. The bit position register 34 is loaded with the number of bits (r) in the data word to be sent after the Sender has synchronized with the channel. It is decremented every time the Sender successfully transmits a data bit. It is also used to determine access privilege to the communication channel. The channel status register 36 is a one bit register which stores the bit value of the last transmission on the communication channel and functions as the receiver portion of the Sender. The word boundary register 38 keeps track of the number of bits that have been sent over the communication channel and is used to determine when a word has been completely transmitted. Until the word is completely transmitted, the word boundary register 38 signals the Sender to attempt to continue its data transmission. 
     As illustrated in FIG. 3, the interface portion 13 of each Sender 10, 12, 14, 16 and 18 has a CITO block transmitter, a next-data register (NDR) 2, a next-bit position register (NBPR) 4, a data-ready register (DRR) 6, and a FIFO buffer 8 in addition to the basic CITO registers which are the data register (DR) 32, the bit position register (BPR) 34, the word boundary register (WBR) 38, and the channel status register 36. 
     To drive the data to and from the various registers and the CITO communication channel 30, there are two functional units, a transmitter 5 and a block transmitter 9. While the transmitter 5 transmits the data from data register 32, onto the CITO communication channel 30, the block transmitter 9 loads the next-data register 2 from the FIFO buffer 8, calculates the next-bit position and sets the next-bit position register 4 to the value. The next-bit position is the location of the first bit of the next-data register (NDR) whose value is not equal to that of the data register 32. After completion of the transmission of the data register 32, the transmitter 5 loads the data register 32 and the bit position register 34 from the next-data register 2 and the next-bit position register 4. 
     The FIFO buffer 8 is required to provide a continuous supply of data to the block transmitter 9. Without the FIFO buffer, the Sender would have to provide the next data item immediately after each transmission of the data item. This would severely reduce the performance of the Sender. With the FIFO buffer, the Sender may write a block of data into the FIFO buffer, as long as the FIFO buffer is not full, without waiting for the completion of data transmission. Thus the Sender is interrupted less frequently. 
     The detailed functional description of the transmitter 5 is as follows. Referring to FIG. 4, the transmitter begins with testing the data-ready register (DRR) as indicated by block 40. If it is ready, the transmitter loads the data register (DR) from the next-data register (NDR) and initializes registers as indicated by block 42. Block 44, illustrates the typical prior art transmission of data using the prior art CITO communication method. After completion of a typical transmission as indicated by the condition &#34;yes&#34; of block 46, the transmitter tests the data-ready register (DRR) as indicated by block 48. If it is not ready, the transmitter completes the transmission of a bucket of data as indicated by block 50. If it is ready, the transmitter examines the value of the next-data register (NDR) at the position of the next-bit position register (NBPR) as indicated by block 52. This test is required to provide the internal CITO data compression of arbitrary data and to prevent the possible error caused by out-of-order data supplied by the Sender. If it is &#34;1&#34;, the value of the next data is larger than that of the current data. Thus the transmitter can immediately participate in the next bit competition and the next data can be transmitted within the current data bucket as indicated by block 54. If the value of the next-data register at the next-bit position is &#34;0&#34;, the value of the next data is smaller than that of the current data; thus transmission has to be suspended until the end of the current data bucket and the next data may be transmitted at the beginning of the next bucket as indicated by block 50. 
     A CITO transmission consists of two types of messages, bit position and data. The length of the data varies from a full length (r), for the first data item in the bucket, to zero, for the message suspended at the last position. However, the length of the bit position message is always a constant log(r). Thus there will be at least log(r) time slots available for the Sender to prepare the next data transmission and therefore provide for the continuous transmission of a block of data. 
     While the transmitter 5 transmits the data from the data register (DR) 32, the block transmitter 9 prepares the next data from the FIFO buffer. As illustrated in FIG. 5, the block transmitter 9 begins with testing the status of the FIFO buffer as indicated by block 60. If it is empty, the block transmitter continues to test the status. If it is not empty, the block transmitter tests the data-ready register (DRR) until it becomes &#34;1&#34; as indicated by block 62. If it is &#34;1&#34;, the block transmitter loads the next-data register from the top of the FIFO buffer and sets the index i to 1 as indicated by block 64. The block transmitter tests the index i and if it is &#34;r&#34; the block transmitter terminates as indicated by block 66. If it is not &#34;r&#34;, the block transmitter tests whether the value of the data register (DR) being transmitted at the bit position i is equal to that of the next-data register (NDR) as indicated by block 68. If they are equal, the block transmitter increases the index i by 1 and repeats the above tests as indicated by block 70. If they are not equal, the block transmitter sets the next-bit position register (NBPR) and data-ready register (DRR) to (r-i+1) and 1, respectively, as indicated by block 72. After setting the registers, the block transmitter completes the processing of one data item and repeats all of the above processes as indicated by block 74. 
     It is not intended that this invention be limited to the hardware or software arrangement, or operational procedures shown disclosed. This invention includes all of the alterations and variations thereto as encompassed within the scope of the claims as follows.