src/TLB/LFSR.py

   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
   5
   6
   7 class LFSRPolynomial(set):
   8     """ implements a polynomial for use in LFSR
   9     """
  10     def __init__(self, exponents=()):
  11         for e in 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
  15
  16     @property
  17     def max_exponent(self):
  18         return max(self) # derived from set, so this returns the max exponent
  19
  20     @property
  21     def exponents(self):
  22         exponents = list(self) # get elements of set as a list
  23         exponents.sort(reverse=True)
  24         return exponents
  25
  26     def __str__(self):
  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)
  30
  31     def __repr__(self):
  32         return "LFSRPolynomial(%s)" % self.exponents
  33
  34
  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])
  59
  60
  61 class LFSR(LFSRPolynomial, Elaboratable):
  62     """ implements a Linear Feedback Shift Register
  63     """
  64     def __init__(self, polynomial):
  65         """ Inputs:
  66             ------
  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)
  70
  71             Outputs:
  72             -------
  73             :state: the LFSR state.  bitwidth is taken from the polynomial
  74                     maximum exponent.
  75
  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)
  79         """
  80         LFSRPolynomial.__init__(self, polynomial)
  81         self.state = Signal(self.max_exponent, reset=1)
  82         self.enable = Signal(reset=1)
  83
  84     def elaborate(self, platform):
  85         m = Module()
  86         # do absolutely nothing if the polynomial is empty (always has a zero)
  87         if self.max_exponent <= 1:
  88             return m
  89
  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)
  92         for exponent in self:
  93             if exponent > 0: # don't have to skip, saves CPU cycles though
  94                 feedback ^= self.state[exponent - 1]
  95
  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)
 101
 102         return m
 103
 104
 105 # example: Poly24
 106 if __name__ == '__main__':
 107     p24 = rtlil.convert(LFSR(LFSR_POLY_24))
 108     with open("lfsr2_p24.il", "w") as f:
 109         f.write(p24)