Block Coding

Linear Block Codes

Cyclic Codes

Checksum

Hamming Codes

Type of Errors

Type of Errors

An electromagnetic signal is subject to interference from heat, magnetism, and other forms of electricity

Single-bit error: 0 1 or 1 0

Burst error: 2 or more bits have changed

Sender site:

1. The message is divided into 16-bit words.

2. The value of the checksum word is set to 0.

3. All words including the checksum are added using one’s complement

addition.

4. The sum is complemented and becomes the checksum.

5. The checksum is sent with the data.

Receiver site:

1. The message (including checksum) is divided into 16-bit words.

2. All words are added using one’s complement addition.

3. The sum is complemented and becomes the new checksum.

4. If the value of checksum is 0, the message is accepted; otherwise, it is

rejected.

**Forward Error Correction**

Purpose: An FEC (n, m) encoder

Take m-bit original data as input

Add r=n-k check bits to the original data to produce a n-bit codeword

The receiver can fix any error

**Hamming Distance**

Code: set of codewords

Hamming distance between 2 codewords is the number of bit positions where the 2 codewords differ

HammingDist(10001001, 10110001) = 3

Hamming distance of a code is the minimum Hamming distance between any two codewords in the code

HammingDist({0000000000,0000011111,1111100000,1111111111}) = 5

**Interesting Findings**

To detect d single-bit errors

Need a distance-(d+1) code

Appling d single-bit errors to a codeword must result in an invalid codeword. (WHY?)

To correct d single-bit errors

Need a distance-(2d+1) code

Given an incorrect codeword, the corresponding correct one must be the codeword closest in Hamming distance (WHY?)

**Linear Block Code: Hamming Code**

All Hamming codes discussed in our textbook have dmin = 3.

The relationship between k and n in these codes is n = 2k − 1

Single-Bit Error

Single-Bit Error

Only one bit of a given data unit is changed

The least likely type of error in serial transmission

Single-bit error can happen in parallel transmission

**Burst Error**

Two or more bits in the data unit have changed

Burst error does not necessarily mean that the errors occur in consecutive bits

Most likely to happen in a serial transmission

Number of bits affected depends on the data rate and duration of noise

Single Bit Error vs. Burst Error

**Error Detection**

Error detection uses the concept of redundancy, which means adding extra bits for detecting errors at the destination.

Redundancy for Error Detection

Parity Check

**Modular Arithmetic**

In modulo-N arithmetic, we use only the integers in the range 0 to N-1, inclusive.

Adding: 0 + 0 = 0 0 + 1 = 1 1 + 0 = 1 1 + 1 = 0

Subtracting: 0 – 0 = 0 0 – 1 = 1 1 – 0 = 1 1 – 1 = 0

XORing of two single bits or two words

**Block Coding**

Divide the message into blocks, each of k bits, called datawords.

Add r redundant bits to each block to make the length n = k + r. The resulting n-bit blocks are called codewords

Example: 4B/5B block coding

k = 4 and n = 5.

2k = 16 datawords and 2n = 32 codewords.

**Error Detection in Block Coding**

Assume the sender encodes the dataword 01 as 011 and sends it to the receiver. Consider the following cases:

1. The receiver receives 011 which is a valid codeword. The receiver extracts the dataword 01 from it.

2. The codeword is corrupted during transmission, and 111 is received. This is not a valid codeword and is discarded.

3. The codeword is corrupted during transmission, and 000 is received. This is a valid codeword. The receiver incorrectly extracts the dataword 00. Two corrupted bits have made the error undetectable.

An error-detecting code can detect only the types of errors for which it is designed; other types of errors may remain undetected

**Linear Block Code: Parity-Check Code**

A simple parity-check code is a single-bit error-detecting code in which n = k + 1 with dmin = 2.

**Encoder and Decoder for Parity-Check Code**

The result of addition over all 5 bits: syndrome

2-d Parity Check

2 Dimensional Parity-Check Code

2 Dimensional Parity-Check Code

**Cyclic Code: CRC**

Cyclic codes are special linear block codes with one extra property.

Cyclic Redundancy Check (CRC)

Checksum

Checksum

Tendency is to replace the checksum with a CRC

Not as strong as CRC in error-checking capability

One’s complement arithmetic

We can represent unsigned numbers between 0 and 2n – 1 using only n bits

If the number has more than n bits, the extra leftmost bits need to be added to the n rightmost bits (wrapping)

A negative number can be represented by inverting all bits. It is the same as subtracting the number from 2n – 1

**Internet Checksum**

## No comments:

## Post a Comment