CSE1010留学生讲解、Python编程设计调试、Python辅导、讲解printFrames
- 首页 >> Python编程 HW 7: Error Correction
CSE1010 Spring 2019
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 7
6.0. Preliminaries 8
6.1. Encoding Phase 8
6.1.1. Function string2bin 8
6.1.2. Function segmentString 9
6.1.3. Function printFrames 11
6.1.4. Function string2frames 12
6.1.5. Function appendParityColumn 13
6.1.6. Function transpose 14
6.1.7. Function appendParityRow 15
6.1.7. Function appendParityToFrame 17
6.1.8. Function appendParityToFrames 18
6.1.9. Summary 19
6.2. Transmission Phase 19
6.2.1. Function transmitFrames 19
6.3. Decoding Phase 21
6.3.1. Function splitFrame 21
6.3.2. Function checkParityOfFrame 22
6.3.3. Function repairFrame 24
6.3.4. Function repairFrames 26
6.3.5. Function stripFrames 28
6.3.6. Function bin2string 29
6.3.7. Function frames2string 30
6.4. Main function 31
6.5. Program comments 322
7. Report 33
8. Submission 33
9. Grading Rubric 34
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.
WARNING!
In this project you must write quite a few functions, and each function you write
depends on the correctness of the one before it. If you get stuck on a function DO NOT
PROCEED TO THE NEXT FUNCTION UNTIL YOU FIX THE PROBLEM because you will not
get the next function working properly and you will waste time on it.
Also do not proceed to the next function UNTIL YOU HAVE TESTED THE FUNCTION
YOU'RE WORKING ON.
2. Due Date
This project is due by midnight at the end of the day on Sunday, April 21, 2019. A penalty of
20% per day will be deducted from your grade, starting at 12:00:01am.
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.3
More binary numbers and character encoding and decoding.
Functions, functions, and more functions.
This project will not use OOP.
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, 4
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 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 5
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 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:
0 1 0 1 0 1 0 1
1 1 1 0 1 1 1 0
1 1 0 0 0 1 0 1
1 0 1 0 1 0 1 0
0 1 0 0 1 0 1 0
1 0 0 0 0 1 1 0
1 0 1 1 0 0 0 0
0 0 1 1 1 1 0 1
What we would normally do is compute a parity bit for each octet, append it to the octet as a
9
th 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 2 3 4 5 6 7 8 9
1 0 1 0 1 0 1 0 1 0
2 1 1 1 0 1 1 1 0 0
3 1 1 0 0 0 1 0 1 0
4 1 0 1 0 1 0 1 0 0
5 0 1 0 0 1 0 1 0 1
6 1 0 0 0 0 1 1 0 1
7 1 0 1 1 0 0 0 0 1
8 0 0 1 1 1 1 0 1 1
Add a 9th row of parity bits, one bit for each column including the 9th:
1 2 3 4 5 6 7 8 9
1 0 1 0 1 0 1 0 1 0
2 1 1 1 0 1 1 1 0 0
3 1 1 0 0 0 1 0 1 06
4 1 0 1 0 1 0 1 0 0
5 0 1 0 0 1 0 1 0 1
6 1 0 0 0 0 1 1 0 1
7 1 0 1 1 0 0 0 0 1
8 0 0 1 1 1 1 0 1 1
9 1 0 0 1 0 1 0 1 0
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 1 0 1 0 1 0 1 0
1 1 1 0 1 1 1 0 0
1 1 0 0 0 1 0 1 0
1 0 1 0 1 0 1 0 0
0 1 0 0 0 0 1 0 1
1 0 0 0 0 1 1 0 1
1 0 1 1 0 0 0 0 1
0 0 1 1 1 1 0 1 1
1 0 0 1 0 1 0 1 0
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 8x8 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 9x9 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 0 1 0 1 0 0
1 1 1 0 1 1 1 0 0 0
1 1 0 0 0 1 0 1 0 07
1 0 1 0 1 0 1 0 0 0
0 1 0 0 0 0 1 0 1 0 ← parity mismatch in this row
1 0 0 0 0 1 1 0 1 1
1 0 1 1 0 0 0 0 1 1
0 0 1 1 1 1 0 1 1 1
1 0 0 1 0 1 0 1 0
1 0 0 1 1 1 0 1 0
↑
parity mismatch in this column
The receiver knows that the 0 in the middle of the 8x8 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 8x8 matrix of bits.
0 1 0 1 0 1 0 1
1 1 1 0 1 1 1 0
1 1 0 0 0 1 0 1
1 0 1 0 1 0 1 0
0 1 0 0 1 0 1 0
1 0 0 0 0 1 1 0
1 0 1 1 0 0 0 0
0 0 1 1 1 1 0 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.
def string2bin(s):
'''Converts a string to a list of lists of binary numbers.
frame = string2bin(str)
'''
...
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.8
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.
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 8, Fall 2018
# Your name goes here
# The current date goes here
# TA: Your TA's name goes here
# Section: Your section number goes here
# Instructor: Your instructor name goes here
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. It's in the errordetection module.
This function iterates over the string, converting each character into a list of bits, and appends
each list to the list of lists.9
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],
[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:
>>> segmentString("Hello, world!", "-")
['Hello, W', 'orld!---']
\ / \ /
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:
>>> segmentString("abcdefgh", "-")
['abcdefgh']
but this is not correct:
>>> segmentString("abcdefgh", "-")
['abcdefgh', '--------']10
Any string that has a length 8 or less should return 1 segment:
>>> segmentString("abc", "^")
['abc^^^^^']
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.
1. Using a while loop
>>> fillChar = '.'
>>> desiredWidth = 8
>>> s1 = 'abc'
>>> while len(s1) < desiredWidth:
s1 += fillChar
>>> s1
'abc.....'
2. Replicating a character with *
>>> fillChar = '~'
>>> desiredWidth = 8
>>> s1 = 'abc'
>>> diff = desiredWidth - len(s1)
>>> s1 += fillChar * diff
>>> s1
'abc~~~~~'
3. Using the ljust method
>>> fillChar = '+'
>>> desiredWidth = 8
>>> s1 = 'abc'
>>> s1 = s1.ljust(desiredWidth, fillChar)
>>> s1
'abc+++++'
Choose one of those ways to do it and use those statements in the body of the function.11
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, the frames parameter (plural) is a list of frames.
def printFrames(frames):
frameN = 0
for frame in frames:
charN = 0
for bin in frame:
char = bin2char(bin)
print(f"{charN:2}", bin, char)
charN += 1
frameN += 1
print()
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.
>>> frames = [[[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, 1, 1, 0, 0], [0, 0, 1, 0, 0, 0, 0, 0], [0, 1, 1, 1, 0, 1, 1, 1]], [[0, 1, 1, 0, 1, 1, 1, 1],
[0, 1, 1, 1, 0, 0, 1, 0], [0, 1, 1, 0, 1, 1, 0, 0], [0, 1, 1, 0, 0, 1, 0, 0], [0, 0, 1, 0, 0, 0, 0, 1], [0, 1, 1, 1, 1, 1, 1,
0], [0, 1, 1, 1, 1, 1, 1, 0], [0, 1, 1, 1, 1, 1, 1, 0]]]
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.
>>> printFrames(frames)
0 [0, 1, 0, 0, 1, 0, 0, 0] H
1 [0, 1, 1, 0, 0, 1, 0, 1] e
2 [0, 1, 1, 0, 1, 1, 0, 0] l
3 [0, 1, 1, 0, 1, 1, 0, 0] l
4 [0, 1, 1, 0, 1, 1, 1, 1] o
5 [0, 0, 1, 0, 1, 1, 0, 0] ,
6 [0, 0, 1, 0, 0, 0, 0, 0]
7 [0, 1, 1, 1, 0, 1, 1, 1] w
0 [0, 1, 1, 0, 1, 1, 1, 1] o
1 [0, 1, 1, 1, 0, 0, 1, 0] r
2 [0, 1, 1, 0, 1, 1, 0, 0] l
3 [0, 1, 1, 0, 0, 1, 0, 0] d12
4 [0, 0, 1, 0, 0, 0, 0, 1] !
5 [0, 1, 1, 1, 1, 1, 1, 0] ~
6 [0, 1, 1, 1, 1, 1, 1, 0] ~
7 [0, 1, 1, 1, 1, 1, 1, 0] ~
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
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
>>> s = "Hello!"
>>> frames = string2frames(s, ' ')
>>> printFrames(frames)
0 [0, 1, 0, 0, 1, 0, 0, 0] H
1 [0, 1, 1, 0, 0, 1, 0, 1] e
2 [0, 1, 1, 0, 1, 1, 0, 0] l
3 [0, 1, 1, 0, 1, 1, 0, 0] l
4 [0, 1, 1, 0, 1, 1, 1, 1] o
5 [0, 0, 1, 0, 0, 0, 0, 0]
6 [0, 0, 1, 0, 0, 0, 0, 0]
7 [0, 0, 1, 0, 0, 0, 0, 0]
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
2
5
, which is the binary number 00100000).
Let's try a longer string:13
>>> s = "Hello, World!"
>>> frames = string2frames(s, ' ')
>>> printFrames(frames)
0 [0, 1, 0, 0, 1, 0, 0, 0] H
1 [0, 1, 1, 0, 0, 1, 0, 1] e
2 [0, 1, 1, 0, 1, 1, 0, 0] l
3 [0, 1, 1, 0, 1, 1, 0, 0] l
4 [0, 1, 1, 0, 1, 1, 1, 1] o
5 [0, 0, 1, 0, 1, 1, 0, 0] ,
6 [0, 0, 1, 0, 0, 0, 0, 0]
7 [0, 1, 0, 1, 0, 1, 1, 1] W
0 [0, 1, 1, 0, 1, 1, 1, 1] o
1 [0, 1, 1, 1, 0, 0, 1, 0] r
2 [0, 1, 1, 0, 1, 1, 0, 0] l
3 [0, 1, 1, 0, 0, 1, 0, 0] d
4 [0, 0, 1, 0, 0, 0, 0, 1] !
5 [0, 0, 1, 0, 0, 0, 0, 0]
6 [0, 0, 1, 0, 0, 0, 0, 0]
7 [0, 0, 1, 0, 0, 0, 0, 0]
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
>>> l1 = [[0, 1, 1, 0, 0, 0, 0, 1], [0, 1, 1, 0, 0, 0, 1, 0], [0, 1, 1, 0, 0, 0, 1, 1]]
>>> printFrames([l1]) # convert l1 to list of frames first14
0 [0, 1, 1, 0, 0, 0, 0, 1] a
1 [0, 1, 1, 0, 0, 0, 1, 0] b
2 [0, 1, 1, 0, 0, 0, 1, 1] c
>>> l2 = appendParityColumn(l1, 0)
>>> printFrames([l2]) # convert l2 to list of frames first
0 [0, 1, 1, 0, 0, 0, 0, 1, 1] ?
1 [0, 1, 1, 0, 0, 0, 1, 0, 1] ?
2 [0, 1, 1, 0, 0, 0, 1, 1, 0] ?
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:
[[1, 2, 3],
[1, 2, 3],
[1, 2, 3]]
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:
def transpose(lst):
lst = list(map(list, zip(*lst)))
return lst
Test the function.
>>> transpose([[1, 1, 1], [2, 2, 2], [3, 3, 3]])
[[1, 2, 3], [1, 2, 3], [1, 2, 3]]15
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
>>> frames = string2frames("Hello", " ")
>>> even = 0
>>> f0 = frames[0]
>>> f1 = appendParityColumn(f0, even)
>>> f2 = appendParityRow(f1, even)
>>> printFrames([f2]) # convert f2 to list of frames first
0 [0, 1, 0, 0, 1, 0, 0, 0, 0] ?
1 [0, 1, 1, 0, 0, 1, 0, 1, 0] ê
2 [0, 1, 1, 0, 1, 1, 0, 0, 0] ?
3 [0, 1, 1, 0, 1, 1, 0, 0, 0] ?
4 [0, 1, 1, 0, 1, 1, 1, 1, 0] T
5 [0, 0, 1, 0, 0, 0, 0, 0, 1] A
6 [0, 0, 1, 0, 0, 0, 0, 0, 1] A
7 [0, 0, 1, 0, 0, 0, 0, 0, 1] A
8 [0, 1, 1, 0, 0, 0, 1, 0, 1] ?
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 righthand
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?
Debugging16
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:
0 [0, 1, 0, 0, 1, 0, 0, 0] H
1 [0, 1, 1, 0, 0, 1, 0, 1] e
2 [0, 1, 1, 0, 1, 1, 0, 0] l
3 [0, 1, 1, 0, 1, 1, 0, 0] l
4 [0, 1, 1, 0, 1, 1, 1, 1] o
5 [0, 0, 1, 0, 0, 0, 0, 0]
6 [0, 0, 1, 0, 0, 0, 0, 0]
7 [0, 0, 1, 0, 0, 0, 0, 0]
Here's the frame after adding a parity column:
0 [0, 1, 0, 0, 1, 0, 0, 0, 0] ?
1 [0, 1, 1, 0, 0, 1, 0, 1, 0] ê
2 [0, 1, 1, 0, 1, 1, 0, 0, 0] ?
3 [0, 1, 1, 0, 1, 1, 0, 0, 0] ?
4 [0, 1, 1, 0, 1, 1, 1, 1, 0] T
5 [0, 0, 1, 0, 0, 0, 0, 0, 1] A
6 [0, 0, 1, 0, 0, 0, 0, 0, 1] A
7 [0, 0, 1, 0, 0, 0, 0, 0, 1] A
Here's the frame after transposing:
0 [0, 0, 0, 0, 0, 0, 0, 0]
1 [1, 1, 1, 1, 1, 0, 0, 0] ?
2 [0, 1, 1, 1, 1, 1, 1, 1]
3 [0, 0, 0, 0, 0, 0, 0, 0]
4 [1, 0, 1, 1, 1, 0, 0, 0] ?
5 [0, 1, 1, 1, 1, 0, 0, 0] x
6 [0, 0, 0, 0, 1, 0, 0, 0]
7 [0, 1, 0, 0, 1, 0, 0, 0] H
8 [0, 0, 0, 0, 0, 1, 1, 1]
Here's the frame after adding a parity column:
0 [0, 0, 0, 0, 0, 0, 0, 0, 0]
1 [1, 1, 1, 1, 1, 0, 0, 0, 1] ?
2 [0, 1, 1, 1, 1, 1, 1, 1, 1] ?
3 [0, 0, 0, 0, 0, 0, 0, 0, 0]
4 [1, 0, 1, 1, 1, 0, 0, 0, 0] ?
5 [0, 1, 1, 1, 1, 0, 0, 0, 0] e
6 [0, 0, 0, 0, 1, 0, 0, 0, 1]
7 [0, 1, 0, 0, 1, 0, 0, 0, 0] ?17
8 [0, 0, 0, 0, 0, 1, 1, 1, 1]
Here's the frame after transposing again:
0 [0, 1, 0, 0, 1, 0, 0, 0, 0] ?
1 [0, 1, 1, 0, 0, 1, 0, 1, 0] ê
2 [0, 1, 1, 0, 1, 1, 0, 0, 0] ?
3 [0, 1, 1, 0, 1, 1, 0, 0, 0] ?
4 [0, 1, 1, 0, 1, 1, 1, 1, 0] T
5 [0, 0, 1, 0, 0, 0, 0, 0, 1] A
6 [0, 0, 1, 0, 0, 0, 0, 0, 1] A
7 [0, 0, 1, 0, 0, 0, 0, 0, 1] A
8 [0, 1, 1, 0, 0, 0, 1, 0, 1] ?
6.1.7. Function appendParityToFrame
This function takes a normal 8x8 frame (8 rows of 8 bits) and a desired parity, and returns a 9x9
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
>>> frames = string2frames('Hello', ' ')
>>> even = 0
>>> f0 = frames[0]
>>> f1 = appendParityToFrame(f0, even)
>>> printFrames([f1]) # convert f1 to list of frames
0 [0, 1, 0, 0, 1, 0, 0, 0, 0] ?
1 [0, 1, 1, 0, 0, 1, 0, 1, 0] ê
2 [0, 1, 1, 0, 1, 1, 0, 0, 0] ?
3 [0, 1, 1, 0, 1, 1, 0, 0, 0] ?
4 [0, 1, 1, 0, 1, 1, 1, 1, 0] T
5 [0, 0, 1, 0, 0, 0, 0, 0, 1] A
6 [0, 0, 1, 0, 0, 0, 0, 0, 1] A
7 [0, 0, 1, 0, 0, 0, 0, 0, 1] A
8 [0, 1, 1, 0, 0, 0, 1, 0, 1] ?18
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
>>> frames = string2frames('Hello', ' ')
>>> even = 0
>>> frames1 = appendParityToFrames(frames, even)
>>> printFrames(frames1)
0 [0, 1, 0, 0, 1, 0, 0, 0, 0] ?
1 [0, 1, 1, 0, 0, 1, 0, 1, 0] ê
2 [0, 1, 1, 0, 1, 1, 0, 0, 0] ?
3 [0, 1, 1, 0, 1, 1, 0, 0, 0] ?
4 [0, 1, 1, 0, 1, 1, 1, 1, 0] T
5 [0, 0, 1, 0, 0, 0, 0, 0, 1] A
6 [0, 0, 1, 0, 0, 0, 0, 0, 1] A
7 [0, 0, 1, 0, 0, 0, 0, 0, 1] A
8 [0, 1, 1, 0, 0, 0, 1, 0, 1] ?
Let's try a longer string now:
>>> frames = string2frames('Hello, world!', ' ')
>>> even = 0
>>> frames1 = appendParityToFrames(frames, even)
>>> printFrames(frames1)
0 [0, 1, 0, 0, 1, 0, 0, 0, 0] ?
1 [0, 1, 1, 0, 0, 1, 0, 1, 0] ê
2 [0, 1, 1, 0, 1, 1, 0, 0, 0] ?
3 [0, 1, 1, 0, 1, 1, 0, 0, 0] ?
4 [0, 1, 1, 0, 1, 1, 1, 1, 0] T
5 [0, 0, 1, 0, 1, 1, 0, 0, 1] Y
6 [0, 0, 1, 0, 0, 0, 0, 0, 1] A
7 [0, 1, 1, 1, 0, 1, 1, 1, 0] ?
8 [0, 0, 1, 1, 1, 0, 0, 1, 0] r
0 [0, 1, 1, 0, 1, 1, 1, 1, 0] T
1 [0, 1, 1, 1, 0, 0, 1, 0, 0] ?
2 [0, 1, 1, 0, 1, 1, 0, 0, 0] ?
3 [0, 1, 1, 0, 0, 1, 0, 0, 1] é
4 [0, 0, 1, 0, 0, 0, 0, 1, 0] B
5 [0, 0, 1, 0, 0, 0, 0, 0, 1] A
6 [0, 0, 1, 0, 0, 0, 0, 0, 1] A
7 [0, 0, 1, 0, 0, 0, 0, 0, 1] A19
8 [0, 0, 0, 1, 0, 1, 0, 0, 0] (
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.
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(?, ?)20
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:
frames = string2frames('Hello', ' ')
even = 0
odd = 1
parity = even
frames1 = appendParityToFrames(frames, parity)
printFrames(frames1)
newFrames = transmitFrames(frames1, 0.01)
for (n, (f1, f2)) in enumerate(zip(frames1, newFrames)):
print("FRAME", n)
printFrames([f1])
printFrames([f2])
The for loop in the test program prints pairs of frames: the original frame, and then the frame
after "transmitting."
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
Number of bits flipped: 1
FRAME 0
Frame 0 (original frame)
0 [0, 1, 0, 0, 1, 0, 0, 0, 0] ?
1 [0, 1, 1, 0, 0, 1, 0, 1, 0] ê
2 [0, 1, 1, 0, 1, 1, 0, 0, 0] ?
3 [0, 1, 1, 0, 1, 1, 0, 0, 0] ?
4 [0, 1, 1, 0, 1, 1, 1, 1, 0] T
5 [0, 0, 1, 0, 0, 0, 0, 0, 1] A
6 [0, 0, 1, 0, 0, 0, 0, 0, 1] A
7 [0, 0, 1, 0, 0, 0, 0, 0, 1] A
8 [0, 1, 1, 0, 0, 0, 1, 0, 1] ?
Frame 0 (transmitted frame)
0 [0, 1, 0, 0, 1, 0, 0, 0, 0] ?
1 [0, 1, 1, 0, 0, 1, 0, 1, 0] ê
2 [0, 1, 1, 0, 1, 1, 0, 0, 0] ?21
3 [0, 1, 1, 0, 1, 1, 0, 0, 0] ?
4 [0, 1, 1, 0, 1, 1, 1, 1, 0] T
5 [0, 0, 1, 0, 0, 0, 1, 0, 1] E
6 [0, 0, 1, 0, 0, 0, 0, 0, 1] A
7 [0, 0, 1, 0, 0, 0, 0, 0, 1] A
8 [0, 1, 1, 0, 0, 0, 1, 0, 1] ?
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 9x9 frame and splits the frame into 3 pieces: the payload (the upper left
8x8 matrix of data bits), the parity column (but only rows 1 - 8), and the parity row (all 9
columns).
Here I show the 8x8 payload in white, the parity column in orange, and the parity row in green:
0 1 0 1 0 1 0 1 0
1 1 1 0 1 1 1 0 0
1 1 0 0 0 1 0 1 0
1 0 1 0 1 0 1 0 0
0 1 0 0 1 0 1 0 1
1 0 0 0 0 1 1 0 1
1 0 1 1 0 0 0 0 1
0 0 1 1 1 1 0 1 1
1 0 0 1 0 1 0 1 0
This function must return three things: the 8x8 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
Here's a test program you can use to test this function.22
# build a frame
frames = string2frames('Hello', ' ')
frame = frames[0]
even = 0
frame1 = appendParityToFrame(frame, even)
# now split the frame
(bits, col, row) = splitFrame(frame1)
print("Payload")
printFrames([bits])
print("Parity column")
print(col)
print("Parity row")
print(row)
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
1 [0, 1, 1, 0, 0, 1, 0, 1] e
2 [0, 1, 1, 0, 1, 1, 0, 0] l
3 [0, 1, 1, 0, 1, 1, 0, 0] l
4 [0, 1, 1, 0, 1, 1, 1, 1] o
5 [0, 0, 1, 0, 0, 0, 0, 0]
6 [0, 0, 1, 0, 0, 0, 0, 0]
7 [0, 0, 1, 0, 0, 0, 0, 0]
Parity column
[0, 0, 0, 0, 0, 1, 1, 1]
Parity row
[0, 1, 1, 0, 0, 0, 1, 0, 1]
6.3.2. Function checkParityOfFrame
This function must re-calculate the parity of the 8x8 payload and compare it to the column and 23
row parity that was sent as part of the 9x9 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 a
tuple of two lists:
1. a list of column numbers where a parity error is detected
2. 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 8x8 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.
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:
# build a frame
frames = string2frames('Hello', ' ')
frame = frames[0]24
even = 0
frame1 = appendParityToFrame(frame, even)
# flip a bit in the frame: row 3, column 4
frame1[3][4] = 1 - frame1[3][4]
# check the parity
res = checkParityOfFrame(frame1, even)
print(res)
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 9x9 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 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 25
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 (4x4 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 there are no error rows and there are no error columns, then there are no errors in
the 8x8 payload portion of the frame, so simply return the repair status 'NO ERRORS'.
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'.
Testing
# build a frame
frames = string2frames('Hello', ' ')
frame = frames[0]
even = 0
frame1 = appendParityToFrame(frame, even)
# flip a bit in the frame: row 3, column 4
frame1[3][4] = 1 - frame1[3][4]
print("With an error:")
printFrames([frame1])
(errCols, errRows) = checkParityOfFrame(frame1, 0)
print(errCols, errRows)
status = repairFrame(frame1, errCols, errRows)
print(status)
printFrames([frame1])26
Note that these are the 9x9 frames with the parity bits, so the characters are not "Hello":
With an error:
0 [0, 1, 0, 0, 1, 0, 0, 0, 0] ?
1 [0, 1, 1, 0, 0, 1, 0, 1, 0] ê
2 [0, 1, 1, 0, 1, 1, 0, 0, 0] ?
3 [0, 1, 1, 0, 0, 1, 0, 0, 0] è (the error is in this row, column 4)
4 [0, 1, 1, 0, 1, 1, 1, 1, 0] T
5 [0, 0, 1, 0, 0, 0, 0, 0, 1] A
6 [0, 0, 1, 0, 0, 0, 0, 0, 1] A
7 [0, 0, 1, 0, 0, 0, 0, 0, 1] A
8 [0, 1, 1, 0, 0, 0, 1, 0, 1] ?
[4, 8] [3]
CORRECTED
0 [0, 1, 0, 0, 1, 0, 0, 0, 0] ?
1 [0, 1, 1, 0, 0, 1, 0, 1, 0] ê
2 [0, 1, 1, 0, 1, 1, 0, 0, 0] ?
3 [0, 1, 1, 0, 1, 1, 0, 0, 0] ? (the error has been corrected)
4 [0, 1, 1, 0, 1, 1, 1, 1, 0] T
5 [0, 0, 1, 0, 0, 0, 0, 0, 1] A
6 [0, 0, 1, 0, 0, 0, 0, 0, 1] A
7 [0, 0, 1, 0, 0, 0, 0, 0, 1] A
8 [0, 1, 1, 0, 0, 0, 1, 0, 1] ?
6.3.4. Function repairFrames
This function takes a list of 9x9 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.27
Testing
# build frames
frames = string2frames("Hello, world!", " ")
even = 0
odd = 1
parity = even
frames = appendParityToFrames(frames, parity)
# flip a bit in frame 0
frames[0][3][4] = 1 - frames[0][3][4]
# display the frames with the error
for frame in frames:
(payload, _, _) = splitFrame(frame)
printFrames([payload])
# repair the frames
results = repairFrames(frames, parity)
# display the frames after correcting the error
for frame in frames:
(payload, _, _) = splitFrame(frame)
printFrames([payload])
Run it
After building frames, after adding an error:
0 [0, 1, 0, 0, 1, 0, 0, 0] H
1 [0, 1, 1, 0, 0, 1, 0, 1] e
2 [0, 1, 1, 0, 1, 1, 0, 0] l
3 [0, 1, 1, 0, 0, 1, 0, 0] d (there is an error in this row)
4 [0, 1, 1, 0, 1, 1, 1, 1] o
5 [0, 0, 1, 0, 1, 1, 0, 0] ,
6 [0, 0, 1, 0, 0, 0, 0, 0]
7 [0, 1, 1, 1, 0, 1, 1, 1] w
0 [0, 1, 1, 0, 1, 1, 1, 1] o
1 [0, 1, 1, 1, 0, 0, 1, 0] r
2 [0, 1, 1, 0, 1, 1, 0, 0] l
3 [0, 1, 1, 0, 0, 1, 0, 0] d
4 [0, 0, 1, 0, 0, 0, 0, 1] !
5 [0, 0, 1, 0, 0, 0, 0, 0]
6 [0, 0, 1, 0, 0, 0, 0, 0] 28
7 [0, 0, 1, 0, 0, 0, 0, 0]
After correcting errors:
Frame 0 has been repaired
Frame 1 has no errors
0 [0, 1, 0, 0, 1, 0, 0, 0] H
1 [0, 1, 1, 0, 0, 1, 0, 1] e
2 [0, 1, 1, 0, 1, 1, 0, 0] l
3 [0, 1, 1, 0, 1, 1, 0, 0] l (the error in this row has been fixed!)
4 [0, 1, 1, 0, 1, 1, 1, 1] o
5 [0, 0, 1, 0, 1, 1, 0, 0] ,
6 [0, 0, 1, 0, 0, 0, 0, 0]
7 [0, 1, 1, 1, 0, 1, 1, 1] w
0 [0, 1, 1, 0, 1, 1, 1, 1] o
1 [0, 1, 1, 1, 0, 0, 1, 0] r
2 [0, 1, 1, 0, 1, 1, 0, 0] l
3 [0, 1, 1, 0, 0, 1, 0, 0] d
4 [0, 0, 1, 0, 0, 0, 0, 1] !
5 [0, 0, 1, 0, 0, 0, 0, 0]
6 [0, 0, 1, 0, 0, 0, 0, 0]
7 [0, 0, 1, 0, 0, 0, 0, 0]
6.3.5. Function stripFrames
This function takes a list of 9x9 frames and removes the parity row and column, returning a list
of 8x8 payload-only frames.
This function should build a new list of new frames. It should not modify the existing frames in
any way.
Testing
# build frames
frames = string2frames("Hello, world!", " ")
even = 0
odd = 1
parity = even
frames = appendParityToFrames(frames, parity)
# flip a bit in frame 0
frames[0][3][4] = 1 - frames[0][3][4]29
# display the frames with the error
payloadFrames = stripFrames(frames)
printFrames(payloadFrames)
# repair the frames
results = repairFrames(frames, parity)
# display the frames after correcting the error
payloadFrames = stripFrames(frames)
printFrames(payloadFrames)
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 8x8 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.
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.
s = segmentString("Hello", "~")
# segmentString returns a list of strings, we want just the first one
s = s[0]
print("Original string:", s)
frame = string2bin(s)
print("Frame:")
printFrames([frame])
str = bin2string(frame, "~")
print("Converted string:", str)30
Output:
Original string: Hello~~~
Frame:
0 [0, 1, 0, 0, 1, 0, 0, 0] H
1 [0, 1, 1, 0, 0, 1, 0, 1] e
2 [0, 1, 1, 0, 1, 1, 0, 0] l
3 [0, 1, 1, 0, 1, 1, 0, 0] l
4 [0, 1, 1, 0, 1, 1, 1, 1] o
5 [0, 1, 1, 1, 1, 1, 1, 0] ~
6 [0, 1, 1, 1, 1, 1, 1, 0] ~
7 [0, 1, 1, 1, 1, 1, 1, 0] ~
Converted string: Hello
6.3.7. Function frames2string
This function takes a list of 8x8 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
8x8 frames and then back into a string.
string = "Hello, world!"
fillChar = "~"
frames = string2frames(string, fillChar)
print("Original frames")
printFrames(frames)
string = frames2string(frames, fillChar)
print("Converted string:", string)
Output:
Original frames
0 [0, 1, 0, 0, 1, 0, 0, 0] H
1 [0, 1, 1, 0, 0, 1, 0, 1] e
2 [0, 1, 1, 0, 1, 1, 0, 0] l31
3 [0, 1, 1, 0, 1, 1, 0, 0] l
4 [0, 1, 1, 0, 1, 1, 1, 1] o
5 [0, 0, 1, 0, 1, 1, 0, 0] ,
6 [0, 0, 1, 0, 0, 0, 0, 0]
7 [0, 1, 1, 1, 0, 1, 1, 1] w
0 [0, 1, 1, 0, 1, 1, 1, 1] o
1 [0, 1, 1, 1, 0, 0, 1, 0] r
2 [0, 1, 1, 0, 1, 1, 0, 0] l
3 [0, 1, 1, 0, 0, 1, 0, 0] d
4 [0, 0, 1, 0, 0, 0, 0, 1] !
5 [0, 1, 1, 1, 1, 1, 1, 0] ~
6 [0, 1, 1, 1, 1, 1, 1, 0] ~
7 [0, 1, 1, 1, 1, 1, 1, 0] ~
Converted string: Hello, world!
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. 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.32
Testing
Enter a string: Hello world!
Number of bits flipped: 0
Frame 0 has no errors
Frame 1 has no errors
Hello, world!
['NO ERRORS', 'NO ERRORS']
Enter a string: Hello world!
Number of bits flipped: 1
Frame 0 has no errors
Frame 1 has been repaired
Hello, world!
['NO ERRORS', 'CORRECTED']
Enter a string: Hello world!
Number of bits flipped: 3
Frame 0 has been repaired
Frame 1 could not be repaired
Hello, wmrld
['CORRECTED', 'NOT CORRECTED']
Enter a string: Hello world!
Number of bits flipped: 4
Frame 0 could not be repaired
Frame 1 could not be repaired
HuLlo, wobld!
['NOT CORRECTED', 'NOT CORRECTED']
Enter a string: Hello world!
Number of bits flipped: 2
Frame 0 has been repaired
Hello, world!
['CORRECTED', 'PARITY ERROR']
6.5. Program comments
Place the normal comment block at the beginning of your project file, and docstring comments
in each function.33
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 LastNameHW7
with a .doc or .docx format.
At the beginning of the document include this information:
Error Correction
CSE1010 Homework 7, Spring 2019
your name goes here
the current date goes here
TA: your TA's name goes here
Lab section: your lab section number goes here
Instructor: your lecturer's name goes here
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 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. If HuskyCT complains that uploading a Python file is a 34
security threat, then compress your file into a zip file and then submit the zip 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.
CSE1010 Spring 2019
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 7
6.0. Preliminaries 8
6.1. Encoding Phase 8
6.1.1. Function string2bin 8
6.1.2. Function segmentString 9
6.1.3. Function printFrames 11
6.1.4. Function string2frames 12
6.1.5. Function appendParityColumn 13
6.1.6. Function transpose 14
6.1.7. Function appendParityRow 15
6.1.7. Function appendParityToFrame 17
6.1.8. Function appendParityToFrames 18
6.1.9. Summary 19
6.2. Transmission Phase 19
6.2.1. Function transmitFrames 19
6.3. Decoding Phase 21
6.3.1. Function splitFrame 21
6.3.2. Function checkParityOfFrame 22
6.3.3. Function repairFrame 24
6.3.4. Function repairFrames 26
6.3.5. Function stripFrames 28
6.3.6. Function bin2string 29
6.3.7. Function frames2string 30
6.4. Main function 31
6.5. Program comments 322
7. Report 33
8. Submission 33
9. Grading Rubric 34
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.
WARNING!
In this project you must write quite a few functions, and each function you write
depends on the correctness of the one before it. If you get stuck on a function DO NOT
PROCEED TO THE NEXT FUNCTION UNTIL YOU FIX THE PROBLEM because you will not
get the next function working properly and you will waste time on it.
Also do not proceed to the next function UNTIL YOU HAVE TESTED THE FUNCTION
YOU'RE WORKING ON.
2. Due Date
This project is due by midnight at the end of the day on Sunday, April 21, 2019. A penalty of
20% per day will be deducted from your grade, starting at 12:00:01am.
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.3
More binary numbers and character encoding and decoding.
Functions, functions, and more functions.
This project will not use OOP.
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, 4
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 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 5
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 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:
0 1 0 1 0 1 0 1
1 1 1 0 1 1 1 0
1 1 0 0 0 1 0 1
1 0 1 0 1 0 1 0
0 1 0 0 1 0 1 0
1 0 0 0 0 1 1 0
1 0 1 1 0 0 0 0
0 0 1 1 1 1 0 1
What we would normally do is compute a parity bit for each octet, append it to the octet as a
9
th 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 2 3 4 5 6 7 8 9
1 0 1 0 1 0 1 0 1 0
2 1 1 1 0 1 1 1 0 0
3 1 1 0 0 0 1 0 1 0
4 1 0 1 0 1 0 1 0 0
5 0 1 0 0 1 0 1 0 1
6 1 0 0 0 0 1 1 0 1
7 1 0 1 1 0 0 0 0 1
8 0 0 1 1 1 1 0 1 1
Add a 9th row of parity bits, one bit for each column including the 9th:
1 2 3 4 5 6 7 8 9
1 0 1 0 1 0 1 0 1 0
2 1 1 1 0 1 1 1 0 0
3 1 1 0 0 0 1 0 1 06
4 1 0 1 0 1 0 1 0 0
5 0 1 0 0 1 0 1 0 1
6 1 0 0 0 0 1 1 0 1
7 1 0 1 1 0 0 0 0 1
8 0 0 1 1 1 1 0 1 1
9 1 0 0 1 0 1 0 1 0
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 1 0 1 0 1 0 1 0
1 1 1 0 1 1 1 0 0
1 1 0 0 0 1 0 1 0
1 0 1 0 1 0 1 0 0
0 1 0 0 0 0 1 0 1
1 0 0 0 0 1 1 0 1
1 0 1 1 0 0 0 0 1
0 0 1 1 1 1 0 1 1
1 0 0 1 0 1 0 1 0
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 8x8 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 9x9 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 0 1 0 1 0 0
1 1 1 0 1 1 1 0 0 0
1 1 0 0 0 1 0 1 0 07
1 0 1 0 1 0 1 0 0 0
0 1 0 0 0 0 1 0 1 0 ← parity mismatch in this row
1 0 0 0 0 1 1 0 1 1
1 0 1 1 0 0 0 0 1 1
0 0 1 1 1 1 0 1 1 1
1 0 0 1 0 1 0 1 0
1 0 0 1 1 1 0 1 0
↑
parity mismatch in this column
The receiver knows that the 0 in the middle of the 8x8 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 8x8 matrix of bits.
0 1 0 1 0 1 0 1
1 1 1 0 1 1 1 0
1 1 0 0 0 1 0 1
1 0 1 0 1 0 1 0
0 1 0 0 1 0 1 0
1 0 0 0 0 1 1 0
1 0 1 1 0 0 0 0
0 0 1 1 1 1 0 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.
def string2bin(s):
'''Converts a string to a list of lists of binary numbers.
frame = string2bin(str)
'''
...
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.8
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.
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 8, Fall 2018
# Your name goes here
# The current date goes here
# TA: Your TA's name goes here
# Section: Your section number goes here
# Instructor: Your instructor name goes here
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. It's in the errordetection module.
This function iterates over the string, converting each character into a list of bits, and appends
each list to the list of lists.9
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],
[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:
>>> segmentString("Hello, world!", "-")
['Hello, W', 'orld!---']
\ / \ /
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:
>>> segmentString("abcdefgh", "-")
['abcdefgh']
but this is not correct:
>>> segmentString("abcdefgh", "-")
['abcdefgh', '--------']10
Any string that has a length 8 or less should return 1 segment:
>>> segmentString("abc", "^")
['abc^^^^^']
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.
1. Using a while loop
>>> fillChar = '.'
>>> desiredWidth = 8
>>> s1 = 'abc'
>>> while len(s1) < desiredWidth:
s1 += fillChar
>>> s1
'abc.....'
2. Replicating a character with *
>>> fillChar = '~'
>>> desiredWidth = 8
>>> s1 = 'abc'
>>> diff = desiredWidth - len(s1)
>>> s1 += fillChar * diff
>>> s1
'abc~~~~~'
3. Using the ljust method
>>> fillChar = '+'
>>> desiredWidth = 8
>>> s1 = 'abc'
>>> s1 = s1.ljust(desiredWidth, fillChar)
>>> s1
'abc+++++'
Choose one of those ways to do it and use those statements in the body of the function.11
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, the frames parameter (plural) is a list of frames.
def printFrames(frames):
frameN = 0
for frame in frames:
charN = 0
for bin in frame:
char = bin2char(bin)
print(f"{charN:2}", bin, char)
charN += 1
frameN += 1
print()
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.
>>> frames = [[[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, 1, 1, 0, 0], [0, 0, 1, 0, 0, 0, 0, 0], [0, 1, 1, 1, 0, 1, 1, 1]], [[0, 1, 1, 0, 1, 1, 1, 1],
[0, 1, 1, 1, 0, 0, 1, 0], [0, 1, 1, 0, 1, 1, 0, 0], [0, 1, 1, 0, 0, 1, 0, 0], [0, 0, 1, 0, 0, 0, 0, 1], [0, 1, 1, 1, 1, 1, 1,
0], [0, 1, 1, 1, 1, 1, 1, 0], [0, 1, 1, 1, 1, 1, 1, 0]]]
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.
>>> printFrames(frames)
0 [0, 1, 0, 0, 1, 0, 0, 0] H
1 [0, 1, 1, 0, 0, 1, 0, 1] e
2 [0, 1, 1, 0, 1, 1, 0, 0] l
3 [0, 1, 1, 0, 1, 1, 0, 0] l
4 [0, 1, 1, 0, 1, 1, 1, 1] o
5 [0, 0, 1, 0, 1, 1, 0, 0] ,
6 [0, 0, 1, 0, 0, 0, 0, 0]
7 [0, 1, 1, 1, 0, 1, 1, 1] w
0 [0, 1, 1, 0, 1, 1, 1, 1] o
1 [0, 1, 1, 1, 0, 0, 1, 0] r
2 [0, 1, 1, 0, 1, 1, 0, 0] l
3 [0, 1, 1, 0, 0, 1, 0, 0] d12
4 [0, 0, 1, 0, 0, 0, 0, 1] !
5 [0, 1, 1, 1, 1, 1, 1, 0] ~
6 [0, 1, 1, 1, 1, 1, 1, 0] ~
7 [0, 1, 1, 1, 1, 1, 1, 0] ~
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
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
>>> s = "Hello!"
>>> frames = string2frames(s, ' ')
>>> printFrames(frames)
0 [0, 1, 0, 0, 1, 0, 0, 0] H
1 [0, 1, 1, 0, 0, 1, 0, 1] e
2 [0, 1, 1, 0, 1, 1, 0, 0] l
3 [0, 1, 1, 0, 1, 1, 0, 0] l
4 [0, 1, 1, 0, 1, 1, 1, 1] o
5 [0, 0, 1, 0, 0, 0, 0, 0]
6 [0, 0, 1, 0, 0, 0, 0, 0]
7 [0, 0, 1, 0, 0, 0, 0, 0]
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
2
5
, which is the binary number 00100000).
Let's try a longer string:13
>>> s = "Hello, World!"
>>> frames = string2frames(s, ' ')
>>> printFrames(frames)
0 [0, 1, 0, 0, 1, 0, 0, 0] H
1 [0, 1, 1, 0, 0, 1, 0, 1] e
2 [0, 1, 1, 0, 1, 1, 0, 0] l
3 [0, 1, 1, 0, 1, 1, 0, 0] l
4 [0, 1, 1, 0, 1, 1, 1, 1] o
5 [0, 0, 1, 0, 1, 1, 0, 0] ,
6 [0, 0, 1, 0, 0, 0, 0, 0]
7 [0, 1, 0, 1, 0, 1, 1, 1] W
0 [0, 1, 1, 0, 1, 1, 1, 1] o
1 [0, 1, 1, 1, 0, 0, 1, 0] r
2 [0, 1, 1, 0, 1, 1, 0, 0] l
3 [0, 1, 1, 0, 0, 1, 0, 0] d
4 [0, 0, 1, 0, 0, 0, 0, 1] !
5 [0, 0, 1, 0, 0, 0, 0, 0]
6 [0, 0, 1, 0, 0, 0, 0, 0]
7 [0, 0, 1, 0, 0, 0, 0, 0]
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
>>> l1 = [[0, 1, 1, 0, 0, 0, 0, 1], [0, 1, 1, 0, 0, 0, 1, 0], [0, 1, 1, 0, 0, 0, 1, 1]]
>>> printFrames([l1]) # convert l1 to list of frames first14
0 [0, 1, 1, 0, 0, 0, 0, 1] a
1 [0, 1, 1, 0, 0, 0, 1, 0] b
2 [0, 1, 1, 0, 0, 0, 1, 1] c
>>> l2 = appendParityColumn(l1, 0)
>>> printFrames([l2]) # convert l2 to list of frames first
0 [0, 1, 1, 0, 0, 0, 0, 1, 1] ?
1 [0, 1, 1, 0, 0, 0, 1, 0, 1] ?
2 [0, 1, 1, 0, 0, 0, 1, 1, 0] ?
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:
[[1, 2, 3],
[1, 2, 3],
[1, 2, 3]]
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:
def transpose(lst):
lst = list(map(list, zip(*lst)))
return lst
Test the function.
>>> transpose([[1, 1, 1], [2, 2, 2], [3, 3, 3]])
[[1, 2, 3], [1, 2, 3], [1, 2, 3]]15
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
>>> frames = string2frames("Hello", " ")
>>> even = 0
>>> f0 = frames[0]
>>> f1 = appendParityColumn(f0, even)
>>> f2 = appendParityRow(f1, even)
>>> printFrames([f2]) # convert f2 to list of frames first
0 [0, 1, 0, 0, 1, 0, 0, 0, 0] ?
1 [0, 1, 1, 0, 0, 1, 0, 1, 0] ê
2 [0, 1, 1, 0, 1, 1, 0, 0, 0] ?
3 [0, 1, 1, 0, 1, 1, 0, 0, 0] ?
4 [0, 1, 1, 0, 1, 1, 1, 1, 0] T
5 [0, 0, 1, 0, 0, 0, 0, 0, 1] A
6 [0, 0, 1, 0, 0, 0, 0, 0, 1] A
7 [0, 0, 1, 0, 0, 0, 0, 0, 1] A
8 [0, 1, 1, 0, 0, 0, 1, 0, 1] ?
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 righthand
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?
Debugging16
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:
0 [0, 1, 0, 0, 1, 0, 0, 0] H
1 [0, 1, 1, 0, 0, 1, 0, 1] e
2 [0, 1, 1, 0, 1, 1, 0, 0] l
3 [0, 1, 1, 0, 1, 1, 0, 0] l
4 [0, 1, 1, 0, 1, 1, 1, 1] o
5 [0, 0, 1, 0, 0, 0, 0, 0]
6 [0, 0, 1, 0, 0, 0, 0, 0]
7 [0, 0, 1, 0, 0, 0, 0, 0]
Here's the frame after adding a parity column:
0 [0, 1, 0, 0, 1, 0, 0, 0, 0] ?
1 [0, 1, 1, 0, 0, 1, 0, 1, 0] ê
2 [0, 1, 1, 0, 1, 1, 0, 0, 0] ?
3 [0, 1, 1, 0, 1, 1, 0, 0, 0] ?
4 [0, 1, 1, 0, 1, 1, 1, 1, 0] T
5 [0, 0, 1, 0, 0, 0, 0, 0, 1] A
6 [0, 0, 1, 0, 0, 0, 0, 0, 1] A
7 [0, 0, 1, 0, 0, 0, 0, 0, 1] A
Here's the frame after transposing:
0 [0, 0, 0, 0, 0, 0, 0, 0]
1 [1, 1, 1, 1, 1, 0, 0, 0] ?
2 [0, 1, 1, 1, 1, 1, 1, 1]
3 [0, 0, 0, 0, 0, 0, 0, 0]
4 [1, 0, 1, 1, 1, 0, 0, 0] ?
5 [0, 1, 1, 1, 1, 0, 0, 0] x
6 [0, 0, 0, 0, 1, 0, 0, 0]
7 [0, 1, 0, 0, 1, 0, 0, 0] H
8 [0, 0, 0, 0, 0, 1, 1, 1]
Here's the frame after adding a parity column:
0 [0, 0, 0, 0, 0, 0, 0, 0, 0]
1 [1, 1, 1, 1, 1, 0, 0, 0, 1] ?
2 [0, 1, 1, 1, 1, 1, 1, 1, 1] ?
3 [0, 0, 0, 0, 0, 0, 0, 0, 0]
4 [1, 0, 1, 1, 1, 0, 0, 0, 0] ?
5 [0, 1, 1, 1, 1, 0, 0, 0, 0] e
6 [0, 0, 0, 0, 1, 0, 0, 0, 1]
7 [0, 1, 0, 0, 1, 0, 0, 0, 0] ?17
8 [0, 0, 0, 0, 0, 1, 1, 1, 1]
Here's the frame after transposing again:
0 [0, 1, 0, 0, 1, 0, 0, 0, 0] ?
1 [0, 1, 1, 0, 0, 1, 0, 1, 0] ê
2 [0, 1, 1, 0, 1, 1, 0, 0, 0] ?
3 [0, 1, 1, 0, 1, 1, 0, 0, 0] ?
4 [0, 1, 1, 0, 1, 1, 1, 1, 0] T
5 [0, 0, 1, 0, 0, 0, 0, 0, 1] A
6 [0, 0, 1, 0, 0, 0, 0, 0, 1] A
7 [0, 0, 1, 0, 0, 0, 0, 0, 1] A
8 [0, 1, 1, 0, 0, 0, 1, 0, 1] ?
6.1.7. Function appendParityToFrame
This function takes a normal 8x8 frame (8 rows of 8 bits) and a desired parity, and returns a 9x9
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
>>> frames = string2frames('Hello', ' ')
>>> even = 0
>>> f0 = frames[0]
>>> f1 = appendParityToFrame(f0, even)
>>> printFrames([f1]) # convert f1 to list of frames
0 [0, 1, 0, 0, 1, 0, 0, 0, 0] ?
1 [0, 1, 1, 0, 0, 1, 0, 1, 0] ê
2 [0, 1, 1, 0, 1, 1, 0, 0, 0] ?
3 [0, 1, 1, 0, 1, 1, 0, 0, 0] ?
4 [0, 1, 1, 0, 1, 1, 1, 1, 0] T
5 [0, 0, 1, 0, 0, 0, 0, 0, 1] A
6 [0, 0, 1, 0, 0, 0, 0, 0, 1] A
7 [0, 0, 1, 0, 0, 0, 0, 0, 1] A
8 [0, 1, 1, 0, 0, 0, 1, 0, 1] ?18
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
>>> frames = string2frames('Hello', ' ')
>>> even = 0
>>> frames1 = appendParityToFrames(frames, even)
>>> printFrames(frames1)
0 [0, 1, 0, 0, 1, 0, 0, 0, 0] ?
1 [0, 1, 1, 0, 0, 1, 0, 1, 0] ê
2 [0, 1, 1, 0, 1, 1, 0, 0, 0] ?
3 [0, 1, 1, 0, 1, 1, 0, 0, 0] ?
4 [0, 1, 1, 0, 1, 1, 1, 1, 0] T
5 [0, 0, 1, 0, 0, 0, 0, 0, 1] A
6 [0, 0, 1, 0, 0, 0, 0, 0, 1] A
7 [0, 0, 1, 0, 0, 0, 0, 0, 1] A
8 [0, 1, 1, 0, 0, 0, 1, 0, 1] ?
Let's try a longer string now:
>>> frames = string2frames('Hello, world!', ' ')
>>> even = 0
>>> frames1 = appendParityToFrames(frames, even)
>>> printFrames(frames1)
0 [0, 1, 0, 0, 1, 0, 0, 0, 0] ?
1 [0, 1, 1, 0, 0, 1, 0, 1, 0] ê
2 [0, 1, 1, 0, 1, 1, 0, 0, 0] ?
3 [0, 1, 1, 0, 1, 1, 0, 0, 0] ?
4 [0, 1, 1, 0, 1, 1, 1, 1, 0] T
5 [0, 0, 1, 0, 1, 1, 0, 0, 1] Y
6 [0, 0, 1, 0, 0, 0, 0, 0, 1] A
7 [0, 1, 1, 1, 0, 1, 1, 1, 0] ?
8 [0, 0, 1, 1, 1, 0, 0, 1, 0] r
0 [0, 1, 1, 0, 1, 1, 1, 1, 0] T
1 [0, 1, 1, 1, 0, 0, 1, 0, 0] ?
2 [0, 1, 1, 0, 1, 1, 0, 0, 0] ?
3 [0, 1, 1, 0, 0, 1, 0, 0, 1] é
4 [0, 0, 1, 0, 0, 0, 0, 1, 0] B
5 [0, 0, 1, 0, 0, 0, 0, 0, 1] A
6 [0, 0, 1, 0, 0, 0, 0, 0, 1] A
7 [0, 0, 1, 0, 0, 0, 0, 0, 1] A19
8 [0, 0, 0, 1, 0, 1, 0, 0, 0] (
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.
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(?, ?)20
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:
frames = string2frames('Hello', ' ')
even = 0
odd = 1
parity = even
frames1 = appendParityToFrames(frames, parity)
printFrames(frames1)
newFrames = transmitFrames(frames1, 0.01)
for (n, (f1, f2)) in enumerate(zip(frames1, newFrames)):
print("FRAME", n)
printFrames([f1])
printFrames([f2])
The for loop in the test program prints pairs of frames: the original frame, and then the frame
after "transmitting."
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
Number of bits flipped: 1
FRAME 0
Frame 0 (original frame)
0 [0, 1, 0, 0, 1, 0, 0, 0, 0] ?
1 [0, 1, 1, 0, 0, 1, 0, 1, 0] ê
2 [0, 1, 1, 0, 1, 1, 0, 0, 0] ?
3 [0, 1, 1, 0, 1, 1, 0, 0, 0] ?
4 [0, 1, 1, 0, 1, 1, 1, 1, 0] T
5 [0, 0, 1, 0, 0, 0, 0, 0, 1] A
6 [0, 0, 1, 0, 0, 0, 0, 0, 1] A
7 [0, 0, 1, 0, 0, 0, 0, 0, 1] A
8 [0, 1, 1, 0, 0, 0, 1, 0, 1] ?
Frame 0 (transmitted frame)
0 [0, 1, 0, 0, 1, 0, 0, 0, 0] ?
1 [0, 1, 1, 0, 0, 1, 0, 1, 0] ê
2 [0, 1, 1, 0, 1, 1, 0, 0, 0] ?21
3 [0, 1, 1, 0, 1, 1, 0, 0, 0] ?
4 [0, 1, 1, 0, 1, 1, 1, 1, 0] T
5 [0, 0, 1, 0, 0, 0, 1, 0, 1] E
6 [0, 0, 1, 0, 0, 0, 0, 0, 1] A
7 [0, 0, 1, 0, 0, 0, 0, 0, 1] A
8 [0, 1, 1, 0, 0, 0, 1, 0, 1] ?
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 9x9 frame and splits the frame into 3 pieces: the payload (the upper left
8x8 matrix of data bits), the parity column (but only rows 1 - 8), and the parity row (all 9
columns).
Here I show the 8x8 payload in white, the parity column in orange, and the parity row in green:
0 1 0 1 0 1 0 1 0
1 1 1 0 1 1 1 0 0
1 1 0 0 0 1 0 1 0
1 0 1 0 1 0 1 0 0
0 1 0 0 1 0 1 0 1
1 0 0 0 0 1 1 0 1
1 0 1 1 0 0 0 0 1
0 0 1 1 1 1 0 1 1
1 0 0 1 0 1 0 1 0
This function must return three things: the 8x8 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
Here's a test program you can use to test this function.22
# build a frame
frames = string2frames('Hello', ' ')
frame = frames[0]
even = 0
frame1 = appendParityToFrame(frame, even)
# now split the frame
(bits, col, row) = splitFrame(frame1)
print("Payload")
printFrames([bits])
print("Parity column")
print(col)
print("Parity row")
print(row)
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
1 [0, 1, 1, 0, 0, 1, 0, 1] e
2 [0, 1, 1, 0, 1, 1, 0, 0] l
3 [0, 1, 1, 0, 1, 1, 0, 0] l
4 [0, 1, 1, 0, 1, 1, 1, 1] o
5 [0, 0, 1, 0, 0, 0, 0, 0]
6 [0, 0, 1, 0, 0, 0, 0, 0]
7 [0, 0, 1, 0, 0, 0, 0, 0]
Parity column
[0, 0, 0, 0, 0, 1, 1, 1]
Parity row
[0, 1, 1, 0, 0, 0, 1, 0, 1]
6.3.2. Function checkParityOfFrame
This function must re-calculate the parity of the 8x8 payload and compare it to the column and 23
row parity that was sent as part of the 9x9 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 a
tuple of two lists:
1. a list of column numbers where a parity error is detected
2. 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 8x8 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.
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:
# build a frame
frames = string2frames('Hello', ' ')
frame = frames[0]24
even = 0
frame1 = appendParityToFrame(frame, even)
# flip a bit in the frame: row 3, column 4
frame1[3][4] = 1 - frame1[3][4]
# check the parity
res = checkParityOfFrame(frame1, even)
print(res)
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 9x9 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 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 25
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 (4x4 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 there are no error rows and there are no error columns, then there are no errors in
the 8x8 payload portion of the frame, so simply return the repair status 'NO ERRORS'.
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'.
Testing
# build a frame
frames = string2frames('Hello', ' ')
frame = frames[0]
even = 0
frame1 = appendParityToFrame(frame, even)
# flip a bit in the frame: row 3, column 4
frame1[3][4] = 1 - frame1[3][4]
print("With an error:")
printFrames([frame1])
(errCols, errRows) = checkParityOfFrame(frame1, 0)
print(errCols, errRows)
status = repairFrame(frame1, errCols, errRows)
print(status)
printFrames([frame1])26
Note that these are the 9x9 frames with the parity bits, so the characters are not "Hello":
With an error:
0 [0, 1, 0, 0, 1, 0, 0, 0, 0] ?
1 [0, 1, 1, 0, 0, 1, 0, 1, 0] ê
2 [0, 1, 1, 0, 1, 1, 0, 0, 0] ?
3 [0, 1, 1, 0, 0, 1, 0, 0, 0] è (the error is in this row, column 4)
4 [0, 1, 1, 0, 1, 1, 1, 1, 0] T
5 [0, 0, 1, 0, 0, 0, 0, 0, 1] A
6 [0, 0, 1, 0, 0, 0, 0, 0, 1] A
7 [0, 0, 1, 0, 0, 0, 0, 0, 1] A
8 [0, 1, 1, 0, 0, 0, 1, 0, 1] ?
[4, 8] [3]
CORRECTED
0 [0, 1, 0, 0, 1, 0, 0, 0, 0] ?
1 [0, 1, 1, 0, 0, 1, 0, 1, 0] ê
2 [0, 1, 1, 0, 1, 1, 0, 0, 0] ?
3 [0, 1, 1, 0, 1, 1, 0, 0, 0] ? (the error has been corrected)
4 [0, 1, 1, 0, 1, 1, 1, 1, 0] T
5 [0, 0, 1, 0, 0, 0, 0, 0, 1] A
6 [0, 0, 1, 0, 0, 0, 0, 0, 1] A
7 [0, 0, 1, 0, 0, 0, 0, 0, 1] A
8 [0, 1, 1, 0, 0, 0, 1, 0, 1] ?
6.3.4. Function repairFrames
This function takes a list of 9x9 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.27
Testing
# build frames
frames = string2frames("Hello, world!", " ")
even = 0
odd = 1
parity = even
frames = appendParityToFrames(frames, parity)
# flip a bit in frame 0
frames[0][3][4] = 1 - frames[0][3][4]
# display the frames with the error
for frame in frames:
(payload, _, _) = splitFrame(frame)
printFrames([payload])
# repair the frames
results = repairFrames(frames, parity)
# display the frames after correcting the error
for frame in frames:
(payload, _, _) = splitFrame(frame)
printFrames([payload])
Run it
After building frames, after adding an error:
0 [0, 1, 0, 0, 1, 0, 0, 0] H
1 [0, 1, 1, 0, 0, 1, 0, 1] e
2 [0, 1, 1, 0, 1, 1, 0, 0] l
3 [0, 1, 1, 0, 0, 1, 0, 0] d (there is an error in this row)
4 [0, 1, 1, 0, 1, 1, 1, 1] o
5 [0, 0, 1, 0, 1, 1, 0, 0] ,
6 [0, 0, 1, 0, 0, 0, 0, 0]
7 [0, 1, 1, 1, 0, 1, 1, 1] w
0 [0, 1, 1, 0, 1, 1, 1, 1] o
1 [0, 1, 1, 1, 0, 0, 1, 0] r
2 [0, 1, 1, 0, 1, 1, 0, 0] l
3 [0, 1, 1, 0, 0, 1, 0, 0] d
4 [0, 0, 1, 0, 0, 0, 0, 1] !
5 [0, 0, 1, 0, 0, 0, 0, 0]
6 [0, 0, 1, 0, 0, 0, 0, 0] 28
7 [0, 0, 1, 0, 0, 0, 0, 0]
After correcting errors:
Frame 0 has been repaired
Frame 1 has no errors
0 [0, 1, 0, 0, 1, 0, 0, 0] H
1 [0, 1, 1, 0, 0, 1, 0, 1] e
2 [0, 1, 1, 0, 1, 1, 0, 0] l
3 [0, 1, 1, 0, 1, 1, 0, 0] l (the error in this row has been fixed!)
4 [0, 1, 1, 0, 1, 1, 1, 1] o
5 [0, 0, 1, 0, 1, 1, 0, 0] ,
6 [0, 0, 1, 0, 0, 0, 0, 0]
7 [0, 1, 1, 1, 0, 1, 1, 1] w
0 [0, 1, 1, 0, 1, 1, 1, 1] o
1 [0, 1, 1, 1, 0, 0, 1, 0] r
2 [0, 1, 1, 0, 1, 1, 0, 0] l
3 [0, 1, 1, 0, 0, 1, 0, 0] d
4 [0, 0, 1, 0, 0, 0, 0, 1] !
5 [0, 0, 1, 0, 0, 0, 0, 0]
6 [0, 0, 1, 0, 0, 0, 0, 0]
7 [0, 0, 1, 0, 0, 0, 0, 0]
6.3.5. Function stripFrames
This function takes a list of 9x9 frames and removes the parity row and column, returning a list
of 8x8 payload-only frames.
This function should build a new list of new frames. It should not modify the existing frames in
any way.
Testing
# build frames
frames = string2frames("Hello, world!", " ")
even = 0
odd = 1
parity = even
frames = appendParityToFrames(frames, parity)
# flip a bit in frame 0
frames[0][3][4] = 1 - frames[0][3][4]29
# display the frames with the error
payloadFrames = stripFrames(frames)
printFrames(payloadFrames)
# repair the frames
results = repairFrames(frames, parity)
# display the frames after correcting the error
payloadFrames = stripFrames(frames)
printFrames(payloadFrames)
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 8x8 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.
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.
s = segmentString("Hello", "~")
# segmentString returns a list of strings, we want just the first one
s = s[0]
print("Original string:", s)
frame = string2bin(s)
print("Frame:")
printFrames([frame])
str = bin2string(frame, "~")
print("Converted string:", str)30
Output:
Original string: Hello~~~
Frame:
0 [0, 1, 0, 0, 1, 0, 0, 0] H
1 [0, 1, 1, 0, 0, 1, 0, 1] e
2 [0, 1, 1, 0, 1, 1, 0, 0] l
3 [0, 1, 1, 0, 1, 1, 0, 0] l
4 [0, 1, 1, 0, 1, 1, 1, 1] o
5 [0, 1, 1, 1, 1, 1, 1, 0] ~
6 [0, 1, 1, 1, 1, 1, 1, 0] ~
7 [0, 1, 1, 1, 1, 1, 1, 0] ~
Converted string: Hello
6.3.7. Function frames2string
This function takes a list of 8x8 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
8x8 frames and then back into a string.
string = "Hello, world!"
fillChar = "~"
frames = string2frames(string, fillChar)
print("Original frames")
printFrames(frames)
string = frames2string(frames, fillChar)
print("Converted string:", string)
Output:
Original frames
0 [0, 1, 0, 0, 1, 0, 0, 0] H
1 [0, 1, 1, 0, 0, 1, 0, 1] e
2 [0, 1, 1, 0, 1, 1, 0, 0] l31
3 [0, 1, 1, 0, 1, 1, 0, 0] l
4 [0, 1, 1, 0, 1, 1, 1, 1] o
5 [0, 0, 1, 0, 1, 1, 0, 0] ,
6 [0, 0, 1, 0, 0, 0, 0, 0]
7 [0, 1, 1, 1, 0, 1, 1, 1] w
0 [0, 1, 1, 0, 1, 1, 1, 1] o
1 [0, 1, 1, 1, 0, 0, 1, 0] r
2 [0, 1, 1, 0, 1, 1, 0, 0] l
3 [0, 1, 1, 0, 0, 1, 0, 0] d
4 [0, 0, 1, 0, 0, 0, 0, 1] !
5 [0, 1, 1, 1, 1, 1, 1, 0] ~
6 [0, 1, 1, 1, 1, 1, 1, 0] ~
7 [0, 1, 1, 1, 1, 1, 1, 0] ~
Converted string: Hello, world!
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. 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.32
Testing
Enter a string: Hello world!
Number of bits flipped: 0
Frame 0 has no errors
Frame 1 has no errors
Hello, world!
['NO ERRORS', 'NO ERRORS']
Enter a string: Hello world!
Number of bits flipped: 1
Frame 0 has no errors
Frame 1 has been repaired
Hello, world!
['NO ERRORS', 'CORRECTED']
Enter a string: Hello world!
Number of bits flipped: 3
Frame 0 has been repaired
Frame 1 could not be repaired
Hello, wmrld
['CORRECTED', 'NOT CORRECTED']
Enter a string: Hello world!
Number of bits flipped: 4
Frame 0 could not be repaired
Frame 1 could not be repaired
HuLlo, wobld!
['NOT CORRECTED', 'NOT CORRECTED']
Enter a string: Hello world!
Number of bits flipped: 2
Frame 0 has been repaired
Hello, world!
['CORRECTED', 'PARITY ERROR']
6.5. Program comments
Place the normal comment block at the beginning of your project file, and docstring comments
in each function.33
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 LastNameHW7
with a .doc or .docx format.
At the beginning of the document include this information:
Error Correction
CSE1010 Homework 7, Spring 2019
your name goes here
the current date goes here
TA: your TA's name goes here
Lab section: your lab section number goes here
Instructor: your lecturer's name goes here
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 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. If HuskyCT complains that uploading a Python file is a 34
security threat, then compress your file into a zip file and then submit the zip 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.