Compression of navigation tables in the Walsh basis C.B. Pashentsev
Navigation Faculty of MSTU, Department of Navigation
Annotation. The paper considers the possibility of using the Walsh-Paley functional basis for compressing linear and rectangular tables. All the formulas necessary for this are given and the real effect of information compression is demonstrated using some examples. The method can be used both for preliminary compression of information and for processing it in real time.
Abstract. A possibility of the using of the Wolsh-Paly functional base for the linear and rectangular compression tables has been considered in the work. All the formulas, necessary for it, are given and the actual effect of information compression has been shown on some examples. The method can be used both for preliminary compression of information, and by its processing in a real time scale.
1. Introduction
Many automatic and automated devices related to navigation use tabular data stored in the memory of decision devices and selected from it as needed. In this case, the most important resource is consumed - memory, and sampling from it consumes an even more important resource - time, affecting the performance of the entire information processing system. Therefore, any methods that reduce storage volume are important. One of such methods may be the method of compressing tabular information due to its spectral decomposition in a certain functional basis. At the moment of consumption, the value of the function is restored by an inverse transformation. Compared to the Fourier expansion, it is more advantageous to use the Walsh basis for the expansion, since for smooth functions the coefficients of the Walsh expansion tend to zero faster. This allows for a greater degree of information compression in the Walsh basis. In addition, restoring table values in the Walsh basis requires less time. This is due to the simpler calculation of Walsh functions compared to the calculation of trigonometric functions. If these functions are generated in hardware, then the benefit from using Walsh functions is even greater, since their possible values +1 and -1 are easily implemented by computing devices. The work uses numerical examples to show the advantages of using the Walsh basis for certain types of smooth functions and tabular data. The computational process is based on programs for fast Fourier and Walsh transforms written by the author, and a comparison of the resulting spectra.
2. Theoretical basis of compression
The general theoretical principles on the basis of which the transformation is carried out in the selected functional basis are well known (Gold, Ryder, 1993; Trakhtman A., Trakhtman V., 1978). It is necessary to highlight discrete transformations when the original number series is finite. Since we are talking about table compression, i.e. about a fundamentally finite series of numbers, then further we will talk only about discrete transformations. If given a series of N numbers
X2, Xk, , XN (1)
then the functional basis should be chosen from a finite set of N functions
Fa(X), a= 1, 2,„., N, (2)
existing on a set of points Xk. Then a discrete transformation in this basis will give exactly N coefficients Ca, Koropbie are found using formal summation:
C„ = ЪкХк Fa(Хк), а= 1, 2,„„ N. (3)
The set of N coefficients Ca constitutes a discrete representation of a number of numbers (1) in
functional basis (2). Often this set of Ca numbers is called the line spectrum in the selected basis. Another interpretation of expansion (3) is to consider it as a linear transformation of the original coordinate system Xk. The Ca coefficients then become coordinates in the new coordinate system 0JX). If the spectrum (set of coefficients Ca) is known, then the series of numbers that generated it can be restored up to calculation errors using an inverse discrete transformation
Xk = (1/N) T.aCa0JXk), k = 1, 2,..., N. (4)
For the validity of simple and almost symmetric transformations (3) and (4), it is necessary that the set of basis functions have the properties of orthogonality and a certain normalization. The orthogonality condition looks like a set of equalities
Zk Фр(Хк) Ф(Хк) = 0, р Ф q, (5)
and the normalization conditions are as a set of equalities
Zk ФрХк) Фр(Хк) = Ек Фр\Хк) = 1. (6)
In addition, a system of basis functions is called complete if it is impossible to specify more than a single function that is orthogonal to all functions of the basis.
Obviously, with this formulation of the question, no compression occurs, since the number of terms of the original series and the number of spectral coefficients are the same. The possibility of compressing information appears if the number of spectrum coefficients can be made less than N. For example, when some of the spectrum coefficients are equal to zero or close to it. Then these coefficients can be neglected, and the resulting spectrum will be shorter. In the first case, when we neglect only the zero coefficients of the spectrum, the original series of numbers will be restored up to calculation errors. If we neglect the spectrum coefficients, which are close to zero to the indicated degree, then the reconstructed values of the original series will include not only calculation errors, but also errors from inaccurate representation of the spectrum. The greater the error in reconstructing the terms of the original series we flonyœaeM, TeM the greater the number of spectrum coefficients can be neglected.
If we denote by n the number of spectrum coefficients that we have neglected, then the ratio in percentage
sq = (n/N) -100% (7)
can be called the degree of compression of the original information. Indeed, in this case we represent it with N-n spectrum coefficients instead of N values of the original series. At sq = 0, compression does not occur at all, and at sq = 100% it reaches the limiting hypothetical value. Actual cases range from 0% to 100%.
The practical side of implementing this idea is somewhat more complicated. If the finite (final) spectral coefficients are zero or small to the indicated degree, then it is not difficult to discard n of them and thereby achieve compression of sq.
If among the spectrum coefficients there are zero or close to zero to a given degree, but they are not final, then difficulty arises in representing such a spectrum from the standpoint of information compression. In this case, it is necessary either to give all spectrum coefficients, including zero and close to them, and then compression does not occur. Or specify groups of zero spectral coefficients by the number of the initial element in the group and the number of elements of the group. This naturally reduces the degree of compression of the original series of numbers. If the zero elements of the spectrum are not final or do not form groups, and their numbers do not reveal a simple pattern, then information compression is not achieved in this way.
So, the possibility of compressing information and the degree of its compression depend both on the series of numbers itself (1) and on the set of functions (2) that form the basis of the spectral decomposition of Ca. Since the series of numbers Xk is given to us, we can control the degree of compression by changing the basis of the spectral decomposition. But with the chosen basis Ф(х), the nature of the given information will affect both the
compression capabilities and the degree of compression. There are quite a lot of functional bases that are successfully used for various tasks of presenting information. Among the most well-known are the bases of power functions and their polynomial variants in the form of the Chebyshev and Legendre polynomials, as well as the bases of Kravchuk, Charlier and Meissner. But the most familiar to us is the basis of trigonometric functions:
sin(2nax) and с s(2n«x), (7)
or the corresponding exponential basis in complex form:
exp(-j 2nax). (8)
In this case, the spectrum of the Ca coefficients is a spectrum in its usual physical sense as a set of amplitudes of a certain set of frequencies of a limited range and a certain frequency resolution. Since in this case the basis has already been selected, the compression possibilities are now associated only with the nature of the source information. If it is adequate in nature to the chosen basis (8), i.e. consists of a linear combination of a finite number of periodic functions, then the spectrum will contain only a finite number of nonzero coefficients, and the possibility of information compression arises.
3. Walsh-Paley function system
If the initial information is of a different nature, for example, it changes according to a power, exponential or logarithmic law, then in the spectrum all its coefficients are not small enough, and compression is either impossible or the degree of compression is small. In these cases, it is reasonable to use a different functional basis. Since for other bases there is no clear physical representation of the spectrum, we can interpret (2) as formulas for the transition from the coordinate system Xk to another coordinate system Fa(X). If some of the coefficients are equal to zero, it means that the vector, specified by the coordinates in the form of the original series of numbers, in the new coordinate system is located in a coordinate hyperplane of dimension N-n. Among the existing possibilities there are several bases generated by the Rademacher functions for Z e (0,1):
R0(z) = 1, Rk(z) = sign (sin (2k nz)), k = 1,2,..., (9)
which, in accordance with the sign() function included in them, take only two values: +1 or -1.
The system of functions (9) is orthogonal and normalized, but is not complete. To it we can add functions of the form sign(cos2knz), which are also orthogonal to the functions of system (9). Therefore, on the basis of representations (9), other complete systems are formed, using products of Rademacher functions and introducing a certain ordering into the new functions thus obtained.
The most interesting for navigation applications in terms of information compression is the Walsh-Paley function system. The formation of this system is closely related to the binary numbers of its constituent functions. Specifically, the Walsh-Paley function with number a is the product of Rademacher functions with the numbers of those binary bits a in which 1s are located. If we write the number a in binary representation with n = log N bits
a = Zk 2k-1 ak, (10)
then the functions of the Walsh-Paley system can be represented as follows:
Wa(z) = Pk M. The number itself can be represented similarly to (12) in binary form:
) = Ek 2k-1]k. (15)
Then the system of Walsh-Paley functions will finally be presented in the form
YaGa)/Sh = WJ (a/K) = (-1)"as1""k + \ (16)
which is used in all subsequent calculations. The software function WolshPaly() in Pascal language for generating Walsh-Paley functions using formulas (16) is given below. For N = 8, the values of the Walsh-Paley functions No(/) are given in Table. 1.
Table 1. Walsh-Paley function values for N = 8
] 0 1 2 3 4 5 6 7
0 1 1 1 1 1 1 1 1
Without discussing the details, we will simply mention the existence of systems of Hadamard and Harmuth functions, which differ from the Walsh-Paley system of functions considered in detail only in the way they organize the same functions. It is the order of the Walsh-Paley functions that provides the largest number of final spectrum coefficients that are zero or close to zero to a given degree.
4. Convergence of Walsh-Paley series
Walsh functions have a number of useful properties, among which we present the symmetry property used in calculations:
Shch (a/Shch. (17)
The binary representation of Walsh function numbers with n = logN bits determines the order p and rank r of the function. The order is the largest number of a binary digit, which is equal to 1. The rank of a function is the number of non-zero binary digits, for example, the Walsh function with the number a = 9 for N = 16 and n = 4 is represented in binary form as 1001, and, therefore, its rank g = 2 (two
non-zero digits) and order p = 3 (the most significant non-zero digit is the third, since counting starts from zero). If a function with number a has rank r, then its number can be represented as:
a (R = r) = 2M1 + 21"2 + ... + 2Mg, (18)
where tsk (k = 1, 2,..., r) are the numbers of non-zero bits of the binary representation of number a. For example, the number 9 can be represented as 23 + 20, taking into account the binary representation of 1001. Directly for the problem of compression of the original information, the rate at which the expansion coefficients Ca in the Walsh basis decreases as the number a increases is important. If the function represented by series (1) has a continuous derivative up to this order, and the maximum value of the modulus of the derivative |A"(m)| is M, then the spectrum coefficients with numbers a, the rank of which is not less than the order of the derivative (r > yes), satisfies the inequality (Design of specialized..., 1984):
| Ca(g>w) |< М/ 2ш(ш+3)/2. (19)
It is this important inequality that guarantees the rapid convergence of the spectral coefficients Ca as the number a increases and opens up prospects for compressing tabular information. Indeed, the rank r of the Walsh function increases with the function number a, so that the condition r > w is satisfied for large numbers a. This means that estimate (19) applies to the final expansion coefficients.
Table 2. Coefficients of spectral expansion of power functions in the Walsh basis
ORDER RANK DEGREE OF FUNCTION
0 0 4.68 3.03 2.20 1.37
1 0 -2.50 -2.34 -1.96 -1.34
2 1 -1.25 -1.17 -1.10 -0.95
3 1 0 0.63 0.88 0.92
4 2 -0.63 -0.59 -0.56 -0.52
5 2 0 0.31 0.44 0.49
6 2 0 0.16 0.22 0.31
7 3 0 0 -0.12 -0.29
8 3 -0.31 -0.29 -0.28 -0.26
9 3 0 0.16 0.22 0.25
10 3 0 0.08 0.11 0.15
11 3 0 0 -0.06 -0.15
12 3 0 0.04 0.05 0.08
13 3 0 0 -0.03 -0.07
14 3 0 0 -0.01 -0.04
15 3 0 0 0 -0.03
od % 43.8 18.8 6.3 0
If, in addition, the function has a finite number of nonzero derivatives (for example, a power function), then all coefficients with numbers whose ranks are greater than this power are identically equal to zero. But for this it is necessary that the number N be large enough, and the rank “managed” to become greater than the number of the highest derivative. As an example, consider the spectral expansion of a power function represented by series (1), with the number of samples equal to 16 (^ = 16, n = 4). A small number of samples was chosen only for the clarity of the example results. Above in the table. 2 shows, rounded to two digits, the spectral expansion coefficients for various power functions: linear, quadratic, cubic and fifth degree - with simultaneous indication of the number a of the spectrum and its rank r.
This example shows that the lower the degree of the function that generates the series of numbers (1), the greater the degree of compression of ods that can be achieved during expansion. If the series is short and the degree is large, then compression is not achieved at all, as happens with the fifth degree of the function. If, for the same degree of function, we increase the number of terms of the series and, consequently, the number of spectrum coefficients, then the degree
compression is growing. So, at N = 64 sq = 7.8%, at N = 128 sq = 18.0%, at N = 256 sq = 23.8%.
Let us note in passing that in the case of the Fourier spectrum, in none of the above cases any compression is achieved - the inadequacy of the trigonometric basis for power functions is obvious.
4. Basic formulas for the discrete Walsh-Paley transform
Usually we talk about representations of a given function in a selected basis, but when working with discrete spectral transformation, we are dealing with a set of its discrete values. These discrete values are represented by a series of numbers (1).
So, we will choose the system of Walsh-Paley functions (16) as a functional basis and present for this system the basic formulas expressing the properties of orthogonality and normalization of functions in this system, and transformation formulas for it:
Formula for direct discrete Walsh transform to obtain spectrum
Ca = (1/N) ZkXkWa(k/N).
Formula for the inverse discrete Walsh transform to restore the original series of values
Xk = EaCaWa(k/N).
Condition for orthogonality and normalization of Walsh functions on a discrete set of points
No = (1/N)Zk Wp(k/N) W(k/N) = 0 if p Ф q and No = 1 if p = q. Parseval's equality
(1/N) ZkXk2= ЪаСа,
which represents the equality of the squared modulus of the vector in the original Xk and new Ca coordinate systems.
5. Elements of software implementation
It was this set of formulas that the author used as a basis when compiling a program in Pascal for a comparative analysis of the results of discrete Fourier and Walsh transforms (certificate for the ROSAPO software product No. 950347 dated 10/02/1995). In this case, discrete transforms were implemented as fast Fourier transforms (FFT) and Walsh transforms (WTF) with base 2 and time decimation (Rabinder and Gold, 1978). This does not matter for the compression of tabular information, since the transformation in this case is performed once, but it is very important when processing information in real time in order to be able to run a larger number of different numerical series (tables, functions) in a minimum time. A similar program, practically without changes, was successfully used in operational spectral analysis on board the IL18-DORR PINRO flying laboratory. The two main parts of this program are shown below. This is a fast Walsh transform procedure and a function for calculating the value of the Walsh function given a number and argument. The entire program takes up too much space and is therefore not included here.
Function WolshPaly(Alf, l: integer) : integer; var J, K, x, y, w, maskl, mask2: integer; begin
w:=l; mask1:=l; mask2:=N div 2; for K:=0 to N-l do begin
if (Alf and mask2)<>0 and (I and mask1)<>0 then w:=-w; mask1:=mask1*2; mask2:=mask2 div 2; end;
WolshPaly:=w; end;
This function takes two parameters - the Alf number and the I argument of the Walsh function and returns the value of the Walsh function itself.
Procedure FastWolshTrans(var ml, m2, m3, m4: masdat); var L, LE, LE1, I, J, IP: integer; T1,T2: real;
beginLE:=1; for L:=1 to M do begin LE1:=LE; LE:=LE*2;
for J:=1 to LE1 do begin I:=J; repeat IP:=I+LEl; T1:=m1; T2:=m2;
If L=M then begin
m3:=m1[I]-T1; m4:=m2[I]-T2; m3[I]:=m1[I]+T1; m4[I]:=m2[I]+T2;
m1:=m1[I]-T1; m2:=m2[I]-T2; m1[I]:= m1[I]+T1; m2[I]:=m2[I]+T2;
I:=I+LE; until I>N; end; end;
/* "D" - direct conversion sign */
if TIP="D" then begin for L:=1 to N do begin m3[L]:=m3[L]/N; m4[L]:=m4[L]/N; end;
The procedure performs a fast Walsh transformation of the data that is passed to the procedure in the ml and m2 arrays. The result of the transformation - the Walsh spectrum - is returned by the procedure in arrays m3 and m4. If data is passed to a procedure in normal order, the result is returned in binary-inverted order. If we want to obtain the usual order of spectrum coefficients, then the original data for processing should be binary inverted. Binary inversion of a number is a number in which the order of its binary digits is reversed, for example, the inversion of the number 6 = 110 is 3 = 011. To invert any numbers, a procedure is proposed in the Pascal language:
Procedure MASINVERSION(sw: integer; var m1, m2: masdat); var I, J, K, NV2: integer; T: real; begin NV2:=N div 2;
for I:=1 to N-1 do begin
if I else begin K:=NV2; while K 6. Compress tables with two arguments The transformations and compression of one-dimensional, linear tables were discussed above. But most of the tables used in navigation are two-dimensional - rectangular matrices. The issue of their compression can be solved in two ways. The first way is to transform the table as linear, considering that it is formed by sequentially placing the rows of the matrix table, starting with the first row. This path is quite common, because this is how a two-dimensional array is stored in a linearly organized computer memory. The advantage of this method is that the size of such a linear table will be large enough that compression can be expected to be efficient. But there are also potential troubles hidden in it. After lining up the rows of the matrix, we will certainly get jumps in the function when moving from the end of one row to the beginning of the next. This difficulty can be circumvented by changing the order of the elements in each even row - inverting this row. Accordingly, the order of the spectral coefficients will change. But this will not complicate it, but will only change the order of numbers when restoring the values of the function itself. So, if the number of the value of the restored function was Npq = (p - 1) M + q, where p is the number of the row with the number M of elements in it, and q is the column number, then after inverting for even rows this number will become equal to (p - 1) M + (M- q + 1). The second way is to first spectral transform the table rows, and then transform the resulting intermediate spectrum along the columns. The disadvantage of this method is the low compression ratio due to the short length of rows and columns. True, the compression effect is enhanced by double conversion of both rows and columns. For example, if rows and columns are compressed by only 10%, the total compression effect will be 1 - 0.9x0.9 = 0.19 = 19%. If, for example, the rows of a table change according to a quadratic law, and the columns according to a cubic law, then the overall compression effect according to the table data. 2 is equal to 1-(1-0.188)x(1-0.63) = 0.24 = 24%. As a specific example, we present the results of transforming the table of the Laplace integral function (Kondrashikhin, 1969), which is used in navigation when assessing the reliability of navigation. Here it is presented in the form of a 30x10 matrix, i.e. consists of 30 rows and 10 columns. There is no point in converting it as two-dimensional: there are too few (10) elements in the lines. Therefore, we transform it as a linear table of 300 values. In the example, we will assume that there are 256 = 28 values. But we could supplement the table with zeros and consider the number of values to be 512 = 29. In both cases, the same result is obtained: the final number of zeros with a degree of closeness to zero of the order of 0.01% of the maximum the coefficient is 46.5%. Restoring the function from the set of spectrum coefficients compressed to 53.5% gave errors: root mean square of 0.005 and maximum of 0.057. The example shows the effectiveness of the table transformation. 7. Conclusion The conducted studies related to the choice of the Walsh-Paley functional basis show that this functional basis can be successfully used in various information processing systems that are not of a pronounced periodic nature. In this case, the advantages of such a functional basis over the Fourier basis are obvious. In addition, the Walsh-Paley basis gives a good effect in compressing information. This is illustrated by the example of the Laplace integral function table, which is typical for navigation reliability problems, where the compression effect reached 53.5%. Literature Gold B., Rader Ch. Digital signal processing. M., Sov.radio, 367 e., 1993. Kondrashikhin V.T. Error theory. M., Transport, 256 e., 1969. Design of specialized information and computing systems. Ed. Smirnova Yu.N. M., Higher School, 359 e., 1984. Rabinder L., Gold B. Theory and applications of digital signal processing. M., Mir, 528 e., 1978. Trakhtman A.N., Trakhtman V.A. Introduction to general spectral theory of signals. M., Sov.radio, 312 e., 1978. Walsh functions are a family of functions that form an orthogonal system, taking values only 1 and -1 throughout the entire domain of definition. In principle, Walsh functions can be represented in continuous form, but more often they are defined as discrete sequences of elements. Group of Walsh functions form the Hadamard matrix. Walsh functions are widely used in radio communications, where they are used to implement code division MA (CDMA), for example, in cellular standards such as IS-95, CDMA2000 or UMTS. The system of Walsh functions is an orthonormal basis and, as a consequence, allows one to expand signals of arbitrary shape into a generalized Fourier series. A generalization of the Walsh functions to the case of more than two values are the Vilenkin–Chrestenson functions. Let the Walsh function be defined on the interval ; outside this interval the function is repeated periodically. Let us introduce dimensionless time . Then the Walsh function numbered k is denoted as . The numbering of functions depends on the method of ordering the functions. There is Walsh ordering - in this case, functions are designated as described above. Paley orderings are also common ( ) and Hadamard ( ). Regarding the moment Walsh functions can be divided into even and odd. They are designated as And respectively. These functions are similar to trigonometric sines and cosines. The relationship between these functions is expressed as follows:
There are several methods of formation. Let's consider one of them, the most visual: The Hadamard matrix can be formed by a recursive method by constructing block matrices using the following general formula:
H_(2^(n-1)) & H_(2^(n-1)) \\ H_(2^(n-1)) & -H_(2^(n-1)) \end(bmatrix) This is how a Hadamard matrix of length can be formed :
1\end(bmatrix)
1 & 1 \\ 1 & -1 \end(bmatrix)
1 & 1 & 1 & 1 \\ 1 & -1 & 1 & -1 \\ 1 & 1 & -1 & -1 \\ 1 & -1 & -1 & 1 \end(bmatrix) Each row of the Hadamard Matrix is a Walsh function. In this case, the functions are ordered by Hadamard. The Walsh function number is calculated from the Hadamard function number by rearranging the bits in the binary notation of the number in reverse order, followed by converting the result from the Gray code. The result is a Walsh matrix in which the functions are ordered by Walsh:
1 & 1 & 1 & 1 \\ 1 & 1 & -1 & -1 \\ 1 & -1 & -1 & 1 \\ 1 & -1 & 1 & -1 \end(bmatrix) The screams and fires in the enemy army occurred because while Napoleon's order was being read among the troops, the emperor himself was riding around his bivouacs on horseback. The soldiers, seeing the emperor, lit bunches of straw and, shouting: vive l "empereur! ran after him. Napoleon's order was as follows: At 5 o'clock in the morning it was still completely dark. The troops of the center, reserves and Bagration’s right flank still stood motionless; but on the left flank the columns of infantry, cavalry and artillery, which were supposed to be the first to descend from the heights in order to attack the French right flank and throw it back, according to disposition, into the Bohemian Mountains, had already begun to stir and began to rise from their overnight positions. The smoke from the fires into which they threw everything unnecessary ate my eyes. It was cold and dark. The officers hurriedly drank tea and had breakfast, the soldiers chewed crackers, beat a shot with their feet, warming up, and flocked against the fires, throwing into the firewood the remains of booths, chairs, tables, wheels, tubs, everything unnecessary that could not be taken with them. Austrian column leaders scurried between the Russian troops and served as harbingers of the attack. As soon as an Austrian officer appeared near the regimental commander’s camp, the regiment began to move: the soldiers ran from the fires, hid tubes in their boots, bags in the carts, dismantled their guns and lined up. The officers buttoned up, put on their swords and knapsacks and walked around the ranks, shouting; The wagon trains and orderlies harnessed, packed and tied up the carts. Adjutants, battalion and regimental commanders sat on horseback, crossed themselves, gave the last orders, instructions and instructions to the remaining convoys, and the monotonous tramp of a thousand feet sounded. The columns moved, not knowing where and not seeing from the people around them, from the smoke and from the increasing fog, either the area from which they were leaving or the one into which they were entering. Engineers selected signals, the use of which should improve the basic characteristics of systems (communication quality, noise immunity), relying only on their intuition. The turning point was the creation of the theory of signal formation, processing and transmission. It allows you to determine the effectiveness of using a specific ensemble (set) of signals, based only on knowledge of their auto- and intercorrelation characteristics. The code sequences used in CDMA systems for signal transmission consist of N elementary symbols (chips). Each information symbol of the signal is added to one N-symbol sequence, which is called a “spreading sequence”, since the “resulting” signal is emitted into the air with a deliberately spread spectrum. The gain in communication quality depends both on the number of symbols (length) of the sequence and on the characteristics of the set of signals, primarily their cross-correlation properties and modulation method. Sequence length. In the domestic literature, signals whose base is significantly greater than unity (B=TF>>1, where T is the duration of the signal element, F is the frequency band) are usually called complex. In relation to the original (information) signal, a complex signal is noise with almost the same spectral power density. It is known that the more the spectrum of a signal is “stretched” on the air, the lower its spectral density. Thanks to this property, signals with a large base can be used in a “foreign” (already occupied) frequency band “on a secondary basis”, having an arbitrarily small impact on the system operating there. Characteristics. The entire set of code sequences used in CDMA is divided into two main classes: orthogonal (quasi-orthogonal) and pseudo-random sequences (PSR) with a low level of cross-correlation (Fig. 1). In an optimal CDMA receiver, the incoming signals, which are essentially additive white Gaussian noise, are always processed using correlation methods. Therefore, the search procedure is reduced to finding a signal that is maximally correlated with the individual subscriber code. The correlation between two sequences (x(t)) and (y(t)) is done by multiplying one sequence with a time-shifted copy of the other. Depending on the type of sequence, CDMA systems use different correlation methods: In order to obtain a gain in communication quality when using any of the correlation processing methods, it is necessary that the ensemble of signals have “good” autocorrelation properties. It is desirable that the signals have a single autocorrelation peak, otherwise false synchronization along the side lobe of the autocorrelation function (ACF) is possible. Note that the wider the spectrum of emitted signals, the narrower the central peak (main lobe) of the ACF. Pairs of code sequences are selected so that the cross-correlation function (MCF) has a minimum value for their pairwise correlation. This guarantees a minimum level of mutual interference. Consequently, the choice of an optimal ensemble of signals in CDMA comes down to searching for a structure of code sequences in which the central peak of the ACF has the highest level, and the side lobes of the ACF and the maximum spikes of the ACF are as minimal as possible. Depending on the method of formation and statistical properties, orthogonal code sequences are divided into actually orthogonal and quasi-orthogonal. A distinctive feature of the sequence is the cross-correlation coefficient pij, which generally varies from -1 to +1. In signal theory it has been proven that the maximum achievable value of the cross-correlation coefficient is determined from the condition The minimum value of the VCF provides codes in which the correlation coefficients for any pairs of sequences are negative ( transorthogonal codes). Cross correlation coefficient orthogonal sequences, by definition, is equal to zero, i.e. O? ij =0. For large values of N, the difference between the correlation coefficients of orthogonal and transorthogonal codes can practically be neglected. There are several ways to generate orthogonal codes. The most common is using Walsh sequences of length 2n, which are formed based on the rows of the Hadamard matrix Repeating the procedure multiple times allows you to form a matrix of any size, which is characterized by the mutual orthogonality of all rows and columns. This method of generating signals is implemented in the IS-95 standard, where the length of the Walsh sequences is chosen to be 64. Note that the difference between the rows of the Hadamard matrix and the Walsh sequences is only that the latter use unipole signals of the form (1,0). Using the Hadamard matrix as an example, it is easy to illustrate the principle of constructing transorthogonal codes. Thus, we can verify that if the first column consisting of only ones is deleted from the matrix, then orthogonal Walsh codes are transformed into transorthogonal ones, in which for any two sequences the number of symbol mismatches exceeds the number of matches by exactly one, i.e. O? ij = -1/(N-1). Another important type of orthogonal codes is biorthogonal a code that is formed from an orthogonal code and its inversion. The main advantage of biorthogonal codes compared to orthogonal ones is the ability to transmit a signal in half the frequency band. For example, the biorthogonal block code (32,6) used in WCDMA allows the transmission of a TFI transport format signal. Note that orthogonal codes have two fundamental disadvantages. 1. The maximum number of possible codes is limited by their length (in the IS-95 standard the number of codes is 64), and accordingly, they have a limited address space. To expand the ensemble of signals, along with orthogonal ones, quasi-orthogonal sequences. Thus, the draft cdma2000 standard proposes a method for generating quasi-orthogonal codes by multiplying Walsh sequences by a special masking function. This method allows one to obtain a set of quasi-orthogonal sequences Quasi-Orthogonal Function Set (QOFS) using one such function. Using m masking functions and an ensemble of Walsh codes of length 2n, one can create (m+1) 2n QOF sequences. 2. Another disadvantage of orthogonal codes (and those used in the IS-95 standard are no exception) is that the cross-correlation function is equal to zero only “at a point,” i.e. in the absence of a time shift between codes. Therefore, such signals are used only in synchronous systems and mainly in direct channels (from the base station to the subscriber). The ability to adapt the CDMA system to different transmission rates is achieved through the use of special orthogonal sequences with a variable spreading factor (OVSF, Orthogonal Variable Spreading Factor), called variable length codes. When transmitting a CDMA signal that was created using such a sequence, the chip speed remains constant, but the information speed changes by a factor of two. The 3rd generation standards propose to use orthogonal Gold codes with multiple transmission rates (multirate) as OVSF codes. The principle of their formation is quite simple; Fig. explains it. 3, which shows a code tree that allows you to build codes of different lengths. Each level of the code tree determines the length of the codewords (spreading factor, SF), with each subsequent level doubling the possible number of codes. So, if at level 2 only two codes can be generated (SF=2), then at level 3 four code words (SF=4) are generated, etc. The complete code tree contains eight levels, which corresponds to SF=256 (only the lower three levels are shown in the figure). Thus, the ensemble of OVSF codes is not fixed: it depends on the spreading factor SF, i.e. in fact, it depends on the channel speed. It should be noted that not all code tree combinations can be simultaneously implemented in the same CDMA cell. The main condition for choosing a combination is the inadmissibility of violating their orthogonality. Along with orthogonal codes, a key role in CDMA systems is played by PRP, which, although generated in a deterministic manner, have all the properties of random signals. However, they differ favorably from orthogonal sequences by being invariant to time shifts. There are several types of PSP with different characteristics. Simply put, today technical tools have appeared that can “derive” any ensemble of sequences with given properties. One of the simplest and extremely effective means of generating binary deterministic sequences is the use of a shift register (RS). The sequence at the output of an n-bit PC with feedback is always periodic, and its period n (the number of cycles after which the circuit returns to its original state) does not exceed 2n. Theoretically, using an n-bit register and appropriately selected feedback logic, it is possible to obtain a sequence of any length N in the range from 1 to 2 n inclusive. The maximum length sequence, or m-sequence, will have a period of 2 n -1. The m-sequence autocorrelation function is periodic and two-valued: The level of side maxima of the autocorrelation function (Fig. 4) does not exceed the value Codes Golda are formed by character-by-character addition modulo 2 of two m-sequences (Fig. 5). The WCDMA draft specifies three types of Gold codes: primary and secondary orthogonal Gold codes (both 256 bits long) and long code. Orthogonal Gold codes are created based on a 255-bit m-sequence with the addition of one redundant symbol. The primary synchronization code has an aperiodic autocorrelation function and is used for initial synchronization. The secondary sync code is an unmodulated orthogonal Gold code that is transmitted in parallel with the primary sync code. Each secondary sync code is selected from 17 different Gold codes (C1,...,C17). The long code for the forward channel is 40,960 chip long Gold code fragments. The WCDMA-based communication system is asynchronous, and neighboring base stations use different Gold codes (512 in total), repeated every 10 ms. The asynchronous operating principle of base stations makes them independent of external synchronization sources. It is intended to use a long code in the reverse channel, but only in those cells where the multi-user detection mode is not enabled. Code family Kasami contains 2 k sequences with a period of 2 n-1. They are considered optimal in the sense that for any “preferred” pair the maximum value of the autocorrelation function is ensured, equal to (1 + 2 k). Kasami code sequences are implemented using three shift registers connected in series (u, v and w) with various feedbacks (Fig. 6), each of which forms its own m-sequence. To obtain Kasami code sequences with given properties, the sequences v and w must have different shifts. Kasami codes with a length of 256 bits are used as short sequences in the return channel (WCDMA project) in those cells that use multi-user detection. Pseudorandom sequences with a small aperiodic ACF value are capable of ensuring synchronization of transmitted and received signals in a fairly short period of time, usually equal to the length of the sequence itself. The Barker sequences are the most famous (see table). The efficiency of sequences with aperiodic ACF is usually assessed by the quality indicator F, which is defined as the ratio of the squares of the in-phase components of the signal to the sum of the squares of its out-of-phase components. Thus, a measure of the effectiveness of aperiodic correlation of a binary sequence is the quality indicator. Walsh functions are a family of functions that form an orthogonal system, taking values only 1 and -1 throughout the entire domain of definition. In principle, Walsh functions can be represented in continuous form, but more often they are defined as discrete sequences of 2^n (\displaystyle 2^(n))22 elements. A group of (\displaystyle 2^(n))2^n Walsh functions forms the Hadamard matrix. Walsh functions are widely used in radio communications, where they are used to implement code division MA (CDMA), for example, in cellular standards such as IS-95, CDMA2000 or UMTS. The system of Walsh functions is an orthonormal basis and, as a consequence, allows one to expand signals of arbitrary shape into a generalized Fourier series. A generalization of the Walsh functions to the case of more than two values are the Vilenkin-Chrestenson functions. M-sequences. Method of formation and properties of M-sequences. Application of M-sequences in communication systems Currently, among long-length binary code sequences, the most widely used are M-sequences, Legendre sequences, Gold and Cassami code sequences, Walsh code sequences, and nonlinear code sequences. The advantage of long M-sequences is that the level of periodic side lobes of the M-sequence uncertainty function decreases as its length increases. L. The maximum level of the periodic sidelobe of the TCF of an M-sequence is inversely proportional to the sequence length (1/L). M-sequences It was mentioned above that sequences of maximum length or M-sequences are optimal for expanding the signal spectrum. Such sequences are formed using digital machines, the main element of which is a shift register with memory cells T1, T2, …, T k(Figure 2). Clock pulses arrive at all cells simultaneously with a period of , moving the symbols stored in these cells to the cells adjacent to the right in one clock cycle. Let us denote by letters the symbols stored in the corresponding cells at the th cycle. - symbol at the input of the first cell; the value of this symbol is formed using a linear recurrence relation In accordance with the value of the symbol in the cell with the number, it is multiplied by a coefficient and added to other similar products. Both symbols and coefficients can have values of 0 or 1; summation operations are performed modulo 2. If the coefficient is , then the cell symbol does not participate in the formation of the sum value. If we take the contents of the shift register cells as the initial state, then after clock cycles this state will again occur. If at the same time we register the sequence of symbols of the -th cell, then the length of this sequence will be equal to . On subsequent measures, this sequence will be repeated again, etc. The number is called the period of the sequence. The value for a fixed shift register length depends on the number and location of taps. For each value, you can specify the number of taps and their positions at which the period of the resulting sequence is maximum. Any state of the shift register (except for the zero combination) can be taken as the initial one; changing the initial state will only cause a sequence shift. Sequences with the maximum possible period for a fixed register length are called M-sequences. Their period (length). The block diagram of an automaton that generates M-sequences is usually specified by a characteristic polynomial: in which always , . In table 1 for the sets of values of the coefficients of this polynomial, defining sequences of maximum length. Vector knowledge – if , then the output of the cell with the shift register number is connected to the adder modulo 2; – if , then the output of the cell with the shift register number is not connected to the modulo 2 adder. (long code for scrambling and identification of mobile stations) When solving many analysis problems, it is convenient to represent a complex signal as a set of elementary signals. In practice, the signal representation has found the greatest application s(t), given on the interval, in the form of a linear combination of some elementary functions (p t (t), / = 0,1,2,..., called basic -
norm of the basis function. The representation of a signal in this form is called a generalized Fourier series. Often a system of trigonometric functions is used as basis functions. or a system of complex exponential functions However, with the development of digital methods of signal transmission and processing in recent years, discrete orthogonal sequences in the form of Rademacher, Walsh, Haar, etc. functions are beginning to be used as basis functions. Let us introduce dimensionless time 0 = t / T . Rademacher functions are formed from sinusoidal functions using the relation In other words, Rademacher functions taking values ±1 can be interpreted as “rectangular sine” functions. The graphs of the first four Rademacher functions look like those shown in Figure 4.12. Rademacher function system r k(0) is orthonormal on the interval 0 Walsh function system is an extension of the system of Rademacher functions to a complete system and is defined as Where kf- meaning j th digit in the number record To in Gray code. For example, since 5=>101 2 =>111 g. The graphs of the first four Walsh functions are shown in Figure 4.13. Rice. 4.13. Walsh functions have the following properties: 5. Multiplying Walsh functions gives a Walsh function, but of a different order wal k (0) wal n (0) = walj (0), j = k ® n, wal k (0 2) wal k (0 2) = wal k(0 3), 0 3 = 0j ® 0 2, where © is addition modulo two. In some cases, Walsh functions of the form are used When using a system of Walsh functions as basis functions, the signal can be represented in the form Set of Walsh-Fourier coefficients (q) or (a k f k) and the set of ordinal numbers of functions form the spectrum of the signal in the Walsh basis, which for brevity is sometimes called the S-spectrum. For example, a signal that is a periodic sequence of rectangular pulses (Fig. 4.14) has an S-spectrum determined by expression (4.39). Rice. 4.14. rectangular pulses Let n= 3, then we obtain the S-spectrum for this case, shown in Figure 4.15. Rice. 4.15. Thus, in contrast to the usual frequency spectrum, the S-spectrum of a sequence of rectangular pulses turns out to be finite. It should be noted that the shift of pulses in time leads to a change in the structure of the S-spectrum. In particular, new components appear. For example, for a sequence of n= 3 pulses shifted by 0=1/16, the S-spectrum looks like in Figure 4.16, while when using the trigonometric system of functions, the time shift changes only the phase spectrum. Due to the possibility of applying logical operations to Walsh functions, they are used in the development of signal generation and conversion devices based on microprocessor technology. Signals based on Walsh functions are used in digital multichannel information transmission systems. Rice. 4.16. shifted by 0=1/16 Haar function system consists of piecewise constant functions har k(0), specified on the interval 0 Where T- the number of the most significant non-zero digit in the binary representation of a number To mod2 w - value To modulo 2 t, is the smallest remainder when dividing a number To on 2 t. Graphs of several Haar functions are given in Figure 4.17. Rice. 4.17. If we consider the signal spectrum in the Haar basis, then, as in the case of the S-spectrum, when the signal shifts in time, the structure of its spectrum changes. Haar functions are used in control and communication systems, in the development of digital filters, and in information compression - these are, for example, various methods of compressing black and white photographs based on Haar functions for subsequent transmission of compressed images over communication channels or their archiving.Designation
Formation
Example
Properties
1. Orthogonality
Write a review about the article "Walsh function"
Literature
see also
Notes
Excerpt characterizing the Walsh Function
“Apparently, not everyone has left yet, prince,” said Bagration. – Until tomorrow morning, tomorrow we’ll find out everything.
“There’s a picket on the mountain, your Excellency, still in the same place where it was in the evening,” Rostov reported, bending forward, holding his hand to the visor and unable to contain the smile of amusement caused in him by his trip and, most importantly, by the sounds of bullets.
“Okay, okay,” said Bagration, “thank you, Mr. Officer.”
“Your Excellency,” said Rostov, “allow me to ask you.”
- What's happened?
“Tomorrow our squadron is assigned to reserves; Let me ask you to second me to the 1st squadron.
- What's your last name?
- Count Rostov.
- Oh good. Remain with me as an orderly.
– Ilya Andreich’s son? - said Dolgorukov.
But Rostov did not answer him.
- So I will hope, Your Excellency.
- I will order.
“Tomorrow, perhaps, they will send some kind of order to the sovereign,” he thought. - God bless".
“Soldiers! The Russian army comes out against you to avenge the Austrian, Ulm army. These are the same battalions that you defeated at Gollabrunn and which you have since constantly pursued to this place. The positions we occupy are powerful, and while they move to flank me on the right, they will expose my flank! Soldiers! I myself will lead your battalions. I will stay far from the fire if you, with your usual courage, bring disorder and confusion into the enemy’s ranks; but if victory is in doubt for even one minute, you will see your emperor exposed to the first blows of the enemy, because there can be no doubt in victory, especially on a day in which the honor of the French infantry, which is so necessary for the honor of his nation, is at issue.
Under the pretext of removing the wounded, do not upset the ranks! Let everyone be fully imbued with the thought that it is necessary to defeat these mercenaries of England, inspired by such hatred against our nation. This victory will end our campaign, and we can return to winter quarters, where new French troops that are forming in France will find us; and then the peace that I will make will be worthy of my people, you and me.
Napoleon."
A soldier on the move is as surrounded, limited and drawn by his regiment as a sailor by the ship on which he is located. No matter how far he goes, no matter what strange, unknown and dangerous latitudes he enters, around him - as for a sailor, there are always and everywhere the same decks, masts, ropes of his ship - always and everywhere the same comrades, the same rows, the same sergeant major Ivan Mitrich, the same company dog Zhuchka, the same superiors. A soldier rarely wants to know the latitudes in which his entire ship is located; but on the day of battle, God knows how and from where, in the moral world of the army, one stern note is heard for everyone, which sounds like the approach of something decisive and solemn and arouses them to an unusual curiosity. During the days of battle, soldiers excitedly try to get out of the interests of their regiment, listen, look closely and eagerly ask about what is happening around them.
The fog became so strong that, despite the fact that it was dawn, it was impossible to see ten steps in front of you. The bushes seemed like huge trees, the flat places looked like cliffs and slopes. Everywhere, from all sides, one could encounter an enemy invisible ten steps away. But the columns walked for a long time in the same fog, going down and up the mountains, passing gardens and fences, through new, incomprehensible terrain, never encountering the enemy. On the contrary, now in front, now behind, from all sides, the soldiers learned that our Russian columns were moving in the same direction. Every soldier felt good in his soul because he knew that in the same place where he was going, that is, unknown where, many, many more of ours were going.
“Look, the Kursk soldiers have passed,” they said in the ranks.
- Passion, my brother, that our troops have gathered! In the evening I looked at how the lights were laid out, there was no end in sight. Moscow - one word!
Although none of the column commanders approached the ranks or spoke to the soldiers (the column commanders, as we saw at the military council, were not in a good mood and were dissatisfied with the undertaking and therefore only carried out orders and did not care about amusing the soldiers), despite However, the soldiers walked cheerfully, as always, going into action, especially offensively. But, after walking for about an hour in thick fog, most of the army had to stop, and an unpleasant consciousness of the ongoing disorder and confusion swept through the ranks. How this consciousness is transmitted is very difficult to determine; but what is certain is that it is transmitted unusually faithfully and spreads quickly, imperceptibly and uncontrollably, like water through a ravine. If the Russian army had been alone, without allies, then perhaps a lot of time would have passed before this consciousness of disorder would have become a general confidence; but now, with special pleasure and naturalness attributing the cause of the unrest to the stupid Germans, everyone was convinced that there was a harmful confusion caused by the sausage makers.Basic Concepts
Orthogonal codes
Pseudo-random sequences
m-sequences
Barker sequences
Figure 2 – Digital automatic machine for M-sequence formation
allows you to unambiguously indicate the structure of a digital automaton that forms the corresponding polynomial (1.16) M-sequence:
