Search

Generalized integrated interleaved (GII) codes nest a set of linear block codewords to generate codewords belonging to stronger codes. They are among the best error-correcting codes for next-generation hyper-speed digital communications and storage. Serial encoders for GII codes based on BCH codes have been previous investigated. They consist of BCH encoders whose inputs and outputs are multiplied by vectors decided by the nesting scheme. However, parallel GII encoders for high-speed systems cannot be designed by directly extending serial encoders due to the unique feature that BCH codes of different error-correcting capabilities are involved. Moreover, GII decoder complexity and latency can be greatly reduced by sharing the encoder to compute short remainders for syndrome computation. Although previous resource-shareable BCH encoders can be utilized to implement resource-shareable GII encoders, they are all serial. This paper first proposes a low-complexity scheme to handle the different error-correcting capabilities of the involved codes and align the input and parity symbols for parallel processing. Then two efficient parallel resource-shareable BCH encoder architectures to be used as GII encoder components are developed. The first design is achieved by deriving parallel register state update formulas for concatenated linear-feedback shift registers (LFSRs). Through reformulating the remainder polynomial divisions, the second design allows the inputs to be added to different LFSR taps, and accordingly reduces the complexity by a significant portion. For an example 160-parallel GII-BCH encoder considered for Flash memory applications, the second proposed design requires 14% smaller area compared to the first one. Besides both of them lead to around 50% latency reduction in the nested syndrome computation with small area overheads compared to the best possible alternative design. [ABSTRACT FROM AUTHOR]

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(2^{8})$ 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. [ABSTRACT FROM AUTHOR]

Generalized integrated interleaved (GII) codes nest linear block codewords to generate codewords belonging to stronger linear block codes. They can achieve very high throughput with excellent error-correcting capability. GII codes can be based on either Reed-Solomon (RS) or BCH codes. GII-BCH codes are the most promising candidate for error correction in next-generation terabit/s Flash and storage class memories, and optical communications. On the other hand, GII decoder implementation faces many challenges. In particular, the key equation solver (KES) in the nested decoding process causes not only clock frequency bottleneck but also large area. Although techniques have been developed recently to address these issues for GII-RS codes, they cannot be directly extended for binary GII-BCH codes if every other iteration of the nested KES is skipped to reduce the latency. Two instead of one higher-order syndromes need to be incorporated into each nested KES iteration and this makes the implementation much more challenging. In this paper, algorithmic reformulations and architectural modifications are developed to eliminate the clock frequency bottleneck and reduce the area of GII-BCH nested KES. Additionally, the number of processing elements is substantially reduced by analyzing the minimum number of coefficients to keep for the involved polynomials without undesirable degradation on the error-correcting performance. The critical path of the proposed scaled nested BCH KES architecture with reduced processing elements is only one multiplier and three adders. For an example GII-BCH code over ${GF}(2^{12})$ that has a ${t}_{v}=58$ -error-correcting code as the most powerful code generated by the nesting, our design also further reduces the area by 33%. [ABSTRACT FROM AUTHOR]

Generalized integrated interleaved (GII) codes allow localized decoding of short sub-codewords. They are essential to hyper-speed data storage, communications, and continued scaling of distributed storage. Sub-codewords, which are usually Reed–Solomon (RS) or BCH codewords, are nested to generate codewords of higher correction capabilities. If the decoding of individual sub-codewords fails, the higher-order syndromes from the nested codewords are utilized to correct more errors. GII decoder design faces many challenges. The major ones include: 1) high-speed nested decoding utilizing the higher-order syndromes; 2) efficient updating of higher-order syndromes after sub-codewords are corrected; 3) computation of nested syndromes and matrix inversion for converting them to higher-order sub-codeword syndromes; and 4) efficient architectures capable of addressing the variable correction capabilities of the nested codewords. This paper proposes novel algorithmic reformulations and architectural transformations to address each bottleneck. For an example, GII code that has the same rate and length as eight un-nested (255, 223) RS codes, the proposed GII decoder achieves more than seven orders of magnitude improvement in error-correcting performance with less than 30% area overhead compared to the RS decoder. With a critical path of seven XOR gates, the proposed decoder can easily achieve more than 40 GB/s throughput. [ABSTRACT FROM AUTHOR]