Open access peer-reviewed chapter

# A New Integer-to-Integer Transform

Written By

Rajesh Cherian Roy

Submitted: 30 June 2020 Reviewed: 10 July 2020 Published: 21 September 2020

DOI: 10.5772/intechopen.93356

From the Edited Volume

## Number Theory and Its Applications

Edited by Cheon Seoung Ryoo

Chapter metrics overview

View Full Metrics

## 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 0 as 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 0 in 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 0 only. 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 Ykp of a 1-D sequence xn,0nN1 is defined [7] as

Ykp=nnkN=pxnnnkN=p+Mxnk=0,1,2N1,p=0,1,2M1,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=0N1Ak,p,nxn,0kN1,0pM1E2
1ifnkN=pAk,p,n=1ifnkN=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=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=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 0M1. Although by definition, p0M1, number theory allows p0N1. p is referred to as a valid phase for a given value of k if kp. For example, for N=6, if k=2, then p=0,2,4 satisfy kp, 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=nanbnb'na'na'nb'Ykp+MYkp=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: 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 Ykp exists given N if congruences (4) and/or (5) have solutions. The necessary and sufficient condition for (4) to have solutions is that gkNp. Similarly, gkNp+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 0N1, 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,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 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 p0M1. When k divides N, gkN=k. The condition according to Eq. (4) now becomes kp. There are Nk such values of p in 0N1. These are p=0,k,2k,,Nk. The condition corresponding to Eq. (5) is now kp+M. When kp, the condition kp+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,,Nk. There are Nk such phases. When kM 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,,Mk. 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,,Nk. 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 pM. However, the relation Ykp=YkpM is still satisfied. Thus, for p>M, there is an allowable but nonvalid phase pM. We can use the relation Ykp=YkpM 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 pM. 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 pM 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

p2p1=qkM

Since kN, 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 kN and k is even, it follows that k2M.

Hence,

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

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

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

p2p1=k2E13

The next valid phase after p1 is

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 p4 given 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 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 kN, the condition for existence for solutions is kp. 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 Nk2. 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 Mk. There are N2k12 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,,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 na of the first element in the positive data group of an MRT coefficient Ykp is na=pk.

b. For kM, 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 kp.

Since kp, 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,.,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=p is pk since kp 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 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 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+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 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 kM. 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 kM,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+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 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+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 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=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 Yk can 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 h such that ghN=1

YhkNhpN=YkpforhpN<M,and,YhkNhpNM=YkpforhpNM

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+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 n and 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=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 kk' 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 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 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=hk1Nqif0hk1Nq<N,qZE43

Using Eq. (43) and gcd property,

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 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 ΦN1 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 0Nk1, 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,ifN1,E47

From Eq. (47), the sum of the terms ΦNk over all divisors of N is given by N, since dNΦd=dNΦNd. Hence, all the N frequency indices k=0N1 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 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 0M1 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=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'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 nkN=p and nkN=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 dp. 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 nkN=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.

## 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+Mt=0log2M12t=1+M112log2M+112=1+N12log2M+1=1+N11N=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+M112log2M+112=Nk'+N122k'=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=0N1xnE48
Ykp=j=0k1xjN+pkx2j+1N+2p2kk=2t,0tlog2M,p=tk,0tMk1E49

(ii) N not 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, 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,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 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=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 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=x0x4. 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=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 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=x0x4,Y20=x0x2+x4x6 and Y40=x0x1+x2x3+x4x5+x6x7. 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=1N12k+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 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 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+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,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.

## 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.

## References

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: 30 June 2020 Reviewed: 10 July 2020 Published: 21 September 2020