Analysis of a 4-Bit Feedback Shift Register f(x₁, x₂, x₃, x₄) = 1 ⊕ x₂(x₁ ∨ x₄)

Article

Abstract

We study a 4-bit feedback shift register (FSR) whose Boolean feedback function is f(x₁, x₂, x₃, x₄) = 1 ⊕ x₂(x₁ ∨ x₄). We enumerate transitions from all 16 initial states, determine singularity, identify cycles, compute the ultimate output periodicity, and derive the Algebraic Normal Form (ANF) of the feedback function. The FSR is shown to be singular, possessing a unique 3-cycle that acts as a global attractor for all states. Through algebraic analysis, we determine that the feedback function has an algebraic degree of 3, which provides high non-linearity but fails to overcome the structural weakness of the state-transition bijectivity collapse. Furthermore, we analyze the hardware implementation complexity and the topological structure of the transient trees. A Python program is provided that reproduces the full state enumeration algorithmically and presents results in compact tables. All 16 states are shown to converge to the single cycle (0110 → 1011 → 1101 → 0110), yielding a maximal period of 3. These findings have direct relevance to the cryptanalysis of stream ciphers based on non-linear feedback shift registers (NLFSRs).