More Mathematical Methods and Algorithms For Signal Processing

polarisgt

I Number Theoretic Methods 1
1 Some number theory and its applications 3
1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2 Divisibility and the Euclidean algorithm . . . . . . . . . . . . . . . . . . . 4
1.2.1 Some applications of the Euclidean algorithm . . . . . . . . . . . . 9
1.2.2 Least common multiples . . . . . . . . . . . . . . . . . . . . . . . 11
1.3 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.4 Congruences and remainders . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.4.1 Properties of the 􀀀 function and an application . . . . . . . . . . . 18
1.4.2 Polynomials evaluation and congruences . . . . . . . . . . . . . . 20
1.5 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
1.6 Solution of linear congruences . . . . . . . . . . . . . . . . . . . . . . . . 23
1.7 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
1.8 The Chinese remainder theorem . . . . . . . . . . . . . . . . . . . . . . . 26
1.9 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
1.10 Example applications of the CRT . . . . . . . . . . . . . . . . . . . . . . . 31
1.10.1 Data rearrangement for DFTs . . . . . . . . . . . . . . . . . . . . 31
1.10.2 Winograd convolution algorithm . . . . . . . . . . . . . . . . . . . 34
1.10.3 Winograd convolution as interpolation . . . . . . . . . . . . . . . . 41
1.11 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
1.12 Number-Theoretic Transforms . . . . . . . . . . . . . . . . . . . . . . . . 44
1.12.1 Modulo arithmetic . . . . . . . . . . . . . . . . . . . . . . . . . . 45
1.12.2 Zero divisors and orders . . . . . . . . . . . . . . . . . . . . . . . 45
1.12.3 Existence of number theoretic transforms . . . . . . . . . . . . . . 48
1.13 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
1.13.1 Fermat Number Transforms . . . . . . . . . . . . . . . . . . . . . 50
1.13.2 Mersenne number transforms . . . . . . . . . . . . . . . . . . . . 52
1.14 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
1.15 Continued fractions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
1.15.1 Basic notations . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
1.15.2 Infinite continued fractions . . . . . . . . . . . . . . . . . . . . . . 55
1.15.3 Finding continued fraction representations . . . . . . . . . . . . . . 57
1.15.4 Continued fraction representation of functions . . . . . . . . . . . . 58
1.16 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
1.17 The M¨obius function and number theoretic inverses . . . . . . . . . . . . . 60
1.18 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
1.19 Cyclotomic polynomials . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
1.19.1 Properties of cyclotomic polynomials . . . . . . . . . . . . . . . . 65
1.20 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
1.21 Subfields and extension fields . . . . . . . . . . . . . . . . . . . . . . . . . 67
1.21.1 Galois fields . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
1.21.2 Signal processing applications of finite fields . . . . . . . . . . . . 72
1.22 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
1.23 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
II Interpolation and Approximation 75
2 Approximation and interpolation methods 77
2.1 Interpolation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
2.2 Sinc function interpolation . . . . . . . . . . . . . . . . . . . . . . . . . . 78
2.3 Polynomial interpolation . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
2.3.1 Canonical basis interpolation . . . . . . . . . . . . . . . . . . . . . 80
2.3.2 Lagrange interpolation . . . . . . . . . . . . . . . . . . . . . . . . 80
2.3.3 Newton interpolation and divided differences . . . . . . . . . . . . 83
2.3.4 Vandermonde systems . . . . . . . . . . . . . . . . . . . . . . . . 85
2.3.5 Interpolation using orthogonal polynomials . . . . . . . . . . . . . 86
2.4 Interpolation using rational functions . . . . . . . . . . . . . . . . . . . . . 87
2.4.1 Existence of rational function interpolators . . . . . . . . . . . . . 87
2.4.2 An algorithm for rational function interpolation . . . . . . . . . . . 89
2.5 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
2.6 Trigonometric interpolation . . . . . . . . . . . . . . . . . . . . . . . . . . 98
2.7 Bandlimited interpolation and approximation . . . . . . . . . . . . . . . . 99
2.8 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
2.9 Approximation using polynomials . . . . . . . . . . . . . . . . . . . . . . 103
2.10 Rational approximations . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
2.10.1 Pad`e approximations . . . . . . . . . . . . . . . . . . . . . . . . . 104
2.10.2 Pad`e approximation of time delays . . . . . . . . . . . . . . . . . . 107
2.10.3 An application of Pad`e approximation: ARMA model identification 108
2.11 Minimax approximations . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
2.11.1 Modifications and simplifications . . . . . . . . . . . . . . . . . . 117
2.12 Extension of minimax approximation to rational functions . . . . . . . . . 119
2.13 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119
2.14 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120
III Other Mathematical Tools 121
3 Complex Analysis and Polynomial Theory 123
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123
3.2 Construction of the complex numbers and basic operations . . . . . . . . . 123
3.3 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126
3.4 Functions of complex variables . . . . . . . . . . . . . . . . . . . . . . . . 126
3.5 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130
3.6 Derivatives of complex functions . . . . . . . . . . . . . . . . . . . . . . . 130
3.7 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132
3.8 Contours and contour integration . . . . . . . . . . . . . . . . . . . . . . . 133
3.9 Independence of path and Cauchy’s integral theorem . . . . . . . . . . . . 139
3.9.1 Multiply connected domains . . . . . . . . . . . . . . . . . . . . . 142
3.10 Cauchy’s integral formula . . . . . . . . . . . . . . . . . . . . . . . . . . . 144
3.11 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147
3.12 Cauchy’s inequality and its consequnences . . . . . . . . . . . . . . . . . . 148
3.13 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 150
3.14 Taylor and Laurent series . . . . . . . . . . . . . . . . . . . . . . . . . . . 151
3.14.1 Classification of isolated singularities [?, p. 269] . . . . . . . . . . 158
3.15 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 160
3.16 Residue theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161
3.17 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164
3.18 Principal of the argument and Rouch`es theorem . . . . . . . . . . . . . . . 165
3.19 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 168
3.20 Contour integration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 168
3.21 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 177
3.22 Conformal mappings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 178
3.23 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 184
3.24 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 184
3.25 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185

weimingdong

xiexie..

yulai860

xiexie..

apteye

thanks

zlhrsy

bucuo,xiexie

risinglee

谢谢楼主分享!!!!!!!!!!

ljuhu78

thanks for submit

272371972

bu cuo

272371972

b ucuo

yulai860

bucuo,xiexie