恒模序列的离散傅立叶变换的快速计算方法和装置

摘要

本发明涉及一种恒模序列的离散傅立叶变换的快速计算方法，包括：根据ZC序列的根序列号获取第一参数值；根据所获取的第一参数值、ZC序列长度和循环移位值获得第一序列的初始值；根据第一序列的初始值和第一参数值进行第一序列的迭代计算；根据第一序列的迭代计算后的值和预设的第二序列的初始值对第二序列的进行迭代计算；根据第二序列的迭代计算后的值获得DFT变换。本发明还提供一种恒模序列的离散傅立叶变换的快速计算装置。本发明可以实现计算过程的很低的复杂度和较高的计算精度，并且可以大大降低计算处理量和存储量。

说明书

技术领域

本发明涉及通信技术领域，尤其涉及恒模序列的离散傅立叶变换的快速 计算方法和装置。

背景技术

在3.9G和4G通信系统中，正交频分复用(Orthogonal Frequency Division Multiplexing，OFDM)已经成为一种广泛应用的技术。在3GPP组织定义的 下一代移动通信系统(Long Term Evolution，LTE)上行链路中，用户设备(User Equipment，UE)采用单载波频分多址(single carrier Frequency Division Multiple Access，SC-FDMA)技术，一方面继承了OFDM各子载波之间正交特性，另 一方面也克服了OFDM技术峰均比(Peak to Average Power Ratio，PAPR)较 大的问题，从而可达到提高功率放大器效率、达到降低UE功耗的目的。LTE 系统中，随机接入过程中的前导序列采用了恒模序列(Zadoff-Chu，ZC)。ZC 序列是一种具有恒包络零自相关序列(Constant Amplitude Zero Auto-Correlation，CAZAC)性质的序列，具有以下两方面特点：(1)序列的 自相关特性和互相关特性良好，特别的当序列长度为质数时，具有理想的自 相关和互相关特性，这样系统中两个用户采用不同的ZC序列、或者同一序列 的不同循环移位进行接入时，相互之间的干扰都很小；(2)具有时域和频域 都是恒模特性，具有较低的PAPR，因此适合于在上行链路中使用。

LTE系统中，分别采用了长度为N_ZC＝839(format 0～3，)和N_ZC＝139(format 4)的时域ZC根序列x_u(n)，其中下标u代表了根序列号：

$x_u\left(n\right)=\exp \{-j\frac{\pi ·u·n(n+1)}{N_{\mathrm{ZC}}}\},$0≤n≤N_ZC-1

UE采用的前导序列是上述ZC根序列的某个其循环移位，其中循环移位 值τ由网络指示：

$x_u^{\tau }\left(n\right)=x_u\left((n+\tau )\mathrm{mod}{N}_{\mathrm{ZC}}\right)$

然后，上述前导序列通过一次N_ZC点的离散傅立叶变换(Discrete Fourier Transform，DFT)到频域，并通过子载波映射模块、插入循环前缀(cyclic prefix， CP)模块和应用功率增益因子(β_PRACH)后在前导发送模块上的PRACH信道 上发射。在LTE系统中一种随机接入前导的生成过程参见图1。

上述过程中，如何计算经过循环移位ZC序列的DFT变换，是前导生成 过程的关键技术点之一。由于ZC序列的长度为质数，因此其DFT无法采用 常规FFT方法实现，因为常规FFT一般要求序列长度可分解，然后采用基-2、 基-3、基-4等模块的串联来实现。如果直接采用DFT来计算，其计算复杂度 将是十分庞大的。业界的一般处理方法是利用ZC序列本身的一些特性，来避 免直接的DFT计算。例如，对于循环移位ZC序列的DFT变换如下公式成立(针对循环移位情况做了扩展)：

$X_u^{\tau }\left(k\right)=\mathrm{DFT}\left[x_u^{\tau }\left(n\right)\right]=C·x_u\left(\tau \right)·\mathrm{conj}\left[x_u\left((k·\Delta +\tau )\mathrm{mod}{N}_{\mathrm{ZC}}\right)\right]$

其中，C是一个复常数，其模值满足而Δ＝u^-1mod N_ZC，即满足 (Δ·u)modN_ZC＝1，其中Δ∈[0，N_ZC-1]是一个非负整数。由于前导发射进行一个固 定的相位旋转并不影响前导在基站处的检测，并且固定的增益可在前导发射 功率控制中体现，因此后述前导生成过程中忽略复常数C。

基于上述公式，可见ZC序列的DFT变换，可看作是一个复数x_u(τ)与另 一个ZC序列x_u((k·Δ+τ)mod N_ZC)的共轭相乘后得到的结果。这样可避免复杂的 DFT变换，只需要计算x_u(τ)和ZC序列x_u((k·Δ+τ)modN_ZC)即可，其中，变量u、 k、Δ和τ均是取值范围是[0，N_ZC-1]的非负整数，这里：

$x_u\left(\tau \right)=\exp \{-j\frac{\pi ·u·\tau (\tau +1)}{N_{\mathrm{ZC}}}\}$

$\mathrm{conj}\left[x_u\left((k·\Delta +\tau )\mathrm{mod}{N}_{\mathrm{ZC}}\right)\right]=\exp \{\mathrm{j\pi }·\frac{u·\left[(k·\Delta +\tau )(k·\Delta +\tau +1)\right]}{N_{\mathrm{ZC}}}\}$

但是，为了计算序列conj[x_u((k·Δ+τ)modN_ZC)]，仍然需要相位因子项 u·[(k·Δ+τ)(k·Δ+τ+1)]，还是涉及了大量比较复杂的乘法和求模运算，因而此种 算法的复杂度依然很复杂。

发明内容

本发明的目的在于提供恒模序列的离散傅立叶变换的快速计算方法和装 置，采用两重迭代方法计算，可以实现计算过程的复杂度很低和高的计算精 率，并且可以大大降低计算处理量和存储量。

本发明提供一种恒模序列的离散傅立叶变换的快速计算方法，包括：根 据ZC序列的根序列号获取第一参数值；根据所获取的第一参数值、ZC序列 长度和循环移位值获得第一序列的初始值；根据第一序列的初始值和第一参 数值进行第一序列的迭代计算；根据第一序列的迭代计算后的值和预设的第 二序列的初始值对第二序列的进行迭代计算；根据第二序列的迭代计算后的 值获得DFT变换。

优选地，上述根据ZC序列的根序列号获取第一参数值的步骤包括：以 ZC序列的根序列号作为索引值查找第一数据表得到第一参数值，其中，第一 数据表存储为Δ＝u^-1modN_ZC，0≤u≤N_ZC-1，Δ取值范围为[0，N_ZC-1]中的整数。

优选地，上述根据所获取的第一参数值、ZC序列长度和循环移位值获得 第一序列的初始值的步骤包括：若获取的第一参数值为奇数，则通过 (τ+(Δ+1)/2)modN_ZC获得第一序列的初始值，其中，τ表示循环移位值，Δ表示 第一参数值，N_ZC表示ZC序列长度；若获取的第一参数值不为奇数，则通过 (τ+(Δ+1+N_ZC)/2)modN_ZC获得第一序列的初始值。

优选地，上述根据第一序列的初始值和第一参数值进行第一序列的迭代 计算的步骤包括：据第一序列的初始值和第一参数值进行第一序列的第一次 迭代计算；之后，根据第k-1次迭代计算后的值和第一参数进行第k次迭代计 算。

优选地，上述根据第一序列的初始值和第一参数值进行第一序列的第一 次迭代计算的步骤包括：通过(B(0)+Δ)modN_ZC来计算第一序列的第一次迭代计 算，其中，B(0)表示第一序列的初始值。

优选地，上述根据第k-1次迭代计算后的值和第一参数进行第k次迭代计 算的步骤包括：通过(B(k-1)+Δ)modN_ZC计算第k次迭代计算，其中，B(k-1)表 示第k-1次迭代计算后的值，其中k≥1为一个正整数，小于等于N_ZC-1。

优选地，上述根据第一序列的迭代计算后的值和预设的第二序列的初始 值对第二序列的进行迭代计算的步骤包括：根据第一序列的初始值和预设的 第二序列的初始值进行第二序列的第一次迭代计算；之后，根据第二序列的 第k-1次迭代计算后值和第一序列的第k-1次迭代计算后的值进行第二序列的 第k次迭代计算。

优选地，上述根据第一序列的初始值和预设的第二序列的初始值进行第 二序列的第一次迭代计算的步骤包括：通过(Y(0)+B(0))modN_ZC计算第二序列的 第一次迭代计算，其中，Y(0)表示预设的第二序列的初始值。

优选地，上述根据第二序列的第k-1次迭代计算后值和第一序列的第k-1 次迭代计算后的值进行第二序列的第k次迭代计算的步骤包括：通过 (Y(k-1)+B(k-1))modN_ZC计算第二序列的第k次迭代计算，Y(k-1)表示第二序列 的第k-1次迭代计算后值，其中k≥1为一个正整数，小于等于N_ZC-1。

优选地，上述根据第二序列的迭代计算后的值获得DFT变换的步骤包括： 判断第二序列的第k次迭代计算后的值是否小于等于(N_ZC-1)/2；若判断小于 等于(N_ZC-1)/2时，根据第二序列的第k次迭代计算后值作为索引直接查找第 二数据表得到DFT变换输出；若判断大于(N_ZC-1)/2时，将N_ZC减去第二序列 的第k次迭代计算后的值作为索引值查找第二数据表得到DFT变换输出。 优选地，上述第二数据表中存储为其中n∈[0，(N_ZC-1)/2]为 非负整数。

本发明还提供一种恒模序列的离散傅立叶变换的快速计算装置，包括： 第一查询模块用于根据ZC序列的根序列号获取第一参数值；初始值计算模块 与第一查询模块连接，用于根据所获取的第一参数值、ZC序列长度和循环移 位值获得第一序列的初始值；第一存储模块与初始值计算模块连接，用于存 储第一序列的初始值；第一取模加法器与第一存储模块和第一存储模块连接， 用于根据第一序列的初始值和第一参数值进行第一序列的迭代计算，并存储 于第一存储模块；第二取模块加法器与第一存储模块连接，用于根据第一存 储模块存储的第一序列的迭代计算后的值和预设的第二序列的初始值对第二 序列的进行迭代计算；第二查询模块用于根据第二序列的迭代计算后的值获 得DFT变换。

优选地，上述恒模序列的离散傅立叶变换的快速计算装置还包括：第一 数据库用于存储构造的第一数据表，第一数据表中存储内容为Δ＝u^-1modN_ZC， 0≤u≤N_ZC-1，Δ取值范围为[0，N_ZC-1]中的整数；第一查询模块进一步用于以 ZC序列的根序列号作为索引值查找Δ-ROM表得到第一参数值。

优选地，上述初始值计算模块进一步用于当获取的第一参数值为奇数时， 通过(τ+(Δ+1)/2)modN_ZC来获得则第一序列的初始值，或进一步用于当获取的 第一参数值不为奇数时，通过(τ+(Δ+1+N_ZC)/2)modN_ZC来获得第一序列的初始 值。

优选地，上述第一取模加法器进一步用于根据第一存储模块存储的第一 序列的初始值和第一参数值进行第一序列的第一次迭代计算，并存储于第一 存储模块，其中，第一取模加法器进一步用于通过(B(0)+Δ)modN_ZC来计算第一 序列的第一次迭代计算，其中，B(0)表示第一序列的初始值。

优选地，上述第一取模加法器进一步用于根据第一存储模块存储的第k-1 次迭代计算后的值和第一参数进行第k次迭代计算，并存储于第一存储模块， 其中，第一取模加法器进一步用于通过(B(k-1)+Δ)modN_ZC计算第k次迭代计 算，其中，B(k-1)表示第k-1次迭代计算后的值，其中k≥1为一个正整数，小 于等于N_ZC-1。

优选地，上述第二取模块加法器进一步用于根据第一存储模块存储的第 一序列的初始值和预设的第二序列的初始值进行第二序列的第一次迭代计 算，进一步用于通过(Y(0)+B(0))modN_ZC计算第二序列的第一次迭代计算，其中， Y(0)表示预设的第二序列的初始值。

优选地，上述第二取模块加法器进一步用于根据第一存储模块存储的第 二序列的第k-1次迭代计算后值和第一序列的第k-1次迭代计算后的值进行第 二序列的第k次迭代计算，进一步用于通过(Y(k-1)+B(k-1))modN_ZC计算第二 序列的第k次迭代计算，Y(k-1)表示第二序列的第k-1次迭代计算后值，其中 k≥1为一个正整数，小于等于N_ZC-1。

优选地，上述恒模序列的离散傅立叶变换的快速计算装置还包括：第二 存储模块与第二取模块加法器连接，用于存储第二取模块加法器的第k-1次迭 代计算后值；第二查询模块进一步用于判断第二序列的第k次迭代计算后的 值是否小于等于(N_ZC-1)/2。

优选地，上述恒模序列的离散傅立叶变换的快速计算装置还包括：第二 数据库，用于存储构造的第二数据表，第二数据表中存储为其 中n∈[0，(N_ZC-1)/2]为非负整数；第二查询模块进一步用于当判断小于等于 (N_ZC-1)/2时，根据第二序列的第k次迭代计算后值作为索引直接查找第二数 据库中的第二数据表得到DFT变换输出；或当判断大于(N_ZC-1)/2时，将N_ZC减 去第二序列的第k次迭代计算后的值作为索引值查找第二数据库中的第二数 据表，并将查表结果共轭后得到DFT变换输出。

本发明实施例所提供的恒模序列的离散傅立叶变换的快速计算方法及装 置，在计算过程中，采用两重迭代方法计算，只涉及整数加，减、比较和查 表操作，不涉及定点处理损失，相对于现有技术而言，可以实现计算过程的 很低复杂度和较高的计算精度，并且可以大大降低计算处理量和存储量。

附图说明

图1为现有技术中LTE系统中一种随机接入前导的生成过程的示意图；

图2为本发明ZC序列的DFT的快速计算方法一实施例的流程示意图；

图3为本发明ZC序列的DFT的快速计算装置一实施例的结构示意图；

图4为本发明ZC序列的DFT的快速计算装置中图3的初始化计算模块 的结构示意图；

图5为图4所示的初始化计算模块的具体电路图；

图6为本发明ZC序列的DFT的快速计算装置中图3的取模加法器的结 构示意图；

图7为图6所示的取模加法器的具体电路图。

具体实施方式

本发明总的技术方案为：本发明充分利用ZC序列的特性，通过两重迭代 的方法来计算其DFT，并且无须乘法计算，只通过简单的加法和移位计算就 可以完成ZC序列(带循环移位)DFT变换的快速计算。

在本实施例中，本发明实施例提供的ZC序列的DFT的快速计算方法可 以通过下面的步骤来实现：

步骤A：根据ZC序列的根序列号获取第一参数值；

步骤B：根据所获取的第一参数值、ZC序列长度和循环移位值获得第一 序列的初始值；

步骤C：根据第一序列的初始值和第一参数值进行第一序列的迭代计算；

步骤D：根据第一序列的迭代计算后的值和预设的第二序列的初始值对 第二序列的进行迭代计算；

步骤F：根据第二序列的迭代计算后的值获得DFT变换。

本发明实施例所提供的ZC序列的DFT的快速计算方法，在计算过程中， 采用两重迭代方法计算，只涉及整数加，减、比较和查表操作，不涉及定点 处理损失，相对于现有技术而言，可以实现计算过程的复杂度很低和高的计 算精率，并且可以大大降低计算处理量和存储量，适合与高效率的软件或硬 件处理需求。本发明可应用于LTE移动通信系统中终端或基站中随机接入前 导(preamble)序列生成过程中DFT的计算。

下面结合附图和具体实施例对本发明技术方案作进一步用于的详细描 述，以使本领域的技术人员可以更好的理解本发明并能予以实施，但所举实 施例不作为对本发明的限定。

图2为本发明ZC序列的DFT的快速计算方法一实施例的流程示意图。

在本实施例中，在执行本发明的方法之前，可以先构造并存储两个只读 内存(Read-Only Memory，ROM)表，可以分别为含有(N_ZC+1)/2个元素的 exp-ROM表和Δ-ROM表。在本实施例中，第一数据表可以为Δ-ROM表，第二 数据表可以为exp-ROM表，exp-ROM表中存储项为：

其中n∈[0，(N_ZC-1)/2]为非负整数，Δ-ROM表中存储内容项 为Δ＝u^-1modN_ZC，依次对应0≤u≤N_ZC-1，Δ取值范围为[0，N_ZC-1]中的整数， 该表中对应N_ZC个的可能取值u，存储了对应的共N_ZC个Δ值。。在本实施例中， u表示ZC序列的根序列号，N_ZC表示ZC序列的长度，在LTE系统中取值为839 (前导格式0～3)或139(前导格式4)。

步骤S201，根据ZC序列的根序列号u获取第一参数值。在本实例中，第 一参数值可以用Δ来表示。在本实施例中，可以以ZC序列的根序列号u作为索 引值查Δ-ROM表得到Δ值。

步骤S203，根据所获取的第一参数值、ZC序列长度和循环移位值获得第 一序列的初始值。在本实施例中，循环移位值用τ表示，第一序列可以用{B(k)} 来表示，其中该序列的初始值可以用B(0)来表示，可以表示为根据Δ值，N_ZC和 τ来获得B(0)。在本实施例中，若Δ为奇数，则B(0)←(τ+(Δ+1)/2)modN_ZC，可 以理解为，B(0)可以通过(τ+(Δ+1)/2)modN_ZC来获得，若Δ不为奇数，则 B(0)←(τ+(Δ+1+N_ZC)/2)modN_ZC，可以理解为，B(0)可以通过 (τ+(Δ+1+N_ZC)/2)modN_ZC来获得。

步骤S205，根据该第一序列的初始值和第一参数值进行第一序列的第一 次迭代计算，之后，并根据第K-1次迭代计算后的值和第一参数进行第K次迭 代计算。在本实施例中，可以理解为，根据B(0)和Δ进行第一次迭代计算。在 本实施例中，可以用B(k)←(B(k-1)+Δ)modN_ZC来表示第一次迭代计算的结果， 其中，K(k≥1为一个正整数，小于等于N_ZC-1)可以表示为第k时刻，在上面 的公式中可以理解为序列的第K次迭代计算，或是可以理解为，在第1时刻、 第2时刻、…、第N_ZC-1时刻共执行了N_ZC-1次迭代计算，因此，第一次迭代 或第一时刻的迭代计算结果B(1)可以通过(B(0)+Δ)modN_ZC来获得，B(2)可以通 过(B(1)+Δ)modN_ZC来获得，以此类推，B(k)可以用(B(k-1)+Δ)modN_ZC来获得。 可以理解的是，进行每一次迭代计算，都有一个相应的迭代值产生，即进行 第k次迭代计算，就能产生一个B(k)。

步骤S207，根据第一序列的初始值和预设的第二序列的初始值进行第二 序列的第一次迭代计算，之后，并根据第二序列的第k-1次迭代计算后值和第 一序列的第K-1次迭代计算后的值进行第二序列的第k次迭代计算。在本实施 例中，第二序列可以用{Y(k)}来表示，其中k≥1为一个正整数，小于等于 N_ZC-1，该序列的初始值可以用Y(0)来表示，在本实施例中，预设的第二序列 的初始值Y(0)可以设为0，也可以理解为，在第0时刻，完成了第二序列的初始 化。在本实施例中，本步骤也可以理解为，根据B(0)和Y(0)进行第一次迭代计 算，第一次迭代计算结果可以用Y(1)来表示，可以理解为第二序列的第一次或 第1时刻的迭代计算，可以用表达式Y(1)←(Y(0)+B(0))mod N_ZC，当进行第二序 列的第二次或第二时刻的迭代计算时，第二次或第二时刻的迭代计算结果Y(2) 可以用表达式Y(2)←(Y(1)+B(1))modN_ZC来表示，以此类推，第k次或第k时刻的 迭代计算结果Y(k)可以用表达式Y(k)←(Y(k-1)+B(k-1))modN_ZC来表示。可以理 解的是，进行每一次迭代计算，都有一个相应的迭代值产生，即进行第k次迭 代计算，就能产生一个Y(k)。

步骤S209，判断第二序列的第k次迭代计算后的值是否小于等于 (N_ZC-1)/2。

在本实施例中，可以理解为，将Y(k)与(N_ZC-1)/2进行比较。由于在步骤 S207中，每进行一次迭代，就会产生一个值，因此，在本步骤，只要步骤S207 中产生一个迭代值，本步骤就会执行一次判断，可以理解为，本步骤需要执 行k次判断。

在本实施例中，若判断Y(k)小于等于(N_ZC-1)/2时，执行步骤S211。

若判断Y(k)大于(N_ZC-1)/2时，执行步骤S213。

在本实施例中，步骤S211，根据第二序列第k次迭代计算后值作为索引直 接查找exp-ROM表得到DFT变换输出。在本实施例中，可以理解为，在步骤 S209中，由于判断Y(k)小于等于(N_ZC-1)/2，因而将此时的Y(k)作为索引值 exp-ROM表得到一个DFT变换的值，并输出。在本实施例中，将Y(k)作为 exp-ROM表中公式中的n的值，n∈[0，(N_ZC-1)/2]，并将得到的一个 DFT变换后的值用X(k)来表示，即

步骤S213，将N_ZC减去第k次迭代计算后的值作为索引值查找exp-ROM表 得到DFT变换输出。在本实施例中，可以理解为，将N_ZC减去Y(k)后的值作为 索引值查询exp-ROM表得到一个DFT变换的值，并输出。在本实施例中，将N_ZC减去Y(k)后的值作为exp-ROM表中公式中的n的值，然后再查询 exp-ROM表，并将查表结果进行共轭后获得对应的X(k)。

本实施例中，也可采用CODRIC方法计算得到X(k)，此处不作限制。

在本实施例中，在步骤S209中，会对每一次产生的迭代计算的值进行判 断，并每一次判断后，都会去查询exp-ROM表得一个DFT变换的值，因此， 在经过N_ZC-1次迭代计算后，并判断N_ZC-1次后，同理会查询N_ZC-1次 exp-ROM，因此，会得到一个完整的DFT变换的值，即{X(k)}，从而将此时产 生的DFT变换的值{X(k)}进入后续的子载波映射、插入CP和应用功率增益因子 (β_PRACH)后，生成LTE移动通信系统中随机接入前导序列，并在PRACH信道 上发射。

本发明实施例所提供的ZC序列的DFT的快速计算方法，在计算过程中， 采用两重迭代方法计算，只涉及整数加，减、比较和查表操作，不涉及定点 处理损失，相对于现有技术而言，可以实现计算过程的复杂度很低和高的计 算精率，并且可以大大降低计算处理量和存储量，适合与高效率的软件或硬 件处理需求。本发明可应用于LTE移动通信系统中终端或基站中随机接入前导 (preamble)序列生成过程中DFT的计算。

图3为本发明ZC序列的DFT的快速计算装置一实施例的结构示意图。

在本实施例中，该ZC序列的DFT的快速计算装置应用于LTE移动通信 系统中终端或基站中随机接入前导(preamble)序列生成过程中DFT的计算。 在本实施列中，ZC序列的DFT的快速计算装置对接收的ZC序列进行DFT 变换后，输出一个完整的DFT变换的值{X(k)}，从而将此时产生的DFT变换 的值进入后续的子载波映射、插入CP和应用功率增益因子(β_PRACH)后，生 成LTE移动通信系统中随机接入前导序列，并在PRACH信道上发射。

在本实施例中，ZC序列的DFT的快速计算装置可以包括第一数据库300， 第一查询模块302，初始值计算模块304，第一存储模块306，第一取模加法 器308，第二取模加法器310，第二存储模块312，第二查询模块314，第二 数据库316。

在本实施例中，第一数据库300用于存储构造的第一数据表，可以为 Δ-ROM表，该Δ-ROM表中存储内容项为Δ＝u^-1modN_ZC，依次对应 0≤u≤N_ZC-1，Δ取值范围为[0，N_ZC-1]中的整数，该表中对应N_ZC个的可能取值 u，存储了对应的共N_ZC个Δ值。在本实施例中，u表示ZC序列的根序列号， 依次对应0≤u≤N_ZC-1，表示ZC序列的长度，在LTE系统中取值为839(前 导格式0～3)或139(前导格式4)。

第二数据库316用于存储构造的第二数据表，可以包括(N_ZC+1)/2个元素 的exp-ROM表，xp-ROM表中存储项为其中n∈[0，(N_ZC-1)/2]为 非负整数。在本实施例中，N_ZC表示ZC序列的长度，在LTE系统中取值为 839(前导格式0～3)或139(前导格式4)。

第一查询模块302与第一数据库300连接，用于根据ZC序列的根序列号 获取第一参数值，可以理解为，根据接收的ZC序列的根序列号u查询第一数 据库300获得第一参数值。在本实例中，第一参数值可以用Δ来表示。在本实 施例中，可以以ZC序列的根序列号u作为索引值查Δ-ROM表得到Δ值。

初始值计算模块304与第一查询模块302连接，用于根据第一查询模块 302所获取的第一参数值、ZC序列长度和循环移位值获得第一序列的初始值， 可以理解为，根据第一查询模块302获得的第一参数值、该ZC序列的长度和 接收的循环移位值获得第一序列的初始值。在本实施例中，循环移位值用τ表 示，第一序列可以用{B(k)}来表示，其中该序列的初始值可以用B(0)来表示， 可以表示为根据Δ值，N_ZC和τ来获得B(0)。在本实施例中，若Δ为奇数，则 B(0)←(τ+(Δ+1)/2)modN_ZC，可以理解为，B(0)可以通过(τ+(Δ+1)/2)modN_ZC来 获得，若Δ不为奇数，则B(0)←(τ+(Δ+1+N_ZC)/2)modN_ZC，可以理解为，B(0) 可以通过(τ+(Δ+1+N_ZC)/2)modN_ZC来获得。

第一存储模块306与初始值计算模块304连接，用于存储初始值计算模 块304获得的第一序列的初始值。

第一取模加法器308与第一查询模块302及第一存储模块306分别连接， 用于根据第一查询模块302存储的第一序列的初始值和第一查询模块302获 得的第一参数值进行第一序列的迭代计算，并存储于第一存储模块302。在本 实施例中，可以理解为，先根据第一查询模块302存储的第一序列的初始值 和第一查询模块302获得的第一参数值进行第一序列的第一次迭代计算。在 本实施例中，该第一取模加法器308进一步用于将第一次迭代计算后的值存 储于第一存储模块306。在本实施例中，该第一取模加法器308进一步用于根 据第一存储模块306存储的第一次迭代计算后的值和第一查询模块302获得 的第一参数值进行第二次迭代计算，并依然将第二次迭代计算后的值存储于 第一存储模块306，以此类推，该第一取模加法器308进一步用于根据第一存 储模块306存储的第k-1次迭代计算后的值和第一查询模块302获得的第一参 数值进行第k次迭代计算，并将迭代计算后的值存储于第一存储模块306。在 本实施例中，可以用下面的描述来解释：根据B(0)和Δ进行第一次迭代计算。 在本实施例中，可以用B(k)←(B(k-1)+Δ)modN_ZC来表示第一次迭代计算的结 果，其中，k(k≥1为一个正整数，小于等于N_ZC-1)可以表示为第k时刻， 在上面的公式中可以理解为序列的第K次迭代计算，或是可以理解为，在第 1时刻、第2时刻、…、第N_ZC-1时刻共执行了N_ZC-1次迭代计算，因此，第 一次迭代或第一时刻的迭代计算结果B(1)可以通过(B(0)+Δ)modN_ZC来获得， B(2)可以通过(B(1)+Δ)modN_ZC来获得，以此类推，B(k)可以用(B(k-1)+Δ)modN_ZC来获得。可以理解的是，进行每一次迭代计算，都有一个相应的迭代计算值 产生，即进行第k次迭代计算，就能产生一个B(k)。因此，第一存储模块306 中存储了多个的迭代计算后的值。

第二取模加法器310与第一存储模块306和第二存储模块312连接，用 于根据第一存储模块306存储的第一序列的迭代计算后的值和预设的第二序 列的初始值对第二序列的进行迭代计算。在本实施例中，可以理解为，先根 据第一存储模块306存储的第一序列的初始值和预设的第二序列的初始值进 行第二序列的第一次迭代计算，并将第一次迭代计算后的值存储于第二存储 模块312。同理，第二取模加法器310进一步用于根据第二存储模块312存储 的第二序列的第k-1次迭代计算后值和和第一存储模块306存储的第一序列的 第k-1次迭代计算后的值进行第二序列的第k次迭代计算，并将该第k次迭代 计算后的值存储于第二存储模块312。在本实施例中，第二序列可以用{Y(k)} 来表示，其中k≥1为一个正整数，小于等于N_ZC-1，该序列的初始值可以用 Y(0)来表示，在本实施例中，预设的第二序列的初始值Y(0)可以设为0，也可 以理解为，在第0时刻，完成了第二序列的初始化。在本实施例中，本步骤 也可以理解为，根据B(0)和Y(0)进行第一次迭代计算，第一次迭代计算结果 可以用Y(1)来表示，可以理解为第二序列的第一次或第1时刻的迭代计算， 可以用表达式Y(1)←(Y(0)+B(0))modN_ZC，当进行第二序列的第二次或第二时刻 的迭代计算时，第二次或第二时刻的迭代计算结果Y(2)可以用表达式 Y(2)←(Y(1)+B(1))modN_ZC来表示，以此类推，第k次或第k时刻的迭代计算结 果Y(k)可以用表达式Y(k)←(Y(k-1)+B(k-1))modN_ZC来表示。可以理解的是， 进行每一次迭代计算，都有一个相应的迭代计算值产生，即进行第k次迭代 计算，就能产生一个Y(k)。因此，第二存储模块312中存储了多个的迭代计 算后的值。

第二查询模块314与第二存储模块312和第二数据库316连接，用于根 据第二序列的迭代计算后的值获得DFT变换。在本实施例中，可以理解为， 根据第二存储模块312中存储的第k次迭代计算后的值查询第二数据库316， 以获得DFT变换的值。在本实施例中，第二查询模块314进一步用于判断第 二序列的第k次迭代计算后的值是否小于等于(N_ZC-1)/2。在本实施例中，每 进行一次迭代，就会产生一个值，因此，第二查询模块314要执行k次判断。

在本实施例中，当第二查询模块314判断Y(k)小于等于(N_ZC-1)/2时，根 据第二存储模块312中存储的第二序列的第k次迭代计算后值作为索引直接 查找第二数据库316中的exp-ROM表得到相应的DFT变换的值，并输出。

在本实施例中，当第二查询模块314判断Y(k)大于(N_ZC-1)/2时，将N_ZC减 去第二存储模块312中存储的第二序列的第k次迭代计算后值作为索引值查 找第二数据库316中的exp-ROM表，并将查表结果进行共轭后得到相应的 DFT变换的值，并输出。

在本实施例中，也可采用CODRIC方法计算得到X(k)，此处不作限制。

在本实施例中，第二查询模块314会对每一次产生的迭代计算的值进行 判断，并每一次判断后，都会去查询exp-ROM表得一个DFT变换的值，因 此，在经过N_ZC-1次迭代计算后，并判断N_ZC-1次后，同理会查询N_ZC-1次 exp-ROM，因此，会得到一个完整的DFT变换的值，即{X(k)}，从而将此时 产生的DFT变换的值{X(k)}进入后续的子载波映射、插入CP和应用功率增益 因子(β_PRACH)后，生成LTE移动通信系统中随机接入前导序列，并在PRACH 信道上发射。

本发明实施例所提供的ZC序列的DFT的快速计算装置，在计算过程中， 采用两重迭代方法计算，只涉及整数加，减、比较和查表操作，不涉及定点 处理损失，相对于现有技术而言，可以实现计算过程的复杂度很低和高的计 算精率，并且可以大大降低计算处理量和存储量，适合与高效率的软件或硬 件处理需求。本发明可应用于LTE移动通信系统中终端或基站中随机接入前导 (preamble)序列生成过程中DFT的计算。

图4为本发明ZC序列的DFT的快速计算装置中图3的初始化计算模块的结 构示意图。

在本实施例中，初始化计算模块包括第一加法器400，选择器402，第二 加法器404，移位器406，取模加法器408。

在本实施例中，第一加法器400用于将第一查询模块302获得的第一参数 值加上1。选择器402分别与第一加法器400及第二加法器404连接，用于根据 第一参数值的最低位判断第一加法器400输出的值是否通过第二加法器404加 上N_ZC。在本实施例中，若Δ的最低位为奇数，则判断第一加法器400输出的 值不需要通过第二加法器404再加上N_ZC；若Δ的最低位不为奇数，则判断第 一加法器400输出的值需要通过第二加法器404再加上N_ZC。

移位器406与第二加法器404连接，用于对第二加法器404输出的值右移一 位；取模加法器408与移位器406连接，用于对移位器406输出的值和循环移位 值进行取模计算。在本实施例中，可以理解为：若Δ为奇数，则取模加法器408 输出的值可以用表达式B(0)←(τ+(Δ+1)/2)modN_ZC来表式，可以理解为，B(0) 可以通过(τ+(Δ+1)/2)modN_ZC来获得，若Δ不为奇数，则取模加法器408输出的 值可以用表达式B(0)←(τ+(Δ+1+N_ZC)/2)modN_ZC来表示，可以理解为，B(0)可 以通过(τ+(Δ+1+N_ZC)/2)modN_ZC来获得。在本实施例中，图5为图4所示的初始 化计算模块的具体电路图。

图6为本发明ZC序列的DFT的快速计算装置中图3的取模加法器的结构示 意图。

在本实施例中，取模加法器包括第一加法器600，比较器602，及减法器 604。在本实施例中，取模加法器可以接收两个输入值，如X，Y，通过第一 加法器600进行加法计算，可以将(X+Y)mod N_ZC作为取模加法器的输出值。

在本实施例中，第一加法器600用于接收两个输入值，对其两个输入值进 行加法计算。

比较器602分别与第一加法器600和减法器604连接，用于将第一加法器 600输出的值与N_ZC进行判断，若判断第一加法器600输出的值小于N_ZC，则将 该第一加法器600输出的值作为取模加法器的输出值；若比较器602判断第一 加法器600输出的值不小于N_ZC，则通知减法器604将第一加法器600输出的值 减去N_ZC。

减法器604与比较器602连接，用于当比较器602判断第一加法器600输出 的值不小于N_ZC时，将第一加法器600输出的值减去N_ZC，并将减去N_ZC后的值 作为取模加法器的输出值。在本实施例中，图7为图6所示的取模加法器的具 体电路图。

以上仅为本发明的优选实施例，并非因此限制本发明的专利范围，凡是 利用本发明说明书及附图内容所作的等效结构或等效流程变换，或直接或间 接运用在其他相关的技术领域，均同理包括在本发明的专利保护范围内。