Generating the 10 bit CRC, for the 16 bit data 'block' (4 needed per frame) for

m.r.b. · 2010-05-24 11:59

I am building a low power FM stereo TX, with RDS functionality

(for getting an MP3 player to connect to a car stereo, with, in the longer term, the track name displayed on the car stereo display, but for the·initially, for testing·a static PS {program service} name " * IPOD * "!· !!)

I'm quite confused by Cyclic Redundancy Checks...· Something I really should learn more about!!!

Could someone help me out with the (spin) code to return the 10 bit CRC, for·a 16 bit data 'block' used within the Radio Data system.
{4 'blocks' are required to form a 'frame' of 104 bytes, to properly display the PS name}

I know pretty much everything else about the baseband coding structure, and also the modulation scheme, but I am stumped by the CRC part of this.... I know what the polynomial is, but I dont know if its byte reversed or not, and whether to set the default state of the CRC to $0000 or $ffff etc)

Any ideas??

·

pullmoll · 2010-05-24 14:30

I would just try the 4 possible ways: LSB first or MSB first and init with all 0s or all 1s. If you have the polynome, calculating the XOR value for the CRC should be easy enough.

Look at what I found in the top rank of googling "rds crc": http://www.ee.ucl.ac.uk/~hamed/docs/final report.pdf
In there is a clear description on how to do the CRC on a microcontroller.
1. Load the register with zero bits.
2. Augment the message by appending W zero bits to the end of it.
while (more message bits)
begin
3. Shift the register left by one bit, reading the next bit of the augmented message into register bit position 0.
if (a 1 bit popped out of the register during step 3)
register = register XOR Poly.
End.

I think that's pretty clear, or is it?

VAR
    long          length
    long          my_crc
    byte          message[noparse][[/noparse]128]                             ' for example

PUB start
    msg_data_base := @message                              ' set the address of the message buffer
    msg_length_ptr := @length                              ' set the address of the message length long
    crc_ptr := @my_crc                                     ' result goes here
    cognew(@crc10, 0)

PUB do_crc10(data,count)
    bytemove(@message, data, count)
    length := count
    repeat while length <> 0
    return my_crc

PUB do_crc10_16bit(value)
    message[noparse][[/noparse] 0] := value & 255
    message[noparse][[/noparse] 1] := value >> 8
    length := 2
    repeat while length <> 0
    return my_crc

DAT
                org  0
crc10
:wait
                rdlong bytecount, msg_length_ptr  wz       ' wait for a message
          if_z  jmp    #:wait                              ' with a non-zero length
                mov    msg_data_ptr, msg_data_base
                mov    crc, #0
:loop
                rdbyte data, msg_data_ptr
                mov    bitcount, #8
:bits           test   data, #$80              wc          ' get bit 7 of data into carry
                rcl    crc, #1                             ' rotate into CRC
                test   crc, bit10              wz          ' test if a 1 bit popped out
          if_nz xor    crc, poly
                shl    data, #1                            ' next bit
                djnz   bitcount, #:bits
                add    msg_data_ptr, #1                     ' next message byte
                djnz   bytecount, #:loop                   ' until message done
                and    crc, mask10                         ' mask 10 bits
                wrlong crc, crc_ptr
                mov    data, #0
                wrlong data, msg_length_ptr                ' set length to 0 to indicate we're done
                jmp    #:wait

poly            long   $05b9                               ' taken from sample program
bit10           long   1<<10
mask10          long   (1<<10)-1
msg_length_ptr  long   0-0
msg_data_base   long   0-0
crc_ptr         long   0-0

crc             res    1
bytecount       res    1
bitcount        res    1
msg_data_ptr    res    1
data            res    1

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Pullmoll's Propeller Projects

Post Edited (pullmoll) : 5/24/2010 3:03:57 PM GMT

JonnyMac · 2010-05-24 20:20

You can caculate the CRC10 value in Spin, too. Thanks to pullmoll's description and demo code I was able to easily translate to Spin:

pub crc10(pntr, n) | tmpcrc, dbyte

  tmpcrc~ 

  repeat (n #> 0)
    dbyte := byte[noparse][[/noparse]pntr++]
    repeat 8
      tmpcrc := (tmpcrc << 1) | ((dbyte & $80) >> 7)
      if (tmpcrc & |<10)
        tmpcrc ^= POLY
      dbyte <<= 1

  return tmpcrc & $03FF

I tested this routine against pullmoll's assembly version and got the same result from each test. That said... you'll pay the price in speed. I measured the number of clock ticks like this:

' check JM's version

  t0 := cnt 
  c := crc10(@Test2, 10)
  tdelta := (||(cnt - t0) - 368) #> 0

... and found that the Spin version took 313_520 clock ticks (3.9ms), while the assembly version took only 6_032 (75.4us) for the same, 10-byte packet. You may need to take this into consideration, depending on the size of your message packets.

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Jon McPhalen
Hollywood, CA

m.r.b. · 2010-05-26 11:57

Thanks, it has taken a lot of the mystery/confusion out of CRC generation...· although, I allways though it was a 'black art'!!!

Initially, the SPIN version will be fast enough (Well, at least until I start using a dynamic PS name, later on ...), because·in reality, you only need·to calculate the CRC once for each of the four 'blocks' that makes up the entire data frame.

.... This is·assuming the message data doesnt change (it wont if I stick to a static PS name for initial testing, for·now..)

However, when I start using dynamic (scrolling PS names) at some later time, I will·possibly either use·the ASM code, or use 'double buffered' data (which I only update when I'm ready), and stick to the slower SPIN crc10 method

Because the packet size per block, is allways a fixed width 16 bit message, I've trimmed out the code for counting through multiple pointer referenced message bytes, giving me this even simpler code, for initial testing with static PS name:-

[noparse][[/noparse]code]

pub crc10(blockdata) | tmpcrc
· tmpcrc~

· 'Radio Data System CRC Polynomial G(x) = x^10 + x^8 + x^7 + x^5 + x^4 + x^3 + 1
· 'Polynomial value =· $05b9

· 'Block data is fixed width, 16 bits, so have dispensed with counting through multiple pointer referenced bytes...

·· repeat 16 '16·bits fixed width packet
···· tmpcrc := (tmpcrc << 1) | ((blockdata & $8000) >> 15)
···· if (tmpcrc & |<10)
······ tmpcrc ^= $05b9
···· blockdata <<= 1

· return tmpcrc & $03FF

[noparse][[/noparse]/code]

regards M.R.B.

B.T.W. Sorry for the confusion, there was a typo in my original post, it should have read:-

{4 'blocks' are required to form a 'frame' of 104 bits, to properly display the PS name}

Generating the 10 bit CRC, for the 16 bit data 'block' (4 needed per frame) for

Comments