UKHAS Wiki

UK High Altitude Society

User Tools

Site Tools


guides:olivia_and_contestia

Olivia and Contestia are amateur radioteletype protocols that were originally developed for HF but have been recently used on High Altitude Balloons. They offer more performance1) than RTTY at the expense of complexity.

This guide assumes you're familiar with RTTY and have probably launched your own payload using it. If not you would be best advised to use RTTY for your first flight!

The Basics

While RTTY uses 2 tones to transmit data, Olivia and Contestia use multiple tones (most commonly 16, 32 and 64). They are therefore described a Multiple Frequency Shift Keying (MFSK) modes. Like RTTY only one tone is transmitted at once. Here's what that looks like on the waterfall:

In RTTY we transmit bits (either 0 or 1) but in Olivia and Contestia we transmit symbols - each of which corresponds to multiple bits. However, these bits do not directly encode the information we want to send: rather there are many more bits are sent than there are in the data packet. This is a result of using Forward Error Correction (FEC). It is this that allows us to decode even when the signal on the waterfall has long disappeared into the noise.

Describing the Mode

Olivia and Contestia each have a number of different sub-modes, each of which are defined by the number of tones used and the bandwidth over which these tones are transmitted. They are usually described in the format “n/m” where n is the number of tones and m is the bandwidth. You can see this in the bottom left of the dl-fldigi window above.

The fact that this notation looks like a division isn't coincidence: If you divide n by m you get the symbol time - that is the length of time each symbol lasts for (in seconds). Also if you divide m by n you get the tone spacing (in hertz). These are shown on the diagram2) below.

The reciprocal of the symbol time is the symbol rate - that is how many symbols are transmitted per second.

It is important to note that the symbol rate and the tone spacing are exactly equal, giving the mode the special property of orthogonality. This means that in one symbol time the number of cycles completed by each possible tone differs by an integer amount. In the diagram below we have three tones with a tone spacing of 1 Hertz. In the one second of time shown they all complete an integer number of cycles and crucially all finish at the same phase at which they started.

This orthogonality allows the receiver to distinguish the tones from one another and simplifies the receiver's design.

Encoding the Data

To send data using Olivia and Contestia the data needs to be encoded into a series of symbols. This section will work through how to do this using Olivia 32/1000 as an example. Below is the overall block diagram for the encoding process.

block_diagram.jpg

Rather than working with characters as RTTY does, Olivia and Contestia work with blocks of symbols. The input to each block is an array of log2(n) characters, where n is the number of tones. In Olivia each block is encoded into 64 symbols, while for Contestia the same data is encoded in 32 symbols with a resulting loss of Forward Error Correcting (FEC) capability3). Each character is encoded separately and the output vectors from each are then interleaved to produce the block of symbols to transmit.

Input Vector

The first step in the encoding process is to construct an vector that represents the character to be transmitted. This vector will be mostly zero apart from one element which will be either +1 (if the MSB is zero) or -1 (if the MSB is one). The index of this element is set by the remaining LSBs. So to encode 'H' = 0b1001000 the array index 8 is set to -1.

int8_t vector[symbols_per_block];
 
/* Set a deviation in the input vector */
memset(vector, 0, symbols_per_block * sizeof(int8_t));
if (character < symbols_per_block) {
  vector[character - 0]                  = 1;	/* +ve */
} else {
  vector[character - symbols_per_block] = -1;	/* -ve */
}

Remember that Olivia uses 7 bit ASCII while Contestia compresses the ASCII space into 6 bits4).

Fast Walsh-Hadamard Transform (FWHT)

The next step is to pass this vector through a Walsh-Hadamard Transform5). This can be implemented without any care for the scaling factors found in the mathematical definitions. The code below uses a divide-and-conquer algorithm6) that decomposes down to a 2-point DFT.

/**
 * Inverse Fast Walsh-Hadamard Transform
 *
 * `data` an array that is the input vector. It is modifed in-place to
 * become the output vector.
 * `len` is the number of elements in `data`.
 *
 * The result is returned in "hadamard" order
 */
void ifwht(int8_t *data, size_t length)
{
  size_t step, decomp_index, index;
  int8_t lvalue, rvalue;
 
  /**
   * The transform is decomposed into smaller WHTs.
   * We ignore the normalisation factors.
   */
 
  /* Iterate through the decompositions of size length --> 8, 4, 2 */
  for (step = length / 2; step; step /= 2) {
 
    /* Iterate through each decomposition for this step size */
    for(decomp_index = 0; decomp_index < length; decomp_index += (step*2)) {
 
      /* Interate through each IDFT in the decomposition */
      for(index = 0; index < step; index++) {
 
        /* Compute a two-point Inverse Discrete Fourier Transform (IDFT) */
        lvalue = data[decomp_index + index];
        rvalue = data[decomp_index + index + step];
 
        /* Difference */
        data[decomp_index + index]        = lvalue - rvalue;
        /* Sum */
        data[decomp_index + index + step] = lvalue + rvalue;
      }
    }
  }
}

Note that Olivia and Contestia use the output of the Walsh-Hadamard Transform in hadamard order rather than sequency order7).

Scrambling

To ensure that the same tone is not transmitted repeatedly, the output from the FWHT is scrambled. This is achieved by flipping the sign of certain elements in the FWHT output according to a pre-defined constant8). To ensure a truly scrambled output this constant is rotated by a pre-defined amount9) for each character.

uint32_t scrambler_right = character_index * 13;
uint64_t rotated_scrambler = 
  (0xE257E6D0291574ECLL >> scrambler_right) |
  (0xE257E6D0291574ECLL << (64 - scrambler_right));
 
/* Iterate over each symbol in the output block */
for (uint32_t symbol = 0; symbol < symbols_per_block; symbol++) {
 
  /* If this bit in the FWHT is significant */
  if (scrambler & (1LL << symbol)) {
 
    /* Flip sign */
    fwht_vector[symbol] = -fwht_vector[symbol];
  }
}

This scrambling poses no problems for the receiver: it is perfectly deterministic and so can be easily reversed.

Interleaving

Each character is responsible for one bit of each symbol, but which bit this is rotates throughout the block. The code below takes a scrambled fwht_vector and sets the appropriate bits in tones.

int8_t tones[symbols_per_block];
memset(tones, 0, symbols_per_block * sizeof(int8_t));
 
/* Iterate over each symbol in the output block */
for (uint32_t symbol = 0; symbol < symbols_per_block; symbol++) {
 
  /* If this bit the FWHT is significant */
  if (fwht_vector[symbol] < 0) {
 
    /* Find the bit index to set */
    uint8_t bit_index = (character_index + symbol) % bits_per_symbol;
 
    /* Set this bit */
    tones[symbol] = (1 << bit_index);
  }
}

Putting it all together

And here it is.10) The scrambling has been rolled into the same loop that tests for significant bits in the FWHT vector.

#include <string.h>
 
void mfsk_encode_block(char* block, int8_t* tones,
                       uint8_t symbols_per_block,	/* The number of on-the-air symbols to transmit for each block */
                       uint8_t bits_per_symbol,		/* The number of bits encoded in each on-the-air symbol */
                       uint64_t scrambler,		/* Scrambler sequence */
                       uint8_t scrambling_shift)	/* Scrambler shift */
{
  int8_t fwht_vector[symbols_per_block];
  memset(tones, 0, symbols_per_block * sizeof(int8_t));
 
  /**
   * There is one bit in the symbol for each character in the
   * block. Iterate over each character.
   */
  for (uint8_t character = 0; character < bits_per_symbol; character++) {
 
    /* Mask off unuseds bits in the character */
    block[character] &= ((symbols_per_block * 2) - 1);
 
    /* Set a deviation in the input vector */
    memset(fwht_vector, 0, symbols_per_block * sizeof(int8_t));
    if (block[character] < symbols_per_block) {
      fwht_vector[block[character] - 0]                  = 1;	/* +ve */
    } else {
      fwht_vector[block[character] - symbols_per_block] = -1;	/* -ve */
    }
 
    /* Perform an in-place Inverse Fast Walsh-Hadamard Transform */
    ifwht(fwht_vector, symbols_per_block);
 
    /* Iterate over each symbol in the output block */
    for (uint32_t symbol = 0, mask_index = character * scrambling_shift;
         symbol < symbols_per_block;
         symbol++, mask_index++) {
 
      mask_index %= symbols_per_block;
 
      /* If this bit in the FWHT is significant */
      if ((scrambler & (1LL << mask_index)) ?
          (fwht_vector[symbol] > 0) :	/* Scrambled:     +ve is significant */
          (fwht_vector[symbol] < 0)) {	/* Not Scrambled: -ve is significant */
 
        /* Find the bit index to set */
        uint8_t bit_index = (character + symbol) % bits_per_symbol;
 
        /* Set this bit */
        tones[symbol] |= (1 << bit_index);
      }
    }
  }
}

For Olivia 32/1000 you might call it like this:

int8_t tones[64];
mfsk_encode_block("HELLO", tones, 64, 5, 0xE257E6D0291574ECLL, 13);

Other Resources

1) More formally the Eb/N0 (wikipedia) figure is much lower - which essentially means we need less received power to decode each bit.
2) This XKCD-style diagram was generated using Jake Vanderplas's work on Python matplotlib
3) An extra ~1.5dB of SNR is required to decode Contestia compared to Olivia. See here for more details
4) See here for more details or here for example code
7) If you're using matlab/octave you'll need to specify this like ifwht([1,0,0,0],64,“hadamard”) - GNU Octave reference
8) 0xE257E6D0291574EC for Olivia, 0xEDB88320 for Contestia
9) 13 for Olivia, 5 for Contestia
guides/olivia_and_contestia.txt · Last modified: 2014/11/29 06:08 by richardeoin