OXYGENHUB
◆ main openmsx / src / unittest / autocorrelation_test.cc
5.6 KiB · C++ · last changed chore(): initial commit 1 month ago source blame history raw
e8555c89 Andy McCall 1 
#include "catch.hpp"
2 
#include "utils/autocorrelation.hh"
3
4 
#include <algorithm>
5 
#include <cmath>
6 
#include <cstddef>
7 
#include <cstdlib>
8 
#include <numbers>
9 
#include <span>
10 
#include <vector>
11
12 
// Reference implementation (O(N²), but always correct)
13 
static std::vector<float> autocorrReference(const std::vector<float>& signal)
14 
{
15 
	const size_t N = signal.size();
16 
	std::vector<float> result(N);
17
18 
	for (size_t lag = 0; lag < N; ++lag) {
19 
		float sum = 0.0f;
20 
		for (size_t i = 0; i < N - lag; ++i) {
21 
			sum += signal[i] * signal[i + lag];
22 
		}
23 
		result[lag] = sum;
24 
	}
25
26 
	return result;
27 
}
28
29 
// Helper: compute max error between two arrays
30 
static float maxError(const std::vector<float>& a, const std::vector<float>& b)
31 
{
32 
	assert(a.size() == b.size());
33 
	float maxErr = 0.0f;
34 
	for (size_t i = 0; i < a.size(); ++i) {
35 
		maxErr = std::max(maxErr, std::abs(a[i] - b[i]));
36 
	}
37 
	return maxErr;
38 
}
39
40 
TEST_CASE("autocorrelation: zero signal")
41 
{
42 
	constexpr unsigned SIGNAL_L2 = 4;
43 
	constexpr unsigned N = 1 << SIGNAL_L2;
44
45 
	std::vector<float> signal(N, 0.0f); // All zeros
46
47 
	std::vector<float> autocorr(N);
48 
	autocorrelation<SIGNAL_L2>(std::span(signal), std::span(autocorr));
49 
	auto reference = autocorrReference(signal);
50
51 
	// Autocorrelation of all zeros should be all zeros
52 
	for (unsigned i = 0; i < N; ++i) {
53 
		CHECK(std::abs(autocorr[i]) < 1e-5f);
54 
	}
55
56 
	// Verify against reference implementation
57 
	float error = maxError(autocorr, reference);
58 
	CHECK(error < 1e-5f);
59 
}
60
61 
TEST_CASE("autocorrelation: impulse signal")
62 
{
63 
	constexpr unsigned SIGNAL_L2 = 4;
64 
	constexpr unsigned N = 1 << SIGNAL_L2;
65
66 
	std::vector<float> signal(N, 0.0f);
67 
	signal[0] = 1.0f; // Impulse
68
69 
	std::vector<float> autocorr(N);
70 
	autocorrelation<SIGNAL_L2>(std::span(signal), std::span(autocorr));
71 
	auto reference = autocorrReference(signal);
72
73 
	// Verify impulse response: autocorr[0] = 1, all others = 0
74 
	CHECK(std::abs(autocorr[0] - 1.0f) < 1e-4f);
75 
	for (unsigned i = 1; i < N; ++i) {
76 
		CHECK(std::abs(autocorr[i]) < 1e-4f);
77 
	}
78
79 
	// Verify against reference implementation
80 
	float error = maxError(autocorr, reference);
81 
	CHECK(error < 1e-4f);
82 
}
83
84 
TEST_CASE("autocorrelation: constant signal")
85 
{
86 
	constexpr unsigned SIGNAL_L2 = 4;
87 
	constexpr unsigned N = 1 << SIGNAL_L2;
88
89 
	std::vector<float> signal(N, 2.0f); // All values = 2.0
90
91 
	std::vector<float> autocorr(N);
92 
	autocorrelation<SIGNAL_L2>(std::span(signal), std::span(autocorr));
93 
	auto reference = autocorrReference(signal);
94
95 
	// For constant signal, autocorr[τ] = (N-τ) * value²
96 
	constexpr float value = 2.0f;
97 
	for (unsigned tau = 0; tau < N; ++tau) {
98 
		float expected = (N - tau) * value * value;
99 
		CHECK(std::abs(autocorr[tau] - expected) < 1e-3f);
100 
	}
101
102 
	// Verify against reference implementation
103 
	float error = maxError(autocorr, reference);
104 
	CHECK(error < 1e-3f); // Slightly higher tolerance for larger values
105 
}
106
107 
TEST_CASE("autocorrelation: sine wave")
108 
{
109 
	constexpr unsigned SIGNAL_L2 = 6;
110 
	constexpr unsigned N = 1 << SIGNAL_L2;
111 
	constexpr float freq = 5.0f; // 5 complete cycles
112
113 
	std::vector<float> signal(N);
114 
	for (unsigned i = 0; i < N; ++i) {
115 
		signal[i] = std::sin(2.0f * std::numbers::pi_v<float> * freq * i / N);
116 
	}
117
118 
	std::vector<float> autocorr(N);
119 
	autocorrelation<SIGNAL_L2>(std::span(signal), std::span(autocorr));
120 
	auto reference = autocorrReference(signal);
121
122 
	// Verify autocorr[0] is maximum
123 
	for (unsigned i = 1; i < N; ++i) {
124 
		CHECK(autocorr[i] <= autocorr[0] + 1e-4f); // Allow small numerical error
125 
	}
126
127 
	// Verify against reference implementation
128 
	float error = maxError(autocorr, reference);
129 
	CHECK(error < 1e-3f);
130 
}
131
132 
TEST_CASE("autocorrelation: random signal")
133 
{
134 
	constexpr unsigned SIGNAL_L2 = 5;
135 
	constexpr unsigned N = 1 << SIGNAL_L2;
136
137 
	// Use fixed seed for deterministic results
138 
	srand(42);
139 
	std::vector<float> signal(N);
140 
	for (unsigned i = 0; i < N; ++i) {
141 
		signal[i] = static_cast<float>(rand()) / RAND_MAX - 0.5f;
142 
	}
143
144 
	std::vector<float> autocorr(N);
145 
	autocorrelation<SIGNAL_L2>(std::span(signal), std::span(autocorr));
146 
	auto reference = autocorrReference(signal);
147
148 
	// Verify autocorr[0] is maximum
149 
	for (unsigned i = 1; i < N; ++i) {
150 
		CHECK(autocorr[i] <= autocorr[0] + 1e-4f);
151 
	}
152
153 
	// Verify against reference implementation
154 
	float error = maxError(autocorr, reference);
155 
	CHECK(error < 1e-3f);
156 
}
157
158 
TEST_CASE("autocorrelation: non-power-of-2 signal length")
159 
{
160 
	constexpr unsigned SIGNAL_L2 = 5;
161 
	constexpr unsigned N = 20;  // Not a power of 2 (SIGNAL_LEN = 32, but we only use 20)
162
163 
	std::vector<float> signal(N);
164 
	for (unsigned i = 0; i < N; ++i) {
165 
		signal[i] = static_cast<float>(i + 1) * 0.1f;  // Simple increasing sequence
166 
	}
167
168 
	std::vector<float> autocorr(N);
169 
	autocorrelation<SIGNAL_L2>(std::span(signal), std::span(autocorr));
170 
	auto reference = autocorrReference(signal);
171
172 
	// Verify autocorr[0] is maximum
173 
	for (unsigned i = 1; i < N; ++i) {
174 
		CHECK(autocorr[i] <= autocorr[0] + 1e-4f);
175 
	}
176
177 
	// Verify against reference implementation
178 
	float error = maxError(autocorr, reference);
179 
	CHECK(error < 1e-3f);
180 
}
181
182 
TEST_CASE("autocorrelation: normalization")
183 
{
184 
	constexpr unsigned SIGNAL_L2 = 4;
185 
	constexpr unsigned N = 1 << SIGNAL_L2;
186
187 
	std::vector<float> signal(N);
188 
	for (unsigned i = 0; i < N; ++i) {
189 
		signal[i] = static_cast<float>(i + 1) * 0.1f;
190 
	}
191
192 
	std::vector<float> autocorrNormalized(N);
193 
	std::vector<float> autocorrUnnormalized(N);
194
195 
	// Test with normalization (default)
196 
	autocorrelation<SIGNAL_L2, true>(std::span(signal), std::span(autocorrNormalized));
197
198 
	// Test without normalization
199 
	autocorrelation<SIGNAL_L2, false>(std::span(signal), std::span(autocorrUnnormalized));
200
201 
	// Unnormalized should be FFT_LEN times larger
202 
	constexpr unsigned FFT_LEN = 2 * (1 << SIGNAL_L2);
203 
	for (unsigned i = 0; i < N; ++i) {
204 
		float expected = autocorrUnnormalized[i] / FFT_LEN;
205 
		CHECK(std::abs(autocorrNormalized[i] - expected) < 1e-5f);
206 
	}
207 
}