Patent Description:
Technologies related to three-dimensional (3D) images have been widely developed. Research on an apparatus for embodying a high image quality hologram in real time by using a complex spatial light modulator (SLM) capable of simultaneously controlling the amplitude and phase of light has been actively conducted.

To reproduce a hologram moving picture, a computer generated hologram (CGH) may be used. An image processing apparatus calculates a hologram value at each position on a hologram plane, and thus, a computational amount is quite huge. In other words, to represent one point in space, the image processing apparatus performs a single Fourier transform. Accordingly, in order to represent an image in space, the Fourier transform should be performed as many times as the number of pixels.

An image processing apparatus such as a television (TV), a mobile device, etc. may process image data to reproduce a hologram image. In this case, the image processing apparatus may perform a Fourier transform on the image data and reproduce an image using transformed data.

When the image processing apparatus performs the Fourier transform, a computational amount is relatively large and much time is needed. In particular, portable devices, such as mobile devices, are limited in their size and usable power. Accordingly, there is a demand for a method of reducing a computational amount and time for performing a Fourier transform.

The document <CIT> provides background information relative to a two-dimensional fast Fourier, transform calculation method and apparatus.

Exemplary embodiments provide an apparatus and method for performing a Fourier transform.

According to an aspect of the invention, there is provided a method for performing a Fourier transform according to claim <NUM>.

Embodiments may be applied to a CGH algorithm of a holographic display. Further, proposed concepts may be embodied as a form of a chip and applied to a holographic display of a mobile phone/television.

When reading one column of the intermediate result values using a proposed embodiment, since the data is sequentially stored in several banks, the reading may be performed while changing the banks. Since the starting bank for each column is different, no delay may then be caused when changing the column.

Proposed embodiments may be used in order to efficiently write and read the FFT data in SDRAM by using a multiple 1D-FFT processor.

By way of example, the intermediate FFT data value from the <NUM>-point FFT may first be written in the SDRAM in the row major order. When writing, one window of the FFT data may be mapped in one row of one bank, and when the window writing is finished, the next window may then be written and mapped in the next bank, not the presently written bank, in the same manner. In this way, all the windows may be mapped in each different bank. After writings of various windows composing one row of the FFT data matrix are finished, the starting point of the next row writing mapping may not be the bank in which the first writing mapping is performed, but the next bank. That is, the banks in which the row writing mapping of the FFT data matrix is performed may be shifted one by one.

In the designating the at least two different banks of the memory as the start positions, sequentially shifted banks may be designated as the start positions.

In the performing the first 1D FFT, for each respective row of the image data, a corresponding one from among a plurality of first processors performs a respective 1D FFT.

The intermediate data may be divided into a plurality of windows, each window having a size that corresponds to the number of first processors and the number of second processors, and in the designating the at least two different banks of the memory as the start positions and the dividing and storing the intermediate data at the start positions, the intermediate data included in the plurality of windows in the same row may be sequentially stored from same start positions.

In the designating the at least two different banks of the memory as the start positions and the dividing and storing the intermediate data at the start positions, when a row is changed, the subsequently generated intermediate data may be stored at a changed start position.

The start position may indicate an address of the memory at which intermediate data transformed in parallel by the plurality of first processors is stored.

In the reading out the intermediate data, a pixel value that corresponds to a number of a plurality of first processors that generate the intermediate data in parallel may be read out at a first start position.

According to another aspect of the invention, there is provided a Fourier transform apparatus.

The memory may be further configured to designate sequentially shifted banks as start positions.

The first core includes a plurality of first processors, and each respective one from among the plurality of first processors is configured to perform a respective 1D FFT with respect to a corresponding row of the image data.

The first core includes a plurality of first processors, the second core includes a plurality of second processors, the intermediate data may be divided into a plurality of windows, each window having a respective size that corresponds to a number of the plurality of first processors and a number of the plurality of second processors, and the memory may be further configured to store each of the plurality of windows in the same row of the intermediate data at same start positions.

When a row of the window is changed, the memory may be further configured to store the subsequently generated intermediate data at a changed start position.

The second core may be further configured to read out a pixel value that corresponds to the number of first processors that generate the intermediate data in parallel, from a first start position.

The above and/or other aspects will become apparent and more readily appreciated from the following description of exemplary embodiments, taken in conjunction with the accompanying drawings in which:.

Reference will now be made in detail to exemplary embodiments, examples of which are illustrated in the accompanying drawings, wherein like reference numerals refer to like elements throughout. Also, the size of each layer illustrated in the drawings may be exaggerated for convenience of explanation and clarity. In this regard, the present exemplary embodiments may have different forms and should not be construed as being limited to the descriptions set forth herein. Accordingly, the exemplary embodiments are merely described below, by referring to the figures, to explain aspects of the present description. In a layer structure, when a constituent element is disposed "above" or "on" to another constituent element, the constituent element may be only directly on the other constituent element or above the other constituent elements in a non-contact manner.

<FIG> is a flowchart of a process of processing image data. Referring to <FIG>, an image processing apparatus may receive image data and output an image.

In operation <NUM>, the image processing apparatus receives image data. For example, in a computer-generated holography (CGH) operation, when a layer-based algorithm is applied to image data, the image data may include color data and/or depth data. The color data may be data indicating a plurality of colors for each plane. The layer-based algorithm is a method of dividing a reproduction area of a hologram based on a depth and processing data of each divided plane. The image processing apparatus may generate a hologram image by performing a Fourier transform or an inverse Fourier transform on data of each divided plane.

In operation <NUM>, the image processing apparatus performs image quality correction and field calculation. The image processing apparatus may correct image data in order to improve image quality of the image data.

In operation <NUM>, the image processing apparatus performs the Fourier transform or a fast Fourier transform (FFT). For example, the image processing apparatus may perform the Fourier transform on image data in a two-dimensional (2D) matrix form. The image processing apparatus may perform a one-dimensional (1D) Fourier transform twice, thereby effectively performing a 2D Fourier transform. The image processing apparatus may perform the 1D Fourier transform on image data in a row direction (i.e., on a row-by-row basis) and the 1D Fourier transform on the transformed image data in a column direction (i.e., on a column-by-column The image processing apparatus generates a holographic image as a result of the execution of the Fourier transform.

In operation <NUM>, the image processing apparatus performs pixel encoding. The image processing apparatus generates data to be input to a screen via pixel encoding.

In operation <NUM>, the image processing apparatus outputs an image to an image display apparatus.

The image processing apparatus may include a plurality of cores that are capable of performing the Fourier transform in parallel on image data. For example, the image processing apparatus may assign image data of each plane to the cores, and the image data assigned to the cores are Fourier transformed.

<FIG> illustrates a process of transforming data. Referring to <FIG>, the image processing apparatus or a Fourier transform apparatus generates final data <NUM> by performing a 1D FFT twice on image data <NUM>. For example, the image processing apparatus performs a first 1D FFT on the image data <NUM> in the column direction (i.e., on a column-by-column basis) in order to generate intermediate data <NUM>, and then performs a second 1D FFT on the intermediate data <NUM> in the row direction (i.e., on a row-by-row basis) in order to generate the final data <NUM>.

In <FIG>, for example, a case in which the image processing apparatus performs the first 1D FFT in the column direction is described. In <FIG>, for example, a case in which the image processing apparatus performs the first 1D FFT in the row direction is described.

Referring to <FIG>, the image processing apparatus performs a 1D FFT on the image data <NUM> in the column direction, i.e., column by column. The intermediate data <NUM> is obtained as a result of performing a 1D FFT on the image data <NUM> in the column direction. Arrows marked on the image data <NUM> indicate directions in which the image processing apparatus performs a 1D FFT. Straight lines marked on the intermediate data <NUM> indicate directions in which the image data <NUM> is transformed.

The image processing apparatus stores the intermediate data <NUM> in a memory (not shown). The image processing apparatus may store the intermediate data <NUM> in a plurality of banks of the memory by dividing the intermediate data <NUM>. For example, the image processing apparatus may divide the intermediate data <NUM> into rectangular or square windows, and then store the intermediate data <NUM> included in the windows from a start position by designating different banks as respective start positions. When storing the intermediate data <NUM>, the image processing apparatus may store the intermediate data <NUM> included in the window in the row direction. A method of storing the intermediate data <NUM> in the row direction is described in detail with reference to <FIG>, <FIG>, and <FIG>.

When the image processing apparatus stores the intermediate data <NUM> in different banks, in the reading out of data, the intermediate data <NUM> is read out from the different banks so that a delay which might otherwise be caused by a time required for activating the banks may be prevented.

The image processing apparatus may perform a 1D FFT in the row direction, i.e., row by row, by reading out the intermediate data <NUM> that is stored. When reading out the intermediate data <NUM>, the image processing apparatus may read out the intermediate data <NUM> in the row direction and output the intermediate data <NUM> that is read to each 1D FFT processor. Since the intermediate data <NUM> located in the same row is stored at the same point or pixel with respect to the start position of the respective designated banks, the image processing apparatus may read out the intermediate data <NUM> in the row direction as the intermediate data <NUM> is read out from the position where the intermediate data <NUM> located in the same row is stored. In particular, the image processing apparatus reads out the pixel value from the same position of the respective designated banks.

The image processing apparatus performs a 1D FFT on the intermediate data <NUM> in the row direction, i.e., row by row, thereby generating the final data <NUM>. The final data <NUM> is data obtained as the image data <NUM> is 1D FFT-transformed sequentially, first in the column direction and second in the row direction.

<FIG> illustrates a process of transforming data, according to another exemplary embodiment. Referring to <FIG>, the image processing apparatus or the Fourier transform apparatus generate final data <NUM> by performing a 1D FFT twice on image data <NUM>. For example, the image processing apparatus generates intermediate data <NUM> by performing a first 1D FFT on image data <NUM> in the row direction, i.e., on a row-by-row basis, and generates the final data <NUM> by performing a second 1D FFT on the intermediate data <NUM> in the column direction, i.e., on a column-by-column basis. In <FIG> and <FIG>, the order of a column and a row is switched and the description presented in <FIG> may be identically applied to the description of <FIG>.

<FIG> is a block diagram of a structure of a transform apparatus. Referring to <FIG>, a Fourier transform apparatus <NUM> may be an example of the image processing apparatus. The Fourier transform apparatus <NUM> may be a graphic processing apparatus or a data processing apparatus, or a part of the graphic processing apparatus or data processing apparatus.

The Fourier transform apparatus <NUM> may include a controller <NUM>, a first core <NUM>, a memory <NUM>, and a second core <NUM>. Although <FIG> illustrates that the Fourier transform apparatus <NUM> includes two cores, that is, the first and second cores <NUM> and <NUM>, the Fourier transform apparatus <NUM> may include three or more cores.

The controller <NUM> controls the first core <NUM>, the memory <NUM>, and the second core <NUM>. The controller <NUM> may designate operations to be performed by the first and second cores <NUM> and <NUM>. For example, the controller <NUM> may control the first core <NUM> to perform a 1D FFT on the image data <NUM> in the row direction and the second core <NUM> to perform a 1D FFT on the intermediate data <NUM> in the column direction. The controller <NUM> may designate a position in the memory <NUM> at which the intermediate data <NUM> is stored.

The first core <NUM> may perform the Fourier transform on data. For example, the first core <NUM> may generate the intermediate data <NUM> by performing a 1D FFT on the image data <NUM> in the row direction. The performance of a 1D FFT on the image data <NUM> in the row direction by the first core <NUM> indicates performing a 1D FFT on pixel values included in respective columns of the image data <NUM>.

The first core <NUM> may output the intermediate data <NUM> to the memory <NUM>. Whenever a result value of performing a 1D FFT, that is, the intermediate data, is generated, the first core <NUM> may output the result value to the memory <NUM>.

The first core <NUM> may include a plurality of 1D FFT processors. Each respective 1D FFT processor may perform a respective 1D FFT on a corresponding column of the image data <NUM>. For example, the number of 1D FFT processors including the first core <NUM> may be a divisor of the number of the columns of the image data <NUM>. For example, when the number of the columns of the image data <NUM> is <NUM>, the first core <NUM> may include eight (<NUM>), sixteen (<NUM>), thirty-two (<NUM>), or sixty-four (<NUM>) 1D FFT processors.

The memory <NUM> may store and output the intermediate data <NUM>. Since the first core <NUM> and the second core <NUM> perform a 1D FFT in different directions, e.g., in the column direction and in the row direction, when the intermediate data <NUM> is stored in the memory <NUM>, the intermediate data <NUM> may be stored in a direction in which the second core <NUM> performs a 1D FFT.

For example, as illustrated in <FIG>, when the first core <NUM> performs a 1D FFT on the image data <NUM> in the column direction and the second core <NUM> performs a 1D FFT on the intermediate data <NUM> in the row direction, the memory <NUM> may store the intermediate data <NUM> in the row direction and output the stored intermediate data <NUM> to the second core <NUM> in the row direction.

The storing of the intermediate data <NUM> in the row direction signifies that the pixel values of the intermediate data <NUM> are sequentially stored in a storage space of the memory <NUM> and the sequentially stored pixel values are located in the same column of the intermediate data <NUM>.

In contrast, as illustrated in <FIG>, when the first core <NUM> performs a 1D FFT on the image data <NUM> in the row direction and the second core <NUM> performs a 1D FFT on the intermediate data <NUM> in the column direction, the memory <NUM> may store the intermediate data <NUM> in the column direction and output the stored intermediate data <NUM> to the second core <NUM> in the column direction.

The storing the intermediate data <NUM> in the column direction signifies that the pixel values of the intermediate data <NUM> are sequentially stored in a storage space of the memory <NUM> and the sequentially stored pixel values are located in the same column of the intermediate data <NUM>. The memory <NUM> may divide the intermediate data <NUM> in the same column to be stored in different banks.

The memory <NUM> may be dynamic random access memory (DRAM) or synchronous DRAM (SDRAM). The memory <NUM> may include a plurality of banks. In particular, the storage space of the memory <NUM> is sectioned into a plurality of banks. For example, the memory <NUM> may include eight (<NUM>) banks, and the memory <NUM> may divide the intermediate data <NUM> and store divided intermediated data in the respective banks. A structure of the banks is described in detail with reference to <FIG> and <FIG>.

The second core <NUM> may perform the Fourier transform on the intermediate data <NUM>. For example, the second core <NUM> may perform a 1D FFT on the intermediate data <NUM> in the column direction. If the first core <NUM> performs a 1D FFT on the image data <NUM> in the row direction, the second core <NUM> performs a 1D FFT on the intermediate data <NUM> in the column direction.

The second core <NUM> may include a plurality of 1D FFT processors. Each respective 1D FFT processor may perform a respective 1D FFT on a corresponding column of the intermediate data <NUM>. For example, the number of the 1D FFT processors included in the second core <NUM> may be a divisor of the number of the columns of the image data <NUM>. For example, when the number of the columns of the image data <NUM> is <NUM>, the second core <NUM> may include eight (<NUM>), sixteen (<NUM>), thirty-two (<NUM>), or sixty-four (<NUM>) 1D FFT processors.

The second core <NUM> may read out the intermediate data <NUM> stored in the memory <NUM>. The second core <NUM> may obtain the intermediate data <NUM> in the column direction by reading out the pixel values of the same column stored in the respective banks of the memory <NUM>.

<FIG> is a flowchart for explaining a Fourier transform method, according to an exemplary embodiment.

In operation <NUM>, the Fourier transform apparatus <NUM> performs a 1D FFT on the image data <NUM> in the row direction in order to generate the intermediate data <NUM>. The image data <NUM> and the intermediate data <NUM> may be arranged in the form of a 2D matrix. For example, the image data <NUM> and the intermediate data <NUM> may be data having a size of <NUM>×<NUM>.

The first core <NUM> performs a 1D FFT with respect to each row of the image data <NUM>. The 1D FFT processors included in the first core <NUM> perform respective 1D FFTs with respect to the corresponding rows of the image data <NUM>. In this state, one 1D FFT processor may perform a 1D FFT with respect to a plurality of rows. For example, when there are thirty-two (<NUM>) 1D FFT processors, a first 1D FFT processor may perform a 1D FFT with respect to the <NUM>th row, the <NUM>nd row, the <NUM>th row, etc. of the image data <NUM>.

In operation <NUM>, the Fourier transform apparatus <NUM> designates different banks of the memory <NUM> as respective start positions, and divides and stores the intermediate data <NUM> at the respective start positions. For example, the Fourier transform apparatus <NUM> may designate sequentially shifted banks as start positions. If the Fourier transform apparatus <NUM> designates the <NUM>th bank as a start position, the <NUM>st bank may be designated as a next start position, and the <NUM>nd bank may be designated as a further next start position. If the intermediate data <NUM> is divided into three parts, the Fourier transform apparatus <NUM> may store a first part from the <NUM>th bank, a second part from the <NUM>st bank, and a third part from the <NUM>nd bank.

In another example, the Fourier transform apparatus <NUM> may designate a bank that is different from bank that corresponds to a previous start position as a start position. The Fourier transform apparatus <NUM> may designate a particular bank that is different from the bank of a previous start position as a next start position, like designation of the <NUM>st bank as the first start position, the <NUM>th bank as the second start position, and the <NUM>th bank as the third start position.

The intermediate data <NUM> may be divided based on a row in which the data is located. For example, if the intermediate data <NUM> includes sixty-four (<NUM>) rows, the <NUM>th to <NUM>st rows form a first part and the <NUM>nd to <NUM>rd rows form a second part. The Fourier transform apparatus <NUM> may store the intermediate data <NUM> in the column direction. For example, the first column of the first part, the first column of the second part, and the first column of the third part of the intermediate data <NUM> may be sequentially stored in the <NUM>th bank.

In operation <NUM>, the Fourier transform apparatus <NUM> reads out the intermediate data <NUM> from the respective start positions of the memory <NUM>. The Fourier transform apparatus <NUM> may read out the intermediate data <NUM> in the column direction by repeating the process of reading out the intermediate data <NUM> from each start position to a particular position. For example, the Fourier transform apparatus <NUM> may read out the <NUM>st to <NUM>nd pixel values from the <NUM>th bank, the <NUM>st to <NUM>nd pixel values from the <NUM>st bank, and the <NUM>st to <NUM>nd pixel values from the <NUM>nd bank, thereby reading out the first column of the intermediate data <NUM>. Furthermore, the Fourier transform apparatus <NUM> reads out the <NUM>rd to <NUM>th pixel values from the <NUM>th bank, the <NUM>rd to <NUM>th pixel values from the <NUM>st bank, and the <NUM>rd to <NUM>th pixel values from the <NUM>nd bank, thereby reading out the second column of the intermediate data <NUM>. As described above, the Fourier transform apparatus <NUM> may read out the intermediate data <NUM> in the column direction by reading out the pixel values at the same relative position from the respective start positions.

In operation <NUM>, the Fourier transform apparatus <NUM> generates the final data <NUM> by performing a 1D FFT on the intermediate data <NUM> in the column direction. Since in the operation <NUM> the Fourier transform apparatus <NUM> reads out the intermediate data <NUM> from the memory <NUM> in the column direction, the Fourier transform apparatus <NUM> may perform a 1D FFT on the intermediate data <NUM> in the column direction by performing a 1D FFT on the read-out data. The respective columns may be transformed by sequentially being input into the 1D FFT processor.

<FIG> is a block diagram for explaining a Fourier transform apparatus <NUM>, according to an exemplary embodiment. Referring to <FIG>, the Fourier transform apparatus <NUM> may include a first core <NUM>, a first buffer <NUM>, a memory <NUM>, a demultiplexer <NUM>, a second buffer <NUM>, and a second core <NUM>.

In <FIG>, a case in which the size of image data is, for example, <NUM>×<NUM>, is described. Accordingly, 1D FFT processors included in the first core <NUM> are a <NUM>-Point FFT processor, and 1D FFT processors included in the second core <NUM> are a <NUM>-Point FFT processor. The <NUM>-Point FFT processor may perform the Fourier transform with respect to one thousand twenty-four (<NUM>) pixel values, and the <NUM>-Point FFT processor may perform the Fourier transform with respect to five hundred and twelve (<NUM>) pixel values. The number of processors included in the first core <NUM> and the second core <NUM> may vary according to the input image data.

The first core <NUM> includes a plurality of <NUM>-Point FFT processors. The <NUM>-Point FFT processors perform respective 1D Fourier transforms on image data. The term "<NUM>-Point" denotes that a processor performs a 1D Fourier transform on one thousand twenty-four (<NUM>) pixel values of the image data. For example, the first core <NUM> may include thirty-two (<NUM>) <NUM>-Point FFT processors. A <NUM>-Point FFT processor <NUM> denotes the <NUM>th processor, a <NUM>-Point FFT processor <NUM> denotes the <NUM>st processor, and a <NUM>-Point FFT processor <NUM> denotes the <NUM>st processor. The <NUM>-Point FFT processor <NUM> may transform the <NUM>th row of the image data, the <NUM>-Point FFT processor <NUM> may transform the first row of the image data, and the <NUM>-Point FFT processor <NUM> may transform the <NUM>st row of the image data. The <NUM>-Point FFT processor <NUM> to the <NUM>-Point FFT processor <NUM> may simultaneously perform Fourier transforms with respect to the respective rows and sequentially output intermediate values. The intermediate value indicates a pixel value generated by performing the Fourier transform on the image data, and represents a portion of the intermediate data.

The first buffer <NUM> sequentially stores the intermediate values output from the first core <NUM>. The first buffer <NUM> stores the intermediate value output from the <NUM>-Point FFT processor <NUM> to the <NUM>-Point FFT processor <NUM>. For example, the first buffer <NUM> may store thirty-two (<NUM>) intermediate values sequentially output from the <NUM>-Point FFT processor <NUM> to the <NUM>-Point FFT processor <NUM>, and output thirty-two (<NUM>) intermediate values to the memory <NUM>. The thirty-two (<NUM>) intermediate values that are primarily stored represent the pixel values of the first column of the intermediate data. Next, the first buffer <NUM> may store the thirty-two (<NUM>) intermediate values that are sequentially output from the <NUM>-Point FFT processor <NUM> to the <NUM>-Point FFT processor <NUM>, and the thirty-two (<NUM>) intermediate values that are secondly stored represent the pixel values of the second column of the intermediate data. The order of the intermediate values output from the first core <NUM> is described in detail with reference to <FIG>.

The memory <NUM> stores the intermediate data. The memory <NUM> may store respective intermediate values output from the first buffer <NUM> at designated start positions. The memory <NUM> may store respective intermediate values at respective start positions designated in different corresponding banks. Whenever one row of image data is transformed, the start position may be changed. Accordingly, when the Fourier transform with respect to one row of image data is completed, intermediate values are stored at different start positions. For example, whenever the <NUM>-Point FFT processor <NUM> to the <NUM>-Point FFT processor <NUM> respectively complete a transform of a single row, the start position is changed. Accordingly, when there are a total of five hundred and twelve (<NUM>) rows and a total of thirty-two (<NUM>) <NUM>-Point FFT processors, as the <NUM>-Point FFT processor <NUM> performs the Fourier transform with respect to sixteen (<NUM>) rows, the start position may be designated sixteen (<NUM>) times. The intermediate values are sequentially stored from the designated start position until the start position is changed. In this state, since the Fourier transform is performed with respect to the <NUM>st row to <NUM>nd row of the image data at the same time, the intermediate values with respect to the <NUM>st row to <NUM>nd row of the image data are sequentially stored at the primarily designated start positions.

The memory <NUM> outputs the intermediate values of the same column to the demultiplexer <NUM>. In other words, the memory <NUM> outputs the intermediate data in the column direction, i.e., on a column-by-column basis. Since the intermediate values of the same column are divided and stored at different start positions, the memory <NUM> may read out the respective intermediate values stored at different start positions and output the intermediate values included in one column, that is, one column of the intermediate data, to the demultiplexer <NUM>. For example, the memory <NUM> may read out thirty-two (<NUM>) intermediate values (a total of <NUM> ×<NUM> = <NUM>) respectively from the first to sixteenth start position and output read-out intermediate values to the demultiplexer <NUM>.

The demultiplexer <NUM> outputs the intermediate values included in one column to the second buffer <NUM>. The demultiplexer <NUM> outputs the intermediate values included in one column of the intermediate data to each of a buffer <NUM> to a buffer <NUM> included in the second buffer. For example, the demultiplexer <NUM> may output the intermediate data of the first or thirty-second column to the buffer <NUM>.

The second buffer <NUM> may include a plurality of buffers. For example, the second buffer <NUM> may include thirty-two (<NUM>) buffers. The number of buffers corresponds to the number of the <NUM>-Point FFT processors included in the second core <NUM>. In other words, each buffer corresponds to a respective <NUM>-Point FFT processor in a one-buffer-to-one-processor correspondence.

The second core <NUM> may include a plurality of <NUM>-Point FFT processors. For example, the second core <NUM> may include thirty-two (<NUM>) <NUM>-Point FFT processors and simultaneously perform the Fourier transform with respect to thirty-two (<NUM>) columns. The <NUM>-Point FFT processors perform a 1D Fourier transform on the intermediate data. The term "<NUM>-Point" denotes that a processor performs the 1D Fourier transform on five hundred and twelve (<NUM>) pixel values of the intermediate data.

<FIG> illustrates dividing data, according to an exemplary embodiment. Referring to <FIG>, data <NUM> is divided into a plurality of windows.

"u0v0" to "u15v31" indicate windows of <NUM>×<NUM>. i.e., <NUM> rows of windows and <NUM> columns of windows. One window may include pixel values of M×N. As an example, as illustrated in <FIG>, each window may include pixel values of <NUM>×<NUM>. "M" denotes a size of a row (horizontal), whereas "N" denotes a size of a column (vertical). (<NUM>,<NUM>) to (<NUM>, <NUM>) indicate coordinates of the data <NUM>.

(<NUM>, <NUM>) to (<NUM>, <NUM>) indicates the <NUM>th row of the data <NUM>. The data <NUM> may include a total of five hundred and twelve (<NUM>) rows from the <NUM>th row to the <NUM>th row. (<NUM>, <NUM>) to (<NUM>, <NUM>) indicates the <NUM>th column of the data <NUM>. The data <NUM> may include a total of one thousand twenty-four (<NUM>) columns from the <NUM>th column to the <NUM>rd column.

The image data <NUM>, the intermediate data <NUM>, and the final data <NUM> of <FIG> may have the same shape as that of the data <NUM> of <FIG>. In other words, if the image data <NUM> includes pixel values of (<NUM>,<NUM>) to (<NUM>,<NUM>), the intermediate data <NUM> and the final data <NUM> include pixel values in the same form as the image data <NUM>.

In <FIG>, the data <NUM> is divided into windows of <NUM>×<NUM>, i.e., each window has <NUM> rows of pixels and <NUM> columns of pixels. The size of a window may be determined according to the number of 1D FFT processors connected to an input end and an output end of the memory <NUM>. The 1D FFT processors connected to the input end are included in the first core <NUM>, whereas the 1D FFT processors connected to the output end are included in the second core <NUM>.

For example, the number of rows of a window is equal to the number of the 1D FFT processors connected to the input end, whereas the number of columns of a window is equal to the number of 1D FFT processors connected to the output end. When the number of the 1D FFT processors connected to the input end and the output end is equal to thirty-two (<NUM>), the data <NUM> are divided into windows of <NUM>×<NUM>. In another example, when the number of the 1D FFT processors connected to the output end is equal to thirty-two (<NUM>), and the number of the 1D FFT processors connected to the input end is equal to sixteen (<NUM>), the data <NUM> is divided into windows of <NUM>×<NUM> (the size of a window is indicated by [height × breadth] or [number of rows × number of columns]).

<FIG> illustrates a method of storing the intermediate data in the memory, according to an exemplary embodiment. Referring to <FIG>, the Fourier transform apparatus <NUM> divides the intermediate data <NUM> and stores divided intermediate data at different respective start positions of the memory <NUM>. The intermediate data <NUM>, as illustrated in <FIG>, is divided into a plurality of windows, and pixel values included in the windows are stored in the memory <NUM>.

<FIG> illustrates an example of sequentially storing Bank0 to Bank7 at start positions. In other words, Bank0 is designated as a first start position (and a ninth start position), Bank1 is designated as a second start position (and a tenth start position), and Bank7 is designated as a sixteenth start position (and an eighth start position).

The banks are not necessarily sequentially designated as start positions. A previous start position and a next start position may be designated as different banks which are not necessarily in sequence with each other. For example, Bank0 may be designated as a first start position, whereas Bank5 may be designated as a second start position.

The Fourier transform apparatus <NUM> designates Bank0 as a start position and sequentially writes pixel values included in u0v0 to u0v31 in Bank0 to Bank7 (write). In other words, the Fourier transform apparatus <NUM> writes the windows u0v0 to u0v31 in the same row at a first start position. The u0v0 to u0v31 are example of the windows of the same row.

The Fourier transform apparatus <NUM> writes the pixel values included in each window in the memory <NUM> in the column direction. For example, a lower end in <FIG> indicates an order of the pixel values written in Bank0 and Bank1. Bank0 is a first start position and Bank1 is a second start position. B(<NUM>,<NUM>) denotes a pixel value of the intermediate data <NUM>. B(<NUM>,<NUM>) to B(<NUM>,<NUM>) are written in Bank0 and then B(<NUM>,<NUM>) to B(<NUM>,<NUM>) are written therein. B(<NUM>,<NUM>) to B(<NUM>,<NUM>) are pixel values included in the first column of u0v0, and B(<NUM>,<NUM>) to B(<NUM>,<NUM>) are pixel values included in the second column of u0v0. The Fourier transform apparatus <NUM>, which writes pixel values in the column direction, may easily read out the intermediate data <NUM> in the column direction when reading out the intermediate data <NUM> from the memory <NUM>. In other words, although the pixel values are written in the memory <NUM> in the row direction of the memory <NUM>, the pixel values are arranged in the column direction of the intermediate data <NUM>.

During the writing of the pixel values included in u0v0 to u0v31, when a storage space in one row of Bank0 is insufficient, the pixel values are written in Bank1. <FIG> illustrates, as an example, a case in which the pixel values included in u0v0 to u0v31 are written in a plurality of rows of Bank0 to Bank7.

After writing all windows u0v0 to u0v31 included in the first row, the Fourier transform apparatus <NUM> writes the windows u1v0 to u1v31 included in the second row at a second start position. The second start position may be a bank that is different from the first start position. In <FIG>, a case in which Bank1 is designated as a second start position is illustrated as an example. The Fourier transform apparatus <NUM> sequentially writes, from Bank1, the pixel values of the windows u1v0 to u1v31 included in the second row.

The Fourier transform apparatus <NUM> writes the pixel values of windows u1v0 to u1v31 included in the second row in the column direction. The lower portion of <FIG> shows an order of writing the pixel values of the windows u1v0 to u1v31 included in the second row by designating Bank1 as a second start position. The Fourier transform apparatus <NUM> writes B(<NUM>,<NUM>) to B(<NUM>,<NUM>) and B(<NUM>,<NUM>) to B(<NUM>,<NUM>) in Bank1. B(<NUM>,<NUM>) to B(<NUM>,<NUM>) are pixel values included in the first column of u1v0, and B(<NUM>,<NUM>) to B(<NUM>,<NUM>) are pixel values included in the second column of u1v0. The Fourier transform apparatus <NUM> writes pixel values included in the thirty-second column of u1v31, thereby terminating the writing of the pixel values of the windows u1v0 to u1v31 included in the second row.

Finally, the Fourier transform apparatus <NUM> writes pixel values of windows u15v0 to u15v31 included in the sixteenth row from Bank7 that is a sixteenth start position. The Fourier transform apparatus <NUM> writes pixel values included in u15v31 that is a last window, in the memory <NUM>, thereby terminating the writing of the intermediate data <NUM> in the memory <NUM>.

<FIG> illustrates a method of reading out intermediate data from the memory <NUM>, according to an exemplary embodiment. Referring to <FIG>, the Fourier transform apparatus <NUM> may read out the intermediate data <NUM> in the column direction. For example, the Fourier transform apparatus <NUM> may read out pixel values B(<NUM>,<NUM>) to B(<NUM>,<NUM>) in the first column of the intermediate data <NUM>, pixel values B(<NUM>,<NUM>) to B(<NUM>,<NUM>) in the second column, and finally, pixel values B(<NUM>,<NUM>) to B(<NUM>,<NUM>) in the one thousand twenty-fourth (1024th) column.

The Fourier transform apparatus <NUM> may read out one column of the intermediate data <NUM> by reading out pixel values that correspond to a size of a column of a window from respective start positions. The start positions indicate positions designated when the intermediate data <NUM> is stored in the memory <NUM>. The size of a column of a window may be or correspond to the number of 1D FFT processors generating the intermediate data <NUM>.

A case in which start positions are sequentially shifted from Bank0 to Bank7 and the size of a column of a window is <NUM> is illustrated, for example in <FIG>. The Fourier transform apparatus <NUM> reads out thirty-two (<NUM>) pixel values B(<NUM>,<NUM>) to B(<NUM>,<NUM>) from the start position of Bank0 and thirty-two (<NUM>) pixel values B(<NUM>,<NUM>) to B(<NUM>,<NUM>) from the start position of Bank1. The Fourier transform apparatus <NUM> reads out pixel values according to the order of start positions, and finally reads out thirty-two (<NUM>) pixel values B(<NUM>,<NUM>) to B(<NUM>,<NUM>) from the start position of Bank7. The Fourier transform apparatus <NUM> reads out thirty-two (<NUM>) pixel values from each of all start positions, thereby reading out pixel values B(<NUM>,<NUM>) to B(<NUM>,<NUM>) in the first column of the intermediate data <NUM>.

In order to read out the pixel values of the second column of the intermediate data <NUM>, the Fourier transform apparatus <NUM> reads out <NUM>rd to <NUM>th pixel values B(<NUM>,<NUM>) to B(<NUM>,<NUM>) from the start position of Bank0 and <NUM>rd to <NUM>th pixel values B(<NUM>,<NUM>) to B(<NUM>,<NUM>) from the start position of Bank1. The Fourier transform apparatus <NUM> reads out pixel values according to the order of start positions and finally reads out <NUM>rd to <NUM>th pixel values B(<NUM>,<NUM>) to B(<NUM>,<NUM>) from the start position of Bank7. The Fourier transform apparatus <NUM> reads out thirty-two (<NUM>) pixel values from each of the thirty-third positions of all start positions, thereby reading out pixel values B(<NUM>,<NUM>) to B(<NUM>,<NUM>) in the second column of the intermediate data <NUM>.

By repeating the above-described process, the Fourier transform apparatus <NUM> may read out a total of one thousand twenty-four (<NUM>) columns from the <NUM>th column to <NUM>rd column of the intermediate data <NUM>. The Fourier transform apparatus <NUM> reads out each column and outputs the read columns to the second buffer <NUM>.

<FIG> is a flowchart for explaining a Fourier transform method, according to another exemplary embodiment. <FIG> illustrates a method in which the Fourier transform apparatus <NUM> performs a 1D FFT on the image data <NUM> in the column direction and then performs a 1D FFT on the image data <NUM> in the row direction, as illustrated in <FIG>.

In operation <NUM>, the Fourier transform apparatus <NUM> performs a 1D FFT on the image data <NUM> in the column direction (i.e., on a column-by-column basis) in order to generate the intermediate data <NUM>. The first core <NUM> performs a 1D FFT with respect to each column of the image data <NUM>. Each of the 1D FFT processors included in the first core <NUM> performs a respective 1D FFT with respect to the corresponding rows of the image data <NUM>. In this state, one 1D FFT processor may perform a 1D FFT with respect to a plurality of rows. For example, when there are thirty-two (<NUM>) 1D FFT processors, a first 1D FFT processor may perform a 1D FFT with respect to the <NUM>th row, the <NUM>nd row, the <NUM>th row, etc. of the image data <NUM>.

In operation <NUM>, the Fourier transform apparatus <NUM> designates different banks of the memory <NUM> as start positions, and divides and stores the intermediate data <NUM> at the respective start positions. For example, if the Fourier transform apparatus <NUM> designates the <NUM>th bank as a start position, the <NUM>st bank may be designated as a next start position and the <NUM>nd bank may be designated as a further next start position. If the intermediate data <NUM> is divided into three parts, the Fourier transform apparatus <NUM> may store a first part from the <NUM>th bank, a second part from the <NUM>st bank, and a third part from the <NUM>nd bank. The intermediate data <NUM> may be divided based on a column in which the data is located. For example, if the intermediate data <NUM> includes sixty-four (<NUM>) columns, the <NUM>th to <NUM>st columns form a first part and the <NUM>nd to <NUM>rd columns form a second part. The Fourier transform apparatus <NUM> may store the intermediate data <NUM> in the row direction, i.e., on a row-by-row basis. For example, the first row of the first part, the first row of the second part, and the first row of the third part of the intermediate data <NUM> may be sequentially stored in the <NUM>th bank.

In operation <NUM>, the Fourier transform apparatus <NUM> reads out the intermediate data <NUM> from the start positions of the memory <NUM>. The Fourier transform apparatus <NUM> may read out the intermediate data <NUM> in the row direction by repeating a process of reading out the intermediate data <NUM> from each start position to a particular position. For example, the Fourier transform apparatus <NUM> may read out the <NUM>st to <NUM>nd pixel values from the <NUM>th bank, the <NUM>st to <NUM>nd pixel values from the <NUM>st bank, and the <NUM>st to <NUM>nd pixel values from the <NUM>nd bank, thereby reading out the first row of the intermediate data <NUM>. Furthermore, the Fourier transform apparatus <NUM> reads out the <NUM>rd to <NUM>th pixel values from the <NUM>th bank, the <NUM>rd to <NUM>th pixel values from the <NUM>st bank, and the <NUM>rd to <NUM>th pixel values from the <NUM>nd bank, thereby reading out the second row of the intermediate data <NUM>. As described above, the Fourier transform apparatus <NUM> may read out the intermediate data <NUM> in the row direction by reading out the pixel values at the same position from the respective start positions.

In operation <NUM>, the Fourier transform apparatus <NUM> generates the final data <NUM> by performing a 1D FFT on the intermediate data <NUM> in the row direction, i.e., on a row-by-row basis. Since in the operation <NUM> the Fourier transform apparatus <NUM> reads out the intermediate data <NUM> from the memory <NUM> in the row direction, the Fourier transform apparatus <NUM> may perform a 1D FFT on the intermediate data <NUM> in the row direction by performing a 1D FFT on the read-out data. The respective rows may be transformed by sequentially being input into the 1D FFT processor.

As described above, the intermediate data may be divided and stored in different respective banks of the memory. The intermediate data stored in different banks may be read out without a delay. An amount of address calculations may be reduced by designating start positions to store the intermediate data.

The apparatus described herein may comprise a processor, a memory for storing program data to be executed by the processor, a permanent storage such as a disk drive, a communications port for handling communications with external devices, and user interface devices, including a display, keys, and/or any other suitable device. When software modules are involved, these software modules may be stored as program instructions or computer readable code executable by the processor on a non-transitory computer-readable medium such as read-only memory (ROM), random-access memory (RAM), compact disk-ROM (CD-ROMs), magnetic tapes, floppy disks, and optical data storage devices. The computer readable recording media may also be distributed over network coupled computer systems so that the computer readable code is stored and executed in a distributed fashion. This media can be read by the computer, stored in the memory, and executed by the processor.

The exemplary embodiments may be described in terms of functional block components and various processing steps. Such functional blocks may be realized by any number of hardware and/or software components configured to perform the specified functions. For example, the exemplary embodiments may employ various integrated circuit (IC) components, e.g., memory elements, processing elements, logic elements, look-up tables, and the like, which may carry out a variety of functions under the control of one or more microprocessors or other control devices. Similarly, where the elements of the exemplary embodiments are implemented using software programming or software elements, the exemplary embodiments may be implemented with any programming or scripting language such as C, C++, Java, assembler language, or the like, with the various algorithms being implemented with any combination of data structures, objects, processes, routines or other programming elements. Functional aspects may be implemented in algorithms that are executed on one or more processors. Furthermore, the exemplary embodiments could employ any number of conventional techniques for electronics configuration, signal processing and/or control, data processing and the like. The words "mechanism," "element," "means," and "configuration" are used broadly and are not limited to mechanical or physical embodiments, but can include software routines in conjunction with processors, etc..

The particular implementations shown and described herein are illustrative examples of the present inventive concept and are not intended to otherwise limit the scope of the present inventive concept in any way. For the sake of brevity, conventional electronics, control systems, software development and other functional aspects of the systems may not be described in detail. Furthermore, the connecting lines, or connectors shown in the various figures presented are intended to represent functional relationships and/or physical or logical couplings between the various elements. It should be noted that many alternative or additional functional relationships, physical connections or logical connections may be present in a practical device.

Claim 1:
A method of performing a Fourier transform, the method comprising:
generating intermediate data (<NUM>) by performing a first one-dimensional, 1D, fast Fourier transform, FFT, on image data (<NUM>) of two-dimensional (2D) matrix form on a row-by-row basis (<NUM>) using a first core (<NUM>,<NUM>) comprising a plurality of first parallel processors which perform a respective 1D FFT with respect to a corresponding row of the image data;
designating at least two different banks of a memory (<NUM>,<NUM>) as respective start positions and storing the intermediate data (<NUM>) at the start positions;
wherein the designating the at least two different banks of the memory (<NUM>,<NUM>) as the start positions comprises designating a second bank that is different from a first bank of a previous start position as a start position;
determining when the first 1D FFT has completed and reading out the intermediate data (<NUM>) from the designated banks and associating intermediate data read from the designated banks through a demultiplexer (<NUM>) and providing the associated intermediate data (<NUM>) to a second core (<NUM>);
generating final data (<NUM>) by performing a second 1D FFT on the intermediate data (<NUM>) based on a column-by-column basis using the second core (<NUM>,<NUM>) which comprises a plurality of second parallel processors which perform a respective 1D FFT with respect to a corresponding column of the image data; and
displaying an image indicated by the image data using the final data (<NUM>), wherein generating the intermediate data by performing the first 1D FFT further comprises:
performing M-times of generating N-rows of the intermediate data (<NUM>) by performing the first 1D FFT on the every N-rows of the image data,
wherein designating banks of the memory further comprises:
designating different M-banks of the memory; and
saving m-th generated N-rows of the intermediate data at m-th bank of the memory,
wherein m, N, and M are integer and m is less than or equal to M and the number of rows of the image data is equal to NxM.