Less is more

Implementing features in software was once thought to be more cost-effective than a hardware alternative. But is it?

Many functions in electronic products are implemented in embedded software. The microprocessor, that forms the heart of the product, executes the software. In many cases software is preferred to a hardware solution because it is more flexible, easier to update, can be reused, and seems less expensive.

However, software also contributes to the product cost, because embedded or separate memories are needed to store it. In many current products, the space occupied by the software is increasing faster than the memory price decreases.

Consequently, memories are beginning to take up a large part of the total costs of products. Economising on software becomes an issue – using as few instructions as possible to implement a certain task and using as little pre-stored data as possible for a graphical user interface. At Philips Research, this approach is being investigated in the appropriately named ThumbScrews project.

‘For a long time implementing features in software was thought to be cost-effective – there are, of course, initial costs for developing it, but once these are paid for, the software comes for free. But it doesn’t. The cost of the memory needed to store the embedded software can no longer be neglected,’ says Rik van de Wiel, Thumbscrews project leader. His colleague, Paul Hoogendijk, involved in data compression for graphics, adds: ‘And the expected thirty-fold increase in icon memory size, due to future use of high-resolution colour displays, will have to be accommodated for by data compression. Now the processor speed is the limiting factor, but as processors are getting faster, more complex compression methods are feasible.’

The increasing number of functions in mobile phones, like organisers and Internet access call for an easy user interface. The trend is towards using graphics, like icons, in the user interface. In the newer Philips mobile phones these are presented in a carousel; a sequence of moving icons from which the user can select a specific function by rotating the carousel to the corresponding icon. By encoding the icons of the carousel with as few bytes as possible, memory space can be saved. This space can then be used to store additional software to increase the functionality of the mobile phone.

Icons and characters

An average icon used in the carousel of the graphical user interface of Philips mobile phones consists of 18 by 22 pixels. Each pixel can be ‘on’ or ‘off ‘ in a monochrome display. Current mobile-phone user interfaces contain more than 1000 icons and so take up a significant part of the available memory.

This will increase even more when colour displays and high-resolution displays enter the scene. Moreover, in countries like China, where other, larger character sets than the Roman alphabet are used, graphical representations of these characters have to be stored as well. For the Chinese language more than 9000 characters are used, and although these are smaller than icons, they come in place of the 26 characters of the Roman alphabet.

Hence the need for economising on data in embedded memory.

The idea is to encode an icon in such a way that as few bytes as possible are needed and that the original icon bit-map can be reconstructed from the encoded bytes. When the user rotates the carousel to select a function, every icon in the carousel has to be decompressed in almost real-time to ensure a smooth movement on the display. This imposes heavy requirements on the decompressing algorithm. The compression algorithm, on the other hand, is only used once to generate the coded information. Compression can thus be executed on a more powerful computer and then be stored in the Flash Read-Only Memory (Flash ROM) of the mobile phone.

Dedicated For mobile applications, dedicated compression techniques are needed. The reason for this is that normal, PC-like compression and decompression algorithms like ZIP, are attuned to large data blocks and result in hardly any compression for the relatively small icons. Moreover the computing power of the embedded processor and the available memory is limited. And, as mentioned already, decompression must be done in real-time.

Predicting pixel values

For this dedicated compression algorithm, predictive filtering is used. The pixels which have already been decompressed are used to predict whether the next pixel is ‘on’ or ‘off ‘. The simplest filter is one which operates on the principle that if the current pixel is ‘on’ (or ‘off’), there is a high probability that the next one will also be ‘on’ (or ‘off ‘). If the predicted value is not the same as the actual value, then that pixel value will be stored as a ‘1’, represented by a white pixel in the compressed icon representations on this page (see also text box ‘Predictive filtering’). The aim is to get as few white pixels as possible. The less white pixels, the better the compression.

For the icons the savings is 65%. The wonderful thing is that this method can be used for any type of image, even Chinese characters. The savings with these are somewhat less, because Chinese characters are more complicated than icons and thus more difficult to predict.

The compression process is based on methods which are more or less standard. The unique combination of these compression methods has been tailored for mobile-phone applications and has been adopted by Philips Consumer Communications.

In the current mobile phones, the displays are limited in size and resolution, but new generations of phones will have high-resolution colour displays and offer wide-ranging facilities like WAP services. For these phones, the memory savings achieved by data compression will become even more pronounced.

Combining instructions

The successful savings in memory by compacting data can be extended to the instruction code stored in the embedded Flash ROM. The approach in this domain is a bit different but can easily be explained by drawing an analogy with shorthand.

Frequently occurring combinations of words or parts of sentences are replaced by one stenographic symbol. The same can be done for combinations of instructions in software code. Frequently occurring sequences of instructions can be replaced by one macro-instruction. In contrast with shorthand, where the stenographic symbols are fixed, the best set of macro-instructions is determined for each application or application area. In addition, Huffman coding is applied: the more often an instruction occurs, the smaller the code chosen to represent this instruction. This further reduces the memory size needed to store the software program.

As with icons, the compression only has to be done once before storing the compact program in the embedded memory. Decoding the compact code in normal processor instructions has, of course, to be done in the handset when needed. To compress the software, a compiler is designed to translate the normal C or C++ code into compact code. This compact code is stored in the embedded memory. When this code has to be executed a hardware module handles the decompression to normal code that can be handled by the standard processor. Because of speed requirements, the decompression is done in hardware instead of in software. This hardware can be skipped when normal code is detected: it is, because of speed requirements, not possible to compact the complete software program.

Using this code compaction approach, the size and cost of the software can be reduced drastically.

Depending on the embedded processor architecture used, the size reduction ranges from 30% to 60%. The savings in memory can, if required, be used to lower the price or to increase the number of functions of a mobile phone.

SIDEBAR: Filter tips: The compression starts by applying a predictive filter to each bitmap. For each pixel in the bitmap a prediction is made of its value (one or zero, corresponding to ‘on ‘ or ‘off’), by using the values of its surrounding pixels. If the prediction is correct the pixel is set to zero, and otherwise to one (represented by a white pixel in the coded icon representations on this page). In this way, the number of ones is drastically reduced. The method can be optimized by using the best set of surrounding pixels, which is chosen by scanning the whole set of icon bitmaps.

After filtering, the bitmaps are compressed by encoding the number of zeros between successive ones (i.e. run lengths of zeros). The different run lengths of zeros are Huffman-encoded: a small number of bits is used to encode common run lengths, less common ones are coded in more bits. This is a so-called lossless compression method, meaning that the original image can be reconstructed exactly equal to the original.