Professor Emanuel Radoi

Professor Benoit Nadège Thirion-Moreau

Keywords:

.3 [4] a linear antenna with N sensors points its highest gain beam, main beam, towards the desired user while directing nulls to unwanted inputs.

has been an honour and a privilege to have studied and worked in a university and a faculty that you have devoted your life to build. It is with your effort and dedication that it has reached its international exposure and distinguished reputation. It has become a second home for the many and has taught us that home is not made of bricks and stones but where the heart and mind belongs.

I would like to, also, express my unending and immeasurable appreciation and gratitude for Mrs Mimo NAKAD, my eternal best friend and my source of boundless motivation. She is an enthusiastic, dedicated and wholehearted person, a true star. From her I learned that, quoting Gibran Khalil Gibran, "You give but little when you give of your possessions. It is when you give of yourself that you truly give".

Finally, I would like to thank my mother Mirana Abed AKKAD, my father Michel AKKAD, my aunt Kety Akkad SAWAYA, my sister Mariam AKKAD and my brothers Charbel and Roufaeil AKKAD, for without them I am nothing.

ADAPTIVE BEAMFORMING: A HISTORY

Since the dawn of digital signal processing, researchers have thrived to develop realtime adaptive systems that can independently self-adjust to estimate/filter the desired data from an incoming noisy signal. The ability of an adaptive system/filter to autonomously operate in an unknown noisy environment, makes it an inevitable feature in numerous applications, such as: wireless communication, digital communication, biomedical engineering, control systems, geology and so on. While these adaptive filters still share a common mode of operation, the manner in which they extract the signal of interest changes for each class of applications [1,2,3]. Thus, the operation of a linear adaptive filter at a discrete time instance k can be summarized as follows: for an input vector signal x(k), a desired reference signal d(k) and an output signal y(k), the adaptive algorithm computes the error signal e(k) = d(k) -y(k) to estimate the variable filter weight vector w(k + 1) [2]. As shown in Figure 1.1, the initial building blocks of an adaptive system are the linear filter and the adaptive algorithm. Moreover, the linear filter block can be modeled with a finite impulse response (FIR) or an infinite impulse response (IIR) for a one dimensional input vector (one sensor) or a spatial filter, i.e. linear combiner (LC) for a N dimensional input (sensor array). For spatial filters, the filtered output signal, y(k), is obtained as a linear combination of the input signal x(k) = [x 1 (k), x 2 (k), ..., x N (k)] T and the filter weights w(k) = [w 1 (k), w 2 (k), ..., w N (k)] T and is given as y(k) = w H (k)x(k), where the superscripts T and H denote respectively the vector transpose and the Hermitian operator, i.e. the conjugate transpose. Furthermore, the adaptive algorithm block is used to estimate the variable filter weights based on certain optimization algorithms. Two classical methods exist, in wide sense stationary (WSS) environments, for deriving recursive algorithms [2]:

1. Stochastic gradient descent (SGD): In SGD, the cost function is defined as the mean squared value of the error, and it is represented by a 2 nd order function of the filter weights. For recursive applications, the instantaneous squared error is supplied to update the variable weights. As such, the SGD technique refers to the least mean square (LMS) algorithm [2].

Least squares (LS):

In this method, the cost function is defined as the sum of weighted error squares. In contrast to the SGD technique, LS utilizes matrix operations to compute the gain matrix and updates the variable weights. Such technique is referred to as the recursive least squares (RLS) [2].

With the recent, exponential, spread of wireless connected devices and their requirements in data rate and accuracy, the complexity of array processing algorithms have drastically increased [3,4]. Such unprecedented growth resulted in a highly congested frequency spectrum [5]. Therefore, many researchers have coupled adaptive signal processing algorithms with antenna arrays to implement adaptive beamforming methods and further increase the spectral efficiency while simultaneously providing a high quality of service (QoS), higher data rates and a wider coverage at a reduced cost. However, the introduction of complex adaptive algorithms, in wireless communication, enforced new limitations on their hardware architecture, such as the need of reduced arithmetic complexity and that of pipeline and parallelism while preserving accelerated convergence and a low residual error in finite precision considerations [4]. Thus, in this chapter, we introduce the recent challenges in signal processing for wireless applications and one of the most adopted array processing technique, i.e. adaptive beamforming. Additionally, we present our research objectives and motivation towards the imposed challenges.

Signal Processing in Wireless Communication

In practice, the majority of wireless communication applications, i.e. mobile communication, radar or sonar, involves spatial filtering techniques [1]. Such techniques are achieved by employing a sensor array architecture, generally, with equally spaced homogeneous elements, as shown in Figure 1.2 [4]. With the first antenna element acting as Figure 1.2 -Simple Antenna Array a reference, θ is the angle of arrival (AOA), D a is the distance between two consecutive antenna elements and x(k) is the input signal. In effect, the acquired signal is sampled in space to exploit the spatial properties of signals and noise through array processing (AP) methods, i.e. beamforming [1].

Figure 1.3 -Adaptive Beamforming System

The first beamforming system, i.e. the intermediate frequency (IF) side-lobe canceler was introduced by Howells in 1957 [2,7]. Howells demonstrated the use of one degree of freedom, two sensor antenna array in amplifying a desired signal while attenuating interference. In his antenna architecture, Howells implemented a high gain antenna element with respect to a low gain, reference, omnidirectional, antenna forming a configurable array with a steerable main beam and null [2,7]. Subsequently, in 1966, Applebaum derived the control law implementing a control loop for each antenna element [8,[START_REF] Applebaum | Adaptive Arrays with Main Beam Constraints[END_REF]. Applebaum's technique resulted in a generalization of Howells side lobe canceler and was based on maximizing the signal to noise ratio (SNR) of the antenna arrays output for random noise environments [2,8,[START_REF] Applebaum | Adaptive Arrays with Main Beam Constraints[END_REF]. Another classical, fully adaptive beamformer, was developed by Widrow et al in 1967 [START_REF] Widrow | The Complex LMS Algorithm[END_REF]. In [START_REF] Widrow | The Complex LMS Algorithm[END_REF], the authors demonstrated the effective use of the LMS algorithm in providing a low complexity adaptive beamformer based on the steepest descent optimization technique and the use of the stochastic gradient [2].

Our Research Project

The LMS algorithm, presented by Widrow et al, iteratively computes the filter weights by minimizing a pre-defined cost function based on the auto-correlation of the input signal and the cross-correlation of the input and the reference signal [START_REF] Widrow | The Complex LMS Algorithm[END_REF]. Moreover, a minimum variance distortionless response (MVDR) [START_REF] Vorobyov | Principles of Minimum Variance Robust Adaptive Beamforming Design[END_REF][START_REF] Vorobyov | Adaptive Beamforming with Joint Robustness Against Mismatched Signal Steering Vector and Interference Nonstationarity[END_REF] adaptive beamformer was later introduced by Capon in 1969 [2]. In this algorithm, Capon proposed minimizing the output average power (variance) subject to a pre-set constraint maximizing that of the desired signal [2]. Unlike the LMS, Capcon's MVDR requires previous knowledge on the incoming signals direction, i.e. the AOA [START_REF] Akkad | An Efficient Non-Blind Steering Vector Estimation Technique For Robust Adaptive Beamforming With Multistage Error Feedback[END_REF]. Numerous modifications and algorithms were later on derived based on the classical approaches to accurately achieve optimal behavior, through the use of multi stage beamformers, in recovering the signal of interest and attenuating interference and noise [4,5,6,[START_REF] Akkad | An Efficient Non-Blind Steering Vector Estimation Technique For Robust Adaptive Beamforming With Multistage Error Feedback[END_REF][START_REF] Akkad | A Multi-Stage Parallel LMS Structure and its Stability Analysis Using Transfer Function Approximation[END_REF][START_REF] Srar | Adaptive Array Beam Forming Using A Combined RLS-LMS Algorithm[END_REF]. Some multi stage beamformers are the least mean square -least mean square (LLMS) algorithm [5], the recursive least mean square (RLMS) algorithm [START_REF] Srar | Adaptive Array Beam Forming Using A Combined RLS-LMS Algorithm[END_REF], the reduced complexity parallel RLMS (RLMSp) [6] and the parallel LMS (pLMS) [START_REF] Akkad | A Multi-Stage Parallel LMS Structure and its Stability Analysis Using Transfer Function Approximation[END_REF].

Our Research Project

While the currently employed adaptive algorithms demonstrate satisfactory behavior and convergence in infinite precision mode, in practical applications, i.e within a finite precision mode, their performance is known to degrade. Such degradation is governed by the resource limitations and analog to digital converters of the hosting processor leading to the accumulation of round off and quantization errors [4,[START_REF] Srar | LLMS Adaptive Beamforming Algorithm Implemented With Finite Precision[END_REF][START_REF] Farina | Effect of ADC and Receiver Saturation On Adaptive Spatial Filtering Of Directional Interference[END_REF][START_REF] Caraiscos | A Roundoff Error Analysis Of The LMS Adaptive Algorithm[END_REF]. Additionally, the increase in complex computations, i.e. matrix operations, divisions and matrix inversions, due to the nature of the operations, severely degrades the speed of operations which in turn affects the beamformers reliability. Several variants of the classical beamformers have been proposed to present a parallel and easy to pipeline architecture while preserving convergence and acceptable performance. Such techniques are and not limited to: the Gauss-Seidel Fast Affine Projection (GS-FAP) algorithm [START_REF] Albu | The Gauss-Seidel Fast Affine Projection Algorithm[END_REF], the a Priori Error-Feedback LSL (EF-LSL) algorithm using a logarithmic arithmetic [START_REF] Albu | Pipelined Implementations Of The a Priori Error-Feedback LSL Algorithm Using Logarithmic Arithmetic[END_REF], the relaxed look ahead pipelined LMS [START_REF] Shanbhag | Relaxed Look-Ahead Pipelined LMS Adaptive Filters And Their Application To ADPCM Coder[END_REF], the time sharedlook up table (LUT)-less LMS architecture [START_REF] Sarma | A Novel Time-Shared and LUT-Less Pipelined Architecture for LMS Adaptive Filter[END_REF] and the division free and variable regularized LMS [START_REF] Zhao | A Division-Free and Variable-Regularized LMS-Based Generalized Sidelobe Canceller for Adaptive Beamforming and Its Efficient Hardware Realization[END_REF], and the relaxed look ahead par-Partie , Chapter 1 -Adaptive Beamforming: A History allel LMS [START_REF] Akkad | Two Stages Parallel LMS Structure A Pipelined Hardware Architecture[END_REF]. The GS-FAP demonstrates better performance over the LMS and some of its variants; However, at the cost of an increase in complexity and processing stages [START_REF] Albu | The Gauss-Seidel Fast Affine Projection Algorithm[END_REF]. The EF-LSL structure presents a considerable reduction in the processing time and look up table usage; However, it is based on the least square algorithm, of O(N 2 ) complexity, and requires the use of a logarithmic number system with a dedicated arithmetic unit [START_REF] Albu | Pipelined Implementations Of The a Priori Error-Feedback LSL Algorithm Using Logarithmic Arithmetic[END_REF]. The LLMS [5] and RLMS [START_REF] Srar | Adaptive Array Beam Forming Using A Combined RLS-LMS Algorithm[END_REF] are multi-stage LMS/LMS and RLS/LMS seperated by an estimate of the steering vector and connected by a delayed error feedback. These techniques show upper level performance over other LMS and RLS variants at the cost of doubling the computational requirements. Nevertheless, presenting a pipeline hardware architecture for the multi stage algorithms is difficult given the design error feedback path and its computational complexity. The previous cascade RLMS algorithm is thus simplified to present a parallel input structure as shown in [6] by eliminating the need for a cascading stage. However, the suggested improvement does not reduce the O(N 2 ) complexity and does not provide an easy to pipeline architecture. On the other hand, the relaxed look-ahead pipeline LMS, and the time shared LUT-less LMS discussed in [START_REF] Shanbhag | Relaxed Look-Ahead Pipelined LMS Adaptive Filters And Their Application To ADPCM Coder[END_REF][START_REF] Sarma | A Novel Time-Shared and LUT-Less Pipelined Architecture for LMS Adaptive Filter[END_REF], present a pipeline architecture for the classical LMS with no noticeable enhancement in the convergence speed nor in the error floor. Furthermore, the pipeline division free variable regularized LMS architecture presented in [START_REF] Zhao | A Division-Free and Variable-Regularized LMS-Based Generalized Sidelobe Canceller for Adaptive Beamforming and Its Efficient Hardware Realization[END_REF] still presents considerable complexity and requires an on-the-fly computation of its step size compared to the classical LMS. Therefore, it is of utmost importance to achieve a parallel, reduced complexity and easy to pipeline beamformer with improved convergence and low residual error.

Motivation

In this context, the main motivation of our research is to eliminate the trade off between the computational complexity and the performance of the multi-stage algorithms while presenting a suitable hardware architecture for limited resource devices. Through the use of the delay feedback technique [5,6,[START_REF] Akkad | A Multi-Stage Parallel LMS Structure and its Stability Analysis Using Transfer Function Approximation[END_REF][START_REF] Srar | Adaptive Array Beam Forming Using A Combined RLS-LMS Algorithm[END_REF], we propose a two stages, parallel input LMS algorithm with an accelerated convergence and a minimal residual error for adaptive beamforming (pLMS). pLMS is formed of two LMS stages operating in parallel, where the final error signal is derived as a combination of individual stage errors. The error signal of the second LMS stage (LM S 2 ) is multiplied by the imaginary number j = √ -1 to combine with that of the first LMS stage (LM S 1 ). Additionally, we further simplify the pLMS to achieve a reduced complexity parallel LMS design (RC-pLMS). The RC-pLMS is obtained by adding a phased sample delayed version of the inputs to the LM S 1 to eliminate the need for a second independent set of weights. In order to present a pipeline, parallel, hardware architecture for the RC-pLMS, we propose the application of the delay and sum relaxed look-ahead technique (DRC-pLMS). Convergence and stability analysis are performed to determine the upper bound of the step size. The quantization effect analysis is conducted to assess the system performance within finite precision arithmetic. Finally, a hardware implementation of the DRC-pLMS design is done in order to study its resource consumption and behavior in finite precision arithmetic. The architecture is implemented using Q2.151 format [4,[START_REF] Meyer-Baese | Digital Signal Processing with Field Programmable Gate Arrays (Signals and Communication Technology)[END_REF].

Outlines

In chapter 1, we first present an overview on the concept of adaptive filtering and the advantages it provides for different digital signal processing (DSP) applications. Second, we discuss the benefits of applying adaptive filtering techniques in wireless communication in order to ease spectral congestion and improve overall performance through beamforming. Finally, we perform a comparative study on different, previous and recent, adaptive beamforming algorithms and hardware implementation while commenting on their advantages and disadvantages.

In chapter 2, we detail the basics of antenna arrays, the popular architectures currently adopted and their essential role in exploiting the spatial domain through beamforming. Concurrently, we explain the basic concepts in spatial filtering and beamforming such as: beam steering, null placement and array ambiguity.

In chapter 3, we highlight the different types and sub-types of adaptive beamforming techniques, i.e. blind, semi-blind, non-blind, temporal based and spatial based. Additionally, we provide an extensive mathematical overview for different, popular, temporal and spatial referenced adaptive beamforming algorithms and their variants. We then present Partie , Chapter 1 -Adaptive Beamforming: A History a comparative study on the performance of each, with respect to the convergence profile, through the use of the mean square error (MSE) criteria. Additionally, we list some of the multi stage, cascade, adaptive beamforming algorithms, i.e. LLMS and RLMS, and we propose a reduced complexity parallel input RLMS structure.

Our contributions are detailed in chapters 4, 5 and 6 and are summarized as follows:

-A comparative experimental study is conducted in order to assess the performance of different processors and tools in implementing DSP related routines. The fast Fourier transform (FFT) is the core of numerous DSP applications and is implemented, in parallel and sequential forms, on different field programmable gate array (FPGA) and system on chip (SoC) families. Moreover, the FFT architecture is modeled through the use of various development techniques and tools such as: traditional hardware description language (HDL), high level language (HLL) and high level synthesis (HLS) tools. Synthesis results have shown that an HDL like, high speed design, can be obtained through the effective use of HLL design techniques and proper HLS compiler directives. Moreover, HLL and HLS tools provides a simple and easy method to target multi processor architectures and heterogeneous systems with a shorter design and testing time. However, the concluded disadvantage of using HLS tools is that optimization related tasks is offloaded to the compiler and is dependent on the proper use of compiler directives.

-A high accuracy, low complexity dynamic twiddle function generator using Chebyshev polynomial approximation. While the FFT contributes in accelerating numerous DSP applications, when implemented in finite precision, on limited resource devices, its performance tend to degrade due to the resulting loss of accuracy. As such, we propose a low complexity, high accuracy, dynamic twiddle factor computation method based on Chebyshev polynomial approximation. Moreover, we present its low complexity, low latency, high throughput architecture in finite precision mode. Simulation and synthesis results highlight the superior performance of the adopted approximation method compared to the classical Taylor approximation. In contrast, to the Taylor approximation method, the Chebyshev approximation achieved an accuracy of three decimal digits and smaller resource usage for a fifth order polynomial.

-A two stages parallel LMS (pLMS), its transfer function approximation and pipeline hardware implementation for adaptive beamforming. In order to eliminate the LMS convergence speed and error floor trade off, while preserving a parallel and low latency architecture, we propose a multi stage parallel LMS architecture connected by error feedback. Where the pLMS overall error is formed as a combination of individual stage errors. In order to numerically compute the maximum step size, the pLMS transfer function approximation derived by modeling the input antenna as a finite input response (FIR) fractional delay filter using Lagrange interpolation. While the proposed pLMS structure is formed of two LMS stages in parallel, presenting a pipeline design is not straight forward given the dependency on the error feedback paths. As such, we propose the application of the delay and sum relaxed look ahead technique, independently, for each of the LMS stages. Thus, the resulting delay pLMS (DpLMS) is obtained and implemented in high throughput, low latency, parallel and pipeline architecture with finite precision. Software simulation results, reflected by the MSE and output beam pattern validated the superior performance of the pLMS with respect to other variants in different signal to noise ratio (SNR) environments. Moreover, with respect to the output beam pattern, the DpLMS implemented in finite precision, showed similar accuracy to that of the infinite precision one. Finally, synthesis results shows that the DpLMS achieved a maximum operating frequency of 208.33 MHz in a low complexity, high throughput architecture.

-A reduced complexity parallel LMS (RC-pLMS), its transfer function approximation and pipeline hardware implementation for adaptive beamforming. While the pLMS eliminated the LMS trade off while maintaining a parallel easy to pipeline design, it is formed of two LMS stages and requires twice the LMS resources. As such, in order to maintain an LMS like complexity while preserving pLMS convergence profile, we propose a single stage RC-pLMS design. RC-pLMS is obtained by modeling the pLMS as a single stage LMS with additional modified inputs, i.e. original input and desired signal subject to a one sample delay. Thus eliminating the need for a second LMS filter and reducing the complexity by half. Similarly, the RC-pLMS transfer function approximation is derived to numerically determine the maximum step size by modeling the input linear combiner as a FIR fractional

Partie , Chapter 1 -Adaptive Beamforming: A History delay filter. The RC-pLMS pipeline hardware architecture is obtained through the application of the delay and sum relaxed look ahead techniques (DRC-pLMS) and implemented in finite precision mode. Simulation results, reflected by the MSE and output beam pattern highlight the superior performance of the RC-pLMS, compared to the pLMS and other variants in different SNR environments. Regardless of the adopted approximation, the RC-pLMS presented accelerated convergence, i.e. first 3 iterations, and low steady error while maintaining a low complexity LMS like design. Additionally, hardware simulation show that the finite precision DRC-pLMS achieved similar beam pointing accuracy to the, theoretical, infinite precision. In contrast to the pLMS, synthesis results shows that the DRC-pLMS is obtained at the cost of a marginal, negligible, increase in resource utilization compared to the classical LMS.

Chapter 2

FUNDAMENTALS OF ANTENNA ARRAY BEAMFORMING

Introduction

In order to better illustrate the advantages of antenna arrays, their geometry and radiation pattern, it is important to first present an overview of the basic concepts of a simple antenna element, i.e. an Hertzian Dipole [START_REF] Allen | Adaptive Array Systems: Fundamentals and Applications[END_REF]. The Hertzian Dipole or short dipole, first introduced by Heinrich Hertz in 1886, and is formed of two conductor wires of equal length oriented end-to-end with a center-feeding source for transmitting or receiving RF energy [START_REF] Couch | [END_REF][START_REF] Alexander | The Design of Dipole and Monopole Antennas with Low Uncertainties[END_REF]. In order to achieve a greater communication range, in 1895 Macroni introduced a special case of the dipole structure, the vertical antenna, by grounding one end of the conductor wires, hence mono-pole, i.e. half dipole [START_REF] Couch | [END_REF]. In theory, simple antenna elements are assumed isotropic radiators, i.e. an element which dissipates equal amount of power P in all directions with a radiation intensity U 0 = P 4π [START_REF] Allen | Adaptive Array Systems: Fundamentals and Applications[END_REF]. As such, for an antenna radiating the same amount of power P , the directive gain can be defined as:

g = U U 0 = 4π U P (2.1)
where U is the practical antenna radiation intensity. From (2.1) we can define the radiation directivity (RD) as a function of the maximum radiation intensity U max [START_REF] Allen | Adaptive Array Systems: Fundamentals and Applications[END_REF], such as:

RD = U max U 0 = 4π U max P (2.2)
Partie , Chapter 2 -Fundamentals of Antenna Array Beamforming However, for the Hertzian Dipole [START_REF] Allen | Adaptive Array Systems: Fundamentals and Applications[END_REF], we have:

RD = 1.5 (2.3)
It is clear from (2.3) that the radiation directivity for a Hertzian Dipole is a constant and thus uncontrollable. However, to exploit the spatial domain and infer frequency reuse, it is mandatory to have an antenna architecture with a configurable and a controllable beam radiation pattern. Given their proven benefit in providing an electronically steerable beam radiation pattern through the application of adaptive beamforming techniques, antenna arrays can be reliably employed to perform spatial multiplexing and frequency reuse. Thus, in this chapter, we present the popular antenna array geometries as well as the basic concepts of the spatial filtering and beamforming.

Antenna Array Architecture

Antenna arrays were introduced to perform beamforming techniques for directional signal transmission and reception. Therefore, a beamforming is achieved by forming a main beam towards the direction of a signal of interest and nulls in the direction of interfering signals [5]. Moreover, the desired radiation pattern is achieved automatically by computing the convenient feeding currents phase and amplitude for each antenna element through the use of an adaptive algorithm. From Figure 2.1, the antenna arrays radiation pattern can be defined as follows [START_REF] Allen | Adaptive Array Systems: Fundamentals and Applications[END_REF]:

-Main beam: The main lobe which holds the highest power, i.e. the strongest radiation intensity U max .

-Side lobes: The side beams acting as a local maxima with a radiation intensity

U < U max .
-Nulls: The angle at which no power or radio waves is radiated.

-Half Power Beam Width (HPBW): The HPBW characterizes the ability of an antenna to direct a beam and represented the 3 dB beamwidth, i.e. BW 3dB . The HPBW angle occupies the intensity region satisfying the condition Umax

2 ≤ U ≤ U max .
-First Null Beam width (FNBW): The FNBW describes the ability of the antenna to attenuate and reject interfering signals. The FNBW angle is formed by the main lobe.

-Side Lobe Level (SLL): The radiation intensity of the highest side lobe with respect to the peak of the main beam. For focused transmission, with minimal power loss, it is desirable to decrease the HPBW, i.e. 5 • for space communication [START_REF] Allen | Adaptive Array Systems: Fundamentals and Applications[END_REF]. With dipole antennas, the decrease in HPBW can only be achieved by increasing the length of the antenna; However, that may generate additional multi-lobes [START_REF] Allen | Adaptive Array Systems: Fundamentals and Applications[END_REF]. Consequently, the generated multi-lobes severally degrade the performance for long distance transmission by diminishing the power radiating in the direction of interest [START_REF] Allen | Adaptive Array Systems: Fundamentals and Applications[END_REF]. In contrast to dipole antennas, antenna arrays can be electronically configured to construct radiation patterns with specific beamwidth and orientation [START_REF] Allen | Adaptive Array Systems: Fundamentals and Applications[END_REF].

As such, different antenna array geometries and structures, i.e. linear, planar and circular, can be built in order to achieve the desired radiation properties [START_REF] Allen | Adaptive Array Systems: Fundamentals and Applications[END_REF].

Linear Array

The simplest and most popular type of antenna arrays is the linear array. The linear array consists of a number of antenna elements mounted on a straight line and separated by a spatial distance. For an equally spaced element configuration, the linear array is said to be uniformly spaced and thus the notation uniform linear antenna (ULA). For narrow-band complex signals incoming from the far field [START_REF] Yedavalli | Far-Field RF Wireless Power Transfer With Blind Adaptive Beamforming For Internet Of Things Devices[END_REF] and with the first antenna element acting as a reference, θ is the angle of arrival, D a and τ d are the distance and time delay between consecutive antenna elements, respectively. The time delay τ d is given by:

τ d = D a sin(θ) c (2.4)
where c is the celerity of electromagnetic waves. Let the input vector,

x(k) = [x 1 (k), x 2 (k), ......, x N (k)] T ,
where N is the number of antenna elements, at the discrete time instant, k, to the narrow-band beamformer be defined by:

x(k) = a d s d (k) + N -1 l=0 a i,l i l (k) + n(k) (2.5)
with [.] T denotes the matrix transpose, s d (k) and i l (k) are, respectively, the desired and interfering signals with l < N , a d and a i,l are the N × 1 complex array steering vector for the desired signal and for l th interference, respectively, and n(k) stands for the complex additive white Gaussian noise (CAWGN) vector. A general form of a d and a i,l is given by: a = [1, e -jψ , e -j2ψ , ........e -j(N -1)ψ ] T (2.6)

where the imaginary number j = √ -1 and ψ is the phase shift of the received signal corresponding to the time delay τ d such as:

ψ = 2πf c τ d = 2πcτ d λ = 2π D a sin(θ) λ (2.7)
where λ is the carrier signal wavelength, of frequency f c defined as:

λ = c f c (2.8)
Assuming the antenna array is of unity amplitude and zero phase weighting, from (2.6), the array sensitivity response, i.e. array factor (AF ), for an angle of arrival (AOA), θ, to the acquired signal and its normalized form at unity, (AF (θ)) n , can be represented as:

AF (θ) = N i=1 e -j(i-1)ψ = e -jN ψ -1 e -jψ -1 = sin( N ψ 2 ) sin( ψ 2 )
e -j(N -1)ψ

2

(2.9)

(AF (θ)) n = sin( N ψ 2 ) N sin( ψ 2 )
e -j(N -1)ψ

2

(2.10) From (2.10) and [START_REF] Allen | Adaptive Array Systems: Fundamentals and Applications[END_REF][START_REF] Skolnik | Resolution of Angular Ambiguities in Radar Array Antennas with Widely-Spaced Elements and Grating Lobes[END_REF] the 3 dB beamwidth, can be expressed as:

BW 3dB = 0.866 λ N D a (2.11)
it is clear from (2.11) that the main beams 3 dB beamwidth, i.e. HPBW, is inversely proportional to the number of antenna elements [START_REF] Allen | Adaptive Array Systems: Fundamentals and Applications[END_REF]. As shown in Figure 2.3 for N = 8, N = 32 and N = 64 antenna elements, a more accurate and precise pointing beam can be achieved by increasing the number of antenna elements [START_REF] Allen | Adaptive Array Systems: Fundamentals and Applications[END_REF]. While (2.11) demonstrated the effect of array elements on the HPBW, its denominator exhibits additional variations dependent on the inter element spacing D a . For arrays following custom configuration or design constraints, a maladjustment in inter element spacing can make rise to grating lobes, i.e. array ambiguity and aliasing issues [START_REF] Allen | Adaptive Array Systems: Fundamentals and Applications[END_REF]. An example of a grating lobe is shown in Figure 2.4 for a ULA array of N = 8 elements with inter element spacing of D a = λ 2 . From figure 2.4, it is clear that the main beam is directed towards the pre-set AOA of 0 • ; Moreover, the radiation pattern plot shows additional peaks at ±180 • , respectively. The additional peaks presented are referred to grating lobes and results in array ambiguity and uncertainty towards the true direction of interest [START_REF] Allen | Adaptive Array Systems: Fundamentals and Applications[END_REF]. To mathematically illustrate the grating lobes effect, the modulus, |.|, of the normalized array factor is obtained from (2.10) as:

|(AF (θ)) n | = 1 N | sin( πDaN sin(θ) λ )| | sin( πDaN sin(θ) λ )| (2.12)
thus, for the 90 From the radiation obtained in Figure 2.5, it is clear that the main beam HPBW becomes narrower as the element spacing becomes wider, however for an element spacing D a > 0.5λ additional lobes appear with and incremental energy as D a becomes larger [START_REF] Allen | Adaptive Array Systems: Fundamentals and Applications[END_REF].

Circular Array

In a circular antenna array, the elements are arranged in a circular shape with a radius R c . The circular array does not suffer from array ambiguity, produces wider beams and provides full coverage on the azimuth plane [START_REF] Allen | Adaptive Array Systems: Fundamentals and Applications[END_REF][START_REF] Xing | A Circular Beam-Steering Antenna With Parasitic Water Reflectors[END_REF][START_REF] Ioannides | Uniform Circular Arrays For Smart Antennas[END_REF]]. An N elements circular antenna array with radius R c is shown in Figure 2.6. Figure 2.6 -Uniform Circular Array [START_REF] Srar | Adaptive Antenna Array Beamforming Using a Concatenation of Recursive Least Square and Least Mean Square Algorithms[END_REF] where φ is the azimuth angle and θ is the elevation angle and P c is a projection point. As such, the new array factor for a circular geometry becomes:

AF (θ, φ) = Nx i=1 e -j2π r λ sin(θ)cos(φ-2iπ N ) (2.13)
Given its previously stated advantages the circular array is a popular antenna geometry employed in application where the signal of interests is known to arrive from an azimuth angle. However, this configuration is at the cost of higher side lobe levels [START_REF] Xing | A Circular Beam-Steering Antenna With Parasitic Water Reflectors[END_REF][START_REF] Ioannides | Uniform Circular Arrays For Smart Antennas[END_REF].

Planar Array

A planar array is a 2D extension of the linear array, i.e. array elements arranged in the x, y plane. A popular planar array configuration is the rectangular array as shown in Figure 2.7.

Figure 2.7 -Uniform Rectangular Array [START_REF] Srar | Adaptive Antenna Array Beamforming Using a Concatenation of Recursive Least Square and Least Mean Square Algorithms[END_REF] As shown in Figure 2.7, the planar array is a uniform rectangular array with inter elements spacing of D ax and D ay , respectively. The rectangular array is formed of a total of N x × N y elements, where N x is the number of antennas along the x-plane and N y is the number of antennas along the y-plane, respectively. In this example, the total number of elements is 24 with N x = 4 and N y = 6. Thus, the overall array factor becomes [START_REF] Allen | Adaptive Array Systems: Fundamentals and Applications[END_REF]:

AF (θ, φ) = Nx i=1
Ny k=1 e -j(i-1)ψx e -j(k-1)ψy

(2.14)

ψ x = 2π D ax sin(θ) cos(φ) λ (2.15)
ψ y = 2π D ay sin(θ) cos(φ) λ (2.16)
In contrast to the ULA and the circular array, the planar array allows the production of pencil beams by steering the main beam in the elevation plane as well [START_REF] Allen | Adaptive Array Systems: Fundamentals and Applications[END_REF].

Partie , Chapter 2 -Fundamentals of Antenna Array Beamforming

Spatial Filtering and Beamforming

Spatial filtering is an inevitable feature of modern wireless communication systems and is used for inferring frequency reuse, limiting interference and providing higher data rates and signal to noise ratio (SNR). An antenna array geometry allows the creation of electronically steerable beams and nulls by specific current feeding and element configuration, i.e. beamforming [START_REF] Allen | Adaptive Array Systems: Fundamentals and Applications[END_REF]. The use of a beamforming technique steers the antennas main beam, with constructive amplitude, towards a signal coming from a desired location while directing nulls towards interference, i.e. spatial filtering [2,[START_REF] Allen | Adaptive Array Systems: Fundamentals and Applications[END_REF][START_REF] Yedavalli | Far-Field RF Wireless Power Transfer With Blind Adaptive Beamforming For Internet Of Things Devices[END_REF].

Beam Steering

An efficient form of adaptive beamforming is achieved by connecting the antenna array to a beamformer processor through the use of a signal conditioning circuit and high speed analog to digital (AD) converters [2,[START_REF] Allen | Adaptive Array Systems: Fundamentals and Applications[END_REF][START_REF] Shang | Digital Beamforming Based On FPGA For Phased Array Radar[END_REF][START_REF] Seneviratne | Multidimensional-DSP Beamformers Using the ROACH-2 FPGA Platform[END_REF]. The received signals are spatially sampled and collected by each antenna element, converted to their digital form and fed to the beamformer. Through the use of an adaptive algorithm, with respect to a desired reference signal, the beamformer appropriately weights the input samples to automatically steer the main beam towards the direction of the desired AOA while placing nulls in the direction of interference [2,4,[START_REF] Allen | Adaptive Array Systems: Fundamentals and Applications[END_REF]. The adaptive weighting correctly filters the interfering signals irrespective of their characteristics and AOA [START_REF] Allen | Adaptive Array Systems: Fundamentals and Applications[END_REF].

Adaptive arrays controls the main beams and null steering towards specific direction with respect to a reference signal. Beam steering is achieved through appropriate complex weighting, i.e. appropriate setting of the complex amplitude and phase of the feeding currents [START_REF] Allen | Adaptive Array Systems: Fundamentals and Applications[END_REF]. The complex weights, for steering control, are of the form w n = ρ n e jωn where w n is the complex weight of the n th antenna element, ρ n and ω n are the corresponding amplitude and phase, controlling the main beam and nulls angles, their beamwidth and their side lobe levels, respectively [START_REF] Akkad | An Efficient Non-Blind Steering Vector Estimation Technique For Robust Adaptive Beamforming With Multistage Error Feedback[END_REF][START_REF] Allen | Adaptive Array Systems: Fundamentals and Applications[END_REF].

The main beam steering equation, assuming no noise nor interference, can be written as [START_REF] Allen | Adaptive Array Systems: Fundamentals and Applications[END_REF]:

w = 1 N a d (θ) (2.17)
where w is the linear combiner filter weights, the added factor 1 N is a normalization factor to obtain a unity response in the direction of interest. Thus, for a 4 element ULA array, i.e. N = 4 with inter element spacing of D a = λ 2 the required weights to steer the main beam towards a desired AOA of θ = 30 • can be computed from (2.9) and (2.17), as follows:

w = 1 4 [1, e -j1.
5708 , e -j3.1416 , e -j4.9348 ] (2.18)

While the application of (2.17) successfully steers the main beam towards the desired AOA, it does not null any interfering signals.

In order to allow automatic null steering and attenuate unwanted signals additional constraints are required on the weight steering equation. In case of interference, directing a main towards the desired direction only results in a 3 dB rejection [START_REF] Allen | Adaptive Array Systems: Fundamentals and Applications[END_REF], which is a relatively small improvement compared to the cost and complexity of the beamformer. However, given the nature of the array configuration, it is possible to steer nulls in the direction of interference by computing the complex weights following a set constraint [START_REF] Allen | Adaptive Array Systems: Fundamentals and Applications[END_REF].

Let a d (θ 0 ) be the array steering vector for the desired signal and a i,1 (θ 1 ), ....., a i,k (θ k ) are the k, N × 1 nulls steering vectors. The overall weight can be obtained as a solution to the following equations:

w H a d (θ 0 ) =1 (2.19
)

w H a d (θ k ) =0 ∀k ∈ [1, ..., L] (2.20)
where the superscript H is the Hermitian transpose, L = N -1. Let A i be a N × N square matrix whose columns are formed by the k + 1 steering vectors and c is a N × 1 constraint vector of the form:

c i =[1, 0, 0, ..., 0] T (2.21)
assuming all steering vectors are linearly independent, i.e. A i is non singular, the weight vector can be computed as [START_REF] Allen | Adaptive Array Systems: Fundamentals and Applications[END_REF]:

w H =c T i A -1 i (2.22)
Partie , Chapter 2 -Fundamentals of Antenna Array Beamforming where A -1 i represents the inverse matrix of A i . Thus, for a 2 element ULA array, i.e. N = 2 with inter element spacing of D a = λ 2 , the required weights to steer the main beam towards a desired AOA of θ 0 = 50 • while steering a null toward an interference signal at θ 1 = -15 • can be obtained as follows:

a d (θ 0 ) =[1, e -j2.
A i =[a d (θ 0 ), a i,1 (θ 1 )]
(2.25) From Figure 2.8, it is clear that the beamformer was able to steer a null toward the direction of the interfering signal θ 1 = -15 • , while keeping its main beam directed at the desired AOA θ 0 = 50 • .

c i =[1, 0] T (2.

Conclusion

In this chapter, we presented the benefits of using antenna arrays with a summary of the popular array geometries employed in communication systems, i.e. Linear, planar and circular arrays. Moreover, through the use of antenna arrays, we presented the concept of spatial filtering through the application of beamforming. While the provided beam and steering technique is effective in attenuating interfering signals, however it does not filter uncorrelated signal noise. Additionally, due to their narrow width, it is difficult to accurately place nulls in the desired direction. Thus, it is of a main interest to design a high performance beamformer with accurate beam and null pointing while maintaining a low complexity architecture.

Chapter 3

OVERVIEW OF ADAPTIVE BEAMFORMING ALGORITHMS

Introduction

While an antenna array configuration is capable of performing spatial filtering through beamforming, it is only a physical arrangement of independent antenna elements and cannot perform any processing task. Thus, a dedicated beamforming processor, i.e. beamformer, is required to collect incoming signal samples and electronically steer the main beam and nulls towards the desired directions [4,5,[START_REF] Akkad | An Efficient Non-Blind Steering Vector Estimation Technique For Robust Adaptive Beamforming With Multistage Error Feedback[END_REF][START_REF] Allen | Adaptive Array Systems: Fundamentals and Applications[END_REF]. To obtain an automatically controllable beam, the beamformer implements an adaptive system that continuously adjusts the array parameters with respect to an adaptive algorithm. As such, the choice of the beamforming algorithm is generally governed by the imposed application constraints, i.e. robustness, accuracy and accelerated convergence, and the limitations of the hosting processor, i.e. limited resources and finite precision [4,[START_REF] Meyer-Baese | Digital Signal Processing with Field Programmable Gate Arrays (Signals and Communication Technology)[END_REF][START_REF] Jing | Performance Analysis Of Multi-Rate Signal Processing Digital Filters On FPGA[END_REF].

Adaptive Beamforming

Most adaptive algorithms are classified into three main categories: non-blind, semiblind or blind [START_REF] Allen | Adaptive Array Systems: Fundamentals and Applications[END_REF], as shown in Figure 3.1. In non-blind beamforming the system relies on the temporal or spatial characteristics, i.e. the direction of arrival (DOA), of a reference signal to iteratively compute the array weights with respect to a set cost function or constraints [3,[START_REF] Allen | Adaptive Array Systems: Fundamentals and Applications[END_REF]. Thus, in non-blind beamforming, a clean copy of the reference signal is needed to achieve satisfactory behavior [2]. In contrast, the blind beamforming system Partie , Chapter 3 -Overview of Adaptive Beamforming Algorithms extracts some unknown characteristics of the incoming signal, related to the channel impulse response, the spectrum, the modulus or the envelop deviation, without any prior knowledge of the array geometry in order to correctly steer the main beam and nulls [2,[START_REF] Allen | Adaptive Array Systems: Fundamentals and Applications[END_REF].

Figure 3.1 -Beamforming Algorithms

While most of the blind algorithms requires complex mathematical routines to achieve their goals, the inclusion of a training sequence is shown greatly accelerate the computation, hence the name semi-blind or hybrid [START_REF] Allen | Adaptive Array Systems: Fundamentals and Applications[END_REF].

Non-Blind based Beamforming

In non-blind beamforming, algorithms rely on a pre-set reference signal or parameters in order to effectively steer the main beam and nulls towards a desired look direction [2,3]. The adaptive algorithm is said to be temporal referenced if it relies on a training sequence to form its reference signal and compute the array weights, or spatial referenced if it relies on the array characteristics and DOA [START_REF] Allen | Adaptive Array Systems: Fundamentals and Applications[END_REF].

For temporal referenced beamforming, all adaptive algorithms continuously update the filter weights with respect to a pre-set cost function, such as:

-Minimum mean square error (MMSE) [START_REF] Allen | Adaptive Array Systems: Fundamentals and Applications[END_REF] -Maximum signal to interference plus noise ratio (MSINR) [START_REF] Allen | Adaptive Array Systems: Fundamentals and Applications[END_REF] -Minimum variance distortionless response (MVDR) [START_REF] Allen | Adaptive Array Systems: Fundamentals and Applications[END_REF] Identically, at convergence, all the listed algorithms compute the optimal weight given by the Weiner-Hopf equation [2,[START_REF] Widrow | The Complex LMS Algorithm[END_REF][START_REF] Allen | Adaptive Array Systems: Fundamentals and Applications[END_REF] and defined as [4]:

w o = R -1 p (3.1)
where R = R(0) and R -1 are the input signal auto-correlation matrix and its inverse, respectively, and p = p(0) is the cross correlation vector of the input x(k) and desired signal d(k). R(0) and p(0) are defined at lag τ = 0 as:

R(τ ) = E[x(k -τ )x H (k)] (3.2)
p(τ ) = E[d * (k -τ )x(k)] (3.3)
with E[.] being the expectation operator, the superscripts * and H denotes the complex conjugation and the Hermitian transpose, and the lag τ = k 1 -k 2 . Where, k 1 and k 2 are different time instances from which an observation of the random process is taken. The performance of temporal adaptive algorithms depends on the selected algorithm and the availability of a noise free copy of the reference signal [START_REF] Allen | Adaptive Array Systems: Fundamentals and Applications[END_REF]. Some of the popular nonblind temporal referenced adaptive beamforming algorithms are the recursive least square (RLS), a simpler form of the Kalman filter, and the least mean square (LMS) [START_REF] Akkad | An Efficient Non-Blind Steering Vector Estimation Technique For Robust Adaptive Beamforming With Multistage Error Feedback[END_REF].

Spatial referenced beamformers make use of the DOA of the incoming signal in order to correctly direct its main beam and nulls, as to amplify the desired signal while suppressing co-channel interferences [2,[START_REF] Allen | Adaptive Array Systems: Fundamentals and Applications[END_REF]. The performance of the spatial reference DOA based methods is mainly correlated with the performance of the DOA algorithm itself and its robustness against array calibration and inter element spacing errors [START_REF] Allen | Adaptive Array Systems: Fundamentals and Applications[END_REF]. Some of the popular direction finding techniques are spectral based, i.e. the Fourier method (FM) and the multiple signal classification (MUSIC) algorithm, and parametric based such as: the Partie , Chapter 3 -Overview of Adaptive Beamforming Algorithms maximum likelihood (ML) and the estimation of signal parameter via rotational invariance techniques (ESPRIT).

Althought fast adaptive algorithms exists, such as: the Fast adaptive ESPRIT algorithm [START_REF] Badau | Fast adaptive esprit algorithm[END_REF][START_REF] Badau | Adaptive ESPRIT algorithm based on the PAST subspace tracker[END_REF], the major disadvantage experienced is their high computational complexity [START_REF] Allen | Adaptive Array Systems: Fundamentals and Applications[END_REF]. The increase in complexity results in an intolerable delay, as the system scales in size, making these algorithms undesirable when targeting a hardware implementation on limited resource processors. In contrast, temporal referenced beamformers, benefits from self-correction against array calibration and pointing errors giving their dependency on a per-determined training sequence. For an array of N elements the beamformer makes use of N degrees of freedom (DoF), as such with one element directed to the desired source N -1 remains for nulling up to N -1 interferences. However, an attractive feature of temporal referenced algorithms is their ability to maximize the systems output signal to interference plus noise ratio (SINR) for a number of sources exceeding the number of antenna elements, i.e greater than N [2,[START_REF] Allen | Adaptive Array Systems: Fundamentals and Applications[END_REF]. Additionally, some of the temporal referenced beamformers, i.e. LMS, implements a low complexity architecture making it the most desirable for hardware implementations [4,[START_REF] Shanbhag | Relaxed Look-Ahead Pipelined LMS Adaptive Filters And Their Application To ADPCM Coder[END_REF][START_REF] Sarma | A Novel Time-Shared and LUT-Less Pipelined Architecture for LMS Adaptive Filter[END_REF][START_REF] Zhao | A Division-Free and Variable-Regularized LMS-Based Generalized Sidelobe Canceller for Adaptive Beamforming and Its Efficient Hardware Realization[END_REF][START_REF] Akkad | Two Stages Parallel LMS Structure A Pipelined Hardware Architecture[END_REF][START_REF] Shang | Digital Beamforming Based On FPGA For Phased Array Radar[END_REF].

Blind Based Beamforming

Since non-blind algorithms rely on a training sequence, during the initialization phase no data can be transmitted over the communication channel thus reducing link efficiency [START_REF] Allen | Adaptive Array Systems: Fundamentals and Applications[END_REF]. However, blind adaptive algorithms exploit the statistical and structural properties of the incoming signal without any knowledge on the arrays geometry or signal characteristics [START_REF] Allen | Adaptive Array Systems: Fundamentals and Applications[END_REF]. As such, blind adaptive algorithms do not need a training sequence, thus, implicitly upgrading the performance of the system and its spectral efficiency [2,[START_REF] Allen | Adaptive Array Systems: Fundamentals and Applications[END_REF].

In the case of blind beamforming, the algorithm samples the input signals in time domain forming the input signals matrix X b to extract the data signal S b and the systems transfer function H b satisfying X b = H b S b [START_REF] Allen | Adaptive Array Systems: Fundamentals and Applications[END_REF]. Most blind algorithms rely on the statistical knowledge of some parameters, i.e. envelop deviation, spectral self-coherence, cyclo-stationary and finite alphabet of symbols, in order to estimate of S b or H b through matrix decomposition. Some of the popular blind algorithms are: the constant modulus (CM) algorithm and the higher order cumulant algorithm (HoCA) [2,3,5,[START_REF] Allen | Adaptive Array Systems: Fundamentals and Applications[END_REF]. However, while fast adaptive algorithms exists [START_REF] Kacha | A fast adaptive blind equalization algorithm robust to channel order over-estimation errors[END_REF][START_REF] Zhang | A fast convergent algorithm for joint blind equalization and carrier recovery[END_REF][START_REF] Xie | Fast Blind Adaptive Beamforming Algorithm With Interference Suppression[END_REF], they are of high complexity, such issue pressures blind algorithms and limits their performance when implemented on dedicated, limited resources, hardware, such as field programmable gate array (FPGA) [START_REF] Meyer-Baese | Digital Signal Processing with Field Programmable Gate Arrays (Signals and Communication Technology)[END_REF].

Semi-Blind based Beamforming

The inclusion of a prior knowledge, i.e. a training sequence, in blind algorithms significantly improves their computational performance and real-time adaptation profile. The use of a training sequence introduces a new class of algorithms identified as hybrid or semi-blind. An example of a semi-blind algorithm with real time beamforming capabilities is the decoupled iterative least squares finite alphabet space-time (DILFAST) [START_REF] Allen | Adaptive Array Systems: Fundamentals and Applications[END_REF][START_REF] Laurila | Semi-Blind Separation and Detection of Co-Channel Signals[END_REF]. The DILFAST algorithm uses a 'bit field' training sequence [START_REF] Allen | Adaptive Array Systems: Fundamentals and Applications[END_REF][START_REF] Laurila | Semi-Blind Separation and Detection of Co-Channel Signals[END_REF] at its initialization phase and performs detection and estimation techniques based on the structural properties of the input signal. The algorithm makes use of the finite alphabet (FA) constellation to map the input samples without any need of subspace estimation [START_REF] Laurila | Semi-Blind Separation and Detection of Co-Channel Signals[END_REF]. While the DIL-FAST algorithm can be implemented in real-time it relies on the use of FA and is not robust against any change of the FA as a consequence of some operating conditions [START_REF] Allen | Adaptive Array Systems: Fundamentals and Applications[END_REF].

Adaptive Algorithms

Non-blind adaptive algorithms provide an attractive set of features making them suitable candidates for hardware implementation [4]. Moreover, an overview on different multi stage adaptive beamformer is presented. The multi stage beamformer is formed by two adaptive algorithms, either in cascade or in parallel, sharing a similar training sequence, in which the error signal, e 2 (k), of the second stage is delayed and fed back to combine with that of the first stage, e 1 (k), to form the total system error e t (k) [4,[START_REF] Akkad | An Efficient Non-Blind Steering Vector Estimation Technique For Robust Adaptive Beamforming With Multistage Error Feedback[END_REF] as follows:

e 1 (k) = d(k) -w H 1 (k)x 1 (k) e 2 (k) = d(k) -w H 2 (k)x 2 (k) e t (k) = e 1 (k) -e 2 (k -1) (3.4)
where w 1 (k), x 1 (k) and w 2 (k), x 2 (k) are the first and second stage filter weight and input vector, respectively. As such, in this section, we select some of the popular algorithms and provide an overview of their mathematical structure, their performance and their computational complexity while listing their advantages and drawbacks.

MVDR Algorithm for Beamforming

The minimum variance distortionless response (MVDR) beamformer maximizes the output SINR by minimizing the interference and noise power (variance), while preserving a distortionless response in the direction of the signal of interest [START_REF] Vorobyov | Principles of Minimum Variance Robust Adaptive Beamforming Design[END_REF][START_REF] Akkad | An Efficient Non-Blind Steering Vector Estimation Technique For Robust Adaptive Beamforming With Multistage Error Feedback[END_REF]. The output SINR is given by:

SIN R = E[|w H s(k)| 2 ] E[|w H (i(k) + n(k))| 2 ] = σ 2 d |w H a(θ)| 2 w H R i+n w (3.5)
where |.| is the complex modulus, a(θ) is the array steering vector in function a known reference angle of arrival (AOA), σ 2 d is the desired signal variance and R i+n is the N × N interference plus noise co-variance matrix defined as [START_REF] Akkad | An Efficient Non-Blind Steering Vector Estimation Technique For Robust Adaptive Beamforming With Multistage Error Feedback[END_REF][START_REF] El-Keyi | Robust Adaptive Beamforming Based on the Kalman Filter[END_REF]. Thus, the MVDR problem can be formulated, with respect to (3.5), as:

R i+n = E[(i(k)+n(k))(i(k)+n(k)) H ] [11,
min w w H R i+n w st w H a(θ) = 1 (3.6)
From (3.6), the optimal weight vector w M V DR can be computed as:

w M V DR = R -1 i+n a(θ) a H (θ)R -1 i+n a(θ) (3.7)
From (3.7), it is clear that the MVDR beamformer steers its main beam and nulls with respect to a known reference AOA, i.e. spatial referencing. Additionally, the unknown interference plus noise co-variance matrix R i+n can be replaced by its estimate R i+n . However, the accuracy of the estimation depends on the length of the training sequence available [START_REF] Vorobyov | Principles of Minimum Variance Robust Adaptive Beamforming Design[END_REF][START_REF] Vorobyov | Adaptive Beamforming with Joint Robustness Against Mismatched Signal Steering Vector and Interference Nonstationarity[END_REF][START_REF] El-Keyi | Robust Adaptive Beamforming Based on the Kalman Filter[END_REF]; Therefore, the data sample co-variance matrix estimate is computed 56

Adaptive Algorithms

using the following equation:

R i+n = 1 K K k=1 x(k)x H (k) (3.8)
where K is the number of training data samples. However, the MVDR does not provide any robustness against array calibration errors or look direction mismatch [2,[START_REF] Vorobyov | Principles of Minimum Variance Robust Adaptive Beamforming Design[END_REF][START_REF] Akkad | An Efficient Non-Blind Steering Vector Estimation Technique For Robust Adaptive Beamforming With Multistage Error Feedback[END_REF][START_REF] Allen | Adaptive Array Systems: Fundamentals and Applications[END_REF]. Moreover, the resulting estimate, R i+n , also includes the desired signal component and presents additional ambiguity [2,4,[START_REF] Akkad | An Efficient Non-Blind Steering Vector Estimation Technique For Robust Adaptive Beamforming With Multistage Error Feedback[END_REF]. In order to provide additional robustness against random mismatch errors, a robust MVDR beamformer is proposed in [START_REF] Vorobyov | Principles of Minimum Variance Robust Adaptive Beamforming Design[END_REF][START_REF] El-Keyi | Robust Adaptive Beamforming Based on the Kalman Filter[END_REF]. The robust MVDR algorithm update the minimization problem described by (3.6) in order to include additional constraints not only for the preset steering vector and look direction but for all other vectors belonging to the set of Ψ(ε) = {c m |c m = a + e m , ||e m || ≤ ε} to become [START_REF] El-Keyi | Robust Adaptive Beamforming Based on the Kalman Filter[END_REF]:

min w w H R i+n w s.t. |w H c m |≥ 1 ∀c m ∈ Ψ(ε) (3.9)
where ||.|| denotes the vector Frobenius norm, e m is the mismatch error in the steering vector and c m is the erroneous steering vector. However, the optimization problem in (3.9) describes an infinite number of non convex constraints [START_REF] El-Keyi | Robust Adaptive Beamforming Based on the Kalman Filter[END_REF] and is reformulated to a single constraint corresponding to the worst case mismatch as a second order cone programming (SOCP) problem [START_REF] El-Keyi | Robust Adaptive Beamforming Based on the Kalman Filter[END_REF], such as:

min w w H R i+n w st w H a ≥ ε||w|| + 1 (3.10)
The SOCP based robust MVDR described in (3.10) is computationally intensive and of order O(N 3 ) [START_REF] El-Keyi | Robust Adaptive Beamforming Based on the Kalman Filter[END_REF].

Least-Mean Square (LMS) Algorithm

The least mean square (LMS) algorithm, was first introduced by Widrow and Hoff in [START_REF] Widrow | The Complex LMS Algorithm[END_REF] and is the realization of the steepest descent optimization method by means of a stochastic gradient [2,3,4]. the LMS minimizes the mean square error (MSE) as a cost function [START_REF] Widrow | The Complex LMS Algorithm[END_REF][START_REF] Mandic | On The Intrinsic Relationship Between The Least Mean Square And Kalman Filters [Lecture Notes[END_REF][START_REF] Kim | Performance Analysis Of The Adjusted Step Size NLMS Algorithm[END_REF], to estimate the optimal filter weight, i.e. the Wiener solution. The MSE cost function, ξ LM S , is defined by:

ξ LM S (k) = E[|e LM S (k)| 2 ] = E[e LM S (k)e * LM S (k)] (3.11)
where e LM S (k) is the error signal and d(k) is the reference signal. Moreover, equation (3.11) can be expanded as:

E[|e LM S (k)| 2 ] = E[|d(k)| 2 ] -p H w(k)-w H (k)p + w H (k)Rw(k) (3.12)
Equation (3.12) is a quadratic equation in function of the array weight vector w(k), the input signal auto correlation matrix R and the input signal and desired signal cross correlation vector p. Therefore, the optimal weight vector, w oplms , of w(k), assuming a wide sense stationary (WSS) process, can be obtained by differentiating (3.12) with respect to w H (k) [5,[START_REF] Srar | Adaptive Array Beam Forming Using A Combined RLS-LMS Algorithm[END_REF][START_REF] Bouboulis | Extension of Wirtinger's Calculus To Reproducing Kernel Hilbert Spaces And The Complex Kernel LMS[END_REF], and setting the resulting LMS gradient, ∇ LM S , to zero, such as:

∇ LM S = ∂ξ LM S (k) ∂w H (k) = -p + Rw(k) (3.13)
Hence w oplms becomes:

w op = R -1 p (3.14)
The LMS error and weight update equations are obtained as follows:

e LM S (k) = d(k)-y(k) (3.15) w(k + 1) = w(k) + µ LM S e * LM S (k)x(k) (3.16)
where µ LM S stands for the gradient descent step or the step size [4,[START_REF] Akkad | A Multi-Stage Parallel LMS Structure and its Stability Analysis Using Transfer Function Approximation[END_REF][START_REF] Mandic | On The Intrinsic Relationship Between The Least Mean Square And Kalman Filters [Lecture Notes[END_REF][START_REF] Kim | Performance Analysis Of The Adjusted Step Size NLMS Algorithm[END_REF]. To ensure stable performance and convergence, the upper bound of the step size, µ LM S , is given with respect to the stability analysis conducted in [2] as:

µ LM S < 1 λ R,max (3.17)
where λ R,max is the maximum eigenvalue of R. Thus, to ensure the convergence and the stability of LMS the step size µ LM S must satisfy (3.17). While LMS offers minimal computational complexity, of order O(N ), it suffers from a trade off between its convergence speed and its error floor [4].

Several variants of the classical LMS have been proposed to improve its performance by eliminating the trade off between its convergence speed and steady state error [4]. This includes, and is not limited to, the normalized LMS (NLMS) [START_REF] Van Veen | Beamforming: A Versatile Approach To Spatial Filtering[END_REF][START_REF] Nascimento | The Normalized LMS Algorithm With Dependent Noise[END_REF], variable step size LMS (VSSLMS) [START_REF] Gorriz | Speech Enhancement in Discontinuous Transmission Systems Using the Constrained-Stability Least Mean Squares Algorithm[END_REF][START_REF] Xiubing | A New Modified Robust Variable Step Size LMS Algorithm[END_REF][START_REF] Shengkui | A Fast Variable Step-Size LMS Algorithm with System Identification[END_REF][START_REF] Kwong | A Variable Step Size LMS Algorithm[END_REF][START_REF] Aboulnasr | A Robust Variable Step-Size LMS-Type Algorithm: Analysis and Simulations[END_REF], the modified robust variable step size LMS (MRVSS) algorithm [START_REF] Lobato | Stochastic Modeling of the Transform-Domain εLMS Algorithm[END_REF] and the least mean square -least mean square algorithm (LLMS) [5]. In NLMS, the authors in [START_REF] Van Veen | Beamforming: A Versatile Approach To Spatial Filtering[END_REF][START_REF] Nascimento | The Normalized LMS Algorithm With Dependent Noise[END_REF] proposed adjusting the step size, µ, in accordance with the input signal power through auto-correlation, thus allowing faster convergence. However, NLMS, suffers degraded performance in low SINR environments due to the reduction in the step size [5], additionally, the systems performance is highly dependent on the choice of its initial parameters. In contrast, the VSSLMS variant described in [START_REF] Xiubing | A New Modified Robust Variable Step Size LMS Algorithm[END_REF] begins the adaptation process with respect to a large step size decremented as the algorithm approaches its steady state. Such technique allows accelerated convergence and a lower steady state error, however at the cost of a high increase in computational complexity [START_REF] Srar | A New LLMS Algorithm for Antenna Array Beamforming[END_REF]. Despite the suggested modifications, the NLMS and VSSLMS algorithms still suffer from degraded performance in low SINR conditions [START_REF] Srar | A New LLMS Algorithm for Antenna Array Beamforming[END_REF]. Thus, to further increase their robustness, the authors in [START_REF] Lobato | Stochastic Modeling of the Transform-Domain εLMS Algorithm[END_REF] proposed the MRVSS LMS algorithm. In comparison, the MRVSS has shown satisfactory robustness against added noisy and when operated in non stationary environments. However, the MVRSS technique results in a considerable increase in the computational complexity and its performance also depends on particular system environments [5].

In LLMS a multi stage structure is proposed for improving the convergence rate while simultaneously reducing the residual error of a classical LMS [5]. LLMS is achieved by cascading two LMS stages by the use of an estimate of the adaptive array vector and error feedback. This technique shows superior performance over previously discussed LMS variants, however at the cost of doubling the computational complexity and the introduction of a division operation with respect to the classical LMS [4,5].

Recursive Least-Square (RLS) Algorithm

The RLS algorithm updates the arrays weight vector based on the minimization of a cost function, i.e. the sum of squared errors, ξ RLS , for a known sampling window [6,[START_REF] Akkad | An Efficient Non-Blind Steering Vector Estimation Technique For Robust Adaptive Beamforming With Multistage Error Feedback[END_REF][START_REF] Srar | Adaptive Array Beam Forming Using A Combined RLS-LMS Algorithm[END_REF] and is given by:

ξ RLS = k i=1 α k-1 |e RLS (k -1)| 2 (3.18)
where the error signal, e RLS (k), is defined as e RLS (k) = d(k) -y(k) and α ∈ [0, 1] is the exponentially weighted forgetting factor [6]. Hence, the weight vector update formula becomes:

e RLS (k) = d(k) -w H (k)x(k) (3.19) L(k) = α -1 Q -1 (k -1) 1 + α -1 x H (k)Q -1 (k -1)x(k) (3.20) w(k) = w(k -1) + L(k)x(k)e * RLS (k) (3.21)
where L(k) is the gain matrix. The inverse signal auto-correlation matrix Q -1 (k) and the weight vector w(k -1) are defined as follows [START_REF] Srar | Adaptive Array Beam Forming Using A Combined RLS-LMS Algorithm[END_REF]:

Q -1 (k) = α -1 Q -1 (k -1) - α -2 Q -1 (k -1)x(k)x H (k)Q -1 (k -1) 1 + α -1 x H (k)Q -1 (k -1)x(k) (3.22) z(k) = k i=1 α k-i p(k) (3.23) Q(k) = k i=1 α k-i R(k) (3.24)
While the RLS provides greater convergence, compared to the LMS it suffers from an increased computational complexity, of O(N 2 ), lacks robustness against fixed point arith-metic, i.e. underflow and divide by zero and does not provide user tracking capabilities [2,6,[START_REF] Akkad | An Efficient Non-Blind Steering Vector Estimation Technique For Robust Adaptive Beamforming With Multistage Error Feedback[END_REF][START_REF] Srar | Adaptive Array Beam Forming Using A Combined RLS-LMS Algorithm[END_REF][START_REF] Meyer-Baese | Digital Signal Processing with Field Programmable Gate Arrays (Signals and Communication Technology)[END_REF]. Several variants have been proposed for maintaining an accelerated convergence profile and providing a tracking ability in time varying environments for the classical RLS [START_REF] Srar | Adaptive Array Beam Forming Using A Combined RLS-LMS Algorithm[END_REF]. These techniques include, and are not limited to, the adaptive forgetting factor RLS algorithm (AFF-RLS) [START_REF] Lee | A Low-Complexity AFF-RLS Algorithm Using a Normalization Technique[END_REF], the variable forgetting factor RLS (VFFRLS), the extended recursive least square (EX-KRLS) algorithm [5], the recursive least mean square (RLMS) [START_REF] Srar | Adaptive Array Beam Forming Using A Combined RLS-LMS Algorithm[END_REF] and the parallel RLMS [6]. However, the improvement in the tracking ability of the RLS when implementing the AFF-RLS, the VFFRLS and the EX-KRLS algorithms is achieved at the cost of a considerably large increase in computational complexity [6,[START_REF] Srar | Adaptive Array Beam Forming Using A Combined RLS-LMS Algorithm[END_REF]. In contrast, the RLMS structure achieves an accelerated convergence with superior tracking capabilities compared to other modifications, by means of a multi-stage algorithm [START_REF] Akkad | An Efficient Non-Blind Steering Vector Estimation Technique For Robust Adaptive Beamforming With Multistage Error Feedback[END_REF]. RLMS employs a RLS stage followed by a LMS stage separated by an estimate of the array image vector and connected by an error feedback. This technique shows superior performance over previously discussed LMS and RLS variants however at the cost of an increase in the computational complexity.

RLMS Adaptive Beamformer

The Recursive-Least mean square (RLMS) algorithm is formed of a RLS stage followed by a LMS stage separated by an estimate of the array image vector. The two stages algorithms are connected by a delayed error feedback [START_REF] Srar | Adaptive Array Beam Forming Using A Combined RLS-LMS Algorithm[END_REF] as shown in Figure 3.2 where the block z -1 represents a one sample delay. In RLMS, the output of the first stage RLS 1 , y RLS1 (k), is multiplied by the estimate of the desired signal steering vector âd (k), forming the input, x 2 (k), to the second LM S 2 stage. Moreover, âd (k), is given by its stochastic approximation near convergence in its instantaneous form, detailed in Appendix A, [START_REF] Akkad | An Efficient Non-Blind Steering Vector Estimation Technique For Robust Adaptive Beamforming With Multistage Error Feedback[END_REF][START_REF] Srar | Adaptive Array Beam Forming Using A Combined RLS-LMS Algorithm[END_REF] as:

âd,m w 1,m (k)x 1,m (k) w 1,m (k)y RLS1 + ϑ (3.25)
where âd,m is the m th elements of the complex steering vector approximate âd (k) and ϑ is a small constant introduced to mitigate a division by zero [5,[START_REF] Akkad | An Efficient Non-Blind Steering Vector Estimation Technique For Robust Adaptive Beamforming With Multistage Error Feedback[END_REF] such that:

0 < ϑ |y RLS1 | N N m=1 |w 1,m | (3.26)
where w 1,m (k), x 1,m (k) and âd,m are the RLS 1 tap weights, input signal and the estimate of the m th antenna element of the complex steering vector ãd at the time instant k with m ∈ {1, 2, 3.......N }. Hence, the input to the m th antenna element for the LM S 2 stage, x 2 ,m (k), is derived in [5,[START_REF] Srar | Adaptive Array Beam Forming Using A Combined RLS-LMS Algorithm[END_REF] as:

x 2,m (k) = w 1,m (k)x 1,m (k) w 1,m (k)y RLS1 (k) + ϑ y RLS1 (k) (3.27)
Moreover, a delayed version of the error signal e 2 (k) of the LM S 2 stage is fed-back to combine with that of the RLS 1 to form the overall error signal e RLM S (k) used to update the main tap weights of the RLS 1 stage. The overall error signal and the RLMS weight update equation, with respect to (3.21), becomes [START_REF] Srar | Adaptive Array Beam Forming Using A Combined RLS-LMS Algorithm[END_REF]:

e RLM S (k) = e 1 (k) -e 2 (k -1) (3.28) w 1 (k) = w 1 (k -1) + L(k)x 1 (k)e * RLM S (k) (3.29)
While the RLMS presents an accelerated convergence and superior tracking abilities, its cascaded form introduces high latency when targeting a hardware implementation with a division operation such as in (3.25). Furthermore, the system complexity is of order

O(N 2
) and is increased by that of the LMS stage and an additional 20N multiplications, 6N additions and 2N divisions for the steering vector estimate in (3.25). Consequently, the cascading nature of the RLMS introduces high latency, given the second stage dependency on the steering vector estimate block, making it difficult to be implemented in a parallel and pipeline architecture [4,[START_REF] Shanbhag | Relaxed Look-Ahead Pipelined LMS Adaptive Filters And Their Application To ADPCM Coder[END_REF][START_REF] Akkad | Two Stages Parallel LMS Structure A Pipelined Hardware Architecture[END_REF].

Parallel RLMS Adaptive Beamformer

In order to present a low latency, division free architecture, suitable for a parallel implementation, we propose in [6] a two-stage parallel input RLMS (RLMSp) structure, as shown in Figure 3.3, where jz -1 denotes a multiplication by the imaginary number j with respect to a one sample delay. From Figure 3.3, it is clear that the LM S 2 input is the signal samples and no longer a reconstructed input dependent on the array steering vector estimation. Moreover, the LM S 2 error signal e 2 (k) is now multiplied by the complex number j to protect against nulls and recurring samples [4]. The overall RLMSp error signal, e RLM Sp (k), and weight update equations are [START_REF] Srar | Adaptive Array Beam Forming Using A Combined RLS-LMS Algorithm[END_REF]:

e RLM Sp (k) = e 1 (k) -je 2 (k -1) (3.30) w 1 (k) = w 1 (k -1) + L(k)x(k)e * RLM Sp (k) (3.31)
Recurring samples in the input and/or desired signals are usually formed as a consequence of repeated samples in the original message signal, analog to digital converter (ADC) impurities [START_REF] Zoubir | Array and Statistical Signal Processing[END_REF], quantization errors [START_REF] Shang | Digital Beamforming Based On FPGA For Phased Array Radar[END_REF][START_REF] Seneviratne | Multidimensional-DSP Beamformers Using the ROACH-2 FPGA Platform[END_REF][START_REF] Jing | Performance Analysis Of Multi-Rate Signal Processing Digital Filters On FPGA[END_REF], low resolution resulting in receivers saturation [4,[START_REF] Farina | Effect of ADC and Receiver Saturation On Adaptive Spatial Filtering Of Directional Interference[END_REF] and of symbol detection errors originated from the digital receivers in low signal to noise ratio (SNR) environments [4,[START_REF] Theodore | Wireless Communications: Principles and Practice[END_REF]. As such, in the adopted delay feedback method described by (3.28), recurring samples can result in error nulls and severely degrade the convergence performance of the RLMSp [4,6,[START_REF] Akkad | A Multi-Stage Parallel LMS Structure and its Stability Analysis Using Transfer Function Approximation[END_REF][START_REF] Akkad | Two Stages Parallel LMS Structure A Pipelined Hardware Architecture[END_REF]. As an example, we consider a sample of the desired signal vector, d, taken at instances k and k -1, respectively and represented in its complex form such as:

d(k) = a 1 + jb 1 (3.32) d(k -1) = a 2 + jb 2 (3.33)
Moreover, the modified RLMS and RLMSp desired signals, S RLM S (k) and S RLM Sp (k), with respect to (3.28) and (3.30), are:

S RLM S (k) = d(k) -d(k -1) (3.34) S RLM Sp (k) = d(k) -jd(k -1) (3.35)
For recurring samples, i.e.

d(k) ≈ d(k -1) we get a 1 ≈ a 2 and b 1 ≈ b 2 , thus S RLM S ≈ 0.
However, the RLMSp overall reference signal, S RLM Sp (k), becomes:

S RLM Sp (k) = a 1 + jb 1 -ja 2 + b 2 = 0 (3.36)
Therefore, from (3.36), the multiplication by the imaginary number j improves the systems robustness against repeated samples [4]. By eliminating the need for a steering vector estimate stage, the RLMSp complexity, compared to the RLMS, is reduced by 20N multiplications, 6N additions and 2N divisions. However, the RLMSp computational complexity is still of order O(N 2 ) and its pipeline remains difficult due to the presence of error feedback paths [4,[START_REF] Shanbhag | Relaxed Look-Ahead Pipelined LMS Adaptive Filters And Their Application To ADPCM Coder[END_REF][START_REF] Akkad | Two Stages Parallel LMS Structure A Pipelined Hardware Architecture[END_REF].

LLMS Adaptive Beamformer

The least mean square-least mean square (LLMS) algorithm is a multi-stage LMS separated by an estimate of the array steering vector [5,[START_REF] Srar | A New LLMS Algorithm for Antenna Array Beamforming[END_REF] as shown in Figure 3

x 2,m (k) = w 1,m (k)x 1,m (k) w 1,m (k)y LM S1 (k) + ϑ y LM S1 (k) (3.37)
Moreover, a delayed version of the error signal e 2 (k) of the LM S 2 stage is fed-back to combine with that of the LM S 1 and form the overall error signal e LLM S (k) used to update the main tap weights of the LM S 1 stage. As such, the LLMS overall error and weight update equations are presented as [5,[START_REF] Srar | A New LLMS Algorithm for Antenna Array Beamforming[END_REF]:

e LLM S (k) = e 1 (k) -e 2 (k -1) (3.38) w 1 (k + 1) = w 1 (k) + µ 1 e * LLM S (k)x 1 (k) (3.39)
The input and desired signals are assumed independent and identically distributed (i.i.d) with zero mean. The process is assumed WSS with no temporal correlation between samples [5].

While the LLMS presents an accelerated convergence with a low steady state error, it does not ensure the same convergence properties against recurring/repeated samples, i.e.

x(k) ≈ x(k -1) and d(k) ≈ d(k -1). Recurring samples are formed as a consequence of a high sampling frequency or re-transmission for robustness. Also, its cascading structure introduces a large increase in computational complexity and latency [4]. Furthermore, the system complexity is increased by an additional 20N real multiplications, 6N real additions and 2N real divisions for the steering vector estimate in (3.25). Consequently, the division operator affects the systems stability when targeting a hardware implementation [START_REF] Akkad | Twiddle Factor Generation Using Chebyshev Polynomials and HDL for Frequency Domain Beamforming[END_REF], i.e. possibility of division by zero in finite precision arithmetic. Similar to the RLMS, the cascading nature of the LLMS introduces a high latency, given the dependency on two error feedback paths, making it difficult to be implemented in a pipeline architecture [4,[START_REF] Shanbhag | Relaxed Look-Ahead Pipelined LMS Adaptive Filters And Their Application To ADPCM Coder[END_REF][START_REF] Akkad | Two Stages Parallel LMS Structure A Pipelined Hardware Architecture[END_REF].

Algorithm Initial Parameters LMS µ LM S = 0.04 RLS α = 0.98, L(0) = 0.5I, Q(0) = 0.025I VFFRLS λ max = 1, γ V F F = 1.5, k α = k β = 6 ε V F F = 1, δ = 1 MRVSS ẽmax = 1, ẽmin = 0, ν = 5 × 10 -4 µ max = 0.2 , µ min = 10 -4 Initially: µ M RV SS = µ max , α = η = 0.97 γ = 4.8 × 10 -4 RLMS α = 0.98, L(0) = 0.5I, Q(0) = 0.025I µ LM S2 = 0.2, ϑ = 0.0004 LLMS µ LM S1 = 0.04, µ LM S2 = 0.04, ϑ = 0.0004 RLMSp α = 0.98, L(0) = 0.5I, Q(0) = 0.025I µ LM S2 = 0.2

Comparison and Discussion

The simulation setups for evaluating the performance of the previously listed algorithms are as follows:

-ULA array with N = 8 antenna elements.

-A message signal and two interferes arriving at AOA of 30 • , 45 • and 80 • , respectively.

The inputs are generated as independent random complex Gaussian sequences [4,[START_REF] Clarkson | Simplified Analysis Of The LMS Adaptive Filter Using A Transfer Function Approximation[END_REF] of the form v m = v 1 + jv 2 , where v 1 and v 2 are taken from a normal (Gaussian) distribution with zero mean and variance σ 2 of the form N (0, σ 2 p ) and N (0, σ 2 q ), respectively, where, σ p = 0.1 and σ q = 0.2. The subscripts p and q denote in-phase and quadrature, out of phase, respectively [4].

-With respect to the simulation criteria in [5], and since the pilot, training, signal is known, the desired signal d(k), is considered as a copy of the message signal corrupted by CAWGN noise with a signal to noise ratio of SNR = 5 dB and SNR = 10 dB, respectively.

The initial parameters were chosen similar to that selected in [5,[START_REF] Srar | Adaptive Antenna Array Beamforming Using a Concatenation of Recursive Least Square and Least Mean Square Algorithms[END_REF] and are presented in Table 3.1 where I is a N × N identity matrix. The simulation is conducted following a Monte Carlo approach [4] with 150 realizations of 150 samples each and the performance of the adaptive algorithms is evaluated with respect to the resulting MSE. From Figure 3.5, all algorithms achieved convergence for a SNR = 10 dB. In contrast to the other variants, it can be seen, that only the LLMS and RLMS achieved their convergence from the 2 nd iteration with a minimal steady state error, i.e. MSE < 0.01.

To better assess their behavior in noisy environments, the simulations were repeated for a SNR = 5 dB. 3.2, presents a comparison of resource complexity where cMultiply, cAdd, cDivide define as complex multiplication, addition or division, respectively. From Table 3.2, it is clear that the RLMS, RLMSp and RLS require an undesirable complexity of order O(N 2 ) and the need of a division operation. On the other hand, only the LLMS achieved accelerated convergence and low steady error in low SNR comparison with a complexity of order O(N ). However, compared to the LMS, the LLMS doubles its resource requirements in addition to N complex divisions [4].

Algorithm cMultiply cAdd cDivide RLMS[15] 3N 2 + 11N + 2 2N 2 + 9N + 6 N + 1 RLMSp[6] 3N 2 + 7N + 1 2N 2 + 6N + 3 1 RLS 3N 2 + 5N 2N 2 + 4N + 2 1 LLMS[5] 6N + 2 5N + 4 N LMS 2N + 1 2N + 1 0
Table 3.2 -Theoretical Complexity and Resource Usage

Conclusion

In this chapter, we introduced the different classes of beamforming algorithms, i.e. nonblind, semi-blind and blind. Additionally, we presented an overview of the most popular non-blind temporal and spatial referenced adaptive algorithms and some of their variants, while listing the advantages and disadvantages of each. To further illustrate their behavior and convergence properties, many simulations were conducted with respect to random complex Gaussian input sequences. The output MSE plot was used to validate and compare the algorithms performance, in terms of convergence speed and steady state error, for different SNR environments. Thus, in contrast to the LMS, RLS and their variants, only the LLMS achieved superior performance through an accelerated convergence and low steady state error profile. However, while the LLMS preserved an order O(N ) complexity, it still requires N complex divisions for the steering vector estimate. Additionally, the cascading nature of the LLMS and the error feedback paths makes it difficult to be implemented in a parallel and pipeline architecture. As such, our main motivation is to present a reduced complexity multi stage LMS variant suitable for a parallel pipeline hardware implementation while maintaining accelerated convergence, low steady state error and robustness against low SNR environments. The work conducted for the RLMSp has been published in the European Signal Processing Conference (EUSIPCO).

Chapter 4

OVERVIEW OF DIGITAL SIGNAL PROCESSING IMPLEMENTATION TECHNIQUES ON EMBEDDED SYSTEMS

Introduction

Signal processing is a multidisciplinary field of study and have become a vital technology in many modern applications [START_REF] Meyer-Baese | Digital Signal Processing with Field Programmable Gate Arrays (Signals and Communication Technology)[END_REF][START_REF] Woods | FPGA-Based Implementation of Signal Processing Systems[END_REF]. Applications embodying signal processing tasks and routines are endless, and rely on both analog and digital processes, however by the end of the 20 th century this discipline have become increasingly dominated by the digital field [START_REF] Woods | FPGA-Based Implementation of Signal Processing Systems[END_REF][START_REF] Tessier | Reconfigurable Computing for Digital Signal Processing: A Survey[END_REF]. Some examples of common digital signal processing (DSP) dependent areas are but not limited to: communication [4], machine learning [START_REF] Burgos | Adaptive Beamforming For Moving Targets Using Genetic Algorithms[END_REF], biomedical and healthcare [START_REF] Boschmann | Fpga-Based Acceleration of High Density Myoelectric Signal Processing[END_REF], radar or sonar imaging [START_REF] Akkad | Constant Time Hardware Architecture for a Gaussian Smoothing Filter[END_REF][START_REF] Akkad | FPGA Hardware Architecture for Stereoscopic Image Compression Based on Block Matching, Watermarking and Hamming Code[END_REF], instrumentation [START_REF] Zoubir | Array and Statistical Signal Processing[END_REF], information technology [START_REF] Mkhinini | HLS Design of a Hardware Accelerator for Homomorphic Encryption[END_REF][START_REF] Migliore | Fast Polynomial Arithmetic for Somewhat Homomorphic Encryption Operations in Hardware with Karatsuba Algorithm[END_REF][START_REF] Akkad | Hardware Architecture for a Bit-Serial Odd-Even Transposition Sort Network[END_REF][START_REF] Ayoubi | Hardware Architecture For A Shift-Based Parallel Odd-Even Transposition Sorting Network[END_REF] and seismology [2].

Historically, electronic signals and radio waves were processed and exchanged in their analog form, with the use of analog chips, filters and amplifiers, and with minimal control over information quality and reliability [START_REF] Woods | FPGA-Based Implementation of Signal Processing Systems[END_REF][START_REF] Tessier | Reconfigurable Computing for Digital Signal Processing: A Survey[END_REF]. However, the emergence of new technologies in the 1960s and 1970s, i.e. satellite transmission, pushed the adopted analog signal processing design methodology and its components to their limits [START_REF] Woods | FPGA-Based Implementation of Signal Processing Systems[END_REF]. An example of a satellite transmission system is the broadcasting station: Pleumeur-Bodou Ground Station in north-west France. As shown in Figure 4.1 [START_REF] Des Telecoms | Antenne PB1 Sous RADOME[END_REF][START_REF] De Gouyon Matignon | Pleumeur-Bodou and the French CNET[END_REF], the ground station and its antenna occupied a tremendous amount of space and resources to build [START_REF] De Gouyon Matignon | Pleumeur-Bodou and the French CNET[END_REF]. Moreover, in order to detect and estimate the signal of interest with respect to the incoming sub-GHz high frequency noisy signal, a data acquisition system was implemented by means of multi-stage analog signal amplifiers and filters with a dedicated cooling unit [START_REF] De Gouyon Matignon | Pleumeur-Bodou and the French CNET[END_REF].

As such, the rapid advancements in signal processing [START_REF] Woods | FPGA-Based Implementation of Signal Processing Systems[END_REF][START_REF] Tessier | Reconfigurable Computing for Digital Signal Processing: A Survey[END_REF] exhausted the use of analog circuitry designs by imposing tighter constraints reflected by the need of a low cost, real-time processing system [START_REF] Tessier | Reconfigurable Computing for Digital Signal Processing: A Survey[END_REF]. In compliance with these advancements, and with the introduction of the programmable, finite precision, DSP processor (PDSP), the field of DSP have emerged to become the newly adopted signal processing design methodology [START_REF] Meyer-Baese | Digital Signal Processing with Field Programmable Gate Arrays (Signals and Communication Technology)[END_REF][START_REF] Tessier | Reconfigurable Computing for Digital Signal Processing: A Survey[END_REF].

In this chapter, we present an overview of the popular hardware used for implementing signal processing routines, i.e. PDSP, field programmable gate array (FPGA) and system on a chip (SoC). Additionally, we discuss the different DSP implementation techniques and tools used, i.e. hardware description language (HDL), high level synthesis tools (HLS) and open computing language (openCL). Furthermore, we propose a high precision, low complexity, pipeline, dynamic fast Fourier transform (FFT) twiddle factor generation architecture using Chebyshev polynomials [START_REF] Akkad | Twiddle Factor Generation Using Chebyshev Polynomials and HDL for Frequency Domain Beamforming[END_REF]. Finally, we compare the performance of the different design techniques and utilized hardware through the implementation of popular signal processing routines, i.e. the FFT and the least mean square (LMS) algorithm.

Embedded Systems for Digital Signal Processing (DSP) Applications

One of the most trivial signal processing tasks is filtering. Filters are used to mathematically modify the content of a signal, through the use of multiplication and addition, in order to either extract or dispose of information or noise [START_REF] Meyer-Baese | Digital Signal Processing with Field Programmable Gate Arrays (Signals and Communication Technology)[END_REF]. A major contributor to the acceleration of DSP development in the 1970s was the introduction of the PDSP capable of performing a single, fixed point, multiply accumulate (MAC) routine in one clock cycle [START_REF] Meyer-Baese | Digital Signal Processing with Field Programmable Gate Arrays (Signals and Communication Technology)[END_REF]. As a result, a broad range of dedicated signal processing hardware and design tools have been put forth to pave the way for the development of atomic, fine grained [START_REF] Tessier | Reconfigurable Computing for Digital Signal Processing: A Survey[END_REF][START_REF] Mueller | Data Processing on FPGAs[END_REF], signal processing routines and hardware architectures [START_REF] Meyer-Baese | Digital Signal Processing with Field Programmable Gate Arrays (Signals and Communication Technology)[END_REF][START_REF] Tessier | Reconfigurable Computing for Digital Signal Processing: A Survey[END_REF][START_REF] Mueller | Data Processing on FPGAs[END_REF]. A general DSP architecture is presented in As shown in Figure 4.2, the DSP system is generally formed of an input analog filter usually acting as an anti-aliasing filter with respect to the sampling frequency f s and the Nyquist theorem [START_REF] Meyer-Baese | Digital Signal Processing with Field Programmable Gate Arrays (Signals and Communication Technology)[END_REF]. The anti aliasing filter removes unwanted mirror frequencies to avoid data ambiguity. The resulting signal is then fed to an analog to digital converter (ADC) which in turn samples and converts the continuous analog signal, x c (t), where t is a time instance, into its equivalent discrete digital form [START_REF] Farina | Effect of ADC and Receiver Saturation On Adaptive Spatial Filtering Of Directional Interference[END_REF][START_REF] Meyer-Baese | Digital Signal Processing with Field Programmable Gate Arrays (Signals and Communication Technology)[END_REF][START_REF] Seneviratne | Multidimensional-DSP Beamformers Using the ROACH-2 FPGA Platform[END_REF][START_REF] Jing | Performance Analysis Of Multi-Rate Signal Processing Digital Filters On FPGA[END_REF]. The resulting digital output vector

x d [k],
where k is a discrete sample time index, is then collected by the DSP processor, i.e. PDSP, FPGA, SoC..., to perform the desired steps and mathematical procedures that would have been previously handled by an analog circuit [START_REF] Meyer-Baese | Digital Signal Processing with Field Programmable Gate Arrays (Signals and Communication Technology)[END_REF]. The final stage of the data flow is the processed signals output, hence as shown, the desired output can be obtained in its digital form for later storage and processing or converted to its Partie , Chapter 4 -Overview of Digital Signal Processing Implementation Techniques on Embedded Systems original analog form through the use of a digital to analog converter (DAC), i.e. audio output [START_REF] Meyer-Baese | Digital Signal Processing with Field Programmable Gate Arrays (Signals and Communication Technology)[END_REF].

Parallel to these developments, programmable processors and VLSI technology are quickly evolving towards the design of heterogeneous systems with high performance, application specific multi core architecture [START_REF] Mueller | Data Processing on FPGAs[END_REF]. Thus, in this section, we present a summary of the popular and currently adopted processors, i.e. PDSP, FPGA and SoC.

Programmable DSP Processors (PDSP)

In the start of the 1980s, Texas Instruments introduced the first reduced instruction set computer (RISC) PDSP microprocessor that revolutionized the era of DSP [START_REF] Meyer-Baese | Digital Signal Processing with Field Programmable Gate Arrays (Signals and Communication Technology)[END_REF][START_REF] Tessier | Reconfigurable Computing for Digital Signal Processing: A Survey[END_REF]. In contrast to the first generation PDSP, based on the Von Neumann architecture, the second generation PDSP, based on the Harvard architecture, effectively separated the data memory from the program memory. Consequently, the RISC architecture allows independent and uninterrupted data communication between the processor pipeline and data memory bus [START_REF] Meyer-Baese | Digital Signal Processing with Field Programmable Gate Arrays (Signals and Communication Technology)[END_REF][START_REF] Tessier | Reconfigurable Computing for Digital Signal Processing: A Survey[END_REF]. Additionally, in contrast to general purpose processors, the PDSP are application specific and can operate in real time with a set of optimized DSP instruction set, i.e. fixed point computation, saturation and overflow control, overlapped data fetch and advanced addressing modes [START_REF] Tessier | Reconfigurable Computing for Digital Signal Processing: A Survey[END_REF][START_REF] Mueller | Data Processing on FPGAs[END_REF]. As such, the PDSP was capable of performing a fixed point MAC operation in a single clock cycle with a minimal overhead, considered the basis of digital filters and most DSP operations [START_REF] Meyer-Baese | Digital Signal Processing with Field Programmable Gate Arrays (Signals and Communication Technology)[END_REF].

Over the past three decades, DSP applications and requirements changed drastically and imposed challenging constraints on the limited resources PDSP [START_REF] Tessier | Reconfigurable Computing for Digital Signal Processing: A Survey[END_REF]. These constraints mainly focused on the need of providing a high speed parallel implementation given the parallel nature of the DSP algorithms. However, since PDSP are single core application specific processors with a pre determined instruction set and limited arithmetic units, it is impossible to reprogram their structure and redistribute resource usage. Moreover, a parallel implementation would require the use of many PDSP modules resulting in a dramatic increase in complexity and latency [START_REF] Tessier | Reconfigurable Computing for Digital Signal Processing: A Survey[END_REF][START_REF] Mueller | Data Processing on FPGAs[END_REF]. Thus, it has become of utmost importance to migrate for field programmable semiconductor chips, i.e. FPGA, that offer resource manipulation for implementing a parallel architecture [START_REF] Tessier | Reconfigurable Computing for Digital Signal Processing: A Survey[END_REF][START_REF] Mueller | Data Processing on FPGAs[END_REF].

Field Programmable Gate Arrays (FPGA) Processors

Field Programmable Gate Array or FPGA is a re-programmable semiconductor device formed of a 2D array of repeated digital configurable logic circuit blocks (CLB) connected by means of an interconnect fabric. Each CLB consists of four logic slices each containing a small number of look up tables, registers and a programmable switch box (SW) connecting the CLB to the internal fabric [START_REF] Meyer-Baese | Digital Signal Processing with Field Programmable Gate Arrays (Signals and Communication Technology)[END_REF][START_REF] Mueller | Data Processing on FPGAs[END_REF]. [START_REF] Chu | FPGA Prototyping by VHDL Examples: Xilinx Spartan-3 Version[END_REF]. Moreover, a Xilinx Spartan 3 FPGA logic cell is formed of a four input look up table, a register element, a carry circuit for arithmetic operations and a multiplexing circuit [START_REF] Chu | FPGA Prototyping by VHDL Examples: Xilinx Spartan-3 Version[END_REF].

The re-configurable nature of the FPGA logic cells allows implementing generic arbitrary and parallel, application specific architectures. A FPGA logic design is defined as a soft IP-core and can be modeled using a wide range of hardware and software design techniques [START_REF] Mueller | Data Processing on FPGAs[END_REF]. These techniques are and not limited to: circuit schematics, hardware description languages, i.e. VHDL, Verilog, SystemVerilog and traditional software languages, i.e. C, synthesized with the use of high level synthesis (HLS) tools, such as the Xilinx Vivado HLS compiler, Intel HLS tools and Matlab HDL toolbox [START_REF] Tessier | Reconfigurable Computing for Digital Signal Processing: A Survey[END_REF][START_REF] Nane | A Survey and Evaluation of FPGA High-Level Synthesis Tools[END_REF]. In addition to the traditional logic blocks, some FPGA families include a wide range of hard-IP, macro, Partie , Chapter 4 -Overview of Digital Signal Processing Implementation Techniques on Embedded Systems blocks for frequently used components and functionalities [START_REF] Mueller | Data Processing on FPGAs[END_REF][START_REF] Chu | FPGA Prototyping by VHDL Examples: Xilinx Spartan-3 Version[END_REF]. Some of the included hard-IP blocks are and not limited to: fast storage block random access memory (BRAM), input/output blocks (IOB), high speed dedicated multipliers, phase locked loop (PLL) blocks, embedded microprocessor, ADC and recently DSP specific blocks [START_REF] Meyer-Baese | Digital Signal Processing with Field Programmable Gate Arrays (Signals and Communication Technology)[END_REF][START_REF] Tessier | Reconfigurable Computing for Digital Signal Processing: A Survey[END_REF][START_REF] Mueller | Data Processing on FPGAs[END_REF]. As such, an important FPGA benchmark parameter is the repetition rate and represents the number of realization of the same block in a device [START_REF] Meyer-Baese | Digital Signal Processing with Field Programmable Gate Arrays (Signals and Communication Technology)[END_REF].

In modern FPGAs, manufacturers provide specific FPGA families and architectures for DSP related operation through the inclusion of a number of dedicated, transistor level, re-configurable DSP blocks [START_REF] Meyer-Baese | Digital Signal Processing with Field Programmable Gate Arrays (Signals and Communication Technology)[END_REF][START_REF] Tessier | Reconfigurable Computing for Digital Signal Processing: A Survey[END_REF][START_REF] Mueller | Data Processing on FPGAs[END_REF]. An example of a DSP block is shown in Figure 4.4 from [START_REF] Altera | Enabling High-Performance DSP Applications with Arria V or Cyclone V Variable-Precision DSP Blocks[END_REF], for the Altera Stratix V FPGA family. As shown in Figure 4.4, the Stratix V DSP block is configured in standard, 18 bits, precision mode while providing dedicated, high speed, arithmetic hardware and storage elements for computing popular DSP operations, i.e. MAC, pre-addition and complex multiplication [START_REF] Tessier | Reconfigurable Computing for Digital Signal Processing: A Survey[END_REF][START_REF] Mueller | Data Processing on FPGAs[END_REF][START_REF] Altera | Enabling High-Performance DSP Applications with Arria V or Cyclone V Variable-Precision DSP Blocks[END_REF]. The Stratix V, standard mode, DSP block allows the following multiplier configurations: -9 × 9 three independent multipliers. -Two 16 × 16 independent multipliers in sum mode.

-One 18 × 36 independent multiplier.

In addition to the presented, the Stratix V DSP block can be configured in high precision mode.

Figure 4.5 -Altera Stratix V Variable Precision DSP Block in High Precision Mode [START_REF] Altera | Enabling High-Performance DSP Applications with Arria V or Cyclone V Variable-Precision DSP Blocks[END_REF] As shown in Figure 4.5, the high precision mode configuration implements one 27 × 27 independent multiplier. As such, the use of re-configurable devices in the deployment of DSP algorithms promises immeasurable aid in the advancement of the applications they embody [START_REF] Woods | FPGA-Based Implementation of Signal Processing Systems[END_REF][START_REF] Tessier | Reconfigurable Computing for Digital Signal Processing: A Survey[END_REF]. Thus, the main benefits adopting re-configurable computing techniques and devices for DSP can be summarized as:

-Implementing a dedicated and specialized architecture.

-Allowing low cost on field full or partial re-configuration.

-Implementing fine-grained [START_REF] Meyer-Baese | Digital Signal Processing with Field Programmable Gate Arrays (Signals and Communication Technology)[END_REF] parallel pipeline architecture.

However, recent trends in DSP applications require the use of complex algorithms, i.e. adaptive, statistical, in parallel with real time data acquisition, processing and decision making routines. As such, modern FPGA families are coupled with a high performance Partie , Chapter 4 -Overview of Digital Signal Processing Implementation Techniques on Embedded Systems multi-core hard intellectual property (IP) microprocessor, i.e. ARM Cortex A9, with a ready to use real time operating system. The FPGA and hard embedded processor architecture is referred to as SoC or system on a chip, and is used to off load certain, non critical and data processing tasks, from the FPGA for efficient resource usage.

System on Chip (SoC) Processors

Resource abundant FPGA families allow an efficient implementation of a soft-IP microprocessor in order to off load non critical data handling tasks from the FPGA pipeline [START_REF] Meyer-Baese | Digital Signal Processing with Field Programmable Gate Arrays (Signals and Communication Technology)[END_REF]. However, implementing a soft-IP microprocessor infer severe performance limitations on the host FPGA mainly by restricting its maximum operating frequency. Additionally, implementing a full pipeline microprocessor would require a larger FPGA thus greatly increasing the cost for a marginal increase in performance [START_REF] Meyer-Baese | Digital Signal Processing with Field Programmable Gate Arrays (Signals and Communication Technology)[END_REF][START_REF] Tessier | Reconfigurable Computing for Digital Signal Processing: A Survey[END_REF][START_REF] Mueller | Data Processing on FPGAs[END_REF]. As such, and with the exponential growth in demand on a small, general purpose, low power and high performing embedded system, computer architectures are rapidly evolving toward heterogeneous multi-core systems, i.e SoC [START_REF] Meyer-Baese | Digital Signal Processing with Field Programmable Gate Arrays (Signals and Communication Technology)[END_REF][START_REF] Tessier | Reconfigurable Computing for Digital Signal Processing: A Survey[END_REF][START_REF] Mueller | Data Processing on FPGAs[END_REF][START_REF] Altera | Enabling High-Performance DSP Applications with Arria V or Cyclone V Variable-Precision DSP Blocks[END_REF]. While it is required to have a general purpose embedded system without a loss of performance, SoC models are equipped with many-cores and macro blocks each tailored for a specific application [START_REF] Meyer-Baese | Digital Signal Processing with Field Programmable Gate Arrays (Signals and Communication Technology)[END_REF]. A popular, low to mid end, SoC model is the Altera Cyclone V SoC and incorporates a dual core, general purpose ARM cortex A9 microprocessor, a Cyclone V FPGA with multiple variable precision, programmable DSP cores. The ARM cortex A9 architecture is shown in

Heterogeneous Systems Design Techniques

Unlike a soft-IP microprocessor, the advanced RISC machines (ARM) cortex A9 is equipped with two 32bits. 800 MHz, hard processors each with a dedicated floating point unit (FPU) [START_REF] Meyer-Baese | Digital Signal Processing with Field Programmable Gate Arrays (Signals and Communication Technology)[END_REF]. Moreover, the processor system provides a direct memory access (DMA) block, multiple timers and supports a variety of communication protocols with ready to use hardware, i.e. universal serial bus (USB), universal asynchronous receiver transmitter (UART), inter-integrated circuit (I2C), controller area network (CAN) and serial peripheral interface (SPI), with high speed memory units. Hence, the use of a dedicated microprocessor with programmable resources, frees critical FPGA resources, contributes to implementing a parallel, uninterrupted pipeline, architecture and accelerates the overall systems performance. However, programming a SoC is a multidisciplinary task and requires excessive software and hardware engineering skills [START_REF] Meyer-Baese | Digital Signal Processing with Field Programmable Gate Arrays (Signals and Communication Technology)[END_REF][START_REF] Nane | A Survey and Evaluation of FPGA High-Level Synthesis Tools[END_REF]. A comparative study based on various cost metrics is performed on the PDSP, the FPGA, the SoC and the general purpose processor (GPP). As shown in Table 4.1, eventhought the SoC platform is the highest performing, it requires an extensive design effort and a variety of skills in order to present an optimized and efficient design. As SoC development requires the use of a set of unified programming tools and languages, i.e. HLS, to efficiently target heterogeneous systems for both hardware and software design and off load performance optimization to the compiler [START_REF] Nane | A Survey and Evaluation of FPGA High-Level Synthesis Tools[END_REF].

Heterogeneous Systems Design Techniques

While specialized hardware and application specific circuits provide considerable performance boost, the main drawback resides in their design and the limitations of their Partie , Chapter 4 -Overview of Digital Signal Processing Implementation Techniques on Embedded Systems synthesize tools [START_REF] Nane | A Survey and Evaluation of FPGA High-Level Synthesis Tools[END_REF]. For over a decade, researchers and engineers unified their efforts in optimizing embedded system design techniques and compilers for heterogeneous systems with multi core processors. A popular and currently adopted solution for the processor diversity problem is the use of higher levels of abstraction with the help of an optimized software compiler to describe hardware functionality [START_REF] Nane | A Survey and Evaluation of FPGA High-Level Synthesis Tools[END_REF].

Traditional HDL, i.e. VHDL and Verilog, allows the designer to define a cycle by cycle behavioral and structural description of a custom digital circuit. The resulting design is then synthesized to obtain its register transfer level (RTL) description with the use of a logic synthesis tool [START_REF] Nane | A Survey and Evaluation of FPGA High-Level Synthesis Tools[END_REF]. However, the use of HDL mandates the user to specify circuits functionality in a low level of abstraction which requires advanced hardware development expertise [START_REF] Nane | A Survey and Evaluation of FPGA High-Level Synthesis Tools[END_REF]. As such, hardware developers are migrating from the use of classical HDL design techniques to higher level, object oriented, languages, i.e. SystemVerilog, and synthesis tools, i.e. VivadoHLS [START_REF] Nane | A Survey and Evaluation of FPGA High-Level Synthesis Tools[END_REF]. In this section, we provide a simple overview on the most popular adopted HLS design techniques for DSP.

High Level Synthesis (HLS) Design

The increased dependency on heterogeneous systems, its multidisciplinary nature and the need of unified programming techniques paved the way towards accelerating HLS design tools and compilers with the aim of achieving a high performance, energy efficient design [START_REF] Nane | A Survey and Evaluation of FPGA High-Level Synthesis Tools[END_REF]. HLS tools implement hardware circuits by automatically converting a software programmable high level language (HLL), i.e. C, python, C++, SystemC, to an equivalent HDL format [START_REF] Nane | A Survey and Evaluation of FPGA High-Level Synthesis Tools[END_REF]. HLS design techniques benefit both software and hardware engineers by off loading the problem of optimization to the compiler through the use of compiler specific directives [START_REF] Nane | A Survey and Evaluation of FPGA High-Level Synthesis Tools[END_REF][START_REF] Akkad | FFT Radix-2 and Radix-4 FPGA Acceleration Techniques Using HLS and HDL for Digital Communication Systems[END_REF]. Thus, allowing them to effectively design complex multi core systems at a high level of abstraction [START_REF] Nane | A Survey and Evaluation of FPGA High-Level Synthesis Tools[END_REF]. Some of the popular HLS tools are the VivadoHLS from Xilinx, Matlab HDL coder toolbox from Mathworks and the Intel Quartus Prime suite [START_REF] Mueller | Data Processing on FPGAs[END_REF][START_REF] Nane | A Survey and Evaluation of FPGA High-Level Synthesis Tools[END_REF][START_REF] Akkad | FFT Radix-2 and Radix-4 FPGA Acceleration Techniques Using HLS and HDL for Digital Communication Systems[END_REF]. An example of some of the frequently used VivadoHLS compiler directives are [START_REF] Akkad | FFT Radix-2 and Radix-4 FPGA Acceleration Techniques Using HLS and HDL for Digital Communication Systems[END_REF]:

-Unroll: Used in order to infer a parallel architecture for iterative procedures while optimizing execution time and resource usage.

FFT and The Dynamic Twiddle Factor Generator

-Pipeline: Used to infer a pipeline architecture for a component or architecture, through the use of additional registers, to increase the maximum operating frequency while decreasing latency and input delay.

-Partition: Used to partition large memory blocks for parallel access.

-Map: Allows the compiler to optimize usage and resource allocation for memory elements.

While the use of HLS tools allows an automatic HDL generation, it will always be dependent on the users experience in adapting the HLL to a specific application structure [START_REF] Nane | A Survey and Evaluation of FPGA High-Level Synthesis Tools[END_REF].

As such, the software programmer is required to understand the basics of digital HDL design and properly adapt his code to reflect his circuit structure [START_REF] Nane | A Survey and Evaluation of FPGA High-Level Synthesis Tools[END_REF], which is considered as a time-consuming and error prone process. Therefore, recent HLS tools offers complete flexibility and support for the HLL with complete freedom for the developer [START_REF] Nane | A Survey and Evaluation of FPGA High-Level Synthesis Tools[END_REF].

FFT and The Dynamic Twiddle Factor Generator

The Fast Fourier Transform or FFT, initially introduced by Cooley and Tukey (1965), is an efficient implementation of the discrete Fourier transform (DFT) one of the most widely used transforms in DSP. The DFT computes a signals frequency spectrum by converting its finite length time domain sequence of equally spaced samples to its equivalent frequency domain representation with respect to its amplitude, frequency and phase [START_REF] Meyer-Baese | Digital Signal Processing with Field Programmable Gate Arrays (Signals and Communication Technology)[END_REF][START_REF] Akkad | Twiddle Factor Generation Using Chebyshev Polynomials and HDL for Frequency Domain Beamforming[END_REF]. The DFT equation is given as follows:

X[k] = Nc-1 n=0 x d [n]e -j2πnk/Nc (4.1)
where x d [n] is a sample of the input signal x d at time index n and X[k] is its Fourier transform at index k. The popular Cooley Tukey FFT algorithms are those with a sequence of length N c , where N c is a power of a basis or a radix r, i.e. N c = r v with v representing the number of stages [START_REF] Meyer-Baese | Digital Signal Processing with Field Programmable Gate Arrays (Signals and Communication Technology)[END_REF][START_REF] Akkad | FFT Radix-2 and Radix-4 FPGA Acceleration Techniques Using HLS and HDL for Digital Communication Systems[END_REF]. The FFT algorithm iteratively divides the input sequence into groups of odd and even samples [START_REF] Meyer-Baese | Digital Signal Processing with Field Programmable Gate Arrays (Signals and Communication Technology)[END_REF][START_REF] Akkad | FFT Radix-2 and Radix-4 FPGA Acceleration Techniques Using HLS and HDL for Digital Communication Systems[END_REF] by the use of decimation in time (DIT) and

Partie , Chapter 4 -Overview of Digital Signal Processing Implementation Techniques on Embedded Systems

decimation in frequency (DIF) techniques. Thus, with respect to (4.1), the N c points FFT achieved through DIF can be computed as follows:

X[2k] = Nc 2 -1 n=0 x d [n] + x d n + N c 2 W kn Nc/2 X[2k + 1] = Nc 2 -1 n=0 W K Nc x d [n] -x d n + N c 2 W -kn Nc/2 (4.2)
where W K Nc is the rotation or twiddle factor [START_REF] Akkad | Twiddle Factor Generation Using Chebyshev Polynomials and HDL for Frequency Domain Beamforming[END_REF][START_REF] Akkad | FFT Radix-2 and Radix-4 FPGA Acceleration Techniques Using HLS and HDL for Digital Communication Systems[END_REF] given as: As shown in Figure 4.7, through continuous decomposition of (4.2), it is clear that the heart of the FFT operation and its building block is the butterfly processor [START_REF] Meyer-Baese | Digital Signal Processing with Field Programmable Gate Arrays (Signals and Communication Technology)[END_REF]. The butterfly processor is presented in details in Figure 4.8 and performs complex addition, complex multiplication and complex subtraction operations.

W k Nc = e -j2πk/Nc = cos 2πk N c -j sin 2πk N c (4.

Twiddle Factor Generator Using Chebyshev Polynomials

When implemented on hardware, in application specific architectures, the FFT butterfly processor rely on pre-computed twiddle factors initially stored in block memory [START_REF] Meyer-Baese | Digital Signal Processing with Field Programmable Gate Arrays (Signals and Communication Technology)[END_REF][START_REF] Akkad | Twiddle Factor Generation Using Chebyshev Polynomials and HDL for Frequency Domain Beamforming[END_REF]. However, the use of internal memory imposes strict and unavoidable timing and precision constraints on the DSP design, where an increase in precision results in an increase in the memory usage [START_REF] Akkad | Twiddle Factor Generation Using Chebyshev Polynomials and HDL for Frequency Domain Beamforming[END_REF]. Additionally, in some DSP applications, generic length FFT is often required and it is of crucial importance to dynamically generate high precision twiddle factors with respect to a low latency and low resource requirements architecture [START_REF] Akkad | Twiddle Factor Generation Using Chebyshev Polynomials and HDL for Frequency Domain Beamforming[END_REF].

Popular, dynamic, twiddle factor generators rely on the use of the coordinate rotation digital computer (CORDIC) algorithm [START_REF] Meyer-Baese | Digital Signal Processing with Field Programmable Gate Arrays (Signals and Communication Technology)[END_REF][START_REF] Akkad | Twiddle Factor Generation Using Chebyshev Polynomials and HDL for Frequency Domain Beamforming[END_REF] or Taylor function approximation [START_REF] Meyer-Baese | Digital Signal Processing with Field Programmable Gate Arrays (Signals and Communication Technology)[END_REF][START_REF] Akkad | Twiddle Factor Generation Using Chebyshev Polynomials and HDL for Frequency Domain Beamforming[END_REF] to compute the cos and sin trigonometric functions as in (4.3). However, CORDIC approximation requires a large number of iterations in order to achieve higher precision, consequently resulting in a considerably large latency and a non optimal pipeline architecture [START_REF] Akkad | Twiddle Factor Generation Using Chebyshev Polynomials and HDL for Frequency Domain Beamforming[END_REF]. In contrast, Taylor polynomial approximation allows the design of a fully pipeline low latency architecture; However, at the cost of a reduced precision the farther the input is from the Taylor expansion point [START_REF] Akkad | Twiddle Factor Generation Using Chebyshev Polynomials and HDL for Frequency Domain Beamforming[END_REF].

Several variants and improvements were suggested for the CORDIC and Taylor approximation in order to present a high precision low complexity, easy to pipeline, design [START_REF] Akkad | Twiddle Factor Generation Using Chebyshev Polynomials and HDL for Frequency Domain Beamforming[END_REF][START_REF] Garrido | A New Representation of FFT Algorithms Using Triangular Matrices[END_REF][START_REF] Hung | Design of an Efficient Variable-Length FFT Processor[END_REF][START_REF] Neuenfeld | Exploiting Addition Schemes for the Improvement of Optimized Radix-2 and Radix-4 FFT Butterflies[END_REF][START_REF] Yu | Low-Complexity Twiddle Factor Generator for FFT Processors[END_REF][START_REF] Zhou | A New Method to Generate Twiddle Factor Using CORDIC Based Radix-4 FFT Butterfly[END_REF][START_REF] Shinde | Twiddle Factor Generation Using CORDIC Processor for Fingerprint Application[END_REF]. However, the adopted design techniques and improvements still heavily rely on the use of internal memory elements and could not eliminate the dependency between CORDIC precision and required number of iterations [START_REF] Akkad | Twiddle Factor Generation Using Chebyshev Polynomials and HDL for Frequency Domain Beamforming[END_REF]. As such, and since twiddle factors precision greatly affects the overall resolution of the FFT processor, we propose a high speed, high precision, low latency and low complexity architecture using Chebyshev polynomial. Chebyshev polynomials are orthogonal polynomials defined over the interval [-1, 1] and can be calculated in a recursive form [START_REF] Akkad | Twiddle Factor Generation Using Chebyshev Polynomials and HDL for Frequency Domain Beamforming[END_REF], such as:

T 0 (u c ) = 1 T 1 (u c ) = u c T n+1 (u c ) = 2u c T n (u c ) -T n-1 (u c ) (4.4)
where u c is the change of variable mapping an input parameter, p t , from the interval [a c , b c ] to [-1, 1] defined as [START_REF] Akkad | Twiddle Factor Generation Using Chebyshev Polynomials and HDL for Frequency Domain Beamforming[END_REF]:

u c = 2p t -b c -a c b c -a c (4.5)
As such, a desired function can be approximated in polynomial form using Chebychev coefficients by expanding (4.4) [START_REF] Akkad | Twiddle Factor Generation Using Chebyshev Polynomials and HDL for Frequency Domain Beamforming[END_REF], such as:

f (u c ) ∼ = L-1 k=0 c g (k)u k c (4.6)
where c g (k) is the k th order Chebyshev polynomial coefficient. Using (4.3), (4.4) and (4.6) the twiddle factors trigonometric terms are approximated, as follows:

Re{f (u c )} = cos(πu c ) Im{f (u c )} = sin(-πu c ) f (u c ) = cos(πu c ) + j sin(-πu c ) (4.7)
Let the twiddle factor exponent be p t = 2k Nc , thus for a c = 0 and b c = 1 the change of

FFT and The Dynamic Twiddle Factor Generator

variable u c defined by (4.5) becomes:

u c = 2p t -1 (4.8)
Moreover, for a power of two length FFT input sequence (4.8) can be written as:

u c = 2 2 k 2 v -1 = k2 2-v -1 (4.9)
thus eliminating the requirements for a multiply-divide procedure by inferring a right shift operation. The Chebyshev coefficients are computed for a 5 th order polynomial approximation are given in Table 4.2.

f (u c ) 5 th order Chebyshev Polynomial Coefficients

c g (0) c g (1) c g (2) c g (3) c g (4) c g (

Computer Simulations

Computer simulations were conducted to study the accuracy of the Chebyshev approximation compared to the traditional Taylor approximation for an input vector, such as p t = [0, 0.125, 0.1667, 0.25, 0.5, 1] [START_REF] Akkad | Twiddle Factor Generation Using Chebyshev Polynomials and HDL for Frequency Domain Beamforming[END_REF]. For comparison purposes a direct computation of the twiddle factor is performed, in infinite precision without considering any approximation and presented in Table 4 The input vector pc was re-evaluated for a 5 th order Taylor approximation, over an expansion point q = 0, and a 5 th order Chebyshev approximation and the simulation result is presented in Tables 4.4 and4 4.4, it is clear that, compared to the direct computation, the Taylor approximation presents satisfactory results for the first three input terms, i.e. p t (0), p t (1), p t (2). However, as the input deviates further from the expansion point, i.e. q = 0, the approximation is no longer credible [START_REF] Akkad | Twiddle Factor Generation Using Chebyshev Polynomials and HDL for Frequency Domain Beamforming[END_REF].

f (u c )
Twiddle Factor Computation Using Chebyshev Approximation As shown in Table 4.6, the Taylor approximation MSE for both the sine and cosine functions is much greater than that of the Chebyshev, with respect to the direct computation results. Thus, validating the superior accuracy of the Chebyshev approximation.

u c (0) u c (1) u c (2) u c (3) u c (4) u c (

Hardware Implementation and Comparison

Given its inherent parallelism and popularity in the majority of the DSP operations, in this section, we implement the FFT radix-2 processor for a length N c = 8 input sequence [START_REF] Akkad | FFT Radix-2 and Radix-4 FPGA Acceleration Techniques Using HLS and HDL for Digital Communication Systems[END_REF]. The FFT implementation is conducted using HDL and HLS design techniques and for different processors, i.e. FPGA and SoC [START_REF] Akkad | FFT Radix-2 and Radix-4 FPGA Acceleration Techniques Using HLS and HDL for Digital Communication Systems[END_REF]. Additionally, we present a hardware implementation for the low complexity, high accuracy dynamic twiddle factor generator using Chebyshev polynomials [START_REF] Akkad | Twiddle Factor Generation Using Chebyshev Polynomials and HDL for Frequency Domain Beamforming[END_REF]. Finally, we implement a pipeline LMS adaptive beamformer using the relaxed look ahead technique as presented in [START_REF] Shanbhag | Relaxed Look-Ahead Pipelined LMS Adaptive Filters And Their Application To ADPCM Coder[END_REF] and we evaluate its performance under a finite precision arithmetic.

Fast Fourier Transform (FFT) Design Using HDL

The FFT radix-2 is first implemented in VHDL for a sequence of length N c = 8 using DIF and under finite precision wordlength, i.e. 16 bits signed representation [START_REF] Akkad | FFT Radix-2 and Radix-4 FPGA Acceleration Techniques Using HLS and HDL for Digital Communication Systems[END_REF]. The implementation is conducted for different architectures, i.e. sequential and fully parallel, and for different processors, such as: FPGA and SoC. The adopted processors are the "Xilinx ZynQ 7Z020CLG484" SoC and the "Intel/Altera Cyclone IV EP4CE115F29C7" FPGA.

Name

Type high speed, transistor level multipliers. On the contrast, the "ZynQ" includes 220 DSP blocks expanding the processors capabilities to perform vital DSP operations, i.e. MAC, complex operations and pre-additions, in high speed, dedicated, transistor level circuitry [START_REF] Akkad | FFT Radix-2 and Radix-4 FPGA Acceleration Techniques Using HLS and HDL for Digital Communication Systems[END_REF]. The experiment was first conducted on the "ZynQ" SoC processor and synthesis results are presented in Table 4.8.

The implementation is studied for two different architectures, i.e. parallel and sequential. The "parallel" architecture is a full parallel, pipeline, implementation of a length N c = 8 radix-2 DIF FFT [START_REF] Akkad | FFT Radix-2 and Radix-4 FPGA Acceleration Techniques Using HLS and HDL for Digital Communication Systems[END_REF]. The architecture is formed of v = 3 stages and a total of five butterfly processors [START_REF] Akkad | Twiddle Factor Generation Using Chebyshev Polynomials and HDL for Frequency Domain Beamforming[END_REF][START_REF] Akkad | FFT Radix-2 and Radix-4 FPGA Acceleration Techniques Using HLS and HDL for Digital Communication Systems[END_REF]. The parallel architecture achieved a maximum operating frequency of 196.539 MHz while using 20 DSP blocks, 3504 registers and 1680 logic units. DSP block allocation adheres with the presented structure in Figure 4.7 and the adopted wordlength since a full three stages radix-2 FFT requires five complex multipliers of four real multipliers each [START_REF] Akkad | FFT Radix-2 and Radix-4 FPGA Acceleration Techniques Using HLS and HDL for Digital Communication Systems[END_REF]. In contrast to the parallel architecture, a sequential structure was considered and implemented with similar simulation conditions [START_REF] Akkad | FFT Radix-2 and Radix-4 FPGA Acceleration Techniques Using HLS and HDL for Digital Communication Systems[END_REF]. The sequential architecture is formed only of one processing stage with four pipelined butterflies each [START_REF] Akkad | FFT Radix-2 and Radix-4 FPGA Acceleration Techniques Using HLS and HDL for Digital Communication Systems[END_REF]. As shown in Table 4.8, the sequential architecture operates at a maximum frequency of 198.087 MHz while using 16 DSP blocks, 1264 registers and 560 logic elements. Compared to the parallel implementation, the sequential design minimizes resource utilization, however at the cost of an increase in the latency and the input delay [START_REF] Akkad | FFT Radix-2 and Radix-4 FPGA Acceleration Techniques Using HLS and HDL for Digital Communication Systems[END_REF]. The implementation was then repeated for the "Cyclone IV" FPGA, synthesis results are displayed in Table 4.9.

Architecture

The "Cyclone IV" allocates 40 and 32 multipliers for a parallel and sequential architecture, respectively. Compared to the "ZynQ", the "Cyclone IV" doubles the required multipliers due to the fact that the embedded multipliers support 9×9 bits multiplications while the "ZynQ" DSP blocks are of 18 × 25 bits, as shown in Table 4 Moreover, the difference in the maximum operating frequency is caused by the processor pre-set timing constraints, compiler efficiency and transistor switching time [START_REF] Meyer-Baese | Digital Signal Processing with Field Programmable Gate Arrays (Signals and Communication Technology)[END_REF][START_REF] Akkad | FFT Radix-2 and Radix-4 FPGA Acceleration Techniques Using HLS and HDL for Digital Communication Systems[END_REF].

Fast Fourier Transform (FFT) Design Using HLS

The VHDL FFT implementation experiment was repeated, using HLS, with respect to the same design parameters and for the ZynQ SoC processor. The HLS design is conducted using a hardware optimized C programming language and different compiler directives [START_REF] Akkad | FFT Radix-2 and Radix-4 FPGA Acceleration Techniques Using HLS and HDL for Digital Communication Systems[END_REF]. The adopted pre-processing directives are: pipeline and unroll and are used to instruct the compiler to generate specific architectures, i.e. parallel, sequential and pipeline [START_REF] Akkad | FFT Radix-2 and Radix-4 FPGA Acceleration Techniques Using HLS and HDL for Digital Communication Systems[END_REF]. The FFT radix-2 DIF was first implemented without the use of "For loops" and evaluated for two different cases: without any directive and with the pipeline directive. Implementation and synthesis results are presented in Table 4 The design utilizes 16 DSP blocks and 12 DSP for a standard and pipeline architecture, respectively. Moreover, in contrast to the standard implementation with no directives, the pipeline directive optimize resource utilization while inferring a reduction in latency and input delay [START_REF] Akkad | FFT Radix-2 and Radix-4 FPGA Acceleration Techniques Using HLS and HDL for Digital Communication Systems[END_REF]. As such, HLS designs are highly correlated with the compilers efficiency

Partie , Chapter 4 -Overview of Digital Signal Processing Implementation Techniques on Embedded Systems

and with the use of the proper directives [START_REF] Akkad | FFT Radix-2 and Radix-4 FPGA Acceleration Techniques Using HLS and HDL for Digital Communication Systems[END_REF]. To further illustrate the effects of the compiler directives and their crucial role in HLS design, the FFT DIF radix-2 design is re-evaluated using "For loops" and with the pipeline and unroll directives [START_REF] Akkad | FFT Radix-2 and Radix-4 FPGA Acceleration Techniques Using HLS and HDL for Digital Communication Systems[END_REF]. Synthesis and implementation results are presented in Table 4 The "For loop" implementation without the use of compiler directives and the unroll FFT both results in a fully sequential scheme with only 1 butterfly, i.e. 4 DSP blocks. The sequential architecture is further validated by the large latency and input delay of 45 and 46, respectively. The resulting sequential architecture is a consequence of the use of a non optimized "For loop" implementation [START_REF] Akkad | FFT Radix-2 and Radix-4 FPGA Acceleration Techniques Using HLS and HDL for Digital Communication Systems[END_REF]. In contrast, it can be seen that the use of the unroll directive for the for loop design reduces the input delay, from 46 to 33 clock cycles and increases the DSP block usage to 16. As such, it can be concluded the unroll directed the HLS compiler to implement the for loop in parallel [START_REF] Akkad | FFT Radix-2 and Radix-4 FPGA Acceleration Techniques Using HLS and HDL for Digital Communication Systems[END_REF]. Therefore, it can be concluded that the HLS design technique is severely affected by the users experience and the proper choice of directive to obtain an efficient architecture [START_REF] Akkad | FFT Radix-2 and Radix-4 FPGA Acceleration Techniques Using HLS and HDL for Digital Communication Systems[END_REF].

Twiddle Factor Generation Using Chebyshev Polynomials in HDL

To further assess the performance of the twiddle factor generator using Chebyshev polynomials, a low complexity, pipeline, hardware architecture is presented. The 5 th order Chebyshev approximation is implemented using 18 bits signed wordlength and its finite precision output is compared to that obtained by the direct and the Taylor schemes [START_REF] Akkad | Twiddle Factor Generation Using Chebyshev Polynomials and HDL for Frequency Domain Beamforming[END_REF]. The implementation is performed for the "Xilinx ZynQ" and "Intel/Altera Cyclone V 5CSEMA5F31C6" SoC. Where, the "Cyclone V" SoC equips 85000 logic units, 128300 registers and 87 variable precision DSP blocks [START_REF] Akkad | Twiddle Factor Generation Using Chebyshev Polynomials and HDL for Frequency Domain Beamforming[END_REF]. Using (4.6) and (4.7), we can write:

cos(πu c ) ∼ = u c (c g (0) + u 2 c (c g (3) + c g (5)u 2 c )) sin(-πu c ) ∼ = c g (0) + u 2 c (c g (2) + c g (4)u 2 c ) (4.10)
Thus, with respect to (4.10), the resulting hardware architecture is shown in Figure 4.9, where denotes a shift right operation. As shown in Figure 4.9, the polynomial approximation is implemented in a pipeline parallel structure and can be used for Taylor and Chebyshev polynomials alike. Additionally, sin(-πu c ) is computed instead ofsin(πu c ), thus, eliminating the need for a two's complement adder at the output. The architecture is formed of five pipeline stages, i.e. the first output is obtained after 5 clock cycles [START_REF] Akkad | Twiddle Factor Generation Using Chebyshev Polynomials and HDL for Frequency Domain Beamforming[END_REF], synthesis and implementation results are given in Table 4.12. The suggested implementation is resource friendly and only requires 2.72% and 6.89% DSP blocks for the "ZynQ" and "Cyclone V" SoC, respectively. Moreover, the maximum clock frequency is 174 MHz, as such the presented architecture is a high speed and low complexity structure [START_REF] Akkad | Twiddle Factor Generation Using Chebyshev Polynomials and HDL for Frequency Domain Beamforming[END_REF].

SoC

Polynomial The finite precision simulation is conducted for an input vector the same input vector p t = [0, 0.125, 0.1667, 0.25, 0.5, 1] in a 18 bits signed format. In contrast to the Chebyshev coefficients with a Q2.15 format1 , the Taylor coefficients required the use of a Q3.14 2 , resulting in a further decrease in precision [START_REF] Akkad | Twiddle Factor Generation Using Chebyshev Polynomials and HDL for Frequency Domain Beamforming[END_REF]. The Taylor and Chebyshev output is presented in Tables 4 4.15, the Taylor approximation MSE for both the sine and cosine functions is much greater than that of the Chebyshev, with respect to the direct computation results. Thus, similar to the computer simulations, the hardware simulations result, validates the superior accuracy of the Chebyshev approximation in finite precision for a smaller order polynomial. Where smaller order polynomials requires less DSP resources, i.e. complex multipliers and adders.

Delay Relaxed Look-Ahead LMS

Presenting a pipe-lined architecture for a high throughput parallel implementation is difficult. Such difficulty is caused by the dependency of the coefficient update loop on the feedback error and filter output [START_REF] Shanbhag | Relaxed Look-Ahead Pipelined LMS Adaptive Filters And Their Application To ADPCM Coder[END_REF][START_REF] Sarma | A Novel Time-Shared and LUT-Less Pipelined Architecture for LMS Adaptive Filter[END_REF][START_REF] Zhao | A Division-Free and Variable-Regularized LMS-Based Generalized Sidelobe Canceller for Adaptive Beamforming and Its Efficient Hardware Realization[END_REF] since we cannot predict what will be the next error in order to determine the weights. Additionally, computing the error in only one clock cycle severely degrades the maximum operating frequency. To overcome the previous problem a delay and sum relaxed look-ahead approximation technique is presented in [START_REF] Shanbhag | Relaxed Look-Ahead Pipelined LMS Adaptive Filters And Their Application To ADPCM Coder[END_REF] for slowly varying signals, i.e. assuming a wide sense stationary (WSS) process, and tested for a tapped delay line filter. Such technique is achieved by applying a delay of D 2 samples for the input and coefficient terms and an additional delay relaxation of D 1 samples for the error path, with D 1 ≤ N , where N is the number of antenna elements. However, for larger filters the resulting hardware overhead becomes unacceptable, thus a sum relaxation is employed. The applied sum relaxation involves averaging only D 3 terms where 1 ≤ D 3 ≤ D 2 [START_REF] Shanbhag | Relaxed Look-Ahead Pipelined LMS Adaptive Filters And Their Application To ADPCM Coder[END_REF]. Hence, the delay relaxed look ahead LMS weight update equation and error term can be expressed as follows:

w(k + 1) = w(k -D 2 ) + µ D 3 -1 i=0 e * DLM S (k -D 1 -i)x(k -D 1 -i) (4.11) e DLM S (k) = d(k) -w H (k -D 2 )x(k) (4.12)
Thus, using (4.11) and (4.12) a pipeline parallel implementation is presented for the delay relaxed look ahead LMS, subject to a linear combiner, in Where x 1..4 (k), x 5..8 (k), w 1..4 (k) and w 5..8 (k) are the LMS input and weight vectors formed of first and last 4 elements, respectively. z -1 , z -D 1 represent the digital delay, i.e. registers of 1 and D 1 samples, respectively. The Conj block denotes complex conjugation. In addition, y 1 and y 2 form the intermediate outputs and they are defined as follows: From Table 4.16 the presented design achieves a maximum operating frequency of 208.33 MHz, while only using 32 DSP blocks, 1746 registers and 773 logic units. Hardware simulation is performed for the delay relaxed look ahead LMS in infinite precision (DLMS) and Q2.15 finite precision mode and is presented with the use of the beam radiation pattern. The simulation parameters are similar to that adopted, i.e. angle of arrival (AOA) As shown in Figure 4.13, for a signal to noise ratio (SNR) of 10 dB both systems converged with near similar beam radiation pattern. As such, the delay relaxed look ahead LMS in Q2.15 precision shows equivalent infinite, theoretical, performance. While the suggested modification realizes a full pipeline architecture, but it doesn't eliminate the convergence speed and error floor trade off, it may deteriorate it in some cases [4,[START_REF] Shanbhag | Relaxed Look-Ahead Pipelined LMS Adaptive Filters And Their Application To ADPCM Coder[END_REF]. Additionally, the reduction in the averaging terms might introduce convergence issues [START_REF] Shanbhag | Relaxed Look-Ahead Pipelined LMS Adaptive Filters And Their Application To ADPCM Coder[END_REF].

y 1 (k) = w H 1..4 (k)x 1..4 (k) (4.

Partie , Chapter 4 -Overview of Digital Signal Processing Implementation Techniques on Embedded Systems

Conclusion

In this chapter, we discussed some issues related to the hardware implementation of digital signal processing along with its advantages towards optimizing the performance and the cost of its host application. Moreover, we presented a comparative overview on several DSP optimized embedded processors, i.e. PDSP, FPGA and SoC, and different hardware design techniques, i.e. HDL and HLS. While general purpose processors presented degraded computational performance, when targeting application specific algorithms, it has been shown that this can be mitigated through the use of heterogeneous systems, i.e. SoC. However, the use of multi core SoC is a multidisciplinary problem and requires the use of HLL programming and HLS design tools. As such, we further proceeded by implementing an FFT radix-2 DIF processor using HDL, i.e. VHDL, and HLS, C on VivadoHLS, for different processor architecture. It has been shown that eventhought HLS design techniques accelerates development by automatically generating RTL equivalent code, it does require a proper use of compiler directives and coding standards. As most DSP routines implement a FFT processor, we proposed a high precision, low complexity, dynamic FFT twiddle factor generator using a 5 th order Chebyshev polynomial approximation and its pipeline hardware architecture. Through hardware and software simulations, we demonstrated the superior accuracy and performance of the proposed approximation scheme with respect to the traditional Taylor approximation. In contrast to the Taylor approximation, the proposed Chebyshev approximation method secured a precision up to three decimal digits for all input test elements in both finite and infinite precision modes. Finally, in this chapter we propose a pipeline implementation for the LMS adaptive beamformer based on the delay and sum relaxed look ahead technique. Hardware simulation is performed in finite, 18 bits, precision mode and demonstrated equivalent performance and accuracy compared to that of infinite precision. The work conducted has been published in the IEEE International Multidisciplinary Conference on Engineering Technology (IMCET) and in the Applications in Electronics Pervading Industry, Environment and Society (APPLEPIES) conference.

Chapter 5

THE PARALLEL LMS AND IT'S PIPELINE HARDWARE IMPLEMENTATION

Introduction

As previously stated, compared to the LMS, the RLS algorithm offers faster convergence and improved robustness against the input signals eigenvalue spread variation [6]. However, the RLS algorithm does not offer reliable tracking capabilities and requires extensive computations, i.e. computational complexity of order O(N 2 ) [4], where N is the number of antenna elements. Several variants of the LMS algorithm have been put to light with the aim of eliminating the trade off between convergence speed and the achievable steady state error for a given adaptation step size [4,[START_REF] Akkad | A Multi-Stage Parallel LMS Structure and its Stability Analysis Using Transfer Function Approximation[END_REF]. Some of the modified LMS algorithms include the normalized LMS (NLMS) [START_REF] Nascimento | The Normalized LMS Algorithm With Dependent Noise[END_REF], the constrained stability LMS (CSLMS) [START_REF] Gorriz | Speech Enhancement in Discontinuous Transmission Systems Using the Constrained-Stability Least Mean Squares Algorithm[END_REF], the variable step size LMS (VSSLMS) [START_REF] Shengkui | A Fast Variable Step-Size LMS Algorithm with System Identification[END_REF][START_REF] Kwong | A Variable Step Size LMS Algorithm[END_REF], the modified robust variable step size LMS (MRVSSLMS) [START_REF] Xiubing | A New Modified Robust Variable Step Size LMS Algorithm[END_REF] and the LLMS [5]. These algorithms use an additional computation stage to dynamically control the step size, i.e NLMS, CSLMS, VSSLMS and MRVSSLMS, or accurately tune the weights with respect to a multi stage, error averaging, structure, i.e. LLMS [5]. The LLMS adaptive algorithm is formed by two LMS stages connected by an estimate of the steering vector, where the overall total error is formed as a linear combination of each individual stages [4,[START_REF] Akkad | A Multi-Stage Parallel LMS Structure and its Stability Analysis Using Transfer Function Approximation[END_REF]. Thus, for a uniform linear antenna (ULA) array of N elements, the LLMS doubles the computational requirements of a classical LMS and requires the use of a division operator for the cascading stage [START_REF] Akkad | Two Stages Parallel LMS Structure A Pipelined Hardware Architecture[END_REF]. Therefore, the implementation of the LLMS requires a total of 6N + 2 complex multiplications, 5N + 4 complex additions and N complex divisions [4]. Given the cas-Partie , Chapter 5 -The Parallel LMS and it's Pipeline Hardware Implementation cading nature of the LLMS, presenting a pipeline hardware implementation is extremely difficult [START_REF] Akkad | Two Stages Parallel LMS Structure A Pipelined Hardware Architecture[END_REF]. Additionally, the introduction of a division operator exposes the system to underflow and to divide by zero errors in finite precision mode [4]. Thus, inspired by the multi stage error feedback technique [5,6,[START_REF] Srar | Adaptive Array Beam Forming Using A Combined RLS-LMS Algorithm[END_REF], we propose a two-stage parallel, least mean square structure (pLMS) for adaptive beamforming and its pipeline hardware implementation. In contrast to LLMS, the pLMS is formed of two parallel LMS connected by error feedback, where the overall error signal is derived as a linear combination of individual stage errors, omitting the need for a cascading stage [4].

Multi Stage Parallel LMS (pLMS) Algorithm

By definition the pLMS beamformer is a multi stage LMS connected by an error feedback. As such, the error signal of the second LMS stage (LM S 2 ), e 2 (k), is delayed by one sample, multiplied by the imaginary number j = √ -1, i.e. phase shift, and combined with the error of the first LMS stage (LM S 1 ), e 1 (k), to form the overall pLMS error e pLM S . We should recall that the multiplication by j, as presented in section 3.3.5 and in (3.36), is introduced as an added robustness against recurring samples [START_REF] Akkad | Two Stages Parallel LMS Structure A Pipelined Hardware Architecture[END_REF]. Recurring samples are formed as a consequence of consecutive data repetition in the original message signal, analog to digital converters (ADC) impurities [4,[START_REF] Farina | Effect of ADC and Receiver Saturation On Adaptive Spatial Filtering Of Directional Interference[END_REF][START_REF] Zoubir | Array and Statistical Signal Processing[END_REF], quantization errors, low resolution [4,[START_REF] Farina | Effect of ADC and Receiver Saturation On Adaptive Spatial Filtering Of Directional Interference[END_REF][START_REF] Shang | Digital Beamforming Based On FPGA For Phased Array Radar[END_REF][START_REF] Seneviratne | Multidimensional-DSP Beamformers Using the ROACH-2 FPGA Platform[END_REF][START_REF] Jing | Performance Analysis Of Multi-Rate Signal Processing Digital Filters On FPGA[END_REF] and symbol detection errors originated from the digital receivers in low SNR environments [4,[START_REF] Theodore | Wireless Communications: Principles and Practice[END_REF]. As such, a multiplication by j is proposed for robustness against resulting error nulls [4,[START_REF] Akkad | Two Stages Parallel LMS Structure A Pipelined Hardware Architecture[END_REF]. The pLMS structure is shown in Figure 5.1, where the block jz -1 represents one sample delay and a multiplication by j [4,[START_REF] Akkad | A Multi-Stage Parallel LMS Structure and its Stability Analysis Using Transfer Function Approximation[END_REF]. As shown in Figure 5.1, the LM S 2 filter is no longer dependent on the steering vector estimate's output and operates in parallel with the LM S 1 . Moreover, the total pLMS is formed as a linear combination of independent stage errors, such that:

e pLM S (k) = e 1 (k) -je 2 (k -1) = d(k) -jd(k -1) -w H 1 (k)x(k) + jw H 2 (k -1)x(k -1) (5.1)
where the superscript H is the Hermitian transpose, x(k) is the input signal at the discrete time instance k, e i (k

) = d(k) -w H i (k)x(k), i = 1, 2 represents the stage identifier, y LM S1 (k) = w H 1 (k)x(k) and y LM S2 (k) = w H 2 (k)x(k)
are the first and second stage outputs, and w 1 (k), w 2 (k -1) are the current and delayed weight vectors of LM S 1 and LM S 2 , respectively. Thus, from (5.1), the pLMS MSE cost function, ξ pLM S (k), can be computed as follows [4]:

ξ pLM S (k) = E[|e pLM S (k)| 2 ] = E[e 1 (k)e * 1 (k) + je 1 (k)e * 2 (k -1) -je * 1 (k)e 2 (k -1) + e 2 (k -1)e * 2 (k -1)] (5.2)
where E[.] is the expectation operation, |.| signifies the complex modulus and the superscript * denotes complex conjugation. Moreover, (5.2) can be expanded to obtain (5.3), further details can be found in Appendix B [4]:

ξ pLM S (k) = E[|d(k)| 2 ] -p H w 1 (k) -w H 1 (k)p + w H 1 (k)Rw 1 (k) + E[|d(k -1)| 2 ] -E[d(k)x H (k -1)]w 2 (k -1) -w H 2 (k -1)E[d * (k)x(k -1)] + jE[d * (k)d(k -1)] +w H 2 (k -1)E[x(k)x(k -1)]w 2 (k -1) + jE[d(k)d * (k -1)] -jw H 1 (k)E[d * (k -1)x(k)] + jw H 1 (k)E[x(k)x H (k -1)]w 2 (k -1) +jE[d(k)x H (k -1)]w 1 (k) + jw H 2 (k -1)E[d(k)x(k -1)] +jE[x H (k)w 1 (k)w H 2 (k -1)x(k -1)] -jE[d(k)x H (k -1)]w 2 (k -1) (5.3)
where R = R(0) is the input signal auto-correlation matrix and p = p(0) is the cross correlation vector of the input x(k) and desired signal d(k). R(0) and p(0) are defined at lag τ = 0 as:

R(τ ) = E[x(k -τ )x H (k)] (5.4) p(τ ) = E[d * (k -τ )x(k)] (5.5)
Where, assuming a wide sense stationary (WSS) process, the lag τ = k 1 -k 2 and k 1 and k 2 are different time instances from which an observation of the random process is taken.

With w 1 (k) being the tap weights of interest [4,5,6,[START_REF] Akkad | An Efficient Non-Blind Steering Vector Estimation Technique For Robust Adaptive Beamforming With Multistage Error Feedback[END_REF][START_REF] Srar | Adaptive Array Beam Forming Using A Combined RLS-LMS Algorithm[END_REF]. The optimal weight vector, w op , of w 1 (k) can be obtained by differentiating (5.3) with respect to w H 1 (k) [5,[START_REF] Srar | Adaptive Array Beam Forming Using A Combined RLS-LMS Algorithm[END_REF][START_REF] Bouboulis | Extension of Wirtinger's Calculus To Reproducing Kernel Hilbert Spaces And The Complex Kernel LMS[END_REF], and setting the resulting pLMS gradient, ∇ pLM S = 0, to obtain [4]:

∇ pLM S = ∂ξ pLM S (k) ∂w H 1 (k) = -p + Rw 1 (k) -jE[d * (k -1)x(k)] + jE[x(k)x H (k -1)]w 2 (k -1) (5.6)
The optimal weight vector, w op , becomes [4]:

w op = R -1 p + jR -1 E[d * (k -1)x(k)] -jR -1 E[x(k)x H (k -1)]w 2 (k -1) (5.7)
where R -1 is the input signals auto-correlation matrix inverse, assuming R is invertible [4]. The resulting gradient can be validated from (5.6) such as [4]:

w 1 (k + 1) = w 1 (k) -µ 1 ∇ pLM S = w 1 (k) -µ 1 [-p + Rw 1 (k) -jE[d * (k -1)x(k) +jE[x(k)x H (k -1)]w 2 (k -1)] = w 1 (k) + µ 1 x(k)[d * (k) -x H (k)w 1 (k) + jd * (k -1) -jx H (k -1)w 2 (k -1)] (5.8)
Thus, the pLMS adaptive algorithm is presented in (5.9) [4] as follow:

LMS 1 : y LM S1 (k) = w H 1 (k)x(k) e 1 (k) = d(k)-y LM S1 (k) e pLM S (k) = e 1 (k) -je 2 (k -1) w 1 (k + 1) = w 1 (k) + µ 1 e * pLM S (k)x(k) LMS 2 : y LM S2 (k) = w H 2 (k)x(k) e 2 (k) = d(k)-y LM S2 (k) w 2 (k + 1) = w 2 (k) + µ 2 e * 2 (k)x(k) (5.9)
where µ 1 and µ 2 are the LM S 1 and LM S 2 step sizes, respectively.

Theoretical Stability Analysis

In order to determine under which conditions the pLMS is stable and converges to the optimal weight, a first order convergence and stability analysis is performed for LM S 1 and LM S 2 .

First LMS Stage

Let the mean coefficient error vector, v(k) [2] be defined as:

v(k) = w(k) -w op (5.10)
where w(k) is the mean weight vector. At steady-state and assuming both stages convergence, i.e. as k → ∞, and d(k -1) ≈ y LM S1 (k -1) ≈ y LM S2 (k -1), (5.7) becomes:

w op ≈ w oplms + jR -1 E[x(k)x H (k -1)]w 2 (k -1) -jR -1 E[x(k)x H (k -1)]w 2 (k -1)
≈ w oplms (5.11) Thus, for identical step sizes i.e. µ pLM S = µ 1 = µ 2 we obtain:

H pLM S (z) = 1 + µ pLM S N R(z) -jz -1 (1 + µ pLM S N R(z)) 2 (5.27)
The presented relationship in (5.26), starting at k = 0, includes both convergence and steady-state results [START_REF] Akkad | A Multi-Stage Parallel LMS Structure and its Stability Analysis Using Transfer Function Approximation[END_REF][START_REF] Clarkson | Simplified Analysis Of The LMS Adaptive Filter Using A Transfer Function Approximation[END_REF][START_REF] Han | Quality of Approximation in Error Transfer Function Analysis of the LMS Adaptive Filters[END_REF]. While (5.26) and (5.27) present a simple approximation for the behavior of the pLMS adaptive beamformer; This approximation doesn't represent the optimal least-square solutions for the steady-state behavior [START_REF] Akkad | A Multi-Stage Parallel LMS Structure and its Stability Analysis Using Transfer Function Approximation[END_REF].

pLMS Pipeline Hardware Implementation

While the pLMS offers an implicitly parallel structure most suitable for hardware implementation [START_REF] Akkad | Two Stages Parallel LMS Structure A Pipelined Hardware Architecture[END_REF]. However, presenting a pipeline architecture is deemed difficult due to the presence of an error feedback loop in the LMS weight update algorithm [START_REF] Shanbhag | Relaxed Look-Ahead Pipelined LMS Adaptive Filters And Their Application To ADPCM Coder[END_REF][START_REF] Sarma | A Novel Time-Shared and LUT-Less Pipelined Architecture for LMS Adaptive Filter[END_REF][START_REF] Zhao | A Division-Free and Variable-Regularized LMS-Based Generalized Sidelobe Canceller for Adaptive Beamforming and Its Efficient Hardware Realization[END_REF][START_REF] Akkad | Two Stages Parallel LMS Structure A Pipelined Hardware Architecture[END_REF][START_REF] Meyer-Baese | Digital Signal Processing with Field Programmable Gate Arrays (Signals and Communication Technology)[END_REF]. As such, we propose the application of the delay and sum relaxed look ahead technique to present a parallel, pipeline pLMS hardware architecture (DpLMS) [START_REF] Shanbhag | Relaxed Look-Ahead Pipelined LMS Adaptive Filters And Their Application To ADPCM Coder[END_REF][START_REF] Akkad | Two Stages Parallel LMS Structure A Pipelined Hardware Architecture[END_REF].

Delay and Sum Relaxed Look Ahead pLMS

The delay and sum relaxation technique is applied for each of the LMS stages i.e., LM S 1 and LM S 2 separately [4,[START_REF] Shanbhag | Relaxed Look-Ahead Pipelined LMS Adaptive Filters And Their Application To ADPCM Coder[END_REF][START_REF] Akkad | Two Stages Parallel LMS Structure A Pipelined Hardware Architecture[END_REF]. As such, with respect to the weight update equation from (5.9), we start with a D 2 averaging look ahead step [START_REF] Shanbhag | Relaxed Look-Ahead Pipelined LMS Adaptive Filters And Their Application To ADPCM Coder[END_REF][START_REF] Akkad | Two Stages Parallel LMS Structure A Pipelined Hardware Architecture[END_REF] in the weight update path and a delay relaxation of D 1 samples in the error path. Hence, we obtain:

w(k + 1) = w(k -D 2 ) + µ D 2 -1 i=0 e * (k -D 1 -i)x(k -D 1 -i) (5.28)
The modification presented in (5.28) is possible assuming the process is WSS and the gradient estimate undergoes only marginal changes over D 1 samples [START_REF] Shanbhag | Relaxed Look-Ahead Pipelined LMS Adaptive Filters And Their Application To ADPCM Coder[END_REF][START_REF] Akkad | Two Stages Parallel LMS Structure A Pipelined Hardware Architecture[END_REF]. In contrast to its set advantages in presenting an easy to pipeline form, the hardware overhead imposed by (5.28) is of N (D 2 -1) adders and becomes unacceptable for larger values of N and D 2 [START_REF] Shanbhag | Relaxed Look-Ahead Pipelined LMS Adaptive Filters And Their Application To ADPCM Coder[END_REF][START_REF] Akkad | Two Stages Parallel LMS Structure A Pipelined Hardware Architecture[END_REF]. Thus, to minimize the resulting overhead complications, an additional sum relaxation of D 3 terms is applied, such that: 1 ≤ D 3 ≤ D 2 . Therefore, (5.28) is modified to become [START_REF] Akkad | Two Stages Parallel LMS Structure A Pipelined Hardware Architecture[END_REF]:

w(k + 1) = w(k -D 2 ) + µ D 3 -1 i=0 e * (k -D 1 -i)x(k -D 1 -i) (5.29)
Moreover, assuming µ is small enough [2], and w(k -D 2 -1) can be approximated by w(k -D 2 ); In this case, the error update equation, with respect to D 2 , becomes [START_REF] Akkad | Two Stages Parallel LMS Structure A Pipelined Hardware Architecture[END_REF]:

e(k) = d(k) -w H (k -D 2 )x(k) (5.30)
Hence, a delayed pLMS (DpLMS) structure is now obtained by applying (5.29) and (6.35) to LM S 1 and LM S 2 [START_REF] Akkad | Two Stages Parallel LMS Structure A Pipelined Hardware Architecture[END_REF].

DpLMS Hardware Architecture

The DpLMS is implemented in finite precision mode with respect to the pLMS top level architecture presented in Figure 5.1 for an input source of N = 8 ULA arrays structure [START_REF] Akkad | Two Stages Parallel LMS Structure A Pipelined Hardware Architecture[END_REF]. The adopted finite precision numbering format is the Q2.151 format. The delay relaxation parameters are initialized, such as: D 1 = 4, D 2 = 2 and D 3 = 1 resulting in a total of six pipeline stages [START_REF] Akkad | Two Stages Parallel LMS Structure A Pipelined Hardware Architecture[END_REF]. The proposed DpLMS top level architecture is shown in Figure 5.2, where x 1..4 (k), x 5..8 (k), w 1..4 (k) and w 5..8 (k) are the DpLMS input and weight vectors formed of the first and last 4 elements of x(k) and w(k), respectively [START_REF] Akkad | Two Stages Parallel LMS Structure A Pipelined Hardware Architecture[END_REF]. The delay z -1 , z -D 1 -1 the * j and the "Conj" blocks denotes a digital delay, i.e. registers of one and D 1 -1 samples, multiplication by j and complex conjugation, respectively.

The linear combiner and weight update blocks are defined in Figures 5. From Figure 5.3, it is clear that all multiplication and addition operation are performed in separate pipeline stages and requires one clock cycle each [START_REF] Akkad | Two Stages Parallel LMS Structure A Pipelined Hardware Architecture[END_REF]. Thus, with an all parallel input architecture, the computational complexity of each stage is of order O(1) [START_REF] Akkad | Two Stages Parallel LMS Structure A Pipelined Hardware Architecture[END_REF]. The 5.1 [START_REF] Altera | Enabling High-Performance DSP Applications with Arria V or Cyclone V Variable-Precision DSP Blocks[END_REF]. In contrast to the pLMS, the DpLMS presents a pipeline high throughput structure at the cost of a negligible increase in the resource usage, i.e. logic elements and registers. Furthermore, in contrast to the original pLMS that can process one sample each (D 1 + D 3 ) × 4.8 ns, i.e. input latency of 28.8 ns, the proposed DpLMS architecture can process one sample each 4.8 ns with an initial, setup, input latency of 6 cycles, i.e. 6 pipeline stages [START_REF] Akkad | Two Stages Parallel LMS Structure A Pipelined Hardware Architecture[END_REF].

Algorithm Initial Parameters LMS µ LM S = 0.03125 RLS α = 0.98, L(0) = 0.5I, Q(0) = 0.025I LLMS µ 1 = 0.03125 µ 2 = 0.03125, ϑ = 0.0004 pLMS µ 1 = 0.03125, µ 2 = 0.03125 DpLMS µ 1 = 0.03125, µ 2 = 0.03125, nu = 5
Table 5.2 -Simulation Initial Parameters

Hardware and Software Simulations

A Monte Carlo type simulation is conducted to assess the behavior of the pLMS, the pLMS transfer function subject to fractional delay (pLMS-FD) and the DpLMS with respect to the LLMS, LMS and RLS adaptive algorithms. The simulation is performed for 500 realizations of 500 samples each where the input source is modeled as a ULA array with N = 8 elements. The input signal is formed by a combination of a message signal and two interferes impinging the array from broadside at an angle of 20 • , 5 • and 65 • , respectively. The inputs are generated as independent random complex Gaussian sequences of the form v m = N (0 , σ 2 p ) + jN (0 , σ 2 q ) where, N denotes normal, zero mean, (Gaussian) distribution. σ 2 p and σ 2 q are the real and complex sequence variances, respectively. The final input signal is corrupted by CAWGN for a signal to noise ratio (SNR) of 10 dB. The parameters and initial conditions at k = 0 are initialized for the LMS and its variants with respect to Table 5.2, where I is the identity matrix.

Mean Square Error Convergence Analysis

The MSE simulation is used to study the convergence behavior of the LLMS, the pLMS, the DpLMS, the RLS and the classical LMS, and is presented in Figure 5.5. As shown in that Figure, the pLMS and the DpLMS convergence profile reflects that of the LLMS however with a lower steady state error, i.e. a better accuracy. The increase in accuracy is a result of eliminating the requirements for a steering vector estimation stage and the division operation. Additionally, it is clear that the DpLMS experienced a small delay in convergence with respect to the pLMs. The resulting delay is a consequence of the adopted delay and averaging scheme. Moreover, while the RLS achieved the best convergence profile, it requires an undesirable computational complexity of order O(N 2 ) and lack tracking ability. In contrast, the pLMS and DpLMS achieved identical accelerated and accurate behavior while maintaining a linear computational complexity of order O(N ) [START_REF] Akkad | A Multi-Stage Parallel LMS Structure and its Stability Analysis Using Transfer Function Approximation[END_REF][START_REF] Akkad | Two Stages Parallel LMS Structure A Pipelined Hardware Architecture[END_REF]. As shown in Figure 5.6, the pLMS and pLMS-FD converged at the same iteration, however the latter experienced a higher residual steady state error. The pLMS-FD steady state error profile is a consequence of the fractional delay filter approximation adopted previously [START_REF] Akkad | A Multi-Stage Parallel LMS Structure and its Stability Analysis Using Transfer Function Approximation[END_REF][START_REF] Akkad | Two Stages Parallel LMS Structure A Pipelined Hardware Architecture[END_REF]. In order to validate the accuracy of the transfer function approximation with respect to the fractional delay filter, the pLMS MSE convergence behavior is evaluated against that of the pLMS-FD. The pLMS was further compared against the LLMS for a sequence with repeated samples, the MSE convergence plot is shown in Figure 5.7. For a sequence with repeated samples, the LLMS failed to preserve its accelerated convergence profile. In contrast, the pLMS provided visible robustness in maintaining its accelerated convergence and low residual error characteristics and a result of the introduced error phase shift, i.e. multiplication by j [4,[START_REF] Akkad | A Multi-Stage Parallel LMS Structure and its Stability Analysis Using Transfer Function Approximation[END_REF][START_REF] Akkad | Two Stages Parallel LMS Structure A Pipelined Hardware Architecture[END_REF].

Finally, the pLMS and DpLMS convergence behavior is analyzed for different SNR environments, i.e. from -5 dB to 7 dB with a step of 6 dB, the MSE output is presented in Figures 5.8 and 5.9.

Beam Radiation Pattern

Similar to the MSE convergence plot the beam radiation pattern is also evaluated in order to better assess the resulting beam pointing accuracy and the effect of the sum relaxation. The beam radiation pattern for the pLMS, the infinite precision DpLMS and the finite precision DpLMS is shown in Figure 5.10. The 18 bits finite precision DpLMS, simulated on the "Intel Stratix V FPGA", presented similar beam pattern and pointing accuracy compared to the infinite precision pLMS and DpLMS for an SNR of 10 dB [START_REF] Akkad | A Multi-Stage Parallel LMS Structure and its Stability Analysis Using Transfer Function Approximation[END_REF]. 5.12 the DpLMS achieves a satisfactory behavior for SNR environments up to only 1 dB, however with a weaker main beam compared to that of the pLMS [START_REF] Akkad | A Multi-Stage Parallel LMS Structure and its Stability Analysis Using Transfer Function Approximation[END_REF]. Such degradation validates the previously stated and can be omitted for large values of D 3 , i.e. a high order moving average filter. However, as D 3 increases the hardware overhead increases [START_REF] Akkad | Two Stages Parallel LMS Structure A Pipelined Hardware Architecture[END_REF].

Pole Zero Map Stability Plot

In order to numerically determine the maximum step size allowed for the pLMS a pole zero plot is performed for the transfer function approximation in (5.27). The pLMS maintaining a computational complexity of order O(N ). Additionally, the pLMS omits the need of a division operator and provides a considerable reduction in resource usage, i.e. 2N complex multiplications, N complex additions and N complex divisions [4,[START_REF] Akkad | A Multi-Stage Parallel LMS Structure and its Stability Analysis Using Transfer Function Approximation[END_REF]. However, compared to the LMS, the pLMS achieves its superior performance at the cost of a considerably large increase in resource requirements, i.e. double. As such, it is of crucial importance to present a reduced complexity structure of the pLMS while maintaining its accelerated convergence profile [4].

Algorithm cMultiply cAdd cDivide RLMS[15] 3N 2 + 11N + 2 2N 2 + 9N + 6 N + 1 RLMSp[6] 3N 2 + 7N + 1 2N 2 + 6N + 3 1 RLS 3N 2 + 5N 2N 2 + 4N + 2 1 LLMS[5] 6N + 2 5N + 4 N pLMS 4N + 2 4N + 4 0 LMS 2N + 1 2N + 1 0

Conclusion

In this chapter, we proposed a multi stage parallel LMS structure (pLMS) for adaptive beamforming, we evaluated its transfer function approximation and we introduced its pipeline hardware implementation. pLMS is formed of two LMS stages operating in parallel and connected by an error feedback. The pLMS transfer function approximation is obtained by modeling the input spatial linear combiner as a fractional delay temporal filter with a Lagrange interpolation. Moreover, we propose a pipeline hardware implementation through the application of the delay and sum relaxed look ahead technique (DpLMS). Stability analysis is performed to determine the theoretical upper bound of the step size required to ensure convergence. The maximum allowable step size is determined numerically with respect to the transfer function approximation and the pole zero plot study. Simulation results demonstrated the superior performance of the pLMS and DpLMS in providing accelerated convergence and maintaining a low steady state error while preserving a complexity of order O(N ). Both algorithms presented a satisfactory convergence profile and beam pattern for SNR up to 1 dB. Through pole zero plot analysis the maximum step size, allowed to maintain a proper pLMS convergence, is in the range of 0.03 < µ < 0.04. Synthesis and implementation results show that, in contrast to other RLS and LMS variants, the DpLMS provides a parallel, pipeline, low complexity and resource friendly architecture suitable for low end processors. Finally, the fixed point DpLMS beam radiation pattern validated the DpLMS accuracy in finite precision mode by providing a similar infinite precision beam directivity. The work conducted for the pLMS derivation and its hardware implementation has been separately published in the European Signal Processing Conference (EUSIPCO).

Partie , Chapter 6 -The Reduced Complexity Parallel LMS and its Pipeline Hardware Implementation RC-pLMS is formed from a single LMS stage with additional inputs, obtained by the applying a sample delay to the input and desired signal, as shown in Figure 6.1 [4]. Where, ULA is a uniform linear antenna, e RC-pLM S (k) is the RC-pLMS overall error, u(k) and S(k) are the new system input and reference signals, respectively [4], the block jz -1 denotes multiplication by j with a one sample delay [4]. The new system inputs are defined, such as:

S(k) = d(k) -jd(k -1) u(k) = x(k) -jx(k -1) (6.1)
where j = √ -1 is the imaginary number, d(k) is the desired signal at the discrete time instance k and x(k) is the input signal. Moreover, The RC-pLMS transfer function approximation is obtained by modeling the input linear combiner filter by a temporal fractional delay finite impulse response (FIR) filter with a Lagrange interpolation [START_REF] Akkad | A Multi-Stage Parallel LMS Structure and its Stability Analysis Using Transfer Function Approximation[END_REF]. Similarly, a parallel pipeline hardware implementation is presented through the application of the delay and sum relaxed look ahead technique (DRC-pLMS) [4]. Stability and quantization effect analyses are performed to determine the upper bound of the step size and assess the behavior of the system in a finite precision mode [4].

Reduced Complexity Multi Stage Parallel LMS (RC-pLMS) Algorithm

As previously stated, the pLMS is a multi stage LMS structure connected by an error feedback and its total error, e pLM S (k), is formed as a linear combination of individual stage errors, given as:

e pLM S (k) = e 1 (k) -je 2 (k -1) = d(k) -jd(k -1) -w H 1 (k)x(k) + jw H 2 (k -1)x(k -1) (6.2)
where the superscript H is the Hermitian transpose, e i (k) = d(k)w H i (k)x(k), i = 1, 2 represents the stage identifier are the first and second stage outputs, and w 1 (k), w 2 (k -1) are the current and delayed weight vectors of the first and second LMS stages, LM S 1 and LM S 2 , respectively. and its weight vector update equation is as follows:

w 1 (k + 1) = w 1 (k) + µ pLM S x(k)[d * (k) -x H (k)w 1 (k) +jd * (k -1) -jx H (k -1)w 2 (k)] (6.3)
where µ pLM S is the pLMS step size, the superscript * represents complex conjugation. Moreover, the pLMS mean square error (MSE) cost function, ξ pLM S , is thus defined from (6.2):

ξ pLM S (k) = E[|d(k)| 2 ] -p H w 1 (k) -w H 1 (k)p + w H 1 (k)Rw 1 (k) + E[|d(k -1)| 2 ] -E[d(k)x H (k -1)]w 2 (k -1) -w H 2 (k -1)E[d * (k)x(k -1)] +w H 2 (k -1)E[x(k)x(k -1)]w 2 (k -1) + jE[d(k)d * (k -1)] +jE[d * (k)d(k -1)] -jE[d(k)x H (k -1)]w 2 (k -1) -jw H 1 (k)E[d * (k -1)x(k)] + jw H 1 (k)E[x(k)x H (k -1)]w 2 (k -1) +jE[d(k)x H (k -1)]w 1 (k) + jw H 2 (k -1)E[d(k)x(k -1)] +jE[x H (k)w 1 (k)w H 2 (k -1)x(k -1)] (6.4)
where E[.] is the expectation operation, |.| signifies the complex modulus, R = R(0) is the input signal auto-correlation matrix and p = p(0) is the cross correlation vector of the input x(k) and desired signal d(k). R(0) and p(0) are defined at lag τ = 0 as:

R(τ ) = E[x(k -τ )x H (k)] (6.5) p(τ ) = E[d * (k -τ )x(k)] (6.6)
Where, assuming a wide sense stationary (WSS) process, the lag τ = k 1 -k 2 and k 1 and k 2 are different time instances from which an observation of the random process is taken. With respect to (6.4), the pLMS optimal weight vector, w op , is derived as follows: where R -1 is the input signals auto-correlation matrix inverse, assuming R is invertible [4]. Assuming both system converges to their respective optimal weight, thus, as k → ∞, we can approximate that w 1 (k) ≈ w 1 (k -1) ≈ w op and that w 2 (k) ≈ w 2 (k -1) ≈ w oplms [4,5]. Therefore, the first and second LMS stages outputs y LM S1 and y LM S2 , having both interference and noise signals being suppressed, tend to approach the desired signal d(k) [4,5,[START_REF] Srar | Adaptive Array Beam Forming Using A Combined RLS-LMS Algorithm[END_REF]. As such, we assume that the filter output and the desired signal can satisfy the approximation d(k -1) ≈ y LM S1 (k -1) ≈ y LM S2 (k -1) [4,5,[START_REF] Srar | Adaptive Array Beam Forming Using A Combined RLS-LMS Algorithm[END_REF]. Thus, from (6.7) we can write:

w op = R -1 p + jR -1 E[d * (k -1)x(k)] -jR -1 E[x(k)x H (k -1)]w 2 (k -1) (6.
w op = w oplms + jR -1 E[d * (k -1)x(k)] -jR -1 E[x(k)x H (k -1)]w 2 (k -1) ≈ w oplms + jR -1 E[y * LM S2 (k -1)x(k)] -jR -1 E[x(k)x H (k -1)]w 2 (k -1) ≈ w oplms + jR -1 E[x(k)x H (k -1)]w 2 (k -1) -jR -1 E[x(k)x H (k -1)]w 2 (k -1)
≈ w oplms (6.8) where w oplms = R -1 p is the LMS optimal weight vector. As such, by simplifying (6.8), we reach the following approximation w op ≈ w oplms and hence we can assume that w 1 (k) ≈ w 2 (k -1), i.e. the use of a single set of weights, w(k) [4]. We now simplify the pLMS weight update equation given in (6.3) and remove any requirement for computing an independent set of filter coefficients, i.e. additional filter [4]. As such, (6.3) becomes:

w(k + 1) = w(k) + µx(k)[d * (k) -x H (k)w(k) + jd * (k -1) -jx H (k -1)w(k)] (6.9)
where µ is the RC-pLMS step size, w(k) is the RC-pLMS filter weight vector. Thus, the RC-pLMS is presented as follows :

S(k) = d(k) -jd(k -1) u(k) = x(k) -jx(k -1) e RC-pLM S (k) = S(k) -w H (k)u(k) w(k + 1) = w(k) + µx(k)e * RC-pLM S (k) (6.10)
The RC-pLMS adaptive beamformer is formed of only one LMS filter with respect to two input adjustment blocks. Therefore, omitting the need for a second independent filter and reducing the original pLMS complexity by 2N + 1 complex multiplications and N + 2 complex additions [4]. The RC-pLMS MSE cost function, defined as

ξ RCpLM S (k) = E[|e RCpLM S (k)| 2 ]
, is re-evaluated to obtain [4]:

∇ RCpLM S = ∂ξ RCpLM S (k) ∂w H (k) = -p + Rw(k) -E[jd * (k -1)x(k)] + E[jx(k)x H (k -1)]w(k) +E[jd * (k)x(k -1)] -E[jx(k -1)x H (k)]w(k) -E[d * (k -1)x(k -1)] + E[x(k -1)x H (k -1)]w(k) (6.11)
where, ∇ RCpLM S is the RC-pLMS gradient. Assuming a WSS process, and using the equality Q r (τ ) = Q * r (-τ ) and z r (τ ) = z * r (-τ ), the RC-pLMS gradient defined in (6.11) can be re-written as [4]: (6.12) where the auto-correlation matrix and the cross-correlation vector are defined such as:

∇ RCpLM S = -p + Rw(k) -z * r (-1) + Q r (1)w(k) +z r (1) -Q * r (-1)w(k) -p + Rw(k) = -2p + 2Rw(k) -2z r (-1) + 2Q r w(k)
Q r (1) = jR(1) and z r (-1) = jp(-1), respectively and represent an observation with a lag τ = 1. Thus, by equating (6.12) to zero the RC-pLMS optimal weight, w opr , is obtained as [4,[START_REF] Bouboulis | Extension of Wirtinger's Calculus To Reproducing Kernel Hilbert Spaces And The Complex Kernel LMS[END_REF]:

w opr = A -1 (p + jp(-1)) (6.13)
where A is the RC-pLMS overall correlation matrix and it is formed as a linear combination of the auto-correlation matrices at lags 0 and 1 and is defined as:

A = R + jR(1) (6.14)
Assuming A is a full rank matrix; Thus its inverse A -1 exists as a consequence of the random added noise [2,4].

Stability Analysis

In order to determine the upper bound of the step size and the conditions where the RC-pLMS converges to its optimal weight, we perform a first order stability analysis. The analysis studied with respect to the RC-pLMS learning rate, i.e. µ and the mean coefficient error vector, v(k) [4,[START_REF] Widrow | The Complex LMS Algorithm[END_REF][START_REF] Macchi | Second-Order Convergence Analysis Of Stochastic Adaptive Linear Filtering[END_REF] which is given by: v(k) = w(k)w opr (6.15) where w(k) is the mean weight vector. From (6.9), we can proceed as follows [4]:

w(k + 1) = w 1 (k) + µp -µRw(k) + jµp(-1) -jµR(1)w(k) (6.16)
At steady state and assuming convergence, we can approximate w(k + 1) ≈ w(k) and w(k -1) ≈ w(k). As such, (6.16) becomes [4]:

w(k + 1)w opr = w(k)w opr + µp + jµR(1)w opr -µRw(k) -µRw opr +µRw opr + jµp(-1) -jµR(1)w opr + µR(1)w(k) (6.17) where w opr is the RC-pLMS optimal weight vector. Using the mean coefficient error vector notation and equations (6.13), (6.17), we can write [4]:

v(k + 1) = (I -µR -jµR(1))v(k) -µRA -1 p -jµRA -1 p(-1)
+µp + jµp(-1)-µR(1)A -1 p + µR(1)A -1 p(-1) (6.18)

Hence, (6.18) can be simplified to obtain [4]: (6.19) can be simplified as follows [4]:

v(k + 1) = (I -µR -jµR(1))v(k) + µp -µ(R + jR(1))A -1 p +jµp(-1) -µ(jR -R(1))A -1 p(-
v(k + 1) = (I -µR -jµR(1))v(k) = (I -µA)v(k) (6.20)
Applying the eigenvalue decomposition (EVD), with Λ being a diagonal matrix whose diagonal entries (λ i ) represent to the eigenvalues of A, and O is a unitary matrix whose rows represent the eigenvectors of A, it is possible to write A = O -1 ΛO [2,4]. Therefore, we can rewrite (6.20) as follows:

v(k + 1) = (I -µO -1 ΛO)v(k) (6.21)
by multiplying both sides of (6.21) by the unitary matrix O, we get [4]:

Ov(k + 1) = (I -µΛ)Ov(k) (6.22)
Let m(k) = Ov(k), which represents v(k) in a rotated coordinate system and it is defined by the eigenvectors in O. Therefore, a convergence in m(k) implies a convergence in v(k) [2,4,[START_REF] Widrow | The Complex LMS Algorithm[END_REF], and we obtain:

m(k + 1) = (I -µΛ)m(k) (6.23)
Since all elements in (I -µΛ) are diagonal, the stability is achieved with respect to the convergence of the first order difference equation formed by all N eigenvalues λ i , ∀i, i ∈ {1, 2, .., N } [2,4]. Thus, with respect to (6.23), we can define a set of N difference equations as follows:

m i (k + 1) = (1 -µλ i )m i (k) (6.24)
The convergence of (6.24) is obtained by satisfying the condition |1 -µλ i | < 1 [2,4,[START_REF] Macchi | Second-Order Convergence Analysis Of Stochastic Adaptive Linear Filtering[END_REF]. Moreover, for the convergence in the mean sense the step size should satisfy the following condition:

µ < 1 |λ A,max | (6.25)
where the norm, |λ A,max |, is the maximum eigenvalue in A and |.| is the complex modulus i.e. Re{λ} 2 + Im{λ} 2 [4].

Transfer Function Approximation

Similar to the pLMS, the RC-pLMS transfer function approximation is obtained by modeling the input source as a temporal fractional delay FIR filter with a Lagrange interpolation [4]. As such, with respect to Appendix D, the pLMS transfer function is modified to reflect (6.10) and thus the RC-pLMS transfer function becomes as follows:

H RC-pLM S (z) = 1 -jz -1 1 + µN (1 -jz -1 )R(z) (6.26)
The RC-pLMS transfer function approximation, given in (6.26), modifies that of the LMS to include the additional delay and phase shift term 1 -jz -1 .

Quantization Effect Analysis

Adaptive algorithms, when implemented in finite precision and fixed point format can suffer a sever degradation in performance and diverge from their theoretical values [2,4,[START_REF] Srar | LLMS Adaptive Beamforming Algorithm Implemented With Finite Precision[END_REF][START_REF] Meyer-Baese | Digital Signal Processing with Field Programmable Gate Arrays (Signals and Communication Technology)[END_REF][START_REF] Srar | Performance of an LLMS Beamformer in the Presence of Element Gain and Spacing Variations[END_REF]. Such performance decay is a result of quantization and round off errors due to the limitations imposed by the finite precision wordlength. Therefore, such errors, if not accounted in the design process, can cause catastrophic outcomes [2,4,[START_REF] Srar | LLMS Adaptive Beamforming Algorithm Implemented With Finite Precision[END_REF][START_REF] Meyer-Baese | Digital Signal Processing with Field Programmable Gate Arrays (Signals and Communication Technology)[END_REF][START_REF] Srar | Performance of an LLMS Beamformer in the Presence of Element Gain and Spacing Variations[END_REF]. Thus, the analysis of the effects of quantization and round off errors becomes mandatory when targeting digital systems with a finite precision [2,4,[START_REF] Srar | LLMS Adaptive Beamforming Algorithm Implemented With Finite Precision[END_REF][START_REF] Caraiscos | A Roundoff Error Analysis Of The LMS Adaptive Algorithm[END_REF].

For simplicity, we assume that the input and reference signals are Gaussian, zero-mean, uncorrelated and generated from an independent identically distributed (i.i.d) sequences. Additionally, the RC-pLMS analysis parameters u q (k), w q (k), S q (k), e q (k) and y q (k), where the subscript q denotes the quantization process, are defined such as [4]:

u q (k) = u(k) + η u (k) w q (k) = w(k) + η w (k) S q (k) = S(k) + η S (k) y q (k) = y(k) + η y (k)
e q (k) = S q (k) -y q (k) (6.27) where η u (k), η w (k), η S (k) and η y (k) are the input signal, weight vector, reference signal and output quantization error respectively [4]. The quantization errors, η u (k) and η w (k), are assumed to be zero mean white sequences with variance σ 2 d , mutually independent and are also independent of u(k) and w(k), respectively. Hence, from (6.27) and the error update term in (6.10) we can write [4]:

e q (k) = S q (k) -y q (k) = S(k) + η S (k) -w H q (k)u q (k) -η y (k) = S(k) + η S (k) -w H (k)u(k) -w H (k)η u (k) -η w (k)u(k)-η * w (k)η u (k) -η y (k) (6.28)
By eliminating higher order quantization error terms, i.e. η * w (k)η u (k) = 0, (6.28) simplifies to [4]:

e q (k) = e RCpLM S (k) + η Sy (k) -w H (k)η u (k) -η w (k)u(k) (6.29)
with η Sy (k) = η S (k) -η y (k). The RC-pLMS MSE subject to a quantization error, RC-pLMSq, can now be defined as ξ RCpLM Sq (k) = [|e q (k)| 2 ] and evaluated to obtain [4]:

ξ RCpLM Sq (k) = E[|e q (k)| 2 ] = ξ RCpLM S (k) + E[e RCpLM S (k)η * Sy (k) + e * RCpLM S (k)η Sy (k) -e RCpLM S (k)w(k)η * u (k) -e RCpLM S (k)u H (k)η * w (k) -e * RCpLM S (k)w H (k)η u (k) -e * RCpLM S (k)u(k)η u (k)] (6.30)
Partie , Chapter 6 -The Reduced Complexity Parallel LMS and its Pipeline Hardware Implementation

Assuming the step size µ is small enough, the quantization error terms η w (k)u(k) and w(k)η u (k) becomes uncorrelated with each other and with the RC-pLMS error e RCpLM S (k) [2,4]. Therefore, from [2,4], (6.30) is simplified to become:

ξ RCpLM Sq (k) = E[|e q (k)| 2 ] = J min (1 + ρ) + ξ 1 (σ 2 w , µ) + ξ 2 (σ 2 d ) (6.31)
where J min (1 + ρ) is the MSE of the infinite precision algorithm, ρ is the misadjustment, ξ 1 (σ 2 w , µ) is the quantization error resulting from η w (k) and ξ 2 (σ 2 d ) is the quantization error resulting from η u (k) and η y (k) [2,4]. With respect to [4,[START_REF] Caraiscos | A Roundoff Error Analysis Of The LMS Adaptive Algorithm[END_REF], (6.31) can now be written, at convergence, as follows:

ξ RCpLM Sq (k) = E[|e q (k)| 2 ] = ξ min + 1 2 µξ min tr(A) + N σ 2 a 2η u (k)µ + 1 η 2 u (k) (|w op | 2 + a)σ 2 d (6.32)
where ξ min is the infinite precision LMS minimum MSE, tr(A) is the trace of the correlation matrix A, i.e. sum of diagonal elements, a is a random variable dependent on the inner product of w H q (k) and u q (k) and σ 2 a is the variance of a [4,[START_REF] Caraiscos | A Roundoff Error Analysis Of The LMS Adaptive Algorithm[END_REF]. From (6.31) and (6.32), it is clear that the step size directly contributes to the performance of the systems. Where, a decrease in the step size µ leads to a decrease in the misadjustment ρ and thus an improved performance [2,4]. Moreover, by evaluating the third term in (6.32), a decrease in the step size µ increases the quantization error effect and causes the system to deviate from the infinite precision, theoretical, performance. Finally, the final term in (6.32) is only a function of the quantization errors η u (k) and η y (k) [2,4,[START_REF] Caraiscos | A Roundoff Error Analysis Of The LMS Adaptive Algorithm[END_REF]. Therefore, it can be concluded that, in finite precision mode, the correct selection of the step size µ directly contributes to the stability and convergence of the systems. As such, µ may be decreased to a certain level, where the degradation effects of the quantization error become significant [2,4].

DRC-pLMS Pipelined Hardware Implementation

Similar to the delayed LMS (DLMS) and the delayed parallel LMS (DpLMS) the RC-pLMS pipeline architecture is obtained through the application of the delay and sum relaxed look ahead technique (DRC-pLMS) [4,[START_REF] Shanbhag | Relaxed Look-Ahead Pipelined LMS Adaptive Filters And Their Application To ADPCM Coder[END_REF][START_REF] Akkad | Two Stages Parallel LMS Structure A Pipelined Hardware Architecture[END_REF]. As such, assuming a WSS process, (6.9) is modified by adding a delay relaxation of D 1 samples in the error path and D 2 delay in the weight update path, as follows [4]:

w(k + 1) = w(k -D 2 ) + µ D 2 -1 i=0 e * RCpLM S (k -D 1 -i)x(k -D 1 -i) (6.33)
From (6.33), it is clear that the hardware overhead is extensive, i.e. N (D 2 -1). Additionally, for larger values of N and D 2 , the hardware overhead becomes unacceptably high resulting in a complex, undesirable structure [4,[START_REF] Shanbhag | Relaxed Look-Ahead Pipelined LMS Adaptive Filters And Their Application To ADPCM Coder[END_REF]. To reduce the occurring overhead, (6.33) is modified by applying a sum relaxation of D 3 samples with 1 ≤ D 3 ≤ D 2 . As such, (6.33) becomes [4]:

w(k + 1) = w(k -D 2 ) + µ D 3 -1 i=0 e * RCpLM S (k -D 1 -i)x(k -D 1 -i) (6.34)
Assuming µ is small enough, the DRC-pLMS error is computed as:

e RCpLM S (k) = S(k) -w H (k -D 2 )u(k) (6.35)
In contrast to the traditional look ahead technique, the delay and sum relaxed look-ahead technique does not result in a unique architecture. However, it may be considered as a transformation in the stochastic sense since the average output profile is conserved [4,[START_REF] Shanbhag | Relaxed Look-Ahead Pipelined LMS Adaptive Filters And Their Application To ADPCM Coder[END_REF].

DRC-pLMS Hardware Architecture

DRC-pLMS is implemented in a finite precision mode for a Q2. The 4-input linear combiner and weight update blocks are presented in Figures 6.3 and 6.4, respectively. From Figure 6.3, we observe that the pipeline stages are formed of independent parallel multiplication and addition operations and thus requires a computational complexity of O(1) [4]. Where each complex multiplier is formed of four real multipliers and one complex adder, i.e. two real adders [4]. In addition, the update term shown in Figure 6.4, is computed with respect to an arithmetic shift right of nu bits. The shifting operation is performed at the wire speed and thus eliminates the need of an

Implementation and Synthesis Results

The DRC-pLMS is implemented on the "Intel Stratix V 5SGXMABN3F45I4" model and compared to the VR-SNC-TDNLMS [START_REF] Zhao | A Division-Free and Variable-Regularized LMS-Based Generalized Sidelobe Canceller for Adaptive Beamforming and Its Efficient Hardware Realization[END_REF] and the LUT-Less Pipelined LMS [START_REF] Sarma | A Novel Time-Shared and LUT-Less Pipelined Architecture for LMS Adaptive Filter[END_REF] as shown in Table 6.1 [4]. Since the VR-SNC-TDNLMS [4,[START_REF] Zhao | A Division-Free and Variable-Regularized LMS-Based Generalized Sidelobe Canceller for Adaptive Beamforming and Its Efficient Hardware Realization[END_REF] and the LUT-Less Pipelined LMS [4,[START_REF] Sarma | A Novel Time-Shared and LUT-Less Pipelined Architecture for LMS Adaptive Filter[END_REF] implementation is conducted for different antenna count, different processors and different finite precision configuration, only the maximum operating frequency is compared.

As shown in Table 6.1, compared to the VR-SNC-TDNLMS [4,[START_REF] Zhao | A Division-Free and Variable-Regularized LMS-Based Generalized Sidelobe Canceller for Adaptive Beamforming and Its Efficient Hardware Realization[END_REF] and the LUT-Less Pipelined LMS [4,[START_REF] Sarma | A Novel Time-Shared and LUT-Less Pipelined Architecture for LMS Adaptive Filter[END_REF] variants, the DRC-pLMS achieved a pipeline structure operating at a maximum frequency of 208.33 MHz. Moreover, in contrast to the DpLMS, the DRC-pLMS only requires the use of 32 DSP blocks, i.e single LMS stage. However, compared to the LMS and DLMS [START_REF] Shanbhag | Relaxed Look-Ahead Pipelined LMS Adaptive Filters And Their Application To ADPCM Coder[END_REF], the proposed RC-DpLMS provides a superior convergence behavior and a lower steady state error at the cost of a negligible increase in resource Partie , Chapter 6 -The Reduced Complexity Parallel LMS and its Pipeline Hardware Implementation source is modeled as a ULA array with N = 8 elements. The input signal is formed by a combination of a message signal and two interferes impinging the array from broadside at different angles of arrival (AOA) of 30 • , 45 • and 80 • , respectively [4]. The inputs are generated as independent random complex Gaussian sequences of the form v m = N (0 , σ 2 p ) + jN (0 , σ 2 q ) where, N denotes normal, zero mean, (Gaussian) distribution. σ 2 p and σ 2 q are the real and complex sequence variances, respectively. The final input signal is corrupted by CAWGN for a signal to noise ratio (SNR) of 10 dB and σ 2 p = 0.01 and σ 2 q = 0.04. The parameters and initial conditions at k = 0 are initialized for the LMS and its variants with respect to Table 6.2, where I is the identity matrix.

Mean Square Error Analysis

The MSE simulation is used to study the convergence behavior of the least mean square -least mean square (LLMS), the pLMS, the RC-pLMS, the LMS and the recursive least square (RLS) [4]. From Figure 6.5, the RC-pLMS presented identical pLMS and LLMS convergence behavior. Moreover, for an SNR of 10 dB and in contrast to the LMS with a step size of 0.5, i.e. maximum suggested step size [2,4], the RC-pLMS preserved a superior convergence profile with the use of a much smaller step size µ RCpLM S = 0.0156 [4]. Additionally, RC-pLMS achieved its convergence in 3 iterations, and a low steady state error < 0.005 [4]. The use of a small step size allows the RC-pLMS to maintain its convergence in low SNR environments [4,[START_REF] Akkad | A Multi-Stage Parallel LMS Structure and its Stability Analysis Using Transfer Function Approximation[END_REF]. However, compared to the RLS with a computational complexity of order O(N 2 ), the suggested RC-pLMS presented faster convergence while maintaining a LMS like computational complexity of order O(N ) [4]. Moreover, the MSE behavior describes the systems convergence behavior with respect to the transient (pLMS) and the steady-state (RC-pLMS) approximation, thus validating the use of single set of weights as presented in (6.9). To further assess the performance and the stability of the RC-pLMS and the DRC-pLMS for different SNR environments, the MSE simulation was re-evaluated for multiple SNR, i.e. -5 dB to 7 dB with a step of 6 dB [4]. From Figure 6.6, it is clear that the RC-pLMS maintained its accelerated convergence and low residual error profile for a SNR = 1 dB. In contrast, for an SNR = -5 dB, RC-pLMS only maintain an accelerated convergence In contrast, as shown in Figure 6.7, the DRC-pLMS was able to maintain accelerated convergence at SNR = 1 dB, however with a larger residual error. Such degradation is a consequence of the sum relaxation adopted in (6.34) [4].

Beam Radiation Pattern

The beam radiation pattern simulation output is presented, in Figure 6.8, to illustrate and compare the beam directivity of the RC-pLMS, the DRC-pLMS and the finite precision DRC-pLMS to that of the finite precision DLMS. From Figure 6.8, and for a SNR environment of 10 dB, similar to the DLMS, the proposed finite precision DRC-pLMS is able to accurately steer the output main beam towards the desired AOA, i.e. 30 • while nulling interfering signals at 45 • and 80 • [4]. Moreover, the finite precision, DRC-pLMS shows near identical results to the theoretical models denoted by RC-pLMS and DRC-pLMS [4]. The RC-pLMS and DRC-pLMS beam radiation pattern is re-evaluated for different SNR environments, i.e.-5 dB to 7 dB with a step of 6 dB [4]. From Figure 6.9, the RC-pLMS successfully steered its main beam and nulls towards the AOA of interest, with an acceptable accuracy, for a SNR environment as low as 1 dB [4]. In contrast, as shown in Figure 6.10, the DRC-pLMS has managed to only steer its main beam towards the AOA of the desired signal for an SNR environment of up to 1 dB. The resulting degradation in beam accuracy perfectly align with the MSE results presented in Figures 6.6 and 6.7 where the average MSE becomes unacceptable for SNR < 1 dB [4]. Additionally, the difference in accuracy between the RC-pLMS and DRC-pLMS is caused by the sum approximation implied in (6.34) [4]. Such difference can be omitted for increased accuracy by setting D 3 = D 2 , however at the cost of a considerable increase in resource usage [4].

Pole Zero Map Stability Plot

In order to numerically determine the maximum step size allowed for the RC-pLMS a pole zero plot is performed for the transfer function approximation in (6.26). The RC-pLMS stability analysis is studied for different µ values and the pole zero plot is shown in Figure 6.11. As the step size µ increases the resulting poles and zeros move further towards the outside of the unit circle. Thus, it can be concluded from the conducted study that the maximum step size to ensure convergence and stability falls in the range of 0.03 < µ < 0.04.

Computational Complexity Comparison

A resource complexity comparison for the RC-pLMS, the RLS, the LMS and their variants is presented in Table 6.3, where cMultiply, cAdd, cDivide and RLMSp denote the complex multiplication, the complex addition, the complex division and the parallel RLMS, respectively [4]. From Table 6.3, the RLS algorithm and its variants require an higher computational complexity of order O(N 2 ). Moreover, both the RLMS and the RLMSp mandate the use of N + 1 and 1 complex dividers, respectively [4]. In contrast, compared to the LLMS and the pLMS, the RC-pLMS provides near identical LMS resource usage and linear computational complexity of order O(N ) while providing a superior convergence profile and a lower residual error floor [4]. Thus, with respect to a marginal increase in resource requirements, i.e. additional adders and subtractors, the RC-pLMS eliminated the LMS convergence speed and error floor trade off, while preserving a LMS like low complexity structure.

Conclusion

In this chapter, we proposed a reduced complexity parallel LMS structure (RC-pLMS) for adaptive beamforming, we evaluated its transfer function approximation and we implemented its pipeline hardware implementation. RC-pLMS is formed of a simple LMS stage with additional modified inputs. The modified inputs are formed by applying a sample delay to the input and desired signals and multiplied by a phase shift, i.e. imaginary number j. The RC-pLMS transfer function approximation is obtained by modeling the input spatial linear combiner as a finite impulse response (FIR) fractional delay temporal filter with a Lagrange interpolation. Moreover, we propose a pipeline hardware imple-mentation through the application of the delay and sum relaxed look ahead technique (DRC-pLMS). Stability and quantization effect analysis are performed to determine the upper bound of the step size required to ensure convergence, as well as the behavior of the system with finite precisions. The maximum allowable step size is determined numerically with respect to the transfer function approximation and the pole zero plot study. Simulation results demonstrate the superior performance of the RC-pLMS and DRC-pLMS in providing accelerated convergence and maintaining a low steady state error while preserving a complexity of order O(N ). The RC-pLMS beam pointing accuracy was evaluated to better highlight its precision and was represented with the beam radiation pattern. Compared to the LLMS and pLMS the RC-pLMS presented a high accuracy beam pattern by accurately steering its main beam towards the desired signal better nulls towards the two interreferences. Furthermore, the RC-pLMS superior performance was achieved by a marginal increase in resource usage, compared to the LMS. Also, compared to the Recursive Least Square (RLS) with quadratic complexity, the RC-pLMS presented near identical behaivor in a linear complexity form. With respect to the pLMS, the RC-pLMS presented similar behavior at half the resource requirements. RC-pLMS and DRC-pLMS algorithms presented a satisfactory convergence profile and beam patterns for a SNR environment as low as 1 dB. Through a pole zero plot analysis the maximum step size allowed to maintain proper RC-pLMS convergence is found to be in the range of 0.03 < µ < 0.04. Synthesis and implementation results show that, in contrast to other RLS and LMS variants, the RC-pLMS provides a parallel, pipeline, low complexity and resource friendly architecture suitable for low end processors. Finally, the fixed point DRC-pLMS beam radiation pattern validated the DRC-pLMS accuracy in a finite precision mode by providing similar infinite precision beam steering. The resulting work has been published in the IEEE Transaction of Circuits and Systems.

CONCLUSION AND FUTURE WORK

Conclusion

Adaptive beamforming has become an inevitable feature in smart antenna systems to infer frequency reuse and ease spectral congestion by directional signal reception and transmission. However, the recent, exponential, growth of internet connected devices has exhausted spectral resources and imposed challenging constraints on adaptive algorithms when implemented on dedicated, limited resource, devices, i.e. field programmable gate array (FPGA). Such constraints are reflected by the requirements of the system to deliver accelerated convergence and high accuracy while maintaining a low complexity and a high throughput architecture.

The least mean square (LMS) is a popular and widely used adaptive algorithm in beamforming given its attractive, low complexity, O(N ) structure, where N is the number of antenna elements, most suitable for a hardware implementation. However, in contrast to its desirable features, the LMS still suffers from a trade off between its convergence speed and steady state error, i.e. accuracy. Moreover, presenting a pipeline LMS architecture is difficult due to the presence of the error feedback path in the weight update equation.

Several variants of the popular least mean square (LMS) have been proposed to present an improved convergence profile with minimal residual error. Similarly, several work has been conducted to implement high throughput, low complexity, pipeline parallel LMS architecture on FPGA. Such modifications are, and not limited to, the use of either of the following:

-The use of a normalized or variable step size to eliminate the LMS error floor and convergence speed trade off, such as: the normalized LMS (NLMS) [START_REF] Nascimento | The Normalized LMS Algorithm With Dependent Noise[END_REF], the variable step size LMS (VSSLMS) [START_REF] Gorriz | Speech Enhancement in Discontinuous Transmission Systems Using the Constrained-Stability Least Mean Squares Algorithm[END_REF][START_REF] Kwong | A Variable Step Size LMS Algorithm[END_REF] and the modified robust VSSLMS (MRVSSLMS) [START_REF] Xiubing | A New Modified Robust Variable Step Size LMS Algorithm[END_REF].

-The use of a multi stage adaptive algorithm to accelerate LMS convergence while maintaining minimal steady state error, such as: the least mean square -least mean square (LLMS) [5], the recursive least mean square (RLMS) [START_REF] Srar | Adaptive Array Beam Forming Using A Combined RLS-LMS Algorithm[END_REF], the Kalman-LMS and Kalman-RLS [START_REF] Akkad | An Efficient Non-Blind Steering Vector Estimation Technique For Robust Adaptive Beamforming With Multistage Error Feedback[END_REF], the parallel RLMS (RLMSp) [6] and the parallel LMS (pLMS) [START_REF] Akkad | A Multi-Stage Parallel LMS Structure and its Stability Analysis Using Transfer Function Approximation[END_REF].

-The use of different delay and approximation techniques to present a pipeline LMS architecture, such as: the delay and sum relaxed look-ahead technique [START_REF] Shanbhag | Relaxed Look-Ahead Pipelined LMS Adaptive Filters And Their Application To ADPCM Coder[END_REF][START_REF] Akkad | Two Stages Parallel LMS Structure A Pipelined Hardware Architecture[END_REF], the time shared look up table (LUT)-less LMS [START_REF] Sarma | A Novel Time-Shared and LUT-Less Pipelined Architecture for LMS Adaptive Filter[END_REF] and the division free and variable regularized LMS [START_REF] Zhao | A Division-Free and Variable-Regularized LMS-Based Generalized Sidelobe Canceller for Adaptive Beamforming and Its Efficient Hardware Realization[END_REF].

Despite the listed modifications, the resulting LMS variants either presented an improved convergence profile, at the cost of an increase of complexity or presented a pipeline hardware architecture without any significant improvement on the theoretical performance, i.e. convergence speed and accuracy.

To present a high accuracy and fast converging adaptive beamforming structure, while maintaining an easy to pipeline low complexity LMS like design, we proposed the reduced complexity parallel LMS (RC-pLMS) algorithm. The RC-pLMS is formed of a single LMS stage with additional modified inputs and a linear computational complexity of order O(N ). Moreover, we implemented the RC-pLMS design in a parallel pipeline high throughput architecture through the application of the delay and sum relaxed look ahead technique (DRC-pLMS). The superior performance of the RC-pLMS and the finite precision DRC-pLMS has been demonstrated through extensive software and hardware simulations. Our contributions throughout this thesis are detailed as follows:

-We performed an experimental study in order to evaluate the behavior of popular signal processing algorithms, i.e. fast Fourier transform (FFT), used in frequency domain beamforming when implemented on limited resource devices. The FFT was implemented considering different architectures, i.e. sequential or parallel, different processors, i.e. FPGA and system on chip (SoC) and different design tools, traditional hardware description language (HDL), high level language (HLL) and high level synthesis (HLS) tools. Through simulation and synthesis results, we demonstrated the efficiency of using HLL and HLS design tools in targeting heterogeneous multi core architectures with embedded digital signal processing (DSP) processors. Additionally, the use of HLS tools resulted in improved design optimization, com-pared to the classical HDL tools, through the use of specific compiler directives, thus reducing design and testing time by two thirds. However, since the HLL optimization efficiency is highly correlated with the HLS compiler, it becomes mandatory to use simple and atomic design techniques. We published this contribution in the IEEE International Multidisciplinary Conference on Engineering Technology (IM-CET) [START_REF] Akkad | FFT Radix-2 and Radix-4 FPGA Acceleration Techniques Using HLS and HDL for Digital Communication Systems[END_REF].

-While the FFT processor is one of the core arithmetic operations in frequency domain beamforming, its performance significantly contributes towards the algorithms convergence speed and beam pointing accuracy. Thus, in this thesis, we proposed a low complexity, high accuracy, dynamic twiddle factor generator based on the Chebyshev polynomial approximation for the sine and cosine functions. Additionally, we proposed its finite precision and high throughput parallel pipeline, hardware implementation. Simulation and synthesis results illustrated the upper level accuracy of the proposed Chebyshev polynomial approximation compared to the traditional Taylor and coordinate rotation digital computer (CORDIC) techniques. We should highlight that only the Chebyshev polynomial approximation achieved a high precision, three decimal digits, low complexity high throughput design. This work has been published in the Applications in Electronics Pervading Industry, Environment and Society (APPLEPIES) conference [START_REF] Akkad | Twiddle Factor Generation Using Chebyshev Polynomials and HDL for Frequency Domain Beamforming[END_REF].

-Inspired by the enhanced performance of the multi stage adaptive beamforming algorithms, i.e. LLMS and RLMS. We conducted an experimental study for different multi stage designs and studied the effect of the steering vector estimation, i.e the cascading stage, on the behavior of the system. Experimental results concluded that the use of the steering vector cascading stage can severally degrade the accuracy of the system and might cause it to diverge from its theoretical value as a consequence of the division operation, i.e. underflow. Moreover, the estimate cascading stage introduces additional computational complexity and thus a larger hardware overhead when implemented on FPGA. Additionally, the cascading nature of the system makes it extremely difficult to present a pipeline and parallel hardware architecture. This contribution has been published in the KES International Conference on Intelligent Decision Technologies (KES-IDT) [START_REF] Akkad | An Efficient Non-Blind Steering Vector Estimation Technique For Robust Adaptive Beamforming With Multistage Error Feedback[END_REF].

-In order to eliminate the requirements of using a steering vector estimate block, we proposed the RLMSp multi stage adaptive beamformer design with parallel inputs. Additionally, the second stage, LMS feedback error was multiplied by a phase shift, i.e. the imaginary number j, for robustness against repeated samples. Simulation results demonstrated the superior performance of the proposed RLMSp with respect to the cascade multi stage structures, i.e. LLMS and RLMS. It has been shown that the proposed RLMSp maintained an accelerated convergence and high accuracy profile under different SNR environments, however with a reduced complexity and a parallel ready architecture. Moreover, by omitting the use of the steering vector estimate block the complexity of the system was reduced by 20N real multiplications, 6N real additions and 2N real divisions. We published this part of our work in the European Signal Processing Conference (EUSIPCO) [6].

-As, the RLMSp still exhibits 2N real divisions and an undesirable computational complexity of order O(N 2 ) making it a unfavorable choice for a pipeline hardware implementation. Thus, we proposed a two stages parallel input LMS structure, i.e. pLMS, for adaptive beamforming and its transfer function approximation. Additionally, in order to present a high throughput pipeline architecture we propose the application of the delay and sum relaxed look ahead technique (DpLMS) for each of the LMS stages. Simulation results demonstrated the superior performance of the pLMS in maintaining an accelerated convergence and a low steady state error profile in an SNR environment as low as 1 dB, compared to other variants. In contrast to the RLMSp, the pLMS exhibits an attractive, linear, computational complexity of order O(N ) and does not necessitate the use of extensive division routines. The theoretical stability analysis is conducted to determine the upper bound of the step size. Additionally, the maximum pLMS step size was numerically determined with respect to the transfer function approximation. Moreover, the pipeline DpLMS design was implemented on FPGA and showed identical, theoretical, beam pointing accuracy, thus further validating its efficiency in finite precision. Synthesis results showed that the pLMS achieved a maximum operating frequency of 208.33 MHz in a low complexity, low latency high throughput design. The work conducted for the pLMS derivation and its hardware implementation has been separately published in the European Signal Processing Conference (EUSIPCO) [START_REF] Akkad | A Multi-Stage Parallel LMS Structure and its Stability Analysis Using Transfer Function Approximation[END_REF][START_REF] Akkad | Two Stages Parallel LMS Structure A Pipelined Hardware Architecture[END_REF].

-While the pLMS presented highest performing and the easiest to pipeline structure, it still doubles the complexity of the classical LMS and requires the use of two independent LMS filters. As such, we proposed The RC-pLMS makes use of a single LMS stage in a similar low complexity design. Similar to the pLMS, in order to implement the RC-pLMS in a low latency, high throughput architecture on FPGA, we proposed the application of the delay and sum relaxed look ahead technique (DRC-pLMS). Simulation results demonstrated the outstanding performance of the proposed RC-pLMS compared to different adaptive beamforming algorithms.

In contrast to the LLMS and pLMS variants, the RC-pLMS reduced the systems resource requirements by half, i.e single LMS stage, while maintaining accelerated convergence, high accuracy and robustness against repeated samples for a signal to noise ratio (SNR) environment as low as 1 dB. Stability analysis and quantization effect have been performed to study the behavior of the system and its robustness. Additionally, the maximum RC-pLMS step size was numerically determined with respect to the transfer function approximation. To further assess the behavior of the system, and compare it to that of the infinite precision theoretical value, we implemented the DRC-pLMS in finite precision mode on FPGA. Hardware simulation results, for the finite precision DRC-pLMS, showed similar infinite precision theoretical convergence behavior and beam pointing accuracy. Synthesis results show that the DRC-pLMS reached a greater operating frequency and low resource usage compared to other LMS implementations. Moreover, compared to the classical LMS pipeline implementation, the DRC-pLMS is achieved at the cost of a marginal and negligible increase in resource usage, i.e. two adders. The resulting work has been published in the IEEE Transaction of Circuits and Systems [4].

Finally, we can state that the RC-pLMS and the finite precision DRC-pLMS satisfied the set constraints by presenting a high performance, high accuracy adaptive beamforming algorithm while maintaining a low complexity high throughput LMS like hardware architecture.

Future Work

Adaptive beamforming is still an attractive area of research and with the recent achievement in communications and processor architectures, the benefits become countless.

I -In the short to medium term, we should try to enhance the results obtained through this thesis. Indeed, the RC-pLMS developed in chapter 6 of this thesis, is designed for a single linear antenna system and narrow band signals. To further explore its potential, we are planning to extend the actual version by investigating the following improvements:

a) In the proposed design, the RC-pLMS implements at its core a classical LMS algorithm, as such it would be worthwhile to study the performance of the system with respect to other variants, i.e. genetic LMS algorithm.

b) 3G, 4G, 5G and further generations dedicated to multimedia and fast internet access should consider wide band signals. Therefore, the RC-pLMS algorithm should be evolved to deal with such signals.

c) To conduct real world experiments and assess the systems behavior with respect to the fading and scattering effects.

d) With respect to the unprecedented popularity of the nanosatellite "CubeSat" communication systems and the spacing constraints they propose, it becomes interesting to investigate the RC-pLMS adaptive algorithms behavior and resources utilization for different antenna array structures, i.e. rectangular and circular, and study its robustness. Due to the strict CubeSat geometry constraints imposed, the proposed algorithm should be evaluated for robustness against the presence of element gain and different inter-element spacing.

II -Light fidelity (Li-Fi) communication systems [START_REF] Nor | Millimeter Wave Beamforming Training Based on Li-Fi Localization in Indoor Environment[END_REF] have gained popularity in indoor usage for communication and localization given their high speed transmission rate and free license. Thus, it would be challenging to implement a high accuracy beamformer system with a low complexity hardware architecture.

III -5G+ and 6G networks are key enablers of the future intelligent, communication, networks and machines and are expected to provide multi-user multi-terabyte per second (Tb/s) data rates [START_REF] Zhang | 6G Wireless Networks: Vision, Requirements, Architecture, and Key Technologies[END_REF]. 5G+ and 6G networks will probably use dedicated artificial intelligence processors and will require real time inference. As such, it will be extremely challenging to develop adaptive beamforming algorithms, for intelligent networks, through the use of deep learning systems and dedicated artificial intelligent processors that meets the networks requirements. We are willing to extend our research axes to include these new challenges.

assuming that the input signal and the available tap weights are uncorrelated the expectation of equation (6.38) can be written as:

E[x
(k)E[x(k)x H (k -1)]w 2 (k -1) +jE[d(k)x H (k -1)]w 1 (k) + jw H 2 (k -1)E[d(k)x(k -1)] +jE[x H (k)w 1 (k)w H 2 (k -1)x(k -1)] -jE[d(k)x H (k -1)]w 2 (k -1) (6.50)
where w 1 (k) is the tap weight of interest.

RC-pLMS Mean Square Error

The RC-pLMS MSE, ξ RC-pLM S , can be obtained from ( where w(k) is the tap weight of interest.

As shown in Figure 6.12, compared to the RLS with a quadratic complexity, the linear complexity RC-pLMS presented a fast and smooth convergence behavior where it achieved its convergence in the first 5 iterations.

The RC-pLMS is now re-evaluated, with respect to its beam pattern plot, for different SNR environments. The desired message is incoming at an angle of arrival of 30 In order to further evaluate the performance of the RC-pLMS we plot its MSE beam localization behavior with respect to the angle of arrival. As shown in Figure 6.14, compared to the RLS with a quadratic computational complexity the linear pLMS presented similar accelerated convergence behavior where it achieved beam convergence in the first few iterations. Also, compared to the pLMS the RC-pLMS presented near identical convergence behavior and accuracy with only half of the resource requirements, thus futrher validating its reliability.

putting w 1 (0) = w 2 (0) = 0, we obtain:

y 1 (k) = µ 1 k-1 i=0
β i (k)e pLM S (i) (6.58)

y 2 (k) = µ 2 k-1 i=0
β i (k)e 2 (i) (6.59) where β i (k) = x H f (i)x f (k). Moreover, since β i (k) is time varying, it is difficult to achieve a solvable difference equation. However, we know that:

β i (k) = N -1 j=0
x f (i-j) x f (k-j) = N r ki (6.60)

r ki = 1 N N -1 j=0
x f (i-j) x f (k-j) (6.61) and r ki is the input signals auto-correlation estimate. Considering the input signal is WSS and its properties can be estimated by a time average to obtain r ki ≈ r k-i . Hence, (6.58) and (6.59) can be approximated as having constant coefficients:

y 1 (k) = N µ 1 k-1 i=0
r k-i e pLM S (i) (6.62)

y 2 (k) = N µ 2 k-1 i=0
r k-i e 2 (i) (6.63) Furthermore, applying the Z transform to both sides of (6.62) and (6.63), we get: Additionally, by taking the expectation, it is assumed that r k-i is the auto-correlation coefficient instead of its estimate and R(z) = r 1 z -1 + r 2 z -2 + .... is a polynomial in the Z field. Furthermore, from (6.54), (6.64) and (6.

RC-pLMS Transfer Function Approximation

The RC-pLMS is computed following the same procedure of the pLMS and with respect to the LMS transfer function approximation in (6.68). Thus, the RC-pLMS transfer function approximation becomes as follows:

H RC-pLM S (z) = 1 -jz -1 1 + µN (1 -jz -1 )R(z) (6.71) Keywords: LMS, Adaptive Beamforming, FPGA, Sensor Array, RC-pLMS.

Abstract: Ever since its inception, adaptive beamforming has become an inevitable feature in smart antenna array to improve the spectrum efficiency. However, modern embedded wireless communication systems have imposed challenging constraints on adaptive algorithms when targeting a parallel and pipelined implementation on limited resource devices, like Field Programmable Gate Array (FPGA). Such constraints include reduced complexity, parallelism, accelerated convergence and low residual error. Several variants of classical adaptive beamformers were proposed to accelerate the convergence while maintaining a low error floor. Other suggestions focused on a parallel, pipeline architecture. The resulting beamforming algorithms either presented an improved convergence profile, at the cost of an increase of complex-ity or presented a pipeline hardware architecture without any significant improvement. To present a unified solution with superior convergence profile while maintaining a low complexity parallel pipeline architecture, we propose a two-stages algorithm, called parallel least mean square structure (pLMS). pLMS is further simplified to obtain the reduced complexity pLMS design (RC-pLMS). In order to design a pipelined hardware architecture, we applied the delay and sum relaxation technique (DRC-pLMS). A study on the behavior and the performance of different hardware design tools and processor architectures is conducted. Computer simulations demonstrated the outstanding performance of RC-pLMS. The DRC-pLMS can operate at a maximum frequency of 208.33 MHz with a minor increase in resource usage compared to LMS.

Figure 1 . 1 -

 11 Figure 1.1 -Classical Adaptive Filter

Figure 2 . 1 -

 21 Figure 2.1 -Antenna Array Radiation Pattern (Cartesian Plot)

  Figure 2.2 presents a ULA of N equally spaced antenna elements [29].

Figure 2 . 2 -

 22 Figure 2.2 -Uniform Linear Antenna Array Structure

Figure 2 . 3 -

 23 Figure 2.3 -Beam Radiation Pattern Vs Number of Antenna Elements with an Angle of Arrival of 0 • and an Inter Element Spacing of D a = λ2

Figure 2 . 4 - 2

 242 Figure 2.4 -ULA array Beam Radiation Pattern for Angle of Arrival 0 • and an Inter Element spacing of D a = λ2

Figure 2 . 5 -

 25 Figure 2.5 -Grating Lobes for Different Inter Element Spacing D a

Figure 2 . 8 -

 28 Figure 2.8 -Main Beam and Null Steering to θ 0 = 50 • and θ 1 = -15 • Respectively

Figure 3 .

 3 Figure 3.2 -Cascaded RLMS

Figure 3 . 3 -

 33 Figure 3.3 -Parallel Input RLMS (RLMSp)

  .

  4. In LLMS, the output of the first stage LM S 1 , y LM S1 (k), is multiplied by the estimate of the desired signals steering vector âd (k), forming the input, x 2 (k), to the LM S 2 stage similar to (3.25) and (3.27).

Figure 3 .

 3 Figure 3.4 -Cascaded LLMS

Figure 3 . 5 -

 35 Figure 3.5 -MSE Convergence Behavior For The LMS and RLS Adaptive Beamformers and Their Variants For SNR = 10 dB

Figure 3 . 6 -

 36 Figure 3.6 -MSE Convergence Behavior For The LMS and RLS Adaptive Beamformers and Their Variants For SNR = 5 dB

Partie , Chapter 4 -

 4 Overview of Digital Signal Processing Implementation Techniques on Embedded Systems

Figure 4 . 1 -

 41 Figure 4.1 -Pleumeur-Bodou Ground Station For Satellite Broadcasting [71]

  Figure 4.2.

Figure 4 . 2 -

 42 Figure 4.2 -General DSP System Structure

Figure 4 . 3 -

 43 Figure 4.3 -Xilinx Spartan 3 Simplified FPGA CLB Fabric

Figure 4 . 4 -

 44 Figure 4.4 -Altera Stratix V Variable Precision DSP Block in Standard Precision Mode[START_REF] Altera | Enabling High-Performance DSP Applications with Arria V or Cyclone V Variable-Precision DSP Blocks[END_REF]

76

 76

4. 2 .

 2 Embedded Systems for Digital Signal Processing (DSP) Applications-Two 18 × 18 independent multipliers in sum mode.

Figure 4

 4

Figure 4 . 6 -

 46 Figure 4.6 -ARM Cortex A9 Architecture[START_REF] Meyer-Baese | Digital Signal Processing with Field Programmable Gate Arrays (Signals and Communication Technology)[END_REF]

3 )

 3 Through successive decomposition for (4.2), i.e. divide and conquer, it is shown in[START_REF] Meyer-Baese | Digital Signal Processing with Field Programmable Gate Arrays (Signals and Communication Technology)[END_REF], that the FFT technique reduces the DFT complexity from O(N 2 c ) to O(N c log(N c )). A widely used and yet simple example is the FFT radix-2 DIF algorithm for a length N c = 8 samples.

Figure 4 . 7 -

 47 Figure 4.7 -FFT Radix-2 DIF For an Input Sequence of Length N = 8 [25]

Figure 4 . 8 -

 48 Figure 4.8 -FFT Radix-2 Butterfly Processor

Figure 4 . 9 - 5 th

 495 Figure 4.9 -5 th Order Polynomial Hardware Architecture

Figure 4 .

 4 10 using finite precision Q2.15 format.

Figure 4 .

 4 Figure 4.10 -Delay Relaxed Look Ahead LMS Hardware Architecture

13 ) y 2

 132 (k) = w H 5..8 (k)x 5..8 (k) (4.14) From Figure 4.10, a 8 input adaptive beamformer is formed by two 4 input linear combiner blocks and two 4 input weight update blocks. The system default external inputs are the input and desired signals x(k) and d(k), respectively. The resulting stage outputs, y 1 and y 2 , of each linear combiner are then combined to form the final output y and the total error e DLM S . The resulting error and the external input signals x 1..4 (k) and x 5..8 (k) are then used to update the previous filter coefficients.

Figure 4 . 11 -

 411 Figure 4.11 -Delay Relaxed Look Ahead LMS 4-Input Linear Combiner Architecture

Figure 4 .

 4 Figure 4.11 shows that the multiplication and addition stages requires only one clock cycle, each, for all parallel inputs. Each complex multiplier is formed of four real multipliers

Figure 4 .

 4 Figure 4.12 -Delay Relaxed Look Ahead LMS 4-Input Weight Update Architecture

of 30 •

 30 , first interference at 45 • and second interference at 80 • , the resulting beam radiation pattern is shown in Figure4.13.

Figure 4 . 13 -

 413 Figure 4.13 -Infinite and Finite Precision DLMS Beam Radiation Pattern

Figure 5 .

 5 Figure 5.1 -pLMS Architecture

Figure 5 .

 5 Figure 5.2 -8-Elements DpLMS Hardware Architecture[START_REF] Akkad | Two Stages Parallel LMS Structure A Pipelined Hardware Architecture[END_REF]

3

 3

  and 5.4, respectively.

Figure 5 . 3 - 4 -

 534 Figure 5.3 -4-Input Linear Combiner Block

Figure 5 . 5 -

 55 Figure 5.5 -pLMS MSE Convergence Behavior

Figure 5 . 6 -

 56 Figure 5.6 -pLMS and pLMS-FD MSE Convergence Behavior For Fractional Delay Filter

Figure 5 . 7 -

 57 Figure 5.7 -LLMS and pLMS MSE Convergence Behavior for Recurring Samples

Figure 5 . 9 -

 59 Figure 5.9 -DpLMS MSE Convergence Behavior for Different SNR Environments

Figure 5 .

 5 Figure 5.10 -DpLMS Finite and Infinite Precision Beam Radiation Pattern

  and 5.12, respectively.

Figure 5 .

 5 Figure 5.11 -pLMS Beam Pattern for Different SNR

Figure 5 .

 5 Figure 5.12 -Finite Precision DpLMS Beam Pattern for Different SNR

7 ) 123 Partie , Chapter 6 -

 71236 The Reduced Complexity Parallel LMS and its Pipeline Hardware Implementation

  15 1 format. The delay relaxation is initialized such as D 1 = 4, D 2 = 2 and D 3 = 1, i.e. six pipeline stages. The DRC-pLMS architecture is shown in Figure 6.2, where u 1..4 (k), u 5..8 (k), w 1..4 (k) and w 5..8 (k) are the DRC-pLMS input and weight vectors formed by the first and last 4 elements, respectively. z -1 , z -D 1 and z -D 1 -1 represent a digital delay element, i.e. register, of 1, D 1 , and D 1 -1 samples, respectively and the Conj block denotes the complex conjugation [4].

Figure 6 . 2 - 8 -

 628 Figure 6.2 -8-Input DRC-pLMS Beamformer Architecture [4]

Figure 6 . 3 -

 63 Figure 6.3 -DRC-pLMS 4-Input Linear Combiner Architecture [4]

Partie , Chapter 6 -

 6 The Reduced Complexity Parallel LMS and its Pipeline Hardware Implementation additional multiplier[4].

Figure 6 . 4 -

 64 Figure 6.4 -DRC-pLMS 4-Input Weight Update Architecture

Figure 6 . 5 -

 65 Figure 6.5 -RC-pLMS MSE Convergence Comparison [4]

Figure 6 . 6 -

 66 Figure 6.6 -RC-pLMS Convergence Behavior [4]

Partie , Chapter 6 -

 6 The Reduced Complexity Parallel LMS and its Pipeline Hardware Implementation however with a larger residual error[4].

Figure 6 . 7 -

 67 Figure 6.7 -DRC-pLMS Convergence Behavior [4]

Figure 6 . 8 -

 68 Figure 6.8 -Infinite and Finite Precision Beam Radiation Pattern for an Angle of Arrival 30 • [4]

Figure 6 .

 6 Figure 6.10 -DRC-pLMS Beam Radiation Pattern for an Angle of Arrival 30 • [4]

Figure 6 .

 6 Figure 6.11 -RC-pLMS Pole Zero Map for Different µ

6 . 50 )

 650 by setting w(k) = w 1 (k) = w 2 (k). As such, we obtain:ξ RC-pLM S (k) = E[|d(k)| 2 ]p H w(k)w H (k)p + w H (k)Rw(k) + E[|d(k -1)| 2 ] -E[d(k)x H (k -1)]w(k -1)w H (k -1)E[d * (k)x(k -1)] + jE[d * (k)d(k -1)] +w H (k -1)E[x(k)x(k -1)]w(k -1) + jE[d(k)d * (k -1)] -jw H (k)E[d * (k -1)x(k)] + jw H (k)E[x(k)x H (k -1)]w(k -1) +jE[d(k)x H (k -1)]w 1 (k) + jw H (k -1)E[d(k)x(k -1)] +jE[x H (k)w(k)w H (k -1)x(k -1)] -jE[d(k)x H (k -1)]w(k -1) (6.51)

  • and corrupted by two interfering signals incoming at 45 • and 80 • , respectively.

Figure 6 .

 6 Figure 6.13 -RC-pLMS Beam Radiation Pattern for a Simple 2-PSK Message Signal and Different SNR

Figure 6 .

 6 Figure 6.14 -RC-pLMS Beam MSE Localization With Respect to the Angle of Arrival

E[Y 1

 1 (z)] = µ 1 N E[J pLM S (z)]R(z) (6.64) E[Y 2 (z)] = µ 2 N E[J 2 (z)]R(z) (6.65)whereE[J 2 (z)] = E[e 2 (0)] + E[e 2 (1)]z -1 + E[e 2 (2)]z -2 + ...(6.66)

  [START_REF] Akkad | Constant Time Hardware Architecture for a Gaussian Smoothing Filter[END_REF], we get:E[D(z)] -jz -1 E[D(z)] = E[J pLM S (z)] + µ 1 N E[J pLM S (z)]R(z) -jz -1 µ 2 N E[J 2 (z)]R(z) (6.67)Using (6.67), and the LMS transfer function approximation given as: function approximate becomes:H pLM S (z) = 1 + µ 2 N R(z) -jz -1 (1 + µ 1 N R(z))(1 + µ 2 N R(z))(6.70)

Figure 6 .

 6 Figure 6.16 -pLMS MSE Convergence Behavior MSE vs Time Plot

TABLE OF CONTENTS LIST OF FIGURES 1

 OF .1 Classical Adaptive Filter . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Simple Antenna Array . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3 Adaptive Beamforming System . . . . . . . . . . . . . . . . . . . . . . . . 2.1 Antenna Array Radiation Pattern (Cartesian Plot) . . . . . . . . . . . . . 2.2 Uniform Linear Antenna Array Structure . . . . . . . . . . . . . . . . . . . 2.3 Beam Radiation Pattern Vs Number of Antenna Elements with an Angle of Arrival of 0 • and an Inter Element Spacing of D a = λ Simulation Initial Parameters . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 Theoretical Complexity and Resource Usage . . . . . . . . . . . . . . . . . .3 Theoretical Complexity and Resource Usage [14] . . . . . . . . . . . . . . . 6.1 8-Input RC-pLMS Beamformer Synthesis Results . . . . . . . . . . . . . . 6.2 Simulation Initial Parameters . . . . . . . . . . . . . . . . . . . . . . . . . 6.3 Theoretical Complexity and Resource Usage [4] . . . . . . . . . . . . . . . 142 NOMENCLATURE

	LIST OF TABLES DRC-pLMS Delayed Reduced Complexity Parallel Least Mean Square LMS Least Mean Square SGD Stochastic Gradient Descent List of Variables H b Communication Channel Transfer Function w oplms LMS Adaptive Beamformers Optimal Weight Vector φ Antenna Arrays Azimuth Angle of Arrival c g (k) Chebyshev Polynomial General Expanded Form Coefficients e RLS (k) RLS Instantaneous Error Signal r ki Fractional Delay Filters Input Signal Auto-Correlation Estimate y(k) Adaptive Filters Output Signal Chapter 1
	EF-LSL LS SLL (AF (θ)) n Error-Feedback LSL Least Squares Side Lobe Level Array Factor Normalized at Unity I Identity Matrix w opr RC-pLMS Adaptive Beamformers Optimal Weight Vector ψ Phase Shift c m Erroneous Steering Vector e t (k) Multi-Stage Adaptive Filters Total Instantaneous Error Signal RD Antenna Radiation Directivity y 1 (k) First N 2 Elements Adaptive Filters Output Signal
	ESPRIT LUT SNR α i l w op Ψ(ε) d(k) f c S(k) y 2 (k)	Estimation of Signal Parameter Via Rotational Invariance Techniques Look Up Table Signal to Noise Ratio RLS Forgetting Factor l th Interference Signal pLMS Adaptive Beamformers Optimal Weight Vector Set of Erroneous Steering Vectors With Respect to ε Desired Signal Instantaneous Sample Carriers Signals Frequency RC-pLMS Total Desired Signal Second N 2 Elements Adaptive Filters Output Signal
	EVD SoC L(k) ψ x g y d (k)	MAC η Sy w q D(z) s(k)	Eigenvalue Decomposition Multiply Accumulate System on Chip Multi-Stage Overall Desired and Output Signals Quantization Error RLS Gain Matrix RC-pLMS Weight Vector Subject to Quantization Error Phase Shift for Elements Placed in the x Plane z Transform Sequence of the Desired Signal d(k) Antenna Directivity Gain Message Signal Adaptive Filters Message Signal Subject to Fractional Delay
	3.1 List of Abbreviations Finite Alphabet ML Maximum Likelihood SOCP FA Second Order Cone Programming η S Multi-Stage Overall Desired Signals Quantization Error m(k) Mean Coefficient Error Vector in a Rotated Coordinate System x(k) Adaptive Filters Input Signal Vector ψ y Phase Shift for Elements Placed in the y Plane D 1 Delay in the Adaptive Filters Instantaneous Error Signal H(z) LMS z Transfer Function S q (k) RC-pLMS Total Desired Signal Subject to Quantization Error y i,j (k) Adaptive Filters j th Interference Signal Subject to Fractional Delay
	AD MMSE η u x 1..4 (k) D 2 H pLM S (z) FIR SPI n(k) σ 2 a S RLM Sp (k) Finite Input Response Analog to Digital Minimum Mean Square Error Serial Peripheral Interface Multi-Stage Overall Input Signals Quantization Error Complex Additive White Gaussian Noise Vector Signal First Four Samples of the Adaptive Filters Input Signal Vector Variance of the Constant a Delay in the Adaptive Filters Weight Update pLMS z Transfer Function RLMSp Total Desired Signal y LM S1 (k) First LMS Stage Output Signal
	AOA MRVSS UART FM η w O x 1 (k) σ 2 d D 3 H RC-pLM S (z) RC-pLMS z Transfer Function Angle of Arrival Fourrier Method Modified Robust Variable Step Size Universal Asynchronous Reciever-Transmitter Adaptive Filter Weight Signals Quantization Error Unitary Matrix of Eigenvectors Rows First Stage Adaptive Filters Input Signal Vector Desired Signals Variance Sum Relaxation Delay in the Adaptive Filters Weight Update S RLM S (k) RLMS Total Desired Signal y LM S2 (k) Second LMS Stage Output Signal
	AP FNBW MSE USB η y p(τ ) x 2 (k) σ 2 p D ax j T k (u c ) y q (k)	Array Processing First Null Beam width Mean Square Error Universal Serial Bus Multi-Stage Output Signals Quantization Error Adaptive Filters Input and Desired Signals Cross Correlation Vector Second Stage Adaptive Filters Input Signal Vector In Phase Message Signals Variance Distance Between Two Consecutive Array Elements in the x Plane Imaginary Complex Number Chebyshev Polynomial Representation With Respect to u c RC-pLMS Output Signal Subject to Quantization Error
	ARM FPGA MSINR VSSLMS âd,m p t x 5..8 (k) σ 2 q D ay J(z) U y RLS1 (k)	Advanced RISC Machines Field Programmable Gate Array Maximum Signal to Interference Plus Noise Ratio Variable Step Size Least Mean Square m th Element of the Desired Signals Steering Vector Estimate FFT Rotation, Twiddle, Factor Exponent Input Vector Last Four Samples of the Adaptive Filters Input Signal Vector Out Of Phase Message Signals Variance Distance Between Two Consecutive Array Elements in the y Plane z Transform Sequence of the Instantaneous Error Signal e(k) Antenna Radiation Sensitivity (Practical) First RLS Stage Output Signal
	FPU WSS Q(τ ) τ N	BRAM MUSIC λ X b D a U 0	Block Random Access Memory Floating Point Unit Multiple Signal Classification Wide Sense Stationary Carrier Signals Wavelength RLS Input Signals Auto-Correlation Matrix Input Signals Matrix Signal Lag in a Wide Sense Stationary Process Distance Between Two Consecutive Array Elements Number of Antenna Elements Antenna Radiation Sensitivity (Theoretical)
	CAN MVDR λ A,max Q r (τ ) GPP x d τ d e(k) N c u c	Controller Area Network General Purpose Processor Minimum Variance Distortionless Response Maximum Eigenvalue in Matrix A RC-pLMS Input Signals Cross-Correlation Matrix Discrete Time FFT Input Signal Vector Time Delay Between Two Consecutive Antenna Elements Adaptive Filters Instantaneous Error Signal FFT Sequence Length Chebyshev Polynomials Change of Variable
	CAWGN GS-FAP NLMS λ i R(τ ) x f θ e 1 (k) N x U max	Complex Additive White Gaussian Noise Gauss-Seidel Fast Affine Projection Normalised Least Mean Square i th Eigenvalues Adaptive Filters Input Signals Auto-Correlation Matrix Adaptive Filters Input Signal Vector Subject to Fractional Delay Antenna Arrays Elevation Angle of Arrival First Stage Adaptive Filters Instantaneous Error Signal Number of Antenna Elements in the x Plane Maximum Antenna Radiation Sensitivity
	CLB PDSP λ R,max R i+n (τ ) HLL z(τ ) ε e 2 (k) N y v 1	Configurable Logic Block High Level Language Programmable Digital Signal Processing Processor Maximum Eigenvalue in Matrix R Interference Plus Noise Correlation Matrix RLS Input and Desired Signals Cross Correlation Vector Maximum Mismatch Error Second Stage Adaptive Filters Instantaneous Error Signal Number of Antenna Elements in the y Plane Random Gaussian Real Sequence
	HLS S b Λ nu	CM PLL v(k) z r (τ ) e DLM S (k) High Level Synthesis Constant Modulus Phased Locked Loop Mean Coefficient Error Vector Unknown Data Signal RC-pLMS Input and Desired Signals Cross Correlation Vector at Different Diagonal Matrix of Eigenvalues λ i Delay LMS Instantaneous Error Signal Step Size Exponent v 2 Random Gaussian Real Sequence
	CORDIC HoCA Higher Order Cumulant Coordinate Rotation Digital Computer pLMS Parallel Least Mean Square w(k) Adaptive Filters Mean Weight Vector u(k) RC-pLMS Total Input Vector τ ϑ Very Small User Introduced Constant e i (k) i th Stage Adaptive Filters Instantaneous Error Signal P Power Radiated by the Antenna v m Random Complex Gaussian Sequence
	DAC HPBW QoS âd u q (k) µ ξ LM S e LLM S (k) Half Power Beam width Digital to Analog Converter Quality of Service Desired Signals Steering Vector Estimate RC-pLMS Total Input Vector Subject to Quantization Error RC-pLMS Optimization Step Size LMS Cost Function LLMS Instantaneous Error Signal P c Projection to the x -y Plane w 1,m m th Element, First Stage, Instantaneous Weight
	DFT RAM R i+n (τ ) µ 1 ξ pLM S I2C w(k) e LM S (k) p t W kn Nc 2	Discrete Fourier Transform Inter-Integrated Circuit Random Access Memory Interference Plus Noise Correlation Matrix Estimate Adaptive Filters Weight Vector First LMS Stage Optimization Step Size LMS Cost Function LMS Instantaneous Error Signal FFT Rotation, Twiddle, Factor Exponent kn th Rotation, Twiddle, Factor for an FFT Sequence of Length Nc 2
	DIF RC-pLMS Intermediate Frequency Decimation in Frequency Reduced Complexity Parallel Least Mean Square A Multi Stage Adaptive Algorithm Overall Input Auto-Correlation Matrix w 1..4 (k) IF Adaptive Filters Weight Vector With Respect to First Four Input Samples µ 2 Second LMS Stage Optimization Step Size ξ RC-pLM S RC-pLMS Cost Function e m Mismatch Error in the Desired Signals Steering Vector q Taylor Series Polynomial Expansion Point W k Nc k th Rotation, Twiddle, Factor for an FFT Sequence of Length N c
	DILFAST Infinite Input Response Decoupled Iterative Least Squares Finite Alphabet Space-Time RF Radio Frequency a d Desired Signals Steering Vector w 1 (k) IIR First Stage Adaptive Filters Weight Vector µ LM S LMS Optimization Step Size ξ RLS RLS Cost Function e pLM S (k) pLMS Instantaneous Error Signal r Base Radix -r Number Representation X[k] FFT Sequence
	DIT RISC a i,l w 2 (k) IOB µ pLM S AF (θ) e q (k) R(z) x 1,m	Decimation in Time Input/Output Block Reduced Instruction Set Computer l th Interference Signals Steering Vector Second Stage Adaptive Filters Weight Vector pLMS Optimization Step Size Array Factor With Respect to Angle of Arrival θ Adaptive Filters Instantaneous Error Signal Subject to QuantizationError z Transform Sequence of the Input Signals Auto-Correlation Matrix R(τ ) m th Element, First Stage, Instantaneous Input Signal
	DMA IP-core RLMS A i w 5..8 (k) ∇ LM S BW 3dB e RC-pLM S (k) RC-pLMS Instantaneous Error Signal Direct Memory Access Intellectual Property Recursive Least Mean Square Matrix of Steering Vectors Adaptive Filters Weight Vector With Respect to Last Four Input Samples LMS Cost Functions Gradient 3 dB Beamwidth R c Circular Antenna Arrays Radius x 2,m m th Element, Second Stage, Instantaneous Input Signal
	DOA RLS c i w i (k) LC ∇ pLM S c e RLM Sp (k) Linear Combiner Direction of Arrival Recursive Least Squares Beamformer Constraint Vector i th Stage Adaptive Filters Weight Vector pLMS Cost Functions Gradient Celerity of Electromagnetic Waves RLMSp Instantaneous Error Signal r k-i Fractional Delay Filters Input Signal Auto-Correlation Estimate Time Av-x c (t) Analog Input Signal
	DoF LLMS RTL d w M V DR ∇ RC-pLM S Least Mean Square -Least Mean Square Degrees of Freedom Register Transfer Level Desired Signal Vector MVDR Adaptive Beamformers Optimal Weight Vector RC-pLMS Cost Functions Gradient C(k) Chebyshev Polynomial Coefficients e RLM S (k) RLMS Instantaneous Error Signal erage x d [k] Discrete Time Input Signals Sample

4.1 Implementation Comparison for DSP Applications [62] . . . . . . . . . . . 4.2 5 th order Chebyshev Polynomial Coefficients For sine and cosine Approximations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.3 Twiddle Factor Direct Computation . . . . . . . . . . . . . . . . . . . . . . 4.4 Twiddle Factor Computation Using 5 th Order Taylor Approximation . . . . 4.5 Twiddle Factor Computation Using 5 th Order Chebyshev Approximation . 4.6 Taylor and Chebyshev Infinite Precision Approximation MSE . . . . . . . 4.7 ZynQ and Cyclone IV Resource Comparison . . . . . . . . . . . . . . . . . 4.8 FFT Radix-2 DIF ZynQ Implementation and Synthesis Results . . . . . . 4.9 FFT Radix-2 DIF Cyclone IV Implementation and Synthesis Results . . . 4.10 ZynQ FFT Radix-2 DIF Implementation Using HLS (Without For Loop) . 4.11 ZynQ FFT Radix-2 DIF Implementation Using HLS (With For Loop) . . . 4.12 5 th Order Polynomial SoC Implementation . . . . . . . . . . . . . . . . . . 4.13 5 th Order Taylor Approximation In Q3.14 Finite Precision Format . . . . 4.14 5 th Order Chebyshev Approximation In Q2.15 Finite Precision Format . . 4.15 Taylor and Chebyshev Finite Precision Approximation MSE . . . . . . . . 4.16 8-Input Delay Relaxed Look Ahead LMS Synthesis Results . . . . . . . . . 5.1 DpLMS Beamformer Synthesis Results . . . . . . . . . . . . . . . . . . . . 5.2 Simulation Initial Parameters . . . . . . . . . . . . . . . . . . . . . . . . . 5

Table 3 .

 3

1 -Simulation Initial Parameters

Table 4 .

 4

		Performance Flexibility Power	Cost	Design Effort
	PDSP	Medium	Medium Medium Medium	Medium
	FPGA	Medium	High	High	Medium	Medium
	SoC	High	High	Medium Medium	High
	GPP	Low	High	Medium	Low	Low

1 -Implementation Comparison for DSP Applications

[START_REF] Tessier | Reconfigurable Computing for Digital Signal Processing: A Survey[END_REF]

Table 4 . 2

 42

	5)

-5 th order Chebyshev Polynomial Coefficients For sine and cosine Approximations

  .3.

	Partie , Chapter 4 -Overview of Digital Signal Processing Implementation Techniques on
	Embedded Systems
	f (p t )	p t (0)	Twiddle Factor Direct Computation p t (1) p t (2) p t (3) p t (4) p t (5)
	sin	0	-0.3827 -0.5000 -0.7071	-1	0
	cos	1	0.9239 0.8660 0.7071	0	-1
	Table 4.3 -Twiddle Factor Direct Computation

Table 4 .

 4 .5, respectively.

	f (p t )	Twiddle Factor Computation Using Taylor Approximation p t (0) p t (1) p t (2) p t (3) p t (4) p t (5)
	sin	0	-0.3827 -0.5000 -0.7071 -1.0045	-0.5240
	cos	1	0.9239 0.8661 0.7074 0.2000	0.1239

4 -Twiddle Factor Computation Using 5 th Order Taylor Approximation

From Table

Table 4 .

 4 5 -Twiddle Factor Computation Using 5 th Order Chebyshev ApproximationIn contrast to the Taylor approximation in Table4.4, the Chebyshev approximation, presented in Table4.5, guarantees a 3 decimal digit accuracy for all input values p. To further validate the Chebyshev approximations performance, the MSE is computed with reference to the result of Table4.3 and is presented in Table4.6.

	5)

Table 4 .

 4

6 -Taylor and Chebyshev Infinite Precision Approximation MSE

Table 4 .

 4 7 -ZynQ and Cyclone IV Resource ComparisonAs shown in Table4.7, the "Cyclone IV" FPGA includes 532, 9 × 9 bits, ready to use,

			Logic Units	DSP	Multipliers Registers
	ZynQ	SoC	85000	220 18 × 25 bits	From DSP	106400
	Cyclone IV FPGA	114480	-	532 9 × 9 bits	NA

Table 4 .

 4

			ZynQ Synthesis Results
		DSP Registers Logic Units Clock (MHz)
	Parallel	20	3504	1680	196.539
	Sequential	16	1264	560	198.087

8 -FFT Radix-2 DIF ZynQ Implementation and Synthesis Results

  .7.

	Architecture	Cyclone IV Synthesis Results Multipliers Registers Logic Units Clock (MHz)
	Parallel	40	1296	2113	251.760
	Sequential	32	432	705	286.53
	Table 4.9 -FFT Radix-2 DIF Cyclone IV Implementation and Synthesis Results

Table 4 .

 4 .10. 10 -ZynQ FFT Radix-2 DIF Implementation Using HLS (Without For Loop)

	Directives	FFT HLS Synthesis Results on ZynQ (Without For) DSP Registers Logic Units Latency Input Delay
	NA	16	1407	578	32	33
	Pipeline	12	1283	453	18	4

Table 4 .

 4 .11.

	Directives	FFT HLS Synthesis Results on ZynQ (With For) DSP Registers Logic Units Latency Input Delay
	NA	4	382	541	45	46
	Pipeline FFT	12	1283	453	18	4
	Pipeline For	4	404	471	23	24
	Unroll For	16	1407	578	23	33
	Unroll FFT	4	382	541	45	46

11 -ZynQ FFT Radix-2 DIF Implementation Using HLS (With For Loop)

Table 4 .

 4 12 -5 th Order Polynomial SoC Implementation

			Approximation Parallel Pipeline Architecture
		DSP Registers Logic Units	Frequency (MHz)
	ZynQ	2.72%	246	0.076%	174.917
	Cyclone V 6.89%	138	0.143%	174.64

Table 4 .

 4 .13 and 4.14, respectively. 13 -5 th Order Taylor Approximation In Q3.[START_REF] Akkad | A Multi-Stage Parallel LMS Structure and its Stability Analysis Using Transfer Function Approximation[END_REF] Finite Precision FormatIn contrast to the Taylor approximation in Table4.13, the Chebyshev approximation, presented in Table4.14, guarantees a 3 decimal digit accuracy for all input values p.

	f (p t )	p t (0)	Finite Precision Taylor Approximation p t (1) p t (2) p t (3) p t (4)	p t (5)
	sin	0	-0.3826 -0.5000 -0.7048 -0.9447 -0.5240
	cos	1	0.9238 0.8661 0.7073 0.0198 0.1218

Table 4 .

 4 14 -5 th Order Chebyshev Approximation In Q2.15 Finite Precision Format To further validate the Chebyshev approximation performance, the finite precision approximation MSE is computed with reference to the infinite precision result of Table 4.3 and is presented in Table 4.15.

	f	Taylor and Chebyshev Finite Precision Approximation MSE Taylor MSE Chebyshev MSE
	sin	0.0463	4.4817 × 10 -6
	cos	0.2098	2.1 × 10 -7

Table 4 .

 4

15 -Taylor and Chebyshev Finite Precision Approximation MSE

As shown in Table

Table 4 .

 4 [START_REF] Srar | LLMS Adaptive Beamforming Algorithm Implemented With Finite Precision[END_REF] for the Intel "Stratix V 5SGXMABN3F45I4" model.

	Design DSP Registers Logic Units Frequency(MHz)
	DLMS 32	1746	773	208.33

Table 4 .

 4 16 -8-Input Delay Relaxed Look Ahead LMS Synthesis Results

Table 5 . 3

 53

-Theoretical Complexity and Resource Usage

[START_REF] Akkad | A Multi-Stage Parallel LMS Structure and its Stability Analysis Using Transfer Function Approximation[END_REF]

Table 6 .

 6 Partie , Chapter 6 -The Reduced Complexity Parallel LMS and its Pipeline Hardware Implementation 3 -Theoretical Complexity and Resource Usage[4]

	Algorithm	cMultiply	cAdd	cDivide
	RLMS[15]	3N 2 + 11N + 2 2N 2 + 9N + 6 N + 1
	RLMSp[6]	3N 2 + 7N + 1	2N 2 + 6N + 3 1
	RLS	3N 2 + 5N	2N 2 + 4N + 2 1
	LLMS[5]	6N + 2	5N + 4	N
	pLMS	4N + 2	4N + 4	0
	RC-pLMS [4] 2N + 1	3N + 2	0
	LMS	2N + 1	2N + 1	0

  1,m (k)] E[w 1,m ]E[x 1,m (k)] (6.43)therefore, from equations (6.42) and (6.43), we can estimate the array steering vector in expectation and instantaneous form as:âd,m (k) E[x 1,m (k)] E[w 1,m ]y RLS (k) + ϑ x 1,m (k) w 1,m (k)y RLS (k) + ϑ (6.44)and the third term of (6.45) becomes:E[e * 1 (k)e 2 (k -1)] = E[-d * (k)w H 2 (k -1)x(k -1) -d(k -1)x H (k)w 1 (k) +d * (k)d(k -1) + x H (k)w 1 (k)w H 2 (k -1)x(k -1)] (6.49)substituting (6.46), (6.47), (6.48) and (6.49), in (6.45) the MSE ξ pLM S becomes:ξ pLM S (k) = E[|d(k)| 2 ]p H w 1 (k)w H 1 (k)p + w H 1 (k)Rw 1 (k) + E[|d(k -1)| 2 ] -E[d(k)x H (k -1)]w 2 (k -1)w H 2 (k -1)E[d

* (k)x(k -1)] + jE[d * (k)d(k -1)] +w H 2 (k -1)E[x(k)x(k -1)]w 2 (k -1) + jE[d(k)d * (k -1)] -jw H 1 (k)E[d * (k -1)x(k)] + jw H 1

1.2. Our Research Project

One signed bit, two integer bits and fifteen precision bits

One sign bit, two integer bits and fifteen decimal bits

One sign bit, three integer bits and fourteen decimal bits

1 signed bit, 2 integer bits and 15 precision bits

to light. I would like to also thank my thesis co-supervisor Professor Bachar ELHASSAN for the similar and for his continuous encouragment.

Second, I would like to thank the jury committee president Professor Christian JUT-It is an honor to have my work examined and assessed by professional experts such as yourselves.

Third, I am grateful to AID -DGA (l'Agence de l'Innovation de Defense -Direction Générale de l'Armement -Ministére des Armées) & ANR (Agence Nationale de la Recherche en France) for supporting our ANR-ASTRID -Project (ANR-19-ASTR-0005-03).

Moreover, I would like to heartily thank my mentors, colleagues and best friends at the University of Balamand (UOB) doubt, definite that the FOE will thrive under your guidance and supervision.

Additionally, I would like to thank the previous Vice President and previous Dean of the UOB Faculty of Engineering Professor Michel NAJJAR for his limitless support.

Using the equality w oplms = R -1 p in (5.11), we assume w op ≈ w oplms . Thus, (5.11) becomes:

(5.12)

Where, A is the final correlation matrix formed as a linear combination of the autocorrelation and cross-correlation matrices at lag 0 and 1, respectively; A is assumed invertible as a result of the random input noise [2] and is defined as:

(5.13) Thus, from (5.11), we can proceed as follows:

w(k + 1)w op = w(k)w op + µ 1 p + jµ 1 R(1)w op -µ 1 Rw(k) -µ 1 Rw op +µ 1 Rw op + jµ 1 p(-1) -jµ 1 R(1)w op + µ 1 R(1)w(k) (5.14) Using the mean coefficient error vector notation and (6.17), we can write:

v(k + 1) = (I -µ 1 R -jµR(1))v(k) + µ 1 p -µ 1 (R + jR(1))A -1 p +jµ 1 p(-1) -µ 1 (jR -R(1))A -1 p(-1) (5.15) The above equation can be simplified as follows:

Using the eigenvalue decomposition (EVD), where Λ is a diagonal matrix with diagonal entries (λ i ) equal to the eigenvalues of A, and O is a unitary matrix whose rows represent the eigenvectors of A. We can now write A = O -1 ΛO [2]. We can rewrite (6.20) as:

Multiplying both sides of (6.21) by O, we get:

Let m(k) = Ov(k), where m(k) is v(k) in a rotated coordinate, defined by the eigenvectors in O, thus a convergence in m(k) means a convergence in v(k) [2], then:

Since (I-µ 1 Λ) is a diagonal matrix, the stability and convergence is achieved with respect to the convergence of different first order difference equations formed by all N eigenvalues

. Thus, we define a set of N difference equations as follows:

The convergence of the set of

Thus for the convergence in the mean sense, we require:

where the norm, |λ A,max |, is the maximum eigenvalue in A and |.| is the complex modulus, i.e. Re{λ} 2 + Im{λ} 2 . Thus, to ensure the convergence and the stability for LM S 1 the step size µ 1 must satisfy (6.25).

As the pLMS total error is formed with respect to LM S 2 , the stability and convergence of LM S 2 is crucial. Since LM S 2 is the classical LMS algorithm with no additional modifications, the upper bound of the step size, µ 2 , is given with respect to [2] as (5.22) where λ R,max is the maximum eigenvalue in R. Thus, to ensure the convergence and the stability for LM S 2 the step size µ 2 must satisfy (5.22).

Transfer Function Approximation

A simple approximation to the behavior of the LMS adaptive algorithm, for temporal sampled signals, has been developed in [START_REF] Clarkson | Simplified Analysis Of The LMS Adaptive Filter Using A Transfer Function Approximation[END_REF]. The proposed approximation, models the system in terms of a discrete linear transfer function applicable for both deterministic and random inputs and is given by (5.23), such as:

µ LM S is the LMS step size, L is the filter length, J(z), D(z) and R(z), are the z transform polynomial whose coefficients are the instantaneous error signal e(k), desired signal d(k) and the input signals, x(k), auto-correlation estimates respectively [START_REF] Clarkson | Simplified Analysis Of The LMS Adaptive Filter Using A Transfer Function Approximation[END_REF][START_REF] Han | Quality of Approximation in Error Transfer Function Analysis of the LMS Adaptive Filters[END_REF]. As such, In order to numerically assess the stability and performance of the proposed system, this section presents a discrete time transfer function approximation of the pLMS. Moreover, the input system described by the N equally spaced, identical antenna elements is modeled as a N th order fractional delay filter employing a Farrow structure and a Lagrange interpolation [START_REF] Laakso | Splitting the Unit Delay FIR all Pass Filters Design[END_REF]. Hence, the new pLMS input signal x f (k) can now be defined as:

where y d (k), y i,j (k) are the message and interfering signals subject to a fractional delay filter and n(k) is a complex additive white Gaussian noise (CAWGN). The pLMS transfer function approximation can now be derived from (5.1) such that:

Assuming a WSS process and through the application of the Z transform for both sides of (5.25), the pLMS transfer function approximate H pLM S (z), as derived in Appendix D, becomes:

inferred multiplier is a complex multiplier and is formed of four real multipliers and one complex adders, i.e. two real adders.

Implementation and Synthesis Results

Synthesis and implementation results for the delayed LMS (DLMS), pLMS and DpLMS are obtained for the Intel "Stratix V 5SGXMABN3F45I4" model are presented in Table stability analysis is studied for different µ values and the pole zero plot is shown in Figure 5.13 [START_REF] Akkad | A Multi-Stage Parallel LMS Structure and its Stability Analysis Using Transfer Function Approximation[END_REF]. As the step size µ pLM S increases the resulting poles and zeros move further towards the outside of the unit circle. Thus, it can be concluded from the conducted study that the maximum step size to ensure convergence and stability falls in the range of 0.03 < µ pLM S < 0.04 [START_REF] Akkad | A Multi-Stage Parallel LMS Structure and its Stability Analysis Using Transfer Function Approximation[END_REF].

Computational Complexity Comparison

A resource complexity comparison for the pLMS against different adaptive algorithms recalled during this study is presented in Table 5.3 [START_REF] Akkad | A Multi-Stage Parallel LMS Structure and its Stability Analysis Using Transfer Function Approximation[END_REF]. It is clear that the RLS adaptive algorithm and its variants require an undesirable complexity of order O(N 2 ) [6,[START_REF] Akkad | A Multi-Stage Parallel LMS Structure and its Stability Analysis Using Transfer Function Approximation[END_REF]. Furthermore, the RLMS, the LLMS and the RLMSp require N + 1, N and 1 complex divisions, respectively [START_REF] Akkad | A Multi-Stage Parallel LMS Structure and its Stability Analysis Using Transfer Function Approximation[END_REF]. In contrast, the proposed pLMS structure presents superior convergence speed, low residual error and a parallel easy to pipeline architecture while Chapter 6

THE REDUCED COMPLEXITY PARALLEL LMS AND ITS PIPELINED HARDWARE IMPLEMENTATION

Introduction

While the parallel LMS (pLMS) presented a parallel, easy to pipeline structure with accelerated convergence and low residual error, it still requires to instantiate two least mean square (LMS) stages, thus doubling the complexity of that of the classical LMS [4,[START_REF] Akkad | A Multi-Stage Parallel LMS Structure and its Stability Analysis Using Transfer Function Approximation[END_REF]. In this chapter, we propose a reduced complexity pLMS structure for adaptive beamforming (RC-pLMS), its transfer function approximation and its pipeline hardware implementation [4].

Hardware and Software Simulations

A Monte Carlo type simulation is conducted to assess the behavior of the RC-pLMS, the RC-pLMS transfer function subject to fractional delay (RC-pLMS-FD) and the DRC-pLMS with respect to the LLMS, pLMS and RLS adaptive algorithms.

Algorithm

.2 -Simulation Initial Parameters

The simulation is performed for 500 realizations of 500 samples each where the input

APPENDIX A

Steering Vector Estimate

The output of the individual taps of the beamformer are given by:

When the first stage, RLS, adaptive algorithm converges the output y RLS tends to approach the desired signal s d (k) by suppressing the interference and noise signals. Therefore, let the beamformer output be defined by:

At convergence and by applying the expectation operator to both sides of equation (2.5), we get:

Assuming that after convergence, we can approximate:

thus equation (6.40) can be rewritten as:

APPENDIX B pLMS Mean Square Error

The parallel LMS (pLMS) mean square error (MSE) ξ pLM S is defined as:

with |.| signifies the complex modulus. Moreover, the first term of (6.45) can be expressed as:

the last term of (6.45) can be developed as follow:

In addition, the second term of (6.45) can be detailed as:

APPENDIX C

RC-pLMS Performance Evaluation With Modulated

Signals

In non-blind, temporal based, adaptive beamforming algorithms, the system undergoes a training phase before transmission in order to receive the training signal, compute its weights and steer its beam pattern accordingly. During the training phase no data is transmitted from the user to the station, and the reference signal is simple and well known. As such, in this section, we evaluate the performance of the RC-pLMS with respect to a simple binary message signal with 2 Phase Shift Keying (PSK) modulation and an amplitude of 0.2. Additionally, we include two interfering signals modulated in 4-PSK and 8 Qadrature Amplitude Modulation (QAM), with an amplitude of 0.1, respectively. The MSE convergence behavior is shown in Figure 6.12.

APPENDIX D pLMS Transfer Function Approximation

The input system described by the N equally spaced, identical antenna elements is modeled as a N th order fractional delay filter employing a Farrow structure and Lagrange interpolation. The new pLMS input signal x f (k) can now be defined as:

where y d (k), y i,j (k) are the message and interfering signals subject to a fractional delay filter and n(k) is a complex additive white Gaussian noise (CAWGN). The pLMS transfer function approximation can now be derived such that:

APPENDIX E

Arithmetic Complexity

In order to better highlight the performance of each algorithm, in this section we present the MSE convergence behavior with respect to time. This simulation is run on a machine with an Intel Core i5-6500HQ processor, 8 gigabytes (GB) of memory, Windows 10, 64-bits operating system and Matlab version 2017. The MSE convergence plot is shown in Figures 6.15, 6.16 and 6.17