1. The Field of the Invention
This invention relates to the fields of communication, control, and signal processing engineering, specifically to the design of equalizers to compensate for the undesired frequency response of a system. Some of the related fields include 330/304, 333/28, 340/825.71, 375/229, and 700/44.
2. Background Information
In the fields of communication and signal processing engineering, equalizers are widely used to adjust the amplitude and the frequency spectrum of input signals, to compensate for the limited bandwidth or the undesired dynamics of a physical system such as a communication channel. For example, in many audio playback systems, pre-equalizers are used to modify the relative amplitudes at different frequency bands of the audio source signal (e.g., from a play out of a audio compact-disk player), to compensate for the non-ideal frequency response of the audio amplifier and the audio speaker, such that the human listener can hear less distorted sound versus the originally recorded sound in the audio compact-disk. In many audio recording systems, post-equalizers are used to compensate for the undesired frequency response of the microphone, before the audio signal is physically recorded on the recording media. FIG. 1A and FIG. 2A show examples for designing a post-equalizer and a pre-equalizer, respectively.
In the field of control engineering, pre-equalizers are interchangeably referred as pre-filters, feed-forward filters, command-shaping filters, input-shaping filters, and feed-forward controllers. For example, pre-equalizers are used in the positioning control of the read/write heads of data storage systems, such as a hard-disk drive or an optical-disk drive used in a modern personal computer. The position seeking commands are filtered by a pre-equalized before being sent to drive the voice-coil actuator. The pre-equalizer suppresses the spectrum contents of the seeking command that are located close to the resonant frequencies of the voice-coil actuator and the mechanical structure supporting the read/write head, in order to reduce the oscillatory response of the resulting positioning trajectory, and the induced vibration due to the resonant modes.
As another example: In the semiconductor manufacturing equipment industry, equipment engineers are responsible for improving the performances of many subsystems from various vendors, while integrating them into a larger manufacturing machine. Usually these subsystems already have feedback controllers provided by their vendors. For example, in a photo-lithography exposure machine, it is typical to find a temperature control system, wafer stage control system, and a vibration control system, etc. The said equipment engineers may find these controllers only provide moderate system performances. In this case, instead of replacing the feedback controllers immediately, the feed-forward controller is preferred during the initial redesign process, because it can be used in parallel with the existing feedback controllers. The said equipment engineers can measure the dynamic response of the original subsystems, and then design a feed-forward controller to improve its performances.
Ideally, an equalizer could be designed to simply inverse all the undesired dynamics of the physical system, such that the dynamics of the compensated system is satisfactory. In practice, many factors constrain the feasibility of this method. For example, the undesired dynamics may contain an unstable zero, whose inversion results in an unstable pole in the equalizer which causes the system response to diverge. The undesired dynamics may have more poles than zeros, such that its inverse is non-causal, which is not desirable if future input is not known in advance. In addition, pole-zero cancellation only works well when an accurate parametric model of the system is available. Furthermore, even if a perfect inversion equalizer can be implemented, the physical limit on actuator efforts and the presence of noise can severely degrade the performance of the compensated system.
In general, there are at least four factors to consider when designing an equalizer: 1. the tradeoff between different performance objectives; 2. the awareness of the input signals entering the equalizer in advanced; 3. the availability of an accurate parametric model of the physical system to be equalized; 4. the computational efficiency of the design algorithms.
The tradeoff between different performance objectives is common in many engineering design problems. In the case of designing pre-equalizers, the tradeoff between the performance of the equalized response and the magnitude of actuating signals entering the physical systems is fundamental as in most control systems. For example in FIG. 1B, the channel H can represent the combined dynamics of an audio amplifier and an audio speaker in the afford-mentioned audio system. There is a physical saturation limit on the amplitude of the signal u coming into the amplifier. Therefore when designing the pre-equalizer Q, both z1, which is the difference between the desired output d and the equalized channel output, and z2, which is the equalizer output signal u, need to be minimized. A performance tradeoff between the two objectives is necessary. In the case of post-equalizers, the tradeoff between the performance of the equalized response and the amplification of noise is fundamental as in most communication systems. For example in FIG. 1A, H can represent the dynamics of an audio recording channel from the sound being recorded to the microphone output. Because the electrical signal coming from a microphone is typically weak, some noise w2 will be added due to the requirement of high-gain amplification. The level and the spectrum of the noise need to be considered. Otherwise, the post-equalizer Q can significantly amplify the noise such that the audio signal w1 is indistinguishable. Therefore, it is desirable that a design algorithm provides some tradeoff capability between multiple performance objectives.
If the input signals to a system are know in advance, instead of designing a pre-equalizer, a set of optimal shaped commands can be directly computed by the method in [Tuttle, et al, U.S. Pat. No. 6,694,196, Feb. 17, 2004], and [S. Boyd, et al, “Control applications of nonlinear convex programming,” Journal of Process Control, 8(5–6):313–324, 1998]. Similarly, in the application of post-compensating a non-perfect communication channel, if all the signals coming out of the communication channel are already known, the original signal can optimally estimated directly without designing a post-equalizer first, using basic least-square estimation techniques shown in [T. Kailath et al, Linear Estimation, 2000].
However, there are many cases when there is not much known about the input signal in advance, or when it is impractical to employ all the possible input command into the design of the feed-forward filter or the shaped input command. In these cases, the designer can not formulate exact constraint equations which specify the limit of the equalized system output, because the equalized system output depends on both the system dynamics and the input command. For example, in the afford-mentioned audio pre-equalizer application, because the audio signals stored on different audio compact disks are different from each other, it should not be considered as known in advance when designing the audio pre-equalizer in practice. In addition, for an audio compact disk storing 74 minutes of two-channel audio digitally sampled at 44.1 kilo-hertz, there are about 196 million samples of data per channel. Solving an optimization problem at such dimension is almost infeasible in practice. Another example is designing the feed-forward controller for the photo-lithography mask writer used in semiconductor manufacturing. For a 30 mm-by-20 mm exposure field with a 10 nanometer grid, there are about 12-tera pixels need to be written to a photo mask. Although the locations of these pixels are known in advance, the problem dimension is so large that it is impractical to apply convex optimization techniques.
In short, when the input signal can not be known in advance, the afford-mentioned approaches to directly optimize the shaped commands or signal estimation can not work. Therefore, an equalizer should be used. Furthermore, performance constraints should be specified in the frequency-domainin such case. These call for a need for designing frequency-shaping equalizers.
Many of the prior arts concerning equalizer design require a parametric model (e.g., a transfer function in the pole-zero form) of the system under control. The parametric model usually comes from applying model fitting to the data obtained by performing an input-output test on the system. For systems with complicated dynamics, some mismatch between the resulting parametric model and the actual dynamic behavior of the system can be significant. For a design algorithm that uses such parametric models, the resulting system performance can be significantly different from what is predicted in the design phase. Therefore, it is desirable that an equalizer design algorithm can directly incorporate the input-output test data of the system to be equalized. One type of such input-output test data is the frequency response measurement at a set of selected frequencies. For a linear time invariant system, it can be measured accurately, no matter how complicated the system dynamics is. It is desired to directly incorporate the frequency response data in the equalizer design process.
Furthermore, the computational efficiency of an equalizer design method should be considered. For a low-cost embedded computer system, the processing power and the available memory are usually quite limited. In addition, if the equalizer needs to be redesigned periodically possibly due to the change of dynamics, it is desirable that the computation algorithm involved is as simple and efficient as possible.
Among some of the prior arts related to the equalizers designs, the zero phase error tracking control proposed in [M. Tomizuka, “Zero phase error tracking algorithm for digital control,” ASME J. Dynamic Systems, Measurement, and Control, vol. 109, no. 1, pp. 65–68, 1987] is capable of handling non-minimum-phase zeros, and it can have some optimal preview action for input commands that can be known in advance. However, it requires a parametric system model, and it does not provide a means to tradeoff between equalized performance and control efforts. The input-shaping technique [N. Singer and W. Seering, “Pre-shaping command inputs to reduce sys-tem vibration,” ASME J. of Dynamic Systems, Measurement, and Control, Vol. 112, March 1990, and Singer, et. al. U.S. Pat. No. 4,916,635, Apr. 10, 1990 and U.S. Pat. No. 5,638,267, Jun. 10, 1997] can be used to generate a FIR (finite impulse response) filter to cancel the unwanted vibration modes of a system, when the input command is known in advance. It does not require a parametric model of the system. However, there is no means for afford-mentioned performance tradeoff. Many standard methods for designing both IIR and FIR digital equalizer are presented in [A. Oppenheim and R. Schafer, Discrete-Time Signal Processing, 2nd ed. 1999]. None of them provide a means for afford-mentioned performance tradeoff between different input-output channels.
Adaptive signal processing techniques can be used to design post equalizers as shown in [B. Widrow et al, Adaptive Signal Processing, 1985], and to design pre-equalizers as shown in [B. Widrow and E. Walach, Adaptive Inverse Control, Prentice Hall, 1996]. Essentially no prior knowledge about the system dynamics is required, due to the use of adaptive algorithms. It tracks the dynamics variation of slow-varying systems. The adaptive algorithm itself is quite simple. However, it dose not provide performance tradeoff capabilities.
In [T. C. Tsao, “Optimal feed-forward digital tracking controller design,” ASME J. Dynamic Systems, Measurement., and Control, vol. 116, no. 4, pp. 583–592, 1994], the pre-equalizer design problem is transformed to a model-matching control problem in the frequency domain, by re-drawing block-diagrams to formulate a generalized control design block diagram as shown in FIG. 1C. Examples of formulating a generalized control design block diagram can be found in many control engineering textbook, such as [S. Skogestad et al, Multivariable Feedback Control, 1996], [S. Boyd et al, Linear Controller Design: Limits of Performance. Prentice-Hall, 1991], and [K. Zhou, Essentials of Robust Control, 1998]. Performance tradeoff in the frequency domain is possible. However, it can not directly incorporate the frequency response measurement. In [Giusto and F. Paganini, “Robust synthesis of feed-forward compensators,” IEEE Transactions on Automatic Control, 44(8), August 1999], a frequency-domain robust synthesis approach is proposed to deal with modeling errors in terms of structured model uncertainty in a robust synthesis framework. The curve-fitting errors to measured frequency data can be incorporated. However, it is well known in the robust control community that the computation algorithm, known as μ-synthesis, is complicated, and its convergence can be quite slow.
Convex optimization techniques can be applied to optimally design multi-object frequency-shaping equalizers with frequency response data incorporated directly. Some of the related prior work includes [B. Rafaely et al, “H2/H∞ active control of sound in a headrest: design and implementation,” IEEE Trans. Control System Technology, vol. 7, no. 1, Jan. 1999][P. Titterton, “Practical method for constrained-optimization controller design: H2 or H∞ optimization with multiple H2 and/or H∞ constraints,” IEEE Proceedings of ASILO 1996][P. Titterton, “Practical multi-constraint H∞ controller synthesis from time-domain data,” International J. of Robust and Nonlinear Control, vol. 6, 413–430, 1996][S. P. Wu et al, “FIR filter design via spectral factorization and convex optimization,” in Applied Computational Control, Signal and Communications, 1997][K. Tsai et al, “DQIT: μ-synthesis without D-Scale Fitting,” American Control Conference 2002, pp. 493–498][S. Boyd et al, Linear Controller Design: Limits of Performance. Prentice-Hall, 1991] and [S. Boyd et al, “A new CAD method and associated architectures for linear controllers,” IEEE Transactions on Automatic Control, vol. 33, p. 268, 1988].
The method starts with transforming equalizer design problems to a generalized control design block diagram as shown in FIG. 1C, in general using a technique known as Q-parameterization or Youla-parameterization. Both of the pre-equalizer and the post-equalizer design problems in FIG. 1B and FIG. 1A can be easily transformed by simply redrawing block diagrams. FIG. 2 shows the general case that includes the design of pre-equalizers, post-equalizers, and feedback controllers in the same framework. When feedback control is needed, a stabilizer J stabilize the system, while the equalizer Q is used to adjust the system response without causing instability, as long as Q itself is stable. The system 210, which is the combination of P and J. is equivalent to the system N in FIG. 1C. Once the design problem has been transformed to the form in FIG. 1C, it can be shown that in the frequency domain, the exogenous output z is related to the exogenous input w as z=(Nzw+NzyQNuw)w, where Nzw is the sub-part of N transferring from w to z, N is the sub-part of N transferring from y to z, and Nuw is the sub-part of N transferring from w to u. The important aspect is that at each frequency, the equalized, closed-loop transfer matrix from w to z is (Nzw+NzyQNuw), which is convex in terms of the frequency response of Q at the same frequency, the equalizer to be designed. Therefore, frequency-shaping specifications and the tradeoff between different input-output channels can be specified as convex objectives and convex constraints when formulating a multi-objective optimization problem. In addition, the frequency response data of Nzw, Nzy, and Nuw can be incorporated without curve-fitting them first.
Although there is no single prior-art publication explaining all the details of each step involved, FIG. 3 shows a typical flowchart of this approach, which assembles each of the steps distributed in the afford-mentioned prior-art publications. First in step 310, the block diagram in the form of FIG. 1c is determined, and input-output channels for performance tradeoff are specified. In step 320, frequency-shaping performance specifications are specified on their corresponding input-output channels at a set of selected frequencies, and a multi-objective convex optimization problem is defined. In step 330, the frequency response data of Nzw, Nzy, and Nuw, at a set of selected frequencies, are incorporated into the equalized transfer matrix Nzw+NzyQNuw. In step 340, the convex optimization problem is solved to simultaneously optimize all the magnitude and the phases of the equalizer Q at the selected frequencies. In step 350, the equalizers coefficients are derived from the magnitudes and phases by either using curve-fitting, or by computing their inverse discrete Fourier transform.
The convex optimization method mentioned above will provide a solution of the equalizer Q that approaches the globally optimal equalizer as long as the degree of freedom of Q is large enough, and the number of selected frequencies is sufficient. For example, if Q has a finite impulse response (FIR) structure, the degree of freedom of Q is related to the number of FIR taps to be optimized. The sufficiency of the number of selected frequencies is to reduce the ripple of frequency response in-between adjacent selected frequencies.
Unfortunately, the dimension of the optimization problem grows significantly with the degree of freedom of Q, and the number of frequencies selected. In general, significant computational resources are required in step 340, even though many efficient convex optimization algorithms have been proposed. When the equalizer decision variables are specified as the coefficients of the FIR taps, they need to be related to the equalizers frequency response by discrete Fourier transform in order to formulate the performance constraint equations in the frequency domain. Similarly, when the equalizer decision variables are specified as the real part and the complex part of the sampled frequency response of the equalizer, they need to be related to each other by the Hilbert transformation relation such that they correspond to the frequency response of a causal and stable system. These transform relations make the decision variables couple to each other, and hence the problem dimension grows with the number of selected frequencies and the number of the equalizer decision variables. Some examples can be found in [K. Tsai et al, “DQIT: μ-synthesis without D-Scale Fitting,” American Control Conference 2002, pp. 493–498]. Solving such kind of large-dimension optimization problems usually requires a high-performance computer with sufficient memory. Therefore, it is not easy to implement the method in FIG. 3 in a low-cost embedded system, or for real-time equalizer adaptations as shown in [B. Widrow and E. Walach, Adaptive Inverse Control, Prentice Hall, 1996, chapter 8 to 10].
Concluding the discussions so far: For the cases when the input signal can not be known or can not be practically treated as known in advance, what is desired for a feed-forward filter design approach is to formulate the design problem in the frequency domain, and to allow the designer to compensate for the undesired system frequency response as much as possible, while limiting the actuator effort in the frequency domain to a reasonable amount. It gives the designer the ability to tradeoff between the actuator effort and the system performance without knowing the detail of the input command. In addition, it is desired that the approach does not require a parametric model (such as an infinite-impulse-response transfer function) of the system, instead just employ the frequency response data of the system directly, which can be measured accurately. Therefore, the actual system performance with the implemented equalizer can be less sensitive to the modeling or curve-fitting errors. This can be done by directly incorporating the accurately measured system frequency response in the design process without the loss of fidelity due to parametric model fitting. These requirements can be satisfied by applying afford-mentioned multi-objective convex optimization technique to optimize the equalized transfer matrix (Nzw+NzyQNuw) at a set of frequencies. This in general solves the multi-objective frequency-shaping design problems for pre-equalizers, post-equalizers, and even the equalizers in FIG. 2 for feedback control. Unfortunately, the dimension of the optimization problem grows significantly with the number of frequencies selected and the number of the equalizer decision variables to be optimized. Therefore, it is not easy to implement such method in a low-cost embedded computer system. The invention discloses methods to decouple the dependency between equalizer decision-variables, which makes it highly efficient to implement, comparing to the afford-mentioned convex optimization method.
USPTO Backgrounds
USPTO Backgrounds