데이터 오류 검출 방식

데이터 오류 검출은 주로 데이터 전송 또는 저장 과정에서 발생할 수 있는 비트 오류를 탐지하는 방법입니다.

 

1. 패리티 검사 (Parity Check) :

홀수 패리티(ODD Parity) 또는 짝수 패리티(EVEN Parity)를 사용합니다. 송수신 측은 1의 개수를 홀수 또는 짝수로 유지하기 위해 약속하고, 이를 위해 패리티 비트를 추가하여 데이터를 전송합니다. 수신자는 데이터와

패리티 비트를 사용하여 오류를 감지합니다.

 

 

홀수 패리티 (ODD Parity)와 짝수 패리티 (EVEN Parity):

짝수(Even) 패리티는 전체 비트에서 의 개수가 짝수가 되도록 패리티 비트를 정하는 것

홀수(Odd) 패리티는 전체 비트에서 1의 개수가 홀수가 되도록 패리티 비트를 정하는 것

패리티 비트를 정하여 데이터를 보내면 받는 쪽에서는 수신된 데이터의 전체 비트를 계산하여 패리티 비트를 다시 계산함으로써 데이터 오류 발생 여부를 알 수 있습니다.

(그러나 패리티 비트는 오류 발생 여부만 알 수 있지 오류를 수정할 수는 없다)

 

동작원리:

1. 비트 수 선정:
   • 데이터 전송에 사용할 비트 수를 결정합니다. 예를 들어, 8비트의 데이터를 전송한다면 7비트는 실제 데이터 비트이고, 나머지 1비트는 패리티 비트로 사용될 것입니다.
2. 패리티 선택 (홀수 또는 짝수):
   • 통신 양측에서 홀수 패리티 또는 짝수 패리티를 선택합니다. 일반적으로는 홀수 패리티 또는 짝수 패리티 중 하나를 선택하여 사용합니다.
3. 데이터 생성 및 송신:
   • 송신자는 전송할 데이터를 이진 형태로 변환합니다. 이때, 실제 데이터 비트들을 포함한 부분을 구성합니다.
4. 패리티 비트 계산:
   • 선택한 패리티 방식에 따라, 송신자는 데이터 비트에 대한 패리티 비트를 계산합니다.
     • 홀수 패리티: 데이터 비트들에 1의 개수가 홀수로 맞춰지도록 패리티 비트를 계산합니다.
     • 짝수 패리티: 데이터 비트들에 1의 개수가 짝수로 맞춰지도록 패리티 비트를 계산합니다.
5. 패리티 비트 추가 및 전송:
   • 계산된 패리티 비트를 데이터에 추가합니다. 이렇게 만들어진 데이터 비트와 패리티 비트를 함께 전송합니다.
6. 수신 및 검사:
   • 수신자는 전송된 데이터를 받으면서 동시에 패리티 비트를 계산합니다.
   • 송신자와 수신자 간의 패리티 계산 방식이 동일하다면, 수신자가 계산한 패리티 비트와 전송된 패리티 비트를 비교합니다.
7. 오류 감지:
   • 만약 오류가 발생하면, 수신자가 계산한 패리티 비트와 전송된 패리티 비트가 일치하지 않을 것입니다. 이로써 오류가 감지됩니다.

문제점과 한계

 

패리티 비트는 홀수 개의 오류만 감지 가능하며, 짝수 개의 오류는 검출하지 못합니다.

 

 

Even Parity에서 검출 불가한 경우:

2개의 비트 오류를 검출하지 못함.

 패리티 검사는 간단하나, 한계가 있어 모든 종류의 오류를 감지하기 어렵습니다.
 더 복잡한 방법이 필요할 수 있으며, 실제로는 CRC나 해밍 코드 등이 활용됩니다.

 

 

 

 

 

2. CRC(Cyclic Redundancy Chcek: 순환 중복 검사)

패리티 검사의 한계를 채워주기 위해 나온 오류 검출 방식이다. 특정 알고리즘에 기초하여 데이터 프레임 내의 데이터에 대한 체크 코드를 계산하고, 데이터 프레임에 체크 코드를 부가하고, 데이터 프레임을 수신단으로 전송한다. 수신 측은 동일한 알고리즘을 사용하여 계산을 반복하여 수신된 데이터의 정확성과 무결성을 검증합니다.

 

동작 원리:

1. 다항식 선택:
   • CRC는 다항식 연산을 기반으로 동작합니다. 송신자와 수신자는 동일한 생성 다항식을 알고 있어야 합니다. 이 다항식을 생성 다항식이라고 부릅니다.
2. 비트 추가:
   • 송신자는 원래 데이터에 일정한 규칙에 따라 생성 다항식에 해당하는 비트를 추가합니다. 이 비트는 CRC 코드 또는 CRC 체크섬이라고 불립니다.
3. 전송:
   • 전송된 데이터에는 추가된 CRC 코드가 포함되어 있습니다.
4. 수신:
   • 수신자는 받은 데이터에 대해 동일한 생성 다항식을 사용하여 연산을 수행합니다.
5. 검사:
   • 수신자는 연산 결과로 나온 CRC 코드를 확인합니다. 원래의 CRC 코드와 수신자가 계산한 CRC 코드가 일치하면 데이터가 손상되지 않았다고 가정합니다.

 

 

예시:

다음은 간단한 예제입니다. 생성 다항식이 x^3 + x + 1 인 경우를 가정해 보겠습니다.

1. 데이터 전송 전:
   • 데이터: 110101
   • 생성 다항식: x^3 + x + 1
   • CRC 코드를 계산하여 데이터에 추가합니다.
2. 데이터 전송 후:
   • 전송된 데이터: 110101110 (CRC 코드 추가)
3. 데이터 수신 후:
   • 수신된 데이터: 110101111
   • 수신자는 동일한 생성 다항식을 사용하여 CRC 코드를 계산합니다.
4. CRC 코드 검사:
   • 송신자와 수신자가 계산한 CRC 코드가 일치하는지 확인합니다.
   • 일치하면 데이터가 손상되지 않았다고 가정합니다.

장점:

• 높은 신뢰성: CRC는 다양한 종류의 오류를 검출하는 데 효과적입니다.
• 간단하고 빠른 연산: CRC 연산이 비교적 간단하고 빠르기 때문에 실시간 통신에 적합합니다.

단점:

• 오류 수정 불가능: CRC는 오류를 검출만 가능하며, 수정은 불가능합니다.
• 생성 다항식의 선택이 중요: 생성 다항식의 잘못된 선택은 신뢰성을 감소시킬 수 있습니다.

CRC는 다양한 통신 프로토콜에서 사용되며, Ethernet, Wi-Fi, Bluetooth 등의 통신에서도 널리 활용됩니다.

 

 

 

 

 

3. 체크섬(Checksum)

체크섬은 데이터 전송 중에 오류를 검출하기 위한 방법 중 하나로 사용됩니다. 이는 데이터의 일부분에서 파생된 값을 통해 오류 여부를 확인하는 방식입니다. 체크섬은 데이터 블록 전체의 일종의 합 또는 체크값을 나타냅니다. 송신자는 데이터와 이에 대한 체크섬을 함께 전송하며, 수신자는 받은 데이터에 대해 체크섬을 다시 계산하여 송신자의 체크섬과 비교함으로써 오류를 감지합니다.

 

동작 원리:

1. 데이터 나누기:
   • 전송할 데이터를 일정한 크기의 블록으로 나눕니다.
2. 체크섬 계산:
   • 각 블록에 대한 체크섬을 계산합니다. 이는 일반적으로 블록 내의 모든 비트를 더하거나 XOR 연산 등을 통해 얻은 결과입니다.
3. 송신:
   • 송신자는 원래 데이터와 계산된 체크섬을 함께 전송합니다.
4. 수신 및 체크:
   • 수신자는 받은 데이터 블록에 대해 동일한 체크섬 계산을 수행합니다.
5. 오류 검출:
   • 송신자와 수신자가 동일한 체크섬을 계산했는지 확인합니다. 계산된 체크섬 값이 일치하면 데이터의 정합성을 확인하고, 불일치하면 오류가 발생했다고 판단합니다.

 

예시:(4비트 데이터 블록에 대한 체크섬을 계산)

1. 송신자에서 데이터 및 체크섬 계산:
   • 송신할 데이터: 1011
   • 체크섬 계산: XOR 연산 사용
   • 1 XOR 0 XOR 1 XOR 1 = 1
   • 송신 데이터: 1011 1
2. 수신자에서 데이터 및 체크섬 계산:
   • 받은 데이터: 1011 1
   • 체크섬 계산: XOR 연산 사용
   • 1 XOR 0 XOR 1 XOR 1 = 1
   • 계산된 체크섬과 송신자의 체크섬이 일치하므로 오류 없음.

이러한 방식으로 체크섬은 간단하지만 효과적인 오류 검출을 제공합니다. 체크섬이 큰 데이터 블록에 적용될 경우, 데이터 블록의 다양한 부분을 고려하여 높은 신뢰성을 유지할 수 있습니다.

 

 

 

 

 

4. 해밍코드(Hamming Code)

해밍 코드는 데이터 전송 중 발생하는 단일 비트 오류를 검출하고 수정할 수 있는 오류 검출 및 수정 코드입니다. 해밍 코드는 추가된 패리티 비트들을 통해 비트의 위치를 식별하고 수정할 수 있는 능력을 제공하여 데이터의 신뢰성을 향상시킵니다. 주로 통신과 메모리 시스템에서 사용됩니다.

 

 

동작 원리:

1. 데이터와 패리티 비트 배치:
   • 해밍 코드는 원래의 데이터 비트에 추가로 패리티 비트를 배치합니다. 패리티 비트의 위치는 2^n의 위치로 정의됩니다.
2. 패리티 비트 값 계산:
   • 각각의 패리티 비트는 특정 비트들의 패리티를 나타내게 됩니다. 예를 들어, P1은 1, P2는 2, P4는 4, P8은 8 비트의 패리티를 나타냅니다.
3. 송신:
   • 송신자는 데이터 비트와 계산된 패리티 비트를 포함한 전체 데이터를 전송합니다.
4. 수신:
   • 수신자는 받은 데이터에서 추가된 패리티 비트를 사용하여 오류 검출 및 수정을 수행합니다.

 

 

예시: 해밍 (7, 4) 코드 

• 원래 데이터 비트: 4비트
• 추가된 패리티 비트: 3비트

1. 데이터 비트와 패리티 비트 배치:
   • 데이터 비트: D1 D2 D3 D4
   • 패리티 비트: P1 P2 D1 P4 D2 D3 D4
2. 패리티 비트 값 계산:
   • P1: D1, D2, D4의 패리티 (D1 XOR D2 XOR D4)
   • P2: D1, D3, D4의 패리티 (D1 XOR D3 XOR D4)
   • P4: D2, D3, D4의 패리티 (D2 XOR D3 XOR D4)
3. 송신:
   • 원래 데이터 비트와 계산된 패리티 비트를 포함하여 전체 데이터를 전송합니다.
4. 수신:
   • 수신자는 받은 데이터에서 패리티 비트를 사용하여 오류 검출 및 수정을 수행합니다.

해밍 코드는 단일 비트 오류를 검출하고 수정할 수 있는 강력한 기능을 제공하며, 다양한 버전이 존재합니다.

 

 

 

예시 2)

 

1010 데이터가 들어왔다고 가정합니다.

 

1) 2^p >= p + 4 + 1 -> p >= 3

 

   7 6 5  4  3 2  1

2) 0 1 0 ㅁ 1 ㅁ ㅁ -> 0 1 0 1 1 0 1 (Even Parity)

 

7, 6, 5번째 자리 + 4번째 자리(패리티 비트) = 0 -> p3 패리티 비트 = 1

7, 6, 3번째 자리 + 2번째 자리(패리티 비트) = 0 -> p2 패리티 비트 = 0

7, 5, 3번째 자리 + 1번째 자리(패리티 비트) = 0 -> p1 패리티 비트 = 1

Even Parity이기 때문에 Modulo-2 연산에 의해 0이 나와야 합니다.

따라서 해밍코드는 0101101가 됩니다.

 

만약, 수신부에서 1101101이 수신됐다면,

 

7 6 5 4 3 2 1

1 1 0 1 1 0 1 -> 1

p1(1, 3, 5, 7번째 자리 중 오류 -> 1을 기록)

 

7 6 5 4 3 2 1

1 1 0 1 1 0 1 -> 1

p2(2, 3, 6, 7번째 자리 중 오류 -> 1을 기록)

 

7 6 5 4 3 2 1

1 1 0 1 1 0 1 -> 1

p3(4, 5, 6, 7번째 자리 중 오류 -> 1을 기록)

 

111 (2)가 기록되었고, 111 (2) = 7, 즉 7번째 자리에서 오류가 난 것을 알 수 있습니다.