Interleaver

The MFSK16 interleaver consists of 10 stages of the IZ8BLY Diagonal interleaver.

In cocoaModem, an equivalent recurrence equation is use to implement the 10 stages of the diagonal interleave steps as a single linear interleaver step. Based on the IZ8BLY documentation, a single stage of the MFSK16 de-interleaver can be seen below:



Data from the demodulator enters the buffer in the order 0, 1, 2, 3, 4, 5, 6, 7..., shown by the green traces. Data exits the de-interleaver in the order 0, 5, 10, 15, 4, 9, 14, 15,... shown by the red boxes in the above figure.

If we consider the index of the output to be of the form (for i = 0, 1, 2...)

(Eq. 1)

then for an input sequence without a de-interleaver, we can write



With a single stage de-interleaver, notice (from the red boxes in the figure above) that we move down one extra row (i.e., 4 input samples) for each column that we move to the right. The index of each row is 4 larger than the index in the previous row thus



Each de-interleaver stage follows the same pattern (moving down one extra row for each column we move to the right), and we can write in general



i.e., the sequence for p is 1, 5, 9, 13, 17, 21, 25, 29, 33, 37, 41, 45..., and the generating function of the recurrence equation p is



where N is the number of de-interleave stages.

For a 10 stage de-interleaver, the value of p in Equation 1 is 41, and the 10-stage diagonal de-interleaver can therefore be implemented using a single array by adding input samples sequentially into the array and extracting the output bits 41 elements apart from one another, viz at the following indexes



cocoaModem outputs 4 bits of data at a time, addressing the 4 elements at 41 counts from one another, before incrementing i by 1, and proceeding to decode the next 4 bits.

Since each 4x4 diagonal de-interleaver requires 16 memory elements, the linear interleaver that is equivalent to 10 of these diagonal interleavers requires a 160 element memory.

The interleaver is the inverse of the de-interleaver and can therefore be implemented by reversing the order of operations, i.e., adding data to a linear array in the order specified by the above recurrence and reading the encoded data out sequentially from the linear array.

The advantage of implementing the diagonal interleaver as a single linear interleaver is that the computation is constant no matter how many interleaver stages are use, and thus avoiding using iterative loops or recursive function calls.


Interleaver Implementation

The following diagram shows how 4 data bits are written in and read out from the linear interleaver/deinterleaver.

The next 4 bits are entered and read from the following locations:

Notice that the relative locations of the input and output taps remain fixed. The data buffer simply advances by 4 elements for each decoding step.


The interleaver is the inverse of the de-interleaver, and can be implemented by swapping the input taps with the output taps in the figures above.

The following figure shows diagrammatically what happens in the combined encoding-decoding process.

Example Code

The following is the Objective-C code for the MFSK16 de-interleaver that is used in cocoaModem. Each "bit" is a floating point soft decoded number between 0.0 and 1.0. The interleaverRegister is an array of 160 floating point elements, used as a ring buffer. Notice that a table lookup can also be used to index into the interleaverRegister array.


typedef struct { float bit[4] ; /* bit[0] = MSB, bit[3] = LSB */ } QuadBits ;

- (QuadBits)deinterleave:(QuadBits)p
{

}

The routine for the interleaver merely swaps the two for loops from the above example.

• MFSK16 > 
• Interleaver >