[컴퓨터네트워크] 10장 연습문제

- QUESTIONS

Q10-1. How does a single-bit error differ from a burst error?

( 단일 비트 오류와 버스트 오류는 어떻게 다른가? )

A: 단일 비트 오류는 데이터 단위에서 한 비트만 손상, 버스트 오류는 하나 이상의 비트가 손상

 

Q10-2. What is the definition of a linear block code?

( 선형 블록 코드란 무엇인가? )

A: 선형 블록 코드는 임의의 2개의 코드 워드의 배타적 논리합이 다른 코드 워드가 되는 블록 코드

 

Q10-3. In a block code, a dataword is 20 bits and the corresponding codeword is 25 bits. What are the values of k, r, and n according to the definitions in the text? How many redundant bits are added to each dataword?

( 블록 코드에서 데이터워드는 20비트이고 이에 해당하는 코드워드는 25비트이다. 텍스트에 있는 정의에 따라 k, r, n의 값은 무엇인가? 그리고 각 데이터워드에 추가된 중복 비트는 얼마나 되는가? )

A: k = 20, r = 5, n = 20/ 데이터워드에는 5개의 중복 비트(r)가 추가됨

k: k 비트 데이터 워드, + r : rebundancy 비트 = n:코드워드

 

Q10-4. In a codeword, we add two redundant bits to each 8-bit data word. Find the number of

a. valid codewords. b.invalid codewords.

( 코드워드에서 각 8비트 데이터워드에 2개의 중복 비트를 추가하였다. a. 유효 코드워드의 수를 구하라. b. 유효하지 않는 코드워드의 수를 구하라. )

A: k : 8 + r : 2 = 10 : n 

a. 유효 코드워드의 수는 2^10 = 256

b. 유효하지 않는 코드워드의 수는 2^n - 2^k => 2^10 - 2^8 = 1024 - 256 = 768

 

Q10-5. What is the minimum Hamming distance?

( 최소 해밍 거리란 무엇인가? )

A: 최소 해밍 거리는 단어 집합에서 가능한 모든 쌍 사이의 최소 해밍 거리

 

Q10-6. If we want to be able to detect two-bit errors, what should be the minimum Hamming distance?

( 만약 2비트 오류를 검출하기를 원한다면, 최소 해밍 거리는 얼마가 되어야 하는가? )

A: dmin = s + 1 => 2(s) + 1 = 3

 

Q10-7. A category of error detecting (and correcting) code, called the Hamming code, is a code in which dmin = 3. This code can detect up to two errors (or correct one single error). In this code, the values of n, k, and r are related as: n = 2^r − 1 and k = n − r. Find the number of bits in the dataword and the code words if r is 3.

( 해밍 코드(hamming code)라고 불리는 오류 검출(그리고 정정) 코드의 범주는 dmin = 3이다. 이 코드는 두 오류를 검출할 수 있다(또는 하나의 단일 오류를 정정한다). 이 코드에서 n, k, r의 값은 n = 2r − 1과 k = n − r과 관련이 있다. r이 3일 때 데이터워드와 코드워드의 비트 수를 구하라. )

A: n = 2r - 1 => 7, k = n - 3 => 4/ 데이터 워드는 4비트, 코드워드는 7비트/ 두 개의 유효 코드워드 사이의 최소 거리 dmin = 3

     

Q10-8. In CRC, if the dataword is 5 bits and the codeword is 8 bits, how many 0s need to be added to the dataword to make the dividend? What is the size of the remainder? What is the size of the divisor?

( CRC에서 데이터워드가 5비트이고 코드워드가 8비트라면, 피제수를 만들기 위해 추가되는 데이터워드는 얼마나 많은 0이 필요한가? 나머지의 크기는 얼마인가? 제수의 크기는 얼마인가? )

A:k = 5, n = 8/ dividend 크기는 코드워드 크기와 동일, 3개의 0으로 데이터워드를 보강 n  = k + r => 8 = 5 + r

나머지 remainder의 크기는 r = n - k = 3비트/ divisor 는 r + 1

 

Q10-9. In CRC, which of the following generators (divisors) guarantees the detection of a single bit error?

a. 101 b. 100 c.1

( CRC의 다음 생성기(제수) 중 단일 비트 오류 검출을 보장하는 것은? )

A: 맨 오른쪽 비트오 맨 왼쪽 비트가 1이기에 모든 오류 검출 감지 가능/ 맨 오른쪽 비트가 0이기에 생성기로 사용 불가능/ 3비트를 가져야 하는데 1비트만 가지고 있어서 불가능

 

Q10-10. In CRC, which of the following generators (divisors) guarantees the detection of an odd number of errors?

a. 10111 b. 101101 c. 111 d.1101

( CRC의 다음 생성기(제수) 중 홀수 개의 오류 검출을 보장하는 것은? )

A: 홀수개의 오류 검출 보장은 1이 짝수일때 검출 가능 => c, d 1 개수가 짝수 이기에 검출 가능

 

Q10-11. In CRC, we have chosen the generator 1100101. What is the probability of detecting a burst error of length

a. 5? b. 7? c. 10?

( CRC에서 생성기가 1100101을 선택했을 때, 길이의 버스트 오류를 검출할 확률은 무엇인가? )

A: r = 7 - 1 = 6 

a. 오차의 길이 L = 5, L <= r 이기에 버스트 오류 검출 100%

b. 오차의 길이 L = 7 L = r +1을 의미/ 확률 1 - (0.5)^5 로 모든 버스트 에러 검출 가능

c. 오차의 길이 L = 10 , L > r 을 의미/ 확률 1 - (0.5)^6으로 모든 버스트 에러 검출 가능

 

Q10-12. Assume we are sending data items of 16-bit length. If two data items are swapped during transmission, can the traditional checksum detect this error? Explain.

( 16비트 길이의 데이터 아이템을 전송했다고 가정하자. 만약 2개의 데이터 아이템이 전송 도중 바뀌었다 면, 통상적인 검사합은 이 오류를 검출할 수 있는가? 설명하라. )

A: checksum 의 영향을 받지 않으므로 오류를 감지할 수 없음.

 

Q10-13. Can the value of a traditional checksum be all 0s (in binary)? Defend your answer.

( 검사합의 값이 모두 0이 될 수 있는가? 설명하라. )

A: checksum의 값은 데이터 합이 모두 1인 경우 모두 0이 됨

 

Q10-14. Show how the Fletcher algorithm (Figure 10.18) attaches weights to the data items when calculating the checksum.

( 검사합을 계산할 때 Fletcher 알고리즘(그림 10.18)이 어떻게 데이터 항목에 가중치를 부가하는지 보여라)

A:

x

Q10-15. Show how the Adler algorithm (Figure 10.19) attaches weights to the data items when calculating the checksum.

( Adler 알고리즘(그림 10.19)이 검사합을 계산할 때 데이터 항목에 가중치를 부여하는 방법을 보여라. )

A:

x