On the Construction of Walsh “Spectrum” Analyzers
Abstract Generated abstract
The paper addresses the hardware realization of signal analysis in orthogonal function systems other than the trigonometric Fourier basis, focusing on the lack of engineering designs for Walsh spectrum analyzers. It uses the properties of Walsh functions, especially their binary structure and values of plus or minus one, to reformulate the computation of expansion coefficients as controlled summation or subtraction over sampled or integrated signal intervals. On this basis, the authors propose discrete and analog analyzer schemes, including sequential and possible parallel implementations using reversible counters or paired integrators controlled by Walsh functions. Issues such as accuracy, operating speed, and comparative performance are left to be determined by the requirements of particular applications.
Full Text
ON THE CONSTRUCTION OF WALSH “SPECTRUM” ANALYZERS
B. N. EPIFANTSEV, Yu. P. ZABASHTA
(Presented by the Department of Computer Engineering)
The idea of representing a signal of arbitrary form as a sum of elementary functions is realized by the Fourier transform. With the aid of a computer and special devices that match the parameters of the signal source with the machine, the process of carrying out the indicated transformation can be automated over a wide range of real conditions, and the whole question consists in evaluating the efficiency of such a procedure.
Indeed, from the conditions
\[ f(t)=c_0+\sum_{k=1}^{\infty}\left(a_k\cos k\omega_1 t+b_k\sin k\omega_1 t\right), \tag{1} \]
\[ a_k=\frac{2}{T}\int_{-T/2}^{T/2} f(t)\cdot \cos k\omega_1 t\,dt, \tag{2} \]
\[ b_k=\frac{2}{T}\int_{-T/2}^{T/2} f(t)\cdot \sin k\omega_1 t\,dt \tag{3} \]
in order to obtain the amplitude-frequency spectrum
\[ c_k=\sqrt{a_k^2+b_k^2} \]
we must synthesize the signals \(\cos k\omega_1 t\), \(\sin k\omega_1 t\), which are then multiplied by \(f(t)\); the resulting products are averaged over the interval \([-T/2;\,T/2]\).
The time required to compute standard functions, for example,
\[ \sin k\omega_1 t = k\omega_1 t - \frac{(k\omega_1 t_i)^3}{3!} + \frac{(k\omega_1 t_i)^5}{5!} - \frac{(k\omega_1 t_i)^7}{7!} +\cdots \]
depends on the number of terms of the series, as well as on the number of subdivisions of the period of the function \(m\) \((1, 2, \ldots, i, \ldots, m)\).
It may turn out that, when computing (2) and (3) with a specified accuracy \(\xi\), the time expenditures exceed the permissible ones determined by the conditions of the problem. At the same time, the cost factor of machine time, as well as the factor of additional expenditures for matching the signal source with the machine and the machine with the consumer, significantly narrow the area of rational application of computers for analysis
signals. Therefore, the problem of developing specialized devices for automating the performance of the Fourier transform for various classes of orthogonal complete systems of functions still remains relevant.
By now, the theory of converters that map the original function space into the coefficient space of the basic trigonometric system of functions, based on the idea of using the resonance phenomenon, has to a certain extent acquired a finished form.
As for the hardware implementation of the Fourier transform in the class of other orthogonal systems, there remain a large number of unresolved questions. One of them is the absence of engineering designs for Walsh “spectrum” analyzers, as was noted, incidentally, in [1]. The purpose of the present work is to eliminate this gap.
Walsh functions [2] are products of the form (Fig. 1)
Fig. 1. Graphs of Walsh functions
\[ W_{n_1,n_2,\ldots,n_k}(x)=R_{n_1}(x)\cdot R_{n_2}(x)\cdots R_{n_k}(x), \tag{4} \]
where
\[ 0<n_1<n_2<\cdots<n_k, \tag{5} \]
\[ R_n(x)=\operatorname{sign}\sin 2^n\pi x \]
are Rademacher functions.
The system (4) is orthogonal, normalized, and complete on \([0,1]\). Walsh functions are defined on \(0,1\); however, it is not difficult to reduce the specification of a function on an arbitrary interval \([a,b]\) to the case under consideration.
A remarkable property of Walsh functions is that they take only the values \(\pm 1\) and are easily determined from the binary expansion of the argument \(x\).
According to Dirichlet’s theorem, practically all signals encountered in radio engineering can be represented by the series
\[ f(t)=\sum_{k=0}^{\infty} a_k W_k(t), \tag{6} \]
where
\[ a_k=\int_0^1 f(t) W_k(t)\,dt. \]
Since \(W_k(t)=\pm 1\), and replacing the process of integration by summation in the first case of (7), relation (6) may be represented in the form
\[ a_k=\sum_{\Delta t} f(t)\cdot W_k(t) \tag{7} \]
or
\[ a_k=\sum_l \int_{\Delta t_l} f(t)\,dt-\sum_r \int_{\Delta t_r} f(t)\,dt, \tag{8} \]
where
\(\Delta t_l\) are portions of the interval \([0,1]\) on which the product \(f(t)\cdot W_k(t)\) has a “plus” sign, and \(\Delta t_r\) are the same, but with a “minus” sign.
Expressions (7) and (8) may be taken as the basis for a hardware implementation for obtaining the coefficients of the Walsh spectrum (respectively, the discrete and analog versions of the analyzer).
For (7), the integration process reduces to the summation (subtraction) of individual values of the function \(f(t)\) under investigation. Expression (7) is conveniently implemented if \(f(t)\), by means of an analog-to-code converter, is represented in digital form as a sequence of pulses, the number of which is proportional to the value of the function \(f(t)\), and if a reversible counter controlled by the corresponding Walsh function is used as the integrator.
Figure 2a shows a functional diagram of the discrete version of a sequential-action Walsh spectrum analyzer.
Fig. 2a. Block diagram of the analyzer.
Discrete version
The signal under investigation \(f(t)\) is fed to the input of an analog-to-code converter, from whose output a sequence of pulses is supplied to the counting input of the reversible counter.
The reversible counter is a device consisting of a chain of flip-flops \((Tr_1—Tr_n)\), connected to one another in series through gate circuits \(B_1—B_n\), \(B'_1—B'_n\), and carry circuits \(Cb_1—Cb_n\). The counter has three inputs: one counting input and two for specifying the arithmetic operation of addition or subtraction.
The sign of the operation corresponds to the sign of the Walsh function. The generated \(k\)-th Walsh function is fed to the operation-sign flip-flop, which controls the operation of the gate circuits that provide the prescribed mode of the counter.
The expansion coefficient \(a_k\) is determined as the final result of the computations and may be output to a printer or an indicator.
By successively connecting the corresponding Walsh functions \((W_0 - W_n)\), it is not difficult to determine all the expansion coefficients \((a_0 - a_n)\).
The analyzer can also be used as a parallel-action device; in this case it is necessary to have \(n\) reversible counters according to the number of expansion coefficients. The functional diagram of the analog version of the analyzer is shown in Fig. 26.
The function under study \(f(t)\) and its inverse \(\bar f(t)\) are fed to switches \(K\ell. 1—K\ell. 4\), controlled by the corresponding direct \(W_k(t)\) and inverse
Fig. 26. Analog version
\(W_k^{-}(t)\) Walsh functions in such a way that, when the product \(f(t)\cdot W_k(t)\) is positive, the integrator of positive values (int. “+”) is connected through the summing circuit \(\left(\sum_{\ell}\right)\); when the sign of the product is negative, the integrator of negative values (int. “−”) is connected.
The difference circuit connected to the outputs of the integrators determines the value of the coefficient \(a_k\) of the expansion of the signal under study \(f(t)\) in the system of orthogonal Walsh functions \(W_k(t)\).
As in the preceding version, the analyzer can also be used as a parallel-action device.
The article has not considered questions of the accuracy of representing \(f(t)\), the speed of the analyzers, or their comparative characteristics, since these are determined entirely by the specific analysis problem.
REFERENCES
-
K. G. Kiryavov. A new algorithm for computing the cross-correlation function and constructing simple correlometers for multidimensional random processes. Problems of Radio Electronics, RT series, issue 4, pp. 57–71, 1967.
-
B. T. Polyak, Yu. A. Shreider. Application of Walsh polynomials in approximate computations. Problems of the Theory of Mathematical Machines, No. 2, 1962.