[네트워크] 오류 제어 정리: 해밍 코드, 패리티 검사, CRC, ARQ

네트워크 통신 오류

네트워크에서 데이터를 전송할 때, 수신 측이 받은 데이터는 송신 측이 보낸 데이터와 같아야 한다.

 

하지만 실제 통신 과정에서는 다양한 이유로 오류가 발생할 수 있다. 전기적 잡음, 신호 간섭, 장비 문제, 전송 매체의 상태 등으로 인해 비트 값이 바뀌거나 데이터 일부가 손상될 수 있다.

 

예를 들어 송신 측이 다음 데이터를 보냈다고 하자.

10110010

 

수신 측이 다음처럼 받았다면 오류가 발생한 것이다.

10100010

 

중간의 1 하나가 0으로 바뀌었다.

신뢰할 수 있는 통신을 위해서는 이런 오류를 검출하고, 가능한 경우 수정할 수 있어야 한다.

 

네트워크 통신 오류의 종류

네트워크 통신 오류는 비트가 얼마나, 어떤 형태로 바뀌었는지에 따라 나눌 수 있다.

 

대표적으로 다음 세 가지가 있다.

단일 비트 오류
다중 비트 오류
집단 오류

 

단일 비트 오류

단일 비트 오류(single-bit error)는 데이터 단위 중 하나의 비트만 바뀌는 오류이다.

 

예를 들어 다음과 같은 데이터가 전송되었다고 하자.

전송 데이터: 10110010
수신 데이터: 10100010

 

비트 하나만 바뀌었다.

 

단일 비트 오류는 하나의 비트만 변경된 경우이다.

다중 비트 오류

다중 비트 오류(multiple-bit error)는 데이터 단위 중 두 개 이상의 비트가 바뀌는 오류이다.

 

이때 바뀐 비트들이 반드시 연속되어 있을 필요는 없다.

전송 데이터: 10110010
수신 데이터: 00110100

 

여러 위치의 비트가 바뀌었다.

 

다중 비트 오류는 단일 비트 오류보다 검출하기 어렵고, 수정도 더 복잡하다.

집단 오류

집단 오류(burst error)는 두 개 이상의 연속된 비트가 바뀌는 오류이다.

 

예를 들어 다음과 같다.

전송 데이터: 10110010
수신 데이터: 10000010

 

연속된 여러 비트가 한꺼번에 손상되었다.

 

집단 오류는 네트워크 통신에서 자주 문제 될 수 있다. 잡음이나 간섭이 일정 시간 동안 지속되면 연속된 비트들이 함께 손상될 수 있기 때문이다.

오류 제어

오류 제어는 전송 과정에서 발생한 오류를 검출하거나 수정하기 위한 방법이다.

오류 제어는 크게 두 가지로 나눌 수 있다.

전진 오류 수정
후진 오류 수정

---

전진 오류 수정

전진 오류 수정(FEC, Forward Error Correction)은 수신 측이 오류를 발견했을 때, 송신 측에 다시 요청하지 않고 스스로 오류를 수정하는 방식이다.

이를 위해 송신 측은 원래 데이터에 오류 수정에 필요한 추가 정보를 함께 보낸다.

수신 측은 이 정보를 이용해 오류를 검출하고 가능한 경우 직접 수정한다.

 

대표적인 예로 해밍 코드가 있다.

 

전진 오류 수정은 재전송이 어렵거나 지연이 큰 환경에서 유용하다.
다만 오류 수정을 위한 추가 정보를 함께 보내야 하므로 전송량이 늘어날 수 있다.

 

해밍 코드

해밍 코드(Hamming Code)는 전진 오류 수정 방식의 대표적인 예이다.

 

전진 오류 수정은 수신 측이 오류를 발견했을 때 송신 측에게 다시 보내달라고 요청하지 않고, 자신이 직접 오류를 수정하는 방식이다.

 

해밍 코드는 데이터 비트 사이에 여러 개의 패리티 비트를 끼워 넣어 오류가 발생한 위치를 찾아낸다.

 

패리티 비트는 오류 검출을 위해 추가하는 비트이다.  아래에서 더 이야기하겠다.

일반 패리티 검사는 오류가 있는지 정도만 알 수 있지만, 해밍 코드는 어느 위치의 비트가 잘못되었는지도 찾을 수 있다.

해밍 코드의 기본 아이디어

해밍 코드는 데이터 비트에 패리티 비트를 추가한다.

 

이때 패리티 비트는 아무 위치에나 넣지 않는다.  

보통 2의 거듭제곱 위치에 배치한다.

 

예를 들어 7비트 해밍 코드를 만든다고 하면, 각 위치는 다음처럼 볼 수 있다.

위치:   1   2   3   4   5   6   7
역할:   P1  P2  D1  P4  D2  D3  D4

 

P는 패리티 비트이고, D는 실제 데이터 비트이다.

 

1번, 2번, 4번 위치에는 패리티 비트가 들어간다.

나머지 3번, 5번, 6번, 7번 위치에는 실제 데이터 비트가 들어간다.

 

왜 1, 2, 4번 위치에 패리티 비트를 둘까?

해밍 코드는 오류가 발생한 위치를 이진수로 찾아내는 방식이다.

 

각 패리티 비트는 특정 위치의 비트들을 검사한다.

 

7비트 해밍 코드에서 각 패리티 비트가 검사하는 위치는 다음과 같다.

P1: 1, 3, 5, 7번 위치 검사
P2: 2, 3, 6, 7번 위치 검사
P4: 4, 5, 6, 7번 위치 검사


P1은 2진수에서 1의 자리가 1인 위치를 검사한다.
P2는 2진수에서 2의 자리가 1인 위치를 검사한다.
P4는 2진수에서 4의 자리가 1인 위치를 검사한다.

 

어떤 비트에 오류가 생기면, 관련된 패리티 검사 결과가 틀어진다.

그 틀어진 결과들을 모으면 오류 위치를 알 수 있다.

예시

데이터 비트가 다음과 같다고 하자.

D1 D2 D3 D4 = 1 0 1 1

 

이 데이터를 해밍 코드에 배치하면 다음과 같다.

위치:   1   2   3   4   5   6   7
역할:   P1  P2  D1  P4  D2  D3  D4
값:     P1  P2  1   P4  0   1   1

 

이제 패리티 비트를 계산한다.

여기서는 짝수 패리티를 사용한다고 하자.
짝수 패리티는 검사 대상 비트들의 1의 개수가 짝수가 되도록 패리티 비트를 정하는 방식이다.

 

P1 계산

P1은 1, 3, 5, 7번 위치를 검사한다.

1번: P1
3번: 1
5번: 0
7번: 1

 

3번, 5번, 7번 위치의 값은 1, 0, 1이다.
1의 개수는 2개이다.

 

이미 짝수이므로 P1은 0이 된다.

 

P2 계산

P2는 2, 3, 6, 7번 위치를 검사한다.

2번: P2
3번: 1
6번: 1
7번: 1

 

3번, 6번, 7번 위치의 값은 1, 1, 1이다.
1의 개수는 3개이다.

 

짝수로 만들기 위해 P2는 1이 된다.

 

P4 계산

P4는 4, 5, 6, 7번 위치를 검사한다.

4번: P4
5번: 0
6번: 1
7번: 1

 

5번, 6번, 7번 위치의 값은 0, 1, 1이다.
1의 개수는 2개이다.

 

이미 짝수이므로 P4는 0이 된다.

 

따라서 최종 해밍 코드는 다음과 같다.

위치:   1  2  3  4  5  6  7
값:     0  1  1  0  0  1  1

해밍 코드 = 0110011

 

오류 검출과 수정에도 수신 측이 다시 패리티 검사를 하여 검사 결과인 이진수를 10진수로 바꾼다.

바꾼 10진수 위치에 오류가 있다는 뜻이다.

 

해밍 코드의 장점과 한계

해밍 코드는 오류가 발생한 위치를 찾아 직접 수정할 수 있다.

그래서 송신 측에 재전송을 요청하지 않아도 된다.

 

하지만 기본적인 해밍 코드는 보통 1비트 오류 수정에 강하다.

여러 비트가 동시에 오류가 나면 정확히 수정하기 어렵다.

 

---

후진 오류 수정

후진 오류 수정(BEC, Backward Error Correction)은 수신 측이 오류를 검출한 뒤, 송신 측에게 다시 보내달라고 요청하는 방식이다.

수신 측이 오류를 발견하면 송신 측에 오류 발생 사실을 알리고, 송신 측은 해당 데이터를 재전송한다.

 

대표적인 방식이 ARQ이다.

 

후진 오류 수정은 오류 수정 정보를 많이 붙이지 않아도 되지만, 재전송이 필요하므로 지연이 발생할 수 있다.

패리티 비트 검사

패리티 비트 검사(parity check)는 오류를 검출하기 위한 가장 단순한 방법 중 하나이다.

전송할 데이터에 패리티 비트 하나를 추가해, 전체 1의 개수가 홀수인지 짝수인지 맞추는 방식이다.

 

패리티 방식에는 두 가지가 있다.

짝수 패리티
홀수 패리티

 

짝수 패리티

짝수 패리티는 전체 1의 개수가 짝수가 되도록 패리티 비트를 붙인다.

예를 들어 전송할 데이터가 다음과 같다고 하자.

1011001

 

이 데이터에는 1이 4개 있다.

 

이미 1의 개수가 짝수이므로, 짝수 패리티에서는 패리티 비트로 0을 붙인다.

10110010

 

전체 1의 개수는 여전히 4개이다.

 

1의 개수가 홀수이면 전체 1의 개수를 짝수로 만들어야 하므로 패리티 비트 1을 붙인다.

 

수신 측은 받은 데이터의 1의 개수가 짝수인지 확인한다.
짝수가 아니면 오류가 발생했다고 판단한다.

홀수 패리티

홀수 패리티는 전체 1의 개수가 홀수가 되도록 패리티 비트를 붙인다.

 

예를 들어 전송할 데이터가 다음과 같다고 하자.

1011001

 

1이 4개이다.

 

홀수 패리티에서는 전체 1의 개수를 홀수로 만들어야 하므로 패리티 비트 1을 붙인다.

10110011

 

전체 1의 개수는 5개가 된다.

수신 측은 받은 데이터의 1의 개수가 홀수인지 확인한다.
홀수가 아니면 오류가 발생했다고 판단한다.

패리티 검사의 한계

패리티 검사는 단순하지만 한계가 있다.

대표적으로 2비트 오류를 검출하기 어렵다.

 

짝수 패리티를 사용하는 상황을 생각해보자.

전송 데이터의 1의 개수가 짝수였는데, 전송 중 비트 두 개가 동시에 바뀌면 전체 1의 개수가 다시 짝수로 유지될 수 있다.

 

수신 측은 1의 개수가 짝수이므로 정상이라고 판단할 수 있다.

패리티 검사는 간단한 오류 검출에는 사용할 수 있지만, 복잡한 오류를 모두 잡아내지는 못한다.

블록합 검사 방식

패리티 검사의 한계를 보완하기 위해 여러 비트를 블록 형태로 묶어 검사할 수 있다.

가로 방향과 세로 방향에 패리티를 붙이는 방식이다.

 

예를 들어 데이터를 표처럼 배치하고, 가로 방향에는 짝수 패리티를 적용하고 세로 방향에는 홀수 패리티를 적용할 수 있다.

 

이렇게 하면 단순한 1차원 패리티보다 오류 위치를 더 잘 파악할 수 있다.

특정 행과 특정 열에서 오류가 발견되면, 그 교차 지점의 비트가 잘못되었을 가능성이 크다.

 

다만 이 방식도 모든 오류를 완벽하게 검출하거나 수정할 수 있는 것은 아니다.
그래도 단순 패리티보다 오류 검출 능력이 좋아진다.

 

순환 중복 검사

순환 중복 검사(CRC, Cyclic Redundancy Check)는 네트워크에서 널리 사용되는 오류 검출 방식이다.

CRC는 전송할 데이터에 대해 계산한 체크값을 함께 전송한다.
수신 측은 받은 데이터로 다시 CRC 값을 계산하고, 전송된 CRC 값과 비교한다.

 

값이 같으면 전송 중 오류가 없다고 판단한다.
값이 다르면 오류가 발생했다고 판단한다.

 

CRC는 패리티 검사보다 더 강력한 오류 검출 능력을 가진다.

 

이더넷 같은 네트워크 기술에서도 CRC가 사용된다.

 

CRC는 데이터를 특정한 값으로 나누는 연산을 바탕으로 체크값을 만든다.
이 체크값을 데이터 뒤에 붙여 보내고, 수신 측은 같은 방식으로 계산해 오류 여부를 판단한다.

 

ARQ

ARQ(Automatic Repeat Request)는 오류가 발생했을 때 데이터를 재전송하여 오류를 수정하는 방식이다.

 

수신 측은 받은 프레임에 오류가 있는지 확인한다.
정상적으로 받았다면 ACK를 보낸다.

 

오류가 발생했다면 NAK를 보내거나, ACK가 오지 않아 송신 측에서 타임아웃이 발생한다.

 

송신 측은 오류가 발생했다고 판단한 프레임을 다시 전송한다.

 

대표적인 ARQ 방식에는 다음이 있다.

Stop-and-Wait ARQ
Go-Back-N ARQ
Selective Repeat ARQ
Adaptive ARQ
Hybrid ARQ

 

 

Stop-and-Wait ARQ

Stop-and-Wait ARQ는 프레임 하나를 보내고, 그에 대한 응답을 받은 뒤 다음 프레임을 보내는 방식이다.

 

송신 측은 1개의 프레임을 수신 측으로 전송한다.

수신 측은 프레임에 오류가 있는지 확인한다.

 

정상적으로 받았다면 ACK를 보낸다.
오류가 있다면 NAK를 보내거나 ACK를 보내지 않는다.

 

송신 측은 ACK를 받으면 다음 프레임을 보낸다.
NAK를 받거나 타임아웃이 발생하면 같은 프레임을 다시 보낸다.

 

Stop-and-Wait ARQ는 구조가 단순하다.

 

하지만 전송 효율이 낮다.
ACK를 기다리는 동안 송신 측은 다음 프레임을 보내지 못한다.

 

Go-Back-N ARQ

Go-Back-N ARQ는 Stop-and-Wait ARQ의 낮은 전송 효율을 보완하기 위한 방식이다.

 

송신 측은 여러 프레임을 연속해서 보낼 수 있다.

이때 송신 측은 윈도우 크기만큼의 프레임에 순서 번호를 부여하고, 일정 범위 안에서 연속 전송한다.

 

전송 중 특정 프레임에서 오류가 발생하면, 해당 프레임부터 뒤의 프레임들을 다시 전송한다.

 

예를 들어 프레임 3에서 오류가 발생했다고 하자.

프레임 1 정상
프레임 2 정상
프레임 3 오류
프레임 4 이미 보냈지만 다시 전송 대상

 

Go-Back-N ARQ에서는 오류가 발생한 지점으로 돌아가 그 이후 프레임을 다시 보낸다.

 

이 방식은 슬라이딩 윈도우 방식과 관련이 있다.
송신 측은 일정 범위의 프레임을 한 번에 보낼 수 있고, ACK가 오면 윈도우를 다음 범위로 이동시킨다.

 

Selective Repeat ARQ

Selective Repeat ARQ는 오류가 발생한 프레임만 선택적으로 재전송하는 방식이다.

Go-Back-N ARQ는 오류가 발생한 프레임 이후의 프레임까지 모두 다시 보낸다.

Selective Repeat ARQ는 정상적으로 받은 프레임은 유지하고, 오류가 발생한 프레임만 다시 요청한다.

 

이 방식은 불필요한 재전송을 줄일 수 있다.

 

하지만 송신 측과 수신 측 모두 더 큰 버퍼가 필요하다.
수신 측은 순서가 맞지 않게 도착한 프레임도 임시로 저장해야 하기 때문이다.

 

Adaptive ARQ

Adaptive ARQ는 통신 회선의 상태에 따라 프레임 길이를 동적으로 조절하는 방식이다.

 

에러 발생률이 낮은 환경에서는 더 긴 프레임을 보내 전송 효율을 높일 수 있다.

에러 발생률이 높은 환경에서는 짧은 프레임을 보내 오류 발생 시 재전송 부담을 줄일 수 있다.

 

Adaptive ARQ는 통신 환경에 맞게 전송 방식을 조절할 수 있다는 장점이 있다.

하지만 회선 상태를 계속 감지하고 프레임 길이를 조절해야 하므로 구현이 어렵다.

 

Hybrid ARQ

Hybrid ARQ(H-ARQ)는 전진 오류 수정과 후진 오류 수정을 함께 사용하는 방식이다.

 

전진 오류 수정은 수신 측이 직접 오류를 수정할 수 있게 추가 정보를 함께 보내는 방식이다.

후진 오류 수정은 오류가 발생했을 때 송신 측에게 재전송을 요청하는 방식이다.

 

Hybrid ARQ는 두 방식을 절충한다.

 

평소에는 FEC 방식으로 오류를 수정하려고 한다.
오류가 너무 커서 수신 측에서 직접 수정할 수 없으면 ARQ 방식으로 재전송을 요청한다.

 

Hybrid ARQ는 이동통신 같은 환경에서 많이 사용된다.

오류를 어느 정도는 수신 측에서 직접 고치고, 복구할 수 없는 경우에만 재전송을 요청하기 때문에 효율성과 신뢰성을 함께 얻을 수 있다.

 

오류 검출과 오류 수정 정리

네트워크 오류 제어 방식은 크게 오류 검출과 오류 수정으로 나눌 수 있다.

 

오류 검출은 오류가 발생했는지 확인하는 방식이다.

대표적으로 패리티 검사와 CRC가 있다.

 

오류 수정은 오류가 발생했을 때 이를 복구하는 방식이다.

 

오류 수정은 다시 전진 오류 수정과 후진 오류 수정으로 나눌 수 있다.

오류 검출
패리티 검사
CRC

오류 수정
전진 오류 수정
후진 오류 수정

 

전진 오류 수정은 수신 측이 직접 오류를 수정하는 방식이다.

 

후진 오류 수정은 오류가 발생했을 때 송신 측에게 다시 보내달라고 요청하는 방식이다.

 

ARQ는 후진 오류 수정의 대표적인 방식이다.