컴퓨터 구조 - 2-3. 데이터의 표현(디지털 코드, 에러 검출 코드)
이 포스트는 패스트캠퍼스의 “컴퓨터 공학 전공 필수 올인원 패키지 Online.” 강의를 보고 정리한 내용입니다.
데이터의 표현
컴퓨터에서 데이터를 표현하는 방법에 대해서 알아보자.
1. 디지털 코드
1-1. BCD Code
BCD Code(Binary Coded Decimal Code: 2진화 10진 코드, 8421 코드)란 큰 값을 가지는 십진수를 2진 변환하는 연산과정을 생략하기 위해 Unpacked Decimal 처럼 비 수치 데이터로서 사용되는 간단한 포맷이다.
십진수의 각 자리수를 4bit의 2진값으로 표현하는 방식을 사용한다.
| 10진수 | BCD Code |
|---|---|
| 0 | 0000 |
| 1 | 0001 |
| 2 | 0010 |
| … | … |
| 9 | 1001 |
| 10 | 0001 0000 |
| 11 | 0001 0001 |
| … | … |
| 99 | 1001 1001 |
| 100 | 0001 0000 0000 |
| 746 | 0111 0100 0110 |
1-2. 3초과 코드(Excess-3 코드)
옛날에 사용하던 코드이다. 기사시험에 나오는 경우가 있다. 10진수를 4자리의 2진값으로 표현한 뒤 3을 더해준다.
| 10진수 | BCD Code | 3초과 코드 |
|---|---|---|
| 0 | 0000 | 0011 |
| 1 | 0001 | 0100 |
| 2 | 0010 | 0101 |
| … | … | … |
| 7 | 0111 | 1010 |
| 8 | 1000 | 1011 |
| 9 | 1001 | 1100 |
신기하게도 가운데를 중심으로 대칭되는 값들이 1의 보수 관계를 가진다.(0 과 9, 1 과 8, 2 와 7, …)
2. 에러 검출 코드
2-1. 패리티 비트
초창기에 사용되던 에러 검출 코드이다. ASCII 코드에서 사용되는 예를 살펴보자.
ASCII 코드는 1963년 미국 ANSI에서 표준화한 7비트 부호체계이고, 여기에 1비트의 패리티 비트를 추가해 1바이트로 구성된다.
ASCII 코드의 값이 전송 도중 신호가 변질되지는 않았는지 확인하기 위해 1비트의 패리티 비트를 사용하는데, 변질을 검출하는 기준은 1 값을 가지는 비트의 개수이다.
| Character | ASCII(binary) | 짝수 패리티 | 홀수 패리티 |
|---|---|---|---|
| A | 1000001 | 0 1000001 | 1 1000001 |
| B | 1000010 | 0 1000010 | 1 1000010 |
| C | 1000011 | 1 1000011 | 0 1000011 |
이렇게 전송된 1의 개수가 짝수인지 홀수인지를 보고 변질을 판단한다. 단, 동시에 짝수개의 신호가 변질이 되면 검출할 수 없다는 한계가 있다.
이러한 개념이 발전해 해쉬 코드, 해쉬 알고리즘 등의 보안 기술이 생겼다.
2-2. 해밍 코드
개념
패리티 비트 하나로는 한계가 있기 때문에 나온 코드이다. 데이터 전송 과정에서 1 비트의 오류를 검출하고 정정까지 할 수 있다.(ECC:Error Correction Code 의 일종)
패리티 비트를 여러개 추가하기 때문에 에러의 위치또한 알아낼 수 있게된다.
사용방법 - 패리티 비트 추가
추가되는 패리티 비트의 개수는 다음 조건에 맞게 설정한다.
p : 패리티 비트 개수, n : 데이터 비트 개수
$2^p >= p + n + 1$
예를들어 데이터 비트가 7개라면, 위 조건을 만족하는 최소 패리티 비트수는 $p_{min} = 4$ 비트가 된다. 따라서 4개의 패리티 비트를 추가해야 하는데, 추가하는 위치는 $2^x$ 위치 즉 1, 2, 4, 8 위치가 된다.
이제 추가한 패리티 비트를 어떻게 사용하는지 확인해보자.
7비트의 데이터는 다음과 같다.
| 자리 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|
| 데이터 | 1 | 1 | 0 | 1 | 0 | 0 | 1 |
따라서 패리티 비트는 다음 위치에 추가되어야 한다.
| 자리 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 값 | $p_1$ | $p_2$ | 1 | $p_3$ | 1 | 0 | 1 | $p_4$ | 0 | 0 | 1 |
이렇게 추가된 패리티 비트는 각각 자신의 비트셋을 가진다. 비트셋의 설정 기준에 대한 자세한 설명은 위키피디아 를 참조하고, 간단하게만 말하자면 다음과 같다.
- 시작은 패리티 비트 자신이고, $p_i$ 부터 길이 $2^{i - 1}$ 만큼 잘라서 첫 부분 그룹을 만든다.
- 부분 그룹이 끝나고 부분 그룹과 똑같은 길이만큼 건너 뛴 위치부터 다음 그룹이 된다.
- $p_2$ 라면, 첫 부분 그룹은
2, 3이고 끝에서 길이 2만큼 건너뛰고 다음 그룹(6, 7)을 묶는다. - $p_3$ 라면, 첫 부분 그룹은
4, 5, 6, 7이고 끝에서 길이 4만큼 건너뛰고 다음 그룹(12, 13, 14, 15)을 묶어야 하지만 없으니 생략한다.
- $p_2$ 라면, 첫 부분 그룹은
위와 같은 규칙을 따라서 만들어진 예제의 비트셋은 다음과 같다.
| 패리티 비트 | 비트셋(자리 기준) |
|---|---|
| $p_1$ | $\lbrace 1, 3, 5, 7, 9, 11 \rbrace$ |
| $p_2$ | $\lbrace 2, 3, 6, 7, 10, 11 \rbrace$ |
| $p_3$ | $\lbrace 4, 5, 6, 7 \rbrace$ |
| $p_4$ | $\lbrace 8, 9, 10, 11 \rbrace$ |
이제 홀수 패리티 혹은 짝수 패리티에 맞춰서 각 패리티 비트를 비트셋을 보고 설정한다. 예제에서는 홀수 패리티를 사용해보겠다.
$p_1$ 의 비트셋의 데이터를 보면 $\lbrace p_1, 1, 1, 1, 0, 1 \rbrace$이므로 홀수 패리티를 만족시키려면 $p_1 = 1$ 이 된다.
마찬가지로 나머지 패리티 비트를 구하면 다음과 같다. $p_2 = 0, p_3 = 1, p_4 = 0$
이제 각각의 비트셋에서 패리티를 보고 오류를 검출할 수 있다.
사용 방법 - 오류 정정
완성된 해밍 코드로 어떻게 오류를 정정할까? 해밍 코드는 1비트의 오류를 정정할 수 있다. 오류를 정정하는 방법은 다음과 같다.
- 각각의 패리티 비트의 비트셋의 오류를 검출해본다.
- 오류가 검출된 비트셋의 패리티 비트 $p_i$ 의 번호 $i$ 에 기반하여 $2^{i-1}$ 를 누적한다.
- 모든 비트셋을 확인해보고 누적된 값에 해당되는 위치의 데이터가 오류가 되므로 1 은 0 으로, 0 은 1 로 정정한다.
예제에서 완성된 해밍 코드는 다음과 같다.
| 자리 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 값 | 1 | 0 | 1 | 1 | 1 | 0 | 1 | 0 | 0 | 0 | 1 |
여기서 8번 자리의 비트가 1로 변질되었다고 가정하자.
| 자리 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 값 | 1 | 0 | 1 | 1 | 1 | 0 | 1 | 0 | 0 | 1 |
이 경우 각 패리티 비트의 비트셋의 오류를 홀수 패리티로 검사해본다.
| 패리티 비트 | 비트셋(값) | 에러 여부 |
|---|---|---|
| $p_1$ | $\lbrace 1, 1, 1, 1, 0, 1 \rbrace$ | 정상(홀수) |
| $p_2$ | $\lbrace 0, 1, 0, 1, 0, 1 \rbrace$ | 정상(홀수) |
| $p_3$ | $\lbrace 1, 1, 0, 1 \rbrace$ | 정상(홀수) |
| $p_4$ | $\lbrace 1, 0, 0, 1 \rbrace$ | 에러!!(짝수) |
에러가 검출된 비트셋을 기준으로 값을 누적하면 $2^{4 - 1} = 2^3 = 8$, 즉 의도한 대로 8번 비트에 변질이 된 걸 확인할 수 있다.