Communications and Network, 2013, 5, 266-270
http://dx.doi.org/10.4236/cn.2013.53B2049 Published Online September 2013 (http://www.scirp.org/journal/cn)
Research on An Improved PMF-FFT Fast PN Code
Acquisition Algorithm
Ning-qing Liu, Bin Sun, Chun-meng Guan
Communication Research Center Harbin Institute of Technology Harbin, China
Received July, 2013
ABSTRACT
To solve the problem of the large Doppler frequency offset in the LEO communication system, this paper studies a
rapid PN code acquisition method based on the PMF-FFT architecture, which searches the phase and frequency offset
and at the same time reduces the acquisition time. It presents an improved method equivalent to windowing function
and uses windowing process to overcome the attenuation of related peak envelope caused by partial matched filters.
Keywords: Doppler Frequency Offset; Rapid PN Code Acquisition Algorithm; PMF-FFT; Windowing
1. Introduction
Doppler frequency offset, which makes it very difficult
for the receiver to seize the signals. Ordinary one-di-
mensional search cannot meet the requirements of the
rapid PN code acquisition, and thus two-dimensional
search method is being gotten more attention. M. Sust
has proposed a fast acquisition concept in the audio
CDMA system [1]. In the paper, he analyzed the method
of using FFT compensation method to solve the problem
of large offset acquisition in the system, and the capture
structure he used was the prototype of PMF-FFT algo-
rithm. G.J.Povey, who first proposed this kind of algo-
rithm which was based on [1] and made an efficient
study and analysis [2-4], has gotten significant conclu-
sions, making great contributions to the later develop-
ment of the algorithm.
Reference [3] describes a non-coherent rapid acquisi-
tion system under the Doppler frequency offset. For the
first time, it gives the PMF-FFT acquisition model and
analyzes the probability of false alarm and detection
probability characteristic in the Gaussian channel. S. M.
Spangenherg proposed the windowing process of the
FFT input to reduce the Scalloping Loss. This paper fo-
cuses on windowing approaches and then improves the
structure of windows, improving the acquisition per-
formance of the algorithm. It also presents a structure
equivalent to windowing function, simplifying the im-
plementation. For some low-pass attenuation of the
matched filters, the window approach is also introduced.
2. Acquisition Algorithm Models Based on
the PMF-FFT Structures
2.1. Acquisition Theory
M. Sust etal first used the FFT compensation, increasing
the search range greatly in the frequency fields, which is
equal to the parallel searches. Then G.J.Povey developed
this method, systematically analyzed the acquisition al-
gorithm of the FFT auxiliary digital matched filters, and
showed the model based on both the digital part of the
matcher filters and the FFT, shown in Figure 1. Here
MX = KN, N is the length of PN code, while K is the
sampling factor.
Supposing the sampling interval Ts=Tc/K, the initial
phase is

, the sampling signal after the down-conver-
sion is
ds
(2π) ds
s
ds
sin(π)
()( )
π
jfnT
fT
xnPTcn Le
fT




(1)
When PN code obtains full synchronization,
ds ds
ds
ds ds
sin( π)sin[π(/)]
(, )πsin[π(/)]
j
fXTM fXTkM
Ykf PMXTe
fXTMfXTk M






(2)
 0
PMF
1
PMF
2
PMF
1
PMF
M

2
PMF
M
222 2 2

Figure 1. Capture model based on PMF-FF T[1].
C
opyright © 2013 SciRes. CN

N.-Q. LIU ET AL. 267
Normalize (2), the normalized frequency response of
the FFT output of the k-th point
d
(, ) ds ds
PMF-FFT d
ds ds
sin(π) sin[π(/)]
(, )πsin[π(/)]
jkf
fXTM fXTkM
Gkf e
fXTMfXTk M



(3)
d
It is shown in Figure 1 that the input which is com-
pared with the preset threshold is the maximum output
value of the k-th FFT point. That is, for a fixed variable
fd, comparing these values of
(, )kf is the phase characteristic of the PMF-FFT.
PMF-FFT d
(, )Gkf, then we
can get the related gains in the acquisition system.

dPMF-FFT d
PMF-FFTc ddd
c
()max(,) (0,1,21)
1,(0
2
AfGkfkM
)
M
GNTff f
NT










(4)


 means to get the integral results downward.
2.2. FFT Compensation Characteristic
Equation (4) can be divided into two parts, and the nor-
malized contribution of the partial matched filter of (4) is
ds
(1)
ds 2
PMF d
ds
sin(/ 2)
() /2
j
XfT
Xf T
Gf e
Xf T


 (5)
And the contribution that the FFT makes to the related
normalized is
FFT d
j(,
FFT dFFT d
(, )(,)kf Gkf Akfe

) (6)
FFT d
(,)
A
kf is the amplitude response, and FFT d (, )kf

is the phase response.
For the moment, partial influence of the matched fil-
ters is not considered, and the following properties can
be deprived from (6):
1) Panning features
Change the form of (6), then
FFTdFFT d
c
1
(1,)(,)Gk f GkfNT   (7)
Equation (7) indicates that the frequency response of
the kth FFT point is actually a 1/NTc units right shift of
the (k-1)th FFT point’s frequency response.
So the synchronization system based on the PMF-FFT
structure in Figure 1, can be extended M times in fre-
quency searching range, which is [0, M/(NTc)]. Therefore
the simultaneous capture algorithm based on the PMF-
FFT structure is not sensitive to the Doppler frequency
offset, and the system is still able to complete the simul-
taneous capture successfully.
2) Period feature
Because the FFT compensation factor km
M
W is a rota-
tion factor with a period of M, and is reflected as a peri-
odic function in frequency domain in (6), with the period
of M/(NTc). According to (6), it can be obtained:
FFTd FFTd
c
(,)(, )
M
GkfGkf
NT
 (8)
3) Ax symmetric feature
It can be found that FFT d (, )Gkf is an ax symmetric
function of fd, and on the axis of k/(NTc). Make simple
algebraic simplification to (6), then
FFTdFFT d
cc
(,) (,)
kk
GkfG kf
NT NT

 (9)
That is
FFTdFFT d
cc
(,) (,)
kk
Gkf Gkf
NT NT
 (10)
4) Dual feature
Now consider the negative frequency, there is
FFTd FFTd
(,)(, )Gkf G Mkf

 (11)
When d
cc
1
[,
22
kk
fNT NT

 ]
, the capture system can
still work effectively, and produces the maximum related
output on the (M-k) FFT.
3. Scalloping Loss
The associated gain of each FFT point is similar to sinc(x)
function. At the crossover point, the associated gain out-
put appears on the trough, presenting the phenomenon of
the Scalloping Loss. Reference [4] proposes two solu-
tions, storage zeros and windowing, and makes a thor-
ough analysis to the former one. This paper focuses on
the study and improvement of the windowing method.
The main idea of this method is to increase the width of
the main lobe and increase the FFT peak output intersect-
tion of the two adjacent points, in order to reduce the
loss.
Now the window function is adapted to the united
form

12π
1cos ,0
1
0
mmM
wm M
others



 1

 






(12)
The related gain is
FFT d
FFT dFFT dFFTdFFT d
cc
(, )
11
(, )(,)(,)(,)
22
jkf
GkfA kfA kfA kf
NT NT
e




 




(13)
Considering the panning features of the FFT compen-
sation, we can change the form of (13). That is

N.-Q. LIU ET AL.
268
FFT dFFT dFFTd
FFT d
(,)(,)( 1,)
2
(1,)
2
Gkf GkfGk f
Gk f




(14)
Thus the weighted sum of three consecutive FFT
points according to (14) can get the same effect as win-
dowing and the structure is simpler. In Figure 2, there is
the comparison of the realization between windowing
and equivalent windowing. It can be seen that the
weighted sum of the FFT output is equal to the window-
ing process of the FFT input. They share the same im-
proving properties.
4. The Low-pass Decay of PMF
As to the discussion about the FFT compensation fea-
tures before, it is supposed to be all-pass without the in-
fluence of FFT. But actually PMF is a limited FIR with
the length of X and all the coefficients are one.
In fact, GFFT (k,fd) is the related gain envelop of the
PMF-FFT. When there is a large Doppler frequency off-
set, the attenuation of the PMF greatly influences the
peak of related gain. This paper uses the same method as
the windowed FFT input to perform the windowing
process to the sampled data entering the FFT, increasing
the width of the main lobe envelop in order to improve
the decay when the frequency is large, shown in Figure
3.
5. The Improved Structure of the Algorithm
Thus, this paper makes a detailed analysis of the acquisi-
tion structure based on PMF-FFT, and discusses two
methods to overcome the Scalloping Loss. After com-
parison, adding zeros by windowing turns to be easier
and more effective. Therefore, this paper introduces
windowing and its equivalent method into the acquisition
system. For the influence on the related gain in the sys-
tem which is made by the low-pass characteristic of some
0500 10001500 20002500 3000 35004000 45005000
0.8
0.82
0.84
0.86
0.88
0.9
0.92
0.94
0.96
0.98
1
多普勒频偏f
d
/Hz
PMF-FFT输出峰值增益
对FFT的输入做加窗处理
对FFT的输出做加权叠加
Figure 2. Simulation of equivalent window function method.
matched filters, this paper presents two effective solu-
tions, which are adaptive threshold method and window-
ing. These two methods can be combined in order to im-
prove the ability of acquiring PN code in large frequency
offset.
The improved PMF-FFT structure is shown in Figure
4.
6. Algorithm Evaluation
Considering the non-coherent detection system, the am-
plitude statistical variables of M-point FFT output are
identically distributed.
In the acquisition system in Figure 4, the statistical
variables R that is compared with the threshold is the
maximum value of M-point FFT output. Now the false
probability is
1
FA FA
0
c
1(1())11exp
2
M
M
k
PPk




 
 


 (15)
2.52.552.6 2.65 2.72.75 2.82.85 2.9 2.953
x 10
4
0. 4
0. 5
0. 6
0. 7
0. 8
0. 9
1
PMF-FFT相关峰值增益
多普勒频偏f
d
/Hz
未加窗
加汉宁窗
PMF-FFT Correlation peak gain
Figure 3. Effect of Amplitude-frequency response of PMF.
...

2

1
FFT
k
FFT
k
1
FFT
k

FFT
k

2


2


2
R
Figure 4. Block diagram of captures structure of Improved
PMF-FFT.

N.-Q. LIU ET AL. 269
From (15), not only the threshold, but the number of
FFT points has connection with false alarm probability.
And the probability increases with the increasing values
of M. Therefore, the number of the chosen FFT points in
actual system is limited, and the false probability and the
searching range of the frequency offset are in contradict-
tion.
For the PMF-FFT capture system the detecting prob-
ability [4, 5] is

DinPMF-FFT
()2(, ),Pk QNSNRGkfc

d (16)
Suppose the preset threshold c=30, at this time PFA =
3.9210-5, the information rate Rb=1kpbs, the period of
the PN code N=10240, the input SNR SNRin = -25 dB.
The relation between the detecting probability and the
Doppler offset before and after the improvement is
shown in Figure 5.
From Figure 5, the PMF-FFT algorithm expands the
right detecting probability in the frequency domain. And
the probability is bigger after windowing process than
before. So the windowing method improves the detecting
probability of the PN code acquisition.
This paper uses the single stay acquisition decision, so
the average acquisition time is
D
Acq d
D
2(2)( 1)(1)
2
Pq kP
TP
FA

 
 (17)
Here q is the number of code offset units to be
searched, q=KN; d

is single stay time. The stay time
will be Ts by using parallel matched filters, but it is at the
cost of huge hardware resource. So it is the serial way
that is chosen in this design and the stay time is XTs; k is
the number of decisions approving the happening of false
alarm. So false alarm penalty time is d
k

. If k = 10, the
relation between PMF-FFT algorithm and the Doppler
frequency offset before and after the improvement is
shown in Figure 6. Figure 7 shows the connection of
algorithm and the input SNR before and after improve-
ment.
05001000150020002500 3000 35004000 45005000
0. 8
0. 82
0. 84
0. 86
0. 88
0. 9
0. 92
0. 94
0. 96
0. 98
1
多普勒频偏f
d
/Hz
检测概率P
D
K
2
=0， 未加窗
K
2
=1， 汉宁窗
K
2
=1.7，改进窗
in
1ms
10240
25dB
b
T
N
SNR



2

2

2

Figure 5. Relationships between probability of detection of
improved algorithm and Doppler shift.
0 1 234 56
x 10
4
75
80
85
90
95
100
105
多普勒频偏f
d
/Hz
平均捕获时间T
Acq
/ms
K
1
=0, K
2
=0
K
1
=0, K
2
=1.7
K
1
=1.7,K
2
=1.7
1
10240
25
b
in
Tms
N
SNR dB



1

1

1

2

2

2

Figure 6. Average capture time of original and improved
algorithm under Doppler shift.
-40 -35 -30 -25-20 -15 -10 -5 0 5
10
1
10
2
10
3
10
4
10
5
输入信噪比SNR
i
n
/dB
平均捕获时间T
Acq
/ms
K
1
=0, K
2
=0
K
1
=0, K
2
=1.7
K
1
= 1.7,K
2
=1.7
1

1

1

2

2

2

b
d
1ms, 10240
30, 59.5kHz
TN
cf


Figure 7. Average capture time of original and improved
algorithm under different SNR.
7. Conclusions
This paper analyses basic theory of the PMF-FFT PN
code acquisition algorithm. For the Scalloping Loss, it
focuses on the windowing function method and improves
the structure, reducing the influence of the Scalloping
Loss. What is more, it proposes an equivalent method
equipped with easier structure. For the loss brought by
PMF fixed low-pass properties, it chooses the windowing
process to the received data. Theoretical analysis results
show that, after windowing twice, the algorithm im-
proves detecting probability and reduces average acquisi-
tion time compared with the original one, improving the
capacity of resisting disturbance.
REFERENCES
[1] M. Sust, R. Kaufman, F. Molitor and A. Bjornstor,
“Rapid Acquisition Concepts for Voice Activated CDMA
Communication,” IEEE Globecom’ 90, 1990, pp.
1820-1828.
[2] G. J. R. Povey and J. Talvitie, “Doppler Compensation
and Code Acquisition Techniques for LEO Satellite Mo-
bile Radio Communications. IEEE Fifth Internation Con-
ference on Satellite Systems for Mobile Communications

N.-Q. LIU ET AL.
270
and Navigation. 1996, pp. 16-19.
doi:10.1049/cp:19960398
[3] R. A. Stirling-Gallacher, A. P. Hulbert and G. J. R. Povey,
“A Fast Acquisition Technique for a Direct Sequence
Spread Specrum Signal in the Presence of a Large Dop-
pler Shift,” Proceedings of ISSSTA’96, Mainz, Germany.
1996, pp. 156-160.
[4] S. M. Spangenberg, I. Scott, S. Mclaughlin and G. J. R.
Povey, “An FFT-Based Approach for Fast Acquisition in
Spread Spectrum Communication Systems,” Wireless
Personal Communications, Vol. 13, No. 1-2, 2000, pp.
27-55. doi:10.1023/A:1008848916834
[5] A. Polydoros and C. L. Weber, “A Unified Approach to
Serial Search Spread-Spectrum Code Acquisition—Part II:
A Matched Filter Receiver,” IEEE Transactions Commu-
nications, 1984, Vol. 32, No. 5, pp. 550-560.
doi:10.1109/TCOM.1984.1096113