Investigate the possibility of achieving the Shannon limit with linear block codes, using the following counting argument. Assume a linear code of large blocklength N and rate R = K/N. The code's parity-check matrix H has M = N - K rows. Assume that the code's optimal decoder, which solves the syndrome decoding problem Hn = z, allows reliable communication over a binary symmetric channel with flip probability f.
How many ‘typical' noise vectors n are there?
Roughly how many distinct syndromes z are there?
Since n is reliably deduced from z by the optimal decoder, the number of syndromes must be greater than or equal to the number of typical noise vectors. What does this tell you about the largest possible value of rate R for a given f?