transpose(H)
matmult(A,B) does the matrix multiplication AB;
calling matmult(A,B,2) will do this mod 2---all our matrix
multiplications will be mod 2 today.
strtobits(s,4) will converts into a string of 4-bit blocks,
i.e., a 0-1 matrix matrix of bits with 4 columns and some number of rows
bitstostr(b) will convert a bit matrix b back to a string
noise(x,p) will apply noise (uniform with probability p
of a bit error) to a bit matrix x
Task 1: (go through the encoding/decoding process with no
noise/no corrections)
Take the test string s, and convert it into a string b of 4-bit blocks.
Encode b with the generator matrix G with the product x = bG.
Now one decodes with y = xR. Recovert to a string and check you get
s back.
Task 2: Write a function pos(u) that takes in a 3-bit
vector and returns the corresponding integer between 0 and 7 so u is
the binary representation of this number. Here low order
bits are to the left, i.e., u = [1, 0, 0] corresponds to 1 and u = [0, 0, 1]
corresponds to 4.)
Task 3:
Write a function correct(y) that takes a list y of 7-bit words
and applies nearest neighbor decoding as follows. For each word w in y,
compute the "syndrome" u = wHT, where
HT is the transpose of H. Flip the bit of w in position pos(u)-1
(since position are indexed starting at 0, not at 1---if u = [0, 0, 0],
then do nothing). Here, feel free to modify the
list y itself, so this function does not need to return anything.
Test this out by taking a codeword w, say w = G[0][:7] (this will copy
the first row of G---if you just set w = G[0], modifying w will
modify G), modifying a single bit, and calling correct([w]).
Task 4: Take the test string s, and encode it as a bit matrix x. Apply noise to x with probability p=0.05 to get a garbled bit matrix y. Try to decode both without and with error correction, i.e., look at the string for yR first without correcting y, then with correcting y. How much of the string is readable in each case? Try experimenting with different values of p. What's approximately the smallest value of p for which the message becomes unreadable?