Discrete-time beamforming

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 communications. 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 $s(\backslash mathbf\{x\},t)$ exists in the spatial domain at position $\backslash mathbf\{x\}$ and at time $t$. The 4-D Fourier transform of the signal yields $S(\backslash mathbf\{k\},\backslash omega)$ which exists in the wavenumber-frequency spectrum. The wavenumber vector $\backslash mathbf\{k\}$ represents the 3-D spatial frequency and $\backslash omega$ represents the temporal frequency. The 4-D sinusoid $e^\{j(\backslash omega\; t\; -\; \backslash mathbf\{k\}\text{'}\; \backslash mathbf\{x\})\}$, where $\backslash mathbf\{k\}\text{'}$ denotes the transpose of the vector $\backslash mathbf\{k\}$, can be rewritten as $e^\{j\; \backslash omega(t\; -\; \backslash boldsymbol\{\backslash alpha\}\text{'}\; \backslash mathbf\{x\})\}$ where $\backslash boldsymbol\{\backslash alpha\}\; =\; \backslash frac\{\backslash mathbf\{k\}\}\{\backslash omega\}$ , 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 $\backslash tau$ such that $\backslash boldsymbol\{\backslash tau\_i\}\; =\; -\backslash boldsymbol\{\backslash alpha\_o\}\text{'}\; \backslash mathbf\{x\_i\}$ is the delay of the ith sensor at position $\backslash mathbf\{x\_i\}$ and where the direction of the slowness vector $\backslash boldsymbol\{\backslash alpha\_o\}$ is the direction of interest.

Source:{{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}}

The discrete-time beamformer output $bf(nT)$ is formed by sampling the receiver signal $r\_i(t)$ and averaging its weighted and delayed versions.

$bf(nT)\; =\; \backslash frac\{1\}\{N\}\; \backslash sum\_\{i=0\}^\{N-1\}\; w\_i\; r\_i\; (nT\; -\; n\_iT)$

where:

• $N$ is the number of sensors
• $w\_i$ are the weights
• $T$ is the sampling period
• $n\_i\; T$ is the steering delay for the ith sensor

Setting $n\_i\; T$ equal to $-\backslash boldsymbol\{\backslash alpha\_o\}\text{'}\; \backslash mathbf\{x\_i\}$ would achieve the proper direction but $n\_i$ must be an integer. In most cases $n\_i$ will need to be quantized and errors will be introduced. The quantization errors can be described as $\backslash Delta\; \backslash tau\_i\; =\; n\_i\; T\; -\; \backslash tau\_i$. The array pattern for a desired direction given by the slowness vector $\backslash alpha\_o$ and for a quantization error $\backslash Delta\; \backslash tau\_i$ becomes:

$H(\backslash mathbf\{k\},\backslash omega)\; =\; \backslash frac\{1\}\{N\}\; \backslash sum\_\{i=0\}^\{N-1\}\; w\_i\; e^\{\; -j(\backslash mathbf\{k\}\; -\; \backslash omega\; \backslash boldsymbol\{\backslash alpha\_0\})\text{'}\; \backslash mathbf\{x\_i\}\}\; e^\{\; -j\; \backslash omega\; \backslash Delta\; \backslash tau\_i\; \}$

Source:D. Dudgeon and R. Mersereau, Multidimensional Digital Signal Processing, Prentice-Hall, First Edition, pp. 307 - 309, 1983.

File:Interpolation beamforming.PNG

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. $n\_i$ 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 $\backslash tilde\{T\}$. The beamformer output $bf(n\backslash tilde\{T\})$ is now

$bf(n\backslash tilde\{T\})\; =\; \backslash frac\{1\}\{N\}\; \backslash sum\_\{i=0\}^\{N-1\}\; w\_i\; \backslash tilde\{r\}\_i(n\backslash tilde\{T\}\; -n\_i\backslash tilde\{T\})$

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

$\backslash tilde\{r\}\_i(m\backslash tilde\{T\})\; =\; \backslash sum\_n\; r\_i(nT)g((m\; -\; nI)\backslash tilde\{T\})$

After $bf(n\backslash tilde\{T\})$ is upsampled and filtered, the beamformer output $bf(m\backslash tilde\{T\})$ becomes:

$bf(m\backslash tilde\{T\})\; =\; \backslash frac\{1\}\{N\}\; \backslash sum\_\{i=0\}^\{N-1\}\; w\_i\; \backslash sum\_p\; r\_i(pT)\; g((m-\; pI\; -\; n\_i)\; \backslash tilde\{T\})$

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

Source:D. Dudgeon and R. Mersereau, Multidimensional Digital Signal Processing, Prentice-Hall, First Edition, pp. 309 - 311, 1983.

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.{{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}}

The discrete-time frequency-domain beamformer is given by

$fd(nT,\backslash omega)\; =\; \backslash frac\{1\}\{N\}\; \backslash sum\_\{i=0\}^\{N-1\}w\_i\; R\_i(nT,\backslash omega)e^\; \{j\backslash omega(n-\backslash boldsymbol\{\backslash tau\}\_i)\}$

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

$R\_i\; \backslash left(\; n,\; \backslash frac\{2\backslash pi\; l\}\{M\}\; \backslash right)\; e^\{j\; \backslash frac\{2\backslash pi\; l\}\{M\}\; n\; \}\; =\; \backslash sum\_\{p=0\}^\{M-1\}\; r\_i(n\; -\; p)v(p)\; e^\{j\; \backslash frac\{2\backslash pi\; l\}\{M\}\; p\}$

where $p\; =\; n-m$. Substituting the 1-D FFT into the frequency-domain beamformer:

$fd\; \backslash left(\; n,\backslash frac\{2\backslash pi\; l\}\{M\}\; \backslash right)\; =\; \backslash left[\; \backslash frac\{1\}\{N\}\; \backslash sum\_\{i=0\}^\{N-1\}\; w\_i\; R\_i\; \backslash left(\; n,\; \backslash frac\{2\backslash pi\; l\}\{M\}\; e^\{j\; \backslash frac\{2\backslash pi\; q\}\{N\}\; i\}\; \backslash right)\; \backslash right]\; e^\{\; j\; \backslash frac\{2\backslash pi\; l\}\{M\}\; n\}$

The term in brackets is the 2-D DFT with the opposite sign in the exponential

$fd\; \backslash left(\; n,\backslash frac\{2\backslash pi\; l\}\{M\}\; \backslash right)\; =\; \backslash frac\{1\}\{N\}\; \backslash sum\_\{i=0\}^\{N-1\}\; \backslash sum\_\{p=0\}^\{M-1\}\; w\_i\; v(p)\; r\_i(n-p)\; e^\{j\; \backslash frac\{2\backslash pi\; l\}\{M\}\; p\; +\; j\; \backslash frac\{2\backslash pi\; q\}\{N\}\; i\}$

if the 2-D sequence $x\_n(p,i)\; =\; w\_i\; v(p)\; r\_i(n-p)$ and $X\_n(l,q)$ is the (M X N)-point DFT of $x\_n(p,i)$ then

$fd\; \backslash left(\; n,\backslash frac\{2\backslash pi\; l\}\{M\}\; \backslash right)\; =\; \backslash frac\{1\}\{N\}\; X\_n(M-l,N-q)$

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

$\backslash alpha\_\{0x\}\; =\; \backslash frac\{Mq\}\{NlD\}$

where:

• $M$ and $N$ are dimensions of the DFT
• $D$ is the sensor separation
• $l$ is the frequency index between $0$ and $M-1$
• $q$ is the steering index between $0$ and $N-1$

$l$ and $q$ can be selected to "steer the beam" towards a certain temporal frequency and spatial position

{{Reflist}}

Category:Digital signal processing