Lecture 6-7 - Error Detection and Correction

Technique to use to detect error in data transmission

• Midterm Exam for sure!

Transmission Modes

Overview

• Parallel Mode: The way internal transfer of binary data takes place inside a computer
  
• Serial Mode: The predominant method of transferring information in data communications
  

Parallel Transmission

• Bits in a group are sent simultaneously, each using a separate link
• n wires are used to send n bits at one time
• Advantage: Speed
• Disadvantage: Cost; limited to short distances

Serial Transmission

• Transmission of data one bit at a time using only one single link
• Advantage: Reduced cost
• Disadvantage: Requires conversion devices
• Methods:
  • Asynchronous
  • Synchronous

Asynchronous and Synchronous Transmission

เราใช้ Clock ในการ sync

Timing Problems

• Timing problems require a mechanism to synchronize the transmitter and receiver
• Receiver samples stream at bit intervals
• If clocks not aligned and drifting will sample at wrong time after sufficient bits are sent
• Two solutions to synchronizing clocks:
  • Asynchronous transmission
  • Synchronous transmission

Asynchronous Transmission

เหมือนพิมพ์คีย์บอร์ด เร็วบ้าง ช้าบ้าง ถือว่าเป็น Asynchronous

• Transfer of data with start and stop bits and a variable time interval between data units
• Timing is unimportant
• Start bit alerts receiver that new group of data is arriving (IMPORTANT)
• Stop bit alerts receiver that byte is finished
• Synchronization achieved through start/stop bits with each byte received
  • Requires additional overhead (start/stop bits)
• Slower, ideal for low-speed communication when gaps may occur during transmission (ex: keyboard)
• Cheap and effective

Gaps between data units can be different (vary)

Key Notes:

• In asynchronous transmission, we send one start bit (0) at the beginning and one or more stop bits (1s) at the end of each byte
• There may be a gap between each byte
• Asynchronous here means "asynchronous at the byte level," but the bits are still synchronized; their durations are the same

คือพูดง่าย ๆ ถ้ามองเข้าไปถึง level Data bit ข้างในก็ยังใช้ Clock ยังต้อง Sync อยู่

Asynchronous Behavior

• Simple
• Cheap
• Overhead of 2 or 3 bits per char (~20%)
• Good for data with large gaps (keyboard)

Synchronous Transmission

• Requires constant timing relationship
• Bit stream is combined into longer frames, possibly containing multiple bytes
• Any gaps between bursts are filled in with a special sequence of 0s and 1s indicating idle
• Advantage: Speed, no gaps or extra bits
• Byte synchronization accomplished by data link layer

Key Notes:

• In synchronous transmission, we send bits one after another without start/stop bits or gaps
• It is the responsibility of the receiver to group the bits

Synchronous Characteristics

• Block of data transmitted sent as a frame
  • ส่งเป็น Frame (ก็คือ a group of character นั่นแหละเด้อ)
• Clocks must be synchronized
  • Can use separate clock line
  • Or embed clock signal in data
• Need to indicate start and end of block
  • Use preamble and postamble
• More efficient (lower overhead) than async

Error Detection

Overview

• Data can be corrupted during transmission
• For reliable communication, errors must be detected and corrected
• Detect using error-detecting code
• Added by transmitter
• Recalculated and checked by receiver
• Still chance of undetected error

Parity

Additional bit

• Parity bit set so character has even (even parity) or odd (odd parity) number of ones
• Even number of bit errors goes undetected

Types of Errors

Single-bit Error

• Single bit errors are the least likely type of errors in serial data transmission
• The noise must have a very short duration which is very rare
• However this kind of errors can happen in parallel transmission
• Example:
  • If data is sent at 1Mbps then each bit lasts only 1/1,000,000 sec. or 1 μs
  • For a single-bit error to occur, the noise must have a duration of only 1 μs, which is very rare

เวลามี Noise หรือว่าอะไรมันก็ควรเกิดนาน ๆ การที่จะมาเปลี่ยนแค่ 1 bit โอกาสเกิดน้อยจ้า

Burst Error

• Caused by Interference (ex. Impulse noise)
• Two or more bits in the data unit have changed
  • Doesn’t have to be consecutive bits
• Most likely to happen in a serial transmission
• Number of bits affected depends on the data rate and duration of noise

อันนี้จำให้ดี ในข้อสอบอาจจะถาม Length of burst error ก็ได้ ไม่ได้นับเฉพาะ Bit ที่เปลี่ยนไปนะ ดูจากรูปได้เลย

Key Notes:

• The term burst error means that two or more bits in the data unit have changed from 1 to 0 or from 0 to 1
• Burst errors ==does not necessarily mean that the errors occur in consecutive bits==
• The length of the burst is measured from the first corrupted bit to the last corrupted bit
• Some bits in between may not have been corrupted
• Burst error is most likely to happen in serial transmission since the duration of noise is normally longer than the duration of a bit
• The number of bits affected depends on the data rate and duration of noise

Example:

• If data is sent at rate = 1Kbps then a noise of 1/100 sec can affect 10 bits (1/100*1000)
• If same data is sent at rate = 1Mbps then a noise of 1/100 sec can affect 10,000 bits (1/100*10^6)

ถ้า Data ส่งไวขึ้น แต่ว่า noise เกิดเท่าเดิม ก็จะ effect a lot more!

Error Detection Methods

Overview

• Error detection means to decide whether the received data is correct or not without having a copy of the original message
• Error detection uses the concept of redundancy, which means adding extra bits for detecting errors at the destination

Four Types of Redundancy Checks

Used in data communications:

1. Vertical Redundancy Check (VRC)

• In parity check, a parity bit is added to every data unit so that the total number of 1s is even (or odd for odd-parity)
• Even-Parity Check: Simple parity check can detect all single-bit errors
• Can detect burst errors only if the total number of errors in each data unit is odd

Even-parity generator จะนับ bit 1 ใน data ว่ามีกี่ตัว — อย่างในรูปมี 3 bits
โดยสิ่งที่ EPG จะทำก็คือ จะ add 1 เข้าไป 1 ตัวด้านหลังให้มันกลายเป็น even (4 bits นั่นเอง)

Example 1:

• Suppose the sender wants to send the word "world"
• In ASCII the five characters are coded as:
  • 1110111 1101111 1110010 1101100 1100100
• The following shows the actual bits sent using even parity bit technique:
  • 11101110 11011110 11100100 11011000 11001001

Example 2:

• Now suppose the word "world" in Example 1 is received by the receiver without being corrupted in transmission:
  • 11101110 11011110 11100100 11011000 11001001
• The receiver counts the 1s in each character and comes up with even numbers (6, 6, 4, 4, 4)
• The data are accepted

Example 3:

• Now suppose the word "world" in Example 1 is corrupted during transmission:
  • 11111110 11011110 11101100 11011000 11001001
• The receiver counts the 1s in each character and comes up with even and odd numbers (7, 6, 5, 4, 4) — มีบางอันเป็น Odd, ดังนั้นก็ reject!
• The receiver knows that the data are corrupted, discards them, and asks for retransmission

รูปข้างบนหมายถึงว่ามันก็ยังมีโอกาสผิด ดันไปผิด 2 bits เพราะมันแค่ odd กับ even เอง

Performance:

• It can detect single bit error
• In case of even-parity, it can detect burst errors only if the total number of errors is odd

2. Longitudinal Redundancy Check (LRC)

LRC ที่ได้จาก 4 อัน ไม่ได้เอามาบวกกันนะ ดูว่าถ้ามีจำนวนเลข 1 เป็น Even เป็น 0, Odd เป็น 1 แล้วเอาทั้งอันนั้นแหละไปยัด at the end of the data stream

• LRC is an error-detection method for determining the correctness of transmitted and stored data
• LRC verifies the accuracy of stored and transmitted data using parity bits
• It is a redundancy check applied to a parallel group of bit streams

Example:

• คือข้างบนดูเป็น bit ๆ ไปนะ ถ้าท้ายสุด 1, 1, 1, 1 เป็น even ก็ใส่ 0 and vice versa
• จะ append ไว้หน้าหรือหลัง จริง ๆ ก็ไว้ที่เดียวมั้ง แต่ต้องดู direction ดี ๆ

Performance:

• LRC increases the likelihood of detecting burst errors
• However, if two bits in one data units are damaged and two bits in exactly the same positions in another data unit are also damaged, the LRC checker will not detect an error → ยังแอบพังได้อยู่

3. Two-dimensional Parity

เอา 1, 2 มารวมกัน เป็นแกงโฮะเลยล่ะ

4. Cyclic Redundancy Check (CRC)

Overview:

• Given a k-bit frame or message, the transmitter generates an n-bit sequence, known as a frame check sequence (FCS)
• The resulting frame, consisting of (k+n) bits, is exactly divisible by some predetermined number
• The receiver then divides the incoming frame by the same number and, if there is no remainder, assumes that there was no error
  

1. เรามี Data + n bits (initially set ให้เป็น 0) ดังนั้น length มันเป็น $k+n$
2. Divisor will be given: length $n+1$
3. จะได้ Remainder เป็น CRC $n$ bits
4. Sender replace $n$ bits ด้วย CRC

หลังจากส่งไป อีกฝ่ายก็จะได้รับแล้วก็ใช้ Divisor ตัวเดียวกัน ถ้าได้ 0 accept; otherwise reject!

CRC Generator Process:

1. Given the length of CRC to be n bits
2. Select Divisor that has n+1 bits and the leftmost bit must be 1
3. Append n bits of zero (0) to the data
4. Divide the result from 3. by the Divisor using Binary Division
5. The remainder is CRC (if less than n bits, fill with 0 at the leftmost)
6. Replace the CRC from 5 (replace 0 bits in 3.)

Binary Subtraction:

• Similar to XOR operation

CRC Generator Example:

• Given 6 bits of data and 4 bits of Divisor

CRC Checker Process:

1. Receive data with CRC (k+n bits)
2. Use the same Divisor
3. Divide the receive data frame from 1) by the Divisor using Binary Division
4. If the remainder equals to zero then the data is correct, otherwise the data is corrupted and need to be resent

CRC Checker (at receiver)

Polynomial Representation for CRC

Polynomials for Cyclic Redundancy Check

• Second way of viewing the CRC process
• Express all values as polynomials in a dummy variable X with binary coefficients
• k message bits and n bits of redundancy

Converting Binary to Polynomial

Example: 1 0 1 1 0 1 1
$1x^6 + 0x^5 + 1x^4 + 1x^3 + 0x^2 + 1x^1 + 1x^0 = x^6 + x^4 + x^3 + x + 1$

CRC Polynomial Process

• M(x) = message polynomial
• P(x) = generator polynomial (divisor)
  • P(x) is fixed for a given CRC scheme
  • P(x) is known both by sender and receiver
• F(x) = block polynomial based on M(x) and P(x)
• Create F(x) such that F(x) is divisible by P(x)

$\boxed{\frac{F(x)}{P(x)} = Q(x) + \frac{0}{P(x)}}$

where $Q(x)$ = quotient

Polynomial CRC Steps

Sending (Transmitter)

1. Multiply M(x) by $x^n$
2. Divide $x^n M(x)$ by P(x)
3. Ignore the quotient and keep the remainder C(x)
4. Form and transmit F(x) = $x^n M(x)$ + C(x)

Receiving (Receiver)

1. Receive F'(x)
2. Divide F'(x) by P(x)
3. Accept if remainder is 0, reject otherwise

Proof of CRC Generation

Prove that $x^n M(x) + C(x)$ is divisible by P(x)

Given: $P(x) \overline{) x^n M(x)}$, remainder C(x)

Therefore: $x^n M(x) = P(x)Q(x) + C(x)$

$\frac{x^n M(x) + C(x)}{P(x)} = \frac{P(x)Q(x)}{P(x)} + \frac{C(x) + C(x)}{P(x)}$

$\downarrow$

Remainder 0

Note: Binary modular addition is equivalent to binary modular subtraction, which is C(x) + C(x) = 0

Polynomial Division Example

• The divisor in a cyclic code is normally called the generator polynomial or simply the generator

Example from textbook:

• $M(x)$ = 110011 → $x^5+x^4+x+1$ (6 bits)

• $P(x)$ = 11001 → $x^4+x^3+1$ (5 bits = n+1 bits) → ดังนั้น $n$ เฉย ๆ คือ 4 bits

• Form $x^nM(x)$ → 110011 0000 (ก็คือ add 4 bits of zeros ไว้ท้ายนั่นแหละ)

  • $x^9+x^8+x^5+x^4$

• Divide $x^nM(x)$ by $P(x)$ to find $C(x)$

• Then transmit $F(x)=x^nM(x)+C(x)$

มี Example ใน Textbook ด้วย ที่มันยาว ๆ ไปทำด้วย

ทำจนกว่าจะได้กำลังน้อยกว่า $x^5$ (หมายถึงตรง $x^3$ นะที่จะหยุด)

Standard Polynomials

Characteristics of Good Polynomial Generator

1. It should have at least two terms
2. The coefficient of the term $x^0$ should be 1
3. It should not divide $x^t + 1$, for t between 2 and n − 1
4. It should have the factor x + 1

Common Standard Polynomials

Checksum

Checksum Overview

• Tendency is to replace the checksum with a CRC
• Not as strong as CRC in error-checking capability
• Uses one's complement arithmetic
• Represents unsigned numbers between 0 and $2^n – 1$ using only n bits
• If number has more than n bits, extra leftmost bits are added to n rightmost bits (wrapping)
• Negative number represented by inverting all bits (same as subtracting from $2^n – 1$)

Checksum Process

At the Sender

1. Unit is divided into k sections, each of n bits
2. All sections are added together using one's complement to get the sum
3. The sum is complemented and becomes the checksum
4. The checksum is sent with the data

At the Receiver

1. Unit is divided into k sections, each of n bits
2. All sections are added together using one's complement to get the sum
3. The sum is complemented
4. If the result is zero, data are accepted; otherwise, rejected

Data ถูก divide เป็น $K$ section แต่ละ section มี $n$ bits แล้ววางเป็น Vertical แล้วก็ sum them together แล้วก็เอาไป complement อีก แล้ว final ก็เอาไป append ไว้ด้านหลัง

Checksum Example

• Sender initializes checksum to 0 and adds all data items and checksum
• If sum exceeds n bits, extra bits are wrapped and added to create wrapped sum
• Sum is then complemented to get final checksum

Checksum Performance

• Detects all errors involving an odd number of bits
• Detects most errors involving an even number of bits
• Limitation: If one or more bits of a segment are damaged and corresponding bits of opposite value in a second segment are also damaged, sums of those columns will not change and receiver will not detect problem

Error Correction

Error Correction Methods

Two ways to handle error correction:

1. Receiver can have sender retransmit entire data unit - ให้ต้นทางส่งใหม่ซะ
2. Receiver can use error-correcting code which automatically corrects certain errors - หรือมี Technique ของตัวเองที่จะแก้ error

Single-bit Error Correction

• To correct an error, receiver reverses the value of altered bit
• Must know which bit is in error

Number of Redundancy Bits Needed

Let:

• m = data bits
• r = redundancy bits
• m+r = total message sent

Formula: $\boxed{2^r \geq m + r + 1}$

Hamming Code Technique

• ใช้กับ One single bit correction!!
  
  ==
  

อ่อ แบบว่าถ้า Data ตรง position ไหนมีตำแหน่ง 1 อยู่ที่ตำแหน่ง ๆ ไหนเหมือนกัน ก็ให้รับ $r$ บางตัวรับผิดชอบไปเลย

Hamming Code Example

Given data: 1001101
Requirements: $2^r \geq m + r + 1$ where m = 7, so r = 4 — ลองแทนไปเรื่อย ๆ เลยล่ะ

คือ Position สีเหลืองคือตัวที่รับผิดชอบ ตำแหน่งไล่ตามแบบ $2^x$ ไปเรื่อย ๆ — แล้วในสีเหลืองจะใส่อะไร เราก็อาจจะใช้ Even parity ก็ได้

Error Detection in Hamming Code

• Uses even parity
• Each redundancy bit checks specific positions
• Error syndrome indicates error position
• If all parity checks pass → no error
• If parity checks fail → error position = binary value of failed checks

Single-bit Error Example

Error Detection Process:

• Check each parity bit group
• Failed checks create binary number
• Binary number indicates error position
• Result: Error in position 7 (0111 in binary)

The error can then be corrected by flipping the bit at the identified position.