(Error Detection and Correction)

Presentation on theme: "(Error Detection and Correction)"— Presentation transcript:

1 (Error Detection and Correction)
Chapter 10 오류 발견과 교정 (Error Detection and Correction)

2 10 장 오류 검출 및 수정 10.1 개요 10.2 블록 코딩 10.3 선형 블록 코드 10.4 순환 코드 10.5 검사합
10.6 요약

3 Data can be corrupted during transmission.
오류 검출 및 수정 데이터는 전송 중에 변경될 수 있다. 신뢰성 있는 통신을 위해 오류들은 검출·정정되어야 한다. Data can be corrupted during transmission. Some applications require that errors be detected and corrected.

4 Topics discussed in this section:
10.1 개요 오류검출 및 오류정정에 직/간접적으로 관련된 사항들에 대해 먼저 살펴본다. Topics discussed in this section: Types of Errors Redundancy Detection Versus Correction Forward Error Correction Versus Retransmission Coding Modular Arithmetic

5 단일-비트 오류(Single-Bit Error)
데이터 부분의 한 비트만 변경

6 In a single-bit error, only 1 bit in the data unit has changed.
단일 비트 오류는 데이터 단위 중 하나의 비트만이 변경되었을 때를 말한다. In a single-bit error, only 1 bit in the data unit has changed.

7 폭주 오류(Burst Error) 데이터 부분의 2개 또는 그 이상의 비트가 변경

8 A burst error means that 2 or more bits in the data unit have changed.
폭주 오류는 데이터 단위에서 2개 이상의 비트들이 변경되는 경우를 일컫는다. A burst error means that 2 or more bits in the data unit have changed.

9 To detect or correct errors, we need to send
오류 검출은 목적지에서 오류를 검출하기 위해서 여분의 비트를 추가하는 중복(잉여)개념을 이용 To detect or correct errors, we need to send extra (redundant) bits with data.

10 중복(redundancy)

11 검출(detection) 대 정정(correction)
오류를 정정하는 것도 검출하는 것보다 어렵다. 전향 오류 정정 대 재전송 forward error correction : 수신자가 메시지의 중복비트를 이용하여 메시지를 추측해가는 과정 retransmission : 오류 발생을 검출하여 송신자에게 다시 보내줄 것을 요청하는 과정

12 오류 검출은 목적지에서 오류를 검출하기 위해 여분의 비트들을 추가하는 중복의 개념을 사용한다.
부호화(coding) 오류 검출은 목적지에서 오류를 검출하기 위해 여분의 비트들을 추가하는 중복의 개념을 사용한다.

13 부호화 방법 1. 블록 부호화(block coding) 2. 나선형 부호화(convolution coding)

14 본 교재에서는 블록 부호화에 집중하며 나선형 부호화는 다른 책에서 참조하기 바란다.
본 교재에서는 블록 부호화에 집중하며 나선형 부호화는 다른 책에서 참조하기 바란다. In this book, we concentrate on block codes; we leave convolution codes to advanced texts.

15 모듈로-N 산술에서는 0부터 N – 1 까지의 정수만을 사용한다.
모듈 연산(modular arithmetic) 법(modulus) N 이라는 제한된 정수를 사용 0 부터 N-1까지 정수 사용 예: 모듈로-2 연산에서 덧셈과 뺄셈 덧셈: = = = = 1 뺄셈: 0 – 1 = 0 0 – 1 = 1 1 – 0 = 1 1 – 1 =0 모듈로-N 산술에서는 0부터 N – 1 까지의 정수만을 사용한다.

16 Figure 10.4 모듈로-2 연산(XORing of two single bits or two words)

17 Topics discussed in this section:
10.2 블록 코딩(BLOCK CODING) 블록 부호화에서는 데이터워드(datawords)라고 불리는 k 비트의 블록으로 메시지를 나눈다. 각 블록에 r개의 중복 비트들을 더하여 길이 n = k + r 이 되도록 한다. 결과로 얻는 n 비트 블록들은 코드워드(codewords)라고 불린다. Topics discussed in this section: Error Detection Error Correction Hamming Distance Minimum Hamming Distance

18 그림 10.5 블록 코딩에서 데이터워드 (Dataword와 코드워드 codeword)

19 Example 10.1 4장에서 공부한 4B/5B 부호화는 이런 종류의 부호화의 좋은 예이다. 이 부호화 방법에서는 k = 4 이고 n = 5 이다. 모두 2k = 16 개의 데이터워드가 있고 2n = 32 개의 코드워드가 있다. 32개의 코드워드 중에서 16개가 메시지 전송에 사용되고 나머지는 다른 목적으로 이용되거나 사용되지 않는다.

20 Figure 10.6 Process of error detection in block coding

21 Example 10.2 k = 2이고 n = 3이라고 하자. 표 10.1 에 데이터 워드와 코드워드가 있다. 나중에 데이터워드로부터 어떻게 코드워드를 만들어 내는지 논의한다. 송신자가 데이터워드 01을 011로 부호화하여 수신자에게 보낸다고 하자. 다음 경우를 생각하라. 수신자가 011을 수신한다. 이는 유효 코드이다. 수신자는 이로부터 데이터워드 01을 추출한다.

22 Example 10.2(continued) 2. 코드워드가 전송 도중 손상되어 111이 수신되었다(맨 왼쪽 비트가 깨졌다). 이는 유효 코드가 아니므로 버려진다. 3. 코드워드가 전송 도중 손상되어 000 이 수신되었다(오른쪽 두 비트가 깨졌다). 이는 유효코드이다. 수신자는 이로부터 부정확한 데이터워드인 00 을 추출한다. 두 개비트가 손상되어 오류를 찾지 못한다.

23 Table 10.1 A code for error detection (Example 10.2)

24 오류 검출 코드는 찾도록 설계된 오류만을 찾아낸다. 다른 오류는 검출되지 못한다.
오류 검출 코드는 찾도록 설계된 오류만을 찾아낸다. 다른 오류는 검출되지 못한다. An error-detecting code can detect only the types of errors for which it is designed; other types of errors may remain undetected.

25 Figure 10.7 Structure of encoder and decoder in error correction

26 Example 10.3 예제 10.2 에 더 많은 중복 비트들을 넣어 수신자가 원래 무엇이 보내졌는지 모르는 상태에서 오류를 정정할 수 있는지 보자. 2비트 데이터워드에 3비트의 중복 비트를 넣어 5비트 코드워드를 만든다. 나중에 어떻게 중복 비트들을 생성하는지를 논의한다. 일단 오류 정정의 개념에 대해서만 집중하자. 표 10.2에 데이터워드와 코드워드가 있다. 데이터워드가 01 이라고 하자. 송신자는 표를 보고(또는 알고리즘을 사용하여) 코드워드 01011을 만들어 낸다. 코드워드가 전송 도중 손상되어 01001이 수신되었다(오른쪽에서 두 번째 비트가 깨졌다). 우선 수신자는 전송 받은 코드워드가 표에 없다는 것을 안다. 이는 오류가 발생한 것을 말한다(정정 이전에 먼저 검출이 되어야 한다). 수신자는 오직 1비트가 망가진 것을 가정하고 다음 전략을 사용하여 올바른 데이터워드를 추정한다.

27 Example 10.3(continued) 1. 수신된 코드워드를 표의 첫 번째 코드워드와 비교하여(01001 대 00000), 수신자는 두 코드워드가 두 비트가 다르므로 첫 번째 코드워드를 보낸 것이 아니라고 추정한다. 2. 같은 이유로 원래의 코드워드는 표의 세 번째나 네 번째의 코드워드가 될 수 없다. 3. 원래의 코드워드는 따라서 표의 두 번째 것일 수밖에 없는데 이는 수신된 코드워드와 1비트가 다른 것은 이것뿐이기 때문이다.수신자는 01001을 01011로 바꾸어 넣고 표로부터 데이터워드가 01 인 것을 알게 된다.

28 Table 10.2 A code for error correction (Example 10.3)

29 두 워드 사이의 해밍 거리는 차이가 나는 해당 비트들의 개수이다.
해밍 코드(Hamming Code) 오류 제어를 위해 해밍 거리(hamming distance) 이용 두 개의 같은 크기의 워드간에 차이가 나는 비트의 갯수 두 워드에 XOR 연산을 해서 얻은 결과 값의 1의 갯수 두 워드 사이의 해밍 거리는 차이가 나는 해당 비트들의 개수이다. The Hamming distance between two words is the number of differences between corresponding bits.

30 Example 10.4 두 워드들 사이의 해밍 거리를 알아보자.
d(000, 011)은 2인데 이는 은 001(두 개의 1) 이기 때문이다. 2. d (10101, 11110)은 3인데 은 01011(3개의 1)이기 때문이다.

31 최소 해밍 거리는 모든 가능한 워드 조합 중 가장 작은 해밍 거리이다.
최소 해밍 거리는 모든 가능한 워드 조합 중 가장 작은 해밍 거리이다. The minimum Hamming distance is the smallest Hamming distance between all possible pairs in a set of words.

32 Example 10.5 표 10.1의 부호화 방식의 최소 해밍 거리를 구하라. Solution 우선 모든 해밍 거리를 구한다. 이 경우의 dmin 은 2이다.

33 Example 10.6 표 10.2의 최소 해밍 거리를 구하라. Solution 우선 모든 해밍 거리를 구한다. 이 경우 dmin 3이다.

34 s 개까지의 오류가 발생해도 오류가 생긴 것을 알아내는 것을 보장하기 위해서는 블록 코드의 최소 해밍 거리는 dmin = s + 1 이어야 한다.
To guarantee the detection of up to s errors in all cases, the minimum Hamming distance in a block code must be dmin = s + 1.

35 Example 10.7 우리의 첫 번째 코드 기법(표 10.1)의 최소 해밍 거리는 2이다. 이 코드는 오직 단일 비트 오류를 검출할 수 있다. 예를 들면 세 번째 코드(101)가 전송되었는데 한 비트 오류가 발생했다면 수신된 코드는 그 어떤 유효 코드가 일치하지 않는다. 그러나 두 개의 오류가 발생했다면 수신된 코드워드는 다른 유효 코드와 일치할 수 있으므로 오류를 알아 낼 수 없다.

36 Example 10.8 두 번째 블록 코드 기법(표 10.2)는 dmin = 3이다. 이 코드는 두 개까지의 오류를 알아 낼 수 있다. 유효 코드가 전송된 경우에 두 개 비트의 오류는 유효 코드와 일치하는 결과를 발생하지 않는다. 수신자는 속을 수가 없는 것이다. 그러나 어떤 세 개의 비트의 오류는 다른 유효 코드로 인식될 수 있다. 수신자는 이 수신된 코드워드를 인정하게 되어 오류는 검출되지 않는다.

37 Figure 10.8 Geometric concept for finding dmin in error detection

38 Figure 10.9 Geometric concept for finding dmin in error correction

39 모든 경우에서 t 개의 오류까지 정정을 보장하기 위하여 블록 코드의 최소 해밍 거리는 dmin = 2t + 1 이어야 한다.
To guarantee correction of up to t errors in all cases, the minimum Hamming distance in a block code must be dmin = 2t + 1.

40 Example 10.9 어떤 코드 방식이 해밍 거리 dmin = 4 이다. 이 방식의 오류 검출 및 정정 능력은 얼마인가?
Solution 이 코드는 최대 3개(s=3)까지의 오류를 검출할 수 있으나 최대 1대 비트의 오류만 정정 가능하다. 다시 말하면 오류 정정에 이 코드가 사용된다면 일부 용량이 낭비되는 것이다. 오류 정정 코드는 홀수 개의 최소 거리를 필요로 한다(3, 5, 7···)

41 Topics discussed in this section:
10.3 선형 블록 코드(LINEAR BLOCK CODE) 오늘날 사용되는 대부분의 블록 코드는 선형 블록 코드(linear block codes) 중 하나이다. 비선형 블록 코드는 오류 검출이나 정정에 널리 쓰이지 않는데 그 구조가 이론적으로 복잡하고 구현하기 힘들기 때문이다. Topics discussed in this section: Minimum Distance for Linear Block Codes Some Linear Block Codes

42 선형 블록 코드에서는 임의의 두 유효 코드워드에 XOR 연산을 가하면 다른 유효 코드워드가 생성된다.
In a linear block code, the exclusive OR (XOR) of any two valid codewords creates another valid codeword.

43 Example 10.10 표 10.1 에 정의한 두 개의 코드워드들이 선형 블록 코드워드에 속하는지 알아보자.
1. 표 10.1 에 사용된 방식은 임의의 코드워드를 다른 코드워드와 XOR 연산을 시키면 다른 유효 코드워드가 나오기 때문에 선형 블록 코드이다. 예를 들면, 두 번째 코드워드와 세 번째 코드워드를 XOR하면 네 번째 코드워드가 나온다. 2. 표 10.2 의 코드 또한 선형 블록 코드이다. 모든 코드워드를 다른 코드워드 두 개를 XOR 하여 구할 수 있다.

44 Example 10.11 표 10.1 의 코드에서는 0 이 아닌 코드워드의 1 의 개수는 각각 2, 2 및 2이다. 그러므로 최소 해밍 거리 dmin = 2이다. 표 10.2의 코드에서는 0이 아닌 코드워드의 1의 개수는 3, 3 및 4 이다. 따라서 이 코드에서는 dmin = 3이다.

45 단순 패리티 확인 코드는 n = k + 1 이며 dmin = 2 인 단일 비트 오류 검출 코드이다.
A simple parity-check code is a single-bit error-detecting code in which n = k + 1 with dmin = 2.

46 Table 10.3 Simple parity-check code C(5, 4)

47 Figure 10.10 Encoder and decoder for simple parity-check code

48 Example 10.12 어떤 전송 시나리오를 살펴보자. 송신자는 1011의 데이터워드를 보낸다고 하자. 이 데이터워드로부터 생성된 코드워드는 10111이며 이것이 수신자에게 보내진다. 다섯 가지 경우에 대해 조사해 보자. 1. 오류가 발생하지 않았다. 수신된 코드워드는 10111이다. 증상은 0이다. 데이터워드 1011이 만들어진다. 2. a1비트에 손상이 생겨 한 비트가 바뀌었다. 수신된 코드워드는 10011이다. 증상은 1이다. 3. r0비트에 손상이 생겨 한 비트가 바뀌었다. 수신된 코드워드는 10110이다. 증상은 1이다. 데이터워드는 만들어지지 않았다. 데이터비트는 손상되지 않았지만 코드가 어디가 손상되었는지 알려주지 못하므로 데이터워드를 만들지 못했다.

49 Example 10.12(continued) 4. r0와 a3비트에 오류가 생겨 해당 비트를 바꾸었다. 수신된 코드워드는 이다. 증상은 0이다. 데이터워드 0011이 수신자에 의해 만들어졌다. 잘못된 증상 값 때문에 잘못된 데이터워드가 만들어졌다는 것에 유의하라. 단순 패리티 확인 코드는 짝수 개의 오류가 발생하면 검출해 내지 못한다. 오류가 서로를 상쇄해서 증상 값이 0이 된다. 5. a3, a2, a1 세 비트가 오류가 발생하여 값이 바뀌었다. 수신된 코드워드는 01011이다. 증상은 1이다. 데이터워드는 생성되지 않았다. 이는 단일 비트 오류를 검출토록 보장된 단순 패리티 확인 코드는 홀수 개의 오류도 검출해 내는 것을 보여준다.

50 A simple parity-check code can detect an odd number of errors.
단순 패리티 확인 코드는 홀수 개의 오류를 검출한다. A simple parity-check code can detect an odd number of errors.

51 All Hamming codes discussed in this book have dmin = 3.
본 교재의 모든 해밍 코드는 dmin = 3이다. m과 n의 관계는 n = 2m – 1이다. All Hamming codes discussed in this book have dmin = 3. The relationship between m and n in these codes is n = 2m − 1.

52 Figure 10.11 Two-dimensional parity-check code

53 Figure 10.11 Two-dimensional parity-check code

54 Figure 10.11 Two-dimensional parity-check code

55 Table Hamming code C(7, 4)

56 Figure 10.12 The structure of the encoder and decoder for a Hamming code

57 Table 10.5 Logical decision made by the correction logic analyzer

58 Example 10.13 송신자로부터 목적지로 가는 세 개의 데이터워드를 따라가 보자.
1. 데이터워드 0100은 코드워드 이 된다. 코드워드 이 수신 되었다. 증상은 000(오류없음)이며 마지막 데이터워드는 0100이다. 2. 데이터워드 0111은 코드워드 이 된다. 코드워드 이 수신되었다. 증상은 011이다. 표 10.5에 따르면 b2 비트를 뒤집어(1을 0으로 바꾸어) 마지막으로 데이터워드 0111을 얻는다. 3. 데이터워드 1101은 코드워드 이 된다. 코드워드 이 수신되었다(두 개의 오류). 증상은 101이며 이는 b0에 오류가 있다는 것을 말한다. 이에 b0의 값을 뒤집은 다음에 데이터워드로 0000을 얻는데 이는 잘못된 데이터워드이다. 이는 이 코드는 두 개의 오류를 정정할 수 없다는 것을 보여준다.

59 Example 10.14 최소 7비트의 데이터워드가 필요하다. 이 경우의 k값과 n값을 구하라 . Solution
여기서 k = n − m 이 7보다 커야 하므로 2m − 1 − m ≥ 7. 1. 만일 m = 3으로 하면 그 결과는 n = 23 − 1 이므로 k = 7 − 3 = 4 인데 그 결과 값을 취할 수 없다. 2. 만일 m = 4로 하면 n = 24 − 1 = 15 에서 k = 15 − 4 =11 이며 이 결과는 조건을 만족한다. 그러므로 코드는 C(15, 11)이다. 데이터워드의 크기를 일정하게 하는 방법들이 있지만 그에 대한 논의는 본 교재의 범위를 벗어난다.

60 Figure 10.13 Burst error correction using Hamming code

61 Topics discussed in this section:
10.4 순환 코드(CYCLIC CODE) 순환코드는 하나의 특별한 성질이 있는 선형 블록 코드이다. 순환코드(Cyclic codes)에서는 코드워드를 순환시키면 다른 코드워드를 얻는다. Topics discussed in this section: Cyclic Redundancy Check Hardware Implementation Polynomials Cyclic Code Analysis Advantages of Cyclic Codes Other Cyclic Codes

62 Table 10.6 A CRC code with C(7, 4)
순환 중복 확인 LAN이나 WAN에서 많이 사용 Table A CRC code with C(7, 4)

63 Figure 10.14 CRC encoder and decoder

64 Figure 10.15 Division in CRC encoder

65 Figure 10.16 Division in the CRC decoder for two cases

66 Figure 10.17 Hardwired design of the divisor in CRC

67 Figure 10.18 Simulation of division in CRC encoder

68 Figure 10.19 The CRC encoder design using shift registers

69 Figure 10.20 General design of encoder and decoder of a CRC code

70 Figure 10.21 A polynomial to represent a binary word

71 Figure 10.22 CRC division using polynomials

72 순환 코드에서 제수는 보통 생성 다항식 또는 생성식이라고 부른다.
순환 코드에서 제수는 보통 생성 다항식 또는 생성식이라고 부른다. The divisor in a cyclic code is normally called the generator polynomial or simply the generator.

73 순환코드에서는 a. 비트 손상이 없거나 1. 만일 s(x) ≠ 0이면 한 개 이상의 비트가 손상된 것이다.
b. 비트 손상이 있었어도 검출에 실패한 것이다.

74 순환 코드에서 g(x)로 나누어 떨어지는 오류는 검출되지 않는다.
In a cyclic code, those e(x) errors that are divisible by g(x) are not caught.

75 생성기가 두 개 이상의 항목을 가지면서 x0 의 계수가 1이면 모든 단일 비트 오류는 검출된다.
If the generator has more than one term and the coefficient of x0 is 1, all single errors can be caught.

76 Example 10.15 다음 중 단일 비트 오류를 검출하는 것을 보장하는 g(x)는? 각 경우 검출할 수 없는 오류는?
a. x b. x c. 1 Solution a. 어떤 xi 도 x + 1로 나누어 떨어지지 않는다. 다시 말하면 xi/(x + 1)은 항상 나머지가 있다. 그러므로 증상은 0이 아니다. 임의의 단일 비트오류를 검출할 수 있다. b. 만일 i가 3이상이면 xi 는 g(x)로 나누어 떨어진다. xi /x3 의 나머지는 0이며 수신자는 오류가 있음에도 불구하고 잘못되어 오류가 없다고 믿게 된다. 이 경우에 손상된 비트는 4 또는 그 이상의 위치이어야 한다. 1부터 3까지의 위치에 발생한 단일 비트 오류는 모두 검출할 수 있다. c. 모든 i 의 값에 대해 xi 는 g(x)로 나누어 떨어진다. 단일 비트 오류를 검출할 수 없다. 더욱이 g(x)는 데이터워드에 n – k 개의 0을 더하여 코드워드를 만든 것이기 때문에 쓸모가 없다.

77 Figure 10.23 Representation of two isolated single-bit errors using polynomials

78 If a generator cannot divide xt + 1 (t between 0 and n – 1),
생성기가 xt + 1(t는 0과 n-1 사이)를 나누어 떨어지게 하지 못하면 모든 분리된 두 개의 오류를 검출할 수 있다. If a generator cannot divide xt + 1 (t between 0 and n – 1), then all isolated double errors can be detected.

79 Example 10.16 다음 생성기의 단일 비트 오류와 분리된 두 개의 오류에 대한 관계를 확인하라.
a. x b. x c. x7 + x d. x15 + x14 + 1 Solution 생성기로서는 매우 적절치 못하다. 서로 이웃하는 두 개의 오류를 검출할 수 없다. b. 이 생성기는 4개 비트 만큼 떨어진 두 개의 오류를 검출할 수 없다. 두 개의 오류는 어디든지 생길 수 있는데 그 거리가 4라면 검출할 수 없다. c. 이 생성기는 이런 목적에 적절하다. d. 이 다항식은 t가 32,768보다 작은 xt + 1 형식의 오류를 나누어 떨어지게 하지 못한다. 이는 서로 이웃하거나 최대 32,768만큼 떨어진 두 개의 오류는 생성기에 의해 검출된다는 것을 말한다.

80 x + 1을 인자로 갖는 생성기는 모든 홀수 개의 오류를 검출할 수 있다.
A generator that contains a factor of x + 1 can detect all odd-numbered errors.

81 ❏ L ≤ r 인 폭주 오류는 모두 검출된다. ❏ L = r + 1 인 폭주 오류는 1 – (1/2)r–1의 확률로 검출된다. ❏ L > r + 1 인 폭주 오류는 1 – (1/2)r의 확률로 검출된다.

82 다음 생성기가 다양한 길이의 폭주 오류를 검출하는 안정도를 찾아라.
Example 10.17 다음 생성기가 다양한 길이의 폭주 오류를 검출하는 안정도를 찾아라. a. x b. x18 + x7 + x c. x32 + x23 + x7 + 1 Solution a. 이 생성기는 길이가 6비트 이하의 모든 폭주 오류를 찾아낸다. 길이 7인 폭주 오류는 100개 중 3개가 검출되지 않을 것이며 길이가 8이상인 폭주 오류는 1000개 중 16개가 검출되지 않을 것이다.

83 Example 10.17(continued) b. 이 생성기는 길이가 18비트 이하의 모든 폭주 오류를 찾아낸다. 길이 18인 폭주 오류는 100만 개 중 8 개가 검출 되지 않을 것이며 길이가 19 이상인 폭주 오류는 100만 개 중 4개가 검출되지 않을 것이다. c. 이 생성기는 길이가 32비트 이하의 모든 폭주 오류를 찾아낸다. 길이 33인 폭주 오류는 100억 개 중 5개가 검출되지 않을 것이며 길이가 33 이상인 폭주 오류는 100억 개 중 3개가 검출되지 않을 것이다.

84 좋은 생성기는 다음 특성을 가져야 한다. 1. 두 개 이상의 항목으로 되어 있어야 한다. 2. 항목 x0 의 계수는 1이어야 한다. 3. 2부터 n – 1 사이의 t 값에 대해 xt + 1을 나누어 떨어지지 않게 해야 한다. 4. x + 1을 인자로 가져야 한다.

85 Table 표준 다항식

86 Topics discussed in this section:
10-5 검사합(CHECKSUM) 여기서 논의하는 마지막 오류 검출 방법은 검사합이다. 검사합은 데이터 링크층 뿐만 아니라 인터넷에서 여러 프로토콜에 의해 사용되고 있다.그렇지만, 여기서는 오류 확인에 대한 논의를 마치기 위해 간단하게 살펴본다 Topics discussed in this section: Idea One’s Complement Internet Checksum

87 Example 10.18 목적지에 보내고자 하는 5개의 4 비트 숫자 데이터가 있다고 가정하자. 이들 숫자에 덧붙여 숫자의 합도 보낸다. 예를 들면, 숫자 (7, 11, 12, 0, 6)에 대해 (7, 11, 12, 0, 6, 36)를 보낸다, 여기서 36은 숫자의 합이다. 수신자는 5개의 숫자를 더해서 그 결과를 합과 비교한다. 만약 두 값이 같으면 수신자는 오류가 없다고 판단하고, 5개의 숫자를 받아들인다. 그렇지 않으면 어딘가 오류가 있다고 판단하고 데이터를 받아들이지 않는다.

88 Example 10.19 검사합(checksum)이라는 합의 음수(보수)를 보내면 수신자가 하는 일을 쉽게 할 수 있다. 이 경우에 (7, 11, 12, 0, 6, −36)를 보내게 된다. 수신자는 검사합을 포함해서 모든 숫자를 더한다. 결과가 0 이면 오류가 없고 그렇지 않으면 오류가 있다고 간주한다.

89 수 21을 단 4 비트만 사용하여 one’s complement arithmetic 으로 표시할 수 있는가?
Example 10.20 1의 보수 0 부터 2n-1 사이의 부호 없는 수를 n 비트만 사용하여 나타냄 수가 n 비트 보다 많으면 왼편의 남은 비트를 n개의 오른편 비트에 더해짐 수 21을 단 4 비트만 사용하여 one’s complement arithmetic 으로 표시할 수 있는가? Solution 이진수 21은 10101이다(5개의 비트가 필요하다). 맨 왼편의 비트를 돌려서 맨 오른편에 더 할 수 있다. 결과로는 = 0110 즉 6 이다.

90 Example 10.21 4비트만을 사용하여 -6을 어떻게 1의 보수 연산으로 표시할 수 있는가? Solution

91 Example 10.22 예제 10.19를 1의 보수 연산을 이용하여 다시 해보자. 그림 송신자와 수신자에서 처리 과정을 보여준다. 송신자는 검사합을 0 으로 초기화한 다음 모든 데이터 항목과 검사합을 더한다(검사합도 하나의 데이터 항목으로 간주한다. 결과는 36이다. 그렇지만 36은 4 비트로 나타낼 수 없다. 여분의 2 비트는 오른쪽으로 돌려져서 결국에 합은 6이 된다. 그림에서 2진수로 자세하게 보여주고 있다. 합은 보수를 취하고 결과가 검사합이 된다. 9 (15 − 6 = 9). 송신자는 검사합 9를 포함해서 수신자에게 6 개의 데이터 아이템을 보낸다.

92 Example 10.22(continued) 수신자는 송신자와 같은 절차를 수행한다. 모든 데이터 아이템을 더한다(검사합 포함). 결과는 45이다. 합은 돌려지고 15가 된다. 돌려진 합은 보수를 취하고 결과는 0이 된다. 검사합이 0 이기 때문에 이것은 데이터가 손상되지 않았음을 의미한다. 수신자는 검사합을 버리고 다른 아이템은 보관한다. 만약 검사합이 0이 아니면 전체 패킷은 버려진다.

93 Figure Example 10.22

94 송신자 쪽 1. 메시지를 16비트 워드로 나눈다. 2. 검사합 워드의 값은 0으로 둔다.
3. 검사합을 포함한 모든 워드는 1의 보수연산을 하여 더한다. 4. 그 합을 보수를 취하여 그 최종 값을 검사합으로 한다. 5. 검사합을 데이터와 함께 보낸다.

95 수신자 쪽 1. 메시지(검사합을 포함)를 16비트 워드로 나눈다. 2. 모든 워드를 1의 보수 연산을 하여 더한다. 3. 그 합을 보수를 취하여 그 최종 값을 새로운 검사합으로 한다. 4. 검사합의 값이 0이면 메시지를 받고 아니면 거부한다.

96 Example 10.23 8개의 문자로 된 Forouzan의 검사합을 계산해 보자. 이 문자열은 16비트 워드로 나누어야 한다. ASCII(부록 A)를 사용하여 각 바이트를 2자리의 16진수로 바꾼다. 예를 들면 F는 0x46 으로 표시되고 o 는 0x6F 로 표시한다. 그림 10.25는 송신자와 수신자가 어떻게 검사합을 계산하는지 보여준다. 그림의 a에서는 첫 번째 열의 부분 합은 0x36 이다. 오른쪽의 6은 유지하고 왼편의 3은 두 번째 열로 보낸다. 각 열에 대해 이 과정을 반복한다. 16진수는 부록 B에 소개되어 있다.

97 Figure Example 10.23

98 10.6 요약 Q & A

99 Report 연습 문제 풀이 다음주 이 시간까지