Skip to main content

qualia_audio/features/spectral/
lpc.rs

1//! Linear predictive coding (LPC) via Levinson-Durbin recursion.
2
3use crate::types::AudioError;
4
5/// Maximum LPC order supported (bounds the on-stack working arrays so the hot
6/// path stays zero-heap).
7pub const MAX_LPC_ORDER: usize = 32;
8
9/// Compute `order` linear-prediction coefficients of `signal` by the
10/// Levinson-Durbin recursion, plus the associated reflection (PARCOR)
11/// coefficients.
12///
13/// The predictor models each sample as a linear combination of its `order`
14/// predecessors, `x[n] ≈ Σ_{j=1}^{order} a_j · x[n-j]`. On success `out_lpc[j]`
15/// receives the predictor coefficient `a_{j+1}` (so `out_lpc[0]` is the weight
16/// of `x[n-1]`) and `out_reflection[i]` the reflection coefficient `k_{i+1}` of
17/// stage `i+1`.
18///
19/// The biased autocorrelation is computed internally from `signal`; all
20/// recursion state lives in fixed on-stack arrays (`MAX_LPC_ORDER`), so the
21/// call performs no heap allocation.
22///
23/// Zero-heap: caller-supplied outputs; bounded on-stack scratch.
24///
25/// # Errors
26/// - [`AudioError::InvalidParameter`] if `order` is `0` or exceeds
27///   [`MAX_LPC_ORDER`], if `signal` has `<= order` samples, or if the signal
28///   carries no energy (a singular, non-invertible autocorrelation).
29/// - [`AudioError::OutputBufferTooSmall`] if `out_lpc` or `out_reflection` is
30///   shorter than `order`.
31pub fn lpc(
32    signal: &[f32],
33    order: usize,
34    out_lpc: &mut [f32],
35    out_reflection: &mut [f32],
36) -> Result<(), AudioError> {
37    if order == 0 || order > MAX_LPC_ORDER || signal.len() <= order {
38        return Err(AudioError::InvalidParameter);
39    }
40    if out_lpc.len() < order || out_reflection.len() < order {
41        return Err(AudioError::OutputBufferTooSmall);
42    }
43
44    // Biased autocorrelation r[0..=order] (f64 for conditioning).
45    let mut r = [0.0f64; MAX_LPC_ORDER + 1];
46    for (lag, rl) in r.iter_mut().enumerate().take(order + 1) {
47        let mut acc = 0.0f64;
48        for n in 0..signal.len() - lag {
49            acc += signal[n] as f64 * signal[n + lag] as f64;
50        }
51        *rl = acc;
52    }
53    if r[0] <= 0.0 {
54        return Err(AudioError::InvalidParameter);
55    }
56
57    // Levinson-Durbin: `a` holds the current predictor coefficients a[1..=i];
58    // `prev` is the copy of the previous stage used for the symmetric update.
59    let mut a = [0.0f64; MAX_LPC_ORDER + 1];
60    let mut err = r[0];
61    for i in 1..=order {
62        // Reflection coefficient k = (r[i] - Σ_{j<i} a[j]·r[i-j]) / err.
63        let mut acc = r[i];
64        for j in 1..i {
65            acc -= a[j] * r[i - j];
66        }
67        let k = acc / err;
68
69        // Symmetric coefficient update using the previous stage's values.
70        let prev = a; // [f64; N] is Copy — on-stack snapshot, no heap.
71        for j in 1..i {
72            a[j] = prev[j] - k * prev[i - j];
73        }
74        a[i] = k;
75
76        out_reflection[i - 1] = k as f32;
77        err *= 1.0 - k * k;
78        // A perfectly predictable stage drives err to 0; floor it so the
79        // recursion stays finite instead of dividing by zero.
80        if err <= 0.0 {
81            err = f64::MIN_POSITIVE;
82        }
83    }
84
85    for j in 1..=order {
86        out_lpc[j - 1] = a[j] as f32;
87    }
88    Ok(())
89}
90
91#[cfg(test)]
92mod tests {
93    use super::*;
94
95    /// Deterministic LCG in [-1, 1) for reproducible excitation.
96    struct Lcg(u64);
97    impl Lcg {
98        fn next(&mut self) -> f32 {
99            self.0 = self
100                .0
101                .wrapping_mul(6364136223846793005)
102                .wrapping_add(1442695040888963407);
103            let u = (self.0 >> 40) as f32 / (1u64 << 24) as f32; // [0,1)
104            2.0 * u - 1.0
105        }
106    }
107
108    /// Golden: an AR(2) process x[n] = a1·x[n-1] + a2·x[n-2] + e[n] driven by
109    /// white noise; order-2 LPC recovers (a1, a2) close to the true values.
110    #[test]
111    fn recovers_ar2_coefficients() {
112        let a1 = 1.2f32;
113        let a2 = -0.5f32;
114        let n = 8000usize;
115        let mut x = vec![0.0f32; n];
116        let mut rng = Lcg(0x1234_5678_9abc_def0);
117        for i in 2..n {
118            x[i] = a1 * x[i - 1] + a2 * x[i - 2] + 0.1 * rng.next();
119        }
120        // Drop the initial transient.
121        let stable = &x[200..];
122
123        let mut coeffs = [0.0f32; 2];
124        let mut refl = [0.0f32; 2];
125        lpc(stable, 2, &mut coeffs, &mut refl).expect("lpc");
126
127        assert!(
128            (coeffs[0] - a1).abs() < 0.1,
129            "a1: got {} want {a1}",
130            coeffs[0]
131        );
132        assert!(
133            (coeffs[1] - a2).abs() < 0.1,
134            "a2: got {} want {a2}",
135            coeffs[1]
136        );
137        // Reflection coefficients of a stable AR(2) have magnitude < 1.
138        assert!(refl[0].abs() < 1.0 && refl[1].abs() < 1.0, "refl={refl:?}");
139        // The second reflection coefficient equals a2 for an AR(2) model.
140        assert!((refl[1] - a2).abs() < 0.1, "k2: got {} want {a2}", refl[1]);
141    }
142
143    #[test]
144    fn order_one_matches_normalized_lag1() {
145        // For order 1, a1 = r[1]/r[0] — the lag-1 correlation coefficient.
146        let x = [1.0f32, 0.8, 0.6, 0.4, 0.2, 0.0, -0.2, -0.4];
147        let mut coeffs = [0.0f32; 1];
148        let mut refl = [0.0f32; 1];
149        lpc(&x, 1, &mut coeffs, &mut refl).expect("lpc");
150
151        let mut r0 = 0.0f64;
152        let mut r1 = 0.0f64;
153        for i in 0..x.len() {
154            r0 += x[i] as f64 * x[i] as f64;
155        }
156        for i in 0..x.len() - 1 {
157            r1 += x[i] as f64 * x[i + 1] as f64;
158        }
159        let expect = (r1 / r0) as f32;
160        assert!(
161            (coeffs[0] - expect).abs() < 1e-5,
162            "a1={} want {expect}",
163            coeffs[0]
164        );
165        assert!((refl[0] - expect).abs() < 1e-5, "k1={}", refl[0]);
166    }
167
168    #[test]
169    fn rejects_bad_order() {
170        let x = [1.0f32, 2.0, 3.0, 4.0];
171        let mut coeffs = [0.0f32; 4];
172        let mut refl = [0.0f32; 4];
173        assert_eq!(
174            lpc(&x, 0, &mut coeffs, &mut refl),
175            Err(AudioError::InvalidParameter)
176        );
177        // order >= signal length.
178        assert_eq!(
179            lpc(&x, 4, &mut coeffs, &mut refl),
180            Err(AudioError::InvalidParameter)
181        );
182        // order > MAX_LPC_ORDER.
183        let big = vec![0.1f32; 128];
184        let mut c = [0.0f32; MAX_LPC_ORDER + 1];
185        let mut rf = [0.0f32; MAX_LPC_ORDER + 1];
186        assert_eq!(
187            lpc(&big, MAX_LPC_ORDER + 1, &mut c, &mut rf),
188            Err(AudioError::InvalidParameter)
189        );
190    }
191
192    #[test]
193    fn rejects_silence() {
194        let x = [0.0f32; 16];
195        let mut coeffs = [0.0f32; 2];
196        let mut refl = [0.0f32; 2];
197        assert_eq!(
198            lpc(&x, 2, &mut coeffs, &mut refl),
199            Err(AudioError::InvalidParameter)
200        );
201    }
202
203    #[test]
204    fn rejects_small_output() {
205        let x = [1.0f32, 2.0, 3.0, 4.0, 5.0];
206        let mut coeffs = [0.0f32; 1];
207        let mut refl = [0.0f32; 4];
208        assert_eq!(
209            lpc(&x, 2, &mut coeffs, &mut refl),
210            Err(AudioError::OutputBufferTooSmall)
211        );
212    }
213}