Recap: Expanders and Coding Theory
We looked at applications of Expanders to Coding Theory and saw that they could be used to obtain efficient encoding and decoding algorithms, with good error-detection and recovery properties.
We first considered codes which used the adjacency matrix of a bipartite expander as the parity check matrix. The simple FLIP algorithm allowed us to decode from a constant fraction of errors in linear time. In this algorithm, vertices of the left partite set are labelled with the bits of the received word, and a vertex of the right partite set is satisfed if an even number of its neighbors are set to '1'. As long as any vertex on the left has more unsatisfied than satisfied neighbors, we flip the bit corresponding to that vertex.
A similar idea could be tried for efficient encoding, but in order to obtain a linear time algorithm, the adjacency matrix must be sparse. Codes with low-density generating matrices have poor error correcting capabilities, but Spielman showed that such codes could be used for error reduction. Using Spielman's error-reducing codes, we can inductively construct error-correcting codes which allow linear-time encoding.
Another use of expanders is in the algorithm of Alon, Bruck, Naor, Naor and Roth; their construction allows us to obtain linear-time encodable and decodable codes with very large minimum distance (and hence good error correction); the price we pay is a significantly increased alphabet size. Finally, we considered list decoding, in which we output all codewords (not just the nearest codeword) that are sufficiently close to the received word. The ABNNR construction allowed us to construct a (1,2,2)-list recoverable code: that is, if in the received codeword, we have a list of two possible symbols for each position of the codeword, we output each of the (at most 2) codewords that are compatible with all the lists. We also saw that a similar construction could be used to obtain list-decodable codes from list-recoverable codes.
We first considered codes which used the adjacency matrix of a bipartite expander as the parity check matrix. The simple FLIP algorithm allowed us to decode from a constant fraction of errors in linear time. In this algorithm, vertices of the left partite set are labelled with the bits of the received word, and a vertex of the right partite set is satisfed if an even number of its neighbors are set to '1'. As long as any vertex on the left has more unsatisfied than satisfied neighbors, we flip the bit corresponding to that vertex.
A similar idea could be tried for efficient encoding, but in order to obtain a linear time algorithm, the adjacency matrix must be sparse. Codes with low-density generating matrices have poor error correcting capabilities, but Spielman showed that such codes could be used for error reduction. Using Spielman's error-reducing codes, we can inductively construct error-correcting codes which allow linear-time encoding.
Another use of expanders is in the algorithm of Alon, Bruck, Naor, Naor and Roth; their construction allows us to obtain linear-time encodable and decodable codes with very large minimum distance (and hence good error correction); the price we pay is a significantly increased alphabet size. Finally, we considered list decoding, in which we output all codewords (not just the nearest codeword) that are sufficiently close to the received word. The ABNNR construction allowed us to construct a (1,2,2)-list recoverable code: that is, if in the received codeword, we have a list of two possible symbols for each position of the codeword, we output each of the (at most 2) codewords that are compatible with all the lists. We also saw that a similar construction could be used to obtain list-decodable codes from list-recoverable codes.
posted by Nitish at
10:10 PM
0 Comments:
Post a Comment
<< Home