Fast Nested Key Equation Solvers for Generalized Integrated Interleaved Decoder

Generalized integrated interleaved (GII) codes nest Reed-Solomon (RS) or BCH sub-codewords to generate codewords belonging to stronger RS or BCH codes. Their hyper-speed decoding and good error-correction capability make them one of the best candidates for next-generation terabit/s digital storage and communications. The key equation solver (KES) in the nested decoding stage causes clock frequency bottleneck and takes a large portion of the GII decoder area. Recent architectures reduce the critical path to two multipliers and rely on the application of the slow-down technique to further reduce it to one. The slow-down technique requires two sub-codewords to be interleaved in the nested KES. However, most of the time, the nested decoding only needs to be carried out on one sub- codeword and half of the clock cycles are wasted. This paper proposes two fast nested KES algorithms, both of which have one multiplier in the critical path without applying slow-down and accordingly reduce the latency of the nested KES to almost a half. The short critical path is achieved by algorithmic reformulations that enable the pre-computation of the scalars in parallel with polynomial updating. Our second design adopts scaled versions of the polynomials to enable product term sharing so that the number of multipliers in each pair of processing elements is reduced from 8 as in the first design to 4. Novel scaling and combined scalar computations are developed to keep the critical path one multiplier. For an example GII code over GF(28) that has 3 nested codewords, our designs achieve 49.9% reduction on the number of clock cycles needed in the nested KES compared to prior designs. Besides, our second design requires 22% less area than the first one under the same timing constraint.