Signal Processing - March 2017 - 100
noninteractive streaming applications.
received by the decoder. In contrast, the
The use of convolutional
However, since the focus of this article is
(6, 3) RS code can recover the missing
codes is more desirable
on FEC for interactive applications, ratesource packet with a worst-case delay of
than block codes, as it
less codes will not be suitable.
T = 3 packets.
enables the decoder to
2) Two isolated losses: Next, consider the
recover from shorter
case in which the channel introduces up
RLC codes
bursts with smaller delays. Together with block codes and rateless
to two isolated losses. For the (4, 2)
code, it can be seen that the worst-case
codes, convolutional codes [16], [18] form a
delay happens when x [0] and one of either x [1] or x [2] is
commonly implemented class of error-correcting codes. Such
codes have an inherent sequential encoding structure. At each
erased. The source packet s [0] can be recovered from
time instant t, an (n, k, m) convolutional code generates one
p [3], resulting in a delay of T = 3 packets. Similarly for
the (6, 3) code, the worst-case delay with two isolated losschannel packet x [t] of size n that is a causal combination of
es is T = 4. This will happen, for example, if x [0] and
the previous m source packets and the current packet-i.e.,
x [t] = ft (s [t - m], f, s [t - 1], s [t]) . The rate of such a code
x [3] are erased, in which case the decoder must wait for
is given by R = k/n, and its redundancy is 100 (n - k) /k% .
p [4] to recover s [0].
The code is said to be systematic if each channel packet x [t]
3) Burst-erasure channel: Finally, consider the case in
which the channel introduces a burst of length B = 3 .
contains the source packet s [t] -i.e., x [t] = (s [t], p [t]) ,
In particular, suppose that x [0], x [1], and x [2] are
where p [t] is the size n - k parity-check packet at time t.
erased. The (4, 2) RS code will not be able to recover
An important class of convolutional codes is linear, timeinvariant convolutional codes, where the parity-check packs [0] and s [1] , although s [2] can still be recovered
ets can be expressed as
from p [4] . In contrast, the (6, 3) RS code successfully
recovers all the erased source packets with a maximum
m
delay of T = 5.
p [t] = / s [t - i] ·H i ,
(4)
Generally speaking, longer block codes in the streaming
i =1
setup will correct from longer bursts but at the expense of
longer delay. However, the size of each block must be small
where m denotes the memory of the code and the matrices
because of the delay constraints. Such an approach signifiH i are of dimension k # n - k for each i = 1, f m. The sumcantly limits the error-correction capability. As we will see,
mation in (4) starts at i = 1 and not i = 0, i.e., p [t] does not
the use of convolutional codes is more desirable than block
combine s [t], because the packet erasure channel considered
codes, as it enables the decoder to recover from shorter bursts
will erase p [t] whenever s [t] is erased. Furthermore, when
with smaller delays, while longer bursts can be recovered with
x [t] is not erased, the systematic code will recover s [t]
longer delays. However, before discussing these, we briefly
directly without the need of p [t].
discuss rateless codes.
If the coefficients in the matrix H i are selected at random, then the codes are said to be RLC codes (see, e.g., [19]
and [20]). Such codes guarantee that, with high probability,
Rateless codes
each parity-check symbol provides an independent equation
RS codes exist over fields of sizes at least as large as the block
involving the source symbols. One can also construct the
length. Typical block lengths for RS codes are restricted to
matrices H i in a deterministic fashion to satisfy this propn # 255. Rateless codes (e.g., Luby transform codes [9] and
raptor codes [10]) are a class of binary codes that can support
erty. Such constructions also achieve the largest distance
considerably longer block lengths that achieve near-optimal
up to the code memory and are referred to as strongly MDS
error correction and are amenable to extremely efficient
codes (see, e.g., [21] and [22]). For simplicity, we will refer
decoding algorithms. This makes them a natural choice in
to all these constructions as RLC codes.
K
K
0ts
s[0]
1ts
2ts
s[1]
3ts
4ts
5ts
6ts
7ts
8ts
9ts
s[2]
s[3]
s[4]
s[5]
s[6]
s[7]
s[8]
s[9]
p[2]
p[3]
p[4]
p[5]
p[6]
p[7]
p[8]
p[9]
FIGURE 5. A (4, 2) RS code applied to a streaming setup. The parity-check packets p [2] and p [3] are generated from s [0] and s [1] but are sent in the
next block.
100
IEEE Signal Processing Magazine
|
March 2017
|
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