Best代写-最专业靠谱代写IT | CS | 留学生作业 | 编程代写Java | Python |C/C++ | PHP | Matlab | Assignment Project Homework代写

编码理论代写|COSC 5P01 – Coding Theory Assignment #2

编码理论代写|COSC 5P01 – Coding Theory Assignment #2


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:

Equivalent tables for Eq(n, d) may be found at
and for Dq(n, d) at

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.


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

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