6.02 Lab #4: Error Correction

Useful links

lab4.py -- testing code for Lab #4
lab4_1.py -- template file for Task #1
lab4_2.py -- template file for Task #2

Goal

Decode a sample bit stream as it might have from a digital receiver, dealing with framing, burst-errors and single-bit error correction.

Instructions

See Lab #1 for a longer narrative about lab mechanics. The 1-sentence version:

Complete the tasks below, submit your task files on-line before the deadline, and complete your check-off interview within a week of the file submission deadline.

As always, help is available in 32-083 (see the Lab Hours web page).

Introduction

In this section we'll be reviewing the channel coding process that produced the bit stream you will decode during the lab on Wednesday. You'll need the information presented here in order to correctly implement the decoding steps needed to recover the transmitted message.

The purpose of the channel coding process is to add redundant information to the transmitted bit stream so that the receiver will be able to detect and correct errors that occurred along the way. As mentioned in lecture, there may be errors that can't be corrected with even the additional information, a circumstance that will be handled by higher levels of the communication protocol, e.g., by checking for uncorrectable errors using, say, a CRC to confirm the correct receipt of the entire message and requesting a retransmission if the message is corrupted.

lab4.py defines several functions useful in channel coding tasks:

even_parity(binmsg)

takes a binary message (a list of 0's and 1's) and returns 0 if the list contains an even number of 1's, otherwise it returns 1.

codeword(data,nrows,ncols)

data is a binary message (a list of 0's and 1's) with nrows*ncols elements. The first ncol elements belong to the first row, the second ncol elements to the second row, and so on. This routine returns a new binary message that starts with data and then appends (in the following order): even parity bits for each row, starting with the first row; even parity bits for each column, starting with the left column (i.e., the first element in each row); and finally an even parity bit for all the data and row/col parity bits. So the length of returned message is nrows*ncols + nrows + ncols + 1. The resulting code word has a Hamming distance of at least 4 from code words constructed from different data.

char2bin(c)

converts the character c into an 8-element binary list of 0's and 1's, where the first element of the list is the least significant bit of the binary representation of c, and so on.

bin2char(binmsg)

convert a binary list 0's and 1's (lsb first) into a printable characters. Returns "?" if character is not printable.

printmsg(msg)

prints out a message represented as a list of characters.

find_sync(msg,sync)

Locate blocks of bits separated by sync patterns. Strip out the syncs and return a list of the blocks. Each element of the list is itself a list of the 0's and 1's that occurred between the sync patterns. Can be used for both interleaving and deinterleaving.

interleave(binmsg,ncols)

takes a binary message (a list of 0's and 1's) and returns a new binary message with the rows and columns interchanged. ncols is the number of columns and binmsg is taken to have multiple rows, each containing ncol binary bits. The length of binmsg must be an integer multiple of ncols.

Here the sequence of steps that were followed to prepare the message youÕll decode during lab on Wednesday:

1. split message bit stream into 8-bit blocks and add the necessary row, column and overall parity bits to enable error correction.

   For this lab, we want to communicate a text message encoded in ASCII, so we chose an 8-bit block.

   We use a (15,8,4) block code that is a simple extension of the (8,4,3) code described in lecture: the eight data bits are organized into 2 rows of 4 columns, where each row and column has an associated parity bit. In order for the generated codewords to have a minimum Hamming distance of 4, we added an overall parity bit P, i.e., a bit that ensures that the 15-bit block has even parity. The 8 data bits (D1, ..., D4 from row 1 and D5, ..., D8 from row 2) are combined with the 7 parity bits (R1, R2, C1, C2, C3, C4, and P) to form the 15-bit codeword. The order of bits in the codeword is shown below:

   D1, D2, D3, D4, D5, D6, D7, D8, R1, R2, C1, C2, C3, C4, P

2. interleave the bits from B codewords to handle up to B-bit burst errors (B=16 in this lab).

   First, we start by filling out the message so that its length is an integer multiple of B. To do the interleaving, take groups of B 15-bit codewords and think of them as a matrix with 15 columns (one for each bit of a codeword) and B rows (one for each of the B codewords). We use the interleave function from lab4.py to do the interleaving.

   Normally one would proceed directly to step 3, but at this point we corrupted each interleaved codeword block with an error burst: a random sequence of between 1 and B bits starting at a random position in the block.

3. insert sync sequence before each bit-stuffed interleaved codeword block

   To make it possible for the receiver to find the start of each block of interleaved codewords, we'll add a sync sequence in front of each block. The sequence we use is defined by the sync variable defined in lab4.py: 0111111110. To ensure that the interleaved codeword block doesn't accidentally contains the sequence of eight 1's found in the sync sequence, we modify each block with a technique called bit stuffing. The block is examined for sequences of 1 bits of length seven (seven is one less than the sequence of eight 1's in the sync) -- for all such sequences, a 0 is inserted into the message after the seventh 1, guaranteeing that there will be no runs of eight 1's.

   The bit stuffing operation is easily reversed at the receiver: it just has to look for sequences of seven 1's and then remove the following 0 that was inserted by the transmitter. Note that the encoder will stuff the 0 into the sequence whether or not the seven 1's are followed by an eighth 1 -- otherwise the receiver won't be able to successfully unstuff the received message.

When the entire message has been converted the accumulated bit stream is written out into a file so that you can have the fun of decoding it. Actually we added some random bits at the front so that one has to search for the sync pattern to find the first interleaved data block.

During this week's lab your job is write a Python program that processes the channel coded bit stream (available as the value of the message variable in lab4.py) and recovers the original message. The bit stream has been corrupted by error bursts, so your program will need to implement the appropriate error correction.

Task 1: Find interleaved blocks, undo bit-stuffing, deinterleave (3 points)

Write a Python function decode to reverse the steps described in the prelab:

• Use the find_sync function in lab4.py to split message into a list of bit-stuffed blocks each containing B-way interleaved codewords.

• For each block of interleaved codewords:
  • undo the bit-stuffing described above. If you've done this correctly, each block should now contain exactly 15*16 bits (i.e., 16 code words of 15 bits each).

  • De-interleave the block using the interleave function defined in lab4.py. Be careful to think about the correct value for the ncols argument -- it changes depending on whether you're doing interleaving or deinterleaving.

  • For each codeword, i.e., for each 15-element segment of the block, extract the uncorrected data bits and use the bin2char function to convert them into an ASCII character, which you can then append to the accumulated message text.

• When all the blocks have been processed use printmsg to print out the message text you've accumulated. It'll look a bit weird since it'll have many uncorrected errors.

lab4_1.py is a template for this task:

# template for Lab #4, Task #1
import lab4
 
def decode(received): 
    message = []
    # find_sync returns a list of bit-stuffed interleaved
    # blocks, each element of the list is itself a list
    # of 0's and 1's that make up that particular block.
    for block in lab4.find_sync(received,lab4.sync):

        # undo the bit-stuffing (remove 0 following seven
        # consecutive 1's)
        ... your code here ...

        # now block should have exactly 15*16 elements.
        # use lab4.interleave to deinterleave the block.
        ... your code here ...

        # for each group of 15 bits in the block, extract
        # the (uncorrected) data bits and use lab4.bin2char
        # to convert them to an ASCII character, which you
        # should append to message
        ... your code here ...

    lab4.printmsg(message)

if __name__ == '__main__':
    decode(lab4.message)

Task 2: Perform error correction (4 points)

Define a Python function correct_errors(binmsg) that takes a 15-element binary list of 0's and 1's which it should interpret as 8-bit data encoded with the (15,8,4) code described in the Introduction. Your function should return an 8-element binary list with the correct data OR it should raise a DecodingError exception if the codeword contains an uncorrectable error.

To detect and correct errors in the codeword, you'll need to redo the row, column, and overall parity calculations to determine if a single-bit error has occurred and, if so, make the appropriate corrections to the data bits before returning the result. Think about the following:

• For what combination of parity errors in the P, Ri and Ci are no modifications necessary to the 8 data bits, i.e., when are there no errors at all, or only errors in the parity bits?

• For what combinations of parity errors has an error been detected in one of the data bits? How can you figure out which data bit got the error? What correction do you have to make to the erroneous data bit?

• All other combinations of parity errors indicate an uncorrectable error and you should raise a DecodingError.

Test your function using the test_correct_errors function defined in lab4.py:

# template for Lab #4, Task #2
import lab4
 
def correct_errors(binmsg): 
    # your function definition here 
 
    # this version of the function always declares
    # a DecodingError!
    raise lab4.DecodingError,"uncorrectable error!"

if __name__ == '__main__':
    lab4.test_correct_errors(correct_errors)

The test_correct_errors function will try a variety of test codewords and check for the correct results. If it finds an error, it'll tell you which codeword failed; if your code is working, it'll print out "Tests completed successfully."

Task 3: Perform error correction (3 points)

Modify your decode function from Task 1 to use your correct function to extract corrected data from each codeword before using bin2char to convert it into a text character.