# On the Optimal Calculation of the Rice Coding Parameter
## 5 Multi-Parameter Rice Coding
### Computing the Cost of All Sub-Sequences Efficiently  
The sub-sequences calculated in the first step do not embrace all potential sub-sequences, but only the shortest ones. The second phase of the algorithm calculates the minimum bit-length of all other possible sub-sequences of \(\mathbf{n}\), by reusing the information generated after the basis calculation by Algorithm 2.  
Algorithm 3 receives as input: an index of the basis sub-sequences (\(k_{0}\)), the values of \(q(r)\) of the basis for each potential value of \(r\) (\(\mathbf{q}\)), the start and end index of the sub-sequence (\(\mathbf{u}\) and \(\mathbf{v}\), respectively), the length of the basis (\(\hat{P}\)), and the range of the values of \(L(n_{i})\) (\(L_{min}\) and \(L_{max}\), respectively).  
```
1:functionMultiParameterSubSequencesFrom(\(k_{0}\), \(\mathbf{q}\), \(\mathbf{u}\), \(\mathbf{v}\), \(\hat{P}\), \(L_{min}\), \(L_{max}\))
2:\(\mathbf{w}\leftarrow(\infty)\)
3:\(\mathbf{z}\leftarrow(0)\)
4:\(\mathbf{y}\leftarrow(0)\)
5:for\(k_{0}\leq k\leq\hat{P}\)do
6:for\(L_{min}\leq r\leq L_{max}\)do\(\triangleright\) see (10) for \(L(x)\)
7:\(\forall_{r}\gets y_{r}+q(k,r)+(v(k)-u(k)+1)\cdot(r+2)\)
8:if\(w_{k}>y_{r}\)then
9:\(w_{k}\gets y_{r}\)
10:\(z_{k}\gets r\)
11:endif
12:endfor
13:endfor
14:return\(\{\mathbf{w},\mathbf{z}\}\)
15:endfunction
```  
**Algorithm 3** Calculation of the cost for all sub-sequences with complexity \(O(L_{max}\cdot\hat{P}^{2})\).  
The algorithm returns the minimum bit-length \(\mathbf{w}\) and the best Rice parameter \(\mathbf{z}\) for each one of the \(K-k_{0}+1\) sub-sequences in \(\mathbf{n}\) that have as first element \(\mathcal{U}_{k_{0}}\).  
Algorithm 3 consists of two nested loops. The outer loop--between Lines 5 and 13--considers the creation of a sub-sequence by merging the sub-sequences from \(k_{0}\) until \(k\) in \(\hat{P}\). Each time it considers the creation of a sub-sequence, the inner loop--between Lines 6 and 12--calculates the bit-length \(y_{r}\) of encoding such a new sub-sequence with different values of \(r\). As a result, Algorithm 3 has a running complexity of \(O(L_{max}\cdot\hat{P})\).  
Algorithm 3 needs to be called once for each sub-sequence in the basis. Therefore, computing the costs of every possible sub-sequence starting at any index of the input data yields a running time complexity of \(O(L_{max}\cdot\hat{P}^{2})\).  
For the example sequence provided in this article, Algorithm 3 is invoked four times (once per sub-sequence in the basis). The values stored in the variable \(y_{r}\) in the first iteration of each call are shown in Table 3. These values correspond to the bit-length of the sub-sequences in the basis for different values of the Rice parameter.  
\begin{table}
\begin{tabular}{c c c c c c c c c} \hline \hline \(\mathbf{k}\) & \multicolumn{4}{c}{\(\mathbf{Q_{k}(r)}\)} & \multicolumn{4}{c}{\(\mathbf{u_{k}}\)} & \(\mathbf{v_{k}}\) & \(\mathbf{\delta_{k}}\) \\ \hline  & \(r=1\) & 2 & 3 & 4 & 5 & 6 & & \\ \hline
1 & 9 & 4 & 0 & 0 & 0 & 0 & 1 & 4 & 20 \\
2 & 18 & 8 & 3 & 0 & 0 & 0 & 5 & 7 & 38 \\
3 & 49 & 24 & 11 & 5 & 2 & 0 & 8 & 9 & 99 \\
4 & 0 & 0 & 0 & 0 & 0 & 0 & 10 & 10 & 1 \\ \hline \hline \end{tabular}
\end{table}
Table 2: The generated \(\hat{P}=4\) sub-sequences for the basis for the example input data with \(N=10\) as a result of Algorithm 2. The values of \(Q_{k}(r)\) represent the value of \(Q(r)\) as given in (9) for the \(k\)-th sub-sequence of the basis, defined by the indices \(u_{k}\) and \(v_{k}\). The column \(\hat{s}_{k}\) provides the sum of the values of the input data within the indices \(u_{k}\) and \(v_{k}\).  
Table 4 shows the input values of Algorithm 3 for the example sequences of this article. Each column represents the minimum bit-length and optimal Rice parameter for each one of the 10 possible sub-sequences for the example problem.