Pulse or digital communications – Systems using alternating or pulsating current – Plural channels for transmission of a single pulse train
Reexamination Certificate
1999-05-25
2001-02-20
Chin, Stephen (Department: 2734)
Pulse or digital communications
Systems using alternating or pulsating current
Plural channels for transmission of a single pulse train
C375S265000, C375S341000, C714S792000, C714S794000
Reexamination Certificate
active
06192084
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates to a soft output decoding method and apparatus for convolutional codes, applied with advantage to, for example, a satellite broadcast reception device. More particularly, it relates to a soft output decoding device in which the probability information is stored on a recording medium a length not less than a truncated length and in which updating of the probability information within the truncation length and computations of the soft output outside the truncated length are executed in parallel to enable high-speed operations.
2. Description of the Related Art
As a decoding method for minimizing the symbol error ratio following decoding of the convolutional codes, there is known a BCJR algorithm from Bahl, Cocke, Jelinek and Raviv, “Optimal Decoding of Linear Codes for Minimizing Symbol Error Rate”, IEEE Trans. Information. Theory, Vol. 1T-20, pp. 284 to 287, March 1974. In the BCJR algorithm, it is not each symbol, but the likelihood of each symbol, that is outputted as the decoding result. This output is termed soft output.
Research is being conducted towards reducing the symbol error rate by using soft outputs as decoded output of the inner code of the conjugated code or as outputs of each reiteration of the iterative decoding method. As a decoding method, suited to this purpose, a BCJR algorithm is stirring up notice.
The contents of the BCJR algorithm are hereinafter explained in detail.
The BCJR algorithm outputs the likelihood of each symbol, instead of outputting each symbol, as a decoding result. The BCJR algorithm is used when convolutional encoding the digital information is convolutional-encoded by a convolutional encoder and the resulting data string obtained on convolutional encoding is observed over a non-storage communication route.
M states (transition states) representing the contents of shift registers of a convolutional encoder are expressed as m(0, 1, . . . M/1). The state at time t is S
t
, an input at t is I
t
, an output at time t is X
t
, and an output sequence is X
t
t′
=X
t
, X
t+1
, . . . , X
t′
. The transition probability between respective states p
t
(m m′) is represented by the following equation (1):
p
t
(
m|m′
)=
Pr{S
t
=m|S
t−1
=m′}
(1)
It is noted that Pr{A|} is a conditional probability of occurrence of A, under a condition that an event B has occurred, while Pr{A;B} is a probability of occurrence of both A and B. It is also assumed that the convolutional codes by the convolutional encoder starts with the state S
0
=0 and outputs X
1
&tgr;
to terminate at S
&tgr;
=0.
The noisy non-storage communication route receives an output X
1
&tgr;
as an input and outputs Y
1
&tgr;
. It is assumed that an output sequence Yt
t′
=Y
t
, Y
t+1
, . . . Y
t′
. Meanwhile, the transition probability of the non-storage communication route can be defined, for all t (1≦t≦&tgr;), by a function R(·|·) satisfying the following equation (2):
Pr
{
Y
1
′
❘
X
1
′
}
=
∑
j
=
1
t
R
(
Y
j
❘
X
j
)
(
2
)
.
Therefore, if the probability &lgr;
t
is defined as in the following equation (3):
λ
t
=
Pr
{
it
=
1
❘
Y
1
τ
}
Pr
{
i
t
=
0
❘
Y
1
τ
}
(
3
)
this probability &lgr;
t
represents the likelihood of the input information at time t when Y
1
&tgr;
is received, such that this probability &lgr;
t
is the soft output to be found.
The BCJR algorithm defines the probabilities &agr;
t
, &bgr;
t
and &ggr;
t
as indicated by the following equations (4) to (6):
&agr;
t
(
m
)=
Pr{S
t
=m; Y
1
t
} (4)
&bgr;
t
(
m
)=
Pr{Y
t+1
&tgr;
|S
t
=m}
(5)
&ggr;
t
(
m′m,i
)=
Pr{S
t
=m;Y
t
;i
t
=i|S
t−1
=m′}
(6)
The contents of &agr;
t
, &bgr;
t
and &ggr;
t
are explained with reference to
FIG. 1
which illustrates the relation between the respective probabilities. It is noted that &agr;
t−1
corresponds to the probability of passing through respective states at time t−1, as computed based on a reception word as from the encoding starting state S
0
=0, while &bgr;
t
corresponds to the probability of passing through respective states at time T as computed in the reverse sequence to the chronological sequence based on the reception word as from the encoding end state S&tgr;=0, and &ggr;
1
corresponds to the reception probability of respective branches in transition through respective states at time t as computed based on the reception word and the input probability at time t.
With the aid of &agr;
t
, &bgr;
t
and &ggr;
t
, the soft output &lgr;
t
can be represented by the following equation (7):
λ
t
=
∑
m
=
0
M
-
1
∑
m
′
=
0
M
-
1
α
t
-
1
(
m
′
)
γ
t
(
m
′
,
m
,
1
)
β
t
(
m
)
∑
m
=
0
M
-
1
∑
m
′
=
0
M
-
1
α
t
-
1
(
m
′
)
γ
t
(
m
′
,
m
,
0
)
β
t
(
m
)
(
7
)
.
It is noted that, for t=1, 2, . . . , &tgr;, the following equation (8) holds:
α
t
(
m
)
=
∑
m
′
=
0
M
-
1
∑
i
=
0
1
α
t
-
1
(
m
′
)
γ
t
(
m
′
,
m
,
i
)
(
8
)
.
where &agr;
0
(0)=1, &agr;
0
(m)=0(m≠0).
Similarly, the following equation (9):
β
t
(
m
)
=
∑
m
′
=
0
M
-
1
∑
i
=
0
1
β
t
+
1
(
m
′
)
χ
t
+
1
(
m
′
,
m
,
i
)
(
9
)
holds for t=1, 2, . . . , &tgr;−1, where &bgr;
&tgr;
(0)=1, &bgr;
&tgr;
(m)=0 (m≠0).
For &ggr;
t
, the following equation (10) holds:
&ggr;
t
(
m′, m, i
)=
P
t
(
m|m′
)
R
(
Y
t
, X
) in case of transition from m′ to m for an input i (X being its output);
and
&ggr;
t
(
m′, m, i
)=0 in case of non-transition from m′ to m for the input i (10)
Based on the above equation, the BCJR algorithm finds the soft output &lgr;
t
in accordance with the following sequence (a) to (c):
(a) each time Y
t
is received, &agr;
t
(m), &ggr;
t
(m′, m, i) is computed using the equations (8) and (10);
(b) after reception of the entire sequence Y
1
&tgr;
, &bgr;
t
(m) is computed for respective states m for the totality of time points t, using the equation (9); and
(c) &agr;
t
, &bgr;
t
and &ggr;
t
, computed at (a) and (b), are substituted into the equation (7) to compute the soft output &lgr;
t
at each time point t.
Meanwhile, the above-described BCJR algorithm suffers from the problem that the volume of computation is considerable because of the product computations involved and that continuous data cannot be received because of the necessity of terminating the codes.
In order to combat these problems, a Max-Log-BCJR algorithm and a log-BCJR algorithm have been proposed as techniques for diminishing the computation volume in Robertson, Villebrun and Hoeher, “A Comparison of Optimal and Sub-Optimal MAP Decoding Algorithms Operating in the Domain”, in IEEE Int. Cof. On Communications, pp. 1009 to 1013, June 1995, while the SW-BCJR algorithm for performing sliding window processing has been proposed as a technique for receiving continuous data in Benedetto and Montorsi, “Soft-Output Decoding Algorithm in Iterative Decoding of Turbo Codes”, TDA Progress Report 42-124, February 1996.
The contents of these algorithms are hereinafter explained.
First, the contents of the Max-Log-BCJR algorithm and the log-BCJR algorithm are explained.
The Max-Log-BCJR algorithm represents the probabilities &agr;
t
, &bgr;
t
and &ggr;
t
, &lgr;
t
by a modulo 2 logarith
Hattori Masayuki
Miyauchi Toshiyuki
Chin Stephen
Ha Dac V.
Limbach & Limbach L.L.P.
Sony Corporation
LandOfFree
Soft output decoding apparatus and method for convolutional... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Soft output decoding apparatus and method for convolutional..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Soft output decoding apparatus and method for convolutional... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2565155