Silas L. Fong, Raymond W. Yeung · 2013
We introduce variable-rate linear network coding for single-source finite acyclic network. In this problem, the source of a network transmits messages at different rates in different time sessions and every non-source node in the network decodes the messages if possible. We propose two efficient algorithms for implementing variable-rate linear network coding under different circumstances. Index Terms Network coding, variable-rate, linear broadcast, static network codes.
Cited by 0
2008
A free cipher? Abstract — We consider the level of information security provided by random linear network coding in network scenarios in which all nodes comply with the communication protocols yet are assumed to be potential eavesdroppers (i.e. “nice but curious”). For this setup, which differs from wiretapping scenarios considered previously, we develop a natural algebraic security criterion, and prove several of its key properties. A preliminary analysis of the impact of network topology on the overall network coding security, in particular for complete directed acyclic graphs, is also included. Index Terms — security, information theory, graph theory, network coding.
Cited by 0
Sidharth Jaggi, Michelle Effros, T. Ho et al. · 2004
Many recent papers study methods, bounds and limitations for linear network coding. We examine prior definitions of linearity in network coding and show their implications in terms of code design and performance. We demonstrate how codes with one notion of linearity can be used to build, in a distributed manner, codes with another notion of linearity. One such reduction provides a simple construction for convolutional multicast network codes. We also provide examples of networks for which convolutional network code design is significantly less complex than for any block code. Finally, we introduce the new class of filter-bank network codes of which all previous definitions of linear network codes are special cases. This work is motivated by discussions with Dr. Ralf Koetter.
Cited by 34
Zihuai Lin · 2022
Cited by 0
Moshe Schwartz, Muriel Médard · arXiv (Cornell University) · 2014
We present a heuristic for designing vector non-linear network codes for non-multicast networks, which we call quasi-linear network codes. The method presented has two phases: finding an approximate linear network code over the reals, and then quantizing it to a vector non-linear network code using a fixed-point representation. Apart from describing the method, we draw some links between some network parameters and the rate of the resulting code.
Cited by 2Open access
Vijayvaradharaj T. Muralidharan, B. Sundar Rajan · NOT FOUND REPOSITORY (Indian Institute of Science Bangalore) · 2013
Discrete polymatroids are the multi-set analogue of matroids. In this paper, we explore the connections among linear network coding, linear index coding and representable discrete polymatroids. We consider vector linear solutions of networks over a field $\mathbb{F}_q,$ with possibly different message and edge vector dimensions, which are referred to as linear fractional solutions. We define a \textit{discrete polymatroidal} network and show that a linear fractional solution over a field $\mathbb{F}_q,$ exists for a network if and only if the network is discrete polymatroidal with respect to a discrete polymatroid representable over $\mathbb{F}_q.$ An algorithm to construct networks starting from certain class of discrete polymatroids is provided. Every representation over $\mathbb{F}_q$ for the discrete polymatroid, results in a linear fractional solution over $\mathbb{F}_q$ for the constructed network. Next, we consider the index coding problem and show that a linear solution to an index coding problem exists if and only if there exists a representable discrete polymatroid satisfying certain conditions which are determined by the index coding problem considered. El Rouayheb et. al. showed that the problem of finding a multi-linear representation for a matroid can be reduced to finding a \textit{perfect linear index coding solution} for an index coding problem obtained from that matroid. We generalize the result of El Rouayheb et. al. by showing that the problem of finding a representation for a discrete polymatroid can be reduced to finding a perfect linear index coding solution for an index coding problem obtained from that discrete polymatroid.
Cited by 5Open access
Sidharth Jaggi Michelle Effros, Tracey C. Ho · 2008
Abstract Many recent papers study methods, bounds and limitations for linear network coding. Weexamine prior definitions of linearity in network coding and show their implications in terms of code design and performance. We demonstrate how codes with one notion of linearity canbe used to build, in a distributed manner, codes with another notion of linearity. One such reduction provides a simple construction for convolutional multicast network codes. We alsoprovide examples of networks for which convolutional network code design is significantly less complex than for any block code. Finally, we introduce the new class of filter-bank networkcodes of which all previous definitions of linear network codes are special cases. This work is motivated by discussions with Dr. Ralf Koetter.
Cited by 0
Ben Grinboim, Itay Shrem, Ofer Amrani · arXiv (Cornell University) · 2022
Increasing network utilization is often considered as the holy grail of communications. In this article, the concept of sub-rate coding and decoding in the framework of linear network coding (LNC) is discussed for single-source multiple-sinks finite acyclic networks. Sub-rate coding offers an add-on to existing LNC. It allows sinks whose max-flow is smaller than the source message-rate, termed \emph{sub-rate sinks}, to decode a portion of the transmitted message without degrading the maximum achievable rate of LNC sinks whose max-flow is equal (or greater) than the rate of the source node. The article studies theoretical aspects of sub-rate coding by formulating the conditions a node (and indeed the network) must fulfill so as to qualify as a legitimate sub-rate sink.
Cited by 0Open access
Pereira-Castillo, R.J. · EngagedScholarship @ Cleveland State University (Cleveland State University) · 2019
Network coding is a widely studied theoretical networking scheme with the potential for improving digital communications. The scheme allows a network node to combine information from multiple edges onto a single edge. Message symbols are represented as elements in a finite field of the form 2n. In a broadcast scenario, network coding achieves information transmission rates at the network's mincut max-flow bound. This potential for improving network efficiency has motivated researchers to consider the practical implications of the scheme.
Cited by 0
CUHK Digital Repository (Chinese University of Hong Kong) · 2007
Cited by 0
Silas L. Fong, Raymond W. Yeung · 2006
Ahlswede et al., (2000) established that if coding is applied to nodes in a network, rather than routing alone, the network capacity can be improved. Li et al., (2003) proved that linear network coding is sufficient to achieve the maximum capacity in a single-source finite acyclic network. In this paper, we study variable-rate linear network coding and propose a scheme for efficient implementation
Cited by 10
Ben Grinboim, Itay Shrem, Ofer Amrani · Computer Communications · 2023
Increasing network capacity is undoubtedly a critical aspect of modern communication systems . In this paper, the concept of sub-rate coding and decoding in the framework of linear network coding (LNC) is introduced for single-source multiple-sinks finite acyclic networks. This methodology offers a modification to existing LNC so that the source transmits its messages in a manner in which a given set of sinks (termed sub-rate sinks), whose max-flow is smaller than the source’s message-rate, can still decode a portion of the transmitted messages, without degrading the maximum achievable rate of LNC sinks whose max-flow is equal (or greater) than the source rate. The paper sets the conditions which a set of sub-rate sinks has to satisfy in order for that methodology to be applicable.
Cited by 0Open access
Tang, Hanqi, Sun, Qifu Tyler, Li, Zongpeng et al. · arXiv (Cornell University) · 2017
We study a class of linear network coding (LNC) schemes, called circular-shift LNC, whose encoding operations consist of only circular-shifts and bit-wise additions (XOR). Formulated as a special vector linear code over GF($2$), an $L$-dimensional circular-shift linear code of degree $δ$ restricts its local encoding kernels to be the summation of at most $δ$ cyclic permutation matrices of size $L$. We show that on a general network, for a certain block length $L$, every scalar linear solution over GF($2^{L-1}$) can induce an $L$-dimensional circular-shift linear solution with 1-bit redundancy per-edge transmission. Consequently, specific to a multicast network, such a circular-shift linear solution of an arbitrary degree $δ$ can be efficiently constructed, which has an interesting complexity tradeoff between encoding and decoding with different choices of $δ$. By further proving that circular-shift LNC is insufficient to achieve the exact capacity of certain multicast networks, we show the optimality of the efficiently constructed circular-shift linear solution in the sense that its 1-bit redundancy is inevitable. Finally, both theoretical and numerical analysis imply that with increasing $L$, a randomly constructed circular-shift linear code has linear solvability behavior comparable to a randomly constructed permutation-based linear code, but has shorter overheads.
Cited by 0Open access
Kenji Harada, H. Yamamoto · IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences · 2008
In a network with capacity h for multicast, information Xh=(X1, X2, …, Xh) can be transmitted from a source node to sink nodes without error by a linear network code. Furthermore, secret information Sr=(S1, S2, …, Sr) can be transmitted securely against wiretappers by k-secure network coding for k≤h-r. In this case, no information of the secret leaks out even if an adversary wiretaps k edges, i. e. channels. However, if an adversary wiretaps k+1 edges, some Si may leak out explicitly. In this paper, we propose strongly k-secure network coding based on strongly secure ramp secret sharing schemes. In this coding, no information leaks out for every (Si1, Si2, …,Sir-j) even if an adversary wiretaps k+j channels. We also give an algorithm to construct a strongly k-secure network code directly and a transform to convert a nonsecure network code to a strongly k-secure network code. Furthermore, some sufficient conditions of alphabet size to realize the strongly k-secure network coding are derived for the case of k<h-r.
Cited by 56
Vijayvaradharaj T. Muralidharan, B. Sundar Rajan · arXiv (Cornell University) · 2013
Discrete polymatroids are the multi-set analogue of matroids. In this paper,\nwe explore the connections among linear network coding, linear index coding and\nrepresentable discrete polymatroids. We consider vector linear solutions of\nnetworks over a field $\\mathbb{F}_q,$ with possibly different message and edge\nvector dimensions, which are referred to as linear fractional solutions. We\ndefine a \\textit{discrete polymatroidal} network and show that a linear\nfractional solution over a field $\\mathbb{F}_q,$ exists for a network if and\nonly if the network is discrete polymatroidal with respect to a discrete\npolymatroid representable over $\\mathbb{F}_q.$ An algorithm to construct\nnetworks starting from certain class of discrete polymatroids is provided.\nEvery representation over $\\mathbb{F}_q$ for the discrete polymatroid, results\nin a linear fractional solution over $\\mathbb{F}_q$ for the constructed\nnetwork. Next, we consider the index coding problem and show that a linear\nsolution to an index coding problem exists if and only if there exists a\nrepresentable discrete polymatroid satisfying certain conditions which are\ndetermined by the index coding problem considered. El Rouayheb et. al. showed\nthat the problem of finding a multi-linear representation for a matroid can be\nreduced to finding a \\textit{perfect linear index coding solution} for an index\ncoding problem obtained from that matroid. We generalize the result of El\nRouayheb et. al. by showing that the problem of finding a representation for a\ndiscrete polymatroid can be reduced to finding a perfect linear index coding\nsolution for an index coding problem obtained from that discrete polymatroid.\n
Cited by 3Open access
Xuan Guang, Raymond W. Yeung · 2020
We consider linear network error correction (LNEC) coding when errors may occur on the edges of a communication network of which the topology is known. In this paper, we first revisit and explore the framework of LNEC coding, and then unify two well-known LNEC coding approaches. In LNEC coding, LNEC maximum distance separable (MDS) codes are a type of most important optimal codes. However, the minimum required field size for the existence of LNEC MDS codes is an open problem not only of theoretical interest but also of practical importance, because it is closely related to the implementation of such coding schemes in terms of computational complexity and storage requirement. In this paper, we obtain an improved lower bound on the required field size by developing a graph-theoretic approach. The improvement over the existing results is in general significant. Furthermore, by applying the graph-theoretic approach to the framework of LNEC coding, we obtain a significantly enhanced characterization of the capability of an LNEC code in terms of its minimum distance.
Cited by 5
Yang Bai, Xuan Guang, Raymond W. Yeung · Entropy · 2023
In this paper, we put forward the model of multiple linear-combination security multicast network coding, where the wiretapper desires to obtain some information about a predefined set of multiple linear combinations of the source symbols by eavesdropping any one (but not more than one) channel subset up to a certain size <i>r</i>, referred to as the <i>security level</i>. For this model, the security capacity is defined as the maximum average number of source symbols that can be securely multicast to all sink nodes for one use of the network under the linear-combination security constraint. For any security level and any linear-combination security constraint, we fully characterize the security capacity in terms of the ratio of the rank of the linear-combination security constraint to the number of source symbols. Also, we develop a general construction of linear security network codes. Finally, we investigate the asymptotic behavior of the security capacity for a sequence of linear-combination security models and discuss the asymptotic optimality of our code construction.
Cited by 2Open access
Joseph Connelly · eScholarship (California Digital Library) · 2018
As connected devices play an ever-growing role in our society, there is a subsequent need for advances in multi-user communication systems. In a network, senders and receivers are connected via a series of intermediate users who share information represented as sequences of bits or elements of some other finite alphabet. By allowing users to transmit functions of their inputs, as opposed to simply relaying received data, the information throughput of a network can be increased. Network codes in which these functions are linear are sub-optimal in general but are of practical interest due to their mathematical tractability and low implementation complexity. The study of linear network coding has primarily been limited to finite field alphabets. In this work, we consider linear network codes over more general algebraically-structured alphabets, namely finite rings. We contrast linear network codes over finite fields, commutative rings, and non-commutative rings, and we discuss cases where non-linear codes attain higher information rates than even very general linear codes. Our results show that finite fields are, in some sense, the best ring alphabets for linear network coding, but in certain instances, it may be advantageous to use linear coding over some other ring alphabet of the same size. Specifically, we prove results related to:(i) network solvability: whether or not a network’s receivers can obtain their desired information using codes over a given alphabet. We characterize the commutative rings for which there exists a network that is linearly solvable over the ring but not over any other commutative ring of the same size. We show that these rings are, in some sense, the best commutative rings of a given size for linear network coding. We then present an infinite class of networks that are linearly solvable over certain non-commutative rings but not over any commutative rings. We also prove that vector linear codes over finite fields minimize the alphabet size needed for linear solvability, which is desirable from an implementation complexity standpoint.(ii) network capacity: how much information per channel use can be sent to the network’s receivers in the limit of large block sizes for transmission. We show that the linear coding capacity of a given network cannot be increased by looking beyond finite fields to more general rings.
Cited by 0Open access
Chunfeng Yang, Chenxi Ming, Jiaqing Huang · Advances in intelligent and soft computing · 2012
Cited by 1
Long Shi, Soung Chang Liew · IEEE Transactions on Information Theory · 2017
This paper presents the results of a comprehensive investigation of complex linear physicallayer network coding (PNC) in two-way relay channels. In this system, two nodes A and B communicate with each other via a relay R. Nodes A and B send complex symbols, wA and wB, simultaneously to relay R. Based on the simultaneously received signals, relay R computes a linear combination of the symbols, w <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">N</sub> = αw <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">A</sub> + βw <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">B</sub> , as a network-coded symbol and then broadcasts wN to nodes A and B. Node A then obtains wB from wN and its self-information wA by wB = β <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">-1</sup> (wN -αwA). Node B obtains wB in a similar way. A critical question at relay R is as follows: “given channel gain ratio η = hA/hB, where hA and hB are the complex channel gains from nodes A and B to relay R, respectively, what is the optimal coefficients (α, β) that minimizes the symbol error rate (SER) of wN = αw <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">A</sub> + βw <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">B</sub> when the relay attempts to detect wN in the presence of noise?” Our contributions with respect to this question are as follows: 1) we put forth a general Gaussian-integer formulation for complex linear PNC in which α, β, w <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">A</sub> , w <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">B</sub> , and w <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">N</sub> are the elements of a finite field of Gaussian integers, that is, the field of 7G[i]/q, where q is a Gaussian prime. Previous vector formulation, in which wA, wB, and wN were represented by 2-D vectors and α and β were represented by 2 x 2 matrices, corresponds to a subcase of our Gaussian-integer formulation, where q is real prime only. Extension to the Gaussian prime q, where q can be complex, gives us a larger set of signal constellations to achieve different rates at different values of SNR; and 2) we show how to divide the complex plane of η into different Voronoi regions, such that the η within each Voronoi region shares the same optimal PNC mapping (α <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">opt</sub> , β <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">opt</sub> ). We uncover the structure of the Voronoi regions that allows us to compute a minimum-distance metric that characterizes the SER of wN under optimal PNC mapping (α <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">opt</sub> , β <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">opt</sub> ). Overall, the contributions in 1) and 2) yield a toolset for a comprehensive understanding of complex linear PNC in 7G[i]/q. We believe investigation of linear PNC beyond 7G[i]/q can follow the same approach.
Cited by 30