UKHAS Wiki

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
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 performance((More formally the E<sub>b</sub>/N<sub>0</sub> ([[http://en.wikipedia.org/wiki/Eb/N0|wikipedia]]) figure is much lower - which essentially means we need less received power to decode each bit.)) 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:

{{:guides:olivia_32_1000_waterfall.png?700}}

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 diagram((This [[http://xkcd.com/|XKCD]]-style diagram was generated using [[http://nbviewer.ipython.org/url/jakevdp.github.com/downloads/notebooks/XKCD_plots.ipynb| Jake Vanderplas's work]] on Python matplotlib)) below.

{{:guides:olivia_4_125_diagram.png}}

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.

{{:guides:orthogonality_rocks.png?700}}

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.

{{:guides:block_diagram.jpg?400}}

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 log<sub>2</sub>(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) capability((An extra ~1.5dB of SNR is required to decode Contestia compared to Olivia. See [[http://f1ult.free.fr/DIGIMODES/MULTIPSK/contestia_rttym_en.htm|here]] for more details)). 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.

<code c>
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 */
}
</code>

Remember that Olivia uses 7 bit [[http://en.wikipedia.org/wiki/ASCII|ASCII]] while Contestia compresses the ASCII space into 6 bits((See [[http://f1ult.free.fr/DIGIMODES/MULTIPSK/contestia_rttym_en.htm|here]] for more details or [[https://github.com/bristol-seds/pico-tracker/blob/contestia_dev/firmware/src/mfsk.c#L134|here]] for example code)).

== Fast Walsh-Hadamard Transform (FWHT)==

The next step is to pass this vector through a Walsh-Hadamard Transform(([[http://en.wikipedia.org/wiki/Hadamard_transform|wikipedia]], [[http://uk.mathworks.com/help/signal/examples/discrete-walsh-hadamard-transform.html|mathworks]])). This can be implemented without any care for the scaling factors found in the mathematical definitions. The code below uses a divide-and-conquer algorithm(([[http://en.wikipedia.org/wiki/Fast_Walsh%E2%80%93Hadamard_transform]])) that decomposes down to a 2-point DFT.
 
<code c>
/**
 * 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;
      }
    }
  }
}
</code>

Note that Olivia and Contestia use the output of the Walsh-Hadamard Transform in //hadamard// order rather than //sequency// order((If you're using matlab/octave you'll need to specify this like //ifwht([1,0,0,0],64,"hadamard")// - [[http://octave.sourceforge.net/signal/function/ifwht.html|GNU Octave reference]])).


== 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 constant((//0xE257E6D0291574EC// for Olivia, //0xEDB88320// for Contestia)). To ensure a truly scrambled output this constant is rotated by a pre-defined amount((//13// for Olivia, //5// for Contestia)) for each character.

<code c>

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];
  }
}
</code>

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//.

<code c>
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);
  }
}
</code>


=== Putting it all together ===

And here it is.((Code taken from the [[http://www.bristol-seds.co.uk/|University of Bristol SEDS]] [[https://github.com/bristol-seds/pico-tracker|pico tracker]])) The scrambling has been rolled into the same loop that tests for significant bits in the FWHT vector.

<code c>
#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);
      }
    }
  }
}</code>

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

<code c>
int8_t tones[64];
mfsk_encode_block("HELLO", tones, 64, 5, 0xE257E6D0291574ECLL, 13);
</code>

=== Other Resources ===

  * Draft specification for Olivia - [[http://www.arrl.org/olivia]]
  * Wikipedia of course - [[http://en.wikipedia.org/wiki/Olivia_MFSK]]
  * A page written by the original designer of Olivia, but all the images appear to be lost - [[http://web.archive.org/web/20070927210543/http://homepage.sunrise.ch/mysunrise/jalocha/fht_coding.htm]]
  * dl-fldigi source - [[https://github.com/jamescoxon/dl-fldigi/blob/master/src/include/jalocha/pj_mfsk.h]]
  * A useful summary of the differences between Olivia and Contestia - [[http://f1ult.free.fr/DIGIMODES/MULTIPSK/contestia_rttym_en.htm]]