The solution outlined below is appropriate for a PC-based based solution
with little constraint on available memory for data and code. It is designed
to be as fast as possible.

It makes extensive use of the preprocessor to do as much work as possible at
compile time.

I would estimate this will take less than 10 microseconds on a 1GHz PC.

// The following array can be indexed by any
// 9-bit number from 0 thru 511 to return the
// number of one bits set in that number:

int    bit_count[512] = {
   0,        // 0 = 000 000 000 binary
   1,        // 1 = 000 000 001 binary
   1,        // 2 = 000 000 010 binary
   2,        // 3 = 000 000 011 binary
   1,        // 4 = 000 000 100 binary
   2,        // 5 = 000 000 101 binary
   2,        // 6 = 000 000 110 binary
   3,        // 7 = 000 000 111 binary
   .....
   8,        // 510 = 111 111 110 binary
   9        //  511 = 111 111 111 binary
};

// The following macros define the bits of the M sequence

#define M1    1
#define M2    1
#define M3    0
#define M4    1
...
#define M511 0

// Define a macro to combine 9 bits of M into a
// single 9-bit mask value

#define MASK(a,b,c,d,e,f,g,h,i)
    ( (a) << 8 ) | ((b) << 7) | ((c) << 6) | ((d) << 5) |         \
    ( (e) << 4 ) | ((f) << 3) | ((g) << 2 ) | ((h) << 1) | (i)

// Define values for each 9 bit consecutive group of bits in the M sequence

#define M_1_9 MASK(M1,M2,M3,M4,M5,M6,M7,M8,M9)
#define M_2_10 MASK(M2,M3,M4,M5,M6,M7,M8,M9,M10)
....
#define M_503_511 MASK(M503,M504,M505,M506,    \
            M507,M508,M509,M510,M511)

    int    S;                    // the sequence S expressed as a 9 bit
binary value

// Set  best to the number of matching bits when comparing S to the
// first 9 bits of M (ie: compute A0).
// Remember where we found this 'best' value.

    int    best = bit_count[ S ^ M_1_9 ];
    int    bestpos = 0;

// Now, for each possible offset into the M-stream compute
// the number of matching bits and see if it is better than the best
// we have so far. If it is, remember the new best value and where we
// found it.

    if ( bit_count[ S ^ M_2_10 ] > best )
    {
        best = bit_count[ S ^ M_2_10 ];
        bestpos = 1;
    }

    if ( bit_count[ S ^ M_3_10 ] > best )
    {
        best = bit_count[ S ^ M_3_10 ];
        bestpos = 2;
    }
    ....

    if ( bit_count[ S ^ M_503_511 ] )
    {
        best = bit_count[ S ^ M_502_511 ];
        bestpos = 501;
    }

> >----- Original Message -----
> >From: "ali dawji" <ali_dawji@HOTMAIL.COM>
> >To: <PICLIST@MITVMA.MIT.EDU>
> >Sent: Monday, April 29, 2002 5:14 AM
> >Subject: M and S sequences
> >
> >
> > > Dear Sir
> > > I have a question and I hope if you can answer me.
> > >
> > > I have tow one dimensional sequence or matrix.,
> > > The first sequence is called M with length 511 number:
> > > M[511]={ 1, 1, 1, 1, 1, 1, 1,-1,-1,1,1,-1,-1,1,-1,-1,-1,1?????..};
> > > And the second sequence is called with nine numbers
> > > S [9] = {1, 1, 1,-1,-1, 1,-1,-1,-1};
> > >
> > > I want to
> > > 1- Multiplied the sequences S with first ninth number of the sequence
M,
> >and
> > > keep the result as A0,
> > > 2- The multiplication procedure as flows
> > > The first number of M * the first number of S, if the answer is
negative
> >=>
> > > (-1), and if the answer is positive => 1
> > > Example:
> > > M= {1, 1, 1, 1, 1, 1, 1,-1,-1};   /*(first ninth number of M
sequence)*/
> > > S= {1, 1, 1,-1,-1, 1,-1,-1,-1};
> > > 1*1=1
> > > 1*1=1
> > > 1*1=1
> > > 1*-1=-1
> > > 1*-1=-1
> > > 1*1=1
> > > 1*-1=-1
> > > -1*-1=1
> > > -1*-1=1
> > > The answer is 3= (6*1- (3*-1))
> > > 3-shift the sequence M on number to the right and multiplied the
> >sequence
> >S
> > > by the M sequence (from number 2-10). And keep the multiplication
result
> >in
> > > A1,
> > > repeat the procedure of the multiplication till  the end of the
sequence
> >M.
> > > 4- Calculate the maximum value multiplication result A0, A1, A2?
> > >
> > >
> > > sorry since my language is not so good
> > > thank you
> > >
> > >
> > >
> > > _________________________________________________________________
> > > Join the world s largest e-mail service with MSN Hotmail.
> > > http://www.hotmail.com
> > >
> > > --
> > > http://www.piclist.com hint: The PICList is archived three different
> > > ways.  See http://www.piclist.com/#archives for details.
> > >
> > >
> >
> >--
> >http://www.piclist.com hint: The PICList is archived three different
> >ways.  See http://www.piclist.com/#archives for details.
> >
> >
>
>
>
>
>
>
> _________________________________________________________________
> Get your FREE download of MSN Explorer at
http://explorer.msn.com/intl.asp.
>
> --
> http://www.piclist.com hint: The PICList is archived three different
> ways.  See http://www.piclist.com/#archives for details.
>
>

--
http://www.piclist.com hint: The PICList is archived three different
ways.  See http://www.piclist.com/#archives for details.