System and Method for Restoring a Clipped Signal

1. Field of the Invention:

The present invention relates generally to restoration of a band-limited signal by signal processing techniques. More particularly, it relates to a system and method for such signal restoration that utilizes inequality constraints in order to restore the signals more accurately.

2. Description of the Prior Art:

Signal interpolation and extrapolation arise in many signal processing applications. The basic problem is to construct unknown signal samples from known samples, using the fact that the signal is band-limited, plus perhaps other information. Example applications include recovering from drop-outs in a digital audio tape, signal reconstruction after nonlinear removal of impulsive noise, and signal inference from incomplete measurements.

A sizeable literature exists on the topics of interpolation and extrapolation. When the known samples of the signal are uniform and sufficiently dense in time that the sample spacing is less than half the period of the highest frequency in the signal, band-limited interpolation provides a unique reconstruction for all time. Band-limited interpolation can be seen as replacing the known samples by a superposition of sinc functions each having spectral width equal to the signal bandwidth.

When the Nyquist sampling theorem is violated, it becomes necessary to use extrapolation techniques. Because every finite-bandwidth signal is analytic, a band-limited signal can be extrapolated for all time from any open set. The extrapolation is simply a Taylor series expansion about any point in the set. However, incompletely sampled signals cannot be so extrapolated. Extrapolation over missing, nonzero samples requires more information than the signal band limits.

A large number of extrapolation techniques construct the unique minimum norm signal which interpolates the known samples and satisfies the band-limited condition. Usually the L.sub.2 norm is minimized, yielding a minimum energy extrapolation. Minimum-norm extrapolation of lowpass signals provides a reconstruction very similar to that obtained using band-limited interpolation where zeros have been inserted for the missing samples; i.e., the extrapolation tends to go to zero after an interval approximately equal to the reciprocal of the assumed signal bandwidth. This seems reasonable when the extrapolation is viewed as a superposition of sinc functions corresponding to the signal bandwidth, along with a second-order correction that adjusts the sinc function heights so as to precisely match the known samples.

Some extrapolation techniques have been devised to make use of other a priori knowledge besides bandwidth. For example, weighting functions can be introduced in both the time and frequency domains to alter the relative strength of norm minimization versus time and frequency. Linear prediction has also been used to extrapolate the signal on the basis of correlation information measured using the available samples. In general, any known properties of the signal can help to improve the quality of its restoration from an incomplete set of samples.

Useful clipped signal restoration may be achieved through use of the novel system and method for restoring a clipped signal herein disclosed. A system for restoring at least an approximation of a clipped signal in accordance with this invention has a signal restorer employing inequality constraints. A means supplies the clipped signal to said signal restorer. A means supplies inequality constraints to the signal restorer. A means supplies known information about the original signal in a form which can include weighting matrices to the signal restorer. The signal restorer is configured to utilize the supplied inequality constraints and known information to restore the clipped signal.

A method for restoring at least an approximation of a clipped signal in accordance with the invention includes supplying the clipped signal to a signal restorer. Inequality constraints are supplied to the signal restorer. Known information about the original signal is supplied to the signal restorer. The supplied inequality constraints and known information are used by the signal restorer to restore the clipped signal.

Toward the attainment of the foregoing, the following and related advantages and features of the invention should be more readily apparent to those skilled in the art, after review of the following more detailed description of the invention, taken together with the drawings:

FIGS. 1-6 are waveform diagrams useful for understanding the invention.

FIG. 7 is a generalized block diagram of a system in accordance with the invention.

FIGS. 8A and 8B are a more detailed block diagram of the system of FIG. 7 and waveform diagrams useful for understanding operation of the FIG. 8A system.

FIG. 9 is a waveform diagram useful for further understanding of the invention.

FIG. 10 is a block diagram of another embodiment of a system in accordance with the invention for restoring the signal shown in the waveform diagram of FIG. 9.

FIG. 11 is a waveform diagram useful for further understanding of the invention.

FIG. 12 is a block diagram of another embodiment of a system in accordance with the invention for restoring the signal shown in the waveform diagram of FIG. 11.

FIG. 13 is a waveform diagram useful for further understanding of the invention.

FIG. 14 is a block diagram of another embodiment of a system in accordance with the invention.

FIG. 15 is a block diagram of another embodiment of a system in accordance with the invention for restoring the signal shown in the waveform diagram of FIG. 13.

FIGS. 16-21 are waveform diagrams presenting results obtained with the invention.

The problem considered here may be stated as follows (see FIG. 1). A band-limited signal s(t) is amplitude limited, resulting in the clipped signal c(t), ##EQU1## Given samples of c(t), knowledge of the band occupied by s(t), and knowledge of the amplitude limiting characteristic it is desired to recover s(t).

Denote by c(i) the ith sample of the clipped signal, and by c the column matrix containing the N clipped signal samples. Similarly, s and r denote the original signal and the restored signals. Knowledge of c and the frequency band occupied by s imposes the following constraints on the restored signal r. ##EQU2## where 1 is a vector containing all ones, and L is the clipping threshold. Above, T.sub.s projects onto the space of known samples; it is obtained from the N.times.N identity matrix by deleting rows corresponding to the unknown (i.e. clipped) samples. The constraint (2) then states that unclipped samples in c are matched by the corresponding samples in r. The matrices T+and T-, in a manner similar to that of T.sub.s, select samples corresponding to samples of c which have been limited to the positive threshold L and the negative threshold -L, respectively. Note that in general the clipping characteristic, and therefore the inequality contraints (3) may be a function of the signal. Conditions (2) and (3) ensure that if r were clipped, it would coincide with c. The matrix B.sup..perp. is defined as I-B, where B projects onto the space of signals which are band-limited to the assumed spectral support of s(t); it may be obtained from the DFT matrix by zeroing rows corresponding to out-of-band frequencies. Accordingly, the constraint (4) requires the reconstruction r to be band-limited.

The question arises as to whether the constraints (2)-(4) are sufficient to specify a unique reconstruction r? If not, what is the nature of the space of signals matching the constraints?

Denote by N.sub.c the number of clipped samples, and by N.sub.b the dimension of the space of band-limited signals, i.e. the rank of B or the number of nonzero DFT bins. Then the number of "unknowns" in this problem is N.sub.c while the number of "constraints" is N-N.sub.b (considering only constraints arising from the band-limited assumption). Thus, if N.sub.c >N-N.sub.b, the reconstruction is not unique. The addition of the amplitude constraints (3) can dramatically reduce the size of this admissible solution space, leaving a set of solutions much closer to the true signal.

We write the restored signal as the sum of the clipped signal and the unknown samples z,

T.sub.c being an N.times.N.sub.c matrix (consisting of columns of .+-.I) which distributes the unknown samples to the appropriate (clipped) sample times, negating entries corresponding to negative amplitudes. This formulation guarantees constraint (2) by construction, and the remaining constraints (3) and (4) on the N samples of r now reduce to the following constraints on the N.sub.c samples of z.

As is clear from (7), when the rank of B.sup..perp. T.sub.c is N.sub.c or greater, the reconstruction is uniquely specified. Uniqueness of the reconstruction (without the need for amplitude constraints) is likely when clipping is slight (large L) or the signal is heavily over-sampled; i.e., when there are at least as many zeros in the DFT of s as there are clipped samples. This situation is illustrated in FIG. 2 in which the original and clipped signals and their spectra are shown along with the restored signal and its spectrum. Note that even though 70% of the samples have been clipped, the signal s is uniquely and accurately restored by making use of the knowledge that the signal c is sampled at four times the Nyquist rate.

Should the rank of B.sup..perp. T.sub.c be less than N.sub.c, the restoration r will not be unique. In this case the linear constraints on z (6)-(7) form a convex polytope of dimension N.sub.c rank (B.sup..perp.). The polytope specified by (6)-(7) is bounded in all but degenerate cases, and is therefore a convex polyhedron.

That the space of unknown samples z is in general bounded means that the space of possible restorations r is bounded. That is, at any given sample, (6) and (7) place upper and lower limits on the value attained by that sample. This is in sharp contrast to the case of interpolation through missing samples, in which the reconstruction may take on virtually any value at missing samples, should the constraints (2) and (4) fail to uniquely specify the signal.

We illustrate this result using the example shown in FIG. 3. In the bottom portion of the figure, the original and clipped signals appear along with a restored signal. The restored signal is the band-limited signal of minimum energy which passes through the known signal points; it was not constrained to exceed the clipping threshold at the unknown samples, and in fact it doesn't.

For this example, after applying the band-limiting and signal matching constraints, there remain three degrees of freedom in choosing a reconstruction. In the upper portion of FIG. 3, three signals appear which are zero at known sample times and are properly band-limited. Ignoring momentarily the inequality constraints z.gtoreq.0, any amount of any of these three signals added to the restoration shown is also a valid restoration. In the absence of the inequality constraints, therefore, signals may be constructed which have various amplitudes at clipped sample points while meeting all bandwidth and signal matching constraints. For this reason, in the case of missing samples as opposed to clipped, a minimum energy or other minimum norm criterion is generally imposed to select a unique reconstruction.

On the other hand, in the presence of the inequality constraints (6), the reconstructed signal is typically limited to a bounded convex subspace in the space of N-long sampled signals. For the signal considered in FIG. 3, these limits are shown in FIG. 4. It still remains to choose a particular reconstruction from among those available, as discussed below.

As illustrated in FIG. 5 for the case of two unknown samples with one degree of freedom, the reconstruction must lie on a polyhedron, in this case a line segment. Several choices for the unknown samples are shown. The z with minimum L.sub..infin. norm will minimize the maximum added amplitude. Picking z to have minimum weighted L.sub.1 or L.sub.2 norm will result in restorations having L.sub.1 or L.sub.2 weighted norm.

In any event, the constraint forms a convex subspace over which any convex signal norm achieves a global minimum. In the case of the L.sub.1 norm, the computationally efficient simplex method may be used to compute r. For the L.sub.2 and L.sub..infin. norms, computationally efficient procedures are also available.

In FIG. 6, the minimum and maximum energy restorations for the example of FIG. 3 are shown. Note that these restorations do not coincide with the limits of the reconstruction envelope.

Should s be noisy, it may have energy outside the signal band. In addition, unclipped signal samples will be perturbed. In this case the equality and inequality constraints above should be relaxed. We propose computing r as an approximately band-limited signal, passing close to the known signal samples, while maintaining the amplitude constraints at the clipped samples.

FIG. 7 shows a signal restorer 10 with its inputs and outputs. The signal to be restored is supplied at input 12. Inequality constraints, such as clipping characteristic applied to the signal are supplied at input 14. Such inequality constraints may be based on the assumption, for example, that amplification of the original signal is linear over its amplitude, but attenuated at the clipping level. If the amplification is nonlinear and known, the inverse of the nonlinear function is applied. The inequality constraints could be essentially any parameterized signal constraint applied to the original signal. The third input at 16 embodies other known information about the original signal, such as its bandwidth or spectral shape. Spectral or temporal weighting in the form of weighting matrices appropriate to the signal due to its nature are used. The known information may be based on physical reasons for preferring certain signal restoration solutions. Such additional information identifies a family of signals that would meet the inequality constraints to produce the signal to be restored. The signal restorer 10 functions to select a signal representing the restored signal supplied as output 18 from such a family of signals.

FIGS. 8A and 8B show details of one form of the signal restorer 10 of FIG. 7. Signal 20 to be restored at 12 is supplied to a segmenter 22, which separates the signal into segments 24, 26 and 28. Segment length and overlap inputs are supplied to the segmenter 22 at 30. The signal segments 24, 26 and 28 are supplied from the segmenter 22 to constrained optimizer 32 at 34. The inequality constraints and weighting inputs are supplied at 14 and 16 to the optimizer 32. The optimizer 32 restores the signal segments 24, 26 and 28 separately to give restored signal segments 36, 38 and 40, which are supplied at 42 to cross fader 44. The cross fader 44 attenuates the restored signal segments 36, 38 and 40 at their beginning and end to avoid redundancy when the segments are overlapped to produce the restored signal. The shape of cross fade window 46 and the amount of segment 36, 38 and 40 overlap for the restored signal are supplied to the cross fader 44 at 48. The shape shown for the cross fade window 46 also reflects the fact that the center part of the segments 36, 38 and 40 is of most interest for restoration. The cross fader produces attenuated restored signal segments 50, 52 and 54, which are delayed at 56 and summed at 58 to produce the restored signal.

In the constrained optimizer 32, a first method uses the sample variables governed by Equation (5) discussed above. Unclipped samples are matched by construction. The variable z, and therefore the restored signal r, is found by constrained optimization as follows: ##EQU3## Here, J.sub.(z) is given by .parallel.r.parallel..sub.W, the weighted norm of the restored signal. If the L.sub.1 norm is chosen, since z.gtoreq.0, the minimization problem becomes ##EQU4## which may be solved using the simplex method or other computationally efficient linear programming methods. Using the L.sub.2 norm, J(z) becomes the weighted energy in the restored signal. Using the L.sub..infin. norm, the restored signal is the one minimizing the maximum deviation.

Note that if B.sup..perp. T.sub.c has full column rank (generally true when N.sub.c <N-N.sub.b), then the band limiting constraint determines the solution. (N.sub.c is the number of clipped samples, N is the number of samples and N.sub.b is the signal bandwidth.) Otherwise,

where (B.sup..perp. T.sub.c) c is the minimum norm solution to B.sup.195 T.sub.c z=c, Q is an orthnormal matrix spanning the null space of (B.sup..perp. T.sub.c) and .alpha. is a column of constants to be determined. Since the columns of Q are orthogonal, band limited and zero at known sample values, the minimization problem is easily reformulated in terms of .alpha..

A second method for the constrained optimizer 32 uses a band limited basis or "additive synthesis." In the relationship

.GAMMA. is the band limited basis (truncated or windowed sinc functions work well) and x represents unknown coefficients. Note that .GAMMA.(.GAMMA..sup.T .GAMMA.).sup.-1 .GAMMA..sup.T =B, where B is a projection onto band limited signals. By construction, the restored signal is band limited. The optimization becomes ##EQU5## where the cost function to be minimized is

The same sorts of solutions as used in the first method are applicable.

Both the first and the second methods fail when the original signal contains energy outside the band. In both, the equality constraint cannot be met. In the second method, the equality constraint may be loosened by adding it to the cost function: ##EQU6## However, this may fail since {x:T.sub.c (Bx-c).gtoreq.0} may be the empty set.

A third, hybrid approach is preferred in the case that the signal contains out-of-band components. The restored signal is band limited by construction ##EQU7## where the cost J(z) is given by

the L.sub.2 norm being preferred. The first term in J(z) represents weighted signal energy, and the second term represents weighted error in matching the unclipped samples. A solution always exists since the constraints specify a non empty convex set and the cost is convex in z.

The weighting W may be chosen to emphasize certain frequency or time components over others. It may be desired to minimize the bandwidth of the restored signal and W would be chosen as, say, W=FDF.sup.T,F being the Fourier transform matrix and D emphasizing high frequencies over low ones.

The weighting V may be used to emphasize the fit to certain unclipped samples over others. It is used in cross fading to de-weight the fit at the signal block boundaries. After any non-linear transformation of the data, as in FIG. 9, the measurement noise is a function of signal amplitude. V may be adjusted to accomodate such variations:

where .sigma..sub.i.sup.2 is the variance of the noise of sample i. For the case of FIG. 9,

where .sigma..sup.2 is measurement variance, which may be set to 1 for weighting. Noise which is correlated from sample to sample may be similarly handled.

In FIG. 9, signal 60 is clipped at level .+-.L and has a known measurement non-linearity. As shown in FIG. 10, the clipped signal 60 has the inverse .phi..sup.-1 (x) of the non-linearity applied to it at 62 and undergoes restoration in signal restorer 64. Additional inputs to the signal restorer 64 are .differential..phi..sup.-1 /.differential.x, used to determine the weighting V and .phi..sup.-1 (L), the clipping level.

FIG. 11 shows a signal 66 with compressing-type nonlinearity. Near x=0, .phi.(x).apprxeq.x. Away from x=0, .vertline..phi..vertline. has a negative second derivative approaching maximum absolute levels. FIG. 12 shows restoration of the clipped and compressed signal 66. Digital clipping is carried out at 68 in the range over which .phi. is approximately linear. The signal is then restored at 70 using the third (hybrid) method discussed above.

Note that for .phi.(x) as in FIG. 11,

Also, .phi.(s(t)) will have greater bandwidth than s(t). Therefore, if the details of .phi. were note that unknown to an extent that simply inverting the measurement nonlinearity is inappropriate, the following formulation may be useful. ##EQU8## W is set such that the first term to the right is a measure of bandwidth, W being a "weak" high-pass filter. For the second term to the right, the restored signal should match the input at small signal levels, and not so much so at high signal levels. V should be set accordingly. As above, if the L.sub.2 norm is used, standard quadratic programming methods may be employed to specify z.

FIG. 13 shows a clipping nonlinearity 72 with hysteresis. If the signal 72 has hysteresis, the methods above can be used, accounting for the hysteresis by adjusting the clipping levels and weighting matrices to be sensitive to the signal derivative, i.e., which part of the hysteresis curve the signal 72 is in. In the case of restoring magnetic media clipping, the hysteresis curve may be determined.

FIG. 14 shows use of the invention in a digital recording application. A voice input from microphone 80 undergoes signal conditioning at 82 and low-pass (antialiasing) filtering at 84. The resulting signal is converted to digital form with A/D converter 86. The resulting signal may be clipped and is therefore supplied to signal restorer 88. The digital signal is also supplied for signal limit measurement at 90 to provide a limit measurement to the signal restorer 88 at 92. An additional weighting input determined by f.sub.c and the signal conditioning is provided to the signal restorer 88 at 94.

FIG. 15 shows restoration of a signal from a magnetic tape deck 96. The signal is digitized at A/D converter 98 and supplied to limiter 100. The output of the limiter 100 is supplied to detector 102 for determining inequality constraints and to signal restorer 104. The inequality constraints are supplied to the signal restorer 104 at 106, along with magnetic tape parameters, such as hysteresis, equalization and the like at 108.

FIGS. 16-21 show results obtained with restoration of an original signal 110 in the form of 1 second of recorded speech, which was clipped as shown at 112. In FIG. 17, original spectrum 114 falls off more than clipped spectrum 116. FIG. 18 shows detail of the original signal 110 and the clipped signal 112 at about the 0.5 second point (see also FIG. 16). FIG. 19 shows the original signal 110, clipped signal 112 at the 0.2 level, and a restored signal 118 (delineated by circles) obtained using conventional interpolation techniques based on selection of the minimum energy signal. FIG. 20 shows the original signal 110, clipped signal 112 and a restored signal 120 obtained using inequality constraints in accordance with the invention. As can be seen, the restored signal 120 matches the original signal 110 much more closely than does the restored signal 118. FIG. 21 shows this result quantitatively, with the x's representing the results for the conventionally restored signal 118.

It should be apparent to those skilled in the art that various changes in form and details of the invention as shown and described may be made. It is intended that such changes be included within the spirit and scope of the claims appended hereto.