Complete redundancy and derived redundancy relations for N = 6.

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

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

In Eq. (1), * M* arrays each of size

Thus, the kernel

Let

Then,

### 2.2 Composition of MRT coefficients

One set of elements that combine to form an MRT coefficient contains those elements satisfying the congruence

The group of data elements whose indices satisfy the congruence relation

An MRT coefficient has two indices, frequency and phase. By formal definition of the MRT, phase has values in the range * p* is referred to as a valid phase for a given value of

### 2.3 Theorem 1: periodicity

** Proof**. The elements

The elements

The elements

The elements

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

Condition 1:

Condition 2:

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

A linear congruence,

The indices of the elements in the positive (or negative) set of an MRT coefficient form an arithmetic progression,

where

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

If * k* and

When

When * c* that satisfies

The gap between two successive valid phases is

Since * t* satisfying

*has to be odd. We know*t

Hence,

The value of

The distance between

The next valid phase after

Let

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

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

b. For

c. The first element in the positive set of an MRT coefficient * k* does not divide

*, has the index*M

a. The first element in MRT coefficient

Solutions exist for Eq. (4) only if

Since

The condition

b. Given

Hence, if index

c. From (18), when

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

Also, the allowable phase indices that produce MRT coefficients having only negative sets are actually nonvalid allowable phase indices. If

If

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

This can be written as

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

When

When

On further simplification,

When

which, when simplified, becomes

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

which, when simplified, becomes

When * N* are co-prime,

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

## 3. Redundancy in MRT

For some values of

### 3.1 Theorem 4: complete redundancy

Given

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

and

If

Given

and a set of indices

If there is

and

Since

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

If

since

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*. As an example, for

If

When * k′* that are co-prime to

*can be obtained from MRT coefficients with a frequency of*N

Let k′ satisfy

### 3.2 Theorem 5: redundancy frequency groups

MRT coefficients with frequency indices that have common

** Proof.** Assume

Assume

From Eq. (41),

Using Eq. (43) and

From Eqs. (41) and (45), and using Theorem 4, it can be concluded that frequency indices

For example, if

Since * N*, there is redundancy among the MRT coefficients of these frequencies. Similarly, since

Theorem 5 shows that we can group frequencies based on their * N*.; and each group corresponds to a some divisor of

*. There are*N

Eq. (46) implies that the set of

From number theory [17],

From Eq. (47), the sum of the terms

Thus, all the frequency indices of 1-D MRT can be classified on the basis of their

### 3.3 Theorem 6: Mapping between phase indices

One-to-one mapping exists between phases of 1-D MRT coefficients having frequencies

** Proof.** For two MRT coefficients having frequencies

*connected by complete redundancy, the number of phases corresponding to each frequency is equal since*k′

*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*M

To look at an example, when

Since

### 3.4 Derived redundancy

For

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 * d* is odd, this can be written as

1 | 5 | 3 |

2 | 4 | 6 |

3 | ||

6 |

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 |

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

### 4.1 Number of unique coefficients

In total, there are * MN* MRT coefficients given a signal of size

*. Now arises the question of the exact number of UMRT coefficients.*N

If

Hence, the number of UMRT coefficients, when

If * N*. Since

We thus conclude that

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

(i)

(ii)

where

## 5. Inverse MRT

### 5.1 Theorem 7: N a power of 2

Given the UMRT of a 1-D signal of size

** Proof.** The data element that needs to be recovered from the UMRT is given by

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

A UMRT coefficient

where

From (12), the general form for a data element

where

Equation (55) can be seen to be a special case of Eq. (56). For any higher frequency

Given

will provide the value of the multiplication factor

Assume

The number of terms in this summation is

From Eq. (57),

Thus, all the other data elements

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

*not being a power of 2, the 1-D signal can be reconstructed from its UMRT by the following formula*N

where

* f* that multiplies

### 5.3 General formula for any even N

Equation (58) can be generalized to be applicable to any even value of

where

For * k* and the phase index

This structure of the UMRT definition has a similar form as that of the Haar transforms [10]. Table 3 shows the mapping for

, | 0,0 | 1,0 | 1,1 | 1,2 | 1,3 | 2,0 | 2,2 | 4,0 |

0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |

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

## Acknowledgments

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

## References

- 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.
Bracewell RN. Discrete Hartley transform. Journal of the Optical Society of America. 1983; 73 :1832-1835. DOI: 10.1364/JOSA.73.001832 - 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.
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.
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.
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.
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.
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.
Fino J. Relations between Haar and Walsh/Hadamard transforms. Proceedings of the IEEE. 1972; 60 :647-648. DOI: 10.1109/PROC.1972.8719 - 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.
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.
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.
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.
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.
Roy RC. Development of a new transform: MRT [thesis]. Cochin University of Science and Technology; 2010 - 16.
Dence JB, Dence TP. Elements of the Theory of Numbers. USA: Academic Press; 1999 - 17.
Apostol TM. Introduction to Analytic Number Theory. USA: Springer; 1976 - 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.
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.
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