Deterministic bit insertion into serial communications

Details Deterministic bit insertion into serial communications Deterministic bit insertion into serial communications

2000-11-15

2004-11-16

Lee, Andy (Department: 2663)

Multiplex communications

Communication techniques for information carried in plural...

Combining or distributing information via time channels

C375S365000

Reexamination Certificate

active

06819684

ABSTRACT:

CROSS-REFERENCE TO RELATED APPLICATIONS
Not applicable.
STATEMENT REGARDING FEDERALLY SPONSORED RESEARCH OR DEVELOPMENT
Not applicable.
BACKGROUND OF THE INVENTION
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 “intranet”, 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 “start bit” 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 “flags”, 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 “1” bits surrounded by “0” 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 “1” 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 “0” after each sequence of five “1” bits in order to avoid an inadvertent flag. On the receiving end, the receiving network element can readily remove the inserted “0” bits by removing each “0” that appears after a sequence of five “1” bits. Of course, if the receiving network element sees a “1” after a sequence of five “1” bits, the sixth “1” 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 “0” 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., “0”), 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, consider

Affiliated with

Also associated with

Rating

Deterministic bit insertion into serial communications does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Deterministic bit insertion into serial communications, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Deterministic bit insertion into serial communications will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3288126