Soft output viterbi algorithm (SOVA) with error filters

Details Soft output viterbi algorithm (SOVA) with error filters Soft output viterbi algorithm (SOVA) with error filters

2001-01-10

2004-03-16

Chung, Phung M. (Department: 2133)

Error detection/correction and fault detection/recovery

Pulse or data error handling

Digital data error correction

C714S780000

Reexamination Certificate

active

06708308

ABSTRACT:

PARTIAL WAIVER OF COPYRIGHT
All of the material in this patent application is subject to copyright protection under the copyright laws of the United States and of other countries. As of the first effective filing date of the present application, this material is protected as unpublished material. However, permission to copy this material is hereby granted to the extent that the copyright owner has no objection to the facsimile reproduction by anyone of the patent documentation or patent disclosure, as it appears in the United States Patent and Trademark Office patent file or records, but otherwise reserves all copyright rights whatsoever.
CROSS-REFERENCE TO RELATED APPLICATIONS
Not Applicable
BACKGROUND OF THE INVENTION
1. Field of the Invention
The invention relates to a Soft Output Viterbi Algorithm. More particularly, the invention is a simplified method and apparatus for more easily computing and providing bit reliabilities in combination with a Viterbi algorithm on a processing unit.
2. The Prior Art
The Viterbi algorithm is used for detecting data possibly corrupted by noise in movement of data through communications or recording systems. The algorithm computes the most likely sequence written on the recording given the received noisy data. The output is consistent with some constraints on the sequences that are allowed to be written.
a. Ordinary SOVA
A channel trellis is a diagram defined by states and branches that describes the “ideal” sequence of outputs to a sequence of inputs. For instance, an Inter-Symbol Interference (ISI) channel trellis, determined by a linear channel impulse response such as Partial Response Class 4 (PR4), Extended Partial Response Class 4 (EPR4) or Extended
2
Partial Response Class 4 (E
2
PR4) describes the ideal response of such a channel to any possible sequence of binary Non-Return to Zero (NRZ) inputs.
For simplicity, an assumption is made that the trellis is a possibly “pruned” version of a standard ISI channel trellis diagram with memory v. The states are binary v-tuples, and for u=0 or 1, there is a branch from state (x
−v
. . . x
−1
) to (x
−v+1
. . . x
−1
u). Each branch has an input label (u) and output label (the ideal channel response to the input sequence (x
−v
. . . x
−1
u).
The “pruning” may be the consequence of a constraint (such as MTR) on the channel inputs designed to improve the performance of the detection process.
If the channel detector is designed to pass soft information to a code whose codewords are in some domain other than NRZ (e.g., NRZI, PR4), then the approach described here could be modified accordingly.
Naturally, an assumption is made that the ideal sequence of channel outputs is corrupted by a noise source. The Bahl, Cocke, Jelinek, Raviv (BCJR) algorithm, produces exact a posteriori probabilities (APP) for each bit, assuming that the noise is uncorrelated and data-independent (for instance, Additive White Gaussian Noise (AWGN)). These APP probabilities can be used as soft-decision inputs passed on to other modules in the detection/decoding process, such as a turbo decoder or low density parity check (LDPC) decoder.
Experimental results on test-stand data show that the BCJR algorithm, in conjunction with low density parity check codes, performs quite well—in spite of the fact that the test-stand noise is typically correlated and data-dependent. But the complexity of the BCJR algorithm may prove too costly for implementation.
SOVA (soft output Viterbi algorithm) is a method for producing approximate APP's at a lower computational cost than BCJR. The estimates produced by SOVA are based on Viterbi margins (i.e., differences between the metric of a survivor path and its non-surviving path in the Viterbi algorithm). SOVA was introduced by Hagenauer and Hoeher in “A Viterbi Algorithm with Soft Decision Outputs and its Applications”, Proceedings of Globecom, 1989, pp. 1680-1686.
b. Description of Algorithm
SOVA begins with an ordinary run of the Viterbi algorithm on a long block (of length N) of data. The branch metrics are ordinarily determined by the received channel sample r
j
and the ideal channel output w on the branch: ∥r
j
−w∥
2
; but prior information from previous LDPC iterations may be incorporated in the branch metrics (by adding a term of the form log p where p is the prior probability that the j-th data bit equals the branch input label).
At each bit position j, in between 1 and N, the Viterbi algorithm computes and outputs a detected data bit x
j
. As is well known this requires a delay equal to the so-called path memory, denoted M (typically, N will be much larger than M). SOVA requires an additional delay, denoted &Dgr;, within which one makes use of Viterbi margins.
At bit position j, after a delay of &Dgr;+M, the Viterbi detector will have detected data bits in positions up to j+&Dgr;. For each k=j+1, . . . , j+&Dgr;, the detected path up to position k will be a survivor path. As such, it will have at most one non-surviving (runner-up) path ending at the same state (it may have no such paths if the trellis has been pruned). Call this non-surviving path p
k
, and let m
k
denote the Viterbi margin (i.e., the difference between the metric of the detected path up to time k and the metric of P
k
) The algorithm is concerned only with those p
k
that would result in a different value for the j-th data bit, i.e.
(
p
k
)
j
≠x
j
.
Such a k is called j-qualified. So, for bit position j, Viterbi margins are computed only for those k that are j-qualified.
FIG. 1
illustrates a non-surviving path p
k
(
100
) for a j-qualified k as described in the prior art.
For the j-th bit position SOVA will output
ω
j
=
(
-
1
)
X
j
⁢
min
k
⁢
m
k
where the minimum runs over all j-qualified k such that j+1≦k≦j+&Dgr;. As shown in J. Hagenauer and E. Offer and L. Papke, “Iterative Decoding of Binary Block and Convolutional Codes”, IEEE Transactions on Information Theory, March, v.42, 1996, pp 429-445, this quantity is an approximation to the true APP log-likelihood:
ω
j
≈
log
⁢
(
P
(
x
j
⁢
&LeftBracketingBar;
r
j
)
P
(
x
_
j
⁢
&LeftBracketingBar;
r
j
)
)
where r
j
denotes the received sequence of samples up to time j+&Dgr;+M and {overscore (&khgr;
j
)}, denotes the binary complement of &khgr;
j
.
c. Access to the non-surviving path p
k
FIG. 2
illustrates a Soft Output Viterbi Algorithm Decoder (
200
) as described in the prior art. Signals are input into the decoder (
200
) from a channel (
202
). The signals pass through an equalizer (
204
) and into the primary decoding stages of the SOVA. The non-surviving path p
k
could be obtained from the Viterbi detector with a delay of time M. But then each state s and each i=1, I . . . , M, would require an enormous buffer to store all the non-surviving paths ending at state s at time slot k-i.
An alternative would be to use a second Viterbi detector (
212
), V
2
, operating with delay M (
210
) with respect to the first Viterbi detector (
206
), V
1
. Then V
1
(
206
) would provide the detected data path with delay M (
210
), and V
2
(
212
) would provide the non-surviving path p
k
. This is described as follows.
First, a buffer is needed, detected buffer (
208
) DB in
FIG. 2
, to store the last &Dgr; detected bits: x
k−&Dgr;+1
. . . x
k
. At time slot k+M, this buffer is updated by shifting one unit to the left and filling in the right-most position with the newly detected bit x
k
from V
1
(
206
). If &Dgr;≧v (i.e., the look-ahead is at least as large as the channel trellis memory), then the ending state s
k
of the detected path can be read directly from DB (
208
) and fed to V
2
(
212
). The differences between the Viterbi detectors V
1
(
206
) and V
2
(
212
) are:
1—V
2
(
212
) has path memory &Dgr; instead of M.
2—At time slot k+M, V
2
(
212
) computes all survivor paths ending at bit position k instead of k+M.
In all other respects, V
2
(
212
) operates ex

Affiliated with

Also associated with

Rating

Soft output viterbi algorithm (SOVA) with error filters 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 viterbi algorithm (SOVA) with error filters, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Soft output viterbi algorithm (SOVA) with error filters will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3190404