---
_id: '10053'
abstract:
- lang: eng
  text: 'This paper characterizes the latency of the simplified successive-cancellation
    (SSC) decoding scheme for polar codes under hardware resource constraints. In
    particular, when the number of processing elements P that can perform SSC decoding
    operations in parallel is limited, as is the case in practice, the latency of
    SSC decoding is O(N1−1 μ+NPlog2log2NP), where N is the block length of the code
    and μ is the scaling exponent of polar codes for the channel. Three direct consequences
    of this bound are presented. First, in a fully-parallel implementation where P=N2
    , the latency of SSC decoding is O(N1−1/μ) , which is sublinear in the block length.
    This recovers a result from an earlier work. Second, in a fully-serial implementation
    where P=1 , the latency of SSC decoding scales as O(Nlog2log2N) . The multiplicative
    constant is also calculated: we show that the latency of SSC decoding when P=1
    is given by (2+o(1))Nlog2log2N . Third, in a semi-parallel implementation, the
    smallest P that gives the same latency as that of the fully-parallel implementation
    is P=N1/μ . The tightness of our bound on SSC decoding latency and the applicability
    of the foregoing results is validated through extensive simulations.'
acknowledgement: "S. A. Hashemi is supported by a Postdoctoral Fellowship from the
  Natural Sciences and Engineering Research Council\r\nof Canada (NSERC) and by Huawei.
  M. Mondelli is partially supported by the 2019 Lopez-Loreta Prize. A. Fazeli and
  A. Vardy were supported in part by the National Science Foundation under Grant CCF-1764104."
article_processing_charge: No
arxiv: 1
author:
- first_name: Seyyed Ali
  full_name: Hashemi, Seyyed Ali
  last_name: Hashemi
- first_name: Marco
  full_name: Mondelli, Marco
  id: 27EB676C-8706-11E9-9510-7717E6697425
  last_name: Mondelli
  orcid: 0000-0002-3242-7020
- first_name: Arman
  full_name: Fazeli, Arman
  last_name: Fazeli
- first_name: Alexander
  full_name: Vardy, Alexander
  last_name: Vardy
- first_name: John
  full_name: Cioffi, John
  last_name: Cioffi
- first_name: Andrea
  full_name: Goldsmith, Andrea
  last_name: Goldsmith
citation:
  ama: 'Hashemi SA, Mondelli M, Fazeli A, Vardy A, Cioffi J, Goldsmith A. Parallelism
    versus latency in simplified successive-cancellation decoding of polar codes.
    In: <i>2021 IEEE International Symposium on Information Theory</i>. Institute
    of Electrical and Electronics Engineers; 2021:2369-2374. doi:<a href="https://doi.org/10.1109/ISIT45174.2021.9518153">10.1109/ISIT45174.2021.9518153</a>'
  apa: 'Hashemi, S. A., Mondelli, M., Fazeli, A., Vardy, A., Cioffi, J., &#38; Goldsmith,
    A. (2021). Parallelism versus latency in simplified successive-cancellation decoding
    of polar codes. In <i>2021 IEEE International Symposium on Information Theory</i>
    (pp. 2369–2374). Melbourne, Australia: Institute of Electrical and Electronics
    Engineers. <a href="https://doi.org/10.1109/ISIT45174.2021.9518153">https://doi.org/10.1109/ISIT45174.2021.9518153</a>'
  chicago: Hashemi, Seyyed Ali, Marco Mondelli, Arman Fazeli, Alexander Vardy, John
    Cioffi, and Andrea Goldsmith. “Parallelism versus Latency in Simplified Successive-Cancellation
    Decoding of Polar Codes.” In <i>2021 IEEE International Symposium on Information
    Theory</i>, 2369–74. Institute of Electrical and Electronics Engineers, 2021.
    <a href="https://doi.org/10.1109/ISIT45174.2021.9518153">https://doi.org/10.1109/ISIT45174.2021.9518153</a>.
  ieee: S. A. Hashemi, M. Mondelli, A. Fazeli, A. Vardy, J. Cioffi, and A. Goldsmith,
    “Parallelism versus latency in simplified successive-cancellation decoding of
    polar codes,” in <i>2021 IEEE International Symposium on Information Theory</i>,
    Melbourne, Australia, 2021, pp. 2369–2374.
  ista: 'Hashemi SA, Mondelli M, Fazeli A, Vardy A, Cioffi J, Goldsmith A. 2021. Parallelism
    versus latency in simplified successive-cancellation decoding of polar codes.
    2021 IEEE International Symposium on Information Theory. ISIT: International Symposium
    on Information Theory, 2369–2374.'
  mla: Hashemi, Seyyed Ali, et al. “Parallelism versus Latency in Simplified Successive-Cancellation
    Decoding of Polar Codes.” <i>2021 IEEE International Symposium on Information
    Theory</i>, Institute of Electrical and Electronics Engineers, 2021, pp. 2369–74,
    doi:<a href="https://doi.org/10.1109/ISIT45174.2021.9518153">10.1109/ISIT45174.2021.9518153</a>.
  short: S.A. Hashemi, M. Mondelli, A. Fazeli, A. Vardy, J. Cioffi, A. Goldsmith,
    in:, 2021 IEEE International Symposium on Information Theory, Institute of Electrical
    and Electronics Engineers, 2021, pp. 2369–2374.
conference:
  end_date: 2021-07-20
  location: Melbourne, Australia
  name: 'ISIT: International Symposium on Information Theory'
  start_date: 2021-07-12
date_created: 2021-09-27T14:33:14Z
date_published: 2021-09-01T00:00:00Z
date_updated: 2024-09-10T13:03:18Z
day: '01'
department:
- _id: MaMo
doi: 10.1109/ISIT45174.2021.9518153
external_id:
  arxiv:
  - '2012.13378'
  isi:
  - '000701502202078'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://arxiv.org/abs/2012.13378
month: '09'
oa: 1
oa_version: Preprint
page: 2369-2374
project:
- _id: 059876FA-7A3F-11EA-A408-12923DDC885E
  name: Prix Lopez-Loretta 2019 - Marco Mondelli
publication: 2021 IEEE International Symposium on Information Theory
publication_identifier:
  eisbn:
  - 978-1-5386-8209-8
  isbn:
  - 978-1-5386-8210-4
  issn:
  - 2157-8095
publication_status: published
publisher: Institute of Electrical and Electronics Engineers
quality_controlled: '1'
related_material:
  record:
  - id: '10364'
    relation: later_version
    status: public
scopus_import: '1'
status: public
title: Parallelism versus latency in simplified successive-cancellation decoding of
  polar codes
type: conference
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
year: '2021'
...
---
_id: '10597'
abstract:
- lang: eng
  text: We thank Emmanuel Abbe and Min Ye for providing us the implementation of RPA
    decoding. D. Fathollahi and M. Mondelli are partially supported by the 2019 Lopez-Loreta
    Prize. N. Farsad is supported by Discovery Grant from the Natural Sciences and
    Engineering Research Council of Canada (NSERC) and Canada Foundation for Innovation
    (CFI), John R. Evans Leader Fund. S. A. Hashemi is supported by a Postdoctoral
    Fellowship from NSERC.
article_processing_charge: No
arxiv: 1
author:
- first_name: Dorsa
  full_name: Fathollahi, Dorsa
  last_name: Fathollahi
- first_name: Nariman
  full_name: Farsad, Nariman
  last_name: Farsad
- first_name: Seyyed Ali
  full_name: Hashemi, Seyyed Ali
  last_name: Hashemi
- first_name: Marco
  full_name: Mondelli, Marco
  id: 27EB676C-8706-11E9-9510-7717E6697425
  last_name: Mondelli
  orcid: 0000-0002-3242-7020
citation:
  ama: 'Fathollahi D, Farsad N, Hashemi SA, Mondelli M. Sparse multi-decoder recursive
    projection aggregation for Reed-Muller codes. In: <i>2021 IEEE International Symposium
    on Information Theory</i>. Institute of Electrical and Electronics Engineers;
    2021:1082-1087. doi:<a href="https://doi.org/10.1109/isit45174.2021.9517887">10.1109/isit45174.2021.9517887</a>'
  apa: 'Fathollahi, D., Farsad, N., Hashemi, S. A., &#38; Mondelli, M. (2021). Sparse
    multi-decoder recursive projection aggregation for Reed-Muller codes. In <i>2021
    IEEE International Symposium on Information Theory</i> (pp. 1082–1087). Virtual,
    Melbourne, Australia: Institute of Electrical and Electronics Engineers. <a href="https://doi.org/10.1109/isit45174.2021.9517887">https://doi.org/10.1109/isit45174.2021.9517887</a>'
  chicago: Fathollahi, Dorsa, Nariman Farsad, Seyyed Ali Hashemi, and Marco Mondelli.
    “Sparse Multi-Decoder Recursive Projection Aggregation for Reed-Muller Codes.”
    In <i>2021 IEEE International Symposium on Information Theory</i>, 1082–87. Institute
    of Electrical and Electronics Engineers, 2021. <a href="https://doi.org/10.1109/isit45174.2021.9517887">https://doi.org/10.1109/isit45174.2021.9517887</a>.
  ieee: D. Fathollahi, N. Farsad, S. A. Hashemi, and M. Mondelli, “Sparse multi-decoder
    recursive projection aggregation for Reed-Muller codes,” in <i>2021 IEEE International
    Symposium on Information Theory</i>, Virtual, Melbourne, Australia, 2021, pp.
    1082–1087.
  ista: 'Fathollahi D, Farsad N, Hashemi SA, Mondelli M. 2021. Sparse multi-decoder
    recursive projection aggregation for Reed-Muller codes. 2021 IEEE International
    Symposium on Information Theory. ISIT: International Symposium on Information
    Theory, 1082–1087.'
  mla: Fathollahi, Dorsa, et al. “Sparse Multi-Decoder Recursive Projection Aggregation
    for Reed-Muller Codes.” <i>2021 IEEE International Symposium on Information Theory</i>,
    Institute of Electrical and Electronics Engineers, 2021, pp. 1082–87, doi:<a href="https://doi.org/10.1109/isit45174.2021.9517887">10.1109/isit45174.2021.9517887</a>.
  short: D. Fathollahi, N. Farsad, S.A. Hashemi, M. Mondelli, in:, 2021 IEEE International
    Symposium on Information Theory, Institute of Electrical and Electronics Engineers,
    2021, pp. 1082–1087.
conference:
  end_date: 2021-07-20
  location: Virtual, Melbourne, Australia
  name: 'ISIT: International Symposium on Information Theory'
  start_date: 2021-07-12
date_created: 2022-01-03T11:31:26Z
date_published: 2021-09-01T00:00:00Z
date_updated: 2024-09-10T13:03:18Z
day: '01'
department:
- _id: MaMo
doi: 10.1109/isit45174.2021.9517887
external_id:
  arxiv:
  - '2011.12882'
  isi:
  - '000701502201029'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://arxiv.org/abs/2011.12882
month: '09'
oa: 1
oa_version: Preprint
page: 1082-1087
project:
- _id: 059876FA-7A3F-11EA-A408-12923DDC885E
  name: Prix Lopez-Loretta 2019 - Marco Mondelli
publication: 2021 IEEE International Symposium on Information Theory
publication_identifier:
  eisbn:
  - 978-1-5386-8209-8
  isbn:
  - 978-1-5386-8210-4
publication_status: published
publisher: Institute of Electrical and Electronics Engineers
quality_controlled: '1'
scopus_import: '1'
status: public
title: Sparse multi-decoder recursive projection aggregation for Reed-Muller codes
type: conference
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
year: '2021'
...