## 2 Algorithm Introduction
### Decoding Algorithm Introduction  
As shown in Figure 4, the decoding process is very similar to the coding process, it is assumed that a sequence \([e(k)]\) (\(k=1,2,\ldots,n\)) is given. Each symbol \(e(k)\) belongs to a finite digital. The sequence \(u(k)\) is the output of the decoding process.  
First, the two-dimensional dictionary \(H\) is created, whose size is the same as the dictionary \(D\) of the coding process. The decoding output \(u(k)\) of \(e(k)\) is stored in the dictionary. The position of the digital \(u(k)\) in the dictionary is the two-dimensional coordinate formed by the first two adjacent digitals \(u(k-2)\) and \(u(k-1)\). When the current decoded digital \(e(k)\) is decoded, the predicted value \(u^{\prime}(k)\) of the decoded digital is read in the dictionary with the address coordinate \((u(k-2),u(k-1))\) of the first two adjacent digitals \(u(k)\). Then the digital \(e(k)\) to be decoded and the predicted value \(u^{\prime}(k)\) are added to get a signal \(u(k)=e(k)+u^{\prime}(k)\), which is the decoded output signal. When the decoding process ends, the adaptive dictionary is still discarded.  
For the decoding process, this method has two special cases, as follows:  
1. The first two digitals \(e(1)\), \(e(2)\) in the input array \([e(k)]\) to be decoded do not have the first two adjacent digitals. Therefore, the first two digitals cannot be decoded, and they need to be directly output as they are.
2. In the early stage of the decoding process, because the dictionary \(H\) is not complete, there may not be predicted values in the dictionary. According to the first two adjacent digitals of the decoded output \(u(k)\), Equation (2) can be used as the predicted value of the current digital to be encoded.  
Figure 3: Example of the predictive coding algorithm based on the adaptive dictionary.  
\[u^{\prime}(k)=a*u(k-2)+b*u(k-1), \tag{2}\]  
where \(u^{\prime}(k)\) is the predicted value of the current digital to be decoded, \(u(k-1)\) and \(u(k-2)\) are the first two adjacent digits of the output of the current decoded digital. \(a\) and \(b\) are constant prediction coefficients, which are the same as the prediction Equation (1) coefficient in the coding process.  
Algorithm 2 is the step of decoding algorithm, which works as follows:  
```
Input: decoded input [e(k)] Output: decoded output [u(k)] Initialize- dictionary H Initialize- address index k\(\leftarrow\) 0 whilek\(<\)=n %n is the length of input array[s(k)] dok\(\leftarrow\) k+1 ifk\(<\)3 thenu(k)\(\leftarrow\) e(k) elseif(u(k-2),u(k-1)) = NULL thenu'(k)\(\leftarrow\) a*u(k-2)+b*u(k-1) elseu'(k)\(\leftarrow\) H(u(k-2),u(k-1)) u(k)\(\leftarrow\) e(k)+u'(k) H(u(k-2),u(k-1))  end while
```  
**Algorithm 2** steps of decoding algorithm  
The example is Algorithm 2, which is shown in Figure 5. Assume that the input data stream for the decoder is '2 3 \(\sim\)3 0 0 0 0 0 0'. First, the first two digitals are read by the decoder. However, their first two adjacent digitals do not exist. Thus, they are directly output as they are (Figure 5a). When the dictionary is not complete, the dictionary H (3,1) is empty. The decoded data is predicted as \(-1\) by Equation (2). In the Equation (2), a \(=-1\), b \(=2\). Thus, the output value of the decoder is 2 (Figure 5b). When the dictionary is complete, the dictionary H (2,3) is not empty. The decoded data  
Figure 4: Principle block diagram of the decoding algorithm.  
is predicted as 1 by the dictionary. Thus, the output value of the decoder is 1 (Figure 5c). When the dictionary is complete, the dictionary is still updated after each prediction (Figure 5d). Finally, the data stream output by the decoder is '2 3 1 2 3 1 2 3 1 2'.