Abstract

Let the number of data bits be n, and the number of coding bits be m. Let the average number of bits required to decode all bits in the code be o, otherwise termed the "overhead". Finally, let the computational overhead of a code be l.

In this paper, we present the optimal systematic codes for each value of n, m and l, such that (n+m)*m is less than or equal to 30. These codes have been derived by an exhaustive search of all codes. It is the intent of this paper to provide systems researchers and programmers with a reference that they may use when they need to evaluate and employ small codes in their applications.

1.0 Introduction

In this paper, we present optimally performing, small codes. Optimality is determined as follows. We are given three parameters:

1. The number of data bits (or blocks, when this is applied to storage applications) is n.
2. The number of coding bits is m. Therefore, the rate of the code is (n/(n+m)). Most research focuses on large codes of specific rates. Our work differs in that we focus on small codes of all rates.
3. The number of links in the graph that represents the code is l. This is a metric that represents the encoding and decoding performance of the code. Specifically, the performance is O(l).

For each value of n, m and l, we present codes that minimize the "overhead" o, defined to be the average number of bits required to reconstruct all the bits of the code.

Since the intent of this paper is to be a reference for systems programmers, its organization is a little eccentric. We first present the basics of coding, how bipartite graphs represent codes, and how to encode and decode given a bipartite graph. We then present optimal codes for all values of n and m such that (n+m)*n is less than or equal to 30. Following that, we present the exact mechanics of encoding, decoding, and computing overhead.

2.0 Systematic Graphs and Codes

Parity-check codes are based on bipartite graphs known as "Tanner" graphs. These graphs have n+m nodes on their left side, sometimes termed the "message" nodes, and m nodes on their right side, termed "check" nodes. Edges only connect message and check nodes. An example graph is depicted in Figure 1.

Figure 1. An example Tanner graph for n=4 and m=3.

The left-hand nodes hold the bits that are to be stored by the application. The edges and the right-hand nodes specify constraints that the left-hand nodes must satisfy. The most straightforward codes are "systematic" codes, where the data bits are stored in n of the left-hand nodes, and the coding bits in the remaining m left-hand nodes are calculated from the data bits and the constraints in the right-hand nodes using exclusive-or.

For example the code in Figure 1, is a systematic one, whose data bits may be stored in nodes l1 through l4. The coding bits are calculated as follows:

• Bit l6 is the exclusive-or of l2, l3 and l4 (from constraint r3).
• Bit l7 is the exclusive-or of l1, l2 and l3 (from constraint r2).
• Bit l5 is the exclusive-or of l2, l4 and l7 (from constraint r1).

We present decoding as an act in a storage system. Suppose we store each of the (n+m) bits on a different storage node. Then we download bits from the storage nodes at random until we have downloaded enough bits to reconstruct the data. To decode in this manner, we start with the Tanner graph for the code, placing values of zero in each right-hand node, and leaving the left-hand nodes empty. When we download a bit, we put its value into its corresponding left-hand hand node lx. Then, for each right-hand node rx to which it is connected, we update the value stored in rx to be the exclusive-or of that value and the value in lx. We then remove the edge (lx,rx), from the graph. At the end of this process, if there are any right-hand nodes with only one incident edge, then they contain the decoded values of the left-hand node to which they are connected, and we can set the value of those left-hand nodes accordingly, and then remove their edges from the graph in the same manner as if they had been downloaded. Obviously, this is an iterative process.

When all nodes' values have been either downloaded or decoded, the decoding process is finished. If a code is systematic, then the data bits are held in n of the left-hand nodes. The number of exclusive-or/copy operations required is equal to the number of edges in the graph.

Encoding with a systematic graph is straightforward -- simply decode using the n data bits.

2.1 "Systematic" Codes, IRA Codes, Gallager Codes, and Tanner Graphs

2.2 Decoding Overhead

The optimal overhead of any decoding scheme is n. Therefore, the overhead factor f(G) of a graph Gis o(G)/n, and the optimal overhead factor of any decoding scheme is 1. Note, Reed-Solomon coding achieves this optimimum; however, its large (O(n*n)) computational overhead renders it unattractive for many applications.

In [PT04], we used a Monte-Carlo simulation to estimate the overhead factor of various codes. In this paper, we determine overhead factor exactly, using a recursive formula. However, before presenting this determination, we describe the optimal codes.

3.0 Optimal Codes

The table that follows presents optimal codes in the following format. First, n, m, l, o(G), and f(G) are listed, then a list of the edges of each left-hand node in the graph, and then finally a list of the coding nodes of the graph. The nodes are zero-indexed. As an example, consider the following table entry:

This says that for n=3 and m=3, and for all values of l greater than or equal to nine, the following graph is optimal, having an overhead of 3.2 and an overhead factor of 1.0667:

Moreover, the graph is systematic, with coding nodes 0, 1 and 3, and data nodes 2, 4 and 5. Note, the graph has 9 edges, as denoted by the l column.

Note, if all graphs for a value of l have overhead factors greater than a graph with a smaller value of l, then the latter graph will perform better in terms of both overhead factor and decoding performance. For that reason, as in the above table entry, if a graph for a certain value of l has a smaller overhead factor than all graphs with higher values of l, we list that graph as the optimal for that value of l "and up."

Tables 1, 2 and 3 list the optimal graphs for (n+m)*m <= 30 and m > 1. (We do not present graphs for m=1 as straight parity is optimal in these cases.)

There are a few interesting trends to the optimal graphs. First, for m=2 and m=3, all the optimal graphs are of a type which we will call simple. That is, each coding node has only one incident edge, and therefore, each coding node is the exclusive-or of only data bits. (These are the codes called "systematic" in [PT04], which is a misnomer, since any code where the data bits are included in the n+m left-hand nodes is systematic). Interestingly, for m=4, the optimal graphs are not simple (e.g. for n=2, m=4, l=9, node 3 is a coding node, but has two edges).

Second, there is a clear trend in the optimal graphs where m=2. That is that the data nodes are divided evenly into three classes: nodes with edges (0), nodes with edges (1), and nodes with edges (0,1). If n is not evenly divisible by three, then the first extra node has edges to 0 and 1, and the second extra node has an edge to 0. To show this pictorally, we picture them below in Figure 2. The shaded nodes are the coding nodes. We suspect that graphs of this form are optimal for all values of n but we have neither proved this nor quantified the overhead of these graphs.

n=2	n=3	n=4
n=5	n=6	n=7
n=8	n=9	n=10

Figure 2. Optimal Tanner Graphs for m=2, n between 2 and 10.

A similar trend emerges with m=3. Again, the n data nodes appear to be equally divided among the possible combinations of edge lists: {(0),(1),(2),(0,1),(0,2),(1,2),(1,2,3)}. However, unlike with m=2, where each additional value of n builds on the previous value's optimal graph in an identifiable pattern, in the limited graphs we have here, there is no such pattern. For example, the graph with n=4 builds on n=3 in a different way from the way in the analogous graph with n=11 builds on n=10. We will continue to explore these patterns.

n=2	n=3	n=4
n=5	n=6	n=7
n=8	n=9	n=10
n=11	n=12	n=13
	n=14

Figure 3. Optimal Tanner Graphs for m=3, n between 2 and 14.

In Figure 4, we show the optimal graphs with m=4. Unlike the graphs for m=3 and m=2, these graphs do not build upon one another. As before, the n nodes are divided "evenly" between the possible combinations of edges. However, the way in which graphs build upon one another is not clear.

n=2	n=3	n=4
n=5	n=6	n=7

Figure 4. Optimal Tanner Graphs for m=4, n between 2 and 7.

Finally, in Figure 5, we show the optimal graphs for m=5. Again, we will need to enumerate more graphs to discover whether there are interesting patterns to these optimal graphs.

n=2

n=3

Figure 5. Optimal Tanner Graphs for m=5, n between 2 and 3.

4.0 Decoding and Computing Overhead - Precise Definitions

When we start, we set all right-hand nodes to zero, and leave the values of all left-hand nodes blank.

To decode, we define two operations on graphs: assigning a value to a node, and downloading a node. Both operations are defined only on left-hand nodes. We start with the former. Given a left-hand node li, when the value of that node becomes known, it should be assigned. When it is assigned, for each right-hand node rj to which li is connected, rj's value is set to the exclusive-or of its previous value and li's value, and then the edge (li,rj) is removed from the graph. If there are any right-hand nodes rj which now have only one incident edge, then the value of the left-hand node to which rj is connected may now be assigned to be the value of rj. Before assigning the value, however, the edge between that node and rj should be removed, and rj should also be removed from the graph. Note, assigning one node's value can therefore result in assigning many other nodes' values.

To download a node, if the node's value has already been assigned, then the node is simply removed from the graph. Otherwise, the value of the node is assigned to its downloaded value, and it is then removed from the graph.

When the values of all left-hand nodes have been assigned, the decoding process is finished.

Computing the overhead o(G) of graph G proceeds as follows. If all nodes have zero edges, then the overhead is zero. Otherwise, we simulate downloading each left-hand node of the graph, and compute the average overhead as the average of all simulations. When we simulate downloading a node li, we assign its value (if unassigned), and remove the node from the graph. We are then left with a residual graph, R(G,li). We can recursively determine R(G,li)'s overhead. Then, the equation for determining a graph's overhead (if not zero), is:

4.1 Example 1: G1

This is a systematic code, where either node may be the data or coding bit. To decode, we first set r0's value to zero:

Then, suppose we download node l0, which has a value of 1. We assign its value by going through the following steps. We set its value to 1, then set r0's value to 0+1 = 1, and remove the edge (l0,r0), from the graph. Since r0 only has one incident edge now, which is to l1, we can assign l1's value to 1, and remove both the edge (l1,r0) and node r0 from the graph. Finally, we remove l0 from the graph. Thus, the residual graph R(G1,l0) is:

And the decoding process is finished. If we download node l1, the process is similar, and the decoding process finishes. Thus, to compute the overhead of decoding graph G1, o(G1), it is:

4.2 Example 2: G2

Note, this is a graph that represents a residual graph of a download, where we already know l2's value, but it has not been downloaded yet. To decode, if we download either nodes l0 or l1, then we may determine the value of all nodes, and decoding is complete. If we download node l2, then we simply remove that node from the graph, and are left with graph G1 as a residual. Therefore, the overhead of decoding G2 is:

4.3 Example 3: G3

This is a simple systematic replication code, where l0 is the data bit, and l1 and l2 are the coding bits. To decode, when any of the three nodes is downloaded, the values of the other two may be assigned. Therefore, the overhead of G3 is:

4.4 Example 4: G4

This is the optimal systematic code for n=2,m=2 and l=5. The data nodes are l0 and l1, and the coding nodes are l2 and l3. To decode, we look at the residual graphs of downloading each of the left-hand nodes. Downloading l0 leaves us with a graph equivalent to G2, Downloading l1 leaves us with a graph equivalent to G3. Downloading l2 leaves us with a graph equivalent to G2, and downloading l3 leaves us with a graph equivalent to G3. Therefore, the overhead of decoding graph G4 is:

Note, that matches the overhead for the graph in the tables above.

5.0 Conclusion and Future Work

We will continue our exhaustive techniques until the graph sizes prove intractable for our computational power. Heuristics for enumerating unique bipartite graphs, and for indexing data structures by graphs will prove helpful.

Our initial exploration has illustrated trends in optimal graphs for m=2 and m=3. We will continue to explore these trends, and attempt to prove optimality for these codes for all values of n.

Finally, our exploration should help us define classes of graphs for larger values of n and m, which may not have optimal performance (or for which optimality cannot be proven), but which have good performance when compared to other evaluations of similarly sized graphs. As with this technical report, we hope to present such graphs so that the systems community, currently without any reference besides the asymptotic (and patented) techniques of Luby et al, have a methodology for constructing and using good systematic parity-check codes.

6.0 Acknowledgements

7.0 References

• [G63] R. G. Gallager, Low-Density Parity-Check Codes, MIT Press, Cambridge, MA, 1963.

• [LMS97] M. Luby, M. Mitzenmacher, A. Shokrollahi, D. Spielman and V. Stemann, "Practical Loss-Resilient Codes," 29th Annual ACM Symposium on Theory of Computing, 1997. pp. 150-159.

• [PT04] J. S. Plank and M. G. Thomason, "A Practical Analysis of Low-Density Parity-Check Erasure Codes for Wide-Area Storage Applications," DSN-2004: The International Conference on Dependable Systems and Networks, IEEE, June, 2004.

• [WK03] S. B. Wicker and S. Kim, Fundamentals of Codes, Graphs, and Iterative Decoding, Kluwer Academic Publishers, Norwell, MA, 2003. ISBN 1-4020-7264-3.