WO2022118324A1 - Method and system for network coding - Google Patents

Abstract

A method of transmitting input information in a communication network from a computing source node characterized by a transmission rate to each of a plurality of computing sink nodes, comprises precoding the input information at the source node, and transmitting the precoded information over the network to provide each of the plurality of sink nodes with a respective sink input. At a sink node having a maximal rate of at least the transmission rate, the method decodes a respective sink input to extract the input information. At a sink node having a maximal rate less than the transmission rate, the method decodes a respective sink input to extract a portion of the input information.

Description

METHOD AND SYSTEM FOR NETWORK CODING

RELATED APPLICATION

This application claims the benefit of priority of U.S. Provisional Patent Application No. 63/121,276 filed on December 4, 2020, the contents of which are incorporated herein by reference in their entirety.

FIELD AND BACKGROUND OF THE INVENTION

The present invention, in some embodiments thereof, relates to a communication systems and, more particularly, but not exclusively, to a method and system for network coding.

Network coding is a technique targeting the improvement of communications within a network. Network coding increases the capacity or throughput of a communication network by mixing information received from source nodes at an intermediate node, and retransmitting the mixed information to one or more destination nodes. The content of any information flowing out of the intermediate node can be derived by the destination nodes from the information which flowed into the intermediate node.

The intermediate nodes in the network serve as computational units rather than merely relays, thus supporting increased overall network throughput. In particular, the nodes are configured to recombine several input packets into one or several output packets. At the intermediate node, some type of coding is performed on the packets present at that node, and the resulting encoded packet can be broadcast for different recipients simultaneously instead of transmitting each packet separately.

SUMMARY OF THE INVENTION

According to some embodiments of the invention the present invention there is provided a method of transmitting input information in a communication network from a computing source node characterized by a transmission rate to each of a plurality of computing sink nodes. The method comprises precoding the input information at the source node, and transmitting the precoded information over the network to provide each of the plurality of sink nodes with a respective sink input. At a sink node having a maximal rate of at least the transmission rate, the method decodes a respective sink input to extract the input information. At a sink node having a maximal rate less than the transmission rate, the method decodes a respective sink input to extract a portion of the input information. According to some embodiments of the invention the communication network employs a multicast network code.

According to some embodiments of the invention the transmission rate is constant.

According to some embodiments of the invention the transmission rate varies.

According to some embodiments of the invention the input information is represented by a vector and wherein the precoding comprises multiplying the vector by an invertible matrix.

According to some embodiments of the invention the invertible matrix is an inverse of a matrix factorized out of a global encoding matrix of the network.

According to some embodiments of the invention the method is executed for scalar network coding.

According to some embodiments of the invention the method is executed for vector network coding.

According to some embodiments of the invention the decoding of the respective sink input to extract the portion of the input information, is at a decoding rate that equals the maximal rate of the sink node.

According to some embodiments of the invention the decoding of the respective sink input to extract the portion of the input information, is at a decoding rate that is less than the maximal rate of the sink node.

According to some embodiments of the invention the method comprises, at an additional sink node having a maximal rate of at least the transmission rate, decoding a respective sink input to extract only a portion of the input information.

According to some embodiments of the invention the method comprises, at an additional node Nf having a maximal rate of at least the source's transmission rate, and which is other than a sink node and other than the source, decoding input received at the additional node Nf to extract the input information, thereby virtually attributing sink properties to the additional node Nf.

According to some embodiments of the invention the method comprises, at an additional node N_s having a maximal rate of less than the source's transmission rate, and which is other than a sink node and other than the source, decoding input received at the additional node N_s to extract a portion of the input information, thereby virtually attributing sink properties to the additional node N_s.

According to some embodiments of the invention the present invention there is provided a communication system. The system comprises: a computing source node, and a plurality of computing sink nodes deployed over an area remote from the computing source node. Each of the source node and the computing sink nodes comprises a circuit for encoding and decoding information, wherein a circuit of the computing source node is characterized by a transmission rate, and wherein the plurality of computing sink nodes comprises at least one sink node of a first type that has a circuit characterized a maximal rate of at least the source's transmission rate, and at least one sink node of a second type that has a circuit characterized a maximal rate of less than the source's transmission rate. The circuit of the computing source node is configured to precode the input information, to transmit the precoded information over the network to provide each of the plurality of sink nodes with a respective a sink input, to transmit to a sink node of the first type a control signal causing a respective circuit of the sink node to decode a respective sink input to extract the input information, and to transmit to a sink node of the second type a control signal causing a respective circuit of the sink node to decode a respective sink input to extract a portion of the input information.

According to some embodiments of the invention the system employs a multicast network code.

According to some embodiments of the invention the source's transmission rate is constant.

According to some embodiments of the invention the source's transmission rate varies.

According to some embodiments of the invention the input information is represented by a vector, and wherein the circuit of the computing source node is configured to multiply the vector by an invertible matrix. According to some embodiments of the invention the invertible matrix is an inverse of a matrix factorized out of a global encoding matrix of the network.

According to some embodiments of the invention the system employs scalar network coding.

According to some embodiments of the invention the system employs vector network coding.

According to some embodiments of the invention the circuit of the source node is configured to transmit to the sink node of the second type a control signal causing the respective circuit of the sink node to decode at a decoding rate that equals the maximal rate of the sink node.

According to some embodiments of the invention the circuit of the source node is configured to transmit to the sink node of the second type a control signal causing the respective circuit of the sink node to decode at a decoding rate that is less than the maximal rate of the sink node.

According to some embodiments of the invention the system comprises, an additional sink node having a circuit characterized by a maximal rate of at least the source's transmission rate, wherein the circuit of the source node is configured to transmit to the additional sink node a control signal causing the circuit of the additional sink node to decode a respective sink input to extract a portion of the input information.

According to some embodiments of the invention the system comprises an additional node Nf, other than a sink node and other than the source, the additional node Nf, having a circuit characterized by a maximal rate of at least the source's transmission rate, wherein the circuit of the source node is configured to transmit to the additional sink node Nf a control signal causing the circuit of the additional sink node Nf to decode input received at the additional node Nf to extract the input information, thereby virtually attributing sink properties to the additional node N_f.

According to some embodiments of the invention the system comprises an additional node N_s, other than a sink node and other than the source, the additional node N_s, having a circuit characterized by a maximal rate of less than the source's transmission rate, wherein the circuit of the source node is configured to transmit to the additional sink node N_s a control signal causing the circuit of the additional sink node N_s to decode input received at the additional node N_s to extract a portion of the input information, thereby virtually attributing sink properties to the additional node N_s.

Unless otherwise defined, all technical and/or scientific terms used herein have the same meaning as commonly understood by one of ordinary skill in the art to which the invention pertains. Although methods and materials similar or equivalent to those described herein can be used in the practice or testing of embodiments of the invention, exemplary methods and/or materials are described below. In case of conflict, the patent specification, including definitions, will control. In addition, the materials, methods, and examples are illustrative only and are not intended to be necessarily limiting.

Implementation of the method and/or system of embodiments of the invention can involve performing or completing selected tasks manually, automatically, or a combination thereof. Moreover, according to actual instrumentation and equipment of embodiments of the method and/or system of the invention, several selected tasks could be implemented by hardware, by software or by firmware or by a combination thereof using an operating system.

For example, hardware for performing selected tasks according to embodiments of the invention could be implemented as a chip or a circuit. As software, selected tasks according to embodiments of the invention could be implemented as a plurality of software instructions being executed by a computer using any suitable operating system. In an exemplary embodiment of the invention, one or more tasks according to exemplary embodiments of method and/or system as described herein are performed by a data processor, such as a computing platform for executing a plurality of instructions. Optionally, the data processor includes a volatile memory for storing instructions and/or data and/or a non-volatile storage, for example, a magnetic hard-disk and/or removable media, for storing instructions and/or data. Optionally, a network connection is provided as well. A display and/or a user input device such as a keyboard or mouse are optionally provided as well.

BRIEF DESCRIPTION OF THE SEVERAL VIEWS OF THE DRAWINGS

Some embodiments of the invention are herein described, by way of example only, with reference to the accompanying drawings. With specific reference now to the drawings in detail, it is stressed that the particulars shown are by way of example and for purposes of illustrative discussion of embodiments of the invention. In this regard, the description taken with the drawings makes apparent to those skilled in the art how embodiments of the invention may be practiced.

In the drawings:

FIGs. 1 A and IB are schematic illustration of a simple communication network known as "butterfly network";

FIGs. 2A-B are schematic illustration of butterfly network with an additional node;

FIGs. 3 A and 3B are schematic illustrations of two cases of three-plane configurations;

FIG. 4 is a graph showing a rate ratio bound as a function of a number of sinks in a communication network;

FIG. 5 is a flowchart diagram describing a method suitable for transmitting input information in a communication network; and

FIG. 6 is a schematic illustration of a communication system.

DESCRIPTION OF SPECIFIC EMBODIMENTS OF THE INVENTION

The present invention, in some embodiments thereof, relates to a communication systems and, more particularly, but not exclusively, to a method and system for network coding.

Before explaining at least one embodiment of the invention in detail, it is to be understood that the invention is not necessarily limited in its application to the details of construction and the arrangement of the components and/or methods set forth in the following description and/or illustrated in the drawings and/or the Examples. The invention is capable of other embodiments or of being practiced or carried out in various ways. Network coding has been shown to increase overall network throughput in single-source multiple-sink communications scenarios (i.e., broadcast of massages), or multi-source networks. Network coding can potentially achieve the maximum capacity to every eligible sink.

Herein, “eligible sink” refers to a sink whose achievable rate is greater or equal to the source transmission-rate.

A sink whose achievable rate is smaller than the source message-rate, is referred to herein as a "sub-rate sink."

The achievable rate of a sink is interchangeably referred to herein as the max-flow of the sink.

FIGs. 1A and IB are schematic illustration of a simple network known as "butterfly network". In the exemplified network, a source node 1 transmits two signals a and b to two sinks, 6 and 7. In FIG. 1A, the network does not employ network coding, so that the intermediate nodes 2, 3, 4, and 5, do not execute any coding-related computations. Thus, in this network, only one of the sinks (6 or 7, in the present example) can decode both messages in each network use. In FIG. IB, the network employs network coding. Intermediate node 4 can XOR (exclusive-or) both its inputs, which in turn allows both sinks 6 and 7 to decode the two transmitted messages.

In conventional techniques pertaining to network coding, sub-rate sinks have been considered ineligible, and so communication to them was avoided. This approach is derived from the classical definition of a multicast: a sink that can not receive all the information (also known as "the network rate") is considered useless.

The Inventors of the present invention found that there are cases where retrieving some of the transmitted data is valuable, for example when a sub-rate sink can benefit from reduced data resolution. In other words, the Inventors found that the ability to communicate with some network sinks in the multicast using higher rate than other sinks, allows the higher-rate sinks to retrieve the transmitted information faster than the others, and may also facilitates the use the residual capacity for conveying data that is not necessarily required by all the sinks, e.g., monitoring information.

The Inventors have therefore devised a network coding technique in which at least some of the sub-rate sinks decode a portion of the input data. An example, which is not to be considered as limiting, is schematically illustrated in FIGs. 2A and 2B. In this example, another node, 8, is added to the butterfly network. The max-flow (from the source) of node 8 is only 1. It is assumed to be beneficial to communicate with node 8 at rate of 1 symbol per network use. In conventional network coding for the butterfly network, node 8 receives a+b and hence cannot decode any symbol, as shown in FIG. 2A. The Inventors found that by properly manipulating the transmitted symbols at the source node 1, for example, as illustrated in FIG. 2B, the network is configured so that node 8 operates at a communication rate of 1 symbol per network use, without affecting the ability of the eligible sinks 6 and 7, to operate at their original rate (2 symbols per network use, in the present example).

Thus, according to some embodiments of the present invention there is provided a method of transmitting input information in a communication network from a computing source node, s, characterized by a transmission rate to each of a plurality of computing sink nodes ti, where z is a sink node index greater than one.

A flowchart diagram of the method according to various exemplary embodiments of the present invention is provided in FIG. 5. It is to be understood that, unless otherwise defined, the operations described hereinbelow can be executed either contemporaneously or sequentially in many combinations or orders of execution. Specifically, the ordering of the flowchart diagrams is not to be considered as limiting. For example, two or more operations, appearing in the following description or in the flowchart diagrams in a particular order, can be executed in a different order (e.g., a reverse order) or substantially contemporaneously. Additionally, several operations described below are optional and may not be executed.

At least part of the operations described herein can be implemented by a data processing system, which is optionally and preferably dedicated circuitry, configured for executing the operations described below. During operation, the data processing system can store in a memory data structures or values obtained by intermediate calculations and pull these data structures or values for use in subsequent operation. All these operations are well-known to those skilled in the art of computer systems.

The method of the present embodiments can be implement in any communication network having a computing source node and a plurality of computing sink nodes. Typically, but not necessarily the communication network employs a multicast network code. The communication network can employ scalar network coding, or vector network coding, as desired.

The computing source node can be, for example, a content provider, a website, a server, or the like. The transmission rate of the source node is denoted by r, and is defined as the number of symbols created by the source node at every network use. Thus, r is positive integer. In some embodiments of the present invention the source's transmission rate is constant, and in some embodiments of the present invention the source's transmission rate varies.

The input information include information symbols, and all possible information symbols that can be transmitted by the source node are collectively referred to as a base field F. The input information can be in the form of data packets (each including one or more information symbols) that are combined during transit. The input information can be mathematically represented by an input vector v ∈ F^r.

One or more of the computing sink nodes can be a consumer node (e.g., a requesting device, an end point device, etc.). The network can alternatively or additionally include a consumer which is a non-computing sink node. Multiple packets transmitted over the network from the computing source node, and optionally and preferably from one or more of the computing sink nodes, can create a new packet set (e.g., stream), where members of the new packet set are optionally and preferably linear combinations of the multiple input packets.

With reference now to FIG. 5, the method begins at 10 and continues to 1 at which the input information is precoded at the source node. The precoding is preferably executed prior to the transmission of the information. In various exemplary embodiments of the invention the precoding includes multiplying the source information v by an r X r precoding matrix P over a field F. The procedure is referred to as "precoding" since the input to the network is vP rather than v. The precoding matrix P is preferably invertible.

Generally, a network having m links can be described by an r×m matrix referred to herein as a global encoding matrix (GEM). Every column of the GEM is associated with one of the network's link, such that multiplying an input vector by this column results in the symbol that the network code conveys on that link per network input vector. In some embodiments of the present invention the invertible matrix P is an inverse of a matrix that is factorized out of the GEM. Representative examples of precoding matrices suitable according to some embodiments of the present invention for various cases, are provided in the Examples section that follows.

Based on the choice of the factorization for obtaining the precoding matrix P, the decoding performed at each computing sink is modified to take into account the precoding operation. Denoting the native decoding matrix of sink t by _t, the modification is achieved by multiplying the native decoding matrix D_t by the inverse P'¹ of the precoding matrix P. Formally, the modification can be written as: by _t → D_tP^-1.

The method continues to 12 at which the precoded information is transmitted over the network, to provide each of the sink nodes with a respective a sink input. For each sink node t_i, the method proceeds to a 13 at which the method determines the maximal rate h_ti of the respective sink node. The method optionally and preferably proceeds to decision 14 at which the method compares the determined maximal rate h_t1 to the transmission rate r of the source node s. If the determined maximal rate of the sink node is less than the source's transmission rate, the method proceeds to 15 at which the respective sink input is decoded by the sink a to extract a portion of the input information. If the determined maximal rate of the sink node is not less than the source's transmission rate, the method proceeds to 16 at which the respective sink input is decoded by the sink to extract all the input information. The sink input for each sink is decoded by multiplying the input by the modified decoding matrix as further detailed hereinabove. Generally, the rank of the modified decoding matrix is smaller for each sink node for which the maximal rate is less than the source's transmission rate, than for any each sink node for which the maximal rate is not less than the source's transmission rate. In other words, the rank of the decoding matrix that is used at 15 is smaller than the rank of the decoding matrix that is used at 16. The decoding matrix used in 16 is typically an invertible matrix. The decoding matrix used in 15 is not necessarily an invertible matrix. In some embodiments of the present invention at least one sink having a maximal rate less than the source's transmission rate decodes the sink input using a non-invertible decoding matrix.

The decoding at 15 can be at a decoding rate that equals the maximal rate h_t1of the respective sink node, or it can be at a decoding rate that is less than the maximal rate of the respective sink node.

From 15 or 16, as the case may be, the method optionally and preferably loops back to 13, for determining the maximal transmission rate of another computing sink of the network. Once the method interrogates all the computing sinks of the network, the method ends at 70.

It is to be understood that it is not necessary for more the method of the present embodiments to extract all the information by each sink node for which the method determines that the sink's maximal rate is not less than the source's transmission rate. The present embodiments also contemplate situations in which for at least one of a sink node that has a maximal rate satisfying h_t1≥ r the respective sink input is decoded to extract only portion of the input information, rather than all input information. In these embodiments, the method can, for at least one sink node that has a maximal rate satisfying h_t1≥ r, skip decision 14, or both operation 13 and decision 14, and move directly to operation 15.

The present embodiments also contemplate situations in which the method virtually attributes sink properties to one or more nodes of the network that are not sink nodes and are not other the source node. Thus, for example, in some embodiments an additional node Nf which has a maximal rate of at least the source's transmission rate r, and which is not one of the sink nodes and is not the source, is caused to decode its input to extract all the input information, thereby virtually attributing sink properties to the node Nf. Additionally of alternatively, an additional node N_s having a maximal rate of less than the source's transmission rate r, and which is not one of the sink nodes and is not the source node, is caused decode its input to extract a portion of the input information, thereby virtually attributing sink properties to additional node N_s.

FIG. 6 is a schematic illustration of a communication system 60, according to some embodiments of the present invention. System 60 is particularly useful for executing method 10, as detailed hereinabove. System 60 comprises a computing source node 62, and a plurality of computing sink nodes 64 deployed over an area 66 remote from computing source node 62, thus forming a network 68. Each of source node 62 and computing sink nodes 64 comprises a circuit (not shown) for encoding and decoding information. The communication between the individual nodes of network 68 are preferably wireless, according to any communication standard, such as, but not limited to, IEEE 802.11 , IEEE 802.11 a-g, IEEE 802.15.4, and derivatives thereof.

The circuit of computing source node 62 is characterized by a transmission rate, r. The computing sink nodes 64 comprise at least one sink node 64a of a first type, and at least one sink node 64b of a second type. Each of the sink nodes 64a has a circuit characterized a maximal rate of at least the source's transmission rate, r, and each of the sink nodes 64b has a circuit characterized a maximal rate of less than the source's transmission rate, r.

In operation of system 60, the circuit of computing source node 62 precodes the input information as further detailed hereinabove, and transmits the precoded information over the network 68 to provide each of the plurality of sink nodes 64 with a respective a sink input. The circuit of computing source node 62 transmits to a sink node 64a a control signal causing the circuit of sink node 64a to decode a respective sink input to extract all the input information, as further detailed hereinabove. The circuit of computing source node 62 transmits to a sink node 64b a control signal causing the circuit of sink node 64b to decode a respective sink input to extract a portion of the input information, as further detailed hereinabove.

It is expected that during the life of a patent maturing from this application many relevant communication networks will be developed and the scopes of the terms computing source node, and computing sink node, are intended to include all such new technologies a priori.

As used herein the term “about” refers to ± 10 %.

The terms "comprises", "comprising", "includes", "including", “having” and their conjugates mean "including but not limited to".

The term “consisting of’ means “including and limited to”.

The term "consisting essentially of' means that the composition, method or structure may include additional ingredients, steps and/or parts, but only if the additional ingredients, steps and/or parts do not materially alter the basic and novel characteristics of the claimed composition, method or structure. As used herein, the singular form "a", "an" and "the" include plural references unless the context clearly dictates otherwise. For example, the term "a compound" or "at least one compound" may include a plurality of compounds, including mixtures thereof.

Throughout this application, various embodiments of this invention may be presented in a range format. It should be understood that the description in range format is merely for convenience and brevity and should not be construed as an inflexible limitation on the scope of the invention. Accordingly, the description of a range should be considered to have specifically disclosed all the possible subranges as well as individual numerical values within that range. For example, description of a range such as from 1 to 6 should be considered to have specifically disclosed subranges such as from 1 to 3, from 1 to 4, from 1 to 5, from 2 to 4, from 2 to 6, from 3 to 6 etc., as well as individual numbers within that range, for example, 1, 2, 3, 4, 5, and 6. This applies regardless of the breadth of the range.

Whenever a numerical range is indicated herein, it is meant to include any cited numeral (fractional or integral) within the indicated range. The phrases “ranging/ranges between” a first indicate number and a second indicate number and “ranging/ranges from” a first indicate number “to” a second indicate number are used herein interchangeably and are meant to include the first and second indicated numbers and all the fractional and integral numerals therebetween.

It is appreciated that certain features of the invention, which are, for clarity, described in the context of separate embodiments, may also be provided in combination in a single embodiment. Conversely, various features of the invention, which are, for brevity, described in the context of a single embodiment, may also be provided separately or in any suitable subcombination or as suitable in any other described embodiment of the invention. Certain features described in the context of various embodiments are not to be considered essential features of those embodiments, unless the embodiment is inoperative without those elements.

Various embodiments and aspects of the present invention as delineated hereinabove and as claimed in the claims section below find experimental support in the following examples.

EXAMPLES

Reference is now made to the following examples, which together with the above descriptions illustrate some embodiments of the invention in a non limiting fashion.

EXAMPLE 1

In this Example, 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. Sub-rate coding offers an add-on to existing LNC. It allows sinks whose achievable rate is smaller than the source message-rate, termed "sub-rate sinks," to 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. This Example provides the theoretical foundations for sub-rate coding, and also formulates preferred conditions for a node (and the network) to become a legitimate sub-rate sink.

This Example includes several definitions, lemmas, corollaries, demonstrations, propositions, and theorems, which are all enumerated consecutively using the same enumerator. This Example demonstrates that the technique of the present embodiments is capable of establishing efficient communication when some of the network nodes are sub-rate max-flow sinks without affecting the eligible sinks.

Notations

The following notations are used in this Example.

Linear Network Coding

Consider a network G' = {V, E}, with V and E denoting network nodes and links respectively (also referred to as vertices and edges in graph theory). The network G' includes a source node s in V and a set T of sink in V. The max-flow between s and the sink t_i ∈ T is denoted by h_t1. All the information symbols are regarded as elements of a base field F.

The rate of the communication network is denoted by r, and is defined as the number of symbols created by the source at every network use. Thus, r is positive integer. For simplicity, r is assumed to be constant, but the present embodiments can be applied also in cases in which r varies with time.

For every node x ∈ V\{s], the sets of input and output links to the node are denoted by In(x) and Out(x) respectively. For convenience, it is customary to add another node s', referred to as the imaginary source, that has r outgoing links to the original source s. The outgoing links of the imaginary source s' are referred to as imaginary links. Thus, In(s) is a set of r imaginary links. It is assumed that G' includes the imaginary source and links.

All the nodes in the network are able to perform calculations over the field F.

Following is a description of a linear network code (LNC) for finite acyclic network :

Definition 1. An r-dimensional LNC operating over a field F in an acyclic communication network is characterized by a set Local Encoding Kernels (LEKs), each being associated with an adjacent pair of links in the network, and a set of Global Encoding Kernels (GEKs), each being associated with a link in the network. A Local Encoding Kernel (LEK) is a scalar k_e, _e E F for a respective adjacent pair of links {e’, e}, where both e' and e share a node such that e' is an incoming link to the respective node and e is an outgoing link from the respective node. The LEKs associated with node x are arranged as a |In(x)| X |0ut(x)| matrix. A Global Encoding Kernel (GEK) is an r-dimensional column vector f_e for a respective link e ∈E, such that for every non-source node x, and every

and such that for the imaginary links e ∈ In(s), the set of vectors ^are the r linearly

independent vectors that constitute the natural basis of the vector space F^r.

Note that according to the above definition, when the LEKs at all the nodes in an acyclic network are known, the GEKs can be calculated recursively in an upstream-to-downstream order.

Definition 2. Let denote the GEKs in an r-dimensional F-valued LNC on a

single-source finite acyclic network. Let A LNC that satisfies

for every non-source node x with is referred to as a "linear

multicast."

In [Li et al., EEE Trans. Inform. Theory, 2003, 49:371], an algorithm for the construction of a linear multicast is provided, requiring the field size |F| to be greater than the size of the set of sinks whose maxfl ow({T}) > r. This algorithm provides a LNC that allows all target sinks to receive decodable information simultaneously in every network use. This algorithm does not require that the set of target sinks include all the eligible sinks (satisfying h_t1 > r). Thus, in this algorithm it is possible to create a generalized linear multicast, which is defined below in Definition 3.

Definition 3. be the set of GEKs in an r-dimensional F -valued LNC on a

single-source finite acyclic network. Let Define a set of non-source

nodes

as sinks. Then, an LNC for which

for any sink t E T with max — is referred to as a "generalized linear multicast".

This Example only considers generalized linear multicasts, and so the term generalized linear multicast is abbreviated as "linear multicast".

Note that not all the links in G' need necessarily be employed by the network code in the case of a generalized linear multicast. Without loss of generality, this Example considers the network G, which is defined as the sub-network of G' consisting only of the links from E that are employed by the network code along with their adjacent nodes. A network node in G that is neither source, nor sink, shall be called an intermediate node. A path is a set of links that provides a connection between two nodes in the network.

As defined in Definition 3, a generalized linear multicast assumes that every network uses the source is generating and transmitting r symbols, and every eligible sink tj can extract the transmitted symbols from the /^different symbols it receives. Nevertheless, in this Example, a node ti is defined as a sink of the multicast even if h_t1 < r. In this case, the algorithm described in Li et al., supra, for constructing a linear multicast yields h_t1 independent paths from s to t_i, resulting in h_t1 linearly independent symbols received by f every network use.

Two different approaches to LNC had been proposed: modeling the data units and the coding operations over the finite field GF(q^L) (scalar network coding), or modeling the data units and vector operations over GF(q)^L (vector network coding) [Ebrahimi et al., 2010 IEEE International Symposium on Information Theory, 2408-2412], For simplicity, this Example describes scalar network coding, but the skilled person, provided with the description provided in this Example, would know how to equivalently apply the results provided herein also to vector network coding.

Global Encoding Kernel and Matrix

For a scenario whereby a network operates at a constant rate r, a GEK can be derived from the LEK and vice versa. Consequently, a LNC is equivalently defined by a r X m matrix B over the field F, where m = |E|. The matrix B is referred to herein as a Global Encoding Matrix (GEM). Every column, b_e, of B is associated with one network link, such that multiplying an input vector v E F^r by this column results in the symbol from F that the network code conveys on that link per network input vector v. Observing that the h_t links impinging on the sink t are employed for decoding the information reaching this sink, one can denote by B_t the r X h_t matrix whose columns are given by {b_e|e is entering t &. used for decoding in t}. The matrix B_t is referred to as the global encoding matrix (GEM) of the sink t. Note that in the special case in which h_t=1, B_t is vector of length r. From the linear multicast definition, it is guaranteed that the columns of B_t are linearly independent. Particularly, if a sink t satisfies h_t > r, B_t is an invertible matrix (the sink only uses min{h_t, r) links for decoding). The vector space spanned by the columns of B_t is denoted by B_t'.

Decoding

Each sink t holds a h_t X h_t decoding matrix, D_t, whose entries are defined over the field F. The decoding matrix is used for extracting the source information v from the sink input, vB_t. When h_t ≥ r, B_t is invertible, and hence, D_t can be selected to be D_t = Bt^-1, so that vB_tD_t = v. The case h_t < r is generally not decodable, and was not considered before. The Inventors found that this case is beneficial, as will be shown below.

Precoding

The Inventors introduce a procedure referred to herein as “precoding” into the framework of network coding. The precoding is optionally and preferably executed at the source node, prior to transmission. To this end, the source information v is multiplied by an r X r matrix P over the field F. The procedure is referred to as "precoding" since the input to the network is vP rather than v.

Data can be decodable by the sinks, when P is invertible, namely when the r outputs from the source are linearly independent. Consequently, for each sink h_t with h_t > r, the choice of decoding matrix D_t is changed to D_t = B_t ^-1P^-1, thus providing vPB_tD_t = v. Given that, the network code and the precoding scheme are independent with respect to one another. Meaning that the construction of the network code is carried out irrespective of the precoding, the precoding process is reversible, so its effect on the information can be mitigated by those sinks satisfying h_t > r.

Sub-Rate Block LNC

I consecutive network uses are referred to as a block LNC of length I • r. This approach is referred to as l-block linear multicast of B. In this Example, the network code and the transmission rate are considered constant within a block. Therefore:

1) A row vector v of length I • r is referred to as LNC message block at the network input;

2) The precoding matrix P is an invertible I • r X I • r matrix;

3) The GEK matrix is a I • r X I • |E| block matrix B, with I identical blocks B on the diagonal, so that each sink t is reached via a global encoding matrix B_t which is a I • r X I • h_t block matrix; and

4) The decoding matrix of the sink t, D_t, is a I • h_t X I • h_t matrix.

The decoding rate of a sink is defined as

For a sink t with h_t > r (i.e B_t is invertible), B_t is also invertible. Therefore, defining allows t

to decode all the transmitted data, thus supporting a decoding rate of r, as in a single-

network-use case.

Sub-rate Codins

Sub-rate coding and decoding is introduced according to some embodiments of the present invention for improving the overall system throughput achievable via linear multicast. Such improvement can be realized by judicious selection of a coding and decoding approach that allows those nodes whose max-flow, h_t, is smaller than the source rate r, to extract a portion of r data units in each network use.

Herein, a sink t with h_t < r, is referred to as a sub-rate sink. According to information theory, a sink cannot operate at rates higher than its max-flow h_t (the max-flow between the source and a sink is essentially the capacity of the corresponding set of links constituting a communication path). The present embodiments thus provide communication rate as close as possible to the max-flow of a sub-rate sink, while allowing no interference, or rate loss, to be experienced by any eligible sink. Note that the max-flow to a sub-rate sink t is sink dependent, and different sub-rate sinks may have different max-flows.

In this section, a few basic scenarios of sub-rate coding shall be explicitly demonstrated in order to explain the coding of the present embodiments by way of examples. All the examples in this section concern a specific case of a network operating at symbol generation rate of r = 3.

A Single Sub-Rate Sink

In the case of a single sub -rate sink t (with h_t < r) the GEM of t, B_t, is a 3 X r full (column) rank matrix.

Lemma 4. Let sink t be a single sub-rate sink, with h_t = 2 in a linear multicast with r = 3. There exists a linear multicast of rate 3 allowing t to work at decoding rate of 2.

Definition 5. A BR-factorization of an arbitrary m X n matrix A, (m > n), with linearly independent columns is defined as a multiplication of two matrices A = BR, where B is an invertible m X m matrix, and R is an m X n matrix whose columns are n out of m (distinct) columns taken from the identity m X m matrix I_m.

Any full rank matrix has a BR-factorization. Consider, for example, B = (A | A^C); A^C as an m X (m — ri) complimentary matrix such that B spans the m-dimensional space over the field F, and R = (The first n columns of I_m).

Note that the BR-factorization of a matrix A is not unique.

Following is a proof of Lemma 4.

Using a BR-factorization of B_t, one can define B_t = BR. By definition, B is invertible. Taking P = B^-1 provides:

1) Any sink t' with

_t can fully decode the transmitted data, with the choice of decoding matrix since

2) The sub-rate sink t can operate with decoding rate of h_t = 2, with the choice of Recall that 7? is a 3 X 2 matrix with columns from I₃ - and so t

can decode two of the three transmitted symbols.

The case of h_t = 1 can be treated in exactly the same way. The decoding rate of t can only be 1 in this case.

Two Sub-Rate Sinks

Lemma 6. In the case of two sub-rate sinks t₁ and t₂, there exists a linear multicast of rate 3 allowing t₁ and t₂ to work at decoding rates of h_t1 and h_t2 respectively.

The proof will be given by examining all possible cases: 1) h_t1 = h_t2 = 1. It is shown that there exists BR-factorizations B

that satisfy

Recall that when h_t=1, the GEM of t is a vector, and so in this case both are vectors.

(a) If the vectors are linearly dependent,

(B_t1 \two complimentary linearly independent vectors'), with D_t1 = 1 and D_t2 =

a, provides PB_t.D_ti = R_t.. In this case, both sub-rate sinks can decode the same symbol.

(b) If the vectors B_t1, B_t2 are linearly independent, the choice

(B_t1 \B_t2 \complimentary linearly independent vector), D_t1 = D_t2 = 1 provides

R_t.. In this case, each sub-rate sink decodes a different symbol.

2) h_t. = 1, h_t. = 2 (without loss of generality, i = l,j = 2). In this case B_t1is a vector, and , B_t is a matrix.

(a) If the vector B_t1 is linearly independent of (i.e. not on the “plane” spanned by) the vectors of B_t2, then choosing where

1, D_t2 = I₂, provide

(b) If the vector B_t1 is on the plane spanned by the vectors of B_t2, a slightly different approach is used: essentially, decoding matrix D_t2 is required to manipulate the columns of B_t2 so that one of them becomes

but the span of the obtained matrix does not change. Stated mathematically, span{B_t2D_t2] = span{B_t2}, while B_t1 is one of the columns of B_t2D_t2. Such D_t2 necessarily exists since B_t1 is in span{B_t2}. Then, the choice of B = (B_t2D_t2 \complimentary linearly independent vector) where provides

Notably,

3) h_t1 = h_t2 = 2. In this case both B_t1 and B_t2 are matrices.

(a) In case the vectors in B_t1 and B_t2 span the same subspace, one can pick any two linearly independent vectors v_r and v₂ in that subspace, then choose B =

Matrices D_t1 and D_t2 exist such that for i = 1,2, the columns of will be As in the previous case,

Therefore alongside the corresponding D_t1 provide

(b) In case the vectors in B_t1 and B_t2 span different subspaces, these subspaces define two different planes. Therefore, their intersection forms a line. Let v be a vector on that line. Let v₁ and v₂ be two vectors

and B_t2 respectively, such that for i = 1,2, and

{v, v_lt v₂} is a linearly independent set. Choosing

decoding matrices D_t1 and D_t2 exist, such that for i = 1,2, the columns of B_t.D_ti will b Therefore P = B^-1 alongside

these D_ti provide PB_t.D_ti = R_t..

Based on the understanding of the methodology gained in the aforementioned scenarios, the following lemma is introduced.

Lemma 7. Let B E M(F)_rxm be a global encoding matrix for a linear multicast on the graph G = {V, E} with a source s E V and set of sinks

where m = | E | . For every sink t E T, denote by B_t the GEM of t, by h_t its max-flow from the source s, and by D_t its decoding matrix. Let T T be a set of sub-rate sinks, If there exists a matrix B, and matrices

D_t and R_t for each sub-rate sink t, such that BR_t is a BR factorization of B_tD_t, then each sub-rate sink t E T' can work at a decoding rate h_t1

Proof. The matrix B is invertible by the definition of the BR-factorization. Hence, the precoding matrix P can be defined as P = B^-1. The input to a sink t will then be PB_t, multiplying this by the decoding matrix of t, D_t, the output of t is: Since

the columns of R_t are, by the definition of the BR-factorization, different columns of I_r, then given a transmitted data vector v and t is capable of working at a

decoding rate h_t1

Definition 8. A set of vector

{ } is referred to as an exact spanner with respect to the set of matrices if for each and every r X h_t matrix B_t E B, there

exists a subset of V with exactly vectors { with sp

def span^Bt} = Bi'.

Note that an exact spanner V may contain linearly dependent vectors.

Corollary 9. Let B ∈ M(F)_rxm be a global encoding matrix in a linear multicast on the graph G = {V, E] with a source

and set of sinks

For every sink t E T, denote by B_t the GEM of t, by h_t its max-flow from the source s, and by D_t its decoding matrix. Let T' c T be a set of sub-rate sinks, with If there exists a set of r vectors U =

such that (i) { are linearly independent, and U is an exact spanner with

respect to B, then each t, ∈ T' can work at a decoding rate h_ti .

Proof, let t ∈ T' be a sub-rate sink. The GEM B_t is a full-rank r X h_t matrix, r > h_t1 Therefore, for any set of h_t length-r vectors spanning the same subspace as do the columns of B_t, there exists a h_t x h_t matrix D such that the columns of B_tD are these vectors. Formally, if

then an h_t x h_t matrix D necessarily exists such that B_tD = Since U is an exact spanner with respect to there exists a subset of

size h_t spanning the same subspace as the columns of B_t. The choice D_t = D, and the matrix created by concatenating the columns of U as B, one gets that for every t ∈ T', all the columns of B_tD_t are also columns in B. The choice of R_t as the columns from I_m pointing at the locations of the columns of B_tD_t in B, one gets that B_tD_t = BR_t, namely - BR_t is a BR-factorization of B_tD_t for every t ∈ T' . Thus, according to Lemma 7 any sub-rate sink t E T' can work at a decoding rate h_t1

Corollary 9 implies that when given a set of sub-rate sinks, in order to enable all of them to work in their maximum possible decoding rates (while not interfering with the full-rate sinks to operate at rate r), it suffices to find a set U of r vectors that: (a) are linearly independent; and (b) U is an exact spanner with respect to the GEMs of all the sub-rate sinks. Note that these conditions do not imply that the cardinality of U has to be r. If indeed |U| < r, then r — |U| linearly independent vectors may be added to U in order to create a linearly independent exact spanner with cardinality r, as required for the precoding scheme described in Corollary 9.

Three sub-rate sinks

Lemma 10. Given three sub-rate sinks with h_ti = 2 for 1 ≤ i ≤ 3, in a linear

multicast with rate

_{l 2} = 0, then there exists a linear multicast with rate r = 3 allowing all three sub-rate sinks to work at decoding rate 2.

This lemma is best understood by geometrically. Based on Corollary 9, it suffices to find a set U, of 3 linearly independent vectors, such that every plane defined by B_t. is spanned by a combination of 2 of the vectors of U. Recalling that every two planes intersect in a line, and given that all three of planes intersect in a point one gets that there are 3 different lines of intersection, so that choosing U to be these 3 lines satisfies the condition of Corollary 9.

Proof of Lemma 10. First, note that B_ti', 1 ≤ i ≤ 3, represent 3 different subspaces (otherwise,

1, since it is an intersection of only two planes). This implies that for every 1

one has

= 1. Denote by a

vector in B_ti' ∩ B_{t j}'. Since the set U is a set of

linearly independent vectors, and since every vector is in the intersection of two subspaces, U is an exact spanner with respect to B_ti, 1 ≤ i ≤ 3. Therefore, according to Corollary 9, all 3 sub-rate sinks can work at a decoding rate of their max-flow - 2.

For other cases pertaining to three sub-rate sinks a set U with the required characteristics does not necessarily exist, as shown in the following demonstration. Demonstration 11. Let B denote a linear multicast of rate r = 3, and let T' = {t₁, t₂, t₃} be a set of sub-rate sinks with h_t = 2 for any t G T' , with B

In this case, namely

1. However, there is no possible choice of 3 vectors satisfying the conditions for U in Corollary

9.

FIGs. 3A and 3B are schematic illustrations of two cases of three-plane configurations that explain the difference between the cases in Lemma 10 and Demonstration 11. A case similar to the one of Demonstration 11 is presented in FIG. 3 A. In this case, the 3 planes intersect on a line and so there is no possible choice of 3 vectors which form an exact spanner. An exact spanner for this example can be, for example, the set of vectors {v,u₁,u₂,u₃} marked on FIG. 3 A. The case shown in FIG. 3B shows three planes that intersect at a point so that B_ti' ∩ B_t2' ∩ B_t3'. In this case a set of 3 linearly independent vectors which is an exact spanner does exist, and it is the set of three vectors that are the intersection of each 2 planes. An exemplified set of vectors {u₁,u₂,u₃} is shown in FIG. 3B.

Full Sub-Rate Coding

This section describes a linear multicast operation at some arbitrary rate r = n. in accordance with embodiments of the present invention, each of the sinks in a subset T' c T of sinks, t ∈ T', with h_t < r, decodes at a rate as close as possible to its max-flow, while any eligible sink t in T \ T' can still decode the incoming information at rate h_t = r.

A sub-rate sink t is declared as fully sub-rate decodable under linear multicast PB_t, if it can decode incoming information at rate h_t1 The matrices D_t G

and R_t G M_nxht(F) include h_t distinct columns taken from l_n, such that PB_tD_t = R_t.

Exemplified procedure for realizing full sub-rate coding

In the following procedure, all vectors are of length r over the field F, and all matrices are full (column) rank matrices with r rows and r or less columns, over the field F. Note that when referring to a set of matrices in case two matrices span the same

vector space, one matrix, say B_b can be omitted from B. The corresponding sink i may still be fully sub-rate decodable, if so is the case with sink j whose matrix is Bj. Thus, without lose of generality, assume that the matrices in the set do span k different subspaces.

Definition 12. The commonality degree of a vector v (a line is referred to herein as a vector lying on that line) with respect to the set of matrices

denoted by , is the number of matrices B_i in with

, the subspace spanned by B_i

Definition 13. The commonality degree of an arbitrary set of vectors

with respect to the set of matrices denoted by is the sum of the

commonality degrees of all the vectors in V with respect to B, namely

Definition 14. The commonality set size of a set of matrices denoted

by is the minimum cardinality of a set of vectors V, where V is an exact spanner of

Lemma 15. Given a set of k sub-rate sinks

T' in a linear multicast B, consisting of a set of global encoding matrices then all the sub-

rate sinks in T' are fully sub-rate decodable.

Proof. By the definition of the commonality set size of

, there exists an exact spanner V with cardinality

Showing that the vectors of V are linearly independent will have V fulfills both conditions of Corollary 9, and hence concludes the proof. Since V is an exact spanner of B, it is also a spanner of meaning that

|V|, where the equality follows from the condition of the lemma. Yet taking into account that any set of vectors satisfies necessarily results with

meaning that all the vectors of V are linearly independent, and by Corollary 9, all the sub-rate sinks in T' are fully sub-rate decodable.

The Inventors devised a procedure for finding the value

when given an arbitrary set of sub-rate sinks T' in order to determine whether exist such that all the

sinks in T' are fully sub-rate decodable.

Referring to Lemma 15, and taking in account that see,

e.g., Demonstration 11, the Inventors provided sufficient conditions under which a set of matrices satisfies Thus, in the following, a (constructive) method for

upper bounding

is described.

Definition 16. The c-commonality set size of a set of matrices denoted

by ) is defined as follows:

Note that the dimensions counted by are not re-counted in

Note that for any

s well defined and is only based on the intersections of relevant vector spaces resulting from B.

Proposition 17. Every element of the (external) sum in c (of either Definition

16(2) or 16(3)) is of the dimension of a c-set intersection perpendicular to any (c + 1)-set intersection that is a sub-vector space. Therefore, given a set of vectors V that span all the (c + 1)-set intersections, c an upper bound on the minimum number of vectors one has to

add to V so as to span also all the c-set intersections. Note that is not necessarily the

minimum possible number, since there is no requirement that all these additional vectors be linearly independent among themselves. This preposition follows from the previous definition.

Definition 18. The commonality polynomial of a set of matrices

denoted

is defined as

i_c = and V is an arbitrary set of vectors, can be thought of as

receiving an arbitrary set of vectors V, and for every 1 ≤ c ≤ k, calculating the number of vectors of commonality degree c in the set, substituting the result as i_c. The outcome of is the commonality degree of V with respect to

In order for a set of vectors to be an exact spanner, all entries of

are optionally and preferably no greater than the c-commonality set size of

hence, when given a set of vectors as long as V is

an exact spanner, as shown in the following lemma.

Lemma 19. Given a set of matrices any vector )

that satisfies

means that there exists a set of vectors V that constitute an exact spanner of B, with \{v E This means that

Proof. For simplicity, a specific special case in which i

is proven. Firstly, note that any subspace B_t' can be presented as a sum of subspaces, each created by the sum of intersections of B_t' with a different number of other subspaces from

Let

be the subspace that is a sum of all possible c-set intersections that include B_t'. B

Denote by the c-commonality dimension of B_t' with respect to

defined as

; and co

For each 1 < c < k, represents the contribution of the c-set intersections (that

include B_t') to the dimension of B_t' that had not been added with (c + 1)-set intersections. By definition

Note that every c-set intersection (with B

included) is contributing its “unique” dimension to both and

with possibly consisting

additional c-set intersections (those that do not include B leading to the fact that

Since any c-set intersection repeats in c sets, one gets the relation c -

which in turn results in:

This means that is indeed an adequate choice for lemma 19.

Consequently, the construction of V can optionally and preferably be carried out according to the guidelines below.

Begin with

The construction is realized by running through the commonality degrees c, beginning with c = k. For c = k, choose linearly

independent vectors from and add them to V.

For each k — 1 ≥ c ≥ 1, choose vectors by creating c-set intersections and

choosing the number of vectors required for spanning them according to the corresponding element of the sum

(iⁿ Definition 16); this process guarantees that vectors with higher commonality degree required for spanning the intersection are already contained in V. Note that by construction, there is a set of

vectors spanning for every c

(practically, any spanning subset o vectors from those chosen by at least c-

intersections including B_t' is be adequate). Overall, a total of vectors of

commonality degree of c are systematically chosen in this step for each value of c. Add them to V.

The process described above ensures that

for every 1 ≤ c ≤ k. Since for every c, one obtains a subset of

vectors spanning one obtains a set of size spanning B_t', so that V is an exact

spanner.

Theorem 20. This theorem is referred to as the Full Sub-Rate Decodability (FSRD) Theorem. Given a set of sub-rate sinks T' in a linear multicast B, consisting of a set of global encoding matrices (every pair of matrices spanning two different subspaces),

if there exists a vector

that then all the sub-rate sinks in

T' are fully sub-rate decodable.

Proof. According to Lemma 19, since

there exists a set of vectors V that is an exact spanner o

. Since V is an exact spanner of B, and hence

which according to Lemma 15, means that all the sub-rate sinks in T' are fully sub-rate decodable.

In a linear multicast network with rate r, in order to determine whether all the sub-rate sinks in a set T' with B are fully sub-rate decodable, and find the proper linear

multicast configuration fulfilling it, the following procedure can be used:

1) Find the proper domain for the polynomial

For every 1 ≤ c ≤ k, compute according to the definition. It is a closed form derived by all the possible

intersections of the subspaces

2) Find a vector satisfying both

conditions:

3) Define an empty set V = {}.

4) For c = k: —1: 1, proceed as follows:

(a) Find i_c linearly independent vectors with commonality degree of

denoted by V_c, such that V_c U V is a linearly independent set.

(b) Substitute

5) Since |F| =

all the vectors in V are linearly independent. If the number of vectors in V is smaller than r, find a set of

vectors, denoted U, such that U + V span the r-dimensional vector space. Accordingly, substitute V ← U + V.

6) Define B = mat(V), a matrix whose columns are the vectors of V. V is an exact spanner of B, allowing to find for each t E T^r an invertible h_t X h_t matrix D_t satisfying B_tD_t = BR_t, with R_t being the columns from I_r pointing at the locations of the columns of B_tD_t in B (see Definition 9). Since B is invertible, it is possible to define the precoding matrix

7) The result, a linear multicast PB, allows any of the sub-rate sinks t ∈ T' to work at a decoding rate of its max-flow h_t using the corresponding decoding matrix D_t.

Demonstrations and Corollaries

Following is a demonstration for the usage of the procedure, as well as two more general cases that are immediate corollaries from the theorem. The Annex below provides examples for more cases in which the FSRD theorem can be applied in order to determine whether a set of sinks are fully sub-rate decodable.

Demonstration 21. Let T' = {_t1, t₂, t₃} be three sub-rate sinks with

3 in a linear multicast B with rate r = 3 over GF (3).

Let

be the corresponding GEMs of these sub-rate sinks, then all the sub-rate sinks in T' are fully sub- rate decodable .

Proof. Since the demonstration can be proven using

Lemma 10. The procedure described at the end of the previous section is used for finding the modifications required in order to find the proper linear multicast enabling full sub-rate decodability.

1) The domain for

is computed to be

as follows:

(a)

can be shown that

0, and so c This means that the third entry of

(b) For c = 2

Since so, the

second entry of has to satisfy

(c) for c = 1,

For each pair of indexes denote the third index by i₃, then:

Since for every

every

1, one gets that This means the the first entry of T is also 0.

2) The vector

is the only vector in the domain that satisfies both conditions of the FSRD theorem:

(a) is the 3-dimentional vector space, hence

3) Define V = {}.

4) Since i₃, i₁ = 0, this stage only requires finding 3 linearly independent vectors with . Such vectors can be found as the intersection vectors of each pair of sub-

spaces. This gives V₂ and hence the output from this stage is V=V2.

5) Since | V| = 3 = r, no vectors need to be added to V in this stage. 6) Define .

(a) For each 1 ≤ i ≤ 3, one finds matrices R , so that

(b) The precoding matrix i

7) The result, PB, is the desired linear multicast.

Corollary 22. Let B denote a linear multicast of rate r. A single sub-rate sink T' = {t}, with h_t < r and B = {B_t}, is always fully sub-rate decodable.

Proof. The proof employs the FSRD theorem. Since there is only one sub-rate sink t, one has comss§(l) = h_t1 The choice of I is i = (h_t). Then

Therefore - according to the FSRD theorem- T' is

fully sub-rate decodable.

Corollary 23. Let B denote a linear multicast of rate r, and let T' be a set of

sub-rate sinks with max-flow h_t = r — 1, consisting of a set of global encoding matrices

that span I different subspaces. If d , then T' is fully sub-rate

decodable.

The proof employs the FSRD theorem. Note that in this case

Since every matrix in B generates a unique (r — 1 dimensional) subspace, as h_t = r — 1 , the fact that the intersection of all the subspaces is of the smallest possible dimension implies that for every Therefore, according to the FSRD theorem, T'

is fully sub-rate decodable.

Partial Sub Rate Decoding Methodology

1) Partial sub-rate decoding in r = 3 for 3 sub-rate sinks.

Referring again to Demonstration 11, let B denote a linear multicast of rate r = 3, and let T' = {t_1, t₂, t₃} be a set of sub-rate sinks with h_t = 2 for every ti ∈ T' . Denote the corresponding matrices by I was shown that when there is no

possible choice of 3 vectors that constitute an exact spanner (Corollary 9). Indeed, in this case the conditions for the full sub-rate decodability theorem are not satisfied, since

and

(so an exact spanner requires 4 vectors, out of which 3 vectors v_t with

Notwithstanding the foregoing, this Example presents an approach through which it is possible to sub-rate decode all t_i ∈ T', by compromising on the decoding rate. The following definition precedes the main lemma of this subsection.

Definition 24. Define a k-degree BR-factorization of a m X n matrix A (m ≥ n ≥ k) as a multiplication of two matrices, A = BR, such that B is a m X m full rank matrix and R is an m X n matrix with k (out of n) columns taken from I_m.

Lemma 25. Let B denote a linear multicast of rate r = 3, and let T' = {t₁, t₂, t₃} be a set of sub-rate sinks with h_t = 2 for every t_i ∈ T' . Denote the corresponding GEM matrices by B = there exists a linear multicast of rate r = 3 allowing

every t_i ∈ T' to work at a decoding rate of hence t_i ∈ T' are partially sub-rate decodable.

Proof. A block of 3 network uses (instead of a single use), allows finding 5-degree BR factorizations with a single full rank matrix for all 3 of the GEM matrices of the sinks in T'. With this factorization, Lemma 7 is used in order to partially-decode 5 out of the 6 symbols each sink receives during the 3 network uses, thus allowing them to work at decoding rate of 5/3. This will now be shown mathematically.

Let and for every is a vector so that

Note that is an exact spanner of B. Let B denote the 3-block linear

multicast of B. Denote by v/ the vector obtained by substituting as the j-th block, with all the other entries being 0. For example, for

( )^T one has

Note that the se

is a linearly independent set of vectors, each of length l • r = 3 • 3 = 9. Defining as the matrix whose columns are the 9 vectors from so that is invertible. Employing

precoding matrix has each sub-rate sink receiving at its input where v denotes an input

data vector v E F^{l r}. Showing that B

for some matrices

matrix with 5 columns taken from I₉), and D provides the

appropriate 5-degree BR factorizations.

Since for every the block form of ' satisfies

For every i, let D/. be a basis transformation matrix such that

hence, there are exactly 5 columns of

_t /

For every i, let D_ti be a matrix such that B_t.D_ti has these 5 columns from

with the sixth column being the zero vector. Then constructing R_t. so that it chooses these 5 columns from B and leaving the sixth column as zero, provides the desired factorizaton

By employing D_ti as the decoding matrix for for every

Therefore each sub-rate sink

can decode 5 symbols every 3 network uses, meaning that it is sub-rate decodable with r_ti = 5/l = 5/3.

Corollary 26. In a linear multicast of rate r = 3, any set of up to 3 sub-rate sinks with max-flow of h_t = 2 can work at decoding rates of at least 5/3.

2) Partial sub-rate decoding in r = 3 for 4 sub-rate sinks.

The Inventors found that it is also possible to use a similar approach for a larger set T' of sub-rate sinks. Following is an example of achieving partial sub-rate decoding in block linear multicasting for 4 sub-rate sinks.

Lemma 27. let B denote a linear multicast of rate r=3, and let be a set

of sub-rate sinks with h_t1 = 2 for any

T . Denote the corresponding GEM matrices by B = {B Assuming that for every there exists a linear

multicast of rate r=3 allowing every o work at a decoding rate o

The proof is similar to that of Lemma 25. Since the intersection of any set of 3 subspaces is of dimension 0, an exact spanning set is of minimum size 4. Denote such spanning set by V =

where is a vector on the intersection line of the spaces

Choosing a 4-block linear multicast

with

would allow every sink to

decode 6 symbols. The rest of this proof follows the same line of arguments of Lemma 25. With 6 symbols decoded in 4 network uses, each sub-rate sink decoding rate is hence r_ti =

6/4 = 1.5.

Existence of partial sub-rate decoding in the general case

The previous lemmas show that for any set of sub-rate sinks T', there is a linear multicast allowing them to work at some decoding rate h_t' < h_t . In the following, this notion is formally substantiated.

Definition 28. Let denote a set of r-row matrices , each B_t comprises of

h_t linearly independent columns. A set of vectors is referred to as a partial exact

spanner with respect to

if for every 1 < t < k, there is a subset of V with h_t' linearly independent vectors, for some 1 denoted by

Lemma 29. Let denote a GEK for a linear multicast of rate r on the graph

with a source s G V and set of sinks For every sink t E T, denote by B

_t the

GEM of t, B , by h_t its max-flow from the source s, and by D_t its decoding matrix.

Let T' ⊂ T be a set of sub-rate sink If there exists a set of r linearly independent

vectors

that constitutes a partial exact spanner with respect to B with } spanning vectors (for each of the d sinks), when for each - then

each sink

an work at decoding rate of

Proof. Le

be a sub-rate sink. Its GEM B_t is a full-rank r X h_t matrix, r

Therefore, for a set U_t of h_t' vectors that span a subspace of

there exist a h_t X h_t' selection matrix C_t (that selects the h_t' out of h_t decodable input coordinates) and h_t' X h_t' decoding matrix D_t, so that the columns of B_tC_tD_t are the vectors of U_t. Since for every t, there is such a set U_t ⊂ U of h_t vectors, there also exist such matrices D_t and C_t. By the choice of D_tc = C_tD_t, and the matrix created by concatenating the columns of U asB, one ensures for every t E T', all the columns of B_tD_t are columns of B. The choice of R_t as the columns from I_r pointing at the locations of the columns of B_tD_t in B, yields B_tD_t = BR_t, namely - BR_t is a h_t- degree BR-factorization of B_tD_tc for every t E T' . Therefore, each sub-rate sink t G T’ can work at decoding rate of h_t'.

Theorem 30. Let B G M(F)_rxm be a GEK for a linear multicast on the graph G = {V, E} with the source s E V and set of sinks For every sink denote by B_t the GEM of t,

by h_t its max-flow from the source s, and by D_t its decoding matrix. Let T' c T be a set of sub- rate sinks, Each sub-rate sink can work at some positive decoding rate.

Proof. Denote by

a set of matrices derived from the GEM of a corresponding set of sub-rate sinks; these matrices span different subspaces. Let V be an exact spanner of (choosing the exact spanner with minimal cardinality provides better results, in the sense of a smaller I, but it is not mandatory). Let and I (the block size) be the number of distinct subsets of V that cons

ist linearly independent vectors. Denote these subsets by

For each

be a set of r linearly independent vectors (spanning the r-dimensional vector space), with

denote the Z -block linear multicast associated with B, and let

be the set of block matrices induced by B. Denote by

the set of r ■ I column vectors created by substituting every as the i-th block with all the

other entries being 0. Note that all the vectors in are linearly independent. Denote

For every t ∈ T', denote by h_t' the number of columns in V that are in the

subspace spanned by B_t . Note that h_t > h_t' ≥ 1, since there have been least h_t vectors spanning B_t in V, and the choice of all the distinct subsets of V that are linearly independent assures that they are included at least once. Therefore, V is a partial exact spanner with respect to B, with

Employing Lemma 29 concludes the proof.

The inventors found that it is possible to express the minimum block length as a function of the intersections between the sets in B. This is advantageous since it shortens the decoding delay, requires smaller amount of memory at the end units and enables all operations to be executed with smaller-size matrices. Note that one may derive the minimum size of a “valid” exact spanner as the minimum value of the sum

when

that is satisfying

(see Lemma 19). In some embodiments, the block length is a function of the values of the c- commonality set sizes of B for all

In some embodiments of the present invention the effective decoding rates are selected to be the maximal effective rates at which all the sub-rate sinks can operate simultaneously. It is noted that the effective rate can also depend on the values of the c-commonality set sizes of B for

All the results in this Example can be applied to vector network coding, which means operation with blocks of size m over a binary field instead of the field of size 2^m, referred to as scalar network coding. Sub-Rate Coding for Static Linear Network Codes

Often, network configuration may change due to various reasons such as node failures and communication-channel variations to name but a few. A method in network coding relates to static linear multicast, aimed at facilitating the communication with all the designated sinks under a few, different, network configurations without having to change the network code when the network configuration changes. This capability comes at the cost of increasing the field size, hence reducing the communication rate, with the number of (predetermined) configurations as a factor of the former increase.

A method for constructing static linear multicast was presented in [Fong et al., 2006, IEEE Information Theory Workshop 409-412], For every sink t ∈ T of the network and every configuration, an virtual sink t^ε is created, with max-flow_ε(t) paths connecting it to the

original source, where max-flow_e(t) denotes the max-flow from the source to the real sink t under the network configuration ε. The linear multicast is designed as further detailed hereinabove, with the set of virtual sinks acting as the designated set of sinks, while making sure that all the paths to each virtual sink t^ε only employ links that are present in network configuration £. This generate ε-GEM matrices, each representing the linear multicast under one of the

link-failure configurations.

Sub-rate coding can be combined with a static network code in more than one way.

When the different configurations are not a result of spontaneous link failures, but rather expected changes in the network’s topology, it is assumed that the network source can keep track of the instantaneous configuration in each network use. In this case, for each configuration £, a set of sub-rate sinks T_ε', each set accompanied by a precoding matrix P_ε, can be defined with respect to the £-GEM B_E, as further detailed hereinabove.

When the current network configuration is not monitored by the source, the choice of the set of sub-rate sinks and precoding matrix cannot change per configuration. In this case, a set of designated sub-rate sinks T' is defined to be fixed. For each sub-rate sink t E T', a specific configuration £_t E £ has to be chosen, and the sink’s ε-GEMs, B is the matrix considered for

the computations detailed above. In this case, the precoding matrix P is fixed, and is computed as an invertible matrix using the set of matrices In general, each designated sub-rate sink

t E T' applies the sub-rate decoding scheme in the configuration ε_t or in other configurations ε E with Note that - for every designated real sink t E T, for any

configuration £ where being the network’s operation rate, is an invertible

matrix, ensuring that the precoding does not interfere with its decoding ability. Sub-Rate Coding for Variable-Rate Linear Network Codes

The sub-rate coding of the present embodiments can also be combined with variable-rate network coding [Fong et al., supra}. This network coding method employs the same linear multicast under different rates of symbol-generation from the source, up to the number of outgoing links from the source. For example, if the source has 5 outgoing links, then linear multicast using variable-rate network coding allow it to operate at any rate r < 5, making the transmission decodable by all sinks whose max-flow is at least r. This method does not necessitate a larger field size, hence it entails no reduction in rate.

The construction method of variable rate linear multicast can be carried out similarly to way described above for the linear multicast, except for the input graph, leading to a change in both the path-finding stage and the value calculation stage of the linear multicast. This results with a LEK. Note that the GEM B can not be well defined, because the number of its rows equals the symbols generation rate r, which is not constant. Alternatively, for every network operation rate 1 ≤ q ≤ r, B_q, a q-GEM is defined, as a q X |E| matrix that represents the network code operation under the rate q. In order to combine sub-rate coding with variable-rate coding, each rate is treated separately. Typically, for every operation rate q a different set of sub- rate sinks is defined with respect to B_q, and a corresponding q X q precoding matrix P_q is derived. Since the network operation rate is determined by the network source, it can also adjust the precoding scheme accordingly.

Note that since the sub-rate coding scheme is adjusted for each rate, one may choose different sinks for each rate. This is advantageous because at each operation rate, different sinks have max-flow from the source that is smaller than the network operation rate. In other words, the set of potential sub-rate sinks changes with the network operation rate.

Sub-Rate Coding as Alternative to Sinks Addition

As more nodes in a network get designated as sinks, the size of the field over which calculations need to be performed increases.. In some cases, this can reduce the communication rate to all the sinks in the network. The present inventors found a solution to this problem, by defining the designated nodes as consequential sub-rate sinks, rather than as standard sinks. Thus, according to some embodiments of the present invention the linear multicast is constructed by defining some of the designated sinks as intermediate nodes. Using the effective rate allowed by the network code, each such intermediate node is approached as sub-rate sink and operate at its consequential max-flow, which is basically the number of linearly independent inputs to this node as entailed by the linear multicast. The inventors found that this approach improves the communication rate with the designated nodes compared to the rate achievable by regarding them as standard sinks, in particular when working with a small set of sinks.

The following proposition provide a sanity-check for identifying whether a single node is to be regarded, according to some embodiments of the present invention, as a standard sink, or as a consequential sub-rate sink. Just recall that, as explained above, this is not the only consideration in favor of employing the sub-rate coding methodology.

Proposition 31. Let B E M(F)_rxm be a GEK for a linear multicast on the graph G = {V, E} with a source s E V and a set of sinks T c V. For every node t E V, denote by h_t its max- flow from the source s, and by B_t the GEM of t, which is the matrix whose columns, taken from B, represent the links entering t, just as the GEM is defined for a “standard” sink. For a node t ∉ T let r_t denote the consequential max-flow, namely the number of linearly independent columns in B_t (for standard sinks, r_t = h_t, but in general r_t < h_t). Denote by F' the field required for considering the set of sinks then considering t as a

sink would reduce its communication rate compared to considering it as a consequential sub-rate sink.

The proof considers two cases, as follows.

1) Referring to t as a consequential sub-rate sink allows it to decode r_t symbols with each network use. Since the network messages under the network code represented by B are elements of the field F, each symbol is represented by

bits, meaning that the communication rate to t as a consequential sub-rate sink is bits per network use.

2) Considering t as a sink, a new linear multicast is calculated with T* sinks. In this linear multicast t decodes at most h_t symbols per network use. In this case, the symbols are elements of the field F' (F' > F), hence the communication rate to t is at most bits per

network use. Notably, that the network’s max-flow in this case is between s and

and may be smaller than h_t1 Thus, if then the number of decoded

bits per network use is higher when referring to t as a consequential sub-rate sink.

Note that, while using proposition 31 is straight-forward for a single consequential sub- rate sink, using it for more than one sink requires that the set of potential consequential sub-rate sinks satisfy the criterion that this set is fully sub-rate decodable.

FIG. 4 shows the function

known as the rate ratio bound, as a function of the number of sinks. As the requirement for the existence of a linear multicast is that for every T, the cardinality of the field to work with is the smallest prime number

greater than T. If the ratio is above the curve in FIG. 4, then considering t as a sink reduces

its communication rate as opposed to considering it as a sub-rate sink. As Shown in FIG. 4, some values of the rate ratio require

to be higher than others in order for sub-rate sink to be superior to standard sink designation.

Conclusions

This Example and the following Annex described and thoroughly studied Sub-rate coding. It amounts to network (pre)-coding at the source side and decoding of partial information by a set of sinks whose max-flow is smaller than the network operation rate. While this Example discussed a single-source, finite acyclic scalar network, the present embodiments also contemplate vector networks.

The sub-rate coding of the present embodiments methodology does not impact the transmission rate towards sinks whose max-flow permits full-rate decoding. This makes sub-rate coding a viable add-on to any network. Applications of sub-rate coding include any scenario that employs multicasting to communicate with different users experiencing different channel qualities, or otherwise when they require different volumes of the data. It is particularly useful when a small number of sinks have a wide dynamic range of max-flows.

This Example also described combinations of sub-rate coding with other LNCs, including combinations of sub-rate coding with static LNCs and with variable-rate LNCs. This Example further showed that sub-rate coding is advantageous when additional sinks are to be added to an existing network.

ANNEX

Following is a list of additional examples for possible types of GEMs (given a set of sinks). For each type of GEM set the values c

and are calculated, and then an exemplified vector i that satisfies

the FSRD theorem conditions (namely,

is provided, if exists.

Although the invention has been described in conjunction with specific embodiments thereof, it is evident that many alternatives, modifications and variations will be apparent to those skilled in the art. Accordingly, it is intended to embrace all such alternatives, modifications and variations that fall within the spirit and broad scope of the appended claims.

It is the intent of the applicant(s) that all publications, patents and patent applications referred to in this specification are to be incorporated in their entirety by reference into the specification, as if each individual publication, patent or patent application was specifically and individually noted when referenced that it is to be incorporated herein by reference. In addition, citation or identification of any reference in this application shall not be construed as an admission that such reference is available as prior art to the present invention. To the extent that section headings are used, they should not be construed as necessarily limiting. In addition, any priority document(s) of this application is/are hereby incorporated herein by reference in its/their entirety.

Claims

WHAT IS CLAIMED IS:

1. A method of transmitting input information in a communication network from a computing source node characterized by a transmission rate to each of a plurality of computing sink nodes, the method comprising: precoding the input information at the source node; transmitting the precoded information over the network to provide each of the plurality of sink nodes with a respective a sink input; at a sink node having a maximal rate of at least the source's transmission rate, decoding a respective sink input to extract the input information; and at a sink node having a maximal rate less than the source's transmission rate, decoding a respective sink input to extract a portion of the input information.

2. The method according to claim 1, wherein the communication network employs a multicast network code.

3. The method according to any of claims 1 and 2, wherein the source's transmission rate is constant.

4. The method according to any of claims 1 and 2, wherein the source's transmission rate varies.

5. The method according to claim 1, wherein the input information is represented by a vector and wherein said precoding comprises multiplying said vector by an invertible matrix.

6. The method according to any of claims 2-4, wherein the input information is represented by a vector and wherein said precoding comprises multiplying said vector by an invertible matrix.

7. The method according to claim 5, wherein said invertible matrix is an inverse of a matrix factorized out of a global encoding matrix of the network.

8. The method according to claim 6, wherein said invertible matrix is an inverse of a matrix factorized out of a global encoding matrix of the network.

9. The method according to claim 1, being executed for scalar network coding.

10. The method according to any of claims 2-8, being executed for scalar network coding.

11. The method according to claim 1, being executed for vector network coding.

12. The method according to any of claims 2-8, being executed for vector network coding.

13. The method according to claim 1, wherein said decoding of said respective sink input to extract said portion of the input information, is at a decoding rate that equals said maximal rate of said sink node.

14. The method according to any of claims 2-12, wherein said decoding of said respective sink input to extract said portion of the input information, is at a decoding rate that equals said maximal rate of said sink node.

15. The method according to claim 1, wherein said decoding of said respective sink input to extract said portion of the input information, is at a decoding rate that is less than said maximal rate of said sink node.

16. The method according to any of claims 2-12, wherein said decoding of said respective sink input to extract said portion of the input information, is at a decoding rate that is less than said maximal rate of said sink node.

17. The method according to claim 1, comprising, at an additional sink node having a maximal rate of at least the source's transmission rate, decoding a respective sink input to extract a portion of the input information.

18. The method according to any of claims 2-16, comprising, at an additional sink node having a maximal rate of at least the source's transmission rate, decoding a respective sink input to extract a portion of the input information.

19. The method according to claim 1, comprising, at an additional node Nf having a maximal rate of at least the source's transmission rate, and which is other than a sink node and other than the source, decoding input received at said additional node Nf to extract the input information, thereby virtually attributing sink properties to said additional node Nf.

20. The method according to any of claims 2-18, comprising, at an additional node Nf having a maximal rate of at least the source's transmission rate, and which is other than a sink node and other than the source, decoding input received at said additional node Nf to extract the input information, thereby virtually attributing sink properties to said additional node Nf.

21. The method according to claim 1, comprising, at an additional node N_s having a maximal rate of less than the source's transmission rate, and which is other than a sink node and other than the source, decoding input received at said additional node N_s to extract a portion of the input information, thereby virtually attributing sink properties to said additional node N_s.

22. The method according to any of claims 2-20, comprising, at an additional node N_s having a maximal rate of less than the source's transmission rate, and which is other than a sink node and other than the source, decoding input received at said additional node N_s to extract a portion of the input information, thereby virtually attributing sink properties to said additional node N_s.

23. A communication system, comprising: a computing source node, and a plurality of computing sink nodes deployed over an area remote from said computing source node, each of said source node and said computing sink nodes comprises a circuit for encoding and decoding information; wherein a circuit of said computing source node is characterized by a transmission rate, and wherein said plurality of computing sink nodes comprises at least one sink node of a first type that has a circuit characterized a maximal rate of at least the source's transmission rate, and at least one sink node of a second type that has a circuit characterized a maximal rate of less than the source's transmission rate; and wherein said circuit of said computing source node is configured to precode the input information, to transmit the precoded information over the network to provide each of the plurality of sink nodes with a respective a sink input, to transmit to a sink node of said first type a control signal causing a respective circuit of said sink node to decode a respective sink input to extract the input information, and to transmit to a sink node of said second type a control signal causing a respective circuit of said sink node to decode a respective sink input to extract a portion of the input information.

24. The system according to claim 23, employing a multicast network code.

25. The system according to any of claims 23 and 24, wherein the source's transmission rate is constant.

26. The system according to any of claims 23 and 24, wherein the source's transmission rate varies.

27. The system according to any of claims 23-26, wherein the input information is represented by a vector and wherein said said circuit of said computing source node is configured to multiply said vector by an invertible matrix.

28. The system according to claim 27, wherein said invertible matrix is an inverse of a matrix factorized out of a global encoding matrix of the network.

29. The system according to any of claims 23-28, employing scalar network coding.

30. The system according to any of claims 23-28, employing vector network coding.

31. The system according to any of claims 23-30, wherein said circuit of said source node is configured to transmit to said sink node of said second type a control signal causing said respective circuit of said sink node to decode at a decoding rate that equals said maximal rate of said sink node.

32. The system according to any of claims 23-30, wherein said circuit of said source node is configured to transmit to said sink node of said second type a control signal causing said respective circuit of said sink node to decode at a decoding rate that is less than said maximal rate of said sink node.

33. The system according to any of claims 23-32, comprising, an additional sink node having a circuit characterized by a maximal rate of at least the source's transmission rate, wherein said circuit of said source node is configured to transmit to said additional sink node a control signal causing said circuit of said additional sink node to decode a respective sink input to extract a portion of the input information.

34. The system according to any of claims 23-33, comprising, an additional node Nf, other than a sink node and other than said source, said additional node Nf, having a circuit characterized by a maximal rate of at least the source's transmission rate, wherein said circuit of said source node is configured to transmit to said additional sink node Nf a control signal causing said circuit of said additional sink node Nf to decode input received at said additional node Nf to extract the input information, thereby virtually attributing sink properties to said additional node N_f.

35. The system according to any of claims 23-33, comprising, an additional node N_s, other than a sink node and other than said source, said additional node N_s, having a circuit characterized by a maximal rate of less than the source's transmission rate, wherein said circuit of said source node is configured to transmit to said additional sink node N_s a control signal causing said circuit of said additional sink node N_s to decode input received at said additional node N_s to extract a portion of the input information, thereby virtually attributing sink properties to said additional node N_s.