WALSH FUNCTIONAL CONVERTER

Yu. P. Zabashta, V. M. Razin

The article considers questions of computing functional dependencies in a polynomial approximation of the function being computed, where the system of orthogonal Walsh functions is adopted as the approximation basis. Such a solution makes it possible to substantially increase the speed of computing functional dependencies and to reduce the amount of converter equipment while maintaining an acceptable computational accuracy of \(10^{-4} \div 10^{-5}\).

In systems operating in real time, which include recognition systems, the question of the speed of computing various kinds of functional dependencies is important. Here, first of all, the advisability is evident of comprehensively increasing the speed of computation of the basic elementary functions, such as \(\operatorname{Sin} x\), \(\operatorname{Cos} x\), \(\operatorname{tg} x\), \(\arcsin x\), \(\ln x\), \(e^x\), as well as other functional dependencies accompanying the recognition process.

As is known from the theory of series, a function \(f(t)\) satisfying the Dirichlet conditions can be represented by the series

\[ f(t)=\sum_{k=0} a_k \varphi_k(t), \tag{1} \]

where \(\{\varphi_k(t)\}\) is any complete orthogonal system of functions.

In addition to the requirements of orthogonality and completeness, the requirement of fastest convergence may be imposed on the system \(\{\varphi_k(t)\}\), and in a number of cases decisive in the choice of the system \(\{\varphi_k(t)\}\) is the simplicity of its physical implementation.

Most often, well-known systems serve as the system \(\{\varphi_k(t)\}\), such as, for example, the polynomials of Hermite, Legendre, Chebyshev, Jacobi, Bessel, the trigonometric system of functions, etc.

In computer engineering, the method of approximation by algebraic polynomials of the form is mainly adopted

\[ f(t)=\sum_{k=0}^{N} a_k t^k . \]

In the theory of signals and circuits, the trigonometric system is most widely used

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

Let us consider the advantages and disadvantages of the indicated systems from the standpoint of the speed of the approximation method and the convenience of technical implementation. In approximation by power polynomials one can achieve the fastest convergence (Chebyshev polynomials). This is their advantage and convenience for mathematical analysis. At the same time, however, the following should be kept in mind:

1. Approximation by algebraic polynomials is performed on separate intervals of definition of the function, i.e., for different intervals of the function under study the approximating polynomial is different. Hence the variety of computational algorithms and the difficulties of technical implementation.

2. Computing the value of a function requires, as is evident from the formula

\[ f(t)=a_0+a_1t+a_2t+\cdots+a_nt^n, \]

\(n\) additions and \(n\) multiplications.

Since the multiplication operation takes several times more time than addition, from the standpoint of speed such a representation is also not optimal. The same disadvantages are inherent in the system of trigonometric functions of multiple arguments. From the standpoint under consideration, the ideal system would be one that:

1) eliminated the multiplication operation when computing the value of the function under study at the point \(t_i\);

2) was convenient from the standpoint of technical implementation, taking into account the requirements of modern discrete technology (integrated circuits, etc.);

3) allowed the values of the approximating polynomial to be computed at the same point with minimal difficulty;

4) permitted a unified computational algorithm for a broad class of functional dependences under study.

The system of orthogonal Walsh functions [1] most fully satisfies these requirements. Since Walsh functions take only two values, \(+1\) and \(-1\), then:

1) there is no multiplication operation in computing the series

\[ f(t)=a_0+a_1\varphi_1(t)+a_2\varphi_2(t)+\cdots;\quad \varphi_i(t)=\pm1, \]

and the value \(f(t)\) is determined by summing constant coefficients taken with the corresponding sign;

2) the value of the function \(\varphi_n(t)\) is easily determined from the binary expansion of the number \(t\);

3) the circumstance that Walsh functions take only two discrete values, \(\pm1\), favorably distinguishes them from other orthogonal systems and is convenient for physical implementation using elements of discrete technology, since the latter also have only two discrete states (“0” and “1”).

For computing the values of Walsh functions at any point, the following notation has been introduced [1]. Define a function of the arguments \(\alpha\) and \(t\):

\[ \{\alpha;t\}= \begin{cases} 0, & \text{if the number of positions in which ones occur in both } \alpha \text{ and } t \text{ is even;}\\ 1, & \text{otherwise.} \end{cases} \]

The function \(\{\alpha,t\}\) is defined for all finite binary fractions \(\alpha\) and real \(t\).

The identity holds

\[ w_\alpha(t)=(-1)^{\{\alpha,t\}} \tag{2} \]

or

\[ w_\alpha(t)=(-1)^{\sum_{j=0}^{\infty}\alpha_j t_j}, \tag{3} \]

where \(\alpha_j;\ t_j;\ r\) are the digits of the binary expansions of \(\alpha\) and \(t\), respectively. The latter identity is a good method for computing the value of \(w_\alpha(t)\).

Let us determine the number \(k\) of terms of series (1) that must be present in the Fourier–Walsh expansion in order to ensure the representation of a certain function \(f(t)\) with a prescribed accuracy \(\xi\).

As the input alphabet, five elementary functions were adopted:

\[ \sin \pi t,\quad \cos \pi t,\quad \operatorname{tg}\frac{\pi}{4}t,\quad e^t,\quad \ln(1+t) \]

for \(0 \leq t \leq 1\). The calculation was carried out on a computer by an algorithm that makes it possible to construct a Walsh series with the minimum number of terms ensuring the prescribed error \(\xi\).

Let \(\Delta_l(k)\) denote the table of errors obtained when approximating the function \(f(t)\) by a series consisting of \(l+1\) terms, where the terms of this series correspond to the coefficients largest in absolute value,

\[ \Delta l(k)=f(t)-\sum_{\{x\}} a(x)w(x,t). \]

If the Walsh coefficients are arranged in decreasing order, then from the table \(\Delta l(k)\) one can construct the table \(\Delta l(k)\) in the following way:

\[ \Delta l(k)=\Delta l-1(k)-a_s w(s,t), \]

where \(a_s\) is the \((l+1)\)-st coefficient in decreasing order. If now, at each computation of the table \(\Delta l(k)\) for \(l=0;\ 1;\ 2;\ \ldots m\), all tabular values are compared with \(\xi\), then the first table \(\Delta l(k)\) in which no value exceeds \(\xi\) will guarantee the smallest number of terms of the Walsh series. The results of the computations for the functions under study are collected in Table 1. For comparison, the necessary number of terms of a power series for approximation with the same accuracy is also given there.

Table 1

According to Table 1, since the Walsh series is slowly convergent, it is most expedient to use Walsh polynomials at an approximation accuracy of \(10^{-4}\div 10^{-5}\). Such accuracy is quite acceptable in all engineering calculations.

In this case, the number of terms of the Walsh series (constant coefficients) will amount to 25–30 constants. When the computation accuracy is increased to \(10^{-7}\div 10^{-8}\), the number of stored constants increases to 100–120; however, the amount of equipment increases only insignificantly.

The task of the converter consists in determining the value of a function \(f(t)\), specified from the set \(\mathcal{M}\), at some point \(t_i\) of its argument.

As the algorithm carrying out the computations, an algorithm is adopted that approximates the given function over the entire interval of variation of its argument \(t \in [0,1]\) by means of Walsh polynomials (polynomial approximation)

\[ f(t)=\sum_{0}^{n} a_k w_k(t). \]

As follows from the basic property of Walsh functions, computation of the value of the function at the point \(t_i\) reduces to determining the sign of the Walsh functions at the point \(t_i\) and summing the constant coefficients \(a_k\) with the sign of the corresponding Walsh function \(w_k(t_i)\). The sign of the Walsh function \(w_k(t_i)\) is computed according to

\[ w_k(t)=(-1)^{\sum_{j=0}^{p} t_j k_j}, \]

where the summation in the exponent is performed modulo 2, and \(t\) and \(k_j\) are represented in their binary expansions.

The block diagram of the device is shown in Fig. 1.

Fig. 1.

1. The decoder (\(\mathrm{Dsh}\, t_i\)) represents the value in binary expansion.

2. The reference generator (RG) serves as the master generator for the synchronizing series.

3. The counter (\(\mathrm{Cch}\,\langle j\rangle\)) and decoder (\(\mathrm{Dsh}\,\langle j\rangle\)) serve to create the sequence \(j = 0,12\,p\).

4. The counter (\(\mathrm{Cch}\,\langle k\rangle\)) is intended to generate the sequence “\(K\)” from 1 to \(n\), specifying the number of the Walsh function in binary expansion.

5. The commutator (“\(K\)”) distributes the readout signal of the shaper \(\Phi\) successively over each of the \(n\) readout channels.

6. The permanent storage device (PSD) serves to store the constant coefficients \(C_k\).

7. Number register \(prch\).

8. Accumulating-type adder \(\Sigma\).

1. The result decoder (\(Dshp\)) serves to convert the binary-coded decimal code of the adder into decimal code.

2. Circuit for computing the sign of the Walsh function.

3. Function-selection circuit.

The converter operates as follows. At the input of the decoder (\(Dsht_i\)), in digital form from the decision device of the automaton, the value of the function argument \(t_i\) is specified in the form of a binary-coded decimal code; at the output of the decoder (\(Dsht_i\)) this value will already be represented in the form of a binary code. The type of the function being computed is determined by the position of the switches of the function-selection circuit, which specifies in the ROM the required set of constant coefficients.

The sign with which these coefficients must be summed, i.e., the sign of the Walsh function, is determined by the Walsh-function sign-computation circuit. Its operation is as follows. For a Walsh function, from the binary expansion of \(k\) and \(t_i\), it is necessary to compute the number of coincident ones in like-order positions of the expansions of \(t_i\) and \(k\). If the number of coincident ones is even, the sign of the Walsh function is positive; if it is odd, it is negative. The computation procedure is greatly simplified if, as the summing device, one uses a flip-flop with a counting input, performing addition modulo 2, and feeds to its input, in succession through coincidence circuits, the like-order positions of \(t_i\) and \(k\).

The computation begins upon the “start” signal. By the leading edge of this signal, the sequence counter “\(j\)” (\(Cch\langle j\rangle\)), the sequence counter “\(k\)” (\(Cch\langle k\rangle\)), and the function-sign flip-flop (\(Tr3\)) are set to their initial state. By the trailing edge of this signal the reference generator of the synchroseries is started. The frequency of the generator determines the speed of the functional unit and is chosen on the basis of the speed of the adopted set of elements for the circuit implementation of the unit being designed.

The pulse train of the reference generator (\(OG\)) is fed to the input of the series counter “\(j\),” which performs division by \(P\), where \(P\) is the maximum order of the Walsh function. The decoder “\(j\)” (\(Dshj\)) provides sequential analysis of the states of the bits of \(t_i\) and \(k\). If there are ones in the like-order positions of \(t_i\) and \(k\), then through the corresponding coincidence circuit and assembly a pulse is applied to the flip-flop (\(Tr3\)), changing its state to the opposite one. Thus all the positions of \(t_i\) and \(k\), from the first to the \(p\)-th, are sequentially analyzed.

The final state of (\(Tr3\)) is equivalent to the sign of the corresponding coefficient \(Ck\) in the expansion.

After analysis of all \(P\) positions is completed and the sign of \(Tr3\) is established, a readout signal is issued from the shaper (\(F\)) to the switch “\(K\).” The switch selects the bus of coefficient \(Ck\), and with the arrival of the readout signal the value \(Ck\) is entered into the number register \(Pr4\). From the number register \(Pr4\), the value \(Ck\) can be sent to the adder \(\Sigma\) in direct or complementary code, depending on the sign of the Walsh function \(W_k(t)\). A group of gates controlled by the flip-flop (\(Tr3\)) ensures execution of the indicated operation. This completes the cycle of selecting coefficient \(Ck\). Next, counter \(k\) is automatically set to position \(K+1\), flip-flop (\(Tr3\)) to its initial state, and the cycle is repeated.

Thus all expansion coefficients \(Ck\) are entered into the adder. Upon completion of the computation of the last coefficient, the reference generator issues the “stop” signal; the counters and \(Tr3\) are set to zero, and the computation result is issued from the adder through the result decoder \(Dshp\) to the indication unit.

The function-selection circuit determines in the ROM only those coefficients \(Ck\) that pertain to the function being computed.

Let us compare the considered variant of the functional converter with a unit, similar in functional capabilities, for computing functions of the specialized computer “Orbita” (currently being introduced at the Kursk plant “Schetmash”).

The algorithm for computing a function in the “Orbita” computer is polynomial approximation by a power series. The method of computation is program control of the machine’s arithmetic unit, depending on the form of the function being approximated.

The speed (time for computing one function) of “Orbita” is \(1.5 \div 1.7\) sec; for the Walsh converter it is \(0.7 \div 1\) msec.

The amount of equipment is, respectively, 290 and 200 integrated elements of the TS series. The accuracy of computation is \(10^{-8} \div 10^{-9}\) and \(10^{-4} \div 10^{5}\), respectively.

REFERENCES

1. B. G. Polyak, Yu. A. Schreider. Application of Walsh polynomials in approximate computations. — Problems in the Theory of Mathematical Machines, issue 2, 1962.