Signals & Noise: August 1, 1996

Can the butterfly algorithm cure a medical-imaging application?

I enjoyed reading Michael Fleming's article, "Frequency-domain DSP: an enabling technology,"(EDN, March 28, 1996, pg 127), but one area left me a little confused. I understand how simple signal processing would be in the frequency domain, but I thought that the transformation to and from the frequency domain made the technique unemployable for real-time applications. Whether the butterfly algorithm improves the situation is not clear. What are the current practical limitations for frequency-domain processing of real-time signals? My application is in spatial and temporal filtering of high-resolution (512×512- to 1k×1k-pixel, 30-frame/sec) medical images. Is there any applicability of the butterfly technique here?

(Author Michael Fleming responds: Real time is generally measured by a DSP system's ability to process sampled data in a continuous fashion. For example, we can filter a continuous signal or an image using a FIR-filter structure that convolves the incoming signal with the desired filter's impulse response by performing a series of dot products. This same filter has an exact equivalent solution that uses frequency-domain butterfly techniques with the advantage of using the FFT to eliminate all the redundancies that were performed. This feature dramatically increases the system's real-time sample rate.

Generally, the FIR filter needs to multiply-accumulate each new sample by the entire length (N) of the filter's impulse response. Therefore, processing a sampled block of data of M length requires (M×N) multiply-accumulates. The FFT approach transforms the M block of data to the frequency domain, multiplies by the desired frequency response, and, if necessary, transforms the multiplied data back to the time domain. This approach generally involves only (M× log base 2(N)) number of multiplies. With the arrival of the multimedia age, the need to filter, compare, and enhance your 1k×1k-pixel images in real time places even more importance on processing performance. We can get millions of transistors on a chip. The true limitations of DSP-system performance lie in achieving desired functionality and data rates with minimum power dissipation and in avoiding the horrors of paralleling programmable DSP processors.

My company has designed 3-D 1k×1k×1k-pixel image filtering and pattern recognition in the frequency domain at 30 frames/sec. This calculates to acquiring and processing with high-level functionality more than 30 billion samples/sec with complex in-phase-and-quadrature relationships. This feat is difficult without the aid of high-speed FFT butterfly constructs.

More on the V-chip debate

As long as my children are in my home, I have a responsibility to raise them properly. Part of my responsibility is to exercise parental control over what they watch on television. They'll find out soon enough about all the crime and sex that occur in our world without my allowing them to use the television to watch it.

I support the V-chip requirement in new TVs for many of the same reasons that Steven H Leibson cites ("To V or not to V," April 25, 1996, pg 13). I am not convinced, however, that TV violence is the most pressing problem facing our country or the only problem that careful program selection might address. How about using similar technology to allow parents to screen out other undesirable content? For starters, I propose screening against racism, sexism, homophobia, consumerism, nationalism, and programs that glamorize cigarette smoking.

Heck, we might as well include the capability to block Rush Limbaugh, Republican political ads, and fundamentalist Christian TV programs. There is no reason why I can't subscribe to the American Civil Liberties Union's rating service, while others subscribe to ratings shaped by the Christian Coalition.

V-chip technology is not about censorship; it is about control. What can any sound, rational person have against controlling his environment? I just hope that I can use the V chip to filter out all of the talk shows.

Although I am sure that Leibson's V-chip position will generate some controversy, I think that most of the debate will stem from ignorance and emotionalism, not from rational thinking. This situation reminds me of when parents and legislators wanted to add warnings to recordings containing explicit song lyrics. The musicians screamed "censorship," but all they showed is that they don't know what censorship is. No one kept them from producing and selling their music, and no one is preventing TV producers from making whatever type of show they want. There is a good possibility that TV advertising revenues may drop, however. But, advertising revenues were never protected by the Constitution.

As a parent, I might appreciate the V chip as a tool to help control what my children view. As an opponent of censorship, I recognize that censorship proponents will abuse this technology by pressuring broadcasters to eliminate all programming containing any violent or sexual content that offends their intolerant sensibilities.

Correction

Due to an editorial error, we listed an incorrect e-mail address for Michael Fleming (EDN, March 28, 1996, pg 127). The correct address is mfleming@pacifier.com.