Teensy CRC Generator/Checker

Status
Not open for further replies.
@FrankB: Excellent news with 0x18,0x18,0x18 and the result 0x01D5. I don't have another verified (longhand) test string yet, but will make one later (busy all day today).

The naming should reflect the ITU document ITU-R M589 Part 3, which mentions Loran/Chayka (where the poly is defined). Perhaps FastCRC::eLOR ? It is eLoran that has the radio data channel and differs it from standard Loran.

If you update the zip today, I will download tonight and give it a test. I have lots of other data from the radio experiment in my "needles in haystack" search, so it should find something very quickly.


Ok, I have added it as "eloran" (not documented so far) - please test it, when you have time :)
crc = CRC14.eloran(buf, sizeof(buf));

Please download the new version.
 
Frank, Pete

Using a T3.5, I made a test of CRC14.eloran just now and it worked brilliantly. The 56 bit test data was... uint8_t buf[] = {0xAA,0xAA,0xAA,0xAA,0xAA,0xAA,0xAA}; and this gave the correct result of "0x19D6".

I performed this calculation longhand prior to the test, just to be sure of the true CRC value. I also tested Pete's software (edited as I described previous) and that also gave the same result - so all three methods are in agreement.

I shall now proceed to hunt for my "needles in the haystack". I'll do a timing test too, just to know how fast this works in real time at 180 MHz clock speed.
 
Timing of FastCRC... on my scope, it took 3.4 uSec to perform the CRC14.eloran call plus one DigitalWriteFast statement. That's a T3.5 running @180 MHz (and a very precise 180 MHz I might add, since the Teensy FTM1 timer clock is phase locked to LORAN 100 KHz :D). The DigitalWriteFast is going to be minimal time.

I was reading tonight that there was an eLoran transmitter trial started in 2015 in Wildwood, N.J. I'm asking around to see if it is still running. Are you in the states Pete? You might be able to receive it... also, a research contract has also been let recently in South Korea.
 
I've been trying to get FastCrc to handle the 14-bit FT4 CRC with no luck so far. I've added this to FastCRChw.cpp:
Code:
uint16_t FastCRC14::ft4(const uint8_t *data,const uint16_t datalen)
{
  return generic(0x2757, 0x0000, CRC_FLAG_NOREFLECT, data, datalen);
}

and used this code to test it:
Code:
#include <FastCRC.h>

FastCRC14 CRC14;

uint8_t t1[12];

uint16_t get_crc(uint8_t *c1,uint8_t *t1)
{
  int i,j;
  uint8_t bits;
  uint16_t b_crc;

  // Extract the 77-bit message
  for(i = 0;i < 10;i++) {
    bits = 0;
    for(j = 0;j < 8;j++) {
      // Have we processed the 77th bit?
      if(i == 9 && j == 5)break;
      bits <<= 1;
      if(c1[i*8+j] == '1')bits |= 1;
    }
    t1[i] = bits;
  }

  t1[9] = bits << 3;
  t1[10] = 0;
  t1[11] = 0;

  // The next 14 bits are the CRC
  b_crc = 0;
  for(i = 0;i < 14;i++) {
    b_crc <<= 1;
    if(c1[i+77] == '1')b_crc |= 1;
  }
  return b_crc;
}

void test_crc(const char *c)
{
  uint16_t b_crc;
  int i;

  // Extract the message and the CRC
  b_crc = get_crc((uint8_t *)c,t1);
  Serial.printf("crc14 = 0x%04X, b_crc = 0x%04X\n",CRC14.ft4(t1,10),b_crc);
}

void setup() {
 uint32_t crc;
 Serial.begin(9600);
 while(!Serial);
  delay(1000);


  char *p = &__FILE__[strlen(__FILE__)-1];
  while(*p != '\\' && p >= __FILE__[0])*p--;
  p++;
  Serial.print("FILE = ");
  Serial.println(p);

const char *c_bits[] = {
  "010011000100101010110000110100000111001010011011011101000101001001100111101101000101110111010010000101001011100111111101000011101000101100101010110011111000001101000010000111",
  "010011110111011001001100101001001110001001100001001011111111001001100101101101011110111101011001010001100011100101110110110011000011110100011011001010011101111001110111101010",
  "001110100010110101011101100101001111111001100100000001001000001001100101111100100110010110110111101011011110000000110110001101000010111010110100100000010110011100101000011101",
  "000010101011010100101011000100000000011101001101110011001000001001100101101101111001010000010010001001110111111010100110111100010011111010100000101110001111111111110000000011",
  "010010100101111011010111110101001110001100110011011011101101110111101001111000000011101100110111100010001111101100101100101111010111011101101010110101101001001011000101001010",
  "010011101000000101000100011110111000100001100110101111001100101001101100101100101101110101011100111011010010111011110000100010111001010101110101000010100110001110000100100100",
  "010010100101111011010111110101100010001101011000001010000101110110001001001000100111010000111100010100000000000101101111001010110100000001110000101101111110111001001011000110", //???
  "000000001010010000100101111110000001111011011111111111100001101001101011011100100000010011001010001110001101111011100011100001101011010001000011110111000001000101010100000110",
  "101011011100101101000100001100000110000001010111010101011100101000011011001000010111000111100011110000001111100100101111110110001011101100011100000000100000001100001111000100",
  "010001100100010100101011110100000000110000101111111101100100101000100011011000000101011000010011110111011000101010101000110011010100100101101110011110010111110101101011011000", //???
  "000111111000110001010001100111001101000001101010011001100111001001101110111101101000000001111110110111111011010011010111101110110011010010100111010001110100011101000111000001",
  "010000111001000100010010111000111011011111001100010001101100101000100011011001101011000101010010000001001100000011011000010110001011001101110111110010000100100100011100110000",
  "010010100101111011010111110100111110001000000011000010010101110001000100011000111111100111101011000001110110101101000101011010110110110111000011001010111100101000110111010101",
  "010011000100101010110000110100000111001010011011011101000101001001100111101101000101110111010010000101001011100111111101000011101000101100101010110011111000001101000010000111",
  "010000000000111100000011100100000000000000111000100111011100101000100011011000001000011000110000110110010001110011101110111010011000110101111101010010100101100000100001111111",
  "000111010011000000001011100010111000011101101011001011101110001001101111011100010011000110001000000001010010101001101111111100111101101010110111101101101010111110000101111011", //???
  "010010100101111011010111110101001101000010000001011111101101111110101001001001101111110010010111101000011110000100101111110110101110111100010111011010000100010011100011000101",
};

  for(uint32_t i = 0;i < sizeof(c_bits)/sizeof(c_bits[0]); i++) {
Serial.printf("i = %2d ",i);
    test_crc(c_bits[i]);
//    Serial.println();
  }
  
}

void loop(void)
{
}
The sample data are valid received FT4 messages. The first 77 bits are the data. The next 14 bits are the CRC and the rest can be ignored.

The odd thing is that it gets 4 of the CRCs right. Here's the output with * to mark the ones it got right.
Code:
i =  1 crc14 = 0xE1D4, b_crc = 0x2F7A
i =  2 crc14 = 0xBAD4, b_crc = 0x132D
i =  3 crc14 = 0x3CA0, b_crc = 0x3CA0 *
i =  4 crc14 = 0xA820, b_crc = 0x01D9
i =  5 crc14 = 0xD844, b_crc = 0x16EA
i =  6 crc14 = 0xBA58, b_crc = 0x13A1
i =  7 crc14 = 0xDE88, b_crc = 0x1026
i =  8 crc14 = 0x6CD8, b_crc = 0x0B8F
i =  9 crc14 = 0x02B0, b_crc = 0x02B0 *
i = 10 crc14 = 0x5354, b_crc = 0x3403
i = 11 crc14 = 0xFB24, b_crc = 0x358A
i = 12 crc14 = 0x7898, b_crc = 0x1FCF
i = 13 crc14 = 0xEC40, b_crc = 0x22EE
i = 14 crc14 = 0xADC8, b_crc = 0x0431
i = 15 crc14 = 0x098C, b_crc = 0x098C *
i = 16 crc14 = 0x37E4, b_crc = 0x37E4 *
crc14 is the calculated CRC using FastCRC ft4. b_crc is the valid CRC contained in the sample data.

The only thing I have noticed which might be significant is that those which are correct are the only ones which have at least two low order zeros in the valid CRC (b_crc).
It is also probably significant that WSJTX uses BOOST to generate and check the CRC14 and it uses an augmented CRC instead of a regular one. The augmented CRC is explained here. It functions somewhat differently than a regular CRC but at the moment I can't figure out how to apply this to the FastCRC FT4 to make it work.

Pete
 
I notice that your printed CRC14's have some values in excess of 14 bits. That cannot be right for a CRC based on 14 bit calculations? Methinks, the CRC cannot be a remainder if it is bigger than 14 bits, or else you would be able to divide by a further poly value (aware that divide means XOR). You learn this when you do it longhand.

The ones which match b_crc are all under 0x3F00 - which is as it should be.

This is issue of 14 bits not being a multiple of an 8 bit byte size (8, 16, 24, 32...) is something that troubles me too about the "CRC14.eloran(data, sizeof(data))" function call. Using "sizeof" as a parameter seems wrong somehow. Surely it should be using a bit size number, and does that number of bits in the source data not have to be padded up to 14 bit multiples if it happens to be other than a 14 bit multiple? I seem to recall that from my student days.

What I ought to do is another longhand calculation that is different to 56 bits (could be a co-incidence that byte multiple values work). I think we need that before we can be confident that we have all bit sizes covered. I'll do that some time soon...
 
Does "augmented" mean that you simply place the CRC first, before the message, when doing a longhand division by the polynomial (at the receiver)? Would you also agree that the "To compensate..." sentence is the same concept as my "padding with zeroes" to make the whole bit length a multiple of 14 bits?

I note also that the CRC bit order is "big endian". I'm suffering confusion with the Eurofix spec because it is not telling me what order the "symbols" are transmitted that make a 6 symbol pattern (which is then applied into the translation table). I had assumed "little endian" meaning that pulse P3 takes the least sig table symbol (and P8 the most sig - P1 to P8 being the time order), but I now suspect this is wrong and like the CRC bit order, 'tis t'other way rooned :eek:
 
@TBill - more details, notes here

from the end:
… The augment can be either at the end of last data block or from an extra call. Remember that if an expected checksum is used as the augment, its bits must be arranged in big-endian order. ...
 
I'm finding the 7 bit and 14 bit worlds very cranky. Suddenly realised why I can't see any patterns in my Loran data... the Eurofix message structure is out of placement sync with the data when stored as 7 bits held in 8. I'm going to have to reform the data into bit streams of length 70 bits before any pattern might appear. Trouble is, I don't know where the message structure starts, and I can start recording bits anywhere in the transmitted bit stream. Without any "bit flags" this really is needles in a haystack.

Which brings me to a few further questions, and my own thoughts...

(1) When using "CRC14.eloran(buff, sizeof(buff))" does this call always assume that "buff" is a pointer on a byte/word boundary? - I think yes (dependent on data type for buff).
(2) Is the "bit stream" that may be in the buffer treated as first received bit is held in lowest memory byte/word in the least sig bit position? - I think yes (seems natural to store bits in ascending address/bit position value significance).
(3) How does the hardware engine know how many bits to process for the CRC14 in the bit stream? - I don't really know.

In Eurofix, the message happens to be 56 bits (with 14 bits CRC) and 56 happens to be a multiple of 8. So if "buff" is byte sized, and if the value of "sizeof(buff)" is 7, then presumably all 56 bits contained in "buff" get processed. That's OK in this specific case, for now that the Eurofix spec is defined/published, I don't think it will change. I'm happy with that.

I made an error in post #30 - the clock speed is 120 MHz, not 180.

Interesting result just discovered with Loran "symbol" data. This is contained in pulses P3 to P8. I measured the total number of 6-symbol patterns received and analysed whether these were "good" (in the symbol table) or "bad" (not found in the table). Out of 100 patterns received, only 2 were bad (probably corrupted by lightning - its been very stormy recently). Lightning is a bogey because it has lots of energy in the 100 KHz band. This means that there should be lots of uncorrupted message/CRC bit strings in the data, so that will help me parse correctly. Also, the symbols are "balanced" - there is always an equal number of "-" and "+" symbols, and an even number of "0"s. This makes it easier to spot data errors.
 
Just performed another test string longhand...
Code:
unsigned char TestData1[] = {0x31,0x32,0x33,0x34,0x35,0x36,0x37,0x38};
The paper answer in 14 bit binary was "01 1010 0010 0010". Expressed as 14 bits held in 16 bits = 0x1A22. This result agrees with a hardware call to "CRC14.eloran(TestData1, 8);".

However, this result contradicts my own thoughts in reply to question 2 above.

So the true answer (2) is... the "incoming message data" in time order expected by "CRC14.eloran" is "...first bit received is held in the m.s.bit position of the lowest buffer memory address". Which in this case is held in TestData1[0] and length 8 bits. Bits are then stored in time order down to the l.s.bit, and then the next bit is stored in the m.s.bit position of the next higher byte address (TestData1[1]). 56 bits of message are expected that the CRC14 protects.
 
Status
Not open for further replies.
Back
Top