A New Integer-to-Integer Transform

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.

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 ${\mathit{Y}}_{\mathit{k}}^{\left(\mathit{p}\right)}$ of a 1-$\mathit{D}$ sequence ${\mathit{x}}_{\mathit{n}},0\le \mathit{n}\le \mathit{N}-1$ is defined [7] as

$$\begin{array}{l}{\mathit{Y}}_{\mathit{k}}^{\left(\mathit{p}\right)}=\sum _{\forall \mathit{n}\Rightarrow {\left(\left(\mathit{nk}\right)\right)}_{\mathit{N}}=\mathit{p}}{\mathit{x}}_{\mathit{n}}-\sum _{\forall \mathit{n}\Rightarrow {\left(\left(\mathit{nk}\right)\right)}_{\mathit{N}}=\mathit{p}+\mathit{M}}{\mathit{x}}_{\mathit{n}}\\ \mathit{k}=\mathrm{0,1,2}\dots \mathit{N}-1,\mathit{p}=\mathrm{0,1,2}\dots \mathit{M}-1,\text{and}\mathit{M}=\frac{\mathit{N}}{2}\end{array}$$E1

In Eq. (1), $\mathit{k}$ can be considered analogous to the frequency in DFT, and $\mathit{p}$ signifies the phase. Thus, 1-D MRT produces M arrays each of size $\mathit{N}$, given a signal of size $\mathit{N}$. Hence, $\mathit{MN}$ coefficients have to be computed using only real additions. Another expression for the 1-D MRT [7] is

$${\mathit{Y}}_{\mathit{k}}^{\left(\mathit{p}\right)}=\sum _{\mathit{n}=0}^{\mathit{N}-1}{\mathit{A}}_{\mathit{k},\mathit{p},\mathit{n}}{\mathit{x}}_{\mathit{n}},0\le \mathit{k}\le \mathit{N}-1,0\le \mathit{p}\le \mathit{M}-1$$E2

$$\begin{array}{c}1\mathit{\text{if}}{〚\mathit{nk}〛}_{\mathit{N}}=\mathit{p}\\ {\mathit{A}}_{\mathit{k},\mathit{p},\mathit{n}}=-1\mathit{\text{if}}\parallel \mathit{nk}{\parallel }_{\mathit{N}}=\mathit{p}+\mathit{M}\\ 0\mathit{\text{otherwise}}\end{array}$$E3

Thus, the kernel ${\mathit{A}}_{\mathit{k},\mathit{p},\mathit{n}}$ maps the data ${\mathit{x}}_{\mathit{n}}$ into the 1-D MRT ${\mathit{Y}}_{\mathit{k}}^{\left(\mathit{p}\right)}$. For example,

Let $\mathit{x}=\left[952361498976462\right]$, $\mathit{N}=8$.

Then, ${\mathit{Y}}_{\mathit{k}}^{\left(\mathit{p}\right)}$, the corresponding MRT of $\mathit{x}$, is

$$\begin{array}{l}{\mathit{Y}}_{\mathit{k}}^{\left(0\right)}=\left[44167761416776\right]\\ {\mathit{Y}}_{\mathit{k}}^{\left(1\right)}=\left[0-530470530-47\right]\\ {\mathit{Y}}_{\mathit{k}}^{\left(2\right)}=\left[01548-15015-48-15\right]\\ {\mathit{Y}}_{\mathit{k}}^{\left(3\right)}=\left[0470-530-47053\right]\end{array}$$

2.2 Composition of MRT coefficients

One set of elements that combine to form an MRT coefficient contains those elements satisfying the congruence ${\left(\mathit{nk}\right)}_{\mathit{N}}=\mathit{p}$, and another set contains those satisfying the congruence ${\left(\left(\mathit{nk}\right)\right)}_{\mathit{N}}=\mathit{p}+\mathit{M}$. Thus, the two relevant congruences are:

$${\left(\left(\mathit{nk}\right)\right)}_{\mathit{N}}=\mathit{p}$$E4

$${\left(\left(\mathit{nk}\right)\right)}_{\mathit{N}}=\mathit{p}+\mathit{M}$$E5

The group of data elements whose indices satisfy the congruence relation ${\left(\left(\mathit{nk}\right)\right)}_{\mathit{N}}=\mathit{p}$ is defined as the positive data group or positive set of the 1-D MRT coefficient ${\mathit{Y}}_{\mathit{k}}^{\left(\mathit{p}\right)}$ The group of data elements whose indices satisfy the congruence relation ${\left(\left(\mathit{nk}\right)\right)}_{\mathit{N}}=\mathit{p}+\mathit{M}$ is defined as the negative data group or negative set of the 1-D MRT coefficient ${\mathit{Y}}_{\mathit{k}}^{\left(\mathit{p}\right)}$. For example, the data elements ${\mathit{x}}_0,{\mathit{x}}_2,{\mathit{x}}_4,{\mathit{x}}_6$ form the positive set of the MRT coefficient ${\mathit{Y}}_4^{\left(0\right)}$ and data elements ${\mathit{x}}_1,{\mathit{x}}_3,{\mathit{x}}_5,{\mathit{x}}_7$ form the negative set of the MRT coefficient ${\mathit{Y}}_4^{\left(0\right)}$.

An MRT coefficient has two indices, frequency and phase. By formal definition of the MRT, phase has values in the range $\left[0,\mathit{M}-1\right]$. Although by definition, $\mathit{p}\in \left[0,\mathit{M}-1\right]$, number theory allows $\mathit{p}\in \left[0,\mathit{N}-1\right]$. p is referred to as a valid phase for a given value of $\mathit{k}$ if $\mathit{k}\mid \mathit{p}$. For example, for $\mathit{N}=6$, if $\mathit{k}=2$, then $\mathit{p}=\mathrm{0,2,4}$ satisfy $\mathit{k}\mid \mathit{p}$, and hence, these are valid phases for this value of $\mathit{k}$. A phase $\mathit{p}$ is defined to be an allowable phase index if $\mathit{p}<\mathit{M}$.

2.3 Theorem 1: periodicity

$${\mathit{Y}}_{\mathit{k}}^{\left(\mathit{p}\right)}=-{\mathit{Y}}_{\mathit{k}}^{\left(\mathit{p}+\mathit{M}\right)}$$

Proof. The elements ${\mathit{n}}_{\mathit{a}}$ that are in the positive group of the MRT coefficient ${\mathit{Y}}_{\mathit{k}}^{\left(\mathit{p}\right)}$ can be found as the solutions of

$${\left(\left({\mathit{n}}_{\mathit{a}}\mathit{k}\right)\right)}_{\mathit{N}}=\mathit{p}$$E6

The elements ${\mathit{n}}_{\mathit{a}}^{\text{'}}$ that are in the negative group of the MRT coefficient ${\mathit{Y}}_{\mathit{k}}^{\left(\mathit{p}\right)}$ can be found as the solutions of

$${\left(\left({\mathit{n}}_{\mathit{a}}^{\text{'}}\mathit{k}\right)\right)}_{\mathit{N}}=\mathit{p}+\mathit{M}$$E7

The elements ${\mathit{n}}_{\mathit{b}}$ that are in the positive group of the MRT coefficient ${\mathit{Y}}_{\mathit{k}}^{\left(\mathit{p}+\mathit{M}\right)}$ can be found as the solutions of

$${\left(\left({\mathit{n}}_{\mathit{b}}\mathit{k}\right)\right)}_{\mathit{N}}=\mathit{p}+\mathit{M}$$E8

The elements ${\mathit{n}}_{\mathit{b}}^{\text{'}}$ that are in the negative group of the MRT coefficient ${\mathit{Y}}_{\mathit{k}}^{\left(\mathit{p}+\mathit{M}\right)}$ be found as the solutions of

$$\begin{array}{l}{\left(\left({\mathit{n}}_{\mathit{b}}^{\text{'}}\mathit{k}\right)\right)}_{\mathit{N}}=\mathit{p}+\mathit{M}+\mathit{M}=\mathit{p}+\mathit{N},\text{which}\mathit{can}\mathit{be}\text{written}\mathit{as}\\ {\left(\left({\mathit{n}}_{\mathit{b}}^{\text{'}}\mathit{k}\right)\right)}_{\mathit{N}}=\mathit{p}\end{array}$$E9

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

$${\mathit{n}}_{\mathit{a}}={\mathit{n}}_{\mathit{b}}^{\text{'}}$$E10

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

$${\mathit{n}}_{\mathit{a}}^{\text{'}}={\mathit{n}}_{\mathit{b}}$$E11

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

$$\begin{array}{l}{\mathit{Y}}_{\mathit{k}}^{\left(\mathit{p}\right)}=\sum {\mathit{n}}_{\mathit{a}}-\sum {\mathit{n}}_{\mathit{b}}\\ \sum {\mathit{n}}_{\mathit{b}}^{\text{'}}-\sum {\mathit{n}}_{\mathit{a}}^{\text{'}}\\ -\left(\sum {\mathit{n}}_{\mathit{a}}^{\text{'}}-\sum {\mathit{n}}_{\mathit{b}}^{\text{'}}\right)\\ -{\mathit{Y}}_{\mathit{k}}^{\left(\mathit{p}+\mathit{M}\right)}\\ \therefore {\mathit{Y}}_{\mathit{k}}^{\left(\mathit{p}\right)}=-{\mathit{Y}}_{\mathit{k}}^{\left(\mathit{p}+\mathit{M}\right)}\end{array}$$

2.4 Theorem 2: existence conditions

An MRT coefficient ${\mathit{Y}}_{\mathit{k}}^{\left(\mathit{p}\right)}$ exists for data of order $\mathit{N}$ if either of the following two conditions is satisfied:

Condition 1: $\mathit{g}\left(\mathit{k},\mathit{N}\right)\mid \mathit{p}$

Condition 2: $\mathit{g}\left(\mathit{k},\mathit{N}\right)\mid \mathit{p}+\mathit{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 ${\mathit{Y}}_{\mathit{k}}^{\left(\mathit{p}\right)}$ exists given $\mathit{N}$ if congruences (4) and/or (5) have solutions. The necessary and sufficient condition for (4) to have solutions is that $\mathit{g}\left(\mathit{k},\mathit{N}\right)\mid \mathit{p}$. Similarly, $\mathit{g}\left(\mathit{k},\mathit{N}\right)\mid \mathit{p}+\mathit{M}$ becomes the necessary and sufficient condition for (5) to have solutions.

A linear congruence, ${\left(\left(\mathit{nk}\right)\right)}_{\mathit{N}}=\mathit{p}$, if solvable, has $\mathit{g}\left(\mathit{k},\mathit{N}\right)$ solutions mod $\mathit{N}$. Hence, there exist $\mathit{g}\left(\mathit{k},\mathit{N}\right)$ solutions for $\mathit{n}$ in the range $\left[0,\mathit{N}-1\right]$, and thus, there exist $\mathit{g}\left(\mathit{k},\mathit{N}\right)$ elements in the positive set. Also, if there is a member ${\mathit{n}}_0$ of the positive set (particular solution), the other solutions are $\mathit{n}={\mathit{n}}_0+\frac{\mathit{N}}{\mathit{g}\left(\mathit{k},\mathit{N}\right)}\mathit{t},0\le \mathit{t}<\mathit{g}\left(\mathit{k},\mathit{N}\right)$. 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,

$${\mathit{n}}_0+{\mathit{jg}}_{\mathit{k}},\mathit{j}=\left[0,\mathit{g}\left(\mathit{k},\mathit{N}\right)-1\right]$$E12

where ${\mathit{n}}_0$ is the smallest member of the positive (or negative) set, and ${\mathit{g}}_{\mathit{k}}=\frac{\mathit{N}}{\mathit{g}\left(\mathit{k},\mathit{N}\right)}$.

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 $\mathit{k}$.

If k and $\mathit{N}$ are relatively prime, then $\mathit{g}\left(\mathit{k},\mathit{N}\right)=1$. When $\mathit{g}\left(\mathit{k},\mathit{N}\right)=1$, the MRT coefficients corresponding to $\mathit{k}$ are in existence for all values of $\mathit{p}\in \left[0,\mathit{M}-1\right]$. When $\mathit{k}$ divides $\mathit{N}, \mathit{g}\left(\mathit{k},\mathit{N}\right)=\mathit{k}$. The condition according to Eq. (4) now becomes $\mathit{k}\mid \mathit{p}$. There are $\frac{\mathit{N}}{\mathit{k}}$ such values of $\mathit{p}$ in $\left[0,\mathit{N}-1\right]$. These are $\mathit{p}=0,\mathit{k},2\mathit{k},\dots ,\mathit{N}-\mathit{k}$. The condition corresponding to Eq. (5) is now $\mathit{k}\mid \mathit{p}+\mathit{M}$. When $\mathit{k}\mid \mathit{p}$, the condition $\mathit{k}\mid \mathit{p}+\mathit{M}$ has solutions only if $\mathit{k}$ divides $\mathit{M}$. Thus, an MRT coefficient has both positive and negative sets only if $\mathit{k}$ divides $\mathit{M}$. Otherwise, only one among the positive or negative sets exists, for a given value of $\mathit{p}$.

When $\mathit{k}$ divides $\mathit{M}$, the valid phases for which MRT coefficients have positive sets are $\mathit{p}=0,\mathit{k},2\mathit{k},\dots ,\mathit{N}-\mathit{k}$. There are $\frac{\mathit{N}}{\mathit{k}}$ such phases. When $\mathit{k}\mid \mathit{M}$ is satisfied, negative sets also exist for all these MRT coefficients. There are thus $\frac{\mathit{M}}{\mathit{k}}$ allowable phases and hence $\frac{\mathit{M}}{\mathit{k}}$ MRT coefficients, the phases are $\mathit{p}=0,\mathit{k},2\mathit{k},\dots ,\mathit{M}-\mathit{k}$. These MRT coefficients have both positive and negative sets simultaneously.

When $\mathit{k}$ is not a divisor of $\mathit{M}$, for a valid phase, only one among the positive or negative sets exists. The valid phases are an arithmetic series $\mathit{p}=0,\mathit{k},2\mathit{k},\dots ,\mathit{N}-\mathit{k}$. In this case, there is no integer c that satisfies $\mathit{p}+\mathit{ck}=\mathit{p}+\mathit{M}$, and hence, ${\mathit{Y}}_{\mathit{k}}^{\left(\mathit{p}\right)}=-{\mathit{Y}}_{\mathit{k}}^{\left(\mathit{p}+\mathit{ck}\right)}$ cannot be true. Thus, for $\mathit{p}>\mathit{M}$, where $\mathit{p}$ is a valid phase, there is no valid phase index $\mathit{p}-\mathit{M}$. However, the relation ${\mathit{Y}}_{\mathit{k}}^{\left(\mathit{p}\right)}=-{\mathit{Y}}_{\mathit{k}}^{\left(\mathit{p}-\mathit{M}\right)}$ is still satisfied. Thus, for $\mathit{p}>\mathit{M}$, there is an allowable but nonvalid phase $\mathit{p}-\mathit{M}$. We can use the relation ${\mathit{Y}}_{\mathit{k}}^{\left(\mathit{p}\right)}=-{\mathit{Y}}_{\mathit{k}}^{\left(\mathit{p}-\mathit{M}\right)}$ to express the MRT corresponding to a valid phase index $\mathit{p}>\mathit{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 $\mathit{p}>\mathit{M}$ is the negative set of the MRT coefficient with allowable nonvalid phase $\mathit{p}-\mathit{M}$. Hence, a subset of the $\mathit{M}$ allowable phase indices are valid phases, while the other subset is made up of allowable nonvalid phases of the form $\mathit{p}-\mathit{M}$ that are obtained from valid phases $\mathit{p}>\mathit{M}$.

The gap between two successive valid phases is $\mathit{k}$. Let there be an allowable and numerically smallest valid phase ${\mathit{p}}_1<\mathit{M}$, and let the nearest allowable nonvalid phase be ${\mathit{p}}_2$. The valid phase corresponding to ${\mathit{p}}_2\text{is} {\mathit{p}}_2^{\text{'}}={\mathit{p}}_2+\mathit{M}$. Let $\mathit{q}$ be the smallest integer such that $\mathit{qk}>\mathit{M}$. Then,

$${\mathit{p}}_2^{\text{'}}={\mathit{p}}_1+\mathit{qk}$$

${\mathit{p}}_2$ is the closest allowable nonvalid phase to ${\mathit{p}}_1$. ${\mathit{p}}_1$ is the lowest allowable valid phase. There is no valid phase ${\mathit{p}}_1^{\text{'}}={\mathit{p}}_1+\mathit{M}$. The next valid phase is hence given by ${\mathit{p}}_2^{\text{'}}={\mathit{p}}_1+\mathit{qk}$, since $\mathit{q}$ is the smallest integer such that $\mathit{qk}>\mathit{M}$

$$\therefore {\mathit{p}}_2-{\mathit{p}}_1=\mathit{qk}-\mathit{M}$$

Since $\mathit{k}\mid \mathit{N}$, there is an integer t satisfying $\mathit{N}=\mathit{tk}$. Hence, $\frac{\mathit{M}}{\mathit{k}}=\frac{\mathit{t}}{2}$. Since $\mathit{k}$ does not divide $\mathit{M}$, $\frac{\mathit{t}}{2}$ is not an integer. For this to be true, t has to be odd. We know $\mathit{k}=\frac{\mathit{N}}{\mathit{t}}$. Since the division of any even number by an odd number produces an even number, $\mathit{k}$ has to be even. Since $\mathit{k}\mid \mathit{N}$ and $\mathit{k}$ is even, it follows that $\frac{\mathit{k}}{2}\mid \mathit{M}$.

Hence,

$$\mathit{M}=\frac{\mathit{dk}}{2},\mathit{d}\text{being an integer}$$

$${\mathit{p}}_2-{\mathit{p}}_1=\mathit{qk}-\frac{\mathit{dk}}{2}$$

$$=\frac{2\mathit{qk}}{2}-\frac{\mathit{dk}}{2}$$

$$=\left(2\mathit{q}-\mathit{d}\right)\frac{\mathit{k}}{2}$$

The value of $\left(2\mathit{q}-\mathit{d}\right)$ cannot be larger than 1, since, in that case,

$${\mathit{p}}_2-{\mathit{p}}_1\text{is greater than or equal to}\mathit{k}.$$

The distance between ${\mathit{p}}_2^{\text{'}}$ and $\mathit{M}$ has to be lesser than $\mathit{k}$. Thus, the distance between ${\mathit{p}}_1$ and ${\mathit{p}}_2$ has to be lesser than $\mathit{k}$. Hence,

$${\mathit{p}}_2-{\mathit{p}}_1=\frac{\mathit{k}}{2}$$E13

The next valid phase after ${\mathit{p}}_1$ is

$${\mathit{p}}_3={\mathit{p}}_1+\mathit{k}$$E14

From Eqs. (13) and (14),

$${\mathit{p}}_3-{\mathit{p}}_2=\frac{\mathit{k}}{2}$$

Let ${\mathit{p}}_4^{\text{'}}$ be the next valid phase index after ${\mathit{p}}_2^{\text{'}}$, then

$${\mathit{p}}_4^{\text{'}}={\mathit{p}}_2^{\text{'}}+\mathit{k}$$E15

${\mathit{p}}_4^{\text{'}}$ has a corresponding nonvalid allowable phase ${\mathit{p}}_4$ given by

$${\mathit{p}}_4={\mathit{p}}_4^{\text{'}}-\mathit{M}$$E16

From Eqs. (15) and (16),

$$\begin{array}{l}{\mathit{p}}_4={\mathit{p}}_2+\mathit{k}\\ \therefore {\mathit{p}}_4-{\mathit{p}}_3=\frac{\mathit{k}}{2}\end{array}$$

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:

$${\mathit{p}}_0,{\mathit{p}}_0+\frac{\mathit{k}}{2,}{\mathit{p}}_0+\mathit{k},{\mathit{p}}_0+3\frac{\mathit{k}}{2}\dots \dots \dots \dots \dots \dots ,{\mathit{p}}_0+\mathit{M}-\frac{\mathit{k}}{2}$$E17

When $\mathit{k}$ does not divide $\mathit{M}$, MRT coefficients exist for these allowable phase indices and they will have either a positive group or a negative group only. There are $\frac{\mathit{N}}{\mathit{k}}$ such allowable phases, and when $\mathit{k}$ does not divide $\mathit{M},\frac{\mathit{N}}{\mathit{k}}$ is odd. Since $\mathit{k}\mid \mathit{N}$, the condition for existence for solutions is $\mathit{k}\mid \mathit{p}$. The smallest value of $\mathit{p}$ that satisfies this condition is $\mathit{p}=0$. Hence, the first valid allowable phase is ${\mathit{p}}_0=0$. MRT coefficients having only a positive set have allowable phases that are even multiples of $\frac{\mathit{k}}{2}$, starting from $0$ and ending at $\frac{\mathit{N}-\mathit{k}}{2}$. There are $\frac{\mathit{N}}{2\mathit{k}}+\frac{1}{2}$ such MRT coefficients. Similarly, the MRT coefficients having only a negative set have allowable phases that are odd multiples of $\frac{\mathit{k}}{2}$, starting from $\frac{\mathit{k}}{2}$ and ending at $\mathit{M}-\mathit{k}$. There are $\frac{\mathit{N}}{2\mathit{k}}-\frac{1}{2}$ such MRT coefficients. The total number of 1-D MRT coefficients is thus $\frac{\mathit{N}}{\mathit{k}}$, and the sequence of allowable phases is:

$$0,\frac{\mathit{k}}{2,}\mathit{k},3\frac{\mathit{k}}{2,}\dots \dots \dots \dots \dots \dots ,\mathit{M}-\frac{\mathit{k}}{2}$$E18

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

$$0,\mathit{k},2\mathit{k},\dots \dots \dots \dots \dots \dots ,\mathit{M}-\frac{\mathit{k}}{2}$$E19

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

$$\frac{\mathit{k}}{2,}3\frac{\mathit{k}}{2,}5\frac{\mathit{k}}{2,.}\dots \dots \dots \dots \dots ,\mathit{M}-\mathit{k}$$E20

2.6 Theorem 3: index of first element

a. When $\mathit{k}\mid \mathit{N}$, the index ${\mathit{n}}_{\mathit{a}}$ of the first element in the positive data group of an MRT coefficient ${\mathit{Y}}_{\mathit{k}}^{\left(\mathit{p}\right)}$ is ${\mathit{n}}_{\mathit{a}}=\frac{\mathit{p}}{\mathit{k}}$.

b. For $\mathit{k}\mid \mathit{M}$, if an element with index $\mathit{n}$ belongs in the positive data set of an MRT coefficient ${\mathit{Y}}_{\mathit{k}}^{\left(\mathit{p}\right)}$, then the element with index $\mathit{n}+\frac{\mathit{M}}{\mathit{k}}$ occurs in the negative data set of the same MRT coefficient.

c. The first element in the positive set of an MRT coefficient ${\mathit{Y}}_{\mathit{k}}^{\left(\mathit{p}\right)}$ when k does not divide M, has the index ${\mathit{n}}_{\mathit{a}}=\frac{\mathit{p}}{\mathit{k}}$. The first element in the negative set of an MRT coefficient ${\mathit{Y}}_{\mathit{k}}^{\left(\mathit{p}\right)}$, when $\mathit{k}$ does not divide $\mathit{M}$, is ${\mathit{n}}_{\mathit{b}}=\frac{\mathit{p}+\mathit{M}}{\mathit{k}}$.

Proof.

a. The first element in MRT coefficient ${\mathit{Y}}_{\mathit{k}}^{\left(\mathit{p}\right)}$ will have an index that is the smallest solution of (4),

$${\left(\left(\mathit{nk}\right)\right)}_{\mathit{N}}=\mathit{p}.$$

Solutions exist for Eq. (4) only if $\mathit{g}\left(\mathit{k},\mathit{N}\right)$ divides $\mathit{p}$. Since $\mathit{g}\left(\mathit{k},\mathit{N}\right)=\mathit{k}$, the former condition can be written as $\mathit{k}\mid \mathit{p}$.

Since $\mathit{k}\mid \mathit{p}$, the smallest solution to Eq. (4) is ${\mathit{n}}_{\mathit{a}}=\frac{\mathit{p}}{\mathit{k}}$, and thus ${\mathit{n}}_{\mathit{a}}=\frac{\mathit{p}}{\mathit{k}}$ is the first member in the positive data set of MRT coefficient ${\mathit{Y}}_{\mathit{k}}^{\left(\mathit{p}\right)}$.

The condition $\mathit{g}\left(\mathit{k},\mathit{M}\right)=\mathit{k}$ is necessary for both positive and negative sets to be present in an MRT coefficient.

b. Given ${\left(\left(\mathit{nk}\right)\right)}_{\mathit{N}}=\mathit{p}$,

$${〚\left(\mathit{n}+\frac{\mathit{M}}{\mathit{k}}\right)\mathit{k}〛}_{\mathit{N}}={〚\mathit{nk}〛}_{\mathit{N}}+{〚\frac{\mathit{M}}{\mathit{k}}\mathit{k}〛}_{\mathit{N}}=\mathit{p}+\mathit{M}$$

Hence, if index $\mathit{n}$ belongs in the positive set, index $\mathit{n}+\frac{\mathit{M}}{\mathit{k}}$ will be present in the negative set since ${〚\left(\mathit{n}+\frac{\mathit{M}}{\mathit{k}}\right)\mathit{k}〛}_{\mathit{N}}=\mathit{p}+\mathit{M}$.

c. From (18), when $\mathit{k}$ does not divide $\mathit{M}$, the sequence of allowable phase indices is

$$0,\frac{\mathit{k}}{2,}\mathit{k},3\frac{\mathit{k}}{2,}\dots \dots \dots \dots \dots .,\mathit{M}-\frac{\mathit{k}}{2}$$

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

$$0,\mathit{k},2\mathit{k},\dots \dots \dots \dots \dots \dots \dots ,\mathit{M}-\frac{\mathit{k}}{2}$$

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

$$\frac{\mathit{k}}{2,}3\frac{\mathit{k}}{2,}5\frac{\mathit{k}}{2,.}\dots \dots \dots \dots \dots ,\mathit{M}-\mathit{k}$$

The first data element that satisfies ${\left(\mathit{nk}\right)}_{\mathit{N}}=\mathit{p}$ is $\frac{\mathit{p}}{\mathit{k}}$ since $\mathit{k}\mid \mathit{p}$ is satisfied, $\mathit{p}$ being a valid phase index. Hence, the first element in the positive set has index ${\mathit{n}}_{\mathit{a}}=\frac{\mathit{p}}{\mathit{k}}$.

Also, the allowable phase indices that produce MRT coefficients having only negative sets are actually nonvalid allowable phase indices. If ${\mathit{p}}_{\mathit{b}}\text{is}$ a nonvalid phase index, there is a valid phase index ${\mathit{p}}_{\mathit{a}}$ given by ${\mathit{p}}_{\mathit{a}}={\mathit{p}}_{\mathit{b}}+\mathit{M}$. Hence, the first data element in the negative set has the index ${\mathit{n}}_{\mathit{b}}=\frac{\mathit{p}+\mathit{M}}{\mathit{k}}$.

If $\mathit{k}$ does not divide $\mathit{N}$, then ${\mathit{n}}_{\mathit{a}}=\frac{\mathit{p}}{\mathit{g}\left(\mathit{k},\mathit{N}\right)}$ cannot be a solution since $\mathit{g}\left(\mathit{k},\mathit{N}\right)\mid \mathit{k}$. The extended Euclidean algorithm can be used to find a particular solution for this case.

2.7 Closed-form expression for 1-D MRT

By the MRT definition, and looking at element indices of both positive and negative data sets in (12), and, assuming ${\mathit{n}}_{\mathit{a}}$ belongs in the positive set, and ${\mathit{n}}_{\mathit{b}}$ in the negative set, a 1-D MRT coefficient can be expressed in the following manner:

$$\begin{array}{ll}{\mathit{Y}}_{\mathit{k}}^{\left(\mathit{p}\right)}=& \left[{\mathit{x}}_{{\mathit{n}}_{\mathit{a}}}+{\mathit{x}}_{{\mathit{n}}_{\mathit{a}}+{\mathit{g}}_{\mathit{k}}}+{\mathit{x}}_{{\mathit{n}}_{\mathit{a}}+2{\mathit{g}}_{\mathit{k}}}+{\mathit{x}}_{{\mathit{n}}_{\mathit{a}}+3{\mathit{g}}_{\mathit{k}}}+..\dots \dots +{\mathit{x}}_{{\mathit{n}}_{\mathit{a}}+\mathit{g}\left(\mathit{k},\mathit{N}\right)-1{\mathit{g}}_{\mathit{k}}}\right]\\ & -\left[{\mathit{x}}_{{\mathit{n}}_{\mathit{b}}}+{\mathit{x}}_{{\mathit{n}}_{\mathit{b}}+{\mathit{g}}_{\mathit{k}}}+{\mathit{x}}_{{\mathit{n}}_{\mathit{b}}+2{\mathit{g}}_{\mathit{k}}}+{\mathit{x}}_{{\mathit{n}}_{\mathit{b}}+3{\mathit{g}}_{\mathit{k}}}+\dots \dots \dots +{\mathit{x}}_{{\mathit{n}}_{\mathit{b}}+\mathit{g}\left(\mathit{k},\mathit{N}\right)-1{\mathit{g}}_{\mathit{k}}}\right]\end{array}$$

This can be written as

$${\mathit{Y}}_{{\mathit{k}}_{\left(\mathit{p}\right)}}^{}=\sum _{\mathit{j}=0}^{\mathit{g}\left(\mathit{k},\mathit{N}\right)-1}{\mathit{x}}_{{\mathit{n}}_{\mathit{a}}+{\mathit{jg}}_{\mathit{k}}}-{\mathit{x}}_{{\mathit{n}}_{\mathit{b}}+{\mathit{jg}}_{\mathit{k}}}$$E21

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

When $\mathit{k}$ divides $\mathit{N}$, using Theorem 3(a), we observe that the first element in the positive set is ${\mathit{n}}_{\mathit{a}}=\frac{\mathit{p}}{\mathit{k}}$. Also, using Theorem 3(b), any index in the positive set is related to any index in the negative set, given $\mathit{k}\mid \mathit{M}$. This relation is ${\mathit{n}}_{\mathit{b}}={\mathit{n}}_{\mathit{a}}+\frac{\mathit{M}}{\mathit{k}}$ When $\mathit{k}$ does not divide $\mathit{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 $\mathit{k}\mid \mathit{M},{\mathit{n}}_{\mathit{a}}=\frac{\mathit{p}}{\mathit{k}}$, and ${\mathit{n}}_{\mathit{b}}={\mathit{n}}_{\mathit{a}}+\frac{\mathit{M}}{\mathit{k}}$. Also, $\mathit{k}$ does not divide $\mathit{M}$. Using these, we can rewrite Eq. (21) as,

$$\begin{array}{ll}{\mathit{Y}}_{\mathit{k}}^{\left(\mathit{p}\right)}=& \left[{\mathit{x}}_{\frac{\mathit{p}}{\mathit{k}}}+{\mathit{x}}_{\frac{\mathit{p}}{\mathit{k}}+\frac{\mathit{N}}{\mathit{k}}}+{\mathit{x}}_{\frac{\mathit{p}}{\mathit{k}}+\frac{2\mathit{N}}{\mathit{k}}}+{\mathit{x}}_{\frac{\mathit{p}}{\mathit{k}}+\frac{3\mathit{N}}{\mathit{k}}}+\dots \dots \mathrm{..}+{\mathit{x}}_{\frac{\mathit{p}}{\mathit{k}}+\frac{\left(\mathit{k}-1\right)\mathit{N}}{\mathit{k}}}\right]\\ & -\left[{\mathit{x}}_{\frac{\mathit{p}}{\mathit{k}}+\frac{\mathit{N}}{2\mathit{k}}}+{\mathit{x}}_{\frac{\mathit{p}}{\mathit{k}}+\frac{3\mathit{N}}{2\mathit{k}}}+{\mathit{x}}_{\frac{\mathit{p}}{\mathit{k}}+\frac{5\mathit{N}}{2\mathit{k}}}+{\mathit{x}}_{\frac{\mathit{p}}{\mathit{k}}+\frac{7\mathit{N}}{2\mathit{k}}}+\dots \dots \mathrm{..}+{\mathit{x}}_{\frac{\mathit{p}}{\mathit{k}}+\frac{\left(2\mathit{k}-1\right)\mathit{N}}{2\mathit{k}}}\right]\end{array}$$E22

On further simplification,

$$\begin{array}{c}{\mathit{Y}}_{\mathit{k}}^{\left(\mathit{p}\right)}=\sum _{\mathit{j}=0}^{\mathit{k}-1}\left[{\mathit{x}}_{\frac{\mathit{jN}+\mathit{p}}{\mathit{k}}}-{\mathit{x}}_{\frac{\left(2\mathit{j}+1\right)\mathit{N}+2\mathit{p}}{2\mathit{k}}}\right]\end{array}$$

$$\begin{array}{c}\mathit{p}=0,\mathit{k},2\mathit{k},\dots ,\mathit{M}-\mathit{k}\end{array}$$E23

When $\mathit{k}$ does not divide $\mathit{M}$, it has been seen that positive and negative groups cannot exist together for the same MRT coefficient. For certain values of $\mathit{p}$, only positive groups exist. For other values of $\mathit{p}$, only negative groups exist. As seen, for positive groups, ${\mathit{n}}_{\mathit{a}}=\frac{\mathit{p}}{\mathit{k}}$, and for negative groups, ${\mathit{n}}_{\mathit{b}}=\frac{\mathit{p}+\mathit{M}}{\mathit{k}}$. An MRT coefficient with only a positive group has the following form:

$${\mathit{Y}}_{\mathit{k}}^{\left(\mathit{p}\right)}=\left[{\mathit{x}}_{\frac{\mathit{p}}{\mathit{k}}}+{\mathit{x}}_{\frac{\mathit{p}}{\mathit{k}}+\frac{\mathit{N}}{\mathit{k}}}+{\mathit{x}}_{\frac{\mathit{p}}{\mathit{k}}+\frac{2\mathit{N}}{\mathit{k}}}+{\mathit{x}}_{\frac{\mathit{p}}{\mathit{k}}+\frac{3\mathit{N}}{\mathit{k}}}+\dots \dots \mathrm{..}+{\mathit{x}}_{\frac{\mathit{p}}{\mathit{k}}+\frac{\left(\mathit{k}-1\right)\mathit{N}}{\mathit{k}}}\right]$$

which, when simplified, becomes

$$\begin{array}{l}{\mathit{Y}}_{\mathit{k}}^{\left(\mathit{p}\right)}=\sum _{\mathit{j}=0}^{\mathit{k}-1}\left[{\mathit{x}}_{\frac{\mathit{jN}+\mathit{p}}{\mathit{k}}}\right]\\ \mathit{p}=0,\mathit{k},2\mathit{k},\dots ,\mathit{M}-\frac{\mathit{k}}{2}\end{array}$$E24

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

$${\mathit{Y}}_{\mathit{k}}^{\left(\mathit{p}\right)}=-\left[{\mathit{x}}_{\frac{\mathit{p}+\mathit{M}}{\mathit{k}}}+{\mathit{x}}_{\frac{\mathit{p}+\mathit{M}}{\mathit{k}}+\frac{\mathit{N}}{\mathit{k}}}+{\mathit{x}}_{\frac{\mathit{p}+\mathit{M}}{\mathit{k}}+\frac{2\mathit{N}}{\mathit{k}}}+\dots \dots \mathrm{..}+{\mathit{x}}_{{\frac{\mathit{p}}{\mathit{k}}}^{+\frac{\left(\mathit{k}-1\right)\mathit{N}}{\mathit{k}}}}\right]$$

which, when simplified, becomes

$$\begin{array}{l}{\mathit{Y}}_{\mathit{k}}^{\left(\mathit{p}\right)}=-\sum _{\mathit{j}=0}^{\mathit{k}-1}\left[{\mathit{x}}_{\frac{\mathit{jN}+\mathit{p}+\mathit{M}}{\mathit{k}}}\right]\\ \mathit{p}=\frac{\mathit{k}}{2},\frac{3\mathit{k}}{2},\dots ,\mathit{M}-\mathit{k}\end{array}$$E25

When $\mathit{k}$ and N are co-prime, $\mathit{g}\left(\mathit{k},\mathit{N}\right)=1$. Hence, the positive set has only one element and similarly the negative set too has only one element. The values of ${\mathit{n}}_{\mathit{a}}$ and ${\mathit{n}}_{\mathit{b}}$ have to be computed using the Euclidean algorithm or by the trial-and-error method. The MRT coefficient has the following form

$$\begin{array}{l}{\mathit{Y}}_{\mathit{k}}^{\left(\mathit{p}\right)}={\mathit{x}}_{{\mathit{n}}_{\mathit{a}}}-{\mathit{x}}_{{\mathit{n}}_{\mathit{b}}}\\ \mathit{p}=\mathrm{0,1,2,3},\dots \mathit{M}-1\end{array}$$E26

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 $\mathit{N}=8$, the DFT coefficient ${\mathit{Y}}_{\mathit{k}}$ can be expressed in terms of associated MRT as

$${\mathit{Y}}_{\mathit{k}}={\mathit{Y}}_{\mathit{k}}^{\left(0\right)}{\mathit{W}}_8^0+{\mathit{Y}}_{\mathit{k}}^{\left(1\right)}{\mathit{W}}_8^1+{\mathit{Y}}_{\mathit{k}}^{\left(2\right)}{\mathit{W}}_8^2+{\mathit{Y}}_{\mathit{k}}^{\left(2\right)}{\mathit{W}}_8^3$$

3. Redundancy in MRT

For some values of $\mathit{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 ${\mathit{Y}}_{\mathit{k}}^{\left(\mathit{p}\right)}$, for all $\mathit{h}$ such that $\mathit{g}\left(\mathit{h},\mathit{N}\right)=1$

$$\begin{array}{l}{\mathit{Y}}_{{\left(\mathit{hk}\right)}_{\mathit{N}}}^{\left({\left(\mathit{hp}\right)}_{\mathit{N}}\right)}={\mathit{Y}}_{\mathit{k}}^{\left(\mathit{p}\right)}\text{for}{〚\mathit{hp}〛}_{\mathit{N}}<\mathit{M},\text{and},\\ {\mathit{Y}}_{{\left(\mathit{hk}\right)}_{\mathit{N}}}^{\left({\left(\mathit{hp}\right)}_{\mathit{N}}-\mathit{M}\right)}=-{\mathit{Y}}_{\mathit{k}}^{\left(\mathit{p}\right)}\text{for}{〚\mathit{hp}〛}_{\mathit{N}}\ge \mathit{M}\end{array}$$

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

$${〚\mathit{q}〛}_{\mathit{N}}=\mathit{d}$$E27

and $\mathit{h}$ is a multiplication factor, then

$${〚\mathit{hq}〛}_{\frac{\mathit{N}}{\mathit{g}\left(\mathit{h},\mathit{N}\right)}}=\mathit{hd}$$E28

If $\mathit{g}\left(\mathit{h},\mathit{N}\right)=1$, Eq. (28) becomes

$${〚\mathit{hq}〛}_{\mathit{N}}=\mathit{hd}$$E29

Given ${\mathit{Y}}_{\mathit{k}}^{\left(\mathit{p}\right)}$, and a set of indices $\mathit{n}$ that satisfies

$${〚\mathit{nk}〛}_{\mathit{N}}=\mathit{p}$$E30

and a set of indices $\mathit{n}$′ that satisfies

$${〚\mathit{n}\text{'}\mathit{k}〛}_{\mathit{N}}=\mathit{p}+\mathit{M}$$E31

If there is $\mathit{h}$ such that $\mathit{g}\left(\mathit{h},\mathit{N}\right)=1$, using Eqs. (27)–(29),

$${〚\mathit{n}\left(\mathit{hk}\right)〛}_{\mathit{N}}=\mathit{hp}$$E32

and

$${〚\mathit{n}\text{'}\left(\mathit{hk}\right)〛}_{\mathit{N}}=\mathit{h}\left(\mathit{p}+\mathit{M}\right)$$E33

$${〚\mathit{n}\text{'}\left(\mathit{hk}\right)〛}_{\mathit{N}}=\mathit{hp}+\mathit{hM}$$E34

Since $\mathit{g}\left(\mathit{h},\mathit{N}\right)=1,\mathit{h}$ is odd, and hence

$$\mathit{hp}+\mathit{hM}\equiv \mathit{hp}+\mathit{M}$$E35

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

$${〚\mathit{n}\text{'}\left(\mathit{hk}\right)〛}_{\mathit{N}}=\mathit{hp}+\mathit{M}$$E36

From the definition of MRT, and Eqs. (32) and (36), it is seen that the set of indices $\mathit{n}$ and $\mathit{n}\text{'}$ form the MRT coefficient ${\mathit{Y}}_{{\left(\mathit{hk}\right)}_{\mathit{N}}}^{{\left(\mathit{hp}\right)}_{\mathit{N}}}$. Using Eqs. (30)–(32) and (36),

$${\mathit{Y}}_{{\left(\mathit{hk}\right)}_{\mathit{N}}}^{\left({\left(\mathit{hp}\right)}_{\mathit{N}}\right)}={\mathit{Y}}_{\mathit{k}}^{\left(\mathit{p}\right)}$$E37

If ${\left(\mathit{hp}\right)}_{\mathit{N}}\ge \mathit{M}$, then

$${\mathit{Y}}_{{\left(\mathit{hk}\right)}_{\mathit{N}}}^{\left({\left(\mathit{hp}\right)}_{\mathit{N}}-\mathit{M}\right)}=-{\mathit{Y}}_{\mathit{k}}^{\left(\mathit{p}\right)}$$E38

since

$${\mathit{Y}}_{\mathit{k}}^{\left(\mathit{p}\right)}=-{\mathit{Y}}_{\mathit{k}}^{\left(\mathit{p}-\mathit{M}\right)}=-{\mathit{Y}}_{\mathit{k}}^{\left(\mathit{p}+\mathit{M}\right)}$$

Hence, the theorem on complete redundancy has been proved.

From Theorem 4, we see that prediction of redundancy is possible from the knowledge of $\mathit{N}$, frequency and phase. Given $\left(\mathit{k},\mathit{p}\right)$, 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 $\mathit{N}=6$, MRT coefficients of $\mathit{k}=5$ are completely redundant MRT coefficients of $\mathit{k}=1$, since 1 and 5 are co-prime to 6.

If $\mathit{k}\text{'}=\mathit{hk}$ and $\mathit{g}\left(\mathit{h},\mathit{N}\right)=1$, then MRT coefficients of the two frequency indices $\mathit{k}$ and $\mathit{k}\text{'}$ are redundant.

When $\mathit{k}=1$, MRT coefficients having frequency k′ that are co-prime to N can be obtained from MRT coefficients with a frequency of $\mathit{k}=1$. If $\mathit{k}\text{'}\mid \mathit{N}$, then we cannot obtain $\mathit{k}\text{'}$ by multiplying an integer $\mathit{k}$ with an integer $\mathit{h},\mathit{k}\text{'}=\mathit{hk}$, satisfying $\mathit{g}\left(\mathit{h},\mathit{N}\right)=1$ and $\mathit{k}\ne \mathit{k}\text{'}$ Thus, MRT coefficients with frequency indices that are divisors of $\mathit{N}$ cannot be redundant to each other.

Let k′ satisfy $\mathit{k}\text{'}=\mathit{hk}$ such that $\mathit{g}\left(\mathit{h},\mathit{N}\right)=1$ and $\mathit{k}\ne \mathit{k}\text{'}$. If $\mathit{k}\text{'}$ is nonprime, there is a nontrivial common divisor with $\mathit{N}$. So, even though it is not a divisor of $\mathit{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. $\mathit{N}$ are all completely redundant to each other.

Proof. Assume ${\mathit{k}}_1$ and ${\mathit{k}}_2$ are two frequency indices that have common $gcd$ w.r.t. $\mathit{N}$.

$$\mathit{g}\left({\mathit{k}}_1,\mathit{N}\right)=\mathit{k}$$E39

$$\mathit{g}\left({\mathit{k}}_2,\mathit{N}\right)=\mathit{k}$$E40

Assume $\mathit{h}$ exists such that

$$\mathit{g}\left(\mathit{h},\mathit{N}\right)=1$$E41

From Eq. (41), $\mathit{h}$ and $\mathit{N}$ are co-prime. Hence,

$$\mathit{g}\left({\mathit{hk}}_1,\mathit{N}\right)=\mathit{k}$$E42

$${〚{\mathit{hk}}_1〛}_{\mathit{N}}={\mathit{hk}}_1-\mathit{Nq}\text{if}0\le {\mathit{hk}}_1-\mathit{Nq}<\mathit{N},\mathit{q}\in \mathbb{Z}$$E43

Using Eq. (43) and $gcd$ property,

$$\mathit{g}\left({\left({\mathit{hk}}_1\right)}_{\mathit{N}},\mathit{N}\right)=\mathit{g}\left({\mathit{hk}}_1-\mathit{Nq},\mathit{N}\right)=\mathit{g}\left({\mathit{hk}}_1,\mathit{N}\right)=\mathit{k}$$E44

From Eqs. (40) and (44),

$${\mathit{k}}_2={〚{\mathit{hk}}_1〛}_{\mathit{N}}$$E45

From Eqs. (41) and (45), and using Theorem 4, it can be concluded that frequency indices ${\mathit{k}}_1$ and ${\mathit{k}}_2$ are completely redundant. Hence, the theorem is proved.

For example, if $\mathit{N}=8$, the following relations exist:

$$\begin{array}{l}{\mathit{Y}}_1^{\left(0\right)}={\mathit{Y}}_3^{\left(0\right)}={\mathit{Y}}_5^{\left(0\right)}={\mathit{Y}}_7^{\left(0\right)}\\ {\mathit{Y}}_1^{\left(1\right)}={\mathit{Y}}_3^{\left(3\right)}=-{\mathit{Y}}_5^{\left(1\right)}=-{\mathit{Y}}_7^{\left(3\right)},\\ {\mathit{Y}}_1^{\left(2\right)}=-{\mathit{Y}}_3^{\left(2\right)}={\mathit{Y}}_5^{\left(2\right)}=-{\mathit{Y}}_7^{\left(2\right)}\text{and},\\ {\mathit{Y}}_1^{\left(3\right)}={\mathit{Y}}_3^{\left(1\right)}=-{\mathit{Y}}_5^{\left(3\right)}=-{\mathit{Y}}_7^{\left(1\right)}.\end{array}$$

Since $\mathit{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 $\mathit{g}\left(2,8\right)=\mathit{g}\left(6,8\right)=2$, ${\mathit{Y}}_2^{\left(0\right)}={\mathit{Y}}_6^{\left(0\right)}$, and ${\mathit{Y}}_2^{\left(2\right)}=-{\mathit{Y}}_6^{\left(2\right)}$.

Theorem 5 shows that we can group frequencies based on their $gcd$ w.r.t. $\mathit{N}$. AII nondivisor frequency indices are related to divisor frequency indices through multiplication factors $\mathit{h}$ such that $\mathit{g}\left(\mathit{h},\mathit{N}\right)=1$. The count of the possible factors of multiplication involved in complete redundancy is Euler’s totient function $\mathit{\Phi }\left(\mathit{N}\right)$, which specifies the count of positive integers smaller than or equal to $\mathit{N}$ that are co-prime to $\mathit{N}$, 1 being considered co-prime to every other integer. Given 1-D MRT coefficients having frequency $\mathit{k}=1$, there would be $\mathit{\Phi }\left(\mathit{N}\right)-1$ other frequencies whose MRT coefficients can be obtained from this MRT coefficient. Combined with $\mathit{k}=1$, these $\mathit{\Phi }\left(\mathit{N}\right)$ frequencies thus comprise the group of frequencies that satisfy $\mathit{g}\left(\mathit{h},\mathit{N}\right)=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 $\mathit{\Phi }\left(\mathit{N}\right)$ possible factors of multiplication that produce other members of the group of frequency indices associated with $\mathit{k}$. From Theorem 4, the equation for complete redundancy is $\mathit{k}\text{'}={\left(\mathit{hk}\right)}_{\mathit{N}}$, where $\mathit{g}\left(\mathit{h},\mathit{N}\right)=1$. Also,

$${〚\mathit{hk}〛}_{\mathit{N}}={〚\left(\mathit{h}+\frac{\mathit{N}}{\mathit{k}}\right)\mathit{k}〛}_{\mathit{N}}$$E46

Eq. (46) implies that the set of $\mathit{k}\text{'}$ that is generated from divisor $\mathit{k}$ is unique only for multiplicative factors in the set $\left[0,\frac{\mathit{N}}{\mathit{k}}-1\right]$, and repeats thereafter for the remaining sets of the same length. Hence, the problem now gets reduced to $\mathit{k}\text{'}={\left(\left(\mathit{hk}\right)\right)}_{\mathit{N}/\mathit{k}}$ where $\mathit{g}\left(\mathit{h},\frac{\mathit{N}}{\mathit{k}}\right)=1$. The number of such multiplicative factors $\mathit{h}$ is $\mathit{\Phi }\left(\frac{\mathit{N}}{\mathit{k}}\right)$, and these factors are the totatives of $\frac{\mathit{N}}{\mathit{k}}$ Hence, the number of frequency indices that are related by complete redundancy to a frequency index $\mathit{k}$ is given by $\mathit{\Phi }\left(\frac{\mathit{N}}{\mathit{k}}\right)$ and they are obtained by $\mathit{k}\text{'}={\left(\mathit{hk}\right)}_{\mathit{N}}$ where $\mathit{g}\left(\mathit{h},\frac{\mathit{N}}{\mathit{k}}\right)=1$.

From number theory [17],

$$\sum _{\mathit{d}\mathit{V}\mathit{N}}\mathit{\Phi }\left(\mathit{d}\right)=\mathit{N},\text{if}\mathit{N}\ge 1,$$E47

From Eq. (47), the sum of the terms $\mathit{\Phi }\left(\frac{\mathit{N}}{\mathit{k}}\right)$ over all divisors of $\mathit{N}$ is given by $\mathit{N}$, since ${\sum }_{\mathit{d}\mid \mathit{N}}\mathit{\Phi }\left(\mathit{d}\right)={\sum }_{\mathit{d}\mid \mathit{N}}\mathit{\Phi }\left(\frac{\mathit{N}}{\mathit{d}}\right)$. Hence, all the $\mathit{N}$ frequency indices $\mathit{k}=\left[0,\mathit{N}-1\right]$ have been mapped.

Thus, all the frequency indices of 1-D MRT can be classified on the basis of their $gcd$ w.r.t. $\mathit{N}$.

3.3 Theorem 6: Mapping between phase indices

One-to-one mapping exists between phases of 1-D MRT coefficients having frequencies $\mathit{k}$ and $\mathit{k}\text{'}$ connected through complete redundancy.

Proof. For two MRT coefficients having frequencies $\mathit{k}$ and k′ connected by complete redundancy, the number of phases corresponding to each frequency is equal since $\mathit{g}\left(\mathit{k},\mathit{N}\right)=\mathit{g}\left(\mathit{k}\text{'},\mathit{N}\right)$, and the number of phase indices is given by $\frac{\mathit{N}}{\mathit{g}\left(\mathit{k},\mathit{N}\right)}$. The phases lie in the range $\left[0,\mathit{M}-1\right]$. From Theorem 4 on complete redundancy, the relation between phases is given by ${\mathit{p}}^{\prime }={〚\mathit{hp}〛}_{\mathit{N}},\mathit{g}\left(\mathit{h},\mathit{N}\right)=1$. Using a theorem on the reduced residue systems, on multiplication with $\mathit{h}$, the resulting group of phase indices $\mathit{p}\text{'}$ too have the same elements as the original group. Multiplication of phases in $\left[0,\mathit{M}-1\right]$ by $\mathit{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 $\mathit{k}$ and $\mathit{k}\text{'}$ connected through complete redundancy.

To look at an example, when $\mathit{N}=8$,

$$\begin{array}{l}{\mathit{Y}}_1^{\left(0\right)}={\mathit{Y}}_3^{\left(0\right)},\\ {\mathit{Y}}_1^{\left(1\right)}={\mathit{Y}}_3^{\left(3\right)}\\ {\mathit{Y}}_1^{\left(2\right)}=-{\mathit{Y}}_3^{\left(2\right)},\text{and},\\ {\mathit{Y}}_1^{\left(3\right)}={\mathit{Y}}_3^{\left(1\right)}.\end{array}$$

Since $\mathit{k}=1$ and $\mathit{k}=3$ are redundant through the co-prime $\mathit{h}=3$, the set of phase indices of $\mathit{k}=1,\mathit{p}=\left[\mathrm{0,1,2,3}\right]$, when subjected to the operation ${\mathit{p}}^{\prime }={\left[\mathit{hp}\right]}_{\mathit{N}}$ would result $\text{in}\mathit{p}\text{'}=\left[\mathrm{0,3,6,1}\right]$, which reduces to $\mathit{p}\text{'}=\left[\mathrm{0,3,2,1}\right]$ after the condition ${〚\mathit{hp}〛}_{\mathit{N}}<\mathit{M}$ is checked and relevant sign change. Hence, $\mathit{p}=\left[\mathrm{0,1,2,3}\right]$ maps to $\mathit{p}\text{'}=\left[\mathrm{0,3,2,1}\right]$.

3.4 Derived redundancy

For $\mathit{N}=6$,

$${\mathit{Y}}_3^{\left(0\right)}={\mathit{Y}}_1^{\left(0\right)}-{\mathit{Y}}_1^{\left(1\right)}+{\mathit{Y}}_1^{\left(2\right)}$$

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 ${\mathit{Y}}_{\mathit{k}\text{'}}^{\left(\mathit{p}\right)}$ and ${\mathit{Y}}_{\mathit{k}}^{\left({\mathit{p}}_{\mathit{a}}\right)}$ be the two MRT coefficients. The congruence relations for ${\mathit{Y}}_{\mathit{k}}^{\left({\mathit{p}}_{\mathit{a}}\right)}$ are ${〚\mathit{nk}〛}_{\mathit{N}}={\mathit{p}}_{\mathit{a}}\text{and}{〚\mathit{nk}〛}_{\mathit{N}}={\mathit{p}}_{\mathit{a}}+\mathit{M}$. The congruence relations for ${\mathit{Y}}_{\mathit{k}\text{'}}^{\left(\mathit{p}\right)}$ are ${〚\mathit{n}{\mathit{k}}^{\prime }〛}_{\mathit{N}}=\mathit{p}$ and ${〚\mathit{n}{\mathit{k}}^{\prime }〛}_{\mathit{N}}=\mathit{p}+\mathit{M}$. Assume that a relation $\mathit{k}\text{'}=\mathit{dk}$ exists between $\mathit{k}$ and $\mathit{k}\text{'}$. Hence, ${〚\mathit{dnk}〛}_{\mathit{N}}=\mathit{p}$ and ${〚\mathit{dnk}〛}_{\mathit{N}}=\mathit{p}+\mathit{M}.{〚\mathit{dnk}〛}_{\mathit{N}}=\mathit{p}$ may be written as ${〚\mathit{nk}〛}_{\mathit{N}}=\frac{\mathit{p}}{\mathit{d}}$ if $\mathit{g}\left(\mathit{d},\mathit{N}\right)=\mathit{d}$, and $\mathit{d}\mid \mathit{p}$. In other words, $\mathit{d}$ should be a divisor of $\mathit{N}$. From ${〚\mathit{nk}〛}_{\mathit{N}}=\frac{\mathit{p}}{\mathit{d}}$ and ${〚\mathit{nk}〛}_{\mathit{N}}={\mathit{p}}_{\mathit{a}},{\mathit{p}}_{\mathit{a}}=\frac{\mathit{p}}{\mathit{d}}$. Multiplying both sides of ${〚\mathit{nk}〛}_{\mathit{N}}={\mathit{p}}_{\mathit{a}}+\mathit{M} \mathit{by} \mathit{d},{〚\mathit{dnk}〛}_{\mathit{N}}={\mathit{dp}}_{\mathit{a}}+\mathit{dM}$. If d is odd, this can be written as ${〚\mathit{dnk}〛}_{\mathit{N}}={\mathit{dp}}_{\mathit{a}}+\mathit{M}$, which becomes ${〚\mathit{n}{\mathit{k}}^{\prime }〛}_{\mathit{N}}=\mathit{p}+\mathit{M}$. Hence, provided there exists an odd-valued divisor $\mathit{d}$ of $\mathit{N}$, such that $\mathit{k}\text{'}=\mathit{dk}$, then there is derived redundancy between and ${\mathit{Y}}_{\mathit{k}\text{'}}^{\left(\mathit{p}\right)}$ and ${\mathit{Y}}_{\mathit{k}}^{\left({\mathit{p}}_{\mathit{a}}\right)}$. Hence, we can conclude that there cannot be derived redundancy when $\mathit{N}$ is a power of 2 since $\mathit{N}$ has no divisors that are odd. For even $\mathit{N}$ not a power of 2, derived redundancy exists since $\mathit{N}$ then has divisors that are odd. Details of derived redundancies are shown in Tables 1 and 2 for $\mathit{N}=6$ and $\mathit{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 $\mathit{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 $\mathit{k}\text{'}=\mathit{dk}$, for $\mathit{d}$ an odd integer. Considering the divisor set of $\mathit{N}$, this condition is satisfied only by divisors that are powers of 2, as observed in the above example. If $\mathit{k}\text{'}=2^{\mathit{a}}$, then given any $\mathit{k}$ and odd-valued $\mathit{d}$ except $\mathit{d}=1,\mathit{k}\text{'}\ne \mathit{dk}$. So, the unique divisor set for $\mathit{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 $\mathit{N}$ is a power of 2, the frequencies that form unique coefficients are themselves powers of 2. Since, $\mathit{k}=0={〚\mathit{N}〛}_{\mathit{N}}$ and $\mathit{N}$ a power of 2, then $\mathit{k}=0$ produces a unique coefficient. The first frequency index is $\mathit{k}=1$, and followed by $\mathit{k}=2,4,\dots ,\mathit{N}$. The number of unique coefficients produced by each frequency index $\mathit{k}$ is given by the number of allowable phase indices for each frequency index $\mathit{k}$. For an MRT coefficient ${\mathit{Y}}_{\mathit{k}}^{\left(\mathit{p}\right)}$ to exist, $\mathit{p}$ should be divisible by $\mathit{k}$. When $\mathit{k}=\mathit{N}$, this condition has only one solution for $\mathit{p},\mathit{p}=0$. All other frequency indices have $\frac{\mathit{M}}{\mathit{k}}$ coefficients each. Hence, the total number of UMRT coefficients is given by

$$\begin{array}{ll}\mathit{Tot}& =1+\sum _{\mathit{t}=0}^{{log}_2\mathit{M}}\frac{\mathit{M}}{2^{\mathit{t}}}\\ & =1+\mathit{M}\sum _{\mathit{t}=0}^{{log}_2\mathit{M}}\frac{1}{2^{\mathit{t}}}\\ & =1+\mathit{M}\frac{1-{\left(\frac{1}{2}\right)}^{\left({log}_2\mathit{M}+1\right)}}{\frac{1}{2}}\\ & =1+\mathit{N}\left(1-2^{-\left({log}_2\mathit{M}+1\right)}\right)\\ & =1+\mathit{N}\left(1-\frac{1}{\mathit{N}}\right)\\ & =\mathit{N}\end{array}$$

Hence, the number of UMRT coefficients, when $\mathit{N}$ is a power of 2, is $\mathit{N}$.

If $\mathit{N}$ is not a power of 2, $\mathit{k}=0$ does not produce UMRT coefficients. Let $\mathit{k}\text{'}$ be the highest power of 2 frequency and a divisor of $\mathit{N}$. Hence $\mathit{N}=\mathit{dk}\text{'},\mathit{d}$ being an odd integer; if $\mathit{d}$ has an even value, then it would violate the assumption that $\mathit{k}\text{'}$ is the highest power of 2 frequency and a divisor of N. Since $\mathit{d}$ has an odd value, it is not possible for $\mathit{k}\text{'}$ to be a divisor for $\mathit{M}$ as $\frac{\mathit{d}}{2}$ cannot be integer-valued. The number of valid phase indices is $\frac{\mathit{N}}{\mathit{k}\text{'}}$ and thus there exist $\frac{\mathit{N}}{\mathit{k}\text{'}}$ MRT coefficients in the case that $\mathit{k}\text{'}$ does not divide $\mathit{M}$. AII the numbers that are powers of 2 and divide $\mathit{N}$ and are smaller than $\mathit{k}\text{'}$ will be divisors of $\mathit{M}$. These are $\mathit{k}=\mathrm{1,2,4},\dots ,\frac{\mathit{k}\text{'}}{2}$. There are $\frac{\mathit{M}}{\mathit{k}}$ MRT coefficients produced by these frequencies. When $\mathit{N}$ is not a power of 2, frequency $\mathit{k}=0$ can be obtained by derived redundancy. A frequency $\mathit{k}=$0 is equivalent to $\mathit{k}=\mathit{N}$, since ${〚\mathit{N}〛}_{\mathit{N}}=0$. Frequency $\mathit{N}$ relates to $\mathit{k}\text{'}$ through $\mathit{N}=\mathit{dk}\text{'},\mathit{d}$ being odd. This can be recalled to be sufficient for derived redundancy to occur. Thus, in case if $\mathit{N}$ is not a power of 2, $\mathit{k}=0$ does not form an absolutely unique MRT coefficient. Hence, the total number of UMRT coefficients is

$$\begin{array}{ll}\mathit{Tot}& =1+\sum _{\mathit{t}=0}^{{log}_2\mathit{M}}\frac{\mathit{M}}{2^{\mathit{t}}}\\ & =1+\mathit{M}\frac{1-{\left(\frac{1}{2}\right)}^{\left({log}_2\mathit{M}+1\right)}}{\frac{1}{2}}\\ & =\frac{\mathit{N}}{\mathit{k}\text{'}}+\mathit{N}\left(1-\frac{2}{2\mathit{k}\text{'}}\right)\\ & =\mathit{N}\end{array}$$

We thus conclude that $\mathit{N}$ UMRT coefficients are needed to represent a 1-D signal of length $\mathit{N}$, whether $\mathit{N}$ is a power of 2 or not, and these coefficients are produced by frequencies that are divisors of $\mathit{N}$ and powers of 2, beginning with $\mathit{k}=1$.

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

(i) $\mathit{N}$ a power of 2

$${\mathit{Y}}_0^{\left(0\right)}=\sum _{\mathit{n}=0}^{\mathit{N}-1}{\mathit{x}}_{\mathit{n}}$$E48

$$\begin{array}{l}{\mathit{Y}}_{\mathit{k}}^{\left(\mathit{p}\right)}=\sum _{\mathit{j}=0}^{\mathit{k}-1}\left({\mathit{x}}_{\frac{\mathit{jN}+\mathit{p}}{\mathit{k}}}-{\mathit{x}}_{\frac{\left(2\mathit{j}+1\right)\mathit{N}+2\mathit{p}}{2\mathit{k}}}\right)\\ \mathit{k}=2^{\mathit{t}},0\le \mathit{t}\le {log}_2\mathit{M},\mathit{p}=\mathit{tk},0\le \mathit{t}\le \frac{\mathit{M}}{\mathit{k}}-1\end{array}$$E49

(ii) $\mathit{N}$ not a power of 2

$$\begin{array}{l}{\mathit{Y}}_{\mathit{k}}^{\left(\mathit{p}\right)}=\sum _{\mathit{j}=0}^{\mathit{k}-1}\left({\mathit{x}}_{\frac{\mathit{jN}+\mathit{p}}{\mathit{k}}}-{\mathit{x}}_{\frac{\left(2\mathit{j}+1\right)\mathit{N}+2\mathit{p}}{2\mathit{k}}}\right)\\ \mathit{k}=2^{\mathit{t}},0\le \mathit{t}\le {log}_2\mathit{M},\mathit{p}=\mathit{tk},0\le \mathit{t}\le \frac{\mathit{M}}{\mathit{k}}-1\end{array}$$E50

$$\begin{array}{l}{\mathit{Y}}_{\mathit{k}\text{'}}^{\left(\mathit{p}\right)}=\sum _{\mathit{j}=0}^{\mathit{k}\text{'}-1}\left({\mathit{x}}_{\frac{\mathit{jN}+\mathit{p}}{\mathit{k}}}\right)\\ \mathit{p}=\mathit{tk}\text{'},0\le \mathit{t}\le \frac{\mathit{M}}{\mathit{k}\text{'}}-\frac{1}{2}\end{array}$$E51

$$\begin{array}{l}{\mathit{Y}}_{\mathit{k}\text{'}}^{\left(\mathit{p}\right)}=-\sum _{\mathit{j}=0}^{\mathit{k}\text{'}-1}\left({\mathit{x}}_{\frac{\mathit{jN}+\mathit{p}+\mathit{M}}{\mathit{k}\text{'}}}\right)\\ \mathit{p}=\mathit{tk}\text{'}+\frac{\mathit{k}\text{'}}{2},0\le \mathit{t}\le \frac{\mathit{M}}{\mathit{k}\text{'}}-\frac{3}{2}\end{array}$$E52

where $\mathit{k}\text{'}$ is the highest frequency index that is a power of 2 and also a divisor of $\mathit{N}$.

5. Inverse MRT

5.1 Theorem 7: N a power of 2

Given the UMRT of a 1-D signal of size $\mathit{N}$, $\mathit{N}$ being a power of 2, the 1-D signal can be reconstructed from its UMRT by the following formula

$${\mathit{x}}_{\mathit{n}}=\frac{1}{\mathit{N}}{\mathit{Y}}_0^{\left(0\right)}+\sum _{\mathit{t}=0}^{{log}_2\mathit{M}}\frac{1}{2^{\mathit{t}+1}}{\mathit{Y}}_{2^{\mathit{t}}}^{\left({\left(2^{\mathit{t}}\mathit{n}\right)}_{\mathit{N}}\right)},0\le \mathit{n}\le \mathit{N}-1$$E53

Proof. The data element that needs to be recovered from the UMRT is given by ${\mathit{x}}_{\mathit{n}}$. For any frequency index $\mathit{k}$, the value of the phase index $\mathit{p}$ of the UMRT coefficient ${\mathit{Y}}_{\mathit{k}}^{\left(\mathit{p}\right)}$ that contains ${\mathit{x}}_{\mathit{n}}$ is given by nk ${\left(\mathit{nk}\right)}_{\mathit{N}}=\mathit{p}$. Thus for a frequency that is a power of 2, $\mathit{k}=2^{\mathit{a}}$, the UMRT coefficient that contains ${\mathit{x}}_{\mathit{n}}$ is ${\mathit{Y}}_{2^{\mathit{a}}}^{\left({\left(2^{\mathit{a}}\mathit{n}\right)}_{\mathit{N}}\right)}$. The UMRT coefficient ${\mathit{Y}}_0^{\left(0\right)}$ contains all the elements of the data including ${\mathit{x}}_{\mathit{n}}$ since ${\left(\mathit{nk}\right)}_{\mathit{N}}=0,\forall \mathit{n}$, when $\mathit{k}=0$. In Eq. (53), ${\mathit{Y}}_0^{\left(0\right)}$ has a factor of multiplication $\frac{1}{\mathit{N}}$, and the remaining UMRT coefficients have a factor of multiplication $\frac{1}{2^{\mathit{t}+1}}$. Consequently, the ${\mathit{x}}_{\mathit{n}}$ that is a part of these coefficients have the corresponding factors of multiplication. The resultant multiplication factor $\mathit{f}$ for ${\mathit{x}}_{\mathit{n}}$ due to the summation is obtained as a sum of the individual factors of multiplication.

$$\begin{array}{cc}\mathit{f}& =\frac{1}{\mathit{N}}+\sum _{\mathit{t}=0}^{{log}_2\mathit{M}}\frac{1}{2^{\mathit{t}+1}}\\ & =\frac{1}{\mathit{N}}+\sum _{\mathit{t}=0}^{{log}_2\mathit{M}}{2}^{-\left(\mathit{t}+1\right)}\\ & =\frac{1}{\mathit{N}}+\frac{1}{2}\frac{\left(1-2^{-\left({log}_2\mathit{M}+1\right)}\right)}{\frac{1}{2}}\\ & =\frac{1}{\mathit{N}}+1-\frac{1}{\mathit{N}}\\ & =1\end{array}$$

Hence, as a result of the summation, one of the components of the result is the data ${\mathit{x}}_{\mathit{n}}$.

A UMRT coefficient ${\mathit{Y}}_{2^{\mathit{a}}}^{\left({\left(2^{\mathit{a}}\mathit{n}\right)}_{\mathit{N}}\right)}$ contains other terms besides ${\mathit{x}}_{\mathit{n}}$. For the inverse transform formula to be correct, these other terms that occur in the various UMRT coefficients ${\mathit{Y}}_{2^{\mathit{a}}}^{\left({\left(2^{\mathit{a}}\mathit{n}\right)}_{\mathit{N}}\right)}$ need to get canceled off. It can be proved that they vanish. Let $\mathit{k}$ be the smallest frequency at which any other data elements co-occur with ${\mathit{x}}_{\mathit{n}}$. ${\mathit{Y}}_0^{\left(0\right)}$ can be excluded as all data elements co-occur in it with a positive sign. Leaving out ${\mathit{Y}}_0^{\left(0\right)}$, another element shows co-occurrence with ${\mathit{x}}_{\mathit{n}}$ for the first time for $\mathit{k}=1$. For example, for $\mathit{N}=8,{\mathit{Y}}_1^{\left(0\right)}={\mathit{x}}_0-{\mathit{x}}_4$. Hence, if ${\mathit{x}}_0$ is the element to be obtained, it is seen that ${\mathit{x}}_4$ occurs with an opposite sign along with ${\mathit{x}}_0$ in the MRT coefficient corresponding to $\mathit{k}=1$, given $\mathit{by}{\mathit{Y}}_1^{\left(0\right)}$. From Eq. (12), when $\mathit{k}=1,\mathit{g}\left(\mathit{k},\mathit{N}\right)=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 $\frac{\mathit{M}}{\mathit{k}}$. Hence, ${\mathit{x}}_{\mathit{n}}$ and ${\mathit{x}}_{\mathit{n}+\mathit{M}}$, occur having opposite polarity, in any MRT coefficient of frequency $\mathit{k}=1$. In the same way, for $\mathit{k}=2$, the data element ${\mathit{x}}_{\mathit{n}+\mathit{M}}\text{occurs}$ with positive $sign$ since ${\mathit{Y}}_2^{\left(\mathit{p}\right)}={\mathit{x}}_{\mathit{n}}-{\mathit{x}}_{\mathit{n}+\frac{\mathit{N}}{4}}+{\mathit{x}}_{\mathit{n}+\frac{\mathit{N}}{2}}-{\mathit{x}}_{\mathit{n}+\frac{3\mathit{N}}{4}}$, given ${\left(\left(\mathit{nk}\right)\right)}_{\mathit{N}}=\mathit{p}$. From (12), the distance between the two successive data elements in a positive or negative group is given by $\frac{\mathit{N}}{\mathit{g}\left(\mathit{k},\mathit{N}\right)}$. Since k is a divisor of $\mathit{N}$, this reduces to $\frac{\mathit{N}}{\mathit{k}}$. Using Theorem 3(b), if elements ${\mathit{x}}_{\mathit{n}\text{'}}$, and ${\mathit{x}}_{\mathit{n}}$ co-occur in ${\mathit{Y}}_{\mathit{k}}^{\left(\mathit{p}\right)}$ but having different signs, then,

$$\mathit{n}\text{'}=\mathit{n}+{\mathit{q}}_{\mathit{odd}}\frac{\mathit{N}}{2\mathit{k}}$$E54

where ${\mathit{q}}_{\mathit{odd}}\text{is}$ an odd integer. At the next higher frequency $\mathit{k}\text{'}=2\mathit{k}$, Eq. (54) becomes

$$\mathit{n}\text{'}=\mathit{n}+{\mathit{q}}_{\mathit{odd}}\frac{\mathit{N}}{\mathit{k}\text{'}}$$E55

From (12), the general form for a data element ${\mathit{x}}_{{\mathit{n}}^{\text{'}}}$ of same sign present along with an element ${\mathit{x}}_{\mathit{n}}$ in the MRT coefficient ${\mathit{Y}}_{\mathit{k}\text{'}}^{\left(\mathit{p}\right)}$ is given by (since $\mathit{k}\text{'}$ is a divisor of $\mathit{N},\mathit{g}\left(\mathit{k}\text{'},\mathit{N}\right)=\mathit{k}\text{'})$

$$\mathit{n}\text{'}=\mathit{n}+\mathit{j}\frac{\mathit{N}}{\mathit{k}\text{'}}$$E56

where $\mathit{j}=\mathrm{0,1,2,3},\dots ,\mathit{k}\text{'}-1$.

Equation (55) can be seen to be a special case of Eq. (56). For any higher frequency $\mathit{k}\text{'}=2^{\mathit{k}}$, Eq. (56) holds. Hence, given $\mathit{k}$ is the lowest frequency at which ${\mathit{x}}_{{\mathit{n}}^{\text{'}}}$ and ${\mathit{x}}_{\mathit{n}}$ occur with opposite signs, for all larger frequencies $\mathit{k}\text{'}=2^{\mathit{k}},$${\mathit{x}}_{{\mathit{n}}^{\text{'}}}$ and ${\mathit{x}}_{\mathit{n}}$ occur with similar signs. For $\mathit{N}=8,{\mathit{Y}}_1^{\left(0\right)}={\mathit{x}}_0-{\mathit{x}}_4,{\mathit{Y}}_2^{\left(0\right)}={\mathit{x}}_0-{\mathit{x}}_2+{\mathit{x}}_4-{\mathit{x}}_6$ and ${\mathit{Y}}_4^{\left(0\right)}={\mathit{x}}_0-{\mathit{x}}_1+{\mathit{x}}_2-{\mathit{x}}_3+{\mathit{x}}_4-{\mathit{x}}_5+{\mathit{x}}_6-{\mathit{x}}_7$. Data elements ${\mathit{x}}_4$ and ${\mathit{x}}_0$ occur with opposite signs in ${\mathit{Y}}_1^{\left(0\right)}$ and similar signs in higher frequencies, $\mathit{k}=2,\mathit{k}=4$. Conversely, another conclusion is that elements ${\mathit{x}}_{{\mathit{n}}^{\text{'}}}$ and ${\mathit{x}}_{\mathit{n}}$ that co-occur with same signs in a UMRT coefficient having frequency $\mathit{k}\text{'}$ also co-occur with opposite signs in a UMRT coefficient having frequency $\mathit{k}$ where $\mathit{k}\text{'}=2^{\mathit{k}}$.

Given $\mathit{k}$ is the lowest frequency where ${\mathit{x}}_{{\mathit{n}}^{\text{'}}}$ and ${\mathit{x}}_{\mathit{n}}$ co-occur with an opposite sign, the factor of multiplication for ${\mathit{x}}_{{\mathit{n}}^{\text{'}}}$ in the inverse transform formula is $-\frac{1}{2\mathit{k}}$. In the case of higher frequencies till $\mathit{M}$, the factor of multiplication is $\frac{1}{2\mathit{k}\text{'}},\mathit{k}\text{'}=2\mathit{k},4\mathit{k},\dots \mathit{M}$. Thus the sum of the series

$$\mathit{f}=\frac{1}{\mathit{N}}-\frac{1}{2\mathit{k}}+\frac{1}{4\mathit{k}}+\frac{1}{8\mathit{k}}+\dots \frac{1}{2\mathit{M}}$$E57

will provide the value of the multiplication factor $\mathit{f}$ associated with element ${\mathit{x}}_{{\mathit{n}}^{\text{'}}}$.

Assume $\mathit{k}=\frac{\mathit{N}}{\mathit{q}}$. First the sum of the following series can be found:

$$\begin{array}{l}\frac{1}{4\mathit{k}}+\frac{1}{8\mathit{k}}+\dots \frac{1}{2\mathit{M}}={\mathit{f}}_{\mathit{a}}\\ {\mathit{f}}_{\mathit{a}}=\sum _{\mathit{j}={log}_2\frac{2\mathit{N}}{\mathit{q}}}^{{log}_2\mathit{M}}\frac{1}{2^{\mathit{j}+1}}\end{array}$$

The number of terms in this summation is ${log}_2\left(\mathit{q}\right)-1$.

$${\mathit{f}}_{\mathit{a}}=\frac{\mathit{q}}{4\mathit{N}}\frac{1-2^{-\left({log}_2\left(\mathit{q}\right)-1\right)}}{\frac{1}{2}}=\frac{\mathit{q}}{2\mathit{N}}\frac{\mathit{q}-2}{\mathit{q}}=\frac{\mathit{q}-2}{2\mathit{N}}$$

From Eq. (57),

$$\mathit{f}=\frac{1}{\mathit{N}}-\frac{1}{2\mathit{k}}+{\mathit{f}}_{\mathit{a}}=\frac{1}{\mathit{N}}-\frac{1}{2\mathit{k}}+\frac{\mathit{q}-2}{2\mathit{N}}=\frac{\mathit{q}}{2\mathit{N}}-\frac{1}{2\mathit{k}}=0$$

Thus, all the other data elements ${\mathit{x}}_{{\mathit{n}}^{\text{'}}}$ that occur along with ${\mathit{x}}_{\mathit{n}}$ in the various MRT coefficients in the summation of the inverse formula cancel out, leaving behind only the desired data element ${\mathit{x}}_{\mathit{n}}$.

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

$${\mathit{x}}_{\mathit{n}}=\frac{1}{\mathit{k}\text{'}}{\mathit{Y}}_{\mathit{k}{\text{'}}_{\left({\left(\mathit{nk}\text{'}\right)}_{\mathit{N}}\right)}}^{}+\sum _{\mathit{t}=0}^{{log}_2\mathit{k}\text{'}-1}\frac{1}{2^{\mathit{t}+1}}{\mathit{Y}}_{2^{\mathit{t}}}^{\left({\left(2^{\mathit{t}}\mathit{n}\right)}_{\mathit{N}}\right)}$$E58

where $\mathit{k}\text{'}$ is the highest frequency index that is a power of 2 and also a divisor of $\mathit{N}$.

Proof.${\mathit{x}}_{\mathit{n}}$ has to be obtained from the UMRT. Given ${\mathit{Y}}_{\mathit{k}}^{\left(\mathit{p}\right)}$ data element ${\mathit{x}}_{\mathit{n}}$ has to satisfy ${\left(\left(\mathit{nk}\right)\right)}_{\mathit{N}}=\mathit{p}$. For $\mathit{k}=2^{\mathit{a}}$, the UMRT coefficient ${\mathit{Y}}_{2^{\mathit{a}}}^{\left({\left(2^{\mathit{a}}\mathit{n}\right)}_{\mathit{N}}\right)}$ contains ${\mathit{x}}_{\mathit{n}}$. The UMRT coefficient ${\mathit{Y}}_{\mathit{k}{\text{'}}_{\left({\left(\mathit{nk}\text{'}\right)}_{\mathit{N}}\right)}}^{}$ is multiplied by $\frac{1}{\mathit{k}\text{'}}$, and the other UMRT coefficients are multiplied by $\frac{1}{2^{\mathit{t}+1}}$. The resultant factor f that multiplies ${\mathit{x}}_{\mathit{n}}$ 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 ${\mathit{x}}_{\mathit{n}}$ cancel out in the summation, leaving behind only the desired data element ${\mathit{x}}_{\mathit{n}}$. 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 $\mathit{N}$. Hence, the following equation can be used for signal reconstruction from UMRT, for a signal of size $\mathit{N},\mathit{N}$ being any even number.

$${\mathit{x}}_{\mathit{n}}=\frac{1}{\mathit{k}\text{'}}{\mathit{Y}}_{{{\left(\mathit{k}\text{'}\right)}_{\mathit{N}}}_{\left({\left(\mathit{nk}\text{'}\right)}_{\mathit{N}}\right)}}^{}+\sum _{\mathit{t}=0}^{{log}_2\mathit{k}\text{'}-1}\frac{1}{2^{\mathit{t}+1}}{\mathit{Y}}_{2^{\mathit{t}}}^{\left({\left(2^{\mathit{t}}\mathit{n}\right)}_{\mathit{N}}\right)}$$E59

where $\mathit{k}\text{'}$ is the highest power of 2 divisor of $\mathit{N}$.

For $\mathit{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 $\mathit{p}$ of an MRT coefficient into an index $\mathit{q}$ as follows:

$$\begin{array}{l}{\mathit{H}}_0\left(\mathit{m}\right)={\mathit{H}}_{0,0}\left(\mathit{m}\right)=1\\ 1,{〚\mathit{nk}〛}_{\mathit{N}}=\mathit{p}\end{array}$$

$$\begin{array}{l}{\mathit{H}}_{\mathit{q}}\left(\mathit{m}\right)={\mathit{H}}_{\mathit{k},\mathit{p}}\left(\mathit{m}\right)=\{-1,{〚\mathit{nk}〛}_{\mathit{N}}=\mathit{p}+\frac{\mathit{N}}{2}\\ 0,\mathit{\text{otherwise}}\\ \mathit{q}=2^{\mathit{k}}+\mathit{p}-1\\ \mathit{m}=0,1,\dots ,\mathit{N}-1\end{array}$$

This structure of the UMRT definition has a similar form as that of the Haar transforms [10]. Table 3 shows the mapping for $\mathit{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 $\mathit{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.