KR102526750B1

KR102526750B1 - 푸리에 변환을 수행하는 방법 및 장치

Info

Publication number: KR102526750B1
Application number: KR1020150181077A
Authority: KR
Inventors: 김호정; 김기철; 이홍석
Original assignee: 삼성전자주식회사; 서울시립대학교 산학협력단
Priority date: 2015-12-17
Filing date: 2015-12-17
Publication date: 2023-04-27
Anticipated expiration: 2035-12-17
Also published as: CN107038678B; CN107038678A; US20170178281A1; EP3182375B1; KR20170072646A; US10223763B2; EP3182375A1

Abstract

일 실시 예에 따른 푸리에 변환 방법은 이미지 데이터의 행 방향으로 1D FFT를 수행하여 중간 데이터를 생성하는 단계; 메모리의 서로 다른 뱅크들을 시작 위치로 지정하고, 상기 시작 위치에 상기 중간 데이터를 분할하여 저장하는 단계; 상기 시작 위치부터 상기 중간 데이터를 독출하는 단계; 상기 중간 데이터를 열 방향으로 1D FFT를 수행하여 최종 데이터를 생성하는 단계를 포함한다.

Description

푸리에 변환을 수행하는 방법 및 장치{Apparatus and Method for performing Fourier transform}

푸리에 변환을 수행하는 방법 및 장치에 관한 것이다.

최근 들어 3차원 영상에 관련된 기술이 많이 연구되고 있다. 빛의 진폭과 위상을 동시에 제어할 수 있는 복합 공간 광변조기(Complex Spatial Light Modulator, SLM)를 이용하여 실시간으로 고화질 홀로그램을 구현하는 장치에 대한 연구가 활발히 진행되고 있다.

최근에는 홀로그램 동영상을 재생하기 위해서 컴퓨터 생성 홀로그램(computer generated hologram, CGH)이 사용되고 있으며, 영상 처리 장치는 홀로그램 평면의 각 위치에 대한 홀로그램 값을 연산하는데, 연산량이 매우 방대하다. 즉, 공간상의 한 점을 표현하기 위해서 영상 처리 장치는 1번의 푸리에 변환(Fourier Transform)을 수행해야 하며, 공간의 영상을 표현하기 위해서는 픽셀의 개수만큼의 푸리에 변환을 수행해야만 한다.

TV, 모바일 디바이스 등의 영상 처리 장치는 홀로그램 영상을 재생하기 위해 이미지 데이터를 처리할 수 있다. 이 경우, 영상 처리 장치는 이미지 데이터에 대해 푸리에 변환을 수행하고, 변환된 데이터를 이용하여 영상을 재생할 수 있다.

영상 처리 장치가 푸리에 변환을 수행할 때, 연산량이 많고, 많은 시간이 소요된다. 특히, 모바일 디바이스와 같은 휴대용 디바이스들은 크기에 제한이 있고, 사용가능한 전력(POWER)에도 제한이 있다. 따라서, 푸리에 변환을 수행할 때, 연산량 및 시간을 줄이기 위한 방법들이 요구된다.

푸리에 변환을 수행하는 방법 및 장치를 제공하는데 있다.

또한, 상기 저장하는 단계는, 순차적으로 시프트(shift)된 뱅크를 시작 위치로 지정하고, 상기 시작 위치에 상기 중간 데이터를 저장하는 것을 특징으로 한다.

또한, 상기 저장하는 단계는, 이전 시작 위치의 뱅크와 다른 뱅크를 시작 위치로 지정하여 상기 시작 위치에 상기 중간 데이터를 저장하는 것을 특징으로 한다.

또한, 상기 중간 데이터를 생성하는 단계는 복수의 제1 프로세서들이 상기 이미지 데이터의 각 행들을 1D FFT를 수행하는 것을 특징으로 하고, 상기 저장하는 단계는 상기 제1 프로세서들로부터 출력되는 상기 중간 데이터를 순차적으로 메모리의 뱅크들에 저장하되, 상기 제1 프로세서들이 1D FFT를 수행하는 상기 이미지 데이터의 행이 변경되면, 다른 뱅크를 시작 위치로 지정하여 상기 메모리에 상기 중간 데이터를 저장하는 것을 특징으로 한다.

또한, 상기 중간 데이터는 제1 프로세서들의 수 및 제2 프로세서들의 수에 대응하는 크기를 갖는 윈도우로 구분되고, 상기 저장하는 단계는 상기 중간 데이터의 동일한 행의 윈도우들을 동일한 시작 위치에 저장하는 것을 특징으로 한다.

또한, 상기 저장하는 단계는 상기 윈도우의 행이 변경되면, 변경된 시작 위치에 상기 중간 데이터를 저장하는 것을 특징으로 한다.

또한, 상기 시작 위치는 복수의 제1 프로세서들에 의해 병렬적으로 변환된 중간 데이터가 저장되는 상기 메모리의 주소를 나타내는 것을 특징으로 한다.

또한, 상기 독출 하는 단계는 상기 중간 데이터를 병렬적으로 생성하는 제1 프로세서들의 수에 대응하는 픽셀값을 상기 시작 위치로부터 독출하는 것을 특징으로 한다.

또 다른 일 실시 예에 따른 푸리에 변환 방법은 이미지 데이터의 열 방향으로 1D FFT를 수행하여 중간 데이터를 생성하는 단계; 메모리의 서로 다른 뱅크들을 시작 위치로 지정하고, 상기 시작 위치에 상기 중간 데이터를 분할하여 저장하는 단계; 상기 시작 위치부터 상기 중간 데이터를 독출하는 단계; 상기 중간 데이터를 행 방향으로 1D FFT를 수행하여 최종 데이터를 생성하는 단계를 포함한다.

일 실시 예에 따른 푸리에 변환 장치는 이미지 데이터의 행 방향으로 1D FFT를 수행하여 중간 데이터를 생성하는 제1 코어; 복수의 뱅크들을 포함하고, 상기 뱅크들 중 서로 다른 뱅크들을 시작 위치로 지정하고, 상기 시작 위치에 상기 중간 데이터 분할하여 저장하는 메모리; 상기 시작 위치부터 상기 중간 데이터를 독출하여, 상기 중간 데이터를 열 방향으로 1D FFT를 수행하여 최종 데이터를 생성하는 제2 코어를 포함한다.

또한, 상기 메모리는 순차적으로 시프트(shift)된 뱅크를 시작 위치로 지정하고, 상기 시작 위치에 상기 중간 데이터를 저장하는 것을 특징으로 한다.

또한, 상기 메모리는 이전 시작 위치의 뱅크와 다른 뱅크를 시작 위치로 지정하여 상기 시작 위치에 상기 중간 데이터를 저장하는 것을 특징으로 한다.

또한, 상기 제1 코어는 복수의 제1 프로세서들을 포함하고, 상기 제1 프로세서들이 상기 이미지 데이터의 각 행들을 1D FFT를 수행하고, 상기 메모리는 상기 제1 프로세서들로부터 출력되는 상기 중간 데이터를 순차적으로 메모리의 뱅크들에 저장하되, 상기 제1 프로세서들이 1D FFT를 수행하는 상기 이미지 데이터의 행이 변경되면, 다른 뱅크를 시작 위치로 지정하여 상기 중간 데이터를 저장하는 것을 특징으로 한다.

또한, 상기 제1 코어는 복수의 제1 프로세서들을 포함하고, 상기 제2 코어는 복수의 제2 프로세서들을 포함하고, 상기 중간 데이터는 제1 프로세서들의 수 및 제2 프로세서들의 수에 대응하는 크기를 갖는 윈도우로 구분되고, 상기 메모리는 상기 중간 데이터의 동일한 행의 윈도우들을 동일한 시작 위치에 저장하는 것을 특징으로 한다.

또한, 상기 메모리는 상기 윈도우의 행이 변경되면, 변경된 시작 위치에 상기 중간 데이터를 저장하는 것을 특징으로 한다.

또한, 상기 제2 코어는 상기 중간 데이터를 병렬적으로 생성하는 제1 프로세서들의 수에 대응하는 픽셀값을 상기 시작 위치로부터 독출하는 것을 특징으로 한다.

중간 데이터를 분할하여 메모리의 서로 다른 뱅크에 나누어 저장할 수 있다.

서로 다른 뱅크에 저장된 중간 데이터를 딜레이(delay)없이 독출할 수 있다.

중간 데이터를 저장할 시작 위치를 지정함으로써 어드레스 연산을 줄일 수 있다.

도 1은 이미지 데이터를 처리하는 과정을 나타내는 흐름도이다.
도 2는 데이터를 변환하는 과정을 나타내는 도면이다.
도 3은 또 다른 실시 예에 따른 데이터를 변환하는 과정을 나타내는 도면이다.
도 4는 변환 장치의 일 예를 설명하기 위한 구성도이다.
도 5는 일 실시 예에 따른 푸리에 변환 방법을 나타내는 순서도이다.
도 6을 일 실시 예에 따른 변환 장치를 설명하기 위한 구성도이다.
도 7은 일 실시 예에 따른 데이터를 분할하는 것을 설명하기 위한 도면이다
도 8은 일 실시 예에 따른 중간 데이터를 메모리에 저장하는 방법을 설명하기 위한 도면이다.
도 9는 일 실시 예에 따른 메모리로부터 중간 데이터를 독출하는 방법을 설명하기 위한 도면이다.
도 10은 또 다른 일 실시 예에 따른 푸리에 변환 방법을 나타내는 순서도이다.

이하에서는 도면을 참조하여 본 발명의 실시 예들을 상세히 설명한다.

도 1은 이미지 데이터를 처리하는 과정을 나타내는 흐름도이다. 도 1을 참조하면, 영상 처리 장치는 이미지 데이터를 수신하여, 영상을 출력할 수 있다.

단계 110에서, 영상 처리 장치는 이미지 데이터를 수신한다. 예를 들어, CGH(Computer-Generated Holography)연산에 있어서 layer based 알고리즘을 이미지 데이터에 적용하는 경우, 이미지 데이터는 컬러 데이터, 깊이 데이터 등일 수 있다. 컬러 데이터는 평면마다 복수의 컬러들을 나타내는 데이터일 수 있다. Layer based 알고리즘은 홀로그램의 재생 영역을 깊이를 기준으로 분할하여 분할된 각 평면의 데이터를 처리하는 방법이다. 영상 처리 장치는 분할된 각 평면의 데이터를 푸리에 변환 또는 역 푸리에 변환(Inverse Fourier Transform)하여 홀로그램 영상을 생성할 수 있다.

단계 120에서, 영상 처리 장치는 화질 보정 및 필드 연산을 수행한다. 영상 처리 장치는 이미지 데이터의 화질을 향상시키기 위해 이미지 데이터를 보정할 수 있다.

단계 130에서, 영상 처리 장치는 푸리에 변환(Fourier Transform) 또는 패스트 푸리에 변환(Fast Fourier Transform)을 수행한다. 예를 들어, 영상 처리 장치는 2D 매트릭스 형태의 이미지 데이터를 푸리에 변환할 수 있다. 영상 처리 장치는 2D 푸리에 변환을 위해 1D 푸리에 변환을 2회 수행할 수 있다. 영상 처리 장치는 이미지 데이터를 행 방향으로 1D 푸리에 변환하고, 변환된 이미지 데이터를 열 방향으로 1D 푸리에 변환할 수 있다. 영상 처리 장치는 푸리에 변환을 통해 홀로그래픽 영상을 생성한다.

도 2는 데이터를 변환하는 과정을 나타내는 도면이다. 도 2를 참조하면, 영상 처리 장치 또는 푸리에 변환 장치는 이미지 데이터(210)를 2번 1D FFT를 수행하여 최종 데이터(230)를 생성한다. 예를 들어, 영상 처리 장치는 이미지 데이터(210)를 열 방향으로 1번 1D FFT하여 중간 데이터(220)를 생성하고, 중간 데이터(220)를 행 방향으로 1번 1D FFT 하여 최종 데이터(230)을 생성한다.

도 2에서는 영상 처리 장치가 열 방향으로 1D FFT를 먼저 수행하는 경우를 예를 들어 설명한다. 도 3은 영상 처리 장치가 행 방향으로 1D FFT를 먼저 수행하는 경우를 예를 들어 설명한다.

영상 처리 장치는 이미지 데이터(210)를 열 방향으로 1D FFT를 수행한다. 중간 데이터(220)는 이미지 데이터(210)를 열 방향으로 1D FFT를 수행한 결과를 나타낸다. 이미지 데이터(210)에 표시된 화살표는 영상 처리 장치가 1D FFT를 수행하는 방향을 나타낸다. 중간 데이터(220)에 표시된 직선은 이미지 데이터(210)가 변환된 방향을 나타낸다.

영상 처리 장치는 중간 데이터(220)를 메모리에 저장한다. 영상 처리 장치는 중간 데이터(220)를 메모리의 복수의 뱅크들에 분할하여 저장할 수 있다. 예를 들어, 영상 처리 장치는 중간 데이터(220)를 직사각형 또는 정사각형의 윈도우들로 분할하고, 서로 다른 뱅크를 시작 위치로 지정하여 시작 위치부터 윈도우들에 포함된 중간 데이터(220)를 저장할 수 있다. 영상 처리 장치는 중간 데이터(220)를 저장할 때, 윈도우에 포함된 중간 데이터(220)를 행 방향으로 저장할 수 있다. 중간 데이터를 행 방향으로 저장하는 방법은 도 7내지 9를 통해 자세히 설명한다.

영상 처리 장치가 서로 다른 뱅크에 중간 데이터(220)를 저장하면, 독출할 때 서로 다른 뱅크로부터 중간 데이터(220)를 독출하므로, 뱅크를 활성화 시키는데 필요한 시간으로 인한 지연을 방지할 수 있다.

영상 처리 장치는 저장된 중간 데이터(220)를 독출하여 행 방향으로 1D FFT를 수행한다. 영상 처리 장치는 중간 데이터(220)를 독출할 때, 중간 데이터(220)를 행 방향으로 독출하여 각각의 1D FFT 프로세서로 출력할 수 있다. 동일한 행에 위치한 중간 데이터(220)는 뱅크들의 시작 위치로부터 동일한 지점(또는 픽셀)에 저장되므로, 영상 처리 장치는 동일한 행이 저장된 위치로부터 중간 데이터(220)를 독출함으로써, 중간 데이터(220)를 행 방향으로 독출할 수 있다.

영상 처리 장치는 중간 데이터(220)를 행 방향으로 1D FFT를 수행하여 최종 데이터(230)를 생성한다. 최종 데이터(230)은 이미지 데이터(210)가 열 방향 및 행 방향으로 각각 1D FFT 변환된 데이터이다.

도 3은 또 다른 실시 예에 따른 데이터를 변환하는 과정을 나타내는 도면이다. 도 3을 참조하면, 영상 처리 장치 또는 푸리에 변환 장치는 이미지 데이터(310)를 2번 1D FFT를 수행하여 최종 데이터(330)를 생성한다. 예를 들어, 영상 처리 장치는 이미지 데이터(310)를 행 방향으로 1번 1D FFT하여 중간 데이터(320)를 생성하고, 중간 데이터(320)를 열 방향으로 1번 1D FFT 하여 최종 데이터(330)를 생성한다. 도 2와 도 3은 행과 열의 순서가 바뀐 것이며, 도 2에서 적용된 내용은 도 3에도 동일하게 적용될 수 있다.

도 4는 변환 장치의 일 예를 설명하기 위한 구성도이다. 도 4를 참조하면, 푸리에 변환 장치(400)는 영상 처리 장치의 일 예일 수 있다. 푸리에 변환 장치(400)는 그래픽 처리 장치 또는 데이터 처리 장치이거나 그래픽 처리 장치 또는 데이터 처리 장치 등의 일 부분일 수 있다.

푸리에 변환 장치(400)는 제어부(410), 제1 코어(420), 메모리(430) 및 제2 코어(440)를 포함한다. 도 4에서 푸리에 변환 장치(400)는 2개의 코어들(420 및 440)을 포함하고 있으나, 푸리에 변환 장치(400)는 2개 이상의 코어들을 포함할 수 있다.

제어부(410)는 제1 코어(420), 메모리(430), 제2 코어(440) 등을 제어한다. 제어부(410)는 제1 및 제2 코어들(420 및 440)이 수행할 연산을 지정할 수 있다. 예를 들어, 제어부(410)는 제1 코어(420)가 이미지 데이터(310)를 행 방향으로 1D FFT를 수행하도록 제어하고, 제2 코어(440)가 중간 데이터(320)를 열 방향으로 1D FFT를 수행하도록 제어할 수 있다. 제어부(410)는 중간 데이터(320)를 저장하기 위한 메모리(430)의 위치를 지정할 수도 있다.

제1 코어(420)는 데이터를 푸리에 변환할 수 있다. 예를 들어, 제1 코어(420)는 이미지 데이터(310)를 행 방향으로 1D FFT를 수행하여 중간 데이터(320)를 생성할 수 있다. 제1 코어(420)가 이미지 데이터(310)을 행 방향으로 1D FFT를 수행한다는 것은 이미지 데이터(310)의 행에 포함된 픽셀값들을 1D FFT를 수행한다는 것을 나타낸다.

제1 코어(420)는 중간 데이터(320)를 메모리(430)로 출력할 수 있다. 제1 코어(420)는 1D FFT를 수행한 결과값(즉, 중간 데이터)이 생성될 때마다 결과값을 메모리(430)로 출력할 수 있다.

제1 코어(420)는 복수의 1D FFT 프로세서들을 포함할 수 있다. 1D FFT 프로세서들은 이미지 데이터(310)의 각 행에 대한 1D FFT를 수행할 수 있다. 예를 들어, 제1 코어(420)에 포함된 1D FFT 프로세서의 수는 이미지 데이터(310)의 행의 수의 약수일 수 있다. 예를 들어, 이미지 데이터(310)의 행의 수가 512인 경우, 제1 코어(420)는 8개, 16개, 32개 또는 64개 등의 1D FFT 프로세서들을 포함할 수 있다.

메모리(430)는 중간 데이터(320)를 저장 및 출력할 수 있다. 제1 코어(420)와 제2 코어(440)는 서로 다른 방향(열 방향 또는 행 방향)으로 1D FFT를 수행하므로, 메모리(430)에 중간 데이터(320)를 저장할 때, 제2 코어(440)의 1D FFT 방향에 따라 중간 데이터(320)를 저장할 수 있다.

예를 들어, 도2에서 처럼 제1 코어(420)가 열 방향으로 이미지 데이터(210)를 1D FFT를 수행하고, 제2 코어(440)가 행 방향으로 중간 데이터(220)을 1D FFT를 수행한다면, 메모리(430)는 중간 데이터(220)를 행 방향으로 저장하고, 저장된 중간 데이터(220)를 행 방향으로 제2 코어(440)로 출력할 수 있다.

중간 데이터(220)를 행 방향으로 저장한다는 것은 중간 데이터(220)의 픽셀값들을 메모리(430)의 저장 공간에 순차적으로 저장하되, 순차적으로 저장되는 픽셀값들이 중간 데이터(220)의 동일한 행에 위치하는 것을 의미한다.

반대의 경우, 도 3에서 처럼 제1 코어(420)이 행 방향으로 이미지 데이터(310)을 1D FFT를 수행하고, 제2 코어(440)가 열 방향으로 중간 데이터(320)을 1D FFT를 수행한다면, 메모리(430)는 중간 데이터(320)를 열 방향으로 저장하고, 저장된 중간 데이터(320)를 열 방향으로 제2 코어(440)로 출력할 수 있다.

중간 데이터(320)를 열 방향으로 저장한다는 것은 중간 데이터(320)의 픽셀값들을 메모리(430)의 저장 공간에 순차적으로 저장하되, 순차적으로 저장되는 픽셀값들이 중간 데이터(320)의 동일한 열에 위치하는 것을 나타낸다. 메모리(430)는 동일한 열의 중간 데이터를 서로 다른 뱅크들에 분할하여 저장할 수 있다.

메모리(430)는 DRAM, SDRAM 등일 수 있다. 메모리(430)는 복수의 뱅크들을 포함한다. 다시 말해서, 메모리(430)의 저장 공간은 복수의 뱅크들로 구분된다. 예를 들어 메모리(430)는 8개의 뱅크들을 포함할 수 있고, 메모리(430)는 중간 데이터(320)을 분할하여 뱅크들에 저장할 수 있다. 뱅크의 구조에 관하여는 도 8 및 9를 통해 상세히 설명한다.

제2 코어(440)는 중간 데이터(320)를 푸리에 변환할 수 있다. 예를 들어, 제2 코어(440)는 중간 데이터(320)를 열 방향으로 1D FFT 수행할 수 있다. 만약, 제1 코어(420)가 이미지 데이터(310)를 행 방향으로 1D FFT를 수행하면, 제2 코어(440)는 중간 데이터(320)를 열 방향으로 1D FFT 수행한다.

제2 코어(440)는 복수의 1D FFT 프로세서들을 포함할 수 있다. 1D FFT 프로세서들은 중간 데이터(320)의 각 열에 대한 1D FFT를 수행할 수 있다. 예를 들어, 제2 코어(440)에 포함된 1D FFT 프로세서의 수는 이미지 데이터(310)의 열의 수의 약수일 수 있다. 예를 들어, 이미지 데이터(310)의 열의 수가 1024인 경우, 제2 코어(440)는 8개, 16개, 32개 또는 64개 등의 1D FFT 프로세서들을 포함할 수 있다.

제2 코어(440)는 메모리(430)에 저장된 중간 데이터(320)를 독출할 수 있다. 제2 코어(440)는 메모리(430)의 복수의 뱅크들에 저장된 동일한 열의 픽셀값들을 독출하여 중간 데이터(320)를 열 방향으로 획득할 수 있다.

도 5는 일 실시 예에 따른 푸리에 변환 방법을 나타내는 순서도이다.

단계 510에서, 푸리에 변환 장치(400)는 이미지 데이터(310)를 행 방향으로 1D FFT 수행하여 중간 데이터(320)를 생성한다. 이미지 데이터(310) 및 중간 데이터(320)는 2D 매트릭스 형태일 수 있다. 예를 들어, 이미지 데이터(310) 및 중간 데이터(320)는 1024 X 512 크기의 데이터일 수 있다.

제1 코어(420)는 이미지 데이터(310)의 각 행에 대한 1D FFT를 수행한다. 제1 코어(420)에 포함된 복수의 1D FFT 프로세서들은 이미지 데이터(310)의 각 행에 대해 1D FFT를 수행한다. 이때, 하나의 1D FFT 프로세서는 복수의 행에 대해 1D FFT를 수행할 수 있다. 예를 들어, 1D FFT 프로세서가 32개인 경우, 제1 1D FFT 프로세서는 이미지 데이터(310)의 0번째 행, 32번째 행, 64번째 행 등에 대해 1D FFT를 수행할 수 있다.

단계 520에서, 푸리에 변환 장치(400)는 메모리(430)의 서로 다른 뱅크들을 시작 위치로 지정하고, 시작 위치에 중간 데이터(320)를 분할하여 저장한다. 예를 들어, 푸리에 변환 장치(400)는 순차적으로 시프트된 뱅크를 시작 위치로 지정할 수 있다. 푸리에 변환 장치(400)는 제0 뱅크를 시작 위치로 지정하였으면, 그 다음 시작 위치는 제1 뱅크를 지정하고, 그 다음 시작 위치는 제2 뱅크를 지정할 수 있다. 중간 데이터(320)가 3부분으로 분할되었다면, 푸리에 변환 장치(400)는 제1 부분은 제0 뱅크부터 저장하고, 제2 부분은 제1 뱅크부터 저장하고, 제3 부분은 제2 뱅크부터 저장할 수 있다.

또 다른 예로서, 푸리에 변환 장치(400)는 이전 시작 위치와 다른 뱅크를 시작 위치로 지정할수 있다. 푸리에 변환 장치(400)는 제1 뱅크를 첫번째 시작 위치로 지정하고, 두번째 시작 위치는 제4 뱅크를 지정하고, 세번째 시작 위치는 제7 뱅크를 지정하는 것과 같이 이전 시작 위치의 뱅크와 다른 뱅크를 다음 시작 위치로 지정할 수도 있다.

중간 데이터(320)는 행을 기준으로 분할될 수 있다. 예를 들어, 중간 데이터(320)가 64개의 행들을 포함한다면, 0행 내지 31행이 제1부분이고, 32행 내지 63행이 제2 부분이 된다. 푸리에 변환 장치(400)는 중간 데이터(320)를 열 방향으로 저장할 수 있다. 예를 들어, 중간 데이터(320)의 제1 부분의 제1 열, 제2 부분의 제1열 및 제3 부분의 제1열을 제0 뱅크에 순차적으로 저장할 수 있다.

단계 530에서, 푸리에 변환 장치(400)는 메모리(430)의 시작 위치부터 중간 데이터(320)를 독출한다. 푸리에 변환 장치(400)는 각 시작 위치들로부터 특정된 위치까지 독출하는 과정을 반복하여 중간 데이터(320)를 열 방향으로 독출할 수 있다. 예를 들어, 푸리에 변환 장치(400)는 제0 뱅크에서 1 내지 32 번째 픽셀값들을 독출하고, 제1 뱅크에서 1 내지 32번째 픽셀값들을 독출하고, 제2 뱅크에서 1 내지 32번째 픽셀값들을 독출하여 중간 데이터(320)의 1열을 독출할 수 있다. 또한, 푸리에 변환 장치(400)는 제0 뱅크에서 33 내지 64 번째 픽셀값들을 독출하고, 제1 뱅크에서 33 내지 64번째 픽셀값들을 독출하고, 제2 뱅크에서 33 내지 64번째 픽셀값들을 독출하여 중간 데이터(320)의 2열을 독출할 수 있다. 상기와 같이, 푸리에 변환 장치(400)는 각 시작 위치로부터 동일한 위치의 픽셀값들을 독출함으로써, 중간 데이터(320)를 열 방향으로 독출할 수 있다.

단계 540에서, 푸리에 변환 장치(400)는 중간 데이터(320)를 열 방향으로 1D FFT를 수행하여 최종 데이터(330)를 생성한다. 단계 530에서 푸리에 변환 장치(400)는 메모리(430)로부터 중간 데이터(320)를 열 방향으로 독출하기 때문에, 푸리에 변환 장치(400)는 독출된 데이터를 1D FFT를 수행함으로써, 중간 데이터(320)를 열 방향으로 1D FFT를 수행할 수 있다. 각 열들은 순차적으로 1D FFT 프로세서에 입력되어 변환될 수 있다.

도 6을 일 실시 예에 따른 변환 장치를 설명하기 위한 구성도이다. 도 6을 참조하면, 푸리에 변환 장치(600)는 제1 코어(610), 제1 버퍼(620), 메모리(630), 디먹스(640), 제2 버퍼(650) 및 제2 코어(660)를 포함한다.

도 6에서는 이미지 데이터의 사이즈가 1K X 512 인 경우를 예를 들어 설명한다. 따라서, 제1 코어(610)에 포함된 1D FFT 프로세서들은 1K-Point FFT 프로세서가 되고, 제2 코어(660)에 포함된 1D FFT 프로세서들은 512-Point FFT 프로세서가 된다. 1K-Point FFT 프로세서는 1024개의 픽셀값들에 대한 푸리에 변환을 수행할 수 있으며, 512Point FFT 프로세서는 512개의 픽셀값들에 대한 푸리에 변환을 수행할 수 있다. 입력되는 이미지 데이터에 따라 제1 코어(610) 및 제2 코어(660)에 포함되는 프로세서들의 수는 변경될 수 있다.

제1 코어(610)는 복수의 1K-Point FFT 프로세서들을 포함한다. 1K-Point FFT 프로세서들은 이미지 데이터에 대한 1차원 푸리에 변환을 수행한다. 1K-Point는 이미지 데이터의 1024개의 픽셀값들에 대한 1차원 푸리에 변환을 수행하는 프로세서임을 나타낸다. 예를 들어, 제1 코어(610)는 32개의 1K-Point FFT 프로세서들을 포함할 수 있다. 1K-Point FFT 프로세서 0 는 0번째 프로세서를 나타내고, 1K-Point FFT 프로세서 1 은 1번째 프로세서를 나타내고, 1K-Point FFT 프로세서 31 는 31번째 프로세서를 나타낸다. 1K-Point FFT 프로세서 0 는 이미지 데이터의 0번째 행을 변환할 수 있고, 1K-Point FFT 프로세서 1 는 이미지 데이터의 1번째 행을 변환할 수 있고, 1K-Point FFT 프로세서 31 는 이미지 데이터의 31번째 행을 변환할 수 있다. 1K-Point FFT 프로세서 0 내지 1K-Point FFT 프로세서 31 은 동시에 각 행을 푸리에 변환을 수행할 수 있으며, 중간값을 순차적으로 출력할 수 있다. 중간값은 이미지 데이터를 푸리에 변환하여 생성되는 픽셀값을 나타내며, 중간 데이터의 일부를 나타낸다.

제1 버퍼(620)는 제1 코어(610)로부터 출력되는 중간값을 순차적으로 저장한다. 제1 버퍼(620)는 1K-Point FFT 프로세서 0 내지 1K-Point FFT 프로세서 31 로부터 출력되는 중간값을 저장한다. 예를 들어, 제1 버퍼(620)는 1K-Point FFT 프로세서 0 내지 1K-Point FFT 프로세서 31 로부터 순차적으로 출력되는 32개의 중간값을 저장하고, 메모리(630)로 32개의 중간값을 출력할 수 있다. 1번째로 저장된 32개의 중간값은 중간 데이터의 제1 열의 픽셀값들을 나타낸다. 그 다음으로, 제1 버퍼(620)는 1K-Point FFT 프로세서 0 내지 1K-Point FFT 프로세서 31 로부터 순차적으로 출력되는 32개의 중간값을 저장할 수 있으며, 2번째로 저장된 32개의 중간값은 중간 데이터의 제2 열의 픽셀값들을 나타낸다. 제1 코어(610)로부터 출력되는 중간값의 순서는 도 8에서 상세히 설명한다.

메모리(630)는 중간 데이터를 저장한다. 메모리(630)는 지정된 시작 위치에 제1 버퍼(620)로부터 출력되는 중간값들을 저장할 수 있다. 메모리(630)는 서로 다른 뱅크들에 지정된 시작 위치에 중간값들 저장할 수 있다. 이미지 데이터의 한 행이 변환될 때마다 시작 위치가 변경될 수 있다. 따라서, 이미지 데이터의 한 행에 대한 푸리에 변환이 완료되면 다른 시작 위치에 중간값들이 저장된다. 예를 들어, 1K-Point FFT 프로세서 0 내지 1K-Point FFT 프로세서 31 가 각각 한 행씩 변환을 완료할 때마다 시작 위치가 변경된다. 따라서, 총 512개의 행들이 있고, 총 32개의 1K-Point FFT 프로세서들이 있는 경우, 1K-Point FFT 프로세서 0 가 16개의 행들에 대해 푸리에 변환을 수행하므로, 시작 위치가 16번 지정될 수 있다. 시작 위치가 변경되기 전까지는 지정된 시작 위치부터 순차적으로 중간값들이 저장된다. 이때, 이미지 데이터의 1번째 행부터 32번째 행에 대한 푸리에 변환은 동시에 수행되므로, 중간 데이터의 1번째 행부터 32번째 행에 대한 중간값들은 순차적으로 1번째로 지정된 시작 위치에 저장된다.

메모리(630)는 중간 데이터의 열 방향에 포함된 중간값들을 디먹스(640)로 출력한다. 다시 말해서, 메모리(630)는 중간 데이터를 열 방향으로 출력한다. 동일한 열에 포함된 중간값들은 분할되어 서로 다른 시작 위치에 저장되어 있으므로, 메모리(630)는 서로 다른 시작 위치에 저장된 중간값들을 독출하여 하나의 열에 포함된 중간값들(즉, 중간 데이터의 하나의 열)을 디먹스(640)로 출력할 수 있다. 예를 들어, 메모리(630)는 1번째 내지 16번째 시작 위치로부터 각각 32개의 중간값들(총 16 X 32 = 512)을 독출하여 디먹스(640)로 출력할 수 있다.

디먹스(640)는 하나의 열에 포함된 중간값들을 제2 버퍼(650)로 출력한다. 디먹스(640)는 제2 버퍼에 포함된 버퍼 0 내지 버퍼 31 에 각각 중간 데이터의 하나의 열에 포함된 중간값들을 출력한다. 예를 들어, 디먹스(640)는 버퍼 0 에 중간 데이터의 제1 열을 출력하거나, 제 32열을 출력할 수 있다.

제2 버퍼(650)는 복수의 버퍼들을 포함한다. 예를 들어, 제2 버퍼(650)는 32개의 버퍼들을 포함할 수 있다. 버퍼들의 수는 제2 코어(660)에 포함된 512-Point FFT 프로세서의 수와 대응된다. 다시 말해서, 각각의 버퍼는 512-Point FFT 프로세서와 1:1로 대응된다.

제2 코어(660)는 복수의 512-Point FFT 프로세서들을 포함한다. 예를 들어, 제2 코어(660)는 32개의 512-Point FFT 프로세서들을 포함할 수 있고, 32개의 열을 동시에 푸리에 변환할 수 있다. 512-Point FFT 프로세서들은 중간 데이터에 대한 1차원 푸리에 변환을 수행한다. 512-Point는 중간 데이터의 512개의 픽셀값들에 대한 1차원 푸리에 변환을 수행하는 프로세서임을 나타낸다.

도 7은 일 실시 예에 따른 데이터를 분할하는 것을 설명하기 위한 도면이다. 도 7을 참조하면, 데이터(700)는 복수의 윈도우들로 분할된다.

u0v0 내지 u15v31 은 16x32 개의 윈도우들을 나타낸다. 하나의 윈도우는 MxN개의 픽셀값들을 포함할 수 있으며, 일 예로서 도 7에서와 같이 윈도우는 32x32 의 픽셀값들을 포함할 수 있다. M은 열의 사이즈(가로)를 나타내고, N은 행의 사이즈(세로)를 나타낸다. (0,0) 내지 (511, 1023)은 데이터(700)의 좌표를 나타낸다.

(0,0) 내지 (0, 1023)은 데이터(700)의 0행을 나타낸다. 데이터(700)는 0행 내지 511행까지 총 512개의 행들을 포함한다.

(0,0) 내지 (511, 0)은 데이터(700)의 0열을 나타낸다. 데이터(700)는 0열 내지 1023열까지 총 1024개의 열들을 포함한다.

도 3에서의 이미지 데이터(310), 중간 데이터(320) 및 최종 데이터(330)는 모두 도 7의 데이터(700)와 동일한 형태일 수 있다. 다시 말해서, 이미지 데이터(310)가 (0,0) 내지 (511, 1023)의 픽셀값들을 포함한다면, 중간 데이터(320) 및 최종 데이터(330)도 이미지 데이터(310)와 동일한 형태의 픽셀값들을 포함한다.

도 7에서는 데이터(700)를 32x32 의 윈도우들로 분할하였다. 윈도우의 크기는 메모리(630)의 입력단과 출력단에 연결되는 1D FFT 프로세서들의 수에 따라 결정될 수 있다. 입력단에 연결되는 1D FFT 프로세서들은 제1 코어(610)에 포함되고, 출력단에 연결되는 1D FFT 프로세서들은 제2 코어(660)에 포함된다.

예를 들어, 윈도우의 행의 수는 입력단에 연결되는 1D FFT 프로세서들의 수이고, 윈도우의 열의 수는 출력단에 연결되는 1D FFT 프로세서들의 수이다. 입력단 및 출력단에 연결되는 1D FFT 프로세서들의 수가 32개인 경우, 데이터(700)는 32x32 의 윈도우들로 분할된다. 또 다른 예로서, 출력단에 연결되는 1D FFT 프로세서들의 수가 32개이고, 입력단에 연결되는 1D FFT 프로세서들의 수가 16개인 경우, 데이터(700)는 사이즈가 32x16 인 윈도우들로 분할된다(윈도우의 사이즈는 [가로x세로] 또는 [열의 수 x 행의 수] 로 표시된다).

도 8은 일 실시 예에 따른 중간 데이터를 메모리에 저장하는 방법을 설명하기 위한 도면이다. 도 8을 참조하면, 푸리에 변환 장치(600)는 중간 데이터(320)를 분할하여 메모리(630)의 서로 다른 시작 위치에 저장할 수 있다. 중간 데이터(320)는 도 7에 도시된 바와 같이 복수의 윈도우들로 분할되고, 윈도우들에 포함된 픽셀값들이 메모리(630)에 저장된다.

도 8에서는 Bank0 내지 Bank7이 순차적으로 시작 위치로 지정되는 일 예를 도시하고 있다. 다시 말해서, 1번째 시작 위치로 Bank0가 지정되고, 2번째 시작 위치로 Bank1이 지정되고, 16번째 시작 위치로 Bank7이 지정된다.

반드시 Bank들이 순차적으로 시작 위치로 지정되는 것은 아니며, 이전 시작 위치와 다음 시작 위치가 서로 다른 뱅크로 지정될 수도 있다. 예를 들어, 1번째 시작 위치로 Bank0가 지정되고, 2번째 시작 위치로 Bank5가 지정될 수도 있다.

푸리에 변환 장치(600)는 Bank0를 시작 위치로 지정하고, u0v0 내지 u0v31 에 포함된 픽셀값들을 Bank0부터 Bank7에 순차적으로 기록한다(write). 다시 말해서, 푸리에 변환 장치(600)는 동일한 행의 윈도우들(u0v0 내지 u0v31)을 1번째 시작 위치에 기록한다. u0v0 내지 u0v31 은 동일한 행의 윈도우들의 일 예이다.

푸리에 변환 장치(600)는 각 윈도우에 포함된 픽셀값들을 열 방향으로 메모리(630)에 기록한다. 예를 들어, 도 8의 하단은 Bank0 및 Bank1에 쓰여지는 픽셀값들의 순서를 표시한다. Bank0 는 1번째 시작 위치이고, Bank1은 2번째 시작 위치이다. B(0,0)는 중간 데이터(320)의 픽셀값을 나타낸다. Bank0에는 B(0,0) 내지 B(31,0)가 기록되고, 이어서 B(0,1) 내지 B(31,0)이 기록된다. B(0,0) 내지 B(31,0)는 u0v0의 1열에 포함된 픽셀값들이고, B(0,1) 내지 B(31,0)은 u0v0의 2열에 포함된 픽셀값들이다. 푸리에 변환 장치(600)는 열 방향으로 픽셀값들을 기록하여, 메모리(630)로부터 중간 데이터(320)를 독출할 때 중간 데이터(320)를 열 방향으로 용이하게 독출할 수 있다. 다시 말해서, 메모리(630)에 픽셀값들이 기록되는 방향은 행 방향이나, 픽셀값들이 중간 데이터(320)에서의 위치는 열 방향이다.

만약, u0v0 내지 u0v31 에 포함된 픽셀값들을 기록하는 중, Bank0의 한 행의 저장 공간을 초과하면 Bank1에 픽셀값들을 기록한다. 도 8에서는 u0v0 내지 u0v31 에 포함된 픽셀값들이 Bank0 내지 Bank7의 복수의 행들에 기록된 경우를 예로서 도시하고 있다.

푸리에 변환 장치(600)는 1행에 포함된 윈도우들(u0v0 내지 u0v31)을 모두 기록한 후, 2행에 포함된 윈도우들(u1v0 내지 u1v31)을 2번째 시작 위치에 기록한다. 2번째 시작 위치는 1번째 시작 위치와 서로 다른 뱅크가 지정될 수 있다. 도 8에서는 2번째 시작 위치로 Bank1이 지정된 경우를 예를 들어 설명한다. 푸리에 변환 장치(600)는 2행에 포함된 윈도우들(u1v0 내지 u1v31)의 픽셀값들을 Bank1부터 순차적으로 기록한다.

푸리에 변환 장치(600)는 2행에 포함된 윈도우들(u1v0 내지 u1v31)의 픽셀값들을 열 방향으로 기록한다. 도 8의 하단에서 Bank1을 2번째 시작 위치로 지정하여 2행에 포함된 윈도우들(u1v0 내지 u1v31)의 픽셀값들을 기록하는 순서를 나타내고 있다. 푸리에 변환 장치(600)는 Bank1에 B(32,0) 내지 B(63,0)를 기록하고, B(32,1) 내지 B(63,1)을 기록한다. B(32,0) 내지 B(63,0)는 u1v0 의 1열에 포함된 픽셀값들이고, B(32,1) 내지 B(63,1)은 u1v0 의 2열에 포함된 픽셀값들이다. 푸리에 변환 장치(600)는 u1v31의 32번째 열에 포함된 픽셀값들을 기록하여, 2번째 행에 포함된 윈도우들(u1v0 내지 u1v31)의 픽셀값들을 기록하는 것을 종료한다.

마지막으로, 푸리에 변환 장치(600)는 16행에 포함된 윈도우들(u15v0 내지 u15v31)의 픽셀값들을 16번째 시작 위치인 Bank7부터 기록한다. 푸리에 변환 장치(600)는 마지막 윈도우인 u15v31에 포함된 픽셀값들을 메모리(630)에 기록하여, 중간 데이터(320)를 메모리(630)에 기록하는 것을 종료한다.

도 9는 일 실시 예에 따른 메모리로부터 중간 데이터를 독출하는 방법을 설명하기 위한 도면이다. 도 9를 참조하면, 푸리에 변환 장치(600)는 중간 데이터(320)를 열 방향으로 독출할 수 있다. 예를 들어, 푸리에 변환 장치(600)는 중간 데이터(320)의 1열의 픽셀값들(B(0,0) 내지 B(511,0))을 독출하고, 2열의 픽셀값들(B(0,1) 내지 B(511,1))을 독출할 수 있고, 마지막으로, 1024열의 픽셀값들(B(0,1023) 내지 B(511,1023))을 독출할 수 있다.

푸리에 변환 장치(600)는 시작 위치들로부터 윈도우의 열의 사이즈에 해당하는 픽셀값들을 독출하여 중간 데이터(320)의 하나의 열을 독출할 수 있다. 시작 위치들은 중간 데이터(320)를 메모리(630)에 저장할 때 지정된 위치들을 나타낸다. 윈도우의 열의 사이즈는 중간 데이터(320)를 생성하는 1D FFT 프로세서의 수일 수 있다.

시작 위치가 Ban0부터 Bank7까지 순차적으로 시프트되고, 윈도우의 열의 사이즈가 32인 경우를 예를 들어 설명한다. 푸리에 변환 장치(600)는 Bank0의 시작 위치로부터 32개의 픽셀값들(B(0,0) 내지 B(31,0))을 독출하고, Bank1의 시작 위치로부터 32개의 픽셀값들(B(32,0) 내지 B(63,0))을 독출한다. 푸리에 변환 장치(600)는 시작 위치들의 순서에 따라 픽셀값들을 독출하고, 마지막으로 Bank7의 시작 위치로부터 32개의 픽셀값들(B(480,0) 내지 B(511,0)을 독출한다. 푸리에 변환 장치(600)는 모든 시작 위치들로부터 각각 32개의 픽셀값들을 독출하여 중간 데이터(320)의 1열의 픽셀값들(B(0,0) 내지 B(511,0)을 독출한다.

푸리에 변환 장치(600)는 중간 데이터(320)의 2열의 픽셀값들을 독출하기 위해, Bank0의 시작 위치로부터 33번째부터 64번째 픽셀값들(B(0,1) 내지 B(31,1))을 독출하고, Bank1의 시작 위치로부터 33번째부터 64번째 픽셀값들(B(32,1) 내지 B(63,1))을 독출한다. 푸리에 변환 장치(600)는 시작 위치들의 순서에 따라 픽셀값들을 독출하고, 마지막으로, Bank7의 시작 위치로부터 33번째부터 64번째 픽셀값들(B(480,1) 내지 B(511,1))을 독출한다. 푸리에 변환 장치(600)는 모든 시작 위치들의 33번째 위치부터 각각 32개의 픽셀값들을 독출하여 중간 데이터(320)의 2열의 픽셀값들(B(0,1) 내지 B(511,1)을 독출한다.

상기와 같은 과정을 반복하여, 푸리에 변환 장치(600)는 중간 데이터(320)의 0열부터 1023열까지 총 1024개의 열들을 독출할 수 있다. 푸리에 변환 장치(600)는 각 열들을 독출하여 제2 버퍼(650)로 출력한다.

도 10은 또 다른 일 실시 예에 따른 푸리에 변환 방법을 나타내는 순서도이다. 도 10은 푸리에 변환 장치(400)가 도 2에 도시된 것처럼 이미지 데이터(210)를 열 방향으로 1D FFT를 수행한 후, 중간 데이터(220)를 행 방향으로 1D FFT를 수행하는 방법을 나타낸다.

단계 1010에서, 푸리에 변환 장치(400)는 이미지 데이터(210)를 열 방향으로 1D FFT 수행하여 중간 데이터(220)를 생성한다. 제1 코어(420)는 이미지 데이터(210)의 각 열에 대한 1D FFT를 수행한다. 제1 코어(420)에 포함된 복수의 1D FFT 프로세서들은 이미지 데이터(210)의 각 열에 대해 1D FFT를 수행한다. 이때, 하나의 1D FFT 프로세서는 복수의 열에 대해 1D FFT를 수행할 수 있다. 예를 들어, 1D FFT 프로세서가 32개인 경우, 제1 1D FFT 프로세서는 이미지 데이터(210)의 0번째 열, 32번째 열, 64번째 열 등에 대해 1D FFT를 수행할 수 있다.

단계 1020에서, 푸리에 변환 장치(400)는 메모리(430)의 서로 다른 뱅크들을 시작 위치로 지정하고, 시작 위치에 중간 데이터(220)를 분할하여 저장한다. 예를 들어, 푸리에 변환 장치(400)는 제0 뱅크를 시작 위치로 지정하였으면, 그 다음 시작 위치는 제1 뱅크를 지정하고, 그 다음 시작 위치는 제2 뱅크를 지정할 수 있다. 중간 데이터(220)가 3부분으로 분할되었다면, 푸리에 변환 장치(400)는 제1 부분은 제0 뱅크부터 저장하고, 제2 부분은 제1 뱅크부터 저장하고, 제3 부분은 제2 뱅크부터 저장할 수 있다. 중간 데이터(220)는 열을 기준으로 분할될 수 있다. 예를 들어, 중간 데이터(320)가 64열들을 포함한다면, 0열 내지 31열이 제1부분이고, 32열 내지 63열이 제2 부분이 된다. 푸리에 변환 장치(400)는 중간 데이터(220)를 행 방향으로 저장할 수 있다. 예를 들어, 중간 데이터(220)의 제1 부분의 제1행, 제2 부분의 제1행 및 제3 부분의 제1행을 제0 뱅크에 순차적으로 저장할 수 있다.

단계 1030에서, 푸리에 변환 장치(400)는 메모리(430)의 시작 위치부터 중간 데이터(220)를 독출한다. 푸리에 변환 장치(400)는 각 시작 위치들로부터 특정된 위치까지 독출하는 과정을 반복하여 중간 데이터(220)를 행 방향으로 독출할 수 있다. 예를 들어, 푸리에 변환 장치(400)는 제0 뱅크에서 1 내지 32 번째 픽셀값들을 독출하고, 제1 뱅크에서 1 내지 32번째 픽셀값들을 독출하고, 제2 뱅크에서 1 내지 32번째 픽셀값들을 독출하여 중간 데이터(220)의 1행을 독출할 수 있다. 또한, 푸리에 변환 장치(400)는 제0 뱅크에서 33 내지 64 번째 픽셀값들을 독출하고, 제1 뱅크에서 33 내지 64번째 픽셀값들을 독출하고, 제2 뱅크에서 33 내지 64번째 픽셀값들을 독출하여 중간 데이터(320)의 2행을 독출할 수 있다. 상기와 같이, 푸리에 변환 장치(400)는 각 시작 위치로부터 동일한 위치의 픽셀값들을 독출함으로써, 중간 데이터(320)를 행 방향으로 독출할 수 있다.

단계 1040에서, 푸리에 변환 장치(400)는 중간 데이터(320)를 행 방향으로 1D FFT를 수행하여 최종 데이터(330)를 생성한다. 단계 530에서 푸리에 변환 장치(400)는 메모리(430)로부터 중간 데이터(320)를 행 방향으로 독출하기 때문에, 푸리에 변환 장치(400)는 독출된 데이터를 1D FFT를 수행함으로써, 중간 데이터(320)를 행 방향으로 1D FFT를 수행할 수 있다. 각 행들은 순차적으로 1D FFT 프로세서에 입력되어 변환될 수 있다.

본 실시 예들에 따른 장치는 프로세서, 프로그램 데이터를 저장하고 실행하는 메모리, 디스크 드라이브와 같은 영구 저장부(permanent storage), 외부 장치와 통신하는 통신 포트, 터치 패널, 키(key), 버튼 등과 같은 사용자 인터페이스 장치 등을 포함할 수 있다. 소프트웨어 모듈 또는 알고리즘으로 구현되는 방법들은 상기 프로세서상에서 실행 가능한 컴퓨터가 읽을 수 있는 코드들 또는 프로그램 명령들로서 컴퓨터가 읽을 수 있는 기록 매체 상에 저장될 수 있다. 여기서 컴퓨터가 읽을 수 있는 기록 매체로 마그네틱 저장 매체(예컨대, ROM(read-only memory), RAM(random-access memory), 플로피 디스크, 하드 디스크 등) 및 광학적 판독 매체(예컨대, 시디롬(CD-ROM), 디브이디(DVD: Digital Versatile Disc)) 등이 있다. 컴퓨터가 읽을 수 있는 기록 매체는 네트워크로 연결된 컴퓨터 시스템들에 분산되어, 분산 방식으로 컴퓨터가 판독 가능한 코드가 저장되고 실행될 수 있다. 매체는 컴퓨터에 의해 판독가능하며, 메모리에 저장되고, 프로세서에서 실행될 수 있다.

본 실시 예는 기능적인 블록 구성들 및 다양한 처리 단계들로 나타내어질 수 있다. 이러한 기능 블록들은 특정 기능들을 실행하는 다양한 개수의 하드웨어 또는/및 소프트웨어 구성들로 구현될 수 있다. 예를 들어, 실시 예는 하나 이상의 마이크로프로세서들의 제어 또는 다른 제어 장치들에 의해서 다양한 기능들을 실행할 수 있는, 메모리, 프로세싱, 로직(logic), 룩 업 테이블(look-up table) 등과 같은 직접 회로 구성들을 채용할 수 있다. 구성 요소들이 소프트웨어 프로그래밍 또는 소프트웨어 요소들로 실행될 수 있는 것과 유사하게, 본 실시 예는 데이터 구조, 프로세스들, 루틴들 또는 다른 프로그래밍 구성들의 조합으로 구현되는 다양한 알고리즘을 포함하여, C, C++, 자바(Java), 어셈블러(assembler) 등과 같은 프로그래밍 또는 스크립팅 언어로 구현될 수 있다. 기능적인 측면들은 하나 이상의 프로세서들에서 실행되는 알고리즘으로 구현될 수 있다. 또한, 본 실시 예는 전자적인 환경 설정, 신호 처리, 및/또는 데이터 처리 등을 위하여 종래 기술을 채용할 수 있다. “매커니즘”, “요소”, “수단”, “구성”과 같은 용어는 넓게 사용될 수 있으며, 기계적이고 물리적인 구성들로서 한정되는 것은 아니다. 상기 용어는 프로세서 등과 연계하여 소프트웨어의 일련의 처리들(routines)의 의미를 포함할 수 있다.

본 실시 예에서 설명하는 특정 실행들은 예시들로서, 어떠한 방법으로도 기술적 범위를 한정하는 것은 아니다. 명세서의 간결함을 위하여, 종래 전자적인 구성들, 제어 시스템들, 소프트웨어, 상기 시스템들의 다른 기능적인 측면들의 기재는 생략될 수 있다. 또한, 도면에 도시된 구성 요소들 간의 선들의 연결 또는 연결 부재들은 기능적인 연결 및/또는 물리적 또는 회로적 연결들을 예시적으로 나타낸 것으로서, 실제 장치에서는 대체 가능하거나 추가의 다양한 기능적인 연결, 물리적인 연결, 또는 회로 연결들로서 나타내어 질 수 있다.

본 명세서(특히 특허청구범위에서)에서 “상기”의 용어 및 이와 유사한 지시 용어의 사용은 단수 및 복수 모두에 해당하는 것일 수 있다. 또한, 범위(range)를 기재한 경우 상기 범위에 속하는 개별적인 값을 포함하는 것으로서(이에 반하는 기재가 없다면), 상세한 설명에 상기 범위를 구성하는 각 개별적인 값을 기재한 것과 같다. 마지막으로, 방법을 구성하는 단계들에 대하여 명백하게 순서를 기재하거나 반하는 기재가 없다면, 상기 단계들은 적당한 순서로 행해질 수 있다. 반드시 상기 단계들의 기재 순서에 한정되는 것은 아니다. 모든 예들 또는 예시적인 용어(예들 들어, 등등)의 사용은 단순히 기술적 사상을 상세히 설명하기 위한 것으로서 특허청구범위에 의해 한정되지 않는 이상 상기 예들 또는 예시적인 용어로 인해 범위가 한정되는 것은 아니다. 또한, 당업자는 다양한 수정, 조합 및 변경이 부가된 특허청구범위 또는 그 균등물의 범주 내에서 설계 조건 및 팩터에 따라 구성될 수 있음을 알 수 있다.

400: 프로세서
410: 제어부
420: 제1 코어
430: 메모리
440: 제2 코어

Claims

푸리에 변환하는 방법에 있어서,
2D 매트릭스 형태의 이미지 데이터를 행 방향으로 1D FFT를 수행하여 중간 데이터를 생성하는 단계;
메모리의 서로 다른 뱅크들을 시작 위치로 지정하고, 상기 시작 위치에 상기 1D FFT 수행이 완료된 상기 중간 데이터를 분할하여 저장하는 단계;
상기 시작 위치부터 상기 중간 데이터를 독출하는 단계;
상기 중간 데이터를 열 방향으로 1D FFT를 수행하여 2D 매트릭스 형태의 최종 데이터를 생성하는 단계를 포함하는 푸리에 변환 방법.
제 1 항에 있어서, 상기 저장하는 단계는,
순차적으로 시프트(shift)된 뱅크를 시작 위치로 지정하고, 상기 시작 위치에 상기 중간 데이터를 저장하는 것을 특징으로 하는 푸리에 변환 방법.
제 1 항에 있어서, 상기 저장하는 단계는,
이전 시작 위치의 뱅크와 다른 뱅크를 시작 위치로 지정하여 상기 시작 위치에 상기 중간 데이터를 저장하는 것을 특징으로 하는 푸리에 변환 방법.
제 1 항에 있어서,
상기 중간 데이터를 생성하는 단계는 복수의 제1 프로세서들이 상기 이미지 데이터의 각 행들을 1D FFT를 수행하는 것을 특징으로 하고,
상기 저장하는 단계는 상기 제1 프로세서들로부터 출력되는 상기 중간 데이터를 순차적으로 메모리의 뱅크들에 저장하되, 상기 제1 프로세서들이 1D FFT를 수행하는 상기 이미지 데이터의 행이 변경되면, 다른 뱅크를 시작 위치로 지정하여 상기 메모리에 상기 중간 데이터를 저장하는 것을 특징으로 하는 푸리에 변환 방법.
제 1 항에 있어서,
상기 중간 데이터는 제1 프로세서들의 수 및 제2 프로세서들의 수에 대응하는 크기를 갖는 윈도우로 구분되고,
상기 저장하는 단계는 상기 중간 데이터의 동일한 행의 윈도우들을 동일한 시작 위치에 저장하는 것을 특징으로 하는 푸리에 변환 방법.
제 5 항에 있어서,
상기 저장하는 단계는 상기 윈도우의 행이 변경되면, 변경된 시작 위치에 상기 중간 데이터를 저장하는 것을 특징으로 하는 푸리에 변환 방법.
제 1 항에 있어서,
상기 시작 위치는 복수의 제1 프로세서들에 의해 병렬적으로 변환된 중간 데이터가 저장되는 상기 메모리의 주소를 나타내는 것을 특징으로 하는 푸리에 변환 방법.
제 1 항에 있어서,
상기 독출 하는 단계는 상기 중간 데이터를 병렬적으로 생성하는 제1 프로세서들의 수에 대응하는 픽셀값을 상기 시작 위치로부터 독출하는 것을 특징으로 하는 푸리에 변환 방법.
푸리에 변환하는 방법에 있어서,
2D 매트릭스 형태의 이미지 데이터를 열 방향으로 1D FFT를 수행하여 중간 데이터를 생성하는 단계;
메모리의 서로 다른 뱅크들을 시작 위치로 지정하고, 상기 시작 위치에 상기 1D FFT 수행이 완료된 상기 중간 데이터를 분할하여 저장하는 단계;
상기 시작 위치부터 상기 중간 데이터를 독출하는 단계;
상기 중간 데이터를 행 방향으로 1D FFT를 수행하여 2D 매트릭스 형태의 최종 데이터를 생성하는 단계를 포함하는 푸리에 변환 방법.
2D 매트릭스 형태의 이미지 데이터를 행 방향으로 1D FFT를 수행하여 중간 데이터를 생성하는 제1 코어;
복수의 뱅크들을 포함하고, 상기 뱅크들 중 서로 다른 뱅크들을 시작 위치로 지정하고, 상기 시작 위치에 상기 1D FFT 수행이 완료된 상기 중간 데이터를 분할하여 저장하는 메모리;
상기 시작 위치부터 상기 중간 데이터를 독출하여, 상기 중간 데이터를 열 방향으로 1D FFT를 수행하여 2D 매트릭스 형태의 최종 데이터를 생성하는 제2 코어를 포함하는 푸리에 변환 장치.
제 10 항에 있어서,
상기 메모리는 순차적으로 시프트(shift)된 뱅크를 시작 위치로 지정하고, 상기 시작 위치에 상기 중간 데이터를 저장하는 것을 특징으로 하는 푸리에 변환 장치.
제 10 항에 있어서,
상기 메모리는 이전 시작 위치의 뱅크와 다른 뱅크를 시작 위치로 지정하여 상기 시작 위치에 상기 중간 데이터를 저장하는 것을 특징으로 하는 푸리에 변환 장치.
제 10 항에 있어서,
상기 제1 코어는 복수의 제1 프로세서들을 포함하고,
상기 제1 프로세서들이 상기 이미지 데이터의 각 행들을 1D FFT를 수행하고,
상기 메모리는 상기 제1 프로세서들로부터 출력되는 상기 중간 데이터를 순차적으로 메모리의 뱅크들에 저장하되, 상기 제1 프로세서들이 1D FFT를 수행하는 상기 이미지 데이터의 행이 변경되면, 다른 뱅크를 시작 위치로 지정하여 상기 중간 데이터를 저장하는 것을 특징으로 하는 푸리에 변환 장치.
제 10 항에 있어서,
상기 제1 코어는 복수의 제1 프로세서들을 포함하고,
상기 제2 코어는 복수의 제2 프로세서들을 포함하고,
상기 중간 데이터는 제1 프로세서들의 수 및 제2 프로세서들의 수에 대응하는 크기를 갖는 윈도우로 구분되고,
상기 메모리는 상기 중간 데이터의 동일한 행의 윈도우들을 동일한 시작 위치에 저장하는 것을 특징으로 하는 푸리에 변환 장치.
제 14 항에 있어서,
상기 메모리는 상기 윈도우의 행이 변경되면, 변경된 시작 위치에 상기 중간 데이터를 저장하는 것을 특징으로 하는 푸리에 변환 장치.
제 10 항에 있어서,
상기 시작 위치는 복수의 제1 프로세서들에 의해 병렬적으로 변환된 중간 데이터가 저장되는 상기 메모리의 주소를 나타내는 것을 특징으로 하는 푸리에 변환 장치.
제 10 항에 있어서,
상기 제2 코어는 상기 중간 데이터를 병렬적으로 생성하는 제1 프로세서들의 수에 대응하는 픽셀값을 상기 시작 위치로부터 독출하는 것을 특징으로 하는 푸리에 변환 장치.
제1항 내지 제9항 중에 어느 한 항의 방법을 컴퓨터에서 실행시키기 위한 프로그램을 기록한 컴퓨터로 읽을 수 있는 비일시적인(non-transitory) 기록매체.