원문 : http://www.dspdimension.com/admin/dft-a-pied/
Posted by Bernsee on September 21, 1999

Step 6 : DFT(Discrete Fourier Transform)

사인 변환에서 푸리에 변환까지 과정을 더 '일반화' 시킴으로써 간단하다. 사인 변환에 측정된 각 진동수를 위한 사인 파형을 사용하는 반면, 푸리에 변환에서는 사인 코사인 파형을 둘다 사용했다. That is, for any frequency we are looking at we ‘compare’ (or ‘resonate’) our measured signal with both a cosine and a sine wave of the same frequency. 만약 우리 신호가 사인 파형과 굉장히 닮았다면, 우리 변환의 사인 부분은 큰 진폭을 가질것이다. 만약 코사인 파형과 닮았다면, 코사인 부분이 커지게 될 것이다. 사인 파형과 정반대라면, 이것은 영에서 시작하여 1로 올라가는게 아니라 -1로 떨어지르것이다, 사인 부분은 음수의 값이 큰 진폭을 가질 것이다. 사인 코사인 위상은 받은 진동수에서 임의의 사인 형태로 보여질 수 있는것과 같이 +와 - 둘이 함께 보여질 수 있다.

//
// Listing 1.2: The direct realization of the Discrete Fourier Transform***:
//

#define M_PI 3.14159265358979323846

long bin, k;
double arg, sign = -1.; /* sign = -1 -> FFT, 1 -> iFFT */

for (bin = 0; bin <= transformLength/2; bin++) {
    cosPart[bin] = (sinPart[bin] = 0.);
    for (k = 0; k < transformLength; k++) {

        arg = 2.*(float)bin*M_PI*(float)k / (float)transformLength;
        sinPart[bin] += inputData[k] * sign * sin(arg);
        cosPart[bin] += inputData[k] * cos(arg);   

     }
}

우리는 여전히 푸리에 변환에 의해 뭔가 유용한 것을 얻어내야하는 과제를 남겨놓고 있다. I have claimed that the benefit of the Fourier transform over the Sine and Cosine transform is that we are working with sinusoids. 그러나 우리는 어떠한 정령 파도 보지 않았다, 오로지 싸인과 코싸인만 있다. 으음 이것은 추가적인 처리를 요구한다.

//
// Listing 1.3: Getting sinusoid frequency, magnitude and phase from 
// the Discrete Fourier Transform:
//

#define M_PI 3.14159265358979323846

long bin;
for (bin = 0; bin <= transformLength/2; bin++) {

    /* frequency */
    frequency[bin] = (float)bin * sampleRate / (float)transformLength;
    /* magnitude */
    magnitude[bin] = 20. * log10( 2. * sqrt( sinPart[bin]*sinPart[bin] + cosPart[bin]*cosPart[bin]) / (float)transformLength);
    
    /* phase */
    phase[bin] = 180.*atan2(sinPart[bin], cosPart[bin]) / M_PI - 90.;

}

DFT 아웃풋의 위 코드를 실행한 한 뒤에, 우리는 정형파의 합으로써 인풋 신호의 계산을 끝날 것이다. k-th 정형파는 frequency[k], magnitude[k] 그리고 phase[k]에 의해 설명된다. 단위는 Hz (Hertz, periods per seconds), dB (Decibel) 그리고 ° (Degree)이다. 이전에 계산한 1.3 Listing의 싱글 정형파의 사인 코사인 부분을 변환한뒤, 이제 항상 양수를 가지는 k-th 정형파의 DFT bin "magnitude" 진폭이라 부를것이고 이것을 기억하고 있어라. 우리는 진폭이 -1.0이든 1.0이든 위상이 +혹은 -180도 다른 magnitude가 1.0이라고 말 할 수 있다. 관련 문헌에서는, magnitude[ ] 배열을 측정된 신호의 Magnitude Spectrum라 부르고, phase[ ] 배열을 프리에 변환에 의해 계산된 측정된 신호의 Phase Spectrum이라 부른다.

데시벨에 bin magnitude를 측정하기 위해 참조함으로써, 우리의 인풋 파형은 DFS(digital full scale)의 0dB 크기를 갖는 [-1.0, 1.0] 범위의 값을 가질 것으로 예상 할 수 있다. DFT의 어플리케이션에 흥미를 보임으로써, 예를 들어 listing 1.3은 DFT를 기반으로한 스펙트럼 분석을 도출하는데 사용될 수 있다.

원문 : http://www.dspdimension.com/admin/dft-a-pied/
Posted by Bernsee on September 21, 1999

Step 5 : Apple과 Oranges에 대해

만약 아직 당신이 따라오고 있다면, 푸리에 변환에 대한 여행이 거의 끝나간다. 우리는 얼마나 많은 사인 파형이 필요로 하는지에 대해 배웠고, 필요로 하는 수는 우리가 보고있는 샘플 수와 밀접한 관게가 있다는것, 낮은 주파수와 높은 진동수의 경계에 있는 것과 어쨋든 우리의 레시피를 완성시키기 위해서는 각 부분의 파형의 진폭을 결정할 필요가 있다는 것을 배웠다. 아직 완벽하게 해결한 것은 아니지만 샘플들을 어떻게 조리할지 결정할 수는 있을 것이다. 쉽게말하면, 우리가 측정한 샘플들과 우리가 알고 있는 진동수의 사인파형을 비교함으로써 사인파형의 진폭을 알아내고, 그것들이 어떻게 '같은지'에 대해 알아내보았다. 만약 그것들이 완벽히 같다면 그 사인파형은 반드시 같은 진폭이고 만약 참고하고있는 사인파형과 우리의 신호가 맞지 않다면 아닐 같은 진폭이 아닐 것이다. 그런데 어떻게 우리가 알고 있는 사인파형과 샘플 신호를 효과적으로 비교할 것인가? 다행히도 DSPer은 이 부분을 미리 만들어 놓았다. 사실 숫자를 곱하거나 더하는 아주 쉬운 부분이다. - 우리는 알고있는 진동수와 유닛진폭(이것은 계산기나 우리 컴퓨터의 sin( )함수로부터 나온 오직 한개의 진폭을 의미한다.)의 '참조하는' 사인파형을 계산하고, 우리의 신호 샘플들을 곱한다. 곱해진 결과값을 더하고나서, 우리가 다루고있는 진동수로부터 사인파형의 진폭을 얻어낸다.

이것을 C로 나타내면 아래와 같이 된다.

#define M_PI 3.14159265358979323846

long bin, k;
double arg;
for (bin = 0; bin < transformLength; bin++) {
    transformData[bin] = 0.;
    for (k = 0; k<transformLength; k++) {

        arg = (float)bin * M_PI * (float)k / (float)transformLength;
        transformData[bin] += inputData[k] * sin(arg);
    }
}

원문 : http://www.dspdimension.com/admin/dft-a-pied/
Posted by Bernsee on September 21, 1999

Step 4 : 요리법(cooking recipes)에 대해

이전 단락에서는 컴퓨터의 어떤 신호가 혼합된 사인파형으로부터 만들어 질 수 있다는 것을 확인했다. 우리는 진동수에 대해 생각해보았고 어떤 최대, 최소 진동수의 사인파형이 우리가 분석하는 신호를 완벽하게 복원하기 위해 필요로하는지도 생각해보았다. 우리가 봐온 샘플의 수가 가장 낮은 사인 파형이 필요로하는 가장 최하 부분을 결정하는데 얼마나 중요한지 봐왔지만, 우리는 아직 실제 사인파형이 최대 몇개의 결과물을 만들어내는지 논의되지 않았다. 사인 파형에의해 만들어진 신호를 구성하기 위해, 우리는 그 중 한 부분을 확인해볼 필요가 있다. 사실은, 주파수는 우리가 알아야할 유일한 것이 아니다. 우리는 또한 사인 파형들의 진폭을 알 필요가 있다. 즉. 인풋 신호를 다시 만들기위한 각 사인 파형의 갯수. 진폭은 사인파횽의 최대 높이이다. 그러니까 0으로부터 최댓값 사이의 거리를 맗나다. 높은 진폭은 음량이 클것이고, 우리도 그렇게 들을 것이다. 그러므로 신호에 저음이 많다면 높은 주파수의 사인파형 보다 낮은 사인파형들이 많이 합쳐져 있을 것으로 예상할 수 있다. 일반적으로 저음의 낮은 주파수의 사인파형은 높은 사인 파형들보다 큰 진폭을 가지고 있다. 우리의 분석에서, 우리는 레시피(recipe)를 완성하기위해 각 사인파형의 진폭을 정해야 할 것이다.

위에서 확인했듯이, 복잡한 모양의 파형은 사인 파형들의 조합으로 만들어 질 수 있다. 우리는 이렇게 질문을 던질 수 있다. “컴퓨터가 신호를 만드는데 얼마나 많이 필요로 하나?” 흠.. 물론 이것은 하나의 사인파형일 수도 있다. 그 주어진 사인파형으로 우리가 다룰 그 시그널이 어떻게 만들어지는지 알고있다. 대부분 우리는 복잡한 구조의 현실세계 신호를 다룬다. 따라서 우리는 현재 파형의 얼만큼 나누어져있는지 미리 알지 못한다. 이 경우, 원본 신호를 구성하는 사인파형이 얼마나 많은 상한선을 필요로하는지 모르는 것은 얼마나 다행스런 일인지 모른다. 그치만 여전히 "얼마나 많이”에 대한 질문은 해결되지 않았다. 그럼 좀 직관적으로 접근해보자: 신호 중 1000개의 샘플이 있다고 가정해보자. 이 짧은 주기(신호 안에 대부분 최댓값과 최솟값이 있는)에 있을 수 있는 사인 파형은 모든 샘플마다 최댓값과 최솟값을 왓다갓다 했다. 그러므로 모든 샘플이 피크가 있다고 가정할 때, 가장 높은 주파수의 사인파형은 1000개의 샘플에서 500개의 최댓값과 500개의 최솟값을 가진다. 아래 그래프의 검정색 점을 말하는 것이다. 따라서 가장 진동수가 높은 사인 파형은 아래와 같이 생겼다. 

원문 : Mastering The Fourier Transform in One Day
Posted by Bernsee on September 21, 1999

Step 2 : 푸리에 변환에 대해 이해하기
Jean-Baptiste Joseph Fourier(푸리에씨)는 부모가 그를 자랑스러워하거나 부끄러워하거나 하는 둘중 하나의 아이였다, 그는 14살때 굉장히 어려운 수학 용어를 막 말하기 시작했다. 비록 그는 일생동안 어마어마하게 많은 중요한 일을 했지만, 가장 중요한 일은 물질에 관한 열 전도를 알아냈다는 것일 것이다. 그는 열이 중간 온도를 맞추기위해 어떻게 움직이는지에대한 방정식을 만들어내고, 삼각함수의 무한급수에 관한 이 방정식을 풀었다(우리가 논쟁하고 있는 사인 코사인). 우리의 주제와 연관지어서 생각해보면, 기본적으로 신호는 복잡하지만 푸리에는 신호가 사인 함수의 합으로 이루어져있고 그것을 합치면 신호가 된다는 것을 알아냈다.

저기 보이는 그래프는 원본 신호이며, 이것은 어떻게 특정 관계로 합쳐진 사인들로인해 비슷한 모양이 되는지 보여준다. 이제 잠시 레시피(recipe)에 대해 이야기 해보자. 당신도 볼 수 있드시 사인함수가 많을 수록 원본 파형에 가깝데 결과가 나타난다. '현실 세계'에서는 당신의 측정장비로는 한계가 있는 극한의 작은 텀으로 측정이 가능할 것이고, 당신은 얻은 신호로부터 무한히 많은 사인 함수를 뽑아내고 싶을 것이다. 불행히도, DSPers로써 우리는 그 세계에 살고 있지 않는다(이상 세계에 살고 있지 않다는 뜻인듯). 오히려, 우리는 일정 간격과 무한하지 않는 정밀도로 측정된 "현실세계"의 셈플을 다루고 있다. 그러므로 우리는 무한히 많은 사인함수는 필요 없고, 그냥 '많다' 싶을 정도만 있으면 된다. 또 우리는 '많다는게 얼만큼이냐'고 되물을 수 있는데 다음 단락에서 알려주겠다. 한 순간동안, 모든 신호는 당신의 컴퓨터가 단순한 사인 파형으로 합쳐서 형상화할 수 있다는 것이 중요하다.(For the moment, it is important that you can imagine that every signal you have on your computer can be put together from simple sine waves, after some cooking recipe.)

원문 : Mastering The Fourier Transform in One Day
Posted by Bernsee on September 21, 1999


신호 처리에 조금이라도 관심이 있다면 제목을보고 의구심을 강하게 느꼈을 것이다. 나도 동의한다.. 물론 당신은 모든 푸리에 변환을 이해하려면 연습하고 반복하고 결국 깊은 수학까지 알아야하지만, 이 온라인 강좌는 푸리에 변환이 어떻게 동작하는지 기본적인 지식을 제공하고, 왜 이것 동작하는지 또한 당신이 틀에 얽매이지 않게 어떤 것에 접근하려할때 왜 이게 사용하기 간편한지 까지 알려 줄 것이다. 요점을 정리하자면 당신은 더하고 빼는 수학적인 요소를 배제한 완전 기초적인 푸리에 변환에 대해 배우게 될 것이다! 나는 6단락이 넘지않게 하여 오디오 신호 처리를 위한 예제 응용프로그램과 함께 푸리에 변환에 대해 설명할 것이다.

Step 1 : 몇몇 반드시 필요한 간단한 요소들

이번 단란에서 당신이 이해하는데 필요한 것은 4가지가 있다: 어떻게 숫자를 더하는가, 어떻게 그것들을 곱하고 나누는가, sin, cos 그리고 sinusoid(번역자:사인 파형)이 무엇이고, 그들이 어떻게 나타나는가. 명백하게 나는 첫번째 두번째를 스킵하고 단지 약간 마지막 것을 설명해 보겠다. You probably remember from your days at school the ‘trigonometric functions’* that were somehow mysteriously used in conjunction with triangles to calculate the length of its sides from its inner angles and vice versa. 이 모든 것들이 필요한건 아니고, “사인”과 “코사인” 두가지 삼각함수만 필요하다. 아주 쉽다: 그것들은 최댓값과 최솟값이 있고 좌우로 끝임없이 쭈우욱 이어져있는 아주 심플한 파형이다.

당신이 확인할 수 있듯이 두 파형은 모두 주기적이며, 이 말은 정확한 주기 시간 뒤에는 똑같은 형태로 보여질 것이라는 뜻이다. 또한 두 웨이브는 서로 비슷하게 생겼다. 대신에 코사인 함수는 최대값(피크값)에서 시작하고, 사인함수는 0에서 시작한다(최솟값이 아님). 이제 실전에서, 우리가 어떻게 최대에서 시작하는지 0에서 시작하는지 알 수 있는가? 좋은 질문이다. 알 수 없다. 실전에서 이것이 사인 함수인지 코사인 함수인지 판별할 방법이 없다, 그래서 우리는 사인이나 코사인 처럼 생긴 파형들을 사인파형(sinusoid)라고 부른다. (그리스어로 번역해보면 “sinus-like”라고 함). 사인 파형의 중요한 요소는 한 주기동안 최댓값과 최솟값을 몇번 왔다갔다 했는지 알 수 있는 “진동수”이다. 높은 진동수는 최댓값 최솟값을 많이 왔다갔다 할 것이고, 낮은 진동수에서는 적게 왔다갔다 할 것이다.