Error in Computer Network
네트워크에서 에러란, 보낸 데이터와 받은 데이터가 다른 것을 의미합니다. 2가지 binary 채널 모델이 있습니다. (binary 채널이란, 0과 1의 두가지 symbol만 전송하는 채널을 말합니다.)
Binary Symmetric Channel (BSC)
0을 보냈을 때,
p의 확률로 1이 도착하는 채널을 말합니다. 반대로, 1을 보냈을 때p의 확률로 0이 도착합니다.1-p의 확률로 보내고자 했던 데이터가 도착합니다.
Binary Erasure Channel (BEC)
데이터를 전송할 때,
p의 확률로 데이터가 유실됩니다.1-p의 확률로 보내고자 하는 데이터가 도착합니다.
Error Detection & Recovery
Error Detection
-
Bit Level Error : BSC 처럼 값을 받긴 하지만 에러인지 판별해야 합니다. 데이터를 추가하여 전송하므로써 에러인지 판별하게 됩니다.
-
Packet Level Error : BEC 처럼 데이터가 도착하지 않는 에러입니다.
Error Recovery
-
Retransmission : 수신자 측에서 송신자 측으로 Feekback을 보내고, 이를 기반으로 송신자가 문제가 된 데이터를 재전송합니다.
-
FEC (Foward Error Correction) : 송신자가 데이터 외에 추가 정보를 보내 재전송 없이 추가 정보만으로 수신자가 자체 복구합니다.
Type of Errors
에러에는 2가지가 존재합니다.
- Single Bit Error : 단일 비트만 에러 발생
- Burst Errors : 여러 구간에 걸쳐 부분부분 에러가 발생합니다.
당연히 Burst Errors 가 복구하기 어렵습니다.
Error Detection
k bit 데이터 + (n - k) bit Code-bits 로 구성된 n bit Codeword 를 생성합니다. 이렇게 생성한 Codeword는 legal codeword 와 illegal codeword 로 나뉩니다.
에러가 발생하는 경우는
1. Legal codeword > illegal codeword (Detectable Error)
2. Legal codeword > Legal codeword (Undetectable Error)
1번의 경우 생성될 수 없는 코드가 도착하였기 때문에 에러를 찾을 수 있습니다. 하지만 2번의 경우, codebit 가 에러일 수도 있고 에러가 발생하여 다른 Legal codeword 로 도착하였을 수도 있기 때문에 에러인지 아닌지 파악할 수 없습니다.
Parity Code
데이터에서 1이 홀수개 혹은 짝수개만 등장하도록 추가 1비트를 더한 데이터를 말합니다. Parity Code는 1비트 에러를 감지할 수 있습니다. 보내고자 하는 데이터에서 에러가 발생할 수 있고, Parity Code 에서도 에러가 발생할 수 있습니다.
- Even Parity 예시 : 0010101 > 00101011
- Odd Parity 예시 : 0010101 > 00101010
Hamming Distance
다른 비트의 개수를 의미합니다. 예를 들어
011011
110001 xor
101010
이고 1이 3개이므로 Hamming Distance = 3 입니다. 그럼 codeword에서는 ?? W1, W2, ..., Wn 이 있을 때, 임의의 두 codeword의 Hamming Distance 중 최소값입니다.
예를 들어
| Data Block | Codeword |
|---|---|
| 00 | 00000 |
| 01 | 00111 |
| 10 | 11001 |
| 11 | 11110 |
의 경우, 최소값은 3입니다. 따라서 Hamming Distance = 3 입니다.
그렇다면, Parity Code의 Hamming Distance는 ?? Data Block 에서 1비트만 다르다고 하면, Parity Code도 달라집니다. 즉 최소 2개는 다르기 때문에 이 경우에는 2 입니다.
Hamming Distance & Error Correction
이런 식으로 ,,,legal code를 적당히 떨어지게 배치하면 복구할 수 있는 에러의 범위가 늘어나게 됩니다.
