1995 NASA GOVERNMENT INVENTION OF THE YEAR

Method for Coding Low Entropy Data

Dr. Pen-Shu Yeh
Goddard Space Flight Center
Greenbelt, MD

DATA COMPRESSION TECHNOLOGY

NASA has selected a technique for encoding and compressing digital data as the winner of the Government Invention of the Year Award for 1995. The "Method for Coding Low Entropy Data", a creation of Dr. Pen-Shu Yeh of the NASA Goddard Space Flight Center in Greenbelt, Md., has been selected by the NASA Office of The General Counsel for the honor.

"This encoding method for improving digital data is a part of the data compression technology developed at Goddard. Several years ago, we realized there is a need to initiate the technology development in this area because our science community has demanded more and more data from their sophisticated instruments," said Dr. Yeh. "The Method for Coding Low Entropy Data extends the performance beyond the bound set by a traditional Huffman code, making this technology even more adaptive to various kinds of instruments and applications."

As scientific instruments grow increasingly more precise and sophisticated, the amount of data generated by them also increases. The lossless data compression technology reduces redundancy in the data representation while guaranteeing full and accurate reconstruction of the data. Using data compression technology on the spacecraft reduces the requirements for onboard memory and ground station contact time, it often translates into millions of dollars of savings for a single space mission.

Implementing data compression on spacecraft requires a technique that adapts easily to changes in data while using little power and memory. Dr. Yeh and her co-workers found that the Rice algorithm, developed at the Jet Propulsion Laboratory in the early 1970s, adapted to their needs for lossless data compression. The Rice algorithm, however, was difficult for system designers to understand. Dr. Yeh showed that the Rice algorithm was actually a derivative of the widely accepted Huffman Code, and extended the code to increase the efficiency of the method. The extended Rice algorithm has been implemented in silicon circuits suitable for space flight use at the Microelectronics Research Lab at the University of Idaho. The circuits have been integrated in several space missions including the Small Satellite Technology Initiative Lewis spacecraft. The technology has also been implemented in software for the Mars Observer, Submillimeter Wave Astronomy Satellite, and others.

The lossless data compression technology developed by Dr. Yeh and co-workers, is currently under consideration to become an recommendation for an international standard for space data systems. "Dr. Yeh has extended a method for data compression which will benefit NASA and industry as well," said Warner Miller, a NASA representative and panel chairman of the Consultative Committee for Space Data Systems.

Benefits of the technology have been transfered to industries as well. "There's a good correlation between the needs of space imaging and medical imaging systems," said Yeh. "Doctors, like scientists, always demand full fidelity of their data." Studies at Goddard indicate the compression technique offers superior performance for medical imaging data such as magnetic resonance, ultrasound, and nuclear medicine.

The development of the lossless data compression technology for space and science use in general, involves a team effort between Goddard Space Flight Center (GSFC), the Center for Advanced Microelectronics and Biomolecular Research (CAMBR) at the University of Idaho and Jet Propulsion Laboratories (JPL). Warner Miller at GSFC directs the technology development, Robert Rice at JPL provided algorithm architecture, Pen-Shu Yeh at GSFC established the preformance of the algorithm and provides simulation support to flight projects, Wai Fong and Joe Miko at GSFC did board level integration and testing, Jack Venbrux at the CAMBR led the development of the VLSI compression/decompression chips with major contributors: M. N. Liu, Jody Gambles and Don Wiseman. Software developments were provided by Lowell Miles at CAMBR. Many users from other organizations provided feedback based on their experience from using the first generation chips.

• 1989 spring, selection of algorithm based on requirements.
• 1989 fall, completed theoretical analysis and began VLSI design.
• 1991 spring, first generation engineering chip fabricated.
• 1992 fall, integrated with testbed and began re-design for space.
• 1993 summer, re-design for space chip completed.
• 1993 fall, demonstrated chip set using Tracking and Data Relay Satellite.
• 1994 spring, fabrication of space qualified chip completed.
• 1994 spring, software implemented for spacecraft SWAS/SMEX. (waiting launch vehicle in 96).
• 1995 fall, delivered compression board to SSTI/Lewis spacecraft (launch 8/96).

Lossless Data Compression Board for SSTI/Lewis

• First generation chip: Advanced Hardware Architecture (AHA)
  contact John Overby (509) 334-1000.
• Second generation chip: ICs
  contact Dr. Gary Maki (505) 277-9700.

• Goddard Space Flight Center Exceptional Achievement Award, 1992
• NASA TechBrief Award Tech Briefs magazine, April 1994 and October 1994.
• Patent Award U. S. Patent #5,448,642 Method for Coding Low Entropy Data, September 1995

Pen-Shu Yeh

Education

MSEE from University of Washington

PhD in EE from Stanford University

Experience

Yeh has been at Goddard for seven years working in developing technology for space, mainly in the area of onboard processing. She is responsible specifically for the analysis, simulation and selection of data compression algorithms for further development into VLSI hardware. She also provides support to flight programs to help scientists and program office decide if data compression is suitable for their projects and what algorithm to use. She is a co-investigator on the compression experiment to be flown on the SSTI/LEWIS spacecraft. For this experiment, both lossless and lossy algorithms are implemented. The lossless compression uses the VLSI hardware, whereas the lossy compression uses a combination of software and hardware.

Prior to working at Goddard, Yeh worked in both academic environment and industry where she did research in computer/robotic vision, pattern recognition and data compression.

[1] Jack Venbrux, Pen-Shu Yeh and Muye N. Liu, "A VLSI Chip Set for High-Speed Lossless Data Compression," IEEE Trans. on Circuits and Systems for Video Technology, Vol. 2, No. 4, Dec. 1992

[2] Robert F. Rice, Pen-Shu Yeh and Warner H. Miller, "Algorithms for High-Speed Universal Noiseless Coding," Proc. of the AIAA Computing in Aerospace 9 Conference, San Diego, CA, Oct. 19-21, 1993

[3] Pen-Shu Yeh, Robert F. Rice and Warner H. Miller, "On the Optimality of a Universal Noiseless Coder," Proc. of the AIAA Computing in Aerospace 9 Conference, San Diego, CA, Oct. 19-21, 1993

[4] Jack Venbrux, Pen-Shu Yeh, G. Zweigle and J. Vesel, "A VLSI Chip Solution for Lossless Medical Imagery Compression," Proceedings of the SPIE Medical Imaging, 1994.

[5] Pen-Shu Yeh and Warner H. Miller, "A Real Time Lossless Data Compression Technology for Remote Sensing and Other Applications," ISCAS-95, 1995.