chipsalliance / chipsalliance/chisel

[GaloisLFSR] Taps defined opposite of Galois Polynomials

Open
#2,483 3 comments 0 reactions 0 assignees View on GitHub
Dominant language
Scala
Stars
4.8k
Forks
658
Avg merge
18h 59m
Merged PRs (30d)
14

Description

**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](https://www.usb.org/document-library/usb-32-specification-released-september-22-2017-and-ecns) (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):
```scala
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).

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.