Error

Type of Errors

• single bit error: 주변 bit에 에러가 나타나지 않고 고립됨

• burst error: 처음과 끝이 에러이며 B의 길이를 가짐

Probability

• $P_b$: 한 bit에 에러가 발생할 확률

• $P_1=(1-P_b)^5$: 한 frame에 bit 에러가 발생하지 않을 확률

  • e.g. ${5 \choose 1}P^1_b(1-P_b)^4$: 1frame 중 1bit가 에러일 확률, $1frame=5bit$

• $P_2$: 에러 감지 알고리즘이 사용되었지마 한 frame에 감지되지 않은 에러가 한개 이상 발생할 확률

• $P_3$: 에러 감지 알고리즘을 사용해 모든 에러를 감지할 확률

Error Detection

1. Parity Check

• even parity: 1의 개수를 짝수로 맞춰 기존 정보와 동일한지 확인

• odd parity: 1의 개수를 홀수로 맞춰 기존 정보와 동일한지 확인

2. Checksum

• one-compliment operation: 0을 1로, 1을 0으로 대체

• one-compliment addition: 두 숫자를 부호없는 이진수로 가정하고 더하는데, 가장 왼쪽 bit에 carry가 발생하면 더한 값에 1을 더함

• e.g. 0001 F203 F4F5 F6F7

  • 0001+F203 = F204, F204+F4F5=E6FA, E6FA+F6F7=DDF2, 15에서 각 값을 뺌=220D

  • 송신측은 0001 F203 F4F5 F6F7 220D를 수신측에 보냄

  • 수신측에서는 에러가 없는지 확인하기 위해 0001+F203+F4F5+F6F7+220D=FFFF인지 확인(아니면 에러)

3. CRC(Cyclic Redundancy Check)

• 가장 흔히 사용되는 강력한 에러 감지 기법

• 송신측에서 데이터를 $X^n$으로 바꾸고 송신자와 수신자간 정해놓은 $P(X)$로 나눔

• 이때 몫 $Q(X)$과 나머지 $R(X)$가 생기는데, 수신측에 원래 데이터와 $R(X)$를 딸려 보냄

• 수신측에서는 받은 데이터를 $P(X)$로 나눠 나머지가 없는지 확인(나머지가 있으면 에러)

• $R(X)$는 $P(X)$의 bit 수로 유효숫자를 맞춤

• e.g. data=1101011011, $P(X)$=1101

  • 1101011011->$X^9+X^8+X^6+X^4+X^3+X^1+1$

  • 1101->$X^3+X^2+1$

  • $(X^9+X^8+X^6+X^4+X^3+X^1+1 )/( X^3+X^2+1)$->$Q(X)=X^6+X, R(X)=1$

  • $R(X)=1$->$R(X)=001$

  • 송신측은 1101011011001을 수신측에 보냄

Error Correction

1. Forward Error Correction

• 송신측이 전송할 프레임에 부가적인 정보를 첨가해 전송하고, 수신측은 이 정보를 이용해 에러를 찾고 정정하는 방식

• 오류가 발생해도 재전송 없이 오류 수정 가능

• 송신측이 한 곳이고 수신측이 여러 곳인 재전송이 어려운 곳에서 사용

2. Backward Error Correction

• 수신측이 에러 발생 데이터에 대한 재전송을 송신측에 요구

3. Block Code Principles

• hamming distance: $d(v_1, v_2)$ , 이진수로 된 $v_1, v_2$ sequence에서 동일하지 않은 bit의 개수

  • e.g. $v_1=1101, v_2=1001 \rightarrow d(v_1, v_2)=1$

• redundancy of code: 얼마만큼의 redundant bit가 추가되었는지에 대한 비율

  • e.g. $k=1, n=3 \rightarrow R=\frac{n-k}{k}=\frac{3-1}{1}=2, 2=2^1=1 bit$, 1bit 에러 정정 가능

• code rate: 전체 bit 중 데이터 bit의 비율, code가 없는 경우 동일한 데이터 전송률로 전송하는데 필요한 추가 대역폭 양을 측정