Signal Recovery Method and Apparatus

1. Field of the Invention

The present invention generally relates to the field of signal recovery, and, more particularly, to a method and apparatus using a programmed digital computer to compute the locations in time of the peaks of a generally sinusoidal signal waveform in especially high noise-to-signal ratio environments. The invention is especially useful in determining phase shift for a head-to-magnetic recording medium interface or in data reconstruction of low amplitude signals.

2. Description of the Prior Art

In the application of detecting a phase shift in a noisy signal, the conventional approach has been to differentiate the input noisy signal and detect the zero crossings of the differentiated signal. This technique is generally illustrated in FIG. 1 of the drawings, wherein the input noisy signal is represented by curve 10, whereas the signal represented by curve 11 is obtained by differentiating the input noisy signal. It will be observed that the zero crossings of the curve 11 occur at each of the maximums of the input signal. This conventional technique works well where the noise-to-signal ratio is relatively low. However, in environments where the noise may be as high as 30-50%, the result of differentiating the noisy signal is to produce a signal that has many spurious zero crossings. This is illustrated in FIG. 2, wherein the input noisy signal is represented by curve 13, and curve 14 represents the differentiated signal. Because of the many zero crossings of the differentiated signal, it becomes impossible to correctly identify the peaks of the noisy signal.

While the reconstruction of information from an input noisy signal having an especially high noise-to-signal ratio presents a slightly different problem from that of detecting phase shift, the same sort of information useful in detecting phase shift can also be used to reconstruct the information signal. In other words, if the locations of the peaks of the input noisy signal can be determined with reasonable accuracy, it is then possible to reconstruct from this data the original information signal.

Therefore, the broad object of this invention is to provide an improved method and apparatus for accurately locating the signal peaks in a generally sinusoidal waveform wherein the noise-to-signal ratio is especially high.

A more specific object of the invention is to provide such a method and apparatus wherein the voltage levels at sampled points of the waveforms are compared to identify linear portions of the waveform. The intersection of respective straight lines drawn through these linear portions locates the times of occurrence of the signal peaks in the input noisy waveform.

The foregoing objects of the invention are attained by periodically sampling the input noisy signal. The signal samples are digitized and supplied to a programmed digital computer. Each digitized input to the digital computer represents the ordinate of the corresponding sampling point of the input noisy signal, the abscissa being the sampling time. As a result, the sequence of digitized inputs to the programmed digital computer represents the coordinates of a time sequence of points at which the noisy signal is sampled. The digital computer is programmed to compare the ordinates of successive points to determine whether the change in value of the ordinates is in the same direction. At such time as the change in value of the ordinates reverses in direction, the computer determines if a sufficient number of points has been accumulated to that point in time to permit a least squares straight line curve-fitting subroutine to be employed. If so, the least squares straight line curve-fitting subroutine generates an output which represents the Y intercept and the slope of the straight line through the sampled points. This process is repeated, and assuming that the slope of the next computed straight line has the opposite sign of the just-preceding computed straight line, then two simultaneous linear equations are defined by the outputs of the least squares straight line subroutine. These simultaneous linear equations can be solved to identify the abscissa of the coordinates of the signal peak. In other words, solution of the simultaneous linear equations provides an output which identifies the time of occurrence of the signal peak. Recognizing that a series of straight lines having slopes which alternate in sign describes a generally triangular waveform, it is possible then to calculate the input signal amplitude at the peak, assuming that the input signal with the noise removed is generally sinusoidal in shape. Alternatively, digital data generated by the programmed digital computer and representing a sequence of coordinates defining the triangular waveform signal can be read out to a digital-to-analog converter which then produces an analog triangular waveform signal. The resulting analog triangular waveform signal is supplied to a low-pass filter which provides at its output the recovered signal.

FIG. 1 is a graphical representation of a noisy signal and the differentiated signal illustrating the conventional method of detecting the location of peaks in the noisy signal.

FIG. 2 is a graphical representation of a noisy signal having an especially high noise-to-signal ratio and of the differentiation of that signal to illustrate the failure of the conventional method to detect the location of the peaks in the noisy signal.

FIG. 3 illustrates a generally sinusoidal waveform useful in explaining the basic technique according to the invention.

FIG. 4 is a block diagram of an apparatus for implementing the invention.

FIG. 5 is a flow diagram illustrating the program employed by the programmed general computer which is a part of the apparatus according to the invention shown in FIG. 4.

FIG. 6 is a representation of an actual computer printout showing a noisy input signal waveform and a computed triangular waveform having peaks corresponding to the peaks in the input noisy signal.

The principle of the invention will be described with reference to the generally sinusoidal waveform 16 graphically illustrated in FIG. 3. The input signal voltage is periodically sampled at points separated by fixed time interval .DELTA.t. The voltage obtained at each sampling time defines the ordinate, and the time at which the sample is taken defines the abscissa of a point on the signal waveform. Thus, the coordinates of successive points on the waveform are accumulated, and each point in succession is tested to determine if there is a monotonic increase or decrease in the voltage--i.e., a change in the sign of the slope of the waveform--such as occurs at a peak in the waveform.

When a change in the sign of the slope of the waveform is detected, a least squares fit of a straight line to the accumulated points is obtained, provided that a sufficient number of points has been accumulated. In practice, thirteen (13) points have been found to provide sufficient accuracy; however, the exact number of points selected will depend in part on the input signal waveform and the sampling time period. The result will be a straight line 17 which will closely follow the most linear portion of the input waveform between the peaks 18 and 19, for example.

It will be understood, of course, that the waveform illustrated in FIG. 3 is a very smooth waveform having well-defined peaks. A waveform having an especially high noise-to-signal ratio, such as that illustrated in FIG. 2, will not have well-defined peaks, but instead the peaks will be more or less obliterated by the noise, thereby resulting in either no peak or many peaks. As a result, the most linear part of the signal waveform will be in the vicinity of the base line cross-over region, which is the part of the waveform that is the least affected by the noise. Moreover, this part of the signal waveform will be more consistent over a period of time than the impinging noise. Once the line 17 has been established, the same process is repeated to establish the next line 20 between the peaks 19 and 21. These two lines, for example, can be expressed as follows:

where:

m.sub.1 and m.sub.2 are the slopes of lines 17 and 20, respectively; and

b.sub.1 and b.sub.2 are the Y intercepts of the lines 17 and 20, respectively.

The solution of these two simultaneous linear equations provides the coordinates of the point 22 of intersection of the two lines. The abscissa of the point 22 is the time of occurrence of the peak 19. The ordinate of the point 22, while not being equal to the amplitude of the peak 19, can be used to calculate a close approximation of the amplitude of the peak 19. More specifically, it can be shown that the amplitude of the triangular waveform defined by the successive lines, including lines 17 and 20, is approximately 1.507 times the amplitude of the sinusoidal waveform 16. The process just described to locate the abscissa of the peak 19 is repeated to locate the abscissa, or time of occurrence, of the peak 21 and successive peaks of the waveform 16.

FIG. 4 shows a block diagram of an apparatus for signal recovery based on the technique described with respect to FIG. 3. The noisy input signal is applied through a switch 24 to a sample-and-hold circuit 25. The sampling period is determined by the output of a clock 26 which is externally synchronized. For example, if the input noisy signal is derived from a magnetic recording medium, say a disk memory, then the synchronization signal to the clock can be generated by a tachometer connected to the disk spindle. The voltage samples temporarily stored in the sample-and-hold circuit 25 are then digitized by an analog-to-digital converter 27 and supplied to a programmed digital computer 28, both of which receive the clock signals generated by the clock 26.

FIG. 5 shows the flow diagram for the program for the programmed digital computer 28. The program is based on APL (A Programming Language) and may, for example, employ the APL package available from International Business Machine Corporation (IBM) and identified as APL Statistical Library for APL SB and APL CMS (5796-PGQ) and for VS APL (5796-PHW). This statistical library includes all of the subroutines required in the program illustrated in flow diagram form in FIG. 5.

Now, with particular reference to FIG. 5, at the beginning of the program, the computer counters and memory matrices are initialized to begin receiving the digitized data from the analog-to-digital converter 27. The first question asked in the flow diagram is whether the input waveform is sufficiently smooth to perform the recovery operation according to the invention. Assuming for the moment that no smoothing routine is required, the next question is whether a slope change has been detected. In other words, each sampled point is compared with the preceding points to detect when a change in sign of the slope of the waveform occurs. The detection of such change in sign of slope is the end of the sequence of the points which defines a section of the waveform that either monotonically increases or decreases. When the end of the sequence has been detected, the number of points in the sequence is tested to determine if enough points have been accumulated for a least squares straight line fit. For example, thirteen (13) points can be arbitrarily chosen as the criterion as to whether enough points have been accumulated. If fewer than thirteen (13) points have been accumulated, then the program returns to the accumulation and testing of points of the next sequence. If, however a sufficient number of points, thirteen (13) or greater in our example, has been accumulated, then these points are used in a least squares straight line fitting subroutine. The output of the subroutine is data defining the slope and Y intercept of the least squares straight line fit.

The next step in the program is to test the slope of this line with the slope of the just-preceding computed line. If the slopes are opposite in sign, then we know that the two lines are intersecting and between different peaks of the input signal waveform. However, if the slopes are of the same sign, then it is assumed that the two lines are really a continuum between the same two peaks of the input waveform. In this event, the program returns to testing and accumulating points in the sampled sequence. Assuming that the slope of the line just computed is opposite to that of the preceding line computed, then the slope and Y intercept of this line is stored in the memory matrix.

At this point in time, either one of two things can be done. Either the data defining each of the computed lines--i.e., slopes and Y intercepts--can be accumulated in memory and, subsequently, this data read out to solve the series of simultaneous linear equations which will define the times of occurrence of the peaks in the input signal waveform, or the simultaneous linear equations can be solved as each straight line fit is computed. The latter approach, of course, permits real time or on-the-fly operation. However, in the program illustrated by the flow diagram in FIG. 5, the solutions of the series of simultaneous linear equations takes place after all of the input data have been evaluated.

The program illustrated by the flow diagram in FIG. 5 includes two refinements which are useful in cases of extremely high noise levels. Returning to the first question in the flow diagram, the input voltage waveform is first tested to determine if it is sufficiently smooth for the signal recovery technique according to the invention. This can be done by testing the sign reversals of the changes in the sampled voltage levels of the input waveform. If a predetermined number of sign reversals occur within a given time period, then the input data will go through a binomial smoothing subroutine. A second test for smoothness is made at the end of the line calculations. More specifically, the line computed by the least squares straight line fit is tested by application of a correlation coefficient to the slope of the calculated line. This is done by comparison to the actual sampled data in the same range. If the correlation coefficient falls below some predetermined value, such as 0.9, then the program is set for the binomial smoothing subroutine. In this way, extra peaks in very noisy signals are eliminated.

It will be understood by those skilled in the art, however, that some of the operations performed digitally can, in a given application, be performed by analog methods. For example, the binomial smoothing subroutine employed in the flow diagram of the program illustrated in FIG. 5 can be replaced by an analog filter. For example, if it is determined that the input data to the programmed digital computer requires smoothing, then a control signal can be generated by the digital computer 28 to control the input switch 24. The switch 24 then supplies the input noisy signal to a low-pass filter 29 before supplying the signal to the sample-and-hold circuit 25.

Returning now to the flow diagram of the program illustrated in FIG. 5, at such time as all of the input data have been used to calculate the series of straight line approximations, then the slope and Y intercept data are read out of memory to calculate both the time of occurrence and the amplitude--i.e., the coordinates of the intersections of the series of straight lines. Before this is done, however, one final test may be made on the computed data to determine if the data is good or not. This test is again a correlation coefficient test, and if a sufficient value of correlation is not achieved, then an error message is generated to indicate that the input data is too noisy and the signal cannot be recovered. On the other hand, if the correlation coefficient is sufficiently high, then the times of occurrence and amplitudes of the peaks of the triangular wave represented by the intersecting straight lines are computed. FIG. 6 illustrates in graphical form the results of this calculation. In FIG. 6, the noisy input signal 33 is approximated by a triangular waveform signal 34 composed of a series of intersecting straight lines. As previously mentioned, the amplitudes of the peaks of the triangular waveform can be divided by a factor of 1.507 to derive a measure of the amplitudes of the peaks of the input waveform.

Referring again to FIG. 4, the computed output data from the programmed digital computer 28 can be supplied to a digital-to-analog converter 30 to generate an output analog signal. The nature of this analog signal will depend on the data supplied by the programmed digital computer 28. For example, if the computer 28 calculates the amplitudes of the input waveform, the output of the digital-to-analog converter 30 would be the recovered signal. On the other hand, it would be possible for the computer 28 to supply data which define the triangular waveform formed by the series of intersecting straight lines. In this case, the analog signal waveform of the digital-to-analog converter 30 would be a triangular waveform signal, and this signal could be supplied to the low-pass filter 31, which would provide a generally sinusoidal output as the recovered signal.

The following is a computer printout of the computer program represented by the flow diagram shown in FIG. 5. ##SPC1##