Three ways for verifying NAV subframe parity

The GPS specs are pretty average on the how the parity calculation for each subframe is performed, with things that I found confusing.

The most confusing thing for me is that the bit numbering within the fields is most significant bit first, so if the Time of Week is from bits 1 to 17 in the subframe bit 1 holds the  2^16 bit, and bit 17 holds the 2^0 bit.

To add to the fun, the bits are numbered from 1 to 30, rather than the more programmer-friendly 0 to 29.

And even worse, it is documented to be viewed as a hardware operation with lots of XOR gates, and that is not to be efficiently be implemented in software.

The routine below takes the last 32 bits to be received in ‘d’ and returns 1 if the parity is correct, or zero if false.

It does this three ways – a either a mass of bit XOR operations (which is great for hardware), or a set of test-bit-then-XOR operations, either from a constants or from a lookup table (which is great for software) – you can select which one to use by changing the “#if” values.

int nav_test_parity(unsigned int d)
{
 /* 'd' holds the 32 bits received, and this function will
 * return true if the low 30 bits is a valid subframe - 
 * the most recent bit is held in bit zero */
 
 /* If the last bit of the last subframe is set
 * then the data in this frame is flipped */
 if(d & 0x40000000)
   d ^= 0x3FFFFFC0;

#if 1
  static const unsigned char parity[32] = {
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x13, 0x25,
    0x0B, 0x16, 0x2C, 0x19, 0x32, 0x26, 0x0E, 0x1F,
    0x3E, 0x3D, 0x38, 0x31, 0x23, 0x07, 0x0D, 0x1A,
    0x37, 0x2F, 0x1C, 0x3B, 0x34, 0x2A, 0x16, 0x29}; 
 for(i = 6; i < 32; i++) {
   if(d&(1<<i)) d ^= parity[i]; 
 }  
 if((d & 0x3F) != 0) return 0; 
#endif 
#if 0
 /* Bits 3 through 0 */  
  if(d & 0x00000001) d ^= 0x00; // Does nothing  
  if(d & 0x00000002) d ^= 0x00; // Does nothing  
  if(d & 0x00000004) d ^= 0x00; // Does nothing
  if(d & 0x00000008) d ^= 0x00; // Does nothing
  /* Bits 7 through 6 */
  if(d & 0x00000010) d ^= 0x00; // Does nothing
  if(d & 0x00000020) d ^= 0x00; // Does nothing
  if(d & 0x00000040) d ^= 0x13;  
  if(d & 0x00000080) d ^= 0x25;  
  /* Bits 11 through 8 */  
  if(d & 0x00000100) d ^= 0x0B;  
  if(d & 0x00000200) d ^= 0x16;  
  if(d & 0x00000400) d ^= 0x2C;  
  if(d & 0x00000800) d ^= 0x31;  
  /* Bits 15 through 12 */  
  if(d & 0x00001000) d ^= 0x32;  
  if(d & 0x00002000) d ^= 0x26;  
  if(d & 0x00004000) d ^= 0x0E;  
  if(d & 0x00008000) d ^= 0x1F;  
  /* Bits 19 through 16 */  
  if(d & 0x00010000) d ^= 0x3E;  
  if(d & 0x00020000) d ^= 0x3D;   
  if(d & 0x00040000) d ^= 0x38;  
  if(d & 0x00080000) d ^= 0x31;  
  /* Bits 23 through 20 */  
  if(d & 0x00100000) d ^= 0x23;  
  if(d & 0x00200000) d ^= 0x07;   
  if(d & 0x00400000) d ^= 0x0D;   
  if(d & 0x00800000) d ^= 0x1A;   
  /* Bits 27 through 24 */  
  if(d & 0x01000000) d ^= 0x37;   
  if(d & 0x02000000) d ^= 0x2F;   
  if(d & 0x04000000) d ^= 0x1C;
  if(d & 0x08000000) d ^= 0x3B;
  /* Bits 29 through 28 */
  if(d & 0x10000000) d ^= 0x34;
  if(d & 0x20000000) d ^= 0x2A;
  /* Bits 1 through 0 of the previous subframe */ 
  if(d & 0x40000000) d ^= 0x16;
  if(d & 0x80000000) d ^= 0x29;
  /* Test all 6 parity bits (5 downto 0) at once */
  if((d & 0x3F) != 0) return 0; #
endif 
#if 0  char D24, D25, D26, D27, D28, D29;  /* A mass of XOR operations */  D24 = (l>> 1) ^ (d>>29) ^ (d>>28) ^ (d>>27) ^ (d>>25)
     ^ (d>>24) ^ (d>>20) ^ (d>>19) ^ (d>>18) ^ (d>>17) 
     ^ (d>>16) ^ (d>>13) ^ (d>>12) ^ (d>>10) ^ (d>> 7); 
 D25 = (l>> 0) ^ (d>>28) ^ (d>>27) ^ (d>>26) ^ (d>>24)
     ^ (d>>23) ^ (d>>19) ^ (d>>18) ^ (d>>17) ^ (d>>16)
     ^ (d>>15) ^ (d>>12) ^ (d>>11) ^ (d>> 9) ^ (d>> 6);
 D26 = (l>> 1) ^ (d>>29) ^ (d>>27) ^ (d>>26) ^ (d>>25)
     ^ (d>>23) ^ (d>>22) ^ (d>>18) ^ (d>>17) ^ (d>>16) 
     ^ (d>>15) ^ (d>>14) ^ (d>>11) ^ (d>>10) ^ (d>> 8);
 D27 = (l>> 0) ^ (d>>28) ^ (d>>26) ^ (d>>25) ^ (d>>24) 
     ^ (d>>22) ^ (d>>21) ^ (d>>17) ^ (d>>16) ^ (d>>15)
     ^ (d>>14) ^ (d>>13) ^ (d>>10) ^ (d>> 9) ^ (d>> 7);
 D28 = (l>> 0) ^ (d>>29) ^ (d>>27) ^ (d>>25) ^ (d>>24) 
     ^ (d>>23) ^ (d>>21) ^ (d>>20) ^ (d>>16) ^ (d>>15) 
     ^ (d>>14) ^ (d>>13) ^ (d>>12) ^ (d>> 9) ^ (d>> 8) ^ (d>> 6);
 D29 = (l>> 1) ^ (d>>27) ^ (d>>25) ^ (d>>24) ^ (d>>22)
     ^ (d>>21) ^ (d>>20) ^ (d>>19) ^ (d>>17) ^ (d>>15)
     ^ (d>>11) ^ (d>> 8) ^ (d>> 7) ^ (d>> 6);
 /* mask the parity values to a single bit */
 D24 &=1; D25 &=1; D26 &=1; D27 &=1; D28 &=1; D29 &=1;
 /* Test and reject */
 if(((d>>5) & 1) != D24) { return 0; }
 if(((d>>4) & 1) != D25) { return 0; }
 if(((d>>3) & 1) != D26) { return 0; } 
 if(((d>>2) & 1) != D27) { return 0; }
 if(((d>>1) & 1) != D28) { return 0; }
 if(((d>>0) & 1) != D29) { return 0; }
#endif
 return 1; /* Success! */
}

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s