FPGA Central

Hello everyone,

when using an LFSR, for each clock cycle step we get a value, making
a pseudo random sequence.
Is it possible to derive an inverse function which would return
sequentially at each step j, the step number which generated the
number j with the LFSR?


Any explanations or pointers to theory or examples would be appreciated
Thanks
Sylvain

sylvain wrote:
> Hello everyone,
>
> when using an LFSR, for each clock cycle step we get a value, making
> a pseudo random sequence.
> Is it possible to derive an inverse function which would return
> sequentially at each step j, the step number which generated the
> number j with the LFSR?

The inverse is the logariphm operation in GF. There is no easy way to
compute it.

> Any explanations or pointers to theory or examples would be appreciated

R. Blahut "Theory and practice of the error control codes"

Vladimir Vassilevsky

DSP and Mixed Signal Design Consultant

http://www.abvolt.com

Vladimir Vassilevsky wrote:
> sylvain wrote:
> > Hello everyone,
> >
> > when using an LFSR, for each clock cycle step we get a value, making
> > a pseudo random sequence.
> > Is it possible to derive an inverse function which would return
> > sequentially at each step j, the step number which generated the
> > number j with the LFSR?
>
> The inverse is the logariphm operation in GF. There is no easy way to
> compute it.

Depends on the size of the LFSR. For a typical <100-bit LFSR it should
be fairly easy.

In cryptography GF(2^k)[x] was a choice [for a while] for
Diffie-Hellman but largely ignored because you needed much larger
fields (than for GF(p)) to achieve the same level of security.

But you are right, it isn't as trivial as just some table lookup.

Tom

Thanks Vladimir , thanks Tom.

It would be at most a 12bit LFSR and I hopped that the resulting
circuitry, if achivable, would be smaller than a ROM.

Sylvain

sylvain wrote:
> Thanks Vladimir , thanks Tom.
>
> It would be at most a 12bit LFSR and I hopped that the resulting
> circuitry, if achivable, would be smaller than a ROM.
>
> Sylvain

Not quite actually. The output of a lfsr is a*(alpha)^j for the jth
secquence, where a is the seed and alpha is the primitive element. So,
you need to divide by 'a' and then take logarithm. Ofcourse if a =
000..1, then division by 1 is trivial and hence only taking log
suffices.

-rajesh