x진수, 바이트, 비트 연산(feat. 순환중복검사 CRC)

SDR를 실습하다보니, RDS를 포함한 다수의 통신에 에러체크를 위하여 CRC(순환중복검사, Cyclic redundancy check)를 사용하는 것 알게 되었습니다. 또 CRC를 구하기 위해서는 비트연산을 해야하고 그래서 이와 연관된 것들을 공부하고 정리해 봅니다.

 

① x진수, 바이트, 비트연산

>>> 0b11010011101100     # 2진수 표현 13548 >>> 0xb     # 16진수 표현 11 >>> bin(11)     # 2진수로 변환 '0b1011' >>> list( b'hello' )     # 바이트를 10진수 리스트로 변환 [104, 101, 108, 108, 111] >>> bytes([104, 101, 108, 108, 111])     # 10진수 리스트를 바이트로 변환 b'hello' >>> bin( 0b11010011101100 ^ 0b1011<<10 )[2:].zfill(14)     # 비트 시프트, 비트 XOR '01100011101100'

 

이밖에 비트 &(AND), |(OR), ^(XOR), ~(NOT) 연산자가 있습니다.

 

② CRC (순환중복검사)

CRC(순환중복검사)는 네트워크 등을 통하여 데이터를 전송할 때 전송된 데이터에 오류가 있는지를 확인하기 위한 체크값을 결정하는 방식중에 하나입니다. CRC는 구현이 간단할 뿐만 아니라, 메시지 내 오류 기호가 연속적으로 연속된 버스트 오류 감지에 특히 적합하다는 장점이 있습니다. 이는 버스트 오류가 자기 및 광학 저장 장치를 포함한 많은 통신 채널에서 흔히 발생하는 전송 오류이기 때문에 중요합니다. 단 CRC 값을 갖는 다른 데이터를 만들기가 쉽고, 따라서 데이터 무결성을 검사하는 데는 (MD5 등의 함수 처럼) 사용될 수는 없다고 합니다.

 

그럼 구체적인 예시와 코드로 설명을 해보겠습니다.

crc_remainder 함수는 임의의 비트스트링과 주어진 특정 다항식으로부터 계산되는 나머지 checksum를 구합니다.

여기서는 14비트 메시지('11010011101100')를 4비트 다항식('1011')으로 비트별 나눗셈(XOR계산)을 한 뒤, 3비트 나머지('100')를 붙여 전송합니다. 

이후 수신한 17비트 데이터( '11010011101100'+'100')에서 4비트 다항식 ('1011')으로 다시 비트별 나눗셈을 한 결과, 당연히 전송오류가 없다면 마지막 3비트가 모두 0이므로 이것으로 전송오류가 없는지 crc_check함수로 확인합니다.

 

def crc_remainder(bitstring, polynomial, filler):

    """Calculate the CRC remainder of a string of bits using a chosen polynomial.

    filler should be '1' or '0'.

    """

    polynomial = polynomial.lstrip("0")   # left '0' 제거

    l = len(bitstring)

    padding = (len(polynomial) - 1) * filler   # 9*'0'

    arr = list(bitstring + padding)

    while "1" in arr[:l]:   # while ('1' in '00') : print('break')

        cur_shift = arr.index("1")   # list('0011').index('1')

        #print(cur_shift)

        for i in range(len(polynomial)):

            arr[cur_shift + i] \

            = str(int( polynomial[i] != arr[cur_shift + i] ))

    return "".join(arr)[l:]

def crc_check(bitstring, polynomial, checksum):

    """Calculate the CRC check of a string of bits using a chosen polynomial."""

    polynomial = polynomial.lstrip("0")

    l = len(bitstring)

    padding = checksum

    arr = list(bitstring + padding)

    while "1" in arr[:l]:

        cur_shift = arr.index("1")

        for i in range(len(polynomial)):

            arr[cur_shift + i] \

            = str(int( polynomial[i] != arr[cur_shift + i] ))

    return ("1" not in "".join(arr)[l:])

print( crc_remainder('11010011101100', '1011', '0') )

>>> 100

print( crc_check('11010011101100', '1011', '100') )

>>> True

 

 

아래 링크에 있는 코드를 더 간결하고 직관적으로 나름 고민해 보았으나, 이미 파이썬스러운 완전한 코드같다는 결론을 내고 그만두었습니다. 아무래도 위 코드가 최선인것 같고, 파이썬스러운 코드를 좀 배웠습니다.

 

 

<참고자료>

1. 순환 중복 검사 - 위키피디아

2. 파이썬 코딩 도장: 47.1 비트 연산자 사용하기