Abstract:
Improved Viterbi decoding of radio signals of the type calculating a metric increment ##EQU1## wherein λ k  is calculated at time intervals indexed by k, i is a data bit position index, y is a received value, x is a coded bit of a predetermined sequence, and a is a fading factor, uses a metric addition B k  according to the equation ##EQU2## where B k  is a function of the quantity 
     
       u.sub.k L.sub.k =log.sub.10  P(u.sub.k =+1)/P(u.sub.k =-1)!. 
     
     If the channel is binary symmetrical, B k  =u k  L k  /L 0k  where L 0k  =log (1-P 0k )/P 0k  ! and P 0k  is the binary symmetrical channel error probability. If the channel is a gaussian and fading channel then B k  =u k  L k  / (E s  /N 0 ) log 10  e! where E s  /N 0  is the channel signal-to-noise ratio and log 10  e is approximately equal to 0.434.

Description:
BACKGROUND OF THE INVENTION 
     1. Field of the Invention 
     The invention relates to a method for source-controlled channel decoding by expanding the Viterbi algorithm incorporating a priori and a posteriori information on the source symbols. 
     2. Description of the Prior Art 
     In the digital transmission of source signal, such as speech, sound, pictures, television, after a source coding, for example a pulse code modulation (PCM), a redundancy-reducing or irrelevance-reducing coding (i.e. MUSICAM), etc., a coding in the broadest sense is employed, for example in the form of 
     a) channel coding 
     b) coded modulation 
     c) crosstalk, for example by multipath propagation at channel. 
     In most cases, the transmission methods set forth above under a) to c) can be represented by a so-called &#34;finite state&#34; machine having ν states. Examples of this are convolutional codes, trellis-coded modulation methods, a multistage coded modulation, transmission channels with crosstalk, magnetic recording channels, and the like. The initial symbols are received disturbed after a transmission and the source data are to be detected by means of a receiver to reestablish the useful signal. 
     When using shift registers or the so-called finite state machine for this purpose advantageously the Viterbi algorithm (VA), a sequential decoding, the M algorithm or algorithms derived therefrom are employed. The algorithms and the apparatuses implemented therewith perform a &#34;maximum-likelihood&#34; (ML) estimation or a &#34;maximum a posteriori&#34; (MAP) estimation of the source data. Errors in such an estimation lead to errors in the source signals, particularly when significant symbols, for example the most significant bits in the PCM coding, are falsified. 
     The Viterbi algorithm is prior art and is used widely in the applications set forth above under a) to c). Furthermore, various expansions and implementation forms of the Viterbi algorithm exist, including the soft output Viterbi algorithm only (SOVA) which is described in patent specification DE 39 10 739, in which further publications on the Viterbi algorithm are mentioned. 
     The Viterbi algorithm used for a detection, i.e. for example for a demodulation, equalization, decoding, and the like, cannot in the present form employ any a priori or a posteriori knowledge of the pulse data sequence although such knowledge is frequently available, such as known bits or known bit frequencies, or can be obtained With the aid of methods as will be described in detail hereinafter. However, a Viterbi algorithm employed in the same manner as hitherto cannot use this information. 
     SUMMARY OF THE INVENTION 
     Consequently, the invention aims at providing a method for expanding the Viterbi algorithm in which detection information on the source bits can be employed in an advantageous manner. 
     The invention therefore proposes a method for source-controlled channel coding by expanding the Viterbi algorithm, in which method for weighting certain information a number of states (for example, the state u k  =1) are raised (or lowered) by a metric addition term B k . B k , containing available a priori or a posteriori information, is determined from the probability P(u k  =1) corresponding to the metric increment ##EQU3## where x k ,i denotes the ith bit (i=1, . . . ,N) at time k, y k ,i is the corresponding received value, and a k ,i is a fading factor, and where B k  is ##EQU4## in the case of a binary symmetrical channel (BSC) and ##EQU5## in the case of a Gaussian and fading channel, where ##EQU6## and E s  /N 0  is the signal-noise ratio (SNR) and ##EQU7## with the error probability P ok  of the binary symmetrical channel (BSC). 
     The method according to the invention for expanding the Viterbi algorithm and the further developments thereof can be employed in particularly advantageous and convenient manner for improving the decoding in the D network according to the GSM standard in the manner set forth with the method steps of claim 5. 
     According to the invention, in the method for expanding the Viterbi algorithm some states, for example half thereof, are raised or lowered by a metric addition for emphasizing certain information bits on which a priori or a posteriori information are available. The metric addition is determined from the probability P(u k  =1) which matches the metric increment. 
     The method according to the invention here may be implemented in the form of an addition implemented in hardware, firmware or software, which can be added in simple manner to all the detection methods a) to c) set forth at the beginning and with a large number of source signals leads to a considerable improvement of the signal quality when disturbances occur in the transmission of coded signals. With knowledge on the statistics, correlation and the like of the information sequence the detection is considerably improved because the control of the Viterbi alogrithm is better. Furthermore, a method for detection taking account of source information can be used in particularly advantageous manner for example directly in the transmission in the D mobile radio network according to the GSM standard. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     Hereinafter the invention will be explained in detail with the aid of preferred embodiments with reference to the attached drawings, wherein: 
     FIG. 1 shows a fragment of a so-called shift register trellis; 
     FIG. 2 is a schematic illustration of an example of a 16 bit pulse code modulation (PCM); 
     FIG. 2a is a schematic illustration of transition probabilities with correlated binary bits; 
     FIG. 3 is a diagram of a measured probability ratio ##EQU8## for five-times oversampled PCM; 
     FIG. 4 is a block diagram of a linked code system; 
     FIG. 5 is a schematic representation of an error protection diagram in the D mobile radio network, and 
     FIG. 6 is a schematic illustration for implementing a method for improved decoding in the D radio mobile network in the GSM standard. 
    
    
     DESCRIPTION OF THE PREFERRED EMBODIMENTS 
     According to the invention, in a decoding of a generalized coding the decoding is a so-called binary &#34;trellis&#34; with 2.sup.ν  states, the trellis being made up of the state transitions set forth in FIG. 1. In FIG. 1, u denotes the data and ν a memory length. The full rectangles in the trellis illustrate the bits which do not change at this transition. The outlined circles are the bits with +1 and the solid circles those with -1. The binary representation chosen here is +1 for &#34;0&#34; and -1 for &#34;1&#34;. 
     On shifting through one clock pulse in the binary trellis the last bit u k- ν  drops out and at the front the bit u k  is shifted in. 
     On deriving the a posteriori probabilities ##EQU9## with the aid of the Baye&#39;s rule and the state relationship. 
     
         P(s.sub.k)=P(s.sub.k-1)·P(u.sub.k)                (2) 
    
     it is seen that the Viterbi algorithm is changed and in equation (2) with P(S k ) or P(S k-1 ) the probability of the old or new state is denoted and with P (u k ) the probability of the new information bit. 
     Instead of the cost function 
     
         M.sub.k.sup.(m) =M.sub.k-1.sup.(m) +λ.sub.k.sup.(m) (3) 
    
     
         λ.sub.k.sup.(m) =ln p(y.sub.k |s.sub.k-1.sup.(m),s.sub.k.sup.(m))              (4) 
    
     a new cost function is used with is as follows: 
     
         M.sub.k.sup.(m) =M.sub.k-1.sup.(m) +λ.sub.k.sup.(m) +B.sub.k(5) 
    
     wherein M k .sup.(m) denotes the metric m of the mth pulse sequence for the clock pulse k, λ k  the corresponding metric increment and B k , the new additional metric term. 
     The &#34;new&#34; Viterbi algorithm operates in the first step like the &#34;old&#34; Viterbi algorithm, i.e. it calculates for the new states the metric increment λ k  and two new metrics and it further selects the metric M k .sup.(m) with the lowest costs and stores the surviving path. 
     Further possible methods for implementations are the &#34;TRACEBACK&#34; or the &#34;register exchange&#34; methods. 
     According to the invention the last term B k  is to be added to the metrics of the states with u=+1 before the Viterbi algorithm advances one clock pulse. In a shift register array these are the first 2.sup.ν-1 states. The term B k  can change from one pulse to the other and can be continuously calculated by the receiver. 
     Methods according to the invention for this purpose will be described below. It will also be shown in some examples how the term B k  is calculated in optimum manner, in particular relatively to the metric increment λ k . 
     In the decoding of the convolution code of the rate 1/N after transmission via the binary symmetrical channel (BSC) of the coded bits x k ,i (with i=1, . . . N) the error probability P ok  determines ##EQU10## Then, the metric implement λ k  is to be selected as usual as ##EQU11## and the new term is ##EQU12## L k  and L ok  being denoted likelihood values. 
     Since the error probability P ok  is usually less than 0.5, the following holds ##EQU13## Here, the term u k  L k  with the known bit u k  =1 is to be set as +∞ and with u k  =-1 to -∞ or to the highest or lowest value used in the metrics. If the value u k  L k  and L ok  are not known, at the receiver in accordance with the invention corresponding estimation means are to be provided. 
     In a decoding in the Gaussian channel or in the Rayleigh channel the metric generally employed is 
     a) for the Gaussian channel ##EQU14## 
     b) for the Rayleigh fading channel ##EQU15## with the fading amplitude a k ,i. According to the invention, the term B k  (metric addition) for the two cases (11a and 11b) ##EQU16## is then to be added for all states with u=+1, E s  /N 0  denoting the mean signal-noise ratio. Thus, in equation (11b) knowledge of the fading factor a k ,i is necessary and for the terms B k  in equation (12) in addition to the knowledge of the mean signal-noise ratio E s  /N 0  ##EQU17## is necessary from a priori, a posteriori or other information. Likewise, a normalisation is to be carried out in the manner described. 
     Thus, according to the invention by controlling the Viterbi algorithm with the metric addition B k  ##EQU18## the states with u k  =+1 are preset. 
     If the channel is poor, i.e. the likelihood value L ok  or the signal-noise ratio E s  /N 0  is small, the information estimation u k  L k  becomes more important. On the other hand, with a good channel the term B k  becomes small and the received channel values become more significant via the metric increment λ k . Consequently, according to the invention a balance is also implemented in optimum manner between the prediction and received values. 
     Below further possibilities and examples of uses for determining the metric addition will be given. 
     1) Known training bits are introduced; then, for these bits: ##EQU19## Here, ∞ is the maximum value of the numerical representation chosen in the decoder. 
     2) With an a priori knowledge it is frequently known that certain bits occur with a predetermined probability P (u k  =+1); then, the selection should be ##EQU20## 
     3) A correlation with previous data frames represents the most usual application. In PCM coding, speech transmission, for example in the D mobile radio network, in an audio transmission in the new DAB radio broadcasting system, in video transmission for example in future digital television, the data are transmitted in frames and coded framewise, as represented for example schematically in FIG. 2, where MSB denotes the most significant bit and LSB the least significant bit. 
     In the schematic illustration of FIG. 2a transition probabilities P k  are represented with correlated binary bits. If the previous frame (k-1) is already decoded, i.e. the data u k-1 ,l are known, then with known correlation probability P k   l  the value required for the metric addition (base term) can be calculated. The metric addition can therefore be determined: ##EQU21## 
     In FIG. 3, as example the measured transition likelihood value L k  with five-fold oversampled pulse code modulation (PCM) is illustrated, the likelihood value being plotted on the ordinate and the index l of the lth PCM bit on the abscissa. 
     Even more accurate values can be obtained if the SOVA algorithm described in DE 39 10 739 C2 is used instead of the Viterbi algorithm. In this case, from the previous frame not only the decision u k-1 ,l is available but also the likelihood value L k-1 ,l thereof; this then gives: ##EQU22## or as an approximation 
     
         u.sub.k,l ·L.sub.k,l =u.sub.k-1,l ·min(L.sub.k-1,l,L.sub.k.sup.l)                  (15) 
    
     This value is then used in the metric addition (equation 12b). This means that according to the invention the base value, i.e. the metric addition, combines in optimum manner the reliability of the previous decisions with the statistical correlation of consecutive source frames. Also, a combination with other a priori or a posteriori information is readily possible. 
     This method is applicable to any source compression procedure. For this purpose, only the correlations of the bits of consecutive source frames need be known or continuously estimated. The estimation of the values P k   l  may also be carried out continuously in recursive and adaptive method. For this purpose, from K preceding frames the relative frequencies of change processes of the bits u k ,l are estimated: ##EQU23## in the last K frames. Here, a progressive weighting of the recently occurred deviations may be carried out to enable rapid changes of the correlation of the source signals to be followed. 
     4) By iterations with concatenated code systems or with product codes, the decoding can be improved after the decisions of the second stage when the latter are added to the first stage as a posteriori information. 
     It is assumed here that the inner code can be decoded by an expanded Viterbi algorithm (SOVA). With a stage or product code coding as apparent from FIG. 4, the received code values y k  are decoded in the inner decoder 1, possibly with one of the methods described at the beginning under a) to c). After any possibly necessary de-interleaving by a de-interleaving unit 1&#39; after the decoding of the outer code &#34;better&#34; recoded values u k  &#39; are available in the outer decoder 2 and their reliabilities L k  at the output of an outer re-encoder 3 and possible de-interleaving. Thus, the inner decoder 1, which now has the metric additions (base terms) at its disposal, is again decoded in accordance with the method according to the invention and consequently an iteration of the decoding initiated. 
     This type of iteration is particularly effective when good reliabilities are furnished by the outer decoder 2 and by the re-encoder 3. This is for example the case when the outer decoder 2 decodes reliably, for example with Reed-Solomon codes having a small decoding error probability, or is also the case when the outer code furnishes reliable values L k , for example with parity check codes and orthogonal methods processed by the Battail method, as described by G. Battail in &#34;Coding for the Gaussian Channel: The Promise of Weighted-Output-Decoding&#34; in INT. Journal of Satellite Communications, vol. 7, pages 183 to 192 (1989). 
     Applications of the described method are product codes from two convolutional codes, convolutional and parity check codes, trellis-coded modulation and convolutional codes as well as Reed-Solomon codes as in ESA/NASA deep-space standard. 
     Hereinafter, with reference to a preferred embodiment a use of the method according to the invention for expanding the Viterbi algorithm will be described with regard to improving decoding in the D mobile radio network which is configured by the GSM standard. For this purpose, in FIG. 5 as example a schematic illustration of an error protection diagram for the full rate codec of the D mobile radio network is shown. In the upper part of the diagram frame-organised speech data are divided into three subframes of different protection rating, i.e. into 50 bits of the class 1a, 132 bits of the class 1b and 78 bits of the class 2. 
     The 50 bits of the class 1a are first coded by means of a block code in the form of a parity check by adding 3 parity bits in the diagram of FIG. 5. The 132 bits of the class 1b are expaned by 4 known terminal bits. The 132 bits of the class 1b expanded by the 4 terminal bits are then attached to the coded 53 bits of the class 1a and thereafter subjected to a convolutional coding with a rate r=1/2 and an constraint length K=5. 
     As apparent from the lower part of the diagram in FIG. 5, finally the 78 bits of the class 2 are appended to the convolutional-coded bits, 378 bits in the embodiment illustrated, and thus in their entirety represent the coded speech data, the frame of which is transmitted in this form. A division of the so-called half-rate codec is used analogously to this procedure. 
     The decoding according to the method of the invention can be improved for both methods, as will be explained below. In FIG. 6 a schematic illustration is given for receiver-side implementation of a method with regard to improving a decoding in the D mobile radio network according to the GSM standard. 
     In the decoding of the first frame the decoder 72 employs only the channel values and finally generates in accordance with the SOVA algorithm (DE 39 10 739 C2) the values u k-1 ,l L k-1 ,l. These values are available for the next frame together with the transition values for determining the metric additions (base values) in accordance with the present invention. 
     In the receiver-side decoder illustrated in FIG. 6 decisions u k-1  from the preceding speech frames are stored, and the quality of these decisions L k-1 ,l for the 50 test bits of the class 1a, i.e. for the bits=1 . . . 50, for the 3 bits l=51, 52 and 53 provided in the embodiment and for the 132 bits of the class 1b, i.e. for the bits l=54, . . . , 185. Thereafter, from transitions values u k   l  ·L k   l  in a logic unit 71 by for example the operation 
     
         u&#39;.sub.k,l =u.sub.k.sup.l ·u.sub.k-1,l 
    
     and 
     
         L&#39;.sub.k,l =α·min{L.sub.k-1,l,L.sub.k.sup.l } 
    
     with a factor α≦1 new metric additions u&#39; k ,l ·L&#39; k ,l are set for a new decoding in the trellis of a Viterbi decoder. The factor α is chosen close to 1 when the previous values are trusted and closer to 0 when they are not trusted. 
     With newly received time-dicrete channel values available as soft or hard decisions, possibly with channel state information, and which are entered into a so-called SOVA (soft output VA) Viterbi decoder 72, a SOVA Viterbi decoding is then carried out so that at the output thereof new decoded values u k ,l ·L k ,l appear. Thereafter, bits protected for example by block codes, the bits 1, . . . , 53 in the embodiment set forth, are subjected by a parity test in the unit 73 to a subsequent improvement, and for the bits linked by a parity relationship ##EQU24## the following improvement is then set: ##EQU25## 
     Thus, both for the source decoder in the receiver and for the decoding of the next speech frame new bits u k ,l and their quality L k ,l are available. This is indicated in FIG. 6 by the reference entered at the bottom arrow &#34;to the speech decoder and for storing for the next frame&#34; which in its basic sequence corresponds to the frame shown at the top in FIG. 6.