Decoder Design And Optimization Of Distributed Arithmetic Code

Distributed source coding is based on the Slepian-Wolf theory and the Wyner-Ziv theory,which is one of the hot research directions in coding field.Distributed arithmetic coding is a coding scheme which is based on the fundamental theory of distributed source coding.It introduces the arithmetic coding as the core of the coding and the decoding.It has been widely recognized and applied,since it shows the capability closed to the compression limit when dealing with small chunks of data.Due to the existence of stack areas,distributed arithmetic coding will form an incomplete binary decoding tree as the progress of the decoding.The traditional distributed arithmetic coding scheme is realized by the breadth-first search.The H-distance between the minimum full distance and the side information is unknown before reaching to the leaf node.Therefore,a large number of nodes need to be accessed in order to realize the full search of the decode tree.Meanwhile,in order to prevent overflow,the decoder needs to allocate space for the end nodes of all the paths,so that the RAM cannot be released until the coding is finished,which is one of the reasons causing a waste of resources.In order to solve this problem,the depth-first decoder will be introduced in this paper,which would make up the deficiency of the traditional coders.The main research contents of this paper are as follows:(1)Realization of traditional distributed arithmetic code codec.Source sequence input is compressed and coded by updating upper and lower bounds to select a numerical value in the final interval as a encoding result.The traditional decoder design scheme is realized by using the breadth-first algorithm to traverse the binary tree which is formed by decoding and select the path with the minimum distance between the edge information as the final decoding results.Besides,distributed arithmetic code performance is analyzed by using the codebook cardinality spectrum.(2)The design of depth-first decoder.The depth-first algorithm is used to traverse the binary tree formed by decoding.When entering the stack area,the branch with the larger path metric is chosen to search continuously and the branch with the smaller path metric enters the suspension queue until this queue becomes empty.Then we output the path which has the minimum distance with the side information as the decoding results.This paper evaluates the distributed arithmetic code decoder based on the depth-first algorithm from two aspects.The experimental results show that the depth-first decoder can achieve full search of decode trees by visiting some parts of the nodes.Meanwhile,the depth-first decoding complexity increases exponentially with the growth of the tail length,and the number of nodes generated by decoding also increases exponentially with the increase of code length.The specialization of the depth-first decoding is that the decoding complexity can be decreased by improving the quality of side information.The higher the quality of the side information has,the less complexity of the decoding will be.By comparing the depth-first decoder and the breadth-first decoder,This paper analyzes that the depth-first decoder shows better performance than the breadth-first decoder in dealing with short codes and mid-codes,and the situation of the better edge information quality.(3)Derivation of the path metric formula.When the decoder enters into the stack,or memory overflow needs to be cut,we need to use the path metric formula to calculate the importance of the branch.Unlike the traditional decoders,the depth-first decoder path metric not only requires the overall metric of each path but also need to consider the factor of the code length.In this paper,the full path metric of depth-first decoder is deduced by using the research results of the codebook cardinality spectrum.