Article

The Undo Machine

by Dr. Howard Johnson. First printed in EDN magazine, January 6, 2011

"In the game of telephone," I explained to my friend Chris "Breathe" Frue, "a simple phrase successively whispered through a chain of people comes out hilariously distorted. 'Send reinforcements now' might turn into 'Cindy divorced Ming Chow'. In that game, you can never regain any information you lost at any stage. Linear electronics doesn't work that way."

"Are you suggesting that you can somehow undo the signal distortion that some of the time-invariant processes cause?" asked Breathe, a talented musician and audio technician who wants to learn more about equalizers.

"Within reason, yes," I replied. "That ability is the beauty of LTI [linear-time-invariant] processes, and the key to understanding all forms of equalization. You can undo almost all linear processes."

"Which ones can't you undo?" Breathe asked.

"In the audio world, if a graphic equalizer mildly attenuates one frequency band, you can boost it back later with another equalizer. But, if the first equalizer completely suppresses a band, setting its gain to zero, you cannot undo that action. You have lost the information in that band."

"Show me something you can undo," Breathe requested.

Let's examine the three-month running average," I said. "Financial advisors use this process to smooth variations in corporate profits." I drew the left side of Figure 1. "Each block on the left holds one data point. Each month, the data in the flow graph advances by one block. The constants next to each branch represent multiplicative gain factors. In any given month, this machine sums the three values on the left and then divides by three, making the three-month running average. If I feed this machine a single impulse, what do you suppose comes out?"

Breathe wrote a "one" next to the box labeled X_N and zeros next to the other two boxes. He slowly worked out the details. "When the impulse first arrives, it loads into the first box. On subsequent samples, the impulse propagates to the middle box and finally to the bottom box. In all three cases, the sum equals one. After those three samples, the impulse falls out of the last block and disappears. Taking into account the scaling factor, the output as it crosses the dotted line must read 1/3, 1/3, and 1/3, with zeros thereafter."

"Perfectly done," I said. "If I pump an unknown sequence through the machine, and all you see is its output, can you restore the original sequence?"

Breathe thought a bit and said, "The first value is easy. It comes straight through your machine unchanged except for the scale factor of 1/3, so just multiply it by three to find the answer. The second value is not too hard, either, because your machine hands me the sum of the first and second values. I already know the first, so I can subtract it from the sum to determine the second. After that point, I get confused."

"That's good," I said, completing the right side of the diagram. "Because my machine on the left uses three storage blocks, the undo machine needs three, as well. Starting with all zeros on the right, see how the first sample comes right through? The undo machine stuffs that sample into a series of delay blocks exactly like the first machine. At each subsequent step, whatever the first machine adds, the undo machine subtracts. The recovered output perfectly tracks the original input."

"Brilliant!" said Breathe. "How did you think of it?"

"I didn't. It's a standard IIR [infinite-impulse-response] filter. With enough delay blocks and suitable branch coefficients, you might use such a thing to undo an undesirable audio reverberation or fine-tune the response of a vintage phonograph recording. In my digital world, a similar structure forms the core of a decision-feedback equalizer. Using that device in a high-speed serial transceiver can undo the dispersive effect on signal transmission due to a long, lossy backplane trace. In all cases, the equalizer accomplishes the same thing: It simply undoes the effect of some LTI process" (Reference 1).

[Ed. note—Those of you who know way too much about DSP may recognize that the three-month running sum can be un-done only if one begins with the correct initial condition. That's because the impulse response (1, 1, 1) harbors poles in the Z-plane located exactly on the unit circle. In the time domain, that means that some sequences, if repeated forever, will produce a steady-state result that cannot be "un-done". It also means that some non-zero initial states, once loaded into the un-do machine, will circulate forever producing spurrious outputs. In practice, such situations are avoided by de-tuning the recovery machine by a slight degree to move its poles slightly inside unit circle, stabilizing the un-do process at the expense of a slight deterioration in un-do accuracy. In the present example, changing the feedback coefficients within the un-do machine from –1 and –1 to –0.99 and –0.98 would have that effect. No matter what initial conditions you use, after a few hundred cycles the machine stabilizes and gives answers accurate within a couple percent.]

Chris "Breathe" Frue is a talented musician and audio technician who wants to learn more about equalizers, a subject pertaining to both audio and high-speed digital systems.