Reference no: EM133089842 , Length: word count:3000

COSC 5P01 Coding Theory - Brock University

In this assignment you are given the challenge of attempting to establish bounds on the size of optimal error-correcting codes. You can choose to apply this to codes defined using Hamming distance, edit distance or insertion-deletion distance. The problem definition is as follows.

A (n, M, d)q code is a set of M q-ary codewords of length n such that every pair of codewords are distance at least d from each other. The value M is called the size of the code and the value d is called the minimum distance of the code for the chosen distance measure.

Given n, d and q, we wish to determine the largest possible value of M for which there exists a (n, M, d)q code. A (n, M, d)q code is optimal if M attains this largest possible value. For Hamming distance codes, this largest value is denoted as Aq(n, d). Equivalently, for edit distance codes we have Eq(n, d) and for insertion-deletion correcting codes we have Dq(n, d).
Tables of best-known values for Aq(n, d) may be found here:

• Binary
• Ternary
• Quaternary
• 5ary

Note that while there are exact values for Aq(n, d), Eq(n, d) and Dq(n, d) for some parameter sets, many others have upper and lower bounds only. You can choose to work on either upper or lower bounds. For edit distance codes and insertion-deletion correcting codes, you can also choose to work on fixed-length or variable-length codes. You are free to choose any method that you think is appropriate including those discussed in class. Generally speaking, if you wish to lower an upper bound then you will require an exhaustive search with mathematical arguments, while if you wish to raise a lower bound then you may consider artificial intelligence techniques (for example evolutionary algorithms).

Important note: Naturally, you are not expected to establish new bounds (because this is very hard!) but rather to develop a working program that will either:

1. Show that a (n, d)q code with more than M codewords cannot exist, for some chosen values
n, M, d and q (by an exhaustive search for such a code), or

2. Show that a (n, d)q code with at least M codewords does exist, for some chosen values n, M, d and q (by producing such a code).
You can choose any value of q that you wish. While there are fewer words to consider for binary codes, and they have an easier representation, they are also much more studied than ternary, quaternary (etc) so it will be harder to approach the values in the tables.

Recommendations:
If you wish to use a particular approach for this assignment then you are more than welcome to discuss this with your instructor.
Regardless of the approach chosen, given a large enough value of n your program will take an extremely long time to run! It will also require huge amounts of memory. It is strongly recommended that you start with codes of small lengths to get comfortable with the problem first. After this, try your program on incrementally larger lengths.
You should also think carefully about representation of the words. You will save a lot of space and also time if you store words as integers (bit-vectors) and use bit manipulations for the calculations if possible.
Save plenty of time for proper analysis of your results, and to write the description of your approach and your summary.