%% slac-pub-7205: page file slac-pub-7205-0-0-2-2.tcx.
%% subsection 2.2 Bit-Strings [slac-pub-7205-0-0-2-2 in slac-pub-7205-0-0-2: slac-pub-7205-0-0-2-3]
%%%% latex2techexplorer block:
%% latex2techexplorer page setup:
\newmenu{slac-pub-7205::context::slac-pub-7205-0-0-2-2}{
\docLink{slac-pub-7205.tcx}[::Top]{Top}%
\sectionLink{slac-pub-7205-0-0-2}{slac-pub-7205-0-0-2}{Above: 2. Program Universe}%
\subsectionLink{slac-pub-7205-0-0-2}{slac-pub-7205-0-0-2-1}{Previous: 2.1. Origin of Program Universe}%
\subsectionLink{slac-pub-7205-0-0-2}{slac-pub-7205-0-0-2-3}{Next: 2.3. Program Universe}%
}
%%%% end of latex2techexplorer block.
\subsection{\usemenu{slac-pub-7205::context::slac-pub-7205-0-0-2-2}{Bit-Strings}}\label{subsection::slac-pub-7205-0-0-2-2}
Define a bit-string {\bf a}(a;W) with length W and Hamming measure $a$
by its $W$ ordered elements $({\bf a})_w \equiv a_w \in 0,1$ where
$w \in 1,2,...,W$. Define the Dirac inner product, which reduces
two bit-strings to a single positive integer, by ${\bf a} \cdot {\bf b}
\equiv \Sigma_{w=1}^W a_wb_w$. Hence ${\bf a}\cdot {\bf a}= a$ and
${\bf b}\cdot {\bf b}= b$. Define {\it discrimination} between
bit-strings of the same length, which yields a third string of the same
length, by $({\bf a} \oplus {\bf b})_w = (a_w-b_w)^2$. Clive and I arrived
at this way of representing discrimination during a session in his office
after ANPA 2 or 3. From this representation the {\it basic bit-string theorem}
follows immediately:
\begin{equation}
({\bf a} \oplus {\bf b})\cdot ({\bf a} \oplus {\bf b})=
a+b-2{\bf a} \cdot {\bf b}
\end{equation}
This equation could provide the starting point for an alternative definition
of ``$\oplus$'' which avoids invoking the explicit structure used above.
We also will need the {\it null string} ${\bf \Phi}(W)$
which is simply a string of $W$ zeros. Note that ${\bf a}\oplus {\bf a}
={\bf \Phi}(W)$, that $({\bf a}\oplus {\bf a})\cdot
({\bf a}\oplus {\bf a}) = 0$ and that ${\bf a}\cdot {\bf \Phi}=0$.
The complement of the null string is
the {\it anti-null string} ${\bf W}(W)$ which consists of $W$ ones
and has the property ${\bf W}\cdot {\bf W} = W$.
Of course ${\bf W}\cdot{\bf \Phi}=0$.
Define {\it concatenation}, symbolized by ``$\Vert$'', for two
string ${\bf a}(a;S_a)$ and ${\bf b}(b;S_a)$ with Hamming measures
$a$ and $b$ and respective lengths $S_a$ and $S_b$ and which
produces a string of length $S_a+S_b$, by
\begin{eqnarray}
({\bf a}\Vert{\bf b})_s &\equiv& a_s \ \ if \ \ s \ \in 1,2,...,S_a\nonumber\\
&\equiv& b_{S_a-s} \ \ if \ \ s \ \in S_a+1,S_a+2,...,S_a+S_b
\end{eqnarray}
For strings of equal length this doubles the length of the string
and hence doubles the size of the bit-string space we are using. For
strings of equal length it is sometimes useful to use the
shorthand but somewhat ambiguous ``product notation'' ${\bf a}{\bf b}$
for concatenation. Note that while ``$\cdot$'' and ``$\oplus$'' are,
separately, both associative and
commutative, in general concatenation is not commutative even for
strings of equal length, although it is always, separately, associative.