CSE1010留学生讲解、Python编程设计调试、Python辅导、讲解printFrames 辅导Database|讲解留学生Proce
- 首页 >> 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 cal
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 cal