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

Research output: Contribution to journalArticle

47 Citations (Scopus)

Abstract

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 2K bits 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.

Original languageEnglish (US)
Article number6920050
Pages (from-to)2268-2280
Number of pages13
JournalIEEE Transactions on Very Large Scale Integration (VLSI) Systems
Volume23
Issue number10
DOIs
StatePublished - Oct 1 2015

Fingerprint

Decoding
Throughput
Turbo codes
VLSI circuits
Clocks

Keywords

  • Algorithm reformulation
  • list decoding
  • multibit decision
  • polar codes
  • Successive cancellation (SC)

Cite this

Low-Latency Successive-Cancellation List Decoders for Polar Codes with Multibit Decision. / Yuan, Bo; Parhi, Keshab K.

In: IEEE Transactions on Very Large Scale Integration (VLSI) Systems, Vol. 23, No. 10, 6920050, 01.10.2015, p. 2268-2280.

Research output: Contribution to journalArticle

@article{52b024b6525e45aeae14f5604cddf1a3,
title = "Low-Latency Successive-Cancellation List Decoders for Polar Codes with Multibit Decision",
abstract = "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 2K bits 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.",
keywords = "Algorithm reformulation, list decoding, multibit decision, polar codes, Successive cancellation (SC)",
author = "Bo Yuan and Parhi, {Keshab K.}",
year = "2015",
month = "10",
day = "1",
doi = "10.1109/TVLSI.2014.2359793",
language = "English (US)",
volume = "23",
pages = "2268--2280",
journal = "IEEE Transactions on Very Large Scale Integration (VLSI) Systems",
issn = "1063-8210",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
number = "10",

}

TY - JOUR

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

AU - Yuan, Bo

AU - Parhi, Keshab K.

PY - 2015/10/1

Y1 - 2015/10/1

N2 - 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 2K bits 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.

AB - 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 2K bits 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.

KW - Algorithm reformulation

KW - list decoding

KW - multibit decision

KW - polar codes

KW - Successive cancellation (SC)

UR - http://www.scopus.com/inward/record.url?scp=84959514530&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84959514530&partnerID=8YFLogxK

U2 - 10.1109/TVLSI.2014.2359793

DO - 10.1109/TVLSI.2014.2359793

M3 - Article

VL - 23

SP - 2268

EP - 2280

JO - IEEE Transactions on Very Large Scale Integration (VLSI) Systems

JF - IEEE Transactions on Very Large Scale Integration (VLSI) Systems

SN - 1063-8210

IS - 10

M1 - 6920050

ER -