---
res:
bibo_abstract:
- 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.@eng
bibo_authorlist:
- foaf_Person:
foaf_givenName: Marco
foaf_name: Mondelli, Marco
foaf_surname: Mondelli
foaf_workInfoHomepage: http://www.librecat.org/personId=27EB676C-8706-11E9-9510-7717E6697425
orcid: 0000-0002-3242-7020
- foaf_Person:
foaf_givenName: S. Hamed
foaf_name: Hassani, S. Hamed
foaf_surname: Hassani
- foaf_Person:
foaf_givenName: Rudiger
foaf_name: Urbanke, Rudiger
foaf_surname: Urbanke
bibo_doi: 10.1109/isit.2017.8006850
dct_date: 2017^xs_gYear
dct_isPartOf:
- http://id.crossref.org/issn/2157-8117
- http://id.crossref.org/issn/9781509040964
dct_language: eng
dct_publisher: IEEE@
dct_title: Construction of polar codes with sublinear complexity@
...