US4291406A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Error correction on burst channels by sequential decoding
Assignee: International Business Machines Corp
•
Filing: 1979-08-06
•
Granted: 1981-09-22
•
Expires: 1999-08-06
Abstract
Abstract A sequential decoder for error correction on burst and random noise channels using convolutionally encoded data. The decoder interacts with a deinterleaver which time demultiplexes data from a data channel from its time multiplexed form into a predetermined transformed order. The decoder includes a memory for storing a table of likelihood values which are derived from known error statistics about the data channel such as the probabilities of random errors and burst errors, burst error severity and burst duration. The decoder removes an encoded subblock of data from the deinterleaver and enters it into a replica of the convolutional encoder which calculates a syndrome bit from a combination of the presently received subblock together with a given number of previous subblocks. The syndrome bit indicates if the current assumption of the path through the convolutional tree is correct. Where there is no error in the channel, then the received sequence is a code word and the syndrome bit indicates that the correct path in the convolution tree is taken. For each received bit, and indicator bit is calculated which is a function of the difference between the current path and the received sequence. The sequential decoder employs the syndrome bit together with burst indicator bits to calculate a table address in a table of likelihood values and error pattern values. The likelihood value is used to update a total likelihood of error value and the error pattern value is used to change the received subblock of data.
Inventors
- 👤 Lalit R. Bahl
- 👤 John Cocke
- 👤 Clifton D. Cullum, Jr.
- 👤 Joachim Hagenauer
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-25 00:51
CPC Classifications
H; H04; H04L; H04L1/00; H04L1/004; H04L1/0045; H04L1/0054
Claims Analysis
Total Claims: 15
Claim 1
Independent Claim
304 words
A sequential decoder and system for determining error patterns for making error correction on burst and random noise channels using convolutionally encoded data comprising: de-interleaver means for time-demultiplexing the convolutionally encoded data from a data channel into a predetermined transformed order; a decoded data buffer for storing received data which has been decoded by said de-interleaver; a syndrome bit generator connected to the output of said de-interleaver means for calculating a syndrome bit from a combination of the presently received subblock together with a given number of previous sub-blocks received from said de-interleaver means and stored in said decoded data buffer, said syndrome bit indicating if the current assumption of the path through a convolutional tree is correct; burst tracking means, connected to the output of said de-interleaver means, for tracking burst errors and deriving burst indicator bits which indicate the presence of burst errors in a channel, said burst tracking means also being connected to said decoded data buffer which stores previously decoded received data; memory means for storing tables of error likelihood and error pattern values derived from known error statistics about the data channel, statistics of probability of random errors and burst errors, error severity within a burst, and average burst duration, said memory means being connected to and addressed by a calculating means for providing error likelihood and error pattern values to said decoded data buffer; and said calculating means connected to both said syndrome bit generator and said burst tracking means for using said syndrome bits and said burst indicator bits to calculate a table address in said tables of error likelihood and error pattern values, said table address providing a likelihood value and an error pattern which are used to update a total likelihood value and determine an error pattern which are used to change received subblock data.
Claim 2
Dependent Claim
304 words
A sequential decoder and system for determining error patterns for making error correction on burst and random noise channels using convolutionally encoded data comprising: de-interleaver means for time-demultiplexing the convolutionally encoded data from a data channel into a predetermined transformed order; a decoded data buffer for storing received data which has been decoded by said de-interleaver; a syndrome bit generator connected to the output of said de-interleaver means for calculating a syndrome bit from a combination of the presently received subblock together with a given number of previous sub-blocks received from said de-interleaver means and stored in said decoded data buffer, said syndrome bit indicating if the current assumption of the path through a convolutional tree is correct; burst tracking means, connected to the output of said de-interleaver means, for tracking burst errors and deriving burst indicator bits which indicate the presence of burst errors in a channel, said burst tracking means also being connected to said decoded data buffer which stores previously decoded received data; memory means for storing tables of error likelihood and error pattern values derived from known error statistics about the data channel, statistics of probability of random errors and burst errors, error severity within a burst, and average burst duration, said memory means being connected to and addressed by a calculating means for providing error likelihood and error pattern values to said decoded data buffer; and said calculating means connected to both said syndrome bit generator and said burst tracking means for using said syndrome bits and said burst indicator bits to calculate a table address in said tables of error likelihood and error pattern values, said table address providing a likelihood value and an error pattern which are used to update a total likelihood value and determine an error pattern which are used to change received subblock data.
Claim 3
Dependent Claim
55 words
A sequential decoder and system as recited in claim 1, wherein said means for tracking burst errors and for deriving burst error indicator bits comprises means for comparing decoded data bits stored in said decoded data buffer with received bits in the de-interleaver and deriving burst indicator bit values as a result of the comparison.
Claim 4
Dependent Claim
69 words
A sequential decoder and system as recited in claim 1, wherein said calculating means for using said syndrome bits and said burst indicator bits comprises means for selecting which table of error likelihood and error pattern values to use based on the combination of the generated syndrome bit and the derived burst indicator bits, and means for selecting a particular error pattern and likelihood value from the selected table.
Claim 5
Dependent Claim
50 words
A sequential decoder and system as recited in claim 1, wherein said memory means for storing tables of error likelihood and error pattern values includes, for a given combination of a syndrome bit and burst indicator bits, a table of error patterns organized in order of decreasing error likelihood values.
Claim 6
Dependent Claim
47 words
A sequential decoder and system as recited in claim 1, wherein said de-interleaver means includes a buffer for storing rows of received data after they are de-multiplexed, said buffer including a preamble section for storing the bits used for calculating initial values of the burst indicator bits.
Claim 7
Dependent Claim
37 words
A sequential decoder and system as recited in claim 1, wherein said de-interleaver includes storage means for a two dimensional array of bits wherein data can be written in column-by-column fashion and read out in row-by-row fashion.
Claim 8
Independent Claim
238 words
A system for determining error patterns for making error correction on burst and random noise channels using convolutional codes with sequential decoding, comprising: encoder means for encoding source data by convolutional encoding; time interleaving means for multiplexing the encoded data from its received order into a predetermined transformed order; data channel means for transmitting said time-interleaved data; de-interleaver means for time-demultiplexing data from a data channel into a predetermined transformed order; a decoded data buffer for storing received data which has been decoded by said de-interleaver, said decoded data buffer storing subblock data; decoder means for sequentially decoding the received convolutionally encoded data from said de-interleaver into the source data form; a syndrome bit generator, connected to said de-interleaver means and said decoded data buffer for calculating a syndrome bit from a combination of the presently received subblock together with a given number of previous subblocks, said syndrome bit indicating if the current assumption of the path through a convolutional tree is correct; burst tracking means, connected to the output of said de-interleaver means, for tracking burst errors and deriving burst indicator bits which indicate the presence of a burst error in a channel; and calculating means, connected to said syndrome bit generator and said burst tracking means for using said syndrome bits and said burst indicator bits to provide an error likelihood value and determine an error pattern which are used to change the received subblock data.
Claim 9
Independent Claim
238 words
A system for determining error patterns for making error correction on burst and random noise channels using convolutional codes with sequential decoding, comprising: encoder means for encoding source data by convolutional encoding; time interleaving means for multiplexing the encoded data from its received order into a predetermined transformed order; data channel means for transmitting said time-interleaved data; de-interleaver means for time-demultiplexing data from a data channel into a predetermined transformed order; a decoded data buffer for storing received data which has been decoded by said de-interleaver, said decoded data buffer storing subblock data; decoder means for sequentially decoding the received convolutionally encoded data from said de-interleaver into the source data form; a syndrome bit generator, connected to said de-interleaver means and said decoded data buffer for calculating a syndrome bit from a combination of the presently received subblock together with a given number of previous subblocks, said syndrome bit indicating if the current assumption of the path through a convolutional tree is correct; burst tracking means, connected to the output of said de-interleaver means, for tracking burst errors and deriving burst indicator bits which indicate the presence of a burst error in a channel; and calculating means, connected to said syndrome bit generator and said burst tracking means for using said syndrome bits and said burst indicator bits to provide an error likelihood value and determine an error pattern which are used to change the received subblock data.
Claim 10
Dependent Claim
73 words
A system as recited in claim 7, further comprising memory means for storing tables of error likelihood and error pattern values derived from known error statistics about the data channel, statistics of probability of random errors and burst errors, error severity within a burst, and average burst duration, said memory means being connected to and addressed by said calculating means for providing error likelihood and error pattern values to said decoded data buffer.
Claim 11
Dependent Claim
68 words
A system as recited in claim 8, wherein said calculating means for using said syndrome bits and said burst indicator bits comprises first means for selecting a table of error likelihood and error pattern values to use based on the combination of the generated syndrome bit and the derived burst indicator bits, and second means for selecting a particular error pattern and likelihood value from the selected table.
Claim 12
Dependent Claim
54 words
A system as recited in claim 7, wherein said burst tracking means for tracking burst errors and for deriving burst error indicator bits comprises means connected to said decoded data buffer for comparing decoded data bits with received bits in the de-interleaver and deriving burst indicator bit values as a result of the comparison.
Claim 13
Dependent Claim
47 words
A system as recited in claim 8, wherein said memory means for storing tables of error likelihood and error pattern values includes, for a given combination of a syndrome bit and burst indicator bits, a table of error patterns organized in order of decreasing error likelihood values.
Claim 14
Dependent Claim
44 words
A system as recited in claim 7, wherein said de-interleaver means includes a buffer for storing rows of received data after they are de-multiplexed, said buffer including a preamble section for storing the bits used for calculating initial values of the burst indicator bits.
Claim 15
Dependent Claim
34 words
A system as recited in claim 7, wherein said de-interleaver includes storage means for a two dimensional array of bits wherein data can be written in column-by-column fashion and read out in row-by-row fashion.
References Cited (Backward Citations)
US3508197A
Cited
US3585586A
Cited
US3588819A
Cited
US3571795A
Cited
US3593282A
Cited
US3891959A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1984-09-21 | 1985-03-23 | 1985-09-22 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1988-09-21 | 1989-03-23 | 1989-09-22 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 1992-09-21 | 1993-03-23 | 1993-09-22 | $7700.00 | Window Closed / Lapsed |