METHOD FOR DECODING DATA SIGNALS USING FIXED LENGTH DECISION WINDOWField of the invention The present invention relates, in general, to the decoding of the encoded data communication signals. More specifically, the present invention relates to an improved decoding method that utilizes a fixed length decision window.
BACKGROUND OF THE INVENTION FIGURE 1 illustrates a conventional digital communication system. The information source 10 supplies analogue or digital information to a source encoder 11 that encodes the information in a sequence of information x. A channel encoder 12 transforms the sequence of information x into a new sequence of information by efficiently introducing redundancy in the information sequence to improve the reliability of the transmission. The redundancy can be used, for example for the receiver to detect the error, correct the error in the receiver and to implement a request for automatic repetition, where the detection of an error by the receiver will automatically initiate a request for repeated transmission of the data. It will be appreciated that more redundancy is required to correct errors than to detect errors in a coded message. The modulator 13 receives the encoded sequence from the channel encoder 12 and generates the channel signals for transmission on a transmission channel 14 using standard modulation techniques such as amplitude, frequency, phase or pulse modulation. In general, transmission channel 14 will present noise or other deterioration, such as frequency or phase formation and a variety of fading characteristics. The digital demodulator 15 receives the signal transmitted on the transmission channel and demodulates the transmitted signal to produce an estimate of the coded information sequence. The channel decoder 16 then uses the estimate to reproduce the information sequence using the redundant bits supplied by the channel encoder 12. Finally, the source decoder 17 transforms the sequence of reconstructed information into a form suitable for the destination of the information 18. The channel encoder 12 usually introduces redundancy using one of two common methods: block coding or convolutional coding. A block code (n, k) transforms a block of k information bits into a code word of n bits by adding parity bits n-k (redundancy) according to a predetermined encoding rule. The n-bit code words are then transmitted over the communication channel. The rate or rate of code, R, is defined as R = k / n. The receiver estimates the original k information bits using the received sequence including the redundancy introduced by the parity bits n-k. The block codes are "without memory" because each code word of n bits sent by the decoder only depends on the information block of k bits present. Convolutional coding is usually done by organizing a bit stream of information in blocks of k-bits, and passing the blocks in a shift register. The stages of the shift register store up to v groups of k-bit blocks, and the stages are connected to the generators of the linear algebraic function. The outputs of the generator are selectively combined to produce an encoded n-bit output. Convolutional coding is not without memory, since each coded block depends only on the input of the k-bits block present in the shift register, but also on the previous message blocks v. In this way, the convolutional code has a memory of order v. The code rate R of a convolutional code is R = k / n, and the restriction length in the code is v + 1. Usually, k and n are small integers and redundancy is added by increasing the length of the shift register. The operation of convolutional encoders and decoders can be described by an interlacing diagram or a state or table diagram, as is well known in the art. Decoders, demodulators and other conventional digital communication system equipment usually use a Viterbi algorithm to estimate the transmitted signals that were encoded using convolutional codes, and to minimize the damage of the communication channel.The Viterbi algorithm generates an estimate of the maximum probability of a single transmitted data sequence searching for the shortest transition path through a sequence of possible states (an "interleaving"). The Viterbi algorithm in general can be described as a method in which all possible transmitted sequences are correlated with the received sequence, and then a "survivor" sequence is chosen based on the maximum correlation, that is, the route with the best "metric" to estimate the received sequence.The Viterbi algorithm can be improved by generating a reliability indicator for each estimated data bit. This may be the amplitude of the calculated data bit, for example. This improvement is generally known as "soft" information. If concatenated codes are used, the additional soft information can be used in the latest decoders to improve the operation of the system. Other modifications to the Viterbi algorithm are described in the European patent application 0 606 724 Al by Nill et al, and in "List and Soft Symbol Output Viterbi Algorithms: Extensions and Comparisons" Nill et al., IEEE Transaction on Communications, Vol. 43, No. 2/3/4, February / March / April 1995. Nill's publications describe a decoding method that uses smooth information and estimates the bits to produce a list of candidate sequences in descending order of probability. The list of candidate sequences can be used in later stages to determine the best estimate of the transmitted sequence. For example, a cyclic redundancy check (CRC), such as the one used in the GSM radio link protocol, can be used to verify the candidate sequences in the list by selecting the first candidate sequence that has the correct CRC information. . The operation of the system is improved allowing the correction of errors without having to retransmit the erroneous frames. The Nill method can be described in general as follows. The received symbols are decoded using the Viterbi algorithm to produce an estimate of the data sequence with greater probability, together with soft information (for example, a maximum probability value). Soft information is used to locate the bit of least probability (the weakest) in the sequence. Instead of choosing the best incoming transition route (for the state that shifts the weakest bit), an alternate incoming transmission route is determined by looking the other way in the Viterbi interlace. To generate the classified list of candidate sequences in order of descending probability, each of the first elements of the list has "a candidate for the element (l + l) th of the list." The element (l + l) th of the list is chosen as the candidate with the best cumulative metric.These steps are repeated until a sufficient number of alternatives have been created.Nill's method requires that all Viterbi interleaving be stored, rendering the Nill method useless for most of practical applications In the Viterbi algorithm, interleaving tends to converge after a certain amount of time.To use memory more efficiently, it would be desirable to store only a part of the interlace (a decision window). it would be desirable for a decoding scheme to be practically useful to offer improved performance over the Viterbi algorithm by allocating multiple data stream estimation without re want the storage of all the interlacing.
SUMMARY OF THE INVENTION The present invention overcomes the aforementioned problems, and provides other advantages by offering a method for decoding transmitted data signals using a fixed length decision window in which multiple transmission paths have converged into a single state. For each state in the decision window, a possible candidate for the second best sequence and associated soft value are determined and compared with a candidate stored for the second best sequence and the second best associated soft value. If the soft value (reliability indicator) associated with the possible candidate sequence is less than the second best soft value associated with the stored candidate sequence, and the possible candidate sequence and the best sequence generated by the Viterbi algorithm converge into a common state Within the decision window, the candidate candidate for the second best sequence replaces the stored candidate for the second best sequence. The method according to the present invention allows the previous smooth values and the best transition path to be discarded from the memory, so that it is not necessary to store all the interleaving to complete the decoding operation.
BRIEF DESCRIPTION OF THE DRAWINGS One. More complete understanding of the present invention can be obtained by reading the following detailed description of the preferred embodiments together with the accompanying drawings, in which like numerals indicate like elements, and in which: FIGURE 1 is a block diagram of a receiver in a conventional communication system in which it is possible to use the method of the present invention; FIGURE 2 is a diagram showing a representative decision window in a Viterbi interleaver according to an embodiment of the present invention; and FIGURE 3 is a flow chart describing the method according to an embodiment of the present invention.
DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS Referring now to FIGURE 2, a fixed length decision window of length w '' + w 'is shown. It can be seen that all upstream search sequences go through the S state. From this state it is possible to produce a possible candidate sequence according to the method of the present invention. The conventional Viterbi (AV) algorithm estimates the sequence of transmitted bits with the highest probability, in asense of probability. To generate a list of possible alternatives to this sequence, according to the present invention, the following additional information is generated or stored in the decoder: -The information about the routes excluded by the AV is stored. This is done for all states between t == k and t = k + w ', relative to FIGURE 2. The necessary memory is, therefore, w' * N * w '' bits. The decision of which routes should be stored as the second best routes (a decision not made in the conventional AV) is done at t = k '+ w'. The second best route that enters each state in the state column S at t = k + w 'is stored until the column of the fixed-length decision window has moved past t = k. -A measure of reliability, also known as a "soft" measure, is stored for each state between t = k and t = k + w '. This measure of reliability indicates the certainty of the displaced bit of this state. The reliability measure can be calculated, for example, as the absolute difference of the cumulative metric between two incoming routes originating the same state at time t = k + w '. A route corresponds to a symbol "1" being moved, the other route corresponds to a "0" being moved. Each time the decision window is moved, the next best routes and soft values are determined by the new column (the column on the right)in FIGURE 2). -A MINSOFT threshold value is generated and used to determine if it is necessary to generate a possible candidate for an alternative sequence. To generate alternative sequences within the decision window, the conventional AV is performed until the decision window is filled with estimated symbols. After w '+ w' 'bit times (starting at 0), the decision window is filled and alternative possible sequences can be obtained. In this way, to generate a possible alternative for the best sequence at this time it is possible to exchange the portion of the sequence estimated by the AV shown in bold in FIGURE 2 with an alternative sequence. The conditions for this are: - The bit to be deleted by moving the state S has a soft value lower than the current threshold value MINSOFT. That is, this bit is less reliable than other bits previously decoded. The state S is determined from the best route in time t = k + w '; and -The sequence estimated by the AV (shown in FIGURE 2) and the alternative sequence must be mixed again within the decision window, that is, before t = kw '', to achieve the appropriate "termination" of the alternative sequence. If these conditions are met, a possible alternative sequence should be constructed. This is done by choosing the other route that gives origin to the state S (shown by the dotted line in FIGURE 2) and then scanning the inverse the interleaved MINSOFT is updated to the soft value of the state S and the previous candidate for the second best sequence it is replaced by the newly found sequence. When the possible alternative sequence is constructed, it is time to make a new bit decision. The decision window moves (to the right in FIGURE 2) to make room for the newly received bit. The length of the decision window is constant whether a possible alternative sequence is generated or not. In relation to FIGURE 2, the decision window now contains the interlace between t = k-w '+ l and t = k + w' + l. The state S can now be found in the column at t = k + l. The newly explained scheme is performed again to verify if a sequence can be generated between t = k + l and t = k-w '' + l (in relation to the bits in FIGURE 2). These steps are performed until the interleaving is completed, that is, all the bits in the present burst have been decoded. To generate two estimates of the transmitted sequence, the conventional AV produces the best estimate, and the second best estimate is generated according to the present invention. To generate a list of some number (L) of estimated sequences, the algorithm described above can be expanded to handle a list of possible candidates for alternative sequences where the candidate sequences are stored together with their corresponding MINSOFT values. When the decision is made whether or not to generate a new candidate sequence, the list is checked if the soft value of the S state is less than any of the stored MINSOFT values. If this is the case, the generation is done and the newly found candidate is inserted in the list. The insertion is done to keep the list stored in terms of the increasing MINSOFT values. That is, the preference list is stored according to the descending probabilities. The decision window is moved and the procedure is repeated. Now in relation to FIGURE 3, a flowchart describing the decoding method according to one embodiment of the present invention is shown. The method can be instrumented in a decoder, demodulator, equalizer or other similar device to determine a sequence of data with greater probability from a sequence of encoded data, received. The flow chart begins at step 100, in which the fixed-length decision window shown in FIGURE 2 is updated (moved), and conventional AV decoding is performed to determine the best transition path. As shown in FIGURE 2, the decision windowit includes a state in which multiple transition paths have converged on a state at time t = k, and extend from time t = k forward for a first time or bit shift w 'and backward for a second time or bit offset w ''. In step 101 it is determined if more than w '' bits have been received by the decoder. Since no alternative sequence differs from the best sequence by up to w '' bits, no additional information needs to be stored for the first w '' bits. In step 102 a possible next best transition route, and the associated soft information (reliability indicator), is determined for each state at the current time 1: = k + w '. This is done by exploring the interleaving inversely to determine the best and second best sequence for each state at t = k + w '. The soft value is calculated as the absolute value of (metric 0-metric 1), where metric 0 and metric 1 are measures of cumulative amplitude. In step 103 it is determined whether the decision window is complete. If so, in step 104 the state S is selected (state which is exploring in reverse the interleaving from the state at t = k + w 'which has the best reliability indicator). In step 105 the soft information (reliability indicator) SOFT of the state S determined in step 104 iscompares with a MINSOFT threshold reliability indicator; if SOFT is not less than MINSOFT, the process returns to step 100 and the fixed length decision window is shifted and a new better S state is determined. It will be appreciated that if a list of L sequences are estimated, they exist (L-1). ) MINSOFT values. If SOFT is less than MINSOFT, the method continues to step 106, in which it is determined whether the best and the second best route have been combined at some point before the end of the decision window defined by time k, the displacement of the time w 'and the length w' 'of the next best route. If the best and possible candidate for the next best routes have not been combined (ie, the sequences differ by more than w '' bits), the process returns to step 100, and the fixed-length decision window is moved and determines a new S state. If the best and possible candidate for the next best routes have been combined, the MINSOFT value is set equal to the SOFT value, the former next best route is discarded from memory, and in step 107 it is stored the new next best length route w ''. The method described above can be instrumented, for example, in a channel decoder of a GSM system, such as the system shown in FIGURE 1. The method can be encoded in a computer codereadable for the machine on a suitable storage medium, such as a computer disk. A common decision window will have a length of, for example, 31 bits of a displacement w 'of approximately 14 bits. It will be appreciated that it is possible to use other lengths of the decision window and displacements w '. Throughout the above description, the terms "route" and "sequence" have been used interchangeably. Although the above description has included multiple details and specificities, it should be understood that these are merely illustrative and are not considered as limitations of the present invention. Numerous modifications will be readily apparent to those skilled in the art, which do not depart from the spirit and scope of the invention, as defined by the following claims and their legal equivalents.