정상훈, 정광식, 윤성식 http://samplesoft.co.kr 2008-07-09 목차 1. 개요... 2 2. 본문... 3 2.1 CRC5 계산방법... 3 2.2 MATLAB을이용한 CRC5 소스... 6 2.2.1 MATLAB을이용한 CRC계산소스개요... 6 2.2.2 데이터입력... 7 2.2.3 FRAME #, CRC5 연산식시프트... 8 2.2.4 CRC5 연산식을이용한 XOR계산... 9 2.2.5 CRC값을 5비트변환... 11 2.2.6 CRC값에 3비트역변환 (INVERSE) 와최종값출력... 12 2.3 C언어를이용한 CRC5 소스... 13 2.3.1 C언어를이용한 CRC계산소스개요... 13 2.3.2 변수선언및데이터입력... 14 2.3.3 FRAME #, CRC5 연산식시프트... 15 2.3.4 CRC5 연산식을이용한 XOR계산... 16 2.3.5 CRC값에 3비트역변환 (INVERSE) 와최종값출력... 17 3. 결론... 18 주작성자 : 한국산업기술대학교메카트로닉스공학과 magic-815@hanmail.net 주소 : 경기도시흥시정왕동한국산업기술대 TIP 1539호 : 한국산업기술대학교메카트로닉스공학과 plantlight@empal.com : 한국산업기술대학교메카트로닉스공학과 hanbomul@kpu.ac.kr INBECS 주소 : 경기도시흥시정왕동 2121번지한국산업기술대 TIP 408호
1. 개요컴퓨터를비롯한 USB와여러장치들사이에정보교환이필요한경우장치에서다른장치로정확한데이터를전송해야한다. 하지만전송하는중에데이터는열, 자기장, 및여러형태의전기등외부환경요인에의해간섭을받을수있다. 따라서데이터를전송할때신뢰성을가지고전송하기위해서는오류를검출하는코드가필요하다. CRC (Cyclic Redundancy Checks, 순환잉여검사 ) 는데이터전송과정에서발생하는오류를검출하기위해사용하는방식이다. 데이터를전송하기전에주어진데이터를생성다항식을이용하여 CRC 부호화과정을거치고, 부호화를마친값은송신데이터의마지막에위치하고있는 CRC필드에덧붙여전송한다. 그리고수신쪽은데이터를복호화하여값의오류여부를판단하고오류가없을시, 송신데이터를수신한다. [ 그림 1] CRC SYSTEM CHART 페이지 2 / 18
2. 본문내용 드는 Frame # 필드의데이터만을이용하여계산하고산출된다. 2.1 CRC5 계산방법 USB의프로토콜은 SOF 패킷, 토큰패킷, 데이터패킷, 핸드세이크패킷으로구성된다. 모든패킷은 SYNC (synchronization) 필드로시작하며, SYNC 필드다음에는 PID(Packet Identifier Field) 필드가있다. 다음으로 SOF 패킷은 [ 그림2.1.3] 과동일하게 11비트로구성된 Frame Number 필드가있으며 Token 패킷의경우는 Frame Number 필드대신 7 비트의 ADDR(Address) 필드와 4 비트의 ENDP(Endpoint) 필드로구성되어있다. CRC5필드는이들필드뒤에위치하고있으며, 이값이오류검출역할을한다. CRC는 5비트로구성되었으며 Token CRC와 Data CRC 두종류가 USB 프로토콜에사용된다. 그중 Token CRC의연산식은다음과같다. G(X)= X X 1 [ 그림2.1.1] 연산식변환과정이연산식은 0과 1의패턴으로나타낼수있으며, 그값은 [ 그림 2.1.1] 과같이 100101 (2) 로나타낸다. SYNC, PID, ADDR, ENDP, Frame # 필드가운데실제 CRC5필드데이터의영향을미치는필드는 Frame # 필드이며, 나머지필드는 CRC5필드데이터에영향을미치지않는다. 따라서 CRC5필페이지 3 / 18
[ 그림2.1.2] USBTracer Bus And Protocol Analyzer [ 그림2.1.3] Packet0 s Bits display [ 그림2.1.3] 의값을예를들어 CRC연산과정을설명하면, 현재신호는 SYNC 0x80, PID 0xA5, Frame # 는 0xBE이다. 이들신호값중 CRC필드데이터에영향을주는데이터는 Frame # 필드값인 0xBE이다. 이값을이진수로변환하면 000 1011 1110 (2) 이다. 하지만실제 CRC 데이터를생성할때는이숫자를반대로읽으므로 [ 그림2.1.3] 과같이 011 1110 1000 (2) 과같이읽어야한다. Frame # 의값이정해졌으면이값을부호화해야한다. Frame # 를이용해 CRC5를계산하여 5비트를산출하기위해서는 Frame # 필드크기 11비트에 CRC5 연산식크기 6비트를빼준 5비트의레지스터를시프트시켜줘야한다. 부가설명을추가하면, Frame # 값인 011 1110 1000 (2) 을 0111 1101 0000 0000 (2) 형식으로바꿔야한다. 그리고이값을 CRC5의연산식 G(X) = X X 1 와단계적으로 XOR을한다. 쉽게풀이과정을보자면다음의 [ 그림 2.1.4] 와같다. [ 그림 2.1.4] CRC5 연산과정 페이지 4 / 18
이진나눗셈과정은십진수의나눗셈과정과동일하다. 하위비트에 5비트를추가한 0111 1101 0000 0000 (2) 데이터에 CRC5 연산식인 100101 (2) 을상위비트부터한단계씩 XOR계산한다. 이렇게연산을시작하다가계산된나머지값의길이가 5비트이하가되면이값이 CRC5값이된다. [ 그림2.1.4] 와같이 Frame # 필드의상위비트 111110 (2) 와연산식 100101 (2) 을 2진나눗셈해준값은 11011 (2) 이고하위비트에 1 을덧붙여서연산식 100101 (2) 와다시 XOR해주고, 또값이나오면이것을연산식에 XOR을반복한다. 하지만 [ 그림2.1.3] 의 CRC5 값과 [ 그림2.1.4] 에서구한 CRC5 값이서로다른것을확인할수있다. CRC5의값은 [ 그림2.1.3] 의 CRC5필드데이터인 11100 (2) 이나와야하지만실제계산결과값은 10100 (2) 가나온다. 따라서 CRC5값을구하기위해서는계산된나머지값의 3번비트를역변환 (Inverse) 해준다. Frame # 필드의데이터를추출해서, 그데이터를 XOR 논리연산을이용해 2진나눗셈을한나머지데이터에 3번비트를역변환 (Inverse) 한값이최종 CRC5필드에데이터이며, [ 그림2.1.3] 을예로구한다면그값은위에서구한바와같이 10100 (2) 의값과동일하다. 이값은 SYNC 필드, PID 필드, Frame # 필드의뒤를이어데이터의마지막필드인 CRC5필드에덧붙여져서최종데이터가완성된다. 페이지 5 / 18
2.2 MATLAB 을이용한 CRC5 코드 2.2.1 MATLAB 을이용한 CRC 계산코드개요 [ 그림 2.2.1] MATLAB 이용한 CRC 계산코드개요 페이지 6 / 18
2.2.2 데이터입력 01. sinput_data=input('input Binary num => ', 's'); 02. sinput_data_temp=sinput_data; 03. ninput_datan=length(sinput_data); 04. 05. for i=0:1:ninput_datan-1 06. temp1(i+1)=sinput_data(ninput_datan-i); 07. end 08. 09. sinput_data=temp1; 10. Frame_num=sInput_Data; sinput_data에데이터를문자열로입력받는데 Frame # 필드의값이 [ 그림2.2.1] 와같이 0xBF (1011 1111 (2) ) 라고한다면, 실제입력은그반대인 111 1110 1000 (2) 로입력받는다. CRC계산을위해서이값을변환해야하는데입력받은데이터의길이를 구하고이데이터의길이를이용하여데이터를모두역으로한다. 입력데이터가 000 1011 1111 (2) 이라한다면이데이터를 for문을이용하여 111 1110 1000 (2) 의데이터로계산가능한값으로전환한다. 페이지 7 / 18
2.2.3 Frame #, CRC5 시프트 11. sinput_data=base2dec(sinput_data,2); 12. sinput_data=dec2base(sinput_data,2); 13. 14. ninput_datan=length(sinput_data); 15. 16. CRC5=37; 17. ncrc5n=6; % CRC5 2진수길이 18. 19. ninput_data=base2dec(sinput_data,2); 20. 21. ncrc5=crc5*(2^(ninput_datan-1)); 22. ncrc5=crc5<<(ninput_datan-1) y=n*2^x; 23. nxor_func=ninput_data*2^5 Frame # 데이터를계산할수있도록변환이후, XOR 연산을해야하는데 MATLAB 프로그램은상위비트에붙어있는 0을제거해야계산이가능하다. 0이제거가안되면, 이값을아스키코드 (ASCII CODE) 로읽게되어계산의오류를발생한다. 그러므로 입력받은데이터 ( 문자형 ) 을정수형 (int) 으로변환하고이것을 2진수의문자형 (char) 으로변환하면상위비트에붙어있는 0이제거된다. 제거된데이터에 5비트의 0을하위비트에덧붙여줌으로서 XOR 논리연산을할수있는모든준비를마친다. 페이지 8 / 18
2.2.4 CRC5 연산식을이용한 XOR 계산 24. while(1) 25. temp1=dec2base(ncrc5,2); 26. temp2=dec2base(nxor_func,2); 27. 28. temp1=double(temp1); 29. temp2=double(temp2); 30. 31. temp1=temp1-48; 32. temp2=temp2-48; 33. 34. nxor_func=xor(temp1,temp2); 35. 36. nxor_func=nxor_func+48; 37. 38. nxor_func=char(nxor_func); 39. nxor_func=base2dec(nxor_func,2); 40. 41. scharn1=dec2base(nxor_func,2); 42. scharn2=dec2base(ncrc5,2); 43. 44. slength=length(scharn1); 45. 46. if (slength)<6 47. break; 48. end 49. 50. ntemp=length(scharn2)-length(scharn1); 51. 52. ncrc5=ncrc5/(2^ntemp); 53. end 페이지 9 / 18
Frmae # 의데이터를 CRC5로부호화하기위해서 [ 그림2.1.4] 와같은연산과정을거친다. 코드에서연산과정을거치기위해서 [ 그림2.2.2] 와같은과정을거쳐야한다. MATLAB은문자열또는 10진수로구성되어있는행렬을 XOR 할경우 2진수형식의계산이되지않는다. 문자열로되어있는데이터를아스키코드값 (0 s ASCII CODE=48, 1 s ASCII CODE =49) 으로변환하고, 이값을 -48 해주면 2진수행렬로변환할수있다. 이때만들어진행렬을 [ 그림2.1.4] 와같이십진수의나눗셈과마찬가지로한단계씩 XOR 연산하고이값의나머지길이를구해데이터의비트길이가 5이하가되면 while문을빠져나와 계산을마친다. [ 그림 2.2.2] MATLA 의 XOR 연산 페이지 10 / 18
2.2.5 CRC 값을 5 비트로변환 54. for i=0:1:5 55. if ((5-slength)==0 56. break; 57. 58. else if(i<5-slength) 59. R(i+1)='0'; 60. 61. else if(i>=5-slength) 62. scharn1=[r scharn1]; 63. break; 64. end 65. end 66. end 67. end 2진나눗셈과정에서계산이되어나머지값으로산출된값이 5 비트가아닌그이하의비트일때, 예를들어 CRC값이 1110 (2) 이 나왔다고했을때 5비트를맞춰주기위해앞에 0을붙임으로서 01110 (2) 5비트를맞춰준다. 페이지 11 / 18
2.2.6 CRC값에 3비트인벌스 && 최종값출력 68. temp1=double(scharn1(2)); 69. temp1=xor(temp1-48,1)+48; 70. scharn1(2)=char(temp1); 71. 72. Result=[Frame_num scharn1]; 73. 74. disp('--------frame num--------'); 75. disp(frame_num); 76. disp('--------crc5계산값--------'); 77. disp(scharn1); % 최종값을출력 78. disp('--------최종--------'); 79. disp(result); 5비트까지갖춘 CRC5값에 3번값을원본데이터의가장마지막비트를역변환 (Inverse) 하므로서필드인 CRC5필드에 5비트를덧최종 CRC5 데이터를구하고그붙여서최종값을출력한다. [ 그림 2.2.3] MATLAB 을이용하여 CRC 계산최종결과 페이지 12 / 18
2.3 C 소스를이용한 CRC5 코드 2.3.1 C 언어를이용한 CRC 계산코드개요 [ 그림 2.3.1] C 언어를이용한 CRC 계산코드개요 페이지 13 / 18
2.3.2 변수선언및데이터입력 01. #include<stdio.h> 02. #include<stdlib.h> 03. #include<string.h> 04. 05. #define CRC5 37 06. #define ncrc5n 6 07. main() 08. { 09. unsigned int ninput_data; 10. unsigned int ninput_datan; 11. unsigned int nxor_func; 12. unsigned int ncrc5; 13. unsigned int ntemp; 14. unsigned int i; 15. char sinput_data[100]; 16. char scharn1[100], scharn2[100]; 17. char scrc5_result[100]; 18. char temp[100]; 19. 20. printf("\n에러체크를할 8비트데이터를 2진수로입력하시오 => "); 21. gets(sinput_data); 필요한변수를정의하고, sinput _Data에 [ 그림2.3.1] 와같이 Frame # 필드데이터 000 1011 1111 (2) 를문자형으로입력받는다. 페이지 14 / 18
2.3.3 Frame#, CRC5 연산식시프트 22. ninput_datan = strlen(sinput_data); 23. 24. for(i=0; i<ninput_datan; i++) 25. temp[i]=sinput_data[ninput_datan-1-i]; 26. 27. temp[ninput_datan]=null; 28. 29. for(i=0; i<ninput_datan; i++) 30. sinput_data[i]=temp[i]; 31. 32. ninput_data=strtoul(sinput_data,null,2); 33. 34. ninput_datan = strlen(sinput_data); 35. ncrc5 = CRC5<<(nInput_DataN-1); 36. nxor_func=ninput_data<<5; 변수 sinput_data에입력받은 Frame # 데이터가예를들어 [ 그림2.3.1] 의 000 1011 1111 (2) 라한다면, 실제입력은데이터를역으로한, 111 1110 1000 (2) 와같다. 따라서이프로그램에서 for문을이용하여데이터를역으로저장하고, CRC를계산하기위해입력 데이터를 111 1110 1000 (2) 와 CRC5 연산식 100101을시프트시킨다. 그결과입력데이터는 1111 1101 0000 0000 (2) 으로, CRC5연산식은 1001 0100 0000 0000 (2) 으로변환된다. 페이지 15 / 18
2.3.4 CRC5 연산식을이용한 XOR계산 34. while(1) 35. { 36. nxor_func = nxor_func^ncrc5; // XOR계산 37. 38. itoa(nxor_func, scharn1,2); 39. itoa(ncrc5, scharn2, 2); 40. 41. if(strlen(scharn1)<=5) 42. break; 43. 44. ntemp=(strlen(scharn2)-strlen(scharn1)); 45. 46. ncrc5=ncrc5>>ntemp; 47.} [ 그림 2.3.2] CRC 연산과정 데이터를 CRC5로계산하기위해서 [ 그림2.3.2] 와같은 2진나눗셈을 10진나눗셈과동일하게한단계씩과정을거쳐야한다. 입력데이터와 CRC5의연산식 100101 (2) 을 XOR하면서 2진나눗셈의나머지값의길이를구해나머지데이터의길이가 5비트이하가되면 while문을빠져나와계산을마친다. 페이지 16 / 18
2.3.5 CRC값에 3비트 Inverse와최종값출력 48. nxor_func = nxor_func^8; 49. itoa(nxor_func, scharn1,2); 50. 51. printf("crc5값 : %s\n", scharn1); 52. ntemp = ninput_data<<5; 53. ntemp = ntemp^nxor_func; 54. itoa(ntemp, scrc5_result, 2); 55. printf("result : %s\n", scrc5_result); 56. } 57. } 마지막으로모두구한 5비트의필드데이터를구하고입력값과 CRC값에 3번비트를역변환함께 CRC5필드데이터를출력 (Inverse) 하므로서최종 CRC5 한다.. [ 그림 2.3.3] C 언어에서의최종결과 페이지 17 / 18
3. 결론 MATLAB과 C를이용하여 CRC5 를계산하는프로그램을살펴보았다. 여러개의필드중에서 Frame # 필드의데이터를이용해피제수의일부와제수인 CRC5 필드데이터값을순차적으로 XOR한다. 나머지가 5비트이하로계산을마쳤을때나머지데이터값의 3 번째비트를역변환 (Inverse) 하므로서최종적인 CRC5필드의데이터를구할수있다. 최종데이터는수신부에서다시피제수가되어제수인연산식과 2진나눗셈을한번더반복하게되고이때의나머지가 0이면비트손상이없는것으로간주하며, 0이아니면한개이상의비트가손상된것으로처리한다. USB 프로토콜에서 CRC5를이용한오류검출은여러오류를검출하는데매우우수할뿐아니라, 쉽게구현할수있다는장점을지닌다. 이장점은 USB가 데이터를전송할때안정성과신뢰성을확보하게해준다. 하지만실제 USB에서는하드웨어상의 USB Controller가 CRC를자동으로구현해주기때문에개발자가 CRC를구현해줄필요는없다. < 마침 > 참고문헌 [1] 이정욱, Embeded USB Inside, 다다미디어, 2008. 05 [2] Behrouz A. Forouzan, 이재광, 박동선, 김한규공역, 데이터통신과네트워킹, McGraw-Hill Korea, 2007. 07 페이지 18 / 18