TIME: 1:30-2:20 pm,  April 8, 2008

PLACE: CSE 503  

SPEAKER: Widad Machmouchi
         University of Washington

TITLE: Repeat Accumulate Accumulate (RAA) Codes Construction


ABSTRACT:

Repeat Accumulate Accumulate (RAA) codes are turbo-like codes where
the message is first repeated $k \geq 2$ times, passed through a first
permutation, then an accumulator, then a second permutation, and
finally an second accumulator. Bazzi, Mahdian and Spielman prove that
RAA codes are asymptotically good with high probability codes when the
two permutations are chosen at random. We focus on the case when $k=2$
and we consider a variation of RAA codes where the inner repeat
accumulate code is systematic. We give an explicit construction of the
first permutation for which we show that the resulting code is
asymptotically good with high probability when the second permutation
is chosen at random. The explicit construction uses a cubic
hamiltonian graph with logarithmic girth.

Joint work with Venkat Guruswami