1

Zero-Error Capacity of
P -ary Shift Channels and FIFO Queues

arXiv:1605.02441v2 [] 10 Sep 2017

Mladen Kovačević, Member, IEEE, Miloš Stojaković, and Vincent Y. F. Tan, Senior Member, IEEE

Abstract—The objects of study of this paper are communication channels in which the dominant type of noise are symbol
shifts, the main motivating examples being timing and bit-shift
channels. Two channel models are introduced and their zeroerror capacities and zero-error-detection capacities determined
by explicit constructions of optimal codes. Model A can be
informally described as follows: 1) The information is stored in
an n-cell register, where each cell is either empty or contains
a particle of one of P possible types, and 2) due to the
imperfections of the device each of the particles may be shifted
several cells away from its original position over time. Model B is
an abstraction of a single-server queue: 1) The transmitter sends
packets from a P -ary alphabet through a queuing system with an
infinite buffer and a First-In-First-Out (FIFO) service procedure,
and 2) each packet is being processed by the server for a random
number of time slots. More general models including additional
types of noise that the particles/packets can experience are also
studied, as are the continuous-time versions of these problems.
Index Terms—Zero-error code, zero-error detection, bit-shift
channel, peak-shift, timing channel, queue, delay.

I. I NTRODUCTION

setting where timing channels naturally arise are molecular
communications [6], [15]. The information here is encoded in
the number and the types of the particles released at given
time instants, and the noise are random delays that particles
experience on their way to the receiving side, caused by their
interaction with the fluid medium.
Motivated by the above examples, we analyze here two
channel models that are intended to capture such impairments.
In the remainder of this section we shall define these models
formally and describe their relation to the models previously
studied in the literature. In Section II, a construction of optimal
zero-error codes for Model A is given and a characterization
of its zero-error capacity is obtained. In Section III the
corresponding results for Model B are derived. In Section
IV we determine the zero-error-detection capacity of the two
channels. Section V contains the analysis of the continuoustime versions of both models. A brief conclusion and several
pointers for further work are stated in Section VI.

AND PRELIMINARIES

In several communication and information storage systems
the dominant type of “noise” introduced by the channel
are shifts of symbols of the transmitted sequence. A classic
example is the so-called bit-shift or peak-shift channel which
has been introduced as a model for some magnetic recording
devices wherein the electric charges (the 1-bits) can be shifted
to the left or to the right of their original position due to various
physical effects (see, e.g., [17]). Another familiar scenario
is the transmission of information packets through a queue
with random processing times. Such a queue is intended to
model, e.g., a network router processing the packets and then
forwarding them towards their destination. The capacity of
such channels can in general be increased by encoding the
information in the transmission times of packets in addition
to their contents [3], in which case the unknown delays of
packets at the output of the queue represent the noise. Another
Date: September 10, 2017.
M. Kovačević and V. Y. F. Tan are supported by the Singapore Ministry
of Education (MoE), under Tier 2 Grant R-263-000-B61-112. M. Stojaković
is partly supported by the Ministry of Education, Science, and Technological
Development, Republic of Serbia, and the Provincial Secretariat for Higher
Education and Scientific Research, Province of Vojvodina.
M. Kovačević is with the Department of Electrical & Computer Engineering, National University of Singapore, Singapore 117583 (email:
mladen.kovacevic@nus.edu.sg).
M. Stojaković is with the Department of Mathematics and Informatics,
Faculty of Sciences, University of Novi Sad, 21000 Novi Sad, Serbia (email:
milos.stojakovic@dmi.uns.ac.rs).
V. Y. F. Tan is with the Department of Electrical & Computer Engineering
and the Department of Mathematics, National University of Singapore,
Singapore 117583 (email: vtan@nus.edu.sg).

A. Model A
Let n, P, K1 , K2 be integers, with n, P, K2 ≥ 0 and
K1 ≤ K2 . The channel inputs are sequences of length n over
the alphabet {0, 1, . . . , P }. Think of such an input sequence
x = (x1 , . . . , xn ) as representing a state of an n-cell register,
where xi = 0 means that the i’th cell is empty, while xi = p,
p ∈ {1, . . . , P }, means that the i’th cell contains a particle of
“type” p. For any such input sequence the channel outputs one
of the sequences z = (z1+K1 , . . . , zn+K2 ) satisfying the following conditions: 1) z is of length n′ = n + K2 − K1 , 2) The
subsequences x̃ = (xi1 , . . . , xim ) and z̃ = (zj1 , . . . , zjm′ ),
obtained by deleting all the zeros in x and z respectively, are
identical (and hence m = m′ ), and 3) K1 ≤ jl − il ≤ K2
for all 1 ≤ l ≤ m. Each of these sequences is output with
positive probability. If x can produce z at the channel output,
we write x
z.
In words, the i’th particle is shifted ki cells to the right of
its original position over time, where K1 ≤ ki ≤ K2 , but no
two particles can swap cells or end up in the same cell (if
ki < 0, then this is of course a shift to the left for |ki | cells).
We assume that there are enough empty cells, to the left or
to the right of the register, for the boundary particles to be
able to shift; this assumption simplifies the analysis slightly
but has no influence on the results.
The channel just described will be referred to as the P -ary
Shift Channel with parameters K1 , K2 , or ShC(P ; K1 , K2 )
for short. ShC(P ; K) will stand for ShC(P ; 0, K). Further
generalization of this model including additional types of noise

2

will be discussed in Section II-C, and its continuous-time
version in Section V-A.
B. Model B
Let n, P, K be nonnegative integers. The channel inputs are
sequences of length n over the alphabet {0, 1, . . . , P }, but
we now think of a sequence x = (x1 , . . . , xn ) as describing
a stream of packets entering a queue, xi = 0 meaning that
the i’th time slot is empty, and xi = p, p ∈ {1, . . . , P },
that a packet of “type” p was transmitted in that slot. For
any such input sequence the channel outputs one of the sequences z = (z1 , . . . , zn′ ), satisfying the following conditions:
1) z is of length n′ ≥ n, and if n′ > n its last symbol,
zn′ , is nonzero, 2) The subsequences x̃ = (xi1 , . . . , xim ) and
z̃ = (zj1 , . . . , zjm′ ), obtained by deleting all the zeros in x
and z, respectively, are identical (and hence m = m′ ), and
3) 0 ≤ jl − max{il , jl−1 + 1} ≤ K for all 1 ≤ l ≤ m,
where j0 = 0. Each of these sequences is output with positive
probability.
In words, the first packet is delayed for at most K slots due
to processing (it was sent in slot i1 and received in slot j1 ). If
the second packet arrives at the queue while the first packet is
being processed, it has to wait for the server to become free,
and the first available slot when it itself starts being processed
is j1 + 1; otherwise it can be processed immediately when it
arrives, which is in slot i2 , etc. Thus, every packet waits in
the queue for the server to become free—so-called First-InFirst-Out (FIFO) service procedure—and is then processed for
a randomly chosen number of slots, this number being ≤ K.
Observe that the total delay of a packet can be much larger
than K due to the possibility of waiting in the queue, and
consequently the output sequence can be as long as (K + 1)n.
As we shall explain shortly (see Section I-C), the probabilistic description of this channel needs to be specified too, even
though we are analyzing only zero-error problems. We assume
that each packet is processed for
PKk ∈ {0, 1, . . . , K} slots with
probability ϕ(k) > 0, where k=0 ϕ(k) = 1, independently
of everything else. Denoting the random variable which represents the processing time by κ, the average
PK processing time
of a packet can be written as Eϕ [κ] = k=0 kϕ(k).
The channel described above will be referred to as
the Discrete-Time Queue with bounded Processing time,
DTQP(P ; K; ϕ). Its generalization including additional types
of noise will also be discussed in Section III-B, and its
continuous-time version in Section V-B.
Note that the shift channel ShC(P ; K) can also be seen
as a discrete-time queue with an infinite buffer and a FIFO
service procedure, but in which the residence times of the
packets are bounded by K, rather than their processing times
(the residence time is the total time the packet spends in the
system, either waiting to be processed, or being processed).
C. Zero-Error Codes and Zero-Error Capacity
An error-correcting code of length n for a particular channel
is a nonempty subset of the set of all possible inputs of length
n. A code C(n) is said to be a zero-error code if its error
probability is equal to zero under optimal decoding. In other

words, the requirement is that all possible errors allowed in the
model can be corrected, or equivalently, that no two different
codewords x, y ∈ C(n) can produce the same sequence z at
the channel output.
For a given code C(n), denote by Lav (n) the average length
of the channel output, the average being taken over all codewords and channel statistics. (The dependence of Lav (n) on the
code and the channel is suppressed
notational simplicity.)
P for P
1
z},
In symbols, Lav (n) = |C(n)|
x∈C(n)
z |z| · Pr{x
where |z| denotes the length of a sequence z and Pr{x
z}
the probability that z is obtained at the channel output when
x is at its input.
Example 1. Consider a code C(n) for the DTQP(1; K; ϕ)
consisting of a single codeword x = (1, . . . , 1) (n identical
packets sent in n successive slots). Denoting the processing
time of the i’th packet by κi , we
Pncan express the length of the
output sequence z as L(n) = i=1 (1 + κi ) (κi ’s are assumed
independent and distributed according to ϕ). Its average value
is Lav (n) = n(1 + Eϕ [κ1 ]). This fact will be used in the proof
of Theorem 6.
N
We define the rate of a code C(n) as Lav1(n) log |C(n)|, where
log is to the base 2. Finally, the zero-error capacity of a
channel is the lim sup of the rates of optimal zero-error codes
(i.e., zero-error codes having the largest possible cardinality)
of length n → ∞ for that channel.
Remark 1 (Code rate). The above definition of the code rate
may seem a bit unusual so we shall elaborate. In channels
with shifts and delays, the length of the output sequence is a
random variable and is in general different from the length of
the corresponding input. Therefore, normalizing the number
of transmitted bits of information, log |C(n)|, by the average
time it takes the receiver to obtain the entire sequence, Lav (n),
is a natural measure of rate of transmission through such
channels. In channels where the length of each possible output
is the same as the length of the corresponding input, we have
Lav (n) = n and the definition of rate reduces to the usual
one. More generally, when Lav (n) = n + o(n), we can again
use the standard definition for the purpose of determining
the capacity because only the asymptotic behavior is relevant
here. This is the case in the ShC(P ; K) for instance, where
Lav (n) ≤ n+K. However, in the case of the DTQP the length
of the output can differ from that of the corresponding input
by a multiplicative constant, and the actual behavior of Lav (n)
will have to be taken into account. This is the reason why
the probability distribution ϕ is included in the description of
the DTQP—the zero-error capacity of this channel in general
depends on it, or at least on its mean.
N
Remark 2 (Concatenated codewords). If one is interested in
the regime of communication where multiple codewords are
being sent in succession, then the notion of zero-error code
needs to be redefined because shifts of symbols can cause
interference between successive codewords. The requirement
in that case is that no two sequences of codewords can produce
the same output [12, Def. 2]. The zero-error capacity, however,
is the same under both definitions.
N

3

Remark 3 (Zero-error capacity). Intuitively, the zero-error
capacity of a channel should be defined as the supremum of
the rates of all zero-error codes for that channel. In most of
the studied models this supremum is equal to the lim sup, and
in fact to the limit of the rates of optimal codes [10]. This does
not necessarily hold for the channels treated here—a zero-error
code of length n may have rate higher than the capacity. This
is a consequence of the definition of the code rate via Lav (n),
and especially manifests itself in the case of the DTQP. It
should be noted, however, that only a bounded amount of
information, i.e., a fixed number of bits, can be transmitted
at such a rate because the code is of finite length, and sending
multiple codewords in succession does not guarantee that the
zero-error property will be preserved (Remark 2). Adopting the
lim sup definition seems to be necessary in order to determine
the zero-error capacity analytically, and this quantity then has
the meaning of the largest rate at which an unbounded amount
of information can be transmitted error-free.
N

D. Previous Work
Models most closely related to the shift channel introduced
in Section I-A are those in [17], [13], [12]. In particular,
[13] studies the zero-error capacity of the bit-shift channel
ShC(1; −K, K) under additional constraints on input sequences (the so-called (d, k)-runlength limited sequences [8]),
and [12] studies a generalization of the ShC(1; K) wherein
multiple (but identical) particles per slot are allowed. We
analyze here generalizations of these models that include
arbitrary shifts (K1 , K2 ), multiple types of particles (P ≥ 1),
additional types of noise that these particles can experience,
and the continuous-time models. We also mention the work
[5] where a particular kind of shift channel was studied and
bounds on its zero-error capacity derived. The exact value of
the zero-error capacity for that model was determined in [11]
using methods very similar to those used here.
The zero-error-detection problem that we address in Section
IV has not been studied before for shift channels, timing
channels, and the like.
As for queuing channels such as the DTQP, this is to our
knowledge the first work addressing zero-error problems for
such models. Shannon capacity of queuing systems, on the
other hand, is relatively well-studied. The seminal work on this
subject is [3] (continuous-time case), which was followed by
[4], [20] (discrete-time case); models with bounded processing
time were analyzed in [16]. Our work may be seen as the zeroerror counterpart of these and similar information-theoretic
studies of queuing systems.

II. Z ERO - ERROR

CAPACITY OF THE SHIFT CHANNEL

In this section we study error-free communication through
the shift channel and give a characterization of its zero-error
capacity. We also state a generalization of these results to the
case where the channel introduces some other types of noise
in addition to the shifts.

A. Reduction to the ShC(1; K)
Before proceeding with the analysis, we point out in this
subsection several simple, but important facts about the effect
of the ShC(P ; K1 , K2 ) on the input sequences. The first such
observation is that codes for this channel depend only on
K = K2 − K1 and not on the particular values K1 , K2 , which
means that there is no loss in generality in focusing on the case
ShC(P ; K) ≡ ShC(P ; 0, K).
Lemma 1. Every zero-error code for the ShC(P ; K1 , K2 ) is
a zero-error code for the ShC(P ; K2 − K1 ), and vice versa.
Proof. Just observe that the receiver can shift all the received
particles for another K1 cells to the left (or, alternatively, shift
its point of reference K1 cells to the right) and thus “create”
the channel with parameters 0 and K2 − K1 . This clearly does
not affect the decoding process and the zero-error property of
the code.
The second observation is that the shift-channel does not
affect the Hamming weight of the transmitted codeword. This
implies that an optimal zero-error code of length n for the
ShC(P ; K) is the disjoint union of optimal zero-error codes of
length n and weight W , over all W ∈ {0, 1, . . . , n}. Denoting
the cardinality of these codes by MP ;K (n) and MP ;K (n, W ),
respectively, we can write
n
X
MP ;K (n) =
MP ;K (n, W ).
(1)
W =0

Therefore, it suffices to focus on the constant-weight case.
Finally, the analysis of communication with several types
of particles can be reduced to that with a single type only,
i.e., P = 1. In other words, we can treat the information
contained in the positions of the particles and that in the types
of the particles separately (see also [3, Sec. IV]). Before stating
this more formally, we introduce two notational conventions:
For x ∈ {0, 1, . . . , P }n , let x denote its indicator sequence—
binary sequence having zeros at the same positions as x, i.e.,
xi 6= 0 ⇔ xi = 1, and let x̃ be the sequence obtained by
deleting all the zeros in x.
Proposition 2. Let C1;K (n) be an optimal zero-error code of
length n for the ShC(1; K). Then
o
n
(2)
CP ;K (n) = x ∈ {0, 1, . . . , P }n : x ∈ C1;K (n)

is an optimal zero-error code of length n for the ShC(P ; K).

Proof: Since insertions, deletions and reordering of particles are not possible, two sequences x, y ∈ {0, 1, . . . , P }n
can be confusable (i.e., can produce the same output) in
the ShC(P ; K) only if the subsequences x̃ and ỹ, obtained
by deleting the zeros in x and y respectively, are identical.
Furthermore, sequences x, y with x̃ = ỹ, are confusable in
the ShC(P ; K) if and only if x and y are confusable in the
ShC(1; K). This implies that the code CP ;K (n), as defined
in (2), is zero-error. It also implies that CP ;K (n) is optimal
because a zero-error code for the ShC(P ; K) can have at most
M1;K (n, W ) codewords x having the same subsequence x̃ of
Hamming weightP
W , and so MP ;K (n, W ) ≤ P W M1;K (n, W )
n
and MP ;K (n) ≤ W =0 P W M1;K (n, W ) = |CP ;K (n)|.

Ͳǡ͹ሻ ሺͳǡ͹
ʹǡ͹ሻ ሺ͵ǡ͹
Ͷǡ͹ሻ ሺͷǡ͹ሻ
ሺͷǡ͹ ሺ͸ǡ͹ሻ
͸ǡ͹ሻ ሺ͹ǡ͹ሻ
ሺ͹ǡ͹
ሺͲǡ͹ሻ
ሺͳǡ͹ሻ ሺʹǡ͹ሻ
ሺ͵ǡ͹ሻ ሺͶǡ͹ሻ
B. Optimal Codes and the Capacity
As demonstrated above, one can focus first on the special
case of ShC(1; K) and obtain the results for the general case
by using Lemma 1 and Proposition 2. Optimal codes for this
channel have in fact been determined in [12], but we shall
rederive here this result and give an alternative proof of optimality by focusing on the constant-weight case. This approach
will lead to an even simpler—geometric—characterization of
optimal codes, and will enable a unified treatment of many
related problems, such as the DTQP channel, the continuoustime models, the error-detection problem, etc.
Let us describe the set of constant-weight inputs to the
ShC(1; K) in a way appropriate for our purpose. Binary
sequences of length n and weight W can be uniquely
represented as W -tuples of positive integers (s1 , . . . , sW ),
where si is the position of the i’th 1-bit in the sequence;
for example, 010001 ↔ (2, 6). The set of all such sequences is therefore
in a one-to-one correspondence with

the simplex (s1 , . . . , sW ) ∈ ZW : 1 ≤ s1 < · · · <
sW ≤ n . For notational convenience, we shall subtract
the vector (1, . . . , W ) from all vectors in this
 set to obtain
another equivalent representation, ∆W
=
(s1 , . . . , sW ) ∈
n−W
ZW : 0 ≤ s1 ≤ · · · ≤ sW ≤ n − W . According
to our channel model, the set of outputs {z : x
z}
is in this representation the hypercube of sidelength K
with
x at its corner (restricted to the simplex), namely

(z1 , . . . , zW ) ∈ ZW : 0 ≤ z1 ≤ · · · ≤ zW ≤ n − W + K,
0 ≤ zi − xi ≤ K (the 1-bits of the transmitted binary
sequence x are shifted to the right for ≤ K positions in the
channel). Figure 1 depicts the just described representation of
the set of binary sequences of length n = 9 and weight W = 2,
as well as the effect of the ShC(1; 1) on these sequences. We
generally do not distinguish between binary sequences and
their integer representations; it will be clear from the context
which description is used.
Theorem 3. The code
n
o
C1;K (n, W ) = x ∈ ∆W
:
x
=
0
(mod
K
+
1)
n−W

(3)

is an optimal zero-error code of length n and weight W for
the ShC(1; K).
Proof: The sets of outputs {z : x
z} and {z : y
z}
(hypercubes of sidelength K) are disjoint for every two distinct
codewords x, y ∈ C1;K (n, W ) because, by construction, the
coordinate-wise differences xi − yi are integral multiples
of K + 1. This proves that the code C1;K (n, W ) is zeroerror. Observe also that C1;K (n, W ) is “perfect”, in the sense
that the sets of outputs {z : x
z}, x ∈ C1;K (n, W ),
cover the entire space ∆W
.
Indeed,
for an arbitrary point
n−W
z = (z1 , . . . , zW ) ∈ ∆W
,
consider
the
point x defined by
n−W
zi
⌋(K + 1); then x ∈ C1;K (n, W ) and x
z. It
xi = ⌊ K+1
follows from the result of Shannon [18, Thm 3] that such
a perfect code for the ShC(1; K) is necessarily optimal. (In
the terminology of [18], the mapping {z : x
z} 7→ x,
x ∈ C1;K (n, W ), is an “adjacency reducing mapping”.)

ሺͲǡ͹ሻ ሺͳǡ͹ሻ ሺ
4

ሺͲǡͲሻ

ሺͲǡͳሻ ሺͳǡͳሻ

ሺͲǡʹሻ ሺͳǡʹሻ ሺʹǡʹሻ

ሺͲǡ͵ሻ ሺͳǡ͵ሻ ሺʹǡ͵ሻ ሺ͵ǡ͵ሻ

ሺͲǡͶሻ ሺͳǡͶሻ ሺʹǡͶሻ ሺ͵ǡͶሻ ሺͶǡͶሻ

ሺͲǡͷሻ ሺͳǡͷሻ ሺʹǡͷሻ ሺ͵ǡͷሻ ሺͶǡͷሻ ሺͷǡͷሻ

ሺͲǡ͸ሻ ሺͳǡ͸ሻ ሺʹǡ͸ሻ ሺ͵ǡ͸ሻ ሺͶǡ͸ሻ ሺͷǡ͸ሻ ሺ͸ǡ͸ሻ

ሺͲǡ͹ሻ ሺͳǡ͹ሻ ሺʹǡ͹ሻ ሺ͵ǡ͹ሻ ሺͶǡ͹ሻ ሺͷǡ͹ሻ ሺ͸ǡ͹ሻ ሺ͹ǡ͹ሻ
Fig. 1. The simplex ∆27 representing the set of binary sequences of length
n = 9 and weight W = 2; the point (i, j) represents the binary sequence
having 1’s on the (i + 1)’th and (j + 2)’th position. Black dots denote
the codewords of the code C1;1 (9, 2)—an optimal zero-error code for the
ShC(1; 1). Dashed lines illustrate sets of sequences that a given codeword
can produce at the output of this channel.

Hence, the cardinality of optimal constant-weight codes for
this channel is M1;K (n, W ) = |C1;K (n, W )|. To determine this
quantity explicitly, write C1;K (n,
form as
 W ) in a different
W
W
C1;K (n,
W
)
=
(K
+
1)
·
∆
=
(K
+
1)
·
s
:
s
∈
∆
, where
d
d


d = n−W
K+1 . It follows that



W + n−W
W
K+1
M1;K (n, W ) = ∆d =
(4)
W
and, by Proposition 2, we have for arbitrary P



W + n−W
K+1
.
(5)
MP ;K (n, W ) = P W
W

Theorem 4. The zero-error capacity of the ShC(P ; K) equals
R∗P ;K = log r, where r is the unique positive real root of the
polynomial xK+1 − P xK − 1.

Proof: The required capacity is equal to the limit of the
rates of optimal codes, so we only need to determine the
asymptotic behavior of MP ;K (n). In order to do this we write
MP ;K (n) in a recurrent form:
MP ;K (n) = P · MP ;K (n − 1) + MP ;K (n − K − 1),

(6)

n

with MP ;K (n) = 1 + P + · · · + P for 0 ≤ n ≤ K, which is
easily verified from (1) and (5). Since MP ;K (n) is the solution
of the linear recurrence (6), it can be expressed in terms of the
roots of its characteristic polynomial
p(x) = xK+1 − P xK − 1
PK
n
[22]. Namely, MP ;K (n) =
k=0 ak rk , where rk ’s are the
roots of p(x) and ak ’s are complex constants determined by
the initial conditions1 . It is known [21], [22, Ch. 3, Thm 2]
P
n
speaking, the expression MP ;K (n) = K
k=0 ak rk is valid only if
all the roots are different, so let us verify that they are. Observe that the unique
positive root satisfies r > P because r K = (r − P )−1 . Now, if some rj had
multiplicity two we would have p(x) = (x − rj )2 q(x) and, by calculating
the derivatives of both sides, (K + 1)xK − P KxK−1 = (x − rj )s(x). This
would imply rj = P K/(K + 1) < P , a contradiction.
1 Strictly

5

that polynomials of this form (leading coefficient positive,
remaining coefficients negative) have a unique positive real
root r0 = r and that the remaining roots cannot exceed r
in modulus, |rk | ≤ r (in fact, it is easy to show that this
inequality is strict in the case of p(x)). This implies that
limn→∞ n1 log MP ;K (n) = log r, as claimed.
Finite-Length Performance: It follows from the above proof
M
(n)
that MP ;K (n) ∼ arn (meaning that limn→∞ Par;Kn
= 1),
where the constant a is determined by the initial conditions of
(6). We therefore have a finer asymptotic expansion
log MP ;K (n) = n · R∗P ;K + log a + o(1)

(7)

which indicates not only the limit of the rates of optimal codes
(the capacity), but also the speed of convergence to the limit.
By using Stirling’s approximation, we can also find from (5)
the asymptotics of MP ;K (n, W ) when n → ∞ and W ∼ wn,
w ∈ (0, 1):
1
log MP ;K (n, wn)
n


w(K + 1)
wK + 1
+ w log P,
H
=
K+1
wK + 1

RP ;K (w) , lim

n→∞

(8)

where H(·) is the binary entropy function. This quantity can
be interpreted as the “constant-weight zero-error capacity”
of the ShC(P ; K)—the largest rate attainable asymptotically
with the requirement that the fraction of the cells containing
a particle is (approximately) w. Since there are linearly many
weights, the zero-error capacity is achievable with constantweight codes, and so another way to characterize it is
R∗P ;K = sup RP ;K (w)
0≤w≤1

 ∗
w (K + 1)
w∗ K + 1
+ w∗ log P,
H
=
K +1
w∗ K + 1

(9)

where w∗ is the maximizer of RP ;K (w). From Stirling’s
approximation we can in fact get more information about the
asymptotics of the rates of optimal constant-weight codes:
1
log n + O(1).
(10)
2
The expressions (7) and (10) are akin to the fundamental
bounds on the finite-length performance of optimal codes
with non-vanishing error probabilities studied in Shannon
theory [19]. Comparing them we see that, even though the
capacity can be achieved with constant-weight codes, their
finite-length performance is worse than that of general codes.
This is quantified by the “second-order” term − 21 log n, which
represents the penalty paid for using constant-weight codes.
Some properties of the capacity and related quantities
mentioned in this subsection, and their behavior as functions
of the channel parameters, are stated in the Appendix.
log MP ;K (n, w∗ n) = n · R∗P ;K −

C. Additional Noise
In many realistic scenarios the “particles”, apart from being
shifted, suffer from other impairments as well. For example, a
packet passing through a queuing system may also be received
erroneously or may be erased (meaning that the symbol ‘E’
is received instead), see [3, Sec. IV]. Suppose that these

additional impairments are modeled by a discrete memoryless
channel with input alphabet {1, . . . , P }, with output alphabet
not containing2 the symbol 0, and with zero-error capacity
equal to C0 (this channel acts on the particles independently
of their shifts; in other words, it acts on the subsequence x̃
of the transmitted sequence x). We refer to the compound
channel as the Noisy Shift Channel with parameters P, K, C0 ,
or NShC(P ; K; C0 ) for short.
Theorem 5. The zero-error capacity of the Noisy Shift Channel NShC(P ; K; C0 ) equals log r, where r is the unique
positive solution to xK+1 − 2C0 xK − 1 = 0.
Proof: We only give a brief outline of the proof. A
statement analogous to Proposition 2 holds in this case too:
if C1;K (n, W ) is an optimal zero-error code of length n and
weight W for the ShC(1; K), and C N (W ) an optimal zeroerror code of length W for the discrete memoryless channel
acting on the particles, then
o
n
x ∈ {0, 1, . . . P }n : x̃ ∈ C N (W ), x ∈ C1;K (n, W ) (11)
is an optimal zero-error code of length n and Hamming
weight W for the NShC(P ; K; C0 ). Its cardinality is |C N (W )|·
|C1;K (n, W )|, and since |C N (W )| = 2C0 W +o(n) when n → ∞,
W ∼ wn, further analysis is the same as in the proof of
Theorem 4 with P replaced by 2C0 (see (5)).
III. Z ERO - ERROR

CAPACITY OF

FIFO

QUEUES

We now turn to the analysis of the DTQP(P ; K; ϕ), a
channel introduced as an abstraction of a single-server queue
with an infinite buffer. The proofs rely on the methods used
in the previous section for the shift channel.
A. Optimal Codes and the Capacity of the DTQP
As for the shift channel, it is enough to solve the constantweight case with P = 1. Also, the set of inputsof length n can
again be identified with the simplex ∆W
n−W = (s1 , . . . , sW ) ∈
ZW : 0 ≤ s1 ≤ · · · ≤ sW ≤ n − W . Before stating the main
result of this section, we describe the construction of optimal
codes on a simple example.
Example 2. Consider the DTQP(1; 2; ϕ), and let n = 10 and
W = 2. The set of binary sequences of length 10 and weight
2 is represented as the simplex ∆28 in Figure 2. We construct
a code by using a procedure analogous to the one used for
the shift channel in [12, Sec. II.B]: List the allowed inputs in
the reverse lexicographic order, and in each step select as a
codeword the first sequence available on the list that does not
conflict with previously chosen codewords, i.e., that cannot
produce the same output as one of them. The resulting code
is depicted in Figure 2(a). Now observe that we can replace
the codewords lying on the right edge of the simplex with
other codewords—(0, 0) with (0, 2), (3, 3) with (3, 5), and
(6, 6) with (6, 8)—without affecting the size of the code and
2 The symbol 0 has a meaning in the shift channel—it represents an empty
cell. Therefore, if a symbol p ∈ {1, . . . , P } could produce a 0, this would
correspond to a deletion of a particle being possible in the compound channel,
in which case our analysis would not apply.

ሺͲǡͲሻ

its zero-error property. Note that the points near the right edge
represent the sequences whose 1’s are too close so that they
can “push” each other (think of packets sent in slots not too
far apart, so that processing one of them may cause the others
to wait in the queue and be further delayed). The result of
this replacement of codewords is the same as if we had first
forbidden the input sequences with 1’s too close to each other,
and then constructed a code in the same way as for the shift
channel; this is illustrated in Figure 2(b). Namely, the effect
of the DTQP(1; K; ϕ) on the inputs with 1’s separated by at
least K zeros is the same as the effect of the ShC(1; K) on
those inputs—each 1 is shifted for ≤ K positions to the right.
Finally, notice that expelling the sequences with 1’s separated
by < K zeros leaves the shape of the space unchanged—it is
still a simplex of the same dimension, only smaller.
N
Theorem
6. The
zero-error
capacity oof
the
n
log(P +1)
log P
DTQP(P ; K; ϕ) equals max
K+1 , Eϕ [κ]+1 , where
PK
Eϕ [κ] = k=0 kϕ(k).

Proof: Let MPQ;K (n, W ) denote the size of an optimal zero-error code of length n and weight W for the
DTQP(P ; K; ϕ) (‘Q’ in the superscript stands for ‘Queue’).
The code construction described in the previous example can
be used in general: 1) Start with ∆W
n−W , 2) keep only the
sequences for which each of the first W − 1 1’s is followed
by at least K zeros (at least one such sequence exists if and
only if n − W − (W − 1)K ≥ 0), 3) in the remaining simplex
construct a code in the same way as for the ShC(1; K). We
shall skip the somewhat tedious argument, but it can be shown
that this construction produces an optimal zero-error code
when3 n ≥ W (K + 1) − K and n ≡ 1 (mod K + 1), e.g.,
via the adjacency reducing mapping theorem [18, Thm 3].
Therefore, for n ≥ W (K + 1) − K, n ≡
1 (mod K + 1),
we
 n−W
−(W −1)K 
Q
,
where
d
=
have M1;K
(n, W ) = ∆W
,
and
d
K+1
so

 n+K 

(K+1) 
W + n+K−W
Q
K+1
= K+1 . (12)
M1;K (n, W ) =
W
W
Q
For general P , MPQ;K (n, W ) = P W ·M1;K
(n, W ). The average
length of the output sequences is in this case Lav (n) ≤ n + K
because consecutive packets are separated by at least K empty
slots by construction and cannot affect each other’s total delay.
1
From this we get, for 0 ≤ w < K+1
,

RPQ ;K (w) , lim

n→∞

1
log MPQ;K (n, wn)
Lav (n)

1
H (w(K + 1)) + w log P.
=
K +1

6

ሺͲǡͳሻ ሺͳǡͳሻ
ሺͲǡͲሻ

ሺͲǡʹሻ ሺͳǡʹሻ ሺʹǡʹሻ
ሺͲǡͳሻ ሺͳǡͳሻ

ሺͲǡ͵ሻ ሺͳǡ͵ሻ ሺʹǡ͵ሻ ሺ͵ǡ͵ሻ
ሺͲǡʹሻ ሺͳǡʹሻ ሺʹǡʹሻ

ሺͲǡͶሻ ሺͳǡͶሻ ሺʹǡͶሻ ሺ͵ǡͶሻ ሺͶǡͶሻ
ሺͲǡ͵ሻ ሺͳǡ͵ሻ ሺʹǡ͵ሻ ሺ͵ǡ͵ሻ

ሺͲǡͷሻ ሺͳǡͷሻ ሺʹǡͷሻ ሺ͵ǡͷሻ ሺͶǡͷሻ ሺͷǡͷሻ
ሺͲǡͶሻ ሺͳǡͶሻ ሺʹǡͶሻ ሺ͵ǡͶሻ ሺͶǡͶሻ

ሺͲǡ͸ሻ ሺͳǡ͸ሻ ሺʹǡ͸ሻ ሺ͵ǡ͸ሻ ሺͶǡ͸ሻ ሺͷǡ͸ሻ ሺ͸ǡ͸ሻ
ሺͲǡͷሻ ሺͳǡͷሻ ሺʹǡͷሻ ሺ͵ǡͷሻ ሺͶǡͷሻ ሺͷǡͷሻ

ሺͲǡ͹ሻ ሺͳǡ͹ሻ ሺʹǡ͹ሻ ሺ͵ǡ͹ሻ ሺͶǡ͹ሻ ሺͷǡ͹ሻ ሺ͸ǡ͹ሻ ሺ͹ǡ͹ሻ
ሺͲǡ͸ሻ ሺͳǡ͸ሻ ሺʹǡ͸ሻ ሺ͵ǡ͸ሻ ሺͶǡ͸ሻ ሺͷǡ͸ሻ ሺ͸ǡ͸ሻ

ሺͲǡͺሻ ሺͳǡͺሻ ሺʹǡͺሻ ሺ͵ǡͺሻ ሺͶǡͺሻ ሺͷǡͺሻ ሺ͸ǡͺሻ ሺ͹ǡͺሻ ሺͺǡͺሻ
ሺͲǡ͹ሻ ሺͳǡ͹ሻ ሺʹǡ͹ሻ ሺ͵ǡ͹ሻ ሺͶǡ͹ሻ ሺͷǡ͹ሻ ሺ͸ǡ͹ሻ ሺ͹ǡ͹ሻ
ሺͲǡͺሻ ሺͳǡͺሻ ሺʹǡͺሻ ሺ͵ǡͺሻ ሺͶǡͺሻ ሺͷǡͺሻ ሺ͸ǡͺሻ ሺ͹ǡͺሻ ሺͺǡͺሻ

(a) Optimal code obtained by a greedy construction applied on binary
sequences listed in the reverse lexicographic order.

ሺͲǡͲሻ

ሺͲǡͳሻ ሺͳǡͳሻ
ሺͲǡͲሻ

ሺͲǡʹሻ ሺͳǡʹሻ ሺʹǡʹሻ
ሺͲǡͳሻ ሺͳǡͳሻ

ሺͲǡ͵ሻ ሺͳǡ͵ሻ ሺʹǡ͵ሻ ሺ͵ǡ͵ሻ
ሺͲǡʹሻ ሺͳǡʹሻ ሺʹǡʹሻ

ሺͲǡͶሻ ሺͳǡͶሻ ሺʹǡͶሻ ሺ͵ǡͶሻ ሺͶǡͶሻ
ሺͲǡ͵ሻ ሺͳǡ͵ሻ ሺʹǡ͵ሻ ሺ͵ǡ͵ሻ

ሺͲǡͷሻ ሺͳǡͷሻ ሺʹǡͷሻ ሺ͵ǡͷሻ ሺͶǡͷሻ ሺͷǡͷሻ
ሺͲǡͶሻ ሺͳǡͶሻ ሺʹǡͶሻ ሺ͵ǡͶሻ ሺͶǡͶሻ

ሺͲǡ͸ሻ ሺͳǡ͸ሻ ሺʹǡ͸ሻ ሺ͵ǡ͸ሻ ሺͶǡ͸ሻ ሺͷǡ͸ሻ ሺ͸ǡ͸ሻ
ሺͲǡͷሻ ሺͳǡͷሻ ሺʹǡͷሻ ሺ͵ǡͷሻ ሺͶǡͷሻ ሺͷǡͷሻ

ሺͲǡ͹ሻ ሺͳǡ͹ሻ ሺʹǡ͹ሻ ሺ͵ǡ͹ሻ ሺͶǡ͹ሻ ሺͷǡ͹ሻ ሺ͸ǡ͹ሻ ሺ͹ǡ͹ሻ
ሺͲǡ͸ሻ ሺͳǡ͸ሻ ሺʹǡ͸ሻ ሺ͵ǡ͸ሻ ሺͶǡ͸ሻ ሺͷǡ͸ሻ ሺ͸ǡ͸ሻ

ሺͲǡͺሻ ሺͳǡͺሻ ሺʹǡͺሻ ሺ͵ǡͺሻ ሺͶǡͺሻ ሺͷǡͺሻ ሺ͸ǡͺሻ ሺ͹ǡͺሻ ሺͺǡͺሻ
ሺͲǡ͹ሻ ሺͳǡ͹ሻ ሺʹǡ͹ሻ ሺ͵ǡ͹ሻ ሺͶǡ͹ሻ ሺͷǡ͹ሻ ሺ͸ǡ͹ሻ ሺ͹ǡ͹ሻ

(b) Optimal code obtained by the same construction as for the
ሺͳǡͺሻ
ሺ͵ǡͺሻ
ሺͶǡͺሻ ሺͷǡͺሻ
ሺͲǡͺሻ 2),
ሺ͸ǡͺሻ
ሺͺǡͺሻ
ሺ͹ǡͺሻ
ShC(1;
after ሺʹǡͺሻ
excluding
the sequences
with 1’s
less than
2 positions
apart (represented by dots in the grey region).
Fig. 2. Zero-error codes of length n = 10 and weight W = 2 for
the DTQP(1; 2; ϕ). Dashed lines illustrate sets of sequences that a given
codeword can produce at the output of the DTQP(1; 2; ϕ).

(13)

(For the purpose of determining RPQ ;K (w), it is not a loss
of generality to restrict to lengths n ≡ 1 (mod K + 1)
because one can use zero-padding to satisfy this condition,
3 The greedy construction in the reverse lexicographic order is always
optimal, but it does not necessarily give the same number of codewords as
the construction given by steps 1)–3). Namely, we have to make sure that
the points with which we are replacing the codewords at the edge of the
simplex are themselves in the given simplex, see Figure 2; this is why the
stated conditions on n are needed.

without affecting the asymptotic rate of codes and their zero1
error property.) Now consider the case w ≥ K+1
. For such
weights, the construction in the reverse lexicographic order
produces at most a polynomial (in n) number of codewords,
Q
e.g., for n = W (K + 1) + 1 we have M1;K
(n, W ) = W + 1.
The asymptotic rate will not be reduced if we keep only a
single codeword which minimizes the expected output length,
and that is 0W (W packets sent in the first W slots). This
will produce P W codewords for general P , with the expected

7

output length of Lav (n) = max{n, W (Eϕ [κ] + 1)} (see
1
Example 1 in Section I-C). Therefore, for K+1
≤ w ≤ 1,
RPQ ;K (w) =

w log P
.
max{1, w(Eϕ [κ] + 1)}

(14)

Finally, maximizing RPQ ;K (w) over all w (see (13) and (14))
gives the expression for the zero-error capacity.
The capacity-achieving strategy is very simple: If the capacity equals log(P + 1)/(K + 1) it can be achieved by inserting
K zeros/empty slots after every symbol of the information
sequence written in the alphabet {0, 1, . . . , P }, and if it equals
log P/(Eϕ [κ]+1) the capacity-achieving code is {1, . . . , P }n .
B. Additional Noise

7.

The

Unlike in the error-correction case, the channels
ShC(P ; K1 , K2 ) and ShC(P ; K2 − K1 ) are not equivalent
from the point of view of error-detection, i.e., the analog
of Lemma 1 does not hold here. As an example, consider
the code {10000, 00100} which is zero-error-detecting in
the ShC(1; −1, 1), but is not zero-error-detecting in the
ShC(1; 0, 2), because in the latter case 10000
00100.
However, the analog of Proposition 2 holds and enables one
to focus on the case P = 1.
The following claim describes a relation between zero-errordetecting and zero-error-correcting codes for the shift channel.
Proposition 8. Let K1 ≤ 0 ≤ K2 .

Suppose that the packets, apart from being delayed in the
queue, experience other types of impairments as well. Suppose
further that these additional impairments are modeled as a
discrete memoryless channel with input alphabet {1, . . . , P },
with output alphabet not containing the symbol 0, and with
the zero-error capacity equal to C0 (this channel acts on the
packets independently of their passing through the queue, i.e.,
it acts on the subsequence x̃ of the transmitted sequence x).
We refer to the compound channel as the Noisy DTQP with
parameters P, K, C0 , or NDTQP(P ; K; C0 ) for short.
Theorem

A. The Shift Channel

zero-error
n log

NDTQP(P ; K; C0 ) equals max

capacity
ofo the
(2C0 +1)
C0
,
K+1
Eϕ [κ]+1 .

Proof: The proof is analogous to that of Theorem 5—the
key is to focus on the constant-weight case and to observe that
the “effective size” of the alphabet of the discrete memoryless
channel acting on the packets is 2C0 . The result is then
obtained by replacing P with 2C0 in Theorem 6.
IV. Z ERO - ERROR

DETECTION

In some situations, it is required of the receiver only to detect that a specific kind of error has happened, not necessarily
to correct it. A code D(n) is said to be zero-error-detecting
for a given channel if it ensures that all possible errors allowed
in the model can be detected, meaning that the receiver can
conclude with probability one whether the transmission was
error-free or not. We shall assume that every input sequence x
can produce itself at the channel output, i.e., x
x, because
otherwise the detection is trivial (for the ShC(P ; K1 , K2 ) this
amounts to assuming K1 ≤ 0 ≤ K2 ). If this is the case, then
an equivalent way of stating the zero-error-detection property
of a code D(n) is that no codeword x ∈ D(n) can produce
another codeword y 6= x at the channel output. This condition
is less stringent compared to the definition of zero-error code
(which will be called zero-error-correcting in this section, to
avoid confusion): two codewords are now allowed to produce
the same output z, but as long as z itself is not a codeword, the
receiver will recognize that an error has occurred. The zeroerror-detection capacity [7], [2] of a channel is the lim sup
of the rates of optimal zero-error-detecting codes of length
n → ∞ for that channel.

(a) Every
zero-error-detecting
code
for
ShC(P ; K1 , K2 ) is a zero-error-correcting
for the ShC(P ; min{|K1 |, K2 }).

the
code

(b) Every
zero-error-correcting
code
for
the
ShC(P ; max{|K1 |, K2 }) is a zero-error-detecting
code for the ShC(P ; K1 , K2 ).
In particular, a code is zero-error-detecting for the
ShC(P ; −K, K) if and only if it is zero-error-correcting for
the ShC(P ; K).
Proof: Assume w.l.o.g. that |K1 | ≥ K2 , and recall the
geometric representation of the code space as described in Section II-B (constant-weight case, P = 1). Let x = (x1 , . . . , xW )
be a codeword. That a code is zero-error-detecting for the
ShC(1; K1 , K2 ) means that every hypercube of the form
{z : K1 ≤ zi − xi ≤ K2 } is such that it does not contain
a codeword other than x. This, together with the assumption
|K1 | ≥ K2 , implies that the hypercubes {z : 0 ≤ zi − xi ≤
K2 }, formed in this way for every codeword x, are pairwise
disjoint, meaning that the code is zero-error-correcting for the
ShC(1; K2 ). The statement (b) is deduced in a similar way
from the geometric interpretation of the involved notions.
Consequently, the zero-error-detection capacity of the
ShC(P ; K1 , K2 ) is lower bounded by the zero-errorcorrection capacity of the ShC(P ; max{|K1 |, K2 }) and upper bounded by the zero-error-correction capacity of the
ShC(P ; min{|K1 |, K2 }). We next prove that this upper bound
can always be achieved.
Theorem 9. Let K1 ≤ 0 ≤ K2 . The zero-error-detection capacity of the ShC(P ; K1 , K2 ) is equal to log s, where s is the
unique positive real root of the polynomial xmin{|K1 |,K2 }+1 −
P xmin{|K1 |,K2 } − 1.
Proof: Again, assume that |K1 | ≥ K2 . As remarked
above, Proposition 8(a) implies that the zero-error-detection
capacity of the ShC(P ; K1 , K2 ) is upper bounded by the
zero-error-correction capacity of the ShC(P ; K2 ), which is
precisely log s by Theorem 4. To prove the claim we need to
demonstrate that the rate log s is achievable, and this is done
by exhibiting a family of codes with the desired properties.

8

Define
(a)

D 1;K2 (n, W ) =
(

x ∈ ∆W
n−W : x = 0 (mod K2 + 1),

W
X

(15)
)

xi = a ,

i=1

where 0 ≤ a ≤ W (n−W ) (recall that 0 ≤ xi ≤ n−W ). Note
(a)
that D1;K2 (n, W ) is a subcode of the code C1;K2 (n,
PW ) from
(3), obtained as its intersection with the hyperplane i xi = a.
We have
W (n−W )

C1;K2 (n, W ) =

[

(a)

D1;K2 (n, W ),

(16)

a=0

and so, for every n and W , there is at least one a for which
it holds that
|C1;K2 (n, W )|
(a)
D1;K2 (n, W ) ≥
.
(17)
W (n − W ) + 1
(a)

Therefore, for a’s chosen in this way, the codes D1;K2 (n, W )
have asymptotically the same rate as the codes C1;K2 (n, W ),
which is log s for W ∼ w∗ n.
(a)
It is left to verify that the codes D1;K2 (n, W ) are indeed
zero-error-detecting for the ShC(1; K1 , K2 ). Suppose that a
(a)
codeword x ∈ D1;K2 (n, W ) was transmitted
P and a sequence z
a, the receiver
received at the output of the channel. If i zi 6= P
will easily recognize an error, so suppose that i zi = a. In
this case, if any shifts have occurred in the channel, some of
them must have been shifts to the right and some
shifts
P of themP
to the left for otherwise we could not have i xi 6= i zi .
Suppose that the j’th particle was shifted to the right, zj > xj .
Then, since xj = 0 (mod K2 +1) and zj −xj ≤ K2 , we have
zj 6= 0 (mod K2 + 1), so z cannot be a codeword. Therefore,
the receiver can detect all errors allowed in the model.
Notice that the zero-error-detection capacity of the
ShC(P ; K) equals log(P + 1) for every K, as if there were
no shifts at all.
B. FIFO Queues
In the DTQP model only shifts to the right are possible,
which makes the detection problem very easy (see also the
last remark in the previous subsection).
Theorem 10. The zero-error-detection capacity of the
DTQP(P ; K; ϕ) is equal to log(P + 1).
Proof: The value log(P + 1) is clearly an upper bound
on the capacity because P + 1 is the cardinality of the input
alphabet, so it is left to prove achievability. The codes
)
(
W
X
xi = a
(18)
D(a) (n, W ) = x ∈ ∆W
n−W :
i=1

are zero-error-detecting for the DTQP(1; K; ϕ). Their cardinality, for appropriately chosen a, satisfies
D(a) (n, W ) ≥

|∆W
n−W |
.
W (n − W ) + 1

(19)

Multiplying the above expression by P W , taking the logarithm, normalizing by n, and letting n → ∞, W ∼ wn, we

get a lower bound on the asymptotic rate of optimal constantweight zero-error-detecting codes for the DTQP(P ; K; ϕ) in
the form H(w) + w log P . The maximum of this function over
w ∈ [0, 1] is precisely log(P + 1).
An important point to emphasize here is that the rate was
computed by normalizing by n, and not by Lav (n) as in
the error-correction case. The reason is the following: since
we are using constant-weight codes, and since we are only
trying to detect the shifts, the receiver can stop looking at the
output after the n’th slot because if some of the packets have
been delayed for more that, it can detect this by counting the
received packets in the first n slots. The actual rate of the
code D(a) (n, W ) in the error-detection context is therefore
1
(a)
(n, W )|.
n log |D
V. C ONTINUOUS - TIME

MODELS

In this section we introduce and analyze the continuous-time
versions of the shift and queuing channels studied up to this
point. The reasoning is analogous to the discrete-time case so
we give only a brief outline.
Throughout the section we shall assume that the probability
distribution of particle/packet delays is absolutely continuous
with respect to the Lebesgue measure. This assumption, in
particular, ensures the existence of an optimal decoding rule,
i.e., decoding rule that minimizes the error probability. A
code will be called zero-error if its error probability (under
an optimal decoding rule) is equal to zero.
Remark 4 (Zero-error codes). Recall (Section I-C) that, in
the discrete-time case, a code is said to be zero-error if either
of the following two equivalent conditions holds: (c1) the
error probability under optimal decoding is equal to zero,
and (c2) no two codewords can produce the same output.
These two requirements are in general not equivalent in the
continuous-time case—the error probability for a given code
can be zero even if two different codewords can produce the
same output, because there are uncountably many possible
outputs. However, it should be noted that both of these
definitions result in the same value of the zero-error capacity.
The reason we have adopted (c1) as the definition of zero-error
codes in this section is that this convention slightly simplifies
the proofs.
N
A. Continuous-Time Shift Channels
We describe the continuous-time version of the shift channel
in the context of queuing systems. Suppose that the transmitter
can send packets from a P -ary alphabet at arbitrary instants
of time, but with the restriction that any two emissions are
separated by at least τ > 0 seconds (think of τ as the time
needed to physically transmit a single packet). Suppose that
W packets were transmitted in a given interval T (the code
“length” is now a continuous parameter T ∈ R+ ). Every such
input of duration T and weight W is uniquely specified (for
P = 1) by the sequence of emission times (s1 , . . . , sW ) ∈
RW , 0 ≤ s1 ≤ s2 − τ ≤ s3 − 2τ ≤ · · · ≤ sW − (W − 1)τ ≤
T − W τ . Therefore, the set of all inputs of duration T and
weight W is in a one-to-one correspondence with the simplex

9


(s1 , . . . , sW ) ∈ RW : 0 ≤ s1 ≤ · · · ≤ sW ≤ T /τ − W (for
convenience, we have scaled the emission times with τ and
subtracted the vector (0, 1, . . . , W − 1) from them; this is how
the latter representation was obtained).
We further assume that the i’th packet is delayed in the
channel for a random amount of time ti,res ∈ [0, Tres ], but
that reordering of packets is not possible. The probability
distribution of ti,res is assumed to be absolutely continuous
with respect to the Lebesgue measure, with the corresponding
density strictly positive on [0, Tres]. In other words, the packets
are processed in a FIFO manner and the total time that any
packet spends in the system—the so-called residence time—
is bounded by Tres . Using the above notation, the set of
outputs {z : x
z} can be represented as the hypercube
of sidelength Tres /τ
 with x at its corner (restricted to the
simplex), namely (z1 , . . . , zW ) ∈ RW : 0 ≤ z1 ≤ · · · ≤
zW ≤ T /τ − W + Tres /τ, 0 ≤ zi − xi ≤ Tres /τ . We refer
to the channel just described as the P -ary Continuous-Time
Shift Channel, CTShC(P ; τ ; Tres ).
Theorem
11. The
zero-error
capacity
of
the
CTShC(P ; τ ; Tres ) equals τ1 log v, where v is the unique
positive solution to xmax{Tres /τ,1} −P xmax{Tres /τ,1}−1 −1 = 0.
Proof: As in the discrete case, codewords can be chosen
so that the hypercubes {z : x
z} pack the simplex perfectly,
implying that the resulting code is optimal, see Theorem 3.
(In the continuous case we allow the decoding regions to
overlap, but their intersection is required to have measure
zero, see Remark 4; in other words, the hypercubes can touch
along their faces only.) If Tres ≥ τ , the cardinality of the
−W 
⌋
W +⌊ TT/τ
res /τ
.
resulting code will be, similarly to (5), P W
W
The constant-weight zero-error capacity is the limit of the rate
of these codes as T → ∞ and W ∼ wT /τ . The zero-error
capacity is then obtained by maximizing over w ∈ [0, 1] and
can be characterized as τ1 log v, where v is the unique positive
solution of xTres /τ − P xTres /τ −1 − 1 = 0. If Tres < τ , the
capacity is trivially τ1 log(P + 1).
B. Continuous-Time FIFO Queues
Consider now the continuous-time analog of the DTQP.
As for the CTShC, we assume that the transmitter is sending
packets from a P -ary alphabet at arbitrary instants of time,
with the restriction that any two emissions are separated by at
least τ > 0 seconds. Further, we assume that the processing
time of each packet is a random variable with distribution
absolutely continuous with respect to the Lebesgue measure,
and with the corresponding density ϕ(t) strictly positive on the
interval [0, Tproc ]. The service procedure is FIFO. We refer to
this model as the P -ary Continuous-Time Queue with bounded
Processing Time, or CTQP(P ; τ ; Tproc ; ϕ) for short.
In a way analogous to the proofs of Theorems 6 and 11 we
deduce the following result.
Theorem
12. The
zero-error
capacity
of
the
o
n
log(P +1)
log P
CTQP(P ; τ ; Tproc ; ϕ) is max max{Tproc ,τ } , max{Eϕ [κ],τ } ,
RT
where Eϕ [κ] = 0 proc tϕ(t)dt.

Notice that the capacity of the CTQP(P ; τ ; Tproc ; ϕ) is
independent of τ when this parameter is small. This is an
important difference compared to the continuous-time shift
channel discussed in the previous subsection. For example,
when the emission time τ → 0, the zero-error capacity of the
CTShC(P ; τ ; Tres ) grows to infinity. This is expected because
τ → 0 means that we can send an unbounded number of
packets in any given interval of time, while the delay of each
of them is bounded by a constant Tres . In the CTQP, however,
sending more packets also means that the time needed to
receive them will be much longer on average, and the rate
in fact remains unchanged.
VI. C ONCLUDING

REMARKS

Channels with symbol shifts as the dominant type of noise
are well-motivated communication models. In the present paper two classes of such channels were studied, both in discrete
and continuous time, and a characterization of their zero-error
capacity and zero-error-detection capacity was obtained. To
conclude the paper, we mention two possible extensions of
these models as directions for further work; we believe that
these extensions are natural and important in the context of
the mentioned applications.
One of the extensions refers to models that include deletions
of particles/packets. One can imagine a queuing system with
a finite buffer which drops an incoming packet whenever the
buffer is full, or a molecular communication system in which
some of the particles never arrive at the receiving side. Another
extension are models in which reordering of particles/packets
is allowed (see, e.g., [1], [9], [14]). For example, due to
properties of most molecular communication systems, it is
reasonable to assume that the order in which the particles
arrive at the receiving side is not necessarily the same as
the one in which they were transmitted. If the particles are
identical, then this reordering has no effect on information
transfer and the analysis is the same as for the ShC(1; K) [12];
however, the case P > 1 seems to be much more difficult and
the corresponding analysis would require different methods
than the ones used here.
Precisely defining and analyzing models similar to those
studied in this paper, but which also include deletions and/or
out-of-order arrival of packets, is an interesting problem for
future investigation.
ACKNOWLEDGMENT
The authors would like to thank the three anonymous
reviewers for their comments which greatly improved the
presentation of this work.
R EFERENCES
[1] R. Ahlswede and A. H. Kaspi, “Optimal Coding Strategies for Certain
Permuting Channels,” IEEE Trans. Inf. Theory, vol. 33, no. 3, pp. 310–
314, May 1987.
[2] R. Ahlswede, N. Cai, and Z. Zhang, “Erasure, List, and Detection ZeroError Capacities for Low Noise and a Relation to Identification,” IEEE
Trans. Inf. Theory, vol. 42, no. 1, pp. 55–62, Jan. 1996.
[3] V. Anantharam and S. Verdú, “Bits Through Queues,” IEEE Trans. Inf.
Theory, vol. 42, no. 1, pp. 4–18, Jan. 1996.

10

[4] A. S. Bedekar and M. Azizog̃lu, “The Information-Theoretic Capacity
of Discrete-Time Queues,” IEEE Trans. Inf. Theory, vol. 44, no. 2, pp.
446–461, Mar. 1998.
[5] S. Engelberg and O. Keren, “Reliable Communications Across Parallel
Asynchronous Channels With Arbitrary Skews,” IEEE Trans. Inf. Theory, vol. 63, no. 2, pp. 1120–1129, Feb. 2017.
[6] N. Farsad, H. B. Yilmaz, A. Eckford, C.-B. Chae, and W. Guo, “A
Comprehensive Survey of Recent Advancements in Molecular Communication,” IEEE Commun. Surveys Tuts., vol. 18, no. 3, pp. 1887–1919,
2016.
[7] L. Gargano, J. Körner, and U. Vaccaro, “Qualitative Independence and
Sperner Problems for Directed Graphs,” J. Combin. Theory Ser. A, vol.
61, no. 2, pp. 173–192, Nov. 1992.
[8] K. A. S. Immink, “Runlength-Limited Sequences,” Proc. IEEE, vol. 78,
no. 11, pp. 1745–1759, Nov. 1990.
[9] K. Kobayashi, “Combinatorial Structure and Capacity of the Permuting
Relay Channel,” IEEE Trans. Inf. Theory, vol. 33, no. 6, pp. 813–826,
Nov. 1987.
[10] J. Körner and A. Orlitsky, “Zero-Error Information Theory,” IEEE Trans.
Inf. Theory, vol. 44, no. 6, pp. 2207–2229, Oct. 1998.
[11] M. Kovačević, “A Note on Parallel Asynchronous Channels With
Arbitrary Skews,” IEEE Trans. Inf. Theory, to appear.
[12] M. Kovačević and P. Popovski, “Zero-Error Capacity of a Class of
Timing Channels,” IEEE Trans. Inf. Theory, vol. 60, no. 11, pp. 6796–
6800, Nov. 2014.
[13] V. Yu. Krachkovsky, “Bounds on the Zero-Error Capacity of the InputConstrained Bit-Shift Channel,” IEEE Trans. Inf. Theory, vol. 40, no. 4,
pp. 1240–1244, Jul. 1994.
[14] M. Langberg, M. Schwartz, and E. Yaakobi, “Coding for the ℓ∞ -Limited
Permutation Channel,” in Proc. 2015 IEEE Int. Symp. Inf. Theory (ISIT),
pp. 1936–1940, Hong Kong, Jun. 2015.
[15] T. Nakano, A. W. Eckford, and T. Haraguchi, Molecular Communication, Cambridge University Press, 2013.
[16] S. H. Sellke, C.-C. Wang, N. Shroff, and S. Bagchi, “Capacity Bounds
on Timing Channels with Bounded Service Times,” in Proc. 2007 IEEE
Int. Symp. Inf. Theory (ISIT), pp. 981–985, Nice, France, Jun. 2007.
[17] S. Shamai (Shitz) and E. Zehavi, “Bounds on the Capacity of the BitShift Magnetic Recording Channel,” IEEE Trans. Inf. Theory, vol. 37,
no. 3, pp. 863–872, May 1991.
[18] C. E. Shannon, “The Zero Error Capacity of a Noisy Channel,” IRE
Trans. Inf. Theory, vol. 2, no. 3, pp. 8–19, Sep. 1956.
[19] V. Y. F. Tan, “Asymptotic Estimates in Information Theory with NonVanishing Error Probabilities,” Foundations and Trends in Communications and Information Theory, vol. 11, nos. 1-2, pp. 1–184, 2014.
[20] J. A. Thomas, “On the Shannon Capacity of Discrete Time Queues,” in
Proc. 1997 IEEE Int. Symp. Inf. Theory (ISIT), p. 333, Ulm, Germany,
Jun./Jul. 1997.
[21] H. S. Wilf, “Perron-Frobenius Theory and the Zeros of Polynomials,”
Proc. Amer. Math. Soc., vol. 12, no. 2, pp. 247–250, Apr. 1961.
[22] H. S. Wilf, Mathematics for the Physical Sciences, Dover Publications,
Inc., 1978.

A PPENDIX
We list here several properties of the zero-error capacity of
the ShC(P ; K) and related quantities, regarded as functions of
the channel parameters. The parameters P and K are assumed
to be integers taking values P ≥ 1 and K ≥ 0. Whenever the
behavior of a function with respect to one variable is discussed,
it is understood that the remaining variables/parameters are
kept fixed.
Proposition 13. The function r, defined by rK+1 −P rK −1 =
0, r > 0, is
(a) Continuous, monotonically decreasing, and convex in K,
with r|K=0 = P + 1 and limK →∞ r = P ;
(b) Continuous, monotonically increasing, and convex in P ,
with limP →∞ Pr = 1.

The function R∗P ;K = log r is
(c) Continuous, monotonically decreasing, and convex in K;
(d) Continuous, monotonically increasing in P , and concave
over P ≥ 2.
Proof: The functions r and log r are well-defined for
arbitrary real (not necessarily integer) K and P in the specified
ranges. The claim is obtained by differentiating them, e.g.,
ṙK =

−(r − P )r ln r
−r ln r
=
, (20)
rK ((K + 1)r − KP )
(K + 1)(r − P ) + P

and verifying the sign of the derivatives.
The function RP ;K (w) is even easier to analyze since it is
explicit, see (8).
Proposition 14. The function RP ;K (w) is
(a) Continuous, monotonically decreasing, and convex in K;
(b) Continuous, monotonically increasing, and concave in P ;
(c) Continuous and concave in w ∈ [0, 1].
The values/limits of RP ;K (w) at K = 0, K → ∞, P = 1,
P → ∞, w = 0 and w = 1, can be found directly from (8).
Finally, we state several properties of the weight (the fraction of occupied cells) which optimizes the rate of a constantweight code.
Proposition 15. Define w∗ = argmaxw∈[0,1] RP ;K (w). The
function w∗ has the following properties:
P
(a) w∗ = (K+1)(r−P
)+P < 1;
(b) It is continuous, monotonically increasing in P , and
concave over P ≥ 2;
(c) For P ≥ 2, it is monotonically increasing in K, with
limK →∞ w∗ = 1;
For P = 1, it is monotonically decreasing in K, with
limK →∞ w∗ = 0.
Proof: Equating the derivative of RP ;K (w) with zero we
get that w∗ is the solution of

 1
w∗ K + 1
1 − w∗ K+1
· P = 1.
(21)
·
w∗ (K + 1)
w∗ K + 1
Letting h = P (w∗ K +1)/(w∗ (K +1)), (21) becomes hK+1 −
P hK − 1 = 0, which means that h = r. This proves (a).
(b) is shown by calculating the derivatives of w∗ from (a).
To prove (c), it is enough to demonstrate that the function
(K + 1)(r − P ) is monotonically decreasing to 0 for P ≥ 2,
and monotonically increasing to ∞ for P = 1, which can
again be shown by analyzing its derivative.

