An algebraic framework for end-to-end
physical-layer network coding

arXiv:1611.04226v1 [cs.IT] 14 Nov 2016

Elisa Gorla and Alberto Ravagnani∗
Institut de Mathématiques
Université de Neuchâtel
Emile-Argand 11, CH-2000 Neuchâtel, Switzerland

Abstract
We propose an algebraic setup for end-to-end physical-layer network coding based on submodule transmission. We introduce a distance function between modules, describe how it relates
to information loss and errors, and show how to compute it. Then we propose a definition of
submodule error-correcting code, and investigate bounds and constructions for such codes.

Introduction and motivation
In the framework of physical-layer network coding (PNC) multiple terminals attempt to exchange
messages through intermediate relays. The relays collect data from the terminals, and try to decode
a function of the transmitted messages. Such function is then broadcasted to the terminals, which
combine it with their side information to recover the other messages.
In [11] the authors proposed a novel approach to PNC based on nested lattices, known as
“compute-and-forward”. Under this approach, the structure of a fixed underlying lattice is exploited
by the relays to decode the function of the messages, which is then forwarded to the terminals. As
observed in [5], this communication scheme induces an end-to-end network coding channel with
channel equation
Y = AX + Z.
(1)
Here X is the transmitted matrix, whose rows are elements from a given ambient space Ω, A is
a transfer matrix, and Z is an error matrix. In practice, A and Z are random matrices drawn
according to certain distributions, that depend on the application at hand.
A general algebraic framework to study and construct nested-lattice-based PNC schemes was
recently proposed in [5] and further developed in [4]. Following this algebraic description, which is
compatible with any underlying lattice, the message space Ω has the structure of a module over a
principal ideal ring
Ω = T /(d1 ) × T /(d2 ) × . . . × T /(dn ),
where T ⊆ C is a principal ideal domain (PID), d1 , d2 ..., dn ∈ T are nonzero, non-invertible elements,
and dn |dn−1 | . . . |d1 . Let R = T /(d1 ), then R is a principal ideal ring (PIR). The ambient space Ω
is isomorphic to an R-submodule of Rn :
Ω∼
= R × (d1 /d2 ) × . . . × (d1 /dn ) ⊆ Rn .
∗

(2)

E-mail addresses: elisa.gorla@unine.ch, ravagnani@ece.utoronto.ca. The authors were partially supported
by the Swiss National Science Foundation through grant no. 200021 150207.

1

In particular, the elements of Ω can be represented via vectors of length n with entries in R. Both
R and Ω are usually finite.
Examples 1. We include a list of rings R and ambient spaces Ω that have been proposed in the
context of physical-layer network coding, producing efficient communication schemes.
• R = Ω = Z2 [i], proposed and studied in [15], [12] and [4, Example 1] for BPSK modulation.
• R = Ω = Zm [i], with m a positive integer, proposed and studied in [15] and [4, Example 2],
and known as “m2 -QAM PNC scheme”.
• R = Zp [i], Ω = Rn , where p is a prime number, proposed in [11].
• R = Zps [i], Ω = R
. . × R} × (p) × . . . × (p) × . . . × (ps−1 ) × . . . × (ps−1 ), where p is a prime
| × .{z
{z
}
{z
}
|
|
n1

n2

ns

power and s ≥ 1 is an integer, proposed in [4, Section VII.A].

• R = Z[ω]/(β), where Z[ω] are the Eisenstein integers and β ∈ Z[ω] is a suitable element,
Ω = Rn , proposed and studied in [13].
As observed in [5], channel equation (1) suggests to define the message to be transmitted as the
module generated over R by the rows of the matrix X, which we denote by row(X). A receiver
attempts to recover the original transmitted module from the matrix Y .
Two important special cases of equation (1) correspond to the noise-free multiplicative matrix channel (MMC), with equation Y = AX, and the multiplication-free additive matrix
channel (AMC), with equation Y = X + Z. These two channel equations are studied in [5] in the
case where the base ring R is a finite chain ring.
The key tool in handling the MMC in [5] is the reduced row-echelon form of a matrix X, which
is a canonical invariant of the row-module of X denoted by RREF(X). In practice, a transmitter
emits a matrix X in reduced row-echelon form, and a receiver attempts to recover it by computing
RREF(Y ) = RREF(AX). Decoding is successful when A is left-invertible. In the same paper, the
authors propose a coding/decoding scheme based on error-trapping for the AMC and the general
case of a channel with equation (1).
In this paper, in analogy with the approach from [8] for random linear network coding, we
propose a new algebraic framework for module transmission based on the notion of length of a
module. We define a submodule code as a collection of submodules of the ambient space Ω, and
propose a notion of distance between submodules based on length, which we call submodule distance.
Then we show that the submodule distance captures both information loss and errors in module
transmissions. The row-echelon form for modules over a PIR proposed by Buchmann and Neis in [2]
allows us to represent messages in a canonical way. Using the same row-echelon form, we reduce
the computation of the distance between submodules to the computation of the length of ideals in
the base ring. We also prove that, in some cases, the error-trapping decoding scheme from [5] is a
minimum-distance decoding with respect to the submodule distance.
We derive two bounds on the cardinality of a submodule code of given minimum distance and
whose codewords have fixed length. For certain classes of rings, we are able to state our bounds
explicitly in terms of the ring and code’s invariants. We also construct submodule codes with
maximum error-correction capability. For R a finite chain ring or R = Zp [i], we show that the codes
that we construct have asymptotically optimal cardinality for their parameters. This also shows
that our bounds are sharp for certain choices of rings and code parameters. We also give some
general code constructions, based on the tensor and on the cartesian product. Our constructions
can be applied to various choices of rings and code parameters.
2

Finally, we study codes over products of rings. This is relevant, since a finite PIR R is isomorphic
to a product of finite fields and finite chain rings. We show that if R ∼
= R1 ×. . .×Rm , then a product
of codes on the Ri ’s yields a code on R, whose parameters are determined and whose decoding can
be reduced to decoding on each of the Ri ’s. However, not every code over a finite PIR is a product
of codes over fields and finite chain rings. We give a construction of a code over R which is not a
product and show that decoding cannot be reduced to decoding on each of the Ri ’s. This shows in
particular how the study of codes over a finite PIR cannot be reduced to the study of codes over
finite fields and finite chain rings.
The structure of the paper is as follows: In Section 1 we recall some definitions and results about
PIR’s, modules, length, row-echelon forms of matrices over PIR’s. In Section 2 we define submodule
codes and submodule distance, and relate it to information loss and errors in module transmissions.
We also show how to efficiently compute the submodule distance. In Section 3 we prove that, in
some cases, the error-trapping decoding from [5] can be viewed as a minimum-distance decoding in
our framework. Section 4 is devoted to bounds on the cardinality of submodule codes, and Section
5 to submodule codes constructions and to codes over products of rings.

1

Algebraic preliminaries

Throughout the paper R denotes a finite PIR and (r) denotes the ideal generated by r ∈ R. Recall
that elements a, b ∈ R generate the same ideal if and only if they are associate, i.e., there exists
an invertible element ε ∈ R with a = εb (see e.g. [1]). An element g ∈ R is a greatest common
divisor (gcd) of a1 , ..., as ∈ R if and only if (a1 )+(a2 )+. . .+(as ) = (g). We write g = gcd(a1 , ..., as ).
The gcd is unique up to associates.
Finite chain rings are a special case of PIR’s. A ring R is a finite chain ring if it is finite
and its ideals form a chain with respect to inclusion. It is well-known that finite chain rings are
principal and local (see e.g. [10], page 339). Moreover, if π is a generator of the maximal ideal of
R, then the ideals of R are
0 ( (π e−1 ) ( (π e−2 ) ( . . . ( (π) ( R,

(3)

where e is the smallest positive integer with π e = 0. The integer e does not depend on the choice
of the generator π of the maximal ideal. The finite field R/(π) is called the residue field of R.
Clearly, R/(π) ∼
= Fq for some prime power q.
For any PIR R, define the annihilator of a ∈ R as
ann(a) = {r ∈ R | ar = 0}.
The annihilator is an ideal of R, and we refer to a generator of ann(a) again as the annihilator of a.
If R is a finite chain ring with ideal chain as in (3), then every a ∈ R is of the form a = uπ α for some
invertible u and some 0 ≤ α ≤ e. Then ann(a) = (π e−α ). Since every finite PIR R is isomorphic
to a product of finite fields and finite chain rings, then annihilators are easy to compute. In the
sequel, we will take computation of annihilators for granted. Moreover, inclusion of annihilators
can be easily tested by checking divisibility.
Proposition 2. Let R be a finite PIR, a, b ∈ R. Then ann(a) ⊆ ann(b) if and only if a | b.
Proof. By the Zariski-Samuel Theorem, any finite PIR is isomorphic to a product of finite fields
and finite chain rings. Hence it suffices to prove the statement for R a finite chain ring. If b = ac
for some c ∈ R, then tb = tac = 0 for every t ∈ ann(a). Hence ann(a) ⊆ ann(b). Conversely, if
3

ann(a) ⊆ ann(b) and R is a finite chain ring with ideal chain as in (3), then a = uπ α and b = vπ β
for some u, v invertible, 0 ≤ α, β ≤ e. Since (π e−α ) = ann(a) ⊆ ann(b) = (π e−β ), then e − α ≥ e − β,
so α ≤ β and a | b.

1.1

Modules and length

We fix an R-module Ω ⊆ Rn as in (2) and let M(Ω) denote the set of R-submodules of Ω. Given
M, N ∈ M(Ω), denote by M + N the smallest submodule of Ω which contains both M and N . We
write M ⊕ N when N ∩ M = 0. Since R is finite, Ω and its submodules are finite. In particular all
modules that we consider are finitely generated.
Definition 3. Let M be an R-module. If
M = {r1 m1 + . . . + rt mt | r1 , . . . , rt ∈ R}
for some m1 , . . . , mt ∈ M , then we say that M is generated by m1 , . . . , mt and m1 , . . . , mt are a
system of generators for M . We write M = hm1 , . . . , mt iR or M = hm1 , . . . , mt i when there is
no ambiguity. A module is finitely generated if it has a finite system of generators.
Definition 4. Let M be an R-module. A chain of distinct submodules of M of the form
0 ( M1 ( M2 ( . . . ( Mλ = M
has length λ. The length of M is
λR (M ) = max{λ | M has a chain of R-submodules of length λ}.
A composition series for M is a maximal chain of distinct R-submodules of M .
When the ring is clear from context, we will omit the subscript R.
Remark 5. Any ring R is an R-module, and its R-submodules coincide with its ideals. Therefore,
the length of a ring R is
λ(R) = max{λ | R has a chain of ideals of length λ}.
For any a ∈ R we denote by λ(a) the length of the ideal generated by a.
Since all modules that we consider are finite, they have finite length. The following properties
are well-known (see e.g. [9, Section V§2]).
Lemma 6. Let R be a ring, let M, N, Ω be R-modules of finite length. Then:
1) λ(M ) = 0 if and only if M = 0.
2) If N ⊆ M , then λ(N ) ≤ λ(M ) and λ(M/N ) = λ(M ) − λ(N ). In particular, λ(M ) = λ(N ) if
and only if M = N .
3) If M, N ⊆ Ω, then λ(M + N ) = λ(M ) + λ(N ) − λ(M ∩ N ).
4) λ(M × N ) = λ(M ) + λ(N ).
The concept of length for an R-module generalizes the concept of dimension for a vector space.

4

Example 7 (fields). Every field F is a ring of length one, since it has no proper nonzero ideals. An
F-module M is an F-vector space with λ(M ) = dimF (M ).
Example 8 (finite chain rings). Let R be a finite chain ring. Let π be a generator of its maximal
ideal and let e be the smallest positive integer such that π e = 0. Then λ(R) = e and λ(a) = min{i :
a ∈ (π e−i )} = min{i : π e−i | a} for all a ∈ R.
It can be shown that every R-module M is isomorphic to a product of ideals:
∼ R × . . . × R × (π) × . . . × (π) × . . . × (π e−1 ) × . . . × (π e−1 ),
M=
{z
} |
|
|
{z
}
{z
}
µ1

µ2 −µ1

µe −µe−1

where 0 ≤ µ1 ≤ µ2 ≤ . . . ≤ µe are non-negative integers. Following [5], we say that M has shape
(µ1 , µ2 , ..., µe ) ∈ Ne . It is easy to show that two R-modules are isomorphic if and only if they have
the same shape. Moreover, by Lemma 6
λ(M ) =

e−1
X
(µi+1 − µi )(e − i),
i=0

where µ0 = 0.

1.2

A reduced row-echelon form for matrices over principal ideal rings

Every finitely generated module M ⊆ Ω may be represented as the rowspace of a matrix with entries
in R, whose row vectors are a system of generators of M . In order to make such a representation
unique, we need a row-canonical form for matrices with entries in a PIR.
In [7] Howell proposes a definition of row-canonical matrix over the ring Zn , showing that every
matrix can be put in row-canonical form by performing invertible row operations. The ideas of
Howell were later extended in [2], where canonical generating systems for submodules of Rn are
defined for any PIR R. In the rest of the section we recall the main results of [2], stating them in
a convenient matrix formulation.
Definition 9. For i ∈ {1, ..., n} we denote by vi the i-th entry of a vector v ∈ Rn . The leading
position of a vector v ∈ Rn is the position of its first nonzero entry:

min{1 ≤ j ≤ k | vj 6= 0} if v 6= 0,
ℓ(v) =
+∞
if v = 0.
Given a matrix A ∈ Rt×n , we denote by A1 , ..., At the rows of A, and by row(A) = hA1 , ..., At i
the R-module generated by the rows of A.
For a module M ⊆ Rn we set M (j) = {v ∈ M | vi = 0 for i < j} for j ∈ {1, ..., n + 1}. Every
M (j) is an R-submodule of M and
0 = M (n+1) ⊆ M (n) ⊆ . . . ⊆ M (1) = M.
Definition 10. Let A ∈ Rt×k be a matrix, and let M = row(A). We say that A is in row-echelon
form if the following hold:
1) for all i ∈ {1, ..., t − 1} we have ℓ(Ai+1 ) > ℓ(Ai ),
2) for all j ∈ {1, ..., n + 1} we have M (j) = hAi | ℓ(Ai ) ≥ ji.

5

The nonzero entries of A of the form Ai,ℓ(Ai ) are the pivots of A.
Fix canonical generators and representatives for the ideals and the residue classes of R. We say
that A is in reduced row-echelon form if it is in row-echelon form and the following hold:
3) every pivot Aij of A is the canonical generator of the ideal (Aij ),
4) if Aij is a pivot of A, then every entry Asj with s < i is the canonical representative of the
residue class Asj + (Aij ).
Definition 11. Two matrices A, B ∈ Rt×n are row-equivalent if there exists an invertible matrix
U ∈ Rt×t such that A = U B.
It is easy to show that A and B are row-equivalent if and only if row(A) = row(B). We now
prove that every matrix is row-equivalent to a matrix in row-echelon form, and to a unique matrix
in reduced row-echelon form. The next lemma is well-known and appears in several references. We
include a proof, since we could not find a complete one in the literature.
Lemma 12. For any a, b ∈ R \ {0} there exist x, y, z, t ∈ R such that

   
x y a
g
=
,
xt − yz = 1,
(g) = (a) + (b).
z t b
0
Proof. By [14, Theorem 33, pg. 245], every principal ideal ring is isomorphic to a direct product of
quotients of PID’s. Therefore it suffices to prove the result for R = D/(π), where D is a PID and
π ∈ D.
If π = 0 then R = D is a PID. Let g = gcd(a, b) and write g = ka + hb for some k, h ∈ R.
Dividing by g we obtain 1 = k(a/g) + h(b/g). Let x = k, y = h, z = −b/g, t = a/g.
Now assume π 6= 0. Recall that every PID D is a unique factorization domain. Consider
the projection map ¯· : D → R and choose elements α, β ∈ D with α = a and β = b. Let
η = gcd(α, β, π) and P = {p ∈ D | p is irreducible and divides both α/η and π/η}. For all p ∈ P
we set ep = max{i | pi divides π/η}. Define

Q
(π/η) / p∈P pep if P 6= ∅,
γ=
(π/η)
if P = ∅.
We claim that α/η + γ(β/η) and π/η are Q
coprime. By contradiction, let p ∈ D be irreducible,
β/η, π/η) = 1
p | gcd(π/η, α/η + γ(β/η)). If p ∤ γ, then p | p∈P pep , so p | (α/η). Since gcd(α/η,
Q
and p | (α/η), (π/η), then p ∤ α/η + γ(β/η), a contradiction. If p | γ, then p ∤ p∈P pep , so p ∤ (α/η).
However p | (α/η + γ(β/η)), a contradiction. We conclude that α/η + γ(β/η) and π/η are coprime,
hence there exist λ, µ ∈ D such that λ(α/η + γ(β/η)) + µ(π/η) = 1, i.e. λ(α + γβ) + µπ = η. Hence
(η) ⊆ (α + γβ, π) ⊆ (α, β, π) = (η).
Therefore (α + γβ) + (π) = (α) + (β) + (π), so a + cb = gcd(a, b) in R = D/(π), where c = γ. Write
b = h(a + cb), for some h ∈ R. Let x = 1, y = c, z = −h, t = −ch + 1.
Remark 13. The element γ ∈ D in the proof of Lemma 12 can be computed (up to associates)
via the following algorithm.
γ := π/η
g := gcd(γ, α/η)
while g 6= 1 do
6

γ ← γ/g
g ← gcd(γ, α/η)
end while
Theorem 14 ([2], Algorithm 3.2 and Theorem 3.3). Given a matrix A ∈ Rt×k , we can compute a
row-equivalent matrix in row-echelon form in O(tk2 ) operations in R.
We describe Algorithm 3.2 from [2], adapting it to our matrix notation.
1) If A is the zero matrix, then it is already in row-echelon form. Otherwise, up to permuting the
rows of A, we may assume without loss of generality that +∞ > ℓ(A1 ) ≥ ℓ(A2 ) ≥ . . . ≥ ℓ(At ).
2) If j = ℓ(A1 ) > ℓ(A2 ) then the first step is concluded. Otherwise, let g = gcd(A1j , A2j , ..., Atj ).
Applying Lemma 12 iteratively one finds a row-equivalent matrix A′ ∈ Rt×n with A′1j = g
and ℓ(A′i ) > j for i > 1.
3) Let x ∈ R be the annihilator of g. We append x · A1 to the matrix A′ , obtaining a matrix
A′′ . Notice that row(A′′ ) = row(A). Moreover, if v ∈ row(A′′ ) and vs = 0 for 1 ≤ s ≤ j, then
v ∈ hA′′2 , ..., A′′t+1 i.
One repeats the three steps above on the matrix obtained from A′′ by deleting the first row, until
there are no more rows left. The algorithm produces a matrix in row-echelon form, which is rowequivalent to A.
Example 15. Consider the matrix



2 1 3
A=
4 1 2

over R = Z6 . Applying the algorithm that we just described, one computes:








2 1 3
2 1 3
2 1 3
2 1 3
0 5 2 .
0 5 2
4 1 2
0 5 2
0 0 3
0 3 3

Notice that the number of rows increased from two to three.

Fix generators and representatives for the ideals and residue classes of R. Every matrix A with
entries in R is row-equivalent to a unique matrix in reduced row-echelon form, with respect to the
given choice of generators and representatives.
Theorem 16 ([2], Algorithm 3.4 and Theorem 3.5). Let A ∈ Rt×n be a matrix. Then A is rowequivalent to a unique matrix in reduced row-echelon form, which we denote by RREF(A). The
reduced row-echelon form of A can be computed from a row-echelon form of A in O(n3 ) operations
in R.
In fact, using the algorithm from Theorem 14, A can be put in row-echelon form. After multiplying it by a diagonal matrix with invertible elements on the diagonal, the matrix satisfies property
3) of Definition 10. Finally, by subtracting suitable multiples of each row from the rows above, one
ensures that property 4) of Definition 10 holds. The last operation corresponds to multiplying on
the left by an upper triangular matrix with ones on the diagonal.
The next result characterizes matrices in row-echelon form over a finite PIR. A proof can be
obtained using Proposition 2.

7

Proposition 17. Let A ∈ Rt×n be a matrix with no zero rows. A is in row-echelon form if and
only if the following hold:
1. ℓ(Ai+1 ) > ℓ(Ai ) for all i ∈ {1, ..., t − 1},
2. Atℓ(At ) | Atj for all ℓ(At ) ≤ j ≤ n,
3. ann(Aiℓ(Ai ) ) · Ai ∈ hAi+1 , ..., At i for all i ∈ {1, ..., t − 1}.
Proposition 17 and Algorithm 4.1 of [2] lead to the following algorithm to test whether a matrix
is in row-echelon form.
Input: a matrix A ∈ Rt×n with ℓ(Ai+1 ) > ℓ(Ai ) for all i ∈ {1, ..., t − 1}
Output: “YES” if A is in row-echelon form, and “NO” otherwise
for i = 1 to t do
ji := ℓ(Ai )
end for
for j = jt to n do
if Atjt ∤ Atj then
return NO
quit
end if
end for
for i = t − 1 downto 1 do
use Algorithm 4.1 of [2] to test if ann(Aiji ) · Ai ∈ hAi+1 , ..., At i
if ann(Aiji ) · Ai ∈
/ hAi+1 , ..., At i then
return NO
quit
end if
end for
return YES
quit
Proposition 18. The previous algorithm terminates correctly.
Proof. Algorithm 4.1 of [2] tests whether a given vector belongs to the module generated by the
rows of a matrix in row-echelon form. Therefore, we first need to show that the last for cycle of the
algorithm is well-defined, i.e., that if the algorithm enters the for cycle for some i, then the matrix
whose rows are Ai+1 , ..., At is in row-echelon form.
We proceed by backward induction on i ∈ {t − 1, ..., 1}. Assume that the algorithm enters the
cycle for i = t − 1. Then by the structure of the algorithm and Proposition 17, the matrix whose
row is At is in row-echelon form, as claimed. Now assume i < t − 1. Since the algorithm enters
the for cycle for i, it entered the for cycle also for i + 1. By induction hypothesis, the matrix
whose rows are Ai+2 , ..., At is in row-echelon form. Since the algorithm enters the for cycle for i,
we have ann(Ai+1 ) · Ai+1 ∈ hAi+2 , ..., At i. Therefore by Proposition 17 the matrix whose rows are
Ai+1 , ..., At is in row-echelon form.
The previous argument also shows that if the algorithm returns YES, then A is in row-echelon
form. Finally, using Proposition 17 one can check that if A is in row-echelon form, then the algorithm
returns YES.

8

2

Submodule codes and submodule distance

Using the length, one can define a distance function between submodules of Ω.
Proposition 19. The function d : M(Ω) × M(Ω) → N defined by
d(M, N ) = λ(M ) + λ(N ) − 2λ(M ∩ N )
for all M, N ∈ M(Ω) is a distance function.
Definition 20. We call d the submodule distance on M(Ω).
Proof of Proposition 19. Let M, N, P ⊆ Ω be R-submodules. By Lemma 6 we have d(M, N ) =
λ(M + N ) − λ(M ∩ N ). Since M ∩ N ⊆ M + N we have d(M, N ) ≥ 0, and equality holds if and
only if M + N = M ∩ N , i.e., if and only if M = N . Moreover, d(M, N ) = d(N, M ) by definition.
To prove the triangular inequality, observe that by definition
d(M, N ) = d(M, P ) + d(P, N ) − 2(λ(M ∩ N ) + λ(P ) − λ(M ∩ P ) − λ(N ∩ P )).
Therefore it suffices to prove that x = λ(M ∩ N ) + λ(P ) − λ(M ∩ P ) − λ(N ∩ P ) ≥ 0. By Lemma 6
we have x = λ(M + P ) + λ(N + P ) − λ(M + N ) − λ(P ). Since (M + P ) + (N + P ) ⊇ M + N and
(M + P ) ∩ (N + P ) ⊇ P , by Lemma 6
λ(M + P ) + λ(N + P ) − λ(P ) ≥ λ(M + P ) + λ(N + P ) − λ((M + P ) ∩ (N + P )) ≥ λ(M + N ),
hence x ≥ 0.
When R = F is a field, the submodule distance on Fn coincides with the subspace distance
proposed by Kötter and Kschischang in [8] for error correction in random linear network coding.
The concepts of information loss and error from [8] can be extended to our setting as follows.
Remark 21. Let M ⊆ Rn be the transmitted module, and let N ⊆ Rn be the received module.
The portion of information that was correctly transmitted is M ∩ N . The quotient M/(M ∩ N )
may be regarded as the information loss module, i.e. the original information modulo the
portion of information that was correctly transmitted. Similarly, the error module is the quotient
N/(M ∩ N ). Using Lemma 6, one can check that
d(M, N ) = λ(M/(M ∩ N )) + λ(N/(M ∩ N )).
In other words, the distance between M and N is the sum of the lengths of the information loss
module and of the error module, similarly to what was shown in [8] in the context of subspace codes.
Definition 22. A submodule code is a subset C ⊆ M(Ω) with |C| ≥ 2. The minimum
(submodule) distance of C is
d(C) = min{d(M, N ) : M, N ∈ C, M 6= N }.
Definition 23. Let C ⊆ M(Ω) be a submodule code. Let M ∈ C be the transmitted module, and
let N ∈ M(Rn ) be the received module. Define the number of erasures as ρ = λ(M/(M ∩ N ))
and the number of errors as e = λ(N/(M ∩ N )).
The next result follows from Remark 21 using a standard argument.
Proposition 24. Let C ⊆ M(Ω) be a submodule code of minimum distance d. Then a minimum
distance decoder successfully corrects N to M , provided that 2(ρ + e) < d(C).
9

2.1

Computing the distance function

In this subsection we show that the length of a module is the sum of the lengths of the ideals
generated by the pivots of a matrix in row-echelon form, whose rows generate the module. Therefore,
computing the length of an R-module can be reduced to computing lengths of ideals in R. This
allows us to efficiently compute distances between submodules of Rn .
Theorem 25. Let M ⊆ Rn be an R-module. Let A ∈ Rt×n be a matrix in row-echelon form with
no zero rows and such that M = row(A). For every j ∈ {1, ..., n + 1} let M (j) = {m ∈ M | vi =
0 for i < j} ⊆ Rn and I (j) = (vj | v ∈ M (j) ) ⊆ R. Let Aiℓ(Ai ) be the pivot of the i-th row of A.
Then:

1) I (ℓ(Ai )) = Aiℓ(Ai ) ∼
= M (j) /M (j+1) for all i ∈ {1, ..., t},

P
2) λ(M ) = ti=1 λ Aiℓ(Ai ) .

Proof.
1) The map M (j) /M (j+1) → I (j) given by v + M (j+1) 7→ vj is a well-defined R-module
isomorphism. Therefore I (j) ∼
= M (j) /M (j+1) . Fix any i ∈ {1, ..., t} and let j = ℓ(Ai ). Since
(j)
(j)
(j)
Ai ∈ M we have (Aij ) ⊆ I (j) . On the other hand,
Pt let 0 6= x ∈ I and let v ∈ M such
that x = vj . Since A is in row-echelon form, v = k=i rk Ak for some ri , ..., rt ∈ R. Therefore
x = vj = ri Aij , so x ∈ (Aij ).
2) Applying [9, Corollary V.2.4] to the chain of R-modules 0 = M (n+1) ⊆ . . . ⊆ M (1) = M we
obtain
n


X
λ M (j) /M (j+1) .
λ(M ) =
j=1


(j+1)

6= 0 if and only if I (j) 6= 0, if and only if j = ℓ(Ai ) for
By Lemma 6 one has λ M (j) /M
some i ∈ {1, . . . , t}. Then


λ M (j) /M (j+1) = λ(Aij ).
Example 26. The module M = h(2, 1, 3), (4, 1, 2)i ⊆ Z36 generated by the rows of the matrix of
Example 15 has length λ(M ) = λ(2) + λ(5) + λ(3) = 1 + 2 + 1 = 4.
Remark 27. Let M = row(A) be the transmitted module, and let N = row(B) be the received
module. By Lemma 6 we have
d(M, N ) = 2λ(M + N ) − λ(M ) − λ(N ).
Therefore the distance between M and N can be computed from the row-echelon forms of A, B,
and of the matrix C obtained by appending the rows of B to A. In fact
M + N = row(A) + row(B) = row(C).
This allows us to compute the distance function without computing intersections of modules.
Example 28. Let R = Z4 . Notice

1

A= 0
0

that the only nonzero, proper ideal of R is (2). Let



1 1 0
1 3 0 2

B=
2 1 2 ,
0 0 1 0
0 2 0
10

be matrices in row-echelon form, whose underlined entries are the pivots. Let M = row(A) and
N = row(B). Then
λ(M ) = λ(1) + λ(2) + λ(2) = 2 + 1 + 1 = 4
λ(N ) = λ(1) + λ(1) = 2 + 2 = 4
Then M + N = row(C), where

whose reduced row-echelon form is



1
0

C=
0
1
0

1
2
0
3
0

1
1
2
0
1


0
2

0

2
0



1 1 0 0
0 2 0 2 .
0 0 1 0

Hence λ(M + N ) = λ(1) + λ(2) + λ(1) = 2 + 1 + 2 = 5 and
d(M, N ) = 2λ(M + N ) − λ(M ) − λ(N ) = 10 − 8 = 2.
One can compute λ(M ∩ N ) = λ(M ) + λ(N ) − λ(M + N ) = 3. Hence the information loss
module has length λ(M/(M ∩ N )) = λ(M ) − λ(M ∩ N ) = 1 and the error module has length
λ(N/(M ∩ N )) = λ(N ) − λ(M ∩ N ) = 1.

3

Recovering known encoding and decoding schemes

In this section we compare our approach to the one proposed by Feng, Nóbrega, Kschischang, and
Silva for the multiplicative-additive matrix channel (MAMC) in [4, Section IX]. We show that their
encoding scheme remains valid in our setup. We also prove that, in some cases, their decoding
scheme corresponds to minimum distance decoding with respect to the distance function that we
propose.
In our notation, Feng, Nóbrega, Kschischang, and Silva consider the MAMC of equation Y =
AX + Z, where R is a finite chain ring, A ∈ RN ×t , X ∈ Rt×n , Z ∈ RN ×n . They assume that
n ≥ 2N , row(A) ∼
= Rt , and row(Z) ∼
= Rv for some integer v ≤ N . They represent matrices in row
canonical form (see [4, Definition 1] for the definition of row canonical form) and define their
codebook to be the set of principal matrices of given shape in row canonical form (see [4, Section
V.B and Sections VII, VIII, IX]). Observe that matrices in row canonical form are not in general
in reduced row-echelon form according to our Definition 10.
Example 29. Let R = Z8 , whose ideals 0 ( (4) ( (2) ( (1) have canonical generators 0, 4, 2, 1.
Choose 0, 1, 2, 3 as canonical representatives for residue classes modulo (4), 0, 1 as canonical representatives for residue classes modulo (2), and 0 as canonical representative for the residue class
modulo (1). The rows of the following matrices generate the same R-module. The first matrix is
in row canonical form (see [4, Example 6]), while the second is in reduced row-echelon form. The
pivots are underlined.




0 2 0 1
2 0 0 1
2 2 0 0
0 2 0 1




0 0 2 0
0 0 2 0 .
0 4 0 0
0 0 0 2
11

The authors of [4] propose asymptotically optimal encoding and decoding schemes using principal matrices over a finite chain ring R. A transmitted module M is encoded as a principal matrix
in row canonical form, whose rows generate M . In the next proposition we show that principal
matrices in row canonical form are in reduced row-echelon form. Therefore, the encoding schemes
of [4] remain valid in our setup.
Proposition 30. Let R be a finite chain ring, and let A ∈ Rt×n be a principal matrix in row
canonical form. Then A is in reduced row-echelon form with respect to the same choices of generators
and representatives.
Proof. Let π be a generator of the maximal ideal of R, let e be the smallest positive integer such
that π e = 0. By the definition of principal row canonical form, the pivot of row Ai is Aii = π ℓi for
i ∈ {1, . . . , t}, with 0 ≤ ℓ1 ≤ . . . ≤ ℓt ≤ e. Moreover, Aij = π aij with aij ≥ ℓi for i < j ≤ n, hence
ann(Aij ) ⊇ ann(Aii ).
Pt
Let v ∈ row(A) \ {0}, let j = ℓ(v). Write v =
i=1 ri Ai for some r1 , ..., rt ∈ R. Hence
v1 = r1 A1,1 = 0, v2 = r1 A1,2 + r2 A2,2 = 0, . . . , vj−1 = r1 Ai,j−1 + . . . + rj−1 Aj−1,j−1 . By induction
on iP
one can show that ri Aii = 0 for 1 ≤ i < j, hence ri Ai = 0 for 1 ≤ i < j. Therefore
v = ti=j ri Ai ∈ hAj , . . . , At i, so A is in reduced row-echelon form according to Definition 10.
We conclude this section with Proposition 32, that shows that the error-trapping decoding
scheme proposed in [4] for the MAMC can be interpreted as a minimum distance decoding with
respect to the distance function from Definition 20. Before stating our result, we recall the scheme
of [4, Section IX].

Example 31 (Error-trapping decoding). Let R be a finite chain ring. Fix N such that n ≥ 2N
and consider the channel equation Y = AX + Z, where A ∈ RN ×t is left-invertible, X ∈ Rt×n is
the matrix whose rows generate the transmitted module, and Z ∈ RN ×n is a noise matrix whose
row-module is isomorphic to Rv for some integer v ≤ N . One can write


0
A = P (N −t)×t ,
It
where P ∈ RN ×N is an invertible matrix. Fix u ≥ v. If t + v > N let X ∈ Rt×n be of the form


0 0
,
X=
0 X
where X is a matrix in principal form of size (N − u) × (n − u). If t + v ≤ N let X ∈ Rt×n be of
the form


X= 0 X ,

where X is a matrix in principal form of size t × (n − u). Under the assumption that error trapping
is successful, [4, Section IX.B] shows that the row canonical form of Y = AX + Z is


Z1 Z2
 0 X,
0
0

for suitable matrices Z1 ∈ Rv×u and Z2 ∈ Rv×(n−u) . Hence X and X can be obtained by computing
the row canonical form of Y .

12

In some cases, the error-trapping decoding from [4] can be seen as an instance of minimum
distance decoding according to our definition. Notice that the choice u = v is particularly interesting, since it maximizes the number of codewords for the given channel, without affecting the
error-correction capability of the code.
Proposition 32. Following the notation of Example 31, and under the assumption that either
t + v = N or u = v and t + v > N , we have






0 0
0 0
d row(Y ), row
≥ d row(Y ), row
0 T
0 X
for any principal matrix in row canonical form T of the same size as X. Moreover, equality holds
if and only if T = X.
Proof. Since error-trapping is successful, by [4, Section IX.B] there exist matrices G, H, K such that


H K
Y =G·
,
0 X
where G ∈ RN ×N is invertible, H ∈ Rv×u and row(H) ∼
= Rv , K ∈ Rv×(n−u) . Since row(H) ∼
= Rv ,








H K
0 0
0 0
0 0
row
∩ row
= row
∩ row
.
0 X
0 T
0 X
0 T
Therefore

0 0
= λ(row(Y )) + λ(row(T )) − 2λ(row(X) ∩ row(T ))
d row(Y ), row
0 T



0 0
+ λ(row(T )) + λ(row(X)) − 2λ(row(X) ∩ row(T ))
= d row(Y ), row
0 X








0 0
0 0
0 0
+ d row
, row
.
= d row(Y ), row
0 X
0 T
0 X




The result now follows from the fact that both X and T are principal matrices in row canonical
form, hence they are in reduced row-echelon form by Proposition 30.

4

Bounds

In this section we derive two upper-bounds on the cardinality of a submodule code with given
minimum distance. We also discuss in detail some choices of rings or of the code parameters, for
which our bound can be made more precise.
As in the previous sections, we fix a finite PIR R, an R-module Ω ⊆ Rn of the form (2), and let
M(Ω) denote the set of R-submodules of Ω.
Notation 33. For M ∈ M(Ω) and 1 ≤ s ≤ λ(M ) let
 
M
= |{N ∈ M(M ) : λ(N ) = s}|.
s R
For 1 ≤ s ≤ λ let


 
 
M
λ
: M ∈ M(Ω), λ(M ) = λ .
= min
s R
s R
13

When there is no ambiguity, we omit the subscript R. Moreover, we denote by
 
 
λ
λ
=
s F
s q
q

the q-ary binomial coefficient.
We restrict our attention to submodules codes C ⊆ M(Ω) where all codewords have the same
length k, 1 ≤ k ≤ n · λ(R) − 1. Submodule codes of this kind have even minimum distance, and
they are the module-analogue of constant-dimension subspace codes. The next result is a natural
extension to submodule codes of the Singleton-like bound for subspace codes.
Theorem 34. Let C ⊆ M(Ω) be a submodule code with λ(M ) = k for all M ∈ C and minimum
distance d(C) = 2δ. Then


λ(Ω) − δ + 1
|C| ≤
.
k−δ+1
Proof. Let M ∈ M(Ω) be an R-module with λ(M ) = λ(Ω) − δ + 1. By Lemma 6, for all N ∈ C
λ(M ∩ N ) = λ(M ) + λ(N ) − λ(M + N ) ≥ λ(Ω) − δ + 1 + k − λ(Ω) = k − δ + 1.
For every N ∈ C choose an R-submodule N ′ ⊆ M ∩ N with λ(N ′ ) = k − δ + 1. For any N, P ∈ C
with N 6= P we have 2δ = d(C) ≤ d(N, P ) = 2k − 2λ(N ∩ P ), hence λ(N ∩ P ) ≤ k − δ. Hence
d(N ′ , P ′ ) = 2(k − δ + 1) − 2λ(N ′ ∩ P ′ ) ≥ 2(k − δ + 1) − 2(k − δ) = 2,
in particular N ′ 6= P ′ . It follows that C ′ = {N ′ : N ∈ C} is a set of submodules of M of length
k − δ + 1 with |C ′ | = |C|. Therefore


M
′
|C| = |C | ≤
,
k−δ+1
for any M ∈ M(Ω) of length λ(Ω) − δ + 1.



M
Remark 35. For a given R and fixed m, ℓ, the quantity
may depend on the choice of M of
ℓ
length m. E.g., let R = Z5 [i] ⊇ I = (2 + i) and Ω = R2 . Then R × 0 and I × I are two R-modules
of length 2. The ideals of length one of R are exactly I = (2 + i) and (2 − i), while I × I contains
at least three submodules of length one, namely I × 0, 0 × I, and (1, 1)I = h(2 + i, 2 + i)i.
Remark 36. Since every R-module of length greater than or equal to λ(Ω) − δ + 1 contains an
R-submodule of length λ(Ω) − δ + 1, the bound of Theorem 34 can also be stated as



M
|C| ≤ min
: M ∈ M(Ω), λ(M ) ≥ λ(Ω) − δ + 1 .
k−δ+1
The following is another simple bound for the cardinality of a submodule code.
Theorem 37. Let C ⊆ M(Ω) be a submodule code with λ(M ) = k for all M ∈ C, and minimum
distance d(C) = 2δ. Then


Ω
k−δ+1
.
|C| ≤ 
k
k−δ+1
14


k
submodules of Ω of length k − δ + 1. Moreover,
Proof. Each M ∈ C contains at least
k−δ+1
a submodule of Ω of length k − δ + 1 cannot be contained in two distinct M, N ∈ C, as otherwise
λ(M ∩ N ) ≥ k − δ + 1, hence d(M, N ) < 2δ. Therefore




Ω
k
≥ |C| ·
,
k−δ+1
k−δ+1


which proves the bound.
Remark 38. The upper bounds of Theorem 34 and 37 are not comparable. For example, let k = δ,
R = Fq , and Ω = Fnq . Assume that k | n. The bound of Theorem 34 is



n−k+1
|C| ≤
= q n−k + q n−k−1 + . . . + q + 1,
1
q
while the bound of Theorem 37 is
 
n
1 q
qn − 1
|C| ≤   = k
= q n−k + q n−2k + . . . + q k + 1.
q −1
k
1 q
However, one can also find examples in which Theorem 34 yields a better bound than Theorem 37.
E.g., let R = Z12 . The Hasse diagram of the ideals of R is
R
(2)

(3)

(4)

(6)
(0)

In particular, λ(R) = 3. Let Ω = R2 and let C ⊆ M(Ω) be a submodule code with k = δ = 2. By
Theorem 25, the module


1 0
M = row
⊆Ω
0 3
has λ(M ) = λ(1) + λ(3) = 5. Moreover, the submodules of M of length 1 are precisely those generated by one of the following vectors: (4, 0), (6, 0), (6, 6), (0, 6). Therefore, |C| ≤ 4 by Theorem 34.
Now let N = h(0, 3)i ⊆ Ω. Then λ(N ) = 2 and N has a unique submodule of length 1, namely
h(0, 6)i. Hence
 
 

2
N
= min
: N ∈ M(Ω), λ(N ) = 2 = 1.
1
1
One can check that the submodules of Ω of length 1 are exactly those generated by one of the
following vectors: (4, 0), (4, 4), (4, 8), (6, 0), (6, 6), (0, 4), (0, 6). Therefore the bound of Theorem 37
reads
   
2
Ω
= 7 > 4.
/
|C| ≤
1
1
15

The bounds of Theorem 34 and Theorem 37 can be made more explicit for PIR’s which are
2
isomorphic to Zm
p for some m ≥ 1. An example of such ring is Zp [i], which is isomorphic to Zp if
p ≡ 1 mod 4, as we show next. Notice that in the other cases Zp [i] is either a finite chain ring or
a finite field.
Remark 39. Let p be a prime. Then

 Z2 [x]/(x + 1)2
2
Zp [i] ∼
F 2
= Zp [x]/(x + 1) ∼
=
 p
Zp × Zp

if p = 2,
if p ≡ 3 mod 4,
if p ≡ 1 mod 4.

Indeed, if p = 2, then x2 + 1 = (x + 1)2 . If p is an odd prime, then x2 + 1 is reducible if and only
if −1 is a quadratic residue modulo p, if and only if p ≡ 1 mod 4. The thesis now follows from the
Chinese Remainder Theorem.
We start with a preliminary result on the structure of rings of the form R ∼
= Zm
p .
Lemma 40. Let R ∼
= Zm
p . Then there exist e1 , . . . , em ∈ R such that
R = (e1 ) ⊕ . . . ⊕ (em )
and e1 + . . . + em = 1, e2i = ei for all 1 ≤ i ≤ m, and ei ej = 0 if i 6= j. Moreover, λ(R) = m.
m
Proof. Fix an isomorphism π : R → Zm
p between R and Zp . Let ei ∈ R be the inverse image via π
m
of the i-th element of the standard basis of Zp . Then e1 + . . . + em = 1, e2i = ei for all 1 ≤ i ≤ m,
and ei ej = 0 if i 6= j. Notice that R is a Zp -vector space via αr = π −1 (απ(r)) for α ∈ Zp , r ∈ R.
This corresponds to identifying Zp with {π −1 (α, . . . , α) : α ∈ Zp } ⊆ R. Since R = (e1 ) ⊕ . . . ⊕ (em ),
then every r ∈ R can be written uniquely as r = r1 e1 + . . . + rm em with ri ∈ Zp , where we regard
Zp as a subset of R via the identification above. Therefore λ(R) = m and a composition series for
R is given by 0 ( (e1 ) ( (e1 , e2 ) ( . . . ( (e1 , . . . , em ) = R.

Using the notation of Lemma 40, we can count the number of submodules of fixed length of any
given R-module M . For the sake of concreteness we limit our attention to submodules of Rn , but
the same proof applies to any finitely generated R-module M .
n
Theorem 41. Let R ∼
= Zm
p , let M ∈ M(R ). The number of R-submodules of M of length ℓ is
 

m 
X
Y
M
dim(ei M )
=
.
ℓ
ℓi
m
p
(ℓ1 , . . . , ℓm ) ∈ N ,
ℓ1 + . . . + ℓm = ℓ

In particular,



i=1

 X
m
pdim(ei M ) − 1
M
=
.
1
p−1
i=1

Proof. By Lemma 40, for all M ∈ M(Rn ) one has

M = e1 M ⊕ . . . ⊕ em M.
Pm

Therefore λ(M ) = i=1 λ(ei M ). Moreover, for all r = r1 e1 + . . . + rm em ∈ R and v ∈ M we have
rei v = ri ei v for all i. Therefore the R-submodules of ei M coincide with its Zp -subspaces, hence
λ(ei M ) = dimZp (ei M ). Hence we have shown that for every R-module M ⊆ Rn
λ(M ) =

m
X

dimZp (ei M ) = dimZp (M ).

i=1

16

Since for every collection of submodules Ni ⊆ ei M the module N = N1 ⊕ . . . ⊕ Nm ∈ M(M ) and
the R-submodules of ei M coincide with its Zp -subspaces, then the number of R-submodules of M
of length ℓ is
 

m 
Y
X
M
dim(ei M )
.
=
ℓ
ℓi
m
p
(ℓ1 , . . . , ℓm ) ∈ N ,
ℓ1 + . . . + ℓm = ℓ

i=1

Theorem 41 allows us to evaluate the bounds of Theorem 34 and Theorem 37 as follows.
∼ Zm . Let C ⊆ M(Ω) be a submodule code with λ(M ) = k for all M ∈ C
Corollary 42. Let R =
p
and d(C) = 2δ. Let






m  


Y
X
ui
m
b(λ, k, δ) = min
: (u1 , . . . , um ) ∈ N , u1 + . . . + um = λ − δ + 1 .
ℓi p




i=1
 (ℓ1 , . . . , ℓm ) ∈ Nm ,

ℓ1 + . . . + ℓm = k − δ + 1

Then

|C| ≤ b(λ(Ω), k, δ).

Moreover,

|C| ≤

X

(ℓ1 , . . . , ℓm ) ∈ Nm ,
ℓ1 + . . . + ℓm = k − δ + 1

(4)


m 
Y
dim(ei Ω)
i=1

ℓi

b(k + δ − 1, k, δ)

If Ω = Rn and δ = k, then
|C| ≤

p

.

(pn − 1)/(p − 1)
.
⌈(pk/m − 1)/(p − 1)⌉

(5)

(6)

If in addition m = 2 and k is odd, then
|C| ≤ ⌊2(pn − 1)/(ph + ph−1 − 2)⌋,

(7)

where h = ⌈k/2⌉.
Proof. Let M ∈ M(Ω) be a submodule of length λ(M ) = λ(Ω) − δ + 1 and let ui = dim(ei M ) for
all i. By Theorem 41, the number of submodules of M of length k − δ + 1 equals


m  
Y
X
M
ui
.
=
k−δ+1
ℓi p
m
(ℓ1 , . . . , ℓm ) ∈ N ,
ℓ1 + . . . + ℓm = k − δ + 1

i=1

Hence Theorem 34 implies bound (4). Similarly, bound (5) follows from Theorem 37.
Now assume δ = k and Ω = Rn . We have
)
!
(
m
m
X
X
1
ui = k .
pui − m : (u1 , ..., um ) ∈ Nm ,
b(2k − 1, k, k) = min
p−1
i=1
i=1
P
xi
m
Let f : Rm → R be the function defined by f (x1 , ..., xm ) = m
i=1 p for all (x1 , ..., xm ) ∈ R . Using
e.g. the method of Lagrange multipliers from Calculus, one can show that the minimum of f in the
region of Rm defined by the constraints
m
X

xi = k,

xi ≥ 0 for all i ∈ {1, ..., m}

i=1

17

is attained for x1 = x2 = . . . = xm = k/m, and that its value is mpk/m . This shows that
b(2k − 1, k, k) ≥ ⌈(mpk/m − m)/(p − 1)⌉.
Bound (6) now follows from bound (5) and the fact that dim(ei Ω) = n for all i ∈ {1, ..., m}. If in
addition m = 2 and k is odd, then without loss of generality we may assume u1 ≥ u2 + 1. Using
elementary methods from Calculus, one shows that
b(2k − 1, k, k) ≥

ph + ph−1 − 2
,
p−1

where h = ⌈k/2⌉. This concludes the proof.
We conclude this section by evaluating the bound of Theorem 34 for finite chain rings. We
concentrate on codes C ⊆ M(Ω) with λ(M ) = k for all M ∈ C and d(C) = 2k.
Theorem 43. Let R be a finite chain ring of length e, let π ∈ R be a generator of the maximal
ideal of R, let q be the cardinality of the residue field of R. Let
Ω = R × (π a2 ) × . . . × (π an )
for some 0 ≤ a2 ≤ . . . ≤ an ≤ e − 1. Let C ⊆ M(Ω) be a submodule code with d(C) = 2k and whose
codewords have length k. Then
qm − 1
|C| ≤
q−1
where m = min{1 ≤ i ≤ n | (n − i)e − ai+1 − . . . − an ≤ k − 1}. In particular, if Ω = Rn , then
|C| ≤

q n−h+1 − 1
q−1

where k = he − r with 0 ≤ r ≤ e − 1.
Proof. We claim that the submodules of length one of an R-module M ⊆ Rn are in bijection with
the vectors v ∈ M of the form
v = (0, . . . , 0, π e−1 , vi+1 , ..., vn )
| {z }

(8)

i−1

where 1 ≤ i ≤ n and vi+1 , ..., vn ∈ (π e−1 ). In fact, every module of length one is minimally generated
by one vector. If we represent a module generated by one vector by a matrix in reduced row-echelon
form, then such a matrix has a unique row by Theorem 25, and by Proposition 17 the row is of
the form v = (0, . . . , 0, π s , vi+1 , ..., vn ) with vi+1 , ..., vn ∈ (π s ). Finally, λ(hvi) = λ(π s ) = e − s by
Theorem 25. Hence the modules of length one are exactly those generated by vectors of the form
(8). By uniqueness of the reduced row-echelon form, two such modules are distinct if and only if
they are generated by distinct vectors in reduced row-echelon form. This proves the claim. Notice
that there are exactly q n−i vectors of the form (8), for a fixed i ∈ {1, . . . , n}.
Let M ⊆ Ω be a submodule of length λ(Ω) − k + 1. Let m be the least integer such that
M ⊆ Rm × |0 × .{z
. . × 0} .
n−m

Notice that m depends on M , and not just on its length. Then M contains exactly q m−1 + q m−2 +
m −1
vectors of the form (8), since each such vector has vi+1 , . . . , vm ∈ (π e−1 )
. . . + q + 1 = qq−1
18

and vm+1 = . . . = vn = 0, for some 1 ≤ i ≤ m. Since Ω = R × (π a2 ) × . . . × (π an ), then
λ(Ω) = ne − a2 − . . . − an . If
M ⊆ (Ri × 0 × . . . × 0) ∩ Ω = R × π a2 R × . . . × π ai R × 0 × . . . × 0
for some i, then λ(M ) = ne − a2 − . . . − an − k + 1 ≤ λ(R × π a2 R × . . . × π ai R) = ie − a2 − . . . − ai .
Hence
m ≥ min{1 ≤ i ≤ n : (n − i)e − ai+1 − . . . − an ≤ k − 1}
and equality holds for any M ⊆ R × (π a2 ) × . . . × (π am ) × 0 × . . . × 0. By Theorem 34



M
|C| ≤ min
: M ⊆ Ω, λ(M ) = λ(Ω) − δ + 1
k−δ+1
= min




qi − 1
qm − 1
i
: M ⊆ Ω ∩ R × 0 × . . . × 0, λ(M ) = λ(Ω) − δ + 1 =
q−1
q−1

where m = min{1 ≤ i ≤ n | (n − i)e − ai+1 − . . . − an ≤ k − 1}.
If Ω = Rn , then a2 = . . . = an = 0. Write k = he − r with 0 ≤ r ≤ e − 1. Then (h − 1)e ≤
k − 1 ≤ he − 1, hence m = min{1 ≤ i ≤ n | (n − i)e ≤ k − 1} = n − h + 1.

5

Constructions

In this section we propose some constructions for submodule codes for an ambient space of the form
Ω = Rn . Throughout the section we say that a code is asymptotically optimal if its cardinality
asymptotically meets one of the bounds of the previous section. We say that a code is optimal if
its cardinality exactly meets one of the bounds.
We first concentrate on finite chain rings, and show how to construct optimal codes of maximum
correction capability. Our codes can be regarded as the submodule code analogue of the partial
spread codes from [6]. We then look at finite PIR’s that contain a field F, and show how subspace
codes over F can be lifted to submodule codes over R by tensoring them with R. This allows us to
construct optimal submodule codes over Zp [i] of maximum correction capability. Finally we show
how to obtain submodule codes over a ring of the form R1 × . . . × Rm from submodule codes over
R1 , ..., Rm . We propose two constructions of the latter type, and discuss their decoding. For the
first construction we take a cartesian product of codes on the Ri ’s and show that this yields a code
on R, whose parameters are determined and whose decoding can be reduced to decoding on each
of the Ri ’s. However, not every code over a R is a product of codes over the Ri ’s: Our second
construction yields a code over R which is not a product. We show that, in that case, decoding
cannot be reduced to decoding on each of the Ri ’s. This shows in particular that, although every
finite PIR R is isomorphic to a product of finite fields and finite chain rings, the study of codes over
R cannot be reduced in general to the study of codes over finite fields and finite chain rings.

5.1

Partial spreads over finite chain rings

We start with a construction that can be applied to any PIR. Its optimality relies on the existence
of large sets of matrices, in which the length of the difference of any two of them is maximum. In
Proposition 46 we will show that such large sets can be constructed over any finite chain ring.
Theorem 44. Let R be a finite PIR. Let n, k be positive integers. Write k = h · λ(R) − r with
0 ≤ r ≤ λ(R) − 1, and assume n ≥ 2h. Write n = ν · h + ρ with 0 ≤ ρ ≤ h − 1. Let A ⊆ Rh×h and
19

A′ ⊆ Rh×(h+ρ) be subsets such that λ(row(A − B)) = h · λ(R) for all A, B ∈ A with A 6= B and
A, B ∈ A′ with A 6= B. For i ∈ {1, ..., ν − 1} let


Si = 0h×h . . . 0h×h Ih×h Ai+1 . . . Aν−1 Aν : Ai+1 , ..., Aν−1 ∈ A, Aν ∈ A′ ⊆ Rh×n ,
where Ih×h is the identity matrix of size h×h. Define Sν =
an ideal of length λ(R) − r. For all i ∈ {1, ..., ν} let



0h×(n−h) Ih×h



. Let ζ ∈ R generate

Si,ζ = {Mζ : M ∈ Si },
where Mζ is the matrix obtained from M by multiplying its last row by ζ. Then
C=

ν
[

{row(M ) : M ∈ Si,ζ }

i=1

is a submodule code of length λ(C) = k, minumum distance d(C) = 2k, and cardinality
|C| = |A′ | ·

|A|ν−1 − 1
+ 1.
|A| − 1

Proof. Let Mζ ∈ Si,ζ . Then Mζ is in row-echelon form and λ(row(Mζ )) = (h − 1) · λ(R) + λ(ζ) = k
by Theorem 25. Define the code
C′ =

ν
[

{row(M ) : M ∈ Si }.

i=1

Again M is in row-echelon form and λ(row(M )) = h · λ(R). Moreover, arguing as in [6, Theorem
13 and Proposition 17] and replacing the rank with the length, one sees that d(C ′ ) = 2h · λ(R), i.e.,
the submodules that constitute C ′ have trivial pairwise intersections. Moreover,
|C ′ | = |A′ | ·

|A|ν−1 − 1
+ 1.
|A| − 1

Now observe that C is obtained from C ′ by taking an appropriate submodule of each codeword.
Therefore the codewords of C have trivial pairwise intersection. Hence d(C) = 2k and |C| = |C ′ |.
We now show that over a finite chain ring R one can construct large sets A and A′ to be used
within the construction from Theorem 44.
Lemma 45. Let R be a ring, let s, t > 0. Then for any v1 , ..., vt ∈ Rs we have λ(hv1 , ..., vt i) ≤ t·λ(R).
Proof. Let A ∈ Rt×s be the matrix with rows v1 , ..., vt . Right multiplication by A induces an
R-homomorphism fA : Rt → Rs , whose image is hv1 , . . . , vt i. Since Im(fA ) ∼
= Rt / ker(fA ), then
t
t
λ(hv1 , . . . , vt i) = λ(R ) − λ(ker(fA )) ≤ λ(R ) = t · λ(R).
Proposition 46. Let R be a finite chain ring with residue field of order q. Then for all h > 0 and
for all 0 ≤ ρ ≤ h − 1 there exists a set A ⊆ Rh×(h+ρ) with |A| = q h+ρ and λ(row(A − B)) = h · λ(R)
for all A, B ∈ A with A 6= B.

20

Proof. We first prove the statement for ρ = 0. Let π be a generator of the maximal ideal of R, and
let f : R → R/(π) be the projection map. Let ι : R/(π) → R be such that f ◦ ι is the identity of
R/(π). Such a ι can be obtained by mapping each element of R/(π) to one of its representatives in
R. Notice that we do not require that ι is a ring homomorphism. We extend f and ι entrywise to
f : Rh×h → (R/(π))h×h and ι : (R/(π))h×h → Rh×h .
, by [3, Section 6] there exists A′ ⊆ (R/(π))h×h with |A′ | = q h and
Since (R/(π))h×h ∼
= Fh×h
q
′
′
′
A − B invertible for any A , B ′ ∈ A′ with A′ 6= B ′ . Then the set of matrices A = {ι(A′ ) : A′ ∈
A′ } ⊆ Rh×h has the expected properties. Indeed, let A′ , B ′ ∈ A′ with A′ 6= B ′ . Since f is a ring
homomorphism, we have
f (det(ι(A′ ) − ι(B ′ ))) = det(f (ι(A′ )) − f (ι(B ′ ))) = det(A′ − B ′ ) 6= 0.
Therefore det(ι(A′ ) − ι(B ′ )) ∈
/ (π). As (π) is the only maximal ideal of R, det(ι(A′ ) − ι(B ′ )) is
invertible, hence ι(A′ ) − ι(B ′ ) is invertible. This implies row(ι(A′ ) − ι(B ′ )) ∼
= Rh , which has length
′
h
h · λ(R). In addition |A| = |A | = q .
Now assume ρ > 0, and set h′ = h+ρ. By the first part of the proof there exists a set of matrices
′
′
B ⊆ Rh ×h with λ(row(A − B)) = h′ · λ(R) for all A, B ∈ B with A 6= B. For A ∈ B denote by A
the matrix obtained from A by deleting the first ρ rows. A simple application of Lemma 45 shows
′
that the set A = {A : A ∈ B} ⊆ Rh×h has the desired properties.
Example 47. Let R be a finite chain ring with residue field of order q. Following the notation
of Theorem 44, Proposition 46 allows us to construct a submodule code C ⊆ M(Rn ) of constant
length λ(C) = k, minimum distance d(C) = 2k, and cardinality
|C| = q h+ρ ·

q n − q h+ρ + q h − 1
q h(ν−1) − 1
+
1
=
∈ O(q n−h )
qh − 1
qh − 1

(as n > h+ρ). Let C be a submodule code with the same parameters as C and maximum cardinality.
By Theorem 43 we have |C| ≤ (q n−h+1 − 1)/(q − 1). Therefore
1≥

q−1
|C|
q n − q h+ρ + q h − 1
q→∞
−→ 1.
· n−h+1
≥
h
q −1
q
−1
|C|

This shows that C is an asymptotically optimal submodule code.

5.2

Tensor product construction and partial spreads over rings of the form Zm
p

Assume that R contains a finite field F ⊆ R as a subring and that R and F have the same one. Let
V ⊆ Fn be an F-linear space. Recall that the tensor product V ⊗F R ⊆ Rn is the submodule of Rn
generated by the elements of V . If V = hv1 , . . . , vm iF , then
V ⊗F R = hv : v ∈ V iR = hv1 , . . . , vm iR .
Lemma 48. Let V ⊆ Fn be an F-linear space. Then
λ(V ⊗F R) = λ(R) · dimF (V ).
Proof. Let t = dimF (V ), and let A ∈ Ft×n be a matrix in reduced row-echelon form, whose rows
generate V . Regard A as a matrix over R. Then A is still in row-echelon form and row(A) = V ⊗F R.
Since all the pivots of A are ones, by Theorem 25 we have λ(V ⊗F R) = λ(1) · t = λ(R) · dimF (V ),
as claimed.
21

Lemma 49. Let V, W ⊆ Fn be F-linear spaces. Then (V ⊗F R) ∩ (W ⊗F R) = (V ∩ W ) ⊗F R.
Proof. By definition (V ∩ W ) ⊗F R ⊆ (V ⊗F R) ∩ (W ⊗F R). Therefore by Lemma 6 it suffices to
show that they have the same length. By Lemma 48
λ((V ∩ W ) ⊗F R) = λ(R) · dimF (V ∩ W ) = λ(R) · (dimF (V ) + dimF (W ) − dimF (V + W )) =
λ(V ⊗F R) + λ(W ⊗F R) − λ((V + W ) ⊗F R) = λ((V ⊗F R) ∩ (W ⊗F R)),
where the last equality follows from Lemma 6 and from observing that (V + W ) ⊗F R = V ⊗F R +
W ⊗F R.
From Lemma 48 and 49 one obtains the following construction.
Theorem 50. Let C ⊆ M(Fn ) be a subspace code of minimum subspace distance 2δ and dimF (V ) =
k for all V ∈ C. Then
C ⊗F R = {V ⊗F R : V ∈ C} ⊆ M(Rn )
is a submodule code of cardinality |C ⊗F R| = |C|, whose codewords have length λ(R) · k, and whose
minimum distance is 2λ(R) · δ.
∼
Example 51. Let F = Zp and R = Zm
p . Then Zp = {(a, a, ..., a) : a ∈ Zp } ⊆ R can be viewed
as a subring of R. We have λ(R) = m. Let h be an integer, 1 ≤ h ≤ n/2. By [6, Theorem 13
and Proposition 17], there exists a subspace code C ⊆ M(Znp ) of constant dimension h, minimum
distance 2h and cardinality (pn − ph+ρ + ph − 1)/(ph − 1), where ρ is the remainder of the division
of n by h. By Theorem 50, C ⊗Zp R ⊆ M(Rn ) is a submodule code whose codewords have length
mh and minimum distance 2mh. Moreover,
|C ⊗Zp R| =

pn − pρ
− pρ + 1.
ph − 1

Let C be a submodule code with the same parameters as C ⊗Zp R and maximum cardinality. By
Theorem 42 (6), |C| ≤ (pn − 1)/(ph − 1). Therefore
1≥

|C ⊗Zp R|
|C|

≥

pn − ph+ρ + ph − 1 ph − 1 q→∞
−→ 1.
· n
ph − 1
p −1

Hence C ⊗Zp R is asymptotically optimal, and it is optimal when ρ = 0.
Fix 1 ≤ ℓ ≤ m − 1. For all M ∈ C ⊗Zp R choose a submodule M ′ ⊆ M with λ(M ′ ) = mh − ℓ.
Then D = {M ′ : M ∈ C ⊗Zp R} ⊆ M(Rn ) is a submodule code with minimum distance 2mh − 2ℓ
and whose codewords have length mh − ℓ. Moreover,
|D| = |C ⊗Zp R| =

pn − pρ
− pρ + 1.
ph − 1

Let D be a submodule code with the same parameters as D and maximum cardinality. By Theorem 42 (6) we have |D| ≤ (pn − 1)/(ph−ℓ/m − 1). Therefore
1≥



|D|
pn − ph+ρ + ph − 1 ph−ℓ/m − 1
−ℓ/m
.
·
∈
O
p
≥
ph − 1
pn − 1
|D|

If in addition m = 2, then by Proposition 42 (7)
1≥

pn − ph+ρ + ph − 1 ph + ph−1 − 2 q→∞
|D|
≥
−→ 1/2.
·
ph − 1
2(pn − 1)
|D|

Therefore D is asymptotically optimal, up to a factor 2.
22

Remark 52. Let C ⊆ M(Fn ) be a subspace code over the finite field F, and let W ⊆ Fn be a
decodable space for the code C, i.e., an F-linear space for which there exists V ∈ C with d(V, W ) ≤
⌊(dS (C)−1)/2⌋, where dS (C) denotes the minimum subspace distance of C. Then W ⊗F R is decodable
in the submodule code C ⊗F R, and it decodes to V ⊗F R.
However, there exist submodules of Rn which are decodable in C ⊗F R but are not of the form
W ⊗F R, with W an F-space which is decodable in C. Moreover, if N ⊆ Rn is decodable in C ⊗F R,
then N ∩ Fn is not necessarily decodable in C.
Let e.g. R = Z5 [i], F = Z5 , and let C = {V1 , V2 } ⊆ M(Z45 ) be the subspace code whose
codewords are the 2-dimensional spaces
V1 = h(1, 0, 1, 0), (0, 1, 0, 1)iZ5 ,

V2 = h(1, 0, 2, 1), (0, 1, 1, 0)iZ5 .

Then C has subspace distance dS (C) = 4. By Theorem 50 the submodule code C ⊗Z5 Z5 [i] has two
codewords of length 4 and submodule distance d(C ⊗Z5 Z5 [i]) = 8.
Let
N = h(i + 2, 0, i + 2, 0), (0, 1, 0, i − 1)iZ5 [i] ⊆ Z5 [i]4
be a received submodule. Then d(N, V1 ⊗Z5 Z5 [i]) = 3 ≤ ⌊(8 − 1)/2⌋ = 3, so N is decodable
in C ⊗Z5 Z5 [i]. However, N is not of the form W ⊗Z5 Z5 [i] for any vector space W . Moreover,
N ∩ Z45 = 0, so N ∩ Z45 is not decodable in C with respect to the subspace distance.

5.3

Two constructions over products of rings

Let R ∼
= R1 × . . . × Rm , where R1 , . . . , Rm are finite commutative rings with identity. Let πi be the
projection on the factor Ri . Then each πi extends componentwise to a map πi : Rn → Rin .
Lemma 53. Let R ∼
= R1 × . . . × Rm be a finite ring, let M ⊆ Rn be an R-module. Then
M∼
= π1 (M ) × . . . × πm (M ), each πi (M ) is an Ri -module and
λR (M ) =

m
X

λRi (πi (M )).

i=1

Proof. Let ri ∈ Ri and v ∈ M . Then πi (v) = (πi (v1 ), . . . , πi (vn )) ∈ πi (M ) ⊆ Rin , and ri πi (v) =
(ri πi (v1 ), . . . , ri πi (vn )) ∈ πi (M ). This makes πi (M ) into an Ri -module. Moreover, the isomorphism
n restricts to an isomorphism M ∼ π (M ) × . . . × π (M ). Hence
Rn ∼
= 1
= R1n × . . . × Rm
m
λR (M ) =

m
X

λR (πi (M )) =

m
X

λRi (πi (M )),

i=1

i=1

where the last equality follows from the fact that any R-submodule of πi (M ) is an Ri -submodule,
and viceversa.
We start with a simple construction, where we produce a code over R1 × . . . × Rm by taking the
n.
cartesian product of codes over each Ri . For simplicity of notation we identify Rn and R1n × . . . Rm
Theorem 54. Let R1 , ..., Rm be finite PIR’s and let R = R1 × . . . × Rm . For i ∈ {1, ..., m} let
Ci ⊆ M(Rin ) be a submodule code whose codewords have length ki . Then
C = C1 × . . . × Cm = {M1 × . . . × Mm : Mi ∈ Ci for all i } ⊆ M(Rn )
is a submodule code of cardinality |C| = |C1 | . . . |Cm |, whose codewords have length k1 + . . . + km ,
and with minimum distance d(C) = min{d(Ci ) : 1 ≤ i ≤ m}.
23

We now show that decoding of the product code C = C1 × . . . × Cm over R can be reduced to
decoding each of the codes Ci over Ri .
Proposition 55. Let R1 , ..., Rm be finite PIR’s and let R = R1 × . . . × Rm . For i ∈ {1, ..., m}
let Ci ⊆ M(Rin ) be a submodule code and let C = C1 × . . . × Cm ⊆ M(Rn ) be the product code.
Let N ⊆ Rn be a received decodable submodule, i.e., an R-module for which there exists an
M = M1 × . . . × Mm ∈ C such that d(N, M ) ≤ ⌊(d(C) − 1)/2⌋. Then for all i ∈ {1, ..., m} we have
d(πi (N ), Mi ) ≤ ⌊(d(Ci ) − 1)/2⌋, i.e., πi (N ) decodes to Mi in Ci .
Proof. By Lemma 53, N = π1 (N ) × . . . × πm (N ), and Mi = πi (M ) for 1 ≤ i ≤ m. Moreover
d(N, M ) = λ(N ) + λ(M ) − 2λ(N ∩ M )
m
m
m
X
X
X
λRi (πi (N ∩ M ))
λRi (πi (M )) − 2
λRi (πi (N )) +
=
≥

i=1

i=1

m
X

d(πi (N ), πi (M )),

i=1

i=1

where the inequality follows from the fact that πi (N ∩ M ) ⊆ πi (N ) ∩ πi (M ). Therefore for all i we
have
d(πi (N ), πi (M )) ≤ d(N, M ) ≤ ⌊(d(C) − 1)/2⌋ ≤ ⌊(d(Ci ) − 1)/2⌋,
hence πi (N ) decodes to Mi in Ci .
Finally, we provide another construction which combines submodule codes over the factors Ri
into a submodule code over R = R1 ×. . .×Rm . Compared to the product construction of Theorem 54,
this construction produces a code with smaller cardinality and larger minimum distance, whose
decoding cannot be reduced to decoding over the Ri ’s. Again, for simplicity we identify Rn and
n.
R1n × . . . × Rm
Theorem 56. Let R1 , ..., Rm be finite PIR’s, and let R = R1 × . . . × Rm . For i ∈ {1, ..., m}
let Ci ⊆ M(Rin ) be a submodule code whose codewords have length ki . Let c = min |Ci |, and
for all i ∈ {1, ..., m} fix a subcode Ci′ ⊆ Ci with |Ci′ | = c. Enumerate the elements of each Ci′ as
Ci′ = {M1,i , ..., Mc,i }. Then
C = {Mj,1 × . . . × Mj,m : 1 ≤ j ≤ c} ⊆ M(Rn )
is a submodule code of cardinality |C| = c, with d(C) ≥ d(C1 ) + . . . + d(Cm ), and whose codewords
have length k1 + . . . + km .
Proof. We only prove the part about the minimum distance. Let j, j ′ ∈ {1, ..., c} with j 6= j ′ .
Arguing as in the proof of Proposition 55, one finds
d(Mj,1 × . . . × Mj,m , M

j ′ ,1

× ... × M

j ′ ,m

)≥

m
X
i=1

d(Mj,i , M

j ′ ,i

)≥

m
X

d(Ci ),

i=1

where the last inequality follows from the fact that Mj,i 6= Mj ′ ,i whenever j 6= j ′ .
Remark 57. Notice that an R-module which is decodable with respect to the code C constructed
in Theorem 56 is not necessarily a product of Ri -modules that are decodable with respect to the
codes Ci . E.g., let m = 2, n = 4, R1 = R2 = Z2 , R = Z2 × Z2 . Let
M1,1 = M1,2 = h(1, 0, 1, 0), (0, 1, 0, 1)iZ2 ,

M2,1 = M2,2 = h(1, 0, 1, 1), (0, 1, 1, 0)iZ2
24

and C1 = C1′ = {M1,1 , M1,2 }, C2 = C2′ = {M2,1 , M2,2 }. Then





(1, 1) (0, 0) (1, 1) (0, 0)
(1, 1) (0, 0) (1, 1) (1, 1)
C = row
, row
.
(0, 0) (1, 1) (0, 0) (1, 1)
(0, 0) (1, 1) (1, 1) (0, 0)
The code C has minimum distance d(C) = 8. Let


(1, 0) (0, 0) (1, 0) (0, 0)
N = row
(0, 0) (1, 1) (0, 1) (1, 1)
be a received submodule. Then N decodes to M1,1 ×M1,2 ∈ C, as d(N, M1,1 ×M1,2 ) = 3 ≤ ⌊(8−1)/2⌋.
However, π2 (N ) = h(0, 1, 1, 1)iZ2 is not decodable in C2 . In fact, d(π2 (N ), M21 ) = d(π2 (N ), M22 ) = 3.

References
[1] D. D. Anderson, M. Axtell, S. J. Forman, J. Stickles, When are Associates Unit Multiples?,
Rocky Mountain Journal of Mathematics 34 (2004), no. 3, 811–828.
[2] J. Buchmann, S. Neis, Algorithms for linear algebra problems over principal ideal rings, technical report, Technische Hochschule Darmstadt (1996).
[3] P. Delsarte, Bilinear forms over a finite field, with applications to coding theory, Journal of
Combinatorial Theory, Series A, 25 (1978), no. 3, 226 – 241.
[4] C. Feng, R. W. Nóbrega, F. R. Kschischang, D. Silva, Communication over finite-chain-ring
matrix channels, IEEE Transactions on Information Theory 60 (2014), no. 10, 5899–5917.
[5] C. Feng, D. Silva, F. R. Kschischang, An algebraic approach to physical-layer network coding,
IEEE Transactions on Information Theory 59 (2013), no. 11, 7576–7596.
[6] E. Gorla, A. Ravagnani, Partial spreads in random network coding, Finite Fields and Their
Applications 26 (2014), 104–115.
[7] J. A. Howell, Spans in the module (Zm )s , Linear and Multilinear Algebra 19 (1986), 67–77.
[8] R. Kötter, F. R. Kschischang, Coding for errors and erasures in random network coding, IEEE
Transactions on Information Theory 54 (2008), no. 8, 3579–3591.
[9] E. Kunz, Introduction to commutative algebra and algebraic geometry, Birkhäuser Boston Inc.,
Boston (1985).
[10] B. R. McDonald, Finite rings with identity, Pure and Applied Mathematics 28, Marcel Dekker
Inc., New York (1974).
[11] B. Nazer, M. Gastpar, Compute-and-forward: harnessing interference through structured codes,
IEEE Transactions on Information Theory 57 (2011), no. 10, 6463–6486.
[12] P. Popovski, H. Yomo, The anti-packets can increase the achievable throughput of a wireless
multi-hop network, Proceedings of the IEEE International Conference on Communications 2006,
ICC ’06, 3885 – 3890.
[13] Q T. Sun, J. Yuan, T. Huang, K. W. Shum, Lattice network codes based on Eisenstein integers,
IEEE Transactions on Information Theory 61 (2013), no. 7, 2713–2725.
25

[14] 0. Zariski, P. Samuel, Commutative Algebra Vol. 1, Graduate Texts in Mathematics 28,
Springer-Verlag, New York-Heidelberg-Berlin, (1975).
[15] S. Zhang, S.-C. Liew, P. P. Lam, Hot topic: physical layer network coding, Proceedings of
the 12th annual international conference on Mobile computing and networking, MobiCom ’06,
358–365.

26

