Auxiliary page

From Wikiversity
Jump to navigation Jump to search

This is the page where I will directly enter the TeX markup and see if it succeeds

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

Introduction[edit | edit source]

The program included generates a lookup table of $3 \times 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.

Lookup Table[edit | edit source]

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

Failed to parse (unknown function "\begin{center}"): {\displaystyle \begin{center} \begin{tabular}{{|c|c|c|c|}} \hline \texttt{Stream1} & 00 & 11 & 00\\ \hline \texttt{Stream2} & 11 & 00 & 11\\ \hline \end{tabular} \end{center} Therefore, these streams are actually \begin{center} \begin{tabular}{{|c|c|c|c|}} \hline \texttt{Stream1} & +1 & -1 & +1\\ \hline \texttt{Stream2} & -1 & +1 & -1\\ \hline \texttt{Multiplication} & -1 & -1 & -1\\ \hline \end{tabular} \end{center} 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 \texttt{Stream1} and \texttt{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$.

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

\section{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 $00$ to $3F$ in hex 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).

\subsection{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.

\subsection{Level Shifting} The decimal values of the binary samples, and what we have designed them to be, are tabulated below \begin{center} \begin{tabular}{|c|c|c|c|} \hline \hline Sample & Decimal Value & Required Value & Offset\\ \hline 00 & +0 & +1 & +1\\ 01 & +1 & +2 & +1\\ 11 & +3 & -1 & -4\\ 10 & +2 & -2 & -4\\ \hline

\end{tabular} \end{center}

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

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