Capacity of Sum-Networks for Different Message Alphabets

Ardhendu S. Tripathy; Aditya Ramamoorthy

doi:10.1109/ISIT.2015.7282526

Capacity of Sum-Networks for Different Message Alphabets

Ardhendu S. Tripathy
, Aditya Ramamoorthy

Computer Science

Research output: Contribution to journal › Article › peer-review

Abstract

A sum-network is a directed acyclic network in which all terminal nodes demand the 'sum' of the independent information observed at the source nodes. Many characteristics of the well-studied multiple-unicast network communication problem also hold for sum-networks due to a known reduction between instances of these two problems. Our main result is that unlike a multiple unicast network, the coding capacity of a sum-network is dependent on the message alphabet. We demonstrate this using a construction procedure and show that the choice of a message alphabet can reduce the coding capacity of a sum-network from 1 to close to 0.

Original language	American English
Journal	IEEE International Symposium on Information Theory - Proceedings
DOIs	https://doi.org/10.1109/ISIT.2015.7282526
State	Published - Sep 28 2015

Keywords

Capacity
Function Computation
Linear Network Coding
Network Coding
Sum-Network

Disciplines

Computer Sciences

Access to Document

10.1109/ISIT.2015.7282526License: Unspecified

https://doi.org/10.1109/ISIT.2015.7282526

Cite this

@article{5f81c2950bc3424cbbdd1b5a510ba2a7,

title = "Capacity of Sum-Networks for Different Message Alphabets",

abstract = " A sum-network is a directed acyclic network in which all terminal nodes demand the 'sum' of the independent information observed at the source nodes. Many characteristics of the well-studied multiple-unicast network communication problem also hold for sum-networks due to a known reduction between instances of these two problems. Our main result is that unlike a multiple unicast network, the coding capacity of a sum-network is dependent on the message alphabet. We demonstrate this using a construction procedure and show that the choice of a message alphabet can reduce the coding capacity of a sum-network from 1 to close to 0.",

keywords = "Capacity, Function Computation, Linear Network Coding, Network Coding, Sum-Network",

author = "Tripathy, \{Ardhendu S.\} and Aditya Ramamoorthy",

year = "2015",

month = sep,

day = "28",

doi = "10.1109/ISIT.2015.7282526",

language = "American English",

journal = "IEEE International Symposium on Information Theory - Proceedings",

}

TY - JOUR

T1 - Capacity of Sum-Networks for Different Message Alphabets

AU - Tripathy, Ardhendu S.

AU - Ramamoorthy, Aditya

PY - 2015/9/28

Y1 - 2015/9/28

N2 - A sum-network is a directed acyclic network in which all terminal nodes demand the 'sum' of the independent information observed at the source nodes. Many characteristics of the well-studied multiple-unicast network communication problem also hold for sum-networks due to a known reduction between instances of these two problems. Our main result is that unlike a multiple unicast network, the coding capacity of a sum-network is dependent on the message alphabet. We demonstrate this using a construction procedure and show that the choice of a message alphabet can reduce the coding capacity of a sum-network from 1 to close to 0.

AB - A sum-network is a directed acyclic network in which all terminal nodes demand the 'sum' of the independent information observed at the source nodes. Many characteristics of the well-studied multiple-unicast network communication problem also hold for sum-networks due to a known reduction between instances of these two problems. Our main result is that unlike a multiple unicast network, the coding capacity of a sum-network is dependent on the message alphabet. We demonstrate this using a construction procedure and show that the choice of a message alphabet can reduce the coding capacity of a sum-network from 1 to close to 0.

KW - Capacity

KW - Function Computation

KW - Linear Network Coding

KW - Network Coding

KW - Sum-Network

UR - https://scholarsmine.mst.edu/comsci_facwork/1006

UR - https://doi.org/10.1109/ISIT.2015.7282526

U2 - 10.1109/ISIT.2015.7282526

DO - 10.1109/ISIT.2015.7282526

M3 - Article

JO - IEEE International Symposium on Information Theory - Proceedings

JF - IEEE International Symposium on Information Theory - Proceedings

ER -

Capacity of Sum-Networks for Different Message Alphabets

Abstract

Keywords

Disciplines

Access to Document

Other files and links

Fingerprint

Cite this