An official website of the United States government
The recursive projection-aggregation (RPA) decoding algorithm for Reed-Muller (RM) codes was recently introduced by Ye and Abbe. We show that the RPA algorithm is closely related to (weighted) belief-propagation (BP) decoding by interpreting it as a message-passing algorithm on a factor graph with redundant code constraints. We use this observation to introduce a novel decoder tailored to high-rate RM codes. The new algorithm relies on puncturing rather than projections and is called recursive puncturing-aggregation (RXA). We also investigate collapsed (i.e., non-recursive) versions of RPA and RXA and show some examples where they achieve similar performance with lower decoding complexity.
more »
« less
High-Rate and Low-Complexity Space-Time Block Codes for 2×2 MIMO Systems
The main design criteria for space-time block codes (STBCs) are the code rate, diversity order, coding gain, and low decoder complexity. In this letter, we propose a full-rate full-diversity STBC for 2 × 2 multiple-input multiple-output (MIMO) systems with a substantially lower maximum likelihood (ML) detection complexity than that of existing schemes. This makes the implementation of high-performance full-rate codes feasible for practical systems. Our numerical evaluation shows that the proposed code achieves significantly lower decoding complexity while maintaining a similar performance compared to that of existing rate-2 STBCs.
more »
« less
- Award ID(s):
- 1642865
- PAR ID:
- 10043846
- Date Published:
- Journal Name:
- IEEE communications letters
- ISSN:
- 1558-2558
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Quantum error correction codes (QECCs) are essential for reliable quantum computing as they protect quantum states against noise and errors. Limited research has explored the resilience of QECCs to biased noise, critical for selecting optimal codes. We examine how different noise types impact QECCs, considering the varying susceptibility of quantum systems to specific errors. Our goal is to identify opportunities to minimize the resources—or overhead—needed for effective error correction. We conduct a detailed study on two QECCs—rotated and unrotated surface codes—under various noise models using simulations. Rotated surface codes generally perform better due to their simplicity and lower qubit overhead. They exceed the noise threshold of current quantum processors, making them more effective at lower error rates. This study highlights a hierarchy in surface code implementation based on resource demand, consistently observed across both code types. Our analysis ranks the code-capacity model as the most pessimistic and the circuit-level model as the most realistic, mapping error thresholds that show surface code advantages. Additionally, higher code distances improve performance without excessively increasing qubit overhead. Tailoring surface codes to align with the target logical error rate and the biased physical error profile is crucial for optimizing reliability and resource use.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
-
In general, the generator matrix sparsity is a critical factor in determining the encoding complexity of a linear code. Further, certain applications, e.g., distributed crowdsourcing schemes utilizing linear codes, require most or even all the columns of the generator matrix to have some degree of sparsity. In this paper, we leverage polar codes and the well-established channel polarization to design capacity-achieving codes with a certain constraint on the weights of all the columns in the generator matrix (GM) while having a low-complexity decoding algorithm. We first show that given a binary-input memoryless symmetric (BMS) channel $$W$$ and a constant $$s \in (0, 1]$$ , there exists a polarization kernel such that the corresponding polar code is capacity-achieving with the rate of polarization $s/2$ , and the GM column weights being bounded from above by $$N^{s}$$ . To improve the sparsity versus error rate trade-off, we devise a column-splitting algorithm and two coding schemes for BEC and then for general BMS channels. The polar-based codes generated by the two schemes inherit several fundamental properties of polar codes with the original $$2 \times 2$$ kernel including the decay in error probability, decoding complexity, and the capacity-achieving property. Furthermore, they demonstrate the additional property that their GM column weights are bounded from above sublinearly in $$N$$ , while the original polar codes have some column weights that are linear in $$N$$ . In particular, for any BEC and $$\beta < 0.5$$ , the existence of a sequence of capacity-achieving polar-based codes where all the GM column weights are bounded from above by $$N^{\lambda} $$ with $$\lambda \approx 0.585$$ , and with the error probability bounded by $${\mathcal {O}}(2^{-N^{\beta }})$$ under a decoder with complexity $${\mathcal {O}}(N\log N)$$ , is shown. The existence of similar capacity-achieving polar-based codes with the same decoding complexity is shown for any BMS channel and $$\beta < 0.5$$ with $$\lambda \approx 0.631$$ .more » « less
-
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
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- The DOI is not currently available.
