[GaloisLFSR] Taps defined opposite of Galois Polynomials

[michael-etzkorn]

Type of issue: other enhancement

Impact: no functional change (additional documentation) | API addition (no impact on existing code)

Development Phase: request

Other information

For a practical example, take the LFSR polynomial: X16+X5+X4+X3+1 which is defined for both USB3 (you can check appendix B for reference) and PCIe Gen 1 and 2. Naively attempting to use the API with these taps, one can miss the fact that the LFSR is actually notated backwards to the notation used for LFSR polynomials.

Initializing the LFSR to 0xFFFF, we should expect 0xe817 (appendix B of USB3.2 confirms this) after advancing 8 serial steps. Instead we get 0xd7ee. Here's a small reproducible failing case (there's likely a better way to compare the entire vector of bools):

  test(
    new GaloisLFSR(
      width = 16,
      // taps = Set(13, 12, 11), // should not need to define taps this way. This produces the expected 0xe817
      taps = Set(16, 5, 4, 3),
      seed = Some(0xffffL),
      step = 8
    )
  ) { c =>
    c.reset.poke(true.B)
    c.clock.step()
    c.reset.poke(false.B)
    c.clock.step()
    c.io.increment.poke(true.B)
    c.clock.step()
    c.io.out(0).expect(1.B) // we expect 0xe817. 0xd7ee differs in the lsb (and a lot of other places)
  }

If the current behavior is a bug, please provide the steps to reproduce the problem: It'd be nice if this was included in the documentation to prevent implementation bugs.

What is the current behavior? Taps have to be defined reverse to the polynomial. What is the expected behavior? Ideally, the tap numbers would match the polynomial. At this point, I think the best we can do is offer an addition to the API to optionally reverse the LFSR or document the API's behavior (the polynomials in the documentation right now are misleading).

[michael-etzkorn]

This would be ideal. Additionally, the reference links in the scaladoc for LFSR outside of wikipedia are dead.

class GaloisLFSR(
  width:         Int,
  taps:          Set[Int],
  seed:          Option[BigInt] = Some(1),
  val reduction: LFSRReduce = XOR,
  step:          Int = 1,
  updateSeed:    Boolean = false)
    extends PRNG(width, seed, step, updateSeed)
    with LFSR {

  def delta(s: Seq[Bool]): Seq[Bool] = {
    val first = s.head
    (s.tail :+ first).zipWithIndex.map {
---  case (a, i) if taps(i + 1) && (i + 1 != s.size) => reduction(a, first)
+++  case (a, i) if taps(width - i - 1) && ((width - i - 1) != 0) => reduction(a, first)
      case (a, _)                                     => a
    }
  }

}

[seldridge]

Yeah, I think I botched this for the Galois LFSR. I'm fine if you want to change it, specifically, to use the taps the way you specify them. The only thing to check is if this continues to work for the big table of LFSR taps or what has to be done to transform that so that it will work with Galois LFSRs. A link to that appears to now live here: https://datacipy.cz/lfsr_table.pdf

[michael-etzkorn]

There's another related issue where the seed of these LFSRs for USB3 Gen2 and PCIe Gen3 has to be put in opposite to the spec. I didn't notice for gen1 since 0xFFFF is symmetrical.

When I get the chance, I'll open a PR to reverse the bit orientation between FibonacciLFSR and GaloisLFSR so things like taps, seeding, and asUInt will work correctly with the GaloisLFSR. This shouldn't affect any general PRNG usage of LFSR and will fix the scrambling use case where the PRNG must follow a specific ordering.

I'll check if this affects the max period of the big table and reverse the notation there if need be.

---

• The confusion on notation is understandable given what that paper uses and what's currently on wikipedia.
• Based on the PCIe and USB specifications (and some sampled academic notes through googling), the notation suggested on Wikipedia and in that paper does not seem to be the standard notation for Galois LFSRs.
• It'd be best to switch the notation to a right shift register from lsb to msb.