Research On Encoding And Decoding Algorithms Of Convolutional Network Error-correction Coding

Network coding,as an information exchange technology combining routing and coding,has great advantages in throughput,load balance,reliability,security and low complexity.However,during the data transmission,various network errors may occur because of various factors such as noise,long distance,man-made,etc.In order to ensure the reliability of the network,we study the convolutional codes for error correction in convolutional network coding or random convolutional network coding.The convolutional code produced at each sink node is referred to as the convolutional network error correction code(CNECC).Since network errors may disperse or neutralize due to network coding,decoding cannot be done at sink nodes merely based on the minimum Hamming distance between the received and sent sequence.A Viterbi-like decoding algorithm based on the minimum network error weight is proposed,then applied to convolutional network coding and random convolutional network coding.(1)We consider the problem of error correction using a convolutional code at the source of a delay-invariant,single source,multicast network with a proper network code.we first give an equivalent maximum likelihood(ML)decoding principle,termed the minimum-network-error-weight principle,that finds the edge error sequence with the minimum weight.Then,as fundamental decoding principle,as long as the intersection of the the sub-codeword s-pace and the error response space only contains the null vector,we will be able to achieve the perfect error correction under the ML decoding rule.However,this fundamental prin-ciple may not be achievable in reality.Instead,we consider a suboptimal decoding rule by assuming that errors always occur sooner than later.In a much simpler scenario where error vectors are most likely separated by a certain number of network uses,we propose a Viterbi-type algorithm that finds the most likely error vector in each decoding window of length no greater than the minimum gap of error vectors.Since our Viterbi-type algorithm is equipped with a decoding window,the decoding process is also named as the sliding window decod-ing.Unlike the previous work,our algorithm can directly work at each sink node and does not require computing the inverse network transfer matrix.Finally,the performance of the decoding algorithm is verified through simulation.(2)To address unknown topology and delay in practice networks,an adaptive construction and decoding for random convolutional network error correction coding(RCNECC)are also considered in this thesis.First,we randomly choose local encoding kernel(LEK)for each node over a small field,and the global encoding kernel(GEK)is put in the head of packets.The length of LEK is increased each time until all the sink nodes have the transfer matrix with full rank.Then,the maximum weight of equivalent errors at source node is estimated for the set of possible network errors,and an error correction code able to correct the errors is used before the messages are sent to the network.Further,we extend the Viterbi-like decoding algorithm based on the minimum network-error weight of combination errors to random coding and field By subtracting the effect of the decoded signal and the estimated network-error,we update the decoding sequence.The algorithm can correct any network error within the capability of RCNECC,and the distributed decoding of RCNECC has low complexity and decoding delay.Finally,we present an example to show how the construction and decoding algorithm works over Fq.