Content deleted Content added
Extensive cleanup in math notation and punctuation. |
→Network coding: more of that |
||
Line 4:
Let <math>G = (V, E)</math> be a [[directed graph]] where <math>V</math> is a set, whose elements are called vertices or [[Node (networking)|node]]s, and <math>E</math> is a set of [[ordered pair]]s of vertices, called arcs, directed edges, or arrows. A source <math>s \in V</math> wants to transmit a file <math>D</math> to a set <math>T \subseteq V</math> of the vertices. One chooses a [[vector space]] <math>W/\mathbb{F}_p</math>(say of dimension <math>d</math>), where <math>p</math> is a prime, and views the data to be transmitted as a bunch of vectors <math>w_1 ,\ldots , w_k \in W</math>. The source then creates the augmented vectors <math>v_1,\ldots , v_k</math> by setting <math> v_i = (0, \ldots , 0, 1, \ldots , 0, w_{i_1}, \ldots , w{i_d})</math> where <math>w_{i_j}</math> is the <math>j</math>-th coordinate of the vector <math>w_i</math>. There are <math>(i-1)</math> zeros before the first '1' appears in <math>v_i</math>. One can assume without loss of generality that the vectors <math>v_i</math> are [[Linear independence|linearly independent]]. We denote the [[linear subspace]] (of <math>\mathbb{F}_p^{k+d}</math> ) spanned by these vectors by <math>V</math> . Each outgoing edge <math>e \in E</math> computes a linear combination, <math>y(e)</math>, of the vectors entering the vertex <math>v = in(e)</math> where the edge originates, that is to say
: <math>y(e) = \sum_{f:\mathrm{out}(f)=v}(m_e(f)y(f))</math>
where <math>m_e(f) \in \mathbb{F}_p</math>. We consider the source as having <math>k</math> input edges carrying the <math>k</math> vectors <math>w_i</math>. By [[Mathematical induction|induction]], one has that the vector <math>y(e)</math> on any edge is a linear combination <math>y(e) = \sum_{1 \le i \le k}(g_i(e)v_i)</math> and is a vector in <math>V</math> . The k-dimensional vector <math>g(e) = (g_1(e), \ldots , g_k(e))</math> is simply the first ''k'' coordinates of the vector <math>y(e)</math>. We call the [[Matrix (mathematics)|matrix]] whose rows are the vectors <math>g(e_1), \ldots , g(e_k)</math>, where <math>e_i</math> are the incoming edges for a vertex <math>t \in T</math>, the global encoding matrix for <math>t</math> and denote it as <math>G_t</math>. In practice the encoding vectors are chosen at random so the matrix <math>G_t</math> is invertible with high probability. Thus any receiver, on receiving <math>y_1, \ldots , y_k</math> can find <math>w_1,\ldots ,w_k</math> by solving
| |||