[데이터통신] 데이터 통신에서 에러 감지하기

 

데이터 통신에서의 오류

 

정보를 주고받을 때 보낸 데이터가 반드시 받는 데이터와 일치한다는 보장은 없다.

어떠한 방식이 되었든, 데이터에 변조가 일어날 가능성이 있다. 데이터 통신에서는 이렇게 데이터가 변경되는 오류에도 얼마만큼 변경되냐에 따라 부르는 이름을 다르게 한다.

 

먼저 Single Bit Error는 데이터 중 하나의 비트만이 변경된 것을 말한다.

 

그리고 여기서 변조된 비트를 Corrupted Bit라고 부른다.

두 번째로 Burst Error는 이러한 Corrupted Bit가 두 개이상인 에러를 의미한다.

 

 

여기서 처음 변조가 일어난 Corrupted Bit와 마지막 Corrupted Bit까지 총 8비트를 에러가 난 부분이라고 판단한다.

 

 

 

 

 

Error Detection

 

이전에 Block Coding은 추가적인 Redundancy(여분의)를 통해 오류를 탐지하는데 도움을 준다고 했다.

이제 이 여분의 정보를 통해 어떻게 에러 감지가 가능한 지 알아볼 것이다.

 

오류를 감지하거나 수정하는 핵심 개념은 중복성이다. 오류를 감지하거나 수정할 수 있으려면, 우리는 데이터와 함께 몇 개의 추가 비트인 여분의 를 보내야 한다. 이러한 중복 비트는 송신자에 의해 추가되고 수신자에 의해 제거되는데, 이 비트들의 존재가 수신자의 손상된 비트를 감지하거나 수정할 수 있도록 도와주는 것이다.

 

 

 

블록 코딩에서는 메시지를 k비트짜리 블록으로 나누고, 이를 Dataword라고 부른다. 이때, 각 블록에 r개의 중복 비트를 추가하여 전체 길이가 n = k + r이 되게 한다.

이렇게 생성된 n비트 블록을 Codeword라고 한다.

 

 

만약 위와 같은 표로 Dataword에 대한 Codewords를 정해놓았다고 하자.

그러면, 송신자 측에서는 보내는 비트들에 대해 해당 표를 보고 여분의 비트를 추가할 것이다.

수신자 측에서는 이제 Codewords 비트들을 받게 될 것인데, 마찬가지로 위 표를 보고 해석하여 Datawords를 추출한다. 만약, 들어오는 Codewords가 표에서 존재하지 않는다면, 정보가 변조되었다는 뜻이므로 에러를 감지할 수 있다.

 

전혀 문제가 없어 보인다.

하지만, 만약 하나의 비트가 아니라 두 개 이상의 비트가 변조된다면 어떨까? 예를 들어, 000이 전달되는 와중에 변조가 되어 011이 되었다고 하자. 그래도 수신자 측에서 해당 Codewords는 표에 존재하는 비트이므로 에러로 판단하지 않을 것이다. 즉, 에러가 감지되어야 할 상황에 정상적인 비트라고 오판해버리고 만다.

 

 

 

 

Simple Parity Bit

 

 

문제가 발생한다는 사실은 알고 있지만, 어떤 방식으로 Codewords가 만들어지고 검사 되는지 Simple Parity Bit를 통해 알아보자.

 

사실 만드는 방법은 매우 간단하다. 방법도 두 가지로 나뉘는데, Datawords를 모두 더했을 때 짝수가 나오도록 Codewords를 작성한다면, 짝수 패리티 비트이고, 홀수가 나오도록 한다면 홀수 패리티비트이다.

 

실제로는 2와 모듈 연산을 통해 비트를 추가하도록 하는데, 의미적으로 본다면 그냥 짝수로 만들기, 홀수로 만들기에 대한 방법이다.

 

 

_Generator_는 앞서 말한 짝/홀수 패리티 비트를 만드는 도구이다.

그리고 수신자 측에서 받은 Codeword를 _Checker_가 Syndrome으로 만드는데, 이 Syndrome은 Codeword의 값을 2와 모듈 연산한 것이다.

 

즉, 홀수 패리티 비트를 만들었다면 1이라는 값이 Syndrome이 되고, 짝수 패리티 비트를 만들었다면 0이라는 값이 Syndrome이 될 것이다. Decision Logic은 해당 Syndrome에 저장된 값을 보고 에러가 났는지 나지 않았는지 감지한다. 

 

※ 문제가 되는 상황

 

이제부터 짝수 패리티를 통해 오류 검출 하는 상황을 가정해 보자.

_1011_이라는 Dataword를 Codeword로 나타내기 위해 _10111_으로 바꾸어주었다.

 

 

1. 오류가 없는 경우

_10111_이 아무런 변조 없이 그대로 수신자에게 도착했다면 문제가 없을 것이다.

 

2. Dataword의 비트 중 하나가 corrupted bit가 된 경우

이 경우는 Dataword 비트 중 하나가 변조가 일어난 경우이다.

_10111_에서 _10011_과 같이 변했다고 하면, Syndrome은 1이 되므로 에러를 정상적으로 검출한다.

 

3. Parity 비트가 corrupted bit가 된 경우

Dataword는 정상적이지만, Parity 비트가 비정상적으로 도착했다. 송신자가 보내는 데이터 자체는 정상적인데, 추가적으로 붙은 Parity 비트 때문에 수신자 측에서는 에러가 난 것으로 감지한다.

 

예를 들어, _10110_으로 잘못 도착했지만, Dataword는 정상이다. 하지만, Parity 비트로 인해 해당 신호를 에러가 난 것으로 판단한다.

 

4. Parity 비트와 Dataword 중 하나의 비트가 corrupted bit가 된 경우

_00110_이 그와 같은 상황이 될 수 있는데, Dataword는 잘못된 값이 도착했으나, Syndrome은 0으로 나와 에러를 감지하지 못한다.

 

5. Dataword의 비트 중 3개가 corrupted bit인 경우

_01011_과 같은 상황으로 제대로 에러를 감지한다.

 

 

이를 통해 이 Parity Check 코드는 홀수 개의 오류만 감지 가능하다는 것을 알 수 있다.

 

 

 

 

 

Two-dimensional Parity-check Code

 

Two-dimensional Parity-check Code는 Single Parity Check Code에서 홀수 개의 오류만을 감지한다는 한계점을 개선한 오류 검출 방식이다.

 

짝수 개의 오류를 감지하기 위해 2차원 배열을 사용하고, 각각 패리티 비트를 추가한다.

 

 

위 그림과 같이 행과 열에 따라 각각 패리티 비트를 생성한다.

만약 하나의 비트만 에러가 난다면, 두 개의 패리티 비트에 영향을 주므로 어떻게든 오류를 감지할 수 있다.

 

 

만약 아래와 같이 두 개의 비트가 에러가 난다면, 한 행에서는 영향을 주지 않더라도 각 열에서 패리티 비트에 영향이 간다.

따라서 오류를 검출할 수 있다.

 

 

아래와 같이 구성된 경우 3가지 에러가 난다면, 4개의 패리티 비트에서 검출 가능하다.

 

 

단, 아래와 같이 같은 행과 같은 열에 2개씩 오류가 난다면, 에러를 감지할 수 없다. 따라서 이 Two-dimensional Parity Check도 완전하다고는 할 수 없다.