UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

Analysis and performance evaluation of an efficient protocol for the CDPD forward channel Zhang, Xu (Jake) 2001

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

Item Metadata

Download

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

Full Text

A N A L Y S I S A N D P E R F O R M A N C E E V A L U A T I O N O F A N E F F I C I E N T P R O T O C O L F O R T H E C D P D F O R W A R D C H A N N E L by X U (JAKE) Z H A N G B . Eng., The Beijing Broadcast Institute, 1996 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 T H E UNIVERSITY O F BRITISH C O L U M B I A September 2001 © Xu (Jake) Zhang, 2001 In presenting this thesis in partial fulfilment of the requirements for an advanced degree at the University of British Columbia, I agree that the Library shall make it freely available for reference and study. I further agree that permission for extensive copying of this thesis for scholarly purposes may be granted by the head of my department or by his or her representatives. It is understood that copying or publication of this thesis for financial gain shall not be allowed without my written permission. Department of ^LtcmicAL $ COMPUTE/? GuamER.^ The University of British Columbia Vancouver, Canada DE-6 (2/88) Abstract The purpose of this thesis is to analyze and evaluate the performance of the Cel lu lar Digital Packet Data (CDPD) forward channel at the Medium Access Control ( M A C ) layer, and propose an efficient protocol to improve the M A C layer throughput. First we study the M A C layer by several performance measures, such as the Block Error Rate ( B L E R ) , Packet Error Rate (PER) , and the throughput. According to our studies on the forward channel M A C layer structure, we analyze the relationship among the three performance measures, and between them and the channel B i t Error Rate ( B E R ) , in the presence of the Additive White Gaussian Noise ( A W G N ) channel. For comparison purposes, computer simula-tions have also been conducted with the A W G N channel, and land-mobile Rayle igh fading channel, with the employment of both a coherent and a 1-bit differential G M S K receiver. A s a result of this study, a source of performance inefficiency, namely, the Correct but Unusable Data (CUD) , is identified. We argue that the M A C layer throughput is affected not only by the error performance of the physical layer, but also by the M A C layer block segmentation, which is the main cause of the C U D . The percentage of C U D peaks to about 45% regardless the channel conditions. In order to eliminate this inefficiency we propose a M A C - A R Q protocol which performs A R Q operation at the M A C layer. Verified by computer simulations, this protocol effectively improves the throughput at certain channel conditions, while slightly degrades the performance at other conditions. Final ly , in order to maintain maximum throughput over all channel conditions, we propose an adaptive scheme which automatically switches back and forth between the conventional A R Q protocol and the M A C - A R Q protocol according to the channel conditions. 11 Table of Contents Abstract ii List of Figures vi List of Tables viii List of Abbreviations ix Acknowledgment xi Chapter 1 Introduction 1 1.1 C D P D Overv iew [2] 2 1.2 Performance Considerat ions 4 1.3 Resea rch Object ives of the Thes is 8 1.4 Thes i s Organizat ion 9 Chapter 2 CDPD System Model 11 2.1 Introduction 11 2.2 P H Y Layer Configuration 13 2.2.1 G M S K Transmitter 13 2.2.2 Communicat ion Channe l Mode l 15 2.2.3 G M S K Rece ivers 18 2.3 M A C La^er Configuration 21 2.3.1 M A C Layer Configuration at the M D B S 22 2.3.2 Packet Reconstruct ion at the M - E S 24 2.3.3 Med ium A c c e s s Algorithm 26 2.4 Log ic Link Layer and A R Q Procedure 26 i i i 2.4.1 L L C Layer Frame Structure 27 2.4.2 A R Q Procedure 28 2.5 Computer Simulat ion Model and Parameters 29 2.5.1 M D B S Model 29 2.5.2 Communicat ion Channe l Mode l 30 2.5.3 M - E S Model 31 2.6 Summary 31 Chapter 3 Performance Analysis and Evaluation 33 3.1 Introduction 33 3.2 Correct but Unusable Data 33 3.3 Block and Packet Error Performance 36 3.4 Throughput Per formance 40 3.5 Numer ica l Resul ts and Discuss ion 42 3.5.1 B L E R s a n d P E R s 42 3.5.2 C U D 51 3.5.3 Throughput 53 3.6 Summary 56 Chapter 4 MAC-ARQ Protocol 57 4.1 Introduction 57 4.2 Descript ion and Performance Evaluation of the M A C - A R Q Protocol 57 4.3 The Adapt ive S c h e m e 63 4.4 Summary 68 Chapter 5 Conclusion and Some Suggestions for Future Research 69 IV 5.1 Conc lus ions 69 5.2 Suggest ions for Future Research 70 • 5.2.1 Effect of the M A C - A R Q protocol to the reverse channel 70 5.2.2 Revoke the A R Q operation at the data link layer for the M A C - A R Q scheme 70 5.2.3 Soft threshold for the adaptive scheme 70 5.2.4 Per formance study for similar appl icat ions other than C D P D 71 5.2.5 Diversity reception 71 5.2.6 More advanced coding techniques 71 References 72 Appendix A. Program Listings 76 List of Figures Figure 1.1 Genera l C D P D system architecture [3] 3 Figure 2.1 OSI reference model 12 Figure 2.2 M - E S protocol stack 12 Figure 2.3 Block diagram of G M S K transmitter 14 Figure 2.4 (a) Pu lse response of Gauss ian lowpass filter, (b) Cor respond ing power spectral of G M S K signals [16] 16 Figure 2.5 B lock diagram of communicat ion channe l model 18 Figure 2.6 Block diagram of coherent G M S K detector 19 Figure 2.7 B lock d iagram of G M S K 1 -bit convent ional differential detector 20 Figure 2.8 Data transmission procedures in the forward channe l 23 Figure 2.9 Flow chart for (a) procedure of F C T S generat ion at the M D B S ; (b) procedure of L P D U reconstruction at the M - E S 25 Figure 2.10 Structure of the L L C frames 27 Figure 2.11 Block diagram of computer simulation model 29 Figure 3.1 Generat ion of correct but unusable data (CUD) 34 Figure 3.2 Percentage of C U D in the A W G N channel with coherent detection 35 i Figure 3.3 Probabil i ty of a packet in error (PP) versus Probabil i ty of a block in error (PB) 39 Figure 3.4 B L E R and" P E R in the A W G N channel 43 F igure 3.5 B L E R and P E R with differential detection in the Rayle igh fading channel with fD =20 Hz 45 Figure 3.6 B L E R and P E R with differential detection in the Rayle igh fading channe l with f D =40 H z 46 Figure 3.7 B L E R and P E R with differential detection in the Rayle igh fading channel with fD =80 Hz ! 47 : vi Figure 3.8 Compar i son of B L E R s and P E R s with different Doppler shift f requencies with differential detection in the Rayle igh fading channel , (a) B L E R . (b) P E R 49 Figure 3.9 B E R with error correction coding in the Rayleigh fading channe l 50 Figure 3.10 Percentage of C U D with differential detection in the Rayle igh fading channel 52 Figure 3.11 Throughput versus B E R with coherent detection in the A W G N channel , where the packets are transmitted in their default lengths 54 Figure 3.12 Throughput versus EJN0 in the Rayleigh fading channel 55 Figure 4.1 Data t ransmission procedures in the forward channel 58 Figure 4.2 Throughput versus B E R with coherent detection in the A W G N channel , where the packets are transmitted in their default lengths 61 Figure 4.3 Throughput versus Eb /No with differential detection in Rayle igh fading channel , where the packets are transmitted in their random lengths 62 Figure 4.4 Throughput versus B E R with differential detection in Rayle igh fading channel ( f D =20Hz), where the packets are transmitted in their random lengths 64 Figure 4.5 Throughput versus B E R with differential detection in Rayle igh fading channel (fD=40Hz), where the packets are transmitted in their random lengths 65 Figure 4.6 Throughput versus B E R with differential detection in Rayle igh fading channel ( f D =80Hz), where the packets are transmitted in their random lengths 66 vii List of Tables Table 3.1 The 9 0 % conf idence interval for each B L E R 44 Table 4.1 Observed B E R thresholds for various Doppler shifts 63 viii List of Abbreviations A M P S Advanced Mobile Phone Service A R Q Automatic Repeat Request A W G N Additive White Gaussian Noise B E R Bit Error Rate B L E R Block Error Rate C D Collision Detection C D P D Cellular Digital Packet Data C F D B S Continuous Frame Data Bi t Stream C L N P Connectionless Network Protocol C P M Continuous Phase Modulation C S M A Carrier Sense Multiple Access C U D Correct but Unusable Data D S M A Digital Sense Multiple Accessing ES End System F C T S Forward Channel Transmission Sequence F E C Forward Error Correction F-ES Fixed End System F M Frequency Modulation G B P F Gaussian Bandpass Filter G L P F Gaussian L o w Pass Filter G M S K Gaussian Minimum Shift Keying G P R S General Packet Radio Service G S M Groupe Speciale Mobile IP Internet Protocol IS Intermediate System ISI Inter-Symbol Interference L L C Logic L ink Control L P Large Packet L P D U Link Protocol Data Unit M A C Medium Access Control M D B S Mobile Data Base Station M D - I S Mobile Data Intermediate System M D L P Mobile Data Link Protocol M - E S Mobile End System M P Medium Packet N A K Negative Acknowledgment N R Z Nonreturn to Zero OSI Open System Interconnection P E R Packet Error Rate P H Y Physical Layer R F Radio Frequency R L C Radio Link Control RS Reed-Solomon R S - D B Reed-Solomon Data Block S N D C P Subnetwork Dependent Convergence Protocol SP Small Packet S-REJ Selective-Reject W W W World Wide Web X Acknowledgments This thesis is dedicated to my father, Hangfu Zhang, my mother, Lanying Guo, and my wife M a n L i , who have been giving me constant, unconditional support during my studies. I am enormously grateful to my supervisor, Dr. P. T. Mathiopoulos, for his constant encouragement and continual guidance. Without his invaluable suggestions and support, the completion of this thesis would not have been possible. Also I would like to thank Dr. A . Salkintzis and my friend Hong Nie for their useful discussions and suggestions on the thesis work. xi Chapter 1 Introduction 1 Chapter 1 Introduction Cellular Digital Packet Data (CDPD) is a mobile data technology that permits subordinate packet data operation on the spectrum assigned to a telephone cellular network, such as the Advanced M o b i l e Phone Service ( A M P S ) . It is considered as a very promising mobile data technology featuring many important benefits [1]. Among many other wireless communication standards, C D P D provides satisfactory performance with comparatively less complexity. For this reason, C D P D technology has been deployed and supported by many major wireless data operators particularly in North America, including G T E Wireless, A T & T Wireless, Be l l Atlantic Mobile , Ameritech, and M c C a w Cellular. C D P D was firstly designed to accommodate short data transmissions during the interval between the talk spurts of a voice network. It is ideally suited for applications where small amounts of data need to be transferred from remote locations to a central system. Typica l examples of its applications include telemetry, vehicle tracking, and personal messaging, etc. However, due to the phenomenal growth of the wireless communication market and the popular-ity of the Internet, the demand for mobile data exchange, e.g. mobile internet access, has been increasing considerably. Particularly, the potential of applications and markets built around the World Wide Web ( W W W ) is enormous. Because these W W W applications usually involve rich multimedia data downloading, it is important for C D P D to support these applications effectively, especially in the forward channel, i.e. the channel from the central system to the mobile user. C D P D supports 19.2-kbps raw data rate at the physical layer, which, at best, allows a mobile user to be able to obtain throughput performance similar to that of a 14.4-kbps wireline modem [1]. Therefore, for applications which only involve a moderate amount of graphics, C D P D is still a Chapter 1 Introduction 2 practical and appropriate solution. In order to effectively maintain and improve the performance, higher transmission efficiency is required on the C D P D forward channel. Consequently it is important to investigate the characteristics of this channel in order to determine its capabilities, to reveal its possible deficiencies and to propose potential improvements. In this thesis, the perfor-mance of C D P D forward channel is studied; a source of data transmission deficiency is identified, and a new protocol, which eliminates this degradation, is proposed, analyzed, and its performance evaluated. 1.1 CDPD Overview [2] The important subsystems of a C D P D network are the E n d Systems (ESs) and the Intermediate Systems (ISs), as shown in F i g . 1.1. The ESs represent the actual physical and logical end nodes that exchange information, while the ISs represent the C D P D infrastructure subsystems that store, forward and route the information. In Internet terminology, the ESs are known as hosts and ISs are known as routers. There are two kinds of ESs: The Mobile End System (M-ES) , which is a device used by a mobile subscriber to access the C D P D network over the wireless interface, and the Fixed End System (F-ES), which is a common host, server or gateway with fixed connection to the C D P D backbone and provides access to specific applications and data. On the other hand, there are two kinds of ISs: A "generic" IS, which is simply a router (in most cases, an Internet Protocol (IP) router) with no knowledge of C D P D and mobility issues, and Mobile Data Intermediate System (MD-IS) , which is a specialized IS that routes messages based on its knowledge of the current location of M - E S s . The M D - I S is a set of hardware components and software functions that provide switching, accounting, registration, authentication, encryption Chapter 1 Introduction 3 External.Network x | {e.g. Interne!) Figure 1.1 General CDPD system architecture [3] and mobili ty management functions. Besides the ESs and ISs, there is another subsystem, the Mobile Data Base Station ( M D B S ) , which is analogous to a common cellular base station. M D B S creates and manages an air interface between the M - E S and the C D P D backbone. It performs no networking functions but rather relays data link information between a number of M - E S s and their serving M D - I S , which is a data-link functional subsystem. It also performs radio resource Chapter I Introduction 4 management procedures such as channel hopping 1 . The C D P D backbone provides connectionless transport services, or "datagram" services, where the network individually routes packets based upon the destination address each packet carries and the knowledge of the current network topology. For example, it supports routing of both IP packets (with the Internet protocol) and the C L N P packets (with the Connectionless Network Protocol) in the Open System Interconnection (OSI) reference model [2]. Al though the C D P D was or iginal ly designed to accomplish data transmission over existing voice communication channels, it can also be implemented over a separated channel, which is permanently dedicated to the C D P D data transmissions. This is referred to as a dedicated channel, while in contrast, in the former case it is referred to as a nondedicated channel, where the C D P D shares a common channel pool with the underlying cellular voice system [3]. In this case, the C D P D has to release its forward channel whenever this channel is selected for voice transmis-sion. 1.2 Performance Considerations The increasing of the C D P D popularity has attracted significant growth of research activi-ties on C D P D performance [4-11]. In general, the performance of the C D P D can be evaluated by the efficiency of data transmission from the source node to the destination node. Due to limited frequency bandwidth and data rate, it is easy to see that the bottle neck of the performance is the wireless interface, i.e. the airlink between the M D B S and the M-ESs . As it wi l l be explained with details in the next chapter, the M D B S functions at and below the medium access control ( M A C ) 1 Channel hopping is required for a nondedicated channel where CDPD overlays the existing cellular voice network [1]. Chapter 1 Introduction 5 layer, and relays information from the logic link control ( L L C ) layer between the M - E S and the M-IS . Hence, it would be beneficial to us by conducting a performance study from the M A C layer point of view. The study wi l l provide us with an idea of how the system behaves over the airlink. Therefore, by identifying and eliminating any possible inefficiencies, the overall system perfor-mance can be improved. Firstly, let us consider the main causes of performance degradations in the C D P D airlink. They usually fall into the following three categories: i) Impact of the underlying voice network This applies only to the nondedicated channel system, where the C D P D overlays on top of the existing voice channel. It "borrows" the voice channel when it is available and hop to another free one before the voice connection is set up in this channel. Saha and Kay[5] as well as Budka [8] have investigated the effects of C D P D on the voice channel and that of the voice channel to the C D P D . They have concluded that the C D P D can provide efficient data transmission without substantial degradations to the voice quality. ii) Sharing of the reverse channel The access to the reverse channel is shared by the M - E S s within the same cell. Therefore, the C D P D employs an algorithm at the M A C layer, namely, the Digital Sense Multiple Accessing with Coll ision Detection ( D S M A / C D ) , to regulate the access of the M - E S s and to avoid collision. In the past, several studies, including [5], [10], and [11], have been carried out on the performance with D S M A / C D , mainly focusing on their time delay performance, or the delay throughput. Hi) Physical channel impairments Chapter 1 Introduction 6 A noisy mobile communication channel may cause severe distortion to the transmitted signal waveform, yielding errors to a large number of bits. To combat this, coding techniques can be employed, such as the Forward Error Correction (FEC) codes, which performs error checking and correction at the receiver end [33]. A l s o the type of the signal detector employed at the receiver can affect the performance significantly. It should be chosen so that it is robust to the particular type of channel impairments. For example, in the C D P D , where the Gaussian Min imum Shift-Keying ( G M S K ) modulation scheme is employed, a differential detector may have better error performance than a coherent detector in a mobile communication channel [28]. There are also other approaches on improving the performance at the physical layer such as to employ diversity or smart antenna technologies at the mobile receiver [4]. As discussed, among the performance studies carried on C D P D so far, only a few address the performance at the M A C layer [5][10][11]. To our best knowledge, there is even no studies focused particularly on the forward channel. Therefore, in this thesis we concentrate on the performance of the forward channel M A C layer. Specifically, we wi l l be investigating a number of performance measures that can be considered for the evaluation of the forward channel perfor-mance, including the average Block Error Rate ( B L E R ) , the average Packet Error Rate (PER) , and the M A C layer throughput. The B L E R is the probability of erroneous blocks encoded with error correction codes at the M A C layer. The P E R is the probabil i ty of erroneous packets generated from the layer above the M A C layer. The throughput represents the transmission efficiency of the actual information at the M A C layer. From the user point of view, these perfor-mance measures are more important than the equivalent physical layer measures, such as the average B i t Error Rate ( B E R ) , since they demonstrate more closely what the user perceives in terms of performance. However, for comparison purposes, the B E R s in the physical channel have Chapter 1 Introduction 7 also been included in this thesis. Although several studies have been carried out on the estimation of the B L E R in mobile communication channels (e.g. [12], [13], and [14]), however, researches on the relations between the B L E R and P E R are relatively rare. Hence, in this thesis we w i l l investigate the performance of B L E R and P E R and their relations. We also identify a source of performance degradation, which we term as "the correct but unusable data" ( C U D ) . It is caused by the variety of the packet lengths and the alignment between the packets and the Reed-Solomn (RS) coded blocks at the M A C layer. To perform a realistic study it was necessary to make several assumptions about the physical layer, such as the type of the communication channel and the type of the detector used at the receiver to detect the G M S K signal. As it wi l l be explained later, we have considered in our computer simulation studies the communication channel to be a narrowband land-mobile Rayleigh fading channel with Additive White Gaussian Noise ( A W G N ) . Furthermore, we have investigated the performance of two types of receiver structures, namely, the coherent receiver and the differential receiver. During our performance studies, we have identified a source of performance degradation that causes the receiver to discard data that is not corrupted by the channel impairments. To mitigate this performance degradation we have proposed a new protocol, namely, the M A C - A R Q protocol, which performs the auto-repeat request (ARQ) operations at the M A C layer instead of the L L C layer. There are similar approaches applied or proposed to other applications [39][40], where the auto retransmission mechanism is e l iminated in the data l i nk operat ion and implemented in the M A C layer. In this thesis, on the other hand, our purpose is to minimize structural modifications to the well-defined C D P D standard, while improve the performance as Chapter 1 Introduction 8 much as possible. Therefore, we leave the conventional A R Q mechanism in the data link layer and propose another selective A R Q operation in the M A C layer. Rather than implementation details, we concentrate on the analysis and evaluation of the performance differences between the conventional scheme and the proposed approach. We demonstrate considerable improvements to the performance under certain channel conditions. Considering the trade-off it also brings up, we discuss an adaptive scheme that dynamically enables/disables the activation of the M A C - A R Q scheme according to the channel conditions. 1.3 Research Objectives of the Thesis Based upon the above discussion, it is worth and of interest to study the forward channel M A C layer performance, identifying, and eliminating (or mitigating) possible inefficiencies, hence improve the overall system performance. In this respect the main research objectives of this thesis can be identified as follows. 1. To analyze the relationship among the M A C layer B L E R , the P E R , and the throughput at the forward channel, and the relationship between these measurements and the channel B E R . Additionally to evaluate analytically and by means of computer simulations, these performance measures with various G M S K receiver types, in the presence of both A W G N channel and land-mobile Rayleigh fading channel. 2. To eliminate a source of performance degradation identified as the C U D , and hence improve the forward channel performance in certain conditions by a new M A C - A R Q pro-tocol. 3. To propose and evaluate an adaptive A R Q scheme to dynamically choose the appropriate A R Q operation with better throughput, and hence improve the overall system perfor-Chapter 1 Introduction 9 mance. 1.4 Thesis Organization Including this introductory chapter, this thesis consists of five Chapters and one Appendix. Its organization is as follows: * Chapter 2 describes the C D P D system model. It starts with an introduction in Section 2.1. Afterwards, a detailed description of the physical layer configuration is presented in Section 2.2. Then the configuration of M A C layer is detailed in Section 2.3, followed by the description of the L L C layer configuration and the A R Q operation in Section 2.4. The computer simulation model and parameters are presented in Section 2.5. The chapter is concluded with a summary in Section 2.6. Chapter 3 evaluates the forward channel performance in terms of the measures discussed above, and introduces the performance degradation source. A brief introduction in presented in Section 3.1. The description of the degradation source is detailed in Section 3.2. Then the relations between the B L E R and P E R are analyzed in Section 3.3, followed by the derivation of the throughput expression in Section 3.4. Numerical results of the computer simulations and discussions are presented in Section 3.5, and a summary of the chapter appears in Section 3.6. Chapter 4 provides descriptions of the proposed M A C - A R Q protocol. After a brief introduction in Section 4.1, the configuration of this protocol is presented in Section 4.2. The throughput evaluation of the proposed protocol is presented in Section 4.3. The adaptive scheme wi l l be discussed in Section 4.4, and the summary of this chapter is in Section 4.5. Chapter 5 presents conclusions of this thesis and some suggestions for future research. Chapter 1 Introduction 10 Appendix A contains program listings for the computer simulations, including the G M S K transmitter, the 1 -bit differential detector, and the Rayleigh fading simulator. Chapter 2 CDPD System Model 11 Chapter 2 CDPD System Model 2.1 Introduction The C D P D standard supports both the internet protocol stack and the Open System Interconnection (OSI) reference model developed by the International Standards Organization [15]. As depicted in F ig . 2.1, it consists of seven layers, namely, the physical layer, the data link layer, the network layer, the transport layer, the session layer, the presentation layer and the application layer. In order to assure the compatibility of C D P D networks with existing applica-tions software, the protocols above the network layer remained with no modification, whereas new protocols below this layer have been designed to accommodate the communications between the M - E S and the M D - I S . The protocol stack below layer 3 at the M - E S is illustrated in F ig . 2.2, where the M A C layer protocol supports the connection between the M - E S and the M D B S , and the pair of protocols, inc luding the M o b i l e Data L i n k Protocol ( M D L P ) and the Subnetwork Dependent Convergence Protocol ( S N D C P ) , enables communications between the M - E S and M D - I S . The network layer supports both IP protocol and the OSI Connectionless Network Protocol ( C L N P ) to accomplish the routing of the I P / C L N P packets over the C D P D backbone. In this thesis we mainly concentrate on the protocols in the three lower layers, including the physical (PHY) layer, the M A C layer and the L L C layer. The organization of this chapter is as follows. After this introduction, in Section 2.2 we wi l l be describing the P H Y layer configuration including the modulation/demodulation schemes and the communication channel. In Section 2.3 we wi l l give detailed description of the M A C layer configuration, including how the link layer data packets are transformed into a bit stream at the M D B S , and how they are reconstructed at the M - E S . In this section we wi l l also briefly address the medium access algorithm. Then in Section Chapter 2 CDPD System Model 12 Layer 7 Application Layer Layer 6 Presentation Layer Layer 5 Session Layer Layer 4 Transport Layer Layer 3 Network Layer Layer 2 DataiJnk Layer Layer 1 Physical Layer Figure 2.1 OSI reference model. M-ES IP/CLNP SNDCP L L C Layer (MDLP) M A C Layer (MAC) Physical Layer ' (PHY) CDPD Air Interface • i Forward RF Channel i • Reverse RF Channel Ethernet Figure 2.2 M-ES protocol stack. 2.4 the configuration of the logic link layer wi l l be provided, together with the A R Q mechanism employed in this layer. Chapter 2 CDPD System Model 13 2.2 PHY Layer Configuration As illustrated in Fig . 2.2, the P H Y layer communication between an M D B S and an M - E S takes place through the C D P D air interface. Furthermore, the communications between the M D B S and the M D - I S takes place through wired connection, such as the Ethernet. In this section we mainly focus on the air-interface between the M - E S and the M D B S . It consists of a pair of 30kHz-bandwidth R F channels, i.e. the forward channel and the reverse channel. The function of the P H Y layer entities is to transform a sequence of bits from the M A C layer into a modulated waveform suitable for transmission onto the 30 kHz Radio Frequency (RF) channel, while being responsible for managing the radio resource and maintaining the signal power and communica-tion quality. The raw data transmission rate that C D P D can provide on both forward and reverse channel is 19.2 kbps. The physical layer modulation scheme employed on the C D P D R F channel is Gaussian Minimum-Shift Keying ( G M S K ) , which is a popular member of the Continuous Phase Modula-tion ( C P M ) family with excellent spectral properties and simple implementation structures [16]. The following sections wi l l describe the G M S K transmitter and receiver structures, as well as the communication model. 2.2.1 GMSK Transmitter The block diagram of a G M S K transmitter is shown in F ig . 2.3. It consists of a Gaussian L o w Pass Filter ( G L P F ) and a Frequency Modulator ( F M ) . The input to the G L P F is a binary nonreturn to zero (NRZ) sequence2. The G L P F is used to bandlimit the input pulses. The output A differential encoding process needs to be applied to the input signal before it is fed into the GLPF, if the sig-nal is detected by a 2-bit or higher bit number differential detector [17]. In this thesis where the coherent detector and 1-bit conventional detector are employed, the presence of diiferential encoder is not required. Chapter 2 CDPD System Model 14 ak GLPF x(t) F M Modulator hjit) h = 0.5 s(t) Figure 2.3 Block diagram of G M S K transmitter signal x(t) can be written as x(t) = £ akg{t~kT) k = -<*> where g(t) = hT{t)®p{t) (2.1) (2.2) where ® denotes a convolution, p(t) is a rectangular pulse of duration Tand unity amplitude, and hj(t) is the impulse response of the G L P F [19]. This impulse response can be mathematically expressed as: hT(t) = - U . ^ e x p H ^ O 2 ] (2.3) where kx = n ^ = 5.336 and Bt is the 3-dB bandwidth of the G L P F . The output of the F M , the transmitted G M S K signal s(t) can be mathematically expressed as s(t) = A o c o s [ 2 7 c / c f + <|>(0] (2-4) where Aa is the constant amplitude, fc is the carrier frequency and Chapter 2 CDPD System Model 15 <K0 = 27u/z £ ak jg(x-kT)dx (2.5) k — — ° ° — 0 0 where h is the modulation index. For MSK- type signals we have h - 1/2 so that the maximum phase change over one symbol duration T is n/2 [20]. g(t) is the input pulse response of the G L P F which is normalized such that [ g(t)dt = — . It is given by [18], Q k7BtT - - -2 ' 2 T (2.6) where k2 = Jlkx ~ 7.547 , BtT is the normalized (to symbol duration) 3-dB bandwidth of G L P F and Q( • ) is the well known Q-function given by [21] 727t y The pulse shape and spectral properties of G M S K signals heavily depend on the BtT product. F ig . 2.4 illustrates the plots of g(t) and corresponding power spectrum with BtT as a parameter. Differ-ent values of the BtT product have been chosen for different applications. For example, G S M has chosen BtT= 0.3 as the standard, while in the C D P D standard that we are investigating in this thesis, BtT= 0.5 has been adopted [1]. 2.2.2 Communication Channel Model In urban areas, the mobile radio environment between an M - E S and an M D B S can be characterized as a multipath medium, where the transmitted signal waves are reflected from Chapter 2 CDPD System Model Figure 2.4 (a) Pulse response of Gaussian lowpass filter, (b) Corresponding power spectral of GMSK signals [16] Chapter 2 CDPD System Model 17 nearby objects or buildings [23]. Therefore, in most cases, the M - E S receives no signal from the direct path but a sum of scattered signals with various strengths and delays, resulting signal amplitude fluctuation and phase randomization. This dispersive medium is a typical land-mobile channel, referred to as multipath fading or Rayleigh fading channel, where the amplitude r of the faded carrier is a Rayleigh distributed random process and the signal phase 0 is uniformly distrib-uted from 0 to 2K [22]. Mathematically this can be expressed as, f(r) = 1 ^ p { ~ ) when r > 0 0, when r<0 (2-8) where / ( • )denotes the probability density function (pdf), and b is the mean power [22]. A fading channel is associated with a multipath spread which represents the time delay spread of the incoming multipath signals. If the multipath spread relative to the symbol duration is small enough so as not to cause any Inter-Symbol Interference (ISI), the fading channel can be classi-fied as frequency-nonselective or flat fading, and as frequency-selective fading i f vise versa [24]. Since a C D P D radio channel is 30-kHz narrow band, we w i l l only consider flat fading in our work. Furthermore, the M - E S in motion also suffers from the Doppler frequency shift, which spreads the received carrier frequency. The maximum Doppler shift frequency is determined by the velocity V of the mobile unit, the transmitted carrier frequency fc, and the speed of light g c ~ 3 x 10 m/s, i.e. Chapter 2 CDPD System Model 18 Vfc (2.9) c Let us consider the value of the normalized Doppler shift bandwidth fDT. Suppose the mobile is moving in 100 km/hour, assume the carrier frequency is 800 M H z , and the transmission data rate is 19.2 kbps, then the resulting fDT is approximately 0.0039, which is a quite small value. Since the mobile's velocity is normally less than 200 km/hour, according to the results illustrated in this example, we can consider that our system is operating in a slow fading environment. A block diagram of the used channel model is shown in F i g . 2.5. The transmitted signal s(t) is multiplied by the fading signal f(t), the resulting signal is then corrupted by the A W G N n(t) with double-sided power spectral density of Na/2. The fading signal is generated by the wel l -known Jakes' fading simulator [22]. 2.2.3 GMSK Receivers G M S K receivers can be classified into two categories, i.e. coherent receivers [16] and noncoherent receivers, which can be either differential receivers or limiter/discriminator receivers [17]. Coherent detection exploits knowledge of the carrier's phase reference and thereby provid-ing the optimum error performance over A W G N channel. However, in real mobile communica-f(t) n(t) Jakes' Fading Simulator Figure 2.5 Block diagram of communication channel model Chapter 2 CDPD System Model 19 tion channels, non-coherent detection such as differential detection, which does not require carrier recovery, exhibits a better error performance with the presence of channel interference including fading. Beyond conventional differential detectors, there are also other types of implementations with various enhancements depending on particular performance requirements, such as the 2-bit differential detector with/without decision feedback [25]. However, for the purpose of this thesis we wi l l consider only the performance with both a conventional coherent receiver and a conven-tional 1 -bit differential detection receiver. Coherent receiver: The block diagram of the coherent receiver is depicted in F ig . 2.6 [16]. The signal is passed through the post-detection filter, which is a Gaussian bandpass filter (GBPF) with BrT= 0.63 [16]. The band-limited signal is then quadrature demodulated into the in-phase and quadrature-phase components I(t) and Q(t). The /, Q baseband signals are alternatively sampled at 2T intervals. Finally the sampled data sequence are fed into a bit decision logic to generate the final information bits. 2cos(27t/cf) r(t) GBPF (2k+l)T Bit Decision Logic -2sin(27t/cf) 2kT Figure 2.6 Block diagram of coherent G M S K detector Chapter 2 CDPD System Model 20 d,(t) dj(kT) Figure 2.7 Block diagram of G M S K 1-bit conventional differential detector Differential receiver: The block diagram of the conventional 1-bit differential detector is depicted in F ig . 2.7 [26]. From the channel model, the received signal can be expressed as the sum of the Rayleigh-faded signal /(t) and the A W G N n(t) as, r(t) = sf(t) + n(t). (2.10) The signal-to-noise ratio (SNR) can be expressed as [18] SNR = K_ = a(t) (2.11) where Brn = 1.0265 r is the normalized noise bandwidth of the predetection receive filter Hr(f), which is a 4-th order bandpass Butterworth filter with BrT= 1.0 [26], and a(t) is the normalized signal amplitude after the signal is filtered [18], i.e. a{t) = J[hr(t) <8> cos(<K0)] 2 + ihr(t) ® sin(())(0)] 2. (2.12) A s illustrated in F ig . 2.7, the bandpassed signal is multiplied by its own version which is one-bit delayed and Tt/2-phase shifted. The sampler output is obtained by lowpass-filtering and sampling the product of the one-bit detector. If the effects of fading, noise, and intersymbol Chapter 2 CDPD System Model 21 interference due to filtering are ignored, the normalized sampled value d}(kT) can be expressed as [26], d^kT) = sm(A<\>k) (2.13) where oo I = - o o is the differential phase angle, with which the decision can be made by ak = sgn[d,(fcr)] (2.15) where ak is the estimate of information bits ak, sgn[x] = 1 for x > Oand sgn[x] = -1 for x < 0. 2.3 MAC Layer Configuration The M A C layer entities logically operate between the P H Y and L L C layers to convey information, namely, link protocol data units ( L P D U s ) , between peer L L C entities across the C D P D air interface. It provides the following primary services [3]: • Encapsulates the L P D U s into frame structures to ensure L P D U delimiting, frame syn-chronization and data transparency; • Encodes the sequence of frames to provide error protection against mobile channel im-pairments; • Detects and corrects bit errors within received frames; Chapter 2 CDPD System Model 22 • Arbitrates access to the shared reverse channel; • Synchronizes with the forward channel transmissions to make feasible the reception of data as well as control information transmitted in every C D P D cell. In Chapter 1 we have discussed several main causes of performance degradations in C D P D airl ink, and argued that it is important and necessary to study the performance of the forward channel M A C layer. Before we start, it is instructive to outline the M A C layer configura-tion and its primary functions in the forward channel. In the following subsection we wi l l describe in detail how the L P D U s are transformed into a continuous data sequence, namely, the Forward Channel Transmission Sequence (FCTS) at the M D B S . Then we wi l l describe the procedure of recovering the received L P D U s at the M - E S in Section 2.3.2. Final ly in Section 2.3.3 we w i l l briefly address the medium access algorithm which is employed at the M A C layer to arbitrate access to the shared reverse channel. 2.3.1 MAC Layer Configuration at the MDBS Let us consider a number of L P D U s that need to be transmitted by the M D B S . A s illustrated in F i g . 2.8, these L P D U s are first flag-delimited using the well-known flag pattern 01111110 at the M A C layer [2]. Subsequently, zero-stuffing takes place to ensure data transpar-ency and then the L P D U s are linked together to form a continuous frame data bit stream. It should be noted that the transmission of this bit stream is never interrupted. For example, even when there are no L P D U data for transmission, instead either control L P D U s or sequences of contigu-ous flags are transmitted. Hence, a contiguous sequence of data packets is continuously transmit-ted on the forward channel, and is referred to as the Continuous Frame Data Bi t Stream ( C F D B S ) . Chapter 2 CDPD System Model 23 • c/3 trot go; trot Addi : ' ; 0 ' ldress ldress Information idress idress : : . C : Information ! : :< : : :u : Lwi£ Protocol Data Units 1 1 1 1 1 1 1 / / Flags •R M CB . E Flags! WIS BU 08 -^274 bits Continuous Frame Data Bit Stream 21A bits ^ Data Block / / ' / i i i i 274 bits z \ 274 bits / i / \ / \ / \ / \ / \ •;274(bitsp; Data W> hits l \ n i i \ 274 bits Data 96 bits Parity Sequence of RS-blocks RS-DB 378 bits RS-DB 378 bits s ^ Color Code N 8 bits w w w RS-DB 378+7x6=420bits RS-DB VControl Flag Forward Channel Transmission Sequence Figure 2.8 Data transmission procedures in the forward channel. * Following the C D P D standard, the C F D B S is divided into segments of 274 consecutive bits and each segment is prefixed by an 8-bit Color Code. In this way, a series of consecutive data blocks is formed each one with a fixed length of 282 bits. The Color Code is a special pattern assigned to every individual C D P D channel stream and is used for co-channel interference detection. For each celi, all R F channels available for C D P D are assigned the same value of Color Code [2]. The data blocks are then encoded using a systematic (63,47) Reed-Solomon (RS) error correcting code. From the encoding point of view, each data block represents an information field of 47 6-bit symbols (or codewords). The encoding of this information field generates a 16-symbol Chapter 2 CDPD System Model 24 parity field (96 bits), which is appended at the end of each data block. Thus, a consecutive sequence of RS-encoded data blocks (RS-DB) is generated, as shown in Fig . 2.8. These R S - D B s , each one with a fixed length of 378 bits, form the basic transmission units of the forward channel. Note that this (63,47) RS coding is common to both the forward channel and the reverse channel and is capable of correcting up to 8 erroneous symbols within one block [7]. Prior to actual transmission on the forward channel, each RS block is passed through a 9th order scrambler with a generator polynomial, g(x) = x9+ x 8 + x5+ x 4 + l . This process reduces the l ikelihood to have long strings of binary ones and zeroes within the transmission bit stream. Such long strings are generally avoided because they are not easily tracked by certain types of demodulators (e.g. phased locked loops) and may result in reduced performance or increased implementation complexity. A general flow chart describing the procedure of generating the Forward Channel Transmission Sequence (FCTS) is illustrated in Fig . 2.9a. It should be noted that the actual F C T S is the contiguous sequence of R S - D B s (after scrambling) interleaved with special Control Flags. These flags carry synchronization information that helps M - E S s acquire block synchronization and decode the forward channel, as well as M A C - l e v e l control information that helps M - E S s effectively share the common reverse channel. 2.3.2 Packet Reconstruction at the M-ES The flow chart of the procedure of L P D U reconstruction at the M - E S is shown in F i g . 2.9b. The received bit sequence is formed at the M - E S after signal demodulation and detection at the P H Y layer. After control flag extraction and descrambling, which are the reverse processes to recover the R S - D B s at the M A C layer, the R S - D B s are Reed-Solomon decoded. The operation Chapter 2 CDPD System Model 25 L L C I^ayer J LPDUs Frame Delimiting i k LPDUs Reconstruct Correct Packets Bit Stuffing • J Discard Erroneous Packets Data Block Generation * Discard Erroneous RS-DBs Reed-Solomon Encoding Reed-Solomon Decoding Scrambling Descrambling Insert Control Flags FCTS Control Flag Extraction Received Bit Sequence (a) ( P H Y Layer )• (b) Figure 2.9 Flow chart for (a) procedure of FCTS generation at the M D B S ; (b) procedure of L P D U reconstruction at the M-ES involves error detection and correction. Those R S - D B s that contains too many errors, i.e. more than 8 codewords in a block are in error, are identified and discarded at the output of the decoding process. B y identifying the flags delimiting the L P D U s , the erroneous L P D U s (packets) can be identified from the sequence of the correct data blocks. Since the M A C layer is not responsible for maintaining the quality of service, i.e. it is not responsible for erroneous packet retransmission, those erroneous packets w i l l be discarded. Only the correct ones are kept for final processing, including the delimit ing flag extraction and de-zero-stuffing. The resulting L P D U s are then passed to the L L C layer for further processing. Chapter 2 CDPD System Model 26 2.3.3 Medium Access Algorithm The reverse channel is shared by a number of M - E S s within a ce l l . In order to avoid collisions, the M - E S who wants to establish connection to the M D B S has to follow a certain type of rule defined by an medium access algorithm. The algorithm employed in the C D P D system is called Digital Sense Multiple Access with Collision Detection ( D S M A / C D ) , which regulates the procedure of M - E S s accessing the reverse channel. This algorithm is similar to the Carrier Sense M u l t i p l e Access with Co l l i s i on Detection ( C S M A / C D ) used in I E E E 802.3 L A N s such as Ethernet. However the M - E S s cannot sense the reverse channel directly, because the reverse channel in C D P D employs different reception and transmission frequency band. In the D S M A / C D the M - E S senses the Busy/Idle flag which is transmitted periodically in the forward channel. When the reverse channel is idle, it starts transmission until the B l o c k Decode Status F lag transmitted in the forward channel signals the M - E S a decoding failure, which is caused either by col l is ion or channel burst errors. Then the transmitting M - E S (or M - E S s ) attempts to regain access to the channel after an appropriately selected exponential backoff delay. 2.4 Logic Link Layer and ARQ Procedure In a point-to-point information transfer, the C D P D can provide reliable communication through acknowledged operation, with which the network layer information is transmitted in frames that are acknowledged at the L L C layer. This layer employs the M D L P protocol, which utilizes the services of the M A C layer to provide access to the physical channel and transparent transfer of link-layer frames between data link layer entities. The M D L P implemented in an M - E S communicates with a peer M D L P located in its serving M D - I S . The M D B S functions primarily as a data link relay between an M D - I S and M - E S s except in some cases where the M D B S may also operate in the L L C layer [1]. Chapter 2 CDPD System Model 27 To ensure re l iable communica t ion between M D L P peers, an A R Q mechanism is employed as part of the M D L P protocol to perform tasks such as identifying missing frames and sending requests for their retransmission. The details of the A R Q procedure wi l l be discussed in Section 2.4.2, following the Section 2.4.1 where we w i l l provide the descriptions of the frame structure in the L L C layer. 2.4.1 LLC Layer Frame Structure Information transfer between peer L L C entities is carried out through a number of L ink Protocol Data Units (LPDUs) . A general structure of the L P D U s is given in F ig . 2.10. The frame consists of three fields, namely, the Address Field, Control Field, and the Information Field. The Address F i e l d is 1-4 octet long, which contains information to specify the virtual data l ink channel. The address information includes a Temporary Equipment Identifier (TEI). B y assigning different values to the TEI , the data link connection can be specified as either point-to-point or broadcast. For point-to-point connection, the TEI is used as the M - E S data link address, which is typically assigned to each M - E S uniquely. Address Meld (1-4 oc'U't.s) Control Field (1-2 octets) Information Field (0-130 octets) Figure 2.10 Structure of the L L C frames Chapter 2 CDPD System Model 28 The Control F i e ld is 1-2 octets long. It contains the frame type identifier as wel l as sequence numbers where applicable. There are three generic types of frames: numbered informa-tion (I) frames, supervisory (S) frames and unnumbered (U) frames. The I-frames are used to carry acknowledged information transfer. The S-frames are used to perform data link supervisory control functions such as acknowledge I-frames, or request retransmission of I-frames. The U -frames are used to provide additional control functions and to carry unacknowledged information transfer. The information field is optional. Some types of frames, for example, S-frames, do not require information field. The size of this field varies from 0 octet to 130 octets [1]. 2.4.2 ARQ Procedure In acknowledged transmission mode, The M D L P is responsible for identifying and requesting retransmission of the missing data frames. This operation is referred to as the A R Q procedures. A t the receiving side, the L P D U s are reconstructed with the R S - D B s decoded at the M A C layer. These frames containing uncorrectable errors are discarded while the recovered ones are forwarded to the L L C layer, where the M D L P identifies the missing frames by checking their sequence numbers carried in the control field of the L P D U s . In the case of receiving an out-of-sequence I-frame, or the expiry of a retransmission timer, the receiving side wi l l send an S- frame to its peer L L C entity requesting for retransmission. The information transfer on the data link is based on a sliding-window (with a window size of 128 frames) protocol with a Selective-Reject (S-REJ) A R Q scheme for error recovery. With S-REJ A R Q , the receiving side sends a negative acknowledgment ( N A K ) for each missing I-frame. The only frames retransmitted are those that receive a N A K or which time out. It is more efficient than other conventional A R Q approaches such as stop-and-wait A R Q and go-back-N Chapter 2 CDPD System Model 29 A R Q , since it minimizes the amount of retransmission [29]. 2.5 Computer Simulation Model and Parameters A general block diagram of our computer simulation system considered in this thesis is given in F i g . 2.11. It consists of three sub-systems, namely, one M D B S , the communication channel, and one M - E S . The M D B S continuously transmits a sequence of data frames through the forward mobile communication channel. The M - E S receives these frames and tries to decode them. Because the system performance study is focused on the forward channel, the reverse channel is assumed ideal, such that there is no transmission failure on the reverse channel and the transmission time is ignored. MDBS Channel M-ES Traffic Generator I LPDUs M A C Processor FCTS G M S K Modulator : • ^JError Counter I LPDUs Packet Reconstruction Coherent Differential Detector Detector Rayleigh Fading + A W G N Figure 2.11 Block diagram of computer simulation model 2.5.1 MDBS Model The traffic generator at the M D B S generates a number of L P D U s , which are transformed Chapter 2 CDPD System Model 30 into the F C T S by the M A C processor. The function of the M A C processor has been detailed in Section 2.3.1. Then the transmission sequence is modulated by a G M S K modulator with the normalized pre-modulation filter bandwidth BtT= 0.5. Since in practice the lengths of the L P D U s generated from the L L C layer are dynamically dependent on the types of the frames and the lengths of the message source from the upper layer, the frame lengths can be considered as random. For simplicity purposes, we choose the following three typical lengths, which wi l l be randomly picked by the traffic generator: (1) Small Packet (SP) with length of 6 octets or 48 bits, corresponding to the length of a supervisory frame, e.g. an acknowledgment frame; (2) Medium Packet (MP) with length of 71 octets or 568 bits, corresponding to the aver-age frame length, i.e. the mean value of the lengths of a Small Packet and a Large Packet; (3) Large Packet (LP) with length of 136 octets or 1088 bits, corresponding to the default data frame length [1], which is also the maximum length allowed for an L P D U . For the sake of simplicity, the three kinds of frames are randomly chosen with equal probability, i.e. each with probability of 1/3. 2.5.2 Communication Channel Model The modulated G M S K signal is passed through the communication channel which we have considered in this thesis to be a narrowband land-mobile Rayleigh fading channel with a maximum Doppler shift fD. The statistical properties of the channel have been detailed in Section 2.2.2. In this thesis where slow fading is considered, the following three values of the maximum Chapter 2 CDPD System Model 31 Doppler sh i f t / D have been chosen: 20Hz, 40Hz and 80Hz. Since the bit rate of a C D P D air link is 19.2 kbps, these values correspond to the normalized Doppler shift bandwidth fDT of approxi-mately 0.001, 0.002, and 0.004, respectively. The three values oifD represent the typical mobile moving speeds, e.g. assuming a carrier frequency of 800 M H z , the three Doppler frequencies correspond to 25, 50, and 100 km/hour respectively. A l so , as previously mentioned, besides Rayleigh fading, the transmitted signal is also corrupted by the A W G N , with a 2-sided power spectral density of NJ2. 2.5.3 M-ES Model As it shown in F ig . 2.11, the channel-corrupted signal is detected at the mobile station by either a differential detector or a coherent detector. A s previously mentioned, we wi l l consider both types of detectors into account in order to illustrate the differences in terms of their perfor-mances under various channel conditions. The detected bit sequence is then passed through a number of processes that perform reconstruction of the correct ly received packets. The reconstruction operations have been depicted in Section 2.3.2. The function of the Error Counter is to not only count the number of erroneous bits, R S - D B s , and L P D U s , but also to measure the amount of information data successfully received at the M - E S . The detailed performance consid-erations wi l l be presented in the next chapter. 2.6 Summary In this chapter the C D P D system model has been described. Descriptions of lower layer protocol sets, including M D L P which operates at the L L C layer, and M A C protocol which operates on the medium access layer, have been provided. The physical layer configuration, including G M S K modulation/demodulation scheme, and the mobile radio channel model, has Chapter! CDPD System Model 32 also been addressed. The functions of the C D P D communication units, such as M D B S , M D - I S , and M - E S are given, and how the transmission sequence is formed in the forward channel are detailed in this chapter. Chapter 3 Performance Analysis and Evaluation 33 Chapter 3 Performance Analysis and Evaluation 3.1 Introduction Given the system model presented in the previous chapter, the main objective of this thesis is to study the performance of the pre-described C D P D system in terms of the B L E R , the P E R , and the M A C layer throughput, over various channel conditions and receiver types. Hence, in this chapter we w i l l investigate the performance of B L E R and P E R and their relations. We also identify a source of performance degradation, namely, the correct but unusable data ( C U D ) , which is caused by the variety of the packet lengths and the alignment of the packets and R S -blocks at the M A C layer. The organization of this chapter is as follows. After this introduction, we wi l l describe the source of degradation, i.e. the C U D in Section 3.2. Then the relations between the B L E R and P E R wi l l be analyzed in Section 3.3, followed by the derivation of the throughput expression in Section 3.4. Numerical results of computer simulations and discussions w i l l be presented in Section 3.5. Finally, a summary of the chapter appears in Section 3.6. 3.2 Correct but Unusable Data One of the major problems addressed in this thesis is the fact that i f one R S block is destroyed, i.e. it is not recovered by the M A C error correction scheme because it entails a large number of errors which cannot be corrected by the available coding scheme, it causes one or more packets to be discarded as unusable. A s an example, let us consider the scenario depicted in F ig . 3.1, the destroyed RS block, B 4 , happens to contain data from two packets, P3 and P4. Both these packets w i l l be discarded at the M A C layer even though only a small fraction of them is unrecov-Chapter 3 Performance Analysis and Evaluation 34 B l , B2 B3 , M , B5 , B6 i i i i / \ i i i • I i i i i i PI !g P2 E x \ 1 X X E / \ 1 P5 E i i i i i i i i i i f x i i i • i i i Correct but Corrupted Correct but Unusable Data Data Unusable Data Figure 3.1 Generation of correct but unusable data (CUD) X : Destroyed block erable. This means that the receiver discards data from additional R S blocks that are not corrupted. In a reliable transmission link with A R Q employed, the discarded packets containing the portion of data that is correct but unusable would have to be retransmitted. Evidently, this fact represents a source of inefficiency. In general, we may argue that a percentage of data arriving at the receiver without being destroyed is discarded as unusable. We refer to this data as correct but unusable data ( C U D ) . To demonstrate the effect of C U D , we define the percentage of C U D as N Tl = 1 0 0 % - i 5 > * (3.1) k = 1 where N is the total number of transmitted bits, ek = 1 i f the k-th. bit belongs to the C U D data, and ek = 0 otherwise. The relations between the percentage T| and the energy per bit-to-noise ratio E// N0 can be illustrated in F ig . 3.2. This graph is derived through computer simulation using the Chapter 3 Performance Analysis and Evaluation 35 model depicted in F i g . 2.11, where a sequence of packets are transmitted through the A W G N channel and received by a coherent detector. As expected, C U D is very low, e.g. less than 10%, at very small and very high values of E\JNQ. During very small values, almost all received R S - D B s contain a large number of errors and cannot be recovered; hence undestroyed data is close to zero. On the other hand, during high values, almost all R S - D B s are correctly received and no blocks are discarded, hence no useless data exist. However, it is interesting to note that, even in the A W G N channe l , the percentage of C U D approximates a peak between 4 0 % and 4 5 % when Eb/N0 = 3.5 dB . Equivalently, this means that nearly 45% of the received data is discarded by the receiver although this data is not destroyed. Clearly, this represents a significant redundancy and this is a source of performance degradation. 1 1.5 2 2.5 3 3.5 4 4.5 5 5.5 6 Eb/No (dB) Figure 3.2 Percentage of CUD in the AWGN channel with coherent detection Chapter 3 Performance Analysis and Evaluation 36 A s w i l l be presented in Section 3.5.2, simulation results of the percentages for the Rayleigh fading channel have also demonstrated similar inefficiency by 40% to 45% of the C U D . To effectively improve the performance of C D P D , it is mandatory to mitigate or even eliminate the above problem. In doing so, we have proposed a new scheme that effectively overcomes the aforementioned deficiencies, by means of an A R Q protocol that operates at the M A C layer. A detailed presentation and analysis of this protocol w i l l be given in Chapter 4. 3.3 Block and Packet Error Performance In this section we address the relation between the B L E R and the P E R . It is instructive to consider this relationship in order to study how the packet error process is affected by the underly-ing block error process. A simple theoretical performance analysis with an A W G N channel is considered first. Let us consider the probability a packet to be destroyed, i.e. the probability one or more blocks containing data from that packet to entail a large number of errors and be unrecoverable at the receiver. Let PP denote the probability one data packet to be destroyed and let PB denote the probability one block to be destroyed. Given our simulation parameters, i.e. the length of a SP is 48 bits, the length of an M P is 568 bits, and the length of an L P is 1088 bits, we have: i) A Small Packet can occupy either 1 or 2 blocks, ii) A Medium Packet can occupy either 3 or 4 blocks, and iii) A Large Packet can occupy either 4 or 5 blocks. Therefore, the probability of one SP to be destroyed is given by: Ps = P r o b { X e sp\X0i S P J } - P r o b { X 0 s p ,} + P r o b { X g SP\X0> SP2} • Pmb{X0 s p > 2 } (3.2) where XeSP represents the event that an SP is destroyed, and X o S P n represents the event that an Chapter 3 Performance Analysis and Evaluation . 37 SP occupies n block(s), n = 1,2, 3,... . Considering that for a memoryless channel, such as the A W G N channel, Prob{XeiSP\X0tSP>n} = \-(l-PB)n n = 1 ,2 ,3 , . . . (3.3) where PB is the probability a block is destroyed, and given the 274 bits packet length, Eq . (3.2) can be rewritten as Ps=PB 1 + [ 1 - ( 1 - P B ) 2 ] - ^ . (3.4) Likewise, the equivalent probabilities for a Medium Packet, PM, and a Large Packet, PL, can be respectively written as: PM = Prob{XeMP\Xo^3} • P r o b { X 0 M P 3 } + (3.5) P r o b { Xe, MP | X o , MP, 4 } P r o b { X o , MP, 4 > = n - ( i - p s ) 3 ] - | ^ + [ i - ( i - p 5 ) 4 ] - ^ and PL = P r o b { X e ) L p X0t L P A } - P r o b { Z 0 > LpA} + (3.6) Prob{XeLP\XoLP5}Pwb{XoLP5} = [l-(l-PB)4]-A + [ 1 - ( 1 - P B ) 5 ] - ^ Thus, the probability a packet to be destroyed is given by, 1 1 1 pp ~ 2Ps + + ^ L - (3.7) Chapter 3 Performance Analysis and Evaluation 38 Substituting Eqs. (3.4)-(3.6) into Eq . (3.7), yields the expression of PP as a function of PB 1 822 ( 2 5 2 3 P B - 3630Pg + 3017Pg - 1353PJ + 265P 5 g ) . (3.8) The curve corresponding to Eq. (3.8) is illustrated in Fig . 3.3 (solid line), which is verified by the simulation results shown in circle points. For comparison purposes, we have included the straight dotted line corresponding to the ideal situation where PP and PB are equal (i.e. each block contains only one packet) and therefore a block loss introduces only one packet loss, which is the minimum. It is interesting to note that the probability a packet to be destroyed, Pp, increases rapidly as PB increases. For example, note that when PB is about 0.1, Pp is almost 0.3, which is considered unacceptable in nearly every operating scenario. In addition, PP is always larger than PB. This is because a block loss always causes one or more packet loss. Therefore, a strong block correction mechanism is necessary in order to keep PP quite small so that for satisfactory perfor-mance for the forward channel can be achieved. Let us now study PP and PB with respect to the communications channel quality, typically measured as a function of E}/N0. It is well-known that an (N,K) Reed-Solomon block is encoded with N codewords including K codewords of information part and (N-K) codewords of parity-check part [33]. Each codeword is /-bit long. For the A W G N channel the probability of an /-bit codeword in error is A n ideal RS code is capable of correcting up to t - (N-K)/2 codewords, therefore, the probability of an RS block is destroyed can be written as [35] P = 1 - ( 1 - P ) . ecw V 1 e> (3.9) Chapter 3 Performance Analysis and Evaluation 39 Analytical O Simulated • Proposed 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 Probability of Blocks in Error (PB) Figure 3.3 Probability of a packet in error (P P) versus Probability of a block in error (P B) k = 0 N-k (3.10) where CN -Nl (N-k)\k\ (3.11) Substituting Eq . (3.9) into Eq . (3.10), PB can be expressed with the bit error probability Pe as N i k l(N-k) (3.12) k = 0 Chapter 3 Performance Analysis and Evaluation 40 From [16], the bit error probability of G M S K with coherent detection can be approxi-mated as a function of y, which denotes the Ef/Na, in the A W G N environment. P e (y) = - erfc(Vay) (3.13) where erfc( • ) is the complementary error function given by erfc(x) = — exp(-r )dt 2 r (3.14) and a is a constant parameter varied with different BtT products, a can be estimated as 0.84 according to our observation of the simulation results over various values of a . Therefore, substi-tuting Eq . (3.13) into Eq . (3.12) yields the expression of the PB in terms of y. A n d the expression of the packet error probability PP in terms of yean be easily obtained by substituting the resulting expression into Eq . (3.8). 3.4 Throughput Performance In order to study the performance of the forward channel with demands to accommodate heavy data load, we focus our investigation on the throughput of the information data rather than the control overhead at the M A C layer. We wi l l define the throughput as the average number of information bits transmitted successfully during one bit time. In other words, it can be calculated by dividing the total number of information bits to be transmitted, N{, by the total number of bits actually transmitted over the channel NTotai, i.e. S MAC ~ (3.15) Total Chapter 3 Performance Analysis and Evaluation 41 In order to derive a simple expression, let us assume the packets have equal length Lp, then 7Y; = n(Lp - Hp), where Hp is the header length, and n is the number of packets to be transmit-ted. Because of the employment of A R Q , the L L C entity at the receiving side w i l l continue to send requests to its peer for retransmission of the discarded packet, until it is correctly received or the retransmission counter has reached a certain number. Hence, the total number of transmitted bits NTotai comprises the number of bits to be transmitted, plus the number of bits retransmitted. Assume the packet error rate is Pp, and the maximum number of retransmissions is set to NR, then Total ~ nLp + nLpPp + nLpPp+ ••• + nLpP nLp{\ -PpR) (3.16) Therefore, Eq . (3.15) can be rewritten as 5 MAC ~ • R (3.17) where, R = (3.18) If the packet error probability PP is small and NR is large, then the term PpR can be ignored, and thus the throughput can be approximated as SMAC = (1 ~pp)R- (3.19) Chapter 3 Performance Analysis and Evaluation 42 As shown in Eq . (3.8), PP is also a function of PB, which, as given by Eq . (3.12), is also a function of the bit error probability Pe. Therefore, the throughput can be estimated by the channel bit error rate. As an example, suppose that the packets are transmitted in their default length, i.e. 1,088 bits per packet, the relationship between PP and PB in the A W G N channel is shown in E q . (3.6), then the corresponding expression for the throughput is, where LP is 1,088 bits, Hp is 48 bits, and PB is expressed in Eq. (3.12). 3.5 Numerical Results and Discussion 3.5.1 BLERs and PERs Fig . 3.4 shows that for an A W G N channel with coherent detection, our computer simula-tion results of B L E R and P E R as a function of E^INg match the curves derived from Eq . (3.12) and (3.8) respectively. According to [1], the parameters in Eq . (3.12) are N = 63, K = 47, t = 8, and / = 6. The same figure also shows that the difference between the B L E R and the P E R is about 0.25-0.5 dB. For example, to achieve 1% block error rate the required Eb/N0 is 4.25 dB, while it requires 4.6 dB to achieve 1% packet error rate. However, the performance difference in a fading environment tends to be much more significant. Using the computer simulation model described in Chapter 2, below we present our simulation results generated in a slow Rayleigh fading channel with several Doppler shift values for a 1-bit differential receiver. The simulation for B L E R / P E R generation has tested from a minimum of 2,072 to a maximum of 576,000 blocks. Each block is 368 bits long and each bit is S MAC ~ (3.20) Chapter 3 Performance Analysis and Evaluation 43 2 2.5 3 3.5 4 4.5 5 5.5 6 Eb/No (dB) Figure 3.4 B L E R and PER in the A W G N channel Chapter 3 Performance Analysis and Evaluation 44 sampled at eight samples/bit. The simulation results were obtained by means of Monte Carlo error counting techniques. In order to have accurate performance results for all simulated B L E R / P E R values, at least 100 erroneous blocks were counted for B L E R from 10"1 to 10"3 and at least 50 erroneous blocks for B L E R of 10" 4. The confidence level of at least 90% is obtained for all simulation results, with the confidence intervals listed in Table 3.1 for each B L E R . The intervals are calculated by using the formula in [30] (Eq. (9)). BLER Number of Blocks Tested 90% Confidence Interval '10-' 2,072 (9.22E-2, 1.08E-1) 10 - 2 8,240 (8.80E-3, 1.14E-2) io- 3 111,950 (8.96E-4, 1.12E-3) io- 4 576,000 (8.58E-5, 1.17E-4) Table 3.1 The 90% confidence interval for each B L E R Figs. 3.5-3.7 illustrate the B L E R and P E R performance versus Ej/N0 with 1-bit differen-tial detection for Doppler shift /o=20 H z , 40 H z and 80 H z , respectively. For comparison purposes, we also consider coherent detection with ideal carrier recovery 3 . Compared to the results for ideal coherent detection, the results for differential detection are only approximately 5 dB worse, which implies that differential detection is relatively robust in the fading environment. A s it shown in terms of Eb/Na, the B L E R declines faster than the P E R , which is worse than the B L E R about 2.5 to 5 dB with various Doppler shifts. It is easy to observe that with Rayleigh fading channel the P E R is almost unacceptable for a wide range of E)JN0. An ideal carrier recovery means that the carrier signal is correctly extracted at the receiver. However, it must be emphasized that this is an ideal case which is practically impossible. It is used as an upper bound for performance comparison purposes. Chapter 3 Performance Analysis and Evaluation 45 Figure 3.5 B L E R and PER with differential detection in the Rayleigh fading channel w i t h / D =20 Hz Chapter 3 Performance Analysis and Evaluation 46 5 10 15 20 25 30 35 40 Eb/No (dB) Figure 3.6 B L E R and PER with differential detection in the Rayleigh fading channel w i t h / D =40 Hz Chapter 3 Performance Analysis and Evaluation 47 Figure 3.7 B L E R and PER with differential detection in the Rayleigh fading channel w i t h / D =80 Hz Chapter 3 Performance Analysis and Evaluation 48 B y comparing the performance evaluation results presented in Figs. 3.5-3.7, we also found it interesting that the impact of different Doppler shift values on the block/packet error performance is different. F ig . 3.8 gives a more clear view of the B L E R / P E R for different fDs. A s it shown, the B L E R / P E R decreases as the Doppler shift fp increases from 20 H z to 80 H z . For example, when the EbIN0 is approximately 26 dB, the B L E R is around 10" 2 w h e n / D = 20 H z , while it is around 10 when fD = 80 Hz . Another point of view of this phenomenon is to look at the bit error rates with the employment of error correction codes for different Doppler shifts, i.e. the estimated probability of bits in error after the error correction. A s it shown in F i g . 3.9, the B E R f o r / D = 80 H z is as much as 5 dB better than the B E R f o r / D = 20 H z as the Eb/Na is large. This applies for both differential detection and the ideal coherent detection. The phenomenon can be justified by the argument that the error correction scheme employed in C D P D performs better in a less slower fading environment. This is because of the characteristics of the fading channel and the error correction scheme. In a slow fading environment, the long duration of deep fades causes some blocks to contain a large number of errors while others contain none (or a lot fewer) errors. The packet containing these large number of errors w i l l have higher probability to be uncorrectable. However, this is not the case for less slower fading, where all blocks encounter errors but the number is relatively smaller. Hence, the error correction scheme is more efficient when fD is large due to the larger spread of errors. For example, wi th R S - c o d i n g scheme employed in C D P D system, an RS-block wi l l be uncorrectable i f it contains less than 8 erroneous codewords. It means the number of erroneous bits has to be large enough and spread enough to cover 8 codewords. Assume Eb/N0 = 20dB, i f / D = 20Hz, there are approximately 91.5% blocks containing 8 or less erroneous codewords, and hence they are correctable. I f / D =80Hz , however, Chapter 3 Performance Analysis and Evaluation Figure 3.8 Comparison of BLERs and PERs with different Doppler shift frequencies with differential detection in the Rayleigh fading channel, (a) B L E R . (b) PER. Chapter 3 Performance Analysis and Evaluation 50 Figure 3.9 BER with error correction coding in the Rayleigh fading channel. Chapter 3 Performance Analysis and Evaluation 51 there are approximately 96.5% blocks which are correctable. On the other hand, when the fading becomes faster, i.e. when/^, increases to a certain large value, or a threshold, the number of errors contained in the blocks w i l l exceed the error correction capability, and the block error perfor-mance w i l l start to decline. Our simulation result indicates that w h e n / D reaches 400-450Hz, the B L E R / P E R starts to increase and the degradation becomes very significant w h e n / ^ is larger than about 500 Hz . 3.5.2 CUD The percentage of C U D with differential detection in the fading environment is presented in F ig . 3.10, where three Doppler shifts = 20 Hz , 40 Hz , and 80 H z are considered. Analogous to the results in A W G N channel, the three percentage curves tend to be zero in very low and very high ranges of EbINQs, but the peaks of the curves are approximately between 36%~43%. The percentages for fD = 20Hz has the highest value of 43%, while the peak forfD = 80Hz is almost 36%. Compared to the case for A W G N channel, the curves for fading channel cover a much wider range of EbINQs. This implies that over a relatively wide range of EfJN0s the system is working in an inefficient manner. For example, the percentage of C U D is over 20% for nearly 10-dB range of Efr/NpS. These curves are generated with the packet length configurations described in Chapter 2, i.e. test data traffic contains SP, M P and L P with equal probability. Although packet length is a parameter affecting the amount of C U D , according to our experiments, the C U D with different settings of packet sizes varying from the minimum to the maximum L P D U lengths, exhibits similar percentage peaks to those shown in Fig . 3.10. Evidently, it is an source of inefficiency that requires improvements. Comparing the peak values of the C U D with the three Doppler shifts, we also found it Chapter 3 Performance Analysis and Evaluation 52 Figure 3.10 Percentage of C U D with differential detection in the Rayleigh fading channel. Chapter 3 Performance Analysis and Evaluation 53 interesting that, although the difference between the three fas are significant, i.e. 80 H z is four times of 20 Hz , the values of the C U D do not show remarkable difference. For example, the peak C U D percentage with fD = 20 H z is about 43%, while that w i t h / D = 80 H z differs only 7% as 36%. Accord ing to the observation we can argue that the differential detection in a Rayleigh fading channel is relatively insensitive to the change of the Doppler shifts. 3.5.3 Throughput In Section 3.4, we have discussed the relation between the throughput and the B L E R , and further the relation between the throughput and the B E R . Eq . (3.20) has shown an expression of the throughput as a function of PB, given that the packets are transmitted in their default lengths, i.e. 1,088 bits per packet. Substituting E q . (3.12) into E q . (3.20), the throughput can be represented as a function of the B E R , the plot of which is illustrated in F ig . 3.11. A s confirmed by the simulation results, the throughput increases as the B E R decreases, and it approaches zero as the B E R increases to above 3.0E-2, whereas it approaches its maximum value when the B E R drops below 7.0E-3. Due to the packet overhead, the throughput can never be 1, even i f there is no packet loss at all . Instead, the maximum throughput, corresponding to the ideal transmission, i.e. Pp = 0, can be computed as (Lp - Hp)/Lp = 0.96. Let us consider the throughput in terms of the channel conditions, i.e. as a function of the Ej/N0. Simulation results have shown that similar curves can be derived for the Rayleigh fading channel with random packet lengths. F i g . 3.12 illustrates the throughputs versus the E[/N0 in Rayleigh channel with Doppler shifts fD = 20 Hz , 40 Hz , and 80 Hz . The solid lines corresponds to the results for differential detection, and the dashed lines show that the throughput for ideal coherent detection is as much as 30% more than the differential detection. Note that the results for Chapter 3 Performance Analysis and Evaluation 54 Figure 3.11 Throughput versus B E R with coherent detection in the A W G N channel, where the packets are transmitted in their default lengths. Chapter 3 Performance Analysis and Evaluation 55 10 15 20 25 30 35 Eb/No (dB) Figure 3.12 Throughput versus Eb/No in the Rayleigh fading channel. Chapter 3 Performance Analysis and Evaluation 56 ideal coherent detection is an unrealistic case and should be only considered as the throughput upper bound for comparison purposes. For all the three Doppler shifts, the throughputs increase as the Ej/N0 increases. The throughputs for smaller Doppler shifts are slightly less than those for larger Doppler shifts when the Ef/Na is between 14 and 30 dB. However, as the Et/N0 increases to a very large value, e.g. larger than 35 dB, the curves for three Doppler shifts tend to merge at approximately 0.92, which is a little less than the throughput with fixed packet length (0.96) because the transmission of fixed default-length packets yields more throughput than the transmission of unfixed random-length packets. 3.6 Summary In this chapter we have investigated analytically and by means of computer simulations, the system performance in terms of the RS-block error rate, the packet error rate, and the through-put at the M A C layer. The relationship between the B L E R and the P E R is analyzed and the C U D is identified as a source of performance inefficiency. The percentage of C U D has been investi-gated by means of computer simulation. This chapter has also presented the analytical results of the B L E R , P E R , and the throughput in the A W G N channel, and the corresponding simulation results for both coherent and differential detector in A W G N channel and a slow Rayleigh fading channel. It has been realized through the performance study that the system can be improved i f the source of degradation can be eliminated. Chapter 4 MAC-ARQ Protocol 57 Chapter 4 MAC-ARQ Protocol 4.1 Introduction As discussed in the previous chapter, it is the correct but useless data ( C U D ) that causes the degradation of the C D P D throughput performance. In order to mitigate the problem, in this chapter we w i l l propose a new scheme that effectively overcomes the aforementioned deficien-cies. The proposed scheme employs an A R Q protocol that operates at the M A C layer, i.e. a protocol that requests retransmission of the erroneous data blocks instead of L P D U s at the L L C layer. It w i l l be referred to as the M A C - A R Q protocol. In this way, only the unrecoverable information is retransmitted and no C U D data arises. A similar approach is applied in the General Packet Radio Service ( G P R S ) [31][32], where the Radio L i n k Control ( R L C ) protocol that operates below the data link layer handles the block transmission and correction. The organization of this chapter is as follows. After this introduction, the description and performance evaluation for the new protocol w i l l be presented in Section 4.2, where both its advantages and performance tradeoff w i l l be discussed. In the next section, Section 4.3, we w i l l propose an adaptive scheme which maximizes the throughput over the conventional and the M A C - A R Q scheme. Finally, a summary w i l l be contained in Section 4.4. 4.2 Description and Performance Evaluation of the MAC-ARQ Protocol In Chapter 3, it was mentioned that for the C D P D system, conventional A R Q is operating in the L L C layer. It only provides retransmission of L P D U s in this layer. Unl ike conventional A R Q , M A C - A R Q is an auto-retransmission scheme operating in the M A C layer, by providing retransmission of RS-blocks in M A C layer, hence avoids retransmission of the L P D U s . A s a consequence, the effect of the C U D could be eliminated. For the retransmission, each block needs Chapter 4 MAC-ARQ Protocol 58 From L L C Layer I * to. E _E Halts Flags 1 4 -t*rM Continuous Frame Data Bit Stream 274-// B bits / 274-// Bbits ^ Data Block / i ' i i i i i 21A-HB bits / , 274-// f ibits i i / \ i \ i \ i \ 274-//,, bits Data 96 bits Parity l l l l l l l i i p : ; : Data 96 bits Parity V*. Sequence of RS-blocks RS-DB 378 bits RS-DB 378 bits Color Code 8 bits To P H Y Layer Figure 4.1 Data transmission procedures in the forward channel, to contain necessary information for its destination and its sequence number. The description of the M A C - A R Q is as follows. A s illustrated in F i g . 4.1, the sequence of packets formed by the L P D U s is segmented into (274 - HB) bits each, where HB is the length of the header to be attached to each data block. Then each segment is prefixed by a block header (HB), together with the 8-bit Color Code, yielding a 282-bit data block. The data block is thereafter RS encoded and transmitted to the physical layer. The block header contains the destination address(s) and the block sequence number to perform the A R Q operations. The destination address(s) identifies the logic link connection(s) where this M A C - b l o c k contains data from. Since a block may contain data from more than one logic link connection, the address field needs to contain addresses for all the connections. Therefore, an implementation dependent algorithm which performs address Chapter 4 MAC-ARQ Protocol 59 compression and mapping can be applied to ensure the M E S side to be able to identify the data block destined to itself from this address field. The receiving M E S identifies the sequence numbers of the blocks which fail decoding, and sends request(s) via the reverse channel for the retransmission of these blocks, while queues the correctly received blocks which have not complete an L P D U . Upon receipt of the retransmitted blocks, the M E S assembles an L P D U with these blocks as well as the queued blocks, and forward it up to the L L C layer. Therefore, at the L L C layer, there wi l l be no missing packets and thereby no retransmission involved. Since all the erroneous data blocks are corrected at the M A C layer, the probability of a packet in error wi l l be zero. Referring to the simulation results for B L E R s and PERs in the fading channel, e.g. Figs. 3.5-3.7, the up to 5-dB of performance degradation between the P E R and the B L E R is eliminated by the M A C - A R Q protocol. The penalty we pay for the performance improvement this new protocol offers, is that extra redundancy needs to be embedded into the forward channel, i.e. the header of each block, and therefore the performance is expected to decline under very good channel conditions. Follow-ing Eq . (3.15), the M A C layer throughput for the M A C - A R Q protocol is S' - N ' - N r o t a l s (4U 0 MAC ~ A r ~ a t . ^MAC \^A) y v Total y v Total where N'Total is the actual number of bits transmitted for M A C - A R Q . Similarly to the derivation of Eq . (3.19), the ratio NTotal/N'Total can be expressed as N Total N'Total = (l-PB)R', (4.2) Chapter 4 MAC-ARQ Protocol 60 where Lo — H R R' = ——- (4.3) B where LB is 274 bits, and HB, containing the necessary destination address and block sequence number, can be sufficiently assumed as three octets or 24 bits in our system. From Eqs. (3.19) and (4.2), E q (4.1) can now be expressed as S'MAC = RR\\-PP){\-PB) . (4.4) Since the M A C - A R Q protocol has ensured every L P D U can be successfully decoded, i.e. Pp=0, Eq. (4.4) can be rewritten as S'MAC = RR'(\-PB) . (4.5) Substituting E q . (3.12) into Eq . (4.5) yields the throughput expression in terms of the bit error probability, and this is plotted in F ig . 4.2. The dashed line in F ig . 4.2 illustrates the throughput versus the Pe of the new scheme in an A W G N channel, where the packets are transmitted only in their default lengths. A s compared to the conventional scheme, the M A C - A R Q scheme has up to 45% higher throughput when Pe is larger than the cross point 1.15E-2, while the conventional scheme outperforms the new one by nearly 10% when Pe is very small, i.e. after Pe crosses the threshold. The s imulat ion performance evaluation results for the throughput versus E[/N0 in Rayle igh fading channels are presented in F i g . 4.3. The results reflect the throughput while packets are transmitted in random lengths. For comparison purposes, the results for the conven-Figure 4.2 Throughput versus BER with coherent detection in the A W G N channel, where the packets are transmitted in their default lengths. Chapter 4 MAC-ARQ Protocol 62 10 15 20 25 30 35 E b / N o (dB) Figure 4.3 Throughput versus Ef/N0 with differential detection in Rayleigh fading channel, where the packets are transmitted in their random lengths. Chapter 4 MAC-ARQ Protocol 63 tional scheme are also included. A s it shown in the figure, the M A C - A R Q scheme shows over 30% increase of the throughput as Eb/N0 is low (e.g. E(/N0 < 15 dB) , while exhibits approxi-mately 10% degradation as Ef/Na is large (e.g. E//N0 > 30 dB). The cross points of these two schemes are ranged within 21-23 dB. As discussed in the previous chapter, the M A C throughput can be estimated by the channel B E R performance. Figs. 4.4-4.6 illustrate the simulation results for the throughput versus bit error rate in Rayleigh fading channels. Similar Pe thresholds can be identified in these figures. Let the curve forfD = 80 H z be an example, when Pe is larger than the threshold, where Pe>threshold = 7.4E-3, the M A C - A R Q scheme has up to 35% higher throughput than the conventional scheme. Nevertheless, the new scheme has about 10% lower throughput than the conventional one when Pe is smaller than the threshold. The throughputs for other Doppler shifts vary but they exhibit similar thresholds. The observed thresholds are listed in Table 4.1 below. / » ( H z ) BER Threshold 20 5.0E-3 IlllSllii'llSI"^0:' ; .  6.5E-3 7.4E-3 Table 4.1 Observed BER thresholds for various Doppler shifts 4.3 The Adaptive Scheme In this section we wi l l discuss an Adaptive scheme which can make further performance improvements, by means of dynamically enabling the A R Q operation at either M A C layer or the L L C layer. Similar to some previous work concerning adaptive A R Q scheme, such as [37][38], where the blocks are transmitted in various sizes as the changing of the channel, the adaptive A R Q protocol that we are proposing, wi l l simply switch the operations according to the channel Chapter 4 MAC-ARQ Protocol 64 Figure 4.4 Throughput versus BER with differential detection in Rayleigh fading channel (fD=20Hz), where the packets are transmitted in their random lengths. Chapter 4 MAC-ARQ Protocol 65 Figure 4.5 Throughput versus BER with differential detection in Rayleigh fading channel (/D=40Hz), where the packets are transmitted in their random lengths. Chapter 4 MAC-ARQ Protocol 66 10"1 10~2 10"3 Bit Error Rate (BER) Figure 4.6 Throughput versus BER with differential detection in Rayleigh fading channel (/D=80Hz), where the packets are transmitted in their random lengths. Chapter 4 MAC-ARQ Protocol 67 conditions. Since it is not a complicated task to estimate the channel B E R between the M D B S and the M - E S s , we can take advantage of the relations between the throughput and the B E R to optimize the throughput performance. For example, as shown in the previous section, in various fading conditions, the two schemes exhibit similar B E R thresholds whereas the throughput of one scheme outperforms another on one side of the threshold and vise versa on another side. Hence, it is worth considering to employ an adaptive scheme where the M A C - A R Q protocol can be automatically enabled and disabled according to the estimated B E R performance. In other words, enable the M A C - A R Q scheme when the B E R is larger than the threshold, and disable it when B E R is smaller than the threshold. For example, the base station w i l l start to transmit data with M A C - A R Q protocol, where each data block to be transmitted from the base station to the M - E S is prefixed by a block header before it is RS encoded. During the transmission, the M - E S constantly estimates the channel condition and B E R performance. When the B E R reaches up to the thresh-old, the M - E S may send an L L C control frame via the reverse channel to request disabling the M A C - A R Q protocol. Upon the reception of the control frame, the base station w i l l switch to the conventional mode, where the data blocks are transmitted without the block header. If the B E R drops below the threshold again, the base station may enable the M A C - A R Q protocol again upon the request by the M - E S . Therefore, if we ignore the processing time of the adaptive operation, this scheme wi l l maintain the throughput performance in its maximum value range. Let us t a k e / D = 80Hz as an example, when the channel B E R is less than the threshold, e.g. B E R = 3.0E-2, the system wi l l take the M A C - A R Q scheme and provide a throughput of 0.6, which is almost twice the throughput provided by the conventional scheme. On the other hand, when B E R is larger than threshold, e.g. B E R = 1.0E-3, the system wi l l take the conventional scheme instead and provide a throughput of 0.91, which is around 0.1 more than what it can provide by the M A C - A R Q scheme. Chapter 4 MAC-ARQ Protocol 68 4.4 Summary In this chapter we have proposed, analyzed, and evaluated by means of computer simula-tions, the performance of the M A C - A R Q scheme. We have presented the advantages on through-put performance of the M A C - A R Q protocol as well its tradeoff in certain channel conditions. We have also identified the performance threshold which can be represented by channel B E R perfor-mance. Consequently, we have discussed an adaptive scheme which automatically select between the two schemes according to the estimated B E R s , thus to achieve optimal throughput. Chapter 5 Conclusion and Some Suggestions for Future Research 69 Chapter 5 Conclusion and Some Suggestions for Future Research 5.1 Conclusions In this thesis we have studied, analyzed, and evaluated C D P D forward channel perfor-mance, in terms of M A C layer block error rate, packet error rate, and the throughput. Our studies have included both analysis and computer simulations, in the presence of various communication channel conditions, including the A W G N channel and land-mobile Rayleigh fading channel. We have also taken into account different type of G M S K receivers, such as the coherent receiver and differential receiver. Computer simulation results have shown that coherent receiver demonstrates better performance than the differential receiver in A W G N channel while it is outperformed by the differential receiver in the fading channel. We have investigated the forward channel M A C layer structure and identified a source of performance degradation, i.e. the correct but unusable data ( C U D ) which peaks about 45% over all transmitted data regardless the channel conditions. To eliminate this inefficiency source, we have proposed an M A C - A R Q protocol which performs A R Q operations at the block level, hence effectively eliminates the C U D . Simulation results have illustrated considerable performance improvement of this protocol. In the fading channel, it demonstrates over 0.3 of increase of the throughput when Ej/N0 is relatively small, although when E//N0 is very high, the extra overhead introduced by the M A C - A R Q protocol results in approximately 0.1 degradation on the through-put. When studying the relations between throughput and channel B E R s over various channel criteria, we have found that the throughput curves for the two schemes intersect at similar B E R values. In order to optimize the throughput performance, we have discussed an adaptive scheme Chapter 5 Conclusion and Some Suggestions for Future Research 70 which dynamically switches back and forth between the conventional scheme and the proposed scheme in accordance with the physical channel B E R performance. B y this means the maximum throughput can be achieved. 5.2 Suggestions for Future Research 5.2.1 Effect of the MAC-ARQ protocol to the reverse channel This thesis has not studied the effect of the M A C - A R Q protocol to the reverse channel performance. Since the A R Q is operating at the M A C layer, it is possible that the number of acknowledgment packets transmitted on the reverse channel is more than that in an conventional scheme; this may cause degradation on the reverse channel performance. Therefore, it would be worth looking into such effects on the reverse channel. 5.2.2 Revoke the ARQ operation at the data link layer for the MAC-ARQ scheme The proposed scheme performs A R Q operation at the M A C layer, while the original A R Q functionality still exists in the upper layer. The M A C - A R Q protocol requires an extra block header containing necessary information for the A R Q , but in the L L C layer the conventional A R Q also requires similar header, this causes some redundancy. For the sake of simplicity, this thesis has not taken this redundancy into consideration. Therefore, it might be useful to perform a small modification on the L L C layer protocol to revoke the A R Q operation, and hence eliminates the redundancy. 5.2.3 Soft threshold for the adaptive scheme Although this thesis has demonstrated similar B E R thresholds in the throughput studies over various channel criteria, the B E R threshold cannot be estimated accurately since the variety of channel conditions, e.g. for different Doppler frequencies, the B E R thresholds are slightly Chapter 5 Conclusion and Some Suggestions for Future Research 71 different. It would be interesting to consider a soft threshold which would involve some statistical studies of channel characteristics to determine the threshold range where the throughput is maximized. 5.2.4 Performance study for similar applications other than CDPD There are many wireless communication applications that possess similar system structure as C D P D . They may have different block/packet lengths and overhead. It would be interesting to investigate the performance for other configurations, and verify the possibility that the M A C -A R Q protocol and the adaptive scheme being applied to these systems and evaluate the improve-ments of the performance. 5.2.5 Diversity reception In this thesis we have investigated the C D P D performance with coherent and differential detection with single antenna reception. For better performance in a fading environment, diversity reception should be a good choice. The combination of diversity reception and the M A C - A R Q / Adaptive scheme wi l l produce significant performance improvement. 5.2.6 More advanced coding techniques C D P D system employs (63,47) Reed-Solomn coding scheme as the F E C . It provides fairly strong error correcting capability. However, in this thesis we have found that the RS codes performs better in a slower fading environment than in a faster fading environment. It would be interesting to investigate the effects of the codes in fading channel with different Doppler shift values, and introduce more advanced coding techniques which give better performance in a slower fading environment. References 72 References [1] C D P D Forum, Cellular Digital Packet Data System Specification, Release 1.1, January 1995. [2] M . Sreetharan and R. Kumar, Cellular Digital Packet Data, Artech House, Inc., 1996. [3] A . K . Salkintzis, "Packet Data Over Cellular Networks: The C D P D Approach," IEEE Commun. Mag., vol. 37, no. 6, Jun. 1999, pp. 152-159. [4] A . K . Salkintzis and P. T. Mathiopoulos, "Adaptive Beamforming in C D P D Mobile End Systems," 6th IEEE International Conf. on Electronics, Circuits and Systems, Pafos, Cyprus, 5-8 Sept. 1999. [5] D . Saha and S. E . Kay, "Cellular Digital Packet Data Network," IEEE Trans. Veh. Technoi, vol. 46, no. 3, Aug . 1997, pp. 697-706. [6] W. A . Massey and R. Srinivasan, " A packet delay analysis for Cellular Digital Packet Data," IEEE J. Select. Commun., vol. 15, no. 7, Sep. 1997, pp. 1364-1370. [7] B . Kamali , "Modulation and channel coding for Cellular Digital Packet Data networks," Applied Microwave & Wireless Mag., vol . 9, no. 3, May/June 1997, pp. 26-38. [8] K . C. Budka, "Cellular digital packet data: Channel availability," IEEE Trans. Veh. Technoi, vol. 46, no. 1, Feb. 1997, pp. 31-40. [9] C. Jedrzycki and V . C . M . Leung, "Optimal channel assignments strategies for forced hopping in C D P D systems," J. Mobile Networks and Applications, vol.5, no . l , 2000, pp. 5-16. [10] T. Wan and A . U . Sheikh, "Performance evaluation of Cellular Digital Packet Data (CDPD) systems," 48th IEEE Veh. Techn. Conf, Ottawa, Ont., 18-21 M a y 1998, vol. 2, pp. 810-814. [11] S. Resheff, " C D P D Performance: A Joint Analysis of the Physical and M A C Layers," 8th IEEE International Symposium, PIMRC '97, vol . 2, Sept. 1997, pp.440-446. References 73 [12] C . Leung and J. N G , "Estimation of block error rates for N C F S K modulation on a V H F / U H F mobile radio channel," IEEE Trans. Veh. Technol., vol . 38, no. 2, May 1989, pp. 46-49. [13] H . Bischl and E . Lutz, "Packet error rate in the non-interleaved Rayleigh channel," IEEE Trans. Commun., vol. 43, no. 2/3/4, Feb./Mar./Apr. 1995, pp. 1375-1382. [14] A . Seyoum and N . C . Beaulieu, "Semianalytical simulation for evaluation of block-error rates on fading channels," IEEE Trans. Commun., vol. 46, no. 7, Jul. 1998, pp. 916-920. [15] A . S. Tenanbaum, Computer Networks, 3rd ed., Prentice Hal l , 1996. [16] K . Murota and K . Hirade, " G M S K modulation for digital mobile radio telephony," IEEE Trans. Commun., vol. 29, July 1981, pp. 1044-1050. [17] J. S. Toor, "Differentially detected G M S K systems in the presence of adjacent channel interference and nonlinearities," Master's Thesis, Dept. of Electrical and Computer Engineering, U B C , Jul. 1994. [18] M . K.Simon and C. C. Wang, "Differential detection of Gaussian M S K in a mobile radio environment," IEEE Trans. Veh. Techn., vol. 33, Nov. 1984, pp. 307-320. [19] S. S. Shin, "Differentially detected M S K and G M S K modulation schemes in C C I channels for mobile cellular telecommunications systems," Master's Thesis, Dept. of Electrical and Computer Engineering, U B C , Oct. 1992. [20] C . -E . W. Sundberg, "Continuous phase modulation," IEEE Commun. Mag., vol. 24, Apr. 1986, pp. 25-38. [21] J. M . Wozencraft and I. M . Jacobs, Principles of Communication Engineering, Wiley, New York, 1965. [22] W. C. Jakes Jr., Microwave Mobile Communications, Wiley, New York, 1974. [23] W. C. Y. Lee, Mobile Cellular Telecommunication Systems, M c G r a w - H i l l , New York, 1989. [24] J. G . Proakis, Digital Communications, M c G r a w - H i l l , New York, 1989. References 74 S. S. Shin and P. T. Mathiopoulos, "Differentially detected G M S K signals in C C I channels for mobile cellular telecommunication systems," IEEE Trans. Veh. Techn., vol. 42, no. 3, Aug . 1993, pp. 289-293. A . Yongacoglu, D . Makrakis, and K . Feher, "Differential detection of G M S K using decision feedback," IEEE Trans. Commun., vol. 36, no. 6, Jun. 1993, pp. 641-649. C. W. Lee, Y. M . Chung, and S. U . Lee, "Bi t error probabilities of C P M signals in frequency-selective fading channels," 1EE Proceedings-I, vol. 138, no. 5, Oct. 1991, pp. 465-472. K . Hirade, F. Adachi , K . Ohtani, and M . Ishizuka, "Error-rate performance of digital F M with differential detection in land mobile radio channels," IEEE Trans. Veh. Techn., vol. 28, no. 3, Aug . 1979, pp. 204-212. W. Stallings, Data and Computer Communications, 4th ed., Prentice Ha l l , 1994. M . C. Jeruchim, "Techniques for estimating the bit error rate in the simulation of digital communication systems," IEEE J. Sel. Areas Commun., vol. 2, Jan. 1984, pp. 153-170. G . Brasche and B . Walke, "Concepts, Services, and Protocols of the New G S M Phase 2+ General Packet Radio Service," IEEE Commun. Mag., vol. 35, no. 8, Aug . 1997, pp. 94-104. ETSI , "General packet radio service (GPRS); Service description," GSM 03.60, Version 7.1.0, 1998. S. B . Wicker, Error Control Systems for Digital Communications and Storage, Prentice Hal l , 1995. B . Kamali and R. L . Brinkley, "Reed-Solomon coding and G M S K modulation for Digital Cellular Packet Data systems," IEEE Pacific Rim Conf. on Communications, Computers and Signal Processing, PACRIM, Victoria, B C , 20-22 Aug . 1997, vol. 2, pp. 745-748. W. C. Y. Lee, Mobile Communications Design Fundamentals, Wiley, New York, 1993. P. Lettieri and M . B . Srivastava, "Adaptive frame length control for improving wireless link throughput, range, and energy efficiency," Proceedings IEEE INFOCOM'98 Conf. on Computer Communications Seventeenth Annual Joint Conf. of the IEEE Computer and References 75 Communications Societies Gateway to the 12st Century, San Francisco, U S A , 29 Mar.-2 Apr. 1998, vol. 2, pp. 564-571. [37] S. Hara, A . Ogino, M . Araki , M . Okada, and N . Morinaga, "Throughput performance of S A W - A R Q protocol with adaptive packet length in mobile packet data transmission," IEEE Trans. Veh. Techn., vol. 45, no. 3, Aug . 1996, pp. 561-569. [38] J. A . C. Martins and J. D . C . Alves, " A R Q protocols with adaptive block size perform better over a wide range of bit error rates," IEEE Trans. Commun., vol . 38, no. 6, June 1990, pp. 737-739. [39] W. Ajib and P. Godlewski, "Acknowledgment operations in the R L C layer of G P R S " , MoMuC '99, 1999 IEEE International Workshop on, 15-17 Nov. 1999, pp. 311-317. [40] D . Kostas, "Proposed M A C A R Q Mechanism for the proposed 802.16.4 Standard", IEEE 802.16 Broadband Wireless Access Working Group <http://www.ieee802.org/16/arc/802-16-tg4/msg00026.html>, I E E E 802.16.4-01/21, Mar. 2001. Appendix A. Program Listings Appendix A. Program Listin Appendix A. Program Listings 77 * S3 o -H 4J * U * d) A ; TJ u G a) TJ H -H 4J TJ a> o •K 4J QJ 4J u fO • H 4J 4J fa 4J g 4J -H VH tc «j - H g CD a* Q G g Ui JJ * fO Ui c 4H c G u c fO tO -H 4-> Ui 4J (0 VH * * 0> M VH 4-> * * * w to to M U to J J * 4J 4-) 4-) U O -P Ui * * * •H •H -H (0 '—I •H Ui 4-) * * 43 43 43 ft 43 42 M. 0> * * U * * * VH TJ TJ TJ TJ O u * * VH to (0 (0 (0 C tO 0) 43 43 43 43 • H 43 a * * * * * * IM UH 4H * * o O O o o O O o * * * * * VH SH VH u u u VH u * * * 0) QJ Q) oi ai 0) Q) 0> * * * * 5 * * * * * C rH G (—1 G i-H c c rH i-H G rH c c rH -dp; * + * u * * * * * * (0 fO fO fO fO to fO fO * * * 4-) 4J 4-) 4-) 4J 4J 4J 4J * c O o o O O o O o * -H * 4-t 4J 4J 4J 4J - U 4J fO * * g * * * * * * * * T3 * * ft * T> * * U * * >< * tn K •3 * * * C Q * * * -i-t 1 1 * TJ w W * * O 4J 4-> * 43 * U •H •H * * • * 1 CQ P3 to to w * rH * 4J JJ 4H 4H U 4* 4-) ft * t0 * 43 C c G c ffl r-t -rH UH * * 43 * u H M CM ffl PQ Efl tn * O * 1 o o TJ TJ TJ TJ UH M u * * rH * 43 u u (0 to fO fO G (0 D) * W 0) 0) XI 43 43 • H 43 °i -J * * = * I I 1 1 1 | 1 1 1 M * * * 0) 4J 4-) i-i 4J 4-) 4-) 4J 4J 4J * * QJ * i-H * * TJ * 43 Oi Oi Oi tn tn tn Ol Ol Oi 10 c 4-1 * * 3 * 3 c C G G a c c c G 4J SH - H * * 1—1 * O o o o o o o o o o 0> TJ •K * U * TJ rH l-l r-t rH rH rH rH o 4J G * c * x a) * * * * a> c o TJ O ft * C •• hi W •H — O O H TJ TJ tQ >—• UJ UJ >1 fO tO g II II C C © 0) * • H - H C C * id id O O * g g 2 2 * c to a) u -H <D > + - O > f0 rH . I ft ifl M -— to o * • > 01 Pi - (0 (0 <—' TJ CJ O ffl > — O (0 ffl i-3 CO * — 4J 3 4-> -H -• 4J * -- U 4J 3 * at u 3 a * S Wl ft 4J * 3 ai c ^ * S Q IH O * - - II -rH - (N N H • -tn ft o t0 fO TJ g II rH TJ tO 4J -H &4 fO O Q) O .J 4J 4J a o d c 4 J W li O O O O 3 TJ TJ i TJ I II II II II -H II II 4J O n o o C 4J 4J 4J C U C c c o o O r H O r H II r , O , 1 _ , L _ _ J ^ _ 1 O O - H en ' ft) fO fO fO •—' ' •—' I l l f f l W ' T J T J a ) < U O T J Q ) ( U H H -i f 0 f 0 > > ' - ' f 0 > T J X 3 f e i O O ; O O f f l f f l g O f 0 f f l U { D 4 3 i h l h l M w 3 j W i w I C g II i O O O O T S O O | 4 3 0 > t I T J T J T J T J - H T J T J 4 J E 1 I T J 01.J TJ -U 1 fO C 4-t 0) 1 r4 4^  0) tn 4-1 -H 4-J < < > 0) ai ^ 4J TJ 4-1 "H tO 43 4-1 * * * * * 1 * 1 * * * * * * * * * * * * * rH * * 43 * l 1 * to * -H * U 1 1 * fO * * > * * TJ * 1 1 * c * (0 a) * rH * * -H 4-1 * * ID * TJ * * rH w O CJ a 0 43 •H •H * 4-> * * rH rH -H * * tfl ffl C * * 43 43 * 1 UI 1 * O O 4-1 1 0) 1 * rH (D * A * O O TJ * 1 -H 1 A 43 * 1 4-4 1 43 A 1 * E . 43 43 1 * * 1 1 I TJ l O •H * c * J J 1 a) 1 -H rH 43 l * 0 * < < 1 TJ l TJ TJ 4-» I * -H * m CQ 1 3 1 4J 4J (0 l * 4J 0 O 1 rH 1 w tn g l * ft * 1 u 1 V V V 1 • H * 0 O 1 a 1 * U * 1 H 1 a) 0) 01 I * OJ O * U-l 0) TJ Tt TJ 1 g Ui * <D a 3 1 * ffl 0) * TJ -H rH rH * Q C O U U 1 * 4-1 Q) c c C 1 * * •H Tt * * * -H -H -i-i * * 4fc \ -v. * •H * * u 4^ 0 U >1 rH O X JJ * * * 43 u •H 43 0 rH tn rH 43 CO rH -H D O 43 4-1 43 oi CO 43 43 a X 4-) Dl 4J Oi ffl M4 01 rji c 0) c CO iJ •J TJ 13 01 c (0 c oi U TJ UI C 0) rH •I-i 0) 4-1 O -i-i rH rH c c iH 0 -H u D -I-i Ui to r4. r4 0) C Q & 4J O U 0) ft O a CM Q Ui -H 4-4 U a> ft •i-i C4 • J & 4J 43 0 Ui J J j h3 -H 0) rH a> ffl 6 43 >1 43 TJ O rH 1—1 01 rH 4J 4J 0 (3 ft 01 •i-i rH 0 •H Cn U P g TJ !H TJ (0 4H r4 C X fO O (0 0) g c fO a> CO ffl to UI J s CO M a. r3 oi 2 * * * * * * * * * * * H in H m ^1 -H >H -H -i-i -H C O h O h l O f N H O l H 01 0) Q) TJ TJ TJ =* # 4fc 4-1 4-1 4-1 01 a> ai TJ TJ TJ * * * 2 h3 h3 2 O g rH rH CN CO [1] w U O rH CN rH CN h3 2 h3 cu TJ to M « W Q ran < M a H AM O Oi M M o> a> Q) 01 0) 01 0) 0) 01 0) C c (3 £3 13 c u c c c c c •i-i H-i •H 4H •H 4H •H 4H 4H -H 4H 0 4-t -H 4-1 -rH 4-1 -H 4-1 -H -H 4H 4-J 0) 01 0) 0) 0) at 0) 01 0) 0) 0) TJ TJ TJ TJ TJ TJ * TJ TJ TJ TJ TJ =»fc # 0) 0) 0) X) TJ Xi ' *fc *fc : 2 H < ° a a 1 J3 T3 U IB J l * J TJ 1 3 0) ft tn CN CN rH J J .-3 —' in rH 43 0 ffl to tO 0 T) 43 43 O O U TJ 4J TJ -H 0) 0) U cn •i-i * rH 4J 4J 4J rH 3 Di tJl tn 43 Ui to in 43 Ol VH C (3 13 0 C fi C c 4J O O O O 0 O 0 O 0 to rH rH TJ 0 O u TJ 4-1 le C 13 fi c C C C c 0) VH SH iH iH VH VH VH VH TJ 3 0> 0) 0) 0) Ol a> 0) 0) 0) at 0 J J J J 4J 4J 4J 4J 4J 4J 4J ft TJ X X X X X X X X X 0) 0) 01 a) 0) 01 0) a) a> 4J Appendix A. Program Listings 78 > 3 + a O S TJ c S 01 CQ l-H 1 •-I to •rH > rH 0> 0 . o u TJ o u II CM Ol + Q oi G to o to II II r-H 4 J + -H CO CQ ol to rH 4H u A : II o G rt -9 -rH °l 3 , ?i 4-» JJ 4 J O Ul ui 171 01 II 4-) 4 J 4 J 3 3 to J o O O TJ >H ba •K >H * 0) xi or th > •SH rG 4 J OH Ol a 0) J J 01 c TJ * ft ng en 01 or * le s rt 01 r-H O 4 J "o u * rH 01 rt o rH u U + TJ 01 SH u u a o 0 0 a u rH u rH O o rt TJ > J J J J J J 01 u •r-i U O o O 4 J 4-J a rt u u u o rQ O 4J 4J U u TJ XI X 01 01 OJ 4J 3 * u u 01 rt OJ > > > u \o o 01 > > XI VJ TJ XI QJ TJ to Ul > > o c rH Q > Xt O rH 4 J 4 J u UH -H o o 0 * -f * * * u * U o S-t A : A ; QJ o o XI rQ c D V-l * rt X) o u u X r* U 4 J -H Q o * 0) ui rt £ u o o u u o 4-J CM u Oi TJ >i u rH rH rt rt rl 4 J OJ to tn 01 01 XI u -* G G U G 01 01 rQ rQ a a o u rH J J OJ •H •H O -H 4 J QJ TJ TJ -H rH * 01 •K £ 4H TJ TJ TJ TJ u > 01 0) id X! rt c * 01 ui 0) 01 o o 0) 01 01 OJ 01 o J J J J £ G -H - H 4-> TJ 4-) VH bi bi bi O) > X U o •rH rH -H £ - H O - H H SH rt rt rt rt 0) Xi QJ QJ tn rt bi 01 * rQ u XJ 0) 01 e 6 £ £ X TJ 4 J 4 J J J -rH 4 J -H 4 J * 01 * rt rt rt rt 01 G Ol QJ Q) U o u -H i-J rJ u U 4H TJ TJ TJ TJ TJ -H c TJ TJ o 4 J o •9 * rd o o O o G * * 1-1 u SH c + * -H J J rH + * + * * 3 * u u rH u rG * U * 0) 0) 01 01 rH J J 01 * * rH * td UH •H e tn *p tu C e to M to 0) CM * * 01 * 01 Xj 01 * Ul OJ * 01 Es OJ 0) * e * rd 0) 6 0) QJ * * * rt * 1 01 rt C C * rt H * rH 01 SH o O + * x: <u * TJ rt 4H 4H * \ * * I •K rH 01 01 * 01 rt * XI rH C * * o o •H o * * rH 01 •K •H * 01 * 01 01 J J * 01 * Ul J 01 * a • • * 01 * * rt * -rt • • J J * rd * * 01 1* U 4 J 3 * 1 * * TJ rH * 01 u 3 a * rH * 3 TJ Ul a J J * TJ * * rH * 0) a 3 * * * O Dl TJ Q H O * TJ * c C •H * •rt •H * * * * -H o o * * * * o -v. >^  rH > -v. > rt rt rt x: x: x; u u u 4, > rd a xi J J XI rt O"1 TJ 01 W JJ 0] II > H xt x: £ II C XI CQ 01 QJ CQ -rl rH 01 U > a 01 rH + C rQ TJ rH o o o 4 J Le U G -9 II 01 4-1 a 01 1 i 0) TJ a >i 01 E-< o rH o 0] OJ TJ rH 0] rt 4 J JJ | 0] O C o 4H JJ x: JJ o o U 01 0) rH c 4-1 oi 4H o CM G rt 0) -H 01 o II Q 01 0) u rH 4 J a > > > II 01 C -H 01 o O o u w QJ > CQ 4H rd rt rt C rH C rH II 4 J CM CM CM QJ > 1 01 rH A ; G TJ TJ TJ N a > XI W a -H rt rt rd 1 a a 4H iH rQ XJ JJ U LSI rt TJ TJ rt •n a 4 J 4 J J J o J J o 4 J 4 J o jJ C c C n rZ a x: c a rC C * 4-1 01 •H 01 •rH •H 01 -H •H O M O rH rH XI Tl 3 10 O XI ~-4-> X! 3 3 o o •0 •a . - to — Xi 6 tn to 4J t u 3 . i o I — tt-t > rH II Xi <o E en I o J - 0) 10 XI fl^fflrtWT! — tn • C I to a> tn a) XJ w I c XJ 0) G rH o 3 * Cn tn T3 T3 O XI 3 Vi 0 O T) tw II O T3 XI C U 0) J . T J * * tfl * 01 * * -H JJ * * * * * •K * * * * * * OJ * to * * QJ X O * * rH * rC * G u * O 4 J T J O rd rH * * * Oi 0) * a + * * c rH * 4 J * * 01 rH •* 01 I1 *" Ul * rH rd * U * U * -H 1 > I * II •K £ * 4H 3 a Q * * * O QJ * T J T J * * 01 * T J rH * QJ * 01 * G -H 4H 4H * rH QJ * rd JJ O O * O rH in * * * -Q * rt * N rG x: * * £ * U * O 4 J JJ O * * 01 rt * QJ o * U oi bi T J * * 01 * >i J J * C G c rH •K * rt G * rH 0) 01 rt + * 4-J 4H * rH •H * + rH rH VH + * * O O * + * * X OJ * * * * •H * •* u u * G )H 01 I * * 0) 0) * -H o * * o * rH JJ * rQ rH * * * rt to * 3 + * G * * — 4J rt * O * 0) * G G * — rt T J 4 J * T J O * * > Q G rt rH * rH * * * G rd T J * + I * T J * * 0) 0) * * * * X) JJ > * T J * * * a rd in G * G O * * Tl U O 01 * 1 O rt * * 1 0) 4 J XI QJ QJ * E - XI U u m * * * 4 J G O a G G * Cn G CM * * * QJ 0) 0) T J O o * QJ Q o * * X J * 01 O > = S S * O H XI G V OJ * * * U OJ OJ -rl CN * * rH * CM u X) X J * + rt Ul > * * > Q 4J a 01 • ^  3 ll * X3 rH G * G * G G u rH O A * O 0 0) * O 01 - G - H n a II T J * rH •9 XI * -H * rH > G QJ -rt G * bi a * 4J * a G QJ rH II VH * >1 T J * a * T J 01 XI I G II o JJ 11 * * 01 XI 1 * -H 4 J * 1 XI OJ > U G G * QJ J J * -• u J J 3 * J J a ri a G > QJ •H G UH T J 0) * QJ U 3 a * QJ T J a T J jJ 0) G rH rH -H * 3 01 £ M a J J * Ol rt XI OJ 1 * * rH rt oi G 3 JJ J J J J O QJ > SH * u 01 T J £ Q H O * T J G G G rH u a a O * * G G -H * •K -H -H -rl -H UH a T J T J 4H * * * * * -H 0 0 * * * O \ -v. # r-H > > ^ c > K ft II p, H^ rH ft« ft | "O tn "0 > rH ft O "G u CM 01 Q — G J -rH XI J J * J J S rH G ii 3 •H n — SH UH —• O o - 4-1 0) rQ N 3 rt -rt 01 - 4 J Ul OJ rt > T J X J > rd rd > G •r-i 4 J G OJ SH (d QJ XJ rt T J XI a > • a T J > T J rH G rt Oi G * rQ XI OJ o a.a T J rH T J O 01 0 — 4 J > 0) G - J J 0) G rt a d QJ T J O u 4 J a 4-1 = •H D II — VJ a a J J UH 1 4H G 01 — -H to ^ rH 01 o a to rH 1 UH rH u * •H QJ UH Appendix A. Program Listings 79 T ) c > x CQ T J (d XI C O T J 0) W (0 XI U 0) >i (0 XI Q C -rt w 4J + (1) + A ; + - H U + rd •H ft c 01 T J rH * J + 1 XI > X 0J XI 1 CQ 4J T J - H (0 bi xi G o > - H o V T ) CM OJ a a XI •rl - H V a •rt T J O ii O + II O II -rt fi -H II 0) I 4-> rH 4J u u to nj ft ft « n) J3 J3 U T3 c c 3 3 — 4J 4J ~ - C C I C * 0) - H > O r-H — ft —' > I "ff a « > u u d) ft o o FLEN C 0> 6 o W + A ft 01 a + QJ TJ rH n 0) II c 4J O Q) bi II •H • H }H X in 1 T3 • H X + + x; 0) •n u TJ * ar c •H 0) • H 01 w 4J TJ x: JJ 52 * bi X! - H • H iH tj) -H 4-1 "c QJ Vr •K 01 0) x: o in S rH rH 1 + rrj P-i J J 3 LE 01 > 0) + TJ O )H • H ffl S 4J TJ to ... XI te bi t-H 01 V in fi II rt fi 4^ 0) V TJ •rt o c a TJ 4J 01 1 • n 3 O 01 6 •- 3 + 6 3 OJ —-. 4J > rH > •H ts fi -V 3 rH > O U 4-1 rH 0 CO o (D 4-1 U TJ (0 4-) CM OJ 0) m CM <4H TJ rH 0) 1 X) TJ Q) (0 > > * n V4 4J 4J (0 XJ U u C M o > (13 II 01 II + X u V CM c o + Q) A rd TJ TJ •rl u >> II 4J CM •rl (0 fO TJ 0) bi ffi • n rt G TJ XI X! 1 C CM 0) trj > O O JJ -H | II 0) rH XI O II II u U TJ tn G 1 nj ll II 0) II O 4J 4J C QJ 4-1 II II • n CM in •+ O -H X3 Q) bi • n TJ + C C 1 CQ bi OJ -H 4-1 (0 0) 0) 4-» 4-1 4H •H 1 o XI rH rH c c c 4-1 > 4J •rt I I 3 H > 44 i o > C •—- 4-4 > > l o O TJ U OJ (Tj u •H •rt o o O (0 Hi rH CM (TJ fU (TJ 0) OJ XJ CM - > TJ CM o CM CM 1 1 1 TJ + U (TJ II TJ !H ^ TJ TJ 4-> 4-1 4-1 ro + rrj X3 (TJ o fU (0 — XI - n CM TJ (0 ~ XI •r4 ' XI 4H — XI <U XI tn i—i Oi * outs outs outs e 3 -H o> (0 4J 0) 44 01 4^ or ho re or * lo >1 44 O 1 tn 44 o 4H tn x: w X3 XI 44 4-1 44 01 Lfl LO XI SH tn * -K + 0 tn -rl o N Xt rt fi X) o 0) T J I X I 1 -rt !D 4J O N 44 44 U II 1! rt H o X 4J tn II da 01 N 44 01 pt II rt eo en !! !i XI BL lo bl 0 o bi ll & -rl O S II 4-3 N 2. 0) 11 X ! fi + > tn r>- 4-1 rt -rt & ,fi + -rt ll 4-1 fi 0) x: T J tn 01 •rl 4J •H G o QJ Q) tn 4-> o o u tn + + -rt (-H 4-) tn XI XI S > oi o X J [S3 + c bi II QJ Q) B U a fi II II 4J w N 01 •rt QJ fi tn rH > tn 44 T J fi 0) II Q II u a fi 4J rH -H rH OJ 4-1 rt 44 o OJ rH OJ 0) 01 1 T J o > o 01 u of 1 a nd OJ O] 4J 01 a rH a N fi XI rt tn 4J of X * CM O nd dP tfl ll ll dP tn de JJ ro 0 em > II || fi o 4J II 44 44 1 4J bl T J 4-> T J •rl o 4J T J 0 4J a it bi II n tn 4J O -rl + •H 4H •rl O at o bi 44 -rl u V II C ll V o fi I O XI -rl O fi O P" c tn fi 0 •rl n tn II -H || bi -rl X > fi rt > II o fi rt rH ii tn n fi II o rH II 4J tS3 01 O II JH o u o n tn II •rt u X J c a W 1 tn 3 a O II 0) II o T J o 4-> 1 4J -rl T J o T J OJ 4J 0 T J II + II U II o 1! C tn 4J fi 44 (TJ 4H rt 1 p* T J — Pi 44 44 rt 1 •rl G p. ll o M 1 II U -rt | 4J C 1 •rt CD a n 4J 0) a II 1! 44 to II 4J 0) a 0) w II U II 1 0 -rl -H 0 U fr e(f a 4-1 rin fr 44 OJ ] 4-1 1 4-> dm if mp int II 44 rm fr 44 Q) ] int rH 1 N II II a M II 14 II 1 unt unt. 4J fi •H u *' i U ec * fo in a Ul T J 0) Q) u c a c II O II 0 o o u * o 0) O 01 O 4-> 0) 44 o> a 0) 01 o LSJ 01 II U II u u OJ 0) 44 w rH tn rH tn w rH tn rH u rH II M II OJ 01 II U U 44 O * 44 rH 1 44 rH u o 1 II 0) II * 1 1 o 0) 4H -H 01 44 •r) Q) o> N •H 01 44 44 tS3 * * * 4J 4J • n 44 • 3 C j_> o 3 i , U O n S 0) g1 U I • HI 4J d) 4J fi o U 1 tn w 4-1 X) •r-i CQ A •rt S o 0) 4-1 fi II - H + bi II fi -rt T J + o + U •r-i 1 4J > fi X rH o CQ o T J 0) rt 1 XI 4J Appendix A. Program Listings 80 rH * * •k O VH O rH + Ui * 4-J D 1 * * * * * rfl + 0) Ui •k VH 0) * rH 01 £ * * O [n QJ * * * 4J a 0) 4-1 * * * r3 G 1 UH 4-1 •rH * * rH * O H Q OJ X * * Ui ffl rH 0) * •k C SH VH -k + -* UH UH 01 01 * II * Oi O O * O O •k T J * + •H 4J 4J * QJ 0) 0) 1 G o •k Ui •k Ui U U T J U U 0) 0) hi T J u + * •k Ui 2 •k 0) Q) G G u u 1 hi Oi G + * rH 0) w CM > > * 4J 01 01 G G c ffl 01 X o + 0) * -H 2, 2. OJ 0) OJ T J -H 01 G T J X * •k 43 & 0) M rH rH * rH & & 2. 2. CJ C 4J O -H •H * •k F £ •k ffl ffl a 0) 0) & & CO c tfl II •H 4J H * >i Ui ffl 43 •K T J c C e 01 CO 01 0 OJ VH II VH 0) ffl •k Ol 3 * c Ol 01 fo CO CO 3 3 4-) u U CO to -k O + ITJ •H •rH * 0) T J 0) & 0) SH G o rH C * -k T J 43 01 01 O) Q) 4J 4J rH 0) VH o QJ rH O S o o 0) fa rfl rH 3 3 o 43 01 43 O 43 3 43 + bJD UI H o Ol 01 a a a 2 3 3 43 UH CO & ffl £ + SH SH 0 1 rfl * G 01 £ 4-1 4-> O O O 0) 3 0) " O (h * u 0) 0) Ui 43 o o Ui -H 0) ffl 3 3 43 T J o T J tfl CO VH to hi * >< fj 4J 4-> CO a CO o o W o 43 •H i-i o O o * -k 6 •k * * e + ffl 01 T J VH V 01 * tr« 3 01 Ui VH VH + * * * + T J N QJ VH 43 * 4* -k G G rH S 0) 0) * rH Pi 01 r-. -H -k o rfl •H rH 0) >^  V T J 01 Ol 43 O jJ 4J 43 2 rH 01 fN 4J 4J f j Ui a T3 •H 3 * i * 3 C C * W rfl 3 rH G rfl 0) £ -H •f~l O * * O QJ -H •rH O 01 01 o 01 •H T J CO rfl O" VH * -k T J 4J o O T J VH c 4J £ t r CO i J 01 43 rfl SH a a 1 O VH 0* (J OJ C o o CO 4J •k ui U O * o Pi 01 >, O 0) 01 G 01 0) -H £ * * -H c QJ 4-1 0) •H 2 4-1 01 43 01 01 01 £ 4-> SH II II U * Ui ffl C U c * 01 o w rfl 01 £ £ a rfl a II hi * * SH OJ 01 -H o rH VH 01 o SH >s •<-) 0] •k * 43 * 4J o > 01 01 2 * * * 0) 4-1 V 0J 0) hi T J CO * * Ql 0) rH 3 G VH -H * > C 4-1 C -H 4J tfl QJ * rH Ol rH ffl o o 0) o ffl OJ T J 0) C + to O1 a rH * * ffl 43 43 01 a Ol 43 CN 01 a G O) 4-1 hi 4J -H 0) 43 * XI 3 c & VH CN 01 O o rfl o VH hi G * 01 3 •k O O O 0 * O 01 1 II II UH U > O •H 01 X) £ 0 * rH T J * -H * T J a 10 rH CN Pi ii 4-> i 3 •H 43 2 G T J T J P. •K 0l 4J * e £ V X X 2 VH 1 01 II a CO 01 O -H UH 03 01 * 01 tu •k •k •k -k W rH D1 i c 4-1 •H UH OJ II G 3 * G -H 4-) C rfl 01 G a 4-i 4-1 3 II O CJ QJ CD OJ * 0) ffl SH 4J * ffl Q) 01 0) QJ 01 1 II -H C7 G •H 0) 01 rH 0) G Ui 4J * * T J SH 0) U a SH rH 4J rH rH rH VH II OJ -H JH 01 G u SH 4J o 0) * 3 4J £ 01 a 4J 43 VH VH 43 43 43 1 l D 1 CO VH 0) 3 o O Q) II rH * * rH rfl 0) c T J O O 3 3 3 Pi a i 0) VH £ a 01 UH rH II VH u 01 * u Ol T J •k Q H o o 43 43 o o O 2 £ * 01 O UH o •k UH O Ql rH UH T J * * c G •H * -H T J to 01 T J T J T J w tfl ^ £ -H 01 UH u •H T J X * * * * * -H O o * * * * * o * <H > > exit(1) ; } * H 01 * + •»• * * * •k * 01 * * 0) •k * 0 * * 4-> -k * * * 4-> 0) * 01 * rH hi * * %\ * C X 0) .—. Q) * * Ui 0 * 0) T J 0) P< * * * •rH > 2 > * II * 4J * ft) 4J U * •k a CO 1 II a rfl * 01 o * M O o 4-1 ll UH PJ * * 01 * u T J T J T J * * rH 0) + G 01 01 G „ ffl * * 0 rH * 0) G c IS) 43 -k * rQ & * * a •rH -H T J 1 - - Oi G * * £ rH * & 4J 4J ffl G 43 G 0) * * Ui (0 0) ffl ffl O CO 01 3 •H rH > * 01 * to u u hi u 4J G £ UH •k •k -k o o o hi hi rJP •H 0) WD * U-l •k rfl * 4-1 rH T J rH VH hi * O O 43 rH VH VH II II 01 3 4J + U + 3 O O rfl tfl * a 4J ffl VH + T ) * * SH SH •K CO 4J 4J CS3 Nl •iH 4J VH O -H * * 0) 0) * X * 0» U u VH VH rH 3 G G 4J X rfl O 43 II G c * * * EH * VH OJ OJ N O O QJ T J 0 QJ 0) TS UH CO + QJ Q) * u + •k > > VH VH •H rH VH G rH rH * 0) UH U SH O N rfl UH 0) hi 1 1 * M •k c c CO + 43 rH rH O OJ 0) rfl 4J CM 4J o rH Q . > > UI * S 4J ffl ffl 43 T J U N rfl 01 J 1 tn u r* * £ •k + O * c G 43 U UH 0) 3 T J N > ffl rH * •k •k Ql Ol Ol 4J UH * 4J X •H u 4-1 Pu m * e VH •H •H 0) 4J 4-1 43 Q 0) rSl CO ffl •H T J T J * VH O 01 oi G G G 0i 01 rH CM CM T J 0) a cu cQ ffl ffl * * O •k 4J 01 •H •H --. 3 Pi rfl 4J G T J UH 43 43 * UH 0) 0) * CO H O rH VH SH + O S G II 4-> 0) 4-1 QJ 4-1 rfl G * * Ui VH c S3 •k a a hi VH 4J 01 M II M O rH \ a •H 43 H II II * QJ o O •k •k •k * hi hi rH 43 1 -H CJ 0) QJ O X V T J + + * * 43 B a 2 2 -k ^ rfl 4J 43 Ui 43 01 UH VH TS 0> -H ffl •K -k — G Pi u 0 9* •H VH G 4J 01 01 •K rH * 0) 01 Oi rH Ui II U T J O QJ T J 1 U r* •k ffl Ui rH hi -H H ffl CO II 1 4J 1 U H a G N -H O 4-1 ffl rH 43 rH * C -k 43 hi 43 hi Ui ex 2 4J 1 4J G o ffl o II UI Cu m * + O O * 0 -k 3 3 & O CD U 4J U IH UH CJ > -H T J T J rH -H •k 0 0 2 W O •H p< 0) T J Q) 4J ffl re 01 — * 4J * H a - T J T J CO 01 M 4-1 4-1 4J II 4-) 43 43 * -k Ui — * a * CO * II II 2 O j j 0) OJ UH OJ UH QJ OJ c 0 1 * •H 4-) * 4* •k G £ II II o H 01 rH 01 1 T J U4 T J 4-1 4-1 a 4-1 4J 4J -H 4J 4-> * 0) 01 * VH 4J * 01 0) 0) 0) 0) 01 4J J J -H G QJ UH G QJ •H * * T J e * U a * e 4J rH rH rH G G ex X 01 ffl c OJ T J II II •H rH -H rH VH 01 ui * * 3 & * e 01 a 4J Ol VH 43 43 — H C Cu a Q 01 0) SH QJ SH QJ 01 3 SH 4J -k * rfl 0) G * o 3 3 4J ll II ffl ffl IS) CO ISI CO a T J a T J 01 UH O * * U Ol T J * Q H o * T J 43 O O G UH UH -k VH * 43 •k UH rH rH UH o o * C c •H * * 01 T J T J -H M •H CM •rH ~-~ 4J U -H OJ Q) -H Q) * * -H o O * * * * O # rH > ^ > Appendix A. Program Listings 81 •k -k + * QJ U £ 0) — QJ 0) >i >, & T u u 05 OJ c c £ SH u tn 0) Q) SH u Di a 2. 2. r0 rt u c UH c & & •H o 0) 0) a a a •J TJ •H Ul Ul e e u XI rt 4J 0) 0) QJ + , 3 M o JJ 4J o in U rH X O * * * 11 H rH > II O En c 14-1 4J - CM 0 •H CQ u * —. rt X 0> O JJ QJ rH X J rt X I Xi u TJ 3 Oi D1 0 3 —-1 Xi Ul TJ 0 --O SH H o* rl l O 1 u —* Xi tn t? 1 f>-rt 1 — o JJ 0i SH Dl SH 1 T J A 4J QJ £ — £ -H rt X QJ N D1 •H -H Ol I O T J 4J •H Ul 4J 4J £ l Ul £ 0) in rt oi rt + 1 -H 1 z-> A + xi 0) rH U JJ W u Ul 1 4J 1 w U o a QJ -rl o 01 o * 1 -H 1 c/i XI T J Xi u O T J u w rH rH "3- rH "J 1 a i En -H 1 Xi XI rH QJ XI •H 1 En T J V T J SH 4J 01 rt T J rt o •H b1 rt X - «H £ SH SH l 1 H o £ tn * •rH QJ SH - A 0) SH • - X ! i T J 1 CM -H Ul rt Ul rH Xi O -rH rH XI o rj £ i )H + £ U —, T J Ul X J XI SH ui XI X] in in (0 1 X M o cy a U QJ -H rt 3 VH XI -H 3 ED VH XI b1 i tn T3 II •H 0* 1 a £ £ £ £ a o a O 0) — tn O S 01 r-. in i 01 1 •H SH U I QJ 01 QJ QJ OJ o UH 01 J> T J T J £ I II II rH rH rH rH rH 4-> JJ a It • n a < II £ 0) II UH QJ Ul •5 11 UH 01 tn <—• i rH 1 X H CQ u a -H rH T J OJ 4J 4J QJ 4J JJ a i T J •o a + UH U 01 rt 0) £ -H £ QJ 4J T J aj £ O1 £ OJ 4J T J 01 I £ i •rH + QJ 0) I 4J 4J 4J jJ X- a T J OJ Ul SH -H rH •H 1 4J H •rl rH •H 1 4J 1 rt i M •H n 4J JJ I lH u u U rH 0) SH o II SH QJ X > 0) II — SH Q) X > 01 1 Ul 1 QJ QJ 1 O o o o O in un rH a T J QJ £ rH a T J QJ £ rH o !H ^ rH r£ xi xi xi X - * UH rH u * •rH UH O 0) CT UH O 01 * * * ll O QJ OJ * tn tn tn Ul M **- -H QJ UH SH •H u T J Vj -rl " U T J s •r-i UH T J T J 3 • H O II •8 -•8 •8=: -S3 -H -H M tH II II •H -H • < CQ 'rH J J X J * •rl X rj 01 rC -k J J U rt J J 01 en rt xi X! i—i 0) TJ * Ul J J j J +• + * * * w bi Ol QJ 4J X tn * * Ul cx J J £ £ U QJ * * rH £ QJ QJ £ el £ * * 0 * H * QJ rH rH 0) el UH OJ * * XI -H 3 TJ a a - - . SH rH * £ TJ o 0> 0) & OJ * O X5 * * * * £ •H * u U QJ 1 4J 3 * * tn * rt 0) * -•^ UH £ £ Ul •o I U 0 * * XI u ^J u * •k UH DM En QJ 01 o £ l QJ TJ * n * QJ o o £ * QJ CM CM 3 3 J J X H i > i & a * * * in 4J 4J QJ * J J o CQ CQ X & & 3 0) a 0i in 6 £ * * Ul * rt u U 2. * 01 U o O 01 QJ QJ a £ (N Q) tn rd rt * in XI 0) 0) & * Ul TJ tn tn i J J £ TJ •rt X g EH rH * * rH 01 > > QJ * UH H UH UH £ 3 •H a TJ rt rt * •K * * O rH * Ul + UH 0) O 0 -H H Ot O 4J TJ rt bi ui £ •K * a * CO r-H rH O J J rt U QJ - £ QJ 01 —« —« rS * p £ 0* * S rt rt TJ + b1 0) w O * * * u SH QJ •rt 01 rH -H Ul Ul Q£ Ul rt Ul in o £ £ 0) + Ul bl rH -v. o N 4J X! X J tn ^4 tn * 01 01 4J + £ -rl rH 3 M X! tO 4J 3 QJ 01 * •K •H •H u * •k •H UH Jj J J rH X 0 3 SH O o rH rH * * UH UH QJ QJ o Ul tn 0) + 01 rH 3 3 rt •0 O 0) O TJ XI XI * o o rH * 4J + rH a Cn a a tH TJ £ 4J H 3 3 M * * XI xa •K u H 01 * rQ £ ^ CM J J J J + SH rH rt QJ TJ + O O u U 3 3 •K 0 TJ * 3 rt CQ 3 3 O J J 4J 01 4J + TJ TJ * u * OJ 01 O O •K 4J o o o ;tn O 0 0 Ul SH X rt O c •K £ X * * XI Xj TJ TJ + u Ul 4J J J 01 * TJ * SH 01 TJ OJ - -H rt * X * QJ 1^ xi * •k * •k OJ 0) -v. N rH O + XI * OH * 3 •K J J o H SH J J * SH X -rl rt a + A : Q) XI x; X * X £ £ -H •rt * 0) J J 01 QJ * -H or O tn r4 X Ul Ul * in Ul + Xi TJ u 4J 4J o * tn £ X5 £ 01 OJ rH rd V OJ OJ £ * •K * * o OJ £ £ J j * tn 4J J J 01 U X X XI X X 01 •k * * U 4J > •H •H * + rH £ a x! 0) X! X * * QJ 1 £ o 0 SH * 01 H •H Ul o rH 4J (JJ V + QJ X3 XJ * * rH rH 4J OJ rH a a QJ * rH £ ¥ SH UH X £ X j J X! xi X) XI * U SH rt J J * X» XI QJ a £ J J -H rH rt o * * * * 3 3 QJ QJ £ £ * 3 m rH OJ X rH H M JH * O 0 * 4J Xi Ol •H * O £ TJ rH OJ iH QJ II CU CM * TJ TJ * 0) 0 -H •H b* 0 * TJ II II II II rd •H + X \ II X C •K Xi * TJ u in Ul tn a * £ u 0 in rt \ X OJ X Ul £ * xi U-l + X! EH rH H cy U XI OJ > S OJ bi O -H * o •H * 0 PQ + £ £ £ XI + a 4J X 4J u Ul * rd U) V TJ * •k U co tn QJ 0) 01 Ul o £ £ OJ X3 rH 1 1 •K £ -k I rH rH * UH XI 4J TJ •- x: u i o •rH II i -H II ll X * •K O O 4J J J * O « Pn •n XI £ rt * * o u * •H 0 O — -H U Ol Ol Ol II II QJ a o Ol 01 * 01 0) 0) •K J J -k QJ 1 H H £ £ £ n X! a SH U UH X ! — £ X c X * w 4J jJ * a •• * J J CM X! •k •k >5 O o O 0) a 1 rH ll o o XI QJ OJ •H J J * QJ TJ rH rH rH UH II QJ U QJ i X rH OJ -H D 1 0) * * QJ TJ TJ SH 4J 3 * TJ < Q) QJ OJ •H X rH II Ul — 4J X in Ul J J * * TJ 0) U 3 a * L0 rH rH rH J J J J J J ~—' X J QJ O > 0) 1 II o i 0) * 3 * * £ tn a J J * •k X3 X) XI bi tn Ul Ul 3 tn rH £ rH U SH ^ r*-. rH * rH 4J J J * rt 01 £ 3 * J J J J 3 3 3 £ £ £ £ UH o UH rH u O 01 * OJ CN o * o 0) * U 01 u SH Q M O * U £ O O o o O O O •H TJ •rl 0) un U TJ --- X X UH UH TJ * £ £ o O * •k O •rl TJ TJ TJ rH u * * * * * -H o r£ xi * * * •K * * * xi \ -v. s , rH in Ul tn ^ Appendix A. Program Listings 82 Oi c 0 -X TJ •X * UH rH Ol rfl Oi •x Q) C "H G •H 4-1 •H X! •X T J a TS fi ffl 0 ffl O rH UH VH SH T J 0 0 O 43 UH SH 4-1 4-1 •X fi (fl Ol UH CJ UJ a •H -H UH ^ 0 G TS 01 43 0 a * > o 4H 4J * CJ rH CJ1 o •H 01 a 0 0 0 4J X a 4J * rH fO Q 4J TJ . rH •H 0) •r-t O OJ oi UH -H ffl QJ 43 •—> X rH X * * XJ H xi UH a fi UI 0) 1 0) a •• 4-> SH O IX ?i 01 CM fi O VH UH XJ TJ iS fi * 01 0 0 O 1 T J c OJ VH - VH a a 43 -H Oi II 0 2 0 a rH • 4-1 G O 43 o >t tO •H fi £ O TJ Ol - H VH 0 VH CQ hi •H o UJ 01 < o SH 4J rfl rH J TJ 0) CO rH 0 G OJ -H 43 43 01 ID rd l—t 01 II u •X O N fi G U fi 2S C 5 CD 43 G + * 43 a TJ < CJ X W -H 0 o T J -H V-i fi •H 44 * * a a C > TJ 4J II O 4J -3 fl * >i to ffl •X -X -X * * 01 rfl rfl ll VH TJ tO -H UI 01 VH G CO 01 o 0 0 VH o 0 D* U 0 4H o rj Tl CJ rH 0 rH UI - C * O 0 0 •X 1 i rH = fO 0 N rH u •X UH •X ffl 4-1 to hi U SH VH O 0 VH rfl •H •X 0 0 01 w SH TJ W V4 V rH 43 XI TJ •X 4-> 43 0 a O 0 a 0 0 fi fi + is U 4-1 VH .X. * fi 0 rH -H O 1 is" Tj U = a 4-1 a ""l VH T J r>- fi •X C c 01 < CJ - 43 TJ TJ -H VH 0) x QJ •H (0 4-1 fi TJ •r-t UI i rH fi 43 * •X -H O 4J rfl 43 J * 0) o U II II o G TJ rfl •H VH C TJ 43 •H - O CJ hi XJ 0) fi Oi 4J w A 0 0 o I - hi <D fi •H a UH 0) c fi CO a a CO - 0 M O -X V X) CO •H CJ a a -H •H PM * 43 TJ TJ 0 T J 01 VH •H rH o TJ SH a 01 VH &t X 4J 4J II U rfl * rH % •H hi a 4H X 0) rH a o TJ * £5 I I 1 UH 0 43 TJ 0) UH fi 43 4-1 •H 4J 1 •J 1 -H 43 S 43 4J 43 1 rH fi -H -H TJ QJ 0) O rH 43 CM W U T J s W 4-1 43 o VH 0) O c > •H CQ TJ rH CJ fi tO 4-1 ro wi O] o C CO II -H 43 hi 0) o 01 VH j CO 43 r H Ol TJ -H CO VH fi CM a a TJ Ui < O Ol CQ o S rfl 0 II o CM o tO Ui hi 43 G II II -X rH 43 a 0 TJ + TJ hi OJ a (0 01 •H * oi a TJ r3 rH 0 ffl >S + II 43 II 4J SH a < II >S CJ * ^ SH VH 43 T J •n 3 II TJ a c 4-1 3 n a T J •n * 01 -H • H rfl rfl fi | -H 0) 01 rrj 01 4H •H 01 3 TJ QJ 01 •H + 0 G 0 43 43 o rfl fi < 4-> (3 CQ O SH Ui o J 4J fi CJ to U 4-> VH TJ CJ CJ TJ 43 0 QJ 43 a OJ o rH > QJ CO 0 fi * fi 0 0 CJ a Oi o VH i—t II fi 01 rH fi rH II o VH rH 4-1 rH •X rH 4-1 4-1 4-1 rH fi -H II o OJ CQ -x 0 UH rH U O 01 * II 0 0 0 -* -X CJ Ol Ol Ol 43 ui to 01 43 01 TS TJ TJ * n TJ •H TJ •H OJ u TJ CJ •H • n 4H TJ VH * G fi fi C ^ C ^ C fi G -H ' -H -H * * * •X -X •H O O O O O 0 o O O O 0 r*-» * rH i—t rH TJ O U o TJ rH > * > * * * VH 0) * c CO •H 4-1 VH -H 44 G 0 VH rO QJ 4J e - H >i U •K Ol * -X u (0 0 G -f * * * -X c -H * * SH > -H rH * TS * o SH 4-1 -x C * •H 4H PM CM (0 10 •x tO CO 0) CM CM rH VH -H •x 43 * 4-1 o •H O CQ CQ a fi a 0 X 0) * OJ rH CJ CJ O O a 01 UH G 0 * W CO II QJ 0) 0 0 * fO 0) * 4-1 01 TJ SH 4H UH 4J VH G Oi 43 VH u CJ * 4-1 Q) O o VH * o o fi * O ro OJ 4J o O Oi * 4J 4-i Oi •X VH QJ rH o 4J 4-> C G VH fi * CO U CJ 2. * Ol O 1 hi •H 0 P3 * s 01 & •X G 4H • H VH SH hi TJ rH < •x CJ > > 01 •H CO QJ 4H 4J 4-1 0 0 fO VH 01 •X rH ii 43 fi fi 4-1 4J X 2 0 0 Ol •X UH rH rH TJ * a co a a G C 0 VH 4-1 fi •X o fO (0 * & a EM CM 4-> 4-1 -H •H T) II 0 rH •H * fi fi 0) 01 ft) m CM CQ fi fi O O G II VH rH rH •H 4-1 \ VH Oi Ol 4-1 * 01 m O o o a a •H O 43 4H ffl * * O •H •H o * UH 4-1 fi CJ 4-1 01 01 0) * 01 * * * * * * -H 0 01 O 1 U 01 4-> * (0 X TJ 01 rH 1 * OJ U M 01 * 43 43 4-1 0 —' «J -4J 0 TS fi SH tO UH a fi G rfl I tJJ 4J O o O TJ O TJ * TJ u 4J J J 01 * TJ 0 G •H SH I * 0) 43 * UI N tO VH (y SH O 1 fi + rH > SH SH 4-1 * •H H 43 01 •H SH I 0 + fO 01 0) -H fO TS 01 Ol VH OI SH SH I -H • H rH 4-1 4-1 O * Ui OJ 4-1 1 43 fi " G 0 1 01 TJ -H 4-> tO fi fi 4-1 fO SH SH Ol -H •—* •X •H -H -H * TJ fi fi -H -H * * II TS X 0 fi 4J VH 4J VH U 1 01 0) O O V4 * OJ >£> 4-1 43 O fO 0 OI X rfl UH 1 0 o> •x 4-1 U •H a a 0 rH EH UH G 0 SH U 4J G C U G 4-1 1 TJ CJ 0) 01 4-1 * 43 CM" in ti •H 0 rH 43 O 0 •H 0 O 0 r-. G i G * 0) fi * fi CO r*i TJ a 0 * 4J rH rH SH rH i—t rH w -H 1 01 OJ iS * 4J UH a -H o tn 4H 1 o TJ TJ hi rH 0 0 hi rH SH I G rH TJ * OJ •H a •H O TJ CM ll a VH C? tO TJ 4-1 - — ffl J a i -H V iS •H * TJ TJ H Ui Ui a * O rH X 4-1 H CO rH VH SH 44 iS T J •X 1 VH 1 SH •H O 0 SH - • H ,G 0 ^ VH - 43 tfl TJ •H CQ * * •H CM X X G 01 > rH hi O -H 4H rH hi O Xf 0 a -H 11 TJ fi C c CQ G fO •H 43 hi VH 01 43 J VH co - r—i hi i fi 1 QJ 0) 0) * 0 0 CO fi D VH CO hi •H fi D SH- J C7 43 hi I * O + 4-1 CO rH rH •n a Tj . o 2 0 r-. CO 01 o 2 0 — 01 fi 13 I Ol o II OJ •H CJ • H t? o tO ^ Ol TS rfl - TJ o 2 i G II 4-1 Oi 4J 4-1 4J VH SH VH < CJ UH UH 0 0 0 G II a - H II ^ - — 0* r~. TJ -H is + II U •X a * 4-1 G c G 43 * * * >S II 4-1 4-1 rH UH -H 3 ll UH 0 to 3 II UH '0 rH 01 " 11 i rH Tj •n •n + •H 4J OJ •H -H - H TJ a G 0 UH — 01 0 4-1 4-1 TJ — 0 4J 4J — — 3 II < a -H G 0) VH 4-1 TJ QJ QJ QJ 0) 0 •H UH •H 0 01 G - H C 0 4J G TJ 0 G CJ1 G 0 4-i TJ 0 0 a^  o CJ CJ n VH U fi a 4-1 4J 4-1 rH rH rH rH rH VH 0 01 fO VH •H rH •H tfl 4J VH -H rH -H 1 4J G < ! fa II * B 01 & 4J * * W CO CO 43 43 43 43 43 Ol a T J 0 O a II — SH 0 X 43 > 0 ll — VH 0 X > 0 01 rH 4-1 * fO QJ C fi 4J G G G fi fi fi fi fi c CO rH a TJ 0 G rH a TJ 0 UH G rH II O OJ Q M o * VH o o o O O O O o o UH rH CJ -H UH + 0 0 D 1 O 0 UH * * •n UH U * * 0 CJ CJ u TJ TJ TJ TJ TJ -H 0 UH VH - H u TJ SH -H U TJ < -rH ^ * •X •X * * * * 43 01 Appendix A. Program Listings 83 TJ * le •X 4c * le * XJ * 3 O * x TS * * 4J * Q) * rH + rH rQ o * Oi * 3 2 * £ * O * Ui 01 * TJ rH •H * QJ rt Ul rH G * b* 2 Xi bi bi * U 3 * •H £ * O Ul •H 4J •X £ TJ TJ UH * Q) bi rt -H -x rH G UH Xi * XI Q> •-^ •H QJ tn * 3 rH JJ JJ JJ TJ CM 3 * o JQ -X -X 4i rt rH SH * TJ 3 £ j5 j3 M rt QJ * 0 Ui > tH + TJ tn Ul QJ QJ Q -H £ + QJ o o Ul * TJ JJ QJ a * u o UH £ * u u o 03 rt b1 e o * OJ M -Q u ^ u -H Q o •X CM 3 •X * 1 QJ •P OJ * QJ o o o •X O G G - TJ c * rH rH OJ H 2 OJ TJ , OJ 01 0) -H o Xi + cn 04 o ll 03 rt bi bi U JJ 2 3 O II V tn JJ 4J 4J O 2 * CQ £ o 01 QJ u * TJ * TJ u rQ rQ * OJ M tn * £ Ui o •X CU Ul £ o -X 0) CM ll II rt ll o -H + -H •X TJ m ll o 4J £ II u Ul i-i OJ £ II - 0) < CQ * a •X UH II 2 < 3 XI JJ rt II II + -H 4-) * 1 c II JJ + + OJ OJ in 4J £ o 01 •H 0) 0) U a * Q) rH 3 rQ < CQ II II * e Ui 4J •X bl rQ * rt 0) £ 3 •X 4J 3 M r-, -H b1 2 p H O TJ £ o O U U -H •H TJ UH •K * * * * * O > ^ >1 >1 + 01 >1 01 rQ 4t rQ 3 QJ * 3 O rH 4i O X •x * T J rQ r£ 4t T J £ 4s * 3 4i 4! * QJ •X * 0 + T J 4" rH X T J C •X X •X -X £ rt 4i £ £ •X QJ -X OJ rt •X -X CQ r£ * •X G 0) X 4J •X JJ 0) G j J •X £ rH -Q 01 £ u •X 3 rH •H OJ •X JJ o II 4J •X •X - c -x T J A * SH r£ •H X * r£ O •X •X * G r£ •X * X Q) * •X Ul •X Q) rQ rH QJ + •X -X SH * rH O X 4i rQ •X X O - 4" X3 £ 3 QJ -X JJ Ul 4i 3 •X O U u O QJ •K •X T J -Q -X 01 o T J JQ 3 > 4J U •X O u -X T J •X X T J -X QJ 4> >S + SH 4t £ •X 0 > •X (J 3 QJ 01 •X 4" 0) O 4J * rH -X c 4J 4" r£ rH •X £ •X o 3 4J •X m •H 4t JJ 01 * •H a rH 4" j J £ * JJ C 3 •X £ * •H •X 3 -H U) •rt £ JJ •X T J rH 01 QJ E •X 1 o i SH •X X -H 4t > > X X X 4" £ £ r£ 1 * = -X •X O o 4" 4i U * rG OJ rt •X u u X >t 01 O - rH rH X SH rH rQ -X rQ SH •X rt 3 J j * 3 0) W rQ 0 M G X O rH •X O T J O 0 + T J •X rH — r£ -H A UH £ -X bi T J Ul JJ T J JJ SH 1 a X 1 •- X £ 3 > > •H •- 4J •K > X £ •rt JJ QJ G £ SH JJ 3 £ - QJ u QJ •X T J O O QJ U 3 a O •H rH a 4< 3 CJ u 4i £ tn a J J + u * rH 03 0) £ 3 JJ * •X O T J T J X 2 Q M O •X T J £ *w C -H •H 4i •H •H -H * * * -X •X •H O O -X 4- 4i 0 •v. -v =tt > > ~-- ~-- > — x 4" 41 4i 41 41 •X 4t 4i 4i 4t JJ * o 4i £ 4i TJ 4i * SH QJ H JJ O QJ O o 41 -X Ul £ •X * 2 =tfc •X O U u 4t 3 QJ TJ o -X < rQ £ 4( £ rt X * SH 3 VJ * QJ Ul £ TJ •X , £ W QJ £ •X •X 4J rH O £ U rt -X •X •H Q) JJ o a iH -X •X QJ G u 01 TJ •X 4( G 0) P- £ TJ QJ •X En 4( rG rt > rt rt > 4i rH •X bl rG JJ SH o rt -X 4i 3 U tn 4t II 0) JJ •X O rH 0 •X a -H 4" SH bl £ 0) JJ o o 4i s X •X rG G bi £ JJ JJ 4i QJ QJ J J QJ •K 4J -H -H £ u 4i a a TJ tn rt OJ bi bi •X rH 4" rH Ifl rfi JJ OJ rt 4i J J TJ JJ QJ a ftJ 4H cy u E rH 4i i 4H 01 I G •X G a •H UH MH 41 x: TJ rG G •X bl rG tH o 4i u QJ rt > QJ QJ U rt rH - H bi 0) a 4i rH O rt rH ,G 4i QJ tn - H TJ QJ 4i SH rQ TJ XI to xa xa u3 U QJ £ 01 rt > 41 M a 03 3 o o 3 3 + £ tn rH a J J £ o OJ QJ 4i r£ O -H TJ TJ O 0 4J OJ + rt tn >i 1 3 CO £ 4t 4i * u TJ 4i 4i 41 TJ TJ U rH JJ r£ rt rt Xi TJ o o 0 4i 01 QJ 4i 4i < OJ OJ En U a H u -H TJ TJ 2 4i rH rH JJ 4J bi 3 3 ty U TJ •X XI xa Ul Ul 0) OJ a U XI * 3 3 £ £ E 4J JJ G £ £ 1! O II V O O O o 0 G G JJ -r> O M II J j X G 4i TJ TJ CJ u rH •H -rH II II C •X o 4i -H 0) IH QJ -X -rt •X rH •rt b1 a J-> P4 9* o •X JJ •X 0) U u £ II 41 a * G 4i 4i J J J J 4J UH 0) JJ JJ * •H JJ 4i £ G 1 JJ JJ 1 •X M JJ 3 41 rt QJ OJ QJ -rl -G c QJ xi 4i QJ u 3 a 4i r£ rH rH U •H rH u SH 4" £ Ul a J J 4i V rQ xa rQ CD SH QJ O rt QJ £ 3 4i 3 3 3 £ a TJ UH 41 2 Q H O 41 TJ O O O O MH UH 41 -H TJ TJ TJ rH •H •H 4i 41 4" 4" 4i 4< 4i 4t OA -rl C b 1 — -H a a —, 1 £ £ J J QJ J J J J — TJ X 41 a rt b 1 -H r-. 1^ u O JJ JJ * 4i i—• + — a JJ + + —. J J -H •H >—• D* a a H U £ £ * + J J 4J r-. 4i * JJ J J •r~i U ,_ , r_, •H D1 H II + —- J J JJ O u — OJ tn 41 01 H a — •— II J J XI TJ + -H 0 1 rt II n II II G u V UH xi -H 1 •H D1 r-, U | £ & a J J J-l 1 0) -H QJ £ £ " xa TJ u bi J J JJ H a a OJ o UH QJ II 1 j J • n JJ QJ 4i . — r H )H QJ O TJ O J iJ o O TJ •d -5^ G G rt rt o •—• — OJ QJ > > rt rt co CO o — oi 0) > > OJ rt co CO o O TJ TJ -0 XI XI o O TJ TJ -U H O o c c 10 10 (H II II II II M O 'ri M CV 01 g ^ o o rH ^ ii d d ~ 10 (0 O rl rl Appendix A. Program Listings 84 G T J G •r-i G 01 -H 0) 01 rt 3 Ul G -G SH O G •r-i O J J -H O O G > G T J 01 rd QJ T J 0) SH •H rH u 0) J J G 3 Ul a C SH G 0) SH 3 Ul C 01 3 Q) rH JJ •r-i T J 3 SH j J 0) rt XI X rt JJ SH O rt 0) o 3 Ul 0) EH rH Ul •H U •r-i u •rH J J C C ^ o 3 0) JJ 01 > > J J T J G rt rt rt G Oi a Ul Ul CO 01 01 CQ T J UH o > a < XI G Q) Q) o T J rt 0) tH XI •H > 0) T J J J * CO T J 2 T J ITJ G rt o G rt - CO o Ul T J •H *> 0) — o XI T J * •H II SH QJ T J G o 0) O 0) I II 0) > * 3 T J 01 rt Jj 3 > Ul VJ rH rt S-j * T J G J J 0) J J 01 rt O X J CO JJ rt rt CO T J CO 01 rt O C JJ O T J 0) 0) o G rt tH T J -H Ul rH G JJ 0) T J 0 XI G * VJ •H >i JJ X-1 3 1H 01 01 > rt SH UH * rH SH J J rt JJ T J •H u rQ rt 0) T J JJ T J Ci G rt 3 rt JJ rd Ul G QJ G >, OJ • H O 0) C 01 Ul 01 JJ •H •r-i N X! -H rt 0) XJ Ol rd 1 rd Q) •H - o J J JJ H rH oi u SH Ul jJ rH Ul T J T J c 01 •r-i rt u C 01 T J rt xa rt * 0) JJ o JJ QJ o 0) rt a rt Oi T J rt o i—I O U 2 tH u 0) o G EH OJ J JJ xt G rt JJ VH c Ul XI o 01 rH 2 r9 G 3 OJ 01 rd o rH 0) Ul xa + * M T J T J -H O Ul 01 Ul 01 J J SH > T J rH •ri rt + PS •r-i * T J -H •r-i o UH O •r-i -H UH rt O <N S rH 01 * e Xt rd o 2 EH C •r-i rH II M II + * a e G G G UH JJ SH 0) JJ 3 tH iJJ > II + r-i c 3 o 3 T J 3 UH O SH G T J Q) G CQ •ri o IH -H T J T J rH a 01 U o UH Ol £ rd •H •r-i Ul 0) T J < 1 T J r-i II •H G 0) G Jj o G T J rH 1 •H a * •r-i tH 01 — -H e * T J • n + - -K rt Ul 0) U Ui c o G Ul o o 1 2 01 >t * 3 r* •ri e -H rV 3 •r-i •rH T J rH rt O e 2 T J Ul >1 V -H T J o -X > ex rG rG 0) rd VJ 3 3 CQ Ol J J •ri -H -H rH •H II •ri M T J G G JJ o JJ QJ C J J T J < C O 0) 1 XJ tH A T J •H O rt JJ rH SH T J T J -H tH o — G G > rH Ul rd *n T J o M •ri •K rH -H G X) 3 01 G G o 2 rt xa O EH V o -H CQ 01 rH o rt j J Ul rt 01 a u rt 0) II G o r- rH V < 01 (N Ul 11 01 -H II J J Ul > Ol >t "> II 0 T J E - rH •ri II o — II + EH c- e 3 T J JJ 0) rd -H G •r-i -H JJ II rt a G rQ II CQ 2 T J o O rJ rt rt XI U > SH u a Ol O u UH 0) rt JJ II 3 < o -H rH O 01 o rd G rd 0) e rH Oi Oi a 3 T J a JJ u II IH c T J V T J EH M T J V H •X V ~ rS XI J J 3 CO JJ Ul SH G G e Vj OJ UH G UH 01 G -H -ri rt •r-i T J 2 T J II •ri CN T J OJ o O 0) 0) •r-i O u O O 01 JJ O -H 01 e O g * •ri II -H •X - n O * G G JJ T J OJ T J £ C 0) c rH JJ a 0] J SH 0 o 3 ll > X) * • n < H rt rt rt •x Ui C * rt G Oi T J Xt rd O a 01 T J VH •ri O T J l T J > T J SH SH SH •r-i •ri VJ rt rt G 6 SH u u 01 * U T J rH u •ri >. O T J •ri 01 •ri •ri T J II •ri 0) o rt UH rt Xi rH rt 3 • n •r-i •H rH •ri -X •ri 01 -X •r-i •x 0] SH •H •H II •H X 0> OS G -H G S -H a u UH SH G 0) Oi JJ JJ XI w JJ —- O >, * rH rH 01 rH j J c rt rt 3 XI rt r-. -H 0) UH -H ' T J XI o 1 X! C o J J J J O H JJ UH -H U-l 3 3 - 3 •r-i rH 01 Ul T J 01 -rH •rH r ^ Xi * e II 3 TJ 0) Q - n II 5 > „ : >, -H n -•ri II •—• II >1 > < e 3 CQ T J < •H E^ 2 >1 V II •H -H E II ... 3 O T J >i 11 -H •H •H Ul 1 Ul JJ G 0) 0) -ri rH rH X J xa rt rt U EH EH o c G UH * * OJ * * * rH * * xa * rC 3 * O TJ * TJ * C + * rd + CQ * — rQ * G J J G * 0) u Q) * rH o rH * rG II * J J Ul A * G < * + -H a * G * * X 01 * rH rH * rQ •K SH * A O * J J 01 * QJ CQ •K U SH * rH G QJ O * xa QJ > J J * 3 M x ; + O * o UH 01 * TJ rG x : 0 > * iH * * o 1 G J J * <, U u rX 1 Xi * O 3 J J * d + M * •H a rH * W H-•ri -H J J C 3 * rH •H + o * 3 •rl U * 1 X + II X * rH 0) * J J UH G CQ •ri A O I SH * G G QJ Jj SH G + M + M + * > > -H G 3 QJ + •- X * c c XJ 1 * rX rH •H jJ rH •ri O G * 0 0 j-i 0) V II •ri 01 -rH * u o rt >i * rt •ri A r-t -H A rH * CQ G r* >1 V G >1 * * J J O OJ II -ri 0) II J J c G II •H rH * G * SH -H QJ -H V II - II o * o 01 rH •r-i o G O rX * •r-i * xi II •r-i 0) II — •H * J J * Ui G VH o * a -• * o 0 11 •ri II •H SH * -rH - - J J * > rH •r-i r^, UH -H o •ri — O G SH J J 3 * G ~~~ >1 UH ~~~ >1 4H ur •K me U Ul 3 a * a J J * CO SH • - ' u J J * rt QJ G 3 * O U-l fo re * * 2 * Q •K W O * * * * TJ -H o > — •H H ^ o -X + •X -X •X •X •X •X •X •X •X •X •X •X QJ -X •X > •X -X rt •X CO •X * QJ 0 •X > T J * •X rd •X •X CO * 0 j J •X T J G + X •ri Jj * x c T J •X •ri rt * o * XI * -X T J o u rd T J •X -X o -X •X XI -X 0 JJ •X o •K T J G •X G -X •ri •X 6 -X G •X JJ •X rt G •X u •X •ri •X X T J •X -X -H * •X •X * •X -X T J 01 •X -X = -ri C •X -X Xi * o •X -X rH •X X r-i Dl •X •X rt G e •X xa o u •X O rH o * •X rH — c •X •X 01 r-i T3 X •X = G G + •X rt rt •X •X Q) H SH •X T J •X 3 OJ OJ •X •X rH r-i rH •X o xa xa * •X G =» 3 * -X * * •H O 0 * T J T J Appendix A. Program Listings 85 ... e x: s 3 H TJ •H M II * II + 6 II | IQ um , , • n TJ • n >1 M •H •ri TJ o > ~" -H * II A um -H • n TJ O V •H CO r - M V < o II B+ * g NT II £ < £ < 3 V TJ tH TJ V •rt TJ 2 TJ II -H £ * •H II •H * • n 3 * •r~, TJ TJ •ri II -H 4H 04 ui SH x; •H •ri if rH 01 fo a g H 3 * TJ I * g 3 ~ - TJ O £ » - 2 >i v -7 S 3 -a < 3 M ~ C/J H T3 Q T I II O ( • H Z - T J •-c a 44 c - H rH J J - H M 3 rH SH xa o m 44 rH rd G i_) rd o TJ 0) N CN - H 0) Ul X ) rd 01 IH rH 0) xa ui to • H tH O c 2 G ai + a o TJ • H J J o > c .J o TJ g 5 XI o TJ 0) QJ > > rd fd co co o o TJ TJ TJ TJ rd (d II D 1 Ul TJ TJ Ul - - H e e - — 3 3 CN O 01 TJ TJ > • O • H - H * H H "—' "—' CN * r j cn > ll o — _ a rH 01 II Ul G G + A ... 01 O >i £ G j_t Ol o 1 rd rd CM u 4-> - H QJ CN o 01 Ul u SH > cr rd • H a II JJ £ rH Ul OJ rl o + * * Ul u JJ SH 44 rH - H rH o o rH S4 J J rd * QJ 3 QJ G o CN xa II > SH -44 CN Ul 44 QJ > II SH £ c JJ 3 U 1! CN CN tJ1 * > 01 Ul (d 3 6 rd G o rt II QJ Ui rH 0) O CO £ jJ c U - H TJ 4H 4J II II rH > rH G o G Ul i—1 o 01 01 fd 01 D* - H II II II u II S4 rH o TJ S4 SH QJ o O QJ Ul CN Ul XJ JJ 4J 3 QJ JJ 3 0) 44 * rH • H - H rH - H > > u 3 O QJ Ql jJ Ul QJ J J OJ 0) xa 4 J 4J xa o rd ui Ul 0) rH Ui QJ if els >ubl nop sta sta nop if TJ 44 01 - H S4 QJ • H SH 5 p . •H -rl _ S (I) to tu --I (0 OJ EH rH OJ n M To EH ° C O a S OJ 0) > > 10 10 in co TJ T l — Ul 3 _ -10 TJ o to OJ TJ TJ * -H •fc TJ TJ TJ > o •H £ O -H -H -H CQ 0i > A Ol * J J > — — CN + SH TJ < G c O QJ tH rH > II o QJ •H E4 o & o 01 II Ul C C + A rG •K O 2 rH QJ O >i £ rH c JJ 01 rd fd CN o JJ II JJ -H 0) o 0) Ul rH rl > D 1 fd O 01 >i > II •H a II * JJ rH Ul 0) u O * Ul — U 4H J J G G •H •H JJ n u 4H •H rH o o H jJ rd * 01 fO o o 3 -—- OJ r? c 0 H rQ II > •—' SH 44 CN Ul Ol 01 a TJ 44 QJ > II u rS G JJ 3 u 11 CN CN D1 * > Oi c G £ rH fd Ul rd & 3 TJ fd c o rd II QJ Ul rH CN o o QJ JJ o QJ o CO £ jJ G u •rl TJ 44 JJ ll II > c O G c rH rH JJ a Ul XI Ul rH o QJ QJ rd QJ D 1 -H II II ll SH II U rd 44 0 rH U TJ JJ U SH QJ u U QJ Ul rH CN Ul J C JJ J J 0) JJ 3 rH X o U QJ o TJ 0) 4H * rH -H •H •H > > SH 3 O QJ QJ JJ Ul 01 jJ • n •H •H rH -H + 0) 0) rQ JJ JJ xa o rd ui UJ 0) rH Ul QJ QJ 01 JJ JJ XI pa JJ Ul rH fd rd TJ 4H 01 •H u QJ •r-i SH rH JJ G rd rd 3 rd 44 rH X I o J J JJ 0 44 rQ G O JJ JJ 0 H J J 44 •H 01 nop TJ Ul Ul TJ •H * 3 o TJ ^ •H rH Ul Ul TJ Pu Ul •ri T G fp XI Oi fp rD G 2 •ri TJ || rd II 01 SH 0) S4 rH = O rQ rQ rd U rd EH G JJ rd 4H - TJ o rd QJ j J CN N rd 01 -H TJ rH Ul xa CN fd „ 0) EH 0) rH 0) rH rQ Ul rQ rd •ri rd EH O EH 01 2 G Ul <-8 •H G o 0) 2 a •k 0 TJ G J J •rl 0) o a G > O rd 44 u = TJ II rd 44 QJ a 44 nt fr -ri u QJ a Ul 44 rH •rl 0) s - > 3 CQ . •° < J -H £H tO « ' > ; ? « • - h ^ i -s rH CO tO a • o H to tu II c H -H C XI it 10 - U II EH C — C - H - H 3 II > T J SH - r " i • H >, O * - H 4H 

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-0065393/manifest

Comment

Related Items