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 © 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) 1) ? (a) : (b)) #define min(a,b) 2) ? (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 © 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 © 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;