---
_id: '6675'
abstract:
- lang: eng
  text: 'We present a coding paradigm that provides a new achievable rate for the
    primitive relay channel by combining compress-and-forward and decode-and-forward
    with a chaining construction. In the primitive relay channel model, the source
    broadcasts a message to the relay and to the destination; and the relay facilitates
    this communication by sending an additional message to the destination through
    a separate channel. Two well-known coding approaches for this setting are decode-and-forward
    and compress-and-forward: in the former, the relay decodes the message and sends
    some of the information to the destination; in the latter, the relay does not
    attempt to decode, but it sends a compressed description of the received sequence
    to the destination via Wyner-Ziv coding. In our scheme, we transmit over pairs
    of blocks and we use compress-and-forward for the first block and decode-and-forward
    for the second. In particular, in the first block, the relay does not attempt
    to decode and it sends only a part of the compressed description of the received
    sequence; in the second block, the relay decodes the message and sends this information
    plus the remaining part of the compressed sequence relative to the first block.
    As a result, we strictly outperform both compress-and- forward and decode-and-forward.
    Furthermore, this paradigm can be implemented with a low-complexity polar coding
    scheme that has the typical attractive features of polar codes, i.e., quasi-linear
    encoding/decoding complexity and super-polynomial decay of the error probability.
    Throughout the paper we consider as a running example the special case of the
    erasure relay channel and we compare the rates achievable by our proposed scheme
    with the existing upper and lower bounds.'
arxiv: 1
author:
- first_name: Marco
  full_name: Mondelli, Marco
  id: 27EB676C-8706-11E9-9510-7717E6697425
  last_name: Mondelli
  orcid: 0000-0002-3242-7020
- first_name: Hamed
  full_name: Hassani, Hamed
  last_name: Hassani
- first_name: Rudiger
  full_name: Urbanke, Rudiger
  last_name: Urbanke
citation:
  ama: 'Mondelli M, Hassani H, Urbanke R. A new coding paradigm for the primitive
    relay channel. In: <i>2018 IEEE International Symposium on Information Theory</i>.
    IEEE; 2018:351-355. doi:<a href="https://doi.org/10.1109/isit.2018.8437479">10.1109/isit.2018.8437479</a>'
  apa: 'Mondelli, M., Hassani, H., &#38; Urbanke, R. (2018). A new coding paradigm
    for the primitive relay channel. In <i>2018 IEEE International Symposium on Information
    Theory</i> (pp. 351–355). Vail, CO, United States: IEEE. <a href="https://doi.org/10.1109/isit.2018.8437479">https://doi.org/10.1109/isit.2018.8437479</a>'
  chicago: Mondelli, Marco, Hamed Hassani, and Rudiger Urbanke. “A New Coding Paradigm
    for the Primitive Relay Channel.” In <i>2018 IEEE International Symposium on Information
    Theory</i>, 351–55. IEEE, 2018. <a href="https://doi.org/10.1109/isit.2018.8437479">https://doi.org/10.1109/isit.2018.8437479</a>.
  ieee: M. Mondelli, H. Hassani, and R. Urbanke, “A new coding paradigm for the primitive
    relay channel,” in <i>2018 IEEE International Symposium on Information Theory</i>,
    Vail, CO, United States, 2018, pp. 351–355.
  ista: 'Mondelli M, Hassani H, Urbanke R. 2018. A new coding paradigm for the primitive
    relay channel. 2018 IEEE International Symposium on Information Theory. ISIT:
    International Symposium on Information Theory , 351–355.'
  mla: Mondelli, Marco, et al. “A New Coding Paradigm for the Primitive Relay Channel.”
    <i>2018 IEEE International Symposium on Information Theory</i>, IEEE, 2018, pp.
    351–55, doi:<a href="https://doi.org/10.1109/isit.2018.8437479">10.1109/isit.2018.8437479</a>.
  short: M. Mondelli, H. Hassani, R. Urbanke, in:, 2018 IEEE International Symposium
    on Information Theory, IEEE, 2018, pp. 351–355.
conference:
  end_date: 2018-06-22
  location: Vail, CO, United States
  name: 'ISIT: International Symposium on Information Theory '
  start_date: 2018-06-17
date_created: 2019-07-24T09:10:38Z
date_published: 2018-06-16T00:00:00Z
date_updated: 2023-02-23T12:56:49Z
day: '16'
doi: 10.1109/isit.2018.8437479
extern: '1'
external_id:
  arxiv:
  - '1801.03153'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://arxiv.org/abs/1801.03153
month: '06'
oa: 1
oa_version: Preprint
page: 351-355
publication: 2018 IEEE International Symposium on Information Theory
publication_identifier:
  eissn:
  - 2157-8117
publication_status: published
publisher: IEEE
quality_controlled: '1'
related_material:
  record:
  - id: '7007'
    relation: later_version
    status: public
status: public
title: A new coding paradigm for the primitive relay channel
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2018'
...
---
_id: '6729'
abstract:
- lang: eng
  text: Consider the problem of constructing a polar code of block length N for the
    transmission over a given channel W. Typically this requires to compute the reliability
    of all the N synthetic channels and then to include those that are sufficiently
    reliable. However, we know from [1], [2] that there is a partial order among the
    synthetic channels. Hence, it is natural to ask whether we can exploit it to reduce
    the computational burden of the construction problem. We show that, if we take
    advantage of the partial order [1], [2], we can construct a polar code by computing
    the reliability of roughly N/ log 3/2 N synthetic channels. Such a set of synthetic
    channels is universal, in the sense that it allows one to construct polar codes
    for any W, and it can be identified by solving a maximum matching problem on a
    bipartite graph. Our proof technique consists in reducing the construction problem
    to the problem of computing the maximum cardinality of an antichain for a suitable
    partially ordered set. As such, this method is general and it can be used to further
    improve the complexity of the construction problem in case a new partial order
    on the synthetic channels of polar codes is discovered.
arxiv: 1
author:
- first_name: Marco
  full_name: Mondelli, Marco
  id: 27EB676C-8706-11E9-9510-7717E6697425
  last_name: Mondelli
  orcid: 0000-0002-3242-7020
- first_name: S. Hamed
  full_name: Hassani, S. Hamed
  last_name: Hassani
- first_name: Rudiger
  full_name: Urbanke, Rudiger
  last_name: Urbanke
citation:
  ama: 'Mondelli M, Hassani SH, Urbanke R. Construction of polar codes with sublinear
    complexity. In: <i>2017 IEEE International Symposium on Information Theory </i>.
    IEEE; 2017:1853-1857. doi:<a href="https://doi.org/10.1109/isit.2017.8006850">10.1109/isit.2017.8006850</a>'
  apa: 'Mondelli, M., Hassani, S. H., &#38; Urbanke, R. (2017). Construction of polar
    codes with sublinear complexity. In <i>2017 IEEE International Symposium on Information
    Theory </i> (pp. 1853–1857). Aachen, Germany: IEEE. <a href="https://doi.org/10.1109/isit.2017.8006850">https://doi.org/10.1109/isit.2017.8006850</a>'
  chicago: Mondelli, Marco, S. Hamed Hassani, and Rudiger Urbanke. “Construction of
    Polar Codes with Sublinear Complexity.” In <i>2017 IEEE International Symposium
    on Information Theory </i>, 1853–57. IEEE, 2017. <a href="https://doi.org/10.1109/isit.2017.8006850">https://doi.org/10.1109/isit.2017.8006850</a>.
  ieee: M. Mondelli, S. H. Hassani, and R. Urbanke, “Construction of polar codes with
    sublinear complexity,” in <i>2017 IEEE International Symposium on Information
    Theory </i>, Aachen, Germany, 2017, pp. 1853–1857.
  ista: 'Mondelli M, Hassani SH, Urbanke R. 2017. Construction of polar codes with
    sublinear complexity. 2017 IEEE International Symposium on Information Theory
    . ISIT: International Symposium on Information Theory, 1853–1857.'
  mla: Mondelli, Marco, et al. “Construction of Polar Codes with Sublinear Complexity.”
    <i>2017 IEEE International Symposium on Information Theory </i>, IEEE, 2017, pp.
    1853–57, doi:<a href="https://doi.org/10.1109/isit.2017.8006850">10.1109/isit.2017.8006850</a>.
  short: M. Mondelli, S.H. Hassani, R. Urbanke, in:, 2017 IEEE International Symposium
    on Information Theory , IEEE, 2017, pp. 1853–1857.
conference:
  end_date: 2017-06-30
  location: Aachen, Germany
  name: 'ISIT: International Symposium on Information Theory'
  start_date: 2017-06-25
date_created: 2019-07-30T07:14:18Z
date_published: 2017-06-15T00:00:00Z
date_updated: 2023-02-23T12:49:08Z
day: '15'
doi: 10.1109/isit.2017.8006850
extern: '1'
external_id:
  arxiv:
  - '1612.05295'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://arxiv.org/abs/1612.05295
month: '06'
oa: 1
oa_version: Preprint
page: 1853-1857
publication: '2017 IEEE International Symposium on Information Theory '
publication_identifier:
  eissn:
  - 2157-8117
  isbn:
  - '9781509040964'
publication_status: published
publisher: IEEE
quality_controlled: '1'
related_material:
  record:
  - id: '6663'
    relation: later_version
    status: public
status: public
title: Construction of polar codes with sublinear complexity
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2017'
...