Pulse or digital communications – Receivers – Particular pulse demodulator or detector
Reexamination Certificate
2000-05-25
2003-12-23
Bocure, Tesfaldet (Department: 2631)
Pulse or digital communications
Receivers
Particular pulse demodulator or detector
C714S794000
Reexamination Certificate
active
06668026
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a decoding method and apparatus suitable for maximum likelihood decoding of a convolutional code, and more particularly, to a decoding method and apparatus suitably usable in a satellite broadcasting, etc.
2. Description of the Related Art
Recently, researches have been made to minimize the symbol error probability by soft-output of decoded code of concatenated codes and iterative output in the iterative decoding method and decoding methods suitable for acquisition of a soft-output are sought with a great interest. The soft output Viterbi algorithm disclosed in “A Viterbi Algorithm with Soft-Decision Outputs and Its Application, Hagenauer and Hoeher, Proc. IEEE Global Telecoim. Conf GLOBECOM, pp. 47.1.1-47.1.7, November 1989” is one of the decoding methods for soft output during decoding of an convolutional code. In the Viterbi algorithm with soft-decision outputs, each symbol is not output as a result of decoding but a likelihood of each symbol is output. Such an output is called a soft-output. What the soft-output Viterbi algorithm (will be referred to as “SOVA” hereinafter) is will be described.
As shown in
FIG. 1
, digital information is convolved by a convolutional encoder
101
, an output from the convolutional encoder
101
is supplied to a decoder
103
via a memoryless channel
102
with noises, and the output is decoded by the decoder
103
.
First, M states (transition) of a shift register in the convolutional encoder
101
are represented by m (
0
,
1
, . . . , M−1), a state at a time t is represented by St, an input at the time t is represented by it, an output at the time t is represented by Xt, and an output sequence is represented by Xtt′=Xt, Xt+1, . . . , Xt′.
The convolutional coding will start at a state SO=0 and end at a state ST=0 with output of X
1
T. The memoryless channel
102
with noises is supplied with X
1
T, and outputs Y
1
T. It is assumed here that Ytt′ Yt, Yt+1, . . . , Yt′. The transition probability of the memoryless channel
102
with noises is defined by R(·|·) which will be as given by the expression (1) for all t (1≦t≦T).
Pr
{
Y
1
t
❘
X
1
t
}
=
∏
j
=
1
t
R
(
Y
j
❘
X
j
)
(
1
)
A likelihood of input information &lgr;t is defined by the expression (2):
λ
t
=
Pr
{
i
t
=
1
❘
Y
1
T
}
Pr
{
i
t
=
0
❘
Y
1
T
}
(
2
)
The input information likelihood &lgr;t is a one at the time t when Y
1
T has been received. It is a soft-output to be determined. Practically, however, the value of &lgr;t itself is less frequently determined than its natural logarithmic value log &lgr;t. In the following description, the log &lgr;t will be referred to as “logarithmic likelihood ratio”.
With the SOVA, the likelihood is not directly determined but a likelihood of a path not selected at each time of the process of selection in the Viterbi decoding, in which a most likely path being sequence most likely to a received code sequence is derived, is used to determine a likelihood of a decoded bit of the most likely path, thereby determining the likelihood of each input information by approximation.
Assuming that the most likely path is PtML, the path not selected as a result of the comparison with the most likely path at a time j is Ptj, a bit entered at the time t of the path Pt is taken as I[Pt, t], the likelihood of the path Pt when Y
1
T is received is Pr(Pt|Y
1
T) and a set of the paths Ptj is &rgr;, a definition is made as given by the expression (3):
&rgr;
0
(
t
)={
Pr:Pt&egr;&rgr;, I[Pt, t|≠I[Pt
ML
, t]}
(3)
With the SOVA, the logarithmic likelihood ratio of the decoded bit at the time t is computed by approximation using the expression (4). Thus, the logarithmic likelihood ration of the decoded bit can be determined as a path-metric difference during Viterbi decoding.
log
max
{
Pr
{
Pt
❘
Y
1
T
}
:
Pt
∈
ρ
0
(
t
)
}
Pr
{
Pt
ML
Y
1
T
}
=
log
{
max
{
Pr
{
Pt
❘
Y
1
T
}
:
Pt
∈
ρ
0
(
t
)
}
-
logPr
{
Pt
ML
❘
Y
1
T
}
(
4
)
Note that with the SOVA, the logarithmic likelihood ratio is computed as a likelihood of the most likely path in relation to the decoded bit, namely, in the form of the expression (5) or (6):
Decoded bit=0
→
Pr{i
t
=1
|Y
1
T
}/Pr{i
t
=0
|Y
1
T
}(=&lgr;
t
) (5)
Decoded bit=1
→
Pr{i
t
=0
|Y
1
T
}/Pr
{1
|Y
1
T
}(=1/&lgr;
t
) (6)
The SOVA algorithm will further be described below:
FIG. 2
shows the merging of paths in the state k at the time j. As shown, a path selected is represented by P
1
(k, j), and a path not selected is by P
2
(k, j). A state through which the path P
1
(k, j) passes at a time j−1 is represented by s
1
(k), a state through which the path P
2
(k, j) passes is represented by s
2
(k), and a path-metric difference between the paths P
1
(k, j) and P
2
(k, j) is represented by &Dgr;k(j). Bits decoded between the paths P
1
(k, j) and P
2
(k, j) at the time t are represented by I[P
1
(k, j), t] and I[P
2
(k, j), t], respectively, and the logarithmic likelihood ratio between the decoded bits of survivor paths in the state k when paths counted up to the time t have been selected is represented by L{circumflex over ( )}t(k, j).
Using the above notation, the decoding procedure with the SOVA will be as follows:
With the SOVA, all the times and states t and k are first initialized to have a logarithmic likelihood ration of L{circumflex over ( )}t(k,
0
).
Next, with the SOVA, operations given by the expressions (7) and (8) are made on all the states k and times t (t=1 to j) during path selection at each time j:
I[P
1
(
k, j
),
t]≠I[P
2
(
k, j
),
t]→L{circumflex over ( )}
t
(
k, j
)=min {
L{circumflex over ( )}
t
(
s
1
(
k
),
j
−1), &Dgr;
k
(
j
)} (7)
I[P
1
(
k, j
),
t]=I[P
2
(
k, j
),
t]→L{circumflex over ( )}
t
(
k, j
)=min {
L{circumflex over ( )}
t
(
s
1
(
k
),
j
−1) (8)
With the SOVA, assuming that the last time is T and the most likely state is k
0
, the logarithmic likelihood ratio being a last soft-output is determined as L{circumflex over ( )}t(k
0
, T).
When the SOVA is installed in a hardware, the hardware will be a SOVA decoder
110
architected as shown in FIG.
3
.
The SOVA decoder
110
includes a branch-metric computation circuit
111
to compute a branch-metric which is a Hamming distance between a received signal and path, an add compare select (ACS) circuit
112
to compare the branch-metric computed by the branch-metric circuit
111
with a state-metric being a cumulative sum of the preceding branch-metrics, a nonnalization circuit
113
to normalize a new state-metric signal s
113
output from the ACS circuit
112
, a state-metric memory circuit
114
to store a normalized state-metric signal s
114
output from the normalization circuit
113
, and a path memory and likelihood update circuit
115
supplied with path selection information s
116
, metric-difference information s
117
and a most likely state signal s
118
from the ACS circuit
112
to output a decoded data s
119
and logarithmic likelihood ratio s
120
.
When the SOVA decoder
110
is supplied with a received value Yt, a priory probability information log Pr(it=0) and log Pr(it=1) as s
111
, it will output the decoded data s
119
being a result of decoding and the logarithmic likelihood ratio s
120
, respectively.
When the branch-metric computation circuit
111
is supplied with a received value and a priory probability information s
111
, it computes a branch-metric of the
Bocure Tesfaldet
Frommer William S.
Frommer & Lawrence & Haug LLP
Sony Corporation
LandOfFree
Decoding method and apparatus does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Decoding method and apparatus, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Decoding method and apparatus will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3137168