Parallelized Generation of ZC/ZC-DFT Sequences
in Vector DSP
Jiangnan Lin
∗
, Kai Xie
†
, Yongtao Su
†
, Yiqing Zhou
†
, Yanbin Yao
∗
and Jinglin Shi
†
∗†
Wireless Communication Technology Research Center, Institute of Computing Technology, Chinese Academy of Sciences
∗†
Beijing Key Laboratory of Mobile Computing and Pervasive Device
∗
University of Chinese Academy of Sciences
Email: {linjiangnan, xiekai, ysu, zhouyiqing, yaoyanbin, sjl}@ict.ac.cn
Abstract—A parallelized generation of Zadoff-Chu (ZC) and
the Discrete Fourier Transform of Zadoff-Chu (ZC-DFT) se-
quences is proposed. In this algorithm, the sampling operation
is completely eliminated for the ZC-DFT sequences generation.
Implemented on a vector Digital Signal Processor (DSP), the
proposed algorithm makes an efficient use of the parallel DSP
structure and achieves a high computing speed, owing to the de-
composition of the root index. Since only a few “seed sequences”
are required, the proposed algorithm obtains an extremely low
memory requirement and a high precision.
I. INTRODUCTION
Due to their perfect periodic autocorrelation properties,
Zadoff-Chu (ZC) sequences [1], [2] and their Discrete Fourier
Transform (DFT) have been widely used as important physi-
cal signals in practical wireless communication systems. For
example, in Long Term Evolution (LTE) systems, the primary
synchronization signal (PSS), the up-link reference signal (RS)
and the preamble in physical random access channel (PRACH)
are all constructed from ZC or ZC-DFT sequences [3], [4].
In modern wireless communication systems, a digital signal
processor (DSP) plays an important role for the meeting
of large-scale and high-speed signal processing requirement.
Moreover, a vector DSP [5], who is equipped with a vector
memory access mechanism and a vector calculation unit,
is especially favored. Because the most significant feature
of a vector DSP is that, it can process a series of data
simultaneously using a parallel method and accelerates an
algorithm exponentially.
Since the ZC sequences consist of exp functions whose
calculation is highly complex for a DSP, it is difficult to
generate the ZC sequences in real time. One possible solution
is based on Look-Up-Table (LUT), which generates sequences
with a required precision, lists them in a table and stores them
in the memory. However, the ZC sequences, characterized by
the root index, are different from each other, which will lead
to a huge memory requirement. For example, there are 60 ZC
sequences with a length of 1193 used as the up-link reference
signal in the 20MHz bandwidth configuration in LTE, if those
ZC sequences are stored with 16-bit precision, a memory of
280KB is needed, and about 7MB will be consumed for all
the ZC/ZC-DFT sequences in LTE. In order to reduce the
memory consumption, various methods have been proposed,
such as the CORDIC (COordinate Rotation DIgital Computer)
algorithm [6] and the Decimation algorithm [7]. Note that
the CORDIC algorithm employs an iteration structure and
thus is more suitable for a circuit but not a vector DSP.
For the Decimation algorithm with extracting operations, it is
complicated to implement the algorithm in a DSP in a vector-
oriented parallel way.
In 2009, an efficient method for computing the DFT of the
ZC sequences has been proposed [8]. It is shown that the
ZC-DFT sequence is a weighted, conjugated and cyclically
sampled version of the original ZC sequence. Therefore, ZC-
DFT sequences can be generated directly from the existing
ZC sequences without the DFT operation. Inevitably, for the
algorithm in [8], a sampling operation is required which is no
other than a memory reading from a group of discontinuous
addresses. However, a vector DSP is usually designed to read
continuous data from sequential address. Therefore, the sam-
pling operation cannot achieve a high adaption to a vector DSP
and will lead to an efficiency reduction when implemented in
a parallel structure.
This paper proposes a novel parallel algorithm for the
efficient generation of ZC and ZC-DFT sequences in DSP.
The proposed algorithm is independent from the sampling
operation for ZC-DFT sequences generation. Moreover, a
parallel structure is designed for generating both ZC and ZC-
DFT sequences which can be readily implemented in a vector
DSP and achieves a remarkable computing speed with a high
precision. In addition, compared to the LUT scheme, the
proposed algorithm significantly reduces the requirement on
memory, e.g., from 280KB to 26KB for the 60 ZC sequences
of length 1193 with the same bit-width.
The rest of this paper is organized as follows. Section II
introduces the ZC sequences and their important properties.
Then, a no-sampling algorithm for ZC-DFT sequences gen-
eration is proposed in Section III. In Section IV, a parallel
algorithm for both ZC and ZC-DFT sequence generation is
presented. Section V gives the evaluations of the time and
space complexity as well as the computing precision when the
proposed algorithm is implemented in a vector DSP. Finally,
conclusions are drawn in Section VI.
2015 IEEE Wireless Communications and Networking Conference (WCNC 2015) - Track 1: PHY and Fundamentals
978-1-4799-8406-0/15/$31.00 ©2015 IEEE 621