US4974223A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Parallel architecture for high speed flag detection and packet identification
Assignee: International Business Machines Corp
•
Filing: 1989-09-18
•
Granted: 1990-11-27
•
Expires: 2009-09-18
Abstract
Abstract The present invention identifies boundaries of data packets within a serial data stream and transfers data belonging to these packets to an external device for processing or storage. Identification is accomplished at relatively high speed by parallel processing techniques using a state machine. Data may be transmitted through separate channels to a multiple channel link. This link selects one channel at a time for a predetermined period of time, and allows the data stream from the selected channel to be transmitted to the flag detector. Some of the bits in the digital data stream may be part of a flag. The flag detector generates a value corresponding to the number of bits which may correspond to a portion of a flag in the data that has entered the flag detector. Additional data from the digital data stream entering the flag detector may include the remaining bits of the flag. If so, then the detector indicates that a flag has been found. Based on the location of a flag, boundaries may be determined for data in a packet.
Inventors
- 👤 Teofilo C. Ancheta
- 👤 Alexander Birman
- 👤 Pao-Chi Chang
- 👤 Roch Guerin
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-31 17:35
CPC Classifications
H; H04; H04L; H04L9/00; H04L9/40; H04L69/00; H04L69/30; H04L69/32; H04L69/322; H04L69/324
Claims Analysis
Total Claims: 20
Claim 1
Independent Claim
145 words
A method of detecting a packet boundary in a digital data stream, wherein the packet boundary is identified by a predetermined bit pattern, said method comprising the steps of: (a) receiving a first plurality of data bits; (b) examining the first plurality of data bits for a first fractional part of said predetermined bit pattern wherein the examination of each bit position of the plurality of data bits is performed concurrently; (c) receiving a second plurality of data bits; (d) examining the second plurality of data bits for a second fractional part of said predetermined bit pattern wherein the examination of each bit position of the second plurality of data bits is performed concurrently; (e) determining a packet boundary based upon the location of the first fractional part of said predetermined bit pattern and the location of the second part of said predetermined bit pattern.
Claim 2
Independent Claim
145 words
A method of detecting a packet boundary in a digital data stream, wherein the packet boundary is identified by a predetermined bit pattern, said method comprising the steps of: (a) receiving a first plurality of data bits; (b) examining the first plurality of data bits for a first fractional part of said predetermined bit pattern wherein the examination of each bit position of the plurality of data bits is performed concurrently; (c) receiving a second plurality of data bits; (d) examining the second plurality of data bits for a second fractional part of said predetermined bit pattern wherein the examination of each bit position of the second plurality of data bits is performed concurrently; (e) determining a packet boundary based upon the location of the first fractional part of said predetermined bit pattern and the location of the second part of said predetermined bit pattern.
Claim 3
Independent Claim
150 words
A method of detecting a packet boundary in a digital data stream, wherein the packet boundary is identified by a predetermined bit pattern, said method comprising the steps of: (a) receiving a plurality of data bits; (b) examining the first plurality of data bits in parallel to locate a first fractional part of said predetermined bit pattern in terms of a distance for the first plurality of data bits, said distance being determined by a bit location, in the first plurality of data bits, of a significant bit of predetermined value; (c) receiving a second plurality of data bits; (d) examining the second plurality of data bits in parallel to locate a second fractional part of said predetermined bit pattern; and (e) determining a packet boundary based upon the distance for the first plurality of data bits and the location of the second fractional part of said predetermined bit pattern.
Claim 4
Independent Claim
150 words
A method of detecting a packet boundary in a digital data stream, wherein the packet boundary is identified by a predetermined bit pattern, said method comprising the steps of: (a) receiving a plurality of data bits; (b) examining the first plurality of data bits in parallel to locate a first fractional part of said predetermined bit pattern in terms of a distance for the first plurality of data bits, said distance being determined by a bit location, in the first plurality of data bits, of a significant bit of predetermined value; (c) receiving a second plurality of data bits; (d) examining the second plurality of data bits in parallel to locate a second fractional part of said predetermined bit pattern; and (e) determining a packet boundary based upon the distance for the first plurality of data bits and the location of the second fractional part of said predetermined bit pattern.
Claim 5
Dependent Claim
60 words
The method of claim 2, wherein step (e) comprises the steps of: (a) determining the presence of a flag based on the results of steps (b) and (d); and (b) determining a boundary for the flag wherein the boundary is a measure of the position of the flag relative to the beginning of a transmission of the digital data stream.
Claim 6
Dependent Claim
21 words
The method of claim 2, wherein, in step (b), each bit of the first plurality of data bits is examined concurrently.
Claim 7
Dependent Claim
21 words
The method of claim 2, wherein, in step (e), each bit of the second plurality of data bits is examined concurrently.
Claim 8
Independent Claim
86 words
A method of using a state machine to locate a flag in a digital stream of data, wherein said flag consists of a predetermined bit pattern, said method comprising the steps of: (a) placing a plurality of bits, including a predetermined fraction of said digital stream of data, into the state machine; (b) concurrently examining each bit in said fraction of said digital data stream to generate a value corresponding to a number of bits occupied by the flag in the fraction of said digital stream.
Claim 9
Independent Claim
86 words
A method of using a state machine to locate a flag in a digital stream of data, wherein said flag consists of a predetermined bit pattern, said method comprising the steps of: (a) placing a plurality of bits, including a predetermined fraction of said digital stream of data, into the state machine; (b) concurrently examining each bit in said fraction of said digital data stream to generate a value corresponding to a number of bits occupied by the flag in the fraction of said digital stream.
Claim 10
Dependent Claim
22 words
The method of claim 6, comprising the additional step of indicating if all the bits that constitute a flag have been received.
Claim 11
Independent Claim
142 words
A method of determining the relationship between a packet boundary and a byte boundary in a data stream, wherein the packet boundary is defined as a discontinuity in the data stream and the byte boundary is defined as a logical separation between successive groups of contiguous bits of data, said method comprising the steps of: (a) locating a fraction of flag pattern from a first group of contiguous bits of the data stream wherein said flag determines said packet boundary; (b) locating a second fraction of a flag from a second group of contiguous bits of the data stream; (c) determining an offset between the packet boundary and the byte boundary defined by said first and second groups of contiguous bits by evaluating the number of bits occupied by the flag in the second group of contiguous bits of said data stream.
Claim 12
Independent Claim
142 words
A method of determining the relationship between a packet boundary and a byte boundary in a data stream, wherein the packet boundary is defined as a discontinuity in the data stream and the byte boundary is defined as a logical separation between successive groups of contiguous bits of data, said method comprising the steps of: (a) locating a fraction of flag pattern from a first group of contiguous bits of the data stream wherein said flag determines said packet boundary; (b) locating a second fraction of a flag from a second group of contiguous bits of the data stream; (c) determining an offset between the packet boundary and the byte boundary defined by said first and second groups of contiguous bits by evaluating the number of bits occupied by the flag in the second group of contiguous bits of said data stream.
Claim 13
Dependent Claim
16 words
The method of claim 8, wherein steps (a) and (b) are performed using a state machine.
Claim 14
Dependent Claim
14 words
The method of claim 8, wherein step (c) is performed by a state machine.
Claim 15
Dependent Claim
14 words
The method of claim 10, wherein step (c) includes the step of detecting errors.
Claim 16
Dependent Claim
15 words
The method of claim 11 including the additional step of recovering from said detected errors.
Claim 17
Dependent Claim
85 words
Apparatus for locating a data delimiting flag in a digital data stream, wherein a flag consists of a predetermined bit pattern, comprising: means for receiving a plurality of bits, including a predetermined fraction of said digital data stream; a state machine including means, coupled to said receiving means, for concurrently examining each bit in the fraction of said digital data stream to generate a partial flag indication value corresponding to a number of bits occupied by the flag in the fraction of said digital stream.
Claim 18
Dependent Claim
85 words
Apparatus for locating a data delimiting flag in a digital data stream, wherein a flag consists of a predetermined bit pattern, comprising: means for receiving a plurality of bits, including a predetermined fraction of said digital data stream; a state machine including means, coupled to said receiving means, for concurrently examining each bit in the fraction of said digital data stream to generate a partial flag indication value corresponding to a number of bits occupied by the flag in the fraction of said digital stream.
Claim 19
Dependent Claim
54 words
The apparatus set forth in claim 13, wherein said state machine further includes: means for storing said partial flag indication value; means for concurrently processing each bit in a subsequent fraction of said digital data stream and said partial flag indication value to generate a flag signal indicating that said flag has been detected.
Claim 20
Dependent Claim
32 words
The apparatus set forth in claim 14, wherein said state machine further includes means, coupled to receive said flag signal for generating signals defining boundaries for the data delimited by said flag.
References Cited (Backward Citations)
US4413337A
Cited
US4494231A
Cited
US4594708A
Cited
US4577314A
Cited
US4631718A
Cited
US4797678A
Cited
US4791639A
Cited
US4779269A
Cited
US4811339A
Cited
US4748623A
Cited
US4764919A
Cited
US4780870A
Cited
US4811367A
Cited
US4727558A
Cited
US4768192A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1993-11-26 | 1994-05-28 | 1994-11-27 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1997-11-26 | 1998-05-28 | 1998-11-27 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2001-11-26 | 2002-05-28 | 2002-11-27 | $7700.00 | Window Closed / Lapsed |