content_image/421805.jpg content_image/421801.jpg content_image/421804.jpg content_image/421814.jpg content_image/421799.jpg content_image/421800.jpg content_image/421806.jpg
where ρ and τ are integer parameters. While ρ upper bounds the collective effect of unfortunate choices of linear com- bination coefficients for the network code, wrong min-cut estimation, and packet erasures, τ measures the maximum number of error packets injected into the network. 

## B. Matrix Codes 

To fulfill an error-free communication over the matrix channel defined by (1) even under the adversities described in (2), matrix codes are employed. A (one-shot) matrix code X is a non-empty subset of F N × T q . Its code rate is given by 

with 0 ≤ R ( X ) ≤ 1 . 

Let X be any codeword of a matrix code X ⊆ F N × T q and Y be the corresponding channel output according to (1). A code X is said to be ( ρ, τ ) -correcting if $^{X}$can be unambigu- ously determined from Y for all choices of A and Z subject to (2). 

## C. Subspace Coding 

In [2], Silva et al. obtained a sufficient condition for the success of one-shot matrix codes under the presumed error model. Their result asserts that a one-shot matrix code X is ( ρ, τ ) - correcting if d$_{S}$ ( 〈X 〉 ) > 2(2 τ + ρ ) . In this inequality, 

(where 〈 X 〉 stands for the vector subspace spanned by the rows of matrix $^{X}$) is the subspace code obtained from X , while d$_{S}$ ( 〈X 〉 ) is the minimum subspace distance of 〈X 〉 . The subspace distance between two subspaces U and V is defined as 

where U ∔ V is the sum subspace and U ∩ V is the intersection subspace. This result reinforces the idea of transmission via subspace selection (i.e., subspace coding), as proposed in [1]. 

We note that in [9], Silva and Kschischang obtained a necessary and sufficient condition for a matrix code X to be ( ρ, τ ) -correcting, namely, d$_{I}$ ( 〈X 〉 ) > 2 τ + ρ , where d$_{I}$ ( · , · ) is called the injection distance . Nevertheless, we still stick to the subspace distance for mathematical simplicity. Moreover, the proposed multilevel construction gives rise to a multishot matrix code with constant-dimension spanned subspaces, in which case the injection distance and the subspace distance are essentially the same. 

## D. Rank-Metric Approach to Network Coding 

In [2], Silva et al. proposed a method to design one-shot matrix codes based on rank-metric codes [3], [4]. A rank- metric code is a block code R ⊆ F N q M in which the metric of concern is the rank distance (as opposed to the Hamming distance). The rank distance between u , v ∈ F N q M is defined as 

<img src='content_image/421805.jpg'>

<img src='content_image/421801.jpg'>

<img src='content_image/421804.jpg'>

<img src='content_image/421814.jpg'>

where u ∈ F N × M q is the matrix whose rows are the M -tuples representing each of the elements of u ∈ F N q M according to some fixed basis for F$_{q}$ M over F$_{q}$ ; the rank distance is indeed a metric [3]. A matrix code X ⊆ F N × T q can be obtained from a rank-metric code R ⊆ F N q M by means of a simple operation called lifting , denoted by I ( · ) and defined by 2 

where I is the N × N identity matrix and T = N + M . 

The significance of the lifting operation resides in the fact that, for u , v ∈ F N q M , 

Thus, if R ⊆ F N q M is a rank-metric code then X = I ( R ) ⊆ F N × T q (obtained by lifting each codeword of R ) gives rise to a matrix code X with |X | = |R| and d$_{S}$ ( 〈X 〉 ) = 2 d$_{R}$ ( R ) [2]. 

The problem of obtaining good one-shot codes for net- work coding could then be reduced to finding good rank- metric codes. But that latter task was already investigated by Gabidulin [3]. He first proved that the Singleton bound is als o valid for rank-metric codes, that is, for every [ N, K, D ] linear rank-metric code over F$_{q}$ M the condition D ≤ N − K + 1 must hold; he called codes achieving this bound “maximum rank distance codes.” Then he constructed a family of max- imum rank distance codes, provided N ≤ M . Even more, Gabidulin described encoding and decoding algorithms for his constructed codes, mainly based on the Reed-Solomon coding theory [8, Chapter 7]. 

Again in [2], Silva et al. adapted Gabidulin’s decoding algorithm for the matrix channel (1). In other words, a method is proposed to solve the following problem: given a received matrix Y ∈ F T × M q and a Gabidulin code R ⊆ F N q M , find ˆ u ∈ R such that 

where X = I ( u ) . The first step of the method is to decompose matrix Y into a triplet ( r , L $^{′}$, E $^{′}$) ∈ F N q M × F N × µ q × F δ × M q , operation therein called reduction (which can be interpreted as the opposite of lifting). Decoding then proceeds similarly to standard Gabidulin decoding of r for code R , except that side information L ′ and E ′ is passed to the decoder. For more details (such as the meanings of matrices L ′ and E $^{′}$) we refer the reader to [2]. 

We finally introduce multishot matrix codes for error contro l in noncoherent network coding. 

<img src='content_image/421799.jpg'>

<img src='content_image/421800.jpg'>

<img src='content_image/421806.jpg'>

## III. MULTISHOT MATRIX CODES 

