# US 2013/0159369 A1 · Apparatus and method for performing discrete fourier transform

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2013/0159369 A1
- Document ID: US20130159369A1
- Status: Published application
- Kind: A1
- Application number: 13/718,599
- Filed: 2012-12-18
- Published: 2013-06-20
- Earliest claimed: 2011-12-19
- Assignees: Samsung Electronics Co., Ltd.
- Inventors: In-Tae KANG; Su-Jin YOON; Sang-Min BAE; Jong-Han LIM
- Web page: https://patentgrep.com/patent/US20130159369A1

## CPC

- G06F 17/141: {Discrete Fourier transforms}
- H04L 27/263: {modification of IFFT/IDFT modulator for performance improvement}
- H04L 27/2651: {Modification of fast Fourier transform [FFT] or discrete Fourier transform [DFT] demodulators for performance improvement}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)

## Abstract

A Discrete Fourier Transform (DFT) apparatus is provided. The DFT apparatus includes a first delay, a second delay, an operator, and a multiplier. The first delay delays one sampling data by N-sample in a time axis when the one sampling data is input. The second delay delays an output value of a frequency component for a previous sampling data by 1-sample. The operator performs an operation based on the input one sampling data, the one sampling data delayed by the N-sample in the time axis, and the 1-sample delayed output value of the frequency component for the previous sampling data. The multiplier multiplies an output value from the operator by a twiddle factor  j  2   π   kn N . Therefore, a complexity of a stream DFT operation can be reduced.

## Claims

### Claim 1

A Discrete Fourier Transform (DFT) apparatus comprising:
a first delay for delaying one sampling data by N-sample in a time axis when the one sampling data is input;
a second delay for delaying an output value of a frequency component for a previous sampling data by 1-sample;
an operator for performing an operation based on the input one sampling data, the one sampling data delayed by the N-sample in the time axis, and the 1-sample delayed output value of the frequency component for the previous sampling data; and
a multiplier for multiplying an output value from the operator by a twiddle factor

j

2


π


kn
N
.

### Claim 2 (depends on 1)

The apparatus of claim 1, wherein an output value of the multiplier is expressed by the equation:
X
n
+
1

[
k
]
=
(
X
n

[
k
]
-
x

[
n
]
+
x

[
n
+
N
]
)


j

2


π


kn
N
for


k
=
0
,
…

,
N
-
1
where k is a subcarrier index, Xn+1[k] is an output value for a k subcarrier in the frequency axis when (n+1)-th sampling data is input, x[n] is n-th sampling data value in the time axis, and

j

2


π


kn
N
is a twiddle factor.

### Claim 3 (depends on 1)

The apparatus of claim 1, wherein the operator comprises one addition operator and one subtraction operator.

### Claim 4 (depends on 1)

The apparatus of claim 1, wherein N is a size of a Discrete Fourier Transform (DFT).

### Claim 5

A Discrete Fourier Transform (DFT) apparatus, the apparatus comprising:
a first delay for delaying one sampling data by N-sample in a time axis when the one sampling data is input;
a plurality of second delays for delaying an output value of a frequency component for a previous sampling data by 1-sample;
a plurality of operators for performing an operation based on the input one sampling data, the one sampling data delayed by the N-sample in the time axis, and the 1-sample delayed output value of the frequency component for the previous sampling data; and
a plurality of multipliers for multiplying each of output values from the plurality of operators by a twiddle factor

j

2


π


kn
N
.

### Claim 6 (depends on 5)

The apparatus of claim 5, wherein an output value of each of the plurality of multipliers is expressed by the equation:
X
n
+
1

[
k
]
=
(
X
n

[
k
]
-
x

[
n
]
+
x

[
n
+
N
]
)


j

2


π


kn
N
for


k
=
0
,
…

,
N
-
1
where k is a subcarrier index, Xn−1[k] is an output value for a k subcarrier in the frequency axis when (n+1)-th sampling data is input, x[n] is n-th sampling data value in the time axis, and

j

2


π


kn
N
is a twiddle factor.

### Claim 7 (depends on 5)

The apparatus of claim 5, wherein each of the plurality of operators comprises one addition operator and one subtraction operator.

### Claim 8 (depends on 1)

The apparatus of claim 1, wherein N is a size of a DFT.

### Claim 9

A Discrete Fourier Transform (DFT) method, the method comprising:
when one sampling data is input, delaying, at a first delay, the one sampling data by N-sample in a time axis;
delaying, at a second delay, an output value of a frequency component for a previous sampling data by 1-sample;
performing, at an operator, an operation based on the input one sampling data, the one sampling data delayed by the N-sample in the time axis, and the 1-sample delayed output value of the frequency component for the previous sampling data; and
multiplying, at a multiplier, an output value from the operator by a twiddle factor

j

2


π


kn
N
.

### Claim 10 (depends on 9)

The method of claim 9, wherein an output value of the multiplier is expressed by the equation:
X
n
+
1

[
k
]
=
(
X
n

[
k
]
-
x

[
n
]
+
x

[
n
+
N
]
)


j

2


π


kn
N
for


k
=
0
,
…

,
N
-
1
where k is a subcarrier index, Xn+1[k] is an output value for a k subcarrier in the frequency axis when (n+1)-th sampling data is input, x[n] is n-th sampling data value in the time axis, and

j

2


π


kn
N
is a twiddle factor.

### Claim 11 (depends on 9)

The method of claim 9, wherein the operator comprises one addition operator and one subtraction operator.

### Claim 12 (depends on 9)

The apparatus of claim 9, wherein N is a size of a DFT.
