고속푸리에 변환 알고리즘 및 응용

1 서론 1
1.1 이산 푸리에 변환의 응용분야 1

2 이산 푸리에 변환 3
2.1 정의 3
2.2 Z-변환 5
2.3 DFT의 성질 11
2.4 콘볼루션 정리 16
2.4.1 곱셈 정리 23
2.5 상관도 정리 23
2.6 오버랩-애드와 오버랩-세이브 기법 26
2.6.1 오버랩-애드 기법 27
2.7 데이터 영역 제로 패딩 30
2.8 하나의 복소 FFT를 이용한 두 실수 시퀀스의 DFT 계산법 32
2.9 DFT 행렬에 의해 대각화된 순환행렬 33
2.9.1 토플리츠 행렬 33
2.9.2 순환 행렬 33
2.9.3 DFT 행렬에 의해 대각화되는 순환 행렬 33
2.10 요약 35
2.11 문제 35
2.12 프로젝트 39

3 고속 알고리즘 41
3.1 라딕스-2 DIT-FFT 알고리즘 41
3.1.1 N = 8의 경우 IFFT를 위한 희소행렬 인자 47
3.2 희소행렬 분해에 의한 고속 알고리즘 48
3.2.1 에 대한 고찰 52
3.3 라딕스-2 DIF-FFT 57
3.3.1 DIF-FFT N=8 59
3.3.2 제자리(In-Place) 연산 64
3.4 라딕스-3 DIT FFT 64
3.5 라딕스-3 DIF-FFT 66
3.6 합성수 N에 대한 FFT 69
3.7 라딕스-4 DIT-FFT [V14] 70
3.8 라딕스-4 DIF-FFT 76
3.9 스플릿-라딕스 FFT 알고리즘 81
3.10 행렬 파티션에 의한 고속 푸리에 및 BIFORE 변환 82
3.10.1 행렬 파티션 82
3.10.2 DFT 알고리즘 85
3.10.3 BT (BIFORE 변환) 87
3.10.4 CBT (복소BIFORE 변환) 87
3.10.5 DFT (희소행렬 분해) 87
3.11 위노그라드 푸리에 변환 알고리즘 [V26] 87
3.11.1 5-점 DFT (그림 3.22) 88
3.11.2 7-점 DFT (그림 3.23) 88
3.11.3 9-점 DFT (그림 3.24) 89
3.11.4 실수 입력 데이터에 대한 DFT 알고리즘 [B29, A38] 91
3.11.5 위노그라드 짧은-N DFT 모듈 91
3.11.6 소인수 맵 인덱싱 [B29] 93
3.11.7 위노그라드 푸리에 변환 알고리즘 (WFTA) 96
3.12 DFT 행렬의 희소행렬화 98
3.12.1 복소회전을 이용한 DFT 행렬의 희소행렬화 98
3.12.2 유니테리 행렬을 이용한 DFT 행렬의 희소행렬화 100
3.13 통합 이산 푸리에-하틀리 변환 103
3.13.1 고속 UDFHT 구조 106
3.14 Bluestein의 FFT 알고리즘 109
3.15 Rader 소수 알고리즘 [A34] 111
3.16 요약 113
3.17 문제 113
3.18 프로젝트 115

4 정수형 고속 푸리에 변환 117
4.1 서론 117
4.2 리프팅 기법 117
4.3 변환 알고리즘 118
4.3.1 고정점 연산 구현 122
4.4 정수형 이산 푸리에 변환 124
4.4.1 준완전 정수 DFT 124
4.4.2 완전 정수 DFT 126
4.4.3 에너지 보존 127
4.4.4 순회 천이 128
4.5 요약 130
4.6 문제 130
4.7 프로젝트 131

5 이차원 이산 푸리에 변환 132
5.1 정의 132
5.2 성질 135
5.2.1 주기성 136
5.2.2 공액 대칭성 136
5.2.3 시간/공간 영역 순회 천이 (주기적 천이) 137
5.2.4 주파수 영역 순회 천이 (주기적 천이) 138
5.2.5 스큐(Skew) 성질 [IP26] 140
5.2.6 회전 성질 140
5.2.7 파세발 정리 140
5.2.8 콘볼루션 정리 141
5.2.9 상관도 정리 143
5.2.10 공간 영역 미분 144
5.2.11 주파수 영역 미분 144
5.2.12 라플라시안 144
5.2.13 구형파 144
5.3 이차원 필터링 146
5.3.1 역 가우시안 필터 (IGF) 148
5.3.2 루트 필터 150
5.3.3 호모모픽 필터링 151
5.3.4 동적 범위 압축 154
5.3.5 가우시안 LPF 155
5.4 인버스 및 위너 필터링 156
5.4.1 위너 필터 158
5.4.2 기하 평균 필터 (GMF) 160
5.5 삼차원 DFT 161
5.5.1 3-D DFT 161
5.5.2 3-D IDFT 161
5.5.3 3-D 좌표계 162
5.5.4 간단한 3-D DFT 162
5.5.5 간단한 3-D IDFT 162
5.6 1-D DFT 영역에서 분산 분포 163
5.7 유니테리 변환에서 분산합의 불변성 164
5.8 2-D DFT 영역에서 분산 분포 165
5.9 분산에 의한 변환계수의 양자화 166
5.10 최대 분산 존 샘플링 (MVZS) 171
5.11 기하학적 구역 샘플링 (GZS) 172
5.12 요약 177
5.13 문제 177
5.14 프로젝트 177

6 벡터-라딕스 2D-FFT 알고리즘 188
6.1 벡터-라딕스 DIT-FFT 188
6.2 벡터-라딕스 DIF-FFT 191
6.3 요약 196

7 비균일 DFT 198
7.1 서론 198
7.2 일차원 NDFT 198
7.2.1 균일 샘플 시퀀스에 대한 DFT 198
7.2.2 NDFT의 정의 200
7.2.3 NDFT의 성질 202
7.2.4 NDFT-2의 예 205
7.3 NDFT의 고속계산 210
7.3.1 전방향 NDFT 210
7.3.2 역방향 NDFT 216
7.4 이차원 NDFT 219
7.4.1 2D 샘플링 구조 220
7.4.2 2-D 비균일 직각 샘플링 예 223
7.5 NDFT에 의한 필터 설계 224
7.5.1 저역통과필터 설계 224
7.5.2 비균일 저역통과필터의 예 231
7.6 요약 235
7.7 문제 235

8 FFT 응용 238
8.1 주파수영역 다운샘플링 238
8.1.1 주파수영역 업샘플링 (제로 첨가) [IN5] 241
8.2 프랙탈 영상압축 [FR3, FR6] 242
8.3 위상만의 상관성 246
8.4 DFT/FFT를 이용한 영상 회전 및 이동 [IP10] 249
8.5 화면내 오차 은닉 [IP28] 252
8.6 표면 텍스쳐 분석 253
8.7 FFT 기반 청각 모델 253
8.8 영상 워터마킹 [E8] 255
8.9 오디오 워터마킹 257
8.9.1 감각 마스킹을 이용한 오디오 워터마킹 258
8.10 OFDM 259
8.10.1 IFFT/FFT를 이용한 OFDM 신호 표현 260
8.11 OFDM을 위한 FFT 프로세서 261
8.12 DF DFT-기반 채널 추정법 [C16] 263
8.12.1 DF DFT-기반 채널 추정법 264
8.12.2 공액-그라디언트 고속 푸리에 변환 (CG-FFT) [K1?4, B12] 264
8.13 수정 이산 여현 변환 (MDCT) 264
8.14 홀수 스택 TDAC 272
8.15 감각적 오디오 부호기 [D3, D4] 275
8.16 OCF 부호기 276
8.17 NMR 측정 시스템 277
8.18 이동 수신용 오디오 부호기 278
8.19 ASPEC 오디오 부호기 279
8.20 RELP 보코더 280
8.21 호모모픽 보코더 [D30] 281
8.22 MUSICAM 오디오 부호기 281
8.23 AC-2 오디오 부호기 [D13, D14, D19, D21, D24] 283
8.24 IFFT에 의한 IMDCT / IMDST 구현 284
8.25 IFFT에 의한 MDCT/MDST 구현 289
8.26 자기상관함수 및 전력밀도 스펙트럼 290
8.26.1 필터된 백색잡음 291
8.27 삼차원 얼굴 인식 292
8.28 이차원 다중율 처리 293
8.28.1 업샘플링및 보간 294
8.28.2 다운샘플링 및 솎음 297
8.29 고속 균일 이산 커브렛 변환 (FUDCuT) 303
8.29.1 라돈 변환 303
8.29.2 리지렛 변환 304
8.29.3 커브렛 변환 305
8.30 문제 313
8.31 프로젝트 316

부록 A 각종 이산변환의 성능 비교 319
A.1 변환부호화 이득 319
A.2 변환영역 분산 분포 320
A.3 정규화 MSE 321
A.4 율-왜곡 관계 321
A.5 잔류 상관도 322
A.6 스칼라 위너 필터링 323
A.7 기하학적 구역 샘플링 (GZS) 324
A.8 최대 분산 구역 샘플링 (MVZS) 325

부록 B 화질평가를 위한 스펙트럼 거리 측정 326

부록 C 정수 이산여현변환 (INTDCT) 332
C.1 리프팅에 의한 정수 DCT 332
C.1.1 왈쉬-하다마드 변환에 의한 DCT 분해 333
C.1.2 정수 DCT의 구현 336
C.2 이항 (dyadic) 대칭 원리를 이용한 정수 DCT 337
C.2.1 8차 정수 DCT 생성 337
C.2.2 비디오 부호화 표준에서 정수 DCT 339
C.2.3 8-점 정수 DCT의 성능 345

부록 D DCT 및 DST 347
D.1 DCT 및 DST 커늘 347
D.2 유니테리 DCT 및 DST 유도 349
D.2.1 2-D DFT에서 2-D DCT-II의 유도 355
D.3 FFT 대신 DCT와 DST를 이용한 순회 콘볼루션 357
D.4 DCT의 순회 천이 성질 358

부록 E 크로네커 곱셈 및 분리성 360
E.1 크로네커 곱셈 360
E.2 일반화된 크로네커 곱셈 361
E.3 분리 변환 361

부록 F 수학 공식 363

부록 G 매트랩 기초 365
G.1 MATLAB 관련 웹사이트 369
G.2 MATLAB 관련 도서 370
부록 H WFTA 및 POC를 위한 매트랩 코드 372
H.1 15-점 WFTA를 위한 매트랩 코드 [A39] 372
H.2 위상만의 상관도 (POC)를 위한 MATLAB 코드 (제8.3절) 374

참고문헌 376
색인 407