Network Coding Theory
Network Coding Theory
Raymond W. Yeung
The Chinese University of Hong Kong
Hong Kong, China
whyeung@ie.cuhk.edu.hk
Shuo-Yen Robert Li
The Chinese University of Hong Kong
Hong Kong, China
bob@ie.cuhk.edu.hk
Ning Cai
Xidian University
Xi’an, Shaanxi, China
caining@mail.xidian.edu.cn
Zhen Zhang
University of Southern California
Los Angeles, CA, USA
zzhang@milly.usc.edu
Boston – Delft
Foundations and Trends
R
in
Communications and Information Theory
Published, sold and distributed by:
now Publishers Inc.
PO Box 1024
Hanover, MA 02339
USA
Tel. +1-781-985-4510
www.nowpublishers.com
sales@nowpublishers.com
Outside North America:
now Publishers Inc.
PO Box 179
2600 AD Delft
The Netherlands
Tel. +31-6-51115274
A Cataloging-in-Publication record is available from the Library of Congress
The preferred citation for this publication is R.W. Yeung, S.-Y.R. Li, N. Cai, and
Z. Zhang, Network Coding Theory, Foundation and Trends
R
in Communications
and Information Theory, vol 2, nos 4 and 5, pp 241–381, 2005
Printed on acid-free paper
ISBN: 1-933019-24-7
c
2006 R.W. Yeung, S.-Y.R. Li, N. Cai, and Z. Zhang
All rights reserved. No part of this publication may be reproduced, stored in a retrieval
system, or transmitted in any form or by any means, mechanical, photocopying, recording
or otherwise, without prior written permission of the publishers.
Photocopying. In the USA: This journal is registered at the Co pyright Clearance Cen-
ter, Inc., 222 Rosewood Drive, Danvers, MA 01923. Authorization to photocopy items for
internal or personal use, or the internal or personal use of specific clients, is granted by
now Publish ers Inc for users registered with the Copyright Clearance Center (CCC). The
‘services’ for users can be found on the internet at: www.copyright.com
For those organizations that have been granted a photo c opy license, a separate system
of payment has been arranged. Authorization does not extend to other kinds of copy-
ing, such as that for general distribution, for advertising or promotional purposes, for
creating new collective works, or for resale. In the rest of th e world: Permission to pho-
tocopy must be obtained from the copyright owner. Please apply to now Publishers Inc.,
PO Box 1024, Hanover, MA 02339, USA; Tel. +1 781 871 0245; www.nowpublishers.com;
sales@nowpublishers.com
now Publishers Inc. has an exclusive license to publish this material worldwide. Permission
to use this content must be obtained from the copyright license holder. Please apply to now
Publishers, PO Box 179, 2600 AD Delft, The Netherlands, www.nowpublishers.com; e-mail:
sales@nowpublishers.com
Contents
1 Introduction 1
1.1 A historical perspective 1
1.2 Some examples 4
I SINGLE SOURCE 9
2 Acyclic Networks 11
2.1 Network code and linear network code 12
2.2 Desirable properties of a linear network code 18
2.3 Existence and construction 25
2.4 Algorithm refinement for linear multicast 40
2.5 Static network codes 44
3 Cyclic Networks 51
3.1 Non-equivalence between local and global descriptions 52
3.2 Convolutional network code 55
3.3 Decoding of convolutional network code 67
4 Network Coding and Algebraic Coding 73
v
