Data Communication and Computer Networks

DATA COMMUNICATION AND Course Instructor : Dr. C. Sreedhar AND COMPUTER NETWORKS Some slides are copies from Forouzan and internet sources

Unit 2 Physical layer and Transmission Media:  Analog and digital signals,  Digital signals –Bit rate, Bit length,  Transmission of digital signals, Transmission Impairments – Attenuation, Distortion and Noise, Transmission Impairments – Attenuation, Distortion and Noise, Performance – Bandwidth, Throughput, Latency, Jitter. Data Link Layer:  Error detection – Introduction, Block coding – error detection, error correction,  hamming distance and minimum hamming distance, CRC codes, Checksum.

Digital Signals  In addition to being represented by an analog signal, information can also be represented by a digital signal.  For example, a 1 can be encoded as a positive voltage  For example, a 1 can be encoded as a positive voltage and a 0 as zero voltage.  A digital signal can have more than two levels. In this case, we can send more than 1 bit for each level. Some slides are copies from Forouzan and internet sources

A digital signal has eight levels. How many bits are needed per level? We calculate the number of bits from the formula Example Each signal level is represented by 3 bits.

Assume we need to download text documents at the rate of 100 pages per minute. What is the required bit rate of the channel? (assuming each page is an average of 24 lines with 80 characters in each line, and one character requires 8 bits) Example Solution Solution The bit rate is

Digital Signals  digital signals can be transmitted by using one of two different approaches:  baseband transmission  baseband transmission  broadband transmission

Baseband Transmission  Baseband Transmission: sending digital signal without changing digital to an analog signal. Baseband communication requires a low-pass channel Low pass channel: a channel with a bandwidth that starts from zero Example: Baseband Ethernet such as 10Base5, 100BaseT

Broadband Transmission  Broadband transmission or modulation means changing the digital signal to an analog signal for transmission. transmission.  If the available channel is a bandpass channel then we cannot send digital signal directly to the channel; Conversion from digital signal to an analog signal must be done before transmission.

Transmission Impairment  Three causes of impairment are  Attenuation: Loss of energy  Distortion: Change in the shape of the signal  Distortion: Change in the shape of the signal  Noise: Caused by thermal, crosstalk, lightening etc.,

Attenuation: causes  Attenuation: signal strength falls off with distance.  When a signal travels through a medium it loses energy overcoming the resistance of the medium  Loss or gain of energy the unit “decibel” is used. Loss of Energy  Loss or gain of energy the unit “decibel” is used. dB = 10log10 P2/P1 P1 - input signal P2 - output signal  Negative value of dB indicates signal is attenuated  Positive value of dB indicates signal is amplified

Attenuation: solution Attenuation is dealt with the use of amplifiers or repeaters.

Attenuation: Problem 1  A signal travels through a transmission medium and its power is reduced to one-half. Calculate the loss of energy.  Solution: Assuming P1 and P2 are input and output signals. Assuming P1 and P2 are input and output signals. According the problem, P2 is reduced to one-half; ie., P2 = P1/2; dB = 10log10(1/2*P1)/P1 = 10 * (-0.3) = -3dB

Attenuation: Problem 2  a signal travels from point 1 to point 4.  decibel value (loss of energy) can be calculated as dB = -3 + 7 + (-3) dB = 1

Attenuation: Problem 3 A signal travels through an amplifier, and its power is increased 10 times. This means that P2 = 10P1 . In this case, the amplification (gain of power) can be calculated as the amplification (gain of power) can be calculated as

Distortion  Change of signal in its form or shape.  Occurs in a composite signal made of different frequencies. frequencies.  Signal components at the receiver have phases different from what they had at the sender.  The shape of the composite signal is therefore not the same.

Noise  In data transmission, received signal can consists of actual transmitted signals and unwanted signals.  Undesired signal is referred as noise.

 Thermal noise: random motion of electrons in a wire which creates an extra signal (undesired signal).  Induced noise: caused due to motors and appliances.  Cross-talk is the effect of one wire on the other. One wire acts as a sending antenna and the other as the receiving acts as a sending antenna and the other as the receiving antenna.  Impulse noise is a spike (a signal with high energy in a very short time) that comes from power lines, lightning, and so on.

The signal-to-noise ratio is defined as: SNR = average signal power / average noise power SNRdB, defined as: SNRdB = 10 log10 SNR

Performance  Bandwidth  Throughput Latency  Latency  Jitter

Bandwidth  Range of frequencies in a composite signal  Measured using Hz when Analog signals are transmitted Measured using bps when Digital signals are transmitted  Measured using bps when Digital signals are transmitted

Bandwidth  The range of frequencies contained in a composite signal is its bandwidth.  Bandwidth of a composite signal is the difference  Bandwidth of a composite signal is the difference between the highest and the lowest frequencies contained in that signal.

If a periodic signal is decomposed into five sine waves with frequencies of 100, 300, 500, 700, and 900 Hz, what is its bandwidth? Draw the spectrum, assuming all components have a maximum amplitude of 10 V. Solution Let fh be the highest frequency, fl the lowest frequency, and B the bandwidth. Then B the bandwidth. Then

A periodic signal has a bandwidth of 20 Hz. The highest frequency is 60 Hz. What is the lowest frequency? Draw the spectrum if the signal contains all frequencies of the same amplitude. Solution Let fh be the highest frequency, fl the lowest frequency, and B the bandwidth. Then B the bandwidth. Then

Throughput  Throughput is a measure of how fast we can actually send data through a network.  Throughput is the actual amount of data that is successfully  Throughput is the actual amount of data that is successfully sent/received over the communication link A network with bandwidth of 10 Mbps can pass only an average of 12,000 frames per minute with each frame carrying an average of 10,000 bits. What is the throughput of this network?

Latency (Delay)  The latency or delay defines how long it takes for an entire message to completely arrive at the destination from the time the first bit is sent out from destination from the time the first bit is sent out from the source. Latency = propagation time + transmission time + queuing time + Processing delay

Latency  Propagation time:  Time required for a bit to travel from source to destination.  Propagation time = Distance / Propagation speed  Transmission time = Message Size / Bandwidth  Processing delay : Amount of time required to process packet header, check for bit-level errors, and determine the packet’s destination  Queuing time:  Time needed for each intermediate or end device to hold the message before it can be processed.

Jitter  Jitter is defined as a variation in the delay of received packets.  Jitter is a problem if different packets of data  Jitter is a problem if different packets of data encounter different delays and the application using the data at the receiver site is time sensitive (Ex: audio and video data)

Summary: Performance  Bandwidth is a measure of how much data over time a communication link can handle, its capacity.  Latency is the time it takes for a packet to get  Latency is the time it takes for a packet to get across the network, from source to destination.  Throughput is the actual amount of data that is successfully sent/received over the communication link.

Data Link Layer  Error detection  Block coding Error Correction  Minimum hamming distance  CRC Codes Checksum  Error Correction  Hamming distance  Checksum  Framing  Flow and Error Control

Data Link Layer  Networks must be able to transfer data from one device to another with complete accuracy.  Data can be corrupted during transmission.  Data can be corrupted during transmission.  For reliable communication, errors must be detected and corrected.  Error detection and error correction are done at DLL as well as Transport Layer

Types of Error  Whenever bits flow from one point to another, they are subject to unpredictable changes because of interference. interference.  Two types of errors:  Single bit error  Burst error

Single bit error  The term single-bit error means that only 1 bit of a given data unit (such as a byte, character, or packet) is changed from 1 to 0 or from 0 to 1. changed from 1 to 0 or from 0 to 1.

Burst Error The term burst error burst error means that two or more bits in the data unit have changed from 1 to 0 or from 0 to 1. to 1. Burst errors does not necessarily mean that the errors occur in consecutive bits, the length of the burst is measured from the first corrupted bit to the last corrupted bit. Some bits in between may not have been corrupted.

 Error detection means to decide whether the received data is correct or not without having a copy of the original message. copy of the original message.  Error detection uses the concept of redundancy, which means adding extra bits for detecting errors at the destination.

structure of encoder and decoder

XORing of two single bits or two words

 In block coding, the message is divided into blocks, each of k bits, called datawords. r redundant bits are added to each block to make the length n = k + r.  The resulting n-bit blocks are called codewords.

Process of error detection in block coding 10.45

What if we want to send 01? We code it as 011. If 011 is received, no problem. What if 001 is received? Error detected. What if 000 is received? Error occurred, but not detected.

Assume dataword is 01. We then transmit 01011. What if an error occurs and we receive 01001. If we assume one bit was in error, we can correct.

 The Hamming distance between two words is the number of differences between corresponding bits.  Find Hamming distance between two pairs of words 000  Find Hamming distance between two pairs of words 000 and 011.  The Hamming distance d(000, 011) is 2 because

 Find Hamming distance d(10101, 11110)  Sol: 3 because  The minimum Hamming distance is the smallest Hamming distance between all possible pairs in a set of words.

 Find the minimum Hamming distance of the coding scheme in The dmin in this case is 2.

Hamming Distance Example  Find the minimum Hamming distance for the following coding scheme The dmin in this case is 3.

Parity Check  A parity bit is added to every data unit so that the total number of 1s(including the parity bit) becomes even for parity bit) becomes even for even-parity check or odd for odd-parity check  Simple parity check

Example 1  Suppose sender wants to send word world. In ASCII five characters are coded as  1110111 1101111 1110010 1101100 1100100  1110111 1101111 1110010 1101100 1100100  The following shows the actual bits sent  11101110 11011110 11100100 11011000 11001001

Now suppose the word world in Example 1 is received by the receiver without being corrupted in transmission.  11101110 11011110 11100100 11011000 11001001 The receiver counts the 1s in each character and comes up with even numbers (6, 6, 4, 4, 4). The data are accepted.

Now suppose the word world in Example 1 is corrupted during transmission.  11111110 11011110 11101100 11011000 11001001 The receiver counts the 1s in each character and The receiver counts the 1s in each character and comes up with even and odd numbers (7, 6, 5, 4, 4). The receiver knows that the data are corrupted, discards them, and asks for retransmission.

Linear Block Codes  Almost all block codes used today belong to a subset called linear block codes.  A linear block code is a code in which the exclusive  A linear block code is a code in which the exclusive OR (addition modulo-2) of two valid codewords creates another valid codeword.  In a linear block code, the exclusive OR (XOR) of any two valid codewords creates another valid codeword.

Simple parity-check code C(5, 4)

Encoder and decoder for simple parity-check code

transmission scenarios  Assume the sender sends the dataword 1011. The codeword created from this dataword is 10111, which is sent to the receiver. We examine five cases: 1. No error occurs; the received codeword is 10111. The syndrome  1. No error occurs; the received codeword is 10111. The syndrome is 0. The dataword 1011 is created.  2. One single-bit error changes a1 . The received codeword is 10011. The syndrome is 1. No dataword is created.  3. One single-bit error changes r0 . The received codeword is 10110. The syndrome is 1. No dataword is created.

 4. An error changes r0 and a second error changes a3 . The received codeword is 00110. The syndrome is 0. The dataword 0011 is created at the receiver. Note that here the dataword is wrongly created due to the syndrome value. wrongly created due to the syndrome value.  5. Three bits—a3, a2, and a1—are changed by errors. The received codeword is 01011. The syndrome is 1. The dataword is not created. This shows that the simple parity check, guaranteed to detect one single error, can also find any odd number of errors.

Two-dimensional parity-check code

CRC  Cyclic Redundancy check  Is an error detecting code used in data communications Invented by Wesley Peterson in 1961  Invented by Wesley Peterson in 1961  At the sender site, sender appends a code (redundant bits) to the actual data  At the receiver site, the data received is detected for any occurs. If errors found, data is discarded, else forwarded

CRC @ Sender Site  Inputs for the CRC is as follows at sender site:  Dataword (in binary)  ‘n’ (length) bits of Predetermined divisor (used at both sender and receiver) Dataword is right padded with (n-1) zeros  Dataword is right padded with (n-1) zeros  The dataword to be transmitted is divided by a predetermined divisor, using XOR  The bits padded with zeros are replaced with the reminder.  The data sent by the Sender contains: Actual data + Reminder

CRC @ Receiver  Upon receiving the data at the receiver site, following steps are involved Division is performed with received data with the  Division is performed with received data with the same predetermined divisor used at sender  Checks for the reminder; If reminder is zero, accept, else discard

CRC Example  Consider  Dataword : 1 0 0 1  Divisor : 1 0 1 1  Divisor : 1 0 1 1

CRC Example 2  Consider the dataword 11001 and the predetermined divisor 101. Answer the following:  Find the data sent from the sender site  Find the data sent from the sender site  Perform the binary division at the receiver site  If the data received at the receiver site is 100100010, What are the syndrome bits? Transmitted message: 1100110

CRC Example 3  Consider the dataword 100100 and the predetermined divisor 1101. Answer the following:  Find the data sent from the sender site  Find the data sent from the sender site  Perform the binary division at the receiver site  If the data received at the receiver site is 100100010, What are the syndrome bits?

CRC Example 4  Given :  Dataword : 10111011  Divisor : 1001  Divisor : 1001  What is the crc?  Find the data transmitted (codeword) from the sender.  Verify the codeword received at the receiver for correctness (Error Detection).

CRC : Example  Consider  Message : 1 1 0 1 0 1 1 0 1 1  Divisor : 1 0 0 1 1  Divisor : 1 0 0 1 1  Find the codeword, sent from the sender site  Verify whether the codeword received at the receiver site for correctness

CRC Polynomial  Patterns of 0s and 1s are represented as polynomial with coefficient 0 and 1. In CRC polynomial division, pairs of identical terms are deleted

CRC Polynomial : Example 1  Consider M(x) = x5+x4+x+1 P(x) = x4+x3+1 P(x) = x4+x3+1  Find C(x)  Verify the codeword received at the receiver

 Send  M(x) = 110011  x5+x4+x+1 (6 bits)  P(x) = 11001  x4+x3+1 (5 bits, n = 4)  4 bits of redundancy  Form xnM(x)  110011 0000  x9+x8+x5+x4  Divide xnM(x) by P(x) to find C(x) 11001 1100111001 11001 • Receive 100001 1001 11001 10000 11001 1100110000 11001 = C(x) 00000 11001 11001 11001 No remainder  Accept

CRC Polynomial : Example 2  Consider M(x) = x3 + x G(x) = x3 + x + 1  G(x) = x3 + x + 1  Find C(x)  Verify the codeword received at the receiver

CRC Polynomial : Example 3  Consider M(x) = x3 + x2 G(x) = x3 + x + 1  G(x) = x3 + x + 1  Find C(x)  Verify the codeword received at the receiver

CRC Polynomial : Example 1  Consider M(x) = x3 + 1 G(x) = x3 + x + 1  G(x) = x3 + x + 1  Find C(x)  Verify the codeword received at the receiver

CRC Polynomial : Example 2  Consider M(x) = x3 + x2 G(x) = x3 + x + 1  G(x) = x3 + x + 1  Find C(x)  Verify the codeword received at the receiver

Hamming distance Performance  Hamming distance: The number of digit positions in which the corresponding digits of two encodings of the same length are different. the same length are different.  Maximum number of detectable errors is dmin-1  Maximum number of correctable errors is (dmin-1)/2

dmin = 2 01 011 Accepted 01 010 Discarded 01 000 Valid codeword Dataword: 00 Error

dmin = 3 01 01011 Accepted 01 01001 Discarded 01 01000 Discarded 01 11110 Valid codeword Dataword: 11 Error

Problem Write the encoding scheme table for the simple parity check code C(5,4), where 5 indicates codeword and 4 indicates dataword. Answer the following, when the sender sends the dataword 1011, along with syndrome:  a) what is the codeword  a) what is the codeword  b) what happens when bit position at a1 is changed  c) what happens when bit position at r0 is changed  d) what happens when two bit positions ie., r0 and a3 are changed  e) what happens when three bit positions ie., a3,a2 and a1 are changed

Encoding scheme table for Simple parity-check code C(5, 4)

Solution: transmission scenarios  Assume the sender sends the dataword 1011. The codeword created from this dataword is 10111, which is sent to the receiver. We examine five cases: 1. No error occurs; the received codeword is 10111. The syndrome  1. No error occurs; the received codeword is 10111. The syndrome is 0. The dataword 1011 is created.  2. One single-bit error changes a1 . The received codeword is 10011. The syndrome is 1. No dataword is created.  3. One single-bit error changes r0 . The received codeword is 10110. The syndrome is 1. No dataword is created.

Two dimensional parity check code

Question:  Find the row parity, column parity and data sent for the following original data

Internet Checksum @ 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  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.

Internet Checksum @ Receiver site:  1. The message (including checksum) is divided into 16-bit words.  2. All words are added using one’s complement addition.  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.

Data Communication and Computer Networks

In this document

More Related Content

What's hot

Similar to Data Communication and Computer Networks

More from Sreedhar Chowdam

Recently uploaded

Data Communication and Computer Networks