1568 IEEE COMMUNICATIONS LETTERS, VOL. 19, NO. 9, SEPTEMBER 2015
Reduced Complexity SNR Estimation via Kolmogorov-Smirnov Test
Yongming Fu, Student Member, IEEE, Jiang Zhu, Member, IEEE, Shilian Wang, and Zhipeng Xi
Abstract—Two complexity reducing schemes are proposed in
this letter for the recently presented Kolmogorov-Smirnov (K-S)
test based signal-to-noise ratio (SNR) estimator. The K-S test based
SNR estimator can work properly over an extended SNR range for
various multilevel constellations with limited signal samples, but
involves considerably more add operations as a result for the huge
amount of reference signals needed for matching operations. The
proposed two complexity reducing schemes explore the order char-
acteristic of the SNR matching pool to accelerate the searching
procedure. For the situation under consideration, the computa-
tional complexities (numbers of add operation) of the two proposed
schemes are about 1/5 and 1/20 of the original one respectively.
Simulation results have verified these schemes’ effectiveness.
Index Terms—SNR estimation, Kolmogorov-Smirnov test, com-
plexity reducing.
I. INTRODUCTION
S
IGNAL-TO-NOISE RATIO (SNR) is the most valuable
measure of the channel quality and a necessary apriori
information in many applications, including power control
in mobile networks, adaptive coding and modulation, turbo
decoding and bit error rate estimation [1]. Like most other
estimation problems, SNR estimators can be categorized as
data-aided (DA) and non-data-aided (NDA) ones. The NDA
estimators, which have the advantages of in-service estimation
not impinging upon the throughput of the channel, are of
particular interest [2]. The most well-known and wide spread
NDA SNR estimators are based on the Method-of-Moments
(MoM) [1]–[5]. However, the classic M
2
M
4
estimator performs
well with respect to constant modulus schemes like M-PSK,
whereas a severe degradation is observed for multilevel con-
stellations in the medium-to-high SNR range [6]. Recently, a
new MoM based approach has been proposed, which exploits
a linear combination of ratios for certain even-order moments
(up to eight-order moment is referred) to improve on previous
estimators of this class [4]. But the weights of the linear com-
bination should be tuned according to the constellation and the
specific SNR operation range. In [7], we have proposed a novel
Kolmogorov-Smirnov (K-S) test based NDA SNR estimator,
which can work properly over an extended SNR range for
various multilevel constellations with limited signal samples.
As to the computation complexity, the K-S test based estimator
involves no multiplication operations, but considerably more
add operations are needed, which requires a large amount of
logic resources in hardware.
Manuscript received April 24, 2015; revised June 16, 2015; accepted June 18,
2015. Date of publication June 26, 2015; date of current version September 4,
2015. This work was supported by the National Natural Science Foundation
of China under Grant Nos. 61401476 and 61201166. The associate editor
coordinating the review of this paper and approving it for publication was
P. Salvo Rossi.
The authors are with the School of Electronic Science and Engineering,
National University of Defence Technology, Changsha 410073, China (e-mail:
fuyongmingcn@hotmail.com).
Digital Object Identifier 10.1109/LCOMM.2015.2450222
In this letter, we propose two complexity reducing schemes
for the K-S test based SNR estimator by exploring the order
characteristic of the SNR matching pool. The two-step search
(TSS) scheme divides the estimation procedure into two steps
(coarse estimation and fine estimation), reducing this way the
complexity of the K-S test based SNR estimator to some extent
almost without any performance loss. However, via a binary
search (BS) scheme, the computational load can be reduced
tremendously. The effectiveness of the two schemes is verified
by extensive simulations at the end of this letter.
II. B
ACKGROUND
A. System Model
Assuming a quasi-static flat-fading channel model, the sym-
bol rate samples at matched filter output are given by [7], i.e.,
r
k
=
√
Sx
k
e
jθ
k
+ w
k
, k = 1,...,K, (1)
in which x
k
are the complex-valued transmitted symbols
(E{|x
k
|
2
}=1 is assumed),
√
S is the unknown channel gain,
θ
k
are unknown (possibly time-varying) phases accounting for
carrier offset and phase jitter, and the complex-valued samples
w
k
are determined by an independent, zero-mean Gaussian
noise process with variance N = 2σ
2
.
Given the K samples {r
1
, r
2
,...r
k
,...,r
K
}, the goal is to
estimate the SNR defined as ρ
.
= S/N.
B. Original K-S Test Based SNR Estimator and Its Complexity
For details about the K-S test, the readers could refer to [8].
The K-S test based SNR estimation procedure proposed in [7]
can be described as follows briefly:
1) Upon the constellation format, choose a proper decision
statistic z (actually, the signal envelope is adopted) and
compute its theoretical CDF F
0
(z), if available.
2) Determine the reference SNR pool =[ρ
1
,ρ
2
,...,ρ
k
snr
,
...,ρ
K
snr
], ρ
k
snr
=ρ
1
+(k
snr
−1) ρ, with ρ the quan-
tization resolution. For each quantized SNR value ρ
k
snr
,a
theoretical CDF line (F
k
snr
0
(z)) is attached (or an empirical
CDF (ECDF) line
ˆ
F
k
snr
0
(z
k
) formed by N
ref
local samples
is attached in the two-sample test case).
3) Compute the ECDF
ˆ
F
1
(z
k
) of the decision statistic se-
quence {z
k
} extracted from the observed samples, and the
K-S statistic is then calculated by:
ˆ
D
k
snr
=
⎧
⎪
⎨
⎪
⎩
max
1≤k≤K
ˆ
F
1
(z
k
) −F
k
snr
0
(z
k
)
one-sample test,
max
1≤k≤K
ˆ
F
1
(z
k
) −
ˆ
F
k
snr
0
(z
k
)
two-sample test.
k
snr
= 1, 2,...,K
snr
. (2)
1558-2558 © 2015 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission.
See http://www.ieee.org/publications_standards/publications/rights/index.html for more information.