10 Linear time in the logarithmic cost model
The product of an outer expander code over an alphabet of \((\log n)/2\) bits with an inner binary code of length \(\log n\) and rate \(1/2\) is the code obtained by encoding each \((\log n)/2\)-bit byte of a codeword with the inner code. Equivalently it is a code over the larger alphabet whose symbols are themselves protected by a short good code.
The product of an asymptotically good linear code of length \(O(\log n)\) with one of the expander codes (of length \(O(n/\log n)\)) from Section V or VI yields an asymptotically good code that can be decoded in linear time on a RAM in the logarithmic cost model.
Decode each of the \(2n/\log n\) bytes by a precomputed nearest-neighbour table lookup, costing \(O(\log n)\) time per byte and \(O(n)\) in total. Then run the expander decoder (Theorem 38) on the resulting symbols: it corrects a constant fraction of error, and unless a constant fraction of error appears in the encoding of a constant fraction of the bytes, very few errors remain after the byte decoding. The expander decoder now manipulates bytes of \((\log n)/2\) bits, so each of its \(O(n/\log n)\) memory accesses costs \(O(\log n)\) in the logarithmic cost model, for \(O(n)\) total. Hence the whole decoder runs in linear time in the logarithmic cost model, and the composite code is asymptotically good.