Compressing signals using serially-concatenated accumulate codes

Abstract

A method compresses a set of correlated signals by first converting each signal to a sequence of integers, which are further organized as a set of bit-planes. This can be done by signal transformation and quantization. An inverse accumulator is applied to each bit-plane to produce a bit-plane of shifted bits, which are permuted according to a predetermined permutation to produce bit-planes of permuted bits. Each bit-plane of permuted bits is partitioned into a set of blocks of bits. Syndrome bits are generated for each block of bits according to a rate-adaptive base code. Subsequently, the syndrome bits can be decompressed in a decoder to recover the original correlated signals. For each bit-plane of the corresponding signal, a bit probability estimate is generated. Then, the bit-plane is reconstructed using the syndrome bits and the bit probability estimate. The sequence of integers corresponding to all of the bit-planes can then be reconstructed from the bit probability estimates, and the original signal can be recovered from the sequences of integers using an inverse quantization and inverse transform.

1 . A method for compressing a set of correlated signals, comprising: 
 converting each signal to a sequence of integers;    organizing each sequence of integers as a set of bit-planes;    applying, to each bit-plane, an inverse accumulator to produce a bit-plane of shifted bits;    permuting each bit-plane of shifted bits according to a predetermined permutation to a produce a bit-plane of permuted bits;    partitioning each bit-plane of permuted bits into a set of blocks of bits; and    generating syndrome bits for each block of bits according to a base code, all the syndrome bits being a compression of the set of correlated signals.    
   
   
       2 . The method of  claim 1 , in which the correlation between the signals is temporal.  
   
   
       3 . The method of  claim 1 , in which the correlation between the signals is spatial.  
   
   
       4 . The method of  claim 2 , in which the correlated signals are images in a video sequence.  
   
   
       5 . The method of  claim 1 , in which the correlated signals are first quantized.  
   
   
       6 . The method of  claim 1 , in which the converting and organizing comprises: 
 transforming each signal to a set of coefficients; and    quantizing each set of coefficients to produce the set of bit-planes.    
   
   
       7 . The method of  claim 4 , further comprising: 
 partitioning each image into a set of macroblocks;    transforming each macroblock to a set of coefficients; and    quantizing each set of coefficients to the set of bit-planes.    
   
   
       8 . The method of  claim 1 , in which the base code is a product code.  
   
   
       9 . The method of  claim 1 , in which the base code is an extended Hamming code.  
   
   
       10 . The method of  claim 1 , further comprising: 
 determining a number of syndromes bits to generate for each correlated signal.    
   
   
       11 . The method of  claim 10 , in which the number of syndrome bits is determined using feedback from a decoder of the syndrome bits.  
   
   
       12 . The method of claim  111 , in which the number of syndrome bits is determined using an estimate of a conditional entropy of the correlated signal with respect to available side information.  
   
   
       13 . The method of  claim 12 , in which the side information is a previously reconstructed signal by the decoder.  
   
   
       14 . The method of  claim 1 , in which a number of the syndrome bits that are generated for the corresponding signals varies adaptively according to the level of redundancy in the corresponding signals.  
   
   
       15 . The method of  claim 14 , further comprising: 
 generating additional syndrome bits incrementally.    
   
   
       16 . The method of  claim 15 , in which the generating of the additional syndrome bits further comprises: 
 partitioning the base code into a set of reduced length base codes according to a predetermined schedule;    partitioning the corresponding block into a set of reduced length blocks, there being one reduced length code for each reduced length base code; and    generating the additional syndrome bits using the syndromes of the reduced length base codes for the reduced length blocks, and previously generated syndrome bits.    
   
   
       17 . The method of  claim 16 , in which the reduced length base codes are extended Hamming codes.  
   
   
       18 . The method of  claim 16 , in which the reduced length base codes are products of single parity check codes.  
   
   
       19 . The method of  claim 13 , in which a first signal is compressed conventionally.  
   
   
       20 . The method of  claim 1 , in which the bit-planes are in a form of Gray codes.  
   
   
       21 . The method of  claim 1 , in which decompressing the syndrome bits corresponding to one of the signals further comprises: 
 generating, for each bit-plane of the corresponding signal, a bit probability estimate for each bit of the bit-plane;    reconstructing the bit-plane using the syndrome bits corresponding to the bit-plane and the bit probability estimates;    reconstructing the sequence of integers corresponding to all of the bit-planes of the corresponding signal; and    reconstructing the signal from the sequence of integers.    
   
   
       22 . The method of  claim 21 , in which the bit probability estimate is generated from a probability distribution dependent on a previously reconstructed signal, and conditioned on previously reconstructed bit-planes of the corresponding signal.  
   
   
       23 . The method of  claim 22 , in which the probability distribution is a Gaussian function.  
   
   
       24 . The method of  claim 22 , in which the probability distribution is a Laplacian function.  
   
   
       25 . The method of  claim 22 , further comprising: 
 estimating the probability distribution from a set of training signals.    
   
   
       26 . The method of  claim 22 , in which the previously reconstructed signal is obtained conventionally.  
   
   
       27 . The method of  claim 21 , in which the bit-planes are processed, during the decompressing, in order from a most-significant bit to a least-significant bit.  
   
   
       28 . The method of  claim 21 , in which the bit-planes are processed, during the decompressing, in order from a least-significant bit to a most-significant bit.  
   
   
       29 . The method of  claim 1 , further comprising: 
 selecting the base codes dependent on the number of syndrome bits to generate and a predetermined base code partitioning schedule.    
   
   
       30 . The method of  claim 21 , in which the reconstructing of the bit-plane further comprises: 
 selecting the base codes dependent on a number of syndrome bits to decompress and a predetermined base code partitioning schedule;    alternately, for a predetermined number of iterations, decoding an accumulate code using the using the bit probability estimates and decoding the selected base codes using the bit probability estimates and the syndrome bits to be decompressed, to produce final bit probability estimates for the bit-plane; and    thresholding the final bit probability estimates to reconstruct the bit-plane.    
   
   
       31 . The method of  claim 30 , further comprising: 
 determining whether the final thresholded bit probability estimates correspond to a coset codeword;    accepting the final thresholded bit probability estimates as the bit-plane if true; and    rejecting the final thresholded bit probability estimates if false.    
   
   
       32 . The method of  claim 31 , in which the rejecting further comprises: 
 increasing the number of the syndrome bits during the generating of the syndrome bits.