Explore BrainMass

Code Size Bounds

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.

Solution Preview

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 ...

Solution Summary

This explains several definitions relating to code size bounds. Singleton bounds for sphere-packing bounds and Varshamor-Gilbert are analyzed.