11. Error Detection and Correction

data

It can be corrupted during transmission.

errors

For reliable communication, ____ must be detected and corrected.

single-bit error and burst error

types of error (HINT: SB)

single-bit error

Only one bit in the data unit has changed.

burst error

2 or more bits in the data unit have changed.

5 bits

What is the length of error?

• repetition

• redundancy

• parity check

• cyclic redundancy check (CRC)

• checksum

types of detection (HINT: RRPCC)

repetition

The simplest form of redundancy.

3-Repetition Code

Repeating each bit 3 times.

majority vote

What is the decoding rule for 3-Repetition Code?

3-Repetition Code

This code can correct 1 bit error per 3-bit codeword.

efficiency or rate of the code

The price we pay in redundancy is measured by the ____.

R

The efficiency or rate of the code is denoted by _.

R = # of information bits / # of bits in codeword

Formula for the efficiency or rate of the code (R)

33%

For the 3-repetition code: R = __

TRUE

[TRUE or FALSE] On average, the noisy channel flips 1 code bit in 100.

3333

The 3-repetition code makes only 1 information bit error in ____ bits.

100,000

The 5-repetition code makes only 1 information bit error in ____ bits.

2,857,142

The 7-repetition code makes only 1 information bit error in ____ bits.

perfect reliability

If we let the number of repetitions grow and grow, we can approach ____.

TRUE

[TRUE or FALSE] As the number of repetitions grows to infinity, the transmission rate shrinks to zero.

low storage density

As we increase the number of repetitions, this results in slow data transmission or _____.

error detection

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

redundancy

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

destination

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

• parity check

• cyclic redundancy check

• checksum

Detection methods (HINT: PCC)

even-parity check

A parity bit is added to every data unit so that the total number of 1s is even.

odd-parity check

A parity bit is added to every data unit so that the total number of 1s is odd.

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).

retransmission

In parity check, what happens after the data is discarded due to corruption during transmission?

TRUE

[TRUE or FALSE] Simple parity check can detect ALL single-bit errors.

odd

Parity check can only detect burst errors ONLY if the total number of errors in each data unit is ____.

two-dimensional parity check

In this type of parity check, a block of bits is divided into rows and a redundant row of bits is added to the whole block.

redundant row of bits

In two-dimensional parity check, a block of bits is divided into rows and a ______ is added to the whole block.

accepted

In CRC, if the remainder is zero, data is ____.

rejected

In CRC, if the remainder is nonzero, data is ____.

0000

In CRC, when the leftmost bit of the remainder is zero, we must use ____ instead of the original divisor.

a polynomial representing a divisor

polynomial

This can be used to represent a divisor.

standard polynomials

(HINT: CCII-AAHL)

TRUE

[TRUE or FALSE] The CRC is the remainder.

0

In CRC, if the remainder is ___, it means there were no transmission errors.

CRC-12

It has a degree of 12, will detect all burst errors affecting an odd number of bits, will detect all burst errors with a length less than or euqal to 12, and will detect, 99.97% of the time, burst errors with a length of 12 or more.

99.97%

CRC-12 has a degree of 12, will detect all burst errors affecting an odd number of bits, will detect all burst errors with a length less than or euqal to 12, and will detect, ___% of the time, burst errors with a length of 12 or more.

checksum

It is another relatively simple form of redundancy error checking where each character has a numerical value assigned to it.

checksum

The characters within a message are combined together to produce an error-checking character or _____, which can be as simple as the arithmetic sum of the numerical values of all the characters in the message.

TRUE

[TRUE or FALSE] Checksum takes place in both the sender and receiver.

accepted, rejected

In checksum, if the result is 0, data is ___; otherwise, ____.

• Unit is divided into k sections, each of n bits.

• All sections are added using one’s complement to get the sum.

• Sum is complemented and becomes the checksum.

• Checksum is sent with the data.

In checksum, the sender follows these steps: (HINT: UASC)

• Unit is divided into k sections, each of n bits.

• All sections are added using one’s complement to get the sum.

• Sum is complemented.

• If the result is zero, data is accepted; otherwise, rejected.

In checksum, the receiver follows these steps: (HINT: UASI)

k sections

In checksum, the unit is divided into ____, each of n bits.

one’s complement

In checksum, all sections are added using _____ to get the sum.

complemented

In checksum, the sum is _____.

1s

In checksum, when the receiver adds the k sections, it will get all __, which, after complementing, is all 0s and shows there is no error.

• retransmission

• burst error correction

• automatic-repeat-request (ARQ)

• forward error correction (FEC)

types of correction (HINT: RBAF)

data and redundancy bits

retransmission

It is when a receive station requests the transmit station to re-send a message (or a portion of a messgae) when the message is received in error.

ARQ

Because the receive terminal automatically calls for a retransmission of the entire message, retransmission is often called ____.

discrete ARQ and continuous ARQ

2 types of ARQ

discrete ARQ

It uses acknowledgment to indicate the successful or unsuccessful reception of data.

positive and negative

2 basic types of acknowledgments

continuous ARQ

It can be used when messages are divided into smaller blocks or frames that are sequentially numbered and transmitted in succession, without waiting for acknowledgments.

smaller blocks or frames

Continuous ARQ can be used when messages are divided into _____ that are sequentially numbered and transmitted in succession, without waiting for acknowledgments.

continuous ARQ

It allows destination station to asynchronously request the retransmission of a specific frame (or frames) of data and still be able to reconstruct the entire message once all frames have been successfully transported thru the system.

asynchronously

Continuous ARQ allows destination station to _____ request the retransmission of a specific frame (or frames) of data and still be able to reconstruct the entire message once all frames have been successfully transported thru the system.

selective repeat

Continuous ARQ is sometimes called _____.

transmitter

ARQ procedures require the _____ to resend the portions of the exchange in which error have been detected.

receiver

It discards frames in which errors are detected.

receiver

For frames in which no error was detected, the ____ returns a positive acknolwedgment to the sender.

negative

For the frame in which errors have been detected, the receiver returns _____ acknowledgment to the sender.

sender

It retransmits the frames in which the receiver has identified errors.

sender

After a pre-established time, the ______ retransmits a frame that has not been acknowledged.

• stop-and-wait

• go-back-n

• selective-repeat

3 common ARQ techniques (HINT: SGS)

stop-and-wait

The sender sends a frame and waits for acknowledgment from the receiver.

stop-and-wait

This ARQ technique is slow.

stop-and-wait

This ARQ technique is suited for half-duplex connection.

half-duplex connection

Stop-and-wait is suited for _______.

go-back-n

The sender sends frames in a sequence and receives acknowledgments from the receiver.

go-back-n

On detecting an error, the receiver discards the corrupted frame, and ignores any further frames.

go-back-n

The receiver notifies the sender of the number of frames it expects to receive.

TRUE

[TRUE or FALSE] In Stop-and-Wait protocol, no specific order is needed at receiver end. In Go-Back-N protocol, in-order delivery only are accepted at receiver end.

go-back-n

On receipt of information, the sender begins re-sending the data sequence starting from that frame.

go-back-n

This technique is faster than stop-and-wait technique.

selective-repeat

It is used on duplex connections.

selective-repeat

The sender only repeats those frames for which negative acknowledgments are received from the receiver, or no acknowledgment is received.

TRUE

[TRUE or FALSE] In selective-repeat, the appearance of a repeated frame out of sequence may provide the receiver with additional complications.

TRUE

[TRUE or FALSE] Go-Back-N protocol re-transmits all the frames whereas Selective Repeat protocol re-transmits only that frame which is damaged.

forward error correction (FEC)

It employs special codes that allow the receiver to detect and correct a limited number of errors without referring to the transmitter.

forward error correction (FEC)

Possible for the receiver to detect and correct errors without reference to the sender.

adding more bits

FEC’s ability to correct errors without reference to the sender is bought at the expense of ______.

forward error correction (FEC)

The only error-correction scheme that actually detects and corrects transmission errors when they are received without requiring a retransmission.

redundant bits

With FEC, ____ are added to the message before transmission.

redundant bits

In FEC, when an error is detected, the ______ are used to determine which bit is in error.

complementing

In FEC, correcting the bit is a simple matter of ______ it.

FEC example