Fast List Decoding of High-Rate Polar Codes Article Swipe

PDF

Yang Lu , Minjian Zhao , Ming Lei , Minjian Zhao ·

YOU? · · 2023 · Open Access · · DOI: https://doi.org/10.48550/arxiv.2311.08188

Due to the ability to provide superior error-correction performance, the successive cancellation list (SCL) algorithm is widely regarded as one of the most promising decoding algorithms for polar codes with short-to-moderate code lengths. However, the application of SCL decoding in low-latency communication scenarios is limited due to its sequential nature. To reduce the decoding latency, developing tailored fast and efficient list decoding algorithms of specific polar substituent codes (special nodes) is a promising solution. Recently, fast list decoding algorithms are proposed by considering special nodes with low code rates. Aiming to further speedup the SCL decoding, this paper presents fast list decoding algorithms for two types of high-rate special nodes, namely single-parity-check (SPC) nodes and sequence rate one or single-parity-check (SR1/SPC) nodes. In particular, we develop two classes of fast list decoding algorithms for these nodes, where the first class uses a sequential decoding procedure to yield decoding latency that is linear with the list size, and the second further parallelizes the decoding process by pre-determining the redundant candidate paths offline. Simulation results show that the proposed list decoding algorithms are able to achieve up to 70.7\% lower decoding latency than state-of-the-art fast SCL decoders, while exhibiting the same error-correction performance.

Related Topics

Computer Science

Algorithm

Concepts

Decoding methods List decoding Computer science Sequential decoding Algorithm Concatenated error correction code Block code

Metadata

Type: preprint
Language: en
Landing Page: http://arxiv.org/abs/2311.08188
PDF: https://arxiv.org/pdf/2311.08188
OA Status: green
Related Works: 10
OpenAlex ID: https://openalex.org/W4388717266

All OpenAlex metadata

Raw OpenAlex JSON

OpenAlex ID: https://openalex.org/W4388717266

Canonical identifier for this work in OpenAlex
DOI: https://doi.org/10.48550/arxiv.2311.08188

Digital Object Identifier
Title: Fast List Decoding of High-Rate Polar Codes

Work title
Type: preprint

OpenAlex work type
Language: en

Primary language
Publication year: 2023

Year of publication
Publication date: 2023-11-14

Full publication date if available
Authors: Yang Lu, Minjian Zhao, Ming Lei, Minjian Zhao

List of authors in order
Landing page: https://arxiv.org/abs/2311.08188

Publisher landing page
PDF URL: https://arxiv.org/pdf/2311.08188

Direct link to full text PDF
Open access: Yes

Whether a free full text is available
OA status: green

Open access status per OpenAlex
OA URL: https://arxiv.org/pdf/2311.08188

Direct OA link when available
Concepts: Decoding methods, List decoding, Computer science, Sequential decoding, Algorithm, Concatenated error correction code, Block code

Top concepts (fields/topics) attached by OpenAlex
Cited by: 0

Total citation count in OpenAlex
Related works (count): 10

Other works algorithmically related by OpenAlex

Full payload

id	https://openalex.org/W4388717266
doi	https://doi.org/10.48550/arxiv.2311.08188
ids.doi	https://doi.org/10.48550/arxiv.2311.08188
ids.openalex	https://openalex.org/W4388717266
fwci
type	preprint
title	Fast List Decoding of High-Rate Polar Codes
biblio.issue
biblio.volume
biblio.last_page
biblio.first_page
topics[0].id	https://openalex.org/T11321
topics[0].field.id	https://openalex.org/fields/17
topics[0].field.display_name	Computer Science
topics[0].score	0.9954000115394592
topics[0].domain.id	https://openalex.org/domains/3
topics[0].domain.display_name	Physical Sciences
topics[0].subfield.id	https://openalex.org/subfields/1705
topics[0].subfield.display_name	Computer Networks and Communications
topics[0].display_name	Error Correcting Code Techniques
topics[1].id	https://openalex.org/T11130
topics[1].field.id	https://openalex.org/fields/17
topics[1].field.display_name	Computer Science
topics[1].score	0.9900000095367432
topics[1].domain.id	https://openalex.org/domains/3
topics[1].domain.display_name	Physical Sciences
topics[1].subfield.id	https://openalex.org/subfields/1702
topics[1].subfield.display_name	Artificial Intelligence
topics[1].display_name	Coding theory and cryptography
topics[2].id	https://openalex.org/T12029
topics[2].field.id	https://openalex.org/fields/13
topics[2].field.display_name	Biochemistry, Genetics and Molecular Biology
topics[2].score	0.978600025177002
topics[2].domain.id	https://openalex.org/domains/1
topics[2].domain.display_name	Life Sciences
topics[2].subfield.id	https://openalex.org/subfields/1312
topics[2].subfield.display_name	Molecular Biology
topics[2].display_name	DNA and Biological Computing
is_xpac	False
apc_list
apc_paid
concepts[0].id	https://openalex.org/C57273362
concepts[0].level	2
concepts[0].score	0.8824399709701538
concepts[0].wikidata	https://www.wikidata.org/wiki/Q576722
concepts[0].display_name	Decoding methods
concepts[1].id	https://openalex.org/C204397858
concepts[1].level	5
concepts[1].score	0.8164311051368713
concepts[1].wikidata	https://www.wikidata.org/wiki/Q4437907
concepts[1].display_name	List decoding
concepts[2].id	https://openalex.org/C41008148
concepts[2].level	0
concepts[2].score	0.7563459873199463
concepts[2].wikidata	https://www.wikidata.org/wiki/Q21198
concepts[2].display_name	Computer science
concepts[3].id	https://openalex.org/C193969084
concepts[3].level	4
concepts[3].score	0.7561022639274597
concepts[3].wikidata	https://www.wikidata.org/wiki/Q7452500
concepts[3].display_name	Sequential decoding
concepts[4].id	https://openalex.org/C11413529
concepts[4].level	1
concepts[4].score	0.6027580499649048
concepts[4].wikidata	https://www.wikidata.org/wiki/Q8366
concepts[4].display_name	Algorithm
concepts[5].id	https://openalex.org/C78944582
concepts[5].level	4
concepts[5].score	0.24262264370918274
concepts[5].wikidata	https://www.wikidata.org/wiki/Q5158264
concepts[5].display_name	Concatenated error correction code
concepts[6].id	https://openalex.org/C157125643
concepts[6].level	3
concepts[6].score	0.07996094226837158
concepts[6].wikidata	https://www.wikidata.org/wiki/Q884707
concepts[6].display_name	Block code
keywords[0].id	https://openalex.org/keywords/decoding-methods
keywords[0].score	0.8824399709701538
keywords[0].display_name	Decoding methods
keywords[1].id	https://openalex.org/keywords/list-decoding
keywords[1].score	0.8164311051368713
keywords[1].display_name	List decoding
keywords[2].id	https://openalex.org/keywords/computer-science
keywords[2].score	0.7563459873199463
keywords[2].display_name	Computer science
keywords[3].id	https://openalex.org/keywords/sequential-decoding
keywords[3].score	0.7561022639274597
keywords[3].display_name	Sequential decoding
keywords[4].id	https://openalex.org/keywords/algorithm
keywords[4].score	0.6027580499649048
keywords[4].display_name	Algorithm
keywords[5].id	https://openalex.org/keywords/concatenated-error-correction-code
keywords[5].score	0.24262264370918274
keywords[5].display_name	Concatenated error correction code
keywords[6].id	https://openalex.org/keywords/block-code
keywords[6].score	0.07996094226837158
keywords[6].display_name	Block code
language	en
locations[0].id	pmh:oai:arXiv.org:2311.08188
locations[0].is_oa	True
locations[0].source.id	https://openalex.org/S4306400194
locations[0].source.issn
locations[0].source.type	repository
locations[0].source.is_oa	True
locations[0].source.issn_l
locations[0].source.is_core	False
locations[0].source.is_in_doaj	False
locations[0].source.display_name	arXiv (Cornell University)
locations[0].source.host_organization	https://openalex.org/I205783295
locations[0].source.host_organization_name	Cornell University
locations[0].source.host_organization_lineage	https://openalex.org/I205783295
locations[0].license
locations[0].pdf_url	https://arxiv.org/pdf/2311.08188
locations[0].version	submittedVersion
locations[0].raw_type	text
locations[0].license_id
locations[0].is_accepted	False
locations[0].is_published	False
locations[0].raw_source_name
locations[0].landing_page_url	http://arxiv.org/abs/2311.08188
locations[1].id	doi:10.48550/arxiv.2311.08188
locations[1].is_oa	True
locations[1].source.id	https://openalex.org/S4306400194
locations[1].source.issn
locations[1].source.type	repository
locations[1].source.is_oa	True
locations[1].source.issn_l
locations[1].source.is_core	False
locations[1].source.is_in_doaj	False
locations[1].source.display_name	arXiv (Cornell University)
locations[1].source.host_organization	https://openalex.org/I205783295
locations[1].source.host_organization_name	Cornell University
locations[1].source.host_organization_lineage	https://openalex.org/I205783295
locations[1].license
locations[1].pdf_url
locations[1].version
locations[1].raw_type	article
locations[1].license_id
locations[1].is_accepted	False
locations[1].is_published
locations[1].raw_source_name
locations[1].landing_page_url	https://doi.org/10.48550/arxiv.2311.08188
indexed_in	arxiv, datacite
authorships[0].author.id	https://openalex.org/A5100454255
authorships[0].author.orcid	https://orcid.org/0000-0002-3580-3255
authorships[0].author.display_name	Yang Lu
authorships[0].author_position	first
authorships[0].raw_author_name	Lu, Yang
authorships[0].is_corresponding	False
authorships[1].author.id	https://openalex.org/A5071265062
authorships[1].author.orcid
authorships[1].author.display_name	Minjian Zhao
authorships[1].author_position	middle
authorships[1].raw_author_name	Zhao, Ming-Min
authorships[1].is_corresponding	False
authorships[2].author.id	https://openalex.org/A5101490865
authorships[2].author.orcid	https://orcid.org/0000-0002-1751-1646
authorships[2].author.display_name	Ming Lei
authorships[2].author_position	middle
authorships[2].raw_author_name	Lei, Ming
authorships[2].is_corresponding	False
authorships[3].author.id	https://openalex.org/A5071265062
authorships[3].author.orcid
authorships[3].author.display_name	Minjian Zhao
authorships[3].author_position	last
authorships[3].raw_author_name	Zhao, Min-Jian
authorships[3].is_corresponding	False
has_content.pdf	True
has_content.grobid_xml	True
is_paratext	False
open_access.is_oa	True
open_access.oa_url	https://arxiv.org/pdf/2311.08188
open_access.oa_status	green
open_access.any_repository_has_fulltext	False
created_date	2025-10-10T00:00:00
display_name	Fast List Decoding of High-Rate Polar Codes
has_fulltext	True
is_retracted	False
updated_date	2025-11-06T06:51:31.235846
primary_topic.id	https://openalex.org/T11321
primary_topic.field.id	https://openalex.org/fields/17
primary_topic.field.display_name	Computer Science
primary_topic.score	0.9954000115394592
primary_topic.domain.id	https://openalex.org/domains/3
primary_topic.domain.display_name	Physical Sciences
primary_topic.subfield.id	https://openalex.org/subfields/1705
primary_topic.subfield.display_name	Computer Networks and Communications
primary_topic.display_name	Error Correcting Code Techniques
related_works	https://openalex.org/W3017203753, https://openalex.org/W4205451769, https://openalex.org/W2385322349, https://openalex.org/W2348545647, https://openalex.org/W2052976169, https://openalex.org/W2369600518, https://openalex.org/W2029144766, https://openalex.org/W2089275957, https://openalex.org/W2165241191, https://openalex.org/W2964031101
cited_by_count	0
locations_count	2
best_oa_location.id	pmh:oai:arXiv.org:2311.08188
best_oa_location.is_oa	True
best_oa_location.source.id	https://openalex.org/S4306400194
best_oa_location.source.issn
best_oa_location.source.type	repository
best_oa_location.source.is_oa	True
best_oa_location.source.issn_l
best_oa_location.source.is_core	False
best_oa_location.source.is_in_doaj	False
best_oa_location.source.display_name	arXiv (Cornell University)
best_oa_location.source.host_organization	https://openalex.org/I205783295
best_oa_location.source.host_organization_name	Cornell University
best_oa_location.source.host_organization_lineage	https://openalex.org/I205783295
best_oa_location.license
best_oa_location.pdf_url	https://arxiv.org/pdf/2311.08188
best_oa_location.version	submittedVersion
best_oa_location.raw_type	text
best_oa_location.license_id
best_oa_location.is_accepted	False
best_oa_location.is_published	False
best_oa_location.raw_source_name
best_oa_location.landing_page_url	http://arxiv.org/abs/2311.08188
primary_location.id	pmh:oai:arXiv.org:2311.08188
primary_location.is_oa	True
primary_location.source.id	https://openalex.org/S4306400194
primary_location.source.issn
primary_location.source.type	repository
primary_location.source.is_oa	True
primary_location.source.issn_l
primary_location.source.is_core	False
primary_location.source.is_in_doaj	False
primary_location.source.display_name	arXiv (Cornell University)
primary_location.source.host_organization	https://openalex.org/I205783295
primary_location.source.host_organization_name	Cornell University
primary_location.source.host_organization_lineage	https://openalex.org/I205783295
primary_location.license
primary_location.pdf_url	https://arxiv.org/pdf/2311.08188
primary_location.version	submittedVersion
primary_location.raw_type	text
primary_location.license_id
primary_location.is_accepted	False
primary_location.is_published	False
primary_location.raw_source_name
primary_location.landing_page_url	http://arxiv.org/abs/2311.08188
publication_date	2023-11-14
publication_year	2023
referenced_works_count	0
abstract_inverted_index.a	71, 141
abstract_inverted_index.In	122
abstract_inverted_index.To	50
abstract_inverted_index.as	18
abstract_inverted_index.by	81, 164
abstract_inverted_index.in	39
abstract_inverted_index.is	15, 43, 70, 150
abstract_inverted_index.of	20, 36, 63, 106, 128
abstract_inverted_index.or	118
abstract_inverted_index.to	1, 4, 46, 90, 145, 182, 185
abstract_inverted_index.up	184
abstract_inverted_index.we	124
abstract_inverted_index.Due	0
abstract_inverted_index.SCL	37, 94, 193
abstract_inverted_index.and	58, 114, 156
abstract_inverted_index.are	79, 180
abstract_inverted_index.due	45
abstract_inverted_index.for	26, 103, 133
abstract_inverted_index.its	47
abstract_inverted_index.low	86
abstract_inverted_index.one	19, 117
abstract_inverted_index.the	2, 9, 21, 34, 52, 93, 137, 153, 157, 161, 166, 175, 197
abstract_inverted_index.two	104, 126
abstract_inverted_index.able	181
abstract_inverted_index.code	31, 87
abstract_inverted_index.fast	57, 75, 99, 129, 192
abstract_inverted_index.list	12, 60, 76, 100, 130, 154, 177
abstract_inverted_index.most	22
abstract_inverted_index.rate	116
abstract_inverted_index.same	198
abstract_inverted_index.show	173
abstract_inverted_index.than	190
abstract_inverted_index.that	149, 174
abstract_inverted_index.this	96
abstract_inverted_index.uses	140
abstract_inverted_index.with	29, 85, 152
abstract_inverted_index.(SCL)	13
abstract_inverted_index.(SPC)	112
abstract_inverted_index.class	139
abstract_inverted_index.codes	28, 67
abstract_inverted_index.first	138
abstract_inverted_index.lower	187
abstract_inverted_index.nodes	84, 113
abstract_inverted_index.paper	97
abstract_inverted_index.paths	169
abstract_inverted_index.polar	27, 65
abstract_inverted_index.size,	155
abstract_inverted_index.these	134
abstract_inverted_index.types	105
abstract_inverted_index.where	136
abstract_inverted_index.while	195
abstract_inverted_index.yield	146
abstract_inverted_index.70.7\%	186
abstract_inverted_index.Aiming	89
abstract_inverted_index.linear	151
abstract_inverted_index.namely	110
abstract_inverted_index.nodes)	69
abstract_inverted_index.nodes,	109, 135
abstract_inverted_index.nodes.	121
abstract_inverted_index.rates.	88
abstract_inverted_index.reduce	51
abstract_inverted_index.second	158
abstract_inverted_index.widely	16
abstract_inverted_index.ability	3
abstract_inverted_index.achieve	183
abstract_inverted_index.classes	127
abstract_inverted_index.develop	125
abstract_inverted_index.further	91, 159
abstract_inverted_index.latency	148, 189
abstract_inverted_index.limited	44
abstract_inverted_index.nature.	49
abstract_inverted_index.process	163
abstract_inverted_index.provide	5
abstract_inverted_index.results	172
abstract_inverted_index.special	83, 108
abstract_inverted_index.speedup	92
abstract_inverted_index.(special	68
abstract_inverted_index.However,	33
abstract_inverted_index.decoding	24, 38, 53, 61, 77, 101, 131, 143, 147, 162, 178, 188
abstract_inverted_index.latency,	54
abstract_inverted_index.lengths.	32
abstract_inverted_index.offline.	170
abstract_inverted_index.presents	98
abstract_inverted_index.proposed	80, 176
abstract_inverted_index.regarded	17
abstract_inverted_index.sequence	115
abstract_inverted_index.specific	64
abstract_inverted_index.superior	6
abstract_inverted_index.tailored	56
abstract_inverted_index.(SR1/SPC)	120
abstract_inverted_index.Recently,	74
abstract_inverted_index.algorithm	14
abstract_inverted_index.candidate	168
abstract_inverted_index.decoders,	194
abstract_inverted_index.decoding,	95
abstract_inverted_index.efficient	59
abstract_inverted_index.high-rate	107
abstract_inverted_index.procedure	144
abstract_inverted_index.promising	23, 72
abstract_inverted_index.redundant	167
abstract_inverted_index.scenarios	42
abstract_inverted_index.solution.	73
abstract_inverted_index.Simulation	171
abstract_inverted_index.algorithms	25, 62, 78, 102, 132, 179
abstract_inverted_index.developing	55
abstract_inverted_index.exhibiting	196
abstract_inverted_index.sequential	48, 142
abstract_inverted_index.successive	10
abstract_inverted_index.application	35
abstract_inverted_index.considering	82
abstract_inverted_index.low-latency	40
abstract_inverted_index.particular,	123
abstract_inverted_index.substituent	66
abstract_inverted_index.cancellation	11
abstract_inverted_index.parallelizes	160
abstract_inverted_index.performance,	8
abstract_inverted_index.performance.	200
abstract_inverted_index.communication	41
abstract_inverted_index.pre-determining	165
abstract_inverted_index.error-correction	7, 199
abstract_inverted_index.state-of-the-art	191
abstract_inverted_index.short-to-moderate	30
abstract_inverted_index.single-parity-check	111, 119
cited_by_percentile_year
countries_distinct_count	0
institutions_distinct_count	4
citation_normalized_percentile