Error correction mechanism using pattern predictive error correction codes

• US 5,181,207 A
• Filed: 01/28/1991
• Issued: 01/19/1993
• Est. Priority Date: 04/14/1988
• Status: Expired due to Term

• Current Assignee: Harris Corporation (L3Harris Technologies, Inc.)
• Original Assignee: Harris Corporation (L3Harris Technologies, Inc.)
• Inventors: Chapman, Daniel H.
• Primary Examiner(s): Baker, Stephen M.
• Application Number:
  US07/646,862
• Time in Patent Office: 722 Days
• Field of Search: 371/37.1, 371/37.4, 371/39.1
• US Class Current: 714/755
• CPC Class Codes: H03M 13/29 combining two or more codes or code structures, e.g. product codes, generalised product codes, concatenated codes, inner and outer codes
• CPC Class Codes: H03M 13/39 Sequence estimation, i.e. using statistical methods for the reconstruction of the original codes

Abstract

A mechanism for correcting errors in a stream of digital data that are encoded at a transmitter site, transmitted over a communication channel to a receiver site and decoded at the receiver site to recover the digital data pre-encodes the data using a parity-encoder. The location of the errors is determined through a comparison operation on which the receiver is able to generate a `template` of the pattern of errors in the received digital data stream. This error pattern template is then used in an iterative pattern predictive error correction process to identify the location of burst errors contained in the recovered data and to controllably modify the output of the receiver'"'"'s host decoder so as to remove the located errors from the originally decoded data.

Claims

1. A method of correcting errors in information signals that are encoded at a transmitter site, transmitted over a communication channel to a receiver site and decoded at said receiver site to recover the original information signals comprising the steps of:

at said transmitter site,

(a) processing said original information signals to obtain first signals representative of characteristics of said information signals;

(b) combining said original information signals and said first signals and encoding the combined signals; and

(c) transmitting the encoded combined signals over said communication channel to said receiver site; and

at said receiver site,

(d) receiving and demodulating the encoded combined signals that have been transmitted over said communication channel and producing demodulated signals representative of the encoded combined signals and soft decision signals representative of the level of confidence as to how accurately said demodulated signals represent the encoded combined signals;

(e) subjecting the demodulated and soft decision signals produced in step (d) to a decoding mechanism to derive output signals representative of the original information signals combined with said first signals;

(f) processing said derived output signals, in accordance with the signal processing mechanism through which the original information signals were processed in step (a) and in accordance with the soft decision signals processed in step (d) to obtain said first signals, and generating therefrom an error pattern template corresponding to the pattern of errors in said output signals;

(g) processing said derived output signals in accordance with said error pattern template and said decoding mechanism, so as to identify where, within said derived output signals, errors are located;

(h) modifying selected ones of said derived output signals in that portion thereof identified in step (g) in accordance with said error pattern template derived in step (f); and

wherein

step (f) comprises the steps of

(f1) processing said derived output signals in accordance with the signal processing mechanism used in step (a) to obtain said first signals; and

(f2) comparing contents of the signals processed by step (f1) with contents of said received signals and generating therefrom said error pattern template; and

wherein

step (g) comprises the steps of

(g1) encoding said derived output signals in accordance with the encoding mechanism employed in step (b) to obtain re-encoded output signals;

(g2) comparing the value of the re-encoded output signals obtained in step (g1) with the value of the encoded combined signals received and demodulated in step (d), and producing therefrom second signals representative of differences therebetween;

(g3) combining respective pluralities of said second signals to obtain respective pluralities of third signals;

(g4) selectively modifying the contents of a respective plurality of said derived output signals in accordance with said error pattern template, so as to obtain fourth signals representative of a modified version of said derived output signals;

(g5) encoding said fourth signals in accordance with the encoding mechanism employed in step (b) so as to obtain an encoded modified version of said derived output signals;

(g6) comparing the value of the encoded fourth signals obtained in step (g5) with the value of the encoded combined signals obtained in step (d), and producing therefrom fifth signals representative of differences therebetween;

(g7) combining a respective plurality of said fifth signals to obtain a respective sixth signal;

(g8) repeating steps (g4)-(g7) for successive pluralities of said derived output signals, thereby obtaining a plurality of said sixth signals;

(g9) generating eighth signals representative of differences between respective ones of said third and sixth signals; and

(g10) locating the beginning of the occurrence of errors in said derived output signals in accordance with prescribed characteristics of said seventh signals.

2. A method according to claim 1, wherein step (h) comprises modifying selected ones of said derived output signals in accordance with said error pattern template beginning with the occurrence of errors located in step (g11) and extending over the pattern of said error pattern template.

3. A method of correcting errors in a stream of digital data that are encoded at a transmitter site, transmitted over a communication channel to a receiver site and decoded at said receiver site to recover the digital data comprising the steps of:

at said transmitter site,

(a) processing respective blocks of the original digital data to obtain respective sets of overhead bits associated with said respective blocks and being representative of prescribed characteristics of said digital data;

(b) combining respective ones of said blocks of digital data with respective ones of said sets of overhead bits to produce a digital bit stream and encoding the digital bit stream; and

(c) transmitting the encoded digital bit stream over said communication channel to said receiver site; and

at said receiver site,

(d) receiving and demodulating the encoded digital bit stream that has been transmitted over said communication channel and producing a demodulated digital bit stream representative of the encoded digital bit stream and soft decision bits representative of the level of confidence as to how accurately said demodulated digital bit stream represents the encoded digital bit stream;

(e) subjecting the demodulated digital bit stream and soft decision bits to a decoding mechanism to derive output data representative of the blocks of original digital data combined with said sets of overhead bits;

(f) processing said combined output digital data, in accordance with the signal processing mechanism through which the original digital data were processed in step (a) and in accordance with the soft decision bits produced in step (d) to obtain respective blocks of output digital data and associated sets of overhead bits, and generating therefrom respective error pattern template codes corresponding to the patterns of errors in said respective blocks of output digital data;

(g) processing said respective blocks of output digital data in accordance with said error pattern template codes and said decoding mechanism, so as to identify where, within said blocks of output digital data, errors are located; and

(h) modifying selected bits of a respective block of output digital data in that portion thereof identified in step (g) in accordance with its associated error pattern template code derived in step (f); and

wherein

step (f) comprises the steps of

(f1) processing said blocks of output digital data in accordance with the signal processing mechanism used in step (a) so as to obtain respective sets of output overhead bits associated therewith; and

(f2) comparing the respective sets of overhead bits contained in the combined output digital data with the respective sets of output overhead bits obtained in step (f1) and generating therefrom said error pattern template codes; and

wherein

step (g) includes

(g1) encoding said blocks of output digital data in accordance with the encoding mechanism employed in step (b) so as to obtain reencoded blocks of digital data and second codes representative of the confidence in the reencoded bit values thereof;

(g2) generating third codes representative of the Hamming distances between the reencoded blocks of digital data and the blocks of output digital data;

(g3) generating a first metric representative of a measure of proximation of the reencoded output data to the received data by summing respective pluralities of said third codes to obtain respective pluralities of fourth codes;

(g4) for each respective block of digital output data, selectively modifying the bit values of a respective portion thereof in accordance with its associated error pattern template code, so as to obtain a modified version of that respective block of output digital data;

(g5) encoding said modified version of a respective block of output digital data in accordance with the encoding mechanism employed in step (b), so as to obtain an encoded modified version of said respective block of output digital data;

(g6) generating fifth codes representative of the Hamming distances between the encoded modified version of said respective block of output digital data and its associated original output block of digital data;

(g7) generating a second metric representative of a measure of proximation of the encoded modified version of the respective block of output digital data to its associated original output block of digital data by summing respective pluralities of said fifth codes to obtain respective pluralities of sixth codes;

(g8) repeating steps (g4)-(g7) for successive portions of a respective block of output digital data, thereby obtaining a plurality of said sixth codes;

(g9) generating seventh codes representative of the differences between respective ones of said fourth and sixth codes;

(g10) generating a third metric by processing said seventh codes to obtain eighth codes; and

(g11) locating the beginning of the occurrence of errors, in a respective block of said output digital data, at the bit position thereof, the corresponding eighth code for which has a prescribed value relative to the remaining ones of said eighth codes.

4. A method according to claim 3, wherein step (h) comprises modifying selected blocks of said output digital data in accordance with said error pattern template codes beginning with the occurrences of errors located in step (g11) and extending over the spans of the respective error pattern codes.

5. A method according to claim 3, wherein said overhead bits comprise parity bits.

6. A system for correcting errors in information signals that are encoded at a transmitter site, transmitted over a communication channel to a receiver site and decoded at said receiver site to recover the original information signals comprising:

at said transmitter site,

first means for processing said original information signals to obtain first signals representative of characteristics of said information signals;

second means for combining said original information signals and said first signals and encoding the combined signals; and

third means for transmitting the encoded combined signals over said communication channel to said receiver site; and

at said receiver site,

fourth means for receiving and demodulating the encoded combined signals that have been transmitted over said communication channel and producing demodulated signals representative of the encoded combined signals and soft decision signals representative of the level of confidence as to how accurately said demodulated signals represent the encoded combined signals; and

fifth means for subjecting the demodulated and soft decision signals produced by said fourth means to a decoding mechanism to derive output signals representative of the original information signals combined with said first signals; and

sixth means for processing said derived output signals, in accordance with the signal processing mechanism through which the original information signals were processed by said first means to obtain said first signals, and in accordance with the soft decision signals produced by said fourth means and generating therefrom an error pattern template corresponding to the pattern of errors in said output signals, processing said derived output signals in accordance with said error pattern template and said decoding mechanism, so as to identify where, within said derived output signals, errors are located, and modifying selected ones of said derived output signals in that portion thereof identified in accordance with said error pattern template; and

wherein

said sixth means comprises

means for processing said derived output signals in accordance with the signal processing mechanism used by said first means to obtain said first signals; and

means for comparing contents of the signals processed by said derived output signals processing means with contents of said received signals and generating therefrom said error pattern template; and

wherein

said sixth means comprises

means for encoding said derived output signals in accordance with the encoding mechanism employed by said second means to obtain re-encoded output signals;

means for encoding said derived output signals in accordance with the encoding mechanism employed by said second means to obtain re-encoded output signals;

means for comparing the accuracy of the re-encoded output signals with the accuracy of the encoded combined signals received and demodulated by said fourth means and producing therefrom second signals representative of differences therebetween;

means for combining respective pluralities of said second signals to obtain respective pluralities of third signals;

means for selectively modifying the contents of a respective plurality of said derived output signals in accordance with the error pattern of said error pattern template, so as to obtain fourth signals representative of a modified version of said derived output signals;

means for encoding said fourth signals in accordance with the encoding mechanism employed by said second means, so as to obtain an encoded modified version of said derived output signals;

means for comparing the accuracy of the encoded fourth signals with the accuracy of the encoded combined signals obtained by said fourth means, and producing therefrom fifth signals representative of differences therebetween;

means for combining a respective plurality of said fifth signals to obtain a respective sixth signal;

means for causing the operation of said fourth signal through sixth signal obtaining means to be repeated for successive pluralities of said derived output signals, thereby obtaining a plurality of said sixth signals;

means for generating seventh signals representative of differences between respective ones of said third and sixth signals;

means for processing seventh signals to obtain eighth signals; and

means for locating the beginning of the occurrence of errors, in said derived output signals, at that derived output signal, the corresponding eighth signal for which has a prescribed value relative to the remaining ones of said eighth signals.

7. A system according to claim 6, wherein said first signals comprise overhead bits.

8. A system according to claim 6, wherein said sixth means further includes means for modifying selected ones of said derived output signals in accordance with said error pattern template beginning with the occurrence of located errors and extending over the error pattern template.

9. For use in a communication system in which a stream of digital data is encoded at a transmitter site, transmitted over a communication channel to a receiver site and decoded at said receiver site to recover the digital data, and wherein, at the transmitter site, respective blocks of the original digital data are processed to obtain respective sets of overhead bits associated with said respective blocks and being representative of prescribed characteristics of the digital data, and respective ones of said blocks of digital data are combined with respective ones of said sets of overhead bits to produce a digital bit stream which is then encoded and transmitted over said communication channel to said receiver site whereat the transmitted encoded digital bit stream is received and demodulated to produce a demodulated digital bit stream representative of the encoded digital bit stream and soft decision bits representative of the level of confidence as to how accurately said demodulated digital bit stream represents the encoded digital bit stream, the demodulated digital bit stream and the soft decision bits being subjected to a decoding mechanism to derive output data representative of the blocks of original digital data combined with said sets of overhead bits, an apparatus for detecting and correcting errors in the decoded data comprising:

first means for processing said combined output digital data in accordance with the signal processing mechanism through which the original digital data were processed at the transmitter site to obtain respective blocks of output digital data and associated sets of overhead bits and in accordance with said soft decision bits, and generating therefrom respective error template pattern codes corresponding to the patterns of errors in said respective blocks of output digital data;

second means, coupled with said first means, for processing said respective blocks of output digital data in accordance with said error pattern template codes and said decoding mechanism, so as to identify where, within said blocks of output digital data, errors are located; and

third means, coupled to said first and second means, for modifying selected bits of a respective block of output digital data in that portion thereof identified by said second means in accordance with its associated error pattern template code derived by said first means; and

wherein said second means comprises;

means for processing said blocks of output digital data in accordance with the signal processing mechanism used at said transmitter site to obtain respective sets of output overhead bits associated therewith; and

means for comparing the respective sets of overhead bits contained in the combined output digital data with the respective sets of output overhead bits and generating therefrom said error pattern codes; and

wherein

said soft decision bits are in the form of first codes representative of the confidence of the digital bit values of the received encoded digital bit stream are generated at said receiver site, and said second means comprises;

means for encoding said blocks of output digital data in accordance with the encoding mechanism employed at said transmitter site to obtain reencoded blocks of digital data and second codes representative of the confidence in the reencoded bit values thereof;

means for generating third codes representative of the Hamming distances between the reencoded blocks of digital data and the blocks of output digital data;

means for generating a first metric representative of a measure of closeness of the re-encoded output data to the received data by summing respective pluralities of said third codes to obtain respective pluralities of fourth codes;

means for selectively modifying the bit values of a respective portion of each respective block of digital output data in accordance with its associated error pattern template code, so as to obtain a modified version of that respective block of output digital data;

means for encoding said modified version of a respective block of output digital data in accordance with the encoding mechanism employed at said transmitter site, so as to obtain an encoded modified version of said respective block of output digital data;

means for generating fifth codes representative of the Hamming distances between the encoded modified version of said respective block of output digital data and its associated original output block of digital data;

means for generating a second metric representative of a measure of the closeness of the encoded modified version of the respective block of output digital data to its associated original output block of digital data by summing respective pluralities of said fifth codes to obtain respective pluralities of sixth codes;

means for causing said fourth code through sixth code obtaining means to repeat their operations for successive portions of a respective block of output digital data, thereby obtaining a plurality of said sixth codes;

means for generating seventh codes representative of the differences between respective ones of said fourth and sixth codes;

means for generating a third metric by processing seventh codes to obtain eighth codes; and

means for locating the beginning of the occurrence of errors, in a respective block of said output digital data, at the bit position thereof, the corresponding eighth code for which has a prescribed value relative to the remaining ones of said eighth codes.

10. An apparatus according to claim 9, wherein said third means comprises means for modifying selected blocks of said output digital data in accordance with said error pattern codes beginning with the occurrences of located errors and extending over the spans of the respective error pattern template codes.

11. An apparatus according to claim 9, wherein said overhead bits comprise parity bits.