A GENERALIZED POST-DETECTOR COMPATIBLE SOFT-OUTPUT VITERBI ALGORITHM (SOVA) By David Kwan B.A.Sc, The University of British Columbia, 1989 A THESIS SUBMITTED IN PARTIAL FULFILLMENT OF THE REQUIREMENTS FOR THE DEGREE OF MASTER OF APPLIED SCIENCE (M.A.Sc) in THE FACULTY OF GRADUATE STUDIES ELECTRICAL ENGINEERING We. accept this thesis as conforming to the required standard THE UNIVERSITY OF BRITISH COLUMBIA April 1996 © David Kwan, 1996 In presenting this thesis in partial fulfilment of the requirements for an advanced degree at the University of British Columbia, I agree that the Library shall make it freely available for reference and study. I further agree that permission for extensive copying of this thesis for scholarly purposes may be granted by the head of my department or by his or her representatives. It is understood that copying or publication of this thesis for financial gain shall not be allowed without my written permission. Department of bUc. L,r\p-£>c. The University of British Columbia Vancouver, Canada Date Apr--, ) IS , l°MC> DE-6 (2/88) Abstract A generalized soft-output Viterbi algorithm (SOVA) that is applicable to any (n, k, m) convolutional code is proposed. The algorithm is compatible with the post-detector ar chitecture proposed by Berrou et al. thereby achieving low computational complexity. By starting with Battail's generalized revision algorithm and re-referencing the relative values to the surviving path to each state, significant simplifications are made possible. By comparing the resultant simplified revision equation for (n, l,m) convolutional codes with Berrou's proposed post-detector compatible algorithm it is possible to deduce the additional modifications necessary to arrive at a (n,k,m) post detector compatible al gorithm. Simulations show that with a revision depth greater than five times a code's constraint length, the proposed algorithm is capable of producing relatively high quality a posteriori input symbol estimates. ii Table of Contents Abstract ii List of Tables vList of Figures vii Dedication ix Acknowledgements x 1 Introduction 1 1.1 Motivation and Scope of the Thesis 1 1.2 Outline of the Thesis 4 2 Background and Underlying Principles 5 2.1 Using Soft-Outputs in Serially Concatenated Systems 5 2.2 The Symbol-by-symbol MAP and "Best-Path" Algorithms 9 2.3 The Soft-Output Viterbi Algorithm (SOVA) 10 2.3.1 Deducing Viterbi Decision Probabilities 1 2.3.2 The Need For Revision 14 2.4 History of SOVA 15 2.4.1 Relative Values2.4.2 A Simplified Revision Algorithm 17 2.4.3 The Post-Detector Architecture 8 iii 3 Derivation of the Generalized Post-Detector 22 3.1 Introduction 23.2 Terminology3.2.1 Relative Values at the Decoder's 0— memory level 22 3.2.2 Conditional Relative Values at the Decoder's j— memory level . . 24 3.3 Re-deriving Battail's Revision Formula 25 3.4 Simplifying the General Revision Formula 7 3.5 Finding a Revision Algorithm That is Post-Detector Compatible 28 3.5.1 Post-Detection Compatible Revision Algorithm for (n,l,m) Codes 30 3.5.2 Post-Detection Compatible Revision Algorithm for (n,k,m) Codes 34 3.6 Application Considerations 37 3.6.1 Deducing Input Probabilities From Relative Values 37 3.6.2 Examining the Effects of the Approximations Made 42 3.6.3 Computational and Storage Requirements 44 4 Evaluating Performance of The Generalized Post-Detector 51 4.1 Introduction . . 54.2 Effects of Code Free Distance on the Estimates of the A Posteriori Prob abilities 52 4.3 Effects of Signaling Constellation on the Quality of the Estimates of the A posteriori Probabilities 58 4.4 Determining Performance of the Generalized Post-Detector for use in Soft-Output Viterbi Equalizers 61 4.5 Determination of the Minimum Required Revision History for the Gener-. alized Post-Detector 70 5 Conclusion 72 iv 5.1 Summary 72 5.2 Proposed Future Work 74 Bibliography 75 A Predicting Concatenated Code Performance - Graphical Method 77 B Code Tables 80 B.l Convolutional Codes 81 B.2 TCM Codes 2 B. 3 ISI Channels 5 C The MAP and "Best-Path" Algorithms 86 Cl The MAP (or Bahl, "forward-backward", "any path") Algorithm 86 C. 2 The "Best-Path" Algorithm . . . 90 C.3 Computational and Storage Requirements 91 v List of Tables 3.1 Signal Mapping used by the 8-PSK Modulator 42 3.2 Computational/Storage Requirements For a Typical Viterbi Decoder. . . 45 3.3 Additional Computation/Storage Required to Implement and Add a Gen eralized Post-Detector 46 3.4 Comparison of the Computation Requirements of Various Soft-Output De coder Algorithms 7 Cl Minimum Operations Required per Input Symbol for the MAP Algorithm. 93 C.2 Minimum Operations Required per Input Symbol for the Best-Path Algo rithm 9vi List of Figures 2.1 Concatenated System with Corresponding Data Flow Diagram 6 2.2 The "Classic" (2,1,2) Convolutional Encoder and its Corresponding Trellis State Diagram 12 2.3 Trellis for (2,1,2) Convolutional Code 14 2.4 Hagenauer and Hoeher's Revision Algorithm 18 2.5 Revision Algorithm by Berrou et al 19 2.6 Post Detector Architecture 20 3.1 Depiction of a Viterbi Decoder's Decisions Made at the 0— and j— Memory Levels 23 3.2 Revision Operation Using Equation (46) 29 3.3 Generalized Revision Algorithm for Post-Detector 38 3.4 Rate 3/4 SOVA system 33.5 Rate-3 Soft-Output Viterbi EQ system 41 3.6 Comparisons of Algorithm Storage Requirements 49 3.7 Comparisons of Algorithm Computational Requirements 50 4.1 Concatenated Coding System Using Convolutional Codes for Both the Inner and Outer Codes 54 4.2 Performance of Various Concatenated Systems Utilizing an Inner Code with dfree = 3 5 4.3 Performance of Various Concatenated Systems Utilizing an Inner Code with dfree = 4 56 vii 4.4 Performance of Various Concatenated Systems Utilizing an Inner Code with dfree = 7 57 4.5 Concatenated Coding System using Multi-Level Modulation for the Inner Code 9 4.6 Effect of Different Signal Constellations on the Quality of Soft-Output Information 60 4.7 Concatenated Coding System with uncoded 8-PSK Modulation Over a Static ISI Channel 4 4.8 Soft-Output Equalizer Performance in a Concatenated System Using Un coded 8-PSK for the Outer Code 65 4.8 Continued 66 4.9 Concatenated System Using Coded 8-PSK Over a Static ISI Channel. . . 67 4.10 Soft-Output Equalizer Performance in a Concatenated System Utilizing Coded 8-PSK for the Outer Code 68 4.10 Continued 69 4.11 Simulation Results of a Concatenated System Utilizing a Post-Detector With Various Revision Depths 71 A.l System Model for Graphical Procedure 78 A. 2 Graphical Determination of Concatenated System Performance 79 B. l Two and Three Tap ISI Channels 85 viii Dedication In memory of my grandmother and father, and for my ever persevering mother. ix Acknowledgements The author would like to thank his advisor Dr. Samir Kallel for proposing such an inter esting project. The many insightful discussions, his guidance, and encouragement have been invaluable. The author would also like to thank Ian Marsland for proof reading the thesis and for his help throughout the project. Finally, credit has to be given to Abderrazek Zaafrani for his invaluable English translation of Battail's paper [2]. x Chapter 1 Introduction 1.1 Motivation and Scope of the Thesis There arises many situations in communications where the serial concatenation of several codes may transpire. For such systems, optimum performance is achieved when the decoding is performed on the resulting effective global code. However, if the global code is too complex, decoding in this manner may not be viable. An alternative is to decode each individual code separately using the results from each decoding stage as input for the subsequent decoding stage. For this arrangement to achieve its full performance potential it is necessary that all of the decoding stages perform soft-decision maximum a posteriori (MAP) decoding. Unfortunately, many of the popular decoding algorithms such as the Viterbi algorithm output hard-decisions. Therefore, if any of these algorithms are used for decoding one of the inner codes, this will constrain the subsequent decoding stage to hard-decision decoding resulting in a degradation of performance. As shall be shown later, it is possible for a subsequent decoding stage to perform soft-decision decoding if the preceding decoding stage can provide a posteriori input symbol probabilities instead of hard decisions. Decoders that are capable of providing such information are usually referred to as "soft-output" decoders. Applications that can benefit from the use of "soft-output" decoders include the serial concatenation of codes to produce a more powerful, yet still easily decoded, global code. Other examples would be the use of Viterbi equalization for previously encoded data, or the transmission of 1 Chapter 1. Introduction 2 previously encoded data using TCM. A more recent example would be the iterative "Turbo" decoding algorithm for use with parallel concatenated codes [4]. Motivated by the potential gains that soft-output decoding can bring to these applications (for Turbo decoding, it is in-fact an essential element) much research has been done in the area of finding fast, efficient, and accurate soft-output decoding algorithms. The work described in this thesis is part of that effort. One of the algorithms that can be employed for soft-output decoding is the symbol-by-symbol MAP algorithm. Proposed in [1] as an optimal method of decoding convolutional codes, its use for soft-output decoding was probably never intended. However, it does produce as a natural by-product of the decoding process the necessary a posteriori input symbol probabilities required for soft-output decoding. Its main advantage is that it deduces the exact value for the a posteriori input probabilities. Its disadvantage is that it requires a relatively large amount of computation. Indeed, this is one of the reasons it is not commonly used for decoding convolutional codes - most designers opt in favour of the Viterbi algorithm. In addition to the relatively high computational requirements, the decoding delay and the amount of storage necessary to implement the algorithm are dependent upon the length of the transmitted code sequence. Several sub-optimal variants of this algorithm have been proposed to address some of these problems. For example, to reduce the amount of computation necessary there is the "Best-Path" algorithm described in [7]. To eliminate the dependence of the decoding delay and required storage on the length of the transmitted code sequence, there is the algorithm proposed in [14]. An alternative approach that may be used for soft output decoding is based upon a heuristic modification to the standard Viterbi algorithm. The resulting soft-output Viterbi algorithms (SOVA) [2] [3] [6] are able to deduce estimates of the a posteriori input Chapter 1. Introduction 3 probabilities.1 One of the main attractions of this approach is that because the resulting algorithms are based on the Viterbi algorithm, they have the desirable quality that the decoding delay and required storage are independent of the length of the transmitted code sequence. They are also computationally efficient in that the majority of the op erations needed to implement these algorithms involve relatively simple operations such as comparisons and additions. Finally, as shown in [3], if one can derive a SOVA that is compatible with the "Post-detector" architecture, then it is possible to significantly reduce the amount of required computation and storage needed to estimate the a posteri ori input probabilities. In the "Post-detection" scheme, the soft-output decoder is given knowledge a priori of what its eventual surviving path shall be. If the algorithm satisfies certain conditions (described in Chapter-2), it may use this information to its advantage thereby eliminating many of the required operations. The work described in this thesis focuses on the heuristic approach to deducing a posteriori input probabilities. At the onset of this project, one major short coming to the SOVA approach to generating soft output information was that there did not seem to exist an efficient algorithm that was applicable to any (n, fc, m)2 code. All of the al gorithms proposed in [2][3][6] are only applicable to binary input (n, l,m) type codes. If it was desired to use any of these algorithms for a rate-fc/n code then such a code would have to be synthesized by puncturing a rate-l/n code. Therefore, the main objective of the research documented by this thesis was to find a heuristic based soft-output decoding algorithm that is applicable to any (n, k, m) type code. For the sake of computational efficiency it was also desirable that this algorithm be compatible with the post-detector 1The term SOVA is often used in reference to the specific algorithm proposed by Hagenauer and Hoeher in [6]. However, due to the similar foundations, for this thesis the term SOVA is used in reference to any algorithm that is based upon a heuristic modification of the standard Viterbi algorithm. 2Following the notation as presented in [11], a (n,k,m) code represents a convolutional code with n-output bits, fc-input bits, and a memory of m-bits. Chapter 1. Introduction 4 architecture proposed in [3]. Having found such an algorithm, its performance was eval uated through the use of computer simulations of various concatenated systems. Its computational complexity was also compared with the MAP and Best-Path algorithms. 1.2 Outline of the Thesis This thesis is organized as follows. In chapter-2, the use of a posteriori input probabilities for soft decision decoding is described. This is followed by a brief description of the algorithms proposed in [2] [3] [6] - on which the derivation described in Chapter-3 depends. In Chapter-3 the newly proposed "generalized post-detector algorithm" is derived. The computational complexity is compared with MAP and Best-Path algorithms. A brief discussion of some of the potential ramifications of the approximations made during the algorithm's derivation is presented. Computer simulation results are shown in Chapter-4. In Chapter-5 a summary is presented and suggestions for possible further investigation are made. Chapter 2 Background and Underlying Principles 2.1 Using Soft-Outputs in Serially Concatenated Systems Consider the serially concatenated system shown in Figure 2.1. In this system a message sequence m is multiplexed into several sub-messages m;. These sub-messages are encoded using the outer code. The resulting code sequences pi are then interleaved resulting in the sequences q~j. The sequences q~j are encoded using the inner code and transmitted over an AWGN channel. The received sequences Rj are decoded resulting in the sequences Uj. These sequences are then de-interleaved into the sequences The purpose of the interleaver/de-interleaver operation is two-fold. First, it eliminates any correlation in the symbols of each sequences q~j. Second, it eliminates any correlation in the "noise" samples in each received sequences Yj. Finally, the sequences F; are then decoded into the sub-messages fh^. For such a system to achieve optimum performance, both the inner and outer decoders should perform soft-decision MAP decoding. Clearly soft-decision decoding for the inner decoder does not pose any problems since the received sequences Rj represent sampled continuous random processes. In addition, since the symbols from the inner decoder are transmitted over an AWGN channel, the conditional density function of the received symbols is well known: where Sj is the transmitted signal sequence and a2 is the noise variance of the AWGN 5 (1) Chapter 2. Background and Underlying Principles m Outer P Inter- Inner Signal 51 Encoder leaver Encoder Mapper AWGN Outer De-inter- Inner Decoder V leaver - Decoder R Interleaver De-interleaver »ii —P- px-ihj —• pi -mK—• PK--+• q\ —• s\ —%*• R{—1+ U] -*> q~j —• Sj —• Rj —• Uj -> q~L —• ?i —+• RL—+ UL J Yi — Yi —> m' YK—¥-m'K Figure 2.1: Concatenated System with Corresponding Data Flow Diagram. Chapter 2. Background and Underlying Principles 7 channel. This conditional density function may be used to perform MAP decoding utiliz ing the unquantized input symbols. Soft-decision decoding for the outer code, however, is not as straight forward since any conventional decoder structure used for the inner decoder will deliver hard quantized decisions. To determine how one can perform soft-decision MAP decoding for the outer code assume, for the time being, the existence of a soft-output inner decoder that will output an unquantized sequence Uj whose samples Uji (and hence Yij) are suitable for any outer decoder to perform soft-decision decoding. To satisfy the condition that the outer decoder perform MAP sequence decoding it must utilize the following selection criteria: Find m'i such that P{m!AYA > P(mi\Yi) V m^m; (2) Substituting PW?) = AW) (3, and asserting the condition that all sequences m are equally likely, then (2) may be rewritten as: Find m'i such that /(F;K) > /(F;K) V rfk ^ mj (4) Because of the one-to-one relationship between the message sequences m and the code words p this is equivalent to: Find m'i such that /(^|pi(m-)) > f (Yi\pi(mi)) V ^ m{ (5) where pi{fhi) represents the specific code sequence pi associated with the message se quence rhi. Defining the "error" sequence fji = Yi — pi(rhi), each side of (5) may be expressed as, Chapter 2. Background and Underlying Principles 8 fWMmi)) = f(fJl = Yi-pi(mi)) (6) L = J]. fiVij = Yij - Pij(mi)) due to interleaving j=i L = Hf(Yii\Pij(^ii)) 3=1 Because q and U are merely p and Y interleaved respectively, /(£|#(m0) = UHUMrrii)) (7) 3=1 Therefore (5) maybe rewritten as: Find m'i such that, * P(^K)|^)P(/JJt) ^ P((b<(mi)|t/J-i)P(t/J-0 m/ P(Uji) does not depend on and therefore can be cancelled from both sides. If the inner code has the property that P(qji(mi)) is equal for all choices of qji then it too can be eliminated. Thus the only term that the outer decoder needs to perform MAP soft-decision decoding are the probabilities P(qji\Uji). Because of interleaving each of the q^ of the sequence q~j are independent. Therefore knowledge of UjX (Va; ^ i) will have no affect on P(qji\Uji). Consequently, it is possible to substitute P(qji\Uji) for P(qji\Uj). The resulting MAP decision criteria becomes: L _ _ L Find m'i such that JJ P(qji(m'i)\Uj) > J] P(qji(mi)\Uj) V mii-w!i (9) 3=1 3=1 The necessity of this substitution shall be shown in the following paragraph. Previously, the assumption of the existence of a soft-output inner decoder that delivers unquantized decoded information sequences U was made. Assume that each of these decoded sequences corresponds to a unique received sample sequence R resulting in a one-to-one relationship between U and R. Under these circumstances, P(qji\Uj) will be equal Chapter 2. Background and Underlying Principles 9 to P(qji\Rj) since knowing Uj is equivalent to knowing Rj (and vice versa). Note however that the procedure for calculating P(qji\Rj) is already well known since these are the exact quantities that must be computed if the inner decoder were a symbol-by-symbol MAP decoder. Therefore, if the outer decoder were to set P(qji\Uj) to P(qji\Rj) as calculated by an inner MAP decoder, this would be equivalent to using the aforementioned fictitious soft-output inner decoder. Since the outputs from this fictitious decoder are unquantized and there is no information reduction going from R to U, the outer decoder will be performing soft-decision decoding. As a result of the discussions presented in the previous paragraphs it can be concluded that the decision rule: L _ _ L Find m'i such that H P(<lji(m'i)\Rj) > II v ™* m'i (10) 3=1 J'=I is sufficient for the outer decoder to perform soft-decision MAP decoding under the condition that all message sequences m, are equally likely and all encoded sequence symbols qji (and hence pij) are also equally likely. For convolutional codes and TCM codes, the condition that all of the possible output symbols from the outer decoder are equally probable is satisfied. 2.2 The Symbol-by-symbol MAP and "Best-Path" Algorithms As mentioned previously, there already exists a known algorithm for calculating the a posteriori input probabilities P(qi\R). This algorithm is, not surprisingly, known as the symbol-by-symbol MAP algorithm (also known as the "Bahl" [1] or "forward-backward" [7] algorithm). This algorithm in optimum in the sense that it determines the exact values for the a posteriori input probabilities P(qi\R). The cost of this precision however is that it requires a relatively large number of multiplications per decoded symbol. This Chapter 2. Background and Underlying Principles 10 may pose a problem if the hardware available is not capable of performing the neces sary calculations in real-time at the desired speeds1. A sub-optimal derivative of this algorithm that reduces the amount of computation required by replacing multiplications with additions and additions with compares is the "Best-Path" algorithm [7]. This al gorithm is computationally efficient and capable of delivering high quality probability estimates. However, because of its similarity to the MAP algorithm it also shares some of its disadvantages. Because both of these algorithms involve a forward computational pass starting from the first received symbol and a reverse computational pass starting from the last received symbol, one must wait for the entire transmitted sequence to be received prior to the completion of the calculation of any of the a posteriori input proba bilities. This may lead to unacceptable decoding delays at the receiver if the transmitted sequence is relatively long. Furthermore, one must at the very least store the entire received sequence so that it may be referenced for the second pass. Hence, the amount of storage required for this algorithm for long transmitted sequences may be quite large. A detailed description of the MAP and Best-Path algorithms is given in Appendix-C. 2.3 The Soft-Output Viterbi Algorithm (SOVA) The soft-output Viterbi algorithm is a name used to describe a family of sub-optimal algorithms that are used for calculating estimates of the a posteriori input probabilities P(qi\R). They are all based upon a heuristic modification of the conventional Viterbi algorithm (for an explanation of the Viterbi algorithm see [9] [10]). Because of this re lationship, the decoding delay and the amount of required storage for these algorithms are independent of the length of the transmitted sequence. In addition, the majority xIt should be pointed out that many modern microprocessors and digital signal processors are capable of performing floating point operations at speeds comparable to integer arithmetic. Furthermore the cost of this type of hardware appears to be continually decreasing. Therefore, concerns over whether a system has sufficient computing power may no longer be a major issue. Chapter 2. Background and Underlying Principles 11 of the computations involved in the calculation of the a posteriori probability estimates involves additions, subtractions, and comparisons - operations that can be performed quite rapidly on simple, inexpensive hardware. 2.3.1 Deducing Viterbi Decision Probabilities The basic supposition is that it is possible to deduce the reliability of the decisions made by a Viterbi decoder by comparing the path metrics of all paths merging into each state of the trellis. Whenever a Viterbi decoder chooses a survivor merging into a state, the confidence in the input bits or symbols associated with that decision is proportional to the magnitude of the difference between the path metrics of the survivor and concurrent paths. For example, in Figure 2.2 consider the two paths merging into state-1 at decoder memory level j = 0. Ms and Mc are respectively the accumulated Viterbi path metrics of the survivor and concurrent paths. If the encoded symbols were transmitted over an AGWN channel, the metrics would be given by: Ml = -lnP(^th-i\rk1) = ^J2\rt-^t{xf)}\2 , i = s,c (11) ^° t=l where r\ is the sequence of received symbols from time-1 up to time-A; (this notation provides a convenient means of referencing sub-sequences of the entire received sequence R), rt is the received sample at time t, and st{x[^} is the transmitted signal at time t corresponding to the output symbol associated with the i-th path. For this channel, the confidence in the Viterbi decoder's decision in choosing the surviving path over the concurrent path may be found by: ^(attLbkdS0-l K) = ^(surviving path|r*) e~M< g-Ms _|_ g—Mc 1 Figure 2.2: "Classic" (2,1,2) Convolutional Encoder and its Corresponding Trellis State Diagram. Chapter 2. Background and Underlying Principles 13 Equation (12) provides an expression for determining the probability of the decision made by the Viterbi decoder at time-A; and state-1. However, the desired quantity is the probability of the input bits or symbol associated with this selection. The relationship between the decisions and input bits or symbols depends on the structure of the encoder. Consider the encoder shown in Figure 2.2. For this example, the encoder's state was denned to be the contents of its shift register. By noting the states at time k — 1 of the survivor and concurrent paths, it becomes apparent that the contents of the encoder's shift register must differ in only the last bit prior to the merger at time-k. Hence the decision probability calculated previously refers the encoder's shift register "roll-off" bit. Equivalently, for this example, the probability calculated corresponds to an input bit decision at time k — 3. For feed-forward encoder's in general, each decision associated with the selection of a survivor to each state corresponds to the selection of a corresponding shift-register roll-off symbol. The bits corresponding to this symbol are, of course, bits that would have been inputted previously. Note that if the encoder consists of shift-registers of differing lengths it is not possible to calculate the input symbol probabilities directly. For a systematic feed-back encoder the relationship is different. In this case, each path merging into a particular state will be associated with unique input symbol. Therefore, the survivor selections also correspond to the selection of a specific input symbol. There is no time delay for this situation. Taking the previous comments into consideration, for the encoder shown in Figure 2.2, equation (12) states: 1 (13) I -|_ e-(Mc-M3) Chapter 2. Background and Underlying Principles 14 State 0(00) 1(01) 2(10) 3(11) 5 4 3 2 1 0 Mem Lev: j k-4 k-3 k-2 k-1 k k+1 Time Figure 2.3: Trellis for (2,1,2) Convolutional Code 4_3 = 1 on surviving path to state-1 = 1 Concurrent decision at t — k, state-1 h-3 — 0 on surviving path to state-1 (14) 2.3.2 The Need For Revision There now exist an expression for the reliability of a Viterbi decision given received symbols r\ = {ri,..., r/t}. However, because the encoder's output symbols are correlated, as subsequent symbols are received, they will have an impact on the probabilities of previous decisions. The values calculated by equation (12) will have to be updated. Hence one requires a revision algorithm that will update the previously calculated probabilities as new symbols are received. This process of calculating new probabilities and revising the previously calculated probabilities must be repeated until the final symbol r^ arrives. The concept is illustrated in Figure 2.3. Assume that the surviving path from Figure 2.2 is now part of the surviving path to state-0 at time k + 1. Then if follows that: Chapter 2. Background and Underlying Principles 15 p Ik-3 = 0 on surviving path ri to state-0 k+1 = P P Ik-3 =0 on Surviving path surviving path at t = k + 1, Ik—3 =0 on Concurrent path surviving path at t = k + 1, to state-1 I state-0 to state-0 | state-0 Once this revision formula has been applied there will exist up-to-date reliability infor mation for the surviving path for decisions at time t = k and time t = k + 1. When the next symbol is received at time k + 2, the revision formula is applied once more to the probabilities computed at times k and k + 1. The process is repeated until the final symbol is received. Finding an efficient revision formula or algorithm is the key to SOVA. Where previous works [2] [3] [6] differ is in the approach and details of this operation. Because of the heavy dependence that the newly proposed revision algorithm has on the previous works, a brief overview of those works shall be presented. 2.4 History of SOVA 2.4.1 Relative Values In 1987 G. Battail published a paper [2](Fr) describing a general SOVA revision algorithm. Rather than revising the actual Viterbi decision probabilities, as was done in the previous section, he revises a quantity known as "valeur relative" (or "relative values"). For a (n, k, m) code the relative values associated with the decoder's most recent decision are defined as: where XQ represents the encoder's roll-off symbol (for a feed-forward encoder) or input symbol (for a systematic feedback encoder) at the time corresponding to decoder memory depth-0. Equivalently the relative value is representative of the confidence in the Viterbi a0p = log Pjxp = 0) P(x0 = p) = MP-M0 p = 0,---,2fc-l (16) Chapter 2. Background and Underlying Principles 16 decoder's decision concerning the 0th and pth paths, as identified by the roll-off or input symbol, to a given state. (This quantity is in-fact the same "relative" metric that was used previously in section 2.3.1.) Using this definition, the confidence in a Viterbi decoder's decision for a non-binary input (n, k, m) convolutional or trellis code is represented by a vector of relative values. Battail also defined the conditional relative value to take into consideration past decisions conditioned on the current choice of survivors to each state. For the decision made j symbols in the past conditioned on the current pth path: „P _ lQC P(xi = °\xo = P) A_0...ofc-1 (17) With these definitions, Battail derived a general revision formula that was applicable to any (n,k,m) code. However, due to its complexity, he concentrated on the binary input (n, l,m) case. By focusing on this this sub-class he was able to limit the number of terms that had to be taken into consideration. Simplifying the resulting (n,l,m) expression he arrived at a revision formula that has a low computational complexity and is relatively simple to implement. His revision formula is reproduced here for the convenience of the reader: ay+i) = max(a], a° + a*, a° + a0, a° + a] + a0) — max(0, a°, a0, a* + a0) (18) The reason there is only one equation and not two (one for each a(-,+i)i , i = 0,1) is that, because of how the relative values are defined, aj0 = 0. Therefore there is no need to calculate it. Similarly, since a0o = 0 and a*0 = 0 always, there is no need for those relative values (where they occur in the revision formula, they have been replaced by 0). Therefore, each term in (18) refers to either a^+iji, c^i, or a*-x. To illustrate how this revision formula is used, refer back to Figures 2.2 and 2.3. In Figure 2.2, Ms is the metric for the 0th path (as identified by the shift-register roll-off bit) while Mc is the metric for the 1th path. Therefore, for the decision made at state-1 Chapter 2. Background and Underlying Principles 17 at time-fc: a00 = Ms - Ms = 0 (19) a0i = Mc- Ms (20) Similarly, there would also be a set of relative values generated for the decisions made to each other state. Referring to Figure 2.3 for state-0, time k + 1, Mc now refers to the 0th path while Ms refers to the Ith path. A new relative value vector [a0o,a0i] is calculated using these metrics while (19) and (20) become [a^a^] since they are now part of the current 1th path. The relative value vector that was calculated for state-0 at time-fc now becomes [a50,a?i] as it is part of the current 0th path. Revision formula (18) states that the updated relative value vector for the decision at memory depth-1 (time-A;) on the surviving path (the 1th path) to state-0 may be found by: aio = 0 (21) an = max(aj1,a§1 + aJ^aQ! + ooi.aQ! + ajx + a0i) - max(0,ao1,a0i,aj1 + a0i) (22) 2.4.2 A Simplified Revision Algorithm Presented at Globecom'89, Hagenauer and Hoeher [6] described an alternate revision algorithm. Reproduced in Figure 2.4, the algorithm compares only two quantities per re vision and only performs the revision if the concurrent and surviving paths yield different decisions. This algorithm revises the log-likelihood ratio: where pj is the a posteriori probability estimate for the decision made at memory level Lj = log 1 -Pj (23) Pi j. The revision function /(Lj, A) is defined as: (24) Chapter 2. Background and Underlying Principles 18 Recursion: a) Classical Viterbi step: For each state sk Compute IXst-i ,sk) = TXsk) + % 2£i (y tn - *to)2 for both transitions (sk-\, sk) • Find r(sk) = min r(sk-i, sk). Store F(sk) and the corresponding survivor iik(sk) • b) Soft-deciding update: For each state sk Store A = maxT(sk~\, sk) - min r(in, sk). Initialize Lk(sk) = +°°. For j = k-v to j = lc-&m Compare the two paths merging in sk if uf\sj) * uf\sj) then update Lj:=f(Lj,A) Figure 2.4: Hagenauer and Hoeher's Revision Algorithm where A = Mc — Ms and a is a constant scaling factor. Like Battail's simplified revision formula, this algorithm is only applicable to (n, l,m) type codes. However, since this revision formula only compares two quantities per revision, the amount of computation required for this revision algorithm is less. 2.4.3 The Post-Detector Architecture In a paper presented at ICC'93 by Berrou et al. [3] the results of the previous two works are combined. The authors started from Battail's original non-simplified revision formula for (n, l,m) codes and were able to derive a simple revision algorithm that parallels the one published by Hagenauer and Hoeher in that the revision operation involves essentially the comparison of only two quantities. Like Battail's algorithm their Chapter 2. Background and Underlying Principles 19 case 1: Sj(k, m) • s'(k, m)<0 dj(k, m) = Sj(k, m) • min [\aj(k, m) |, a(k,m)\] case 2: Sj(k, m) • s'j(k, m) > 0 cij(k, m) = SjQc, m) • min [ | a,(&, m) \, \a(k,m)\ + \a'j(k,m)\] Figure 2.5: Revision Algorithm by Berrou et al. algorithm revises "relative values". Their algorithm is reproduced in Figure 2.5. The a[j\k,m) and a(k,m) terms are the same as the a*- and a0 terms in Battail's revision formula (equation (12)) with the exception that the time-A; and state-m are explicitly shown. The term Sj(k,m) is the sign of the relative value a,j(k,m). One of the author's findings was that the quality of the a posteriori probability estimates was not seriously affected by the neglecting case-2. This was fortuitous since the author's realized that significant computational savings could be realized by this action. The authors noted that case-1 depends solely on the "relative values" (referred to as "weights" in [3]) of the path currently being revised. Therefore, by choosing to revise only the globally best path (the overall survivor), the "relative value" information of the concurrent paths need neither be computed nor stored. To take advantage of these potential savings, all that is required is that the module performing the SOVA operation know a priori what the surviving path is. This resulted in the post-detector architecture outlined in Figure 2.6. To illustrate why a post-detector architecture is beneficial for Berrou's algorithm and not Battail's, consider the example shown in Figures 2.2 and 2.3. Consider the hypothetical situation in which both state-1, time-k and state-0, time k + 1 lie on the global surviving path. Using Battail's notation, according to Berrou et al, the relative value an can be sufficiently approximated by: an = sign(ajx) • minflajj, |a0i|] ' (25) Chapter 2. Background and Underlying Principles 20 Encoder Mod Channel Xj :i=\-N Delay Line Viterbi Decoder SOVA Post-Detector a posteriori i/p symbol probabilities P(x,\Y) Figure 2.6: Post Detector Architecture Note that is the relative value for state-1, time-A; conditioned on the surviving path. Compare this with equation (22) where it was necessary to also know - a relative value associated with a decision at a state and time (state-0, time-A;) not lying on the globally best path. Therefore, for Battail's algorithm, regardless of having a priori knowledge of what is the globally best path, one still needs have the updated relative values conditioned on the concurrent paths. Since the concurrent paths may have in the past traversed through any trellis state, at each time step one must still revise the relative values of every surviving path to each and every state. As a result, there are no computational or storage savings if a post-detector architecture is used with Battail's algorithm. At this point, it is convenient to state the conditions under which an algorithm will benefit from a post-detector architecture: The revision algorithm must only depend upon relative values of decisions made on the globally best path. It may depend on the aoi terms if these relative values are for a state lying on the globally best path. It may depend on the ciji terms if these relative values are conditioned on being part of the globally best path. It should be pointed out that the decrease in computational complexity that results from using a post-detector architecture does not come without a price. In this case additional decoding delay has been introduced. Not surprisingly, there appears to be a Chapter 2. Background and Underlying Principles 21 trade-off being made between precision, complexity, and decoding delay. Chapter 3 Derivation of the Generalized Post-Detector 3.1 Introduction In this chapter the generalized post-detector algorithm is derived. As was done in [3], the derivation presented here begins with Battail's unsimplified revision equation for relative values. However, unlike [3], this treatment begins with the more general equation that is applicable to any (n, k, m) code. For the sake of some of the simplifications that will be made later, and the convenience of the reader, Battail's general revision equation will be re-derived. The derivation parallels the steps as presented in [2], however, the relative values have been referenced against the metric of the surviving path to each state. (As shown in equations (16) and (17), Battail referenced his relative values to the metric of the 0th path to each state.) As shall be shown later, this step makes possible some crucial simplifications that lead to an intermediate revision formula that is essential to the derivation of the final proposed post-detection compatible algorithm. 3.2 Terminology 3.2.1 Relative Values at the Decoder's 0— memory level Referring to Figure 3.1 in which two Viterbi decoder m-ary decisions are depicted (one at the 0th memory level and the other at the jth memory level conditioned upon the 0th) the "relative values" of the decoder's most recent decision (at an arbitrary state) are 22 Chapter 3. Derivation of the Generalized Post-Detector 23 Most Recent Viterbi Decision (Memory Level-O) Viterbi Decoder Path Memory to Previous States at time: t=k » Trellis Transition Xn Viterbi Decision Made j Symbols Previously Along the Path Associated with the i-th Transition -Viterbi Decoder Path Memory to Previous States at time: t=k-j « I« . Trellis Transition XJ\XQ = i Figure 3.1: Depiction of a Viterbi Decoder's Decisions Made at the 0— and j— Memory Levels Chapter 3. Derivation of the Generalized Post-Detector 24 defined as: A Pr(xo = Tna) a0m = log p _ ^ , m = 0,... ,q - 1, m, € {0,... ,q - 1} (26) £o is a discrete random variable representing the roll-off symbol for a feed-forward encoder or the input symbol for a systematic feedback encoder. Equivalently, it may represent the corresponding path merging into the given state, m represents the possible values for the roll-off or input symbols ranging from 0 to q — 1. For an (n, k, m) code, q is equal to 2k. ms is the specific roll-off or input symbol associated with the surviving path merging into the given state. For an AWGN channel, if Mm and Mms are the trellis path metrics of a concurrent path and the survivor path merging into a given state, then the relative values respectively become: a0m = log = log = Mm- Mms 27 Hence, for each decision made at the decoder's 0— memory level (one for each possible trellis state), a vector a0 = [a0o, Qoi, • • • ,ao(g-i)] of relative values representing the re liability of that decision is generated. The relative value vector may be viewed as an alternative representation of the p.d.f. of the random variable x0. Rearranging (26) yields an expression for the probability of a specific path in terms of its relative value and the probability of the surviving path being traversed: Pr(x0 =m) = e~a0mPr{xQ = ms) (28) 3.2.2 Conditional Relative Values at the Decoder's j— memory level Following a similar procedure as was done for the 0— memory level, the relative values for decisions made in the past are now defined. Consider a decision made j symbols previously from the current decision conditioned on it being part of the i— path to a Chapter 3. Derivation of the Generalized Post-Detector 25 specified current state. Define: ,• A, Pr{Xj = ms\xn = i) .. ,„ . . As before the vector = [0^0,^1,... , a^^] is representative of the reliability of the decision made by the decoder. Rearranging (29) gives an expression for the probability of a specific path traversed j symbols in the past conditioned upon it being part of the current i— path: Pr(xj = m\x0 = i) = e~a^mPr(xj - ms\x0 = i) (30) For the derivation that follows, it is helpful to fully express Pr(xj = m\x0 = i) in terms of relative values. This is readily accomplished by noting that (due to a corollary from the theorem of total probability): 9-1 Pr(xj = k\x0 = i) = 1 (31) k=0 By using equation (30): 9-1 Pr{Xj = ms\x0 = i)J2 e~a)k = 1 (32) Pr(xj = ms\x0 = i)= 1 _ai (33) Now substituting this result back into equation (30) yields: —a1-6 Jm Pr{xj = m\xQ = i)= _ai (34) ELoe jk 3.3 Re-deriving Battail's Revision Formula From the theorem of total probability: 9-1 Pr(xj — i) = ^2 Pr(xj — i\xo = m)Pr(x0 — m) (35) m=0 Chapter 3. Derivation of the Generalized Post-Detector 26 At this point a slight change in notation is made to reflect the fact that as new deci sions are made, they are stored in the decoder's path history and all prior decisions are "shifted-up" in memory level by 1. Therefore (35) is rewritten as: 9-1 Pr(xj+i = i) = ^2 Pr(xj = i\x0 = m)Pr(x0 = m) m=Q Substitute (28), (34) into equation (36): <?-i r Pr(xj+1 = i) = Y, m=0 e J* LELo^J 9-1 p-a]l~ao" =0 Z^fc=0 e 3 {e-aomPr{x0 = ms)] Pr(xQ = ms) With i = ms (37) yields: Pr{xj+i =ms) = Substitute (37) and (38) into: 0-1 — -<»0rj =0ELoe 3k Pr(xQ = ms) «(i+i)i = log yields: 9_1 -a?i-a0m £ e a0'+i)« = lo§ Recall that by construction oJ^ms = 0,. m = 0,..., q — 1. Pr(Xj+i = z) 'f.1 e-aTms-"0m = 0 ££« ' a(i+i)i = log '9-1 V-> e~a0m - log la ^,-1 -a™ .™=°£Loe J*J (36) (37) (38) (39) (40) (41) Equation (41) describes how to "heuristically" revise the relative values of the sur viving paths given a Viterbi decoder's most recent decisions. This formula is applicable to any (n,k,m) code however, due to its complexity it is not very practical. Chapter 3. Derivation of the Generalized Post-Detector 27 3.4 Simplifying the General Revision Formula The problems with using equation (41) directly are two fold. First, the outright number of operations required is rather large. Secondly is the fact that many of those operation involve exponentials. To circumvent these problems, it is hoped that many of the terms in equation (41) can be approximated by simpler expressions without drastically affecting the quality of a posteriori input probability estimates. Indeed, this was the primary motivation for re-referencing the relative values to the surviving path since, by doing so, many of the operations can be eliminated. By using the following approximation to the sum of a set of exponentials: 9-1 e ik ~ e 1 ik' k=0 (42) Due to the re-referencing of the relative values to the surviving path, it follows that for k 7^ ras, djl > 0, while a™ms — 0. This implies that: 9-1 £ e-a7« « 1 fc=0 (43) Substitution into equation (41) yields: a(j+l)i log log 9-1 ^2 g —a0m. m=0 9-1 £ g j. Lm=0 g-mm{oom} e-min{aJl+aom} Similarly since for m / ms, a0m > 0, while arjms = 0: 1 (44) Oy+i)i W log -min{aYi+aom} (45) a(j+i)i « min {a^ + a0m} m=0...q—1 J (46) Chapter 3. Derivation of the Generalized Post-Detector 28 3.5 Finding a Revision Algorithm That is Post-Detector Compatible Equation (46) provides a relatively simple revision formula for any (n,k,m) code. As a soft-output Viterbi decoder selects a survivor merging into a particular state, it can use this formula to revise the stored relative values associated with the surviving path. However, since this operation is done for each surviving path entering into each possible trellis state, the number of revisions required will be quite large. Furthermore, this entails the storage of the relative value vectors associated with each of these surviving paths. Depending upon the hardware available this may not be very practical. One way to overcome these problems is to try to implement (46) as a "post-detector". The rational behind such a scheme is that if the decoder knows a priori what the globally best path is, it needs only to revise the relative values associated with that path. Why spend precious computational cycles on revising relative values of paths that shall never be emitted by the decoder? Furthermore, if one can eliminate from the revision operation any dependence upon the relative values of the concurrent paths then one only needs to allocate storage for the relative values of a single path. This unfortunately leads to a problem in using equation (46) as it stands for a post-detector. Referring to Figure 3.2, in which a revision operation using equation (46) is depicted, it becomes apparent that as one uses (46) to revise the relative values of a surviving path (at time t = k + 1) to a state that is part of the globally best path, one requires knowledge of the relative values of not only the survivor path (to state-6, at time t = k) but also of the concurrent paths (to states-a, c, d, at time t — k). This implies that at each time step, the decoder must still store and revise the relative values of each survivor to each possible trellis state. This forfeits any potential savings that might have been realized by using a post-detector architecture. If equation (46) can somehow be modified in such a manner so that the revision of the surviving path (at time t = k + 1) does not depend on the knowledge of Chapter 3. Derivation of the Generalized Post-Detector 29 Survivor Path Concurrent Paths State -> a ->b Allowed trellis transitions into state-a t=k t=k+l «00 tfoi «03 Relative values of surviving paths merging into each state attimet=k. Relative values of surviving path merging into state-a attimet=k+l. State "i a,-+i a(,-+i),;= min {a%+aom} m=0-3 Figure 3.2: Revision Operation Using Equation (46) Chapter 3. Derivation of the Generalized Post-Detector 30 concurrent paths (at time t = k) then the computational/storage savings hoped to be gained by using a post-detector architecture can be realized. Insight into finding the appropriate modifications can be gained by considering (46) for the (n, l,m) case and determining what necessary changes must be made in order that it meet the "post-detector" requirements outlined previously. It is hoped that these modifications will provide sufficient clues on how to adapt (46) into a "post-detector" compatible algorithm that may be applied to any (n,k,m) code. 3.5.1 Post-Detection Compatible Revision Algorithm for (n, l,m) Codes From equation (46): ay+i)0 = minfojo + ooo, ajo + floi} (47) a(j+1)1 = minfa^ + a0o , a]i + ^oi} (48) There are eight possible cases to consider: x0 = 0 or 1, Xj = 0 or l\x0 = 0, and Xj = 0 or 1\XQ = 1, where x denotes the decision made by a Viterbi decoder. The effect of these Viterbi decisions on the revision equations is shown in the following tables. Case 1 - (n,l,m) codes Case 2 - (n,l,m) codes Mem Lev Decision Implied Rel Val's Mem Lev Decision Implied Rel Val's 0 xo = 0 aoo = 0 0 x0 = 0 a0o = 0 3 £j = 0\xo = 0 Xj — 0\xo = 1 «°o = 0 a)0 = 0 j Xj = 0\XQ = 0 Xj = 1\£Q = 1 «}i = 0 Revision Equations for Surviving Path Revision Equations for Surviving Path a(j+i)o = 0 a(j+i)i = minfa^, a} + a0ij = min{a^, a01} Chapter 3. Derivation of the Generalized Post-Detector 31 Case 3 - (n,l,m) codes Case 4 - (n,l,m) codes Mem Lev Decision Implied Rel Val's Mem Lev Decision Implied Rel Val's 0 x0 = 0 a0o = 0 0 x o = 0 aoo = 0 3 Xj = l\xr, = 0 Xj = 0\XQ = 1 4=° ojo = 0 3 f j = l\xo = 0 = l|£o = 1 a^O a), = 0 Revision Equations for Surviving Path Revision Equations for Surviving Path a(j-+1)o = minja^o, a0i} a(j+i)0 = mm{a°j0, aj0 + a0i} °(j+i)i = 0 Case 5 - (n,l,m) codes Case 6 - (n,l,m) codes Mem Lev Decision Implied Rel Val's Mem Lev Decision Implied Rel Val's 0 x0 = 1 a0i = 0 0 £0 = 1 OQI = 0 3 = 0|^o = 0 £j = 0\XQ — 1 4 = 0 «jo = 0 3 = 0\xo = 0 = l\£o = 1 4 = o a), = 0 Revision Equations for Surviving Path Revision Equations for Surviving Path aO+i)o = 0 a(j+i)i = min{a^ + a00) ajj O(j+i)0 = min{a00, a}0} %'+!)! = 0 Case 7 - (n,l,m) codes Case 8 - (n,l,m) codes Mem Lev Decision Implied Rel Val's Mem Lev Decision Implied Rel Val's 0 x0 = 1 a0i = 0 0 £o = 1 a0i = 0 3 = l\xo — 0 ij - 0\XQ = 1 4 = 0 4 = ° 3 ij = l\xo = 0 fj = l|fo = 1 4 =0 Revision Equations for Surviving Path Revision Equations for Surviving Path aO+i)o = 0 %•+!)! = min{a0o, a}x} °>(j+i)o = min{a°0 + a00, a)0} °(i+i)i = 0 Chapter 3. Derivation of the Generalized Post-Detector 32 To find an algorithm that is compatible with the post-detection scheme presented in [3] it is necessary that revision depend only on the relative values of the surviving path and the most recent decision. This is true for cases: 2, 3, 6, 7 - when the decisions made at memory level-j were different. To uncover what additional approximations have to be made to make the other cases (when the decisions made at memory level-j were identical) post-detector compatible, consider case-1. According to the algorithms by Berrou et al. and Hagenaurer/Hoeher, revision is not necessary if both the concurrent and survivor paths yield the same decision. Therefore, in compliance with their findings, revision should not be necessary for case-1. Expressed in the notation used for this chapter this would imply: %+i)o = a% (49) flfj+i)i = aji In case-1, the revision equation for a(j+i)o satisfies (49) already since a°0 = 0. The revision equation for <2(j+i)i can be made to satisfy (49) if the a]x + a0i term is neglected. This is not entirely unreasonable since by construction all of the terms are positive. In essence, by neglecting this term, the assumption made is that the sum of two terms will always be greater than a single term. Examination of cases 4, 5, and 8 show that they too can be made post-detector compatible by making this same assumption. The resulting revision equations follow: Chapter 3. Derivation of the Generalized Post-Detector 33 Case 1 Case 2 "0+i)o = "°o 00+1)1 = "°i aO'+i)o = a% "0+1)1 = min{"°i> a°i} Case 3 Case 4 "0+1)0 = minja^o, a0ij "0+i)i = "°i "0+i)o = a°jo "0+1)1 = a°i Case 5 Case 6 "0+i)o ~ ajo "0+1)1 = "]l a(j+i)0 = min{a0o, a)0} "0+i)i = a)i Case 7 Case 8 aO+i)o — "}o "0+1)1 = min{a0o, a^} "0+i)o = "}o "0+i)i = a]i This can be shown to be the exact same algorithm, given notational differences, as the one proposed by Berrou et al. in [3] for their post-detector. To summarize, it was discovered that by using the revision equation (46) for binary (n, l,m) codes, and by applying the assumption that the sum of two terms is always greater than a single term, it was possible to derive a revision algorithm (or set of equations in this case) that was post-detector compatible. It now remains to be shown that by using the same equation for the more general case of (n,k,m) codes and by applying the same assumption, this will also result in a post-detector compatible revision algorithm. Chapter 3. Derivation of the Generalized Post-Detector 34 3.5.2 Post-Detection Compatible Revision Algorithm for (n, k, ra) Codes To derive a revision algorithm for the non-binary (n, k, m) case a procedure similar to that for the binary (n, l,m) case is followed. The case where k = 2 is used to illustrate the effects of the assumptions made. This will keep the number of terms that must be considered in the case studies reasonable. Since none of the assumptions made will be specific to the case where k = 2 the resulting algorithm should be applicable to the more general case. For an (n,2,m) code, equation (46) yields: a(j+i)0 = min{a^0 + a0u , a}0 + a0i, a2j0 + a02 , a30 + a03} ay+iji . = minfa^ + a00 , a)x + a0i, a]x + a02 , a)x + a03} (50) ay+1)2 = min{a°2 + a00 , a)2 + a0i, aj2 + a02 , a32 + a03} ay+i)3 = min{a^3 + a00 , aj3 + a0i, aj3 + a02 , a% + a03} Is Revision Necessary if All Antecedents Yield The Same Decision? Although, with increasing k, this scenario becomes less likely early on in the Viterbi decision process, it is still applicable once all of the surviving paths have merged at some arbitrary memory depth ([12] implies that this usually occurs within 5 constraint lengths). This prevents the decoder from performing revision over the entire decoder memory. It will only be done where it is "necessary" to achieve satisfactory a posteriori information. Consider the following case studies: Chapter 3. Derivation of the Generalized Post-Detector Case 1 - (n,2,m) codes Mem Lev Decision Resulting Known Rel Val 0 x0 = 0 aoo = 0 3 cbj = 0\xo = 0 Xj ' 0\XQ = 1 Xj = 0\xo = 2 Xj = 0\XQ = 3 a% = 0 a]0 = 0 a% = 0 a% = 0 Resulting Revision Equations for Surviving Path Observations o(j+l)0 = 0 = 4 aC?+i)i = min {a0^ + aoi, 4 + ao2 , a|i + a03} *4 a0+l)2 = min{a°2 . 4 + a0i, a?j2 + a02 , a3j2 + a03} «4 a0+l)3 = min{a°3 > 4 + OQI , a?j3 + a02 , a3j3 + a03} «o?3 Case 2 - (n,2,m ) codes Mem Lev Decision Resulting Known Rel Val 0 x0 = 0 a0o = 0 3 ij = l|xo = 0 Xj = l|xrj = 1 Xj = l|£o = 2 i^' = 1|XQ = 3 4 = ° a), = 0 4 = o Resulting Revision Equations for Surviving Path Observations °0'+i)o = mhi{a5o . 4 + a0i, fljo + a02 , a3jQ + a03} «a°0 ao+i)i = 0 a(j + l)2 = min{a?2 > 4 + aoi, o?j2 + ao2 , o?j2 + a03} a(j+l)3 = min{a°3, a}3 + a0i, a2j3 + a02 , a?j3 + a03} «4 Chapter 3. Derivation of the Generalized Post-Detector 36 From the previous two examples it can be seen that if the assumption that the sum of two relative value terms is always greater than a single relative value term then revision is not necessary when all of the "antecedents" (surviving paths to each allowed state at the previous time step) yield the same decision. Stated in another way, once all of the surviving paths to each state in the trellis have merged, say at memory level-/, then no revision is necessary beyond this point. Revision Algorithm for Case When All Paths Do Not Yield The Same Deci sion To determine the revision algorithm when the antecedents do not all yield the same decision, it is convenient to place all of the terms of equation (50) in a revision matrix: -So + aoo + am a% + a02 + a03 + a00 + aoi + a02 + a03 aj2 + aoo + a0i ah + a02 ah + a03 aj3 + a00 ah + aoi a% + a02 a% + a03 (51) Suppose the most recent decision to a given state is XQ — i, then ao, = 0. This leaves only the a^k terms in column i+l of matrix (51). Since, in the resulting revision algorithm, the assumption is made that the sum of two relative values will always be greater than any single relative value, this implies the dependency of the resulting algorithm on the relative value terms of the surviving path (at time step t = k). Now consider the case where the n— path yields the following decision: £j = l\x0 = n. This leads to a"; = 0 which eliminates a term in the I + 1th row and n + 1th column leaving only the a0n term. Therefore, the decisions made on the preceding paths at the j— level indicate which relative value terms a0n are relevant in making the current revision. The following example illustrates this finding: Chapter 3. Derivation of the Generalized Post-Detector 37 Example - (n,2,m) codes Mem Lev Decision Known Rel Val 0 x0 = 1 001 = 0 3 Xj = 3\$o = 0 a°3=0 Xj = Q\xo = 1 0J0 = 0 £j = 2\xo = 2 a% = 0 £j = 2\XQ = 3 af2 = 0 Resulting Revision Equations for Surviving Path Post-Detector Revision Equations O(j+l)0 = min{a?0 + aoo , 0 + 0, aj0 + a02 , a3j0 + a03} = min{a}0, a0i} = minfa^ + a00 , a)x + 0, a?x + a02 , + 0-03} ~a}i °U+1)2 = min{a°2 + a00 , a)2 + 0, 0 + a02 , 0 + a03} « min{a)2 , a02 , a03} a0'+l)3 = min{0 + a00 , a}3 + 0, a?3 + a02 , a?3 + a03} « min{a}3 , a00} Note that the approximate revision algorithm only requires knowledge of the surviving path's relative values {a^0, ajx, a^2, aj3} and the relative values corresponding to the most recent decision {aoo > &01 > a02 , 003}- Hence this algorithm appears to be the M-ary equivalent of the algorithm presented by Berrou et al. in [3]. By comparing the decisions made by the decoder with the resulting revision equations a pattern becomes apparent. This pattern leads to the revision algorithm outlined in Figure 3.3. 3.6 Application Considerations 3.6.1 Deducing Input Probabilities From Relative Values To this point consideration has only been given to the problem of finding an efficient method of revising the relative values derived from a Viterbi decoder's decisions. As mentioned previously, to deduce the a posteriori probabilities of the encoder's input bits Chapter 3. Derivation of the Generalized Post-Detector 38 Possible trellis transitions into given state. Surviving state at time t=k as determined byapre-detector. t=k t=k+l Relative values of path merging into state-y at time t=k. Relative values of path merging into state-z at time t-k+1 HU Generalized post-detection compatible algorithm —* To update a0+1), given that x0 = s (ie no, = 0), If all paths merging into the current state yield the same decision at memory depth j then: No revision is necessary. Seta(y+i), = <^. else Are any of the decisions made, at memory depth j, on the possible merging paths equal to index i ? No -» No revision is necessary. Set fl(y+i)j =aj. Yes -» Say on paths mx and m2. Revision is required. Set = min{ajj,aomi,aom2}• (end). Figure 3.3: Generalized Revision Algorithm for Post-Detector Chapter 3. Derivation of the Generalized Post-Detector 39 rate 3/4 encoder modulo-2 summing network Signal Mapper o-SOVA Gaussian Channel o- post-delector Vilerbi Decoder delay line Figure 3.4: Rate 3/4 SOVA system or symbols from the relative values, one must consider the structure of the encoder. To illustrate how this is accomplished consider the following two examples. Example 1: Feed-Forward Encoder Consider finding the a posteriori input bit probabilities for the rate-| system depicted in Figure 3.4. Suppose the SOVA outputs the following relative value vector at time t = k: Ofc = [OfcO) akli <2*:2, Ofc3) ak4, &fc5> ak6, Ukl] If the paths merging into each state were identified using the shift-register "roll-off" symbol then: . P(xk = 0) P{bk0 - 0, 6(fc_2)1 = 0, 6(fc-i)2 = 0) Qfco = log 777- -r = log P{xk = ms) P(bk0 = ms0, 6(fe_2)i = msi, b(k-i)2 = ms2) Chapter 3. Derivation of the Generalized Post-Detector 40 Therefore P(xk=l) P{bk0 = 0) l\bko=0 7 £ e~afc< i|fcfco=0 7 P(&fc0 = 1) 1 - P(bk0 0) Similarly it is possible to deduce P(/3(fc_2)i = 0) and P(b^-i)2 = 0). To determine P(bki = 0) and P(bk2 = 0) one must use the relative value vectors afc+2 and afc+1 re spectively. This implies that one must buffer several relative values vectors after the completion of revision or use relative value vectors that may not have been fully revised. The latter situation should be acceptable so long as the revision memory is sufficiently long such that all concurrent paths have merged for D symbols prior to symbol output -where D is the maximum length shift register. Note that it is not possible to determine the a posteriori input symbol probabilities for this encoder since the shift-registers are of differing lengths. Example 2: ISI Channel Consider finding the a posteriori input symbol and bit probabilities for the ISI channel shown in Figure 3.5. Because the signaling constellation is 8-PSK, the relative value vector will have 8 components: &k — [flfcOj afcl) Qfc2) ak3, <2fc4> <2fc5, Ofc6, ak7. Chapter 3. Derivation of the Generalized Post-Detector 41 buf>~ bkp-bkP 1 8PSK Signal Mapper at* Sk CO Soft-Output Viterbi EQ (SOVE) R —0 c\—0 c2—® Gaussian Channel Figure 3.5: Rate-3 Soft-Output Viterbi EQ system For this case the shift-register "roll-off" symbol is just the ISI channel input symbol offset by two time periods. Therefore given that: . P(xk = 0) P(sfc_2 = 0) GfcO = log r = log P(xk = ms) the 0-symbol probability may be found by: P(Sk-2 = 0) P{bk-2 = ma) P(sk-2 = 0) P(sk-2=0) P{sk-2=™-s) _ e E P(sk-2 = 1) E Ee-0 p(**-a=m') /=0 The probabilities for the other symbols can be calculated similarly. Determining the a posteriori input bit probabilities probabilities is a fairly straight forward procedure given knowledge of the mapping used by the modulator. They can either be calculated directly as was done in Example-1 or calculated from the a posteriori input symbol probabilities. For these simulations the mapping used is shown in Table 3.1. Chapter 3. Derivation of the Generalized Post-Detector 42 &0M2 ->• sn:an + j(3n 000 -> 0 : +cos(22.5°) -;sin(22.5°) 001 -> 1 : -sin(22.5°) + jcos(22.5°) 010 -> 2 : + cos(22.5°) + ;sin(22.5°) on -)• 3 : +sin(22.5°) + jcos(22.5°) 100 -> 4 : -cos(22.5°) + j sin(22.5°) 101 ->• 5 : +sin(22.5°) - jcos(22.5°) 110 ->• 6 : -cos(22.5°) - jsin(22.5°) 111 -»• 7 : -sin(22.5°) -;'cos(22.5°) Table 3.1: Signal Mapping used by the 8-PSK Modulator. Using the a posteriori input symbol probabilities, P(b<k-2)o) may be found by: P(6(fc-2)0 = 0) = P(5fc_2 = 0) + P(sfc_2 = 1) + P(sk-2 = 2) + P(sfc_2 = 3) P(6(fc-2)0 = 1) = l-P(6fc-2=0) The probabilities for P(/3(fc_2)i) and P(b^-2)2) can be found in a similar manner. 3.6.2 Examining the Effects of the Approximations Made During the derivation of the generalized post-detection algorithm several approximations were made to arrive at a simple expression. It may be interesting to determine how these approximations affected the "physical" meaning of the equations. The unsimplified revision equation (equation (40)) can be rearranged as follows: e°o+i)i = Pr(xj+i - mt) Pr(zj+i = i) Pr(x0 = ms) Pr(x0 = ms) (52) For the time being consider only the denominator terms. Pr(xj+i — i) i e-aomPr{x0 - ms)] (53) ljk m=0 Chapter 3. Derivation of the Generalized Post-Detector 43 ^-1 Pr(xj = i\x0 = ra) rr^o lpr(xj = ms\x0 = m)\ [Pr(xj = ms\x0 = ra)] [Pr(x0 = ra)] The first approximation made during the derivations was as follows: 1 \ 1 1 XLoe lk. le jfc J , where a£, <aJkVk,k^k' (54) Since by construction the survivor's relative value a™k, — 0: Pr(xj = ms\x0 — ra) « 1 (55) This implies that given knowledge of the encoder's most recent decision, the decoder is certain of the encoder's decision j symbols previously. Stated another way, the decoder assumes it made the correct decision j symbols in the past. Applying this same assumption to the numerator as well the denominator leads to the following equation: eao+i)i Pr(xj+i = ms) E[e-aOmPr(i0 = ms)] m=0 Pr(xj+l - l) ^ [e-«£][e-aompr(£0 = ms)] (56) m=0 The next approximation made involved the numerator of this equation. 9-1 53 e_a°m « e~a°m', where a0m' < a0m Vm, ra ^ m' m=0 Once again, by construction, a0m> = 0. Therefore, g Pr(£0 = ra) _ 1 (57) m=0Pr(^0 = ms) 9-1 53 -Pr(£() = "l) ~ Pr(xo = ms) m=0 This implies that: Pr(x0 = ms) » Pr(xo = ra) , Vra, ^ m. (58) (59) (60) Chapter 3. Derivation of the Generalized Post-Detector 44 Determining the physical meaning of the approximations made beyond this point be comes quite difficult. However, the two assumptions that have been uncovered (equations (55) and (60)) do provide some indication of what conditions are required for the derived algorithm to work well. The two assumptions are generally true for codes with good dis tance qualities and high SNR. Since most system designers generally choose such codes and operate at moderate signal strengths these conditions should not pose any problems for systems such as concatenated coding where the inner code is a convolutional code or a TCM code. However, these conditions also suggest that the new revision algorithm may not be suited for applications such as Viterbi equalization where the channel may not necessarily conform to a "good code". To determine if this is true, computer simulations would have to be performed. 3.6.3 Computational and Storage Requirements Because of the generalized post-detector's dependency upon the Viterbi algorithm, the computational and storage requirements of the standard Viterbi decoder shall be re viewed. The additional resources required to implement the generalized post-detector shall then be discussed. The results will be compared with the resource requirements of the MAP algorithm and the Best-Path algorithm. Consider a typical (n, k, m) convolutional code. The trellis diagram of this code will have 2m states. If 8vtb represents the length of the past history memory of the corre sponding Viterbi decoder then Svtb • 2m storage elements (most likely integer quantities) for the path history arrays will need to be allocated. In addition, 2m additional storage elements (typically floating point quantities) are required to hold the metrics of each of the surviving paths. The Viterbi decoding process involves for each received symbol: 2" branch metric calculations followed by 2m • 2fc additions for path metric calculations. In addition, 2m Chapter 3. Derivation of the Generalized Post-Detector 45 comparisons of 2k path metrics are required for the selection of the surviving paths to each state. If it is assumed that a comparison of 2fc items can be accomplished by 2fc — 1 binary comparisons then that leads to a requirement of 2m(2k — 1) binary comparisons per received symbol. These results are summarized in Table 3.2. The exact number of additions/multiplications for the branch metric calculation will not be considered as it depends on the specific application - most notably, the type of modulation used. However, since all of the decoding methods to be considered here require the computation of a similar quantity, it can be considered as a constant computational overhead that is not a factor when selecting between the various algorithms. .The addition of the generalized post-detector derived in Chapter-3 will entail a second Viterbi decoder to calculate the path metrics for the relative value calculations. If the post-detector has a path memory of length 8pd the this will require an additional 5pd • 2m storage elements for path histories to each state. As in the standard Viterbi decoder each storage element must store the input symbol decision. However, if a feed-forward code is used, the roll-off symbol will also have to be stored. Hence the required storage for the path history arrays is 25pd • 2m (probably integer quantities). As before, 2m elements for path metric storage (floating point quantities) are required. The relative value arrays require Spd • 2k elements (floating point). Viterbi Storage Requirements Integer Floating-Point 2m Viterbi Computational Requirements Binary Compares Binary Add./Sub. Branch Metric Calculations 2m(2fc - 1) 2m2fc 2" Table 3.2: Computational/Storage Requirements For a Typical Viterbi Decoder. Chapter 3. Derivation of the Generalized Post-Detector 46 Additional Storage Required for Implementing a Post-Detector Integer Floating-Point 26pd2m 2m + 8pd2k Additional Computation Required for Implementing a Post-Detector Operation Binary Compares Binary Add./Sub. Brnch Met Calc's Exp. Mult./Div. Viterbipd 2m(2fc - 1) 2m2fc 2™ r.v. calc. 2fc Rev. Nec. ? Spd(2k - 1) Comp. Past Dec. (Spd • 2k)2k Select Min. (Spd • 2fe)2fc Calc Pr(sym) 2fc - 1 2h 2fe Table 3.3: Additional Computation/Storage Required to Imple ment and Add a Generalized Post-Detector. Computation requirements for the second Viterbi consist of performing the following for each received symbol: 2n branch metric calculations, 2m • 2fc binary additions for path metric calculations, and 2m(2fc — 1) binary comparisons. The calculation of the relative value vectors consist of 2h subtractions per received symbol. To determine where revision is necessary, 5pd(2h — 1) comparisons are required. Assuming it is necessary for the entire path history length, this should impose at most 5pd • 2k revisions each consisting of 2k comparisons to examine the branch decisions made in the past, followed by at most 2k binary comparisons for the "select min" operation. To obtain a normalized "roll-off" symbol probability that may later be used to deduce the input bit a posteriori probabilities will require 2k exponentials, 2k — 1 additions, followed by 2k divisions. These incremental computational costs are summarized in Table 3.3. The overall computational requirements of implementing a SOVA utilizing the gener alized post-detector algorithm can be determined by adding the various quantities pre sented in Table 3.2 and Table 3.3. For example, the number of binary additions required Chapter 3. Derivation of the Generalized Post-Detector 47 Generalized Post-Det. MAP Algorithm Best-Path Alg. Storage: Integer (<W + 25pd)2m Float-Point 2(2m) + 6pd2k Lmsg{2m + 1) Lmsg{2m + 1) Computation: Binary Compares 2m+1(2k - 1) + Spd(2'2h+1 + 2k) 2m+1(2fe - 1) Binary Add./Sub. 2m+l2fc _|_ 2k+l - l 2m+1(2fc - 1) 2(2m+12fc) Brnch Met Calc's 2n+l 2n 2n Exponentials 2k 2n 2m2fc Mult./Div. 2fe 2(2m+12fc) Table 3.4: Comparison of the Computation Requirements of Vari ous Soft-Output Decoder Algorithms. is: 2m2fc + 2m2k + 2k + 2k -1 = 2m+12k + 2k+l - 1 (61) whereas the number of comparisons necessary has been approximated by: 2m(2fc - 1) + 2m(2fc - 1) + Spd{2k - 1) + (Spd • 2k)2k + (6pd • 2k)2k « 2m(2fc - 1) + 2m(2fc - 1) + 6pd • 2k + (5pd • 2k)2k + (5pd • 2k)2k « 2m+1(2fc-l) + r5pd(22'c+1 + 2fc) (62) The number of branch calculations is 2n+1. The number of exponentials and multiplica tion/division operations necessary each remain at 2fc. These results along with the compu tation and storage requirements of the MAP and Best-Path algorithms (see Appendix-C) are shown in Table 3.4. By substituting the appropriate hardware and system parameters into Table 3.4, a system designer can determine which soft-output algorithm is most suited for his par ticular application. For example, suppose the available hardware can perform a binary comparison in one time unit, a binary addition in one time unit, and a binary multiplica tion in four time units. A time unit being defined as the duration of the fastest of those Chapter 3. Derivation of the Generalized Post-Detector 48 three operations. Also, if a generalized post-detector is used, the decoders are to have a path memory of 5vtb — Spd = 5m. (This should be sufficient since a code's constraint length is equal to at most m.) Finally, the transmitted sequence length in symbols is LmSg = 256. Then the computational and storage costs of the various algorithms can be compared by examining Figure 3.6 and Figure 3.7. In Figure 3.6, the amount of memory required to store the integer variables and the floating-point variables is assumed to be the same. Figure 3.6 depicts the amount of these "generic" storage elements required to implement the decoder versus code memory m and number of input bits k. Figure 3.7 depicts the amount of computation time required per decoded symbol vs. code memory m and number of input bits k. In Figure 3.7 the calculations of the branch metrics and exponentials were assumed to be performed by table lookup resulting in negligible computational costs. A word of caution must be noted when interpreting the various tables and graphs. The actual amount of computation required depends not only on the number of additions, compares, multiplications, etc, but also on many other factors which are implementation specific. Just to name one, the tables and graphs did not take into account whether various operations were performed on integer or floating point quantities. The ratio of integers to floating-point variables required can be heavily influenced by the specific implementation and by constraints imposed upon the designer by the available hardware. Also note that the time required to move data from one storage location to another was completely neglected. The tables and graphs shown should only be used to provide a rough estimate of the amount of computation/storage required. If a designer can meet his computational/storage "budget" using worst case values for each operation (most likely floating point operations) then he can be fairly confident that the algorithm being considered can be implemented with the hardware at hand. Chapter 3. Derivation of the Generalized Post-Detector MAP or Best-Path Decoder vs Viterbi Decoder Generalized Post-Detector vs Viterbi Decoder MAP or Best-Path Decoder vs Generalized Post-Detector Num. input bits - k Figure 3.6: Comparisons of Algorithm Storage Requirements Chapter 3. Derivation of the Generalized Post-Detector MAP Algorithm vs Best-Path Algorithm vs Standard Viterbi Algorithm Generalized Post-Detector vs Standard Viterbi Algorithm Generalized Post-Detector vs Best-Path Algorithm Generalized Post-Detector vs MAP Algorithm Figure 3.7: Comparisons of Algorithm Computational Requirements Chapter 4 Evaluating Performance of The Generalized Post-Detector 4.1 Introduction To determine how well the proposed post-detection algorithm would perform in actual practice, a computer model of a post-detector decoder was created. Simulations of various concatenated systems were performed covering a range of codes, signaling constellations, and channels. The simulations were arranged in sets such that each suite would vary a single system parameter such as the choice of inner code or choice of signaling constella tion. In this way it would be possible to isolate the effects of each of these parameters on the post-detector's performance. The results of these simulations are described in the following sections. In those sections, the results of the simulations are presented in the form of a graph depicting the resultant bit error rate (BER) vs SNR per input bit of the post-detection system. For comparison, the performance curve of the optimum serially concatenated system, as predicted by the graphical procedure described in [3] and Appendix-B, is also provided. In addition, the performance curve of a corresponding system not utilizing a soft-output inner decoder is also shown. The codes and channels used for each of the simulations are referred to by a code or channel label such as cc2_3.df4 or isi2.70.30. cc2_3.df4 represents a a rate-| convolutional code with a free distance dfree = 4 bits. Whereas isi2.70.30 represents an ISI channel with two taps: 70% of the received signal energy is transmitted via the first path while 51 Chapter 4. Evaluating Performance of The Generalized Post-Detector 52 30% of the energy is transmitted via a second delayed path. The delay is set to the symbol transmission interval. Unless otherwise stated, the channel tap weights are real (as opposed to complex value quantities). The generator matrices of each code and the tap weights of each ISI channel used for the simulations described in this thesis can be found in Appendix-C. All of the computer models were created in C using the GNU C compiler. The code was compiled and run on either a Sun Sparcstation running SunOS 4.1.3, an AMD 486DX2-80 running FreeBSD 2.0.5, or a Cyrix 5x86-120 also running FreeBSD 2.0.5. In many cases, the same simulations were run on more that one computer system to verify the results. For all of the graphs shown, each point represents the transmission of at minimum 100000 bits and the counting of at least 400 bit errors in the received data stream. In order for a simulation to stop it had to meet both of these conditions. This should provide a sufficient number of error events to ensure statistical significance. 4.2 Effects of Code Free Distance on the Estimates of the A Posteriori Prob abilities To determine what effect code free distance has on the quality of the a posteriori proba bilities generated by the post-detector, the simple concatenated coding scheme depicted in Figure 4.1 was implemented through software. Three convolutional codes with differ ent free distances were selected for the inner code. To reduce the likelihood of selecting an outer code that was relatively insensitive to poor a posteriori probability estimates, three different convolutional codes were selected for the outer code. Every combination was implemented resulting in the nine graphs shown in Figures 4.2 - 4.4. Figure 4.2 shows the three cases where the inner code was set to cc2_3.df3. Figure 4.3 and 4.4 show the results of the simulations for the cases when the inner codes were fixed at cc2_3.df4 Chapter 4. Evaluating Performance of The Generalized Post-Detector 53 and cc2_3.df7 respectively. For each simulation, a block type interleaver was used. The interleaver depth and width were each set to a value much greater than either of the codes constraint lengths and free distances. The modulation used for every case was BPSK. Transmission was through an AWGN channel. The revision history of the post-detectors and the path history memory of the Viterbi decoders were set to a value much greater than five times either of the code's constraint lengths (> 20x). Observe that all of the curves seem to show a similar result. As expected for a sub-optimal algorithm, the performance curve of the concatenated system using the proposed post-detector derived in Chapter-2 deviates from the ideal graphical prediction. This deviation can be characterized by a gradual "pulling away" from the ideal case as SNR increases. However, this deviation is quite small: less than 0.2 dB from the ideal case at bit error rates of 10-4. This is quite acceptable when compared to the gain made over the system using a hard-output inner decoder. The graphs indicate that there does not seem to be a simple relationship between the code free distance and the quality of the a posteriori information produced. The simulations do imply however that it should be possible to use the proposed post-detection algorithm on a variety of different convolutional codes regardless of the inner code's free distance. Chapter 4. Evaluating Performance of The Generalized Post-Detector M=[mo,mu--,mK-\] «j,e {0,1}, i = 0,--,K-l X=[Xo,X\,--;XN-\] Xie {0,1}, i = 0,.--,JV-l Outer Convolutional Encoder Viterbi Decoder Block Interleaver Inner Convolutional Encoder X=[x0,X\,--,XN-[] ii 6 {0,1}, ;'= 0, • •-JV-1 Block De-interleaver M= [mo, mi, • ••,m K-\] fhiG {0,1}, i = 0,---,K-\ Generalized Post-Detector BPSK Modulator Viterbi Decoder Delay Line AWGN [P] = P(x0=0\R) P(Xx=0\R) ••• P(xN^=0\R) P(x0 = l\R) P(x\ = l\R) ••• P(xN-i = l\R) Figure 4.1: Concatenated Coding System Using Convolutional Codes for Both the Inner and Outer Codes. Chapter 4. Evaluating Performance of The Generalized Post-Detector 55 10u 10° 10'2 103 10-4 106 10'6 10"7 Inner code: cc2_3.df3 Outer code: cc3_4.df4 Modulation: BPSK Perfect reliability estimation o Generalized SOVA post-det *——* No reliability info available -2.0 -1.0 0.0 1.0 2.0 3.0 4.0 5.0 6.0 E,/N0 (dB) 10 lO"' 10'2 10* 10"" h 10 10 10 Inner code: cc2_3.df3 Outer code: cc3_4.df6 Modulation: BPSK — Perfect reliability estimation o Generalized SOVA post-det -* No reliability info available -2.0 -1.0 0.0 1.0 2.0 3.0 4.0 5.0 6.0 10 10"' 10"2 10'3 10'4 lO"5 106 10"7 Inner code: cc2_3.df3 Outer code: cc7_8.df2 Modulation: BPSK Perfect reliability estimation o Generalized SOVA post-det *-—* No reliability info available -2.0 -1.0 0.0 1.0 2.0 3.0 4.0 5.0 6.0 7.0 8.0 E./N. (dB) Figure 4.2: Performance of Various Concatenated Systems Utilizing an Inner Code with dfree = 3 (channel: AWGN). Chapter 4. Evaluating Performance of The Generalized Post-Detector 56 10" iff1 10"2 10"3 lo in6 10e io-7 Inner code: cc2_3.df4 Outer code: cc3_4.df4 Modulation: BPSK Perfect reliability estimation ° Generalized SOVA post-det *—No reliability info available -2.0 -1.0 0.0 1.0 2.0 3.0 4.0 5.0 6.0 E,/N0 (dB) 10 10° 102 IO"3 10"4 105 10* 107 Inner code: cc2_3.df4 Outer code: cc3_4.df6 Modulation: BPSK Perfect reliability estimation o Generalized SOVA post-det •*——* No reliability info available -2.0 -1.0 0.0 1.0 2.0 3.0 4.0 5.0 6.0 E,/N0 (dB) 10 IO"1 10* 10"3 10'4 IO* 10'6 10'7 Inner code: cc2_3.df4 Outer code: cc7_8.df2 Modulation: BPSK Perfect reliability estimation o Generalized SOVA post-det * * No reliability info available -2.0 -1.0 0.0 1.0 2.0 3.0 4.0 5.0 6.0 7.0 8.0 Figure 4.3: Performance of Various Concatenated Systems Utilizing an Inner Code with dfree = 4 (channel: AWGN). Chapter 4. Evaluating Performance of The Generalized Post-Detector 57 10 IO"' 10'2 10"3 IO'4 106 10e 10'7 ;"::«"ll«:;iH"::::::H!!:::r--"::;:;l::;;::-::4::!::J:::t::l::d::: Inner code: cc2_3.df7 Outer code: cc3_4.df4 Modulation: BPSK Perfect reliability estimation o Generalized SOVA post-det *—j-* No reliability into available -2.0 -1.0 0.0 1.0 2.0 3.0 4.0 5.0 6.0 10 10' 10'2 10"3 10"4 106 106 10'7 Inner code: cc2_3.df7 Outer code: cc3_4.df6 Modulation: BPSK — Perfect reliability estimation o Generalized SOVA post-det -* No reliability info available -2.0 -1.0 0.0 1.0 2.0 3.0 4.0 5.0 6.0 Et/N. (dB) 10" IO"1 102 10'3 10'4 10"5 10"6 10'7 Inner code: cc2_3.df7 Outer code: cc7_8.df2 Modulation: BPSK Perfect reliability estimation o Generalized SOVA post-det * * No reliability info available -2.0 -1.0 0.0 1.0 2.0 3.0 4.0 5.0 6.0 7.0 8.0 Eb/NJdB) Figure 4.4: Performance of Various Concatenated Systems Utilizing an Inner Code with dfree = 7 (channel: AWGN). Chapter 4. Evaluating Performance of The Generalized Post-Detector 58 4.3 Effects of Signaling Constellation on the Quality of the Estimates of the A posteriori Probabilities To determine whether increasing the size of the signaling constellation would have any effect on the quality of the reliability information, software simulations of the concate nated CC/TCM system shown in Figure 4.5 were performed. Three simulations were performed. The first used coded 8-PSK modulation for the inner code, the second coded 16-QASK, while the third used coded 32-CROSS. Transmission was over an AWGN channel. The results, shown in Figure 4.6 are quite similar to the results obtained in the previous section: a gradual increasing deviation with increasing SNR from the ideal graphically derived curve. As before, the deviation is small when compared to the gain made over the system utilizing the conventional Viterbi decoder for the inner code. The graphs suggest that the proposed generalized post-detection algorithm should work reasonably well for a variety of different coded signaling constellations. Chapter 4. Evaluating Performance of The Generalized Post-Detector M= [mo /«, e {0 O,/MI, •••,mK-i] "\ ,1}, i = 0,-,K-l) Outer Convolutional Encoder X=[Xo,Xi,- -,XN-\] xte {0,1}, i = 0, Block Interleaver Inner TCM Encoder X=[x0,X\,---,XN-i] xt e {0,1}, / = 0, • •-TV-1 Viterbi Block De-interleaver Generalized Post-Detector Decoder Signal Mapper Viterbi Decoder! Delay Line AWGN R = [ro,r\,---,ry-\] M=[m0,rhlt--;mK-i] rhi& {0,1}, i = Q,--,K-\ [P] = P(x0=0\R) P(XI =0\R) P(X0 = I\R) P(xi = l\R) P(xN-i =0\R) P(xN-i = l\R) Figure 4.5: Concatenated Coding System using Multi-Level Modulation for the Inner Code. Chapter 4. Evaluating Performance of The Generalized Post-Detector 10 10" 10'2 IO"3 10"4 10'6 10E IO"7 Inner code: cc2_3.tcm Outer code: cc3_4.df4 Signal set: 8-PSK Perfect reliability estimation o Generalized SOVA post-det * * No reliability info available -2.0 -1.0 0.0 1.0 2.0 3.0 4.0 5.0 6.0 7.0 8.0 E,/N0 (dB) 10 10" 10* 10"3 10"4 IO'6 10° 10'7 Inner code: cc3_4.tcm Outer code: cc3_4.df4 Signal set: 16-QASK — Perfect reliability estimation o Generalized SOVA post-det -* No reliability info available -2.0 -1.0 0.0 1.0 2.0 3.0 4.0 5.0 6.0 7.0 8.0 9.0 1 0 ni:M:!H:!:<:*:^±:V:*:b!t:l:!:!:i:J:J: 10 10'2 103 10"4 10'5 10'6 10"7 ililil;!;!:!;!:!:!:^^^**^:^!:!:!;!;!!!:!:!:^!:^-.:*.-.:!:!!!: Inner code: cc4_5.tcm Outer code: cc3_4.df4 Signal set: 32-CROSS Perfect reliability estimation o Generalized SOVA post-det * * No reliability info available -2.0-1.0 0.0 1.0 2.0 3.0 4.0 5.0 6.0 7.0 8.0 9.0 10.011.0 E,/N.(dB) Figure 4.6: Effect of Different Signal Constellations on the Quality of Soft-Output Information (channel: AWGN). Chapter 4. Evaluating Performance of The Generalized Post-Detector 61 4.4 Determining Performance of the Generalized Post-Detector for use in Soft-Output Viterbi Equalizers To determine if the proposed post-detection algorithm can be used for implementing a soft-output Viterbi equalizer, the concatenated systems shown in Figure 4.7 and Figure 4.9 were tested via computer simulations. For these simulations, the soft-output Viterbi equalizers (SOVE) were given full knowledge of the channel tap weights. The channel tap weights were invariant with time. The interleaver depth and width were set to values much greater than the constraint length of either the "outer" code or the ISI channel. The post detector revision length and Viterbi decoder path memories were all much greater than five times the constraint length of either the code or the channel. The first suite of simulations was used to determine the effects of the different ISI channel tap weights on the quality of the a posteriori information produced by the soft-output Viterbi equalizer. For these simulations, binary data was encoded using the convolutional code cc2_3.df4 and transmitted over the various ISI channels using 8-PSK modulation. The deduced a posteriori 8-PSK symbol probabilities were used to calculate a posteriori input bit probabilities of the modulator. These bit probabilities were in turn used for the decoding of the convolutional code. Hence, the convolutional code was decoded as if binary modulation had been used - even though, the probabilities themselves were originally deduced using the received 8-PSK symbols. The ISI channel was comprised of two taps only. The delay between the taps was one 8-PSK symbol interval. The results of these simulations are depicted in Figure 4.8. Observe that the quality of the soft-output information appears to degrade with increasing ISI. However, even for the worst case scenario (two taps of equal weight), the degradation is not too severe. Therefore the simulations indicate that for moderate levels of ISI the quality of the a Chapter 4. Evaluating Performance of The Generalized Post-Detector 62 posteriori probability estimates is quite good. For the second suite of simulations a three tap ISI channel is used for the inner code. In addition, the outer encoder is replaced by a TCM modulator (coded 8-PSK). As a result, the outer decoder would need to have knowledge of the a posteriori input symbol probabilities (as opposed to the bit probabilities used for the first suite of simulations). Results from the second suite of simulations are shown in Figure 4.10. For compar ison, the results of equivalent systems utilizing the MAP and Best-Path algorithms are also provided in addition to the graphically predicted curve. The most notable charac teristic of these simulations is that for the system with a higher level of ISI (inner code: isi3.60.20.20), the resultant curve of the MAP based system does not coincide with the curve generated by the graphical procedure described in [3]. Yet for the system with less ISI (inner code: isi3.80.10.10) the MAP based system does appear to agree with the graphically predicted curve. One possible explanation is as follows. The graphical procedure described in [3] assumes that the inner code can be modeled by an equivalent Gaussian channel. Referring to equation (6) and (10) in section 2.1, the model assumes that: n%wi^) = cn/(**iipyto)) (63) j=l j=l where C is some constant and v is an equivalent noise variance. The fact that for the high ISI case, the MAP based curve does not coincide with the graphically deduced curve would suggest that it is not possible to find an equivalent sequence Y\ that can satisfy equation (64). When the outer code utilizes non-binary signaling it would seem that there are not enough degrees of freedom to find a suitable fit. Why then, does the MAP based curve match the graphically deduced curve for the low ISI case? This may be explained Chapter 4. Evaluating Performance of The Generalized Post-Detector 63 by the following reasoning. The one situation where equation (64) should hold is for a channel with no ISI. In that particular case, the equalizer should not do anything and should not affect the channel statistics. Therefore, a MAP based simulation with such a channel (inner code: isi3.100.0.0) should match perfectly with the graphically produced curve. However, as ISI increases, the statistics produced by the soft-output decoder seem to become less Gaussian and result in a deviation of the MAP based simulation curve from the graphically produced curve. This deviation would increase as the level of ISI over the inner channel increases. This explanation seems to be consistent with the observed results from the simulations. Overlooked in the previous discussion is the fact that the generalized post-detection algorithm seems to also work reasonably well for SOVE in systems that utilize non-binary modulation. The deviation from the optimum curve (determined by the MAP based system for this case) is not too unreasonable. It displays the same characteristic behaviour as was seen in the first suite of simulations. The deviation from the ideal case increases with increasing ISI. The results of the previous two suites of simulations suggest that for moderate lev els of ISI, the quality of a posteriori probabilities produced by the proposed generalized post-detection algorithm is quite good. This is a somewhat surprising result considering the concerns that were raised in Section 3.6.2 . One can only conclude that the approxi mations made during the derivation of the generalized post-detection algorithm are quite reasonable when the transmitted sequence from the "inner" code (in this case, it is an ISI channel) is transmitted over an AWGN channel. Chapter 4. Evaluating Performance of The Generalized Post-Detector M=[m0,mi,--,mK-i] w,£ {0,1}, i = 0,--,K-l U=[u0,UU-;U3N-l] «,e {0,1}, 7 = 0,--,3JV-l X=[x0,X\,- ;XN_i] Xi 6 {So,--;S7}, i = 0,---,N-Outer Convolutional Encoder Block 8-PSK Modulator ISI Interleaver Channel X- [XQ,X\, • • -,XN-\] xte {so,- -,s7}, i = 0,-N-l Viterbi Decoder Block De-interleaver Deduce Bit Prob Generalized Post-Detector Viterbi Equalizer Delay Line AWGN M= [fflo,mi,-',»!H] thi £ {0,1}, i = 0,--,K-l P(X0=S0\R) P(Xi=s0\R) ••• P(XN-\=S0\R) P(X0=S7\R) P(XI=S7\R) ••• P(xN-i=s7\R) [P] = P(u0 = 0\R) P(Ux=0\R) P(U0 = 1\R) P(u\ = l\R) ••• P(«3W-1 =0\R) ••• P(uiN-i=l\R) Notes: (1) ISI channel taps are static. (2) ISI channel tap weights are known by the equalizers. Figure 4.7: Concatenated Coding System with Uncoded 8-PSK Modulation Over a Static ISI Channel. Chapter 4. Evaluating Performance of The Generalized Post-Detector 10 10'1 10"2 10'3 10"4 10"6 10'6 107 Inner code: Isi2.90.10 Outer code: cc2_3.df4 Signal set: 8-PSK Perfect reliability estimation o Generalized SOVA post-det * * No reliability info available -2.0-1.0 0.0 1.0 2.0 3.0 4.0 5.0 6.0 7.0 8.0 9.0 10.011.012.0 Ei/N„ (dB) 10 10"1 10'2 10'3 104 10* 10"6 10"7 ^!:!:!:!:!:hS::::*::i:':!:!:!:!:!:h^i?;::^:!: Inner code: ISI2.80.20 Outer code: cc2_3.df4 Signal set: 8-PSK Perfect reliability estimation o Generalized SOVA post-det * * No reliability info available -2.0-1.0 0.0 1.0 2.0 3.0 4.0 5.0 6.0 7.0 8.0 9.010.011.012.0 E./N. (dB) 10° 10"' 10* 103 IO"4 10-5 10"6 10"7 *J;J:):!;!;l;l;l:l:^H:J:f;!;|;!:!;!:l;l:lAJ:«:J: Inner code: isi2.70.30 Outer code: cc2_3.df4 Signal set: 8-PSK Perfect reliability estimation o Generalized SOVA post-det *—* No reliability info available -2.0-1.0 0.0 1.0 2.0 3.0 4.0 5.0 6.0 7.0 8.0 9.010.011.012.0 Et/N0 (dB) Figure 4.8: Soft-Output Equalizer Performance in a Concatenated System Us ing Uncoded 8-PSK for the Outer Code. Chapter 4. Evaluating Performance of The Generalized Post-Detector 66 i....;....i....;...n,...,i,,,,i,...i,,,,i,,,,i .... i -2.0-1.0 0.0 1.0 2.0 3.0 4.0 5.0 6.0 7.0 8.0 9.010.011.012.0 10 IO"' 102 10'3 10'4 10'5 10"6 10"7 Inner code: isi2.50.50 Outer code: cc2_3.df4 Signal set: 8-PSK Perfect reliability estimation o Generalized SOVA post-det * % No reliability info available -2.0-1.0 0.0 1.0 2.0 3.0 4.0 5.0 6.0 7.0 8.0 9.010.011.012.0 E./N.tdB) Figure 4.8: Continued. Chapter 4. Evaluating Performance of The Generalized Post-Detector M=[mo,m\,-;mK-\] nti e {0,1}, i = 0,--,K- 1 X=[X0,X\,--;XN_l] Xj£ {s0,--,Sq-\}, i = 0,--;N-l Outer TCM Encoder Signal Block Interleaver ISI Mapper Channel X=[x0,Xl,--;XN-i] Xj e {s0, • • -,sq.i}, /' = 0, • • -N- 1 Viterbi Decoder Block Generalized Post-Detector De-interleaver Viterbi Equalizer Delay Line AWGN R = [ro,r\,--;ry-\] M=[m0,m\,--;mK-\] OT, e {0,1}, ; = 0, P(x0 = s0 \R) =s0\R) ••• P(xN-i = s0 \R) P(x0 = sq-x\R) P{X\ = sq-x\R) ••• P(xN-x = sq-i\R) [P] Notes: (1) ISI channel taps are static. (2) ISI channel tap weights are known by the equalizers. Figure 4.9: Concatenated System Using Coded 8-PSK Over a Static ISI Chan nel. Chapter 4. Evaluating Performance of The Generalized Post-Detector Figure 4.10: Soft-Output Equalizer Performance in a Concatenated System Using Coded 8-PSK for the Outer Code. Chapter 4. Evaluating Performance of The Generalized Post-Detector 69 Eb/N0 (dB) Figure 4.10: Continued. Chapter 4. Evaluating Performance of The Generalized Post-Detector 70 4.5 Determination of the Minimum Required Revision History for the Gen eralized Post-Detector To determine what is the minimum revision depth for the generalized post-detector in order for it to provide reasonably good estimates of the a posteriori input probabilities, the concatenated system shown in Figure 4.1 was once again simulated via computer software. However, this time the revision depth of the post-detector was varied between lx and 10 x the inner code's constraint length. The length of the Viterbi path history arrays were kept at a value much greater than 5x the appropriate code's constraint length. The results of these simulations are shown in Figure 4.11. The curves show the effect of changing the revision depth (and hence required memory) of the generalized post-detector. The curves indicate that a generalized post-detector should generate reasonable good quality a posteriori input probability estimates if its revision depth is set to a value of Spd > 5 x (constraint length). This result is not unexpected since the proposed algorithm does not revise the relative value vector for a given memory depth index if all of the possible paths yielded the same decision at that index. Since all of the surviving paths of a Viterbi decoder tend to merge by 5x the code's constraint length, clearly revision beyond this point is generally not done. Chapter 4. Evaluating Performance of The Generalized Post-Detector 71 -22-10" 10" 10"' 10"' 10" Inner code: cc3_4.df6 Outer code: cc2_3.df4 Modulation: BPSK 10x Constraint Length 5x Constraint Length 3x Constraint Length 1x Constraint Length Graphical Prediction Soft-Output Not Used _] i i i i i_ 0.0 1.0 2.0 3.0 4.0 Eb/N0 (dB) 5.0 6.0 0), CL 10u 10" 10" 10"' 10" Inner code: cc2_3.df4 Outer code: cc7_8.df2 Modulation: BPSK 10x Constraint Length 5x Constraint Length 3x Constraint Length 1x Constraint Length Graphical Prediction « » Soft-Output Not Used -2.0 -1.0 0.0 1.0 2.0 3.0 4.0 5.0 6.0 Eb/N0 (dB) Figure 4.11: Simulation Results of a Concatenated System Utilizing a Post-Detector With Various Revision Depths (channel: AWGN). Chapter 5 Conclusion 5.1 Summary This thesis tackles the problem of finding an efficient heuristic algorithm for deducing estimates of the a posteriori input probabilities of a Markovian based encoder. When this project was begun, the better known variants of this approach were applicable to (n,l,m) codes only. Therefore there existed a need to find an efficient heuristic based algorithm that would be applicable to the more general case of (n,k,m) codes. Of the known (n, l,m) heuristically based soft-output decoders, the most efficient of these in regards to computational and memory storage requirements is the decoder proposed by Berrou et al. [3]. The key to this decoder's efficiency was that it utilized a post-detector architecture. Berrou et al. were able to find a simple (n, l,m) revision algorithm that was compatible with this type of decoder architecture. The question naturally arose of whether it would be possible to find a (n,k,m) revision formula that was also compatible with this particular architecture. Fortunately, it was indeed possible. Finding such an algorithm involved several steps. The first was to use several ap proximations to simplify Battail's general heuristic revision formula [2] such that its complexity would be reduced to a reasonable level. The next step involved a compari son of the revision operations dictated by this simplified formula (for the (n, 1, m) case) with the revision operations dictated by the (n, l,m) post-detector algorithm published by Berrou et al. These comparisons resulted in the determination of what additional 72 Chapter 5. Conclusion 73 modifications had to be made to the simplified Battail revision formula in order for it to be able to take advantage of the post-detector decoder architecture. The resulting algorithm is the "generalized post-detector algorithm" described in Chapter-3. Simulations show that the proposed algorithm is capable of providing reasonably high quality estimates of a posteriori input probabilities for a variety of different convolutional codes. Furthermore, despite some concerns raised in Section 3.6.2, the proposed algo rithm also seems adequate for use with Viterbi equalizers. In addition, it was found that a revision depth of 5 x (constraint length) should be sufficient for many applications. For the serial concatenation of two codes, performance can be characterized as follows. Approximately 80% of the maximum possible SNR (dB) gain attainable through the use of soft-decision decoding for each stage is achieved (the best performance being arrived at through the use of a soft-output MAP inner decoder and the worst through the use of a standard hard-output inner decoder). This seems to be typical of heuristic based algorithms. Benefits of using the new algorithm include the fact that it can be applied to any (n, k, m) trellis based code. The decoding delay is independent of the length of the trans mitted code sequence and can be as short as 10 x (constraint length). Disadvantages of this algorithm include the fact that the quality of a posteriori input probability esti mates is not as good as those produced by the MAP or Best-Path algorithms. Since the algorithm is based on the Viterbi algorithm it shares the same limitations of the Viterbi algorithm: practical only for relatively short constraint length codes. Finally, knowledge of the channel variance is required by the receiver to calculate the branch metrics (a problem shared by the MAP and Best-Path algorithms as well). Chapter 5. Conclusion 74 5.2 Proposed Future Work One of the main incentives for the renewed interest in soft-output decoders is that they are an essential element of Turbo decoders[4]. It would be worthwhile to determine how well the new algorithm performs for this particular application. One question that arises is whether it is even worthwhile to consider a sub-optimal soft-output algorithm. It may be that for a given level or performance, the turbo decoder may have to perform more iterations with a SOVA type algorithm than it would with a MAP type algorithm. This might offset any computational advantages that the SOVA algorithm may have held. For this thesis, the main objective of the computer simulations was to determine how certain system parameters would affect the quality of the a posteriori input probabilities deduced by the generalized SOVA. Several concatenated systems were simulated in which individual system parameters such as dfree or the choice of signaling constellation could be isolated and changed. Consequently, many of the simulated systems seem artificial in that one would never choose those combinations of "codes" for actual applications. It would be desirable to perform some simulations that are more indicative of "real world" systems. The codes selected should be representative of codes used in actual practice. On a related note, it would be desirable to determine how real world channel impairments affect the quality of the soft-output information. For example, simulations should be performed over the Rayleigh and Rician fading channels. Finally, incidental to the main goal of the work described in this thesis, it was dis covered that the graphical algorithm described by Berrou et al. [3] may not accurately predict the performance of a concatenated system that must directly use the a posteriori input symbol probabilities for calculating the metrics of the outer decoder. It is hy pothesized that this is due to the deduced a posteriori input symbol probabilities having non-Gaussian statistics for these cases. This should be verified. References [1] L. R. Bahl, J. Cocke, F. Jelinek, and J. Raviv, "Optimal Decoding of Linear Codes for Minimizing Symbol Error Rate," IEEE Trans. Inform. Theory, Vol. IT-20, No. 2, pp. 284-287, March 1974. [2] G. Battail, "Ponderation des symboles decodes par l'algorithme de Viterbi," (in French), Annales des Telecommunications, Fr., 42, N° 1-2, pp. 31-38, January 1987. [3] C. Berrou, P. Adde, E. Angui, and S. Faudeil, "A Low Complexity Soft-Output Viterbi Decoder Architecture," 1993 IEEE Internat. Conf. on Comm., Vol. 2, pp. 737-740. [4] C. Berrou, A. Glavieux, P. Thitimajshima, "Near Shannon Limit Error Correct ing Coding and Decoding: Turbo-codes," IEEE Int. Conference on Comm, ICC'93 Geneva, Switzerland, Vol 2/3, pp. 1064-1070, May 1993. [5] D. G. Daut, J. W. Modestino, L. D. Wismer, "New Short Constraint Length Con volutional Code Constructions for Selected Rational Rates," IEEE Trans. Inform. Theory, Vol. IT-28, No. 5, pp. 794-800, September 1982. [6] J. Hagenauer, P. Hoeher, "A Viterbi Algorithm with Soft-Decision Outputs and its Applications," Proc. of IEEE Globecom'89, Dallas, Texas, pp. 47.1.1-47.1.7, November 1989. [7] P. A. Humblet, "Efficient Maximum-a-Posteriori Symbol Detection," submitted for publication, Institut Eurecom, Sophia-Antipolis, France, July 1994. [8] G. D. Forney, JR., "Maximum-Likelihood Sequence Estimation of Digital Sequences in the Presence of Intersymbol Interference," IEEE Trans, on Inform. Theory, Vol. IT-18, No. 3, pp. 363-378, May 1972. [9] G. D. Forney, JR., "The Viterbi Algorithm," Proc. of the IEEE , Vol. 61, No. 3, pp. 268-278, March 1973. [10] Y. Jain, "Convolutional Codes Improve Bit-Error Rate in Digital Systems," EDN pp. 129-133, August 20, 1990. [11] S. Lin, D. J. Constello Jr., "Error Control Coding: Fundamentals and Applications," Prentice-Hall, Inc., Englewood Cliffs, N.J., 1983. 75 Bibliography 76 [12] J. G. Proakis, "Digital Communications, Second Edition," McGraw-Hill, Inc, New York, N.Y., 1989. [13] G. Ungerboeck, "Trellis-Coded Modulation with Redundant Signal Sets," IEEE Communications Magazine, Vol. 25, No. 2, pp. 5-21, February 1987. [14] X. Wang, S. B. Wicker, "A Soft-Output Decoding Algorithm for Concatenated Sys tems," IEEE Trans, on Inform. Theory, Vol. IT-42, No. 2, pp. 543-553, March 1996. Appendix A Predicting Concatenated Code Performance - Graphical Method Consider the concatenated system depicted in Figure A.l. The output of the inner soft-output decoder is a discrete-time continuous random variable. If sufficient interleaving is used there should be little correlation amongst the errors entering the outer decoder. If the assumption is made that any decoding metric based upon these samples is Gaus sian distributed then it is possible to treat the inner-code/interleaver combination as an equivalent discrete-time AWGN channel. This is the basis of the graphical procedure described in [3] used to predict the bit-error rate (BER) performance of a concatenated system. To use this procedure it is necessary to determine the relationship between the signal-to-noise ratio (SNR) of the global concatenated system and the SNR of a system com prised of the inner code only. If Efobal and Elbnner represent the transmitted energy per bit of the global concatenated system and inner coding system respectively, while Es represents the energy per symbol transmitted over the channel then: global = & where Rg = RoRi (65) Kg Ri Therefore, E Einner _ (66Thinner rpglobal r> ^ = ^ El (67) N0 N0 Rl K ' 77 Appendix A. Predicting Concatenated Code Performance - Graphical Method 78 Now letting SNR = 10 log ^ it follows that: SNpinner = SNRglobal _ ^ A = 10 log ^ = 10 log (68) Rg R0 To determine the BER of the concatenated system at a specified global SNR (point-a in figures A.l and A.2) perform the following procedure. Use equation (68) to determine the SNR of the inner code system (point-6). Look-up in a graph or table the resultant BER of the inner system (point-c). Determine what SNR would be required to achieve this BER on an equivalent uncoded AWGN channel (point-d). (In effect, the inner coding system is being emulated by an equivalent AWGN channel.) Once again, using equation (68), translate this SNR back to the equivalent system's overall SNR (point-e). Using a graph or table of the BER performance of the outer system operating over a standard AWGN channel use the equivalent system's overall SNR to look-up the resultant BER of the outer code (point-/). The abscissa (^-coordinate) of point-a and the ordinate (in coordinate) of point-/ specify an operating point of the concatenated system (point-g). Outer Encoder rate: R„ ' SNRs hbal © ^lleaterH Encoder H Inner Encoc rate: Ri Modu- _h/j!V-k lator I^Y* Soft-Output Decoder ® No var = -f SNR™" = SNRs'° ba' - A De-inter- Outer leaver Decoder © \/ Outer Modu Equivalent AWGN Channel Outer Encoder lator Decoder rate: R„ Figure A.l: System Model for Graphical Procedure Appendix A. Predicting Concatenated Code Performance - Graphical Method 10L 10" 10" GC .3 tu 10 m 10" 10 10" -5 Inner Code: CC, Rate 2/3 Outer Code: CC, Rate 3/4 AWGN Binary Channel Figure A.2: Graphical Determination of Concatenated System Performance Appendix B Code Tables The following tables describe the codes associated with each "code label" referenced the simulations shown in Chapter-4. 80 Appendix B. Code Tables 81 B.l Convolutional Codes Label Rate CL. Tot Mem Generator Sequences dfree Reference (symbols) (bits) (octal) 6 2 6 cc2_3.df3 2 3 1 2 3 [11] 2 4 4 4 2 6 cc2_3.df4 2 3 2 3 4 [11] 1 4 7 64 30 64 cc2_3.df7 2 3 3 6 7 [11] 30 64 74 4 4 4 4 cc3_4.df4 3 4 2 3 0 6 2 4 4 [11] 0 2 5 5 6 1 0 7 cc3_4.df6 3 4 2 6 3 4 1 6 6 [11] 2 3 7 4 2 0 2 0 2 0 6 6 0 0 0 0 0 4 0 4 0 0 0 0 4 0 0 4 cc7_8.df2 7 8 1 1 0 0 0 4 0 0 0 4 2 [Daut et al] 0 0 4 0 0 0 0 4 0 4 0 0 0 0 0 4 4 0 0 0 0 0 0 4 Appendix B. Code Tables B.2 TCM Codes Label CL. Tot Mem Generator Sequences (sym) (bits) (octal) 4 0 0 cc2_3.tcm 2 2 0 7 5 Mapping: 0 : +cos(22.5°) - jsin(22.5°) 1 : -sin(22.5°) + j cos(22.5°) 2 : +cos(22.5°) + j sin(22.5°) 3 : +sin(22.5°) + jcos(22.5°) 4 : -cos(22.5°) + jsin(22.5°) 5 : + sin(22.5°) - j cos(22.5°) 6 : -cos(22.5°) - jsin(22.5°) 7 : -sin(22.5°) - jcos(22.5°) Notes: Feed-forward version of code presented in [13] Appendix B. Code Tables Label CL. (sym) Tot Mem (bits) Generator Sequences (octal) cc3_4.tcm 4 0 0 0 0 4 2 0 0 3 5 2 Mapping: Notes: 0 : + 1 2 3 JVTo 3 Vw + _L_ _ 9'_3_ v/io J vTo + +-?v7T0 4 : +v^o +-?vlo 5 6 7 3 %/To J ./Tn +7To +:>7w +-2- - i'-3-L_ + ,-_3_ \/io ^ ^ \/io 3_ _ 1 11 12 1 A 3 ,/Tn J vTo 1 vTo v/10 J7w 14 • vTo •7v/lO 15 : ._L_ + ,-_L_ VTo ^ J Vw From [13] Appendix B. Code Tables Label CL. (sym) Tot Mem (bits) Generator Sequences (octal) cc4_5.tcm 4 0 0 0 0 0 4 0 0 0 0 0 4 2 0 0 0 3 5 2 Mapping: 0 : + _3_ _ ,-_L_ v/20 J v/20 16 5 v/20 v/20 1 : 4^ 4 7-2-' v/20 ' J v/20 17 + v/20 _ ^720 2 : ~*~72o ~ 18 4-5-+ v/20 + J71o 3 : 4-2- 4- 7^-v/20 J v/20 19 1 v/20 +^T!O 4 : 4—5- 4 7-3-v/20 J v^O 20 _ 5 v/20 +^TIO 5 : 3_ , -_3_ v/20 1 J v/20 21 3 v/20 - 7-5-J v/20 6 : 4^- 4 7-L 1 v/20 ' ^ v/20 22 4-5-+ v/20 - 7-^-J v/20 7 : + -2- - 7 — v/20 ^ v/20 23 4-2-+ v/20 + ^720 8 : L_ 4. W_3_ v/20 J v/20 24 1 v/20 - 7-5-J v/20 9 : _720 ~~ ^720 25 4^-+ v^o _ ^720 10 v/20 ^ J v/20 26 + v/20 +^TIO 11 • L_ _ 7-^_ v/20 J v/20 27 5 v/20 + ^720 12 ' _720 _ ^720 28 4-2-+ v/20 ~~ ^'720 13 • 4^- - 7-5-v/20 J v/20 29 4^-+ v/20 + -?7to 14 • ~ 720 — j 720 30 3 v/20 +JTIO 15 • L_ 4. ,-_L_ V20 J v/20 31 5_ v/20 Notes: From [13] Appendix B. Code Tables B.3 ISI Channels Two Tap ISI Channels Label Chan. mem. C0 Cl isi2.50.50 1 VolE Vol isi2.60.40 1 Vol6 Vol isi2.70.30 1 Vols isi2.80.20 1 VoU isi2.90.10 1 VOA Three Tap ISI Channels Label Chan. mem. Co Cl C2 isi3.60.20.20 2 VoU Voi V0~2 isi3.80.10.10 2 Vox Vol Vol isi3.100.0.0 2 vTo Void Volo Appendix C The MAP and "Best-Path" Algorithms The following descriptions of the MAP and "best-path" algorithms are based on the derivations presented in the paper written by Humblet [7]. C.l The MAP (or Bahl, "forward-backward", "any path") Algorithm Consider a discrete-time finite-state Markovian process. An input sequence X± = (Xi, X2,X^) will result in a state sequence Si+1 = (Si, S2,SV+i) along with an as sociated output sequence. It is assumed that the starting state Si and final state SJV+I are known (The final input symbols are preset such that the process terminates in a known state.). Transmission of the output sequence over a discrete-time memoryless channel will result in the sequence = (Yi, Y2,YN) being observed by the receiver. Upon detection of the sequence YXN, the MAP receiver calculates the a posteriori state prob abilities P(Sn\Yf) or transitional probabilities P(S^+1\Yf). From these, it is possible to deduce the a posteriori input symbol probabilities P(Xn\YlN). Using the a posteriori input symbol probabilities the receiver may make a decoding decision or, in the case of a soft-output decoder, output the a posteriori probabilities themselves. An explanation of how the MAP algorithm calculates the state/transition probabili ties begins by taking into consideration the following probability expansion: 86 Appendix C. The MAP and "Best-Path" Algorithms 87 P<.S*,Y?) P(S^+\Yf) = P(S1)P(S2,Y1\S1)P(S3!Y2\SlY1)P(Si,Y3\SlYl)-P(Sn<Yn-1\S^-\Y1n-2)x (69) p(s„+1,y„|sr,y1"-1)•••p(s^-1,^_2|5^-^^-3)F(s^,,yN_1|sf-^y1N-2)P(5^+1,^|5ff,y1JV-1) s * ' ^(s^+1,yjJ,_1isf-1,y1w_2) N : v ' v v ' Each of the terms on the right hand side of equation (69) can be simplified by noting the following property of Markovian processes: given Sn and Sn+i, Yn is independent of all previous states and received samples. Similarly, given Sn, Sn+i is also independent of the same previous states and received samples. Therefore, = P(Sn+i\Sn)P(Yn\Sn-i.i, Sn) = P(Sn+l,Yn\Sn) (70) Similarly, Pffi1, Yf\S?, Fr1) = P(S%g, YnN\Sn) (71) It is convenient to define the following quantity: Q(Yn, Sn, S'n+l) — P(Sn+i, Yn\Sn) The first of two recursive relations is now noted: PiS^Y?-1) = £ PiS^Y?'1) <— "upper-half" ofeqn (69) sn-leSn-l = £ p(sr\Yr2)p(sn,y„-iisr\Y?-2) sn-l£<s„_i Appendix C. The MAP and "Best-Path" Algorithms 88 = E S„_lGS 53 Pisrwr2) sr>-2e5„_2 (72) Defining P(5n,yln_1) as the "forward" probability P/(5n,yln_1) gives: *n-ie«5 (73) Since it was assumed that the Markovian process starts in a known state, for instance sQ, the calculation of equation (73) begins with the initial condition: Pf(Si) 1 , Si = sa 0 , Si ^ sa The second recursive relation can be found by noting that: (74) P(YnN\Sn) = £ P(S™,YnN\Sn) 5^+11G5JV-"+1 "lower-half" of eqn (69) 5^+11e5JV-"+1 EpfO V Qn Vn~l\P( QN+1 VN qn+l yn\ — 53 ^'('S'n+l, Yn\Sn) 53 P(Sn+2i Y^+1\Sn+i) Q N+ 1C SN—n. an+2 fco — E P(Sn+i,Yn\Sn)P(Yn+i\Sn+i) Sn+i€S Defining P(Y?\Sn) as the "backward" probability Pb(Sn,Y^) yields: p*(5B,yBJV)= 53 Q(rn,5n,5n+1)Ph(5n+1,yn+1) If sw represents the assumed terminating state, then the initial condition is: P'(5„+I) = { 1 1 S"+1 = «" 0 , S/V+l 7^ Sw (75) (76) (77) Appendix C. The MAP and "Best-Path" Algorithms 89 Once the "forward" and "backward" probabilities have been calculated the state probabilities can be determined by: £ £ P{S™Y») 5n-le5„_l 5JV + le5JV-„ + l £ £ Pi^YrWsZgtYfWsY?-1) Sr,-le5„-l sAf + le<5JV_„+l £ p(s?,Yrl) £ P^Y.^ISn) ST,-lg5„-l pfis^Yr^p'is^) The conditional state probability may be found by: P(Sn\YxN) N\ _ P(Sn, Y-f*) P(Y») (78) (79) The transitional probabilities are found from: P(S^+1,y1JV) = £ £ P{S»+I,Y») £ £ p^r.yr-^pcs^Y.^isr.i-r1) sn-le<s„_! sN + leSN-n £ pfsr.y^-1) |p(sn+1,yn|sn) Lsp'efi"-1 J = Pf(Sn, y1n-1)Q(Yn, 5„, 5n+i)P6(5n+i, yn^i) The conditional transition probability may be found by: p(qn+l yN\ IM ; — pfy^) Finally, to find the a posteriori input symbol probabilities: £ P{Sn+2 ' Yn+11 Sn+1) (80) (81) p(xB>y1JV) = £ P(^+\>f) (82) •?n + 1 |'V(5'n,5„+l)=Xn where A^S^, Sn+i) is a mapping from the state transition to the associated input symbol. Appendix C. The MAP and "Best-Path" Algorithms 90 C.2 The "Best-Path" Algorithm The "best-path" algorithm comes about by noting that the Viterbi algorithm uses the iteration: rn-l\ A pi{Sn,Yrl) = max P(S?, y^1) — max Sn-ieS nmax P(Sr\Yr2) P{Sn, Yn-l\Sn-l) = maxcP/(5n_i>y1n-2)Q(yn_1,Sn_1,S'n) (83) where P^(5„_i, Y™~2) represent the survivor path metrics to each previous state and Q(yn_i, 5„_i, Sn) are the branch metrics associated with each possible transition. In a similar manner, maximizing in the reverse direction: P"(Sn,YnN) ±\ max P(S™,Yf\Sn) 5»+ieS + = WJ.,ma^ P(Sn+i,Yn\Si,Y™ 1)P(5^21, Y„+i\Si+l, y") 5n+i e5 = max P(5n+1,yn|5„) max P(S»£,YnN+1\Sn+1) Sn+ies s^esN~n = maxQ(Yn,Sn,Sn+1)Pb(Sn+l,Y1?+1) (84) This formula once again describes the Viterbi algorithm except it is now run in reverse. Pb(Sn+i,Y^f+l) are the reverse path metrics and Q(Yn-i, Sn-i, Sn) are, as stated previ ously, the branch metrics. Now that the best "forward" and "backward" probabilities to each state are known, the probability of the best path through a particular state can be determined by: PtSn.lf) = max max P{S»+1, Y») = P'(5„,l^-1)Pt(5n>yn'v) (85) Appendix C. The MAP and "Best-Path" Algorithms 91 Likewise, the probability of the best path with a specific transition may be found by: P(5^+1,yiJV) = max max P(Sf+1,rf) = p'(5B,i7,-1)g(y„,5BJ5B+i)P6(5fH.1,yBJ5.1) (se) By using the probabilities determined in equation (86) in equation (82) one is able to obtain an estimate of the a posteriori input symbol probabilities. C.3 Computational and Storage Requirements A decoder can be implemented to be efficient in either the amount of computation re quired or the amount of storage space required. In the discussion that follows, for the determination of the minimum storage requirements, the "save storage" implementation shall be assumed, whereas, for the calculation of the minimum computational require ments, the "save time" implementation shall be used. It should be pointed out that in the case of the MAP and Best-Path algorithms, these two cost factors are mutually ex clusive. However, the resulting expressions for computational and storage requirements will be the best that can be achieved by the basic MAP and Best-Path algorithms. It is with these best case metrics that the comparisons with other competing algorithms shall be made. Consider decoding a sequence of N received symbols produced by the transmission of N output symbols from an (n,k,m) Markovian process. Assuming a minimum mem ory configuration of either the MAP or Best-Path algorithms, the decoder will need to store the received sequence so that it may calculate Q(Yn, Sn, Sn+i) (a quantity that is similar to the Viterbi branch metric) as needed. This will require the allocation of N storage elements (double this if the received sequence is complex). If it is desired that the output information come out of the decoder in the correct order without having to Appendix C. The MAP and "Best-Path" Algorithms 92 buffer decisions, it will be necessary to calculate and store Pb(Sn, Y^). This will require the allocation of N2m storage locations. The subsequent calculation of Pf (Sn, Y"'1) can then be made immediately followed by the calculation of the transition probabili ties P(S^+1,Y1N). If the received sequence is sufficiently long, the amount of temporary storage required to calculate these quantities will be small in comparison to the stor age requirements of the received sequence and Pb(Sn, Y^). Hence a minimum memory configuration decoder will require at least N2m + N storage elements. To determine the computational requirements of a typical MAP decoder, the assump tion of a "save time" implementation is made. (In this implementation the quantities Q(Yn, Sn, Sn+i) are calculated once only and stored for later retrieval as needed.) Cal culation of probabilities Pf(S^Y^1) and Pb{Sn,YnN) will each require: 2m2fc binary multiplications and 2m(2k — 1) binary additions per symbol. Q(Yn, Sn, Sn+i) requires es sentially the same computational effort as the Viterbi metric with the exception that an additional exponential must be calculated to return e_metrtc. Since this quantity depends on the specific application it is not possible to determine a general expression for the amount of elementary operations required for its computation. However since a metric is calculated for each possible output symbol at each time index it is safe to assume that the time required will be proportional to 2n per symbol. The transition probabilities will each require 2 binary multiplications for each of the 2m2fc state transitions per time index for a total of 2m2fc+1 binary multiplications per symbol. If the effort required to calculate the input symbol probability is neglected (which consists of several compares, additions, and normalization if required) then, excluding the computation required for Q(Yn: Sn, Sn+i), the total amount of elementary operations is as shown in table Cl. When implementing the "best-path" algorithm, one usually uses the logarithm of the quantities Pf(Sn,l?-1), Pb(Sn,YnN), and Q{Yn, Sn, Sn+1). Therefore, for a "save time" implementation of the "best-path" algorithm, the following calculations will have to be Appendix C. The MAP and "Best-Path" Algorithms 93 binary multiplications binary additions exp p>(sn,Yri) 2m2k 2m(2fc - 1) 2m2k 2m(2fc - 1) Q{Yn, Sn, Sn+i) (see text) 2" 2^2^+1 Table C.l: Minimum Operations Required per Input Symbol for the MAP Algorithm. binary compares binary additions exp log p'tSn.yr1) 2m(2fc - 1) 2m2fc iogp*(5n>yBJV) 2m(2fc - 1) 2m2k \ogQ(Yn,Sn,Sn+1) (see text) P(SZ+\Y») 2m2fc Table C.2: Minimum Operations Required per Input Symbol for the Best-Path Algorithm. made. The determination of log(Pf (Sn, Y^'1)) and log(P6(5n, Yj?)) will each require 2m2k binary additions and 2m(2k — 1) binary compares per symbol. Computation of \og(Q(Yn, Sn, Sn+i)) does not require any exponentials however exponentials are now required during the later step when the trellis transition probabilities are calculated. The transition probabilities will require 2 binary additions for each of the 2m2fc state transitions for a total of 2m2k+1 binary additions per symbol. The total number of operations are summarized in table C.2.
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- A generalized post-detector compatible soft-output...
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
A generalized post-detector compatible soft-output vitebri algorithm (sova) Kwan, David 1996-12-31
pdf
Page Metadata
Item Metadata
Title | A generalized post-detector compatible soft-output vitebri algorithm (sova) |
Creator |
Kwan, David |
Date | 1996 |
Date Issued | 2009-02-10 |
Description | A generalized soft-output Viterbi algorithm (SOVA) that is applicable to any (n, k, m) convolutional code is proposed. The algorithm is compatible with the post-detector architecture proposed by Berrou et al. thereby achieving low computational complexity. By starting with Battail's generalized revision algorithm and re-referencing the relative values to the surviving path to each state, significant simplifications are made possible. By comparing the resultant simplified revision equation for (n,1,m) convolutional codes with Berrou's proposed post-detector compatible algorithm it is possible to deduce the additional modifications necessary to arrive at a (n,k,m) post detector compatible algorithm. Simulations show that with a revision depth greater than five times a code's constraint length, the proposed algorithm is capable of producing relatively high quality a posteriori input symbol estimates. |
Extent | 4123908 bytes |
Genre |
Thesis/Dissertation |
Type |
Text |
File Format | application/pdf |
Language | eng |
Collection |
Retrospective Theses and Dissertations, 1919-2007 |
Series | UBC Retrospective Theses Digitization Project |
Date Available | 2009-02-10 |
Provider | Vancouver : University of British Columbia Library |
Rights | For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use. |
DOI | 10.14288/1.0065312 |
URI | http://hdl.handle.net/2429/4376 |
Degree |
Master of Applied Science - MASc |
Program |
Electrical and Computer Engineering |
Affiliation |
Applied Science, Faculty of Electrical and Computer Engineering, Department of |
Degree Grantor | University of British Columbia |
Graduation Date | 1996-05 |
Campus |
UBCV |
Scholarly Level | Graduate |
Aggregated Source Repository | DSpace |
Download
- Media
- 831-ubc_1996-0235.pdf [ 3.93MB ]
- Metadata
- JSON: 831-1.0065312.json
- JSON-LD: 831-1.0065312-ld.json
- RDF/XML (Pretty): 831-1.0065312-rdf.xml
- RDF/JSON: 831-1.0065312-rdf.json
- Turtle: 831-1.0065312-turtle.txt
- N-Triples: 831-1.0065312-rdf-ntriples.txt
- Original Record: 831-1.0065312-source.json
- Full Text
- 831-1.0065312-fulltext.txt
- Citation
- 831-1.0065312.ris
Full Text
Cite
Citation Scheme:
Usage Statistics
Share
Embed
Customize your widget with the following options, then copy and paste the code below into the HTML
of your page to embed this item in your website.
<div id="ubcOpenCollectionsWidgetDisplay">
<script id="ubcOpenCollectionsWidget"
src="{[{embed.src}]}"
data-item="{[{embed.item}]}"
data-collection="{[{embed.collection}]}"
data-metadata="{[{embed.showMetadata}]}"
data-width="{[{embed.width}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.831.1-0065312/manifest