On Wed, 17 May 2000, Bennett, Matt wrote:

> I'm looking for some code that will perform a correlation on a PIC (or an
> AVR), and if that fails, some ideas or advice on how to code it.  Here's the
> basic idea of what I'm trying to do:  I have a stream of serial data (SD)
> (252 bits) that I have collected and placed in memory.  I want to correlate
> a portion of this stream with a pseudo noise (PN) sequence (126 bits long),
> and determine where in the stream the correlation has the best match- this
> is done by XNORing the two streams and counting up the 1's.  I need to do
> this at every possible delay where I can fit the PN sequence in the serial
> data (bits 1-126 of SD with bits 1-126 of PN, bits 2-127 of SD with bits
> 1-126 of PN, ... , bits 127-252 of SD with bits 1-126 of PN)

Matt,

There are probably a number of ways to attack this. If your serial data has
already been acquired and is sitting in a buffer then it make most sense to
perform the autocorrelation between bits 1-126 of the serial data, then 9-134,
then n*8+1 through n*8+126 for n=16 (or n=32 and truncate the processing when
the last bit of the serial data has been encountered). After those n passes,
shift the serial data stream one position and repeat the process. Repeat this
for a total of 8 times. This looping method saves you the trouble of shifting
all 252 bits of the serial data stream for each pass through the algorithm.

Now, as far as counting bits in a byte, I've got four really bad examples on my
web page. They're bad because the best one takes 16-cycles and Dmitry has posted
a solution that takes 11 or 12 cycles (IIRC).

As far as organizing the data, I suggest a linear array and indirect addressing.
The 18cxxx has a very good indirect address scheme (especially when compared to
the mid range pics). So you can do something like:


    ;; indf0 points to the Serial Data
    ;; indf1 points to the PN stream

loop:
    comf   postinc0,w   ;Get the next byte in the serial data stream
    xorwf  postinc1,w   ;XNOR with the PN stream

    COUNTBITS ...       ;autocorrelate

    decfsz loopcounter,f
     goto  loop


The other approach to take is to process the bits as they're being received (I'm
assuming bit banging and not using the usart). In this scheme, you'll only need
to autocorrelate the most recent 126 bits. The caveat is that you'll have to
perform 16 RRF's in addition to one full 126-bit autocorrelation in the time it
takes to receive one bit. I estimate about 300 cycles to perform this
operation. This would take 30uS on an 18cxxx with a 10Mhz crystal. Thus the
fastest bit stream would be limited to about 33kbits/sec.

A possible speed up for the bit counting algorithm would be to take advantage of
the enormous program memory space of the 18cxxx and to create a 256 byte table
whose entries contain the number of bits for the index (e.g. bit_count[i] = sum
of bits in `i'). If the table is aligned on a 256 byte boundary, then the table
read instruction could efficiently obtain the number of bits. This speed up
reduces the above estimate to about 100 cycles or 10uS or 100kbits/sec.

Note, even if you are using the uart, it still be possible to process the data
as it is being received. The only difference is that you'd be taking the bits
one at a time from the uart receive register instead of from the bit-banged
serial line.

>
> I've been attaching this problem with an AVR (4414), since I have a test
> board handy, and it has some very convenient features for some other parts
> of the program, but I also have some brand new 18CXXX's that were just
> sampled to me., so if you happen to have PIC or AVR code you would be
> willing to share, I'm willing to trade it for a cool, refreshing beverage
> the next time you happen to be in Austin.

I'm in Austin already. I was going to go to the seminar tomorrow (the 18'th) -
but I ain't got the time.

Scott