Electrical Engineering-Systems Dept.

You are invited to attend a lecture by

Idan Goldenberg

(Ph.D. student under the supervision of Prof. David Burshtein)

on the subject:

On Linear Programming Based Decoding of Graph-Based Codes

The idea of using linear-programming (LP) based techniques as a tool to decode graph-based codes has been proposed about a decade ago. These techniques have an interesting theoretical appeal, in part owing to the maximum-likelihood (ML) certificate property: Whenever an LP-based decoder outputs a codeword, it is guaranteed to be the ML codeword.

In this talk the basics of LP decoding will be reviewed, and our results referring to low-density parity-check (LDPC) codes will be presented. These include

·        A general technique to improve performance of LP decoding via check node merging.

·        An efficient algorithm which calculates a lower bound on the minimum distance of a specific code.

·        An efficient algorithm which calculates a tight lower bound on the fractional distance (a quantity related to the LP decoder).

·        A new theoretical property which we call the approximate ML certificate. This property allows us to provide a bound on the reliability of a codeword obtained for example by the standard belief-propagation (sum-product) decoder, by using the LP decoder

Time permitting, we will discuss two additional results. First, an upper bound on the error exponent over the binary erasure channel (BEC), which relates to ensembles of regular LDPC codes, is proposed. In this case of the BEC the performance of the LP decoder is identical to that of the sum-product decoder. It is demonstrated that in some cases this upper bound coincides with an existing lower bound on the error exponent, thus giving the exact exponential behavior. Second, we derive an upper bound on the LP decoding error probability of repeat-accumulate (RA) codes. This bounding technique is applicable to regular RA(q) codes (q is the repetition degree) with even q and also to irregular RA codes where all repetition degrees are even, and assumes transmission of the code over a memoryless binary-input, output-symmetric channel. This bound extends a previous result relating to regular RA(2) codes.