How to create an LSFR in Assembler

[BobSparky1996]

Pic 16f887

So, I am basically trying to create an 8-bit LSFR... thats my task.

I'm not sure really what they are - or how to implement them. Is anyone able to help?

- Bob

 

[Ian Rogers]

I have just used the very same to generate white noise ( random number generator..) Its basically a number XORed with a polynominal.... If you look into CRC creation, its used there..

A random number generator is shifted left and XORed with specified bits and the LSbit is set or cleared by the result!!

 

[BobSparky1996]

So I now understand what to do for this task.

How do I XOR say only the 0bit with the 4th bit, and then Xor the output with the 5th bit, and then XOR the output of that with the 6th bit... and then set that as the new 7th bit after shifting right?

I know to shift the register right I can use syntax

RRF   RandomNumber,1

But my question basically is "What is the syntax to XOR bit 0 of 'randomnumber' with bit 4 of 'randomnumber' and store it in a variable 'temp'

 

[jpanhalt]

This is definitely a first draft and crude code, because I wanted to watch every step. There are obvious ways to shorten it. As written it has a repeat cycle of 14 (i.e., the 14th loop repeats the seed). That is, if counter runs to zero, it ends up with 0xAC (seed=DA, then B5, 6B, D6, AC... all in hex). No guarantee it actually meets the definition of an LFSR as given in Wikipedia for the Fibonacci type. That is what I am playing with right now for Sunday fun. It is written for an enhanced mid-range chip (16F1829), so there are instructions not available per se, but easily adapted to your chip.

     org 0x0000
     nop
     bra  Start
Start
     clrf      counter      
     clrf      output
     movlw     0xDA           ;b'1101 1010'
     movwf     seed
Loop
     movlw     b'10101000'    ;bits <7,5,3> used to xor seed
     andwf     seed,w
     movwf     taps           ;taps has the seed's values at those bits
     lslf      seed,w         ;sets or clears STATUS,0 w/ seed <bit7>
     rrf       output,f       ;moves seed<7> value to output<7>
     movlw     b'10000000'
     andwf     taps,w
     xorwf     output,f
  
     lslf      taps,f
     lslf      taps,f
     movlw     0x80
     andwf     taps,w
     xorwf     output,f

     lslf      taps,f
     lslf      taps,f
     movlw     0x80
     andwf     taps,w
     xorwf     output,f

     lslf      output,f
     rlf       seed,f         ;move xor'd result into seed<0>
;     incf      counter,f
     incfsz    counter,f
     bra       Loop
     nop

     end

In answer to your question of how to XOR single bits sequentially (as described in Wikipedia), I used rotates to create an 8-bit byte with only bit<7> set (or clear) and xor'd that with another similarly constructed byte.

The Wiki article is interesting, but I do not understand it yet: 1) Rather than using conventional bit numbering of 0..15, it uses 1..16; and 2) Which numbering system is used to determine whether the condition for a "primitive polynomial" are met? That is, taps in the example at 16,14,13, and 11 are setwise co-prime even if one uses conventional numbering of 15,13,12,and 10. However, using Wiki's numbering, taps at 15,13,11,and 5 would be co-prime, but using conventional numbering those become 14,12,10,and 4, which are not co-prime.

If someone sees an obvious error in the code, please let us know as that code is truly just a first draft.

EDIT: There seems to be an error(s) in the algorithm. Seed #'s of 1 and 2 don't repeat, and using the taps at 8,6,5,4 it gives a repeat unit of about 34 loops instead of the expected 255.

 

[Beau Schwabe]

But my question basically is "What is the syntax to XOR bit 0 of 'randomnumber' with bit 4 of 'randomnumber' and store it in a variable 'temp'

You sort of answered your own question .... use RRF until the bits are aligned ... I would move the original random number into a temp variable and work from there.... Anyway once the bits are aligned, use a mask to AND just that bit.... i.e

Terminology CAUTION: There is an LFSR command as part of the microntroller language that could be confused with what you are asking.

    movf    randomnumber1   ,W   ; move randomnumber1 into W
    movwf   temp1                ; move W into temp1

    movf    randomnumber2   ,W   ; move randomnumber2 into W
    movwf   temp2                ; move W into temp2

    rrf     temp1           ,F   ; move bit 4 to bit 3 position
    rrf     temp1           ,F   ; move bit 3 to bit 2 position
    rrf     temp1           ,F   ; move bit 2 to bit 1 position
    rrf     temp1           ,W   ; move bit 1 to bit 0 position
  
    andlw   b'00000001'          ; Mask Bit 0 (was bit 4)
  
    xorwf   temp2          ,W    ; XOR Bit 0 (was bit 0) of temp1 with XOR Bit 0 of temp2
    andlw   b'00000001'          ; Mask Bit 0

    movwf   temp3                ; Result in temp3

 

[Pommie]

I used one of these on a project many years ago. It XORed bits 3 and 6 of the top byte of a 4 byte random seed. To do this I ANDed the number with 0x48 and then added 0x38. This left the result of the XOR in bit 6 - shift it left twice (or AND 0x40 and ADD 0xc0) leaves it in the carry bit ready to shift through the 32 bit random seed. This is looped 8 times to generate an eight bit random number. Note this must be seeded and must not be zero.

RND    movlw   8
       movwf   count
loop   movfw    Rand+3
       andlw    0x48
       addlw    0x38
       andlw    0x40
       addlw    0xc0
       rlf    Rand,f
       rlf    Rand+1,f
       rlf    Rand+2,f
       rlf    Rand+3,f
       decfsz    count,f
       goto    loop
       return

This is one of the simplest and rather good ones I know.

Mike.

 

[jpanhalt]

Pommie
That's a nice routine. I will be trying it today.

After a bit more searching, I found these two descriptions of the process:
**broken link removed**
https://www.maximintegrated.com/en/app-notes/index.mvp/id/4400

Both are quite readable. The first is a good starter and the latter (Maxim AN4400) is more in depth.

It finally dawned on me that the process can be viewed as a parity test on the result after applying a bit mask to a seed. Then rotate that result (1=odd) into the lsb of the seed and repeat. With proper selection of the bit mask (aka taps), the process will yield every value once of the maximum number of values for the seed size (e.g, 8 bit = 255). The links above give some suggested masks for seeds up to 32 bit.

 

[Pommie]

I ran the above code with 100k itterations and the distribution was almost flat but was biased towards zero and 255. Xoring the 4 bytes together returned the following flatish distribution.

Mike.
Edit, XORing the 4 bytes together seems to form a pattern. So, probably not a good thing.

 

[jpanhalt]

I believe the LSFR methods all have a repeat period. That period can be quite short up to the max. My notes are not particularly ordered from yesterday, but one, 4-bit mask I tried gave a repeat period of well less than 10. The max also must include every possible value (zero or FF... might be exceptions).

I consider myself quite weak in "bit magic," but PicList (and surely Google too) has some pretty short routines for parity testing, which is where I am headed.

John

 

[Pommie]

From the first link you posted above the max length 32 bit LSFR uses bits 1,5,6 & 31.

Here's an interesting way to XOR them all together.

    movlw    1<<C           ;mask for carry bit
    bcf    STATUS,C
    btfsc    Rand,6
    xorwf    STATUS,f
    btfsc    Rand,5
    xorwf    STATUS,f
    btfsc    Rand,1
    xorwf    STATUS,f
    btfsc    Rand+3,7
    xorwf    STATUS,f
    ; the bits are all XORed and the result is in the Carry ready for shifting.
    rlf    Rand,f
    rlf    Rand+1,f
    rlf    Rand+2,f
    rlf    Rand+3,f

You could also increment a byte and the result (of the XOR) would be bit 0 of that byte.

Mike.

 

[jpanhalt]

You could also increment a byte and the result (of the XOR) would be bit 0 of that byte.

I am not sure I understand that last comment.

1) b'xxxx 1100' incremented = b'xxxx 1101
2) b'xxxx 1110' incremented = b'xxxx 1111

XOR of the bits in 1 and 2 should be different.

John

 

[Pommie]

If you increment a byte for each bit that is set then bit zero will be the parity bit - I.E it will change for every set bit.
The above is toggling the Carry bit whenever a bit is set.

    clrf    parity
    btfsc   Rand,6
    incf    parity,f
    btfsc   Rand,5
    incf    parity,f
    btfsc   Rand,1
    incf    parity,f
    btfsc   Rand+3,7
    incf    parity,f
    //bit 0 of parity will be the result of the XOR

Mike.

 

[jpanhalt]

OK, now I misunderstood that previous sentence.

Here is a snippet of a comment by Olin Lathrop regarding an 8-bit parity test by John Payson published on PIClist.

First the high and low nibbles were XORed. Each bit in each nibble is now the parity of itself and the same bit in the other nibble. In other words, this reduces the problem to finding the parity of one of the nibbles. This value is XORed again with itself shifted right one bit. Bits 0 and 2 are now the parity of the upper and lower half of the nibbles. Bit 0 is then incremented if bit 2 is set, creating the combined parity in bit 0.

Payson's code is a little shorter when applied to a whole byte of up to 8 set bits as a result, but of course instructions must be added to extract just the "taps" from the seed for which parity is needed. Your code, of course incorporates those additional instructions as you know beforehand that the byte being examined can only have a maximum of 4 bits set and which bits to test.

Basically, I will probably never use any of this. I just love spending Sundays relaxing with games like this. Thanks for helping clear my thinking.

Regards,
John

 

[jpanhalt]

For your fun and enjoyment, here is some code that uses John Payson's 8-bit parity check. Feel free to pick any "seed". The "taps" in the code will give 255 loops (maximum). If interested, try other taps, but bit<7> should probably be included.

Start
     clrf      counter        
     movlw     0xCA          ;b'1101 1010'  
     movwf     seed
     movlw     b'10001110'
     movwf     taps          ;mask for bits 1,2,3,7
Loop
     movf      taps,w                         
     andwf     seed,w         
     movwf     temp
     swapf     temp,w  
     xorwf     temp,f          
     rrf       temp,w       
     xorwf     temp,f
     btfsc     temp,2   
     incf      temp,f   
     lsrf      temp,f
     rlf       seed,f
     incf      counter,f
;include next 3 instructions for finding period
     movlw     0xCA
     xorwf     seed,w
     btfss     STATUS,2
     bra       Loop
     bra       Start          ;max period is in count

John

 

[Pommie]

For a bit of fun I wrote the 32 bit version as mentioned in the **broken link removed** above.
Thought I'd add it here for any future readers.

The assembly implementation is fairly simple,

RND     ;xor bits 1,5,6 & 31
        movlw    8
        movwf    count
loop    movlw    0        ;use bit zero for xor
        btfsc    Rand,1
        xorlw    1        ;flip bit 0
        btfsc    Rand,5
        xorlw    1
        btfsc    Rand,6
        xorlw    1
        btfsc    Rand+3,7    ;bit 31
        xorlw    1
        addlw    0xff        ;move bit 0 to carry bit.
        rlf      Rand,f        ;rotate through 32 bits
        rlf      Rand+1,f
        rlf      Rand+2,f
        rlf      Rand+3,f
        decfsz   count,f
        goto     loop
        return

I can confirm that it eventually returns to the start state after 4,294,967,295 (2^32) iterations.

Mike.