Software Design and Implementation
T9:
Error Detection
When data is transmitted, it is subject to noise, which may introduce errors into the data. Error detection techniques in the transmission of digital data, such as the inclusion of a parity bit, allow detecting such errors.
Objectives
- More practice breaking a larger problem down into smaller pieces using functions
- Gain practice using strings
- Introduce concepts about binary and parity
Binary and Error Detection
Most modern human cultures use the decimal, or base 10, number
system. Computers use a different system called binary for
more than just processing numbers. Binary is a base 2 number system
in which values are represented by different combinations of 0 and
1, also known as OFF or ON. It is the primary "alphabet" of all
digital information (text, music, photos, videos, etc).
Binary may seem weird to us, but it is not new to humans. Morse code also uses two digits (long and short) to represent the entire alphabet. In addition, Australia's aboriginal peoples counted by two, and numerous tribes of the African bush sent complex messages using drum signals at high and low pitches.
When data is transmitted, it is subject to noise which may introduce errors into the data. Error detection techniques such as the parity bit allow detecting such errors with the addition of a single bit. There are two types of parity (even and odd), but we only need one of the them, so we will choose to use even parity.
An even parity bit can be added to the end of a string of binary code as a simple form of error detection. The number of 1 bits in the bit string are counted. If that total is odd, the parity bit value is set to 1, making the total count of 1's in the set an even number. If the count of 1's in the bit string is already even, the parity bit's value is 0.
Here is a video which explains this notion in a fun way. Think of the green sides of the cards as 1 and the white sides as 0.
What the magician did was to add a parity row and column which allowed him not only to detect, but to correct the "error." Correction was possible because he added along both axes. Cool, huh?
In serial data transmission, a common format utilizes chunks which consist of 7 data bits and an even parity bit. This was chosen because the American Standard Code for Information Interchange (ASCII), a character-encoding scheme based on the English alphabet encodes 128 of the most important alphabetic, numeric, and other characters into 7-bit binary integers.
For example: Using the chart, one can see that the character 'J' is 1001010 (100+1010) in ASCII, and the character 'S' is 1010011 (101+0011).
In modem-type communications, a parity bit is added to the beginning of the 7-bit ASCII character, making it 8 bits, or 1 byte, long.
So, when even parity is used and a parity bit is added to the front, the letter 'J' would be encoded as 11001010 (1+100+1010) because summing the bits 1+0+0+1+0+1+0 = 3 is not even, so the even parity bit must be a 1 to make it even.
When even parity is used, 'S' becomes 01010011 (0+101+0011) because summing the bits gives 1+0+1+0+0+1+1 which is already even, so 0 is used for the parity bit.
Binary may seem weird to us, but it is not new to humans. Morse code also uses two digits (long and short) to represent the entire alphabet. In addition, Australia's aboriginal peoples counted by two, and numerous tribes of the African bush sent complex messages using drum signals at high and low pitches.
When data is transmitted, it is subject to noise which may introduce errors into the data. Error detection techniques such as the parity bit allow detecting such errors with the addition of a single bit. There are two types of parity (even and odd), but we only need one of the them, so we will choose to use even parity.
An even parity bit can be added to the end of a string of binary code as a simple form of error detection. The number of 1 bits in the bit string are counted. If that total is odd, the parity bit value is set to 1, making the total count of 1's in the set an even number. If the count of 1's in the bit string is already even, the parity bit's value is 0.
Here is a video which explains this notion in a fun way. Think of the green sides of the cards as 1 and the white sides as 0.
What the magician did was to add a parity row and column which allowed him not only to detect, but to correct the "error." Correction was possible because he added along both axes. Cool, huh?
In serial data transmission, a common format utilizes chunks which consist of 7 data bits and an even parity bit. This was chosen because the American Standard Code for Information Interchange (ASCII), a character-encoding scheme based on the English alphabet encodes 128 of the most important alphabetic, numeric, and other characters into 7-bit binary integers.
7-Bit ASCII Character Codes
| ---0000 | ---0001 | ---0010 | ---0011 | ---0100 | ---0101 | ---0110 | ---0111 | ---1000 | ---1001 | ---1010 | ---1011 | ---1100 | ---1101 | ---1110 | ---1111 | |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 000---- | NUL | SOH | STX | ETX | EOT | ENQ | ACK | BEL | BS | HT | LF | VT | FF | CR | SO | SI |
| 001---- | DLE | DCL | DC2 | DC3 | DC4 | NAK | SYN | ETB | CAN | EM | SUB | ESC | FS | GS | RS | US |
| 010---- | space | ! | " | # | $ | % | & | ' | ( | ) | * | + | , | - | . | / |
| 011---- | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | : | ; | < | = | > | ? |
| 100---- | @ | A | B | C | D | E | F | G | H | I | J | K | L | M | N | O |
| 101---- | P | Q | R | S | T | U | V | W | X | Y | Z | [ | \ | ] | ^ | _ |
| 110---- | ` | a | b | c | d | e | f | g | h | i | j | k | l | m | n | o |
| 111---- | p | q | r | s | t | u | v | w | x | y | z | { | | | } | ~ | DEL |
For example: Using the chart, one can see that the character 'J' is 1001010 (100+1010) in ASCII, and the character 'S' is 1010011 (101+0011).
In modem-type communications, a parity bit is added to the beginning of the 7-bit ASCII character, making it 8 bits, or 1 byte, long.
So, when even parity is used and a parity bit is added to the front, the letter 'J' would be encoded as 11001010 (1+100+1010) because summing the bits 1+0+0+1+0+1+0 = 3 is not even, so the even parity bit must be a 1 to make it even.
When even parity is used, 'S' becomes 01010011 (0+101+0011) because summing the bits gives 1+0+1+0+0+1+1 which is already even, so 0 is used for the parity bit.
Test Driven Development (TDD)
Test-driven development (TDD) (also called test-driven design) is a method of software development in which unit tests are written prior to the actual code. Functions are written as "stubs." The main idea is to get something working and keep making it better until all the unit tests are satisfied. The process is iterated as many times as necessary until each function (or unit) is functioning according to the desired specifications.We will use test-driven development in this assignment.
The Team Assignment
In this assignment, we will take a string of 0's and 1's and do the following:- Test the string to see if it consists entirely of 0's and 1's (It should be because it should be binary.)
- Test the string to see if it's length is evenly divisible by 7. (It should be because it should consist of 7-bit ASCII characters.)
- If the string passes both of the above tests, chunk it into chunks of 7 bits. (These should each be an ASCII character.)
- For each chunk, prepend (i.e. concatenate at the front end) an even parity bit (Prepend a 1 if the sum of the 7 bits is odd, and prepend a 0 otherwise). This will make each chunk an 8-bit chunk typically called a byte.
Hint: The following example illustrates appending to a list which you will find very useful in this assignment: peel_digits.py
Geek note: Because we are using strings to represent bits, and each character in a string uses 7 bits, we are actually using 7 times more space than we need to. In other words, these same ideas can be done with bits rather than bytes. The ideas are all the same.
Be sure to follow good "pair-programming" practices in this paired assignment.
Requirements:
- Get started by downloading yourusername-T9-parity.py
- Complete each of the functions:
is_binary()which takes a bit string as input, returningTrueif it is at least 7-bits and consists solely of 0s and 1s, and returningFalseotherwise.is_div_by_sevens()takes a bit string as input, returningTrueif the length of the string is evenly divisible by 7, and returningFalseotherwise.split_into_sevens()takes a bit string whose length is evenly divisible by 7 as input, and returns the resultant list of 7-bit long strings as output.- Write additional unit tests as needed to fully test each of the above functions.
- Be sure to include good documentation: including good comments in addition to the given docstring for each function.
- Be sure to modify the standard header at the top of your program with your name, username, assignment number, purpose and acknowledgements.
- Remember that you only need to submit a single program per team and that you must include both team members' names and the roles you had in each of the python program files. It is also a good idea for the partner who is not submitting to upload the name of his or her partner.
Submitted files with incorrect filenames may not receive full credit because it makes grading more difficult for us and the TAs, so please check filenames carefully!