## 3 Adaptive Computation
### Adapting the Number of Operations  
The number and nature of low level operations can also be adapted dynamically to optimize power consumption. As an example, in a video encoder application, the number of computations for motion estimation is adapted for each macro-block [21]. Motion estimation is performed by comparing a macro-block with all macro-blocks in a reference frame, within a search window of size \(\pm\)32 pixels. This leads to comparisons with 65 \(\times\) 65 = 4225 macro-blocks in the reference frame. With each comparison requiring the calculation of the sum of absolute difference as given in Equation 3:  
\[sad=\sum_{i=1}^{16}\sum_{j=1}^{16}\left|C\left(i,j\right)-R\left(i+v_{i},j+v_{j }\right)\right| \tag{3}\]  
Here \(v\) = (\(v_{i}v_{j}\)) is the motion vector relative to the current macro-block. This equation requires 256 subtractions, 256 absolutes and 255 additions and when performed over all the search points in the \(\pm\)32 search window, requires over two million arithmetic operations per macro-block. Comparison complexity can be reduced by partitioning the 16 \(\times\) 16 macro-block into 16 groups each with 4 \(\times\) 4 pixels [22]. Each partition is now represented by a sum of all the pixels in the partition and comparison computation is done using this reduced 16 element vector. The total computation per search point reduces to 71 operations with this approach. In general, the number of computations for each macro-block comparison decreases with reduced number of partitions. For example with a 2 \(\times\) 2 partition, _i.e._, with each partition having a size of 8 \(\times\) 8 pixels, the number of operations reduces to 33. However the overall compression quality could degrade in general. But when the macro-block is from a portion of the image with uniform background, like a wall for instance, then reducing the number of partitions doesn't compromise compression quality. This motivates an adaptive partitioning scheme, where an analysis of the macro-block indicates how fine to partition the macro-block [21]. Hadamard transform coefficients, along with the pixel variances for the macro-block are used to come up with the optimal partition. Figure 10 illustrates an example of a macro-block with an edge in the lower right corners. Since the top left of the macro-block is uniform, a large partition of 8 \(\times\) 8 suffices in this region. The partitions next to it are of size 8 \(\times\) 4 and 4 \(\times\) 4 respectively. Finally the partitions to the right and bottom are all smaller with size 4 \(\times\) 4 pixels, ensuring that the edge doesn't get smeared out across the partitions.  
Figure 10: Partition of a 16 \(\times\) 16 macro-block into 11 partitions, based on the edge features. The top left 8 \(\times\) 8 sub-blocks have no further partitions. The edges lie mostly within each partition.  
Table 2 shows the relative savings in the computations and power of the adaptive partitioning scheme [21] when compared to a fixed partitioning scheme of \(4\times 4\) partitions [22]. The second entry indicates a power increase using this technique, even though the number of computations is reduced. This happens due to power overheads of using additional structures like FIFOs in an actual implementation, which are not captured by just counting the number of computations.