python代写: CSE1010 HW 6 Error Correction

HW 6: Error Correction

CSE1010 Spring 2018 Jeffrey A. Meunier University of Connecticut

Table of Contents

1. Introduction 2 2. Due Date 2 3. Value 2 4. Objectives 2 5. Background 3

5.1. Binary data transmission 3

6. Assignment
6.0. Preliminaries

6.0.1. Read the

7

7 background 7 8 8 string2bin 8 segmentString 9 printFrames 10 string2frames 11 appendParityColumn 13 transpose 14 appendParityRow 14 appendParityToFrame 17 appendParityToFrames 17 18 6.2. Transmission Phase 18 6.2.1. Function transmitFrames 19 6.3. Decoding Phase 20 6.3.1. Function splitFrame 20 6.3.2. Function checkParityOfFrame 22

6.0.2. New file 6.1. Encoding Phase

6.1.1. Function 6.1.2. Function 6.1.3. Function 6.1.4. Function 6.1.5. Function 6.1.6. Function 6.1.7. Function 6.1.7. Function 6.1.8. Function 6.1.9. Summary

6.3.3. Function repairFrame 6.3.4. Function repairFrames 6.3.5. Function stripFrames 6.3.6. Function bin2string 6.3.7. Function frames2string

6.4. Main function

23
26
27
28
29
30

1

6.5. Program comments 32 7. Report 32 8. Submission 33 9. Grading Rubric 33

1. Introduction

In this project you will use arrays of numbers to create groups of bits (binary digits) that are to be sent over a simulated communications channel from one computer to another. The sender uses parity bits to encode extra information in the data that allows the receiver to detect and correct errors in the transmitted bits. The simulated communications channel will be a function that, with low probability, flips bits randomly.

2. Due Date
This project is due by midnight at the end of the day on Sunday, April 8, 2018. A penalty

of 20% per day will be deducted from your grade, starting at 12:00:01am.

Notice that this is a 1+ week project, almost 2 weeks. That means that I’m quite confident that you will need more than one week to finish the project because in previous semesters when I gave a variant of this project, very few students could finish it in one week. So then that means that if you don’t start the project until the second week, you won’t be able to finish it.

I will not give an extension on this project. It’s getting too close to the end of the semester and we have other things we need to do.

3. Value

This program is worth a maximum of 30 points. See the grading rubric at the end for a breakdown of the values of different parts of this project.

4. Objectives

In this project you will learn about:

• ⁃  Using and manipulating strings.
• ⁃  More lists, lists of lists, and lists of lists of lists.
• ⁃  More binary numbers and character encoding and decoding.

2

⁃ Functions, functions, and more functions. 5. Background

• ⁃  Read the first section on this web page: Basic Concepts Behind the Binary System.
• ⁃  Read this link from Wikipedia about what a parity bit is.
• ⁃  Read this web page for a brief definition of ASCII.

  5.1. Binary data transmission

  Modern wired networks and telephone lines are very reliable and have very low error rates, but wireless networks are subject to much higher error rates from radio interference. Interference can come from a wide range of sources, including other nearby radio networks, airplanes, clouds (clouds with lots of ionization will reflect and distort radio signals), lightning, heavy machinery, sunspot activity, and even cosmic rays emitted by stars that are millions of light years away.

  An error in data communication is any bit that is changed from its original value. In a received data stream, it is impossible just to look at the bits and determine which bits, if any, are in error, so the sender and receiver must agree on a specific data protocol that dictates the use of extra bits in the data stream that are used for error detection and/or correction.

  One error detection scheme calls for placing one extra bit in the data stream at regular intervals. Say you have groups of 8 bits to be sent over a network. A 9th bit is added after every 8 bits, and its value is set so that it makes the total number of 1s in the 9 bits either even or odd (depending on whether even or odd parity has been chosen).

  0 1 1 0 0 1 0 1 1 0 1 1 0 0 0 1 0 0 0 1 1 1 0 0 1 0 1 0 1 ...
  

  \_____________/ | \_____________/ | \_____________/ | \______
  

data parity data parity data parity

\_______________/ \_______________/ \_______________/ \______

9 bits 9 bits 9 bits

When a receiver receives the group of 9 bits (data + parity), the parity bit of the received 8 bits (without the parity bit) is recalculated, and if it matches the received parity bit, then it is assumed that the group of 8 bits contains no errors (even though it is possible that it contains an even number of errors, or the parity bit itself is in error). If the parity bit does not match, then the preceding group of 8 bits contains an error and the receiver asks the sender to re-send the data. More advanced parity schemes allow the receiver to detect any

3

small number of errors, and in some cases to correct one or more errors.

In this assignment you will employ parity generation and analysis that could be used to detect and correct errors in bit streams. The bit stream will in fact just be a two- dimensional list (a list of lists) of 0s and 1s. Applying parity to each row and column of this list will enable you to write a function that can actually correct a certain small number of errors.

Bytes and Octets

Because all values in a computer are stored internally using binary values (ones and zeros), it is only natural that a computer would transmit data to other computers using this format. When a byte leaves a computer and is sent out into some transmission medium (like a network), the byte is usually called an octet, which means ‘group of eight’. The reason for this is that in some computers (usually old ones), a byte can be more or fewer than 8 bits, but in a network, we need to know exactly how many bits we’re dealing with, so a group of 8 bits is called an octet in order to be more specific.

Parity

When an octet is sent from one computer to another, the sender appends additional information to the byte in order to allow the receiver to detect if a transmission error has occurred. A single bit called a parity bit is often appended to each octet. This bit is used to add redundant information to each octet, making the total number of bits in each 9-bit group either even or odd. The sender and receiver must agree ahead of time to use either even or odd parity. If the receiver receives an odd number of ones in a 9-bit group, but the sender and receiver are using even parity, then the receiver knows that one of the bits was flipped from 0 to 1 or from 1 to 0 during transmission.

For example, say that the sender wishes to send the octet 11010011 over the network. The sender and receiver have agreed to use even parity, which means that an additional bit will be appended to the octet that makes the number of bits even. The octet has 5 ones, so a 1 is appended to the octet in the 9th bit position, making it 110100111. This entire group (it can no longer be called an octet) now has an even number of bits. Note that if the original octet already had an even number of bits, then the sender would have appended a 0, keeping the number of bits even. Finally, after appending the parity bit to the octet, the 9-bit group is sent to the receiver.

Now assume that the receiver receives this nine bit group: 110000111 (notice that it’s different from the one that the sender sent). The receiver calculates the parity (even parity, in this case) for the first 8 bits, which is 0 (since 4 of the 8 bits are 1). However, the sender sent a 1 for the parity bit (the 9th bit). The received and calculated parity bits disagree, which tells the receiver that this octet contains one flipped bit. In this case the receiver

4

might ask the sender to re-send the 9 bits.

Now let’s assume that we have the following 8 octets to send (where an octet is a row of 8 bits), making a total of 64 bits:

0101010 1 1110111 0 1100010 1 1010101 0 0100101 0 1000011 0 1011000 0 0011110 1

What we would normally do is compute a parity bit for each octet, append it to the octet as a 9th bit, and send each 9-bit group in succession. However, by adding even more parity information we can give the receiver the ability to both detect and correct a single bit error. We can do this by calculating parity bits not only across the rows of bits, but also down the columns of bits. This generates one parity bit for each row, plus an extra row of parity bits, one for each column.

Here the even parity bits are calculated for the rows and columns. The row and column numbers are shown in light blue, and the parity bits are in column 9 and row 9.

Add a 9th column of parity bits, one bit for each row:

1 23456789

1. 1  010101010
2. 2  111011100
3. 3  110001010
4. 4  101010100
5. 5  010010101
6. 6  100001101
7. 7  101100001
8. 8  001111011

Add a 9th row of parity bits, one bit for each column including the 9th:

1 23456789

1. 1  010101010
2. 2  111011100
3. 3  110001010
4. 4  101010100
5. 5  010010101
6. 6  100001101
7. 7  101100001
8. 8  001111011
9. 9  100101010

5

Note that here we are using even parity, and each row of 9 bits now contains an even number of bits, and each column of 9 bits contains an even number of bits. It turns out that it is a coincidence that the 9th row contains an even number of bits: it may not be this way for every example.

After transmission, the receiver receives the entire 81-bit group (which includes the data bits and parity bits) and places it into nine rows and nine columns. In this example I will now assume that during transmission there was some noise interference and one of the bits was flipped from 1 to 0, shown highlighted in the middle:

0 10101010 1 11011100 1 10001010 1 01010100 0100 00101 1 00001101 1 01100001 0 01111011 1 00101010

The receiver does not yet know that there was a transmission error. In order to determine this, the receiver calculates its own parity bits for each row and column of data bits (not including the parity bits that the sender sent) and compares them to the parity bits that the sender sent. If the parity columns differ in any location or the parity rows differ in any location, then that row and column indicate where the flipped bit is.

Below, the upper left 8×8 square of bits with the white background is called the payload. The parity bits calculated by the sender are shown with a gold background. Together the payload and the calculated parity bits make up the whole 9×9 frame. The parity bits calculated by the receiver are shown in green. The receiver compares the received parity bits to the calculated parity bits, and determines that one of the rows and one of the columns contains an error. The intersection of this row and column indicates where the error is:

0 1 0 1
1 1 1 0
1 1 0 0
1 0 1 0
0 1 0 0
1 0 0 0
1 0 1 1
0 0 1 1

0 1 0 1 00
1 1 1 0 00
0 1 0 1 00
1 0 1 0 00
0 0 1 0 1 0 ← parity mismatch in this row 0 1 1 0 11

0 0 0 0 11 1 1 0 1 11 0
1

↑

101 0

101 0

6

parity mismatch in this column

The receiver knows that the 0 in the middle of the 8×8 payload block of bits is incorrect, so the correct value must be 1, and it simply flips the bit to correct it, and then discards all the parity information, leaving the original 8×8 matrix of bits.

0101010 1 1110111 0 1100010 1 1010101 0 0100 1010 1000011 0 1011000 0 0011110 1

6. Assignment

Write the functions shown in the following sections. Be sure to place internal docstring comments in each of your functions. Each comment must describe briefly what the function does, and also how to call the function.

The program consists of three phases, neatly divided into three parts:

1. Encoding: a string is encoded as bits with parity.
2. Transmission: noise is added to the signal to simulate transmission over a noisy

   channel.

3. Decoding: the bits with parity are decoded back into a string.

6.0. Preliminaries
6.0.1. Read the background

I know you skipped it because it was tl;dr. But just do it. It’s part of the assignment. You’ll learn stuff you need to know to complete this assignment, and stuff you’ll need to know for the final exam.

7

6.0.2. New file

In your CSE1010 folder create a new folder for this assignment.

Copy your program file from the Error Detection assignment into this assignment folder before you begin. Whatever you named that file in the last project, rename it to errordetection.py.

Start a new file called errorcorrection.py. In that file put this comment block at the top:

# Error Correction
# CSE1010 Homework 6, Spring 2018
# Your name goes here
# The current date goes here
# TA: Your TA’s name goes here
# Section: Your section number goes here
# Instructor: Jeffrey A. Meunier or Joe Johnson (choose one)

Then import the errordetection module. 6.1. Encoding Phase

6.1.1. Function string2bin

This function takes a string and converts it into a list of bit lists. Each row in the list (meaning each inner list) contains the bits that encode the ASCII value for a single character. Use the char2bin function that you already wrote.

This function iterates over the string, converting each character into a list of bits, and appends each list to the list of lists.

Write this function.

Testing

>>> string2bin('a')
[[0, 1, 1, 0, 0, 0, 0, 1]]

>>> string2bin('abc')
[[0, 1, 1, 0, 0, 0, 0, 1], [0, 1, 1, 0, 0, 0, 1, 0],

8

[0, 1, 1, 0, 0, 0, 1, 1]]

6.1.2. Function segmentString

This function takes any string and a fill character, and returns a list of 8-character strings with any extra space filled by the fill character.

Here’s an example:

\/\/ 8 characters 8 characters

Notice that the second string is padded with the “-” fill character in order to make it 8 characters long.

Write this function. I give hints below.

Be sure that your program works correctly when the input string is a multiple of 8 characters in length. In other words this is correct:

but this is not correct:

Any string that has a length 8 or less should return 1 segment:

Note that the fill character is completely arbitrary. It’s just a character that we specify to fill out the string to 8 characters.

There are a number of ways to fill a string to a specific length.

>>> segmentString(“Hello, world!”, “-“) [‘Hello, W’, ‘orld!—‘]

>>> segmentString("abcdefgh", "-")
['abcdefgh']

>>> segmentString(“abcdefgh”, “-“) [‘abcdefgh’, ‘——–‘]

>>> segmentString(“abc”, “^”) [‘abc^^^^^’]

9

1. Using a while loop

2. Replicating a character with *

3. Using the ljust method

6.1.3. Function printFrames

Add this function to your program. This will help you debug the next function you need to write. The function is shown below. Just copy & paste it.

In this function, it is assumed that a frame is made up of rows. Each row is a list of bits for a single character. Thus, frames (plural) is a list of frames.

10

Test the function. It’s best to just copy & paste this next statement. This is a list of frames, but there is only one frame in the list. The frame contains 8 rows, and each row has 8 bits.

Now test the printFrames function to see the output. It shows the bits in each row, and decodes the bits in each row into a character.

6.1.4. Function string2frames

This function takes a string of any length and a fill character, and cuts the string it into 8- character segments using the segmentString function, then calls the string2bin function on each segment. The result of each call to string2bin is a frame, so you must append each of

11

these frames to a list of frames.

Write the function.

Here are the steps needed to write this function:

1. Create an empty list in which to store the frames.
2. Segment the string.
3. Iterate over the segments, converting each segment into a frame by calling

   string2bin on it.

4. Append the frame to the list of frames.
5. Return the list of frames.

Testing

The string ‘Hello’ fits into a single frame. Also notice that the last three characters are the fill character, which in this example is a the space character (which has character value 32, which is 25, which is the binary number 00100000).

Let’s try a longer string:

12

The string “Hello, World!” uses two frames.

6.1.5. Function appendParityColumn

This function accepts a frame (a list of bit lists) and a desired parity. It appends a parity bit to each list in the frame. Use the appendParity function that you already wrote in order to append a parity bit to each of the bit lists in the list.

Since the appendParity function does not modify the list you give to it (it returns a new list), you should build a new frame with all the return values from the appendParity function. You might be tempted to store each of the lists back into the original frame, but please don’t do that. If anything in your program doesn’t work correctly it will be very difficult to debug.

Return the new frame from this function. Notice that here I use the printFrames function to print the single frame in each of the variables l1 and l2, but I convert each of them into a list of frames first.

Testing

13

6.1.6. Function transpose

An operation that you’ll need to perform on a frame is a transpose. This essentially rotates the list around the diagonal.

The transpose of this:

     [[1, 1, 1],
      [2, 2, 2],
      [3, 3, 3]]

is this:

The rows become columns and the columns become rows.

Add this next function to your program. You will need this in the next function you need to write. Just copy & paste it:

Test the function.

6.1.7. Function appendParityRow

This function takes a frame and a desired parity, and adds a 9th row of bits that are the parity bits of the columns of the frame. (Did you skip the background section of this document? If you don’t understand what’s going on, that’s probably the reason why.)

It turns out that you can use the appendParityColumn to your advantage here. Even though that function appends a parity column to the end of each row of the frame instead of appending a row at the bottom of the frame, all you need to do is transpose the frame, call appendParityColumn, and then transpose the frame again to return it to the correct orientation.

Testing

[[1, 2, 3],
 [1, 2, 3],
 [1, 2, 3]]

>>> transpose([[1, 1, 1], [2, 2, 2], [3, 3, 3]])
[[1, 2, 3], [1, 2, 3], [1, 2, 3]]

14

Notice that the bits no longer represent the characters “Hello”. Take the second character, the Ê. The bits in that row are:
[0, 1, 1, 0, 0, 1, 0, 1, 0]
which is the same as the number 202. This happened because a 0 was appended to the right-hand side of that list. Thus, the original bits in the list were:

[0, 1, 1, 0, 0, 1, 0, 1]
which is the same as the number 101.

So check it out: Appending a 0 on the right-hand side of a binary number multiplies that number by 2. Removing a 0 from the right-hand side divides by 2. Neat, huh?

Debugging

Here I show the frame of the string “Hello” in various stages. You can use this to debug your function in case it’s not working right.

Here’s the original frame, 8 rows of 8 bits each, using space as the fill character:

Here’s the frame after adding a parity column:

 0 [0, 1, 0, 0, 1, 0, 0, 0, 0]

15

Here’s the frame after transposing:

Here’s the frame after adding a parity column:

Here’s the frame after transposing again:

16

6.1.7. Function appendParityToFrame

This function takes a normal 8×8 frame (8 rows of 8 bits) and a desired parity, and returns a 9×9 frame that has both a column and a row of parity bits appended to it.

Inside this function all you need to do is call the appendParityColumn function first, then call the appendParityRow function on that result, then return that result.

Testing

6.1.8. Function appendParityToFrames

This function takes a list of frames and a desired parity, and it appends a parity row and column to each frame in the list and returns the new list of frames.

Testing

17

 8 [0, 1, 1, 0, 0, 0, 1, 0, 1] Å

Let’s try a longer string now:

6.1.9. Summary

You have now written functions that encode any string into frames that have two- dimensional parity bits appended to them. The parity bits will be used during the decoding phase to determine if any bits were erroneously flipped during transmission.

6.2. Transmission Phase

This is where errors will be introduced into the blocks of bits, simulating the transmission of the bits over a noisy communications channel. Examples of communications channels are: Ethernet network cables, Wi-fi wireless networks, phone lines, fiber optic cables, cable TV cables, even storage media like hard disks and CD or DVD ROM disks can have errors. In fact, no communications channel is perfectly error-free, it’s just that some are much more reliable than others.

18

6.2.1. Function transmitFrames

This function takes a list of frames and an error probability from 0 to 1. Call the addNoise function (from the previous project) on each row of each frame, with the given error probability. Collect the new rows into a new frame, and collect the new frames into a new list of frames. Total up the number of bits flipped in all the frames.

At the end of the function, print the total number of flipped bits and then return the list of new frames from this function.

Hints

You’ll need to use a nested loop: an outer one to iterate over the list of frames, and an inner one to iterate over each row in a frame.

The outer loop builds a new list of frames. The inner loop builds a new frame (list of rows).

The addNoise function returns two values, the new row and the number of bits that were flipped.

(newRow, bitsFlipped) = addNoise(?, ?)

You need to append the new row to the new frame.

You need to append the new frame to the new list of frames.

Testing

Test program:

The for loop in the test program prints pairs of frames: the original frame, and then the frame after “transmitting.”

19

You can see by comparing the symbols to the right of the bit lists that row 5 in the transmitted frame contains a flipped bit when compared to row 5 of the original frame.

Output:

6.3. Decoding Phase

Make sure you read and understand the material in the Introduction section, otherwise this may not make much sense.

6.3.1. Function splitFrame

This function takes a 9×9 frame and splits the frame into 3 pieces: the payload (the upper left 8×8 matrix of data bits), the parity column (but only rows 1 – 8), and the parity row (all 9 columns).

Here I show the 8×8 payload in white, the parity column in orange, and the parity row in green:

20

0 10101010 1 11011100 1 10001010 1 01010100 0 10010101 1 00001101 1 01100001 0 01111011 1 00101010

This function must return three things: the 8×8 payload as a list of lists, the parity column as a list, and the parity row as a list.

I wrote this function using just a single for loop and three new lists: the payload, the parity column, and the parity row.

Don’t iterate over all 9 rows. Iterate over the first 8 rows. The 9th row is a special case.

Test it

After calling splitFrame on that frame, the payload variable contains this list:

[[0, 1, 0, 0, 1, 0, 0, 0], [0, 1, 1, 0, 0, 1, 0, 1], [0, 1, 1, 0, 1,
1, 0, 0], [0, 1, 1, 0, 1, 1, 0, 0], [0, 1, 1, 0, 1, 1, 1, 1], [0, 0,
1, 0, 0, 0, 0, 0], [0, 0, 1, 0, 0, 0, 0, 0], [0, 0, 1, 0, 0, 0, 0, 0]]

I use the printFrames function to display that frame in a pleasant way. This is the output

Payload
 0 [0, 1, 0, 0, 1, 0, 0, 0] H

21

6.3.2. Function checkParityOfFrame

This function must re-calculate the parity of the 8×8 payload and compare it to the column and row parity that was sent as part of the 9×9 frame. If the parity does not match in any location, then an error has been detected.

The function has two parameters: the frame and the desired parity. This function returns two lists: a list of column numbers where a parity error is detected, and a list of row numbers where there a parity error is detected.

To do this, compare the received parity column to the calculated parity column. The rows where the columns do not match (are not equal) indicate the row or rows in the payload where there is an error. Also compare the received parity row to the calculated parity row. The columns where the rows do not match indicate the column or columns in the payload where there is an error.

Hints
Use the splitFrame function to split the frame into the payload, the received parity column, and the received parity row.

Use the appendParityToFrame function to re-calculate the parity of the 8×8 payload. This returns a new frame. Be sure to store it in a variable.

Call the splitFrame function again on this new frame to obtain the payload (which you don’t need), the calculated parity column, and the calculated parity row.

Compare the received parity column list to the calculated parity column list. Make a new list of all the locations where the two lists don’t have equal values.

22

Do the same for the received and calculated parity row lists.

Be REALLY CAREFUL here: as you iterate over the parity column, if you detect an error then you have found the row where there is an error. Likewise, as you iterate over the parity row, then if you detect an error then you have found the column where there is an error.

Testing

Here I have flipped one of the bits in the payload of this frame. Let’s use the checkParityOfFrame function to see where it is:

The output is this:

([4, 8], [3])

There are errors in columns 4 and 8 (counting from 0, don’t forget), and in row 3. Knowing those coordinates, you know which bit in the payload has an error.

If there is a single error at all in the payload then you will see an error in column 8 because that’s the calculated parity for that row. In that situation one of the parity bits in column 8 (which is the 9th column) is different from what was sent, so the parity generation function indicates that there has been a change in that column. It’s fine. We can ignore the 8 in the result shown.

Thus, the error is in column 4 and row 3. This is correct.

6.3.3. Function repairFrame

This function takes a 9×9 frame, a list of error columns, a list of error rows, and tries to repair the frame. The error columns and error rows are the lists returned by the

23

checkParityOfFrame function that you just wrote.
This function repairs the frame in-place, meaning it does not create a new frame from the

old frame. It simply modifies the frame that was given to it.

This function returns just the repair status, which is one of these strings:

• ⁃  ‘NO ERRORS’: means that the frame contained no error
• ⁃  ‘CORRECTED’: means that the frame contained an error and was corrected
• ⁃  ‘PARITY ERROR’: means that one of the parity bits was in error
• ⁃  ‘NOT CORRECTED’: means that the frame contained errors but could not be

  corrected.

  If there is a single bit error in the payload then there will be a single error row indicated, and two error columns indicated: the actual error column, and column 8 (because the parity column will be incorrect).

  If there are two bit errors in the payload then it is not possible to correct the error. Using a pencil and a piece of paper, draw a matrix of bits (4×4 is sufficient), add a parity column and parity row, and flip two bits that are not in the same row or same column. Determine why you can’t locate exactly where the errors are.

  If there is a single bit error either in just the columns or just the rows, then it means that a parity bit itself has been flipped and you can’t correct the error. But when the string is reconstructed from the bits it has no errors in it, because the payload itself had no errors in it.

  The function must work like this:

1. If either there are no error rows or no error columns, then there are no errors in the

8×8 payload portion of the frame, so simply return the repair status ‘NO ERRORS’. ⁃ Consider: If there no error rows but there is an error column (or vice versa),

then the error is in the parity bits themselves and they can safely be ignored.

This case already handles this because I wrote either/or above.

2. If there is exactly 1 error row and exactly 2 error columns and one of those

   columns is column 8, then the error row number and column number indicate which bit in the payload is in error. Flip that bit from a 0 to a 1, or from a 1 to a 0. Return the repair status ‘CORRECTED’.

3. If you get this far then there is an error and it might be a parity error. If there is either no error row or no error column (but you already established in step 1 that one of them has an error) then return the repair status ‘PARITY ERROR’.
4. Otherwise return the repair status ‘NOT CORRECTED’.

24

Testing

Note that these are the 9×9 frames with the parity bits, so the characters are not “Hello”:

25

6.3.4. Function repairFrames

This function takes a list of 9×9 frames and a desired parity. It returns list of repair statuses, one for each frame.

To do this, iterate over all the frames one at a time. For each frame, call the checkParityOfFrame function on it and save the return values. Then take those return values and use them to call the repairFrame function on the same frame and save the return value in a list.

Examine the repair status and depending on its value display one of these messages:

• ⁃  ‘Frame frameNumber has no errors’
• ⁃  ‘Frame frameNumber has been repaired’
• ⁃  ‘Frame frameNumber could not be repaired’

  In each case, frameNumber is the index number of the frame in the list of frames. Testing

Run it

After building frames, after adding an error:

 0 [0, 1, 0, 0, 1, 0, 0, 0] H

26

After correcting errors:

6.3.5. Function stripFrames

This function takes a list of 9×9 frames and removes the parity row and column, returning a list of 8×8 payload-only frames.

27

This function should build a new list of new frames. It should not modify the existing frames in any way.

Testing

The output of this test will be the same as the previous test for the repairFrames function. The only difference is that the loops have been replaced with calls to the stripFrames function.

6.3.6. Function bin2string

This function does the opposite of the string2bin function. It takes a an 8×8 frame and a fill character, and returns the 8-character string encoded by that frame. It does not include any of the fill characters.

The function iterates over each list in the frame, converts each list into a character (use your bin2char function). If the character is the fill character, then exit the loop, otherwise append the character to the end of a list of characters.

Finally join the list into a string and then return the string.

28

Testing

Notice that here I use the tilde character ‘~’ as the fill character. I do that so you can see the characters at the end of the string. It’s hard to see spaces when they appear at the end of the string.

Output:

6.3.7. Function frames2string

This function takes a list of 8×8 frames and a fill character. This function iterates over each frame and converts each frame into a string.

For each frame in the list of frames, call the bin2string function on that block (also with the fill character) and append the returned string to a list of strings.

Join the strings into a single string and return that string.

Testing

This test doesn’t use any of the parity functions. It just tests that a string can be converted into 8×8 frames and then back into a string.

29

Output:

6.4. Main function

This function ties it all together. Do this:

1. Define three variables:

              errorProb = 0.01
              desiredParity = 0 # even
              fillChar = "~" # tilde
   

2. Get a string from the user.
3. Convert that string to frames. Use the fill character variable you already defined.

   Test your program at this point to ensure that it works correctly (i.e., print out those

   frames to be sure they are correct).

4. Append parity to those frames. Use desiredParity. Store the result in a new variable.

30

I call these frames the transmitted frames.
Test your program at this point to ensure that it works correctly (i.e., print out those frames to be sure they are correct).

5. Transmit the new frames (the ones with parity), use errorProb, and store the result in a new variable. I call these new frames the received frames.
   Test your program.
6. Repair the received frames using desiredParity. Save the repair statuses in a variable.
7. Strip the received frames. I call the result the stripped frames.
8. Convert the stripped frames to a string. Use the fillChar variable you defined.
9. Display the string.
10. Display the list containing the repair statuses.

Testing

Enter a string: Hello world!

31

6.5. Program comments

Place the normal comment block at the beginning of your project file, and docstring comments in each function.

7. Report

Create a Microsoft Word or Google Docs or LibreOffice Word file (or some other format that your TA agrees on — ask your TA if you are not sure). Save the file with the name LastName-HW6 with a .doc or .docx format. For example, my report would be named Meunier-HW6.docx.

At the beginning of the document include this information:

Error Correction
CSE1010 Homework 6, Spring 2018
Your name goes here
The current date goes here
TA: Your TA’s name goes here
Section: Your section number goes here Instructor: Jeffrey A. Meunier or Joe Johnson

Be sure to replace the parts that are underlined above, and choose only one instructor.

Now create the following five sections in your document.

1. Introduction

In this section copy & paste the text from the introduction section of this assignment. (It’s not plagiarism if you have permission to copy something. I give you permission.)
2. Inputs & outputs
Describe what kind of values the user is expected to supply, and what kind of values the program displays. Don’t give examples, just describe the information: pretend you’re telling your mom or dad or S.O. about it over the phone. “The user must enter a string, and the program converts the string into bits. Then the program displays the string after simulating transmission of that string over a noisy channel.” Etc. Also describe any

32

constants used in the program (this is the error probability and the parity used, even or odd, and the fill character).
3. Sample run
Copy & paste sample runs. Run the program enough times that you see all four variations of the repair statuses in any frame. Include those four runs.

4. Source code
Copy & paste the contents of your .py file here. You do not need to write anything.

8. Submission

Submit the following things things on HuskyCT:

1. The errorcorrection.py file.
2. The report document.

If for some reason you are not able to submit your files on HuskyCT, email your TA before the deadline. Attach your files to the email.

9. Grading Rubric

Your TA will grade your assignment based on these criteria:

• ⁃  (20 points) The program works correctly
• ⁃  (5 points) The program is formatted neatly and there are comments where they need

  to be — one header comment block at the top of the file and a docstring comment

  in each function.

• ⁃  (5 points) The document contains all the correct information and is formatted

  neatly.

33