# Source Symbol Purging-Based Distributed Conditional Arithmetic Coding
## 2 Source Symbol Purging-Based Distributed Conditional Arithmetic Coding
### SPDCAC Encoding Process  
Suppose that the binary source sequence to be encoded is \(X^{N}=(x_{1},x_{2},...,x_{N})\). When the SPDCAC encoder based on a \(k\) th \((k\geq 1)\)-order context model encodes this source sequence, the encoder needs to use \(k\) source symbols \((x_{i-1},x_{i-2},...,x_{i-k})\) before the symbol \(x_{i}\) to be encoded as the context condition, \((x_{i-1},x_{i-2},...,x_{i-k})\) will be denoted as \(x_{i-1}^{i-k}\), and the conditional probability: \(P(x_{i}|x_{i-1}^{i-k})\) is used as the encoding probability. \(P(x_{i}|x_{i-1}^{i-k})\) needs to be estimated by the counting statistics of the encoded symbols and dynamically updated during the encoding process. This means the underlying encoder of SPDCAC is a context-based adaptive arithmetic encoder.  
The encoder of SPDCAC only encodes a part of the symbols in the source sequence through the arithmetic encoder based on the context model. Other 'purged' symbols in the source sequence are not encoded and are only used as the context conditions for the coding of subsequent symbols. Figure 2 shows an example of the SPDCAC encoding process. The first \(n-1\) symbols in every \(n\) source symbols need to be encoded, and the remaining 'purged' symbol together with those encoded symbols are used as the context conditions for the coding of following symbols (it can be regarded that the purging rate is \(1/n\)). We use \(CX^{i}\) to represent the codeword output by the SPDCAC encoder after encoding \(X^{i}\). Since the underlying encoder of SPDCAC is an arithmetic encoder, as the encoding continues, bits are constantly added to the codeword, and the length of the codeword will continue to increase. It should be noted that if the encoder encodes the source symbol \(x_{i}\) at moment \(i\), but does not encode the source symbol \(x_{i+1}\) at moment \(i+1\), then the codeword \(CX^{i+1}\) is the same as the codeword \(CX^{i}\). When the encoder completes the encoding of the entire \(X^{N}\) sequence, it outputs the codeword \(CX^{N}\).  
A forbidden symbol is considered during the encoding process of SPDCAC. The encoder of SPDCAC reserves a sub-interval that does not correspond to any valid source symbol in the encoding probability distribution intervals. This interval is related to a forbidden symbol that is not encoded. If there is no error in the codeword, the forbidden symbol should not be decoded during the decoding process. Otherwise, if the decoder finds that the codeword falls into the forbidden interval, it can be determined that the codeword is incorrect. Adding 'forbidden symbols' in the coding process will only increase the size of the alphabet, which will not break the internal correlation among the symbols in the source sequence. This approach can rapidly detect whether the codeword is wrong so that the decoder can terminate the corresponding branch in the decoding tree immediately to improve decoding performance.  
As shown in Figure 3, in the probability distribution for a binary source, the forbidden sub-interval is added at the end of the probability intervals right beside the sub-interval of the symbol with the larger probability. The length of the forbidden sub-interval is of length \(\mu\) which is only related to the larger probability. Let \(p_{0}\) and \(p_{1}\) be the original probabilities of the symbols 0 and 1, respectively. If \(p_{0}\) is larger, it will become \(p_{0}^{{}^{\prime}}\) after the forbidden sub-interval \(\mu\) is added; otherwise, \(p_{1}\) will become \(p_{1}^{{}^{\prime}}\).  
Figure 2: An example of the SPDCAC encoding process.