US3775746A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for detecting odd numbers of errors and burst errors of less than a predetermined length in scrambled digital sequences
Assignee: International Business Machines Corp
•
Filing: 1972-05-19
•
Granted: 1973-11-27
•
Expires: 1992-05-19
Abstract
Abstract If digital data sequences of length n bits are successively encoded for protection against error by appending to each block of n bits in a sequence of r check bits, the r check bits being calculated from the n bits of the block by iteratively dividing the data stream, by a generator polynomial g(x) prior to each transmission and then by iteratively dividing the data sequence and remainder by a scrambler polynomial S(x), then the apparent error E(x) at the receiver due to channel error e(x), after descrambling (multiplying) by polynomial S(x), is represented by the relation E(x) S(x) e(x). When scrambling polynomial S(x) is of the form S(x) 1 + x, then each channel error is replaced by two adjacent errors, hence E(x) (1 x) e(x). All single and odd errors are nevertheless detectable in such circumstances by modifying g(x) such that g(x) (1 + x)m 1 t(x). Furthermore, burst type channel error of length > OR = b is detectable, in addition to all single and odd errors, if the scrambler polynomial S(x) assumes the form S(x) (1 + x)m f(x) and the generator polynomial is modified so that g(x) (1 + x)m 1 t(x) where f(x) and t(x) are polynomials having an odd number of terms and relatively prime and t(x) is of degree > OR = b.
Inventors
- 👤 P Boudreau
- 👤 R Chien
- 👤 C Peck
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-26 12:54
CPC Classifications
H; H03; H03M; H03M13/00; H03M13/03; H03M13/05; H03M13/09; H03M13/13; H03M13/17
Claims Analysis
Total Claims: 15
Claim 1
Independent Claim
147 words
A method for detecting odd numbers of errors and burst errors of length < OR = b bits in scrambled digital data sequences comprising the steps of: encoding each n-r bit digital block of data sequence prior to transmission by appending to the data sequence a remainder obtained from the successive division of the data sequence by a coding polynomial g(x) (1 + x)m 1 t(x); and then iteratively dividing the data sequence and remainder by scrambling polynomial S(x) (1 + x)m f(x), where t(x) and f(x) are polynomials each being relatively prime and containing an odd number of terms, and where t(x) is of degree > OR = b; decoding each received data sequence by the successive iteratively multiplication of the received sequence by the polynomial S(x); and detecting error from the presence of a predetermined bit pattern obtained by dividing the received sequence by g(x).
Claim 2
Independent Claim
147 words
A method for detecting odd numbers of errors and burst errors of length < OR = b bits in scrambled digital data sequences comprising the steps of: encoding each n-r bit digital block of data sequence prior to transmission by appending to the data sequence a remainder obtained from the successive division of the data sequence by a coding polynomial g(x) (1 + x)m 1 t(x); and then iteratively dividing the data sequence and remainder by scrambling polynomial S(x) (1 + x)m f(x), where t(x) and f(x) are polynomials each being relatively prime and containing an odd number of terms, and where t(x) is of degree > OR = b; decoding each received data sequence by the successive iteratively multiplication of the received sequence by the polynomial S(x); and detecting error from the presence of a predetermined bit pattern obtained by dividing the received sequence by g(x).
Claim 3
Dependent Claim
75 words
A method according to claim 1, wherein each block of data sequence is transmitted as a data sequence of n-r bits and remainder of r bits with the remainder being formed as the data bits are transmitted, the remainder being transmitted afterwards; and further wherein the last r bit positions constituting the remainder also constitute a preselected portion of the decoded and iteratively multiplied data sequence wherein the predetermined bit pattern is to be found.
Claim 4
Independent Claim
121 words
A method for detecting odd numbers of errors in scrambled digital data sequences comprising the steps of: encoding each n bit digital block of data sequence prior to transmission by appending to the data sequence a remainder formed from the successive iteratively division of the data sequence by a coding polynomial g(x) (1 + x)m t(x) and then iteratively dividing the data sequence and remainder by the scrambling polynomial S(x) 1 + x, where t(x) is any polynomial having an odd number of terms; decoding each received data sequence by the successive iteratively multiplication of the received sequence by the polynomial S(x); and detecting error from the presence of a predetermined bit pattern obtained by dividing the received sequence by g(x).
Claim 5
Independent Claim
121 words
A method for detecting odd numbers of errors in scrambled digital data sequences comprising the steps of: encoding each n bit digital block of data sequence prior to transmission by appending to the data sequence a remainder formed from the successive iteratively division of the data sequence by a coding polynomial g(x) (1 + x)m t(x) and then iteratively dividing the data sequence and remainder by the scrambling polynomial S(x) 1 + x, where t(x) is any polynomial having an odd number of terms; decoding each received data sequence by the successive iteratively multiplication of the received sequence by the polynomial S(x); and detecting error from the presence of a predetermined bit pattern obtained by dividing the received sequence by g(x).
Claim 6
Independent Claim
142 words
A method for detecting burst errors of length < or = b bits in scrambled digital data sequences comprising the steps of: encoding each k bit digital block of data sequence prior to transmission by appending to the data sequence a remainder formed from the successive division of the data sequence by a coding polynomial g(x) (1 + x)m t(x) and then iteratively dividing the data sequence and remainder by scrambling polynomial S(x) (1 + x)m f(x); where t(x) and f(x) are polynomials each being relatively prime and containing an odd number of terms, and where t(x) is of degree > or = b; decoding each received data sequence by the successive iterative multiplication of the received sequence by the polynomial S(x); and detecting error from the presence Of a predetermined bit pattern obtained by iteratively multiplying the received sequence by g(x).
Claim 7
Independent Claim
142 words
A method for detecting burst errors of length < or = b bits in scrambled digital data sequences comprising the steps of: encoding each k bit digital block of data sequence prior to transmission by appending to the data sequence a remainder formed from the successive division of the data sequence by a coding polynomial g(x) (1 + x)m t(x) and then iteratively dividing the data sequence and remainder by scrambling polynomial S(x) (1 + x)m f(x); where t(x) and f(x) are polynomials each being relatively prime and containing an odd number of terms, and where t(x) is of degree > or = b; decoding each received data sequence by the successive iterative multiplication of the received sequence by the polynomial S(x); and detecting error from the presence Of a predetermined bit pattern obtained by iteratively multiplying the received sequence by g(x).
Claim 8
Dependent Claim
38 words
A method according to claim 1, wherein the coding polynomial assumes the form g(x) (1 + x)3 (1 + x + x4) and the scrambling polynomial assumes the form S(x) (1 + x)2 (1 + x + x3).
Claim 9
Dependent Claim
196 words
In a digital data transmission system comprising a digital data source; a transmitter for applying suitably modulated digital data sequences from the source to a communications medium; and a receiver coupled to the medium for converting the modulated sequences back into the original sequences; the improvement comprises: in the transmitter: means for appending to each k bit digital block of data sequence, prior to transmission a remainder formed by dividing the data sequence by an encoding polynomial of the form g(x) (1 + x)m 1 t(x); and means for iteratively dividing the data sequence and remainder by a scrambling polynomial of the form S(x) (1 + x)m f(x); where t(x) and f(x) are polynomials each being relatively prime and containing an odd number of terms; and where t(x) is of degree > or = b; in the receiver: means for decoding each received data sequence by successively iteratively multiplying each sequence by the scrambling polynomial S(x); and means for detecting the occurrence of either an odd number of errors or a burst error of duration < or = b bits from the presence of a predetermined bit pattern obtained by dividing the received sequence by g(x).
Claim 10
Dependent Claim
196 words
In a digital data transmission system comprising a digital data source; a transmitter for applying suitably modulated digital data sequences from the source to a communications medium; and a receiver coupled to the medium for converting the modulated sequences back into the original sequences; the improvement comprises: in the transmitter: means for appending to each k bit digital block of data sequence, prior to transmission a remainder formed by dividing the data sequence by an encoding polynomial of the form g(x) (1 + x)m 1 t(x); and means for iteratively dividing the data sequence and remainder by a scrambling polynomial of the form S(x) (1 + x)m f(x); where t(x) and f(x) are polynomials each being relatively prime and containing an odd number of terms; and where t(x) is of degree > or = b; in the receiver: means for decoding each received data sequence by successively iteratively multiplying each sequence by the scrambling polynomial S(x); and means for detecting the occurrence of either an odd number of errors or a burst error of duration < or = b bits from the presence of a predetermined bit pattern obtained by dividing the received sequence by g(x).
Claim 11
Dependent Claim
50 words
In a digital transmission system according to claim 6; wherein in the transmitter and in the receiver the coding polynomial is of the form g(x) (1 + x)3 (1 + x + x4) and the scrambling polynomial is of the form S(x) (1 + x)2 (1 + x + x3).
Claim 12
Dependent Claim
150 words
In a digital data transmission system comprising a digital data source; a transmitter for applying suitably modulated digital data sequences from the source to a communications medium; and a receiver coupled to the medium for converting the modulated sequences back into the original sequences; wherein the improvement comprises: in the transmitter: means for appending to each n bit digital block of data sequence, prior to transmission, a remainder formed by dividing the data sequence by the encoding polynomial g(x) (1 + x)m t(x); and means for iteratively dividing the data sequence and the remainder by the scrambling polynomial S(x) 1 + x; in the receiver: means for decoding each received data sequence by iteratively multiplying each sequence by the scrambling polynomial S(x); and means for detecting the occurrence of an odd number of errors by the presence of a predetermined bit pattern obtained by dividing the received sequence by g(x).
Claim 13
Dependent Claim
150 words
In a digital data transmission system comprising a digital data source; a transmitter for applying suitably modulated digital data sequences from the source to a communications medium; and a receiver coupled to the medium for converting the modulated sequences back into the original sequences; wherein the improvement comprises: in the transmitter: means for appending to each n bit digital block of data sequence, prior to transmission, a remainder formed by dividing the data sequence by the encoding polynomial g(x) (1 + x)m t(x); and means for iteratively dividing the data sequence and the remainder by the scrambling polynomial S(x) 1 + x; in the receiver: means for decoding each received data sequence by iteratively multiplying each sequence by the scrambling polynomial S(x); and means for detecting the occurrence of an odd number of errors by the presence of a predetermined bit pattern obtained by dividing the received sequence by g(x).
Claim 14
Dependent Claim
32 words
In a digital transmission system according to claim 8, the means for detecting errors include means for testing whether the last m bits of each decoded sequence are of binary zero value.
Claim 15
Dependent Claim
35 words
In a digital transmission system according to claim 7, wherein upon the encoding polynomial assuming the form g(x) (1 + x)m t(x) then only bursts errors of length < or = b bits become detectable.
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) | 1976-11-26 | 1977-05-28 | 1977-11-27 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1980-11-26 | 1981-05-28 | 1981-11-27 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 1984-11-26 | 1985-05-28 | 1985-11-27 | $7700.00 | Window Closed / Lapsed |