Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

International Symposium on Turbo Codes and Iterative Information Processing

xSA: A Binary Cross-Entropy Simulated Annealing Polar Decoder

Ryan Seah, Huayi Zhou, Marwan Jalaleddine, Warren J. Gross

Published Sep 4, 2023• 2 citations
Publisher

Abstract

Polar decoders such as successive-cancellation and successive-cancellation list decoders are limited by their sequential nature, which leads to a linear increase in latency with the codeword length. Heuristic based decoders such as quantum annealing have been proposed to overcome this limitation. However, these decoders have shown poor performance when decoding polar codes with more than eight bits. In this paper, we developed new meta-heuristic based polar decoder, called xSA, which uses a new receiver constraint modeled by the binary cross-entropy function. We also propose a method to determine the weights used in a quadratic unconstrained binary optimization (QUBO) function. The polar code is assumed to have been sent across an AWGN channel and we conducted our experiments and simulations using PyQUBO and dwave-neal. Our results show that xSA is able to decode codes of length 16 and 32 with a near-ML FER performance, presenting itself as a promising alternative to traditional polar decoders for real world applications and next generation cellular communications.

DOI
10.1109/istc57237.2023.10273491

Related papers

Decoding of Polar Codes Using Quadratic Unconstrained Binary Optimization

Huayi Zhou, Ryan Seah, Marwan Jalaleddine +1 more

Polar codes encounter challenges in decoder complexity while preserving good error-correction properties. Instead of conventional decoders, a quantum annealer (QA) decoder has been proposed to explore untapped possibilities. For future QA applications, a crucial prerequisite is transforming the optimization problem into quadratic unconstrained binary optimization (QUBO) form. However, existing QUBO forms for polar decoding result in suboptimal frame error rate (FER) performance for codes exceeding 8 bits. This paper redesigns the QUBO form for polar decoding. We first introduce a novel receiver constraint modeled by the binary cross-entropy (BCE) function. Utilizing a simulated annealing (SA) solver with the proposed QUBO form with BCE (QUBO-BCE) achieves maximum-likelihood (ML) performance for a code length of 32 bits. Next, to reduce the number of variables, we remove the frozen variables and introduce a simplified QUBO-BCE form (SQUBO-BCE). Additionally, CRC polynomials are modelled into constraints in QUBO form, resulting in a CRC-aided SQUBO-BCE (CA-SQUBO-BCE) form for polar decoding to further enhance the FER. Numerical results demonstrate that SQUBO-BCE achieves ML performance and reduces up to 61.5% of variables compared to QUBO-BCE. Furthermore, the proposed CA-SQUBO-BCE achieves near CRC-aided ML performance. The proposed SQUBO-BCE requires the lowest number of SA processes to reach a specific FER.

IEEE Journal on Selected Areas in Communications•Jul 22, 2024•3 citations

Simulated Annealing Algorithm-Aided SC Decoder for Polar Codes

Guiping Li, Ye Tang, Liu He

A new decoding scheme aided by simulated annealing algorithm is proposed to further improve the decoding performance of successive cancellation (SC) for polar codes at the short block. We use simulated annealing to revise the decoding result of SC which cannot pass the CRC check. To generate the new neighbors, the decoder flips one bit from the set of the least unreliable information bits each time in the estimated source vector of SC decoding. Euclidean distance is used to measure the gap between the new neighbor solution and the received word so that the decoder can obtain a global optimal solution. Simulation shows that the proposed decoder has a performance gain about 0.5 dB in terms of frame error rate (FER) under short blocks in the additive white Gaussian noise (AWGN) channel compared to other basic decoders, while keeping a low time cost through a parameter tuning process.

Journal of Circuits Systems and Computers•Jun 17, 2022•1 citation

SIMPLIFIED SUCCESSIVE-CANCELLATION LIST POLAR DECODING FOR BINARY LINEAR BLOCK CODES

Driss Khebbou, Reda Benkhouya, Idriss Chana +1 more

This paper aims to take advantage of the performances of polar decoding techniques for the benefit of binary linear block codes (BLBCs) with the main objective is to study the performances of the SSCL decoding for short-length BLBCs. Polar codes are one of the most recent error-correcting codes to be invented, and they have been mathematically demonstrated to be able to correct all errors under a specific situation, using the successive-cancellation decoder. However, their performances for real-time wireless communications at short block lengths remain less attractive. To take advantage of the performance of these codes in favor of error correction codes of short block length, an adaptation of the simplified successive-cancellation list as a decoder for polar codes for the benefit of short block length binary linear block codes is presented in this paper. This adaptation makes it possible to take advantage of the performances of less complex decoding methods for polar codes for BLBCs with latency and complexity optimization of the standard successive-cancellation list decoder. The experiment shows that the method can achieve the performances of the most famous order statistic decoder for binary linear block codes, which can achieve the performances of maximum-likelihood decoding with computational complexity and memory constraints.

Journal of Southwest Jiaotong University•Dec 24, 2021•3 citations

Improved Ising Model Formulation for Polar Codes

Ryan Seah, Warren J. Gross

This paper presents an improved Ising model framework for polar codes, termed POLARIS, which reduces the number of binary variables by incorporating rate-1 node structures and embedding elements of successive-cancellation decoding into the Ising formulation. The decoder scales efficiently to block lengths up to N = 64, doubling prior Ising-based limits. POLARIS achieves near-successive-cancellation list performance within 0.4 dB while reducing QUBO dimensionality from 192 to 126 variables. These advancements bring Ising-based polar decoding closer to practical realization, offering improved efficiency for implementation on both quantum and hybrid CMOS-classical annealing hardware.

IEEE International Symposium on Multiple-Valued Logic (ISMVL)•May 19, 2026•0 citations

A Low-Latency Successive Cancellation Hybrid Decoder for Convolutional Polar Codes

Yu Wang, Shikai Qiu, Lirui Chen +4 more

By adopting successive cancellation list decoding (SCL), polar codes demonstrate competitive error correction performance over LDPC and Turbo codes. However, SCL decoding suffers from high computational complexity and long decoding latency, especially when the list size is very large. Successive cancellation flip (SCF), as another decoding algorithm that can achieve high error correction performance, has a complexity that is close to that of successive cancellation (SC) decoding. With the observation that SCL and SCF decoding are similar at giving more chances to inspect possible codewords simultaneously or sequentially, a novel hybrid decoder is proposed in this paper, which essentially combines the ideas of SCF and SCL decoders. Moreover, in order to compensate for the degradation of performance caused by the reduction of path splitting and further reduce the decoding latency, the convolutional polar codes are adopted with a designed bit-flipping set. Simulation results demonstrate that the proposed decoder achieves the reduction of decoding latency while attaining better performance than conventional CRC-aided SCL decoder.

IEEE International Conference on Acoustics Speech and Signal Processing•Apr 9, 2020•1 citation

Belief Propagation Bit-Flip Decoder for Polar Codes

Yongrun Yu, Zhiwen Pan, Nan Liu +1 more

The bit-flip method has been successfully applied to the successive cancellation (SC) decoder to improve the block error rate (BLER) performance for polar codes in the finite code length region. However, due to the sequential decoding, the SC decoder inherently suffers from longer decoding latency than that of the belief propagation (BP) decoder with efficient early stopping criterion. It is natural to ask how to perform bit-flip in a polar BP decoder. In this paper, bit-flip is introduced into the BP decoder for polar codes. The idea of critical set (CS), that is, originally proposed by Zhang et al. for identifying unreliable bits in a SC bit-flip decoder, is extended to the BP decoder here. After revealing the relationship between CS and the incorrect BP decoding results, critical set with order ω (CS-ω) is constructed to identify unreliable bit decisions in polar BP decoding. The simulation results demonstrate that compared with the conventional BP decoder, the BLER of the proposed bit-flip decoder can achieve significant signal-to-noise ratio (SNR) gain which is comparable to that of a cyclic redundancy check-aided SC list decoder with a moderate list size. In addition, the decoding latency of the proposed BP bit-flip decoder is only slightly higher than that of the conventional BP decoder in the medium and high SNR regions.

IEEE Access•Jan 1, 2019•67 citations
Polar decoders such as successive-cancellation and successive-cancellation list decoders are limited by their sequential nature, which leads to a linear increase in latency with the codeword length. Heuristic based decoders such as quantum annealing have been proposed to overcome this limitation. However, these decoders have shown poor performance when decoding polar codes with more than eight bits. In this paper, we developed new meta-heuristic based polar decoder, called xSA, which uses a new receiver constraint modeled by the binary cross-entropy function. We also propose a method to determine the weights used in a quadratic unconstrained binary optimization (QUBO) function. The polar code is assumed to have been sent across an AWGN channel and we conducted our experiments and simulations using PyQUBO and dwave-neal. Our results show that xSA is able to decode codes of length 16 and 32 with a near-ML FER performance, presenting itself as a promising alternative to traditional polar decoders for real world applications and next generation cellular communications.
Polar codes encounter challenges in decoder complexity while preserving good error-correction properties. Instead of conventional decoders, a quantum annealer (QA) decoder has been proposed to explore untapped possibilities. For future QA applications, a crucial prerequisite is transforming the optimization problem into quadratic unconstrained binary optimization (QUBO) form. However, existing QUBO forms for polar decoding result in suboptimal frame error rate (FER) performance for codes exceeding 8 bits. This paper redesigns the QUBO form for polar decoding. We first introduce a novel receiver constraint modeled by the binary cross-entropy (BCE) function. Utilizing a simulated annealing (SA) solver with the proposed QUBO form with BCE (QUBO-BCE) achieves maximum-likelihood (ML) performance for a code length of 32 bits. Next, to reduce the number of variables, we remove the frozen variables and introduce a simplified QUBO-BCE form (SQUBO-BCE). Additionally, CRC polynomials are modelled into constraints in QUBO form, resulting in a CRC-aided SQUBO-BCE (CA-SQUBO-BCE) form for polar decoding to further enhance the FER. Numerical results demonstrate that SQUBO-BCE achieves ML performance and reduces up to 61.5% of variables compared to QUBO-BCE. Furthermore, the proposed CA-SQUBO-BCE achieves near CRC-aided ML performance. The proposed SQUBO-BCE requires the lowest number of SA processes to reach a specific FER.
A new decoding scheme aided by simulated annealing algorithm is proposed to further improve the decoding performance of successive cancellation (SC) for polar codes at the short block. We use simulated annealing to revise the decoding result of SC which cannot pass the CRC check. To generate the new neighbors, the decoder flips one bit from the set of the least unreliable information bits each time in the estimated source vector of SC decoding. Euclidean distance is used to measure the gap between the new neighbor solution and the received word so that the decoder can obtain a global optimal solution. Simulation shows that the proposed decoder has a performance gain about 0.5 dB in terms of frame error rate (FER) under short blocks in the additive white Gaussian noise (AWGN) channel compared to other basic decoders, while keeping a low time cost through a parameter tuning process.
This paper aims to take advantage of the performances of polar decoding techniques for the benefit of binary linear block codes (BLBCs) with the main objective is to study the performances of the SSCL decoding for short-length BLBCs. Polar codes are one of the most recent error-correcting codes to be invented, and they have been mathematically demonstrated to be able to correct all errors under a specific situation, using the successive-cancellation decoder. However, their performances for real-time wireless communications at short block lengths remain less attractive. To take advantage of the performance of these codes in favor of error correction codes of short block length, an adaptation of the simplified successive-cancellation list as a decoder for polar codes for the benefit of short block length binary linear block codes is presented in this paper. This adaptation makes it possible to take advantage of the performances of less complex decoding methods for polar codes for BLBCs with latency and complexity optimization of the standard successive-cancellation list decoder. The experiment shows that the method can achieve the performances of the most famous order statistic decoder for binary linear block codes, which can achieve the performances of maximum-likelihood decoding with computational complexity and memory constraints.
This paper presents an improved Ising model framework for polar codes, termed POLARIS, which reduces the number of binary variables by incorporating rate-1 node structures and embedding elements of successive-cancellation decoding into the Ising formulation. The decoder scales efficiently to block lengths up to N = 64, doubling prior Ising-based limits. POLARIS achieves near-successive-cancellation list performance within 0.4 dB while reducing QUBO dimensionality from 192 to 126 variables. These advancements bring Ising-based polar decoding closer to practical realization, offering improved efficiency for implementation on both quantum and hybrid CMOS-classical annealing hardware.
By adopting successive cancellation list decoding (SCL), polar codes demonstrate competitive error correction performance over LDPC and Turbo codes. However, SCL decoding suffers from high computational complexity and long decoding latency, especially when the list size is very large. Successive cancellation flip (SCF), as another decoding algorithm that can achieve high error correction performance, has a complexity that is close to that of successive cancellation (SC) decoding. With the observation that SCL and SCF decoding are similar at giving more chances to inspect possible codewords simultaneously or sequentially, a novel hybrid decoder is proposed in this paper, which essentially combines the ideas of SCF and SCL decoders. Moreover, in order to compensate for the degradation of performance caused by the reduction of path splitting and further reduce the decoding latency, the convolutional polar codes are adopted with a designed bit-flipping set. Simulation results demonstrate that the proposed decoder achieves the reduction of decoding latency while attaining better performance than conventional CRC-aided SCL decoder.
The bit-flip method has been successfully applied to the successive cancellation (SC) decoder to improve the block error rate (BLER) performance for polar codes in the finite code length region. However, due to the sequential decoding, the SC decoder inherently suffers from longer decoding latency than that of the belief propagation (BP) decoder with efficient early stopping criterion. It is natural to ask how to perform bit-flip in a polar BP decoder. In this paper, bit-flip is introduced into the BP decoder for polar codes. The idea of critical set (CS), that is, originally proposed by Zhang et al. for identifying unreliable bits in a SC bit-flip decoder, is extended to the BP decoder here. After revealing the relationship between CS and the incorrect BP decoding results, critical set with order ω (CS-ω) is constructed to identify unreliable bit decisions in polar BP decoding. The simulation results demonstrate that compared with the conventional BP decoder, the BLER of the proposed bit-flip decoder can achieve significant signal-to-noise ratio (SNR) gain which is comparable to that of a cyclic redundancy check-aided SC list decoder with a moderate list size. In addition, the decoding latency of the proposed BP bit-flip decoder is only slightly higher than that of the conventional BP decoder in the medium and high SNR regions.