fork download
copy 
  1. from dataclasses import dataclass
  2. from typing import List, Optional, Callable
  3.  
  4. def int_to_bits(x: int, n: int) -> List[int]:
  5.     return [(x >> (n-1-i)) & 1 for i in range(n)]
  6.  
  7. def xor_all(values: List[int]) -> int:
  8.     s = 0
  9.     for v in values:
  10.         s ^= (v & 1)
  11.     return s
  12.  
  13. @dataclass
  14. class LFSR:
  15.     n: int
  16.     taps: List[int]
  17.     state: List[int]
  18.     def step(self) -> int:
  19.         fb = 0
  20.         for d in self.taps:
  21.             fb ^= self.state[self.n - 1 - d]
  22.         out_bit = self.state[-1]
  23.         self.state = [fb] + self.state[:-1]
  24.         return out_bit
  25.     def generate(self, length: int) -> List[int]:
  26.         return [self.step() for _ in range(length)]
  27.  
  28. @dataclass
  29. class NFSR:
  30.     n: int
  31.     feedback_fn: Callable[[List[int]], int]
  32.     feedforward_fn: Optional[Callable[[List[int]], int]] = None
  33.     state: List[int] = None
  34.     def step(self) -> int:
  35.         new_bit = self.feedback_fn(self.state)
  36.         out_bit = self.feedforward_fn(self.state) if self.feedforward_fn else self.state[-1]
  37.         self.state = [new_bit] + self.state[:-1]
  38.         return out_bit
  39.     def generate(self, length: int) -> List[int]:
  40.         return [self.step() for _ in range(length)]
  41.  
  42. # lfsr_min.py  — LFSR for p(x)=x^7 + x^4 + x^2 + 1 (reducible)
  43. # Fibonacci, right-shift; state = [s6..s0], taps at degrees {4,2,0}
  44.  
  45. def int_to_bits(x, n):
  46.     return [(x >> (n-1-i)) & 1 for i in range(n)]
  47.  
  48. class LFSR:
  49.     def __init__(self, n, taps_degrees, seed_bits):
  50.         self.n = n
  51.         self.taps = taps_degrees[:]        # degrees (0..n-1)
  52.         self.state = seed_bits[:]          # [s6..s0]
  53.  
  54.     def step(self):
  55.         # feedback = XOR of degrees d => index = n-1-d
  56.         fb = 0
  57.         for d in self.taps:
  58.             fb ^= self.state[self.n-1-d]
  59.         out_bit = self.state[-1]           # old LSB
  60.         self.state = [fb] + self.state[:-1]  # right shift
  61.         return out_bit
  62.  
  63.     def period(self, limit_mult=4):
  64.         start = self.state[:]
  65.         limit = (1 << self.n) * limit_mult
  66.         steps = 0
  67.         while steps < limit:
  68.             self.step()
  69.             steps += 1
  70.             if self.state == start:
  71.                 return steps
  72.         return -1
  73.  
  74. if __name__ == "__main__":
  75.     n = 7
  76.     taps = [4, 2, 0]               # x^7 + x^4 + x^2 + 1
  77.     seed_int = 0x5A                # example non-zero seed = 90 = 0b1011010
  78.     seed = int_to_bits(seed_int, n)
  79.  
  80.     l = LFSR(n, taps, seed[:])
  81.     per = l.period()
  82.     # regenerate one full cycle to show sequence
  83.     l = LFSR(n, taps, seed[:])
  84.     seq = [l.step() for _ in range(per if per > 0 else 64)]
  85.  
  86.     print(f"Polynomial: x^{n} + x^4 + x^2 + 1 (reducible)")
  87.     print(f"n = {n}, seed = 0x{seed_int:X} -> {''.join(map(str, seed))}")
  88.     print(f"Measured period: {per} (expected ~63 for non-zero seeds)")
  89.     print("First 32 bits:", ''.join(map(str, seq[:32])))
  90.  
  91.  
Success #stdin #stdout 0.38s 19240KB
comments (?)
stdin
copy 
45
stdout
copy 
Polynomial: x^7 + x^4 + x^2 + 1 (reducible)
n = 7, seed = 0x5A -> 1011010
Measured period: 63 (expected ~63 for non-zero seeds)
First 32 bits: 01011011000011111001000110011100
https://ideone.com/BfVi8s
language:
Python 3 (python  3.12)
created:
8 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!