Decoding of raptor codes
View Patent ↗There are provided a method and apparatus for decoding Raptor code. The apparatus includes a decoder for decoding a sequence of packets representative of a sequence of encoding symbols. The decoder at least partially recovers at least some lost or corrupted packets of the sequence using Raptor code.
1. An apparatus, comprising:
a decoder for decoding a sequence of packets representative of a sequence of encoding symbols,
wherein said decoder at least partially recovers at least some lost or corrupted packets of the sequence using Raptor code, and said decoder constructs a linear system of equations based on the encoding symbols, the linear system of equations represented by
[
{
0
⋮
0
}
S
{
0
⋮
0
}
H
{
E
[
I
0
]
⋮
E
[
I
M
-
1
]
}
]
=
[
(
H
LDPC
)
S
×
Κ
I
S
×
S
0
S
×
H
(
H
Half
)
H
×
(
Κ
+
S
)
I
H
×
H
(
H
~
LT
)
M
×
L
]
︸
B
·
[
C
[
0
]
C
[
1
]
⋮
C
[
L
-
1
]
]
,
wherein E represents the encoding symbols with indexes {I 0 , I 1 , . . . , I M-1 }, M represents a number of the encoding symbols, C[0], C[1], . . . C[L−1] represent intermediate symbols to be encoded into the sequence of packets, K represents a number of source symbols which correspond to a subset of the intermediate symbols when using non-systematic Raptor code or correspond to a subset of the encoding symbols when using systematic Raptor code, S represents Low Density Parity Check symbols generated from the intermediate symbols, H LDPC represents a matrix used to generate the Low Density Parity Check symbols, H represents half symbols generated from the intermediate symbols, H Half represents a matrix used to generate the half symbols, {tilde over (H)} LT represents a matrix for generating the encoding symbols, I S×S represents an identity matrix of dimension S×S, 0 S×H represents a zero matrix of dimension S×H, I H×H represents an identity matrix of dimension H×H, B represents a matrix, and L represents a number of the intermediate symbols,
wherein said decoder converts the matrix B into an upper triangulation matrix, and
wherein said decoder performs a trace-back operation to recover at least some of the intermediate symbols, represented by [C[p 0 ], C[p 1 ], . . . , C[p w-1 ]] T , where p i denotes an index of a particular one of the at least some intermediate symbols, W denotes a number of the at least some intermediate symbols, 0≦p i ≦L, and W<L, and computes lost or corrupted source symbols, corresponding to the lost or corrupted packets, from the at least some intermediate symbols, using:
[
E
[
0
]
E
[
1
]
⋮
E
[
L
-
1
]
⋮
]
=
H
LT
·
[
C
[
0
]
C
[
1
]
⋮
C
[
L
-
1
]
]
,
when a conversion of the matrix B into the upper triangulation matrix fails.
2. The apparatus of claim 1 , wherein said decoder converts the matrix B into the upper triangulation matrix using a Gaussian elimination method.
3. The apparatus of claim 1 , wherein said decoder performs the trace-back operation only when a rank of the matrix B is greater than a pre-specified threshold.
4. The apparatus of claim 1 , wherein said decoder performs a trace-back operation to obtain a subset of intermediate symbols corresponding to the encoding symbols, and computes lost or corrupted source symbols, corresponding to the at least some lost or corrupted packets, from the subset of intermediate symbols.
5. A method, comprising:
decoding a sequence of packets representative of a sequence of encoding symbols,
wherein said decoding step at least partially recovers at least some lost or corrupted packets of the sequence using Raptor code, and said decoding step constructs a linear system of equations based on the encoding symbols, the linear system of equations represented by
[
{
0
⋮
0
}
S
{
0
⋮
0
}
H
{
E
[
I
0
]
⋮
E
[
I
M
-
1
]
}
]
=
[
(
H
LDPC
)
S
×
Κ
I
S
×
S
0
S
×
H
(
H
Half
)
H
×
(
Κ
+
S
)
I
H
×
H
(
H
~
LT
)
M
×
L
]
︸
B
·
[
C
[
0
]
C
[
1
]
⋮
C
[
L
-
1
]
]
,
wherein E represents the encoding symbols with indexes {I 0 , I 1 , . . . , I M-1 }, M represents a number of the encoding symbols, C represents source symbols to be encoded into the sequence of packets, K represents a number of the source symbols, S represents Low Density Parity Check symbols generated from the source symbols, H LDPC represents a matrix used to generate the Low Density Parity Check symbols, H represents half symbols generated from the source symbols, H Half represents a matrix used to generate the half symbols, {tilde over (H)} LT represents a matrix for generating the encoding symbols, I S×S represents an identity matrix of dimension S×S, 0 S×H represents a zero matrix of dimension S×H, I H×H represents an identity matrix of dimension H×H, B represents a matrix, and L represents a number of intermediate symbols,
wherein said decoding step converts the matrix B into an upper triangulation matrix,
wherein said decoding step performs a trace-back operation to recover at least some of the intermediate symbols, represented by [C[p 0 ], C[p 1 ], . . . , C[p w-1 ]] T , where p i denotes an index of a particular one of the at least some intermediate symbols, W denotes a number of the at least some intermediate symbols, 0≦p i ≦L, and W<L, and computes lost or corrupted source symbols, corresponding to the lost or corrupted packets, from the at least some intermediate symbols, using:
[
E
[
0
]
E
[
1
]
⋮
E
[
L
-
1
]
⋮
]
=
H
LT
·
[
C
[
0
]
C
[
1
]
⋮
C
[
L
-
1
]
]
,
when a conversion of the matrix B into the upper triangulation matrix fails.
6. The method of claim 5 , wherein said decoding step converts the matrix B into the upper triangulation matrix using a Gaussian elimination method.
7. The method of claim 5 , wherein said decoding step performs the trace-back operation only when a rank of the matrix B is greater than a pre-specified threshold.
8. The method of claim 5 , wherein said decoding step performs a trace-back operation to obtain a subset of intermediate symbols corresponding to the encoding symbols, and computes lost or corrupted source symbols, corresponding to the at least some lost or corrupted packets, from the subset of intermediate symbols.