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

arXiv:1506.05896 · IEEE International Conference on Acoustics Speech and Signal Processing

A hybrid partial sum computation unit architecture for list decoders of polar codes

Jun Ting Lin, Zhiyuan Yan

Published Apr 1, 2015• 3 citations
arXivHTMLPDF

Abstract

Although the successive cancelation (SC) algorithm works well for very long polar codes, its error performance for shorter polar codes is much worse. Several SC based list decoding algorithms have been proposed to improve the error performances of both long and short polar codes. A significant step of SC based list decoding algorithms is the updating of partial sums for all decoding paths. In this paper, we first proposed a lazy copy partial sum computation algorithm for SC based list decoding algorithms. Instead of copying partial sums directly, our lazy copy algorithm copies indices of partial sums. Based on our lazy copy algorithm, we propose a hybrid partial sum computation unit architecture, which employs both registers and memories so that the overall area efficiency is improved. Compared with a recent partial sum computation unit for list decoders, when the list size L = 4, our partial sum computation unit achieves an area saving of 23% and 63% for block length 213and 215, respectively.

DOI
10.1109/icassp.2015.7178135

Related papers

Hardware And Latency Efficient Architecture for Successive Cancellation List Decoding of Polar Codes

M Lakshmi, Narayanan G Lakshmi

In order to achieve a magnificent error-correcting performance Successive Cancellation List (SCL) decoding is a powerful and excellent method which considers L decoding paths at each decoding stage concurrently. However, the conventional SCL decoder uses L copies of Successive Cancellation (SC) decoder for a list size of L thereby resulting in a massive increase in the hardware as the list size increases which is one of the major drawbacks of SCL decoder. One more drawback of SCL decoder architecture is the long latency of the architecture. Using the proposed efficient utilization of existing hardware architecture, there is a reduction in the number of Merged Processing Elements (MPE) by 39% for a list size of 2 and 45% for a list size of 4 when compared to the existing architectures and a vast reduction compared to conventional SCL decoder. The partial pipelining considered in this work can reduce the latency compared to conventional SCL multi-bit architecture to a greater extent.

TEQIP III Sponsored International Conference on Microwave Integrated Circuits, Photonics and Wireless Networks (IMICPW)•May 1, 2019•1 citation

Hardware Architecture for List Successive Cancellation Decoding of Polar Codes

Alexios Balatsoukas‐Stimming, Alexandre J. Raymond, Warren J. Gross +1 more

This brief presents a hardware architecture and algorithmic improvements for list successive cancellation (SC) decoding of polar codes. More specifically, we show how to completely avoid copying of the likelihoods, which is algorithmically the most cumbersome part of list SC decoding. The hardware architecture was synthesized for a block length of N=1024 bits and list sizes L=2, 4 using a UMC 90 nm VLSI technology. The resulting decoder can achieve a coded throughput of 181 Mb/s at a frequency of 459 MHz.

IEEE Transactions on Circuits & Systems II Express Briefs•May 29, 2014•124 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

Efficient Partial Sum Architecture and Memory Reduction Method for SC-Flip Polar Decoder

Jae Hong Roh, Useok Lee, Yongje Lee +1 more

To improve the error correction performance of successive cancellation (SC) decoding of polar codes, SC-flip (SCF) decoding was proposed. However, it requires large additional memory to save the decoding history for hardware implementation. This paper proposes a partial sum (PS) memory reduction method and a PS architecture for SCF decoders. We analyze the fractal structure of the generator matrix and propose a logic circuit to decide the corresponding row of the generator matrix for an arbitrary bit-index. The proposed design was implemented on the Xilinx Virtex-7 FPGA, which can reduce the number of flip-flops by up to 47% and the PS history memory size by 94% compared to other PS architectures.

International SoC Design Conference•Oct 6, 2021•0 citations

Low-Latency Successive-Cancellation List Decoders for Polar Codes With Multibit Decision

Bo Yuan, Keshab K. Parhi

Polar codes, as the first provable capacity-achieving error-correcting codes, have received much attention in recent years. However, the decoding performance of polar codes with traditional successive-cancellation (SC) algorithm cannot match that of the low-density parity-check or Turbo codes. Because SC list (SCL) decoding algorithm can significantly improve the error-correcting performance of polar codes, design of SCL decoders is important for polar codes to be deployed in practical applications. However, because the prior latency reduction approaches for SC decoders are not applicable for SCL decoders, these list decoders suffer from the long-latency bottleneck. In this paper, we propose a multibit-decision approach that can significantly reduce latency of SCL decoders. First, we present a reformulated SCL algorithm that can perform intermediate decoding of 2 b together. The proposed approach, referred as 2-bit reformulated SCL (2b-rSCL) algorithm, can reduce the latency of SCL decoder from (3n-2) to (2n-2) clock cycles without any performance loss. Then, we extend the idea of 2-b-decision to general case, and propose a general decoding scheme that can perform intermediate decoding of any 2Kbits simultaneously. This general approach, referred as 2K-bit reformulated SCL (2Kb-rSCL) algorithm, can reduce the overall decoding latency to as short as n/2K-2-2 cycles. Furthermore, on the basis of the proposed algorithms, very large-scale integration architectures for 2b-rSCL and 4b-rSCL decoders are synthesized. Compared with a prior SCL decoder, the proposed (1024, 512) 2b-rSCL and 4b-rSCL decoders can achieve 21% and 60% reduction in latency, 1.66 and 2.77 times increase in coded throughput with list size 2, and 2.11 and 3.23 times increase in coded throughput with list size 4, respectively.

arXiv:1406.7036•IEEE Transactions on Very Large Scale Integration (VLSI) Systems•Jan 19, 2015•119 citations

A Hybrid OSD-SC Decoding Algorithm for Polar Codes

Yusheng Xing, Guofang Tu

In this paper, we propose a low complexity hybrid ordered statistics decoding (OSD) successive cancellation (SC) decoding algorithm for the polar codes. By replacing smaller size SC decoder with OSD decoder, we can improve the error correcting performance of the SC algorithm. The size of the OSD decoder can be changed to control the trade-off between the decoding complexity and the error correcting performance of the proposed algorithm. We also provide a method to further simplify the proposed algorithm. Simulation results show that the proposed algorithm offers about 0.3 dB gain comparing to the SC at target bit error rate (BER) 10-5with code length N = 1024, 512,256 and code rate R = 1 /3. The impact of the OSD size is also simulated and analyzed.

IEEE Information Technology, Networking, Electronic and Automation Control Conference (ITNEC)•Mar 1, 2019•4 citations
Although the successive cancelation (SC) algorithm works well for very long polar codes, its error performance for shorter polar codes is much worse. Several SC based list decoding algorithms have been proposed to improve the error performances of both long and short polar codes. A significant step of SC based list decoding algorithms is the updating of partial sums for all decoding paths. In this paper, we first proposed a lazy copy partial sum computation algorithm for SC based list decoding algorithms. Instead of copying partial sums directly, our lazy copy algorithm copies indices of partial sums. Based on our lazy copy algorithm, we propose a hybrid partial sum computation unit architecture, which employs both registers and memories so that the overall area efficiency is improved. Compared with a recent partial sum computation unit for list decoders, when the list size L = 4, our partial sum computation unit achieves an area saving of 23% and 63% for block length 213and 215, respectively.
In order to achieve a magnificent error-correcting performance Successive Cancellation List (SCL) decoding is a powerful and excellent method which considers L decoding paths at each decoding stage concurrently. However, the conventional SCL decoder uses L copies of Successive Cancellation (SC) decoder for a list size of L thereby resulting in a massive increase in the hardware as the list size increases which is one of the major drawbacks of SCL decoder. One more drawback of SCL decoder architecture is the long latency of the architecture. Using the proposed efficient utilization of existing hardware architecture, there is a reduction in the number of Merged Processing Elements (MPE) by 39% for a list size of 2 and 45% for a list size of 4 when compared to the existing architectures and a vast reduction compared to conventional SCL decoder. The partial pipelining considered in this work can reduce the latency compared to conventional SCL multi-bit architecture to a greater extent.
This brief presents a hardware architecture and algorithmic improvements for list successive cancellation (SC) decoding of polar codes. More specifically, we show how to completely avoid copying of the likelihoods, which is algorithmically the most cumbersome part of list SC decoding. The hardware architecture was synthesized for a block length of N=1024 bits and list sizes L=2, 4 using a UMC 90 nm VLSI technology. The resulting decoder can achieve a coded throughput of 181 Mb/s at a frequency of 459 MHz.
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.
To improve the error correction performance of successive cancellation (SC) decoding of polar codes, SC-flip (SCF) decoding was proposed. However, it requires large additional memory to save the decoding history for hardware implementation. This paper proposes a partial sum (PS) memory reduction method and a PS architecture for SCF decoders. We analyze the fractal structure of the generator matrix and propose a logic circuit to decide the corresponding row of the generator matrix for an arbitrary bit-index. The proposed design was implemented on the Xilinx Virtex-7 FPGA, which can reduce the number of flip-flops by up to 47% and the PS history memory size by 94% compared to other PS architectures.
Polar codes, as the first provable capacity-achieving error-correcting codes, have received much attention in recent years. However, the decoding performance of polar codes with traditional successive-cancellation (SC) algorithm cannot match that of the low-density parity-check or Turbo codes. Because SC list (SCL) decoding algorithm can significantly improve the error-correcting performance of polar codes, design of SCL decoders is important for polar codes to be deployed in practical applications. However, because the prior latency reduction approaches for SC decoders are not applicable for SCL decoders, these list decoders suffer from the long-latency bottleneck. In this paper, we propose a multibit-decision approach that can significantly reduce latency of SCL decoders. First, we present a reformulated SCL algorithm that can perform intermediate decoding of 2 b together. The proposed approach, referred as 2-bit reformulated SCL (2b-rSCL) algorithm, can reduce the latency of SCL decoder from (3n-2) to (2n-2) clock cycles without any performance loss. Then, we extend the idea of 2-b-decision to general case, and propose a general decoding scheme that can perform intermediate decoding of any 2Kbits simultaneously. This general approach, referred as 2K-bit reformulated SCL (2Kb-rSCL) algorithm, can reduce the overall decoding latency to as short as n/2K-2-2 cycles. Furthermore, on the basis of the proposed algorithms, very large-scale integration architectures for 2b-rSCL and 4b-rSCL decoders are synthesized. Compared with a prior SCL decoder, the proposed (1024, 512) 2b-rSCL and 4b-rSCL decoders can achieve 21% and 60% reduction in latency, 1.66 and 2.77 times increase in coded throughput with list size 2, and 2.11 and 3.23 times increase in coded throughput with list size 4, respectively.
In this paper, we propose a low complexity hybrid ordered statistics decoding (OSD) successive cancellation (SC) decoding algorithm for the polar codes. By replacing smaller size SC decoder with OSD decoder, we can improve the error correcting performance of the SC algorithm. The size of the OSD decoder can be changed to control the trade-off between the decoding complexity and the error correcting performance of the proposed algorithm. We also provide a method to further simplify the proposed algorithm. Simulation results show that the proposed algorithm offers about 0.3 dB gain comparing to the SC at target bit error rate (BER) 10-5with code length N = 1024, 512,256 and code rate R = 1 /3. The impact of the OSD size is also simulated and analyzed.