To form a single beam with data sampled at 100 KHz from an array of 100 elements, 10 million multiply-accumulates (MACs) are required per second. To form 50 beams, 500 million MACs per second are required, which is 1000 MFLOPS. These numbers are for digital beamforming without interpolation.
Fortunately, the beamforming algorithm is extremely parallelizable.
Traditionally, expensive custom hardware has been required to implement these algorithms in real time. Hardware commonly consists of hardware state machines with multiply-accumulate circuits (MACS). With the push towards COTS (commercial off-the-shelf) technologies, implementations with many DSP boards in a VME chassis are becoming more common. These implementations are still expensive.
Vertical Beamforming
The above discussion has applied only to 2-D (horizontal) beamforming...
In order to image environments in three dimensions, sonar arrays have multiple vertical elements per horizontal location. These elements are vertically beamformed into logical horizontal elements (or staves) before horizontal beamforming. Vertical beamforming has been performed by:
- tying vertical elements together
- analog weighting and summing
- analog weighting, delaying, and summing
- digital weighting, delaying, and summing
Digital Interpolation Beamforming as a Sparse FIR
Filter
Modeling the beamformer as a FIR filter allows for a simple, concise organization of the algorithm. For our model we use the following parameters, with values from the example in parentheses:
- T - the total number of elements in the array (80)
- D - the maximum sample delay due to array geometry (31)
- L - the length of the interpolation filter (2)
- B - the number of beams calculated (61)
- S - the number of staves (elements) used to calculate a beam (50)
In this example we use unity shading, and simply interpolate across two samples. As a result, all coefficient values are between zero and one. The figure below plots these values, where white is one and black is zero. Non-zero coefficients are extremely sparse, allowing efficient implementation. Note that each "picture" contains the values required to calculate one sample of one beam output.
If multiple samples of the entire sensor array are stored contiguously in memory, then each beam's coefficients can be represented by a FIR filter of length N = (D+L-1)T. Now the entire beamforming operation (for one sample of B beams) can be represented by a single operation:
The FIR filter length, N, can be extremely long -- in our example it is 2560. However, the number of non-zero coefficients is only 100, for a sparsity of 96%. As a result, 6100 multiply-accumulates (MACs) are required per sample. At high-frequency sonar sample rates, we are approaching one billion MACs per second.
