Signal processing: Look-up tables to shoulder the processing load

March 13, 2013

Advanced mathematical algorithms are essential for processing electronic signals within computers and embedded processors. Scientists and engineers are constantly refining and redesigning their algorithms to obtain higher throughput of information on ever smaller devices that consume less power.

Now, Pramod Kumar Meher of the A*STAR Institute for Infocomm Research in Singapore and co-workers at Central South University in Changsha, China, have developed an efficient new method to implement an important step in , called the discrete cosine transform (DCT). Their method could lead to devices that occupy smaller areas, provide higher throughput of information, and consume less power than existing devices.

The DCT is commonly used for the compression of digital video and audio such as MPEG files (see image). Similar to the better-known Fourier transform, the DCT involves expressing a series of data points as a sum of their product with cosine functions.

Several algorithms and software architectures already exist for computing so-called 'power-of-two-length DCTs'. But, those DCTs are not suitable for all applications. The prime-length DCT is an alternative to the power-of-two-length DCT that has the potential to be more efficient for implementation in hardware, Meher notes.

Meher and his co-workers have focused on computing the DCT of different lengths of practical interest using specialized digital circuits that occupy less area on a and use less power, but run at adequate speed. They not only derived a more efficient algorithm for DCT, but also derived new architecture—based on the 'distributed ' approach—for implementing the algorithm in integrated circuit chips.

Meher and co-workers made use of a theorem that inter-relates the transforms with cyclic convolution of two finite duration sequences. By using look-up tables, this convolution, and thereafter the prime-length DCT, could be performed quickly and accurately.

The team also described a new, efficient algorithm for decomposing the DCT—in mathematics, this means rewriting the problem in terms of a combination of simpler quantities. In addition to reducing the required size of read-only memory (ROM), the researchers found that overall their algorithm significantly reduced the computation time.

"We found that the proposed design involves significantly less area and it yields higher with less power consumption than the corresponding existing designs," says Meher. "The structure we propose is highly regular, modular and therefore suitable for Very Large Scale Integration realization."

More information: Xie, J., Meher, P. K. & He, J. Hardware-efficient realization of prime-length DCT based on distributed arithmetic. IEEE Transactions on Computers preprint, 6 March 2012 (doi: 10.1109/TC.2012.64). http://www.computer.org/csdl/trans/tc/preprint/ttc2012990042-abs.html

Related Stories

Afib triggered by a cell that resembles a pigment-producing skin cell

October 12, 2009

The source and mechanisms underlying the abnormal heart beats that initiate atrial fibrillation (Afib), the most common type of abnormal heart beat, have not been well determined. However, a group of researchers at the University ...

Peppers may increase energy expenditure in people trying to lose weight

April 27, 2010

Imagine your delight while enjoying your favorite Mexican food - perhaps a fully loaded bean burrito topped with an ample supply of thinly sliced jalepeno peppers. What happens when you bite into a few more peppers than you ...

New algorithm improves the way computers interpret readings of the brain’s electrical signals

May 30, 2011

Electroencephalography (EEG) records the electrical signals produced by the brain using an array of electrodes placed on the scalp. Computers use an algorithm called common spatial pattern (CSP) to translate these signals ...

The faster-than-fast Fourier transform

January 18, 2012

The Fourier transform is one of the most fundamental concepts in the information sciences. It’s a method for representing an irregular signal — such as the voltage fluctuations in the wire that connects an MP3 ...

Lowell's Large Monolithic Imager sees first light on the Discovery Channel Telescope

September 21, 2012

(Phys.org)—The Large Monolithic Imager (LMI), a camera built at Lowell Observatory and funded by the National Science Foundation (NSF), recently took a set of first-light images on Lowell's 4.3-m Discovery Channel Telescope ...

Quantum algorithm breakthrough

February 24, 2013

An international research group led by scientists from the University of Bristol, UK, and the University of Queensland, Australia, has demonstrated a quantum algorithm that performs a true calculation for the first time. ...

Recommended for you

Mapping coal's decline and the renewables' rise

June 23, 2016

Even as coal-fired power plants across the U.S. are shutting down in response to new environmental regulations and policy mandates, defenders of the emissions-heavy fuel still have cost on their side. Coal, after all, is ...

Driverless cars: Who gets protected? Study shows public deploys inconsistent ethics on safety issue

June 23, 2016

Driverless cars pose a quandary when it comes to safety. These autonomous vehicles are programmed with a set of safety rules, and it is not hard to construct a scenario in which those rules come into conflict with each other. ...

Electric racing car breaks world record

June 23, 2016

The Formula Student team at the Academic Motorsports Club Zurich (AMZ) accomplished its mission today: the grimsel electric racing car accelerated from 0 to 100 km/h in just 1.513 seconds and set a new world record. It reached ...

Flower power—photovoltaic cells replicate rose petals

June 24, 2016

With a surface resembling that of plants, solar cells improve light-harvesting and thus generate more power. Scientists of KIT (Karlsruhe Institute of Technology) reproduced the epidermal cells of rose petals that have particularly ...

Borophene could be an extraordinary sodium anode material for sodium-based batteries

June 24, 2016

Sodium-based batteries are a prospective alternative to lithium-based batteries due to the abundance and low price of sodium. However, finding a suitable anode material has been a longstanding hurdle to the commercialization ...

Computer sketches set to make online shopping much easier

June 24, 2016

A computer program that recognises sketches pioneered by scientists from Queen Mary University of London (QMUL) could help consumers shop more efficiently.