Другие предметы \ Основы передачи дискретных сообщений

Data Compression. RunLength Encoding. Data Compression. Huffman Coding. Lempel-Ziv Compression, страница 3

a 1 b 2 c 3 d 4 e 5 f 6 g 7 h 8 i 9 j 10 k 11 l 12 m 13 n 14 o 15 p 16 q 17 r 18 s 19 t 20 u 21 v 22 w 23 x 24 y 25 z 26 _ 27

A special case

(yes, really!)

spin-s

R L L’

Error Detection and Correction

Error Detection

Tanenbaum 3rd edition: 183-190

ERROR DETECTION

Errors caused by noise Impulse (clicks) Crosstalk (between lines) Thermal (can’t eliminate)

Bank transactions

If we can detect errors, we can eliminate them Undetected errors can’t be eliminated altogether Aim for a detection rate high enough for application

Video transfer

Error Detection and Correction

Error Detection Methods

ERROR DETECTION

METHODS

Double sending

used by data prep operators not normally used in data comms

Parity

Add 1 or 0 after character to make total no of 1s even (even parity ) or odd (odd parity)

0111111 ↓ 01111110

with even parity: 1111111 ↓ 11111111

On arrival, no. of 1 bits in characters should still be even Single-bit corruptions make no. of 1 bits odd Two-bit corruptions are undetected.

Error Detection and Correction

Block Checksums

BLOCK CHECKSUMS

Sender sends byte sequence & XOR sum of byte sequence

Receiver calculates XOR sum of complete byte sequence detects error if calculated XOR sums is non-zero

does not detect two characters that are reversed.

Error Detection and Correction

Block Parity

BLOCK PARITY

Uses both longitudinal and horizontal parity.

conventional “horizontal” parity

“longitudinal” parity

Note: positional information => block parity can be used for error correction

Error Detection and Correction

CRCs

CRC (CYCLIC REDUNDANCY CHECK)

remainder

quotient

DATA

quotient

DATA’

Error Detection and Correction

CRCs

CRC (CYCLIC REDUNDANCY CHECK)

If data = 11100110, divisor = 11001 (D = 4 (x4 is the highest term)) add D 0s to the data divide, using rules of modulo-2 division: XOR instead of subtraction

Error Detection and Correction

CRCs

CRC (CYCLIC REDUNDANCY CHECK)

11001



0101

The CCITT polynomial (divisor) is x16 + x15 + x2+ x0

00000

1011

11000000000000101

11001

1110

11001

0101

00000

CRCs detect all single bit errors, most double bit errors, all error bursts <16 bits most error burst >16 bits.

1010

11001

1101

11001

0011

00000

Error Detection and Correction

Error Correction

ERROR CORRECTION

ARQ (Automatic Retransmission on reQuest) Most common in data comms if received data contains errors, request retransmission

FEC (Forward Error Control) Used where retransmission is undesirable Include extra information with message so it can be reconstructed Computer memory, or disk Simplex transmission from a data logger Transmissions from distant spacecraft

Error Detection and Correction

Hamming Codes

HAMMING CODES

Closer to 111 than to 000

Richard Hamming

Facilitate error detection and correction Use >1 bit to encode a bit

0 in data becomes codeword 000 1 in data becomes codeword 111

“Hamming Distance” = 3

000

Closer to 000 than to 111

With HD = 3, it is possible EITHER to detect 2-bit errors OR to correct 1-bit errors

To detect d bit errors, a code’s HD must be  d+1 To correct d bit errors, a code’s HD must be  2d+1

Error Detection and Correction

Hamming Codes

HAMMING CODES

Richard Hamming

So, for 2-bit error correction, HD  5

a 0000011111 b 0000000000 c 1111100000 d 1111111111

HD for some character-pairs is 10 But minimum intercharacter HD is 5, so HD for the whole code is 5. If 1 or 2 bits change, the result is nearer to the original valid codeword

0000011111 a 0000000000 b 1111100000 c 1111111111 d

0000011111

0000101111

Error Detection and Correction

Hamming Codes