The Encoding of the WAAS data signal is more complicated than the Navstar data as it incorporates FEC coding and CRC parity coding as well as a frame and preamble.
Each WAAS message is 250 data bits in length and 1 second in time. They consist of
The preamble is actually 24 bits long but is split in to three 8 bit words that repeat every 3 messages. The end of the message consists of 24 Parity bits calculated using a CRC algorithm applied to the first 226 bits of the message.
The resulting bit stream is then rate ½ convolutionally encoded with a Forward Error Correction (FEC) code. The convolutional coding is constraint length 7 as standard for Veterbi decoding, the G1 symbol is selected on the output of the first half of a 4 millisecond data bit resulting from the bitwise sum of the last 7 bits of the data stream OR'ed with Octal 171, for the G2 symbol Octal 133 is used.
The CRC algorithm is defined as follows in the WAAS definition documents.
The CRC word is calculated in the forward direction on the entire bit-oriented message, including the block header containing the preamble and message type identifier, and using a seed of 0. The sequence of 24 bits (p1,p2,...,p24) is generated from the sequence of information bits (m1,m2,.......,m226). This is done by means of a code that is generated by the polynomial
g(X) = E24i=0
where gi = 1 for i = 0, 1, 3, 4, 5, 6, 7, 10, 11, 14, 17, 18, 23, 24
g = 0 otherwise.This code is called CRC-24Q (Q for Qualcomm). The generator polynomial of this code is in the following form (using binary polynomial algebra):
g(X) = (1 + X)p(X)
where p(X) is the primitive and irreducible polynomial
p(X) = X23 + X17 + X13 + X12 + X11 + X9 + X8 + X7 + X5 + X3 + 1
When, by the application of the binay polynomial algebra, the above g(X) is divided into m(X)X24, where the information sequence m(X) is expressed as
m(X) = mk + mk-1X1 + mk-2X2 +.....+ m1Xk-1the result is a quotient and a remainder R(X) of degree < 24. The bit sequence formed by this remainder represents the parity check sequence. parity bit pi, for any i from 1 to 24, is the coeffecient of X24-i in R(X).
The section above is a direct extract from the WAAS DTFA-001 and for most of us is not very meaningful. So what does this mean in practice, if the first bit of the message is 1, we bitwise OR the first 25 bits of the message with g(X), the binary value of which is 1100001100100110011111011, (0x01864cfb in hexadecimal). Then we repeat this process starting with the next bit of the message, until the last bit of the message is reached. The resulting 24 bit value is the required parity code.
If you are unfamiliar with the notation used the following example should help clarify what happens in practice, you will see it is pretty simple.
for(bit=0;bit<226;bit++)
{
if(bit%8 == 0)shift += (unsigned int)data[byte++];
if((shift&0x80000000) == 0x80000000)
{
shift = shift ^ (CRC_POLY<<7);
}
shift = shift<<1;
}
There is an example in the manual of a 250 bit data string including the correct parity, to enable one to validate your algorithm is correct.
Preamble, Message Id, IODF, IODP: Binary 11, followed by Hex: 1824For an example using the full message to calculate the parity see here.
The resulting bit stream is rate ½ encoded, this means we produce two values from a single bit stream and we do that by bitwise ORing the bit stream with two different binary values. The constraint length is 7, this means that use a 7 digit binary value to bitwise OR with the next 7 bits of the bit stream.
for(bit=0;bit<256;bit++)
{
if(bit%8 == 0)byte++;
next_bit = bit%8;
shift += data[byte]>>(8 - next_bit);
shift &= 0x80;
sym1 = shift ^ 0x79;
sym2 = shift ^ 0x5a
shift = shift<<1;
}
So we start by getting the next byte every 8 bits, we then move a bit at a time to the shift register, starting with the MSB or 7th bit and after we get to the 0th bit we move on to the next byte. Then for every new bit we clear out the current 8th bit and OR the remaining 7 bits with Convolution Polynomial A for output symbol G1 and Polynomial B for output symbol G2. For decoding the polynomials are in reverse bit order, (0x4f and 0x6d). In practise this is a continuous process and there is no break between messages.
The Waas message has several different types and data formats, also there is no guaranteed order of the messages.