Computer Science Colloquium
Time+Place : Tuesday 28/02/2012 14:30 room 337-8 Taub  Bld.
Speaker    : Ido Tal
Affiliation: UCSD
Host       : Tuvi Etzion
Title      : Polar codes: construction and improved decoding
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 a binary, memoryless, symmetric channel). More
so, they have corresponding efficient encoding and decoding algorithms. To
date, no other family of codes is known to posses all of these favorable
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 component in the
construction is a method by which a channel with a large output alphabet
size can be "sandwiched" between two channels with a smaller output alphabet
Once polar codes were constructed, it quickly became apparent that they were
uncompetitive with current state-of-the-art LDPC codes. In the second part
of the talk we present an improved decoder for polar codes. Our improved
decoder is a list decoder. 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
Visit our home page-   <>
Technion Math. Net (TECHMATH)
Editor: Michael Cwikel   <> 
Announcement from: Hadas Heier   <>