One main task of coding theory is to construct good error-correcting codes, and, in practice, a good code must have efficient encoding and decoding algorithms. Moreover, a family of codes is asymptotically good provided that there exists an infinite subset of [n_i,k_i,d_i] codes from this family with lim_{i→ ∞} n_i = ∞ such that both lim inf_{i → ∞} k_i/n_i > 0 and lim inf_{i → ∞} d_i/n_i > 0.

The main result of this note is a new time-space tradeoff lower bound for the decoding complexity of asymptotically good error-correcting codes for oblivious write-k-times branching programs. Using one computational technique, branching programs, the author proves that if a leveled oblivious write-k-times branching program with time T and space S is used to decode a binary error-correcting code , {0,1}^m → {0,1}ⁿ, which is able to correct at most e errors, then S ... T^k ≥ . This result is interesting and the technique of branching programs can be modified and used to study other kinds of codes, such as ternary and quaternary codes. Overall, the author not only presents a time-space tradeoff lower bound for the decoding complexity of asymptotically good error-correcting codes, but also provides a new approach for the study of the complexity theory of decoding error-correcting codes.