Calculations in Galois Fields

Ilya Pirkin, who holds a masters degree in Physics from Moscow State University, works on real-time market information systems at CQG. He can be contacted at [email protected].

For decades, error-correcting codes have been used in digital communications to recover data received from undependable sources such as noisy channels or unreliable media. Recently, the widespread use of multicast technologies on the Internet introduced a new application for forward error correction (FEC)—recovering completely lost data. Modern networks usually don't guarantee data delivery, and network packets may be lost for a number of different reasons; for example, congestions and router buffer overflows. The traditional (and most obvious) way of recovering missing data is to use the solution officially called "automatic request for retransmission"(ARQ). A good example of this is the reliable multicast protocol (RMTP) [1]. This approach, however, has a serious disadvantage: When the number of receivers grows, the request rate grows too, which ends up with so-called "re-request implosions" and significant performance degradation. Besides, re-requests are not possible for storage devices (such as RAID) and one-way broadcast networks.

It turns out that FEC offers a better solution because it may be designed to recover completely lost data. If an IP packet is lost, it is much faster to recover it on the spot, instead of re-requesting and waiting for retransmission. Of course, FEC requires that you add some redundancy to the information you send, but usually this overhead pays off. I've even seen successful attempts to use FEC in plain TCP to reduce latency in bad networks. In this article, I'll present a C++ implementation of Galois fields-based FEC.

Erasures Versus Errors

From the information theory perspective, there is a clear difference between corrupted data and completely lost data. When you are dealing with data from unreliable sources, each bit may be corrupted. To fix the errors, the decoder first has to find the error locations, and then fix them. In packet-lossy networks, the situation is different. In this case, some packets may not arrive completely and typically do not have bit errors (packets containing errors are usually discarded). Coding theory refers to this situation, where the locations of corrupted data are known in advance, as "erasure."

Perhaps one of the most widely known nonbinary FEC is Reed-Solomon code. I'll use its most important subtype—Reed-Solomon code over Galois Field FG(2^m). Its codeword is a sequence of n=(2^m)-1 m-bit numbers or symbols. Any consecutive symbols may be chosen to contain the payload (arbitrary information), and the remaining n-k symbols are checksums. Such code is capable of correcting t erroneous and e erased symbols if 2t+e<=n-k. For pure erasures, this means that any k out of n symbols are still enough for recovering the entire codeword. Not all of the information part of the codeword has to be used: If you need a shorter code, set some of the information symbols to zero and don't transmit them at all.

An important feature of Reed-Solomon codes is that they are optimal, which means there is no better linear code with the same n and k. A major disadvantage of the code is that it has quadratic decoding time, so long codes are slow to decode. That's bad news. Why? Because typically, the longer the codeword, the better the performance of the codes at the same error (erasure) rate. Consequently, if there is no strict limitation for the data latency, it's always better to use longer codes. This is not the case for something like voice-over-IP or streaming media applications, but if you decide to create, say, a file format to be used on CDs that would tolerate a couple of faulty sectors, the decoding time becomes a major problem.

To reduce the decoding time for long codes, a number of new, fast erasure codes have been invented. [3,4] The site http://www.icsi.berkeley.edu/~luby/erasure.html lists modern erasure FEC and the results of their benchmark tests. To give you an idea of what's feasible, a 1-MB codeword with half of its symbols erased takes 1-100 second(s) to recover on an average PC (depending on the code).

In most cases, however, you won't need such long codes if you can organize the data as a table with the lines transmitted as independent packets—such a table is sometimes called a "bundle." FEC is applied to the columns of the table, so additional n-k redundant lines are added at the end of the table. This solution helps to keep the length of the code small and hence decoding fast and simple; moreover, the most time-consuming operation involved in the decoding—matrix inversion—may be calculated only once per bundle, which means its time can be spread over all the columns of the same bundle so that the decoding speed grows to about 10 MB per second. An example of such an approach is the RMTP extension for FEC in RFC 3453 [2].

Galois Fields

The key part of Reed-Solomon codes (plus some modern erasure FEC) is Galois field arithmetic. The word "field" points to a specific algebraic object: A field, in general, is a set of elements, for which the result of arithmetic operations (addition, subtraction, multiplication, division) between any elements is another element of the set. More importantly, Galois fields are finite, which means there is a finite amount of elements in the set. Let me explain why these two properties are crucial for building FEC and why ordinary integer or floating-point numbers cannot be used. The majority of error-correcting codes are based on linear algebra: Linear expressions are used to calculate the checksums; when the decoder is recovering a corrupted codeword, it is in fact solving a system of linear equations and calculating the correct symbols. Since such solutions involve lots of multiplication and division, it would not be possible to preserve the precision if FEC was implemented using conventional numbers. On the contrary, the result of Galois field operations is always precise and fits into the size of the original codeword symbols.

Galois fields are operating over a set of m-bit symbols that are interpreted as polynomials; the bits of the symbol are corresponding coefficients. This interpretation is rather typical for coding theory [5]. Addition and subtraction are bit-wise XOR, but multiplication and division are more complicated. First of all, such operations should be done using conventional polynomial division procedure [5] where the bitwise XOR is used instead of arithmetic addition and subtraction. Second, all operations are done modulo a special polynomial of degree m called "field-generator polynomial." This polynomial must be irreducible (not divisible by any other polynomial); for example, for m=4 it's 0x13 (x⁴+x+1), for m=8 it's 0x11d (x⁹+x⁴+x³+x²⁺¹), and so on. For more information, see [6].

Multiplication and division implemented directly in Galois fields are time consuming. Luckily, there is a trick that allows you to use lookup tables if m is small (less then 16) and reduces the calculation time by approximately a factor of 4. This trick is based on the fundamental property of finite fields, which says that all q=2^m-1 nonzero elements may be represented as consecutive powers of some element that is called primitive (): 1, , ²,...^(q-1). If some x=^b then b is called the logarithm of x (logarithms in finite fields are always integers, unlike logarithms of real numbers). So, if we want to multiply x and y, all we have to do is convert them to the logarithmic form: x=ⁱ y=^j, then x*y=^(i+j). The last formula means that we may replace multiplication (and division, too) with integer addition (subtraction) and a couple of table lookups. I will now present a C++ class template that represents an element of a Galois field:

template<class _T, int _m> class galois {
    int m_val;
    static g_table<_T, _m> m_table;
public:
    galois(const _T x) { ... }
    galois& operator+ (const galois& n) { ... }
    galois& operator- (const galois& n) { ... }
    galois& operator* (const galois& n) { ... }
    galois& operator/ (const galois& n) { ... }
}

_T is the storage type that is at least _m bit long. m_val contains the logarithm of the fields element. m_table contains the static lookup tables that will be shared among all elements of the same Galois field:

public:
    enum { _Q = (1 << _size) - 1 };
    _T  m_exp[_Q + 1];
    int m_log[_Q + 1];
    g_table(_T _alpha, unsigned long _field_generator) { ... }

Here, m_exp is the power table of alpha and m_log is the reverse table, which is also the table of logarithms (by the definition of a logarithm). I used a trick to represent the zero element: The value _Q in the tables denotes zero. To fill the exponent table in the constructor, you must implement polynomial multiplication in a straightforward way and use it.

    g_table(_T _alpha, unsigned long _field_generator) { 
        _T x = 1; // alpha^0 = 1
        for (unsigned i = 0; i < _Q; ++i) {
            m_exp[i] = x;
            x = _T(Galois_Mul(x, _alpha, _field_generator));
        }

Some important details of this operation include:

• We start with alpha^0=1 and continue until all q nonzero elements of the field are calculated. It is a common mistake to iterate i2^m times. Note that alpha^q = alpha ^0 = 1.
• The speed of Galois_Mul execution doesn't really matter since it's used only once during the initialization and can be implemented using direct polynomial multiplication, as in [5].

Calculation of the reverse (logarithm) table is straightforward:

for (i = 0; i <= _Q; ++i) {
  m_log[m_exp[i]] = i;
}

There are some important details worth noting in Listing 1, the galois class.

• The class keeps the logarithm of the original value rather than the value itself. This makes multiplication and division faster but addition requires conversion back to normal representation, an XOR operation, and conversion back to a logarithm. In some cases it is worth omitting the last operation by converting the galois element back to normal binary representation and using bitwise XOR directly; for example, sum ^= (a*b).convert().
• I always check whether one of the multipliers is zero because table lookup is not applicable in this case (remember that fake value _Q used for zero element). The division is even worse: We should always check for division by zero, which is an error, as in real-number arithmetic.
• I always sum the logarithms by modulo q. This comes from the fact that ^(x+q)=^x and keeps the result within the table bounds. A similar rule applies for division.
• The template I wrote is universal and can be used to implement any Galois field with a small m without any modification.

Recovering Erasures

Decoding Reed-Solomon codes is a complicated task; there are several generic algorithms that you can use [6]. You can find a good (though pure C) implementation of the so-called Berlekamp-Massy algorithm at http://rscode.sourceforge.net/. Another good open-source implementation is at http://itpp.sourceforge.net/. Instead of traditional error correction, I'd like to demonstrate the use of the galois class template in erasure FEC. For this example, I chose the so-called "Vandermond FEC" [3]. The generic encoding procedure for any FEC may be represented by linear matrix equation:

    [c<sub>0</sub> c<sub>1</sub> ... c<sub>n-1</sub>] = [b<sub>0</sub> b<sub>1</sub> ... b<sub>k-1</sub>] x G

where [c] is the resulting codeword, [b] is the original information symbols, and G is the (n×k) generator matrix. For Vandermonde FEC, the top k rows of G contain the identity matrix and the first k symbols of the codeword will have verbatim copy of the information symbols; the bottom n-k rows responsible for redundant symbols contains elements of the Vandermonde matrix: g[i][j] = alpha^(i*j).The following code fragment implements the encoder using a typical matrix multiplication:

for (int i = 0; i < _l; i++) {
  redundant[i] = 0;
  for (int j = 0; j < _k; j++) {
        gal a = gal::alpha();
        a.pow(i*j);
     redundant[i] += a * information[j];
  }
}

If any k symbols of the codeword are received, it's still possible to calculate all symbols of the original codeword. In this case, the equation becomes:

[c]' = [b] x G'

where [c]' and G' are versions of the original [c] and G containing only available symbols and corresponding rows (G' is now a square (k×k) matrix): The solution is well known from linear algebra:

    [b] = [c]' x inverse(G')

The important point here is that this solution works equally well for conventional numbers and for finite fields; moreover, calculations in the finite fields, as I mentioned before, are always precise. Now all you have to do is to implement matrix inversion—and here is where the advantages of C++ templates and overloaded operations really work out. Since I've implemented all operations, almost any existing code may be used to perform the inversion. I took the code of Gauss-Jordan elimination from [5] and it worked just fine for me with the following small modifications:

• I removed fabs since there are no negative numbers in Galois fields.
• I removed search for the maximum element in the column.
• I replace real "0." with integer 0 whenever it occurs.

The final version of the erasure decoder is presented in Listing 2. Of course, by using the existing matrix inversion procedure, I saved a lot of time writing and debugging this code. It's also worth mentioning that the rest of the procedures look much better with the overloaded operations than you may typically find in FEC implementations.

Conclusion

Galois fields are the basis for many FECs used in computer communications. C++ templates and overloaded operations provide a unique possibility to construct a universal class implementing Galois field arithmetic and to utilize lots of existing C/C++ code (such as matrix inversion) without major changes. As an example, I implemented one of the recently invented FECs, which can be used in multicast applications for missing packet recovery.

References

[1] Paul, S. and K. Sabnani. "Reliable Multicast Transport Protocol (RMTP)," IEEE Journal of Selected Areas in Communications, 1997. See also RFC 2887.

[2] Luby, M., L. Vicisano, J. Gemmell, L. Rizzo, M. Handley, and J. Crowcroft. The Use of Forward Error Correction (FEC) in Reliable Multicast (RFC 3453).

[3] Rizzo, Luigi. "On the feasibility of software FEC," http://www.iet.unipi.it/~luigi/softfec.ps.

[4] Blomer, J. et al. "A XOR-based erasure-resilient coding scheme," http://www.icsi.berkeley.edu/~luby/PAPERS/cauchypap.ps.

[5] Press, William H. et al. Numerical Recipes in C: The Art of Scientific Computing, Second Edition. Cambridge University Press. 1992.

[6] Levesque, Allen H. and Arnold M. Michelson. Error-Control Techniques for Digital Communications, John Wiley & Sons, 1985.