Abstract

This study falls into two areas: image modelling in which we study the lossless compression of bilevel images, and spread spectrum message authentication.

Firstly, we present a context-weighting algorithm for probability estimation in lossless bilevel image compression. This algorithm adaptively weights in real time two or three context models based on their relative accuracy, and automatically selects the better model over different regions of an image. Combined with the Block Arithmetic Coder for Image Compression (BACIC), the overall performance obtained is slightly better than the state-of-art facsimile standard, JBIG, for the eight CCITT business-type test images. The encoder outperforms JBIG by 13.8% on halftone images and by 17.5% for compound images containing both text and halftones. We derive weighting factors which can be updated pixel by pixel based upon the relative accuracy of the corresponding context models; also we propose a forgetting factor to adjust each update of the weighting factors. Using this algorithm, the encoder eliminates the disadvantage of JBIG and the original BACIC in that users no longer need to select context models to get the best performance. The encoder produces better probability estimates than using either model exclusively.

Secondly, we present a new scheme to reduce the communications requirements of sending message authentication tags (MAC's) when sending the MAC's over direct sequence spread spectrum wireless channels. In direct sequence spread spectrum, each data bit is represented by multiple chips (64 chips/bit in typical systems), which have much lower energy-to-noise ratio than do bits. We propose to use a sequence of chips to represent the MAC tag and decode the chip sequence as a whole at the receiver. In contrast, conventional demodulation firstly de-spreads chips to form bits and decodes based on bits. We greatly reduce the number of chips required with the proposed scheme. In one example, based on the IS-95 CDMA Digital Cellular Standard, we reduce the chips needed from 3072 to 1142 by a hard decision decoding scheme, and to 728 by a soft decision decoding scheme, achieving savings of factors about three and four respectively. Robustness for the soft decision decoder is also presented. By making a simple modification on the log-likelihood ratio function, we make the decoder adaptive to several other noise models, while only slightly sacrificing the performance on a Gaussian noise model.

The spread spectrum message authentication technique is then applied to the Noise-Tolerant Message Authentication Codes (NTMAC). We greatly reduce the number of chips required by replacing each sub-MAC with a chip sequence (sub-tag) considered as a whole, while all the advantages of the original NTMAC are retained.