We now turn to limitations of codes, in the form upper bounds on the rate of codes as a function of their relative distance. We will typically give concrete bounds on the size of codes, and then infer as corollaries the asymptotic statement for code families relating rate and relative distance. All the bounds apply for general codes and they do not take advantage of linearity. However, for the most sophisticated of our bounds, the linear programming bound, which we discuss in the next set of notes, we will present the proof only for linear codes as it is simpler in this case.
We recall the two bounds we have already seen. The Gilbert-Varshamov bound asserted the existence of (linear) 
As remarked in our discussion on Shannon’s theorem for the binary symmetric channel, if the Hamming bound could be attained, that would imply that we can correct all (as opposed to most) error patterns of weight 
1. Singleton bound
We begin with the simplest of the bounds:
Theorem 1 Let
be a code of block length
.
Proof: Suppose not, and 
This gives an alphabet-independent asymptotic upper bound on the rate as a function of relative distance.
Corollary 2 The rate
and relative distance
.
on the rate of 
(you are asked to prove this for the binary case on your problem set). Using this and the proof of the Johnson bound for the binary case, we concluded the Elias-Bassalygo upper bound, our last of the “elementary” upper bounds.
, the quantity 
equals 
if 
and equals 
otherwise.
supported on a finite set 
, then Shannon’s source coding theorem states that one can compress its output to 
bits per time step (on average, over 
). In other words 
possible outputs. Here ![\displaystyle H(Z) = \sum_{z \in {\cal Z}} \mathop{\mathbb P}[Z=z] \log \frac{1}{\mathop{\mathbb P}[Z=z]} \ . \ \ \ \ \ (1)](http://s0.wp.com/latex.php?latex=%5Cdisplaystyle+H%28Z%29+%3D+%5Csum_%7Bz+%5Cin+%7B%5Ccal+Z%7D%7D+%5Cmathop%7B%5Cmathbb+P%7D%5BZ%3Dz%5D+%5Clog+%5Cfrac%7B1%7D%7B%5Cmathop%7B%5Cmathbb+P%7D%5BZ%3Dz%5D%7D+%5C+.+%5C+%5C+%5C+%5C+%5C+%281%29&bg=ffffff&fg=000000&s=0 "\displaystyle H(Z) = \sum_{z \in {\cal Z}} \mathop{\mathbb P}[Z=z] \log \frac{1}{\mathop{\mathbb P}[Z=z]} \ . \ \ \ \ \ (1)")
is to the base 
. Thus the entropy of a fair coin toss is 
, and that of a 
-biased coin toss is 
. The source decoder at the other end of the communication channel then decompresses the received information into (hopefully) the original output of the source.
, must then be communicated over a noisy channel. The channel’s noisy behavior causes errors in the received symbols at the destination. To recover from the errors incurred due to the channel, one should encode the information output by the source coder by adding systematic redundancy to it. This is done through channel coding which maps 
of some suitable error-correcting code (the study of channel coding will be our focus in this course).
is denoted simply as 
. 
of radius 
centered at the codewords of 
, denote by 
the volume of (i.e., the number of strings in) a Hamming ball of radius 
in 
. Note that this number does not depend on where the ball is centered and equals
-error-correcting codes, leading to the Hamming/Volume upper bound on rate.
