UKHAS Wiki

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.

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²⁾ 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.

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.

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₂(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³⁾. Each character is encoded separately and the output vectors from each are then interleaved to produce the block of symbols to transmit.

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 bits⁴⁾.

The next step is to pass this vector through a Walsh-Hadamard Transform⁵⁾. 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⁶⁾ 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 order⁷⁾.

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⁸⁾. To ensure a truly scrambled output this constant is rotated by a pre-defined amount⁹⁾ 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.

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);
  }
}

And here it is.¹⁰⁾ 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);

• 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