Linear network coding | EPFL Graph Search

Are you an EPFL student looking for a semester project?

Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.

In computer networking, linear network coding is a program in which intermediate nodes transmit data from source nodes to sink nodes by means of linear combinations. Linear network coding may be used to improve a network's throughput, efficiency, and scalability, as well as reducing attacks and eavesdropping. The nodes of a network take several packets and combine for transmission. This process may be used to attain the maximum possible information flow in a network. It has been proven that, theoretically, linear coding is enough to achieve the upper bound in multicast problems with one source. However linear coding is not sufficient in general; even for more general versions of linearity such as convolutional coding and filter-bank coding. Finding optimal coding solutions for general network problems with arbitrary demands is a hard problem, which can be NP-hard and even undecidable. In a linear network coding problem, a group of nodes are involved in moving the data from source nodes to sink nodes. Each node generates new packets which are linear combinations of past received packets by multiplying them by coefficients chosen from a finite field, typically of size . More formally, each node, with indegree, , generates a message from the linear combination of received messages by the formula: Where the values are coefficients selected from . Since operations are computed in a finite field, the generated message is of the same length as the original messages. Each node forwards the computed value along with the coefficients, , used in the level, . Sink nodes receive these network coded messages, and collect them in a matrix. The original messages can be recovered by performing Gaussian elimination on the matrix. In reduced row echelon form, decoded packets correspond to the rows of the form A network is represented by a directed graph . is the set of nodes or vertices, is the set of directed links (or edges), and gives the capacity of each link of . Let be the maximum possible throughput from node to node .

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related publications (72)

Related people (16)

Related units (2)

Related concepts (2)

Related courses (1)

Related lectures (24)

COM-102: Advanced information, computation, communication II

Text, sound, and images are examples of information sources stored in our computers and/or communicated over the Internet. How do we measure, compress, and protect the informatin they contain?

MicroCast: Cooperative Video Streaming Using Cellular and Local Connections

Christina Fragouli, Lorenzo Keller

We consider a group of mobile users, within proximity of each other, who are interested in watching the same online video. The common practice today is that each user downloads the video independently

Ieee-Inst Electrical Electronics Engineers Inc2016

Efficient Algorithms for the Data Exchange Problem

Michael Christoph Gastpar, Sameer Pawar

In this paper, we study the data exchange problem, where a set of users is interested in gaining access to a common file, but where each has only partial knowledge about it as side-information. Assumi

Institute of Electrical and Electronics Engineers2016

Bringing physical layer cooperation closer to practical wireless systems

Emre Atsan

Nowadays the demand for communication over the wireless medium is significantly increasing, while the available wireless spectrum is already limited. In this thesis, we introduce new practical physica

EPFL2015

Introduces network coding, explaining its benefits, implications, and practical applications in networking systems.

Explains Reed-Solomon error-correcting codes and their unique decoding property over finite fields.

Discusses linear codes' dimension and Hamming weight with examples and theorems.

In computing, telecommunication, information theory, and coding theory, forward error correction (FEC) or channel coding is a technique used for controlling errors in data transmission over unreliable or noisy communication channels. The central idea is that the sender encodes the message in a redundant way, most often by using an error correction code or error correcting code (ECC). The redundancy allows the receiver not only to detect errors that may occur anywhere in the message, but often to correct a limited number of errors.