Bit stuffing for synchronous HDLC

Details Bit stuffing for synchronous HDLC Bit stuffing for synchronous HDLC

1999-07-07

2004-01-06

Chin, Wellington (Department: 2664)

Multiplex communications

Communication techniques for information carried in plural...

Combining or distributing information via time channels

C370S529000

Reexamination Certificate

active

06674770

ABSTRACT:

The present invention relates generally to data communication and data link control protocols, and in particular to flag hunting and bit stuffing methods in communication according to HDLC and devices for accomplishing the methods.
BACKGROUND
In all communication systems according to the state of the art different link protocols are responsible to keep track of the traffic. For digital data communication, the most important data link control protocol is HDLC (ISO 33009, ISO 4335).
The lowest level of this protocol is the part which sends data packets, so called frames, on a serial channel. Each frame is preceded by a specific bit pattern which indicates the start of the frame. This specific bit pattern is usually denoted a flag. The binary value of this flag in the HDLC-like protocols is represented by the eight bits 0111 1110. This flag is also added after each frame to indicate the end of the frame. The frames may vary in length and the stop flag is therefore necessary to identify the frame end.
The receiver of these kind of frames searches the incoming bit stream for the start flag. This procedure known in the art is called flag hunt. When a flag is detected, the receiver collects the incoming bits as the content of an incoming frame. This collection continues until the flag is detected once again, which now serves as a stop flag indicating the end of frame. However, since the content of the frame is a arbitrary series of 0's and 1's, the selected flag pattern may incidentally appear somewhere in the data. This appearance will then be interpreted as a flag and the frame-level synchronisation is destroyed.
To avoid this problem, it is known in the art to use a procedure defined as “bit stuffing”. An example of such a bit stuffing procedure is as follows: between the transmission of the start and stop flags, the transmitter will always insert an extra 0 bit after each occurrence of five 1's in a row, transmission bit stuffing. The receiver then must perform the inverse function. Accordingly, after detecting a start flag, the receiver monitors the bit stream. When a pattern of five 1's in a row appears, the sixth bit is examined. If this bit is 0, it is deleted. If this bit is a 1 and the seventh bit is 0, the combination is accepted as a flag. If the sixth and seventh bits both are 1, the sender is indicating an abort condition. This is an example of a flag hunting and reception bit stuffing procedure according to the state of the art.
When discussing bit “stuffing” in the below description, the expression “stuffing” is intended to include both the insertion and the removal of the extra bit. Accordingly, “stuffing” in a transmitter means the insertion of an extra character, and “stuffing” in a receiver refers to the procedure of removing the stuffed character.
When using a protocol like HDLC, which uses flags and bit stuffing, normally the hardware in the serial port performs these tasks. If the serial port does not support this, some extra hardware is added. Handling the flags and bit stuffing, both insertion and removal, i.e. transmission and reception bit stuffing, respectively, are easily implementable in hardware. Such solutions are e.g. disclosed in the U.S. Pat. Nos. 5,263,056, 5,280,502, 5,357,514 and 5,331,671, the published Japanese patent application A, 59-044139 and the published European Patent Application 0 480 566 A2.
However, when implementing bit stuffing in software in e.g. a general DSP (Digital Signal Processor), there are severe problems in writing efficient code. This is due to the fact that DSPs and CPUs (Central Processing Unit) are created to work efficient with bytes (8 bits), words (16 bits) or long words (32 bits), and not to work with single bits. It is possible to work with bits in general purpose processors, but this normally uses many instructions per bit. This is also the manner in which bit stuffing normally is implemented in the state of the art. The problem is that since this implementation uses a significant part of the processor capacity, there is less capacity available for other tasks. Thus, there is a severe problem in general DSPS, that bit stuffing requires an unproportionally big part of the processor capacity.
The Japanese patent JP 9305509 discloses an apparatus temporarily storing a data row. A data search unit then searches the bit row for a flag sequence pattern.
SUMMARY
An object for the present invention is thus to provide a method and device for bit stuffing in general digital systems using software routines, which requires less processor power and time than methods according to the state of the art.
The above object is achieved by the methods disclosed in the independent claims. A method according to the present invention contains a process related to bit stuffing, comprising the steps of selecting n bits from a first queue forming a first bit sequence, comparing the first bit sequence with prestored bit stuffing data and performing actions with the selected bit sequence and first queue according to data comprised in the prestored bit stuffing data. In a bit stuffing process according to the present invention a number of bits are added to a second queue and a number of bits are removed from the first queue, said bit sequences or number of bits are determined from the prestored bit stuffing data. The process of comparing the selected bit sequence with prestored data is possible to perform in all steps involved with bit stuffing, both in the transmitting process and in the receiving process, and during flag hunting as well as bit stuffing. In a preferred embodiment the prestored bit stuffing data is in the form of a lookup table.
A device for bit stuffing related processes according to the present invention comprises a first storage means for storing a first queue of bits, a second storage means comprising prestored bit stuffing data and stuffing means for selecting n bits from the first queue forming a first bit sequence, for comparing the first bit sequence with the prestored bit stuffing data and for performing actions with the selected bit sequence and first queue according to data comprised in the prestored bit stuffing data. A device for bit stuffing according to the present invention further comprises a third storage means for a second queue of bits, and the stuffing means comprises means for adding a number of bits to the second queue and means for removing a number of bits from the first queue, said bit sequences or number of bits are determined from the prestored bit stuffing data. A device for bit stuffing related processes may be present both in the transmitter and in the receiver. In a preferred embodiment the second storage means comprises a lookup table with the prestored bit stuffing data.


REFERENCES:
patent: 5263056 (1993-11-01), Urbansky
patent: 5280502 (1994-01-01), Niegel et al.
patent: 5331671 (1994-07-01), Urbansky
patent: 5357514 (1994-10-01), Yoshida
patent: 5428611 (1995-06-01), Jain et al.
patent: 5570306 (1996-10-01), Soo
patent: 5586273 (1996-12-01), Blair et al.
patent: 5675617 (1997-10-01), Quirk et al.
patent: 0 346 555 (1989-12-01), None
patent: 0 480 566 (1992-04-01), None
patent: 0 544 963 (1993-06-01), None
patent: 93/05509 (1993-03-01), None

Affiliated with

Also associated with

Rating

Bit stuffing for synchronous HDLC does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Bit stuffing for synchronous HDLC, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Bit stuffing for synchronous HDLC will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3266372