IEICE TRANS. FUNDAMENTALS, VOL.E90–A, NO.9 SEPTEMBER 2007

1729

PAPER

Special Section on Information Theory and Its Applications

Construction Algorithm for Network Error-Correcting Codes
Attaining the Singleton Bound
Ryutaroh MATSUMOTO†a) , Member

SUMMARY
We give a centralized deterministic algorithm for constructing linear network error-correcting codes that attain the Singletonbound of network error-correcting codes. The proposed algorithm is basedon the algorithm by Jaggi et al. We give estimates on the time complexity
and the required symbol size of the proposed algorithm. We also estimate
the probability of a random choice of local encoding vectors by all intermediate nodes giving a network error-correcting codes attaining the Singletonbound. We also clarify the relationship between the robust network coding
and the network error-correcting codes with known locations of errors.
key words: error correction, MDS code, network coding, random network
coding, Singleton bound1.

Introduction

Ahlswede et al. [1] proposed the notion of network coding that multicasts data from a single sender to multiple
receivers at a rate at which the ordinary store and forward
routing cannot multicast the data. Such high rate multicast
becomes feasible by allowing intermediate nodes to encode
and decode the data. A sender is usually called a source anda receiver is called a sink. A network coding is said to be linear if every intermediate node outputs a linear combinationof its inputs [10].
A study of network coding usually assumes that an error does not occur in networks. Recently, Cai and Yeung[2], [13] considered errors in network coding, and proposed
the network error correcting codes that allow sinks to recover the information even when errors occur on intermediate edges in the network. After formulating the network
error correction, they proposed the lower and upper bounds
on the number of messages in a network α-error correcting
code, and one of their upper bound was a natural generalization of the Singleton bound for the ordinary error-correcting
codes. Recently, Zhang [14] and Yang et al. [11] independently observed that the Singleton bound can be refined. We
note that the problem formulation in [2], [13] was later independently presented in [4]. (The proceedings paper of [2],[13] appeared in 2002.)
Cai and Yeung mostly considered the case that intermediate nodes perform only simple encoding and decoding
without delay, such as computing the output of the node as a
Manuscript received December 11, 2006.
Manuscript revised March 30, 2007.
Final manuscript received May 17, 2007.
†
The author is with the Department of Communications andIntegrated Systems, Tokyo Institute of Technology, Tokyo, 1528550 Japan.
a) E-mail: ryutaroh@rmatsumoto.org
DOI: 10.1093/ietfec/e90–a.9.1729

linear combination of its inputs, and the sinks perform complex decoding computation. The network error correcting
codes can avoid introducing decoding computation and delay into intermediate nodes, which is the advantage over useof ordinary error correcting codes between nodes.
Note that a similar type of network failure in a slightly
diﬀerent context was considered in [7, Sect. V] and [6,Sect. VI] in which every sink is assumed to know the set offailed edges and failed edges are assumed to emit zero symbols. Network error correction does not assume the knowledge of edges causing errors, and the problem formulation
is diﬀerent from [6], [7]. Note also that Kurihara [8] considered the diﬀerent notion of robustness. In his paper, heconsidered network coding that allows sinks to recover partial information with edge failures.
For the construction of the network error-correcting
codes, Jaggi et al. [5] proposed a randomized construction that uses coding among diﬀerent time intervals. Theirmethod produces codes attains the Singleton bound withhigh probability with suﬃciently long block length, where
the block length refers to the number of time intervals
among which coding is done. It is desirable to have a network error-correcting code that does not code among diﬀerent time intervals and thus does not introduce delay. Concurrently to this paper, Yang et al. [11] proposed an explicit
construction algorithm that produces codes attaining the refined Singleton bound. The idea in [11] is similar to thispaper in the sense that they also regard errors as information from the source and add extra components in the global
encoding vectors corresponding to errors.
In this paper, we give a deterministic and centralizedalgorithm that constructs a network error-correcting codethat attains the Singleton bound of network error-correcting
codes obtained in [13]. We also give a relationship between
the success probability and the field size for successful construction of network error-correcting codes when intermediate nodes choose their encoding coeﬃcients randomly andindependently. The proposed algorithms are based on [6].
Our network error-correcting codes make multicast robust toerrors without introducing delay in the transmission, which
is very attractive to delay sensitive multicast applications,such as multicast of video or audio. Our method is also
useful for cryptographic applications, because it can tolerate modification and deletion of data by an adversary.
This paper is organized as follows. Section 2 introduces notations and the model of errors. Section 3
proposes an algorithm for constructing network error-

c 2007 The Institute of Electronics, Information and Communication Engineers
Copyright IEICE TRANS. FUNDAMENTALS, VOL.E90–A, NO.9 SEPTEMBER 2007

1730

correcting codes attaining the Singleton bound. Section 4shows how to modify the algorithm in Sect. 3 to attain therefined Singleton bound, the success probability of the random construction of network error-correcting codes, and therelationship between the robust network coding [6], [7] andthe network error-correcting codes with known locations oferrors [12]. Section 5 gives concluding remarks.
2.

Very recently, Zhang [14] and Yang et al. [11] observedthat the above proposition can be refined as follows.
Proposition 2: [11], [14] Let nt be the min-cut from thesource s to a sink t. If the sink t can correct any αt errors
then the number M of messages in the network correcting
code, not necessarily linear, is upper bounded by
M ≤ qnt −2αt .

Preliminary

2.1 Basic Notations
We consider an acyclic directed graph G = (V, E) with possible parallel edges of unit capacity. V  s denotes the source
and V ⊃ T denotes the set of sinks. Let n be the smallest
min-cut separating s from any t ∈ T throughout this paper.
For v ∈ V, Γ+ (v) (resp. Γ− (v)) denotes the set of edges leaving (resp. reaching) the node v, and start(e) (resp. end(e))
denotes the node at which the edge e starts (resp. ends).
We consider linear coding over a finite field Fq withq elements. The source s gets k (≤ n) input symbols from
Fq . The symbol y(e) ∈ Fq carried by an edge e is a linear
combination of the symbols carried by the edges entering
start(e). The local encoding vector me : Γ− (start(e)) → Fq
determines the coeﬃcients of this linear combination, thatis,
y(e) =me (e )y(e ).
e ∈Γ− (start(e))

In this paper, a nonsink node performs only the computation of linear combination of its inputs, and they do notcorrect errors. An error is assumed to occur always at anedge. When an error occurs at an edge e, the symbol received by end(e) is diﬀerent from one sent by start(e), andend(e) computes its outputs as if there was no error at e.
The error value at an edge e is defined by the received symbol minus the transmitted symbol at e. Note that we express
a failure of a node v ∈ V in a real network as errors on edgesin Γ+ (v) in our model. The number of errors is the number of edges at which errors occur. A network code is said
to correct α errors if every sink can recover the original information sent by the source when α or less errors occur atarbitrary edges. We call the recovery of information by asink decoding.
We represent errors occurred in the whole network by
a vector e in F|E|
q , where |E| denotes the number of elements
in E. Fix some total ordering in E, and enumeration of theerror values gives e.
Regarding on the number of messages in a network αerror correcting code, Cai and Yeung obtained the following
result.
Proposition 1: [13] The number M of messages in a network α-error correcting code, not necessarily linear, is upperbounded by
M ≤ qn−2α .

2.2 Jaggi et al.’s Algorithm for Construction of an Ordinary Network CodeIn this subsection, we review Jaggi et al.’s algorithm [6] forconstruction of an ordinary network coding. The proposed
algorithm uses a modified version of their algorithm.
Since linear coding is used, the information carried byan edge e is a linear combination of k information symbols
in Fq . We can characterize the eﬀect of all the local encoding vectors on an edge e independently of a concrete k information symbols using global encoding vectors b(e) ∈ Fkq .
When the information from the source is i ∈ Fkq , the transmitted symbol on an edge e is equal to the inner productof i and b(e). In order to decide the encoding at the source
node s, we have to introduce an imaginary source s and kedges of unit capacity from s to s. We regard that s sends
k symbols to s over k edges.
We initially computes an s -t flow f t of magnitude kfor each t ∈ T and decomposes this flow into k edge disjoint
paths from s to t. If an edge e is on some flow path W fromt(e) denote the predecessor edge of the edges to t, let f←e on the path W. Jaggi et al.’s algorithm steps through thenodes v ∈ V in a topological order induced by the directed
graph G. This ensures that the global encoding vectors of alledges reaching v are known when the local encoding vectorsof the edges leaving v are determined. The algorithm defines
the coeﬃcients of me for one edge e ∈ Γ+ (v) after the other.
There might be multiple flow paths to diﬀerent sinks throughan edge e. Let T (e) denote the set of sinks using e in somet(e) | t ∈ T (e)} denote the set offlow f t and let P(e) = { f←predecessors edges of e in some flow path. The value 0 ischosen for me (e ) with edges e  P(e).
We introduce two algorithmic variables Bt and Ct thatare updated by Jaggi et al.’s algorithm. Ct contains one edge
from each path in f t , namely the edge whose global encoding vector was defined most recently in the path. Bt = {b(e) |e ∈ Ct } is updated when Ct is updated. The algorithm determines me so that for all t ∈ T , Bt is linearly independent.
After finishing the algorithm, every sink can decode theoriginal information because Bt is linearly independent.
3.

Construction Algorithm

We shall propose an algorithm constructing a network αerror correcting code carrying k information symbols in Fq
with n − k ≥ 2α, which is equivalent to the Singleton bound(Proposition 1). The proposed construction is based on [6].

MATSUMOTO: OPTIMAL NETWORK ERROR-CORRECTING CODES

1731

We assume that the size of alphabet Fq satisfies
 |E|q > |T | ·
.
2α

(1)

Definition 3: For the original information i ∈ Fkq and the− e) ∈ Fq|Γ (t)| be the vector of symbols
error e ∈ F|E|
q , let φt (i, carried by the input edges to t.
Lemma 4: If a sink t can decode the original information iwith any 2α or less errors whose locations are known to thesink t, then the sink t can decode the original information
with any α or less errors without the knowledge of the error
locations under the assumption that the number of errors is≤ α.
Note that errors with known locations are called erasures in[12] and the properties of erasures are also studied in [12].
Proof: Denote the Hamming weight of a vector x by w(x).
The assumption of the lemma implies that for any i  j ande with w(e) ≤ 2α we haveφt (i, e)  φt (j, 0).

Fig. 1 Example of a network with imaginary nodes and edges. Nodes A
and B are the imaginary nodes added in Step 2 and the dashed lines from s
to A and B represent the imaginary edges added in Step 2. See Example 6
for explanation.

(2)

Equation (2) implies that for any i  j and e1 , e2 withw(e1 ) ≤ α and w(e2 ) ≤ α we haveφt (i, e1 )  φt (j, e2 ),which guarantees that t can decode the original information
under the assumption that the number of errors is ≤ α byexhaustive search.

Remark 5: The above lemma does not guarantee the existence of an eﬃcient decoding algorithm.
Fix F ⊂ E with |F| = 2α. We shall show how to construct a network error-correcting code that allows every sink
to decode the original information when the errors can occur
only at F. We call F the error pattern. The following description is a condensed version of the proposed algorithm,
which is equivalent to the full description with F = {F} in
Fig. 2.
1. Add the imaginary source s and draw k edges from s
to s.
2. Add an imaginary node v at the midpoint of each e ∈ F
and add an edge of unit capacity from s to each v.
3. For each sink t, do the following:a. Draw as many edge disjoint paths from s to t
passing through the imaginary edges added at
Step 2 as possible. Let mtF (≤ 2α) be the numberof paths.
b. Draw k edge disjoint paths passing through s thatare also edge disjoint from the mtF paths drawn in
the previous step.

4. Execute the algorithm by Jaggi et al. with t∈T (k + mtF )edge disjoint paths constructed in Step 3.

Example 6: In Fig. 1, we give an example of addition ofimaginary nodes and edges. The network structure in Fig. 1
is taken from [3, Fig. 2]. Nodes A and B are the imaginary
nodes added in Step 2 and the dashed lines from s to A andB represent the imaginary edges added in Step 2.
The min-cut from s to every sink is 4 in the original
network. The set F of edges with errors consists of the edge
from s to node 1 and the edge from node 1 to node 5.
We denote a path by enumerating nodes on the path. In
Step 3a for t1 we can find two edge disjoint paths, namely(s , A, 1, t1 ) and (s , B, 5, 8, t1). On the other hand, in Step 3afor t2 , we can find only one edge disjoint path, namely(s , A, 1, B, 5, 8, t2) or (s , B, 5, 8, t2). Therefore mtF1 = 2
while mtF2 = 1.
In Step 3b for t1 , we find two edge disjoint pathsas (s , s, 3, 6, 9, t1) and (s , s, 4, 7, 10, t1). In Step 3b for
t2 , we find three edge disjoint paths as (s , s, 2, 6, 9, t2),(s , s, 3, 7, 10, t2), and (s , s, 4, t2 ). We can use arbitrary twopaths among the three paths. In either case, we can findn − mtF paths in Step 3b.
In Step 3b, we can guarantee the existence of k paths asfollows: Suppose that edges in mtF paths used in Step 3a areremoved from the original network (V, E). Then the min-cut
from s to a sink t in the original network (V, E) is at leastn − mtF , which is larger than or equal to k.
In Step 4 we use the algorithm by Jaggi et al. as if theimaginary source s sent information on the α imaginaryedges added in Step 2. We denote by BtF the set Bt of global
encoding vectors for k + mtF edge disjoint paths. BtF consistsof k + mtF vectors of length k + 2α. We require that every
sink t is able to decode k information symbols, while t may
be unable to decode 2α error symbols in general because
mtF ≤ 2α.
There are always two edges end at the added imagi-

IEICE TRANS. FUNDAMENTALS, VOL.E90–A, NO.9 SEPTEMBER 2007

1732

nary node v and one edge starts from v in Step 2. Since v
is imaginary, we cannot choose local encoding vectors at v.
Therefore, in Step 4, all components in the local encoding
vector at v must be selected to 1, which keeps Bt linearly independent. The reason is as follows: Let e be the edge froms to v added in Step 2. The global encoding vector of e is of
the form(0 j−1 , 1, 0n− j ),that is, it has only 1 at the j-th component. All other global
encoding vectors in BtF have zero at the j-th component,
since they are not in downstream of e when we choose local encoding vectors at v. Therefore, the added imaginary
node v does not interfere with the execution of Jaggi et al.’s
algorithm.
Observe also that q > |T | guarantees the successful execution of the algorithm as with the original version of Jaggi
et al.’s algorithm.
We shall show how each sink t can decode the original
information sent from the source s. After executing Step 4
we have decided all the local encoding vectors in the original
network (V, E). Consider the three linear spaces defined by
V1 = {φt (i, e) | i ∈ Fkq , e ∈ F|E|q },V2 = {φt (i, 0) | i ∈ Fkq },V3 = {φt (0, e) | e ∈ F|E|q },where components in e corresponding to E \ F are zero, andφt is as defined in Definition 3. We consider V1 , V2 , andV3 in the original network (V, E) without added imaginary
nodes and edges. Then we have
V1 = V2 + V3 , dim V2 ≤ k.

(3)

Since we keep BtF linearly independent,
dim V1 ≥ k + mtF .

(4)

Since the maximum number of edge disjoint paths passing
through the imaginary edges added in Step 2 is mtF , we havedim V3 ≤ mtF .

(5)Equations (3–5) imply
dim V1 = k + mtF ,dim V2 = k,dim V3 = mtF ,dim V2 ∩ V3 = 0.

(6)
(7)

The number of nonzero components in φt (i, e) is k + mtF andthe number of unknowns in φt (i, e) is k + 2α, which can belarger than k + mtF . However, by Eq. (7), the sink t can compute φt (i, 0) from φt (i, e) as follows: Write φt (i, e) as u + v
such that u ∈ V2 and v ∈ V3 . By Eq. (7) u and v are uniquelydetermined [9, p.19, Theorem 4.1]. We have u = φt (i, 0) andthe eﬀect of errors is removed. The sink t can also compute(* Initialization *)Added imaginary node s and edges e1 , . . . , ek from s to s. O(k)foreach error pattern F ∈ F do
Initialize global encoding vectorbF (ei ) = (0i−1 , 1, 0k+2α−i ) ∈ Fk+2α.
O((k + 2α)2 )qforeach edge e ∈ F do
Add an imaginary node v at the midpoint of e ∈ F.
O(1)Divide e into an edge to v and an edge from v.
O(1)(*) O(1)Draw an imaginary edge from s to v.
endforeachforeach sink t ∈ T do
Draw as many edge disjoint paths from s to t as possible
passing through the edge added in (*).
O(2α(|E| + k + 4α))Draw k edge disjoint path from s to t passing throughs and also disjoint from paths made in the previous step.
O(k(|E| + k + 4α))Initialize the basis BtF = {bF (ei ) | ei is on a path to t}.
O((k + 2α)2 )endforeach
endforeach(* Main loop *)
foreach edge e ∈ F∈F E F \ {e1 , . . . , ek } in a topological order do
if start(e) ∈ V then
Choose a linear combination bF (e) = p∈PF (e) me (p)b(p)Fsuch that Bt remains linearly independent for all t
and F by the method in [6, Sect. III.B].
(**)
else

me (p) = 1 for all p ∈ PF (e) and bF (e) = p∈PF (e) b(p).
O(k + 2α)endif
endforeach
return {me (·) | start(e) ∈ V}.
Fig. 2 Construction algorithm for a network α-error correcting code.
The rightmost O(·) indicates the time complexity executing the step.

the original information i from φt (i, 0) by Eq. (6).
We shall describe how to construct a network errorcorrecting code that can correct errors in any edge set F ⊂ Ewith |F| = 2α. Let F = {F ⊂ E : |F| = 2α}. The idea in thisparagraph is almost the same as the construction of the robust network coding in [6, Sect. VI]. Recall that BtF is the setof global encoding vectors on edge disjoint paths to a sink twith an edge set F of errors. Execute Jaggi et al.’s algorithm
keeping BtF linearly independent for all t ∈ T and all F ∈ F .
Then every sink t can decode the original information withthe knowledge of the edge set F on which errors actuallyoccur. As in [6, Sect. VI], 
|E|q > |T | · |F | = |T |2αguarantees the successful execution of the algorithm.
We present a pseudo programming code of the proposed algorithm in Fig. 2. In order to present a detailed
description, we introduce new notations. G F = (VF , E F )denotes the network with added imaginary nodes and edgesin Steps 1 and 2 with the error pattern F ⊂ E. Let f t,F be thet,F(e) denoteflow established in Steps 3a and 3b in G F . Let f←
the set of predecessor edges of the edge e in a flow path in
f t,F . Let T F (e) denote the set of sinks using e in some flowt(e) | t ∈ T (e)}.
f t,F and let PF (e) = { f←

MATSUMOTO: OPTIMAL NETWORK ERROR-CORRECTING CODES

1733

We shall analyze the time complexity of the proposed
algorithm in Fig. 2. As in [6] we assume that any arithmetic
in the finite field is O(1) regardless of the field size. First we
analyze that of the initialization part. Observe that |E F | =|E| + k + 2|F| = |E| + k + 4α because each edge in F adds twoedges to E and there are k edges from s to s. The most time
consuming part in the initialization is construction of edge
disjoint paths, whose overall time complexity is O((|E| + k +4α)|F ||T |(k + 2α)).
Next we analyze the time complexity of the main
loop. By [6, Proof of Lemma 8], the time complexity ofchoosing the local encoding vector me (p) in Step (**) isO((|F ||T |)2 (k + 2α)), which is the most time consuming partin the main loop. Choice of me (p) is executed for |E| edges
starting from a real node in V. Thus, the time complexity ofthe main loop is O(|E|(|F ||T |)2 (k + 2α)), and the overall timecomplexity isO(|F ||T |(k + 2α)[|E| + k + 4α + |F ||T |]). Notethat |F | = |E|
2α .
A sink decodes the information by exhaustive search.
Specifically the sink enumerates all the possible information and all the possible errors for all F ∈ F , then compares the resulting symbols on incoming edges with theactual received symbols by the sink. The computation of
the resulting symbols can be done by a matrix multiplication in O((k + α)2 ) time complexity. The number of possible information
is qk and the number of possible errors isα |E|j
j=0 j (q − 1) . Thus, the time complexity of decoding by 
a sink is O(qk αj=0 |E|j (q − 1) j (k + α)2 ).
4.

Variants of the Proposed Method and Its Relation to
the Robust Network Coding

We shall introduce two variants of the proposed method inthis section.
4.1 Attaining the Refined Singleton Bound
Network error-correcting codes constructed by the proposed
method attains the Singleton bound (Proposition 1), while
they do not necessarily attains the refined Singleton bound(Proposition 2). Yang et al. [11] concurrently proposed a
construction algorithm that produces a code attaining therefined Singleton bound. In this subsection we modify the
proposed method so that it can produce a code attaining therefined Singleton bound.
Let nt be the min-cut from s to t, and suppose that thesource s emits k symbols within unit time interval. A sinkt can correct α errors if2α ≤ nt − k. Let Ft = {F ⊂ E :|F| = nt − k} and F = t∈T Ft . For fixed F ∈ F and t ∈ T ,we cannot garuantee that there exists k edge disjoint paths in
Step 3b. For such F, the sink t cannot decode information
with errors occered at F. We exclude BtF with such (t, F)from the algorithm. Note that if |F| ≤ nt − k then there
always exist k edge disjoint paths in Step 3b.
In order to attain the refined Singleton bound we keep
the linear independence of all bases in {BtF | t ∈ T , F ∈ F ,|F| ≤ nt − k} in Step (**) in Fig. 2. By the exactly same
argument, we see that the produced code attains the refinedSingleton bound.
By almost the same argument as Sect. 3, we see thatthe modified proposed algorithm runs in time complexity
O(|F ||T |(k + 2αmax )[|E| + k + 4αmax + |F ||T |]), where αmax =(maxt∈T nt − k)/2 . The required field size for successful
execution of the algorithm is |T | · |F |, and in this case |F |depends on the structure of the network (V, E).
On the other hand, the time complexity of constructing
local encoding vectors by the method of Yang et al. [11] is
⎞
⎛
 
t −k
 n
⎟⎟⎟
⎜⎜⎜
|E|
(q − 1) j ⎟⎟⎟⎠ ,O ⎜⎜⎜⎝|E|qkjt∈T j=0

and the required field size is nt + |E| − 2.
nt − kt∈T
The time complexity of the proposed algorithm can besmaller or larger depending on the network structure andq than Yang et al. [11]. The required field size of the proposed algorithm can also be smaller or larger depending on
the network structure. However, for the special case nt = n
for all t ∈ T , the required field size of the proposed method
is smaller than Yang et al. [11].
4.2 Completely Randomized Construction
By using the idea in the previous section, we can estimate the success probability of constructing a network errorcorrecting code by randomly choosing local encoding vectors as follows. The idea behind its proof is almost the sameas [6, Theorem 12]. Observe that the random choice of local
encoding vectors completely remove the time complexity of
selecting encoding vectors in the centralized manner at theexpense of larger required field size q.
Proposition 7: Suppose that the source s transmits k symbols within unit time interval, and let F = {F ⊂ E :|F| = 2α} be the set of edges on which errors can occur. Suppose also that local encoding vector coeﬃcients are generated at random independently and uniformly over Fq . With
this network error-correcting code, all sinks can correct errors in any edge set F ∈ F with probability at least 1 − δ if
q ≥ |E||T ||F |/δ.
Proof: First pick independent random local encoding vectors for all edges in the network simultaneously. Then pickan error pattern F ∈ F . For this F, execute Steps 1 and 2 inpage 1731 and compute the global encoding vectors bF (e)’s. For each cut in the test whether BtF ’s arebelonging to Fk+|F|qlinearly independent for all t. This test fails with probability
at most |T |/q by the proof of [6, Theorem 9] provided that
this tests succeed on all the upstream cuts and n ≥ k + 2α.
In the proposed algorithm in Fig. 2, we test linear independence of BtF ’s on |E| cuts in Step (**), which is suﬃcientIEICE TRANS. FUNDAMENTALS, VOL.E90–A, NO.9 SEPTEMBER 2007

1734
Table 1 Comparison among the proposed methods and [5], [11]. We assumed that the min-cut is n
for all t ∈ T and k = n − 2α. I denotes the maximum of in-degrees of nodes.
delay

Figure 2

none

Sect. 4.2

none

Paper [11]none

required field size for the success probability of code construction to be ≥ 1 − δ |T | |E|
2α |E||T | |E|
2α /δ
n+|E|−2
|T | 2αPaper [5]large

not explicitly estimatedto garuantee the decodability of the information by every
sink. By the same reason, for each sink to be able to correct errors in F, one needs to consider linear independence
only on at most |E| such cuts with random choice of local
encoding vectors. By the union bound, the probability thatthe the independence tests fails for any of |T | sinks in anyof the |E| cuts in any of the |F | error patters is at most δ if
q ≥ |E||T ||F |/δ.

Jaggi et al. [5] do not provide an explicit estimate on
the relation between the success probability of their algorithm and the field size q. Their method [5] uses coding
among diﬀerent time intervals and thus introduces delays
while our methods do not introduce extra delay. In addition to this, α-error correcting codes by constructed by the
proposed methods allow sinks to correct less than α errors,
while the method in [5] does not. The advantage of themethod in [5] over the proposed methods in this paper isthat their method allows eﬃcient decoding of informationby every sink, while our proposed methods require exhaustive search of transmitted information.
We summarize the comparison among the proposed algorithms and [5], [11] in Table 1.
4.3 Relation to the Robust Network Coding
We clarify the diﬀerence between the robust network codingin [7, Sect. V],[6, Sect. VI] and the network error-correcting
codes with known locations of errors [12]. A network error
correcting codes that can correct errors on a known locations
F ⊂ E is a robust network coding tolerating edge failures on
F. However, the converse is not always true. Consider the
network consists of three nodes {s, t, v} with two directededges from s to v and one directed edge from v to t. The
source is s and the sink is t. The intermediate node v sends tot the sum of two inputs from s. This network coding tolerate
single edge failure between s and v but cannot correct single
error between s and v.
5.

Concluding Remarks

In this paper, we proposed an algorithm constructing network error-correcting codes attaining the Singleton bound,and clarified its relation to the robust network coding [6,Sect. VI].
There are several research problems that have not beenaddressed in this paper. Firstly, the proposed deterministic

time complexity of code construction

time complexity of decoding
by sinks

 
|E|O( |E|
2α |T |(k + 2α)[|E| + k + 4α + 2α |T |])α |E|j2
j=0 j (q − 1) (k + α) )|E|O(qk αj=0 j (q − 1) j (k + α)2 )  O(qk αj=0 |E|j (q − 1) j (k + α)2 )

O(I)

O(I)
O(|E||T |qk2α |E|
j
j=0 j (q − 1) )O(qkO((n × delay)3 )|E|
algorithm requires tests of linear independence against 2α
sets consisting of k + mtF vectors, which is really time consuming. It is desirable to have a more eﬃcient deterministic
construction algorithm.
Secondly, since there seems no structure in the constructed code, the decoding of the original information at asink t requires the exhaustive search by t for possible information from the source and possible errors. It is desirable tohave a code with structure that allows eﬃcient decoding.
Finally, the case |T | = 1 and |E| = n includes the ordinary error correcting codes as a special case. Substitutingn,|T | = 1, |E| = n and 2α = n − k into Eq. (1) gives q > n−kwhich can be regarded as a suﬃcient condition for the existence of the MDS linear code. On the other hand, a wellknown suﬃcient condition for the existence of the MDS linear code is q > n − 2, which suggests that Eq. (1) is loose
and that there is a room for improvement in Eq. (1).
Acknowledgment
The author thanks for constructive criticisms by reviewersthat improved the presentation of the results very much. He
also thanks Dr. Masazumi Kurihara for pointing out ambiguity in the earlier manuscript. He would like to thankProf. Kaoru Kurosawa for drawing his attention to the network error correction, Prof. Raymond Yeung, Prof. Olav
Geil, Prof. Toshiya Itoh, Prof. Tomohiko Uyematsu, Mr.
Akisato Kimura, and Dr. Shigeaki Kuzuoka for helpful comments and discussions. He also would like to thank Dr.
Sidharth Jaggi and Mr. Allen Min Tan for informing the papers [5], [11]. Part of this research was conducted during theauthor’s stay in the Department of Mathematical Sciences,
Aalborg University.
References[1] R. Ahlswede, N. Cai, S.Y.R. Li, and R.W. Yeung, “Network information flow,” IEEE Trans. Inf. Theory, vol.46, no.4, pp.1204–1206,
July 2000.
[2] N. Cai and R.W. Yeung, “Network error correction, part II: Lowerbounds,” Communications in Information and Systems, vol.6, no.1,
pp.37–54, 2006.
[3] K. Harada and H. Yamamoto, “Strongly secure network coding
schemes with a ramp threshold,” Proc. SITA 2005, vol.2, pp.741–
744, Okinawa, Japan, Nov. 2005.
[4] S. Jaggi, M. Langberb, T. Ho, and M. Eﬀros, “Correction of adversarial errors in networks,” Proc. ISIT 2005, pp.1455–1459, Adelaide, Australia, Sept. 2005.

MATSUMOTO: OPTIMAL NETWORK ERROR-CORRECTING CODES

1735[5] S. Jaggi, M. Langberg, S. Katti, T. Ho, D. Katabi, and M. Médard,“Resilient network coding in the presence of Byzantine adversaries,”
Proc. INFOCOMM 2007, pp.616–624, Anchorage, Alaska, USA,May 2007.
[6] S. Jaggi, P. Sanders, P.A. Chou, M. Eﬀros, S. Egner, K. Jain, and
L.M.G.M. Tolhuizen, “Polynomial time algorithms for multicast
network code construction,” IEEE Trans. Inf. Theory, vol.51, no.6,
pp.1973–1982, June 2005.
[7] R. Koetter and M. Médard, “An algebraic approach to network coding,” IEEE/ACM Trans. Netw., vol.11, no.5, pp.782–795, Oct. 2003.
[8] M. Kurihara, “On some robust and secure transformations for linear
network coding,” IEICE Technical Report, IT2006-41, July 2006.
[9] S. Lang, Linear Algebra, 3rd ed., Undergraduate Texts in Mathematics, Springer-Verlag, New York, USA, 1987.
[10] S.Y.R. Li, R.W. Yeung, and N. Cai, “Linear network coding,” IEEE
Trans. Inf. Theory, vol.49, no.2, pp.371–381, Feb. 2003.
[11] S. Yang, C.K. Ngai, and R.W. Yeung, “Construction of linear network codes that achieve a refined Singleton bound,” Proc. ISIT 2007,
pp.1576–1580, Nice, France, June 2007.
[12] S. Yang and R.W. Yeung, “Characterizations of network error
correction/detection and erasure correction,” Proc. NetCod 2007,
UCSD, San Diego, California, USA, Jan. 2007, available fromhttp://code.ucsd.edu/netcod07/[13] R.W. Yeung and N. Cai, “Network error correction, part I: Basicconcepts and upper bounds,” Communications in Information and
Systems, vol.6, no.1, pp.19–36, 2006.
[14] Z. Zhang, “Network error correction coding in packetized networks,” Proc. ITW’06, Chengdu, China, pp.433–437, Oct. 2006.

Ryutaroh Matsumoto
was born in Nagoya,Japan, on November 29, 1973. He received the
B.E. degree in computer science, the M.E. degree in information processing, and the Ph.D.
degree in electrical and electronic engineering,
all from Tokyo Institute of Technology, Japan,
in 1996, 1998, 2001, respectively. He was an
Assistant Professor from 2001 to 2004, and has
been an Associate Professor since 2004 in the
Department of Communications and Integrated
Systems of Tokyo Institute of Technology. His
research interest includes error-correcting codes, quantum information theory, and communication theory. Dr. Matsumoto received the Young Engineer Award and the Excellent Paper Award from IEICE as well as theEricsson Young Scientist Award from Ericsson Japan in 2001.