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 32
   2
7. Report 33
8. Submission 33
9. Grading Rubric 34
10. 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.
11. 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.
12. 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.
13. 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.
14. 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
15. 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).
16. 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:
17. 1 0 1 0 1 0 1
18. 1 1 0 1 1 1 0
19. 1 0 0 0 1 0 1
20. 0 1 0 1 0 1 0
21. 1 0 0 1 0 1 0
22. 0 0 0 0 1 1 0
23. 0 1 1 0 0 0 0
24. 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
25. 0 1 0 1 0 1 0 1 0
26. 1 1 1 0 1 1 1 0 0
27. 1 1 0 0 0 1 0 1 0
28. 1 0 1 0 1 0 1 0 0
29. 0 1 0 0 1 0 1 0 1
30. 1 0 0 0 0 1 1 0 1
31. 1 0 1 1 0 0 0 0 1
32. 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
33. 0 1 0 1 0 1 0 1 0
34. 1 1 1 0 1 1 1 0 0
35. 1 1 0 0 0 1 0 1 0
    6
36. 1 0 1 0 1 0 1 0 0
37. 0 1 0 0 1 0 1 0 1
38. 1 0 0 0 0 1 1 0 1
39. 1 0 1 1 0 0 0 0 1
40. 0 0 1 1 1 1 0 1 1
41. 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:
42. 1 0 1 0 1 0 1 0
43. 1 1 0 1 1 1 0 0
44. 1 0 0 0 1 0 1 0
45. 0 1 0 1 0 1 0 0
46. 1 0 0 0 0 1 0 1
47. 0 0 0 0 1 1 0 1
48. 0 1 1 0 0 0 0 1
49. 0 1 1 1 1 0 1 1
50. 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 8×8 square of bits with the white background is called the payload. The
    parity bits calculated by the sender are shown with a gold background. Together the payload
    and the calculated parity bits make up the whole 9×9 frame. The parity bits calculated by the
    receiver are shown in green. The receiver compares the received parity bits to the calculated
    parity bits, and determines that one of the rows and one of the columns contains an error. The
    intersection of this row and column indicates where the error is:
51. 1 0 1 0 1 0 1 0 0
52. 1 1 0 1 1 1 0 0 0
53. 1 0 0 0 1 0 1 0 0
    7
54. 0 1 0 1 0 1 0 0 0
55. 1 0 0 0 0 1 0 1 0 ← parity mismatch in this row
56. 0 0 0 0 1 1 0 1 1
57. 0 1 1 0 0 0 0 1 1
58. 0 1 1 1 1 0 1 1 1
59. 0 0 1 0 1 0 1 0
60. 0 0 1 1 1 0 1 0
    ↑
    parity mismatch in this column
    The receiver knows that the 0 in the middle of the 8×8 payload block of bits is incorrect, so the
    correct value must be 1, and it simply flips the bit to correct it, and then discards all the parity
    information, leaving the original 8×8 matrix of bits.
61. 1 0 1 0 1 0 1
62. 1 1 0 1 1 1 0
63. 1 0 0 0 1 0 1
64. 0 1 0 1 0 1 0
65. 1 0 0 1 0 1 0
66. 0 0 0 0 1 1 0
67. 0 1 1 0 0 0 0
68. 0 1 1 1 1 0 1
69. 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:
70. Encoding: a string is encoded as bits with parity.
71. Transmission: noise is added to the signal to simulate transmission over a noisy channel.

72. 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.

73. Using a while loop

    fillChar = ‘.’
    desiredWidth = 8
    s1 = ‘abc’
    while len(s1) < desiredWidth:
    s1 += fillChar
    s1
    ‘abc…..’

74. Replicating a character with *

    fillChar = ‘~’
    desiredWidth = 8
    s1 = ‘abc’
    diff = desiredWidth – len(s1)
    s1 += fillChar * diff
    s1
    ‘abc~‘

75. 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)

76. [0, 1, 0, 0, 1, 0, 0, 0] H
77. [0, 1, 1, 0, 0, 1, 0, 1] e
78. [0, 1, 1, 0, 1, 1, 0, 0] l
79. [0, 1, 1, 0, 1, 1, 0, 0] l
80. [0, 1, 1, 0, 1, 1, 1, 1] o
81. [0, 0, 1, 0, 1, 1, 0, 0] ,
82. [0, 0, 1, 0, 0, 0, 0, 0]
83. [0, 1, 1, 1, 0, 1, 1, 1] w
84. [0, 1, 1, 0, 1, 1, 1, 1] o
85. [0, 1, 1, 1, 0, 0, 1, 0] r
86. [0, 1, 1, 0, 1, 1, 0, 0] l
87. [0, 1, 1, 0, 0, 1, 0, 0] d
    12
88. [0, 0, 1, 0, 0, 0, 0, 1] !
89. [0, 1, 1, 1, 1, 1, 1, 0] ~
90. [0, 1, 1, 1, 1, 1, 1, 0] ~
91. [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:
92. Create an empty list in which to store the frames.
93. Segment the string.
94. Iterate over the segments, converting each segment into a frame by calling string2bin
    on it.
95. Append the frame to the list of frames.

96. Return the list of frames.
    Testing

    s = “Hello!”
    frames = string2frames(s, ‘ ‘)
    printFrames(frames)

97. [0, 1, 0, 0, 1, 0, 0, 0] H
98. [0, 1, 1, 0, 0, 1, 0, 1] e
99. [0, 1, 1, 0, 1, 1, 0, 0] l
100. [0, 1, 1, 0, 1, 1, 0, 0] l
101. [0, 1, 1, 0, 1, 1, 1, 1] o
102. [0, 0, 1, 0, 0, 0, 0, 0]
103. [0, 0, 1, 0, 0, 0, 0, 0]

104. [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)

105. [0, 1, 0, 0, 1, 0, 0, 0] H
106. [0, 1, 1, 0, 0, 1, 0, 1] e
107. [0, 1, 1, 0, 1, 1, 0, 0] l
108. [0, 1, 1, 0, 1, 1, 0, 0] l
109. [0, 1, 1, 0, 1, 1, 1, 1] o
110. [0, 0, 1, 0, 1, 1, 0, 0] ,
111. [0, 0, 1, 0, 0, 0, 0, 0]
112. [0, 1, 0, 1, 0, 1, 1, 1] W
113. [0, 1, 1, 0, 1, 1, 1, 1] o
114. [0, 1, 1, 1, 0, 0, 1, 0] r
115. [0, 1, 1, 0, 1, 1, 0, 0] l
116. [0, 1, 1, 0, 0, 1, 0, 0] d
117. [0, 0, 1, 0, 0, 0, 0, 1] !
118. [0, 0, 1, 0, 0, 0, 0, 0]
119. [0, 0, 1, 0, 0, 0, 0, 0]

120. [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 first
     14

121. [0, 1, 1, 0, 0, 0, 0, 1] a
122. [0, 1, 1, 0, 0, 0, 1, 0] b

123. [0, 1, 1, 0, 0, 0, 1, 1] c

     l2 = appendParityColumn(l1, 0)
     printFrames([l2]) # convert l2 to list of frames first

124. [0, 1, 1, 0, 0, 0, 0, 1, 1] ?
125. [0, 1, 1, 0, 0, 0, 1, 0, 1] ?

126. [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

127. [0, 1, 0, 0, 1, 0, 0, 0, 0] ?
128. [0, 1, 1, 0, 0, 1, 0, 1, 0] ê
129. [0, 1, 1, 0, 1, 1, 0, 0, 0] ?
130. [0, 1, 1, 0, 1, 1, 0, 0, 0] ?
131. [0, 1, 1, 0, 1, 1, 1, 1, 0] T
132. [0, 0, 1, 0, 0, 0, 0, 0, 1] A
133. [0, 0, 1, 0, 0, 0, 0, 0, 1] A
134. [0, 0, 1, 0, 0, 0, 0, 0, 1] A
135. [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?
     Debugging
     16
     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:
136. [0, 1, 0, 0, 1, 0, 0, 0] H
137. [0, 1, 1, 0, 0, 1, 0, 1] e
138. [0, 1, 1, 0, 1, 1, 0, 0] l
139. [0, 1, 1, 0, 1, 1, 0, 0] l
140. [0, 1, 1, 0, 1, 1, 1, 1] o
141. [0, 0, 1, 0, 0, 0, 0, 0]
142. [0, 0, 1, 0, 0, 0, 0, 0]
143. [0, 0, 1, 0, 0, 0, 0, 0]
     Here’s the frame after adding a parity column:
144. [0, 1, 0, 0, 1, 0, 0, 0, 0] ?
145. [0, 1, 1, 0, 0, 1, 0, 1, 0] ê
146. [0, 1, 1, 0, 1, 1, 0, 0, 0] ?
147. [0, 1, 1, 0, 1, 1, 0, 0, 0] ?
148. [0, 1, 1, 0, 1, 1, 1, 1, 0] T
149. [0, 0, 1, 0, 0, 0, 0, 0, 1] A
150. [0, 0, 1, 0, 0, 0, 0, 0, 1] A
151. [0, 0, 1, 0, 0, 0, 0, 0, 1] A
     Here’s the frame after transposing:
152. [0, 0, 0, 0, 0, 0, 0, 0]
153. [1, 1, 1, 1, 1, 0, 0, 0] ?
154. [0, 1, 1, 1, 1, 1, 1, 1]
155. [0, 0, 0, 0, 0, 0, 0, 0]
156. [1, 0, 1, 1, 1, 0, 0, 0] ?
157. [0, 1, 1, 1, 1, 0, 0, 0] x
158. [0, 0, 0, 0, 1, 0, 0, 0]
159. [0, 1, 0, 0, 1, 0, 0, 0] H
160. [0, 0, 0, 0, 0, 1, 1, 1]
     Here’s the frame after adding a parity column:
161. [0, 0, 0, 0, 0, 0, 0, 0, 0]
162. [1, 1, 1, 1, 1, 0, 0, 0, 1] ?
163. [0, 1, 1, 1, 1, 1, 1, 1, 1] ?
164. [0, 0, 0, 0, 0, 0, 0, 0, 0]
165. [1, 0, 1, 1, 1, 0, 0, 0, 0] ?
166. [0, 1, 1, 1, 1, 0, 0, 0, 0] e
167. [0, 0, 0, 0, 1, 0, 0, 0, 1]
168. [0, 1, 0, 0, 1, 0, 0, 0, 0] ?
     17
169. [0, 0, 0, 0, 0, 1, 1, 1, 1]
     Here’s the frame after transposing again:
170. [0, 1, 0, 0, 1, 0, 0, 0, 0] ?
171. [0, 1, 1, 0, 0, 1, 0, 1, 0] ê
172. [0, 1, 1, 0, 1, 1, 0, 0, 0] ?
173. [0, 1, 1, 0, 1, 1, 0, 0, 0] ?
174. [0, 1, 1, 0, 1, 1, 1, 1, 0] T
175. [0, 0, 1, 0, 0, 0, 0, 0, 1] A
176. [0, 0, 1, 0, 0, 0, 0, 0, 1] A
177. [0, 0, 1, 0, 0, 0, 0, 0, 1] A

178. [0, 1, 1, 0, 0, 0, 1, 0, 1] ?
     6.1.7. Function appendParityToFrame
     This function takes a normal 8×8 frame (8 rows of 8 bits) and a desired parity, and returns a 9×9
     frame that has both a column and a row of parity bits appended to it.
     Inside this function all you need to do is call the appendParityColumn function first, then call
     the appendParityRow function on that result, then return that result.
     Testing

     frames = string2frames(‘Hello’, ‘ ‘)
     even = 0
     f0 = frames[0]
     f1 = appendParityToFrame(f0, even)
     printFrames([f1]) # convert f1 to list of frames

179. [0, 1, 0, 0, 1, 0, 0, 0, 0] ?
180. [0, 1, 1, 0, 0, 1, 0, 1, 0] ê
181. [0, 1, 1, 0, 1, 1, 0, 0, 0] ?
182. [0, 1, 1, 0, 1, 1, 0, 0, 0] ?
183. [0, 1, 1, 0, 1, 1, 1, 1, 0] T
184. [0, 0, 1, 0, 0, 0, 0, 0, 1] A
185. [0, 0, 1, 0, 0, 0, 0, 0, 1] A
186. [0, 0, 1, 0, 0, 0, 0, 0, 1] A

187. [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)

188. [0, 1, 0, 0, 1, 0, 0, 0, 0] ?
189. [0, 1, 1, 0, 0, 1, 0, 1, 0] ê
190. [0, 1, 1, 0, 1, 1, 0, 0, 0] ?
191. [0, 1, 1, 0, 1, 1, 0, 0, 0] ?
192. [0, 1, 1, 0, 1, 1, 1, 1, 0] T
193. [0, 0, 1, 0, 0, 0, 0, 0, 1] A
194. [0, 0, 1, 0, 0, 0, 0, 0, 1] A
195. [0, 0, 1, 0, 0, 0, 0, 0, 1] A

196. [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)

197. [0, 1, 0, 0, 1, 0, 0, 0, 0] ?
198. [0, 1, 1, 0, 0, 1, 0, 1, 0] ê
199. [0, 1, 1, 0, 1, 1, 0, 0, 0] ?
200. [0, 1, 1, 0, 1, 1, 0, 0, 0] ?
201. [0, 1, 1, 0, 1, 1, 1, 1, 0] T
202. [0, 0, 1, 0, 1, 1, 0, 0, 1] Y
203. [0, 0, 1, 0, 0, 0, 0, 0, 1] A
204. [0, 1, 1, 1, 0, 1, 1, 1, 0] ?
205. [0, 0, 1, 1, 1, 0, 0, 1, 0] r
206. [0, 1, 1, 0, 1, 1, 1, 1, 0] T
207. [0, 1, 1, 1, 0, 0, 1, 0, 0] ?
208. [0, 1, 1, 0, 1, 1, 0, 0, 0] ?
209. [0, 1, 1, 0, 0, 1, 0, 0, 1] é
210. [0, 0, 1, 0, 0, 0, 0, 1, 0] B
211. [0, 0, 1, 0, 0, 0, 0, 0, 1] A
212. [0, 0, 1, 0, 0, 0, 0, 0, 1] A
213. [0, 0, 1, 0, 0, 0, 0, 0, 1] A
     19
214. [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)
215. [0, 1, 0, 0, 1, 0, 0, 0, 0] ?
216. [0, 1, 1, 0, 0, 1, 0, 1, 0] ê
217. [0, 1, 1, 0, 1, 1, 0, 0, 0] ?
218. [0, 1, 1, 0, 1, 1, 0, 0, 0] ?
219. [0, 1, 1, 0, 1, 1, 1, 1, 0] T
220. [0, 0, 1, 0, 0, 0, 0, 0, 1] A
221. [0, 0, 1, 0, 0, 0, 0, 0, 1] A
222. [0, 0, 1, 0, 0, 0, 0, 0, 1] A
223. [0, 1, 1, 0, 0, 0, 1, 0, 1] ?
     Frame 0 (transmitted frame)
224. [0, 1, 0, 0, 1, 0, 0, 0, 0] ?
225. [0, 1, 1, 0, 0, 1, 0, 1, 0] ê
226. [0, 1, 1, 0, 1, 1, 0, 0, 0] ?
     21
227. [0, 1, 1, 0, 1, 1, 0, 0, 0] ?
228. [0, 1, 1, 0, 1, 1, 1, 1, 0] T
229. [0, 0, 1, 0, 0, 0, 1, 0, 1] E
230. [0, 0, 1, 0, 0, 0, 0, 0, 1] A
231. [0, 0, 1, 0, 0, 0, 0, 0, 1] A
232. [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 9×9 frame and splits the frame into 3 pieces: the payload (the upper left
     8×8 matrix of data bits), the parity column (but only rows 1 – 8), and the parity row (all 9
     columns).
     Here I show the 8×8 payload in white, the parity column in orange, and the parity row in green:
233. 1 0 1 0 1 0 1 0
234. 1 1 0 1 1 1 0 0
235. 1 0 0 0 1 0 1 0
236. 0 1 0 1 0 1 0 0
237. 1 0 0 1 0 1 0 1
238. 0 0 0 0 1 1 0 1
239. 0 1 1 0 0 0 0 1
240. 0 1 1 1 1 0 1 1

241. 0 0 1 0 1 0 1 0
     This function must return three things: the 8×8 payload as a list of lists, the parity column as a
     list, and the parity row as a list.
     I wrote this function using just a single for loop and three new lists: the payload, the parity
     column, and the parity row.
     Don’t iterate over all 9 rows. Iterate over the first 8 rows. The 9th row is a special case.
     Test it
     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

242. [0, 1, 0, 0, 1, 0, 0, 0] H
243. [0, 1, 1, 0, 0, 1, 0, 1] e
244. [0, 1, 1, 0, 1, 1, 0, 0] l
245. [0, 1, 1, 0, 1, 1, 0, 0] l
246. [0, 1, 1, 0, 1, 1, 1, 1] o
247. [0, 0, 1, 0, 0, 0, 0, 0]
248. [0, 0, 1, 0, 0, 0, 0, 0]
249. [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 8×8 payload and compare it to the column and
     23
     row parity that was sent as part of the 9×9 frame. If the parity does not match in any location,
     then an error has been detected.
     The function has two parameters: the frame and the desired parity. This function returns a
     tuple of two lists:
250. a list of column numbers where a parity error is detected

251. a list of row numbers where there a parity error is detected.
     To do this, compare the received parity column to the calculated parity column. The rows
     where the columns do not match (are not equal) indicate the row or rows in the payload where
     there is an error. Also compare the received parity row to the calculated parity row. The
     columns where the rows do not match indicate the column or columns in the payload where
     there is an error.
     Hints
     Use the splitFrame function to split the frame into the payload, the received parity column, and
     the received parity row.
     Use the appendParityToFrame function to re-calculate the parity of the 8×8 payload. This
     returns a new frame. Be sure to store it in a variable.
     Call the splitFrame function again on this new frame to obtain the payload (which you don’t
     need), the calculated parity column, and the calculated parity row.
     Compare the received parity column list to the calculated parity column list. Make a new list of
     all the locations where the two lists don’t have equal values.
     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

     frame13 = 1 – frame13

     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 9×9 frame, a list of error columns, a list of error rows, and tries to repair
     the frame. The error columns and error rows are the lists returned by the 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 (4×4 is sufficient), add a parity column and
     parity row, and flip two bits that are not in the same row or same column. Determine why you
     can’t locate exactly where the errors are.
     If there is a single bit error either in just the columns or just the rows, then it means that a
     parity bit itself has been flipped and you can’t correct the error. But when the string is
     reconstructed from the bits it has no errors in it, because the payload itself had no errors in it.
     The function must work like this:

252. If there are no error rows and there are no error columns, then there are no errors in
     the 8×8 payload portion of the frame, so simply return the repair status ‘NO ERRORS’.
253. 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’.
254. 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’.

255. 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

     frame13 = 1 – frame13
     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 9×9 frames with the parity bits, so the characters are not “Hello”:
     With an error:

256. [0, 1, 0, 0, 1, 0, 0, 0, 0] ?
257. [0, 1, 1, 0, 0, 1, 0, 1, 0] ê
258. [0, 1, 1, 0, 1, 1, 0, 0, 0] ?
259. [0, 1, 1, 0, 0, 1, 0, 0, 0] è (the error is in this row, column 4)
260. [0, 1, 1, 0, 1, 1, 1, 1, 0] T
261. [0, 0, 1, 0, 0, 0, 0, 0, 1] A
262. [0, 0, 1, 0, 0, 0, 0, 0, 1] A
263. [0, 0, 1, 0, 0, 0, 0, 0, 1] A
264. [0, 1, 1, 0, 0, 0, 1, 0, 1] ?
     [4, 8] [3]
     CORRECTED
265. [0, 1, 0, 0, 1, 0, 0, 0, 0] ?
266. [0, 1, 1, 0, 0, 1, 0, 1, 0] ê
267. [0, 1, 1, 0, 1, 1, 0, 0, 0] ?
268. [0, 1, 1, 0, 1, 1, 0, 0, 0] ? (the error has been corrected)
269. [0, 1, 1, 0, 1, 1, 1, 1, 0] T
270. [0, 0, 1, 0, 0, 0, 0, 0, 1] A
271. [0, 0, 1, 0, 0, 0, 0, 0, 1] A
272. [0, 0, 1, 0, 0, 0, 0, 0, 1] A

273. [0, 1, 1, 0, 0, 0, 1, 0, 1] ?
     6.3.4. Function repairFrames
     This function takes a list of 9×9 frames and a desired parity. It returns list of repair statuses, one
     for each frame.
     To do this, iterate over all the frames one at a time. For each frame, call the
     checkParityOfFrame function on it and save the return values. Then take those return values
     and use them to call the repairFrame function on the same frame and save the return value in a
     list.
     Examine the repair status and depending on its value display one of these messages:
     ? ‘Frame frameNumber has no errors’
     ? ‘Frame frameNumber has been repaired’
     ? ‘Frame frameNumber could not be repaired’
     In each case, frameNumber is the index number of the frame in the list of frames.
     27
     Testing

     build frames

     frames = string2frames(“Hello, world!”, ” “)
     even = 0
     odd = 1
     parity = even
     frames = appendParityToFrames(frames, parity)

     flip a bit in frame 0

     frames0[4] = 1 – frames0[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:

274. [0, 1, 0, 0, 1, 0, 0, 0] H
275. [0, 1, 1, 0, 0, 1, 0, 1] e
276. [0, 1, 1, 0, 1, 1, 0, 0] l
277. [0, 1, 1, 0, 0, 1, 0, 0] d (there is an error in this row)
278. [0, 1, 1, 0, 1, 1, 1, 1] o
279. [0, 0, 1, 0, 1, 1, 0, 0] ,
280. [0, 0, 1, 0, 0, 0, 0, 0]
281. [0, 1, 1, 1, 0, 1, 1, 1] w
282. [0, 1, 1, 0, 1, 1, 1, 1] o
283. [0, 1, 1, 1, 0, 0, 1, 0] r
284. [0, 1, 1, 0, 1, 1, 0, 0] l
285. [0, 1, 1, 0, 0, 1, 0, 0] d
286. [0, 0, 1, 0, 0, 0, 0, 1] !
287. [0, 0, 1, 0, 0, 0, 0, 0]
288. [0, 0, 1, 0, 0, 0, 0, 0]
     28
289. [0, 0, 1, 0, 0, 0, 0, 0]
     After correcting errors:
     Frame 0 has been repaired
     Frame 1 has no errors
290. [0, 1, 0, 0, 1, 0, 0, 0] H
291. [0, 1, 1, 0, 0, 1, 0, 1] e
292. [0, 1, 1, 0, 1, 1, 0, 0] l
293. [0, 1, 1, 0, 1, 1, 0, 0] l (the error in this row has been fixed!)
294. [0, 1, 1, 0, 1, 1, 1, 1] o
295. [0, 0, 1, 0, 1, 1, 0, 0] ,
296. [0, 0, 1, 0, 0, 0, 0, 0]
297. [0, 1, 1, 1, 0, 1, 1, 1] w
298. [0, 1, 1, 0, 1, 1, 1, 1] o
299. [0, 1, 1, 1, 0, 0, 1, 0] r
300. [0, 1, 1, 0, 1, 1, 0, 0] l
301. [0, 1, 1, 0, 0, 1, 0, 0] d
302. [0, 0, 1, 0, 0, 0, 0, 1] !
303. [0, 0, 1, 0, 0, 0, 0, 0]
304. [0, 0, 1, 0, 0, 0, 0, 0]

305. [0, 0, 1, 0, 0, 0, 0, 0]
     6.3.5. Function stripFrames
     This function takes a list of 9×9 frames and removes the parity row and column, returning a list
     of 8×8 payload-only frames.
     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

     frames0[4] = 1 – frames0[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 8×8 frame and a fill
     character, and returns the 8-character string encoded by that frame. It does not include any of
     the fill characters.
     The function iterates over each list in the frame, converts each list into a character (use your
     bin2char function). If the character is the fill character, then exit the loop, otherwise append
     the character to the end of a list of characters.
     Finally join the list into a string and then return the string.
     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:

306. [0, 1, 0, 0, 1, 0, 0, 0] H
307. [0, 1, 1, 0, 0, 1, 0, 1] e
308. [0, 1, 1, 0, 1, 1, 0, 0] l
309. [0, 1, 1, 0, 1, 1, 0, 0] l
310. [0, 1, 1, 0, 1, 1, 1, 1] o
311. [0, 1, 1, 1, 1, 1, 1, 0] ~
312. [0, 1, 1, 1, 1, 1, 1, 0] ~
313. [0, 1, 1, 1, 1, 1, 1, 0] ~
     Converted string: Hello
     6.3.7. Function frames2string
     This function takes a list of 8×8 frames and a fill character. This function iterates over each
     frame and converts each frame into a string.
     For each frame in the list of frames, call the bin2string function on that block (also with the fill
     character) and append the returned string to a list of strings.
     Join the strings into a single string and return that string.
     Testing
     This test doesn’t use any of the parity functions. It just tests that a string can be converted into
     8×8 frames and then back into a string.
     string = “Hello, world!”
     fillChar = “~”
     frames = string2frames(string, fillChar)
     print(“Original frames”)
     printFrames(frames)
     string = frames2string(frames, fillChar)
     print(“Converted string:”, string)
     Output:
     Original frames
314. [0, 1, 0, 0, 1, 0, 0, 0] H
315. [0, 1, 1, 0, 0, 1, 0, 1] e
316. [0, 1, 1, 0, 1, 1, 0, 0] l
     31
317. [0, 1, 1, 0, 1, 1, 0, 0] l
318. [0, 1, 1, 0, 1, 1, 1, 1] o
319. [0, 0, 1, 0, 1, 1, 0, 0] ,
320. [0, 0, 1, 0, 0, 0, 0, 0]
321. [0, 1, 1, 1, 0, 1, 1, 1] w
322. [0, 1, 1, 0, 1, 1, 1, 1] o
323. [0, 1, 1, 1, 0, 0, 1, 0] r
324. [0, 1, 1, 0, 1, 1, 0, 0] l
325. [0, 1, 1, 0, 0, 1, 0, 0] d
326. [0, 0, 1, 0, 0, 0, 0, 1] !
327. [0, 1, 1, 1, 1, 1, 1, 0] ~
328. [0, 1, 1, 1, 1, 1, 1, 0] ~
329. [0, 1, 1, 1, 1, 1, 1, 0] ~
     Converted string: Hello, world!
     6.4. Main function
     This function ties it all together. Do this:
330. Define three variables:
     errorProb = 0.01
     desiredParity = 0 # even
     fillChar = “~” # tilde
331. Get a string from the user.
332. 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).
333. 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).
334. 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.
335. Repair the received frames using desiredParity. Save the repair statuses in a variable.
336. Strip the received frames. I call the result the stripped frames.
337. Convert the stripped frames to a string. Use the fillChar variable you defined.
338. Display the string.
339. 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
340. 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.
341. 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.)
342. 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).
343. 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.
344. Source code
     Copy & paste the contents of your .py file here. You do not need to write anything.
345. Submission
     Submit the following things things on HuskyCT:
346. 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.
347. 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.
348. 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.