ELFT 443 – Communications II
Introduction to Information Theory
Information
· A measure of the freedom of choice with which a message is selected from the set of all possible message
Information Measure
(bits)
where: Pj is the probability of transmitting the jth message
Average Information Measure
(bits)
where: m is the number of possible different source messages
Source Rate
(bits/sec)
Problems:
1. Find the information content of a message that contains a digital word 12 digits long in which each digit may take on one of four possible values. The probability of sending any one of the four levels is assumed to be equal and the level in any digit does not depend on the values taken in by previous digits. (24 bits)
2. A single digit, seven – segment liquid crystal display (LCD) emits a 0 with a probability of 0.25; a 1 and a 2 with a probability of 0.15 each; 3, 4, 5, 6, 7 and 8 with a probability of 0.07 each and a 9 with a probability of 0.03. Find the average information for this source.
3. A numerical keypad has the digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9. Assume that the probability of sending any one digit is the same as that for sending any other digits. Calculate how often the buttons must be pressed in order to send out information at the rate of 2 bits/second.
4. A digital source emits -1.0 & 0.0 V level s with a probability of 0.2 each and +3.0 & +4.0 V with a probability of 0.3 each. Evaluate the average information of the source. (1.97 bits)
Channel Capacity and Ideal Communication Systems
Claude Shannon showed that (for the case of signal plus white gaussian noise) a channel capacity C (bits/second) could be calculated such that if the rate of information R was less than C, the probability of error would approach zero. The equation for C is:
(bits/sec)
where B - channel bandwidth in Hertz
S/N - signal to noise power ratio (watts/watts, not dB) at the input to the digital receiver
Problems:
1. A computer user plans to buy a higher-speed modem for sending data over his or her analog telephone line. The telephone line has a signal-to-noise ratio of 25 dB and passes audio frequencies over the range from 300 to 3200 Hz. Calculate the maximum data rate that could be sent over the telephone line when there are no errors at the receiving end.
2. Evaluate the channel capacity for a teleprinter channel that has a 300 Hz bandwidth and a signal – to – noise ratio of 30 dB.
3. Assume that a computer keyboard has 110 characters and that each character is sent using binary words.
a. What is the number of bits needed to represent each character?
b. How fast can the character be sent (char/sec) over a telephone line channel having a bandwidth 3.2 kHz and a signal – to – noise ratio of 20 dB?
c. What is the information content of each character if each is equally likely to be sent?
Data Communication Codes
· are prescribed bit sequence used for encoding characters and symbols
Common Data Communication Codes
1. Baudot Code
o a simple alphanumeric code for telex machines and teleprinters which uses 5-bit characters plus a start and stop bit.
o also known as the Murray Code.
o This is the International Telegraphic Alphabet also known as the ASCII no. 2, since five bits can only produce 32 unique codes, two codes (figure shift and letter shift) are used to shift between figures function mode (with 31 characters) and a letter mode (with 31 characters).
o was developed by Thomas Murray and was named after Emile Baudot in 1875.
2. ASCII Code (American Standard Code for Information Interchange)
o ASCII No. 5 – is a 7 bit standard for characters, numeral, punctuation, space, carriage return, line-feed, and a few control command keys.
o The ISO adapted the 7-bit ASCII as the standard ISO-646 then modified it to 8 bits adding another 128 characters from the original and called it Latin 1.
o The 8 bit variation was standardized by IBM-compatibles and called it Extended ASCII
3. EBCDIC (Extended Binary Coded Decimal Interchange Code
o This is IBM’s unique 8-bit answer to the international use of the ASCII code system.
o It has 256 numbers, letters, and symbols. This was widely used by IBM mainframes.
Error Detection Techniques
Error Detection
· is the process of monitoring the received data and determines when a transmission error has occurred. It does not identify the bit or bits is/are in error, only that an error has occurred.
Three Classes of Probabilities:
1. Class 1: A frame arrives with no error.
2. Class 2: A frame arrives with one or more errors detected.
3. Class 3: A frame arrives with one or more errors but undetected.
Types of Errors:
1. Single-Bit Error
o means that only one bit of a given data unit is changed from 1 to 0 or 0 to 1.
2. Multiple-Bit Error
o means that two or more nonconsecutive bits in a data unit have changed from 1 to 0 or 0 to 1
3. Burst Error
o means that two or more consecutive bits in the data unit have changed from 1 to 0 or 0 to 1.
Error Detection Techniques
Redundancy
- this concept is used in most error detection techniques
- means adding extra bits for detecting errors at the destination
Four Types of Redundancy Checks
a. Vertical Redundancy Check (VRC)
- a redundant bit, called the parity bit, is appended to every data unit so that the total number of 1s in the unit (including the parity bit) becomes either even for even-parity check or odd for odd-parity check.
- determines if a transmission error has occurred within a data unit
- can detect all single-bit errors; also can detect multiple-bit or burst errors only if the total number of errors is odd.
b. Longitudinal Redundancy Check (Horizontal Redundancy Check)
- a redundant unit is added after a number of data units.
- determines if a transmission error has occurred in a message
- can not detect multiple-bit or burst errors if an even number of error has occurred in corresponding positions in any even number of data units
c. Cyclical Redundancy Check
- instead of adding bits together to achieve a desired parity, a sequence of redundant bits, called the CRC or the CRC remainder, is appended to the end of a data unit so that the resulting data unit becomes exactly divisible by a second, predetermined number.
- the redundancy bits are derived by dividing the data unit by the predetermined divisor, the remainder is the CRC.
- the CRC must have to qualities:
· it must be exactly one less bit than the divisor
· appending it to the end of the data string must make the resulting bit sequence exactly divisible by the divisor
Steps in deriving the CRC:
1. A string of n 0s are appended to the end of the data unit. The number n is one less than the number of bits in the predetermined divisor.
2. The newly elongated data unit is divided by the divisor using a process called binary division. The remainder resulting from this division is the CRC.
3. The derived CRC of n bits replaces the appended 0s at the end of the data unit.
a. If the derived remainder has fewer than n bit, the missing, the leftmost, bits are presumed to be 0s.
b. If the division process has not yielded a remainder at all, it means that the original data is already divisible by the divisor, and the n 0s take the place of a remainder as the CRC.
The CRC generator
- the CRC generator or the divisor is most often represented as an algebraic polynomial.
Types of CRC
1. CRC-12 x12+x11+x3+x+1
2. CRC-16 x16+x15+x2+1
3. CRC-ITU x16+x15+x5+1
4. CRC-32 x32+x26+x23+x22+x16+x12+x11+x10+x8+x7+x6+x5+x4+x2+1
d. Checksum
- the error detection method used by the higher protocols
The Checksum Generator
To create the checksum, the sender does the following:
1. The unit is divided into k sections, each of n bits.
2. Sections 1 and 2 are added together using one’s complement.
3. Section 3 is added to the result of the previous step.
4. The process repeats until section k is added to the result of the previous step.
5. The final result is complemented to make the checksum.
The Checksum Checker
The receiver divides the data unit (the last segment will be the checksum field) and adds all segments together. If the extended data is intact, the total value found by adding the data segments and the checksum field should be zero. If the result is non zero, the packet contains an error and the receiver rejects it.
Error Correction Techniques
1. Symbol Substitution
- designed to be used in human environment: when there is a human at the receiving terminal to analyze the received data and make decisions on its integrity.
- When there is a character error, a reversed ( ? ) is placed and it is up to the operator to correct it; if the operator can not discern the true character, retransmission will be required.
2. Retransmission
- re-sending of a message when it is received in error and the receiving terminal automatically calls for retransmission of the entire message.
- often called ARQ (automatic request for retransmission)
3. Forward Error Correction
- the only error detection scheme that actually detects and corrects transmission errors at the receive terminals without calling retransmission
- bits are added to the message prior to transmission called the Hamming code (dependent on the number of bits in the data character.
2n >= m + n + 1
where m: number of bits in the data character
n: number of hamming bits
17
ermtiong