77 lines
2.3 KiB
Go
77 lines
2.3 KiB
Go
package audio
|
|
|
|
import (
|
|
"math"
|
|
"math/cmplx"
|
|
)
|
|
|
|
// fft выполняет БПФ по основанию 2 in-place (Кули-Тьюки, прореживание
|
|
// по времени). len(x) должна быть степенью двойки — вызывающий код
|
|
// (Spectrogram) сам округляет размер окна до ближайшей степени двойки.
|
|
//
|
|
// Классический учебный алгоритм: сначала битовая реверсия элементов
|
|
// (переставляет их в порядок, в котором рекурсивный Кули-Тьюки строил
|
|
// бы их снизу вверх, но без рекурсии и лишних аллокаций), затем
|
|
// итеративные "бабочки" по возрастающим длинам блоков (2, 4, 8, ..., n).
|
|
func fft(x []complex128) {
|
|
n := len(x)
|
|
if n <= 1 {
|
|
return
|
|
}
|
|
|
|
for i, j := 1, 0; i < n; i++ {
|
|
bit := n >> 1
|
|
for ; j&bit != 0; bit >>= 1 {
|
|
j ^= bit
|
|
}
|
|
j ^= bit
|
|
if i < j {
|
|
x[i], x[j] = x[j], x[i]
|
|
}
|
|
}
|
|
|
|
for length := 2; length <= n; length <<= 1 {
|
|
angle := -2 * math.Pi / float64(length)
|
|
wlen := cmplx.Exp(complex(0, angle))
|
|
for i := 0; i < n; i += length {
|
|
w := complex(1.0, 0.0)
|
|
half := length / 2
|
|
for j := 0; j < half; j++ {
|
|
u := x[i+j]
|
|
v := x[i+j+half] * w
|
|
x[i+j] = u + v
|
|
x[i+j+half] = u - v
|
|
w *= wlen
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
// hannWindow — стандартное окно Ханна: сглаживает края каждого
|
|
// STFT-окна перед БПФ, снижая "утечку спектра" (артефакты от резкого
|
|
// обрыва сигнала на границе окна, которые иначе размазывают чёткие
|
|
// частотные линии в шум).
|
|
func hannWindow(n int) []float64 {
|
|
w := make([]float64, n)
|
|
if n == 1 {
|
|
w[0] = 1
|
|
return w
|
|
}
|
|
for i := 0; i < n; i++ {
|
|
w[i] = 0.5 * (1 - math.Cos(2*math.Pi*float64(i)/float64(n-1)))
|
|
}
|
|
return w
|
|
}
|
|
|
|
// nextPowerOfTwo округляет вверх до ближайшей степени двойки — БПФ
|
|
// в этой реализации требует именно такой размер.
|
|
func nextPowerOfTwo(n int) int {
|
|
if n < 1 {
|
|
return 1
|
|
}
|
|
p := 1
|
|
for p < n {
|
|
p <<= 1
|
|
}
|
|
return p
|
|
}
|