Reed-solomon decoder using discrete time delay in power sum computation

• US 5,471,485 A
• Filed: 11/24/1992
• Issued: 11/28/1995
• Est. Priority Date: 11/24/1992
• Status: Expired due to Term

• Current Assignee: LSI Logic Corporation (Broadcom, Inc.)
• Original Assignee: LSI Logic Corporation (Broadcom, Inc.)
• Inventors: Tong, Po
• Primary Examiner(s): Baker, Stephen M.
• Application Number:
  US07/980,944
• Time in Patent Office: 1,099 Days
• Field of Search: 371/37.6, 371/37.1, 371/38.1, 371/40.1
• US Class Current: 714/757
• 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 power sum computation unit for a Reed-Solomon decoder having r redundant symbols and in which a code word, R, has a first plurality (n) of symbols, each symbol having a plurality (m) of bits, including multiplier unit for multiplying in parallel M symbols by powers of a finite field element, α, to obtain the power sums ##EQU2## The multiplier unit includes M multipliers for multiplying M symbols by powers of alpha, and memory delay including a latch, a random access memory, and a flipflop store symbols and sequentially provide M symbols to the multiplier unit. Exclusive OR gate selectively connects products from the multiplier unit and data input words to the memory delay. A counter is provided for the random access memory with the counter having a modulo number equal to one less than r/M, and the random access memory having a depth equal to one less than r/M.

Claims

1. A power sum computation unit for a decoder of a Reed-Solomon code having a redundancy of r symbols and m bits per symbol in which M parallel multipliers operate on M symbols simultaneously to increase computation speed by M over a symbol-serial computation speed, said power sum computation unit comprising

data input means for sequentially receiving coded symbols,

a plurality of exclusive OR gates equal in number to said plurality of multipliers,

memory delay means having a bit width equal in number to said number of multipliers times the number of bits per symbol, and a depth equal in number to said redundancy divided by the number of multipliers,

said plurality of exclusive OR gates connecting coded symbols to said memory delay means,

multiplication means including said M parallel multipliers,

gate means for sequentially applying said symbols stored in said memory delay means to said M parallel multipliers,

means for providing powers of a finite field element, α

, from the power 0 to the power equal in number to one less than the redundancy to said multiplication means, whereby said multiplication means multiplies in parallel M symbols by said powers of said alpha, and

means for applying the products from said multiplications means to said exclusive OR gates along with coded symbols to provide a power sum output from said exclusive OR gate.

2. The power sum computation unit as defined by claim 1 wherein said memory delay means comprises a latch having a bit width equal in number to Mxm, a random access memory having an input and an output, said random access memory having a bit width equal to Mxm, said latch being connected to an input of said random access memory, and a flipflop having a bit width equal in number Mxm, said flipflop being connected to the output of said random access memory.

3. The power sum computation unit as defined by claim 2 and further including a counter for said random access memory, said counter having a modulo number equal to one less than r/M, said random access memory having a depth equal to one less than r/M.

4. The power sum computation unit for a Reed-Solomon decoder in which a code word, R, comprises a first plurality, n, said power sum computation unit comprising multiplication means for multiplying in parallel said n symbols by powers of a finite field element, α

, to obtain the power sums ##EQU5## said multiplication means including M multipliers for simultaneously multiplying M symbols by powers of said finite field element,

memory delay means for storing symbols and simultaneously providing M Symbols to said multiplication means, said memory delay means comprising a latch having a bit width equal in the number of symbols per word times the number of bits per symbol (Mxm), a random access memory having an input and an output, said random access memory having a bit width equal to Mxm, said latch being connected to an input of said random access memory, and a flipflop having a bit width equal to Mxm, said flipflop being connected to the output of said random access memory, and

exclusive OR means for selectively connecting products from said multiplication means and data input symbols to said memory delay means.

5. The power sum computation unit as defined by claim 4 and further including a counter for said random access memory, said counter having a modulo number equal to one less than r/M, where r is the number of redundant symbols said random access memory having a depth equal to one less than r/M.