US5367544A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Data stream frame synchronisation
Assignee: Ericsson AB
•
Filing: 1993-11-04
•
Granted: 1994-11-22
•
Expires: 2013-11-04
Abstract
Abstract A data stream has frames of fixed, or variable but determined, length and includes a fixed length header at a predetermined position in the frame, which header has a linear systematic code structure including information digits and check digits. The check digits are employed for frame synchronization detection, as well as error detection and correction, using, for example, a modified CRC (cyclic redundancy check) decoder.
Inventors
- 👤 Simon D. Bruekheimer
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-29 06:02
CPC Classifications
H; H04; H04L; H04L7/00; H04L7/04; H04L7/048
Claims Analysis
Total Claims: 18
Claim 1
Independent Claim
247 words
A method of detecting frame synchronisation of a data stream, which frames are of fixed length or of a variable but determinable length indicated by a pattern or by information in the data stream, which Said frames include a fixed length header at a predetermined position in each frame, which said header has a linear systematic code structure including information symbols and check symbols, which said check symbols are derived from a polynomial representative of the information symbols of the header, which said polynomial has coefficients valid over a Galois field, by their polynomial division by a code generator polynomial whose coefficients are defined over a Galois field, and wherein the check symbols are employed for frame synchronisation detection without compromising their possible use for error detection in and correction of the header, the method of detection comprising the steps of dividing an incoming data stream by the code generator polynomial, simultaneously dividing a preceding but delayed incoming data stream by the code generator polynomial, comparing any remainder of the first mentioned division with any remainder of the second mentioned simultaneous division, the presence of identical remainders indicating that the incoming data stream is a valid code word, and determining the occurrence of a succession of said valid code word once every frame length for a predetermined number of frames, which said occurrence indicates frame synchronisation, and also including determining the frame length from the data stream if the frames are of said variable but determinable length.
Claim 2
Independent Claim
247 words
A method of detecting frame synchronisation of a data stream, which frames are of fixed length or of a variable but determinable length indicated by a pattern or by information in the data stream, which Said frames include a fixed length header at a predetermined position in each frame, which said header has a linear systematic code structure including information symbols and check symbols, which said check symbols are derived from a polynomial representative of the information symbols of the header, which said polynomial has coefficients valid over a Galois field, by their polynomial division by a code generator polynomial whose coefficients are defined over a Galois field, and wherein the check symbols are employed for frame synchronisation detection without compromising their possible use for error detection in and correction of the header, the method of detection comprising the steps of dividing an incoming data stream by the code generator polynomial, simultaneously dividing a preceding but delayed incoming data stream by the code generator polynomial, comparing any remainder of the first mentioned division with any remainder of the second mentioned simultaneous division, the presence of identical remainders indicating that the incoming data stream is a valid code word, and determining the occurrence of a succession of said valid code word once every frame length for a predetermined number of frames, which said occurrence indicates frame synchronisation, and also including determining the frame length from the data stream if the frames are of said variable but determinable length.
Claim 3
Dependent Claim
39 words
A method as claimed in claim 1 wherein each division is carried out in a respective decoder including a respective shift register and wherein the shift registers are not preset preceding all divisions, other than in the initial condition.
Claim 4
Dependent Claim
23 words
A method as claimed in claim 1 wherein the division steps are carried out in parallel by means of parallely disposed division means.
Claim 5
Dependent Claim
20 words
A method as claimed in claim 1 and wherein the incoming data stream is continuously monitored at all symbol positions.
Claim 6
Dependent Claim
51 words
A method as claimed in claim 1 and wherein the syndrome of an errored code word is obtained by modulo-Q addition (where Q represents the number of valid coefficients of the code generator polynomial) of the remainders of the first and second mentioned divisions, which syndrome is used for error correction.
Claim 7
Dependent Claim
125 words
A method as claimed in claim 1 wherein said data stream is transmitted from a transmitter to a receiver at which latter said frame synchronisation detection is performed, including a step of adding at the transmitter a non-trivial coset polynomial to the code to be transmitted, which said added polynomial results in an error in cyclically shifted code words, in an error when symbol by symbol monitoring is not at the true code word position, and in symbol slips and gains from the true code word position, and wherein a difference between said remainders, equal to a coset polynomial indicates detection of a valid code word, a succession of valid code words once every frame length for a predetermined number of frames indicating frame synchronisation.
Claim 8
Dependent Claim
19 words
A method as claimed in claim 1 wherein the header code structure is a pure or shortened cyclic code.
Claim 9
Independent Claim
243 words
An apparatus for detecting frame synchronisation of a data stream, which frames are of a fixed length or of a variable but determinable length indicated by a pattern or by information in the data stream, which said frames include a fixed length header at a predetermined position in each frame, which said header has a linear systematic code structure including information symbols and check symbols, which said check symbols were derived from a polynomial representative of the information symbols of the header, which said polynomial has coefficients valid over a Galois field, by their polynomial division by a code generator polynomial whose coefficients are defined over a Galois field, the apparatus including means which divide an incoming data stream by the code generator polynomial, means which simultaneously divide a preceding but delayed incoming data stream by the code generator polynomial, means which compare any remainder of the first mentioned division with any remainder of the second mentioned division, the presence of a predetermined relationship between the remainders corresponding to the said incoming data stream being a valid code word, and means which correlate valid code word positions and indicate frame synchronisation in response to receipt of a succession of said valid code word once every frame length for a predetermined number of frames, and also including means in response to said valid code word, which determine the frame length from the data stream if the frames are of said variable but determinable length.
Claim 10
Independent Claim
243 words
An apparatus for detecting frame synchronisation of a data stream, which frames are of a fixed length or of a variable but determinable length indicated by a pattern or by information in the data stream, which said frames include a fixed length header at a predetermined position in each frame, which said header has a linear systematic code structure including information symbols and check symbols, which said check symbols were derived from a polynomial representative of the information symbols of the header, which said polynomial has coefficients valid over a Galois field, by their polynomial division by a code generator polynomial whose coefficients are defined over a Galois field, the apparatus including means which divide an incoming data stream by the code generator polynomial, means which simultaneously divide a preceding but delayed incoming data stream by the code generator polynomial, means which compare any remainder of the first mentioned division with any remainder of the second mentioned division, the presence of a predetermined relationship between the remainders corresponding to the said incoming data stream being a valid code word, and means which correlate valid code word positions and indicate frame synchronisation in response to receipt of a succession of said valid code word once every frame length for a predetermined number of frames, and also including means in response to said valid code word, which determine the frame length from the data stream if the frames are of said variable but determinable length.
Claim 11
Dependent Claim
16 words
Apparatus as claimed in claim 8 wherein the predetermined relationship requires the remainders to be identical.
Claim 12
Dependent Claim
102 words
Apparatus as claimed in claim 8 and for use with a data stream transmitted from a transmitter to a receiver at which latter the said frame synchronisation detection is performed, and including means at the transmitter for adding a non-trivial coset polynomial to the code to be transmitted, which added polynomial results in an error in cyclically shifted code words, in an error when symbol by symbol monitoring is not at the true code word position, and in symbol slips and gains from the true code word position, and wherein the predetermined relationship requires the remainders to differ by the coset polynomial.
Claim 13
Dependent Claim
69 words
Apparatus as claimed in claim 8 and wherein the dividing means for performing the division of said incoming data stream by the code generator polynomial comprises first decoder means, and the dividing means for performing the division of the preceding but delayed incoming data stream by the code generator polynomial comprises second decoder means, delay line means being coupled between the inputs of the first and second decoder means.
Claim 14
Dependent Claim
19 words
Apparatus as claimed in claim 8 wherein the first mentioned and second mentioned division means are disposed in parallel.
Claim 15
Dependent Claim
81 words
Apparatus as claimed in claim 10 and wherein the dividing means for performing the division of said incoming data stream by the code generator polynomial comprises first decoder means, and the dividing means for performing the division of the preceding but delayed incoming data stream by the code generator polynomial comprises second decoder means, delay line means being coupled between inputs of the first and second decoder means and including means for applying the coset polynomial coefficients to the comparator means.
Claim 16
Dependent Claim
179 words
Apparatus as claimed in claim 11 wherein the first decoder means comprises a first shift register employing linear feedback by exclusive-or operations, the said incoming data stream being applied to the first shift register via an input thereof comprising the input of the first decoder means, wherein the second decoder means comprises a second shift register employing linear feedback by exclusive-or operations, the preceding but delayed incoming data stream being applied to the input of the second shift register via an input thereof comprising the input of the second decoder means, the first shift register having the same number of stages as the second shift register, wherein the output of each stage of the first shift register is applied to a respective exclusive-or element, the output of each stage of the second shift register is applied to a corresponding one of said exclusive-or elements whereby to compare said outputs, and wherein the outputs of said exclusive-or elements are applied to a multi-input logical nor element which has a non-zero output only when there is a said valid code word.
Claim 17
Dependent Claim
78 words
Apparatus as claimed in claim 14 and including a linear operator apparatus disposed between one of said first and second decoder means and the exclusive-or elements, whereby the remainder associated with the said one of said first and second decoder means is applied to the linear operator apparatus prior to comparison with the remainder associated with the other one of said first and second decoder means whereby to detect a code word of a shortened cyclic code format.
Claim 18
Dependent Claim
51 words
Apparatus as claimed in claim 14 and including means for pre-multiplying the data stream applied to one of said first and second decoder means by a further polynomial having coefficients valid over a Galois field and such as to allow detection of a code word of a shortened cyclic code format.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1997-11-21 | 1998-05-23 | 1998-11-22 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2001-11-21 | 2002-05-23 | 2002-11-22 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2005-11-21 | 2006-05-23 | 2006-11-22 | $7700.00 | Window Closed / Lapsed |