KR101183658B1 - 이산 퓨리에 변환의 고속 처리 장치 및 방법 - Google Patents

Abstract

본 발명은 이산 퓨리에 변환을 고속으로 처리하는 장치 및 방법에 관한 것으로서, 랜덤 액세스 신호 검출을 위한 제1 입력신호를 입력받아 2의 지수승의 길이를 갖는 제2 입력신호로 변환하여 출력하는 제로 패딩부; 상기 제로 패딩부에서 출력된 상기 제2 입력신호에 대하여 고속 퓨리에 변환을 수행하는 고속 퓨리에 변환부; 및 상기 고속 퓨리에 변환부에서 출력된 출력신호로부터 프리앰블 인덱스를 검출하는 프리앰블 인덱스 결정부를 포함하는 이산 퓨리에 변환의 고속 처리 장치 및 그 처리 방법을 제공한다.

본 발명에 따르면, SC-FDMA 시스템에서 랜덤 액세스 신호를 검출하기 위해 수행되는 이산 퓨리에 변환을 고속 퓨리에 변환을 이용하여 신속하게 수행할 수 있고, 연산에 필요한 하드웨어의 구성을 단순화할 수 있다.

이산 퓨리에 변환, 고속 퓨리에 변환, FDMA, 랜덤 액세스 신호

Description

이산 퓨리에 변환의 고속 처리 장치 및 방법{APPARATUS AND METHOD OF EXECUTING DISCRETE FOURIER TRANSFORM FAST}

본 발명은 무선 통신 시스템에 관한 것으로서, 구체적으로는 SC-FDMA 시스템에서 랜덤 액세스 신호를 검출하기 위해서 실행되는 이산 퓨리에 변환을 고속으로 처리하는 장치 및 방법에 관한 것이다.

본 발명은 지식경제부 및 정보통신연구진흥원의 IT성장동력기술개발사업의 일환으로 수행한 연구로부터 도출된 것이다[과제관리번호: 2006-S-001-03, 과제명: 4세대 이동통신을 위한 적응 무선접속 및 전송 기술개발].

일반적으로, 이산 퓨리에 변환(DFT : Discrete Fourier Transform)은 수학 등 여러 분야에서 응용되고 있으며, DFT 수식은 [수학식 1]과 같다.

DFT 연산은 통신 분야에서도 많이 이용되고 있는데, 예컨대 도 1은 시스템에서 DFT가 수행된 상태를 나타내고 있다.

도 1은 일반적인 3GPP-LTE 시스템에서 839의 길이를 갖는 이산 퓨리에 변환(DFT)을 수행한 결과를 나타낸 그래프이다. 즉, 도 1은 프리앰블 인덱스(preamble index)가 1일 때 839-DFT의 출력을 나타낸 것으로서, 최고값을 나타내는 인덱스(index)는 77임을 알 수 있다.

3GPP-LTE 시스템에서 단말기의 랜덤 액세스 신호(PRACH : Physical Random Access Channel)를 기지국이 검색하기 위해서는 839의 길이를 갖는 DFT를 수행해야 한다. DFT 결과는 도 1과 같이 임의의 지점에서 피크(peak)가 되는 값을 갖게 되고 이를 바탕으로 PRACH 신호를 검출하게 된다. 그러나, 839의 길이를 갖는 DFT를 하드웨어로 구현하기에는 하드웨어 크기와 속도에서 제약사항이 따르게 된다.

한편, 고속 퓨리에 변환(FFT : Fast Fourier transform)은 DFT 정의를 바로 계산한 결과와 정확하게 같은 결과를 얻을 수 있다. 하나의 차이점은 FFT가 DFT에 비해서 훨씬 빠르다는 점이다.

FFT가 얼마나 효율적인지를 알아보기 위해서 복소수 승산(complex multiplication)과 복소수 가산(complex addition)을 고려해 본다.

우선, DFT를 계산하기 위해서는

의 복소수 승산과와

의 복소수 가산이 요구된다. 그런데, 잘 알려진 radix-2 Cooley-Turkey FFT algorithm의 경우, N이 2의 지수승일 때 같은 결과를 얻기 위해서는,

의 복소수 승산과

의 복소수 가산이 필요하다.

예컨대, N이 64일 경우 DFT를 바로 계산한다면 4096의 복소수 승산과 복소수 가산이 필요하며, 똑같은 결과를 얻기 위해서 radix-2 Cooley-Turkey FFT algorithm을 사용한다면 192의 복소수 승산과 384의 복소수 가산이 필요하게 된다. 따라서, FFT 연산은 DFT 연산에 비하여 복소수 승산은 약 1/21로 줄어들었고 복소수 가산은 1/11로 줄어들었다.

상기한 바와 같이, 시스템을 구현하는데 있어서 FFT 알고리즘을 사용하게 되면 DFT를 계산하는데 걸리는 시간을 줄일 수 있고, 계산하기 위해서 필요한 하드웨어의 양을 줄일 수 있다.

그러나, FFT는 N이 2의 지수승일 때만 구현이 가능하다는 제약사항이 따른다.

즉, DFT를 하드웨어로 구현하기에는 하드웨어 크기와 속도에서 제약사항이 따르며, 이를 해결하기 위해 FFT 알고리즘을 사용하여 계산시간과 하드웨어의 양을 줄일 수는 있으나, FFT는 N이 2의 지수승일 때만 구현이 가능하기 때문에, SC-FDMA 시스템에서 랜덤 액세스 신호를 검출하기 위해서 수행해야 하는 소수 길이를 갖는 이산 퓨리에 변환의 고속 처리에는 적용될 수 없다.

도 2는 종래의 소수 길이를 갖는 입력신호에 대해 이산 퓨리에 변환(DFT)을 수행하는 장치의 구성을 나타낸 예시도로서, 랜덤 액세스 신호를 검출하기 위해 DFT를 수행하는 장치의 구성을 나타낸 것이다. 또한, 도 3은 도 2에 도시된 장치에서 소수 길이를 갖는 입력신호에 대해 이산 퓨리에 변환(DFT)을 수행한 결과를 나 타낸 예시도이다.

즉, 랜덤 액세스 신호 검출을 위해, 소수(prime number) 길이를 갖는 입력신호에 대해 DFT를 수행하는 장치의 구성은 도 2에 도시된 바와 같이, M-DFT(11) 및 프리앰블 인덱스 결정부(Preamble Index Decision)(12)를 포함하여 구성되어 있다.

상기 장치에서, 소수인 M의 길이를 갖는 입력신호가 들어오면 M-DFT(11)은 [수학식 1]의 동작을 수행하고 소수인 M의 길이를 갖는 출력신호를 내보낸다.

이때, M-DFT의 출력신호는 도 3과 같다. 즉, M-DFT의 출력신호는 프리앰블 인덱스(preamble index)에 따라서 각각 0, CS, 2*CS...에 최고값을 나타낸다. 여기서 CS는 프리앰블 인덱스에 의해서 결정되는 프리앰블 시퀀스(preamble sequence)의 사이클릭 쉬프트 크기를 나타낸다. 즉, 프리앰블 인덱스에 해당하는 프리앰블 시퀀스들은 각각 CS만큼 차이를 두고 사이클릭 쉬프트되어 있다.

이러한 프리앰블 시퀀스는 송신기의 송신 지연 및 무선 채널의 채널 지연에 의해서 최고값들이 좌측으로 움직이게 된다.

따라서, PRACH 수신기는 (V_MAX*CS)~(M-1)에 존재하는 최고값은 0에서 최고 값을 갖는 프리앰블 인덱스로 검출하고, 1~(CS-1)에 존재하는 최고값은 CS에서 최고 값을 갖는 프리앰블 인덱스로 검출한다. 나머지도 이와 같다.

종래에는 소수 길이를 갖는 입력신호로부터 랜덤 액세스 신호를 검출하기 위해서는, 전술한 바와 같이, M-DFT를 이용하여 PRACH 신호를 처리하였으나, 이 경우, M-DFT(11)의 계산량이 많아지게 됨으로, 시스템 전체적으로 시간이 지연될 뿐만 아니라, 그 구성이 복잡하게 된다.

상기와 같은 문제점을 해결하기 위한 본 발명의 목적은, SC-FDMA 시스템에서 랜덤 액세스 신호를 검출하기 위해 수행되는 이산 퓨리에 변환을 고속 퓨리에 변환을 이용하여 수행할 수 있는, 이산 퓨리에 변환의 고속 처리 장치 및 방법을 제공하는 데 있다.

상기 목적을 달성하기 위하여, 본 발명은 랜덤 액세스 신호 검출을 위한 제1 입력신호가 입력되면, 상기 제1 입력신호를 2의 지수승의 길이를 갖는 제2 입력신호로 변환하여 출력하는 제로 패딩부; 상기 제로 패딩부에서 출력된 상기 제2 입력신호에 대하여 고속 퓨리에 변환을 수행하는 고속 퓨리에 변환부; 및 상기 고속 퓨리에 변환부에서 출력된 출력신호로부터 프리앰블 인덱스를 검출하여 랜덤 액세스 신호가 검출될 수 있도록 하기 위한 프리앰블 인덱스 결정부를 포함하는 이산 퓨리에 변환의 고속 처리 장치를 제공한다.

본 발명의 다른 면에 따라, 소수 길이의 제1 입력신호를 2의 지수승 길이의 제2 입력신호로 변환하는 단계; 상기 제2 입력신호에 대하여 고속 퓨리에 변환을 수행하는 단계; 및 상기 고속 퓨리에 변환을 통해 출력된 출력신호로부터 프리앰블 인덱스를 검출하는 단계를 포함하는 이산 퓨리에 변환의 고속 처리 방법이 제공된다.

본 발명은 SC-FDMA 시스템에서 랜덤 액세스 신호를 검출하기 위해 수행되는 이산 퓨리에 변환을 고속 퓨리에 변환을 이용하여 수행함으로써, 랜덤 액세스 신호의 검출 시간을 줄일 수 있다. 즉, 본 발명은 SC-FDMA 시스템에서 FFT를 활용하여 고속으로 DFT를 수행한 후 최고치를 갖는 인덱스로부터 랜덤 액세스 신호를 검출함으로써, 검출 시간을 줄일 수 있다.

아울러, 본 발명은 SC-FDMA 시스템에서 랜덤 액세스 신호를 검출할 때 하드웨어를 복잡하게 만들고, 또한, 검출하는데 큰 시간 지연을 발생시킬 수 있는 소수 길이를 갖는 DFT 블록을, FFT 블록으로 대체함으로써, 하드웨어를 간단하게 만들 수 있을 뿐만 아니라, 검출하는데 요구되는 시간 지연을 줄일 수 있게 된다.

이하, 첨부된 도면을 참조하여 본 발명이 상세히 설명된다.

도 4는 본 발명에 따른 이산 퓨리에 변환의 고속 처리 장치의 일실시예 구성도로서, 특히 소수(Prime Number) 길이를 갖는 입력신호로부터 랜덤 액세스 신호를 검출하기 위해 FFT를 수행하는 장치의 구성을 나타낸 것이다.

도 5는 도 4에 도시된 장치에서 소수 길이를 갖는 입력신호에 대해 고속 퓨리에 변환(FFT)을 수행한 결과를 나타낸 예시도로서, 특히 도 4에 도시된 고속 퓨리에 변환부(22)에서 고속 퓨리에 변환을 수행한 결과를 나타낸 예시도이다.

종래의 3GPP LTE 이동 통신 시스템의 통신용 모뎀에서 SC-FDMA(Single-Carrier Frequency Division Multiple Access) 방식의 변조기를 살펴보면, 변조기는 비트 스트림 형태의 데이터를 입력받아 변조기의 변조 형태에 따라 심볼로 변환한 다음, 심볼에 DFT를 수행하여 심볼을 주파수 도메인(Domain)의 신호로 변환하였으나, 본 발명은 상기와 같은 이동 통신 시스템에서, 단말기가 전원이 온(ON)된 상태에서 최초로 기지국과 통신을 수행하기 위해, 랜덤 액세스 신호를 검출하는 장치에 적용되는 것으로서, 특히, 소수 길이를 갖는 입력신호에 대한 DFT를 FFT를 활용하여 고속으로 처리한다.

즉, 종래에는 소수 길이를 갖는 입력신호로부터 랜덤 액세스 신호를 검출하기 위해서는 DFT만을 수행하였으나, 본 발명에서는 이러한 DFT를 FFT로 대체하고 있다는 특징을 가지고 있다.

이를 위해, 본 발명에 따른 이산 퓨리에 변환의 고속 처리 장치는 도 4에 도시된 바와 같이 FFT를 수행할 수 있는 고속 퓨리에 변환부(N-FFT)(22)를 포함하고 있다.

즉, 도 4는 본 발명에 따라 2의 장치가 변형된 구조를 나타낸 것으로서, 본 발명에 따른 이산 퓨리에 변환의 고속 처리 장치는, 제로 패딩부(Zero Padding)(21), 고속 퓨리에 변환부(N-FFT)(22) 및 프리앰블 인덱스 결정부(Preamble Index Decision)(23)를 포함하여 구성되어 있다.

우선, 도 4에서, 소수인 M의 길이를 갖는 제1 입력신호는 제로 패딩부(21)를 거치면서 제1 입력신호의 뒷부분에 0이 채워짐으로써 길이가 2의 지수승(N=2ⁿ)을 갖는 제2 입력신호로 변경되어 출력된다.

여기서, 소수(Prime Number)란, 1과 자기 자신만으로 나누어지는 1보다 큰 양의 정수를 말하는 것으로서, 예를 들어, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31,… 등과 같은 숫자를 말하는데, 또한, 소수 M의 길이를 갖는 제1 입력신호의 뒷부분에 0이 채워짐으로써 길이가 2의 지수승(N=2ⁿ)을 갖는 제2 입력신호로 변경된다는 것은, 소수 M 이후에 발생되는 2의 지수승에 해당하는 숫자의 길이(N)를 갖는 제2 입력신호에 대하여 상기 M 다음부터 N까지에 할당된 인덱스 값을 0으로 설정한다는 의미이다.

예를 들어, 소수인 839의 길이(M)를 갖는 제1 입력신호가 제로 패딩부(21)로 입력된 경우, 제로 패딩부는 우선 적으로 839 이후의 2의 지수승을 추출하게 된다. 이 경우 2의 지수승으로는, 1024, 2048, 4096 등이 선택될 수 있다. 여기서, 1024의 길이(N)를 갖는 제2 입력신호가 선택되었다면, 제로 패딩부는, 소수인 839의 길이를 갖는 제1 입력신호에 대하여, 840부터 1024까지의 인덱스를 추가적으로 할당하는 한편, 840부터 1024까지의 인덱스 값으로 0을 할당하게 된다. 즉, 도 1에 도시된 바와 같은 839의 길이를 갖는 제1 입력신호를 살펴보면, 1부터 839까지의 모든 인덱스 값에 대하여 다양한 값들이 설정되어 있는바, 제로 패딩부는 상기에서 임의적으로 추가된 840부터 1024까지의 인덱스 값으로는 0을 할당함으로써, 전체적으로 제1 입력신호와 제2 입력신호의 상태 변화는 없게 된다.

한편, 제로 패딩부에서 출력된 2의 지수승의 길이(N)를 갖는 제2 입력신호는 고속 퓨리에 변환부(22)로 입력으로 들어가서 FFT를 거치게 되며, 이후, 고속 퓨리에 변환부는 길이가 N인 출력신호를 발생시킨다.

여기서, 고속 퓨리에 변환부의 출력신호는 도 5와 같다. 여기서, 종래의 기술에 따른 결과를 나타낸 도 3에서 839-DFT의 출력으로 나타났던 최고값의 위치인 CS, 2*CS...는, 도 5에서와 같이

배의 upper bound 형태로 나타난다.

즉, N>M 임으로, CS<(CSN/M)임을 알 수 있으며, 따라서, 해상도가 증가했음을 알 수 있다.

[표 1]은 839-DFT를 이용할 때와 1024-FFT를 이용할 때의 복소수 승산의 수와 복소수 가산의 수를 비교한 것으로서, 복소수 승산의 경우 약 0.73%로 줄어들었고, 복소수 가산의 경우 약 1.45%로 줄어들었음을 알 수 있다.

	Complex multiplication	Complex addition
839-DFT
1024-FFT
1024-FFT/839-DFT (%)	0.73	1.45

한편, 프리앰블 인덱스 결정부(23)는 고속 퓨리에 변환부(22)에서 출력된 신호로부터 프리앰블 인덱스를 검출한다.

도 6 및 도 7에 도시된 FFT 출력 그래프에서 잘 드러나는 바와 같이, DFT의 출력으로 나타났던 최고값의 위치인 CS, 2*CS...가 FFT의 출력으로는

배의 upper bound 형태로 나타나므로, 이를 기준으로 프리앰블 인덱스를 검출한다.

도 6은 본 발명에 따른 이산 퓨리에 변환의 고속 처리 장치에서 1024-FFT를 수행한 후의 출력값을 나타낸 예시도로서, 도 1에서 사용된 제1 입력신호를 본 발명에 따른 이산 퓨리에 변환의 고속 처리 장치에서 처리한 출력값을 나타낸 예시도이다.

부연하여 설명하면, 도 6은 프리앰블 인덱스가 1일 때 839의 길이(M)를 갖는 제1 입력신호를 1024의 길이(N)를 갖는 제2 입력신호로 변경시킨 후, 고속 퓨리에 변환을 수행한 출력값을 나타낸 것이다. 본 발명에 따른 FFT 처리 후 최고값을 나타내는 인덱스는 DFT 처리 후의 최고값에 비하여

배의 upper bound 형태로 나타나므로 94가 된다.

도 7은 본 발명에 따른 이산 퓨리에 변환의 고속 처리 장치에서 2048-FFT를 수행한 후의 출력값을 나타낸 예시도로서, 도 1에서 사용된 제1 입력신호를 본 발명에 따른 이산 퓨리에 변환의 고속 처리 장치에서 처리한 출력값을 나타낸 예시도이다.

즉, 도 7은 프리앰블 인덱스가 1일 때 2048-FFT의 출력을 나타낸 것으로서, 최고값을 나타내는 인덱스는 188임을 알 수 있다.

부연하여 설명하면, 본 발명은 소수 길이를 갖는 제1 입력신호를 2의 지수승의 길이를 갖는 제2 입력신호로 변경하여 고속 퓨리에 변환을 수행하는 것으로서, 제1 입력신호의 소수 길이 이후에 발생되는 하나의 2의 지수승에 한정하여 제2 입력신호의 길이를 변경하는 것이 아니라, 그 이후에 발생되는 다양한 2의 지수승으로 변경하여 이용할 수도 있다.

한편, 이하에서는 상기한 바와 같은 본 발명에 따른 이산 퓨리에 변환의 고속 처리 장치에서 실행되는 본 발명에 따른 이산 퓨리에 변환의 고속 처리 방법이 설명된다. 이때, 상기에서 설명되는 내용과 중복되는 내용은 간단히 설명된다.

도 8은 본 발명에 따른 이산 퓨리에 변환의 고속 처리 방법의 일실시예 흐름도로서, 도 4에 도시된 바와 같은 이산 퓨리에 변환의 고속 처리 장치에서 실행되는 방법을 나타낸 것이다.

이동 통신 시스템의 단말기 또는 기지국에서 랜덤 액세스 신호 검출을 위한 소수 길이(M)를 갖는 제1 입력신호가 입력되면, 제로 패딩부(21)는 제1 입력신호의 뒷부분에 0을 채움으로써, 제1 입력신호를 길이가 2의 지수승(N=2ⁿ)인 제2 입력신호로 변경시킨다(S802).

즉, 제로 패딩부는 상기한 바와 같이, 소수인 M 이후에 발생되는 2의 지수승에 해당하는 숫자의 길이(N)를 갖는 제1 입력신호에 대하여 상기 M 다음부터 N까지에 할당된 인덱스 값을 0으로 설정한다.

다음으로, 고속 퓨리에 변환부(22)는 제로 패딩부에서 출려된 2의 지수승의 길이(N)를 갖는 제2 입력신호에 대하여 고속 퓨리에 변환을 수행하여, 길이가 N인 출력신호를 발생시킨다(S804). 고속 퓨리에 변환부의 출력신호는 도 5 내지 도 7과 같다.

다음으로, 프리앰블 인덱스 결정부(23)는 고속 퓨리에 변환부에서 출력된 신호로부터 프리앰블 인덱스를 검출하게 된다(S806). 이후, 단말기 또는 기지국은 상기 프리앰블 인덱스를 이용하여 랜덤 액세스 신호를 검출하게 된다.

이상 설명한 내용을 통해 당업자라면 본 발명의 기술사상을 일탈하지 아니하는 범위에서 다양한 변경 및 수정이 가능함을 알 수 있을 것이다. 따라서, 본 발명의 권리 범위는 명세서의 상세한 설명에 기재된 내용으로 한정되는 것이 아니라 특허 청구의 범위에 의해 정하여져야 할 것이다.

도 1은 일반적인 3GPP-LTE 시스템에서 839의 길이를 갖는 이산 퓨리에 변환(DFT)을 수행한 결과를 나타낸 그래프.

도 2는 종래의 소수 길이를 갖는 입력신호에 대해 이산 퓨리에 변환(DFT)을 수행하는 장치의 구성을 나타낸 예시도.

도 3은 도 2에 도시된 장치에서 소수 길이를 갖는 입력신호에 대해 이산 퓨리에 변환(DFT)을 수행한 결과를 나타낸 예시도.

도 4는 본 발명에 따른 이산 퓨리에 변환의 고속 처리 장치의 일실시예 구성도.

도 5는 도 4에 도시된 장치에서 소수 길이를 갖는 입력신호에 대해 고속 퓨리에 변환(FFT)을 수행한 결과를 나타낸 예시도.

도 6은 본 발명에 따른 이산 퓨리에 변환의 고속 처리 장치에서 1024-FFT를 수행한 후의 출력값을 나타낸 예시도.

도 7은 본 발명에 따른 이산 퓨리에 변환의 고속 처리 장치에서 2048-FFT를 수행한 후의 출력값을 나타낸 예시도.

도 8은 본 발명에 따른 이산 퓨리에 변환의 고속 처리 방법의 일실시예 흐름도.

<도면의 주요 부호에 대한 설명>

21 : 제로 패딩부 22 : 고속 퓨리에 변환부(N-FFT)

23 : 프리앰블 인덱스 결정부(Preamble Index Decision)

Claims (9)

1. 소정 길이의 제1 입력신호를 입력받아 2의 지수승의 길이를 갖는 제2 입력신호로 변환하여 출력하는 제로 패딩부;

   상기 제로 패딩부에서 출력된 상기 제2 입력신호에 대하여 고속 퓨리에 변환을 수행하는 고속 퓨리에 변환부; 및

   상기 고속 퓨리에 변환부에서 출력된 출력신호로부터 프리앰블 인덱스를 검출하는 프리앰블 인덱스 결정부

   를 포함하는 이산 퓨리에 변환의 고속 처리 장치.
2. 제1항에 있어서, 상기 제로 패딩부로 입력되는 상기 제1 입력신호는

   소수(Prime Number) 길이를 갖는 것인 이산 퓨리에 변환의 고속 처리 장치.
3. 제2항에 있어서, 상기 제로 패딩부는

   상기 소수 길이의 제1 입력신호를 상기 소수보다 큰 2의 지수승 중 어느 하나의 길이를 갖는 제2 입력신호로 변환하여 출력하는 것인 이산 퓨리에 변환의 고속 처리 장치.
4. 제1항에 있어서, 상기 제로 패딩부는

   상기 제1 입력신호 이후의 부분을 모두 0으로 패딩하여 상기 제2 입력신호를 생성하는 것인 이산 퓨리에 변환의 고속 처리 장치.
5. 제1항에 있어서, 상기 프리앰블 인덱스 결정부는

   상기 출력신호의 최대값이 제1 입력신호를 DFT한 신호의 최대값의 N/M 배가 되는 점에 기초하여 상기 프리앰블 인덱스를 결정하는 것인 이산 퓨리에 변환의 고속 처리 장치(여기서, N은 제1 입력신호의 길이이며, M은 제2 입력신호의 길이).
6. 소수 길이의 제1 입력신호를 2의 지수승 길이의 제2 입력신호로 변환하는 단계;

   상기 제2 입력신호에 대하여 고속 퓨리에 변환을 수행하는 단계; 및

   상기 고속 퓨리에 변환을 통해 출력된 출력신호로부터 프리앰블 인덱스를 검출하는 단계

   를 포함하는 이산 퓨리에 변환의 고속 처리 방법.
7. 제6항에 있어서, 상기 소수 길이의 제1 입력신호를 2의 지수승 길이의 제2 입력신호로 변환하는 단계는,

   상기 소수보다 큰 2의 지수승 중 어느 하나를 선택하는 단계; 및

   제1 입력신호의 뒷부분에 0을 패딩하여 상기 선택된 2의 지수승 길이의 제2 입력신호를 생성하는 단계

   를 포함하는 것인 이산 퓨리에 변환의 고속 처리 방법.
8. 제6항에 있어서, 상기 검출하는 단계는

   상기 제1 입력신호와 상기 제2 입력신호의 길이 비율에 기초하여 상기 출력신호의 최대값 인덱스를 구하고 이로부터 프리앰블 인덱스를 검출하는 것인 이산 퓨리에 변환의 고속 처리 방법.
9. 제6항에 있어서, 상기 검출하는 단계는

   상기 제1 입력신호를 이산 퓨리에 변환 처리한 신호에서의 프리앰블 인덱스가 1일 경우의 최대값 인덱스를 확인하는 단계;

   상기 제2 입력신호의 길이를 상기 제1 입력신호의 길이로 나누어 이동 팩터를 구하는 단계;

   상기 최대값 인덱스를 상기 이동 팩터로 곱하여 상기 출력신호 상의 최대값인덱스를 구하는 단계;

   상기 출력신호 상의 최대값 위치를 검출하는 단계; 및

   상기 검출된 위치에서 상기 최대값 인덱스를 감산하여 프리앰블 인덱스를 검출하는 단계

   를 포함하는 것인 이산 퓨리에 변환의 고속 처리 방법.

Images