1

Time-Varying Block Codes for Synchronization
Errors: MAP Decoder and Practical Issues

arXiv:1802.08595v1 [cs.IT] 23 Feb 2018

Johann A. Briffa, Victor Buttigieg, Member, IEEE, and Stephan Wesemeyer

Abstract—In this paper we consider Time-Varying Block
(TVB) codes, which generalize a number of previous synchronization error-correcting codes. We also consider various practical
issues related to MAP decoding of these codes. Specifically, we
give an expression for the expected distribution of drift between
transmitter and receiver due to synchronization errors. We
determine an appropriate choice for state space limits based on
the drift probability distribution. In turn, we obtain an expression
for the decoder complexity under given channel conditions in
terms of the state space limits used. For a given state space, we
also give a number of optimizations that reduce the algorithm
complexity with no further loss of decoder performance. We
also show how the MAP decoder can be used in the absence of
known frame boundaries, and demonstrate that an appropriate
choice of decoder parameters allows the decoder to approach
the performance when frame boundaries are known, at the
expense of some increase in complexity. Finally, we express some
existing constructions as TVB codes, comparing performance
with published results, and showing that improved performance
is possible by taking advantage of the flexibility of TVB codes.
Index Terms—Insertion-Deletion Correction, MAP Decoder,
Forward-Backward Algorithm

I. I NTRODUCTION
Most error-control systems are designed to detect and/or
correct substitution errors, where individual symbols of the
received sequence have been substituted while maintaining
synchronization with the transmitted sequence. Some channels, however, also experience synchronization errors, where
symbols may additionally be deleted from or inserted into the
received sequence. It has long been recognized that codes can
be designed specifically for synchronization error correction
[1], [2]. Except for the less-known work by Gallager [3],
for a long time only some short block codes were known.
This changed when Davey and MacKay [4] proposed a concatenated scheme combining an outer LDPC code with good
error-correction capability with an inner code whose aim is
to correct synchronization errors. Ratzer [5] took a different
approach, using short marker sequences inserted in binary
LDPC codewords; a similar approach was used by Wang
et al. [6]. Yet another approach extends the state space of
convolutional codes to allow correction of synchronization
errors [7]–[9]. The problem of convolutional code design for
Manuscript submitted February 27, 2014; accepted May 29, 2014 for
publication in the IET Journal of Engineering. This research has been carried
out using computational facilities procured through the European Regional
Development Fund, Project ERDF-080.
J. A. Briffa and S. Wesemeyer are with the Dept. of Computing, University of Surrey, Guildford GU2 7XH, England. Email: j.briffa@surrey.ac.uk;
s.wesemeyer@surrey.ac.uk
V. Buttigieg is with the Dept. of Comm. & Computer Engineering, University of Malta, Msida MSD 2080, Malta. Email: victor.buttigieg@um.edu.mt

synchronization error channels has been considered in [10].
More recently, this approach has been applied successfully to
turbo codes [11]. The renewed increase in interest is mainly
due to new applications requiring such codes. A recent survey
can be found in [12].
We have in previous papers extended the work of DaveyMacKay, proposing a maximum a posteriori (MAP) decoder
[13], improved code designs [14], [15], as well as a parallel
implementation of the MAP decoder resulting in speedups of
up to two orders of magnitude [16]. However, these papers
were restricted to the case where the frame boundaries were
known by the decoder. While Davey and MacKay showed that
the frame boundaries could be accurately determined for their
bit-level decoder and code construction [4], it has not been
shown whether this property extends to our MAP decoder and
improved constructions.
In this paper we define Time-Varying Block (TVB) codes in
terms of the encoding used in [16], and show that TVB codes
represent a new class of codes which generalizes a number of
previous synchronization error-correcting codes. We use the
MAP decoder of [16] for these codes, showing how it can
be used in an iterative scheme with an outer code. We also
consider a number of important issues related to any practical
implementation of the MAP decoder. Specifically, we give
an expression for the expected distribution of drift between
transmitter and receiver due to synchronization errors. We
determine an appropriate choice for state space limits based
on the drift probability distribution. In turn, we obtain an
expression for the decoder complexity under given channel
conditions in terms of the state space limits used. For a
given state space, we also give a number of optimizations
that reduce the algorithm complexity with no further loss of
decoder performance. We also show how the MAP decoder
can be used for stream decoding, where the boundaries of
the received frames are not known a priori. In doing so we
demonstrate how an appropriate choice of decoder parameters
allows stream decoding to approach the performance when
frame boundaries are known, at the expense of some increase
in complexity. We express some previously published codes
as TVB codes, comparing performance with published results,
and showing that the greater flexibility of TVB codes permits
the creation of improved codes.
In the following, we start with definitions in Section II
and summaries of results from earlier work. The applicable
design criteria for TVB codes are considered in Section III,
together with the representation of previously published codes
as TVB codes. The appropriate choice for state space limits is
given in Section IV, followed by expressions for the decoder

2

complexity in Section V. MAP decoder optimizations are given
in Section VI and the changes necessary for stream decoding in
Section VII. Finally, practical results are given in Section VIII.
II. BACKGROUND
A. TVB Codes
Consider the encoding defined in [16], used there to simplify
the representation of the inner code of [4]. We observe that
this encoding generalizes a number of additional previous
schemes, including the inner codes of [5], [6], [15] (c.f.
Section III-B). We define a TVB code in terms of this encoding
by the sequence C = (C0 , . . . , CN −1 ), which consists of the
constituent encodings Ci : Fq ,→ Fn2 for i = 0, . . . , N − 1,
where n, q, N ∈ N, 2n ≥ q, and ,→ denotes an injective
mapping. Two constituent encodings Ci , Cj are said to be
equal if Ci (D) ∈ Cj ∀D. For a given TVB code, the set
of unique constituent encodings is that set where no two
constituent encodings are equal; the cardinality of this set,
denoted by M ≤ N , is called the order of the code. Note that
unique constituent encodings may still have some common
codewords. We denoted a TVB code by the tuple (n, q, M ).
We restrict ourselves to binary TVB codes, where codewords
are sequences of bits; the extension to the non-binary case is
trivial.
For any sequence z, denote arbitrary subsequences as
zba = (za , . . . , zb−1 ), where zaa = () is an empty sequence. Given a message DN
= (D0 , . . . , DN −1 ), each
0
Ci maps the q-ary message symbol Di ∈ Fq to codeword
nN
Ci (Di ) of length n. That is, DN
=
0 is encoded as X0
C0 (D0 )k · · · kCN −1 (DN −1 ), where ykz is the juxtaposition
of y and z. Each q-ary symbol is encoded independently of
previous inputs, and different codebooks may be used for
each input symbol. This time-variation offers no advantage
on a fully synchronized channel. However, in the presence
of synchronization errors, the differences between neighbouring codebooks provide useful information to the decoder to
recover synchronization.
In practice a TVB code is suitable as an inner code to correct
synchronization errors in a serially concatenated construction.
A conventional outer code corrects residual substitution errors.
In such a scheme, the inner code’s MAP decoder a posteriori
probabilities (APPs) are used to initialize the outer decoder.
The concatenated code can be iteratively decoded, in which
case the prior symbol probabilities of the inner decoder are
set using extrinsic information from the previous pass of the
outer decoder.
B. Channel Model
We consider the Binary Substitution, Insertion, and Deletion
(BSID) channel, an abstract random channel with unbounded
synchronization and substitution errors, originally presented in
[17] and more recently used in [4], [5], [13]–[15] and others.
At time t, one bit enters the channel, and one of three events
may happen: insertion with probability Pi where a random
bit is output; deletion with probability Pd where the input is
discarded; or transmission with probability Pt = 1 − Pi − Pd .
A substitution occurs in a transmitted bit with probability Ps .

After an insertion the channel remains at time t and is subject
to the same events again, otherwise it proceeds to time t + 1,
ready for another input bit.
We define the drift St at time t as the difference between
the number of received bits and the number of transmitted
bits before the events of time t are considered. As in [4], the
channel can be seen as a Markov process with the state being
the drift St . It is helpful to see the sequence of states as a
trellis diagram, observing that there may be more than one
way to achieve each state transition. Also note that the state
space is unlimited for positive drifts but limited for negative
drifts. Specifically, St may take any positive value for t > 0,
though with decreasing probability as the value increases. On
the other hand, St ≥ −t where the lower limit corresponds to
receiving the null sequence.
C. The MAP Decoder
We summarize here the MAP decoder of [16]; this is the
same as the MAP decoder of [13] with a trivial modification
to work with the notation of TVB codes. The decoder uses
the standard forward-backward algorithm for hidden Markov
models. We assume a message sequence DN
0 , encoded using a
(n, q, M ) TVB code to the sequence Xτ0 , where τ = nN . The
sequence Xτ0 is transmitted over the BSID channel, resulting
in the received sequence Y0ρ , where in general ρ is not equal
to τ . To avoid ambiguity, we refer to the message sequence
as a block of size N and the encoded sequence as a frame
of size τ . We calculate the APP Li (D) of having encoded
symbol D ∈ Fq in position i for 0 ≤ i < N , given the entire
received sequence, using
X
1
σi (m0 , m, D),
(1)
Li (D) =
λN (ρ − τ ) 0
m ,m

where λi (m) = αi (m)βi (m),

(2)

σi (m0 , m, D) = αi (m0 )γi (m0 , m, D)βi+1 (m),

(3)

and αi (m), βi (m), and γi (m0 , m, D) are the forward, backward, and state transition metrics respectively. Note that
strictly, the above metrics depend on Y0ρ , but for brevity we do
not indicate this dependence in the notation. The summation in
(1) is taken over the combination of m0 , m, being respectively
the drift before and after the symbol at index i. The forward
and backward metrics are obtained recursively using
X
αi (m) =
αi−1 (m0 )γi−1 (m0 , m, D),
(4)
m0 ,D

and βi (m) =

X

βi+1 (m0 )γi (m, m0 , D).

(5)

m0 ,D

Initial conditions for known frame boundaries are given by
(
(
1 if m = 0
1 if m = ρ − τ
α0 (m) =
and βN (m) =
0 otherwise,
0 otherwise.
Finally, the state transition metric is defined as
n(i+1)+m

γi (m0 , m, D) = Pr {Di = D} R(Yni+m0

| Ci (D)) (6)

where Ci (D) is the n-bit sequence encoding D and R(ẏ|x) is
the probability of receiving a sequence ẏ given that x was sent

3

through the channel (we refer to this as the receiver metric).
The a priori probability Pr {Di = D} is determined by the
source statistics, which we generally assume to be equiprobable so that Pr {Di = D} = 1/q. In iterative decoding, the
prior probabilities are set using extrinsic information from the
previous pass of an outer decoder, as explained in Section II-A.
The receiver metric is obtained by calculating the forward
recursion
X

t+m
α̇t−1 (m0 ) · Q ẏt−1+m
α̇t (m) =
(7)
0 |xt−1 ,
m0

where for brevity we do not show the dependence on ẏ and
x, and Q(y|x) can be directly computed from y, x and the
channel parameters:

if µ = 0

 Pd 

Pi µ−1
1
Q(y|x) =
Pt P s + 2 Pi P d
if µ > 0, yµ−1 6= x
2


 Pi µ−1
1
Pt P̄s + 2 Pi Pd
if µ > 0, yµ−1 = x,
2
where µ is the length of y and P̄s = 1 − Ps . The required
value of the receiver metric is given by R(ẏ|x) = α̇n (µ̇ − n),
where µ̇ is the length of ẏ, n is the length of x.
As in [16], the α, β, and α̇ metrics are normalized as
they are computed to avoid exceeding the limits of floatingpoint representation. We also assume that (7) is computed at
single precision1 , while the remaining equations use double
precision.
III. TVB C ODE D ESIGN
A. Construction Criteria
In any error-correcting scheme, the decoder’s objective is
to minimize the probability of decoding error (at the bit or
codeword level depending on the application). If the channel
does not introduce synchronization errors, this optimization
may be performed independently of previous or subsequent
codewords. Hence the performance of the code depends exclusively on its distance properties. In particular, the performance
of the code at low channel error rate is dominated by the code’s
minimum Hamming distance. At any channel error rate the
performance is determined by the code’s distance spectrum
[18], [19]. Thus when designing codes for substitution error
channels, either the minimum Hamming distance or the more
complete distance spectrum needs to be optimized for the
given code parameters.
In the case of the BSID channel, and other channels that
allow synchronization errors, a similar behaviour is observed
if the codeword boundaries are known, only this time the
Levenshtein distance [2] replaces the Hamming one. Recall
that the Levenshtein distance gives the minimum number of
edits (insertions, deletions, or substitutions) that will change
one codeword into another.
For the BSID channel an upper bound for the probability
of decoding a codeword in error was given in [15], assuming
codeword boundaries are known. For Pi , Pd , Ps  1, the
bound of [15, (9)] is dominated by the number of correctable
1 We refer to 32-bit floating point as single precision, and 64-bit floating
point as double precision.

errors, t. Now, for a code with jminimumk Levenshtein distance
d
−1
[2]. Hence designing
dlmin , it can be shown that t = lmin
2
TVB codes with constituent encodings having large dlmin will
result in the greatest improvement to the code’s performance
at low channel error rates.
However, in general the codeword boundaries are not known
and need to be estimated by the decoder. Therefore decoding
a given codeword on synchronization error channels depends
not only on the current received word, but also on previous and
subsequent ones. This means that the performance of a TVB
code depends not only on the distance properties of constituent
encodings considered separately, but also on the relationship
between constituent encodings. This effect becomes more
significant under poorer channel conditions, where the drift
can easily exceed the length of a codeword. Unfortunately,
the required relationship between constituent encodings for
optimal performance over the BSID channel is still an open
problem. What is known is that the diversity created by a
sequence of different encodings helps the decoder estimate
the drift within a codeword length, improving performance at
higher channel error rates [15].
B. Representation of Previous Schemes as TVB Codes
TVB codes generalize a number of existing synchronization
error-correcting codes. The flexibility of the generalization
allows the creation of improved codes at the same size and
rate, as we shall show.
Consider first the sparse inner codes with a distributed
marker sequence2 of the Davey-MacKay construction [4]. It is
clear that the sparse code is a fixed encoding C 0 : Fq ,→ Fn2 ;
these codewords are then added to a distributed marker sequence wi of length n, specific for each codeword index i.
Thus we can write Ci (Di ) = C 0 (Di ) + wi to represent the
inner codes of [4] as TVB codes. The equivalence of this
mapping to the inner code of [4] has also been shown in [16].
The distributed marker serves the same function as the use of
different encodings in TVB codes. The decoder of [4] tracks
the marker sequence directly, treating the additive encoded
message sequence as substitution errors. Therefore, to corrupt
the marker sequence as little as possible, the inner code used is
sparse. The sparseness results in a low dlmin , making it harder
for the decoder to distinguish between the various codewords,
and leads to relatively poor performance at low channel error
rates.
The codes of [15] can similarly be represented as TVB
codes, with C 0 corresponding to the Synchronization and Error
Correcting (SEC) code and wi corresponding to the Allowed
Modification Vectors (AMVs). SEC codes are designed with
a large dlmin for good performance at low channel error rates.
For such channels this code can perform much better than
the sparse code of [4]. AMVs are chosen such that when
added to the SEC code the resulting code’s dlmin does not
change. Clearly, the AMVs serve the same function as the
use of different encodings in TVB codes. In contrast to a
random distributed marker sequence, the use of AMVs does
2 This

was originally referred to as a watermark sequence.

4

Table I
A (7, 8, 4) TVB CODE C = (C0 , . . . , C3 ) WITH dlmin = 3.

100
C1
0000000
0000111
0011110
0110101
1001001
1100110
1111000
1111111

C2
0000011
0001100
0011111
0101010
1011001
1100000
1100111
1111110

C3
0000000
0001111
0101001
0110110
1000011
1001100
1110000
1111111

10−1

Symbol Error Rate

C0
0000000
0000111
0011001
0110110
1001010
1100001
1111000
1111111

Comparison of Inner Codes with (n,q) =(7,8) and N =666
(7,8) sparse + random marker
3 data bits + 4 marker bits
(7,8,3) SEC code with 8 AMVs
(7,8,4) TVB code

10−2

10−3

not compromise the performance of the underlying SEC code
at low channel error rates. In general, however, the Levenshtein distance spectrum is altered. The separate constituent
encodings in TVB codes give greater design freedom than SEC
codes with AMVs and also allows the design of constituent
encodings that maintain the required optimized Levenshtein
distance spectrum.
The marker codes given by Ratzer [5] can also be cast as
TVB codes by letting each possible sequence of data bits
(between markers) be represented by a q-ary symbol. For
example, consider a marker code with 3 marker bits inserted
after every 9 data bits, where the 3-bit marker is randomly
chosen between the sequences 001 and 110. This can be
represented as a (12, 512, 2) TVB code, where encoding C0
consists of all possible 9-bit sequences appended with 001,
and C1 consists of all possible 9-bit sequences appended with
110. Like the sparse codes of [4], these marker codes suffer
from a low dlmin , leading to relatively poor performance at
low channel error rates. On the other hand, the fixed marker
bits improve the determination of codeword boundaries, and
the random use of different marker bits creates the necessary
diversity to improve performance in poorer channel conditions.
To illustrate the difference in performance between the
various designs, consider encodings of size (n, q) = (7, 8)
with N = 666 (same size as codes C and H in [4]). A (7, 8, 4)
TVB code where each constituent code has the best possible
Levenshtein distance spectrum with dlmin = 3, found through
an exhaustive search, is given in Table I. In Fig. 1 we compare
this TVB code with earlier constructions from the literature
at the same size. Consider first the SEC code of the same
size and dlmin from [15], used with 8 AMVs in a random
sequence. As expected, the TVB code performs better due to
its improved Levenshtein distance spectrum, even though both
TVB and SEC codes have the same dlmin . The performance
of the sparse code with random distributed marker from [4]
is considerably worse, particularly at low channel error rates.
Similarly a code with three data bits and four marker bits
(randomly chosen between 0011/1100), similar to [5], also
performs poorly at low channel error rates.
IV. A PPROPRIATE L IMITS ON S TATE S PACE
The equations in Section II-C assume that summations can
be taken over the set of all possible states. For a channel such
as the one considered, the state space is unbounded for positive
drifts. A practical implementation will have to take sums over
a finite subset of states. In [4] the state space was limited

10−4 −5
10

10−4

10−3

10−2

Channel Error Event Probability (Pd = Pi; Ps =0)

10−1 3 ×10−1

Figure 1. Comparison of inner code designs of size (n, q) = (7, 8) with
N = 666: a sparse code with random distributed marker from [4], a marker
code with 0011/1100 marker bits similar to [5], a SEC code with randomlysequenced AMVs from [15], and the TVB code of Table I.

to a drift |St | ≤ xmax , where xmax was chosen to be ‘several
times larger’ than the standard deviation of the synchronization
drift over one block length, assuming this takes a Gaussian
distribution. No recommendation was given for the value that
should be used.
Limiting the state space is by definition sub-optimal. However, we can arbitrarily lower the number of cases where the
sub-optimal solution is worse than the optimal one, by ensuring that only the least likely states are omitted. The choice
of summation limits also involves a trade-off with complexity,
which has a polynomial relationship with the size of the state
space (c.f. Section V). Therefore, an appropriate choice of
summation limits will result in the smallest state space such
that the probability of the drift being outside that range is as
low as required. The first step to identify good summation
limits is to derive an accurate probability distribution of the
state space, avoiding the Gaussian approximation of [4].
A. Drift Probability Distribution
The drift ST after transmission of T bits was stated in [4]
(and shown in [20]) to be normally distributed with zero mean
and a variance equal to T p/(1 − p) for the special case where
p := Pi = Pd . This distribution is asymptotically valid as
T → ∞. For cases where Pi 6= Pd or where T is not large
enough, this distribution cannot be used. This is particularly
relevant for determining the summation limits of (7) where
the sequence length n is not large. An exact expression for
the probability distribution of ST is given by
ΦT (m) = Pr {ST = m}

j
T  
X
T
T +m+j−1
Pi Pd
T m
= Pt Pi
,
j
m+j
Pt
j=j

(8)

0

where j0 = max(−m, 0). Observe that for a drift of m bits,
we need m insertion events more than we have deletion events.
Over a sequence of T bits, for j deletion events, this means

5

m + j insertion events and T − j transmission events. The
j
probability of this is Pim+j Pdj PtT −j = PtT Pim [Pi Pd /Pt ] . We
get (8) by adding all different combinations of these events,
and summing over j, noting that we cannot have fewer than 0
events of any type. Specifically, the number of combinations

for j deletions in T transmitted bits is given by Tj . The
number of combinations for m + j insertions is given by
T +m+j−1
, as the m + j insertion events create an additional
m+j
m + j opportunities for insertion.
B. Avoiding Numerical Issues
In a practical implementation, computing the drift probability (8) requires a few special considerations. Practical
codes from the literature have codeword size n in the range
5–12 bits and number of codewords N up to 1000, for a
frame length nN of about 4000–6000 bits. These codes are
designed to operate under channel conditions Pi , Pd from 10−3
to above 10−1 . Evaluating (8) under these conditions, one
encounters very large values for the two binomial coefficients
and very small values for the power term. For example,
consider evaluating (8) at m = 0 for T = 6000 and
Pi = Pd = 10−3 . The two binomial coefficients have a range
of up to 1.56 × 101804 (at j = 3000) and 8.34 × 103609
(at j = 6000) respectively. The power term has a range of
down to 1.65 × 10−35995 (at j = 6000). This range is far
beyond that representable even in double-precision floating
point. A direct implementation of (8) will therefore result in
numerical overflow and underflow (in computing the binomial
coefficients and power term respectively) for typical frame
sizes and channel conditions, even though the summation term
itself is representable.
The above numerical range problem can be avoided by
combining the computation of all terms in the summation as
follows. Observe that (8) can be rewritten as
ΦT (m) =

T
X

δj ,

(9)

j=j0

j
 

T +m+j−1
Pi Pd
T m T
(10)
where δj = Pt Pi
Pt
j
m+j
and j0 = max(−m, 0) as before. In this expression, note
that the summation is empty if j0 > T , resulting in zero
probability. Also, since j ≥ 0, the first binomial coefficient
is always non-zero, while the second binomial coefficient is
non-zero if T > 0. Expanding the binomial coefficients using
the factorial formula, we can express the summation term
recursively as
δj = δj−1 ·

Pi P d T + m + j − 1 T − j + 1
·
·
,
Pt
m+j
j

(11)

allowing successive factors to be determined easily from
previous ones. The initial factor required is the one at j0 ,
and can be determined from (10) by expanding the binomial
coefficients using the multiplicative formula:

j
j0
m+j0
Y
T − j0 − i Y T − 1 − i Pi Pd 0
δj0 = PtT Pim
.
i
i
Pt
i=1
i=1
(12)

Consider the earlier example, now evaluating (9) at m = 0
for T = 6000 and Pi = Pd = 10−3 . In this case, the initial
value δj0 = 6.07 × 10−6 , and the multiplier δj /δj−1 in the
recursive expression (11) has its smallest value of 3.34×10−10
at j = 6000. Both values are easily representable as floating
point numbers.
Using (9), numerical range issues remain when computing
δj0 for larger values of Pi , Pd , and consequently also for storing successive values of δj . For example, consider evaluating
(9) at m = 0 for T = 6000 and Pi = Pd = 10−1 . In
this case δj0 = 3.47 × 10−582 , and one needs to accumulate
a number of δj values in this range to obtain the required
result Φ6000 (0) = 0.0109. Again, the intermediate values are
beyond the range of double-precision floating point numbers
although the final result is representable. These numerical
range issues can be avoided by computing (11) and (12) using
logarithms. For the earlier example with m = 0, T = 6000,
and Pi = Pd = 10−1 , we now get log δj0 = −1.34 × 103 and
the smallest value of log δj is −1.93 × 104 at j = 6000.
Finally, the required drift probability is obtained by accumulating the exponential of the log δj values using (9).
However, the individual values of δj are still beyond the
range of double-precision floating point. In practice, we have
found that the use of extended-precision (80-bit) floating point
provides sufficient range. Alternatively, the accumulation in (9)
may be computed in logarithmic domain using
the property

log(A + B) = log A + log 1 + elog B−log A .
Note that expression (8) is valid for any Pi ≥ 0, Pd ≥ 0,
and Pi + Pd < 1. However, the computation using logarithms
cannot be applied directly when either or both of Pi and
Pd are zero. These degenerate cases have to be handled as
special cases, by first reducing (8) and then implementing the
simplified equations using logarithms.

C. Probability of Drift Outside Range
+
We want to choose lower and upper limits m−
T , mT such
that the drift after transmitting a sequence of T bits is outside
+
the range {m−
T . . . mT } with an arbitrarily low probability Pr :



+
Pr ST < m−
< Pr ,
T + Pr ST > mT

(13)

m+
T

or equivalently: 1 −

X

ΦT (m) < Pr .

(14)

m=m−
T

An appropriate choice of limits can be obtained iteratively
as follows. Observe that for the BSID channel ΦT (m) is
monotonically decreasing with increasing |m|. A first estimate
for the limits is given by:
−(1)

mT

+(1)

and mT

Pr
2
Pr
= min m ΦT (m + 1) <
,
2
= max m ΦT (m − 1) <

(15)
(16)

where the number in superscript parentheses indicates the
iteration count. If these estimates satisfy (14), we use them

6

103

That is, we extend the range by one in the direction of greatest
gain. The iterative process is repeated until (14) is satisfied.
−
The size of the state space is given by MT = m+
T − mT + 1.

E. Example
Overestimating the required state space increases computational complexity, while underestimating the state space
often results in poor decoding performance. Accurate limits
are particularly important for restricting the drifts considered
across each codeword. It is therefore useful to illustrate the
discrepancy between the approximate distribution of [4] and
the exact expression for the distribution of the drift. Consider
a system with typical block and codeword sizes N = 500, n =

Mτ (appr.)
Mτ (exact)
Mn (appr.)
Mn (exact)
M1 (appr.)
M1 (exact)

102

101

100 −4
10

D. Choice of Summation Limits

10−3

10−2

10−1

Channel Error Event Probability (Pd = Pi; Ps =0)

100

(a)

Probability of Event Outside Chosen Limits

When considering the whole frame, T = τ , so that the
overall size of the state space is given by Mτ . Now the final
output of the MAP decoder is calculated using (1), which sums
0
+
over all Mτ prior states m−
τ ≤ m ≤ mτ . For each prior state,
however, only the drifts introduced by the transmission of n
bits need to be considered, corresponding to a subset Mn of
+
states m−
n ≤ m ≤ mn . Similarly, the computation of (4)
+
and (5) is required for all Mτ states m−
τ ≤ m ≤ mτ , each
involving a summation over Mn prior or posterior states m−
n ≤
respectively.
Finally,
the
state
transition
metric
is
m0 ≤ m+
n
obtained using the forward pass of (7); this is computed over
+
a sequence of n bits for each of Mn states m−
n ≤ m ≤ mn .
Each recursion consists of a summation over prior states m0 ;
in this case only the drifts introduced by the transmission of
one bit need to be considered, corresponding to a subset M1
+
0
of prior states m−
1 ≤ m ≤ m1 .
Now consider that we want to limit the probability of any
of these summations not covering an actual channel event over
a whole frame to, say, no more than Pe . When computing the
limits over the whole frame, m±
τ , we simply need to set Pr =
Pe . However, when computing limits over an n-bit sequence,
m±
repeated for each of N such
n , since this summation is √
sequences, we set Pr = 1 − N 1 − Pe ≈ PNe for small Pe .
Similarly,
for limits over a 1-bit sequence, m±
1 , we use Pr =
√
τ
1 − 1 − Pe ≈ Pτe for small Pe .
Except in the case of stream decoding (c.f. Section VII),
the state space limits only need to be determined once and
remain valid as long as the channel conditions do not change.
In any case, the required values of ΦT (m) depend only on
the code parameters and channel conditions, so that a table
may be pre-computed. This makes the average complexity of
determining the state space limits negligible.

N =500, n =10, Pe =10−10

104

Number of States

as our lower and upper limits. Otherwise these estimates are
updated iteratively as follows:
(
−(i)
+(i)
−(i)
mT − 1 if ΦT (mT + 1) ≤ ΦT (mT − 1)
−(i+1)
mT
=
−(i)
mT
otherwise,
(17)
(
+(i)
+(i)
−(i)
mT + 1 if ΦT (mT + 1) > ΦT (mT − 1)
+(i+1)
mT
=
+(i)
mT
otherwise.
(18)

100
10−1
10−2
10−3
10−4
10−5
10−6
10−7
10−8
10−9
10−10
10−11
10−12
10−13 −4
10

N =500, n =10, Pe =10−10
Mτ (appr.)
Mτ (exact)
Mn (appr.)
Mn (exact)
M1 (appr.)
M1 (exact)

10−3

10−2

10−1

Channel Error Event Probability (Pd = Pi; Ps =0)

100

(b)
Figure 2. (a) Number of states within summation limits, and (b) probability
of encountering a channel event outside the chosen summation limits over a
single frame, using the approximation of [4] and our exact computation.

10. We plot in Fig. 2a the number of states within summation
limits using the approximate and exact expressions, in each
case for Pe = 10−10 . For T = 1, [4, Section VII.A] assumes
a maximum of two successive insertions; this is equivalent to
setting m+
1 = 2, so that M1 = 4. It is immediately apparent
that while the approximation is very close for large T and high
Pi = Pd , it quickly starts to underestimate the required range
at lower channel error rates. As expected, the discrepancy
is particularly large when considering shorter sequences. For
T = 1 it is not surprising that there is a large discrepancy for
channels with high error rate.
Next, we determine the probability of encountering a channel event outside the chosen limits over a single frame, shown
in Fig. 2b for the same limits used in Fig. 2a. For the
exact distribution, this probability is always below the chosen
threshold Pe = 10−10 , as expected. For the approximation,
however, the probability of exceeding the chosen limits is
higher than the threshold throughout the range considered.

7

At lower channel error rates, the discrepancy is significant
(several orders of magnitude) even for large T . For small T ,
the probability of exceeding the chosen limits is high enough
to make the approximation useless. For T = 1, the artificial
limit of two successive insertions of [4] means that channels
with high error rate will exceed this limit with high probability.
V. A LGORITHM C OMPLEXITY
A. Complexity of the MAP Decoder
As a first step towards determining the overall complexity of
the decoder, consider first the calculation of the state transition
metric in (6). This is recursively computed using the forward
pass of (7) over a sequence of n bits, for each of Mn states
m. Each recursion consists of a summation over M1 prior
states m0 as argued in Section IV-D. The bit-level probability
Q can be obtained by a look-up table. Thus the complexity
for calculating a single state transition metric is Θ(nMn M1 ).
The final output of the algorithm consists of q probabilities
for each of N symbols, calculated using (1). This equation
sums over all Mτ prior states m0 and Mn states m, defining the
domain for σi (m0 , m, D). It follows from (3) that the domain
for γi (m0 , m, D) is the same. Now the computation of (3) is
dominated by the evaluation of γi (m0 , m, D) in (6), whose
complexity is Θ(nMn M1 ) as shown. Considering the number
of times the γ metric is computed, the MAP decoder has an
asymptotic complexity of Θ(N nqMτ Mn2 M1 ).
B. Complexity of the Davey-MacKay Decoder
It would initially appear that the MAP decoder complexity
is significantly higher than that of the Davey-MacKay decoder,
given as O(N nMτ M1 ) in [4] for a direct implementation
(using our notation). However, the expression of the DaveyMacKay decoder seems to consider only the complexity of the
initial forward and backward passes, ignoring the additional
small forward passes needed to compute the final decoder
output.
The final output of the Davey-MacKay algorithm also consists of q probabilities for each of N symbols. Each of these is
computed using [4, (4)], which sums over all possible prior and
posterior states. In a direct implementation all possible prior
states need to be considered; using our notation the number of
states is Mτ . While not stated in [4], the number of posterior
states that need to be considered is Mn , as argued for the MAP
decoder. The computation within the summation of [4, (4)] is
dominated by the conditional probability, which is computed
using a separate forward pass. This forward pass is effectively
identical to (7) whose complexity is Θ(nMn M1 ). Considering
the number of times the forward pass is computed, it follows
that the Davey-MacKay decoder has an overall asymptotic
complexity of Θ(N nqMτ Mn2 M1 ).
C. Comments on Algorithm Complexity
Comparing the complexity expressions for the MAP decoder
for TVB codes and the Davey-MacKay decoder for sparse
codes with a distributed marker sequence, it follows that the
asymptotic complexity for both decoders is the same. This is

consistent with experimental running times for both decoders
in [13].
In the complexity expression note that N , n, and q depend
only on the code parameters while Mτ , Mn , and M1 also
depend on the channel conditions. For M1 , it was argued in
[4, Section VII.A] that it is sufficient to consider a maximum
of two successive insertions, at a minimal cost to decoding
performance. This is equivalent to setting m+
1 = 2, so
that M1 = 4; these limits were also used in [13], [14].
However, this artificially low limit is insufficient for more
advanced code constructions, as shown in [15]. It was also
argued in [4] that useful speedups can be obtained by only
following paths through the trellis that pass through nodes with
probabilities above a certain threshold. However, the choice of
this threshold was not analyzed. It is also likely that this choice
would depend on the properties of the inner code being used.
VI. S PEEDING T HINGS U P
A. Batch Computation of Receiver Metric
In a naïve implementation, each γ computation (6) requires
the computation of the receiver metric as a separate forward
pass using (7). However it can be observed that for a given
starting state m0 and symbol D, the γ metric will be computed for each end state m within the limits considered (c.f.
equations (1), (3), (4), and (5), where the γ computations are
used). In turn, this means that for a given x, the receiver metric
will need to be determined for all subsequences ẏ within the
drift limit considered. It is therefore sufficient to compute the
forward pass (7) once, with the longest subsequence ẏ required. In doing so, the values of the receiver metric for shorter
subsequences are obtained for free. We call this approach
batch computation. This effectively reduces the complexity
of computing the collection of γ metrics by a factor of Mn .
The asymptotic complexity of the MAP decoder is therefore
reduced to Θ(N nqMτ Mn M1 ).
B. Lattice Implementation of Receiver Metric
To compute the receiver metric, an alternative to the trellis
of (7) is to define a recursion over a lattice as in [17]. For
the computation of R(ẏ|x), the required lattice has n + 1
rows and µ̇ + 1 columns. Each horizontal path represents an
insertion with probability 21 Pi , each vertical path is a deletion
with probability Pd , while each diagonal path is a transmission
with probability Pt Ps if the corresponding elements from x
and ẏ are different or Pt P̄s if they are the same. Let Fi,j
represent the lattice node in row i, column j. Then the lattice
computation in the general case is defined by the recursion
Fi,j =

1
Pi Fi,j−1 + Pd Fi−1,j + Q̇(ẏj |xi )Fi−1,j−1 ,
2

(19)

which is valid for i < n, and where Q̇(y|x) can be directly
computed from y, x and the channel parameters:
(
Pt Ps if y 6= x
Q̇(y|x) =
(20)
Pt P̄s if y = x.

8

Table II
C OMPLEXITY EXPRESSIONS FOR THE MAP DECODER FOR VARIOUS
COMPUTATION MODES OF THE RECEIVER METRIC .

Initial conditions are given by
(
1 if i = 0, j = 0
Fi,j =
0 if i < 0 or j < 0.

(21)

The last row is computed differently as the channel model
does not allow the last event to be an insertion. In this case,
when i = n, the lattice computation is defined by
Fn,j = Pd Fn−1,j + Q̇(ẏj |xn )Fn−1,j−1 .

C. Optimizing the Lattice Implementation
In the lattice implementation of the receiver metric, it can
be readily seen that the horizontal distance of a lattice node
from the main diagonal is equivalent to the channel drift for
the corresponding transmitted bit. It should therefore be clear
that the likelihood of a path passing through a lattice node
decreases as the distance to the main diagonal increases.
We can take advantage of the above observation by limiting
the lattice computation to paths within a fixed corridor around
the main diagonal. Specifically, the arguments of Section IV
can be applied directly, resulting in a corridor of width Mn
in general for the transmitted sequence of n bits considered.
Exceptions to this width occur in the first few rows with index
+
i < −m−
n and the last few rows with index i > µ̇ − mn ,
where part of the corridor falls outside the lattice rectangle.
The number of nodes within this corridor is given by
where κUL =
κLR =

−
∆(−m−
n ) − ∆(−mn − n),
+
∆(n + m+
n − µ̇) − ∆(mn −

(
and ∆(k) =

k2 +k
2

0

if k > 0
otherwise.

(23)
(24)
µ̇),

Algorithm
Original
Batch computation
Lattice receiver

D

Corridor constraint

Complexity
Θ(N nqMτ Mn2 M1 )
Θ(N nqMτ Mn M1 )
+
Θ(N
 nqMτ h[n + mn ]) h
ii
−
2
Θ N qMτ nMn − 21 (m−
n ) − mn

(22)

Finally, the required receiver metric is obtained from this
computation as R(ẏ|x) = Fn,µ̇ . The calculation of a single
run through the lattice requires a number of computations
proportional to the number of nodes in the lattice. Now for
the transmitted sequence of n bits considered, the number of
rows will always be n while the number of columns is at most
n + m+
n . The complexity of a direct implementation of this
algorithm is therefore Θ(n[n + m+
n ]).
It has been argued in Section VI-A that for a given x,
the receiver metric R(ẏ|x) needs to be determined for all
subsequences ẏ within the drift limit considered. Observe
that the same argument applies equally when the receiver
metric is computed using the lattice implementation (19).
Therefore, when the lattice implementation is used in batch
mode, the MAP decoder has an asymptotic complexity of
Θ(N nqMτ [n + m+
n ]).

κ = nMn − κUL − κLR ,

A
B
C

(25)
(26)

The complexity of the corridor-limited lattice algorithm is
therefore Θ(nMn − κUL − κLR ).
Some simplification of this expression is possible when
the corridor-limited lattice algorithm is used in the MAP
decoder with batch computation for the channel considered.
When batch computation is used, µ̇ = n + m+
n by definition, so that κLR = 0. Furthermore,
for
the
BSID
channel,
 − 2

1
−
−n ≤ m−
≤
0,
so
that
κ
=
(m
)
−
m
.
Under
these
UL
n
n
n
2

conditions,the MAP decoder
has an asymptotic
complexity of


2
−
Θ N qMτ nMn − 12 (m−
)
−
m
.
n
n
D. Comparing Complexity
A summary of the complexity expressions for the MAP
decoder for various computation modes of the receiver metric
is given in Table II. Comparing the expressions in rows A
and B of Table II we can immediately see that the batch
computation of the receiver metric reduces complexity by a
factor equal to Mn . Unfortunately, the remaining complexity
expressions contain terms that depend on the code parameters
and channel conditions in a rather opaque way, making it
harder to understand the benefits of these improvements. In
the first instance, we can simplify the expressions further to
facilitate comparison. Consider the expression in row C of
Table II, when the lattice implementation is used. It can be
shown that n + m+
n → Mn − 1 as channel conditions get
worse; we can therefore simplify the complexity expression to
O(N nqMτ Mn ). Comparing this to the expression in row B of
Table II we can see that the use of the lattice implementation
reduces complexity by a factor of at least M1 . Finally, consider
the expression in row D of Table II, when the corridor
−
constraint
 −is 2applied
 to the lattice algorithm. Since mn ≤ 0,
1
−
the 2 (mn ) − mn term is strictly positive. The reduction in
complexity offered by the corridor constraint is therefore equal
2nMn
to 2nM −(m
− , and becomes significant as channel con− 2
n
n ) +mn
ditions improve. As channel conditions get worse, m−
n → −n,
so that the expression is dominated by the nMn term. Under
these conditions, the complexity of the corridor-constrained
lattice implementation becomes approximately equal to that
of the unconstrained lattice implementation.
We can also illustrate the effect of the proposed speedups
by considering a rate- 21 TVB code with typical block and
codeword sizes N = 500, n = 10, and q = 32. We
compute the MAP decoder complexity for this code under
a range of channel conditions, using the original algorithm
of Section II-C and the improvements described above. We
plot these in Fig. 3 using the same summation limits as
in Section IV-E. Note that for a fairer comparison between
the lattice and trellis modes, we include a constant factor of
three in the lattice computation. This follows the observation
that each lattice node computation (19) requires three multiplications while each trellis computation (7) requires only
one. A few general observations can be made on this graph:
a) The batch computation of the receiver metric results in
a considerable reduction of complexity throughout, but is
even more significant under poor channel conditions. b) The
lattice implementation is considerably less complex than the

9

N =500, n =10, q =32

Complexity (Number of Arithmetic Operations)

1014
1013
1012

Trellis
Trellis (batch)
Lattice (batch)
Lattice corridor (batch)

1011
1010
109
108
107 −4
10

10−3

10−2

10−1

Channel Error Event Probability (Pd = Pi; Ps =0)

100

Figure 3. MAP decoder complexity (in number of arithmetic operations) under
a range of channel conditions, for various computation modes of the receiver
metric.

trellis implementation at high channel error rates. c) The
lattice corridor constraint extends this improvement to the low
channel error rate range. In conclusion, the proposed speedups
result in a considerable reduction in complexity of almost
two orders of magnitude for typical code sizes and channel
conditions. We have observed a similar trend under a range of
typical code sizes, so this result can be taken as representative.

Note that in general this distribution βN (m) has a wider spread
than Φτ (m).
As discussed in Sections IV-C and IV-D, the choice of state
space limits depends on the expected distribution of drift.
For limits involving the whole frame, the distribution used
is Φτ (m), which assumes that the initial drift is zero. The
assumption does not hold under stream decoding conditions,
where the initial drift is not known a priori, although its distribution can be estimated. The uncertainty in locating the startof-frame position increases the uncertainty in locating the endof-frame position, resulting in a wider prior distribution for the
end-state boundary condition βN (m). Therefore, any limits on
state space determined using Φτ (m) will be underestimated.
The severity of this error depends on the difference between
βN (m) and Φτ (m), which increases as channel conditions
get worse. For stream decoding, therefore, it is sensible to
recompute the state space limit Mτ at the onset of decoding a
given frame, using βN (m) in lieu of Φτ (m). Doing so avoids
underestimating the required state space, and implies that for
stream decoding, the state space size will change depending
on how well-determined the frame boundaries are.
After decoding the current frame, we obtain the posterior
probability distribution for the drift at end-of-frame, given by:
n
o
n
o
τ +m+
τ +m+
Pr Sτ = m Ym− τ = λN (m)/ Pr Ym− τ
τ

τ

λN (m)
.
=P
0
m0 λN (m )

(28)

The most likely drift at end-of-frame can be found by:
VII. S TREAM D ECODING
We have so far considered the case where frame boundaries
are known exactly. While there are practical cases involving
single-frame transmission where this is true, exact frame
boundaries are often unknown. The MAP decoder can handle
such cases by changing the initial conditions for (4) and (5)
and choosing appropriate state space limits. This obviates
the need for explicit frame-synchronization markers as used
in conventional communication systems, and can therefore
reduce this overhead. The approach presented here is in
principle similar to that used in [4] for ‘sliding window’
decoding. However, there are some critical differences which
we explore further in Section VII-C.
A. Choosing End-of-Frame Priors
Consider first the common case where a sequence of frames
is transmitted in a stream. The usual practice in communication systems is for the receiver to decode one frame at a time,
starting the decoding process as soon as all the data related to
the current frame is obtained from the channel. In this
case,
τ +m+
the current received frame is considered to be Ym− τ , which
τ
may include some bits from the end of the previous frame and
start of the next frame. The end-state boundary condition for
(5) can be obtained by convolving the expected end-of-frame
drift probability distribution with the start-state distribution:
X
βN (m) =
α0 (m0 )Φτ (m − m0 ).
(27)
m0

λN (m)
= arg max λN (m).
0
m
m0 λN (m )

Ŝτ = arg max P
m

(29)

As in [4], we determine the nominal start position of the next
frame by shifting the received stream by τ + Ŝτ positions.
The initial condition for the forward metric for the next frame,
α̂0 (m), is set to:
λN (m + Ŝτ )
α̂0 (m) = P
,
0
m0 λN (m )

(30)

replacing the initial condition for (4) reflecting a known frame
boundary.
B. Stream Look-Ahead
Taking advantage of the different constituent encodings in
TVB codes, the MAP decoder can make use of information
from the following frame to improve the determination of the
end-of-frame position. We augment the current block of N
symbols with the first ν symbols from the following block
(or blocks, when ν > N ), for an augmented block size
N 0 = N +ν. The MAP decoder is applied to the corresponding
augmented frame. After decoding, only the posteriors for the
initial N symbols are kept; the start of the next frame is
determined from the drift posteriors at the end of the first
N symbols, and the process is repeated.
Consider the latency of the MAP decoder to be the time
from when the first bit of a frame enters the channel to when
the decoded frame is available. The cost of look-ahead is an
increase in decoding complexity and latency corresponding

10

to the change in block size from N to N 0 . The effect
on complexity is seen by using terms corresponding to the
augmented block size in the expressions of Table II. The
latency is equal to the time it takes to receive the complete
frame and decode it. Look-ahead increases the time to receive
the augmented frame linearly with ν and the decoding time
according to the increase in complexity.
The required look-ahead ν depends on the channel conditions and the code construction. In general, a larger value is
required as the channel error rate increases. We show how
an appropriate value for ν can be chosen for a given code
under specific channel conditions in Section VIII-A. Typical
values for ν are small (ν < 10) for good to moderate
channels (Pi , Pd < 10−2 ). The required look-ahead increases
significantly for poor channels: the example in Section VIII-A
requires ν = 1000 at Pi = Pd = 2 × 10−1 .
C. Comparison with Davey-MacKay Decoder
A key feature of the Davey-MacKay construction is the
presence of a known distributed marker sequence that is
independent of the encoded message. This allows the decoder,
in principle, to compute the forward and backward passes
over the complete stream. However, to reduce decoding delay,
the decoder of [4] performs frame-by-frame decoding using
a ‘sliding window’ mechanism. The ‘sliding window’ mechanism seems intended to approximate the computation of the
forward and backward passes over all received data at once.
This approach is similar in principle to ours when stream lookahead is used; however, there are some critical differences
which we discuss below.
In [4], the starting index for a given frame is taken to
be the most likely end position of the previous frame, as
determined by the Markov model posteriors. This is the same
as the approach we use in Section VII-A. However, in [4], the
initial conditions of the forward pass are simply copied from
the final values of the forward pass for the previous frame.
This is consistent with the view that the ‘sliding window’
mechanism approximates the computation over all received
data at once, but contrasts with our method. In Section VII-A
the initial conditions of the forward pass are determined from
the posterior probabilities of the drift at the end of the previous
frame. These drift posteriors include information from the
look-ahead region and from the priors at the end of the
augmented frame, which were determined analytically from
the channel parameters.
Observe that in the ‘sliding window’ mechanism of [4],
the backward pass values cannot be computed exactly as for
the complete stream. Instead, the decoder of [4] computes the
forward pass for some distance beyond the expected end of
frame position, and initializes the backward pass from that
point. The suggested distance by which to exceed the expected
end of frame position is ‘several (e.g. five) multiples of xmax ’,
where xmax is the largest drift considered. The concept is the
same as the stream look-ahead of Section VII-B. However,
we recommend choosing the look-ahead quantity ν based on
empirical evidence (c.f. Section VIII-A).
It is claimed in [4] that the backward pass is initialized
from the final forward pass values; the reasoning behind this

is unclear, and does not seem to have a theoretical justification.
We initialize the backward pass with the prior probabilities for
the drift at the end of frame, as explained in Section VII-A.
D. Initial Synchronization
The only remaining problem is to determine start-of-frame
synchronization at the onset of decoding a stream. This
can be obtained by choosing state space limits Mτ large
enough to encompass the initial desynchronization and by
setting equiprobable initial conditions: α0 (m) = βN (m) =
1
∀m. Previous experimental results [4] have assumed a
Mτ
known start for the first frame, with the decoder responsible
for maintaining synchronization from that point onwards. We
adopt the same strategy in the following.
VIII. R ESULTS
Practical results are given in this section. We show how
an appropriate choice of decoder parameters allows stream
decoding to perform as well as when frame boundaries are
known. Results are also given for existing constructions which
can be expressed as TVB codes, showing how the symbol-level
MAP decoder improves on the original decoder (in the case of
[4]) or is equivalent (in the case of [5]). We also demonstrate
some improved constructions allowed by the flexibility of TVB
codes. These are achieved by using simulated annealing to
find TVB codes of a required order with a good Levenshtein
distance spectrum. Specifically, we seek to find constituent
codes with the highest possible minimum Levenshtein distance
and the lowest multiplicity at small distances. For all codes
so designed, M < N ; we construct our TVB codes using a
random sampling with replacement of the unique constituent
codes, and use this as our inner code. Construction parameters
for all codes used in this section are given in Table III. To
facilitate reproduction of these results, the TVB codebooks
used are available for download from the first author’s web
site3 .
A. Stream Decoding with MAP Decoder
The results of [13] assumed known frame boundaries; under
these conditions, the decoder is arguably at an advantage
when comparing with the results of [4], [5]. It is also not
clear whether the MAP decoder can keep track of frame
boundaries with the non-sparse constructions of [13], [15] and
the TVB codes introduced here, especially in the absence of
a known marker sequence. In the following we investigate
the performance of the MAP decoder under stream decoding
conditions, and consider the choice of look-ahead required.
As in [4] we assume that the start of the first frame is known,
while the decoder is responsible for keeping synchronization
from that point onwards. We use the limits specified in
Section IV.
We start by investigating the effect of stream decoding on
the ability of the MAP decoder to track codeword boundaries.
We consider a (6, 8, 12) TVB code, which is the inner code
for the concatenated system N2b of Table III. We simulate
3 Available

at http://jabriffa.wordpress.com/publications/data-sets/.

11

Table III
C ONSTRUCTION PARAMETERS OF CODES USED IN SIMULATIONS .
Labela
P1
N1a
N1b
P2
N2a
N2b
P3
N3
P4
N4
P5
N5

Inner code
(5, 16) sparse
(5, 16) sparse
(10, 256, 3) TVB
(6, 8) sparse
(6, 8) sparse
(6, 8, 12) TVB
9 bits, uncoded
9 bits, uncoded
not applicable
(7, 8, 8) TVB
not applicable
(7, 4, 32) TVB

Marker
random, distributed
random, distributed
none
random, distributed
random, distributed
none
001/110, appended
001/110, appended
not applicable
none
not applicable
none

Outer code
LDPC (999, 888) F16
LDPC (999, 888) F16
LDPC (499, 444) F256
LDPC (1000, 100) F8
LDPC (1000, 100) F8
LDPC (1000, 100) F8
LDPC (3001, 2000) F2
LDPC (2997, 1998) F2 b
3
turbo code F2
Rate 14
LDPC (666, 333) F8
1
turbo code F2
Rate 10
LDPC (855, 300) F4

Comment
Published in [4, Fig. 8, Code D]
Identical construction to P1, symbol-level MAP decoder
Same overall rate and block size as P1
Published in [4, Fig. 8, Code I]
Identical construction to P2, symbol-level MAP decoder
Same overall rate, block size, and outer code as P2
Published in [5, Fig. 7, Code D]
Identical inner code to P3, marginally smaller outer code
Published in [11, Fig. 4, Code T2]
Same overall rate as P4
Published in [11, Fig. 4, Code T4]
Same overall rate as P5

a Labels

starting with P indicate previously published results, while labels starting with N indicate new simulation results.
by truncating the LDPC (3001, 2000) F2 of P3. This truncation is necessary so that the outer-encoded sequence can be expressed by an
integral number of inner codewords.
b Obtained

Fidelity at codeword boundaries, (p = Pd = Pi; Ps =0)

100

Frame Error Rate

Fidelity

10−2

10−3

10−1

10−2

(6,8,12) TVB, p =0.22

10−4

0

500
1000
1500
Index for codeword following boundary

2000

Figure 4. The fraction of correctly resynchronized codeword boundaries
(fidelity) as a function of codeword index, for code N2b of Table III.

this inner code with a block size N = 2000 under the channel
conditions at the onset of convergence for the concatenated
system, that is at Pi = Pd = 0.22, assuming only the
start position of the first frame is known. At each codeword
boundary we plot the fraction of correctly determined drifts
(fidelity) in Fig. 4. As expected, the fidelity drops at the end
of the frame, where the actual drift is unknown to the decoder.
However, it can be observed that the fidelity reaches a steady
high value within about 1000 codewords from the end of
frame. It could therefore be supposed that a look-ahead of
ν = 1000 would be sufficient for this code under these channel
conditions. The dip at the start of the frame is caused by the
uncertainty in the frame start position, due to the very low
fidelity at the end of the previous frame.
To test this hypothesis, we concatenate this inner code
with the (1000, 100) LDPC code over F8 of [4, Code I]. We
simulate this system under the following conditions: 1) known
frame start and end (frame decoding); 2) known start for
the first frame, unknown frame ends (stream decoding), no

Comparison of frame and stream decoding for code N2b

10−3 −1
10

Frame [1 iter]
Frame [5 iter]
Stream, ν =0 [1 iter]
Stream, ν =0 [5 iter]
Stream, ν =1000 [1 iter]
Stream, ν =1000 [5 iter]

Channel Error Event Probability (Pd = Pi; Ps =0)

100

Figure 5. Demonstration of the effect of look-ahead on the MAP decoder’s
performance under stream decoding conditions, and comparison with frame
decoding.

look-ahead; 3) stream decoding with look-ahead ν = 1000
codewords. Results are shown in Fig. 5. We give results after
the first and fifth iterations. As anticipated, performance under
stream decoding conditions is poorer than frame decoding if
there is no look-ahead. However, an appropriate look-ahead
quantity allows the decoder to perform as well under stream
decoding as under frame decoding.
It is important to highlight that this result is dependent on
the inner code structure, and that therefore the generalization
to other constructions is not obvious. However, we have
repeated the same test with other constructions, including
those of [4], [5], [13]–[15] and the new constructions in this
paper, and under different channel conditions. In all cases we
have found that the result is repeatable, in that it is possible
to approach the performance of frame decoding with stream
decoding, as long as an appropriate look-ahead quantity is
chosen. The only cost of stream decoding is therefore the need
for a fidelity analysis to determine a suitable look-ahead value

12

100

Comparison with Davey & MacKay

100

10−1

Frame Error Rate

Frame Error Rate

10−1

10−2

10−3

P1
N1a [1 iter]
N1a [5 iter]
N1b [1 iter]
N1b [5 iter]

10−4

10−5 −3
3 ×10

Comparison with Ratzer and Mansour & Tewfik

10−2

P2
N2a [1 iter]
N2a [5 iter]
N2b [1 iter]
N2b [5 iter]

10−1
Channel Error Event Probability (Pd = Pi; Ps =0)

3 ×10−1

Figure 6. Comparison with Davey-MacKay: improving the performance of
[4, Code D] (left) and [4, Code I] (right) using our MAP decoder, iterative
decoding, and an inner code with better Levenshtein distance spectrum.

and the increased decoding latency and complexity caused
by the augmented block size. Since the code performance is
undiminished, to simplify our analysis from this point onwards
we assume known frame start and end positions.
B. Comparison with Prior Art
We have already shown in [13] that the (symbol-level) MAP
decoder allows us to obtain better performance from the codes
of [4]. Further improvement can be obtained with iterative
decoding, as we show here. Additionally, the flexibility of
TVB codes allows us to obtain codes that perform better
at the same size and/or rate. In the following, we simulate
channel conditions Pi = Pd ; Ps = 0 in order to compare with
published results.
For low channel error rates, consider [4, Code D], listed as
P1 in Table III. We compare the previously published result
with a MAP decoding of the same code (N1a) in Fig. 6. As
shown in [13], the MAP decoder improves the performance
of this code even after the first iteration; additional iterations
improve the result further. At the same overall code rate and
block size we can improve the performance further by designing an inner TVB code with a better Levenshtein distance
spectrum (N1b). We repeat the process at higher channel
error rates for [4, Code I], listed as P2 in Table III. Again,
compared to the published result, a MAP decoding of the same
code (N2a) improves performance even after the first iteration,
also in Fig. 6. Additional iterations improve the result, but
the difference in this case is less pronounced. Replacing the
inner code with one of the same size but a better Levenshtein
distance spectrum (N2b) improves performance further.
As we have already discussed in Section II-A, the marker
codes given by Ratzer [5] can also be cast as TVB codes.
In [5] binary outer LDPC codes were used. To use a binary
outer code with our MAP decoder, the bitwise APPs can
be obtained from the q-ary symbol APPs by marginalizing
over the other bits [21, p. 326]; these are then passed to the
decoder for the binary outer code. In this case, for a binary

10−2

P3 [serial]
P3 [iterative]
N3 [1 iter]
N3 [20 iter]
P4 [10 iter]
N4 [5 iter]
P5 [10 iter]
N5 [20 iter]

10−3

10−4

10−5 −2
10

10−1

Channel Error Event Probability (Pd = Pi; Ps =0)

100

Figure 7. Comparison with Ratzer and with Mansour & Tewfik: demonstrating
the equivalence of our MAP decoder on [5, Code D], with and without iterative
decoding, and improving performance on [11, Codes T2, T4] at the same
overall code rate, using inner codes with improved Levenshtein distance in
concatenation with LDPC outer codes.

outer code we expect the performance of the concatenated
code to be identical, whether the inner code is decoded with
the bit-level (MAP) decoder of [5] or with our symbol-level
decoder. We show this in Fig. 7 for [5, Code D], listed as
P3 in Table III, in comparison with an almost-identical code
(N3) using our MAP decoder. It is important to highlight that
decoding marker codes as TVB codes provides no material
advantage; in fact, a cost is paid in complexity for doing
so. We do not propose or expect that marker codes will be
decoded as TVB codes. However, there is value in showing
that marker codes can be decoded as TVB codes with no loss
in performance. Specifically, this allows us to compare the
structure of marker codes with other constructions, within the
same context.
Finally, in Fig. 7 we compare with the more recent turbo
codes of [11, Codes T2, T4], respectively listed as P4 and P5
in Table III, with concatenated systems of the same overall
rate, using a TVB inner code and an LDPC outer code. It can
be seen that our concatenated systems outperform the codes of
[11], significantly at lower channel error rates, and somewhat
less so at higher channel error rates.
IX. C ONCLUSIONS
In this paper we have considered TVB codes, which generalize a number of previous codes for synchronization errors.
We discussed the applicable design criteria for TVB codes,
expressing some previously published codes as TVB codes
and showing that the greater flexibility of TVB codes allows
improved constructions. For example, our (7, 8, 4) TVB code
achieves a SER of 10−4 at a Pi , Pd that is almost two orders of
magnitude higher than a marker or distributed marker code of
the same size, and slightly better than our earlier SEC codes.
We also considered a number of important issues related
to a practical implementation of the corresponding MAP
decoder. Specifically, we have given an expression for the

13

expected distribution of drift between transmitter and receiver
due to synchronization errors, with consideration for practical
concerns when evaluating this expression. We have shown how
to determine an appropriate choice for state space limits based
on the drift probability distribution. The decoder complexity
under given channel conditions is then expressed as a function
of the state space limits used. For a given state space, we have
also given a number of optimizations that reduce the algorithm
complexity with no further loss of decoder performance. The
proposed speedups, which are independent of the TVB code
construction, result in a considerable reduction in complexity
of almost two orders of magnitude for typical code sizes and
channel conditions. For code constructions with appropriate
mathematical structure we expect to be able to replace the
receiver metric, which considers each possible transmitted
codeword, with a faster soft-output algorithm. Next, we have
considered the practical problem of stream decoding, where
there is no prior knowledge of the received frame boundary
positions. In doing so we have also shown how an appropriate choice of decoder parameters allows stream decoding to
approach the performance when frame boundaries are known,
at the expense of some increase in complexity.
Finally, practical comparisons of TVB codes with earlier
constructions were given, showing that TVB code designs can
in fact achieve improved performance. Even compared to the
state of the art codes of [11], the TVB codes presented here
1
achieve a FER of 10−3 at 24% higher Pi , Pd for a rate- 10
3
code, and at 84% higher Pi , Pd for a rate- 14 code. We expect
further improvements to the codes shown here to be possible,
particularly by co-designing optimized outer codes. However,
a detailed treatment of the design process is beyond the scope
of this paper, and will be the subject of further work.
R EFERENCES
[1] F. F. Sellers, “Bit loss and gain correction code,” IRE Trans. Inf. Theory,
vol. IT-8, pp. 35–38, 1962.
[2] V. I. Levenshtein, “Binary codes capable of correcting deletions, insertions and reversals,” Sov. Phys. Doklady, vol. 10, no. 8, pp. 707–710,
1966.
[3] R. G. Gallager, “Sequential decoding for binary channels with noise and
synchronization errors,” Massachusetts Inst. of Tech. Lexington Lincoln
Lab, Tech. Rep. 2502, Oct. 27th, 1961.

[4] M. C. Davey and D. J. C. MacKay, “Reliable communication over
channels with insertions, deletions, and substitutions,” IEEE Trans. Inf.
Theory, vol. 47, no. 2, pp. 687–698, 2001.
[5] E. A. Ratzer, “Marker codes for channels with insertions and deletions,”
Annals of Telecommunications, vol. 60, pp. 29–44, Jan. 2005.
[6] F. Wang, D. Fertonani, and T. M. Duman, “Symbol-level synchronization
and LDPC code design for insertion/deletion channels,” IEEE Trans.
Commun., vol. 59, no. 5, pp. 1287–1297, May 2011.
[7] T. Swart, H. Ferreira, and M. dos Santos, “Using parallel-interconnected
Viterbi decoders to correct insertion/deletion errors,” in 7th AFRICON
Conference in Africa, vol. 1, Sep. 2004, pp. 341–344.
[8] M. Schlauweg, D. Profrock, and E. Muller, “Correction of insertions and
deletions in selective watermarking,” in IEEE Intern. Conf. on Signal
Image Technology and Internet Based Systems (SITIS), 2008, Nov. 30th–
Dec. 3rd, 2008, pp. 277–284.
[9] M. Mansour and A. Tewfik, “Convolutional decoding in the presence
of synchronization errors,” IEEE J. Sel. Areas Commun., vol. 28, no. 2,
pp. 218–227, Feb. 2010.
[10] M. F. Mansour and A. H. Tewfik, “Convolutional decoding in the
presence of synchronization errors,” IEEE J. Selected Areas in Commun.,
vol. 28, no. 2, pp. 218–227, Feb. 2010.
[11] ——, “A turbo coding scheme for channels with synchronization errors,”
IEEE Trans. Commun., vol. 60, no. 8, pp. 2091–2100, Aug. 2012.
[12] H. Mercier, V. Bhargava, and V. Tarokh, “A survey of error-correcting
codes for channels with symbol synchronization errors,” IEEE Commun.
Surveys Tuts., vol. 12, no. 1, pp. 87–96, First Quarter 2010.
[13] J. A. Briffa, H. G. Schaathun, and S. Wesemeyer, “An improved
decoding algorithm for the Davey-MacKay construction,” in Proc. IEEE
Intern. Conf. on Commun., Cape Town, South Africa, May 23–27, 2010.
[14] J. A. Briffa and H. G. Schaathun, “Improvement of the Davey-MacKay
construction,” in Proc. IEEE Intern. Symp. on Inform. Theory and its
Applications, Auckland, New Zealand, Dec. 7–10, 2008, pp. 235–238.
[15] V. Buttigieg and J. A. Briffa, “Codebook and marker sequence design for
synchronization-correcting codes,” in Proc. IEEE Intern. Symp. Inform.
Theory, St. Petersburg, Russia, Jul. 31–Aug. 5, 2011.
[16] J. A. Briffa, “A GPU implementation of a MAP decoder for synchronization error correcting codes,” IEEE Commun. Lett., vol. 17, no. 5,
pp. 996–999, May 27th 2013.
[17] L. R. Bahl and F. Jelinek, “Decoding for channels with insertions,
deletions, and substitutions with applications to speech recognition,”
IEEE Trans. Inf. Theory, vol. 21, no. 4, pp. 404–411, Jul. 4, 1975.
[18] L. C. Perez, J. Seghers, and D. J. Costello, Jr., “A distance spectrum
interpretation of turbo codes,” IEEE Trans. Inf. Theory, vol. 42, no. 6,
pp. 1698–1709, Nov. 1996.
[19] G. Ferrari and K. M. Chugg, “Linear programming-based optimization
of the distance spectrum of linear block codes,” IEEE Trans. Inf. Theory,
vol. 49, no. 7, pp. 1794–1800, 2003.
[20] M. C. Davey, “Error-correction using low-density parity-check codes,”
Ph.D. dissertation, University of Cambridge, 1999.
[21] D. J. C. MacKay, Information Theory, Inference, and Learning Algorithms. Cambridge University Press, 2003.

