The NEO binary entropy coding method and system

In this thesis, a new binary entropy coding method and system for compression and decompression are presented. The compression method is based on the non-increasing encoding order (hereafter: NEO) method. This method encodes data items from the largest one to the smallest. It determines the encoding length of the current data item from the previous encoded data item. This current encoding length is the same as the minimum required encoding length of the previous encoded data item.; There are several important techniques introduced that considerably improve the performance of the NEO method. One such technique employs a smaller encoding length that includes a flag bit to achieve more efficient compression. This smaller encoding length is one bit (the most significant bit) less than the encoding length of the initial NEO encoding method. The decoder then determines whether or not to add a flag bit. This work can be done by comparing the value of the current encoded data item with the previous data item without the most significant bit. Another method reduces the range of the encoding data values by employing the incremental subtrahend method (hereafter: ISM). This technique is employed to encode distinct data items. ISM subtracts data items from the smallest one to the largest by an increasing subtrahend. We then get smaller data items and shorter ranges of encoding data values. Another special NEO encoding method is also proposed. It uses compact look-up tables to fulfill a combination computation which is used to determine the position of the encoding item. This fast combination computation is very efficient when the number of the encoding items is low. Also some existing techniques are considered to improve the encoding performance such as Huffman coding, differential coding, and run-length coding.; Since the NEO method is a variable-size coding technique, the delimitations between each NEO encoding string is an important problem. Both headers and end-of-string symbols are used to resolve this problem. There are two kinds of headers. The first indicates the precise number of encoded items in each string. The second indicates the range of the number of encoded items in each string. In the second case, an extra end-of-string symbol is required. (Abstract shortened by UMI.)...