Useful links
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:
Here the sequence of steps that were followed to prepare the message youĂ•ll decode during lab on Wednesday:
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
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.
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:
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:
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.