The modification of algorithm of Viterbi convolutional decoding for the fading channels and use of interleaving of symbols is described. The modification represents the use of additional correcting coefficients in the process of calculation of metrics of various parts in the trellis diagram. It gives opportunity to reduce the probability of errors of decoded symbols.
The well-known method of “soft” Viterbi decoding is based on selection of the path of the trellis diagram, which possesses the minimum metric in general ([1-4]). All paths are sums of Euclidean distances between levels of received symbols obtained from the demodulator and variants of the code which corresponds to each symbol. Possible levels of received demodulated symbols usually are divided on eight discretes, so a receiver can take into account the damage of every symbol by noise. Such variant of “soft” decoding implies same working conditions of receiving of every symbol of the sequence. (the same average SNR during symbol).
Some communication systems use interleaving of time positions of transmitted symbols for example as means against fadings of level of a signal. In such a case time intervals between initially neighbor symbols become rather big and their levels will be different. After the receiving the true sequence of symbols is restored. But in comparison with the translation without interleaving in this case the average SNR of initially neighbour symbols is different. But a receiver decodes the coded sequence using usual “soft” decoding rule. Now the path of minimum sum of metrics is not corresponded to the most proper sequences of symbols, and the probability of errors increases. So, the aim of this article is the description of the algorithm of “soft” Viterbi decoding taking into account the different conditions of receiving symbols. 2
The rule of using of the path of trellis diagram with minimum metric is caused by the following. According to the method of the maximum likelihood from all possible variants of sequences of received symbols one must choose the most probable sequence. Let Pq be the probability of number q variant of some binary sequence of symbols. It is necessary to find that number q which provides max {Pq} in conditions of receiving of the sequence with various levels of received symbols.
Let the length of symbols sequence be N. Each q variant consists of the sequence of logic “0” and “1”. The value of i symbol in the sequence of number q is denoted as ai (q). We shall consider that values of transferred symbols and noise components on time intervals of different symbols are mutually independent, so probabilities Pq are equal to:
N
Pq = ∏ pi(q){yi / ai(q)} (
i pi (q) {yi/ai (q)} - are the conditional probabilities of that the demodulator makes voltage equal yi when the value of the i transmitted symbol is equal to ai (q).
Let's observe a communication link without of a fading of level of received
signals. (Interleaving and restoring of sequence of a signal do not perform.) If the
distribution of noise is Gaussian then each conditional probability in the equation (
σ 2 2σ 2
σ2 – the noise power that is the same for all received symbols. For the simplification
of calculations magnitudes ln (Pq) are compared instead of magnitudes of Pq. So,
ln(Pq ) = − N lnσ i − 0,5N ln 2 − Ni 2σ1 2 [ yi − ai(q) ]2 (
Other situation will be when signal fades and the communication systems uses interleaving and restoring to sequence of transmitted symbols. Levels of any neighbor symbols of restored sequence will differ and conditional probabilities of every symbol must be described by mathematical expressions with different parameters.
In systems with BPSK when the level of received signal changes (but the average
noise power on the input of the receiver is constant) then after demodulation the SNR
changes too, but now the average level of signal is constant and average level of noise
changes. So, equations (
1 [ yi − ai(q) ]2
σ i 2 2σ i2
Where σi - standard deviation of noise on time interval of i symbol that is different
for every symbol. Equation (
N N 1 ln(Pq ) = − lnσ i − 0,5N ln 2 −
i 2σ i2 [ yi − ai(q) ]2 = i
}
The scheme of realization of the modified algorithm of decoding is shown in the figure 2. In the receiver 1 the signal is carried from microwaves into intermediate frequency. In the block 2 it is regulated automatically to the constant mean level needed for the BPSK demodulation. Usual “soft” demodulation is made in the block 3. In the block 4 the interleaved initial sequence of symbols is restored. In the block 5 the sequence of symbols is decoded by Viterbi procedure. All above-named blocks carry out the usual Viterbi algorithm of convolutional decoding.
The modification of the algorithm is performed by adding blocks 6-10. In the bock 6 the level of the amplitude of the signal is detected. In the block 7 the average level of signal during some time is determined. This time is inversely proportional to maximum frequency of fadings. The determined average level is converted in a digital form. Block 8 carries out exactly the same operations as the bock 4, so symbols of the restored sequence and information about levels of these symbols in the input of receiver are generated simultaneously. The block 9 calculates correcting coefficients αi according the known level of noise on the input of the receiver, according the level of signal on the output of the bock 8 and according the parameters of BPSK demodulator.
In usual “soft” decorders block 11 forms differences [ yi − ai(q) ]2 in order to sum them further. In the described modified algorithm the new block 10 is included into the order of operations of the decoding. In this block 10 all differences [ yi − ai(q) ]2 is multiplied firstly by correcting coefficients αi and only after that are summed. 3
In order to study the modified algorithm some series of computer experiments were made. The aim of all experiments was comparative examination of the algorithm with the usual decoding algorithm. All series were carried out according the same scheme. Every series consisted of three groups of experiments.
In the first group of experiments usual “soft” convolution decoding without interleaving and without fading of symbols was analyzed. Informational sequence was modeled by sequence of randomly distributed binary symbols of the constant level. Probabilities of both variants of symbols were equal. Overall quantity of symbols of series in every experiment was 3· 105 ÷ 106. Then this sequence was encoded by the convolutional algorithm with the rate R=½ and parameters of code equal to (m1;m2). These parameters were varied in different series of experiments. After that noise with Gaussians distribution and with certain level was added to the sequence and caused its distortion. The levels of noise of receiver were equal in all experiments.
The sum of signal and noise was decoded by the Viterbi algorithm. The decoded sequence was compared with the initial binary sequence. According a quantity of different symbols in this both sequences a probability of error (PER) corresponding to the used SNR and code parameters was determined.
In the second group of experiments usual “soft” convolution decoding was examined but levels of signals sequences were variated. This variations modeled fading of received signal levels in fluctuating channels of transmission. In order to model fades the Rayleigh distribution was used ([5]). In this group the informational sequence was also modeled by sequence of randomly distributed binary symbols but levels of symbols before summing with noise were variated according the Rayleigh distribution. The mean value of the distribution of symbols was equal to the constant value of symbols in the first group of experiments. After summing with noise this sum was decoded by the Viterby algorithm and PER corresponding to the used SNR and code parameters was determined.
The third group of experiments was made using the described modified algorithm of decoding. As in the second group of experiments a sum of fading coded sequence and Gaussian noise was obtained but after that it was decoded by the described modified algorithm.
A set of parameters used in experiments was varied with a step of one bit from most simple codes (5;7) coinciding the length of 3 bits coding register to rather complicated codes (133;171) coinciding the length of 7 bits coding register (NASA codes). On the figures 3–7 some summarized results of experiments are adduced. Diagrams on these figures are the functions of the dependence of probability of error after decoding on the SNR of received signals. Every figure shows the results of experiments with various parameters of codes. The correspondence of figures and code parameters is shown on the TABLE I.
Diagrams from all three groups of experiments corresponding to used code parameters are adduced on every figure. Numbers of diagrams conform to numbers of groups. The decoding of fading signals with the help of usual “soft” algorithm has considerably worse characteristics in comparison with the decoding without fading. The reasons of this fact are often mistakes in selection of the optimal path with minimum metrics in trellis diagram that were caused by inexact calculation of metrics of symbols with bad “quality”.
The use of modified algorithm gives opportunity to come nearer to the situation without fading and interleaving. The quality of decoding increases when encoding becomes more complicated. The diagrams of the second group show big growth of PER because significant part of work time of transmission system a level of received signal is small. The difference of diagrams of the first and the third groups can be most likely explained by the fact that symbols with bad “quality” influence to the selection of optimal path insignificantly but the quantity of symbols with good “quality” decreases too.
Using of the described modified algorithm of Viterbi convolution decoding gives opportunity to improve the characteristics of decoding of communication with interleaving of symbols. If the modified algorithm is used in situation without interleaving and fading then its characteristics are identical to characteristics of usual “soft” decoding.