genmultscript.cpp

產生你所需要的FIR濾波器

///////////////////////////////////////////////////////////////
// Automatic Multiplier Generator Tool                       //
// convert signed multiplication to script                   //
// using Nonrecursive Signed Common Subexpression Algorithm  //
///////////////////////////////////////////////////////////////
//
// Writer      : Boris Kipnis
// Last Update : 5/5/2005
//

#include "GenMultScript.h"

#define GMULT_MIN_OPTIMIZE 0
#define GMULT_TAB_OFFSET 0

////////////////////////////////////////////
// PRINT FUNCTIONS                        //
// Visualization functions for debugging  //
////////////////////////////////////////////
void GenMultScript::printArray(vector<int> ar) {
  for (int j=0;j<ar.size();j++) {
      printf("%d,",ar[j]);
  }
  printf("\r\n");
}
// Show Dual array a line, b line
void  GenMultScript::printDualArray(vector<inta_intb_s> ar) {
  for (int j=0;j<ar.size();j++) {
      printf("%d,",ar[j].a);
  }
  printf("\r\n");
  for (int j=0;j<ar.size();j++) {
      printf("%d,",ar[j].b);
  }
  printf("\r\n");
}
// Show position Array X,Y
void  GenMultScript::printPosArray(vector<pos_s> ar) {
  for (int j=0;j<ar.size();j++) {
    printf("%d,%d : ",ar[j].x,ar[j].y);
  }
  printf("\r\n");
}

void  printMultScript(vector<mult_s> ar) {
  int i;
  if (ar.size()==0) printf("0");
  for (i=0;i<ar.size();i++) {
    switch((ar[i]).type) {
	   case TERMT_PP : printf("+Term%d<<%d",(ar[i]).termNum,(ar[i]).shift);  break;
	   case TERMT_MM : printf("-Term%d<<%d",(ar[i]).termNum,(ar[i]).shift);  break;
	   case TERMT_PM : printf("+Term%d<<%d",(ar[i]).termNum,(ar[i]).shift);  break;
	   case TERMT_MP : printf("-Term%d<<%d",(ar[i]).termNum,(ar[i]).shift);  break;
	   case SIG_P    : printf("+In<<%d",(ar[i]).shift);  break;
	   case SIG_M    : printf("-In<<%d",(ar[i]).shift);  break;
       case TEMP_P   : printf("+Temp%d<<%d",(ar[i]).termNum,(ar[i]).shift); break;
       case TEMP_M   : printf("-Temp%d<<%d",(ar[i]).termNum,(ar[i]).shift); break;
       default       : printf("Unknown, "); break;
    }
  }
  printf("\r\n");
}

////////////////////////////////////////
// Convert Integer to Binary String   //
////////////////////////////////////////
string  GenMultScript::int2binStr(int num, const int size) {
  int i;
  string str;
  char *str_c;
 
  for (i=0;i<size;i++) {

    if (num & 0x01) {
       str = '1' + str;
    } else {
       str = '0' + str;
    }

    num = num >> 1;
  }
  return(str);
}

/////////////////////////////////////////////////
// Convert Integer to base (3x) I multArraySingleTermnteger Array  //
// 0101 = [0,1,-1,1-1]                         //
/////////////////////////////////////////////////
vector<int>  GenMultScript::int23x(int num,int size) {
  string str;
  vector<int> ar;
  string sym_char;
  int  sym;
  int i;
  int numAbs;

  // Limit LOWER Size to avoid calculation errors
  if (size<2) size = 2;

  // Calculate binary representation for Integer value
  numAbs = abs(num);              // convert to positive
  str = int2binStr(numAbs,size);  // convert to binary

  printf("%d binary = %s =>",num,str.c_str());

  //////////////////////////////////////////////
  // Convert Binary to 3x representation
  str='0'+str+'0';
  size=str.size();
  
  ar.clear();
  for (i=0;i<size-1;i++) {

      sym_char = str[i];
      sym_char += str[i+1];

      if      (!sym_char.compare("00")) sym = 0;
      else if (!sym_char.compare("11")) sym = 0;
      else if (!sym_char.compare("01")) sym = 1;
      else if (!sym_char.compare("10")) sym =-1;
      else                              sym = 0;

      // check for negative number
      if (num<0) sym = sym * (-1);

      // push to array
      ar.push_back(sym);
  }
 
  return(ar);
}

// convert 3x to integer
int  GenMultScript::convert_3x_2int(vector<int> num) {
	int i,res;
	
	res=0;
	for (i=0;i<num.size();i++) {
   	    res = res <<1;
		if (num[i]>0) res+=1;
		if (num[i]<0) res-=1;
	}
	return(res);
}


/////////////////////////////////////////////////////////////////////////////////////////
// Calculate Number of cases for selected distance                                     //
/////////////////////////////////////////////////////////////////////////////////////////
int  GenMultScript::calcSingleDistance(vector<int> ar3x,int dist,int type) {
  int i;
  int numOfBits;
  vector<int> ar3xTemp;
  int count;

  numOfBits = ar3x.size();
  ar3xTemp  = ar3x;

  count = 0;
  for (i=0;i<(numOfBits-dist-1);i++) {
      
      if ( ( ( ( (ar3xTemp[i]==  1 )&&(ar3xTemp[i+dist+1]==  1 ) ) ||
	       ( (ar3xTemp[i]==(-1))&&(ar3xTemp[i+dist+1]==(-1)) ) ) &&
	         (type==DIST_PP_MM)) ||
	   ( ( ( (ar3xTemp[i]==(-1) )&&(ar3xTemp[i+dist+1]==  1 ) ) ||
	       ( (ar3xTemp[i]==  1  )&&(ar3xTemp[i+dist+1]==(-1)) ) ) &&
                 (type==DIST_PM_MP)) ) {
	////////////////////////////////////////////////////
	ar3xTemp[i]=0; // Erase Current
	ar3xTemp[i+dist+1]=0;
	count++; // Increment counter
      }   
  }
  return(count);
}

//////////////////////////////////////////////////////////////
//               Calculate distances array                  //
//////////////////////////////////////////////////////////////
vector<int>  GenMultScript::calcDistance(vector<int> ar3x,int type) {
  int dist,numOfBits,count;
  vector<int> ar;

  numOfBits = ar3x.size();
  ar.clear();
 
  /////////////////////////////////////////
  // scan distance scan
  for (dist=0;dist<numOfBits-1;dist++) {
    count = calcSingleDistance(ar3x,dist,type);
    ar.push_back(count);
    //printf("Dist=%d Count=%d\r\n",dist,count);      
  }

  return(ar);
}

///////////////////////////////////////////////////////////
//            calculate distances array (dual)           //
///////////////////////////////////////////////////////////
vector<inta_intb_s>  GenMultScript::calcDistance(vector<int> ar3x) {
  int dist,numOfBits;
  vector<inta_intb_s> ar;
  inta_intb_s count;

  numOfBits = ar3x.size();
  ar.clear();
 
  /////////////////////////////////////////
  // scan distance scan
  for (dist=0;dist<numOfBits-1;dist++) {
    count.a = calcSingleDistance(ar3x,dist,DIST_PP_MM);
    count.b = calcSingleDistance(ar3x,dist,DIST_PM_MP);
    ar.push_back(count);
  }

  return(ar);
}

/////////////////////////////////////////////////////////////////
//             Calculate Distances Array/Array                 //
/////////////////////////////////////////////////////////////////
vector<vector<inta_intb_s> >  GenMultScript::calcDistanceArray(vector<vector<int> > ar3x) {
  int i;
  vector<int> b3x;
  vector<vector<inta_intb_s> > ar_dist;

  ar_dist.clear();
  for (i=0;i<ar3x.size();i++) {
    b3x = ar3x[i];
    ar_dist.push_back(calcDistance(b3x));

    //printf("\r\n");
    //printDualArray(ar_dist[i]);
  }
  return(ar_dist);
}

/////////////////////////////////////////////////////////////////
//        Find and Delete single distance from array           //
/////////////////////////////////////////////////////////////////
vector<int>  GenMultScript::deleteDistanceSingle(vector<int> ar_i,int dist,int type) {
  int i,numOfBits;
  vector<int> ar;

  numOfBits = ar_i.size();
  ar  = ar_i;

  for (i=0;i<(numOfBits-dist-1);i++) {
      
      if ( ( ( ( (ar[i]==  1 )&&(ar[i+dist+1]==  1 ) ) ||
	       ( (ar[i]==(-1))&&(ar[i+dist+1]==(-1)) ) ) &&
	         (type==DIST_PP_MM)) ||
	   ( ( ( (ar[i]==(-1) )&&(ar[i+dist+1]==  1 ) ) ||
	       ( (ar[i]==  1  )&&(ar[i+dist+1]==(-1)) ) ) &&
                 (type==DIST_PM_MP)) ) {
	////////////////////////////////////////////////////
	ar[i]=0; // Erase Current
	ar[i+dist+1]=0;
      }   
  }
  return(ar);
}

//////////////////////////////////////////////////////////////////////////
//                     Delete Distances Array                           //
//////////////////////////////////////////////////////////////////////////
vector<vector<int> >  GenMultScript::deleteDistance(vector<vector<int> > ar_i,int dist,int type) {
  vector<vector<int> > ar;
  int i;

  ar.clear();
  for (i=0;i<(ar_i).size();i++) {
    ar.push_back(deleteDistanceSingle(ar_i[i],dist,type));
  }
  return(ar);
}


//////////////////////////////////////////////////////////////////////
//                  Calculate global distance                       //
//              (add all single distances together)                 //
//////////////////////////////////////////////////////////////////////
vector<inta_intb_s>  GenMultScript::calcGlobalDistance(vector<vector<inta_intb_s> > l_dist) {
  int i,j;
  vector<inta_intb_s> g_dist;

  g_dist=l_dist[0];

  for (i=1;i<(l_dist).size();i++) {

    // Add current to previous
    for (j=0;j<(l_dist[i]).size();j++) {
      g_dist[j].a+=(l_dist[i])[j].a;
      g_dist[j].b+=(l_dist[i])[j].b;
    }
  }

  printf("\r\n");
  printDualArray(g_dist);

  return(g_dist);
}

/////////////////////////////////////////////////////////////////////////
//           Find Maximum Value and their location in array            //
/////////////////////////////////////////////////////////////////////////
max_s  GenMultScript::findMax(vector<inta_intb_s> ar) {
  max_s p;
  int x,max;
  max=0;
  for (x=GMULT_TAB_OFFSET;x<ar.size();x++) {
    if (ar[x].a>=max) {
      max = ar[x].a;
      p.max = max;
      p.pos.x=x;
      p.pos.y=0;
    }
    if (ar[x].b>=max) {
      max = ar[x].b;
      p.max = max;
      p.pos.x=x;
      p.pos.y=1;
    }
  }
  return(p);
}

///////////////////////////////////////////////////
//               Find Common Terms               //
///////////////////////////////////////////////////
vector<pos_s>  GenMultScript::getCommonTerms(vector<vector<int> > ar3x) {
  vector<vector<inta_intb_s> > l_dist;
  vector<inta_intb_s> g_dist;
  vector<vector<int> > ar3xTemp;
  max_s m;
  vector<pos_s> term;
  
  ar3xTemp = ar3x;
  term.clear();

  do {
    l_dist = calcDistanceArray(ar3xTemp);  // Calculate Distances Array
    g_dist = calcGlobalDistance(l_dist);   // calculate global distance array
    m = findMax(g_dist);                   // look for maximum

    if (m.max>GMULT_MIN_OPTIMIZE) {
      ar3xTemp = deleteDistance(ar3xTemp,m.pos.x,m.pos.y);
      term.push_back(m.pos);
    }
  } while(m.max>GMULT_MIN_OPTIMIZE);

  printf("\r\nTerm Array:\r\n");
  printPosArray(term);

  return(term);
}

/////////////////////////////////////////////////////
// Get Other feild left after extract common terms //
/////////////////////////////////////////////////////
vector<vector<int> >  GenMultScript::getOthers(vector<vector<int> > ar3x,vector<pos_s> Term) {
  vector<vector<int> > ar3xTemp;
  int i;

  ar3xTemp = ar3x;
 
  for (i=0;i<Term.size();i++) {
    ar3xTemp = deleteDistance(ar3xTemp,(Term[i]).x,(Term[i]).y);
  }

  printf("\r\nOthers:\r\n");