| Session: | 1.1.3 - Network Coding I |
| Session Time: | Monday, July 10, 09:40 - 11:00 |
| Paper Time: | Monday, July 10, 09:40 - 10:00 |
| Title: |
Low Complexity Encoding for Network Codes |
| Authors: |
Sidharth Jaggi; Massachusetts Institute of Technology | | |
| | Yuval Cassuto; California Institute of Technology | | |
| | Michelle Effros; California Institute of Technology | | |
| 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 block-length 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. |
