2차원 패리티

요약

데이터를 바이트마다 한 줄씩 쌓아 표로 만든 뒤, 줄마다 끝에, 칸마다 아래에 1의 개수를 짝수로 맞추는 비트(패리티 비트)를 하나씩 붙인다. 비트 하나가 뒤집히면 그 비트가 있는 줄과 칸의 검사가 함께 틀리므로, 두 검사가 만나는 곳에서 어느 비트인지 알아내 고칠 수도 있다. 2·3비트 오류도 모두 잡는다. 하지만 직사각형 네 꼭짓점이 함께 뒤집히는 4비트 오류처럼 줄과 칸마다 짝수 개씩 바뀌면 놓친다.

예시로 보기

패리티 비트 하나에는 약점이 둘 있다. 비트 두 개가 함께 뒤집히면 놓친다. 오류를 잡아도 어느 비트가 틀렸는지는 모른다(오류 검출 코드). 2차원 패리티는 같은 검사를 가로와 세로로 두 번 해서 두 약점을 함께 줄인다.

표를 만들고 패리티 붙이기

7비트짜리 6바이트 데이터를 예로 든다. 한 바이트를 한 줄로 놓고 6줄을 위아래로 쌓으면 6줄 7칸의 표가 된다. 여기에 짝수 패리티를 가로와 세로로 붙인다.

그림의 흰 칸 6줄 7칸이 데이터다. 오른쪽 파란 칸 한 줄이 줄마다 붙인 가로 패리티이고, 그 오른쪽 글자는 그 줄 데이터의 1의 개수와 붙인 값이다. 아래쪽 파란 칸 한 줄이 칸마다 붙인 세로 패리티 바이트이고, 그 아래 숫자가 그 칸 데이터의 1의 개수다. 오른쪽 아래 보라 칸이 모서리 비트다.

가로 패리티를 한 줄만 직접 계산해 본다. 첫 줄 0101001의 1을 왼쪽부터 센다. 둘째, 넷째, 일곱째 비트가 1이라 모두 3개다. 홀수이므로 1을 붙여 1을 4개로 만든다. 그래서 첫 줄 끝의 가로 패리티는 1이다. 1이 4개인 둘째 줄 1101001은 이미 짝수라 0을 붙인다.

세로도 방법이 같다. 첫째 칸은 여섯 줄의 첫 비트를 위에서부터 모은 0, 1, 1, 0, 0, 1이다. 1이 3개라 1을 붙인다. 그래서 세로 패리티 바이트의 첫 비트가 1이다. 일곱 칸을 모두 이렇게 구하면 세로 패리티 바이트 1111011이 나온다¹.

오른쪽 아래 모서리 비트는 어떻게 정할까? 가로 패리티 6개(1, 0, 1, 1, 1, 0)도 위아래로 늘어선 한 칸이다. 이 칸의 1은 4개라 0을 붙인다. 세로 패리티 바이트 7비트 1111011도 한 줄이다. 이 줄의 1은 6개라 역시 0이다.

두 계산이 늘 같은 값을 내는 데는 이유가 있다. 가로 패리티는 줄마다 1의 개수의 짝홀이다. 그래서 가로 패리티 6개를 모두 더한 수의 짝홀은 데이터 42비트 전체의 1의 개수의 짝홀과 같다. 세로 패리티 7개도 칸마다 세어 같은 전체 개수에 이른다. 이 예 데이터의 1은 모두 24개(짝수)라 어느 쪽으로 구해도 모서리 비트는 0이다¹.

받는 쪽은 받은 표의 줄마다 패리티 비트까지 8비트의 1을 세고, 칸마다 패리티 바이트까지 7비트의 1을 센다. 모두 짝수면 오류가 없다고 본다. 모서리 비트가 있어서 맨 오른쪽 칸(가로 패리티들)과 맨 아래 줄(세로 패리티 바이트)도 똑같이 검사할 수 있다.

덧붙는 비트는 가로 패리티 6개, 세로 패리티 7개, 모서리 1개로 \(6 + 7 + 1 = 14\)개다. 데이터 42비트에 14비트가 붙어 모두 56비트를 보낸다. 보내는 비트의 4분의 1이 검산용이다¹.

1비트 오류는 위치까지 찾는다

다섯째 줄 첫째 비트가 0에서 1로 뒤집혔다고 하자.

받는 쪽이 다섯째 줄을 센다. 원래 0110100과 패리티 1을 합쳐 1이 4개였는데, 첫 비트가 1이 되어 5개다. 홀수라 이 줄의 검사가 틀린다. 첫째 칸도 센다. 원래 0, 1, 1, 0, 0, 1과 패리티 1을 합쳐 4개였는데 다섯째가 1이 되어 5개다. 이 칸의 검사도 틀린다. 다른 줄과 칸은 뒤집힌 비트를 하나도 품지 않으므로 그대로 짝수다¹.

그림의 오른쪽 글자는 줄마다 센 1의 개수이고, 아래 숫자는 칸마다 센 1의 개수다. 다섯째 줄만 5개로 홀수라 주황 띠가 가로로 깔렸고, 첫째 칸만 5개로 홀수라 주황 띠가 세로로 깔렸다. 두 띠가 겹치는 진한 칸이 뒤집힌 비트다².

틀린 줄이 하나, 틀린 칸이 하나뿐이다. 뒤집힌 비트는 그 줄에도 그 칸에도 있어야 하므로, 두 띠가 만나는 칸밖에 없다. 받는 쪽은 그 비트를 다시 뒤집어 원래 표로 되돌린다. 이렇게 오류를 찾아 고칠 수 있는 코드를 오류 수정 코드라 부른다.

패리티 칸이 뒤집혀도 같은 방법이 통한다. 가로 패리티 비트 하나가 뒤집히면 그 줄과 맨 오른쪽 칸이 틀리고, 둘이 만나는 곳이 바로 그 패리티 비트다. 모서리 비트가 맨 오른쪽 칸에도 검사를 만들어 주기 때문이다. 56칸 어디서 비트 하나가 뒤집혀도 이렇게 위치를 찾는다¹.

2·3비트 오류는 늘 잡는다

2비트 오류는 두 경우로 나눠 본다.

두 비트가 서로 다른 줄에 있으면, 두 줄이 뒤집힌 비트를 하나씩 품는다. 두 줄 모두 1의 개수가 1만큼 변해 홀수가 되므로 가로 검사가 잡는다.
두 비트가 같은 줄에 있으면, 그 줄은 개수가 2만큼 변하거나 그대로라 짝수로 남는다. 가로 검사로는 못 잡는다. 하지만 같은 줄의 두 비트는 반드시 서로 다른 칸에 있다. 두 칸이 하나씩 품어 홀수가 되므로 세로 검사가 잡는다.

어느 경우든 적어도 한 검사는 틀린다. 그래서 2비트 오류는 늘 검출한다¹.

그림은 둘째 줄의 셋째와 여섯째 비트가 함께 0에서 1로 뒤집힌 경우다. 오른쪽 글자를 위에서부터 보면 모든 줄이 짝수라 가로 검사는 하나도 틀리지 않는다. 둘째 줄도 4개에서 6개로 늘었을 뿐 짝수다. 아래 숫자를 보면 셋째 칸과 여섯째 칸만 5개로 홀수다. 오류가 있다는 것은 알지만, 어느 줄인지 알려 주는 가로 띠가 없다³.

받는 쪽은 왜 어느 줄인지 모를까? 넷째 줄의 같은 두 칸이 뒤집혀도 받는 쪽이 보는 결과는 똑같다. 셋째 칸과 여섯째 칸만 틀린다. 여섯 줄 중 어느 줄에서 일어났든 증상이 같으니 하나로 정할 수 없다. 그래서 고치지 못하고 검출만 한다¹.

두 비트가 서로 다른 줄, 서로 다른 칸에 있어도 고칠 수 없다. 이때는 줄 둘, 칸 둘이 틀려 띠가 만나는 칸이 네 곳 나온다. 진짜 오류는 그중 대각선으로 마주 보는 두 곳이다. 하지만 반대쪽 대각선의 두 곳이 뒤집혀도 똑같은 줄과 칸이 틀리므로, 어느 대각선인지 고를 수 없다¹.

3비트 오류는 어떨까? 세 비트를 여러 줄에 나눠 넣을 때, 모든 줄이 짝수 개(0개나 2개)씩만 품을 수는 없다. 짝수끼리 더하면 짝수인데 3은 홀수이기 때문이다. 그래서 적어도 한 줄은 홀수 개를 품고, 그 줄의 가로 검사가 틀린다. 같은 이유로 5비트, 7비트처럼 홀수 개 오류는 모두 잡는다¹.

놓치는 4비트 오류

줄마다, 칸마다 뒤집힌 비트가 짝수 개씩이면 모든 검사가 그대로 짝수라 놓친다. 4비트로 이렇게 되려면 뒤집힌 비트가 직사각형의 네 꼭짓점에 있어야 한다.

위쪽 두 꼭짓점은 한 줄에, 아래쪽 두 꼭짓점은 다른 한 줄에 있다. 그래서 두 줄이 각각 2개씩 품어 짝수로 남는다. 왼쪽 두 꼭짓점은 한 칸에, 오른쪽 두 꼭짓점은 다른 한 칸에 있다. 그래서 두 칸도 2개씩 품어 짝수로 남는다. 틀리는 검사가 하나도 없어 받는 쪽은 아무것도 알아채지 못한다¹.

다른 4비트 모양은 숨지 못한다. 한 줄에 4개가 모두 있으면 네 칸이 하나씩 품어 세로 검사가 틀린다. 세 줄 이상에 흩어지면 어느 줄은 홀수 개를 품는다. 남는 것은 두 줄에 2개씩, 그것도 같은 두 칸에 놓이는 모양뿐이고, 그것이 직사각형이다¹.

검증: 위 예의 패리티 비트와 패리티 바이트, 1비트 오류 56곳 모두 위치 찾기와 고치기, 2·3비트 오류 전수 검출, 직사각형 4비트 오류는 놓침, 카드 C2 — 48_two-dimensional-parity_impl.py

정의

데이터를 \(m\)바이트(각 \(n\)비트)의 표로 놓는다. \(m\)은 줄 수, \(n\)은 칸 수다. 위 예에서는 \(m = 6\), \(n = 7\)이다.

가로 패리티(VRC): 바이트마다 1의 개수가 짝수가 되게 비트 하나를 붙인다. 1의 개수가 홀수면 1, 짝수면 0이다.
세로 패리티(LRC): 같은 자리(칸)의 비트들마다 같은 방식으로 비트 하나를 붙여 패리티 바이트를 만든다.

이름의 Vertical(세로)과 Longitudinal(길이 방향)은 이 문서의 가로·세로와 반대로 보인다. 이 이름은 옛 자기 테이프에서 한 문자의 비트가 테이프 폭 방향으로 나란히 적히고, 문자들이 테이프 길이 방향으로 이어지던 모습에서 왔다⁴ [확인필요]. 헷갈리면 바이트마다 붙이는 쪽이 VRC, 같은 자리끼리 모아 붙이는 쪽이 LRC라고 기억한다.

덧붙는 비트는 줄마다 하나, 칸마다 하나, 모서리 하나라 \(m + n + 1\)개다. 위 예의 값을 넣으면 \(6 + 7 + 1 = 14\)개다.

검출과 수정. 2차원 패리티는 1·2·3비트 오류를 모두 검출하고, 1비트 오류는 위치를 알아 고칠 수 있다(오류 수정 코드). 이것은 재전송 없이 받는 쪽이 고치는 순방향 오류 수정의 예다.

활용

복잡도: 표를 한 번 훑으며 줄마다, 칸마다 1을 함께 세면 된다. 비트 수 \(mn\)에 비례하는 \(O(mn)\)이다.
옛 터미널 통신과 테이프 저장에서 VRC/LRC로 쓰였다. 지금의 링크는 같은 비용으로 훨씬 강한 CRC를 쓴다⁵.
흔한 실수: “2차원이니 2비트 오류도 고친다”고 생각하는 것. 같은 줄의 2비트 오류는 세로 두 칸만 틀려 어느 줄인지 모른다. 서로 다른 줄·칸의 2비트 오류는 교차점이 네 곳이라 진짜 두 곳을 고를 수 없다. 둘 다 검출만 한다.

연결

선수: 오류 검출 코드(1차원 패리티)
오류를 고치는 쓰임: 오류 복구와 FEC
다른 코드와 비교: 오류 검출 방식 비교

확인 문제

C1 2차원 패리티가 반드시 검출하는 오류와 고칠 수 있는 오류를 쓰라.

답: 1·2·3비트 오류는 모두 검출한다. 고칠 수 있는 것은 1비트 오류다(틀린 줄과 칸의 교차점).

C2 받은 표를 점검했더니 가로 패리티는 셋째 줄(번호 2), 세로 패리티는 여섯째 칸(번호 5)만 틀렸다. 어떻게 고치나?

답: 셋째 줄 여섯째 칸의 비트 하나가 뒤집힌 것이다. 그 비트를 다시 뒤집는다. 그러면 모든 줄과 칸의 패리티가 맞는다.

C3 2차원 패리티가 놓치는 4비트 오류를 들라.

답: 직사각형의 네 꼭짓점, 예를 들어 (줄 0, 칸 0), (줄 0, 칸 3), (줄 2, 칸 0), (줄 2, 칸 3)이 함께 뒤집히는 오류. 줄 0, 줄 2, 칸 0, 칸 3에서 각각 두 비트씩 바뀌어 모든 패리티가 그대로다.

C4 “틀린 줄 번호와 틀린 칸 번호의 교차점 비트를 뒤집는다”는 수정 절차가 하는 일을 한 문장으로 쓰라.

답: 비트 하나가 뒤집히면 그 비트가 속한 줄과 칸의 패리티만 틀리므로, 두 정보를 겹쳐 오류 위치를 찾아 원래 값으로 되돌린다.

48_two-dimensional-parity_plot.py와 구현 코드로 확인했다. ↩ ↩² ↩³ ↩⁴ ↩⁵ ↩⁶ ↩⁷ ↩⁸ ↩⁹ ↩¹⁰ ↩¹¹
48_two-dimensional-parity_plot.py로 그렸고, 다섯째 줄 첫째 비트가 뒤집히면 다섯째 줄과 첫째 칸만 5개(홀수)가 되는 것을 같은 코드로 확인했다. 카드 C2의 자리(셋째 줄 여섯째 칸)와 다른 자리를 골랐다. ↩
48_two-dimensional-parity_plot.py로 그렸고, 둘째 줄 셋째·여섯째 비트가 뒤집히면 가로 검사는 모두 통과하고 셋째·여섯째 칸만 틀리는 것, 넷째 줄의 같은 두 칸이 뒤집혀도 같은 결과가 나오는 것을 같은 코드로 확인했다. ↩
테이프 기록 방식에 따른 일반적인 설명이다. ↩
구현 코드로 모든 경우를 확인했다. ↩