(16C) Linear Feedback Shift Registers

[badacktor]

I recently picked up an HP-16C and decided to try writing some linear feedback shift registers for it. wasn't feeling too ambitious, so I just replicated the two that had diagrams on wikipedia. https://en.wikipedia.org/wiki/Linear-fee...t_register

(16 bit unsigned mode, displaying leading 0s. the status screen should read 0 - 16 - 1000 or something. be sure to preload the index register with the value of however many times you want things to loop, and the X register with a seed that can be anything except all 0s.)

Code:

 Bit Extraction Subroutine 
──────────────────┬──────────────────
                  │
 001 - 43. 22. b  │ [g][LBL] B
                  │
 002 -         26 │ [BIN]
                  │
 003 -     42  6  │ [f][B?]
                  │
 004 -         1  │  1
                  │
 005 -         0  │  0
                  │
 006 -     42  b  │ [f][SR]
                  │
 007 -         23 │ [HEX]
                  │
 008 -     43  21 │ [g][RTN]
                  │

 Linear Feedback Shift Register #1 (Fibonacci)
──────────────────┬────────────────────────────
                  │
 009 - 43. 22. E  │ [g][LBL] E
                  │
 010 -         23 │ [HEX]
                  │
 011 -     44  4  │ [STO] 4
                  │
 012 -         F  │  F
                  │
 013 -     21  b  │ [GSB] B
                  │
 014 -     44  5  │ [STO] 5
                  │
 015 -     45  4  │ [RCL] 4
                  │
 016 -         d  │  D
                  │
 017 -     21  b  │ [GSB] B
                  │
 018 -     45  5  │ [RCL] 5
                  │
 019 -     42  10 │ [f][XOR]
                  │
 020 -     44  5  │ [STO] 5
                  │
 021 -     45  4  │ [RCL] 4
                  │
 022 -         C  │  C
                  │
 023 -     21  b  │ [GSB] B
                  │
 024 -     45  5  │ [RCL] 5
                  │
 025 -     42  10 │ [f][XOR]
                  │
 026 -     44  5  │ [STO] 5
                  │
 027 -     45  4  │ [RCL] 4
                  │
 028 -         A  │  A
                  │
 029 -     21  b  │ [GSB] B
                  │
 030 -     45  5  │ [RCL] 5
                  │
 031 -     42  10 │ [f][XOR]
                  │
 032 -     45  4  │ [RCL] 4
                  │
 033 -     42  A  │ [f][SL]
                  │
 034 -         40 │ [+]
                  │
 035 -     42  26 │ [f] SHOW [BIN]
                  │
 036 -     43  34 │ [g][PSE]
                  │
 037 -     43  23 │ [g][DSZ]
                  │
 038 -     22  E  │ [GTO] E
                  │
 039 -         31 │ [R/S]
                  │

 Linear Feedback Shift Register #2 (Galois)
──────────────────┬─────────────────────────
                  │
 040 - 43. 22. F  │ [g][LBL] F
                  │
 041 -         23 │ [HEX]
                  │
 042 -     44  4  │ [STO] 4
                  │
 043 -     42  d  │ [f][RR]
                  │
 044 -     44  6  │ [STO] 6
                  │
 045 -     45  4  │ [RCL] 4
                  │
 046 -         0  │  0
                  │
 047 -     21  b  │ [GSB] B
                  │
 048 -     44  7  │ [STO] 7
                  │
 049 -     45  4  │ [RCL] 4
                  │
 050 -         b  │  B
                  │
 051 -     21  b  │ [GSB] B
                  │
 052 -     45  7  │ [RCL] 7
                  │
 053 -     43  49 │ [g][x=y]
                  │
 054 -     22  0  │ [GTO] 0
                  │
 055 -     21  1  │ [GTO] 1
                  │
 056 - 43. 22. 0  │ [g][LBL] 0
                  │
 057 -     45  6  │ [RCL] 6
                  │
 058 -         A  │  A
                  │
 059 -     42  5  │ [f][CB]
                  │
 060 -     22  2  │ [GTO] 2
                  │
 061 - 43. 22. 1  │ [g][LBL] 1
                  │
 062 -     45  6  │ [RCL] 6
                  │
 063 -         A  │  A
                  │
 064 -     42  4  │ [f][SB]
                  │
 065 -     22  2  │ [GTO] 2
                  │
 066 - 43. 22. 2  │ [g][LBL] 2
                  │
 067 -     44  6  │ [STO] 6
                  │
 068 -     45  4  │ [RCL] 4
                  │
 069 -         d  │  D
                  │
 070 -     21  b  │ [GSB] B
                  │
 071 -     45  7  │ [RCL] 7
                  │
 072 -     43  49 │ [g][x=y]
                  │
 073 -     22  0  │ [GTO] 0
                  │
 074 -     22  1  │ [GTO] 1
                  │
 075 - 43. 22. 0  │ [g][LBL] 0
                  │
 076 -     45  6  │ [RCL] 6
                  │
 077 -         C  │  C
                  │
 078 -     42  5  │ [f][CB]
                  │
 079 -     22  2  │ [GTO] 2
                  │
 080 - 43. 22. 1  │ [g][LBL] 1
                  │
 081 -     45  6  │ [RCL] 6
                  │
 082 -         C  │  C
                  │
 083 -     42  4  │ [f][SB]
                  │
 084 -     22  2  │ [GTO] 2
                  │
 085 - 43. 22. 2  │ [g][LBL] 2
                  │
 086 -     44  6  │ [STO] 6
                  │
 087 -     45  4  │ [RCL] 4
                  │
 088 -         E  │  E
                  │
 089 -     21  b  │ [GSB] B
                  │
 090 -     45  7  │ [RCL] 7
                  │
 091 -     43  49 │ [g][x=y]
                  │
 092 -     22  0  │ [GTO] 0
                  │
 093 -     22  1  │ [GTO] 1
                  │
 094 - 43. 22. 0  │ [g][LBL] 0
                  │
 095 -     45  6  │ [RCL] 6
                  │
 096 -         d  │  D
                  │
 097 -     42  5  │ [f][CB]
                  │
 098 -     22  2  │ [GTO] 2
                  │
 099 - 43. 22. 1  │ [g][LBL] 1
                  │
 100 -     45  6  │ [RCL] 6
                  │
 101 -         d  │  D
                  │
 102 -     42  4  │ [f][SB]
                  │
 103 -     22  2  │ [GTO] 2
                  │
 104 - 43. 22. 2  │ [g][LBL] 2
                  │
 105 -     43  34 │ [g][PSE]
                  │
 106 -     43  23 │ [g][DSZ]
                  │
 107 -     22  F  │ [GTO] F
                  │
 108 -         31 │ [R/S]
                  │

additionally, I was talking to a friend who's got some computer science background but doesn't mess with old HP calculators a lot, and they asked if I could write an explanation for "us dirty scrubs" and I was like, oh heck, yeah!

two months later, I've got ~50 page long pdf explaining the fundamentals of computer science and RPN calculators all in service of sharing some LFSRs I wrote for the 16C. which is bananas. but it's written so that just about anyone with zero background could understand it. I'm hoping it's got enough of a light/goofy tone that it's worth reading.

I'll share it here, and if y'all got any suggestions on what I could do with it, where to send it or post it, or something, I'd appreciate that immensely! also if you see any typos. I've tried so hard to crush 'em all.

https://drive.google.com/file/d/1dDYeiRl...sp=sharing

anyway, I hope my little linear feedback shift registers are fun to play with! be well!

[Gamo]

Very nice article about the HP Voyager Series that focus on the HP-16C

You're right that not many information or interest in this HP-16C stuff.


Gamo

[cdmackay]

ah some nice bedtime reading, thank you very much indeed

[badacktor]

squashed one more typo. the google drive link is the better copy now. whoopsie.

[badacktor]

okay so pwarden42 in the mirror post I posted on the swissmicros forums had some super cool ideas for better "get bit" subroutines, right? and like...here, I'll let him explain:

pwarden42 Wrote:For the "get bit" routine I would probably use masking instead of branching, something like:
[g][LBL] B
[RRn]
1
[f][AND]
[RTN]

If you really wanted to use branching, you could use the carry flag:
[g][LBL] B
[g][CF] 4
[f][B?]
[g][SF] 4
0
[g][RLC]
[RTN]

I got *really* excited about these. so excited I wrote 8 more stupid freaking pages in that big pdf thing. it's honestly a small book now. I have no idea what to do with it. whatever. if you're looking for the new addendum, it starts on page 63.

[wynen]

Here is a programm for an LFSR of any length (up to 64 bits) and any structure, such as this one for example.

   

The n XOR gates form an adder for n+1 1-bit numbers without carry. This means that the output of the last gate is 1 if the number of ones at the inputs is odd.

This leads to a very simple programm.

The WSIZE is set to the length of the shift register (in the example 8).
The "polynomial" is stored in register 0 (in the example 10111000 binary).
The value of the shift register is in register 1 (initial value not equal to zero).

A step in the shift register is thus calculated as follows:

Code:


45,1        RCL 1       Initial value of the shift register
45,0        RCL 0       
42,20       f AND       Input of the XOR registers
43,7        g #B        Number of bits set
42,B        f SR        If the number is odd, set the carry flag
45,1        RCL 1       
43,C        g RLC       Shift one bit left and set Bit 0 by the carry bit
44,1        STO 1       Store the new value of the shift register

For such problems, the HP-16C is exactly the right calculator.
Thank you for the inspiring thread and the stimulating article.

Hartmut