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.

See Usage Policy.


Use this Persistent URL to link to this item:


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
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:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:7296
Deposited By: Archive Administrator
Deposited On:26 Jan 2007
Last Modified:08 Nov 2021 20:41

Repository Staff Only: item control page