This tutorial will demonstrate computation at the byte level (raw message data) by introducing the forward error-correction (FEC) coding module. Please note that liquid only provides some very basic FEC capabilities including some Hamming block codes and repeat codes. While these codes are very fast and enough to get started, they are not very efficient and add a lot of redundancy without providing a strong level of correcting capabilities. liquid will use the convolutional and Reed-Solomon codes described in libfec , if installed on your machine.
Problem Statement∞
Digital communications over a noisy channel can be unreliable, resulting in errors at the receiver. Forward error-correction (FEC) coding adds redundancy to the original data message that allows for some errors to be corrected at the receiver. The error-correction capability of the code is dependent upon many factors, but is usually improved by increasing the amount of redundancy added to the message. The drawback to adding a lot of redundancy is that the communications rate is decreased as the link must be shared among the important data information as well as the redundant bits. The benefit, however, is that the receiver has a better chance of correcting the errors without having to request a retransmission of the message. Volumes of research papers and books have been written about the error-correction capabilities of certain FEC encoder/decoder pairs (codecs) and their performance in a variety of environments. While there is far too much information on the subject to discuss here, it is important to note that liquid implements a very small subset of simple FEC codecs, including several Hamming and repeat codes. If the libfec library is installed when liquid is configured this list extends to convolutional and Reed-Solomon codes.
In this tutorial you will create a simple program that will generate a message, encode it using a simple Hamming(7,4) code, corrupt the encoded message by adding an error, and then try to correct the error with the decoder.
Setting up the Environment∞
Create a new file fec.c and open it with your favorite editor. Include the headers stdio.h and liquid/liquid.h and add the int main() definition so that your program looks like this:
#include <stdio.h>
#include <liquid/liquid.h>
int main() {
printf("done.\n");
return 0;
}
Compile and link the program using gcc :
$ gcc -Wall -o fec fec.c -lm -lc -lliquid
The flag " -Wall " tells the compiler to print all warnings (unused and uninitialized variables, etc.), " -o fec " specifies the name of the output program is " fec ", and " -lm -lc -lliquid " tells the linker to link the binary against the math, standard C, and liquid DSP libraries, respectively. Notice that the above command invokes both the compiler and the linker collectively. If the compiler did not give any errors, the output executable fec is created which can be run as
$ ./fec
and should simply print " done. " to the screen. You are now ready to add functionality to your program.
We will now edit the file to set up the basic simulation by generating a message signal and counting errors as a result of channel effects. The error-correction capabilities will be added in the next section. First set up the simulation parameters: for now the only parameter will be the length of the input message, denoted by the variable n ( unsigned int ) representing the number of bytes. Initialize n to 8 to reflect an original message of 8 bytes. Create another unsigned int variable k which will represent the length of the encoded message. This length is equal to the original ( n ) with the additional redundancy. For now set k equal to n as we are not adding FEC coding until the next section. This implies that without any redundancy, the receiver cannot correct for any errors.
Message data in liquid are represented as arrays of type unsigned char . Allocate space for the original, encoded, and decoded messages as msg_org[n] , msg_enc[k] , and msg_dec[n] , respectively. Initialize the original data message as desired. For example, the elements in msg_org can contain 0,1,2,...,n-1 . Copy the contents of msg_org to msg_enc . This effectively is a placeholder for forward error-correction which will be discussed in the next section. Corrupt one of the bits in msg_en c (e.g. msg_enc[0] \verb|^|= 0x01; will flip the least-significant bit in the first byte of the msg_enc array), and copy the results to msg_dec . Print the encoded and decoded messages to the screen to verify that they are not equal. Without any error-correction capabilities, the receiver should see a message different than the original because of the corrupted bit. Count the number of bit differences between the original and decoded messages. liquid provides a convenient interface for doing this and can be invoked as
unsigned int num_bit_errors = count_bit_errors_array(msg_org, msg_dec, n);
Print this number to the screen. Your program should look similar to this:
#include <stdio.h>
#include <liquid/liquid.h>
int main() {
// simulation parameters
unsigned int n = 8; // original data length (bytes)
// compute size of encoded message
unsigned int k = n; // (no encoding yet)
// create arrays
unsigned char msg_org[n]; // original data message
unsigned char msg_enc[k]; // encoded/received data message
unsigned char msg_dec[n]; // decoded data message
unsigned int i;
// create message
for (i=0; i<n; i++) msg_org[i] = i & 0xff;
// "encode" message (copy to msg_enc)
for (i=0; i<n; i++) msg_enc[i] = msg_org[i];
// corrupt encoded message (flip bit)
msg_enc[0] ^= 0x01;
// "decode" message (copy to msg_dec)
for (i=0; i<n; i++) msg_dec[i] = msg_enc[i];
printf("original message: [%3u] ",n);
for (i=0; i<n; i++)
printf(" %.2X", msg_org[i]);
printf("\n");
printf("decoded message: [%3u] ",n);
for (i=0; i<n; i++)
printf(" %.2X", msg_dec[i]);
printf("\n");
// count bit errors
unsigned int num_bit_errors = count_bit_errors_array(msg_org, msg_dec, n);
printf("number of bit errors received: %3u / %3u\n", num_bit_errors, n*8);
return 0;
}
Compile the program as before, creating the executable " fec ." Running the program should produce an output similar to this:
original message: [ 8] 00 01 02 03 04 05 06 07
decoded message: [ 8] 01 01 02 03 04 05 06 07
number of bit errors received: 1 / 64
Notice that the decoded message differs from the original and that the number of received errors is nonzero.
Creating the Encoder/Decoder∞
So far our program doesn't use any liquid interfaces (except for the function used to count bit errors). The FEC module in liquid provides a simple interface for adding forward error-correction capabilities to your project. The fec object abstracts from the gritty details behind the bit manipulation (packing/unpacking of bytes, appending tail bits, etc.) of error-correction structures. As an example, convolutional codes observe bits one at a time while Reed-Solomon codes operate on entire blocks of bits. The fec object in liquid conveniently abstracts from the organization of the codec and takes care of this overhead internally. This allows seamless integration of different codecs with one simple interface. As with the iirfilt_rrrf object in the phase-locked loop tutorial ([ref:section-tutorial-pll] ) the fec object has methods create() , print() , and destroy() . Nearly every object in liquid has these methods; however the fec object replaces execute() with encode() and decode() as the same object instance can be used for both encoding and decoding. The fec_create() method accepts two arguments, although the second one is basically ignored. The first argument is an enumeration of the type of codec that you wish to use.
To begin, create a new fec object of type LIQUID_FEC_HAMMING7 4 (the second argument can simply be NULL ) which creates a Hamming(7,4) code:
fec q = fec_create(LIQUID_FEC_HAMMING74, NULL);
Details of the available codes in liquid can be found in[ref:section-fec] . This codec nominally accepts 4 bits, appends 3 parity bits, and can detect and correct up to one of these seven transmitted bits. The Hamming(7,4) code is not particularly strong for its rate; however it is computationally efficient and has been studied extensively in coding theory. The interface provided by liquid conveniently abstracts from the process of managing 8-bit data symbols (bytes), converting to 4-bit input symbols, encoding to 7-bit output symbols, and then re-packing into 8-bit output bytes. This is consistent with any forward error-correction code in liquid ; as the user, you simply see data bytes in and data bytes out. The length of the output sequence can be computed using the method
unsigned int k = fec_get_enc_msg_length(LIQUID_FEC_HAMMING74, n);
where n represents the number of uncoded input bytes and k represents the number of encoded output bytes. This value should be used to appropriately allocate enough memory for the encoded message. Encoding the data message is as simple as invoking
fec_encode(q, n, msg_org, msg_enc);
which uses our newly-created fec object q to encode n input bytes in the array msg_org and store the result in the output array msg_enc . The interface for decoding is nearly identical:
fec_decode(q, n, msg_enc, msg_dec);
Notice that the second argument again represents the number of uncoded data bytes ( n ). Don't forget to destroy the object once you are finished:
fec_destroy(q);
Final Program∞
The final program is listed below, and a copy of the source is located in the doc/tutorials/ subdirectory.
#include <stdio.h>
#include <liquid/liquid.h>
int main() {
// simulation parameters
unsigned int n = 8; // original data length (bytes)
fec_scheme fs = LIQUID_FEC_HAMMING74; // error-correcting scheme
// compute size of encoded message
unsigned int k = fec_get_enc_msg_length(fs,n);
// create arrays
unsigned char msg_org[n]; // original data message
unsigned char msg_enc[k]; // encoded/received data message
unsigned char msg_dec[n]; // decoded data message
// CREATE the fec object
fec q = fec_create(fs,NULL);
fec_print(q);
unsigned int i;
// generate message
for (i=0; i<n; i++)
msg_org[i] = i & 0xff;
// encode message
fec_encode(q, n, msg_org, msg_enc);
// corrupt encoded message (flip bit)
msg_enc[0] ^= 0x01;
// decode message
fec_decode(q, n, msg_enc, msg_dec);
// DESTROY the fec object
fec_destroy(q);
printf("original message: [%3u] ",n);
for (i=0; i<n; i++)
printf(" %.2X", msg_org[i]);
printf("\n");
printf("decoded message: [%3u] ",n);
for (i=0; i<n; i++)
printf(" %.2X", msg_dec[i]);
printf("\n");
// count bit errors
unsigned int num_bit_errors = count_bit_errors_array(msg_org, msg_dec, n);
printf("number of bit errors received: %3u / %3u\n", num_bit_errors, n*8);
printf("done.\n");
return 0;
}
The output should look like this:
fec: Hamming(7,4) [rate: 0.571]
original message: [ 8] 00 01 02 03 04 05 06 07
decoded message: [ 8] 00 01 02 03 04 05 06 07
number of bit errors received: 0 / 64
done.
Notice that the decoded message matches that of the original message, even though an error was introduced at the receiver. As discussed above, the Hamming(7,4) code is not particularly strong; if too many bits in the encoded message are corrupted then the decoder will be unable to correct them. Play around with changing the length of the original data message, the encoding scheme, and the number of errors introduced.
For a more detailed program, see examples/fec_example.c in the main liquid directory.[ref:section-fec] describes liquid 's FEC module in detail. Additionally, the packetizer object extends the simplicity of the fec object by adding a cyclic redundancy check and two layers of forward error-correction and interleaving, all of which can be reconfigured as desired. See [ref:section-framing-packetizer] and examples/packetizer_example.c for a detailed example program on how to use the packetizer object.