Network coding: Is zero error always possible?

M. Langberg, M. Effros

פרסום מחקרי: פרק בספר / בדוח / בכנספרסום בספר כנסביקורת עמיתים

תקציר

In this work we study zero vs. ε-error capacity in network coding instances. For multicast network coding it is well known that all rates that can be delivered with arbitrarily small error probability can also be delivered with zero error probability; that is, the ε-error multicast capacity region and zero-error multicast capacity region are identical. For general network coding instances in which all sources originate at the same source node, Chan and Grant recently showed [ISIT 2010] that, again, ε-error communication has no rate advantage over zero-error communication. We start by revisiting the setting of co-located sources, where we present an alternative proof to that given by Chan and Grant. While the new proof is based on similar core ideas, our constructive strategy complements the previous argument. We then extend our results to the setting of index coding, which is a special and representative form of network coding that encapsulates the "source coding with side information" problem. Finally, we consider the "edge removal" problem (recently studied by Jalali, Effros, and Ho in [Allerton 2010] and [ITA 2011]) that aims to quantify the loss in capacity associated with removing a single edge from a given network. Using our proof for co-located sources, we tie the "zero vs. ε-error" problem in general network coding instances with the "edge removal" problem. Loosely speaking, we show that the two problem are equivalent.

שפה מקוריתאנגלית
כותר פרסום המארח2011 49th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2011
עמודים1478-1485
מספר עמודים8
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - 2011
אירוע2011 49th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2011 - Monticello, IL, ארצות הברית
משך הזמן: 28 ספט׳ 201130 ספט׳ 2011

סדרות פרסומים

שם2011 49th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2011

כנס

כנס2011 49th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2011
מדינה/אזורארצות הברית
עירMonticello, IL
תקופה28/09/1130/09/11

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'Network coding: Is zero error always possible?'. יחד הם יוצרים טביעת אצבע ייחודית.

פורמט ציטוט ביבליוגרפי