CRC Algorithm - A Haskell Implementation

articles ✒ crc-algorithm

Following on from my article on error detection, this program is a Haskell implementation of the CRC algorithm.

CRC uses polynomial long-division over the field Z_2 to generate a checksum for an input message.

 
crc :: [Int] -> [Int] -> [Int]
 
-- crc should give the remainder when dividing
-- x^n * msg (as a polynomial in x with coefficients in Z_2) by poly
-- polynomials are written with highest coefficient first
-- poly must start with a 1
 
rep x n | n == 0    = []
           | otherwise =  x:(rep x (n-1))
 
crc poly msg = crc' (poly,lpoly) (paddedmsg,lpaddedmsg)
    where lpaddedmsg = length msg + lpoly - 1
          lpoly = length poly
          paddedmsg = msg ++ rep 0 (lpoly - 1)
 
 
listsub :: [Int] -> [Int] -> [Int]
-- returns a-b, assumes length a >= length b
listsub (a:as) (b:bs) = (a-b):listsub as bs
listsub as []         = as
 
crc' :: ([Int], Int) -> ([Int], Int) -> [Int]
 
crc' (poly,lpoly) ((m:ms),lmsg)
    | lmsg == lpoly - 1 = (m:ms)
    | m == 0 = crc' (poly,lpoly) (ms, lmsg-1)
    | m == 1 = crc' (poly,lpoly) (subbedtail, lmsg-1)
       where subbedtail = map (`mod` 2) (listsub ms (tail poly))
              -- the head would be 0 so we discard it
 

comment on this page