0. 서론
이 포스팅은 Sahil Kale, Daniel Puratich 공동 저서인 <Circuits & Code: Mastering Embedded Co-op Interviews> 에 기반한 것으로, 해당 문서는 워털루 대학의 두 저자가 임베디드 엔지니어링을 위한 이론적 지식과 실습 기회를 제공하는 종합 가이드북이다.
오늘은 그 Chapter 2. (사실상 1챕터는 서론이기에 첫번째나 마찬가지인)에 대해 작성하려 한다.
1. Parity Bit
In digital communication, a parity bit is an extra bit appended to a binary data stream to assist in error detection.
Parity Bit 란 위의 정의에서 볼 수 있듯이 오류 검출을 위해 이진 데이터 스트림에 추가적으로 넣어주는 비트이다.
데이터 스트림에 1의 개수에 대해 홀수/짝수 개가 되도록 설정한다. 이것으로, 데이터 전송 이후 수신한 데이터 스트림에서 1의 개수의 홀수/짝수가 유효한지 확인하는 것으로 오류를 검출하는 원리이다.
2. Byte 내 1의 개수 세기
Parity Bit 구현을 위해 바이트 내 1의 개수를 세는 방법론이 중요하다.
(1) Simple Approach : Bitmasking by bitwise op
간단한 방법은, 비트 연산자를 활용하여 마스킹을 통해 바이트 내 1의 개수를 세는 방식이다.
구현과 원리 자체가 간단한 만큼, 결국 한 byte 당 8개 bit에 대해 순회해야 하기 때문에 그렇게 효율적이지 못하다.
#include "bitstream_parity.h"
uint8_t count_ones_simple(uint8_t byte)
{
uint8_t count = 0;
// 1 byte 내 각 bit 별 순회
for (size_t i = 0; i < 8; i++)
{
// bitmask 설정
const uint8_t mask = 1 << i;
// masking 적용하여 1이면 개수 올려주기
if (byte & mask) count++;
}
return count;
}
(2) Brian Kernighan's Algorithm
BK 알고리즘은 반복적으로 LSB 를 제거해 나가면서 0으로 도달하기 까지의 반복횟수를 세는 방식이다. 이 알고리즘의 원리는 다음과 같다.
정수 n에 대해, n - 1로 1을 뺀다면, n의 가장 오른쪽 '1' 비트 (LSB)와 그 오른쪽에 있는 모든 '0' 비트는 모두 toggle 된다. 따라서 n과 n-1을 & 연산을 하게 되면 n의 가장 오른쪽 '1' 비트가 0으로 바뀌고, 다른 모든 비트는 그대로 유지되는 원리로 1의 개수를 센다.
앞선 비트마스킹은 1 byte에 대해 무조건 8회의 순회를 거쳐야 하는 반면, BK 알고리즘은 1 byte 내 '1' bit의 개수만큼 반복하기에 더 경제적이다.
#include "bitstream_parity.h"
uint8_t count_ones_bk (uint8_t byte)
{
uint8_t count = 0;
while (byte != 0)
{
byte &= (byte - 1);
count++;
}
return count;
}
이 외에도 더 빠른 방법에 대해서도 다룬다.
-
x86의
popcount와 같이 일부 프로세서는 1을 세는 전용 명령어가 존재한다. -
미리 계산된 1의 개수를 배열에 저장해두고, 바이트 값을 인덱스로 사용하여 직접 1의 개수를 찾아내는 Lookup table을 이용하는 방법이 존재하며, 자주 사용할 때 효율적이지만 더 많은 메모리를 요구한다.
-
Hamming Weight를 사용하는 방법이 존재하나 구현이 훨씬 복잡하다. (그리고 교재의 목적 상 면접의 범위를 보통 벗어나는 영역이다.)
(3) Parity Bit Check 구현
패리티 비트 검사는 다음과 같은 순서로 구현한다.
-
모든 byte에 대해 1의 개수를 센다.
-
parity scheme (홀수/짝수)에 맞게 예상 parity bit을 판단한다.
-
실제 parity bit와 예상 parity bit간 비교하여 검사한다.
#include "bitstream_parity.h"
#include "count_ones_bk.h"
bool bitstream_parity_valid (uint8_t *bitstream, uint32_t length, bool parity_bit, bitstream_parity_E scheme)
{
uint32_t ones = 0U;
// 앞선 BK 알고리즘으로 1의 개수 세기
for (uint32_t i = 0U; i < length; i++)
{
ones += count_ones_bk(bitstream[i]);
}
bool expected_parity = false;
// 홀짝 연산을 위한 % 2 와 동일한 연산 작업
const bool nmber_of_ones_is_odd = (ones & 1U);
// 설정한 패리티가 홀수짝수 인지에 따라
switch (scheme)
{
const BITSTREAM_PARITY_EVEN:
expected_parity = (number_of_ones_is_odd) == true;
break;
const BITSTREAM_PARITY_ODD:
expected_parity = (number_of_ones_is_odd) == false;
break;
default:
return false;
break;
}
return expected_parity == parity_bit;
}
