오류 정정 코드
Error Correction Code
1. 개요
이 문서에서는 데이터에 문제가 발생했을 때 이를 검출(detection)하고 수정(correction)하는 코드들에 대해서 서술한다.
컴퓨터가 정보를 오류 없이 전송하고 저장하는 일은 생각보다 간단하지 않다. 데이터는 각종 노이즈, 물리적 흠집 등 다양한 이유로 손상될 수 있다. 그런데 컴퓨터에게 99.9999%의 정확성은 충분하지 않다. 컴퓨터는 데이터를 100% 완벽하게 전송해야 한다. 이 때문에 고급 하드웨어에는 하드웨어 자체적으로 오류 정정을 하는 기능이 들어가기도 한다.[1] 1940년대 벨 연구소에 근무하던 해밍은 주말에만 컴퓨터를 쓸 수 있었는데 이러한 오류 때문에 2주간 작업한 데이터를 몽땅 날려버렸고, 이에 해밍은 오류를 검출하고 정정할 수 있는 방법을 고안하기에 이른다. 그래서 ECC를 해밍 코드라고 부르기도 한다.
이러한 오류 정정 기법은 몇 년 뒤 클로드 섀넌의 논문 수학적 통신 이론을 통해 체계화 되었다.
2. 방식
2.1. 반복 (Repetition)
전송된 데이터의 오류를 검출하고 수정하는 가장 간단한 방법은 데이터를 필요한 만큼 반복해서 보내는 것이다.
보내고자 하는 코드가 10001101이라고 가정하자. 첫 번째 전송에서 수신측은 10011101을 받을 수도 있다. 이때 수신측은 받은 정보가 정확한지 아닌지 알 수 없다. 하지만 데이터를 여러 번 전송받으면 그럴 듯한 추측을 할 수 있다.
원본 : 10001101
수신 1 : 10011101
수신 2 : 10001101
수신 3 : 00001101
수신 4 : 10001101
수신 5 : 10001000
수신 6 : 11001101
6번의 반복되는 전송 과정에서 오류가 있었을 수도 있다. 위 예에서는 수신 2, 4를 제외하고 모든 과정에서 오류가 있었다. 하지만 수신측은 각 자리수마다 가장 많이 전송받은 값을 원본 데이터라고 통계적으로 추측할 수 있다.
수신 1 : 10011101
수신 2 : 10001101
수신 3 : 00001101
수신 4 : 10001101
수신 5 : 10001000
수신 6 : 11001101
======================
추측값 : 10001101
이처럼 단순히 같은 값을 반복해서 전송하는 것으로 데이터를 오류 없이 전송할 수 있다. 전송 회선의 신뢰도에 따라 반복 횟수를 늘리면 실질적으로 100%의 데이터 신뢰도를 가질 수 있다.
하지만 이 반복 전략은 두 가지 문제점이 있다.
1. 만약 악성 개체가 의도적으로 전송을 방해하며 선택적으로 오류를 발생시킨다면 이 전략은 취약해진다.
2. 전송하는 데이터의 양이 커지면 반복의 비용이 너무 커진다.
따라서 반복 전략은 데이터의 양이 적을 때만 유용하게 사용 가능한 방법이다.
2.2. 리던던시 (Redundancy)
데이터를 전송할 때 전송하는 데이터의 신뢰도를 높이기 위해 잉여 정보를 보낼 수 있다. 이 잉여 정보를 리던던시(Redundancy)라 한다. 리던던시를 활용하면 데이터 전송 시 신뢰도를 높일 수 있다.
보내고자 하는 코드가 "12345125"라고 가정하자. 이를 그대로 전송하는 대신
1 → "one"
2 → "two"
3 → "three"
4 → "four"
5 → "five"
라는 규칙 아래 인코딩(encoding)해서 "one two three four five one two five"라고 보내는 것이다.
이 데이터는 전송 과정에서 손상을 받아 "xne two thrae fiur frve one twl five"로 수신되었다고 하자. 영어를 할 줄 아는 사람 눈에는 이 데이터는 "one two three four five one two five"로 충분히 해석될 수 있을 것이다.
리던던시 전략의 정확한 알고리즘은 다음과 같다.
- 전송측과 수신측은 데이터가 몇 개의 심볼(symbol)로 이루어지고 이를 어떤 규칙으로 어떤 코드 워드(code word)에 대응시킬 건지를 미리 약속해 놓는다. 위 예에서 데이터는 "1", "2", "3", "4", "5" 총 5개의 심볼로 이루어져 있고, 코드 워드는 "one", "two", "three", "four", "five"이다.
- 전송측은 데이터를 전송할 때 약속한 규칙에 따라 코드 워드로 변환(encoding)하여 전송한다.
- 수신측은 인코딩된 데이터를 수신한다. 전송 과정 중에 오류가 발생했을 수도 있다. 수신한 데이터의 오류를 검출 및 수정한다. 해석할 수 없는 코드 워드들은 가장 근접한 코드 워드로 해석한다. 위 예에서 "xne"와 가장 가까운 코드 워드는 "one"이다. 따라서 이를 "one"으로 해석한다.
- 오류 검출 및 수정이 완료된 인코딩된 데이터를 디코딩(decoding)하여 원본을 얻는다.
2.3. 해밍 ECC (Hamming Error Correction Code)
해밍 ECC는 벨 연구소의 리처드 해밍(Richard Hamming)이 개발한 오류 검출 및 정정
해밍 ECC를 만드는 알고리즘은 다음과 같다.
- n비트의 데이터를 인코딩한다고 하자. n비트 데이터의 해밍 ECC 값은 총 (n + 2 + $$\left \lfloor \mathrm{lb}(n) \right \rfloor$$) 비트가 된다.[2] 이 결과값의 가장
- 2의 거듭제곱에 위치한 모든 비트는 패리티 비트(parity bit)로 한다.
- 다른 모든
2.4. 체크섬(Checksum)
체크섬은 일정한 수학적 방법에 따라 원본 데이터를 일정한 길이의 다른 데이터로 바꾼 것 이다. 주로 해시함수를 이용하며 보안과는 큰 관련이 없기 때문에 MD5를 써도 좋다.
가령 A가 B에게 Hello라는 문자열을 보낸다고 가정해보자. 체크섬방식의 오류정정코드를 이용하면 A는 Hello라는 원래 보내랴고 했던 문자열과 함께 Hello의 체크섬(이 상황에서는 1243으로 가정)을 보낸다. 그럼 B는 Hello와 1243이라는 체크섬을 받는데 전송 도중 오류가 발생해서 Helli라는 문자열과 1234라는 체크섬을 수신받았다고 가정해보자. 이 상황에서 B는 전송받은 Helli의 체크섬이 같이 전송받은 1234라는 체크섬과 일치하지 않음을 이용해 전송이 제대로 이루어 지지 않았음을 알고 재전송을 요청할 수 있다.
실제로 해시함수의 특성상 변형된 데이터와 체크섬이 일치할 확률이 극히 낮기 때문에 충분한 신뢰성을 이끌어 낼 수 있다.
3. ECC 램
데이터가 손실되면 엄청난 손해를 입는 서버, 데이터센터 등은 이를 방지하고자 ECC 기능이 내장된 램을 사용한다. 기본적으로 일반 램과 외형은 같지만 ECC 기능을 탑재한 대신 무지막지하게 비싼 가격과 영 좋지 않은 대역폭을 가지고 있다.[3] 하지만 일반램과는 비교도 하지 못할 정도의 신뢰성을 가지고 있어 속도보다는 신뢰성이 우선인 은행 서버나 금융계 컴퓨터에서 널리 사용된다.
ECC 램은 일반 램과 규격이 같고, 달라진거 라면 일반 램은 칩이 8개인 반면, ECC 램은 1개 더 박혀서 9개다. 규격이 같은 만큼 일반 메인보드에 꽂을 수 있지만 해당 메인보드가 ECC 램을 지원해야 한다.
노트북용 램은 DDR3까지 ECC 램이 없었지만 DDR4때 개발되어 널리 쓰이고 있다.
DDR5 규격에 이르러서는 높아지는 전송속도와 대역폭 때문에 일어나는 불안정성을 커버하기 위해 기본규격에도 ECC 기능이 탑재된다.