William Stallings Data And Computer Communications
William StallingsData and ComputerCommunicationsChapter 6Digital Data CommunicationsTechniques1
Digital Data CommunicationsTechniquesSynchronizationDr. Mohammed ArafahWilliam Stallings “Data and Computer Communications”2
Standard Interchange CodesAmerican Standards Committee for Information Interchange (ASCII):BitPositions40000000011111111Dr. Mohammed NEMSUBESCFSGSRSUSSP!“# %&’()* ,./0123456789:; ?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\] \abcdefghijklmnopqrstuvwxyz{ } DELWilliam Stallings “Data and Computer Communications”3
Standard Interchange CodesAmerican Standards Committee for Information Interchange (ASCII):BitPositions40000000011111111Dr. Mohammed NEMSUBESCFSGSRSUSSP!“# %&’()* ,./0123456789:; ?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\] \abcdefghijklmnopqrstuvwxyz{ } DELWilliam Stallings “Data and Computer Communications”4
Standard Interchange CodesExtended Binary Coded Decimal Interchange Code 0110011001100110101010101010101BitPositionsDr. Mohammed NLBSILCANEMSMM CCVTFF IFSCR IGSSO IRSSI IUS001000110100DSSPSOSFS SYNBYPLFEOBPRE01010110&/0111PNRSUCEOTSMDC4ENQ NAKACKBEL SUB . ( ! *); ’% ?10001001abcdefghijklmnopqr:#@, ”William Stallings “Data and Computer JKLMNOPQN11101111STUVWXYZ0123456789 5
Standard Interchange CodesExtended Binary Coded Decimal Interchange Code 0110011001100110101010101010101BitPositionsDr. Mohammed NLBSILCANEMSMM CCVTFF IFSCR IGSSO IRSSI IUS001000110100DSSPSOSFS SYNBYPLFEOBPRE01010110&/0111PNRSUCEOTSMDC4ENQ NAKACKBEL SUB . ( ! *); ’% ?10001001abcdefghijklmnopqr:#@, ”William Stallings “Data and Computer JKLMNOPQN11101111STUVWXYZ0123456789 6
Synchronization To correctly interpret the signals received, thereceiver’s bit intervals must correspondexactly to the sender’s bit intervals (thesame clock rate). timing problems require a mechanism tosynchronize the transmitter and receiver if clocks not aligned and drifting will sample atwrong time after sufficient bits are sentDr. Mohammed ArafahWilliam Stallings “Data and Computer Communications”7
Lack of Synchronization Example: Faster receiver clockDr. Mohammed ArafahWilliam Stallings “Data and Computer Communications”8
Synchronization Two solutions to synchronizing clocks Asynchronous transmission Synchronous transmissionDr. Mohammed ArafahWilliam Stallings “Data and Computer Communications”9
Transmission ModesTransmission ModeSynchronous r-OrientedPrintable- CharacterFrameBinary Data FrameDr. Mohammed ArafahAsynchronous TransmissionCharacterBitFrameSynchronization Synchronization intable- CharacterFrameBinary Data FrameDifferentialManchesterEncodingWilliam Stallings “Data and Computer Communications”10
Asynchronous Transmission In asynchronous transmission, the receiver clock (R C) runsunsynchronized with respect to the incoming signal (R D). Each character (byte) is encapsulated between an additionalstart bit and one or more stop bits. The state of the signal on the transmission line betweencharacters is idle state.Dr. Mohammed ArafahWilliam Stallings “Data and Computer Communications”11
Asynchronous Transmission send one character (e.g. 8 bits) at a time no data: idle state (usually negative volt) start bit (usually zero) data: usually use NRZ-L party bit can be added for error control stop bit, 1-2 bit time, same as idle timing requirement is modest (within 1 char)Dr. Mohammed ArafahWilliam Stallings “Data and Computer Communications”12
Asynchronous Transmission Parity parity bit set so character has even (even parity) or odd (oddparity) number of ones Error Detection010101 11010 101 10111110 00111110 0100000010000000Dr. Mohammed Arafah0William Stallings “Data and Computer Communications”013
Asynchronous Transmission(NRZ-L)(NRZ-L)Dr. Mohammed ArafahWilliam Stallings “Data and Computer Communications”14
Asynchronous TransmissionExample50 0.94650 0.94850 0.94 Data rate 10 kbps, bit time 0.1 ms 100 μs Receiver is faster by 6% of bit time 6 μs Receiver samples bit every 94 μs Last bit is in errorDr. Mohammed ArafahWilliam Stallings “Data and Computer Communications”15
Asynchronous Transmission In previous example, actually two errors last bit is incorrect When a valid stop bit is not detected at end ofeach character (i.e., it is supposed to be logic 1and found logic 0) Framing ErrorDr. Mohammed ArafahWilliam Stallings “Data and Computer Communications”16
Asynchronous Transmission Advantage simple and cheap Disadvantage requires overhead 2 to 4 bits / character for 8 bit char, no parity, 1 stop bit, 20% overheadDr. Mohammed ArafahWilliam Stallings “Data and Computer Communications”17
Asynchronous Transmission –Example 1Construct the transmitted frame using asynchronous transmissionmode which contains the following data: GO. Assume that thenumber of bits per character is 8, the number of stop bits is 2, andparity bit is used.STXPGPOPETXPEfficiency ( ) 8/(1 8 1 2) 8/12 66.67%Dr. Mohammed ArafahWilliam Stallings “Data and Computer Communications”18
Asynchronous Transmission –Example 1Construct the transmitted frame using asynchronous transmissionmode which contains the following data: GO. Assume that thenumber of bits per character is 8, the number of stop bits is 2, andodd parity bit is used.Hints:1. No need to include framing characters such as STX and ETX2. G 1100 0111, O 1101 0110, STX 1101 0110 , ETX 1101 01103. The least significant bit (lsb) is transmitted first1 1 1 0 0 0 1 10 1 1 0 1 0 1 1Efficiency ( ) 8/(1 8 1 2) 8/12 66.67%Dr. Mohammed ArafahWilliam Stallings “Data and Computer Communications”19
Asynchronous Transmission –Example 2Construct the transmitted frame using asynchronous transmissionmode which contains the following data: YES. Assume that thenumber of bits per character is 7, the number of stop bits is 1 and noparity bit is used.STXYESETXEfficiency ( ) 7/(1 7 1) 7/9 77.78%Dr. Mohammed ArafahWilliam Stallings “Data and Computer Communications”20
Asynchronous Transmission –Example 2Construct the transmitted frame using asynchronous transmissionmode which contains the following data: YES. Assume that thenumber of bits per character is 7, the number of stop bits is 1 and noparity bit is used.Hints:1. No need to include framing characters such as STX and ETX2. Y 101 1001, E 100 0101, S 101 00113. The least significant bit (lsb) is transmitted first1 0 0 1 1 0 11 0 1 0 0 0 11 1 0 0 1 0 1Efficiency ( ) 7/(1 7 1) 7/9 77.78%Dr. Mohammed ArafahWilliam Stallings “Data and Computer Communications”21
Asynchronous TransmissionDr. Mohammed ArafahWilliam Stallings “Data and Computer Communications”22
Asynchronous TransmissionDr. Mohammed ArafahWilliam Stallings “Data and Computer Communications”23
Asynchronous TransmissionBit Synchronization using Asynchronous Transmission: The local receiver clock is N times the transmitted bit rate (N 16is common). The first 1 0 transition is associated with the start bit. Each bit is sampled at the center to avoid delay distortionproblem. After the first transition is detected, the signal is sampledafter N/2 clock cycles and then subsequently after N clockcycles for each bit in the character.Dr. Mohammed ArafahWilliam Stallings “Data and Computer Communications”24
Asynchronous TransmissionN 4Dr. Mohammed ArafahWilliam Stallings “Data and Computer Communications”25
Asynchronous TransmissionN 16Dr. Mohammed ArafahWilliam Stallings “Data and Computer Communications”26
Asynchronous TransmissionDr. Mohammed ArafahWilliam Stallings “Data and Computer Communications”27
Asynchronous TransmissionCharacter Synchronization using Asynchronous Transmission:After the start bit is detected, the receiver achieves charactersynchronization simply by counting the programmed numberof bits.Dr. Mohammed ArafahWilliam Stallings “Data and Computer Communications”28
Asynchronous TransmissionFrame Synchronization using Asynchronous Transmission: Frame synchronization is used to determine the start and end offrame. 1. Printable Characters Encapsulate the complete block between two non-printablecharacters: STX (start-of-text) and ETX (end-of-text). 2. Binary DataStart of framesequenceDr. Mohammed ArafahInsertedDLEWilliam Stallings “Data and Computer Communications”End of framesequence29
Asynchronous Transmission ExampleConstruct the transmitted frame using asynchronous transmission mode whichcontains the following binary data: DLE DLE DLE ETX ETX ETX.Assume that the number of stop bits is 1 and no parity bit is used.DLESTXStart of DLEETXETXDLEInsertedDLEDLEETXEnd of framesequenceDr. Mohammed ArafahWilliam Stallings “Data and Computer Communications”30
Synchronous Transmission block of data transmitted sent as a frame No start or stop bits clocks must be synchronized can use separate clock line or embed clock signal in data need to indicate start and end of block use preamble and postamble more efficient (lower overhead) than asyncDr. Mohammed ArafahWilliam Stallings “Data and Computer Communications”31
Synchronous TransmissionClock Encoding and Extraction:Dr. Mohammed ArafahWilliam Stallings “Data and Computer Communications”32
Synchronous TransmissionClock Encoding and Extraction:Dr. Mohammed ArafahWilliam Stallings “Data and Computer Communications”33
Synchronous TransmissionCharacter-Oriented Synchronous Transmission: The SYN character enables the receiver to achieve charactersynchronization before the STX character. Once the receiver has obtained bit synchronization, it entersHunt Mode. When the receiver enters hunt mode, it starts to interpret thereceived bit stream in a window of 8 bits as each new bit isreceived. It checks whether the last eight bits were equal toSYN character. If they are not, it receives the next bit andrepeats the check. If they are, then the correct characterboundary is found and hence the following characters are thenread after each subsequent eight bits have been received.Dr. Mohammed ArafahWilliam Stallings “Data and Computer Communications”34
Synchronous TransmissionCharacter-Oriented Synchronous Transmission:Dr. Mohammed ArafahWilliam Stallings “Data and Computer Communications”35
Synchronous TransmissionCharacter-Oriented Synchronous Transmission:1. Printable characters:2. Binary data:Dr. Mohammed ArafahWilliam Stallings “Data and Computer Communications”36
Digital Data CommunicationsTechniquesError Detection & CorrectionDr. Mohammed ArafahWilliam Stallings “Data and Computer Communications”37
Types of Error an error occurs when a bit is altered betweentransmission and reception Single bit errors only one bit altered caused by white noise Burst errors contiguous sequence of B bits in which first and last andany number of intermediate bits in error caused by impulse noise or by fading in wireless effect greater at higher data ratesDr. Mohammed ArafahWilliam Stallings “Data and Computer Communications”38
Error DetectionError DetectionDr. Mohammed ArafahWilliam Stallings “Data and Computer Communications”39
Error Detection Error detecting code added by transmitter k data bits (n–k) check bits n-bit frame Receiver separates k, n–k bits Receiver calculates error-detecting code match received code: assume no error mismatch: error Some errors will be undetectedDr. Mohammed ArafahWilliam Stallings “Data and Computer Communications”40
Error Detection ProcessDr. Mohammed ArafahWilliam Stallings “Data and Computer Communications”41
Error Detection Parity parity bit set so character has even (even parity) or odd (oddparity) number of ones even number of bit errors goes undetected1 11010101 101 11 0 0011111001001000 0 00 000101100Dr. Mohammed Arafah10000William Stallings “Data and Computer Communications”42
Cyclic Redundancy Check one of most common and powerful checks for block of k bits transmitter generates an n bitframe check sequence (FCS) transmits k n bits which is exactly divisibleby some number receiver divides frame by that number if no remainder, assume no errorDr. Mohammed ArafahWilliam Stallings “Data and Computer Communications”43
Cyclic Redundancy CheckExample 1An 8-bit message 1 1 0 1 0 1 1 0 is tobe transmitted across a data linkusing CRC for error detection.1 0 0 1 0 1 0 11 1 0 0 11 1 0 1 0 1 1 0 0 0 0 01 1 0 0 1- 0 0 1 10 0 0 0- 0 1 10 0 0A generator polynomial x4 x3 1 isto be used. Find the contents of thetransmitted frame T(x).101 10 0- 1 1 1 1 01 1 0 0 1- 0 1 1 1 00 0 0 0 0- 1 1 1 01 1 0 0- 0 1 00 0 0- 1 01 1- 10110101000 00 10 1R(x)T(x) 1 1 0 1 0 1 1 0 1 1 0 1M(x)Dr. Mohammed ArafahR(x)William Stallings “Data and Computer Communications”44
Cyclic Redundancy CheckExample 1 – Circuit ImplementationGenerator Polynomial x4 x3 1Presence of X3Dr. Mohammed ArafahAbsence of X2Absence of XWilliam Stallings “Data and Computer Communications”45
Cyclic Redundancy CheckExample 21 0 1 1 0 0 0 1An 8-bit message 1 0 0 1 0 0 1 1 is tobe transmitted across a data link usingCRC for error detection.1 0 1 0 1 11 0 0 1 0 0 1 1 0 0 0 0 01 0 1 0 1 1- 0 1 1 10 0 0 0- 1 1 11 0 1A generator polynomial x5 x3 x 1is to be used. Find the contents of thetransmitted frame T(x).1010101 11 1- 1 0 1 0 0 01 0 1 0 1 1- 0 0 0 1 1 00 0 0 0 0 0- 0 0 1 1 0 00 0 0 0 0 0- 0 1 1 0 00 0 0 0 0- 1 1 0 01 0 1 0000 01 1- 1 1 0 1 1R(x)T(x) 1 0 0 1 0 0 1 1 1 1 0 1 1M(x)Dr. Mohammed ArafahR(x)William Stallings “Data and Computer Communications”46
Cyclic Redundancy CheckExample 2 – Circuit ImplementationGenerator Polynomial x5 x3 x 1Absence of X4Dr. Mohammed ArafahPresence of X3Absence of X2Presence of XWilliam Stallings “Data and Computer Communications”47
Cyclic Redundancy CheckExample 31 1 1 0 0 1 0 0Assume that the following frame:111101101100is received across a data link usingCRC for error detection. A generatorpolynomial x4 x 1 is to be used.Check whether the received frame iscorrect or incorrect. If the frame iscorrect, then deduce the originalmessage.1 0 0 1 11 1 1 1 0 1 1 0 1 1 0 01 0 0 1 1- 1 1 0 11 0 0 1- 1 0 01 0 0- 0 00 0110110110 00 0- 0 1 0 0 10 0 0 0 0- 1 0 0 11 0 0 1- 0 0 00 0 0- 0 00 0- 01100000000 00 00 0R(x)R(x) 0 The Message is correct M(x) 1 1 1 1 0 1 1 0Dr. Mohammed ArafahWilliam Stallings “Data and Computer Communications”48
Cyclic Redundancy CheckExample 3 – Circuit ImplementationGenerator Polynomial x4 x 1Absence of X3 Absence of X2Dr. Mohammed ArafahPresence of XWilliam Stallings “Data and Computer Communications”49
Cyclic Redundancy CheckExample 4Assume that the following frame:1001100010111is received across a data link usingCRC for error detection. A generatorpolynomial x5 x2 1 is to be used.Check whether the received frame iscorrect or incorrect. If the frame iscorrect, then deduce the original1 0 0 0 1 1 0 11 0 0 1 0 11 0 0 1 1 0 0 0 1 0 1 1 11 0 0 1 0 1- 0 0 0 10 0 0 0- 0 0 10 0 01010000 00 0- 0 1 1 0 0 10 0 0 0 0 0- 1 1 0 0 1 01 0 0 1 0 1message.- 1 0 1 1 1 11 0 0 1 0 1- 0 1 0 1 0 10 0 0 0 0 0- 1 0 1 0 1 11 0 0 1 0 1- 0 1 1 1 0R(x)R(x) 0 Error is detected. The message is discarded.Dr. Mohammed ArafahWilliam Stallings “Data and Computer Communications”50
Cyclic Redundancy CheckExample 4 – Circuit ImplementationGenerator Polynomial x5 x2 1Absence of X4 Absence of X3Dr. Mohammed ArafahPresence of X2Absence of XWilliam Stallings “Data and Computer Communications”51
Cyclic Redundancy Check Four versions of Polynomial Division P(X) are widely used: CRC-12 X12 X11 X3 X2 X 1 CRC-16 X16 X15 X2 1 CRC-CCITT X16 X12 X5 1 CRC-32 X32 X26 X23 X22 X16 X12 X11 X10 X8 X7 X5 X4 X2 X 1 CRC-32 is used in IEEE 802 LAN standards.Dr. Mohammed ArafahWilliam Stallings “Data and Computer Communications”52
Cyclic Redundancy CheckImplementation The CRC process can be represented by, and indeed implemented as, adividing circuit consisting of XOR gates and a shift register. The shift register is a string of 1-bit storage devices. Each device has anoutput line, which indicates the value currently stored, and an input line. At discrete time instants, known as clock times, the value in the storagedevice is replaced by the value indicated by its input line. The entire register is clocked simultaneously, causing a 1-bit shift alongthe entire register. The circuit is implemented as follows:1. The register contains n-k bits, equal to the length of the FCS.2. There are up to n-k XOR gates.3. The presence or absence of a gate corresponds to the presence orabsence of a term in the divisor polynomial, P(X), excluding theterms 1 and Xn-k.Dr. Mohammed ArafahWilliam Stallings “Data and Computer Communications”53
Cyclic Redundancy CheckImplementationDr. Mohammed ArafahWilliam Stallings “Data and Computer Communications”54
Circuit with Shift Registers for Dividingby the Polynomial X5 X4 X2 1Presence of X4Dr. Mohammed ArafahAbsence of X3Presence of X2William Stallings “Data and Computer Communications”Absence of X55
Circuit with Shift Registers for Dividingby the Polynomial X5 X4 X2 11 0 1 1 0 0 0 1An 10-bit message 1 0 1 0 0 0 1 1 0 1 isto be transmitted across a data linkusing CRC for error detection.1 1 0 1 0 11 0 1 0 0 0 1 1 0 1 0 0 0 0 01 1 0 1 0 1- 1 1 1 01 1 0 1- 0 1 10 0 0A generator polynomial x5 x4 x2 1is to be used.1010110 10 0- 1 1 1 0 1 01 1 0 1 0 1- 0 1 1 1 1 10 0 0 0 0 0n bitsk bitsn-k bitsT(x) 1 0 1 0 0 0 1 1 0 1 0 1 1 1 0- 1 1 1 1 1 01 1 0 1 0 1- 0 1 0 1 10 0 0 0 0- 1 0 1 11 1 0 1- 1 1 01 1 0- 0 00 000000110011010011 00 0R(x)- 0 1 1 1 0M(x)Dr. Mohammed ArafahR(x)William Stallings “Data and Computer Communications”56
Circuit with Shift Registers for Dividingby the Polynomial X5 X4 X2 1An 10-bit message 1 0 1 0 0 0 1 1 0 1 isto be transmitted across a data linkusing CRC for error detection.1 0 1 1 0 0 0 11 1 0 1 0 11 0 1 0 0 0 1 1 0 1 0 0 0 0 01 1 0 1 0 1- 1 1 11 1 0- 11A generator polynomial x5 x4 x2 1is to be used.01111010110 1 01 0 1- 1 1 1 1 1 01 1 0 1 0 1- 1 0 1 11 1 0 1- 1 1 01 1 00001011 00 1R(x)- 0 1 1 1 0n bitsk bitsn-k bitsT(x) 1 0 1 0 0 0 1 1 0 1 0 1 1 1 0M(x)Dr. Mohammed ArafahWilliam Stallings “Data and Computer Communications”R(x)57
Cyclic Redundancy CheckGeneral ImplementationDr. Mohammed ArafahWilliam Stallings “Data and Computer Communications”58
Cyclic Redundancy CheckGeneral Implementation - ExampleGenerator Polynomial x5 x4 x2 1Dr. Mohammed ArafahWilliam Stallings “Data and Computer Communications”59
Error CorrectionError CorrectionDr. Mohammed ArafahWilliam Stallings “Data and Computer Communications”60
Error Correction Error detection is not always sufficient wireless links have many errors satellite links have long propagation delay in both cases, retransmissions are expensive Error-correcting codes add redundant bits to transmitted message also known as forward error correction (FEC)Dr. Mohammed ArafahWilliam Stallings “Data and Computer Communications”61
Error Correction ProcessDr. Mohammed ArafahWilliam Stallings “Data and Computer Communications”62
Error Correction – FEC Decoder This block is passed through an FEC decoder, with one of fourpossible outcomes: 1. If there are no bit errors, the input to the FEC decoder isidentical to the original codeword, and the decoder produces theoriginal data block as output. 2. For certain error patterns, it is possible for the decoder to detectand correct those errors. Thus, even though the incoming datablock differs from the transmitted codeword, the FEC decoder is ableto map this block into the original data block. 3. For certain error patterns, the decoder can detect but notcorrect the errors. In this case, the decode simply reports anuncorrectable error. 4. For certain, typically rare, error patterns, the decoder does notdetect that any errors have occurred and maps the incoming n-bitdata block into a k-bit block that differs from the original k-bit block.Dr. Mohammed ArafahWilliam Stallings “Data and Computer Communications”63
How Error Correction Works adds redundancy to transmitted message can deduce original despite some errors eg. block error correction code map k bit input onto an n bit codeword each distinctly different if get error assume codeword sent was closestto that received means have reduced effective data rateDr. Mohammed ArafahWilliam Stallings “Data and Computer Communications”64
Codewordsn bits total: k data bits, (n–k) redundant bits2n possible codewords2k valid codewords represent dataThe ratio of redundant bits to data bits, (n-k)/k is called theredundancy of the code The ratio of data bits to total bits, k/n , is called the code rate. The code rate is a measure of how much additional bandwidth isrequired to carry data at the same data rate as without the code. For example, a code rate of 2/5 requires 2.5 times thecapacity of an uncoded system. For example, if the data rateinput to the encoder is 1 Mbps, then the output from theencoder must be at a rate of 2.5 Mbps to keep up. Dr. Mohammed ArafahWilliam Stallings “Data and Computer Communications”65
CodewordsExample:d 1d 2d 4d 3Dr. Mohammed ArafahWilliam Stallings “Data and Computer Communications”66
CodewordsExample:Dr. Mohammed ArafahWilliam Stallings “Data and Computer Communications”67
CodewordsExample:Dr. Mohammed ArafahWilliam Stallings “Data and Computer Communications”68
Hamming Distance Number of different bits between two codewords Calculated using bitwise XOR, counting 1s Example v1 011011,v2 110001 v1 v2 101010, d(v1, v2) 3 Minimum distance for code consisting of w1, w2, , ws, s 2n dmin min i j [d(wi, wj)]Dr. Mohammed ArafahWilliam Stallings “Data and Computer Communications”69
Hamming Distance Maximum number of errors (t) that can be detected satisfies:t d min 1 t single bit errors will not produce a valid codeword Maximum number of guaranteed correctable errors percodeword satisfies: d 1 t min 2 with t single bit errors, resulting codeword is still closer to one ofthe valid codewordsDr. Mohammed ArafahWilliam Stallings “Data and Computer Communications”70
Hamming Distance - Example Maximum number of errors (t) that can be detected satisfies:t d min 1dmin 7ValidCode12t 13t 24t 35t 46t 5ValidCode7t 6t 6 Generated codewords will be invalid since dmin 7 Maximum number of guaranteed correctable errors per codeword satisfies: d 1 t min 2 dmin 7ValidCode1t 12t 234567ValidCodet 3t 3 Assume codeword sent was closest to that receivedDr. Mohammed ArafahWilliam Stallings “Data and Computer Communications”71
Hamming Distance - Example Maximum number of errors (t) that can be detected satisfies:t d min 1dmin 8ValidCode12t 13t 24t 35t 46t 57t 6ValidCode8t 7t 7 Generated codewords will be invalid since dmin 8 Maximum number of guaranteed correctable errors per codeword satisfies:dmin 8ValidCode1t 12t 23456 d 1 t min 2 78ValidCodet 3t 3 Assume codeword sent was closest to that receivedDr. Mohammed ArafahWilliam Stallings “Data and Computer Communications”72
Hamming Distance The design of a block code involves a number of considerations:1. For given values of n and k, we would like the largest possiblevalue of dmin.2. The code should be relatively easy to encode and decode, requiringminimal memory and processing time.3. We would like the number of extra bits, (n - k), to be small, toreduce bandwidth.4. We would like the number of extra bits , (n - k), to be large, toreduce error rate.Clearly, the last two objectives are in conflict, and tradeoffs must bemade.Dr. Mohammed ArafahWilliam Stallings “Data and Computer Communications”73
Hamming Distance - Example 1 Valid codewords:000000, 000111, 111000, 111111 Hamming distance 3t d min 1 Can detect up to 2 errors 000011, 000110, 100100, 100001 001111, 000110, 110111, 101111Discard 110011, 011110, 101101, 111100Dr. Mohammed ArafahWilliam Stallings “Data and Computer Communications”74
Hamming Distance - Example 2 Valid codewords:0000000000, 0000011111, 1111100000, 1111111111 Hamming distance 5 d 1 t min 2 Can correct up to 2 errors 0000000011, 0000000101 0000000000 0000000111, 0001111111 0000011111Dr. Mohammed ArafahWilliam Stallings “Data and Computer Communications”75
Single Error CorrectionHamming Code It is a code with m message bit and r parity bits that will allow allsingle errorsto be corrected.Transmitter: The bits of a codeword are numbered consecutively, starting withbit 1 at the left end. The bits that are powers of 2 (1, 2, 4, 8, 16, etc.) are parity bits.The rest (3, 5, 6, 7, 9, etc.) are filled up the m data bits. The parity bits are calculated such that we make (c1 c2 c4 0)according to the following equations:c1 p1 m3 m5 m7 m9 m11 .c2 p2 m3 m6 m7 m9 m10 .c4 p4 m5 m6 m7 m12 m13 .c8 p8 m9 m10 m11 m12 m13 .Dr. Mohammed ArafahWilliam Stallings “Data and Computer Communications”76
Single Error CorrectionHamming CodeReceiver: The receiver calculates the check bits (c1, c2, c4, c8, etc.) using thesame previous equations.c1 p1 m3 m5 m7 m9 m11 .c2 p2 m3 m6 m7 m9 m10 .c4 p4 m5 m6 m7 m12 m13 .c8 p8 m9 m10 m11 m12 m13 . If (c1 c2 c4 c8 0), then the codeword is received correctly.Otherwise, the values of the check bits are used to determine thelocation of the error in the codeword.Dr. Mohammed ArafahWilliam Stallings “Data and Computer Communications”77
Single Error CorrectionHamming Code – Example 1:Solution of Example 1:Assuming that the transmittedcharacter 'C', generate theHamming codeword.C1 P1 m3 m5 m7 m9 m11'C' 11000011P1P2?m3 P41?m51m6 m700P8?m9 m10 m11 m1200110001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 C1 ? 1 1 0 0 1C1 0 P1 1C2 P2 m3 m6 m7 m10 m11 C2 ? 1 0 0 0 1C2 0 P2 0C4 P4 m5 m6 m7 m12 C4 ? 1 0 0 1C4 0 P4 0C8 P8 m9 m10 m11 m12 C8 ? 0 0 1 1C8 0 P8 0 The transmitted Hamming codeword is:1Dr. Mohammed Arafah0101William Stallings “Data and Computer Communications”000001178
Single Error CorrectionHamming Code – Example 2:Solution of Example 2:Assuming that the transmittedcharacter 'M', generate theHamming codeword.C1 P1 m3 m5 m7 m9 m11'M' 11010100P1P2?m3 P40?m50m6 m710P8?m9 m10 m11 m1210110001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 C1 ? 0 0 0 1 1C1 0 P1 0C2 P2 m3 m6 m7 m10 m11 C2 ? 0 1 0 0 1C2 0 P2 0C4 P4 m5 m6 m7 m12 C4 ? 0 1 0 1C4 0 P4 0C8 P8 m9 m10 m11 m12 C8 ? 1 0 1 1C8 0 P8 1 The transmitted Hamming codeword is:0Dr. Mohammed Arafah0000William Stallings “Data and Computer Communications”101101179
Single Error CorrectionHamming Code – Example 3:The received Hamming codeword is:P1P210m3 P41m500m6 m701P81m9 m10 m11 m1201110001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100Deduce the correct character fromthe above codeword after correctionany error, if any.Conclusion: The codeword is correct The codeword is 1 0 1 0 0 0 1 1 0 1 1 1 The message is 1 1 1 0 1 0 0 1 The EBCDIC character is ZDr. Mohammed ArafahSolution of Example 3:C1 P1 m3 m5 m7 m9 m11 C1 1 1 0 1 0 1 C1 0C2 P2 m3 m6 m7 m10 m11 C2 0 1 0 1 1 1 C2 0C4 P4 m5 m6 m7 m12 C4 0 0 0 1 1 C4 0C8 P8 m9 m10 m11 m12 C8 1 0 1 1 1 C8 0C8 C4 C2 C10William Stallings “Data and Computer Communications”00080
Single Error CorrectionHamming Code – Example 4:The received Hamming codeword is:P1P200m3 P411m50m6 m700P80m9 m10 m11 m1200010001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100Deduce the correct character fromthe above codeword after correctionany error, if any.Conclusion: m11 is incorrect m11 must be 1 The codeword is 0 0 1 1 0 0 0 0 0 0 1 1 The message is 1 1 0 0 0 0 0 1 The EBCDIC character is ASolution of Example 4:C1 P1 m3 m5 m7 m9 m11 C1 0 1 0 0 0 0 C1 1C2 P2 m3 m6 m7 m10 m11 C2 0 1 0 0 0 0 C2 1C4 P4 m5 m6 m7 m12 C4 1 0 0 0 1 C4 0C8 P8 m9 m10 m11 m12 C8 0 0 0 0 1 C8 1C8 C4 C2 C11Dr. Mohammed Arafah0William Stallings “Data and Computer Communications”1181
Single Error CorrectionHamming Code – Example 5:The received Hamming codeword is:P1P200m3 P41m501m6 m701P80m9 m10 m11 m1211110001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100Deduce the correct character fromthe above codeword after correctionany error, if any.Conclusion: m5 is incorrect m5 must be 0 The codeword is 0 0 1 0 0 0 1 0 1 1 1 1 The message is 1 1 1 1 1 0 0 1 The EBCDIC character is 9Dr. Mohammed ArafahSolution of Example 5:C1 P1 m3 m5 m7 m9 m11 C1 0 1 1 1 1 1 C1 1C2 P2 m3 m6 m7 m10 m11 C2 0 1 0 1 1 1 C2 0C4 P4 m5 m6 m7 m12 C4 0 1 0
Dr. Mohammed Arafah William Stallings “Data and Computer Communications” 19 Asynchronous Transmission – Example 1 Construct the transmitted frame using asynchronous transmission mode which contains the following data: GO. Assume that the number of bits per character is 8, the number
CRYPTOGRAPHY AND NETWORK SECURITY, SIXTH EDITION A tutorial and survey on network security technology. Each of the basic building blocks of network security, . THE WILLIAM STALLINGS BOOKS ON COMPUTER AND DATA COMMUNICATIONS TECHNOLOGY. Foundations of Modern Networking SDN, NFV, QoE, IoT, and Cloud William Stallings With contributions by:
Chapter 1 - William Stallings, Data and Computer Communications, 8/e Author: Dr Lawrie Brown Subje
Larry Stallings Paso Robles 2 Iva Wilcox San Luis Obispo 3 02 - Cut Flowers ············· 3 records Larry Stallings Paso Robles 1 Rick Hicks Templeton 2 Joe Sabol San Luis Obispo 3 03 - Potted Plants ············· 3 records Larry Stallings Paso Robles 1
Nov 06, 2012 · William Stallings Computer Organization and Architecture 7th Edition Chapter 6 External Memory Types of External Memory Magnetic Disk —RAID —Removable Optical —CD-ROM —CD-Recorda
William Stallings Book: Chapter 5 OS – has processes and threads Multiprogramming: The management of multiple processes within in a uniprocessor system Distributed processing: The management of multiple processes executing on multiple distributed computer systems. Fundamental to OS is
Eight S-boxes which map 6 input to 4 bits out . William Stallings, Cryptography and Network Security 5/e Author: Dr Lawrie Brown Subject: Lecture
1. Computer Architecture and organization – John P Hayes, McGraw Hill Publication 2 Computer Organizations and Design- P. Pal Chaudhari, Prentice-Hall of India Name of reference Books: 1. Computer System Architecture - M. Morris Mano, PHI. 2. Computer Organization and Architecture- William Stallings, Prentice-Hall of India 3.
Abrasive jet Machining consists of 1. Gas propulsion system 2. Abrasive feeder 3. Machining Chamber 4. AJM Nozzle 5. Abrasives Gas Propulsion System Supplies clean and dry air. Air, Nitrogen and carbon dioxide to propel the abrasive particles. Gas may be supplied either from a compressor or a cylinder. In case of a compressor, air filter cum drier should be used to avoid water or oil .
