Discrete-time beamforming explained

Beamforming is a signal processing technique used to spatially select propagating waves (most notably acoustic and electromagnetic waves). In order to implement beamforming on digital hardware the received signals need to be discretized. This introduces quantization error, perturbing the array pattern. For this reason, the sample rate must be generally much greater than the Nyquist rate.^[1]

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 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( x ,t) exists in the spatial domain at position x and at time t . The 4-D Fourier transform of the signal yields S( k ,\omega) which exists in the wavenumber-frequency spectrum. The wavenumber vector k represents the 3-D spatial frequency and \omega represents the temporal frequency. The 4-D sinusoid e ^{j(\omega} , where k ' denotes the transpose of the vector k , can be rewritten as e ^{j} ' x )} where \boldsymbol{\alpha} = (k)/(\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

\tau such that \boldsymbol{\tau _{i}} = - \boldsymbol{\alpha _{o}'} x _{i} is the delay of the ith sensor at position x _{i} and where the direction of the slowness vector \boldsymbol{\alpha _{o}} is the direction of interest.

Discrete-time weighted delay-and-sum beamforming

Source:^[2]

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) = (1)/(N) \sum ^{N -1} _{i =0} w _{i} r _{i} (nT - n _{iT)}

where:

N is the number of sensorsw _{i} are the weightsT is the sampling periodn _{i} T is the steering delay for the ith sensorSetting n _{i} T equal to - \boldsymbol{\alpha _{o}'} 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 \Delta \tau _{i} = n _{i} T - \tau _{i} . The array pattern for a desired direction given by the slowness vector \alpha _{o} and for a quantization error \Delta \tau _{i} becomes:H( k ,\omega) = (1)/(N) \sum ^{N -1} _{i =0} w _{i} e ^{- j( k - \omega \boldsymbol{\alpha _{0}} )' x _{i} } e^

Interpolation

Source:^[3]

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 \tilde{T} . The beamformer output bf(n\tilde{T}) is nowbf(n\tilde{T}) = (1)/(N) \sum ^{N -1} _{i =0} w _{i} \tilde{r} _{i(n\tilde{T}} - n _{i\tilde{T})}

The sampling period ratio

I = (T)/(\tilde{T) } is set to an integer to minimize the increase in computations. The samples \tilde{r} _{i(m\tilde{T})} are interpolated from r _{i(nT)} such that\tilde{r} _{i(m\tilde{T})} = \sum _{n} r _{i(nT)g((m} - nI)\tilde{T})

After

bf(n\tilde{T}) is upsampled and filtered, the beamformer output bf(m\tilde{T}) becomes:bf(m\tilde{T}) = (1)/(N) \sum ^{N -1} _{i =0} w _{i} \sum _{p} r _{i(pT)} g((m - pI - n _{i)} \tilde{T})

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

Frequency-domain beamforming

Source:^[4]

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.^[5]

The discrete-time frequency-domain beamformer is given by

fd(nT,\omega) = (1)/(N) \sum ^{N -1} _{i =0} w _{i} R ^{j\omega(n - \boldsymbol{\tau} _{i)}}

For linearly spaced sensor arrays

\boldsymbol{\tau} _{i} = - (Mq)/(Nl) i . The discrete short-time Fourier transform of r _{i(nT)} is denoted by R _{i(nT,\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 \omega . If \omega = (2 \pi l)/(M) for 0 \le l < M then R ^{j\omega(n - \boldsymbol{\tau} _{i)}} becomes:R _{i} \left( n, (2 \pi l)/(M) \right) e ^{j (2 \pi l)/(M) n} = \sum ^{M -1} _{p =0} r _{i(n} - p)v(p) e ^{j (2 \pi l)/(M) p}

where

p = n - m . Substituting the 1-D FFT into the frequency-domain beamformer:fd \left( n, (2 \pi l)/(M) \right) = \left[ (1)/(N) \sum ^{N -1} _{i =0} w _{i} R _{i} \left( n, (2 \pi l)/(M) e ^{j (2 \pi q)/(N) i} \right) \right] e ^{j (2 \pi l)/(M) n}

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

fd \left( n, (2 \pi l)/(M) \right) = (1)/(N) \sum ^{N -1} _{i =0} \sum ^{M -1} _{p =0} w _{i} v(p) r _{i(n-p)} e ^{j (2 \pi l)/(M) p + j (2 \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)} thenfd \left( n, (2 \pi l)/(M) \right) = (1)/(N) X _{n(M-l,N-q)}

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

\alpha _{0x} = (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

Notes and References

1. http://users.ece.utexas.edu/~bevans/courses/ee381k/lectures/SonarBeamforming/lecture12/discrete.html Sonar Beamforming
2. Book: Multidimensional Signal Processing. Dudgeon. Dan. Prentice-Hall. 1983. 0-13-604959-1. 303–307. Russel. Mersereau.
3. D. Dudgeon and R. Mersereau, Multidimensional Digital Signal Processing, Prentice-Hall, First Edition, pp. 307 - 309, 1983.
4. D. Dudgeon and R. Mersereau, Multidimensional Digital Signal Processing, Prentice-Hall, First Edition, pp. 309 - 311, 1983.
5. Web site: A Frequency Domain Beamforming Method to Locate Moving Sound Sources. 10919/27765. 4 May 2010. Camargo. Hugo Elias.