File size: 2,730 Bytes
5316c4e
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
-- SPDX-License-Identifier: AGPL-3.0-or-later

module Main (main) where

import MP.Algebra
import MP.Check
import MP.Recurrence

main :: IO ()
main =
  runSuite
    "mp-seq"
    [ prop "SQ-01" "BM's polynomial regenerates the sequence over GF(2)" (listUpTo 40 gf2) regenerates
    , prop "SQ-01" "BM's polynomial regenerates the sequence over Q" (listUpTo 14 (rationalIn (-5) 5 3)) regenerates
    , propN "SQ-02" "BM is minimal: no shorter LFSR generates the sequence (GF(2), brute force)" 300 (listUpTo 11 gf2) minimal
    , propN "SQ-03" "a length-l LFSR is recovered from 2l terms and predicts the rest (Massey)" 300 genLFSR recovered
    , unit "SQ-04" "x^5 + x^2 + 1 is primitive: period 31, linear complexity 5" $
        let c = map GF2 [True, False, True, False, False, True] -- 1 + x^2 + x^5
            s = runLFSR c (map GF2 [True, False, False, False, False]) 62
         in period c (take 5 s) 100 === Just 31 .&&. fst (berlekampMassey s) === 5
    , unit "SQ-04" "x^4 + x^2 + 1 = (x^2 + x + 1)^2 is not primitive: period 6, not 15" $
        let c = map GF2 [True, False, True, False, True]
         in period c (map GF2 [True, False, False, False]) 100 === Just 6
    , unit "SQ-05" "Fibonacci over Q has connection polynomial 1 - x - x^2" $
        berlekampMassey (take 20 fibs) === (2, [1, -1, -1])
    , unit "SQ-05" "the zero sequence has linear complexity 0" $
        berlekampMassey (replicate 10 (0 :: Rational)) === (0, [1])
    ]
  where
    fibs = 0 : 1 : zipWith (+) fibs (drop 1 fibs) :: [Rational]

gf2 :: Gen GF2
gf2 = GF2 <$> boolG

regenerates :: (Field a, Show a) => [a] -> Result
regenerates s =
  let (l, c) = berlekampMassey s
   in assert ("C = " <> show c <> " does not generate it") (generates c s)
        .&&. length c === l + 1
        .&&. assert "L > length" (l <= length s)

-- Every connection polynomial over GF(2) of degree at most l.
allPolys :: Int -> [Poly GF2]
allPolys l = map (one :) (mapM (const [GF2 False, GF2 True]) [1 .. l])

minimal :: [GF2] -> Result
minimal s =
  let (l, _) = berlekampMassey s
      shorter = [c | k <- [0 .. l - 1], c <- allPolys k, generates c s]
   in assert ("a length " <> show (map (subtract 1 . length) shorter) <> " LFSR exists") (null shorter)

genLFSR :: Gen ([GF2], [GF2])
genLFSR = do
  l <- intIn 1 8
  taps <- listOfLength l gf2
  initial <- listOfLength l gf2
  pure (one : taps, initial)

recovered :: ([GF2], [GF2]) -> Result
recovered (c, initial) =
  let l = length initial
      long = runLFSR c initial (6 * l)
      (l', c') = berlekampMassey (take (2 * l) long)
   in assert ("complexity " <> show l' <> " exceeds " <> show l) (l' <= l)
        .&&. assert ("recovered " <> show c' <> " fails beyond 2l") (generates c' long)