|
Contact:
Marcus Greferath
School of Math. Sciences
University College Dublin
Belfield, Dublin 4, Ireland
Phone:
+353-1-716-2588 (UCD)
+353-85-153-0951 (mobile)
Joachim Rosenthal
Institut of Mathematics
University of Zurich
Winterthurerstrasse 190
8057 Zurich, Switzerland
Phone:
+41-44-63 55884 (office)
|
|
ITW 2010 Dublin
IEEE Information Theory Workshop
Dublin, August 30 - September 3, 2010
Polar codes
Tue 31 Aug, 09.55-12.45, Room 1
Invited session
Organizer: Emre Telatar
|
|
Emmanuel Abbe
Universal Source Polarization and Sparse Recovery
|
|
Abstract:
Polar codes allow to perform lossless compression of i.i.d. sources
at the lowest rate with low encoding and decoding complexity. In
this paper, it is shown that for binary sources, there exist
"universal polar codes" which can compress any source of low
enough entropy, without requiring knowledge of the source
distribution. While this result does not extend to q-ary sources,
it is shown how it extends to q-ary sources which belong to a
restricted family. An analogy between this family and BECs in
channel polarization is discussed. Finally, an application of the
universal source polarization results to sparse data recovery is
proposed.
Tue 31 Aug, 09.55-10.20, Room 1
|
|
|
Ilya Dumer
Polarized properties of subcodes of Reed-Muller codes
|
|
Abstract:
We analyze recursive decoding algorithms known for general Reed-Muller
(RM) codes and their subcodes. The basic recursive procedure
discussed in this talk is similar to the cancellation decoding of
polar codes and uses the same channel recalculations to derive
information bits of a given RM code. For different information bits,
this recursive algorithm also exhibits a substantial range of the
output bit error rates. Therefore, we turn to the subcodes that
eliminate some of the most error-prone information bits of an RM code
and show that these subcodes achieve channel capacity similarly to
polar codes. We then enhance recursive techniques by using the
intermediate lists of the recovered information strings. Finally, we
study the error probabilities of different information bits and their
exponential moments. It is proven that these moments achieve
polarized properties on the symmetric memoryless channels.
Tue 31 Aug, 10.20-10.45, Room 1
|
|
|
Hesham El Gamal
TBA
|
|
Tue 31 Aug, 10.45-11.10, Room 1
|
|
|
Eran Hof and Shlomo Shamai
Secrecy-Achieving Polar-Coding
|
|
Abstract:
A polar coding scheme is suggested for the binary-input memoryless
symmetric and degraded wire-tap channel. The provided scheme
achieves the entire rate-equivocation region for the considered
model.
Tue 31 Aug, 11.30-11.55, Room 1
|
|
|
Toshiyuki Tanaka
On speed of channel polarization
|
|
Abstract:
We review some recent progresses in studies on speed of channel
polarization. Firstly, results on a coderate-dependent upper bound
of block error probability of polar codes with successive
cancellation decoding are reviewed. Then an approach of
constructing polar codes for non-binary input alphabet with
asymptotic speed of polarization much faster than previous
approaches is briefly described.
Tue 31 Aug, 11.55-12.20, Room 1
|
|
|
Ido Tal, Alexander Vardy
How to Construct Polar Codes
|
|
Abstract:
Polar codes approach the capacity of binary-input symmetric discrete
memoryless channels with low encoding and decoding complexity.
However, the best-known complexity of their con- struction scales
exponentially with the code length, unless the underlying channel is
an erasure channel. Specifically, although several heuristics for this
problem have been proposed, there is no known algorithm for
constructing polar codes that runs in polynomial time on one hand and
provides explicit guarantees on the quality of its output on the other
hand.
In this work, we present such an algorithm. It is well known that
constructing a polar code of length n is equivalent to evaluating n
constituent channels, and the problem is that the output alphabet of
each such channel grows exponentially fast with n. We introduce a
method which makes it possible to circumvent this problem of
prohibitively large alphabet size. Using this method, we can compute
in polynomial time explicit upper and lower bounds on the relevant
properties of the n constituent channels, such as capacity,
error-probability, and the Bhattacharyya parameter. This, in turn,
enables us to identify the good channels, thereby constructing a polar
code.
Tue 31 Aug, 12.20-12.45, Room 1
|
Back to previous page
Return to conference mainpage
|
|
