Multishot Codes for Network Coding using Rank-Metric Codes

A. Error Model

• The channel model treats the transfer matrix and additive error matrix as unknown, with ρ bounding rank deficiency and τ bounding injected error packets.The number of source and sink packets is set equal to N throughout the work.Source: §I · p. 1, A. Error Model · pp. 1–2

I. INTRODUCTION

• Multishot codes use n consecutive channel uses and were reported to correct more errors than one-shot codes, motivating this work.A multishot code is a non-empty subset of n-tuples of matrices.Source: §I · p. 1
• The proposed construction combines the rank-metric approach of Silva et al. with multilevel coding to obtain multishot network-coding codes.The authors also interpret the construction through generalized concatenated codes to adapt encoding and decoding procedures [8, Chapter 15].Source: §I · p. 1
• The paper's main contribution is to specialize multilevel coding to rank-metric space and derive coset-partition encoding and hard-decision multistage decoding.The paper also reviews background on one-shot noncoherent network coding and rank-metric codes.Source: §I · p. 1

B. Matrix Codes

• A one-shot matrix code is a non-empty set of matrices used for communication over the matrix channel.Its code rate is bounded between 0 and 1.Source: B. Matrix Codes · p. 2

C. Subspace Coding

• A one-shot matrix code is sufficient for (ρ, τ)-correction when its spanned subspace code has minimum subspace distance greater than 2(2τ + ρ).The paper notes that injection distance gives a necessary and sufficient condition, but uses subspace distance for mathematical simplicity; for constant-dimension spanned subspaces, the two distances are essentially the same.Source: C. Subspace Coding · p. 2

D. Rank-Metric Approach to Network Coding

• Silva et al. proposed a method to design one-shot matrix codes based on rank-metric codes,,, and Gabidulin had already investigated the task of finding good rank-metric codes.For every [N, K, D] linear rank-metric code over FqM, D ≤ N − K + 1; Gabidulin constructed maximum-rank-distance codes when N ≤ M [3].Source: D. Rank-Metric Approach to Network… · p. 2
• Lifting rank-metric codewords produces a matrix code with the same cardinality and subspace distance equal to twice the rank-metric code's minimum distance.The lifting uses an identity matrix and sets T = N + M.Source: D. Rank-Metric Approach to Network… · p. 2
• The described decoding method reduces a received matrix to a triplet, then decodes the rank-metric component while passing side information to the decoder.The triplet is (r, L′, E′); the reduction is described as the opposite of lifting.Source: D. Rank-Metric Approach to Network… · p. 2

III. MULTISHOT MATRIX CODES

• Multishot matrix codes are introduced for error control in noncoherent network coding.Source: §III · p. 2
• The paper's lifting definition differs from Silva et al.'s, where lifting a matrix U is the subspace spanned by [I|U].Source: §III · p. 2

A. Motivation

• When field size q and packet size T cannot be increased, multishot codes offer the number of channel uses n as another way to improve error-correcting capability.The paper gives fast-topology-changing networks, such as wireless networks, as an example where the transfer matrix does not remain the same for long.Source: A. Motivation · p. 3
• The paper frames multishot coding as spreading redundancy across multiple channel uses when q and T are fixed and errors occur randomly.It states that repeated use of the matrix channel is needed to approach capacity under those conditions.Source: A. Motivation · p. 3

B. Model and Definitions

• The block model uses the matrix channel n times in a row and allows adversities to be distributed in any way among the time slots.Source: B. Model and Definitions · p. 3
• An n-shot matrix code is a non-empty set of n-tuples of matrices, and it is (ρ, τ)-correcting if the transmitted tuple is unambiguous for every allowed transfer and error sequence.The code rate is the ratio of information symbols conveyed to physical symbols spent per codeword.Source: B. Model and Definitions · p. 3

C. The Extended Subspace Distance

• The section extends subspace distance to n-tuples of subspaces and states a multishot counterpart to the one-shot result.Source: C. The Extended Subspace Distance · p. 3
• A multishot code is (ρ, τ)-correcting when its extended subspace distance exceeds 2(2ρ + τ).Source: C. The Extended Subspace Distance · p. 3
• A minimum extended-subspace-distance decoder is guaranteed to recover the transmitted subspace sequence when ρ + 2τ < dS(⟨X⟩)/2.Source: C. The Extended Subspace Distance · p. 3

D. Multishot Rank-Metric Codes

• Componentwise lifting preserves code cardinality and makes the lifted minimum subspace distance twice the multishot rank distance.Source: D. Multishot Rank-Metric Codes · p. 3

• An m-level partition refines the set through nested partitions represented by a tree, with each required nested level having the same number of children per node.The construction also defines an intrasubset distance for each level.Source: §IV · p. 4
• Classical Hamming-metric component codes protect each level, with their minimum distances specified for the construction.Source: §IV · p. 4
• Rows of an array are component-code codewords, and each column selects a tree path that determines a codeword of the constructed block code.When all leaves are singletons, each array yields exactly one codeword, as represented by Figure 1.Source: §IV · p. 4, Figure 1 · p. 4
• The construction specifies the resulting code's cardinality and lower-bounds its minimum extended distance.Source: §IV · p. 4

• The construction targets multishot rank-metric codes that can be lifted into multishot block matrix codes with T = N + M.Source: §V · p. 4
• It specializes the general multilevel construction to the rank-metric space F_q^{N×M}, using a q^M-ary [N, K, D] linear rank-metric code as its finite subset.Source: §V · p. 4
• Coset partitioning supplies the multilevel partition of the selected rank-metric code.Source: §V · p. 4

A. Coset Partitioning

• The m-level partition groups codewords into cosets of nested subcodes, with the whole code at level 0 and singletons at level m.The partition also assigns minimum intrasubset distances to its levels.Source: A. Coset Partitioning · pp. 4–5

B. Generalized Concatenation and Encoding Procedure

• The special-case construction yields a multishot rank-metric code with minimum distance d and a cardinality given by the construction.The supplied passages do not include the cardinality expression.Source: B. Generalized Concatenation and… · p. 5
• The partition and suitable Hamming-metric component codes combine to form a multishot rank-metric code.The generalized-concatenated-code connection is used because the general multilevel construction does not itself specify efficient encoding or decoding.Source: B. Generalized Concatenation and… · p. 5
• Encoding maps component-code symbols to messages for coset codes [R_i/R_i+1], then combines their codewords to produce each output coordinate.The coset codes are the inner codes, while the Hamming-metric component codes are the outer codes.Source: B. Generalized Concatenation and… · p. 5

C. A Special Situation

• Under the stated conditions, the construction yields a multishot rank-metric code with minimum distance d and the cardinality specified by the construction.The rank-metric codes must be maximum rank distance, and the component codes must be maximum-distance-separable.Source: C. A Special Situation · p. 5
• Gabidulin codes meet the maximum-rank-distance condition whenever N ≤ M, and Reed–Solomon codes can meet the component-code condition when n < q^M.The latter condition is described as typically true.Source: C. A Special Situation · p. 5
• Maximizing the constructed code's cardinality over K gives an upper bound on the size of codes produced by the proposed method.Source: C. A Special Situation · p. 5

D. Hard-Decision Multistage Decoding

• The proposed hard-decision multistage decoder is sub-optimal and is specified for the case where all R_i are Gabidulin codes.Source: D. Hard-Decision Multistage Decoding · p. 6
• Decoding first reduces the received sequence, then repeats the stage procedure m times.At each stage, inner decoding uses the generalized method of Silva et al. to find a coset codeword and its message.Source: D. Hard-Decision Multistage Decoding · p. 6
• Outer decoding maps the possibly erroneous inner-decoder output to the closest Hamming-distance codeword before the next stage.The decoded outer codeword is used to reconstruct the next-stage input.Source: D. Hard-Decision Multistage Decoding · p. 6

VI. CONCLUSION

• The paper presents a more explicit multilevel construction of multishot network-coding codes than the construction in.Source: §VI · p. 6
• Assessing the proposed codes requires comparing their size with known bounds or previous one-shot constructions.Source: §VI · p. 6
• Adapting soft-decision multistage decoding to rank distance remains open, with rank-metric list decoding identified as a possible opportunity.Source: §VI · p. 6