1#ifndef CONSTFILT_DISCRETIZE_HPP
2#define CONSTFILT_DISCRETIZE_HPP
4#include "vendor/consteig/consteig.hpp"
5#include "vendor/gcem_wrapper.hpp"
26template <
typename T, consteig::Size N>
struct StateSpace
28 consteig::Matrix<T, N, N> A{};
29 consteig::Matrix<T, N, 1> B{};
30 consteig::Matrix<T, 1, N> C{};
34template <
typename T, consteig::Size NB, consteig::Size NA>
35struct TransferFunction
47template <
typename T, consteig::Size N>
48constexpr consteig::Matrix<T, N, N> matrix_exp(
49 const consteig::Matrix<T, N, N> &A)
51 using Complex = consteig::Complex<T>;
52 using ComplexMat_NN = consteig::Matrix<Complex, N, N>;
53 using ComplexMat_N1 = consteig::Matrix<Complex, N, 1>;
56 const auto evals = consteig::eigenvalues(A);
57 const auto V = consteig::eigenvectors(A, evals);
60 const auto lu_V = consteig::lu(V);
62 ComplexMat_NN V_inv{};
63 for (consteig::Size col = 0; col < N; ++col)
65 ComplexMat_N1 e_col{};
66 e_col(col, 0) = Complex{
static_cast<T
>(1),
static_cast<T
>(0)};
67 auto col_vec = consteig::lu_solve(lu_V, e_col);
68 for (consteig::Size row = 0; row < N; ++row)
70 V_inv(row, col) = col_vec(row, 0);
76 ComplexMat_NN result_c{};
77 for (consteig::Size i = 0; i < N; ++i)
79 Complex exp_lambda = consteig::exp(evals(i, 0));
80 for (consteig::Size r = 0; r < N; ++r)
82 for (consteig::Size c = 0; c < N; ++c)
85 result_c(r, c) + exp_lambda * V(r, i) * V_inv(i, c);
91 consteig::Matrix<T, N, N> result{};
92 for (consteig::Size r = 0; r < N; ++r)
94 for (consteig::Size c = 0; c < N; ++c)
96 result(r, c) = result_c(r, c).real;
110template <
typename T, consteig::Size N>
111constexpr StateSpace<T, N> zoh_discretize(
const StateSpace<T, N> &sys_c, T Ts,
114 const auto &Ac = sys_c.A;
115 const auto &Bc = sys_c.B;
118 const consteig::Matrix<T, N, N> Ad = matrix_exp(Ts * Ac);
121 const consteig::Matrix<T, N, N> AdmI = Ad - consteig::eye<T, N>();
124 const consteig::Matrix<T, N, 1> rhs = AdmI * Bc;
127 const auto lu_Ac = consteig::lu(Ac);
128 const auto Bd = consteig::lu_solve(lu_Ac, rhs);
130 StateSpace<T, N> sys_d{};
145template <
typename T, consteig::Size N>
146constexpr void char_poly(
const consteig::Matrix<T, N, N> &Ad,
149 using Complex = consteig::Complex<T>;
151 const auto evals = consteig::eigenvalues(Ad);
155 p[0] = Complex{
static_cast<T
>(1),
static_cast<T
>(0)};
157 for (consteig::Size k = 0; k < N; ++k)
159 const Complex lam = evals(k, 0);
161 p[k + 1u] = Complex{
static_cast<T
>(0),
static_cast<T
>(0)} - lam * p[k];
162 for (consteig::Size i = k; i > 0u; --i)
164 p[i] = p[i] - lam * p[i - 1u];
169 for (consteig::Size i = 0; i <= N; ++i)
171 coeffs[i] = p[i].real;
181template <
typename T, consteig::Size N>
182constexpr void markov_numerator(
const StateSpace<T, N> &sys_d,
183 const T (&a_coeffs)[N + 1u], T (&b)[N + 1u])
185 const auto &Ad = sys_d.A;
186 const auto &Bd = sys_d.B;
187 const auto &Cd = sys_d.C;
194 consteig::Matrix<T, N, N> A_pow = consteig::eye<T, N>();
196 for (consteig::Size k = 1u; k <= N; ++k)
199 T val =
static_cast<T
>(0);
200 for (consteig::Size c = 0; c < N; ++c)
203 T AB_c =
static_cast<T
>(0);
204 for (consteig::Size col = 0; col < N; ++col)
206 AB_c += A_pow(c, col) * Bd(col, 0);
208 val += Cd(0, c) * AB_c;
217 for (consteig::Size k = 0; k <= N; ++k)
219 T sum =
static_cast<T
>(0);
220 for (consteig::Size jj = 0; jj <= k; ++jj)
222 sum += a_coeffs[jj] * h[k - jj];
231template <
typename T, consteig::Size N>
232constexpr TransferFunction<T, N + 1u, N + 1u> ss_to_tf(
233 const StateSpace<T, N> &sys_d)
235 TransferFunction<T, N + 1u, N + 1u> tf{};
236 char_poly(sys_d.A, tf.a);
237 markov_numerator(sys_d, tf.a, tf.b);
258template <
typename T, consteig::Size N>
259constexpr StateSpace<T, N> tf_to_ss(
const T (&b)[N + 1u],
const T (&a)[N + 1u])
261 StateSpace<T, N> sys{};
263 const T inv_a0 =
static_cast<T
>(1) / a[0];
265 sys.D = b[0] * inv_a0;
269 for (consteig::Size k = 1u; k <= N; ++k)
271 e[k] = b[k] * inv_a0 - sys.D * (a[k] * inv_a0);
275 for (consteig::Size row = 0; row < N - 1u; ++row)
277 sys.A(row, row + 1u) =
static_cast<T
>(1);
281 for (consteig::Size k = 0; k < N; ++k)
283 sys.A(N - 1u, k) = -(a[N - k] * inv_a0);
287 sys.B(N - 1u, 0) =
static_cast<T
>(1);
290 for (consteig::Size k = 0; k < N; ++k)
292 sys.C(0, k) = e[N - k];
304template <
typename T, consteig::Size N>
305constexpr TransferFunction<T, N + 1u, N + 1u> matched_z_discretize_tf(
306 const T (&b_c)[N + 1u],
const T (&a_c)[N + 1u], T Ts, MatchedZ )
308 using Complex = consteig::Complex<T>;
311 consteig::Size d_b = 0;
312 while (d_b <= N && b_c[d_b] ==
static_cast<T
>(0))
316 const consteig::Size nz = (d_b > N) ? 0u : N - d_b;
319 const T k_c = (d_b > N) ?
static_cast<T
>(0) : b_c[d_b] / a_c[0];
324 consteig::Matrix<T, N, N> A_pole{};
325 for (consteig::Size i = 0; i < N - 1u; ++i)
326 A_pole(i + 1u, i) =
static_cast<T
>(1);
327 for (consteig::Size i = 0; i < N; ++i)
328 A_pole(i, N - 1u) = -(a_c[N - i] / a_c[0]);
329 const auto p_c_evals = consteig::eigenvalues(A_pole);
332 Complex p_d_vals[N]{};
333 Complex pole_poly[N + 1u]{};
334 pole_poly[0] = Complex{
static_cast<T
>(1),
static_cast<T
>(0)};
335 for (consteig::Size k = 0; k < N; ++k)
338 consteig::exp(p_c_evals(k, 0) * Complex{Ts,
static_cast<T
>(0)});
339 const Complex zk = p_d_vals[k];
341 Complex{
static_cast<T
>(0),
static_cast<T
>(0)} - zk * pole_poly[k];
342 for (consteig::Size i = k; i > 0u; --i)
344 pole_poly[i] = pole_poly[i] - zk * pole_poly[i - 1u];
353 Complex z_c_finite[N]{};
354 Complex z_d_finite[N]{};
355 Complex zero_poly[N + 1u]{};
356 zero_poly[0] = Complex{
static_cast<T
>(1),
static_cast<T
>(0)};
360 consteig::Matrix<T, N, N> A_zero{};
361 for (consteig::Size i = 0; i + 1u < nz; ++i)
362 A_zero(i + 1u, i) =
static_cast<T
>(1);
363 for (consteig::Size i = 0; i < nz; ++i)
364 A_zero(i, nz - 1u) = -(b_c[d_b + (nz - i)] / b_c[d_b]);
365 const auto z_c_evals = consteig::eigenvalues(A_zero);
369 for (consteig::Size m = 0; m < d_b; ++m)
371 consteig::Size min_idx = 0;
372 T min_mag_sq =
static_cast<T
>(-1);
373 for (consteig::Size i = 0; i < N; ++i)
378 z_c_evals(i, 0).real * z_c_evals(i, 0).real +
379 z_c_evals(i, 0).imag * z_c_evals(i, 0).imag;
380 if (min_mag_sq <
static_cast<T
>(0) || mag_sq < min_mag_sq)
387 spurious[min_idx] =
true;
391 consteig::Size nz_cnt = 0u;
392 for (consteig::Size k = 0; k < N; ++k)
396 z_c_finite[nz_cnt] = z_c_evals(k, 0);
397 z_d_finite[nz_cnt] = consteig::exp(
398 z_c_evals(k, 0) * Complex{Ts,
static_cast<T
>(0)});
399 const Complex zk = z_d_finite[nz_cnt];
400 zero_poly[nz_cnt + 1u] =
401 Complex{
static_cast<T
>(0),
static_cast<T
>(0)} -
402 zk * zero_poly[nz_cnt];
403 for (consteig::Size i = nz_cnt; i > 0u; --i)
405 zero_poly[i] = zero_poly[i] - zk * zero_poly[i - 1u];
413 const consteig::Size n_extra = (nz + 1u < N) ? (N - nz - 1u) : 0u;
414 for (consteig::Size e = 0; e < n_extra; ++e)
416 const consteig::Size cur_deg = nz + e;
417 zero_poly[cur_deg + 1u] = zero_poly[cur_deg + 1u] + zero_poly[cur_deg];
418 for (consteig::Size i = cur_deg; i > 0u; --i)
420 zero_poly[i] = zero_poly[i] + zero_poly[i - 1u];
423 const consteig::Size num_deg = nz + n_extra;
426 const T tol = gcem::sqrt(consteig::epsilon<T>());
427 T w_c =
static_cast<T
>(0);
428 for (consteig::Size attempt = 0; attempt < 1000u; ++attempt)
430 bool collision =
false;
431 for (consteig::Size i = 0; i < N && !collision; ++i)
433 const T dr = w_c - p_c_evals(i, 0).real;
434 const T di = p_c_evals(i, 0).imag;
435 if (dr * dr + di * di < tol * tol)
440 for (consteig::Size i = 0; i < nz && !collision; ++i)
442 const T dr = w_c - z_c_finite[i].real;
443 const T di = z_c_finite[i].imag;
444 if (dr * dr + di * di < tol * tol)
453 w_c +=
static_cast<T
>(0.1) / Ts;
457 const Complex w_c_cx{w_c,
static_cast<T
>(0)};
458 const Complex w_d_cx =
459 consteig::exp(w_c_cx * Complex{Ts,
static_cast<T
>(0)});
461 Complex num_c_cx{
static_cast<T
>(1),
static_cast<T
>(0)};
462 for (consteig::Size i = 0; i < nz; ++i)
464 num_c_cx = num_c_cx * (w_c_cx - z_c_finite[i]);
467 Complex den_c_cx{
static_cast<T
>(1),
static_cast<T
>(0)};
468 for (consteig::Size i = 0; i < N; ++i)
470 den_c_cx = den_c_cx * (w_c_cx - p_c_evals(i, 0));
473 Complex num_d_cx{
static_cast<T
>(1),
static_cast<T
>(0)};
474 for (consteig::Size i = 0; i < N; ++i)
476 num_d_cx = num_d_cx * (w_d_cx - p_d_vals[i]);
479 Complex den_d_cx{
static_cast<T
>(1),
static_cast<T
>(0)};
480 for (consteig::Size i = 0; i < nz; ++i)
482 den_d_cx = den_d_cx * (w_d_cx - z_d_finite[i]);
484 for (consteig::Size e = 0; e < n_extra; ++e)
486 den_d_cx = den_d_cx *
487 (w_d_cx - Complex{
static_cast<T
>(-1),
static_cast<T
>(0)});
490 const Complex gain_num =
491 Complex{k_c,
static_cast<T
>(0)} * num_c_cx * num_d_cx;
492 const Complex gain_den = den_c_cx * den_d_cx;
493 const T gain_den_sq =
494 gain_den.real * gain_den.real + gain_den.imag * gain_den.imag;
496 (gain_num.real * gain_den.real + gain_num.imag * gain_den.imag) /
500 TransferFunction<T, N + 1u, N + 1u> tf{};
501 for (consteig::Size i = 0; i <= N; ++i)
503 tf.a[i] = pole_poly[i].real;
505 const consteig::Size pad = N - num_deg;
506 for (consteig::Size i = 0; i <= num_deg; ++i)
508 tf.b[pad + i] = k_d * zero_poly[i].real;
528template <
typename T, consteig::Size N>
529constexpr StateSpace<T, N> tustin_discretize(
const StateSpace<T, N> &sys_c,
532 const auto &Ac = sys_c.A;
533 const auto &Bc = sys_c.B;
534 const auto &Cc = sys_c.C;
536 const T alpha =
static_cast<T
>(2) / Ts;
537 const T inv_alpha =
static_cast<T
>(1) / alpha;
540 const consteig::Matrix<T, N, N> M = consteig::eye<T, N>() - inv_alpha * Ac;
541 const consteig::Matrix<T, N, N> P = consteig::eye<T, N>() + inv_alpha * Ac;
543 const auto lu_M{consteig::lu(M)};
546 consteig::Matrix<T, N, N> M_inv{};
547 for (consteig::Size col = 0; col < N; ++col)
549 consteig::Matrix<T, N, 1> e_col{};
550 e_col(col, 0) =
static_cast<T
>(1);
551 const auto col_vec{consteig::lu_solve(lu_M, e_col)};
552 for (consteig::Size row = 0; row < N; ++row)
554 M_inv(row, col) = col_vec(row, 0);
559 const consteig::Matrix<T, N, N> Ad{P * M_inv};
562 const consteig::Matrix<T, N, 1> Bd{inv_alpha *
563 (Ad + consteig::eye<T, N>()) * Bc};
566 const consteig::Matrix<T, 1, N> Cd{Cc * M_inv};
569 const T Dd{sys_c.D + inv_alpha * (Cd * Bc)(0, 0)};
571 StateSpace<T, N> sys_d{};
580template <
typename T, consteig::Size N>
581constexpr TransferFunction<T, N + 1u, N + 1u> matched_z_discretize(
582 const StateSpace<T, N> &sys_c, T Ts, MatchedZ )
585 char_poly(sys_c.A, a_c);
587 markov_numerator(sys_c, a_c, b_c);
588 return matched_z_discretize_tf<T, N>(b_c, a_c, Ts, MatchedZ{});
593template <
typename T, consteig::Size N>
594constexpr TransferFunction<T, N + 1u, N + 1u> analog_to_digital(
595 const StateSpace<T, N> &sys_c, T Ts, ZOH)
597 return ss_to_tf(zoh_discretize(sys_c, Ts, ZOH{}));
600template <
typename T, consteig::Size N>
601constexpr TransferFunction<T, N + 1u, N + 1u> analog_to_digital(
602 const StateSpace<T, N> &sys_c, T Ts, MatchedZ)
604 return matched_z_discretize(sys_c, Ts, MatchedZ{});
607template <
typename T, consteig::Size N>
608constexpr TransferFunction<T, N + 1u, N + 1u> analog_to_digital(
609 const StateSpace<T, N> &sys_c, T Ts, Tustin)
611 return ss_to_tf(tustin_discretize(sys_c, Ts, Tustin{}));
616template <
typename T, consteig::Size N>
617constexpr TransferFunction<T, N + 1u, N + 1u> analog_to_digital(
618 const T (&b_c)[N + 1u],
const T (&a_c)[N + 1u], T Ts, ZOH)
620 return ss_to_tf(zoh_discretize(tf_to_ss<T, N>(b_c, a_c), Ts, ZOH{}));
623template <
typename T, consteig::Size N>
624constexpr TransferFunction<T, N + 1u, N + 1u> analog_to_digital(
625 const T (&b_c)[N + 1u],
const T (&a_c)[N + 1u], T Ts, MatchedZ)
627 return matched_z_discretize_tf<T, N>(b_c, a_c, Ts, MatchedZ{});
630template <
typename T, consteig::Size N>
631constexpr TransferFunction<T, N + 1u, N + 1u> analog_to_digital(
632 const T (&b_c)[N + 1u],
const T (&a_c)[N + 1u], T Ts, Tustin)
634 return ss_to_tf(tustin_discretize(tf_to_ss<T, N>(b_c, a_c), Ts, Tustin{}));