这是一个编码理论的作业代写

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: http://www.win.tue.nl/~aeb/codes/binary-1.html

• Ternary: http://www.win.tue.nl/~aeb/codes/ternary-1.html

• Quaternary: http://www.win.tue.nl/~aeb/codes/quaternary-1.html

• 5ary: http://www.win.tue.nl/~aeb/codes/5ary-1.html

Equivalent tables for Eq(n, d) may be found at http://www.cosc.brocku.ca/~houghten/edit.html

and for Dq(n, d) at http://www.cosc.brocku.ca/~houghten/insdel.html.

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.

## Submission Requirements:

All submissions will be via Sakai. All of the following must be put in a single, zipped folder for

submission:

1. A 1-2 page description of the approach used to solve the problem.

2. A 2-3 page summary of results/conclusions that you can draw from using the chosen approach.

This should describe the most difficult parameter set(s) that your program was able to solve. It

should also include a description of possible future improvements.

3. Commented and properly documented PDF “printouts” for all of your program(s).