Viterbi algorithm outputting a plurality of most probable sequences in descending probability order

0001The invention relates to a Maximum Likelihood Sequence Estimation (MLSE) algorithm, and more specifically to a method according to the introduction of claim 1.

0002Generally, the communication on a memory containing channel becomes more difficult due to the unintentional analog convolution coding, which is due to the interaction between symbols. In this context the term "memory containing" may be understood so that the value of respective bits in a sequence or in a bit string in a digital transmission system depend on the bits preceding and/or succeeding it, i.e. on the "memory" of the system. A memory containing channel is intentionally constructed in the case of convolution codes. The memory of the system is utilized to make the transmission more reliable.

0003Usually efforts are made to remove the unintentional interaction on the transmission path, e.g.. with linear or non-linear filtering, the receiver "seeing" a channel almost without memory.

0004A receiver for data transmission systems containing memory is in a known way based on the MLSE algorithm. With the aid of the MLSE algorithm such a sequence or a bit string is found, which with the greatest probability is the same as the transmitted sequence.

0005In an ideal MLSE algorithm the signal formed through all possible symbol strings (combinations of symbols or bits) is tested against the signal actually received. Thereby it is assumed that the response of the channel is known and/or measured. It is possible to select the "best" symbol string with different criteria, which minimize the error probability of the decision.

0006The use of the MLSE algorithm is in practice limited by the fact that when the length of the symbol string increases, the number of possible combinations to be tested will increase exponentially.

0007Efforts have been made to solve this problem by taking into account the length of the channel, whereby the calculation requirements are exponentially proportional to the length of the channel instead of to the length of the sequence. The Viterbi algorithm is a well known algorithm of this kind. As an example of a system where the MLSE-algorithm may be used, the pan-European GSM system may be mentioned, in which it is possible with the Viterbi algorithm to solve the coding for the error correction and the unintentional coding due to the radio transmission path. With the Viterbi algorithm it is possible to find efficiently the best possible symbol sequence or that sequence, at which the ideal MLSE algorithm also would arrive.

0008Xnown methods, that are less complicated than the complete MLSE and the Viterbi algorithm, have a disadvantage of poorer performance than the MLSE.

0009So called look-up algorithms are also known, with which the Viterbi algorithm can be extended so that it will be able to find the most probable sequence, and in addition a desired number of sequences in descending probability order. As an example of a look-up algorithm of this type there may be mentioned Henry S. Thomson, "Active Chart Parsing/Best First Enumeration of Parts in a Lattice", European Conference on Speech Communication and Technology, Paris, September 1989.

0010On the other hand, in transmission systems it is known to use error monitoring or error detection to detect, and possibly to correct, an error in a received sequence. Several error detecting functions are known; they are generally of a block type and based on the use of a polynomial. A generic name for these is CRC (Cyclic Redundancy Check) - in colloquial language we talk about parity checks.

0011Proceedings of the Global Telecommunications Technology and Exhibition - Globecom 89, 27-30 Nov. 1989, Dallas, vol. 3, 2989, New York, IEEE pages 1680-1686; J. Hagenauer et al.: "A Viterbi Algorithm with Soft-Decision Outputs and its Applications" describes a method to extend the standard Viterbi algorithm in a way that it produces high quality soft decisions while the standard Viterbiy algorithm only gives hard decisions. This SOVA algorithm is widely known and at least a simplified version of it has been implemented in the future Pan-European Mobile Radio System (GSM) . A GSM product always includes an equalizer to cope with multipath propergation. The SOVA algorithm can be used in GSM applications if the channel equalizer is based on the Viterbi algorithm. Then the equalizer can provide high quality soft output information for the convolutional code decoder, which is usually also implemented with Viterbi algorithm.

0012The aim of the invention is to improve the efficiency of known receiving methods, or to increase the efficiency of the Viterbi algorithm in a system, in which the channel contains memory, and in which error detection is used.

0013This is accomplished in accordance with the invention by the characterizing features of claim 1, by combining the Viterbi algorithm with a function, with which the most probable sequence and in addition several sequences in descending probability order are found, of which the best or error-free sequence is selected with the aid of error detection.

0014The method according to the invention will improve the efficiency of known methods. A similar result could be conceived to be achieved by trying out all bit combinations and then testing the result with an error detection function. However, such a procedure would result in calculating requirements increasing exponentially with the length of the MLSE algorithm sequence. On the other hand the success probability of the error detection function is less than 1, and thus the number of combinations to be tested has to be limited, so that the success probability would not decrease to a value too small (whereby several other sequences along with the correct one could pass the correctness test). These details of the invention are explained below.

0015In a method according to the invention a limit for a sufficient error detection reliability is set by adapting the operating point so that the number of errors for the sequences to be tested can be detected with a great probability (100 %).

0016The method according to the invention utilizes known methods (the extended Viterbi algorithm and error detection) by combining them in a new way. The prior art Viterbi algorithm, for example, produces lots of information (information on many sequences or bit strings with different probabilities), of which only one piece of information is utilized (the most probable sequence). In accordance with the present invention the information produced by the Viterbi algorithm is not "lost", but it is stored (into the memory of the equipment using it). The next best sequences are found from the stored information, and from all found sequences the best is found using error detection. As an advantage this will limit calculation requirements; in this method they increase linearly when the length of the symbol string increases (and not exponentially as in the ideal MLSE algorithm).

0017The method according to the invention may be applied in general to memory containing systems, which include an error detecting or error monitoring function. The method is not restricted to any specified algorithm or error detection function; some methods have been mentioned above only as illustrative examples.

0018On the basis of the above description and the inventive idea in the enclosed claims it is a simple task for a person skilled in the art to implement present method, he being able to use electronic circuits known per se for the realization.

0019The invention is preferably applied to digital radio telephone systems and to (mobile) telephone devices and base station equipment in these systems.