Data Communication and Networking - Chapter 2: Data Communications - Vo Que Son

Nội dung text: Data Communication and Networking - Chapter 2: Data Communications - Vo Que Son

1. Data Communication and Networking Dr. –Ing. Vo Que Son Email: sonvq@hcmut.edu.vn Telecomm. Dept. DCN 1 Faculty of EEE HCMUT
2. Coding schemes  EBCDIC (Extended Binary Coded Decimal Interchange Code):  Invented by IBM  8-bit character encoding used mainly on IBM mainframe and IBM midrange computer operating systems.  ASCII (American Standards Committee for Information Interchange): defined by ITU-T  character-encoding scheme originally based on the English alphabet that encodes 128 specified characters - the numbers 0- 9, the letters a-z and A-Z, some basic punctuation symbols, some control codes that originated with Teletype machines, and a blank space - into the 7-bit binary integers.  ASCII codes represent text in computers, communications equipment, and other devices that use text. Most modern character-encoding schemes are based on ASCII, though they support many additional characters. Telecomm. Dept. DCN 3 Faculty of EEE HCMUT
3. ASCII Table  Data characters  Control characters Telecomm. Dept. DCN 5 Faculty of EEE HCMUT
4. Network Topology  Bus  Point-to point  Star  Multipoint  Ring  Mesh Telecomm. Dept. DCN 7 Faculty of EEE HCMUT
5. Transmission modes  The transmission of binary data across a link can be accomplished in either parallel or serial mode. In parallel mode, multiple bits are sent with each clock tick. In serial mode, 1 bit is sent with each clock tick. While there is only one way to send parallel data, there are three subclasses of serial transmission: asynchronous, synchronous, and isochronous. Telecomm. Dept. DCN 9 Faculty of EEE HCMUT
6. Serial transmission  Bits are transmitted over one line sequentially  Low speed over long distance  Asynchronous and Synchronous transmission Telecomm. Dept. DCN 11 Faculty of EEE HCMUT
7. Asynchronous transmission  Asynchronous here means “asynchronous at the byte level,” but the bits are still synchronized; their durations are the same.  Each character of data is treated independently Telecomm. Dept. DCN 13 Faculty of EEE HCMUT
8. Asynchronous Transmission Asynchronous Data transmitted one character at a time 5 to 8 bits Timing only needs to be maintained within each character Transmitter and Receiver clocks need not be in sync Resynchronize at the beginning of each character Behavior: In a steady stream, interval between characters is uniform • Length of stop element In idle state • Receiver looks for transition 1 to 0 Then samples next seven intervals • Char length Then looks for next 1 to 0 for next char Telecomm. Dept. DCN 15 Faculty of EEE HCMUT
9. Asynchronous Transmission  How can the receiver detect bits?  How can the receiver receive the whole byte?  How can the receiver receive the whole frame? Common synchronization techniques Bit synchronization Byte synchronization Frame synchronization Telecomm. Dept. DCN 17 Faculty of EEE HCMUT
10. Asynchronous Transmission If N is larger, the sampling is more precise Usually, N=16 Telecomm. Dept. DCN 19 Faculty of EEE HCMUT
11. Asynchronous Transmission Frame synchronization: If Blocks of printable characters Encapsulate complete block between two special (non- printable) transmission control characters • STX : Start-of-text • ETX : End-of-text Telecomm. Dept. DCN 21 Faculty of EEE HCMUT
12. Example  DTE A transmits to DTE B a sequence of characters: T S L DLE  The message is transmitted in Asynchronous mode using RS232 (8-bit data, 1 parity bit, 1 stop bit), R=1200 bps and characters are in ASCII code  Show the data frame? (If transmitting: T S L DLE ETX? What is the transmitted frame?)  Determine the time to transmit this data frame (ignoring the processing time) and the effficiency? DLE STX T S L DLE DLE DLE ETX T = (9 x 11)/1200 = 82.5 ms Telecomm. Dept. DCN 23 Faculty of EEE HCMUT
13. Synchronous Transmission Bit level: Block of data transmitted without start or stop bits Tx and Rx clocks must be synchronized!!! Option 1 Can use separate clock line Good over short distances Subject to impairments Option 2 Embed clock signal in data Manchester encoding Carrier frequency (analog) Telecomm. Dept. DCN 25 Faculty of EEE HCMUT
14. Synchronous Transmission  Bit synchronization using DPLL:  Which holds its frequency sufficiently constant to require only very small adjustment at irregular intervals.  Assuming the incoming bit stream and the local clock are in synchronism. The state (1 or 0) will be sampled at the center of each bit cell with exactly 32 clock periods between each sample.  To sync clock at receiver, the transmitted bit stream must be encoded to have enough transitions for synchronization: using line codes NRZ, Manchester, AMI, HDB3, B8ZS Telecomm. Dept. DCN 27 Faculty of EEE HCMUT
15. Synchronous Transmission  Each bit is divided into 5 segments: A, B,C,D,E. For example, a transition during segment A indicates that the last sampling pulse was too close the next transition and hence late. The time period to the next sampling pulse is shortened to 30 clock periods. Similarly, transition occurring in segment E means the previous sampling pulse was too early relative to the transition. Hence, the time period to the next pulse is lengthened to 34 clock periods.  Transition in segments B and D are clearly nearer to the assumed transition and hence the relative adjustments are less (-1 and +1). Finally, a transition in segment C is deemed to be close enough to the assumed transition to warrant no adjustment.  In practice, A=E=10, B=D=4, C=4 (clock periods). The worst case, 10 bits are needed for synchronization (5 bit periods of coarse adjustments ( 2), 5 bit periods for fine adjustments ( 1): need to transmit a number of bytes/characters for synchronization. Telecomm. Dept. DCN 29 Faculty of EEE HCMUT
16. Synchronous Transmission Character-Oriented: Used for transmission of block of characters • e.g., files of ASCII characters Character synchronization • Achieved with synchronous idle character (SYN) Frame synchronization • STX-ETX sequence preceded by SYN char • Once bit-synchronization is achieved • Receiver enters “hunt mode” • Bit stream is interpreted in windows of 8 bits Low efficiency because of using many STX, ETX, Telecomm. Dept. DCN 31 Faculty of EEE HCMUT
17. Synchronous Transmission  Bit-Oriented: Used for transmission of binary data • Preferred control scheme Point-to-point links • Uses a flag pattern for start and end of frame – Idle bytes: 01111111 (0x7F) – Flag pattern: 01111110 (0x7E) • Bit stuffing (or zero bit insertion) – Inserts a “0” after five consecutive 1s • LANs use a similar scheme • More efficient (lower overhead) than asynchronous transmission Telecomm. Dept. DCN 33 Faculty of EEE HCMUT
18. Channel Coding  Channel coding is a technique used for controlling errors in data transmission over unreliable or noisy communication channels. The central idea is the sender encodes their message in a redundant way by using an error-correcting code (ECC).  The redundancy allows the receiver to detect a limited number of errors that may occur anywhere in the message, and often to correct these errors without retransmission. Telecomm. Dept. DCN 35 Faculty of EEE HCMUT
19. Error control coding  Types of Errors  Single Bit Errors: • only one bit in a given data unit (byte, packet, etc.) gets corrupted  Burst Errors • two or more bits in the data unit have been corrupted errors do not have to occur in consecutive bits • burst errors are typically caused by external noise (environmental noise) • burst errors are more difficult to detect / correct Telecomm. Dept. DCN 37 Faculty of EEE HCMUT
20. Example: Detect Error On Credit Card n = 3 d1 d2 d3 d15 d16 Telecomm. Dept. DCN 39 Faculty of EEE HCMUT
21. Example: Detect Error On Credit Card  The test performed on the credit card number is called a parity check equation. The last digit is a function of the other digits in the credit card. This is how credit card numbers are generated by Visa and Master Card. They start with an account number that is 15 digits long and use the parity check equation to find the value of the 16th digit.  “This method allows computers to detect 100% of single- position errors and about 98% of other common errors”  Other examples:  ISBN (international standard book number) • 0 – 20 – 1 – 36186 – 8  UPC (universal product codes): 12-digit sequence • 0 16000 66610 8 Telecomm. Dept. DCN 41 Faculty of EEE HCMUT
22. Parity Check Encoder and decoder for single parity check code  Info Bits: b1, b2, b3, ,  Check Bit: bk+1= b1+ b2+ b3+ + bk  Codeword: [b1, b2, b3, , bk+1]  Receiver CAN DETECT all single-bit errors& burst errors with odd number of corrupted bits  Single-bit errors CANNOT be CORRECTED: position of corrupted bit remains unknown  All even-number burst errors are undetectable  What is the error detection probability? (50%?) Telecomm. Dept. DCN 43 Faculty of EEE HCMUT
23. Parity Check: Example Single Even parity check Information (7 bits): [b1 b7]= [0, 1, 0, 1, 1, 0, 0] Parity Bit: b8= (0 + 1 + 0 + 1 +1 + 0) mod 2 = 1 Codeword (8 bits): [0, 1, 0, 1, 1, 0, 0, 1] If single error in bit 3 : [0, 1, 1, 1, 1, 0, 0, 1] # of 1’s = 5, odd: Error detected ☺ If errors in bits 3 and 5: [0, 1, 1, 1, 0, 0, 0, 1] # of 1’s = 4, even: Error not detected If errors in bit 3, 5, 6 : [0, 1, 1, 1, 0, 1, 0, 1] # of 1’s = 5, odd: Error detected ☺ Telecomm. Dept. DCN 45 Faculty of EEE HCMUT
24. Example Telecomm. Dept. DCN 47 Faculty of EEE HCMUT
25. Cyclic Redundant Check  Cyclic codes are special linear block codes with one extra property. In a cyclic code, if a codeword is cyclically shifted (rotated), the result is another codeword.  Useful to detect error bursts  Process Steps:  For a block of k bits (message), transmitter generates an (n – k) bit sequence. Known as the Frame Check Sequence (FCS)  Transmit n bits which is exactly divisible by some number/generator  Receiver divides frame by that number/generator  If no remainder, assume no error  Definition:  T(x) : the transmitted codeword has n bits  M(x) : the dataword to be transmitted has k bits  G(x) : the divisor or generator has n-k+1 bits  R(x) : remainder has n-k bit  Q(x) : quotient Telecomm. Dept. DCN 49 Faculty of EEE HCMUT
26. CRC procedure  Receiver: assuming that the error polynomial of the transmission channel is E(x) with the same size of the transmitted polynomial T(x). The receiver will get: System A System B Y(x) = T(x) + E(x)  Receiver perform: T(x) E(x) Y(x) Y xx T(x)+0 .M x +Rn-kn-k x x M x R xR x R x ===+ =Q x ++ =Q x G(x) G(x)G xG x G xG x G x =0  In case there is no error: there is no remainder in the above division or the receiver can not detect errors. Otherwise, there is errors Telecomm. Dept. DCN 51 Faculty of EEE HCMUT
27. Division in CRC encoder Telecomm. Dept. DCN 53 Faculty of EEE HCMUT
28. A CRC code with C(7, 4) Telecomm. Dept. DCN 55 Faculty of EEE HCMUT
29. CRC  General design of encoder and decoder of a CRC code Telecomm. Dept. DCN 57 Faculty of EEE HCMUT
30. Standard polynomials Telecomm. Dept. DCN 59 Faculty of EEE HCMUT
31. Data Compression  Data compression implies sending or storing a smaller number of bits.  Benefits Reduce storage needed Reduce transmission cost / latency / bandwidth  Although many methods are used for this purpose, in general these methods can be divided into two broad categories: lossless and lossy methods.  Lossless • Preserves all information • Exploits redundancy in data • Applied to general data  Lossy • May lose some information • Exploits redundancy & human perception • Applied to audio, image, video Telecomm. Dept. DCN 61 Faculty of EEE HCMUT
32. Data Compression  Packed Decimal: A packed decimal representation stores two decimal digits in one byte. For example, the value 23 would be stored in two nibbles, using the hexadecimal digits 2 and 3 (the bit representation would be 0010 0011).  Relative coding: instead of transmitting the whole number value, the transmitter only transmits the difference between values.  Character Suppression: when transmitting the same continuous printable characters, all the same continuous characters will be encoded with a representative character and the number of this character. Example: AAAAABBBBCC = A5B4C2 Telecomm. Dept. DCN 63 Faculty of EEE HCMUT
33. Huffman code  Huffman coding is statistical coding technique  Approach  Variable length encoding of symbols  Exploit statistical frequency of symbols  Efficient when symbol probabilities vary widely  Principle  Use fewer bits to represent frequent symbols  Use more bits to represent infrequent symbols A A B A A A B A Telecomm. Dept. DCN 65 Faculty of EEE HCMUT
34. Huffman coding principle Encoding Calculate frequency of symbols Create binary tree representing “best” encoding Use binary tree to encode symbols • For each symbol, output path from root to leaf • Size of encoding = length of path Save binary tree Symbol Stage 1 Stage 2 Stage 3 Stage 4 Codeword S0 0.4 0.4 0.4 0.6 0 00 1 S1 0.2 0.2 0.4 0 0.4 10 S2 0.2 0.2 0 0.2 1 11 S3 0.1 0 0.2 1 010 1 S4 0.1 011 Telecomm. Dept. DCN 67 Faculty of EEE HCMUT
35. Performance Evaluation  Entropy: H=pi log2 (1/pi) (bits/symbol)  Average length of codewords: N =  piNi (bits/symbol)  Variance: measure what? 2 2  =pi .(Ni-N)  Efficiency of codeword set: h = H/N  Bit rate (after encoding): Rb= RS.N (bps), RS is the symbol rate (symbol/s) Telecomm. Dept. DCN 69 Faculty of EEE HCMUT
36. Run-Length coding  Run-length encoding is probably the simplest method of compression. It can be used to compress data made of any combination of symbols. It does not need to know the frequency of occurrence of symbols and can be very efficient if data is represented as 0s and 1s.  The general idea behind this method is to replace consecutive repeating occurrences of a symbol by one occurrence of the symbol followed by the number of occurrences.  The method can be even more efficient if the data uses only two symbols (for example 0 and 1) in its bit pattern and one symbol is more frequent than the other. Telecomm. Dept. DCN 71 Faculty of EEE HCMUT
37. Run-Length coding  Each line in a page will have a number of black/white pixel continuous sequence  Each continuous bit sequence is encoded by  Termination code: in the range 0 63 switches between black and white code  Makeup code: can extend length of a run by a multiple of 64  EOL is inserted at the end of each line (EOL=00000000001)  End of each page will be ended with 6 EOL Telecomm. Dept. DCN 73 Faculty of EEE HCMUT
38. Lempel Ziv encoding  Lempel Ziv (LZ) encoding is an example of a category of algorithms called dictionary-based encoding. The idea is to create a dictionary (a table) of strings used during the communication session. If both the sender and the receiver have a copy of the dictionary, then previously-encountered strings can be substituted by their index in the dictionary to reduce the amount of information transmitted. Telecomm. Dept. DCN 75 Faculty of EEE HCMUT