EO 3240 Fundamentals of Network Coding (10 Credits)

Registration to the course leader

 

       Dr. Ming Xiao: ming.xiao@ee.kth.se

 

       Teaching assistant:  Mr. Sheng Huang: sheng.huang@ee.kth.se

 

 

Notice board (NEW):

 

1.       The deadline of homework is May 1, 2012. No extension.

2.       The deadline of the final report is May 15, No extension. The final report should be a topic report related to network coding. It is about 4—6 pages, two column IEEE conference format, font size 10 PT, either your own work or a literature survey or some research ideas.

3.       Presentation will be before April 15 or after May 15, The latest date is May 22. 20-30 minutes. The topic should be approved by teacher in advance.

 

Abstract (Kort beskrivning)

 

Network coding is a relatively new cross-disciplined research area. It involves the areas of coding theorem, information theory, graph theory and networking. New applications of network coding have been emerging substantially for the recent years in the area of wireless communications, internetworking, content distribution, security, storage etc. The basic idea of network coding is to allow nodes in a network to compute functions of their incoming information messages before transmitting them further. Thus it is more general than routing which is currently the dominant network information transfer paradigm. It turns out that the use of network coding can provably improve network throughput and robustness. The objective of this course is to understand the basics of network coding theory and its applications.

 

 

Keywords

 

Network Coding; Min-cut Max-flow; Existence and Field Size; Code Construction; Complexity;

 

Learning outcomes (Läranda mål)

 

After the course, the students should be able to:

(1). Know the max-achievable flow for different network setups.

(2). Know the basic properties of network coding.

(3). Know the existence and construction of network codes.

(4). Know the codes for acyclic or cyclic networks.

(5). Master the algebraic forms of network coding.

(6). Have solid knowledge on coherent and non-coherent network codes.

(7). Know the different application approaches of network coding.

 

 

Course main content (Kursens huvudsakliga innehåll)

 

This course shall give a rigorous introduction on the fundamentals of network coding. The main contents are on the information theoretic and algebraic structure of network coding. We shall also study the existence, the complexity, the construction, and the properties of network codes. The recent topics of subspace network codes will be discussed.

 

Course disposition

 

Lectures, homework and final paper presentation

 

Requirement for final grade (Krav för slutbetyg)

 

The lecture is given once per week.

     The final results are based on homework (64%) and the final report (26%) and presentation (10%). 

    

     Grade:   

                 Each home work is has the grade 0 – 8. If you miss the deadline, you will be

                 marked as -2.

                

 Final report should be related to the students’ own research background. That is, how the network coding can be (potentially) applied in your own area. What is the state of arts? Are there potentially some new area? Why not? The minimum requirement is 2000 Words.

 

                Presentation: Based on your report or a selected paper by the teacher.

        

 

                Ph.D students should have the overall grade 80% to pass.

 

Course literature

 

Textbook

 

1.      Raymond Yeung, “Information Theory and Network Coding”, Springer Publisher, 2008.

2.      Christina Fragouli and Emina Soljanin, “Network Coding Fundamentals”, NOW publisher, 2007.

 

 Papers:

 

1.       R. Koetter and M. Medard, “An algebraic approach to network coding,” IEEE/ACM Transactions on networking.

2.      T. Ho, M. Médard, R. Koetter, D. Karger, M. Effros, J. Shi, and B. Leong, “A random linear network coding approach to multicast,” IEEE Trans. Inf. Theory, vol. 52, no. 10, pp. 4413–4430, Oct. 2006.

3.      R. Koetter, F. R. Kschischang: “Coding for Errors and Erasures in Random Network Coding,” IEEE Transactions on Information Theory 54(8): 3579-3591 (2008)   

 

Lectures outline (Preliminary, may be updated)

 

1.     Introduction and Main theorem of network multicast.

2.      Theoretical framework of network coding I

3.      Theoretical framework of network coding II

4.      Throughput benefits of network coding.

5.      Network coding design/construction.

6.      Network with delay and cycles.

7.      Coding Complexity.

8.      Subspace network coding.

 

Homework

 

Homework submitted to TA (or Dr. Xiao)

 

Homework 1, Raymond Yeung, Chapter 17, Questions 1, 2, 3.

Homework 2, Raymond Yeung, Chapter 19, Questions, 1, 2, 3, 4.

Homework 3, Raymond Yeung, Chapter 18, Questions: 2, 3, 4. 

Extra question: Find a scenario (other than the example in the class), such that vector coding has higher rate than scalar coding (You can get extra 3 points if solve the question; If cannot solve, you point will not be reduced from HW 3).

Homework 4.

Homework 5

Homework 6, Raymond Yeung, Chapter 20, Questions 1, 3, 5.

Homework 7

Homework 8

 

 

Preliminary Scheduling

 

    

 

 

 

Address: School of Electrical Engineering Communication Theory Royal Institute of Technology (KTH) Osquldas vg 10 SE-100 44 Stockholm		Office: KTH Stockholm (main campus) Osquldas vg 10 Floor 4, Room B:420
Phone: Fax:	+46-(0)8-790 6577 +46-(0)8-790 7260	E-mail & URL: ming.xiao@ee.kth.se http://www.s3.kth.se/~mingx