Approximate Prefix Coding for Program Compression
The Invention Reduction in the size of software on a chip without the reduction of functionality is now possible through the innovation of Approximate Prefix Coding for program compression. This is a PLA (Programming Logic Array) class-based method, which can significantly decrease the amount of memory needed. This is crucial to the embedded microprocessor market, in which the entire embedded system is just one chip, and there is little extra memory for the decompressed data. The Approximate Prefix Coding software helps to reduce the size of the software on the chip (application programs, real-time operating system), without reducing its functionality.Additionally, the Approximate Prefix Coding is capable of decoding 8 symbols in parallel, as opposed to the existing solutions, which are incapable of parallel decoding. Parallel decoding increases the decompression rate significantly – to 16 bytes per clock cycle.
The Need The Approximate Prefix Coder employs class-based coding, which is a hierarchical decomposition strategy. The method also makes use of a variation of the Huffman Code – a code that changes according to a certain statistic of letter repetition.
The source alphabet is broken up into a number of classes and coding is done in two phases: A class code is assigned to every class and a symbol code is assigned to every symbol in the class. The class code is dependant on the number of symbols in the class. This simplifies the decoding process, and enables parallel decoding of multiple symbols.
In addition, the Approximate Prefix Coding can deal with larger alphabets than previous designs, since the PLA (Programming Logic Array), which is the limiting component, is used only for decoding the class code. A relatively small ROM stores the most frequently used symbols while the remaining symbols are encoded as literals.
Commercial Applications Embedded systems – Embedded microprocessors are widely used in many products, ranging from cellular phones to digital video cameras to engine controllers in automobiles. These systems must provide random access to compressed blocks of object code. The Approximate Prefix Coder decreases the memory size needed, while increasing the decoding rate, thus providing efficient use of available memory space and enabling more complex tasks on any given memory size.
Implementation Using the Approximate Prefix Coder requires implementation of unique hardware, which includes the PLA based coder/decoder. However, changing the compression algorithm according to the needs of specific products is simple and cheap, since the compression algorithm may easily be adapted to the symbol frequency statistics of each program by modifying the symbol codebook, which is stored in a ROM.
References Weiss S. & Beren S. “Class-Based Decompressor Design for Compressed Instruction Memory in Embedded Processors”, IEEE Transactions on Computers, Vol. 52, no. 11,pp. 1495-1500, Nov. 2003
Patent Granted: US Tech Transfer Officer Mr. Larry Loev Office: +972-3-6406544 Fax: +972-3-6406675 Mail: [email protected]
Inventor(s): Shlomo Weiss
Type of Offer: Licensing
« More Engineering Patents