# On the Optimal Calculation of the Rice Coding Parameter
## 5 Multi-Parameter Rice Coding  
As shown in Section 4.5, when a large data sequence comprises samples of different orders of magnitude, Rice coding using a single parameter may be inefficient. This is because there is no Rice parameter that can be set efficiently for the whole sequence: a large Rice parameter may aid in the reduction of the bit-length of samples having large values at the expense of increasing the bit-length of small samples, while a small Rice parameter may aid in the reduction of the bit-length of samples having small values at the expense of increasing the bit-length of large samples.  
As an example, we show in Figure 7 a sequence of 128 measurements taken from the interval rain dataset. Most of the values of this sequence are close to zero, but a few peak values are found at the beginning of the sequence. The optimal Rice coding parameter for this particular sequence is \(R^{*}=4\), yielding a code of 987 bits. Instead, if we are allowed to partition the sequence of 128 values into sub-sequences, in such a way that a different Rice coding parameter can be used for each sub-sequence, it could probably yield a shorter code (after taking into account the overhead of encoding the extra parameters). The optimal solution for this instance of the partitioning problem is represented in the same figure with coloured boxes. It consists of partitioning the sequence into four sub-sequences and Rice coding them with parameters 5, 0, 9, and 0, respectively. This solution can encode the same sequence in 359 bits, after considering an overhead of 16 bits for appending to the stream the corresponding value of the Rice parameter for each sub-sequence.  
Figure 6: Normalised compression factor for each data type as the batch size varies.  
More formally, for a given input sequence of samples, \(\mathbf{n}\), a more optimal encoding can be achieved if we partition the sequence of input data, \(\mathbf{n}\), into a set \(\mathcal{P}=(\mathbf{p}_{k})\) of \(P\) consecutive sub-sequences and we allow ourselves to encode each sub-sequence \(\mathbf{p}_{k}\) with a different Rice parameter \(r_{k}\). We would like the reader to notice that these two decision problems--viz. how each sub-sequence is defined and what Rice parameter is to be used for each sub-sequence--are interrelated: the choice of the ranges defining each sub-sequence boundaries has an effect on the value of its optimal parameter for efficient Rice coding and vice versa.  
In this section, we present an algorithm for finding the optimal bounds for each sub-sequence and the corresponding Rice parameters so as to minimise the overall total bit-length.  
The algorithm is divided into three phases. In the first phase, in Section 5.1, a set of special sub-sequences is calculated, namely basis. In the second phase (Section 5.2), the algorithm calculates the costs of all feasible sub-sequences in an efficient manner, by reusing previous calculations of other sub-sequences (including the basis). In the third phase (Section 5.3), the algorithm constructs an auxiliary Directed Acyclic Graph (DAG) with at most \(2\cdot N+2\) weighted nodes. The optimal solution to the problem results from finding the shortest path in the auxiliary weighted DAG.  
While this approach is generally tedious, simply because it would require the calculation of the costs of all possible sub-sequences, it will help us in setting up the basic concepts for two efficient heuristics suitable for implementation in constrained IoT devices. These efficient heuristics will be presented later in Section 5.4.