An official website of the United States government
The generalized integrated interleaved BCH (GII-BCH) codes are among the best error-correcting codes for next-generation terabit/s memories. The key equation solver (KES) in the nested decoding of GII codes limits the achievable clock frequency. Recently, by polynomial scalar pre-computation, the critical path of the nested KES for Reed-Solomon (RS)-based GII codes has been reduced to one multiplier. However, for GII-BCH codes, the nested KES has more complicated formulas in order to skip the odd iterations and hence prior techniques do not directly extend. This paper proposes novel reformulations of the nested BCH KES to enable scalar pre-computation. Additionally, polynomial scaling is incorporated to enable complexity reduction. As a result, the critical path of the nested BCH KES with odd iterations skipped is reduced to one multiplier. For an example GII-BCH code over GF(2^{12}), the proposed design reduces the average nested BCH KES latency to around a half with similar silicon area compared to the best prior design.
more »
« less
Efficient Nested Key Equation Solver for Short Generalized Integrated Interleaved BCH Codes
Generalized integrated interleaved (GII) codes can nest BCH sub-codewords to form stronger BCH codewords. They are among the best candidates for error correction in the new storage class memories (SCMs). However, SCMs require short codeword length and low redundancy. In this case, the nested key equation solver (KES), which is a key step in GII decoding, has a small number of iterations. The initialization and/or scalar pre-computation in previous nested KES designs have large area and may take even longer time than the iterations themselves. This paper proposes an efficient nested KES design for short GII-BCH codes. The polynomial updating is decomposed into two steps to reduce the critical path without requiring scalar pre-computation. Besides, the KES is reformulated to reduce the number of clock cycles without incurring any area overhead. For an example code over GF(2^{10}) that protects 2560 bits with 10% redundancy, the proposed design achieves at least 25% area reduction and 37% reduction on the area-time product averaged over the nested decoding rounds compared to prior efforts.
more »
« less
- Award ID(s):
- 2011785
- PAR ID:
- 10329903
- Date Published:
- Journal Name:
- Proceedings IEEE International Symposium on Circuits and Systems
- ISSN:
- 0271-4310
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Reed–Muller (RM) codes exhibit good performance under maximum-likelihood (ML) decoding due to their highly- symmetric structure. In this paper, we explore the question of whether the code symmetry of RM codes can also be exploited to achieve near-ML performance in practice. The main idea is to apply iterative decoding to a highly-redundant parity-check (PC) matrix that contains only the minimum-weight dual codewords as rows. As examples, we consider the peeling decoder for the binary erasure channel, linear-programming and belief propagation (BP) decoding for the binary-input additive white Gaussian noise channel, and bit-flipping and BP decoding for the binary symmetric channel. For short block lengths, it is shown that near-ML performance can indeed be achieved in many cases. We also propose a method to tailor the PC matrix to the received observation by selecting only a small fraction of useful minimum-weight PCs before decoding begins. This allows one to both improve performance and significantly reduce complexity compared to using the full set of minimum-weight PCs.more » « less
-
An expurgating linear function (ELF) is an outer code that disallows low-weight codewords of the inner code. ELFs can be designed either to maximize the minimum distance or to minimize the codeword error rate (CER) of the expurgated code. A list-decoding sieve can efficiently identify ELFs that maximize the minimum distance of the expurgated code. For convolutional inner codes, this paper provides analytical distance spectrum union (DSU) bounds on the CER of the concatenated code. For short codeword lengths, ELFs transform a good inner code into a great concatenated code. For a constant message size of K = 64 bits or constant codeword blocklength of N = 152 bits, an ELF can reduce the gap at CER 10−6 between the DSU and the random-coding union (RCU) bounds from over 1 dB for the inner code alone to 0.23 dB for the concatenated code. The DSU bounds can also characterize puncturing that mitigates the rate overhead of the ELF while maintaining the DSU-to-RCU gap. List Viterbi decoding guided by the ELF achieves maximum likelihood (ML) decoding of the concatenated code with a sufficiently large list size. The rate-K/(K+m) ELF outer code reduces rate and list decoding increases decoder complexity. As SNR increases, the average list size converges to 1 and average complexity is similar to Viterbi decoding on the trellis of the inner code. For rare large-magnitude noise events, which occur less often than the FER of the inner code, a deep search in the list finds the ML codeword.more » « less
-
Tal, Ido (Ed.)Recently, rate-1/ n zero-terminated (ZT) and tail-biting (TB) convolutional codes (CCs) with cyclic redundancy check (CRC)-aided list decoding have been shown to closely approach the random-coding union (RCU) bound for short blocklengths. This paper designs CRC polynomials for rate-( n - 1)/ n ZT and TB CCs with short blocklengths. This paper considers both standard rate-( n -1)/ n CC polynomials and rate-( n - 1)/ n designs resulting from puncturing a rate-1/2 code. The CRC polynomials are chosen to maximize the minimum distance d min and minimize the number of nearest neighbors A dmin . For the standard rate-( n - 1)/ n codes, utilization of the dual trellis proposed by Yamada et al . lowers the complexity of CRC-aided serial list Viterbi decoding (SLVD). CRC-aided SLVD of the TBCCs closely approaches the RCU bound at a blocklength of 128. This paper compares the FER performance (gap to the RCU bound) and complexity of the CRC-aided standard and punctured ZTCCs and TBCCs. This paper also explores the complexity-performance trade-off for three TBCC decoders: a single-trellis approach, a multi-trellis approach, and a modified single-trellis approach with pre-processing using the wrap around Viterbi algorithm.more » « less
-
A status updating system is considered in which a variable length code is used to transmit messages to a receiver over a noisy channel. The goal is to optimize the codewords lengths such that successfully-decoded messages are timely. That is, such that the age-of-information (AoI) at the receiver is minimized. A hybrid ARQ (HARQ) scheme is employed, in which variable-length incremental redundancy (IR) bits are added to the originally-transmitted codeword until decoding is successful. With each decoding attempt, a non-zero processing delay is incurred. The optimal codewords lengths are analytically derived utilizing a sequential differential optimization (SDO) framework. The framework is general in that it only requires knowledge of an analytical expression of the positive feedback (ACK) probability as a function of the codeword length.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- The DOI is not currently available.
