컴퓨터 알고리즘 중간고사 과제 (Fast Fourier Transform 알고리즘)
FFT 고속 푸리에 변환이란?
FFT는 푸리에 변환을 통해 이산적인 형태의 데이터들이 있을 때 이 데이터들을 벡터로 나타낸 후
각 데이터 point들이 어떠한 진동수로 되어있는지 쪼개고 같은 진동수끼리 더하여 전체 데이터가 어떠한
진동수를 가지고 있는지 푸리에 도메인에서 나타내는 방법이다.(시간 도메인 > 주파수 도메인)
이 개념을 이해하기 위해서 이산 푸리에 변환(Discrete Fourier Transform), DFT 라는 알고리즘의
개념에 대해서 알아야 한다. 그 이유는 FFT는 DFT를 더 효율적으로 계산하는 방법이다.
출처:https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=lecroykorea&logNo=130182273773
위의 사진은 300-Khz 구형파의 fft이다. fft이론에서는 무한히 연속된 시간 도메인 신호가 모두 주파수 도메인 스펙트럼으로 변환되는 것을
가정으로 하고 있지만, 실제 fft에서는 불가능한 일이다. 따라서 이러한 이론과 현실의 차이를 구분하기 위해 신호의 주기성과 대칭성을 이용하여
신호의 특정부분을 선택해 같은 신호가 무한히 반복된다고 생각하여 fft를 연산하게 된다.
DFT 이산 푸리에 변환
DFT는 간단하게 시간 도메인의 이산 신호를 주파수 도메인으로 변환하는 작업을 수행하는데,
서로 다른 N개의 복소수값이 주어질 때, 어떤 원칙에 의해 이 값들을 각각 N개의 다른 복소수값으로 변환하는 과정이다.
DFT는 공학,과학 및 신호처리와 관련된 많은 분야에서 사용되고 있지만, 계산 복잡도가 O(N^2)로, 큰 데이터들에 대해 비효율이다.
FFT 알고리즘의 간단한 원리(쿨리-튜키 알고리즘)
FFT는 기본적으로 DFT을 계산할 때 중복되는 계산을 줄이고 더 효울적인 방법을 찾는 것이다.
이 방법을 통해 DFT의 계산 복잡도인 O(N^2)를 O(N*logN)으로 줄이게 된다.
FFT의 알고리즘 중에서 가장 대표적인 것은 쿨리-튜키 알고리즘이다. 쿨리-튜키 알고리즘은
분할정복 전략을 사용하여 입력데이터를 작은 부분으로 나누어 문제를 간소화 시킨다.
쿨리-튜키 알고리즘의 원리는 다음과 같다.
- 분할: 입력 데이터를 작은 문제로 나눈다
- 정복: 나누어진 작은 문제를 해결한다. 각 하위 배열에 대해서 재귀적으로 FFT를 수행한다.
- 결합: 나누어진 작은 문제의 해결 결합하여 원래 문제의 해를 구한다. **이 과정에서 홀수 인덱스와 짝수 인덱스 배열의 결과를 결합하여 최종 DFT 출력을 얻는다.
이러한 과정을 통해 FFT 알고리즘은 계산 시간을 크게 단축 시키게 된다.쿨리-튜키 알고리즘을 이해하기 위한 예와 구현
위에서 설명한 원리 순서에 따라 예를 들어 설명을 해보자
x(n) = [1, 2, 3, 4] (시간 도메인의 이산신호) - 분할:
x_even(n) = [1, 3]
x_odd(n) = [2, 4] // 짝수 인덱스와 홀수 인덱스로 데이터를 분할함 - 정복:
X_even(k) = [4, -2] (짝수 인덱스의 DFT)
X_odd(k) = [6, -2] (홀수 인덱스의 DFT) // 하위 배열이 크기가 충분히 작으므로, 직접 DFT를 계산함 - 결합:
X(0) = X_even(0) + W^0_4 * X_odd(0) = 4 + 1 * 6 = 10
X(1) = X_even(1) + W^1_4 * X_odd(1) = -2 + (-1 + 0j) * (-2) = 0
X(2) = X_even(0) + W^2_4 * X_odd(0) = 4 + (-1) * 6 = -2
X(3) = X_even(1) + W^3_4 * X_odd(1) = -2 + (1 - 0j) * (-2) = -4
(W_N = exp(-j * 2 * π / N)은 특정 주파수 인덱스 k에 대한 특정 크기 N의 특수 복소수 상수)
결과는 다음과 같다. X(k) = [10, 0, -2, -4]
FFT 알고리즘 구현
실제로 자바에서 코드로 구현했을 때는 다음과 같다. (주석을 포함하여 설명하였음)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
public class FFT {
// FFT 함수: 주어진 복소수 배열에 대해 고속 푸리에 변환을 수행합니다.
public static void fft(double[] data) {
int n = data.length; // 복소수 배열의 길이를 계산함.
if (n == 2) return; // 입력 크기가 2 (1개의 복소수)이면 반환함.
if (n % 4 != 0) throw new IllegalArgumentException("n is not a power of 2");
// 짝수 인덱스의 복소수와 홀수 인덱스의 복소수를 분리함.
double[] even = new double[n / 2];
double[] odd = new double[n / 2];
for (int i = 0; i < n / 4; i++) {
even[2 * i] = data[4 * i];
even[2 * i + 1] = data[4 * i + 1];
odd[2 * i] = data[4 * i + 2];
odd[2 * i + 1] = data[4 * i + 3];
}
// 재귀적으로 짝수와 홀수 배열에 대한 FFT를 계산함.
fft(even);
fft(odd);
// 짝수와 홀수 배열의 결과를 결합하여 최종 결과를 구함.
for (int i = 0; i < n / 4; i++) {
double t = -2 * i * Math.PI / (n / 2); // 각도
double cosT = Math.cos(t); // 코사인
double sinT = Math.sin(t); // 사인 값
// 홀수 배열의 요소에 twiddle factor를 곱함.
double real = odd[2 * i] * cosT - odd[2 * i + 1] * sinT;
double imag = odd[2 * i] * sinT + odd[2 * i + 1] * cosT;
// 짝수 배열과 홀수 배열의 결과를 결합.
data[4 * i] = even[2 * i] + real;
data[4 * i + 1] = even[2 * i + 1] + imag;
data[4 * i + 2] = even[2 * i] - real;
data[4 * i + 3] = even[2 * i + 1] - imag;
}
}
public static void main(String[] args) {
double[] data = {1, 0, 2, 0, 3, 0, 4, 0}; // 복소수 입력: {1+0j, 2+0j, 3+0j, 4+0j}
fft(data); // 입력 데이터에 대해 FFT를 수행.
for (int i = 0; i < data.length; i += 2) {
System.out.println(data[i] + ", " + data[i + 1]); // 결과를 출력.
}
}
}
실행 결과:
10.0, 0.0
-2.0, 2.0
-2.0, 0.0
-1.9999999999999998, -2.0 // 여기서 결과값이 -2.0이 되어야 하지만 컴퓨터의 부동 소수점 반올림 오차로 인해 생기는 현상
FFT 고속 푸리에 변환을 사용하는 이유는 무엇일까?
위의 예제를 통해 분할, 정복, 결합하는 과정이 효율적으로 이산 푸리에 변환을 계산하는 것을 확인 할 수 있다.
또한, 이 알고리즘을 사용 하였을 때 장점에 대해서 알아보자.
- 시간 절약: FFT는 DFT보다 빠르게 주파수 도메인 변환을 하기 때문에 시간 소요가 많이 되는 앱에서 효율성이 크게 향상된다.
- 실시간 처리: 특히 실시간 앱에서는 빠른 변환 속도가 중요하므로, FFT의 빠른 계산 속도로 인해 실시간 신호 처리와 분석이 가능하다.
- 계산 리소스 절약: FFT는 저 적은 연산을 필요로 하므로 메모리와 처리 성능에 대한 요구사항이 현저하게 줄어든다. 이로 인해서 >낮은 컴퓨팅 리소스를 가진 장치에서도 복잡한 신호 처리 작업을 수행할 수 있다.
FFT를 구현하고 해당 알고리즘의 성능 평가
아래의 코드는 위에서 구현한 FFT 함수를 호출하여 성능 평가를 구현 하였으며,
입력 데이터를 무작위로 생성하여 실행 시간 측정과 메모리 사용량을 측정하는 기능을 구현하였다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
import java.util.Arrays;
import java.util.Random;
public class FFTPerformanceTest {
public static void main(String[] args) {
int n = 1024; // 입력 데이터 크기
int iterations = 10; // 반복 횟수
double[] inputData = new double[n * 2]; // 입력 데이터를 저장할 배열
Random random = new Random();
// 입력 데이터를 무작위로 생성
for (int i = 0; i < inputData.length; i += 2) {
inputData[i] = random.nextDouble();
inputData[i + 1] = 0;
}
System.out.println("Input data: " + Arrays.toString(inputData));
// 실행 시간 측정 시작
long startTime = System.nanoTime();
// 알고리즘 반복 실행
for (int i = 0; i < iterations; i++) {
double[] data = inputData.clone(); // 입력 데이터를 복사
SimpleFFT.fft(data); // FFT 실행
}
// 실행 시간 측정 종료 및 결과 출력
long endTime = System.nanoTime();
double duration = (endTime - startTime) / 1e6; // 밀리초 단위로 변환
System.out.println("Average execution time: " + (duration / iterations) + " ms");
// 메모리 사용량 측정
Runtime runtime = Runtime.getRuntime();
long usedMemory = runtime.totalMemory() - runtime.freeMemory();
System.out.println("Memory used: " + usedMemory + " bytes");
}
}
실행결과:
//처음에는 랜덤으로 만들어진 입력값도 출력되게 만들었지만 값이 너무 많아 입력값을 출력되지 않게 수정하였음.
Average execution time: 0.56343 ms
Memory used: 6219888 bytes
FFT를 이용한 응용 분야
현재 졸업 작품으로 아두이노를 이용한 심전도 검사 및 건강관리 구현중인 상태이며, FFT를 이용하여 심전도 데이터를 분석할 수 있다는 정보를 알게 되었다. 이에 FFT를 이용하여 심전도 데이터를 분석하는 방법에 대해 알아보자.
우선 심전도 데이터는 전극을 통해 측정되는 심장 신호이다. 위에서 설명했듯이 fft는 주파수 영역에서의 성분을 분석할 수 있기 때문에 이를 이용하여 다양한 분야의 분석에 활용되고 있는데, 심전도 데이터 역시 주파수 영역에서 분석이 가능하다. 예를 들어 규칙적인 심장박동은 주파수가 높은 성분에 해당되고 심장의 수맥과 같은 생리적인 요소는 주파수가 낮은 성분에 해당된다. 따라서 심장 신호의 주요 주파수 성분을 파악하여 심장 질환의 치료에 활용되어질 수 있다.
FFT를 활용한 심전도 분석 단계
심전도 데이터는 일정 시간 간격으로 측정된 전기 신호 데이터임으로, 특정 시간 간격으로 샘플링 된다.
이러한 데이터를 FFT에 적용하기전에, 입력데이터의 일부분을 강조하거나 감소시켜 FFT의 정확도를 높이는 단계를 거친다.
이 단계에서 윈도수 함수를 사용할 수 있는데 이 함수는 위에 설명한 것과 같이 강조,감소를 통해 분석의 정확도를 높이는 역할을 한다.
출처:https://www.google.com/url?sa=i&url=https%3A%2F%2Fir.ymlib.yonsei.ac.kr%2Fbitstream%2F22282913%2F135985%2F1%2FTA00950.pdf&psig=AOvVaw3UjJefrQk3ZKEjXrP65dEp&ust=1683188144189000&source=images&cd=vfe&ved=0CBMQjhxqFwoTCPCVv87a2P4CFQAAAAAdAAAAABAE
위의 사진은 연세대학교에서 시-주파수 분석을 이용한 심전도 분석에 대한 연구자료중 하나이다.
위 사진은 심실세동 데이터인데, 이 데이터들을 시-주파수 분석, 다시 말해 fft를 이용해 분석할 수 있다는 것이다.
이 다음 단계부터는 순서대로 설명을 해보자.
- FFT 알고리즘을 적용을 하여 데이터를 분석하면 시간 영역에서의 신호를 주파수 영역에서의 파워 스펙트럼 값으로 변환한다.
- 파워 스페트럼을 계산하여야 하는데, 이 값은 각 주파수 대역의 성분에 대한 크기를 나타내는 값이다. 따라서 이 값은 주파수 대역 별로 구할 수 있으며, 입력데이터에서 주파수 대역을 파악할 수 있다.
- 주요 주파수 대역을 분석을 함으로써 해당 주파수 대역과 관련된 심장질환이 있는지 확인하고 분석한다.
이러한 방법을 통해서 FFT를 심전도 분석에 활용하여 실제로 진행할 수 있는데, 지금 진행중인 졸업 프로젝트 작품에서 FFT를 실제로 구현하여 적용시킬 계획이다.
이상으로 fft가 무엇인지에 대해서 알아보고, 실제 구현 및 분석을 통해 실제 데이터값들이 어떻게 출력되는지 직접 확인해보는 과제를 통해
fft의 활용도가 높다는것을 알게되었으며, 실제로 진행중이었던 프로젝트에도 이용되어질 수 있다는 정보를 알게되어 유익한 과제로 마무리 한다.
