# Source Symbol Purging-Based Distributed Conditional Arithmetic Coding
## 3 The Calculation of the Posterior Probability  
According to the theory of the context-based arithmetic coding, only if the decoder uses the same conditional probability distributions in the context model and follows the same updating rules as that of the encoder, can the source sequence \(X^{N}\) be recovered correctly using the received codeword \(CX^{N}\). Since only part of the symbols in \(X^{N}\) are encoded by an arithmetic encoder based on the context model, the remaining purged symbols are not encoded (they are still used as the context); it is impossible for the decoder to know the correct updating rules for those conditional probability distributions in the context model. Without the correctly updated context model, the decoded sequence from \(CX^{N}\) is erroneous and irrelevant to the original source sequence \(X^{N}\). However, with the help of the side information sequence, for moment \(i\), we can utilize the correlation between \(X^{i-1}\) and \(Y^{i-1}\) to estimate the source sequence \(X^{i-1}\) as accurately as possible such that the context model could be updated properly, and the correct symbol \(X_{i}\) could be decoded from \(CX^{i}\). To this end, since we have the side information sequence \(Y^{N}\), we can calculate the cumulative product of posterior probabilities of all estimated \(\hat{X}^{i-1}\) sequences, and use the one with the largest cumulative product of posterior probabilities as the estimate of \(X^{i-1}\). In DAC research [15], Formula (1) is usually used to calculate the cumulative product of posterior probabilities of each decoding path from moment 1 to  
Figure 4: A part of the decoding tree where \(x_{i}\) is a purged symbol. \[\Lambda=P(\hat{X}^{N}|Y^{N},CX^{N})=\prod_{i=1}^{N}P(\hat{X}_{i}=\hat{x}_{i}|Y_{i}=y _{i},CX^{i}) \tag{1}\]  
where \(\hat{X}^{N}\) represents one of the decoded symbol sequences in the decoding tree from moment 1 to \(N\), \(Y^{N}\) represents the corresponding sequence of side information \(Y\), \(CX^{N}\) is the SPDCAC encoder output codeword after encoding \(X^{N}\), and \(CX^{i}\) is the codeword received up to the moment \(i\). A virtual binary symmetric channel (BSC) is usually used in the DSC research to describe the correlation between any \(X_{i}\) and \(Y_{i}\) pair [24], the transition probability \(P(y_{i}|x_{i})\) of the channel measures the correlation between the two sources. A small transition probability represents the strong correlation between the \(X_{i}\) and \(Y_{i}\) pairs. Since BSC is a memoryless channel, the side information symbol \(Y_{i}\) is considered only related to the corresponding original source symbol \(X_{i}\), but not related to \(X_{i-1}\), \(X_{i+1}\), \(Y_{i-1}\) and \(Y_{i+1}\). However, this posterior probability calculation method only considers the correlation between the symbols of two sources at moment \(i\), but does not consider the situation of sources with memory. In the decoding process of SPDCAC, the correlation between adjacent symbols within the source sequence should also be used as an important part to determine whether the decoding result is correct. The conditional probability in the context model can be added to the posterior probability calculation as a means of using this correlation. Since the side information sequence \(y^{N}\) is known during the calculation of the posterior probability, the joint probability \(P(Y^{N}=y^{N})\) is considered as the prior probability of the side information sequence, and is also known and is a constant. \(CX^{N}\) is the unique codeword received by the decoder; it is fixed for all decoding branches in the decoding tree. Therefore, the probability \(P(CX^{N})\) is also considered as the prior probability of \(CX^{N}\) during the decoding process. From the perspective of the decoder, before the correct source sequence \(X^{N}\) is found, the codeword \(CX^{N}\) and the source sequence \(X^{N}\) are independent because the decoder does not know which path in the decoding tree corresponds to the correct source sequence \(X^{N}\).