패리티 비트 튜토리얼: 단일 비트 오류 검출
XOR로 짝수 및 홀수 패리티를 유도하고, 균형 잡힌 생성기와 검사기를 구축하며, 검출되지 않는 오류를 정량화하고, UART 패리티가 증명할 수 있는 것과 없는 것을 이해합니다.
요약: 패리티 비트는 데이터 워드를 확장하여 1의 총개수가 짝수 또는 홀수가 되게 합니다. XOR는 생성과 검사를 모두 구현합니다. 이렇게 만들어진 부호는 모든 단일 비트 오류를 포함하여 홀수 개의 비트 반전을 모두 검출하지만, 짝수 가중치 오류 패턴은 모두 보이지 않습니다.
패리티는 가장 작으면서도 유용한 오류 검출 부호입니다. 비트 하나를 추가하고, XOR 리덕션 하나만 필요하며, 홀수 개의 비트를 바꾸면 워드의 패리티가 바뀐다는 정확한 보장을 제공합니다.
이 보장은 “데이터가 유효하다”는 주장보다 범위가 좁습니다. 검사 결과가 정상이어도 변하지 않은 워드와 두 개, 네 개 또는 다른 짝수 개 위치가 반전된 워드를 구별할 수 없습니다. 전문적인 사용은 이 한계를 명시하고 남아 있는 미검출 오류 확률을 받아들일 수 있는지 판단하는 것에서 시작합니다.
짝수 패리티와 홀수 패리티
비트 데이터 워드
에 대해 XOR 리덕션을 다음과 같이 정의합니다.
데이터에 포함된 1의 개수가 홀수일 때에만 입니다.
짝수 패리티에서는 다음을 선택합니다.
그러면 전송된 모든 위치의 XOR는 0입니다.
홀수 패리티에서는 그 비트를 반전합니다.
그러면 결합 XOR는 1입니다. 어느 규약도 본질적으로 더 강력하지는 않습니다. 송신기와 수신기는 같은 규약을 사용하고, 정확히 어떤 필드가 보호 범위에 포함되는지 합의해야 합니다.
4비트 생성기 표
| 1의 개수 | |||
|---|---|---|---|
0000 | 0 | 0 | 1 |
0001 | 1 | 1 | 0 |
0011 | 2 | 0 | 1 |
0111 | 3 | 1 | 0 |
1111 | 4 | 0 | 1 |
생략한 행도 같은 규칙을 따릅니다. 비트 패턴의 수치값은 중요하지 않습니다. 2를 법으로 한 1의 개수만 중요합니다.
이는 두 원소 체에서의 덧셈입니다.
두 번의 반전은 패리티 합에서 서로 상쇄되며, 이는 회로와 그 한계를 모두 설명합니다.
생성기 구축하기
2입력 XOR 게이트는 결합 법칙을 만족합니다.
따라서 여러 토폴로지가 같은 부울 함수를 구현할 수 있습니다.
선형 체인
D7 ─┐
XOR─┐
D6 ─┘ XOR─┐
D5 ─────┘ XOR─ ... ─ P
개 입력의 경우 단순 체인은 2입력 XOR 연산을 번 사용하며, 최대 개의 논리 게이트 단계를 가집니다.
균형 트리
D7 ─┐
XOR─┐
D6 ─┘ │
XOR─┐
D5 ─┐ │ │
XOR─┘ │
D4 ─┘ │
XOR─ P
D3 ─┐ │
XOR─┐ │
D2 ─┘ │ │
XOR─┘
D1 ─┐ │
XOR─┘
D0 ─┘
8개 입력의 경우 균형 이진 트리는 논리 XOR 단계가 세 개입니다. 보통 7단계 체인보다 논리 깊이가 작습니다.
어느 그림에도 보편적인 나노초 값을 붙이지 마세요. 실제 지연은 게이트 패밀리 또는 FPGA 매핑, 배선, 팬아웃, 전원, 온도, 입력 도착 시간에 따라 달라집니다. 넓은 패리티 트리가 타이밍 경로에 있다면 대상 구현의 타이밍 도구로 검증하세요.
수신기 검사기
수신한 데이터 와 수신한 짝수 패리티 비트 에 대해 다음과 같습니다.
는 흔히 패리티 신드롬 또는 패리티 오류 표시라고 합니다.
- : 홀수 가중치 오류가 검출되지 않았습니다.
- : 보호 범위에 포함된 위치 중 홀수 개가 전송된 값과 다릅니다.
검사기는 위치를 식별할 수 없으므로 워드를 정정할 수 없습니다. 그 출력은 정의된 대응으로 이어져야 합니다. 워드를 무효로 표시하거나, 상태 비트를 설정하거나, 진단 카운터를 증가시키거나, 상위 수준 프로토콜을 통해 재전송을 요청합니다.
홀수 패리티에서는 통과/실패 해석을 반대로 하거나 결합 XOR를 1과 비교합니다.
8비트 예제
데이터 바이트가 다음과 같다고 하겠습니다.
D = 10110100
1이 네 개이므로 짝수 패리티는 P=0을 추가합니다.
transmitted codeword = 10110100 0
오류 없는 수신
9개 위치 전체의 XOR는 0이므로 검사기는 검출된 패리티 오류가 없다고 보고합니다.
한 위치의 반전
D3가 0에서 1로 바뀌면 다음과 같습니다.
received = 10111100 0
결합 XOR는 1입니다. 수신기는 코드워드가 손상되었다는 것은 알지만, 장애가 D3에 있는지 다른 데이터 위치에 있는지 또는 P에 있는지는 알 수 없습니다.
두 위치의 반전
D3가 0→1로 바뀌고 D5가 1→0으로 바뀌면 다음과 같습니다.
received = 10011100 0
결합 XOR는 다시 0이 됩니다. 오류 패턴의 가중치가 짝수이므로 손상된 워드는 패리티 검사를 통과합니다.
패리티가 보장하는 것
단일 패리티 비트는 최소 해밍 거리가 2인 부호를 만듭니다. 가중치가 1인 모든 오류 패턴을 검출하며, 더 일반적으로 다음과 같습니다.
| 반전된 보호 대상 위치 수 | 검출 여부 |
|---|---|
| 1 | 항상 |
| 2 | 절대 안 됨 |
| 3 | 항상 |
| 4 | 절대 안 됨 |
| 홀수 개 | 항상 |
| 양의 짝수 개 | 절대 안 됨 |
여기서 “절대 안 됨”은 패리티만으로는 해당 오류 패턴을 유효한 코드워드와 구별할 방법이 없다는 뜻입니다. CRC, 시퀀스 번호, 프레이밍 규칙 또는 애플리케이션 제약 같은 다른 계층은 여전히 이를 드러낼 수 있습니다.
패리티는 다음을 하지 못합니다.
- 바뀐 비트의 위치를 찾기;
- 데이터를 정정하기;
- 모든 버스트를 검출하기;
- 메시지를 인증하기;
- 물리 링크가 정상임을 증명하기;
- 보호 범위에서 제외된 필드를 보호하기.
공격자는 의도적으로 데이터를 수정하고 패리티를 다시 계산할 수 있습니다. 악의적인 변조가 위협 모델에 포함된다면 암호학적 메시지 인증 메커니즘을 사용하세요.
무작위 미검출 오류 정량화
코드워드에 보호 대상 위치가 개 있고 각각이 확률 로 독립적으로 반전된다고 가정합니다. 짝수 개의 비트가 반전될 확률은 다음과 같습니다.
여기에는 확률이 인 무오류 사건이 포함됩니다. 따라서 검출되지 않은 손상 코드워드의 확률은 다음과 같습니다.
가 작을 때 지배적인 항은 다음과 같습니다.
8비트 데이터 워드와 패리티를 합치면 이므로, 1차 미검출 기여분은 가 아니라 약 입니다. 패리티 위치도 실패할 수 있기 때문입니다.
이 모델은 비트 반전이 독립이고 동일한 분포를 따른다고 가정합니다. 실제 채널에는 상관된 잡음과 버스트가 있을 수 있으므로, 측정되었거나 규정된 채널 동작에 따라 부호를 선택해야 합니다.
맥락 속의 UART 패리티
구성 가능한 비동기 직렬 프레임은 보통 다음과 같은 문자열로 설명합니다.
8N1: 데이터 비트 8개, 패리티 없음, 정지 비트 1개;8E1: 데이터 비트 8개, 짝수 패리티, 정지 비트 1개;8O1: 데이터 비트 8개, 홀수 패리티, 정지 비트 1개.
UART 프레이밍과 RS-232 전기 인터페이스는 많은 시스템에서 관련되어 있지만 같은 규격은 아닙니다. UART는 문자를 직렬화하고 검사하는 방법을 정의하며, RS-232 트랜시버는 인터페이스의 전압 수준 신호를 정의합니다.
잘못된 패리티를 검출한 수신기는 보통 패리티 오류를 보고합니다. 프레이밍 오류는 일반적으로 유효하지 않은 정지 비트와 관련된 별개의 조건입니다. 마이크로컨트롤러 USART는 이러한 이벤트를 위한 별도의 상태 플래그를 제공하는 경우가 많습니다.
수신기가 문자를 버릴지, 오류 플래그와 함께 전달할지, 인터럽트를 발생시킬지는 구현 및 소프트웨어 정책의 문제입니다. 패리티가 자동으로 재전송을 요청한다고 가정하지 마세요. UART 상위의 프로토콜이 그 동작을 정의해야 합니다.
패리티, 해밍 부호, CRC
| 속성 | 단일 패리티 | Hamming(7,4) 디코더 | CRC |
|---|---|---|---|
| 핵심 연산 | XOR 리덕션 | 패리티 검사 신드롬 | GF(2)에서의 다항식 나머지 |
| 오류 정정 | 아니요 | 오류 모델 내에서 1비트 | 보통 아니요 |
| 모든 단일 비트 오류 검출 | 예 | 예 | 다항식에 따라 다름. 표준 선택은 대체로 가능 |
| 짝수 가중치 오류 가시성 | 패리티만으로는 없음 | 부호 및 디코더에 따라 다름 | 다항식 및 메시지 길이에 따라 다름 |
| 일반적 역할 | 가벼운 워드별 검사 | 작은 블록을 위한 순방향 정정 | 강력한 프레임/블록 검출 |
확장 해밍 부호는 전체 패리티를 추가하여, 가정한 오류 한도 내에서 단일 오류 정정과 이중 오류 검출을 지원합니다. CRC의 강도는 생성 다항식과 보호 길이에 따라 달라지므로, 그런 매개변수 없이 “모든 버스트를 잡는다”라고 요약해서는 안 됩니다.
DigiSim에서 구축하기
8비트 직렬 송신기/수신기 템플릿 또는 새 캔버스를 사용하세요.
- 데이터 스위치 여덟 개를 배치합니다.
- 짝수 패리티용 균형 XOR 트리를 구축합니다.
- 데이터 워드에 P를 추가합니다.
- 수신된 아홉 위치 전체에 걸친 두 번째 XOR 트리를 구축합니다.
- 전송된 각 위치에 오류 주입 XOR 하나를 추가합니다.
- 모든 단일 위치 오류가
S=1을 만들어 내는지 확인합니다. - 선택한 두 위치 오류를 주입하여 검출되지 않고 통과하는지 확인합니다.
- P를 반전하여 홀수 패리티로 변경하고 예상 검사 값을 갱신합니다.
정적 워드뿐 아니라 전이도 시험하세요. 여러 데이터 입력이 변할 때 경로 지연이 같지 않으면 일시적인 패리티 펄스가 생길 수 있습니다. 검사 전에 완전한 데이터 워드를 레지스터에 저장하거나, 프로토콜이 워드가 안정적이라고 지정할 때만 신드롬을 샘플링하세요.
다음 요구 사항이 단일 비트 정정이라면 Hamming(7,4)로 계속 진행하세요. 여러 패리티 검사가 하나의 오류 표시를 위치를 식별하는 신드롬으로 바꿉니다.



