See discussions, stats, and author profiles for this publication at: [Link]

net/publication/321604609

A New Coding/Decoding Algorithm using Fibonacci Numbers

Article in Discrete Mathematics Algorithms and Applications · December 2017

DOI: 10.1142/S1793830918500283

CITATIONS READS
20 2,000

4 authors:

Nihal Tas Sümeyra Uçar

Balıkesir University Balıkesir University
92 PUBLICATIONS 1,271 CITATIONS 37 PUBLICATIONS 609 CITATIONS

SEE PROFILE SEE PROFILE

Nihal Özgür Öznur Öztunç Kaymak

İzmir Democracy University İzmir Democracy University
124 PUBLICATIONS 1,576 CITATIONS 17 PUBLICATIONS 69 CITATIONS

SEE PROFILE SEE PROFILE

All content following this page was uploaded by Nihal Tas on 14 December 2017.

The user has requested enhancement of the downloaded file.

 A NEW CODING/DECODING ALGORITHM USING
FIBONACCI NUMBERS

NİHAL TAŞ*, SÜMEYRA UÇAR, NİHAL YILMAZ ÖZGÜR,

arXiv:1712.02262v1 [[Link]] 1 Dec 2017

AND ÖZNUR ÖZTUNÇ KAYMAK

Abstract. In this paper we present a new method of coding/decoding al-

gorithms using Fibonacci Q-matrices. This method is based on the blocked
message matrices. The main advantage of our model is the encryption of each
message matrix with different keys. Our approach will not only increase the
security of information but also has high correct ability.

1. Introduction and Background

It is well known that the Fibonacci sequence is defined by
Fn = Fn−1 + Fn−2 with n ≥ 2, (1.1)
with the initial terms F0 = 0, F1 = 1. The Fibonacci Q-matrix is defined in [2]
and [3] as follows: !
1 1
Q= .
1 0
From [5] and [7], we known that the [Link] power of the Fibonacci Q-matrix is of
the following form: !
Fn+1 Fn
Qn = .
Fn Fn−1
In recent days information security becomes a more important matter in terms
of data transfer over communication channel. So coding/decoding algorithms
are of great importance to help in improving information security. Especially,
Fibonacci coding theory has been considered in many aspects (see [1], [4], [6],

2010 Mathematics Subject Classification. 68P30, 11B39.

Key words and phrases. Coding/decoding algorithm, Fibonacci Q-matrix.
*Corresponding author: N. TAŞ
Balıkesir University, Department of Mathematics, 10145 Balıkesir, TURKEY
e-mail: nihaltas@[Link].
1
2 N. TAŞ, S. UÇAR, N. YILMAZ ÖZGÜR, AND Ö. ÖZTUNÇ KAYMAK

[7], [8] and [9] for more details). For example, in [7], it was given a new coding
theory using the generalization of the Cassini formula for Fibonacci p-numbers
and Qp -matrices.
In this study we present a new coding/decoding algorithm using Fibonacci Q-
matrices. The main idea of our method depend on dividing the message matrix
into the block matrices of size 2×2. We use different numbered alphabet for each
message, so we get a more reliable coding method. The alphabet is determined
by the number of block matrices of the message matrix. Our approach will not
only increase the security of information but also has high correct ability for data
transfer over communication channel.

2. The Blocking Algorithm

At first, we put our message in a matrix of even size adding zero between two
words and end of the message until we obtain the size of the message matrix
is even. Dividing the message square matrix M of size 2m into the matrices,
named Bi (1 ≤ i ≤ m2 ) of size 2 × 2, from left to right, we construct a new
coding method.
Now we explain the symbols of our coding method. Assume that matrices Bi ,
Ei and Qn are of the following forms:

! ! !
bi1 bi2 ei1 ei2 q1 q2
Bi = , Ei = and Qn = .
bi3 bi4 ei3 ei4 q3 q4

The number of the block matrices Bi is denoted by b. According to b, we choose

the number n as follows:
(
3 , b≤3
n= .
b , b>3

Using the choosen n, we write the following letter table according to mod27 (this
table can be extended according to the used characters in the message matrix).
We begin the “n” for the first character.
 A NEW CODING/DECODING ALGORITHM USING FIBONACCI NUMBERS 3

A B C D E F G H I J
n n+1 n+2 n+3 n+4 n+5 n+6 n+7 n+8 n+9
K L M N O P Q R S T
n + 10 n + 11 n + 12 n + 13 n + 14 n + 15 n + 16 n + 17 n + 18 n + 19
U V W X Y Z 0
n + 20 n + 21 n + 22 n + 23 n + 24 n + 25 n + 26
Now we explain the following new coding and decoding algorithms.
Coding Algorithm (Fibonacci Blocking Algorithm)
Step 1. Divide the matrix M into blocks Bi (1 ≤ i ≤ m2 ).
Step 2. Choose n.
Step 3. Determine bij (1 ≤ j ≤ 4).
Step 4. Compute det(Bi ) → di .
Step 5. Construct F = [di , bik ]k∈{1,2,4} .
Step 6. End of algorithm.
Decoding Algorithm
Step 1. Compute Qn .
Step 2. Determine qj (1 ≤ j ≤ 4).
Step 3. Compute q1 bi1 + q3 bi2 → ei1 (1 ≤ i ≤ m2 ).
Step 4. Compute q2 bi1 + q4 bi2 → ei2 .
Step 5. Solve (−1)n di = ei1 (q2 xi + q4 bi4 ) − ei2 (q1 xi + q3 bi4 ).
Step 6. Substitute for xi = bi3 .
Step 7. Construct Bi .
Step 8. Construct M.
Step 9. End of algorithm.
In the following examples we give applications of the above algorithm for b > 3
and b ≤ 3, respectively.

Example 2.1. Let us consider the message matrix for the message text “NIHAL
HELLO”:  
N I H A
 L 0 H E 
M =  .
 
 L L O 0 
0 0 0 0 4×4
Coding Algorithm:
4 N. TAŞ, S. UÇAR, N. YILMAZ ÖZGÜR, AND Ö. ÖZTUNÇ KAYMAK

Step 1. We can divide the message matrix M of size 4 × 4 into the matrices,
named Bi (1 ≤ i ≤ 4), from left to right, each of size is 2 × 2 :
! ! ! !
N I H A L L O 0
B1 = , B2 = , B3 = and B4 = .
L 0 H E 0 0 0 0
Step 2. Since b = 4 ≥ 3, we choose n = 4. For n = 4, we use the following
“letter table” for the message matrix M :
N I H A L 0 H E L L O
.
17 12 11 4 15 3 11 8 15 15 18
Step 3. We have the elements of the blocks Bi (1 ≤ i ≤ 4) as follows:
b11 = 17 b12 = 12 b13 = 15 b14 =3
b21 = 11 b22 =4 b23 = 11 b24 =8
.
b31 = 15 b32 = 15 b33 =3 b34 =3
b41 = 18 b42 =3 b43 =3 b44 =3
Step 4. Now we calculate the determinants di of the blocks Bi :
d1 = det(B1 ) = −129
d2 = det(B2 ) = 44
.
d3 = det(B3 ) = 0
d4 = det(B4 ) = 45
Step 5. Using Step 3 and Step 4 we obtain the following matrix F :
 
−129 17 12 3
 44 11 4 8 
F = .
 
 0 15 15 3 
45 18 3 3
Step 6. End of algorithm.
Decoding algorithm:
Step 1. It is known that
!
4 5 3
Q = .
3 2

Step 2. The elements of Q4 are denoted by

q1 = 5, q2 = 3, q3 = 3 and q4 = 2.
 A NEW CODING/DECODING ALGORITHM USING FIBONACCI NUMBERS 5

Step 3. We compute the elements ei1 to construct the matrix Ei :

e11 = 121, e21 = 67, e31 = 120 and e41 = 99.

Step 4. We compute the elements ei2 to construct the matrix Ei :

e12 = 75, e22 = 41, e32 = 75 and e42 = 60.

Step 5. We calculate the elements xi :

(−1)4 (−129) = 121(3x1 + 6) − 75(5x1 + 9)

⇒ x1 = 15.

(−1)4 44 = 67(3x2 + 16) − 41(5x2 + 24)

⇒ x2 = 11.

(−1)4 0 = 120(3x3 + 6) − 75(5x3 + 9)

⇒ x3 = 3.

(−1)4 45 = 99(3x4 + 6) − 60(5x4 + 9)

⇒ x4 = 3.

Step 6. We rename xi as follows:

x1 = b13 = 15, x2 = b23 = 11, x3 = b33 = 3 and x4 = b43 = 3.

Step 7. We construct the block matrices Bi :

! ! ! !
17 12 11 4 15 15 18 3
B1 = , B2 = , B3 = and B4 = .
15 3 11 8 3 3 3 3

Step 8. We obtain the message matrix M :

   
17 12 11 4 N I H A
 15 3 11 8   L 0 H E 
M = = .
   
 15 15 18 3   L L O 0 
3 3 3 3 0 0 0 0

Step 9. End of algorithm.

6 N. TAŞ, S. UÇAR, N. YILMAZ ÖZGÜR, AND Ö. ÖZTUNÇ KAYMAK

Example 2.2. Let us consider the message matrix for the message text “MATH”:
!
M A
M= .
T H
2×2

Coding Algorithm:
Step 1. Since the size of message matrix M is 2 × 2, we have only one block
matrix B1 = M.
Step 2. Since b = 1 < 3, we choose n = 3. For n = 3, we use the following
“letter table” for the message matrix M :
M A T H
.
15 3 22 10
Step 3. We have the elements of the blocks B1 as follows:

b11 = 15 b12 = 3 b13 = 22 b14 = 10 .

Step 4. Now we calculate the determinant d1 of the block matrix B1 :

d1 = det(B1 ) = 84 .

Step 5. Using Step 3 and Step 4 we obtain the following matrix F :

 
F = 84 15 3 10 .

Step 6. End of algorithm.

Decoding algorithm:
Step 1. It is known that
!
3 2
Q3 = .
2 1

Step 2. The elements of Q3 are denoted by

q1 = 3, q2 = 2, q3 = 2 and q4 = 1.

Step 3. We compute the element e11 to construct the matrix E1 :

e11 = q1 b11 + q3 b12 = 51.

Step 4. We compute the element e12 to construct the matrix E1 :

e12 = q2 b11 + q4 b12 = 33.

 A NEW CODING/DECODING ALGORITHM USING FIBONACCI NUMBERS 7

Step 5. We calculate the element x1 :

(−1)3 (84) = 51(2x1 + 10) − 33(3x1 + 20)
⇒ x1 = 22.
Step 6. We rename x1 as follows:
x1 = b13 = 22.
Step 7. We construct the block matrix Bi :
!
15 3
B1 = .
22 10
Step 8. We obtain the message matrix M :
! !
15 3 M A
M= = .
22 10 T H
Step 9. End of algorithm.

3. A Computer Application
To determine the verification of our coding method, in this section we construct
a computer algorithm. We creat the MATLAB codes for the examples given in
the previous section. So our blocking algorithm is checked for n = 2 and n = 4
for different message texts, respectively. It can be seen that the algorithm works
errorless. Moreover, complex message texts are solved correctly thanks to these
algorithms. By a similar way, this algorithm can be extended for convenient
n. At first we define the Fibonacci numbers in the algorithm then we give the
following code segments for n = 2 (see Table 1).
The second algorithm seen in Table 2 provides more faster solution for complex
text. The readers can verify these algorithms for varied values of n.

4. Conclusion
The main idea of our method depends on dividing the message matrix into the
block matrices of size 2 × 2. We give an algorithm using Fibonacci numbers and
the numbers corresponding to each letter in used alphabet changes for each new
message matrix. We verify our new algorithm with illustrative examples. Also
our method is supported by a code in MATLAB programme for n = 2 and n = 4.
This algorithm can be improved for any n in the light of similar arguments.
8 N. TAŞ, S. UÇAR, N. YILMAZ ÖZGÜR, AND Ö. ÖZTUNÇ KAYMAK

References
[1] M. Basu, B. Prasad, The generalized relations among the code elements for Fibonacci coding
theory, Chaos Solitons Fractals 41 (2009), no. 5, 2517–2525.
[2] H. W. Gould, A history of the Fibonacci Q-matrix and a higher-dimensional problem,
Fibonacci Quart. 19 (1981), no. 3, 250–257.
[3] V. E. Hoggat, Fibonacci and Lucas Numbers, Houghton-Mifflin, Palo Alto (1969).
[4] S. Prajapat, A. Jain, R. S. Thakur, A Novel Approach For Information Security With
Automatic Variable Key Using Fibonacci Q-Matrix, IJCCT 3 (2012), no. 3, 54–57.
[5] A. P. Stakhov, A generalizition of the Fibonacci Q-matrix, Rep. Natl. Acad. Sci. Ukraine
9 (1999), 46-49.
[6] A. Stakhov, V. Massingue, A. Sluchenkov, Introduction into Fibonacci Coding and Cryp-
tography, Osnova, Kharkov (1999).
[7] A. P. Stakhov, Fibonacci matrices, a generalization of the Cassini formula and a new coding
theory, Chaos Solitons Fractals 30 (2006), no. 1, 56–66.
[8] B. S. Tarle, G. L. Prajapati, On the information security using Fibonacci series, Interna-
tional Conference and Workshop on Emerging Trends in Technology (ICWET 2011)-TCET,
Mumbai, India.
[9] F. Wang, J. Ding, Z. Dai, Y. Peng, An application of mobile phone encryption based on
Fibonacci structure of chaos, 2010 Second WRI World Congress on Software Engineering.

Balıkesir University, Department of Mathematics, 10145 Balıkesir, TURKEY

E-mail address: nihaltas@[Link]

Balıkesir University, Department of Mathematics, 10145 Balıkesir, TURKEY

E-mail address: sumeyraucar@[Link]

Balıkesir University, Department of Mathematics, 10145 Balıkesir, TURKEY

E-mail address: nihal@[Link]

Balıkesir University, 10145 Balıkesir, TURKEY

E-mail address: oztunc@[Link]
 A NEW CODING/DECODING ALGORITHM USING FIBONACCI NUMBERS 9

Table 1. The Algorithm for n = 2

a=input(’a=’); b=input(’b= ’); c=input(’c= ’); d=input(’d= ’);

A= [a, b; c, d];
F=[det(A), a; c, d];%End of Coding Algorithm
f ibf (1) = 1; f ibf (2) = 1; p=3;
while fibf(p − 1) < 1000 fibf(p)=fibf(-1)+fibf(p-2); p=p+1; end
Q = [fibf(n+1), fibf(n); fibf(n), fibf(n-1)];
e1= fibf(n+1)*a+fibf(n)*b; e2= fibf(n)*a+fibf(n-1)*b;
x = sym(’x’);
eqn = (-1)ˆn*det(A) == (e1*(fibf(n)*x+fibf(n-1)*d))-(e2*(fibf(n+1)*x+fibf(n)*d));
solx = solve(eqn,’x’);
E =[a,b;solx,d] %End of Decoding Algorithm
 10 N. TAŞ, S. UÇAR, N. YILMAZ ÖZGÜR, AND Ö. ÖZTUNÇ KAYMAK

Table 2. The Algorithm for n = 4

a=input(’a=’); b=input(’b= ’); c=input(’c= ’); d=input(’d= ’);

e=input(’e = ’); f =input(’f = ’); g=input(’g = ’);h=input(’h = ’);
i=input(’i= ’); j=input(’j = ’); k=input(’k = ’); l=input(’l = ’);
m=input(’m = ’); n=input(’n = ’); p=input(’p = ’); r=input(’r = ’);
A = [a, b, c, d; e, f, g, h; i, j, k, l; m, n, p, r];
M = [a, b; e, f ]; N = [c, d; g, h]; O = [i, j; m, n]; P = [k, l; p, r];
d1=det(M); d2=det(N); d3=det(O); d4=det(P);
F=[d1, a, b, f ; d2, c, d, h; d3, i, j, n; d4, k, l, r]%End of Coding Algorithm
f ibf (1) = 1; f ibf (2) = 1; p=3;
while f ibf (p-1) < 1000 f ibf (p) = f ibf (p-1)+f ibf (p-2); ;
p=p+1;end
de11=f ibf (s+1)*a+f ibf (s)*b;
e12= f ibf (s+1)*c+f ibf (s)*d;
e13= f ibf (s+1)*i+f ibf (s)*j;
e14= f ibf (s+1)*k+f ibf (s)*l;
e21= f ibf (s)*a+f ibf (s-1)*b;
e22= f ibf (s)*c+f ibf (s-1)*d;
e23= f ibf (s)*i+f ibf (s-1)*j;
e24= f ibf (s)*k+f ibf (s-1)*l; x = sym(’x’);
eqn1 = (-1)ˆs*d1 == (e11*(f ibf (s)*x+f ibf (s-1)*f))-(e21*(f ibf (s+1)*x+f ibf (s)*f));
eqn2 = (-1)ˆs*d2 == (e12*(f ibf (s)*x+f ibf (s-1)*h))-(e22*(f ibf (s+1)*x+f ibf (s)*h));
eqn3 = (-1)ˆs*d3 == (e13*(f ibf (s)*x+f ibf (s-1)*n))-(e23*(f ibf (s+1)*x+f ibf (s)*n));
eqn4 = (-1)ˆs*d4 == (e14*(f ibf (s)*x+f ibf (s-1)*r))-(e24*(f ibf (s+1)*x+f ibf (s)*r));
solx1 = solve(eqn1,’x’); solx2 = solve(eqn2,’x’);
solx3 = solve(eqn3,’x’); solx4 = solve(eqn1,’x’);
B1 = [a, b;solx1,f ]; B2 = [c, d;solx2,h]; B3 = [i, j;solx3, n]; B4 = [k, l;solx4,r];
M=[a, b, c, d;solx1,f ,solx2, h; i, j, k, l;solx3,n,solx4,r]%End of Decoding Algorithm

View publication stats