Consider meets the Singleton bound with rate of , i.e. has relative distance In order for to be an asymptotically good code, also needs to be an asymptotically good code which means, needs to have rate and relative distance .
We can construct a code that achieves the Zyablov bound in polynomial time. In particular, we can construct explicit asymptotically good code (over some alphabets) in polynomial time.
Linear Codes will help us complete the proof of the above statement since linear codes have polynomial representation. Let Cout be an Reed-Solomon error correction code where (evaluation points being with , then .
To perform an exhaustive search on all generator matrices until the required property is satisfied for . This is because Varshamovs bound states that there exists a linear code that lies on Gilbert-Varshamon bound which will take time. Using we get , which is upper bounded by , a quasi-polynomial time bound.
To construct in time and use time overall. This can be achieved by using the method of conditional expectation on the proof that random linear code lies on the bound with high probability.
Thus we can construct a code that achieves the Zyablov bound in polynomial time.