Compute minimal weight of cyclic code using only linear structure. Fast on low-dimensional codes.

weight-basis.hs

{-# LANGUAGE Strict #-}
module Main where

{-
ghc -O2 weigth-basis.hs # Was not tested with default level.
./weight-basis.hs
-}

import Control.DeepSeq

import Debug.Trace

import Data.Bits
import Data.Word (Word64)

type N = Int

degree :: Word64 -> Int
degree p = (finiteBitSize p) - (countLeadingZeros p) - 1

iso :: Word64 -> N -> Int -> Word64
iso gen n a = foldr (\k sum -> sum `xor` if testBit a k
                                     then shift gen k
                                     else 0
                    ) 0 [0..n - degree gen] 

minimalDistance :: N -> Word64 -> Int
minimalDistance n gen =
  foldr ( \a m -> force $ min m (if a == 0 then m else a)
        ) n ( map (popCount . iso gen n) [1..2^(n - degree gen)]
            )

-- Construct polynomial from more friendly input.
buildGen :: [Int] -> Word64
buildGen = foldr (flip setBit) 0

main :: IO ()
main = do
  putStrLn "Insert modulus (1 <= n <= 64): "
  -- Bigger values will cause overflows. Or, hopefully, errors.
  n <- read <$> getLine
  putStrLn "Insert list of degrees of generating polynomial (format [a,b,c]): "
  a' <- read <$> getLine
  putStrLn "Minimal distance of the code (is being computed): "
  print $ minimalDistance n (buildGen a')