CRC 구현

LONG

1) CRC Generation 프로그램

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <conio.h>

void main( void )
{
  char bin_ger_poly[1024];
  char ascii_frame_data[1024];
  char bin_frame_data[1024];

  unsigned int  ger_poly    = 0;
  unsigned int  cnt_ger_poly  = 0;
  unsigned int  crc        = 0;
  unsigned int  crc_mask    = 0; 
  bool      msb_crc      = 0; /* MSB of crc */

  int i, j, cnt;  /* for loop and calculate */

  // initialization
  //
  memset( bin_frame_data, 0, 1024 );

  // input
  //
  printf("CRC generation\n");
  printf("input\n");
  printf("=> generator polynominal : ");
  scanf("%s", bin_ger_poly );  // input generator polynominal
  printf("=> original frame data ( ASCII ) : ");
  scanf("%s", ascii_frame_data );// input frame data
 
  // frame data ascii string -> binary string
  //
  cnt = 0;

  for( i = 0; i < strlen( ascii_frame_data ); i++ )
  {
    for( j = 7; j >= 0; j-- )
    {
      bin_frame_data[ cnt ] = ( ascii_frame_data[ i ] & ( 1 << j ) ) ? '1' : '0';
      cnt++;
    }
  }

  // make generator polynominal, crc mask
  //
  for( i = 1; i < strlen( bin_ger_poly ); i++ )
  {
    ger_poly <<= 1;
    ger_poly |= ( bin_ger_poly[i] == '1' ) ? 1 : 0;

    crc_mask <<= 1;
    crc_mask |= 1;

    cnt_ger_poly++;
  }   

  // adjust frame data
  //
  for( i = 0; i < cnt_ger_poly; i++ )
  {
    strcat( bin_frame_data, "0" );
  }

  // crc calculate
  //
  for( i = 0; i < strlen( bin_frame_data ); i++ )
  {
    crc <<= 1;
    crc |= ( bin_frame_data[i] == '1' ) ? 1 : 0;

    msb_crc = ( crc & ~crc_mask );
    crc &= crc_mask;

    if( msb_crc )
    {
      crc ^= ger_poly;
    }
  }

  // make binary frame data to transfer
  //
  for( i = 0; i < cnt_ger_poly; i++ )
  {
    bin_frame_data[ strlen( bin_frame_data ) - 1 - i ]
    = ( ( crc & 1 << i ) ? '1' : '0' );
  }

  // output
  //
  printf("output\n");
  printf("=> frame data & CRC : %s\n", bin_frame_data );
  getch();
}

 

[실행화면]

 

 

 

2) Error Detection 프로그램

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <conio.h>

void main( void )
{
  char bin_ger_poly[1024];
  char bin_frame_data[1024];

  unsigned int  ger_poly    = 0;
  unsigned int  crc        = 0;
  unsigned int  crc_mask    = 0; 
  bool      msb_crc      = 0; /* MSB of crc */

  int i;      /* for loop and calculate */

  // input
  //
  printf("error detection\n");
  printf("input\n");
  printf("=> receive frame data : ");
  scanf("%s", bin_frame_data );  // input frame data
  printf("=> generator polynominal : ");
  scanf("%s", bin_ger_poly );    // input generator polynominal
 
  // make generator polynominal, crc mask
  //
  for( i = 1; i < strlen( bin_ger_poly ); i++ )
  {
    ger_poly <<= 1;
    ger_poly |= ( bin_ger_poly[i] == '1' ) ? 1 : 0;

    crc_mask <<= 1;
    crc_mask |= 1;
  }   

  // crc calculate
  //
  for( i = 0; i < strlen( bin_frame_data ); i++ )
  {
    crc <<= 1;
    crc |= ( bin_frame_data[i] == '1' ) ? 1 : 0;

    msb_crc = ( crc & ~crc_mask );
    crc &= crc_mask;

    if( msb_crc )
    {
      crc ^= ger_poly;
    }
  }

  // output
  //
  printf("output\n");
  printf("=> %s\n", ( crc ) ? "error" : "no error" );
  getch();
}

 

[실행화면]

 

 

ARTICLE

기본원리

원리라기 보다는 간단한 예제부터 함 보자.
아담과 이브가 약속한 값 "1101" ( Generator Polynominal 이다. 이를 다항식으로 표시하면, 이다 -> 최고차가 3이기에 CRC-3 이라고도 할 수 있다. 진짜?) 일 때,
나머지 ( FCS : Frame Check Sequence )와 실제 전송할 비트열을 구해보자
잠깐, 여기서 더하기 빼기는 carry를 고려하지 않는 것을 원칙으로 한다
※ 1 + 1 = 0, 0 - 1 = 1 : 더하기 빼기 연산이 동일하며, 논리연산으로 XOR이다

이를 "modulo-2" 연산이라 한다

"01100001"에 다가 Generator Polynominal의 최대차수인 3 만큼 0을 붙히자.

그럼 "01100001000" 이 된다.
최대차수만큼 "0"을 붙이는 의미는 몰까? 수식등으로 여러 가지로 의미를 줄 수 있지만
내생각엔 원래의 데이터를 바꾸지 않고, 나머지 비트를 들어갈 수 있는 공간만 만들어 줘서

그 공간에 나머지를 넣으면, Generator Polynominal 나누었을 때 똑 떨어지겠금 하기 위함인거 같다.
실제 modulo-2 연산으로 나눗셈을 해보자

 

( 몬가 A4용지에 끄적끄적한다는 건 기분 좋은 일이다.. 간만에 나눗셈 했다. 사실은 나모 수식편집기로 하다가 속터져서.. )

나머지가 "11"이 나왔다. 이걸, 원래 비트열 "01100001" + "011" 하면 "01100001011"이 된다
이 "01100001011"를 이브한테 보내는 것이다.. 자 그럼 이브는 어떻게 할까?
"01100001011"를 "1101"로 나누어 보고 나머지가 나오는 지 안 나오는 지 확인을 하면 된다

 

자 "01100001011"가지고 확인 해보니 나머지가 나오지 않았다.
( 눈썰미가 있으신 분은 알겠쥐만,, 귀찮아서 포토샵 처리로..ㅍㅎㅎ )

 

 

하드웨어 구현

이 나눗셈을 기계가 알아먹도록 해보자
"1101" 사이에 buffer가 있다고 가정하자, 그리고 "1"로 연결된 부분은 XOR 게이트로 구성하자
단 젤 상위 비트는 loopback 시킨다. 이렇게 구성을 하고 input 단자에 데이터를 클럭에 따라 넣으면 아래와 같이 나온다..

 

결과는 "11" 이라는 값이 나왔다.

 

나눗셈을 보고 바로 하드웨어 구성을 하라고 하면, 나는 못하지 싶은데.. 일단 어떤 천재가 해놓았다. ( by Prange in 1957 )
대충 따라는 하겠는 데, 이게 왜 이렇게 되지 고민을 해보니, 쉽게 답이 안나왔다.
위 그림은 나눗셈과 하드웨어 구현( shift register implementation )을 한 것을 가지고
뚫어져라 처다 보니깐 공통점 몇가지를 발견할 수 있었다..
(그림에서 색깔로 표시했으니 알아서 보기 바란다. 몫, 나머지, 중간 계산과정, 등등

 일치하는 부분이 있다. 아직 내공이 부족해서 이런 설계를 할 수 있을 만큼 설명을 못하겠다..  )

소프트웨어 구현

shift register implementation을 프로그램으로 구현하기 위해서 좀 더 자세히 들여보자
위에서 나눗셈이랑 shift register implementation이랑 같은 거라는 걸 알았으니,
여기에선 나눗셈을 잠시 잊자. 나눗셈이랑 같이 생각하면 머리가 복잡해진다.. 헐..
그림에서 점선 앞부분,, 3비트 정보를 crc 변수에 담자. 왜 3비트인지는 위에서 유추해보자

unsigned int crc = 0; // 초기값은 0 이다

 

input값이 crc에 하나 하나 입력되는 것을 볼 수 있다

crc <<= 1;
crc |= ( bin_frame_data[i] == '1' ) ? 1 : 0;

빨간 박스 친 부분을 crc의 MSB라고 하자.

bool msb_crc = 0; /* MSB of crc */
....
msb_crc = ( crc & ~crc_mask );
crc &= crc_mask;

unsigned int 형이기에 3비트만 취하기 위해서 crc_mask을 사용하였다. ( 여기에 0x0007 이 들어감 )

msb_crc가 0 ( false ) 일 때는 crc 값의 변동없이 input 값이 차례 차례 들어간다
여기서도 XOR이 일어나지만 0과 XOR를 취하면 자기 자신이 나오기 때문이다
그럼 msb_crc가 1 ( true ) 일 때를 보자 

 

msb_crc가 1 ( true )일 때는 "100" 과 "101"이 XOR 취하여 "001"이 나온다.
자 여기서 "1101"이 아니라 "101"과 XOR를 한다. 즉 generator polynominal( ger_poly )의 최대차항은 제외시킨다.
msb_crc가 이미 그 역할을 해주기 때문이다. 1일 때만 XOR을 하니, "101"과 XOR 시키는 것과 마찬가지.
여기서 많이 헷갈렸는 데, 아래 나눗셈 하던 것을 잠시 상기 시켜보자

 

나눗셈을 보면, 뒤에 3비트만 XOR 취해도 나온다는 것을 알 수가 있다.
( 그리고 좀 더 생각해보면 MSB가 "0"일 때는 자신도 모르게 자리수 shift 했음을...
그래서 shift가 생략되어 있는 나눗셈 줄 수 보다 하드웨어 구현으로 계산된 줄 수가 더 길다 => 순전 개인차..헐 )
수식으로 접근하면 좀 더 명확하게 나오지 싶은 데, 이번 강좌는 이 정도로만 하자

if( msb_crc )
{
    crc ^= ger_poly;
}

이것이 XOR 취하는 부분이며, ger_poly 에는 "1101"가 아닌 최대차항이 생략된 "101"을 넣어야 된다.

실제 돌아가는 소스를 보자
아래에 데이터를 입력하면 CRC Generation하는 프로그램과 CRC Generation에서 생성된 데이터를 Error Detection하는 프로그램 두 개가 있다