[데이터 통신]Error Detection and Correction

Type of Errors

1. Single bit errors : 연속저기지 않은 bit 에러

2. Burst bit errors : 일정 범위 내 무더기로 bit에 에러가 발생한 것

Error Detection

오류는 전송 시스템의 설계와 무관하게 발생하는데, 전송 프레임에서 하나 이상의 비트가 변경된다.

비트당 에러 발생율을 같기 때문에 프레임이 길면 길수록 에러가 발생 활 확률이 늘어난다. 이러한 이유로 프레임의 길이를 너무 줄이면 헤더의 길이는 고정이기 때문에 낭비가 발생할 수 있다.

Parity Check

오류검출 방식중 가장 쉬운 방식이며 프레임의 단어 끝에 패리티 비트를 각 단어 끝에 붙인다. 단어의 1의 개수를 세어 짝수냐 홀수냐에 따라 특정 비트를 맨 뒤에 추가하여 보낸다. 짝수 페리티는 동기식 전송에 쓰이고 홀수 페리티는 비동기식 전송에 쓰인다.

매트릭스 모양으로 해서 페리티를 보내도 2개 이상의 오류를 찾지 못한다.

Cyclic Redundancy Check(CRC) - 순환 중복 검사

에러 찾는 방법 중 성능이 좋은 것이다. k-비트 블록 데이터와 n-k개의 FCS를 붙인다. 총 n개의 데이터를 보내는데 정해진 n개의 숫자로 나누어 떨어지면 오류가 없는 것이다.

나누는 수는 최소 n-k+1이상이어야 한다.

보낼 데이터 M : 1010001101

crc 길이 5 : M * 2^5

crc의 M : 101000110100000

divisor : 110101

1 1 0 1 0 1						1	1	0	1	0	1	0	1	1	0
	1	0	1	0	0	0	1	1	0	1	0	0	0	0	0
	1	1	0	1	0	1
		1	1	1	0	1	1
		1	1	0	1	0	1
				1	1	1	0	1	0
				1	1	0	1	0	1
						1	1	1	1	1	0
						1	1	0	1	0	1
								1	0	1	1	0	0
								1	1	0	1	0	1
									1	1	0	0	1	0
									1	1	0	1	0	1
											0	1	1	1	0

진짜 보낼 M : 101000110101110

수신자가 110101로 나누었을 때 나머지가 000000이 나오면 정상적으로 전송된 것이다. 그러나 에러가 있다는 것만 알고 복구를 하지 못한다.

Forward Error Correction

오류가 발생한 것을 알았을 때 수신기는 재 전송을 요청한다. 그러나 특수한 상황에서는 재 전송이 힘들다.

위 방법은 코드 복구를 하는 방법중하나이다.

k비트의 전송 데이터를 FEC 인코더에 넣어 n비트 데이터로 만든다 (n>k) 이후 만들어진 코드워드를 전송하여 수신기는 해당 코드워드를 디코더하여 원래 데이터를 찾는다.

Block Code Principles

오류가 나도 확률적으로 원래 데이터를 유추한다. 원리는 Hamming distance를 이용하였다.

예로 011011과 110001의 d는 3이다.

k가 2이고 n이 5일 때

가 되고 00100데이터를 수신하였다면 가장 거리가 가까운 00000으로 변경된다.

n이 5비트일 때 만들 수 있는 경우의 수는 32가지인데 여기서 4개를 선택할 시 거리가 가장 먼것들로 4개를 정한다.

확률적으로 수정하기 때문에 완벽하지 않다. 복수의 데이터가 변경될시 거리가 같은 경우가 나오며 이때 선택을 해야 한다.->2가지의 경우는 오류를 찾아도 정확한 복구를 못한다.

또한 각각의 차이의 최소가 3이기 때문에 에러 발견은 2개까지 할 수 있다.

블록코드를 설계시 주의할 것

1.주어진 n과 k에 대해 d는 가장 커야한다.

2.인코딩과 복호화가 상대적으로 쉬워야한다.

3.대역폭을 줄이기 위해 n-k가 작아야한다.

4.오류율을 줄이기 위해 n+k가 커야한다.

왼쪽은 추가의 검사 비트가 시스템의 오버헤드를 증가시켜 데이터 비트당 에너지를 감소시켰다.