# On the Optimal Calculation of the Rice Coding Parameter
## 5 Multi-Parameter Rice Coding
### Basis--Reducing Input Length  
Initially, we attempt to reduce the input length of our problem. For this, we partition the input sequence of \(N\) samples into \(\hat{P}\leq N\) consecutive sub-sequences of samples, in such a way that the samples in each sub-sequence require the same number of bits for encoding, as given by the value of the function \(L(n_{i})\) previously defined in (10).  
Figure 7: Scaled sequential difference of 128 measurements of interval rain from the 63 rd Street Weather Station in Chicago, USA, between 09:00:00 and 19:00:00 local time on 1 March 2017. The continuous (black) line represents the sequence of measurements over time. The shaded (coloured) boxes represent the way in which the given sequence of measurements can be partitioned into four sub-sequences in order to achieve shorter Rice codes.  
In this section, the sub-sequences are defined by the pair of indices of the start and end positions in its original input sequence \(\mathbf{n}\). We illustrate the outcomes of this process with the example dataset previously presented in Table 1. In this case, a total of four sub-sequences--viz. \([1,4]\), \([5,7]\), \([8,9]\) and \([10,10]\)--shall conform the basis, since the values of \(L(n_{i})\) for the samples within these ranges is the same.  
In this first step, for each sub-sequence in the basis, we compute and store: the value of \(Q(r)\) of (9) for different values of \(r\), the range index in the sequence, and the sum of the values of that sub-sequence. This information will be used to generate all the other potentially needed sub-sequences in the second step of this algorithm (see Section 5.2). The function for computing these parameters can be seen in Algorithm 2. For each sub-sequence \(p_{k}\), the function returns the index of its starting and last elements in \(\mathbf{u}\) and \(\mathbf{v}\), respectively. Note that \(u_{k+1}=v_{k}+1\), since no sample is lost in the partitioning, nor repeated. The function also returns in \(\mathbf{q}\) the encoding length of the each one of the \(\hat{P}\) sub-sequences for different potential values of \(r\), and also the sum of the values for each sub-sequence \(\hat{s}_{k}\).  
```
1:functionMultiParameterBasis(\(\mathbf{n}\), \(N\))
2:\(k\gets 1\)
3:\(i^{\prime}\gets 1\)
4:\(l^{\prime}\gets L(n(1))\)\(\triangleright\) see (10) for \(L(x)\)
5:\(\mathbf{q}\leftarrow(0)\)
6:\(\mathbf{\hat{s}}\leftarrow(0)\)
7:\(L_{min}\leftarrow\min_{i}L(n(i))\)
8:\(L_{max}\leftarrow\max_{i}L(n(i))\)
9:for\(1\leq i\leq N\)do
10:\(\hat{s}_{k}\leftarrow\hat{s}_{k}+n(i)\)
11:for\(L_{min}\leq r\leq L_{max}\)do
12:\(q_{kr}\gets q_{kr}+\left\lfloor\frac{n(i)}{2}\right\rfloor\)
13:endfor
14:if\(L(n(i))\
eq l^{\prime}\)then
15:\(u_{k}\gets i^{\prime}\)
16:\(v_{k}\gets i\)
17:\(k\gets k+1\)
18:\(i^{\prime}\gets i+1\)
19:\(l^{\prime}\gets L(n(i^{\prime}))\)
20:endif
21:endfor
22:return\(\{\mathbf{q},\mathbf{\hat{s}},\mathbf{u},\mathbf{v},k,L_{min},L_{max}\}\)
23:endfunction
```  
**Algorithm 2** Calculation of the basis for the multi-parameter Rice-encoding problem with complexity \(O(L_{max}\cdot N)\).  
Algorithm 2 has two nested loops. The outer loop--between Lines 9 and 21--iterates over all input values. The inner loop--between Lines 11 and 13--calculates the values \(q_{kr}\) for every potential value of \(r\) for the input value in consideration. Therefore, this step has a complexity of \(O(L_{max}\cdot N)\).  
The output of Algorithm 2 for the example data presented in Table 1 is provided in Table 2.  
In order to better illustrate constant values in the remaining part of this section, we will use \(\mathcal{U}_{k}\) and \(\mathcal{V}_{k}\) to denote the set of indices of \(\mathbf{n}\) where the sub-sequence \(k\) of the basis starts and ends, respectively. These two values correspond to the output values of \(\mathbf{u}\) and \(\mathbf{v}\) of Algorithm 2. In addition, the output value of \(k\) becomes the constant \(\hat{P}\): the length of the basis and the output matrix \(\mathbf{q}=(Q_{k}(r))\) become an array of constants \(q(k,r)\).