Saturday, August 24, 2019

M4RI library

This is just a quick note referencing the M4RI library that implements the "Method of four Russians (M4RM)", and the Strassen-Winograd algorithm, see these references.

Among other things, the M4RI library provides matrix inversion in GF(2) and computing the row-echelon form of a given matrix in GF(2) which is relevant for
  • finding the polynomial generating an LFSR sequence (see here and here), and
  • for detecting the presence of convolutional codes in a given bit stream by analyzing rank-deficiencies (see here and here).

M4RI seems to be available on most linux distributions. Although its latest release is from 2014, it looks quite mature and there are recent commits to the M4RI repository.

It is now being used in


The demodulated symbols of an ARINC635 HFDL burst are shown below in terms of 180-symbol long frames. Doppler offset correction and symbol timing estimation were done manually using GNU octave.

According to the ICAO ARINC635 HFDL physical layer description (see correction here and here), 30 data symbols alternate with 15 known symbols. The data symbols are scrambled with a 120-bit long scrambling sequence which explains the 180-symbol period. This scrambling sequence is generated by an LFSR, and it can be checked that the sequences A, M1, and T are generated by LFSRs as well.

It should be easy to implement this mode in gr-digitalhf.

HFDL burst
See also DK8OK's excellent posts about ARINC635 HFDL.