Error-correction with limited working storage

• US 6,732,325 B1
• Filed: 11/08/2000
• Issued: 05/04/2004
• Est. Priority Date: 11/08/2000
• Status: Expired due to Term

• Current Assignee: ARRIS Enterprises LLC (CommScope Holding Company, Inc.)
• Original Assignee: Digeo Incorporated (CommScope Holding Company, Inc.)
• Inventors: Tash, Jonathan K., Furman, Scott F.
• Primary Examiner(s): DILDINE JR, R STEPHEN
• Application Number:
  US09/709,005
• Time in Patent Office: 1,273 Days
• Field of Search: 714/784, 714/785, 714/793
• US Class Current: 714/785
• CPC Class Codes: H03M 13/15 Cyclic codes, i.e. cyclic shifts of codewords produce other codewords, e.g. codes defined by a generator polynomial, Bose-Chaudhuri-Hocquenghem [BCH] codes H03M13/17 takes precedence

Abstract

A method and apparatus for encoding and decoding linear block codes while using limited working storage is disclosed. For decoding, the error syndromes are calculated incrementally as each encoded symbol is received. That is, as each symbol, r_i of the code word is received, the received symbol, r_i is multiplied by the entries in the “ith” column of a decoding matrix, resulting in intermediate syndrome components. The intermediate syndrome components are added to the appropriate entry in a syndrome vector. Once all symbols r_i are received, the syndrome vector contains the error syndromes s_i for the received code word.

Claims

1. A method for calculating a syndrome vector for an incoming stream of symbols that is protected by a block error-correction code, the stream of symbols having N symbols, with K symbols being original data symbols (K<

N), and N−

K symbols being redundant symbols, the method comprising;

making a decoding matrix available, the decoding matrix having N columns and “

N−

K”

rows;

receiving the stream of symbols, r_i, where “

i”

is an integer from 1 to N that identifies a particular position of the symbols within the stream of symbols; and

as each symbol, r_i, is received, multiplying the received symbol, r_i, by the entries in the “

ith”

column of the decoding matrix, thereby resulting in “

N−

K”

intermediate syndrome components, and adding each of the intermediate syndrome components for the received symbol, r_i, to a corresponding position of a syndrome vector.

2. A method according to claim 1, further comprising storing each of the received symbols, r_i, in a secondary store.

3. A method according to claim 2, further comprising removing the received symbol, r_i, from a working memory after each of the intermediate syndrome components for the received symbol, r_i are added to the syndrome vector.

4. A method according to claim 1, further comprising initializing the syndrome vector to zero before any of the intermediate syndrome components are added to the syndrome vector.

43. A system according to claim 1, wherein the degree of interleave is different for selected streams.

5. A method for decoding a stream of symbols that is protected by a block error-correction code, the method comprising:

receiving the stream of symbols;

as each symbol is received, calculating one or more intermediate syndrome components, and adding the intermediate syndrome components to a corresponding entry of a syndrome vector;

using the syndrome vector to identify error locations of those symbols that have an error, and calculating an error magnitude for each errored symbol; and

applying the error magnitudes to the corresponding errored symbols to produce corrected symbols.

6. A method according to claim 5, wherein the syndrome vector is initialized to zero before any of the intermediate syndrome components are added to the syndrome vector.

7. A method according to claim 5, further comprising identifying erasure locations for those symbols in the stream of symbols.

8. A method according to claim 7, wherein those symbols that have an error are identified using both the syndrome vector and the erasure locations.

9. A method according to claim 5, further comprising storing the received stream of symbols in a secondary store.

10. A method according to claim 9, further comprising removing the received symbol from a working memory after each of the intermediate syndrome components for the received symbol are added to the syndrome vector.

11. A method according to claim 10, further comprising storing the syndrome vector in a working store.

12. A method according to claim 11, further comprising storing the error locations in the working store.

13. A method according to claim 12, further comprising storing the error magnitudes in the working store.

14. A method according to claim 13, further comprising:

fetching the errored symbols from the secondary store; and

fetching the error magnitudes from the working store before the error magnitudes are applied to the corresponding errored symbols to produce the corrected symbols.

15. A method according to claim 5, wherein the error magnitudes are subtracted from the corresponding errored symbols to produce the corrected symbols.

16. A method according to claim 5, further comprising storing the corrected symbols in the secondary store.

17. A method according to claim 5, further comprising storing the error magnitudes and the error locations in the secondary store.

18. A method according to claim 17, further comprising fetching the error locations, errored symbols and error magnitudes from the secondary store at some later time, and then applying the error magnitudes to the corresponding errored symbols to produce the corrected symbols.

19. A method for decoding an incoming stream of symbols that is protected by a block error-correction code, the stream of symbols having N symbols, with K symbols being original data symbols (K<

N), and N−

K symbols being redundant symbols, the method comprising;

initializing a syndrome vector to zero, the syndrome vector having N−

K entries;

making a decoding matrix available, the decoding matrix having N columns and “

N−

K”

rows;

receiving the stream of symbols, r_i, where “

i”

is an integer from 1 to N that identifies a particular one of the symbols within the stream of symbols;

determining if the received symbol, r_i is identified as an erasure location, and if so, recording index “

i”

as an erasure location and setting r_i to zero;

multiplying the received symbol, r_i, by the entries in the “

ith”

column of the decoding matrix, thereby resulting in “

N−

K”

intermediate syndrome components, and adding the intermediate syndrome components for the received symbol, r_i to the corresponding entry in the syndrome vector;

if i<

K, store r_i in the secondary store;

once all N of the symbol positions have been processed, calculating error locations in the stream of symbols using the syndrome vector and the identified erasure locations;

calculating an error vector, e, using the error locations and the syndrome, the error vector, e, storing error magnitudes for selected symbols in the received stream of symbols;

for each erasure location, j, calculating the additive inverse of error magnitude e_j to −

e_j, and store the additive inverse −

e_j in the secondary store, overwriting the symbol that corresponds to the erasure location, j; and

for each non-erasure error location, subtracting the error magnitude e_j from the corresponding errored symbol, resulting in a corrected symbol, and storing the corrected symbol in the secondary store, overwriting the errored symbol that corresponds to the non-erasure error location.

20. A syndrome processor for calculating a syndrome vector of an incoming stream of symbols that is protected by a block error-correction code, the stream of symbols having N symbols, with K symbols being original data symbols (K<

N), and N−

K symbols being redundant symbols, the syndrome processor comprising;

an input for receiving the stream of symbols, r_i, where “

i”

is an integer from 1 to N identifying a particular position of the symbols within the stream of symbols;

a storage element for storing a decoding matrix, the decoding matrix having N columns and “

N−

K”

rows;

a multiplier for multiplying each received symbol, r_i, by the entries in the “

ith”

column of the decoding matrix, thereby resulting in “

N−

K”

intermediate syndrome components for each received symbol, r_i; and

an adder for adding the intermediate syndrome components for each received symbol, r_i to the corresponding entry in the syndrome vector.

21. A syndrome processor according to claim 20, wherein the incoming stream of symbols is interleaved with other incoming streams of symbols.

22. A decoder for decoding a stream of symbols that is protected by a block error-correction code, the decoder comprising:

an input for receiving the stream of symbols;

syndrome calculating block for calculating one or more intermediate syndrome components as each symbol is received, and adding the intermediate syndrome components to a corresponding entry of a syndrome vector;

an error locator for identifying the location of the errored symbols using the syndrome vector;

an error magnitude calculator for calculating the error magnitude for each errored symbol using the locations of the errored symbols provided by the error locator and the syndrome vector; and

an error corrector for applying the error magnitudes to the corresponding errored symbols, thereby resulting in corrected symbols.

23. A decoder according to claim 22, further comprising a working store and a secondary store.

24. A decoder according to claim 23, wherein the working store comprises random access memory.

25. A decoder according to claim 23, wherein the secondary store comprises a magnetic or optical disk.

26. A decoder according to claim 23, wherein the stream of symbols are stored in the secondary store.

27. A decoder according to claim 23, wherein the syndrome vector is stored in the working store.

28. A decoder according to claim 27, wherein the error locator reads the syndrome vector from the working store.

29. A decoder according to claim 23, wherein the error locator stores the locations of the errored symbols in the working store.

30. A decoder according to claim 23, wherein the error locator stores the locations of the errored symbols in the secondary store.

31. A decoder according to claim 23, wherein the error magnitude calculator stores the error magnitude for each errored symbol in the working store.

32. A decoder according to claim 23, wherein the error magnitude calculator stores the error magnitude for each errored symbol in the secondary store.

33. A decoder according to claim 23, wherein the error corrector stores the corrected symbols in the working store.

34. A decoder according to claim 23, wherein the error corrector stores the corrected symbols in the secondary store.

35. A method for encoding and delivering a stream of data having a number of symbols in an original order, the method comprising:

assigning each of the symbols of the stream to one of a number of blocks;

encoding each of the blocks using a block error-correction code;

interleaving the symbols from two or more of the blocks to provide a stream of output symbols; and

the assigning, encoding and interleaving steps operatively configured so that the stream of output symbols are delivered in the original order of the stream.

36. A system for encoding and delivering a stream of data having a number of symbols in an original order, the encoder comprising:

a block assignor for assigning each of the symbols of the stream to one of a number of blocks;

an encoder for encoding each of the blocks using a block error-correction code; and

an interleaver coupled to the encoder for interleaving the symbols from two or more of the blocks, the block assignor, encoder and interleaver operatively configured such that the interleaver outputs the symbols of the stream of data in the original order of the stream of data.

37. A system according to claim 36, further comprising a receiver for receiving the symbols from the interleaver and storing the output symbols to a secondary store without de-interleaving.

38. A system according to claim 37, wherein the receiver further comprises a de-interleaver for de-interleaving the output symbols.

39. A system according to claim 36, wherein the order of the block error-correction code of the encoder is different for selected objects.

40. A system according to claim 36, wherein the order of the block error-correction code of the encoder is different for selected blocks.

41. A system according to claim 40, wherein the order of the block error-correction code is specified in a predetermined data field that is read by the encoder.

42. A system according to claim 36, wherein the block size is different for selected streams.

44. A method for encoding and delivering a stream of data having a number of symbols, the method comprising:

assigning each of the symbols of the stream of data to one of a number of first ECC blocks;

encoding each of the first ECC blocks using a block error-correction code (ECC) to provide a first ECC layer;

interleaving the symbols from two or more of the encoded first ECC blocks to provide a stream of first ECC output symbols;

assigning each of the first ECC output symbols to one of a number of second ECC blocks;

encoding each of the second ECC blocks using a block error-correction code (ECC), to provide a second ECC layer; and

delivering a stream of second ECC output symbols.

45. A method for receiving and decoding the stream of second ECC output symbols of claim 44, comprising:

receiving the stream of second ECC output symbols;

decoding the stream of second ECC output symbols resulting in a stream of first ECC output symbols arranged into a number of second ECC blocks;

determining if there is an error in one of the second ECC blocks;

de-interleaving the stream of first ECC output symbols if an error is detected in one of the second ECC blocks;

decoding the de-interleaved stream of symbols if an error is detected in one of the second ECC blocks; and

skipping the de-interleave and second decoding step if an error is not detected during the determining step.