[데이터 통신] 10. Error Detection and Correction

cyclic code, checksum 시험 문제 무조건 나옴(교수님 피셜)

• code를 주고 어떻게 cyclic code를 generation 하고 어떻게 generated 된 코드를 통해서 error가 있는지 없는지를 detection 하는 부분

10.1 Introduction

Type of Errors

• An electromagnetic signal is subject to interference from heat, magnetism, and other forms of electricity
• Single-bit error: 0 → 1 or 1 → 0
  • A single bit per data unit is inverted (such as a byte, character, or packet)
• Burst error: two or more bits have changed
  • burst length는 bit rate와 연관이 있고 noise의 size와도 연관이 있다고 말할 수 있다.
  • 보통 burst error가 많이 일어남.

Redundancy

• Error detection and correction use the concept of redundancy, which means adding extra (redundant) bits for detecting errors at the destination.

message만 달랑 보내서는 error detection을 할 수 없기 때문에 generator라고 하는 특수한 방법론을 이용해서 message로 부터 redundancy를 만들어 내서 붙여서 보내고 수신측에서는 그 redundancy와 함께온 message로부터 error가 있는지 없는지 check(점검)를 하게 된다.

그래서 error 없으면 original message만을 뽑아가고 error가 있으면 message를 버린다.

 

Error Control

• Detection Versus Correction
  • Detection: error ? yes or no (즉, error가 있는지 없는지)
  • Correction: Need to know the exact number of bits that are corrupted, and their location in the message
• Forward Error Correction versus Retransmission
  • Retransmission (resending) : Backward error correction
  • forward error correction: sender가 보내면 receiver가 받아서 거기서 스스로 error를 correction을 하는데 이 error를 correction하기 위해서는 error의 유무만 알아서는 안되고 error의 위치까지 알아서 그것 을 1이면 0으로 0이면 1로 바꿔주는 것이다.
    • 왔다갔다 하지 않아도 되지만 error의 유무 뿐만 아니라 error의 위치까지 알아내야 하기 때문에 좀 더 복잡한 detection algorithm이 있어야 한다.(훨씬 더 redundancy가 많아짐)
  • Backward error correction: sender가 receiver에게 보내고 receiver는 error를 detection 해 보니까 error가 있는데 위치까지는 모른다 그러면 backward 즉, 다시 sender에게 재전송(resending) 을 요구하는 것이다.
    • error가 있는지 없는지만 알아내면 되기 때문에 overhead가 적고 error가 있으면 sender에게 재전송을 요구하는 방식이다.
  • 각각의 장단점이 있지만 보편적으로 일반적인 통신에서는 backward error detection을 더 많이 사용한다.
• Coding for redundancy
  • Block coding: discussed in our textbook
  • Convolution coding: 매우 복잡하여 이번에는 다루지 않을 것임

 

10.2 Block Coding

• Divide the message into blocks, each of k bits, called datawords.
• Add r redundant bits to each block to make the length n = k + r. The resulting n-bit blocks are called codewords
  • original message를 잘게 자른 k-bit에다가 k-bit를 안전하게 전달하고 안전하게 error detection을 하기 위해서 redundancy r을 붙이게 되는데 그러면 n이 나오게 되고 결과적으로 k bit block이 n bit block으로 바뀌는 것이다. 이 과정에서 바뀐 n bit의 code block을 codeword라고 함.
• receiver가 valid codewords를 가지거나 찾을 수 있고, orginal codeword가 invalid codeword를 바꿀 수 있으면 error를 detect 할 수 있다.
• Example: 4B/5B block coding
  • k = 4 and n = 5.
    • r = 1
  • 2^k = 16 datawords and 2ⁿ = 32 codewords.
    • 4 bit 단위의 각 datawords를 5 bit 단위의 codewords로 바꾸었다.

Error Detection in Block Coding

• 이 세상에 존재하는 transmission은 unreliable transmission임.
• k bits의 dataword에 generator를 통해 redundancy r을 붙여 n bits의 codeword를 생성해 낸다.
• 그래서 transmission을 통해 도착한 codeword가 손상을 입었을 수도 안 입었을 수도 있는데 이를 위의 checker를 통해서 만약 손상을 입었으면 버리고 안 입었으면 그대로 가져가서 dataword만 뽑아내는 과정이다.

 

• Example 10.1:
  • Assume that k = 2 and n = 3 (Table 10.1)

• ex) generator에서 dataword를 add한 결과를 뒤에 붙이게 된다.
• 여기서 유의해야 할 점은 우리가 실제로 보내고 싶어하는 data는 2 bit의 dataword인데 이 codewords를 어떻게 해석하여 다시 dataword로 변환할 수 있는지이며 이는 뒤에서 배워보도록 하겠다.

 

Error Detection

• Assume the sender encodes the dataword 01 as 011 and sends it to the receiver. Consider the following cases:

1. The receiver receives 011 which is a valid codeword. The receiver extracts the dataword 01 from it.(by checker)
2. The codeword is corrupted during transmission, and 111 is received. This is not a valid codeword and is discarded.
3. The codeword is corrupted during transmission, and 000 is received. This is a valid codeword. The receiver incorrectly extracts the dataword 00. Two corrupted bits have made the error undetectable.
   • 두 bit가 깨짐으로써 valid한 경우에는 valid한 것으로 착각하여 위로 보내게 되는 문제가 발생한다. 이로써 두 bit가 깨지면 error undetectable임을 알 수 있다.

→ An error-detecting code can detect only the types of errors for which it is designed; other types of errors may remain undetected

 

Hamming Distance

위에서 봤듯이 어떤 경우는 error detection이 되고(single bit) 어떤 경우에는 error detection이 안 되는 경우(2 bit)가 있었기 때문에 이를 해결하고자 나온 방법론에 대해서 배워볼 것인데 그 전에 word 간의 bit corrupted가 알마나 되었는지를 알기 위함 hamming distance에 대해서 알아보자.

• The Hamming distance between two words is the number of differences between corresponding bits.
• Example: Hamming distance d(10101, 11110) is 3
• Minimum Hamming Distance for Error Detection: d_min
  • The smallest Hamming distance between all possible pairs of codewords
  • 차이가 가장 없는 수치
• To guarantee the detection of up to s errors in all cases, the minimum Hamming distance in a block code must be d_min = s +1
  • 예를 들어, 우리가 single bit error detection 을 하고 싶다고 하면 dmin = 1+1 = 2 이므로 모든 가능한 pairs of codewords 중에서 최소 2개의 bit가 달라야 하는 것이다.

s 보다 dmin이 항상 적어도 1만큼 더 커야한다.


그래서 아까 살펴 보았던 예제 10.1 표에서 볼 수 있듯이 codeword에서 서로서로가 2 bit씩만 다르기 때문에 hamming distance가 2였기 때문에 single bit error detection(s=1) 까지만 가능했던 것이다.

 

Linear Block Codes

대부분 linear block codes를 사용한다.

valid한 두 개의 codeword가 있을 때 그 두 개의 codeword에 대해 XOR를 하게 되면 새로운 valid codeword가 만들어 지도록 동작하게 된다.

• XOR: 같으면 0 다르면 1
• 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 OR (addition modulo-2) of two valid codewords creates another valid codeword
• The minimum Hamming distance is the number of 1s in the nonzero valid codeword with the smallest number of 1s
  • nonzero valid codeword 중에서 1의 갯수가 가장 적은 case가 minimum hamming distance

 

그럼 다시 예제 10.1로 이것을 이해해 보도록 하자.

• 위 표에서 두 개의 codewords에 대해서 XOR를 진행하면 모든 경우에 another valid한 codeword가 나오게 되고 이것이 linear block code의 특징으로 볼 수 있다.
• 또한 1이 적어도 한 개라도 있는 codewords 중에서 1이 최소한으로 있는 경우에서 1의 갯수가 the minimum hamming distance이고 이를 통해 최대 single bit의 error detection을 할 수 있음을 알 수 있다.

 

Linear Block Code: Parity-Check Code

parity-check: 보내고 싶어하는 정보에 대해서 쭉 add해서 1의 자리 숫자가 홀수이면 1을 붙이고 1의 자리 숫자가 짝수면 0을 붙이는 과정

dataword의 모든 bit를 더해서 1의 자리 숫자가 홀수이면 1을, 1의 숫자가 짝수면 0을 맨 뒤에 붙여서 codewords를 만든다.

Simple parity check method consists of just one redundant bit per data unit.

• A simple parity-check code is a single-bit error-detecting code in which n = k + 1 with d_min = 2.

• 가장 작은 valid 1의 숫자를 통해서도 dmin을 구할 수 있다.
  • dmin = 2
• XOR 를 했을 때 1의 최소 갯수
• even number의 error는 detect 하지 못함

 

Encoder and Decoder for Parity -Check Code

• The result of addition over all 5 bits: Syndrome

• syndrome에서 모든 bit를 더한 결과를 0으로 받으면 decision logic에서 error가 없는 것으로 판단하여 redundancy를 빼고 받아들이고
• 0이 아니면 error가 있는 것으로 판단하여 버리게 된다(discard).

 

10.3 Cyclic Codes: CRC (Cyclic Redundancy Code)

cycles means shift

• Cyclic codes are special linear block codes with one extra property.
• If a codeword is cyclically shifted (rotated), the result is another codeword
• Cyclic Redundancy Check (CRC)

• left shift를 시켰을 때 맨 앞의 bit가 맨 뒤로 붙게 되었을 때 valid한 codeword가 나오게 된다.
• right shift를 시켰을 때 맨 뒤의 bit가 맨 앞로 붙게 되었을 때 valid한 codeword가 나오게 된다.

 

CRC Encoder and Decoder

• syndrome 값이 000으로 딱 맞아 떨어지면 error가 없다고 판단하여 받아들인다.
• CRC에서 generator에서는 아까와 다르게 add만 하는 것이 아니라 Divisor를 사용하여 나눗셈을 통해 redundancy를 붙이게 된다.
  • 근데 이 Divisor 숫자는 Generator와 Checker 모두에게 쓰여(shared) 각자 할 일을 위해 결과 값이 사용된다.
    • 똑같은 Divisor 사용

 

Division in CRC Encoder

1001을 보내고 싶은 경우 이 값에 000을 붙여서 Divisor로 나눠서 몫은 버리고 나머지 부분을 redundancy로써 원래의 1001 뒤에 붙여준다.

parity check보다 좀 더 복잡한 generator 연산이 이루어짐을 알 수 있다.(나눗셈/곱셈)

 

dividend는 나눠지는 수이며 dataword에 [# divisor bit - 1]bit 만큼의 0이 뒤에 붙은 것이 dividend이다.

 

Division in CRC Decoder

• 제대로 도착한 경우
  • Divisor로 나눈 경우 나머지(syndrome)이 나누어 떨어짐으로 error가 없는 것으로 판단할 것이다.
• 오다가 1 bit가 깨진 경우(손상을 입은 경우)
  • Divisor로 나누었을 때 나누어 떨어지지 않기 때문에 syndrome(나머지)이 000 값을 가지지 않을 것이고 이는 error가 있는 것으로 판단하여 decision logic에서 discard된다.

parity checker에서는 2 bit가 깨지면 error detection에 실패했는데 그것보다 훨씬 더 정교한 error detection이 가능하기 때문에 훨씬 더 중요한 error detection 방식이다.

이와 관련된 간단한 문제 한 두 개 정도 반드시 풀어보기!!!!

 

Polynomials

앞선 CRC에서 binary bit 간의 divisor가 이루어졌기 때문에 이를 Polynomials 형태로 바꾸어 생각하면 더 편하게 계산이 가능할 것이다.

• Degree of a polynomial: the highest power in the polynomial
  • Example: x⁶ + x + 1 → the degree '6'
  • bit 로 따지면 7 bit

 

Polynomial Operation

• Adding and subtracting polynomials
  • 1(2) + 1(2) = 0이기 때문에 사라지는 셈이다.

(x⁵ + x⁴ + x²) + (x⁶ + x⁴ + x²) → x⁶ + x⁵

• Multiplying two polynomials= x⁷ + x⁶ + x⁵ +x⁵ + x⁴ + x³ + x⁴ + x³ + x² + x³ + x² + x
• = x⁷ + x⁶ + x³ + x
• (x⁵ + x³ + x² + x) (x² + x¹ + 1)
• Dividing one polynomial by another
• Shifting
  • Shifting left 3 bits: 10011 becomes 10011000
    • 뒤에 0이 shift 된 만큼 붙는다.
  • Shifting right 3 bits: 10011 becomes 10 (x⁴ + x + 1 → x )
    • 마지막 bit부터 shitf된 만큼 버린다.

 

CRC Division Using Polynomials

• The divisor in a cyclic code is normally called the generator polynomial or simply the generator.

Cyclic Code Analysis

• f(x) is a polynomial with binary coefficients
  • Dataword: d(x)
  • Codeword: c(x)
  • Generator: g(x)
  • Syndrome: s(x)
  • Error: e(x)
• In a cyclic code,

1. If s(x) ≠ 0, one or more bits is corrupted.
2. If s(x) = 0, eitherb. Some bits are corrupted, but the decoder failed to detect them (Problem)
   • 그래서 CRC는 parity check 보다 error detection을 잘하긴 하지만 완벽하진 않은 것이다.
3. a. No bit is corrupted. -> Okay

• Received codeword = c(x) + e(x)
• Received codeword/g(x) = c(x)/g(x) + e(x)/g(x)
  • error가 없는 경우 c(x)가 g(x)로 나누어지기만 하면 error가 없는 것으로 판단하지만 e(x)가 있는데 e(x)도 g(x)로 나누어 떨어지면 error detection을 하지 못하는 문제가 있는 것이다.
  • In a cyclic code, those e(x) errors that are divisible by g(x) are not caught
• CRC는 error detection을 잘하기는 하지만 완벽하지는 않다.
  • 언제?
  • 원래의 codeword(c(x))를 g(x)로 나누는데 error(e(x))가 있으면 error term 때문에 나머지가 나오지 않아야 하는데 e(x)도 g(x)로 나누어지는 경우 즉, 나머지값이 안 만들어지는 그러한 패턴이 탔다면 이런 error는 detect 하지 못하기 때문에 완벽하지 않다.

 

Error Detection

error detection는 generator에 따라 달라진다.

• Single-bit error
  • If the generator has more than one term and the coefficient of x⁰ is 1, all single errors can be caught.
  • 마지막 bit가 1인 경우 모든 single bit error는 detect 가능
• Two isolated single-bit error
  • If a generator cannot divide x^t + 1 (t between 0 and n – 1), then all isolated double errors can be detected
  • 0부터 n-1이 아니라 2부터 n-1아닌가?

Example 10.8

• Which of the following g(x) values guarantees that a single-bit error is caught? For each case, what is the error that cannot be caught?

​ a. x + 1 b. x³ c. 1

Solution

a. No xⁱ can be divisible by x + 1. Any single-bit error can be caught.

• 어떠한 single bit error도 detect 할 수 있다.
  • 마지막 bit가 1이기 때문에
  • 어떠한 xi도 x+1로 나누어지지 않기 때문에

b. If i is equal to or greater than 3, xⁱ is divisible by g(x). All single-bit errors in positions 1 to 3 are caught.

• 즉 x⁴ 부터는 x³으로 나누어지기 때문에 3 이상의 i의 경우 single bit error detection을 못한다.

c. All values of i make xⁱ divisible by g(x). No single-bit error can be caught. This g(x) is useless.

• 어떠한 single bit error도 detect 하지 못한다.
  • 무조건 다 나누어 떨어지기 때문에

 

Example 10.9

• Find the status of the following generators related to two isolated, single-bit errors.

a. x + 1

b. x⁴ + 1

c. x⁷ + x⁶+ 1

d. x¹⁵ + x¹⁴ + 1

Solution

a. This is a very poor choice for a generator. Any two errors next to each other cannot be detected.

• 두 개의 error가 바로 이웃해 있다면 이 generator (x+1)로 나누면 나머지 값이 나오지 않기 때문에 연속적인 single bit error는 detect 하지 못하기 때문에 그렇게 좋은 generator는 아니다.

b. This generator cannot detect two errors that are four positions apart.

• 10001: error가 있고 또 세 개가 떨어져서 error가 있는 경우는 divisible 하기 때문에 이런 경우는 error가 있어도 나머지값이 안 떨어지기 때문에 이 경우의 error detection을 하지 못한다.

c. This is a good choice for this purpose.

d. This polynomial cannot divide x^t + 1 if t is less than 32,768. A codeword with two isolated errors up to 32,768 bits apart can be detected by this generator.

이를 통해 어떤 generator가 a나 b와 같이 clear하게 인수분해가 되지 않는 함수들에 대해서는 two isolated single bit error detection에 유리하다는 것이다.

 

Error Detection

• Odd numbers of errors
  • A generator that contains a factor of x + 1 can detect all odd-numbered errors
• Burst errors
  • L = burst size
  ❏ All burst errors with L ≤ r will be detected.
  • 1 – (1/2)^r–1 -> 이러한 확률로 burst error detection 할 수 있다는 것.
  • ❏ All burst errors with L > r + 1 will be detected with probability
  • 1 – (1/2)^r : burst size가 더 커지면 이러한 확률로 detect 할 수 있음 (r=2이면 3/4)
• ❏ All burst errors with L = r + 1 will be detected with probability

'A'는 0x41(100 0001), 'a'는 0x61(110 0001)

 

Example 10.10

• Find the suitability of the following generators in relation to burst errors of different lengths.
• a. x⁶ + 1

b. x¹⁸ + x⁷ + x + 1

c. x³² + x²³ + x⁷ + 1

Solution

a. This generator can detect all burst errors with a length less than or equal to 6 bits; 3 out of 100 burst errors with length 7 will slip by; 16 out of 1000 burst errors of length 8 or more will slip by.

• divisor: 7bit
• redundancy: 6bit
• 6bit보다 작거나 같은 length의 burst error는 모두 detect 가능

b. This generator can detect all burst errors with a length less than or equal to 18 bits; 8 out of 1 million burst errors with length 19 will slip by; 4 out of 1 million burst errors of length 20 or more will slip by.

• redundancy: 18bit
• devisor 19bit
• 18보다 작은 영역까지는 100% detect
• 19 이상부터는 확률로

c. This generator can detect all burst errors with a length less than or equal to 32 bits; 5 out of 10 billion burst errors with length 33 will slip by; 3 out of 10 billion burst errors of length 34 or more will slip by.

• divisor: 33bit
• redundancy: 32bit

 

tradeoff: redundancy and error detection probability and degree

• 차수를 높이면 높일 수록 error를 detection할 확률이 올라가지만 매 dataword 마다 상당 수의 redundancy를 붙여야 하는 문제가 있다.

 

Summary and Standard Polynomials

• A good polynomial generator needs to have the following characteristics:
  1. It should have at least two terms.
  2. The coefficient of the term x⁰ should be 1.
     • because of single bit error
  3. It should not divide x^t + 1, for t between 2 and n − 1.
     • (떨어져 있는 single bit error에 대해서) 나눠지기 때문에 error detect가 안 되기 때문에
  4. It should have the factor x + 1.
     • all odd number에 대한 detection

CRC-8이 뜻하는 것은 polynomial 형태에서 최고 차항의 계수가 8이라는 것이다. 따라서 divisor는 9bit이다.

 

10.4 Checksum

• Tendency is to replace the checksum with a CRC
• Not as strong as CRC in error-checking capability
  • 그러나 CRC보다 연산은 간단하긴 해서 TCP와 같은 곳에 쓰인다.
• One’s complement addition arithmetic
  • We can represent unsigned numbers between 0 and 2ⁿ – 1 using only n bits
  • If the number has more than n bits, the extra leftmost bits need to be added to the n rightmost bits (wrapping)
  • A negative number can be represented by inverting all bits. It is the same as subtracting the number from 2ⁿ – 1Checksum can only detect

 

Example 10.13: Checksum

• The sender initializes the checksum to 0 and adds all data items and the checksum.
• However, 36 cannot be expressed in 4 bits.
• The extra two bits(맨 앞쪽의) are wrapped and added with the sum to create the wrapped sum value 6.
• The sum is then complemented, resulting in the checksum value 9 (15 − 6 = 9) 1.

그러면 sender는 checksum까지 같이 묶어서 데이터를 보내면 reciever site에서는 이 data를 전부다 add해서 똑같은 과정을 거쳐 최종 값이 0으로 떨어지면 error가 없는 것으로 판단하는 것이다.

 

Internet Checksum

인터넷에서는 16bit의 checksum을 많이 쓴다.

10.5 forward error correction

Hamming Distance for Error Correction

• To guarantee correction of up to t errors in all cases, the minimum Hamming distance in a block code must be d_min = 2t + 1
  • t: 몇 개까지의 error을 correction할 것인가.

작은 오차의 오류들이 원상태로 들어오도록 할 수 있지만 두 영역(code와 code사이의 h.distance)이 너무 가까워서 원이 겹쳐지면 error가 어디껀지 모르기 때문에 겹쳐지지 않기 위한 최소 거리를 정한 것이다.

 

Using XOR

• Another recommendation is to use the property of the exclusive OR operation as shown below.
  • 
  • Pi가 중간에 날라가더라도 나머지 P값들과 Redundancy R값을 모두 XOR을 하면 Pi값을 알아낼 수 있다.
  • 그래서 data chunk 끼리의 XOR 연산으로 R값을 만들어 같이 보냄으로써 loss를 해결하는 방법이다.
• This means

Chunk Interleaving

• We cannot afford to let all the chunks belonging to the same packet be missing;
  • however, we can afford to let one chunk be missing in each packet.

전달을 하다가 한 packet(위 그림에서 packet 3)이 lost가 된다고 가정하자.

그러면 receiver에서 왔던 packet을 풀어서 봤을 때 하나의 packet의 정보가 다 날아가는 것이 아니라 pakcet 마다의 error가 하나씩 생기는 것으로 바뀌어 error가 분산되도록 할 수 있다.

오디오나 라디오 같은 multi media 같은 경우는 저렇게 다 날라가는 것보다 중간에 자그마한 손실이 생긴 경우에는 귀나 눈으로 이를 인지하지 못하는 경우가 많다. 그래서 오히려 저렇게 error를 분산하면 조금의 차이밖에 나지 않아서 오디오, 비디오 통신의 경우 유리한 면이 많아서 쓰고 있는 방법 중에 하나이다..

 

Compounding High-and Low Resolution Packets

해상도가 높은 비디오의 정보를 P1, P2 ,... 로 보내는데 P1에서 P2로 보낼 때 P1에서 low resolution을 같이 실어서 보내준다.(그림에서 빨간 화살표)

그런데 만약 중간에 P2가 날라가 버렸다고 하면 frame덩어리를 전부 잃어버린 것이 되는데 이 방법으로 아까 low resolution을 넣어준 P3에서 low resolution 정보를 보내줘서 그것으로 대치하면 frame이 아예 날아간 것보다는 더 좋은 화질을 제공할 수 있게 되는 것이다.(lost of frame에도 불구하고)

화질이 날라간 것보다는 좋은 효과를 보여줌

• 물론 high만 보내는 것이 아니라 low resolution을 같이 실어 보내줘야 한다는 것의 부담은 있음

 

Q&A

잘 알다시피 ASCII는 현재 컴퓨터에서 사용하고 있는 대표적인 부호화 표준입니다.

0 (0x00) 부터 127 (0x7F) 까지 128개의 코드로 다양한 문자와 기호를 표시합니다.

ASCII는 7 bits로 표현되며, 보통 1 byte(8 bits)에서 MSB는 parity check와 같은 에러

체크를 위해 사용되고 나머지 7 bits는 ASCII 코드를 표현합니다.

학생들이 이 코드를 다 기억할 필요는 없지만, 숫자는 '0' 부터 0x30 (011 0000)으로 시작되고

'A'는 0x41(100 0001), 'a'는 0x61(110 0001)으로 시작된다는 것을 기억하면 매우 유용합니다.

즉, '0'은 0x30, '1'은 0x31, '2'은 0x32..., 'A'는 0x41, 'B'는 0x42, 'C'는 0x43...,

'a'는 0x61, 'b'는 0x62, 'c'는 0x63... 이것을 기억하면 관련된 프로그램을 할 때에도 유용합니다.

'G'는 7번째 대문자이므로 0x47 (100 0111)이고, 'D'는 0x44 (100 0100) 입니다. G를 전송했는데

D가 수신되었다는 말은 2 bits에 오류가 생긴 것이니 burst error라고 할 수 있습니다.

'H'는 0x48 (100 1000), 'L'은 0x4C (100 1100)이므로, H를 보냈는데 L이 수신 되었다면 1 bit

오류가 생긴 것이니 single bit error에 해당됩니다.

다시 한번 이야기 하면.... 대부분의 컴퓨터와 통신 분야에서 사용되는 ASCII 코드를 외울 필요는

없지만, 숫자와 영문 대문자, 소문자가 0x30, 0x41, 0x61로 시작한다는 것은 꼭 기억했으면

좋겠습니다.

 

정답은 “checksum+data= all 1”, 즉 -0 입니다.

One’s complement arithmetic에는 두가지 ‘0’, 즉 (-0, +0)이 있고, 둘은 보수 관계입니다. (교과서 279 page 참고)

positive zero +0은 0000 (all m bits set 0), negative zero -0은 1111 (all bits set 1) 에러가 없이 수신되면 checksum과 data의 합은 negative zero (1111)가 되고,

complement를 취하면 positive zero (0000)가 됩니다.