Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR03-033 | 6th May 2003 00:00

Bounds on Linear Codes for Network Multicast


Authors: Meir Feder, Dana Ron, Ami Tavory
Publication: 12th May 2003 20:00
Downloads: 1766


Traditionally, communication networks are composed of
routing nodes, which relay and duplicate data. Work in
recent years has shown that for the case of multicast, an
improvement in both rate and code-construction complexity can be
gained by replacing these routing nodes by linear coding
nodes. These nodes transmit linear combinations of the inputs
transmitted to them.
In this work, we deal with bounds on the alphabet size of
linear codes for multicast. We show both lower and upper bounds as
a function of sink-set size and graph topology. We show that these
bounds apply, as well, to a special case of multicast,
static broadcast. We also show how node-memory addition
can increase the effective alphabet-size available for coding.


Comment #1 to TR03-033 | 23rd June 2003 16:09

Comment Comment on: TR03-033

Comment #1
Authors: Ami Tavory, Meir Feder, Dana Ron
Accepted on: 23rd June 2003 16:09
Downloads: 1508


We have included a section on the number of nodes in which coding
is required, as a function of the number of terminals and their rates.

ISSN 1433-8092 | Imprint