BITS Correlator

This document tries to explain the working of the working of the lookup table program for the BITS Radio Telescope Correlator. Note that this program is later separately implemented as a function, as the aim is to write a lookup table to memory

Why Correlation

Cross correlation is needed in order to calculate the complex visibilities $V_{1}V_{2}^{*}$ from pairs of two antennas each. The Fourier Transform of these complex visibilities for all sets of possible baselines in the plane will give us the final radio image.

Cross Correlation

The finite Cross Correlation of two discrete antenna streams $V_{1}$ and $V_{2}$ is given by :

$(V_{1}\star V_{2})[n]\ {\stackrel {}{=}}\sum _{m=-N}^{+N}V_{1}^{*}[m]\ V_{2}[n+m].$

Here, 2N is the number of samples in the frame that we use. For the BITS Telescope using the lookup table, this number is typically 8 or 16. Increase in this number increases the spectral density and information, but also increases the computational cost

Introduction : Lookup Table

The program included generates a lookup table of 3 × 3, i.e., it generates a lookup table that gives the result of all possible termwise multiplications of a 3-element stream by another 3-element stream. This can later be looked up just by referring to an array index defined by the two bitsreams, which greatly reduces the computation time.

3×3 Lookup Table

Consider two bitstreams (00|11|00) and (11|00|11). According to the scheme that we use for representation (00 = +1, 01 = +2, 11 = -1, 10 = -2), we have these two bitstreams as

Stream1	00	11	00
Stream2	11	00	11

Therefore, these streams are actually

Stream1	(+1)	(-1)	(+1)
Stream2	(-1)	(+1)	(-1)

Thus, the end result is equal to : -1 + -1 + -1 = -3

Now, we want to store this result in a location, which is defined by Stream1 and Stream2. One could store this in a two-dimensional array, or in a linear one. In this implementation, it has been stored in a linear array due to declaration constraints on higher level tables. Therefore, the result will be stored in location 001100110011, or in other words, 0x333.

Note: At this point, the program can be checked by modifying the print statement to print the results for desired bitstreams.

Construction of the Table

The idea behind the construction of the table is very simple. All numbers from 00-00-00 to 11-11-11, ie from 0x00 to 0x3F are taken one at a time in the outer loop. In the inner loop, the termwise multiplication of each of these streams is taken with every other possible stream, i.e. again from 00-00-00 to 11-11-11 and stored in the location defined by the two streams. One immediate scope for improvement is that repetitions in the table (caused by interchange of indiced of the inner and outer loops) may be avoided by means of a better loop structure).

Bit Masks

Since each element of the individual streams needs to be separated in order to perform the termwise multiplication, we create bit masks to separate out that element. For example, in order to separate 10 from $11-10-00$, we create the bit mask $00-11-00$ and OR it with the sample, and shift the result left to get the actual sample.

Level Shifting

The decimal values of the binary samples, and what we have designed them to be, are tabulated below

Sample	Decimal Value	Required Value	Offset
00	(+0)	(+1)	(+1)
01	(+1)	(+2)	(+1)
11	(+3)	(-1)	(-4)
10	(+2)	(-2)	( -4)

Thus, if the offsets are applied according to the initial values of the corresponding elements.

Index of result

The index has to be of the form Stream1Stream2. This is done by multiplying the entire bitstream of Stream1 by 2^{length}, which is 2^{12}, i.e. 4096. This is then added to Stream2 and the resulting index is Stream1Stream2 The result of the termwise multiplication and addition is stored in this array element.