각종 표기법 및 오류 검출 코드

각종 표기법

1.  BCD(Binary Coded Decimal)코드

• 네 개의 각 비트들이 $ 2^{n-1} $ 의 자릿수를 가지는 가중치 코드(weighted code)로서, 8421코드라고도 함
  • 주로 weight(자릿수)가 $ 2^{3}, 2^{2}, 2^{1}, 2^{0} $ , 즉 8, 4, ,2, 1 에 있어서 8421코드라고도 부름
  • ex) $ (792)_{10} $ = $ ( 0111 1001 0010 )_{BCD} $ 3증수 코드(excess-3 code) (잘 사용하지는 않는다)

3증수 코드

• BCD코드의 각 비트 패턴에 대하여 $ 3(0011_{2}) $ 씩을 더하여 만들어진 코드
  • ex) 2: 0010 + 0011 = 0101
  • ex) $ (826)_{10} $ -> $ (1011 0101 1001)_{excess-3} $

 

2.  밀집형 10진수 (packed BCD) (잘 사용하지는 않는다)

• 한 데이터 단어에 여러 개의 10진 숫자를 넣는 수 표현 방식
  • 4비트: 니블(nibble)
  • 16비트 단어 : 4개의 니블 저장
• 부호 표현: BCD에서 사용 않는 패턴을 마지막 니블에 배치
  • 음수: 1101
  • 양수: 1100
  • 부호 없는 수: 1111
• ex) +64: 0000 0110 0100 1100
• ex) -792: 0111 1001 0010 1101

 

3.  그레이 코드(Gray code) (응용 분야에서 주로 사용)

• 자릿수(weight)를 가지지 않는 코드
• 순서적으로 앞과 뒤의 숫자에 대한 비트 표현에서 단 한 개의 비트만 서로 다른 값을 가지는 코드
• 산술적 연산 불가
• Gray 코드는 아날로그 → 디지털 변환기(ADC)나 모터의 위치 센서처럼 하나씩 바뀌는 환경에서 오류를 줄이기 위해 사용돼.
• 2진수 $ \rightarrow $ 그레이 코드 (xor로 하는게 더 간단하지만 아직 안 배웠으므로 이렇게 한다)
  1. 2진수의 최상위 비트(Most Significant Bit)는 그대로 그레이 코드의 최상위 비트가 된다
  2. 우측으로 진행하며 인접한 두 비트들을 더하고, 올림수를 제외한다.
     

     

• 그레이 코드 $ \to $ 2진수
  1. 그레이 코드의 MSB는 그대로 2진수의 최상위 비트가 된다
  2. 2진 코드의 MSB를 그레이 코드의 다음 비트와 더하고, 올림수를 제외한다.
  3. 같은 방식으로 우측으로 이동하면서 모든 비트들에 적용한다.
     

     

 

4.  ASCII 코드(American Standard code for Information Interchange)

• 7비트를 이용하여 문자,숫자 혹은 특수 문자를 표현하는 국제표준 코드
• 존(zone)비트: 상위 3비트, 정보의 종류 지정
  • *ex) 011: 숫자( 7은 존비트를 이용하여 0110111이렇게 표현)
• 제어 기능 키: 32개 (BS, CR, 등)와 실제 프린트 될 수 있는 문자: 94개로 이루어짐
  

  

 

---

오류 검출 코드(error detection codes)

1. 패리티 비트(parity bit)

• 통신 과정에서 발생하는 비트 오류를 검출하기 위하여 추가되는 비트
• 홀수개의 비트 오류 검출만 가능하며, 정정은 불가능
  • 짝수 패리티(Even parity): 전체 데이터에 포함되는 1의 수가 짝수가 되도록 패리티 비트를 추가
  • 홀수 패리티(Odd parity): 전체 데이터에 포함되는 1의 수가 홀수가 되도록 패리티 비트를 추가

예시

ASCII코드:G = 100 0111을 보낸다고 가정하자
짝수 패리티는 ASCII코드 G의 비트들에서 1이 홀수 개이므로 상위 비트에 0을 추가하여 0100 0111을 보낼 것이다.
홀수 패리티는 ASCII코드 G의 비트들에서 1이 짝수 개이므로 상위 비트에 1을 추가하여 1100 0111을 보낼 것이다.

ASCII코드	짝수 패리티	홀수 패리티
100 0111	0100 0111	1100 0111

 

만약 100 0000같은 코드를 전송한다고 하면 비트들의 집합에서 1이 홀수 개이니
짝수 패리티는 상위 비트에 1을 추가한 1100 0000을 보낼 것이다
홀수 패리티는 상위 비트에 0을 추가한 0100 0000을 보낼 것이다

 

패리티 비트가 오류를 검출하는 방법

ASCII코드:G = 100 0111을 보낸다고 가정하자
이러면 짝수 패리티는 0100 0111를 보낼 것이다 그런데 데이터 전송 중 비트가 깨져 도착한 비트가 0101 0111이라고 한다면 짝수 패리티에서는 최종 도착 비트에서 1이 홀수이니 오류를 검출 할 수 있다.
,단 짝수 개의 비트가 깨질 경우는 오류를 검출 할 수 없다(이는 직접 해보면 그 이유를 바로 알 수 있다)

 

2.  2차원 패리티 방식

• 여러 데이터 단어들에 대하여 수평 방향뿐 아니라 수직 방향으로도 패리티 비트를 추가하는 방식
• 짝수 패리티를 수평 방향으로 둔다. (이때 비트를 앞 혹은 뒤 아무곳에나 해도 상관없다)
• 홀수 패리티를 수직 방향으로 둔다.

경우에 따라 여러 bit error를 검출 할 수 있으나 홀수 개의 비트에서 오류 검출을 목표로 한다(특히 1개의 비트에 대해서)

3. 해밍 코드(Hamming code) 데이터 비트 + 패리티 비트

• 오류 검출뿐 아니라 오류 정정도 가능한 코드 (단, 1bit에 한해서만 정정 가능, 여러 비트가 오류시 이상한 결과값 도출)
• 다수의 패리티 비트 추가
  • 패리티 비트 수: K, 데이터 비트 수 : d 일 때, $ 2^{k} -1 \geqslant d + k $
  • 이 때 k는 조건을 만족하는 최소를 지정하는게 좋다 (k가 클수록 용량 낭비)
  • ex) d=4 $ \rightarrow $ k=3
  • 패리티 비트의 자리는 $ 2^{n} $ 에서 n=0 부터 k-1까지다. ( k=3 -> 0,1,2,4가 패리티 비트)
  • 각 패리티 비트에서 해당하는 자릿수와 같은 비트가 포함된 다른 수의 비트에서 1의 개수가 짝수이면0, 홀수이며 1로 세트

 

  해밍 코드 예시

• 데이터가 0101인 경우, d=4 이고 k=3
• 패리티 비트가 들어갈 1,2,4를 제외한 자리 7,6,5,3이 0101
  

  7(111)	6(110)	5(101)	4(100)	3(011)	2(010)	1(001)
  0	1	0	$ p_{4} $	1	$ p_{2} $	$ p_{1} $

이렇게 표시된 상태에서 100 맨 좌측에 1이 포함한 비트 번호는 7(111), 6(110), 5(101) 이고 이 비트들은 각각 0, 1, 0, 즉 1이 홀수개이므로 4(100)에 1세트

	7(111)	6(110)	5(101)	4(100)	3(011)	2(010)	1(001)
	0	1	0	0	1	$ p_{2} $	$ p_{1} $

2(010)는 가운데에 1이 들어간 비트 번호7(111), 6(110), 3(011)이 각각 0,1,1이므로 0세트

비트 번호	7 (111)	6 (110)	5 (101)	4 (100)	3 (011)	2 (010)	1 (001)
값	0	1	0	0	1	0	$p_{1}$

같은 방식으로 1(001)은 111, 101, 011 이 각각 0, 0, 1이므로 1세트

비트 번호	7 (111)	6 (110)	5 (101)	4 (100)	3 (011)	2 (010)	1 (001)
값	0	1	0	0	1	0	1

최종적으로 데이터 0101인 경우의 해밍 코드는 010 0101이 된다.

해밍코드의 신드롬 비트(syndrome bit)

• 해밍 코드에서 오류를 검출 했을 경우 정정을 위한 신드롬 비트
• 신드롬 비트 조합 = 오류 발생한 비트 위치 번호

예시

만약 010 1101을 보냈는데 수신된 해밍코드가 010 0101 일 때

 

$ s_{1} $ : 비트 번호(1,3,5,7) = 1, 1, 0, 0 이므로 0세트
$ s_{2} $ : 비트 번호(2,3,6,7) = 0, 1, 1, 0 이므로 0세트
$ s_{4} $ : 비트 번호(4,5,6,7) = 0, 0, 1, 0 이므로 1세트

 

신드롬 단어가 100, 즉 4을 가리키므로 4번 비트를 반전시키면 010 1101으로 오류가 해결된다.

데이터를 전송할 때 오류가 발생한다면 대게는 1bit만 오류가 발생할 확률이 높기에 1bit를 정정할 수 있으면 충분하다