Permalink
Cannot retrieve contributors at this time
Name already in use
A tag already exists with the provided branch name. Many Git commands accept both tag and branch names, so creating this branch may cause unexpected behavior. Are you sure you want to create this branch?
Error-Correction/.gitignore/error correction
Go to fileThis commit does not belong to any branch on this repository, and may belong to a fork outside of the repository.
219 lines (189 sloc)
6.95 KB
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# Error Detection | |
# CSE1010 Homework 7, Fall 2018 | |
# Katy Miller | |
# 10/31/18 | |
# Chloe Cachet | |
# Lab Section: 013L | |
# Instructor: Ahmad Jbara | |
import errordetection | |
e = errordetection | |
def string2bin(string): | |
"""takes a string and returns the string in binary form""" | |
stringList = [] | |
for n in string: | |
s = e.char2bin(n) | |
stringList.append(s) | |
return stringList | |
def segmentString(string, fill): | |
"""splits a string into segments of 8 chracters. fills the string if it is less than 8""" | |
desiredWidth = 8 | |
s1 = [] | |
if len(string) <= 8: | |
while len(string) < desiredWidth: | |
string += fill | |
s1.append(string) | |
return s1 | |
else: | |
s1.append(string[0:8]) | |
s2 = string[8:] | |
while len(s2) < desiredWidth: | |
s2 += fill | |
s1.append(s2) | |
return s1 | |
def printFrames(frames): | |
"""prints a frame made up of rows (lists) of bits""" | |
frameN = 0 | |
for frame in frames: | |
charN = 0 | |
for bin in frame: | |
char = e.bin2char(bin) | |
b = bin | |
b = [int(n) for n in b] | |
print(f"{charN:2}", b, char) | |
charN += 1 | |
frameN += 1 | |
print() | |
def string2frames(string, fill): | |
"""takes a string of any length and a fill character, cuts it into segments of 8, and returns a list of bits from the string""" | |
frames = [] | |
newString = segmentString(string, fill) | |
for n in newString: | |
b = string2bin(n) | |
frames.append(b) | |
return frames | |
def appendParityColumn(frame, parity): | |
"""calculates the parity of a frame and appends the parity bit to the column""" | |
newFrame = [] | |
for n in frame: | |
n = [int(k) for k in n] | |
F1 = e.appendParity(n, parity) | |
newFrame.append(F1) | |
return newFrame | |
def transpose(lst): | |
"""rotates a list around the diagonal and returns the output""" | |
lst = list(map(list, zip(*lst))) | |
return lst | |
def appendParityRow(frame, parity): | |
"""calculates the parity of a frame and appends the parity bit to the row""" | |
tFrame = transpose(frame) | |
newFrame = appendParityColumn(tFrame, parity) | |
tFrame2 = transpose(newFrame) | |
return tFrame2 | |
def appendParityToFrame(frame, parity): | |
"""appends a parity row and column to a frame""" | |
frame1 = appendParityColumn(frame, parity) | |
frame2 = appendParityRow(frame1, parity) | |
return frame2 | |
def appendParityToFrames(frames, parity): | |
"""appends a parity row and column to each frame in the list and returns the new list of frames""" | |
newFrames = [] | |
for frame in frames: | |
newFrame = appendParityToFrame(frame, parity) | |
newFrames.append(newFrame) | |
return newFrames | |
def transmitFrames(frames, error): | |
"""this function adds noise to a list of frames, and returns a new list of frames with flipped bits""" | |
noisyFrames = [] | |
newFrames = [] | |
bitsFlipped2 = 0 | |
for frame in frames: | |
newFrames = [] | |
for row in frame: | |
row = [int(n) for n in row] | |
(newFrame, bitsFlipped) = e.addNoise(row, error) | |
newFrames.append(newFrame) | |
bitsFlipped2 = bitsFlipped + 1 | |
noisyFrames.append(newFrames) | |
print('The number of bits flipped', bitsFlipped2) | |
return noisyFrames | |
def splitFrame(frame): | |
"""splits the frame into an 8x8 payload, a parity column, and a parity row""" | |
payload = [] | |
parityColumn = [] | |
for row in frame[0:8]: | |
payload.append(row[0:8]) | |
parityColumn.append(row[8]) | |
parityRow = frame[8] | |
return payload, parityColumn, parityRow | |
def checkParityOfFrame(frame, parity): | |
"""calculates the parity of an 8x8 payload and compares it to the parity recieved""" | |
wrongColumns = [] | |
wrongRows = [] | |
(payload, parityColumn, parityRow) = splitFrame(frame) | |
frame2 = appendParityToFrame(payload, parity) | |
(newPayload, calParityColumn, calParityRow) = splitFrame(frame2) | |
for n in range(len(parityColumn)): | |
if int(parityColumn[n]) != int(calParityColumn[n]): | |
wrongRows.append(n) | |
for n in range(len(parityRow)): | |
if int(parityRow[n]) != int(calParityRow[n]): | |
wrongColumns.append(n) | |
return (wrongColumns, wrongRows) | |
def repairFrame(frame, wrongColumns, wrongRows): | |
""" detects where an error occurs and determines if it is able to be fixed. if it can be, the wronf bit is flipped and the frame is repaired""" | |
if wrongColumns == [] and wrongRows == []: | |
return 'NO ERRORS' | |
elif len(wrongRows) == 1 and len(wrongColumns) == 2 and wrongColumns[1] == 8: | |
fixRow = wrongRows[0] | |
fixColumn = wrongColumns[0] | |
frame[fixRow][fixColumn] = int(frame[fixRow][fixColumn])^1 | |
return 'CORRECTED' | |
elif wrongColumns == [] or wrongRows ==[]: | |
return 'PARITY ERROR' | |
else: | |
return 'NOT CORRECTED' | |
def repairFrames(frames, parity): | |
"""returns a repair status for each frame in a list of frames""" | |
correctionStatuses = [] | |
for frame in frames: | |
(wrongColumns, wrongRows) = checkParityOfFrame(frame, parity) | |
correctionStatus = repairFrame(frame, wrongColumns, wrongRows) | |
if correctionStatus == 'NO ERRORS': | |
print('Frame', frames.index(frame), 'has no errors') | |
correctionStatuses.append(correctionStatus) | |
elif correctionStatus == 'CORRECTED': | |
print('Frame', frames.index(frame), 'has been repaired') | |
correctionStatuses.append(correctionStatus) | |
else: | |
print('Frame', frames.index(frame), 'could not be repaired') | |
correctionStatuses.append(correctionStatus) | |
return correctionStatuses | |
def stripFrames(frames): | |
"""returns an 8x8 payload for each frame""" | |
newFrames = [] | |
for frame in frames: | |
(payload, parityColumn, parityRow) = splitFrame(frame) | |
newFrames.append(payload) | |
return newFrames | |
def bin2string(frame, fill): | |
""" takes an 8x8 frame and fill and returns the string ecoded by the frame""" | |
string = [] | |
for n in frame: | |
char = e.bin2char(n) | |
if char != fill: | |
string.append(char) | |
string = ''.join(string) | |
return string | |
def frames2string(frames, fill): | |
"""iterates over each frame in a list of frames and returns the strings encoded by the frames""" | |
newString = [] | |
for frame in frames: | |
s1 = bin2string(frame, fill) | |
newString.append(s1) | |
newString = ''.join(newString) | |
return newString | |
def main(): | |
errorProb = 0.01 | |
desiredParity = 0 # even | |
fillChar = "~" # tilde | |
string = input('Enter a string: ') | |
frames = string2frames(string, fillChar) | |
transmittedFrames = appendParityToFrames(frames, desiredParity) | |
recievedFrames = transmitFrames(transmittedFrames, errorProb) | |
repairStatuses = repairFrames(recievedFrames, desiredParity) | |
strippedFrames = stripFrames(recievedFrames) | |
newString = frames2string(strippedFrames, fillChar) | |
print(newString) | |
print(repairStatuses) | |
if __name__ == '__main__': | |
main() | |