PowerPoint (418) (1)

profiletandr102

 

Multimedia Presentation In this assignment, you will 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. xX or Cl(A)Cl(X-A); and select fonts, backgrounds, etc. to make your presentation look professional.  

Course and Learning Objectives This Writing Assignment supports the following Course and Learning objectives: CO-4 Determine if a topological space is a metric space and generate a topology from a metric. LO-13: Understand the definitions of a metric and metric space. LO-14: Develop a topology from a metric. 

    • 2 years ago
    • 100
    Answer(0)