# On the Optimal Calculation of the Rice Coding Parameter
## 5 Multi-Parameter Rice Coding
### Auxiliary DAG and Optimal Solution  
In the third phase, we construct an auxiliary Directed Acyclic Bipartite Graph (DABiG) for finding the best subset of sub-sequences that yield the best multi-parameter solution.  
The DABiG is constructed as follows:  
* for each sub-sequence in the basis \(k\), we add two vertices \(u_{k}\) and \(v_{k}\), representing the sub-sequence's start \(\mathcal{U}_{k}\) and the \(\mathcal{V}_{k}\), respectively;
* we add two special vertices \(v_{\alpha}\) and \(u_{\omega}\);
* we add one edge from each vertex \(u_{k_{1}}\) to each vertex \(v_{k_{2}}\), where \(k_{2}\geq k_{1}\), with the cost given by \(\mathbf{w}_{k_{2}}\) when Algorithm 3 is invoked with \(k_{1}\) as its first parameter;
* we add one edge from each vertex \(v_{k}\) to \(u_{k+1}\) with cost \(\epsilon\); and finally,
* we add one edge from \(v_{\alpha}\) to \(u_{1}\) with cost \(\epsilon\) and another edge from \(v_{M}\) to \(u_{\omega}\) with cost zero.  
Therefore, the DABiG consists of \(2\cdot\hat{P}+2\) vertices and \(\frac{\hat{P}\cdot(\hat{P}+1)}{2}+\hat{P}+2\) directed edges. A graphical representation of the DABiG can be observed in Figure 8.  
\begin{table}
\begin{tabular}{c c c c c c c c c c} \hline \hline
**From (\(\mathbf{k_{0}}\))** & \multicolumn{3}{c}{**1**} & \multicolumn{3}{c}{**5**} & \multicolumn{3}{c}{**8**} & **10** \\ \hline To (\(k\)) & 4 & 7 & 9 & 10 & 7 & 9 & 10 & 9 & 10 & 10 \\ \(w\) & 20 & 38 & 59 & 64 & 18 & 35 & 41 & 16 & 23 & 3 \\ \(z\) & 2 & 3 & 3 & 3 & 3 & 4 & 4 & 5 & 4 & 1 \\ \hline \hline \end{tabular}
\end{table}
Table 4: Output data of Algorithm 3. The first header row (\(k_{0}\)) represents the starting index of the sub-sequence. The second header row (\(k\)) represents the end index of the sub-sequence. Each column provides values of the minimum bit-length for the sub-sequence (\(w\)) and the corresponding value of the Rice parameter (\(z\)).  
\begin{table}
\begin{tabular}{c c c c c c c} \hline \hline
**Basis** & \(\mathbf{r=1}\) & **2** & **3** & **4** & **5** & **6** \\ \hline \([1,4]\) & 21 & 20 & 20 & 24 & 40 & 48 \\ \([5,7]\) & 27 & 20 & 18 & 18 & 21 & 21 \\ \([8,9]\) & 55 & 32 & 21 & 17 & 16 & 17 \\ \([10,10]\) & 3 & 4 & 5 & 6 & 7 & 8 \\ \hline \hline \end{tabular}
\end{table}
Table 3: Total bit-length for each one of the \(\hat{P}=4\) sub-sequences of the basis (shown in Table 2) for each value of the Rice parameter (\(r\)). Each row of this table is implicitly calculated by Algorithm 3 in its first iteration and stored in variable \(y_{r}\) for further usage.  
Figure 8: The directed acyclic bipartite graph for solving the multi-parameter Rice encoding problem. Each pair of \(u_{k}\) and \(v_{k}\) vertices represents the start and end of a sub-sequence in the basis (see Algorithm 2). The edges represent all possible ways of grouping the input data into larger sub-sequences. Edge costs are equal to the minimum bit-length of the sub-sequence \(w_{k}^{(i)}\) (see Algorithm 3) or to the overhead bit-length caused due to adding an extra sub-sequence to the solution (\(\epsilon\)). The solution to the problem is given by the shortest path from \(v_{\alpha}\) to \(u_{\omega}\).  
The solution to our problem is given by the shortest path from \(v_{\alpha}\) to \(u_{\omega}\). The total minimal cost of the encoding is the cost of the shortest path found.  
Following with our example, Figure 9 shows the DABiG based on the found sub-sequences by Algorithm 3, which were previously mentioned in Table 4.