linear-code 0.1.0 → 0.1.1

raw patch · 8 files changed

+178/−49 lines, 8 filesdep +random-shuffledep −combinatPVP ok

version bump matches the API change (PVP)

Dependencies added: random-shuffle

Dependencies removed: combinat

API changes (from Hackage documentation)

Files

• ChangeLog.md +12/−0
• README.md +2/−0
• linear-code.cabal +5/−5
• src/Math/Algebra/Code/Linear.hs +103/−29
• src/Math/Algebra/Field/Instances.hs +1/−1
• src/Math/Algebra/Field/Static.hs +1/−1
• src/Math/Algebra/Matrix.hs +13/−2
• test/Main.hs +41/−11

@@ -1,3 +1,15 @@+0.1.1+-----+* Backwards compatible changes+  - Add golay code+  - Add `codeFromAD`, `dualCodeD` creators+  - Add `extendCode` code transformer+  - Replace `combinat` dependency with `random-shuffle`++* Bugfixes+  - calcSyndromeTable uses known code distances correctly++ 0.1.0 ----- 

@@ -1,3 +1,5 @@+[![Hackage](https://img.shields.io/hackage/v/linear-code.svg)](https://hackage.haskell.org/package/linear-code) [![Hackage Deps](https://img.shields.io/hackage-deps/v/linear-code.svg)](http://packdeps.haskellers.com/reverse/linear-code)+ # linear-code Library to handle linear codes from coding theory. 

@@ -2,17 +2,17 @@ -- -- see: https://github.com/sol/hpack ----- hash: 515c75757e8c9b5fe6719710a1cfb652f7f850ab85098dc5d664b0b0aaf02230+-- hash: 55bce838924f0e4cb6a0546858fe4c3e48ed8f6aad2203e308d94f3bf40087a4  name:           linear-code-version:        0.1.0+version:        0.1.1 synopsis:       A simple library for linear codes (coding theory, error correction) description:    Please see the README on GitHub at <https://github.com/wchresta/linear-code#readme> category:       Math homepage:       https://github.com/wchresta/linear-code#readme bug-reports:    https://github.com/wchresta/linear-code/issues author:         Wanja Chresta-maintainer:     wanja.hs@chrummibei.ch+maintainer:     wanja dot hs at chrummibei dot ch copyright:      2018, Wanja Chresta license:        GPL-3 license-file:   LICENSE@@ -40,13 +40,13 @@   build-depends:       HaskellForMaths     , base >=4.7 && <5-    , combinat     , containers     , data-default     , ghc-typelits-knownnat     , ghc-typelits-natnormalise     , matrix     , random+    , random-shuffle   default-language: Haskell2010  test-suite linear-code-test@@ -61,7 +61,6 @@       HaskellForMaths     , QuickCheck     , base >=4.7 && <5-    , combinat     , containers     , data-default     , ghc-typelits-knownnat@@ -69,6 +68,7 @@     , linear-code     , matrix     , random+    , random-shuffle     , smallcheck     , tasty     , tasty-hunit

@@ -28,7 +28,7 @@ Description : Linear codes over arbitrary fields Copyright   : (c) Wanja Chresta, 2018 License     : GPL-3-Maintainer  : wanja.hs@chrummibei.ch+Maintainer  : wanja dot hs at chrummibei dot ch Stability   : experimental Portability : POSIX @@ -95,7 +95,7 @@ module Math.Algebra.Code.Linear     ( LinearCode (..)     , Generator, CheckMatrix-    , codeFromA+    , codeFromA, codeFromAD      , standardForm, standardFormGenerator @@ -108,10 +108,10 @@     , SyndromeTable      -- * Code transformers-    , dualCode, permuteCode+    , dualCode, dualCodeD, permuteCode, extendCode      -- * Special codes and their generators-    , trivialCode, simplex, hamming+    , trivialCode, simplex, hamming, golay     , BinaryCode      -- * Helper functions@@ -139,21 +139,20 @@  import Data.Bifunctor (first) import Data.Monoid ((<>))-import Data.Maybe (fromMaybe) import Data.List (permutations) import qualified Data.Map.Strict as M import Data.Proxy (Proxy (..))-import System.Random (Random, RandomGen, random, randomR)+import System.Random (Random, RandomGen, random, randomR, split)+import System.Random.Shuffle (shuffle')  import Math.Core.Utils (FinSet, elts)-import Math.Combinat.Permutations (_randomPermutation) import Math.Common.IntegerAsType (IntegerAsType) import Math.Algebra.Field.Base (Fp, F2, F3, F5, F7, F11) import Math.Algebra.Field.Static (Size, Characteristic, char) import Math.Algebra.Field.Extension (F4, F8, F16, F9) import Math.Algebra.Field.Instances () -- import Random instances for Fields import Math.Algebra.Matrix-    ( Matrix, matrix, transpose, (<|>), (.*)+    ( Matrix, matrix, transpose, (<|>), (<->), (.*)     , identity, zero, fromList, fromLists, Vector, rref, submatrix     ) @@ -205,13 +204,13 @@                 where c = char (Proxy :: Proxy f)                       n = natToInt @n Proxy                       k = natToInt @k Proxy-                      dist = fromMaybe "" $ fmap (\d -> ',':show d) md+                      dist = maybe "" (\d -> ',':show d) md  instance forall n k f.     (KnownNat n, KnownNat k, k <= n, Eq f, FinSet f, Num f, Ord f)       => Bounded (LinearCode n k f) where     minBound = trivialCode-    maxBound = codeFromA $ matrix (const $ last elts)+    maxBound = codeFromAD (Just 1) $ matrix (const $ last elts)   -- | A random permutation matrix@@ -220,10 +219,11 @@ randomPermMatrix g =     let n = natToInt @n Proxy         delta i j = if i == j then 1 else 0-        (perm,g') = _randomPermutation n g+        (g1,g2) = split g+        perm = shuffle' [1..n] n g1      in (fromLists [ [ delta i (perm !! (j-1))                      | j <- [1..n] ]-                   | i <- [1..n] ],g')+                   | i <- [1..n] ],g2)  -- | A random code with a generator in standard form. This does not generate --   all possible codes but only one representant of the equivalence class@@ -252,9 +252,8 @@            in shuffleCode rcode g2  --- | Uses Gaussian eleminiation via 'rref' from 'Data.Matrix.Safe' to---   find the standard form of generators. This might fail since not all---   codes can be converted to standard form without permutation of columns.+-- | Uses Gaussian eleminiation via 'rref' from 'Math.Algebra.Matrix' to+--   find the standard form of generators. standardForm :: forall n k f.     (Eq f, Fractional f, KnownNat n, KnownNat k, k <= n)       => Generator n k f -> Generator n k f@@ -262,7 +261,7 @@   -- | The standard from generator of a linear code. Uses 'standardForm' to---   try to create a standard form generator which might fail.+--   calculate a standard form generator. standardFormGenerator :: forall n k f.     (Eq f, Fractional f, KnownNat n, KnownNat k, k <= n)       => LinearCode n k f -> Generator n k f@@ -281,18 +280,32 @@ weight :: forall f m. (Eq f, Num f, Functor m, Foldable m) => m f -> Int weight = sum . fmap (\x -> if x==0 then 0 else 1) --- | Generate a linear [n,k]_q-Code over the field a with the generator in---   standard form (I|A), where the given function generates the k×(n-k)-matrix---   A.+-- | Generate a linear \( [n,k]_q \)-Code over the field @f@ with the+--   generator in standard form @(I|A)@, where the given function generates+--   the \( k \times (n-k) \)-matrix A.+--   The distance is unknown for this code and thus decoding algorithms may+--   be very inefficient. codeFromA :: forall k n f.     (KnownNat n, KnownNat k, k <= n, Eq f, FinSet f, Num f, Ord f)       => Matrix k (n-k) f             -- ^ Elements of A where top-left is (1,1) and bottom right (k,n-k)       -> LinearCode n k f-codeFromA a = recalcSyndromeTable LinearCode+codeFromA = codeFromAD Nothing+++-- | Generate a linear \( [n,k,d]_q \)-Code over the field @f@ with the+--   generator in standard form @(I|A)@, where the given function generates+--   the \( k \times (n-k) \)-matrix A.+codeFromAD :: forall k n f.+    (KnownNat n, KnownNat k, k <= n, Eq f, FinSet f, Num f, Ord f)+      => Maybe Int -- ^ Distance of the code. Give Nothing if it is unknown+      -> Matrix k (n-k) f+            -- ^ Elements of A where top-left is (1,1) and bottom right (k,n-k)+      -> LinearCode n k f+codeFromAD d a = recalcSyndromeTable LinearCode     { generatorMatrix = identity <|> a     , checkMatrix = (-transpose a) <|> identity -- () are important for f/=F2-    , distance = Nothing+    , distance = d     , syndromeTable = undefined     } @@ -333,7 +346,7 @@     shuffledVecs :: [[f]]     shuffledVecs = orderedVecs >>= permutations --- | List of all words with (non-zero) hamming weight smaller than a given +-- | List of all words with (non-zero) hamming weight smaller than a given --   boundary lighterWords :: forall n f. (KnownNat n, FinSet f, Num f, Eq f)     => Int -> [Vector n f]@@ -390,7 +403,7 @@     where minWt x y = if weight x < weight y then x else y           n = natToInt $ Proxy @n           k = natToInt $ Proxy @k-          w = fromMaybe (n-k+1) $ distance c+          w = maybe (n-k+1) (\d -> div (d-1) 2) $ distance c            allSyndromes :: [(Syndrome n k f, Vector n f)]           allSyndromes = [(syndrome c e,e) | e <- lighterWords w]@@ -420,21 +433,36 @@  -- * Code transformers --- |The dual code is the code generated by the check matrix+-- | The dual code is the code generated by the check matrix+--   +--   This drops already calculated syndromeTables. dualCode :: forall n k f.     (KnownNat n, KnownNat k, k <= n, Eq f, FinSet f, Num f, Ord f)       => LinearCode n k f -> LinearCode n (n-k) f-dualCode c = recalcSyndromeTable+dualCode = dualCodeD Nothing+++-- | The dual code is the code generated by the check matrix.+--   +--   This drops already calculated syndromeTables.+dualCodeD :: forall n k f.+    (KnownNat n, KnownNat k, k <= n, Eq f, FinSet f, Num f, Ord f)+      => Maybe Int -- ^ The distance of the new code (if known) or Nothing+      -> LinearCode n k f -> LinearCode n (n-k) f+dualCodeD d c = recalcSyndromeTable                     LinearCode { generatorMatrix = checkMatrix c                                , checkMatrix = generatorMatrix c-                               , distance = distance c+                               , distance = d                                , syndromeTable = undefined                                }   -- | Permute the rows of a code with a permutation matrix. The given permutation --   matrix must be a valid permutation matrix; this is not checked.---   This effectively multiplies the generator and check matrix from the right+--   This effectively multiplies the generator and check matrix from the right.+--   Te distance of the resulting code stays the same.+--   +--   This drops already calculated syndromeTables. permuteCode :: forall n k f.     (KnownNat n, KnownNat k, k <= n, Eq f, FinSet f, Num f, Ord f)       => LinearCode n k f -> Matrix n n f -> LinearCode n k f@@ -448,7 +476,10 @@   -- | Randomly permute the elements of the code. This is a shuffle of the---   positions of elements of all codewords+--   positions of elements of all codewords. The distance of the resulting+--   code stays the same.+--   +--   This drops already calculated syndromeTables. shuffleCode :: forall n k f g.     (KnownNat n, KnownNat k, k <= n, RandomGen g, Eq f, FinSet f, Num f, Ord f)       => LinearCode n k f -> g -> (LinearCode n k f, g)@@ -457,6 +488,26 @@      in (permuteCode c p, g')  +-- | Extend the given code \( c \) by zero-columns. Vectors +--   \( v_{ext} \in c_{ext} \) have the form +--   \( v = (v_1, \dots , v_n, 0, \dots, 0) \) . The distance of the extended+--   code stays the same.+--   This drops a calculated syndromeTable and makes it necessary to recalculate+--   it if it's accessed.+extendCode :: forall n k f r.+    (KnownNat n, KnownNat k, KnownNat r, k <= n, 1 <= r, k <= n+r+    , Num f, Ord f, FinSet f)+      => LinearCode n k f -> LinearCode (n+r) k f+extendCode c = recalcSyndromeTable LinearCode+    { generatorMatrix = generatorMatrix c <|> zero :: Generator (n+r) k f+    , checkMatrix = (checkMatrix c <|> (zero :: Matrix (n-k) r f))+                    <->+                    ((zero :: Matrix r n f) <|> (identity :: Matrix r r f))+    , distance = distance c+    , syndromeTable = undefined+    }++ -- * Special codes and their generators  -- | A binary code is a linear code over the field GF(2)@@ -483,8 +534,31 @@ -- | The /Hamming(7,4)/-code. It is a [7,4,3]_2 code hamming :: (KnownNat m, 2 <= m, m <= 2^m, 1+m <= 2^m)         => LinearCode (2^m-1) (2^m-m-1) F2-hamming = dualCode simplex { distance = Just 3 }+hamming = dualCodeD (Just 3) simplex ++-- | The _Golay_-code is a perfect [24,12,7]-code.+--   It is the only other non-trivial perfect code and the only perfect code+--   that is able to correct 3 errors.+--   +--   Syndrome decoding on this code takes a very, very long time.+golay :: LinearCode 23 12 F2+golay = codeFromAD (Just 7) golayA+  where+    golayA = fromList+        [0,1,1,1,1,1,1,1,1,1,1+        ,1,1,1,0,1,1,1,0,0,0,1+        ,1,1,0,1,1,1,0,0,0,1,0+        ,1,0,1,1,1,0,0,0,1,0,1+        ,1,1,1,1,0,0,0,1,0,1,1+        ,1,1,1,0,0,0,1,0,1,1,0+        ,1,1,0,0,0,1,0,1,1,0,1+        ,1,0,0,0,1,0,1,1,0,1,1+        ,1,0,0,1,0,1,1,0,1,1,1+        ,1,0,1,0,1,1,0,1,1,1,0+        ,1,1,0,1,1,0,1,1,1,0,0+        ,1,0,1,1,0,1,1,1,0,0,0+        ]  -- * Helper functions 

@@ -21,7 +21,7 @@ Description : Missing instnaces for @HaskellForMaths@'s 'Math.Algebra.Field' Copyright   : (c) Wanja Chresta, 2018 License     : GPL-3-Maintainer  : wanja.hs@chrummibei.ch+Maintainer  : wanja dot hs at chrummibei dot ch Stability   : experimental Portability : POSIX 

@@ -25,7 +25,7 @@ Description : Some type families extracting finite field parameters Copyright   : (c) Wanja Chresta, 2018 License     : GPL-3-Maintainer  : wanja.hs@chrummibei.ch+Maintainer  : wanja dit hs at chrummibei dot ch Stability   : experimental Portability : POSIX 

@@ -28,7 +28,7 @@ Description : Type safe matrix wrapper over the matrix library Copyright   : (c) Wanja Chresta, 2018 License     : GPL-3-Maintainer  : wanja.hs@chrummibei.ch+Maintainer  : wanja dot hs at chrummibei dot ch Stability   : experimental Portability : POSIX @@ -44,6 +44,7 @@     , Vector     , transpose     , (<|>)+    , (<->)     , identity     , zero     , fromList@@ -134,7 +135,17 @@ -- > ( A ) <|> ( B ) = ( A | B ) (<|>) :: forall m n k a. (KnownNat n, KnownNat k)       => Matrix m n a -> Matrix m k a -> Matrix m (k+n) a-(Matrix x) <|> (Matrix y) = Matrix $ x M.<|> y+Matrix x <|> Matrix y = Matrix $ x M.<|> y++-- | Horizontally join two matrices. Visually:+--+-- >                   ( A )+-- > ( A ) <-> ( B ) = ( - )+-- >                   ( B )+(<->) :: forall m k n a. (KnownNat m, KnownNat k)+      => Matrix m n a -> Matrix k n a -> Matrix (m+k) n a+Matrix x <-> Matrix y = Matrix $ x M.<-> y+  -- | /O(rows*cols)/. Identity matrix identity :: forall n a. (Num a, KnownNat n) => Matrix n n a

@@ -1,14 +1,13 @@ {-# LANGUAGE ScopedTypeVariables, DataKinds, TypeOperators, TypeFamilies #-} {-# LANGUAGE FlexibleContexts, FlexibleInstances, MultiParamTypeClasses #-}+{-# OPTIONS_GHC -fno-warn-orphans #-} module Main where  import GHC.TypeLits (KnownNat, natVal, type (<=))-import Data.Maybe (fromJust) import Data.Proxy (Proxy(..))-import Control.Applicative (empty)  import qualified Math.Algebra.Matrix as M-import Math.Algebra.Field.Instances -- Import random instances+import Math.Algebra.Field.Instances() -- Import random instances import qualified Math.Core.Utils as F import qualified Math.Algebra.Field.Base as F import qualified Math.Algebra.Field.Extension as F@@ -21,11 +20,11 @@ import qualified Test.Tasty.SmallCheck as S import qualified Test.Tasty.QuickCheck as Q import qualified Test.SmallCheck.Series as S-import qualified Test.QuickCheck.Arbitrary as Q  main :: IO () main = defaultMain tests +tests :: TestTree tests = testGroup "linear-code" [ fieldTests, codeTests ]  fieldTests :: TestTree@@ -40,6 +39,7 @@ codeTests =     let tc = trivialCode :: BinaryCode 5 3         hamming74 = hamming :: BinaryCode 7 4+        eHamming94 = extendCode hamming74 :: BinaryCode 9 4      in testGroup "Codes"         [ testGroup "Instances"             [ testCase "Show works for unknown distance" $@@ -77,22 +77,52 @@                                 (encode hamming74 (fromList [x,y,z,w]))             , Q.testProperty "List all codewords" $                 \(c :: LinearCode 7 4 F.F5) ->-                    length (codewords c) == 5^4+                    length (codewords c) == 5^(4 :: Int)             , Q.testProperty "Simple decode of single error" $                 \(v :: Vector 4 F2) ->-                    let c = encode hamming74 v :: Vector 7 F2-                     in decode hamming74 (c + e2) == Just c+                    let w = encode hamming74 v :: Vector 7 F2+                     in decode hamming74 (w + e2) == Just w             ]+        , testGroup "Code transformers"+            [ Q.testProperty "dualCode . dualCode == id" $+                \(c :: LinearCode 9 3 F.F4) ->+                    c == (dualCode . dualCode $ c)+            ]+{- This test is too slow+   , testGroup "Golay"+            [ testCase "Golay can correct 3 errors" $+                -- \((w,a,b,c) :: (Vector 12 F2,F2,F2,F2)) ->+                let w = fromList [0,0,1,0,1,1,1,1,0,1,0,1] :: Vector 12 F2+                    (a,b,c) = (1,1,1) :: (F2,F2,F2)+                 in+                    let v = encode golay w+                        ve = v + a M.^* e3 + b M.^* e7 + c M.^* eVec 14+                     in decode golay ve @?= Just v+            ]+-}         , testGroup "Standard form"             [ Q.testProperty "Standard form of standard form is equal" $                 \(c :: LinearCode 7 4 F.F3) ->                     let sc = standardFormGenerator c                      in sc == standardForm sc             ]-        --, testGroup "Code transformers"-        --    [ testProperty "Dual of dual is identitiy" $-        --        \(c :: LinearCode 7 4 F2) -> (dualCode . dualCode) c == c-        --    ]+        , testGroup "Code transformers"+            [ Q.testProperty "Dual of dual is identitiy" $+                \(c :: LinearCode 7 4 F2) -> (dualCode . dualCode) c == c+            , Q.testProperty "Extended codes are of same distance" $+                \(c :: LinearCode 7 4 F5) ->+                    distance (extendCode c :: LinearCode 9 4 F5) == distance c+            , testCase "Extended hamming have distance 3" $+                distance (extendCode hamming74 :: BinaryCode 9 4) @?= Just 3+            , Q.testProperty "Extended hamming can correct 1 error" $+                \(v :: Vector 4 F2) ->+                    let w = encode eHamming94 v+                     in decode eHamming94 (w + e3) == Just w+            , Q.testProperty "Extended hamming can correct 1 in extension" $+                \(v :: Vector 4 F2) ->+                    let w = encode eHamming94 v+                     in decode eHamming94 (w + e8) == Just w+            ]         ]  -- SmallCheck Series for GF