Random linear network coding is widely proposed as the solution for practical network coding applications due to the robustness to random packet loss, packet delays as well as network topology and capacity changes. In order to implement random linear network coding in practical scenarios where the encoding and decoding methods perform efficiently, the computational complex coding algorithms associated with random linear network coding must be overcome. This research contributes to the field of practical random linear network coding by presenting new, low complexity coding algorithms with low decoding delay. In this thesis we contribute to this research field by building on the current solutions available in the literature through the utilisation of familiar coding schemes combined with methods from other research areas, as well as developing innovative coding methods. We show that by transmitting source symbols in predetermined and constrained patterns from the source node, the causality of the random linear network coding network can be used to create structure at the receiver nodes. This structure enables us to introduce an innovative decoding scheme of low decoding delay. This decoding method also proves to be resilient to the effects of packet loss on the structure of the received packets. This decoding method shows a low decoding delay and resilience to packet erasures, that makes it an attractive option for use in multimedia multicasting. We show that fountain codes can be implemented in RLNC networks without changing the complete coding structure of RLNC networks. By implementing an adapted encoding algorithm at strategic intermediate nodes in the network, the receiver nodes can obtain encoded packets that approximate the degree distribution of encoded packets required for successful belief propagation decoding. Previous work done showed that the redundant packets generated by RLNC networks can be used for error detection at the receiver nodes. This error detection method can be implemented without implementing an outer code; thus, it does not require any additional network resources. We analyse this method and show that this method is only effective for single error detection, not correction. In this thesis the current body of knowledge and technology in practical random linear network coding is extended through the contribution of effective decoding techniques in practical network coding networks. We present both analytical and simulation results to show that the developed techniques can render low complexity coding algorithms with low decoding delay in RLNC networks. / Thesis (PhD (Computer Engineering))--North-West University, Potchefstroom Campus, 2013

Random linear network coding is widely proposed as the solution for practical network coding applications due to the robustness to random packet loss, packet delays as well as network topology and capacity changes. In order to implement random linear network coding in practical scenarios where the encoding and decoding methods perform efficiently, the computational complex coding algorithms associated with random linear network coding must be overcome. This research contributes to the field of practical random linear network coding by presenting new, low complexity coding algorithms with low decoding delay. In this thesis we contribute to this research field by building on the current solutions available in the literature through the utilisation of familiar coding schemes combined with methods from other research areas, as well as developing innovative coding methods. We show that by transmitting source symbols in predetermined and constrained patterns from the source node, the causality of the random linear network coding network can be used to create structure at the receiver nodes. This structure enables us to introduce an innovative decoding scheme of low decoding delay. This decoding method also proves to be resilient to the effects of packet loss on the structure of the received packets. This decoding method shows a low decoding delay and resilience to packet erasures, that makes it an attractive option for use in multimedia multicasting. We show that fountain codes can be implemented in RLNC networks without changing the complete coding structure of RLNC networks. By implementing an adapted encoding algorithm at strategic intermediate nodes in the network, the receiver nodes can obtain encoded packets that approximate the degree distribution of encoded packets required for successful belief propagation decoding. Previous work done showed that the redundant packets generated by RLNC networks can be used for error detection at the receiver nodes. This error detection method can be implemented without implementing an outer code; thus, it does not require any additional network resources. We analyse this method and show that this method is only effective for single error detection, not correction. In this thesis the current body of knowledge and technology in practical random linear network coding is extended through the contribution of effective decoding techniques in practical network coding networks. We present both analytical and simulation results to show that the developed techniques can render low complexity coding algorithms with low decoding delay in RLNC networks. / Thesis (PhD (Computer Engineering))--North-West University, Potchefstroom Campus, 2013

One of the most important technologies used in modern communication systems is channel coding. Channel coding dates back to a paper published by Shannon in 1948 [1] entitled “A Mathematical Theory of Communication”. The basic idea behind channel coding is to send redundant information (parity) together with a message to make the transmission more error resistant. There are different types of codes that can be used to generate the parity required, including block, convolutional and concatenated codes. A special subclass of codes consisting of the codes mentioned in the previous paragraph, is sparse graph codes. The structure of sparse graph codes can be depicted via a graphical representation: the factor graph which has sparse connections between its elements. Codes belonging to this subclass include Low-Density-Parity-Check (LDPC) codes, Repeat Accumulate (RA), Turbo and fountain codes. These codes can be decoded by using the belief propagation algorithm, an iterative algorithm where probabilistic information is passed to the nodes of the graph. This dissertation focuses on noisy decoding of fountain codes using belief propagation decoding. Fountain codes were originally developed for erasure channels, but since any factor graph can be decoded using belief propagation, noisy decoding of fountain codes can easily be accomplished. Three fountain codes namely Tornado, Luby Transform (LT) and Raptor codes were investigated during this dissertation. The following results were obtained: <ol> <li>The Tornado graph structure is unsuitable for noisy decoding since the code structure protects the first layer of parity instead of the original message bits (a Tornado graph consists of more than one layer).</li> <li> The successful decoding of systematic LT codes were verified.</li> <li>A systematic Raptor code was introduced and successfully decoded. The simulation results show that the Raptor graph structure can improve on its constituent codes (a Raptor code consists of more than one code).</li></ol> Lastly an LT code was used to replace the convolutional incremental redundancy scheme used by the 2G mobile standard Enhanced Data Rates for GSM Evolution (EDGE). The results show that a fountain incremental redundancy scheme outperforms a convolutional approach if the frame lengths are long enough. For the EDGE platform the results also showed that the fountain incremental redundancy scheme outperforms the convolutional approach after the second transmission is received. Although EDGE is an older technology, it still remains a good platform for testing different incremental redundancy schemes, since it was one of the first platforms to use incremental redundancy. / Dissertation (MEng)--University of Pretoria, 2008. / Electrical, Electronic and Computer Engineering / MEng / unrestricted