The Hamming(7,4) Code from
the Wolfram Demonstrations Project
Contributed by: Jacob A. Siehler
This project will familiarize you with the important data link tool of error correcting and error detecting codes by experimenting with the Hamming Code.
NAME
myhamming --- hamming encode/decode a binary data stream, using (7,4) Hamming with Parity
SYNOPSIS
myhamming [-e|-d] [-v] [-D n]
DESCRIPTION
Takes bytes from standard in and write bytes to standard out. The bytes and bits are
numbered as so:
+---+---+---+---+---+---+---+---+
| 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | Input Byte
+---+---+---+---+---+---+---+---+
First Output Byte Second Output Byte
+---+---+---+---+---+---+---+---+ +---+---+---+---+---+---+---+---+
| A | B | 8 | C | 7 | 6 | 5 | X | | D | E | 4 | F | 3 | 2 | 1 | Y |
+---+---+---+---+---+---+---+---+ +---+---+---+---+---+---+---+---+
Where A, B and C are Hamming bits corresponding to parity signatures 001, 010 and 100,
and 8, 7, 6 and 5 are the data bits from the input byte corresponding to parity
signatures 011, 101, 110, and 111. X is the overall parity bit for the first output
byte, parity even. Likewise for D, E and F parity bits protecting data bites 4, 3, 2
and 1, and Y the overall parity bit protecting the second byte.
The left most byte is written to standard out first on encode, and read from standard
in first on decode.
If the 7 bits of the Hamming portion show no error, and the overall parity bit is
ignored and the output data bits are 8, 7, 6, 5 (4, 3, 2, 1).
If the 7 bits of the Hamming portion show an error, and the overall parity bit X (Y)
shows no error, it is assumed that two bit errors have occurred, and the program aborts.
In other cases, the Hamming Code parity bits A, B, and C (D, E and F) are used to
correct the one bit of error in 8, 7, 6, 5 (4, 3, 2, 1).
OPTIONS
-e encode the data stream. The default if no flag specified.
-d decode the data stream.
-v verbose
-D debug level, takes an positive integer 0 (default) through [your choice].
RETURNS
Returns 0 if not errors, or only 1 bits errors. Halts immediately on a 2 bit
error or uneven number of input bytes on decode, and returns -1.
AUTHOR
You!
Copy the files from [class-repo]/class/proj1 into [class-repo]/[username]/proj1 directory, add, commit, make clean, make, make test.
Study the provided Makefile. No project is correct without a correct Makefile. The grader and I expect that we can:
and be exactly where you are on the project. Same code, same headers, same compiler options, same test case, same bug.If you know nothing of makefiles, find a tutorial and read it. The make concept is there are targets, which depend on dependencies. If any of the dependencies change, the target must be rebuilt to include those changes. This is done by checking the date stamps of the target and dependences (and this can sometimes lead to trouble).
The actions are the sequence of commands to run to rebuild the target. Make works recursively to determine if any of the dependencies are out of date, and rebuilds those first.
The syntax is:
<TARGET>: <DEPENDENCY-1> < DEPENDENCY-2> [TAB] <ACTION-1> [TAB] <ACTION-2>
# sample makefile.
# everything after a # is a comment
# this is a makefile variable.
ME= my-executable
MS= my-subroutines
my-executable: my-executable.c my-executable.h my-subroutines.o
cc -o my-executable my-executable.c my-subroutines.o
my-subroutines.o: my-subroutines.c my-executable.h
cc -c my-subroutines.c
test:
@echo The answer is 42.
clean:
-rm ${MS}.o ${ME}
submit:
make clean
svn commit -m "Submitted for grading"
See the Projects tab on the home page for information about platform preparation: the lab account, working directly on a Mac OSX machine, working on Ubuntu on a virtual machine, or working on a cloud AWS image.
The use of a parity bit allows us to identify two bit errors. With two bits of error, at least one error must be in the data, and if two bits are in the data, they cannot cancel. Hence the hallmark of two bits of error is correct Bit Parity, and incorrect Hamming Parity. If we knew that one bit error was the Bit Parity, we could correct the data bits, but we cannot know this.
Further than two bit errors, the results can misinterpreted as fewer error bits than had actually occurred.
This project is less than 100 lines of code. If it takes up to 300 lines of code, that's probably normal. If you start hitting 500 lines of code, you might want to reconsider your approach. Here is the edited the output of wc run in the class directory ("before") and in a solutions directory ("after").
Author: Burton Rosenberg
Created: January 17, 2015
Last Update: January 17, 2015