CaltechAUTHORS
  A Caltech Library Service

Low Complexity Encoding for Network Codes

Jaggi, Sidharth and Cassuto, Yuval and Effros, Michelle (2006) Low Complexity Encoding for Network Codes. In: IEEE International Symposium on Information Theory (ISIT '06), Seattle, WA, 6-12 July 2006. IEEE , Los Alamitos, CA, pp. 40-44. ISBN 1-4244-0504-1. https://resolver.caltech.edu/CaltechAUTHORS:JAGisit06

[img]
Preview
PDF
See Usage Policy.

227Kb

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:JAGisit06

Abstract

In this paper we consider the per-node run-time complexity of network multicast codes. We show that the randomized algebraic network code design algorithms described extensively in the literature result in codes that on average require a number of operations that scales quadratically with the blocklength m of the codes. We then propose an alternative type of linear network code whose complexity scales linearly in m and still enjoys the attractive properties of random algebraic network codes. We also show that these codes are optimal in the sense that any rate-optimal linear network code must have at least a linear scaling in run-time complexity.


Item Type:Book Section
Related URLs:
URLURL TypeDescription
https://doi.org/10.1109/ISIT.2006.261594DOIUNSPECIFIED
ORCID:
AuthorORCID
Cassuto, Yuval0000-0001-6369-6699
Additional Information:© Copyright 2006 IEEE. Reprinted with permission. We thank Jehoshua Bruck and Alexander Sprintson for useful discussions and comments. [S.J. was] [s]upported by AFOSR FA9550-06-1-0155. [Y.C. was] [s]upported by the Lee Center for Advanced Networking and by NSF grant ANI-0322475.
Record Number:CaltechAUTHORS:JAGisit06
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:JAGisit06
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:7296
Collection:CaltechAUTHORS
Deposited By: Archive Administrator
Deposited On:26 Jan 2007
Last Modified:09 Mar 2020 13:18

Repository Staff Only: item control page