Create a correctable code for a list of key words. Your task is to create an efficient, correctable code for a list that contains at least 6 key words. The words in your code will be represented as binary strings using only 0’s and 1’s. Stringent correctability requirements mean your code must have a minimum distance of 3.
– First, watch the following two videos, then read the following information to understand the definitions for bit, binary word, code, codewords, Hamming distance, and minimum distance of a code:
Video 1: Parity Checksums
Video 2: Hamming distance
Consider a sequence of 0’s and 1’s of length n. This can be represented by an n-tuple of 0’s and 1’s such as (1,0,1,1) if n=4. If V={0,1}, then we can form the product of V with itself n times and denote it by Vn. So Vn={(a1, a2, …, an)|ai∈{0,1}}. Vn consists of all possible binary words of length n. We can define a metric on Vn called the Hamming distance dH as follows:
For binary words x and y of length n, dH(x, y) is the number of places in which x and y differ.
Given this metric, Vn is now a metric space, and the topology induced by this metric is the discrete topology on Vn since the topology induced by a metric on a finite set is the discrete topology, and Vn is finite.
To send a message using binary words, not all of Vn will be used; rather, only a subset of Vn will be used. A subset C of Vn is called a code of length n, and the binary words in C are called codewords. The smallest Hamming distance between any two codewords in C is called the minimum distance of the code C.
It turns out that, if a code C of length n is designed so that the minimum distance of C is d, then any binary word that had up to d-1 errors can be detected. Furthermore, any binary word that had floor((d−1)/2) or fewer errors can be corrected. [Here, floor is the floor function; for example, floor(3.6)=3 and floor(8)=8.]
Now, you’re ready to create your correctable code. – Create a code consisting of binary codewords. – The code must meet three requirements — Contain at least 6 codewords — Have a minimum distance of 3 (explain why a min distance of 4 is no better than 3) — Maintain efficiency by using the fewest number of bits per codeword as possible – Clearly document and describe your code: what it is, why you chose it, etc. – Discuss how topology relates to the selection of your code and the Hamming metric
A few notes about format: use MS PowerPoint for your presentation; develop a presentation that is 10-15 slides in length; incorporate audio files into your presentation in order to explain your work; use Equation Editor for all mathematical symbols, e.g. x ∈ X or Cl(A) ⋂ Cl(X-A); and select fonts, backgrounds, etc. to make your presentation look professional.