Chapter 3



Chapter 3 Codes

Purposes:

• How to use binary combinations to represent code characters?

• How to detect or correct an error (errors) generated when information bits are transmitted over a communications channel?

Codes can represent digits, letters, punctuation marks, control characters, words, strings, pictures, etc.

What we are going to study:

• BCD code and other weighted/unweighted codes for the ten decimal digits;

• ASCII code;

• Error detecting and correcting codes;

Binary Coded Decimal (BCD) Characters

BCD code 2421 code

0 0000 (0) 0

1 0001 (1) 1

2 0010 (2) 2

3 0011 (3) 3

4 0100 (4) 4

5 0101 (5) 5

6 0110 (6) 6

7 0111 (7) 7

8 1000 (8) 8

9 1001 (9) 9

1010 (A)

1011 (B)

1100 (C)

1101 (D)

1110 (E)

1111 (F)

The number of total possible codes to represent the ten decimal characters is [pic], since the first character has 16 choices, the second one has 15 choices, … and the last one has [pic]choices.

Example: The decimal number 9872 is represented in BCD as

Weighted Codes: There exists a fixed weight associated with each bit position in the binary representation of the code character. Weighted code character can be represented by [pic], where [pic] is the bit and [pic] is the weight at position [pic].

• Weight can be positive and negative. For example, weights 8,4,-2,-1 define one mapping (coding) for decimal numbers

• For each group of weight, there may exist multiple codes. For example, there are 36 different codes that can use weights 3,3,2,1

• There are only 70 weighted-code groups that represent decimal digits, among which 17 are positive.

Examples: All codes within group 3,3,2,1 and group 8,4,-2,-1

Unweighted Codes:

• Excess-3 code (XS3): adds binary 3 to each character of the BCD code. It is self-complementing and used in the early Univac I computer.

• Gray code: only a single bit changes between any two consecutive code characters.

Properties of Codes:

• Self-complementing codes: 9’s complement in decimal is the 1’s complement in binary. Example: the 2,4,2,1 code, the XS3.

If a weighted code is self-complementing, the total weight must be 9.

• Reflective codes: a code that reflects the bit pattern of its characters about its mid point. Example: the gray code.

Algorithm: to compute the corresponding Gray code character for the binary number and vice versa.

Let [pic] be the binary numbers, and let [pic] be the corresponding Gray code characters, then

[pic] [pic]

Example: For the binary number 101101, compute the Gray code character.

Alphanumeric Code

ASCII: 7 bits per character

EBCDIC: introduced by IBM. 8 bits per character.

Latin-1: Can support characters with accent marks in Spanish and French. 8 bits per character.

Unicode: 16 bits character. Can represent non-Latin characters.

Read the text yourself for more.

Note: Your hello.c is stored in a file as a sequence of bytes. Each byte has an integer value corresponding to some character. This value is the ASCII code of the character.

Control of Transmission Errors

Sources of transmission errors: electrical noise, inter-symbol interference, electrical echo, crosstalk, environmental interference, etc.

Transmission errors can not be completely avoided but can be detected and/or corrected.

Error Detecting Codes

Definition:

The Hamming Distance of two code characters is the number of bit positions in which the two code characters differ.

The Distance of a code is the minimum distance between any pair of the code characters.

Example: What is the distance of the BCD code?

Remark: To detect [pic] errors, we need a distance of [pic] code; To correct [pic] errors, we need a distance of [pic] code.

Justification:

One bit error detection: use a parity bit to detect a one-bit error: even or odd parity.

Question: why the one bit parity makes the code distance to become two?

Practice Problem: Fill the blanks of the table.

|Decimal |BCD |Odd Parity |Odd Parity Code |Even Parity |Even Parity Code |

|0 | | | | | |

|1 | | | | | |

|2 | | | | | |

|3 | | | | | |

|4 | | | | | |

|5 | | | | | |

|6 | | | | | |

|7 | | | | | |

|8 | | | | | |

|9 | | | | | |

Probability of detecting an error with parity:

• Using one parity bit can detect that an odd number of bits have changed!

• Error detection probability analysis

Error Correcting Codes (Hamming Codes)

We know to correct [pic] errors, we need a distance of [pic] code. Consider the case of [pic]. For a code containing [pic]-bit code characters, how many check bits do we need in order to change the distance of the code from 1 to 3? Let [pic] be the number of check bits.

Example: compute [pic]for [pic].

By adding 3 check bits, we obtain the Hamming (7,4) code, which indicates that in each code character, there are 4 bits data and 3 bits for error correction.

Questions: How to build the one-bit error correcting code after computing the number of check bits? How to detect the one bit error if it occurs?

In 1950, Hamming proposed a method to answer the above questions. The resultant error correction code is called a Hamming Code.

Idea:

let [pic] denote the bit positions in the resultant hamming code, among which [pic], [pic], are check bit positions and others are data bit positions.

The check bit at position [pic] checks the data bit at position [pic] if [pic] [pic] [pic]. Here [pic] is a logic (bit-wise) [pic] operation.

The [pic] of each check bit and all its checked data bits must be zero if no errors occur.

Let [pic] be the [pic] results. [pic] represents the data bit position that an error occur. If [pic] is 0, then no errors occur.

Example: Construct the Hamming code for the BCD code.

|Decimal |BCD |(7,4) Hamming Code |Notes |

|0 | | | |

|1 | | | |

|2 | | | |

|3 | | | |

|4 | | | |

|5 | | | |

|6 | | | |

|7 | | | |

|8 | | | |

|9 | | | |

Example: If bit position 3 has an error for decimal 6, what is the received code character? How this error is corrected?

Remarks:

1. Hamming codes can correct only one-bit errors

2. By adding one additional parity bit to each Hamming code character, we obtain a single-error correcting, double-error detecting code.

Polynomial Codes

Polynomial codes are used to compute the CRC (Circular Redundancy Check) checksum widely used in computer networks for error detection. It is called polynomial codes because a polynomial is used to represent the bits in the code word.

A code polynomial is the polynomial to represent the code [pic], which can be written as [pic], where coefficients [pic] [pic].

For a [pic] bit polynomial code, its code polynomial has order (degree) [pic].

Example: The polynomial code 11001011 can be written as [pic].

Arithmetic Operations on Code Polynomials:

• Addition, Subtraction, Multiplication, and Division are defined as in ordinary algebra, except that in modulo-two arithmetic is used to compute coefficients.

• In modulo-two arithmetic, both addition and subtraction are equivalent to xor operation.

Example: [pic] and [pic]. Then

[pic]

[pic]

[pic]

[pic]

Example: [pic], [pic]. Compute [pic].

The quotient [pic] is

The Remainder [pic] is

Question: How to compute the CRC checksum given the code polynomial [pic] for the data bits?

• We need a generating polynomial [pic], which contains the term [pic], and has degree [pic], where [pic] is the required number of bits in the CRC checksum.

• Compute [pic], which results in [pic] and [pic]. The checksum contains the coefficients of [pic].

• Sender transmit [pic]; Receiver check whether the remainder of [pic] is 0 or not.

• If the remainder is not a 0, then errors occur.

Standardized generating polynomial used in computer networks:

CRC-5:

CRC-12:

CRC-16:

CRC-CCITT:

CRC-32:

CRC-16, CRC-CCITT, and CRC-32 are the most popular ones in data link layer and network layer of the protocol stack.

Error Detecting Capabilities of Polynomial Codes:

• Strong.

• Special requirement for the generating polynomial.

Hamming codes are a subset of polynomial codes!

................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download