Error Detection and Correction System

1. Field of the Invention

This invention relates to error reduction in communications systems, and more particularly to receiver-based error reduction in systems having variable signal channel quality.

2. Description of the Prior Art

In the continuing search for more reliable communications systems, many different approaches have been tried. One very useful approach has been to make use of a process of sampling and quantizing, which converts continuous scales of time and amplitude, respectively, into discrete scales, permitting representation of the signal by a finite number of quantized coded symbols. As described in U.S. Pat. No. 2,681,385, issued to B. M. Oliver on June 15, 1954, sampling alone does not entail any loss of information if the sampling frequency is at least twice as great as the highest frequency of interest in the information signal. Furthermore, quantization does not cause a serious loss of information if the number of quantizing levels is sufficiently high.

The quantized coded signals are normally transmitted across an information channel, i.e., from transmitter to receiver, in binary coded form. Such a coded signal consists of a timewise serial train of pulses and spaces representing "high" (or "1") and "low" (or "0") states, respectively. Each pulse and space constitutes a "bit" of the binary code, and n bits in time sequence constitutes an n bit "word". Thus, for example, a "three-bit" binary coded signal consists of a sequence of "three-bit" words, each of which represents a quantum level of the sampled and quantized input analog signal.

An error in the state of one of the binary word bits can cause a very large error in the resulting output quantum level. For example, a transmission error in the leftmost bit of the transmitted binary word 1001 representing the decimal quantum value 9 would result in the word being received as the binary word 0001 representing the decimal quantum value 1. Single bit errors in received binary coded signals can thus cause serious distortion of the receiver output analog signal.

Much progress has been made in bit error detection and correction apparatus for quantized coded information transmission systems. The common approaches used include: (1) repetition of data techniques; (2) transmission over multiple channels; and (3) parity checking with error detecting codes. Each of these approaches requires additional equipment at both the transmitter and receiver. Examples of such systems are found in U.S. Pat. No. 3,444,516, issued to Joseph W. Lechleider on May 13, 1969, and U.S. Pat. No. 3,475,723, issued to Herbert O. Burton on Oct. 28, 1969.

Solely receiver-located error detection and correction is desirable, since it avoids the need for more complex transmitters. The article "Average and Median Based Smoothing Techniques for Improving Digital Speech Quality in the Presence of Transmission Errors," IEEE Transactions on Communications, Volume 24, pages 1043-1045, September, 1976, discloses receiver-located smoothing techniques for noise attenuation in signals from digital channels with relatively high error probability.

The article "Detection and Partial Correction of Isolated Errors from the Received Data in a 1st-Order D.P.C.M. CODEC," by R. Steele and M. A. Yeoman, Electronics Letters, Volume 11, No. 11, pages 230-232, May, 1975, discloses a slope-limited transmission and reception system which senses and partially modifies high divergent data points in a received signal based on its deviation from the known slope limitations of the transmitted signal. In this slope limited system, however, the analog signal must be sampled appreciably above the Nyquist rate. When a highly divergent data point is detected, the deviant sample is replaced by the value of the most recent preceding reconstructed sample which does not violate the slope limitations of the transmitted signal. The reconstructed samples constitute the output of a slope-limited differential pulse code modulator located in the receiver.

It is an object of the present invention to provide an improved arrangement for receiver-located error detection and correction wherein a received signal sampled at or above the Nyquist rate is selectively corrected by a smoothing filter only when apparent errors have been detected.

The invention is directed to an error detection and correction system located at the receiving end of an information channel. An error reducing circuit receives a sequence of signals and divides said sequence of signals into a plurality of groups and into a plurality of subgroups. A first signal representative of the deviations among the signals of each group is generated as well as a second signal representative of the deviations among the signals of each subgroup. A third signal corresponding to the difference between said second signal and said first signal is compared with a predetermined threshold signal. Responsive to said third signal exceeding said threshold signal, a corrector is introduced to alter the received signals so that said third signal becomes less than said threshold signal.

In one embodiment of the present invention, means are provided for measuring the correlation coefficients of both a large group of quantized sampled codes, e.g., 64, and a much smaller included subgroup, e.g., 8. These correlation coefficients are then compared. If the subgroup correlation coefficient is determined to be larger than a predetermined acceptable deviation from the correlation coefficient of the large group, a smoothing filter is temporarily introduced to change the subgroup codes to more closely match the correlation coefficient of the subgroup with the correlation coefficient of the large group which includes the subgroup.

In another embodiment of the present invention, the RMS value of the difference between successive received samples of a relatively large group of quantized sampled codes are measured. The differences between immediately successive group samples are then compared with the already determined RMS value for the group. If any of these individual differences are unacceptably divergent from the group RMS value, a smoothing filter is temporarily introduced to substitute a value for the divergent sample which is more closely matched to the group's RMS value.

In both embodiments, the quality of a high error content received signal is significantly improved while there is little or no degradation of a low error content received signal.

FIG. 1 shows an overall block diagram of an embodiment illustrative of the invention in which difference detection and correction is used;

FIG. 2 shows a detailed diagram of "absolute value of successive differences" circuit 103 of FIG. 1;

FIG. 3A shows the clock generator and countdown circuitry for producing the necessary timing pulses for the circuit of FIG. 1;

FIG. 3B shows the timing waveforms of the circuit of FIG. 3A;

FIG. 4 shows a detailed diagram of absolute value of difference circuit 112 of FIG. 1;

FIG. 5 shows a block diagram of the median filter 121 of FIG. 1;

FIGS. 6A through E illustrate the effect of the difference detection and correction system on a received signal with an erroneous data point due to a transmission error; and

FIG. 7 shows a block diagram of another embodiment illustrative of the invention in which sliding block correlation error detection and correction is used.

FIG. 1 shows a block diagram of an error detection and correction system illustrative of the invention in which the RMS value of differences among a large group of coded signals is compared with the values of differences between immediately successive coded signals. A sequence of serial binary coded signals are applied from a transmission channel to lead 101 at a bit rate of 48 kilobits per second. Each coded signal constitutes a serial six-bit binary code so that the code or word rate is 8 kiloHertz. The serial coded signals from lead 101 are applied to both serial-to-parallel converter 102 and shift register 113. The parallel code output of serial-to-parallel converter 102 is clocked into absolute difference circuit 103. Circuit 103 generates a signal .DELTA.X.sub.n, corresponding to the absolute value of the difference between successive pairs of codes, e.g., X.sub.n, X.sub.n+1, coming from serial to parallel converter 102 (i.e., .DELTA.X.sub.n = .vertline.X.sub.n -X.sub.n+1 .vertline.). Difference value signals .DELTA.X.sub.n are then applied to digital-to-analog converter 104 which transforms the .DELTA.X.sub.n codes into an analog difference signal. The analog output signal of digital-to-analog converter 104 is applied to the input of amplifier 105 which increases the analog signal by a factor L. The scaled analog difference signal from the output of amplifier 105 is applied to RMS value generator 106 which produces a signal, V.sub.RMS, representative of the root mean square (RMS) value of the scaled analog differences, i.e., ##EQU1## RMS generator 106 may be the AD531K multifunction converter module described in Analog Devices Corporation Technical Bulletin "IC Programmable Multiplier Divider Computation Circuit," pages 1-8, or any other similar devices well known in the art. The RMS value signal V.sub.RMS from generator 106 is supplied to a sample and hold circuit 107 wherein it is sampled once every 64 words responsive to the CLK3 clock signal.

The coded signal sequence on lead 101 is also applied to shift register 113 which acts as a 64-bit delay. The delayed coded signal output of shift register 113 is serially inserted into shift register 114. Shift register 114 acts as a serial-to-parallel converter and provides a sequence of parallel coded signals to median filter 121 via cable 122. Shift register 114 is also operative to delay each serial coded input signal by six bits and to supply the delayed serial coded signal to both line 115 and to the input of shift register 116 via line 135. Shift register 116 includes a serial-to-parallel converter and provides a parallel coded signal to median filter 121 via cable 123 responsive to each serial coded signal from register 114. Shift register 116 is also operative to delay the serial coded signals applied thereto by six bits and to transfer the delayed serial codes to line 117. The parallel output codes of shift register 116 are also transmitted via cable 125 to absolute differencing circuit 112. The signal on line 118 is applied to the input of shift register 119 via error replacement logic circuit 131. The parallel output of shift register 119 is transmitted via cable 124 to the median filter 121, via cable 134 to digital-to-analog converter 127, and via cable 126 to absolute differencing circuit 112. The signal from shift register 119 on line 134 constitutes the output digital signal of the system. This digital signal is transmitted to D-A inverter 127 and through low pass filter 128 to produce the analog output signal of the system on line 133.

Absolute differencing circuit 112 generates a signal representative of absolute value of the difference of the signals applied thereto from cables 126 and 125. The signal on cable 126 from shift register 119 represents the current digital output signal. The signal on cable 125 from shift register 116 constitutes the next succeeding received code word. The output of differencing circuit 112 is converted into an analog level by digital-to-analog converter 111. The output analog signal of digital-to-analog converter 111 is transmitted via line 109 to comparator 110, where it is compared with the scaled RMS value signal from sample and hold circuit 107 on line 108. Thus, the scaled RMS value of the absolute value of successive differences of a large block of input codes is compared on a sample-by-sample basis with the absolute value of the difference of the quantized current digital signal S.sub.n contained in shift register 119 and the next possible output digital signal S.sub.n+1 contained in shift register 116. If the absolute value of the difference of the signals contained in these shift registers .vertline.S.sub.n+1 - S.sub.n .vertline. is larger than the RMS value of the absolute value of successive differences of the quantized signal taken over the large signal block, S.sub.n+1 is considered erroneous and the comparator 110 sends an error signal P1 to the error replacement logic circuit 131.

Median filter 121 then picks the middle value of S.sub.n from register 114, S.sub.n+1 from register 116, and S.sub.n+2 from register 114 and transmits the selected middle value via the error replacement logic circuit to shift register 119 to replace the erroneous signal, S.sub.n+1, with the selected middle signal S.sub.n or S.sub.n+2 which is closer to the correct value. The output signal P1 of comparator 110, on line 130, is "high" (1) when the output signal of D-A converter 111 is higher than the scaled RMS signal on line 108. If the scaled RMS value signal on line 108 is larger than the output signal of D-A converter 111, the output P1 of comparator 110 is "low" (0). When signal P1 is low, there has been no error detected and the error replacement logic circuit 131 transmits the data S.sub.n+1 from register 116 on line 117, via NAND gate 604, directly to line 118. The signal in shift register 119 is then replaced by the signal from shift register 116. When S.sub.n+1 from register 116 is entered into register 119 via replacement logic 131, the system has not used the median filter and has passed the received signal S.sub.n+1 to the output digital-to-analog converter 127.

If P1 from comparator 110 is high, indicating that the system has detected an error, the serial signal S.sub.n+2 on line 115 from shift register 114, or the signal S.sub.n line 120 from shift register 119 is sent to line 118. In this manner, signal S.sub.n+1 from register 116 is replaced by signal S.sub.n+2 from register 114 or the signal S.sub.n is recirculated in shift register 119. The output Z1 of the median filter circuit 121 determines whether a replacement by S.sub.n+2 or recirculation of S.sub.n will occur. When Z1 is high, the signal on line 115 in selected, thus replacing the previous signal S.sub.n in shift register 119 with the signal S.sub.n+2 presently in shift register 114. If Z1 is low, the signal S.sub.n in shift register 119 is recirculated. In either case, when P1 is high, the signal S.sub.n+1 in shift register 116, which has been determined by the system to contain an error, is discarded. Thus, when an error is detected in the signal in shift register 116, the next output word is selected from the signal in either shift register 119 or shift register 114. The replacement choice is based upon the median filter rule embodied in circuit 121 (FIG. 5).

FIG. 3A shows the pulse generator and frequency divider circuits for producing the necessary timing pulses for the system of FIG. 1. Circuit 700 is an astable multivibrator operating at a frequency of 48 kiloHertz. The output of multivibrator 700 on line 701 is CLK1. Inverter 702 produces CLK1 on line 703. The CLK1 signal frequency is divided by six in frequency divider 704 which provides the CLK2 signal on line 705. The CLK2 signal is inverted by inverter 706 to provide the CLK2 signal on line 707. The CLK2 signal frequency is divided by 64 in frequency divider 708, thus providing the CLK3 signal on line 709. CLK3 is inverted by inverter 710 to provide CLK3 on line 711. CLK1 constitutes the bit clock, CLK2 is the word clock, and CLK3 represents the block clock. The relationship of these timing waveforms are illustrated in FIG. 3B.

FIG. 2 is a detailed diagram of the "absolute value of successive differences" circuit 103 of FIG. 1. FIG. 2 shows two shift registers 201 and 202 which contain the value of each of two successive received coded signal words. The words in register 202 are subtracted from the word in register 201 in subtraction circuit 214. The output of register 201 on line 203 is applied to the input of register 202. Register 201 receives the parallel output code of serial-to-parallel converter 102 via cable 132. The output of register 201 is transmitted by data cable 204 to inverter 205. The output of inverter 205 on line 206 is supplied to six-bit binary adder 207. The output of register 202 is sent via cable 208 to the other input of binary adder 207. The magnitude output of binary adder 207, on cable 209, is applied as one input to "exclusive OR" network 210. The other input of the "exclusive OR" network is the sign bit from binary adder 207 on line 211. The output of the "exclusive OR" network 310 is thus the inverted absolute value of the difference of the outputs of register 201 and register 202. Inverter 213 inverts the signal on cable 212 to provide a binary representation of the absolute value of the difference of the output signal values of registers 201 and 202. This difference signal appears on cable 215.

FIG. 4 is also an absolute value of differences circuit whose operation is essentially the same as the circuit of FIG. 2 except that the input signals to shift registers 401 and 402 arrive simultaneously from different sources instead of arriving sequentially from the same source. The input to shift register 401 is on cable 125 coming from shift register 116, and the input to shift register 402 is on cable 126 coming from shift register 119. The output of shift register 401 on line 403 is added to the inverted output of shift register 402 on line 404 by adder 405. The magnitude of this sum on cable 406 and its sign bit on line 407 constitute the inputs to the "exclusive OR" network 408. The inverted output of the "exclusive OR" network on cable 409 is the absolute value of the difference of the input signals on lines 125 and 126.

FIG. 5 shows a diagram of a smoothing filter, which in this case is median filter 121. This median filter is operative to select the middle value of a group of three input values S.sub.n+2, S.sub.n+1, and S.sub.n. There are three magnitude comparators in the median filter: M1, M2, and M3.

The inputs to magnitude comparator M1 are S.sub.n on cable 124 from register 119 and S.sub.n+2 on cable 122 from register 114. Output N2 of comparator M1 on cable 511, is low (0) when the value of the signal S.sub.n on cable 124 is less than S.sub.n+2 on cable 122, otherwise N2 is high (1). Inputs to magnitude comparator M2 are S.sub.n+1 on cable 123 from register 116 and S.sub.n+2 on cable 122 from register 114; and output N3 of magnitude comparator M2 on cable 512 is 0 when the signal value S.sub.n+1 in shift register 116 on cable 123 is less than S.sub.n+2 in shift register 114 on cable 122; otherwise N3 is 1. The inputs to magnitude comparator M3 are S.sub.n on cable 124 and S.sub.n+1 on cable 123; and the N2 output of comparator M3 appears on cable 510. N1 is 0 when the signal value S.sub.n in shift register 119 is less than S.sub.n+1 in shift register 116, otherwise N1 is 1. The N1, N2, and N3 of comparators M3, M1, and M2, respectively, are inputs to logic network L1 consisting of inverters 513, 514, and 515 and NAND gates 516, 517, and 518. Logic network L1 functions so that its output Z1 is 0 if N1 is 0, N2 is 1, and N3 is 1 or if N1 is 1, N2 is 0, and N3 is 1. Z1 is 1 if N1 and N2 are 0 and N3 is 1 or if N1 and N2 are 1 and N3 is 0. Comparators M1, M2, and M3 in conjunction with the logic network L1 operate to select the middle value of the three adjacent parallel signal words S.sub.n+2, S.sub.n+1, and S.sub.n contained in shift registers 114, 116, and 119, respectively. For example, if S.sub.n+1 > S.sub.n > S.sub.n+2, N1 equals 0, N2 equals 1, and N3 equals 1, and the output Z1 is 0. The output of logic network L1 from gate 518 is applied to storage register 519 which register provides word synchronization for the median filter network. The output Z1 of register 519 appears on line 129. If Z1 is 1 the error replacement logic circuit 131 causes the data S.sub.n+2 in shift register 114 to replace the data S.sub.n in shift register 119. When Z1 is 0, the data S.sub.n in shift register 119 is recirculated. Thus a largely divergent quantized received signal S.sub.n+1 is to be sensed as an error and is to be replaced by one of its immediately adjacent quantized signals which more nearly approximates the correct transmitted signal value.

The "error replacement logic" circuit 131 of FIG. 1 consists of inverters 605 and 606, and NAND gates 601, 602, 603, and 604. There are five inputs to the error replacement logic block, three of which, lines 115, 120, and 117, are serial data lines and two of which, lines 129 and 130, are control lines. The output of the error replacement logic circuit, line 118, is the serial data line that is connected to the input to shift register 119. One of the three data inputs S.sub.n, S.sub.n+1, and S.sub.n+2 is selected by the combination of the two control inputs. One of S.sub.n, S.sub.n+1, and S.sub.n+2 is sent to the shift register 119 according to Table I.

For example, when P1 is 1, indicating an error, and Z1 is 0, indicating that the contents of shift register 119 should be recirculated, the error replacement logic circuit will transmit the signal S.sub.n on line 120 directly to the input of shift register 119 via line 118, and lines 115 and 117 will have no effect on shift register 119.

For purposes of illustration, consider the example depicted in FIGS. 6A through 6E. FIG. 6A shows an analog input signal corresponding to the ramp function V.sub.A (t) = 2 .times. 10.sup.3 .times. t. Signal V.sub.A (t) is sampled and quantized as indicated in FIG. 6B (Qs(t)) and transmitted in coded from. The received signal, Q.sub.R (t) corresponding to V.sub.A (t), contains an error S.sub.n+1 as shown in FIG. 6C. When the quantized signal Q.sub.R (t) is applied to the system of FIG. 1, the erroneous data point will be detected and replaced by a value closer to the transmitted value.

The binary serially coded quantized signal applied at input lead 101 is converted to a parallel coded quantized signal by the serial-to-parallel converter 102. The signal is then transmitted via parallel data cable 132 to circuit 103 which generates the absolute value of the differences between the successive parallel data points as they are received. This output is converted to an analog signal by digital-to-analog converter 104 and is then scaled by a factor L by amplifier 105. RMS value generator circuit 106 then produces an output signal corresponding to the RMS value of the waveform shown in FIG. 6D calculated over a time interval of 8 milliseconds (i.e., the time for 64 coded words) and scaled by a factor of L. If, for this example, L is equal to 4, then the RMS value signal appearing at the output of circuit 106 will be slightly greater than 8 quantum units at the end of 64 coded words, i.e., 8 milliseconds. The RMS value signal is sampled at the end of each 64 words and this value is stored in sampled and hold circuit 107 for use in comparator 110.

Simultaneously, the binary serially coded quantized signal applied at input lead 101 is transmitted through shift registers 113, 114, 116, and 119. When the erroneous signal S.sub.n+1 reaches register 116, its value is compared with the value of the immediately preceding signal S.sub.n, which has already been placed in shift register 119. S.sub.n+1 and S.sub.n are compared in comparator 112 which generates the absolute value of the difference of its two input signals. In this example, this difference, .vertline.S.sub.n+1 - S.sub.n .vertline., is 16 quantum units. This difference value is converted to an analog signal by digital-to-analog converter 111 and is transmitted to the other input of comparator 110. Comparator 110 compares the RMS value signal from sample and hold circuit 107 and the difference output from converter 111 and senses that the output of digital-to-analog converter 111 is larger than the scaled RMS value contained in sample and hold circuit 107. Accordingly, comparator 110 generates an "error" signal P1 = 1 on line 130.

The median filter 121 simultaneously determines that the middle value S.sub.n+2 of the signals S.sub.n, S.sub.n+1, S.sub.n+2 contained in shift registers 119, 116, and 114 respectively, is in shift register 114. Consequently the Z1 output of median filter 121 (1) is applied to error replacement logic circuit 131 via line 129. Responsive to control signals P1 = 1 and Z1 = 1, error replacement logic circuit 131 connects the output of shift register 114 to the input of shift register 119 via gates 603 and 604 so that the next output of shift register 119 will be S.sub.n+1 from shift register 114. The effect of this operation illustrated in FIG. 6E in which the corrected signal value S.sub.n+2 much closer to the true value of the transmitted signal replaces the erroneous data point S.sub.n+1 of FIG. 6C. In accordance with the invention, error correction is performed only on signals having higher than expected deviations. Other signals are unaltered.

FIG. 7 shows a block diagram of another embodiment illustrative of the invention which utilizes "sliding block correlation" error detection and correction. The quantized input data is applied to line 701 and is temporarily stored in shift register 702. This same data is also applied to the input to the correlation coefficient generator 703. The output correlation coefficients b and R.sub.j of generator 703 are computed over data blocks of two different lengths. The coefficient b is computed over a long block of samples, providing an estimate of the local correlation of the sample values q(t) of that block as described by the "short term" autocorrelation equation: ##EQU2## Coefficients R.sub.j constitute a sequence of "short term" autocorrelation coefficients computed for a plurality of shorter blocks contained within the above-mentioned long block i.e., ##EQU3## where T.sub.2 < T.sub.1. Methods and means for generating these correlation coefficients are well known in the art, e.g., U.S. Pat. No. 2,854,191 issued to Gordon Raisbeck on Sept. 30, 1958. The coefficient b is scaled by the factor K by multiplier 707. The resultant scale coefficient. Kb, appearing on line 708, is compared in comparator 709 with each small block correlation coefficient R.sub.j contained within the large block over which coefficient b was generated. Whenever one of the small block coefficients, R.sub.j, is less than the quantity Kb, comparator 709 produces an error signal which is applied via line 710 to switch control 717 to actuate the switch. Responsive to the error signal, line 715 is disconnected from line 713 and is connected to line 714 from the output of median filter 712. When line 715 is connected to line 714, the signal on line 715 is the output of the median filter rather than the delayed input signal from register 702. As described with respect to the circuit of FIG. 1, the output of the median filter is the value of the sample which is the median of the "error sample" and its two adjacent samples. This median filter output signal is applied to low pass filter 716 via line 715 to be substituted for the erroneous signal. The analog signal from filter 716 on line 718 constitutes the corrected output signal. If the next value of R.sub.j is not less than the quantity Kb, the comparator will send a "no error" signal to the switch control 717, thus causing the switch to return to its normal position connecting line 713 to line 715. Switch control 717 remains in its normal position until another error signal is generated by the comparator. The error threshold level is controlled by the signal K. An increase in K will cause the system to be more sensitive to sudden deviations in the input signal. Thus, the system can be adjusted for the desired error sensitivity, depending on the expected nature of the input signal as well as the quality of the transmission channel.

While the invention has been explained and described with reference to preferred embodiments thereof, numerous modifications thereof will be readily apparent to those skilled in the art without departing from the spirit and scope of the invention.