View source for Discrete-time beamforming

{{multiple issues|
{{cleanup|reason=copyedit / title not in lead, bad bold of other article, more citations, citations out of headings|date=January 2019}}
{{one source|date=January 2019}}
}}

'''[[Beamforming]]''' is a [[signal processing]] technique used to spatially select propagating waves (most notably [[Acoustic wave|acoustic]] and [[Electromagnetic radiation|electromagnetic]] waves). In order to implement beamforming on digital hardware the received signals need to be discretized. This introduces [[Quantization (signal processing)|quantization]] error, perturbing the array pattern. For this reason, the sample rate must be generally much greater than the [[Nyquist rate]].<ref>[http://users.ece.utexas.edu/~bevans/courses/ee381k/lectures/SonarBeamforming/lecture12/discrete.html Sonar Beamforming] users.ece.utexas.edu. Retrieved November 12, 2015</ref>

== Introduction ==
Beamforming aims to solve the problem of filtering signals coming from a certain direction as opposed to an omni-directional approach. Discrete-time beamforming is primarily of interest in the fields of [[seismology]], [[acoustics]], [[sonar]] and low frequency [[Wireless|wireless communications]]. [[Antenna (radio)|Antennas]] regularly make use of [[beamforming]] but it is mostly contained within the analog domain.

Beamforming begins with an array of sensors to detect a 4-D signal (3 physical dimensions and time). A 4-D signal <math>s(\mathbf{x},t)</math> exists in the spatial domain at position <math>\mathbf{x}</math> and at time <math>t</math>. The 4-D [[Fourier transform]] of the signal yields <math>S(\mathbf{k},\omega)</math> which exists in the wavenumber-frequency spectrum. The wavenumber vector <math>\mathbf{k}</math> represents the 3-D spatial frequency and <math>\omega</math> represents the temporal frequency. The 4-D sinusoid <math>e^{j(\omega t - \mathbf{k}' \mathbf{x})}</math>, where <math>\mathbf{k}'</math> denotes the transpose of the vector <math>\mathbf{k}</math>, can be rewritten as <math>e^{j \omega(t - \boldsymbol{\alpha}' \mathbf{x})}</math> where <math>\boldsymbol{\alpha} = \frac{\mathbf{k}}{\omega}</math> , also known as the slowness vector.

Steering the beam in a particular direction requires that all the sensors add in phase to the particular direction of interest. In order for each sensor to add in phase, each sensor will have a respective delay <math>\tau</math> such that <math>\boldsymbol{\tau_i} = -\boldsymbol{\alpha_o}' \mathbf{x_i}</math> is the delay of the ith sensor at position <math>\mathbf{x_i}</math> and where the direction of the slowness vector <math>\boldsymbol{\alpha_o}</math> is the direction of interest.

=== Discrete-time weighted delay-and-sum beamforming ===
Source:<ref>{{Cite book|title = Multidimensional Signal Processing|last1 = Dudgeon|first1 = Dan|publisher = Prentice-Hall|year = 1983|isbn = 0-13-604959-1|location = |pages = 303–307|first2 = Russel|last2 = Mersereau}}</ref>

The discrete-time beamformer output <math>bf(nT)</math> is formed by sampling the receiver signal <math>r_i(t)</math>  and averaging its weighted and delayed versions.

<math>bf(nT) = \frac{1}{N} \sum_{i=0}^{N-1} w_i r_i (nT - n_iT)</math>

where:
* <math>N</math> is the number of sensors
* <math>w_i</math> are the weights
* <math>T</math> is the sampling period
* <math>n_i T</math> is the steering delay for the ''i''th sensor
Setting <math>n_i T</math> equal to <math>-\boldsymbol{\alpha_o}' \mathbf{x_i}</math> would achieve the proper direction but <math>n_i</math> must be an integer. In most cases <math>n_i</math> will need to be quantized and errors will be introduced. The quantization errors can be described as <math>\Delta \tau_i = n_i T - \tau_i</math>. The array pattern for a desired direction given by the slowness vector <math>\alpha_o</math> and for a quantization error <math>\Delta \tau_i</math> becomes:

<math>H(\mathbf{k},\omega) = \frac{1}{N} \sum_{i=0}^{N-1} w_i e^{ -j(\mathbf{k} - \omega \boldsymbol{\alpha_0})' \mathbf{x_i}} e^{ -j \omega \Delta \tau_i }</math>

=== Interpolation ===
Source:<ref>D. Dudgeon and R. Mersereau, Multidimensional Digital Signal Processing, Prentice-Hall, First Edition, pp. 307 - 309, 1983.</ref>
[[File:Interpolation beamforming.PNG|none|thumb|784x784px|Flowchart of upsample and linear filter for discrete-time beamforming]]

The fundamental problem of discrete weighted delay-and-sum beamforming is quantization of the steering delay. The interpolation method aims to solve this problem by [[upsampling]] the receiving signal. <math>n_i</math> must still be an integer but it now has a finer control. Interpolation comes at the cost of more computation. The new sample rate is denoted as <math>\tilde{T}</math>.  The beamformer output <math>bf(n\tilde{T})</math> is now

<math>bf(n\tilde{T}) = \frac{1}{N} \sum_{i=0}^{N-1} w_i \tilde{r}_i(n\tilde{T} -n_i\tilde{T})</math>

The sampling period ratio <math>I = \frac{T}{\tilde{T}}</math> is set to an integer to minimize the increase in computations. The samples <math>\tilde{r}_i(m\tilde{T})</math> are interpolated from <math>r_i(nT)</math> such that

<math>\tilde{r}_i(m\tilde{T}) = \sum_n r_i(nT)g((m - nI)\tilde{T})</math>

After <math>bf(n\tilde{T})</math> is upsampled and filtered, the beamformer output <math>bf(m\tilde{T})</math> becomes:

<math>bf(m\tilde{T}) = \frac{1}{N} \sum_{i=0}^{N-1} w_i \sum_p r_i(pT) g((m- pI - n_i) \tilde{T})</math>

At this point the beamformer's sample rate is greater than the highest frequency it contains.

== Frequency-domain beamforming ==
Source:<ref>D. Dudgeon and R. Mersereau, Multidimensional Digital Signal Processing, Prentice-Hall, First Edition, pp. 309 - 311, 1983.</ref>

As seen in the discrete-time domain beamforming section, the weighted delay-and-sum method is effective and compact. Unfortunately quantization errors can perturb the array pattern enough to cause complications. The interpolation technique reduces the array pattern perturbations at the cost of a higher sampling rate and more computations on digital hardware. Frequency-domain beamforming does not require a higher sampling rate which makes the method more computationally efficient.<ref>{{Cite web|url=http://hdl.handle.net/10919/27765|hdl=10919/27765|title=A Frequency Domain Beamforming Method to Locate Moving Sound Sources|date=4 May 2010|last1=Camargo|first1=Hugo Elias}}</ref>

The discrete-time frequency-domain beamformer is given by

<math>fd(nT,\omega) = \frac{1}{N} \sum_{i=0}^{N-1}w_i R_i(nT,\omega)e^ {j\omega(n-\boldsymbol{\tau}_i)}</math>

For linearly spaced sensor arrays <math>\boldsymbol{\tau}_i = - \frac{Mq}{Nl} i</math>. The discrete [[short-time Fourier transform]] of <math>r_i(nT)</math> is denoted by <math>R_i(nT,\omega)</math>. In order to be computationally efficient it is desirable to evaluate the sum in as few calculations as possible. For simplicity <math>T = 1</math> moving forward. An effective method exists by considering a 1-D FFT for many values of <math>\omega</math>. If <math>\omega = \frac{2\pi l}{M}</math>  for <math>0 \le l < M</math> then <math>R_i(n,\omega)e^ {j\omega(n-\boldsymbol{\tau}_i)}</math> becomes:

<math>R_i \left( n, \frac{2\pi l}{M} \right) e^{j \frac{2\pi l}{M} n } =  \sum_{p=0}^{M-1} r_i(n - p)v(p) e^{j \frac{2\pi l}{M} p}</math>

where <math>p = n-m</math>. Substituting the 1-D FFT into the frequency-domain beamformer:

<math>fd \left( n,\frac{2\pi l}{M} \right) = \left[ \frac{1}{N} \sum_{i=0}^{N-1} w_i R_i \left( n, \frac{2\pi l}{M} e^{j \frac{2\pi q}{N} i} \right) \right] e^{ j \frac{2\pi l}{M} n}</math>

The term in brackets is the 2-D [[Discrete Fourier transform|DFT]] with the opposite sign in the exponential

<math>fd \left( n,\frac{2\pi l}{M} \right) = \frac{1}{N} \sum_{i=0}^{N-1} \sum_{p=0}^{M-1} w_i v(p) r_i(n-p) e^{j \frac{2\pi l}{M} p + j \frac{2\pi q}{N} i}</math>

if the 2-D sequence <math>x_n(p,i) = w_i v(p) r_i(n-p)</math> and <math>X_n(l,q)</math> is the (M X N)-point DFT of <math>x_n(p,i)</math> then

<math>fd \left( n,\frac{2\pi l}{M} \right) = \frac{1}{N} X_n(M-l,N-q)</math>

For a 1-D linear array along the horizontal direction and a desired direction:

<math>\alpha_{0x} = \frac{Mq}{NlD}</math>

where: 
* <math>M</math> and <math>N</math> are dimensions of the DFT 
* <math>D</math> is the sensor separation 
* <math>l</math> is the frequency index between <math>0</math> and <math>M-1</math> 
* <math>q</math> is the steering index between <math>0</math> and <math>N-1</math> 
<math>l</math> and <math>q</math> can be selected to "steer the beam" towards a certain temporal frequency and spatial position

== References ==
{{Reflist}}

[[Category:Digital signal processing]]