[Libre-soc-bugs] [Bug 782] add galois field bitmanip instructions

[bugzilla-daemon at libre-soc.org]

https://bugs.libre-soc.org/show_bug.cgi?id=782

--- Comment #6 from Luke Kenneth Casson Leighton <lkcl at lkcl.net> ---
(In reply to Jacob Lifshay from comment #3)
> (In reply to Luke Kenneth Casson Leighton from comment #2)
> > (In reply to Jacob Lifshay from comment #1)
> > > I could be wrong, but from what I know of how Galois fields work, the degree
> > > parameter is entirely derived from the reducing polynomial:
> > 
> > iirc some implementations have an implicit top bit removed similar
> > to how 
> > 
> > > If this sounds good, I'll make the changes needed to have the reducing
> > > polynomial as an input, and degree derived from it.
> > 
> > doesn't feel right.
> > 
> > i definitely need the full parameter space similar to FMAC, a full
> > 4-operand MAC, for the SVP64 NTT to work.
> 
> then we need a gfmadd instruction.
> 
> we probably also want a gfdiv instruction, but that may be too complex.
> 
> also, gfadd is just xor iirc...so maybe we don't need that one.
> 
> > 
> > (NTT, part of Reed Solomon, is the same algorithm as Discrete Fourier
> > Transform just using GF arithmetic)
> > 
> > https://en.wikipedia.org/wiki/Talk%3ANumber-theoretic_transform
> > 
> > note in that page that:
> > 
> >      The modulus in a Number Theoretic Transfer doesn't necessarily have to
> > be prime.
> 
> yup, here, I'm assuming the modulus (which ends up being the number of
> values in the field (not to be confused with the reducing polynomial, which
> is a different kind of modulus)) is 2^deg(reducing-polynomial).

do they mean e.g. Gf 2^5 

> also, iirc it's Number Theoretic *Transform* (like Fourier Transform).

doh. how did i end up typing transfer??

> > this tends to point towards using SPRs.
> 
> ok, sounds good!
> 
> what do you think of just using CTR?

see sv.bc for how much functionality would be lost.
sv.bc is stunningly powerful, a "simple" bc gets something
mad like 128 additional options half of which rely on CTR.


>         # all reducing polynomials of degree > 1 must have the LSB set,
>         # because they must be irreducible polynomials (meaning they
>         # can't be factored),


take a look again at the wikipedia NTT talk page apparently nonprime
polynomials are actually useful, and LSB=0 is nonprime.

oh right GF 2^5 i.e.the degree.

can you doublexheck to see if there are any circumstances where
a polyynomial with LSB=0 is useful or not?

-- 
You are receiving this mail because:
You are on the CC list for the bug.