IP Library › Granted Patent US 7,028,245
Granted Patent B2
US 7,028,245 · App. 09/935,166 · Granted Apr 11, 2006

Even-load software Reed-Solomon decoder

View Patent ↗
Loading inventors, assignments & file history…
Monitor This Case
Get email alerts when status or documents change.
Order Certified Copies
Most orders are placed with the USPTO same day — all within 24 business hours.
Order via The Patent Place →
Pre-filled with this patent's details
Quick Facts
Patent No.
US 7,028,245
App. No.
09/935,166
Granted
Apr 11, 2006
Kind
B2
Abstract

A software implementation of a Reed-Solomon decoder placing a constant load on the processor of a computer. A Berlekamp-Massey Algorithm is used to calculate the coefficients of the error locator polynomial, a Chien Search is used to determine the roots of the error locator polynomial, and a Forney Algorithm is used to determine the magnitude of the errors in the received digital code word. Each step is divided into m small tasks where m is the number of computational blocks it takes to read in a code word and the processor can pipeline or parallel process one task from each step each time a block is read.

Claims (56)

1. A computing system for decoding a Reed-Solomon-encoded string of data, the computing system comprising a processor circuit operable to:

store a portion of a first Reed-Solomon code word, the portion being less than the entire first code word;

store a portion of a second Reed-Solomon code word, the portion being less than the entire second code word; and

while storing the portion of the second code word, decoding the portion of the first code word and no other portion of the first code word.

2. The computing system of claim 1 wherein:

storing the portions of the first and second Reed-Solomon code words comprises storing each of the portions in a respective time having a duration t; and

decoding the portion of the first code word comprises decoding the portion in the duration t.

3. A computing system for decoding a Reed-Solomon-encoded string of data, the computing system comprising a processor circuit operable to:

receive m portions of a first Reed-Solomon code word, m being greater than one;

receive m portions of a second Reed-Solomon code word after receiving the first code word;

while receiving a first portion of the second code word, decoding a first portion of the first code word and no other portion of the first code word; and

while receiving a second portion of the second code word, decoding the second portion of the first code word and no other portion of the first code word.

4. The computing system of claim 3 wherein the processor circuit is further operable to:

receiving the first and second portions of the second code word during respective first and second time periods each having a same duration; and

decode the first and second portions of the first code word during the first and second time periods respectively.

5. The computing system of claim 3 wherein the processor circuit is further operable to:

receive m portions of a third Reed-Solomon code word;

while receiving a first portion of the third code word, decoding a first portion of the second code word and no other portion of the second code word; and

while receiving a second portion of the third code word, decoding the second portion of the second code word and no other portion of the second code word.

6. The computing system of claim 3 wherein:

the first and second Reed-Solomon code words each comprise n symbols; and

n/m equals an integer that is greater than one.

7. A computing system for decoding a Reed-Solomon-encoded string of data, the computing system comprising a processor circuit operable to:

receive m portions of each of five Reed-Solomon code words during respective time periods each having a duration, each code word comprising n symbols such that n/m equals an integer that is greater than one;

while receiving a first portion of the second code word, decoding a first portion of the first code word according to a first algorithm and decoding no other portion of the first code word;

while receiving a first portion of the third code word, decoding a first portion of the second code word according to the first algorithm, decoding the first portion of the first code word according to a second algorithm, and decoding no other portions of the first and second code words;

while receiving a first portion of the fourth code word, decoding a first portion of the third code word according to the first algorithm, decoding the first portion of the second code word according to the second algorithm, decoding the first portion of the first code word according to a third algorithm, and decoding no other portions of the first, second, and third code words; and

while receiving a first portion of the fifth code word, decoding a first portion of the fourth code word according to the first algorithm, decoding the first portion of the third code word according to the second algorithm, decoding the first portion of the second code word according to the third algorithm, decoding the first portion of the first code word according to a fourth algorithm, and decoding no other portions of the first, second, third, and fourth code words.

8. A method of operating a computing system with a Reed-Solomon decoding application comprising the steps of:

receiving a portion of a first Reed-Solomon code word, the portion being less than the whole first code word;

receiving a portion of a second Reed-Solomon code word, the portion being less than the whole second code word; and

while receiving the portion of the second code word, decoding the portion of the first code word and no other portion of the first code word.

9. The method of claim 8 wherein the portion of the first Reed-Solomon code word is the same length as the portion of the second Reed-Solomon code word.

10. The method of claim 8 wherein:

receiving the portion of the second code word comprises receiving the portion of the second code word in a time T; and

decoding the portion of the first code word comprises decoding the portion of the first code word in the time T.

11. The method of claim 8 wherein:

the first and second code words each comprises m portions of equal-length.

12. A method of operating a computing system with a Reed-Solomon decoding application comprising the steps of:

receiving m portions of a first Reed-Solomon code word, m being greater than one;

receiving m portions of a second Reed-Solomon code word after receiving the first code word; and

while receiving a first portion of the second code word, decoding a first portion of the first code word and no other portion of the first code word; and

while receiving a second portion of the second code word, decoding the second portion of the first code word and no other portion of the first code word.

13. The method of claim 12 wherein:

receiving the m portions of the first and second code words comprises receiving each of the m portions during a respective period of time T; and

decoding each of the first and second portions of the first code word during the same respective periods that the first and second portions of the second code word are received.

14. The method of claim 12 wherein:

the first and second code words each comprise n equal-length symbols; and

n/m equals an integer greater than one.

15. A method of operating a computing system with a Reed-Solomon decoding application comprising the steps of:

receiving m portions of each of five Reed-Solomon code words during respective time periods each having a duration, each code word comprising n symbols such that n/m equals an integer that is greater than one;

while receiving a first portion of the second code word, decoding a first portion of the first code word according to a first algorithm and decoding no other portion of the first code word;

while receiving a first portion of the third code word, decoding a first portion of the second code word according to the first algorithm, decoding the first portion of the first code word according to a second algorithm, and decoding no other portions of the first and second code words;

while receiving a first portion of the fourth code word, decoding a first portion of the third code word according to the first algorithm, decoding the first portion of the second code word according to the second algorithm, decoding the first portion of the first code word according to a third algorithm, and decoding no other portions of the first, second, and third code words; and

while receiving a first portion of the fifth code word, decoding a first portion of the fourth code word according to the first algorithm, decoding the first portion of the third code word according to the second algorithm, decoding the first portion of the second code word according to the third algorithm, decoding the first portion of the first code word according to a fourth algorithm, and decoding no other portions of the first, second, third, and fourth code words.

16. The method of claim 15 wherein the portions of the five Reed-Solomon code words each have a same size.

Assignments (1)
MERGER Recorded Nov 12, 2015
From: MEYER BROS. TECHNOLOGY GROUP LLC
To: GULA CONSULTING LIMITED LIABILITY COMPANY
Reel/Frame 037028/0283 →