Reduced complexity turbo decoding scheme
A reduced complexity turbo decoding scheme combines elements from two MAP (Maximum a posteriori) algorithms, namely a LogMAP algorithm and a max-LogMAP algorithm. Forward and backward recursive metrics are computed in accordance with the max-LogMAP algorithm, while output extrinsic LLR (Log Likelihood Ratio) values are computed in accordance with the LogMAP algorithm.
1. In an iterative decoder, an iterative decoding method for decoding received digital data elements representing source data elements coded according to a turbo coding scheme, the iterative decoding method comprising:
computing a set of branch metrics for the received digital data elements based upon at least one received digital data element;
computing a set of forward recursive metrics based upon the set of branch metrics according to an approximation:
A
k
(
m
)
=
log
[
α
k
(
m
)
]
=
max
m
′
{
Γ
(
u
k
,
c
k
,
m
′
,
m
)
+
A
k
-
1
(
m
′
)
}
-
H
A
k
;
computing a set of backward recursive metrics based upon the set of branch metrics according to an approximation:
B
k
(
m
′
)
=
log
[
β
k
(
m
′
)
]
=
max
m
{
Γ
(
u
k
,
c
k
,
m
′
,
m
)
+
B
k
+
1
(
m
)
}
-
H
B
k
;
and
computing a set of output extrinsic Log Likelihood Ratio (LLR) values based upon the set of backward metrics and the set of forward metrics according to an equation:
Λ
(
d
k
)
=
log
[
∑
e
:
u
(
e
)
=
d
k
=
+
1
ⅇ
{
A
k
-
1
(
m
′
)
+
Γ
1
(
c
k
,
m
′
,
m
)
+
B
k
(
m
)
}
]
-
log
[
∑
e
:
u
(
e
)
=
d
k
=
0
ⅇ
{
A
k
-
1
(
m
′
)
+
Γ
0
(
c
k
,
m
′
,
m
)
+
B
k
(
m
)
}
]
;
and
outputting the set of output extrinsic Log Likelihood Ratio (LLR) values.
2. The iterative decoding method of claim 1 , wherein computing the set of backward recursive metrics comprises:
using a sliding window for processing less than the entirety of received digital data elements.
3. The iterative decoding method of claim 2 , wherein using a sliding window for processing less than the entirety of received digital data elements comprises:
initializing the set of backward recursive metrics with equal probabilities.
4. The iterative decoding method of claim 2 , wherein using a sliding window for processing less than the entirety of received digital data elements comprises:
initializing the set of backward recursive metrics with the set of forward recursive metrics.
5. Apparatus for decoding received digital data elements representing source data elements coded according to a turbo coding scheme, the apparatus comprising:
branch metric logic operably coupled to compute a set of branch metrics for the received digital data elements based upon at least one received digital data element;
forward recursive metric logic operably coupled to compute a set of forward recursive metrics based upon the set of branch metrics according to an approximation:
A
k
(
m
)
=
log
[
α
k
(
m
)
]
=
max
m
′
{
Γ
(
u
k
,
c
k
,
m
′
,
m
)
+
A
k
-
1
(
m
′
)
}
-
H
A
k
;
backward recursive metric logic operably coupled to compute a set of backward recursive metrics based upon the set of branch metrics according to an approximation:
B
k
(
m
′
)
=
log
[
β
k
(
m
′
)
]
=
max
m
{
Γ
(
u
k
,
c
k
,
m
′
,
m
)
+
B
k
+
1
(
m
)
}
-
H
B
k
;
extrinsic logic operably coupled to compute a set of output extrinsic Log Likelihood Ratio (LLR) values based upon the set of backward metrics and the set of forward metrics according to an equation:
Λ
(
d
k
)
=
log
[
∑
e
:
u
(
e
)
=
d
k
=
+
1
ⅇ
{
A
k
-
1
(
m
′
)
+
Γ
1
(
c
k
,
m
′
,
m
)
+
B
k
(
m
)
}
]
-
log
[
∑
e
:
u
(
e
)
=
d
k
=
0
ⅇ
{
A
k
-
1
(
m
′
)
+
Γ
0
(
c
k
,
m
′
,
m
)
+
B
k
(
m
)
}
]
;
and
output logic operably coupled to output the set of output extrinsic Log Likelihood Ratio (LLR) values.
6. Apparatus according to claim 5 , wherein the backward recursive metric logic comprises:
logic for using a sliding window for processing less than the entirety of received digital data elements.
7. Apparatus according to claim 6 , wherein the logic for using a sliding window for processing less than the entirety of received digital data elements comprises:
logic for initializing the set of backward recursive metrics with equal probabilities.
8. Apparatus according to claim 6 , wherein the logic for using a sliding window for processing less than the entirety of received digital data elements comprises:
logic for initializing the set of backward recursive metrics with the set of forward recursive metrics.
9. An apparatus for decoding received digital data elements representing source data elements coded according to a turbo coding scheme, the apparatus comprising:
a first iterative decoder;
a second iterative decoder;
an interleaver operably coupled to receive first output extrinsic Log Likelihood Ratio (LLR) values from the first iterative decoder and to provide interleaved output extrinsic Log Likelihood Ratio (LLR) values to the second iterative decoder; and
a deinterleaver operably coupled to receive second output extrinsic Log Likelihood Ratio (LLR) values from the second iterative decoder and to provide deinterleaved output extrinsic Log Likelihood Ratio (LLR) values to the first iterative decoder, wherein each iterative decoder comprises:
branch metric logic operably coupled to compute a set of branch metrics for the received digital data elements based upon at least one received digital data element;
forward recursive metric logic operably coupled to compute a set of forward recursive metrics based upon the set of branch metrics according to an approximation:
A
k
(
m
)
=
log
[
α
k
(
m
)
]
=
max
m
′
{
Γ
(
u
k
,
c
k
,
m
′
,
m
)
+
A
k
-
1
(
m
′
)
}
-
H
A
k
;
backward recursive metric logic operably coupled to compute a set of backward recursive metrics based upon the set of branch metrics according to an approximation:
B
k
(
m
′
)
=
log
[
β
k
(
m
′
)
]
=
max
m
{
Γ
(
u
k
,
c
k
,
m
′
,
m
)
+
B
k
+
1
(
m
)
}
-
H
B
k
;
extrinsic logic operably coupled to compute a set of output extrinsic Log Likelihood Ratio (LLR) values based upon the set of backward metrics and the set of forward metrics according to an equation:
Λ
(
d
k
)
=
log
[
∑
e
:
u
(
e
)
=
d
k
=
+
1
ⅇ
{
A
k
-
1
(
m
′
)
+
Γ
1
(
c
k
,
m
′
,
m
)
+
B
k
(
m
)
}
]
-
log
[
∑
e
:
u
(
e
)
=
d
k
=
0
ⅇ
{
A
k
-
1
(
m
′
)
+
Γ
0
(
c
k
,
m
′
,
m
)
+
B
k
(
m
)
}
]
;
and
output logic operably coupled to output the set of output extrinsic Log Likelihood Ratio (LLR) values.
10. Apparatus according to claim 9 , wherein the backward recursive metric logic comprises:
logic for using a sliding window for processing less than the entirety of received digital data elements.
11. Apparatus according to claim 10 , wherein the logic for using a sliding window for processing less than the entirety of received digital data elements comprises:
logic for initializing the set of backward recursive metrics with equal probabilities.
12. Apparatus according to claim 10 , wherein the logic for using a sliding window for processing less than the entirety of received digital data elements comprises:
logic for initializing the set of backward recursive metrics with the set of forward recursive metrics.
13. An apparatus comprising a digital storage medium having embodied therein a program for controlling a programmable logic device to decode received digital data elements representing source data elements coded according to a turbo coding scheme, the program comprising:
branch metric logic programmed to compute a set of branch metrics for the received digital data elements based upon at least one received digital data element;
forward recursive metric logic programmed to compute a set of forward recursive metrics based upon the set of branch metrics according to an approximation:
A
k
(
m
)
=
log
[
α
k
(
m
)
]
=
max
m
′
{
Γ
(
u
k
,
c
k
,
m
′
,
m
)
+
A
k
-
1
(
m
′
)
}
-
H
A
k
;
backward recursive metric logic programmed to compute a set of backward recursive metrics based upon the set of branch metrics according to an approximation:
B
k
(
m
′
)
=
log
[
β
k
(
m
′
)
]
=
max
m
{
Γ
(
u
k
,
c
k
,
m
′
,
m
)
+
B
k
+
1
(
m
)
}
-
H
B
k
;
extrinsic logic programmed to compute a set of output extrinsic Log Likelihood Ratio (LLR) values based upon the set of backward metrics and the set of forward metrics according to an equation:
Λ
(
d
k
)
=
log
[
∑
e
:
u
(
e
)
=
d
k
=
+
1
ⅇ
{
A
k
-
1
(
m
′
)
+
Γ
1
(
c
k
,
m
′
,
m
)
+
B
k
(
m
)
}
]
-
log
[
∑
e
:
u
(
e
)
=
d
k
=
0
ⅇ
{
A
k
-
1
(
m
′
)
+
Γ
0
(
c
k
,
m
′
,
m
)
+
B
k
(
m
)
}
]
;
and
output logic programmed to output the set of output extrinsic Log Likelihood Ratio (LLR) values.
14. The apparatus of claim 13 , wherein the programmable logic device comprises one of:
a microprocessor;
a digital signal processor; and
a field programmable gate array.
15. The apparatus of claim 13 , wherein the backward recursive metric logic comprises:
logic for using a sliding window for processing less than the entirety of received digital data elements.
16. The apparatus of claim 15 , wherein the logic for using a sliding window for processing less than the entirety of received digital data elements comprises:
logic for initializing the set of backward recursive metrics with equal probabilities.
17. The apparatus of claim 15 , wherein the logic for using a sliding window for processing less than the entirety of received digital data elements comprises:
logic for initializing the set of backward recursive metrics with the set of forward recursive metrics.