Advertisement
2. Mapped real transform (MRT)
2.1 Forward 1-D MRT
The MRT Ykp of a 1-D sequence xn,0≤n≤N−1 is defined [7] as
Ykp=∑∀n⇒nkN=pxn−∑∀n⇒nkN=p+Mxnk=0,1,2…N−1,p=0,1,2…M−1,andM=N2E1
In Eq. (1), k can be considered analogous to the frequency in DFT, and p signifies the phase. Thus, 1-D MRT produces M arrays each of size N, given a signal of size N. Hence, MN coefficients have to be computed using only real additions. Another expression for the 1-D MRT [7] is
Ykp=∑n=0N−1Ak,p,nxn,0≤k≤N−1,0≤p≤M−1E2
1ifnkN=pAk,p,n=−1if∥nk∥N=p+M0otherwiseE3
Thus, the kernel Ak,p,n maps the data xn into the 1-D MRT Ykp. For example,
Let x=952361498976462, N=8.
Then, Ykp, the corresponding MRT of x, is
Yk0=44167761416776Yk1=0−530470530−47Yk2=01548−15015−48−15Yk3=0470−530−47053
2.2 Composition of MRT coefficients
One set of elements that combine to form an MRT coefficient contains those elements satisfying the congruence nkN=p, and another set contains those satisfying the congruence nkN=p+M. Thus, the two relevant congruences are:
nkN=pE4
nkN=p+ME5
The group of data elements whose indices satisfy the congruence relation nkN=p is defined as the positive data group or positive set of the 1-D MRT coefficient Ykp The group of data elements whose indices satisfy the congruence relation nkN=p+M is defined as the negative data group or negative set of the 1-D MRT coefficient Ykp. For example, the data elements x0,x2,x4,x6 form the positive set of the MRT coefficient Y40 and data elements x1,x3,x5,x7 form the negative set of the MRT coefficient Y40.
An MRT coefficient has two indices, frequency and phase. By formal definition of the MRT, phase has values in the range 0M−1. Although by definition, p∈0M−1, number theory allows p∈0N−1. p is referred to as a valid phase for a given value of k if k∣p. For example, for N=6, if k=2, then p=0,2,4 satisfy k∣p, and hence, these are valid phases for this value of k. A phase p is defined to be an allowable phase index if p<M.
2.3 Theorem 1: periodicity
Ykp=−Ykp+M
Proof. The elements na that are in the positive group of the MRT coefficient Ykp can be found as the solutions of
nakN=pE6
The elements na' that are in the negative group of the MRT coefficient Ykp can be found as the solutions of
na'kN=p+ME7
The elements nb that are in the positive group of the MRT coefficient Ykp+M can be found as the solutions of
nbkN=p+ME8
The elements nb' that are in the negative group of the MRT coefficient Ykp+M be found as the solutions of
nb'kN=p+M+M=p+N,whichcanbewrittenasnb'kN=pE9
From Eqs. (6) and (9), it can be inferred that
na=nb'E10
From Eqs. (7) and (8), it can be inferred that
na'=nbE11
From Eqs. (10) and (11) and the definition of MRT in Eq. (1),
Ykp=∑na−∑nb∑nb'−∑na'−∑na'−∑nb'−Ykp+M∴Ykp=−Ykp+M
2.4 Theorem 2: existence conditions
An MRT coefficient Ykp exists for data of order N if either of the following two conditions is satisfied:
Condition 1: gkN∣p
Condition 2: gkN∣p+M
If Condition 1 is satisfied, the positive data set is not a null set. If Condition 2 is satisfied, the negative data set of the MRT coefficient is not a null set.
Proof. An MRT coefficient Ykp exists given N if congruences (4) and/or (5) have solutions. The necessary and sufficient condition for (4) to have solutions is that gkN∣p. Similarly, gkN∣p+M becomes the necessary and sufficient condition for (5) to have solutions.
A linear congruence, nkN=p, if solvable, has gkN solutions mod N. Hence, there exist gkN solutions for n in the range 0N−1, and thus, there exist gkN elements in the positive set. Also, if there is a member n0 of the positive set (particular solution), the other solutions are n=n0+NgkNt,0≤t<gkN. These are the other members of the positive set.
The indices of the elements in the positive (or negative) set of an MRT coefficient form an arithmetic progression,
n0+jgk,j=0gkN−1E12
where n0 is the smallest member of the positive (or negative) set, and gk=NgkN.
2.5 Dependence of phase index on frequency
The existence of 1-D MRT coefficients can be studied for their dependence [15] on the frequency index k.
If k and N are relatively prime, then gkN=1. When gkN=1, the MRT coefficients corresponding to k are in existence for all values of p∈0M−1. When k divides N, gkN=k. The condition according to Eq. (4) now becomes k∣p. There are Nk such values of p in 0N−1. These are p=0,k,2k,…,N−k. The condition corresponding to Eq. (5) is now k∣p+M. When k∣p, the condition k∣p+M has solutions only if k divides M. Thus, an MRT coefficient has both positive and negative sets only if k divides M. Otherwise, only one among the positive or negative sets exists, for a given value of p.
When k divides M, the valid phases for which MRT coefficients have positive sets are p=0,k,2k,…,N−k. There are Nk such phases. When k∣M is satisfied, negative sets also exist for all these MRT coefficients. There are thus Mk allowable phases and hence Mk MRT coefficients, the phases are p=0,k,2k,…,M−k. These MRT coefficients have both positive and negative sets simultaneously.
When k is not a divisor of M, for a valid phase, only one among the positive or negative sets exists. The valid phases are an arithmetic series p=0,k,2k,…,N−k. In this case, there is no integer c that satisfies p+ck=p+M, and hence, Ykp=−Ykp+ck cannot be true. Thus, for p>M, where p is a valid phase, there is no valid phase index p−M. However, the relation Ykp=−Ykp−M is still satisfied. Thus, for p>M, there is an allowable but nonvalid phase p−M. We can use the relation Ykp=−Ykp−M to express the MRT corresponding to a valid phase index p>M in terms of an allowable phase index. MRT coefficients formed by valid phases have only positive sets. Thus, the positive set of the MRT coefficient with p>M is the negative set of the MRT coefficient with allowable nonvalid phase p−M. Hence, a subset of the M allowable phase indices are valid phases, while the other subset is made up of allowable nonvalid phases of the form p−M that are obtained from valid phases p>M.
The gap between two successive valid phases is k. Let there be an allowable and numerically smallest valid phase p1<M, and let the nearest allowable nonvalid phase be p2. The valid phase corresponding to p2is p2'=p2+M. Let q be the smallest integer such that qk>M. Then,
p2'=p1+qk
p2 is the closest allowable nonvalid phase to p1. p1 is the lowest allowable valid phase. There is no valid phase p1'=p1+M. The next valid phase is hence given by p2'=p1+qk, since q is the smallest integer such that qk>M
∴p2−p1=qk−M
Since k∣N, there is an integer t satisfying N=tk. Hence, Mk=t2. Since k does not divide M, t2 is not an integer. For this to be true, t has to be odd. We know k=Nt. Since the division of any even number by an odd number produces an even number, k has to be even. Since k∣N and k is even, it follows that k2∣M.
Hence,
M=dk2,dbeing an integer
p2−p1=qk−dk2
=2qk2−dk2
=2q−dk2
The value of 2q−d cannot be larger than 1, since, in that case,
p2−p1is greater than or equal tok.
The distance between p2' and M has to be lesser than k. Thus, the distance between p1 and p2 has to be lesser than k. Hence,
p2−p1=k2E13
The next valid phase after p1 is
p3=p1+kE14
From Eqs. (13) and (14),
p3−p2=k2
Let p4' be the next valid phase index after p2', then
p4'=p2'+kE15
p4' has a corresponding nonvalid allowable phase p4 given by
p4=p4'−ME16
From Eqs. (15) and (16),
p4=p2+k∴p4−p3=k2
Hence, there exists an allowable nonvalid phase between every consecutive pair of allowable valid phases. The MRT coefficient produced by these allowable nonvalid phases will have equal magnitude and opposite sign as the MRT coefficient produced by the corresponding non-allowable valid phases.
The sequence of allowable phase indices would thus be:
p0,p0+k2,p0+k,p0+3k2………………,p0+M−k2E17
When k does not divide M, MRT coefficients exist for these allowable phase indices and they will have either a positive group or a negative group only. There are Nk such allowable phases, and when k does not divide M,Nk is odd. Since k∣N, the condition for existence for solutions is k∣p. The smallest value of p that satisfies this condition is p=0. Hence, the first valid allowable phase is p0=0. MRT coefficients having only a positive set have allowable phases that are even multiples of k2, starting from 0 and ending at N−k2. There are N2k+12 such MRT coefficients. Similarly, the MRT coefficients having only a negative set have allowable phases that are odd multiples of k2, starting from k2 and ending at M−k. There are N2k−12 such MRT coefficients. The total number of 1-D MRT coefficients is thus Nk, and the sequence of allowable phases is:
0,k2,k,3k2,………………,M−k2E18
The sequence of allowable phases that correspond to MRT coefficients having only positive sets is
0,k,2k,………………,M−k2E19
and the sequence of allowable phases that correspond to MRT coefficients having only negative sets is
k2,3k2,5k2,.……………,M−kE20
2.6 Theorem 3: index of first element
a. When k∣N, the index na of the first element in the positive data group of an MRT coefficient Ykp is na=pk.
b. For k∣M, if an element with index n belongs in the positive data set of an MRT coefficient Ykp, then the element with index n+Mk occurs in the negative data set of the same MRT coefficient.
c. The first element in the positive set of an MRT coefficient Ykp when k does not divide M, has the index na=pk. The first element in the negative set of an MRT coefficient Ykp, when k does not divide M, is nb=p+Mk.
Proof.
a. The first element in MRT coefficient Ykp will have an index that is the smallest solution of (4),
nkN=p.
Solutions exist for Eq. (4) only if gkN divides p. Since gkN=k, the former condition can be written as k∣p.
Since k∣p, the smallest solution to Eq. (4) is na=pk, and thus na=pk is the first member in the positive data set of MRT coefficient Ykp.
The condition gkM=k is necessary for both positive and negative sets to be present in an MRT coefficient.
b. Given nkN=p,
n+MkkN=nkN+MkkN=p+M
Hence, if index n belongs in the positive set, index n+Mk will be present in the negative set since n+MkkN=p+M.
c. From (18), when k does not divide M, the sequence of allowable phase indices is
0,k2,k,3k2,…………….,M−k2
From (19), the sequence of allowable phase indices that correspond to MRT coefficients having only positive groups is
0,k,2k,…………………,M−k2
From (20), the sequence of allowable phase indices that correspond to MRT coefficients having only negative groups is
k2,3k2,5k2,.……………,M−k
The first data element that satisfies nkN=p is pk since k∣p is satisfied, p being a valid phase index. Hence, the first element in the positive set has index na=pk.
Also, the allowable phase indices that produce MRT coefficients having only negative sets are actually nonvalid allowable phase indices. If pbis a nonvalid phase index, there is a valid phase index pa given by pa=pb+M. Hence, the first data element in the negative set has the index nb=p+Mk.
If k does not divide N, then na=pgkN cannot be a solution since gkN∣k. The extended Euclidean algorithm can be used to find a particular solution for this case.
2.7 Closed-form expression for 1-D MRT
By the MRT definition, and looking at element indices of both positive and negative data sets in (12), and, assuming na belongs in the positive set, and nb in the negative set, a 1-D MRT coefficient can be expressed in the following manner:
Ykp=xna+xna+gk+xna+2gk+xna+3gk+..……+xna+gkN−1gk−xnb+xnb+gk+xnb+2gk+xnb+3gk+………+xnb+gkN−1gk
This can be written as
Ykp=∑j=0gkN−1xna+jgk−xnb+jgkE21
Here, Eq. (21) is a closed-form formula for MRT coefficients.
When k divides N, using Theorem 3(a), we observe that the first element in the positive set is na=pk. Also, using Theorem 3(b), any index in the positive set is related to any index in the negative set, given k∣M. This relation is nb=na+Mk When k does not divide M, from Theorem 3(c), we obtain the phases that correspond to MRT coefficients with only positive sets, and MRT coefficients with only negative sets.
When k∣M,na=pk, and nb=na+Mk. Also, k does not divide M. Using these, we can rewrite Eq. (21) as,
Ykp=xpk+xpk+Nk+xpk+2Nk+xpk+3Nk+……..+xpk+k−1Nk−xpk+N2k+xpk+3N2k+xpk+5N2k+xpk+7N2k+……..+xpk+2k−1N2kE22
On further simplification,
Ykp=∑j=0k−1xjN+pk−x2j+1N+2p2k
p=0,k,2k,…,M−kE23
When k does not divide M, it has been seen that positive and negative groups cannot exist together for the same MRT coefficient. For certain values of p, only positive groups exist. For other values of p, only negative groups exist. As seen, for positive groups, na=pk, and for negative groups, nb=p+Mk. An MRT coefficient with only a positive group has the following form:
Ykp=xpk+xpk+Nk+xpk+2Nk+xpk+3Nk+……..+xpk+k−1Nk
which, when simplified, becomes
Ykp=∑j=0k−1xjN+pkp=0,k,2k,…,M−k2E24
Similarly, an MRT coefficient with only a negative group has the following form:
Ykp=−xp+Mk+xp+Mk+Nk+xp+Mk+2Nk+……..+xpk+k−1Nk
which, when simplified, becomes
Ykp=−∑j=0k−1xjN+p+Mkp=k2,3k2,…,M−kE25
When k and N are co-prime, gkN=1. Hence, the positive set has only one element and similarly the negative set too has only one element. The values of na and nb have to be computed using the Euclidean algorithm or by the trial-and-error method. The MRT coefficient has the following form
Ykp=xna−xnbp=0,1,2,3,…M−1E26
2.8 Physical significance
An MRT coefficient possesses both frequency and phase. A DFT coefficient has only the frequency index. Hence, the presence of an extra index distinguishes the MRT coefficient. The physical significance of an MRT coefficient is that the phase specifies the beginning of the frequency cycle. The MRT can thus be thought of as a time-frequency representation of a 1-D signal. In contrast to the DFT, the MRT while related to the DFT, has localization in both time and frequency. Also, MRT coefficients can be considered to be constituent parts of the DFT; these parts, if weighted by the exponential kernel, would produce the DFT. For N=8, the DFT coefficient Yk can be expressed in terms of associated MRT as
Yk=Yk0W80+Yk1W81+Yk2W82+Yk2W83
Advertisement
3. Redundancy in MRT
For some values of N, a set of MRT coefficients having different values for frequency and phase have the same magnitude. The polarity of the coefficients may be different. This phenomenon is an indication of redundancy in MRT. The MRT can be relieved of the redundancy to arrive at a simpler transform that has no redundancy.
3.1 Theorem 4: complete redundancy
Given Ykp, for all h such that ghN=1
YhkNhpN=YkpforhpN<M,and,YhkNhpN−M=−YkpforhpN≥M
Proof. From a basic theorem [16] in number theory, if
qN=dE27
and h is a multiplication factor, then
hqNghN=hdE28
If ghN=1, Eq. (28) becomes
hqN=hdE29
Given Ykp, and a set of indices n that satisfies
nkN=pE30
and a set of indices n′ that satisfies
n'kN=p+ME31
If there is h such that ghN=1, using Eqs. (27)–(29),
nhkN=hpE32
and
n'hkN=hp+ME33
n'hkN=hp+hME34
Since ghN=1,h is odd, and hence
hp+hM≡hp+ME35
Using Eq. (35), Eq. (34) may be written as
n'hkN=hp+ME36
From the definition of MRT, and Eqs. (32) and (36), it is seen that the set of indices n and n' form the MRT coefficient YhkNhpN. Using Eqs. (30)–(32) and (36),
YhkNhpN=YkpE37
If hpN≥M, then
YhkNhpN−M=−YkpE38
since
Ykp=−Ykp−M=−Ykp+M
Hence, the theorem on complete redundancy has been proved.
From Theorem 4, we see that prediction of redundancy is possible from the knowledge of N, frequency and phase. Given kp, frequency and phase pairs of redundant MRT coefficients are given by Theorem 4. The redundancy condition is that the factor of multiplication that connects the frequencies of redundant MRT coefficients should be co-prime to N. As an example, for N=6, MRT coefficients of k=5 are completely redundant MRT coefficients of k=1, since 1 and 5 are co-prime to 6.
If k'=hk and ghN=1, then MRT coefficients of the two frequency indices k and k' are redundant.
When k=1, MRT coefficients having frequency k′ that are co-prime to N can be obtained from MRT coefficients with a frequency of k=1. If k'∣N, then we cannot obtain k' by multiplying an integer k with an integer h,k'=hk, satisfying ghN=1 and k≠k' Thus, MRT coefficients with frequency indices that are divisors of N cannot be redundant to each other.
Let k′ satisfy k'=hk such that ghN=1 and k≠k'. If k' is nonprime, there is a nontrivial common divisor with N. So, even though it is not a divisor of N, it will have complete redundancy with the common divisor.
3.2 Theorem 5: redundancy frequency groups
MRT coefficients with frequency indices that have common gcd w.r.t. N are all completely redundant to each other.
Proof. Assume k1 and k2 are two frequency indices that have common gcd w.r.t. N.
gk1N=kE39
gk2N=kE40
Assume h exists such that
ghN=1E41
From Eq. (41), h and N are co-prime. Hence,
ghk1N=kE42
hk1N=hk1−Nqif0≤hk1−Nq<N,q∈ZE43
Using Eq. (43) and gcd property,
ghk1NN=ghk1−NqN=ghk1N=kE44
From Eqs. (40) and (44),
k2=hk1NE45
From Eqs. (41) and (45), and using Theorem 4, it can be concluded that frequency indices k1 and k2 are completely redundant. Hence, the theorem is proved.
For example, if N=8, the following relations exist:
Y10=Y30=Y50=Y70Y11=Y33=−Y51=−Y73,Y12=−Y32=Y52=−Y72and,Y13=Y31=−Y53=−Y71.
Since k=1,3,5 and 7 share the same gcd of 1 w.r.t. N, there is redundancy among the MRT coefficients of these frequencies. Similarly, since g28=g68=2, Y20=Y60, and Y22=−Y62.
Theorem 5 shows that we can group frequencies based on their gcd w.r.t. N. AII nondivisor frequency indices are related to divisor frequency indices through multiplication factors h such that ghN=1. The count of the possible factors of multiplication involved in complete redundancy is Euler’s totient function ΦN, which specifies the count of positive integers smaller than or equal to N that are co-prime to N, 1 being considered co-prime to every other integer. Given 1-D MRT coefficients having frequency k=1, there would be ΦN−1 other frequencies whose MRT coefficients can be obtained from this MRT coefficient. Combined with k=1, these ΦN frequencies thus comprise the group of frequencies that satisfy ghN=1. There are other sets of frequency indices that have a common gcds w.r.t. N.; and each group corresponds to a some divisor of N. There are ΦN possible factors of multiplication that produce other members of the group of frequency indices associated with k. From Theorem 4, the equation for complete redundancy is k'=hkN, where ghN=1. Also,
hkN=h+NkkNE46
Eq. (46) implies that the set of k' that is generated from divisor k is unique only for multiplicative factors in the set 0Nk−1, and repeats thereafter for the remaining sets of the same length. Hence, the problem now gets reduced to k'=hkN/k where ghNk=1. The number of such multiplicative factors h is ΦNk, and these factors are the totatives of Nk Hence, the number of frequency indices that are related by complete redundancy to a frequency index k is given by ΦNk and they are obtained by k'=hkN where ghNk=1.
From number theory [17],
∑dVNΦd=N,ifN≥1,E47
From Eq. (47), the sum of the terms ΦNk over all divisors of N is given by N, since ∑d∣NΦd=∑d∣NΦNd. Hence, all the N frequency indices k=0N−1 have been mapped.
Thus, all the frequency indices of 1-D MRT can be classified on the basis of their gcd w.r.t. N.
3.3 Theorem 6: Mapping between phase indices
One-to-one mapping exists between phases of 1-D MRT coefficients having frequencies k and k' connected through complete redundancy.
Proof. For two MRT coefficients having frequencies k and k′ connected by complete redundancy, the number of phases corresponding to each frequency is equal since gkN=gk'N, and the number of phase indices is given by NgkN. The phases lie in the range 0M−1. From Theorem 4 on complete redundancy, the relation between phases is given by p′=hpN,ghN=1. Using a theorem on the reduced residue systems, on multiplication with h, the resulting group of phase indices p' too have the same elements as the original group. Multiplication of phases in 0M−1 by h and then computing modulo w.r.t. M produces the same group, but with the order possibly altered. Thus, one-to-one mapping exists between the phases of 1-D MRT coefficients having frequencies k and k' connected through complete redundancy.
To look at an example, when N=8,
Y10=Y30,Y11=Y33Y12=−Y32,and,Y13=Y31.
Since k=1 and k=3 are redundant through the co-prime h=3, the set of phase indices of k=1,p=0,1,2,3, when subjected to the operation p′=hpN would result inp'=0,3,6,1, which reduces to p'=0,3,2,1 after the condition hpN<M is checked and relevant sign change. Hence, p=0,1,2,3 maps to p'=0,3,2,1.
3.4 Derived redundancy
For N=6,
Y30=Y10−Y11+Y12
Certain MRT coefficients can be obtained using the summation of certain other unique MRT coefficients. This phenomenon is also a kind of redundancy, but it cannot be considered as complete redundancy. This phenomenon is referred to as derived redundancy. An MRT coefficient is considered a derived MRT coefficient if we can be obtain it by combining other MRT coefficients.
Let Yk'p and Ykpa be the two MRT coefficients. The congruence relations for Ykpa are nkN=paandnkN=pa+M. The congruence relations for Yk'p are nk′N=p and nk′N=p+M. Assume that a relation k'=dk exists between k and k'. Hence, dnkN=p and dnkN=p+M.dnkN=p may be written as nkN=pd if gdN=d, and d∣p. In other words, d should be a divisor of N. From nkN=pd and nkN=pa,pa=pd. Multiplying both sides of nkN=pa+M by d,dnkN=dpa+dM. If d is odd, this can be written as dnkN=dpa+M, which becomes nk′N=p+M. Hence, provided there exists an odd-valued divisor d of N, such that k'=dk, then there is derived redundancy between and Yk'p and Ykpa. Hence, we can conclude that there cannot be derived redundancy when N is a power of 2 since N has no divisors that are odd. For even N not a power of 2, derived redundancy exists since N then has divisors that are odd. Details of derived redundancies are shown in Tables 1 and 2 for N=6 and N=24, respectively.
N = 6 | Complete redundancy (5) | Derived redundancy (3) |
1 | 5 | 3 |
2 | 4 | 6 |
3 | | |
6 | | |
Table 1.
Complete redundancy and derived redundancy relations for N = 6.
N = 24 | Co-primes | Odd divisors |
5 | 7 | 11 | 13 | 17 | 19 | 23 | 3 |
1 | 5 | 7 | 11 | 13 | 17 | 19 | 23 | 3 |
2 | 10 | 14 | 22 | | | | | 6 |
3 | 15 | 21 | 9 | | | | | |
4 | 20 | | | | | | | 12 |
6 | | 18 | | | | | | |
8 | 16 | | | | | | | 24 |
12 | | | | | | | | |
24 | | | | | | | | |
Table 2.
Complete redundancy and derived redundancy relations for N = 24.
Advertisement
4. Unique MRT
Based on the two types of redundancy presented above, MRT coefficients can be considered to be unique or relatively unique. It is impossible to obtain MRT coefficients of divisor frequencies from MRT coefficients of other divisor frequencies by complete redundancy. These can hence be named as unique MRT coefficients. If divisors have a relationship to other divisors by multiplication using a divisor that is odd-valued, derived redundancy is exhibited by them. They are thus considered only relatively unique. For N=6, the set of divisor frequencies is {1, 2, 3, 6}. In this set, 3 and 6 are relatively unique divisor frequencies. If we remove these, we obtain the absolutely unique divisor set {1, 2}. It is not possible to express absolutely unique divisors as k'=dk, for d an odd integer. Considering the divisor set of N, this condition is satisfied only by divisors that are powers of 2, as observed in the above example. If k'=2a, then given any k and odd-valued d except d=1,k'≠dk. So, the unique divisor set for N contains only divisors which are powers of 2. MRT coefficients formed by unique divisor frequencies are referred to as unique MRT (UMRT) coefficients. Thus, 1-D UMRT is the set of all MRT coefficients having frequencies that are powers of 2.
4.1 Number of unique coefficients
In total, there are MN MRT coefficients given a signal of size N. Now arises the question of the exact number of UMRT coefficients.
If N is a power of 2, the frequencies that form unique coefficients are themselves powers of 2. Since, k=0=NN and N a power of 2, then k=0 produces a unique coefficient. The first frequency index is k=1, and followed by k=2,4,…,N. The number of unique coefficients produced by each frequency index k is given by the number of allowable phase indices for each frequency index k. For an MRT coefficient Ykp to exist, p should be divisible by k. When k=N, this condition has only one solution for p,p=0. All other frequency indices have Mk coefficients each. Hence, the total number of UMRT coefficients is given by
Tot=1+∑t=0log2MM2t=1+M∑t=0log2M12t=1+M1−12log2M+112=1+N1−2−log2M+1=1+N1−1N=N
Hence, the number of UMRT coefficients, when N is a power of 2, is N.
If N is not a power of 2, k=0 does not produce UMRT coefficients. Let k' be the highest power of 2 frequency and a divisor of N. Hence N=dk',d being an odd integer; if d has an even value, then it would violate the assumption that k' is the highest power of 2 frequency and a divisor of N. Since d has an odd value, it is not possible for k' to be a divisor for M as d2 cannot be integer-valued. The number of valid phase indices is Nk' and thus there exist Nk' MRT coefficients in the case that k' does not divide M. AII the numbers that are powers of 2 and divide N and are smaller than k' will be divisors of M. These are k=1,2,4,…,k'2. There are Mk MRT coefficients produced by these frequencies. When N is not a power of 2, frequency k=0 can be obtained by derived redundancy. A frequency k=0 is equivalent to k=N, since NN=0. Frequency N relates to k' through N=dk',d being odd. This can be recalled to be sufficient for derived redundancy to occur. Thus, in case if N is not a power of 2, k=0 does not form an absolutely unique MRT coefficient. Hence, the total number of UMRT coefficients is
Tot=1+∑t=0log2MM2t=1+M1−12log2M+112=Nk'+N1−22k'=N
We thus conclude that N UMRT coefficients are needed to represent a 1-D signal of length N, whether N is a power of 2 or not, and these coefficients are produced by frequencies that are divisors of N and powers of 2, beginning with k=1.
The 1-D UMRT coefficients can be computed as below:
(i) N a power of 2
Y00=∑n=0N−1xnE48
Ykp=∑j=0k−1xjN+pk−x2j+1N+2p2kk=2t,0≤t≤log2M,p=tk,0≤t≤Mk−1E49
(ii) N not a power of 2
Ykp=∑j=0k−1xjN+pk−x2j+1N+2p2kk=2t,0≤t≤log2M,p=tk,0≤t≤Mk−1E50
Yk'p=∑j=0k'−1xjN+pkp=tk',0≤t≤Mk'−12E51
Yk'p=−∑j=0k'−1xjN+p+Mk'p=tk'+k'2,0≤t≤Mk'−32E52
where k' is the highest frequency index that is a power of 2 and also a divisor of N.
Advertisement
5. Inverse MRT
5.1 Theorem 7: N a power of 2
Given the UMRT of a 1-D signal of size N, N being a power of 2, the 1-D signal can be reconstructed from its UMRT by the following formula
xn=1NY00+∑t=0log2M12t+1Y2t2tnN,0≤n≤N−1E53
Proof. The data element that needs to be recovered from the UMRT is given by xn. For any frequency index k, the value of the phase index p of the UMRT coefficient Ykp that contains xn is given by nk nkN=p. Thus for a frequency that is a power of 2, k=2a, the UMRT coefficient that contains xn is Y2a2anN. The UMRT coefficient Y00 contains all the elements of the data including xn since nkN=0,∀n, when k=0. In Eq. (53), Y00 has a factor of multiplication 1N, and the remaining UMRT coefficients have a factor of multiplication 12t+1. Consequently, the xn that is a part of these coefficients have the corresponding factors of multiplication. The resultant multiplication factor f for xn due to the summation is obtained as a sum of the individual factors of multiplication.
f=1N+∑t=0log2M12t+1=1N+∑t=0log2M2−t+1=1N+121−2−log2M+112=1N+1−1N=1
Hence, as a result of the summation, one of the components of the result is the data xn.
A UMRT coefficient Y2a2anN contains other terms besides xn. For the inverse transform formula to be correct, these other terms that occur in the various UMRT coefficients Y2a2anN need to get canceled off. It can be proved that they vanish. Let k be the smallest frequency at which any other data elements co-occur with xn. Y00 can be excluded as all data elements co-occur in it with a positive sign. Leaving out Y00, another element shows co-occurrence with xn for the first time for k=1. For example, for N=8,Y10=x0−x4. Hence, if x0 is the element to be obtained, it is seen that x4 occurs with an opposite sign along with x0 in the MRT coefficient corresponding to k=1, given byY10. From Eq. (12), when k=1,gkN=1 and so both positive and negative data sets contain only one element each. Using Theorem 3(b), the distance between corresponding elements in the two data groups is Mk. Hence, xn and xn+M, occur having opposite polarity, in any MRT coefficient of frequency k=1. In the same way, for k=2, the data element xn+Moccurs with positive sign since Y2p=xn−xn+N4+xn+N2−xn+3N4, given nkN=p. From (12), the distance between the two successive data elements in a positive or negative group is given by NgkN. Since k is a divisor of N, this reduces to Nk. Using Theorem 3(b), if elements xn', and xn co-occur in Ykp but having different signs, then,
n'=n+qoddN2kE54
where qoddis an odd integer. At the next higher frequency k'=2k, Eq. (54) becomes
n'=n+qoddNk'E55
From (12), the general form for a data element xn' of same sign present along with an element xn in the MRT coefficient Yk'p is given by (since k' is a divisor of N,gk'N=k')
n'=n+jNk'E56
where j=0,1,2,3,…,k'−1.
Equation (55) can be seen to be a special case of Eq. (56). For any higher frequency k'=2k, Eq. (56) holds. Hence, given k is the lowest frequency at which xn' and xn occur with opposite signs, for all larger frequencies k'=2k,xn' and xn occur with similar signs. For N=8,Y10=x0−x4,Y20=x0−x2+x4−x6 and Y40=x0−x1+x2−x3+x4−x5+x6−x7. Data elements x4 and x0 occur with opposite signs in Y10 and similar signs in higher frequencies, k=2,k=4. Conversely, another conclusion is that elements xn' and xn that co-occur with same signs in a UMRT coefficient having frequency k' also co-occur with opposite signs in a UMRT coefficient having frequency k where k'=2k.
Given k is the lowest frequency where xn' and xn co-occur with an opposite sign, the factor of multiplication for xn' in the inverse transform formula is −12k. In the case of higher frequencies till M, the factor of multiplication is 12k',k'=2k,4k,…M. Thus the sum of the series
f=1N−12k+14k+18k+…12ME57
will provide the value of the multiplication factor f associated with element xn'.
Assume k=Nq. First the sum of the following series can be found:
14k+18k+…12M=fafa=∑j=log22Nqlog2M12j+1
The number of terms in this summation is log2q−1.
fa=q4N1−2−log2q−112=q2Nq−2q=q−22N
From Eq. (57),
f=1N−12k+fa=1N−12k+q−22N=q2N−12k=0
Thus, all the other data elements xn' that occur along with xn in the various MRT coefficients in the summation of the inverse formula cancel out, leaving behind only the desired data element xn.
Hence, the formula for inverse UMRT is proved.
5.2 Theorem 8: N not a power of 2
Given the UMRT of a 1-D signal of size N, N not being a power of 2, the 1-D signal can be reconstructed from its UMRT by the following formula
xn=1k'Yk'nk'N+∑t=0log2k'−112t+1Y2t2tnNE58
where k' is the highest frequency index that is a power of 2 and also a divisor of N.
Proof.xn has to be obtained from the UMRT. Given Ykp data element xn has to satisfy nkN=p. For k=2a, the UMRT coefficient Y2a2anN contains xn. The UMRT coefficient Yk'nk'N is multiplied by 1k', and the other UMRT coefficients are multiplied by 12t+1. The resultant factor f that multiplies xn as a result of the summation can be proved by using the same method used earlier. Similarly, it can also be shown that data elements other than xn cancel out in the summation, leaving behind only the desired data element xn. Hence, the proposed formula is proved.
5.3 General formula for any even N
Equation (58) can be generalized to be applicable to any even value of N. Hence, the following equation can be used for signal reconstruction from UMRT, for a signal of size N,N being any even number.
xn=1k'Yk'Nnk'N+∑t=0log2k'−112t+1Y2t2tnNE59
where k' is the highest power of 2 divisor of N.
For N a power of 2, the UMRT basis matrix can be defined in a new form by combining the frequency index k and the phase index p of an MRT coefficient into an index q as follows:
H0m=H0,0m=11,nkN=p
Hqm=Hk,pm={−1,nkN=p+N20,otherwiseq=2k+p−1m=0,1,…,N−1
This structure of the UMRT definition has a similar form as that of the Haar transforms [10]. Table 3 shows the mapping for N=8.
k,p | 0,0 | 1,0 | 1,1 | 1,2 | 1,3 | 2,0 | 2,2 | 4,0 |
q | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
Table 3.
Proposed mapping between 1-D UMRT indices and array indices, for N = 8.