File size: 3,330 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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
-- SPDX-License-Identifier: AGPL-3.0-or-later

-- | Linear recurrences over a field.
--
-- A connection polynomial @C(x) = 1 + c_1 x + ... + c_L x^L@ generates @s@
-- when @s_n + c_1 s_(n-1) + ... + c_L s_(n-L) = 0@ for every @n >= L@. The
-- linear complexity of a finite sequence is the least @L@ for which some such
-- @C@ exists. Berlekamp–Massey computes it, and a minimal @C@, in @O(N^2)@
-- field operations.
--
-- The algorithm is written once, over any 'Field'. The prism-ciris kernel only
-- verified that a given recurrence held; this finds the recurrence.
module MP.Recurrence
  ( Poly
  , berlekampMassey
  , generates
  , runLFSR
  , period
  ) where

import MP.Algebra

-- | Coefficients, constant term first.
type Poly a = [a]

-- | Linear complexity and a minimal connection polynomial of exactly
-- @L + 1@ coefficients.
berlekampMassey :: Field a => [a] -> (Int, Poly a)
berlekampMassey s = finish (go 0 [one] [one] 0 1 one)
  where
    n = length s
    finish (l, c) = (l, take (l + 1) (c ++ repeat zero))
    go k c b l m bInv0
      | k >= n = (l, c)
      | otherwise =
          let d = discrepancy k c l
           in if isZero d
                then go (k + 1) c b l (m + 1) bInv0
                else
                  let coef = d .*. bInv0
                      c' = polySub c (shiftScale m coef b)
                   in if 2 * l <= k
                        then go (k + 1) c' c (k + 1 - l) 1 (maybe zero id (recipF d))
                        else go (k + 1) c' b l (m + 1) bInv0
    -- d = s_k + sum_{i=1..L} c_i s_(k-i)
    discrepancy k c l =
      sumS [ci .*. sk | (i, ci) <- zip [0 ..] (take (l + 1) c), Just sk <- [ix (k - i)]]
    ix i = if i < 0 then Nothing else case drop i s of
      (v : _) -> Just v
      [] -> Nothing

-- | @x^m * coef * b(x)@.
shiftScale :: Semiring a => Int -> a -> Poly a -> Poly a
shiftScale m coef b = replicate m zero ++ map (coef .*.) b

polySub :: Ring a => Poly a -> Poly a -> Poly a
polySub (x : xs) (y : ys) = (x .-. y) : polySub xs ys
polySub xs [] = xs
polySub [] ys = map neg ys

-- | Whether @c@ generates every term of @s@ from its predecessors.
generates :: Ring a => Poly a -> [a] -> Bool
generates c s = all holds [l .. length s - 1]
  where
    l = length c - 1
    window k = reverse (take (l + 1) (drop (k - l) s)) -- s_k, s_(k-1), .., s_(k-L)
    holds k = isZero (sumS (zipWith (.*.) c (window k)))

-- | Extend @l@ initial terms by the recurrence, for @count@ terms in total.
runLFSR :: Ring a => Poly a -> [a] -> Int -> [a]
runLFSR c initial count = take count (initial ++ continue (reverse initial))
  where
    taps = drop 1 c -- c_1 .. c_L
    -- @recent@ is s_(n-1), s_(n-2), ..; zipWith stops at the last tap.
    continue recent =
      let v = neg (sumS (zipWith (.*.) taps recent))
       in v : continue (v : recent)

-- | The least @p >= 1@ with the state after @p@ steps equal to the initial
-- state, searching up to @bound@ steps. Over GF(2) a primitive connection
-- polynomial of degree @L@ gives the maximal period @2^L - 1@.
period :: (Ring a, Eq a) => Poly a -> [a] -> Int -> Maybe Int
period c initial bound =
  let l = length initial
      s = runLFSR c initial (bound + l)
      stateAt k = take l (drop k s)
   in case [p | p <- [1 .. bound], stateAt p == initial] of
        (p : _) -> Just p
        [] -> Nothing