Data Structures in liquid-dsp

Keywords: data structures rrrf crcf cccf

Most of liquid 's signal processing elements are C structures which retain the object's parameters, state, and other useful information. The naming convention is basename_xxxt_method where basename is the base object name (e.g. interp ), xxxt is the type definition, and method is the object method. The type definition describes respective output, internal, and input type. Types are usually f to denote standard 32-bit floating point precision values and can either be represented as r (real) or c (complex). For example, a dotprod (vector dot product) object with complex input and output types but real internal coefficients operating on 32-bit floating-point precision values is dotprod_crcf .

C struct Objects

Most objects have at least four standard methods: create() , destroy() , copy() , print() , and execute() . Certain objects also implement a recreate() method which operates similar to that of realloc() in C and are used to restructure or reconfigure an object without completely destroying it and creating it again. Typically, the user will create the signal processing object independent of the external (user-defined) data array. The object will manage its own memory until its destroy() method is invoked. A few points to note:

  • The object is only used to maintain the state of the signal processing algorithm. For example, a finite impulse response filter needs to retain the filter coefficients and a buffer of input samples. Certain algorithms which do not retain information (those which are memoryless) do not use objects. For example FIR filter design calculates the coefficients of a square-root raised-cosine filter, a processing algorithm which does not need to maintain a state after its completion.
  • While the objects do retain internal memory, they typically operate on external user-defined arrays. As such, it is strictly up to the user to manage his/her own memory. Shared pointers are a great way to cause memory leaks, double-free bugs, and severe headaches. The bottom line is to remember that if you created a mess, it is your responsibility to clean it up.
  • Certain objects will allocate memory internally, and consequently will use more memory than others. This memory will only be freed when the appropriate delete() method is invoked. Don't forget to clean up your mess!

Basic Life Cycle

Listed below is an example of the basic life cycle of a iirfilt_crcf object (infinite impulse response filter with complex float inputs/outputs, and real float coefficients). The design parameters of the filter are specified in the options section near the top of the file. The iirfilt_crcf filter object is then created from the design using the iirfilt_crcf_create() method. Input and output data arrays of type float complex are allocated and a loop is run which initializes each input sample and computes a filter output using the iirfilt_crcf_execute() method. Finally the filter object is destroyed using the iirfilt_crcf_destroy() method, freeing all of the object's internally allocated memory.

#include <liquid/liquid.h>

int main() {
    // options
    unsigned int order=4;   // filter order
    float fc=0.1f;          // cutoff frequency
    float f0=0.25f;         // center frequency (bandpass|bandstop)
    float Ap=1.0f;          // pass-band ripple [dB]
    float As=40.0f;         // stop-band attenuation [dB]
    liquid_iirdes_filtertype ftype  = LIQUID_IIRDES_ELLIP;
    liquid_iirdes_bandtype   btype  = LIQUID_IIRDES_BANDPASS;
    liquid_iirdes_format     format = LIQUID_IIRDES_SOS;

    // CREATE filter object (and print to stdout)
    iirfilt_crcf myfilter;
    myfilter = iirfilt_crcf_create_prototype(ftype,
                                             btype,
                                             format,
                                             order,
                                             fc, f0,
                                             Ap, As);
    iirfilt_crcf_print(myfilter);

    // allocate memory for data arrays
    unsigned int n=128; // number of samples
    float complex x[n]; // input samples array
    float complex y[n]; // output samples array

    // run filter
    unsigned int i;
    for (i=0; i<n; i++) {
        // initialize input
        x[i] = randnf() + _Complex_I*randnf();

        // EXECUTE filter (repeat as many times as desired)
        iirfilt_crcf_execute(myfilter, x[i], &y[i]);
    }

    // DESTROY filter object
    iirfilt_crcf_destroy(myfilter);
}

A more comprehensive example is given in the example file examples/iirfilt_crcf_example.c , located under the main liquid project directory.

Why C?

A commonly asked question is "why C and not C++?" The answer is simple: portability . The project's aim is to provide a lightweight DSP library for software-defined radio that does not rely on a myriad of dependencies. While C++ is a fine language for many projects (and theoretically runs just as fast as C), it is not as portable to embedded platforms as C and typically has a larger memory footprint. Furthermore, the majority of functions simply perform complex operations on a data sequence and do not require a high-level object-oriented programming interface. The significance of object-oriented programming is the techniques used, not the languages describing it.

While a number of signal processing elements in liquid use structures, these are simply to save the internal state of the object. For instance, a firfilt_crcf (finite impulse response filter) object is just a structure which contains|among other things|the filter taps (coefficients) and an input buffer. This simplifies the interface to the user; one only needs to "push" elements into the filter's internal buffer and "execute" the dot product when desired. This could also be accomplished with classes, a construct specific to C++ and other high-level object-oriented programming languages; however, for the most part, C++ polymorphic data types and abstract base classes are unnecessary for basic signal processing, and primarily just serve to reduce the code base of a project at the expense of increased compile time and memory overhead. Furthermore, while C++ templates can certainly be useful for library development their benefits are of limited use to signal processing and can be circumvented through the use of pre-processor macros at the gain of increasing the portability of the code. Under the hood, the C++ compiler's pre-processor expands templates and classes before actually compiling the source anyway, so in this sense they are equivalent to the second-order macros used in liquid .

The C programming language has a rich history in system programming|specifically targeting embedded applications|and is the basis behind many well-known projects including the Linux Kernel and the python programming language . Having said this, high-level frameworks and graphical interfaces are much more suited to be written in C++ and will beat an implementation in C any day but lie far outside the scope of this project.

Data Types

The majority of signal processing for SDR is performed at complex baseband. Complex numbers are handled in liquid by defining data type liquid_float_complex which is simply a place-holder for the standard C math type float complex and C++ type std::complex<float> . There are no custom/proprietary data types in liquid!

.. footnote
The only exception to this are the fixed-point data types,
defined in the `liquidfpm` library which hasn't been released yet,
and even these data types are actually standard signed integers.

Custom data types only promote lack of interoperability between libraries requiring conversion procedures which slow down computation. For those of you who like to dig through the source code might have stumbled upon the typedef macros at the beginning of the global header file include/liquid.h which creates new complex data types based on the compiler, (e.g. liquid_complex_float ). While technically this code does define of a new type specification, its purpose is for compatibility between compilers and programming language (see [ref:section-datastructures-c++] on C++ portability), and is binary compatible with the standard C99 specification. In fact, these data types are only used in the header file and should not be used when programming. For example, the following example program demonstrates the interface in C:

// file:    nco.c
// build:   gcc -c -o nco.c.o nco.c
// link:    gcc nco.c.o -o nco -lm -lc -lliquid

#include <stdio.h>
#include <math.h>
#include <liquid/liquid.h>
#include <complex.h>

int main() {
    // create nco object and initialize
    nco_crcf n = nco_crcf_create(LIQUID_NCO);
    nco_crcf_set_phase(n,0.3f);

    // Test native C complex data type
    float complex x;
    nco_crcf_cexpf(n, &x);
    printf("C native complex:   %12.8f + j%12.8f\n", crealf(x), cimagf(x));

    // destroy nco object
    nco_crcf_destroy(n);

    printf("done.\n");
    return 0;
}

Building/Linking with C++

Although liquid is written in C, it can be seamlessly compiled and linked with C++ source files. Here is a C++ example comparable to the C program listed in the previous section:

// file:    nco.cc
// build:   g++ -c -o nco.cc.o nco.cc
// link:    g++ nco.cc.o -o nco -lm -lc -lliquid

// NOTE: The definition for liquid_float_complex will change
//       depending upon whether the standard C++ <complex>
//       header file is included before or after including
//       <liquid/liquid.h>; I strongly recommend including
//       <complex> first.
#include <iostream>
#include <math.h>
#include <complex>
#include <liquid/liquid.h>

int main() {
    // create nco object and initialize
    nco_crcf n = nco_crcf_create(LIQUID_NCO);
    nco_crcf_set_phase(n,0.3f);

    // Test liquid complex data type
    liquid_float_complex x;
    nco_crcf_cexpf(n, &x);
    std::cout << "liquid complex:     "
              << x.real() << " + j" << x.imag() << std::endl;

    // Test native c++ complex data type
    std::complex<float> y;
    nco_crcf_cexpf(n, &y);
    std::cout << "c++ native complex: "
              << y.real() << " + j" << y.imag() << std::endl;

    // destroy nco object
    nco_crcf_destroy(n);

    std::cout << "done." << std::endl;
    return 0;
}

It is important, however, to link the code with a C++ linker rather than a C linker. For example, if the above program ( nco.cc ) is compiled with g++ it must also be linked with g++ , viz

$ g++ -c -o nco.cc.o nco.cc
$ g++ nco.cc.o -o nco -lm -lc -lliquid

Learning by example

While this document contains numerous examples listed in the text, they are typically condensed to demonstrate only the interface. The examples/ subdirectory includes more extensive demonstrations and numerous examples for all the signal processing components. Many of these examples write an output file which can be read by Octave to display the results graphically.