1

A Finite Block Length Achievability Bound for
Low Probability of Detection Communication

arXiv:1801.05071v1 [] 15 Jan 2018

Nick Letzepis, Member, IEEE.

Abstract
Low probability of detection (or covert) communication refers to the scenario where information
must be sent reliably to a receiver, but with low probability of detection by an adversary. Recent
works on the fundamental limits of this communication problem have established achievability and
converse bounds that are asymptotic in the block length of the code. This paper uses Gallager’s random
coding bound to derive a new achievability bound that is applicable to low probability of detection
communication in the finite block length regime. Further insights are unveiled that are otherwise hidden
in previous asymptotic analyses.

I. I NTRODUCTION
Often in defence and national security, information must be conveyed with low probability of
detection (LPD) by unauthorised adversaries. The problem is similar to secure communications,
but stricter in the sense that the sender cannot afford the transmission to be detected let alone
its message being compromised. In an information theoretic setting, the problem becomes one
of maximising the amount of information that can be sent reliably, whilst satisfying a constraint
on the probability of detection. A number of authors have studied LPD communication in this
context [1], [2], [3], [4], [5].
In [1], Hero studied the LPD problem in the context of space-time codes for multi-antenna
communication subjected to quasi-static fading. Rather than constraining the probability of
N. Letzepis is with the Cyber and Electronic Warfare Division, Defence Science and Technology Group, West Avenue,
Edinburgh SA 5111, Adelaide, Australia. Email: nick.letzepis@ieee.org.

January 17, 2018

DRAFT

2

detection, Hero maximises the information rate whilst constraining the Chernoff information [6,
Theorem 11.9.1], i.e. the best achievable exponent in the adversary’s Bayesian probability of
error. A salient point here is that Hero is only constraining the rate at which detection error
probability decays to zero with the code word length (or block length), not the detection
error probability itself. It turns out that for additive white Gaussian noise (AWGN) channels
the Shannon capacity of the channel is zero for a constraint explicitly on the detection error
probability sum, i.e. the sum of the adversary’s false and miss detection error probabilities.
Moreover, in this instance LPD communication obeys the so called square-root law (SRL),
√
i.e. only O( n) bits of information can be transmitted reliably in n channel usages whilst
constraining the detection error probability sum [2]. Recently, Wang et al. [3], [4] proved that
the SRL extends to LPD communication over a broad class of discrete memoryless channels as
√
well. Moreover, they showed that the rate of increase of information with n is proportional to
mutual information maximised over all input distributions subject to a constraint on the relative
entropy. It should be noted, however, that their results assume the adversary observes the same
channel outputs as the intended receiver, which is unrealistic in many practical situations. In [5],
Bloch considers the LPD problem from a resolvability perspective for the more general case
when both the receiver and adversary’s channels are separate discrete memoryless channels (i.e.
they do not observe the same channel outputs). Not only does Bloch prove the SRL in this more
general setting, but also fundamental limits on the asymptotic scaling of the message and key size
when communication must be both covert and secret. Central to the achievability results of [3],
[4], [5] is the use of a low weight, or sparse signalling scheme (as referred to in this paper) to
satisfy the LPD constraint. This is where the probability of sending an innocent symbol (defined
as the channel input when no communication takes place [5]) approaches 1 as n → ∞.
This paper takes a different approach to [2], [3], [4], [5] to establish an achievability bound that
applies to finite block length codes. The contributions of this paper are summarised as follows.
Following important preliminary details in Section II, Section III revisits the implications of
the LPD constraint on the input signalling density. It is shown that the LPD constraint can
be recast as a constraint on the chi-squared distance between the densities of the adversary’s
observations conditioned on transmission and no transmission, similar to [2], [3], [4], [5], but
without using Pinsker’s inequality [7, Theorem 2.33], Taylor series expansions or bounds on

January 17, 2018

DRAFT

3

m 2 {1, . . . , M }
n

X 2C

Tx

Xn

pY n |X n

pW n |X n

Yn

Wn

Rx

Dx

Fig. 1. The LPD communication scenario: the transmitter (Tx) sends message m ∈ {1, . . . , M } to the receiver (Rx) with LPD
by an adversary with a detector (Dx).

the natural logarithm. Using this relationship the spareness factor, defined as the probability
of sending a non-innocent symbol, is derived in terms of the block length, LPD constraint
and chi-squared distance. In Section IV, Gallager’s error exponent [8], [9] is lower bounded in
terms of the sparseness factor and the exponent of the density of the non-innocent symbols.
Combining this result with the constraint on the sparseness factor, a finite block length lower
bound is derived on the number of bits that can be transmitted with non-vanishing LPD and
decoding error probability. Interestingly, in the finite block length regime the bound indicates
there is an optimal block length that maximises the achievable information rate (bits per channel
use), i.e. the achievable rate increases with n until it reaches this optimal block length and then
√
begins decreasing at a rate proportional to 1/ n as a result of the SRL. In the asymptotic
large block length regime, the lower bound can be written in terms of the mutual information
of the Rx’s channel similar to [3], [4], [5]. In Section V, the utility of the finite block length
achievability bound is demonstrated for the well known binary symmetric channel (BSC) and
AWGN channel [6].

II. P RELIMINARIES
Consider the LPD communication scenario shown in Fig. 1 consisting of a transmitter (Tx),
receiver (Rx) and detector (Dx).1 In this scenario, the Tx wishes to send a message to the Rx
1

In related works [2], [3], [4], [5], the Tx, Rx and Dx are referred to as ”Alice”, ”Bob” and ”Willie” respectively.

January 17, 2018

DRAFT

4

with a LPD by the Dx. Let M = (1, . . . , M ) denote the set of possible messages the Tx can
send. For each message, the Tx constructs a code book C consisting of M , n-length code words,
where each code word, xm = (x1 (m), . . . , xn (m)), is generated independently according to the
joint density pX n with support X n . Further assume the symbols (or letters) of each code word
Q
are independently and identically distributed (i.i.d.) so that pX n (x) = ni=1 pX (xi ), xi ∈ X .
To send message m, the Tx transmits code word x(m) to the Rx who observes the corrupted
version y = (y1 , . . . , yn ) ∈ Y n with probability pY n |X n (y|x(m)). Given knowledge of C, the Rx
decodes its observation outputting the decision m̂ and a decoding error occurs when m̂ 6= m.
When no message is transmitted, it is assumed the Tx inputs x0 = (x0 , . . . , x0 ) ∈ X n to the

channel. Using the terminology of [5], x0 is referred to as the innocent symbol, representing the
case where the Tx expends no resources.
Unfortunately for the Tx, the Dx also receives a corrupted version of the code word, w =
(w1 , . . . , wn ) ∈ W n with probability pW n |X n (w|x(m)). The Dx does not know C, but knows the
distribution used to construct it, i.e. pX . Given this knowledge, the Dx attempts to decide whether
the input to its channel was either x0 or x ∈ C. It is assumed the Dx and Rx channels are memoryQ
less and conditionally independent, so that pY n W n |X n (y, w|x) = ni=1 pY |X (yi |xi )pW |X (wi |xi ).
As in [5], it is assumed that pW is dominated by pW |X=x0 to exclude scenarios where the Dx
would always detect the Tx’s code word with non-vanishing probability, or never detect it.2
Similarly it is assumed pY is dominated by pY |X=x0 to ensure the Rx does not have an unfair
advantage over the Dx.

III. D ETECTION E RROR P ROBABILITY
From its observation w the Dx must decide between two hypotheses: H0 , the input to its channel
was x0 ; and H1 , the input to its channel was x ∈ C. The probability of the Dx’s observation
2

In other words, let W0 = {w : pW |X (w|x0 ) = 0}, if pW is dominated by pW |X=x0 then pW (w) = 0 for all w ∈ W0 .

January 17, 2018

DRAFT

5

conditioned on H0 and H1 are given by
Pr{w|H0 } = p

W n |X n

(w|x0 ) =

Pr{w|H1 } = pW n (w) =

n
Y
i=1

n Z
Y
i=1

X

pW |X (wi |x0 )

pX (x)pW |X (wi |x) dx,

(1)
(2)

where (2) assumes the messages are equally likely. Let α and β denote the false and miss
detection probabilities respectively, i.e. α is the probability of deciding H1 when H0 is true, and
β is the probability of deciding H0 when H1 is true. Further define α + β as the detection error
probability sum. Assume the Dx knows the statistics of its observations and employs an optimal
statistical hypothesis test that minimises α + β. From [10, Theorem 13.1.1] for any such optimal
test
α + β = 1 − V (pW n , pW n |X n =x0 )
where V (p, q) =

1
2

R
X

(3)

|p(x)−q(x)| dx is the variational distance between densities p(x) and q(x)

of support X . From this point, the works of [2], [3], [4], [5] proceed to lower bound (3) in terms
of the relative entropy via Pinsker’s inequality [7, Theorem 2.33] and then further approximate
or weaken the bound using Taylor series expansion methods. In particular, using bounds on the
natural logarithm, Bloch [5] bounds the relative entropy in terms of the chi-squared distance
plus other related terms. This paper takes much simpler approach, as given by the following
lemma.
Lemma 1. Define pW n and pW n |X n as in (1) and (2) respectively. Then,
q

1
W0−1 nχ2 (pW k pW |X=x0 )
V (pW n , pW n |X n =x0 ) ≤
2

(4)

where W0−1 (z) = ze−z , z ≥ −1/e, is the inverse of the Lambert-W function on the principle
R
2
branch [11] and χ2 (p k q) , X (p(x)−q(x))
dx is the chi-squared distance.
q(x)

January 17, 2018

DRAFT

6

Proof: By the definition of variational distance,
Z
1
V (pW n , pW n |X n =x0 ) =
pW n (w) − pW n |X n (w|x0 ) dw
2 Wn
Z
pW n (w) − pW n |X n (w|x0 ) q
1
p
pW n |X n (w|x0 ) dw
=
2 Wn
pW n |X n (w|x0 )
s
sZ
2
Z
n
n
n
p
(w)
−
p
(w|x
)
1
W
0
W |X
≤
dw
pW n |X n (w|x0 ) dw
2
pW n |X n (w|x0 )
Wn
Wn
1q 2
χ (pW n k pW n |X n =x0 ),
(5)
=
2
where the second line follows since pW is dominated by pW |X=x0 by assumption and the third
line results from application of Hölder’s inequality. Finally, application of [12, Lemma 3.3.10]
on χ2 (pW n k pW n |X n =x0 ) results in (4) as stated in the lemma.
Hence combining (3) and (4), the constraint on α + β can be written as a constraint on the
chi-squared distance as given in the following corollary.
Corollary 1. Suppose the Tx must constrain α + β ≥ 1 − det for 0 < det < 1. This constraint
can be satisfied by ensuring
χ2 (pW k pW |X=x0 ) ≤
1


4ξ 2 2det
1
=
42det + O(4det )
n
n

(6)

2

where ξ = e− 2 W0 (4det ) .
To avoid detection, it is clear from the above analysis that the Tx should use a code book
whose code words are close to x0 . One approach, in a similar vein as [3], [4], [5], is to use a
sparse signalling scheme, i.e. the Tx generates code words such that symbols x 6= x0 occur very
infrequently. More formally, in this paper the sparse signalling density is defined as follows.
Definition 1 (Sparse signalling density). Let pX̃ (x) denote an arbitrary kernel density. The sparse
signalling density is defined as
pX (x; τ, pX̃ ) = (1 − τ )δ(x − x0 ) + τ pX̃ (x),

(7)

where 0 ≤ τ ≤ 1 is the sparseness factor and δ(x) denotes the Dirac-delta function.
Substituting (7) into (6) translates the detection error probability sum constraint to a constraint
on the sparseness factor, i.e. the constraint α + β ≥ 1 − det can be satisfied using a sparse
January 17, 2018

DRAFT

7

signalling density with
2ξdet
,
τ≤p
nχ2 (pW̃ k pW |X=x0 )
where pW̃ (w) =

R
X

(8)

pX̃ (x)pW |X (w|x) dx is the density of the Dx’s channel outputs induced by

the Kernel density pX̃ .

IV. LPD ACHIEVABILITY B OUND
The achievability results of previous works [2], [3], [4], [5] on LPD communication are only
applicable in the asymptotic large block length regime. The approach of Wang et al. [3], [4] is
based on one-shot achievability bounds [13], [14]. While, Bloch’s approach [5], uses suitably
modified typical sets to enable the application of concentration inequalities. This section takes
a much simpler approach to the aforementioned works, which not only proves the asymptotic
achievability of the SRL, but also yields additional insights on the number of achievable bits
in the finite block length regime. Central to this approach is Gallager’s coding theorem [8], [9]
stated as follows.
Theorem 1 (Gallager’s coding theorem [8], [9]). For any pX n (x) =

Qn

i=1

pX (xi ) and 0 ≤ ρ ≤ 1

there exists a code with M , n-length code words with average probability of decoding error,
dec > 0, such that
i

h
ρ
dec ≤ exp −n E0 (ρ, pX , pY |X ) − log M ,
n

(9)

where
E0 (ρ, pX , pY |X ) = − log

Z Z
Y

 1
pX (x) pY |X (y|x) 1+ρ dx


1+ρ
dy.

(10)

X

The maximisation of the square-bracketed term in (9) over pX and ρ is Gallager’s well known
error exponent and describes how rapid the average probability of decoding error reduces with
increasing block length [8], [9]. When sparse signalling is employed, (10) is lower bounded as
follows.

January 17, 2018

DRAFT

8

Lemma 2. Suppose the input density is sparse as defined by (7) with 0 ≤ τ < 1, then for
0 ≤ ρ ≤ 1,
i
h

1
E0 (ρ, pX , pY |X ) ≥ −(1 + ρ) log 1 − τ 1 − e− 1+ρ E0 (ρ,pX̃ ,pY |X )


1
≥ (1 + ρ)τ 1 − e− 1+ρ E0 (ρ,pX̃ ,pY |X )

(11)
(12)

Proof: See Appendix A.
From Lemma 2, it can be seen that the lower bound (12) is proportional the sparseness factor
τ times a factor that is dependent on the E0 value of the underlying kernel density. Moreover,
when τ = 1, (11) reverts to (10). On the other hand if τ = 0, or E0 (ρ, pX̃ , pY |X ) = 0 then the
lower bound is also zero. Since (12) is proportional to the sparseness factor τ and from (8) τ is
√
O(1/ n) to satisfy the LPD constraint, then the following theorem is proved.
Theorem 2. Suppose the Tx employs the sparse signalling scheme (7) with sparseness factor (8).
Then there exists a code with M , n-length code words with an average decoding error probability
not exceeding dec and probability of detection not exceeding det such that for any 0 ≤ ρ ≤ 1,
√
1
log2 M ≥ det nL(ρ) + log2 dec .
ρ

(13)

where
2ξ
L(ρ) =
log 2



1+ρ
ρ



1

1 − e− 1+ρ E0 (ρ,pX̃ ,pY |X )
p
χ2 (pW̃ k pW |X=x0 )

!
(14)

From (13), some interesting insights can be made. Firstly, for large block lengths the achievability
bound is dominated by the first term of (13), and as expected from the analyses of [2], [3], [4],
√
[5], scales asymptotically with O( n) as a consequence of the SRL. The quantity L(ρ) is of a
similar form as [4, eq. (28)], but now takes into account both the Rx and Dx’s channel statistics,
whereas [4, eq. (28)] assumes the Dx has the same observations as the Rx. In the asymptotic
large block length regime one has the following corollary.
Corollary 2.
lim

log2 M
2ξ
I(X̃; Y )
√ ≥
p
2
log 2 χ (pW̃ k pW |X=x0 )
n

n→∞ det

where I(X; Y ) ,

R R
X

Y

(15)

(x,y)
dy dx is the mutual information between random
pXY (x, y) log pXpXY
(x)pY (y)

variables X and Y [6, Sec 2.3].
January 17, 2018

DRAFT

9

Proof: Dividing both sides of (13) by

√
n, yields limn→∞

Theorem 2], E0 (ρ, pX̃ , pY |X ) is a non-decreasing function and

∂
∂ρ

√1
n

log2 M ≥ det L(ρ). From [8,

E0 (ρ, pX̃ , pY |X )

ρ=0

= I(X̃; Y ).

Therefore L(ρ) is maximised when ρ = 0 and hence (15) is obtained using L’Hospital’s Rule [15,
Sec. 3.4] on (14).
From (15) it can be observed that replacing χ2 (pW̃ k pW |X=x0 ) with χ2 (pỸ k pY |X=x0 ) and
√
√
multiplying by ξ(log 2)/ 2 ≈ (log 2)/ 2 results in [4, eq. (28)]. The first alteration is required
to ensure the Dx and Rx have the same channel as assumed in [4], and the log 2 scaling is to
√
convert from bits to nats. The extra division by 2 is a consequence of [4] constraining the
relative entropy rather than the variational distance as done in this paper. There is a further
subtle difference between (15) and [4, eq. (28)], in that (15) is expressed directly in terms of
I(X̃; Y ) whereas [4, eq. (28)] requires E[D(pY |X=X̃ k pY |X=x0 )], a consequence of using the
Taylor series expansion of I(X; Y ) in τ .
In contrast to Corollary 2, for the finite block length regime the last term of (13) becomes
significant, particularly if one considers the information rate as demonstrated in the following
corollary.
Corollary 3. In Theorem 2, define the achievable information rate
R(n) ,

det L(ρ)
1
1
log2 M ≥ √
+
log2 dec
n
nρ
n

for any 0 ≤ ρ ≤ 1. Then (16) is maximised by
√

n∗ =

2 log2

1
dec

det ρL(ρ)

(16)

(17)

for which
R(n∗ ) ≥

2det
2
1 ρL (ρ).
4 log2 dec

(18)

Moreover, the number of achievable bits that can be sent in n∗ channel uses is given by
k ∗ = n∗ R(n∗ ) =

1
1
log2
.
ρ
dec

(19)

Corollary 3 shows that in the finite block length regime, the achievable rate first increases with
n to a maximum value R(n∗ ) and then begins decreasing as the SRL dominates. From (17) it
can be seen that n∗ increases with decreasing det and dec , while on the other hand, from (18),

January 17, 2018

DRAFT

10

R(n∗ ) decreases. Interestingly, from (19), the number of achievable bits that can be sent in n∗
channel uses is only dependent on dec .

V. LPD C OMMUNICATION E XAMPLES
To highlight the insights of the previous section, this section applies Theorem 2 to two well
known channels studied in the literature - the BSC and AWGN channel [6].

A. Binary Symmetric Channel
Theorem 3. Suppose the Dx and Rx’s channels are independent BSCs with crossover probabilities Dx and Rx respectively. Then for any 0 ≤ ρ ≤ 1,
log2 M ≥

√

ndet LBSC (ρ, Rx , Dx ) +

1
log2 dec
ρ

(20)

where

p
Dx (1 − Dx )
2ξ
1+ρ
LBSC (ρ, Rx , Dx ) =
log 2
ρ
(1 − 2Dx )

h
ρ i
1
ρ
1
1+ρ
1+ρ
1+ρ
1+ρ
− Rx
− Rx .
× (1 − Rx )
(1 − Rx )

(21)

In addition,
p
1 − 2Rx
1
lim √ log2 M ≥2det ξ Dx (1 − Dx )
log2
n→∞
1 − 2Dx
n



1 − Rx
Rx


.

(22)

Proof: See Appendix B
From (21), LBSC (ρ, Rx , 0) = LBSC (ρ, Rx , 1) = 0, i.e. when the Dx has a perfect (or perfectly
inverted) channel, no information can be sent covertly. On the other hand, LBSC (ρ, Rx , 12 ) = ∞,
i.e. when Dx’s channel is useless for detection the Tx can send information at an order greater
√
than n. In fact, for this case, constraint (6) is redundant, since χ2 (pW k pW |X=x0 ) = 0 regardless
of pX and therefore the Tx can transmit unfettered at the capacity of the Rx’s channel. If the
Rx’s channel is useless, LBSC (ρ, 21 , Dx ) = 0, as expected, no information can be sent. As shown
in Appendix B the lower bound (20) requires taking the limit pX̃ (1) → 0. This peculiarity does

January 17, 2018

DRAFT

11

not imply that a binary 1 is never transmitted, but rather results in the overall probability of
√
sending a 1, i.e. τ pX̃ (1), being O(1/ n).
Fig. 2 illustrates these insights for the case when det = 0.1, dec = 10−3 , and various Dx . The
solid lines plot the finite block length achievable information rate, i.e. (20) divided n, and exhibits
the behaviour as expected from Corollary 3. For small n, the achievable rate increases with n
up to a maximum value and then decreases with n as the SRL dominates. The dashed lines plot
√
the asymptotic large block length achievable rate, i.e. (22) divided by n/det , confirming the
convergence of the finite block length results to the asymptotic large block length bound as n
increases. Interestingly, this convergence is slow with n, which further highlights the importance
of finite block length analysis in LPD communication system design.

B. AWGN Channel
For the AWGN channel, applying Theorem 2 yields the following result.
Theorem 4. Suppose the Rx and Dx channels are independent AWGN channels with noise
2
2
variance σRx
and σDx
respectively. Assuming a Gaussian kernel density, then for any 0 ≤ ρ ≤ 1,
√
2
1
2ndet ξ σDx
+ log2 dec .
(23)
log2 M ≥
2
(1 + ρ) log 2 σRx ρ

Provided
4
1 σRx
1
log2
2
4
2
2ξ det σDx
dec

n > nmin =

(24)

then (23) is maximised by
∗

ρ =q

"

1
n
nmin


1+

−1

 41 #

n

.

nmin

(25)

The peak achievable information rate and the block length it occurs at are given by
Rawgn (n∗ ) =
n∗ =

4
2det ξ 2
σDx
1
4
σRx
8(log 2) log dec

(26)

4
8 log2 dec σRx
4
2det ξ 2 σDx

(27)

respectively. Moreover, the number of achievable information bits that can be sent using n∗
channel uses is given by
k ∗ = n∗ Rawgn (n∗ ) = log2
January 17, 2018

1
dec

.

(28)
DRAFT

12

Proof: See Appendix C.
From Theorem 4 it is clear that the ratio

2
σDx
2
σRx

plays an important role in the achievability bound.

Intuitively, the noisier the Dx’s channel is relative to the Rx, then more bits are achievable with
LPD and the smaller the minimum block length (24). Note that from (28), while k ∗ is constant, as
2
σDx
2
σRx

decreases, the required number of channel uses (27) increases and hence the peak achievable

information rate decreases. These insights are illustrated in Fig. 3 which plots (23) divided by
n (solid lines) compared to the asymptotic large block length result (dashed lines), i.e. the first
term of (23) divided by n with ρ = 0, for det = 0.1, dec = 10−3 and various

2
σDx
2 .
σRx

In addition,

the minimum block length required to support a positive achievable information rate (24) is also
shown (dot-dashed line).

ACKNOWLEDGEMENT
The author is thankful to Prof. Albert Guillén i Fàbregas for insightful discussions on the work
presented in this paper.

VI. C ONCLUSION
A PPENDIX A
P ROOF OF L EMMA 2
Using (7) the integral in (10) can be written as
1+ρ
Z Z
1

 1+ρ
I=
pX (x) pY |X (y|x)
dx
dy
Y

X

Z 
=
Y

(1 − τ )p

1
1+ρ

Z
(y|x0 ) + τ
X

1
1+ρ

pX̃ (x)pY |X (y|x) dx

1+ρ
dy

1+ρ
1
1+ρ ! 1+ρ
Z 
Z
1
1

=
(1 − τ )pY1+ρ
pX̃ (x)pY1+ρ
dy
|X (y|x0 ) + τ
|X (y|x) dx


Y

January 17, 2018

(29)

X

DRAFT

Information Rate (bits/channel use)

13

10 -2
Finite n Bound
Asymptotic n Bound

10 -3
ǫDx = 0.4

10 -4

ǫDx = 0.2

10 -5

ǫDx = 0.1

10 -6
10 2

10 4

10 6

10 8

10 10

Blocklength n
LPD achievable information rate (bits/channel use) for the BSC with dec = 10−3 , det = 0.1, Rx = 0.1 and various
√
Dx . Solid lines plot (20) divided by n and dashed lines plot (22) divided by n
Fig. 2.

.

Using Minkowski’s inequality,
1+ρ

1
(Z Z
1
 1+ρ
1+ρ ) 1+ρ
Z
1

I≤
(1 − τ )1+ρ pY |X (y|x0 ) dy
+τ
pX̃ (x)pY1+ρ
dy
|X (y|x) dx
Y



Y



(Z Z

= 1 − τ 1 −
h



Y

pX̃ (x)pY |X (y|x) dx

1
− 1+ρ
E0 (ρ,pX̃ ,pY |X )

= 1−τ 1−e

January 17, 2018

X

1
1+ρ

i1+ρ

X

1+ρ
1
) 1+ρ

1+ρ
dy


(30)

DRAFT

Information Rate (bits/channel use)

14

10 -2
Finite n Bound
Asymptotic n Bound
nmin

10 -3

10

2
σDx
2
σRx

-4

2
σDx
2
σRx

10 -5

10 -6
10 2

10 4

=4

=1
2
σDx
2
σRx

=2

10 6

10 8

10 10

Blocklength n
Fig. 3.

LPD achievable information rate (bits/channel use) for the AWGN channel with dec = 10−3 , det = 0.1 and various

2
2
. Solid lines plot (23) divided by n and dashed lines plots the asymptotic large block length bound.
/σRx
noise power ratios σDx

The dot-dashed lines show the minimum block length (24).

A PPENDIX B
P ROOF OF T HEOREM 3
For the BSC it is not difficult to show that

E0 (ρ, pX̃ , pY |X ) = E0 (ρ, u, Rx ) = − log

(1 − u)(1 − Rx )


1+ρ !
1
1
1+ρ
+ (1 − u)Rx
+ u(1 − Rx ) 1+ρ
χ2 (pW̃ k pW |X=x0 ) = χ2 (u, Dx ) =

January 17, 2018

u2 (1 − 2Dx )2
Dx (1 − Dx )

1
1+ρ

1
1+ρ

1+ρ

+ uRx

(31)
(32)

DRAFT

15

Substituting the above expressions into (14) yields

p
Dx (1 − Dx )
1+ρ
2ξ
LBSC (ρ, u, Rx , Dx ) =
log 2
ρ
(1 − 2Dx )
"
(
1+ρ
1
1
1
1+ρ
1+ρ
× 1−
(1 − u)(1 − Rx )
+ uRx
u


1
1+ρ

+ (1 − u)Rx + u(1 − Rx )

1
1+ρ

1 #
1+ρ ) 1+ρ
.

Now consider the function g(x) and its derivative, i.e.
1
g(x) = [1 − f (x)]
x
1
1
g 0 (x) = − 2 [1 − f (x)] − f 0 (x)
x
x
where

f (x) = [(1 − x)a + xb]1+c + [(1 − x)b + xa]1+c

(33)

(34)
(35)

1
1+c

f 0 (x) = (b − a)f −c (x) ([(1 − x)a + xb]c − [(1 − x)b + xa]c )

(36)
(37)

for 0 ≤ a, b, c ≤ 1. Suppose a ≥ b and 0 ≤ x ≤ (1 − b)/(a − b). Then, from the above,

g 0 (x) < 0 when [(1 − x)a + xb]c ≤ [(1 − x)b + xa]c , or x ≥

1
.
2

Now suppose b ≥ a and

0 ≤ x ≤ (1 − a)/(b − a). Then g 0 (x) < 0 when [(1 − x)a + xb]c ≥ [(1 − x)b + xa]c , or x ≤ 12 .
Hence, g(x) is a decreasing function for 0 ≤ x ≤ 1. Moreover, using L’Hospital’s Rule
(ac − bc )(a − b)
lim g(x) =
c
x→0
(a1+c + b1+c ) 1+c
1

(38)

1

Hence, using a = (1−) 1+ρ , b =  1+ρ and c = ρ, with some simplification (33) reduces to (21) as
stated. Finally, from Corollary 2, applying L’Hospital’s Rule to obtain limρ,u→0 LBSC (ρ, u, Rx , Dx )
results in (22).
A PPENDIX C
P ROOF OF T HEOREM 4
x2 √
For the AWGN channel with pX̃ (x) = e− 2P / 2πP computing the required integrals yields


1 P
ρ
2
E0 (ρ, pX̃ , pY |X ) = E0 (ρ, P, σRx ) = log 1 +
(39)
2
2
1 + ρ σRx
1
2
χ2 (pW̃ k pW |X=x0 ) = χ2 (P, σDx
)= q
− 1.
(40)
2
1 − σP4
Dx

January 17, 2018

DRAFT

16

Note that (39) is equal to [8, eq. (124)] with r = 0, since the LPD constraint is accounted for
by (8). Substituting the above above expressions into (14) yields

− 12


2ξ
1+ρ 
1
2
2
q
LAWGN (ρ, P, σRx
, σDx
)=
− 1
P2
log 2
ρ
1− 4
σDx

"


× 1− 1+

1 P
2
1 + ρ σRx

#
ρ
− 2(1+ρ)
.

(41)

Now consider the function
1 − (1 + ax)−c √
f (x) = q
= 2ac
√ 1
−
1
2
1−x



1 − 12 c(c + 1)a2 x + O(x2 )
3 2
x + O(x4 )
1 + 16


(42)

for a, c > 0. It is clear from the expansion of f (x) that it is a decreasing function for 0 < x < 1.
Moreover,
lim f (x) =

√

x→0

Therefore, using a =

2

1 σDx
2
1+ρ σRx

and c =

2ac.

(43)

ρ
2(1+ρ)

in (43) results in
√
2
2ξ
σDx
2
2
lim LAWGN (ρ, P, σRx , σDx ) =
.
2
P →0
(1 + ρ) log 2 σRx

(44)

Hence substituting (44) into (13) yields (23) as stated. Now consider the function g(x) =
for a > b > 0. It is not difficult to show that g(x) is maximised when x =

b
a−b

a
− xb
1+x

1+

pa
.
b

Applying this solution to (23) yields the optimal value for ρ, i.e. (25). Applying Corollary 3 and
maximising over ρ yields (26) and (27). Finally (28) is simply the product of (26) and (27).

R EFERENCES
[1] A. O. Hero III, “Secure space-time communication,” IEEE Trans. Info. Theory, vol. 49, no. 12, pp. 3235–3249, 2003.
[2] B. A. Bash, D. Goeckel, and D. Towsley, “Limits of reliable communication with low probability of detection on AWGN
channels,” IEEE J. Sel. Areas Commun., vol. 31, no. 9, pp. 1921–1930, Sep. 2013.
[3] L. Wang, G. W. Wornell, and L. Zeng, “Fundamental limits of communication with low probability of detection,” in Proc.
Int. Symp. on Info. Theory, Hong Kong, 2015.
[4] L. Wang, G. W. Wornell, and L. Zeng, “Fundamental limits of communication with low probability of detection,” IEEE
Trans. Info. Theory, vol. 62, no. 6, pp. 3493–3503, June 2016.

January 17, 2018

DRAFT

17

[5] M. R. Bloch, “Covert communication over noise channels: A resolvability perspective,” IEEE Trans. Info. Theory, vol.
62, no. 5, pp. 2334–2354, May 2016.
[6] T. M. Cover and J. A. Thomas, Elements of Information Theory, Wiley, 2nd edition, 2006.
[7] R . W. Yeung, A First Course in Information Theory, Springer, New York, 2002.
[8] R. G. Gallager, “A simple derivation of the coding theorem and some applications,” IEEE Trans. Info. Theory, vol. 11,
no. 1, pp. 3–18, Jan. 1965.
[9] R. G. Gallager, Information Theory and Reliable Communication, John Wiley and Sons Inc., 1968.
[10] E. L. Lehmann and J. P. Romano, Testing Statistical Hypothesis, Springer, New York, 2005.
[11] R. M. Corless, G. H. Gonnet, D. E. G. Hare, D. J. Jeffrey, and D. E. Knuth, “On the Lambert W function,” Advances in
Computational Mathematics, vol. 5, no. 1, pp. 329–359, Dec 1996.
[12] R. D. Reiss, Approximate distributions of order statistics: with applications to nonparametric statistics, Springer series
in statistics. Springer, 1989.
[13] L. Wang, R. Colbeck, and R. Renner, “Simple channel coding bounds,” in Proc. Int. Symp. on Info. Theory, Seoul, South
Korea, 2009.
[14] Y. Polyanskiy, H. V. Poor, and S. Verdú, “Channel coding rate in the finite block length regime,” IEEE Trans. Info. Theory,
pp. 2307–2359, May 2010.
[15] M. Abramowitz and I. A. Stegun, Handbook of mathematical functions with formulas, graphs and mathematical tables,
United States Department of Commerce, USA, 10th edition, 1972.
[16] G. Anderson, M. Vamanamurthy, and M. Vuorinen, “Monotonicity rules in calculus,” The American Mathematical Monthly,
vol. 113, no. 9, pp. 805–816, 2006.

January 17, 2018

DRAFT

