Performance Analysis of IEEE 802.15.4a B P S K / B P P M U W B Transmission by Zahra Ahmadian B.Sc, Ajman University of Science and Technology, 2005 A THESIS SUBMITTED IN PARTIAL FULFILLMENT OF THE REQUIREMENTS FOR THE DEGREE OF MASTER OF APPLIED SCIENCE in THE FACULTY OF GRADUATE STUDIES (Electrical and Computer Engineering) THE UNIVERSITY OF BRITISH COLUMBIA September 2007 © Zahra Ahmadian. 2007 Abstract The ultra-wideband (UWB) technology has recently attracted considerable attention in industry and academia. This is due to the great potentials of the license exempt operation with U W B signals. These include high data. rate, low power consumption, robustness to multipath propagation, good penetration properties and the ability for accurate localization and ranging. The I E E E working group 802.15 set up two task groups (TGs) for the standardization of U W B physical layers for short-range communication: the I E E E T G 802.15.3a for high data-rate transmission which was officially formed in December 2007 and the I E E E T G 802.154a for low data-rate that became an official task group in March 2004. While the T G 802.15.3a did not succeed and was finally disbanded in January 2006; the T G 802.15.4a approved a draft standard in March 2007. This standard prescribes a rather unique coding and modulation scheme, namely the concatenation of an outer Reed-Solomon and an inner convolutional encoder with a mixed binary phase-shift keying and pulse position modulation ( B P S K / B P P M ) and time-varying spreading and position hopping. The decoding for and performance analysis of this coding and modulation scheme are the subjects of this thesis. First, we study the inner convolutional coded B P S K / B P P M in isolation. We suggest an optimal symbol-wise decoding metric, which replaces the sub-optimal bit-wise metric previously suggested in standardization documents, and we define semi-analytical ex-n pressions for the bit-error rate (BER) performance with both optimal and sub-optimal decoding metrics. It is shown through analytical and simulated results that, using the optimal symbol-wise metric results in significant performance gains, of e.g. 2 dB at B E R of 10~3. while decoding complexity is identical to that with bit-wise decoding metric. Based on our semi-analytical results, we also quantify the performance loss due to R A K E combining with a limited number of fingers as opposed to ideal combining. Next, we investigate the entire concatenated coded B P S K / B P P M scheme, including the outer RS code and the inner convolutional code, and we suggest an improved decoding scheme by introducing reliability information generated by the inner decoder. More specifically, two different soft output Viterbi algorithms (SOVA) are considered and compared for generation of reliability information. For the conventional setup of inner Viterbi and outer RS decoder, we define semi-analytical expressions for the frame-error rate (FER) of the overall system, these expressions are highly valuable for quick performance assessment, since simulating the system's performance is extremely time consuming. In addition to decoding assuming perfect channel state information at the receiver (coherent receiver) considered so far, we also study the performance of decoding without channel state information (non-coherent receiver) to detect the B P P M data bit. This decoding mode is explicitly envisioned by the standard. Again, analytical expressions for BER. and F E R are obtained, and the performance of non-coherent and coherent receivers are compared. m Contents A b s t r a c t i i Contents iv L i s t of F igures v i i L i s t of A b b r e v i a t i o n s a n d Symbols x A c k n o w l e d g m e n t s x i i 1 I n t r o d u c t i o n 1 1.1 Background and Motivation 2 1.2 Contributions 4 1.3 Thesis Organization 5 2 U W B System M o d e l 7 2.1 Transmitter 7 2.1.1 Channel Coding 8 2.1.2 Modulator 9 2.1.3 B P S K / B P P M Symbol Structure 10 2.2 Channel Model 13 2.3 Receiver . . .- 14 3 C o n v o l u t i o n a l C o d e d B P S K / B P P M 16 iv 3.1 Equivalent Channel Model 17 3.2 Decoding Metrics 17 3.2.1 Symbol-wise Metric 18 3.2.2 Bit-wise Metric 19 3.3 Viterbi Decoding Algorithm 20 3.4 B E R Analysis for Convolutional Code Decoding 21 3.4.1 B E R Analysis for Symbol-wise Decoding Metric 22 3.4.2 BER, Analysis for Bit-wise Decoding Metric 25 3.5 B E R Numerical and Simulated Results 29 3.5.1 BER, Performance for Symbol-wise and Bit-wise Decoding Metrics 30 3.5.2 R A K E Receiver 31 3.5.3 Effect of Time-varying Scrambling Sequence 32 4 Concatenated Coded B P S K / B P P M 37 4.1 Soft Output Viterbi Algorithm ( S O V A ) 38 4.1.1 Symbol-based SOVA 39 4.1.2 Bit-based SOVA 40 4.2 Decoding of the Concatenated Code 41 4.3 FER. Analysis for Decoding of the Concatenated Code 43 4.4 Performance of Concatenated B P S K / B P P M 45 4.4.1 FER, Using Symbol-wise Decoding Metric 46 4.4.2 F E R Using Bit-wise Decoding Metric 47 4.4.3 Improved Decoding Scheme with Symbol-based SOVA 50 4.4.4 Improved Decoding Scheme with Bit-based SOVA 53 5 Non-Coherent B P P M Detection 57 •5.1 Non-Coherent Detection 57 5.2 B E R Analysis of Non-Coherent B P P M 59 5.3 F E R Analysis of Non-Coherent B P P M with RS-Decoding 60 v 5.4 B E R and F E R for Coherent B P P M Detection 60 5.5 Results and Discussion 61 6 Conclusions and Future Work 64 6.1 Conclusion 64 6.2 Recommendations on Future Works 65 Bibliography 67 vi List of Figures 1.1 FCC limits for indoor UWB emission, source: www.fcc.gov 3 2.1 Block diagram of the transmitter 8 2.2 Block diagram of the systematic convolutional rate-1/2 code 9 2.3 The symbol structure of a UWB signal. Durations are for mandatory trans-mission mode of IEEE 802.15.4a with pulse repetition frequency of 15.44 MHz. 11 2.4 The linear feed back shift register structure of scrambler 12 2.5 Block diagram of the considered receiver 14 3.1 Trellis of the convolutional code 18 3.2 Trellis of the convolutional codeword 21 3.3 Two error events with respect to the all-zero codeword. The error events involve the same set of B P S K / B P P M symbols, but in a different order. . . . 24 3.4 Illustration of dominant error events 25 3.5 B E R for decoding with symbol-wise and bit-wise metrics. Average over 100 CM2 channels and A R A K E combining. Lines: Analytical results. Markers: Simulation results 32 3.6 BER for S R A K E combining with Ls = 12 and Ls = 24 fingers. BER for A R A K E as reference. Decoding with symbol-wise metrics. Average over 100 CM2 channels. Lines: Analytical results. Markers: Simulation results. . . . 33 3.7 SNR(ARAKE)—SNR(SRAKE) (in dB) required for a BER of 10"4 for S R A K E combining with different Ls. Decoding with symbol-wise metrics. Average over 100 CM2 channels. Analytical results 34 v i i 3.8 BER(p) [Eq.(3.16)] for ten different trellis positions p. One CM2 channel realization and A R A K E combining. Decoding with symbol-wise metrics. . . 35 3.9 Simulated BER for A R A K E combining with and without time-varying scram-bler for symbol-wise metric 36 4.1 Effect of number of paths on calculated FER in Symbol-wise decoding metric. Lines: Analytical results. Markers: Simulation results 47 4.2 FER for A R A K E combining for 3 channels. Lines: Analytical results. Mark-ers: Simulation results 48 4.3 FER and F E R C C for A R A K E combining for single channel realization. Lines: Analytical results. Markers: Simulation results 48 4.4 Effect of number of paths on calculated FER, in Bit-wise decoding metric. Lines: Analytical results. Markers: Simulation results 49 4.5 F E R with A R A K E combining for symbol-wise and bit-wise decoding metrics for one channel realization. Lines: Analytical results. Markers: Simulation results 50 4.6 Probability of correct decoding for reliability information in the range 0 to f for symbol-based SOVA 51 4.7 Probability of correct decoding for reliability information in the range 0.9 to f for symbol-based SOVA 52 4.8 F E R vs EJJNQ for the iterative erasures-and-errors decoding with a maximum of e erasures. Symbol-based SOVA. One channel realization 52 4.9 FER vs -E/;/A'"o for the non-iterative erasures-and-errors decoding with e era-sures. Symbol-based SOVA. One channel realization 53 4.10 FER vs Eb/N0 for the iterative erasures-and-errors decoding with a maximum of e erasures, bit-based SOVA. One channel realization 54 4.11 FER vs Eij/No for the non-iterative erasures-and-errors decoding with e era-sures. Symbol-based SOVA. One channel realization 55 viii 4.12 F E R vs Eb/Nr, for the iterative erasures-and-errors decoding with a maximum of e erasures. Dotted: symbol-based SOVA. dashed: bit-based SOVA. One channel realization 55 4.13 FER vs Eb/No for the non-iterative erasures-and-errors decoding with e era-sures. Dotted: symbol-based SOVA. dashed: bit-based SOVA. One channel realization 56 5.1 B E R for non-coherent and coherent detection with R A K E receivers with Ls = 33 fingers 62 5.2 FER for non-coherent and coherent detection with R A K E receivers with Ls = 33 fingers 63 5.3 SNR required at B E R = fO" 2 for S R A K E receiver with SLC combining with different Ls 63 i x List of Abbreviations Acronyms A R A K E A l l R A K E Combining A W G N Additive White Gaussian Noise B E R Bit-Error Rate B M A Berlekamp-Massey Algorithm B P P M Binary Pulse Position Modulation B P S K Binary Phase-Shift Keying C M Channel Model C R C Cyclic Redundancy Check CSS Chirp Spread Spectrum F C C Federal Communications Commission F E C Forward Error Correction F E R Frame-Error Rate G F Galois Field G P R Ground Penetrating Radar I R - U W B Impulse Radio Ultra-wideband L F S R Linear Feed-back Shift Register L L R Log-Likelihood Ratio M A C Medium Access Control M L Maximum Likelihood M R C Maximal-Ratio Combining P E P Pairwise Error Probability pdf Probability Density Function RFID Radio-Frequency Identification R R C Root Raised Cosine RS Reed-Solomon SER Symbol-Error Rate SLC .Square-Law Combining SNR Signal-to-Noise Ratio SOVA Soft Output Viterbi Algorithm S R A K E Selective R A K E Combining T G Task Group U W B Ultra-wideband V A Viterbi Algorithm W P A N Wireless Personal Area Network XI Acknowledgments Undoubtedly, the completion of this thesis came from the support of many individuals. I would like to convey my gratitude first and foremost to my supervisor Professor Lutz Lampe for his invaluable guidance and continuous support. Professor Lampe provided much of the initial motivation for pursuing this investigation and also provided priceless feedback that has improved this work in nearly every aspect. I would also like to thank my parents who ha.ve always encouraged me in my quest for higher education and especially my husband Hani for his persistent support. Finally. I would like to extend my thanks to the colleagues at the Department of Electrical and Computer Engineering. U B C , for creating a stimulating and a friendly environment at work. Z A H R A A H M A D I A N The University of British Columbia Vancouver. Canada September 2007 xn Chapter 1 Introduction The ultra-wideband (UWB) technology, which is based on transmission of short dura-tion pulses with very high bandwidth, has recently shown its excellent potential as a suitable alternative for many wireless communication scenarios. Besides the applica-tion for data communication in wireless personal area networks (WPAN) . the small, inexpensive and low power structure of U W B transceivers makes them an excellent candidate for wireless sensor networks [1] and radio frequency identification (RFID). The very wide frequency spectrum of U W B signals gives them high penetration ca-pabilities which is useful in the UWB-based ground-penetrating radars (GPR). The G P R under investigation, can be used by disaster recovery teams for under rubble and through-wall detection [2], Furthermore, the fine time-delay in U W B signals allows accurate ranging and positioning for inventory control and asset management. In ad-dition to the above mentioned applications, U W B has medical applications in both medical imaging in the form of detecting respiratory and cardiac functions as well as body area networks. 1 1.1 Background and Motivation The earliest records of the use of U W B signals goes back to 1901 when Guglielmo Marconi transmitted Morse code sequences across the Atlantic. Approximately fifty years later, modern U W B radio was born by the introduction of impulse radio radars by Ross and Benneth [3] and Ha.rmuth [4]. From the 1960s to the 1990s, this technol-ogy ,was restricted to military applications. It was not until February 2002 that the US Federal Communications Commission (FCC) approved the use of U W B for data communications as well as radar and imaging applications under strict power emission limits [5]. U W B signals are defined as the signal with bandwidth of greater than 500 MHz or with a fractional bandwidth larger than 0.2 at all times of transmission. The F C C rulings ha,ve allocated the frequency spectrum from 3.1 GHz to 10.6 GHz to U W B communication. However, the maximum power available to a transmitter over the 7.5 GHz bandwidth is only 0.5 mW. Figure 1.1 shows the F C C emission mask for indoor U W B systems. U W B systems for data communication are typically divided into two classes: U W B systems for high data-rate transmission (above 100 Mbps) and U W B systems for low data-rate transmission (typically below 1 Mbps). The standardization of high data-rate U W B transmission was considered by the I E E E 802.15.3a task group, which however disbanded due to unsolvable disputes between two industry groups. The standardization of the low data-rate option has successfully been completed un-der the auspices of the I E E E 802.15.4a task group. This task group was formed to amend the previous I E E E 802.15.4 standard for low-rate W P A N s in March 2004 and terminated its work in June 2007 upon successful approval of the I E E E 802.15.4a standard. The standard supports three independent bands of operation below 1 GHz, which is a single channel. (249.6 - 749.6 MHz), the low-band consisting of four channels 9 — Indoor Limit Part 15 Limit 10' [GHz] > Figure 1.1: FCC limits for indoor UWB emission, source: www.fcc.gov. between 3.1 GHz and 4.8 GHz. arid the high-band which consists of eleven channels be-tween 6.0. GHz and 10.6 GHz. The modulation format is combined binary phase shift keying (BPSK) and binary pulse position modulation (BPPM) which is denoted as B P S K / B P P M in the following. The forward error correction (FEC) is a concatenated coding scheme with an outer systematic Reed-Solomon (RS) and inner systematic con-volutional code. The use of systematic codes allows detection of the transmitted bits without decoding and this utilizes non-coherent detection of the transmitted B P P M bit through energy detection which is explicitly envisioned in the standard. Similar to other proposals time-hopping and spreading are performed for spectral smoothing and multi-user interference rejection. The spreading sequence is a time-varying pseudo-random binary sequence generated by a linear feedback shift register (LFSR) of length 15. In addition to U W B , the standard supports optional chirp spread spectrum (CSS) at 2.450 MHz to support long-range links and links to mobile devices moving at higher speeds [6]. The low power, low complexity and low cost of U W B transceivers com--40 N I D Q C -45 -50 « -55 w o -60 E -65 U J Q . DC -70 LU CO 5 "75 _3 -80 10 Frequer 3 plying with this standard make them very attractive for most of the above mentioned low-rate applications such as wireless sensor networks. The particular coding and modulation scheme prescribed by the I E E E 802.15.4a stan-dard is rather unique. It is therefore interesting to investigate optimum and sub-optimum decoding for I E E E 802.15.4a systems. Furthermore, the performance eval-uation for such (and other) coded U W B systems is extremely time consuming, since simulations need to be repeated for many, say 100, different transmission channels generated according to the I E E E 802.15.4a model. Hence, analytical expressions for the error-rate performance of these U W B systems are highly desirable. Therefore, in this work we investigate the decoding for the I E E E 802.15.4a transmission system, and derive semi-analytical expressions for the bit-error rate (BER) and frame-error rate (FER) of these systems and present performance comparisons for different receiver structures. 1.2 Contributions The main contributions of the present research work are as follows: • We propose an optimal symbol-wise decoding metric for Viterbi decoding of the convolutional code, which outperforms the bit-wise decoding metric suggested .in [7]. • We derive semi-analytical expressions for the B E R performance of the convo-lutional coded BPSK/BPPiVI transmission, for both symbol-wise and bit-wise decoding metrics, taking into account the effect of the time-varying spreading. • We derive semi-analytical expressions for the F E R of the concatenated coding system according to the I E E E 802.15.4a standard. 4 • Based on the evaluation of the derived expressions and complemented by sim-ulation results, we compare the performances of Viterbi decoding with bit- and symbol-wise metrics and quantify the effect of R A K E combining with a finite number of fingers. • We devise the use of soft-output Viterbi decoding to take advantage of the erasures-and-errors decoding capability of the outer RS decoder. A n iterative and a non-iterative decoding scheme are suggested and the performance gains over convolutional decoding are studied through simulation results. • Finally, we investigate the non-coherent reception of the U W B B P P M signal as envisioned in the I E E E 802.15.4a standard and derive analytical results for the B E R before and the F E R after RS decoder. Overall, this thesis provides a comprehensive investigation and analysis of the decoding for the I E E E 802.15.4a standard with novel schemes for improved decoding and new expressions for quick performance analysis. 1.3 Thesis Organization This thesis is organized as follows: In Chapter 2, the U W B system model is presented. The I E E E 802.15.4a transmission system blocks together with the U W B channel model are explained. Chapter 3 presents the two decoding metrics for Viterbi decoding of the convolutional coded B P S K / B P P M . Expressions for the B E R for both decoding metrics are derived using a modified truncated union bound approach. Chapter 4 considers the entire concatenated coded B P S K / B P P M transmission system according to I E E E 802.15.4a standard. Two soft output Viterbi algorithms (SOVAs) are introduced and decoding of the concatenated code using reliability information from the inner code is investigated. The performance of the concatenated coded system is then analyzed and frame error rate (FER) approximations are provided. Chapter 5 introduces the non-coherent detection of the B P P M U W B signal. An-alytical results on coherent and non-coherent detection are given and performance comparison for the two schemes is presented. Finally, this thesis is summarized in Chapter 6 and possible future work is suggested. 6 Chapter 2 U W B System M o d e l In this chapter, the overall I E E E 802.15.4a transmission system, including transmitter, forward error correction, symbol structure, channel model and receiver structure are discussed. Section 2.1 provides the details of the transmitter, forward error correc-tion scheme and transmission pulse shape, as specified in the I E E E 802.154a standard. • Section 2.2 describes the communication channel model as developed for U W B trans-mission by the task group TG4a. The receiver structure is described in Section 2.3. 2.1 Transmitter The I E E E 802.15.4a transmitter is shown in Fig. 2.1. It consists of four main blocks: forward error correction encoder, modulator, time hopping/spreading sequence gener-ator and pulse shaping filter. Each of these blocks will be explained in the following sub-sections. 7 Systematic Reed-Solomon Encoder, (63. 55) Figure 2.1: Block diagram of the transmitter. 2.1.1 Channel Coding The I E E E 802.15.4a standard specifies a concatenated forward error correction cod-ing. The concatenated coding consists of an outer systematic Reed-Solomon rate-55/63 (RS) and an inner systematic rate-1/2 convolutional encoder. There is no interleaving between the two constituent encoders. Systematic RS encoder: RS-codes are a member of polynomial codes and are based on polynomial arithmetic. The specified systematic rate-55/63 RS code is formed over 7 the Galois field GF(2 6 ) with generator polynomial g(x) = YI (x + a ' f c) a n d primitive fc=0 binary polynomial p(x) = x6 + x + 1. The primitive binary polynomial has a root a such that p(a) = 0. The term "systematic" means that the original information sequence is part of the generated codeword. Thus, the 8 parity RS symbols are ap-pended at the beginning of the information sequence to form the RS codeword. The encoding process is performed by processing the information polynomial (m(x)) with the generator polynomial (g{x)) as follows c(x) = xn~h m(x) + [xn-k m(x) mod g{x)} , (2.1) where, c(x) is the generated RS-codeword, xn~k m(x) represents cyclic shift by k positions and xn~k m(x) mod g(x) represents the remainder of the polynomial division m(x)/g(.?;). The RS encoder accepts 330 data bits. If fewer than 330 data bits are available, the remaining bits will be zero-padded. Then the bits will be converted into 8 Systematic Convolutional Encoder. R,. = i /2 BPPM Modulator Position Bit Sign Bit BPSK Modulator Time Hopping and Spreading Sequences Root Raise Cosine Pulse Shaping Position Bit Delay Delay Sign Bit F i g u r e 2.2: B l o c k d i ag ram of the systematic convolu t iona l rate-1/2 code. 55 RS-symbols defined over GF(2 6 ) . i.e. m = 6 bits form one RS symbol. Next, the 8 parity RS symbols will be appended at the beginning of the codeword. The RS codeword is then converted into 378 bits, which are forwarded to the convolutional encoder. Systemat ic convolut ional encoder: The inner code is a rate-1/2 convolutional code with constraint length K = 3. The encoder is a four-state machine as shown in Fig. 2.2. with a memory of I = 2 and a pair of systematic and non-systematic code bits at the output. The constraint length K = I + 1 is the number of input bits that affect one output bit. The generator vectors of the two bits are defined as: gx = [0 1 0] and g2 = [101]. In the encoding process, the systematic position bit is obtained by-multiplying the input bit and the contents of the two shift registers with q\, i.e. it is the delayed input bit. The non-systematic sign bit is similarly obtained by multiplying the input bit and the contents of the two shift registers with g2- More details on Reed-Solomon and convolutional codes can be found in [8. 9. 10, 11] The modulation is a combination of binary pulse-position modulation (BPPM) and binary phase shift keying (BPSK) . which is referred to as B P S K / B P P M in the follow-ing. The B P P M maps the value of the bit to pre-defined positions within the transmit 2.1.2 M o d u l a t o r 9 signal. The systematic code bit of the convolutional encoder is the input to the B P P M modulator and represents the position hit. The B P S K modulation chooses the polarity of the transmitted signal based on the input bit. The non-systematic code bit is the input to the B P S K modulator and represents the sign bit. The combination of B P P M / B P S K is advantageous in both complexity and performance of the system. The B P P M modulated signal is detectable by both coherent and non-coherent receivers, where a non-coherent receiver does not require channel estimation at the receiver. The systematic code bit is modulated into the position of the pulse and since, the non-coherent receiver can recover the original data without the need for complex channel estimation. In case of a coherent receiver, which assumes reliable channel estimation, detection of both sign and position bits is accomplished by means of Viterbi decoding algorithm that improves the performance by correcting and recovering the transmitted bits prior to forwarding them to the RS-decoder. It is worth noting that the use of B P P M signaling reduces the periodicity of the transmitted signal and therefore is effective in spectrum smoothing. 2.1.3 B P S K / B P P M Symbol Structure The B P S K / B P P M symbols are transmitted as bursts of N pulses or chips with pulse shape gc{t). Each pulse is multiplied with a coefficient Q £ {±1} of a time-varying binary spreading sequence. In addition, each burst is time-hopped among pre-defined hopping positions. Figure 2.3 shows schematically, the structure and timing of such a symbol for the mandatory transmission mode with pulse repetition frequency of 15.44 MHz. The spreading sequences are the N consecutive outputs of a scrambler. The scrambler is a pseudo-random binary sequence generator that is defined by a linear feedback shift register of length 15 with period 2 l 0 — 1 as. shown in Fig. 2.4. The generator polyno-10 P P M D e l a y A m 5 1 2 P o s s i b l e B u r s t P o s i t i o n s G u a r d T i m e ^ 256ns P o s s i b l e B u r s t P o s i t i o n s G u a r d T i m e 1. i / \ ^ S y m b o l D u r a t i o n Ts 1 0 2 4 - a s II I - I II i 1 ThurSt = N T c « 3 2 n « Figure 2.3: The s y m b o l structure of a UWB signal. Durations are for mandatory transmis-sion mode of IEEE 802.15.4a with pulse repetition frequency of 15.44 MHz. mial of this linear feedback shift register is: g(x) = 1 + x14 + a;10. Using the spreading sequence results in spectral smoothing as well as interference suppression in multiple user scenarios. Multi-user interference rejection is improved by time hopping the posi-tion of the burst. The time hopping position is obtained from the linear feedback shift register as: d,k = Sj 2° + s 7 _ i 2' + s,-_2 2 2 . with Sj being the current state of the shift register (see Fig. 2.4). Overall, the transmit signal can be written as oo s(t) = £ akPk(t - k:Ts - bkA) , (2.2) k= — oo where ak € {±1} and bk G {0 ; 1} are the kth B P S K and B P P M data symbols respec-tively, Ts is the symbol interval. A is the P P M delay and pk(t) is a burst of N chips. Denoting the chip interval by Tc. the burst signal is given by N - l pk(t) = ckN+lgc(t - ITC - dkNTc) . (2.3) Throughout this work, we consider the mandatory transmission mode with a data rate of 851 kbps, where T c « 2 ns and T s = 512TC « 1 us. Since A = Ts/2 is true for all modes, we have A = 512 ns for the mandatory mode. The two mandatory pulse repetition frequencies are 15.44-MHz and 3.90 MHz. for which N = 16. dk € 11 S.; 5.7-1 D S 7 - 2 D D Hopp ing Posi t ion Address S 7 - 3 S 7 - 4 S 7 - I 3 S 7 - H Scrambler Coeff icients D 1 + s , 7 - i o D Figure 2.4: The linear feed back shift register structure of scrambler. { 0 . 1 , . . . . 7} and N — 4. dk G {0 ; 1.... , 31}. respectively. Taking into account the time hopping, this leaves a guard time of 128TC « 256 ns between the two P P M positions to account for channel delay spread. The chip pulse gc(t) is constrained by its normalized cross-correlation with a root raised cosine (RRC) pulse gv(t) with a roll-off factor B = 0.6. The normalized cross-correlation is given by $(1 f gr(t + T) gc(t) dt (2.4) VE0,E9c where. E(Jr and Egc are the energies of the gr(t) and gc(t) pulses respectively. For the mandatory transmission mode., the standard specifies the main-lobe width Tw = 2 ns for the transmission pulse gc(t). A transmitter compliant with standard should have a transmitted pulse that has |(I?(r)| > 0.8 in the main lobe and |$(r) | > 0.3 for each of the. side lobes. Assuming the set of points r,: for % = 1, 2, • • • as the points at which ^ l ^ > ( T ) l = 0; t n e maximum of function (r, n a a ;) occurs at one ofthe r,; points. Therefore, the restriction requires |<E>(r)| > 0.8 for the duration Tw and | $ ( T J ) | < 0.3 for all T{ [6]. For simplicity, in the following it is assumed that gc(t) is an R R C pulse with B — 0.6. 12 2.2 Channel M o d e l The transmission environment affects a U W B signal in a. different way, compared to a narrow-band signal. Modeling the transmission channel is based on calculating and measuring the statistical parameters of the channel. The I E E E 802.15.4a channel model adopted in this work was developed by the TG4a task group for both indoor and outdoor environments. The final report and a M A T L A B program to generate the channel impulse responses was released in November 2004 [12]. The aforementioned channel model is based on the Saleh-Valenzuela model with some modifications to account for the properties of the measured U W B channels. The im-pulse response of the multi-path channel consists of L c clusters of L r rays and can be expressed in the complex baseband as follows: u /.,• h(t) = £XAME~J 2* / C ( T'+ T M ) ( J(* ~ T < - T M ) , (2-5) /=0 A:=0 where akj is the tap weight of the kth component in the Ith cluster, TJ is the delay of the Ith cluster. T u is the delay of the kUl multi-path component relative to the Ith cluster arrival time Tj and fc is the baseband transformation frequency. The statistics of these parameters are specified in eight channel models (CMs) according to different environ-ments which are categorized as: residential, indoor office, outdoor and industrial. In generating the channel realizations using M A T L A B program, the parameters of each environment are given to the program and based on the statistical characteristics, the multi-path components of the channel are generated. Some of the parameters to be specified are cluster arrival times, cluster decay rates and the multi-path component arrival times within a cluster which is modeled as a Poisson random variable or mixture of two Poisson processes. More details on statistical characteristics of the channel can be found in [13] and [12]. 13 r(t) S R A K E Viterbi 1 R S Decoder j Decoder ! estimated data Figure 2.5: Block diagram of the considered receiver. 2.3 Receiver The block diagram of the receiver is shown in Fig. 2.2, where the received signal is r(t) = s(t) * h(t) + n(t) (2.6) where n(t) is the white Gaussian noise process and (*) denotes the convolution. The R A K E receiver front-end is commonly used for detection in I R - U W B systems [14, 15, 16]. The operation of a. R A K E receiver is based on collecting the signal energy from Ls different multi-path components of the signal and combining them to make a decision on the transmitted data. We assume that noise reduction is accomplished by the use of chii>matched filtering with g*(—t) and that the R A K E fingers are spaced by integer multiples of the chip interval Tc [15]. In case of coherent detection, the R A K E receiver requires knowledge of both amplitude and phase of the multi-path channel gain coefficients. The received samples from the fingers corresponding to the Ls strongest resolvable paths are optimally combined using maximal-ratio combining (MRC) . If Ls equals the total number of the resolvable paths, this combiner is referred to as all R A K E ( A R A K E ) , otherwise it is referred to as selective R A K E ( S R A K E ) [15]. Note that due to the large guard time of about 256 ns, it can be safely assumed that no interference occurs between the two P P M positions and between different symbols, i.e. orthogonal B P P M and intersymbol-interference-free B P S K / B P P M is assumed. In case of non-coherent detection, the S R A K E carr be used with square-law combining (SLC) [16] to capture the signal energy in each of the two P P M positions and no 14 information about amplitude and pha.se of the channel coefficients is required. The output of the R A K E front-end is passed to the Viterbi decoder. Viterbi and RS decoding are discussed in detail in Chapters 3 and 5 assuming coherent R A K E detection. Non-coherent detection and decoding is studied in Chapter 5. 15 Chapter 3 Convolutional Coded B P S K / B P P M In this chapter, we consider and analyze the convolutional-coded B P S K / B P P M trans-mission part of the I E E E 802.15.4a standard. For this purpose. Section 3.1 defines an equivalent channel model which is used in Section 3.2 to describe the decoding met-rics. We will introduce two methods to define the decoding branch metrics based on maximum likelihood (ML) and an approximate M L decoding. The Viterbi decoding algorithm using these branch metrics is briefly reviewed in Section 3.3. Next, a de-tailed bit-error rate (BER) analysis is performed for both M L and approximate M L decoding in Section 3.4. The obtained expressions are evaluated and discussed together with B E R simulations in Section 3.5. While the expressions and results derived in this chapter are interesting in its own right, they will be useful when considering the overall concatenated coding scheme in Chapter 4. Throughout this chapter and Chapter 4. we assume perfect channel information being available at the receiver. 16 3.1 Equivalent Channel Model It is convenient to derive a simplified, equivalent channel model for B P S K / B P P M transmission as described in Chapter 2. To this end, we note two outputs corresponding to the two B P P M positions are generated per bit interval. Then, it readily follows that the channel between B P S K / B P P M modulation and the S R A K E outputs for one bit interval can be represented by the real-valued two-dimensional vector model as follows: fh - "ks'l: • nh . (3.1) where rk is the two-dimensional S R A K E output vector, nk is the two-dimensional additive white Gaussian noise (AWGN) vector and the vectors s ° = [\/F\-0]T and si = [0 \ / ^ ] 7 represent the B P P M data bit. The noise has a variance a\ = JVQ/2 per dimension, where J\fQ denotes the two-sided power spectral density of the complex-baseband noise process. The normalized effective channel energy can be defined as 2 E Pk(t) * h(t) * gc(-t)\ P k = - — m — r w \ ~ • ( 3 - 2 ) 9c(t) * £ 7 c ( - i ) | t = 0 where ti are the sampling instances and (*) denotes convolution operation. Note that, due to the time-varying spreading sequence, Pk depends on the symbol-time index k. 3.2 Decoding Metrics In this section, we devise two methods of decoding using the Viterbi algorithm [8]. The first method is based on a maximum likelihood (ML) decoding approach employing symbol-wise branch metrics. The second method is an approximate M L decoding that uses bit-wise branch metrics in the form of log-likelihood ratios. The reason to consider the latter is that (i) it was suggested during the standardization in [7] and (ii) bit-wise 17 Sign B i t ^ V^Position Bit Figure 3.1: Trellis of the convolutional code. metrics are often applied when convolutional coded linear (e.g. Q A M ) modulations axe considered. 3.2.1 Symbol-wise Metr ic Considering the equivalent channel model in Eq.(3.1). the maximum log-likelihood metric \k(a, b) associated with a hypothetical B P S K symbol a and a hypothetical B P P M symbol b at time k readily follows as Xk(a, b) = a • rlsbk , a G {±1} , b G {0 ; 1} , (3.3) where we have exploited the fact that ||aSfc|| 2 = Pk and || 'a ; | | 2 are independent of the transmitted a and b. Considering the particular mapping of the encoder outputs to B P S K and B P P M sig-nal elements and the equivalent data vectors aksbkk in Eq.(3.1). Fig. 3.1 shows the corresponding trellis diagram with the branches labeled with these vectors. 18 3.2.2 Bit-wise Metr ic The second decoding metric definition which is referred to as bit-wise branch metric was described in the standardization document [7]. It is in the form of log-likelihood ratios (LLRs). The L L P , for the B P S K bit is given by /-4 = l o g = log / P r K = - l } ' \ ,Pr{a f c = + l } , P{n\s°k) + p(rk\sk) Mn\-a°k) + p(rk\-sk) / e H l n - - s < > | | 2 / ( 2 ^ ) + e - | | r„- a j f . | | 2 / (2o-= i ) \ l0g [(r\\r,+s»\\y(2al) + e-\\rk+sl\\y(2a'i) J ' (3'4) where p(rk\sbk) denotes the probability density function (pdf) of rk given sbk. The L L R for the B P P M bit is given by = log /Pr{b f c = 0}' p(rk\s°k) + p(rk\ - si) P{rk\slk) + p(rk\ - s£), e-\\rk-4\e/(2a?,) + e - | | r „ + s g | | V ( 2 o - ? ) ' e - l ! n - 4 l l 2 / ( 2 ^ ) + e - | | n - + 4 i r - / ( 2 C T ? , ) (3.5) To simplify the bulky expressions for /.i,'k and v'k, one can apply the nearest-neighbor (or "max-log") approximation log(eQ + e1') = max(a. b) + log(l + e ( _ | a _ 6 | ) ) « max (a, b) and the simplified bit-wise metrics become ,,k = max (\\rl - s°f ., \\rTk - a\f) - max (\\rTk + 8°k\\* , | | r [ + 4l| 2) = rlsl + rlsl, (3.6) and vk = max (\\rl - s°kf , \\vTk + s°kf) - max (\\rTk - slf , \\rTk + sif) = \rlsl\-\rl4\. (3.7) 19 The bit-wise decoding metric can readily be defined as sum of two L L R s as follows A f c(a,6) - ^ y % f c + ( l - & K , (3.8) where the L L R s are added only for zero sign and position bits. The defined approximate M L decoding metrics provide simple and direct soft deci-sions on the sign and position bits separately. However, as it will be shown in the simulation and analytical results in Section 3.5, the bit-wise metric shows considerable performance loss compared to the optimum symbol-wise decoding metric. 3.3 Vi terbi Decoding Algori thm The Viterbi decoding algorithm provides an efficient method for M L decoding of a sequence. Following the standard specifications [6], we assume that the encoder starts at all-zero sta/te and returns to all-zero state at the end of the transmitted codeword, i.e. the codeword is padded by two zeros. Fig. 3.2 shows the complete trellis of the inner convolutional codeword of length c. The solid lines represent a transmitted information bit of 0 and dashed lines, a 1. For an arbitrary codeword of length c, the decoding starts by calculating the branch metrics along the trellis starting at time k = 1, where the two possible paths diverge from the all-zero state. The decoder uses the previously defined metrics in Section 3.2 to calculate the two possible branch metrics arriving at nodes 0 and 2. These two paths diverge into four different paths at time k = 2. From this point forward, there are two paths arriving at each state node and eight possible path metrics are calculated. The decoder has to decide upon the four survivor paths at the four state nodes and discard the other four paths. The decision is made in favor of the path with the maximum accumulated path metric. The path metric at time index k and state node i is defined in terms of the branch metrics A' as k. A* = X > K a t , M - (3-9) 20 At each step, the path metric for two arbitrary paths A arid B arriving at a state node is updated according to the following equation: A* ^ ^ ( A ^ + A ^ A ^ + A^) . (3.10) At time k = c — 1, the four survivor paths merge into two paths and only one path with the maximum accumulated path metric is selected as the survivor path arriving at the state node 0 at time k = c. The Viterbi algorithm was implemented for both symbol-wise and bit-wise decoding metrics. 3.4 B E R Analysis for Convolutional Code Decod-ing It is desirable to obtain analytical B E R results for coded I R - U W B transmission to avoid the inefficiency of simulations in terms of computational complexity, resources and time. This is particularly pronounced for U W B transmission, as simulations have to be repeated for many different channel realizations to obtain statistically significant results. In this section, we derive analytical results for both symbol-wise.and bit-wise decoding metrics. The analytical results axe obtained in the form of modified truncated union bounds in both cases. 3.4.1 B E R Analysis for Symbol-wise Decoding Metr ic The classical method to analyze the error rate of convolutionally coded transmission with Viterbi decoding is to apply the union bound over codeword pairwise error prob-abilities (PEP) together with the extended path enumerator of the encoder [8. Ch. 4]. Due to the linearity of the code and since each trellis branch corresponds to one B P S K / B P P M symbol, the error probability is the same for all possible codewords. Hence it suffices to assume that the all-zero word c 0 . i.e.. a sequence of (+s° ) sym-bols, was transmitted. Considering the symbol-wise metric Xk(a,b) in Eq.(3.3) and the equivalent A W G N channel model in Eq.(3.1). the P E P with respect to any alternative codeword can be calculated by combining the three possible error probabilities which result from incorrect decoding of (+s° —> — s°k, +s\, —si). In the following we calculate each one of these probabilities and then combine them to obtain P E P for codewords. For the error (s° —» — s°k) we find where Q(-) is the Gaussian Q-function. Similarly the probability of error for the trans-s°k) = Pr{rk-sl<rk-(-sl)} = P r{2 | | s 0 J 2 + 2 s ° f c - n f c < 0 } (3.11) mitted s° decoded as s 1 is given by si) Pr{r f c • si < rk • «; [ = Pr{\\sl\\2 - (s°k - si) • nk < 0} (3.12) Since s ° and s\ are orthogonal. \\s°k — si 1 112 _ II „ 0 . 0 1 1 2 Therefore Pe(s°k si. -si and the probability of error in the position bit follows as (3.13) Next, using equations (3.11) and (3.13). the P E P with respect to an alternative code-word Ci, i > 0, representing a single error event starting at k = p and terminating at k — q + 1 and corresponding to q — p + 1 B P S K / B P P M symbols (avsbp . . . aqSq), can be formulated as Pe(c0 Q E k=P \al-ak8bt\\*/{tol) (3-14) Furthermore, since (i) aksk -s°k only for k = p and k = q (see Fig. 3.1), (ii) , 0 1 1 2 ,1 112 Pk, and (iii) si. 1 112 l ^ + 4 l l 2 2Pk, this expression s i m p l i to Pe(CQ Ci = (7-1 "p + A fc=P+l 2al (3.15) If P f c was a constant, i.e., Pk = P . the P E P in Eq.(3.15) would only be a function of the Hamming weight dUa of the position bits of c» and given by Q(sJ(2 + dH ;i/2)P/<x 2). However, because of the time variance of Pk due to the time-varying spreading se-quences, the P E P depends on the positions of the bits in which c 0 and c , differ. Fig. 3.3 illustrates this for the two error events [—s°. — sp+1, sp+2-, —sp+:i, s ° + 4 : sp+5, — sp+6] and Q0 (3 1 Q 0 Q 1 Q 1 Q 1 ~*p> °p+l> °p+2' °p+3'°p+4> °p+5 ,0 1 ,p+61' which only differ in the order of B P S K / -23 all-zero code word error events Figure 3.3: Two error events with respect to the all-zero codeword. The error events involve the same set of B P S K / B P P M symbols, but in a different order. B P P M symbols. For the same reason, the P E P also depends on the starting position p of the error event. Hence, the union bound based on the extended path enumerator of the encoder is not applicable to the coded B P S K / B P P M system considered here. Therefore, a different approach is chosen. First, in the calculation of P E P only dominant error events that include dSl < L symbols (±sj.) . are considered. Figure 3.4 shows these error events for dSl = 1 (left) and dSl = 2 (right). Second, the truncated union bound is calculated for the B E R using these error events and assuming a given starting position p. L BER(p) = J 2 J 1 dM<* - Ci) , (3.16) dSl =1 i\dSl ,p where, the second sum is over all codewords C ; . such that the error event starts at a time p and traverses along dSl symbols (±sj.). The time varying scrambling sequences result in a different bit error probability at each starting position p. Therefore, the effect of different scrambling sequences is 24 Figure 3.4: Illustration of dominant error events, accounted for by an average BER, which is obtained as 2 1 5 - 1 B E R = 2 T T = 1 E B E R ^ ) > ( 3- 1 7) where 2 l 0 — 1 is the period of the linear feedback shift register of length 15 which is used for generation of spreading sequences. It will be seen in Section 3.5, that the calculated a.verage B E R obtained from Eq.(3.17) coincides well with the simulated B E R . 3.4.2 B E R Analysis for Bit-wise Decoding Metr ic Similar to the symbol-wise decoding metric the probability that the transmitted s° is incorrectly decoded can be found by forming the difference metric in terms of L L R s (see the L L R expressions in equations (3.6) and (3.7)). The results can be combined to obtain the P E P of the transmitted all-zero codeword with respect to any alternative codeword. 25 The individual error probabilities are given by P e ( s ° - - s 0 ) = P i ' K + "fc < "fc} = Pr{Mfc < 0} , P e ( s 0 - + S l ) = Pr{Atfc + ^ < M = P r W < 0 } , (3.18) Pe(s°^-Sl) = Pr{/ i f c + /A ; < 0} . combining the above probabilities, the probability of error for a codeword Cj deviating from c 0 at k — p and merging at k = q + 1 with g — p + 1 B P S K / B P P M symbols (cipSp" . • . aqsbq) along the detour is given by P e ( c 0 -» C i ) = Pr ^ («fc - 1) 2 / ' t - - bkisk >0} . (3.19) Unlike the case of decoding with symbol-wise metrics (see Eq.(3.14)), there is no closed-form solution to the P E P expression in (3.19). We therefore provide a numeri-cally efficient approach to evaluate (3.19) for the dominant error events. In the following, the probability of error for the shortest error event, which is shown in Fig. 3.4 (left side), is calculated to illustrate the proposed procedure. The accumulated metric difference for this error event is = —Pp — Vp+\ — f-lp+2 = — (rpsp 4- rpSp) — ( | r p + 1 s ° + 1 | — \rp+1sp+^ |) — {rp+2sp+2 + rp+2sp+2) = -\K\\2 - (sl)Tnp - (sl)Tnp - | | | S ° + 1 | | 2 + (s°p+l)Tnp+1 \ + \(s1p+1)Tnp+1\- | | s ° + 2 | | 2 - (s°p+2)Tnp+2 - {slp+2)Tnp+2 = A'p;i + \NPi2\ - |A<^|-, (3.20) where NpA, Npo. and Np:i are real-valued Gaussian random variables NP,i = - N p l l 2 - ( 4 ) 7 ^ P - ( 4 ) 7 - ( ^ ° + 2 ) 7 - ( 4 + 2 ) ^ ^ p + 2 , (3.21) Np,2 = | ( 4 + 1 ) T n p + 1 | ; (3.22) NPt3 = I ll*p+il|2 + ( s ° + i ) T n P + i I • (3-23) 26 with mean values. mN„A mNv.2 mN„,3 o ; Pp+l 1 (3.24) and variances. a 9 o-l(2Pp + 2P1 P+2) • A ' , , . : an.Po+l (3.25) The P E P for this error event is Pr{Ap > 0}. which can be expressed as C O c + j o o Pr{A, > 0} = j pAl,(:i:)dx = ~ J ^ ^ d s , (3.26) 0 c—joo where PAP{%) is the probability density function (pdf) of AP, <E>Ap(S) is the Laplace transform of PA,XX)-, a n d c < 0 lies in the region of convergence of $ A p ( s ) . Since NPA. Np:2- and A'-.^ are independent random variables, $>AP(S) is given by the product of the Laplace transforms of the pdfs of NPA. \NP2\-, and — |A ' P .3| $ A „ ( S ) = * N P 1 1 ( S ) * | J V P , 2 | ( S ) * ( - | J V P , 3 | ) ( S ) • (3.27) Using the expressions for the pdfs of Gaussian. Rayleigh, and Ricean distributed ran-dom variables [17]. the Laplace transforms on the right-hand side of (3.27) are quickly found as _r / \ sm.y ,-\-S~cr\, 1 $ | N P l 2 | ( s ) = 2e~Np*a~12 Q{soNp * ( - | J V p , - l ) W , O 9 g 'V-i A p : 3 + e 2rs /2 S O " sa A ' J»,3 ;J,3 V 3 (3.28) (3.29) (3.30) (3.31) 27 where the Q-function is defined for complex-valued arguments and is related to the error function through erf (a;) = 1 — 2Q(\/r2x) [18]. While a closed-form solution of the integral (3.26) cannot be obtained for $ A p ( s ) in equations (3.27) with (3.28)-(3.31). efficient numerical integration based on Gauss-Chebyshev quadratures is possible [19, 18] and Pr{Ap > 0} is approximated as P r { A p > 0 } « - E { K [ « % ( c + J C T f c ) ] + T , , ; 9 [ # A p ( c + j C T f c ) ] } , (3.32) where Tk = tan[(2/,-; — l)ir/(2K)}. and K is the number of nodes at which the function is evaluated. A value of K equal to 200 was found to yield satisfactory results. (The approximation can be made arbitrary precise by increasing K.) The P E P for other error events involving symbols —8% and s\. for various k can be obtained similarly, since the corresponding Laplace transform $ i s a product of the transforms in equations (3.28)-(3.31). If the error event also traverses along a branch corresponding to —sp+i, for example for one of the error events on the right-hand side of Fig. 3.4 for % = 1 and i = 2. the procedure is slightly different. In the following we calculate the probability of error for the error event of length four with dSi = 2 (see Fig.3.4). The accumulated metric difference for this error event can be written as A p = —f-lp — LLp+l — Vv+i — f.lp+2 — Vp+2 — /-tp+3 {' pbp ^ ' pbp) I ' p + l V l ^ ' p+l°p+lj (3.33) _ ( l r p + l S ° + l l ~ \rp+1Sl+l\) ~ ( r p + 2 S ; ° + 2 + rp+2SP+2) ~~ (\rl+2Sp+2\ " \rl+2sl+2\) ~ ( r p + 3 S p + 3 + rp+:lsp+:i) • In the above, two independent random variables NpA = -\PP+l + < + i a ° + i | - (Pp+i + nf)+ls°p+l) (3.34) and ^P:» = l^l+iSp+il - nTp+ls\+l (3.35) 28 occur along with (some of) the other distance terms Np,\, l A ^ I , — \Np.:i\ in the metric difference Ap. Denoting u(-) as the unit-step function. A ^ . 4 and Np.s can be written as NpA = -2{Pp+l + nl+lsl+l)u(Pp+l + nTp+lsl+l) , (3.36) NPt5 = - 2 < + i a , 1 , + i u ( - « + i S 1 + i ) ) . (3.37) The Laplace transforms of the pdfs of Np,4 and Np,5 are obtained as = e 2 P ^ 1 + - » ) g ^ ( l + 2 ^ ) ^ ^ j + Q ^ ^ j , (3.38) and *N,„M = ( 2 s V ^ ! ) + \ , (3-39) respectively, thus the PEPs for the error events involving —sp+i can also be numerically evaluated using (3.32): The PEPs for the L dominant error events are used in the truncated union bound (3.16) and the individual BER, approximations are averaged with respect to the spreading sequences according to (3.17). 3 . 5 B E R N u m e r i c a l a n d S i m u l a t e d R e s u l t s In this section we present the numerical and simulated results for both decoding metrics to show the good convergence of approximations which are a valuable tool for quick performance evaluation. In addition we compare the performance of the two decoding metrics. For both analysis and simulation, we have used the U W B impulse responses defined in Section 2.2 according to the I E E E 802.15.4a channel model generated by the M A T L A B code provided in [12]. As an interesting example, Channel Model 2 (CM2) is assumed, which represents residential non-line-of-sight environments. The average 29 signal-to-noise ratio (SNR) for each channel is given by After chip-matched filtering S R A K E combining is applied by selecting the Ls strongest paths, assuming perfect channel estimation. If all paths are selected, i.e., Ls equals the number of all resolvable paths, S R A K E combining becomes A R A K E combining. 3.5.1 B E R Performance for Symbol-wise and Bit-wise Decod-ing Metrics In this section, we compare the B E R performances for convolutional B P S K / B P P M de-coding with symbol-wise and bit-wise metrics, using A R A K E and S R A K E combining. For this purpose we evaluate the B E R expressions derived in Section 3.4 and present the results together with the simulated BERs . For numerical B E R evaluations we include L — 15 dominant error events when consid-ering symbol-wise metrics and L = 4 dominant error events for decoding with bit-wise metrics. The smaller number in the latter case is motivated by the fact that the con-tributions from PEPs for longer error events to the union bound diminish very quickly for decoding with bit-wise metrics. Figure 3.5 compares the average B E R performances of the coded B P S K / B P P M , being decoded with symbol-wise and bit-wise metrics over 100 channel realizations. Both analytical and simulation results are shown, and A R A K E combining is performed. It can be seen that the analytical (lines) and simulated (markers) B E R curves match very well and thus corroborate the validity of the B E R approximations developed in Section 3.4. It is worth pointing out that while the B E R simulation takes approximately 4-5 hours per channel realization for reaching a. B E R « 10~°. the analytical results, for example, for the symbol-wise decoding metric are obtained in less than a, minute per . 30 channel realization for the same number of Ei,/NQ points. Thereby, the amount of time consumed for simulation results increases dramatically with lower target BERs, where as the calculation time of the analytical results is independent of the E\,/N0 and thus of the target B E R . We further observe that the use of bit-wise metrics incurs a considerable loss in power efficiency of. for example. 2.2 dB at a B E R of 10~4, which increases for lower target error rates. It should be noted that decoding with symbol-wise metrics requires about the same computational complexity as decoding with bit-wise metrics that is two cor-relations and addition of eight branch metrics per B P S K / B P P M symbol are required (see equations (3.3), (3.6) and (3.7)). Therefore, we conclude that symbol-wise metrics should be applied rather than bit-wise metrics suggested in [7]. 3.5.2 R A K E Receiver Next, we investigate the effect of S R A K E combining with a, fixed number Ls of fingers. Figure 3.6 shows the analytical (lines) and simulated (markers) B E R results for S R A K E combining with Ls — 12 and Ls = 24 fingers. As a reference, the results for A R A K E combining are included. Once again, the analytical approximations and the simulation results match very well. We observe that S R A K E with Ls = 24 achieves a performance very close to that of A R A K E , while degradations of about 1-2 dB occur for Ls = 12. This performance penalty due to S R A K E combining is made more explicit in Fig. 3.7. where the difference in SNR between A R A K E and S R A K E combining for a target B E R of 10~4 is plotted as a function of Ls. While with only Ls — 5 fingers the A R A K E performance is approached within about 2 dB, rather large Ls (> 20) are needed to make the performance loss incurred by S R A K E combining disappear. We note, however, that CM2 models a residential non-line-of-sight environment with relatively many multi-path components and that other environments [13] may be less demanding 31 2 Eb/N() [dB] Figure 3.5: BER for decoding with symbol-wise and bit-wise metrics. Average over 100 C M 2 channels and A R A K E combining. Lines: Analytical results. Markers: Simulation results. in terms of the required number of R A K E fingers. 3.5.3 Effect of Time-varying Scrambling Sequence The effect of time-varying spreading sequences on the B E R is illustrated in Fig. 3.8 for one CM2 channel realization and A R A K E combining. The ten B E R curves correspond to BER(p) (see Eq.(3.16)) for ten different, rather arbitrarily chosen trellis positions p — 2. 7.12.. . . ,47. Apparently, the variation of the effective channel energy Pk due to different spreading sequences are quite significant, since the "local" error rates BER(p) range over several orders of magnitude. Hence, this effect must not be neglected for 10' E„/N() [dB] Figure 3.6: BER for S R A K E combining with Ls = 12 and Ls = 24 fingers. B E R for A R A K E as reference. Decoding with symbol-wise metrics. Average over 100 CM2 channels. Lines: Analytical results. Markers: Simulation results. performance evaluation, whether simulative or analytical. In considering the effect of the scrambling sequence, it is interesting to look at the sys-tem performance without scrambler. For this purpose, we fix the scrambler coefficients to Ci — —1. Figure 3.9 shows the simulated B E R with disabled scramble in comparison to the normal scrambled operation for symbol-wise decoding metric, a performance degradation of approximately 0.6 dB is evident. It should be noted that we have not considered the multi-user interference in this work. We expect that in a multi-user scenario the performance gain due to scrambling is considerably larger. 33 10 15 2 0 2 5 3 0 Figure 3.7: SNR(ARAKE)-SNR(SRAKE) (in dB) required for a B E R of fO" 4 for S R A K E combining with different Ls. Decoding with symbol-wise metrics. Average over fOO CM2 channels. Analytical results. 34 10' 2 3 4 5 6 7 8 Eb/NQ [dB] Figure 3.8: BER(p) [Eq.(3.16)] for ten different trellis positions p. One CM2 channel real-ization and A R A K E combining. Decoding with symbol-wise metrics. 35 Figure 3.9: Simulated B E R for A R A K E combining with and without time-varying scrambler for symbol-wise metric. 36 Chapter 4 Concatenated Coded B P S K / B P P M In this chapter, we consider the decoding and analysis of the concatenated B P S K / B P P M scheme specified for the I E E E 802.15.4a standard as described in Chapter 2. Since the early introduction of concatenated coding schemes by Forney [20], combinations of two error correcting codes have been vastly used in communication systems from space application to data transfer and multimedia to improve error correction capability of the system [10]. In order to improve the performance of concatenated systems of inner convolutional and outer RS codes, the passing of reliability information from the inner decoder to the outer one and iterations between them have been considered in [21. 22]. The outer RS decoder can use the reliability information to perform erasures-and-errors decoding, which improves the error-correction capability if indeed errors of the inner decoder are transformed into erasures. In this context, it is desirable to align the re-liability output from the inner decoder with the boundaries of the RS symbols [21]. As for the iterative decoding, it is typically assumed that the convolutional and RS codes are connected through an interleave!' and that the corresponding de-interleaving at the receiver side distributes error bursts from the inner decoder over multiple RS codewords [21, 22]. This is unfortunately not the case in the standardized U W B sys-37 tern. Considering the above, we propose an improved decoding procedure that uses the soft-outputs generated by a modified Viterbi Algorithm (VA). Two modified Viterbi decoders with soft output reliability information are described in Section 4.1. The en-tire decoding scheme using inner code soft output reliability information is presented in Section 4.2. Based on the BER, analysis of the inner convolutional code in Chapter 3, we derive analytical results for the frame error rate (FER) performance of the entire concatenated coding scheme in Section 4.3. The analytical and simulation results are presented and discussed in Section 4.4. 4.1 Soft Output Viterbi Algori thm (SOVA) The V A as the optimum decoder for convolutional codes accepts soft decisions from the channel and generates hard output data. For decoding a concatenated code with inner convolutional code, a so-called soft output Viterbi algorithm (SOVA) is necessary. The SOVA generates soft output, i.e.. reliability information, for the decoded bits, along with hard decoding decision. There are several versions of the SOVA which have been introduced in the literature, e.g. [23, 24, 25]. Since the quality of soft outputs is directly related to decoding performance of RS erasures-and-errors decoding following the SOVA. we compare two methods of generating soft output, which mainly differ in the way the reliability output from the inner decoder is aligned with the boundaries of the RS symbols. The first one is adopted from the work by Huber and Riippel [23] which directly matches the reliability information to the sequence of RS-symbols. The second method is based on work by Hagenauer and Holier [24] and generates bit-based soft outputs, which are then mapped to RS-symbols reliabilities in a separate, sub-optimum step. The two SOVAs are briefly described in the following two sections. It should be noted that both SOVA implementations in the following sections and the results presented in Section 4.4. use the symbol-wise decoding metric and the terms 38 symbol-based and bit-based only refer to the two different SOVAs. 4.1.1 Symbol-based SOVA The symbol-based SOVA devised in [23] calculates the probability of error based on the difference in the metric of the two paths merging at every state node and updates these probabilities for the RS symbol to which the bit information belongs. The hard decision Viterbi decoding procedure stays intact but the symbol-wise metric for which we implement the SOVA, needs to be modified. Considering the equivalent A W G N channel model from Eq.(3.1). the log-likelihood probability is obtained as log (p(rk\a,b)) = J K : - a 4 l l 2 + l Q g (J_ • B r . l l ' - ^ I ^ + I K I I ' _ a2n ' "° \iro? The reliability difference measure only depends on (2/cr.2) arj.sk. Therefore, the pre-viously defined symbol-wise metric notation is multiplied by the factor 2/er*. In the following we consider the modified decoding steps for two survivor paths, A and B, merging to produce a. new path C at time k. Without loss of generality, we assume that A is the survivor path when C is produced. Denoting Ak as the partial path metric ending in trellis state X and A ^ 1 ' as the branch metric for the branch from X to Y at epoch k, the decoder will select the path with maximum accumulated metric, A. as survivor and the reliability difference is calculated as A ^ = | A ^ + A f - ( A f + A f c ) | . (4.2) The probability that the decision for path .4 over path B was correct is Pk = 1 , c , (4-3) where pk varies between 0.5, if Ajj? « 0, and 1, for large values of Ajj?. Furthermore, we introduce the vectors dk = [d£'[0], d%[1],..., d£>] ] and Pkx = [Pkx{0], P A V [1 ] , . . . , P,^{K}} 39 which contain the K = \k/m~\ RS symbols associated with the partial path to state X and their reliability after decoding until time k, respectively. If k is not a multiple of m, then dk [K] represents a partial RS symbol. When two paths A and B merge to produce the new path C, where we assume that A is the survivor, the reliability vector Pk+i is updated as [23] Pf \l] = ) M J l k iii/ 0 < 1 < K . (4.4) Note that P^[re] is initialized by 1 at the beginning of the symbol. 4.1.2 Bit-based S O V A The bit-based SOVA was introduced in [24]. Considering the two paths defined in Section 4.1.1 and the reliability difference, A^' , defined in Eq.(4.2), the probability of selecting the wrong survivor path is tk =1-P% = 7T-Zc , (4-5) 1 + e^k where pk approaches 0.5 if A ^ « 0 and 0 if L\f. 2> 1. The pk is introduced to keep the equations consistent with [24]. Under the assumption that path A has been selected, the Viterbi decoder has made errors with probability p% in all the eh po-sitions where the information bits of path B differ from path A. The two vectors 4 = [ ^ [ 0 ] : ^ [ 1 ] ; . . . ; ^ [ A ; ] ] and />* = [P* [0], P?[l),. . ., P^k]} are defined differ-ently now as the decoded binary information bits and the probability of previous erro-neous decisions with the path to state X up to decoding instant k. The probabilities of erroneous decisions are updated according to [24] i Pk I'] • ( 1 " P?) + ( 1 - Pk M) • P? , if dt [l] ± d? [I] p C m = ) v . 0 < I < k . (4.6) PM], iid£[l] = d%[t\ 4 0 where Pk\l) varies in the range 0 < Pk[l] < 0.5 and Pk\l] « 0 represents a highly reliably decoding decision arid vise versa. The vector Pk is initialized as zero for all the four survivor paths propagating through the trellis at the beginning of the decoding process. The generated soft-output values belong to information bits and they are mapped to RS symbols by selecting the maximum bit reliability within a symbol as the symbol reliability [10]. The two SOVAs differ in the way the reliability information are updated as well as the mapping of reliability information to bits. 4.2 Decoding of the Concatenated Code We now turn to the decoding of the concatenated code, using the SOVA as inner decoder. Note that the conventional V A is a. special case of the SOVA, if the extra reliability information is ignored by the RS decoder. The hard decoded bits from the SOVA are converted into symbols to be fed to the RS decoder. Each RS symbol represents in = 6 binary symbols. The maximum error correcting capability of the RS code is t — |_(f/,„in — 1)/2J = 4 RS-symbols for an error only decoding scheme, where ^min — 9 is the minimum distance of the RS code. In addition to error decoding, the RS decoder can perform erasures-arid-errors decoding when the location of some errors are known. Denoting the number of declared erasures as e, the error correcting capability of the code is changed to [(dm-m — 1 — e)/2j. Therefore, every two declared erasure positions reduce the number of correctable unknown errors by one. On the other hand, if erasure declared error-positions correspond to actual error positions, then the error correcting capability is improved at most twice. Among several different algorithms for decoding RS codes, the Berlekamp-JVIassey A l -gorithm (BMA) [26] is the most widely used. The B M A is an iterative decoding 41 algorithm that computes the error-syndrome polynomial and then iteratively searches for the minimum linear feed-back shift register (LFSR) polynomial that can reproduce the error-syndrome polynomial. The roots of the LFSR, polynomial are equal to the inverses of error locations. For details about the BIVIA we refer to [11]. In this work, we have both implemented the B M A for RS decoding, and have as well considered the FER. simulation by counting the number of symbol errors after SOVA decoding: If this number exceeded [Wnin — 1 — e)/2j, a frame error was declared. Based on the soft output of the SOVA decoder, the e RS-symbols with the lowest probabilities in symbol-based SOVA and highest probabilities in bit-based SOVA, are declared as erasures and the RS decoder applies erasures-and-errors decoding. Since the choice of e is critical, we suggest to perform several decoding attempts with the RS decoder for different even numbers of erasures e, 0 < e < dmm — 1 = 8. until the correct information sequence is found. For the (63,55)-R,S code the probabilities of decoding error can be defined as the probabilities that an incorrect codeword is decoded if more than [rf"""~:~e j RS-symbol errors occur after Viterbi decoding and considering the erasures. These probabilities are 0.03. 0.14, 0.46. 0.97 and 1.00 for e equal to 0,2.4.6 and 8. respectively [27]. Thus we cannot rely on error-only detection by the R,S decoder. Instead we assume that the cyclic redundancy check (CRC) code applied to the data, stream at the medium access control layer (MAC) can be utilized for this task. We further note that, unlike the systems considered in [21, 22], feedback from the RS decoder output to the Viterbi decoder cannot improve the performance due to the absence of interleaving between the convolutional and RS encoders. 42 4.3 F E R Analysis for Decoding of the Concatenated Code In this section, we present analytical expressions for the F E R of the concatenated coded scheme. For analytical tractability, we assume only error decoding, i.e., no reliability information is exploited by the RS decoder. The error-rate analysis for concatenated convolutional and RS coded systems is typi-cally based on the symbol-error rate (SER), that is the probability of at least one error in a sequence of rn consecutive bits, at the output of the Viterbi decoder assuming (ideal) symbol de-interleaving before RS decoding [28], or the use of a Markov chain to model the errors produced by Viterbi decoding and finite de-interlea,ving [29]. Since the considered concatenated coded system does not employ an interleave!', the bit and consequently symbol errors are no longer independent. Therefore error-gap distribu-tion measures can not be used for calculation of the SER. On the other hand, given the relatively simple trellis-structure of the convolutional code, a different approach can be used to analyze Viterbi and RS decoding jointly. To this end, as in Section 3.4, the analysis is restricted to the dominant error events of the Viterbi decoding. Furthermore, a simplifying assumption is made such that the error events do not extend over more than two adjacent RS symbols. This procedure can be extended further to include more error events affecting more than 2?rt bits. In spite of the simplifying assumption, the calculated F E R gives a close match with the performance of the simulated system. Hence, it is reasonable to keep the assumption and reduce the number of calculations. Wi th this assumption, it suffices to distinguish the two cases that an error event falls completely within an RS code symbol and that it extends over two adjacent RS symbols, which are referred to as single-symbol errors and double-acljacent-symbol errors, respectively. 43 Denoting the RS symbol time-index by K, and considering, as in Section 3.4. an error event cx starting at k = nm + p. 0 < p < m. and terminating at k — nm + q + 1. which corresponds to q — p+ 1 B P S K / B P P M symbols, the probability of single-symbol errors can be upper bounded by SER 1 («) = Y Y E F * ( c ° ~* c ' ) > ( 4 J ) p=0 dH=l i:dH.K,n+P, where the inner sum is such that the error event starts at time nm + p. traverses along dSi symbols {±#1), and is not longer than m symbol intervals. The pairwise error event probability is the same as the results obtained in Section 3. Likewise, the probability for double-adjacent-symbol errors can be upper bounded by m—1 L S E R 2 ( K ) = YI P ^ C o c ^ ' (48) p=0 dSi=l , K . m + ; i . I I I<( ;<2? ; I For the purpose of F E R calculation, all combinations of e-\ single- and e2 double-adjacent-symbol errors with e\ + 2e2 > t would need to be considered for all e^i"e2 j possible positions within the R.S codeword, which is clearly infeasible. Here n is the length of the RS codeword and is equal to 63. Also the effect of time-varying spreading sequence has to be taken into account. Therefore, averages of SERj(«;) and S E R 2 ( K ; ) are calculated first with respect to K and then the F E R is determined based on the averaged single- and double-adjacent-symbol error probabilities. In doing so, the time-varying spreading is taken into account for calculating the symbol-error probabilities, but its effect on the probability of multiple symbol errors is neglected. Since the period of the spreading sequence with respect to RS symbols is 2 1 5 — 1, the average symbol-error probability becomes: 2 1 5 — 1 S E R , = Y SER„ ( / c ) , v = 1, 2 . (4.9) The RS decoder can correct up to t symbol errors, which could result from single- and 44 double-adjacent symbol errors. The probability of having j double-adjacent-symbol errors and up to t — 2j single-symbol errors can be formulated as PeJ = [ 1 ) (SER2)>'(1 - S E R 2 ) " ~ 1 " ^ £ (") ( S E R O X l - S E R ^ ' 1 " 1 . (4.10) \ '•) / 1 = 0 1 Since t = 4 for the (63,55)-RS code, the F E R is finally obtained as 2 F E R = 1 - P e j (4.11) :l=o We note that the F E R calculation is possible for both symbol-wise and bit-wise decod-ing metrics. As a special case of Eqs.(4.10) and (4.11). we can calculate the F E R at the output of Viterbi decoder. Since, the probability of correct decoding is the probability of having no single- and no double-adjacent symbol error, the F E R at the output of the Viterbi decoder is given by F E R C C = 1 - P e,0| t=o = 1 - [(1 - S E R 2 ) n _ 1 (1 - SERi ) n ] . (4.12) 4.4 Performance of Concatenated B P S K / B P P M In this section, we evaluate the F E R expression derived above and compare the re-sults with F E R simulations. Furthermore, we present the results for error-and-erasures decoding, making use of the reliability information from the different SOVA implemen-tations. 45 4.4.1 F E R Using Symbol-wise Decoding Metr ic The analytical results were calculated using the probabilities of the L dominant errors previously obtained in Section 3.4.1 in Eqs.(4.7) and (4.8). The effect of the number of error events on the accuracy of the analytical results can be observed in Fig. 4.1 for the symbol-wise decoding metric using L — 4, 7,15 dominant error events. It is shown that use of L = 15 error events results in close match with simulation. Figure 4.2 shows the analytical and simulation results for three different channel realizations, A R A K E combining is assumed. We observe the very good match between analytical and simulation results (note the scaling on the x-axis). A n even earlier (at lower £ b/A'" 0) convergence of analytical and simulated curves is obtained for higher performance channels. The time required to obtain simulation results for the eight E},/NQ points with F E R > 10~4 using symbol-wise decoding metric was approximately 24 hours per channel realization while the calculated analytical results were still obtained in less than a minute. The simulation time extends to more than 24 hours for a single Eb/l\0 at F E R < 1 0 - 4 . This motivates use of analytical approximations over simulation. Figure 4.3 compares the F E R at the output of the Viterbi decoder in the first decoding stage and the F E R resulting from the second stage RS-decoder. The calculated F E R at the output of Viterbi decoder in Eq.(4.12) is validated by observing the close match between the simulated and analytical results. The error correction capability of the RS-decoder provides a performance gain of approximately 2 dB at F E R = 10 _ 1 , which increases for lower FERs . The analytical average F E R over 100 channels are shown for both convolutional and RS decoder. We note that obtaining simulation results for 100 channel realizations would require more than 100 days if the simulations were run serially for the 100 channels, this is totally infeasible in terms of resources, and therefore we can not show the simulation results for this case. Instead, we use the analytical results to calculate the average F E R over 100 channels in less than an hour. The average F E R over 100 channels is very close to the single channel realization result 46 I U ;]; s Simulation L = 4paths 10" 6 L= 7 paths • • L = 15 paths 1 0-'L , , , , , 1 2 2.5 3 3.5 4 4.5 5 E b /N 0 [dB] > Figure 4.1: Effect of number of paths on calculated FER in Symbol-wise decoding metric. Lines: Analytical results. Markers: Simulation results. that is because the F E R curves for the 100 channel realizations are very similar. 4.4.2 F E R Using Bit-wise Decoding Metr ic Similar to the results presented for symbol-wise decoding metric, the analytical results are calculated using the probabilities of the L dominant errors previously obtained in Section 3.4.2 in Eqs.(4.7) and (4.8). Figure 4.4 shows the effect of number of error events for L = 4, 7,15 using bit-wise decoding metric. It is shown that using the probabilities of error for 15 error events produces results that match very well with the simulation. Including a. higher number of error events in the calculation provides more accurate result at the cost of higher calculation complexity. This is significantly important in bit-wise decoding metric, since analytical calculations involve enumeration of complex 47 « Ch=1 Simulation • Ch=70 Simulation A Ch=92 Simulation Ch=1 Analytical Ch=70 Analytical Ch=92 Analytical E h ' N . [dB] Figure 4.2: F E R for A R A K E combining for 3 channels. Lines: Analytical results. Markers: Simulation results. E b / N 0 [dB] > Figure 4.3: FER and F E R C C for A R A K E combining for single channel realization. Lines: Analytical results. Markers: Simulation results. 48 io" 4 f - -,0-=l , 1 i ; i i . 2 2 . 5 3 3 . 5 4 4.5 5 5 . 5 E b / N 0 [ d B ] ^ F i g u r e 4.4: Effect of n u m b e r of paths o n calculated F E R i n B i t - w i s e d e c o d i n g metr ic . L ines: A n a l y t i c a l results. M a r k e r s : S i m u l a t i o n results. v a l u e d Q - f u n c t i o n a r i d n u m e r i c a l i n t e g r a t i o n . F i g u r e 4.5. c o m p a r e s t h e F E R p e r f o r m a n c e s of t h e c o n c a t e n a t e d c o d e d B P S K / B P P M . b e i n g d e c o d e d w i t h s y m b o l - w i s e a n d b i t - w i s e d e c o d i n g m e t r i c s for o n e c h a n n e l r e a l i z a -t i o n . B o t h a n a l y t i c a l ( l ines) a r i d s i m u l a t i o n ( m a r k e r s ) are s h o w n . A g a i n , s i m i l a r to t h e B E R r e s u l t s p r e s e n t e d i n S e c t i o n 3.5.1. i t is o b s e r v e d t h a t t h e use of b i t - w i s e m e t r i c s i n c u r s a. c o n s i d e r a b l e loss i n p o w e r ef f ic iency of. e.g. 1.7 d B a t B E R of 1 0 - 2 . S i n c e t h e V i t e r b i d e c o d i n g p r o c e d u r e s for t h e t w o d e c o d i n g m e t r i c s i n v o l v e s a m e n u m b e r of c a l c u l a t i o n s , c o n s i d e r i n g t h e B E R r e s u l t s i n S e c t i o n 3.5.1 a n d F E R r e s u l t s i n F i g . 4.5, we c o n c l u d e t h a t s y m b o l - w i s e m e t r i c s s h o u l d be u s e d i n s t e a d of b i t - w i s e m e t r i c . 49 2 2.5 3 3.5 4 4.5 5 5.5 6 E b / N 0 f d B ] _ ^ Figure 4.5: F E R with A R A K E combining for symbol-wise and bit-wise decoding metrics for one channel realization. Lines: Analytical results. Markers: Simulation results. 4.4.3 Improved Decoding Scheme with Symbol-based S O V A Next, we present FER, results with erasures-and-errors RS decoding, which utilizes reliability information provided by the SOVA. In this section, we consider the symbol-based SOVA. introduced in Section 4.1.1. Since an analysis of erasures-and-errors decoding seems infeasible,' we resort to showing simulation results throughout this section. As mentioned before, the generation of reliability information requires the application of symbol-wise decoding metrics. First, it is insightful to consider whether the SOVA soft output represents a faithful reliability information. For this purpose, Fig. 4.6 shows the reliability information Pk defined in Section 4.1.1 versus the probability of correct decoding for the RS-symbol dk associated with Pk . In other words, the x-axis represents the value of the reliability information of RS-symbol dk estimated by SOVA and the y-axis represents the actually 50 O 0.7 a O 0.4 o X3 ra 0.2 .Q o 0.5 0.7 0.8 0.9 Figure 4.6: Probability of correct decoding for reliability information in the range 0 to 1 for symbol-based SOVA. measured reliability of the decoded symbol. Figure 4.7 shows P£ versus probability of correct decoding for the RS-symbol d:k in the range of 0.9 < Pkx < 1 with a higher resolution on the x-a,xis. The approximately linear relation (with slope 1) shows that the reliability information Pk estimated by the SOVA is almost identical to the actually measured reliability for RS-symbol dk . Next, we consider the F E R performance of erasures-and-errors RS decoding. Iterative erasures-and-errors decoding was suggested in Section 4.2. In this method, additional erasures are declared if there exist more errors after decoding with previously declared erasures. Figure 4.8 shows the simulated result of such scheme for a single channel realization. Based on the reliability of the generated soft output values, increasing the number of declared erasures e enhances the performance. This is the case even for e = 8 at which point, the decoder is an erasure-only RS decoder. The FER, at the output of the Viterbi decoder is shown for better comparison. 51 T J O O ) 1 0.99 0.98 0.97 0.96 0.95 0.94 0.93 0.92 0.91 0.9 0.89 0.88 * ** : / itf. * * "0.9 0.91 0.92 0.93 0.94 0.95 0.96 0.97 0.98 0.99 1 Figure 4.7: Probability of correct decoding for reliability information in the range 0.9 to 1 for symbol-based SOVA. Figure 4.8: FER vs E^/N® for the iterative erasures-and-errors decoding with a maximum of e erasures. Symbol-based SOVA. One channel realization. 10 1 ' ' 1 1 1 1 1 1 ? 2 2.2 2.4 2.6 2.8 3 3.2 3 4 3.6 E b / N 0 [ d B ] > Figure 4.9: FER vs Eb/No for the non-iterative erasures-ancl-errors decoding with e erasures. Symbol-based SOVA. One channel realization. When it is not possible to use the C R C code for error detection for iterative erasures-and-errors decoding, we suggest picking a fixed number of erasures that results in the best decoding performance in most of the cases. Figure 4.9 shows the simulated F E R for the non-iterative decoding scheme, in which a fixed number of erasures are declared for all frames. It can be observed that declaring two to four erasures can result in moderate gain. However, if more than four erasures are declared, the performance degrades again. This is due to the fact that, if the erased bits do not correspond to the actual errors, the overall error-correction capability of the RS-decoder is reduced. 4.4.4 Improved Decoding Scheme with Bit-based S O V A In this section, we consider erasures-and-errors decoding with the bit-based SOVA introduced in Section 4.1.2. Figures 4.10 and 4.11 show the F E R for iterative and 5 3 10-JI 1 1 1 1 ' 1 1 1 1 2 2.2 2.4 2,6 2.8 3 3.2 3.4 3.6 3.8 E b / N 0 [ d B ] > Figure 4.10: F E R vs Eb/No for the iterative erasures-and-errors decoding with a maximum of e erasures, bit-based SOVA. One channel realization. non-iterative erasures-and-errors decoding. Similar to the symbol-based SOVA. the performance gain increases with increasing number of declared erasures for iterative decoding. In the non-iterative decoding scheme, again similar to the symbol-based case, two and four declared erasures yield a performance improvement. Hence, we suggest declaring e = 4 erasures in cases where reliable error detection and therefore, iterative erasures-and-errors decoding is not possible. Finally, figures 4.12 and 4.13 compare the performances with the two SOVAs when declaring 2 and 8 erasures in iterative and non-iterative decoding, respectively. Perhaps surprisingly, we observe that the performance merit of using symbol-based soft outputs instead of bit-based soft output is quite insignificant. 54 Figure 4.11: FER vs EI,/NQ for the non-iterative erasures-and-errors decoding with e era-sures. Symbol-based SOVA. One channel realization. Figure 4.12: FER vs E^/NQ for the iterative erasures-and-errors decoding with a maximum of e erasures. Dotted: symbol-based SOVA. dashed: bit-based SOVA. One channel realization. 5 5 Figure 4.13: FER vs EiJNo for the non-iterative erasures-and-errors decoding with e era-sures. Dotted: symbol-based SOVA, dashed: bit-based SOVA. One channel realization. 56 C h a p t e r 5 N o n - C o h e r e n t B P P M D e t e c t i o n The I E E E 802.15.4a standard strongly emphasizes on simple transmitter and possible simple receiver structure with low complexity and low cost. In cases where complexity and cost do not allow implementing a reliable channel estimator, non-coherent detec-tion of the B P P M symbol can be performed. More specifically, since the convolutional encoder is systematic, the data can be recovered using a simple energy detector with subsequent RS decoding. Section 5.1 describes such a non-coherent detection of the B P P M I R - U W B signal using square-law R A K E combining. The B E R and F E R analy-sis for this detector are given in Sections 5.2 and 5.3, respectively. For completeness, the error-rate expansion for coherent detection is stated in Section 5.4. Finally, analytical and simulated performance results are presented and discussed in Section 5.5. 5.1 Non-Coherent Detection Non-coherent receivers are generally low cost and simple compared to the coherent receivers. However, non-coherent receivers exhibit a significant drop in performance compared to coherent receivers. A popular choice for non-coherent reception of B P P M 57 signals is energy detection through auto-correlation or R A K E receivers [16. 30]. In the auto-correlation method, the received signal is correlated with itself or a previously received one. This is often done based on the analog received signal. In case of non-coherent RAKE-based reception, the entire received signal is' not used for energy detection, but only samples at certain delays are considered. Since channel estimation required for optimal maximum-ratio combining is not available, suboptimal square-law combining (SLC) ; which does not require knowledge of the channel information, is often applied. In SLC the multi-path components of the received vector are squared and summed to form the decision variables for each of the two possible pulse positions. This form of energy detection is highly dependent on the tap selection. For simplicity, we assume that the taps corresponding to the Ls strongest resolvable paths are selected at the receiver, i.e., the receiver has some knowledge about the energy-delay profile of the channel. Assuming again the chip-matched filtering front-end introduced in Section 2.3, and defining Lt = Ts/Tc, the discrete time equivalent channel model r>- - 4 • nh : (5.1) results, where rk — [rk,\, rk,2, • • • , i'k,ii] is the vector of received samples at the output of R A K E receiver. nk = [nkA,nk,2, • • •,«*.z,J is the vector of noise samples with vari-ance cr2,. and s ° = [skA, skt2,.... sk tj_. 0 , . . . , 0] and sk = [0 , . . . , 0, sk.\, s k t 2 , s k L^] represent the B P P M data bits. The data bit samples axe given by pk(t) * h{t) * gc(t)\t=i Tc 9^ The SLC selects the Ls samples rk,i corresponding to the largest \sk,i\. Specifying the corresponding sample incidences by = 1,2, ••• ,LS, the SLC decision variable follows as ?:=i i = i 5 8 If dk > 0, the B P P M data bit is decided'as 0. and if dk < 0. the data bit is decided to be 1. 5.2 B E R Analysis of Non-Coherent B P P M In this section, we derive an analytic expression for the B E R at the output of the SLC. To this end ; without loss of generality, we assume that s°k was transmitted. The probability of error can be written as Pb = P r { 4 < 0} = P r J X > M W + n M ( i ) ) 2 - (nkMl))2 < 0 j , (5.4) The above equation can be easily mapped to a quadratic form of Gaussian random variables D = J^ A\Xi\2 + B\Yi\2 + CX.Y; + c*x;Yi, (5.5) n = l where A, B, and C are constants and Xi and Yi, are mutually independent. In mapping the two equations; A = 1. B = —1, C — 0, Xi = ?'A:;/(0 and Y\ — rk The solution of Eq.(5.4) for such quadratic form is given in [31, Appendix 9 A ] as Pb = l + ^ T T E C t - l ) [ Q l { a - b ) " Q ( ( M ] ' ( 5 ' 6 ) /E(sfr,«(.->)2 U n „ where a = 0, b = \ '-—^— and £ ( s u ( » ) ) = IKJI = pk in this case. The Marcum Q-function Qj(a. 6) for the special case of a = 0 can be written in series form as ^ ( 0 ^ X > p ( 4 ) < ^ . (,7, n=0 ^ ' By substituting Eq.(5 .7) in Eq. (5 .6) . the solution of the quadratic form in Eq.(5.4) can be written as i=i v b 71=0 59 (5.8) Since the normalized effective energy Pk is time-varying, the scrambling sequence has direct impact on Eq.(5.8), which is emphasized by writing Pb as a function of k. The average B E R is then given as 2 1 S - 1 1 A.—0 5.3 F E R Analysis of Non-Coherent B P P M with RS-Decoding In this section, we extend the analytical results obtained in Section 5.2 to calculate the F E R at the output of the RS-decoder. For the B P P M transmission, since the errors are independent, the SER can be written as a function of average bit error probability B E R , more specifically, the SER is the complement of probability of having no error in any of the m = 6 bits within an RS-symbol and is given by S E R - 1 - (1 - B E R ) 6 . (5.10) Since the RS-decoder can correct up to t = 4 symbol errors within a. frame, the proba-bility of frame error is calculated as a sum over probabilities of having more than t = 4 errors in a frame F E R = ] T f63\ SER' (1 - S E R ) 6 : j - 1 . (5.11) •i'=5 ^ 5.4 B E R and F E R for Coherent B P P M Detection For completeness, we state the B E R and F E R expressions for coherent B P P M detec-tion, i.e.. R A K E with M R C is applied. For M R C the decision variable is given by 4 = Ey rM(o sM(o ~ Yrk..^f+i{i)sm) • (5-12) i=i i = i 60 Therefore, assuming s°k is transmitted, the probability of error can be written as ™-«(JW)-Q{M)- (5I3) The SER for RS-symbols and the F E R with RS-decoding are again given by equa-tions^.10) and (5.11) substituting Pb{k) from Eq.(5.13). 5.5 Results and Discussion In this section we present analytical and simulation results for non-coherent B P P M detection and compare them with those for coherent detection. For the results, L( s) = 33 is assumed. Figure 5.1 shows the analytical and simulated B E R results. We observe an excellent match between the analytical arid simulated curves. This also justifies the suggested averaging over possible values of the effective normalized energy. Pk. As mentioned before, the absence of channel information can cause a significant perfor-mance degradation for the B P P M transmission considered here, a, loss of approximately 7 dB can be observed at B E R = 1 0 - 2 . Figure 5.3 shows the F E R at the output of the RS-decoder. Due to the error correcting capability of the RS-code, the frame error rate decreases with a steep slope after 14 dB in the non-coherent and after 7 dB in the coherent case. At F E R = 10~ 2. coherent receiver has a considerable performance gain of approximately 6 dB. The effect of number of fingers on performance of the R A K E receiver with square-law combining is explicitly shown in Fig. 5.2. The Eb/N0 at which the target B E R of 10~2 is obtained is plotted as a function of L s for one channel realization. As it can be seen, initially, increasing the number of fingers, the performance is improved and the target B E R is achieved at lower Eb/N0. However, at Ls R J 50 the performance starts 61 W d B ) Figure 5.1: B E R for non-coherent and coherent detection with R A K E receivers with Ls — 33 fingers. to degrade slightly. This is due to the fact that the effect of additional white Gaussian noise becomes dominant starting at L s « 50. The performance loss highly increases for Ls > 70. In conclusion, there are significant losses in power efficiency due to non-coherent decod-ing if channel information is not, available. Hence, obtaining channel state information is highly desirable for the U W B system under consideration. In addition, to fully benefit from the concatenated coding scheme applied to the data at the transmitter, channel state information is needed. 62 ' -... O Simulation N-Coh ::::: Analytical N-Coh o Simulation Coh Analytical Coh ' | I j | I 1 i I L_ 2 4 6 8 1 0 1 2 1 4 1 6 Eb/N0(dB) F i g u r e 5.2: F E R for non-coherent, and coherent detect ion w i t h R A K E receivers w i t h Ls fingers. 63 C h a p t e r 6 C o n c l u s i o n s a n d F u t u r e W o r k 6.1 Conclusion In this thesis we have investigated decoding for U W B transmission systems comply-ing with the I E E E 802.15.4a standard. The main contributions and results can be summarized as follows: • The probability of error for the convolutional coded B P S K / B P P M system for decoding with symbol-wise and bit-wise metrics, taking into account the time-varying spreading prescribed by the standard, has been analyzed. The presented numerical and simulation results have shown that (i) the B E R approximations are tight over a wide range of BER.S, (ii) decoding with symbol-wise metrics is clearly advantageous in terms of performance-complexity trade off over bit-wise metrics, and (iii) S R A K E combining with about 5-10 fingers is sufficient to approach the optimal performance within 1-2 dB for highly dispersive U W B transmission channels. • The performance of the concatenated coded B P S K / B P P M in the absence of 64 interleaving and the presence of time-varying spreading has been considered arid analytical results for FER, have been obtained. The analytically obtained F E R s closely match the simulated results, which renders the derived expressions highly valuable for quick performance evaluation. • Improved decoding schemes using erasures-and-errors decoding of the outer RS code have been suggested. The Viterbi decoding algorithm has been modified to produce soft output reliability values that are passed to the RS decoder for erasure declaration. Two different modified SOVA have been implemented, where one is based on assigning reliability information to RS-symbols arid the other to bits. By means of simulation results, it has been found that (i) the two SOVAs show approximately the same F E R (ii) using SOVA 0.4 dB gain can be obtained over the conventional decoding. • Non-coherent detection of the U W B B P P M signal without channel estimation using a R A K E receiver with square-law combining has been investigated and the corresponding bit and frame error probabilities have been analyzed. A Compar-ison of the coherent and non-coherent receivers has shown that a performance degradation of approximately 6 dB is incurred by the absence of channel infor-mation in non-coherent receivers. 6.2 Recommendations on Future Works We have investigated the performance of and have provided analytical tools for per-formance evaluation of the basic U W B system complying with the recently approved standard I E E E 802.15.4a. There are various extensions that could be considered. Per-haps most interestingly are • To study the effect of channel estimation errors on the system performance in case 65 of coherent decoding using R A K E receiver and M R C combining with practical channel estimation. The inclusion of multi-user interference and its effect on the system performance. 66 B i b l i o g r a p h y [1] A . Molisch, P. Orlik, Z. Sahinoglu, and J. Zhang, "UWB-based sensor networks and the I E E E 802.15.4a standard - a tutorial.'1 in Proc. of First International Conference on Communications and Networking in China, 2006, pp. 1-6. [2] H . Burchett, "Advances in through wall Radar for search, rescue and security ap-plications," in Proc. of The Institution of Engineering and Technology Conference on Crime and Security., 2006. pp. 511-525. [3] C. Bennett and G. Ross, 'Time-domain Electromagnetics and its Applications," Proc. of the IEEE, vol. 66, no. 3, pp. 299-318, 1978. [4] H . Harrnuth, Nonsinusoid/d Waves for Radar and Radio Communication. New York, N Y , USA: Academic Press, 1981. [5] M . - G . D. Benedetto, T. Kaiser, A . F. Molisch, I. Oppermann. C. Politano, and D. Porcino. UWB Communication Systems: A Comprehensive Overview. Hin-dawi, 2006. [6] I E E E P802.15.4a/D7, "Wireless Medium Access Control (MAC) and Physical Layer (PHY) Specifications for Low-Rate Wireless Personal Area Networks (LR-WPANs) : Ammendment to add alternate P H Y , " Jan. 2007. [7] G. M . Maggio, " IEEE 15-05-0707-01-004a TG4a U W B - P H Y overview," available . online at: lrcwww.epn.ch/uwb/mics/doc/2006/02/maggio_802-15-4a_overview.pdf, Nov. 2005. 67 [8] R. Johannesson and K . Zigangirov, -'Fundamentals of Convolutional Coding. I E E E Press, New York, 1999. [9] A . J. Viterbi, Principles of Digital Communication and Coding. McGraw Hil l , 1979. [10] S. B. Wicker arid V . K . Blmrgava, Reed-Solomon Codes and Their Application. I E E E Press, 1994. [11] R. H . Morelos-Zaragoza, The Art of Error Correcting Coding. 2nd ed. John Wiley, 2006. [12] A . F. Molisch, K . Balakrishnan, C.-C. Chong, S. Eniami, A . Fort, J. Karedal, J. Kunisch. H . Schantz, U . Schuster, and K . Siwiak, " IEEE 802.15.4a channel model - final report," Tech. Rep., 2005, document 802.1504-0662-0l-004a. [13] A . Molisch. D. Cassioli. C.-C. Chong, S. Emami. A . Fort, B. Kanhan. J . Karedal, J. Kunisch, H . Schantz. K . Siwiak, and M . Win , "A Comprehensive Standardized Model for Ultrawideband Propagation Channels," IEEE Trans. Antennas Propa-gat, vol. 54, no. 11, p p . 3151 - 3166, Nov. 2006. [14] M . Win and Z. Kostic. "Virtual path analysis of selective Rake receiver in dense multipath channels," IEEE Commun. Lett., vol. 3, no. 11, pp. 308 - 310, Nov. 1999. [15] D. Cassioli, M . Z. Win, F. Vatalaro, and A. F. Molisch, "Performance of Low-complexity Rake Reception in a Realistic U W B Channel," in Proc. of IEEE Int. Conf. Commun. (ICC), vol. 2, May 2002, pp. 763-767. [16] J. Choi and W. Stark. "Performance of Ultra-Wideband communications with suboptimal receivers in multipath channels," IEEE J. Select. Arms Commun., vol. 20, no. 9, pp. 1754 - 1766, Dec. 2002. 68 [17] M . Simon, Probability Distributions Involving Gaussian, Random Variables. Kluwer Academic Publishers, Boston, 2002. [18] M . Abramowitz and I. Stegun, Handbook of Mathematical Functions. New York: Dover Publications, 1972. [19] E. Biglieri, G. Caire, G. Taricco, and J. Ventura-Traveset, "Computing error prob-abilities over fading channels: a unified approach," European Transactions on Telecommun., vol. 9, no. 1. pp. 15 - 26, Jan./Feb. 1998. [20] G. D. Forney, Concatenated Codes. Cambridge, M.I.T. Press, 1966. [21] L . - N . Lee, '''Concatenated coding systems employing a unit-memory convolutional code and a byte-oriented decoding algorithm," IEEE Trans. Commun., vol. 25, no. 10, pp. 1064 - 1074, Oct. 1977. [22] J. Hagenauer, E . Offer, and L . Papke, "Matching Viterbi decoders and Reed-Solomon decoders in a concatenated system," in Reed-Solomon Codes and Their Applications. Edited by S.B. Wicker and V.K. Bhargava, I E E E Press, New York, 1994. [23] J. Huber and A. Riippel, "Reliability estimation for symbols detected by trellis decoders," (in German). International Journal of Electronics and Communication (AEU), vol. 44, pp. 8 - 21, Jan./Feb. 1990. [24] J. Hagenauer and P. Hoeher. "A Viterbi algorithm with soft-decision outputs and its applications," in Proc. of Global Telecommunications Conference. 1989, pp. 1680-1686 vol.3. [25] M . Fossorier, F. Burkert, S. Lin . and J. Hagenauer, "On the equivalence between SOVA and max-log-MAP decodings," IEEE Commun. Lett., vol. 2, no. 5, pp. 137-139, 1998. 69 [26] J. L . Massey, "Shift register synthesis and B C H decoding," IEEE Trans. Inform. Theory, vol. IT-15, no. 1, pp. 122-127, Jan 1969. [27] R. McEliece and L. Swanson, "On the decoder error probability for Reed-Solomon codes," IEEE Trans. Commun;, vol. 32, no. 5, pp. 701 - 703, Sept. 1986. [28] A . Lapidoth, "On the probability of symbol error in Viterbi decoders," IEEE Trans. Commun., vol. 45, no. 2, pp. 152 - 155, Feb. 1997. [29] C. Valadon, R. Tafazolli, and B. Evans, "Performance evaluation of concatenated codes with inner trellis codes and outer Reed-Solomon code." IEEE Trans. Com-mun.. vol. 49, no. 4, pp. 565 - 570, Apr. 2001. [30] X . Chu, J. Liu , and M . Ghavami, "Pulse-coded orthogonal P P M for non-coherent receivers in low-data-rate U W B communications," in Proc of IEEE 17th Interna-tiona,!, Symposium, on Personal, Indoor and Mobile Radio Communications, 2006, pp. 1-5. [31] M . K . Simon and M.-S. Alouini, Digital Communication Over Fading Channels: a unified, approach to performance analysis. New York, John Wiley & Sons, 2000. 70
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Performance analysis of IEEE 802.15.4a BPSK/BPPM UWB...
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
Performance analysis of IEEE 802.15.4a BPSK/BPPM UWB transmission Ahmadian, Zahra 2007
pdf
Notice for Google Chrome users:
If you are having trouble viewing or searching the PDF with Google Chrome, please download it here instead.
If you are having trouble viewing or searching the PDF with Google Chrome, please download it here instead.
Page Metadata
Item Metadata
Title | Performance analysis of IEEE 802.15.4a BPSK/BPPM UWB transmission |
Creator |
Ahmadian, Zahra |
Publisher | University of British Columbia |
Date Issued | 2007 |
Description | The ultra-wideband (UWB) technology has recently attracted considerable attention in industry and academia. This is due to the great potentials of the license exempt operation with UWB signals. These include high data. rate, low power consumption, robustness to multipath propagation, good penetration properties and the ability for accurate localization and ranging. The IEEE working group 802.15 set up two task groups (TGs) for the standardization of UWB physical layers for short-range communication: the IEEE T G 802.15.3a for high data-rate transmission which was officially formed in December 2007 and the IEEE TG 802.154a for low data-rate that became an official task group in March 2004. While the TG 802.15.3a did not succeed and was finally disbanded in January 2006; the TG 802.15.4a approved a draft standard in March 2007. This standard prescribes a rather unique coding and modulation scheme, namely the concatenation of an outer Reed-Solomon and an inner convolutional encoder with a mixed binary phase-shift keying and pulse position modulation (BPSK/BPPM) and time-varying spreading and position hopping. The decoding for and performance analysis of this coding and modulation scheme are the subjects of this thesis. First, we study the inner convolutional coded BPSK/BPPM in isolation. We suggest an optimal symbol-wise decoding metric, which replaces the sub-optimal bit-wise metric previously suggested in standardization documents, and we define semi-analytical ex- pressions for the bit-error rate (BER) performance with both optimal and sub-optimal decoding metrics. It is shown through analytical and simulated results that, using the optimal symbol-wise metric results in significant performance gains, of e.g. 2 dB at BER of 10‾³. while decoding complexity is identical to that with bit-wise decoding metric. Based on our semi-analytical results, we also quantify the performance loss due to RAKE combining with a limited number of fingers as opposed to ideal combining. Next, we investigate the entire concatenated coded BPSK/BPPM scheme, including the outer RS code and the inner convolutional code, and we suggest an improved decoding scheme by introducing reliability information generated by the inner decoder. More specifically, two different soft output Viterbi algorithms (SOVA) are considered and compared for generation of reliability information. For the conventional setup of inner Viterbi and outer RS decoder, we define semi-analytical expressions for the frame-error rate (FER) of the overall system, these expressions are highly valuable for quick performance assessment, since simulating the system's performance is extremely time consuming. In addition to decoding assuming perfect channel state information at the receiver (coherent receiver) considered so far, we also study the performance of decoding without channel state information (non-coherent receiver) to detect the BPPM data bit. This decoding mode is explicitly envisioned by the standard. Again, analytical expressions for BER. and FER are obtained, and the performance of non-coherent and coherent receivers are compared. |
Genre |
Thesis/Dissertation |
Type |
Text |
Language | eng |
Date Available | 2011-02-18 |
Provider | Vancouver : University of British Columbia Library |
Rights | For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use. |
DOI | 10.14288/1.0100754 |
URI | http://hdl.handle.net/2429/31506 |
Degree |
Master of Applied Science - MASc |
Program |
Electrical and Computer Engineering |
Affiliation |
Applied Science, Faculty of Electrical and Computer Engineering, Department of |
Degree Grantor | University of British Columbia |
Campus |
UBCV |
Scholarly Level | Graduate |
AggregatedSourceRepository | DSpace |
Download
- Media
- 831-ubc_2007-0306.pdf [ 3.1MB ]
- Metadata
- JSON: 831-1.0100754.json
- JSON-LD: 831-1.0100754-ld.json
- RDF/XML (Pretty): 831-1.0100754-rdf.xml
- RDF/JSON: 831-1.0100754-rdf.json
- Turtle: 831-1.0100754-turtle.txt
- N-Triples: 831-1.0100754-rdf-ntriples.txt
- Original Record: 831-1.0100754-source.json
- Full Text
- 831-1.0100754-fulltext.txt
- Citation
- 831-1.0100754.ris
Full Text
Cite
Citation Scheme:
Usage Statistics
Share
Embed
Customize your widget with the following options, then copy and paste the code below into the HTML
of your page to embed this item in your website.
<div id="ubcOpenCollectionsWidgetDisplay">
<script id="ubcOpenCollectionsWidget"
src="{[{embed.src}]}"
data-item="{[{embed.item}]}"
data-collection="{[{embed.collection}]}"
data-metadata="{[{embed.showMetadata}]}"
data-width="{[{embed.width}]}"
data-media="{[{embed.selectedMedia}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
https://iiif.library.ubc.ca/presentation/dsp.831.1-0100754/manifest