Abstract:

Polar codes, a class of binary error-correcting codes, have recently been
invented by Arikan. Polar codes have an explicit construction and are known
to be capacity achieving (for binary, memoryless, symmetric channels).
Moreover, they have corresponding efficient encoding and decoding
algorithms. To date, no other family of codes is known to possess all of
these favorable traits.

Although polar codes are explicitly defined, a straightforward construction
is intractable. In the first part of the talk we present a method by which
polar codes can be efficiently constructed. The key observation is that a
channel with a large output alphabet size can be "sandwiched" between two
channels with a smaller output alphabet size.  

Once polar codes were constructed, it quickly became apparent that their
performance under Arikan's successive cancellation decoding scheme is
inferior to that of the current state-of-the-art LDPC codes. In the second
part of the talk we present an improved decoder for polar codes. Our decoder
employs list decoding at an intermediate stage, but ultimately puts out a
single codeword. The complexity of decoding is O(L n  \log n), where L is
the list size and n is the codeword length. We then introduce a slightly
modified family of polar codes. Decoding the modified family of polar codes
with our improved decoder results in performance comparable with the current
state-of-the-art.

Short bio:
Ido Tal got his B.Sc., M.Sc., and Ph.D. from the Computer Science
Department, Technion, Israel. His M.Sc. was done under Prof. Ronny Roth. His
Ph.D. was done under Prof. Tuvi Etzion and Prof. Ronny Roth. Ido is
currently an ITA postdoc at UCSD, working with Prof. Alexander Vardy. Ido's
research interests are coding theory in general, polar codes,
multidimensional constraints, and list decoding. He is the recipient of the
Hewlett-Packard Excellence Fellowship for Technion Ph.D. Students.

Refreshments served from 14:15 on,
 	Lecture starts at 14:30