THE IZ8BLY DIAGONAL INTERLEAVER
Nino Porcino IZ8BLY - 07 July 2000
This is a brief description of the data-bit Interleaver/De-interleaver used in the MFSK-2000 mode (IZ8BLY's STREAM program). The description is necessary because the interleaver is unconventional, something I've called "diagonal interleaver".
The purpose of a data interleaver is to spread the bits through the transmission in time, so burst errors (typically QRM) don't cause consecutive damaged bits to go into the FEC decoder. In fact a Viterbi decoder (the one used in the program) performs badly when there are more consecutive errors than the constraint length (K), that is, when the shift register becomes full of wrong bits. This is usually happens when the low-level modulation scheme encodes more than one bit per symbol, i.e. in our 16-MFSK mode, since when a tone is wrongly received four consecutive bits are damaged. When two tones are badly received eight consecutive bits are damaged, exceeding the constaint length capacity (which is 8 bits for K=7).
The reason for using this "Diagonal Interleaver" is that it doesn't require any synchronization. This is a very important aspect because our mode (MFSK-2000) must work in very poor conditions, where synchronization could be critical. (In other words we want the computer take as few decisions as possible -- a sort of "Fuzzy" rule).
Let's refer to what we've called "MODE A" - a 16 tones MFSK 15.625 baud transmission, where each tone encodes four data bits. In this mode the FEC is R=1/2, K=7 (NASA standard). Let's call each bit to encode "ABCDEF...." so we can instantly figure out the original position of the bits. Thus the tones of our 16-MFSK transmission are:
tone 1 = ABCD
tone 2 = CDEF
and so on...
In an usual interleaver a table of symbols is used - the symbols to encode are placed in columns and encoded symbols are taken by rows every n-steps.
Example of a usual interleaver:
AEIMQUY BFJNRVZ CGKOSW0 DHLPTX1
String passed to the interleaver: ABCD EFGH IJKL MNOP .... Strings returned from the interleaver: DHLP CGKO BFJN AEIM ....
Note how if the receiver isn't properly synched the returned string is wrong, i.e. "HLPT" instead of "DHLP"... and so on.
In the diagonal interleaver the encoded symbols are taken not by rows but by the main diagonal of the table (on decoding bits are read by the opposite diagonal). This resolves the problem of having to synchronize. In our example the returned text would be:
AEIMQUY BFJNRVZ CGKOSW0 DHLPTX1
Returned: AFKP EJOT INSX MRW1 ....
Another difference from the more usual interleavers is that the table must square (n x n, where n is the number of bits of the low-level modulation scheme). This means that only small tables are possible. In our MFSK mode "A" only a 4x4 table is possible, which gives very poor interleaving. A good idea from Murray ZL1BPU was to sequentially concatenate more than one interleaver to achieve different levels of interleaving. Actually the program uses 10 Diagonal Interleavers as shown in the example (4 letters = 4 bits = 1 tone = 1/15.625 seconds)
To encode: ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789abcdefghijklmnopqrstuvwxyz----------------------------------------------------------------------------------------- Encoded: A E I M Q U Y 2 6 a eB iF mJ qN uR yV -Z -3 -7 -b -fC -jG -nK -rO -vS -zW --0 --4 --8 --c --gD--kH--oL--sP--wT---X---1 Decoded: ABCDEFGHIJKLMNOPQRSTUVWXYZ01 12345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890 0 1 2 3 4 5 6 7 8 9 10
Performance of the diagonal interleaver:
Spreading of a symbol = 94 bits = 23.5 tones =
Delay introduced = 71 bits = 17.75 tones = 1.136 seconds
Of course this can be easily improved by concatenating more interleavers, still without requiring any synch!
All questions / comments / ideas / suggestions are appreciated. Please post them to the MFSK reflector