-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/
-- | A simple library for linear codes (coding theory, error correction)
--
-- Please see the README on GitHub at
-- https://github.com/wchresta/linear-code#readme
@package linear-code
@version 0.1.1
-- | Some important instances like Random and Bounded are
-- missing from HaskellForMath's implementation of finite fiels.
-- Here, orphan instances for these classes are added.
module Math.Algebra.Field.Instances
instance Math.Common.IntegerAsType.IntegerAsType p => System.Random.Random (Math.Algebra.Field.Base.Fp p)
instance (Math.Core.Utils.FinSet fp, GHC.Classes.Ord fp, GHC.Num.Num fp, Math.Algebra.Field.Extension.PolynomialAsType fp poly) => System.Random.Random (Math.Algebra.Field.Extension.ExtensionField fp poly)
instance Math.Common.IntegerAsType.IntegerAsType p => GHC.Enum.Bounded (Math.Algebra.Field.Base.Fp p)
instance (Math.Core.Utils.FinSet fp, GHC.Classes.Eq fp, GHC.Num.Num fp, Math.Algebra.Field.Extension.PolynomialAsType fp poly) => GHC.Enum.Bounded (Math.Algebra.Field.Extension.ExtensionField fp poly)
-- | Some finite field parameters are missing from HaskellForMaths
-- implementation. Here, we add type classes to add these parameters to
-- the type level.
module Math.Algebra.Field.Static
-- | The characteristic of a finite field on the type level. The
-- characteristic is: For any element x in the field f
-- with characteristic c, we have: c * x = x + x + .. + x (c
-- times) = 0
-- | Characteristic of a field. It takes a finite field type in the proxy
-- value and gives the characteristic. This is done using type families
-- To support new finite field types, you need to add a type instance for
-- the type family Characteristic.
char :: forall c f. (KnownNat c, c ~ Characteristic f) => Proxy f -> Int
-- | Type family which gives the degree of a polynomial type. This is used
-- to extract type level information from Extension
-- | Type family which gives the size of a field, i.e. the number of
-- elements of a finite field.
-- | Math.Algebra.Matrix wraps matrix's Data.Matrix functions and
-- adds size information on the type level. Additionally, it fixes some
-- issues that makes the library work well with finite fields. The name
-- of most functions is the same as in Data.Matrix
module Math.Algebra.Matrix
-- | A matrix over the type f with m rows and n
-- columns. This just wraps the Matrix constructor and adds size
-- information to the type
newtype Matrix (m :: Nat) (n :: Nat) (f :: *)
Matrix :: (Matrix f) -> Matrix
-- | O(rows*cols). Generate a matrix from a generator function. |
-- The elements are 1-indexed, i.e. top-left element is (1,1).
matrix :: forall m n a. (KnownNat m, KnownNat n) => ((Int, Int) -> a) -> Matrix (m :: Nat) (n :: Nat) a
-- | A row vector (a matrix with one row).
type Vector = Matrix 1
-- | O(rows*cols). The transpose of a matrix.
transpose :: forall m n a. Matrix m n a -> Matrix n m a
-- | Horizontally join two matrices. Visually:
--
--
-- ( 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
-- | 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
-- | O(rows*cols). Identity matrix
identity :: forall n a. (Num a, KnownNat n) => Matrix n n a
-- | O(rows*cols). The zero matrix
zero :: forall m n a. (Num a, KnownNat n, KnownNat m) => Matrix m n a
-- | Create a matrix from a list of elements. The list must have exactly
-- length n*m. This is checked or else an exception is thrown.
fromList :: forall m n a. (KnownNat m, KnownNat n) => [a] -> Matrix m n a
-- | Create a matrix from a list of rows. The list must have exactly
-- m lists of length n. An exception is thrown
-- otherwise.
fromLists :: forall m n a. (KnownNat m, KnownNat n) => [[a]] -> Matrix m n a
-- | Get the elements of a matrix stored in a list.
toList :: forall m n a. Matrix m n a -> [a]
-- | Get the elements of a matrix stored in a list of lists, where each
-- list contains the elements of a single row.
toLists :: forall m n a. Matrix m n a -> [[a]]
-- | Type safe matrix multiplication
(.*) :: forall m k n a. Num a => Matrix m k a -> Matrix k n a -> Matrix m n a
-- | Type safe scalar multiplication
(^*) :: forall m n a. Num a => a -> Matrix m n a -> Matrix m n a
-- | Reduced row echelon form. Taken from rosettacode. This is not the
-- implementation provided by the matrix package.
-- https://rosettacode.org/wiki/Reduced_row_echelon_form#Haskell
rref :: forall m n a. (KnownNat m, KnownNat n, m <= n, Fractional a, Eq a) => Matrix m n a -> Matrix m n a
-- | O(1). Extract a submatrix from the given position. The size of
-- the extract is determined by the types, i.e. the parameters define
-- which element is the top-left element of the extract. CAUTION: It is
-- not checked if an extract is possible. Wrong parameters will cause an
-- exception.
submatrix :: forall m n m' n' a. (KnownNat m, KnownNat n, KnownNat m', KnownNat n', m' <= m, n' <= n) => Int -> Int -> Matrix m n a -> Matrix m' n' a
instance GHC.Base.Monoid f => GHC.Base.Monoid (Math.Algebra.Matrix.Matrix m n f)
instance Data.Traversable.Traversable (Math.Algebra.Matrix.Matrix m n)
instance Data.Foldable.Foldable (Math.Algebra.Matrix.Matrix m n)
instance GHC.Base.Applicative (Math.Algebra.Matrix.Matrix m n)
instance GHC.Base.Functor (Math.Algebra.Matrix.Matrix m n)
instance GHC.Classes.Eq f => GHC.Classes.Eq (Math.Algebra.Matrix.Matrix m n f)
instance GHC.Show.Show f => GHC.Show.Show (Math.Algebra.Matrix.Matrix m n f)
instance GHC.Classes.Ord f => GHC.Classes.Ord (Math.Algebra.Matrix.Matrix m n f)
instance GHC.Num.Num f => GHC.Num.Num (Math.Algebra.Matrix.Matrix m n f)
instance (GHC.TypeNats.KnownNat m, GHC.TypeNats.KnownNat n, System.Random.Random a) => System.Random.Random (Math.Algebra.Matrix.Matrix m n a)
-- | Naive implementation of coding theory linear codes and error
-- correcting codes over arbitrary fields, including finite fields. Goes
-- well with the HaskellForMath library and its finite field
-- implementations in Math.Algebra.Field. To use extension
-- fields (fields of prime power, i.e. <math> with <math>,
-- use one of the exported finite fields in
-- Math.Algebra.Field.Extension like F16 and its generator
-- a16.
--
-- As theoretical basis, Introduction to Coding Theory by Yehuda Lindell
-- is used. It can be found at
-- http://u.cs.biu.ac.il/~lindell/89-662/coding_theory-lecture-notes.pdf
--
-- Usage
--
--
-- >>> :set -XDataKinds
-- >>> c <- randomIO :: IO (LinearCode 7 4 F5)
-- >>> c
-- [7,4]_5-Code
-- >>> generatorMatrix c
-- ( 1 0 1 0 0 2 0 )
-- ( 0 2 0 0 1 2 0 )
-- ( 0 1 0 1 0 1 0 )
-- ( 1 0 0 0 0 1 1 )
-- >>> e1 :: Vector 4 F5
-- ( 1 0 0 0 )
-- >>> v = encode c e1
-- >>> v
-- ( 1 0 1 0 0 2 0 )
-- >>> 2 ^* e4 :: Vector 7 F3
-- ( 0 0 0 2 0 0 0 )
-- >>> vWithError = v + 2 ^* e4
-- >>> vWithError
-- ( 1 0 1 2 0 2 0 )
-- >>> isCodeword c v
-- True
-- >>> isCodeword c vWithError
-- False
-- >>> decode c vWithError
-- Just ( 1 0 2 2 2 2 0 )
--
--
-- Notice, the returned vector is NOT the one without error. The reason
-- for this is that a random code most likely does not have a distance
-- >2 which would be needed to correct one error. Let's try with a
-- hamming code
--
--
-- >>> c = hamming :: BinaryCode 7 4
-- >>> generatorMatrix c
-- ( 1 1 0 1 0 0 0 )
-- ( 1 0 1 0 1 0 0 )
-- ( 0 1 1 0 0 1 0 )
-- ( 1 1 1 0 0 0 1 )
-- >>> v = encode c e2
-- >>> vWithError = v + e3
-- >>> Just v' = decode c vWithError
-- >>> v' == v
-- True
--
module Math.Algebra.Code.Linear
-- | A <math>-Linear code over the field f. The code
-- parameters f,n and k are carried on the
-- type level. A linear code is a subspace C of <math>
-- generated by the generator matrix.
data LinearCode (n :: Nat) (k :: Nat) (f :: *)
LinearCode :: Generator n k f -> CheckMatrix n k f -> Maybe Int -> SyndromeTable n k f -> LinearCode
-- | Generator matrix, used for most of the operations
[generatorMatrix] :: LinearCode -> Generator n k f
-- | Check matrix which can be automatically calculated from the standard
-- form generator.
[checkMatrix] :: LinearCode -> CheckMatrix n k f
-- | The minimal distance of the code. This is the parameter <math>
-- in <math> notation of code parameters. The problem of finding
-- the minimal distance is NP-Hard, thus might not be available.
[distance] :: LinearCode -> Maybe Int
-- | A map of all possible syndromes to their error vector. It is used to
-- use syndrome decoding, a very slow decoding algorithm.
[syndromeTable] :: LinearCode -> SyndromeTable n k f
-- | A Generator is the generator matrix of a linear code, not
-- necessarily in standard form.
type Generator (n :: Nat) (k :: Nat) = Matrix k n
-- | A CheckMatrix or parity matrix is the dual of a
-- Generator. It can be used to check if a word is a valid code
-- word for the code. Also, <math> i.e. the code is generated by
-- the kernel of a check matrix.
type CheckMatrix (n :: Nat) (k :: Nat) = Matrix (n - k) n
-- | Generate a linear <math>-Code over the field f with the
-- generator in standard form (I|A), where the given function
-- generates the <math>-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 -> LinearCode n k f
-- | Generate a linear <math>-Code over the field f with the
-- generator in standard form (I|A), where the given function
-- generates the <math>-matrix A.
codeFromAD :: forall k n f. (KnownNat n, KnownNat k, k <= n, Eq f, FinSet f, Num f, Ord f) => Maybe Int -> Matrix k (n - k) f -> LinearCode n k f
-- | Uses Gaussian eleminiation via rref from 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
-- | The standard from generator of a linear code. Uses standardForm
-- to 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
-- | A row vector (a matrix with one row).
type Vector = Matrix 1
-- | Get the codeword generated by the given k-sized vector.
encode :: forall n k f. Num f => LinearCode n k f -> Vector k f -> Vector n f
-- | Check if the given candidate code word is a valid code word for the
-- given linear code. If not, the party check failed.
isCodeword :: forall n k f. (Eq f, Num f, KnownNat n, KnownNat k, k <= n) => LinearCode n k f -> Vector n f -> Bool
-- | Check if the given candidate code word has errors, i.e. if some
-- element changed during transmission. This is equivalent with
-- not isCodeword
hasError :: forall n k f. (Eq f, Num f, KnownNat n, KnownNat k, k <= n) => LinearCode n k f -> Vector n f -> Bool
-- | The hamming weight of a Vector is an Int between 0 and n
weight :: forall f m. (Eq f, Num f, Functor m, Foldable m) => m f -> Int
-- | A list of all codewords
codewords :: forall n k f. (KnownNat n, KnownNat k, k <= n, Num f, Eq f, FinSet f) => LinearCode n k f -> [Vector n f]
-- | List all vectors of length n over field f
allVectors :: forall n f. (KnownNat n, FinSet f, Num f, Eq f) => [Vector n f]
-- | List all vectors of length n with non-zero elements over field f
fullVectors :: forall n f. (KnownNat n, FinSet f, Num f, Eq f) => [Vector n f]
-- | List of all words with given hamming weight
hammingWords :: forall n f. (KnownNat n, FinSet f, Num f, Eq f) => Int -> [Vector n f]
-- | 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]
-- | Give the syndrome of a word for the given code. This is 0 if the word
-- is a valid code word.
syndrome :: forall n k f. Num f => LinearCode n k f -> Vector n f -> Syndrome n k f
-- | Synonym for syndromeDecoding, an inefficient decoding algorithm that
-- works for all linear codes.
decode :: forall n k f. (KnownNat n, KnownNat k, k <= n, Ord f, Num f) => LinearCode n k f -> Vector n f -> Maybe (Vector n f)
-- | Uses the exponential-time syndrome decoding algorithm for general
-- codes. c.f:
-- https://en.wikipedia.org/wiki/Decoding_methods#Syndrome_decoding
syndromeDecode :: forall n k f. (KnownNat n, KnownNat k, k <= n, Ord f, Num f) => LinearCode n k f -> Vector n f -> Maybe (Vector n f)
-- | Return a syndrome table for the given linear code. If the distance is
-- not known (i.e. minDist c = Nothing) this is very
-- inefficient.
calcSyndromeTable :: forall n k f. (KnownNat n, KnownNat k, k <= n, Eq f, FinSet f, Num f, Ord f) => LinearCode n k f -> SyndromeTable n k f
-- | Replace the syndromeTable of a code with a newly calculated
-- syndrome table for the (current) generator. Useful to get a syndrome
-- table for transformed codes when the table cannot be transformed, too.
recalcSyndromeTable :: forall n k f. (KnownNat n, KnownNat k, k <= n, Eq f, FinSet f, Num f, Ord f) => LinearCode n k f -> LinearCode n k f
-- | A syndrome table is a map from syndromes to their minimal weight
-- representative. Every vector v has a syndrome <math>.
-- This table reverses the syndrome function S and chooses the
-- vector with the smallest hamming weight from it's image. This is a
-- lookup table for syndrome decoding.
type SyndromeTable n k f = Map (Syndrome n k f) (Vector n f)
-- | 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
-- | 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 -> LinearCode n k f -> LinearCode n (n - k) f
-- | 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. 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
-- | Extend the given code <math> by zero-columns. Vectors
-- <math> have the form <math> . 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
-- | The trivial code is the identity code where the parity bits are all
-- zero.
trivialCode :: forall n k f. (KnownNat n, KnownNat k, k <= n, Eq f, FinSet f, Num f, Ord f) => LinearCode n k f
-- | A simplex code is a code generated by all possible codewords
-- consisting of 0's and 1's except the zero vector.
simplex :: forall k p s. (KnownNat s, KnownNat k, IntegerAsType p, 1 <= (s ^ k), k <= (s ^ k), (1 + k) <= (s ^ k), Size (Fp p) ~ s) => LinearCode ((s ^ k) - 1) k (Fp p)
-- | 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
-- | 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
-- | A binary code is a linear code over the field GF(2)
type BinaryCode n k = LinearCode n k F2
-- | A random permutation matrix
randomPermMatrix :: forall g n r. (KnownNat n, Num r, RandomGen g) => g -> (Matrix n n r, g)
-- | Convenience function to extract the length n from the type
-- level
codeLength :: forall n k f. KnownNat n => LinearCode n k f -> Int
-- | Convenience function to extract the rank k from the type
-- level.
rank :: forall n k f. KnownNat k => LinearCode n k f -> Int
-- | Standard base vector [0..0,1,0..0] for any field. Parameter must be
-- >=1
eVec :: forall n f. (KnownNat n, Num f) => Int -> Vector n f
-- | First base vector [1,0..0]
e1 :: forall n f. (KnownNat n, Num f) => Vector n f
-- | Second base vector [0,1,0..0]
e2 :: forall n f. (KnownNat n, Num f) => Vector n f
e3 :: forall n f. (KnownNat n, Num f) => Vector n f
e4 :: forall n f. (KnownNat n, Num f) => Vector n f
e5 :: forall n f. (KnownNat n, Num f) => Vector n f
e6 :: forall n f. (KnownNat n, Num f) => Vector n f
e7 :: forall n f. (KnownNat n, Num f) => Vector n f
e8 :: forall n f. (KnownNat n, Num f) => Vector n f
e9 :: forall n f. (KnownNat n, Num f) => Vector n f
e10 :: forall n f. (KnownNat n, Num f) => Vector n f
-- | Characteristic of a field. It takes a finite field type in the proxy
-- value and gives the characteristic. This is done using type families
-- To support new finite field types, you need to add a type instance for
-- the type family Characteristic.
char :: forall c f. (KnownNat c, c ~ Characteristic f) => Proxy f -> Int
-- | O(rows*cols). Generate a matrix from a generator function. |
-- The elements are 1-indexed, i.e. top-left element is (1,1).
matrix :: forall m n a. (KnownNat m, KnownNat n) => ((Int, Int) -> a) -> Matrix (m :: Nat) (n :: Nat) a
-- | O(rows*cols). The zero matrix
zero :: forall m n a. (Num a, KnownNat n, KnownNat m) => Matrix m n a
-- | O(rows*cols). The transpose of a matrix.
transpose :: forall m n a. Matrix m n a -> Matrix n m a
-- | Create a matrix from a list of elements. The list must have exactly
-- length n*m. This is checked or else an exception is thrown.
fromList :: forall m n a. (KnownNat m, KnownNat n) => [a] -> Matrix m n a
-- | Create a matrix from a list of rows. The list must have exactly
-- m lists of length n. An exception is thrown
-- otherwise.
fromLists :: forall m n a. (KnownNat m, KnownNat n) => [[a]] -> Matrix m n a
type F2 = Fp T2
type F3 = Fp T3
type F5 = Fp T5
type F7 = Fp T7
type F11 = Fp T11
type F4 = ExtensionField F2 ConwayF4
type F8 = ExtensionField F2 ConwayF8
type F16 = ExtensionField F2 ConwayF16
type F9 = ExtensionField F3 ConwayF9
instance (GHC.Classes.Eq f, GHC.Real.Fractional f, GHC.TypeNats.KnownNat n, GHC.TypeNats.KnownNat k, k GHC.TypeNats.<= n) => GHC.Classes.Eq (Math.Algebra.Code.Linear.LinearCode n k f)
instance (GHC.TypeNats.KnownNat n, GHC.TypeNats.KnownNat k, GHC.TypeNats.KnownNat (Math.Algebra.Field.Static.Characteristic f)) => GHC.Show.Show (Math.Algebra.Code.Linear.LinearCode n k f)
instance (GHC.TypeNats.KnownNat n, GHC.TypeNats.KnownNat k, k GHC.TypeNats.<= n, GHC.Classes.Eq f, Math.Core.Utils.FinSet f, GHC.Num.Num f, GHC.Classes.Ord f) => GHC.Enum.Bounded (Math.Algebra.Code.Linear.LinearCode n k f)
instance (GHC.TypeNats.KnownNat n, GHC.TypeNats.KnownNat k, k GHC.TypeNats.<= n, GHC.Classes.Eq f, Math.Core.Utils.FinSet f, GHC.Num.Num f, GHC.Classes.Ord f, System.Random.Random f) => System.Random.Random (Math.Algebra.Code.Linear.LinearCode n k f)