Throughput Bound of XOR Coded Wireless Multicasting to Three Clients
Qureshi, Malik · cs.NI,cs.IT,math.IT · 2015-12-16 · 原文
It is a well-known result that constructing codewords over GF(2) to minimize the number of transmissions for a single-hop wireless multicasting is an NP-complete problem. Linearly independent codewords can be constructed in polynomial time for all the n clients, known as maximum distance separable (MDS) code, when the finite field size q is larger than or equal to the number of clients, q\geq n. In this paper we quantify the exact minimum number of transmissions for a multicast network using erasure code when q=2 and n=3, such that q<n. We first show that the use of Markov chain model to derive the minimum number of transmissions for such a network is limited for very small number of input packets. We then use combinatorial approach to derive an upper bound on the exact minimum number of transmissions. Our results show that the difference between the expected number of transmissions using XOR coding and MDS coding is negligible for n=3.
讲义
讲义·推断 依据「原文」自动生成的结构化摘要（推断），非原文表述；以原文为准。
1. 人话版
It is a well-known result that constructing codewords over GF(2) to minimize the number of transmissions for a single-hop wireless multicasting is an NP-complete problem.
Linearly independent codewords can be constructed in polynomial time for all the n clients, known as maximum distance separable (MDS) code, when the finite field size q is larger than or equal to the number of clients, q\geq n.
2. 领域脉络
本文类目：cs.NI、cs.IT、math.IT，属于其所在研究脉络的最新进展。
3. 机制拆解
We then use combinatorial approach to derive an upper bound on the exact minimum number of transmissions.
4. 证据与数字
In this paper we quantify the exact minimum number of transmissions for a multicast network using erasure code when q=2 and n=3, such that q<n.
Our results show that the difference between the expected number of transmissions using XOR coding and MDS coding is negligible for n=3.
5. 反例与边界
We first show that the use of Markov chain model to derive the minimum number of transmissions for such a network is limited for very small number of input packets.
6. 跨领域连接与意外收获
横跨 3 个类目（cs.NI、cs.IT、math.IT），关注其在你兴趣板块间的迁移面。
7. 可复用方法
把本文机制与你手头项目对照，找一个两周内能验证的最小实验。
8. 术语表
精读时把不熟的术语记入此处，作为下次回忆的锚点。