BIDIRECTIONAL ASSOCIATIVE MEMORY SYSTEMS IN C++

Recent innovation makes associative memory practical for real-world problems

Adam Blum

Adam is a programmer analyst at Ketron Inc. of Arlington, Virginia, and is the principal developer of several commercial software packages. His interests include compiler design, C++, and (of course) applications of neural nets. He can be contacted at 1700 N. Moore St., Ste. 1710, Arlington, VA 22209, or on CompuServe at 72650, 1773.

Content-addressability was always a goal of early neural network pioneers. It is a quest that has been pursued by computer scientists in general for decades. However, the goal has proved highly elusive. Search time has always depended on the amount of data stored, although much research has gone into reducing the slope of this curve. Real-time pattern recognition (as applied to any number of fields, be it speech recognition, radar signature identification, or part classification) is still far from reality. One particular neural-network construct, bidirectional associative memory (or BAM), has promised some solution to this problem.

I'll first describe the BAM concept, then show you how a relatively recent construct, the Bam System, can make it immediately feasible for real problems. Finally, I'll present an actual implementation of the Bam System written in C++.

As developed by Bart Kosko, BAMs are a neural-network-based attempt at content-addressable memories. They are based on a two-layer feedback neural network. They attempt to encode m pattern pairs (A_i,B_i) where A_i {-1,+1}ⁿ and B_i {-1,+1}^p in an n x p matrix M. BAMs are globally stable and provide instant recall of either of the two-pattern pair elements. However, BAMs face some limitations. For large pattern lengths, n, storage requirements increase O(n²). More importantly, storage capacity is only, on an average, m < min(n,p). Thus, for moderate pattern lengths, capacity of the matrix M becomes a problem. Recent research promises help for this problem. However, some initial description of BAMs should be made.

Encoding

BAM encoding is accomplished by simply summing the correlation matrices of each of the pattern pairs. That is, the matrix that encodes the first m pattern pairs, M, is simply:

    
    m   
M =  A_i^TB_i
   i=1

Thus, to encode a pattern pair, simply produce its correlation matrix, A_i^TB_i, and add the values to the current matrix M. For discrete implementations, it so happens that the matrix arithmetic works out better if 0s and 1s are encoded as -1s and +1s. So the first step in the process will be to convert any {0,1} string to {-1,+1}. Example 1 shows this process.

Example 1: The encoding process

If we are trying to encode

      A₁ = (101010) B₁ = (1100)
      A₂ = (111000) B₂ = (1010)

we first convert to {-1,+1}.

      X₁ = (1 -1 1 -1  1 -1)      Y₁ = (1  1 -1 -1)
      X₂ = (1  1 1 -1 -1 -1)      Y₂ = (1 -1  1 -1)

                 X₁^TY₁ = 1  1 -1 -1
                        -1 -1  1  1
                         1  1 -1 -1
                        -1  1  1  1
                         1  1 -1 -1
                        -1 -1  1  1

              X₁^TY₂ = 1 -1  1 -1
                      1 -1  1 -1
                      1 -1  1 -1
                     -1  1 -1  1
                     -1  1 -1  1
                     -1  1 -1  1

                  M = 2  0  0 -2
                      0 -2  2  0
                      2  0  0 -2
                     -2  2  0  2
                      0  2 -2  0
                     -2  0  0  2

Note that we can erase association (A_i,B_i) from M by adding -X_iTY_i to M. But if we are using a {-1,+1} representation, this is the same as adding (A_i,B_iC) or (A_iC,B_i) to M (where C represents the pattern's complement). This fact will become important in our implementation of the BAM system.

Decoding

After we have "trained" our BAM with the m pattern pairs (A_i,B_i), we want the BAM to recall pattern B_i every time A_i is presented to the matrix (and, conversely, recall A_i every time B_i is presented to the matrix). It turns out that BAMs also have the property that B_i will be recalled every time something close to A_i is presented. Example 2 outlines the steps involved in the decoding process.

Example 2: The decoding process

Each neuron b_j in field Fb (Fa and Fb will be used to refer to the two pattern fields A and B) receives a gated input of all the neurons in Fa with a nonlinear threshold function applied. In our bipolar discrete example a typical function might be:

  f(x,y) = 1 if x > 0
  y if x = 0
  0 if x < 0

We now have a pattern B₁. However, we aren't done yet. The output from pattern B is then fed back through the transpose of matrix M to produce pattern A₁. That is, each neuron A_i in A receives gated input from each neuron B_j in B and applies the same threshold function to it.

A₁ is then sent back through the matrix again to produce B₂, and on this goes.

  A --> F(AM) --> B₁
  A₁ <-- F(B₁M^T) <-- B₁
  A₁ --> F(A₁M) --> B₂
		.
		.
  A_i --> F(A_i) --> B_i
  A_i --> F(B_iM) --> B_i

But it won't go on forever. As shown in Example 2, eventually the fields will "resonate" to steady patterns. This property of BAMs is called "global stability." Lyapunov energy functions allow us to prove that BAMs are globally stable.

The vector class is implemented in classic fashion (almost identical to Stroustrup's). Methods are provided for assignment, multiplication by scalar constant, and dot product. This is all that is really necessary, but a few more methods are provided for completeness. Streams input and output are provided to read the patterns in and display patterns to the user. The streams functions do the necessary (0,1) to (-1, +1) conversion discussed earlier.

The matrix class is implemented as an array of pointers (int **), with indicators of the number of rows and columns. It could conceivably have been implemented as an array of vector objects. I chose representation for efficiency. There are several constructors provided. The first simply initializes the matrix from specified dimensions. These dimensions default to the particular application's two pattern lengths (specified by the ROWS and COLS constants). Other constructors are provided to form a matrix from a pair of vectors by multiplying one vector by the transpose of another (M=AB^T). Standard matrix arithmetic functions are included. Methods are also provided to form a vector from a row or column "slice" of the matrix. Streams output is provided for debugging diagnostics.

Another fundamental construct is the pattern pair. This is, after all, what the BAM lets us do -- retrieve pattern associations. Pattern pairs are represented by the "vecpair" (vector pair) class. An "encode" operation will encode a vecpair. A "recall" operation will return a vecpair, when supplied with a pattern (or "vec").

Once we have these vector, matrix, and vector pair classes, implementing the BAM is fairly simple. The BAM is essentially just a matrix. We use the C++ inheritance mechanism to inherit the matrix and all its functions. We made the matrix's data structures "protected" instead of "private" so the derived BAM matrix class could use the matrix's data structures. We now just add a vecpair pointer for the pattern pair list and the BAM matrix functions.

These consist mainly of the "encode" and "recall" functions central to the BAM. Encode simply takes the "vecpair" corresponding to the association and adds it (with matrix add) to the current BAM. Recall "feeds" the presented pattern through the matrix (with dot products and by applying a threshold function as discussed earlier) to return another vector. We keep feeding the vectors back and forth until they stabilize to a consistent pattern association. There are also some auxiliary functions for checking the integrity of the BAM, returning its energy for a particular association (as discussed earlier), and for "uncoding" or removing an association from the BAM.

The Bam System class consists of an array of pointers to BAM matrices. Each time a BAM matrix is saturated, a new matrix is created, and the new pattern association is stored in it. The major functions are again "encode" and "recall." Encode attempts to store the pattern association in each of the BAM matrices until it succeeds. It will create a new BAM matrix if it runs out of matrices. Recall performs a BAM matrix recall operation on each of the BAM matrices. The returned association that is closest to the presented pattern and has the lowest energy relative to its matrix (as discussed earlier) is then returned as the "correct" pattern association. Another function is provided to "train" the Bam System from a specified file of pattern associations. The patterns happen to be represented as 01 strings, but this could be easily changed to whatever representation (for example, floating-point numbers, character strings) suits the specific application.

Thanks to the wonders of C++, the code is very readable. Most of the algorithms can be implemented in the same vocabulary as the theory. Take a look at it to examine the mechanics in detail. It should even be clearer (and certainly more specific) than the discussion above.

The Test Program

I've included a test program (TESTBAM.CPP, Listing Three, page 88) that demonstrates an actual running Bam System. A Bam System is created and told to "train" itself from the file TEST.FIL (see Listing Four, page 88). This file contains a set of simple "pattern pairs," represented as (0,1) strings delimited by commas -- one pattern pair to a line. Once the Bam System is trained, you can enter any pattern you want (using the 01 format mentioned) and the correct pattern association will be recalled. If the pattern is slightly wrong, the correct pattern association will still most likely be recalled. The make file, TESTBAM.MK (Listing Five, page 88), shows how to construct this test program.

What Can you Do With It?

Uses of the Bam System are constrained only by your imagination. Obvious uses include optical character recognition (the pixel patterns scanned in would be associated with the actual letters), voice recognition (the acoustic pattern would be associated with the actual word), or a super spell checker (word patterns associated with phonemestring patterns). You can use a Bam System in just about any application where you have a large number of "associations" that you would like to be able to recall close to instantaneously, and where some tolerance for error would be useful.

A successful application of BAM for radar signature classification was presented at the January 1990 International Joint Conference on Neural Networks (IJCNN). However, it was not a Bam System, and the implementors had to resort to various other tricks to get around capacity limitations. Several other associative memory applications appeared; but none of them were associative memory systems. They all would probably run into the capacity roadblock eventually for large data sets. Associative memories and BAMs have begun to appear implemented in VLSI, but again the capacity will prove to be a limitation for practical work. Bam Systems should have a radical effect on the usefulness of these chips.

Conclusion

Bidirectional associative memories appear to provide the content-addressable memory long sought after by computer scientists. They provide instant recall of pattern association, tolerance for error and fuzziness in the provided pattern, and global stability. However, by themselves they face some limitations. Simple BAM matrices cannot encode more pattern pairs than the smaller of their two dimensions. Some applications have inherently smaller pattern length, and, for them, matrix capacity will prove to be a severe limitation. However, the Bam System appears to overcome this problem, making associative memory a reality.

Notes

Grossberg, S. The Adaptive Brain, I & II. Boston, Mass.: Reidel Press, 1982.

Kohonen, T. Self-Organization and Associative Memory. Berlin, W. Germany: Springer-Verlag, 1977.

Kosko, B. "Bidirectional Associative Memories," IEEE Trans. Systems, Man, Cybernetics, Vol. SMC-L8, 49-60, Jan./Feb. 1988.

Rumelhart, D.E., McClelland, J.L., eds., Parallel Distributed Processing, I & II. Cambridge, Mass.: MIT Press, 1986.

Simpson, P.K. "Bidirectional Associative Memory Systems," Heuristics, 1989.

Simpson, P.K., "Associative Memory Systems," Proceedings of the International Joint Conference on Neural Networks, January 1990.

BIDIRECTIONAL ASSOCIATIVE MEMORY SYSTEMS IN C++ by Adam Blum [LISTING ONE]



////////////////////////////////////////////////////////////
// BAM.HPP  Provide vector, matrix, vector pair, matrix, BAM matrix, and
// BAM system classes and methods to implement BAM system concept.
// Extended note:
// This is an implementation of the concept of Bidirectional
// Associative Memories as developed by Bart Kosko and others.
// It includes the extended concept introduced by Patrick Simpson
// of the "BAM System". Where reasonable Simpson's notation has been
// been maintained. The presentation benefits greatly from C++ and OOP, in that
// (I believe) it is both easier to understand than a "pseudocode" version,
// yet more precise (in that it works!)
// Developed with Zortech C++ Version 2.0 -- Copyright (c) Adam Blum, 1989,90

#include<stdlib.h>
#include<io.h>
#include<stdio.h>
#include<string.h>
#include<limits.h>
#include<ctype.h>
#include<stream.hpp>
#include "debug.h" // debugging devices
// where are Zortech's min,max?
#define max(a,b)   (((a) > (b)) ? (a) : (b))
#define min(a,b)   (((a) < (b)) ? (a) : (b))

// will be changed to much higher than these values
const ROWS=16;   // number of rows (length of first pattern)
const COLS=8;   // number of columns (length of second pattern)
const MAXMATS=10; // maximum number of matrices in BAM system
const MAXVEC=16; // default size of vectors

class matrix;
class bam_matrix;
class vec {
   friend class matrix;
   friend class bam_matrix;
   friend class bam_system;
      int n;
      int *v;
   public:
      // see BAM.CPP for implementations of these
      vec(int size=MAXVEC,int val=0); // constructor
      ~vec();   // destructor
      vec(vec &v1); // copy-initializer
      int length();
      vec& operator=(const vec& v1); // vector assignment
      vec& operator+(const vec& v1); // vector addition
      vec& operator+=(const vec& v1); // vector additive-assignment
      vec& operator*=(int i); // vector multiply by constant
      // supplied for completeness, but we don't use this now
      int operator*(const vec& v1); // dot product
      vec operator*(int c); // multiply by constant
      // vector transpose multiply needs access to v array
      int operator==(const vec& v1);
      int& operator[](int x);
      friend istream& operator>>(istream& s,vec& v);
      friend ostream& operator<<(ostream& s, vec& v);
}; //vector class

class vecpair;

class matrix {
   protected:
   // bam_matrix (a derived class) will need to use these members
   // preferred to "friend class", since there may be many derived
   // classes which need to use this
      int **m; // the matrix representation
      int r,c; // number of rows and columns
   public:
      // constructors
      matrix(int n=ROWS,int p=COLS);
      matrix(const vec& v1,const vec& v2);
      matrix(const vecpair& vp);
      matrix(matrix& m1); // copy-initializer
      ~matrix();
      int depth();
      int width();
      matrix& operator=(const matrix& m1);
      matrix& operator+(const matrix& m1);
      matrix& operator+=(const matrix& m1);
      vec colslice(int col);
      vec rowslice(int row);
      friend ostream& operator<<(ostream& s,matrix& m1);
}; // matrix class

class vecpair {
   friend class matrix;
   friend class bam_matrix;
   friend class bam_system;
      int flag; // flag signalling whether encoding succeeded
      vec a;
      vec b;
   public:
      vecpair(int n=ROWS,int p=COLS); // constructor
      vecpair(const vec& A,const vec& B);
      vecpair(const vecpair& AB); // copy initializer
      ~vecpair();
      vecpair& operator=(const vecpair& v1);
      int operator==(const vecpair& v1);
      friend istream& operator>>(istream& s,vecpair& v);
      friend ostream& operator<<(ostream& s,vecpair& v);
      friend matrix::matrix(const vecpair& vp);
};

class bam_matrix: public matrix {
   private:
      int K; // number of patterns stored in matrix
      vecpair *C; // actual pattern pairs stored
      int feedthru(const vec&A,vec& B);
      int sigmoid(int n); // sigmoid threshold function
   public:
      bam_matrix(int n=ROWS,int p=COLS);
      ~bam_matrix();
      // but we supply it with the actual matrix A|B (W is implied)
      void encode(const vecpair& AB); // self-ref version
      // uncode only necessary for BAM-system
      void uncode(const vecpair& AB); // self-ref version
      vecpair recall(const vec& A);
      int check();
      int check(const vecpair& AB);
      // Lyapunov energy function: E=-AWBtranspose
      int energy(const matrix& m1); // Lyapunov energy function
}; // BAM matrix

class bam_system {
      bam_matrix *W[MAXMATS];
      int M; // number of matrices
   public:
      bam_system(int M=1);
      ~bam_system();
      void encode(const vecpair& AB);
      vecpair& recall(const vec& A);
      // train equiv. to Simpson's encode of all pairs
      void train(char *patternfile);
      friend ostream& operator<<(ostream& s,bam_system& b);
}; // BAM system class

[LISTING TWO]



///////////////////////////////////////
// BAM.CPP Provide vector, matrix, vector pair, matrix, BAM matrix, and BAM
// system classes to implement BAM systems
// Extended note:
// This is an implementation of the concept of Bidirectional
// Associative Memories as developed by Bart Kosko and others.
// It includes the extended concept introduced by Patrick Simpson
// of the "BAM System". Where reasonable Simpson's notation has been
// been maintained. The presentation benefits greatly from C++ and OOP, in that
// (I believe) it is both easier to understand than a "pseudocode" version,
// yet more precise (in that it works!)
// Developed with Zortech C++ Version 2.0 -- Copyright (c) 1989,90 Adam Blum

#include"bam.hpp"

///////////////////////////////////
// vector class member functions

vec::vec(int size,int val) {
   v = new int[size];
   n=size;
   for(int i=0;i<n;i++)
      v[i]=0;
} // constructor
vec::~vec() { delete v;} // destructor
vec::vec(vec& v1) // copy-initializer
{
   v=new int[n=v1.n];
   for(int i=0;i<n;i++)
      v[i]=v1.v[i];
}
vec& vec::operator=(const vec& v1)
{
   delete v;
   v=new int[n=v1.n];
   for(int i=0;i<n;i++)
      v[i]=v1.v[i];
   return *this;
}
vec& vec::operator+(const vec& v1)
{
   vec sum(v1.n);
   sum.n=v1.n;
   for(int i=0;i<v1.n;i++)
      sum.v[i]=v1.v[i]+v[i];
   return sum;
}
vec& vec::operator+=(const vec& v1)
{
   for(int i=0;i<v1.n;i++)
      v[i]+=v1.v[i];
   return *this;
}
vec vec::operator*(int c)
{
   vec prod(length());
   for(int i=0;i<prod.n;i++)
      prod.v[i]=v[i]*c;
   return prod;
}
int vec::operator*(const vec& v1) // dot-product
{
   int sum=0;
   for(int i=0;i<min(n,v1.n);i++)
      sum+=(v1.v[i]*v[i]);
   //D(cout << "dot product " << *this << v1 << sum << "\n";)
   return sum;
}
int vec::operator==(const vec& v1)
{
   if(v1.n!=n)return 0;
   for(int i=0;i<min(n,v1.n);i++){
      if(v1.v[i]!=v[i]){
         return 0;
      }
   }
   return 1;
}
int& vec::operator[](int x)
{
   if(x<length() && x>=0)
      return v[x];
   else
      cout << "vec index out of range";
}
int vec::length(){return n;} // length method

istream& operator>>(istream& s,vec &v)
// format: list of ints followed by ','
{
   char c;
   v.n=0;
   v.v=new int[MAXVEC];
   for(;;){
      s>>c;
      if(s.eof())return s;
      if(c==',')return s;
      if(isspace(c))continue;
      v.v[v.n++]=((c!='0')?1:-1);
   }
}
ostream& operator<<(ostream& s, vec& v)
// format: list of ints followed by ','
{
   for(int i=0;i<v.n;i++)
      s << (v.v[i]<0?0:1);
   s << ",";
   return s;
}

///////////////////////////////
// matrix  member functions
matrix::matrix(int n,int p)
{
   //D(cout << "Constructing " << n << " x " << p << " matrix.\n";)
   m=new int *[n];
   for(int i=0;i<n;i++){
      m[i]=new int[p];
      for(int j=0;j<p;j++)
         m[i][j]=0;
   }
   r=n;
   c=p;
} // constructor
matrix::matrix(const vecpair& vp)
{
   //D(cout << "Constructing matrix from: " << vp;)
   r=vp.a.length();
   c=vp.b.length();
   m=new int *[r];
   for(int i=0;i<r;i++){
      m[i]=new int[c];
      for(int j=0;j<c;j++)
         m[i][j]=vp.a.v[i]*vp.b.v[j];
   }
}// constructor
matrix::matrix(const vec& v1,const vec& v2)
{
   //D(cout << "Constructing matrix from " << v1 << v2 << "\n";)
   r=v1.length();
   c=v2.length();
   m=new int *[r];
   for(int i=0;i<r;i++){
      m[i]=new int[c];
      for(int j=0;j<c;j++)
         m[i][j]=v1.v[i]*v2.v[j];
   }
}// constructor
matrix::matrix(matrix& m1) // copy-initializer
{
   //D(cout << "matrix copy-initializer\n"; )
   r=m1.r;
   c=m1.c;
   m=new int *[r];
   for(int i=0;i<r;i++){
      m[i]=new int[c];
      for(int j=0;j<c;j++)
         m[i][j]=m1.m[i][j];
   }
}
matrix::~matrix()
{
   for(int i=0;i<r;i++)
      delete m[i];
   delete m;
} // destructor
matrix& matrix::operator=(const matrix& m1)
{
   for(int i=0;i<r;i++)
      delete m[i];
   r=m1.r;
   c=m1.c;
   m=new int*[r];
   for(i=0;i<r;i++){
      m[i]=new int[c];
      for(int j=0;j<r;j++)
         m[i][j]=m1.m[i][j];
   }
   return *this;
}
matrix& matrix::operator+(const matrix& m1)
{
   matrix sum(r,c);
   for(int i=0;i<r;i++)
      for(int j=0;j<r;j++)
         sum.m[i][j]=m1.m[i][j]+m[i][j];
   return sum;
}
matrix& matrix::operator+=(const matrix& m1)
{
   //D(cout << "matrix additive assignment\n";)
   for(int i=0;i<r&&i<m1.r;i++)
      for(int j=0;j<c&&j<m1.c;j++)
         m[i][j]+=(m1.m[i][j]);
   return *this;
}
vec matrix::colslice(int col)
{
   vec temp(r);
   for(int i=0;i<r;i++)
      temp.v[i]=m[i][col];
   return temp;
}
vec matrix::rowslice(int row)
{
   vec temp(c);
   for(int i=0;i<c;i++)
      temp.v[i]=m[row][i];
   return temp;
}
int matrix::depth(){return r;}
int matrix::width(){return c;}

ostream& operator<<(ostream& s,matrix& m1)
// print a matrix
{
   for(int i=0;i<m1.r;i++){
      for(int j=0;j<m1.c;j++)
         s << m1.m[i][j] << " ";
      s << "\n";
   }
}
//////////////////////////////////////////
// vecpair  member functions
// constructor
vecpair::vecpair(int n,int p) { }
vecpair::vecpair(const vec& A,const vec& B) {a=A;b=B;}
vecpair::vecpair(const vecpair& AB) {*this=vecpair(AB.a,AB.b);}
vecpair::~vecpair() {} // destructor
vecpair& vecpair::operator=(const vecpair& v1)
{
   a=v1.a;
   b=v1.b;
   return *this;
}
int vecpair::operator==(const vecpair& v1)
{
   return    (a == v1.a) && (b == v1.b);
}
istream& operator>>(istream& s,vecpair& v1)
// input a vector pair
{
   s>>v1.a>>v1.b;
   return s;
}
ostream& operator<<(ostream& s,vecpair& v1)
// print a vector pair
{
   return s<<v1.a<<v1.b<<"\n";
}
/////////////////////////////////
//bam_matrix  member functions
bam_matrix::bam_matrix(int n,int p):(n,p)
{
   // the maximum number of pattern pairs storable
   // is around min(n,p) where n and p are
   // the dimensionality of the matrix
   C=new vecpair[min(n,p)*2];
   K=0;
}
bam_matrix::~bam_matrix()
{
} // destructor
void bam_matrix::encode(const vecpair& AB)
// encode a pattern pair
{
   //D(cout << "BAM Matrix encoding: " << AB;)
   matrix T(AB);
   (*this)+=T; // add the matrix transpose to the current matrix
   C[K]=AB;
   K++;
}
void bam_matrix::uncode(const vecpair& AB)
// get rid of a stored pattern (by encoding A-B complement)
{
   //D(cout << "uncode\n";)
   vec v=AB.b*-1;
   matrix T(AB.a,v); // T is A transpose B complement
   *this+=T;// add the matrix transpose to the current matrix
   K--;
}
vecpair bam_matrix::recall(const vec& A)
// BAM Matrix recall algorithm (used by BAM SYSTEM recall)
{
   int givenrow=(A.length()==width());
   D(cout<<"BAM matrix recall of" << A << givenrow?"(row)\n":"(col)\n";)
   vec B(givenrow?depth():width(),1);
   for(;;){ // feed vectors through matrix until "resonant" pattern-pair
      feedthru(A,B);
      if(feedthru(B,A))break; // stop when returned A = input A
   }
   D(cout<< "resonant pair " << A << "\n and " << B << "\n";)
   if(givenrow)
      return vecpair(B,A);
   else
      return vecpair(A,B);
}
int bam_matrix::feedthru(const vec&A,vec& B)
{
   //D(cout << "Feeding " << A << "\n"; )
   vec temp=B;int n;
   for(int i=0;i<B.length();i++){
      if(A.length()==width())
         n=sigmoid(A*rowslice(i));
      else
         n=sigmoid(A*colslice(i));
      if(n)
         B.v[i]=n;
   }
   return B==temp;
}
int bam_matrix::sigmoid(int n)
// VERY simple (but classic one for BAM) threshold function
//
//         1   --------------
//              |
//  - -----------      +
//        -1
{
   if(n<0)return -1;
   if(n>0)return 1;
   return 0;
}
int bam_matrix::check()
// check to see if we have successfully encoded pattern-pair into this matrix
{
   D(cout << "Check BAM matrix for " << K << " pattern pairs\n";)
   vecpair AB;
   for(int i=0;i<K;i++){
      AB=recall(C[i].a);
      if(!(AB==C[i])){
         D(cout <<"failed check\n ";)
         return 0;
      }
   }
   D(cout << "passed check\n ";)
   return 1;
}
int bam_matrix::check(const vecpair& AB)
{
   // different check routine for orthogonal construction BAM
   //check to see energy of present pattern pair to matrix
   // is equal to orthogonal BAM energy
   matrix T(AB);
   return energy(T)== -depth()*width();
}
int bam_matrix::energy(const matrix& m1)
{
   int sum=0;
   for(int i=0;i<depth();i++)
      for(int j=0;j<width();j++)
         sum+=(m1.m[i][j]*this->m[i][j]);
   D(cout << "Energy of matrix " << -sum << "\n";)
   return -sum;
}

///////////////////////////////////////////
// bam system  functions
// top level of system (for now)

// constructor
bam_system::bam_system(int n)
{
   M=n;
   for(int i=0;i<M;i++)
      W[i]=new bam_matrix;
}
bam_system::~bam_system() // destructor
{
   for(int i=0;i<M;i++)
      delete W[i];
}
void bam_system::encode(const vecpair& AB)
// encode the pattern pair AB into the BAOM system
{
   D(cout << "BAM System encode\n";)
   for(int h=0;h<M;h++){
      W[h]->encode(AB);
      if(!W[h]->check())
         W[h]->uncode(AB);
      else
         break;
   }
   if(h==M){ // all matrices full, add another
      if(h<MAXMATS){
         W[M]=new bam_matrix();
         W[M]->encode(AB);
         M++;
      }
      else{
         cout << "BAM System full\n";
         exit(1);
      }
   }
}
vecpair& bam_system::recall(const vec& A)
// presented with pattern A, recall will return pattern-PAIR
{
   vecpair XY[MAXMATS];matrix *M1,*M2;
   int E,minimum=0,emin=INT_MAX;
   D(cout << "BAM System recall\n";)
   for(int h=0;h<M;h++){
      XY[h]=W[h]->recall(A);
      D(cout << h <<"-th matrix, returned vecpair "<< XY[h];)
      M1=new matrix(XY[h]);
      E=W[h]->energy(*M1);
      if(A.length()==W[h]->width())
         M2=new matrix(XY[h].a,A);
      else
         M2=new matrix(A,XY[h].b);
      if (  ( E-(W[h]->depth()*W[h]->width()) < emin )
              && (E==W[h]->energy(*M2))
      )
      {
         emin=E-(W[h]->depth()*W[h]->width());
         minimum=h;
      }
      delete M1;
      delete M2;
   }
   return XY[minimum];
}
void bam_system::train(char *patternfile)
// A "multiple-pair" encode - which Simpson calls "encode"
// this could be used for initial BAM Sys training. However an up
// and running BAM Sys should only need to use "encode".
{
   FILE *f=fopen(patternfile,"r");int n=0;
   filebuf sfile(f);
   istream s(&sfile,0);
   vecpair AB;
   for(;;){
      s >> AB;
      if(s.eof())break;
      D(cout << "Encoding " << n++ << "-th pattern pair:\n" << AB;)
      encode(AB);
   }
   D(cout << "Completed training from " << patternfile;)
}
ostream& operator<<(ostream& s,bam_system& b)
// operator to print out contents of entire BAM system
{
   for(int i=0;i<b.M;i++)
      s<< "BAM Matrix " << i << ": \n" << *(b.W[i]) << "\n";
}

[LISTING THREE]



////////////////////////
// TESTBAM.HPP
// Interactive BAM System Demonstration Program. Used to verify BAM system
// algorithms and demonstrate them on an abstract (i.e. just 0s and 1s) case.
// Developed with Zortech C++ 2.0 -- Copyright (c) 1989,90 Adam Blum

#include"bam.hpp"

vec v;
vecpair AB;
bam_system B;
char *p;
char patternfile[16]="TEST.FIL"; // file where test data is stored
int trace=0; // SET TRACE=<whatever> at DOS prompt to turn trace on
main()
{
     cout << "Interactive BAM System Demonstration\n";
     trace=(p=getenv("TRACE"))?1:0;
     cout << "Training from " << patternfile << "\n";
     B.train(patternfile);
     D(cout << "Resulting BAM System\n" << B;)
     cout <<"Enter patterns as 0's and 1's terminated by comma.\n"
     <<"Patterns must be length of " << ROWS << " or " << COLS <<".\n"
     << "Null vector (just "","") to end.\n\n" ;
     for(;;){
          cout << "Enter pattern: ";
          cin >> v;
          if(!v.length())break;
          if(v.length()!=ROWS && v.length()!=COLS){
               cout << "Wrong length.\n";
               continue;
          }
          AB=B.recall(v);
          cout << "Recalled pattern pair\n" << AB;
     }
}

[LISTING FOUR]




1100101011010011,11101010,
0110110111110110,11010101,
1101111001010101,11110010,
1010101000010111,11001101,
0011001101011011,11110100,
1100101011010011,11101010,
0110100111110110,11010101,
1101110101010101,11110010,
1011101010010111,11001101,
0001011101011011,11110100,
1100101001010011,11101010,
0110110110110110,11010101,
1100111011010101,11110011,
1010000100010111,11001101,
0001101101011011,11110110,
1100100011010011,11100110,
0110110011110110,11010101,
1101111001010101,11110011,
1010100000011111,11001101,
0001100101111011,11111000,
1100101011010011,11011010,
0010100111110110,11010101,
1101111101010101,11110010,
1010111000010111,11101101,
0001000001011011,11110100,
1100101011010011,11101010,
0110110111110110,11010101,
1101111000010101,11110110,
1010100111010111,11001101,
0001000101011011,11110100,
0110110101110110,11010111,
1101111001010101,11110110,
1010111100110111,11001101,
0001000101011011,11110100,
1100101010010011,11101010,
0110110111110110,11010101,
1101111001010101,11110010,
1010110000010111,11001101,
0011000101011011,11110100,
0011010101111011,10010111,

[LISTING FIVE]



# TESTBAM.MK
# Make file for BAM System implementation tester
# Uses Microsoft Make
# Compiler: Zortech C++ 2.0
# To make with diagnostics enabled:
# make CFLAGS="-DDEBUG=1" testbam.mk
#

CFLAGS=
.cpp.obj:
     ztc -c $(CFLAGS) $*.cpp
bam.obj: bam.cpp bam.hpp
testbam.obj: testbam.cpp bam.hpp
testbam.exe: testbam.obj bam.obj
     blink testbam bam;