Fast Successive-Cancellation Decoding of Polar Codes with Sequence Nodes Article Swipe
Yang Lu
,
Minjian Zhao
,
Ming Lei
,
Minjian Zhao
·
YOU?
·
· 2022
· Open Access
·
· DOI: https://doi.org/10.48550/arxiv.2204.12115
YOU?
·
· 2022
· Open Access
·
· DOI: https://doi.org/10.48550/arxiv.2204.12115
Due to the sequential nature of the successive-cancellation (SC) algorithm, the decoding of polar codes suffers from significant decoding latencies. Fast SC decoding is able to speed up the SC decoding process, by implementing parallel decoders at the intermediate levels of the SC decoding tree for some special nodes with specific information and frozen bit patterns. To further improve the parallelism of SC decoding, this paper present a new class of special nodes composed of a sequence of rate one or single-parity-check (SR1/SPC) nodes, which can be easily found especially in high-rate polar code and is able to envelop a wide variety of existing special node types. Then, we analyse the parity constraints caused by the frozen bits in each descendant node, such that the decoding performance of the SR1/SPC node can be preserved once the parity constraints are satisfied. Finally, a generalized fast decoding algorithm is proposed to decode SR1/SPC nodes efficiently, where the corresponding parity constraints are taken into consideration. Simulation results show that the proposed decoding algorithm of the SR1/SPC node can achieve near-ML performance, and the overall decoding latency can be reduced by 43.8% as compared to the state-of-the-art fast SC decoder.
Related Topics
Concepts
Decoding methods
Computer science
Sequential decoding
List decoding
Algorithm
Node (physics)
Parity bit
Low-density parity-check code
Concatenated error correction code
Block code
Physics
Quantum mechanics
Metadata
- Type
- preprint
- Language
- en
- Landing Page
- http://arxiv.org/abs/2204.12115
- https://arxiv.org/pdf/2204.12115
- OA Status
- green
- Related Works
- 10
- OpenAlex ID
- https://openalex.org/W4224988900
All OpenAlex metadata
Raw OpenAlex JSON
- OpenAlex ID
-
https://openalex.org/W4224988900Canonical identifier for this work in OpenAlex
- DOI
-
https://doi.org/10.48550/arxiv.2204.12115Digital Object Identifier
- Title
-
Fast Successive-Cancellation Decoding of Polar Codes with Sequence NodesWork title
- Type
-
preprintOpenAlex work type
- Language
-
enPrimary language
- Publication year
-
2022Year of publication
- Publication date
-
2022-04-26Full publication date if available
- Authors
-
Yang Lu, Minjian Zhao, Ming Lei, Minjian ZhaoList of authors in order
- Landing page
-
https://arxiv.org/abs/2204.12115Publisher landing page
- PDF URL
-
https://arxiv.org/pdf/2204.12115Direct link to full text PDF
- Open access
-
YesWhether a free full text is available
- OA status
-
greenOpen access status per OpenAlex
- OA URL
-
https://arxiv.org/pdf/2204.12115Direct OA link when available
- Concepts
-
Decoding methods, Computer science, Sequential decoding, List decoding, Algorithm, Node (physics), Parity bit, Low-density parity-check code, Concatenated error correction code, Block code, Physics, Quantum mechanicsTop concepts (fields/topics) attached by OpenAlex
- Cited by
-
0Total citation count in OpenAlex
- Related works (count)
-
10Other works algorithmically related by OpenAlex
Full payload
| id | https://openalex.org/W4224988900 |
|---|---|
| doi | https://doi.org/10.48550/arxiv.2204.12115 |
| ids.doi | https://doi.org/10.48550/arxiv.2204.12115 |
| ids.openalex | https://openalex.org/W4224988900 |
| fwci | |
| type | preprint |
| title | Fast Successive-Cancellation Decoding of Polar Codes with Sequence Nodes |
| 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.9979000091552734 |
| 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.992900013923645 |
| 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/T10125 |
| topics[2].field.id | https://openalex.org/fields/22 |
| topics[2].field.display_name | Engineering |
| topics[2].score | 0.9613000154495239 |
| topics[2].domain.id | https://openalex.org/domains/3 |
| topics[2].domain.display_name | Physical Sciences |
| topics[2].subfield.id | https://openalex.org/subfields/2208 |
| topics[2].subfield.display_name | Electrical and Electronic Engineering |
| topics[2].display_name | Advanced Wireless Communication Techniques |
| is_xpac | False |
| apc_list | |
| apc_paid | |
| concepts[0].id | https://openalex.org/C57273362 |
| concepts[0].level | 2 |
| concepts[0].score | 0.8851706981658936 |
| concepts[0].wikidata | https://www.wikidata.org/wiki/Q576722 |
| concepts[0].display_name | Decoding methods |
| concepts[1].id | https://openalex.org/C41008148 |
| concepts[1].level | 0 |
| concepts[1].score | 0.6927638053894043 |
| concepts[1].wikidata | https://www.wikidata.org/wiki/Q21198 |
| concepts[1].display_name | Computer science |
| concepts[2].id | https://openalex.org/C193969084 |
| concepts[2].level | 4 |
| concepts[2].score | 0.6827993392944336 |
| concepts[2].wikidata | https://www.wikidata.org/wiki/Q7452500 |
| concepts[2].display_name | Sequential decoding |
| concepts[3].id | https://openalex.org/C204397858 |
| concepts[3].level | 5 |
| concepts[3].score | 0.6351040005683899 |
| concepts[3].wikidata | https://www.wikidata.org/wiki/Q4437907 |
| concepts[3].display_name | List decoding |
| concepts[4].id | https://openalex.org/C11413529 |
| concepts[4].level | 1 |
| concepts[4].score | 0.6154776811599731 |
| concepts[4].wikidata | https://www.wikidata.org/wiki/Q8366 |
| concepts[4].display_name | Algorithm |
| concepts[5].id | https://openalex.org/C62611344 |
| concepts[5].level | 2 |
| concepts[5].score | 0.5715727806091309 |
| concepts[5].wikidata | https://www.wikidata.org/wiki/Q1062658 |
| concepts[5].display_name | Node (physics) |
| concepts[6].id | https://openalex.org/C131521367 |
| concepts[6].level | 2 |
| concepts[6].score | 0.45573362708091736 |
| concepts[6].wikidata | https://www.wikidata.org/wiki/Q625502 |
| concepts[6].display_name | Parity bit |
| concepts[7].id | https://openalex.org/C67692717 |
| concepts[7].level | 3 |
| concepts[7].score | 0.42186951637268066 |
| concepts[7].wikidata | https://www.wikidata.org/wiki/Q187444 |
| concepts[7].display_name | Low-density parity-check code |
| concepts[8].id | https://openalex.org/C78944582 |
| concepts[8].level | 4 |
| concepts[8].score | 0.141808420419693 |
| concepts[8].wikidata | https://www.wikidata.org/wiki/Q5158264 |
| concepts[8].display_name | Concatenated error correction code |
| concepts[9].id | https://openalex.org/C157125643 |
| concepts[9].level | 3 |
| concepts[9].score | 0.1093742847442627 |
| concepts[9].wikidata | https://www.wikidata.org/wiki/Q884707 |
| concepts[9].display_name | Block code |
| concepts[10].id | https://openalex.org/C121332964 |
| concepts[10].level | 0 |
| concepts[10].score | 0.05896538496017456 |
| concepts[10].wikidata | https://www.wikidata.org/wiki/Q413 |
| concepts[10].display_name | Physics |
| concepts[11].id | https://openalex.org/C62520636 |
| concepts[11].level | 1 |
| concepts[11].score | 0.0 |
| concepts[11].wikidata | https://www.wikidata.org/wiki/Q944 |
| concepts[11].display_name | Quantum mechanics |
| keywords[0].id | https://openalex.org/keywords/decoding-methods |
| keywords[0].score | 0.8851706981658936 |
| keywords[0].display_name | Decoding methods |
| keywords[1].id | https://openalex.org/keywords/computer-science |
| keywords[1].score | 0.6927638053894043 |
| keywords[1].display_name | Computer science |
| keywords[2].id | https://openalex.org/keywords/sequential-decoding |
| keywords[2].score | 0.6827993392944336 |
| keywords[2].display_name | Sequential decoding |
| keywords[3].id | https://openalex.org/keywords/list-decoding |
| keywords[3].score | 0.6351040005683899 |
| keywords[3].display_name | List decoding |
| keywords[4].id | https://openalex.org/keywords/algorithm |
| keywords[4].score | 0.6154776811599731 |
| keywords[4].display_name | Algorithm |
| keywords[5].id | https://openalex.org/keywords/node |
| keywords[5].score | 0.5715727806091309 |
| keywords[5].display_name | Node (physics) |
| keywords[6].id | https://openalex.org/keywords/parity-bit |
| keywords[6].score | 0.45573362708091736 |
| keywords[6].display_name | Parity bit |
| keywords[7].id | https://openalex.org/keywords/low-density-parity-check-code |
| keywords[7].score | 0.42186951637268066 |
| keywords[7].display_name | Low-density parity-check code |
| keywords[8].id | https://openalex.org/keywords/concatenated-error-correction-code |
| keywords[8].score | 0.141808420419693 |
| keywords[8].display_name | Concatenated error correction code |
| keywords[9].id | https://openalex.org/keywords/block-code |
| keywords[9].score | 0.1093742847442627 |
| keywords[9].display_name | Block code |
| keywords[10].id | https://openalex.org/keywords/physics |
| keywords[10].score | 0.05896538496017456 |
| keywords[10].display_name | Physics |
| language | en |
| locations[0].id | pmh:oai:arXiv.org:2204.12115 |
| 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/2204.12115 |
| 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/2204.12115 |
| locations[1].id | doi:10.48550/arxiv.2204.12115 |
| 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.2204.12115 |
| 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/A5013642287 |
| authorships[2].author.orcid | https://orcid.org/0000-0003-4696-9346 |
| 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/2204.12115 |
| open_access.oa_status | green |
| open_access.any_repository_has_fulltext | False |
| created_date | 2025-10-10T00:00:00 |
| display_name | Fast Successive-Cancellation Decoding of Polar Codes with Sequence Nodes |
| 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.9979000091552734 |
| 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:2204.12115 |
| 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/2204.12115 |
| 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/2204.12115 |
| primary_location.id | pmh:oai:arXiv.org:2204.12115 |
| 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/2204.12115 |
| 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/2204.12115 |
| publication_date | 2022-04-26 |
| publication_year | 2022 |
| referenced_works_count | 0 |
| abstract_inverted_index.a | 67, 75, 99, 141 |
| abstract_inverted_index.SC | 21, 29, 42, 62, 194 |
| abstract_inverted_index.To | 56 |
| abstract_inverted_index.as | 188 |
| abstract_inverted_index.at | 36 |
| abstract_inverted_index.be | 86, 132, 184 |
| abstract_inverted_index.by | 32, 114, 186 |
| abstract_inverted_index.in | 90, 118 |
| abstract_inverted_index.is | 23, 95, 146 |
| abstract_inverted_index.of | 5, 12, 40, 61, 70, 74, 77, 102, 127, 170 |
| abstract_inverted_index.or | 80 |
| abstract_inverted_index.to | 1, 25, 97, 148, 190 |
| abstract_inverted_index.up | 27 |
| abstract_inverted_index.we | 108 |
| abstract_inverted_index.Due | 0 |
| abstract_inverted_index.and | 52, 94, 178 |
| abstract_inverted_index.are | 138, 158 |
| abstract_inverted_index.bit | 54 |
| abstract_inverted_index.can | 85, 131, 174, 183 |
| abstract_inverted_index.for | 45 |
| abstract_inverted_index.new | 68 |
| abstract_inverted_index.one | 79 |
| abstract_inverted_index.the | 2, 6, 10, 28, 37, 41, 59, 110, 115, 124, 128, 135, 154, 166, 171, 179, 191 |
| abstract_inverted_index.(SC) | 8 |
| abstract_inverted_index.Fast | 20 |
| abstract_inverted_index.able | 24, 96 |
| abstract_inverted_index.bits | 117 |
| abstract_inverted_index.code | 93 |
| abstract_inverted_index.each | 119 |
| abstract_inverted_index.fast | 143, 193 |
| abstract_inverted_index.from | 16 |
| abstract_inverted_index.into | 160 |
| abstract_inverted_index.node | 105, 130, 173 |
| abstract_inverted_index.once | 134 |
| abstract_inverted_index.rate | 78 |
| abstract_inverted_index.show | 164 |
| abstract_inverted_index.some | 46 |
| abstract_inverted_index.such | 122 |
| abstract_inverted_index.that | 123, 165 |
| abstract_inverted_index.this | 64 |
| abstract_inverted_index.tree | 44 |
| abstract_inverted_index.wide | 100 |
| abstract_inverted_index.with | 49 |
| abstract_inverted_index.43.8% | 187 |
| abstract_inverted_index.Then, | 107 |
| abstract_inverted_index.class | 69 |
| abstract_inverted_index.codes | 14 |
| abstract_inverted_index.found | 88 |
| abstract_inverted_index.node, | 121 |
| abstract_inverted_index.nodes | 48, 72, 151 |
| abstract_inverted_index.paper | 65 |
| abstract_inverted_index.polar | 13, 92 |
| abstract_inverted_index.speed | 26 |
| abstract_inverted_index.taken | 159 |
| abstract_inverted_index.where | 153 |
| abstract_inverted_index.which | 84 |
| abstract_inverted_index.caused | 113 |
| abstract_inverted_index.decode | 149 |
| abstract_inverted_index.easily | 87 |
| abstract_inverted_index.frozen | 53, 116 |
| abstract_inverted_index.levels | 39 |
| abstract_inverted_index.nature | 4 |
| abstract_inverted_index.nodes, | 83 |
| abstract_inverted_index.parity | 111, 136, 156 |
| abstract_inverted_index.types. | 106 |
| abstract_inverted_index.SR1/SPC | 129, 150, 172 |
| abstract_inverted_index.achieve | 175 |
| abstract_inverted_index.analyse | 109 |
| abstract_inverted_index.envelop | 98 |
| abstract_inverted_index.further | 57 |
| abstract_inverted_index.improve | 58 |
| abstract_inverted_index.latency | 182 |
| abstract_inverted_index.near-ML | 176 |
| abstract_inverted_index.overall | 180 |
| abstract_inverted_index.present | 66 |
| abstract_inverted_index.reduced | 185 |
| abstract_inverted_index.results | 163 |
| abstract_inverted_index.special | 47, 71, 104 |
| abstract_inverted_index.suffers | 15 |
| abstract_inverted_index.variety | 101 |
| abstract_inverted_index.Finally, | 140 |
| abstract_inverted_index.compared | 189 |
| abstract_inverted_index.composed | 73 |
| abstract_inverted_index.decoder. | 195 |
| abstract_inverted_index.decoders | 35 |
| abstract_inverted_index.decoding | 11, 18, 22, 30, 43, 125, 144, 168, 181 |
| abstract_inverted_index.existing | 103 |
| abstract_inverted_index.parallel | 34 |
| abstract_inverted_index.process, | 31 |
| abstract_inverted_index.proposed | 147, 167 |
| abstract_inverted_index.sequence | 76 |
| abstract_inverted_index.specific | 50 |
| abstract_inverted_index.(SR1/SPC) | 82 |
| abstract_inverted_index.algorithm | 145, 169 |
| abstract_inverted_index.decoding, | 63 |
| abstract_inverted_index.high-rate | 91 |
| abstract_inverted_index.patterns. | 55 |
| abstract_inverted_index.preserved | 133 |
| abstract_inverted_index.Simulation | 162 |
| abstract_inverted_index.algorithm, | 9 |
| abstract_inverted_index.descendant | 120 |
| abstract_inverted_index.especially | 89 |
| abstract_inverted_index.latencies. | 19 |
| abstract_inverted_index.satisfied. | 139 |
| abstract_inverted_index.sequential | 3 |
| abstract_inverted_index.constraints | 112, 137, 157 |
| abstract_inverted_index.generalized | 142 |
| abstract_inverted_index.information | 51 |
| abstract_inverted_index.parallelism | 60 |
| abstract_inverted_index.performance | 126 |
| abstract_inverted_index.significant | 17 |
| abstract_inverted_index.efficiently, | 152 |
| abstract_inverted_index.implementing | 33 |
| abstract_inverted_index.intermediate | 38 |
| abstract_inverted_index.performance, | 177 |
| abstract_inverted_index.corresponding | 155 |
| abstract_inverted_index.consideration. | 161 |
| abstract_inverted_index.state-of-the-art | 192 |
| abstract_inverted_index.single-parity-check | 81 |
| abstract_inverted_index.successive-cancellation | 7 |
| cited_by_percentile_year | |
| countries_distinct_count | 0 |
| institutions_distinct_count | 4 |
| citation_normalized_percentile |