arXiv:1801.02329v2 [] 29 Jan 2018

Grassmannian Codes with New
Distance Measures for Network Coding
Tuvi Etzion

Hui Zhang

Dept. of Computer Science
Technion-Israel Institute of Technology
Haifa 3200003, Israel
Email: etzion@cs.technion.ac.il

Dept. of Computer Science
Technion-Israel Institute of Technology
Haifa 3200003, Israel
Email: hzhang.chn@gmail.com

Abstract—Subspace codes are known to be useful in errorcorrection for random network coding. Recently, they were
used to prove that vector network codes outperform scalar
linear network codes, on multicast networks, with respect
to the alphabet size. In both cases, the subspace distance is
used as the distance measure. In this work we show that
we can replace the subspace distance with two other possible
distance measures which generalize the subspace distance. We
prove that each code with the largest number of codewords
and the generalized distance, given the other parameters, has
the minimum requirements needed to solve a given multicast
network with a scalar linear code. We discuss lower and upper
bounds on the sizes of the related codes.

I. I NTRODUCTION
Network coding has been attracting increasing attention
in the last fifteen years. The seminal work of Ahlswede,
Cai, Li, and Yeung [1] and Li, Yeung, and Cai [15]
introduce the basic concepts of network coding and how
network coding outperforms the well-known routing. The
class of networks which were mainly studied are the multicast networks and these are also the target of this work.
A multicast network is a directed acyclic graph with one
source. The source has h messages, which are scalars over
a finite field Fq . The network has N receivers, each one
demands all the h messages of the source to be transmitted
in one round of a network use. An up-to-date survey on
network coding for multicast networks can be found for
example in [10]. Kötter and Médard [16] provided an
algebraic formulation for the network coding problem: for
a given network, find coding coefficients (over a small
field) for each edge, which are multiplied with the symbols
received at the starting node of the edge, such that each
receiver can recover all the demanded information from its
received symbols on its in-coming edges. This sequence of
coding coefficients at each edge is called the local coding
vector. Such an assignment of coding coefficients for all the
edges in the network is called a solution for the network.
The coding coefficients are scalars and the solution is a
scalar linear solution. Ebrahimi and Fragouli [4] have
extended this algebraic approach to vector network coding.
In this setting the messages are vectors of length t over Fq
and the coding coefficients are t×t matrices over Fq . A set
of coding matrices such that all the receivers can recover
their requested information, is called a vector solution.
The alphabet size of the solution is an important parameter that directly influences the complexity of the

calculations at the network nodes and as a consequence
the performance of the network. Jaggi et al. [14] have
shown a deterministic algorithm to find a network code
(for multicast networks) of a field size which is the first
prime power greater or equal to the number of receivers.
In general, finding the minimum required alphabet size
of a network code for a given multicast network is NPcomplete [19]. Vector network coding solution with vectors
of length t over Fq outperforms the scalar linear network
coding solution for the same network if the scalar solution
requires an alphabet of size qs , where qs > q t .
An important step in the evolution of network coding
was the introduction of random network coding [12], [13].
Instead of the deterministic algorithm to design the network
code, there is a random selection of coefficients for the
local coding vectors at each coding point (taken from Fq ).
By choosing a field size large enough, the probability that
this random selection won’t be a solution for the network
tends to zero.
Kötter and Kschischang [17] introduced a framework
for error-correction in random network coding. They have
shown that for this purpose the codewords are taken as subspaces over a finite field Fq , where the distance measure,
called the subspace distance is defined as follows. The set
of all subspaces of Fnq is called the projective space and
denoted by Pq (n). For two subspaces X, Y ∈ Pq (n) the
subspace distance dS (X, Y ) is defined by
dS (X, Y ) = dim X + dim Y − 2 dim(X ∩ Y ) .
It was shown later in [22] that another metric called
the injection metric is better suitable for random network
coding. For two subspaces X, Y ∈ Pq (n) the injection
distance dI (X, Y ) is defined by
dI (X, Y ) = max{dim X, dim Y } − dim(X ∩ Y ) .
These two papers [17], [22] have motivated an extensive
work on subspace codes and in particular on codes in which
all the subspaces have the same dimension. These codes are
called constant dimension codes or Grassmannian codes
since they belong to the Grassmann space. For a given
positive integer n and a given integer k, 0 ≤ k ≤ n, the
Grassmannian Gq (n, k) is the set of all subspaces in Pq (n)

whose dimension is k. The two distance measures coincide for this family of subspaces or more precisely, if
X, Y ∈ Gq (n, k) then dS (X, Y ) = 2dI (X, Y ). Since we
concentrate on Grassmannian codes in this paper we will
define the Grassmannian distance dG (X, Y ) to be
dG (X, Y ) = k − dim(X ∩ Y ) .
Most of the research on subspace codes motivated
by [17] was in two directions – find the largest codes
with prescribed minimum subspace distance and looking
for designs based on subspaces. To this end, two quantities
were defined. The first one Aq (n, d) is the maximum size
of a code in Pq (n) with minimum subspace distance d.
The second one Aq (n, d, k) is the maximum size of a code
in Gq (n, k) with minimum subspace distance d (Grassmannian distance d/2). A related concept is a subspace design
or a block design t-(n, k, λ)q which is a collection S of
k-subspaces from Gq (n, k) (called blocks) such that each
subspace of Gq (n, t) is contained in exactly λ blocks of S.
In particular if λ = 1 this subspace design is called a qSteiner system and is denoted by Sq (t, k, n). Note, that such
a q-Steiner system is a Grassmannian code in Gq (n, k) with
minimum Grassmannian distance k − t + 1.
It was shown recently [8], [9] that subspace codes are
useful in vector network coding and by using subspace
codes it can be shown that vector network codes outperform
scalar linear network codes, in multicast networks, with
respect to the alphabet size. The comparison between the
alphabet size for a vector network coding solution is done
as follows. For a given network N , if there exists a vector
network coding solution with vectors of length t and a finite
field of size q and a scalar linear network coding solution
requires a finite field of size at least qs , then the gap in
the between the two solutions is qs − q t . The proof that
vector network coding outperforms scalar linear network
coding used a family of networks called the generalized
combination networks, where the combination networks
were defined and used in [21] (but were defined informally
before too).
The goal of this work is to show that there is a
tight connection between optimal Grassmannian codes and
network coding solutions for the generalized combination
networks. We will define two new dual distance measures
on Grassmannian codes which generalize the Grassmannian
distance. We discuss on the maximum sizes of the new
Grassmannian codes with the new distance measures. We
explore the connection between these codes and related
generalized combination networks. Our exposition will
derive some interesting properties of these codes with
respect to the traditional subspace codes and some subspace
designs. We will show, using two different approaches, that
codes in the Hamming space with minimum Hamming distance are a special case of subspace codes. Some interesting
connections to subspace designs will be also explored.
The rest of this paper is organized as follows. In
Section II we present the combination network and its
generalization which was defined in [8], [9]. We discuss
the family of codes which provide network coding solutions
for these networks. In Section III we further consider this

family of codes, define two dual distance measures on these
codes, and show how these codes and the distance measures
defined on them generalize the conventional Grassmannian
codes and Grassmannian distance. We show the connection
of these codes with subspace designs. We prove that for
each such code of the largest size, over Fq , there exists a
generalized combination network which is solved only by
this code (or a code with more relaxed parameters). We also
discuss how codes in the Hamming space form a subfamily
of these subspace codes. Finally, we show which subfamily
of these codes is useful for vector network coding. In
Section IV we present basic results for the bounds on sizes
of these codes and concentrate on the subfamily of these
codes which are useful to show how vector network coding
outperform scalar linear network coding. We analyse this
family of codes in general and concentrate on one specific
code with specific parameters in particular. In Section V
we provide a conclusion and directions for future research.
II. G ENERALIZED COMBINATION NETWORKS
In this section we will define the generalized combination network which is a generalization of the combination
network [21]. This network defined in [8], [9] was used to
prove that vector network coding outperforms scalar linear
network coding with respect to the alphabet size.
The generalized combination network is called the
ǫ-direct links ℓ-parallel links Nh,r,s network, in short the
(ǫ, ℓ)-Nh,r,s network. The network has three layers. In the
first layer there is a source with h messages. In the second
layer there are r nodes. The source has ℓ parallel links
to each node in the middle layer. From any α = s−ǫ
ℓ
nodes in the middle layer, there are ℓ parallel
links to one

receiver in the third layer, i.e. there are αr receivers in the
third layer. Additionally, from the source
there are ǫ direct

parallel links to each one of the αr receivers in the third
layer. Therefore, each receiver has s = αℓ + ǫ incoming
links. The (0, 1)-Nh,r,s network is the combination network
defined in [21]. We will assume some relations between the
parameters h, α, ǫ, and ℓ such that the resulting network is
interesting and does not have a trivial or no solution [8].
Theorem 1. The (ǫ, ℓ)-Nh,r,αℓ+ǫ network has a trivial
solution if ℓ + ǫ ≥ h, and it has no solution if αℓ + ǫ < h.
Otherwise, the network has a nontrivial solution.
The immediate natural question is which codes will solve
the generalized combination network over Fq . The answer
is quite simple. Since each receiver has ǫ direct links from
the source, it follows that the source can send any required
ǫ-subspace of Fhq to the receiver. Hence, the receiver must
be able to obtain an (h−ǫ)-subspace of Fhq from the middle
layer nodes connected to it. The receiver is connected to
α nodes in the middle layer and each one can send to the
receiver an ℓ-subspace of Fhq . Hence, a solution for the
network exists if and only if there exists a code with r ℓsubspaces of Fhq , such that each α codewords (ℓ-subspaces)
span a subspace whose dimension is at least h − ǫ.
III. C OVERING /M ULTIPLE G RASSMANNIAN C ODES
In this section we provide the formal definition for
the codes required to solve the generalized combination

networks. We define two distance measures on these codes,
prove that both Grassmannian codes, codes in the Hamming
space, and subspace designs, are subfamilies of this family
of codes. We present some basic properties of these codes
and their connection to the solution of the generalized
combination networks.
An α-(n, k, δ)cq covering (generalized) Grassmannian
code (code in short) C is a subset of Gq (n, k) such that
each α codewords of C span a subspace of dimension at
least δ + k in Fnq . The following theorem is easily verified.
Theorem 2. A code C in Gq (n, k) with Grassmannian
distance δ is a 2-(n, k, δ)cq Grassmannian code.
Theorem 2 implies that the Grassmannian codes form
a subfamily of the α-(n, k, δ)cq codes. It is also natural to define the quantity δ as the minimum α-covering
Grassmannian distance of the code, where the 2-covering
Grassmannian distance is just the Grassmannian distance.
In other words, the α-covering Grassmannian distance of
α subspaces in Gq (n, k) is the dimension of the subspace
which they span in Fnq minus k. A natural problem is
to find maximum size of such codes? For this we define
the quantity Bq (n, k, δ; α) to be the maximum size of an
α-(n, k, δ)cq code. From our discussion it can be readily
verified that if C is an α-(n, k, δ)cq code which attains
Bq (n, k, δ; α) then C solves the (ǫ, k)-Nn,r,αk+ǫ network,
where ǫ = n − δ − k and r = Bq (n, k, δ; α). But, clearly
we also have from our previous discussion that such a code
has parameters with the minimum conditions which are
necessary to solve such a network. Thus, each such code
of the maximum size is exactly what needed to solve a
certain instant of the generalized combination networks.
Finally, for a given Grassmannian code C in Gq (n, k) we
can define covering hierarchy, where the 1-covering is just
k, the α-covering is the α-covering Grassmannian distance
of C plus k. This hierarchy is a q-analog for the generalized
Hamming weights [24] for constant weight codes.
The way we have described the code which solves
the generalized combination network is very natural when
we consider the definition of the generalized combination
network. We have also defined a natural generalization for
the Grassmannian distance, although some might argue that
it is less natural from a point of view of a code definition.
Hence, we will give now a more natural definition from
a point of view of coding theory, or more precisely from
a point of view of a packing, which is the combinatorial
property of an error-correcting code. For this we will need
to use the dual subspace V ⊥ of a given subspace V in Fnq ,
and the orthogonal complement of a given code C. For a
code C in Pq (n) the orthogonal complement C⊥ is defined
def
by C⊥ = {V ⊥ : V ∈ C}. It is well-known [7] that
the minimum subspace distance of C and C⊥ are equal.
The following lemma is also well known (see for example
Lemma 12 in [7]).

Corollary 1. For any given set of α subspaces
V1 , V2 , . . . , Vα of Fnq we have
!⊥
α
α
X
\
⊥
.
Vi
Vi =
i=1

i=1

Corollary 1 induces a new definition of a distance measure for the orthogonal complements of the Grassmannian
codes which solve the generalized combination networks.
For a Grassmannian code C ∈ Gq (n, k), the minimum
λ-multiple Grassmannian distance is k − τ + 1, where τ
is the largest integer such that each τ -subspace of Fnq is
contained in at most λ k-subspaces of C.
Theorem 3. If C ∈ Gq (n, k) is an α-(n, k, δ)cq code
then C⊥ has minimum (α − 1)-multiple Grassmannian
distance δ.

Proof. By the definition of an α-(n, k, δ)cq code it follows
that for each α subspaces
V1 , V2 , . . . , Vα of C we have

Pα
Pα
⊥
≤
that dim
i=1 Vi
i=1 Vi ≥ δ + k and hence dim
n −Tδ − k. Therefore, by Corollary 1 we have that
α
dim i=1 Vi⊥ ≤ n − δ − k. This implies that each
subspace of dimension n − δ − k + 1 of Fnq can be
contained in at most α − 1 codewords of C⊥ . Thus, since
C⊥ ∈ Gq (n, n − k), it follows by definition that the
minimum (α − 1)-multiple Grassmannian distance of C⊥
is (n − k) − (n − δ − k + 1) + 1 = δ.
Theorem 3 leads to a new definition for Grassmannian
codes (orthogonal complements of α-(n, k, δ)cq codes).
An s-(n, k, λ)m
q multiple (generalized) Grassmannia code
(code in short) C is a subset of Gq (n, k) such that each
s-subspace of Fnq is contained in at most λ codewords of C.
Similarly, let Aq (n, k, s; λ) denote the maximum size of an
s-(n, k, λ)m
q code. One can verify that
Theorem 4. An s-(n, k, 1)m
q code is a Grassmannian
code in Gq (n, k) with minimum Grassmannian distance
k − s + 1.
Clearly, by Theorem 4 we have that the λ-multiple
Grassmannian distance is a generalization of the Grassmannian distance (1-multiple Grassmannian distance). The
generalization implied by Theorem 4 is for the packing
interpretation of an s-(n, k, 1)m
q code. If each s-subspace
is contained exactly once in an s-(n, k, 1)m
q code C, then
C is a q-Steiner system Sq (s, k, n). If each s-subspace is
contained exactly λ times in an s-(n, k, λ)m
q code C, then C
is an s-(n, k, λ)q subspace design. Similarly to Theorem 3
we have
Theorem 5. If C ∈ Gq (n, k) is an s-(n, k, λ)m
q code
then C⊥ has minimum (λ + 1)-covering Grassmannian
distance k − λ + 1.
Corollary 2. C ∈ Gq (n, k) is an α-(n, k, δ)cq code if and
only if C⊥ is an (α − 1)-(n, n − k, n − k − δ + 1)m
q code.

Lemma 1. For any two subspaces U, V in Pq (n) we have
that U ⊥ ∩ V ⊥ = (U + V )⊥ .

Corollary 3. For any feasible s, k, n, and λ, we have that
Aq (n, k, s; λ) = Bq (n, n − k, k − λ + 1; λ + 1).

Clearly, by induction we have the following consequence
from Lemma 1.

Not all Grassmannian codes can be used as solutions
in vector network coding. If there are h messages and

each message is a vector of length t over Fq , then each
link will carry a t-subspace of Fht
q . Therefore, the only
Grassmannian codes which are used in vector network
coding are α-(ht, ℓt, δt)cq codes, where 1 ≤ ℓ ≤ h − 1,
1 ≤ δ ≤ h − 1, and 2 ≤ α.
It should be noted that codes in the Hamming space with
the Hamming distance form a subfamily of the subspace
codes. This can be shown using two different approaches.
The first one was pointed in 1957 by Tits [23] who
suggested that combinatorics of sets could be regarded as
the limiting case q → 1 of combinatorics of vector spaces
over the finite field Fq .
The second approach is based on the solution for the
generalized combination networks. It was proved in [21]
that the (0, 1)-Nh,r,s network has a scalar linear solution
over Fq if and only if there exists a linear code, over Fq ,
of length r, dimension h, and minimum Hamming distance
r − s + 1. For such a code we have an h × r generator
matrix G for which any set with s columns has a subset
of h linearly independent columns. These r columns of G
form an s-(h, 1, h − 1)cq code. Such codes were already
very well studied in coding theory (and also in projective
geometry, see [11]) and we omit their discussion here.
Linear codes in the Hamming schemes can be used also
in other ways as solutions for the generalized combination
network. Let C be a linear code, over Fq , of length n,
dimension k, and minimum Hamming distance d. For such
a code, in the (n− k)× n parity-check matrix H each d− 1
columns are linearly independent. Hence, the n columns of
H form an (d− 1)-(n− k, 1, d− 2)cq code. This code solves
the (n − k − d + 1, 1)-Nn−k,n,d−1 network.
Each s-(h, 1, δ)cq code C which solves the (ǫ, 1)-Nh,r,s
network yields also a related vector solution. This solution
forms an s-(ht, t, δt)cq code C′ with the sam size as C, but
usually much larger codes than |C| can be constructed.
Also nonlinear codes can be used as solutions for the
generalized combination networks. Some of them (for the
combination networks) were discussed in [21] and some
will be discussed in the full version of this paper.
IV. B OUNDS

ON THE

S IZES OF C ODES

In this section we will present some bounds on the sizes
of codes. Clearly, there is a huge ground for research since
the parameters of the codes are in a very large range and
our knowledge is very limited. Hence, we will give a brief
discussion. More will be given in the full version of the
paper. We will give some ideas and some insight about the
difficulty of obtaining new bounds and especially the exact
size of optimal codes. The bounds are on Aq (n, k, s; λ)
and on Bq (n, k, s; α) and clearly by Corollary 3, bounds
only on one of them is needed since they are equivalent.
There is duality between the two types of codes which were
considered with two dual distance measures. We start by
considering this duality and related four different simple
approaches for bounds on the maximum sizes of codes.
In an α-(n, k, δ)cq code C, each subset of α codewords
(k-subspaces) span a (δ + k)-subspace of Fnq . In other
words, each (δ + k − 1)-subspace of Fnq contains at most
α − 1 subspaces of C. The orthogonal complement C⊥ is

an (α − 1)-(n, n − k, n − δ − k + 1)m
q code. In such a
code each (n − δ − k + 1)-subspace of Fnq is contained
in at most α − 1 codewords. In other words, any set of
α codewords intersect in a subspace of dimension at most
n−δ−k. Bounds can be obtained based on any one of these
four observations. Each one can give another direction to
obtain related bounds.
The classic bounds for the cases λ = 1 or α = 2, for an
c
s-(n, k, λ)m
q code and an α-(n, k, δ)q code, respectively,
can be easily generalized for higher λ (respectively, α),
where the simplest ones are the packing bound and the
Johnson bounds [7]. It might be easier to generalize the
bounds when we consider s-(n, k, λ)m
q codes.
Theorem 6. If n, k, s, and λ are
 positive integers such
that 1 ≤ s < k < n and 1 ≤ λ ≤ ns q , then
$ n %
s q

Aq (n, k, s; λ) ≤ λ k

.

s q

Corollary 4. If n, k, δ, and α are positive integers
such
 
that 1 < k < n, 1 ≤ δ ≤ n − k and 2 ≤ α ≤ nk q , then


 


n

n−δ−k+1 q 
Bq (n, k, δ; α) ≤ (α − 1) 
  .
k
n−δ−k+1 q

Theorem 7. If n, k, s, and λ are
 positive integers such
that 1 ≤ s < k < n and 1 ≤ λ ≤ ns q , then

 n
q −1
Aq (n − 1, k − 1, s − 1; λ) .
Aq (n, k, s; λ) ≤ k
q −1

Corollary 5. If n, k, δ, and α are positive integers
such
 
that 1 < k < n, 1 ≤ δ ≤ n − k and 2 ≤ α ≤ nk q , then

 n
q −1
Bq (n − 1, k − 1, δ; α) .
Bq (n, k, δ; α) ≤ k
q −1

Theorem 8. If n, k, s, and λ are
 positive integers such
that 1 ≤ s < k < n and 1 ≤ λ ≤ ns q , then
 n

q −1
Aq (n, k, s; λ) ≤ n−k
Aq (n − 1, k, s; λ) .
q
−1

Corollary 6. If n, k, δ, and α are positive integers
such
 
that 1 < k < n, 1 ≤ δ ≤ n − k and 2 ≤ α ≤ nk q , then
 n

q −1
Bq (n, k, δ; α) ≤ n−k
Bq (n − 1, k, δ; α) .
q
−1
Finally, also the following bound was obtained.
Theorem 9. If k + δ ≤ n ≤ 2k, then
Bq (n, δ, k; α) ≥ (α − 1)Bq (n, δ, k; 2) , and
(α−1)q k(n−k−δ+1) ≤ Bq (n, δ, k; α) ≤ (α−1)Q(q)q k(n−k−δ+1) ,
Q
−j
where Q(q) = ∞
).
j=1 (1 − q
We would also like to mention that some bounds can be
obtained from known results on arcs and caps in projective
geometry [11]. Discussion on these will be given in the full
version of this paper.
How good are these bounds? Can the bound of Theorem 6 be attained? If λ = 1 then good constructions and

asymptotic bounds are known [2], [6]. But, Theorem 6
might be misleading. Consider the case where n = 6,
k = 4, s = 3, λ = 1, and q = 2. By Theorem 6 we
have that A2 (6, 4, 3; 1) ≤ 93, while the actual value is
A2 (6, 4, 3; 1) = 21. This is not unique for these parameters,
and it occurs since Aq (n, k, s; 1) = Aq (n, n − k, n − 2k +
s; 1), i.e. we should consider only k ≤ n/2, when λ = 1.
For λ > 1 (respectively, α > 2) there is no similar connection between codes of Gq (n, k) and codes of Gq (n, n − k).
The big difference is when k > n/2. A good example can
be given by considering the (1, 1)-N3,r,4 network which
was used in [8] to show that there is a network with three
messages for which vector network coding outperforms
scalar linear network coding. For a vector solution of this
network we need an 3-(3t, t, t)cq code. For simplicity and
for explaining the problems in obtaining lower and upper
bounds on Aq (n, k, s; λ) we consider the case of t = 2 and
q = 2, i.e. a 3-(6, 2, 2)c2 code or its orthogonal complement
a 3-(6, 4, 2)m
2 code. In [9] a code with 51 codewords was
presented. By using a modification on rank-metric codes
we can find a 2-(6, 4, 3)m
2 code of size 64. But, when a
3-(6, 2, 2)c2 code was considered a code of size 82 was
obtained [5] using a general method. This general methods
implies that
B2 (n + 2, 2, 2; 3) ≥ 8B2 (n, 2, 2; 3) + 2,
for n ≥ 3. How these lower bounds are compared
with the upper bound? By Theorem 6 we have that
A2 (6, 4, 3; 2) ≤  186. By Theorem
7 we have that

A
(5,
3,
2;
2)
.
Hence,
we have to
A2 (6, 4, 3; 2) ≤ 63
2
15
consider the value of A2 (5, 3, 2; 2). An upper bound on
A2 (5, 3, 2; 2) involves some more complicated analysis of
the way that the 3-subspaces of the related codes are obtained from extensions of subspaces in F42 using also some
sets of linear equations. A bound of A2 (5, 3, 2; 2) ≤ 34 [5]
was obtained and hence A2 (6, 4, 3; 2) ≤ 142. A code of
size 30 [5] was found and hence 30 ≤ A2 (5, 3, 2; 2) ≤ 34.
Recently, these last results were improved and some other
interesting bounds were obtained by Sascha Kurz [18].
There is a sequence of subspace designs in which each
s-subspace is contained in exactly λ times, which form
optimal generalized Grassmannian codes. These subspace
designs have small block length and very large λ. Hence,
they are limited for solutions of generalized combination
networks for which the subspaces have dimension close to
the one of the ambient space. For example, Thomas [20]
have constructed a 2-(n, 3, 7)2 design, where n ≥ 7 and
n ≡ 1 or 5 (mod 6). This is the same as a 7-(n, 3, 2)m
2
code and its orthogonal complement is an 8-(n, n − 3, 2)c2
code. Such a code provides a solution for the (1, n − 3)Nn,7·381,8(n−3)+1 network. Note, that even for the smallest
number of messages n, i.e. n = 7, the in-degree of each
receiver is 33. It looks more interesting to find solutions for
generalized combination networks for which the number of
parallel links is small compared to the number or messages.
Some interesting codes and related networks exist for small
parameters. For example, consider the 2-(6, 3, 3)2 design
presented in [3], which is a 3-(6, 3, 2)m
2 code and its
orthogonal complement is a 4-(6, 3, 2)c2 code. Such a code

provides a solution for the (1, 3)-N6,279,13 network. Other
designs which lead to optimal codes for related networks
can be found in many recent papers on this emerging topic.
V. C ONCLUSIONS

AND

O PEN P ROBLEMS

We have introduced a new family of Grassmannian
codes with two new distance measures which generalize the traditional Grassmannian codes and Grassmannian
distance. There is a correspondence between the set of
these codes of maximum size and the set of generalized
combination networks. There is a natural generalization of
our exposition to subspace codes, where codewords can be
of different dimensions. The investigation we have started
for bounds on the sizes of such codes is very preliminary
and there are many obvious coding questions related to
these codes and they are currently under research and will
provide lot of ground for future research. All these issues
will be addressed in the full version of this paper. Another
issue is the related distance measures in the Hamming
scheme, where our suggested distance measures are the
q-analog. This direction will be discussed in another work.
R EFERENCES
[1] R. Ahlswede, N. Cai, S.-Y. R. Li, and R. W. Yeung, “Network
information flow”, IEEE Trans. Inform. Theory, vol. 46, pp. 1204–
1216, 2000.
[2] S. Blackburn and T. Etzion, “The Asymptotic Behavior of Grassmannian Codes”, IEEE Trans. Inform. Theory, vol. 58, pp. 6605–
6609, 2012.
[3] M. Braun, A. Kerber, and R. Laue, “Systematic construction of qanalogs of t−(v, k, λ)-designs”, Designs, Codes, and Cryptography,
vol. 34, pp. 55–70, 2005.
[4] J. B. Ebrahimi and C. Fragouli, “Algebraic algorithms for vector
network coding”, IEEE Trans. Inform. Theory, vol. 57, pp. 996–
1007, 2011.
[5] T. Etzion, K. Otal, and F. Özbudak, manuscipt in preparation.
[6] T. Etzion and N. Silberstein, “Codes and Designs Related to Lifted
MRD Codes”, IEEE Trans. Inform. Theory, vol. 59, pp. 1004–1017,
2013.
[7] T. Etzion and A. Vardy, “Error-correcting codes in projective space”,
IEEE Trans. on Inform. Theory, vol. 57, pp. 1165–1173, 2011.
[8] T. Etzion and A. Wachter-Zeh, “Vector network coding based on
subspace codes outperforms scalar linear network coding”, IEEE
Trans. on Inform. Theory, to appear.
[9] T. Etzion and A. Wachter-Zeh, “Vector network coding based on
subspace codes outperforms scalar linear network coding”, Proc.
of IEEE Int. Symp. on Inform. Theory (ISIT), pp. 1949–1953,
Barcelona, Spain, July 2016.
[10] C. Fragouli and E. Soljanin, “(Secure) Linear network coding
multicast”, Designs, Codes, and Crypt., vol. 78, pp. 269–310, 2016.
[11] J. W. P. Hirschfeld and L. Storme, “The packing problem in
statistics, coding theory and nite projective spaces: Update 2001”,
Finite Geometries (Developments in Mathematics), vol. 3. Dordrecht,
The Netherlands: Kluwer, pp. 201–246, 2001.
[12] T. Ho, R. Koetter, M. Médrad, D. R. Karger, M. Effros, “The benefits
of coding over routing in randomized setting”, Proc. of IEEE Int.
Symp. on Inform. Theory (ISIT), Yokohama, Japan, June/July 2003.
[13] T. Ho, M. Médrad, R. Koetter, D. R. Karger, M. Effros, J. Shi, B.
Leong, “A random linear network coding approach to multicast”,
IEEE Trans. Inform. Theory, vol. 52, pp. 4413–4430, 2006.
[14] S. Jaggi, P. Sanders, P. A. Chou, M. Effros, S. Egner, K. Jain,
L. Tolhuizen, “Polynomial time algorithms for multicast network
code construction”, IEEE Trans. Inform. Theory, vol. 51, pp. 1973–
1982, 2005.
[15] S.-Y. R. Li, R. W. Yeung, and N. Cai, “Linear network coding”,
IEEE Trans. Inform. Theory, vol. 49, pp. 371–381, 2003.
[16] R. Kötter and M. Médrad, “An algebraic approach to network
coding”, IEEE Trans. Networking, vol. 11, pp. 782–795, 2003.
[17] R. Kötter and F. R. Kschischang, “Coding for errors and erasures in
random network coding”, IEEE Trans. on Inform. Theory, vol. 54,
pp. 3579–3591, 2008.

[18] S. Kurz, personal communication.
[19] A. Rasala Lehman and E. Lehman, “Complexity classification of
network information flow problems”, Proc. 15th Annu. ACM/SIAM
Symp. Discrete Algorithms (SODA), pp. 142–150, New Orleans, LA,
January 2004.
[20] S. Thomas, “Designs over finite fields”, Geometriae Dedicata,
vol. 21, pp. 237–242, 1987.
[21] S. Riis and R. Ahlswede, “Problems in network coding and error
correcting codes” appended by a draft version of S. Riis “Utilising
public information in network coding”, General Theory of Information Transfer and Combinatorics, in Lecture Notes in Computer
Science, vol. 4123 pp. 861–897, 2006.
[22] D. Silva and F. Kschischang, “On metrics for error correction in
network coding”, IEEE Trans. Inform. Theory, vol. 55, pp. 5479–
5490, 2009.
[23] J. Tits, Sur les analogues algébriques des groupes semi-simples
complexes, in Colloque d’Algébre Supèrieure, tenu á Bruxelles du 19
au 22 décembre 1956, Centre Belge de Recherches Mathématiques
Établissements Ceuterick, Louvain, Paris: Librairie Gauthier-Villars,
pp. 261–289, 1957.
[24] V. K. Wei, “Generalized Hamming weights for linear codes,” IEEE
Trans. Inform. Theory, vol. 37, pp. 1412–1418, 1991.

