# Source Symbol Purging-Based Distributed Conditional Arithmetic Coding
## 2 Source Symbol Purging-Based Distributed Conditional Arithmetic Coding
### SPDCAC Decoding Process  
The SPDCAC decoder needs to use the received codeword to reconstruct the original source sequence as accurately as possible with the help of a side information sequence, which is correlated to the source sequence. The initial probability distribution used by the decoder must be the same as that of the encoder. The conditional probability distributions in the context model at the decoder need to synchronously perform the same counting and updating operations as what is performed at the encoder. The decoder must know the purging rate of the encoder. In the actual coding process, the purging rate can be preset to be the same in the encoder and the decoder. In the encoding process, those purged symbols are not encoded, but they are used as context conditions for the encoding of subsequent symbols. Therefore, the SPDCAC decoder cannot recover those purged symbols by directly decoding the codeword, and the context probability model of the decoder does not count those symbols. This will let the SPDCAC decoder use an incorrect probability distribution to decode the received codeword, the decoded result must be wrong. If a decoding error occurs during the decoding process, due to the error propagation characteristics of arithmetic coding, the decoding error will continue to appear in the subsequent decoding process, making the decoding completely fail. In order to decode successfully, the SPDCAC decoder has to recover those purged symbols according to the purging rate of the encoder. For the recovering of an unencoded symbol, the decoder must make assumptions about all possible symbols in this position. This means the decoding ambiguity phenomenon occurs. In the process of decoding a binary sequence, whenever the decoding ambiguity takes place, two possible decoding results will appear, the decoder has to use a binary decoding tree to record this event, and two new decoding branches are extended from the original decoding branch based on these two results (a new branch is added to the decoding tree). The decoder stores all possible decoding branches of the binary decoding tree, where each path in the tree represents a possible decoding output sequence. Figure 4 shows a part of the decoding tree where \(x_{i-1}\)\(\sim\)\(x_{i-3}\) are unambiguously decoded symbols in one of the branches in the decoding tree, and these symbols are encoded by the context-based arithmetic encoder, so they can be directly decoded at the decoder. \(x_{i}\) is a symbol that is 'purged' at the encoder. The decoder needs to assume two possible decoding results for \(x_{i}\) at this position, and based on these two results, independent decoding processes on their respective decoding branches are performed. Let \(x_{i}^{0}\) and \(x_{i}^{1}\) be the two possible decoding results of \(x_{i}\), the decoder can obtain two different decoding branches: \(x_{i}^{0},x_{i+1}^{0},\cdots\) and \(x_{i}^{1},x_{i+1}^{1},\cdots\). The decoding process of each decoding branch needs to be synchronized, which means that the decoder needs to simultaneously decode the symbols at: \(i,i+1,\cdots\) in two different branches. The specific decoding process can be described as follows:  
1. Decoding starts;
2. Determine whether the current decoding position \(i\) is less than or equal to the sequence length \(N\); if so, perform the operation: 1. Synchronously decode the \(i\) th symbol of all decoding branches that are still alive in the decoding tree: 1. If the symbol that needs to be decoded at the current position \(i\) is encoded at the encoder, the decoder can use the symbols at positions  
Figure 3: An example of SPDCAC coding interval adjustment process with a forbidden symbol. \(i-1{\sim}i-k\) in the current decoding sequence as the context conditions of the current decoding symbol and perform decoding to obtain a clear decoding result. If the decoding result is a forbidden symbol, the current decoding branch is deleted.