Fourier transform for a signal to be transmitted on a random access channel

Patent metadata

Field	Value
Publication number	US-9788347-B2
Application number	US-201514729575-A
Country	US
Kind code	B2
Filing date	Jun 3, 2015
Priority date	Mar 30, 2010
Publication date	Oct 10, 2017
Grant date	Oct 10, 2017

Abstract

Provided is a recursive method and apparatus for processing a signal for determining a plurality of frequency components of the signal, the signal being a chirp-like polyphase sequence. In one embodiment, the method includes: (1) determining a first frequency component of the plurality of frequency components, (2) determining a component factor by accessing a factor table, (3) determining the second frequency component using the determined first frequency component and the determined component factor. If there is at least one further frequency component of the signal, the method further comprising for each of the further frequency components: (4) determining a respective further component factor by accessing the factor table, and (5) determining the further frequency component using a previously determined frequency component and the determined further component factor, wherein the previously determined frequency component is the frequency component determined most recently prior to determining each respective further frequency component.

First claim

What is claimed is:

1. A recursive method for determining a plurality of frequency components of a signal, the signal being a chirp-like polyphase sequence, the method comprising:
determining a first frequency component of the plurality of frequency components;
determining a component factor by accessing a factor table;
determining a second frequency component of the plurality of frequency components using the determined first frequency component and the determined component factor; and
determining a further frequency component of the signal by using a previously determined frequency component and a respective further component factor of the further frequency component, wherein the previously determined frequency component is the frequency component determined most recently prior to determining each respective further frequency component and the respective further component factor is determined by accessing the factor table.

2. The method of claim 1 further comprising setting the first frequency component to 1 so it does not need to be computed.

3. The method of claim 1 wherein the factor table stores a plurality of component factors in an indexed manner for use in determining the plurality of frequency components of the signal, and wherein the steps of determining each of the plurality of component factors comprises indexing the factor table with an index corresponding to the each of the plurality of component factors.

4. The method of claim 3 further comprising calculating the plurality of component factors and storing the calculated component factors in the factor table.

5. The method of claim 1 wherein the component factor is a multiplication factor, and wherein the step of determining the second frequency component comprises multiplying the first frequency component by the component factor.

6. The method of claim 1 wherein the signal is a Zadoff-Chu sequence in which the signal, x, at each position, n, of each root, μ, of the Zadoff-Chu sequence is given by

x
μ

⁡

(
n
)

=

e

-
j

⁢

⁢
πμ
⁢

n
⁡

(

n
+
1

)

N
ZC

,

where N ZC is the length of the Zadoff-Chu sequence.

7. The method of claim 6 wherein the length of the Zadoff-Chu sequence is a prime number.

8. The method of claim 7 wherein the length of the Zadoff-Chu sequence is 139 or 839.

9. The method of claim 6 wherein the (k+1)th frequency component, X(k+1), of the signal is determined using the kth frequency component, X(k), of the signal and the (k+1)th component factor, F k+1 , according to the formula:
X ( k+ 1)= X ( k ) F k+1 ,
where

F

k
+
1

=

e

2
⁢
j
⁢

⁢
π
⁢

⁢
nk

N
ZC

⁢

e

j
⁢

⁢
πμ
⁢

m
⁡

(

m
+
1

)

N
ZC

⁢

e

2
⁢
j
⁢

⁢
π
⁢

⁢

C
v

N
ZC

,

and where m is an integer chosen such that mμ=1 mod N ZC , and C v is an integer defined by the equation x μ,v =x μ ((n+C v )mod N ZC ) where for the μth root of the Zadoff-Chu sequence, x μ,v is a cyclically shifted version of x μ wherein x μ,v and x μ have zero correlation zones of length N CS −1.

10. The method of claim 6 further comprising:
setting an increment variable, γ; and
setting an index variable I,
wherein the step of determining a component factor comprises loading the component factor from the factor table using the index variable I, the method further comprising:
incrementing the index variable I by the increment variable γ for determining a further component factor by loading the further component factor from the factor table using the incremented index variable.

11. The method of claim 6 further comprising:
setting the first frequency component to 1 so it does not need to be computed:
setting an increment variable, γ;
setting an index variable I;
setting a loading variable J such that J=I initially,
wherein the step of determining a component factor comprises loading the component factor from the factor table using the loading variable J, and said step of determining the s

Assignees

• Nvidia Tech Uk Ltd
• Nvidia Corp

Inventors

• Tabet Tarik
• Costa Godfrey
• Ramesh Nallepilli

Classifications

• G06F17/141 Primary

  Discrete Fourier transforms · CPC title

• H04W74/0833 Primary

  Random access procedures, e.g. with 4-step access · CPC title

• H04L27/2636

  with FFT or DFT modulators, e.g. standard single-carrier frequency-division multiple access [SC-FDMA] transmitter or DFT spread orthogonal frequency division multiplexing [DFT-SOFDM] · CPC title