In the previous chapters, we have already seen constructions of asymptotically good codes of good rate over both large alphabets (the AG-codes from Chapter 6) and the binary alphabet (the concatenated codes from Chapter 8), that are efficiently list decodable up to a "maximum" possible radius. By "maximum" possible radius we mean list decoding up to a fraction (1 - 1/q - ε) of errors for q-ary codes. This translates into a fraction (1 - ε) of errors for codes over large enough alphabets, and a fraction (1/2-ε) of errors for binary codes. For codes with such large list decodability, which we called "highly list decodable codes", the goal is to find efficient constructions that achieve good rate (typically of the form Ω(ε{sup}a) for some reasonably small a), together with efficient list decoding algorithms.
展开▼
