I. INTRODUCTION

The selective directional enhancement of a uniform plane wave based on its direction of propagation constitutes a beamforming operation. For ultrawideband plane waves contaminated by wide sense stationary additive white Gaussian noise (AWGN), the optimal beamformer takes the form of a true time delay-based delay-end-sum operation. For example, to directionally enhance a wideband wave arriving at angle ϕ measured from the broadside direction from an N -element linear aperture of antennas, the delay and sum operation for beamforming requires the computation of y(t) = N k=1 x k (tkτ ) where τ = ∆x c sin ϕ and where ∆x is the inter antenna distance and c is the speed of light. A single beam requires N delay elements; thus, N simultaneous beams at arbitrarily chosen angles would naturally lead to N parallel copies of the beamformer thus leading to O(N 2 ) delay elements in total. The N × N delay Vandemonde matrix (DVM) N -beam beamformer is a special case where each p = 1, 2, ..., N beam is realized by integer multiple delays of τ p = pτ /N 2 . The frequency responses (beam shapes) of the DVM for N = 16 beams are shown in Fig. 1. The DVM-form of the N -beam wideband beamformer will be reviewed in Section II.

The straightforward realization of N -beams using the DVM-vector operation leads to a parallel hardware realization that essentially uses N 2 delays. The circuit complexity associated with this multi-beam receiver/transmitter thus scales as O(N 2 ); such as "quadratic complexity" makes scaling to a large number of beams from a high valued N (dense aperture arrays) extremely challenging. To address this problem, our recent work led to a new class of DVM beamforming algorithms that factor the matrix-vector product into a sequence of sparse matrices-vector products so that the net number of delays is reduced to O(N log N ), where N = 2 r (r ≥ 2); this is the same log N N factor of reduction albeit for the number of delays just like for the well-known case of applying fast Fourier transforms (FFTs) in place of direct matrix-vector operations when one is computing a discrete Fourier transform (DFT). FFTs exhibit butterfly networks in their signal flow graph representations. We refer you to our recent work [1] for a treatment of the O(N log N ) wideband DVM beamformers.

II. MATHEMATICAL INTERPRETATION OF O(N )

APPROXIMATE DVM N -BEAM BEAMFORMER Here, we disclose our most recent innovation: a DVM wideband multi-beam beamforming algorithm that achieves Nwideband beams at linear complexity; that is, the proposed DVM beamformer requires only O(N ) delays to realize Nbeams. The realized beams are within about 2 dB of the ideal DVM beams in their directional selectivity. We achieve this massive reduction by starting from the recently proposed O(N log N ) DVM multi-beam algorithm [1] which makes use of the exact-DFT. Here, we propose to replace the DFT in [1] with an approximate DFT instead [2]- [4]. An exact DFT can be realized at O(N log N ) via FFTs while the approximate DFT has a corresponding matrix sparse factorization that exhibits O(N ) delays in DVM aggregated across its butterfly networks [2]- [4]. Therefore, even though there is a small (1.5 dB or less) loss of directional selectivity, we can achieve a massive reduction in number of true time delay (TTD) circuits while still achieving Nsimultaneous beams [2]- [4].

A. Construction of the Delay Vandermonde Matrix (DVM) [5]-[7]

The DVM is explicitly defined by

where N = 2 r (r ≥ 1), {α, α 2 , . . . , α N } are distinct complex nodes s.t. α = e -jωτ , j 2 = -1, ω is the temporal frequency, and τ is the delay. The scaled DVM, i.e., scaling w.r.t. a diagonal matrix, is defined as

The coefficient α kl is a temporal Fourier transform of a pure time-delay of duration τ. The signal x(t) with Fourier transform X(ω) is related to the delayed version of the signal x(t -pτ ) via the relationship X(ω)e -jpωτ . So the corresponding phase rotation of X(ω) is simply α p = e -jωpτ . Crucially, the DVM contains closed-form complex functions of ω given as complex phase rotations in integer powers p of α. That is, α p are not numerical values; they are complex functions of frequency ω raised to power p. So an N ×N DVM containing powers of α looks like a matrix-vector product but remember, we are in the temporal Fourier domain; so this is defined O(N 2 ) number of delay-and-sum dot product, not the usual O(N 2 ) number of multiply-and-sum dot product.

B. Review of DVM vs DFT, and FFT Algorithms

There are several mathematical techniques available to derive radix-2 and split-radix FFT algorithms, as described in [1], [8]- [14]. Even though the derivation of size-N DFT into two size-N 2 DFTs can be done easily, the extension of this idea to the DVM is cumbersome because the useful DFT matrix properties, like periodicity and unitary, are not present in the DVM [1], [5]. Consequently, considering these mathematical properties and the representation of DVM elements through TTD wideband multi-beam-unlike the narrowband representation characterized by the FFT-beams-it becomes evident that DVM serves as a superclass of DFT matrices.

Our previous work introduced various DVM algorithms designed to accurately compute the exact DVM-vector product for both narrowband and wideband communication systems. Our latest study [1] presents a derivation of the DVM algorithm, successfully reducing the complexity of RF N -beam analog beamforming systems from O(N 2 ) to O(N log N ). While the DVM algorithms proposed in [5], [7] show greater efficiency compared to brute-force matrix-vector calculations, their arithmetic complexity remains substantially higher than O(N log N ) [1]. On the other hand, our work in [6] focuses on numerically stable DVM algorithms with complexity of O(N log N ) that apply to Vandermonde matrices with nodes positioned on the unit circle (not exclusively at the roots of unity) and also on circles with their center at the origin and a radius exceeding one. Unlike the DVM algorithms highlighted in [5]- [7], which are specifically designed for narrowband communication systems, the radix-2 DVM algorithm presented in [1] is tailored for TTD wideband communication systems.

With these said, we introduce sparse factors to compute an approximate DVM (ADVM) using approximate DFT to reduce delay complexity from quadratic to linear. Before stating the factorization formula for the approximate DVM, we state the factorization leading O(N log N ) DVM algorithm as follows.

C. Review of DVM factorization [1]

The scaled DVM factorization resulting in an O(N log N ) DVM algorithm is presented in [1], and it executes based on the DVM factorization defined below

sparse matrix containing the identity matrix I N and the zero matrix 0 N , T denotes the transpose of matrices. The matrices

and DM = diag FM c are diagonal matrices, and a circulant matrix

The DFT matrix is defined by Remark 2.1: It is important to highlight that the O(N log N ) DVM algorithm in [1] executes recursively utilizing the wellknown FFTs in [8], [9].

Following the discussion on implementing the DVM algorithm using the FFT, we would like to explicitly refer the reader to papers [15], [16] to compute multiplierless approximated 16-point and 32-point DFT matrices having a product of highly sparse matrices. The approximate DFT factorization is then embedded into the DVM algorithm in [1] to reduce the complexity of computing the DVM-vector product, reducing it from O(N 2 ) to O(N ).

D. Proposed ADVM-Factorization for O(N ) DVM Algorithm

Building on the DVM factorization [1] and multiplierless approximate DFT factorization [15], [16], we state a factorization to approximate DVM. For a comprehensive understanding and in-depth algorithmic interpretation, we refer readers to [17].

Proposition 2.2: [from [17]] Let the scaled DVM

k,l=0 be defined by nodes {1, α, α 2 , . . . , α N -1 } ∈ C, N = 2 r (r ≥ 3), and M = 2N . Then, an approximation for the scaled DVM denoted as A N by vector x ∈ R ⋉ or C n , i.e., y = A N x can be computed through the following:

where F N is the approximate DFT matrix. Remark 2.3: Let us assume that we had utilized multiplierless approximated DFT matrices in computing the approximated scaled DVM-vector product in Proposition 2.2, then the explicit delay complexity in computing the scaled DVM-vector product is 4N -2, which intern has O(N ) complexity. Furthermore, by following the multiplierless 16-point and 32-point DFT algorithms in [15], [16], we could explicitly compute the approximated scaled DVM-vector product with 6N -6, 8N -14, and 10N -30 when N = 32, 64, 128. Thus, by following a series of complexity counts, we could state that the proposed approximated scaled DVM-vector product has the linear order, i.e. multiplication complexity of O(N ) as opposed to the FFT-like O(N log N ) complexity algorithms, for N = 16 to 1024 [17]. On the other hand, we note that the proposed DVM-vector product calculates an approximated DVM algorithm as opposed to the exact DVM algorithms in [1], [5]- [7], but with O(N ) complexity.

III. PROPOSED DVM BEAMFORMING RECEIVER

A. RF Front-Ends

The wideband low-noise amplifiers (LNAs) and Vivaldi antennas must cover the frequency span of up to 32 GHz as this is a direct-digital architecture. Design of such components can be difficult and procurement very expensive. For example, the LNA ZVA-0.5W303GX+ from MiniCircuits cover up to 30 GHz, with gain of and noise figure 4.2 dB, can be used as a transmit device. Similarly, MiniCircuits LVA-273PN-DG+ has frequency response up to 26.5 GHz, noise figure of about 10 dB, and gain of around 18 dB. The design of the frontend with up to 8 such amplifiers requires further study as these amplifiers cost several thousand dollars per unit and therefore careful optimized and cost-minimum design is a crucial requirement.

B. Wideband Data Conversion

The signals of interest are assumed to be of immense bandwidth, typically in the order of F s /2 = B = 32 GHz per channel. Sampling such wideband signals requires special circuitry as a single analog-to-digital converter (ADC) typically would not be able to sample, hold, and quantize such bandwidth at reasonable levels of precision and power consumption. We assume a time-interleave ADC with P parallel time-interleaved ADC sub-circuits. Each of these P sub-ADCs is further assumed to undergo temporal decimation by factor L such that the total number of parallel digital channels on the digital signal processor (DSP) would be P L and the digital clock period would be F Clk = Fs P L . For example, assuming a channel bandwidth of 32 GHz and a Nyquist rate of F s = 64 GS/s, and a P = 16 phase time-interleaved ADC, each sub-ADC will be sampling at 4 GS/s, with the DSP operating at F Clk = 256 MHz for a temporal decimation factor of L = 16.

C. Digital Delay Filters

The digital delays operate within the field programmable gate array (FPGA) or application specific integrated circuit (ASIC) fabric at a sample rate of F Clk MHz, over P L parallel channels that make up the multirate-DSP core that must finally realize any fractional delays or dot-products that are needed for the realization of the matrix analysis required in DVM wideband beamforming in real-time. The basic principle is as follows: let τ u be a fractional delay filter, which implies 0 ≤ τ u < 1 with reference to the full-scale clock F s GHz. A delay τ u causes a phase rotation in the frequency domain exp(-jωτ u ) where ω is the normalized frequency variable with reference to the master sample rate F s GHz.

An M -th order finite impulse response (FIR) can be designed and realized as a multirate filter to achieve the necessary fractional time sample delays. Typically, multiplications are directly correlated to filter order M that is required for the FIR filter for high bandwidth and precise operation therein causing FIR delays to be a major factor for complexity in multi-beam systems. In our hypothetical design, with P L = 256 we may assume M = 16 for a reasonable reference design. The blockwise computation of the order-M FIR fractional delay filter (an interpolation operation between integer multiples of the clock at frequency F s ) can be realized as a matrix-vector product of the form y = Tx where T is a banded Toeplitz matrix.

The structure of the banded Toeplitz matrix lends itself well for FFT-based computation and can be realized using the maximally-decimated uniform-DFT polyphase filterbank approach to efficient FIR filter realization. Here, the number of phases is P L = 256 thus leading to a massively parallel digital architecture.

D. Wideband Digital FPGA Platforms

In the past, fully-digital realizations of wideband beamforming networks that operate over multi-GH bandwidths have been only a dream due to the lack of ADC/DAC and fast DSP technologies. However, the most recent innovations from Intel Corporation, namely the Series 9 Direct-RF Agilex system on chip (SoC) using multi-chiplets packaged together offers exciting possibilities for multi-beam wideband DVM beamformers that span the legacy bands up to 7 GHz (FR1), and upper mid-band (7-24 GHz) and frequency range two (24-32 GHz) in a single antenna system and DSP platform. Our proposed low-complexity O(N ) linear delay-complexity digital DVM algorithm is a key enabler that when coupled with the latest Direct-RF chiplets leads to a new realm of possibilities for fully digital broadband antenna aperture arrays. The Series 9 Agilex Direct-RF chiplets offer 8 ADCs, 8 DACs, and a field programmable gate array (FPGA) device on the same package, where each DAC/DAC can operate up to 64 GS/s (bandwidth of 32 GHz).

IV. CONCLUSIONS

The paper presents our innovative, patent-pending algorithm for low-complexity true time delay DAS multi-beam beamforming, which is based on delay Vandermonde matrices. The proposed DVM factorization significantly enhances efficiency by reducing the complexity of computing the DVM-vector product from O(N 2 ) to O(N ). This significant reduction in computational complexity allows us to develop an algorithm for TTD wideband multi-beam beamformers enabling approximating DVM with O(N ) complexity, streamlining the process and improving performance. The algorithm uses only O(N ) delay lines, which is a linear complexity system, as opposed to traditional multi-beam wideband beamformers that have O(N 2 ) which is quadratic in delay complexity. A brief overview of our ongoing work with fully digital multi-beam beamformers that use the state-of-the-art (SOTA) chiplets from Intel Altera was provided. No real-world realization has been attempted thus far due to lack of resources. However, the authors are working towards an experimental realization.