Can you explain what do Singleton bound, the sphere-packing bound and the Varshamor-Gilbert mean? Determine what the Singleton bound, the sphere-packing bound and the Varshamor-Gilbert bound say about the maximum number of information bits that codewords with ten check bits can have if the codewords are protected from 3 or fewer errors

Please see the attached file.

Code Size Bounds

The general block codes take a block of data, say k 'symbol's, add redundancy to it and produces n symbols, these are called code words. These symbols could be anything, the most common example is binary where the symbols are 0 or 1 (the code would then be a binary code) - in general we normally say that there are q symbols to choose from (the code is then said to be q-ary). Diagrammatically:

These code words get sent across a noisy channel, some of the symbols can be corrupted. When we receive something from the noisy channel we try and work out which codeword was actually sent. Once we think we know which codeword was sent we then run the block encoder 'in reverse' to work out what we think the original source x was.

The size of the code is defined as the number of code words, let's call this S.

Now if the code words are 'close' then there is a high chance that the noise introduced by the channel will make the original code word look more like another one - so the message will be decoded incorrectly. So ideally the code words would be 'far' apart. Some idea of how far apart the code words are is encapsulated in the 'minimum distance'. The minimum distance is the smallest distance between two code words, the distance is the number of places where the code words differ.

A code is normally typified by the set [n,k,d] and the number of available symbols q. Can we construct a code with any n, k and d? Here's an easy example, what about [3,1,5] - well the code words have 3 symbols in them and supposedly code words differ in at least 5 places, clearly this is impossible! That's a trivial example, what about more useful bounds?

Singleton Bound

The code word y is n symbols long, each symbol can take q values, so:

Now each pair of code words differs in at least d places.
So the first n-d+1 bits of each pair of code words differ in at least 1 place.
So the first n-d+1 bits of each code word are distinct, hence

This is the Singleton bound.

Note that if we wanted a code word for all possible inputs x then

Hence
Hence

Sphere Packing Bound (also known as the Hamming Bound)

When we get a transmitted signal, we compare it to all the code words and choose the 'closest' one. How many vectors are there that are 'close' to a codeword? This depends on the minimum distance d. Let's say the minimum distance is 3, such codes can correct 1 error (if 2 errors occurred then the vector would be closer to a wrong codeword). So the vectors 'close' to a code word differ in only 1 place, that difference can mean that instead of the correct symbol, one of the other q-1 symbols is chosen. So:

Number of vectors differing in 1 place = Number of places where difference occurs *
Number of possible other symbols
= n(q-1)

So if d=3, the number of vectors close to a code word = 1 + n(q-1) (the 1 is for the original codeword, this is obviously 'close' to the original codeword).

In general if the code can correct t errors then:

Number of vectors 'close' to a codeword = Number of vectors differing in i places
Number of vectors 'close' to a codeword = Number of places the i differences occur *
Number of possible other symbols used
Number of vectors 'close' to a codeword =
If a code has minimum distance d then it can correct errors, so .
Each codeword can be viewed as having a sphere around it, inside which are all the vectors close to it. The total number of vectors inside all these spheres is:

But there are only so many vectors we can receive, i.e. . In order that our spheres have enough room:

This is the sphere packing bound. If this is violated it means that at least 2 spheres overlap, which basically means that 2 code words are closer than the minimum distance d.

Gilbert-Varshamov Bound

This bound is to do with a maximal code, that is, a code which has the greatest number of code words given the constraint n, k and d. (E.g. if you take a code and just make sure one of the code words is never produced the code will still work - it just won't be maximal in this sense. Maximal codes don't waste anything, basically.) That means that any vector must be less than d away from a codeword (i.e. any vector must have less than d differences between itself and some codeword). If x is d or more away from all code words then we could actually make x a new codeword (as the result will still be a code with minimum distance d). So by assuming the code is maximal we know that every vector is less than d away from a codeword.

Now how many vectors are there less than d away from a code word?

Number of vectors <d from a codeword = Number of vectors differing in i places
Number of vectors <d from a codeword = Number of places i differences occur *
Number of possible other symbols used
Number of vectors <d from a codeword =
Because our code is maximal, every possible vector lies in one of these 'spheres'.
If we were to add up all the vectors in all these 'spheres' (mostly overlapping spheres) then this should certainly be bigger than or equal to the total number of possible vectors. So

This is the Gilbert Varshamov bound which applies to maximal codes

Examples

1) Can we have a binary [12,7,5] code?

The Singleton bound:

So the Singleton bound is satisfied

The sphere packing bound
For a binary code q=2

Now k=7, so we're hoping to have code words. This contradicts the bound so we can't have a [12,7,5] binary code where all the inputs are valid.

The Gilbert-Varshamov bound

So a maximal code must have at least 6 code words. Well this is satisfied by .

So our code passes the Singleton bound and the Gilbert-Varshamov bound but fails the sphere packing bound. If any one of these fails then the code with the given values n, k, d and q cannot exist. Conclude no binary [12,7,5] exists.

2) Another example is given k=5 information bits and a code that can correct 3 errors (d must be 7 in order to do this, at least) (note q=2 again as we're talking bits) what can we say about n?

The Singleton bound:

So

The sphere packing bound
Now we want

When n=0 the inequality is violated. For large n the right hand side dominates. Both sides are increasing in n. So there is some value of n, below which the inequality is violated and equal to and above it the inequality is satisfied. By graphing both sides you will be able to show that if
Then

The Gilbert-Varshamov bound

The inequality holds for n=0 and is violated for large n. Both sides increase in n. By graphing both sides of the inequality you can find the cross over point. One finds that

So putting all of these bounds together we get .

That is to say that for k=5, d=7 and to have a maximal code then n can only take the values 18, 19, 20 or 21.

3) The last example is to find restrictions on k, given that the code can correct 3 errors (so d=7 again) and the encoder adds 10 bits of redundancy, so n=10+k

The Singleton bound:

So
So the Singleton bound is automatically met.

The sphere packing bound
Now we want

The left hand side is increasing in k. By graphing the left hand side you should be able to see that the largest value of k for which the inequality holds is 8. So

The Gilbert-Varshamov bound

The left hand side is increasing in k, the smallest value of k for which this is true is k=1.
So
This isn't much use as k=0 means encoding nothing! So this bound is of no use

The only useful bound is the sphere packing one which tells us that: