컴퓨터 네트워크를 공부하면서 정리를 한 내용들 입니다.

-참고 K-mooc 부산 대학교 유영환 교수님 : 컴퓨터 네트워크 강의

CRC Principle : Receiver

CRC Principle: Sender 관련 포스트

이전 포스트에서는 Sender 측에서 CRC를 추가한 데이터를 보냈습니다.

이번에는 이 데이터를 전달 받은 receiver는 이제 어떻게 하는지 살펴봅니다.

그림의 오른쪽을 예로 봅니다.

For Example

101110011이라고 되어 있는 데이터를 서로 약속 하고 있는 1001(G)로 나눕니다.

쭉 계산을 하고나면 나머지가 000이 나온다는 것을 알 수 있습니다.

이런 경우는 bit가 프레임이 제대로 전송 되었다고 하며,

이 중 1 bit라도 바뀌게 되면 나머지가 0이 나오지 않으므로

해당 프레임에는 문제가 있다고 판단 할 수 있습니다.

그래서 이 CRC 기술은 매우 간단하면서도 강력하기 때문에

이더넷이나 와이파이 같은데 널리 쓰이고 있습니다.

그러나 CRC는 에러를 감지할 수는 있지만,

어떤 bit가 바뀌었는지는 알 수가 없습니다.

Error Correction

그래서 에러를 실제로 수정 할 수 있는 방법이 있지 않을까 고민을 했고

그 결과 나온 기술을 통틀어서 FEC(Forward error correction)라고 하거나

channel coding 기술을 써서 FEC 서비스를 제공한다고 말을 합니다.

FEC 기술에서는 다 block code라는 것을 쓰게 되는데

이 코드에 사용하는 몇 가지 공통적인 용어들이 있습니다.

For example

일단 예를 들어서 k라는 길이의 데이터를 보내고자 합니다.

여기에 Detection이나 Correction을 위해 redundant한 데이터를 붙여,

sender가 전송하는 데이터를 코드워드(codeword) 라고 합니다.

코드워드의 길이를 n 이라고 할 때,

redundancy는 (n-k)/k

즉, 전체 내가 실제 k bit의 데이터를 보내기 위해서는

n-k라는 길이의 redundant한 데이터를 붙여야 된다는 뜻 입니다.

그래서 전체 code rate이라는 것은 k/n으로 볼 수 있는데

예를 들어 1 bit의 데이터를 보내기 위해서

1 bit의 부가 정보를 붙여서 보내야 된다면 code rate는 1/2이 됩니다.

code rate의 값이 작으면 작을 수록,

redundant한 데이터가 많이 들어가고 그 만큼 데이터를 받았을 때

수정 해 낼 수 있는 가능성은 높아지게 됩니다.

그러나 그만큼 오버헤드가 커지기 때문에 그런 부분을 잘 고려해야 합니다.

FEC : Hamming Code

FEC 기술 중에서 또 많이 쓰이는 기술이 hamming code라는 기술입니다.

예를 들어 그림에서와 같은 시스템을 가정해봅시다.

k라는 메시지의 길이는 2 bit, n라는 물리적으로 전송해야 되는 bit는 5인

Code rate는 2/5가 됩니다.

5 bit 중에서 2 bit만 유효한 데이터이고,

나머지 3 bit는 redundant한 데이터라는 뜻입니다.

보내려고 하는 데이터가 실제로 2 bit씩 전송 한다면 경우는 4가지 입니다.

`00`을 전송 해야 될 때 `00`을 전송 하는게 아니라 `00000` 을 전송 하고

`01`을 전송 하려고 할 때는 `01`만 전송 하는게 아니라 `00111` 을 전송 하고

`10`을 전송 하려고 할때, `11`을 전송 하려고 할 때 각각 표의 워드코드를 보낸다는 겁니다.

그러면 어떤 경우가 생길 수 있냐 하면 receiver가 어떤 패턴을 받았는데

받은게 00100일 때, 00100은 이 워드코드에 없기 때문에 잘못된 데이터입니다.

그러면 여기서 이 00100을 유효한 워드코드 네 가지 하고

각 워드코드들과 비교해서 bit의 개수가 얼마나 차이가 나는지 확인합니다.

FEC가 에러를 수정한다고 해서

항상 정확하게 수정하는 것은 아니고 확률적으로 수정하는데

이 중에서 원래 어떤 데이터였을 확률이 가장 높은가를 생각 해 보는 겁니다.

그러므로 4가지 코드 중 가장 가까운 숫자인 00000로 수정을 하게 됩니다.

이렇게 수정된 코드 자체도 물론 틀렸을 수 있습니다.

그 경우 상위 계층인 네트워크 계층으로 올라 갔을 때 checksum에서 걸리게 됩니다.

hamming distance : 두 개의 코드워드 사이 bit의 차이

FEC : Hamming Code(2)

5 bit를 보냈을 때, 5 bit로 표현 할 수 있는 코드워드는 2의 5승으로 32가지 입니다.

32가지 중에 어떻게 해서 네 개의 코드워드를 선택 했느냐 살펴 보면

네 개의 코드워드 사이에 `hamming distance를 비교 해 보면

최소 3의 distance가 있다는 겁니다.

distance의 차이가 1씩 난다면 에러가 생긴건지 생기지 않은 건지

알기가 어렵기 때문에 서로간의 hamming distance가 가장 먼 4가지를 골라낸 겁니다.

만약 1 bit가 바뀌더라도 2 bit의 차이가 나니까

에러를 수정 할 때는 “가장 가까운 코드워드가 sender에서 전송 되었던 코드일 것이다.”

2 bit 에러가 발생하면 detection까지는 할 수 있게 됩니다.