High speed hardware implementation of modified Reed-Solomon decoder

A digital communications system utilizing an RS(n′, k′) code modified from an RS(n, k) code, wherein n, k, n′, and k′ are integers, and k′<n′<n, k′<k <n, comprising:

• a channel for data transmission;
• a transmitter for encoding k′-symbol message blocks into n-symbol codewords and transmitting n′-symbols of each codeword into the channel;
• and
• a receiver for receiving and decoding n′-symbol vectors each corresponding to the n′ symbols of one codeword transmitted by the transmitter, the receiver comprising
• a memory device having stored therein one erasure locator polynomial σ0 (x) and look-up tables,
• a syndrome calculator for receiving the n′-symbol vectors and for calculating syndromes of each n′-symbol vector, wherein the i-th syndrome Si of one n′-symbol vector R′, (rn′−1, rn′−2, . . . , r0), is Si=Rs(αi+1) for i=0, 1, . . . , n−k−1, wherein Rs(x)=rn′−1xn′−1+rn′−2xn′−2+ . . . +r0, and
• means for finding the locations and values of the errors in each n′-symbol vector using the syndromes thereof and the one erasure locator polynomial σ0(x).

A method performed by a decoder for decoding an RS( n′, k′) code modified from an RS( n, k) code, wherein n, k, n′, and k′are integers, and k′<n′<n, k′<k <n, the method comprising:

• storing one erasure locator polynomial σ0(x) in a memory device in the decoder;
• receiving n′-symbol vectors each corresponding to a k′-symbol message block;
• and
• decoding each n′-symbol vector R′, (rn′−1, rn′−2, . . . , r0), including
• calculating syndromes of R′, wherein the i-th syndrome Si is Si=Rs(αi+1) for i=0, 1, . . . , n−k−1, wherein Rs(x)=rn′−1xn′−1+rn′−2xn′−2+ . . . +r0;
• generating an adjusted error/erasure locator polynomial {tilde over (σ)}(x) and an adjusted error/erasure evaluator polynomial {tilde over (ω)}(x) based on the syndromes;
• and
• finding the locations and values of errors in R′based on the adjusted error/erasure locator polynomial {tilde over (σ)}(x) and the adjusted error/erasure evaluator polynomial {tilde over (ω)}(x), using a look-up table stored in the memory device.