Electrical computers and digital processing systems: multicomput – Computer-to-computer protocol implementing – Computer-to-computer data framing
Reexamination Certificate
1996-07-12
2001-10-02
Chan, Eddie (Department: 2183)
Electrical computers and digital processing systems: multicomput
Computer-to-computer protocol implementing
Computer-to-computer data framing
C370S509000, C375S368000, C710S057000
Reexamination Certificate
active
06298387
ABSTRACT:
TECHNICAL FIELD
The invention relates to the field of computer communications, and in particular, to the area of detecting the start of a packet within a bitstream.
BACKGROUND OF THE INVENTION
Packets in a bitstream are often delineated by the appearance therein of a particular data value, e.g., a particular 8 bit wide (byte or octet) data pattern, which may be termed the “synchronization pattern”. When the synchronization pattern is 8 bits in length, it is often referred to as a synchronization byte. When explicit framing signals are not received along with the bitstream, the equipment receiving the bitstream can use the synchronization pattern to identify the start of a packet. Doing so, however, is complicated when the particular data value employed as the synchronization pattern can appear elsewhere within the bits that make up the rest of a packet. Such an appearance may occur a) when the value of the synchronization pattern is not reserved solely for identifying the start of a packet, b) when the bitstream does not have any predefined bit group, e.g., byte, alignment, or c) when errors occur in the bitstream.
For example, according to the so-called “motion pictures expert group-2” (MPEG-2) international standard ISO/IEC 13818-1, the data value used for the synchronization pattern, referred to therein as the “sync-byte”, is 0×47. Each MPEG-2 transport bitstream packet has a length of 188 bytes, the first of which is the sync-byte. Thus, a sync-byte should appear in the bitstream every 188 bytes.
According to one prior art technique, each 8 bit pattern of an MPEG-2 bitstream is tested to determine if it is a sync-byte. The testing is performed using an eight bit window that is slid one bit each time the test is performed, until a sync-byte is found. When a tested group of eight bits matches the sync-byte, the next 187 eight bit groups are counted as they pass, but they are not tested. Then, the 189th byte is tested to determine if it is a sync-byte. If so, it is determined that the preceding 188 bytes, i.e., the first found sync-byte and the counted 187 eight bit groups, were likely to have been a packet. The process is then repeated several times to minimize the chance that the apparent detection of sync-bytes spaced apart by the length of one packet is the result of a value equal to that of the sync-byte randomly appearing in the bitstream at the correct interval and not actual packet delineating sync-bytes. Note that the appearance in the bitstream of a value equal to that of the sync-byte at a position where a sync byte should not appear is referred to as “sync-byte emulation”. If ever the 189th 8 bit pattern does not conform to the sync-byte, the process is restarted.
Disadvantageously, in applications where there is sync-byte emulation, this technique may be slow to determine that a packet has been received. Also, the delineation process causes the loss of the data of all of the packets used to determine the packet delineation.
SUMMARY OF THE INVENTION
An improvement in the delineation of packets in a bitstream is achieved, in accordance with the principles of the invention, by 1) employing a first in, first out buffer (FIFO) that has a) an effective storage capacity equal to the number of bits in a packet plus the number of bits in the synchronization pattern and b) is arranged so that a comparison may be made of the data in its head end and its tail end with the data pattern of the synchronization pattern, and 2) declaring that a packet is detected when both the head end and the tail end of the FIFO each, substantially simultaneously, contains information equal to the synchronization pattern. In the event that packets within a bitstream may have different lengths, the effective storage capacity of the FIFO may be adjusted if the packet length to be detected is known a priori, or the FIFO may be arranged to have multiple simultaneous effective tail ends. If different packets of the bitstream may have different synchronization patterns, multiple comparators may be employed to check for valid combinations of synchronization patterns, and this may be done at proper displacements within the bitstream. A state machine may be employed to keep track of complex cycles of synchronization patterns that may be expected. Advantageously, the invention may be employed whether or not the bitstream is byte-, or other group of bits-aligned.
In one embodiment of the invention, data from the incoming bitstream is supplied to the FIFO. Once the FIFO is filled, each time a new unit of data is suppled to the FIFO the head end and the tail end thereof are both checked to determine if they contain the synchronization pattern. If so, a packet is preliminary declared and the checking and preliminary declaration process is repeated a predetermined number of times, but only at intervals of time equal to the time necessary for an entire packet to exit the FIFO rather than each time a new unit of data is supplied to the FIFO. These repetition are performed to assure that the synchronization pattern is validly detected at the correct intervals within the bitstream, thus minimizing the chance of a false packet delineation due to emulation of the synchronization pattern. Performance of each repetition only at the packet interval is contingent upon the prior repetition resulting in a preliminary packet declaration. Upon successful completion of all repetitions, packets are then indicated to be valid and they are delineated each time tail end data completes transiting through the FIFO to the head end, provided that the tail end contains a synchronization pattern at that time. If any of the repetitions prior to declaring packets to be valid fails to result in a preliminary declaration, the process is restarted so that the head end and the tail end of the FIFO are both checked each time a new unit of data is suppled thereto.
REFERENCES:
patent: 3938106 (1976-02-01), Becker et al.
patent: 4208650 (1980-06-01), Horn
patent: 4344180 (1982-08-01), Cummiskey
patent: 4458314 (1984-07-01), Grimes
patent: 4665396 (1987-05-01), Dieleman
patent: 4922438 (1990-05-01), Ballweg
patent: 5644577 (1997-07-01), Christensen et al.
patent: 5668840 (1997-09-01), Takano
patent: 5671227 (1997-09-01), Keller et al.
IBM-TDB (Service processor architecture and microcode algorithm for performing console custmization under customer control TDB, pp. 130-135, Nov. 1988.*
John Uffenbeck (Microcomputers and Microprocessors) 1985, Prentice-Hall, Inc., pp. 415-416.
Akiwumi-Assani Samuel Olu
Lin Chin-Sung
Prasad Sanand
Chan Eddie
Gross Russell
Patel Gautam R.
Philips Electronics North America Corp
LandOfFree
System for detecting a data packet in a bitstream by storing... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System for detecting a data packet in a bitstream by storing..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System for detecting a data packet in a bitstream by storing... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2575968