WO1989008360A1

WO1989008360A1 - An adaptive detection method for quantized signals

Info

Publication number: WO1989008360A1
Application number: PCT/FI1989/000037
Authority: WO
Inventors: Teuvo Kohonen
Original assignee: Nokia Oyj
Current assignee: Nokia Oyj
Priority date: 1988-03-04
Filing date: 1989-03-03
Publication date: 1989-09-08
Anticipated expiration: 1990-09-04
Also published as: AU4074389A; GB2233865A; GB2233865B; GB9018361D0; JPH03503234A; FI881007A0; JP2806584B2

Abstract

The invention is generally concerned with an adaptive detection method for quantized signals having nominal values which at different moments define a finite set of discrete states, wherein the discrete state of a signal at a certain moment is interpreted by comparing the sample value of the signal to a set of reference numbers, on the basis of which the recognition of the signal state takes place. According to the principle of the method the values of the reference numbers used in the detection are corrected adaptively towards the actual signal states of the signal to be detected by, e.g., a k-means clustering method or by self-organizing feature maps.

Description

An adaptive detection method for quantized signals

The invention relates to an adaptive detection method for quantized signals having nominal values which at different moments define a finite set of discrete states, in which method the discrete state of a signal at a certain moment is interpreted by comparing the sample value of the signal to a set of reference numbers, on the basis of which the recognition of the signal state takes place.

In practice, the transmission path in a data transmission system is never ideal, wherefore the transmission always distorts the signal to some extent, which may hamper the detection of the signal at the receiving end. The transmission path may cause even great random variation, variation and deformations in the representations (signal values) of the discrete states of the signal to be transmitted, which causes errors in detection or makes the detection impossible. For instance, in the transmission of quantized signals by radio transmission or by carrier waves in cables, digital codes are often transmitted in the form of modulation depths corresponding to their binary number values, that is, by quantized analog variables. Thereby the transmission path may cause great and relatively rapid variation in the level of modulated waves.

Consequently, it is usually necessary to apply an adaptive receiving method (equalizer) in the transmission. In such a method, the sensitivity of the detecting method automatically follows up variations in the level of the signal to be transmitted.

There exist various well-known automatic level control methods which usually aim at normalizing the intensity of the carrier wave in reception. A problem that remains is that although variations in the carrier wave could be compensated for, the modulation depth may vary in reception due to inaccurate or faulty function of the transmitter and receiver circuits, when the properties of the medium are varying, or when the signals are applied to the receiver through several paths, whereby signals arriving with varying delays interfere with each other.

Furthermore, a great variety of adaptive equalizers are known in which the transfer function tends to approximate the inverse function of the transfer function of the transmission line, whereby they partially compensate for deformations caused by the transmission channel in the signal before the signal is detected and recoded into digital form.

Such solutions aim at correcting the signal before the signal states are detected whereas they do not aim at correcting the detection process itself.

The object of the invention is to provide a new adaptive detection method for quantized signals, which reduces the effect of variations and deformations caused by the Transmission line on the interpretation of signal states.

This is achieved by means of an adaptive detection method of the type described in the introductory chapter, which method is according to the invention characterized by adaptively correcting the values of the reference numbers used in the detection towards the actual signal states of the signal to be detected. An account of this, although the transmission path possibly causes even large random variation and distortion in the signal states, these changes are relatively continuous in time.

In the invention, at least the reference number selected as an recognition result is corrected on the basis of the distance between the sample value and the reference number after each sample value, or each reference number is corrected at regular intervals on the basis of the cluster means of the sample values grouped into clusters according to the recognition results.

According to one feature of the invention, received signals are sampled and it is determined by a number of samples as low as possible whether there is statistical clustering present in the samples, whereby the means or other averages of such clusters are observed and used as new reference numbers when detecting various quantized states. In this way, the reference numbers follow up the levels of the signals rather accurately, thus improving the detection accuracy.

In certain cases, for instance, at the start of the reception or when the connection is interrupted, the reference values of the different clusters determined as described above may attain incorrect order and be trapped in this order, which causes severe, prolonged disturbances in reception, because the discrete states of the signals are continually misinterpreted.

According to another feature of the invention, the principle of self-organizing feature maps is applied to the correction of reference numbers. The object of the detection method utilizing self-organizing feature maps is to restore the metric-topological relations of the reference values according to the corresponding relations present in the signal values, also when the order of the reference numbers is temporarily incorrect.

According to still another feature of the invention, a detection method based on averages and another method based on self-organizing feature maps are used alternately. Such a solution enables an optimal compromise between the follow-up accuracy and the ability to restore the correct order.

The detection method according to the invention provides increased accuracy of detection and moderates requirements set on the accuracy of the preceding equalizers or even replaces such equalizers. The method becomes even more advantageous when the number of different signal states increases, because even a minor disturbance may thereby cause errors in detection.

Numerically, the method of the invention is rather light to realize and enables efficient correction even at high transmission rates, so that the detector applying the invention can be realized as a signal processor or microcircuit in a more advantageous manner than conventional equalizers. The rate of previous signal processors is not sufficient for processing signals having a very high speed.

The method can be realized by digital or analog computation methods.

It can be applied, e.g., in digitally modulated data transmission using radio waves and carrier waves in cables, in measurement and control engineering, in medical engineering, computer technology, and, generally whenever quantized signals are transmitted.

The invention will now be described in greater detail by means of embodiments and with reference to the attached drawings, wherein

Figure 1 shows a one-dimensional feature map; Figure 2 shows one way of realizing the feature map of Figure 1;

Figure 3 shows an example of the function of a method utilizing the feature map;

Figure 4 shows a two-dimensional feature map; and Figure 5 shows an apparatus applying the method of the invention.

In its simplest form, the method of the invention is applicable with a one-dimensional signal ( such as a multi-level signal), the values of which are quantized over a domain [a, a + nq], where a is the lowest value of the domain, n is an integer, and q is the quantum step. In transmission, the aim is thus to give the signals one of the values a + hq, where h is the sequential index of the signal state, 0, 1, ...,n; however, the transmission path alters it into a random value a + hq + 6_h, where ∊_h is a random error (possibly larger than the quantum step q). It is nevertheless assumed that when the same circuits or the same transmission path is affected by various factors causing variations, consecutive values of 6_h correlate in such a manner that the probability of the absolute value of the difference thereof | ∊_h - ∊_h-1 | being greater than q/2 is very small.

The received signal value passed through the transmission path is thereby represented by the quantity x = a + hq + ∊_h, where h and ∊_h are the sequential index of the signal state and its random deviation, respectively.

Recognition (detection) of the signal states The signal states of the signal are identified by comparing them with predetermined reference values m_i. Assume initially that the values of the reference numbers m_i are known. The closest reference value m_c is determined using a suitable distance measure d = d(x, m_i), for instance, d = | x - m_i |, which reference number is the recognition result:

d(x, m_c ) = min {d(x, m_i )}. (1) i Updating of the reference values Even though the original reference values m_i would give a satisfactory detection result, the accuracy of detection can be improved by continuously correcting the reference values in response to the variation caused by the transmission path in the received signal and its signal states.

The signal states of the received signal may vary within wide limits due to various disturbances; however, within a short time span, the metric-topological relations between the signals remain unchanged.

The principle in the present method is to automatically observe by means of the lowest possible number of samples of received signals whether there is statistical grouping (clustering) present in the samples and to produce adaptive reference numbers or vectors best corresponding to these clusters, whereby the reference numbers or vectors can be used for the recognition of quantized signal states. This can be achieved by means of conventional clustering methods or vector algorithms. These include the k-means clustering applied in digital signal technology and pattern recognition, disclosed in the reference: [1] J. Makhoul, S. Roucos, H. Gish, "Vector

Quantization in Speech Coding", Proc, IEEE, Vol. 73, p. 1551-1588, 1985.

One way of updating the reference numbers m, by k-means clustering in the method of the invention will be described in the following.

Updating of the reference numbers by cluster means:

In the k-means method, discussed in Reference

[1], a set of consecutive signal samples is collected such that each possible signal state occurs in the samples several times. The samples are classified on the basis of the recognition result described under the preceding heading, and the mean of each class is determined. The means taken from the samples or, for instance, a weighed linear combination of the old reference numbers and the means taken from the samples can now be used as new reference numbers m_i. When the method is repeated continuously while receiving new signals, the reference numbers follow up variations in the signal values. The updating of the numbers is here performed at regular intervals.

Updating of the reference numbers on the basis of the distance between the signal sample and the reference number: The updating of the reference numbers may also be performed after each signal sample, whereby an experimental recognition of the sample according to Eq. (1) has to be carried out first so as to find the closest reference value m_c. This and this only is updated:

m_c(t + 1) = m_c(t) + α (x(t) - m_c(t)) (2) m_i (t + 1) = m_i (t), for i ≠ c (3)

Here m_i = m_i (t) is the value of the reference number immediately before the signal sample is obtained at a moment (t) (t = 0,1,2... is a so called discretetime parameter). The parameter α (0 < α < 1) is a coefficient determining the relative magnitude of the corrections. The corrected reference number is obtained in such a manner that the difference between the signal sample x and the original reference number is multiplied with α and this is added to the original reference number. By updating the reference numbers m. as described above, the reference numbers of different signal states can normally be made to very accurately follow up the cluster means of the representations of the signal states. However, these updating numbers are still partly defective, because there exists a danger that the reference values m_i of the different clusters, defined by the algorithm, may get into wrong order due to the large control corrections and be trapped in this order due to the control method in use, which causes severe, prolonged disturbances in reception, because the discrete states are continually misinterpreted. So the adaptive method should be self-correcting in such a manner that it aims at maintaining and restoring the correct metric-topological relations according to the corresponding relations present in the signal values, also in cases where the relations of the reference numbers are temporarily incorrect.

The preferred embodiment of the method of the invention utilizes so called self-organizing feature maps having this property.

Updating of reference numbers by means of selforganizing mapping, simultaneously restoring the correct order: The principle of self-organizing map representation in a one-dimensional case is illustrated in Figure 1, which shows a set of processing units called nodes hereinbelow. A reference number m_i, i = 0, 1,...,n is stored in each node and used for the recognition and detection of the signal state of the received signal x. In Figure 1, the lines between the nodes denote topological neighbourhood relations, that is, which nodes are topologically closest to each other. As used herein, the topological order of the nodes means that the reference numbers m, the intended values of which are closest to each other are located at adjacent nodes in the map representation of Figure 1, that is, belong to the topological neighbourhood of each other. At an erroneous state this order, however, may temporarily differ from that.

The topological map representation of Figure 1 can also be illustrated as shown in Figure 2, in which the nodes, that is, the processing units, are connected in parallel to the signal line, and one and the same signal x is connected to the input of each processing unit. Each processing unit comprises an output y_i at which it produces an output signal when the signal state of the signal x is closest to the reference number m_i of the node in question. If the signal x is a multi-level signal , for instance, the processing units could be, e.g., comparators.

The above is only intended to facilitate the understanding of the invention. A more detailed description of self-organizing topological feature maps and their use appears from the following references:

[2] T. Kohonen, "Clustering, Taxonomy, and Topological Maps of Patterns", Sixth International Conference on Pattern Recognition, Munich, Germany, October 19-22, 1982, p. 114-128. [3] T. Kohonen, "Self-Organization and Associative Memory", Springer-Verlag, Series in Information Sciences, Vol. 8, Berlin-Heidelberg-New York-Tokyo, 1984, 2. ed. 1988.

A drawback of the above-described methods of updating reference numbers is that if the reference numbers m_i should, for a reason such as malfunction or computing error, attain values whose magnitude relations deviate from the original ones (m_i > m_i although i < j), this wrong order will be retained. On the contrary, the method to be described in the following is able to automatically restore the correct order. This is proved in Reference [3] and its cross-references, and it is also illustrated herein by an example.

In the method, the recognition of the signal states of the received signal is carried out according to Eq. (1).

The updating of the reference numbers is carried out by the following correction rule (adaptation rule, clustering rule) : both the reference number m_c selected as the recognition result and the reference numbers of the nodes neighbouring to the node c corresponding to the reference number m_c are corrected towards the value of x. That is:

m_i (t + 1) = m_i (t) + α(x-m_i(t)), i ∈ N_c (4) m_i(t + 1) = m_i(t), i ∉ N_c (5)

where M_i = m_i (t) is the value of the reference number immediately before the signal sample is obtained at a moment t (t = 0, 1, 2,... is a so called discrete time parameter) and m_i ( t + 1) is the new reference value to be used when taking a subsequent sample. The parameter a is a coefficient which determines the relative magnitude of the corrections. N_c is an index set conεisting of the node c and its topological neighbours. In Figure 1, nodes which are topological neighbours are interconnected by a line.

Above, the parameter α = α(t) always fulfills the condition 0 < α < 1, but it can be varied as required, and N_c = N_c(t) is an index set comprising all the nodes neighbouring to the node c within a certain radius. When the radius is equal to or greater than the spacing between neighbouring nodes, the above correction rule is able to efficiently restore the magnitude order of the reference number m_i so that it is equal to that present in the received signal states, whereas a certain bias is left in the values m_i, which will be discussed below.

When the value of the radius is zero (N_c = {c}), the correction rule aims at giving the reference numbers cluster means which are as unbiased as possible, whereas it is not able to restore the correct order. It is a situation of this type that corresponds to the correction rule of Eq. 2 and 3. A compromise has to be reached between these two properties. In practice, this implies that different choices for α = α(t) and N_c = N_c ( t ) have to be applied as required at prescribed intervals, at least when the data transmission is interrupted and then again continued.

In many cases, it can be assumed that the signal states of the transmitted signal vary at random with the same probability of occurrence. This is the case, for instance, if analog signals are quantized using so called delta modulation, and the bits so obtained are combined to form a code; the numerical values of these codes, by which the transmission is modulated, are generally so called pseudo-random numbers. There then exists a one-to-one numerical correspondence between the reference numbers generated by the correction rule and the cluster means (see Reference [3]). If the received signal values x are precompensated for in the correction rule by the expression b_i + d _i x specific for each reference number, b_i and d_i being constant parameters, the bias left by the above-described correction rule can be for a major part compensated for and the reference numbers will attain more accurate values, which now approximate the cluster means. The same method is also applicable in other cases wherein the probability density p(x) of the signal x is an arbitrary, but known function, whereby parameters b_i and d_i compensating for the bias are computable for the precompensation equation. At its simplest, the final weighed correction rule, by which the abovementioned bias, too, can be compensated for, is then typically of the form

m_i(t + 1) = m_i (t) + α(b_i + d_i ×-m_i(t)), i ∈ N_c (6) m_i(t + 1) = m_i (t), i ∉ N_c (7)

Example 1

This example illustrates the ability of the improved precompensated correction rule of Eq. (6) and (7) to determine topologically ordered reference numbers m_i which promptly follow up general variations in the signal set {x = x(t), t = 0, 1, 2, ...). Assume that there are four signal states occurring at random with the same probability. In this example, the following parameters are used: b₀ = b₁ = b₂ = b₃ = 0, d₀ = 0.7, d₁ = 1, d₂ = 1, d₃ = 1.14. The continuous curves in Figure 3 describe possible signal states, the magnitudes of which vary herein according to a certain arbitrarily chosen law. The actual values of the signal x are picked up at random from these four curves at different moments. Curves drawn by separate dots show how the corresponding reference numbers follow up these variations. In the example, α = 0.1 and N_c = ({max (0, c-1), c, min (3, c+1)}, that is, in the figure, only the closest neighbours are included in the neighbourhood of the node c. It further appears from the example how the magnitude order of the reference numbers m_i, initially wrong (1-0-3-2), is corrected (0-1-2-3) after about 30 samples. Random deviations of the reference numbers are due to the fact that the different signal states occur in the signal x completely at random, whereby the reference numbers, too, are corrected in random order.

The one-dimensional map representation described above and illustrated in Figure 1 can be easily generalized into several dimensions. This is the case, for instance, when the transmitted signal contains two or more separate signal components due to combined modulation. Assume in the following that simultaneous signal states (h₁ and h₂ ) present in the signal and transmitted signals corresponding thereto are x₁ = a₁ + h₁ q₁ and x₂ = a₂ + h₂ q₂, where h₁ and h₂ are integers, and q₁ and q2 the quantum steps, respectively. In this case, the transmitted signal is defined as the vector X = (x₁, x₂ ) = X(t), and the corresponding reference numbers m_i1, m_i2 as the vectors M_i = (m_i1, m_{i 2} ) = M_i(t). The recognition rule can be defined as comparison of distances according to some vectorial norm. Recognition:

d(X,M_c) = min {d(X,M_i)} i

where d(^.) may be some Minkowski distance measure, a special case of which is the Euclidean distance. Updating of the reference vectors (without the precompensation equation):

M_i(t + 1) = M_i (t) + β(X(t) - M_i(t)), i ∈ N'_c M_i(t + 1) = M_i (t), i ∉ N'_c

where β = β(t) is another scalar parameter (0 < β < 1) and N'_c = N' (t) is a neighbourhood set in a twodimensional network of nodes, as shown in Figure 4, for instance. In Figure 4, the neighbourhood set N'_c of the node c comprises the surrounding nodes closest to the node c, as is shown by the continuous line. In this case, the topological order of the nodes can be such, for instance, that the reference numbers m_i1 of the reference vectors M_i present at the nodes increase from the top towards the bottom while the reference numerals m_i2 increase from the left to the right.

The rules described above illustrate the general principle, whereby we are concerned with the same method although the topology of the node set would be chosen in a different way, and although the defining of the neighbourhoods N_c and N'_c used in the modification would deviate from those in the examples above, as long as they aim at the topological order described above. Nor is there any need for the parameters α = α(t) and β = β(t) to be the same for all nodes, but they can be generalized as functions of distances computed from the node c.

In general, when the number of the signal parameters x is n, each reference vector M_i correspondingly contains n reference numbers m₁.

It is to be emphasized that the adaptive reference numbers used in the present detection method are solely determined on the basis of the metric-topological relations of the different signal states inherent in the detected signal without any need to identify or label any signal state in the transmitted signal. This method is thus concerned with nonsupervised learning, which is typical of all clustering methods and most adaptive signal processing systems. Various embodiments

The present method thus comprises two essential modes: 1. The mode in which the reference numbers of the different signal states are made to follow up the cluster means of the representations of the states. 2. The mode in which correct magnitude relations of the reference numbers are restored if these for some reason (operational disturbance, faulty correction, etc.) should be mixed up.

The operations required by the modes 1 and 2 can be implemented numerically, for instance, using so called signal processing architectures constructed of available components, or analog circuits. The choice depends on the required accuracy, computing speed, and costs; the compromise in each particular case is determined by the prevailing state-of-the-art of different circuits technologies. For instance, the signal processor solution described in Reference [4], used for speech recognition, is technically possible for the purpose but unnecessarily complicated and expensive. The correction rule can also be implemented by conventional analog computing technology, described, e.g., in G.A. Korn, T.M. Korn, "Electronic Analog and Hybrid Computers", McGraw-Hill, New York, 1964, or equivalent electronic, optic or optoelectronic constructions.

If the method is applied in data transmission by radio waves or carrier cables using a modulated carrier wave, the detection in the receiver can be very simple; the demand for accuracy is very modest, because the adaptive control automatically compensates for nonlinearities and instabilities. In fact, it is sufficient for the detector that the magnitude relations of the detected signal states are preserved over a short time span, because the clustering analysis used is able to automaτically find the clusters of transmitted signals corresponding to these states and adapt to them.

Figure 5 illustrates a typical block scheme of an apparatus applying the method. Part 1 is a means for modulation and transmission of the signals; part 2 is a means for reception and detection (demodulation) of the signals; part 3 is a means in which reference numbers which follow up the received signal states with an accuracy as high as possible (using, e.g., the k-means method); and part 4 is a means in which the reference numbers are determined, e.g., by correction rules based on self-organizing map representations, whereby their correct metric-topological relations are restored automatically. Part 5 is a means for connecting the signal either to part 3 or part 4; and part 6 is a means which controls the operation of part 5. Part 6 may receive information from manual control, from the receiver (part 3) of the transmitted signal, which receiver indicates when the transmission is started and interrupted, or from interpretation means (parts 3 and 4) which are able to indicate continual misinterpretation. In addition, part 5 may be connected to parts 3 and 4 at regular or otherwise predetermined intervals, controlled by a timer.

At the startup, the initial values of the reference numbers m_i or M. contained in parts 3 and 4 may be preset to precomputed values. The control means, part 6 may also set the reference numbers m_i or M_i to suitable default values.

An advantage of the apparatus described is that at the startup of the reception, after interruptions and in case of severe malfunction, the correct order of the reference numbers can be restored by connecting the signal to part 4. At continued reception, the signal can be connected to part 3, which computes the reference values more accurately. In this way it is possible to optimize both accuracy and restoration after disturbances.

The adaptive and self-correcting signal detection method of the invention is suitable for use in any kind of data transmission in which the nominal values of the signals to be transmitted at different moments define a finite group of discrete states.

The signals may directly convey digital information, e.g. in transmission within a device. The method can be applied when digital signals or states are converted into analog quantities and are transmitted as such, and then again analyzed, detected and coded by this method into digital form. One application is a cellular radio (mobile telephone) in which speech or other analog signals are first digitized by deltamodulation, then converted into analog form (e.g., QAM), transmitted in this form, recoded into digital form and reconstructed into speech.

The present method, however, is not restricted to any particular modulation method or standard in data transmission, but it is generally intended to separate quantized states from each other.

The method is also applicable to optic signals or to devices reading digital signals from magnetic or optic memories.

The figures attached and the description related thereto are only intended to illustrate the present invention. In its details, the method according to the invention may vary within the scope of the attached claims.

Claims

Claims:

1. An adaptive detection method for quantized signals having nominal values which at different moments define a finite set of discrete states, in which method the discrete state of a signal at a certain moment is interpreted by comparing the sample value of the signal to a set of reference numbers, on the basis of which the recognition of the signal state takes place, c h a r a c t e r i z e d by adaptively correcting the values of the reference numbers used in the detection towards the actual signal states of the signal to be detected.

2. A method according to claim 1, c h a r a ct e r i z e d in that at least the reference number selected as the recognition result is corrected either on the basis of the distance between the sample value and the reference number after each sample value, or each reference number is corrected at regular intervals on the basis of the cluster means of sample values grouped into clusters according to the recognition results.

3. A method according to claim 1 or 2, wherein two or more separate simultaneously occurring signal variables are present in the signal, both comprising a finite number of discrete states, c h a r a c t e ri z e d in that the reference numbers are reference vectors.

4. A method according to claim 2 or 3, c h a ra c t e r i z e d in that a number of consecutive signal sample values is collected, said number being such that each possible recognition result occurs several times; the samples are divided into clusters according to the recognition results and a cluster mean is defined for each cluster; said computed cluster means or the linear combination of said computed cluster means and previous reference numbers are taken as new reference numbers at regular intervals.

5. A method according to claim 2 or 3, c h a ra ct e r i z e d in that the reference number selected as the recognition result is corrected after each sample value towards the sample value.

6. A method according to claim 2 or 3, c h a ra c t e r i z e d in that the reference numbers are updated by observing the metric and topological relations of the different signal states and by defining the reference numbers which follow up the same metrictopological relations.

7. A method according to claim 6, c h a r a ct e r i z e d in that the reference numbers are determined by self-organizing feature maps.

8. A method according to claim 1, 2, 3, 5, 6 or 7, c h a r a c t e r i z e d in that both the reference number selected as the recognition result and a predetermined number of other reference numbers forming the predetermined topological neighbourhood set of the selected reference number are corrected after each sample value.

9. A method according to claim 8, c h a r a ct e r i z e d in that the reference numbers are corrected towards the sample value to an extent equivalent to a value obtained by multiplying a value proportional to the distance between the sample value and each particular reference number by a parameter α varying between 0 and 1.

10. A method according to claim 9, c h a r a ct e r i z e d in that before the correction of each particular reference number, the sample value is compensated for by an expression b_i + d_i x specific for each reference value, where x is a sample value, b_i and d_i are constant parameters and i is the sequential index of the reference number.