Open Collections

UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

A soft decision concatenated coding scheme for mobile packet radio applications Poon, Patrick C.H. 1996

Your browser doesn't seem to have a PDF viewer, please download the PDF to view this item.

Item Metadata

Download

Media
831-ubc_1996-0348.pdf [ 3.91MB ]
Metadata
JSON: 831-1.0065313.json
JSON-LD: 831-1.0065313-ld.json
RDF/XML (Pretty): 831-1.0065313-rdf.xml
RDF/JSON: 831-1.0065313-rdf.json
Turtle: 831-1.0065313-turtle.txt
N-Triples: 831-1.0065313-rdf-ntriples.txt
Original Record: 831-1.0065313-source.json
Full Text
831-1.0065313-fulltext.txt
Citation
831-1.0065313.ris

Full Text

A SOFT DECISION CONCATENATED CODING SCHEME FOR MOBILE PACKET RADIO APPLICATIONS by PATRICK C H . POON B.ENG. (Computer Engineering), McMaster University, Canada, 1993 A THESIS SUBMITTED IN PARTIAL FULFILLMENT OF THE REQUIREMENTS FOR THE DEGREE OF MASTER OF APPLIED SCIENCE in THE FACULTY OF GRADUATE STUDIES DEPARTMENT OF ELECTRICAL ENGINEERING We accept this thesis as conforming to the required standard THE UNIVERSITY OF BRITISH COLUMBIA June 1996 © Patrick C H . Poon, 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 ' i 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 ^[&ct<n CaS( t^Ji n The University of British Columbia Vancouver, Canada Date DE-6 (2/88) Abstract Concatenated coding systems can offer good error performance over severely degraded channels. The combination of an inner trellis code and an outer Reed Solomon code has been a popular choice since it offers a good compromise between performance and complexity. In this thesis, a concatenated coded modulation scheme based on trellis coded modula-tion and a Reed Solomon code in the presence of Rayleigh fading is studied. The inner decoding process uses a soft output Viterbi algorithm which produces reliability information along with its output. This information is used to erase unreliable symbols in the decoded output. An errors-erasures Reed Solomon decoder is then used for the outer code. The block error probability performance gain achievable through the use of a soft output Viterbi algorithm in concatenated coding is studied using analysis and simulation. The effect of finite interleaving for the outer code is also considered. 11 Table of Contents Abstract » List of Tables vi List of Figures vii Acknowledgment x Chapter! Introduction 1 1.1 Motivation and Scope of the thesis 2 1.2 Overview of the Thesis 3 Chapter 2 Background 5 2.1 Concatenated Coding Scheme 5 2.1.1 The Outer Reed S olomon Coding 6 2.1.2 The Inner Trellis Coded Modulation 7 2.2 Interleaving 9 2.3 Channel Model 11 Chapter 3 Decoding Algorithms for Concatenated Code 12 3.1 Truncated Viterbi Decoding Algorithm 12 3.2 Soft Output Viterbi Decoding Algorithm ..17 3.3 Errors-Only Decoding 21 3.4 Errors-Erasures Decoding 21 Chapter 4 Performance Analysis of Concatenated Coding 23 4.1 Performance Evaluation of Trellis Coded Modulation 23 4.1.1 Derivation of Symbol Error Probability 24 iii iv 4.1.2 Upper Bound on Pairwise Error Probability 26 4.1.3 Derivation of Exact Pairwise Error Probability 28 4.1.4 An Approximation for Symbol Error Probability 30 4.1.5 Examples 32 4.2 Performance Evaluation with Reed Solomon Coding 33 4.2.1 Derivation of Block Error Probability ...33 4.2.2 Example 35 Chapter 5 Design of System Model 38 5.1 General Overview of SPW™ 38 5.1.1 Basic Components in SPW™ 38 5.2 Simulation Model 40 5.2.1 Transmitter Structure 41 5.2.2 Channel Model 42 5.2.3 Receiver Structure 43 5.2.4 Simulation Parameters 45 5.3 Validation of the Simulation Model 47 5.3.1 Rayleigh Fading Simulator 48 5.3.2 SOVA "Custom-coded" Block.. 49 Chapter 6 Simulation Results and Discussion 50 6.1 The Basic Model.; 50 6.1.1 Error Performance of the Basic Model 50 6.1.2 Effect of No Outer Interleaving 53 V 6.1.3 Comparison of Single Code with Concatenated Code 54 6.2 The Modified Model (SOVA) .55 6.2.1 Optimum Erasure Threshold... 56 6.2.2 Error Performance of the Modified Model 57 6.3 Finite Interleaving 61 6.3.1 Error Performance of Finite Interleaving 61 Chapter 7 Conclusions 67 7.1 Summary 67 7.2 Suggestions of Future Work 68 Glossary 69 References 70 Appendix A. Chernoff Bound 73 Appendix B. Residue Theorem . 74 Appendix C. Block Diagram of Simulation Model 75 Appendix D. Example of TCM file in SPW™ 78 Appendix E. Rayleigh Distribution 79 Appendix F. Source code of SOVA 81 List of Tables Table 2.1 16-PSK TCM Codes 8 Table 5.1 Summary of SPW™ modules' functions 39 Table 5.2 Summary of DSP block libraries in SPW™ 40 Table 6.1 Descriptions of the four trellis codes used 51 Table 6.2 Descriptions of two single code tested systems 54 Table 6.3 Five erasure thresholds considered 56 Table 6.4 Span and depth distribution of the outer interleaver/deinterleaver 62 vi List of Figures Figure 1.1 Concatenated Coding System 2 Figure 2.1 TCM and RS concatenated coding system 6 Figure 2.2 Encoding Bits Sequence 7 Figure 2.3 Example of the V(3) trellis encoder implementation 9 Figure 2.4 Natural and Gray Code Mapping with 16-PSK signal constellation 9 Figure 2.5 An interleaver with span s and depth d 10 Figure 3.1 16-PSK Signal Constellation 13 Figure 3.2 8-state trellis flow diagram...; 16 Figure 3.3 Erasure Declaring Operation 18 Figure 3.4 Example of erasure declaring ....20 Figure 4.1 Model of a rate m/(m+l) TCM scheme 24 Figure 4.2 Example of an error event of length N 25 Figure 4.3 An approximation of symbol error probability for (a) the rate 3/4 32-state 16-PSK TCM code and (b) the rate 3/4 8-state 16-PSK TCM code 33 Figure 4.4 An approximation of the average BKER for concatenated coding scheme with an outer (63,47) RS code and an inner (a) rate 3/4 32-state TCM code; and (b) rate 3/4 8-state TCM code 36 Figure 4.5 An approximation of the average bit error rate for concatenated coding scheme with an outer (63,47) RS code and an inner (a) rate 3/4 32-state TCM code; (b) rate 3/4 8-state TCM code. 37 Figure 5.1 Block diagram of simulated system model!.... 41 Figure 5.2 Block diagram of transmitter 41 Figure 5.3 Block diagram of Rayleigh fading amplitude simulator 43 vii Figure 5.4 Block diagram of receiver 44 Figure 5.5 Theoretical and simulation Rayleigh fading amplitude distributions 48 Figure 5.6 The average symbol error probability of rate 3/4, 8-state trellis-coded 16-PSK modulation using 1) analytical method and 2) simulation method 49 Figure 6.1 (a) BKER and (b) BER simulation results on different inner trellis codes: i) U435 code, ii) V435 code, iii) U433 code and iv) V433 code of the basic model with perfect interleaving 51 Figure 6.2 (a) BKER and (b) BER results for the V433 inner code and the basic model by simulation and theoretical analysis ...52 Figure 6.3 (a) BKER and (b) BER results with different inner trellis codes: i) U435 code, ii) V435 code, iii) U433 code and iv) V433 code and the basic model without outer interleaving 53 Figure 6.4 A comparison of the (a) BKER and (b) BER results of the V433 inner code of the basic model and two single code systems: i) trellis coded modulation only, and ii) Reed Solomon code only. 55 Figure 6.5 A comparison of various erasure thresholds based on the BKER results of (a) the V433 inner code, and (b) the U435 inner code of the modified SOVA model 57 Figure 6.6 (a) BKER and (b) BER simulation results for various inner TCM codes concatenated with a (63,47) RS code and the modified SOVA model with erasure threshold -ln(R) = 0.02 .....58 Figure 6.7 The BKER results of the SOVA simulation model using (a) U433 inner code and (b) V433 inner code for four different conditions: i) without erasure and without outer interleaving, ii) with erasure and without outer interleaving, iii) without erasure and with perfect outer interleaving, and iv) with erasure and with perfect outer interleaving 59 Figure 6.8 The BKER results of the SOVA simulation model using (a) U435 inner code and (b) V435 inner code for four different conditions: i) without erasure and without outer interleaving, ii) with erasure and without outer interleaving, iii) without erasure and with perfect outer interleaving, and iv) with erasure and with perfect outer interleaving. 60 viii Figure 6.9 (a) BKER and (b) BER results of using finite outer interleaving in the SOVA model with various depth D and span S: i) DxS: 5x126, ii) DxS: 10x63, iii) DxS: 21x30, iv) DxS: 30x21, v) DxS: 63x10, and vi) DxS: 126x5 63 Figure 6.10 (a) BKER and (b) BER results of using finite interleaving in the basic model with various depth D and span S: i) DxS: 5x126, ii) DxS: 10x63, iii) DxS: 21x30, iv) DxS: 30x21, v) DxS: 63x10, and vi) DxS: 126x5 64 Figure 6.11 Diagram of outer deinterleaver with various span and depth: (a) DxS = 10x63, (b) DxS = 30x21, and (c) DxS = 5x216 65 ix Acknowledgment I would like to thank my academic supervisor, Dr. C. Leung and my industrial advisor, Mr. S. Alamouti, for their continuous guidance and encouragement throughout the research work for this thesis. This work was supported by a G.R.E.A.T. award from the Science Council of British Columbia. Chapter 1 Introduction To meet the ever-increasing demand for wireless communication, the need for better digital transmission techniques is growing quickly in importance. If a certain information rate is set or high accuracy of transmitted information is required, the increase in code redundancy comes at the expense of increased channel bandwidth. In a bandwidth constrained environ-ment, trading bandwidth for performance is not an attractive choice and it is desirable to improve the system's performance while at the same time maintaining the same bandwidth efficiency as in an uncoded system. To this end, trellis coded modulation (TCM) has been used [1,2, 3]. ' TCM has evolved over the past decade as a combined coding and modulation technique for digital transmission over band-limited channels. Its main attraction comes from the fact that it can achieve significant coding gains over conventional uncoded multilevel modulations without compromising bandwidth efficiency [1, 4, 5]. However, to achieve very high coding gains with a single modulation code, the decoding complexity increases drasti-cally and the implementation of the decoder becomes very expensive [6]. On many real links such as radio, satellite or mobile channels, transmission errors are mainly caused by variations in received signal strength referred to as fading. In such fading channels, TCM code errors tend to propagate due to long fades or unreliable soft-decision information [7, 8, 9]. To overcome severe signal error bursts due to fading, two levels of coding are employed. Thus, another reason for using concatenated coding scheme is a simpler implementation for a 1 Chapter 1 Introduction 2 similar performance improvement. The original concatenated coding scheme was proposed by Forney [10] and is illustrated in figure 1.1. Data in Outer Encoder Data out Outer Decoder Inner Encoder Channel Inner Decoder Superchannel Figure 1.1 Concatenated Coding System 1.1 Motivation and Scope of the thesis In this thesis, a concatenated coding system is considered. Trellis codes of low complexity using phase shift keying (PSK) modulation are used for the inner codes and a Reed Solomon (RS) code is used as the outer code. These inner codes are selected because they require no bandwidth expansion and can be decoded by a modified Viterbi algorithm which produces reliability information along with the decoded output. For the selection of outer code, a RS code can handle multibit character-based erasure information and perform very well on burst-error channels. It also offers flexibility in block length and symbol size. Concatenated codes with T C M inner codes and RS outer codes on Gaussian channels, have been considered in [11, 12] where the performance of concatenated coding was Chapter 1 Introduction 3 evaluated by simulations. In this thesis, Rayleigh fading channels with additive white Gaussian noise (AWGN) are used. To improve the code performance on fading channels, signal phase changes are compensated for by using a reference pilot tone, and signal amplitude variations are used to form the metric for the inner Viterbi decoder with channel state information (CSI). An erasure decoding technique based on the Soft Output Viterbi Algorithm (SOVA), proposed by Hagenauer [13], is then applied. SOVA modifies the original Viterbi algorithm to calculate the path metrics for soft decisions, and decides in a soft way by providing reliability information together with the output bits. This information can be used to erase unreliable bits in the decoded output and an errors-and-erasures RS decoder can be employed for the outer code. With the use of SOVA, the performance of the concatenated coding system has been considered in [14, 15] where bit error rate (BER) is studied and infinite interleaving is assumed. However, in some applications such as voice packet transmission environments, time delay is an important issue. Infinite interleaving may not be a reasonable assumption. Therefore, finite interleaving is examined in this thesis. Lastly, the packet loss rate of concate-nated coding scheme is studied and hence the block error rate (BKER) performance is evaluated in this thesis. 1.2 Overview of the Thesis In chapter 2, we discuss the system model of a concatenated coding scheme. A detailed description of the inner TCM codes and an outer RS code are given. Furthermore, the importance of the use of interleaving is discussed. In chapter 3, four decoding algorithms for Chapter 1 Introduction 4 the concatenated coding scheme are presented. We first describe the conventional Viterbi decoding algorithm for the inner codes and then explain the modified SOVA algorithm. Finally, we compare the errors-only decoding and the errors-erasures decoding for the outer RS code. In chapter 4, the performance evaluation of the concatenated coding scheme assuming infinite interleaving is considered. Analytic results for both BKER and BER results are presented. In chapter 5, a simulation model of the concatenated coding scheme is discussed and is implemented using Signal Processing Worksystem (SPW™) [16]. In chapter 6, the error performance of the concatenated coding scheme is evaluated using simulation. The effect of finite interleaving for the outer code is taken into account and a symbol interleaver with varying dimensions is considered. Simulation results are compared with those of an uncoded system as well as a concatenated system without erasure decoding. The main conclusion and some suggestions for future work appear in chapter 7. Chapter 2 Background In this chapter, we describe the concatenated coding scheme involving inner T C M codes and an outer RS code. We also discuss the importance of using an interleaver in order to break the error bursts which occur during transmission. 2.1 Concatenated Coding Scheme In order to reduce coding complexity and achieve a high error correcting capability, concatenated coding schemes are commonly employed. Previous studies [11, 14, 15] have shown that such schemes can yield a high coding gain over the uncoded system. In [11], a concatenated coding scheme over an A W G N channel with no reliability information analyzed. Assumed infinite interleaving, the B E R performance of concatenated coding scheme was examined in [14, 15]. In this section, we discuss a system model of an outer RS code concate-nated with inner T C M codes in the presence of Rayleigh fading. Thus, in voice packet transmission environments, the B K E R is of greater importance than the BER. We discuss the B K E R performance with the use of finite interleaving between the inner and outer codes. The encoding-decoding block diagram of the concatenated coding scheme is shown in figure 2.1. 5 Chapter 2 Background 6 Data in Outer RS Encoder Data out Outer RS Decoder Outer Interleaver Outer Deinterleaver Inner TCM Modulator Inner TCM Demodulator ^ Inner Interleaver r Fading Channel f Inner Deinterleaver Figure 2.1 TCM and RS concatenated coding system 2.1.1 The Outer Reed Solomon Coding The outer code is a (n, h) RS code with code symbols from the Galois field GF(2'), i.e. the uncoded input bit sequence is divided into blocks of k uncoded symbols, each of length / bits. Each block is encoded using the RS code into RS codewords of length n RS symbols. A .(«, k) RS code is summarized in [17] by the following parameters: • RS block length :n = 2l-\ • Number of parity check digits : n - k = It • Minimum distance : dmin = 2t+ 1 where t is the error correcting capability. In this thesis, we employ a (63,47) RS code and it can correct up to 8 RS symbol errors. Thus, an error block of RS code is defined as an undetected error block which carries more than t symbol errors. The reason for choosing RS Chapter 2 Background 7 code is that it has an erasure decoding capability. That is, if reliability informations are provided from the inner decoder, a combination of erasures and errors can be corrected in the RS decoder. The errors-erasures decoding algorithm for RS code appears later in chapter 3. 2.1.2 The Inner TVellis Coded Modulation The inner encoding stage uses a rate ml(m+l) trellis coded M-PSK modulator. As shown in figure 2.2, the nl bits from the RS encoder are grouped into nllm symbols, each of length m bits. Each m-bit symbol is encoded to (m+l)-bit inner convolutional code as described in [3, 18]. Each group of (ra+1) bits is then mapped into a M-PSK signal, where M=2m+1, based on Gray code or natural mapping. Thus, each PSK signal corresponds to an m-bit RS encoded symbol and mkln user information bits. Therefore, we have s n 0 (2.1) where Es is the average energy per PSK signal and Eb is the average energy per user bit. / bits I bits k blocks x / bits I bits I bits n RS codes x / bits m+1 bits m+1 bits m+1 bits m+1 bits nllm Convolutional codes x (m+1 )bits 1 signal 1 signal 1 signal 11 signal nllm PSK signals Information bits V RS codeword t Convolutional code t PSK signal Figure 2.2 Encoding Bits Sequence Chapter 2 Background 8 In this thesis, rate 3/4 trellis coded 16-PSK modulation is adopted. The choice of a rate 3/4 trellis code is to allow each (6-bit) RS symbol to be accommodated using two 16-PSK signals. In order to assess the performance of different code structures, 8-state and 32-state trellises are considered. In previous analyses of TCM [19], it has been shown that the Ungerboeck codes may not minimize the BER on fading channels. In [18], a new set of trellis codes has been developed for use in the presence of Rayleigh fading. The new Vucetic codes can achieve larger coding gains at high SNR than the Ungerboeck codes for given BERs. Both Vucetic codes and Ungerboeck codes are considered for their BKER performance in this thesis. The code constructions for the four TCM codes are summarized in table 2.1. IBB h(2) h(l) h(0) mapping U{3) - - - ' 048 13g Natural V(3) 15g 178 058 138 Gray Code U(5) • - -' • 108 45g Natural V(5) 75 8 73 8 • 47g 57g Gray Code Table 2.1 16-PSK TCM Codes Here, U(i) designates a 21-state Ungerboeck code and V(i) designates a 21-state Vucetic code. And the h(i)'s are the parity check coefficients which leads to the systematic (feedback) implementation of the convolutional encoder as illustrated in figure 2.3. For instance, if h(3) = 15g, its binary representation of (1101)2 will connect x2 to the first, second and fourth "Exclusive-OR" adders as shown in the diagram. Chapter 2 Background 9 x2 x l xO h(2) i • w y y — • s ! — i y y — • s 2 — < H y — • s 3 — i y h(0) • y3 -> y2 yi -> yo Figure 2.3 Example of the V(3) trellis encoder implementation Here, (Sy, S2, S3) forms the trellis state of TCM codes and x's and y's denote the input and output bits of the convolutional encoder respectively. The output bits are then mapped to the PSK signals using two types of mappings as shown in figure 2.4. Im 5.  4l 3 Im 7' 10 11 Re '15 14 12 13 5, 4o 2 o •1 ,0 12* if •8 • 15 "9 14 10 * n Natural Mapping Gray Code Mapping 2.2 Figure 2.4 Natural and Gray Code Mapping with 16-PSK signal constellation Interleaving The purpose of interleaving is to break the error bursts introduced during the transmis-Chapter 2 Background 10 sion. However, interleaving introduces long delay. In many applications, long delays are not acceptable at the receiver. For good performance, the span of the inner interleaver/deinter-leaver should be chosen in the order of trellis decoder buffer size while the depth of inner interleaver/deinterleaver should be chosen in the order of anticipated length of fade duration [20]. For outer interleaving, the span and depth of the outer interleaver/deinterleaver should be large enough to break the symbol bursts out of the inner decoder [14]. For long block lengths or inner decoder error bursts, a large interleaver memory is rejected and a long delay will be incurred. In such cases, infinite interleaving may not be a good assumption. The effect of finite interleaving for inner codes has been studied [15]. In this thesis, the effect of finite interleav-ing for the outer code is considered. By keeping a constant memory storage of the interleaver/ deinterleaver, we alter the depths and spans of the outer interleaver in pairs. (Cj, C2, C 3 , C d s ) Input Cs+1 2s+l Span Cs+2 C2s+2 C(d-l)s+l I C(d-l)+2 (Cj, C S + I , C2S+J, Cds) Output 2s c 3s c Depth Figure 2.5 An interleaver with span s and depth d The operation of an interleaver is illustrated in figure 2.5. We assume an input sequence (Cj, C2, C3, Cds) is being interleaved and its corresponding output sequence Chapter 2 Background 11 becomes (Cj, Cs+1, C2s+], Cds). The operation of a deinterleaver is an inverse of the interleaver. A symbol sequence to be interleaved is first filled up in rows (span) inside the interleaver and then output in columns (depth). 2.3 Channel Model The channel is modeled as Rayleigh fading. With the assumption of perfect CSI, the fading amplitude for each received signal is known. We also assume that the signal phase changes due to fading are fully compensated for by using a reference pilot tone. In this model, the amplitude of the envelope of the received signal is multiplied by a Rayleigh distributed random variable a. In order to equate the average received signal energy to the transmitted energy, we set E[ce2] = 1, where E[.] denotes the expectation operation. The probability density function (pdf) of a is given by [21] p(a) = 2a exp(-a 2), a > 0 (2.2) In order to eliminate channel memory, inner interleaving is used. With the assumption of infinite interleaving, fade bursts are broken up so that the fading appears to be independent from symbol to symbol at the input of the inner decoder. Chapter 3 Decoding Algorithms for Concatenated Code In this chapter, we give detailed descriptions of four decoding algorithms for both inner and outer codes. They are the truncated Viterbi algorithm and Soft Output Viterbi Algorithm (SOVA) for the inner codes; and the errors-only decoding and errors-erasures decoding for the outer code. We also discuss the significant differences between the conven-tional Viterbi algorithm and the SOVA. Finally, we discuss the errors-erasures correcting capability of the outer code. 3.1 Truncated Viterbi Decoding Algorithm As described in chapter 2, the inner codes we used are rate 3/4 16PSK TCM codes. For optimum decoding of the inner codes, Viterbi decoding is applied at the receiver. Suppose the set of all possible coded PSK signal.sequences z# at the output of the inner TCM encoder is denoted by C and z# is a coded PSK signal sequence of length TV: ZN = (ZPz2> •••>z;> •••>%) where N is the surviving path length of the TCM code, i.e. the number of the latest N received signals in the Viterbi decoder from which the path metric is computed. In [19], this is referred as the truncated Viterbi decoding algorithm. The decoder keeps and updates the latest N elements of the surviving path in memory. The decoding process outputs one demodulated symbol per state transition instead of waiting until the entire sequence has been received to 12 Chapter 3 Decoding Algorithms for Concatenated Code 13 make a decision. It is also desirable to have a large N for involving more received signals in computing the path metric. A path metric from large N will output a more reliable decision of the survivor path. However, a longer surviving path will lead to a longer delay and a larger memory storage in the decoder. Therefore, N is usually set to 4 or 5 times the constraint length of the trellis [19]. The constraint length is defined as the number of shifts in information bits over which a single bit can influence the encoder output [17]. In our simulations, N is set to 36 which is sufficient for the decoder to make a reasonable decision on the surviving path. Using complex notation, each z,- in the code sequence z# is a point in the complex plane and the set of distinct z,-'s forms the signal constellation as shown in figure 3 . 1 . We normalized each signal constellation such that E{z t -} = 1 where E { . } is an expected value. Im Figure 3.1 16-PSK Signal Constellation Now, suppose the coded PSK signal sequence vN = (v,, v2, v,-, vN) (3.2) is transmitted. With ideal interleaving of transmitted sequences over a fading channel, the Chapter 3 Decoding Algorithms for Concatenated Code 14 fading process w i l l appear to be independent from symbol to symbol. A s assumed infinite interleaving and perfect CSI , the received signal r,- corresponding to a transmitted symbol V; can be written as [21] r f = a- V,- + nt (3.3) where a , is the amplitude of the received signal and n, is a sample of a zero mean complex A W G N process. The random variable a , is normalized such that E{oc; } = 1. After deinter-leaving, the received sequence, rN, appears at the output of the inner deinterleaver as RN = {rl,r2,...,ri,...,rN) (3.4) With the use of the conventional Viterbi algorithm, the decoder searches in the set C for the sequence z#. To select the most probable survivor sequence z#> the a posteriori probability P(z# I rN> a#) of sending z# given rN and a# must be the largest in C [21] where aN = (a,, a 2 , a ( - , a N ) (3.5) Since the channel is assumed memoryless, the cc,'s and r / s are independent random variables and hence, the a posteriori probability satisfies: N P(zN\rN, aN) = ]JP {zi | r (-, a.) (3.6) i = l where P(z, I rit a t ) is the a posteriori probability for each individual transmitted and received codeword pair [21]. Thus, the decoding process uses a maximum-likel ihood metric of the Chapter 3 Decoding Algorithms for Concatenated Code 15 form m(z^, rN, aN) to represent the a posteriori probability if side information a, is available: m(zN, rN, aN) = -In {P (zN | rN , aN)} (3.7) It is desirable from the standpoint of simplifying the decoding process that the path metric is chosen with an additive property, i.e. the path metric m(z^, rN, aN) is the sum of N branch metrics rafz; ,r± from each state transition: N N m(zN, rN, aN) = m(zi, r ; , a-) = - £ l n p(zi \ ri > ) (3-8) i=1 (=1 Therefore, to select the most probable survivor sequence z^ from its a posteriori probability, it is equivalent for the Viterbi algorithm to choose the coded sequence Z/y whose path metric m(z#, rN, aN) is the smallest since we have N m(zN, rN, aN)min = ln [ />( Z / 1 r,-, a(- )]max (3.9) i= 1 With the assumption of perfect CSI, the corresponding fading amplitude a, can be estimated from the signal power. Each branch metric m(z,- ,r, ,a,-) is defined in [21] as the squared Euclidean distance for each received and transmitted codeword pair in C such that m(z- , r . ,a ( ) = I r ^ - a ^ l 2 (3.10) Suppose we have the smallest path metric m(z^, rN, aN) at time t with a surviving code sequence z#- For the state transition in Viterbi decoding, the algorithm will update the Chapter 3 Decoding Algorithms for Concatenated Code path metric and survivor code sequences at time t+1 as follows: 1. Decode the z j element from the surviving code sequence z# with the smallest path metric and output its corresponding uncoded information. 2. Update the surviving paths for each trellis state by shifting one element down, i.e. for every 0<i<N, z± = z ( + 1 , such that the sliding path window keeps a constant length of N. 3. Compute the branch metrics m(z[+-i ,rt+i, OL[+I) from the received signal r r + 1 for each codeword z f + 1 . 4. Add the computed branch metrics to the previous path metrics and obtain a new mini-mum path metric for each state. 5. Choose the minimum path metric among the minimized metrics from each state and declare the corresponding code sequence as the surviving path for output. 6. Repeat step 1 at time t+2. It is worth to notify that in this truncated Viterbi decoding, the new surviving path for output may not be diverging from the previous surviving paths of output. As shown in figure 3.2, the output at time t+2-N is not diverging from the same surviving path for output at time t+1 -N. Chapter 3 Decoding Algorithms for Concatenated Code 17 i=t+l-N i=t+2-N state 0 ® • f-state 1 - © f state 2 » ' -state 3 <* » state 4 • state 5 ° -state 6 • • state 7 -Figure 3.2 8-state trellis flow diagram 3.2 Soft Output Viterbi Decoding Algorithm The soft output Viterbi algorithm (SOVA) and the erasure decoding algorithm have been developed in [13, 22, 23]. The main idea in these algorithms is to transform path metric differences, which indicate the reliability of competing path sequences, into reliability values for individual symbols. These information can be used to erase unreliable symbols at the decoder output and can be recursively updated with each survivor extension. We also expect that the outer code (e.g. RS code) can improve its error performance by providing some erased symbols in addition to the hard decisions from the inner decoding. A simplified operation of the decoding process is shown in figure 3.3. Chapter 3 Decoding Algorithms for Concatenated Code 18 Viterbi Demodulator erasure Outer Decoding Device reliability value W; Threshold Device SOVA Figure 3.3 Erasure Declaring Operation The operation of SOVA is similar to that of the conventional Viterbi algorithm. It searches all possible code sequences to find the most probable transmitted sequence. However, instead of only considering the code sequence with the highest a posteriori probabil-ity (the smallest metric), SOVA also keeps the second best code sequence from the current survivor state with its corresponding path metric. Suppose the most probable transmitted sequence is z# with the highest a posteriori probability P(z# I rN aN). The decoding process will choose z# to be the new surviving path for output as in the conventional Viterbi algorithm. However, instead of carrying onto another state transition directly, SOVA searches through all the incoming paths at the surviving node (the node which ends at the most probable survivor path for output) for the second most probable transmitted sequence iN by comparing its a posteriori probability P(zN \ rN> a#) Chapter 3 Decoding Algorithms for Concatenated Code 19 with P(z# I r-N aN). If the ratio of their a posteriori probabilities is larger than a certain thresh-old i.e. > R (3.11) " (zN rN , CLfl) erasures will be declared for all those symbols at which the sequences z# and zN differ. In other words, the algorithm actually compares their corresponding path metric difference. And erasures are declared if they satisfy m(zN,rN,aN) - m(zN,rN,aN) < -ln(R) (3.12) Figure 3.4 illustrates the described algorithm. Here, two paths merge at the same node (state 1) at time t. The decoder has to choose one of them as the surviving path. The conven-tional Viterbi decoder will ignore the fact that the two paths have nearly equal accumulated path metrics and choose the path with the smallest metric as the survivor. However, with the use of SOVA, the decoder recognizes that the two paths have a nearly indistinguishable metric, i.e. metric difference less than -\n(R). The decoding process will deliver erasures at all those positions in which two paths differ. Chapter 3 Decoding Algorithms for Concatenated Code 20 i=t-N i=t-3 i=t-2 i=t-l i=t state 0 state 1 • m 0 f - ZN • • state 2 • e ^. state 3 • • ..02 31 21 23 12 32 30 -m(z, r) 1 • ..02 31 32 00 12 32 11 -m(z, r) ...02 31 ee ee 12 32 ee Surviving paths Surviving path with erasures Figure 3.4 Example of erasure declaring As for state transition, the described algorithm is only slightly more complex than the conventional Viterbi algorithm. Like the conventional Viterbi algorithm, SOVA computes the branch metrics leading to each node and chooses the one with the smallest metric as the new surviving path. However, if the new surviving path diverges from an old surviving path which contains some erasures, all those erasures will automatically be carried over to the new path. In other words, although the new metric difference is much larger than the threshold, there may still be some erasures in the new surviving path. Another important issue in SOVA is to choose the erasure declaring threshold R. We could not find an analytical method to optimize this threshold. At high signal to noise ratio (SNR), we usually choose a larger value of R for a better performance. However, if the set value of R is too large, the decoding process will not likely to output an erasure because the metric difference cannot be small enough to meet -ln(R). In this case, the performance of Chapter 3 Decoding Algorithms for Concatenated Code 21 SOVA will be very close to that of the conventional Viterbi algorithm. In contrast, if the value of R is too small, the decoding process will deliver too many erasures i.e. false alarms. Thus, the overall performance will be degraded. In our simulations, the optimal threshold R is found by trial and error. 3.3 Errors-Only Decoding As described in chapter 2, the outer code is a (63,47) RS code. When no reliability information is provided from the inner decoder, an errors-only decoding algorithm is applied at the outer decoder. This algorithm is designed to correct symbol errors only. If the received block sequence at the input of the outer decoder has less than or equal to t symbol errors, they will be successfully corrected by the outer code, where and dmin is the minimum distance of the RS code. However, if the number of symbol error is larger than t, an undetected error block of RS code will be received. 3.4 Errors-Erasures Decoding When reliability values are provided from the inner decoder, an errors-erasures decoding algorithm can be applied. The outer decoder with errors-erasures decoding algorithm is designed to correct both symbol errors and erasures. Suppose the received block sequence contains t symbol errors and e erasures. The decoder can successfully correct the errors and erasures if (3.13) Chapter 3 Decoding Algorithms for Concatenated Code 22 2t + e ^ d m i n - l (3.14) However, if (3.12) is not satisfied, an error block with no attempt at any correction will be received. Chapter 4 Performance Analysis of Concatenated Coding One of the important issues in designing a communication system is to consider its error performance. Nowadays, performance evaluation techniques usually fall into two categories: analysis-based method and simulation-based method. In this chapter, we will first look at the analytic approach of computing error probability. With the assumption of perfect CSI and infinite interleaving, the error probability of Viterbi decoding in the presence of Rayleigh fading has been derived in [21, 24, 25, 26]. In this chapter, by assuming infinite interleaving between inner and outer codes, the error perfor-mance of concatenated coding based on RS code and TCM code is considered. Both BKER and BER are derived analytically. Finally, the derived expressions for BKER and BER will be applied to our concatenated coding system. 4.1 Performance Evaluation of Trellis Coded Modulation In order to evaluate the error performance of trellis code, it is necessary to first consider the pairwise error probability P(z —> z) of TCM [19]. The pairwise error probability is defined as the probability that the decoder chooses an incorrect coded sequence z when in fact the sequence z was transmitted. The derivation of pairwise error probability bounds can be found in [21, 24]. An upper bound on BER for the trellis code is derived in terms of the pairwise error probabilities. In [25], an expression of the exact pairwise error probability in the presence of Rayleigh fading is derived. In the following sections, both the upper bound 23 Chapter 4 Performance Analysis of Concatenated Coding 24 and the exact pairwise error probability of TCM are considered. With slight modifications to the derivations in [21, 24, 25], the average symbol error rate of TCM is then derived in terms of the pairwise error probability. 4.1.1 Derivation of Symbol Error Probability Consider a rate m/(m+l) TCM scheme as shown in figure 4.1. Here, a rate m/(m+l) convolutional encoder takes m source bits at a time and transforms them into a codeword _yf- of m+1 bits that are fed into a PSK signal mapper f(.). The mapper outputs channel signal z,-where z, is complex PSK signal with normalized magnitude equal to 1. Therefore, we have a one-to-one correspondence between the m-bit input symbol x,- and the PSK signal zv Trellis Encoder PSK Mapper zi=f(yt) x-<2> 1 tl yl» f 1 1 1 Y.(m) w 1 1 1 v.(m+l) y i fc w Figure 4.1 Model of a rate m/fm+1 j TCM scheme Let C be the set of all possible coded PSK symbol sequences. Now, suppose and iN denote two sequences of PSK signal z; and z • respectively in C of length N: ZN — ( Z i , Z 2 , Z-, Z^y) _ _ „ . (4.1) ZN ~ (zl> z2> •••> zi> •••> ZN' An error event of length N occurs when the demodulator chooses, instead of the Chapter 4 Performance Analysis of Concatenated Coding 25 transmitted sequence z^, another sequence iN of channel signals corresponding to a trellis path that splits from the correct path at a given time, and remerges exactly N discrete signals later. An error event of length TV is shown in figure 4.2. 1 2 1 *2 "• • I Z n J 1 1 ."V \ / — / ZN 2 v Figure 4.2 Example of an error event of length N The probability of this error event is defined as the pairwise error probability P(zN —> °f sequences z# and zN. In order to determine the average error event probabil-ity, all the signal sequences in C are considered. Following [19], the average error event probability P(e) is bounded by the union bound: oo X Z X nzN)P{zN^~zN) (4.2) N = 1 % 6 C ZN * *N where P(zN -> zN) denotes the pairwise error probability that zN is chosen over z# and P(zN) denotes the probability of transmitting the signal sequence z#. In order to obtain the average symbol error probability from P(zN —»£#), it is necessary to average the number of symbol errors associated with each error event [25]. Let n(zN, zN) be the number of symbol errors that occur when the sequence z# is transmitted and Chapter 4 Performance Analysis of Concatenated Coding 26 the sequence zN is chosen by the decoder. Following [19], the upper bound on the average symbol error probability can be modified from (4.2) as where Ps is the average symbol error probability at the output of the demodulator. 4.1.2 Upper Bound on Pairwise Error Probability Evaluation of the pairwise error probability bound depends on the maximum-likeli-hood metric and the presence or absence of CSI. Since the decoder incorrectly chooses zN as the transmitted sequence, zN must attain the largest a posteriori probability (smallest path metric) among all other paths as described in section 3.1. Therefore, its path metric m(zN, rN, aN) will be smaller than that of the transmitted sequence^, i.e. where rN is the received signal sequence and aN is the fading amplitude sequence of the received signal. With the assumption of infinite interleaving, each received signal rt is independent for each ith transmission interval [19]. Therefore, following (3.8), the above equation is equal to (4.3) m(zN,rN,aN) < m(zN,rN,aN) (4.4) (4.5) Chapter 4 Performance Analysis of Concatenated Coding 27 where mQ.-^ r •, a •) is the branch metric of zN and r(- for the /th transmission interval. The pairwise error probability of sequence z# and zN is then equal to the probability of choosing the wrong survivor path by getting the smallest path metric from zN. The pairwise error probability P(zN —> zN) is therefore given by r N N P(zN -> ~zN) = Pr\ 2 m(i,-, r(, a(-) < ]T m(z-, rf, a ;) I (4.6) w = i i = l -* Using (3.10), (4.6) can be expressed in terms of the squared Euclidean distance as P(zN^~zN) = Pr^0< £a?|z . -z , . | 2 J (4-7) ~ 2 ~ where I z,- - z • I is the squared Euclidean distance between two signals z,- and z •. With the assumption of perfect CSI, the fading amplitude a- is known. Applying the Chernoff bound (see Appendix A) as in [24], the pairwise error probability in a Rayleigh fading environment is given by -Es P(zN-*zN) < expj — f N o 2 i ~ |2 v i = i y (4.8) £ s denotes the average received signal energy for each PSK symbol sent and NJ2 is the double-sided power spectral density (PSD) of the AWGN. With perfect CSI, the fading Chapter 4 Performance Analysis of Concatenated Coding 28 amplitude CC; is known for each /th transmission interval. Each a ( has a Rayleigh fading distri-bution [27] with pdf: p(a) = 2a exp (-a ) (4.9) By averaging (4.8). over (4.9), an upper bound on pairwise error probability over the Rayleigh fading channel with perfect CSI can be obtained as [24] P(zN^zN) < f N n Vi = i AN, 2- — Z-l l ~ ,2 • (4.10) 4.1.3 Derivation of Exact Pairwise Error Probability In the case of PSK modulation with perfect CSI, an exact pairwise error probability over fading environment is derived in [25, 26]. Following (4.6), the pairwise error probability can be written as r N P(zN->zN) - Pr (4.11) where Dt is an independent random variable representing the path metric difference for the ith transmission interval. We have Dt = m(i-, r •, a ( ) - m(z/; r •, a-) (4.12) Or, Di can be modified from (3.10) as Chapter 4 Performance Analysis of Concatenated Coding 29 (4.13) Let cpj(s) be the two-sided Laplace transform of the pdf of the random variable Dt-According to [25], (Pj(s) can be written as PuPli (s-pu)(s-p2i) (4.14) where pj{ andp2[ are the left plane (LP) and the right (RP) poles of the transformation, respec-tively, with Pu = \ ~ Jl-PuPu Pu = \ + \\-PuPn (4.15) and PuPli = -1 (4.16) Because of the independence of the D,'s, the two-sided Laplace transform of the pdf of the sum of D,'s is the product of (p,(s)'s, i.e. f N AN, 2 ^ ,-1 z- — z-r N n - l \ Hs-pu)(s-p2i) (4.17) where Or;(s) is the Laplace transform of the cumulative pdf of Note that the first term in Chapter 4 Performance Analysis of Concatenated Coding 30 (4.17) is the upper bound of pariwise error probability in (4.10). In (4.17), it is multiplied by a correction factor whose value depends on poles of the Laplace transform of £>,. The pairwise error probability is actually an inverse Laplace transform of <&r)(s) and can be obtained by using the residue theorem (see Appendix B). Therefore, we have The above expression gives the exact pairwise error probability for the TCM scheme with PSK modulation and perfect CSI over a Rayleigh fading environment. 4.1.4 An Approximation for Symbol Error Probability In most communication systems, the average bit or symbol error probability is of greater interest than the pairwise error probability. In order to obtain the average symbol error probability from (4.3), it is impossible to add the pairwise error probabilities for all error events of different path lengths because N is counting from 1 to infinite in (4.3). Therefore, it is simpler to approximate the symbol error probability by considering only a small set of short error events from (4.3) as follows: for 5 < 0 (4.18) L (4.19) N =\zNe C zN*zN with min < L (4.20) Chapter 4 Performance Analysis of Concatenated Coding 31 where Lmin is the length of the shortest error event path, i.e. the minimum effective length taken over all error paths in the trellis where the effective length of an error path is the number of erroneous symbols on the error path. The selection of L controls the maximum length of an error event used for approximation, but L has to be larger than L m i n , otherwise no error event will be examined. A usual choice of L depends on the signal to noise ratio (SNR). At sufficient high SNR's, the average error probability will be dominated by the shortest error events. A long error burst event is less likely. Therefore, L can be chosen to be one or two branches more than Lmin and this will be enough for a good approximation. However, at low SNR's, a larger L is required for a better estimation. It is also noted that the computational complexity grows roughly exponentially with L. If L is chosen to be larger than 4, the amount of computation will be excessive. It is also mentioned in [19] that TCM is in general a nonlinear operation. That is, the error performance depends on the transmitted sequence z#. This means that the approximation of error probability in (4.19) should use the set of all short error events in C. However, for simplicity, we assume the transmitted sequence z# to be the all zero-phase codeword and approximate the error probability from those error events that diverge from the all zero-phase codeword path. This assumption has been shown to be reasonably accurate at high SNR's in [25]. Therefore, the approximation in (4.19) can further be written as L p*~ X _ X « ( ^ % ) / > ( % ^ ^ ) (4-21) N = 1 zN^zN Chapter 4 Performance Analysis of Concatenated Coding 32 4.1.5 Examples In this section, we approximate the symbol error probability Ps of some TCM schemes. We consider two rate 3/4 16-PSK trellis codes as described in section 2.1.2. They are the 8-state and 32-state Vucetic codes. From their code structures in [18], we see that both codes have the same Lmin of 2. This means that the length of an error event must involve at least 2 consecutive error transmissions. In the approximation, we substitute L with 4 in (4.21). In order to obtain an estimate of the average symbol error probability, we first identify all error events with code sequences that merge with the transmitted codeword in less than or equal to 4 trellis branches. According to (4.21), the average symbol error probability is approximated by adding the symbol error probabilities for each corresponding error event. For simplicity, we again assume an all-zero codeword sequence is transmitted. The average symbol error probabilities of two rate 3/4 16-PSK TCM codes are computed from (4.21) and their results are illustrated in figure 4.3. In figure 4.3, the approximation of the average source symbol error probabilities and their upper bounds are shown. The upper bounds of symbol error rates are computed from substituting (4.10) with (4.21). They are about 3dB away from the approximated values at high SNR for both TCM codes. The error performance of the 32-state trellis code is about 3 dB higher than that of the 8-state trellis code. Chapter 4 Performance Analysis of Concatenated Coding 33 o 8 9 10 11 12 13 14 15 16 17 Energy per bit to Noise Ratio, Eb/No (dB) Figure 4.3 An approximation of symbol error probability for (a) the rate 3/4 32-state 16-PSK TCM code and (b) the rate 3/4 8-state 16-PSK TCM code. 4.2 Performance Evaluation with Reed Solomon Coding In order to consider the error performance of concatenated coding with an outer RS code, it is of greater interest to look at the BKER. With the assumption of infinite interleaving at the output of the inner decoder, the BKER can then be computed analytically. 4.2.1 Derivation of Block Error Probability As described in section 3.3, for an (n, k) RS code with t-enoi correcting capability, an error-free block of n RS symbols will be received if there are t or fewer symbol errors occurring in one RS codeword. Thus, one RS codeword carries k source symbols of / bits each. Chapter 4 Performance Analysis of Concatenated Coding 34 The average BKER of the RS code is the average number of undetected error blocks in which each carries t or more symbol errors at the output of the outer decoder. BKER depends on the coded RS symbol error rate Prs. If Prs is constant for all RS symbols, the decoded block error probability at the output of the outer decoder can be given by n BKER = £ ^(Pj ( l - P , / - 1 (4.22) i = t + 1 For a concatenated coding scheme, it is important to relate the inner probability rate to the outer probability rate. The independence of RS symbols can be obtained by introducing an deinterleaver between the inner and the outer codes. If the decoded TCM symbols at the output of the inner decoder are also independent, the RS symbol error rate Prs at the input of the outer RS decoder can be expressed as Prs = l - ( l - P s ) l / m (4.23) where Ps is the average TCM symbol error rate at the output of the inner decoder in (4.21). m is the number of bits representing one decoded TCM symbol and / is the number of bits per RS symbol so that each RS symbol corresponds to l/m TCM symbols. If one can obtain the average BKER from (4.22), the source symbol error rate Psymb0i at the output of the outer decoder can be obtained from BKER = l-d-PsymbJ (4.24) Chapter 4 Performance Analysis of Concatenated Coding 35 which further implies that Psymbol = 1 - d - B K E R ) 1/k (4.25) where k is the number of source symbols per RS codeword. Similarly, if every source symbol is of / bits length, the average BER at the output of the outer decoder is given by 4.2.2 Example In this section, we consider the error performance of an outer (63,47) RS code concat-enated with an inner rate 3/4 16-PSK TCM code as described in section 4.1.5. The BKER is obtained from (4.22) and (4.23) with the substitution of P S from previous analysis in (4.21). Note that the (63,47) RS code has an 8-error correcting capability (i.e., t - 8) and each RS symbol is of length 6 bits (i.e. / = 6). Figure 4.4 illustrates plots of BKER versus SNR for a concatenated coding scheme based on two inner TCM codes and an outer RS code with infinite interleaving in the presence of Rayleigh fading. It is observed that the upper bounds of the average BKER for both cases are about 3dB higher than the approximated values. With the use of a 32-state trellis code, the BKER of concatenated coding scheme is enhanced. Its BKER performance achieves more than 3dB coding gain over the 8-state trellis code at a 10"8 BKER value. BER - 1 - (.1 - Psymboi) \/l (4.26) Chapter 4 Performance Analysis of Concatenated Coding 36 9.5 10.5 11.5 12.5 13.5 14.5 15.5 16.5 17.5 18.5 Energy per bit to Noise Ratio, Eb/No (dB) Figure 4.4 An approximation of the average BKER for concatenated coding scheme with an outer (63,47) RS code and an inner (a) rate 3/4 32-state TCM code; and (b) rate 3/4 8-state TCM code. By substituting the BKER values from (4.22) into (4.25) and (4.26). Plots of BER for the same two coding systems are presented. Figure 4.5 illustrates the average BERs of the concatenated coding schemes based on two inner TCM codes and an outer RS code with infinite interleaving in the presence of Rayleigh fading at different SNR. Again, the BER performances of the two coding schemes appear similar to that shown in figure 4.4. The 32-state trellis concatenated coding scheme achieves more than 3dB coding gain over the 8-state trellis at high SNR at a 10"10 BER value. These analytic results will be compared with the simulation results in chapter 6. Chapter 4 Performance Analysis of Concatenated Coding 37 Figure 4.5 An approximation of the average bit error rate for concatenated coding scheme with an outer (63,47) RS code and an inner (a) rate 3/4 32-state TCM code; (b) rate 3/4 8-state TCM code. Chapter 5 Design of System Model In many communication environments, a reliable simulation model is very important in evaluating the performance of complicated system designs. In this chapter, we use a simula-tion approach to look at our concatenated coding scheme. With the proper choice of simula-tion tool and model set up, a well-defined simulation model can be used to represent a real life system. The simulation tool used in this thesis is the Signal Processing Workstation (SPW™) [16]. In the following sections, we give an overview of SPW™ and we also discuss the overall design of the communication system model used in our simulation. Finally, we will discuss the validation of our simulation model. 5.1 General Overview of SPW The SPW™ is a software package for developing, simulating, debugging and evaluat-ing digital signal processing (DSP) and communication system algorithms. It provides an advanced computer-aided engineering tools and a complete DSP block library. Using these tools, one can build many types of DSP systems out of library blocks, simulate the system, and generate a hardware implementation of the design. SPW also provides a graphical user interface for all aspects of system design, simulation and implementation. 5.1.1 Basic Components in SPW The SPW™ software package is divided into different program modules that run 38 Chapter 5 Design of System Model 39 under a "windowing" environment on the computer workstation. They include File Manager, Block Diagram Editor (BDE), Signal Calculator (SigCalc) and Simulator (SPB). The functions of theses modules are summarized in table 5.1. Name of Module Function File Manager The File Manager is the "windowing" tool from which one invokes an SPW tool. It also manages all types of SPW data files and one can select and run the SigCalc and B D E from the File Manager. Block Diagram Editor (BDE) The B D E is the basic design environment for DSP systems. From the B D E , one can place graphical symbols representing the system's elements on the screen and link them up to form a signal flow diagram. In a simulation, signal values flow from the output of one block to the input of the next. Signal Calculator (SigCalc) The SigCalc can display, edit and analyze all types of signal waveforms gener-ated from the simulations. There are two main types of SigCalc windows. They are the "signal page" and "analysis page", from which one can edit and analyze the signal respectively. Simulator (SFB) The SPB converts the signal flow block diagram from the B D E database into an executable program that simulates the behavior of the signal processing system. It then places the simulation's outputs into the SigCalc database. Table 5.1 Summary of S P W I M modules' functions In addition to the basic program modules in SPW , there are two main categories of DSP blocks: the functional blocks and the "custom-coded" blocks (CCBs). The functional blocks are supplied with SPW™ in the DSP block libraries. These blocks are commonly used in the BDE to build models of signal processing systems and they are divided into separate libraries for different simulation purposes. Table 5.2 gives a summary of different DSP block libraries. However, if the system includes elements that cannot be modeled effectively by existing blocks in the libraries, the user has to create CCBs. To incorporate CCBs, template files in ' C code will automatically be created by the CCBs function in SPW™. The user can Chapters Design of System Model 40 edit the source code to define the functionality of the block. After adding the compiled code to a "simulation kernel", a corresponding symbol block is created. One can use the CCBs as elements of a simulation hierarchy in the same way as standard library blocks. After saving the CCBs, they can be used repeatedly without additional programming. Library Name Content Adaptive (adapt) library It contains Least-Means Squared (LMS) and Recursive Least Square (RLS) adaptive filter blocks. Communication (comm) library It contains a set of communication design applications: encoders/ decoders, modulators/demodulators, estimator etc. Filler dill) library It contains the filter blocks of various types: frequency domain, time domain, Bessel, Chebyshev etc. Instrument (iii) library It contains blocks which facilitate the interface of SPW™ with HP and Acurex 7000 MDAS devices. Simulation Program Builder (spb) library It contains the basic signal processing blocks such as linear and non-linear processing blocks, vector processing blocks etc. Table 5.2 Summary of DSP block libraries in SPW 5.2 Simulation Model A communication simulation model usually consists of three major components: the transmitter, the channel and the receiver. The block diagram of our system model is illustrated in figure 5.1. The task of the transmitter is to encode the source information with adequate interleaving and transmit it over the channel as a signal waveform. The channel is Rayleigh fading with AWGN. The task of the receiver is to implement the decoding algorithm and make the best estimate of the source information from the received signals. Each major component in the simulation is described in detail in this section. A block diagram of the complete SPW™ simulation model is given in Appendix C. Chapters Design of System Model 41 Random Data Source Error Estimator Transmitter Receiver \ . / Channel Rayleigh Fading AWGN Figure 5.1 Block diagram of simulated system model 5.2.1 Transmitter Structure The transmitter uses two levels of coding. They are RS code and TCM code as illustrated in figure 5.2. Data Source Reed Solomon Encoder Interleaver Trellis Coded Modulator Complex Signals Figure 5.2 Block diagram of transmitter The transmitter first takes the binary bit stream from the random source generator. The functional block, " R A N D O M D A T A " , from the SPW™ (comm) library generates a random bit Chapter 5 Design of System Model 42 stream with equal probability of 1 or 0. The random data is then fed into the functional block "REED-SOLOMON ENCODER", from the SPW™ (comm) library. This block encodes informa-tion bits at the input and produces coded bits for the output using RS coding. Its parameters include the block length and the number of information symbols per code block. The coded RS block is then interleaved using the functional block " INTERLEAVE", from the SPW™ (comm) library. This block outputs the same data stream as the input stream, but it differs in a rearrangement of order depending on two predefined parameters: the span and the depth. The interleaved RS symbols are later modulated through the functional "TCM" block, from the SPW™ (comm) library to some PSK signals for transmission. This modulator block is a general two dimensional trellis coded modulator which encodes the input symbol and produces a coded complex output symbol. The complex symbol can be thought of as the complex envelope representation of a modulated signal using phase shift keying in two dimensions. The state transitions and corresponding signal constellation are specified in a separate file as described in Appendix D. 5.2.2 Channel Model It is assumed that there is no line-of-sight between the transmitter and the receiver, and therefore a Rayleigh fading channel model is adopted. With the combination of the inner interleaver/deinterleaver pair, each received signal is independent of fade. For the effect of fading on the phase of the received signal, we assume it to be fully compensated by tracking it with pilot tone calibration techniques [29, 30]. Thus, our results will reflect only the degrada-tion due to the effect of the fading on the amplitude of the received signal. The probability Chapter 5 Design of System Model 43 density function (pdf) for the normalized amplitude fading random variable, a, is given by "2 p(a) = 2aexp(-a ) (5.1) The above equation is implemented using two Gaussian random variables, as shown in figure 5.3, in pur simulations. The basis for this implementation is given in Appendix E. N(0, 0.5) Figure 5.3 Block diagram of Rayleigh fading amplitude simulator The transmitted signal is multiplied by the simulated fading amplitude generated in the CCB " R A Y L E I G H FADING AMPLITUDE " as shown in Appendix C . Furthermore, the thermal noise and the effect of other interferences is modeled by an additive white Gaussian noise source with double sided power spectral density NJ2. We then add the transmitted signal to the output of the functional block " C O M P L E X WHITE NOISE" from the SPW™ (comm) library. This block generates complex Gaussian white noise with user-defined mean value and variance as parameters. 5.2.3 Receiver Structure With the assumption of perfect channel state information (CSI), the PSK signal is Chapter 5 Design of System Model . 4 4 demodulated using 1) the conventional Viterbi decoding algorithm and 2) the SOVA as shown in figure 5.4. Complex Received Signals I • Trellis Coded • Demodulator Rayleigh amplitude Figure 5.4 Block diagram of receiver For the conventional Viterbi decoding, the functional block, "TCM DEMODULATOR", from the SPW™ (comm) library is applied. This block performs the general Viterbi decoding using the Euclidean distance between incoming complex symbols as the metric in (3.10). The state transitions and corresponding output to be used by the decoder are specified in the same file described in Appendix D, as in the TCM encoder. This block also takes the Rayleigh fading amplitude as the average power of the incoming signal. This can be used to calculate the signal gain of the channel and to normalize the power of the incoming symbols. This block has an additional parameter for the truncated path length which defines the length (number of branches) of the survivor path kept in the decoder. For SOVA, there is no functional block in the standard SPW™ DSP library can apply. In order to perform the desired operation, the CCBs function is used. This generates a CCB based on the source code we supplied to perform our desired function. The source code for the SOVA is given in Appendix F. After compiling the source code of SOVA, the code is then Deinterleaver Reed Solomon Decoder Data Chapter 5 Design of System Model 45 linked to the simulation kernel. A new C C B of "SOFT T C M DEMODULATOR" is created and added to the blocklist in S P W ™ . This block performs the operation of S O V A as described in section 3.2. It demodulates the received P S K signal and outputs its corresponded symbol with or without erasure. It also provides an extra parameter for the erasure threshold which regulates the declaring of an erasure when two survivor paths are sufficiently close. A t the output of the "SOFT T C M DEMODULATOR", the decoded symbols are fed into a functional block "DEESfTERLEAVE" from the S P W ™ (comm) library. This block performs the inverse operation to that of interleaving by rearranging the input sequence. It has two parame-ters: the span and the depth, as in the block "INTERLEAVE". After deinterleaving, the symbol sequence is decoded using a functional block "REED-SOLOMON DECODER" from the S P W ™ library. This block uses R S decoding to decode coded bits at the input and produces informa-tion bits at the output. Finally, to evaluate the error performance of the communication system, the received bit sequences are compared with the source information sequences using an error estimator. A C C B "BLOCK ERROR ESTIMATOR" (see Appendix C) is used for the estimation of block error performance. The simulation results are given in chapter 6. 5.2.4 Simulation Parameters To make the simulation as flexible as possible, many parameters can be changed by the user. In this section, we explain the usage of the different parameters appearing in the simula-tion. The efficiency of the decoding algorithm is also closely related to the setting of three Chapter 5 Design of System Model - • ' " . 46 different parameters: 1) the span of the outer interleaver, 2) the depth of the outer interleaver and 3) the erasure threshold of the SOVA. 1. Block length This defines the number of symbols in a coded RS block. For an (n, k) RS code, n is the "Block length" and is of the form n = 2m -1, m = 2, 3, 4,... etc. 2. Information symbol (for RS code) This defines the number of source information symbols at the input of the RS encoder. It must be less than or equal to "Block length". For an (n, k) RS code, k is the "Information symbol." 3. Bit per RS (for RS code) This represents the number of information bits per RS symbol. It is equal to log 2(Block length +1). 4. Span (for outer interleaving) This is the number of elements stored in one row of the interleaver. The total delay of the interleaver is equal to "span" x "depth". 5 . Depth (for outer interleaving) This is the number of elements stored in one column of the interleaver. 6. State (for TCM code) This defines the number of possible states for each trellis extension. It is usually set to a power of 2. 7. PSK signal (for TCM code) Chapter 5 Design of System Model 47 This represents the number of possible signals in the signal space and is usually set to a power of 2. 8. Bit per TCM (for TCM code) This defines the number of bits per one uncoded T C M symbol at the input of T C M encoder. The total number of possible inputs is then equal to 2 to the power of "Bit per T C M " . 9. Erasure threshold (for TCM code) This represents -ln(R) in (3.12) and this sets the decision threshold for SOVA. Accord-ing to (3.12), if the two best paths' metrics difference is less than "Erasure threshold," an erasure occurs at those branches in which two paths differ. 10. Filename (for TCM code) This specifies the name of an existing text file which contains the state table for the T C M encoder/decoder as described in Appendix D. 11. Es/No (for channel model) This denotes the signal to noise ratio in dB. In this thesis, error rates are usually expressed in terms of "Es/No." 5.3 Validation of the Simulation Model In order to ensure that the simulation model truly reflects the performance of the communication system, it is very important that the simulation model be set up properly and accurately. One of the possible validation steps is to compare the simulation results with theoretical values. In this section, we examine the two CCBs: " R A Y L E I G H F A D I N G Chapter 5 Design of System Model 48 AMPLITUDE" and "SOFT T C M DEMODULATOR" because they are user-made blocks. 5.3.1 Rayleigh Fading Simulator In order to ensure that samples of the block "RAYLEIGH FADING AMPLITUDE" follow a Rayleigh distribution, 100,000 samples of the output of the block were used to estimate the cumulative distribution function (CDF). The theoretical Rayleigh CDF is obtained by integrat-ing (5.1), i.e. r P(a<r) = jp(a)da = l - e x p ( - r 2 ) (5.2) o Figure 5.5 shows the analytic and simulation results. It can be observed that the simulation results agree closely with (5.2). Fading amplitude Figure 5.5 Theoretical and simulation Rayleigh fading amplitude distributions Chapter 5 Design of System Model 49 5.3.2 SOVA "Custom-coded" Block The theoretical analysis on SOVA is not available. In order to validate the source code for this block, we first treat it as a Viterbi decoding block. By setting its erasure threshold to zero, no erasure will be declared. The SOVA block should then perform like a conventional Viterbi decoder. The simulation results can be compared with the theoretical values of conven-tional Viterbi decoding. Signal to Noise Ratio, Es/No (dB) Figure 5.6 The average symbol error probability of rate 3/4, 8-state trellis-coded 16-PSK modulation using 1) analytical method and 2) simulation method. Figure 5.6 shows the symbol error rates Ps obtained using two different methods. Both curves are obtained for the same T C M code over a Rayleigh fading channel. The theoretical values of Ps is actually reproduced from figure 4.3. The simulated results of Ps from the SOVA CCB agree closely with the theoretical results. Chapter 6 Simulation Results and Discussion In order to study the performance with SOVA in concatenated coding, simulations have been performed, since the preceding analytic study of concatenated coding is only applicable to errors-only decoding (without SOVA). Given all the simulation assumptions defined in chapter 5, the semi-analytical results of using SOVA are obtained by SPW™ simulation for the inner codes and the analytical bound from (4.22) for the outer code. The BER and BKER for without SOVA are compared with the analytic values described in chapter 4. Moreover, the effect of finite interleaving for the outer code is discussed in section 6.3. 6.1 The Basic Model In this section, the error performance of the basic model of concatenated coding is considered. This model refers to an inner rate 3/4 trellis coded 16-PSK modulation with conventional Viterbi decoding (errors-only decoding) and an outer (63,47) RS code with perfect interleaving over a Rayleigh fading channel. Both BKERs and BERs are obtained from simulations. The simulated results are compared with the theoretical values when available. 6.1.1 Error Performance of the Basic Model Throughout the simulations in this thesis, four different inner trellis codes are used. They are U433, V433, U435 and V435 codes, as described in table 6.1. The simulation results are based on 60,000,000 random sample bits which make a total number of 158,729 RS 50 Chapter 6 Simulation Results and Discussion codewords. 51 Code Name Descriptions U433 Ungerboeck code: rate 3/4, 8-state trellis coded 16-PSK modulation. V433 Vucetic code: rate 3/4,8-state trellis coded 16-PSK modulation. U435 Ungerboeck code: rate 3/4, 32-state trellis coded 16-PSK modulation. V435 Vucetic code: rate 3/4, 32-state trellis coded 16-PSK modulation. Table 6.1 Descriptions of the four trellis codes used The BER and BKER simulation results of the basic model are illustrated in figure 6.1. o o 9.5 10.5 11.5 12.5 13.5 14.5 15.5 9.5 10.5 11.5 12.5 13.5 14.5 15.5 Energy per bit to Noise Ratio, Eb/No (dB) Energy per bit to Noise Ratio, Eb/No (dB) (a) (b) Figure 6.1 (a) BKER and (b) BER simulation results on different inner trellis codes: i) U435 code, ii) V435 code, iii) U433 code and iv) V433 code of the basic model with perfect interleaving. By comparing the BKERs and the BERs of the four codes, the V435 inner code achieves the best error performance with more than ldB coding gain over the other codes at Chapter 6 Simulation Results and Discussion 52 high SNR (>16dB). This V435 code represents a 32-state trellis with the length of the shortest error event path Lmin equal to 2 (see section 4.1.4). This means that it uses no parallel transi-tion, and for each error event occurred, the error path must carry at least 2 consecutive symbol errors. At sufficient high SNR and with infinite inner interleaving, consecutive symbol errors are less often to happen. And therefore, it is less likely for the V435 code to have an error event in two or more consecutive symbol errors than for the other codes (with parallel transi-tion) to have the same errors. In contrast, when the channel performance is worse at low SNR (<14dB), signal errors are more severe. Error performances for most codes are worse in general. Therefore, the V435 inner code results in a similar BKER and BER with the others at low SNR; • 0 0 Figure 6.2 (a) BKER and (b) BER results for the V433 inner code and the basic model by simulation and theoretical analysis. Chapter 6 Simulation Results and Discussion 53 The analytic approximations of BKER and BER described in chapter 4 are illustrated in figure 6.2. We use the V433 inner code for illustration. The BKER and BER analytic approximation curves are close to the simulation values. Moreover, the upper bound estima-tions reproduced from figure 4.3 and figure 4.4 give loose bounds on the simulation results which further confirm the simulation values. 6.1.2 Effect of No Outer Interleaving The task of the outer interleaver is to break the symbol error bursts introduced by the inner Viterbi decoder. With infinite interleaving, errors are spread out evenly to each block. With no outer interleaving, the error bursts occurring in an RS codeword can easily exceed the error correcting capability of the RS code. Figure 6.3 (a) BKER and (b) BER results with different inner trellis codes: i) U435 code, ii) V435 code, iii) U433 code and iv) V433 code and the basic model without outer interleaving. Chapter 6 Simulation Results and Discussion 54 Figure 6.3 illustrates the effect of no outer interleaving for the basic model using the four inner trellis codes. The BKER and BER results show that the four inner trellis codes have a similar error performance in the absence of outer interleaving. A comparison with figure 6.1 shows that the error performance of the system without outer interleaving is much worse than with infinite interleaving. To understand this, since the symbol error bursts at the output of the inner decoder are without being interleaved, they are kept in the same RS codewords. These error bursts exceed the error correcting capability of RS code and cause the major reason for this performance degradation. In contrast, if the symbol errors are spread evenly to each RS codeword in the presence of infinite interleaving, each RS codeword has a small number of symbol errors which do not exceed the error correcting capability of RS code. 6.1.3 Comparison of Single Code with Concatenated Code To assess the advantage of concatenated coding, we consider two single code systems as described in table 6.2. System Single Code Descriptions 1 a (63,47) RS code with uncoded 8-PSK modulation. 2 an uncoded 47 symbol block (6 bits per symbol) with V433 trellis coded modulation. Table 6.2 Descriptions of two single code tested systems. In both coding systems, we assume a Rayleigh fading environment with perfect interleaving. Figure 6.4 compares the BKER and BER results of the V433 inner code for the basic model with the BKER and BER results for the two single code systems. The BKER curves for the concatenated coding system at a 10"1 error rate value shows a coding gain of Chapter 6 Simulation Results and Discussion 55 about 4dB compared to the single code systems. 10 r**-10 PQ >; -2 I g pa 10 t 10 t 10 V433 Inner Code T C M only RS only Concatenated code Energy per bit to Noise Ratio, Eb/No (dB) (a) 10 10 Pi w PQ g T C M only RS only Concatenated code Energy per bit to Noise Ratio, Eb/No (b) (dB) Figure 6.4 A comparison of the (a) B K E R and (b) B E R results of the V433 inner code of the basic model and two single code systems: i) trellis coded modulation only, and ii) Reed Solomon code only. 6.2 The Modified Model (SOVA) In the SOVA simulation model, we replace the conventional Viterbi algorithm of the basic concatenated coding model with the SOVA and the outer RS decoding is also modified with the errors-erasures decoding. Theoretically, by using the erasure decoding technique, the outer RS decoder may be able to identify more possible error locations which can enhance the overall performance of the concatenated code system. In this section, we first determine an optimum erasure threshold for the SOVA and then look at the BKER and BER results of this modified simulation model. Chapter 6 Simulation Results and Discussion 56 6.2.1 Optimum Erasure Threshold Unfortunately, the optimum erasure threshold R of SOVA cannot be determined analytically. A trial and error method was used to estimate the appropriate erasure threshold for a given trellis code. In our simulations, we choose five various values of erasure threshold from (3.12) for the inner V433 and U435 codes of the system model as summarized in table 6.3. Case Choice of Erasure Threshold, R 1 -\n(R) = 0.0000 2 -ln(/?) = 0.0333 3 -ln(R) = 0.0200 4 -\n(R) = 0.0125 5 -ln(R) = 0.0100 Table 6.3 Five erasure thresholds considered. The BKER simulation results for the five predefined erasure thresholds are illustrated in figure 6.5. The results show that the erasure threshold of -\n(R) = 0.02 yields the best error performance among the five thresholds. If R is too small, very few erasures will be declared and the error performance will be close to that of conventional Viterbi decoding. If R is too large, the declared erasures will include too many false alarms. The resulting performance might be even worse than that of the basic model (errors-only decoding). Chapter 6 Simulation Results and Discussion 57 o o 9.5 10.5 11.5 12.5 13.5 14.5 15.5 9.5 10.5 11.5 12.5 13.5 14.5 15.5 Energy per bit to Noise Ratio, Eb/No (dB) Energy per bit to Noise Ratio, Eb/No (dB) (a) (b) Figure 6.5 A comparison of various erasure thresholds based on the BKER results of (a) the V433 inner code, and (b) the U435 inner code of the modified SOVA model. 6.2.2 Error Performance of the Modified Model After choosing a good threshold for the SOVA, we can look at the error performance of the modified SOVA model. Figure 6.6 summarizes the BKER and BER results of the modified SOVA model using the four different inner trellis codes. The erasure threshold used is -\n{R) = 0.02. Chapter 6 Simulation Results and Discussion 58 Figure 6.6 (a) BKER and (b) BER simulation results for various inner TCM codes concatenated with a (63,47) RS code and the modified SOVA model with erasure threshold -ln(7?) = . 0.02. Again, the V435 inner code of this modified model attains the best error performance among the four inner trellis codes. However, the coding gain of the V435 inner code over the other three codes is less significant compared to the basic model, as illustrated in figure 6 .1. It achieves less than ldB gain over the other codes at high SNR. For a more detailed study of SOVA on the different trellis codes, we consider the BKER for each individual code. Chapter 6 Simulation Results and Discussion 59 o o Energy per bit to Noise Ratio, Eb/No (dB) • Energy per bit to Noise Ratio, Eb/No (dB) (a) (b) Figure 6.7 The BKER results of the SOVA simulation model using (a) U433 inner code and (b) V433 inner code for four different conditions: i) without erasure and without outer interleaving, ii) with erasure and without outer interleaving, iii) without erasure and with perfect outer interleaving, and iv) with erasure and with perfect outer interleaving. From figure 6.7, we can observe that the SOVA does not have the same improvement for all codes. At high SNR, the enhancement of using SOVA with U433 code can bring up to ldB gain over the conventional Viterbi decoding at a 10"4 BKER value, while the benefit of using SOVA in V433 code is smaller. In addition, we also consider the error performances of concatenated coding with the two inner 32-state trellis codes. Chapter 6 Simulation Results and Discussion 60 o. • o Energy per bit to Noise Ratio, Eb/No (dB) Energy per bit to Noise Ratio, Eb/No (dB) (a) (b) Figure 6.8 The BKER results of the SOVA simulation model using (a) U435 inner code and (b) V435 inner code for four different conditions: i) without erasure and without outer interleaving, ii) with erasure and without outer interleaving, iii) without erasure and with perfect outer interleaving, and iv) with erasure and with perfect outer interleaving. In figure 6.8(b), although the overall gain has more than 2dB at low BKER values over the system with neither interleaving nor erasure decoding, the benefit of using SOVA in V435 code is very small. In figure 6.8(a), the improvement of using SOVA with the U435 inner code is larger. At high SNR, the BKER curve with SOVA shows that there is a ldB gain over the system with errors-only decoding. Generally speaking, the SOVA and erasure decoding technique can improve the error rate of the concatenated code. However, the amount of improvement is very dependent on the Chapter 6 Simulation Results and Discussion 61 choice of trellis code. 6.3 Finite Interleaving The purpose of interleaving is to break error bursts. Theoretically, the larger the span and depth of the deinterleaver, the better is the error burst spread out. However, in many applications, infinite interleaving is not practical. Especially in the case of outer interleaving, the span and depth of the outer interleaver/deinterleaver are usually 4 or 5 times larger than those of the inner interleaver/deinterleaver [20]. The corresponding time delay for outer interleaving is therefore much longer than that of inner interleaving. Whenever the span and the depth of the interleaver is limited to a certain time or memory constraint, we have finite interleaving. In this section, we will study the effect of finite interleaving at the outer interleaver/deinterleaver pair. 6.3.1 Error Performance of Finite Interleaving The BER and BKER performances of concatenated coding with finite interleaving are investigated by simulations in this section. First of all, we decide on the amount of memory storage at the outer interleaver/deinterleaver pair. By keeping the product of the span S and the depth D constant, we keep the same number of symbols stored in the interleaver. As an example, we fix the memory storage of the outer interleaver at 630 RS symbols. The span and depth pairs are chosen in table 6.4. Chapter 6 Simulation Results and Discussion 62 Case 1!!!!!^  (in RS symbol) l i i l i i ^ (in RS symbol) SxD (in RS symbol) 1 5 126 630 2 10 63 630 3 21 30 630 4 30 21 630 5 63 10 630 6 126 5 630 Table 6.4 . Span and depth distribution of the outer interleaver/deinterleaver Figure 6.9 illustrates the BKER and BER results of finite interleaving in a modified SOVA model. Given a certain size of interleaving, the error performance is proportional to the size of the span, i.e. a larger span/smaller depth pair results in a better performance. The performance difference between a good and a bad choice for S (and D) can be more than IdB at low BKER (<14dB). However, it is also observed that when the span reaches 63, which is the block length of RS code, the BKER can hardly be improved. And, the results of BKER taking a larger span interleaving (DxS: 5x126) are actually slightly worse than that of the 63-symbol span interleaving (DxS: 10x63). Chapter 6 Simulation Results and Discussion 63 Energy per bit to Noise Ratio, Eb/No (dB) Energy per bit to Noise Ratio, Eb/No (dB) (a) (b) Figure 6.9 (a) BKER and (b) BER results of using finite outer interleaving in the SOVA model with various depth D and span S: i) DxS: 5x126, ii) DxS: 10x63, iii) DxS: 21x30, iv) DxS: 30x21, v) DxS: 63x10, and vi) DxS: 126x5. The effect of finite interleaving in the basic model (errors-only decoding) is also studied using simulation. Again, we assume a constant size of the outer interleaver as 630 RS symbols. The BKER and BER results are illustrated in figure 6.10. The effect of finite interleaving on error performances are similar to those observed for the SOVA model. The best BKER is again achieved by the depth and span pair equal to 10 by 63 RS symbols respec-tively. Hence, we conclude that for a good choice for a good error performance with a limited memory constraint would be when there is a span of the outer interleaver equal to the block length of the outer code. Chapter 6 Simulation Results and Discussion 64 Pi » 10 Ir -§ § A UJ -4 •a 1 0 o PQ i o > 10. V433 Inner Code DxS:5xl26 DxS: 10x63 e DxS:21x30 x DxS:30x21 o DxS:63xlO G DxS: 126x5 A 9.5 10.5 11.5 12.5 13.5 14.5 15.5 Energy per bit to Noise Ratio, Eb/No (dB) (a) 10.5 11.5 12.5 13.5 14.5 15.5 Energy per bit to Noise Ratio, Eb/No (dB) (b) Figure 6.10 (a) BKER and (b) BER results of using finite interleaving in the basic model with various depth D and span S: i) DxS: 5x126, ii) DxS: 10x63, iii) DxS: 21x30, iv) DxS: 30x21, v) DxS: 63x10, and vi) DxS: 126x5. To further discuss this phenomenon, we use an example to illustrate the performance for various spans and depths of interleaving. Suppose we receive 10 blocks of 63 RS symbols at the input of the outer deinterleaver and the first 80 symbols of these blocks are corrupted by error bursts. Since the error correcting capability of (63,47) RS code is 8 symbol errors, the 10 RS blocks will be error-free if the 80 errors are evenly spread out. Here, we apply three differ-ent types of deinterleaving with depths and spans as 10x63, 30x21 and 5x126 RS symbols respectively. The operations of these three outer deinterleavers are illustrated in figure 6.11. Chapter 6 Simulation Results and Discussion 65 © II 41 Q o a. Q ll si o. <u Q Input of Deinterleaver {elt e2, e3 e80, C 8 1 , C 8 2 , . . . . C 6 3 0 ] V, USL (a) (b) (c) ILL .£20-Span = 63 Span = 21 Span = 126 '621 C622 621 77 6M e, ^601 ^602 e3 e33 em -MO— e, ^626 eo e7 ^627 ei e8 ^62R ed es em C63Q Output of Deinterleaver ^ ' j '? ~^*? } ( e j , e 7 1 , C 8 1 , C 6 2 1 ) ( e 2 , e 7 2 , C 8 2 , . . . . C 6 2 2 ) ( e 1 0 , e 8 0 , C 9 0 C 6 3 0 ) {E/? -E^  -E> -E) ^ —'y } (el> e31' e61' ^601' e2> e32> —^603) (e4, e34, e64, C 6 0 4 , e5, e35, . . . C 6 0 6 ) (e28' e58> C88> •- C628> e29> e59> -C63o) { I E ) t'? -Ej IE5 -^^ 5 ^*} ~~ ( e j , e 6 , C n , . . . , C 3 1 J ) (C3I6' C321< C326> •••'C626) (C320> C325' C330< -<C63o) where E is an error block which has more than 8 symbol errors e C is an error-free block which has less than 9 symbol errors e Figure 6.11 Diagram of outer deinterleaver with various span and depth: (a) DxS = 10x63, (b) DxS = 30x21, and (c) DxS = 5x126. We observe from figure 6.11 that the 80 symbol errors are spread out in three different ways. With 5x126 interleaving in (c), the span of the deinterleaver is larger than the block size. The 80 symbol errors are separated into 5 output blocks having a BKER equal to 0.5. In (b), the span is 21 which is smaller than the block size, and the 80 errors are distributed into 6 output blocks having a BKER equal to 0.6. The interleaving dimensions in (b) and (c) do not yield the maximum "spread-out" of symbol errors. Finally, in case (a), the span of interleaving Chapter 6 Simulation Results and Discussion 66 is 63 which is the block length of RS code. The symbol errors are evenly separated into 10 output blocks and resulted in zero BKER. From this example, we can see that a good interleaver should have an span equal to the block length of the outer code in the finite interleaving situation. Chapter 7 Conclusions In this chapter, we summarize the main contributions of this thesis and provide some suggestions for the future work. 7.1 Summary The error performance for a concatenated coding scheme used for communication over a Rayleigh fading channel is studied. The analytic performance evaluation of the coding system is first investigated in chapter 4. Thus, a simulation model of the concatenated code based on an outer RS code and an inner TCM code is developed in chapter 5. This model has been tested and validated. The use of a soft output Viterbi algorithm (SOVA) with erasure decoding is examined using simulation and the effect of finite interleaving for the outer code is studied. In order to provide a basis for comparison, the BKER is used as the major performance parameter. With the assumption of perfect CSI and infinite inner interleaving, analytical approximations and upper bounds on BKER of the basic model (conventional Viterbi decoding) are obtained. There is close agreement between the theoretical and simulation results. It is found that the concatenated coding schemes provide significant improvement on BKER relative to the single code system. In studying the performance of SOVA and erasure decoding, the choice of the erasure threshold cannot be too small or too large. For a given BKER, the erasure threshold can 67 Chapter 7 Conclusions 68 typically change the performance of the same coding system. Moreover, it is observed that the effect of using SOVA on various TCM codes can be quite different. The improvement from using SOVA on four different trellis codes varied from 0 to ldB relative to the basic system model. Another important design factor for the concatenated code is the outer interleaver. Ideally, an infinite span and depth will generally maximize the channel throughput (packet success rate). However, the assumption of infinite interleaving is not practical in many real time applications. For a given memory size of the outer interleaver, our results show that an interleaver with span equal to the block length of the outer code yields good error perfor-mance. 7.2 Suggestions of Future Work Below is a list of topics related to concatenated coding systems which deserve further investigation: • An analytic method for determining the optimum erasure threshold in SOVA. • Search for a more efficient code than RS in handling soft output reliability infor-mation from SOVA. • Alternative SOVA algorithms. • Determination of the best packet size for the concatenated coding scheme. Glossary AWGN - Additive White Gaussian Noise BDE - Block Diagram Editor BER - Bit Error Rate BKER - Block Error Rate CCB - Custom Coded Block CSI - Channel State Information D - Depth of Interleaver/Deinterleaver DSP - Digital Signal Processing Lmin - Length of the Shortest Error Event P„ - RS Symbol Error Rate Ps - TCM Symbol Error Rate PSD - Power Spectral Density PSK - Phase Shift Keying RS - Reed Solomon S - Span of Interleaver/Deinterleaver SigCalc - Signal Calculator SNR - Signal to Noise Ratio SOVA - Soft Output Viterbi Algorithm SPB - Simulator SPW™ - Signal Processing Workstation™ TCM - Trellis Coded Modulation 69 Bibliography [ I ] G. Ungerboeck, "Channel coding with multilevel phase signals," IEEE Trans. Information Theory, vol. IT-28, pp. 55-67, Jan! 1982. [2] G. Ungerboeck, "Trellis-coded modulation with redundant signal sets part I: introduction," IEEE Communications Magazine, vol. 25, pp. 12-21, Feb. 1987. [3] G. Ungerboeck, "Trellis-coded modulation with redundant signal sets part I I : state of the art," IEEE Communications Magazine, vol. 25, pp. 12-21, Feb. 1987. [4] G. Ungerboeck and I. Csajka, "On improving data-link performance by increasing the channel alphabet and introducing sequence coding," 7976 Int. Symp. Inform. Theory, Ronneby, Sweden, Jun. 1976. [5] E. Zehavi and J.K. Wolf, "On the performance evaluation of trellis codes," IEEE Trans. Inform. Theory, vol. IT-33, pp. 196-202, Mar. 1987. [6] S. Haykin, "An introduction to analog and digital communications," New York: Wiley Series in Telecommunications 1989. [7] D. Divsalar and M.K. Simon, "Design of trellis coded MPSK for fading channels: set partitioning for optimum code design," IEEE Trans. Commun., vol. 36, pp. 1013-1021, Sept. 1988. [8] C. Schlegel and D.J. Costello Jr., "Bandwidth efficient coding for fading channels: code construction and performance analysis," IEEE Journal on Selected Areas in Commun., vol. 7, pp. 1356-1368, Dec. 1989. [9] D. Divsalar and M.K. Simon, "The performance of trellis coded multilevel DPSK on a fading mobile satellite channel," IEEE Trans. Vehicular Technology, vol. 37, pp. 78-91, May 1988. [10] G.D. Forney, "Concatenated codes," Research Monograph 37, M.I.T. Press, 1966. [ I I ] T. Kasami, T. Takata, T. Fujiwara and S. Lin, "A concatenated coded modulation scheme for error control," IEEE Trans. Commun., vol. 38, pp. 752-763, Jun. 1990. [12] Z. Siveski, R. Bozovic and D.L. Schilling, "Concatenated trellis/high rate Reed Solomon and projection codes," IEEE Int. Conf. Commun. Conf: Rec, 1989. 70 Bibliography 71 [13] J. Hagenauer and P. Hoeher, " A Viterbi algorithm with soft-decision outputs and its applications," IEEE GLOBECOM'89 Conf. Rec, Dallas, TX, vol. 3, pp. 47.1.1.-47.1.7, Nov. 1989. [14] R.H. Deng and D.J. Costello, Jr., "High rate concatenated coding systems using bandwidth efficient trellis inner codes," IEEE Trans. Commun., vol. 37, pp. 420-427, May 1989. [15] B. Vucetic, "Bandwidth efficient concatenated coding schemes for fading channels," IEEE Trans. Commun., vol. 41, pp. 50-61, Jan. 1993. [16] ComDisco System, Inc., SPW™ - The DSP Framework™ User's Guide and Tutorial, Document Version 3.0, Sep. 1992. [17] S. Lin and D. Costello, "Error control coding: fundamentals and applications," Englewood Cliffs, NJ: Prentice-Hall 1982. [18] J. Du and B. Vucetic, "New M-PSK trellis codes for fading channels," IEE Electronics Letters, vol. 26, No. 16, pp. 1267-1269, Aug. 1990. [19] E. Biglieri, D. Divsalar, P.J. McLane and M.K. Simon, "Introduction to trellis-coded modulation with applications," New York: Macmillan 1991. [20] D. Divsalar, "Trellis coded multilevel DPSK system with Doppler correction for mobile satellite channels," United States Patent, Patent No. 5,023,889, Jun. 1991. [21] D. Divsalar and M.K. Simon, "Trellis coded modulation for 4800 to 9600 bps transmission over a fading satellite channel," IEEE Journal on Selected Areas in Commun., vol. SAC-5, pp. 162-175, Feb. 1987. [22] T. Schaub and J.W. Modestino, "An erasure declaring Viterbi decoder and its applications to concatenated coding systems," IEEE Int. Conf. Commun. Conf. Rec, pp. 1612-1616, Jun. 1986. [23] C. Nill and CW. Sundberg, "List and soft symbol output Viterbi algorithms: extensions and comparisons," IEEE Trans. Commun., vol. 43, pp. 277-287, Apr. 1995.. [24] D. Divsalar and M.K. Simon, "The design of trellis coded MPSK for fading channels: Performance criteria," IEEE Trans. Commun., vol. 36, pp. 1004-1012, Sep. 1988. [25] J.K. Cavers and P. Ho, "Analysis of the error performance of trellis-coded modulations in Rayleigh fading channels," IEEE Trans. Commun., vol. 40, pp. 74-83, Jan. 1992. Bibliography 72 [26] P. Ho and D.K.P. Fung, "Error performance of interleaved trellis-coded PSK modulations in correlated Rayleigh fading channels," IEEE Trans. Commun., vol. 40, pp. 1800-1809, Dec. 1992. [27] W.C.Y. Lee, "Mobile communications design fundamentals," New York: Wiley Series in Telecommunications 1993. [28] E. Kreyszig, "Advanced engineering mathematics sixth edition," John Wiley & Sons, Inc. 1988. [29] J.G. Proakis, "Digital communications, 2nd edition," New York: McGraw-Hill, 1989. [30] J.K. Cavers, "Pilot symbol assisted modulation in fading and delay spread," IEEE Trans. Commun., vol., 1993. Appendix A. Chernoff Bound The Chernoff bound is given as follows. If x is a continuous random variable, then Pr{x>0} <E{exp(lx)} ( A . l ) where X > 0 is a parameter to be optimized. If x is itself the sum if N independent continuous random variables Xj, x 2 , t h e n the above becomes H^"'-0 -n £ { e x p ( k ' ) } (A-2> 73 Appendix B. Residue Theorem Suppose there is a contour integrals taken around a simple closed path C. jf(z)dz (BA) c If f(z) has a singularity at a point z = z0 inside C, but is otherwise analytic on C and inside C, then f(z) has a Laurent series f(z)= j^an(z-z0f + ^ 1 7 + - ^ T 2 + - (B.2) n = 0 The coefficient bj is called the residue of f(z) at z = zQ and we shall denote it by bx = Resz = 2/(z) (B.3) Let f(z) be an analytic function that has a pole of any order m > 1 at a point z = z0. Then, the Laurent Series off(z) converging near z = z0 (except at z = z0 itself) is f(z) = - ^ L - + K ~ m + . . . + ^ + a 0 + ai(z-z0) + ... (BA) (z-zf (z-zf Hence if/(zj has a pole of mth order at z = z0, the residue is given by * « w w - ^ M^z-^niA <B-5) 74 Appendix C. Block Diagram of Simulation Model L O TO D £ CO c r JJ TO SZ CT CD LY m 3 "OR z <c OR z c "OR S3 ISS ND0I :RAT I: c SSI NDO r— c UJ z I: . <c LU <E <L a : z <c CD UJ CD CD UJ CD z z: 75 Appendix C. Block Diagram of Simulation Model rv K) CS CS C3 LT) IGPS cs cs CO T CD ho • Ul CD CO Ul cc e £. cn 0 n E L CD Span epth £ c hold o \ C7> CD 0 c CD TD CD o ZP CO c o Span o CD ui — CD O r 1 ea> L CD CO CD L CD CO CD _ l L O thre <r \ K7 Ul a o C 0) tl-L Z \ Ul UJ o -*- CD CD O CD CD c CD m CO ^_ L — " O CD L -t-£ L 0 c CD L CD CJ Z> H Ul CO CO OC CO a C CD <4- c CJ C- w N TD c — — I— UJ CD a) O 0  Ul C J o JD e CD U- 0 CO m C. z CY CO t - r: 0 z CJ i— CD E CD _ C o CO cn c T D O C J T J C D CD c Q ) C D O c O C J - 1 c 5 i S —T-+ o "it-i t ,1 ft 1 °, 1 ^.SIGNAL e i 1 J J R i g a 1 :5 nnoo T - 1 * i • • • it 31dU«S NMOQ Appendix C. Block Diagram of Simulation Model Appendix D. Example of T C M file in SPW T M The first line of the file specifies N, K and L, where 2N is the total number of signals in the signal space, K is the input vector length, and 2L is the number of possible states. The second line is ignored and can be used for labeling the columns of the succeeding lines. The rest of the file specifies the state transition and output symbol "transmitted" given the current state and input. Example: Rate 2/3,4-state trellis coded 8-PSK modulation s t a t e O t 0' 0 0 0 1 1 1 1 2 2 2 2 3 3 3 • 3 2 2 i n p u t s t a t e @ t + l 0 1 2 3 0 1 2 3 0 1 2 3 0 1 2 3 0 0 1 1 2 2 3 3 •1 1 0 0 3 3 2 2 r e a l - o u t p u t 0 .923879532 -0 .923879532 0 .382683432 -0 .382683432 0 .923879532 -0 .923879532 -0 .382683432 0 .382683.432 0 .923879532 -0 .923.879532 0 .382683432 -0 .382683432 0 .923879532 -0 .923879532 - 0 . 3 8 2 6 8 3 4 3 2 0 .382683432 i m a g - o u t p u t -0 .382683432 0 .382683432 0 .923879532 -0 .923879532 0 .382683432 -0 .382683432 0 .923879532 -0 .923879532 -0 .382683432 0 .382683432 0 .923879532 -0 .923879532 0 .382683432 -0 .382683432 0 .923879532 -0 .923879532 78 Appendix E . Rayleigh Distribution Consider a complex phasor rel% which may be written as ie re = x + ty (E.1) where x = r cos 6 y = r sin 9 (E.2) If x and y are Gaussian random variables, their probability density function are given by PX(X) = py(y) 1 J: :exp 27ta 1 :exp 27TO V 2 0 y V 2a2 y (E.3) Here, o 2 is the variance of the two random variables x and y. And if x and y are independent, the joint density function is given by , x •, . , , exp((-U 2 + y 2 ) ) / ( 2 a 2 ) ) 27ta (E.4) But p r 6 ( r6 ) drdQ = pxy(xy) dxdy (E.5) 79 Appendix E. Rayleigh Distribution 80 and transforming differential areas such that rdrdQ = dxdy (E.6) where r2=x2+y2. Substitute (C.4) and (C.6) into (C.5), we have 2 2 prQ(rQ) drdQ = p (xy) rdrdQ = Y e x P ( ( ~ r > ^ 2 a ^ drdQ (E.7) 2KG If r and 9 are independent, we have PreirQ) = pr(r)pe(Q) (E.8) where p M ) = r exp(-r2A2o2)) o (E.9) Therefore, pr(r) is the Rayleigh distribution generated from two Gaussian random 2 variables x and y. If o = 0.5, pr(r) = 2r exp(-r 2) (E.10) which express the same equation as (5.1). A p p e n d i x F. Source code o f SOVA The fallowings list the source code of implementing SOVA in SPW 1 M simulation software. • i n c l u d e " s p w _ p l a t f o r m . h " t t i f d e f UNIX ' . • . # i n c l u d e " c a e d a t a / p a t r i c k p l i b / s o f t _ t c m / b l o c k c o d e / s o f t _ t c m u . c " # e l s e ' # i f d e f VAX_VMS •• • i n c l u d e " [ c a e d a t a . p a t r i c k p l i b . s o f c _ c c m . b l o c k c o d e ] s o f c_ccmu.'c" t t e n d i f VAX_VMS #endif UNIX s t a t i c c h a r 'REVISION = "2.50"; / * • • * B l o c k F u n c t i o n : s o f t _ t c m * L i b r a r y : p a t r i c k p l i b - ' *' Date: Sun J u l 16 10:52:45 1995 . . . */ /* . . • . V /* FEED_THROUGH_LIST INFORMATION: . " ' */ / * ' */' /* • --> FEED_THROUGH_TYPE IS NOT EDITABLE. The BDE p a r a m e t e r */ /* s c r e e n a s s o c i a t e d ' w i t h t h e b l o c k must be e d i t e d t o change */ /*. t h e b l o c k ' s FEED_THROUGH_TYPE. ,. */' / * ' ' • . * / /* FEED_THROUGH_TYPE = ALL_FEED_THROUGH. /' */ /* */ ^ l t * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * / * *•/ /*• LINK_OPTIONS INFORMATION: - */ / * • ' * * / /* --> The LINK_OPTIONS l i s t i s e d i t a b l e . I t c o n t a i n s all t h e */ /* l i b r a r i e s w h i c h t h e code must be l i n k e d t o . Each i t e m i n */ /* t h e l i s t must be s u r r o u n d e d by .double q u o t e s and */ /* s e p a r a t e d by commas. The math l i b r a r y i s a u t o m a t i c a l l y */ /* l i n k e d , and does n o t need t o be s p e c i f i e d . The p a t h s ' */ /* may be s p e c i f i e d as f u l l p a t h s . o r as p a t h s r e l a t i v e t o */ 7* t h e h o s t . . */ /* A l i n k o p t i o n can a l s o be s p e c i f i e d . i n t h e form " - I x " */ /*' (where x i s d e f i n e d i n t h e UNIX manual on " I d " */ /* ' ' . ' V /« IMPORTANT: The e n t i r e LINK_OPTIONS l i s t must be d e l e t e d */ /* i f i t d o e s n ' t c o n t a i n any e l e m e n t s . */ / * ' * / /* Sample LINK_OPTIONS l i s t : ' . *7 /* ' ( A c t u a l l i s t s h o u l d be p l a c e d below t h i s comment b l o c k ) */ 81 Appendix F. Source code of SOVA /* V /• LINK_OPTIONS = ( "-lm", . */ /* "//host/code/lib/sample.a" } ,- */ /* V /" */ ^ * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *.* + /* • • v /* INCLUDE_DIRS INFORMATION: */ /* */ /" --> The INCLUDE_DIRS l i s t i s e d i t a b l e . The l i s t should */ /* contain a l l d i r e c t o r y search paths needed to l o c a t e a l l */ /* the include f i l e s used by' t h i s block. I t has the same . */ /* format as the LINK_OPTIONS l i s t . */ / * ' * / /* IMPORTANT: The e n t i r e INCLUDE_DIRS l i s t must be delete d */ /* i f i t doesn't contain any elements. */ /* • */ /* Sample INCLUDE_DIRS l i s t : _ */ /* (Actual l i s t should be placed below t h i s comment block) */ /* . V /• INCLUDE_DIRS = { "//host/u/code/include", V /* , " / / h o s t / l i b / d i r " }; */ / * * / /* . */ /* V /" EDITABLE FUNCTIONS */ /* --> I n _ s o f t _ t c m _ p a t r i c k p l i b () */ /* --> R o _ s o f t _ t c m _ p a t r i c k p l i b () */ /* --> T e _ s o f t _ t c m _ p a t r i c k p l i b () V /* •-' • • V /* St r u c t u r e use: */ /* T y p i c a l input value reference */ /* l o c a l _ v a r = *(spb_input->var_name); */ /* **0R** l o c a l _ v a r = I_var_name; */ /* T y p i c a l output value update */ /* spb_output->var_name = l o c a l _ v a r ; V /* **0R** 0_var_name•= l o c a l _ v a r ; */ /' T y p i c a l parameter reference */ /* l o c a l _ v a r = spb__parm->var_name; */ /* **0R** l o c a l _ v a r = P_var_name; */ /* V /* (See reference manual f or f u r t h e r information) */ /* */ * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * / * I n i t i a l i z e Function (must be present) * --> I f e d i t i n g , modify only the l i n e s w i t h i n the * function's opening and c l o s i n g brackets. * This f u n c t i o n i s used to i n i t i a l i z e the s t a t e s t r u c t u r e * and constant outputs of the block. I t i s c a l l e d once * for each block instance during s i m u l a t i o n . * Function must always return e i t h e r SYS_OK, SYS_TERM, * or SYS_FATAL by using the return() f u n c t i o n . * User may modify the l i n e c o n t a i n i n g " r e t u r n ( S Y S _ 0 K ) . Appendix F. Source code of SOVA I n _ s o f t _ t c m _ p a t r i c k p l i b (spb_parm, s p b _ i n p u t , s p b _ o u t p u t , s p b _ s t a t e ) STRUCT P C _ s o f t _ t c m _ p a t r i c k p l i b *spb_parm; STRUCT I t _ s o f t _ t c m _ p a t r i c k p l i b * s p b _ i n p u t ; STRUCT O t _ s o f t _ t c m _ p a t r i c k p l i b * s p b _ o u t p u t ; STRUCT S t _ s o f t _ t c m _ p a t r i c k p l i b * s p b _ s t a t e , -{ " i n t g e t _ c o n s t _ n k l ( ) , g e t _ c _ t r e l _ t a g ( ) ; i n t t w o _ r a i s e d ( ) , i n i t _ v a r ( ) ; i n t i , check, l i n e _ n u m , - o u t s a m p _ r a t e ; c h a r filename[MAX_MESSAGE]; s t r u c t c _ s i g n a l _ m a g * d s i g p ; /* Check p a r a m e t e r s */ i f ( s u p _ c h k _ n o _ b l k _ e r r s ( P _ n o _ b l k _ e r r s , " d e c o d e r " , s p b _ s t a t e - > i n s t a n c e ) == SUP_INVALID_PARM) r e t u r n ( SYS_FATAL) ,-/* Check t h e a c t i o n t a k e n p a r a m e t e r */ i f ( s u p _ a c t i o n _ t a k e n ( P _ a f t e r _ e r r s , " d e c o d e r " , s p b _ s t a t e - > i n s t a n c e ) == SUP_INVALID_PARM) r e t u r n ( S Y S _ F A T A L ) ; i f ( P _ b a u d _ r a t e <= 0.0) { s u p _ i n i t _ e r r _ m s g ( " d e c o d e r " , s p b _ s t a t e - > i n s t a n c e ) ,-s l a n g f ( w m s g b u f , " Encoded b i t r a t e must be g r e a t e r t h a n 0 " ) ; wm s g E r r o r s ( w m s g b u f ) ; r e t u r n (SYS_FATAL); ) i f ( P _ s a m p _ f r e q <= 0.0) { s u p _ i n i t _ e r r _ m s g ("decoder", s p b _ s t a t e - > i n s t a n c e ) ,-s l a n g f ( w m s g b u f , " S a m p l i n g f r e q u e n c y must be g r e a t e r t h a n 0 " ) ; wm s g E r r o r s ( w m s g b u f ) ; r e t u r n (SYS_FATAL)-; ) i f ( P _ t p a t h _ l e n <= 0) { s u p _ i n i t _ e r r _ m s g ( " d e c o d e r " , s p b _ s t a t e - > i n s t a n c e ) ; s l a n g f ( w m s g b u f , " T r u n c a t i o n p a t h l e n g t h must be g r e a t e r t h a n 0 " ) ; wm s g E r r o r s ( w m s g b u f ) ; r e t u r n (SYS_FATAL); } i f ( P _ t p a t h _ l e n > MAXPLEN) { s u p _ i n i t _ e r r _ m s g ( " d e c o d e r " , s p b _ s t a t e - > i n s t a n c e ) ; s l a n g f ( w m s g b u f , " T r u n c a t i o n p a t h l e n g t h must be l e s s t h a n % d . " , MAXPLEN) wm s g E r r o r s ( w m s g b u f ) ; r e t u r n (SYS_FATAL); } /* C o n s t r u c t t h e f i l e name */ / * / * V Check t h e v a l u e of t h e n o _ b l k _ e r r s / * s t r c p y ( f i l e n a m e , "/spwdata/" ) ; s t r c a t ( f i l e n a m e + s i z e o f ( " / s p w d a t a / " ) - 1 , P _ t c m _ f i l e ) ; /* Get n , k , l from t h e TCM i n p u t f i l e */ s u p _ b l k _ b u i l d _ p a t h ( f i l e n a m e , N U L L , NULL, P _ t c m _ f i l e , SUP_NON_STANDARD); l i n e _ n u m = 1; i f ( ( c h e c k = g e t _ c o n s t _ n k l ( & ( S _ n ) , & ( S _ k ) , & ( S _ l ) , f i l e n a m e ) ) != 0) s u p _ i n i t _ e r r _ m s g ("decoder-s w i t c h (check) ( c a s e ERR_OPENFILE: s p b _ s t a t e - > i n s t a n c e ) ; Appendix F. Source code of SOVA 84 s l a n g f ( w m s g b u f , " C o u l d n o t r e a d Tern i n p u t f i l e % s " , f i l e n a m e ) ; b r e a k ; c a s e ERR_MAXN: s l a n g f (wmsgbuf, " N. must' be l e s s t h a n % d " , MAXN); b r e a k ; c a s e ERR_MAXK: s l a n g f ( w m s g b u f , " K must be l e s s t h a n % d " , MAXK); b r e a k ; c a s e ERR_MAXL: s l a n g f ( w m s g b u f , " L must be l e s s t h a n %d", MAXL); break,-c a s e ERR_EOF: s l a n g f ( w m s g b u f , " M i s s i n g p a r a m e t e r s i n l i n e %d o f t h e Tcm i n p u t f i l e . " , l i n e _ n u m ) ; b r e a k ; c a s e ERR_EXTRA: s l a n g f ( w m s g b u f , " E x t r a p a r a m e t e r s i n l i n e %d o f t h e Tcm i n p u t f i l e . " , l i n e _ n u m ) ; break,-c a s e ERR_M1SSING: s l a n g f ( w m s g b u f , " M i s s i n g p a r a m e t e r s i n l i n e %d o f . t h e Tcm i n p u t f i l e . " , l i n e _ n u m ) ,-b r e a k ; c a s e ERR_NZN: s l a n g f ( w m s g b u f , " N must be g r e a t e r t h a n 0 " ) ; b r e a k ; c a s e ERR_NZK: s l a n g f ( w m s g b u f , " K must be g r e a t e r t h a n 0 " ) ; b r e a k ; c a s e ERR_NZL: s l a n g f ( w m s g b u f , " L must be g r e a t e r t h a n 0 " ) ; b r e a k ; ) /* end s w i t c h */ w m s g E r r o r s ( w m s g b u f ) ; r e t u r n ( S Y S _ F A T A L ) ; } /* Check k from t h e T c m _ f i l e w i t h t h e one from t h e p a r a m e t e r s c r e e n */ . i f ( S _ k != O _ o u t _ i o v e c _ l e n ) { s u p _ i n i t _ e r r _ m s g ( " d e c o d e r " , s p b _ s t a t e - > i n s t a n c e ) ; s l a n g f ( w m s g b u f , " The v e c t o r l e n g t h i n t h e p a r a m e t e r s c r e e n s h o u l d be e q u a l t o K i n t h e Tcm f i l e . " ) ,-wmsgErrors(wmsgbuf) ; r e t u r n (S Y S _ F A T A L ) ; } ' i f H S_k + S _ l ) > WARNING_KL) { i f ( ( S _ k + S _ l ) > MAXKL) { s u p _ i n i t _ e r r _ m s g ( " d e c o d e r " , s p b _ s t a t e - > i n s t a n c e ) ; s l a n g f ( w m s g b u f , " k+1 must be l e s s t h a n % d . " , MAXKL); wm s g E r r o r s ( w m s g b u f ) ; r e t u r n (SYS_FATAL); } e l s e { s u p _ i n i t _ w a r n _ m s g ("decoder", s p b _ s t a t e - > i n s t a n c e ) ,-s l a n g f ( w m s g b u f , " WARNING: k+1 i s g r e a t e r t h a n % d . " , WAKNING_KL); wmsgErrors (wmsgbuf ) ,-•} /* p u t o u t a w a r n i n g b u t c o n t i n u e */ } /* C a l c u l a t e n s t a t e and n i n V S _ n s t a t e = t w o _ r a i s e d ( S _ l ) ; Appendix F. Source code of SOVA 85 S _ n i n = t w o _ r a i s e d ( S _ k ) ; S _ n s i g = t w o _ r a i s e d ( S _ n ) ; /* Check s a m p l i n g r a t e , o u t p u t s a m p l e s / b i t must be an i n t e g e r */ o u t s a m p _ r a t e = ( P _ s a m p _ f r e q / P _ b a u d _ r a t e ) + 0.5; i f ( ( ( P _ b a u d _ r a t e * o u t s a m p _ r a t e ) != P_samp_freq) II ( o u t s a m p _ r a t e < 1 ) ) ( s u p _ i n i t _ e r r _ m s g ( " d e c o d e r " , s p b _ s t a t e - > i n s t a n c e ) ; s l a n g f ( w m s g b u f , " Samples p e r symbol ( i . e . samp, f r e q . / baud r a t e ) s h o u l d be an i n -t e g e r . " ) ,-w m s g E r r o r s ( w m s g b u f ) ; r e t u r n (SYS_FATAL); } • . • . /* A l l o c a t e s p a c e s */ i f ( ( s p b _ s t a t e - > v p = ( i n t *) c a l l o c ( ( u n s i g n e d ) ( S _ k ) , s i z e o f ( i n t ) ) ) == NULL) g o t o ERRORM; i f ( ( s p b _ s t a t e - > d i s t _ p = ( d o u b l e *) c a l l o c ( ( u n s i g n e d ) ( S _ n s i g ) , s i z e o f ( d o u b l e ) ) ) == NULL) g o t o ERRORM; i f ( ( s p b _ s t a t e - > f r o m _ s t a t e p = ( s t r u c t s u r v i v e _ i n f o *) c a l l o c ( ( u n s i g n e d ) ( S _ n s t a t e ) , s i z e o f ( s t r u c t s u r v i v e _ i n f o ) ) ) == NULL) g o t o ERRORM; i f ( ( s p b _ s t a t e - > t o _ s t a t e p = ( s t r u c t t e m p _ i n f o *) c a l l o c ( ( u n s i g n e d ) ( S _ n s t a t e ) , s i z e o f ( s t r u c t t e m p _ i n f o ) ) ) == NULL) g o t o ERRORM; i f ( ( s p b _ s t a t e - > t r e l - l _ t a b l e p = ( s t r u c t c o n s t _ t r e l l _ t a g *) c a l l o c ( ( u n s i g n e d ) ( S _ n s t a t e * S_nin) , s i z e o f ( s t r u c t c o n s t _ t r e l l _ t a g ) ) ) == NULL) { sup_memerr_msg("decoder", s p b _ s t a t e - > i n s t a n c e ) ; r e t u r n ( S Y S _ F A T A L ) ; } i f ( ( s p b _ s t a t e - > s i g _ t a b l e p _ m a g = ( d o u b l e *) c a l l o c ( ( u n s i g n e d ) ( S _ n s i g ) , s i z e o f ( d o u b l e ) ) ) == NULL) { sup_memerr_msg("decoder", s p b _ s t a t e - > i n s t a n c e ) ; r e t u r n ( S Y S _ F A T A L ) ; } _ ' i f ( ( s p b _ s t a t e - > s i g _ t a b l e p _ r e = ( d o u b l e *) c a l l o c ! ( u n s i g n e d ) ( S _ n s i g ) , s i z e o f ( d o u b l e ) ) ) == NULL) { sup_memerr_msg("decoder", s p b _ s t a t e - > i n s t a n c e ) ; r e t u r n ( S Y S _ F A T A L ) ; } • i f ( ( s p b _ s t a t e - > s i g _ t a b l e p _ i m = ( d o u b l e *) c a l l o c ( ( u n s i g n e d ) ( S _ n s i g ) , s i z e o f ( d o u b l e ) ) ) == NULL) { sup_memerr_msg("decoder", s p b _ s t a t e - > i n s t a n c e ) ; r e t u r n ( S Y S _ F A T A L ) ; } /* Get i m p u l s e r e s p o n s e p a r a m e t e r from TCM i n p u t f i l e */ i f ( ( c h e c k = g e t _ c _ t r e l _ t a g ( f i l e n a m e , s p b _ s t a t e - > t r e l l _ t a b ' l e p , s p b _ s t a t e -> s i g _ t a b l e p _ m a g , s p b _ s t a t e - > s i g _ t a b l e p _ r e , s p b _ s t a t e - > s i g _ t a b l e p _ i m , & s p b _ s t a t e - > n s i g , & s p b _ s t a t e - > n , & s p b _ s t a t e - > k , & s p b _ s t a t e - > l , & l i n e _ n u m ) ) != 0) { i f ( check == WARN_FEWSIGNAL) { s u p _ i n i t _ w a r n _ m s g ( " d e c o d e r " , s p b _ s t a t e - > i n s t a n c e ) ; s l a n g f ( w m s g b u f , " WARNING: Number o f d i s t i n c t s i g n a l s i s l e s s t h a n % d " , t w o _ r a i s e d ( S _ n ) ) ; wmsgErrors(wmsgbuf) ; } e l s e ( s u p _ i n i t _ e r r _ m s g ( " d e c o d e r " , s p b _ s t a t e - > i n s t a n c e ) ,-s w i t c h (check) { c a s e ERR_OPENFILE: s l a n g f ( w m s g b u f , " C o u l d n o t r e a d Tcm i n p u t f i l e % s " , f i l e n a m e ) ; b r e a k ; c a s e ERR_MAXN: Appendix F. Source code of SOVA 86 s l a n g f ( w m s g b u f , " N must be l e s s t h a n %d", MAXN); . b r e a k ; c a s e ERR_MAXK: s l a n g f ( w m s g b u f , * K must be l e s s t h a n - % d " , MAXK); b r e a k ; c a s e ERR_MAXL: s l a n g f ( w m s g b u f , " L must be l e s s t h a n %d", MAXL); b r e a k ; • c a s e ERR_EOF: • / s l a n g f I w m s g b u f , " M i s s i n g p a r a m e t e r s i n l i n e %d o f t h e Tem i n p u t f i l e . " , l i n e _ n u m ) ; b r e a k ; c a s e ERR_EXTRA: s l a n g f (wmsgbuf, " E x t r a p a r a m e t e r s i n l i n e %d o f t h e Tem i n p u t f i l e . " , " l i n e _ n u m ) ; b r e a k ,-c a s e ERR_MAXSTATE: s l a n g f ( w m s g b u f , " S t a t e e x c e e d s %d i n l i n e %d of t h e Tem i n p u t f i l e . " , S _ n s t a t e , l i n e _ n u m ) ; ' b r e a k ; case' ERR_MAX IN PUT: s l a n g f ( w m s g b u f , " I n p u t e x c e e d s %d i n l i n e %d o f t h e Tem i n p u t f i l e . " , S _ n i n , l i n e _ n u m ) ,-b r e a k ; c a s e ERR_MAXSIG: s l a n g f (wmsgbuf, " Number o f d i s t i n c t s i g n a l s e x c e e d s %d''in l i n e %d o f t h e Tem i n -p u t f i l e . " , f i l e . " , l i n e _ n u m j ; t w o _ r a i s e d ( S_n) , l i n e _ n u m ) ,-b r e a k ; c a s e ERR_INCOMPLETE: s l a n g f ( w m s g b u f , " Next s t a t e o f s t a t e %d and i n p u t %d m i s s i n g i n t h e Tem i n p u t l i n e _ n u m / S _ n i n , l i n e _ n u m % S _ n i n ) ; b r e a k ; c a s e ERR_MISSING: s l a n g f ( w m s g b u f , " M i s s i n g p a r a m e t e r s i n l i n e %d o f t h e Tem i n p u t f i l e . " , b r e a k ; c a s e ERR_NZN: s l a n g f ( w m s g b u f , " N must be g r e a t e r t h a n 0 " ) ; b r e a k ; c a s e ERR_N2K: s l a n g f ( w m s g b u f , " K must be g r e a t e r t h a n 0 " ) ; b r e a k ; c a s e ERR_NZL: s l a n g f (wmsgbuf, " L must be g r e a t e r t h a n 0"),-b r e a k ; c a s e ERR_NSI: s l a n g f ( w m s g b u f , " S t a t e o r i n p u t i s l e s s t h a n z e r o i n l i n e %d of t h e Tem i n p u t f i l e . " , l i n e _ n u m ) ; b r e a k ; } /* end s w i t c h */ wmsgErrors(wmsgbuf) ; r e t u r n (SYS_FATAL); ) /* end i f n o t w a r n _ f e w s i g n a l */ } /* end i f e r r o r */ /* P r e - p r o c e s s t h e s i g n a l t a b l e */ s p b _ s t a t e - > a v g _ p o w e r = 0 . 0 ; d s i g p = s p b _ s t a t e - > s i g _ t a b l e p ; V Appendix F. Source code of SOVA 87 f o r ( i = 0 ; i < S _ n s i g ; i++) { s p b _ s t a t e - > s i g _ t a b l e p _ m a g [ i ] = ( s p b _ s t a t e - > s i g _ t a b l e p _ r e [ i ] * s p b _ s t a t e -> s i g _ t a b l e p _ r e [ i ] ) + ( s p b _ s t a t e - > s i g _ c a b l e p _ i m [ i ] * s p b _ s c a t e - > s i g _ c a b l e p _ i m [ i ] ) ,-spb_scace->avg_power += s p b _ s t a t e - > s i g _ t a b l e p _ m a g [ i ] ; s p b _ s t a t e - > s i g _ t a b l e p _ r e ( i ] *= 2 . 0 ; s p b _ s c a t e - > s i g _ t a b l e p _ i m [ i ] *= 2 . 0 ; } /* C a l c u l a t e a v e r a g e power of t h e c o n s t e l l a t i o n */ sp b _ s t a t e - > a v g _ p o w e r /= ( d o u b l e ) S _ n s i g ; /* I n i t i a l i z e v a r i a b l e s */ i n i t _ v a r ( s p b _ s t a t e , spb_parm, s p b _ o u t p u t ) ; r e t u r n (SYS_OK!; ERRORM: • sup_memerr_msg("decoder" , s p b _ s t a t e - > i n s t a n c e ) ; r e t u r n ( S Y S _ F A T A L ) ; } Run Output F u n c t i o n (must be p r e s e n t ) --> I f e d i t i n g , m o d i f y o n l y t h e l i n e s w i t h i n t h e f u n c t i o n ' s o p e n i n g and c l o s i n g b r a c k e t s . ' T h i s f u n c t i o n i s u s e d t o u p d a t e t h e o u t p u t s a n d /or s t a t e o f t h e b l o c k . I t i s c a l l e d each i t e r a t i o n , f o r each b l o c k i n s t a n c e d u r i n g s i m u l a t i o n . F u n c t i o n must a l w a y s r e t u r n e i t h e r SYS_OK, SYS_TERM, o r SYS_FATAL by u s i n g t h e r e t u r n ! ) f u n c t i o n . U s e r may m o d i f y t h e l i n e c o n t a i n i n g " r e t u r n ( S Y S _ O K ) ; " R o _ s o f t _ t c m _ p a t r i c k p l i b (spb_parm, s p b _ i n p u t , s p b _ o u t p u t , s p b _ s t a t e ) STRUCT P t _ s o f t _ t c m _ p a t r i c k p l i b *spb_parm; STRUCT I t _ s o f t _ t c m _ p a t r i c k p l i b * s p b _ i n p u t ; STRUCT O t _ s o f t _ t c m _ p a t r i c k p l i b * s p b _ o u t p u t ; STRUCT S t _ s o f t _ t c m _ p a t r i c k p l i b * s p b _ s t a t e , -{ /* Decodes u s i n g t h e v i t e r b i a l g o r i t h m . */ /* C l o c k i n i s r e q u i r e d by t h i s f u n c t i o n . */ /* Any i n c o m i n g samples n o t a c c o m p a n i e d by */ /* c l o c k i n i s d i s r e g a r d e d . */ i n t b i n _ t o _ i n t ( ) , i n t _ t o _ b i n ( ) , c a l c _ m e t r i c ( ) ; s t r u c t c _ s i g n a l i n p u t _ s i g ; s t r u c t c o n s t _ t r e l l _ t a g * d t r _ p ; s t r u c t s u r v i v e _ i n f o *dfrom_p, *dftem_p, *So_dftem_p; s t r u c t t e m p _ i n f o * d t o _ p ; i n t i , s, i n ; i n t tem, v _ i n t , s u r _ s t a t e ; i n t *dv_p; d o u b l e s u r ^ m e t r i c , p s k ; /* R e t u r n i f h o l d */ i f ( I _ h o l d > 0 . 0 ) r e t u r n (SYS_OK); Appendix F. Source code of SOVA 88 /* T h i s w i l l be s e t t o TRUE , u n d e r . t h e r i g h t c o n d i t i o n , b e l o w */ O _ c l o c k _ o u t = FALSE; /* Check i f v a l i d sample */ i f ( ( I _ c l o c k _ i n ) == TRUE) { /* Check i f a l p h a > 0.0 */ i f ( I _ a l p h a <= 0.0) { s u p _ r u n _ e r r _ m s g ( " d e c o d e r " , s p b _ s t a t e - > i n s t a n c e ) ; s l a n g f ( w m s g b u f , " E s t _ p o w e r i n p u t must be g r e a t e r t h a n z e r o . " ) ; w m s g E r r o r s ( w m s g b u f ) ; r e t u r n (SYS_FATAL); /* c a l c u l a t e s t h e d i s t a n c e o f each s i g n a l p o i n t s t o t h e r e c e i v e d s i g n a l */ i n p u t _ s i g . c _ r e a l = l _ i n [ 0 ] ; i n p u t _ s i g . c _ i m a g = I _ i n [ l ] ; c a l c _ d i s t a n c e ( S _ n s i g , s p b _ s t a t e - > s i g _ t a b l e p _ m a g , s p b _ s t a t e - > s i g _ t a b l e p _ r e , s p b _ s t a t e -> s i g _ t a b l e p _ i m , s p b _ s t a t e - > d i s t _ p , i n p u t _ s i g , I _ a l p h a ) ; /* i n i t i a l i z e t o _ s t a t e a r r a y */ d t o _ p = s p b _ s t a t e - > t o _ s t a t e p ; f o r ( i = 0 ; i < ( S _ n s t a t e ) ; i++) { d t o _ p - > t e m p _ m e t r i c = l : 0 e 3 8 ; /* t h e l a r g e s t v a l u e */ d t o _ p - > S o _ t e m p _ m e t r i c = 1.0e38; /* t h e s e c o n d b e s t v a l u e */ d t o _ p - > w o r s t _ m e t r i c = 0 . 0 ; /* t h e w o r s t v a l u e */ dto_p++; ) /* C a l c u l a t e m e t r i c s f o r a l l b r a n c h e s */ d t r _ p = s p b _ s t a t e - > t r e l l _ t a b l e p ; /* p o i n t t o t r e l l _ t a b l e p t s = 0 j [ i n = 0 ] */ dfrom_p = s p b _ s t a t e - > f r o m _ s t a t e p ; /* p o i n t s t o f r o m _ s t a t e [ s = 0 ] */ f o r (s = 0; s' < S _ n s t a t e ; s + +) ( f o r ( i n = 0 ; i n < S _ n i n ; in++) { /* c a l c u l a t e m e t r i c f o r t h i s p a r t i c u l a r b r a n c h */ s u r _ m e t r i c = * ( s p b _ s t a t e - > d i s t _ p + d t r _ p - > t a g ) ; •/* l o o k up d i s t a n c e ' f o r t h i s b r a n c h o r t a g */ s u r _ m e t r i c += d f r o m _ p - > m e t r i c ; /* P o i n t s t o t o _ s t a t e [ n e x t _ s t a t e ] t o g e t s m a l l e s t m e t r i c so f a r */ d t o _ p = s p b _ s t a t e - > t o _ s t a t e p + ( d t r _ p - > n e x t _ s t a t e ) ; /* Check i f t h i s b r a n c h i s a s u r v i v o r */ i f ( s u r _ m e t r i c < d t o _ p - > t e m p _ m e t r i c ) { / • U p d a t e b e s t m e t r i c i n f o i n t o _ s t a t e */ d t o _ p - > S c _ f r o m _ s t a t e = d t o _ p - > f r o m _ s t a t e ; d t o _ p - > f r o m _ s t a t e = s; dto_p->'So_branch = d t o _ p - > b r a n c h ; d t o _ p - > b r a n c h = i n ; d t o _ p - > S o _ t e m p _ m e t r i c = d t o _ p - > t e m p _ m e t r i c ; d t o _ p - > t e m p _ m e t r i c = s u r _ m e t r i c ; } e l s e i f ( s u r _ m e t r i c < d t o _ p - > S o _ t e m p _ m e t r i c ) { /* Update s e c o n d b e s t m e t r i c i n f o i n t o _ s t a t e */ d t o _ p - > S o _ f r o m _ s t a t e = s; d t o _p->So_branch = i n ; d t o _ p - > S o _ t e m p _ m e t r i c = s u r _ m e t r i c ; } e l s e i f ( s u r _ m e t r i c > d t o _ p - > w o r s t _ m e t r i c ) { d t o _ p - > w o r s t _ m e t r i c = s u r _ m e t r i c ; ) ' dtr_p++; /* p o i n t t o t r e l l _ t a b l e p [ s ] [ i n ] */ Appendix F. Source code of SOVA 89 } dfrom_p++; /* points to from_state[s] */ } /* Find smallest metric among the states */ dto_p = spb_state->to_statep; /* point to to_state[0] */ sur_metric = 1.0e3 8; /* set to maximum */ sur_state = 0; for (s=0; s < S_nstate; s++) { i f (dto_p->temp_metric < sur_metric) { sur_metric = dto_p->temp_metric; sur_state = s; } dto_p++; /* point to dto_p[s+l) */ ) /* Update num_current and num_previous */ /* This determines which path i n the from_state s t r u c t u r e i s current now */ tem = S_num_current; S_num_current = S_num_previous; S_num_previous = tem; /* Update from_state array i n f o and normalize the metrics */ dto_p = spb_state->to_statep,- /* point to to_state[0] */ dfrom_p = spb_state->from_statep; /* point to from_state[0] */ for (s=0; s < S_nstate; S++) { I*- make dftem_p point to the state where l a t e s t survivor branch came from */ dftem_p = spb_state->from_statep + dto_p->from_state; So_dftem_p = spb_state->from_statep + dto_p->So_from_state; /* update from_state */ dfrom_p->metric = dto_p->temp_metric - sur_metric; dfrom_p->So_metric = dto_p->So_temp_metric - sur_metric; psk• = dto_p->So_temp_metric - dto_p->temp_metric; psk = 1.0/psk; /* copy survivor path from dftem_p to dfrom_p */ for (i=0; i<(P_tpath_len + 1); i++) { dfrom_p->path[S_num_current][i] = dftem_p->path|S_num_previous][i]; dfrom_p->So_path|S_num_current][i] = So_dftem_p->path[S_num_previous)[i]; i f ( (df rom_p->path [ S_num_current ] [ i ] == df rom_p->So_path ( S_num_current ] [ i ] ) II (dftem_p->erase(S_num_previous] [i] >- psk)) ( df rom_p->erase [ S_num_current ] [ i j = df tem_p->erase [ S_num_previous ] [ i ] ,-} e l s e { dfrom_p->erase[S_num_current][i] = psk; } } ' . /* appends branch to survivor path */ dfrom_p->pathIS_num_current][S_path_index] = dto_p->branch; dfrom_p->So_path[S_num_current][S_path_index] = dto_p->So_branch; dfrom_p->erase[S_num_current][S j>ath_index) = psk; dto_p++; /* points to to_state(s+1] */ dfrom_p++; /* points to from_state(s+1] */ } S_path_index++; /* Note that path[] i s a "wrap around b u f f e r */ S_path_index = S_path_index % (P_tpath_len + 1); /* path_index now points to the branch to be placed'at the output b u f f e r */ /* Place the e a r l i e s t branch of the survivor with the largest metric i n the */ /* output b u f f e r . The e a r l i e s t branch i s pathlen behind the current. */ dfrom_p = spb_state->from_statep + sur_state; /* point to stat e with largest metric */ v _ i n t = dfrom_p->path[S_num_current][S_path_index]; psk = dfrom_p->erase[S_num_current][S_path_index]; Appendix F. Source code of SOVA i n t _ t o _ b i n ( S _ k , v _ i n t , spb_state->vp); /* v(] now contains the branch to be output */ /* note that the f i r s t pathlen number of output w i l l be '0' during s t a r t u p * / /* Update clock_out and prepare outputs */ i f (spb_state->on) 0_clock_out = TRUE; e l s e { . spb_state->cntr++; dv_p = spb_state->vp; for (i=0; i<S_k; i++) *dv_p++ = 0.0; /* I t can be set to any value */ i f (spb_state->cntr == P_tpath_len) spb_state->on = TRUE; /" i f "turned on", output w i l l be v a l i d s t a r t i n g at the next symbol */ } ) /* end of c l o c k i n */ dv_p = spb_state->vp; for ( i = 0; i<S_k; i + +) (-O_out[i] = *dv_p++); 0_erasure = psk; retu r n (SYS_0K); } V Termination Function (must be present) --> I f e d i t i n g , modify only the l i n e s w i t h i n the function's opening and c l o s i n g brackets. This f u n c t i o n i s used to dump the f i n a l s t a t e of the block. I t i s c a l l e d once for each block instance during the s i m u l a t i o n . Function must always r e t u r n e i t h e r SYS_OK, SYS_TERM, or SYS_FATAL by using the r e t u r n f ) f u n c t i o n . User may modify the l i n e c ontaining "return(SYS_OK);". T e _ s o f t _ t c m _ p a t r i c k p l i b (spb_parm, spb_input, spb_output, spb_state) STRUCT P t _ s o f t _ t c m _ p a t r i c k p l i b *spb_parm;' STRUCT I t _ s o f t _ t c m _ p a t r i c k p l i b *spb_input; STRUCT O t _ s o f t _ t c m _ p a t r i c k p l i b *spb_output; STRUCT S t _ s o f t _ t c m _ p a t r i c k p l i b *spb_state; free(spb_state->yp); f r e e ( s p b _ s t a t e - > d i s t _ p ) ; free(spb_state->sig_tablep_mag); free ( spb_state->sig_tablep_re) ;' free(spb_state->sig_tablep_im); f r e e ( s p b _ s t a t e - > t r e l l _ t a b l e p ) ; free(spb_state->from_statep); fr e e ( s p b _ s t a t e - > t o _ s t a t e p ) ; r e t u r n (SYS_0K); ^ * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * « * * * * * * * * * * * * * * * * * * * * * * * * * / / * . • V /* Add any a d d i t i o n a l functions you need here. */ Appendix F. Source code of SOVA 91 s t a t i c i n i t _ v a r ( u s e r p , paramp, o u t p u t p ) STRUCT S t _ s o f t _ t c m _ p a t r i c k p l i b * u s e r p ; STRUCT P t _ s o f t _ t c m _ p a t r i c k p l i b *paramp; STRUCT O t _ s o f t _ t c m _ p a t r i c k p l i b * o u t p u t p ; { . ' i n t i , i i ; i n t *dvp; s t r u c t s u r v i v e _ i n f o *dfrom_p; s t r u c t t e m p _ i n f o * d t o _ p ; o u t p u t p - > c l o c k _ o u t = FALSE;' /* I n i t i a l i z e o u t p u t t o 0.0 */ f o r ( i = 0 ; i < u s e r p - > k ; i++) ( o u t p u t p - > o u t [ I ] = 0.0); u s e r p - > c n t r = 0; userp->on = FALSE; u s e r p - > n u m _ p r e v i o u s = 0; u s e r p - > n u m _ c u r r e n t = 1; u s e r p - > p a t h _ i n d e x = 0; /* I n i t f r o m _ s t a t e and t o _ s t a t e a r r a y */ dfrom_p = u s e r p - > f r o m _ s t a t e p ; d t o _ p = u s e r p - > t o _ s t a t e p ; f o r ( i = 0 ; i < u s e r p - > n s t a t e ; i++) { f o r ( i i = 0 ; i i < ( p a r a m p - > t p a t h _ l e n + 1 ) ; i i + +) { d f r o m _ p - > p a t h [ 0 ] [ i i ] = 0; d f r o m _ p - > p a t h [ 1 ] [ i i ] = 0; d f r o m _ p - > S o _ p a t h ! 0 ] [ i i ] = 0 ; • ' dfrom_p->So_path|1J | i i ) = 0; d f r o m _ p - > e r a s e ( 0 ) ( i i ] = 0.0; d f r o m _ p - > e r a s e [ 1 ] [ i i ] = 0.0; ) d f r o m _ p - > m e t r i c = 0 . 0 ; d f r o m _ p - > S o _ m e t r i c = 0 . 0 ; d t o _ p - > f r o m _ s t a t e = 0; d t o _ p - > b r a n c h = 0; d t o _ p - > t e m p _ m e t r i c = 1.0e38; d t o _ p - > S o _ f r o m _ s t a t e = 0; d t o _ p - > S o _ b r a n c h = 0; d t o _ p - > S o _ t e r a p _ m e t r i c = 1.0e38; dfrom_p++; dto_p++; } /* I n i t v [ ] */ dvp = userp->vp; f o r ( i = 0; i<userp->k; i + +) *dvji++ = 0; r e t u r n (0) ; } s t a t i c g e t _ c o n s t _ n k l (n_jD, k_p, l_p, f i l e _ j 3 ) /* Read n_p, k_p, and l _ p a r e r e a d from t h e f i r s t l i n e o f f i l e _ p */ /* A p p r o p r i a t e e r r o r messages a r e r e t u r n . g */ /* ' V i n t *n_p, *k_p, * l _ p ; c h a r * f i l e _ p ; { F I L E * f o p e n ( ) , * f p ; i n t r e a d _ l i n e ( ) ; ' Appendix F. Source code of SOVA 92 i n t a t o i ( ) , c o u n t , c h e c k ; c h a r line[MAXVALUE_LEN+1]; i f ( ( f p = f o p e n ( f i l e _ p , NULL r e t u r n ( E R R _ O P E N F I L E ) ; /* r e a d i n f i r s t l i n e /* n,k, 1 i f ( r e a d _ l i n e ( f p , *n_p = a t o i ( l i n e ) i f (*n_p > MAXN) MAXVALUE_LEN, S c o u n t , l i n e ) 0) r e t u r n (ERR_MISSING) return(ERR_MAXN); i f l ' n _ p <= 0) r e t u r n ( E R R _ N Z N ) ; • i f ( r e a d _ l i n e ( f p , MAXVALUE_LEN, i c o u n t , l i n e ) *k_p = a t o i ( l i n e ) ; i f (*k_p > MAXK) r e t u r n (ERR_MAXK); i f (*k_p <= 0) r e t u r n (ERR_NZK); check = r e a d _ l i n e ( f p , MAXVALUE_LEN, i c o u n t , l i n e ) ; i f ( c o u n t == 0) r e t u r n ( E R R _ M I S S I N G ) ; /* r e a d n o t h i n g * i f ((check = = 0) II (check = = D) { * l _ p = a t o i ( l i n e ) ; /* i f w h i t e s p a c e o r c r l f */ i f ( * l _ p > MAXL) r e t u r n (ERR_MAXL); i f ( * l _ p <= 0) r e t u r n (ERR_NZL); } e l s e r e t u r n ( E R R _ E O F ) ; /* EOF e n c o u n t e r e d */ i f (check==0) { i f ( ( r e a d _ l i n e ( f p , MAXVALUE_LEN, Scount, l i n e ) != 1) r e t u r n IERR_EXTRA); /* c r l f e x p e c t e d */ 0) r e t u r n (ERR_MISSING) ,-/ I I (count!=0)) f c l o s e ( f p ) ; r e t u r n ( 0 ) ; s t a t i c g e t _ c _ t r e l _ t a g ( f i l e _ p , t a b l e _ p , s i g n a l _ p _ m a g , s i g n a l _ p _ r e , s i g n a l _ p _ i m , c o u n t _ s i g p , n_p, k_p, l _ p , l i n e _ e r p ) /* Reads i n t h e t r e l l i s d i a g r a m f r o m f i l e _ p , and p l a c e i t i n t a b l e _ p . I t a l s o s o r t s o u t t h e d i s t i n c t s i g n a l s and p l a c e them i n s i g n a l _ p . n_p, k_p, and l _ p a r e r e a d from t h e f i r s t l i n e o f f i l e _ p . I t a l s o a s s i g n s o r t a g s t h e s i g n a l s w i t h an i n t e g e r f o r e a s i e r and f a s t e r a c c e s s . The i t h s i g n a l i n t h e s i g n a l _ p t a b l e i s a s s i g n e d t h e t a g " i " . The c o r r e s p o n d i n g s i g n a l i n t h e t r e l l i s t a b l e w i l l be g i v e n t h i s t a g . /* /* /* /* /* /* /* /* /* /* /* /* /* /* /* /* /* /* /* /* /« /* i n t * c o u n t _ s i g p c h a r * f i l e _ p ; d o u b l e * s i g n a l _ p _ m a g , * s i g n a l _ p _ r e , s t r u c t c o n s t _ t r e l l _ t a g * t a b l e _ p ; S t a t e s r e a d from t h e f i l e must n o t e x c e e d ( 2 * * ( * l _ p ) - 1) and i n p u t s must n o t e x c e e d ( 2 * * ( * k _ p ) - 1 ) . The number o f of d i s t i n c t s i g n a l s i s e x p e c t e d t o be l e s s t h a n o r e q u a l t o 2 * M * n _ p ) . A w a r n i n g i s r e t u r n i f i t s l e s s t h a n . F o r e v e r y c u r r e n t s t a t e i n t h e t r e l l i s , t h e n e x t s t a t e c o r r e s p o n d i n g t o a l l p o s s i b l e i n p u t s s h o u l d be s p e c i f i e d . O t h e r w i s e an e r r o r message (ERR_INCOMPLETE) i s r e t u r n . A p p r o p r i a t e e r r o r messages a r e r e t u r n w i t h t h e c o r r e s p o n d i n g l i n e number where i t o c c u r r e d ( i n l i n e _ e r p ) , i f a p p l i c a b l e . I f t h e e r r o r message i s ERR_INCOMPLETE, t h e f u n c t i o n p l a c e ' ( c u r r e n t s t a t e * ( 2 * * k ) ) + i n p u t i n l i n e _ e r p . V V V */ */ */ V V */ */ */ V */ */ V • V */ */ *./ V V */ */ •n_p, 'k_p, * l _ p , ' l i n e _ e r p ; * s i g n a l _ p _ i m ; Appendix F. Source code of SOVA 93 F I L E * f o p e n ( ) , * f p ; i n t r e a d _ l i n e ( ) , t w o _ r a i s e d ( ) ; i n t a t o i l ) , c o u n t , check, done, i , j ,-i n t n u m _ s t a t e , num_input, num_sig, e n t r y ; i n t c u r _ s t a t e , i n p u t , n e x t _ s t a t e ; d o u b l e a t o f ( ) , x , y ; c h a r 1ine[MAXVALUE_LEN+1]; s t r u c t c o n s t _ t r e l l _ t a g *dum_p; /* I f we c a n ' t open t h e g e n e r a t o r f i l e , do n o t h i n g , and r e t u r n s " 1 " */ i f ( ( f p = f o p e n t f i l e _ p , " r " ) ) == NULL ) r e t u r n ( E R R _ O P E N F I L E ) ; 0) r e t u r n (ERR_MISSING); /* r e a d i n f i r s t l i n e n , k , l */ /* V * l i n e _ e r p =• 1; i f ( r e a d _ l i n e ( f p , MAXVALUE_LEN, i c o u n t , l i n e ) *n_p = a t o i ( l i n e ) ; i f («n_p > MAXN) r e t u r n (ERR_MAXN) ; i f (*n_p <= 0) r e t u r n ( E R R _ N Z N ) ; i f ( r e a d _ l i n e ( f p , MAXVALUE_LEN, i c o u n t , l i n e ) != 0) return(ERR_MISSING) *k_p = a t o i ( l i n e ) ; i f ( *k_p > MAXK) r e t u r n {ERR_MAXK) ,-i f (*k_p <= 0) r e t u r n (ERR_NZK); check = r e a d _ l i n e ( f p , MAXVALUE_LEN, S c o u n t , l i n e ) ; i f ( c o u nt == 0) r e t u r n ( E R R _ M I S S I N G ) ; /* r e a d n o t h i n g */ i f ( ( c h e c k = = 0) II (check= = D ) { * l _ p = a t o i ( l i n e ) ; /* i f w h i t e space o r c r l f */ i f ! * l _ p > MAXL) r e t u r n (ERR_MAXL); i f ( * l _ p <= 0) r e t u r n (ERR_NZL); e l s e r e t u r n ( E R R _ E O F ) ; /* EOF e n c o u n t e r e d */ i f (check==0) { i f ( ( r e a d _ l i n e ( f p , MAXVALUE_LEN, &count, l i n e ) r e t u r n ( E R R _ E X T R A ) ; 7* c r l f e x p e c t e d */ != 1) I i ( c o u n t ! /* Read i n and i g n o r e a l i n e o f t e x t */ ( * l i n e _ e r p ) + + ; w h i l e ( ( ( c h e c k = f g e t c ( f p ) ) >.= '\n') && (check != EOF)) {;} i f (check == EOF) r e t u r n (ERR_EOF)'; /* u n e x p e c t e d e of d e t e c t e d */ num_sig = t w o _ r a i s e d ( * n _ p ) ; n u m _ s t a t e = t w o _ r a i s e d ( * l _ p ) ,-num_input = t w o _ r a i s e d ( * k _ p ) ; e n t r y = n u m _ s t a t e * num_input; ./* I n i t i a l i z e f o r c h e c k i n g p u r p o s e s l a t e r */ dum_p = t a b l e _ p ; f o r ( i = 0 ; i < e n t r y ; i++) { dum _ p - > n e x t _ s t a t e = - 1 ; dum_i3++ ; ) * c o u n t _ s i g p = 0 ; /* Read i n e x p e c t e d number o f l i n e s V f o r ( i = 0; i < e n t r y ; i + +) '{ ( * l i n e _ e r p ) + + ; i f ( ( c h e c k = r e a d _ e n t r y ( f p , & c u r _ s t a t e , & i n p u t , & n e x t _ s t a t e , & x , & y ) ) != 0) r e t u r n ( c h e c k ) ; i f ( c u r _ s t a t e > ( n u m _ s t a t e - l ) ) r e t u r n (ERR_MAXSTATE); i f ( c u r _ s t a t e < 0) r e t u r n (ERR_NSI); Appendix F. Source code of SOVA 94 i f ( n e x t _ s t a t e > ( n u m _ s t a t e - l ) ) ' r e t u r n (ERR_MAXSTATE); i f ( n e x t _ s t a t e < 0) r e t u r n (ERR_NSI); i f ( i n p u t > ( n u m _ i n p u t - l ) ) r e t u r n (ERR_MAXINPUT); i f ( i n p u t < 0) r e t u r n (ERR_NSI); /* c o u n t number and s t o r e d i s t i n c t s i g n a l p o i n t s */ f o r ( j = 0 ; j < * c o u n t _ s i g p ; j++) { i f ( (x == s i g n a l _ p _ r e ( j ] ) &S, (y == s i g n a l _ p _ i m [ j ] ) ) b r e a k ; } /* e r r o r i f t h e r e a r e more s i g n a l p o i n t s t h a n e x p e c t e d */ i f ( ( j == * c o u n t _ s i g p ) && • ( * c o u n t _ s i g p == num_sig)) r e t u r n (ERR_MAXSIG) ,-i f ( j == * c o u n t _ s i g p ) ( s i g n a l _ p _ r e ( * c o u n t _ s i g p ] = x; s i g n a l _ p _ i m [ * c o u n t _ s i g p ] = y; (*c o u n t _ s i g p ) + + ; ) dum_p = t a b l e _ p + ( c u r _ s t a t e * num_input) + i n p u t ; d u m _ p - > n e x t _ s t a t e = n e x t _ s t a t e ; dum_p->c_rea1 = x; dum_p->c_imag = y; } /* r e a d i n e x c e s s c h a r a c t e r ; e x p e c t c r l f and EOF o n l y V done = FALSE; . • w h i l e (!done) { ( * l i n e _ e r p ) + + ; check = r e a d _ l i n e (fp,- MAXVALUE_LEN, &count, l i n e ) ; i f ( c o u n t !=0) r e t u r n (ERR_EXTRA); i f "(check == 2) done = TRUE; /* EOF e n c o u n t e r e d ; done */ /* o t h e r w i s e c r l f e n c o u n t e r e d , c o n t i n u e */ ) /* c h e c k t h e t a b l e */ dum_p = table_p,-/* check i f i t has t h e c o r r e c t number o f e n t r i e s */ f o r ( i = 0 ; i < e n t r y ; i++) { * l i n e _ e r p = i ; i f ( d u m _ p - > n e x t _ s t a t e == -1) return(ERR_INCOMPLETE); dum_p +1- ; } • /* t a g t h e s i g n a l s i n t h e t r e l l i s t a b l e */ dum_p = t a b l e _ p ; f o r l i = 0 ; i < e n t r y ; i++) { f o r ( j = 0 ; j < * c o u n t _ s i g p ; j++) ( i f ( ( s i g n a l _ p _ r e ( j ] == dum_p->c_real) && ' ( s i g n a l _ p _ i m [ j ] == dum_j3->c_imag) ) dum_p->tag = j ; } dum__p + +; } /* r e t u r n w a r n i n g i f number o f d i s t i n c t s i g n a l i s l e s s t h a n 2**n */ i f ( * c o u n t _ s i g p < num_sig) { f c l o s e ( f p ) ; . r e t u r n (WARN_FEWSIGNAL) ; • } f c l o s e ( f p ) ; r e t u r n ( 0 ) ; /* r e t u r n "0" i f ok */ s t a t i c r e a d _ e n t r y ( f p , f r o m _ s t a t e p , i n p , t o _ s t a t e p , xp, yp) F I L E * f p ; Appendix F. Source code of SOVA i n t * f r o m _ s t a t e p , * i n p , * t o _ s t a t e p ; d o u b l e * x p , * y p ; { i n t r e a d _ l i n e ( ) ; d o u b l e a t o f ( ) ; i n t c o u n t , c h e c k ; c h a r l i n e [ M A X V A L U E _ L E N + 1 ] ; . i f ( r e a d _ l i n e ( f p , M A X V A L U E _ L E N , i c o u n t , l i n e ) != 0 ) r e t u r n ( E R R _ M I S S I N G ) * f r o m _ s t a t e p = a t o i ( l i n e ) ; i f ( r e a d _ l i n e ( f p , M A X V A L U E _ L E N , i c o u n t , l i n e ) 1= 0 ) r e t u r n ( E R R _ M I S S I N G ) * i n p = a t o i ( l i n e ) ; i f ( r e a d _ l i n e ( f p , ' M A X V A L U E _ L E N , i c o u n t , l i n e ) != 0 ) r e t u r n ( E R R _ M I S S I N G ) * t o _ s t a t e p = a t o i 1 l i n e ) , -i f ( r e a d _ l i n e ( f p , M A X V A L U E _ L E N , i c o u n t , l i n e ) ! = 0 ) r e t u r n ( E R R _ M I S S I N G ) * x p = a t o f ( l i n e ) ; c h e c k = r e a d _ l i n e ( f p , M A X V A L U E _ L E N , i c o u n t , l i n e ) ; i f ( c o u n t == 0 ) r e t u r n ( E R R _ M I S S I N G ) ; / * r e a d n o t h i n g * / i f ( ( c h e c k = = 0 ) I I ( c h e c k = = D ) ( ' * y p = a t o f ( l i n e ) ; / * i f w h i t e s p a c e o r c r l f * / } ' ' • e l s e r e t u r n ( E R R _ E O F ) ; / * E O F e n c o u n t e r e d * / i f ( c h e c k = = 0 ) ( i f ( ( r e a d _ l i n e ( f p , M A X V A L U E _ L E N , i c o u n t , l i n e ) != 1) II ( c o u n t ! = 0 ) ) r e t u r n ( E R R _ E X T R A ) ; / * c r l f e x p e c t e d * / } r e t u r n ( 0 ) ;• / * o k * / } s t a t i c r e a d _ l i n e ( f p , m a x c h a r , n u m _ p , s t r i n g _ p ) / * R e a d s i n c h a r - f r o m f i l e p o i n t e d t o b y f p u n t i l a * / / * n e w l i n e i s d e t e c t e d o r E O F o r a s t r i n g t e r m i n a t e d b y a * / / * w h i t e c h a r a c t e r . T h e c h a r s a r e p l a c e d * / / * i n a s t r i n g f o r m a t i n s t r i n g _ p . I t a l s o r e t u r n s t h e * / / * n u m b e r o f " v a l i d " c h a r s r e a d . "*/ / * T h e f u n c t i o n r e t u r n s a ' 1 ' i f a n e w l i n e i s d e t e c t e d * / / * I t r e t u r n s a ' 2 ' i f E O F .• * / / * O t h e r w i s e i t r e t u r n s a ' 0 ' * / / , * / / * T h e f u n c t i o n r e t u r n s i f n u m b e r o f c h a r s r e a d i s m a x c h a r . * / / * I t w i l l s t i l l r e t u r n a ' 0 ' . * / F I L E * f p ; i n t * n u m _ p , m a x c h a r ; c h a r * s t r i n g _ p ; { i n t f g e t c ( ) ; i n t c ; * n u m _ p = 0 ; / * D i s c a r d l e a d i n g w h i t e c h a r a c t e r s * / w h i l e ( ( ( c = f g e t c ( f p ) ) == ' ' ) | | ( c == ' \ t ' ) ) { ; } / * R e t u r n i f E O F o r n e w l i n e w a s d e t e c t e d * / i f ( c == E O F ) r e t u r n ( 2 ) ; i f ( c == ' \ n ' ) r e t u r n ( 1 ) ; * s t r i n g _ p + + = c ; -( * n u m _ p ) + + ; / * R e a d i n s t r i n g o f v a l i d c h a r a c t e r s u n t i l a w h i t e c h a r a c t e r i s d e t e c t e d * / w h i l e ( ( ( c = f g e t c ( f p ) ) != ' \ n ' ) i i ( c != ' ' ) i i f c != ' \ t ' ) i i ( c != E O F ) ) • * s t r i n g _ p + + = c ; ( * n u m _ p ) + + ; Appendix F. Source code of SOVA 96 i f ( * n u m _ p m a x c h a r ) - b r e a k ; / * b u f f e r f u l l * / } . ' • ' ' i f ( c == E O F ) r e t u r n ( 2 ) ; / * a p p e n d a ' \ 0 ' t o m a k e i t a v a l i d s t r i n g i n ' C * / * s t r i n g _ p = ' \0 ' ,-i f ( c == ' \ n ' ) r e t u r n ( l ) ; e l s e r e t u r n ( O ) ' ; } s t a t i c c a l c _ d i s t a n c e ( c o u n t _ s i g , s i g n a l _ p _ m a g , s i g n a l _ p _ r e , s i g n a l _ p _ i m , d i s t _ p , i n p u t _ s i g , f a d i n g _ a m p ) / * l e t ( x i , y i ) b e t h e i t h c o n s t e l l a t i o n p o i n t a n d ( x , y ) b e t h e * / / * i n p u t . T h i s f u n c t i o n a s s u m e s ( 2 x i , 2 y i , x i * * 2 + y i * * 2 ) t o * / / * b e t h e d a t a i n t h e s i g n a l _ p t a b l e a n d c a l c u l a t e s * / / • d i s t [ i ] ' = ( x i * * 2 + y i * * 2 ) - ( 2 x i * x i - ( 2 y i * y ) * / / « * / i n t c o u n t _ s i g ; s t r u c t c _ s i g n a l i n p u t _ s i g ; d o u b l e * d i s t _ p , * s i g n a l _ p _ m a g , * s i g n a l _ p _ r e , * s i g n a l _ p _ i m ; d o u b l e f a d i n g _ a m p ; ( i n t i ; f o r ( i = 0 ; i < c o u n t _ s i g ; i + + ) ( d i s t _ p [ i ] = f a d i n g _ a m p * f a d i n g _ a m p * s i g n a l _ p _ m a g [ i ] - f a d i n g _ a m p * ( i n p u t _ s i g . c _ r e a l * s i g n a l _ p _ r e [ i ] ) - f a d i n g _ a m p * ( i n p u t _ s i g . c _ i m a g * s i g n a l _ p _ i m [ i ] ) + i n p u t _ s i g . c _ i m a g * i n p u t _ s i g . c _ i m a g + i n p u t _ s i g . c _ r e a l * i n p u t _ s i g . c _ r e a l , - . ) '} s t a t i c i n t _ t o _ b i n ( n u m b i t s , n u m b e r , d e s t _ p ) / * C o n v e r t a n i n t e g e r n u m b e r t o b i t s a n d p l a c e i t i n * / / * t h e a r r a y p o i n t e d t o b y d e s t _ p * / / * T h e f i r s t e l e m e n t i n t h e a r r a y c o n t a i n s t h e l e a s t * / / * s i g n i f i c a n t b i t * / i n t n u m b i t s , n u m b e r ; i n t * d e s t _ p ; { f o r ( ; n u m b i t s > 0 ; n u m b i t s - - ) { * d e s t _ p + + = ( n u m b e r & 1 ) ; n u m b e r >>= 1; ) r e t u r n ( 0 ) ; -J s t a t i c t w o _ r a i s e d ( p o w e r ) / * C a l c u l a t e s 2 * * p o w e r * / i n t p o w e r ; { i n t d u m , -d u m = 1 ; f o r ( ; p o w e r > 0 ; p o w e r - - ) d u m « = l ; r e t u r n ( d u m ) ; } 

Cite

Citation Scheme:

        

Citations by CSL (citeproc-js)

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>
                        
                    
IIIF logo 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-0065313/manifest

Comment

Related Items