Skip to main content

autocorrelation

Function autocorrelation 

Source
pub fn autocorrelation(truth: &[bool]) -> Option<Vec<i64>>
Expand description

The autocorrelation spectrum of a Boolean function: r_f(a) = Σ_x (−1)^{f(x) ⊕ f(x⊕a)}, the correlation of f with its shift by a. Computed by Wiener–Khinchin — the Walsh transform of the squared Walsh spectrum, scaled by 2ⁿ — so it costs one extra butterfly over walsh_spectrum. r_f(0) = 2ⁿ always; |r_f(a)| = 2ⁿ exactly when the derivative f(x⊕a) ⊕ f(x) is CONSTANT — i.e. a is a linear structure. None for a malformed table.