Arie Dickman Verified Signal Processing Algorithms in Matlab and C Advised by Israel Greiss Verified Signal Processing Algorithms in Matlab and C Arie Dickman Verified Signal Processing Algorithms in Matlab and C Advised by Israel Greiss Arie Dickman Rishon Lezion, Israel ISBN 978-3-030-93362-3 ISBN 978-3-030-93363-0 (eBook) https://doi.org/10.1007/978-3-030-93363-0 © The Editor(s) (if applicable) and The Author(s), under exclusive license to Springer Nature Switzerland AG 2022 This work is subject to copyright. All rights are solely and exclusively licensed by the Publisher, whether the whole or part of the material is concerned, specifically the rights of translation, reprinting, reuse of illustrations, recitation, broadcasting, reproduction on microfilms or in any other physical way, and transmission or information storage and retrieval, electronic adaptation, computer software, or by similar or dissimilar methodology now known or hereafter developed. The use of general descriptive names, registered names, trademarks, service marks, etc. in this publication does not imply, even in the absence of a specific statement, that such names are exempt from the relevant protective laws and regulations and therefore free for general use. The publisher, the authors and the editors are safe to assume that the advice and information in this book are believed to be true and accurate at the date of publication. Neither the publisher nor the authors or the editors give a warranty, expressed or implied, with respect to the material contained herein or for any errors or omissions that may have been made. The publisher remains neutral with regard to jurisdictional claims in published maps and institutional affiliations. This Springer imprint is published by the registered company Springer Nature Switzerland AG The registered company address is: Gewerbestrasse 11, 6330 Cham, Switzerland To Rina for her love and support, to Yonathan for the joy he brought into our lives and to Alon, Eran, and Michal Preface This book is for engineers in the field of signal processing who wish to implement in the shortest time working systems that are mostly built from a collection of build- ing blocks, residing in an ASIC or FPGA firmware or in C language software, run- ning on an SBC or DSP. The book provides the software path regarding implementation, keeping in mind design. A substantial part of the material may be found in books, papers, or application notes, but to the best of my knowledge there is currently no such book that presents ready-to-use solutions to common signal processing problems under one binding. Most of the graduates or advanced course students in engineering faculties join the industry; after graduating, they are less interested in theory or math, but in solv- ing problems, they are the public to whom this book is directed. After an extended experience with the industry, I know that not many engineers are familiar with both Matlab and C programming, so this book may assist to either weakness. After reading this book and practicing the enclosed examples, one will under- stand how to design using Matlab and implement in C basic elements involved in signal processing and some in control design. All Matlab and C codes in the book are verified and almost all are original since processing times for all C codes are specified; the reader is able to estimate the pro- cessing time on his own target, by comparing it to the I5 2.9 GHz CPU used for measurement here. The book does not pretend to present the optimal solution for every algorithm, but rather to offer simple and practical solutions, I believe in solutions that consume less than 50% of the hardware resources, so that when a new requirement appears, there is still no need to replace hardware. This book is not directed to total beginners, and notions like FFT, IFFT, FIR, and IIR are assumed as known to the reader. Rishon Lezion, Israel Arie Dickman vii Acknowledgment I would like to thank Professor Anthony J. Weiss from Tel Aviv University, Israel, for his brilliant comments and useful critiques of this book. I thank Mrs. Mary E. James from Springer for her continuous help and initiative which were essential for the publication of this book. Thanks to MathWorks Inc. for letting me use the Matlab software which is an integral part of this book. ix Contents 1 Overview of Signal Detection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 About Signal Detection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.3 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2 Measures for Verification and Implementation of Algorithms . . . . . . 9 2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 2.2 Measures Details . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 2.2.1 Algorithm Verification in Frequency . . . . . . . . . . . . . . . . . . 9 2.2.2 Preparing Coefficients File for C Software . . . . . . . . . . . . . 11 2.2.3 Algorithm Verification in Time . . . . . . . . . . . . . . . . . . . . . . 12 2.2.4 Algorithm Transient Time Measurement . . . . . . . . . . . . . . . 14 2.2.5 Algorithm Processing Time Measurement . . . . . . . . . . . . . 15 2.3 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 3 Narrow Band & Wide Band Processing Basics . . . . . . . . . . . . . . . . . . 17 3.1 Narrow Band Processing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 3.1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 3.1.2 Numerically Controlled Oscillator . . . . . . . . . . . . . . . . . . . . 18 3.1.3 Finite Impulse Response Decimators. . . . . . . . . . . . . . . . . . 21 3.1.4 Low Decimation Ratio Finite Impulse Response Filters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 3.1.5 Higher Decimation Ratio Finite Impulse Response Filters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 3.1.6 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 3.2 Wide Band Processing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 3.2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 3.2.2 Shaping Windows . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 3.2.3 Designing Self Made Windows . . . . . . . . . . . . . . . . . . . . . . 44 3.2.4 Fast Fourier Transform. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 xi xii Contents 3.2.5 Fast Fourier Transform Implementation . . . . . . . . . . . . . . . 46 3.2.6 Implementing Large Fast Fourier Transform by Smaller Ones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 3.2.7 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 4 Complex Finite Impulse Response Filters . . . . . . . . . . . . . . . . . . . . . . 59 4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 4.2 Complex Finite Impulse Response Filter Design . . . . . . . . . . . . . . 59 4.2.1 Modified Low Pass Filter Design Method . . . . . . . . . . . . . . 60 4.2.2 Matlab Direct Complex Filter Design Method . . . . . . . . . . 61 4.2.3 Preferred Design Method . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 4.2.4 Property of Complex Filters . . . . . . . . . . . . . . . . . . . . . . . . . 62 4.2.5 Implementation of Complex Filters . . . . . . . . . . . . . . . . . . . 63 4.3 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 5 Infinite Impulse Response Filters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 5.2 Infinite Impulse Response Filter Design . . . . . . . . . . . . . . . . . . . . . 65 5.2.1 Low Pass Filter Design . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 5.2.2 High Pass Filter Design . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 5.2.3 Band Stop Filter Design . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78 5.2.4 All Pass Filter Design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81 5.2.5 Band Pass Filter Design . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83 5.3 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87 6 Non-Linear and Batch Filters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89 6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89 6.2 Median Filter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89 6.3 Batch Filter with Comparison to Median Filter . . . . . . . . . . . . . . . . 92 6.4 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93 7 Interpolators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95 7.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95 7.2 Interpolator Design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95 7.2.1 Fractional Interpolation/Decimation . . . . . . . . . . . . . . . . . . 98 7.3 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106 8 Direct Digital Synthesis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107 8.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107 8.2 Direct Digital Synthesizer Details . . . . . . . . . . . . . . . . . . . . . . . . . . 107 8.2.1 Frequency Modulation of a Direct Digital Synthesizer . . . . 109 8.2.2 Receiver—Frequency Demodulator for Verification . . . . . . 111 8.2.3 Amplitude Modulation of a Direct Digital Synthesizer . . . . 113 8.2.4 Receiver—Amplitude Demodulator for Verification . . . . . . 115 8.3 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117 Contents xiii 9 Inverse Fast Fourier Transform . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119 9.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119 9.2 Inverse Fast Fourier Transform Details . . . . . . . . . . . . . . . . . . . . . . 119 9.3 Inverse Fast Fourier Transform Implementation . . . . . . . . . . . . . . . 121 9.4 Frequency Modulation of Inverse Fast Fourier Transform Output . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122 9.5 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124 Reference . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124 10 Hilbert Transform . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125 11 Channelizer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127 11.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127 11.2 Channelizer Fundamentals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127 11.2.1 Comparing Channelizer and Narrow Band Processing Times . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129 11.2.2 Channelizer Design Considerations . . . . . . . . . . . . . . . . . . 130 11.3 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134 12 Correlation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135 12.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135 12.2 Correlation Details . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135 12.2.1 Fast Correlation by Using Fast Fourier Transform . . . . . . 138 12.3 Pattern Recognition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140 12.4 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144 13 Adaptive Filters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145 13.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145 13.2 Equalizers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145 13.2.1 Least Mean Squares Algorithm . . . . . . . . . . . . . . . . . . . . . 146 13.2.2 Normalized Least Mean Squares Algorithm . . . . . . . . . . . 150 13.2.3 Multi-input Equalizer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151 13.3 Interference Cancellation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154 13.3.1 Least Mean Squares Cancelling Algorithm . . . . . . . . . . . . 156 13.3.2 Recursive Least Squares Cancelling Algorithm . . . . . . . . . 157 13.4 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 158 Reference . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159 14 Unequally Spaced Sampling. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161 14.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161 14.2 Modified Lomb–Scargle Algorithm . . . . . . . . . . . . . . . . . . . . . . . . 161 14.3 Algorithm Performance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165 14.4 Algorithm Quality Factor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166 14.5 Algorithm Sensitivity to Interference . . . . . . . . . . . . . . . . . . . . . . 167 14.6 Algorithm Implementation in C . . . . . . . . . . . . . . . . . . . . . . . . . . . 169 14.7 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171