用于将在随机接入信道上发射的信号的傅里叶变换

摘要

用于使用确定信号的多个频率分量的递归方法来处理该信号的方法和设备，该信号是类线性调频多相序列，其中确定多个频率分量的第一频率分量；通过访问因子表来确定分量因子，以用于确定多个频率分量的第二频率分量；以及使用所确定的第一频率分量和所确定的分量因子来确定第二频率分量。

说明书

技术领域

本发明涉及对将在随机接入信道上发射的信号进行处理，更具体地， 涉及信号用作随机接入信道前导的情况。

背景技术

在无线蜂窝通信系统中，在移动终端或用户设备(UE)与基站之间建 立通信的过程称作随机接入。这样的随机接入可使用例如正交频分多址 (OFDM)通信系统或单载波频分多址(SC-FDMA)通信系统中的随机接 入信道(RACH)来实施。随机接入使得能够建立从UE至基站的上行链 路。使用RACH，UE可发送指示UE有数据待发射的通知至网络。在基站 处通知的接收允许基站估计UE的正时，从而实现UE与基站之间的上行 链路同步。

典型地，随机接入信道(RACH)包括测距信号或前导。如本领域所 知，前导设计为允许基站对目标检测内的随机接入尝试和误报警概率进行 检测，以及最小化RACH上冲突的影响。此外，基站应该能够对发送自不 同UE的数个同时的随机前导进行检测，并且正确地估计每个UE的正时。 为了达到该目标，RACH前导应该具有：i)良好的互相关性以虑及不同 的同时的和非同时的RACH前导的准确的正时估计，ii)良好的自相关性 以虑及准确的正时估计，iii)用于同步的和同时的RACH前导的零互相关。

3GPP工作组正对长期演进(LTE)无线网络进行标准化，其也称为演 进的通用陆地无线接入网络(E-UTRAN)。分别选择正交频分多址接入 (OFDMA)接入方案和单载波频分多址接入(SC-FDMA)接入方案用于 E-UTRAN的下行链路(DL)和上行链路(UL)。在物理上行链路共享信 道(PUSCH)中从时间上和频率上复用从不同用户设备(UE)至基站的信 号。在UE没有被UL同步的情况下，UE使用非同步化的物理随机接入信 道(PRACH)来与基站通信，并且作为应答基站提供UL资源和正时提前 信息以允许UE在PUSCH上发射。

3GPP RAN工作组1(WG1)已经对PRACH的基于前导的物理结构 达成一致(如在“3GPP TS 36.211 Evolved Universal Terrestrial Radio Access (E-UTRA)；Physical channels and modulation”中所述)。RAN WG1还对可 并发使用的可用前导的数目达成一致，来使得以基于竞争的方式接入 PRACH的UE之间的冲突概率最小化。已经挑选Zadoff-Chu(ZC)序列 用于针对LTE网络的RACH前导。

Zadoff-Chu序列是当用于无线信号时产生信号的复值数学序列，由此 当例如在基站处恢复信号时，信号的循环移位形式彼此间不互相关。所生 成的尚未移位的Zadoff-Chu序列称为“根序列”。假如，在信号的时域内 看，当信号在UE和基站之间发射时每个循环移位均大于信号的组合的传 播延迟和多路径延迟扩展，那么Zadoff-Chu序列展现出序列的循环移位形 式保持彼此间正交的有用性质。

Zadoff-Chu序列的每个根(μ)的每个位置(n)处的复值由以下公式 给出(对于奇数N_ZC，其中N_ZC是Zadoff-Chu序列的长度)：

$x_{\mu }\left(n\right)=e^{-j\frac{\mathrm{\pi \mu n}(n+1)}{N_{\mathrm{ZC}}}},$

其中0≤n≤N_ZC-1。

所有的RACH前导都由Zadoff-Chu序列的很多根序列的循环移位所 生成，其可以以小区为基础来配置。从UE发射RACH前导至基站，以允 许基站估计和如果需要则调整UE发射的正时。RAN WG1已经同意，共 有64个RACH前导分配用于基站的每个小区。特别是，小区可使用相同 ZC根序列或如果需要使用其他ZC根序列的不同循环移位形式作为RACH 前导。为了最大化某序列长度(N_ZC)的可用的Zadoff-Chu序列的数目， 优选地选择序列长度为质数，并且因此为奇数。典型地，对于LTE， Zadoff-Chu的长度可以是例如839或139，这取决于RACH前导的格式。

对于LTE无线网络中的上行链路，使用SC-FDMA，其为基于离散傅 里叶变换(DFT)扩展OFDM的单载波发射。现在参考图1描述SC-FDMA 的原理。图1示出用户设备101和基站121。用户设备包括用于接收串行 信号、具有串行输入的串行至并行块102。用户设备101进一步包括N点 离散傅里叶变换(DFT)块104、副载波映射块106、M点离散傅里叶逆变 换(IDFT)块108、并行至串行块110、循环前缀(CP)和脉冲整形(PS) 块112、数模转换器(DAC)和射频(RF)转换器块114以及用于在通信 系统的信道118上发射信号的天线116。串行至并行块102具有耦合至N 点DFT块104的并行输入的并行输出。N点DFT块104的并行输出耦合 至副载波映射块106的并行输入。副载波映射块106的并行输出耦合至M 点IDFT块108的并行输入。M点IDFT块108的并行输出耦合至并行至 串行块110的并行输入。并行至串行块110的串行输出耦合至CP和PS块 112的输入。CP和PS块112的输出耦合至DAC和RF转换器块114的输 入。DAC和RF转换器块114的输出耦合至天线116。

基站121包括用于在通信系统的信道118上接收信号的天线120。基 站进一步包括射频(RF)转换器和模数转换器(ADC)块122、移除循环 前缀(CP)块124、串行至并行块126、M点离散傅里叶变换(DFT)块 128、副载波去映射和均衡块130、N点离散傅里叶逆变换(IDFT)块132、 并行至串行块134和用于检测信号的检测块136。

天线120的串行输出耦合至RF转换器和ADC块122的串行输入。 RF转换器和ADC块122的串行输出耦合至移除CP块124的串行输入。 移除CP块124的串行输出耦合至串行至并行块126的串行输入。串行至 并行块的并行输出耦合至M点DFT块128的并行输入。M点DFT块128 的并行输出耦合至副载波去映射和均衡块130的并行输入。副载波去映射 和均衡块130的并行输出耦合至N点IDFT块132的并行输入。N点IDFT 块132的并行输出耦合至并行至串行块134的并行输入。并行至串行块134 的串行输出耦合至检测块136的串行输入。

在操作中，对于UE 101处的LTE上行链路，一批共N个调制符号在 串行至并行块102处接收，并应用作为N点DFT块104的并行输入。N 点DFT块104执行针对调制符号的离散傅里叶变换，并且随后N点DFT 块104的输出经由副载波映射块106应用于M点IFFT块108(其中，M＞N) 的连续输入。M点IDFT块108的输出由并行至串行块110转换为串行信 号，并且循环前缀应用于CP和PS块112中的每批串行信号。在使用天线 116通过信道118发射信号至基站121的天线120之前，信号转换为模拟 信号并在DAC和RF转换器块114中在射频进行调制。

在基站121的天线120处所接收的信号在RF转换器和ADC块122 中解调并转换为数字信号。在移除CP块124中移除循环前缀。随后在M 点DFT块128执行信号的离散傅里叶变换前，由串行至并行块126将该信 号转换为并行信号。在由N点IDFT块132执行信号的离散傅里叶逆变换 前，副载波去映射和均衡块130去映射并均衡M点DFT块128的输出。 在N点IDFT块132的输出传递至检测块136用于检测前，由并行至串行 块134将其转换为串行信号。

典型地，由于对于RACH前导，需要采用大小为N＝839或139的DFT (取决于前导的格式)，因此依据计算复杂度和存储器来要求在N点DFT 块104中执行的操作。用于实施DFT的大小为质数的DFT的一种方法是 Bluestein算法(Leo I.Bluestein，″A linear filtering approach to the computation  of the discrete Fourier transform，″Northeast Electronics Research and  Engineering Meeting Record 10，218-219(1968))。在Bluestein算法中， DFT重新表示为卷积，其提供具有O(NlogN)阶的计算复杂度的计算质数大 小的DFT的方法。

本发明的主要目的在于，减小执行质数DFT所要求的计算复杂度，该 质数DFT用于处理将在随机接入信道中发射的信号。

发明内容

根据本发明的第一方面，提供处理将在随机接入信道上发射的信号的 方法，该信号为类线性调频(chirp-like)多相序列，该方法为用于确定 信号的多个频率分量的递归方法，其包括：确定多个频率分量的第一频率 分量；通过访问因子表来确定分量因子，以用于确定多个频率分量的第二 频率分量；以及使用所确定的第一频率分量和所确定的分量因子来确定第 二频率分量。

根据本发明的第二方面，提供用于使用确定将在随机接入信道上发射 的信号的多个频率分量的递归方法来处理所述信号的设备，该信号为 chirp-like多相序列，该设备包括：用于确定多个频率分量的第一频率分 量的装置；用于通过访问因子表来确定分量因子以用于确定多个频率分量 的第二频率分量的装置；以及用于使用所确定的第一频率分量和所确定的 分量因子来确定第二频率分量的装置。

根据本发明的第三方面提供一种计算机程序产品，其包括用于在计算 机上执行的计算机可读指令，该指令用于处理将在随机接入信道上发射的 信号，该信号为chirp-like多相序列，该指令包括用于执行确定信号的多 个频率分量的递归方法的指令，所述递归方法包括以下步骤：确定多个频 率分量的第一频率分量；通过访问因子表来确定分量因子，以用于确定多 个频率分量的第二频率分量；以及使用所确定的第一频率分量和所确定的 分量因子来确定第二频率分量。

提供一种Zadoff-Chu序列(或任意其他chirp-like多相序列)的DFT 的有效实施方式，其无需执行傅里叶变换。该方法使用递归关系，复杂度 减小。由于已经选择Zadoff-Chu序列用于LTE无线网络中的RACH前导， 因此针对Zadoff-Chu序列复杂度减小的实施傅里叶变换的能力是特别有 益的。然而，注意到该方法适用于是chirp-like多相序列的任意信号。 Zadoff-Chu序列仅是chirp-like多相序列的一个范例。如对于技术人员 显然的是，chirp-like多相序列具有理想的周期性的自相关函数。对于 chirp-like多相序列的详细内容可在1992年7月的IEEE Transactions on  Information Theory，第38卷第4期，第1406至1409页Branislav M. 的“Generalized Chirp-Like Polyphase Sequences with optimum  Correlation Properties”文中找到。在该引用文章中描述了Zadoff-Chu 序列、Frank序列和Ipatov序列都为chirp-like多相序列。

通过用简单索引计算使用查找表减小了实施傅里叶变换的复杂度。这 样的索引要求比执行常规DFT更小的处理能力。可以在UE处存储该表。可 以由UE计算表中的分量因子。可替代地，存储在表中的分量因子可以由除 UE外的实体来计算并传递至UE用于储存于其上。

附图说明

为了更好地理解本发明并示出相同情况可以如何实施，通过示例的方 式参考以下附图，其中：

图1是SC-FDMA通信系统的示意图；以及

图2是根据优选实施例对信号进行处理的过程流程图。

具体实施方式

在描述本发明的优选实施例前，提供在优选实施例中使用的等式的推 导以促进对本发明的理解。

如上所述，Zadoff-Chu序列(针对奇数N_ZC)定义为

$x\left(n\right)=e^{-j\frac{\mathrm{\pi \mu n}(n+1)}{N_{\mathrm{ZC}}}}$

$x\left(n\right)=e^{\left(\frac{2\mathrm{j\pi \mu }{\Sigma }_{i=1}^{n}i}{N_{\mathrm{ZC}}}\right)}$

$x\left(n\right)=\underset{i=1}{\overset{n}{\Pi }}{e}^{\left(\frac{2\mathrm{j\pi \mu i}}{N_{\mathrm{ZC}}}\right)}$

其中已经使用${\Sigma }_{i=1}^{n}i=\frac{n(n+1)}{2}.$

这可重写为递归等式，使得：

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

对以上关系进行离散傅里叶变换，并使用DFT性质，得到：

$X\left(k\right)=X(k+\mu )e^{-\frac{2\mathrm{j\pi }(\mu +k)}{N_{\mathrm{ZC}}}}---\left(1\right)$

其中X(k)是x(n)的离散傅里叶变换。

基于等式(1)，可以使用DFT的移位性质递归地写：

$X\left(k\right)=X(k+\mu )e^{(-\frac{2\mathrm{j\pi }(\mu +k)}{N_{\mathrm{SC}}})}$

$=X(k+2\mu )e^{(-\frac{2\mathrm{j\pi }(\mu +k)}{N_{\mathrm{ZC}}})}{e}^{(-\frac{2\mathrm{j\pi }(2\mu +k)}{N_{\mathrm{ZC}}})}$

$\left(\begin{array}{c}.\\ .\\ .\end{array}\right)$

$=X(k+\mathrm{m\mu })e^{(-\frac{2\mathrm{j\pi }{\Sigma }_{l=1}^m(k+\mathrm{l\mu })}{N_{\mathrm{ZC}}})}$

$=X(k+\mathrm{m\mu })e^{-\frac{2\mathrm{j\pi mk}}{N_{\mathrm{ZC}}}}{e}^{-\mathrm{j\pi \mu }\frac{m(m+1)}{N_{\mathrm{ZC}}}}$

引入以下表示法。如果两个整数a和b的差a-b是n的整数倍数，那 么整数a和b称为对于模数n同余。等价(equivalent)定义是，两个数当 除以n时具有相同的余数。如果是这样的情况，其表示为：

a＝bmodn

选择m，使得mμ＝1modN_ZC。由于N_ZC和μ是由Zadoff-Chu序列构建 的互质数(即，除了1以外，它们没有共同的正数因子，或除数)，因此总 是存在m。然后，根据DFT的周期性性质：

X(k+mμ)＝X(k+1)

获得最后结果为：

$X(k+1)=X\left(k\right)e^{\frac{2\mathrm{j\pi mk}}{N_{\mathrm{ZC}}}}{e}^{\mathrm{j\pi \mu }\frac{m(m+1)}{N_{\mathrm{ZC}}}}---\left(2\right)$

其中

$X\left(0\right)={\Sigma }_{n=0}^{N_{\mathrm{ZC}}-1}{e}^{-\mathrm{j\pi \mu }\frac{n(n+1)}{N_{\mathrm{ZC}}}}.$

由等式(2)，可以得到X(k)的表达为：

$X\left(k\right)=X(k-1)e^{\frac{2\mathrm{j\pi m}(k-1)}{N_{\mathrm{ZC}}}}{e}^{\mathrm{j\pi \mu }\frac{m(m+1)}{N_{\mathrm{ZC}}}}$

通过递归得到：

$X\left(k\right)=X(k-2)e^{\frac{2\mathrm{j\pi m}(k-2)}{N_{\mathrm{ZC}}}}{e}^{\mathrm{j\pi \mu }\frac{m(m+1)}{N_{\mathrm{ZC}}}}{e}^{\frac{2\mathrm{j\pi m}(k-1)}{N_{\mathrm{ZC}}}}{e}^{\mathrm{j\pi \mu }\frac{m(m+1)}{N_{\mathrm{ZC}}}}$

其得到：

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

并最终得到结果：

$X\left(k\right)=X\left(0\right)e^{\frac{2\mathrm{j\pi mk}(k-1)}{N_{\mathrm{ZC}}}}{e}^{\mathrm{j\pi \mu }\frac{\mathrm{km}(m+1)}{N_{\mathrm{ZC}}}}---\left(3\right)$

在N_ZC是偶数的情况下，Zadoff-Chu序列给出如下：

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

可通过归纳证明示出：

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

与以上推导类似，获得：

$X\left(k\right)=X(k+\mu )e^{-\frac{2\mathrm{j\pi }(\mu +k)}{N_{\mathrm{ZC}}}}{e}^{-\frac{\mathrm{j\pi \mu }}{N_{\mathrm{ZC}}}}---\left(4\right)$

其得到：

$X\left(k\right)=X(k+\mathrm{m\mu })\underset{l=1}{\overset{m}{\Pi }}{e}^{-\frac{2\mathrm{j\pi }(\mathrm{l\mu }+k)}{N_{\mathrm{ZC}}}}{e}^{-\frac{\mathrm{j\pi \mu }}{N_{\mathrm{ZC}}}}$

$X\left(k\right)=X(k+\mathrm{m\mu })e^{-\frac{2\mathrm{j\pi mk}}{N_{\mathrm{ZC}}}}{e}^{-\mathrm{j\pi \mu }\frac{m(m+1)}{N_{\mathrm{ZC}}}}{e}^{-\frac{\mathrm{j\pi m\mu }}{N_{\mathrm{ZC}}}}$

如果m使得mμ＝1modN_ZC存在，那么可重写以上等式为：

$X\left(k\right)=X(k+1)e^{-\frac{2\mathrm{j\pi mk}}{N_{\mathrm{ZC}}}}{e}^{-\mathrm{j\pi \mu }\frac{m(m+1)}{N_{\mathrm{ZC}}}}{e}^{-\frac{\mathrm{j\pi m\mu }}{N_{\mathrm{ZC}}}}---\left(5\right)$

X(k)可表示为(如果m使得mμ＝1modN_ZC存在)：

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

$X\left(k\right)=X{\left(0\right)e}^{\frac{\mathrm{j\pi mk}(k-1)}{N_{\mathrm{ZC}}}}{e}^{\mathrm{j\pi \mu }\frac{\mathrm{km}(m+1)}{N_{\mathrm{ZC}}}}{e}^{\frac{\mathrm{j\pi km\mu }}{N_{\mathrm{ZC}}}}$

如果m使得mμ＝1modN_ZC不存在，可找到最小整数β使得min{β|β＜μ 且mμ＝βmodN_ZC }以最小化延迟，并且等式(3)成为：

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

由Zadoff-Chu序列的第μ个根，具有长度为N_CS-1的零相关区的随 机接入前导由根据以下公式的循环移位定义：

x_μ，v＝x_μ((n+C_v)modN_ZC)

$x_{\mu }\left(n\right)=e^{-\mathrm{j\pi \mu }\frac{n(n+1)}{N_{\mathrm{ZC}}}}$

对于0≤n≤N_ZC，其中

并且N_CS由高层标志。

用于奇数长度的Zadoff-Chu序列的DFT由以上等式(2)给出：

$X_{\mu }(k+1)=X_{\mu }\left(k\right)e^{\frac{2\mathrm{j\pi mk}}{N_{\mathrm{ZC}}}}{e}^{\mathrm{j\pi \mu }\frac{m(m+1)}{N_{\mathrm{ZC}}}}$

经第v个循环移位的Zadoff-Chu序列的DFT由以下公式给出：

$X_{\mu ,v}\left(k\right)=X_{\mu }\left(k\right)e^{\frac{2\mathrm{j\pi }{C}_{v}k}{N_{\mathrm{ZC}}}}$

因此通过修改以上所示的递归等式(2)，获得：

$X_{\mu ,v}(k+1)=X_{\mu ,v}\left(k\right)e^{\frac{2\mathrm{j\pi mk}}{N_{\mathrm{ZC}}}}{e}^{\mathrm{j\pi \mu }\frac{m(m+1)}{N_{\mathrm{ZC}}}}{e}^{\frac{2\mathrm{j\pi }{C}_{v}k}{N_{\mathrm{ZC}}}}---\left(7\right)$

如下所述，用于不同k值的等式7的指数部分可以存储在用户设备处 的表中，用作确定信号的频率分量的分量因子。随后通过索引到分量因子 表中来容易地实现获得等式7的指数部分(即，分量因子)，为便于表示该 分量因子的表限制至N_ZC的大小，其对应于具有2π/N_ZC解析度的2π。在可 替代实施例中，可以使用不同解析度和长度的表。

以这种方式，用于不同频率分量(k)的等式(7)的指数部分(本文 称之为分量因子)被计算并存储在表中。使用在先计算的频率分量和从表 中获得的分量因子，可计算信号(X(k+1))的每个频率分量。换言之 X(k+1)＝X(k)F_k+1，其中F_k+1是用于频率分量X(k+1)的分量因子且由 给出，并且F_k+1的值可通过以索引的方式访问表来确 定。如下更详细的描述，指数的值(除以因子)用作访问表的索引。 用于信号中的不同频率分量(k)的F_k的值可以在用户设备101处计算并 存储在表中。可替代地，用于信号中的不同频率分量(k)的F_k的值可以 在除用户设备101以外的实体处计算并存储在表中。用于信号中不同频率 分量(k)的F_k的值可以在需要前计算并且在需要前存储在表中。以这种 方式，当需要因子F_k时仅需要从表中查找而不是进行计算。表存储在用户 设备的存储器中。

现参考图2的流程图来描述根据优选实施例实现本发明的方法。实现 本方法以实施DFT，以用于处理用于在RACH上发射的信号的方法中，该 RACH例如其中信号是RACH前导。例如，可以在如图1的系统中所示的 N点DFT块104中实施该方法。

在步骤S202，确定频率分量X(0)。可以通过从存储设备加载频率分 量来确定X(0)。可替代地，可以根据信号计算X(0)。一旦已经确定了 信号的频率分量X(0)，可使用以上等式(7)通过递归方式计算信号中的 其他频率分量。

为了开始递归方法，在步骤S204，计数器i最初设置为1。然后在步 骤S206，通过对表进行索引来查找用于信号的第i个频率分量的分量因子 F_i。因此，在第一次运行递归方法时从表中获得分量因子F₁。在步骤S208， 使用在先确定的频率分量(X(i-1))和在步骤S206获得的用于第i个频 率分量的分量因子来确定第i个频率分量(X(i))。在第一次运行递归方 法时，通过X(0)乘以F₁来确定频率分量X(1)。在该意义上，存储在 表中的分量因子F_i是乘因子。可替代地，存储在表中的分量因子F_i可以用 于以通过和在先确定的频率分量相乘的方式以外的其他方式来获得第i个 频率分量。如对于技术人员显而易见的，从表中获得的分量因子可以通过 任意方式和在先确定的频率分量结合，来确定信号的第i个频率分量。

在上述实施例中，分量因子F_k存储在表中。这是比针对每个分量因子 计算DFT更简单的操作。

在步骤S210，计数器i增加1，并且在步骤S212确定计数器i是否大 于或等于Zadoff-Chu序列的长度N_ZC。如果计数器大于或等于N_ZC，那么 信号的所有频率分量都已经确定，并且过程在步骤S214结束。然而，如果 计数器i小于N_ZC，那么方法回到步骤S206，并且确定信号的下一个频率 分量。继续过程直到信号的所有频率分量都已经确定。

以这种方式，获得运行表索引，其被初始化为：对于k＝0， 当访问表时使用该索引将返回分量因子F₁的值， 其由(参见以上用于F_k+1的等式)给出。随后该分量因子 乘以X(0)来给出X(1)。递归中的下一次传递要求通过m来更新I，如 下：

m＝γmodN_ZC

I_i+γ＝I_i+1modN_ZC

其中I_i是迭代i的索引。注意到，由于(I+γ)从不会超过2N_ZC，因此取 模操作不需要除(divide)。

现在将对可用于实施上述方法的伪代码进行描述。伪代码可实现在计 算机程序产品中，其用于在计算机或用于执行如上所述的方法的其他合适 硬件上执行。可替代地，如对技术人员显而易见的，除了软件外可以以硬 件实现该方法。

在下文中表示法a＝bmodn等价于b＝mod(a，n)。

伪代码可按如下编写：

对于本领域技术人员将显而易见的是，使用上述方法，如通过以上伪 代码所提供的，可通过递归方式来确定频率分量X(i)，因此比执行常规 傅里叶变换来确定频率分量X(i)要求更小的计算能力和复杂度。

在可替代的实施例中，甚至可以进一步减小计算复杂度。如果信号可 乘以复数型常数，可确保频率分量X(0)＝1。以这种方式，第一频率分量 设置为1，从而不需要计算它。由复数型常数乘以信号等价于在通信信道 118中引入缩放(scaling)，其不改变如由基站121所确定的接收到的正时， 或RACH检测概率或误报警概率。因此由复数型常数乘以信号不会不利地 影响信号作为RACH前导使用。

在由复数型常数乘以信号以确保频率分量X(0)等于1的情况下， 可以完全避免在上述递归方法中从因子表获得的分量因子与在先确定的频 率分量相乘。在这种情况下，算法可修改为具有以下伪代码：

在该可替代实施例中，可以从X(0)等于1的等式(7)看出，所有 频率分量将等于其中用于每个频率分量X(i)的d_i是不同的。由于 e^ae^b＝e^a+b，因此可以通过将所有在先频率分量的指数相加并且使用指数的 和作为访问表的索引来计算每个频率分量。通过使用索引J来加载分量因 子，其中J是所有在先确定的索引I的和，以上针对该可替代实施例而给 出的伪代码实现了该方法。

如对于技术人员显而易见的，类似的实现方法可用于基于等式5和6 N_ZC是偶数的情况。

以上已经描述了实施傅里叶变换的方法，用于使用Zadoff-Chu序列的 RACH前导的信号处理中。上述方法不使用用于计算信号的频率分量的专 用的傅里叶变换算法。这使得复杂度和存储器要求减小。通过使用表查找 和索引计算，简化了DFT的实施。

虽然具体的描述是针对使用Zadoff-Chu序列的信号的信号处理，对于 技术人员将显而易见的是，该方法还可应用于任何其他的chirp-like多相序 列。

虽然参考优选实施例具体地示出和描述本发明，本领域技术人员将理 解，可以进行形式上和细节上的各种改变，而如不脱离所附权利要求所限 定的本发明的范围。