A global optimization algorithm （GOA） for parallel Chien search circuit in Reed-Solomon （RS） （255,239） decoder is presented. By finding out the common modulo 2 additions within groups of Galois field （GF） mult...A global optimization algorithm （GOA） for parallel Chien search circuit in Reed-Solomon （RS） （255,239） decoder is presented. By finding out the common modulo 2 additions within groups of Galois field （GF） multipliers and pre-computing the common items, the GOA can reduce the number of XOR gates efficiently and thus reduce the circuit area. Different from other local optimization algorithms, the GOA is a global one. When there are more than one maximum matches at a time, the best match choice in the GOA has the least impact on the final result by only choosing the pair with the smallest relational value instead of choosing a pair randomly. The results show that the area of parallel Chien search circuits can be reduced by 51% compared to the direct implementation when the group-based GOA is used for GF multipliers and by 26% if applying the GOA to GF multipliers separately. This optimization scheme can be widely used in general parallel architecture in which many GF multipliers are involved.展开更多
Reed-Solomon (RS) and Bose-Chaudhuri-Hocquenghem (BCH) error correcting codes are widely used in digital technology. An important problem in the implementation of RS and BCH decoding is the fast finding of the error p...Reed-Solomon (RS) and Bose-Chaudhuri-Hocquenghem (BCH) error correcting codes are widely used in digital technology. An important problem in the implementation of RS and BCH decoding is the fast finding of the error positions (the roots of error locator polynomials). Several fast root-finding algorithms for polynomials over finite fields have been proposed. In this paper we give a generalization of the Goertzel algorithm. Our algorithm is suitable for the parallel hardware implementation and the time of multiplications used is restricted by a constant.展开更多
文摘A global optimization algorithm （GOA） for parallel Chien search circuit in Reed-Solomon （RS） （255,239） decoder is presented. By finding out the common modulo 2 additions within groups of Galois field （GF） multipliers and pre-computing the common items, the GOA can reduce the number of XOR gates efficiently and thus reduce the circuit area. Different from other local optimization algorithms, the GOA is a global one. When there are more than one maximum matches at a time, the best match choice in the GOA has the least impact on the final result by only choosing the pair with the smallest relational value instead of choosing a pair randomly. The results show that the area of parallel Chien search circuits can be reduced by 51% compared to the direct implementation when the group-based GOA is used for GF multipliers and by 26% if applying the GOA to GF multipliers separately. This optimization scheme can be widely used in general parallel architecture in which many GF multipliers are involved.
基金This work was partially supported by the National Natural Science Foundation of China (Grant Nos. 60433050, 90607005)
文摘Reed-Solomon (RS) and Bose-Chaudhuri-Hocquenghem (BCH) error correcting codes are widely used in digital technology. An important problem in the implementation of RS and BCH decoding is the fast finding of the error positions (the roots of error locator polynomials). Several fast root-finding algorithms for polynomials over finite fields have been proposed. In this paper we give a generalization of the Goertzel algorithm. Our algorithm is suitable for the parallel hardware implementation and the time of multiplications used is restricted by a constant.
