Home  |   ¹æ¸í·Ï 2023-01-28 (Åä) 
Untitled Document
  S e a r c h
M e n u
ÇÁ·Î±×·¥
°³¹ßÀÚ·á
°íÀüÀ½¾Ç½Ç
´ëû¸¶·ç
ÁýÁÖÀÎ
ºñ¸Á·Ï
°¶·¯¸®
  B o a r d
°Ô½ÃÆÇ
Untitled Document
°³¹ßÀÚ·á Software / Hardware °³¹ß °ü·Ã Á¤º¸

CRC : CRC-16, CRC-32¿¡ ´ëÇÑ ¼³¸í°ú ±¸Çö


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 °è»ê¿¡ »ç¿ëµÇ´Â modulo-2 ¿¬»êÀÇ ¼¼°è¸¦ »ìÆìº¸ÀÚ.

CRC °è»ê½ÃÀÇ »çÄ¢¿¬»êÀº carry¸¦ °í·ÁÇÏÁö ¾Ê´Â´Ù.
1 + 1 = 0 (carry´Â »ý°¢ÇÏÁö ¾ÊÀ½)
0 - 1 = 1
µ¡¼À ¿¬»êÀº »¬¼À ¿¬»ê°ú °á°ú°¡ °°À¸¸ç XOR ¿¬»ê°úµµ °°´Ù.

´ÙÇ×½Ä Ç¥Çö ¹æ¹ýÀ» ÅëÇØ CRC °è»ê ¹æ¹ýÀ» »ìÆìº¸ÀÚ.

(1) 2Áø ´ÙÇ×½ÄÀ¸·Î Ç¥½Ã

¿¹) ºñÆ®¿­ 101 --> ´ÙÇ×½Ä x2 + 1

Á¤º¸ ´ÙÇ×½Ä: µ¥ÀÌÅÍ ºñÆ®¿­ÀÇ ´ÙÇ×½ÄÀ¸·Î P(x) = pn xn-1 + ... + p3x2 + p2x1 + p1
CRC ´ÙÇ×½Ä: CRC »ý¼ºÀ» À§ÇÑ ´ÙÇ×½ÄÀ¸·Î G(x) (¹Ì¸® Á¤ÇØÁø Ű °ª)
¸ò: Q(x)
³ª¸ÓÁö: R(x)
Àü¼Û µ¥ÀÌŸ: T(x)

(2) CRC °è»ê ¹æ¹ý

P(x)¸¦ k ºñÆ® ¸¸Å­ ÀÚ¸®¸¦ ¿Ã¸®°í( P(x)¿¡ xk¸¦ °öÇÏ´Â °Í°ú µ¿ÀÏ) G(x)·Î ³ª´©¸é

xk P(x) = Q(x)*G(x) +/- R(x) ÀÌ´Ù.

(k´Â CRC ´ÙÇ×½ÄÀÇ ÃÖ°í Â÷¼ö)

R(x) = dk xk-1 + .. + d2x1 + d1 ( R(x)ÀÇ ÃÖ°í Â÷¼ö´Â k-1)

ºñÆ®¿­ dk ... d2 d1 À» FCS(Frame Check Sequence) ¶ó ÇÔ

À§ ½Ä¿¡¼­ xk P(x) + R(x) ´Â Q(x)*G(x) ¿Í °°´Ù.

Áï, xk P(x) + R(x) ´Â G(x)ÀÇ ¹è¼öÀ̹ǷΠG(x) ·Î ³ª´©¸é ³ª¸ÓÁö°¡ 0 ÀÓÀ» ¾Ë ¼ö ÀÖ´Ù.

°á°úÀûÀ¸·Î Àü¼ÛµÇ´Â µ¥ÀÌÅÍ ºñÆ®¿­ : pn ... p3 p2 p1 dk ... d2 d1

Áï, Àü¼Û T(x) = xk P(x) + R(x)

¡¡

¿¹) µ¥ÀÌÅÍ ºñÆ®¿­ 110011 Áï P(x) =x5+x4+x1+x0, CRC ´ÙÇ×½ÄG(x) = x4+x3+1, Áï 11001ÀÏ °æ¿ì FCS¿Í Àü¼ÛµÇ´Â ºñÆ®¿­Àº?

xkP(x) = x4 (x5 + x4 + x1 + 1) = x9 + x8 + x5 + x4, ºñÆ®¿­·Î Ç¥½ÃÇϸé 1100110000

                   100001
          ____________
11001 | 1100110000
            11001
          ____________
                     10000
                     11001
          ____________
                       1001    

xkP(x) = Q(x)G(x) - R(x)¿¡¼­

Q(x) = x5 + x0 À̹ǷÎ,

R(x) = x3 + x0, ---> 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

2004-06-14 [Á¶È¸: 32767]

ÀÌÀü±Û: TWAIN : ½ºÄ³³Êµî À̹ÌÁöÀåÄ¡ ÀÎÅÍÆäÀ̽º API ±Ô¾à
´ÙÀ½±Û: I2C : Inter IC Bus

¸ñ·Ïº¸±â
±Ã±Ý...
CRC16ÀÇ °æ¿ì ¿¡·¯ È®À²Àº p = 2-16 = 1 / 65536 = 0.0000152587890625 = 0.0015%
¹Ý´ë·Î µ¥ÀÌÅÍÀÇ ½Å·Ú¼ºÀº 1 - p = 0.9999847412109375 = 99.9984 %
--------------------------------------
ÀÌ ºÎºÐÀÇ ¸»ÀÌ ÀÌÇØ°¡ °¡Áú ¾Ê³×¿ä.
Àú·± °è»êÀº. 16ºñÆ®°¡ ÀÕ°í. °¢ ºñÆ®´ç ¿¡·¯ È®·üÀÌ 0.5À̸ç. ÀÌ ºñÆ®¿­ ¸ðµÎ°¡ ¿¡·¯³¯ È®·üÀÌ 0.0015%¶ó´Â ¸» ¾Æ´Ñ°¡¿ä? ¾î°¼­ Àú·¸°Ô µÇ´Â°ÇÁö..
Â÷¶ó¸®. Àü¼Û´Ü°è¿¡¼­ ÇÑ °³ÀÇ ºñÆ®°¡ ¿¡·¯³¯ È®·üÀÌ 0.1À̸ç CRC-16ÀÌ ¿¡·¯³¯ È®·üÀº

ÇÑ °³ÀÇ ºñÆ®°¡ Á¤»óÀÏ È®·ü 0.9.
16ºñÆ® ¸ðµÎ°¡ Á¤»óÀÏ °æ¿ì´Â (0.9)^16À̸ç
CRC-16°¡ ¿¡·¯³¯ °æ¿ì´Â 1 - (0.9)^16¶ó´Â°Ô ¸»ÀÌ µÇ¾îº¸¿©¼­¿ä.

±×³É ¿¹¸¦ °£´ÜÈ÷ µç°Å¶ó¼­ Àǹ̰¡ Å©Áö ¾Ê´Â ¸»Àΰ¡¿ä? 2018-11-25 13:11
¡¿
 
À̸§ ¾ÏÈ£ Ȩ
(½ºÆÔ ¹æÁö¿ë)¿À´ÃÀÇ ³¯Â¥¸¦ ¼ýÀÚ¸¸À¸·Î ÀÔ·ÂÇϼ¼¿ä.(¿¹: 12)

ºñ¹Ð¹øÈ£
¸ñ·Ïº¸±â
 
Copyright ¨Ï 2023 All Rights Reserved.