Open access peer-reviewed chapter

A New Integer-to-Integer Transform

By Rajesh Cherian Roy

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

DOI: 10.5772/intechopen.93356

Downloaded: 62

Abstract

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.

Keywords

  • 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

Ykp=nnkN=pxnnnkN=p+Mxnk=0,1,2N1,p=0,1,2M1,andM=N2E1

In Eq. (1), kcan be considered analogous to the frequency in DFT, and psignifies the phase. Thus, 1-D MRT produces M arrays 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

Ykp=n=0N1Ak,p,nxn,0kN1,0pM1E2
1ifnkN=pAk,p,n=1ifnkN=p+M0otherwiseE3

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

Yk0=44167761416776Yk1=053047053047Yk2=01548150154815Yk3=047053047053

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=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. p is 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

Ykp=Ykp+M

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

nakN=pE6

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

na'kN=p+ME7

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

nbkN=p+ME8

The elements nb'that are in the negative group of the MRT coefficient Ykp+Mbe 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=nanbnb'na'na'nb'Ykp+MYkp=Ykp+M

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,

n0+jgk,j=0gkN1E12

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 k and 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 c that 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,

p2'=p1+qk

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

p2p1=qkM

Since kN, there is an integer t satisfying N=tk. Hence, Mk=t2. Since kdoes not divide M, t2is 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, khas to be even. Since kNand kis even, it follows that k2M.

Hence,

M=dk2,dbeing an integer
p2p1=qkdk2
=2qk2dk2
=2qdk2

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,

p2p1=k2E13

The next valid phase after p1is

p3=p1+kE14

From Eqs. (13) and (14),

p3p2=k2

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

p4'=p2'+kE15

p4'has a corresponding nonvalid allowable phase p4given by

p4=p4'ME16

From Eqs. (15) and (16),

p4=p2+kp4p3=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+Mk2E17

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:

0,k2,k,3k2,,Mk2E18

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

0,k,2k,,Mk2E19

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

k2,3k2,5k2,.,MkE20

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 k does 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.

Proof.

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

nkN=p.

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,

n+MkkN=nkN+MkkN=p+M

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

0,k2,k,3k2,.,Mk2

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

0,k,2k,,Mk2

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

k2,3k2,5k2,.,Mk

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:

Ykp=xna+xna+gk+xna+2gk+xna+3gk+..+xna+gkN1gkxnb+xnb+gk+xnb+2gk+xnb+3gk++xnb+gkN1gk

This can be written as

Ykp=j=0gkN1xna+jgkxnb+jgkE21

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,

Ykp=xpk+xpk+Nk+xpk+2Nk+xpk+3Nk+..+xpk+k1Nkxpk+N2k+xpk+3N2k+xpk+5N2k+xpk+7N2k+..+xpk+2k1N2kE22

On further simplification,

Ykp=j=0k1xjN+pkx2j+1N+2p2k
p=0,k,2k,,MkE23

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:

Ykp=xpk+xpk+Nk+xpk+2Nk+xpk+3Nk+..+xpk+k1Nk

which, when simplified, becomes

Ykp=j=0k1xjN+pkp=0,k,2k,,Mk2E24

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

Ykp=xp+Mk+xp+Mk+Nk+xp+Mk+2Nk+..+xpk+k1Nk

which, when simplified, becomes

Ykp=j=0k1xjN+p+Mkp=k2,3k2,,MkE25

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

Ykp=xnaxnbp=0,1,2,3,M1E26

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

Yk=Yk0W80+Yk1W81+Yk2W82+Yk2W83

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

YhkNhpN=YkpforhpN<M,and,YhkNhpNM=YkpforhpNM

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

qN=dE27

and his a multiplication factor, then

hqNghN=hdE28

If ghN=1, Eq. (28) becomes

hqN=hdE29

Given Ykp, and a set of indices nthat satisfies

nkN=pE30

and a set of indices n′ that satisfies

n'kN=p+ME31

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

nhkN=hpE32

and

n'hkN=hp+ME33
n'hkN=hp+hME34

Since ghN=1,his odd, and hence

hp+hMhp+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 nand n'form the MRT coefficient YhkNhpN. Using Eqs. (30)(32) and (36),

YhkNhpN=YkpE37

If hpNM, then

YhkNhpNM=YkpE38

since

Ykp=YkpM=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=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 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 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.

gk1N=kE39
gk2N=kE40

Assume hexists such that

ghN=1E41

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

ghk1N=kE42
hk1N=hk1Nqif0hk1Nq<N,qZE43

Using Eq. (43) and gcdproperty,

ghk1NN=ghk1NqN=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 k1and k2are 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,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,

hkN=h+NkkNE46

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],

dVNΦd=N,ifN1,E47

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. 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 kand k'connected through complete redundancy.

To look at an example, when N=8,

Y10=Y30,Y11=Y33Y12=Y32,and,Y13=Y31.

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,

Y30=Y10Y11+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'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 d is 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)
153
246
3
6

Table 1.

Complete redundancy and derived redundancy relations for N = 6.

N = 24Co-primesOdd divisors
5711131719233
15711131719233
21014226
315219
42012
618
81624
12
24

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 MN MRT 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

Tot=1+t=0log2MM2t=1+Mt=0log2M12t=1+M112log2M+112=1+N12log2M+1=1+N11N=N

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

Tot=1+t=0log2MM2t=1+M112log2M+112=Nk'+N122k'=N

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

Y00=n=0N1xnE48
Ykp=j=0k1xjN+pkx2j+1N+2p2kk=2t,0tlog2M,p=tk,0tMk1E49

(ii) Nnot a power of 2

Ykp=j=0k1xjN+pkx2j+1N+2p2kk=2t,0tlog2M,p=tk,0tMk1E50
Yk'p=j=0k'1xjN+pkp=tk',0tMk'12E51
Yk'p=j=0k'1xjN+p+Mk'p=tk'+k'2,0tMk'32E52

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

xn=1NY00+t=0log2M12t+1Y2t2tnN,0nN1E53

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.

f=1N+t=0log2M12t+1=1N+t=0log2M2t+1=1N+1212log2M+112=1N+11N=1

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,

n'=n+qoddN2kE54

where qoddisan 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 xnin the MRT coefficient Yk'pis 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 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

f=1N12k+14k+18k+12ME57

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:

14k+18k+12M=fafa=j=log22Nqlog2M12j+1

The number of terms in this summation is log2q1.

fa=q4N12log2q112=q2Nq2q=q22N

From Eq. (57),

f=1N12k+fa=1N12k+q22N=q2N12k=0

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, 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.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 f that 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.

xn=1k'Yk'Nnk'N+t=0log2k'112t+1Y2t2tnNE59

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 k and the phase index pof an MRT coefficient into an index qas follows:

H0m=H0,0m=11,nkN=p
Hqm=Hk,pm={1,nkN=p+N20,otherwiseq=2k+p1m=0,1,,N1

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,p0,01,01,11,21,32,02,24,0
q01234567

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.

Acknowledgments

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

© 2020 The Author(s). Licensee IntechOpen. This chapter is distributed under the terms of the Creative Commons Attribution 3.0 License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

How to cite and reference

Link to this chapter Copy to clipboard

Cite this chapter Copy to clipboard

Rajesh Cherian Roy (September 21st 2020). A New Integer-to-Integer Transform, Number Theory and Its Applications, Cheon Seoung Ryoo, IntechOpen, DOI: 10.5772/intechopen.93356. Available from:

chapter statistics

62total chapter downloads

More statistics for editors and authors

Login to your personal dashboard for more detailed statistics on your publications.

Access personal reporting

Related Content

This Book

Next chapter

Digit Sums and Infinite Products

By Samin Riasat

Related Book

First chapter

Cyclotomic and Littlewood Polynomials Associated to Algebras

By José-Antonio de la Peña

We are IntechOpen, the world's leading publisher of Open Access books. Built by scientists, for scientists. Our readership spans scientists, professors, researchers, librarians, and students, as well as business professionals. We share our knowledge and peer-reveiwed research papers with libraries, scientific and engineering societies, and also work with corporate R&D departments and government entities.

More About Us