NetworkCodingforErrorCorrectionandSecurity.pptVIP

Network Coding forError Correction and Security Raymond W. Yeung The Chinese University of Hong Kong Outline Introduction Network Coding vs Algebraic Coding Network Error Correction Secure Network Coding Applications of Random Network Coding in P2P Concluding Remarks Introduction A Network Coding Example The Butterfly Network A Network Coding Example with Two Sources Wireless/Satellite Application Two Themes of Network Coding When there is 1 source to be multicast in a network, store-and-forward may fail to optimize bandwidth. When there are 2 or more independent sources to be transmitted in a network (even for unicast), store-and-forward may fail to optimize bandwidth. In short, Information is NOT a commodity! Model of a Point-to-Point Network A network is represented by a graph G = (V,E) with node set V and edge (channel) set E. A symbol from an alphabet F can be transmitted on each channel. There can be multiple edges between a pair of nodes. Single-Source Network Coding The source node s generates an information vector x = (x1 x2 … xk) ? Fk. What is the condition for a node t to be able to receive the information vector x? Max-Flow Bound. If maxflow(t) k, then node t cannot possibly receive x. The Basic Results If network coding is allowed, a node t can receive the information vector x iff maxflow(t) ≥ k i.e., the max-flow bound can be achieved simultaneously by all such nodes t. (Ahlswede et al. 00) Moreover, this can be achieved by linear network coding for a sufficiently large base field. (Li, Y and Cai, Koetter and Medard, 03) Global Encoding Kernels of a Linear Network Code Recall that x = (x1 x2 … xk) is the multicast message. For each channel e, assign a column vector fe such that the symbol sent on channel e is x fe. The vector fe is called the global encoding kernel of channel e. The global encoding kernel of a channel is analogous to a column in the generator matrix of a classical block code. The global encoding kernel of an output channel a