원문 : 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를 기반으로한 스펙트럼 분석을 도출하는데 사용될 수 있다.





WRITTEN BY
tucan.dev
개인 iOS 개발, tucan9389

,

원문 : 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);
    }
}

이 코드는 inputData[0...transformLength-1] 에 저장된 샘플 포인트를 transformData[0...transformLength-1]에 사인 파형의 진폭들의 배열 형태로 변환한다. According to common terminology, we call the frequency steps of our reference sine wave bins, which means that they can be thought of as being ‘containers’ in which we put the amplitude of any of the partial waves we evaluate. 일반적으로 쓰이는 용어를 빌리지면, 우리가 계산한 부분 파형의 어떤 진폭을 담은 'containers' 로써 생각될 수 있음을 의미하며, 참조하는 사인 파형 bin들의 진동수 단계라고 부른다
DST(Discrete Sine Transform)는 사인파형 부분들의 진폭을 구하기 위해 우리의 신호가 어떻게 생겼는지 모르거나 아니면 우리가 효과적인 방법을 사용할 수 있다고 가정하는 그러한 일반적인 흐름을 따른다. (예를들어 우리가 미리 우리의 신호가 알고있던 진동수의 한 ㅏ인 파형이라고 안다면, 우리는 즉시 사인파형의 큰 범위를 계산함 없이 진폭을 구할 수 있을 것이다. 푸리에이론에 기반한 이 효과적인 접근은 “Goertzel” 알고리즘을 찾을 수 있게 해주었다.)




WRITTEN BY
tucan.dev
개인 iOS 개발, tucan9389

,

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


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

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


WRITTEN BY
tucan.dev
개인 iOS 개발, tucan9389

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

Step 3 : “많다”는게 얼만큼인가?

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


이제 가장 낮은 진동수의 사인 파형이 어떻게 생겼는지 확인해 보자. 만약 우리가 오직 하나의 샘플 점을 얻었다면, 이 점 하나가지고 어떻게 사인파형의 최댓값과 최솟값을 구하겠는가? 할 수 없다, 그러므로 이 한 점으로부터 나올 수 있는 파형의 주기는 무수히 많다.


그러므로 한개의 데이터 점은 전동수를 표현하기에는 충분하지 않다는 것이다. 이제 우리는 두개의 샘플이 지정되있을 경우, 이 두개의 점을 가지고 가장 낮은 진동수의 사인파형을 만들 수 있을까? 이 경우는 굉장히 단순하다. 여기서 두 점으로 부터 얻은 가장 낮은 진동수의 파형은 오직 하나밖에 없다. 아래 그림을 보자.



한뼘 정도 되는 두 못 사이에 줄이 연결되어 있는 상황을 상상해 보아라 (위 그래프는 사인 파형이 주기를 갖는다는 것을 세개의 점으로 표현한 것이다. 그러나 우리는 진동 수를 알아내기 위해 단지 제일 왼쪽 두 점만 있으면 된다). 사인 파형이 두 점 사이에서 왼쪽으로 가는 것과 같이, 우리가 볼 수 있는 가장 낮은 진동수는 두 못 사이에서 앞 뒤로 흔들리는 줄이다. 1000개의 샘플을 가지고 있다면, 두 ‘못’은 첫번째 샘플과 마지막 샘플이 될 수 있을 것이다, 예를들어 샘플 1번과 샘플 1000번. 우리는 우리의 경험으로 악기의 현 길이가 길어질수록 진동수가 낮아진다는 것을 안다. 그래서 우리는 못을 멀리 떨어뜨릴수록 사인파형의 주파수가 낮아짐을 예상할 수 있다. If we choose 2000 samples, for instance, the lowest sine wave will be much lower since our ‘nails’ are now sample number 1 and sample number 2000. 사실 1000 샘플에서 못을 두배 멀리 떨어뜨리면, 두배로 낮아질 것이다. 그러므로 우리가 더 많은 샘플을 가지고 있으면 0을 교차하는 점('못')을 멀리 떨어뜨려 더 낮은 주파수를 구할 수 있다. 이것은 설명을 이해하는데 굉장히 중요한 부분이다. 

또한 두 ‘못’과 함께 파형은 오르막 경사와 함께 반복된 후에 확인 할 수 있을 것이다(처음과 세번째 못은 동일하다). This means that any two adjacent nails embrace exactly one half of the complete sine wave, 다른말로는 한 최대점 혹은 한 최솟점 혹은 1/2 주기이다.


방금 무엇을 배웠는지 요약하자면, we see that the upper frequency of a sampled sine wave is every other sample being a peak and a valley and the lower frequency bound is half a period of the sine wave which is just fitting in the number of samples we are looking at. But wait – wouldn’t this mean that while the upper frequency remains fixed, the lowest frequency would drop when we have more samples? 정확하다! 우리는 낮은 주파수에서 시작하기 때문에, 이 결과는 알 수 없는 컨텐트의 더 긴 신호를 합치길 원할 때 더 많은 사인 파형을 필요로 하게 될 것이다.

모든것이 순조롭다. 그러나 여전히 결과적으로 얼마만큼의 사인 파형이 필요한지는 알 지 못했다. 이제 낮은 주파수나 높은 주파수의 사인 파형의 일부분을 알 수 있음으로써, 우리는 이 두 한계치 사이에서 얼만큼이 맞는지 계산할 수 있다. 우리는 극좌에서 극우까지 사이에서 가장 낮은 사인파형을 넣었어야 하기 때문에, 다른 모든 사인 파형 뿐만 아니라 nails까지 필요로 한다(왜 저렇게 다르게 다루고 있는가? 모든 사인파형은 같게 만들어지기 때문!). 단지 기타에서 두 고정된 점이 연결되 있는 현을 사인파형이라고 상상해보아라. 현은 두 고정된 점 사이에서만 진동할 것이다(부서지지 않는한), 우리의 사인 파형과 닮았다. 우리가 다루고 있는 1000 샘플에서 가장 낮은 1/2 주기를 가진 부분, 1주기를 가진 두번째 부분, 1과 1/2(1.5)주기를 가진 세번째 부분의 관계를 도출해낸다.

그림으로 그려보면 아래와 같다.


이제 1000샘플에서 얼마나 많은 사인파형이 적당한가를 물어본다면, 정확히 1000개의 사인 파형이 필요하다고 답해주면 된다. 사실 우리는 항상 가지고 있는 샘플의 수에 따라 사인파형이 필요하다는 것을 발견할 것이다.




WRITTEN BY
tucan.dev
개인 iOS 개발, tucan9389

,

원문 : 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”라고 함). 사인 파형의 중요한 요소는 한 주기동안 최댓값과 최솟값을 몇번 왔다갔다 했는지 알 수 있는 “진동수”이다. 높은 진동수는 최댓값 최솟값을 많이 왔다갔다 할 것이고, 낮은 진동수에서는 적게 왔다갔다 할 것이다.




WRITTEN BY
tucan.dev
개인 iOS 개발, tucan9389

,