Not applicable.
Not applicable.
This invention is in the field of data communications, and is more specifically directed to coding techniques useful in serial data communication.
Data communication among computers has become widespread over recent years, connecting computer users and their applications to remote sources of data. Such communication may be relatively local, such as among computers in a small office over a local area network (LAN) among computers, within an enterprise but at different locations over a private wide area network (WAN) or xe2x80x9cintranetxe2x80x9d, among computers over the worldwide and public medium commonly referred to as the Internet. Additionally, in recent years, data communication among computers over wireless networks has become available, and is rapidly increasing in popularity.
Recent improvements in the data communication technology have provided huge increases in the bandwidth of the data communicated which in combination with the widespread coverage of the interconnected computers, has enabled new applications for computers and work stations. For example, data communications among computers are now of sufficient bandwidth to now enable the transmittal and receipt of multimedia signal, including audio and full-motion video. It is contemplated that these applications will become even more popular with the continuing widespread deployment of high speed networks, both public and private.
Typically, a large portion of the overall data communicated worldwide is communicated by way of a serial link. In a serial link, the data communication message is transmitted one bit at a time, in a bitstream, over a (wire or wireless) conductor between the source and the destination. Such serial communication may be synchronous, in which some form of clock is provided in connection with the communicated bitstream data either on a separate conductor or within the bitstream itself; the clock permits the receiver to sample the incoming bitstream at the appropriate points in time, so that the message communicated by the bitstream may be properly decoded. Asynchronous serial links are also known in the art, by way of which a series of bits in the bitstream following a xe2x80x9cstart bitxe2x80x9d are decoded according to a presumed line speed.
Of course, communication between any selected pair of end stations may involve many computers and data processing systems therebetween, particularly in the case of Internet communications. Over recent years, various standards have developed for such communications to effect communications among computers that were previously unconnected with one another. It is contemplated that any given message may be formatted and reformatted several times among various standard formats in its travels from its source to its destination. In each case, the formatting for transmission and receipt will generally involve coding according to a particular standard that has been selected for good communications performances both in accuracy and speed, over the particular leg of the network.
Many serial data communications standards have been promulgated to ensure compatibility of the numerous transmitting computers. According to many standards, the communications are packet-based, in that the transmitted bits and bytes of data are grouped into packets of data, which may be either of a fixed length (such as Asynchronous Transfer Mode, or ATM, communications) or of a variable length. Packet data communications permits error detection techniques to be applied, so that those packets that have been distorted in transmission to the extent of having one or more bit errors can be identified, and retransmitted if necessary. Each packet of data in a bitstream is typically delimited by known sequences that indicate the beginnings and ends of a given packet, so that the receiving computer can extract the data contained within the packet, and perform the appropriate error detection routines and other appropriate processing thereupon.
One well-known protocol for packet-based serial communications is referred to as High-level Data Link Control, or HDLC. According to this standard, each frame of communicated data includes start and end xe2x80x9cflagsxe2x80x9d, also referred to as opening and closing flags, in the bitstream that delimit a packet within the communicated bitstream. In the HDLC protocol, the start and end flags are identical, and are represented by a sequence of six xe2x80x9c1xe2x80x9d bits surrounded by xe2x80x9c0xe2x80x9d bits, or 01111110. FIG. 1 illustrates the arrangement of an HDLC frame. As shown therein, opening flag 2 and closing flag 12 are represented by the bit sequence 01111110. Following opening flag 2, address 4 indicates the Internet Protocol (IP) address that is to receive the communication, and control portion 6 includes the appropriate control bits associated with the frame. Following the actual data payload 8, a frame check sequence 10 is provided for verification of the data integrity by way of a cyclic redundant check (CRC) operation. The closing flag 12 then follows.
It is of course apparent from the foregoing that the communicated frame must not include a sequence of six xe2x80x9c1xe2x80x9d bits in succession at any point during the non-flag portions, as such an inadvertent sequence would be incorrectly interpreted as closing flag 12. In particular, address and control portions 4, 6 can be specified so as not to include this sequence, but data and FCS portions 8, 10 depend upon the message being transmitted and thus may include any particular sequence of bits as determined by the message itself. As a result, in the formatting of an HDLC frame, the transmitting network element must review the bitstream to be transmitted and insert a xe2x80x9c0xe2x80x9d after each sequence of five xe2x80x9c1xe2x80x9d bits in order to avoid an inadvertent flag. On the receiving end, the receiving network element can readily remove the inserted xe2x80x9c0xe2x80x9d bits by removing each xe2x80x9c0xe2x80x9d that appears after a sequence of five xe2x80x9c1xe2x80x9d bits. Of course, if the receiving network element sees a xe2x80x9c1xe2x80x9d after a sequence of five xe2x80x9c1xe2x80x9d bits, the sixth xe2x80x9c1xe2x80x9d indicates the presence of opening flag 2 or closing flag 12.
Many conventional approaches are known for bit insertion into HDLC and similar protocols for this reason. FIG. 2 illustrates, at a high level, a typical bit insertion approach, in which bit insertion circuit and buffer 14 receives an input bitstream IN and produces an output bitstream OUT, for transmission over the communications network. Bit insertion circuit and buffer 14 in this conventional approach first analyzes the front of the input bitstream IN by determining whether the particular pattern after which a bit is to be inserted appears thereat; in the HDLC example, the trigger pattern corresponds to the sequence 011111, where the leading xe2x80x9c0xe2x80x9d is either pre-existing in the data pattern or has been inserted as the result of detecting a previous contiguous trigger pattern. If not, a portion of the input bitstream is advanced to the output bitstream OUT. If, however, the trigger pattern is found, bit insertion circuit and buffer 14 inserts the desired bit (e.g., xe2x80x9c0xe2x80x9d), and then advances the bitstream by the corresponding number of bits according to the pattern that was matched.
It has been observed, according to the present invention, that this conventional approach is not particularly efficient. First, the bit insertion process is serial, in that identification of a second trigger pattern cannot begin until after the bit insertion process is complete for the previously detected trigger pattern. As a result, this conventional approach can be quite slow in its operation, and the processing time is necessarily dependent on the data being processed. Secondly, the number of bits that are advanced from bit insertion circuit and buffer 14 to output bitstream OUT will vary in a data-dependent manner, and can vary quite widely. Such operation requires relatively complex circuitry to implement the bit insertion function, considering the wide range in the number of bits to be examined, and also requires the downstream elements to expect data at rates that vary widely, and in a non-deterministic fashion.
By way of further background, other bit insertion techniques are also known in the art. One example is described in U.S. Pat. No. 5,119,478, in which each byte of the transmitted data is examined by way of specific logic circuitry (as shown in its FIG. 12) to generate logic signals corresponding to the potential insertion of zero bits; these logic signals are then applied to updating logic (as shown in its FIG. 13) which, after the application of additional logic circuitry, generates logic signal is that are applied to a coder that determines the number of xe2x80x9c0xe2x80x9d bits to be inserted in connection with the examined byte in transmission. U.S. Pat. No. 5,465,345 describes a bit insertion technique that relies upon a table lookup approach, in which a table is accessed according to values of certain counters pertaining to the number of consecutive xe2x80x9c1xe2x80x9d bits, to produce a data word from which the data frame is then built.
It is therefore an object of the present invention to provide a method and circuitry for serial transmission in which the processing time required is deterministic, and not data dependent.
It is a further object of the present invention to provide such a method and circuitry in which a constant rate of output bit forwarding may be achieved.
It is a further object of the present invention to provide such a method and circuitry in which identification of later instances of the bit insertion trigger pattern may take place without waiting for bit insertion for previous instances.
It is a further object of the present invention to provide such a method and circuitry that may be easily adapted to perform bit insertion over a wide range of protocols.
Other objects and advantages of the present invention will be apparent to those of ordinary skill in the art having reference to the following specification together with its drawings.
The present invention may be implemented into a serial transmission circuit, such as an instruction-programmable integrated circuit, in which an infinite impulse response (IIR) digital filter is applied to the data bitstream to detect sequences therein that require a bit to be inserted. The output of the IIR digital filter is an insertion bitstream having a bit associated with each bit of the data bitstream, and indicating the positions of those bits after which a bit is to be inserted. A downstream function analyzes the insertion bitstream, and modifies the transmission bitstream to insert bits of a desired state at the indicated locations.
USPTO Backgrounds
USPTO Backgrounds