# US 5,703,887 A · Synchronization and error detection in a packetized data stream

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 5,703,887 A
- Document ID: US5703887A
- Status: Granted
- Kind: A
- Application number: 08/363,252
- Filed: 1994-12-23
- Granted: 1997-12-30
- Earliest claimed: 1994-12-23
- Assignees: General Instrument Corporation of Delaware
- Inventors: Chris Heegard; Andrew J. King; Sydney Lovely; Thomas J. Kolze
- Web page: https://patentgrep.com/patent/US5703887A

## CPC

- H04N 21/4382: {Demodulation or channel decoding, e.g. QPSK demodulation (analog front ends or means for connecting modulators, demodulators or transceivers to a transmission line H04L27/0002)}
- H03M 13/33: Synchronisation based on error coding or decoding
- H04L 1/0057: {Block codes (H04L1/0061, H04L1/0064 take precedence)}
- H04L 7/048: {using the properties of error detecting or error correcting codes, e.g. parity as synchronisation signal}
- H04N 19/00: Methods or arrangements for coding, decoding, compressing or decompressing digital video signals
- H04N 19/61: in combination with predictive coding
- H04N 19/89: involving methods or arrangements for detection of transmission errors at the decoder
- H04N 19/70: characterised by syntax aspects related to video coding, e.g. related to compression standards
- H04N: PICTORIAL COMMUNICATION, e.g. TELEVISION
- H03M: CODING; DECODING; CODE CONVERSION IN GENERAL (using fluidic means F15C4/00; optical analogue/digital converters G02F7/00; coding, decoding or code conversion, specially adapted for particular applications, see the relevant subclasses, e.g. G01D, G01R, G06F, G06T, G09G, G10L, G11B, G11C, H04B, H04L, H04M, H04N; ciphering or deciphering for cryptography or other purposes involving the need for secrecy G09C)
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)

## Abstract

A method and apparatus are provided for achieving synchronization and detecting errors in a data stream such as an MPEG-2 transport packet stream. In an MPEG embodiment, the MPEG sync word is removed and replaced with a parity code that is used at the decoder for both synchronization and error detection. A syndrome calculator in the decoder can be implemented using a unique one bit in, one bit out FIR filter. Codewords used to generate the parity code can be provided by a linear block code that is a dual of a shortened cyclic code.

## Claims

### Claim 1

A method for achieving synchronization and detecting errors in a data stream carrying successive packets of k information bits and r synchronization bits, the synchronization bits of each packet comprising a predefined searchable pattern, comprising the steps of:
locating at least one synchronization pattern in said data stream to enable the boundaries for the k information bits of successive packets to be determined;
replacing the synchronization pattern in each packet with an r-bit parity code derived from a counterpart set of k information bits in said data stream, thereby generating a modified data stream;
communicating said modified data stream to a decoder;
locating at least one of said parity codes in said modified data stream at said decoder to achieve synchronization, thereby enabling the boundaries for the k information bits of successive packets to be determined; and
comparing said parity codes to checksums obtained from their counterpart k information bits at said decoder to determine when the information bits in a packet contain an error.

### Claim 2 (depends on 1)

A method in accordance with claim 1 wherein:
the synchronization pattern for each packet precedes the k information bits of that packet; and
the counterpart set of k information bits for each parity code comprises the k information bits immediately preceding the parity code.

### Claim 3 (depends on 1)

A method in accordance with claim 1 wherein said parity code is generated from a linear block code comprising a dual of a shortened cyclic code.

### Claim 4 (depends on 1)

A method in accordance with claim 1 wherein said data stream is an MPEG compatible data stream.

### Claim 5 (depends on 4)

A method in accordance with claim 4 comprising the further step of scaling said parity codes such that when decoded at said decoder, they will match MPEG synchronization patterns.

### Claim 6 (depends on 4)

A method in accordance with claim 4 wherein k=1496.

### Claim 7

Communication apparatus for enabling a receiver to robustly obtain synchronization and detect errors in a data stream carrying successive packets of k information bits and an r-bit parity code, the parity code of each packet comprising a predefined pattern of bits detectable at said receiver by searching for said pattern and functioning as a checksum for information bits carried in said data stream, said apparatus comprising:
means for inserting the parity codes in said packets prior to communication to said receiver, each of said parity codes being derived from a counterpart set of k information bits in said data stream;
means for communicating said data stream to said receiver after insertion of said parity codes;
means for locating at least one parity code in said data stream at said receiver to achieve synchronization, thereby enabling the boundaries for the k information bits of successive packets to be determined; and
means at said receiver for comparing said parity codes to checksums obtained from their counterpart k information bits to determine when the information bits in a packet contain an error.

### Claim 8 (depends on 7)

Apparatus in accordance with claim 7 further comprising:
a parity check matrix at said receiver for generating a predefined synchronization pattern from valid parity codes.

### Claim 9 (depends on 8)

Apparatus in accordance with claim 8 wherein said predefined synchronization pattern is a standard MPEG synchronization pattern.

### Claim 10 (depends on 7)

Apparatus in accordance with claim 7 wherein said data stream contains synchronization patterns prior to insertion of said parity codes, said apparatus further comprising:
means for replacing said synchronization patterns with said parity codes to provide a modified data stream for communication to said receiver.

### Claim 11 (depends on 10)

Apparatus in accordance with claim 10, further comprising:
means at said receiver for reconstructing said data stream from said modified data stream by replacing said parity codes with said synchronization patterns.

### Claim 12 (depends on 10)

Apparatus in accordance with claim 10 wherein:
each packet commences with one of said synchronization patterns, with the k information bits for the packet following the synchronization pattern for that packet; and
each synchronization pattern is replaced with a parity code derived from the k information bits of the preceding packet.

### Claim 13 (depends on 12)

Apparatus in accordance with claim 12 wherein said data stream is an MPEG compatible data stream.

### Claim 14 (depends on 13)

Apparatus in accordance with claim 13 further comprising:
means for scaling said parity codes such that when decoded at said receiver, they will match an MPEG synchronization pattern.

### Claim 15

A decoder for a packetized digital data stream in which successive packets each contain k information bits and an r-bit parity code, the parity code of each packet being derived from k bits of information carried by said data stream, comprising:
means for searching said data stream during a signal acquisition phase to locate a parity code contained therein;
means for establishing a synchronization condition based on one or more parity codes located by said searching means;
means for comparing a checksum derived from the k information bits of each packet to the parity code for those k information bits during a tracking phase; and
means for signalling an error in the k information bits for a packet when the checksum for those bits does not match the parity code therefor.

### Claim 16 (depends on 15)

A decoder in accordance with claim 15 wherein:
each parity code is derived from the k information bits of the immediately preceding packet.

### Claim 17 (depends on 15)

A decoder in accordance with claim 15 wherein said parity codes are generated from a linear block code comprising a dual of a shortened cyclic code.

### Claim 18 (depends on 15)

A decoder in accordance with claim 15 wherein said data stream is encoded in an MPEG compatible format, said decoder further comprising:
means for replacing the parity code in each packet with an MPEG synchronization pattern.

### Claim 19 (depends on 15)

A decoder in accordance with claim 15 further comprising:
means for monitoring said parity codes during said tracking phase; and
means responsive to said monitoring means for switching from said tracking phase to said acquisition phase after a predetermined plurality of r-bit patterns considered by said monitoring means to be parity codes are found to be invalid.

### Claim 20 (depends on 19)

A decoder in accordance with claim 19 wherein said data stream is encoded in an MPEG compatible format, said decoder further comprising:
means for replacing the parity code in each packet with an MPEG synchronization pattern.

### Claim 21 (depends on 20)

A decoder in accordance with claim 20 wherein:
each parity code is derived from the k information bits of the immediately preceding packet; and
each synchronization pattern comprises the first r bits in a packet and is followed by the k information bits for that packet.

### Claim 22

Apparatus for calculating syndromes for linear block coded codewords, comprising:
a finite impulse response filter having an input for receiving a serial bit stream of codeword data, each codeword containing k information bits and r parity bits, said filter having an output for providing a serial bit stream of syndromes, said syndromes comprising a fixed linear combination of a current bit of said codeword data input to said filter and the k previous bits of said codeword data;
wherein said filter has an impulse response h.sup.k+1 (x), where: ##EQU18## g(x) is a generator polynomial of degree r describing a recursion to provide an infinite impulse response, and
a(x) and b(x) are polynomials chosen such that the polynomial h.sup.k+1 (x) will be of degree k, have a non-zero constant term h.sub.0 =1, and have a non-zero final term h.sub.k =1 to provide finite impulse responses.

### Claim 23 (depends on 22)

Apparatus in accordance with claim 22 wherein said linear block code is a dual of a shortened cyclic code.

### Claim 24 (depends on 22)

Apparatus in accordance with claim 22 further comprising:
means coupled to the output of said filter for detecting a synchronization pattern in the serial bit stream of syndromes.