Post Reply 
(16C) Linear Feedback Shift Registers
06-14-2021, 06:13 PM (This post was last modified: 07-02-2021 06:26 AM by badacktor.)
Post: #1
(16C) Linear Feedback Shift Registers
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!
Find all posts by this user
Quote this message in a reply
06-15-2021, 09:59 AM (This post was last modified: 06-15-2021 10:03 AM by Gamo.)
Post: #2
RE: (16C) Linear Feedback Shift Registers
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
Find all posts by this user
Quote this message in a reply
06-15-2021, 10:48 PM
Post: #3
RE: (16C) Linear Feedback Shift Registers
ah some nice bedtime reading, thank you very much indeed Smile

Cambridge, UK
41CL/DM41X 12/15C/16C DM15/16 17B/II/II+ 28S 42S/DM42 32SII 48GX 50g 35s WP34S PrimeG2 WP43S/pilot
Casio, Rockwell 18R
Find all posts by this user
Quote this message in a reply
06-16-2021, 06:14 PM
Post: #4
RE: (16C) Linear Feedback Shift Registers
squashed one more typo. the google drive link is the better copy now. whoopsie.
Find all posts by this user
Quote this message in a reply
07-02-2021, 06:30 AM
Post: #5
RE: (16C) Linear Feedback Shift Registers
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.


Attached File(s)
.pdf  HP16C_LFSR_plus.pdf (Size: 193.83 KB / Downloads: 13)
Find all posts by this user
Quote this message in a reply
11-01-2021, 06:49 PM
Post: #6
RE: (16C) Linear Feedback Shift Registers
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
Find all posts by this user
Quote this message in a reply
Post Reply 




User(s) browsing this thread: 1 Guest(s)