Intellectual Property Office

Non-Confidential Disclosures

“Method of Correcting Bursts of Errors”

PSU Inv. Disc. No 2007-3342

Keywords:

Burst error correction, Cyclic codes, vector symbol decoding, Reed-Solomon codes; wireless communications

Inventors:

J. Metzner

Links:

http://www.ee.psu.edu/faculty/metzner/metzner1.html
http://www.ipo.psu.edu

Background:

Cyclic codes are almost universally used for block burst error correction because of their simpler implementation with feedback shift registers. In US Patent 5,657,331 a class of cyclic codes is developed for which almost all burst patterns of length n-k-1 or less can be decoded with high probability using a feedback shift register. The class of codes to achieve this result is restricted to rate less than 1/2, which is usually a lower rate than desired, and the codes in the class do not have good Hamming distance, which makes them vulnerable to not discovering events with a small number of errors that are not bursts of length < n-k. Also shown in that patent are codes of rate > 1/2 can be devised, but these required restriction to bursts smaller than n-k-1. The codes described here, in the first variation using Reed-Solomon components, have the highest possible Hamming minimum distance and are not restricted in rate. Also, the ability extends even to bursts of length n-k, provided at least one of the symbols in the burst is correct. The second and third variations, with binary cyclic code structure, cover a far wider range of cyclic codes and data rates than in the prior patent - almost any cyclic code, and even if applied to the limited class of codes in the prior patent, allows correction of a significantly larger number of burst cases.

Invention description:

Simple methods are shown for correcting bursts of large size and bursts combined with random errors using vector symbols and primarily vector XOR and feedback shift register operations. One result is that any (n, k) cyclic code with minimum distance > 2 can correct all full vector symbol error bursts of length n-k-l or less if the error vectors are linearly independent. If the bursts are not full but contain some error-free components the capability of correcting bursts up to n-k-1 or less is code-dependent. Also, vector symbol decoding with Reed-Solomon component codes can correct, very simply, with high probability. The techniques often work when there is linear dependence. In cases where most errors are in a burst but a small number of errors are outside, the solution, given error-correcting capability, can be broken down into a simple solution for the small number of outside errors, followed by a simple subtraction to reveal all the error values in the burst part.

Advantages:

• Simple burst error correction method
  
• Covers a wide range of cyclic codes and data rates
  
• Highest possible Hamming minimum distance
  

Contact:

Bradley A. Swope
Sr. Technology Licensing Officer
Intellectual Property Office
113 Technology Center
The Pennsylvania State Univ.
University Park, PA 16802-7000
Phone: (814) 865-6279
Fax: (814) 865-3591
E-mail:bradswope@psu.edu