Signal Processing - March 2017 - 99
30
Conventional Code
Optimal Code
25
Recovery Delay (Packets)
packets to recover them. In the special case of the burst-erasure channel with burst length of B and R = 1/2, this results
in a delay of T = 2B.
One can significantly improve upon the performance of
traditional FEC over burst-erasure channels. Such constructions are referred to as streaming codes in this article. Unlike
traditional FEC, they do not force simultaneous recovery
of all the source packets. Instead, the construction of parity checks is such that the older source packets with earlier
deadlines are recovered before the later source packets. The
streaming codes discussed in this article are illustrated in
Figure 3. The minimum delay achieved by this method is
T = B, when R = 1/2.
In Figure 4, we provide a comparison between traditional
FEC and streaming codes. We sketch the maximum correctable burst length on the x axis and the resulting delay for different codes on the y axis. The rate of all codes is fixed to
R = 1/2. As we discussed, when the burst length equals B,
the minimum delay for traditional FEC is T = 2B, which is
shown by the blue line in the figure. The associated region
T $ 2B is shaded light blue. In contrast, the minimum delay
achieved by streaming codes is T = B and is shown by the red
line. Thus, the longer the burst length, the higher will be the
gain provided by streaming codes. As we will see, the codes
achieving minimum delay over burst loss channels are sensitive to other erasure patterns. Thus, in practice one must develop robust extensions that are also resilient to isolated erasure
patterns. Such codes will require slightly larger delays than
T = B and will achieve a performance in the light-red region
shown in Figure 4. We discuss three such constructions-
shifted RLC codes, concatenated codes, and dual-delay
codes-in the respective eponymous sections below. The corresponding generalizations to arbitrary rates are discussed in
the "General Code Constructions" section.
20
Region for
Achievable Delays Using
Traditional FEC
ble
va es
e
i
d
h
Ac Co
or ing
f
ion am
eg Stre
R
l
na ing
itio s Us
d
Ad elay
D
Infeasible
Region
15
10
5
2
4
8
10 12 14 16
Burst Length (Packets)
18
20
FIGURE 4. The achievable delays for erasure recovery of different burst
lengths using FEC at rate 1/2. The solid red line shows the minimum delay
that can be achieved for a given burst length. The delay below this threshold cannot be achieved by any code. The blue region shows the delay
achieved by traditional FEC codes that perform simultaneous recovery of
the source packets. Streaming codes that perform sequential recovery can
achieve delay in the red region. By tracing the regions marked by the green
line, we can see that at a recovery delay of T = 11 and R = 0.5, it is possible to achieve an optimal burst length recovery of 11 packets versus the
conventional approach, which can only recover six packets. Conversely,
for recovering a burst length of 11, the traditional codes require a delay of
21 packets while the optimal code only requires a delay of 11 packets.
In Figure 5, a (4, 2) RS code is applied to each group of two
consecutive source packets to generate two parity-check packets. For example, in the first block we generate
RS codes
(4, 2) RS Code
(s [0], s [1])
An (n, k) block code operates on k source packets and generates n > k packets. Hence, the rate of an (n, k) code is given by
k/n. Systematic codes are a class of block codes where the first
k packets of the codeword are the source packets, whereas the
last n - k are parity-check packets. RS codes [12], [16] are the
most commonly used block codes. These codes belong to the
class of maximum distance separable (MDS) codes, which
guarantee the recovery of the maximum number of packet
losses for a given redundancy. An (n, k) RS code can recover
up to n - k erased packets in any codeword of length n.
While an (n, k) block code does not directly fit into the
streaming setup, it can be easily adapted, as discussed below.
The stream of source packets is logically split into segments,
each of size k. An (n, k) block code is then applied to each
segment to generate n - k parity-check packets. These
parity-check packets are then transmitted together with the
source packets in the next block of k packets. This construction is particularly simple for R = 1/2, which is the case
treated in this section. For the case of general rates, we refer
the reader to [17].
6
(s [0], s [1], p [2], p [3]) .
(3)
The resulting parity-check packets (p [2], p [3]) are transmitted
in the next block by appending them to s [2] and s [3], respectively. The resulting channel packets are x [2] = (s [2], p [2])
and x [3] = (s [3], p [3]) . More generally, for the group of
source packets (s [2i], s [2i + 1]) , a (4, 2) RS code is applied
to generate parity checks p [2i + 2] and p [2i + 3], which are
transmitted along with the source packets at times t = 2i + 2
and t = 2i + 3, respectively.
A longer (6, 3) RS code can be applied in an analogous
fashion by considering groups of three source packets and generating three parity-check packets, which must be transmitted
in the next block of three source packets.
We now discuss the error-correction properties based on
three following cases.
1) Single isolated loss: Consider a channel that introduces a
single isolated erasure, i.e., N = 1. The (4, 2) RS code can
recover the missing source packet with a delay of no more
than T = 2 packets. For example, if x [0] is lost, then the
associated source packet is recovered as soon as p [2] is
IEEE Signal Processing Magazine
|
March 2017
|
99
Table of Contents for the Digital Edition of Signal Processing - March 2017
Signal Processing - March 2017 - Cover1
Signal Processing - March 2017 - Cover2
Signal Processing - March 2017 - 1
Signal Processing - March 2017 - 2
Signal Processing - March 2017 - 3
Signal Processing - March 2017 - 4
Signal Processing - March 2017 - 5
Signal Processing - March 2017 - 6
Signal Processing - March 2017 - 7
Signal Processing - March 2017 - 8
Signal Processing - March 2017 - 9
Signal Processing - March 2017 - 10
Signal Processing - March 2017 - 11
Signal Processing - March 2017 - 12
Signal Processing - March 2017 - 13
Signal Processing - March 2017 - 14
Signal Processing - March 2017 - 15
Signal Processing - March 2017 - 16
Signal Processing - March 2017 - 17
Signal Processing - March 2017 - 18
Signal Processing - March 2017 - 19
Signal Processing - March 2017 - 20
Signal Processing - March 2017 - 21
Signal Processing - March 2017 - 22
Signal Processing - March 2017 - 23
Signal Processing - March 2017 - 24
Signal Processing - March 2017 - 25
Signal Processing - March 2017 - 26
Signal Processing - March 2017 - 27
Signal Processing - March 2017 - 28
Signal Processing - March 2017 - 29
Signal Processing - March 2017 - 30
Signal Processing - March 2017 - 31
Signal Processing - March 2017 - 32
Signal Processing - March 2017 - 33
Signal Processing - March 2017 - 34
Signal Processing - March 2017 - 35
Signal Processing - March 2017 - 36
Signal Processing - March 2017 - 37
Signal Processing - March 2017 - 38
Signal Processing - March 2017 - 39
Signal Processing - March 2017 - 40
Signal Processing - March 2017 - 41
Signal Processing - March 2017 - 42
Signal Processing - March 2017 - 43
Signal Processing - March 2017 - 44
Signal Processing - March 2017 - 45
Signal Processing - March 2017 - 46
Signal Processing - March 2017 - 47
Signal Processing - March 2017 - 48
Signal Processing - March 2017 - 49
Signal Processing - March 2017 - 50
Signal Processing - March 2017 - 51
Signal Processing - March 2017 - 52
Signal Processing - March 2017 - 53
Signal Processing - March 2017 - 54
Signal Processing - March 2017 - 55
Signal Processing - March 2017 - 56
Signal Processing - March 2017 - 57
Signal Processing - March 2017 - 58
Signal Processing - March 2017 - 59
Signal Processing - March 2017 - 60
Signal Processing - March 2017 - 61
Signal Processing - March 2017 - 62
Signal Processing - March 2017 - 63
Signal Processing - March 2017 - 64
Signal Processing - March 2017 - 65
Signal Processing - March 2017 - 66
Signal Processing - March 2017 - 67
Signal Processing - March 2017 - 68
Signal Processing - March 2017 - 69
Signal Processing - March 2017 - 70
Signal Processing - March 2017 - 71
Signal Processing - March 2017 - 72
Signal Processing - March 2017 - 73
Signal Processing - March 2017 - 74
Signal Processing - March 2017 - 75
Signal Processing - March 2017 - 76
Signal Processing - March 2017 - 77
Signal Processing - March 2017 - 78
Signal Processing - March 2017 - 79
Signal Processing - March 2017 - 80
Signal Processing - March 2017 - 81
Signal Processing - March 2017 - 82
Signal Processing - March 2017 - 83
Signal Processing - March 2017 - 84
Signal Processing - March 2017 - 85
Signal Processing - March 2017 - 86
Signal Processing - March 2017 - 87
Signal Processing - March 2017 - 88
Signal Processing - March 2017 - 89
Signal Processing - March 2017 - 90
Signal Processing - March 2017 - 91
Signal Processing - March 2017 - 92
Signal Processing - March 2017 - 93
Signal Processing - March 2017 - 94
Signal Processing - March 2017 - 95
Signal Processing - March 2017 - 96
Signal Processing - March 2017 - 97
Signal Processing - March 2017 - 98
Signal Processing - March 2017 - 99
Signal Processing - March 2017 - 100
Signal Processing - March 2017 - 101
Signal Processing - March 2017 - 102
Signal Processing - March 2017 - 103
Signal Processing - March 2017 - 104
Signal Processing - March 2017 - 105
Signal Processing - March 2017 - 106
Signal Processing - March 2017 - 107
Signal Processing - March 2017 - 108
Signal Processing - March 2017 - 109
Signal Processing - March 2017 - 110
Signal Processing - March 2017 - 111
Signal Processing - March 2017 - 112
Signal Processing - March 2017 - 113
Signal Processing - March 2017 - 114
Signal Processing - March 2017 - 115
Signal Processing - March 2017 - 116
Signal Processing - March 2017 - 117
Signal Processing - March 2017 - 118
Signal Processing - March 2017 - 119
Signal Processing - March 2017 - 120
Signal Processing - March 2017 - 121
Signal Processing - March 2017 - 122
Signal Processing - March 2017 - 123
Signal Processing - March 2017 - 124
Signal Processing - March 2017 - Cover3
Signal Processing - March 2017 - Cover4
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_201809
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_201807
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_201805
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_201803
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_201801
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_1117
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0917
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0717
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0517
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0317
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0117
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_1116
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0916
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0716
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0516
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0316
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0116
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_1115
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0915
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0715
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0515
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0315
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0115
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_1114
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0914
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0714
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0514
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0314
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0114
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_1113
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0913
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0713
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0513
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0313
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0113
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_1112
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0912
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0712
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0512
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0312
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0112
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_1111
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0911
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0711
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0511
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0311
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0111
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_1110
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0910
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0710
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0510
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0310
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0110
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_1109
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0909
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0709
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0509
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0309
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0109
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_1108
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0908
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0708
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0508
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0308
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0108
https://www.nxtbookmedia.com