# Properties of Carry Value Transformation

Authors: Suryakanta Pal; Sudhakar Sahoo; Birendra Kumar Nayak
Journal: International Journal of Mathematics and Mathematical Sciences
 (2012)

---

## Abstract

Carry Value Transformation (CVT) is a model of discrete deterministic dynamical system. In the present study, it has been proved that (1) the sum of any two nonnegative integers is the same as the sum of their CVT and XOR values. (2) the number of iterations leading to eitherCVT=0 or XOR=0 does not exceed the maximum of the lengths of the two addenda expressed as binary strings. A similar process of addition of modified Carry Value Transformation (MCVT) and XOR requires a maximum of two iterations for MCVT to be zero. (3) an equivalence relation is shown to exist on Z×Z which divides the CV table into disjoint equivalence classes.


---

## Body

## 1. Introduction

The notion of transformation is very important in mathematics. Accordingly, in the literature, one finds many kinds of transformations with interesting properties. Carry Value Transformations (CVTs) and Modified Carry Value Transformations (MCVTs) are two challenging transformations which currently have assumed much significance because of their applications in fractal formation [1], designing new hardware circuits for arithmetic operations [2], and so forth. Similar kind of transformations such as Extreme Value Transformation (EVT) [3], 2-Variable Boolean Operation (2-VBO) [4], Integral Value Transformation (IVT) [5] are also used to manipulate strings of bits and applicable in pattern formations [3, 4], solving Round Rabin Tournaments problem [6], Collatz-like functions [5], and so forth. All these applications in diversified domain motivated us to study the mathematical properties of these kinds of transformations.The hardware circuit for arithmetic operations as designed in [2] is based on a result that after finite number of iterations, either CVT of the two nonnegative integers is equal to 0 or their XOR value is equal to 0. But no mathematical proof regarding this result was discussed in [2]. This important result has been proved in this paper. Section 2 provides the basic concepts of CVT, MCVT, and XOR earlier defined in [1, 2]. In Section 3, it is proved that addition of any two nonnegative integers expressed as binary numbers is the same as addition of their CVT and their XOR values. This result is also shown to be true for any base of the number system. In Section 4, it is proved that in a successive addition of CVT and XOR of any two nonnegative integers, the maximum number of iterations required to get either CVT = 0 or XOR = 0 is equal to the length of the bigger integer expressed as a binary string. Further, in the same section, it is shown that MCVT of any two nonnegative integers = 0 requires a maximum of two iterations. In Section 5, an equivalence relation is defined using the concept of CVT, and the equivalence classes obtained due to it are presented.


## 2. Definitions of CVT and MCVT in Binary Number System

Let “a” and “b” be decimal representations of the binary strings (an,an-1,…,a1)2 and (bn,bn-1,…,b1)2, respectively, where each  ai,bi∈B2={0,1} for all i=1,2,…,n  and  B2n  be the set of all possible binary strings of length n on the set B2. In binary number system, CVT as discussed in [1] is a mapping CVT:B2n×B2n→B2n×{0} defined by CVT(a,b)=(an∧bn,an-1∧bn-1,…,a1∧b1,0)2, whereas MCVT in [1] is a mapping  MCVT:B2n×B2n→B2n defined by MCVT(a,b)=(an∧bn,an-1∧bn-1,…,a1∧b1)2. That is, to find out CVT, we perform the bit wise XOR operation of the operands to get a string of sum-bits (ignoring the carry-in while performing the addition of a and b) and simultaneously the bit wise ANDing of the operands to get a string of carry-bits, the latter string is padded with a “0” on the right is called the CVT of these operands as shown in Figure 1, and MCVT is only the ANDing values except the bit “0” padded on the right, and thus the relation between these two operation is CVT(a,b)=2×MCVT(a,b).Figure 1
Carry generated inith column counted from LSB is saved in (i+1)th column.For example, suppose we want to find out the CVT of two numbers say 23 and 27. First of all, we have to find out the binary representation of these numbers, that is,(23)10≡(10111)2 and (27)10≡(11011)2.The carry value is computed as in Figure2.Figure 2
Carry generated inith column is saved in (i+1)th column for i=0,1,2,…,n.Thus,CVT(23,27)=CVT(10111,11011)=(1∧1,0∧1,1∧0,1∧1,1∧1,0)2(100110)2=(38)10, and MCVT(23,27)=(19)10.  It may be noted that in any number system, CVT and MCVT are mapping from Z×Z to Z, where  Z is set of nonnegative integers.


### 2.1. Extensions of CVT, MCVT, and XOR Operations for Arbitrary Number System

For any number system in baseβ, CVT of any two nonnegative integers a=(an,an-1,…,a1)β and  b=(bn,bn-1,…,b1)β  is defined by an integer c=(cncn-1···c10)β, where ci={1,ifai+bi≥β0,ifai+bi<β for i=1,2,3,…,n.  Similarly, MCVT of a and b in base β is the CVT value c=(c1c2⋯cn)β except the padding bit 0 in the least significant bit position. That is CVT(a,b)=β×MCVT(a,b) and the definition of  XOR operation in binary number system can be extended for any number system in base β as a⊕b=((an+bn)modβ,(an-1+bn-1)modβ,…,(a1+b1)modβ), where +  is the usual addition in decimal number system.For example, in ternary number system,CVT(466,458)=CVT(122021,121222)=(110110)3=336, MCVT(466,458)=MCVT(122021,121222)=(11011)3=112, XOR(466,458)=XOR(122021,121222)=(210210)3=588.


## 2.1. Extensions of CVT, MCVT, and XOR Operations for Arbitrary Number System

For any number system in baseβ, CVT of any two nonnegative integers a=(an,an-1,…,a1)β and  b=(bn,bn-1,…,b1)β  is defined by an integer c=(cncn-1···c10)β, where ci={1,ifai+bi≥β0,ifai+bi<β for i=1,2,3,…,n.  Similarly, MCVT of a and b in base β is the CVT value c=(c1c2⋯cn)β except the padding bit 0 in the least significant bit position. That is CVT(a,b)=β×MCVT(a,b) and the definition of  XOR operation in binary number system can be extended for any number system in base β as a⊕b=((an+bn)modβ,(an-1+bn-1)modβ,…,(a1+b1)modβ), where +  is the usual addition in decimal number system.For example, in ternary number system,CVT(466,458)=CVT(122021,121222)=(110110)3=336, MCVT(466,458)=MCVT(122021,121222)=(11011)3=112, XOR(466,458)=XOR(122021,121222)=(210210)3=588.


## 3. Properties of CVT and XOR

We have observed in the last example thatCVT(23,27)=38 and XOR(23,27)=12. Now 23+27=38+12, that is, 23+27=CVT(23,27)+(23⊕27). In general, we prove the following.Theorem 3.1.
a+b=CVT(a,b)+(a⊕b),  where a and b are any two nonnegative integers.Proof.
Supposea=anan-1···ak-1akak+1···a2a1 and  b=bnbn-1···bk-1bkbk+1···b2b1 are the binary representations of a and b both expressed using n bits. Then, CVT(a,b)=cncn-1cn-2···c10 for i=1,2,…,n. We will prove that sum of the contribution of ak and  bk in a+b is the same as the sum of the contribution of ck and ak⊕bk in CVT(a,b)+(a⊕b),  where k=1,2,3,…,n. The place values of ak and bk in a and b are ak×2k-1 and  bk×2k-1, respectively. So the total contributions of both  ak and  bk in  a+bis (ak+bk)2k-1. The binary variable ak and bk can have four choices, and their place values are shown in Table 1.
From third column and seventh column, it can be verified that the total contribution ofak and bk in a+b is the same as the sum of the contribution of ck and ak⊕bk in CVT(a,b)+(a⊕b) for k=1,2,…,n. Therefore, a+b=CVT(a,b)+(a⊕b).Table 1
Shows the contributions in calculating the sum in different cases.
akbkSum of contributions ofak and bk in a+bck=ak∧bkContribution ofck in CVT(a,b)Contribution ofak⊕bk in (a⊕b)Sum of contributions ofck and ak⊕bk in CVT(a,b)+(a⊕b)012k-1002k-12k-1102k-1002k-12k-10000000112k12k02k(A) General Proof for an Arbitrary Number System
Leta=∑k=1nak×βk-1 and b=∑k=1nbk×βk-1 be two numbers from a number system with base β, and let CVT(a,b) = cncn-1···c10. We will prove that sum of the contribution of ak and bk  in a+b is the same as the sum of the contribution of ck and ak⊕bk in CVT(a,b)+(a⊕b) for k=1,2,3,…,n.
Note that the individual place values ofak and bk in a and b are ak×βk-1 and bk×βk-1, respectively. So the total contributions for both ak and bk in a+b is (ak+bk)βk-1. Two cases arise: case 1,ak+bk<β and case 2,ak+bk≥β. In both cases, the contributions from ak and bk in a+b remain (ak+bk)βk-1, whereas in a⊕b they differ; for the first case it is (ak+bk)βk-1 and for the second case it is (ak+bk)βk-1-βk. The value of ck is zero in the first case, whereas in the second case it is 1 so that the respective contributions of ck in CVT(a,b) are 0 and βk. It can be summarised in a table as shown in Table 2.
From third column and last column of Table2, it can be seen that sum of the contribution of ak and bk in a+b is the same as the sum of the contribution of ck and ak⊕bk in CVT(a,b)+(a⊕b) for k=1,2,3,…,n.  Therefore, a+b=CVT(a,b)+(a⊕b).Table 2
Shows the contributions in calculating the sum for two possible cases.
CasesConditionsSum of contributions ofak and  bk in a+bckContribution ofck in CVT(a,b)Contribution ofak⊕bk  in (a⊕b)Sum of contributions ofck and ak⊕bk in CVT(a,b)+(a⊕b)Case 1ak+bk<β(ak+bk)βk-100(ak+bk)βk-1(ak+bk)βk-1Case 2ak+bk≥β(ak+bk)βk-11βk(ak+bk)βk-1-βk(ak+bk)βk-1


## 4. Convergence Behavior of CVT and MCVT

### 4.1. Convergence of  CVT

Letf:Z×Z→Z×Z be defined as f(a,b)=(CVT(a,b),(a⊕b)) for all (a,b)∈Z×Z. Consider the iterative scheme  (xn+1,yn+1)=f(xn,yn), n=0,1,2,3,….  In this section, we will prove an important theorem which states that the sequence generated by the iterative scheme (xn+1,yn+1)=f(xn,yn), n=0,1,2,3,… converges to (0,x0+y0). The convergence behavior of CVT and XOR values of different order pairs are shown in Table 3.Table 3
Generated sequences of CVT and XOR values.
Initial guess (x0,y0)Generated sequences(xn+1,yn+1)(1,8)(0,9)(12,10)(16,6),(0,22)(17,11)(2,26),(4,24),(0,28)(1,23)(2,22),(4,20),(8,16),(0,24)(1,15)(2,14),(4,12),(8,8),(16,0),(0,16)(27,5)(2,30),(4,28),(8,24),(16,16),(32,0),(0,32)(127,65)(130,62),(4,188),(8,184),(16,176),(32,160),(64,128),(0,192)The sequences generated from the ordered pair(127,65) in Table 3 may be interpreted as 127 + 65 = 130 + 62 = 4 + 188 = 8 + 184 = 16 + 176 = 32 + 160 = 64 + 128 = 0 + 192. These generated sequences are named as the orbit of the order pair (127,65). Figure 3 shows the state transition diagrams (STDs) of some of the points and their orbits.Figure 3
Showing the state transition diagrams (STDs) of three order pairs(1,23),(1,15), and (17,11) as shown in Table 3.Observations:(1)
in any number system, CVT = 0 in any iteration⇔ in its previous iteration the sum of the corresponding bits of CVT and XOR is always less than the base of that number system;(2)
if two numbers expressed in binary are complement to each other, then their CVT = 0. But the converse is not true;(3)
if XOR value is 0 in any iteration, then CVT = 0 in the next iteration;(4)
the points in a single orbit are collinear as shown in Figure3.According to the definition of CVT for any twon-bit numbers, CVT will be of at most (n+1) bits.  It seems that the recursive procedure of the CVT + XOR of two nonnegative integers always increases the length of the CVT by 1 in each iteration but it is not true, which is clear from the next proof.Lemma 4.1.
If the maximum length of two nonnegative integers in binary representation is n then the CVT and XOR values in each iteration expressed in binary strings must be of length at most (n+1).Proof.
Leta and b be two nonnegative integers with length at most n in their binary representations. Let c and d be two numbers to be added in kth iteration while performing the repeated sum of CVT and XOR. Suppose the number of (valid) bits in CVT(c,d)≥n+2 (rejecting the zeros in the left of the first nonzero bit) in an iteration. The smallest number with valid (n+2) bits is 100···0=1×2n+1=2n+1.  So, CVT(c,d)≥2n+1⇒CVT(c,d)+(c⊕d)≥2n+1.
SinceCVT(c,d)+(c⊕d)=c+d (from Theorem 3.1), c+d≥2n+1. Since c+d=a+b, so
(4.1)a+b≥2n+1.
The maximum number withn+2 bits is 111···11 = 1×2n-1+1×2n-2+···+1×21+1×20=1+2+4+8+···+2n-2+2n-1.
Maximum value ofa+b is 2(1+2+4+···+2n-2+2n-1)=2(2n-1)/(2-1)=2n+1-2:
(4.2)⇒a+b≤2n+1-2.
From (4.1) and (4.2), we get 2n+1≤a+b≤2n+1-2 which is absurd. Thus, our assumption was wrong, and hence all CVTs will be of at most (n+1) bits in every iteration.
Same logic can be applied to XOR operation also, that is, if we write CVT in place of XOR in above proof, we also get an absurd result for XOR. Therefore, all XOR operations are of at most(n+1) bits in every iteration.Lemma 4.2.
In any iteration if there is a “0” in CVT atkth position (counted from right), then there must be a “0” in (k+1)th position in the next iteration while forming the subsequent CVTs. The number of zeros in the CVT increases by at least one in each iteration.Proof.
Suppose a CVT contains 0 atkth position in any iteration. In the next iteration, this 0 will be added to either 0 or 1 of XOR value obtained in the previous iteration. When we form CVT, (k+1)th position of CVT will be either 0∧1=0 or 0∧0=0. Thus, we get a 0 in the (k+1)th position of the newly formed CVT. Thus, once a “0” appears in a CVT in any iteration, then “0” appears in all subsequent CVT’s in all subsequent iterations, but the position will be shifted by one in each iteration. By definition of CVT, one additional zero is added to the rightmost position in each iteration. So number of zero increases by at least one in a CVT in each iteration.Lemma 4.3.
If a and b are of maximum n binary bits, then the number of iterations required to getCVT=0 is at most (n+1).Proof.
By Lemma4.1, all CVTs will be of at most (n+1) bits in all iterations.
By Lemma4.2, once a “0” appears in a CVT in any iteration, then this zero will appear in all the subsequent CVT’s in all subsequent iterations, but the position will be shifted by one in each iteration.
Also the number of zero in CVT increases by at least one in each iteration, the(n+1) bits in CVT will be converted to (n+1) zeros in at most (n+1)-iterations.Note.
Ifa and b are of maximum n binary bits and Hamming distance between a and b is n, then CVT=0 in one iteration. Otherwise, if Hamming distance between two selected numbers is k for k<n, then number of iterations required to get CVT=0 is at most (k+2).Lemma 4.4.
If a and b are of maximum n binary digits andCVT=0 in (n+1)th iteration, then XOR=0 in the nth iteration.Proof.
Let us assume thatCVT=0 in the (n+1)th iteration and suppose XOR≠0 in the nth iteration. Then at least, one bit of the XOR in nth iteration must be “1”. It is sure that in the kth iteration (where k=1,2,3,… or (n-1)) of successive addition, XOR bit must be 1, and the corresponding carry bit must be 1 which is impossible. So our assumption was wrong. Thus, XOR=0 in the nth iteration. Hence proved.Combining Lemmas4.3 and 4.4, we have proved the following theorem.Theorem 4.5.
Letf:Z×Z→Z×Z be defined as f(a,b)=(CVT(a,b),(a⊕b)). Then, the iterative scheme (xn+1,yn+1)=f(xn,yn), n=0,1,2,3,… converges to (0,x0+y0) for any initial choice (x0,y0)∈Z×Z. Further, for any nonnegative integers “x0” and “y0” (where x0≥y0), the number of iterations required to get either CVT=0 or XOR=0 is at most the length of “x0” when expressed as a binary string.


### 4.2. Convergence of  MCVT

The following theorem gives the number of iterations required forMCVT=0.Theorem 4.6.
The procedure of calculating the MCVT and XOR values of any two nonnegative integers requires a maximum of two iterations to get theirMCVT=0.Proof.
Leta=anan-1···a1  and  b=bnbn-1···b1 be two n-bits number. In the first iteration, we get MCVT(a,b) and a⊕b.
Letx=MCVT(a,b)=(an∧bn,an-1∧bn-1,…,a1∧b1)and y=a⊕b=(an⊕bn,an-1⊕bn-1,…,a1⊕b1).  Then in the second iteration, we get MCVT(x,y) and (x⊕y). We will show that MCVT(x,y)=0.
From Table4, it can be verified that:
(4.3)MCVT(x,y)=((an∧bn)∧(an⊕bn),(an-1∧bn-1)∧(an-1⊕bn-1),…,(a1∧b1)∧(a1⊕b1))=(0,0,0,0,…,0)=0.
Ifai∧bi≠1 for all i, then MCVT(a,b)=0 in one iteration. Hence proved.Table 4
Showing calculation of MCVT.
aibiai∧biai⊕bi(ai∧bi)∧(ai⊕bi)11100100100101000000


## 4.1. Convergence of  CVT

Letf:Z×Z→Z×Z be defined as f(a,b)=(CVT(a,b),(a⊕b)) for all (a,b)∈Z×Z. Consider the iterative scheme  (xn+1,yn+1)=f(xn,yn), n=0,1,2,3,….  In this section, we will prove an important theorem which states that the sequence generated by the iterative scheme (xn+1,yn+1)=f(xn,yn), n=0,1,2,3,… converges to (0,x0+y0). The convergence behavior of CVT and XOR values of different order pairs are shown in Table 3.Table 3
Generated sequences of CVT and XOR values.
Initial guess (x0,y0)Generated sequences(xn+1,yn+1)(1,8)(0,9)(12,10)(16,6),(0,22)(17,11)(2,26),(4,24),(0,28)(1,23)(2,22),(4,20),(8,16),(0,24)(1,15)(2,14),(4,12),(8,8),(16,0),(0,16)(27,5)(2,30),(4,28),(8,24),(16,16),(32,0),(0,32)(127,65)(130,62),(4,188),(8,184),(16,176),(32,160),(64,128),(0,192)The sequences generated from the ordered pair(127,65) in Table 3 may be interpreted as 127 + 65 = 130 + 62 = 4 + 188 = 8 + 184 = 16 + 176 = 32 + 160 = 64 + 128 = 0 + 192. These generated sequences are named as the orbit of the order pair (127,65). Figure 3 shows the state transition diagrams (STDs) of some of the points and their orbits.Figure 3
Showing the state transition diagrams (STDs) of three order pairs(1,23),(1,15), and (17,11) as shown in Table 3.Observations:(1)
in any number system, CVT = 0 in any iteration⇔ in its previous iteration the sum of the corresponding bits of CVT and XOR is always less than the base of that number system;(2)
if two numbers expressed in binary are complement to each other, then their CVT = 0. But the converse is not true;(3)
if XOR value is 0 in any iteration, then CVT = 0 in the next iteration;(4)
the points in a single orbit are collinear as shown in Figure3.According to the definition of CVT for any twon-bit numbers, CVT will be of at most (n+1) bits.  It seems that the recursive procedure of the CVT + XOR of two nonnegative integers always increases the length of the CVT by 1 in each iteration but it is not true, which is clear from the next proof.Lemma 4.1.
If the maximum length of two nonnegative integers in binary representation is n then the CVT and XOR values in each iteration expressed in binary strings must be of length at most (n+1).Proof.
Leta and b be two nonnegative integers with length at most n in their binary representations. Let c and d be two numbers to be added in kth iteration while performing the repeated sum of CVT and XOR. Suppose the number of (valid) bits in CVT(c,d)≥n+2 (rejecting the zeros in the left of the first nonzero bit) in an iteration. The smallest number with valid (n+2) bits is 100···0=1×2n+1=2n+1.  So, CVT(c,d)≥2n+1⇒CVT(c,d)+(c⊕d)≥2n+1.
SinceCVT(c,d)+(c⊕d)=c+d (from Theorem 3.1), c+d≥2n+1. Since c+d=a+b, so
(4.1)a+b≥2n+1.
The maximum number withn+2 bits is 111···11 = 1×2n-1+1×2n-2+···+1×21+1×20=1+2+4+8+···+2n-2+2n-1.
Maximum value ofa+b is 2(1+2+4+···+2n-2+2n-1)=2(2n-1)/(2-1)=2n+1-2:
(4.2)⇒a+b≤2n+1-2.
From (4.1) and (4.2), we get 2n+1≤a+b≤2n+1-2 which is absurd. Thus, our assumption was wrong, and hence all CVTs will be of at most (n+1) bits in every iteration.
Same logic can be applied to XOR operation also, that is, if we write CVT in place of XOR in above proof, we also get an absurd result for XOR. Therefore, all XOR operations are of at most(n+1) bits in every iteration.Lemma 4.2.
In any iteration if there is a “0” in CVT atkth position (counted from right), then there must be a “0” in (k+1)th position in the next iteration while forming the subsequent CVTs. The number of zeros in the CVT increases by at least one in each iteration.Proof.
Suppose a CVT contains 0 atkth position in any iteration. In the next iteration, this 0 will be added to either 0 or 1 of XOR value obtained in the previous iteration. When we form CVT, (k+1)th position of CVT will be either 0∧1=0 or 0∧0=0. Thus, we get a 0 in the (k+1)th position of the newly formed CVT. Thus, once a “0” appears in a CVT in any iteration, then “0” appears in all subsequent CVT’s in all subsequent iterations, but the position will be shifted by one in each iteration. By definition of CVT, one additional zero is added to the rightmost position in each iteration. So number of zero increases by at least one in a CVT in each iteration.Lemma 4.3.
If a and b are of maximum n binary bits, then the number of iterations required to getCVT=0 is at most (n+1).Proof.
By Lemma4.1, all CVTs will be of at most (n+1) bits in all iterations.
By Lemma4.2, once a “0” appears in a CVT in any iteration, then this zero will appear in all the subsequent CVT’s in all subsequent iterations, but the position will be shifted by one in each iteration.
Also the number of zero in CVT increases by at least one in each iteration, the(n+1) bits in CVT will be converted to (n+1) zeros in at most (n+1)-iterations.Note.
Ifa and b are of maximum n binary bits and Hamming distance between a and b is n, then CVT=0 in one iteration. Otherwise, if Hamming distance between two selected numbers is k for k<n, then number of iterations required to get CVT=0 is at most (k+2).Lemma 4.4.
If a and b are of maximum n binary digits andCVT=0 in (n+1)th iteration, then XOR=0 in the nth iteration.Proof.
Let us assume thatCVT=0 in the (n+1)th iteration and suppose XOR≠0 in the nth iteration. Then at least, one bit of the XOR in nth iteration must be “1”. It is sure that in the kth iteration (where k=1,2,3,… or (n-1)) of successive addition, XOR bit must be 1, and the corresponding carry bit must be 1 which is impossible. So our assumption was wrong. Thus, XOR=0 in the nth iteration. Hence proved.Combining Lemmas4.3 and 4.4, we have proved the following theorem.Theorem 4.5.
Letf:Z×Z→Z×Z be defined as f(a,b)=(CVT(a,b),(a⊕b)). Then, the iterative scheme (xn+1,yn+1)=f(xn,yn), n=0,1,2,3,… converges to (0,x0+y0) for any initial choice (x0,y0)∈Z×Z. Further, for any nonnegative integers “x0” and “y0” (where x0≥y0), the number of iterations required to get either CVT=0 or XOR=0 is at most the length of “x0” when expressed as a binary string.


## 4.2. Convergence of  MCVT

The following theorem gives the number of iterations required forMCVT=0.Theorem 4.6.
The procedure of calculating the MCVT and XOR values of any two nonnegative integers requires a maximum of two iterations to get theirMCVT=0.Proof.
Leta=anan-1···a1  and  b=bnbn-1···b1 be two n-bits number. In the first iteration, we get MCVT(a,b) and a⊕b.
Letx=MCVT(a,b)=(an∧bn,an-1∧bn-1,…,a1∧b1)and y=a⊕b=(an⊕bn,an-1⊕bn-1,…,a1⊕b1).  Then in the second iteration, we get MCVT(x,y) and (x⊕y). We will show that MCVT(x,y)=0.
From Table4, it can be verified that:
(4.3)MCVT(x,y)=((an∧bn)∧(an⊕bn),(an-1∧bn-1)∧(an-1⊕bn-1),…,(a1∧b1)∧(a1⊕b1))=(0,0,0,0,…,0)=0.
Ifai∧bi≠1 for all i, then MCVT(a,b)=0 in one iteration. Hence proved.Table 4
Showing calculation of MCVT.
aibiai∧biai⊕bi(ai∧bi)∧(ai⊕bi)11100100100101000000


## 5. An Equivalence Relation is Defined Using the Notion of CVT

LetA={0,1,2,3,…,2n-1} be a finite subset of  Z  for some nonnegative integer n, and let R  be a relation on A×A defined as (a,b)R(c,d)⇔(a,b) and (c,d) requiring equal number of iterations for their CVT=0 or XOR=0.It can be easily verified that the relationR is reflexive, symmetric, and transitive on the set A×A. Therefore, R is an equivalence relation on A×A.We have calculated the number of iterations required for the set of ordered pair inA×A, where A={0,1,2,…,31} and constructed Figure 4 using a two-step procedure as follows.Figure 4
Showing the number of iterations required for eitherCVT=0 or  XOR=0.Step 1.
Write all the integers0,1,2,3,…,31 in ascending order in both, uppermost row and leftmost column of Figure 4.Step 2.
Compute number of iterations required for any ordered pair(a,b) to get either CVT=0 or  XOR=0 and store it in the position (a,b).From Figure4, we have observed that:(1)
the matrix is symmetric;(2)
if we consider Figure4 as 4 quadrants, each quadrant is a symmetric matrix. Again if each quadrant is divided further into 4 smaller quadrants, then also the 1st quadrant is the same as the 3rd quadrant. Hence a self-similar fractal behaviour is noticed in Figure 4;(3)
in a block of size(2n-1)×(2n-1), there are no ordered pairs in the 2nd quadrant which transform into CVT=0 or XOR=0 in n-iterations.In Figure4R divides the set {0,1,2,3,…,2n-1}×{0,1,2,3,…,2n-1} into n disjoint equivalence classes.Forn=1, there is one equivalence class [(0,0)]={(0,0),(0,1),(1,0),(1,1)} and |[0,0]|=4.Forn=2, there are two equivalence classes [(0,0)],[(1,3)], where(5.1)[(0,0)]={(0,0),(0,1),(0,2),(0,3),(1,0),(1,1),(1,2),(2,0),(2,1),(2,2),(3,0),(3,3)},(5.2)[(1,3)]={(1,3),(2,3),(3,1),(3,2)}.
Here, |[0,0]|=12,|[1,3]|=4.Forn=3, there are three equivalence classes [(0,0)],[(1,3)], and [(1,7)]:(5.3)|[0,0]|=34,|[1,3]|=18,|[1,7]|=12.Forn=4, there are four equivalence classes [(0,0)],[(1,3)],[(1,7)], and [(1,15)]:(5.4)|[0,0]|=96,|[1,3]|=78,|[1,7]|=58,|[1,15]|=24.Forn=5, there are five equivalence classes [(0,0)],[(1,3)],[(1,7)],[(1,15)], and [(1,31)]:(5.5)|[0,0]|=274,|[1,3]|=306,|[1,7]|=263,|[1,15]|=133,|[(1,31)]|=48.From above, we conclude that if we take a block of size(2n-1)×(2n-1), then(1)
number of ordered pairs for whichCVT=0 or  XOR=0 in one iterations is 3n+(2n-1) for n=1,2,3,4,…;(2)
number of ordered pairs for whichCVT=0 or XOR=0 in n iterations is 3×2n-1 for n=3,4,5,….


## 6. Conclusion and Future Research Work

In the present paper, we have proved some important results on Carry Value Transformation (CVT) and Modified Carry Value Transformation (MCVT). Firstly, it has been proved that for any base of the number system, the sum of any two nonnegative integers is the same as the sum of their CVT and XOR values. This result is actually the correctness proof of the algorithm based on which the adder circuit is designed in [2]. Our second result, that is, “the number of iterations leading to either CVT=0 or XOR=0 does not exceed the maximum of the lengths of the two addenda expressed as binary strings” is about the efficiency at which the hardware circuit designed in [2] will produce the addition result. The state transition diagrams (STDs) and certain observations on CVT and MCVT are found out. Our third result such as addition of Modified Carry Value Transformation (MCVT) and XOR requires a maximum of two iterations for MCVT to be zero, is an interesting result for MCVT. A new equivalence relation is obtained on the set Z×Z which divides the CV Figure 4 into disjoint equivalence classes.In future we propose to study the following aspects:(1)
investigating into the state transition diagrams (STDs) of different IVTs;(2)
extending the domain of CVT from nonnegative integers to real numbers and complex numbers;(3)
exploring the behaviour of hybrid IVTs and their applications;(4)
explaining the relationship of IVTs with cellular automata.



---

*Source: 174372-2012-04-01.xml*