High -throughput and universal architectures for Reed -Solomon decoders

This dissertation studies high-throughput and universal architectures of RS decoders. Since arithmetic operations in the encoding and decoding of RS codes are carried out over finite fields, this dissertation also studies high-throughput and universal architectures for finite field arithmetic operations.;First, high-throughput architectures for finite field arithmetic operations are studied. Two generic finite field multipliers are discussed, and pipelined architectures based on these two multipliers are presented. New systolic architectures for finite field inversion and division are proposed. In comparison to previously proposed architectures, these new architectures have smaller critical path delays and smaller or comparable gate counts. Two types of control mechanisms based on centralized adders (or ring counters) and distributed ring counters are considered. The architectures using distributed ring counters have both small critical path delays and small cell sizes that do not grow with the size of the field, and thus are suitable for cryptographic applications wherein large fields are typically used.;Next; new modified versions of the extended Euclidean algorithm are proposed for both errors-only and errors-and-erasures RS decoding. In contrast to the algorithms in the literature, which use variable numbers of iterations, the modified algorithms proposed in this dissertation have fixed numbers of iterations. Based on these modified algorithms, new architectures using two types of control signals---broadcast and propagated---are designed. All the proposed architectures can be delay-scaled and pipelined to achieve small critical path delays.;Finally, universal field arithmetic operations and universal Reed-Solomon decoders are investigated. A new method for embedding field elements in universal architectures is proposed so as to easily adapt the high-throughput architectures for field arithmetic operations to universal architectures. The properties of these universal architectures with respect to two polynomial bases are studied. The scaling factor associated with the universal multiplier is shown to be inconsequential to the universal RS decoder. Architectures for all three blocks of universal decoder are discussed.