An algebraic approach to network coding pdf

While the results of Li et al. On the contain algebraic elements, i. The capacity of such networks is shown to to concepts from algebraic geometry opens up the opportunity be the maximum flow from the source to each receiver in the net- to employ very powerful theorems in well developed mathemat- work.

This approach may be generalized from directed acyclic ical disciplines. For networks which are restricted to using linear graphs to general directed graphs as long as we consider delays codes later we make precise the meaning of linear codes, since along the links.

Koetter is with the Coordinated Science Laboratory, University of Illinois possible delays due to coding. Links, however, are allowed to fail Digital Object Identifier For an early work pointing into this direction, refer to. Ayanoglu et al. Such failures are different from link er- random processes , rors, described by ergodic processes, which would be typically denotes the output at.

A connection dealt with by using channel coding. The failures we consider is established successfully if a pos- entail the permanent removal of an edge, such as would occur sibly delayed copy of is a subset of. We show that network coding can provide nections. We will make a number of simplifying assumptions. Moreover, we prove that there exist coding strategies that time unit. This is an assumption that can be satisfied to an do not require an adaptation to a specific link failure pattern.

If the capacity exceeds bits per time unit, we model this as parallel edges with unit II. Fractional capacities can be well approximated A communication network is a collection of directed links by choosing the time unit large enough. It may be rep- 2 Each link in the communication network has the same resented by a directed graph with a vertex set and delay.

We will allow for the case of zero delay, in which an edge set. We will allow multiple edges between two ver- case we call the network delay-free. We will always tices and hence, is a subset of , where the last assume that delay-free networks are acyclic in order to integer enumerates edges between two vertices. Edges links avoid stability problems. If no confusion can arise, we also denote edges simply dependent and have a constant and integral entropy rate as.

The and of an edge is de- of, e. The unit time is chosen noted by and. We define as the set of edges that end at a vertex This implies that the rate of any connection and as the set of edges originating at. Formally, we have is an integer equal to. This assumption can be satisfied with arbitrary accuracy by letting the time basis be large enough and by modeling a source of larger entropy rate as a number of parallel sources.

The in-degree of is defined as , while 4 The random processes are independent for dif- the out-degree is defined as. This assumption reflects the nature of a com- A network is called cyclic if it contains directed cycles, i. In particular, information that is in- there exists a sequence of edges jected into the network at different locations is assumed in. A network is called acyclic if it does not contain directed independent.

To each link we associate a nonnegative number In addition to the above constraints, we assume that commu- , called the capacity of. The length of the vectors is equal in all trans- a collection of discrete random processes that are missions and we assume that all links are synchronized with observable at node. We want to allow communication respect to the symbol timing. The random processes in at some different node. We define a processes , , and can, hence, be modeled as a triple , as discrete processes , where denotes the power set of.

The rate , and , of a connection is defined as that consist of a sequence of symbols from. Definition 1: Let be a delay-free communication For notational convenience, we will always assume that network. We say that is a -linear network, if for all links. The random process transmitted through link is denoted by.

In addition to the random processes in , node can observe random processes for all in. In general, where the coefficients and are elements of.

While it is straightforward to investigate the cesses that are transmitted on the links of the network. It is pos- solvability for a given failure pattern, finding common solutions sible to consider time-varying coefficients and and we for classes of failure patterns is a much more interesting task.

We call the network time-invariant or time-varying, depending on say that a network solution is static under a set of link failure this choice. Static processes for. It will be sufficient for the pur- solutions are particularly desirable because: pose of this paper to restrict ourselves to the case that 1 no new solution has to be found and distributed in the are also linear combinations of the , i.

Indeed, we The fundamental questions that we strive to answer in this will prove in Section III-A that, for linear networks, it suffices paper are the following. The concepts of Definition 1 are illustrated problem solvable? The main tools we will use for answering the above ques- tions involve concepts from algebraic geometry. In particular, we will relate the network coding problem to the problem of finding points on algebraic varieties, which is one of the central questions of algebraic geometry.

In Section III, we introduce part of the algebraic framework. The goal of the section is to make the reader familiar with some of the employed concepts. We point out the algebraic interpretation of this theorem in the context of the We emphasize that we can freely choose and the field Ford—Fulkerson algorithm. In particular, we In Section IV-A, we apply the algebraic framework to acyclic frequently choose to consider the algebraic closure of , networks.

We rapidly recover and extend the work of Li et al. In particular, we are able to an- of. Once we find suitable coefficients in , it is clear that swer some of the problems left open by the authors [9]. In Sec- these coefficients also lie in a finite extension of.

The ditions to guarantee the solvability of a network coding problem. This is equivalent to treated in Section V. The main surprising result is that robust finding elements , , and in a suitably chosen field multicast can be achieved with static solutions to the network such that all desired connections can be established suc- coding problem.

Section VI extends the results to networks with cessfully by the network. Such a set of numbers , , and delay and networks with cycles. If a solution exists, the network coding problem will be III. The solution is time-invariant time-varying if the , and are independent dependent of the time. In this section, we will develop some of the algebraic con- We also consider the case of networks that suffer from link cepts used throughout this paper.

Link failures are not assumed to be ergodic processes we will follow a simple example of a point-to-point connection and we assume that a link either is working perfectly or is ef- in the communication network given in Fig.

A link failure pattern can Let be a communication network. A between be identified with binary vectors of length such that each a node and is a partition of the vertex set of into two position in is associated with one edge in. If a link fails, we classes and of vertices such that contains assume that the corresponding position in equals one, other- and contains.

The value of the cut is defined as wise the entry in corresponding to the link equals zero. The fol- lowing set of equations governs the parameters , and and the random processes in the network. In particular, let matrices network with nodes representing the random processes to be transmitted in the and be defined as network.

The network problem is solvable if and only if the rate of the connection is less than or equal The system matrix is found to equal to the minimum value of all cuts between and. Proof: See [16] and [17]. The Ford—Fulkerson labeling algorithm [16] gives a way for finding a solution for point-to-point connections provided a net- work problem is solvable. The algorithm is graph theoretic by The determinant of matrix equals design and finds, under the assumptions made in Section II, a solution such that all parameters and in Definition 1.

We can choose parameters in an are either zero or one. Hence, we can choose as the identity matrix and elegant solution for point-to-point connections, the technique is so that the overall matrix is also an identity matrix. One not powerful enough to handle a more involved communications such solution found by the Ford—Fulkerson algorithm would scenario. In the remainder of this section, we develop some be to let while all other theory and notation necessary for more complex setups.

We first parameters of type are chosen to equal zero. Clearly, a consider a point-to-point setup. Let node be the only source point-to-point communication between and is possible in the network. We let at a rate of three bits per unit time. We note that, over the denote the vector of input processes observed at. Sim- algebraic closure there exists an infinite number of solutions ilarly, let be the only sink node in a network.

We let to the posed networking problem, namely, all assignments to be the vector of parameters which render a nonzero determinant of the output processes. The most important consequence of considering an - Inspecting Example 1, we see that the crucial prop- linear network is that we can give a transfer matrix describing erty of the network is that the equation the relationship between an input vector and an output vector admitted a choice.

Let be the system transfer matrix of a network with input of variables so that the polynomial did not evaluate to zero. For a fixed set of coefficients The following simple lemma will be the foundation of many , , and , is a matrix whose coefficients are existence proofs given in this paper. Hence, we mials over an infinite field in variables.

The following theorem makes the connection between the network transfer matrix an algebraic quantity , and the Min-Cut Max-Flow Theorem a graph-theoretic tool. Theorem 2: Let a linear network be given with source node , sink node , and a desired connection of rate. The following three statements are equivalent. We say that any edge transfer matrix is nonzero over the ring feeds into edge if is equal to.

We define the directed labeled line graph of as Proof: Most of the theorem is a direct consequence of with vertex set and edge set the Min-Cut Max-Flow Theorem. In particular, 1 and 2 are. Any edge is labeled equivalent by Theorem 3. In fact, the theorem only treats with the corresponding label. The Ford—Fulkerson algorithm thus We define the adjacency matrix of the graph with ele- yields edge-disjoint paths between source and sink ments given as nodes.

We show the equivalence of 1 and 3. This in turn will show the equivalence of 2 and 3. The Ford—Fulkerson algorithm implies that a solution to the linear network coding otherwise. Choosing this solution for the parameters Lemma 2: Let be the adjacency matrix of the labeled line of the linear network coding problem yields a solution such graph of a cycle-free network.

The matrix — has a polyno- that is the identity matrix and, hence, the determinant of mial inverse with coefficients in. Conversely, if the determinant of is nonzero graph is acyclic. Hence, we may assume that the vertices in over we can invert matrix are ordered according to an ancestral ordering.

It follows by choosing parameters accordingly. From Lemma 1, that is a strict upper-triangular matrix and, hence, — is we know that we can choose the parameters as to make this invertible in the field of definition of. The claim that the determinant nonzero. Hence, 3 implies 1 and the equivalence — is invertible in the ring of polynomials rather than the is shown. The third statement of Theorem 3 allows us to translate graph-theoretical properties as the vector of input processes on all vertices in.

Powerful algebraic tools can then be employed to ar- responding parameter equal to zero. It is worth- is a vector of length. In other words, if a solution to a point-to-point network problem exists, there also exists a solution restricted to the algebraic closure of the bi- otherwise.

Hence, there is no need or advantage to consider Similarly, let fields of other characteristic. Nevertheless, it is not clear if linear be coding strategies are sufficient for a general network problem. If is not a sink node of any In Section III-A, we investigate the structure of general transfer connection, we let be equal to zero. Let the entries of a matrix be defined as A. Transfer Matrices In a linear communication network of Definition 1, any node otherwise.

This relationship be- Example 2: We consider the network depicted in Fig. It is straightforward to verify that the path between nodes in the network are accounted for in the series. Matrix is nilpotent and eventually there will be a such that is the all zero matrix. Hence, we can write. The theorem follows. In the sequel, we will use a vector to denote the set of variables , and, hence, we consider as a matrix with elements in.

We will use the explicit form of the vector only if we want to make statements about a specific solution of a particular network problem. We conclude this section with a remark that it is sufficient b to form the output processes by a linear function of Fig. Indeed, provided a network labeled line graph. Labels in b are omitted for clarity. The edge e does not feed into any other edge and no edge feeds into e , which renders an isolated problem is solvable, let the output process be equal vertex in the labeled line graph.

By Definition 1, the pro- We assume that the network is supposed to accommo- cesses are a linear function of the input processes. We fix an ordering of edges as input, the function describes a vector space homomorphism , ,. In particular, we show that the error probability be linear combinations of the M original messages. Note, for hypercube-shaped LNC schemes is largely determined by however, that only linearly independent linear combinations the ratio of the squared minimum inter-coset distance and the are useful.

A receiver node will try to decode as many linearly variance of the effective noise in the high-SNR regime. This independent packets as possible, but obviously the number of result leads to several design criteria for LNC schemes: 1 the packets it is able to decode will depend on channel conditions.

Outline of the Paper inter-coset distance is maximized. In the remainder of the paper, we mainly focus on the Applying these criteria, we provide explicit algorithms communication problem at Layer 1, as it fundamentally sets up for choosing receiver parameters in Section V-B and give the problems to be solved at the higher layers.

In particular, we show that the problem of Layer 1. We introduce the nominal coding gain for lattice Criteria to construct LNC schemes using practical, finite- partitions — an important figure of merit for comparing dimensional, lattice partitions are not immediately obvious.

We then illustrate how to design lattice The purpose of this paper is to study practical LNC schemes partitions with large nominal coding gains. It is shown through both analysis Note that these properties are symmetric with respect to a and simulation that a nominal coding gain of 3 to 5 dB and b.

A more elaborate scheme, based on signal codes [25], is described in B. Modules [26]. Section VII concludes this paper. The following section presents some well-known mathemat- Modules are to rings as vector spaces are to fields.

An R-module framework. An R-submodule of M is a subset of M which itself forms In this section we recall some essential facts about principal an R-module. Let N be a submodule of M. Again, there is a natural projection see, e. A, called the ideal generated by A. An ideal generated by a There are several isomorphism theorems for modules.

The single element is called a principal ideal. Two elements a p. Congru- R-module homomorphism. The quotient Let M be an R-module. The set of all elements addition and multiplication operations on the cosets of I in R of R that annihilate M is called the annihilator of M , denoted in the usual way, as by Ann M.

A Gaussian integer is called a Gaussian prime if it is a prime in Z[i]. L to be finitely generated. If r1 ,. Thus, each Fig. Computing a linear function over a Gaussian multiple-access channel. Let w1 ,. The elements r1 ,. L X Theorems 2 and 3 are connected as follows. In matrix form, the objective of the receiver is III. This is achieved by applying a decoder In this section, we describe in more detail the physical- layer network coding problem at Layer 1.

A linear combination whose coefficient vector is predetermined. In matrix form, the decoder wishes to 1 Rmes , log2 W. Hence, the interpretation of SNR as the average other advantages over the basic setup.

Although not originally stated in m is some positive integer. Consider the encoder this form, some of the main results in [14] can be summarized as in the following theorem. SNR ah nations.

Architecture of the encoding and decoding methods for LNC. When R is a subring of C, as will be the case throughout be a discrete subring of C forming a principal ideal domain this paper, the use of a linear labelling induces a natural PID. Typical examples include the integer numbers Z and the compatibility between the C-linear arithmetic of the multiple- Gaussian integers Z[i].

An R-lattice of dimension access channel observed by the receiver, and the R-linear N in Cn is defined as the set of all R-linear combinations of arithmetic in the message space W , and this compatibility is N linearly independent vectors in Cn , i.

Algebraically, an R-lattice is an R-module. A high-level view of our generic LNC scheme is as follows. Throughout this decoder estimates one or more R-linear combinations from a paper, we only consider the case of finite lattice partitions, i. Encoding and Decoding We note that the encoder E is a standard Voronoi constel- We present a generic LNC scheme that makes no assump- lation encoder, as described, e. The encoding and decoding shaping region.

Such translation is We also note that a generalized lattice quantizer that satisfies easily implemented at the transmitters and accommodated by the property 5 e. A pseudorandom additive dither encoding and decoding operations. This may provide some can be implemented similarly. The rationale behind this decoding combinations.

Once these coefficient vectors are chosen, the architecture is explained by the following proposition. Algebraic Structure of Lattice Partitions seen shortly. L X integer m must be zero.

Moreover, 0. In this case, since p can be by using 12 and 13 whenever there exist generator matrices factored into two Gaussian primes, i. Constructions of Lattice Partitions sum up, the message space W is isomorphic to either a vector In the previous sections, we presented an algebraic frame- space over Fp2 or a direct sum of two vector spaces over Fp , work for studying a variety of LNC schemes.

In this sec- depending on the choice of the prime p. However, this generally requires the prime parameter p. We then apply the algebraic framework both the prime p and the dimension n to go to infinity.

In this way, we obtain a lattice partitions for LNC schemes. Construction A and lifted Construction D. Hence, we obtain a R. Without loss of generality, there exists a basis matrices satisfying the relation Construction D reduces to complex Construction A. When a lattice partition has triangular matrix with diagonal elements equal to 1. This corresponds to so-called space which is more complicated than a vector space.

In the sequel, Wpayload is given by we will provide an approximate upper bound for the error probability for LNC schemes that admit hypercube shaping.

Uniform ing union bound estimate UBE of the error probability. Let u be a predetermined note that the lattice partitions in Example 3 and Example 4 linear function. Theorem 7 has the following important implications. These two implications will be discussed fully in Sec. V-B Note that the effective noise n is not necessarily Gaussian, and Sec.

Here, we point out that, under hypercube making the analysis nontrivial. To alleviate this difficulty, we shaping, the effective noise n is a random vector with i. We call such feasible solutions the probability of decoding error is dominated solutions, as defined below. Recall that the linear combinations u1 ,. For ease of presenta- is as small as possible under the constraint that u1 ,.

This can be regarded as a constrained plex Construction A here, since similar methods apply to other minimum variance criterion, which will be explored next. Note that for complex Construction A, the linear independence of u1 ,. The existence of dominated a In the previous section, we derive a minimum variance solutions is proven in the following theorem. Hence, the results in [14] can be carried The proof is given in Appendix C. By by using a greedy search algorithm given as Algorithm 1.

It follows that 3. Thus, finding an optimal coefficient vector a is equivalent to 6. Our proposed method is in the spirit of ceiver has the freedom to choose m coefficient vectors. Then sphere-decoding algorithms, since sphere-decoding algorithms these coefficient vectors a1 ,.

We will role here, just as it does for sphere-decoding algorithms. We use complex Construction A as literature.

Among them, the LLL reduction algorithm is of a particular example, since similar methods can be applied to particular importance. Recently, the LLL reduction algorithm other constructions as well.

It is of MIMO communication. The maximized. IV-B to demonstrate the usefulness of this generalized R which are not units in R and which satisfy the divisibility code construction.

Let r be a nonzero, nonunit element of R. Suppose the We now propose explicit encoding and decoding methods factorization of r into distinct prime powers in R is for our generalized code construction.

Hence, we have the following theorem unless otherwise mentioned. Then it follows immediately that in [3]. This result implies that if p is also a prime in L Z[i], then the field size is actually p2 rather than p as claimed in [3]. Note that our mapping is given in 2. Smith normal form of the matrix J. An Example of Practical PNC Schemes Our generalized code construction together with encoding As another application of our algebraic framework, we and decoding methods provide an algebraic framework for present a concrete design example of PNC schemes.

Recall PNC. To demonstrate its potential, we provide two applications that the design space defined by our algebraic framework in this section. In contrast, we use [3] are constructed as follows. Signal codes are a special class of Z[i]-lattices simultaneously good for covering, quantization, and AWGN whose generator matrix is given by channel coding. In other words, we remove all the dithers. As a result, our encoder E is identical to that entries of J are from Z[i].

The shaping operator is identical to that in 0. By applying this operator, the heap-based stack decoder proposed in [7] can be used without any modification. We emphasize here this additional shaping operator does not 0. IV-B, we present simulation results for an illustrative 5 10 15 20 25 30 network scenario. We then discuss several more elaborate SNR dB designs that may achieve better performance in practice.

The Fig. Comparison of achievable throughput of PNC schemes using signal work along this line is in progress. Similar to [3], we consider a canonical Gaussian relay network with two transmitters and a single decoder, as depicted using nested lattice shaping can be made only 3. Two relays in the network are connected to the the sphere bound [10].

This makes it very attractive to be decoder through rate-limited bit pipes. For the purpose of used in our framework. IV-B, with VI. Gastpar [3] towards the design of PNC schemes via lattice z1 partitions for general network scenarios. Finally, we have presented an illustrative design x2 h22 R0 example to demonstrate the potential of our algebraic ap- z2 proach. We believe that we have merely scratched the surface Fig. A canonical Gaussian relay network.

We evaluate the performance in terms of the network throughput. Zhang, S. Liew, and P.