Method for Storage and Reconstruction of the Extended Hamming Code for an 8-dimensional Lattice Quantizer
Technical Challenge:Efficient Compression and Transmission of Video Images Videoconferencing uses a huge number of bits to encode a picture, and pictures are typically sent at a rate of about 30 frames per second. Since video devices are generally designed to show a person sitting in one place and speaking, there is very little motion, and pictures change very gradually over time. For this reason, it would be very wasteful to send the entire picture. Motion estimation techniques enable the receiver to predict the new picture from the previous frame. Unfortunately, this process introduces some error and the errors tend to propagate.
Description:A popular commercial boardroom videoconferencing device designed by Baker, et al. uses an innovative method for encoding the error due to motion compensation on a pixel-by-pixel basis. The method uses a technique called lattice quantization, to encode the error in 8 pixels taken as an 8-long vector. By exploiting various symmetries, Baker can reconstruct the 2400 most likely vectors (excepting the all 0's vector) by storing only 920 of them.
This algorithm is an improved technique in which all 2400 vectors can be recovered by storing only the 16 code words of the 8-long extended Hamming code, an enormous reduction of storage requirements. It also drastically reduces the work required at the receiver to reconstruct these vectors, replacing matrix multiplies by mere substitutions. This particular technique reduces the number of vectors required to be stored form 16 to only one. It can efficiently re-create the rest of the extended hamming code to reference all of the required lattice points.
Demonstration Capability:There is no existing software. A published paper explaining algorithm.
Potential Commercial Application(s):This would primarily be used for videoconferencing and video compression. It could also potentially be adapted for other data compression applications.
Patent Status:Issued-U.S. Patent Number 6,404,820
Reference Number: 1096
If you are interested in exploring this technology further, please call express your interest in writing to the:
National Security Agency
Date Posted: Jan 15, 2009 | Last Modified: Jan 15, 2009 | Last Reviewed: Jan 15 2009