# Generalized Orthogonal Discrete W Transform and Its Fast Algorithm

Authors: Jichao Sun; Zhengping Zhang
Journal: Discrete Dynamics in Nature and Society
 (2021)

---

## Abstract

Based on the generalized discrete Fourier transform, the generalized orthogonal discrete W transform and its fast algorithm are proposed and derived in this paper. The orthogonal discrete W transform proposed by Zhongde Wang has only four types. However, the generalized orthogonal discrete W transform proposed by us has infinite types and subsumes a family of symmetric transforms. The generalized orthogonal discrete W transform is a real-valued orthogonal transform, and the real-valued orthogonal transform of a real sequence has the advantages of simple operation and facilitated transmission and storage. The generalized orthogonal discrete W transforms provide more basis functions with new frequencies and phases and hence lead to more powerful analysis and processing tools for communication, signal processing, and numerical computing.


---

## Body

## 1. Introduction

The orthogonal transform is a good mathematical tool and has been used in many applications of digital signal processing, such as harmonic analysis, numerical computation, image processing, data compression, and information hiding [1–6]. Therefore, the method of constructing orthogonal transforms has become an important research topic. The orthogonal transforms include many transforms such as discrete Fourier transform (DFT), discrete Hartley transform, discrete W transform, discrete cosine transform, discrete Walsh transform, and discrete Haar transform.The DFT is the most widely used and influential transform. Since it was proposed by Fourier in 1822, the Fourier transform has been the most basic analysis method in the analysis of continuous signal and system [7]. In order to adapt to the spectrum analysis by computer, DFT was proposed, which is the approximation of spectrum analysis for continuous time signals. Frequency domain analysis was often superior to time-domain analysis. However, it was impractical to use DFT in the spectrum analysis due to high computational complexity before the advent of the fast algorithm of DFT (FFT). In 1965, Cooley and Tukey [8] published a famous paper on the FFT, which reduced the computation time of DFT by several orders of magnitude. As a result, FFT technology has been widely used in various scientific fields. It broadly promoted the effective combination of engineering and computer technologies. Also, it realized the rapid and effective analysis and processing of engineering problems by enabling use of computers. Fourier transform has a wide range of applications in discrete dynamics, acoustics, optics, and other physics, as well as number theory, combinatorial mathematics, probability, statistics, signal processing, cryptography, and many other fields [9–11].In order to extend the application scope of DFT, the kernel function of DFT should be generalized to construct as many basis functions with new frequencies and phases as possible.The kernel function of the DFT isexpi2π/Nlx, where x = 0, 1, …, N − 1, l = 0, 1, …, N − 1. If ωN=1 and ωn≠1, where n<N (n is a positive integer), ω is called an Nth-order primitive root of unity. It is easy to verify that expi2π/N is an Nth-order primitive root of unity in the field of complex numbers (N ≥ 2). In fact, the base expi2π/N of the kernel function can be further extended to any Nth-order primitive root of unity in the field of complex numbers, and l,x can be extended to l+α,x+β, where α and β can be any real numbers. In this paper, we prove that if ωN is an Nth-order primitive root of unity in the field of complex numbers (N ≥ 2), then the row vectors of the transform matrix associated with the kernel function ωNl+αx+β are orthogonal to each other, where l and x denote, respectively, the row and column indices of the transform matrix, while the α and β parameters can be any real numbers. The generalized discrete Fourier transform is constructed using the normalized kernel function 1/NωNl+αx+β.However, since the DFT is a complex-valued transform, a real sequence becomes a complex sequence after DFT. Complex sequences are not as easy to transmit and store as real sequence. Therefore, a real-valued transform was studied to replace the DFT. The discrete Hartley transform (DHT) advanced by Bracewell [12] is a real-valued orthogonal transform. When the DHT is applied to real sequences, it avoids complex operations and speeds up calculations [13]. A transformed real sequence is still a real sequence, which is easy to transmit and store. The DHT and the DFT are related by a simple conversion relationship; that is, the DHT kernel function cas2π/Nlx = cos2π/Nlx + sin2π/Nlx, where x, l = 0, 1, …, N − 1 is the sum of the real and imaginary parts of the DFT kernel function expi2π/Nlx = cos2π/Nlx + isin2π/Nlx, where i is the imaginary unit, x, l = 0, 1, …, N − 1, and casx denotes cosx+sinx for a real number x. Therefore, the DHT can be used widely instead of DFT [14].Wang and Hunt [15] developed the discrete W transform (DWT), which is a generalized DHT. There are four types of orthogonal discrete W transform (ODWT), whose kernel function is still the sum of real and imaginary parts of Fourier transform kernel function. DWT and DHT have attracted many scholars’ attention due to their advantage compared to DFT in processing real number sequences [16].DWT and DHT are both discrete Hartley-type transforms. Besides DFT, other complex-valued orthogonal transforms have been recently gaining attention. For each of these complex-valued orthogonal transforms, a real-valued orthogonal transform can be obtained by adding the real and imaginary parts of the kernel function of the complex-valued orthogonal transform together to form the kernel function of the real-valued orthogonal transform. Many of these constructed real-valued orthogonal transforms were found to resemble the DHT and hence are collectively called the discrete Hartley-type transforms [17–20]. These include the Zhang–Hartley transform and the discrete W transform (DWT). Such transforms have been applied in spectral analysis, data compression, convolution, data security, and so on. These transforms have been widely used in communication and signal processing [21–30]. Numerous approaches on fast algorithms for discrete Hartley-type transforms have been reported [31–34].Thus, for the generalized discrete Fourier transform, its corresponding discrete Hartley-type transform should be considered. Accordingly, the generalized ODWT (GODWT) is proposed in this paper. We show that ODWT is a special case of GODWT. Unlike the ODWT that has only four types, the proposed GODWT has infinite types, subsuming a family of symmetric transforms.GODWT can replace generalized DFT in wide applications by inheriting the advantages of DHT and DWT. The GODWT is a Hartley-type transform, and it has its fast algorithm. The transformed signal of the real sequence is still of real values, which makes the transmission and storage convenient. Compared with DHT and DWT, GODWT provides a large number of basis functions with new frequency, phase, and a large number of new transformations. It indicates that more transmission methods of information are available when adopting GODWT. In the digital hiding technology, the password can be embedded into transform coefficients. The GODWT is applied to digital hiding technology in the transform domain. The transform space is expanded from ODWT space to GODWT space and the secret key space increases significantly so that the decoding gets more difficult.GODWT not only provides integer multiples of frequency and phase but also provides various fractional multiples of frequency and phase. The signals in the objective world are various, and it is likely to be a linear combination of several fractional frequency and phase basis functions. If only integer frequency and phase basis function are used for orthogonal decomposition, the number of basis functions will be increased. The proposed fractional multiple frequency and phase basis functions provide a basis for simplifying some problems. The choice of the basis function is actually a subtle matter. For example, if the functiony=x2 is expanded by the Maclaurin series in a zero-centered finite interval, only one term arises in the expansion. However, there are an infinite number of terms if the same function is expanded by a trigonometric series. From this example, we can see the importance of the basis function choice for function approximation, spectral analysis, data compression, etc. A problem can be well solved only if it uses basis functions whose frequencies and phases are appropriate for or match the problem. Based on the generalized DFT and GODWT, we have at our disposal a large number of new basis functions with rich frequency and phase information.In this paper, we use the primitive roots of unity to construct the generalized DFT. Based on the generalized DFT, we also propose and prove the GODWT. Thus, ODWT is expanded from the original four types to infinite types. Moreover, we propose the fast algorithms for computing the generalized DFT and the GODWT. At the end of the paper, the fast algorithm of GODWT and the application of new frequency and phase basis function in communication are illustrated and given as an example. In addition, the key space of GODWT used in digital hiding technology is analyzed. In a word, our generalization provides better mathematical tools for analysis and processing in engineering fields such as communication.


## 2. Construction of the Generalized DFT Using Primitive Roots of Unity

We show in three stages the construction of the generalized discrete Fourier transform using primitive roots of unity in the complex number field:(a)
Ifq is a positive integer, q and N are relatively prime; that is, (q, N) = 1, and we can know that expi2π/Nq is the Nth-order primitive root of unity in the complex number field (N ≥ 2).In fact, whenn = 1, 2, …, N − 1, n is not divisible by N, that is, N ∤ n, and (q, N) = 1. Then, the product of q and n is not divisible by N, that is, N ∤ qn:(1)∴expi2πNqn=expi2πNqn≠1,when(2)n=N,expi2πNqn=expi2πq=1.Hence,expi2π/Nq is the Nth-order primitive root of unity in the complex number field.Obviously,exp−i2π/Nq = expi2π/Nq−1 is also an Nth-order primitive root of unity in the complex number field.(b)
IfωN = r⋅expiθ is an Nth-order primitive root of unity, then(3)r⋅expiθN=1=expik2π,wherek is any integer:(4)∴r=1,θ=2kπN,thenωN=expi2kπN,Whenk = 0, ωN=1, and ωN becomes a first-order primitive root of unity. This root has no practical significance and will not be considered.Whenk is a positive integer, we get ωN=expik2π/N, where k and N are relatively prime. Otherwise, if k and N have a common divisor s, s ≠ 1, then k=sk1, N=sN1, and N1<N; then(5)ωNN1=expik2πNN1=expik12πN1N1=1,Therefore,ωN is not an Nth-order primitive root of unity. This contradicts the assumptions.Whenk is a negative integer, we similarly get ωN=expik2π/N, where −k and N are relatively prime.From (a) and (b), we realize that anNth-order primitive root of unity ωN in the complex number field can only be expik2π/N, where k is a positive or negative integer and k and N are relatively prime (N ≥ 2).(c)
Ifτ is a real number and the conjugate of ωNτ is denoted by ωNτ¯, then(6)ωNτ¯=expik2πNτ¯=expik2πNτ¯=exp−ik2πNτ=expik2πN−τ=ωN−τ.Now, we prove the orthogonality of the rows of the transform matrix that is associated with the kernel functionωNl+αx+β, where l and x denote the row and column indices of the transform matrix, respectively. The parameters α and β can be any real numbers; ωN is Nth-order primitive root of unity. For any two row vectors ωNl1+αx+β and ωNl2+αx+β, where l1, l2 ∈ {0,1,...,N−1}, x = 0, 1, …, N − 1, denote their dot product by ωNl1+αx+β,ωNl2+αx+β:(7)ωNl1+αx+β,ωNl2+αx+β=∑x=0N−1ωNl1+αx+βωNl2+αx+β¯=∑x=0N−1ωNl1+αx+βωN−l2+αx+β,=∑x=0N−1ωNl1−l2x+β,=ωNl1−l2β∑x=0N−1ωNl1−l2x,whenl1 ≠ l2, ωNl1−l2 ≠ 1, and ωNN=1; therefore,(8)ωNl1−l2β∑x=0N−1ωNl1−l2x=ωNl1−l2β1−ωNl1−l2N1−ωNl1−l2=0.Thus, the row vectors of the transform matrix associated with the kernel functionωNl+αx+β are orthogonal to each other.Whenl1  =  l2,(9)ωNl1−l2β∑x=0N−1ωNl1−l2x=N.The modulus of each row vector isN.IfU is a complex matrix of order N and UUT¯=UT¯U=E, U is called unitary matrix, where UT¯ is the transposed conjugate matrix of U, and E is a unit matrix. Therefore, the N × N matrix generated by the kernel function 1/NωNl+αx+β = 1/Nexp±i2π/Nql+αx+β is a unitary matrix, where l, x = 0, 1, …, N − 1, and each of the parameters α and β can be any real number. The kernel function 1/NωNl+αx+β lies at the l-th row and the x-th column of the unitary matrix.When(10)α=−2l+α′,1Nexpi2πNql+αx+β=1Nexp−i2πNql+α′x+β.Therefore, only the kernel function1/Nexpi2π/Nql+αx+β constructed by the primitive root of unity ωN=expi2π/Nq should be considered.The transform with the kernel function1/Nexpi2π/Nql+αx+β is expressed as(11)Fl=1N∑x=0N−1fxωNl+αx+β=1N∑x=0N−1fxexpi2πNql+αx+β,where,l=0,1,…N−1.The transform in (11) is called a generalized discrete Fourier transform, and its inverse transform is(12)fx=1N∑l=0N−1FlωN−1l+αx+β,where,x=0,1,…N−1.


## 3. Construction of the GODWT

The DWT with two parameters,α and β, is defined as follows:(13)Fl=2N∑x=0N−1fxsinπ4+2πNl+αx+β=1N∑x=0N−1fxcas2πNl+αx+β,where x = 0, 1, …, N − 1, l = 0, 1, …, N − 1, and DWT is orthogonal for four (α, β) values, that is, (α, β) = {(0, 0), (1/2, 0), (0, 1/2), (1/2, 1/2)}. The orthogonal discrete W transform has only the four types. We denote the four transforms associated with these parameter value pairs by DWT-I, DWT-II, DWT-III, and DWT-IV, respectively, and we call them ODWT.The parameterq can be added to the expression in (13) to obtain(14)Fl=1N∑x=0N−1fxcas2πNql+αx+β,where,x=0,1,…,N−1,l=0,1,…,N−1.At this point, many meaningful orthogonal transforms can be constructed. Two lemmas are proved as follows.Lemma 1.
Ifp is positive integer p,N=1, β=h/2p, and both h and m are integers, then(15)∑x=0N−1sin2πNpmx+β=0.Proof.
IfN ∤ m, p,N=1, ∴N ∤ pm, expi2π/Npm ≠ 1,(16)∴1−expi2πNpm≠0,(17)1−expi2πNpm∑x=0N−1expi2πNpmx=1−expi2πpm=0.
From (16) and (17), we get ∑x=0N−1expi2π/Npmx=0. And,(18)∴∑x=0N−1expi2πNpmx+β=expi2πNpmβ⋅∑x=0N−1expi2πNpmx=0,∴∑x=0N−1sin2πNpmx+β=0.
Ifm is divisible by N, that is, N|m, m = Nd,(19)∑x=0N−1sin2πNpmx+β=∑x=0N−1sinπN2pNdx+h2p=∑x=0N−1sinπd2px+h=0.
Q.E.D.Lemma 2.
A real or complex sequencefx, where x=0,1,…N−1, can be regarded as a function defined on the set JN=0,1,…,N−1. A finite Abelian group can be formed through modulo-N addition on JN. This group is called a residual-class additive group and is denoted by ZN.Next, we derive below the conditions for constructing a real-valued orthogonal system by adding the real and imaginary parts of a complex-valued orthogonal system together.Let the complex-valued function set onZN, that is,(20)Φkx=Rkx+iNkx|k=0,1,…,N−1,be a normalized orthogonal function system, where Rkx and Nkx are the real and imaginary parts of Φkx, respectively. Then, the condition for the real-valued function set,(21)Ψkx=Rkx+Nkx|k=0,1,…,N−1,to be a normalized orthogonal function system is(22)∑x=0N−1Rk1xNk2x=0,where k1, k2 ∈ {0, 1, …, N − 1}.Proof.
Φkx is a normalized orthogonal system. Hence, for any k1, k2 ∈ {0, 1, …, N − 1},(23)Im∑x=0N−1Φk1xΦk2x¯=0,which can be rewritten as(24)∑x=0N−1−Rk1xNk2x+Rk2xNk1x=0.
Hence, we find that(25)∑x=0N−1Rk1xNk2x=∑n=0N−1Rk2xNk1x,(26)∑x=0N−1Ψk1xΨk2x=∑x=0N−1Φk1xΦk2x¯+∑x=0N−1Rk1xNk2x+Rk2xNk1x+i∑x=0N−1Rk1xNk2x−Rk2xNk1x.
From (25) and (26), we can get(27)∑x=0N−1Ψk1xΨk2x=∑x=0N−1Φk1xΦk2x¯+2∑x=0N−1Rk1xNk2x.
From (27), we find that, for any k1, k2 ∈ {0, 1, …, N − }, the condition ∑x=0N−1Rk1xNk2x=0 is the necessary and sufficient condition for Ψkx=Rkx+Nkx,k=0,1,…,N−1 to be a real normalized orthogonal function system.


### 3.1. The Generalized Orthogonal Discrete W Transform

The unitary matrix with the kernel function1/Nexpi2π/Nql+αx+β is constructed as discussed above. The N row vectors of an N × N unitary matrix form a normalized orthogonal system. The sum of the real and imaginary parts of the kernel function 1/Nexpi2π/Nql+αx+β is given as(28)1Ncos2πNql+αx+β+sin2πNql+αx+β=1Ncas2πNql+αx+β,and this sum is used as the kernel function of a new real matrix. According to Lemma 2, we know that the necessary and sufficient conditions for the orthonormality of the N row vectors of the real matrix can be formulated as(29)1N∑x=0N−1cos2πNql1+αx+βsin2πNql2+αx+β=0,for anyl1,l2∈0,1,…,N−1,Let(30)σα,β=1N∑x=0N−1cos2πNql1+αx+βsin2πNql2+αx+β.Using the product-to-sum formula (i.e., the Prosthaphaeresis formula), from (30), we can get(31)σα,β=12N∑x=0N−1sin2πNql1+l2+2αx+β−sin2πNql1−l2x+β.Ifq = q1q2, both q1 and q2 are positive integers, ∵(q, N) = 1, ∵(q2, N) = 1; let α = g/2q1 and β=h/2q2, where g and h can be any integers; by substitution in (31), we get(32)σg2q1,h2q2=12N∑x=0N−1sin2πNq2q1l1+l2+2g2q1x+h2q2−sin2πNq2q1l1−l2x+h2q2,∴q1l1+l2+2α = q1l1+l2+2g/2q1 = q1l1+l2+g is an integer and q1l1−l2 is also an integer.According to Lemma1, we get(33)σg2q1,h2q2=12N∑x=0N−1sin2πNq2q1l1+l2+2g2q1x+h2q2−sin2πNq2q1l1−l2x+h2q2=0,Then, whenα=g/2q1 and β=h/2q2, equation (29) holds, and the N functions,(34)1Ncas2πNql+αx+β=1Ncas2πNql+g2q1x+h2q2,wherel=0,1,…,N−1,form a normalized orthogonal basis, where the independent variable x = 0, 1, …, N − 1.The real-valued orthogonal matrix is obtained with the kernel functions in (34), where l and x are the row and column indices of the matrix. The transform(35)Fl=1N∑x=0N−1fxcas2πNql+g2q1x+h2q2,wherel=0,1,…N−1,is GODWT, and its inverse transform is(36)fx=1N∑l=0N−1Flcas2πNql+g2q1x+h2q2,wherel=0,1,…,N−1.Ifs1 is the factor of 2 q1 and s2 is the factor of 2 q2, we get 2q1 = t1s1 and 2q2 = t2s2. So, parameter α of (28) and (29) becomes α = g/2q1 = g/t1s1. Similarly, parameter β of (28) and (29) becomes β = h/2q2 = h/t2s2. Then, we set g = t1g1 and h = t2h2, where g1 and h2 can be any integers. Finally, we obtain α = g1/s1 and β = h2/s2. Thus, the N row vectors of the real matrix with the kernel functions 1/Ncas2π/Nql+g1/s1x+h2/s2 form a normalized orthogonal basis. If you change g1 and h2 into g and h, or any other two letters, the new letters express the same settings as long as they are any integers.Letα = g/s1 and β = h/s2, where g and h can be any integers; if q = q1q2 = 1, the factors s1 of 2q1 and s2 of 2q2 can only be taken as 1 or 2. When (α, β) ∈ {(0, 0), (1/2, 0), (01/2), (1/21/2)}, the four transforms are given by the kernel function 1/Ncas2π/Nql+αx+β, and it is obvious that they are DWT-I, DWT-II, DWT-III, and DWT-IV, respectively, that is, ODWT.For the GODWT, whenq = 1, it reduces to the ODWT, and when q ≠ 1, a new family of orthogonal transforms arises. This family greatly expands the ODWT and also subsumes a family of symmetric transforms.Ifq contains a factor s2, we can construct a transform matrix such that α=f/2s and β=f/2s, where f can be any integer. This transform matrix includes two special cases, namely, (α=f/2, β=f/2) and (α=f/s, β=f/s). In these cases, the real-valued orthogonal matrix is a symmetric matrix, and the forward and inverse transforms have the same form.


## 3.1. The Generalized Orthogonal Discrete W Transform

The unitary matrix with the kernel function1/Nexpi2π/Nql+αx+β is constructed as discussed above. The N row vectors of an N × N unitary matrix form a normalized orthogonal system. The sum of the real and imaginary parts of the kernel function 1/Nexpi2π/Nql+αx+β is given as(28)1Ncos2πNql+αx+β+sin2πNql+αx+β=1Ncas2πNql+αx+β,and this sum is used as the kernel function of a new real matrix. According to Lemma 2, we know that the necessary and sufficient conditions for the orthonormality of the N row vectors of the real matrix can be formulated as(29)1N∑x=0N−1cos2πNql1+αx+βsin2πNql2+αx+β=0,for anyl1,l2∈0,1,…,N−1,Let(30)σα,β=1N∑x=0N−1cos2πNql1+αx+βsin2πNql2+αx+β.Using the product-to-sum formula (i.e., the Prosthaphaeresis formula), from (30), we can get(31)σα,β=12N∑x=0N−1sin2πNql1+l2+2αx+β−sin2πNql1−l2x+β.Ifq = q1q2, both q1 and q2 are positive integers, ∵(q, N) = 1, ∵(q2, N) = 1; let α = g/2q1 and β=h/2q2, where g and h can be any integers; by substitution in (31), we get(32)σg2q1,h2q2=12N∑x=0N−1sin2πNq2q1l1+l2+2g2q1x+h2q2−sin2πNq2q1l1−l2x+h2q2,∴q1l1+l2+2α = q1l1+l2+2g/2q1 = q1l1+l2+g is an integer and q1l1−l2 is also an integer.According to Lemma1, we get(33)σg2q1,h2q2=12N∑x=0N−1sin2πNq2q1l1+l2+2g2q1x+h2q2−sin2πNq2q1l1−l2x+h2q2=0,Then, whenα=g/2q1 and β=h/2q2, equation (29) holds, and the N functions,(34)1Ncas2πNql+αx+β=1Ncas2πNql+g2q1x+h2q2,wherel=0,1,…,N−1,form a normalized orthogonal basis, where the independent variable x = 0, 1, …, N − 1.The real-valued orthogonal matrix is obtained with the kernel functions in (34), where l and x are the row and column indices of the matrix. The transform(35)Fl=1N∑x=0N−1fxcas2πNql+g2q1x+h2q2,wherel=0,1,…N−1,is GODWT, and its inverse transform is(36)fx=1N∑l=0N−1Flcas2πNql+g2q1x+h2q2,wherel=0,1,…,N−1.Ifs1 is the factor of 2 q1 and s2 is the factor of 2 q2, we get 2q1 = t1s1 and 2q2 = t2s2. So, parameter α of (28) and (29) becomes α = g/2q1 = g/t1s1. Similarly, parameter β of (28) and (29) becomes β = h/2q2 = h/t2s2. Then, we set g = t1g1 and h = t2h2, where g1 and h2 can be any integers. Finally, we obtain α = g1/s1 and β = h2/s2. Thus, the N row vectors of the real matrix with the kernel functions 1/Ncas2π/Nql+g1/s1x+h2/s2 form a normalized orthogonal basis. If you change g1 and h2 into g and h, or any other two letters, the new letters express the same settings as long as they are any integers.Letα = g/s1 and β = h/s2, where g and h can be any integers; if q = q1q2 = 1, the factors s1 of 2q1 and s2 of 2q2 can only be taken as 1 or 2. When (α, β) ∈ {(0, 0), (1/2, 0), (01/2), (1/21/2)}, the four transforms are given by the kernel function 1/Ncas2π/Nql+αx+β, and it is obvious that they are DWT-I, DWT-II, DWT-III, and DWT-IV, respectively, that is, ODWT.For the GODWT, whenq = 1, it reduces to the ODWT, and when q ≠ 1, a new family of orthogonal transforms arises. This family greatly expands the ODWT and also subsumes a family of symmetric transforms.Ifq contains a factor s2, we can construct a transform matrix such that α=f/2s and β=f/2s, where f can be any integer. This transform matrix includes two special cases, namely, (α=f/2, β=f/2) and (α=f/s, β=f/s). In these cases, the real-valued orthogonal matrix is a symmetric matrix, and the forward and inverse transforms have the same form.


## 4. Fast Algorithms for the Generalized Discrete Fourier and GODWT

### 4.1. The Fast Algorithm for the Generalized Discrete Fourier Transform

Letfx be a sequence, where x=0,1,…,N−1, and let ωN be an Nth-order primitive root of unity in the complex number field. Then, the transform of fx by the kernel function 1/NωNl+αx+β (the generalized DFT) is expressed as(37)Fl=1N∑x=0N−1fxωNl+αx+β=1N∑x=0N−1fxωNαxωNlxωNl+αβ,wherel=0,1,…,N−1.From (37), we can identify two steps for the transform of fx with the kernel function 1/NωNl+αx+β:(1)
WhenN is a composite number (nonprime, N ≥ 2), fxωNαx is transformed by the kernel function 1/NωNlx. This is adopted for the generalized fast Fourier transform (FFT) [35].(2)
The result from the first step is multiplied byωNl+αβ.So, whenN is a composite number, there is a fast algorithm for computing the transform of fx with the kernel function 1/NωNl+αx+β.IfωN is an Nth-order primitive root of unity in the complex field, then ωN−1 is also an Nth-order primitive root of unity in the complex field. Similarly, when N is a composite number, a fast algorithm exists for computing the inverse transform(38)fx=1N∑l=0N−1FlωN−1l+αx+β=1N∑l=0N−1Flω¯Nl+αx+β,wherel=0,1,…,N−1.


### 4.2. The Fast Algorithm for the GODWT

LetΦ be a unitary matrix: Φ = R + iN, where R and N are real matrices and Ψ = R + N forms an orthogonal matrix. Then, the inverse transform matrix of Φ is its conjugate transposed matrix ΦT¯ = RT − iNT. The inverse transform matrix of Ψ is its transposed matrix ΨT = RT + NT.IfL is a real-valued column vector, then the actions of the matrices on this vector are as follows:(39)ΦL=R+iNL=RL+iNL,(40)ΨL=R+NL=RL+NL,(41)ΦT¯L=RT−iNL=RTL−iNTL,(42)ΨTL=RT+NTL=RTL+NTL,From (39) and (40), we see that ΨL is the sum of the real and imaginary parts of ΦL. Moreover, from (41) and (42), we see that ΨTL is the real part minus the imaginary part of ΦT¯L.For forward and inverse transforms of the GODWT, the transformed sequences are all real value sequences. Using the above relations ofΨL and ΦL as well as ΨTL and ΦT¯L, we can obtain fast algorithms for computing the GODWT and its inverse transform. However, the advantages of real-valued operations can be brought into play only by developing direct fast algorithms of real-valued orthogonal transforms on real sequences. This is one of the problems in the anticipated future work on the GODWT.Example 1.
LetN=8, q=9, q1=3, q2=3, g=1, and h=1. Therefore, α = g/2q1 = 1/6, and β=h/2q2 = 1/6. The transform is(43)Fl=1N∑x=0N−1fxcas2πNql+g2q1x+h2q2=24∑x=07fxcas2π×98l+16x+16,wherefxis the real sequence.
The fast algorithm of the transform in (43) is given as follows.
Due to the fact that the kernel function2/4cas[2π×9/8l+1/6x+1/6] is the sum of the real and imaginary parts of the generalized DFT kernel function 2/4ωl+1/6x+1/6, where ω = expi2π×9/8, we firstly calculate the transform of fx with the kernel function 2/4ωl+1/6x+1/6:(44)F″l=24∑x=07fxωl+1/6x+1/6=∑x=07fxω1/6xωlx24ωl+1/61/6.
In order to getF″l, first, we calculate f′x, f′x = fxω1/6x, where x = 0, 1, …, 7. Second, f′x is transformed with the kernel function ωlx into F′l; then we calculate F″l, F″l=2/4F′lωl+1/61/6, where l = 0, 1, …, 7. We get Fl after the real and the imaginary parts of F″l are added.
The matrixΦ is formed with the kernel function ωlx, x = 0, 1, …, 7, l = 0, 1, …, 7. It can be decomposed into the product of a sparse matrix according to the method in [35], so it has a fast algorithm Φ = F1F2F3,(45)Φ=111111111ωω2ω3ω4ω5ω6ω71ω2ω4ω61ω2ω4ω61ω3ω6ωω4ω7ω2ω51ω41ω41ω41ω41ω5ω2ω7ω4ωω6ω31ω6ω4ω21ω6ω4ω21ω7ω6ω5ω4ω3ω2ω,F1=11000000001ω000000001ω2000000001ω31ω4000000001ω5000000001ω6000000001ω7,where ω4=−1.(46)F2=1010000001010000000010ω200000010ω210−100000010−10000000010ω600000010ω6,F3=100010000101010000101010000101011000−100001000−100001000−100001000−1.
By using the sparse matrix, it is easy to draw a signal flow diagram that a column vector is transformed by the matrixΦ. The FFT flow diagram is depicted in Figure 1.
We calculate the inverse transform ofFl=2/4∑x=07fxcas2π×9/8l+1/6x+1/6. First, we calculate the inverse transform of the transform associated with the kernel 2/4ωl+1/6x+1/6 as follows:(47)f2x=24∑l=07Flω−l+1/6x+1/6=∑l=07Flω¯1/6lω¯lx24ω¯x+1/61/6,where ω¯ is the conjugate of ω.
In order to getf2x, first, F1l is computed as F1l=Flω¯1/6l. Then, the FFT of F1l is computed using a kernel function ω¯lx. The transform matrix Φ1 formed by kernel function ω¯lx is the conjugate transpose matrix ΦT¯ of Φ. Φ is the symmetric matrix. So Φ1=Φ¯. In the product of sparse matrix of Φ, that is, F1∗F2∗F3 and its corresponding signal flow diagram, ω is replaced with ω¯, the product of the sparse matrix decomposed by Φ1 and its corresponding signal flow diagram can be obtained. The input and output of the signal flow diagram are F1l and f1x, respectively. Then, given f2x = 2/4f1xωx+1/61/6, fx is obtained using the real part minus the imaginary part of f2x.
Another method of computing∑l=07Flω¯1/6lω¯lx is as follows:
∑l=07Flω¯1/6lω¯lx¯ = ∑l=07Fl¯ω1/6lωlx, so, in order to calculate the FFT of Flω¯1/6l with kernel function ω¯lx, we can firstly calculate the FFT of Fl¯ω1/6l with kernel function ωlx and then take the conjugate. The product of sparse matrix and signal flow graph of Φ can be directly used for FFT with kernel function ωlx.
In this example, the transformFl = 2/4∑x=07fxcas2π×9/8l+1/6x+1/6 is symmetric transform; thus, the inverse transform is the same as the positive transform. The inverse transform is(48)fx=24∑l=07Flcas2π×98l+16x+16.
Therefore, we can use the same fast algorithm as the positive transform.Figure 1
The FFT flow diagram.


### 4.3. Examples of the GODWT Application

(1)
In communication field, the communication between different users using different frequency bands is frequency division multiplexing, and the communication between different users relying on different address codes is code division multiplexing. The code division multiplexing and frequency division multiplexing can be combined by using GODWT. We still take the primitive unit rootω = expi2π×9/8, and three kernel functions of GODWT, that is, 2/4cas[2π×9/8xl], 2/4 cas [2π×9/8x+1/3l], and 2/4cas[2π×9/8x+2/3l] can be obtained. For the three transmitted code sequences, that is, ax, bx, and cx, x = 0, 1, …, 7, the transforms of them are calculated, respectively, to get Al, Bl, and Cl, where l = 0, 1, …, 7.(49)Al=24∑x=07axcas2π×98xl,Bl=24∑x=07bxcas2π×98x+13l,Cl=24∑x=07cxcas2π×98x+23l,Al=2/4∑x=07axcas2π×9/8xl; the equation is written in matrix forms as(50)A0,A1,…,A7=24a0,a1,…,a7cas9π40×0cas9π40×1…cas9π40×7cas9π41×0cas9π41×1…cas9π41×7⋮⋮⋮⋮cas9π47×0cas9π47×1…cas9π47×7.Let the carrier of code division multiplexing beZ10,Z11,…,Z17:(51)Z10=cas9π40×0cas9π40×1…cas9π40×7,the angular frequency ofZ10is9π4×0,Z11=cas9π41×0cas9π41×1…cas9π41×7,the angular frequency ofZ11is9π4×1,⋮⋮…⋮……⋮Z17=cas9π47×0cas9π47×1…cas9π47×7,the angular frequency ofZ10is9π4×7The carriersZ10Z11, …, Z17 are periodic and repetitive. The amounts of information carried by each carrier wave over a period are constant, which are 2/4a0, 2/4a1...2/4a7, respectively.The matrix equation above can be written as(52)A0,A1,…,A7=24a0Z10+a1Z11+⋯+a7Z17.In order to transmitAl = 2/4∑x=07axcas2π×9/8xl, l = 0, 1, …, 7, the angular frequency of carriers is from 9π/4×0 to 9π/4×7. It is called code division multiplexing where we have transmitting Al, l = 0, 1, …, 7 instead of transmitting ax, x = 0, 1, …, 7. Both the input and output are eight real numbers. In contrast, if we use the DFT, the output is eight complex numbers. The transmission of eight complex numbers requires the transmission of sixteen real numbers. Accordingly, the transmission efficiency of GODWT is two times that of DFT. Transmitting Bl and Cl instead of transmitting bx and cx is also code division multiplexing, but they all have different carriers. Bl = 2/4∑x=07axcas2π×9/8x+1/3l, l = 0, 1, …, 7; when transmitting Bl, the angular frequency of carriers is from 9π/4×0+1/3 to 9π/4×7+1/3. Cl = 2/4∑x=07cxcas2π×9/8x+2/3l, l = 0, 1, …, 7; when transmitting Cl, the angular frequency of carriers is from 9π/4×0+2/3 to 9π/4×7+2/3.When they are transmitted together, it is frequency division multiplexing. The receiver would receive their sum:(53)Al+Bl+Cl=24∑x=07axcas2π×98xl+24∑x=07bxcas2π×98x+13l+24∑x=07cxcas2π×98x+23l.These three components are separated with a filter, and thenaxbx,cx were restored using the inverse GODWT.Time-division multiplexing (TDM) is also a method to transmit multiway signals. Time-division multiplexing is used primarily for digital signals but may be applied in analog multiplexing in which two or more signals or bit streams are transferred appearing simultaneously as subchannels in one communication channel but are physically taking turns on the channel. Each signal appears on the line only a fraction of time in an alternating pattern. The time domain is divided into several recurrent time slots of fixed length.TransmittingAl, Bl, and Cl with different time slots, they can be separated at the receiving end, and then ax, bx, and cx were restored using the inverse GODWT. This realizes the combination of code-division multiplexing and time-division multiplexing. It shows that the proposed GODWT provides more means for the transmission in communication, compared with DHT and ODWT.(2)
In the digital hiding technology, the password can be embedded into transform coefficients.The secret key space of ODWT is (N, α, β), where (α, β) = {(0, 0), (1/2, 0), (0, 1/2), (1/2, 1/2)}, and N is a positive integer. Actually, N cannot be big; if N is bigger, it is not easy to calculate. The secret key space of GODWT is (N, q, α, β). It includes the secret key space of ODWT. Because the value of q is not limited in principle and the parameter value pairs (α, β) changed from 4 pairs of ODWT to infinity pairs of GODWT: (α, β) = g/2q1,h/2q2 where q1q2 = q, g and h can be any integers, the secret key space of GODWT has been greatly generalized.


## 4.1. The Fast Algorithm for the Generalized Discrete Fourier Transform

Letfx be a sequence, where x=0,1,…,N−1, and let ωN be an Nth-order primitive root of unity in the complex number field. Then, the transform of fx by the kernel function 1/NωNl+αx+β (the generalized DFT) is expressed as(37)Fl=1N∑x=0N−1fxωNl+αx+β=1N∑x=0N−1fxωNαxωNlxωNl+αβ,wherel=0,1,…,N−1.From (37), we can identify two steps for the transform of fx with the kernel function 1/NωNl+αx+β:(1)
WhenN is a composite number (nonprime, N ≥ 2), fxωNαx is transformed by the kernel function 1/NωNlx. This is adopted for the generalized fast Fourier transform (FFT) [35].(2)
The result from the first step is multiplied byωNl+αβ.So, whenN is a composite number, there is a fast algorithm for computing the transform of fx with the kernel function 1/NωNl+αx+β.IfωN is an Nth-order primitive root of unity in the complex field, then ωN−1 is also an Nth-order primitive root of unity in the complex field. Similarly, when N is a composite number, a fast algorithm exists for computing the inverse transform(38)fx=1N∑l=0N−1FlωN−1l+αx+β=1N∑l=0N−1Flω¯Nl+αx+β,wherel=0,1,…,N−1.


## 4.2. The Fast Algorithm for the GODWT

LetΦ be a unitary matrix: Φ = R + iN, where R and N are real matrices and Ψ = R + N forms an orthogonal matrix. Then, the inverse transform matrix of Φ is its conjugate transposed matrix ΦT¯ = RT − iNT. The inverse transform matrix of Ψ is its transposed matrix ΨT = RT + NT.IfL is a real-valued column vector, then the actions of the matrices on this vector are as follows:(39)ΦL=R+iNL=RL+iNL,(40)ΨL=R+NL=RL+NL,(41)ΦT¯L=RT−iNL=RTL−iNTL,(42)ΨTL=RT+NTL=RTL+NTL,From (39) and (40), we see that ΨL is the sum of the real and imaginary parts of ΦL. Moreover, from (41) and (42), we see that ΨTL is the real part minus the imaginary part of ΦT¯L.For forward and inverse transforms of the GODWT, the transformed sequences are all real value sequences. Using the above relations ofΨL and ΦL as well as ΨTL and ΦT¯L, we can obtain fast algorithms for computing the GODWT and its inverse transform. However, the advantages of real-valued operations can be brought into play only by developing direct fast algorithms of real-valued orthogonal transforms on real sequences. This is one of the problems in the anticipated future work on the GODWT.Example 1.
LetN=8, q=9, q1=3, q2=3, g=1, and h=1. Therefore, α = g/2q1 = 1/6, and β=h/2q2 = 1/6. The transform is(43)Fl=1N∑x=0N−1fxcas2πNql+g2q1x+h2q2=24∑x=07fxcas2π×98l+16x+16,wherefxis the real sequence.
The fast algorithm of the transform in (43) is given as follows.
Due to the fact that the kernel function2/4cas[2π×9/8l+1/6x+1/6] is the sum of the real and imaginary parts of the generalized DFT kernel function 2/4ωl+1/6x+1/6, where ω = expi2π×9/8, we firstly calculate the transform of fx with the kernel function 2/4ωl+1/6x+1/6:(44)F″l=24∑x=07fxωl+1/6x+1/6=∑x=07fxω1/6xωlx24ωl+1/61/6.
In order to getF″l, first, we calculate f′x, f′x = fxω1/6x, where x = 0, 1, …, 7. Second, f′x is transformed with the kernel function ωlx into F′l; then we calculate F″l, F″l=2/4F′lωl+1/61/6, where l = 0, 1, …, 7. We get Fl after the real and the imaginary parts of F″l are added.
The matrixΦ is formed with the kernel function ωlx, x = 0, 1, …, 7, l = 0, 1, …, 7. It can be decomposed into the product of a sparse matrix according to the method in [35], so it has a fast algorithm Φ = F1F2F3,(45)Φ=111111111ωω2ω3ω4ω5ω6ω71ω2ω4ω61ω2ω4ω61ω3ω6ωω4ω7ω2ω51ω41ω41ω41ω41ω5ω2ω7ω4ωω6ω31ω6ω4ω21ω6ω4ω21ω7ω6ω5ω4ω3ω2ω,F1=11000000001ω000000001ω2000000001ω31ω4000000001ω5000000001ω6000000001ω7,where ω4=−1.(46)F2=1010000001010000000010ω200000010ω210−100000010−10000000010ω600000010ω6,F3=100010000101010000101010000101011000−100001000−100001000−100001000−1.
By using the sparse matrix, it is easy to draw a signal flow diagram that a column vector is transformed by the matrixΦ. The FFT flow diagram is depicted in Figure 1.
We calculate the inverse transform ofFl=2/4∑x=07fxcas2π×9/8l+1/6x+1/6. First, we calculate the inverse transform of the transform associated with the kernel 2/4ωl+1/6x+1/6 as follows:(47)f2x=24∑l=07Flω−l+1/6x+1/6=∑l=07Flω¯1/6lω¯lx24ω¯x+1/61/6,where ω¯ is the conjugate of ω.
In order to getf2x, first, F1l is computed as F1l=Flω¯1/6l. Then, the FFT of F1l is computed using a kernel function ω¯lx. The transform matrix Φ1 formed by kernel function ω¯lx is the conjugate transpose matrix ΦT¯ of Φ. Φ is the symmetric matrix. So Φ1=Φ¯. In the product of sparse matrix of Φ, that is, F1∗F2∗F3 and its corresponding signal flow diagram, ω is replaced with ω¯, the product of the sparse matrix decomposed by Φ1 and its corresponding signal flow diagram can be obtained. The input and output of the signal flow diagram are F1l and f1x, respectively. Then, given f2x = 2/4f1xωx+1/61/6, fx is obtained using the real part minus the imaginary part of f2x.
Another method of computing∑l=07Flω¯1/6lω¯lx is as follows:
∑l=07Flω¯1/6lω¯lx¯ = ∑l=07Fl¯ω1/6lωlx, so, in order to calculate the FFT of Flω¯1/6l with kernel function ω¯lx, we can firstly calculate the FFT of Fl¯ω1/6l with kernel function ωlx and then take the conjugate. The product of sparse matrix and signal flow graph of Φ can be directly used for FFT with kernel function ωlx.
In this example, the transformFl = 2/4∑x=07fxcas2π×9/8l+1/6x+1/6 is symmetric transform; thus, the inverse transform is the same as the positive transform. The inverse transform is(48)fx=24∑l=07Flcas2π×98l+16x+16.
Therefore, we can use the same fast algorithm as the positive transform.Figure 1
The FFT flow diagram.


## 4.3. Examples of the GODWT Application

(1)
In communication field, the communication between different users using different frequency bands is frequency division multiplexing, and the communication between different users relying on different address codes is code division multiplexing. The code division multiplexing and frequency division multiplexing can be combined by using GODWT. We still take the primitive unit rootω = expi2π×9/8, and three kernel functions of GODWT, that is, 2/4cas[2π×9/8xl], 2/4 cas [2π×9/8x+1/3l], and 2/4cas[2π×9/8x+2/3l] can be obtained. For the three transmitted code sequences, that is, ax, bx, and cx, x = 0, 1, …, 7, the transforms of them are calculated, respectively, to get Al, Bl, and Cl, where l = 0, 1, …, 7.(49)Al=24∑x=07axcas2π×98xl,Bl=24∑x=07bxcas2π×98x+13l,Cl=24∑x=07cxcas2π×98x+23l,Al=2/4∑x=07axcas2π×9/8xl; the equation is written in matrix forms as(50)A0,A1,…,A7=24a0,a1,…,a7cas9π40×0cas9π40×1…cas9π40×7cas9π41×0cas9π41×1…cas9π41×7⋮⋮⋮⋮cas9π47×0cas9π47×1…cas9π47×7.Let the carrier of code division multiplexing beZ10,Z11,…,Z17:(51)Z10=cas9π40×0cas9π40×1…cas9π40×7,the angular frequency ofZ10is9π4×0,Z11=cas9π41×0cas9π41×1…cas9π41×7,the angular frequency ofZ11is9π4×1,⋮⋮…⋮……⋮Z17=cas9π47×0cas9π47×1…cas9π47×7,the angular frequency ofZ10is9π4×7The carriersZ10Z11, …, Z17 are periodic and repetitive. The amounts of information carried by each carrier wave over a period are constant, which are 2/4a0, 2/4a1...2/4a7, respectively.The matrix equation above can be written as(52)A0,A1,…,A7=24a0Z10+a1Z11+⋯+a7Z17.In order to transmitAl = 2/4∑x=07axcas2π×9/8xl, l = 0, 1, …, 7, the angular frequency of carriers is from 9π/4×0 to 9π/4×7. It is called code division multiplexing where we have transmitting Al, l = 0, 1, …, 7 instead of transmitting ax, x = 0, 1, …, 7. Both the input and output are eight real numbers. In contrast, if we use the DFT, the output is eight complex numbers. The transmission of eight complex numbers requires the transmission of sixteen real numbers. Accordingly, the transmission efficiency of GODWT is two times that of DFT. Transmitting Bl and Cl instead of transmitting bx and cx is also code division multiplexing, but they all have different carriers. Bl = 2/4∑x=07axcas2π×9/8x+1/3l, l = 0, 1, …, 7; when transmitting Bl, the angular frequency of carriers is from 9π/4×0+1/3 to 9π/4×7+1/3. Cl = 2/4∑x=07cxcas2π×9/8x+2/3l, l = 0, 1, …, 7; when transmitting Cl, the angular frequency of carriers is from 9π/4×0+2/3 to 9π/4×7+2/3.When they are transmitted together, it is frequency division multiplexing. The receiver would receive their sum:(53)Al+Bl+Cl=24∑x=07axcas2π×98xl+24∑x=07bxcas2π×98x+13l+24∑x=07cxcas2π×98x+23l.These three components are separated with a filter, and thenaxbx,cx were restored using the inverse GODWT.Time-division multiplexing (TDM) is also a method to transmit multiway signals. Time-division multiplexing is used primarily for digital signals but may be applied in analog multiplexing in which two or more signals or bit streams are transferred appearing simultaneously as subchannels in one communication channel but are physically taking turns on the channel. Each signal appears on the line only a fraction of time in an alternating pattern. The time domain is divided into several recurrent time slots of fixed length.TransmittingAl, Bl, and Cl with different time slots, they can be separated at the receiving end, and then ax, bx, and cx were restored using the inverse GODWT. This realizes the combination of code-division multiplexing and time-division multiplexing. It shows that the proposed GODWT provides more means for the transmission in communication, compared with DHT and ODWT.(2)
In the digital hiding technology, the password can be embedded into transform coefficients.The secret key space of ODWT is (N, α, β), where (α, β) = {(0, 0), (1/2, 0), (0, 1/2), (1/2, 1/2)}, and N is a positive integer. Actually, N cannot be big; if N is bigger, it is not easy to calculate. The secret key space of GODWT is (N, q, α, β). It includes the secret key space of ODWT. Because the value of q is not limited in principle and the parameter value pairs (α, β) changed from 4 pairs of ODWT to infinity pairs of GODWT: (α, β) = g/2q1,h/2q2 where q1q2 = q, g and h can be any integers, the secret key space of GODWT has been greatly generalized.


## 5. Conclusions

The kernel function of the generalized DFT is1/Nexpi2π/Nql+αx+β, where (q, N) = 1, and parameters α and β can be any real numbers. When l = 0, 1, …, N-1, these N functions form a complex-valued normalized orthogonal system.For the kernel function1/Nexpi2π/Nql+αx+β of the generalized DFT, the real and imaginary parts are added together leading to the functions:1/N cas [2π/Nql+αx+β] =  1/Ncos2π/Nql+αx+β+sin2π/Nql+αx+β, (l = 0, 1, …, N-1). If q  =  q1q2, both q1 and q2 are positive integers; let α  =  g/2q1, β=h/2q2, where g and h are any integers. These N functions form a real normalized orthogonal system, where the independent variable x = 0, 1, …, N-1. The transform with the kernel function 1/N cas [2π/Nql+g/2q1x+h/2q2] is GODWT. For setting the values of α and β, if the factor μ1 of 2q1 replaces 2q1and the factor μ2 of 2q2 replaces 2q2, the conclusion is still valid.WhenN is a composite number, based on the fast algorithms of the generalized DFT and its inverse transform, we get the fast algorithm of the GODWT and its inverse transform.GODWT can replace the generalized DFT in wide applications. The transformed signal of the real sequence is still of real values, which makes the transmission and storage convenient. Also, GODWT provides a large number of basis functions with a new frequency, phase, and a large number of new transforms and subsumes a family of symmetric transforms; their forward and reverse transformations can be implemented by the same computer programs or hardware.It can be seen that GODWT can provide more transmission means for communication, better security for digital hiding technology, and many new methods for data compression. Hence, it can be used as a more powerful analysis and processing tool for communication, signal processing, and numerical computing.



---

*Source: 2529754-2021-01-11.xml*