CRC-16/32

CRC(Cyclic Redundancy Check)는 시리얼 전송에서 데이타의 신뢰성을 검증하기 위한 에러 검출 방법의 일종이다.

간단한 에러 검출방법으로는 parity 비트에 의한 방법과 check-sum에 의한 에러 검출 방법이 있지만 parity 비트에 의한 방법은 데이타 중에 한꺼번에 2비트나 4비트가 변하게 되면 검출을 할 수 없고, check-sum에 의한 방법은 한 바이트에서 +1, 다른 바이트에서는 -1로 에러가 생기는 경우만 해도 에러는 검출 되지 않는다. 즉, 이들 방법으로는 에러를 검출해 낼 수 있는 확률이 대단히 낮다.

CRC에 의한 방법은 높은 신뢰도를 확보하며 에러 검출을 위한 오버헤드가 적고, 랜덤 에러나 버스트 에러를 포함한 에러 검출에 매우 좋은 성능을 갖는 것을 특징으로 한다.

이러한 CRC 방법으로 보통 2가지 종류가 사용 되는데, 원칩 마이크로 프로세서와 같이 간단한 용도에서는 CRC-16 이 사용되고, 이보다 더욱 정확한 에러 검출이 필요한 경우에는 CRC-32를 사용한다.

ZIP,ARJ,RAR 과 같은 압축 프로그램이나 플로피 디스크 등의 데이터 검증 용도에 널리 사용되고 있다.

* CRC 검증의 에러 확률 p = 2^-k (여기서 k는 CRC 비트수)
예를들어 CRC16의 경우 에러 확율은 p = 2^-16 = 1 / 65536 = 0.0000152587890625 = 0.0015%
반대로 데이터의 신뢰성은 1 - p = 0.9999847412109375 = 99.9984 %

기본 원리

n 비트의 주어진 정보가 있을때, 이를 k 비트 만큼 자리를 올리고 미리 약속한 k 비트의 키 값으로 나누면 r 비트의 나머지가 남게 된다. 송신측에서는 원래의 정보 비트를 k 비트 자리 올린 것에 r 비트의 나머지를 더해서 n+r 비트의 데이타를 만들어 보낸다.
수신측에서는 수신된 n+r 비트의 데이타를 키 값으로 나누어 보고 나머지가 정확히 0 이 되는지를 검사하면 된다.

이 때 k 가 16 비트이면 CRC-16, 32비트이면 CRC-32 가 되고 키 값으로는 수학자 들에 의해 정해진 값을 주로 사용한다.
CRC-16 에는 0x8005, CRC-32 에는 0x04c11db7 이 많이 사용된다. 그리고 r 비트의 나머지를 Frame Check Sequence(FCS)라고 부른다.

다항식 표현 방법을 통해 CRC 계산 방법을 살펴보자.

(1) 2진 다항식으로 표시

예) 비트열 101 --> 다항식 x² + 1

정보 다항식: 데이터 비트열의 다항식으로 P(x) = p_n x^n-1 + ... + p₃x² + p₂x¹ + p₁
CRC 다항식: CRC 생성을 위한 다항식으로 G(x) (미리 정해진 키 값)
몫: Q(x)
나머지: R(x)
전송 데이타: T(x)

(2) CRC 계산 방법

P(x)를 k 비트 만큼 자리를 올리고( P(x)에 x^k를 곱하는 것과 동일) G(x)로 나누면

x^k P(x) = Q(x)*G(x) +/- R(x) 이다.

(k는 CRC 다항식의 최고 차수)

R(x) = d_k x^k-1 + .. + d₂x¹ + d₁ ( R(x)의 최고 차수는 k-1)

비트열 d_k ... d₂ d₁ 을 FCS(Frame Check Sequence) 라 함

위 식에서 x^k P(x) + R(x) 는 Q(x)*G(x) 와 같다.

즉, x^k P(x) + R(x) 는 G(x)의 배수이므로 G(x) 로 나누면 나머지가 0 임을 알 수 있다.

결과적으로 전송되는 데이터 비트열 : p_n ... p₃ p₂ p₁ d_k ... d₂ d₁

즉, 전송 T(x) = x^k P(x) + R(x)

예) 데이터 비트열 110011 즉 P(x) =x⁵+x⁴+x¹+x⁰, CRC 다항식G(x) = x⁴+x³+1, 즉 11001일 경우 FCS와 전송되는 비트열은?

x^kP(x) = x⁴ (x⁵ + x⁴ + x¹ + 1) = x⁹ + x⁸ + x⁵ + x⁴, 비트열로 표시하면 1100110000

                   100001
          ____________
11001 | 1100110000
            11001
          ____________
                     10000
                     11001
          ____________
                       1001    

x^kP(x) = Q(x)G(x) - R(x)에서

Q(x) = x⁵ + x⁰ 이므로,

R(x) = x³ + x⁰, ---> FCS는1001

따라서 전송되는 비트열 1100111001

연산의 최적화

CRC의 계산은 일반 나눗셈 명령을 이용해 구현할 수 없다. 1비씩 shift 하면서 XOR 연산을 통해 나머지를 구해야 한다.
하지만 정보 비트에 대해 하나하나씩 연산을 하는 것에는 분명 속도 개선의 여지가 있다.
실제 계산 시에는 모든 바이트에 대해 CRC 다항식에 대한 CRC값을 계산해 표로 만들어 두고 들어오는 데이타를 인덱스로 삼아 계산값을 바로 얻는 방법을 사용 한다.

CRC-16 C소스 : crc16h.c
CRC-32 C소스 : crc32h.c

8051 어셈블리 CRC-8 소스 : 8051crc8.zip
8051 어셈블리 CRC-16 소스 : 8051crc16.zip

인터넷 주소가 고갈되기 직전이라는 우려는 이제 거의 잦아들었다. 느리긴 해도 인터넷 프로토콜 버전 4(Internet Protocol Version 4, IPv4)에서 IPv6으로의 이동이 확실히 시작됐고, 많은 이가 예상했던 인터넷 주소 대란을 방지하기 위한 소프트웨어도 나와 있기 때문이다. IPv6의 현황과 전망을 설명하기 전에 인터넷 주소의 초창기를 잠깐 살펴보자.

IPv6은 무엇이고 왜 중요한가
IPv6은 인터넷 전역에서의 기기를 식별해 그 위치를 알 수 있게 해주는 인터넷 프로토콜의 최신 버전이다. 인터넷 커뮤니케이션을 위해 인터넷을 사용하는 모든 기기는 IP 주소를 통해 식별된다. 그런 면에서 편지를 쓸 때 알아야 하는 주소 및 우편 번호와 비슷하다.

이전 버전인 IPv4는 32비트 주소 체계를 사용해 총 43억 개의 기기를 지원한다. 과거에는 그 정도로 충분하다고 생각했다. 그러나 인터넷, 개인용 컴퓨터, 스마트폰에 이어 이제는 사물인터넷 기기까지 확산되면서 필요한 주소의 수도 그만큼 늘었다.

다행히 인터넷 엔지니어링 태스크 포스(Internet Engineering Task Force, IETF)는 20년 전부터 이를 대비했다. IETF는 1998년 128비트 주소 체계를 사용해 2,128개의 주소를 지원하는 IPv6을 고안했다. 1~3자리 수 4개가 한 세트가 되는 IPv4와 달리 IPv6은 콜론으로 구분되는 4자리의 16진수 8개 묶음을 사용한다.

IPv6의 장점과 도입 현황
IETF는 IPv6를 만들면서 IPv4에 비해 더 개선된 부분을 포함했다. IPv6 프로토콜은 더 효율적으로 패킷을 처리하고 성능을 개선하고 보안을 강화할 수 있다. 또한 라우팅 테이블을 더 계층화해 인터넷 서비스 제공업체가 라우팅 테이블의 크기를 줄일 수 있게 해준다.

이러한 모든 장점을 감안하면 업계가 IPv4에서 IPv6으로 전환하는 데 오랜 시간이 걸린다는 점이 이상하게 보일 수 있다. 전환이 지연되는 이유 가운데 하나는 네트워크 주소 변환(Network Address Translation, NAT)이다. NAT는 각기 하나의 퍼블릭 IP 주소를 사용하는 NAT 게이트웨이를 통해 프라이빗 네트워크의 수많은 개별 IP 주소로 트래픽을 보낼 수 있게 해준다.

통신업체와 ISP들은 IPv6을 가장 먼저 구축하기 시작한 그룹이며 그 가운데서도 모바일 네트워크가 가장 앞서 있다. 예를 들어 T-모바일 USA는 트래픽의 90% 이상을 IPv6으로 처리하며 버라이즌 와이어리스가 82.25%로 그 뒤를 따르고 있다. 월드 IPv6 런치(World IPv6 Launch)에 따르면, 컴캐스트와 AT&T는 각각 네트워크의 63%와 65%가 IPv6이다.

주요 웹사이트가 그 뒤를 따른다. 월드 IPV6 런치 측에 따르면, 알렉사 상위 1,000개 웹 사이트 가운데 현재 IPv6을 통해 접속이 가능한 비율은 30%가 조금 못된다.

IPv6 구축에서 기업은 뒤처져 있다. 인터넷 소사이어티(Internet Society)의 "2017 IPv6 구축 현황" 보고서에 따르면, IPv6을 본격적으로 사용하는 기업의 비율은 1/4에 약간 못 미친다. 이유는 복잡성, 비용, 완료되기까지 소요되는 시간 등이다. 또한 일부 프로젝트는 소프트웨어 호환성 문제로 지연됐다. 예를 들어 2017년 1월 한 보고서에 따르면, 윈도우 10의 버그로 인해 마이크로소프트 시애틀 본사에 IPv6으로만 구성된 네트워크를 구축하려는 계획이 지연되기도 했다.

IPv6, 본격적인 구축은 올해부터 
인터넷 소사이어티 측은 IPv4 주소의 비용이 2018년에 최고조에 이르고 이후 IPv6 구축이 50%를 돌파하면서부터 하락할 것으로 예상했다. 현재 구글에 따르면 전 세계 IPv6 도입 비율은 20 ~ 22%다(미국의 경우 약 32%).

인터넷 소사이어티는 IPv4 주소 가격이 하락하기 시작하면 기업은 IPv6 구축 비용을 충당하기 위해 기존 IPv4 주소를 팔게 될 것으로 예상했다. 깃허브의 한 게시물에 따르면, 매사추세츠 공과 대학은 이미 IPv4 주소를 팔았다. 이 대학은 2,000양 개(2 뒤에 0이 31개가 붙는 수)의 IPv6 주소를 보유한만큼 함께 보유한 800만 개의 IPv4 주소는 "과잉"이고, 따라서 팔아도 현재 또는 미래의 주소 수요에는 영향이 없을 것으로 판단했다는 것이다.

또한 구축이 늘어날수록 IPv6 서비스를 무료로 제공하면서 IPv4 주소 사용에 대해 비용을 청구하는 기업이 증가하게 된다. 영국의 ISP 미딕 비스트(Mythic Beasts)의 경우 "IPv6 연결이 표준이고 IPv4 연결은 옵션으로 제공되는 부가 서비스"라고 말했다.

IPv4, 천천히 사라질 뿐 폐기는 없다 
2011년~2018년 사이 대부분의 세계에서 신규 IPv4 주소가 "고갈"되지만 IPv4 주소는 앞서 언급했듯이 판매 후 재사용되므로 완전히 사라지지는 않으며, 남은 주소는 IPv6 전환에 사용된다.

공식적으로 정해진 폐기 날짜는 없으므로 어느 날 갑자기 인터넷 접속이 안 될까 걱정할 필요는 없다. 전환되는 네트워크가 증가하고 IPv6을 지원하는 콘텐츠 사이트가 늘어나고 IPv6 기능이 있는 장비로 업그레이드하는 최종 사용자가 늘어남에 따라 세계는 IPv4에서 천천히 멀어질 것이다.

원문보기: 
http://www.itworld.co.kr/news/108307#csidx3c6ade770fefa4683f8b5ea1c1633c5