Checksums & CRCs Book Pointers

{book cover}

Philip Koopman, Understanding Checksums & Cyclic Redundancy Codes, 2024, ISBN 9798876380579

Source code with examples:

Clickable Footnote Links

  1. --
  2. --
  3. https://en.wikipedia.org/wiki/Coding_theory
  4. --
  5. --
  6. --
  7. --
  8. --
  9. --
  10. --
  11. --
  12. --
  13. --
  14. --
  15. --
  16. https://en.wikipedia.org/wiki/Telephone_exchange_names
  17. --
  18. https://en.wikipedia.org/wiki/Hash_function
  19. --
  20. https://en.wikipedia.org/wiki/Luhn_algorithm
  21. --
  22. --
  23. https://patents.google.com/patent/US2950048A/en
  24. https://en.wikipedia.org/wiki/ISBN#ISBN-13_check_digit_calculation
  25. --
  26. https://www.wolframalpha.com/input?i=0984449000+isbn
  27. --
  28. --
  29. --
  30. --
  31. https://www.cbp.gov/sites/default/files/documents/in_bond_check_1.pdf
  32. https://en.wikipedia.org/wiki/International_Bank_Account_Number#Modulo_operation_on_IBAN
  33. --
  34. https://en.wikipedia.org/wiki/Universal_Product_Code#Check_digit_calculation
  35. https://en.wikipedia.org/wiki/ABA_routing_transit_number
  36. https://en.wikipedia.org/wiki/Check_digit
  37. --
  38. --
  39. --
  40. --
  41. --
  42. --
  43. --
  44. https://en.wikipedia.org/wiki/Dependability#Threats
  45. https://en.wikipedia.org/wiki/Probability#Independent_events
  46. https://www.wolframalpha.com/input?i=f%3D3+%3B+n%3D100+%3B+b%3D1e-6%3B+X%3D%28b**f%29%3B+Y%3D%28%281-b%29**%28n-f%29%29%3B+Z%3Dcombin%28n%2Cf%29%3B++X*Y*Z
  47. --
  48. --
  49. https://en.wikipedia.org/wiki/Hamming_weight
  50. http://www.pcg-random.org
  51. https://en.wikipedia.org/wiki/Monte_Carlo_method
  52. --
  53. --
  54. --
  55. https://en.wikipedia.org/wiki/Hamming_distance
  56. --
  57. --
  58. --
  59. --
  60. --
  61. https://en.wikipedia.org/wiki/Hamming_code
  62. https://en.wikipedia.org/wiki/Parity_bit
  63. https://en.wikipedia.org/wiki/Hamming_weight
  64. https://en.wikipedia.org/wiki/Longitudinal_redundancy_check
  65. https://en.wikipedia.org/wiki/Adder_(electronics)
  66. --
  67. https://en.wikipedia.org/wiki/Two%27s_complement
  68. --
  69. https://en.wikipedia.org/wiki/Adder_(electronics)#Adders_supporting_multiple_bits
  70. https://en.wikipedia.org/wiki/Ones'_complement
    https://en.wikipedia.org/wiki/Signed_number_representations
  71. --
  72. --
  73. --
  74. --
  75. --
  76. --
  77. http://en.wikipedia.org/wiki/Adler-32
  78. --
  79. --
  80. --
  81. http://en.wikipedia.org/wiki/Adler-32
  82. --
  83. https://en.wikipedia.org/wiki/Fletcher%27s_checksum#Caution_on_modulus
  84. --
  85. --
  86. --
  87. --
  88. --
  89. https://www.wolframalpha.com/input?i=0x12345600+mod+0xFD
  90. https://www.wolframalpha.com/input?i=%28%28%28%28%28%28%28%28%280x12%29*+0x100%29%2B+0x34%29mod+0xFD%29*+0x100%29%2B0x56%29+mod+0xFD%29*+0x100%29%2B+0x00%29+mod+0xFD
  91. https://www.wolframalpha.com/input?i=%28%28%280x12*0x1000000%29mod+0xFD%29%2B%280x345600%29%29+mod+0xFD
  92. https://www.wolframalpha.com/input?i=0x7800000000+mod+0xFD
  93. https://www.wolframalpha.com/input?i=%28%280x78+mod+0xFD%29*0x100000000%29mod+0xFD
  94. https://www.wolframalpha.com/input?i=%28%28%28%280x78+mod+0xFD%29+*+0x10000%29+mod+0xFD%29+*+0x10000%29+mod+0xFD
  95. https://www.wolframalpha.com/input?i=%28%28%28%28%28%28%28%280x78+mod+0xFD%29*0x100%29mod+0xFD%29*0x100%29mod0xFD%29*0x100%29mod0xFD%29*0x100%29mod0xFD
  96. https://www.wolframalpha.com/input?i=0x7800000000+mod+0xFFEF
  97. https://www.wolframalpha.com/input?i=%28%280x78mod+0xFFEF%29+*+0x10000+mod+0xFFEF%29+*+0x10000+mod+0xFFEF
  98. https://www.wolframalpha.com/input?i=%28%28%28%280x78mod+0xFFEF%29*0x100mod0xFFEF%29*0x100mod0xFFEF%29*0x100mod0xFFEF%29*0x100mod0xFFEF
  99. https://www.wolframalpha.com/input?i=%28%28%28%28%28%28%28%280x78mod+0xFFEF%29*0x10mod0xFFEF%29*0x10mod0xFFEF%29*0x10mod0xFFEF%29*0x10mod0xFFEF%29*0x10mod0xFFEF%29*0x10mod0xFFEF%29*0x10mod0xFFEF%29*0x10mod0xFFEF
  100. --
  101. --
  102. https://wolframalpha.com/input?i=0x080200+mod+0xCD
  103. https://www.wolframalpha.com/input?i=0x1000+mod+0xC3
  104. --
  105. --
  106. --
  107. --
  108. --
  109. --
  110. --
  111. https://en.wikipedia.org/wiki/Cyclic_redundancy_check
    https://en.wikipedia.org/wiki/Polynomial_long_division
    https://en.wikipedia.org/wiki/GF(2)
    https://en.wikipedia.org/wiki/Mathematics_of_cyclic_redundancy_checks
  112. --
  113. https://en.wikipedia.org/wiki/Byte#History_of_the_conflicting_definitions
  114. https://en.wikipedia.org/wiki/CAN_bus#Data_frame
  115. --
  116. --
  117. https://en.wikipedia.org/wiki/Finite_field
  118. --
  119. --
  120. A video illustrating this division example can be found here: https://youtu.be/1t3DacyL5HA and here:
    https://archive.org/details/L600-crc-operation-examples-division-and-shift-register
  121. https://en.wikipedia.org/wiki/Long_division
  122. --
  123. --
  124. --
  125. --
  126. --
  127. --
  128. --
  129. https://users.ece.cmu.edu/~koopman/crc/crc32.html
  130. https://reveng.sourceforge.io/crc-catalogue/all.htm
  131. https://en.wikipedia.org/wiki/Endianness
  132. --
  133. --
  134. --
  135. --
  136. --
  137. --
  138. --
  139. --
  140. --
  141. --
  142. --
  143. --
  144. --
  145. https://users.ece.cmu.edu/~koopman/crc/crc32.html
  146. https://www.google.com/search?q=0x17b01bd
  147. --
  148. --
  149. --
  150. --
  151. --
  152. https://www.wolframalpha.com/input?i=factor+%281x**3%2B0x**2%2B0x%2B1%29+over+GF%282%29
  153. https://www.wolframalpha.com/input?i=factor+x8+%2Bx7+%2Bx6+%2Bx3+%2Bx2+%2Bx+%2B1+over+GF%282%29
  154. https://www.wolframalpha.com/input?i=factor+x8+%2Bx4+%2Bx3+%2Bx+%2B1+over+GF%282%29
  155. https://www.wolframalpha.com/input?i=factor+x8%2Bx5%2Bx3%2Bx2%2Bx%2B1+over+GF%282%29
  156. https://www.wolframalpha.com/input?i=factor+x8+%2Bx5+%2Bx4+%2Bx2+%2Bx+%2B1+over+GF%282%29
  157. https://www.wolframalpha.com/input?i=factor+x8+%2Bx6+%2Bx3+%2B1+over+GF%282%29
  158. https://en.wikipedia.org/wiki/Primitive_polynomial_(field_theory)
  159. https://en.wikipedia.org/wiki/Exponentiation_by_squaring
  160. https://users.ece.cmu.edu/~koopman/lfsr/
  161. https://en.wikipedia.org/wiki/Superposition_principle
  162. --
  163. --
  164. --
  165. https://www.wolframalpha.com/input?i=factor%28x8%2Bx5%2Bx3%2Bx2%2Bx%2B1%29+over+gf%282%29
  166. https://www.wolframalpha.com/input?i=factor+%28x5%2Bx3%2Bx%2B1%29+over+GF%282%29
  167. https://www.wolframalpha.com/input?i=k%3D16%3B+2**%28k-1%29+-+k+-+1
  168. --
  169. --
  170. https://en.wikipedia.org/wiki/Mathematics_of_cyclic_redundancy_checks#Reciprocal_polynomials
  171. --
  172. --
  173. --
  174. --
  175. --
  176. https://en.wikipedia.org/wiki/Enumerator_polynomial#MacWilliams_identity
  177. --
  178. --
  179. --
  180. https://en.wikipedia.org/wiki/CAN_bus
  181. --
  182. https://www.wolframalpha.com/input?i=BitXor%5B0x8E%2C0x47%2C0xAD%2C0xD8%2C0x6C%2C0x36%2C0x1B%5D
  183. --
  184. https://www.wolframalpha.com/input?i=BitXor%5B0x13d%2C0x1a3%2C0x1ec%2C0x0f6%2C0x07b%5D
  185. --
  186. https://en.wikipedia.org/wiki/Binomial_distribution
  187. --
  188. --
  189. https://www.rfc-editor.org/rfc/rfc1624
  190. --
  191. --
  192. https://www.wolframalpha.com/input?i=factor+%28x32%2Bx28%2Bx25%2Bx19%2Bx18%2Bx16%2Bx15%2Bx13%2Bx10%2Bx8%2Bx6%2Bx5%2Bx4%2Bx%2B1%29+over+gf%282%29
  193. --
  194. https://en.wikipedia.org/wiki/Big_O_notation
  195. --
  196. https://en.wikipedia.org/wiki/Computational_complexity_theory
  197. https://en.wikipedia.org/wiki/Hash_table
  198. --
  199. https://en.wikipedia.org/wiki/Hash_collision
  200. https://en.wikipedia.org/wiki/Hash_table#Open_addressing
  201. --
  202. --
  203. --
  204. --
  205. --
  206. --
  207. --
  208. --
  209. --
  210. --
  211. --
  212. https://www.wolframalpha.com/input?i=n%3D100%3Bf%3D3%3BB%3D1e-5%3B+++X%3D%28B**f%29%3B+Y%3D%28%281-B%29**%28n-f%29%29%3B+Z%3Dcombination%28n%2Cf%29%3B++X*Y*Z
  213. https://betterembsw.blogspot.com/2012/02/can-protocol-vulnerabilities.html
  214. https://www.wolframalpha.com/input?i=n%3D100%3Bf%3D6%3BB%3D1e-2%3B+++X%3D%28B**f%29%3B+Y%3D%28%281-B%29**%28n-f%29%29%3B+Z%3Dcombination%28n%2Cf%29%3B++X*Y*Z++*+1000+*+3600
  215. https://reveng.sourceforge.io/
  216. https://en.wikipedia.org/wiki/Cyclic_redundancy_check#Data_integrity
  217. --
  218. https://users.ece.cmu.edu/~koopman/ece649/lectures/23_flexray.pdf
  219. https://en.wikipedia.org/wiki/Train_communication_network
  220. https://en.wikipedia.org/wiki/CAN_bus#Bit_stuffing
  221. --
  222. https://en.wikipedia.org/wiki/8b/10b_encoding
  223. https://en.wikipedia.org/wiki/64b/66b_encoding
  224. https://en.wikipedia.org/wiki/Line_code
  225. --
  226. https://en.wikipedia.org/wiki/Scrambler#Additive_(synchronous)_scramblers
  227. --
  228. --
  229. https://en.wikipedia.org/wiki/Single-event_upset

Clickable Resource Links

  1. Arazi (1988) https://archive.org/details/commonsenseappro0000araz
  2. Baicheva et al. (1998) https://doi.org/10.1016/S0140-3664(98)00165-0
    https://www.researchgate.net/publication/222584690_On_the_cyclic_redundancy-check_codes_with_8-bit_redundancy
  3. Baicheva et al. (2000) https://doi.org/10.1049/ip-com:20000649
    https://www.researchgate.net/publication/3350132_On_the_cyclic_redundancy-check_codes_of_16-bit_redundancy
  4. Barr (1999) https://barrgroup.com/tech-talks/checksums-and-crcs
  5. Boudreau et al. (1994) https://doi.org/10.1147/rd.386.0651
  6. Braun & Waldvogel (2001) https://doi.org/10.1109/HPSR.2001.923602
    https://www.researchgate.net/publication/2400251_Fast_incremental_CRC_updates_for_IP_over_ATM_networks
  7. Castabnoli et al. (1993) https://doi.org/10.1109/26.231911
    https://ia600704.us.archive.org/view_archive.php?archive=/24/items/wikipedia-scholarly-sources-corpus/10.1109%252F08IAS.2008.237.zip&file=10.1109%252F26.231911.pdf
  8. Castagnoli et al. (1990) https://doi.org/10.1109/26.46536
  9. Cideciyan & Gustlin (2012) https://grouper.ieee.org/groups/802/3/bj/public/jul12/cideciyan_01_0712.pdf
  10. Cook (2022) https://reveng.sourceforge.io/ / https://reveng.sourceforge.io/crc-catalogue/
  11. Driscoll et al. (2009) https://www.faa.gov/sites/faa.gov/files/aircraft/air_cert/design_approvals/air_software/AR-09-24.pdf
    https://users.ece.cmu.edu/~koopman/pubs/faa09-24_data_network_evaluation_criteria_handbook.pdf
  12. Feldmeier (1995) https://doi.org/10.1109/90.477710
  13. Fiorini et al. (1994) https://dl.acm.org/doi/10.1145/205511.205521
    https://www.researchgate.net/publication/234829693_Can_we_trust_in_HDLC
  14. Fletcher (1982) https://doi.org/10.1109/TCOM.1982.1095369
  15. Fujiwara et al. (1985) https://doi.org/10.1109/TCOM.1985.1096340
  16. Fujiwara et al. (1989) https://doi.org/10.1109/26.35380
  17. Funk (1982) https://doi.org/10.1109/TCOM.1982.1095367
  18. Funk (1996) https://doi.org/10.1109/26.476086
  19. Jain (1990) https://doi.org/10.1109/26.58757
  20. James (2005) http://doi.org/10.17863/CAM.11801
  21. Jiao & Schwiebert (2001) https://doi.org/10.1109/ICCCN.2001.956312
  22. Klove (2007) ISBN-10 9812705864
  23. Koopman (2002) https://doi.org/10.1109/DSN.2002.1028931
    https://users.ece.cmu.edu/~koopman/networks/dsn02/dsn02_koopman.pdf
  24. Koopman & Chakravarty (2004) https://doi.org/10.1109/DSN.2004.1311885
  25. Koopman et al. (2015) https://users.ece.cmu.edu/~koopman/pubs/faa15_tc-14-49.pdf
  26. Koopman (2023) https://arxiv.org/abs/2302.13432
  27. Leung-Yan-Choeng & Hellman (1976) https://doi.org/10.1109/TIT.1976.1055515
  28. Leung-Yan-Choeng et al. (1979) https://doi.org/10.1109/TIT.1979.1055991
  29. Lin & Costello (1983) ISBN 013283796X
  30. MacWilliams (1963) https://doi.org/10.1002/j.1538-7305.1963.tb04003.x
    https://archive.org/details/bstj42-1-79
  31. Maxino & Koopman (2009) https://doi.org/10.1109/TDSC.2007.70216
    https://users.ece.cmu.edu/~koopman/pubs/maxino09_checksums.pdf
  32. McAuley (1994) https://doi.org/10.1109/90.282604
  33. Nguyen (2005) https://doi.org/10.1109/TC.2005.7
  34. Paulitsch et al. (2005) https://doi.org/10.1109/DSN.2005.31
    https://users.ece.cmu.edu/~koopman/pubs/paultisch05_dsn_crc_ultradependable.pdf
  35. Peterson & Brown (1961) https://doi.org/10.1109/JRPROC.1961.287814
  36. Plank (2013) https://www.usenix.org/publications/login/december-2013-volume-38-number-6/erasure-codes-storage-systems-brief-primer
  37. Peterson & Weldon (1972) ISBN 9780262527316
    https://archive.org/details/errorcorrectingc00pete/page/n5/mode/2up
  38. Ramabadran & Gaitonde (1988) https://doi.org/10.1109/40.7773
  39. Ray & Koopman (2006) https://doi.org/10.1109/DSN.2006.30
    https://users.ece.cmu.edu/~koopman/pubs/ray06_crcalgorithms.pdf
  40. Sarwate (1988) https://dl.acm.org/doi/10.1145/63030.63037
  41. Sheinwald et al. (2002) https://datatracker.ietf.org/doc/rfc3385/
  42. Stone et al. (1998) https://doi.org/10.1109/90.731187
    http://ccr.sigcomm.org/archive/1995/conf/partridge.pdf
  43. Stone & Partridge (2000) https://doi.org/10.1145/347057.347561
  44. Sweeney (2002) ISBN 047084356X
  45. Wells (1998) ISBN 0139613277
  46. Witzke (1984) https://open.library.ubc.ca/soa/cIRcle/collections/ubctheses/831/items/1.0096199
  47. Williams (1993) http://ross.net/crc/download/crc_v3.txt
    https://web.archive.org/web/20240203182343/http://ross.net/crc/download/crc_v3.txt
  48. Youssef et al. (2006) https://doi.org/10.1109/EDCC.2006.5