Induced Weights on Quotient Modules and an Application to Error Correction in Coherent Networks

We consider distance functions on a quotient module $M/K$ induced by distance functions on a module $M$. We define error-correction for codes in $M/K$ with respect to induced distance functions. For the case that the metric is induced by a homogeneous weight, we derive analogues of the Plotkin and Elias-Bassalygo bounds and give their asymptotic versions. These results have applications to coherent network error-correction in the presence of adversarial errors. We outline this connection, extending the linear network coding scheme introduced by Yang et al.

referred to as multicast. Successful delivery of all data packets to a sink requires at least m edge disjoint paths from the source to the sink. In a linear network coding scheme, at each node in the network linear combinations of packets on its incoming edges are transmitted along its outgoing edges. Transfer of data from source to sink nodes may be described by a transfer matrix, which can be assumed to be invertible if its coefficients are chosen from a large enough ring or field. Full details of this approach for a finite field alphabet may be read in [16]. A transfer matrix F is constructed as F = (I − K) −1 , where an entry of K is non-zero only if the corresponding entry of the adjacency matrix of the line graph of the network is non-zero, that is, if K 'fits' this adjacency matrix. Each column of F corresponds to an edge in the network; a particular sink only 'sees' the columns of F corresponding to the edges incident with it. The projection of F onto these columns yields a matrix whose row space is a linear code and the sink can retrieve all m packets if the particular m-subset of its rows (corresponding to the source packets) are linearly independent.
Error correction in the coherent network coding model is an important and challenging problem. A single (Hamming) error introduced in a link can propagate through the network infecting many other links. However, inherent redundancy in the network means that some error patterns are invisible to a given sink node, specifically, those error patterns corresponding to elements orthogonal to its code. Aside from these irrelevant errors, the code of a sink node may have some error correction capability.
In an effort to quantify these properties of a linear network code, in [26] the authors present refinements of the sphere-packing, Singleton and Gilbert-Varshamov bounds for an arbitrary linear error-correcting network code over a finite field. The error-model considered is for adversarial errors, that is, where it is assumed that an adversary has access to some number of edges in the network. The bounds in [26] and the references therein are implicitly bounds on the size of codes in a quotient vector space, with respect to a distance function induced by the Hamming distance on the original vector space.
In this work we continue this line of research, establishing refinements of the Plotkin and Elias-Bassalygo bounds for codes in quotient modules. Our results are of independent interest and can be expressed without direct reference to a network. However, in the context of network coding, we extend the framework of [26] to present a model that holds not only for finite field alphabets and Hamming errors, but also for their natural coding theoretic generalizations. When reduced to the finite field case, the bounds given here outperform the sphere-packing and Singleton bounds for some parameters, similar to the comparison of the Plotkin and Elias-Bassalygo bounds for classical Hamming codes.
In our setting, the underlying alphabet is a finite bimodule and the codes are equipped with a distance function induced by the homogeneous weight. This very general model includes the case where the alphabet is a finite field and the induced metric comes from the Hamming weight and so is a strict extension of the coding scheme described in [26]. More importantly, we develop upper bounds on codes associated with a fixed network based on the Plotkin and Elias bounds. These results are new both for the classical case of a finite field and in the more general case of a finite Frobenius bimodule 2 .
We will close this section with a motivating example from network coding, to show how codes in quotient spaces may arise in applications. In Section 2 we give preliminary facts on rings and modules relevant to the paper, and introduce weight functions on quotient modules induced from other weight functions. In Section 3 we discuss the homogeneous weight and its behaviour on Frobenius bimodules. In particular we note the character theoretic description of such weights in this case, which we require for the results given in Section 4. The main results of the paper are in Section 4, where we give analogues of the Plotkin and Elias-Bassalygo bounds for codes in quotient modules with respect to the induced homogeneous weight. We furthermore give asymptotic versions of these bounds. In Section 5 we describe how codes in quotient modules fit into a model of coherent network error-correction.

A Motivating Example from Network Coding
We give a simple example, in advance of giving a formal description of a network code.
Example 1. Consider the following network, whose source s emits 2 packets x 1 and x 2 along the edges a 1 and a 2 , and which has two sink nodes t 1 and t 2 as shown. The aim is that each sink should be able to retrieve both transmitted packets from the data it collects from its incident edges. The line-graph of the network has adjacency matrix as shown below on the left. If we treat this as a matrix K over F 2 then one possible invertible transfer matrix for the network is given by F = (I − K) −1 , as shown below on the right. 001100000000000  000011000000000  000000000010000  000000100000000  000000100000000  000000000000000  000000011000001  000000000000000  000000000001100  000000000010000  000000000001100  000000000000010  000000000000000  000000000000000 101100111010001  010011111001111  001000000011110  000100111001111  000010111001111  000001000000000  000000111001111  000000010000000  000000001001110  000000000111110  000000000011110  000000000001010  000000000000100  000000000000010 The word x = (x 1 , x 2 , 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0) ∈ F 15 2 corresponds to the source transmitting packets x i along its incident edges a i , i = 1, 2. This word traverses the network as The sink t 1 received the projection onto the 6th and 8th columns, which is the subvector (x 2 , x 1 + x 2 ), while the receiver at t 2 gets the projection onto coordinates 13, 14, 15 and so receives (x 2 , x 2 , x 1 + x 2 ). Both receivers can recover the source packets x 1 and x 2 . We may associate with each sink t i a code C i . If we let F 2 2 be the message space for each sink then C 1 = F 2 2 is an F 2 -[2, 2] code with generator matrix G 1 = 01 11 , found by projecting onto the 1st 2 rows and columns 6 and 8 of F. C 2 is an F 2 - [3,2] code with generator matrix G 2 = 001 111 found by projecting onto the 1st 2 rows and last 3 columns of F. In fact, we embed F 2 2 into F 15 2 to get a message space M = {(x 1 , x 2 , 0, 0, ..., 0) : x i ∈ F 2 }. We call F 1 the 15 × 2 matrix consisting of the 6th and 8th columns of F and we call F 2 the 15 × 3 matrix consisting of the last 3 columns of F.
Now suppose that an adversary can corrupt any links in the network by injecting errors. This may be represented by an error vector e ∈ F 15 2 , where e i is non-zero if an error occurs on the arc a i of the network. The error e propagates through the network as eF and the codeword c = xF is corrupted, resulting in the network word (x + e)F. The sink at t 1 gets the received word (x + e)F 1 = (x 2 + e 2 + e 6 , x 1 + x 2 + e 1 + e 2 + e 4 + e 5 + e 7 + e 8 ). If the error vector e has the form e = (e 1 , e 2 , e 3 , e 4 , e 5 , e 2 , e 7 , e 1 + e 2 + e 4 + e 5 + e 7 , e 9 , e 10 , ..., e 15 ), that is, if e is in the left nullspace K 1 of F 1 , then the received word is (x 2 , x 1 + x 2 ), which can be decoded. Otherwise, sink t 1 will incorrectly decode its received packets as x 1 + e 1 + e 4 + e 5 + e 6 + e 7 + e 8 and x 1 + x 2 + e 1 + e 2 + e 4 + e 5 + e 7 + e 8 . Errors in the kernel K 1 are 'invisible' to t 1 . Errors that lie outside K 1 cannot be corrected by the receiver. Therefore, it makes sense to identify the code C 1 as a subspace of the quotient space F 15 2 /K 1 and to measure the distance of an error to a codeword in this quotient space. For a distance function on F 15 2 , the induced weight of a coset w+K 1 may be defined to be the minimum weight over all elements of w+K 1 with respect to this original distance function (the weight of a coset leader). With respect to the Hamming metric, every non-zero word of C 1 has induced weight 1, since every coset of K 1 contains a word of Hamming weight 1 and hence C 1 corrects no errors. The code C 2 at t 2 can tolerate erasures in the first and second coordinates but not in the third. Let K 2 = {e ∈ F 15 2 : eF 2 = 0}, which has dimension 13 in F 15 2 . The 4 codewords of C 2 correspond to the following cosets of K 2 in F 15 2 : K 2 0 001 10 00000 00000 000 + K 2 1 110 00 10000 00000 000 + K 2 1 111 01 00000 00000 000 + K 2 1 C 2 is itself a subspace of F 3 2 and again all its elements have weight 1 with respect to the weight induced by the Hamming metric, so C 2 is 0-error-correcting. However, the receiver at t 2 can detect certain error patterns, namely those v for which vF 2 has different coordinates in the first two positions.

Modules, Quotients and Induced Metrics
In terms of the network code, which we define formally in Section 5, each constituent code will have the bimodule A as its alphabet and the intermediate node operations will be R-linear. For the weight function we consider in later sections, we will assume further properties of A , namely that it be a Frobenius bimodule.

Bimodules over a Finite Ring
Let R be a finite ring with unity and let A be a finite R-R bimodule. This means that A is both a left and right R-module satisfying (ra)r = r(ar) for all r ∈ R and a ∈ A . We write R A R to indicate that A is an R-R bimodule. The reader is referred to [1,15] for further background material on rings and modules.
Example 2. We give some examples of R-R bimodules A . There are many.
If R is commutative then any left R-module is an R-R bimodule. 8. The tensor product U ⊗V over Z is an R-R bimodule for a left R-module U and right R-module V . 9. For any finite ring R, its character moduleR := Hom(R, C × ) (the homomorphisms from (R, +) to the multiplicative group of C) is an R-R bimodule.

Submodules, Homomorphisms and Induced Weights
Definition 1. Let R be a finite ring and let M and N be left R-modules.
for any r 1 , r 2 ∈ R, a ∈ M. An R-homomorphism is defined similarly for right R-modules M and N. If M and N are both R-R bimodules then an In other words, f is an R-homomorphism from M to N as both left and right R-modules.
We'll write Hom( R M, R N) and Hom(M, N) to denote the R-linear left and bimodule homomorphisms, respectively from M to N. A submodule K of a bimodule M is both a left and right R-submodule of M.
We define a weight function, or weight on an R-module M to be a map w : Definition 2. Let M be a left (resp. right, resp. bi-) modules over a finite ring R. Let Definition 3. Let δ > 0. Let M be a left (resp. right, resp. bi-) module over a finite ring R and let K be an R-submodule of M. Let d be a distance function on M and letd be the distance function on M/K induced by d. We say that a non-empty subset C of M/K is a δ -error correcting code with respect tod if for any z + K ∈ M/K and c + K ∈ C satisfyingd(z + K, c + K) < δ , it holds that Now suppose that we have R-modules K, M with K a left (resp. right, resp. bi-) submodule of M. Let N be a left (resp. right, resp. bi-) R-module and let f be an Rmodule epimorphism from M to N as left (resp. right, resp. bi-) modules, with kernel K. Then a distance function d on M gives rise to an induced distance functiond on N defined byd( f (x), f (y)) =d(x + K, y + K). In particular, we have an isometry between (M/K,d) and (N,d).
Let n be a positive integer. We extend a weight function w of an R-module A to a weight function on A n in the obvious way: for any c = (c 1 , . . . , c n ) ∈ A n . Obviously, not all weight functions on A n can be derived in this way, but for the bounds we derive later we restrict to such weight functions. With respect to the application to coherent network coding we describe later, we will take M = A n , N = A N for a bimodule A .

Modules and Homogeneous Weights
The homogeneous weight was first introduced on the ring Z m in [5]. It is a very a natural generalization of the Hamming weight. On Z 4 it is given by the Lee weight which yields an isometry to F 2 2 under the Hamming weight. Generalizations of this weight function have appeared in [7,8,12]. In coding theory, codes whose alphabet is a finite Frobenius ring, or more generally is a finite Frobenius bimodule, play an important role. This is because these are the largest class of rings or modules such that fundamental theorems such as those extending the MacWilliams duality theorem and the MacWilliams extension theorem hold for ring-linear codes (see [6,7,22,23] and associated references for further details).

Homogeneous Weight Functions
Recall that a weight on an R-module M is a map w : M −→ R such that w(0) = 0. The homogeneity conditions in [7] are given by the following.
Right homogeneous weights are defined similarly. The value γ is the average weight of a cyclic left R-submodule. The homogeneity property says that this average value is independent A homogeneous weight function exists on any finite R-module and is unique up to choice of average weight γ [12].
The Lee weight is homogeneous on M with γ = 1.
Example 5. Let R = M = Z p k for a prime p. The weight function defined by In [7], the authors show that every finite unital ring R has a quasi-Frobenius bimodule, which is unique up to right and left R-isomorphism if the sum of its minimal left submodules is cyclic both as a left and right R-module. Such a module is then called a Frobenius bimodule.

Homogeneous Weights and Characters of a Bimodule
With respect to the R-R bimodule A we writeÂ to denote Hom Z (A , C × ), the group of characters of the additive group of A . ThenÂ is an R-R bimodule according to the relations r χ(x) = χ(xr), χ r (x) = χ(rx) for all r ∈ R, x ∈ A and χ ∈Â . A character χ ∈Â is called (left) generating if given any φ ∈R there is some r ∈ R satisfying φ = r χ. This is equivalent to the property that ker χ contains no non-zero left R-submodule of A . In [23] the authors show that every finite ring possesses a quasi-Frobenius bimodule and that this is moreover unique up to module isomorphism if its socle is cyclic as a module over R, in which case it is called a Frobenius bimodule. We refer the interested reader to that paper and the references given there for a detailed exposition. For the purposes of this paper, it is enough to observe the behaviour of the homogenous weight on such bimodules.
This gives a construction of a Frobenius bimodule R A R for a finite ring R: choose A to be the character moduleR of R. Any other Frobenius R-R bimodule is isomorphic to A =R. If R is a Frobenius ring then A = R itself is the canonical choice.
By duality, if R A R is Frobenius then RÂ ∼ = R R andÂ R ∼ = R R . In particular, if R A R is a Frobenius bimodule thenÂ is generated by a character χ both as a left and as a right R-module. It is exactly this property that makes the homogeneous weight behave so nicely on a Frobenius ring or bimodule, and is the reason why we restrict to this (large) class of modules. More precisely, the existence of such a generating character χ ∈Â gives the following characterisation of the homogeneous weight on a Frobenius bimodule (c.f. [10]). Lemma 1. Let R A R be a Frobenius bimodule with generating character χ. Then the weight function is homogeneous.

A Key Lemma
For a positive integer n, word z ∈ A n and set X ⊂ {1, ..., n} we define the projection of z onto the coordinates not in X by In other words, π X (x) is obtained by puncturing x on the coordinates of X.
Given an R-submodule M < A n , we define the support of M to be the set supp(M) := {i : z i = 0 for some z ∈ M}.
Using the character-theoretic description of the homogeneous weight given above we following result. The proof proceeds almost exactly as in [4, Lemma 1].
Lemma 2. Let R A R be a Frobenius bimodule with homogenous weight function w : A −→ R. Let n be a positive integer, let M be an R-submodule of A n and let x ∈ A n . Then ∑ c∈M w(x + c) = γ|M||supp(M)| + |M|w(π supp(M) (x)).
In particular, if the module M has full support then the average homogeneous weight of any coset of (M, +) has the same constant value γn.
Unless stated otherwise, for the remainder we will assume that A is a Frobenius R-R bimodule and that w denotes the homogeneous weight on A k for any positive integer k.

Upper Bounds on Codes in Quotient Modules
For the remainder of Section 4 we fix the following notation. Let n be a positive integer, let and let K be an submodule of of the R-R bimodule A n . Let M be a union of cosets of K in A n and let Letŵ be the weight function on A n /K induced by w with respect to K, soŵ(x) = w(u + K) := min{w(v) : v ∈ u + K}. Let d be the minimum distance of C with respect to the weight functionŵ that is, We furthermore fix s := |supp(M)| and := |supp(K)|.
Then |A | s ≥ |M|, |A | ≥ |K|. For this reason, we assume throughout the next two subsections that M has full support and so s = n, since otherwise we can simply derive upper bound on |C |, which has full support. In the application to network coding, we cannot assume that n = s, but for the purposes of the bounds we derive here, there is no loss of generality in making this assumption.
We now present two new upper bounds on |C|. Our results are generalizations of the Plotkin bound and of the Elias-Bassalygo bound for linear block codes and invoke these bounds for codes constructed as quotient modules. As in the classical case, the Plotkin-like bound is applicable for codes with high minimum distance (d > γs) and the Elias-Bassalygo bound is applicable for code with minimum distance upper-bounded by γs. Our results hold in particular for codes defined over finite fields (and are new in this case) with respect to the metric induced by the Hamming weight, but of course holds for a much larger class of alphabets.

A Plotkin-Like Upper Bound
Following the usual argument for the classical Plotkin bound, we obtain lower and upper bounds on ∑ c,c ∈Cd (c, c ). Proposition 2.1 of [9] gives a Plotkin bound for codes over finite Frobenius rings with respect to the homogeneous weight, which has the following easy extension for a code in A s .

Lemma 3. Let C ⊂ A s have support size s and have minimum homogeneous distance d(C ).
Then We are now ready to prove our first main result, which relies on the Lemma 3 (the Plotkin bound for the homogeneous weight) and on Lemma 2, which computes the average homogeneous weight of a coset.
If d > γs then PROOF. We give an estimate of the sum of the distances between ordered pairs of distinct codewords of C.
We compute the left-hand sum using Lemma 3 and the right-hand sum using Lemma 2, which yields: from which we get (2). In the case that d > γs we rearrange (2) to obtain the following upper bound on the size of C: Example 8. Let R = A = Z 4 . The Lee weight d L is homogeneous on Z 4 with γ = 1. Let K = 0111333 ⊂ Z 7 4 , which has support size 6. Then the distance functiond L on Z 7 4 /K induced by d L is the minimum Lee weight of each coset of K in Z has cardinality 2 and minimum distance 8, since the minimum Lee distance between elements of the different cosets is 8. Therefore, C is optimal with respect to Theorem 4.
For a concrete realization of C as a submodule of Z 6 4 , let f be a Z 4 -homomorphism of Z 7 4 that has K as its kernel. For example, say f is the map with following matrix representation in Z

An Elias Bassalygo Bound for Quotient Modules
We now give an upper bound on |C| for the case d < γs. We recall the following well-known lemma (see, for example [17,Lemma 5.2.9]).

Lemma 5. Let M be an additive group and let A, B be subsets of M. Then there exists
x ∈ M such that For each nonnegative real number r we definê which is the set of words z such that the average homomgeneous weight in the coset z + K is at most r. For a positive integer k, we denote by B k (r) ⊂ A k the standard sphere of radius r > 0 about zero with respect to the homogeneous weight w on A , that is Clearly for R = F q = A , this is the usual Hamming sphere. Setting A to be a translate ofB av (r) and B = C we deduce from Lemma 5 that For each vector x ∈ A s , we define Observe that if x + K = y + K for some x, y ∈ A s then π(x) = π(y).
PROOF. Since any x, y ∈ A s in the same coset of K satisfy π(x) = π(y), we see that the set on the right-hand-side is well defined. Let z + K ∈ A s /K. Applying Lemma 2, z + K ∈B av (r) if and only if which is true if and only if w(π(z)) ≤ r − γ .
Applying (3), along with Corollary 7 we now have the following result.
We now obtain an upper bound on the size ofB av (r) ∩C. First we define the anticode C(r) :=B av (r) ∩C.
Clearly, C(r), being a subset of C, has minimum induced distanced(C(r)) ≥ d.
We denote by C π (r) the multiset of words in A s− constructed by applying the puncturing map π to exactly one word from each distinct coset x + K in C(r), that is and the sum of the multiplicities of the members of C π (r) is |C(r)|. We will compute a lower bound on the sum of the distances between pairs of elements of C π (r), counting multiplicities.
We now obtain an upper bound on the sum of the weights of differences of members of C π (r), adapting the argument used in the classical Elias-Bassalygo bound.
PROOF. We may assume that supp(K) = {s − + 1, ..., s}. For each i ∈ {1, ..., s}, let m i (u) be the multiplicity of the element u ∈ A in the ith coordinate of C π (r). Therefore, Since A is a Frobenius bimodule the homogeneous weight takes the form given in Lemma 1, therefore, for each i ∈ {1, ..., s − } we have ∑ a,b∈A From the Cauchy-Schwarz inequality we have We therefore arrive at the inequality ∑ a,b∈A Again, using the Cauchy-Schwarz inequality we have that Let T := ∑ u∈C π (r) w(u). Recall that z ∈ C(r) only if the average homogeneous weight of the elements of z +K is at most r, in which case we have w(π(z)) ≤ r −γ . It follows that T ≤ |C(r)|(r − γ ). Since 2|C(r)|T − T 2 γ(s− ) is increasing on [0, |C(r)|γ(s − )], if r ≤ γs then |C(r)|(r − γ ) falls within this range, so we may write .
PROOF. Combine Theorems 9 and 11 to get which gives Therefore, under the hypothesis of the theorem, we have .
Finally, combining Theorems 8 and 12 we obtain the Elias-Bassalygo bound for codes in quotient modules.

Code Optimality
We use A(A : n, s, , d) to denote the maximum size of any code C in A n /K with induced minimum homogeneous distance d =d(C) over all possible choices of submodules K of A n with support size and such that the support of M = ∪ x∈C (x + K) has size s ≤ n. Clearly, if 2r ≤ d − 1, then from the usual sphere-packing argument we have: sinceB av (δ ) ⊂B(r). If δ ≥ γ , then using Corollary 7 we get We summarize the preceding as follows.
Theorem 14. Let n, s, , d be nonnegative integers satisfying n ≥ s ≥ . Then
As in the classical Hamming case, we will require an asymptotic expression for the size of the homogeneous sphere B k (δ k) ⊂ A k . This was essentially answered first in [18] and in a slightly different form (which we use here) in [9, Theorem 4.1] as follows: Lemma 15. For all δ ∈ [0, γ] there holds: Definition 7. Let δ ≥ 0. We define the function PROOF. If δ > γσ , then from Theorem 4 we have that α(A : σ , λ , δ ) = 0. Now suppose that δ ≤ γσ . Let C ⊂ A n /K be an optimal code and let d = δ n. Choose s to be the greatest integer satisfying γs ≤ d − 1. Then s − s > 0 and s > by our choice of s . Consider the words of M ⊂ A n . By a standard coding theory argument we can take s − s successive (affine) shortenings of M on its coordinates in supp(M)\supp(K) to arrive at a code in A n of order at least |M|/|A | s−s . Then puncture the code on these coordinates, as well as any coordinate not in supp(M), to obtain a code M ⊂ A s of the same order. The corresponding code K obtained by puncturing K on the same coordinates satisfies |K | = |K| and so the set of words of M is a union of at least |C|/|A | s−s distinct cosets of K in A s . This yields a code C satisfying d(C ) = d ≥ d > γs . Again apply Theorem 4 to get Then Theorem 17 (Asymptotic Elias Bound). Let ρ, δ > 0 and let σ , λ ∈ (0, 1). Suppose that γλ ≤ ρ, δ ≤ γσ and further that ρ Then lim n→∞ sup n −1 log |A | (A(A : n, σ n, λ n, δ n))) ≤ σ − λ − H A (ξ ).
In particular, PROOF. It is easy to see that n −1 log |A | h(ρ, σ , u, v) → 0 as n → 0. From Theorem 13, for σ , λ , δ , ρ as above, we have Since this holds true for any choice of ρ, by continuity of H A , the final inequality holds.
Similarly, we have an asymptotic sphere-packing bound.
In Figures 1,2 and 3 we compare these asymptotic bounds for codes over Z 4 and Z 8 .

Quotient Modules and Linear Network Coding
We define a communications network to be a directed acyclic graph N = (V, E), with a set of nodes or vertices V and an edge set E of order n. We assume that N has a single source node s incident with some m outgoing edges and has several sinks labelled by elements of a set T . A message of m packets is transmitted from the source node to be received at each sink in T . For each sink t ∈ T , let E t denote the set of edges incident with t and let |E t | = n t . We furthermore assume that n t ≥ m for each t and indeed that there are at least m edge disjoint paths connecting s to t. It is assumed that the network topology is known by the sender and the sinks, since we are working with a coherent network model.

Linear Network Codes
We now formally describe a network and what we mean by a linear code for a network, extending the definition given in [26] for the finite field case. Such a code will be a collection of codes (one for each sink). We do not require each code to itself be linear, the term 'linear' in this context refers to the fact that data traverses the network via sequences of R-linear homomorphisms. In other words, at each node in the network, linear combinations of packets on its incoming edges are transmitted along its outgoing edges. If the set of messages is itself a vector space or module, as in the Example 1, then so will be each code, however, we do not impose this restriction in general.
The network N has m edges with tail at the source node s and n edges in total. The set of messages of N is a subset M 0 of A m . We do not assume that M 0 is itself an R-module. Each message x 0 ∈ M 0 corresponds to a unique network word x = [x 0 , 0] in M := {[u, 0] : u ∈ M 0 } ⊂ A n , under the canonical embedding A m into A n . The network itself may be identified with A n , where each i-th coordinate projection from A n onto A corresponds to the i-th edge of the network, under some ordering.
A word z ∈ A n is transmitted along the network by an R-automorphism of A n that can be realized as an invertible transfer map of the form: .., f n (z)), for some R-linearly independent epimorphisms f j ∈ Hom(A n , A ). If x ∈ A n is transmitted from the source node s and some edges of the network are corrupted by er-rors in the form of an error word e ∈ A n then the network transmission is given by y = F (x + e). In other words, it is assumed that errors propagate through the network.
In [16], F is represented by an invertible transfer matrix F ∈ R n×n , R = F q , with respect to some fixed basis of R n . For the usual scalar linear network coding (as in [24,25,28]) we have the case R = A = F q . For vector linear network coding often described in the literature (e.g. [21]), we usually see R = F q and A = F q r or F r q . We now define a set of R-homomorphisms associated with each sink node. Each one will give rise to a code over A . For each sink t ∈ T , let Π t : A n −→ A n t : z → (z j ) j∈E t be the projection onto the coordinates indexed by the edges of the network incident with t. We further define maps In the multicast setting, for each t ∈ T , we require that F t : M −→ A n t be an injection, in order that each sink t can decode the transmitted word to the same unique message in M . Definition 8. Let N be a network with transfer map F ∈ Aut R (A n ). The network code for node t of (N , F ) is the set The network code of (N , F ) is the collection C := {C t : t ∈ T }.
We reiterate that neither M nor any C t need be an R-module; the linearity of C refers only to R-linearity of the transfer map F .
For the network message x ∈ A n and an error word e ∈ A n the word received by node t is y t = F t (x + e). We denote by K t the kernel of the map F t in A n so that C t = F t (M ) ⊂ A n t which is isomomorphic as a bimodule to A n /K t . Observe that if e ∈ K t then y t = F t (x + e) = F t (x) is received as if no errors have occurred. If m = n t , the kernel K t is trivial and the decoder will not detect any errors.
Given the received word y ∈ A n t , the decoder at node t decides that c = F t (x) has been transmitted if d t (z, c) < d t (z, c ) for all c ∈ C t . Example 9. Let R = A = F q and let w denote the usual Hamming weight on F n q . Let N be a network and let C t be a network code for N at one of its sink nodes t. F t has a representation as an n × n t matrix F t with respect to a chosen basis. Then w t (u) = min{w(z) : zF t = u, } = w(x + K t ) counts the minimum number of linearly independent rows of F t required to obtain a representation of u = xF t . If x ∈ M is transmitted and y is received at t, the decoder will decode to y − eF t ∈ C t for some error e ∈ F n q of least Hamming weight satisfying y = (x + e)F t . In other words, the decoder will assume that an adversary has tampered with the least number of network edges resulting in a non-trivial contribution to the received word y.
Let d t denote the minimum distance of C t with respect to d t . Let t be the size of the support of K t . For each t ∈ T , we write M t to denote the preimage of C t in A n , so that F t (M t ) = C t . We let s t denote the support of M t . We say that C is an (n, {(n t , s t t , |C t |, d t ) : t ∈ T }) network code. We define s(C ) := min{|C t | : t ∈ T }, which we call the size of C , and seek upper bounds on this number, which is the effective maximum possible size of the message space M . For example, with respect to this notation, the network code described in Example 1 is a Definition 9. We denote by A(n, {(n t , s t , t , d t ) : t ∈ T }) the maximum size s(C ) of any (n, {(n t , s t , t , |C t |, d t ) : t ∈ T }) network code C .
There are network coding analogues of the sphere-packing, Gilbert-Varshamov and Singleton bounds over finite fields [24,26]). With the results presented here, we now add Plotkin and Elias-Bassalygo bounds. For codes with alphabet F 2 , we give a graphical comparison of the Sphere-Packing, Singleton, Plotkin and Elias bounds, shown in