Skip to main content

maximal_order_complexity

Function maximal_order_complexity 

Source
pub fn maximal_order_complexity(bits: &[bool]) -> usize
Expand description

The maximal order complexity (Jansen) of a bit sequence: the length of the shortest feedback shift register — linear OR nonlinear — that generates it, i.e. the smallest L such that every length-L window has a unique successor (s[i] = f(s[i-1],…,s[i-L]) for some feedback function f). It is the TOP of the FSR complexity hierarchy — MOC ≤ 2-adic complexity and MOC ≤ linear complexity — so it catches nonlinear generators (NFSRs, algebraic combiners with memory) that fool both Berlekamp–Massey and the 2-adic Rational Approximation. Low relative to n ⇒ a short-register generator; ≈ n/2 for a random sequence. Consistency is monotone in L, so we binary-search it.