1 # SPDX-License-Identifier: LGPL-2.1-or-later
2 # See Notices.txt for copyright information
3 from nmigen
import Signal
, Module
, Const
, Cat
, Elaboratable
4 from nmigen
.cli
import verilog
, rtlil
7 class LFSRPolynomial(set):
8 """ implements a polynomial for use in LFSR
10 def __init__(self
, exponents
=()):
12 assert isinstance(e
, int), TypeError("%s must be an int" % repr(e
))
13 assert (e
>= 0), ValueError("%d must not be negative" % e
)
14 set.__init
__(self
, set(exponents
).union({0}
)) # must contain zero
17 def max_exponent(self
):
18 return max(self
) # derived from set, so this returns the max exponent
22 exponents
= list(self
) # get elements of set as a list
23 exponents
.sort(reverse
=True)
27 expd
= {0: "1", 1: 'x', 2: "x^{}"} # case 2 isn't 2, it's min(i,2)
28 retval
= map(lambda i
: expd
[min(i
,2)].format(i
), self
.exponents
)
29 return " + ".join(retval
)
32 return "LFSRPolynomial(%s)" % self
.exponents
35 # list of selected polynomials from https://web.archive.org/web/20190418121923/https://en.wikipedia.org/wiki/Linear-feedback_shift_register#Some_polynomials_for_maximal_LFSRs # noqa
36 LFSR_POLY_2
= LFSRPolynomial([2, 1, 0])
37 LFSR_POLY_3
= LFSRPolynomial([3, 2, 0])
38 LFSR_POLY_4
= LFSRPolynomial([4, 3, 0])
39 LFSR_POLY_5
= LFSRPolynomial([5, 3, 0])
40 LFSR_POLY_6
= LFSRPolynomial([6, 5, 0])
41 LFSR_POLY_7
= LFSRPolynomial([7, 6, 0])
42 LFSR_POLY_8
= LFSRPolynomial([8, 6, 5, 4, 0])
43 LFSR_POLY_9
= LFSRPolynomial([9, 5, 0])
44 LFSR_POLY_10
= LFSRPolynomial([10, 7, 0])
45 LFSR_POLY_11
= LFSRPolynomial([11, 9, 0])
46 LFSR_POLY_12
= LFSRPolynomial([12, 11, 10, 4, 0])
47 LFSR_POLY_13
= LFSRPolynomial([13, 12, 11, 8, 0])
48 LFSR_POLY_14
= LFSRPolynomial([14, 13, 12, 2, 0])
49 LFSR_POLY_15
= LFSRPolynomial([15, 14, 0])
50 LFSR_POLY_16
= LFSRPolynomial([16, 15, 13, 4, 0])
51 LFSR_POLY_17
= LFSRPolynomial([17, 14, 0])
52 LFSR_POLY_18
= LFSRPolynomial([18, 11, 0])
53 LFSR_POLY_19
= LFSRPolynomial([19, 18, 17, 14, 0])
54 LFSR_POLY_20
= LFSRPolynomial([20, 17, 0])
55 LFSR_POLY_21
= LFSRPolynomial([21, 19, 0])
56 LFSR_POLY_22
= LFSRPolynomial([22, 21, 0])
57 LFSR_POLY_23
= LFSRPolynomial([23, 18, 0])
58 LFSR_POLY_24
= LFSRPolynomial([24, 23, 22, 17, 0])
61 class LFSR(LFSRPolynomial
, Elaboratable
):
62 """ implements a Linear Feedback Shift Register
64 def __init__(self
, polynomial
):
67 :polynomial: the polynomial to feedback on. may be a LFSRPolynomial
68 instance or an iterable of ints (list/tuple/generator)
69 :enable: enable (set LO to disable. NOTE: defaults to HI)
73 :state: the LFSR state. bitwidth is taken from the polynomial
76 Note: if an LFSRPolynomial is passed in as the input, because
77 LFSRPolynomial is derived from set() it's ok:
78 LFSRPolynomial(LFSRPolynomial(p)) == LFSRPolynomial(p)
80 LFSRPolynomial
.__init
__(self
, polynomial
)
81 self
.state
= Signal(self
.max_exponent
, reset
=1)
82 self
.enable
= Signal(reset
=1)
84 def elaborate(self
, platform
):
86 # do absolutely nothing if the polynomial is empty (always has a zero)
87 if self
.max_exponent
<= 1:
90 # create XOR-bunch, select bits from state based on exponent
91 feedback
= Const(0) # doesn't do any harm starting from 0b0 (xor chain)
93 if exponent
> 0: # don't have to skip, saves CPU cycles though
94 feedback ^
= self
.state
[exponent
- 1]
96 # if enabled, shift-and-feedback
97 with m
.If(self
.enable
):
98 # shift up lower bits by Cat'ing in a new bit zero (feedback)
99 newstate
= Cat(feedback
, self
.state
[:-1])
100 m
.d
.sync
+= self
.state
.eq(newstate
)
106 if __name__
== '__main__':
107 p24
= rtlil
.convert(LFSR(LFSR_POLY_24
))
108 with
open("lfsr2_p24.il", "w") as f
: