chisel icon indicating copy to clipboard operation
chisel copied to clipboard
verified publisher icon chipsalliance

[NFC] GaloisLFSR: Note on taps === LSb-to-MSb polynomial

Open metzkorn opened this issue 3 years ago • 3 comments

  • Also fixed a README link issue in CONTRIBUTING.md

Related Issue: https://github.com/chipsalliance/chisel3/issues/2483

  • Due to shifting towards LSb, the polynomials are currently implemented with a LSb to MSb notation
  • Most scrambling polynomials are notated MSb-to-LSb
  • This can lead to user trouble.
  • It's still confusing even with the note, but I hope it helps. (The notation for these polynomials is a mess everywhere)

I don't think anyone cares about this quirk in the notation for the FibonacciLFSR. AFAIW, the GaloisLFSR is the only one used to implement specific scrambling polynomials.

A more proper fix requires left shifting since the Seq of Bools is MSb to LSb (need to shift towards MSb).

I triple-checked this and I'm ~95% sure I have MSb to LSb the right way around. I still appreciate someone quadruple-check ing me before merge.

Contributor Checklist

  • [ ] Did you add Scaladoc to every public function/method?
  • [ ] Did you add at least one test demonstrating the PR?
  • [ ] Did you delete any extraneous printlns/debugging code?
  • [ ] Did you specify the type of improvement?
  • [ ] Did you add appropriate documentation in docs/src?
  • [ ] Did you state the API impact?
  • [ ] Did you specify the code generation impact?
  • [ ] Did you request a desired merge strategy?
  • [ ] Did you add text to be included in the Release Notes for this change?

Type of Improvement

API Impact

Backend Code Generation Impact

Desired Merge Strategy

Release Notes

Reviewer Checklist (only modified by reviewer)

  • [ ] Did you add the appropriate labels?
  • [ ] Did you mark the proper milestone (Bug fix: 3.4.x, [small] API extension: 3.5.x, API modification or big change: 3.6.0)?
  • [ ] Did you review?
  • [ ] Did you check whether all relevant Contributor checkboxes have been checked?
  • [ ] Did you do one of the following when ready to merge:
    • [ ] Squash: You/ the contributor Enable auto-merge (squash), clean up the commit message, and label with Please Merge.
    • [ ] Merge: Ensure that contributor has cleaned up their commit history, then merge with Create a merge commit.

metzkorn avatar Jun 19 '22 20:06 metzkorn

CLA assistant check
All committers have signed the CLA.

CLAassistant avatar Jun 19 '22 20:06 CLAassistant

I'll ping @seldridge.

My understanding summarized: the shift for the multiplication of the Galois Polynomial is towards the msb when using MSb-to-LSb notation.

metzkorn avatar Jun 19 '22 20:06 metzkorn

Yeah, I think that's a good practice to get into with PRs. I figured I'd fix that link since it's a small change, but I've now separated the two changes. That PR is now #2596

The main goal of this PR is to add some a note to help #2483 while I find time to work on a more permanent patch.

metzkorn avatar Jun 22 '22 04:06 metzkorn