Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
1999-03-24
2002-05-14
Decady, Albert (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
C714S794000, C714S796000
Reexamination Certificate
active
06389574
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention concerns the field of digital transmissions.
We consider the transmission of digital data, i.e. in the form of symbols taking a finite number ND of values d
0
, . . . ,d
ND−1
, and discrete in time: it is therefore a digital symbol sequence D
m
(m=0,1,2,etc.) belonging to a defined alphabet {d
i
, 0≦i<ND}.
The role of the detector, in terms of the present invention, is to provide estimations of successive symbols D
m
in a sequence to be detected from an “encoded” observation signal available at a receiver. The “encoder”, which provides the observation signal representing the sequence to be detected to the detector must be taken in the most general sense: it can be seen as a black box, developed by the designer or not. It may be an error correcting encoder (in this case, the observation signal is also a digital signal, and the “detector” is a correcting decoder), or the compound of a correcting encoder-modulator-propagation channel-demodulator (the observation signal is then a digital sequence marred by errors), or else the more straightforward compound of a modulator-propagation channel (the “detector” is then a demodulator).
The detector has hard inputs if the observation signal which it processes is a digital sequence of symbols with discrete values, and soft inputs if the observation signal is a sequence of sampled and quantified values, or of discrete estimations accompanied by respective weights representing the degrees of confidence vested in these estimations.
The detector has soft outputs if the symbol estimations which it delivers are accompanied by respective weights representing the degrees of confidence vested in these estimations, and hard outputs if it simply delivers discrete estimations.
In real transmission systems, it is common to process signals having a memory, i.e. the signal segment carrying the data at a given moment depends not only on this data at the same moment, but also on the past data or past signal segments. If this memory verifies certain properties, particularly the fact that a trellis exists describing the production process of the observation signal, then the receiver can determine the data symbols carried by the observation signal in the sense of maximum likelihood, by means of the Viterbi algorithm (see G. D. Forney, Jr., “The Viterbi Algorithm”, Proc. IEEE, Vol.61, No.3, March 1973, pages 268-278) or the MAP (Maximum A Posteriori) algorithm also set out in the article by G. D. Forney.
Different versions of the MAP algorithm are described in the following references: K. Abend and B. D. Fritchman, “Statistical Detection for Communication Channels with Intersymbol Interference”, Proc. IEEE, Vol.58, No.5, May 1970, pages 779-785; R. W. Chang and J. C. Hancock, “On Receiver Structures for Channels Having Memory”, IEEE Trans. on Information Theory, Vol.IT-12 No.4, October 1966, pages 463-468; and L. R. Bahl et al, “Optimal Decoding of Linear Codes for Minimizing Symbol Error Rate”, IEEE Trans. on Information Theory, Vol.IT-20, March 1974, pages 284-287.
It also happens that “encoders” COD
1
,COD
2
, . . . ,COD
N
are cascaded in transmission systems (for example several error correcting encoders, or one or several error correcting encoders followed by a modulator and a propagation channel), often with intermediate interleaving operations. In this case (concatenated memory system), the receiver under consideration may consist of a cascade of elementary decoder/detectors DEC
N
,DEC
N−1
, . . . ,DEC
1
. This receiver is optimal in the sense of maximum likelihood if the decoder/detectors DEC
p
have soft outputs (for p>1) and soft inputs, whereby the decoder/detector DEC
p
(p>1) associates with each discrete estimation of a decoded symbol D
m
of the sequence to be detected (this sequence is the one delivered by the encoder COD
p−1
) a weight represented by the likelihood equal or proportional to the logarithm of the ratio between the probability that the symbol D
m
of the unknown sequence does in fact correspond to its estimation provided by the decoding and the probability that the symbol D
m
is different from its estimation, the probabilities in question being conditional probabilities, with the knowledge of the available observation signal. In this case, the soft outputs of each decoder/detector constitute the “observation signals” for the next decoder/detector, and the likelihood data is not lost.
The advantage of the Viterbi algorithm is that its implementation by a circuit or a processor entails no great difficulties. given the straightforwardness of the operations involved: multiplications, additions/subtractions, comparisons. Furthermore, the regularity of the trellis often enables the use of tricks for programming or organising the memory, which make the algorithm even easier to implement. This explains why its use is today widespread in different categories of detector. But, in its traditional version, it does not provide the likelihood of the discrete estimations which it delivers, so that it does not allow optimal processing in the case of a concatenated memory system.
On the other hand, the MAP algorithm, in essence, provides the likelihoods of the symbols that it estimates, but poses serious difficulties of implementation: exponential quantity calculations, need to know the noise variance, sensitivity to errors in this variance, problems of digital analysis for its very low values etc.
For the concatenated memory systems mentioned above, several methods have been proposed for weighting the estimations produced by a Viterbi detector. Examples of such methods, referred to as “SOVA” (Soft Output Viterbi Algorithm), are:
a method consisting in taking as the likelihood of an estimation the difference between the metric accumulated at a node of the trellis corresponding to this estimation and the metric of the best path corresponding to a different discrete estimation (see C. Berrou et al, “A Low Complexity Soft-Output Viterbi Decoder Architecture”, Proc. ICC'93, Geneva, May 1993). This straightforward technique is commonly employed, but very sub-optimal;
the Hagenauer algorithm, described in J. Hagenauer and P. Hoeher, “A Viterbi Algorithm with Soft-Decision Outputs and its Applications”, Proc. Globecom'89, Dallas, November 1989, pages 47.1.1-47.1.7;
the Battail algorithm, described in U.S. Pat. No. 4,328,582;
the optimal (OSA) or sub-optimal (SSA) SOVA described in Y. Li, B. Vucetic and Y. Sato, “Optimum Soft-Output Detection for Channels with Intersymbol Interference”, IEEE Trans. on Information Theory, Vol. IT-41, No.3, May 1995, pages 704-713.
Except for the OSA, each of these SOVA methods bring a degradation of performance compared with the MAP algorithm.
The Hagenauer, Battail and Li, Vucetic and Sato algorithms are similar to the MAP in that they carry out the calculations in the probability domain. As a result, they involve the calculation of exponentials, which makes their implementation by means of circuits or processors unattractive, even if the exponential quantities are replaced by approximations.
A primary object of the present invention is to propose a SOVA method of reasonable complexity, allowing an evaluation of likelihoods of symbols estimated by a Viterbi detector, and which brings little error probability degradation compared with the optimal case of the MAP algorithm.
SUMMARY OF THE INVENTION
This invention thus proposes a method for detecting a discrete symbol sequence from an observation signal the production of which can be described by means of a trellis of NE states E
e
(0≦e<NE) and NB branches B
b
(0≦b<NB), each branch having a start state and an arrival state among the NE states and being associated with a single Q-uplet of discrete symbols, Q being an integer at least equal to 1,
the trellis comprising paths each formed by a succession of branches, each path having a metric defined by a sum of elementary metrics relative to the successive branches which form it, and being associated wi
Belveze Fabrice
Chancel Florence
De'cady Albert
Lamarre Guy
Matra Nortel Communications
Trop Pruner & Hu P.C.
LandOfFree
Method for detecting a discrete symbol sequence from an... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method for detecting a discrete symbol sequence from an..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for detecting a discrete symbol sequence from an... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2909996