Communication and Networks Assignment
Tubekbay001
0_Lesson11ErrorHandling.pptxCommunications and Networks
version 1.0
Diploma in Information Technology
Copyright © 2020 by Singapore Institute of Management Pte Ltd. All rights reserved.
Lesson 11: Error Handling
1
Lesson 11 Learning Outcomes
Describe the main sources of transmission errors
Understand the effects of transmission errors on data
Describe two strategies to handle channel errors
Describe block error codes and convolutional error codes
2
Lesson 11 Learning Outcomes
Describe single parity checking
Calculate Hamming distance between pair of words
Understand the error checks used on the Internet
3
Lesson 11 Outline
Transmission Errors
Channel Coding
4
Data Communication Issues
Data communications systems are prone to errors
Some are inherent in the physics of the universe
Some from devices that fail
Some from equipment that does not meet the engineering standards
Small errors that occur during transmission are more difficult to detect than complete failures
Need mechanisms to control and recover
5
Transmission Errors (1/2)
Interference: electromagnetic radiation emitted from devices like electric motors
Background cosmic radiation
Cause noise that can disturb radio transmissions and signals traveling across wires
Attenuation: signal loss over distance
signals on wired media become weaker over long distances
radio signal becomes weaker with distance
6
Transmission Errors (2/2)
Distortion: all physical systems distort signals
As pulse travels along fiber, it disperses
Capacitance and inductance: block signals at some frequencies while admitting signals at other frequencies
Placing wire near metal object can change the frequencies that can pass through wire
Metal objects can block some frequencies of radio waves, while passing others
7
Reducing Errors
Shannon's Theorem suggests to increase SNR:
Either increase signal or lower noise if possible
Mechanisms like shielded wiring can help lower noise
Physical transmission system is always prone to errors
May not be possible to change the SNR
8
Error Handling
Noise/interference cannot be eliminated completely
Many errors can be detected
Some can be corrected automatically
But Error detection adds overhead
Error handling is a tradeoff
To decide whether a given error is likely to occur
If so, what is the consequence
9
Types of Errors
Spike: extremely short duration interference,
often the cause of a single bit error
Longer duration interference or distortion can produce burst errors
Sometimes signal is neither clearly 1 nor clearly 0, but falls in an ambiguous region, which is known as an erasure
10
Types of Errors Summary
Source: Douglas, C (2016) Computer Networks and Internets
11
Burst Error
For a burst error:
Burst size/length: number of bits from the start of the corruption to the end of the corruption
Source: Douglas, C (2016) Computer Networks and Internets
12
Lesson 11 Outline
Transmission Errors
Channel Coding
Parity Checking
Hamming Distance and Hamming Code
Row and Column Parity (RAC)
Internet Checksum
13
Error Correction History
Source: https://www.youtube.com/watch?v=q-3BctoUpHE
14
Channel Coding
Number of mathematical techniques have been developed to overcome errors
Known collectively as channel coding
These techniques are
Forward Error Correction (FEC)
Automatic Repeat reQuest (ARQ)
15
Automatic Repeat Request
ARQ requires cooperation of sender and receiver
Receiver needs to send a short acknowledgement (ACK) message back
If A sends message to B, B sends ACK back to A
Once receives ACK, A knows that the message arrived correctly
If no ACK is received after T time, A assumes the message was lost and retransmits a copy
16
ARQ Limitations
Useful with detecting errors but not for error correction
For error correction, most use Cyclic Redundancy Check (CRC)
ARQ scheme can be added to guarantee delivery if a transmission error occurs
Receiver discards message if an error occurs
Sender retransmits another copy
17
Forward Error Correction
FEC adds additional information to data to allow receiver to verify data arrives correctly (detection)
Tries to correct errors if possible
FEC mechanisms allow receivers to determine
Which bits have been changed
How to compute correct values
18
Visualising FEC
Source: Douglas, C (2016) Computer Networks and Internets
19
Block Error Codes
Block Error Codes is a type of FEC
Divides data sent into set of blocks
Attach information known as redundancy to each block
Encoding for a given block of bits depends on the bits themselves, not on bits sent earlier
Memoryless: does not carry state information from one block of data to the next
20
Convolutional Error Codes
Convolutional Error Codes is also a type of FEC
Treats data as a series of bits
Computes a code over a continuous series
Code computed for a set of bits depends on current input and some of the previous bits in the stream
Codes with memory
21
Single Parity Checking
Single Parity Checking (SPC): a type of block error codes
SPC can define a block to be 8-bit (byte) of data
Sender and receiver must be configured for either even parity or odd parity
On sender, an encoder adds an extra bit, parity bit
Total bits: 9-bit (8-bit data, 1-bit parity)
Receiver uses parity bit to check whether bits in the byte are correct
22
SPC Example
Source: Douglas, C (2016) Computer Networks and Internets
What is the limitation?
23
Practice 11.1
Complete the table below
| Original Data | Even Parity | Odd Parity |
| 0011 1100 | ||
| 1111 1100 | ||
| 0101 0101 | ||
| 1100 0011 | ||
| 1010 1100 | ||
| 0011 0111 | ||
| 1111 1111 |
24
SPC Limitation
SPC can detect errors but cannot correct errors
Even parity fails if odd number of bits changed
Odd parity fails if even number of bits changed
Consider even parity example:
If one-bit changed value, receiver will declare incoming byte is invalid
If two, four, six, or eight bits changed value, receiver will incorrectly declare valid
25
Lesson 11 Outline
Transmission Errors
Channel Coding
Parity Checking
Hamming Distance and Hamming Code
Row and Column Parity (RAC)
Internet Checksum
26
Some Definitions
Datawords: set of all possible messages
Codewords: set of all possible encoded versions
Codebook: subset of the possible combinations that are valid codewords
27
Hamming Distance
Engineers use a measure known as the Hamming distance
named after a theorist at Bell Laboratories who was a pioneer in the field of information theory and channel coding
Given two strings of n-bit each, Hamming distance is defined as the number of differences
Number of bits to change for one string to be identical to another
28
Hamming Distance Example
Source: Douglas, C (2016) Computer Networks and Internets
29
Computing Hamming Distance
Straight forward way is manual observation
Another way is:
Perform exclusive or (XOR) between two strings
Counting number of 1 bits in the answer
| Input 1 | Input 2 | Output |
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
XOR Function
| String 1: | 1 | 1 | 0 |
| String 2: | 0 | 1 | 1 |
| 1 | 0 | 1 |
Total number of 1s = 2
Hence, Hamming distance = 2
30
Hamming Distance for Codebook
Errors can transform a valid codeword into another valid codeword
To measure such transformations, compute the Hamming distance
between all pairs of codewords in a codebook
Source: Douglas, C (2016) Computer Networks and Internets
31
Minimum Hamming Distance
Minimum Hamming distance (dmin): lowest Hamming distance among pairs in a codebook
Number of bits that cause a transformation from one valid codeword to another valid codeword
In this example, dmin = 2
Source: Douglas, C (2016) Computer Networks and Internets
32
Hamming Distance Implication
Implication of dmin = 2:
There is at least one valid codeword that can be transformed into another valid codeword,
If 2-bit errors occur during transmission
A large value of dmin is desirable
if < dmin bits are changed, the code can detect that error(s) occurred
33
Bit Error Detection
Maximum number of bit errors that can be detected:
e = dmin – 1
Code with higher dmin sends more redundant information
34
Hamming Code
Hamming code uses multiple parity bits within a code
Each parity bit checks a unique combination of bits
Parity bit appears in bit positions that are powers of 2
i.e. bits 1, 2, 4, 8
Remaining bit positions are occupied by bits that are to be checked
35
Hamming Code Parity Checks
This table shows the bits check by each parity bits
b1: checks all the odd bits
b2: checks b2, b3, b6, b7, b10, b11
b4: checks b4, b5, b6, b7, b12
b8: checks b8, b9, b10, b11, b12
Binary code for bit number at top of each column can be obtained by reading all the bits in that column from bottom up
20 = 1
21 + 23 = 10
36
Hamming Example (1/3)
Code 0110 1110 in even Hamming code
Step 1: Place bits from this byte in first row of a table headed with bit numbers in reverse order, leaving spaces for parity bits
Step 2: In b1 row, place all the bits that are checked by b1
Step 3: Calculate value of b1 which give even parity and write in b1 column (use hamming code parity table)
Step 4: Repeat Step 2 and 3 for b2 in b2 row, b3 in b4 row and b8 in b8 row
37
Hamming Example (2/3)
Step 1: Place bits from this byte in first row of a table headed with bit numbers in reverse order, leaving spaces for parity bits
Step 2: In b1 row, place all the bits that are checked by b1
Step 3: Calculate b1 and write in b1 (using Hamming parity table)
Step 4: Repeat Step 2 and 3 for b2 in b2 row, b3 in b4 row and b8 in b8 row
38
Hamming Example (3/3)
With the parity bits calculated, even Hamming code is as follows 0110 0111 1001
As such, 0110 0111 1001 is transmitted
39
Hamming Example Error (1/2)
Original: 0110 0111 1001
Error: 0110 0011 1001
Assuming the error byte is received
Step 1: Enter the error byte in the first row
Step 2: Check parity calculation for b1, b2, b4 and b8
Step 3: If total parity is odd, underline parity bit and place a 1, which is what is needed to ensure even parity, in the “fix” column and a 0 otherwise
40
Hamming Example Error (2/2)
Error occurs in parity bit 1, 2 and 4 but not 8
b7 is the only one check by bit 1,2 and 4
Shows that b7 is the one corrupted
Interesting fact is reading the bits in fix column upwards gives the decimal number 7, confirming that error is in b7 i.e. 01112 = 710
Correct the 7th bit to get the original byte 0110 1110
41
Practice 11.2
Code 1101 1010 in even Hamming code
42
Hamming Code Implication
Hamming codes is a useful FEC technique
But overhead is 50% for 8-bit characters
Redundant data transmitted
However, there is a potential saving in terms of reduced re-transmissions
43
Lesson 11 Outline
Transmission Errors
Channel Coding
Parity Checking
Hamming Distance and Hamming Code
Row and Column Parity (RAC)
Internet Checksum
44
Row and Column Parity (RAC)
Imagine an array of 3-rows and 4-columns
Row and Column (RAC) code: parity bit added to each row and column
Source: Douglas, C (2016) Computer Networks and Internets
45
RAC Error Detection
On the receiver, bits are arranged into an array and parity bits are recalculated
If single bit error, two of the calculations will disagree with the parity bits received
Source: Douglas, C (2016) Computer Networks and Internets
46
Practice 11.3
Assuming even parity, identify the error bit in the following array.
| 1 | 0 | 1 | 1 | 0 | 1 |
| 1 | 0 | 1 | 1 | 0 | 1 |
| 0 | 0 | 1 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 | 0 | 0 |
47
RAC Uses and Limitations
Two disagreements correspond to the row and column position of the error
Receiver uses calculated parity bits to determine exactly which bit is in error and corrects the bit
RAC can only correct single-bit errors
In cases where two or three bits are changed
RAC encoding will be able to detect an odd number of errors
48
Lesson 11 Outline
Transmission Errors
Channel Coding
Parity Checking
Hamming Distance and Hamming Code
Row and Column Parity (RAC)
Internet Checksum
49
Internet Checksum
Internet checksum is a coding scheme on the Internet
Code consists of 16-bit 1s complement checksum
The Internet checksum does not impose a fixed size on a dataword
Allows a message to be of any length
Computes a checksum over the entire message
50
Padding the Message
Internet checksum treats data in a message as a series of 16-bit integers
Source: Douglas, C (2016) Computer Networks and Internets
51
Computing Internet Checksum
Sender adds the numeric values of the 16-bit integers, transmits the result
Checksum computed in 1s complement arithmetic
Uses 16-bit integers instead of 32 or 64-bit
To validate the message, a receiver performs the same computation
52
Internet Checksum Example
On the receiver:
If sum is all 1’s, no error
If sum has a 0 somewhere, error has occurred
53
Getting the Checksum (1/2)
| 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | |||||
| 1 | 0 | 0 | 1 | 1 | 0 | 1 | 1 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | |
| 1 | 1 | 1 | 0 | 1 | 0 | 1 | 1 | 1 | 1 | 0 | 1 | 0 | 1 | 1 | 1 | |
| 1 | 1 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 |
Step 1: Perform binary addition
Step 2: Bring the leftmost carry to rightmost
| 1 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | |
| 1 | ||||||||||||||||
| 1 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 1 |
54
Getting the Checksum (2/2)
Getting the Checksum
| Original | 1 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 1 |
| Complement | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 1 | 1 | 0 | 1 | 1 | 1 | 1 | 0 |
Step 3: One complement
Checksum: 0111 1000 1101 1110
55
Detecting Errors (1/2)
Valid 1st word: 1001 1011 0100 1001
Valid 2nd word: 1110 1011 1101 0111
1st word corrupted 3rd bit from right: 1001 1011 0100 1101
Checksum: 0111 1000 1101 1110
| 11 | 11 | 1 | 11 | 11 | 1 | 11 | 1 | 1 | ||||||||
| 1 | 0 | 0 | 1 | 1 | 0 | 1 | 1 | 0 | 1 | 0 | 0 | 1 | 1 | 0 | 1 | |
| 1 | 1 | 1 | 0 | 1 | 0 | 1 | 1 | 1 | 1 | 0 | 1 | 0 | 1 | 1 | 1 | |
| 0 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 1 | 1 | 0 | 1 | 1 | 1 | 1 | 0 | |
| 10 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 |
| 1 | ||||||||||||||||
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 |
Step 1: Perform binary addition with checksum
56
Detecting Errors (2/2)
Step 2: Spot the error bit
Error bit
| 11 | 11 | 1 | 11 | 11 | 1 | 11 | 1 | 1 | ||||||||
| 1 | 0 | 0 | 1 | 1 | 0 | 1 | 1 | 0 | 1 | 0 | 0 | 1 | 1 | 0 | 1 | |
| 1 | 1 | 1 | 0 | 1 | 0 | 1 | 1 | 1 | 1 | 0 | 1 | 0 | 1 | 1 | 1 | |
| 0 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 1 | 1 | 0 | 1 | 1 | 1 | 1 | 0 | |
| 10 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 |
| 1 | ||||||||||||||||
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 |
Valid 1st word: 1001 1011 0100 1001
Valid 2nd word: 1110 1011 1101 0111
1st word corrupted 3rd bit from right: 1001 1011 0100 1101
Checksum: 0111 1000 1101 1110
57
Practice 11.4
Calculate the Internet checksum for:
10101100 10010101
00100100 11100100
58
Reading
Douglas, C. (2016). Computer Networks and Internets, Global Edition (6th ed.). Pearson Education. ISBN: 978-1292061177 Chapter 8
59
End of Lesson
60
