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

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.

Claims

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_{\mu }\left(n\right)=e^{-j\mathrm{\pi \mu }\frac{n\left(n+1\right)}{N_{\mathrm{ZC}}}},$ where N.sub.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.sub.k+1, according to the formula:
X(k+1)=X(k)F.sub.k+1, where $F_{k+1}=e^{\frac{2j\pi \mathrm{nk}}{N_{\mathrm{ZC}}}}{e}^{j\mathrm{\pi \mu }\frac{m\left(m+1\right)}{N_{\mathrm{ZC}}}}{e}^{\frac{2j\pi C_v}{N_{\mathrm{ZC}}}},$ and where m is an integer chosen such that mμ=1 mod N.sub.ZC, and C.sub.v is an integer defined by the equation x.sub.μ,v=x.sub.μ((n+C.sub.v)mod N.sub.ZC) where for the μth root of the Zadoff-Chu sequence, x.sub.μ,v is a cyclically shifted version of x.sub.μ wherein x.sub.μ,v and x.sub.μ have zero correlation zones of length N.sub.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 second frequency component comprises setting the second frequency component to be the determined component factor, the method further comprising: incrementing the index variable I by the increment variable γ; and incrementing the loading variable J by the index variable I for determining a further component factor by loading the further component factor from the factor table using the incremented loading variable.

12. The method of claim 10 wherein the increment variable γ is set such that γ=mod(m,N.sub.ZC), where m is an integer chosen such that mμ=1 mod N.sub.ZC, and the index variable I is set such that $I=\mathrm{mod}\left(\mathrm{\mu m}\frac{\left(m+1\right)}{2}+C_v,N_{\mathrm{ZC}}\right).$

13. An apparatus for processing a signal to be transmitted on a random access channel using a recursive method for determining a plurality of frequency components of the signal, the signal being a chirp-like polyphase sequence, the apparatus comprising a processor configured to: determine a frequency component X(0) of the plurality of frequency components; set a counter i to 1; obtain a component factor for a frequency component X(i) of the signal from a factor table by indexing the factor table with an index corresponding to the component factor for the frequency component X(i), 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; determine the frequency component X(i) using the determined frequency component X(i−1) and the obtained component factor for the frequency component X(i), wherein the frequency component X(i−1) is the frequency component determined most recently prior to determining the frequency component X(i); and increment the counter i by 1 and continue to obtain the component factor for the frequency component X(i) of the signal and determine the frequency component X(i) until each frequency component of the plurality of frequency components is determined.

14. The apparatus of claim 13 further comprising a memory for storing the factor table and a transmitter for transmitting the signal.

15. The apparatus of claim 13 wherein the processor is further configured to apply the determined frequency components of the signal to consecutive inputs of an Inverse Fast Fourier Transform block.

16. The apparatus of claim 13 wherein the signal is a random access channel preamble and the processor is configured to perform the recursive method to provide a Discrete Fourier Transform of the signal.

17. The apparatus of claim 13 wherein the processor is further configured to separate the signal into blocks for transmission and insert a cyclic prefix into each block.

18. A computer program product comprising computer readable instructions stored on a non-transitory computer readable medium for execution on a computer, the instructions being for processing a signal to be transmitted on a random access channel, the signal being a chirp-like polyphase sequence, the instructions comprising instructions for executing a recursive method for determining a plurality of frequency components of the signal comprising the steps of: determining a first frequency component of the plurality of frequency components; determining a component factor by accessing a factor table for use in determining a second frequency component of the plurality of frequency components; determining the second frequency component using the determined first frequency component and the determined component factor; and determining a further frequency component of the signal 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 that stores a component factor for each of the plurality of frequency components.

19. The computer program product of claim 18 wherein the recursive method further comprises calculating the plurality of component factors and storing the calculated component factors in the factor table.

20. The computer program product of claim 18 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.

Description

BRIEF DESCRIPTION

(1) Reference is now made to the following descriptions taken in conjunction with the accompanying drawings, in which:

(2) FIG. 1 is a schematic representation of a SC-FDMA communication system; and

(3) FIG. 2 is a flow chart of an embodiment of a process of processing a signal according to the principles of the disclosure.

DETAILED DESCRIPTION

(4) An efficient implementation of the DFT of a Zadoff-Chu sequence (or any other chirp-like polyphase sequence) is provided without needing to perform a Fourier transform. The method uses a recursive relation with reduced complexity. The Zadoff-Chu sequence has been chosen to be used for RACH preambles in LTE wireless networks, so the ability to implement a Fourier transform with reduced complexity on Zadoff-Chu sequences is particularly beneficial. However, it is noted that the method works with any signal that is a chirp-like polyphase sequence.

(5) The Zadoff Chu sequence is just one example of a chirp-like polyphase sequence. As would be apparent to a skilled person, chirp-like polyphase sequences have ideal periodic autocorrelation functions. Details on chirp-like polyphase sequences can be found in “Generalized Chirp-Like Polyphase Sequences with optimum Correlation Properties” by Branislav M. Popović, IEEE Transactions on Information Theory, vol. 38, No. 4, July 1992, pages 1406 to 1409. It is described in that reference that as well as Zadoff-Chu sequences, Frank sequences and also Ipatov sequences are chirp-like polyphase sequences.

(6) The complexity of implementing the Fourier Transform is reduced by using a lookup table with a simple index computation. Such indexing requires less processing power than performing a conventional DFT. The table may be stored at the UE. Component factors in the table may be calculated by the UE. Alternatively, the component factors stored in the table may be calculated by an entity other than the UE and passed to the UE for storage thereon.

(7) Before describing an embodiment of the disclosure, there is provided a derivation of equations that are used in the embodiment to facilitate the understanding of the disclosure.

(8) As described above, the Zadoff-Chu sequence (for odd N.sub.ZC) is defined by

(9) $x\left(n\right)=e^{-j\frac{\mathrm{\pi \mu }n\left(n+1\right)}{N_{\mathrm{zc}}}}$$x\left(n\right)=e^{\left(-\frac{2j\pi \mu \underset{i=1}{\overset{n}{.Math.}}i}{N_{\mathrm{zc}}}\right)}$$x\left(n\right)=\underset{i=1}{\overset{n}{.Math.}}{e}^{\left(-\frac{2j\pi \mu i}{N_{\mathrm{zc}}}\right)}$
where the fact that

(10) $\underset{i=1}{\overset{n}{.Math.}}i=\frac{n\left(n+1\right)}{2}$
has been used.

(11) This can be rewritten as a recursive equation, such that:

(12) $x\left(n\right)=x\left(n-1\right)e^{\frac{2j\mathrm{\pi \mu }n}{N_{\mathrm{zc}}}}.$

(13) Taking the Discrete Fourier transform of the above relation and using the DFT properties, one gets:

(14) $\begin{array}{cc}X\left(k\right)=X\left(k+\mu \right)e^{\frac{2j\pi \left(\mu +k\right)}{N_{\mathrm{zc}}}},& \left(1\right)\end{array}$
where X(k) is the discrete Fourier transform of x(n).

(15) Based on equation (1), recursively one can write using the shift properties of the DFT:

(16) $\begin{array}{c}X\left(k\right)=X\left(k+\mu \right)e^{\left(-\frac{2j\pi \left(\mu +k\right)}{N_{\mathrm{zc}}}\right)}\\ =X\left(k+2\mu \right)e^{\left(-\frac{2j\pi \left(\mu +k\right)}{N_{\mathrm{zc}}}\right)}{e}^{\left(-\frac{2j\pi \left(2\mu +k\right)}{N_{\mathrm{zc}}}\right)}\mathrm{.Math.}\\ =X\left(k+m\mu \right)\underset{i=1}{\overset{m}{.Math.}}{e}^{\left(-\frac{2j\mu \left(l\mu +k\right)}{N_{\mathrm{zc}}}\right)}\\ =X\left(k+m\mu \right)e^{\left(-\frac{2j\pi \underset{i=1}{\overset{m}{.Math.}}\left(k+l\mu \right)}{N_{\mathrm{zc}}}\right)}\\ =X\left(k+m\mu \right)e^{-\frac{2j\pi \mathrm{mk}}{N_{\mathrm{zc}}}}{e}^{-j\mathrm{\pi \mu }\frac{m\left(m+1\right)}{N_{\mathrm{zc}}}}\end{array}$

(17) Let us introduce the following notation. Two integers a and b are said to be congruent modulo n, if their difference a−b is an integer multiple of n. An equivalent definition is that both numbers have the same remainder when divided by n. If this is the case, it is expressed as:
a=b mod n.

(18) Let us choose m such that mμ=1 mod N.sub.ZC. m always exists since N.sub.ZC and μ are relatively prime numbers (i.e. they share no common positive factors, or divisors, except 1) by construction of the Zadoff-Chu sequence. Then, from the periodicity property of the DFT:
X(k+mμ)=X(k+1),
one obtains the final result as:

(19) $\begin{array}{cc}X\left(k+1\right)=X\left(k\right)e^{\frac{2j\pi \mathrm{mk}}{N_{\mathrm{zc}}}}{e}^{j\mathrm{\pi \mu }\frac{m\left(m+1\right)}{N_{\mathrm{zc}}}}& \left(2\right)\end{array}$
with

(20) $X\left(0\right)=\underset{n=0}{\overset{N_{\mathrm{ZC}}-1}{.Math.}}{e}^{-j\mathrm{\pi \mu }\frac{n\left(n+1\right)}{N_{\mathrm{zc}}}}.$

(21) From equation (2), one can get an expression for X(k) as:

(22) $X\left(k\right)=X\left(k-1\right)e^{\frac{2j\pi m\left(k-1\right)}{N_{\mathrm{zc}}}}{e}^{j\mathrm{\pi \mu }\frac{m\left(m+1\right)}{N_{\mathrm{zc}}}}$
By recursion one gets:

(23) 0$X\left(k\right)=X\left(k-2\right)e^{\frac{2j\pi m\left(k-2\right)}{N_{\mathrm{zc}}}}{e}^{j\mathrm{\pi \mu }\frac{m\left(m+1\right)}{N_{\mathrm{zc}}}}{e}^{\frac{2j\pi m\left(k-1\right)}{N_{\mathrm{zc}}}}{e}^{j\mathrm{\pi \mu }\frac{m\left(m+1\right)}{N_{\mathrm{zc}}}}$
which leads to:

(24) $X\left(k\right)=X\left(0\right)\underset{l=0}{\overset{k-1}{.Math.}}{e}^{\frac{2j\pi \mathrm{ml}}{N_{\mathrm{zc}}}}{e}^{j\mathrm{\pi \mu }\frac{m\left(m+1\right)}{N_{\mathrm{zc}}}}$
and finally to the result that:

(25) $\begin{array}{cc}X\left(k\right)=X\left(0\right)e^{\frac{2j\pi \mathrm{mk}\left(k-1\right)}{N_{\mathrm{zc}}}}{e}^{j\mathrm{\pi \mu }\frac{\mathrm{km}\left(m+1\right)}{N_{\mathrm{zc}}}}& \left(3\right)\end{array}$

(26) In the case where N.sub.ZC is even, the Zadoff-Chu sequence is given by:

(27) $x\left(n\right)=e^{-j\mathrm{\pi \mu }\frac{n^2}{N_{\mathrm{zc}}}}.$
One can show by inductive proof that:

(28) $x\left(n\right)=x\left(n-1\right)e^{\left(-\frac{2j\mathrm{\pi \mu }n}{N_{\mathrm{zc}}}\right)}{e}^{\left(-\frac{j\mathrm{\pi \mu }}{N_{\mathrm{zc}}}\right)}.$
Similarly to the derivations above, one obtains:

(29) $\begin{array}{cc}X\left(k\right)=X\left(k+\mu \right)e^{\frac{2j\pi \left(\mu +k\right)}{N_{\mathrm{zc}}}}{e}^{-\frac{j\mathrm{\pi \mu }}{N_{\mathrm{zc}}}}& \left(4\right)\end{array}$
which leads to:

(30) $X\left(k\right)=X\left(k+m\mu \right)\underset{l=1}{\overset{m}{.Math.}}{e}^{-\frac{2\mathrm{j\pi }\left(l\mu +k\right)}{N_{\mathrm{zc}}}}{e}^{-\frac{j\mathrm{\pi \mu }}{N_{\mathrm{zc}}}}$$X\left(k\right)=X\left(k+m\mu \right)e^{-\frac{2j\pi \mathrm{mk}}{N_{\mathrm{zc}}}}{e}^{-j\mathrm{\pi \mu }\frac{m\left(m+1\right)}{N_{\mathrm{zc}}}}{e}^{-\frac{j\pi m\mu }{N_{\mathrm{zc}}}}$
If m is such that mμ=1 mod N.sub.ZC exists, then one can rewrite the above equation as:

(31) $\begin{array}{cc}X\left(k\right)=X\left(k+1\right)e^{\frac{2j\pi \mathrm{mk}}{N_{\mathrm{ZC}}}}{e}^{-j\mathrm{\pi \mu }\frac{m\left(m+1\right)}{N_{\mathrm{ZC}}}}{e}^{\frac{j\pi m\mu }{N_{\mathrm{ZC}}}}& \left(5\right)\end{array}$
X(k) can be expressed as (if m is such that mμ=1 mod N.sub.ZC exists):

(32) $X\left(k\right)=X\left(0\right)\underset{l=0}{\overset{k-1}{.Math.}}\left(e^{\frac{2j\pi \mathrm{ml}}{N_{\mathrm{ZC}}}}{e}^{j\mathrm{\pi \mu }\frac{m\left(m+1\right)}{N_{\mathrm{ZC}}}}{e}^{\frac{j\pi m\mu }{N_{\mathrm{ZC}}}}\right)$$X\left(k\right)=X\left(0\right)e^{\frac{2j\pi \mathrm{mk}\left(k-1\right)}{N_{\mathrm{ZC}}}}{e}^{j\mathrm{\pi \mu }\frac{\mathrm{km}\left(m+1\right)}{N_{\mathrm{ZC}}}}{e}^{\frac{j\pi \mathrm{km}\mu }{N_{\mathrm{ZC}}}}$

(33) If m is such that mμ=1 mod N.sub.ZC does not exist, one can find the smallest integer β such that min{β|β<μ and mμ=β mod N.sub.ZC} in order to minimize the delay, and Equation (3) becomes:

(34) $\begin{array}{cc}X\left(k\right)=X\left(k+\beta \right)e^{\frac{2j\pi \mathrm{mk}}{N_{\mathrm{ZC}}}}{e}^{-j\mathrm{\pi \mu }\frac{m\left(m+1\right)}{N_{\mathrm{ZC}}}}{e}^{\frac{j\mathrm{\pi \mu }m}{N_{\mathrm{ZC}}}}& \left(6\right)\end{array}$

(35) From the μth root of the Zadoff-Chu sequence, random access preambles with zero correlation zones of length N.sub.CS−1 are defined by cyclic shifts according to:

(36) 0$x_{\mu ,v}=x_{\mu }\left(\left(n+C_v\right)\mathrm{mod}{N}_{\mathrm{ZC}}\right)$$x_{\mu }=e^{-j\mathrm{\pi \mu }\frac{n\left(n+1\right)}{N_{\mathrm{ZC}}}}$
for 0≦n≦N.sub.ZC, where

(37) $C_v=\{\begin{array}{ccc}{\mathrm{vN}}_{\mathrm{CS}}& v=0,1,\mathrm{.Math.},.Math.N_{\mathrm{ZC}}/N_{\mathrm{CS}}.Math.-1,N_{\mathrm{CS}}\ne 0& \mathrm{for}\mathrm{unrestricted}\mathrm{sets}\\ 0& N_{\mathrm{CS}}=0& \mathrm{for}\mathrm{unrestricted}\mathrm{sets}\\ d_{\mathrm{start}}.Math.v/n_{\mathrm{shift}}^{\mathrm{RA}}.Math.+\left(v\mathrm{mod}{n}_{\mathrm{shift}}^{\mathrm{RA}}\right)N_{\mathrm{CS}}& v=0,1,\mathrm{.Math.},n_{\mathrm{shift}}^{\mathrm{RA}}{n}_{\mathrm{group}}^{\mathrm{RA}}+{\stackrel{\_}{n}}_{\mathrm{shift}}^{\mathrm{RA}}-1& \mathrm{for}\mathrm{restricted}\mathrm{sets}\end{array}$
and N.sub.CS is signalled by high layers.

(38) The DFT for a Zadoff-Chu sequence of odd length is given by Equation (2) above:

(39) $X_{\mu }\left(k+1\right)=X_{\mu }\left(k\right)e^{\frac{2j\pi \mathrm{mk}}{N_{\mathrm{ZC}}}}{e}^{j\mathrm{\pi \mu }\frac{m\left(m+1\right)}{N_{\mathrm{ZC}}}}$
The DFT of the with cyclically shifted Zadoff-Chu sequence is given by:

(40) $X_{\mu }\left(k\right)=X_{\mu }\left(k\right)e^{\frac{2j\pi C_{v}k}{N_{\mathrm{ZC}}}}.$
Therefore by modifying the recursive equation (2) shown above, one obtains:

(41) $\begin{array}{cc}{X}_{\mu ,v}\left(k+1\right)=X_{\mu ,v}\left(k\right)e^{\frac{2j\pi \mathrm{mk}}{N_{\mathrm{ZC}}}}{e}^{j\mathrm{\pi \mu }\frac{m\left(m+1\right)}{N_{\mathrm{ZC}}}}{e}^{\frac{2j\pi C_{v}k}{N_{\mathrm{ZC}}}}& \left(7\right)\end{array}$
The exponential part of equation 7 for different values of k may be stored in a table at the user equipment, for use as component factors in determining the frequency components of the signal, as described below. Obtaining the exponential part of equation (i.e. a component factor) can then be easily implemented by indexing into the table of component factors which for ease of notation is restricted to a size of N.sub.ZC, which corresponds to 2π with a resolution of 2π/N.sub.ZC. In alternative embodiments, a table of different resolution and length may be used.

(42) In this way the exponential part of equation (7) (referred to herein as the component factor) for different frequency components (k) is calculated and stored in the table. Each frequency component of the signal (X(k+1)) can be calculated using the previously calculated frequency component and a component factor obtained from the table. In other words X(k+1)=X(k)F.sub.k+1, where F.sub.k+1 is the component factor for the frequency component X(k+1) and is given by

(43) $F_{k+1}=e^{\frac{2j\pi \mathrm{mk}}{N_{\mathrm{ZC}}}}{e}^{j\mathrm{\pi \mu }\frac{m\left(m+1\right)}{N_{\mathrm{ZC}}}}{e}^{\frac{2j\pi C_v}{N_{\mathrm{ZC}}}},$
and the values of F.sub.k+1 can be determined by accessing the table in an indexed manner. The value of the exponent

(44) $\left(\mathrm{divided}\mathrm{by}a\mathrm{factor}\mathrm{of}\frac{2\pi j}{N_{\mathrm{ZC}}}\right)$
is used as the index for accessing the table, as described in more detail below.

(45) The values of F.sub.k for the different frequency components (k) in the signal may be calculated at the user equipment 101 and stored in the table. Alternatively, the values of F.sub.k for the different frequency components (k) in the signal may be calculated at an entity other than the user equipment 101 and stored in the table. The values of F.sub.k for the different frequency components (k) in the signal may be calculated before they are needed and stored in the table before they are needed. In this way, when the factors F.sub.k are needed they just need to be looked up from the table rather than calculated. The table is stored in memory of the user equipment.

(46) An embodiment of a method according to the principles of this disclosure is now described with reference to the flow chart of FIG. 2. The method is carried out to implement a DFT, for use in a method of processing signals for transmission on a RACH, e.g. where the signals are RACH preambles. For example, the method may be implemented in the N-point DFT block 104 as shown in the system of FIG. 1.

(47) In step S202 the frequency component X(0) is determined. X(0) may be determined by loading the frequency component from a store. Alternatively, X(0) may be calculated from the signal. Once the frequency component X(0) of the signal has been determined, the other frequency components in the signal can be calculated in a recursive manner using equation (7) above.

(48) In order to begin the recursive method, in step S204, a counter i is set to 1 initially. Then in step S206 the component factor F.sub.i for the ith frequency component of the signal is looked up by indexing the table. Therefore on the first run through of the recursive method the component factor F.sub.1 is obtained from the table. In step S208 the ith frequency component (X(i)) is determined using the previously determined frequency component (X(i−1)) and the component factor for the ith frequency component obtained in step S206. In the first run through of the recursive method the frequency component X(1) is determined by multiplying X(0) with F.sub.1. In this sense, the component factors F.sub.1 stored in the table are multiplying factors. Alternatively, the component factors F.sub.1 stored in the table may be used to obtain the ith frequency component in other ways than by multiplication with a previously determined frequency component. The component factors obtained from the table may be used in conjunction with a previously determined frequency component in any way, as would be apparent to the skilled person, leading to a determination of the ith frequency component of the signal.

(49) In the embodiments described above the component factors F.sub.k are stored in the table. This is a much simpler operation than calculating the DFT for each component factor.

(50) In step S210 the counter i is incremented by 1 and in step S212 it is determined whether the counter i is greater than or equal to the length of the Zadoff-Chu sequence N.sub.ZC. If the counter is greater than or equal to N.sub.ZC then all of the frequency components of the signal have been determined and the process ends in step S214. However, if the counter i is less than N.sub.ZC then the method passes back to step S206 and the next frequency component of the signal is determined. The process continues until all of the frequency components of the signal have been determined.

(51) In this way, a running table index is obtained which is initialised to

(52) $\frac{\mu m\left(m+1\right)}{2}+C_v=I\mathrm{mod}{N}_{\mathrm{ZC}}\mathrm{for}k=0.$
Using this index when accessing the table will return the value of the component factor F.sub.1, given by

(53) $F_1=e^{\frac{2j\pi }{N_{\mathrm{ZC}}}\left(\frac{\mu m\left(m+1\right)}{2}+C_v\right)}$
(see the equation above for F.sub.k+1). This component factor is then multiplied with X(0) to give X(1). The next pass in the recursion requires I to be updated by m as:
m=γ mod N.sub.ZC
I.sub.i+γ=I.sub.i+1 mod N.sub.ZC
where I.sub.i is the index at iteration i. Note that the modulo operation does not need a divide since (I+γ) can never exceed 2N.sub.ZC.

(54) Pseudo code which may be used to implement the above described method will now be described. The pseudo code may be implemented in a computer program product for execution on a computer or other suitable hardware for carrying out the method as described above. Alternatively, the method may be carried out in hardware, rather than in software, as would be apparent to a skilled person.

(55) In the following the notation a=b mod n is equivalent to b=mod(a,n).

(56) The pseudo code may be written as follows:

(57) TABLE-US-00001 load X(0) from a pre computed table or compute X(0) Compute γ = mod(m,Nzc) initialise I to mod(μm(m+1)/2 +Cv,Nzc) for i=1 to Nzc−1   e = load exp from table with index I   X(i)=X(i−1)*e   I=I+γ   If I>=Nzc I=I−Nzc endfor

(58) It will be apparent to a person skilled in the art that using the method described above, as provided for by the pseudo code above, the frequency components X(i) can be determined in a recursive manner, thus requiring less computing power and complexity than performing a conventional Fourier transform to determine the frequency components X(i).

(59) In an alternative embodiment, the computational complexity may be reduced even further. If the signal may be multiplied by a complex constant we can ensure that the frequency component X(0)=1. In this way the first frequency component is set to 1 so it does not need to be computed. Multiplying the signal by a complex constant is equivalent to a scaling introduced in the communication channel 118, which changes neither the received timing nor RACH detection probability nor false alarm probability as determined by the base station 121. Therefore multiplying the signal by a complex constant does not detrimentally affect the use of the signal as a RACH preamble.

(60) Where the signal is multiplied by a complex constant to ensure that the frequency component X(0) is equal to 1, the multiplication of the component factor obtained from the factor table and the previously determined frequency component in the recursive method described above may be avoided altogether. In this case the algorithm may be modified to have the following pseudo code.

(61) TABLE-US-00002 Set X(0) = 1 Compute γ= mod(m,Nzc) Initialise I to mod(μm(m+1)/2 +Cv,Nzc) J=0 for i=1 to Nzc−1   J=J+I   If J>=Nzc, J=J−Nzc   e = load exp from table with index J   X(i)=e   I=I+γ   If I>=Nzc I=I−Nzc endfor

(62) In this alternative embodiment, it can be seen from equation (7) that with X(0) equal to 1, all of the frequency components will equal e.sup.d.sup.i where d.sub.i is different for each of the frequency components X(i). Since e.sup.ae.sup.b=e.sup.a+b, each frequency component can be computed by adding up the indices for all previous frequency components and using the sum of the indices as the index for accessing the table. The pseudo code given above for this alternative embodiment implements this by loading the component factors using the index J where J is the sum of all previously determined indices I.

(63) As would be apparent to the skilled person, a similar implementation approach could be used for the case where N.sub.ZC is even based on Equations 5 and 6.

(64) There have been described above methods of implementing a Fourier transform for use in the signal processing of RACH preambles using the Zadoff-Chu sequence. The methods described above do not use a dedicated Fourier transform algorithm for calculating the frequency components of the signal. This results in reduced complexity and reduced memory requirements. The implementation of the DFT is simplified by using a table-lookup with index computation.

(65) While the specific description is directed towards signal processing of signals using the Zadoff-Chu sequence, it would be apparent to a skilled person that the method could also be applied to any other chirp-like polyphase sequence.

(66) While this invention has been particularly shown and described with reference to embodiments, it will be understood to those skilled in the art that various changes in form and detail may be made without departing from the scope of the invention as defined by the appendant claims.

(67) Those skilled in the art to which this application relates will appreciate that other and further additions, deletions, substitutions and modifications may be made to the described embodiments.