On the Construction of Optimal Walsh Filters in Recognition Systems

Yu. P. Zabashtha, V. M. Razin

Recognition problems can often be reduced to correlation methods, that is, to the problem of constructing optimal filters and computing the probabilities of hypotheses concerning the membership of the input situation.

Since the class of input situations is usually large, there arises the need for parallel processing of information or for constructing tunable (programmable) optimal filters.

It is known [1] that the amplitude-frequency characteristic of an optimal filter differs from the amplitude spectrum of the signal for which this filter is optimal only by a factor, while its phase characteristic supplements the phase spectrum of the signal to a linear function of frequency.

Thus, the characteristics of an optimal filter are in the best possible way matched to the spectral characteristics of the signal (in the literature an optimal filter is often called a matched filter).

Since real signals admit representation by a system of orthogonal functions different from the classical trigonometric system, one may assume that it is possible to construct filters that differ from the classical ones.

As was pointed out in [2], the description of signals and devices in the classical spectral language does not meet the requirements imposed by the modern development of technology, in particular, by integrated circuits.

From this point of view, methods of spectral analysis (and, correspondingly, synthesis) that use as a basis the system of orthogonal Walsh functions [3] are more convenient.

A frequency interpretation can be given to Walsh functions if by “frequency” one understands half the number of zero crossings of a function per unit time. For example, for the trigonometric system an oscillation of frequency \(1\ \mathrm{Hz}\) has 2 zero crossings per second.

Figure 1 presents the first 16 Walsh functions, arranged in order of increasing frequency. For clarity of comparison with the trigonometric system, the Walsh functions are placed on the interval

\[ -\frac{1}{2} \leq \frac{t}{T} = \Theta \leq \frac{1}{2}. \]

It is not difficult to see that two Walsh functions having equal frequencies differ from one another only by a phase shift. One of them—

an even function with respect to \(\Theta=0\) (like a cosine function), the other an odd function (like a sine function).

By analogy, the even Walsh functions are called \(\operatorname{Cal}(\nu,\Theta)\), and the odd ones \(\operatorname{Sal}(\nu,\Theta)\) [4], where \(\nu\) is the frequency of the function, \(\Theta\) is the normalized argument \(\Theta=\dfrac{t}{T}\), and \(T\) is the period of the Walsh function. For \(\nu=0\),

\[ \operatorname{Cal}(\nu,\Theta)=\operatorname{Sal}(\nu,\Theta)=\operatorname{Wal}(\nu,\Theta). \tag{1} \]

The electrical properties of a filter are characterized by its amplitude and phase characteristics, the first of which determines the attenuation of the signal components, and the second—their phase shifts.

[Figure: plots of Walsh functions over \(\Theta=t/T\), from \(-1/2\) through \(0\) to \(+1/2\), labeled \(\operatorname{Wal}(0,\Theta)\), \(\operatorname{Sal}(0,\Theta)\), \(\operatorname{Cal}(1,\Theta)\), \(\operatorname{Sal}(1,\Theta)\), \(\operatorname{Cal}(2,\Theta)\), \(\operatorname{Sal}(3,\Theta)\), \(\operatorname{Cal}(3,\Theta)\), \(\operatorname{Sal}(4,\Theta)\), \(\operatorname{Cal}(4,\Theta)\), \(\operatorname{Sal}(5,\Theta)\), \(\operatorname{Cal}(5,\Theta)\), \(\operatorname{Sal}(6,\Theta)\), \(\operatorname{Cal}(6,\Theta)\), \(\operatorname{Sal}(7,\Theta)\), \(\operatorname{Cal}(7,\Theta)\), \(\operatorname{Sal}(8,\Theta)\).]

Fig. 1

If a function \(f(t)\) acts at the input of the filter,

\[ f(t)=\sum_{k=0}^{\infty}\left[a_k\cos k\omega t+b_k\sin k\omega t\right], \tag{2} \]

then each component of the signal at the filter output will have the form

\[ a'_k \cos k\omega (t-t_c) \quad \text{and} \quad b'_k \sin k\omega (t-t_s). \]

The attenuation of each of the components introduced by the filter is determined as \(\frac{a_k'}{a_k}\) and \(\frac{b_k'}{b_k}\), and the phase shift is \(\varphi_c=-k\omega t_c\) and \(\varphi_s=-k\omega t_s\).

The amplitude and phase characteristics for a Walsh filter are determined analogously. Represent \(f(\Theta)\) in the form of the series [3]

\[ f(\Theta)=a_0 \operatorname{Wal}(\Theta)+\sum_{\nu=1}^{\infty} \left[a_c(\nu)\operatorname{Cal}(\nu,\Theta)+a_s(\nu)\operatorname{Sal}(\nu,\Theta)\right], \]

where \(\Theta=\frac{t}{T}\), \(T\) is the period of the function,

\[ a(0)=\int_{-1/2}^{1/2} f(\Theta)\operatorname{Wal}(\Theta)\,d\Theta, \]

\[ a_c(\nu)=\int_{-1/2}^{1/2} f(\Theta)\operatorname{Cal}(\nu,\Theta)\,d\Theta, \]

\[ a_s(\nu)=\int_{-1/2}^{1/2} f(\Theta)\operatorname{Sal}(\nu,\Theta)\,d\Theta. \tag{3} \]

Introduce the attenuation coefficient \(\kappa_c(\nu)\) and \(\kappa_s(\nu)\) for the corresponding functions \(\operatorname{Cal}(\nu,\Theta)\) and \(\operatorname{Sal}(\nu,\Theta)\). Then at the output of the filter the function \(f(\Theta)\) will have the form \(f_\nu(\Theta-\Delta\Theta)\)

\[ f_\nu(\Theta-\Delta\Theta)=\kappa(0)a(0)\operatorname{Wal}(\Theta-\Delta\Theta)+ \]

\[ +\sum_{\nu=1}^{\infty} \left[\kappa_c(\nu)a_c(\nu)\operatorname{Cal}(\nu,\Theta-\Delta\Theta) +\kappa_s(\nu)a_s(\nu)\operatorname{Sal}(\nu,\Theta-\Delta\Theta)\right]. \tag{4} \]

Figure 2 presents a block diagram of a Walsh filter [4] implementing expression (4). The WFG—the Walsh-function generator—produces the functions \(\operatorname{Cal}(\nu,\Theta)\) and \(\operatorname{Sal}(\nu,\Theta)\) in the form of periodic sequences with period \(\Theta=1\) \(\left(-\frac{1}{2}\leq \Theta<\frac{1}{2}\right)\left(\frac{1}{2}\leq \Theta\leq \frac{3}{2}\right)\cdots\).

In switches \(k_1-k_n\), the signal arriving at the input is multiplied by the functions \(\operatorname{Cal}(\nu,\Theta)\) and \(\operatorname{Sal}(\nu,\Theta)\). Since the latter take only two values, \(\pm 1\), in practice switches \(k_1-k_n\), in accordance with the sign of the Walsh functions, connect the signal to the direct or inverted input of the integrator INT. The integration time of the integrator is equal to the period of occurrence of the functions \(T\).

At the points \(\Theta=\frac{1}{2};\frac{3}{2};\ldots\), the voltages from the outputs of the integrators, corresponding to the expansion coefficients \(a(0)\), \(a_c(\nu)\), \(a_s(\nu)\), are fed to the memory elements ME. The periodically repeating functions \(\operatorname{Cal}(\nu,\Theta)\) and \(\operatorname{Sal}(\nu,\Theta)\) are multiplied in switches \(k'_1-k'_n\) by the values \(a_c(\nu)\) and \(a_s(\nu)\) at the output of the ME and, with attenuation coefficient \(\kappa_c(\nu)\) and \(\kappa_s(\nu)\), are fed to the adder, at whose output we obtain the function \(f_\nu(\Theta-\Delta\Theta)\).

By changing the values of the corresponding resistances \(R_0\cdots R_n\), thereby changing the attenuation coefficient \(\kappa_{c,s}(\nu)\) within the limits \(\kappa_{c,s}=\infty\) at \(r=0\), and \(\kappa_{c,s}(\nu)=0\) at \(r=\infty\), it is not difficult to obtain the required transfer characteristic of the filter. It is also not difficult to program-

varying the attenuation coefficients, i.e., to obtain a programmable filter.

The technical implementation of such a filter presents no difficulties. The filter can be made both in discrete and in analog versions.

Fig. 2

The time delay of the output signal \(f_y(\Theta)\) relative to the input \(f(\Theta)\) in such a filter is a time equal to the period \(T\), \((\Delta \Theta = 1)\). In some problems (especially in recognition systems operating in real time) such a delay is inadmissible.

Let us consider a Walsh filter having a signal delay time equal to \(\Delta \Theta = \dfrac{1}{2^n}\), where \(n\) is the order of the Walsh function. The principle underlying the operation of this filter is as follows.

The function under study \(f(\Theta)\) is approximated by a piecewise-constant function (Fig. 3), which in turn can be represented by a set of steps concentrated on the binary interval [3].

Fig. 3

\[ r_n^s(\Theta)= \begin{cases} 1, & \text{if } \dfrac{s}{2^n}\leq \Theta < \dfrac{s+1}{2^n},\\[6pt] 0, & \text{otherwise.} \end{cases} \tag{5} \]

The amplitude of each step is determined as

\[ r_n^s(s)\cdot f\!\left(\frac{2s+1}{2^{n+1}}\right). \tag{6} \]

The spectrum of the unit step \(r_n^s\) for \(\Theta=\dfrac{s}{2^n}\) is determined [3] by

\[ a(\kappa)=\frac{1}{2^n}w_\kappa(\Theta)=(-1)^{\sum_{j=1}^{n}\kappa_j\Theta_j}, \tag{7} \]

where \(\kappa_j\) and \(\Theta_j\) are the \(j\)-th digits of the binary expansions of \(\kappa\) and \(\Theta\), and the summation in the exponent is performed modulo 2.

Thus, a certain spectrum, determined by (7), corresponds to the unit step specified for the value of the argument \(\Theta=\dfrac{s}{2^n}\). Next, this spectrum must be multiplied by the value of the function \(f(\Theta)\) at the point \(\Theta=\dfrac{s}{2^n}\), and attenuation coefficients \(\kappa_c(\nu)\) and \(\kappa_s(\nu)\), according to the transfer characteristic of the filter being synthesized, must be introduced into the corresponding spectral components \(a_c(\nu)\) and \(a_s(\nu)\). All these operations are performed during the time in which the argument changes over

\[ \frac{s}{2^n}\leqslant \Theta<\frac{s+1}{2^n}, \]

i.e., during the time \(\dfrac{1}{2^n}\). The synthesis of the output function \(f_\nu(\Theta-\Delta\Theta)\) can be started on the next interval

\[ \frac{s+1}{2^n}\leqslant \Theta<\frac{s+2}{2^n}. \]

The delay of \(f_\nu(\Theta-\Delta\Theta)\) relative to \(f(\Theta)\) will be \(\Delta\Theta=\dfrac{1}{2^n}\). A block diagram of the filter is shown in Fig. 4. Since the spectrum of the unit step \(a_{c,s}(\nu,\Theta)\) is determined through the Walsh functions (7), it can be obtained with the aid of the same WFG generator. Multiplication of the spectral coefficients, each of which takes the value \(\pm1\), by the function \(f(\Theta)\) takes place in the multiplier devices \(m_0-m\), analogous to the switches \(\kappa_0-\kappa_n\) in Fig. 2, at the time instant

\[ \Theta=\frac{s}{2^{n+1}}+\frac{1}{2^{n+1}}=\frac{2s+1}{2^{n+1}}. \]

The multiplication result, equal to

\[ a_{c,s}(\nu,\Theta)\cdot f\!\left(\frac{2s+1}{2^{n+1}}\right), \tag{8} \]

is stored for a time \(\Delta\Theta'=\dfrac{1}{2^{n+1}}\) in the corresponding memory elements ME.

The indicated products (8), at the switches \(\kappa'_0-\kappa'_n\), are multiplied by the values of the Walsh functions \(\operatorname{Col}(\nu,\Theta-\Delta\Theta)\), \(\operatorname{Sol}(\nu,\Theta-\Delta\Theta)\), delayed for the time \(\Delta\Theta=\dfrac{1}{2^n}\), and with the corresponding attenuation coefficient \(\kappa_s(\nu)\) and \(\kappa_c(\nu)\) are fed to an adder, from whose output the function

\[ f_\nu\!\left(\Theta-\frac{1}{2^n}\right) \]

is taken.

Similar to the filter in Fig. 2, the filter may be implemented in both variants (discrete or analog). Since the process of changing the transfer characteristic of the filter does not cause difficulties, the filter may be implemented as programmable or adaptive, which is especially valuable in recognition systems.

Fig. 4

In addition, an undoubted advantage of the indicated filters is the simplicity of their synthesis and technical implementation using modern advances in integrated technology.

REFERENCES

1. Yu. S. Lezin. Optimal Filters and Accumulators of Pulse Signals. Moscow, “Sovetskoe radio,” 1969.

2. H. F. Harmuth. A generalized concept of frequency and some applications. IEEE Trans. IT-14 May, 1968, pp. 375—382.

3. B. T. Polyak, Yu. A. Shreider. Application of Walsh polynomials in approximate computations. — Problems in the Theory of Mathematical Machines, Issue 2, Moscow, “Nauka,” 1962.

4. H. F. Harmuth. Crundzuge einer Filtertheorie fur die Männderfunktionen. An (Θ) AEÜ. 18. 1964, 544—554.