18.310 Assignment 4 Due Monday October 4, 2004

1. Express Shannon’s Second Theorem in your own words and outline a proof of it.

2. Construct a perfect matrix single error correcting code on 11 message bits, on a spreadsheet.

3. Create a spreadsheet encoder for your code.

4. Create an automatic spreadsheet decoder for your code. This should allow you to decode any 15 bit received message and reverse any single b8 error and find the sent message, if there is at most 1 error.

Hint: the easiest way to do this (I think) is:

Write down your decoding matrix D.

Assign a distinct number to each row of it by treating its bits as forming the bits of a number in binary Thus 0110 would be 6, etc (this takes one instruction, and copying).

Write your “received message” as a column.

Form a new matrix whose entries are the products of the entries of D with the corresponding entry of your received matrix. (Takes one instruction and copying)

Sum the columns of this mod 2 and form its number. (easy)

Identify which row of D has the same number and copy the received message flipping the bit in that row. (use one if statement, copied)

Add a parity bit ( for a total of 16, and use it to detect if there are two errors.