An official website of the United States government
Convolutional codes have been widely studied and used in many systems. As the number of memory elements increases, frame error rate (FER) improves but computational complexity increases exponentially. Recently, decoders that achieve reduced average complexity through list decoding have been demonstrated when the convolutional encoder polynomials share a common factor that can be understood as a CRC or more generally an expurgating linear function (ELF). However, classical convolutional codes avoid such common factors because they result in a catastrophic encoder. This paper provides a way to access the complexity reduction possible with list decoding even when the convolutional encoder polynomials do not share a common factor. Decomposing the original code into component encoders that fully exclude some polynomials can allow an ELF to be factored from each component. Dual list decoding of the component encoders can often find the ML codeword. Including a fallback to regular Viterbi decoding yields excellent FER performance while requiring less average complexity than always performing Viterbi on the original trellis. A best effort dual list decoder that avoids Viterbi has performance similar to the ML decoder. Component encoders that have a shared polynomial allow for even greater complexity reduction.
more »
« less
An Efficient Parallel Architecture for Resource-Shareable Reed-Solomon Encoder
Reed-Solomon (RS) codes are adopted in many digital communication and storage systems to ensure data reliability. For many of these systems, the encoder and decoder are not active at the same time. In previous designs, RS encoders implemented as linear feedback shift registers in a concatenated structure are reused to compute the syndromes so that the decoder complexity is reduced. However, the parallel versions of such encoders have very long critical path and hence can not achieve high speed. This paper proposes a new parallel resource-shareable RS encoder architecture based on the Chinese Remainder Theorem (CRT). The generator polynomial of RS codes is decomposed into factors of degree one and state transformation is developed to enable the sharing of the hardware units for syndrome computation. As a result, the critical path is reduced to only one multiplier and one adder, regardless of the parallelism. Additionally, by utilizing the property that the degrees of the decomposed polynomial factors are one, optimizations are also developed to greatly simplify the CRT-based encoder. For example encoders of a (255, 229) RS code over GF(2^8), our proposed design can achieve at least 29% higher efficiency in terms of area-time product for moderate or higher parallelisms compared to the previous resource-shareable RS encoder and traditional parallel RS encoders combined with syndrome computation units that implement the same functionality.
more »
« less
- Award ID(s):
- 2011785
- PAR ID:
- 10329904
- Date Published:
- Journal Name:
- IEEE Workshop on Signal Processing Systems
- Page Range / eLocation ID:
- 152 to 157
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
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
-
Yael Tauman Kalai and Adam D. Smith and Daniel Wichs (Ed.)Constructions of locally decodable codes (LDCs) have one of two undesirable properties: low rate or high locality (polynomial in the length of the message). In settings where the encoder/decoder have already exchanged cryptographic keys and the channel is a probabilistic polynomial time (PPT) algorithm, it is possible to circumvent these barriers and design LDCs with constant rate and small locality. However, the assumption that the encoder/decoder have exchanged cryptographic keys is often prohibitive. We thus consider the problem of designing explicit and efficient LDCs in settings where the channel is slightly more constrained than the encoder/decoder with respect to some resource e.g., space or (sequential) time. Given an explicit function f that the channel cannot compute, we show how the encoder can transmit a random secret key to the local decoder using f(⋅) and a random oracle 𝖧(⋅). We then bootstrap the private key LDC construction of Ostrovsky, Pandey and Sahai (ICALP, 2007), thereby answering an open question posed by Guruswami and Smith (FOCS 2010) of whether such bootstrapping techniques are applicable to LDCs in channel models weaker than just PPT algorithms. Specifically, in the random oracle model we show how to construct explicit constant rate LDCs with locality of polylog in the security parameter against various resource constrained channels.more » « less
-
This paper treats point-to-point, multiple access and random access lossless source coding in the finite-blocklength regime. A random coding technique is developed, and its power in analyzing the third-order coding performance is demonstrated in all three scenarios. Results include a third-order-optimal characterization of the Slepian-Wolf rate region and a proof showing that for dependent sources, the independent encoders used by Slepian-Wolf codes can achieve the same third-order- optimal performance as a single joint encoder. The concept of random access source coding, which generalizes the multiple access scenario to allow for a subset of participating encoders that is unknown a priori to both the encoders and the decoder, is introduced. Contributions include a new definition of the probabilistic model for a random access-discrete multiple source, a general random access source coding scheme that employs a rateless code with sporadic feedback, and an analysis demonstrating via a random coding argument that there exists a deterministic code of the proposed structure that simultaneously achieves the third- order-optimal performance of Slepian-Wolf codes for all possible subsets of encoders.more » « less
-
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
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- https://doi.org/10.1109/SiPS52927.2021.00035
