Block Codes February 21, 2006

A code with fixed code length, n, is called a block code. For such a block code, there are bounds on the number of codes M, given a code length n and minimum distance d (and hence a bound on the error-detecting and correcting capabilities).

[Hamming Bound]


Hamming bound

[Gilbert-Varshamov Bound]


Gilbert-Varshamov bound

[At some point in the past, I was looking at the possibility of changing the shape of a density function by re-shuffling its support. At that point, it looked like the following theorem [see Baylis] would be useful. Turned out not to be what I needed once I understood the problem better.]

[Theorem]
Performing a positional permutation on the words of a code does not change its minimum distance.

[Plotkin Bound]
The Hamming and Singleton (not shown above) bounds give bounds on M for some arbitrary n and d. If willing to constrain d, the Plotkin gives a tighter (can we really say that ?) bound on M for the case when d > n/2, which given the dependence on number of correctable errors on d, will be useful for when we need to correct a largen number of errors.

[Theorem (Plotkin bound)]


Plotkin bound

Tags
Conversation
Related Tags
Comments
Trackback


Leave a Reply

You must be logged in to post a comment.

This entry was posted on Tuesday, February 21st, 2006 at 3:58 pm. You can follow any responses to this entry through the RSS 2.0 feed. If you're wondering how to get your own icon next to your comment, go visit gravatar.com and get yourself hooked up.
 steal compass, drive north, disappear...