1. Welcome to our site! Electro Tech is an online community (with over 170,000 members) who enjoy talking about and building electronic circuits, projects and gadgets. To participate you need to register. Registration is free. Click here to register now.
    Dismiss Notice

How to create an LSFR in Assembler

Discussion in 'Homework Help' started by BobSparky1996, Dec 10, 2017.

  1. BobSparky1996

    BobSparky1996 New Member

    Joined:
    Dec 9, 2017
    Messages:
    8
    Likes:
    0
    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
     
  2. Ian Rogers

    Ian Rogers User Extraordinaire Forum Supporter Most Helpful Member

    Joined:
    Mar 28, 2011
    Messages:
    9,684
    Likes:
    947
    Location:
    Rochdale UK
    ONLINE
    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!!
     
  3. BobSparky1996

    BobSparky1996 New Member

    Joined:
    Dec 9, 2017
    Messages:
    8
    Likes:
    0
    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
    Code (asm):

    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'
     
  4. dave miyares

    Dave New Member

    Joined:
    Jan 12, 1997
    Messages:
    2
    Likes:
    -10


     
  5. jpanhalt

    jpanhalt Well-Known Member Most Helpful Member

    Joined:
    Jun 21, 2006
    Messages:
    6,280
    Likes:
    554
    Location:
    Cleveland, OH, USA
    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.
    Code (asm):

         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.
     
    Last edited: Dec 10, 2017
  6. Beau Schwabe

    Beau Schwabe Member

    Joined:
    Jun 4, 2017
    Messages:
    101
    Likes:
    8
    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.

    Code (text):

        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
     

     
     
  7. Pommie

    Pommie Well-Known Member Most Helpful Member

    Joined:
    Mar 18, 2005
    Messages:
    10,568
    Likes:
    395
    Location:
    Brisbane Australia
    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.

    Code (text):

    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.
     
    Last edited: Dec 10, 2017
    • Like Like x 1
  8. dave miyares

    Dave New Member

    Joined:
    Jan 12, 1997
    Messages:
    2
    Likes:
    -10


     
  9. jpanhalt

    jpanhalt Well-Known Member Most Helpful Member

    Joined:
    Jun 21, 2006
    Messages:
    6,280
    Likes:
    554
    Location:
    Cleveland, OH, USA
    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:
    https://www.eetimes.com/document.asp?doc_id=1274550&print=yes
    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.
     
  10. Pommie

    Pommie Well-Known Member Most Helpful Member

    Joined:
    Mar 18, 2005
    Messages:
    10,568
    Likes:
    395
    Location:
    Brisbane Australia
    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.
    random.png
     
  11. jpanhalt

    jpanhalt Well-Known Member Most Helpful Member

    Joined:
    Jun 21, 2006
    Messages:
    6,280
    Likes:
    554
    Location:
    Cleveland, OH, USA
    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
     
  12. Pommie

    Pommie Well-Known Member Most Helpful Member

    Joined:
    Mar 18, 2005
    Messages:
    10,568
    Likes:
    395
    Location:
    Brisbane Australia
    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.
    Code (text):

        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.
     
  13. jpanhalt

    jpanhalt Well-Known Member Most Helpful Member

    Joined:
    Jun 21, 2006
    Messages:
    6,280
    Likes:
    554
    Location:
    Cleveland, OH, USA
    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
     
  14. Pommie

    Pommie Well-Known Member Most Helpful Member

    Joined:
    Mar 18, 2005
    Messages:
    10,568
    Likes:
    395
    Location:
    Brisbane Australia
    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.
    Code (text):

        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.
     
  15. jpanhalt

    jpanhalt Well-Known Member Most Helpful Member

    Joined:
    Jun 21, 2006
    Messages:
    6,280
    Likes:
    554
    Location:
    Cleveland, OH, USA
    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.
    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
     
  16. jpanhalt

    jpanhalt Well-Known Member Most Helpful Member

    Joined:
    Jun 21, 2006
    Messages:
    6,280
    Likes:
    554
    Location:
    Cleveland, OH, USA
    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.
    Code (asm):

    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
     
  17. Pommie

    Pommie Well-Known Member Most Helpful Member

    Joined:
    Mar 18, 2005
    Messages:
    10,568
    Likes:
    395
    Location:
    Brisbane Australia
    For a bit of fun I wrote the 32 bit version as mentioned in the article linked to by John above.
    Thought I'd add it here for any future readers.

    The assembly implementation is fairly simple,
    Code (text):

    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.
     

Share This Page