Chapter 6. Error detection

Error detection

 

어떤 경우든 error가 없을 수는 없고, error는 frame 속 bit의 변화를 말한다.

* frame: 하나 이상의 연속적 bit로 전송되는 데이터

 

1. frame size가 커질수록 -> 에러 없이 도착할 확률(Pf)은 낮아짐

frame size=n bit
Pf = "probability that a frame arrives with no bit errors"
=> n과 Pf는 반비례

 

 

2. single bit error가 발생할 확률(Ps)이 높아질수록 -> 에러 없이 도착활 확률(Pf)은 낮아짐

Pf = (1-Ps)^n

 

=> Ps가 낮아질수록, n이 작아질수록 Pf가 커짐

 

그럼에도 불구하고 error detection code 넣음

Error Detection Process

 

- transmitter: 함수로 redundancy 만들어 보냄

- receiver: 똑같은 함수로 결과값 내어 redundancy와 비교

* redundancy: data를 반영한 값

 

=> 비교해 같지 않으면 error로 판단

 

Types of errors

 

- single bit error: 이론적

: bit 한 개 바뀌었을 때

: 근접한 bit는 영향받지 않음

: 백색소음에 의해 영향받음

 

- burst bit error: 실제 발생

RX가 받았을 때 error 발견 -> "지금까지는 괜찮아. 이제부터는 error 반영해 !"

 

<1Mbps>

: 1초에 10^6bit를 보내면 -> 1bit당 10^-6초 걸림

<1Gbps>

: 1Mbps*(10^3)

-> 1Mbps보다 1000배 더 망가짐

 

3 Error detection techniques

 

Error Detection Process

 

: additional bit를 사용하는 error detection 기술들이다.

-> additional bit는 transmitter가 error detection 목적으로 payload data에 추가해놓음

 

<Parity Check>-L2에서

: Asynchronous에서 1개의 parity bit 넣어 오류 검출

: XOR 연산 사용(하드웨어)

 

예: even parity bit 사용할 때

 

* parity: state of being equal -> 1의 개수가 짝수개인지/홀수개인지에 따라 결정

- even parity bit: data에 다음으로 0/1 중 어떤 값을 넣었을 때 1이 짝수개가 되는지 확인 -> 홀수개이면 error

- odd parity bit: data에 다음으로 0/1 중 어떤 값을 넣었을 때 1이 홀수개가 되는지 -> 짝수개이면 error

=> 짝수개의 bit가 flip되어 오류난다면 검출 불가

 

ex. "data=0101011" even parity 사용해 오류 검출하기

1. 송신자와 수신자가 parity 방식 합의(even/odd parity)

2. 송신자 -> 수신자 : "01010110"(뒤에 parity=0 붙여) 전송

3. 수신자 : 송신자가 보낸 데이터에서 1 개수 count -> even parity 사용하므로 1 개수 짝수이면 no error, 홀수이면 error

 

"2-dimensional parity check"

- error detection: error 검출된 column과 row의 교차점이 error bit라고 본다.

- error correction: 그 error bit를 flip하면 오류 수정한 것이다.

 

(1) If a single bit error occurs

Detection & Correction

 

(1)' 하지만 만약 single bit이 아니라 여러 bit 에서 오류가 생긴다면?

=> Detection & Correction

But, Not 100% accuracy (하나만 detection 가능)

위와 같은 경우 교차 지점인 '0'만 검출

 

(2) If even number of errors in a row only or in a column only occurs

=> Detection & Not Correction

error가 있다고만 알고 어느 것이 정확히 error인지는 모르기 때문

 

(2)' If odd number of errors in a row only or in a column only occurs

=> Detection & Correction

But not 100% accuracy

왼쪽의 경우를 말하는 것이지만,

오른쪽같은 경우 왼쪽이랑 같은 결과를 가져오기 때문에

 

 

(3) If 4 errors forming a rectangle occur

=> Not Detection & Not Correction

 

(3)' If odd number of errors forming multiple rectangles occur

=> Detection & Correction

But, not 100% accuracy

왼쪽의 경우를 말하는 것이지만

오른쪽 경우도 똑같은 결과를 가져오기 때문에

 

<Internet checksum>-L3, L4

: TCP, UDP, IPv4에서 사용되는 error detecting code

: 덧셈 사용(ones complement)

1. 16bit alignment

: checksum이 16bit이기 때문

2. 첫 번째 두 줄을 Ones-complement addition

 

3. Ones-complement operation

: 0을 1로, 1을 0으로 바꿈

 

<예제>

Consider a header that consists of 10 octets, with the checksum in the last two octets:

 

1. 16bit alignment

: 16bit씩 나누기

 

2. ones complement addition

00 01

F2 03

F4 F5

F6 F7

모두 complement addition -> carry 나오면 더해주기 -> 새로운 checksum

 

3. ones complement operation

: bit flip -> 더해서 FFFF 만들기

ex. RX가 flip한 것과 안 한 것 더함(DDF2+220D) -> 합이 FFFF가 됨 -> good

 

 

 

<한계>

two bits between 16 bits are exchanged된 형태일 경우, Internet checksum은 error detection할 수 없다.

쉽게 말해, 위 예제에서 "00 01" 과 "F2 F3" 이 뒤바뀌어도 덧셈 결과는 똑같기 때문에 error인지 알 수 없다는 것이다.

 

<CRC(Cyclic Redundancy Check)>-L2에서

: 곱셈 사용

 

- CRC의 redundancy = "FCS" = F(n-k)

* k = D(k)의 bit수

* n = T(n)의 size

- (FCS bit 수) + 1 = (divisor bit 수)

ex. "Ethernet" (FCS bit 수) = 32  =>  (divisor bit 수) = 33

ex. "HDLC" (FCS bit 수) = 8  =>  (divisor bit 수) = 9

- T(n) = D(k) + FCS

 

"FCS(redundancy)에 무엇을 넣으면 T(n)이 divisor로 나누어떨어질까?"

<No error 인 경우>

RX가 T(n)을 divisor로 나눔 -> 나누어떨어지면 no error

<Error detection 불가능한 경우>

error난 데이터도, 원래의 데이터도 divisor로 나누어 떨어지면 error detection 불가능

 

 

<CRC code가 생성되는 방법>

1. Bit operation using Modulo 2 arithmetic

: carry 없이 binary addition

: XOR 연산과 같음

: 처음에는 (n-k)bit짜리 FCS를 0으로 초기화

 

mod2 사용한 덧셈과 뺼셈 연산은 XOR 연산과 결과가 같음

 

 

<예제>

Q) D = 1010001101, P = 110101 일 때, FCS는?

 

A) P가 6bit이므로 R은 5bit이며, TX와 다음과 같이 계산해 RX에게 전송해준다.

 

RX도 XOR 연산을 해 합이 FFFF가 되면 no error!

 

2. Polynomial using Modulo 2 arithmetic

 

P(6) = 110101  ->  x^5 + x^4 + x^2 + 1
D(10) = 1010001101  ->  x^9 + x^7 + x^3 + x^2 + 1

 

(1) bit를 다항식으로 바꿔 표현

* Divisor의 최고차항과 최저차항은 항상 1 => 1______1 형식 !! -> accuracy 높임

* 각 bit는 다항식의 계수 => 계수가 0인 차수는 없어짐

따라서 다음과 같은 경우에는 항이 5개다.

각 bit는 다항식의 계수

 

divisor P가 6bit면 최고차항이 5차인 다항식이라고 유추할 수 있고, 반대로 최고차항이 5차인 다항식이면 divisor가 6개의 bit로 이루어진다고 유추 가능하다.

 

(2) Shift

 

divisor가 6bit -> FCS 5bit -> 5자리 shift -> x^5 곱해주기 -> 나온 결과를 bit로 다시 변환 -> 뒤에 0으로 채우기 -> TX가 RX로 보냄

 

 

(3) mod 2 division

 

 

(4) 나머지를 FCS에 더함

"원래 frame 찾기"

 

3. Digital Logic

shift + XOR

- (shift register 개수) = (FCS bit 수) = (n-k)

- (XOR gate 개수) = 최고차항 제외한 항 개수

- 계수가 1인 항 앞에 XOR gate 놓기

- sender/receiver 모두에서 똑같이 진행

 

<예제>

 

 

complexity: Parity Check < Internet checksum < Cyclic Redundancy Check(CRC)

robustness: Parity Check < Internet checksum < Cyclic Redundancy Check(CRC)

error: Parity Check > Internet checksum > CRC

 

	Parity Check	Internet checksum	CRC
No error인 경우	Even parity: 1이 짝수개이면 no error Odd parity: 1이 홀수개이면 no error	RX가 flip한 것과 안 한 것 더한 합이 FFFF -> no error	RX가 T(n)을 divisor로 나눔 -> 나누어떨어지면 no error
error detection 불가능 경우	single bit error가 아닌 많은 경우	덧셈 피연산자인 두 16bit가 뒤바뀐 형태로 error 날 경우	error난 데이터도, 원래의 데이터도 divisor로 나누어떨어질 때