Open access peer-reviewed chapter

A New Integer-to-Integer Transform

Written By

Rajesh Cherian Roy

Submitted: February 12th, 2020 Reviewed: July 10th, 2020 Published: September 21st, 2020

DOI: 10.5772/intechopen.93356

Chapter metrics overview

422 Chapter Downloads

View Full Metrics


This chapter presents a detailed analysis of an integer-to-integer transform that is closely related to the discrete Fourier transform, but that offers insights into signal structure that the DFT does not. The transform is analyzed for its underlying properties using concepts from number theory. Theorems are given along with proofs to help establish the salient features of the transform. Two kinds of redundancy exist in the transform. It is shown how redundancy implicit in the transform can be eliminated to obtain a simple form. Closed-form formulas for the forward and inverse transforms are presented.


  • transforms
  • discrete transforms
  • integer transforms
  • DFT
  • MRT

1. Introduction

Transforms are tools used in signal processing to arrive at deeper insights into the underlying structure of signals. The discrete Fourier transform (DFT), discrete cosine transform (DCT) [1], discrete sine transform (DST), discrete Hartley transform (DHT) [2], and discrete wavelet transform (DWT) are significant discrete transforms. Discrete transforms are characterized by their basis matrices. The Haar transform is distinct in that its basis matrix has only 1, −1, or 0as elements. The Walsh-Hadamard transform basis matrix is entirely composed of 1 and −1. The discrete Fourier preprocessing transform [3] also has only 1, −1, or 0in its basis matrix. A new discrete transform, M-dimensional real transform (MRT) based on linear congruences was first proposed [4] for two-dimensional signals. Its basis matrix contains 1, −1, and 0only. However, it has a high level of redundancy. The orthogonal discrete periodic radon transform (ODPRT) [5] is another transform that is based on linear congruences. MRT has been applied to image compression by making use of a set of unique MRT coefficients [6, 7]. A one-dimensional form of the MRT exists [8]. The Haar transform is related to the Walsh-Hadamard transform [9]. The MRT is related [10] to the Haar transform. One can be obtained from the other through a sequence of bit reversal operations on the rows and columns. Similarly, the Hadamard transform and the MRT can be derived from each other [11]. In [12], 2-D gcd-delta functions that contain only zeroes and ones are used to generate integer 2D DFT pairs. The Weyl transform which has binary valued inner elements is described in [13]. Integer-to-integer approximations of DST are still an active research area, as can be seen in [14]. In comparison to most integer-to-integer transforms, the MRT is distinguished by the utmost simplicity of its kernel. In this context, the MRT can be grouped together with Haar and Walsh-Hadamard transforms as regards the contents of their basis matrices. This chapter presents a detailed study of the MRT in its one-dimensional form and offers an analytical path that justifies placing the MRT beside the Haar transform in the family of discrete transforms.

The MRT is defined and its salient characteristics are presented by way of theorems and their proofs. The redundancy inherent in the MRT is studied and the redundancy-removed version of the MRT named the unique MRT (UMRT) is presented. The inverse UMRT is presented. Described next is a form of the UMRT basis matrix which can be indexed using only 2 indices.


2. Mapped real transform (MRT)

2.1 Forward 1-D MRT

The MRT Ykpof a 1-Dsequence xn,0nN1is defined [7] as


In Eq. (1), kcan be considered analogous to the frequency in DFT, and psignifies the phase. Thus, 1-D MRT produces Marrays each of size N, given a signal of size N. Hence, MNcoefficients have to be computed using only real additions. Another expression for the 1-D MRT [7] is


Thus, the kernel Ak,p,nmaps the data xninto the 1-D MRT Ykp. For example,

Let x=952361498976462, N=8.

Then, Ykp, the corresponding MRT of x, is


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:


The group of data elements whose indices satisfy the congruence relation nkN=pis defined as the positive data group or positive set of the 1-D MRT coefficient YkpThe group of data elements whose indices satisfy the congruence relation nkN=p+Mis defined as the negative data group or negative set of the 1-D MRT coefficient Ykp. For example, the data elements x0,x2,x4,x6form the positive set of the MRT coefficient Y40and data elements x1,x3,x5,x7form 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 0M1. Although by definition, p0M1, number theory allows p0N1. pis referred to as a valid phase for a given value of kif kp. For example, for N=6, if k=2, then p=0,2,4satisfy kp, and hence, these are valid phases for this value of k. A phase pis defined to be an allowable phase index if p<M.

2.3 Theorem 1: periodicity


Proof. The elements nathat are in the positive group of the MRT coefficient Ykpcan be found as the solutions of


The elements na'that are in the negative group of the MRT coefficient Ykpcan be found as the solutions of


The elements nbthat are in the positive group of the MRT coefficient Ykp+Mcan be found as the solutions of


The elements nb'that are in the negative group of the MRT coefficient Ykp+Mbe found as the solutions of


From Eqs. (6) and (9), it can be inferred that


From Eqs. (7) and (8), it can be inferred that


From Eqs. (10) and (11) and the definition of MRT in Eq. (1),


2.4 Theorem 2: existence conditions

An MRT coefficient Ykpexists for data of order Nif either of the following two conditions is satisfied:

Condition 1: gkNp

Condition 2: gkNp+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 Ykpexists given Nif congruences (4) and/or (5) have solutions. The necessary and sufficient condition for (4) to have solutions is that gkNp. Similarly, gkNp+Mbecomes the necessary and sufficient condition for (5) to have solutions.

A linear congruence, nkN=p, if solvable, has gkNsolutions mod N. Hence, there exist gkNsolutions for nin the range 0N1, and thus, there exist gkNelements in the positive set. Also, if there is a member n0of the positive set (particular solution), the other solutions are n=n0+NgkNt,0t<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,


where n0is 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 kand Nare relatively prime, then gkN=1. When gkN=1, the MRT coefficients corresponding to kare in existence for all values of p0M1. When kdivides N, gkN=k. The condition according to Eq. (4) now becomes kp. There are Nksuch values of pin 0N1. These are p=0,k,2k,,Nk. The condition corresponding to Eq. (5) is now kp+M. When kp, the condition kp+Mhas solutions only if kdivides M. Thus, an MRT coefficient has both positive and negative sets only if kdivides M. Otherwise, only one among the positive or negative sets exists, for a given value of p.

When kdivides M, the valid phases for which MRT coefficients have positive sets are p=0,k,2k,,Nk. There are Nksuch phases. When kMis satisfied, negative sets also exist for all these MRT coefficients. There are thus Mkallowable phases and hence MkMRT coefficients, the phases are p=0,k,2k,,Mk. These MRT coefficients have both positive and negative sets simultaneously.

When kis 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,,Nk. In this case, there is no integer cthat satisfies p+ck=p+M, and hence, Ykp=Ykp+ckcannot be true. Thus, for p>M, where pis a valid phase, there is no valid phase index pM. However, the relation Ykp=YkpMis still satisfied. Thus, for p>M, there is an allowable but nonvalid phase pM. We can use the relation Ykp=YkpMto express the MRT corresponding to a valid phase index p>Min 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>Mis the negative set of the MRT coefficient with allowable nonvalid phase pM. Hence, a subset of the Mallowable phase indices are valid phases, while the other subset is made up of allowable nonvalid phases of the form pMthat 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 qbe the smallest integer such that qk>M. Then,


p2is the closest allowable nonvalid phase to p1. p1is 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 qis the smallest integer such that qk>M


Since kN, there is an integer tsatisfying N=tk. Hence, Mk=t2. Since kdoes not divide M, t2is not an integer. For this to be true, thas to be odd. We know k=Nt. Since the division of any even number by an odd number produces an even number, khas to be even. Since kNand kis even, it follows that k2M.


M=dk2,dbeing an integer

The value of 2qdcannot be larger than 1, since, in that case,

p2p1is greater than or equal tok.

The distance between p2'and Mhas to be lesser than k. Thus, the distance between p1and p2has to be lesser than k. Hence,


The next valid phase after p1is


From Eqs. (13) and (14),


Let p4'be the next valid phase index after p2', then


p4'has a corresponding nonvalid allowable phase p4given by


From Eqs. (15) and (16),


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:


When kdoes 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 Nksuch allowable phases, and when kdoes not divide M,Nkis odd. Since kN, the condition for existence for solutions is kp. The smallest value of pthat 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 0and ending at Nk2. There are N2k+12such MRT coefficients. Similarly, the MRT coefficients having only a negative set have allowable phases that are odd multiples of k2, starting from k2and ending at Mk. There are N2k12such MRT coefficients. The total number of 1-D MRT coefficients is thus Nk, and the sequence of allowable phases is:


The sequence of allowable phases that correspond to MRT coefficients having only positive sets is


and the sequence of allowable phases that correspond to MRT coefficients having only negative sets is


2.6 Theorem 3: index of first element

a. When kN, the index naof the first element in the positive data group of an MRT coefficient Ykpis na=pk.

b. For kM, if an element with index nbelongs in the positive data set of an MRT coefficient Ykp, then the element with index n+Mkoccurs in the negative data set of the same MRT coefficient.

c. The first element in the positive set of an MRT coefficient Ykpwhen kdoes not divide M, has the index na=pk. The first element in the negative set of an MRT coefficient Ykp, when kdoes not divide M, is nb=p+Mk.


a. The first element in MRT coefficient Ykpwill have an index that is the smallest solution of (4),


Solutions exist for Eq. (4) only if gkNdivides p. Since gkN=k, the former condition can be written as kp.

Since kp, the smallest solution to Eq. (4) is na=pk, and thus na=pkis the first member in the positive data set of MRT coefficient Ykp.

The condition gkM=kis necessary for both positive and negative sets to be present in an MRT coefficient.

b. Given nkN=p,


Hence, if index nbelongs in the positive set, index n+Mkwill be present in the negative set since n+MkkN=p+M.

c. From (18), when kdoes not divide M, the sequence of allowable phase indices is


From (19), the sequence of allowable phase indices that correspond to MRT coefficients having only positive groups is


From (20), the sequence of allowable phase indices that correspond to MRT coefficients having only negative groups is


The first data element that satisfies nkN=pis pksince kpis satisfied, pbeing 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 pbisa nonvalid phase index, there is a valid phase index pagiven by pa=pb+M. Hence, the first data element in the negative set has the index nb=p+Mk.

If kdoes not divide N, then na=pgkNcannot be a solution since gkNk. 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 nabelongs in the positive set, and nbin the negative set, a 1-D MRT coefficient can be expressed in the following manner:


This can be written as


Here, Eq. (21) is a closed-form formula for MRT coefficients.

When kdivides 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 kM. This relation is nb=na+MkWhen kdoes 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 kM,na=pk, and nb=na+Mk. Also, kdoes not divide M. Using these, we can rewrite Eq. (21) as,


On further simplification,


When kdoes 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:


which, when simplified, becomes


Similarly, an MRT coefficient with only a negative group has the following form:


which, when simplified, becomes


When kand Nare 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 naand nbhave to be computed using the Euclidean algorithm or by the trial-and-error method. The MRT coefficient has the following form


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 Ykcan be expressed in terms of associated MRT as


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 hsuch that ghN=1


Proof.From a basic theorem [16] in number theory, if


and his a multiplication factor, then


If ghN=1, Eq. (28) becomes


Given Ykp, and a set of indices nthat satisfies


and a set of indices n′ that satisfies


If there is hsuch that ghN=1, using Eqs. (27)(29),




Since ghN=1,his odd, and hence


Using Eq. (35), Eq. (34) may be written as


From the definition of MRT, and Eqs. (32) and (36), it is seen that the set of indices nand n'form the MRT coefficient YhkNhpN. Using Eqs. (30)(32) and (36),


If hpNM, then




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=5are completely redundant MRT coefficients of k=1, since 1 and 5 are co-prime to 6.

If k'=hkand ghN=1, then MRT coefficients of the two frequency indices kand k'are redundant.

When k=1, MRT coefficients having frequency k′that are co-prime to Ncan be obtained from MRT coefficients with a frequency of k=1. If k'N, then we cannot obtain k'by multiplying an integer kwith an integer h,k'=hk, satisfying ghN=1and kk'Thus, MRT coefficients with frequency indices that are divisors of Ncannot be redundant to each other.

Let k′ satisfy k'=hksuch that ghN=1and kk'. 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 gcdw.r.t. Nare all completely redundant to each other.

Proof.Assume k1and k2are two frequency indices that have common gcdw.r.t. N.


Assume hexists such that


From Eq. (41), hand Nare co-prime. Hence,


Using Eq. (43) and gcdproperty,


From Eqs. (40) and (44),


From Eqs. (41) and (45), and using Theorem 4, it can be concluded that frequency indices k1and k2are completely redundant. Hence, the theorem is proved.

For example, if N=8, the following relations exist:


Since k=1,3,5and 7 share the same gcdof 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 gcdw.r.t. N. AII nondivisor frequency indices are related to divisor frequency indices through multiplication factors hsuch 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 Nthat 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 ΦN1other frequencies whose MRT coefficients can be obtained from this MRT coefficient. Combined with k=1, these ΦNfrequencies 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 ΦNpossible 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,


Eq. (46) implies that the set of k'that is generated from divisor kis unique only for multiplicative factors in the set 0Nk1, and repeats thereafter for the remaining sets of the same length. Hence, the problem now gets reduced to k'=hkN/kwhere ghNk=1. The number of such multiplicative factors his ΦNk, and these factors are the totatives of NkHence, the number of frequency indices that are related by complete redundancy to a frequency index kis given by ΦNkand they are obtained by k'=hkNwhere ghNk=1.

From number theory [17],


From Eq. (47), the sum of the terms ΦNkover all divisors of Nis given by N, since dNΦd=dNΦNd. Hence, all the Nfrequency indices k=0N1have been mapped.

Thus, all the frequency indices of 1-D MRT can be classified on the basis of their gcdw.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 kand k'connected through complete redundancy.

Proof.For two MRT coefficients having frequencies kand 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 0M1. 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 0M1by hand then computing modulo w.r.t. Mproduces 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 kand k'connected through complete redundancy.

To look at an example, when N=8,


Since k=1and k=3are 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=hpNwould result inp'=0,3,6,1, which reduces to p'=0,3,2,1after the condition hpN<Mis checked and relevant sign change. Hence, p=0,1,2,3maps to p'=0,3,2,1.

3.4 Derived redundancy

For N=6,


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'pand Ykpabe the two MRT coefficients. The congruence relations for Ykpaare nkN=paandnkN=pa+M. The congruence relations for Yk'pare nkN=pand nkN=p+M. Assume that a relation k'=dkexists between kand k'. Hence, dnkN=pand dnkN=p+M.dnkN=pmay be written as nkN=pdif gdN=d, and dp. In other words, dshould be a divisor of N. From nkN=pdand nkN=pa,pa=pd. Multiplying both sides of nkN=pa+M by d,dnkN=dpa+dM. If dis odd, this can be written as dnkN=dpa+M, which becomes nkN=p+M. Hence, provided there exists an odd-valued divisor dof N, such that k'=dk, then there is derived redundancy between and Yk'pand Ykpa. Hence, we can conclude that there cannot be derived redundancy when Nis a power of 2 since Nhas no divisors that are odd. For even Nnot a power of 2, derived redundancy exists since Nthen has divisors that are odd. Details of derived redundancies are shown in Tables 1 and 2 for N=6and N=24, respectively.

N = 6Complete redundancy (5)Derived redundancy (3)

Table 1.

Complete redundancy and derived redundancy relations for N = 6.

N = 24Co-primesOdd divisors

Table 2.

Complete redundancy and derived redundancy relations for N = 24.


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 dan 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 kand odd-valued dexcept d=1,k'dk. So, the unique divisor set for Ncontains 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 MNMRT coefficients given a signal of size N. Now arises the question of the exact number of UMRT coefficients.

If Nis a power of 2, the frequencies that form unique coefficients are themselves powers of 2. Since, k=0=NNand Na power of 2, then k=0produces 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 kis given by the number of allowable phase indices for each frequency index k. For an MRT coefficient Ykpto exist, pshould be divisible by k. When k=N, this condition has only one solution for p,p=0. All other frequency indices have Mkcoefficients each. Hence, the total number of UMRT coefficients is given by


Hence, the number of UMRT coefficients, when Nis a power of 2, is N.

If Nis not a power of 2, k=0does not produce UMRT coefficients. Let k'be the highest power of 2 frequency and a divisor of N. Hence N=dk',dbeing an odd integer; if dhas an even value, then it would violate the assumption that k'is the highest power of 2 frequency and a divisor of N. Since dhas an odd value, it is not possible for k'to be a divisor for Mas d2cannot 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 Nand are smaller than k'will be divisors of M. These are k=1,2,4,,k'2. There are MkMRT coefficients produced by these frequencies. When Nis not a power of 2, frequency k=0can be obtained by derived redundancy. A frequency k=0 is equivalent to k=N, since NN=0. Frequency Nrelates to k'through N=dk',dbeing odd. This can be recalled to be sufficient for derived redundancy to occur. Thus, in case if Nis not a power of 2, k=0does not form an absolutely unique MRT coefficient. Hence, the total number of UMRT coefficients is


We thus conclude that NUMRT coefficients are needed to represent a 1-D signal of length N, whether Nis a power of 2 or not, and these coefficients are produced by frequencies that are divisors of Nand powers of 2, beginning with k=1.

The 1-D UMRT coefficients can be computed as below:

(i) Na power of 2


(ii) Nnot a power of 2


where k'is the highest frequency index that is a power of 2 and also a divisor of N.


5. Inverse MRT

5.1 Theorem 7: N a power of 2

Given the UMRT of a 1-D signal of size N, Nbeing a power of 2, the 1-D signal can be reconstructed from its UMRT by the following formula


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 pof the UMRT coefficient Ykpthat contains xnis given by nk nkN=p. Thus for a frequency that is a power of 2, k=2a, the UMRT coefficient that contains xnis Y2a2anN. The UMRT coefficient Y00contains all the elements of the data including xnsince nkN=0,n, when k=0. In Eq. (53), Y00has a factor of multiplication 1N, and the remaining UMRT coefficients have a factor of multiplication 12t+1. Consequently, the xnthat is a part of these coefficients have the corresponding factors of multiplication. The resultant multiplication factor ffor xndue to the summation is obtained as a sum of the individual factors of multiplication.


Hence, as a result of the summation, one of the components of the result is the data xn.

A UMRT coefficient Y2a2anNcontains other terms besides xn. For the inverse transform formula to be correct, these other terms that occur in the various UMRT coefficients Y2a2anNneed to get canceled off. It can be proved that they vanish. Let kbe the smallest frequency at which any other data elements co-occur with xn. Y00can be excluded as all data elements co-occur in it with a positive sign. Leaving out Y00, another element shows co-occurrence with xnfor the first time for k=1. For example, for N=8,Y10=x0x4. Hence, if x0is the element to be obtained, it is seen that x4occurs with an opposite sign along with x0in the MRT coefficient corresponding to k=1, given byY10. From Eq. (12), when k=1,gkN=1and 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, xnand 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+Moccurswith positive signsince Y2p=xnxn+N4+xn+N2xn+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 xnco-occur in Ykpbut having different signs, then,


where qoddisan odd integer. At the next higher frequency k'=2k, Eq. (54) becomes


From (12), the general form for a data element xn'of same sign present along with an element xnin the MRT coefficient Yk'pis given by (since k'is a divisor of N,gk'N=k')


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 kis the lowest frequency at which xn'and xnoccur with opposite signs, for all larger frequencies k'=2k,xn'and xnoccur with similar signs. For N=8,Y10=x0x4,Y20=x0x2+x4x6and Y40=x0x1+x2x3+x4x5+x6x7. Data elements x4and x0occur with opposite signs in Y10and similar signs in higher frequencies, k=2,k=4. Conversely, another conclusion is that elements xn'and xnthat co-occur with same signs in a UMRT coefficient having frequency k'also co-occur with opposite signs in a UMRT coefficient having frequency kwhere k'=2k.

Given kis the lowest frequency where xn'and xnco-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


will provide the value of the multiplication factor fassociated with element xn'.

Assume k=Nq. First the sum of the following series can be found:


The number of terms in this summation is log2q1.


From Eq. (57),


Thus, all the other data elements xn'that occur along with xnin 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, Nnot being a power of 2, the 1-D signal can be reconstructed from its UMRT by the following formula


where k'is the highest frequency index that is a power of 2 and also a divisor of N.

Proof.xnhas to be obtained from the UMRT. Given Ykpdata element xnhas to satisfy nkN=p. For k=2a, the UMRT coefficient Y2a2anNcontains xn. The UMRT coefficient Yk'nk'Nis multiplied by 1k', and the other UMRT coefficients are multiplied by 12t+1. The resultant factor fthat multiplies xnas 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 xncancel 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,Nbeing any even number.


where k'is the highest power of 2 divisor of N.

For Na power of 2, the UMRT basis matrix can be defined in a new form by combining the frequency index kand the phase index pof an MRT coefficient into an index qas follows:


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.


Table 3.

Proposed mapping between 1-D UMRT indices and array indices, for N = 8.


6. Conclusions and future development

The MRT is a new representation of signals and involves only real additions. However, the MRT is expansive and redundant. The UMRT removes these features of MRT to give a real, invertible, nonexpansive signal transform for any even values of N. The MRT belongs in the same family of transforms as the Haar transform and the Hadamard transform. A number-theoretical foundation has hereby been laid for the 1-D MRT. However, the 2-D version of the MRT also exists. The interconnections between the 1-D version and 2-D version need to be studied further. The real merit of this transform is its utmost simplicity in terms of computational requirements. Simple integer-to-integer transforms will retain their attractiveness in the light of the ongoing switch to Internet of Things (IoT) and edge computing. A potential application of the MRT is its use as a feature vector in various contexts, just like how the Hadamard Transform has been used, as shown in [18, 19, 20]. Numerous other applications await the MRT.



The author would like to acknowledge the guidance and contributions of Dr. R. Gopikakumari.


  1. 1. Ahmed N et al. Discrete cosine transform. IEEE Transactions on Computers. 1974;C-23:90-93. DOI: 10.1109/T-C.1974.223784
  2. 2. Bracewell RN. Discrete Hartley transform. Journal of the Optical Society of America. 1983;73:1832-1835. DOI: 10.1364/JOSA.73.001832
  3. 3. Ersoy OK. A two-stage representation of DFT and its applications. IEEE Transactions on Acoustics, Speech, and Signal Processing. 1987;35:825-831. DOI: 10.1109/TASSP.1987.1165202
  4. 4. Roy RC, Gopikakumari R. A new transform for 2-d signal representation (MRT) and some of its properties. In: Proceedings of the International Conference in Signal Processing and Communication (SPCOM ‘04). Bangalore: IEEE; 2004. pp. 363-367. DOI: 10.1109/SPCOM.2004.1458423
  5. 5. Lun DPK, Hsung TC, Shen TW. Orthogonal discrete periodic Radon transform. Part I: Theory and realization. Signal Processing. 2003;83:941-955. DOI: 10.1016/S0165-1684(02)00498-X
  6. 6. Roy RC, Anish Kumar MS, Gopikakumari R. An invertible transform for image representation and its application to image compression. In: Proceedings of the International Symposium in Signal Processing (ISSPA ‘07). Sharjah: IEEE; 2007. DOI: 10.1109/ISSPA.2007.4555504
  7. 7. Anish Kumar MS, Roy RC, Gopikakumari R. A new transform coder for gray scale images using 4×4 MRT. Elsevier AEU—International Journal of Electronics and Communications. 2008;62–8:627-630. DOI: 10.1016/j.aeue.2007.04.009
  8. 8. Roy RC, Gopikakumari R. 1-D MRT: A new transform for 1-D signals. In: Proceedings of the all India Seminar on Innovative Electronics Technology and Futuristic Communication, Kochi. 2009. pp. 85-88
  9. 9. Fino J. Relations between Haar and Walsh/Hadamard transforms. Proceedings of the IEEE. 1972;60:647-648. DOI: 10.1109/PROC.1972.8719
  10. 10. Roy RC. Relationship between the Haar transform and the MRT. In: Proceedings of the Eighth International Conference on Information Communication and Signal Processing (ICICS ‘11), December 2011. Singapore: IEEE; 2011. DOI: 10.1109/ICICS.2011.6173127
  11. 11. Roy RC. The relationship between the Hadamard transform and the MRT. In: Proceedings of the National Conference on Power Instrumentation Control and Computing (PICC ‘10), Thrissur. 2010
  12. 12. Pei S, Chang K. Integer 2-D discrete Fourier transform pairs and eigenvectors using Ramanujan’s sum. IEEE Signal Processing Letters. 2016;23–1:70-74. DOI: 10.1109/LSP.2015.2501421
  13. 13. Qiu Q, Thompson A, Calderbank R, Sapiro G. Data representation using the Weyl transform. IEEE Transactions on Signal Processing. 2016;64(7):1844-1853. DOI: 10.1109/TSP.2015.2505661
  14. 14. Kamisli F. Lossless image and intra-frame compression with integer-to-integer DST. IEEE Transactions on Circuits and Systems for Video Technology. 2019;29(2):502-516. DOI: 10.1109/TCSVT.2017.2787638
  15. 15. Roy RC. Development of a new transform: MRT [thesis]. Cochin University of Science and Technology; 2010
  16. 16. Dence JB, Dence TP. Elements of the Theory of Numbers. USA: Academic Press; 1999
  17. 17. Apostol TM. Introduction to Analytic Number Theory. USA: Springer; 1976
  18. 18. Lakshmi PG, Dominic S. Walsh–Hadamard transform kernel-based feature vector for shot boundary detection. IEEE Transactions on Image Processing. 2014;23(12):5187-5197. DOI: 10.1109/TIP.2014.2362652
  19. 19. Tang M, Chen X, Wen J, Han Y. Hadamard transform-based optimized HEVC video coding. IEEE Transactions on Circuits and Systems for Video Technology. 2019;29(3):827-839. DOI: 10.1109/TCSVT.2018.2810324
  20. 20. Rout DK, Subudhi BN, Veerakumar T, Chaudhury S. Walsh–Hadamard-kernel-based features in particle filter framework for underwater object tracking. IEEE Transactions on Industrial Informatics. 2020;16(9):5712-5722. DOI: 10.1109/TII.2019.2937902

Written By

Rajesh Cherian Roy

Submitted: February 12th, 2020 Reviewed: July 10th, 2020 Published: September 21st, 2020