COPYRIGHT AND CITATION CONSIDERATIONS FOR THIS THESIS/ DISSERTATION o Attribution — You must give appropriate credit, provide a link to the license, and indicate if changes were made. You may do so in any reasonable manner, but not in any way that suggests the licensor endorses you or your use. o NonCommercial — You may not use the material for commercial purposes. o ShareAlike — If you remix, transform, or build upon the material, you must distribute your contributions under the same license as the original. How to cite this thesis Surname, Initial(s). (2012) Title of the thesis or dissertation. PhD. (Chemistry)/ M.Sc. (Physics)/ M.A. (Philosophy)/M.Com. (Finance) etc. [Unpublished]: University of Johannesburg. Retrieved from: https://ujdigispace.uj.ac.za (Accessed: Date). MODULATION CODESFOR MOBILE COMMUNICATIONS by Pieter Gcrt Wessel van Rooyen TlmSIS submitted as partial fulfillment for the requirements for the degree MASTER or ENG INEERING in ELECTRICAL AND ELECTRONIC ENGINEERING in the FACULTY OFENGINEERING at the RAND AFRIKAANS UNIVERSITY SUPERVISOR: PROF. II.C. FERREIRA June 1991 -\--~\U t=>OJ:) DEDICATION Dedicated to my God, who gives me tnlents to develop and the ability towork, and to my wife, Venessa, who gives me the freedom and latitude to do so. SUMMARY This thesis sets alit to a theoretical and experimental investigation ofcommunication systems, in particular digital communication systems. Finite-state machine representations of modulation codes arc investigated and a procedure to map a class of coding rules into fixed rate state systems arc presented. The performance of binary modulation codes on recording channels have been studied fairly extensively. this is usually not thc case for other bnndlimited channels, and this thesis addresses the gap: various modulation codes were transmitted through filters with various cut off frequencies and slopes to obtain quantitative results for modulation codes through bandlimited channels in general. As application of the above results, a selection of constrnined codes were studied for clock extraction when transmitting data over bandwidth-limited, voice band VHF FM mobile communication systems. OPSOMMING llicrdie t«;sis behandel 'n tcoretiesc en ekspcrimentele ondersock van kommunikasiestelscls, in die besonder digitale kommuniknsiestelscls. Eindige-tocstands·masjien-voorstellings van modulasiekodes word ondersock en In metodc om 'n klas vaste-lengte kodes op die masjienc af te beeld, word aangebicd, Die verrigting van binere modulasickodes op opnemer kanale is alreeds goed ondersoek, wat nie die geval is vir onder bandbeperkte kanale nie. llierdie tcsis spreek die gaping aan: verskeie modulasiekodes word deur filters met verskillende afsnyfrekwensies en hellings gestuur om kwantitatiewe resultate te vcrkry deur bandbeperktc kanale. As toepassing van bogenoemde resultate word 'n paar spcsificke modulasickodcs bcstudeer vir klokhcrwinning oar mobiele BHF FM kommunikasiekanale. ACKNOWLEDGEMENT I am indebted to many for their advice and assistance during the period of this study; suggestions and help from my fellow students, in particular Francis Swarts, who never hesitated in spending hours to be of assistance to me, and to Prof. Il.C. Ferreira for the constructive suggestions and guidance throughout the project. CONTENTS PAGE LIST 011 FlOURES LIST OF TA8Lru; vi usr OF SYMBOLS viii I) INTRODUcnON 1 2) MODILE COMMUNICATIONS 6 2. l) Analog vs Digital 9 2.2) Digital Signaling Over Fading Mullipath Channels 12 2.2.1) Free Space Lost 13 2.2.2) Attenuation 13 2.2.3) Multipath 14 2.2.3.1) Delay Spread 15 2.2.3.2) Rayleigh Fading 15 2.2.3.3) Doppler Shift 17 2.4) The Cellular Concept 18 2.5) Present Coding Techniques 21 2.5.1) Spectral Efficiency 22 2.5.2) Narrow Power Spectrum 23 2.5.3) Intersymbol Interference 24 2.5.4) Clock Extraction 25 2.6) Cellular Radio in the R.S.A. 25 3) THEORY OF FINrI'E-STAffi MACIIINr!.S 28 3.1)The Finite-State Model 28 3.1.0 The Basic Model 30 3.2) Predicting Machine Behavior 31 3.3) Trnnsition Tables, Diagrams and Matrices 32 3.3.1) ThcTransition Tables 32 3.3.2) TI1C Transition Diagram 34 3.3.3) TI1C Transition Matrix 36 3.4) Classification of states 37 3.5) Equivalence and Minlmization 38 3.5.1) StateEquivalence 38 3.5.1.1) k • Equivalence 41 3.5.1.2) k - Equivalence Partitions 42 3.5.1.3) Consnuction of Pk Tables 43 3.5.1.3.1) Construction of the PI Table 43 3.5.1.3.2) Construct ion of the Pk+1 Table 44 3.5.2) Machine Equivalence 46 4) MODULATION coons FOR CLOCK r~RA(.'TJON 48 4.0 Introduction 48 4.2) Finite-State Transition Diagrams 53 4.2.1) Synthesis Algorithm (or Modulation Codes 55 4.3) Spectrum of RLL sequences 56 4.4) Fixed-Length Binary RLL Codes 59 4.5) Variable-Length Binary RLL Codes 61 4.6) DC-Dalanced Codes 64 5) NEW FSM RRI'RESENTATIONS FOR MODUI.ATION CODr!S 66 5. I) Converting between Isomorphic Machines 67 5.2) Mapping Fixed-Length Coding Rules on FSM's 74 6) NEW RESULTS ON (0,k) MODUl..ATION CODES 80 6.0 The TS Algorithm 82 7) ExPERIMf!NI'AL SET UP 99 7.1) Design Descriptions 100 7.2) Experimental SetUp 102 8) FREQUENCY DoMAIN INVESTIGATION OF MODULATION CODES 105 8.I) Experimental Spectral Analysis 105 8.2) Spectra of Modulation Codes 107 8.3) Modulation Codcs Through Bandlimlted Channels 108 8.4) Modulation Codes for Mobile Communication Channel 113 8.5) Modulation Scheme Spectra 114 9) MOI)ULATION CODES ON DIGITAL MOnu.F. VIIF CIIANNFJS: Rp.AL TIME EXPr!.RIMENTS 134 9.1) Mobile VIIF Experiments 135 9.1.1) Gnp Distribution 137 9.1.2) Durst Distribution 137 9.1.3) Burst-lnterval Distribution 137 9.1.4) Cluster Distribution 137 9.1.5) Error-Free Run Distribution 137 9.2) Results 138 9J) Channel Models 147 10) CONCLUSION 149 ApPENDICES A) IIARDWARE DrlSCRwnON 151 A.I) Programmable Logic Devices 153 A.l.t) Design Implementation of GAL's 154 A.2) Which Processor? 156 AJ) Random Access Storage 159 A.3.t) Static vs Dynamic 159 AA) The Tri·State Concept 160 A.5) The Phase Locked Loop 161 A.6) Design Descriptions 167 A.6.l) DSP Finite-State Machine Generator 167 A.6.2) Timer Card 170 A.6.3) Mobile Coders 171 n) PROGRAMS FOR DSP FSM AND PC DECODER 173 C) PROGRAMMES FOR Monll..E ExPERIMENTS 178 D) ERROR DISTRJDlTI10N RF.5UL1'5 184 E) PROGRAM FOR MF.ALY TO MOORE MACIIINE CONVERSION AND FSM MINIMI7..ATION 209 f1 GAL UsnNOS 226 G) PC TO TMS PROGRAM M(~ORY TRANSFF.R PROORAM 232 II) liP 49258 ClOCK RECOVF.RY CIRCUIT REFERENCES 238 239 UST OFFIGURES FIGURE NO. TI1l.F. PAGE 2.)) Receiver Quieting Curve 11 2.2) Radio Propagation in Urbnn Areas 14 2.3) Illustration ofDelay Spread 15 2.4) Fading Signal Received while Mobile is Moving 17 2.5) Cellular Architecture 19 2.6) Frequency Reuse 20 2.7) Typical Power Spectrum 23 2.8) Transfer Function of Mobile Communication Channel 24 3.)) Branch Labelling 35 3.2) Machine Al 36 3.3) Types of Branches 38 3.4) Machine A2 40 3.5) Machine A3 44 3.6) Machine A4 47 3.7) Machine A5 47 4.)) Finite-State Diagram for (d, k) = 0.3) 54 4.2) Coders for a rate R=1/3, ClI, k) = (3, 7) Code 56 4.3) Spectrum of MFM Code 58 4.4) Spectrum of Maxentropic RLL Sequence, k Constant 58 4.5) Spectrum of Maxentropic RLL Sequence, d Constant 59 4.6) MFM Code (NRZI) 60 4.7) MFM Code (NRZ) 61 4.8) FSM Encoder for ~i, k) =(l , 7) Code 62 4.9) Decoder for ~i. k) = (2, 7) Code 63 4.10) Spectrum ofa rate R =1/2, fll, k. C) =(0. 1, 1) 65 5.)) State Diagram of the Miller Code 69 5.2) State Diagram of Moore Machine 70 5.3) Minimi7.cd Moore Machine 71 5.4) State Transition Diagram of the vi, k, C) = (0,2.1) 72 5.5) State Transition Diagram of Moore Machine 73 ii 5.6) Basic Block Diagram of BW Algorithm 75 5.7) Block Diagram for Example 5.2 76 5.8) State Transition Diagram 78 6.1) Exhaustive Search vs TS Algorithm; k =4 85 6.2) Exhaustive Search vs TS Algorithm; k =5 ' 85 6.3) Time for Exhaustive Search: 1 S k S5. 14S n S 20 86 6.4) Time forTSAlgorithm: 1 :S k S 5. 14 S II S 20 86 6.5) Valid Codewords for k = 1. 2 S II S 20 87 6.6) Valid Codewords fork = 2. 2 S II S 20 87 6.7) Valid Codewords for k = 3. 2 S" S 20 87 6.8) Valid Codewords for k = 4. 2 S II S 20 88 6.9) Valid Codewords for 1 S k S 20. 2 S II S 20 88 7.1) Block Diagram ofTMS 320C 10 DSP Card 101 7.2) Spectra of Miller Code 101 7.3) Block Diagram for Timer Card 102 7.4) Block Diagram for Mobile Coders 103 7.5) Block Diagram for Bandpass Experiments 103 7.6) Block Diagram for Mobile Experiments 104 8.1) Spectra of (d. k) =O. 3) code on Linear Scale 106 8.2) Spectra of (d. k) =0.3) code on Logarithmic Scale 107 8.3) Transfer Functions of Filters Used 109 8.4) Filter Set Up for IIighpass Results 112 8.5) FiIter Set Up forLowpass Experiments 112 8.6) Filter Set Up forBandpass Experiments 113 8.7) Spectrum ofPN·Seqllcnce on Linear scale 115 8.8) Spectrum ofPN·Seqllcnce on Logarithmic Scale 115 8.9) Spectrum of (d. k) = (0. 3); LinearScale; R=8/9 116 8.10) Spectrum of (d,k) = (0.3); Logarithmic Scale; R=8/9 116 8.11) Spectrum of (d. k) = (0. 3); LinearScale; R=11/12 117 8.12) Spectrum of (d,k) = (0.3);Logarithmic Scalc;R=11/12 117 8.13) Spectrum of (d. k,C) = (0. 1. 1); Linear Scale 118 8.14) Spectrum ofvi. k, C) = (0. 1.U; Logarithmic Scale 118 8.15) Spectrum of (d. k, C) = (0. 2. 1); Linear Scale 119 8.16) Spectrum of (d. k,C) = (0. 2.1); Logarithmic Scale 119 8.17) 8.18) 8.19) 8.20) 8.21) 8.22) 8.23) 8.24) 8.25) 8.26) 8.27) 8.28) 8.29) 8.30) 8.31) 8.32) 8.33) 8.34) 8.35) 8.36) 8.37) 8.38) 8.39) 8.40) 8.41) 8.42) 8.43) 9.0 9.2) 9.3) 9.4) 9.5) 9.6) 9.7) 9.8) 9.9) 9.10) iii Spectrum of (tI, k) = (l, 2): LinearScale Spectrum of td, k) = (I, 2): Logarithmic Scale Spectrum of td, k) = (l, 7): LinearScale Spectrum of (tI, k) = (I, 7): Logarithmic Scale Spectrum of (tI, k, C) = 0, 4, 3); Linear Scale Spectrum of (tI, k, C) =0, 4,3); Logarithmic Scale Spectrum of (tI, k, C) =0, 5,3); Linear Scale Spectrum of (tI, k, C) = 0, 5,3); Logarithmic Scale Spectrum of (tl, k) = (2. 7); LinearScale Spectrum of (ti. k) = (2, 7); Logarithmic Scale Spectrum of (tI, k) = (3, 7): LinearScale Spectrum of (tI, k) = (3, 7); Logarithmic Scale Spectrum of (tI, k) = (4, 7): LinearScale Spectrum of (ti. k) = (4, 7): Logarithmic Scale Spectrumof (tI, k) =(4, 8); LinearScale Spectrumof (tI, k) = (4, 8): Logarithmic Scale Spectrum of (tI, k) = (5, 9): Linear Scale Spectrum of (ti. k) = (5, 9): Logarithmic Scale FFSK Spectrum ofPN-Scquence FFSK Spectrum of (tI, k, C) =(0, I, 1) Code FFSK Spectrum of (tI, k, C) =(0,2, 1) Code FFSK Spectrum of id, k) = 0,3) Code FFSK Spectrum of id, k) = 0, 7) Code FFSK Spectrum of td, k) = (2. 7) Code DPSK Spectrum of PN-Scquence QPSK Spectrum of PN-Scquence 8PSK Spectrum of PN-Scquence An Error Sequence with Error Events 4-Ary PSK Signal Constellation 8-Ary PSK Signal Constellation 4-Ary PSK Signal Constellation in Fading Condition 8-Ary PSK Signal Constellation in Fading Condition SNR of (tl, k, C) = (0, 2, 1) Code on Highway SNR of (tl, k, C) =(0, 2, 1) Code in City 4-Ary PSK in city Environment Error Distribution for QPSK in City Environment Modeling ofSuper Channel 120 120 121 121 122 122 123 123 124 124 125 125 126 126 127 127 128 128 129 129 130 130 131 131 132 132 133 136 138 139 139 140 140 141 144 147 148 10.1) A.}) A.2) AJ) A.4) A.S) A.6) A.7) A.8) A.9) A.lO) A.I t) A.12) A.13) A.14) A.lS) A.16) A.17) D.}) 0.2) OJ) 0.4) 0.5) 0.6) 0.7) 0.8) 0.9) 0.10) 0.1 I) 0.12) D.13) 0.14) 0.15) 0.16) 0.17) iv 4-Ary PSK Signal Constellation TIle GAL, a Great Performer Static Memory Dynamic Memory The Tri-State Memory Block Diagram ofPLL Frequency Multiplier Block Diagram PLL Multiplier Bode Plots of Loop Gain Loop Galn Memory Elements PC Address Decoding Memory Decoding for the TMS 320ClO TMS 320ClO Digital Signal Processor TMS 320ClO I/O Ports Composed Circuit Diagram for DSP FSM generator Circuit Diagram for Timer Card Circuit Diagram for Mobile Coder Error Distribution: (cI.k,C> = (0,2,0; QPSK in City Error Distribution: (cI.k,C> = (0,1,0; QPSK in City Error Distribution: (cI, k) = 0, 3); QPSK in City Error Distribution: (cI, k) =0, 7); QPSK in City Error Distribution: id, k) = (2, 7); QPSK in City Error Distribution: (cI.k,C> = (0,2,0; QPSK in Hgw Error Distribution: (cI.k,C> = (0,1,0; QPSK in Hgw Error Distribution: (cI, k) =0, 3); QPSK in lIgw Error Distribution: td, k) = 0, 7); QPSK in lIgw Error Distribution: (cI, k) = (2, 7); QPSK in Hgw Error Distribution: (cI.k,C> =(0,2,1); QPSK in City Error Distribution: (cIt,c> =(0,1,0; QPSK in City Error Distribution: (cI, k) = (J, 3); QPSK in City Error Distribution: u. k) = 0, 7); QPSK in City Error Distribution: (cI, k) = (2, 7); QPSK in City Error Distribution: (cI.k,C> =(0,2,0; QPSK in llgw Error Distribution: (cI.k,C> =(0,1,0; QPSK in Hgw 150 155 159 160 161 161 163 164 165 166 168 169 170 170 171 172.A 172.B 173.C 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 vD.18) Error Distribution: (d. k) =(1.3); QPSK in Hgw D.l9) Error Distribution: (d. k) =(I. 7); QPSK in Hgw D.20) Error Distribution: (d. k) =(2. 7); QPSK in Hgw 202 203 204 vi UST OFTADLES TADLR No. TI1l.I! PAGE s.» General Transition Table 33 3.2) Machine Al 34 3.3) Machine A2 41 3.4) PI Table for A3 45 3.5) P2 Table for A3 45 3.6) P3 Table for A3 46 3.7) P4 Table for A3 46 4.)) Capacities VS Runlength Parameters d and k 52 4.2) C and DRvs Minimum Runlengthd 53 4.3) Comparison of codes 54 4.4) Coding Rules for MFM Code 60 4.5) Variable-Length Synchronous (2, 7) Code 62 s.n State Tmnsition Diagram of the Miller Code 69 5.2) Check for Moore Equivalent States 71 5.3) Truth Table for Example 5.2 77 5.4) State Transition Table 77 5.5) Present State- Next State Table 78 6.1) CandidateCodewords for Example6.1 83 6.2) k =1, C(O, 1) =0.694242 89 6.3) k = 2, C(O, 2) =0.879146 89 6.4) k =3, C(O, 3) =0.946777 90 6.5) k = 4, C(O, 4) =0.975225 90 6.6) k = 5, C(O, 5)=0.988109 91 6.7) k =6, C(O, 6) =0.994192 91 6.8) k =7, C(O, 7) =0.997134 92 6.9) k = 8, C(O, 8) =0.998578 92 6.10) k =9, C(O, 9) =0.999292 93 6.11) k =10, C(O, 10) =0.999647 93 6.12) k =11, C(O, 1))=0.999824 94 6.13) k =12,C(O, 12) =0.999912 94 vii 6.14) k = 13, C(O, 13) =0.999956 95 6.15) k = 14, C(O, 14) =0.999978 95 6.16) k = IS, C(O, 15) =0.999989 96 6.17) k = 16, C(O, 16) =0.999994 96 6.18) k = 17, C(O, 17) =0.999997 97 6.19) k = 18, C(O, 18) =0.999999 97 6.20) k = 19, C(O, 19) =0.999999 98 6.21) k = 20, C(O, 20) =0.999999 98 8.0 Summary ofCodes Investigated 108 8.2) BandpassExperiment Results 110 A.O PLL GainCalculations 165 A.2) Calculated Values 167 D.l) Probabilities P(II, v):vlt,c> =(O,2,t);QPSK in City 185 0.2) Probabilities Ni" v):(dt,c> =(O,J.J);QPSK in City 186 OJ) Probabilities Ni" v):(d, k) = 0,3); QPSK in City 187 0.4) Probabilities P(II, v):(d, k) = 0, 7);QPSK in City 188 0.5) Probabilities Ni" v):(d, k) = (2, 7);QPSK in City 189 0.6) Probabilities P(II, v):vlt,C> =(0,2,1); QPSK in IIgw 190 0.7) Probabilities P(J.l, v):vlt,c> =(0,1,1); QPSK in Hgw 191 0.8) Probabilities P(I'. v): vi, k) = 0, 3); QPSK in Hgw 192 0.9) Probabilities P(/I, v): vi, k) = (I, 7); QPSK in IIgw 193 0.10) Probabilities P(/I, \.): vi, k) = (2, 7); QPSK in Hgw 194 0.10 Probabilities P(I'. \'):vlt,c> =(O,2,l);QPSK in City 195 0.12) Probabilities P(I', v):("t,c> =(O,l,1);QPSK in City 196 0.13) Probabilities P(/I, v):vi, k) = 0,3); QPSK in City 197 0.14) Probabilities P(/I, v): vi, k) = 0, 7);QPSK in City 198 0.15) Probabilities Ni" v):vi, k) = (2,7);QPSK in City 199 0.16) Probabilities P(/I, v):vlt,c> =(0,2,1); QPSK in IIgw 200 0.17) Probabilities Nil. \'):vlt,c> =(0,1,1); QPSK in IIgw 201 0.18) Probabilities P(II. \,): vi, k) = 0, 3); QPSK in IIgw 202 0.19) Probahilities P(/I, \.): vi, k) = 0, 7); QPSK in llgw 203 0.20) Probabilities Ni" v): vi, k) = (2, 7); QPSK in IIgw 204 viii LJ~'T OF SYMnO~ AO Free-space transmission loss C Shannon capacity C Charge constraint D Present data bit DR Density ratio d Minimum runlength ~O Durst density E Electric field E State transition matrix ....v f; NRZ channel bits f s State characterizing function f z Output characterizing function r Output matrix I Number of states K Number of input words k Maximum runlength I Distance between two antennas A Eigen value M Finite-state machine m Input word length #J Number of errors N Number of output words Nd(n) Number of distinctd sequencesof length n n Codeword length v Block of v bits ix 0 Previous codeword P(II, v) Block error probability R Code ratc S Finite-state set Sv State ofmachine at time tv C1 State in state set T State transition matrix tv time at v V Approximate eigenvector X Finite input alphabet Xv Input symbol ~ Element of finite input alphabet Yi Channel signals Z Finite output alphabet Zv Output symbol t Element of finite output alphabet 1CHAPTER 1 INTRODUCTION Alexander Graham Bell 0847-1922) invented and patented in 1876 the first telephone that was of any real practical usc. In 1874 he said: "If I could make a current of electricity vary in intensity precisely as the air varies in density during the production 01sound, J should be able to transmit speech telegraphically." With this remark as principle for a telephone. analog telecommunication as we know it today was on its way. Until Alexander Graham Bell, the world of communication was a digital world. The preeminent digital device was the telegraph, which communicated by turning an electrical current on and off. It was simple. robust and effective. By pressing down the telegraph key, the operator completed the circuit. Bolding it down for a short time created a "dot"; a longer contact constituted a "dash." 111e presence or absence of gross electrical energy defined a message by means of an accepted code (the Morse code was one of several). The chief constraint was the speed of transmission. A good operator could manage 25 or 30 words, occasionally 40 words perminute [11. Before long it occurred to a number of inventors. including 1110mas Alva Edison (1874·1931), that the keys could be rigged to transmit mechanically at much higher speeds CIIAP'rnR ONE INTRODUcnON 2 than human operators could attain. '11e Morse letters could be punched out on a paper tape ahead of time and the tape could then be drawn through a special automatic keying device to activate the telegraph transmitter at a faster rate. By the 1870's, automatic telegraphs were transmitting at rates in excess of 500 words per minute over test lines and rates of from 100 to 200 words per minute were routinely achieved on ordinary inter city telegraph circuits. This was the wircline corollary oftoday's goal of "spectrum efficiency." By utilizing the same wire circuits but transmitting at a much higher rate, the carrying capacity of the telegraph wasgreatly increased. Telegraphers encountered a special problem, however, when the first transatlantic cables were laid in the 1850's and 1860's. Here were true long distance circuits, reaching some 2500 kilometers from Ireland to Newfoundland. The laying of these huge cables out across the open Atlantic in waters 3 kilometers deep was a feat of engineering audacity comparable to digging the Panama Canal or landing on the Moon and it captured the public imagination and came to symbolize technological progress for the Victorian era. Yet the physical challenges of laying the cable were matched by the unforeseen electrical challenges involved in actually transmitting signals on these immensely long circuits. Of course regeneration was impossible. For reasons that were not fully understood at the time, the effective transmission rate on the transatlantic circuits was reduced to two or three letters per minute. Here. on the most expensive circuit of all, where wireline "transmission efficiency" was most needed. the transmission rates were so slow, three hours or so for the text contained on one page of the average book, that even after the cable was installed, it was still quicker to transport a typical journal across the ocean byship than to transmit itscontents byundersea telegraph. The first "multilevel coding" composure was used to improve the situation somewhat. The English scientist William Thomson (who became the first Baron Kelvin) realized that the ordinary Morse code was itself rather inefficient. TIle symbols only recognized two level of current ("on" and "off") and two intervals of time ("short" and "long") and did not even utilize these code parameters very efficiently. With such symbols it was not necessary to transmit up to five symbols ("dots" and "dashes") to signify a single letter of the alphabet. Thomson constructed an apparatus that was capable of transmitting symbols based on up to five distinct voltage levels. In Thomson's code, two of these five level symbols were sufficient for unique designation of 25 of the 26 letters in the alphabet. Thomson's multilevel code had increased the information density of each symbol. It was the symbol rate that was limited by the electrical and physical characteristics of the cable. If each CHAPTP.R ONE INTRODUcnON 3 symbol could be made to carry more information. the overall throughput of the cable could be increased substantially, to from 16 to 20 words per minute. In modem terminology, Bell's undulatory current is referred to as analog transmission. Instead of transmitting discrete pulses of energy. an analog system like Bell's telephone transmits a complex. unbroken electrical waveform. which corresponds closely to the waveforms produced by the original sounds of human speech. Analog transmission proved to be simple. reliable and economical for large scale applications. It was heralded as a breakthrough from the older telegraphic thinking. The idea of waveform reproduction guided early radio researchers as well. All the radio systems developed through the first half of the twentieth century utilized the same basic analog signal processing principles of wireline telephony. In general. from 1876 until about 1950. analog transmission reigned supreme among all communication media. with only vestigial survivals of the older telegraphic techniques. Over the past thirty-five years. digital systems have penetrated every segment of society. Digital switches are revolutionizing telephone central-office and network control functions. Digital transmission systems are now installed on more than half of all interchange telephone trunks, The use of digital microwave is increasing. In the local distribution segment hundreds of thousands of "digital" subscriber loops are being installed every year. Fiber optics. another technological buzzword for the 1990's. utilizes digital technology. Digital techniques are invading other industries, Digital audio systems are rapidly displacing the standard analog media (LP records and analog audio tape cassettes). Digital television is on the horizon. Digital photography. digital x rays. are now being developed. Obviously. the pervasiveness of the computer has transformed the workplace and brought digital electronics into millions of homes. Against this backdrop. cellular mobile radio in its current form will almost certainly be the last major analog communication system ever deployed. Also. analog cellular radio finds itself in the early 1990's in a situation similar to that of the LP record industry a few years back. faced with the onset of digital compact laser disk media. Compact disk (CD) market share has rocketed from almost nothing in 1980 to overtake analog Jll's by 1990. Communication engineers are beginning to talk about digital cellular in terms which suggest a similar upheaval of current industry patterns in mobile telephony. An interesting observation in the history of analog vs digital, is that digital was the first CIIAPrnR ONE INTRODUcnON 4 and last. Digital was replaced by analog and with the might of a battleship regained its position as the supreme. The processes of digital communication are awe-inspiring, in speed, in precision, in terms of sheer technical accomplishment, yet these processes are clearly much more complex than Bell's simple telephone! Aquestion therefore arises: Why bother'? Or, to put itanother way, why does digital, with all its expensive overhead, payoff? 111is question and other interesting aspects of digital communication, digital cellular radio and the radio channel itsclf will be discussed in chapter two. Alan Mathison Turing's (t 912-1954) claim to fame is as one of the fathers of the electronic computer. His 1936 paper, "On Computable Numbers, with an application to the Entscheidungsproblem" is the classic in its field. The EnJscheidJuJgsprob/em: "to find a method for deciding whether or not a given formula is a logical consequence of some other given formulae. " lie dreamed of making a "brain", his Universal Machine, essentially what we would now recognize as an automatic digital computer with internal storage. This "brain" of Turing could be realized with a finite-state machine with millions of states. (The formal definitions for a finite-state machine and a state can be found in chapter three). In chapter three a formal or "computer scientist" discussion concerning finite-state machines (FSM) is presented. Although some of the material presented in thischapter will not have any direct relation to work done in this thesis, it will serve as an introduction to the theory of finite-state machinesfor students to follow and finite-state-machine-enthusiasts alike. Modulation codes are also known as runlength limited codes, constrained codes, line codes or dk codes and are employed on self-synchronizing digital communication systems. These codes usually find application on digital magnetic and optical recorders [3]. As another (Jesser known) application for these codes, a selection of modulation codes were investigated for clock extraction when transmitting data over bandwidth-limited, voice band VHF FM mobile communication systems. Chapter four presents the necessary background on the relevant information theory and its implications on digital communication systems. Chapter five deals with applications of finite-state machines, maybe less impressive and with a million or so states less than Turing's "brain", in digital communication systems. CUAPTER ONE INTRODUcnON 5 Furthermore, finite-state machine representations of modulation codes are investigated and a procedure is presented to map a class of coding rules into fixed rnte systems. This procedure to set up state systems for codes with memory, described by fixed length rules, is based on an engineering approach to sequential design [4J. A method for converting between Mealy and Moore representations of finite-state machines is also presented in this chapter, together with a method to obtain a minimum Moore machine. A special class of modulation codes with only a maximum nmlength constraint, were considered for use on mobile communication channels. The results obtained is presented in chapter six. Experiments were conducted and custom designs were undertaken in this study. Chapter seven gives a system-based description of the various facets of the experimental set up which was developed. Codes with various runlength and charge constraints were generated and transmitted through highpass, lowpass and bandpass filters with various cut off frequencies and slopes to obtain quantitative results for these codes through bandlimited channels.. The parameters of the code selected also determine the shape of the power spectral density and the bandwidth requirements of the modulated FM signal on the channel. Chapter eight deals with these results. Chapter nine is the "proof of the pudding": the results obtained for modulation codes transmitted over mobile VHF radio channels. Since the topics investigated in this study arestill new, some meaningful suggestions for future research arc made in chapter ten together with some concluding remarks. Supplementary material including circuit diagrams, programs written in Turbo C and TMS Assembler are included in the appendices at the back of the thesis, and since we arc living in the "digital" age, an IBM compatible floppy disk, with some of the programs developed. is presented in the cover of this thesis. 6CHAPTER2 MOBILE COMMUNICATIONS The telephone was introduced to the public in 1876 at the Centcnnial Exposition of the United States in Philadelphia. Alexander Graham I3c1l was able to transmit speech electrically, in one direction only, over a copper wire circuit of several hundred meters in length. Although not everyone present that day could immediately perceive its commercial value, the "speaking telegraph" was quickly perfcctcd for adequate two-way communication and was offered for business and residential service the following ycar. Within a short time there were thousands, then tens of thousands and soon hundreds of thousands of paying customers. TIle story of the evolution of the wire network is in large part the story of a long struggle against thc burden and expense of the physical wire plant. Scientists were led deeper and deeper into the study of electrical transmission, to understand in detail the characteristics of wire media and to search (or ways to utilize this costly transmission facility more and more efficiently. Toward the end of the nineteenth century, while this struggle was only beginning, a young Gcnnan scientist named lIeinrich Rudolf Hcrtz discovered a strange and wonderful phenomenon: from an electric spark of sufficient intensity there seemed to emanate CIIAJrrnR TWO MOOIlE COMMUNICA110NS 7 invisible waves of force which could be captured at a distant location by a suitable constructed receiving device. It seemed to be a realization of the ancient concept of "action at 11 distance. II Classical physicists found this philosophically disturbing and postulated the existence of some impalpable intervening medium, the Ether, which actually transmitted these strange waves. Hertz's own experiments extended only over a few meters. A few years later, Guglielmo Marconi transmitted these waves over several kilometers, and began to call it Radio. The early telephone engineers, caught up in the heroic and unrelenting struggle with copper wire physics and economics, looked upon the new phenomenon with awe. "/1 has been shown," wrote one John J. Carty in 1891, "that longer waves may be generated which arc capable of electrical action ami which can be propagated Ihrough the densest jog and even through a stone wall with just as much case as through the clearest atmosphere [1]. Communication devices which exploited these "Jlertzian" waves experienced a much slower technological gestation but a more rapid market development than the telephone. Radio broadcasting was introduced commercially in the United States in 1921. Within ten years, more than 50% of all American households boasted a radio set. Within twenty years, it was over 900AJ. The growth of television, another technology based on radio transmission, was even more rapid. Once it became readily available to the American public in 1946 it took only nine years to reach the50% level and only fourteen years to reach 90%. Such inventions, inherently far more complex and costly than the telephone instrument, were able to spread so much more rapidly because they did not require a massive investment in wireline infrastructure. John J. Carty, however, writing in 1891, had not foreseen either radio or TV broadcasting as we know it today. For him, the promise of Hertz's discoveries lay in another direction: itA system oftelephony without wires seems one ofthe interesting possibilities..." The possibility for utilizing radio devices for communicating with moving vehicles was quickly appreciated. The earliest commercial application of radio had been for communication with ships at sen. As early as 1921, the Detroit Police Department was conducting experiments with "mobile" radio. Throughout the 1930's, experience with mobile communication accumulated. It was World War II, however, and the sudden and pressing need for two-way mobile communication on a large scale, that gave the real impetus to mobile radio technology. It is impossible to imagine any of the characteristic tactical operations of that war functioning effcctively without radio. CIIAPrnRTwO MOWLe COMMUNlCAnoNs 8 At the end of the war, the first licenses were granted for the provision of true mobile telephone services; in other words, to allow a user calling by radio from a moving vehicle to be interconnected into the public telephone network. TIle car phone was conceived. The war had brought to prominence a new type of radio technology, frequency modulated radio or FM, which permitted superior mobile voice communication. Interfaces to telephone switches had been established. Americans were buying automobiles in record numbers. Prosperity had returned. Along with television, mobile radio seemed poised for a postwar boom. But, something went wrong. From the promise of those early commercial systems in the late 1940's, the actual deployment of mobile telephone systems proved painfully slow. More than forty years Inter, even after the development of "modem" cellular radio systems, the actual development of the market for mobile telephony was abysmal. In the densest traffic centers in the US, the penetration in the mid-1980's is considerably less than 1%!1 Moreover, based on current technology the available spectrum is loaded to near capacity. Even to double this penetration will apparently involve very substantial technical and economic challenges. Mobile telephony [t] has undoubtedly set the record for the slowest penetration by any technology to the mass marketplace. • Cost is not the whole explanation. The cost of ordinary wireline telephony in the early years ofthe twentieth century was, in relative terms, much higher than the cost of mobile service today; • Spectrum shortage isno explanation at all, but a symptom; • Insufficient demand is most decidedlynot the explanation. Ifanything, the indications have all been strongly in the other direction, tending toshow a very large demand for affordable mobile communication services. The realization is growing among industry observers that interconnected mobile radio, in its current configuration, cannot become the mainstream mobile service that its designers once hoped for. However, we have advanced to the point where no policeman, fireman, taxi-driver or sccurity guard would be able to fulfill hisdesignated role efficiently without suitable radio equipment. Today "cellular radio" stands in the spotlight, with its hopes illuminated and its deficiencies exposed, still pretending to a degree of technological permanence that once CIIAI'l'F.R TwO MODIl.E COMMUNlCA110NS 9 seemed more valid than it docs today, The "mobile revolution" is, however, much larger than the current generation of cellular radio and its immediate problems, although severe in some respects, should be recognized as developmental rather than fundamental. Consider a parallel case. Thirty years ago computers were bulky monstrosities: expensive, power-hungry, slow, finicky. Viewed from today's perspective, the basic technology was inadequate. Computers were too slow for many tasks and too fragile for most environments. It would have been inconceivable to put such computers in a car, aboard an orbiting satellite, or on someone's desk. Yet, the breakthroughs came and today observers would agree that computer applications are no longer restricted by technology-hardware capability and availability as much as by the economics, architecture and ingenuity of the software implementations. At least as far as conventional data-processing (nonreal-tlme) applications are concerned, the hardware is fast enough, cheap enough and durable enough to go anywhere and to do almost anything that we arc willing to pay programmers to develop and debug. Mobile radio today is in the same situation as the computer of the 1950's. Our goals for mobile communication, in terms of performance, cost, capacity, spectrum efficiency and portability, seem far beyond the reach of today's hardware. This, it is believed, will prove to be a very temporary state of affairs [5]. Imminent technical breakthroughs, some already unfolding, will completely change our thinking about mobile radio and trnnsfonn our sense of the possible. This study is hoped to contribute in a decisive way to this course. 2.1) ANALOG VSDIGITAL Digital systems are increasingly favored because they enjoy certain general advantages over analog techniques, the most important of which have to do with the emerging plans for a digital network that will possess capabilities far beyond those of today's telephone and radio systems. A point wise comparison, advantages and disadvantages, of a digital system to an analog system will follow. AnVANTAGFS OF DlOrrAL RADIO SYSTEMS: • Digital equipment is transparent to the type of traffic which it carries, i.e. the traffic may originate from telephone, computer, facsimile, telex, ete., it may be integrated into one bit stream for transmission over the same radio bearer (or other transmission systems), and it may be switched together. As the data stream is always present, whether infonnation is contained in it or not, the load on the CUAPTF.R TWo M08U.£ COMMUNlCAnoNS 10 radio system is therefore constant. Thls is not true for analog radio systems, where the loading depends upon the amount and the type of traffic being carried at anyone time; • TIle accumulated noise of analog systems which posed serious constraints on equipment design is avoided in a digital system by regenerating the data stream; • Digital radio systems are less prone to interference and can operate satisfactorily with a carrier-to-interference ratio of 15 to 30 dn. This permits the same frequency to be re-used on the orthogonal polarization, thus conserving bandwidth and effectively doubling the spectrum efficiency or doubling the capacity which the RF channel can carry. This feature is one of the best advantages of digital radio over analog, for in the analog case the requirement for carrier-to-interference ratio is much higher: approximately 45 to 60 dB [6]; • TIle output power of a digital radio transmitter can be less than that of the analog radio for a given transmission quality. This lowersthecost of the equipment, increase reliability and saves on power and air-conditioning costs. Smaller output power also has the advantage that smaller interference levels are produced, making it possible for higher co-channel frequency re-use within a given geographical area and coexistence of digital systems with existing analog systems; • Depending on the modulation system in use, digital systems are able to produce a voice channel of acceptable quality with a carrier-to-noise ratio of as little as 15 dB, whereas for an analog system this may be designated as 30 dB or more, again depending upon the system. Figure 2.1 shows the comparison of the signal-to-noise ratio (SNR) versus input receive level ireceivcr quieting curve) of analog and a digital radio system. Under flat jading conditions, the analog system shows a gradual decline of SNR (dB for dB) for a decrease in received signal level. The digital system is unaffected until a threshold is reached. This characteristic is due to the regeneration process, in which the digital signal can be regenerated to its pristine fonn as long as the system is operated above a predetermined threshold. This threshold behavior thus permits a constant transmission quality to be achieved, which is independent of thereceived field variations, path length and the number of repeaters. These points together with the fact that a digital radio network can be established by using existing towers and antennas mokc digital systems attractive. With the reduction in large scale integrated (LSI) circuit costs, and thc large scale production of digital integrated circuits, equipment costs arc reduced, making digital systems cost competitive with thnt of analog systems. Indeed the total CO~1 for a digital system is at present gcnerally lower than CIIAI1fF.R TWO for an analog system. 90 10 ·1 80 10 • 70 10 ' m GO a: 10 •u w~ OJ iii" 50 10 ' 40 10· • 30 10 ) M08JLH COMMUNICAnONS 11 I 2L_~~.__~.'0' j - 30 - 40 -!i0 - 60 - 70 -. UO -!JO - 30 - 40 - 50 - 60 - 70 - 60 - 90 RF input. dlllll RF Input.dlJm (nl fbI FIGURE 2.1 RECEIVER QUIETING CURVE: (a) ANALOG SYSTEM; (b) DIGITAL SYSTEM DISADVANTAGF..5 OF DIGITAL RADIO SYSTEMS: • Digital radio and digital systems have to be integrated in the early stages with ~n existing analog network. The associated interfacing problems, costs and interference problems make the situation difficult: • Present digital radio systems are not as RF bandwidth efficient as analog systems of 600 voice channels or more. These problems will be resolved or not be that important, as the operating carrier frequencies are pushed higher; • To carry the same traffic as an optical fiber, a digital radio requires to operate with a larger RF bandwidth. This large bandwidth makes the radio link susceptible to selective fading, which results in the consequent loss of all traffic. A wideband analog system by the same token would suffer only an increase in noise: • The introduction of new and many varied techniques over those required in the design, testing and maintenance of analog systems poses a problem in the retaining of personnel and in the training of new engineering staff. There is in reality a threefold problem. The first aspect is that there is already a heavy capital investment in analog systems, which have proven to be reliable, Personnel arc thus still heavily committed in this area and will be for some years to come. Secondly, digital radio or systems require that new skills be learnt and acquired, which arc not easily accepted in general. Finally, transmission technology has strong competitors in the information technology and computer tcchnology areas, CJlAJYn!R TWo MODIl.H COMMUNlCA110NS 12 which may bemore immediotely appealing to prospective new engineers. The decisive advantages of digital radio over analog are: economy, better interference immunity and betterquality circuitsover long distances. It should be clear by now that the choice of analog or digital technology is a fundamental, irreversible decision that will define the next generation of cellular systems. Is there any rl'aSOI1 to consider analog technology for the next generation of mobile radio? Admittedly, I believe the answer is obvious. The next generation will be digital, for all the reasons presented. Since it is evident that digital is the future, this study will only consider digital radio systems. 2.2) DIGITAL SIGNALING OVER FADING MULTIPA1'1 CHANNELS Since this study is by no means concerned with the modeling of the mobile communication channel, the contemplation of the mobile communication channel to follow can be considered strictly introductory, with only physical observations being discussed. However, for a more expanded and mathematical approach to the digital mobile radio channel [7], [8] and [9] can be approached. RF channels having a randomly time-variant impulse response is named lading mul/ipa/h channels [10]. This characterization serves as a model for signal transmission over many radio channels, such as shortwave ionospheric radio communication in the 3 to 30 MHz frequency band (IIF), tropospheric scatter (beyond-the-horizon) radio communications in the 300 to 3000 Mllz frequency band (UHF) and 3 to 30 QBz frequency band (SHF) and ionospheric forward scatter in the 30 to 300 Mllz frequency band (VHF). The time-variant impulse response of these channels arc a consequence of the constantly changing physical characteristics of the media. Radio waves may be propagated around the globe differently. The two main routes which they may travel from the transmitting antenna to the receiving antenna are either by the ionosphere (d:y WQl'C) or by hugging the ground wround WtH'c). The ground wave may itself he divided into two types; the surface wave and the space wave. For the space wave, three paths may be used to traverse the distance between the transmitted antenna and the receiving antenna. These arc the direct wave, the ground reflected wave and the troposphcrically reflected wave. In the space wave mode of propagation, which is used by the systcrn considered in this CHAPTER TwO MoonECOMMUNICAnONS 13 study, the wave travels in the tropos..phere, which extends to 16 kilometers above the Earth's surface. The wave energy travels from the transmitting to receiving antenna either in a straight line (tine of sight) or is reflected at the ground or from the troposphere. The space wave is the one which isof importance in VHF, UHF and SHFcommunications. Several things happen to n radio wave transmitted to or from a moving vehicle [1], [5] and [11 ]: 2.2.1) FREE SPACE Loss First, the free-space basic transmission loss (Ao) is the transmission that would occur if the antennas were replaced by isotropic antennas located in a perfect dielectric, homogeneous, isotropic and unlimited environment, the distance between the antennas being retained. If the distance I between the antennas is much greater than the wavelength A, the free-space transmission loss can be written as: Ao= 20 log«4J1'/1).). • e E ~ -20 i ~ - -30 C8 I I ~~jL ._1.__ r:.~:r:~_=_. l_ o O~ I I~ t. In \tcond, t----i5 £6 •• on wQvt1tnql/\ .. FIGURE 2.4 FADING SIGNAL RECEIVED WHILE 11IE MOBILE UNIT IS MOVING mobile-radio proposal. It is a characteristic of the environment and cannot be altered by the mobile systems engineer. Cellular radio today is the final flower of frequency modulated (FM) analog radio. Multipath fading is the great destroyer of mobile-radio signals; it overwhelms AM and single sideband systems. The great advantage of FM when it was applied to mobile radio in the 1930's was due to the fact that the FM receiver suppressed (ignored) amplitude modulation. and thus the degradation due to amplitude fading is greatlyreduced. 2.2.3.3) DOPPLER SHIFT Whenever relative motion exists there is a shift in the received signal. this being a manifestation in the frequency domain of the envelope fading in the time domain. This is the varialion in the frequency of the received signal known as the Doppler !ihift [to] (after Chrisrhn Johann Doppler, a nineteenth-century Austrian physicist who first called attention to frequency shifts caused by relative motion.) Much as the sound of a hom on a moving car appears to the stationary observer to be slighlly higher in pitch when the car is approaching rapidly and slightly lower when the car is receding. 50 radio transmissions arc frequency shifted due to the relative motion of the vehicle. This frequency shift varies considerably as the mobile unit changes direction, speed and it introduces considcrubly random frequency ITlodulation in the mobile signal. Moreover, the Doppler shift affects all CIIAI'I1Ut TwO M081l.E COMMUNlCAll0NS 18 multiple propagation paths, some of which may exhibit 8 positive shift and some a negative ~hift, at the same instant. 2.4) Tne CF..LLULAR CONCEPT It is important to recognize that today's analog cellular radio is not so much a new technology as a new idea for organizing existing technology on a larger scale. The critical innovation was the "cellular idea". Cellular represented a very different approach to structuring a radio-telephone network. It was an idea that held out the fantastic promise of virtually unlimited system capacity, breaking through the barriers that had restricted the growth of mobile telephony and it did so without any fundamental technological leap forward; simply through working smarter with the same resources. Cellular architecture was a system-level concept, essentially independent of radio technology. It appealed to mobile system engineers, because it kept them on relative familiar hardware ground. It appealed to businessmen and entrepreneurs, because it seemed to open the path to a really large market: by the application of the cellular idea, mobile communication could become another first-class growth industry, like television or radio, or telephone itself. The cellular idea also appealed to the authorities, because it seemed to break out of the spectrum shortage that had created terrific political difficulties. 111e cellular idea is elusively simple; one writer concluded that it seemed "to have materialized from III1I1'/lCrc" [Il. It began to appear in Bell System proposals during the late 1940's. It had occurred to people that the problem of spectrum congestion might be alleviated by restructuring the coverage areas of mobile radio systems. The traditional approach to mobile radio viewed the problem in terms similar to radio or television broadcasting: it involved selling up a high-power transmitter on top of the highest point in the area and blasting out the signal to the horizon (as much as 70 to 80 kilometers away.) It meant that the few available channels were locked up over a large area by a small numberof calls. 111e cellular idea approached the coverage problem quite differently. It abandoned the broadcasting model. Cellular called instead for low-power transmitters, lots of them, each specifically designed to serve only a small area, perhaps only a few kilometers across. By reducing the coverage areas and creating a large number of small cells, it became possible to re-use the some frequencies in different small coverage areas, called cetls. For a graphic description of a "traditional" vs cellular transmitting system refer to figure 2.5. To CIlAPIl~ TwO MOOIl.E COMMUNlCAnONS 19 understand how this changes total picture. imagine that all the available frequencies could be reused in every cell. If this can be done, then instead of 12simultaneous telephone circuits for the entire city there would be 12 circuits for every cell. If there are 100 cells (each about 16 kilometers across), there would be 1200 circuits for the city, instead ofonly 12. nut. it is not quite as neat. Early calculations indicated that, because of interference between mobiles operating on the same channel in adjacent cells, the same frequency could not be used in every cell. It would be necessary to skip severnI cells before reusing the AOURE2.5 CELLULAR ARCJrrmcnJRE :mn!e frequencies, sec figure 2.6. nut the basic idea of reuse appears to be valid. Moreover -and here lay the real power of the cellular idea- it appears that the cffccts of interference arc not related to absolute distance between cells, but to the ratio ofthe CIfAMF.R TWo MODILE COMMUNlCA110NS 20 FIGURE 2.6 FREQUENCY REUSE distance between cell,' to the radius 01 the cells. The cell radius is determined by the transmitter power; in other words, it is under the system engineer's control. If. for example. a grid of 16 kilometer radius cells allowed reuse of the frequencies in cell A at a distance of48 kilometers, thcn a grid of 8 kilometer radius cells would allow reuse at 24 kilometers and 2 kilometer radius cells would allow reuse at 6 kilometers. Because of the fabulous cellular geometry (based on the m.2 nile for cell coverage area), however, each reduction in cell radius by 50% led to a quadrupling of the number ofcircuits per megahertz per square kilometer. A system based on 1 kilometer radius ceJls would generateone hundred times as many circuits as a system based on 10kilometer radius cells. Of course. it would have been enonnously expensive to build thousand-cell systems right from the beginning. It appears, however, that large-radius cells could evolve gracefully into small-radius cells over a period of time through a technique called cell-splitting. When the traffic reaches the point ina particular cell stich that the existing allocation of channels in that cell could no longer support a good grade of service, that cell would be subdivided into a number of new cells, with even lower transmitter powers, fitting within the area of the former cell. 111C reuse pattern of capacity multiplied for that area by a factor equal to the number of new cells, When. in time, the smaller cells are saturated, still smaller cells could be created. Cell-splitting offers many advantages. It allows the financial investment to be spread out CIIAIFJ'ER TwO MomLRCOMMUNlCAnONS 21 as the system grow. New cells would only be added as the number of revenue-generating customers increases. Moreover. cell-splitting can be applied in a geographically selective manner: the expense of smaller cells would only be necessary in the high density traffic centers. In the minds of cellular architects. it is the ideal surgical technique for boosting capacity precisely where and when it is needed, Since the mobile user is liable to wander out of one cell and into another as the call progresses. the system must reroute the call to the new base station and switch the call to a new radio channel without interruption. This procedure, known as "and-off, is one of the distinguishing features of cellular systems. 2.5) PRESENT CODING TEellNIQUES In real-thne speech requirements. the much-used protocol for data packets known as ARQ [5]. or automatic retransmission request. cannot be applied. An ARQ system needs only to utilize a sufficient amount ofcoding to enable the receiver to detect errors in a packet and initiate a retransmission request if errors are found. Real-time speech. however. does not allow for this procedure. Two types of coding arc widely used for structuring the code words. The most commonly used is the linear error correcting block code and in particular the Bosc-Chaudhuri-Hocqucnghem (BClI) variant. An alternative technique is offered by convolutional coding. of which the best known type is the Reed-Solomon code (the Reed-Solomon code can also be implemented as a block code). Insofar as generalization are possible. Reed-Solomon codes perform well in narrowband channels where burst errors predominate and nCIl codes work well where uniformly distributed statistically-independent errors are encountered [I]. In some commercial applications the baseband data streams in both directions arc encoded such that each non-rerum-to-zero (NRZ) binary I becomes a O-to-I transition and each NRZ zero becomes a one-to-zero trnnsition. This example of a modulation code has been considered on multipath (ading channels and is known as the vi. k, C) =(0. I, I) Manchester code; a strategy which assists the receiving end in recovering the basic data clock. Seechapter 8. p257 in Parsons [5] (ora full description. '111C choice of modulation/coding techniques (or a mobile radio-telephone system is driven by several technical considerations. chief among which are: CJlAI"'~ TWO MornLB COMMUNJCAnONS 22 • The scarcity of bandwidth, leading toa need for spectral efficiency; • 111e problem of adjacent-channel interference, lending to the requirement for narrow-power spectra; • 111e problem of intersymbol interference, which imposes hard limits on the transmission rate in a mobile environment; • The problem of clock extraction, synchronization is lost if there are too many successive symbols without transitions. II should be kept in mind that all four parameters are interrelated; in the following discussion, for the purpose of clarification of the underlying issues, someconceptual liberties are taken in treating each of the four constraints separately. 2.5.1) SPECTRAL EFFICIENCY Spectral efficiency refers to the number of bits that are transmltted in a given period of time, usually one second, over a radio channel with a defined bandwidth. Since the channel bandwidth is measured in kilohertz (kl'lz) or megahertz (Mllz), it is possible to define spectral efficiency as the number of bits per second per hertz (Hz), sometimes loosely referred to as bits per hertz (b/lIz). ntis is also commonly called information density; how many bitscan be pumped through a given channel in one second. l11C concept of multi-ary modulation is very powerful. (It is assumed that the reader is familiar with the principles of multi-ary coding.) It is certainly possible to conceive of an a-ary system, which would transmit three bits per symbol, achieving 3 b/hz. A 16-ary modulator, encodingfour bits per symbol, would achieve 4 b/Hz. Multi-ary coding is a logical concept that may be applied to any of the familiar modulationschemes. Whilc spectral efficiency increases arithmetically, the number of levels nnd the precision required at the demodulator increase exponentially. If n is the number of bits per symbol, then the number of levels equals z!I. which also correlates with the degree of precision required in the demodulator, The diffcrence in signal level between 4-ary PSK nnd 16-ary PSK is about 13 dB; the signal-to-nolse ratio mus.. be about 200 times bener for 16-nry PSK to equal the performance or 4-nry PSK. ntis trnnslatcs into higher power requirements, reduced range and at some point into absolute limits on the nhilily or higher-nry modulotion schemes to function. 111C mobile environment is particularly severe nnd mnny observers today (11) doubt whether modulators much above 16 levels or so will ever he made to work well for mobile radio. Most field work has favored either 2·ary, CUAIFJll.R TwO MOWLE COMMUNlCA110NS 23 -t-ary or B-ary, for robustness. A quantative confinnation of this statement is presented in chapter 9. 2.5.2) NARROW POWER SPECTRUM When a modulated radio carrier wave is transmitted, the energy it contains is distributed in a characteristic fashion about the center frequency (See figure 2.7). The distribution is known as the power sipcctrum. TIle father away from the center frequency in either direction, the less strong the signal. Typically, the energy is concentrated in a main band. Some forms of modulation and coding, however, produce significant sidebands. In fact, the particular "signature" of the power spectrum, especially the size of the sidclobes, is one of the most important factors for distinguishing among different modulation and coding proposals. FIGURE 2.7 TYPICAL PoWER SPECTRUM TIle power spectrum is a determinant of adjacent-channel interference. A modulator with a very broad power spectrum, like conventional FM, will overlap significantly with adjacent transmissions. A broad power spectrum is therefore not desirable. It can be filtered to fit the mask, but such filtering can add considerableexpense to the mobile unit. Another method to ensure a power spectra ofdesirable shape, is to look at the transfer function of the given channel and shape the data spectrum in such a way as to fit the channel response in the best possible way. The measured transfer function of a mobile communication channel is presented in figure 2.8. It is clear the channel is more lenient on the low frequency side. A code an(Vor modulation scheme which could shape the power spectra in such a fashion as to fit the transfer function of the channel would he a better choice over one that have for instance a peak at the high frequency side of the spectra. CIIAI'n~ TwO 2.5.3) INTERSYMBOL INTERFERENCE MomL£ COMMUNlCAnONS 24 AMPLITUDE IN dB As discussed earlier, one of the effects produced by the mobile environment is the tle/tlY spread. Depending upon the nature of the environmental reflectors that create multipath transmission. the speed of the mobile unit, and other factors, a sharp transmitted pulse of. say. a fifth of a microsecond duration will be detected by the receiver as a smeared and flattened bulge of considerably greater duration. sometimes up to several microseconds. If 10 ---'--- A M p L I -20 . T U 0 -30E -40 -50 __l__I .L__L_L__I--J_._--L-__'-_-' o 500 1000 1500 2000 2500 3000 3500 4000 4500 5000 FREQUENCY (Hz) FIGURE 2.8 MEASURED TRANSFER F'UNcnON OF MOBILE COMMUNICATION CHANNEL it is severe enough -that is. if the transmission-induced delay spread is large relative to the average symbol time, intersymbol interference will result as the individual symbols begin to overlap one another. Delay spread is produced by the environment; for a given frequency and a given environment the delay spread should be the same (or all radio signals propagating in that environment. To some extent this can be controlled by adaptive equalization. Another method to reduce intersymhol interference is to make usc of nanlength-Iimited coding on thc digital sequence. In doing this thcre will always be a minimum of d (Sec chapter 4) symbols without transitions; restraining the effects of intersyrnbol interference to a certain degree. depending on d. Naturally, thc most effective way to reduce intcrsymbol intcrference will be to utilize both these techniques. CIIAP11~ TWO 2.5.4) CLOCK EXTRACTION Monu.B COMMUNlCA110NS 25 It must be noted that coding in this study is by no means the same as used in present mobile communication papers and handbooks. Under coding is understood shaping of the power spectra and inserting some kind of unique characteristic in the digital channel bits, such as rigidity against intersymbol interference and clock recovery properties. Mobile communication literature view coding as error correction coding, where channel injected errors arc corrected, or digitizing the analog speech signal using various techniques to reduce the number of bits that need to be transmitted, while maintaining "telephone voice quality." Some of the techniques used are: • Continuously variable slope delta modulation (CVSD); • Adaptivesubband coding (SBC); Residual-excited linear predictive coding (RELP); Vector quantization. For a detailed discussion on these techniques [1] and [11] can be consulted. When digital data is transmitted over a channel the receiver must be able to recover the clock from the received data. If the channel bitsdo not have enough transitions, the receiver can, in worst case conditions, loose synchronization and extra errors can occur because of this. By the effective use of coding the data stream can be altered in such a way as to ensure regular transitions. A further advantage of regular transitions can be appreciated when the signal enters a deep fade and clock extraction is impossible. When the signal recovers from the fade, clock extraction can be regained from the next 10 to20 bits in a coded scheme, while, in an uncoded scheme, clock extraction may only be regained from the next 100 to 200 bits. 111is so called "modulation coding" or "line coding" will be the focus of this investigation; trying to reduce the aforementioned intersymbol interference and ensuring regular transitions in thc digital data stream. 2.6) CELLULAR RADIO IN TIlE Rsrunuc OF South AFRICA The first generation of mobile telephone systems, such as the system installed in November CIIAI"'~ Two Morum COMMUNICATIONS 26 1981 by the SAPT in the Pretoria-Witwatersrand area, were not suitable for the expected growth in mobile communications: it did not utilize the cellular concept. In May 1986 a cellular mobile telephone network was introduced by the SAPT, using the C450 public land-mobile system from Siemens [t 2]. The C450 system operates in the 450 MJ Iz band. Jt is designed for the reuse of frequencies in every seventh cell, thereby fonning a seven-cell "cluster". A unique feature of the C450 system is that hand-offs are not just determined by field strength distribution and signal quality as in most other systems, but by actual determination of the stations in a cluster. This is accomplished by synchronizing all the base stations and therefore evaluating the relative delay times of the signals from the control channels of the surrounding bose stations in the mobile set itself. '111e mobile set also retransmits the distance data with a fixed delay. By using various algorithms the position of the mobile user can be detennined to a resolution of 400 meters. 111is allows accurate detennination and flexibility of cell boundaries. A unique feature of the mobile sets is the use of a personal identification card for each subscriber, similar in size to a credit card. There is no identity allocated to a mobile set (MS). Each MS has a card reader that will read the magnetic code on the subscriber's personal identification can! and the MS will then assume the identity of a mobile set with the specified dircctory number. This allows the driver of a rented car to make/receive calls in his rented car using his own directory number. There arc seven base stations, comprising one seven-cell cluster. Base stations are located at Strydom Tower (Johannesburg), Langerand (Vereenigingl, Springs, Benoni. Doornkloof, Lewisham (Krugersdorp) and John Vorster Tower (Pretoria). The ultimate theoretical capacity with the existing equipment is approximately 6500 subscribers. If there is further growth the existing cell boundaries would have to redesigned for the addition of new cells. Ilowever due to frequency limitations the theoretical capacity is presently only about 2500 subscribers, At present there are approximately 600 mobile telephone users connected to the C450 system nnd these are still growing steadily. Although the present system is adequate, the restricted radio spectrum in the 450 Mllz band and lower where this system and other existing mobile radio systems work has to be overcome. Future systems will usc digital technology and generally usc the 900 MHz band where adequate frequencies are still available. CJlAI"IT~ TWO MOWLE COMMUNlCA110NS 27 Since the capital investment involved is considerable (in excess of RIO million for the C450 system installed in the PWV area in 1986), the South African mobile telephone system will only be expanded to the other major urban centers such as Cape Town and Durban, once the PWV system has proven tobe commercially viable. 28 CHAPTER 3 THEORYOFFINITE-STATE MACHINES TIle study of finite-state machines (FSM) in this chapter is concerned with describing their structure, analyzing their capabilities and limitations and investigating various fonns in which they can be realized physically. The significance of such machines is that these models are not confined to any particular scientific area, but arc directly applicable to problems in practically every field of investigation - from psychology to business administration, from communication to computer science. Since the human brain operates in a sequential manner, even the thinking process and the analysis of the English syntax can be employed with a FSM. FSM's arc also used extensively in communication engineering, hence a solid background on this topic is essential. The discussion to follow will give a general background on FSM behavior, following [13], [14], and implementations on communication systems will be considered in chapters to follow. 3.1) TI IE FINn'E-STA'I1~Monm.. M01l1 problems encountered in engineering investigations can be classified as analysis problems or synthesis problems. Analysis problems usually involve prediction of the CIIAP'Jl1.R TURJm THEORY OF FINITE-SfA11! MACJIINI!S 29 behavior of a system. and synthesis problems where one wishes to construct D system with a specified behavior. In this chapter the analysis part of finite-state machines will be considered. where as in chapters to follow. some synthesis problems will be encountered. In both analysis lind synthesis problems three groups of variables are encountered which characterize a system. namely excitation variables, which represents the stimuli generated by systems othcr than the one under investigntion, and which Influence the behavior of the system under investigation; response variabtcs, representing those aspects of system behavior which arc of intcrest to the invcstlgator: tntermcdkue variables, whose Importance does not lie in their individual behaviors, but rather in their combined effcct on the relationship between the input and output variables. A finite-state machine is an abstract model consisting of a finite set of input symbols representing the excitation variables, a finite set of output symbol: representing the response variables. a finite set of states representing the intermediate variahies, a next-state function and an output function, '111e intermediate variables, which arc of no direct interest. are assumed to he embedded inside the system. 111e sets of input and output symbols arc usually referred to as the input and output alphabets. Input, output and state variables nrc defined only for integral values of time. Every system representable by the basic finite-state model is assumed to be controlled by an independent synchronizing source, in the following fashion: TIle system variables are not measured continuously. but only at the discrete instants of time nt which a certain specified event, called a synchronizing signal. is exhibited by the source. These instants of time are called sampling limes, the 11h sampling time being denoted by t (v = l, 2....). An additional assumption is v that the behavior of the system at nny sampling time I is independent of the interval between v I and the previous sampling time I J' Thus, the true independent quantity, against which v v· every system variable is measured, is not time, but the ordinal number associated with the sampling times. As will be seen. synchronization is most important in communication systems, It should be emphasized that the foregoing assumptions do not imply that the time intervals between two successive synchroniaing signals arc uniform, neither docs it imply that a system variable, within such an interval. exhibits some specific mode of behavior. The only implication is that, whntever the interval is and whatever the 5)'l\1Cm variations within the interval are, the values of the variables at the rth sampling time depend on the number v and noton the value of I. Systems which conform with the time-discreteness assumption lIrc said v to be synchronous. Systems in which this assumption is not valid lire CIIArrF.R TlIRF.E 'nIEORY OF FlNITE-srATE MACJIINP..S 30 called asynchronous systems. Such systems will not be discussed. 3.1.1) TilE BASIC MODEL An exact definition for the class of systems which we shall call finite-state machines can now he provided. DEFINrnON 3.1 A finite-state machine M is a synchronous system with a finite input alphabet X = (~.' ';2' ... ,.;), a finite output alphabet Z =It., ~2' ... '~q}' a finite state set S =(ai' (f2' ••• , a }, and a pair of characterizing functions! and! given by n t s z =/l:c,s) v : v v s -/(t s) v+l - s v' v (3.1) (3.2) where x ,z and s arc, respectively the input symbol, output symbol and state of M at time t v v v v (v = 1,2, ...). Throughout, the assumption will be that M, as postulated in definition 3.1, is deterministic, i.e., its characterizing functions are not subject to any uncertainty and that Mis nonrestricted, i.e., any input symbol can be applied to M at any time t . v A special case of finite-state machine arises when (3.3) Such a machine is called a trivial machine. The intermediate variables in a trivial machine have no effect on its input-output relationship and hence the concept of state in this case is redundant. A nontrivial machine is one in which jCx .s) "I-ICx ) t v v : v (3.4) When a machine is considered that has just one input symbol, there is never really any choice as to what symbol to apply to such a machine at a given time instant. The machine operates without any influence from the outside world. A machine of this type is called an autonomous machine. Since there is only one input symbol, we do not onJinnrily bother to give it a name. (Some people like to think of an autonomous machine as having no inputs CIIAIJW.R n IRilE n IEORY OP FINITE-STATE MACIIINES 31 at all. since its transitions are not under external control. TIle viewpoint taken is largely academlc.) Machines whose characterizing functions arc the same except for possible differences in state labeling are said to be isomorphic to each other. Given a finite-state machine M representing a certain system. any machine which is isomorphic to M may serve as a representation of the same system. The representation of a system by a flnite-state machine is. by no means unique. A good example of two isomorphic machines is the Mealy and Moore representation of a given machine [13]. A machine whose characterizing function,!.. is solely a function of the t state that is entered. iscalled a Moore-type machine. In a Mealy machine however.j' isalso a t function of the input alphabet. Conversion from the one to the other will be discussed in chapter 5. together with some more synthesis problems concerning finite-state machines. A program listing in Turbo C can be found in Appendix E to convert between the two types of machines. It is important to remember that the finite-state model is an abstract model and. as such, says nothing about a physical realization of the process it describes. The states and symbols need not be thought of as having physical representations in terms of voltages or currents. level or pulses etc. All the physical phenomena of a sequential or iterative realization have been replaced by the next-state and output functions. The value of such an abstraction is that it enables us to strip away the unimportant physical details andstudy the common properties of a variety of different processes. 3.2) PREDlcnNG MACHINE BEHAVIOR A succession of input symbols ie. ~'/' followed by ~.,..... followed by ~'I' is called an input, ~ , sequence and written as ;./;.,•...• ~'r A succession of output symbols ie. t./. followed by t.", I ~ , J J.. followed t'l' is called an output sequence and is written as ~,/t" ....• t'r The number ofJ J J- J symbols in a sequence is referred to as the length of the sequence. As is evident from the time-discreteness assumption. excitations applied to finite-state machines are always in the fonn of input sequences and responses are always in the form of output sequences; an input sequence of length I always results in an output sequence of length I. 111e state of machine M at time t / is called the initial state of M. Since t / is arbitrary. the initial state of M is commonly token as the state in which Mis found whcn first presented to the invcstigator. The state of machine M at timc I is called the final state of machine M. v CIIAMT~ THREE TlmORY OF FlNITE-SfATE MACHlNFS 32 'J)mORRM 3•• Let Mbe a nontrivial machine with characterizing functions! andf.. Then the response of M. I S at any initial state (1., to any input sequence ~'J~'" •••• s.,: I I I.:. u • • is not predictable if only! andf. are known; I S is predictable ifI.,I. and a, are known. I S The proof of this theorem can be found in [13]. The functions! and f. of a FSM arc t S analogous to the equilibrium equations characterizing a linear device. with the initial state of the machine analogous to the initial energy distribution in the linear device. The response of the device to any given excitation can be predicted whcn both the equilibrium equation and the initial energy distribution nrc known. but it isunpredictable when the initial energy distribution is not specified. 3.3) TRANSITION TAllLES. DIAGRAMS AND MATRICF..s Once all the variables of a system arc established. the system can be formalized by means of a table, a diagram or a matrix. The table, diagram or matrix are alternative fonns of displaying the characterizing functions of the FSM. Such a display is indispensable to any precise analysis or synthesis of a FSM and it will beused extensively. 3.3.1) Tne TRANSmON TABLES The characterizing functions I. and I. can be displayed in a tabular form referred to as the t s transition table. This table lists the values of the two functions for all possible arguments, i.e.• for all possible ordered pairs (x ,s ). where x ranges over the input alphabet X and s over the v v v v state set S. The format of the transition table for a machine whose input alphabet is {~t' ~2'''' , spl. output alphabet is {~I' t2, ..·, tq }, and stateset is {a., 02' •••• On}' is shown in table 3.1. TIle table is composed of two adjacent subtables, the 1 subtable and the s 1 v v+ subtable, which display I andI., respectively. The two subtahles have a common stub which : s lists all possible present states s : the column headings in both subtables arc the same and v consist of all possible present input symbols xv' 111e rows, then, arc labelled 0.,°2, ... , all' and the columns ~I' ~2' ... 'Sp' TIle entry common to the row (1, and column s} is.f:(;. (1) in the z suhtahle and is], (~., a.) in the s J subtable. 111C Z and S J entries arc seen to range v S J I v+ V v+ over the output alphabet Z and the stale set S, respectively, or over any subset thereof. See table 3.1. Under the assumption that f and I are the characterizing function of a deterministic. t S CUAPrnR 1'IIRIm TlIF~RYOF FlNrrn-SfATE MACJlJNF.S 33 nonrestricted machine, these functions must be uniquely defined forevery ordered pair (r ,S I, v " where x ranges over X and s over S. Consequently, the z subtable must contain exactly one v " y clement of Z and the S J subtable exactly one element of S at the intersection of every rowy+ and column. z s v y+J x ~I ~2 ... ~p ~I ~ ... ~p "s " 0'1 0'2 · Enlrics Entries · lIClcctcd rrom selected rrom · tl, t2, ..• , tq 0'1' 0'2' ••• , an ·0' n TABLE 3.1 GENERAL TRANsmON TABLE EXAMPLE 3.1 To illustrate the variety of situations which lend themselves to representation by the basic finite-state model, an example is presented. TIle pertinent input alphabet X, output alphabet Z and an appropriate state set S is listed. TIle names of the states will be so chosen as to convey the system conditions which the states imply. Given: An English text, composed of the 26 letters of the alphabet and spaces has to be scanned with the purpose of counting the number of wonts starting with "un" and cnding with "d" (i.e, "understand", "united", etc.), For simplicity, a space will be designated by 1C and letters other thand, nand u by A. For this machinc: X = (d, II, u, x, AI; 7. = (Count, No count I; s = (New word, Wait for new word, Mark u, Mark u-n, Mark u-n-di relabeled as (I, 2, 3,4,5). CIIAlrnm TlIRFE 1lIP.DRY OF flNIm-srATE MAClIINFS 34 To illustrate the construction of a transition table, table 3.2 shows the transition table for the system described. The system is referred to as "machine At" and the states "New word". "Wnit for new word", "Mark u", "Mark u-n", "Mark u-n-d" arc relabeled as 1, 2, 3. 4 and 5 respectively. TIle table entries constitute the numerical counterpart to the verbal arguments justifying the choice ofstate set. When the input is "Jr", the next state is "New Word", regardless of the present state. If the present state "Mark u-n-d' and the input is "n", the output is "Count"; under all other conditions the output is "No count". If the present state is "New word" and the input is "u". the next state is "Mark u"; if the input is "d", lin" or "A", the next state is "Wait for new word". If the present state is "Mark u" and the input is "n". the next state is "Mark u-n"; if the input is "d", "u" or "A", the next state is "Wait for new word". If the present state is "Mark u·n" or "Mark u-n-d" and the input is "d", the next state is "Mark u-n-d"; if the input is "n", "UN or ").... the next state is "Murk II-n". If the state is "Wait for new word" and the input is other than "x", the state remains unchanged. z s v HI x d 11 U 3C ). d n u 1C ,\v S v 1 0 0 0 0 0 2 2 3 1 2 2 0 0 0 0 0 2 2 2 1 2 3 0 0 0 0 0 2 4 2 1 2 4 0 0 0 0 0 5 4 4 1 4 5 0 0 0 1 0 5 4 4 1 4 TADLE 3.2 MACHINE AI 3.3.2) Tns TRANSmON DIAGRAM The transition diagram can he considered as a directed graph and is a structure composed of vertices, drown as smnll circles and of edges or oriented branches, drawn as lines between pairs of vertices, with arrow signs pointing from one vertex to the other. A trnnsition diagram describing an n-state machine contains n vertices, each vertex representing a different state; the state represented by a vertex is identified hy the label attached to this CIIAIYffiR TJlREP. THEORY OP FlNIlE-SfAm MACIIINES 35 vertex. The oriented branches arc drown and labelled according to the following nile: Let X. ={~J' ~2' ... , ~ } be thc set of.\' values for which! (t • a.> =a .• and Ictf (gil' a)J r v SV" I' =~1I for h =1.2, ..., r. If Xj is nonempty a branch is drawn from the vertex labeled a, to the vertex labeled a.; the arrow sign of this branch is pointed J . the symmetric law ( if C1. = CJ.. then OJ = CJ.) and theI J J , , J , transitive law (if CJ. =C1. and CJ. = CI,.• then C1. =CJJ. Consequently, state equivalence can be 'J J A. I II. treated as an ordinal)' equivalence relation and applied directly to sets of states of any size. State distinguishability. on the other hand, docs not obey the reflexive and transitive laws and. hence, can be applied only on pairs of states. In some cases equivalence or disti nguishability of a pair of states belonging to the same machine can be established by inspection of the transition table of this machine. Some of these cases arc described by means of the three lemmas. LEMMA 3.1 Let C1. and a. be states of machine M. If rows CJ. and CJ. in the z subtable of M are distinct , J , J v then C1. 'I- a: , J LEMMA 3.2 Let C1; and ~ be states of machine M. If rows C1, and ~ spanning the entire transition table of M. are identical. then CJ, = C1r LEMMA 3.3 Let a. and aj be states of machine M. If rows C1. and a. spanning the entire transition table of, , J M. become identical when every a, is replaced by ~. (or every C] is replaced by ail then (1, = C1~ J CHAPTER nlREE THEORY OFFINITE-SfATE MACIIINES 40 h/l) FIGURE 3.4 MACIlINE A2 Pairs of rows which exhibit the property cited in lemma 3.1 are said to be simply distlnguishable. Pairs of rows which exhibit the properties cited in lemma 3.2 or lemma 3.3 are said to be simply equivalent. We thus have: THEOREM 3.2 If 0, and a. are simply distinguishable, then 0, ~ a: If a. and 0, aresimply equivalent, then Of I J I J I J =(J. J It should be pointed out that the converse of theorem 3.2 is nottrue: Not every distinguishable pair of states is simply distinguishable and not every equivalent pair of states is simply equivalent. To illustrate lemmas 3.1 to 3.3, consider machine A2, specified by figure 3.4 and table 3.3. It can be noted that rows 1 and 5 in the transition table arc identical and that rows 2 and 6 become identical when every 2 is replaced by 6 (or every 6 is replaced by 2). Consequently, each of the state pairs (1, 5) and (2, 6) is equivalent, A glance at the z" subtable of machine 2 reveals that no state in the set (1, 4, 5, 8) can be equivalent to any state in the set (2, 3, 6, 7). CIIAIFJ'F.R TlIRP.F. TIIP.DRY OF ANrrn-SfA'm MACInNES 41 z S"'.1.., x a f3 r a f3 rv S v 1 1 0 1 2 '5 5 2 0 1 1 6 2 5 3 0 1 1 2 2 7 4 1 0 1 8 3 1 5 1 0 1 2 5 5 6 0 1 1 2 6 5 7 0 1 1 6 6 3 8 1 0 1 8 7 5 TAnw3.3 MACIIINB A2 3.5.1.1) k-EQUIVALENCE A useful notation for future discussions is that ofk-equivalence: DEFlNmON 3.3 State a; of machine M. and state C] of machine M2 arc said to be k-equivalcnt, if M1/ C1i and M!~, when excited by an input sequence of length k, yield identical output sequences. If C1{ and ~ arc not k-equivalentthey are said to be k-distinguishable. M1and M2 may refer to the same machine. Thus C1. and a. arc k·cquivalent iff there is no way of distinguishing, by using input sequences I J of length k and by observing the external terminals, between machine MI at state C1i and machine M2 at state C1j From definition 3.2 it can be readily verified that k'equivalence obeys the reflex, symmetric and transitive laws. Consequently, k-cquivnlence can be treated as ordinary equivalence relation and applied directly to sets of states of any size. LEMMA 3.4 • If two l\1ates nrc k·cquivnlent, then they nrc I-equivalent for every I ~ k: • If two states arc k-di~1inguishnhle, then they arc l-distinguishable for every I ~ k. CUAm!R TIIRlm TlIP.oRY OPFlNrrn·SfATB MACInNES 42 Thestate into which state 0, passes when an input sequence of length k is applied is called the ttll successor of 0, with respect to this sequence, 111e zeroth successor of D state is the state itself, TlmOIU~ 3.3 If states 0, and 0, are k·equivnlcnt and if their kth successors wilh respect to any input , J sequence of length k are equivalent. then 0, =Of TIIEORHM 3.4 If stlltcs 0, and (~nrc equivalent, then their tth successors. with respect to any input sequence of length k and for nny k, are equivalent. The preceding results can he used. in many cases. to estuhlish equivalence of states when the equivalence of other states is already established. Suppose. forexample that the puirsof states (1, 5} and (3. 7} in mnchine A2 of figure 3.4 are known to be equivalent. Consequently, the pair (", H) must be equivalent. since 4 and 8 lire l-equivalcnt, with the pairs (1,5) and (3,7) being their first successors, If the pair (4. 8} isknown to be equivalent , then the pairs (I, 5}, (2.61 and (3. 7) must also be equivalent, since they constitute pairs ofcorresponding states in paths originating in states 4 and 8. 3.5.1.2) A:-EQUIVALENCE PARTITIONS For the purpose of state minimization, it is of interest to divide, or partition. the states of a machine into classes according to the following criteria: • All states which belong to the same class must be k·cquivalent; • nil states which belong to different classes mustbe k-distinguishable. 111is partition is called the k-cquivalcnce partitioninG of the machine and is denoted by Pi' 111e classes of p~ arc called k-equivalcncc classes nnd nrc denoted by ru ' Iu ' Iv. etc. States belonging to the same class arc called m/joint states; states belonging to different classes ara called tli90inr states, IJ~MA 1.5 TIle t'cquivnlcnce partition of n machine il& unique, Lr~MA 3.6 States which arc disjoint in p~ must also be disjoint in PhI' CIIAlrrP.R TIIRF.F. 'nmORY OF FJNJTP.-SI'Am MACHINES 43 I.EMMA 3.7 If machine M contains two distinguishable states which are r-cqulvalent, then it must also contain two states which arek-equivnlent but (k + t)-distinguishable. TIIEORF.M 3.5 Pt + } must be a proper refinement of Pt , unless the adjoint states in every class of Pi are equivalent, in which case Pk and Pk+J arc identical. In any but the simplest cases, the process of determining the equivalence partition of a given machine by inspection of the transition table ordiagram is virtually impossible. A method for describing the partitioning can be carried out systematically, by constructing a series of so-called PI: tables. The Pk table of a given machine is essentially the same as thesv+} subtable for that machine, with the following modifications: If {a. l , a,'2' ..., o. } is a class in p,., rows a.}. a." .... u, are grouped together.",r /1;' U r each group from the adjacent ones by a rule. The order of the groups in the table and the order of the rows within each group are arbitrary. Rows which belong to the same group and hence represent a k-equivalence class. will be called adjoint rows; rows which belong to different groups will be called disjoint rows; a "r" column is added. which labels each group of rows in the Pk table. The labels are arbitrary and may bechosen independently ineach new Pk table; a subscript is attached to every s"+1 entry, which identifies the group in the Pk table to which the entry belongs. Thus, if row a. is in the group labelled "a"., then every s }entry" 0." is assigned the subscript "a".v+ , Tables 3.4 to 3.7 are the PI' P2' P3 and P4 tables for machine A3 of figure 3.5. 3.5.1.3) CONSTRUCTION OF Pk T AnLr~ 3.5.1.3.1) CONSTRucnON OPTIm PI TAnlF. Reorder the rows of the transition tahie so that rows which are identical in the z subtable v become adjnccnt. Each group of such rows corresponds to a l-equivalence class and hence to a group of adjoint rows in the PI table. The PI table can now be constructed by CIIAIFJl~ THREE (0/1) v (1lIO) (a/O) (all) TlIEORV OP FlNITF.-STATI! MACIIINP.S 44 (~/O) (0/0) V <'r/I) (Il/I) ( 'r/I) FIGURE 3.5 MACIIINE AJ (6/1) deleting the z subtable, separating the row groups by rules, adding a "1:" column and v subscripting the S J entries as described above. v+ 3.5.1.3.2) CONSfRUcnON OF TIlE PhI TADLE (k ~ 1) A pair of adjoint rows in the PA: table which, in every column, exhibit identical subscripts are adjoint rows in the Pk+1 table. A pair of adjoint rows in the Pk table which, in some column, exhibit different subscripts arc disjoint rows in the PA:+I table. Disjoint rows in the Pk table are also disjoint in the PA:+J table. A group in the Pk table consisting of a single row remains a single-row group in the PA:+J table. Thus, the groups of the Pk+ J table can be established by inspection of the subscripts in the Pk table. Once the groups arc established, the table itself can be constructed according to the format stipulated above. The justification for the foregoing niles follows directly from the manner in which the subscripts are assigned and from the criteria for determining PhI from Pl. As an example, consider the P3 table for machine AJ, shown in table 3.6. In group -a-, rows I. 3 and 8 have identical subscripts in every column and so do rows 5 and 7 (whose subscripts differ from those of I. 3 and 8). Consequently, rows I. 3 and 8 and rows 5 and 7 enAPTF.R TIIRP.E s v+1 . x a (J y .. E s .. t 2b 2b Sa 3 2b 2b Sa a 5 6b 4b 3a 7 6b 2b 8a 8 4b 4b 7a 2 1a 4b 4b 4 3a 2b 2b b 6 8a 9b 6b 9 7a 9b 7a TARLE 3.4 P1TADLE FOR A3 TlIP.QRY OF FlNrm-SfATE MACIIINES 45 sHI x a f3 y .. l: s v 1 2b 2b 5a 3 2b 2b Sa a 5 6b 4b 3a 7 6b 2b 8a 8 4b 4b 7a 2 1a 4b 4b b 4 3a 2b 2b 6 8a ge 6b c 9 7a ge 7a TADLE 3.5 P2 TABLE FOR A3 constitute two groups of rows in the P4 table. In group "b" all rows exhibit identical subscripts in every column and hence the group remains intact in the P4 table. Groups "e" and "d", consisting of one row each, can be transferred intact to the P4 table. Given a procedure for constructing the PI table and the PhI table from the PA: table (): ~ 1), one can construct the Pk table for successive values of k, until a table is obtained in which all adjoint rows exhibit identical subscripts in every column. TIle stub entries of these adjoint rows represent equivalent states and hence the groups of stub entries in this table represent the desired equivalence classes. For machine A3 the condition is exhibited by the P4 table in table 3.7. TIle equivalence partition for mnchine A3 is, therefore, given by: P: {I, 3, 8}, (2, 4), (5, 7), (6), (9) CIIAP1l!R TIIRtm Svt/ x a p tv ~ S v t 2b 2b Sa 3 2b 2b Sa (I 5 6c 4b 3a 7 6c 2b 8a 8 4b 4b 7a 2 la 4b 4b b 4 3a 2b 2b c 6 8a 9d 6c d 9 7a 9d 7a TABLE 3.6 P3 TABLE FOR A3 3.5.2) MACIIINE EQUIVALENCE TUEORY OP FlNITE-SI'A'm MACJlINES 46 s v+/ X a (J y v r s v t 2b 2b Sc a 3 2b 2b Sc 8 4b 4b 7c 2 la 4b 4b b 4 3(1 2b 2b 5 6d 4b 3a c 7 6d 2b 8a d 6 8a ge 6d e 9 7c g e 7 c TAOLE 3.7 P4TABLE FOR A3 The concept of equivalence can be extended to entire machines, through the following definition: DEFINmON 3.4 Machine M. and machine M2 are said to be equivalent if to each state 0; of M. there corresponds at least one state of M2 which is equivalent to (1; and to each state C] of M2there corresponds at le3!11 one state of M I which is equivalent to (1j If M. and M2 ore not equivalent, they are said to he dlstlnguishable. CIIAPmR TIIRr~ TIIP.DRY OP FlNrm-STATE MACIIINES 47 111l1S, M. and M2 are equivalent iff there is no way of distinguishing. by observing the external terminals, between machine M. at any of its states and machine M2 and between machine M2 at any of its states and machine MI' M 1 and M2 are distinguishable iff there is at least one state in M1 which is not equivalent to any state in M2• or at least onestate (~/I) (PM (all) FIGURE 3.6 MACIIINE A4 in M2 which is not equivalent to any state Mr Equivalence between M1 and M 2 is indicated hy Mt =M 2 and distinguishablity is indicated by M. i- M2' From definition 3.4 it can be readily verified that machine equivalence obeys the reflexive law (M, =M}. the symmetric law (if M. =M., then M. =M,) and the transitive law (M. = M. and Mj =MI.' then M, =M.'>., J J' 'J'" A Consequently, machine equivalence can be treated as an ordinary equivalence relation and applied directly to sets of machines of any size. ((111) FIGURE 3.7 MAClIlNR AS Machines A4 and AS of figures 3.6 nnd 3.7, respectively, represent two equivalent machines. ntis can be verified by noticing that machine AS becomes identical to machine A4 when sme 3 of machine A4 is ignored; consequently, states) and 2 of machine A4 arc equivalent to states I and 2. respectively, of machine AS. Also states) and J of machine A4 are simply equivalent and hence equivalent; consequently, state 3 of machine A4 is equivalent to stllte ) of machine AS. 48 CHAPrER4 MODULATION CODES FOR CLOCK EXTRACTION Perhaps some future historian will classify this as the digital age, when everyday processes increasingly came to be performed using discrete numbers. Theprinciples of numerical coding can be found in this chapter, accentuating modulation codes. Modulation codes, ie. codes based on runlcngth-limited (RLL) sequences or (tI, k) constrained codes are, at present, used on disk recorders whether their nature is magnetic or optical. By far the most frequently reported coding schemes applied in recording practice have been those constituted by RLL sequences. Although this study is not concerned with recorders, it is with this type of coding scheme that this chapter is almost exclusively concerned. TIIC reason for this is to providc a thorough background on RLL sequences for reference in chapters to follow, since we shall investigate modulation codes for usc on channels other than recording channels. 4.1) INTRODUCl10N Many popular recording codes for peak detection channels fnll into the class of RLL codes. A digital magnetic recording channel is an example of a peak detection channel. For an indepth description of such a channel sec [3]. These (d, k) codes, in their general form, were CIIAPmR FOUR MODULATION COD~ FOR ClOCK ExTRAcnON 49 pioneered by Freiman and Wyner[t5]. Kautz[l6], Gabor[t7J. Tang and 8ahl[18] and notably by P. Franaszek [19J in the late 1960's. Since then. a considerable body of engineering and mathematical literature have been written on the subject. The length of time usually expressed in channel bits between transitions is known as the nmlcngth. RLL sequences are characterized by two parameters, (d + 1) and (k + 1) which stipulate. respectively. the minimum and maximum runlength that may occur in the sequence. The parameter d controls the highest transition frequency, and thus has a bearing on intersymbol interference when the sequence is conveyed over a bandwidth-limited channel. In the transmission of binary data It is generally desirable that thc received signal isself-synchronizing or self-clocking. Timing is commonly recovered with a phase-locked loop which adjusts the phase of the detection instant according to observed transitions of the received waveform. The parameter k ensures adequate frequency of transitions for synchronization of the received data. This quality is of interest for usc on mobile radlo channels, DEFINmON 4.1 A elk-Iimitcd binary sequence, in short, td, k) sequence, satisfies simultaneously the following two conditions: I) d constraint: Two logical "ones" are separated by a nan of consecutive "zeros" of length at least d. 2) k constraint: Any run of consecutive "zeros" is of length at most k, If only condition I is satisfied, the sequence is said to be d-Iimited (with k = - ) and will be termed d-sequence. In general, a id, k)-sequcnce is employed in optical recording. magnetic recording and mobile radio channels with a simple preceding step. A td, k)-sequence is converted to a runlength-lirnited channel sequence in the following way. Let the channel signals be represented by a sequence {Yi),Y' e {-I. I}. The logical "ones" in the (d, k)-sequence indicate the positions of a transition 1 .. -lor -1 -. 1 of the corresponding runtength-limited sequences. EXAMPlE 4.1 Consider the binary Vi, k)·sequcnce given by: Coder output: 0 1 0 0 0 I 0 0 1 0 0 0 1 10 I ... The transformed RLL channel sequence would be converted to: CIIAPlV.R FOUR MODULATION CODFS FOR CLOCK ExTRAcnON 50 Channel waveform: 1 -1 -1 -I ·11 1 1 -1 -1 -1 -I I -1·1 1 The mapping of the wavefonn by the precoding step is known asnon-retum-to-zero-inversion (NRZJ), or change of state encoding. Waveforms which arc transmitted without such an intermediate coding step are referred to as non-return-to-zero (NRZ). These names stcm (rom telegraphy and has no meaning in relation to recording channels; these nebulous tenns are in common usc and will be used throughout. It can readily be verified that the minimum and maximum distance between consecutive transitions of the RLL sequence derived from a (d, k)-scquence , respectively, isd + 1 and k + I symbols. For example, most flexible and low-end rigid disk files, as well as some high-end drives, today incorporate a code known as Modified Frequency Modulation (MFM). It also goes by other names, such as Delay Modulation or the Miller code. MFM is an RLL code with id, k) =(l, It 3). The usc of this code on the flexible 51/4 disk uscd on IBM PC's, made it possible to store twice the previous amount of data on a disk made of the same material. The reason for this will become more apparent later. The grounds on which d and k values are chosen, in tum, depend on various factors such as the channel response, the desired data rate (or infonnation density) and the jitter and noise characteristics. TIle problem faced by the coding theorist is the construction of a simple, efficient correspondence, or code mapping, between the arbitrary binary strings that a user might want to store on a magnetic disk or transmit over a channel, and the id, k) constrained code strings which the peak detector can more easily recover correctly. The tenn "efficient" arc now given quantitative meaning, by introducing the third important parameter, the code rate. TIle conversion of arbitrary strings to constrained (d, k) strings could be accomplished as follows. Pick a codeword of length n. List all the strings of length n which satisfy the 'd, k) constraint. If there are at least t" such strings, assign a unique codeword to each of t" possible binary input words of length m. This kind of code mapping is commonly referred to as a block code. The ratio, mln, of input word length m to codeword length n is called the code rate, designated hy R. Since there are only t' unconstrnincd binary strings of length n, there will be less than this numher of constrainedcodewords, Therefore, the rate must satisfy mln < I. In fact there is II maximum achievable rate, called theShannon capacity C. In 1948, Shannon proved that, as the codeword length grows, the number of constrained codewords approaches 2Cn from below, for some constant C which depends on the code constraints. This CIIAIYJl~ FOUR MODULATION CODES FOR CLOCK ExTRAcnON 51 result implies that the rate mln of any code mapping for that constraint must satisfy mln S C. Roughly speaking. a code is called efficient if the rate mln is close to C. It is possible to derive the capacity C~/. k) of Cli. k)-scquences. Sequences that meet prescribed W. k) constrains may be thought of to be composed of phrases of lengthj + 1. d Sj S k, denoted by ( nI' rf'+/ rI' ~l: rI' .~'+J' of the fonn Iv, 1 , .... 1 ..... llr}, wher~ stands for a sequence of} consecutive "zeros". The characteristic equation of fli. k)·sequences ([2] and [3]) is (for finite k): Z·(k+l) + z-k + ... +z·{tl+l) _ 1 = O. or k+2 k+J l;·tI+J + 1 0z -z -z = Following Shannons definition. the capacity of a (ti. k) sequence isgiven by: C(t/. k) = lim lIn log N ,(II) n~OO 2 t where N/n) denotes the number of distinct d sequences of length n [3]. For large n, N (II)OC,tn d max (4.1) (4.2) (4.3) (4.4) Applying equation (4.3), the capacityof d constrained sequences. denoted by C(d. 00) is: C(d, 00) = 1 i m I/n log Nd(n) =log). . n~oo 2 2 max with). the maximum real root (eigen value) of the characteristic equation. max (4.5) Table 4.1 lists some of the capacities. CCtI. k). V~1IS the runlength parameters d and k. A complete list of (tl. k) capacities can be found in (20]. As can be seen in table 4.1. the quantity C(d. 00) supplies the maximum rate possible of any implemented code for a given d constraint. TIle capacity decreases with increasing d which may be a property of much concernon some channels, especially on mobile communication channels where there is such a bandwidth shortage. On a recording medium an increasing tl parameter, as will be seen in the following paragraph. suggests a higher density ratio. CIIAIYJl!R FOUR MODULATION CODES FORCLOCK ExTRAcnON 52 Some further results of computations. which arc obtained by numerical methods [3), are collected in table 4.2. The quantity DR. called(Iensity ratio, sometimes called packing (Icnsity which express the minimum physical distance between consecutive nansitions of an RLL sequence, is defined as: DR =vl+ J)R (4.6) where R is the rate of the RLL code. It can he seen in table 4.2 that an increase of the density ratio can be obtained at the expense of decreased code rate. It can even be shown that the density ratio DR can be made arbitrurily large by choosing the minimum runlength d sufficiently large. This follows from: DR =vi + Illog ).,2 max d=O d=1 d=2 d=3 d=4 k = 1 0.694242 0.000000 0.000000 0.000000 0.000000 2 0.879146 0.405685 0.000000 0.000000 0.000000 3 0.946777 0.551463 0.287761 0.000000 0.000000 4 0.975225 0.617447 0.405685 0.223180 0.000000 5 0.988109 0.650900 0.464958 0.321757 0.182342 6 0.994192 0.669032 0.497906 0.374585 0.266896 7 0.997134 0.679286 0.517370 0.405685 0.314230 8 0.998578 0.685252 0.529340 0.425068 0.343229 9 0.999292 0.688789 0.5369JJ 0.437620 0.361992 10 0.999647 0.690915 0.541797 0.445971 0.374585 11 0.999824 0.692203 0.544997 0.451640 0.383262 12 0.999912 0.692989 0.547114 0.455546 0.389359 13 0.999956 0.693471 0.548527 0.458268 0.393709 14 0.999978 0.693767 0.549475 0.460182 0.396847 15 0.999989 0.693949 0.550114 0.461539 0.399133 00 1.000000 0.694242 0.551463 0.464958 0.405685 TARLE 4.1 CAPAcrrY cu. I) VP.RSUS RUNLF.NOTII PARAMETF.RS d AND k TIle root of equation 4.2 Slltisfies (4.7) (4.8) CIIAP'J11.R FOUR MODULAnON COD~ FOR CLOCK ExTRAcnON 53 d C(d, -) (d + I)C(d, -) 1 0.694 1.388 2 0.551 1.654 3 0.465 1.860 4 0.406 2.028 TADLE4.2 C AND DR VF.RSUS MINIMUM RUNLENOTII d for large d [3]. Thus DR grows like a constant times log d, see table 4.2. Another important parameter in recording systems, is the width of the detection window, during which the presence or absence of a transition has to be detected. This detection window is of width mln data bit intervals and a large detection window is preferred due to possible bit synchronization imperfections during the read or receive process. It should be appreciated thatcodes with a larger value of d, and thus a lower rate, provide an increasingly difficult trade-off between the detection window and the density ratio in applications with very high information density and data rates. However, it was experimentally demonstrated that the detection window has no apparent influence on a mobile radio channel. This experimental results can be found in chapter 9. 4.2) Finite-State Transition Diagrams In this section the background developed in chapter 3 are put to usc in communication systems employing runlength-limited codes. Most (dt k) codes can be implemented as FSM's and D brief description of the procedure taken to develop a FSM for a specified Cd, k) sequence will be shown. One can employ efinite-state transition diagram (FSTD), also known as a Markov model, in order toconveniently represent the infinitude of binary strings sntisfying the Cd, 1;) constraint. This graph representation for constrained channel strings dates back to Shannon's seminal paper [21] and it was exploited by Franaszek in his work on RLL codes. figure 4.2 shows a FSTD for the (t, 3) consrralnt, It consists of a graph with 4 vertices, called states and oriented branches between them, called edges, represented by arrows, TIle edges are labelled with CIIAMF.R FoUR MODULAnON COD&c; FOR CLOCK ExTRAcnON 54 channel bits. Paths through the graph correspond precisely to the binary strings satisfying the (I, 3) constraint. A similar FSTD having k + 1 states can be used to describe any (d,!) constraint. While table 4.1 shows f.tl, k) sequences with their theoretical capacities C, table4.3 shows the practical achievable rates, R = mln im and n small integers), and the efficiencies" = RIC for a few constraints. 1 1 1 FIGURE 4.1 FJNTrn SfATE DIAGRAM FOR f.t/, k) =(1,3) The conclusion drawn from table 4.3 is that it is possible to construct codes in such a way that the rate will be near the theoretical limit for thecode. The rate R =112. (d, k) =(2, 7) code is currently applied in the IBM 3380 rigid disk drive. (P,k) CAPAcrrY RATH EFFIClHNCY C R '1 (0, 1) 0.6942 2/J 0.96 (1,3) 0.5515 112 0.91 (1,7) 0.679 2/J 0.98 (2,7) 0.5172 tl2 0.97 TAnLE4.3 COMPARISON OP COORS The capacity C of the RLL v,, 1:) constrained channel is directly related to the structure of the FSTD. TI,e state-transition matrix T=I .. is defined and associated to the FSTD with states I, IJ ..., k + 1as follows: CIIAPJ11.R FOUR MODULATION COD~ FOR CLOCK ExTRACTION 55 • tij =x, if there are x edges from state ; to statej; = O. otherwise. For example, for the -2 => a 01 => -1 => b 10 => +1 => c 11 => +2 => d Whcn the two input bits are repeated: => 0 => e DATA: 01 00 10 00 00 01 01 01 CODE SF.QUENCE: b a e a e b e b Using the previously outlined steps: What must be stored in the memory e/cmcnL'i? TIIC previouscode-word, because of the repetition rule in the code description, Draw a block dUlgram: 11lC hlock diagram, figure 5.7, shows the present data hils (01' D} and previous code wont (0 ,v being time dependent) as input to the system, with II five-level code word I'V (OJ) as output. CIIAPmR AVE FSM REPRFSFNrA110NS FOR CONSJ'RAINlID CODES 76 FIGURE 5.7 BLOCK DIAGRAM FOR ExAMPLE 5.2 SCI/ing up the truth table: Thc truth table iscomposed of the previously mentioned inputs and nn output, thc code wont. Consider table 5.3, the entries can be explained as follows: For thc first entry: the present data bits (Dr D2) arc 00, the previous code wont (0 ) was a, thus the present output must be e (following the coding rules); I'V second entry: the present data bits are 00, the previous code word was b, thus the present output must be a; third entry: the present data bits are 00, the previous code word was c, thus the present output must be a, etc. It is clear that a e as output will only be present when the previous code word would have been the same as the present code word. Derive a present state-nextstate diagram from the truth table: Consider table 5.4, the present states arc taken from the column designated by C and I the next states and outputs nrc taken as the CJ column. By re-assigning the emeries,V in C and C/ so that a becomes state A, b becomes state B ete., we have everythingI ,V that is necessary for a state diagram: inputs, present states, next states and outputs. Ifnecessary, minimize the slate diagram: For this example thnt was not even necessary. Table 5.5 shows the state transition table and figure 5.8 shows the state transition diagram. CIIAm~AvH FSM RHPRPSroNrA110NS FOR CONSTRAINF'D CODF'..s 77 D1 D C C12 I-v 0 0 a e 0 0 b n 0 0 c a 0 0 d n 0 0 e n 0 1 a b 0 1 b e 0 1 c b 0 1 d b 0 1 c h 1 0 n c 1 0 b c 1 0 c e 1 0 d c 1 0 e c 1 1 n d 1 1 b d 1 1 c d 1 1 d e 1 1 e d TABLES.3 rnrrn TABLE FOR ExAMPLE 52 . 00 01 10 11 00 01 10 11 A e b c d E B C 0 n n e c d A E C 0 C a b e d A B E 0 0 n b c c A B C E E n b c d A B C 0 TAOLE5.4 STAru TRANsmON TAmJ~ CIIAYrnR nvu FSM RRPRr..sENTAll0NS FOR CONSTRAINED CODES 78 Input P.S. N.S. Output 00 A E e 01 A n b 10 A C c 11 A D d 00 B A ' n 01 D E e 10 D C c 11 D D d 00 C A a 01 C n b 10 C E c 11 C D d 00 D A n 01 D n b 10 D C c 11 D E e 00 E A a 01 E n b 10 E C c 11 E D d TAllLE5.5 PRr~ENTSTATE- NF.-XTSTATETAnLE FIGURE 5.8 STArn TRANSmON DIAGRAM CIIAPTI!R AVE FSM REPRESENTATIONS FOR CONSTRAINED CODES 79 A test string from thestate diagram verifies thealgorithms validity. staning in state A: DATA: CODE SEQUF.NCE: 01 b 00 10 a c 00 a 00 01 c b 01 e 01 b 80 CHAPTER6 NEW RESULTS ON (O,k) MODULATION CODES With the necessary background on RLL codes developed in chapter 4, we have now acquired an infonnation-theoretical knowledge on the key aspects of these sequences, enabling us to venture deeper into this interesting field. As mentioned in chapter 4, the larger the d parameter, the lower the code rate R (table 4.1) and the larger the bandwidth when a constant data rate is to be achieved over a given channel. When mobile radio channels are considered, the available bandwidth must be used as efficiently as possible, see chapter 2. Hence, to gain clock extraction via modulation codes on mobile radio channels, a small or ultimately no d parameter must be compelled on the code stream, Thus, this chapter will look at a special class ofd and k parameters; the event where d =O. An interesting property of this class of vi, k) codes are that the channel capacities (e) of these codes asymptotical approach I for k .. 00. Further, they can be consnucted with practical coding rates of R = n-iln; for a relatively large n, clock extraction can be gained with a marginal loss in bandwidth. It is thus evident that this class of codes had to be investigated for usc on mobile radio channels. At present the well known Manchester, or rate R = ]12, (tl, k, C) =(0, I, I) code is used on mobile radio channels, thus further strengthening the idea of investigating this class of codes. CIIAM'ER SIX NEW RESULTS ON (0,k) MODULA110N CODES 81 At the moment only two (0. 1:) codes are widely used. the Group-Coded Recording (GCR), rate R = 4/5, (0, 2) code (3) and the rate R =8/9. (0, 3) code [29]. Doth these codes are used in a large variety of magnetic tape products. In the OCR code, 4 userbits are uniquely represented by 5 channel bits, while 8 user bits are mapped on 9 channel bits for the (0, 3) code. According to table 4.1, the capacity of a sequence with no runs of more than two "zeros" Is C(O. 2) ~ 0.879, while the channel capacity of a sequence with no runs of more than three "zeros" is C(O. 3) ~ 0.946. Jlence, the efficiencies of the aforementioned two codes are respectively '1=91 % and '1 =94%. As mentioned earlier, for a larger codeword length. n, an inclination to a smaller bandwidth can be achieved. With this in mind, a rate R = 11/12, (d, k) = (0.3) code was developed. using a newly developed time saving algorithm, the TS algorithm, TheTS algorithm can also be used in future when other (0, k) codes need to be developed. The efficiency of the aforementioned code is '1 =11/t:JC(O. 3) ~ 0.968, but more important. the bandwidth is almost the same as that of the uncoded data. Since the codeword length is so large, 211 bits. it was decided to present the code table for the encoder on a floppy disk, in the cover of this thesis. with filename 0_3.TXT. The code table for the decoder can be found on the same disk, with filename DECO_3.TXT. As Immink [3] points out. the dk constraints define a number of channel states; the states of a Markov model for a given dk constraint. The crucial problem for the creation of fixed-length (d. k) codes of minimum length. of which (0. k) codes is a subset. is to find a subset of states. referred to as principal states, of which there exist a sufficient number of sequences of length n terminating at other principle states. The existence of a set of principal states can also be used to verify the existence of a code with a specified rote and codeword length. Franaszek [19] developed a recursive search technique for determining the existence of a set of principal states through operations on the connection matrix. TIle advantage of the TS algorithm over the method developed by Franaszek is that a code book can be obtained while searching for the code existence. with a negligible loss in speed. A timesaving with the TS algorithm for large n is also anticipated, since the Franaszek algorithm involves plenty of multiplications (raising matrices to powers). Since the developed TS algorithm was so powerful and easy to implement on a digital computer, it was decided to do a complete search for the .class of (0, k) codes in the range 1 S k S 20 and 2 S n S 20. CUAP11!R SIX NEW R~ULTS ON (0,1) MODULA110N CODES 82 When something new is developed, it is wise and imperative, to confinn its validity. It was thus decided to first check the algorithm by duplicating the known results for the GCR and rate 8/9. (ti. 1:) = (0. 3) code. For the OCR code; from the 32 possible unconstrained combinations of 5 bits, 15 were eliminated, leaving 17 valid codewords, From the 512 possible unconstrained combinations of 9 bits, 219 can be eliminated leaving 293 valid codewords in the (0, 3) code. This Information, which can also be obtained from Immink [3], serves as confirmation of the TS algorithm. since the exact same number of valid codewords was obtained using theTS algorithm (sec tables 6.3 and 6.4). 6.1) Tim TS ALGORITIIM Pillis section wiII be devoted to a description of the TS algorithm. Consider the following representation of a candidate codeword. consisting of n bits; numbered from the least significant bit (LSB). 0, to the most significant bit (MSn), n-l: Potential codewords II-J o 11-2 1 , .... , ..., t-J o , ..., o o With the above representation in mind, the algorithm can be described step by step in the following way: When searching for valid codewords, the first Z'.2 n·bit binary words (in normal counting or hexicographical order) arc ignored, since we do not include codewords ending with more than one zero. In other words, if bit n-I is zero (the MSm. bit n-2 is not allowed to be zero: this was done since experimentation showed that the largest number of valid codewords can be obtained in the least time with this restriction; Next. bits 0 to 1:-1 of the remaining candidate codewords are searched for a violation of I: consecutive zeros. simultaneously with zeros that violate the k constraint from bit n·2 to bit k; • Finally, the number of valid codewords obtained in the previous search must be at least 1'./ for the (0. 1:) code to be valid. since wearcdealing with a code rate of R =n-i!«. The example to follow will give the reader a feeling how this algorithm can be implemented. CIIAM'F.R SIX NEW R~ULTSON (0,A:) MODULAll0N CODES 83 2 1 0 0 0 0 0 1 0 0 1 2 0 1 0 3 0 1 1 4 1 0 0 5 1 0 1 6 1 1 0 7 1 1 1 TAnLF. 6.1 CANDIDATE CODEWORDS FOR ExAMPLE 6.1 ExAMPU~6.1 In this example we shall construct a rate R =2/3, (d, k) = (0, 2) code. Admittedly this example docs not utilize the full power of theTS algorithm, but will serve a tutorial purpose. Using the previously outlined steps: Ihe first 2"-2 potentia! codewords mustbediscarded: With n =3, the first 23.2 =2 words are ignored, since bits2 and 1are both zeros. IJiLv 0 to k-I = 1 must be searched for a violation of k zeros; simultaneously with a search for a violation oft zeros from bitn-2 to bit k: Only word 4, in table 6.1, violate k zeros at bit positions 0 and 1, with no violation ofk zeros between bits n-t =2 and k-l = 1. For a rate R =n-ltn; (d, J:) = (0, 2) code to be valid, there must be at least Z'-1 =4 valid codewords: Since words 0, 1 and 4 arc invalid, the remaining words 2, 3, 5, 6 and 7 are valid, hence, there arc 5 valid and 3 unvalid codewords, and since 23•1 =4 < 5, a rate 2/3, (tI, k) = (0,2) code can be constructed with 5 potential codcwords. One of the codewords may be discarded, leaving 4 unique codewonJs to be mapped on by the t- I =22 =4 data bits. CUAP1F.R SIX NEW RESULTS ON (O,!) MODULAnON CODES 84 rille search with the TS algorithm was performed on an 10M AT compatible with a 16 Mllz clock. figures 6.1 to 6.2 compare the time in seconds ve~'1IS n for the 1'8 algorithm and an exhaustive search for valid codewords (i,e. exhaustively checking binary words 0 to 2"-1 (or violation of the k constraint), with k =4, 5 and 14 S n S 20. Figures 6.3 and 6.4 show 3D graphs for k versus n and the time in seconds for, respectively, the exhaustive search and the TS algorithm. The graphs show a constant improvement in speed for a fixed value of k. The TS algorithm achieves more than twice the speed of the exhaustive search. TIle gain of the TS algorithm is directly proportional to n; thelargern, the better the improvement on anexhaustive search. From the i' possible unconstrained combinations of n bits, the valid codewords in the first 2,,·1 unconstrained words, designated by No, were recorded, together with the valid codewords in the second i") unconstrained words, designated by N). Figures 6.5 to 6.8 show these valid wonts (and the sum No+N)} for different values of n, The reason why No and N1 were recorded, is to confinn the anticipation of more valid codewords in the second 2'1-1 unconstrained words, NJ' Figure 6.9 shows a comprehensive 3D graph with No+NJ, 1 SA: S 20 and 2!an S 20. Table 6.2 to 6.21 show the efficiencies and number of valid codewords for 1 S k S 20 and 2 S n S 20. When, for a specific k and n value, a code does not exist, no entries are listed in the efficiency ('1) column of tables 6.2 to 6.21. There are two possible reasons for this; firstly, the search yielded fewer than 1'.) valid codewords, and secondly, since these are block codes, the A: constraint could not be accomplished. This happens when k >n. CIIAI~.R SIX NEW R~ULTS ON (0. t) MODULAl1ON CODES 85 100 8 E C 0 N 0 8 .~ TI ALOOAIlHII I I 14 15 10 17 18 I; 20 n FIGURE 6.1 1~MR COMPARISON OFExHAUSTIVE SF.ARCH AND TS ALGORmlM FOR Ie =4 -------------------:;.+ 100~------------::ro<::._---::~:'---l 8 E C o N o8 10f..--::r'~--:::>,,~-----------j [ -- EXHAUSTIVE SEAACH -II- T8 ALOOAIlHII , 201817 n 1015 1l.--_-..L.. ~___L.__.L.._ _L--_ __' 14 FlOURE 6.2 1lMR COMPARISON OFExHAUSTIVE SEARCH AND TS ALGORmIM FOR Ie = 5 6.3 I:OR l~lfJ\m",vl': ,,"'·,"'",,!c,U wml 1 « 5, 14 11 S E N S S E C N o S o N o S (.'1mII1ll6A AL(:~ORITnM wm, 1 k NEW R~Ul.TS ON (0, A:) MODUI.ATION CODES 87 10 ------------------------ N U M 8 E n ----------- r --~Valld-W-o-,d-a :"-O'~"I·A· Valid Wo'da I" ,,'.•. Valid Wo'da I" ,,0 20IIIIII141~10 0.1 ... - -~.,. ~~-- I.n ~. .a _,.".. ,..•_--0· • ~ n FIGURH6.5 VALlI> COI>EWORI>S POR k =1, 2 S n S 20 10 -- -.---- - ---.- .• ------- -- --.•.. ----------- N U M 8 E n -~ Valid Wo,da '0 "0'''' -A- Valid Wo,da 100' -K- Valid Wo'da 10"0 10 12 14 n .- .. -.- III III 20 FIGURH 6.6 VAllO COOEWOROS FOR k =2, 2 S n S 20 10,---------------------, N U M 8 E R -~ Valid Wo,da '0 110.", A Valid Wo'da ,,, ., • - Valid Wo'da '0 110 0.1'· ~ 20 n FrOURP. 6.7 VALIn CODEWORDS FOR k =3, 2 S n S 20 ' 1IAI' m R SI EW RFSUI:rS ON (0 . k) MODULA'n N 10 H s . :t< :( U " ~of:M It .. ~ ;;. ~ 'J' II .\ 'I/ \ Vali d Wo u Sa In nO-n ' t v A Valid WOl d a '" n' K Valid Wo rd a In nO 0 .1 I 2 4 6 e ' 0 12 14 16 10 20 n F J(llJRE6.H VAI.\D ' ODEW OlmS FOR k = iI, 2 s 1\ 20 r--- (~.O .- z c () « - + f t { ) 0 e,3 ·( )z <:» ~_O 19 0 t ·e) --l 1'1CiURE 6.1) YAI.ID ' ODEWORDS ur AI ED w rrn TS AU iORfl1lM \' RItO, z + n o CIIAP'n~ SIX NEW RF.SUI.TS ON (0, k) MODUl.ATION CODES 89 n " No HI No+NI 2 0.720 1 1 2 3 0.961 1 2 3 4 · 2 3 5 5 · 3 5 8 6 · 5 8 13 7 · 8 13 21 8 · 13 21 34 9 · 21 3,1 55 10 · 34 55 89 11 · 55 89 144 12 · 89 144 233 13 · 144 233 377 14 · 233 3n 610 15 · 377 610 987 16 · 610 987 1597 17 · 987 1597 2584 18 · 1597 2584 4181 19 · 2584 4181 6765 20 · 4181 6765 10946 TAnLE6.2 k =I, C(O, 1) = 0.694242 n " No HI No+NI 2 0.569 1 2 3 3 0.758 2 3 5 4 0.853 3 6 9 5 0.910 6 11 17 6 · 11 20 31 7 · 20 37 57 8 · 37 68 105 9 · 68 125 193 10 · 125 230 355 11 · 230 423 653 12 · 423 n8 1201 13 · 778 1431 2209 14 · 1431 2632 4063 15 · 2632 4841 7473 16 · 4841 89Q.1 13745 17 · 8904 163n 25281 18 · 163n 30122 46499 19 · )0122 55403 85525 20 · 55403 101902 157305 TAnt.H6.3 k: =2, C(O, 2) =0.879146 CIIAI"I1~ SIX NEW RHSULTS ON (0, A;) MODULATION CODES 90 n " No Nl No+Nl 2 - 1 2 3 3 0.704 2 4 6 4 0.792 4 7 11 5 0.844 7 14 21 6 0.880 14 27 41 7 0.905 27 52 79 8 0.924 52 100 152 9 0.938 100 193 293 10 0.950 193 372 565 11 0.960 372 717 1089 12 0.968 717 1382 2099 13 - 1382 2664 4046 14 - 2664 5135 7799 15 · 5135 9898 15033 16 · 9898 19079 28977 17 - 19079 36776 55855 18 - 36776 70888 107664 19 - 70888 136641 207529 20 - 136641 263384 400025 TABU~6.4 k =3,C(O, 3) = 0.946777 n " No Nl No+Nl 2 - 1 2 3 3 · 2 4 6 4 0.769 4 8 12 5 0.820 8 15 23 6 0.854 15 30 45 7 0.878 30 59 89 8 0.897 59 116 175 9 0.911 116 228 344 10 0.922 228 448 676 11 0.932 448 881 1329 12 0.939 881 1732 2613 13 0.946 1732 3405 5137 14 0.952 3405 6694 10099 15 0.957 6694 13160 19854 16 0.961 13160 25872 39032 17 0.965 25872 508(13 76735 18 0.968 50863 99994 150857 19 0.971 99994 196583 2965n 20 0.974 196583 386472 583055 TAnLH6.5 k =4, C(O. 4) = 0.975225 CIIAIYJ'!R SIX NEW RF.SULTS ON (0, k) MODULATION CODF.5 91 n " No NI No+NI 2 · 1 2 3 3 · 2 4 6 4 · 4 8 12 5 0.809 8 16 24 6 0.843 16 31 47 7 0.867 31 62 93 8 0.885 62 123 185 9 0.899 123 244 367 10 0.910 244 484 728 11 0.920 484 960 1444 12 0.927 960 1904 2864 13 0.934 1904 srn 5681 14 0.939 3777 7492 11269 15 0.944 7492 14861 22353 16 0.948 14861 29478 44339 17 0.952 29478 58472 87950 18 0.955 58472 115984 174456 19 0.958 115984 230064 346048 20 0.961 230064 456351 686415 TABLE 6.6 k =5, C(O,5) = 0.988109 n " No Nl No+NI 2 - 1 2 3 3 - 2 4 6 4 · 4 8 12 5 · 8 16 24 6 0.838 16 32 48 7 0.862 32 63 95 8 0.880 63 126 189 9 0.894 126 251 377 10 0.905 251 500 751 11 0.914 500 996 1496 12 0.922 996 1984 2980 13 0.928 1984 3952 5936 14 0.933 3952 7872 11824 15 0.938 7872 15681 23553 16 0.942 15681 31236 46917 17 0.946 31236 62221 93457 18 0.949 62221 123942 186163 19 0.952 123942 2·16888 370830 20 0.955 246888 ·191792 738680 TAm.F. 6.7 k =6, C(O,6) =0.994192 CJ IAP1l~ SIX NEW RmiULTS ON (0, A:) MODULATION CODES 92 n " No NI No+NI 2 · 1 2 3 3 · 2 4 6 4 · 4 8 12 5 · 8 16 24 6 · 16 32 48 7 0.859 32 64 96 8 0.877 64 127 191 9 0.891 127 254 381 10 0.902 254 507 761 11 0.911 507 1012 1519 12 0.919 1012 2020 3032 13 0.925 2020 4032 6052 14 0.931 4032 8048 12080 15 0.936 8048 16064 24112 16 0.940 16064 32064 48128 17 0.943 32064 64001 96065 18 0.947 64001 127748 191749 19 0.950 127748 254989 382737 20 0.952 254989 508966 763955 TABLE 6.8 k =7, C(O, 7) = 0.997134 n " No NI No+NJ 2 · 1 2 3 3 · 2 4 6 4 · 4 8 12 5 - 8 16 24 6 · 16 32 48 7 - 32 64 96 8 0.876 64 128 192 9 0.890 128 255 383 10 0.901 255 510 765 11 0.910 510 1019 1529 12 0.917 1019 2036 3055 13 0.924 2036 4068 6104 14 0.929 4068 8128 12196 15 0.934 8128 16240 24368 16 0.9.18 16240 32448 48688 17 0.942 32448 64832 97280 18 0.945 64832 129536 194368 19 0.948 129536 258817 388353 20 0.951 258817 517124 775941 TAnw6.9 k =8, C(O, 8) = 0.998578 CIIAP1l~ SIX NEW RESULTS ON (0, k) MODULATION CODES 93 n ,., No Nt No+Nt 2 · 1 2 3 3 · 2 4 6 4 · 4 8 12 5 · 8 16 24 6 · 16 32 48 7 · 32 64 96 8 · 64 128 192 9 0.889 128 256 384 10 0.900 256 511 767 11 0.909 511 1022 1533 12 0.917 1022 2043 3065 13 0.923 2043 4084 6127 14 0.929 4084 8164 12248 15 0.933 8164 16320 24484 16 0.938 16320 32624 48944 17 0.941 32624 65216 97840 18 0.945 65216 130368 195584 19 0.948 130368 260608 390976 20 0.950 260608 520960 781568 TABLE 6.10 k =9, C(O, 9) = 0.999292 n ,., No Nt No+Nt 2 · 1 2 3 3 · 2 4 6 4 · 4 8 . 12 5 · 8 16 24 6 · 16 32 48 7 · 32 64 96 8 · 64 128 192 9 · 128 256 384 10 0.900 256 512 768 11 0.909 512 1023 1535 12 0.916 1023 2046 3069 13 0.923 2046 4091 6137 14 0.928 4091 8180 12271 15 0.933 8180 16356 24536 16 0.937 16356 32704 49060 17 0.941 32704 65392 98096 18 0.944 65392 130752 196144 19 0.947 130752 261440 392192 20 0.950 261440 522752 784192 TAnLP. 6.11 k =10, C(O, 10) =0.999647 NEW RESULTS ON (0, I) MODU1.A110N COOF..5 94 n " No N, No+N, 2 · 1 2 3 3 · 2 4 6 4 · 4 8 12 5 · 8 16 24 6 · 16 32 48 7 · 32 64 96 8 · 64 128 192 9 · 128 256 3M 10 · 256 512 768 11 0.909 512 1024 1536 12 0.916 1024 2047 3071 13 0.923 2047 4094 6141 14 0.928 4094 8187 12281 IS 0.933 8187 16372 24559 16 0.937 16372 32740 49112 17 0.941 32740 65472 98212 18 0.944 65472 130928 196400 19 0.947 130928 261824 392752 20 0.950 261824 523584 785408 TABLE 6.12 k = 11, C(O, 11) = 0.999824 n " No Nl No+N1 2 - 1 2 3 3 · 2 4 6 4 - 4 8 12 5 · 8 16 24 6 · 16 32 48 7 · 32 64 96 8 · 64 128 192 9 · 128 256 384 10 · 256 512 768 11 - 512 1024 1536 12 0.916 1024 2048 3072 13 0.923 2048 4095 6143 14 0.928 4095 8190 12285 15 0.933 8190 16379 24569 16 0.937 16379 32756 49135 17 0.941 32756 65508 98264 18 0.944 65508 131008 196516 19 0.947 131008 262000 393008 20 0.950 262000 523968 785968 TABU~6.'J k =12, C(O, 12) =0.999912 CIIAI~I1~ SIX NEW RRSUl.TS ON (0, k) MODUl.ATION CODP..s 95 n " No HI No+NI 2 · 1 2 3 3 · 2 4 6 4 · 4 8 12 5 · 8 16 24 6 · 16 32 ' 48 7 · 32 64 96 8 · 64 128 192 9 · 128 256 384 10 · 256 512 768 11 · 512 1024 1536 12 · 1024 2048 3072 13 0.923 2048 4096 6144 14 0.928 4096 8191 12287 15 0.933 8191 16382 24573 16 0.937 16382 32763 49145 17 0.941 32763 65524 98287 18 0.944 65524 131044 196568 19 0.947 131044 262080 393124 20 0.950 262080 524144 786224 TA8LE6.14 k = 13, C(O, 13) = 0.999956 n " No HI No+N I 2 · 1 2 3 3 · 2 4 6 4 · 4 8 12 5 · 8 16 24 6 · 16 32 48 7 · 32 64 96 8 · 64 128 192 9 · 128 256 384 10 · 256 512 768 11 · 512 1024 1536 12 · 1024 2048 3072 13 · 2048 4096 6144 14 0.928 4096 8192 12288 15 0.933 8192 16383 24575 16 0.937 16383 32766 49149 17 0.941 32766 65531 98297 18 0.944 65531 131060 196591 19 0.947 131060 262116 393176 20 0.950 262116 524224 786340 TAnu~ 6.15 k = 14, C(O, 14) = 0.999978 CIIAI"l~ SIX NEW RESUl.TS ON (0, k) MODUl.A110N CODES 96 n '1 No NI No+NI 2 - 1 2 3 3 · 2 4 6 4 · 4 8 12 5 · 8 16 24 6 · 16 32 48 7 · 32 64 96 8 · 64 128 192 9 · 128 256 384 10 - 256 512 768 11 - 512 1024 1536 12 · 1024 2048 3072 13 - 2048 4096 6144 14 · 4096 8192 12288 15 0.933 8192 16384 24576 16 0.937 16384 32767 49151 17 0.941 32767 65534 98301 18 0.944 65534 131067 196601 19 0.947 131067 262132 393199 20 0.950 262132 524260 786392 TABLE 6.16 k =15, C(O, 15) =0.999989 n '1 No NI No+NI 2 · 1 2 3 3 - 2 4 6 4 - 4 8 12 5 - 8 16 24 6 - 16 32 48 7 - 32 64 96 8 - 64 128 192 9 - 128 256 384 10 · 256 512 768 11 · 512 1024 1536 12 · 1024 2048 3072 13 - 2048 4096 6144 14 · 4096 8192 12288 15 · 8192 16384 24576 16 0.937 16384 32768 49152 17 0.941 32768 65535 98303 18 0.944 65535 131070 196605 19 0.947 131070 262139 393209 20 0.950 262139 524276 786415 TAnt...R6.17 k: =16, C(O, 16) =0.999994 CUAltl'P.R SIX NEW RESULTS ON (0, k) MODULATION CODES 97 n 1J No NI No+NI 2 · 1 2 3 3 · 2 4 6 4 · 4 8 12 5 · 8 16 24 6 · 16 32 48 7 · 32 64 96 8 · 64 128 192 9 · 128 256 384 10 · 256 512 768 11 · 512 1024 1536 12 · 1024 2048 3072 13 · 2048 4096 6144 14 · 4096 8192 12288 15 · 8192 16384 24576 16 · 16384 32768 49152 17 0.941 32768 65536 98304 18 0.944 65536 131071 196607 19 0.947 131071 262142 393213 20 0.950 262142 524283 786425 TAnLE6.18 k = 17, C(O, 17) = 0.999997 n 1J No NI No+NI 2 · 1 2 3 3 · 2 4 6 4 · 4 8 12 5 · 8 16 24 6 · 16 32 48 7 · 32 64 96 8 · 64 128 192 9 · 128 256 384 10 · 256 512 768 11 · 512 1024 1536 12 · 1024 2048 3072 13 · 2048 4096 6144 14 · 4096 8192 12288 15 · 8192 16384 24576 16 · 16384 32768 49152 17 · 32768 65536 98304 18 0.944 65536 131072 196608 19 0.947 131072 262143 393215 20 0.950 262143 524286 786429 TAnLE6.19 k =18, C(O, 18) = 0.999999 NEW RESUl.TS ON (0, k) MODUl.ATION CODF..s 98 n " No NI No+NI 2 · 1 2 3 3 - 2 4 6 4 - 4 8 12 5 · 8 16 24 6 · 16 32 48 7 · 32 64 96 8 · 64 128 192 9 · 128 256 384 10 · 256 512 768 11 · 512 1024 1536 12 · 1024 2048 3072 13 · 2048 4096 6144 14 · 4096 8192 12288 15 - 8192 16384 24576 16 · 16384 32768 49152 17 · 32768 65536 98304 18 - 65536 131072 196608 19 0.947 131072 262144 393216 20 0.950 262144 524287 786431 TAnrn6.20 k =19, C(O, 19) =0.999999 n " No NI No+NJ 2 - 1 2 3 3 - 2 4 6 4 · 4 8 12 5 · 8 16 24 6 · 16 32 48 7 - 32 64 96 8 · 64 128 192 9 - 128 256 384 10 - 256 512 768 11 - 512 1024 1536 12 · 1024 2048 3072 13 · 2048 4096 6144 14 · 4096 8192 12288 15 · 8192 16384 24576 16 · 16384 32768 49152 17 · 32768 65536 98304 18 · 65536 131072 196608 19 · 131072 262144 393216 20 0.950 262144 524288 786432 TAIU.E 6.21 k =20, C(O, 20) =0.999999 99 CHAPTER 7 EXPERIMENTAL SET UP With the theoretical background and theoretical results concluded, the experimental set up and experimental results obtained can be discussed. One might venture the opinion that the experimental results ratified this study; the results were truly meaningful. This chapter will give a system level (block diagram) discussion of the apparatus designed and developed to assist the experimental observations, while Appendix A comprehend the circuit diagrams and a confinnative discussion why certain components were used in the designs. Three basic designs are presented, the "flagship" of which is an JnM PCbased, programmable DSP finite-state machine generator, which consist of a Texas lnstruments TMS 32010 digital signal processor with a potential of sixteen 16-hit programmable input-output (I/O) ports. The PC act as an operating system for the nSf> processor hoard hy transferring pre-compiled program memory to static RAM common to the TMS and PC. This method ensures a quick and easy alternative to burning a ROM for every small change in the program. TIle second design consists of another PC based system incorporating the 8255 prr'.l:rammable pcriphera! interface (PPJ) and 8254 programmable event counter (PEC), both from Intel. This design assists the nSf> processor board in some essential timing CIIAIYJ'ER SEVF.N EXPERIMF.NTAL SET UP 100 functions and serve as baseband decoder for bandpass channel experiments conducted. The concourse of the previously mentioned designs will be made evident at a later stage in this chapter. Since this project concerned mobile experiments. it was impractical to implement the aforementioned PC apparatus in a vehicle to carry out the desired measurements. TIle best solution to this problem was to construct a dedicated piece of apparatus which could be interfaced with existing mobile equipment. The apparatus consisted of a programmable finite-state machine generator, an encoder, which could be programmed to test various modulation codes over a mobile VHF channel. This encoder was designed with existing modems in mind, which was already adopted for usc in a mobile environment (a suitable power supply and connectors were available for existing mobile radio transmitters), and had sockets available for plug in modules, like the encoder. A "plug in" decoder module was also designed for usc with the stationary receiving end modem. 7.1) DESIGN DESCRIIYfIONS As previously mentioned three designs arc presented. Figure 7.1 presents a block diagram of the IBM PC based, programmable DSP finite-state machine generator. Between the PC, TMS and the static memory on thc card there are tri-state buffers. These are needed to prevent any clashes on the bus of either processor; when the PC is transferring program memory to the static RAM, the TMS buffcr is in tri-state mode; whcn the TMS is reading program memory. the PC buffer is tri-stated, The concept of tri-state will be discussed in Appendix A. This unit was used as encoder for measuring spectra of various modulation codes; the spectra were necessary to decide which modulation codes were to be considered for usc over mobile communication channels. Chapter 8 deals with the results obtained in this investigation. Since modulation codes have rates R =mln < I, the data clock had to be divided by nand multiplied by m for correct coding. A programmable divide by n and multiply by m generator had to be developed. This was realized with an Intel 8254 PEC and a 4046 CMOS phase-locked loop (PLI.). 111e bandpass experiments required an encoder, the DSf» FSM, and a decoder to pcrfonn these experiments. The 8255 PPI enabled the PC to act assuch a decoder. CIIAIFJl!R SeVF.N ExPfl.RIMF.NTAL SET UP 101 Since spectra were measured at 1200 baud, it was decided to verify the usc of the super-fast TMS 320ClO. In othcrwords, to check if the TMS 320CIO was not anoverkill for measuring spectra at such low data rates, 111C spectrum of a rate 1/2, (tI, k) =0,3) code was measured with the TMS and PC, respectively depicted in figure 7.2 (a) and (b). 1llI-STATt COOlRot. SlAne ClOH1IlCI. 1M I'IDI PC 10 STAIlr NS lRl-STATt BUnTRS ANtI IllS IUS lilt DlClO l)(CODIHO LOClC FIGURE 7.1 BLOCK DIAGRAM OF TMS 320C10 DSPCARD Admittedly, the DSP FSM spectrum looks better; the symbols generated with the DSP FSM arc almost jitter free when leaving the encoder (thc smoother spectra), while the slower PC variation induced pulscwidth variations on the channel bits, not a desired property! 10 o -!\-------- ~ • ,0 J "'-----v~~ ·'0 ./ T - -- --u ~ "0 ·.0 '10 -- - .•. ,. o 01 A""L II UOC I••• II , ,. :I :16 Hon.. ALUID "1I0UIHCY ., -'0 "~-""._ ....._,~_._... - ... ~.......-..~"."'--_ .. ,,.-. __... -_.."'_.--... o 01 I II r r. :a :I, • Hon.. ALlIIO ,nlOUIHCY _""\11* I••• " FIGURE 7.2 SI'ECfRA OF MillER cons a) MP.ASURIID wrm TIlE DSP FSM b) M(~IID wrm AN 10M PC CIIAI'1lUl SRVRN ExPfUlIMFNfAL SET UP 102 '111C block diagram of the PPI-PEC unit is illustrated in figure 7.3. c::cm DATAam PPI an4 ~ PEe AHO D£COOlHO LOQC '-_--' INPUT C1J( DATA III ADOfl£SS BUS HP 482S11 DATA IBM PC IDIIImJI lNl'UT Q.J( • m " FlOURH 7.3 nl.OCK DIAGRAM FOR nMER CARD Since the well-known Intel 8751 microcontrollcr is so versatile, the mobile coders basically consist of this component, a divide-by-a, multiply by m circuit and a RS 232 - TTL - RS 232 , i converter. TIle mobile encoder and decoder arc the same circuit, but programmed differently. lienee, figure 7.4 showsone block diagram for both these units. TIle equipment developed in this study can be used for at least a few generations of post-graduate studies. For instance, mobile communications, at present in the RSA. operate at ] 200 to 4800 baud, which is well within reach of the DSP can! to do realistic frequency domain investigations. In addition, the mobile coders are fully programmable and can be used in future to implement mobile experiments; if error correcting codes are investigated. this error correcting codes can be programmed in the mobile-coders, and real-time tests cnn be conducted. 7.2) EXPERIMENTALStIT lit) 'This sectinn will he devoted to a block diagrammatic description of the experimental set up for thc bandpass experiments and the mohile experiments. CIIAm~ SRVF.N EXPF.RIMFNJ'AL SET UP 103 8751 OUTPUT 'lInIn FIGURE 7.4 nWCK DIAGRAMS FOR MonU.p. cooess The bandpass experiments were conducted as shown in figure 7.5. An liP 49258 BER meter [30] was used to generate a 29_1 = 511 PN-scqucnce. 'ntis PN-scqucnce was coded with a pre-programmed modulation code in the DSP FSM generator and transmitted through lowpass, highpass and bandpass filters with various cut off frequencies and slopes. The liP 49258 compares the decoded data, received from the I'C, with the transmitted data until a DER of 10-1 is achieved. The same PC can be used for both the encoder and decoder, since the DSP FSM runs, after being started, independent from the PC. TIle results obtained with these experiments arc presented in chapter 8. EIlCOClQ DATA QAT" I••0'2S~ _ FIGURE 7.5 nU>CK DIAGRAM FOR nANOJ-A.,CiS RXltf.RIMIWTS Mohile experiments were conducted with an experimental set up as shown in figure 7.6. Again the lIP 49258 nER mcter was used as data source for the mohile encoder. which was installed in a vehicle. Since only an analog radio was available, indirect modulation of the carrier had to be accomplished; the modern converts the digital coded signal to n sinusoidal CIIAMF.R SF.VF.N ExI'f1.RIMENTAL SET UP 104 analog signal. '111e modem could be programmed to either elght-phase-shlft-keying or four-phase-shift-keying: the output was then frequency translated to the VIIF region and transmitted to the base station, situated at the RAU. The process was reversed for the received signal. 111e received VIIF data was converted back .to a phase-shirt-keyed baseband signal and decoded by the decoder, where error-recording equipment [7J recorded the gap recording of the received data. 111c gap recording and related issues, together with the results obtained with this experiments, will be discussed in chapter9. I=H-H.:.H-~ FIGURE 7.6 BLOCK DIAGRAM FOR MORU..E ExPERIMfNrS 105 CHAPTER 8 FREQUENCY DOMAININVESTIGATION OFMODULATION CODES The communication systems engineer is often concerned with the signal location in the frequency domain and the signal bandwidth rather than the time transient analysis: this is, for example, useful when the energy of a signal lit a specific frequency is needed. This chapter will launch a frequency domain investigation of modulation codes. 8.1) EXPERIMENTAL SPECTRAL ANALYSIS A spectrum analyzer presents a window to the frequency domain, and, since this study concentrate on experimental rather than theoretical results, this apparatus was used to gain information applicable tothe frcquency domain. SpCClnllll analyzers come in two basic varieties: swept-tuned and real-time. '1tC swept spectrum analyzer looks at only one frequency at a lime and generates n complete spectrum by sweeping in time. 'ntis can he n real d isndvnntagc, since transient events cannot he measured. In addition, when scanning with narrow bandwidth, the ~'\VlOCP ratemust be kept slow. finally, only a small portion of the input signal is being used at anyone time, CIIAI"n~ EIGIrr FREQUHNCY DoMAIN INV~"OA"ONOF CODES 106 These disadvantages of swept spectrum analyzers are remedied in the real-time spectrum analyzers. which was used in this study. '111is spectrum analyzer is based on digital Fourier analysis, in particular the famous Cooley-Tukey fast Fourier transfonn (FFT). Using a fll~1 analog-to-digital converter. the analog input signal is converted to digital numbers where D special purpose computer implements the F(71'. generating a digital frequency spectrum. Since this method looks at all frequencies simultaneously. it has excellent sensitivity and speed. The spectrum obtained is thus the Fourier spectrum of the signal and not the power spectral density (PSD). When consulting literature on modulation codes. spectra usually refers to the PSI) anti not the Fourier spectra of a given code. llence, to havecomparable results. the PSD must he derived from the measured Fourier spectrum by calculating the square of each measured point. Luckily a shortcut exists. By plotting the measured Fourier spectra on a logarithmic scale. the spectra will have the same shape as the PSD. with an offset. If desired. the average power can also becalculated directly from the logarithmic Fourier spectra. Figures 8.1 and 8.2 depict the baseband spectra of the well-known rate R=1/2. (d. k) =0.3) Miller code on a linear and logarithmic scale. 111is spectra were compared to previously published spectra [3] and serves as an affinnation of the techniques and methods used to measure spectra of modulation codes. 1.4 -~. -- ._-,. & _. A M P L I T U D E 1.2 1 0.8 0.6 0.4 0.2 o o 0.2 0.4 0.6 0.8 1 1.2 1.4 NORMALIZED FnEQUENCY 1.6 1.8 2 AMPLITUD~ IN VOLT J·)(jlJRH ft.1 MHASUREJ> Sl'f·:tTRA OFRAll~ R =1/2. ~/. k) = (I. 3) Corm ON IJNHAR SCAl.F. CIIAI'11~ EIGIrr 10 --- FREQUENCY DoMAIN INVF..\'110A110N OF CODES 107 A M p L I T U D E 0.1 0.01 0.4 0.6 0.0 1 1.2 1.4 NORMALIZED FREQUENCY 0.001 o AMPLITUDE IN en 0.2 1 1_ I. __ _I • 1_ __ .1 __ J_ 1.6 ____ 1.__ . 1.0 2 FIGURE 8.2 MEASURED SPE<..IRA OF RATE R =1/2, (d, k) =(t. 3) CODP. ON LOOARmlMlC SCALE 8.2) SPECTRA OF MODUl..ATION CODr..s Table 8.1 summarizes the fourteen modulation codes investigated for usc on mobile communication channels. TIIC selected PN-scqucnce was a random sequence of 29_1 = SI1 bits, obtained from a liP 492511 bit error rate meter [30]; this specific PN-scquence was also used throughout as an information bit source for the codes generated. Further, the rate R = 8/9, VI, k) =(0, 3) code investigated, was developed by Patel [29], while thc rate R = 11/12, (d, k) = (0, 3) code was synthesized with the algorithm described in chapter 6. TIle DC-free codes, rate R =1/2, (tI, 1:, C) = (0, 1, 1); R = 1/2, (tI, t, C) =(1,4,3); R =1/2, ftl, t, C) = 0,5,3) and R = 1/2, (tI, k, C) = (0, 4, 1), arc respectively the more than well-known Manchester [31], IICF 132], Miller2 [3], and IIcdcman (33) codes. As mentioned in chapter4, the rate R =1/3, vi, k) = (3, 7) code was synthesized using the algorithms for sliding block codes, while the rate R = 1/2, (d, k) = (2, 7) is the well-known code uscd in 10M rigid disk drives 13]. Jacoby and Kost developed one of the several rate R =2/3, td, k) = (l , 7) codes [3·t]. This specific version was preferred over the others, because of the simplified decoder. 111C remaining four codes were synthesized hy van Renshurg and Ferreira 135]. CIIAI'n~ EIGIIT F'RRQUF.NCY DoMAIN JNV~"OAnON OF CODES 108 The encoders and decoders for the rate R = 1/3, ~/, k) = (3, 7) and rate R = 11/12, (tI, k) = (0, 3) codes can be found, respectively, in chapter 4 and, as mentioned in chapter 6, on the floppy disk at the back of this thesis, while the other encoders and decoders arc available in the enclosed references. MOI)ULA'nON RATE COI>I~ R ((I.J:) • (0,3) 8/9 ((I.J:) • (0,3) 11/12 ttlkC> IS (0.1, J) 1/2({lkC> "" (0.2. J) 1/2 II 0.4.3) 1/2((1.k,C> a 0.5.3) 1/2 and 8.3.c arc 500 liz and 1 kllz, 11m bandwidth of the highpass filters are 1 kllz, between 1 kl lz and 2 kllz. Filters with different phase shift responses were investigated. with no apparent effect on the results. 111011 PASS Low PASS nAND PASS 1:;& 200 4d' 1st 2rd 4d' 1st 200 4d' PN.SEQ 0.19 0.t4 0.10 0.62 0.65 0.70 0.72 0.76 0.80 (0,3)1 0.23 0.19 0.15 0.71 0.74 0.78 0.80 0.84 0.88 (0,3)2 0.21 0.16 0.13 0.67 0.71 0.75 o:n 0.82 0.86 (0,1,1) 0.70 0.64 0.58 1.32 1.36 1.41 1.31 1.36 1.42 (0,2,1) 0.50 0,45 0.39 1.11 1.15 1.20 1.31 1.35 1.41 0,2) 0.81 0.76 0.71 2.06 2.10 2.15 2.t3 2.17 2.22 0,3) 0.49 0.45 0.39 1.38 1.40 1.44 1.44 1.48 1.53 0,7) 0.31 0.26 0.20 1.06 1.10 1.15 1.13 1.17 1.23 0,4,3) 0.46 0.42 0.38 1.46 1.51 1.55 1.50 1.54 1.59 0,5,3) 0.45 0.42 0.37 1.50 1.56 1.60 1.53 1.57 1.62 (2,7) 0.40 0,35 0.31 1.17 1.20 1.25 1.39 1.43 1.47 (3,7)3 0.37 0,33 0.27 2.21 2.25 2.30 2.42 2.46 2.52 (4,7)4 0.46 0.41 0.38 2.91 2.96 3.10 3.24 3.28 3.36 (4,8)4 0.49 0.45 0.40 2.80 2.84 2.90 3.17 3.20 3.25 (5,9)4 0.48 0.44 0.39 2.91 2.1)6 3.00 3.22 3.26 3.30 I) Rale R =Rr) 2) Rale R =11/12 RC!l1: R =1{2 3) Rate R • 1/3 4) Rate R • 1/4 TAnll~ 8.2 BANDPASS r..xmRIMENT RESULTS CIIAlrJ11.R EIGHT FREQUENCY DoMAIN INVF~"GA110NOF CODES III Since the liP 492513 llER meter played such an important role in the experimental set up, Appendix II contains the circuit diagram for the clock recovery and bit synchronization circuits used by the liP 49250bit error rate meter. The modulation codes investigated had different code rates, starting as high as R =11/12, going down to R =1/4. To be consistent the data rote for the investigated codes were constant; for a constant data rate and code rate of R =mln the bandwidth will increase nlm times over the PN-sequcnce bandwidth. The emeries in table 8.2 arc presented with ascending d parameter and frequencies normalized relative to the data rates of the codes. These entries are unitless quantities, indicating the code's performance through bandlimited channels with channel properties as outlined above. A discussion to interprctthe entries in table 8.2 will follow. Considerthe rate R =1/2, (d, k) =0, 3) fourth order highpass, lowpass and bandpass entries in table 8.2, respectively 0.39, 1.44 and 1.53. If the data rate for the modulation code is 600 bits/s, the entry 0.39 can be intcrpreted as follows: a channel with a poor low frequency response, suppressing frequencies from 0 lIz to a -3 dD cutoff frequency of 600 x 0.39 =234 liz will achieve a llER of lO-t for this modulation code; the entry 1.44 can be interpreted as follows: a channel with a poor high frequency response, suppressing frequencies from a -3 dB cutoff frequcncy of 600 x 1.44 = 864 liz upward will achieve a OER of 10- 1 for this modulation code and the cntry of 1.53 as: a channel with a poor high frequency and poor low frequency response need a -3 dB bandwidth of 600 x 1.53 =918 liz to achieve a BER of 10-1 for this modulation code, Consider figure 8.4; the highpass filter results were obtained in this way. A lowpass filtcr with cutoff frequcncy nlm (at the first spectral null of thc modulation code under investigation) was positioned at the high frequency side of the modulation code spectra; starting at the origin (0 1170), thc highpass filter'scut off frequency was tuned higher until a HER of 10-1 was achieved, A definite threshold was observed: the bit crror rate increased suddenly from zero to 10-1• Since the k parameter determine the amount of energy at the low frequcncy side of the code spectra, this experiment quantified the influence of thc k parameter when transmitting the code sequences through n bandpass channel with poor low frequency response. CUAI"W.R EIGHT F'RHQUHNCY DoMAIN INVHSI10ATION OFCODES 112 10 ---- - - - -- 0 ---- --- --- - 0 0 o- f·': r.:»: :~.:;":'-':::': ~.:::'. T ~U , o I: -30 -&0 _. I . .•. 1_ .• I __.1 .• ,_~.1. ._~•••~_~_.I. o 02 0.4 00 011 I 12 1.4 III III 2 NOIlt.tAlllED fnEOUfHCY FIGURB 8.4 FlLmR SET Ult FOR IIJOIIPASS RESULTS The lowpass fiIter experiments were conducted as seen in figure 8.5. Starting at the first spectral null Inlm), the cutoff frequency of the low pass filter was lowered until a OER of 10./ was achieved. These results give a quantntive indication of the d parameter, since the tI parameter limits thc high frequency components of the modulationcode spectra. 10 --- A -10 t.I p l I -20 T U D E -30 -40 -60 _'_L~_I---&--l__-l__""'__.L-- o 02 0.4 0.11 011 I U l4 III III 2 NORMALIZED fnEOUENCY FIGURE 8.5 FlI.1T-.R ssr UP FOR LoWPASSFlLTF.R EXPERIMFNr The bandpass results were obtained (figure 8.6) by a low pass filtcr at the first spectral null and highpass filter at thc origin. By sequentially lowering thc lowpass filter's cut off frequency until thc threshold was observed, and raising the high pass filter's cut off frequency until the threshold was observed, a point was reached wherc thc BER was 10. 1• ntis experiment gives an indication of the simultaneous influcnce of thed and k parameters through a bandlimited channel, since the low and high frequcncy components nrc simultaneously affected by the filters. CJlAm~ EIGIIT FRRQUF.NCV DoMAIN INV(~"OATION OP CODES 113 10 [- - -- - - - _.._-j. l-lOW",,"lIli 'llUII .... HIGH'AIlI 'llUII·40 I-I·--·l-· ..·····•..-- ..·-·..--u.- ..- ....- .. - ..- 0--· A M P L I T U D e ·:SO .50 J __ ' ' .'_l__.. 1.----'_'__,_. o 0.2 0.4 0.11 0.11 I 1.2 1.4 1.11 1.& 2 NORMALIZED fREQUENCY FIGURE 8.6 foll.TIm srrr VI' FOR BANOPASS r..xPHRIMENTS In future. reference can he made to these quantitative comparative results when choosing a code for a bandlimitcd channel, Although this list is by no means exhaustive, a proper understanding of the influence of the d and k parameters through bandpass channels can be gained. For instance: for a large k parameter (more energy concentrated at low frequencies) a feeble response through a poor low frequency channel will be achieved. On the other hand a feeble response through a channel with a poor high frequency response will be achieved when the d parameter is increased. The DC-free property. the C parameter, will naturally only have an influence on the low frequency side of the spectrum, thus enabling a better response through a channel with poor low frequency properties. 8.4) MODULATION CODES FOR MODILE COMMUNICATION CHANNELS As a direct result of the bandpass experiments, five codes were selected for usc on mobile radio channels. 111e codes chosen were: the rate R=1/2, vi, k, C) = (0, I, 1) code, since it is already used on mobile radio channels [5] and [471, the rate R = 1/2. (d, k) = 0, 3) code, since it was recommended by the CerR [36], the rate R =2/J, vi, k) =0, 7) code, to look at the influence of the larger detection window (chapter 4) on a mobile radio channel, the rate R = 1/2, (d, k) = (2, 7) code, 10 consider the influepcc of a larger d parameter and, finally. the rete R =1/2. ~/, k, C) =(0,2, J) code, since the bandpass experiments showed that this code, although a rate R =1/2 code, cnn achieve a data rate comparable to a PN-scquence for the same bandwidth constraint. TI1C performance of these five modulation codes and the selected PN-sequcnce on a mobile radio channel is presented in chapter 9. One might venture to say that the rate R =11/12, ~/, k) =(0, J) code would be preferred on a mobile communication channel, since clock extraction nnd a relative small bandwidth CIIAIYJ'F.R EIGIIT AU~UHNCY DoMAIN INVE.\"OATION OF CODF.5 114 expansion can be gained from this code. However, the bandpass experiments showed that the rate R = 1/2, (tI, t, C) = (0,2, t) code also needed a small bandwidth, with, of course, clock extraction gained. When consulting figures 8.15 and 8.16 it is evident why this code needs such a small bandwidth; almost all the energy is concentrated in the first half (low frequency side) of the spectrum, thus enabling us to achieve a higher data rate through D bandllmlted channel. The rate R =11/12 code was thus rejected: the encoder and decoder complexity were also considerably reduced by using the rate R =1/2 code. Also, the decoder error propagation for the R= 1/2 code will be notably better. 8.5) MODULATION ScIIEME SPECTRA Since indirect modulation was used to transmit the modulation codes over the mobile radio channel, four modulation schemes were considered; g-ury PSK, -t-ary PSK, differential PSK (DPSK) and fast-frequency-shift-keying (I;'f'SK). 111e 8-ary PSK at 1600 baud, 4-nry PSK at 1200 baud and DPSK at 1200 baud werc generated by a Rockwell DTY-500 programmable modern [7). The FrSK modems employed the FX 419 and FX 429 chip sct from Consumer Microcircuits Limited [8] and werc generated at 1200 baud; a binary one is represented by one cycle of a 1200 liz sinusoidal and a binary zero is represented by one and a half cycles of a 1800 liz sinusoidal. Figures 8.35 to 8.40 describe the FFSK spectra of the five chosen modulation codes and the selected PN·scquencc on a logarithmic scale. Figures 8.41 to 8,43 describe a PN-scquence respectively as DPSK, 4·ary PSK and 8-ary PSK on a logarithmic scale. TI1C spectra of the five selected codes after PSK modulation looked very similar to the PSK modulated PN-scquence; the PSK spectra do not have any sharp peaks in the spectrum (figures 8.37 to 8.39), thus the modulation code spectrum isspread out over the whole PSK spectrum, a 2500 liz bandwidth for the g-ary PSK, which makes it very difficult to ohserve a difference in the various PSK spectra, A difference between the various modulation codes after FFSK can be observed because of the sharper peaks (more concentrated energyat a specific frequency] in the spectra. FFSK is known for its symmetric spectra; the sinusoidal transitions from a binary one to a binary zero (or vice versa) always change through the origin (mean value of sinusoidal). Thc PSK spectra, however, can make sinusoidal phase transitions fmm a binary one to a binary zero (orvice versa) anywhere, thus resulting in an unsymctric spectra (figul'CS 8.41 to 8.43). CJlAI""~ EIGIrr FREQUF.NCY DoMAIN JNVI~"OA"ON 011COOPS 115 1 - -0.8 A M 0.6P L I T U 0.4 D E 0.2 o o 0.1 0.2 - I . I I. . 0.3 0.4 0.5 0.6 0.7 NORMALIZED FREQUENCY 0.0 0.9 1 AMPLITUDE IN VOLT FIGURF. 8.7 SPE<..'TRUM OFTIm SELF.crFD PN·SEQUENCR ON A LINEAR SCALF. A M P L I 0.1 T U o E 0.01 . I I. . I .._ o 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.0 0.9 1 NORMALIZeD FREQUENCY AMPLITUDE IN dO FrGURF. 8.8 SPECTRUM OF11m SP,l£crno PN·SEQURNCP. ON A LoOARmlMIC SCAl.E CIIAI"I1~ Elmrr 7 6 . A 6 M p 4 . L I T 3 . U D E 2 . 1 F'REQUI~CY DoMAIN INVI~"OAnONOFCODr~ 116 o l-----IL.--L__I.__L--J_-.JL.----IL--l._-l..::::::~ o 0.112 0.226 0.337 0.45 0.563 0.675 0.788 0.9 1.013 1.125 NORMALIZED FREQUENCY AMPLITUDE IN VOLT R' 8/9 FIGURE 8.9 SPECrRUM or: A RAm R =8/9. Cli. k) =(0. 3) CODE ON A LINEAR SCALE . I A M P L I T U ~ 0.1 ~-:---~-~-~---~--~--::__-~_e__t 0.01 I-----J'----l'---_l-.-'-_-'__--L-__..._->-_-...._-" o 0.112 0.225 0.337 0.45 0.563 0.6750.788 0.9 1.013 1.12G NORMALIZED FREQUENCY AMPLITUDE IN dB R • 8/0 FIGURH 8.10 SrEt7RUM 01' A RAll~ R =8/9. ~J. i) =(0.3) CODE ON A 1.00ARI111MICSCAIJ~ CIIAI.,l!R EIGHT FREQUENCY DoMAIN INVI~nGA1l0NOF CODES 117 2r-----------------------, 1.76 1.6 A M 1.26 P L I T U D 0.76' E 0.6 0.26 . OL..----J'---__'-_-J.-_-1-_-L.-_--L-_--L-_--J-_--...L_~ o 0.109 0.218 0.327 0.436 0.646 0.655 0.764 0.873 0.982 1.091 NORMALIZED FREQUENCY AMPLITUDE IN VOLT FlGURR8.11 SI'EC"TRUM OF A RATE R = 11/12.l.IJ. k)= (0.3) CODR ONA LJNr~R SCALE A M P LI 0.1l--------------~----"-e----f T U D E 0.01 -.---~-------~--~-----:---~--l 0.001l.-.--lL.---1--.l---1-_J--...l_--!-,_-1-_..J.-_-.J o 0.109 0.218 0.327 0.4360.546 0.6660.7604 0.873 0.982 1.091 NORMALIZED FREQUENCY AMPLITUDE IN dB FlGURH 8.12 SPEcrRUM OF A RAm R =11/12. (d. k) =(0, 3) CODe ON A I.ooARmlMIC SCALI! CIIAI"n~ ElGirr 0.6 0.7 0.6 - A M 0.5 P L I 0.4 T U 0.30 E 0.2 0.1 0 0 FRHQUF.NCY DoMAIN INV~"OA"ONOF CODES 118 . I. . L. 0.2 0.4 0.6 0.6 1 1.2 1.4 1.6 1.8 2 NORMALIZED FREQUENCY AMPLITUDE IN VOLT FJGURH 8.13 SPEcrRUM OP A RATE R =1/2. (d. k. C) = (0. 1. 1) CODE ON A LtNl!AR SCALE A M P L I T U o E 0.1 0.0 1 .~ ./ ~ ./.----_.- .... ------.- ---- ..- ..._._ .._--_._----- .-._---- 0.00 1 a AMPLITUDE IN en I. "I 0.2 0.4 0.6 0.8 1 1.2 1.4 1.6 1.8 NORMALIZED FREQUENCY 2 FJOURH 8.14 SPECTRUM OF A RATE R =1/2. W. k. C) = (0, 1, I) CODE ON A UXlARrnrMlC SCAl.p. CIIAI>'fF.R EIGHT FRRQUP.NCY DoMAIN INVP~"OAnON OP CODES 119 3.5r--~---~-~------------, A M P L I T U o E 0.2 0.4 0.6 0.8 1 1.2 1.4 1.6 1.8 2 NORMALIZED FREQUENCY AMPLITUDE IN VOLT FIGURE 8.15 SPECTRUM OP A RATE R = 1/2, (p, k, £:) =(0,2, 1) CODE ON A LINEAR SCALE 10r------------~-----__:_-__, A M P L I T U o E 0.01 1_ --!__i __i.__l __J__L--_l---!._--L_--J o 0.2 0.4 0.6 0.8 1 1.2 1.4 1.6 1.8 2 NORMALIZED FREQUENCY AMPLITUDE IN dB FlOURH 8.16 SPEcrRUM OP A RAm R =1/2, (p, k, C) =(0, 2, J) COOl! ON A LOOARmlMtC SCALF. CIIAIYJ1!R EIGIIT FRRQUF.NCY DoMAIN INV~OA110NOF CODES 120 0.4 ------------- 0.35 - 0.2 0.15 - I .__ _I __ . 1_ _I _ _ L ---t-=~=:-l 30.3 0.6 0.9 1.2 1.5 1.8 2.1 2.4 2.7 NORMALIZED FREQUENCY o o 0.05 0.1 0.3 . A ~ 0.25 L I T U D E AMPLITUDE IN VOLT n • 1/3 FIGURE 8.17 SPEcrRUM OFA RAm R =1/2, (d, k) =0,2) CODE ONA LINEAR SCALE 1 .----.- .------.------.-. --.---------------, A M p L I T U D E 0.1 ~._---- 0.01 :---------.-----------.-- -----------.------~-.-----.-.-- 0.001 o I _ 0.3 0.6 0.9 1.2 1.5 1.8 2.1 2.4 2.7 NORMALIZED FREQUENCY 3 AMPLITUDE IN dO n· 1/3 FIGURH 8.18 SPECTRUM OF A RAm R =1/2, (d, k) =0,2) CODE ON A LOOARmlMtC SCALE CIIAlrn~ EIGIrr 1.2 FRF.QUl~<''Y DoMAIN INVI~"OAl1ONOF CODES 121 A 0.8M P L I O.G T U 0 0.4E 0.2 0 1- 0 0.25 AMPLITUDE IN VOLT 0.5 0.75 1 NORMALIZED FREQUENCY 1.25 i.e FIGURE 8.19 SPECfRUM OFA RAm R =2/3. VI. k) = O. 7) CODE ON A UNRAR SCALE 10 -;---- ----------- ---------------------------, A M P L I T U D E 1 -~ - -. - -- ---- - -- ------ - -------------- / ~ 0.1 0.01 o 0.25 0.5 Q75 1 NORMALIZED FREQUENCY 1.25 1.5 AMPLITUDE IN en FlOURE 8.20 SPE<.TRUM OF A RA"rn R =2/3. (d. k) =0, 7) CODE ON A tooARm'MlC SCAI.E CIIAl'mR EIGIIT 1.2 FREQUI~CY DoMAIN INVI~"GA"ONOF CODl!S 122 A M p L I T U D E 0.8 O.G 0.4 0.2 0 . I I .. I. . ..... I .... I. __ L .. ., L ... •.. 1.. .•.__1.___." 0 0.2 0.4 O.G 0.8 1 1.2 1.4 1.6 1.8 2 NORMALIZED FREQUENCY AMPLITUDE IN VOLT AGURH8.21 SPECTRUM OF A RA'rn R =1/2. (d. k. C) = (t. 4.3) coos ON A LINEAR SCALE A M P L I T U o E 10 -...- 0.1 0.01 ',,'-- ------ ..._- ._--_.---- .__._-_.- ---------, - . .--- ...- .... ---- _ ..~--- -----.. --·-..---1 0.001 o AMPLITUDE IN eln 0.2 0.4 I. ..1. . I. 0.6 0.8 1 1.2 1.4 NORMALlZr:o FREQUENCY r., 1.6 1_ ., 1.0 2 FIGURH8.12 SI'P.t'TRUM OF A RAm R =1/2. flf. k. C) = (1,4, 3) COJ)(~ ON A LOOARmlMIC SCALE CUAmR EIGHT FREQUI!N<"'Y DoMAIN INV~"OA110NOP CODES 123 1.2 --.-.---- -.-..-.-----.-----.-----.-.-----~ 1 A 0.8 . M P L I 0.6 T U D 0.4 .E 0.2 . o -.. o . I. .• _ I _.1_ .••• 1._...• 1_..•._.1 1..__ .1__.•._1.••__ 0.2 0.4 0.6 0.8 1 1.2 1.4 1.6 1.8 2 NORMALIZED FREOUENCY AMPLITUDE IN VOLT FlOURF. 8.23 SPECTRUM OF A RATE R =1/2. SroCTRUM OF A RAm R = ]/2, -"fi"'-" • .) '.' ,'" ('0' ... '.~ 't,.• __ "_ •• ,_·~_.o •• ".n IF." 17.01 17.7. ,7.1, '7.t1 ".01 TIIoII! FIGURE 9.7 SNR OF Vi, k, C) =(0, 2, 1) CODE IN CITY It is interesting to note that the SNR fluctuate roughly between 24 dO and 21.5 dB, with an average of 22.5924 dD. A strikingdifference between the SNR's for a city and highway environment is the larger SNR fluctuations in a highway environment. An explanation for the previous observation is twofold, the first of which is the higher overage speed on a highway and thus a more dominant doppler shift on the received signal and secondly, the mobile unit travelled a longer distance from the transmitter; the signal strength gets weaker and is more affected by fading conditions. The recorded SNR's for the other codes and the PN-scquence had a similar progress in city and highwayenvironments. Table 9.1 shows the measured bit error rates and signal-to-noise-ratios for the five modulation codes and the PN-scquence. It must be noted at this stage, that the channel rate (code rate) was fixed for a given modulation scheme, not the data rates; coherent modems were used and the channel rote was thus dictated by the modem baud rotc. Since the code rates, R =min, varied as indicated, the codes haddifferent data rates. Consulting Stremlcr (31 J. 4-ary PSK offers a good trade-off between power and bandwidth, requiring very modest increases (OJ· OA dB) in transmitted power for n potential doubling in bandwidth efficiency over that of coherent PSK. While an B-ary PSK modulation scheme offers a potential bandwidth efficiency of 3 hps/llz, it exacts n SNR penalty of almost 4 dB CHAPTER NINE CONSTRAINED CODES ON MOBn.B VIIF CUANNP.LS 142 CooP. MODULATION ENVIRONMF.Nr SNR DER SCIIF.MP. dO xl 0-3 PN·scq 4-ary PSK CITY 23.7 2.30 HIGHWAY 22.2 4.88 8-ary PSK CITY 23.1 2.10 JIIGHWAY 23.0 2.60 (0,1,1) 4-ary PSK CITY 22.3 2.95 HIGHWAY 21.1 6.29 8-ary PSK CITY 21.9 1.88 HIGIiWAY 21.0 3.29 (0,2,1) 4-ary PSK CITY 21.8 1.93 HlGIlWAY 21.4 4.99 8-ary PSK CITY 22.6 1.05 JIlGIlWAY 21.7 2.77 (I ,3) 4-ary PSK CITY 21.1 2.27 HIGHWAY 20.2 3.29 8-ary PSK CITY 22.8 2.11 HIGHWAY 20.1 2.57 (I ,7) 4-ary PSK CITY 23.1 2.33 HIGHWAY 21.6 3.43 8-ary PSK CITY 22.7 1.84 HIGHWAY 22.0 1.51 (2,7) 4-ary PSK CITY 22.1 1.21 HIGHWAY 21.3 2.98 8-ary PSK CITY 22.7 0.86 HIGHWAY 21.9 1.36 . TABLE 9.1 MEASURED SNR's AND BER's over that required for coherent PSK aterror rates between 104 and 10-5. Interpreting table 9.J with the aforementioned in mind, table 9.1 seems incorrect; the bit error rates for 8·ary PSK arc, without exception, better than the corresponding bit error rates for 4-ary PSK, with approximately the same SNR! This highlight yet another important property of a mobile communication channels; the difference between fa~1 fnding and slow fading (chapter 2). (Fast fading as opposed toslow fading; more fadc.~ per bit interval.l Since 4-ary JlSK was transmitted nt 1200 baud and g·ary PSK at 1600 baud. CIlAP11!R NINE CONSTRAINED COOIlS ON MODlLl! VHF CUANNELS 143 the former was more subjccted to fast fading (longer bit interval). while the laner was more subjected to slow fading (shorter bit interval). Natumlly, this interesting trade·off between faster baud rotc and better DER could not be achieved indefinitely. A certain threshold point is thus anticipated where the DER will increase sharply as the baud rate is increased; jitter and noise have more pronounced effects at higher baud rates in bandlimited channels. IJ P{p.31) PCp,15) PCp,7) 0 0.978391 0.986730 0.991035 1 0.004299 0.003010 0.002571 2 0.003485 0.002404 0.002256 3 0.002819 0.001930 0.001899 4 0.002276 0.001568 0.001334 5 0.001833 0.001285 0.000672 6 0.001473 0.001043 0.000203 7 0.001181 0.000809 0.000026 8 0.000945 0.000573 - 9 0.000756 0.000354 - 10 0.000605 0.000182 - 11 0.000484 0.000075 - 12 0.000386 0.000023 - 13 0.000306 0.000005 - 14 0.000238 0.000000 - 15 0.000179 0.000000 - 16 0.000129 - - 17 0.000088 - - 18 0.000056 - - 19 0.000032 - - 20 0.000017 - - 21 0.000008 - - 22 0.000003 - - 23 0.000001 - - 24 0.000000 - - 25 0.000000 - - 26 0.000000 - - 27 0.000000 - - 28 0.000000 - - 29 6.1E-ll - - 30 3.9E-12 - - 31 1.2E-13 - - TAnLP. 9.2 PCp. v) FOR RAm R =1/2. W. k, C) = (0, 2. 1) CODE 4-ARY PSK IN CITY ENvIRONMENT CIIAPTF.R NINP. CONSTRAINF.D Coors ON MaDIll! VIIF CIIANNELS 144 To sum up: in a city environment the average SNR is higher (with a lower 8ER) than in a freeway environment, with marc acceptable SNR fluctuations: an g-ary PSK modulation scheme at 1600 baud would be recommended for usc on a mobile communication channel, irrespective of the modulation codeused. Before recommending an appropriate modulation code (or mobile VHF communication channels, let us first look at the measured probability that a block of v code bits contain Il error bits. As example, figure 9.8 and table 9.2 depict, respectively, the measured probability, P(Jl, v), versus the number of errors in v bits, 1', graphically and in tabulated form for a rate R = 1/2, (d, 1:, C) =(0, 2, 1) code, with 4-ary PSK in a city environment. Three block lengths are presented on the graph and in the table: v =7, 15 and 31 (which concurs with the codeword length of several Hamming and nClI codes). TIle quantative values of the probability P(/J, v), for the five modulation codes and the selected PN-scquence, for both modulation schemes in a city and highway environment, arc tabulated in Appendix D (or block lengths o( v = 7, 15 and 31. ny comparing these values with the block error probability of a PN-sequcnce (Appendix D), a modulation code can be more accuratelychosen. 1 " - __ ...•. _ .. ""'-'" ---' .._•._ .•• _.•..• _ .. 1.000E-09. 1.000E-10. 1.000E-11· 0.0 1 ~ p 1.000E- 03 • R 1.000E-04, o B 1.000E-OS A B 1.000E-06 L 1.000E- 07 . I 1.000E-08Ty 0.1 • 1.000E-12 . ----- 1 1_. --1_.,. __ 1__•. _1.._.__ 1__ o 6 10 15 20 25 30 36 flip.,t FIGURE 9.8 P{s.t, v) FOR RAm R = 1/2, (d, 1,Q = (0, 2, 1) CODE 4-ARY PSK IN CITY F.Nv1RONMF.NT As mcntioned earlier, the rate R = 112. Cli. k, C) = (0, I, 1) Manchester code is already in usc on mobile communication channels 15). [47] and the CCIR recommended (J6] the rate R CUAPTP.R NINE CONSTRAINED COOFS ON MODILE VHF CIIANNF.LS 145 =1/2. vi. k) =0.3) Miller code for use on mobile communication channels to achieve clock extraction and a bandwidth saving in an environment with an ever increasing spectrum shortage. Hence. this study set out to investigate the CCIR recommendation and to further investigate modulation codes for clock extraction, improved intersymbol interference properties and bandwidth saving. Two of the three properties investigated were fruitful; clock extraction can be gained because of regular transitions in the transmitted waveform (due to D bounded k parameter) and intersymbol Interference can be reduced by choosing a proper (I pnrarncter, the third property. however. cannot be achieved with modulation codes, since a fixed data rate result in a bandwidth increase of nlm > lover an uncodcd PN-scquence (chapter 8). Thus, when choosing a modulation code for a mobile VHF channel, these advantages and restrictions must be kept in mind. Since the signal constellation (modulation scheme employed on carrier) has lillie effect on the modulation code performance, the following discussion will only consider the 4-ary PSK entries in the tables rcferenccd. Each modulation code will be compared with an uncoded PN-sequcnce. using the BER's of table 9.1 and block error probabilities of the tables presented in Appendix D. The spectral efficiency of each modulation code, in comparison with the PN-sequcnce, will also be discussed. The spectral efficiency of a modulation code equal its rate R = mln. (Spectral efficiency refers to the number of bits that are transmltted in a given period of time, usually one second. over a radio channel with a defined bandwidth. For instance, a PN-scquence transmitted at 1200 baud with a 1200 Hz-bandwidth has a spectral efficiencyofone bit per second perhertz.) • The rate R =1/2, (P, k,C) = (0, I, 1) code versus the PN-scquence: The bit error rate for this modulation code in both the environments is the worst; the spectrum efficiency for the modulation code is 1/2 bJWHz as opposed to 1 bps/llz for the PN-sequence; the probability of no errors in blocks of v =7, 15 and 31 bits (the first entries in the tables in Appendix 0, tables 0.2, 0.7, 0.21 and 0.22) are lower. Thus, except clock extraction, not very much else is gained from this code; hence, there is hope for a better choice of modulation code over the presently used Manchester code. • 111e rate R = 1/2, (jl.k, C) =(0, 2, 1) code versus the PN-scquence: Considering table 9.1, the modulation code and PN-scquencc have similar BERs in a city and highway environment; the spectrum efficiency for the modulation code is 1/2 bps/llz. Although this may seem low. the bandpass results in chapter 8 showed that a higher data rate can be achieved with this CJlAPTP.R NINE CONSTRAINED CODES ON MaDlLE VHF CUANNELS 146 modulation code if a custom modem is designed to take advantage of its special spectrnl properties. P(O, v) (v = 7. 15 and 31) arc lower for the modulation scheme when the first entries in tables 0.1.0.6. 0.21 and 0.22 are considered. A major improvement of this code over the Manchester code, is the smaller bandwidth required (chapter 8). Whcn compared to the PN·scquence. clock extraction can be gained in almost thesame bandwidth constraint, • nle rate R = 1/2. W. k) = (t, 3) code versus the PN-scquencc: With this modulation code the influence of a larger d parameter was investigated. A slight improvement in the nER nnd basically the same P(O, v) (tables 0.3. 0.8, D.21 and D.22) were encountered. The spectral efficiency is 1/2 bps/liz. There is thus an inclination to a better code performance with a larger d parameter. • 111c rate R = 2/3, It/, k) =(l, 7) code versus the PN-scquencc: This modulation code had a similar performance to the Miller code previously described; a slight improvement in the BER and very much the same P(O, v) (tables D.4. 0.9, 0.21 and 0.22) were encountered, The spectral efficiency, however, was improved to 2/3 bps/llz. As mentioned in chapter 8, this code was chosen to verify the influence of a larger detection window over mobile radio channels. Although a larger detection window plays a significant role on magnetic and optical recording channels (chapter 4), it has no significant influence on mobile radio channels. • The ratc R =1/2, W, k)= (2, 7) code versus the PN-scquencc: This modulation code performed the best on mobile mdio channels. The HER and P(O, v) (tables 0.5, 0.10. 0.21 and 0.22) were better. The spectral efficiency. however, is 1/2 bps/llz. It is thus evident that the larger d parameter has an influence on a mobile radio channel. This can be attributed to the better resistance against intcrsymbol interfcrence brought about by the larger d parameter. However, a larger d parameter results in a lower spectral efficiency, since the code rate is lowered accordingly. A possible solution to this problem will be presented in chapter 10 where recommendations (or futuro research will bediseussed. With the advantages and disadvantages of modulation codes discussed in terms of an uncoded PN-scquence, it ispossible to recommend a modulation code for usc on mobile communication channels. CIlAYruR NINE CONSTRAINRD CODES ON MOBIl..E VIIF CIIANNP.LS 147 TIle (0,1:) codes did not pcrfonn vcry well on a mobile radio channel. The influence of the DC-free property also did not influence the codes to perform better since indirect modulation was used: the modulation code spectrum was frequency shifted by the modem to a higher frequency band, thus canceling the need for DC·freencss. When spectral efficiency is considered, the rate R =1/2, €II, 1:, C) =(0, 2, 1)code and the rate R =2/3, vi, k) =O. 7) code take the lead. Since the rnte R = 2/3, (tI, 1:) = O.7) code has better block error probability. with approximately the same bandwidth requirements, this code would be preferred over the DC·free code. The rate R =]/2, (tI, k) = (2. 7) code performed the best when error properties are considered, because of the larger tI parameter. With all this in mind it is evident that n better code can be recommended than the presently used Manchester code and CCIR proposed Miller code. Since clock extraction can be gained from the rate R = 1/2, id, k, C) = (0,2, 1) code and the rate R =2/3, ClI,I:) = (1,7) code. with good error characteristics, these codes would definitely be recommended for (uture use on mobile radio channels. If the proposed solution in chapter 10 is found to be valid, modulation codes with a larger d parameter can beused in future to improve intersymbol interference problems. 9.3) CHANNELMODELS -~...t.MIWl-"'- I.OE'02 I.OE·02 1.0E'O. '.OE·oa LENOTlt ! f I I t 0.2 Figure 9.9 shows a graph depicting the burst distribution, burst interval distribution. cluster distribution and error free run for the rate R =1/2, W,I:, C) = (0. 2, t) code in a city environment, with a 4-ary PSK modulation scheme. Appendix D contains similar graphs for the other five modulation codes in city and highway environments for both the modulation schemes. 1.2 FlOURF. 9.9 r~ROR DISTRmunoN FOR A RAm R =112. (P. k. C) =(0.2. 1) COOK 4-ARY PSK IN CITY EHVtRONMFNr CIIAPrnR NINE CONSTRAINED CODF.5 ON MODILE VIIF CHANNELS 148 111is measurements were conducted as shown in figure 9.10: the modulation codes together with the mobile VIIF channel were considered as a black box containing the channel. This representation of the channel is known as a superchannel. ERROR SEQUENCE FlOURE 9.10 MODEUNO OF SUPER CIIANNPL Although this study is not concerned with channel models, this measurements will enable future students to apply the work of Swarts [7], Tsai [38] and Fritchman [39] to find channel models for modulation codes on mobile communication channels. These results are also available on a floppy disk in the cover of this thesis. The filenames which contain these results have the following legend: the first and second letter respectively indicate the modulation scheme and environment, The next letters indicate the (d, k) or (d, k, C) code parameters. For instance, a file with the name 4J10_C2.TXT contains the results for the rate R = 1/2; (d, k,C) = (0, 1, 2) code, with a 4-ary PSK modulation scheme in a highway environment. 149 CHAPTER 10 CONCLUSIONS AND RECOMMENDATIONS This thesis contains the results of an investigation devoted to a theoretical and experimental study of communication systems, with contributions to the information theory and mobile communication disciplines. The theoretical results obtained in this thesis can be found in chapters five and six. Chapter five describes a method to map fixed-length coding rules on finite-state machines, realized with the OW algorithm. Although the algorithm can be applied with success to both binary and multilevel coding rules, the algorithm has the restriction that it can only be applied to fixed-length coding rules, such as table 4.4, and not to variable-length coding rules, such as table 4.5. The algorithm should thus in future be extended or amended to incorporate both fixed-length coding niles and variable-length coding niles, or 0 new algorithm specifically devoted to variable-length coding niles may have to be developed; this, however, may not be a trivial task! Although there is mom for improvement in the OW algorithm, it gives future research in this field a good starting point. In the literature there arc numerous coding rules that need to be converted to FSM representations. in order to compute spectra e.g., thus making this investigation and the DW algorithm a worthwhile contribution to the information theory literature. CIIAP'rnR TF.N CONCLUSION 150 Chapter 6 presented new results for (O.k) modulation codes. together with the 1'8 algorithm. which can be used in future when other (0. k) codes need to be developed. As mentioned. 8 timesaving with the TS algorithm for large" is also anticipated over methods presently used. making the 1'8 algorithm a meaningful contribution to the information theory literature. Although the rate R = 11/12. (ti. k) =(0.3) code developed with the 1'8 algodihm was not selected for experiments on the mobile communication channel. since it can be used on magnetic recording channels or even on optical recording channels. In future the error propagation properties etc. for this code can also be investigated. Chapter 8 was one of two chapters on the experimental results obtained in this study. Experimentally measured baseband spectra of fourteen modulation codes and the selected PN-scquence are presented on a linear and logarithmic scale. The measured spectra compared favorably with known theoretical spectra found in the literature. see e.g. Immink [3] and Zehnvi and Wolf [48]. to mention II few. However. seven modulation codes' spectra were measured that were previously unpublished. the rate R = 8/9. (d. k) = (0.3); the rate R = 11/12. (d, k) =(0,3); the rate R =1/2, (d. k) =0.2); the rate R =1/3. (d.k) =(3,7); the rate R =1/4, (tI, k) = (4. 7); the rate R= 1/4. (d. k) =(4,8); and the rate R =1/4, (ti. k) = (5.9). The two (tI, k) = (0. 3) codes with different code rates had, as anticipated. very similar spectra. see figures 8.9 to 8.12. with the rate R = 1]/12 code needing a smaller bandwidth. The measured spectra give the reader a feeling of the influence of the d, k and C parameters on the energy content at a specific frequency. These measurements also verified the expected influence of these parameters on the frequency characteristics of the code as described in chapter 2; although these parameters arc interrelated. the d parameter has a bearing on the high frequency components of the modulation code spectra. the k parameter determine the low frequency components of the modulation code spectra. and the C parameter determine the accumulated charge of the waveform. Spectra of modulation codes after FFSK and PSK modulation were also investigated. FFSK modulation is known for its symmetric spectra (resulting in a smaller bandwidth than FSK) which is verified in figures 8.35 to 8.40. It is evident that the DC·free property. present in some modulation codes. is not a desired property when frequency modulated. since most of the signal energy is needed at the center of the passband, When considering figure 8.35. the FFSK spectrum of the PN-sequence. it is clear that most of the energy is concentrated around the carrier frequency. a desired property. When the FFSK spcctrn of the rate R =1/2. W. k, C') = (0. I, 1). Manchester code and the rate R = 1/2. (t/, k, C') =(0.2. n. IIcdeman 11·2 code are considered, figures 8.36 and 8.37. it is evident that most of the energy is concentrated 8t frequencies removed from the cnrrier frequency. Considering the rnte R = 1/2, W. k) = O.3) CIIAPmR TF.N CONCLUSION Millercode. the rate R =2/3. (d. k) = O. 7) Jackoby-Kost code and the rate R = 1/2. fli. k) = (2. 7) IBM code, figures 8.38 to 8.40. it is clear that most of the energy of the signal are concentrated around the carrier frequcncies. The Jackoby-Kost code has 0 little less energy concentrated round carrier frequencics than the other two codes. Against this backdrop. it is evident that a certain class of modulation codes would be preferred over an uncoded PN·scquence when energy need to be concentrated round the carrier frequencies. However. this is accomplished at theexpense ofa lower dato rote. It is interesting to note that the modulation codesdid not influence the PSK spectra as much as it influenced the FFSK spectra. It was impossible to distinguish betwecn the various modulation codes and the PN·sequence after PSK modulation. 111is can be ascribed to the PSK spectra (DPSK. 4·ary PSK and 8·ary PSK) that do not have any sharp peaks in the spectrum (no large amounts of energy concentrated at certain frequencies). figures 8.37 and 8.39. The conclusion can thus be drawn. when comparing FFSK and PSK spectra. that PSK modulation would be preferred over FFSK as modulation scheme when using modulation codes. PSK modulation gives us more freedom in the choice of a modulation code. since the energy of the modulation code is spread out over the whole PSK spectrum, which is not true in the FFSK case, The bandpass experiment results presented can be used as reference to recommend a modulation code through a bandlimited channel. Although this list is by no means exhaustive. a proper understanding of the influence of the d. k and C parameters through bandpass channels can be gained. (By considering the bandwidth ofa given channel the best choice of d. k and Cparameters can be determined with table 8.2 at hand.) 111e bandpass filter settings (LPF/IIPF) compare best with 0 mobile communication channel and can he used in future to predict and/or simulate the actual mobile communication channel in laboratory conditions. In this way the actual mobile channel. or for that mauer any other channel. can be classified and verified in a more controlled manner in the laboratory. allowing more reliable conclusions to be drawn regarding the recommended choice of specific modulation codes best suited for the application. These results is thus only a preliminary study and can berepeated in order to achieve more extended results, CIlAJYrnR TF.N CONCLUSION Chapter 9 contains results obtained by transmitting modulation codes over mobile VHF channels, Except for n first-hand acqualntance with the mobile communicntion channel and environment. these experiments also made it possible to recommend n certain class of modulation codes and modulation schemes to improve reliable data trnnsmission over these channels, The error distribution of the five modulation codes were measured to verify the experimentnl results when n proven model of a digital mobile communication channel is available. These results are presented in appendix D. When clock extraction is needed over a mobile communication channel, a modulation code has to be considered. The choice of modulation scheme depend, to a great extend, on the available bandwidth, thedata rate to be achieved, the modulation scheme used and the allowable nER. Table 9.1 and the bandpass results obtained in chapter 8 can be of great assistance when n modulation code is needed. The results of chapter 8 can be a guide to choose a modulation code for a certain bandwidth. Since a high code rate (R) result in n theoretical smaller bandwidth (when compared to n code with a low code ratel, a code with a high rate (R = mIn) would be preferred. As previously discussed, PSK modulation would be used with a modulation code since the modulation code spectra is spread out over the whole PSK spectrum. When a low DER is needed, a code such as the rate R = 1/2, W, k) = (2, 7) IBM code would be considered, apparently because of the larger d parameter which reduced intersymbol interference. Although the PN-scquence resulted in a bit synchronization loss during fading, this phenomenon is not reflected in the results of table 9.1; the error recording equipment did not count biterrors duringsynchronization loss. As mentioned, the influence of a larger detection window and higher density ratio was also investigated over a mobile radio channel. A larger detection window had no apparent influence on a mobile communication channel, whilc a higher density ratio, larger d parameter, resulted in a lower nER. The global conclusion thnt can he drown from this study would he that modulation codes are necessary when clock extraction isneeded, hut can be implcmented more efficiently on mobile communication channels. To implcmcnt a modulation code on these channels, depend to a great extend on the type of data which need 10 be transmiued. When data is transmitted, like a PN-scqucnce, where there would not be nny consecutive runs of zeros or ones longer than 20 CIIAPTER TEN CONll.USJON to 30 bits. modulation codes would not be considered. However. when. (or instance, computer data is transmltted, where 0 nan of many consecutive zeros or ones ore transmitted, modulation codes would be essential. Even then modulation codes can be implemented more efficiently. which will be discussed shortly. However, this study showed that a better modulation code than the presently used Manchester code can be recommended. 111e CCIR recommended the Miller code (or a more efficient usc of bandwidth. which proved to be unsuccessful; the Miller code need twice the bandwidth of uncoded data and the some bandwidth as the Manchester code. With nil the previously mentioned in mind. the five modulation codes can be rank, in order of merit. as follows: I) Rate R= 1/2. (d. k, C) = (0,2. 1); 2) Rate R= 2/3. (d. k) = 0.7); 3) Rate R=J/2. (d. k) =(2. 7); 4) Rate R= 1/2. (d. k) = 0,3); 5) Rate R= 1/2. (d. k, C) = (0, 1. 1). A few meaningful suggestions can be made concerning modulation codes on mobile radio channels. TIle first would be to use direct modulation of the VHF radio carrier; since digital radio will be the next generation of mobile communication systems, the d and k parameters can be investigated under these conditions. For n more efficient use of modulation codes. the modulation codes need to be integrated "+0110 00 10 a) 10 b) c) FlOURP. 10.1 a) UNCOOlID 4-ARY PSK b) COI>HJ> 4-ARY PSK c) OmMAL COOl~) "'ARV PSK CIIAP'rnR TF.N CONa.USION with the modulation scheme used. For example. consider a 4-ary PSK modem with signal constellation as shown in figure 10.1a. By choosing a rate R = 1/2. vi. k) = (0,2) modulation scheme which consists of two codcwords 01 and 10. the signal constellation will look like figure lO.1b when transmitted through the -t-ary PSK modem. By designing a dedicated modem the two points can be placed at optimal position as indicated in figure lO.lc. We now have a scheme with a noise immunity similar to 2-ary PSK. clock extraction and the same bandwidth constraint as uncodcd data; in short a desired modulating system! A larger d parameter, in the same bandwidth constraint. can also be incorporated with a scheme like this. This is only a trivial example. but the real power in n scheme like this will become more apparent when the number of points are not equal to t. TIle usc of vi. k) modulation codes on mobile radio channels can also be integrated with compatible error correction to improve the DER, as well as bandwidth and lSI limiting strategies to enable high data rates on narrowband channels. The latter cnn be achieved by limiting the intersymhol interference variation (ISV) in the same way the digital sum variance (DSV) is limited to construct DC-free codes. Apart from the above. codes can also be designed to simultaneously achieve maximum Hamming distance (or improved error performance. The usc of partiaI response techniques can also be investigated to achieve better bandwidth efficiencies, with the additional possibility to incorporate error detection/correction with Viterbi decoding to improve the DER. 151 APPENDIXA HARDWARE DESCRIPTION Developments in the field of electronics have constituted one of the great success stories of this century. Beginning with crude sparkgap transmitters and "eat's-whisker" detectors at the tum of the century, we have passed through a vacuum-tube em of considerablesophistication to a solid-state era in which the flood of stunning advances shows no signs of abating. Calculators, computers and even talking machines with vocabularies of several hundred words are routinely being manufactured on single chips of silicon as part of the technology of large scale integration (LSI) and current developments in ~'Cry large scale integration (VLSI) promise even more remarkable devices. Perhaps as noteworthy is the pleasant trend toward increased performance per rand. TIle cost of nn electronic microcircuit routinely decreases to a fraction of its initial cost as the manufacturing process is perfected. In fact, it is often the case that the panel controls and cabinet hardware of an instrument cost more than theactual electronics inside. Since Claude Shannon systematized and adapted George Boote's theoretical work in 1938. there has been unprecedented growth in the application of digital concepts. Other fields that emerged in the late 1930's and early 40's have "peaked" and leveled or declined. while the application of digital concepts is stilt growing exponentiatty. Each day digital concepts AJ»W.NOIXA IIARDWARE DISCRJP110N 152 are being applied to problems that could only be solved by analog methods several years ago. Fast, reliable nnd modestly priced analog to digital (NO) and digital to analog (D/A) converters are presently available, facilitating the application of digital concepts for solving complex analog problems using microprocessors and other programmable digital systems. In short, the rapid expansion of discrete practices has served notice to the academic community to restructure curricula to treat discrete mathematics and other discrete sciences. Certainly tho "microprocessor" revolution has penetrnted all fields ofendeavor and will continue to do so for many years, Since digital techniques arc cheaper, easier and more convenient to usc in a design than most other techniques, the designs undertaken in this study will to a great extend implement digital techniques, including digital signal processors (DSP), mlcrocontrollers, programmable logical devices (PLD's), random access memory (RAM), read only memory (ROM) and a handful of the common garden variety transistor-transistor logic (11'L) gates, counters, shift-registers etc. Although sheer "number crunching" is an important application of digital electronics, the real power of digital techniques is seen when digital methods are applied to analog (or "linear") signals and processing. Some elementary analog techniques in the form of low-pass, high-pass, and band-pass filters were also implemented, As is evident in the walk of life, hybrids do exist. Phase-locked loops (PLL) is one of the "hybrids" in the electronics world, where analog and digital techniques are combined, giving us the best of two worlds. A thorough discussion concerning the lock runge, capture transient anel low-pass filter design for a given set of parameters will be presented. This section may well be used as a tutorial guide for future students on the design of PLL's. With the design of digital systems a few obvious questions arise; when must a DSP processor be used instead of an "ordinary" microprocessor VIP), which type of RAM must beused, static or dynamic, must complimentary metal oxide semiconductor (CMOS) technology with their low power consumption be used instead of the faster TI'L technology, must the black art of PLD's be conquered? Answers will be given in a corroborate discussion where tradeoffs betweencost, efficiency and simplicity wage the overtone. 111is chapter will describe the three designs mentioned in chapter 7 on a circuit diagram level, together with a conflnnative discussion why certain components were used, AJ»I-RNDiX A A. t) PROGRAMMABLE LOGIC DEVICES IIARDWARE DlSCRlmON 153 As system design methodology continues to evolve, there becomes nn increasing need to not only simplify the design process, but to reduce the overall system size and cost, and increase system reliability. It was this mlndset that led to the development of the first programmable logic devices. In fact, the evolution of programmable logic has changed the way systems are designed, since it offers the designer a single tool that solves nil his needs. Programmable logic is ideal for simplifying the design process because the designer can implement the exact logic functions wherever and whenever required. It is also ideal for reducing system size and cost by offering significantly higher functional density than its small- and medium-scale-integration (SSI/MSt) predecessors. Finally, system reI inbitity is significantly improved because of simplified designs and lower parts count. The programmable array logic (PAL) device is an extension of the fusible link technology used in bipolar programmable read onb' memory's (PROM's). 111e fusible link PROM first gave the digital systems designer the power to "write on silicon". In a few seconds he was able to transform a blank PROM from a general purpose device into one containing a custom algorithm, microprogram or Boolean transfer function. This opened up new horizons for the use of PROM's in computer control stores, data storage tables and many other applications. The PAL device extends this programmable flexibility by utilizing proven fusible link technology to implement logic functions. By using PAL circuits the designer can quickly and effectively implement custom logic varying in complexity from random gates to complex arithmetic functions. Although PAL devices are superior to PROM's and even erasable PROM's (EPROM) they have disadvantages; it offers high speed, but is saddled with high power dissipation becauseof its bipolar fuse-link tcchnology. This not only significantly increases system power supply and cooling requirements, but also limits the ability of high functional density. Another shortcoming of this technology is the one-time-programmable fuses: no reuse in the event of mistakes during prototyping or errors on the production floor are possible, and any misprogrammed devices must be dlscanlcd. Ultra Violct CMOS (UVCMOS) addresses many of the shoncomings of the bipolar approach. but introduccs many shortcomings of its own. This tcchnology requires much lower power and, while it has the capability to erase, this comes at expense of slower speeds ApPF.NDlX A IIARDWARE DlSCRJmON 154 and cumbersome erase procedures: exposing the device to ultraviolet light for at least 20 minutes. Additionally. the devices must be housed in expensive windowed packages to allow users to erase them. Of the three major technology approaches available, elcctrlcal erasable CMOS (E2CMOS). UVCMOS and bipolar. the technology of choice is clearly E2CMOS. for many reasons. including: testability. quality, highspeed, low power. and instant erasure for prototyping and error recovery. Generic Array Logic (GAL) devices utili7.c this technology. GAL devices are ideal programmable logic devices because. as the nome implies. thcy are architecturally generic, These devices employ the Output Logic Macrocell (OLMC) approach [40]. which allows users to definc the architecture and functionality of each output. TIle key benefit to the user is the freedom from being tied to any specific functionality. Comparing the GAL device with fixed-architecture programmable logic devices is much like comparing these same fixed PLDts with SSI/MSI. '111c GAL family is the next generation in simplified system design. Thc user needs not bother searching for the architecture that best suits a particular design. Instead. the GAL family's generic nrchltecture lets him configure as he goes. Each OLMC can be individually set to active high or active low. with either combinational (asynchronous) or registered (synchronous) configurations. A common output enable can be connected to all outputs. or separate inputs or product terms can be used to provide individual output enable controls. The OLMC provides the designer with maximal output flexibility in matching signal requirements, thus providing more functions than possible with existing 20-pin PAL devices. It should be noted that actual implementatlon is accomplished by development software/hardware and is completely transparent to the user. In the designs presented. GAL devices were exclusively applied where PLO's were thought to be necessary. because. as ilhistrated in figure A.t. the GAL is a great pcrformerll A.I.l) DESIGN IMPLEMENTATION OF GAL'S TIlC tools required for designing with GAL productscan be separated into twocategories: • Programmable logic development software: • Device programmers. ApPF.NDlX A IIARDWARR DISCRJP110N 155 A G ....eat Pet-former! FlOURE A.I TilE GAL, A GREAT PERFORMER! Universal programming hardware allows the progrnmming of B variety of devices without the aid of custom fixtures or manufacture's adapters. Since the GAL programming algorithm requires no abnormal voltages or timing, as some one-time programmable technologies do, most nil hardware manufacturers support GAL devices onexisting models. Software packages, such as ABEL from Data I/O, CUPL from Assisted Technology and Logic Lab from Programmable Logic Technologies, offer generic development support for all programmable logic devices, and, with periodic updates the user will be kept up on all programmable logic device developments from nil manufacturers. '111e software offer a PC-based PLD programming langunge, suitable for programming various PLD devices. Once the software knows which device will be used, fields are provided fot optional information, such ns design description etc. The device pinout and pin labels need to be specified. Entry of the logic functions is next. Traditionally, this entry is in the fonn of Boolean equations. Current revisions of development software allow truth-table, state-machine and schcmauc-emry formats, as well. 111e development software and device progrnmmer used was the Logic Lob package, intended for programming most PLOts on the market today. An example of the afore AplI(!NOIX A HARDWARE DlSCRlmON 156 mentioned procedure for programming the devicescan be found at the end of this appendix. A.2) Wlllcn PROCESSOR? Amid the plethora of alternative microprocessors currently available, it is sometimes difficult to come to a rational decision on the best choice of processors for a given task. There are two mutually opposed common misnpprehensions on this subject; the first is that certain CPU's are generally "beuer" than others. '11e second, that there is lillie to choose between devices and nny CPU will perform any task equally well given the right software. The truth lies somewhere between these two poles. The choice of processor for a given task depends primarily on the application designer's criteria in a givcn design situation. Alternative factors which could guide or dictate choice are: • System chip count in a low cost commercial application; • System throughput as an absolute parameter; • System efficiency as an absolute parameter; • System cost effectively represented as throughput per rand cost: • System adaptability for non-standard implementations; • System reliability or the capacity of the system for self-maintenance: • Designer familiarity with the system. The list could goon indefinitely. but this sample shows just how diverse are the factors which seem significant in varying designsituations. It is important to be clear on the distinction between microcomputers. microprocessors and microcontrollers. A microprocessor is the CPU part of a computer without the memory, I/O and peripherals needed for a complete system. All the other chips in a microcomputer. such as the IBM PC, arc there to add features not within the microprocessor itself. When a microprocessor is combined with external I/O and memory. the combination is called a microcomputer. A device having the I/O and memory peripheral functions on the same substrate all the CPU to make a complete microcomputer is called a Single-Chip Microcomputer (SCM). Generally. SCM's are designed for very small computer based devices that do not require all the (unctions of a full computer system. In cost sensitive control applicatiOl1J. even the ApW.NDlX A IIARDWARE DISCRIPnON 157 few chips needed to support a CPU like a 8088 or Z80 may take too much space and power; instead, designers often employ a SCM to handle the control-specific activities. Where single-chip micros arc designed or used in industrial control systems, they are often called microcontrollers. Basically, there is no difference ,between single-chip microcomputers and microcontrollers. Sometimes the term "embedded controllers" is used instead of microcontroller; Intel, for instance, has adopted the tenn for its controller chips. However, an embedded controller, according to one definition [41], is a computer system hidden within some other device. By another definition [421, it's a computer whose programs cannot be altered by the user. Generally, the term embedded controller suggests a highly compact, although not very powerful, dedicated processor; for example, an SCM controlling a microwave oven. Intel introduced its first microcontroller architecture, the 8048, in 1976. It was designed for general-purpose 8 bit control, with on-board ROM and RAM, plus 27 I/O lines. Four years later came the 8051, which was upto ten times faster than the 8048 and had a IllS instruction cycle at 12Mllz. Intel and other companies sell variations of the 8051 family enhanced with more internal memory, more VO, lower power and so forth. All members of the 8051 family have the same core instruction set, but some have one or two additional instructions for features unique to the particular chip. The 8751 is an EPROM version of the 8051 whose on-chip program memory can be electrically programmed and can be erased byexposure to UV light. The mobile decoder used a 8751 EPROM as its "brain", while the encoder used yet another version of the famous 8051, the DSSOOO. The DSSOOO offers "softness" in all aspects of its application. This is accomplished through the comprehensive use of nonvolatile technology to preserve all infonnation in the absence of the system power. Initial loading of the application software into the DS5000 is possible from either a parallel or serial Interface toa host system. Serial loading uses the on-chip serial I/O port to accept incoming data from a host computer with a RS232 port, such as 0 PC-bnscd development system. 111e device program can thus be rcprogmmmed and altered instanteneousty, 111e reason why only the encoder used the DSsOOO is of an economical nature. All development for both the encoder and decoder was done on the more expensive DS5000, for apparent reasons, and thcn transferred to the 8751 for the decoder. AltmNDlxA A.2.1) DIGITAL SIGNAL PROCESSING IIARDW ARe DISCRJPnON 158 Application speeiflc microcomputers and microprocessors, known today as Dlglta! Signal Processots possess two important characteristics which distinguish them from ordinary microprocessors. Firstly. they can execute almost their entire Instructlon set in one cycle. Secondly, they arc designed to execute a complete Mulliply anti Accumuillfe (MAC) instruction also in one clock cycle (Dy comparison, the previously mentioned 8051 execute a multiply instruction in 48 clock cycles). Numerical algorithms by which DSP applications arc normallycharacterized are very MAC intensive. The all important deciding criterion in DSP is real-time-processing. With the continued improvement in dedicated DSP solutions in real speed, architecture and application ~..pecific instruction sets, new market segments arc opening and oldones arc expanding. The majority of electronic applications are concerned with the manipulation of signals: filtering of unwanted components from an input signal, extraction of information from a signal, generating waveforms, modifying the amplitude characteristics of an output signal in order to improve the information content. etc. In the past all this manipulation was performed using analog circuits and techniques. Analog circuits require a special design for almost every application and are therefore not particularly well suited to VLSI applications. Especially when the problem is considered from the aspect of using common analog VLSI function elements. All analog designs are dependent on sensitive components, ie, resistor and capacitor values are never completely accurate. but more importantly, their values change as a function of time, voltage and temperature. Although DSP's main application are quantization of an analog signal into digital values and performing a precomposcd algorithm stored in memory on the digltized data, the DSP npplication for the purpose of this study was one where real-time processing was needed: a finite-stnte machine generator was to he employed, generating coded data at rates varying (rom n few baud to a possible 1M baud, depending. or course, on the complexity of the coder. Since the DSP finite-stale machine can operate up to an estimated IM baud, a piece of equipment was thus developed that could be used for at least a few generations of post-graduate studies in real-time coded data. ApPF.NDlX A A.3) RANDOM ACCESS STORAGE IIARDWARE DISCRIPJ10N 159 The storage of infonnntion in computer systems is accomplished by utilizing collections of individual storage clements, each of which is capable of maintaining a single bit. Thus, for 11 device to be useful as n memory element it must have two stable states, a reliable mechanism for setting the device to one state or the other, and a mechanism for interrogating the state. Memories have been built of a variety of devices that match this characteristic, including relays, individual vacuum tubes, delay lines (which form a type of serial memory) and obviously semiconductors. In each case, information in the fonn of bits was entered into the memory, and then at some Inter time extracted for usc by the system. The technique of storing information by the magnetic orientation of a ferrous material was once used for the central memory ofa computer [43J. Allhough this is not the case any more, this technique is now used more prevalently for other types of storage in a computer. The magnetic orientation of a region of ferrous material on a surface is used to store a bit, and this surface is most often on a rotating magnetic disk, oron a magnetic tape, fThe various codes investigated in this study have implementations on this storage medium, see chapter 8.) A.3.l) STATIC VS DYNAMIC Static memories generally have a smaller number of bits per package and a higher power consumption than dynamic memories. The static mechanism of Figure A.2 requires six transistors in every cell; other static memory configurations utilize fewer active elements. One of the tasks of memory designers is to reduce the number of components needed in an individual storage cell, since fewer clements means that each individual cell can be smaller and require less power, which in tum leads to larger memories. TIle memories with the largest capacities usc not a static mechanism, but rather a dynamic mechanism, as shown in Figure A.l Here the value ofthe bit is not determined by the ()Jlott FlOURP. A.2 SfA"C MHMORY ApW.NDIX A _rA\~ _L 00/\11 Co II FIGURE AJ DYNAMIC MF.MORY IIARDWARH DISCRJP110N 160 current flowing through one of the two different paths. but rather the bit value isdetermined hy the amount of charge stored on a capacitor. The capacitor is created with semiconductor technology and is extremely small. TIle sensing of the charge is also vcry difficult and handled by circuitry on the device itself. 111e infonnation is placed on the capacitor by opening an electronic gate and establishing the proper charge level. Then, the gate is closed and the charge maintained on the node by the electronically isolating it from surrounding influences. However, the time which the charge can be reliably maintained in this manner is not very long, and so it must be re-established periodically. This is done by a "refresh" cycle, which detects the appropriate bit values and refreshes the bits. The length of time between refresh cycles varies from memory tomemory, but a common value is 8 ms; each row must be visited at least once every 8 ms, For this reason dynamic memory controllers are designed to periodically access rows to ensure that the data is maintained in the memory cells. With the afore mentioned as backdrop for selecting suitable memory for the nsp board. there was decided on static memory, since the memory requirements was 4k x 16 bit. Although dynamic memory is cheaper per I mega bit, the overhead is far to expensive when small quantities arc needed: the refresh controller would be more expensive than the actual memory usedI Also. it would complicate the design considerably. AA) Tun TRI-STATE CONeEM' As mentioned in chapter 7. there arc tri-state buffers between the PC. TMS and static memory on the DSP finite-state mnchine card, These arc needed to prevent nny clashes on the bus of either processor, The concept of tri·state buffering will now be discussed. Figure A.4 shows the prevalent mechanism used to accomplish a tn-state action. This is AllPf1.NDIX A JlARDWARE DISCRIPnON 161 so called because the output can assume one of three states. Two of the states are the "normal" states of a TTL gate: low and high. The output will be low whcn the logic of the function creates a situation in which transistor lI all is turned "on", and trnnsistor "b" is turned "off"; the output will be high when transistor 11011 is turned 1I0 ff ll and tmnslstor "b" is turned "on". The third state occurs when the logic of thc function creates a situntion where both transistors "a" and "b" arc turned off. In this case. the output is electrically disconnected from the system, since the paths through transistor lin" and through trnnsistor "b" present an extremely high impedance. This third. high impedance state is created by an enable (or disable) input to the function. Itl r----.., I Lo!)!c of function : "':I I ~ ..J FlOURHA.4 11lH TRI-SfATE CONcm Output 01 tri-sht. ~ylc~ / TIle TTL 74LS245. 8 bit tri-state buffer was used in the DSP board design. A.5) Tns PHASE LocKED Loop TIle phase-locked loop is a unique and versatile feedback system that provides frequency selectivetuning and filtering without the need for coils or inductors. It consists of three basic functional blocks; phase comparator. low-pass filter and vouage-controlled oscillator (VeO). interconnected as shown in figure A.5. With no input signal applied to the system. the error voltage. Vd' is equal to zero. 111e VCO operates at a set "free-running" _p"t 1~1" p.." vco FlOURF. AS Rl.ocK DIAGRAM OF ru, ApW.NDlxA IIARDWAim DISCRII'I1ON 162 frequency. fo' If an input signal is applied to the system, the phase comparator compares the phase and frequency of the input signal with the veo frequency and generates an error voltage. Ve(t), that is related to the phase and frequency difference between the two signals. This error voltage is then filtered and applied to the control terminal of the Yeo. If the input signal frequency is sufficiently close to f o ' the feedback causes the veo to synchronize or "lock" with the incoming signal. Once in lock. the veo frequency is identical to the input signal. except for a finite phase difference. Two key parameters of a phase-locked loop system is its "lock" and "capture" ranges, These can be defined as follows: tocx RANGF.: 11lC band of frequencies in the vicinity of foover which the PLL can maintain lock with an input signal. It is also known as the "tracking" or"holding" range, Lock range increases as the overall loop gain of the PLL is increased. CAPTURE RANGE: TIIC band of frequencies in the vicinity of fo where the PLL can establish oracquire lock with an input signal. It is also known as the "acquisition" range. The capture range is always smaller or equal to the lock range. It is related to the low-pass filter bandwidth and decreases as the low-pass filter time constant increase. TIlC PLL responds only to those input signals sufficiently close to the veo frequency. fo' to fall within the "lock" or "capture" range of the system. Its performance characteristics. therefore, offer a high degree of frequency selectivity. with the selectivity characteristics centered about fo' A.S.I)TnsPnAsE-LocKED Loop ASFRr~Ur~CY MULTIPLIER It is more than often in telecommunication circuits necessary to multiply a given operating clock with a certain integer. Genemting n fixed multiple of an input frequency is one of the most common applications of PLL's [~1J. 11lis is done in frequency synthesizers. where an integer multiple n of a stable low-frequency reference signal is generated as an output; n is settable digitally. giving a flexible signal source that can be controlled by computer. In more mundane applications. a PLL might be used to generate a clock frequency locked to some reference frequency already available. An example of this would be the generation of the rate R = 2/3. flJ. k) = (1. 7) code, discussed elsewhere in this thesis. To maintain ApPENDIX A HARDWARE DISCRIPnON 163 synchronization and no phase error with the input clock, the input frequency (1200 liz, say) must be multiplied by two (2400 liz) and divided by 3 (800 liz), in order to achieve COrTeCt encoding and decoding. Figure A,6 illustrates the standard PLL scheme, with a divide-by-a counter added between the veo output and the phase detector. In this diagram thc units of gain for each function in the loop is indicated as this will be important in stability calculations. Note particularly that the phase detector converts phase to voltage and thot the veo converts voltage to the time derivative ofphase, frequency. This has the important consequence that the veo is actually an integrator; a fixed input voltage error produces a linearly rising phase error at the VCO output. TIle low-pass filter ph". V, ~- V,,'elretl)' -- ~ vco ~~, ~---. K...."1"" 1t..1,,"\I,.. ' ..nl(~._I til . K~ lv.. III:.." ..",1 1(, (volll'oolll I( .,co (,,,I,,,,'/~ ..... volll ,.... l~""l FIGURE A6 FllEQUENCY MULTIPUER BLOCK DIAGRAM and the divide-by-a counter both have unitlcss gain. Returning to the rate R =mln = 2/3, vi, k) = 0, 7) code, a circuit had to be developed to generate a clock at two-thirds the rate of the operating frequency, and still be in phose, to ensure accurate coding of the data. The complete coder circuit diagram is presented later in this chapter. The infamous 4046 CMOS PLL was used, since both the phase detector and VCO are incorporated in one chip. The edge-triggered type of phase detector is used in this circuit (the .4046 actually contains both kinds 145]). Implcmenting a flLl .., the fim step would be to set the veo's lock range and capture range. TIlC VCO allows us to set the minimum and maximum frequencies corresponding to control voltages ofzero and VOD' respectively, by choosing RI, R2 and C. according to the design graphs in the dala sheets (45). (mu is controlled by R1-C. and f min is determined by C1 and the series combination R.-R2• It ApW.NDlxA IIARDWARB DlSCRlPnON 164 should be noted that, by suitable choice of R. and R2 values, the restricted-range yeO can be mode to "span" any range from 1:1 to ncar-infinity. Since the operating frequency ranged between 1200 liz and 4800 liz (standard modem rates) there was decided on f . = 100 and ( = 10 kllz, just to be on the safe side. The nun max component values (or these frequencies is shown in figure A.7. Ilaving rigged up the veo range, the remaining task is the low-pass filter design. This port is crucial. Since a first-order loop do not have n narrow bandwidth and good tracking capabilities, a second-order loop must be implemented. The trick to a stable second-order ..--__~INPUT Cl.K )( _In CLK/n INPUT elK CLK/m C2 FIOURE A.7 PLL MULTIPUF.R phase-locked loop is shown in the Bode plots of loop gain in Figure A.8. TIle yeO acts as an integrator, with 11/ response and 90° lagging phase shift. In order to have a respectable phase margin, the low-pass filter has an additional resistor in series with the capacitor to stop the rolloff at some frequency. TIle combination of these two responses produces the loop gain shown. As long as the loop gain rolls of( at 6dll/octave in the neighborhood of unity loop gain, the loop will be stable. The "lend-lag" low-pass filter docs the trick, if the properties is chosen correctly. Begin hy writing down the loop gain, as in table A.l, consldcring each component (refer to Figure A.6). Take special care to keep the units consistent. 11,e only gain term still to be decided is KF' It is done by writing down the overall loop gllin, remembering that the veo is an integrntor: APmNDlxA CD U , , , --- ' III U ~ I IU0 BEGIN >A • INITIALIZING MEMORY ADDRESSES WITH CODE INFORMATION. PSTATE DATA >0 PCODEO DATA >0 PCODEI DATA >1 AORG >100 • PROGRAM START. nEGIN DINT LACK PSTATE TnLR DSTATE LACK PCODEO TBLR DCODEO LACK PCODEt TnLR DCODm E1NT GCODE IN DDTA.a ZALS DSTAm XOR DCODEO nz STATEO nNZ STATEt STATEO ZALS DOTA AIJIJ(!NDlX n PROGRAMS FOR DSP FSM AND PC DECODER 175 XOR DCODEO nz TRANO nNZ SfAYO TRANO OUT DCODEO,t OUT DCODEO,t LACK PCODEt TfiLR DSTATE n GCODE STAYO OUT DCODEO,t OUT DCODEl,t n GCODE STATEl ZALS DDTA XOR DCODEO nz SfAYl DNZ TRANt STAY) OUT DCODEl,t OUT DCODEO,t n GCODE TRANt OUT DCODEO,l OUT DCODEl,O LACK PCODEO TBLR DSTATE n GCODE END • TMS ASSEMBLER PROGRAM END • ApW.NDlX n PROGRAMS FOR DSP FSM AND PC DECODER 176 /*••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••t /* Program writtcn in TurboC to decode D ., /* rate R=1/2, ClI, k) = (I, 3) code ., /*••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••, #includc #includc #inclmlc mninO int cbitt =0, cbit2 =0, ddtn =0; int z=0, x; clrscrf): olltportb( Ox30f, 0:<89 ); 1* initialize 8255 (J2) ., outportbl Ox30b, Ox9b ); 1* initialize 8255 (3) ., outportb( Ox313, Ox16 ); 1* initialize 8254 ., outportb( Ox310, Ox02); 1* devidc external elk by 2.' outportb( Ox3Oc, Ox01 ); 1* port A of 8255 ., puts( "Decoding MILLER code...." ); disablef): 1* disable intCITUpts.' whilc( z = 0) ( ir( (x =inportb( 0:<3Oc ))= 1 ) ( outporth( 0:<3Od, ddta ): 1* decoded dala bit 01 port n of J2 ., cbitl = inportb( 0,,308); ,. first coded bit It port A of J3 ., outportbl Ox3Oc, Ox02); /. initialize (or next elk ., ) ir( (inporth( 0:<3Oc )) = 2 ) ( APIIfl.NDIX n I~OORAMS FOR DSP FSM AND PCDp.coDF.R In cbit2 = lnportbf Ox308); ~ second coded bit at port A of JJ ., ddta = cbit1 • cbit2; ,. decode received bits ., outportbt OxJOc. OxOl ); ~ initialize (or next elk ., ) ft' End o(decoding program ., 178 APPENDIXC PROGRAMS FOR MOBILEEXPERIMENTS Again, this appendix contains two sample program listings: realizing a rate R =1/2. W. k) = 0,3) code for the mobilc flnhe-state machine encoder and the 8751 based decoder. both written in PLM/51. Other programs written in a similar fashion nrc presented on n floppy disk at the back of this thesis, with filenames having the following legend: the first three letters indicate if the program is used for encoding (ENe) or decoding (DEC). TIle next letters indicate the W. k) or (11• 7) 0 0.976544 0.98-1694 0.989423 I 0.003891 0.003130 0.002816 2 0.003322 0.002626 0.002537 3 0.0021BO 0.002192 0.002313 4 0.002403 0.00182·1 0.001748 5 0.002033 0.001523 O.OOOR83 6 0.001714 0.00\27·1 0.0002·18 7 0.001438 0.001039 0.000028 8 0.001200 0.000781 ·9 0.0()()995 0.lIOll505 · 10 0.000820 U,lIOll2M - II 0.000670 O.OOUI06 - 12 0.000543 0.1)011031 · 13 0.000436 0.00000(1 - 14 0.000345 O,O()OOOO · 15 0.000267 0.000000 · 16 0.000199 · · 17 0.000140 · - 18 0.000092 · · 19 0.000055 · - 20 0.000029 · - 21 0.000014 · - 22 0.000005 · · 23 0.000002 · · 24 0.000000 . · 25 0.000000 · · 26 0.000000 · - 27 0.00000o · - 28 0.00000o · - 29 5.4E·JJ · -30 3.0E·12 · - 31 7.9E-14 · - TABLE 0.8 PRODAnIUTIES P{p. v): (d.k) =O. 3);4-ARY PSK ON 1II011WAY , J II 0.2 o - •.U _ ..... -,"--"..... lOE'OO lOE.O' lOl!.02 lor'03 lOEo04 \Of·os LlNO'H ~ ...... -- .....,I."'''' .•c...... -- •.- ,..;-..:.) AOURP. 0.8 ERROR DISTRJDUTION: (,/. 1) =u, 3); 4·ARY PSK ON 1II001WAY AI'I'~()JX J) ERROR D~iRlOl1I10NRESULTS 193 I' N,II. JJ) 11~1.15) 1'(s4.7) 0 0.960426 0.974352 0.982347 I 0.00655J 0.005254 0.()O.1594 2 0.005614 0.00.1374 0.0041(15 3 0.0047ll9 0.003623 0.OOJH55 4 O.()()'1067 0.003000 0.002972 5 0.003436 0.()()2508 0.001550 6 O.002li1l9 0.O()2 II9 0.000457 7 0.002·115 0,001758 0.000056 8 0.002007 ononso ·9 O.OOIMIl O.OOOIl?6 ·10 0.0013M 0.000.183 ·II 0.001111 O.O()()201 ·12 0.OO09()j o.Oll()!lfll · 13 0.000729 0.11110012 ·101 0.000584 0.000001 · 15 0.000460 0.000000 · 16 0.000351 · ·17 0.000254 · ·18 0.000171 · ·19 0.000106 · ·20 0.000058 · ·21 0.000028 · ·22 0.000012 · ·23 0.000004 - ·24 0.000001 · ·25 0.00000o · ·26 0.00000o · ·27 0.00000o · ·28 0.000000 · ·29 1.7E-I0 - · 30 9.8E·12 · · 31 2.8E-13 · · TAmp. D.9 PRODADJLmES P(p, v): (d, k) =(1, 7); 4-ARY PSK ON JllOIIWAY u..------..---.----r---r- - - ,--, • --,...... o -.'U -.......... Wllr;=:ao.............-Io.... " lOE'DO lOE'Ot lOE'OJ lOE'O' lCM!o04 lOl·Oe LlNOTH I DO f 0.8I .. AOURP. D.9 ERROR DISTRlOlmON: flJ. k) =(J, 7);4·ARY PSK ON IIJOIIWAY ApPF.NOIX D ERROR DISI'RJDU11ON RESULTS 194 I' 1'<1'. 3J) 1·~1.15) .'lI,. 7) 0 0.969705 0.979983 0.985489 I 0.004587 0.003551 0.003493 2 0.003960 0.003052 0.003503 3 0.003412 0.002663 0.003301 4 0.002933 0.0<12378 0.002485 5 0.002516 0.002157 0.001285 6 0.002155 0.001929 0.000389 7 0.001844 0.0<1I(,24 0.ססOO50 8 0.001579 0.001222 ·9 0.001356 0.000785 ·10 0.001168 O.Oroll J ·II 0.001010 0.000171 ·12 0.000872 0.000053 ·13 0.0007-15 0.000011 ·14 0.000622 0.000001 ·IS 0.00().199 0.00ססoo ·16 0.000379 · ·17 0.000269 · ·18 0.000175 · ·19 0.000104 · ·20 0.000055 · ·21 0.ססOO26 · ·22 0.000011 · ·23 O.ooooor · ·24 0.0ססoo1 · ·25 0.00ססOO · ·26 0.o00ooo · ·27 0.o00ooo · ·28 0.o00ooo · ·29 1.8E·10 · ·30 1.1 E·l1 · ·31 3.4E·1J · - TA8LH 0.10 PRoDABlrmHS PCp. v): (d. k) =(2. 7); 4-ARY PSK ON IIIOnWAY ~,: '" --.. 1.0£·0:1 lot·O' 1.01.04 1.01'05 LINOTH NI9i.............--....--.'.-_••• 1.0t!·OO t.2,--..---r---.,.--...--~ ...---,---, , 1 ' I f I 0.:1' ........, ,...."" ....c...... AOURP. D.lO r~ROR DfSTRmtmoN: (d, A:) =(2, 7); 4·ARY PSK ON 1I1011WAY AI'Pf~DlX D ERROR DISI'RJDtmON RESULTS 195 " I»CJI. 31) I»CJ,. 15) 1'{J1.7) 0 0.992938 0.995526 0.996891 1 0.001335 0.000970 0.000906 2 0.001096 0.000796 0.000824 3 0.000899 0.000661 0.000682 .1 0.000736 0.000556 0.000441 5 O.OOOllOl 0.000-166 0.000196 6 0.000491 0.0003n 0.000052 7 0.000402 0.000282 0.000006 8 0.000328 0.000186 - 9 0.000269 O.()OO IlJ.I - 10 0.000220 0.OOOQ.17 - II 0.000179 0.000017 - 12 0.0001·14 0.00000·1 - 13 0.000113 O.llOOOOO - 14 0.OOOllR5 O.(l()OO/lll - 15 0.000061 0.000000 - 16 0.ססOO41 · - 17 0.ססOO25 · -18 0.00001·1 · - 19 0.1100007 · - 20 0.000003 · - 21 0.000001 · - .,., 0.000000 · . .... 23 0.o00ooo · - 24 0.000000 · - 25 0.000000 · - 26 0.o00ooo · - 27 0.00ססoo · - 28 4.JE-l1 - - 29 3.8E·12 · - 30 2.2E·13 · - 31 6.m·15 · - --- TAOLE 0.11 PROBAOIU11ES PCp. V): W. k, Q = (0,2. 1); 8-ARY PSK IN CITY 1.2.----,,---.,----.------.---.............. ! r !I o.a· : ? I f 0.2 o -r1~ - ..... tOE.OO tOE'Ol -.,. _::f..~.u ... 1.0E.02 1.01·0) LENOllt tOll'04 tOI'OI I:tOURH 0.11 ERROR DISTRIDlTI10N: W, k, Q = (0, 2. 1); 8-ARV PSK IN CITY ApW.NDlX 0 ERROR DlSTRlDtmON RESULTS 196 II I)CI,. 3J) I)CJ,. 15) I·CI,.7) 0 0.982961 0.989004 0.992191 I 0.0021UJ 0.OO212J 0.001·)&1 2 0.OO2]l)C) 0.00171H 0.001936 3 0.002027 O.OOISlJ 0.001764 4 0.001709 0.001312 0.001272 S 0.001437 0.1101158 0.000632 6 0.001207 0.001008 0.0001&1 7 0.001012 0.000825 0.ססOO24 8 0.0008-18 0.llOO602 · 9 0.000712 0.000374 · 10 0.000599 0,11110 Il)() · II 0.()OO506 0.OllOO76 · 12 0.000·127 0.000023 · JJ 0.000356 0,llOOOO4 · I·' 0.000290 0.00ססoo · 15 0.OOO.?27 0,00ססoo - 16 0.000168 · ·17 0.000116 · · 18 0.()(1007·1 · ·19 0.0000.12 · · 20 0.ססOO22 · · 21 0.000010 - - 22 0.ססOO0-1 · · 23 0.0ססoo1 · ·24 0.o00ooo · ·25 0.ססOO00 · · 26 0.o00ooo · · 27 0.o00ooo · · 28 0.o00ooo · ·29 6.3E-ll · · 30 4.1E·12 · · 31 l.3E·1J · · TAmE 0.12 PROBAOII.mES P(p. v): W. k, C)= (0, 1. 1): 8-ARY PSK IN CITY I.2,.-.--.----,-----,---.,r---..,-..., I I" 0.2 o -tt. - •. tat.oo lOl'O' I I• o,a I I FWtlRI\ n.12 ERROR DISTRltnmON: li', k. C) = (0, I. I): 8-ARY PSK IN CITY ApPf.NDlX D ERROR DlSTRIDU110N RESULTS 197 I' PIJMII ,.oeoo' 10100' "01·04 UNO'H f:tOURR D.l4 F..RROR DlSTRmunoN: (d, t) =(1,7); 8-ARY rsK INCt1Y Arw.NDlx D ERROR DISTRIOU11ON RESULTS 199 I' I-~,. 3J) 11~.15) I-e". 7) 0 0.985207 0.990691 0.993495 I 0.002715 0.00IlJ.t) 0.001751 2 0.002243 0.001589 0.001674 J 0.001850 0.001315 0.001468 4 0.001523 0.001116 0.000997 5 0.001251 O.OOO96~ O.()()()464 6 0.OOIO.?7 0.0/101121 0.000130 7 0.0008-11 O.OOlIMK 0.000016 II 0.0006119 0.000·151 ·9 0.000566 O.OOOUl4 ·10 0.000467 O.()(lOl2() ·II 0.000387 O.O()()()47 · 12 0.000320 0.000013 · 13 0.000262 0.000002 ·14 0.000208 0.00000o · 15 0.000158 0.000000 ·16 0.000113 · ·17 0.000074 · ·18 0.000045 · · 19 0.000024 · · 20 0.000012 · ·21 0.000005 · · 22 0.000002 · ·23 0.000000 · · 24 0.00000o · · 25 0.00000o · · 26 0.000000 · · 27 0.00000o · · 28 2.2E·1O · ·29 2.m· J) · ·30 1.3E·12 · ·31 4.0I~·14 · · TABU! D.lS PRonADlLmES P(p. * (PIt) = (21 7) ; 8-ARY PSK IN crrv i 0.2-i .... • f' '~to -,r. __It_" . ,11111 • "................. - •• 1,01.00 t,O£'Ot 1,01'02 1,01·03 t.oe·04 \.01·06 I,CM!·oe LENOTH , I :} r I:tOURR 0.15 HRROR DlSTRltltmON: W. t) = (21 7); 8-ARV PSK IN CITY =9 ApPf.NDlX D ERROR DasnummON RESULTS 200 II f>(,11.3J) 1-(,11.15) .ICJ,.7) -- 0 0.970107 0.9/10111 0.985551 I 0.()().1568 0.OOJ5·16 0.003571 2 0.003925 0.OOJ079 0.003572 3 0.003369 0.002709 0.003340 4 0.0021191 0.1102422 0.002425 5 0,(lO2·11lO 0.1l()21I1S 0.001173 6 0.(102129 0.0019J2 0.000325 7 O.OOHUO 0.1101595 0.()()OO311 II o.oolsn 0.0011M ·9 0.001.l62 Il.Ooml" ·III O.IKlII7H O.1I0(),IS·1 ·II O.OOlOIK O,()()() 1.15 · 12 0.000103 0.1I11110JK ·IJ 0.000735 n,lJOllll1l7 · 14 O.(){)OflO I O.1I0()()(11l · 15 O.OOO·lfll) 0.000000 · 16 O,OOOJ·15 · 17 O.OOO2J5 · · 18 0.0001·16 · 19 0.OOOOK2 · - 20 0.0000·11 · · 21 O.lIOllOIK · ·22 0.000007 - 23 0.000002 ·24 0.000000 · · 25 0.000000 · - 26 0.000000 · · 27 0.000000 · - 28 0.00000o · · 29 6.1E·J1 · ·30 3.51~-12 · ·31 9.5E·I·I · TAmp. D.l6 PRonAn~ P{p, v): (d, k, C) =(0,2, 1): 8-ARY PSK ON HrOlfWAY 1.2r---..----r--.....,.---,----,--, \.i u /'i .. .. . _. o -,t.t. __ lo,.uooJ:LUllh ._.t,,,,"__... _4 1.0E.OO 1.0I!.01 1.0E.02 10f'O:l "0I!'04 1.01·01 UNOTtf AOURH 0.16 ERROR DJSTRlOunON: (d, k, C) =(0. 2, I): 8-ARY PSK ON1II00rwAY ApPP.NDIX D mn _ r~ROR DlsnuOlmON RESULTS 201 I' I'{J,. J J) ..~,. 15) It(sl_ 7) -- 0 0.9f!.l-1:?4 0.988375 0.991093 I 0.001955 0,001648 0.001788 2 0,001765 0.001·1112 0.OO20118 3 0.001589 0,001365 0.002153 ·1 0.001428 0,001312 0.001685 5 0,001280 0,001307 O,OOOAA9 6 0.001146 0,0012116 O.OOO:?HI 7 0.001024 0.00111l7 0.0000·10 II 0.000917 0,0001)22 ·9 0.0001126 0.000610 ·10 0.000751 0.000327 ·II 0.000690 O,OOOIJ8 ·12 0.000638 O,()OOO..·1 ·1J 0.000585 0.000010 · 1·1 0.000522 0.000001 ·15 0.000"·15 0.000000 ·16 0.000355 · ·17 0.000262 · ·18 0.000176 · ·19 0.000107 · ·20 0.000058 · ·21 0.000028 · ·22 0.000012 · ·23 0.000004 · ·24 0.000001 · ·25 0.000000 · ·26 0.000000 · ·27 0.000000 · ·28 0.000000 · ·29 0.000000 · ·30 1.8E·11 · ·31 6.m·13 · - . TAnU! OJ7 PRODAnll.rMES P~l. V): (d, t, C) =(0, 1, 1); 8-ARY PSK ON 1II00rwAY , I f I 1.2,--.--.---.......----,.---....----.--, ')' / " .::~;t.t " lO(-02 lOl-03 toe.o. 10(-0' LlNOTlt FlClURH D.17 ERROR DISTRlOtmON: (d, 1:, C) =(0, 1, I); 8-ARY PSK ON IIrOfIWAY ApJIP.NDlX D ERROR DlSTRIDtmON RESULTS 202 I' J»(JI. 3J) I·~,. 15) JI<,J.7) 0 0.977821 0,983054 0.986012 I 0.002012 0.001769 0.002791 2 0.001856 0.001759 0.003612 3 0.001712 0,001901 0.003562 4 0.001581 0.002155 0.002480 5 0.001·167 0.002357 0.001161 6 0.OOLl76 0,002311 0.OOOJ34 7 0.00Ll16 0.0019·16 0.000045 8 0.001294 0,001374 ·9 0.001303 0.000800 ·10 0.001326 0,000378 ·II O,OOLl33 0,000141 · 12 0.001290 0,0000,10 ·IJ 0.001178 0,000008 · 14 O,(lOIOOI 0.000001 · 15 0.00071B 0,000000 · 16 0,000560 · ·17 0,0003£1.1 · ·18 0.000214 · ·19 0,000113 ·20 0.000054 · ·21 0.000023 · · 22 0,000008 · · 23 0.000002 · · 24 0.000000 · - 25 0.000000 · - 26 0.000000 · - 27 0.000000 · · 28 0.000000 · - 29 9.7E·11 · - 30 6.4E·12 · - 31 2.IE·1J · - TAnLE D.l8 PRonAnrunES PCp, v): Cd. k) =(J. 3); 8-ARY PSK ON JllOIIWAY 1.2,....--~,...--......--....,.--.-,---...,--......, ! r, i 0.8' f rI 0,2' 0-·" lOE'OO 1.0E·01 ... /. lOI.04 1.or,O. lOl'OI ACIURP. D.18 ERROR DI5TRlUtmON: fll.!) =(I, 3); 8-ARY PSK ON 1II00IWAY Al'llf-.NDlX D ERROR D~lRmU110N RESULTS 203 --- I' I'{JI. 3J) I'{JI, 15) I t (P. 7) 0 0.9R4I01 0.989727 0.992M·1 I 0.002601 0,00 I',M2 o.oorsn 2 0.002208 0.001633 0.001809 3 O.001H70 0.001391 0.001670 01 0.001581 0.1101216 0.001212 5 0.00133·1 O.oollll{fl 0.()OOflO9 6 0.001123 0.0(0951) . 0.000186 7 0.1)()09·14 0.000795 O.OOO(}25 8 0.000794 0.000585 · 9 0.000Ml9 0.000367 · 10 0.000566 0,000189 · II 0.000·182 o,oooon · 12 0.000410 0.000023 · u 0.0003·16 O.OOOOOS · 101 0.000286 0.000000 - 15 0.000227 0.000000 · 16 0.000170 · · 17 0.000118 · · 18 0.000076 · ·19 0.0000·101 · - 20 0.000023 · · 21 0.000011 - 22 0.00000·1 - 23 0.000001 · · 2·1 0.000000 · · 25 0.000000 · · 26 0.000000 · - 27 0.000000 · - 28 0.000000 · · 29 8.5E·II · -30 5.7E·12 · - 31 1.9E·13 · - TAnl.E 0.19 PRonAmunr-s PC/J. v): (d. k) =(1, 7): 8-ARY PSK ON JIIonWAY Ur-~-...----,-----r---"'---'" I f I , I I 1.0!.02 I.oe·o' LENOftt Fl(llJRI~ 1>.19 r~ROR DISTRlI1tmON: "'. k) =(J, 7); 8·ARY PSK ON JlIOIIWAY ApPf.NDlX D ERROR DISTRIDU110N RESULTS 204 " J) #inc\udc #inc\udc #inc\udc #inc\lIdc #inc\lIdc #define TLC ""C9' #define TRC \,'~DD' #define DLC \xCS' #define DRC ""DC' #define JlLNE \'(CD' #define VLNE \xDA' #define RCNTR \xD9' #define LCNTR \'(CC' #define TCNTR \'(CD' #define CNTR ""CE' #define DCNTR ""CA' MP.ALY TO MOORE AND FSM MINIMIZA110N 210 I*Dcfinc characters for window.' char (*elements[6]) = {"Create", "Mealy to Moore", "Moore to Mealy", "Reduction", "~nd", "Save"); char ch='n'; int cur_row, k; void reversevideofvoid): void nvideolvoid): void drawbordcr(int tlx, int tly, int brx, int bry, int lycntr, int lxcntr): void up_arrow(void); void down_arrow(void); void arrow(void); void filcnms(chnr pathnnmc[Rt]); void cwindow(int nstate, int k); void cmalrix(int nstate, double alpha, int outputsl; void createflnt tx, int ty, inl by): void mealytvoid): ApPf.NDIX E Mp.ALY TO MOORE AND FSM MINIMIZA110N 211 void moorefvold): void reductiontvold): void loadfint tx, int ty, int by); void savelvold): void quitfint tx, int ty, int by); void selectflnt tx, int ty, int by); void twindow(int amnt, int tx, int ty, int by); /*••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••t void reversevideofvold) tcxtattr(llLACK + (WIIITE«4»; /*••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••, void nvideotvoid) tcxtattr(WIIITE + (DLACK«4»; /*••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••, void drawborderfint tlx, int tly, int brx, int bry, int Iyentr, int lxcntr) ( int i; for(i =tlx + 1; i <= brx • 1; i++) gotoxyfi, tly): pUlch(lILNE): gotoxyfi, bry): putch(IILNE); (or(i =tly + I; i <= bry- 1; i++) ( gotoxyltlx, 1): Apw.NDlX E putch(VLNE); gotoxytbrx, 0; plltch(VLNE); gotoxyltlx, tly); plltch(TLC); gotoxyfbrx, tly); plltch(TRC); gotoxyulx, bry): plItch(nLC); gotoxyfbrx, bry): plItch(nRC); if(Jycnlr != 0) ( for(i =tlx + 1; i <= brx- I; i-++) ( gotoxyfi, lycntr): putch(J ILNE); gotoxyttlx, lycntr): putch(LCNTR); gotoxyfbrx, lycntr): pUlch(RCNTR); if(lxcntr != 0) ( for(j =tly + 1: i <= bry • 1: i++) ( gotoxytlxcntr, i); putch(VLNE); gOloxy(Jxcntr. tly); MF.ALY TO MOORE AND FSM MINIMlZAnoN 212 ApPF~D1X E putch(TCNTR): gotoxytlxcntr, lycntr): plltch(CNTR): gotoxytlxcntr, bry): plltch(DCNTR): MEALY TO MOORE AND FSM MlNIMIZAllON 213 ~................................................•................., void up_nrrow(void) ( cur_row = whcrcyO: switchlcur_row) case 1 : case 2 : case 3 : case 4 : case 5 : case 6 : nvidcoO: gotoxytl, cur_row); cputslelcmcntslcurrow-Ill; cur_row =6: reversevideof): gotoxytl, cur_row); cpntsfclcmentslcur.row-Il): break; nvidcoO: gOloxy(t. cur_row); cpntsfelcmcntslcur_row- J)); reversevideofl: cur_row--: gotoxy(t. cur_row); cputsfclememslcur.row-l )); brenk; AI'rP.NDlX E MJ7.AI.Y TO MOORE AND FSM MINIMJZAl10N 214 /*••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••t void down arrowfvold) switchfcurJOW =whcrcyO> ( case 6 : case 1 : case 2 : case 3 : case 4 : case 5 : nvidcoO; gotoxyf}, cur.row): CpUls(clcmcnls[curJow.l )); cur_row =1; reverscvideof): . gotoxyf l, cur_row); cpuls(clcmcnls[cur_row.t )); break; nvideof): gotoxytl , cur_row); cputsfelcmcntslcur.jow-l ]); reversevideof): cucrow++; gotoxytt, cur_row); cputsfelernentslcurrow-I )); break; /*••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••t void arrowfvoid) !lowitch(ch = getchf)) ( case 'PO : down_nrrowO; break; . . • . .. ApPP.NDlX E case IHI : Mp.Al.Y TO MOORE AND FSM MINlMlZAnON 215 up_nrrowO: break; /*••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••, void filenmstchar pathnameldl]) ( int count =3, col = 1; struct ffblk filcinfo; window(31, 9, 74, 18); gotoxy(l8, 1); printf("%s\\•.MCII ", pathname): if(findfirst('\•.mch", &fiIeinfo, 0) != 0) gotoxyfl , 2): cputs("No file's foundll!"): else gotoxytl , 2); printf("%s", fileinfo,fCnnmc); while(findncxt(&fiIeinfo) = 0 ) gotoxyfcol, count); printf("%s\n", fileinfo.fCnnmc); count++; if«count = 1J) && (col = 14)) brenk; if(count == 1J) ( count = 2; col =14; ArPHNDIX E MF.ALY TO MOORE AND FSM MINIMlZAnoN 216 I····················································· t void loadlint tx, int ty, int by) ( char pathnllme[81 l, ·tbllffcr; int tbufsize: struet ffblk fileinfo; if(gctcwd(pllthnnmc, 80) == NULL) perrorf'Error establishing directory!!!!"); else tbutsize =2.(22 • 7 +0.02 - 7 + 1); if((tbuffer = (char s) mallocttbufslze) == NULL) cputs("Error allocating buffer!!!!"); exltfl); if(!gettext(7. 7,22, 12, tbufferr) ( cputs("Error saving text!!!I"): exitfl); ) drawborderf l, I, 15,3, 0, 0); gotoxy(2, 2); printf("%s"•• MCII", pathname): whilc«ch =getch(» !=\x 1B') ( switchlch) case V: filenmsfpathname); break; AI'W.NDlX E } windowltx, ty, (tx+15), by); if(!puttcxt(7. 7, 22, 12, tbuffcr)) cputsf'Error restoring text!!!! "): gotoxytl , 5>: MF.ALY TO MOORE AND FSM MlNlMlZAl10N 217 /*••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••, void ewindowfint nstate, int k] int m, n: int fbufsize] 16]; char .fbuffcr[16]; fbufsiza[k] =2.«nstnte + 3) - 3).«nstate + 3) • 2); if«fbllffer[k] = (char s) mallocffbufsizejkl)) == NULL) ( cputs("Error allocating buffcr!!!I"); exit(t); ) if(!gettcxt(4, 3. (nstate +3), (nstate +3), fbllffcr[k))) ( cputs("Error saving textllll"): cxit(t ): ) window(4. 3. (nstate + 3), (nstate + 2»; c1rscrO; window(4. 3. (nstate + 3), (nsmte + 3»; for(m =1: m <= nstate: m+t) for(n = 1: n <= nstate: nt+) gotoxytn, m): putch(OxOF); ApPf.NDIX E Mr.AJ.Y TO MOORE AND FSM MINIMIZAnON 218 ,..••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••t void earrowfvold) char p; switch( P =getch()) ( case 'B' : clrserf): ,.. , void ematrix(int nstate, double alpha, int outputs) ( int i, j; char 8_e)em[t6][80][25]; for(i =1; i <= nstate; i++) gotoxyt}, i + 2); printf("o/od". 0; drnwbordcr= '0') II !(o_clcm[k][i-llO-l] <= 'I')) gotoxyfi, j); a_clcm[k](i-JlU-I] =getchef): switch(a_clcm[k)[i- JlU-}]) ( case oxln case '\.'~O' : k++; ewindowfnstate, k); i =j =I; break; earrowf): break; ApmNDlX E k++: ewlndowtnstate, k): MEALY TO MOORE AND FSM MINIMlZA110N 220 / t void createflnt tx, int ty, int by) ( int i, sbufsize, tbufsize, nstate, stntcslzl = (0,0), outputs: double alpha, inputs: char .sbuffer, .tbuffcr, chs; sbufsize =2.(75 - 5 + 1).09 - 5 + 0: tbefsize =2.(20 - 6 +1).05 - 12 + 0: if«sbllffcr =(char .) malloctsbufslzel) == NULL) ( cputst'Error allocating bufferllll"): exit0 ); if(tbllffer = (char .) mallocltbufsizel) = NULL) ( cpllts("Error allocating buffer!!!!"): exittl): if(!gettext (5, 5, 75, 19, sbuffcr) II Igcttext(6. 12. 20, 15, tbuffcr» cputs("Error saving textllll"): cxit(I ); window(6, 12.29. 14}; elrscrO: drnwborderO. I, 23, 3, 0, 0): ApPENDIX E ch = 'a'; whllekh != \r') { nstate =inputs = outputs = 0; gotoxy(2.2): cputsl" gotoxy(2. 2): eputs("lIow mnny states? H): MEALY TO MOORE AND FSM MINlMJZAnON 221 H): whilc(l(nstnte > 0) III(nstate < 23)) { gotoxy(l9.2); for(i = 0: i <= 1; i++) { chs =gcteheO: if(!(ehs >= 0,(30) " !(chs < 0,(40)) gotoxy(l9,2): else statesli] =(int) chs - 48; } nstate =10*statcs[0) + statesltl: } delay(I 00): gotoxy(2. 2): cputs(" gotoxy(2. 2): cputs("lnput symbols? H); whilc(l(inputs > 0) II !(inputs < 9)) { chs = gctehcO: if(!(ehs > 0,(30) II Hchs < 0,(40)) gotoxy(t7,2); inputs =(int) chs• 48; } H): ,APPIOOlIX P. delllYO(0): gotmcy(2, 2); cputs(" gotoxy(2, 2); cputs("Output symhols? "); 'gmt Mp.Al.Y TO MOORP. AND FSM MINlMIZA110N 222 whilc(!(outputs >0) II Huutputs < 9)) ( chs = getchef): i«l(chs > Ox30) II Hchs < 0,,-10)) gotoxy(J8,2); outputs = (int) chs- 4R; ) dclay( J00); gotoxy(2, 2); eputs("Entcr to continue."); eh =getchf): c1rscrO: pullext(6, J2, 20. J5, tbuffer): alpha =pow(2.0. inputs); window(J' I, BO. 25); c1rscrO: print(("You have to enter IJW E and %c rnllriCCs,", Cindalpha. O"f-.2); Cf11lurix(nstatc. n1rhll. Ot,tput,); window(o" ty. (IX + J5), by); gOloxy(J, J); ,..............•................................................••••/ \'aidquil(int IX. int Iy. int hy) ( ApPeNDIX E windowO. 1.79.25); gotoxy(22. 25): nvideoO: CpUIS("Surc you want 10 exil[N]? H); ch = lolower(gctch()); if(ch == 'y') c1rscrO; else gotoxy(22. 25); clreolf): windowttx, ty, (Ix + 15), by); gotoxytt , cur.jow): MF.ALY TO MOORe AND FSM MINIMlZA110N 223 /*•••••••••••••••••••••••••••••*••••••••••••••••••••••••••••••••••••, void selectflnt tx, int ty, int by) ( nvideoO; switchfcur_row =whercyO) ( case 1 : createttx, ty, by); break; case 2 : mealyf): break; case 3 : moorcO; break; case 4 : reductionf): break; case 5 : loadftx, Iy, by); brenk; case 6 : snvcO: break; ApPF.NDIX E MEAI.Y TOMOORE AND FSM MINIMlZA110N 224 r • ,..........•.•.••..............................•.•..•.............•./ void twindow(int arnnt, int tx, int ty, int by) ( int i, butsize, oty; char .bllffcr; oty = ty; bulsize =2.(by - ty + O.((lx + 15) - tx + J); if((buffcr =(char .) maJloc(bufsizc» == NULL) ( cputsf'Error allocating buffer!!! l"): exittl): nvideoO: forf = 1; i <= arnnt; i++, oly++) { gotoxyttx, oty); cputsfelernentsli-I ]); } highvideol); gOloxy(t6,7); cputs("Mcnu"); gOIOXY(SO, 7); cPllts("Window") ; normvidcoO; windowux, ty, (tx + 15), by); if(!gcItCXI(tx, ty, (tx + 15), by, buffer» ( cputs("Error saving textllll"): exitll]: ApP£ND1X E reversevideoO: cputslelcmentslul): whilelch != 'y') ( ch=getcht): switchfch) case \x0' Mp.Al.Y TO MOORE AND FSM MOOMtZAnON 225 : DITOWO; ~Check for arrow keys.' break: case '\r' : select (tx, ty, by); break; "'Chcck for Enter key.' case \x Ill' : quil(tX. ty, by); break; "..............................................................•...., void mainlvoid) clrserf): drawborder(5. 5. 75. 19.8,30): twindow(6.7. 10. 17); 226 APPENDIXF GALLISTINGS The GAL program listings for the DSP flnite-state machine and the 8254 timcr card arc presented in this appendix. As mentioned in Appendix A, the DSP finitc state machine used two GAL 20V8's and the timer card used only oneGAL 16V8. It must be noted that the symbols &, land! indicate, respectively, the logical AND, OR and NOT functions. This listings will also serve asexamples for GAL programming. ApW.NDlX F DEVICE 20V8; TITLE ADRESS DECODING FOR PC; NAME ADR.PLD; SIGNATURE ADR_DEC; ~ ADRESS LINE INPUTS., PIN 1 = CLK; PIN 2 = A19; PIN 3 = AlB; PIN 4 = AI?; PIN 5 = A16; PIN 6 = A15; PIN 7 = A14; PIN 8 = AI3; PIN 9 = AI2; PIN 10 = All; PIN 11 = DO; PIN 12 = GND; PIN 13 = OE; PIN 14 = LOE; PIN 24 = VCC; ~ CIIIP SELECT OUTPl!fS., PIN 15 = SO; PIN 16 = SI; PIN 17 = S'·.., PIN 18 = S3; PIN 19 = S4', PIN 20 = ccso. PIN 21 = CCSl; PIN 22 = RSTMS; ~ GENERATING CIIIP SELECTS ., GAL LIS'11NOS 2T1 ISO =A19 & A18 & IAl? & lA16 & Al5 &Al4 & IA13 & IAl2 & IAI1; ApPENDIX F GAL 1JS'I1NOS 228 !SI =Al9 & AlB & !AI? & !A16 & AI5 & AI4 & !A13 & !A12 & All; !S2 =Al9 & AlB & !AI? & !A16 & Al5 & Al4 & !A13 & Al2 & !All; !S3 =AI9 & AlB & !AI? & !A16 & AI5 & AI4 & !A13 & Al2 & All; !54 =A19 & AlB & tAl? & !A16 & Al5 & A14 & AIJ & !At2 & tAll; !CCSO =Al9 & AlB & !AI? & !A16 & Al5 & Al4 & !A13 & !A12 & !All IAl9 & AI8 & !Al? & IAI6 & Al5 & Al4 & !AIJ & !At2 & All; tCCSI =A19 & A18 & !Al?& !A16 & Al5 & Al4 & tA13 & A12 & IAll I A19 & AlB & !Al? & tA16 & Al5 & Al4 &tA13 & A12 & All; 1* latch programmed in GAL ./ RSTMS.D =LOE & RSTMS.Q IDO& tLOE; APPF.NDlX F GAL US'nNOS 229 DEVICE 20V8: TITLE ADRESS DECODING FORTMS; NAME TADR.PLD; SIGNATURE TMSADEC; PIN 1 = A3; PIN 2 = A4: PIN 3 = AS; PIN 4 = A6; PIN 5 = A7: PIN 6 = AS; PIN 7 = A9; PIN S = AlO; PIN 9 = All; PIN 10 = MEN; PIN 11 = DEN; PIN 12 = GND; PIN 13 = WE; PIN 14 = RSTMS; PIN 23 = CSO; PIN 15 = SO; PIN 16 = SI; PIN 17 = MEMW; PIN 18 = EN; PIN 19 = POE; PIN 20 = RSTMSL; PIN 21 = DDlR; PIN 22 = N.C; PIN 24 = VCC; ISO =!All & OMEN IIWE); lSI =All & OMEN I !WE); MEMW = t(!WE & t(!A3 & IA4 & lAS & !A6 & !A? & !A8 & IA9 & IAIO & !AII)); ApPENDIX F GAL US'nNOS 230 lPOE =IDEN & \VE & (!A3 & !A4 & lAS & IA6 & !A? & !AB & IA9 & !AIO & IAll ) I DEN & IWE & (lA3 & IA4 & lAS & IA6 &IA? & !AS & !A9& IAIO & fAll): lEN = ICSO & fRSTMS: RSTMSL = !RSTMS; DDIR =DEN & MEN: ApW.NDlX F DEVICE 16V8: TITLE ADDRESS DECODING FOR TIMER CARD IN PC: NAME IOPORT.PLD SIGNATURE I/O PORT; PIN 1 = A2; PIN 2 = A3; PIN 3 = A4; PIN 4 = AS; PIN 5 = A6; PIN 6 = A7; PIN 7 = AS; PIN B = A9; PIN 9 = AEN; PIN 10 = GND; PIN 12 = CSO; PIN 13 = csr, PIN 15 = eS2; PIN t4 = ccs PIN 20 = vee, !CSO =IAEN & !A9 & lAB& !A7 & A6 & AS& A4 & AJ & A2; !CSt =!AEN & !A9 & !AB & !A? & A6 & A5 & A4 & AJ & !A2; ices =!AEN & !A9 & !A8& !A? & A6& A5& A4 & AJ & A2 I !AEN & !A9 & !AB & !A? & A6 & AS & A4 & AJ & IA2 IIAEN & !A9 & !AB & !A? & A6 & A5 & A4 & IA3 & A2; GAL LIS'J1NOS 231 232 APPENDIXG PC TOTMSPROGRAMMEMORY TRANSFERPROGRAM This appendix contains a program listing in Turbo C. which enabled the PC to test the TMS program memory and to transfer precompiled program memory to the static RAM common to both processors. Arl'l~lx G #include #includc #includc #includc #includc #includc void tescmcmO: void rcad_mpoO: int ctoi( int nib): PC TO TMS PROORAM Mfl.MORV TRANSw.R PROORAM 233 ft'•••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••• • • • • ••, void testrnemf) int i =0; unsigned scgO =OxccOO. seg! = OxcdOO. off; char x =Ox80. y = Ox?f. xt, yt; pokebl OxccOO. OxO, Oxl ); clrscrO; for( off =0; off <= Oxfff; of(++ ) ( pokebl segu, off. x ); pokebl seg1. off. Y): xt =pcckb( segf), off ); yt=peekbl seg1. off ); if( xt != x II yt != y ) i++; J if( i >0 ) printf( "Program memory of TMS has o/ed errorsll", i ); else puts( "Program memory of TMS is OKIl"); ApPP.ND1X a PC TO TMS PROGRAM MEMORY TRANsFP.R PROORAM 234 /*••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••, void rcnd_mpoO ( int len, i, j =0, k =0, I, m=0, n, off; unsigned scgO =OxccOO, scg1 =O.xcdOO; int dtn(4096), In, hn; char infilcnnmc[lO), ans ='a'; char extil] = ".MPO"; ALE .infilc; printf( '\n\nEntcr TMSobject file [•.MPO): " ); gets( infilennmc ); len =strlcn( infilennme ); for( i =0; i <= len; i++ ) ( if( infilcnnmc[i] != ',' ) j++; ) if( j != len) &1rcnt( infilcnamc, exti ); if« infile =fopcn( infilennmc, "rb" »== NULL) ( printf( ''\n\n\"%s\"", infilename ); perrorf "" ); exitll): ) whilc« dtn[k) =getcl infile» != EOr) k++; pokebl OxccOO, OxO, Oxl ); if( dtn[O) == Ox4b ) n =13; ApfIl.NDlX o PC TO TMS PROGRAM MF.MORY TRANSFER PROORAM 235 fore off= 0,1 = n: I <= k: I += 5 ) ( switch( dtn[l] ) ( cnse Ox39 : off = ctoi( dta[J+4] ) + 16*cloi( dto[J+3] ) + 256*ctoi( dta[l+2] ) +4096*ctoi( dtn[l+ 1] ); brenk; case Ox42 : In =ctoildlo[l+4]) + 16*cloi( 01011+3] ); hn =ctoi(dla[J+2» + 16*Cloi(dln[J+t]); pokeb( scgO. off, In ); pokeb( seg l, off, hn ); off++; brenk; case Ox46 : 1= m +=77; break; case Ox3a : fclosc( infilc ); printf( "'nConverted file has o/ro bytes.", k ); printf'( ''\n\nStart TMS (YIN): "); while( !kbhitO ) ( gotoxyl 18, 8 ); ans=toupper( getchcO ); if( ans = 'Y' ) ( pokeb! OxccOO, 0, 0 ); prinlf( "\n\nTMS cxecutlng file \"%s\".". infilennmc); cxit(l); ) if( ans == 'N' ) ( ApPeNDIX 0 ) ) ) PC TO TMS PROGRAM MF.MORY TRANsFER PROORAM 236 print(( "\n\nProgrnm terminated without starting TMS.- ); exittl]: } ) /*••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••, int ctol! int Inib ) int i, j; switch( Inib ) case Ox30 : i = 0; break; case Ox31 : i = I; break; case Ox32 : i =2; break; case Ox33 : i =3; break; case Ox34 : i =4; break; case Ox35 : i = 5; break; case Ox36 : i =6; break; case Ox37 : i = 7; break; case Ox38 : i = 8; break; case 0:<39 : i = 9; brenk; case Ox41 : i =10; brenk; Apw~D1x G case 0:<42: i =11; brenk: case 0:<43 : i =12; brenk: case 0:<44 : i =13; brenk: case 0:<45 : i =14; brenk: case 0:<46: i = 15; brenk: } rctum{ i ); } PC TO TMS PROGRAM MF.MORY 1'RANSl-n PROGRAM 237 /.......•.....•................................•...............•.•...•, mainO test_memO: 1* void which tests the static RAM */ read_mpoO: 1* void which transfers program memory to RAM ., } 238 APPENDIXH HP4925BCLOCKRECOVERYCIRCUIT With the frequency domain results (chapter 6) the liP 492SB bit error rate meter played a very important role in the experimental set up. Toensure complete documentation and repeatability of results, it was decided to include the clock extraction circuit diagram of the UP 49258 BER meter; this appendix contains just that, 239 REFERENCES [I] G. Calhoun, "Digital Cellular Radio," Ar1ech House, Inc., Norwood, 1988. (2) P.A. Siegel, "Recording codes (or digital magnetic storage," IEEE Trnnsactlons on Magnetics, vol. Mng-21, no. 5, September 1985, pp 1344·1349. [3J K.A. Schouhammcr Immink, "Coding techniques for optical and magnetic recording channels," Prentice Hall Inc, New York, 1990. [4] \V.I. Fletcher. "Engineering approach to digital design," Prentice Hall, New Jersey, 1980, pp111-118. [5] J.D. Parsons andJ.G. Gardiner, "Mobile communication systems: John Wileyand Sons lnc., New York, 1989. [6] CCIR: International Radio Consultive Committee. "Recommendations and reports of the CCIR, 1981," fCporr780.1. (7) F. Swarts, "Markov characterisation of foding channels: M.r:.ng thesis, Rand Afrikaans University, June 1991. RF.fI1.RI!N(.'F.S 240 ISJ D.R. Oosthuizen, "Markov models for mobile rndio data communication systems," M.Eng thesis, Rand Afrikaans University, December 1990. 19] L.N. Kanal and A.R.K. Sastry, "Models for channels with memory lind their applications to error control," Proceedings of the IEEE, vol 66, no 7, July 1978, pp 724-744. ltoJ J.G. Proakis, "Digital communications," McGraw-lIi11, London, 1985. 11 t] W.C.Y. Lee, "Mobile communication engineering," McGraw-lIi11, New York, 1982. 112J A.N. Kruger, "Introduction of the first cellular mobile radiotelephone system in the Republic of South Africa,II Elckiro, Technical journal of the Department of Posts nnd Telecommunications, vol I, no 2, 1986. 113] A. Gill, "Introduction to the theory of finite-state machines," McGraw-lIiII, New York, J962. 114] F.C. Hennle, "Finite-state models for logical machines," John Wiley and Sons Inc., New York, 1968. 115] C.V. Freiman and A.D. Wyner, "Optimal block codes for noiseless input restricted channels," Information and Control, vol. 7, 1964, pp 398-415. 116] W.H. Kautz, "Fibonacci codes for synchronization control," IEEE Transactions on Information Theory, volIT-J 1,1965, pp 284-292. 117] A. Gabor, "Adaptive Coding for self-clocking recording," IEEE Transactions on Electronic Computers, vol EC-J6, 1967, pp 866-868. 118] D.T. Tang and L.R. Bahl. "Block codes for a class of constrained noiseless channels," Infonnation nnd Control, vol 17, 1970, pp 436-461. It9] P.A. Franaszek, "Sequence-stare encoding for digital transmisslon," Bell Systems Technical Journal, vol 47, January 1968, pp 143-157.: 241 120] K. Norris 11K! D.S. lllOOlnberg. -Channel Cllpacily of charge con.sInined nmltnglh limited codes," IElm Transactions on Magnetics, vol MAO·I?, no. 6, Novemtw 1981, pp 3·152-3455. 121] C.E. Shannon, -A rmllh~mllticDI theory o( communlcauoa," nell SyS1enll T«hnlCllI Journal, vol 27, July 1948, PI) 379·423. 1221 Rot.. Adler, D. CoppMimhh and M. 1I1l!L'in~r, •Algorithms fOf sliding block eedes, An upplication of symbolic dyruunicli to in(()olUliion theory," limE TnrwClions on Information Theory, vol rl'·29, JanuDry 1983, pp 5·22. 12.1] I.. lIong and P. Ostapo, ·Code:c fOf Helf·c1ocking Innllmis.'iion," IBM 'I'«hnlcal Journal of Research and Development, vol 20, July 1975, pp 358·365. 124] K.\V. Cauermole, "Prlnciples of digital line coding," Inlemalionol Journal on Electronics, vol 55, July 1983, JlP 3·33. 1251 J.M. Griffiths, -Binary code suitable for line transmission," E1cclronics Letters, vol 5, 1969, pp 79·81. 126J K V. Khrishnamunhy, "lniroductory theory of computer science," John Wiley and Sons lnc., New York, 1985. 127] G.L Cariolaro et al, "AnolY5is ofcodes and spectra calculations," Inlernational Journal of Electronics, vol 55, no I, t983, pp 33·79. 1281 L Borha, II.C. Ferreira, I. Broere, -New multilevel line codes," IEEE OIobal Telecommunication Conference, December 2-5, 1990, pp 501.4.1·501.4.6. 129] A.M. Patel, "ImproVed encoder and d«Otkr (or D byte-ooentcd rate 819 (0, J) codt," InM Tcchnical Disclosure Dulletin, vol 28, 1985. pp 1938. 130] Hewleu PIlckanJ, -Orenning Ind Jm'ICt manulli (ot' the III'49ZSn bit mor role lest RI And A~'IOriCS,· Mantu,1 p:art no ().192S·9002I. 1.1I J F.G. SI remler, -lntmductinl1 In communication J)'Jtmu,- AddiJllOO' Westey, S)'drwy. 1982. 242 [32] II.C. Ferreira, "On de free mngnetic recording codes generated by (jnile-state machines," IEEE Transactions on MlIgnclics, vol MAO-19, no 6, November 1981, pp 3452-3455. [33] J.L La Cicero, DJ. Costello lind I..C. Peach, "Chnracterisucs of Ihe Hedeman II- J. 11-2 and 11-3 codes," IEEE Transactions on Communications, vol COM·29, no 6, June 1981, pp 901-908. (34) G.V. Jacoby and R. KOSI, "Binary two-thirds rate code with full word look-ahead," IEEE Transnctions on Magnetics, vol MAG-20, September 1984, pp 709-714. (35) G. van Rensburg and I1.C. Ferreira, "Four new runlength constrnined recording codes," Electronic Letters, vol 24, nO 17, 18 August 1988, pp 1110·1111 [36] CCJR: International Rndio Consultive Committee. "Recommendations and reports of the ccm, 1986," vol VIII-L, Land Mobile Service, Amateur Service, Amateur SOlcllite Service, Duvrovnik, 1986, report 903. (37) F. Swarts, II.C. Ferreira and n.R. Oosthuizen, "Renewal channel models for PSK on slowly fading Rayleigh channel," Electronic Letters, vol 25, no 22, October 1989, pp 1514-1415. [38] S. Tsai, "Markov characterization of the IIF channel," IEEE Transactions on Communication Technology, vol COM-17, no I, February 1969, pp 24-32. [39] RD. Frithchman, "A hinary characterization using partitioned Markov chains," IEEE Transactions on Information Theory, vol IT·13, April 1967, pp221-227. [40] Lattice Semiconductor Corporntion, "GAL handbook," 1990. (41) Electronics World + Wireless World, August 1990. (42) Intel Corporation, "Microcontrollcr handbook," 1990. [.13] L.II. Po11ard, "Computer design and architecture," Prentice-Hall International, New Jersey. 1990. 243 [44] F. Gardener, "Phaselock techniques,", McGraw-Hili. 1966. [45] RCA Solid State, "CMOS integrated circuits," 1983. [46] Texas Instruments, "TMS32010 user's guide." 1983. [47] TEMC 32-2, "Fail-safe telemetry system technical manual," M.l4. Engineering Ltd. (Plymouth), UK, Issue 4, January 1987, PP 2-8. (48) E. Zchnvi and J.K. Wolf, "On runlength codes," IEEE Transactions on Information 111COry, vol 34, no I, January 1988, Pi> 45-55.

Efficient frequency modulation systems

Abstract

Extracted data

Efficient frequency modulation systems

Abstract

Extracted data

Related items

Related items