A new class of Fibonacci sequence based error correcting codes

Abstract

A new class of matrices is introduced for use in error control coding. This extends previous results on the class of Fibonacci error correcting codes. For a given integer p, a (p+1)×(p+1) binary matrix M _p is given whose nonzero entries are located either on the superdiagonal or the last row of the matrix. The matrices ${M^{n}_{p}}$ and $M^{-n}_{p}$, the nth power of M _p and its inverse, are employed as the encoding and decoding matrices, respectively. It is shown that for sufficiently large n, independent of the message matrix M, relations exist among the elements of the encoded matrix $E=M\times {M_{p}^{n}}$. These relations play a key role in the error detection and correction.

1 Introduction and background

The well-known Fibonacci sequence is defined by f ₀ = 0, f ₁ = 1 and f _n = f _n−1 + f _n−2, n ≥ 2. For an integer p ≥ 0, the Fibonacci p-numbers, introduced in [1], are defined by F _p (1) = F _p (2)=⋯ = F _p (p) = F _p (p+1)=1 and the recursive relation

$$ F_{p}(n)=F_{p}(n-1)+F_{p}(n-p-1), ~~~~n>p+1. $$

(1)

The matrix $Q=\left (\begin {array}{cc}1&1\\1&0 \end {array}\right )$ is known as the Fibonacci Q-matrix [2, 3]. The nth power of Q is $Q^{n}=\left (\begin {array}{cc}f_{n+1}&f_{n}\\f_{n}&f_{n-1} \end {array}\right )$. The Q _p -matrices, an extension of the Q-matrix, are defined as [4]

$$Q_{1}=\left( \begin{array}{cc}1&1\\1&0 \end{array}\right),~~~ Q_{2}=\left( \begin{array}{ccc}1&1&0\\0&0&1\\1&0&0 \end{array}\right), $$

$$ Q_{p}=\left( \scriptsize{\begin{array}{ccccccc} 1&1&0&0&\cdots&0&0\\ 0&\ddots&1&0&\ddots&\ddots&\vdots\\ \vdots&\ddots&\ddots&1&\ddots&\ddots&\vdots\\ \vdots&\ddots&\ddots&\ddots&\ddots&\ddots&\vdots\\ \vdots&\ddots&\ddots&\ddots&\ddots&1&0\\ 0&\ddots&\ddots&\ddots&\ddots&0&1\\ 1&0&0&0&\cdots&0&0 \end{array}}\right)_{(p+1)\times (p+1)} $$

(2)

It was shown in [4] that ${Q_{p}^{n}}$, the nth power of Q _p , is

$${Q^{n}_{p}}= \left( \begin{array}{ccccc} F_{p}(n+1) & F_{p}(n) & {\cdots} & F_{p}(n-p+2) & F_{p}(n-p+1) \\ F_{p}(n-p+1) & F_{p}(n-p) & {\cdots} & F_{p}(n-2p+2) & F_{p}(n-2p+1) \\ {\vdots} & {\vdots} & {\vdots} & {\vdots} & {\vdots} \\ F_{p}(n-1) & F_{p}(n-2) & {\cdots} & F_{p}(n-p) & F_{p}(n-p-1) \\ F_{p}(n) & F_{p}(n-1) & {\cdots} & F_{p}(n-p+1) & F_{p}(n-p) \end{array} \right). $$

(3)

An encoding and decoding technique based on these matrices and referred to as Fibonacci coding theory was introduced in [5–7].

Another extension of the Fibonacci sequence is the Fibonacci polynomial defined by the recurrence relation f ₁(x) = 1, f ₂(x) = x and f _n (x) = x f _n−1(x) + f _n−2(x), n ≥ 3 [8, 9]. The m×m matrix Q _m (x) is given by

$$Q_{m}(x)=\left( \begin{array}{cccccc} x&1&0&0&\cdots&0\\ 0&x&1&0&\cdots&0\\ 0&0&x&1&\cdots&0\\ \vdots&\vdots&\ddots&\ddots&\ddots&\vdots\\ 0&0&\cdots&0&x&1\\ 0&0&\cdots&0&1&0 \end{array} \right)_{m \times m} $$

It was shown in [10] that for n ≥ 2 and m ≥ 2, the entries of ${Q_{m}^{n}}(x)$ are Fibonacci polynomials. The matrix ${Q_{m}^{n}}(x)$ was employed in [10, 11] to obtain an error detection and correction technique referred to as Fibonacci polynomial based coding. In this case, ${Q_{m}^{n}}(x)$ is the encoding matrix.

Similar to the above coding methods, in this paper a new class of square matrices is presented that is suitable for channel coding. For a given integer p, a binary (p+1)×(p+1) matrix is given whose nth power, referred to as the Fibonacci ${M^{n}_{p}}$-matrix, is used as the encoding matrix. The entries of ${M_{p}^{n}}$ are represented by a sequence of numbers a _n , referred to as the Fibonacci M _p -sequence. The decoding matrix $M^{-n}_{p}$ is characterized by a sequence of numbers b _n , referred to as the Fibonacci $M^{-1}_{p}$-sequence b _n , that is based on the entries of $M^{-1}_{p}$ and a recursive relation very similar to that for sequence a _n .

The rest of the paper is organizedas follows. The M _p -matrix and Fibonacci M _p -sequence a _n are introduced in Section 2. The elements of ${M^{n}_{p}}$ are characterized by the sequence a _n . In Section 3, the inverse of ${M^{n}_{p}}$, denoted $M^{-n}_{p}$, is determined. This matrix is characterized by the Fibonacci $\hspace *{-.3pt}M^{-1}_{p}$-sequence b _n . Another expression for the sequence a _n is given in Section 4 which is more suitable for proving some results in Section 6. The encoding and decoding operations are described in Section 5. Some relations among the entries of the encoded matrix E are provided in Section 6. Using the results in Section 6, the error detection and correction processes are discussed in Section 7, followed by a summary of the paper in Section 8.

2 The ${M^{n}_{p}}$-matrix and the Fibonacci M _p -sequence

In this section, for a given number p a (p+1)×(p+1) matrix denoted by M _p and a sequence of numbers a _n referred to as the Fibonacci M _p -sequence, are introduced. The matrix M _p and the sequence a _n can be considered a generalization of the matrix Q _p given by (2), and the Fibonacci p-numbers given by (1), respectively. In fact, if p = 1 then the sequence a _n is the Fibonacci sequence defined by f ₀ = 0, f ₁ = 1 and f _n = f _n−1 + f _n−2, n ≥ 2. Similar to the relation in (3), it is shown that the nth power of M _p , denoted ${M_{p}^{n}}$, can be expressed by the sequence a _n . The matrix ${M_{p}^{n}}$ is used as an encoding matrix.

Consider the following four (p+1)×(p+1) matrices

$$M_{p1}\,=\,\left( \scriptsize{\begin{array}{ccccccc} 0&1&0&0&\cdots&0&0\\ 0&0&1&0&\ddots&\ddots&\vdots\\ \vdots&\ddots&\ddots&1&\ddots&\ddots&\vdots\\ \vdots&\ddots&\ddots&\ddots&\ddots&\ddots&\vdots\\ \vdots&\ddots&\ddots&\ddots&\ddots&1&0\\ 0&0&0&0&\cdots&0&1\\ 1&1&1&1&\cdots&1&1 \end{array}}\right)_{(p+1)\times (p+1)} ~~~~~ M_{p2}\,=\,\left( \scriptsize{\begin{array}{ccccccc} 1&1&0&0&\cdots&0&0\\ 1&0&1&0&\ddots&\ddots&\vdots\\ \vdots&\vdots&\ddots&1&\ddots&\ddots&\vdots\\ \vdots&\vdots&\ddots&\ddots&\ddots&\ddots&\vdots\\ \vdots&\vdots&\ddots&\ddots&\ddots&1&0\\ 1&0&0&0&\ddots&0&1\\ 1&0&0&0&\cdots&0&0 \end{array}}\right)_{(p+1)\times (p+1)} $$

$$M_{p3}\,=\,\left( \scriptsize{\begin{array}{ccccccc} 0&\cdots&\cdots&\cdots&\cdots&0&1\\ 1&\ddots&\ddots&\ddots&\ddots&\vdots&\vdots\\ 0&1&\ddots&\ddots&\ddots&\vdots&\vdots\\ \vdots&\ddots&\ddots&\ddots&\ddots&\vdots&\vdots\\ \vdots&\ddots&\ddots&\ddots&\ddots&\vdots&\vdots\\ \vdots&\ddots&\ddots&\ddots&1&0&1\\ 0&\cdots&\cdots&\cdots&0&1&1 \end{array}}\right)_{(p+1)\times (p+1)} ~~~~ M_{p4}\,=\,\left( \scriptsize{\begin{array}{ccccccc} 1&1&\cdots&\cdots&\cdots&\cdots&1\\ 1&0&\cdots&\cdots&\cdots&\cdots&0\\ 0&1&\ddots&\ddots&\ddots&\ddots&\vdots\\ \vdots&\ddots&\ddots&\ddots&\ddots&\ddots&\vdots\\ \vdots&\ddots&\ddots&\ddots&\ddots&\ddots&\vdots\\ \vdots&\ddots&\ddots&\ddots&1&\ddots&\vdots\\ 0&\cdots&\cdots&\cdots&0&1&0 \end{array}}\right)_{(p+1)\times (p+1)} $$

The matrices M _p3 and M _p4 are the transposes of M _p1 and M _p2, respectively. These four matrices have similar structural properties with respect to the symmetry of the location of their nonzero entries, hence we consider only M _p1 in the rest of the paper. For simplicity, denote the matrix M _p1 by M _p .

Definition 1 (Fibonacci M _p -sequence)

Denoting the nth, n ≥ 0, Fibonacci M _p -number by a _n , define the first p(p+1)+1 elements of the sequence by the entries of the matrix M _p given by

$$M_{p}=\left( \begin{array}{ccccc} a_{0} & a_{1} & {\cdots} & a_{p-1} & a_{p}\\ a_{p} & a_{p+1} & {\cdots} & a_{2p-1} & a_{2p} \\ {\vdots} & {\vdots} & {\vdots} & {\vdots} &{\vdots} \\ a_{(p-1)p} & a_{(p-1)p+1} & {\cdots} &a_{p^{2}-1}& a_{p^{2}} \\ a_{p^{2}} & a_{p^{2}+1} & {\cdots} & a_{p^{2}+p-1} & a_{(p+1)p} \end{array} \right), $$

and define

$$ a_{n}:=a_{n-p}+a_{n-2p}+\cdots+a_{n-(p+1)p},~~~~n>p(p+1). $$

(4)

For example, for p = 2 we have

$$M_{2}= \left( \begin{array}{ccc}0&1&0\\ 0&0&1\\ 1&1&1 \end{array} \right)= \left( \begin{array}{ccc}a_{0}&a_{1}&a_{2}\\ a_{2}&a_{3}&a_{4}\\ a_{4}&a_{5}&a_{6} \end{array}\right), $$

and a _n = a _n−2 + a _n−4 + a _n−6 for n>6. Therefore, a ₀ = 0, a ₁ = 1, a ₂ = a ₃ = 0, a ₄ = a ₅ = a ₆ = 1, a ₇ = a ₈ = 2, a ₉ = 3, a ₁₀ = 4, a ₁₁ = 6, a ₁₂ = 7, a ₁₃ = 11, a ₁₄ = 13, a ₁₅ = 20, ⋯.

It follows from Definition 1 that if p = 1 then a ₀ = 0, a ₁ = a ₂ = 1 and a _n = a _a−1 + a _n−2. Thus the Fibonacci M ₁-sequence gives the Fibonacci numbers, and hence the Fibonacci M _p -sequence is a generalization of the well-known Fibonacci sequence.

Theorem 1

The determinant of M _p is det(M _p ) = (−1)^p.

Proof

Using cofactor expansion along the first row, we see that det(M _p ) = −det(M _p−1). This together with induction on p completes the proof. □

Theorem 2

The nth power of M _p is

$$ {M_{p}^{n}}=\left( \begin{array}{ccccc} a_{p(n-1)} & a_{p(n-1)+1} & a_{p(n-1)+2} & {\cdots} & a_{pn} \\ a_{pn} & a_{pn+1} & a_{pn+2} & {\cdots} & a_{p(n+1)} \\ {\vdots} & {\vdots} & {\vdots} & {\vdots} & {\vdots} \\ a_{p(n+p-2)} & a_{p(n+p-2)+1} & a_{p(n+p-2)+2} & {\cdots} & a_{p(n+p-1)} \\ a_{p(n+p-1)} & a_{p(n+p-1)+1} & a_{p(n+p-1)+2} & {\cdots} & a_{p(n+p)} \end{array} \right). $$

(5)

Proof

The proof is by induction on n. The statement obviously holds for n = 1 as ${M_{p}^{1}}=M_{p}$. Assume that (5) holds for n−1. It follows from ${M_{p}^{n}}=M_{p}M_{p}^{n-1}$ that ${X_{p}^{n}}(i)$, the ith column of ${M_{p}^{n}}$, is $M_{p}X_{p}^{n-1}(i)$. Using (4), the ith column of the matrix is

$$M_{p}X_{p}^{n-1}(i)=\left( \scriptsize{\begin{array}{ccccccc} 0&1&0&0&\cdots&0&0\\ 0&0&1&0&\ddots&\ddots&\vdots\\ \vdots&\ddots&\ddots&1&\ddots&\ddots&\vdots\\ \vdots&\ddots&\ddots&\ddots&\ddots&\ddots&\vdots\\ \vdots&\ddots&\ddots&\ddots&\ddots&1&0\\ 0&0&0&0&\cdots&0&1\\ 1&1&1&1&\cdots&1&1 \end{array}}\right) \left( \begin{array}{c} a_{p(n-2)+i-1} \\ a_{p(n-1)+i-1} \\ {\vdots} \\ a_{p(n+p-3)+i-1} \\ a_{p(n+p-2)+i-1} \end{array} \right), $$

and thus (5) holds for n. □

Remark 1

A consequence of Theorems 1 and 2 is that $\det ({M^{n}_{p}})=(-1)^{np}$.

3 The $M^{-n}_{p}$-matrix and the Fibonacci $M^{-1}_{p}$-sequence

In this section, the inverse of matrix ${M^{n}_{p}}$, denoted $M^{-n}_{p}$, is given. The entries of $M^{-n}_{p}$ have a simple expression in terms of a sequence called the Fibonacci $M^{-1}_{p}$-sequence b _n . Consider the (p+1)×(p+1) matrix defined by

$$M_{-p}:=\left( \begin{array}{cccccc} -1 &-1 &{\cdots} &{\cdots} &-1 &1 \\ 1 &0 &{\cdots} &{\cdots} &{\cdots} &0 \\ 0 &1 &{\ddots} &{\ddots} &{\ddots} &{\vdots} \\ {\vdots} &{\ddots} &{\ddots} &{\ddots} &{\ddots} &{\vdots} \\ {\vdots} &{\ddots} &{\ddots} &1 &0 &0 \\ 0 &{\cdots} &{\cdots} &0 &1 &0 \end{array} \right)_{(p+1)\times(p+1)} $$

It is easy to verify that

$$M_{p}M_{-p}= \left( \begin{array}{cccccc} 0 &1 &0 &{\cdots} &{\cdots} &0 \\ 0 &0 &1 &{\ddots} &{\ddots} &{\vdots} \\ {\vdots} &{\ddots} &{\ddots} &{\ddots} &{\ddots} &{\vdots} \\ {\vdots} &{\ddots} &{\ddots} &{\ddots} &{\ddots} &0 \\ 0 &{\ddots} &{\ddots} &{\ddots} &0 &1 \\ 1 &1 &{\cdots} &{\cdots} &{\cdots} &1 \end{array} \right) \left( \begin{array}{cccccc} -1 &-1 &{\cdots} &{\cdots} &-1 &1 \\ 1 &0 &{\cdots} &{\cdots} &{\cdots} &0 \\ 0 &1 &{\ddots} &{\ddots} &{\ddots} &{\vdots} \\ {\vdots} &{\ddots} &{\ddots} &{\ddots} &{\ddots} &{\vdots} \\ {\vdots} &{\ddots} &{\ddots} &1 &0 &0 \\ 0 &{\cdots} &{\cdots} &0 &1 &0 \end{array} \right)=I_{p+1}, $$

where I _p+1 is the (p+1)×(p+1) identity matrix. Therefore M _−p is in fact $M_{p}^{-1}$, the inverse of M _p . Hence in the rest of the paper M _−p is denoted by $M_{p}^{-1}$.

Now we define a sequence b _n referred to as the Fibonacci $M^{-1}_{p}$-sequence.

Definition 2 (Fibonacci $M^{-1}_{p}$-sequence)

Using the matrix $M_{p}^{-1}$, define the integers b _i , 0 ≤ i ≤ p ² + p, such that

$$ M^{-1}_{p}=\left( \begin{array}{cccccc} b_{p^{2}+p} &b_{p^{2}+p-1} &{\cdots} &{\cdots} &b_{p^{2}+1} &b_{p^{2}} \\ b_{p^{2}} &b_{p^{2}-1} &{\cdots} &{\cdots} &b_{p^{2}-p+1} &b_{p^{2}-p} \\ {\vdots} &{\cdots} &{\cdots} &{\cdots} &{\cdots} &{\vdots} \\ {\vdots} &{\cdots} &{\cdots} &{\cdots} &{\cdots} &{\vdots} \\ b_{2p} &b_{2p-1} &{\cdots} &{\cdots} &b_{p+1} &b_{p} \\ b_{p} &b_{p-1} &{\cdots} &{\cdots} &b_{1} &b_{0} \end{array} \right). $$

(6)

For i>p ² + p, let

$$ b_{n}:=b_{n-(p+1)p}-\cdots-b_{n-3p}-b_{n-2p}-b_{n-p},~~~n>p(p+1). $$

(7)

It follows from $M_{p}M^{-1}_{p}=I_{p+1}$ that $(M_{p})^{n}(M^{-1}_{p})^{n}=(M_{P}M^{-1}_{p})^{n}=I_{p+1}$, and hence the inverse of ${M_{p}^{n}}$ is $(M^{-1}_{p})^{n}$, denoted by $M^{-n}_{p}$. The matrix $(M^{-1}_{p})^{n}=M^{-n}_{p}$ is characterized in the following theorem.

Theorem 3

The matrix $M_{p}^{-n}$ , the nth power of $M^{-1}_{p}$ , is the following (p+1)×(p+1) matrix

$$ M_{p}^{-n}=\left( \begin{array}{cccccc} b_{p(n+p)} &b_{p(n+p)-1} &{\cdots} &{\cdots} &b_{p(n+p-1)+1} &b_{p(n+p-1)} \\ b_{p(n+p-1)} &b_{p(n+p-1)-1} &{\cdots} &{\cdots} &b_{p(n+p-2)+1} &b_{p(n+p-2)} \\ {\vdots} &{\cdots} &{\cdots} &{\cdots} &{\cdots} &{\vdots} \\ {\vdots} &{\cdots} &{\cdots} &{\cdots} &{\cdots} &{\vdots} \\ b_{p(n+1)} &b_{p(n+1)-1} &{\cdots} &{\cdots} &b_{pn+1} &b_{pn} \\ b_{pn} &b_{pn-1} &{\cdots} &{\cdots} &b_{p(n-1)+1} &b_{p(n-1)} \end{array} \right). $$

(8)

Proof

The proof is by induction on n. For n = 1 the statement is true from (6). Assume that (8) holds for n−1. It follows from $M_{p}^{-n}=M^{-1}_{p}M_{p}^{-(n-1)}$ that $Y_{p}^{-n}(i)$, the ith column of $M_{p}^{-n}$, is $M^{-1}_{p}Y_{p}^{-(n-1)}(i)$. Applying (7), the ith column of the matrix given by (8) is

$$M^{-1}_{p}Y_{p}^{-(n-1)}(i)\,=\, \left( \scriptsize{ \begin{array}{cccccc} -1 &-1 &{\cdots} &{\cdots} &-1 &1 \\ 1 &0 &{\cdots} &{\cdots} &{\cdots} &0 \\ 0 &1 &{\ddots} &{\ddots} &{\ddots} &{\vdots} \\ {\vdots} &{\ddots} &{\ddots} &{\ddots} &{\ddots} &{\vdots} \\ {\vdots} &{\ddots} &{\ddots} &1 &0 &0 \\ 0 &{\cdots} &{\cdots} &0 &1 &0 \end{array}} \right) \left( \begin{array}{c}b_{p(n+p-1)-(i-1)}\\b_{p(n+p-2)-(i-1)}\\\vdots\\b_{pn-(i-1)}\\b_{p(n-1)-(i-1)} \end{array} \right)\,=\,\left( \begin{array}{c} b_{p(n+p)-(i-1)} \\ b_{p(n+p-1)-(i-1)} \\ {\vdots} \\ b_{p(n+1)-(i-1)} \\ b_{pn-(i-1)} \end{array} \right)\!, $$

so that (8) holds for n. □

4 Another expression for the Fibonacci M _p -sequence a _n

In order to provide a proof for the error-correction relations, we give a new definition for sequence a _n . For p = 2 we have

$${M_{2}^{n}}= \left( \begin{array}{ccc} a_{2n-2} & a_{2n-1} & a_{2n}\\ a_{2n} & a_{2n+1} & a_{2n+2}\\ a_{2n+2} & a_{2n+3} & a_{2n+4} \end{array} \right)~. $$

It follows from ${M_{2}^{n}}=M_{2}^{n-1}M_{2}$ that the first row of ${M_{2}^{n}}$ is

$$\left( \begin{array}{ccc} a_{2n-2} & a_{2n-1} & a_{2n} \end{array} \right)~= \left( \begin{array}{ccc} a_{2n-4} & a_{2n-3} & a_{2n-2} \end{array} \right)~ \left( \begin{array}{ccc} 0 & 1 & 0\\ 0 & 0 & 1\\ 1 & 1 & 1 \end{array} \right)\, . $$

Hence

$$\left\{ \begin{array}{ccc} a_{n}&=&a_{n-3}+a_{n-1}\,~~\text{if}~\textit{n}~\text{is~odd},\\ a_{n}&=&a_{n-3}+a_{n-2}\,~~\text{if}~\textit{n}~\text{is~even}; \end{array} \right.$$

which can be expressed by

$$ a_{n}=\left\{ \begin{array}{ccc} a_{n-3}+a_{n-1} &\text{if}& n=1~\text{mod}~2,\\ a_{n-3}+a_{n-2} & \text{if}&n=0~\text{mod}~2. \end{array} \right. $$

(9)

For example, if for p = 2 we want to determine a _n using relation (9), we need the first three elements of the sequence. From matrix M ₂, a ₀ = 0, a ₁ = 1, a ₂ = 0, and using (9) gives

$$ \left\{ \begin{array}{cccccc} a_{3}=0&a_{4}=1&a_{5}=1&a_{6}=1 & a_{7}=2&a_{8}=2 \\ a_{9}=3 & a_{10}=4&a_{11}=6&a_{12}=7&a_{13}=11&a_{14}=13\\ a_{15}=20 & a_{16}=24 & a_{17}=37 &a_{18}=44 &a_{19}=68 &a_{20}=81\\ a_{21}=125 &a_{22}=149 &a_{23}=230&a_{24}=274&a_{25}=423 &a_{26}=504 \end{array} \right. . $$

(10)

Using relation (4) for the definition of a _n , we see that for p = 2 we have a _n = a _n−2 + a _n−4 + a _n−6. It is easily shown that this relation together with the initial values a ₀ = a ₂ = a ₃ = 0 and a ₁ = a ₄ = a ₅ = a ₆ = 1 gives the sequence in (10), verifying that the two definitions for a _n generate the same sequence.

We now generalize the definition of sequence a _n . From ${M_{p}^{n}}=M_{p}^{n-1}M_{p}$ and relation (5), the first row of ${M_{p}^{n}}$ is

$$\left( \begin{array}{ccccc} a_{p(n-1)} & a_{p(n-1)+1} & a_{p(n-1)+2} & {\cdots} & a_{pn} \end{array} \right)\, = $$

$$\left( \begin{array}{ccccc} a_{p(n-2)} & a_{p(n-2)+1} & a_{p(n-2)+2} & {\cdots} & a_{p(n-1)} \end{array} \right)~ \left( {\begin{array}{ccccccc} 0&1&0&0&\cdots&0&0\\ 0&0&1&0&\ddots&\ddots&\vdots\\ \vdots&\ddots&\ddots&1&\ddots&\ddots&\vdots\\ \vdots&\ddots&\ddots&\ddots&\ddots&\ddots&\vdots\\ \vdots&\ddots&\ddots&\ddots&\ddots&1&0\\ 0&0&0&0&\cdots&0&1\\ 1&1&1&1&\cdots&1&1 \end{array}}\right)\, . $$

Similar to the case p = 2, it follows that

$$ a_{n}=\left\{ \begin{array}{ccc} a_{n-p-1}+a_{n-1} &\text{if}& n=1~\text{mod}~p,\\ a_{n-p-1}+a_{n-2} &\text{if}& n=2~\text{mod}~p,\\ \vdots&\vdots&\vdots\\ a_{n-p-1}+a_{n-p} &\text{if}& n=0~\text{mod}~p. \end{array} \right. $$

(11)

This expression for a _n will be used to derive the limit of the numbers e _i /e _i+1 defined in the next section.

5 Fibonacci coding using ${M_{p}^{n}}$ and $M^{-n}_{p}$

In this section, a channel coding method is introduced based on the matrices ${M_{p}^{n}}$ and $M_{p}^{-n}$. The message is represented by a square (p+1)×(p+1) matrix M called the message matrix. The number p is chosen by the user. For fixed integers p and n, the encoding matrix ${M_{p}^{n}}$ is given by (5). The encoding matrix is then multiplied from the left by the message matrix M to obtain the encoded matrix E. For example, for p = 2 we have

$$ E=M\times{}{M_{2}^{n}}=\left( \begin{array}{ccc} m_{1} & m_{2} & m_{3} \\ m_{4} & m_{5} & m_{6} \\ m_{7} & m_{8} & m_{9} \end{array} \right)\left( \begin{array}{ccc} a_{2n-2} & a_{2n-1} & a_{2n} \\ a_{2n} & a_{2n+1} & a_{2n+2} \\ a_{2n+2} & a_{2n+3} & a_{2n+4} \end{array}\right)=\left( \begin{array}{ccc} e_{1} & e_{2} & e_{3} \\ e_{4} & e_{5} & e_{6} \\ e_{7} & e_{8} & e_{9} \end{array}\right). $$

(12)

The elements of E, e ₁, e ₂,⋯ , e ₉, and det(M) are sent through the channel. Assuming that the transmitted sequence is received with no errors, E can be multiplied by $M_{2}^{-n}$ to recover the message matrix

$$ M=E\times M_{2}^{-n}=\left( \begin{array}{ccc} e_{1} & e_{2} & e_{3} \\ e_{4} & e_{5} & e_{6} \\ e_{7} & e_{8} & e_{9} \end{array}\right)\left( \begin{array}{ccc} a_{2n-2} & a_{2n-1} & a_{2n} \\ a_{2n} & a_{2n+1} & a_{2n+2} \\ a_{2n+2} & a_{2n+3} & a_{2n+4} \end{array} \right)^{-1}=\left( \begin{array}{ccc} m_{1} & m_{2} & m_{3} \\ m_{4} & m_{5} & m_{6} \\ m_{7} & m_{8} & m_{9} \end{array}\right). $$

(13)

The matrix $M_{2}^{-n}$ can be obtained directly from ${M_{2}^{n}}$ as

$$ M_{2}^{-n}\,=\,\left( \begin{array}{ccc}a_{2n+1}a_{2n+4}-a_{2n+2}a_{2n+3}&a_{2n}a_{2n+3}-a_{2n-1}a_{2n+4}&\! a_{2n-1}a_{2n+2}-a_{2n}a_{2n+1}\\ a_{2n+2}^{2}-a_{2n}a_{2n+4}&a_{2n-2}a_{2n+4}-a_{2n}a_{2n+2}& \!a_{2n}^{2}-a_{2n-2}a_{2n+2}\\ a_{2n}a_{2n+3}-a_{2n+1}a_{2n+2}&a_{2n-1}a_{2n+2}-a_{2n-2}a_{2n+3}& a_{2n-2}a_{2n+1}-a_{2n-1}a_{2n} \end{array}\!\right), $$

(14)

or from (8). The main question is how to detect and correct errors in the encoded matrix E that occur due to channel noise. This will be discussed in Section 7.

6 Some relations among the elements of the encoded matrix E

In this section, it is shown that if ${M_{p}^{n}}$ is used as the encoding matrix, then for n sufficiently large, independent of the message matrix M, there exist some relations among the entries of the corresponding encoded matrix (given in (21)–(23) and (29)). These relations are employed in decoding. We first consider the case p = 2. The result $\det ({M^{n}_{2}})=(-1)^{2n}=1$ gives

$$ \begin{array}{ll} \det({M^{n}_{2}})&=a_{2n-2}(a_{2n+1}a_{2n+4}-a_{2n+2}a_{2n+3})\\ &-a_{2n-1}(a_{2n}a_{2n+4}-a^{2}_{2n+2})\\ &+a_{2n}(a_{2n}a_{2n+3}-a_{2n+1}a_{2n+2})\\ &=1. \end{array} $$

(15)

It follows from (13) and (14) that

$$ \begin{array}{l} m_{1}=e_{1}(a_{2n+1}a_{2n+4}-a_{2n+2}a_{2n+3})+e_{2}(a^{2}_{2n+2}-a_{2n}a_{2n+4})+e_{3}(a_{2n}a_{2n+3}-a_{2n+1}a_{2n+2})>0,\\ m_{2}=e_{1}(a_{2n}a_{2n+3}-a_{2n-1}a_{2n+4})+e_{2}(a_{2n-2}a_{2n+4}-a_{2n}a_{2n+2}) +e_{3}(a_{2n-1}a_{2n+2}-a_{2n-2}a_{2n+3})>0,\\ m_{3}=e_{1}(a_{2n-1}a_{2n+2}-a_{2n}a_{2n+1})+e_{2}(a^{2}_{2n}-a_{2n-2}a_{2n+2})+e_{3}(a_{2n-2}a_{2n+1}-a_{2n-1}a_{2n})>0. \end{array} $$

(16)

Theorem 4

With the notation of ( 12 ), one of the following two systems of three inequalities holds

$$ \left\{ \begin{array}{c} \vspace{-2mm} \frac{a_{2n-2}}{a_{2n-1}}\leq \frac{e_{1}}{e_{2}}\leq \frac{a_{2n}}{a_{2n+1}},\\\\ \vspace{-2mm} \frac{a_{2n-1}}{a_{2n}}\leq \frac{e_{2}}{e_{3}}\leq \frac{a_{2n+1}}{a_{2n+2}},\\\\ \frac{a_{2n-2}}{a_{2n}}\leq \frac{e_{1}}{e_{3}}\leq \frac{a_{2n}}{a_{2n+2}}; \end{array}\right. ~~~~~~~~~~~~~ \left\{ \begin{array}{c} \vspace{-2mm} \frac{a_{2n-2}}{a_{2n-1}}\geq \frac{e_{1}}{e_{2}}\geq \frac{a_{2n}}{a_{2n+1}},\\\\ \vspace{-2mm} \frac{a_{2n-1}}{a_{2n}}\geq \frac{e_{2}}{e_{3}}\geq \frac{a_{2n+1}}{a_{2n+2}},\\\\ \frac{a_{2n-2}}{a_{2n}}\geq \frac{e_{1}}{e_{3}}\geq \frac{a_{2n}}{a_{2n+2}}. \end{array}\right. $$

(17)

Proof

We show that depending on the sign of the three numbers K ₁ = a _{2 n} a _{2 n+3}−a _{2 n+1} a _{2 n+2}, K ₂ = a _{2 n−1} a _{2 n+2}−a _{2 n−2} a _{2 n+3}, and K ₃ = a _{2 n−1} a _{2 n} −a _{2 n−2} a _{2 n+1}, we have either the left system or the right one. Each of these numbers is either negative, zero or positive, hence there are 27 choices for the three-tuple (K ₁, K ₂, K ₃). A detailed proof is given for the case where K ₁, K ₂ and K ₃ are positive (the proofs for the other 26 cases are similar). For this case we have the left system.

It follows from (16) that

$$\left\{ \begin{array}{l} e_{{1}} a_{{2\,n+2}}a_{{2\,n+3}} +e_{{2}} a_{{2 \,n}}a_{{2\,n+4}} +e_{{3}} a_{{2\,n+1}}a_{{2\,n+2}}<e_{{1}}a_{{2\,n+1}}a_{{2\,n+4}} +e_{{2}} {a^{2}_{{2\,n+2}}} +e_{{3}} a_{{2\,n}}a_{{2\,n+3}}, \\ e_{{1}}a_{{2\,n-1}}a_{{2\,n+4}} +e_{{2}} a_{{2 \,n}}a_{{2\,n+2}} +e_{{3}} a_{{2\,n+2}}a_{{2\,n+3}}<e_{{1}} a_{{2\,n}}a_{{2\,n+3}} +e_{{2}} a_{{2\,n-2}}a_{{2\,n+4}} +e_{{3}}a_{{2\,n-1}}a_{{2\,n+2}}, \\ e_{{1}}a_{{2\,n}}a_{{2\,n+1}} +e_{{2}} a_{{2\,n -2}}a_{{2\,n+2}}+e_{{3}} a_{{2\,n-1}}a_{{2\,n}} <e_{{1}} a_{{2\,n-1}}a_{{2\,n+2}} +e_{{2}} {a^{2}_{{2\,n}}} +e_{{3}} a_{{2\,n-2}}a_{{2\,n+1}}. \end{array}\right. $$

which is equivalent to

$$ \left\{ \begin{array}{l} {\frac {e_{{2}} \left( a_{{2\,n}}a_{{2\,n+4}}-{a^{2}_{{2\,n+2}}} \right) }{e_{{1}}}}+a_{{2\,n+2}}a_{{2\,n+3}}-a_{{2\,n+1}}a_{{2\,n+4}}<{\frac {e_{{3}} \left( a_{{2\,n}}a_{{2\,n+3}}-a_{{2\,n+1}}a_{{2\,n+2} } \right)}{e_{{1}}}},\\ {\frac {e_{{2}} \left( a_{{2\,n}}a_{{2\,n+2}}-a_{{2\,n-2}}a_{{2\,n+4}} \right) }{e_{{1}}}}+a_{{2\,n-1}}a_{{2\,n+4}}-a_{{2\,n}}a_{{2\,n+3}}<{\frac {e_{{3}} \left( a_{{2\,n-1}}a_{{2\,n+2}}-a_{{2\,n-2}}a_{{2\,n+3} } \right)}{e_{{1}}}},\\ {\frac {e_{{2}} \left( {a^{2}_{{2\,n}}}-a_{{2\,n-2}}a_{{2\,n+2}} \right) }{e_{{1}}}}+a_{{2\,n-1}}a_{{2\,n+2}}-a_{{2\,n}}a_{{2\,n+1}}>{\frac {e_{{3}} \left( a_{{2\,n-1}}a_{{2\,n}}-a_{{2\,n-2}}a_{{2\,n+1}} \right) }{e_{{1}}}}. \end{array}\right. $$

(18)

Using K ₁ = a _{2 n} a _{2 n+3}−a _{2 n+1} a _{2 n+2}, K ₂ = a _{2 n−1} a _{2 n+2}−a _{2 n−2} a _{2 n+3}, and K ₃ = a _{2 n−1} a _{2 n} −a _{2 n−2} a _{2 n+1}, from (18) we have

$$ \begin{array}{l} {\frac {e_{{2}} \left( a_{{2\,n}}a_{{2\,n+4}}-{a^{2}_{{2\,n+2}}} \right) }{e_{{1}}K_{{1}}}}+{\frac {a_{{2\,n+2}}a_{{2\,n+3}}-a_{{2\,n+ 1}}a_{{2\,n+4}}}{K_{{1}}}}<{\frac {e_{{3}}}{e_{{1}}}},\\ {\frac {e_{{2}} \left( a_{{2\,n}}a_{{2\,n+2}}-a_{{2\,n-2}}a_{{2\,n+4}} \right) }{e_{{1}}K_{{2}}}}+{\frac {a_{{2\,n-1}}a_{{2\,n+4}}-a_{{2\,n} }a_{{2\,n+3}}}{K_{{2}}}}<{\frac {e_{{3}}}{e_{{1}}}},\\ {\frac {e_{{3}}}{e_{{1}}}}<{\frac {e_{{2}} \left( {a^{2}_{{2\,n}}}-a_{{2\,n-2}}a_{{2\,n+2}} \right) }{e_{{1}}K_{{3}}}}+{\frac {a_{{2\,n-1}}a_{{2\,n+2}}-a_{{2\,n}}a_{{2\,n+1}}}{K_{{3}}}}. \end{array} $$

(19)

The first and third relations give that

$$\begin{array}{l} {\frac {e_{{2}} \left( a_{{2\,n}}a_{{2\,n+4}}-{a^{2}_{{2\,n+2}}} \right) }{e_{{1}}K_{{1}}}}+{\frac {a_{{2\,n+2}}a_{{2\,n+3}}-a_{{2\,n+ 1}}a_{{2\,n+4}}}{K_{{1}}}}\\<{\frac {e_{{2}} \left( {a^{2}_{{2\,n}}}-a_{ {2\,n-2}}a_{{2\,n+2}} \right) }{e_{{1}}K_{{3}}}}+{\frac {a_{{2\,n-1}}a_{{2\,n+2}}-a_{{2\,n}}a_{{2\,n+1}}}{K_{{3}}}}, \end{array} $$

and hence

$$\begin{array}{l} {\frac {K_{{3}} \left( a_{{2\,n+2}}a_{{2\,n+3}}-a_{{2\,n+1}}a_{{2\,n+4 }} \right) -K_{{1}} \left( a_{{2\,n-1}}a_{{2\,n+2}}-a_{{2\,n}}a_{{2\,n +1}} \right) }{K_{{1}}K_{{3}}}}<{\frac {e_{{2}} \left( K_{{1}} \left( {a^{2}_{{2\,n}}}-a_{{2\,n-2}}a_{{2\,n+2}} \right) -K_{{3}} \left( a_{{ 2\,n}}a_{{2\,n+4}}-{a^{2}_{{2\,n+2}}} \right) \right) }{e_{{1}}K_{{1} }K_{{3}}}}. \end{array} $$

This together with (15) and

$$\begin{array}{l}K_{{1}} \left( {a^{2}_{{2\,n}}}-a_{{2\,n-2}}a_{{2\,n+2}} \right) -K_{{3}} \left( a_{{2\,n}}a_{{2\,n+4}}-{a^{2}_{{2\,n+2}}} \right)=a_{{2\,n}}\det({M^{n}_{2}})=a_{2n},\\ K_{{3}} \left( a_{{2\,n+2}}a_{{2\,n+3}}-a_{{2\,n+1}}a_{{2\,n+4 }} \right) -K_{{1}} \left( a_{{2\,n-1}}a_{{2\,n+2}}-a_{{2\,n}}a_{{2\,n +1}}\right)=a_{{2\,n+1}}\det({M^{n}_{2}})=a_{2n+1}, \end{array} $$

gives that

$$\frac{e_{1}}{e_{2}}\leq \frac{a_{2n}}{a_{2n+1}}. $$

Further, from the second and third relations in (19)

$$\begin{array}{l} \frac {e_{{2}} \left( a_{{2\,n}}a_{{2\,n+2}}-a_{{2\,n-2}}a_{{2\,n+4}} \right) }{e_{{1}}K_{{2}}}+{\frac {a_{{2\,n-1}}a_{{2\,n+4}}-a_{{2\,n} }a_{{2\,n+3}}}{K_{{2}}}}\\<{\frac {e_{{2}} \left( {a^{2}_{{2\,n}}}-a_{{2 \,n-2}}a_{{2\,n+2}} \right) }{e_{{1}}K_{{3}}}}+{\frac {a_{{2\,n-1}}a_{{2\,n+2}}-a_{{2\,n}}a_{{2\,n+1}}}{K_{{3}}}}, \end{array} $$

resulting in

$$ \begin{array}{l} {\frac {e_{{2}} \left( K_{{3}} \left( a_{{2\,n}}a_{{2\,n+2}}-a_{{2\,n- 2}}a_{{2\,n+4}} \right) -K_{{2}} \left( {a^{2}_{{2\,n}}}-a_{{2\,n-2}}a_{{2\,n+2}} \right) \right) }{e_{{1}}K_{{2}}K_{{3}}}}\\<{\frac {K_{{2}} \left( a_{{2\,n-1}}a_{{2\,n+2}}-a_{{2\,n}}a_{{2\,n+1}} \right) -K_{{3 }} \left( a_{{2\,n-1}}a_{{2\,n+4}}-a_{{2\,n}}a_{{2\,n+3}} \right) }{K_{{2}}K_{{3}}}}. \end{array} $$

(20)

It follows from (20) and

$$\begin{array}{l}K_{{3}} \left( a_{{2\,n}}a_{{2\,n+2}}-a_{{2\,n-2}}a_{{2\,n+4}} \right)\,-\,K_{{2}} \left( {a^{2}_{{2\,n}}}-a_{{2\,n-2}}a_{{2\,n+2}}\right)=a_{{2\,n-2}}\det({M^{n}_{2}})=a_{{2\,n-2}},\\ K_{{2}} \left( a_{{2\,n-1}}a_{{2\,n+2}}-a_{{2\,n}}a_{{2\,n+1}} \right) \,-\,K_{{3}} \left( a_{{2\,n-1}}a_{{2\,n+4}}\,-\,a_{{2\,n}}a_{{2\,n+3 }} \right)=a_{{2\,n-1}}\det({M^{n}_{2}})\!=a_{{2\,n-1}}, \end{array} $$

that $\frac {a_{2n-2}}{a_{2n-1}}\leq \frac {e_{1}}{e_{2}}$. □

By simulation, it has been determined that for even integers n = 2k, the sequence a _n /a _n+1 converges to 0.64779887126. In fact, for any even integer n ≥ 30 we have a _n /a _n+1≈0.64779887126. The values of a _n /a _n+1 for some values of n are given in Table 1. Based on these results, according to (17) for n sufficiently large we have e ₁/e ₂≈0.64779887126. Further, for odd integers n the sequence a _n /a _n+1 converges to 0.83928675521, and the sequence a _n /a _n+2 for both odd and even integers converges to 0.54368901269. Hence for p = 2 and n ≥ 30 we have

$$ \left\{\begin{array}{l} e_{1}/e_{2}=e_{4}/e_{5}=e_{7}/e_{8}\approx \alpha:=0.64779887126,\\e_{2}/e_{3}=e_{5}/e_{6}=e_{8}/e_{9}\approx \beta:= 0.83928675521,\\ e_{1}/e_{3}=e_{4}/e_{6}=e_{7}/e_{9}\approx \alpha\beta=0.54368901269. \end{array}\right. $$

(21)

Theorem 5 provides a proof for these limits.

Table 1 Values of e _i /e _j for n between 10 and 500

Theorem 5

If ${M_{p}^{n}}$ is used as the encoding matrix, then it can be shown that for n sufficiently large, there are real numbers α _i , 1 ≤ i ≤ p, such that

$$ \left\{ \begin{array}{l} e_{1}/e_{2}=e_{p+2}/e_{p+3}=\cdots=e_{p^{2}+p+1}/e_{p^{2}+p+2}\approx \alpha_{1},\\ e_{2}/e_{3}=e_{p+3}/e_{p+4}=\cdots=e_{p^{2}+p+2}/e_{p^{2}+p+3}\approx \alpha_{2},\\ \vdots\\ e_{p}/e_{p+1}=e_{2p+1}/e_{2p+2}=\cdots=e_{p^{2}+2p}/e_{p^{2}+2p+1}\approx \alpha_{p}. \end{array}\right. $$

(22)

where by e _k /e _l ≈ α _i we mean e _k /e _l is approximately equal to α _i .

Proof

Given a message matrix m and an encoding matrix ${M_{p}^{n}}$, we have $E=M\times {M_{p}^{n}}$, and $m=E\times {({M_{p}^{n}})}^{-1}$. Let E have the form

$$E=\left( \begin{array}{ccccc} e_{1} & e_{2} & {\cdots} & e_{p} & e_{p+1}\\ e_{p+2} & e_{p+3} & {\cdots} & e_{2p+1} & e_{2p+2} \\ {\vdots} & {\vdots} & {\vdots} & {\vdots} &{\vdots} \\ e_{p^{2}+p+1} & e_{p^{2}+p+2} & {\cdots} & e_{p^{2}+2p} & e_{p^{2}+2p+1} \end{array} \right)\, . $$

Similar to the approach used in Theorem 4, the following relations among the entries of the first row of E are obtained where the a _i are the Fibonacci M _p -numbers. Similar relations can be obtained for the other rows of E

$$ \left\{ \begin{array}{ccc} \frac{ a_{p(n-1)}}{a_{p(n-1)+1}} &\leq \frac{e_{1}}{e_{2}} \leq &\frac{a_{pn}}{a_{pn+1}} \hspace{2mm}, \\ &&\\ \frac{ a_{p(n-1)+1}}{a_{p(n-1)+2}} &\leq \frac{e_{2}}{e_{3}} \leq &\frac{a_{pn+1}}{a_{pn+2}} \hspace{2mm} , \\ &&\\ \vdots&\vdots&{\vdots} \vspace{2mm} \\ &&\\ \frac{ a_{pn-1}}{a_{pn}} &\leq \frac{e_{p}}{e_{p+1}} \leq &\frac{a_{p(n+1)-1}}{a_{p(n+1)}} \hspace{2mm} . \end{array} \right. $$

(23)

Suppose there are α _i satisfying the following relations

$$ \left\{ \begin{array}{ccccc} \lim_{n\rightarrow\infty}&\frac{a_{p(n-1)}}{a_{p(n-1)+1}}=&\lim_{n\rightarrow\infty}&\frac{a_{pn}}{a_{pn+1}}=&\alpha_{1}~, \\ \\ \lim_{n\rightarrow\infty}&\frac{a_{p(n-1)+1}}{a_{p(n-1)+2}}=&\lim_{n\rightarrow\infty}&\frac{a_{pn+1}}{a_{pn+2}}=&\alpha_{2}~, \\ \\ {\vdots} &{\vdots} &{\vdots} &{\vdots} &{\vdots} \\ \\ \lim_{n\rightarrow\infty}&\frac{a_{pn-1}}{a_{pn}}=&\lim_{n\rightarrow\infty}&\frac{a_{pn+p-1}}{a_{pn+p}}=&\alpha_{p}~. \end{array} \right. $$

(24)

We make use of the following definition for a _n to derive relations among the α _i .

$$ a_{n}=\left\{ \begin{array}{cc} a_{n-p-1}+a_{n-1} & n=1(\text{mod} \hspace{2mm}p)~,\\ a_{n-p-1}+a_{n-2} & n=2(\text{mod} \hspace{2mm}p)~,\\ {\vdots} \hspace{5mm}+\hspace{5mm}\vdots&\vdots\\ a_{n-p-1}+a_{n-p} & n=0(\text{mod} \hspace{2mm}p)~. \end{array} \right. $$

(25)

As p n+1=1 (mod p), it follows from (25) that

$$ \frac{a_{pn}}{a_{pn+1}}=\frac{a_{pn}}{a_{pn-p}+a_{pn}}=\frac{1}{\displaystyle{1+\frac{a_{pn-p}}{a_{pn}}}}=\frac{1}{\displaystyle{1+ \frac{a_{pn-p}}{a_{pn-p+1}}\frac{a_{pn-p+1}}{a_{pn-p+2}}\times\cdots\times\frac{a_{pn-2}}{a_{pn-1}}\frac{a_{pn-1}}{a_{pn}}}}. $$

(26)

Hence $\alpha _{1}=\frac {1}{\displaystyle {1+\alpha _{1}\alpha _{2}\cdots \alpha _{p-1}\alpha _{p}}}$, implying that ${\alpha _{1}^{2}} \alpha _{2} {\cdots } \alpha _{p-1} \alpha _{p}+\alpha _{1}-1=0$.

To form a second relation among the α _i , consider $\frac {a_{pn+1}}{a_{pn+2}}$. Making use of (25) gives that

$$\begin{array}{@{}rcl@{}} \frac{a_{pn+1}}{a_{pn+2}}&=&\frac{a_{pn+1}}{a_{pn-p+1}+a_{pn}}=\frac{1}{\displaystyle{\frac{a_{pn-p+1}}{a_{pn+1}}+\frac{a_{pn}}{a_{pn+1}}}} \\ &=&\frac{1}{\displaystyle{\frac{a_{pn-p+1}}{a_{pn-p+2}} \frac{a_{pn-p+2}}{a_{pn-p+3}} \times {\cdots} \times \frac{a_{pn-1}}{a_{pn}} \frac{a_{pn}}{a_{pn+1}}+\frac{a_{pn}}{a_{pn+1}}}}. \end{array} $$

(27)

Thus $\alpha _{2}=\frac {1}{\displaystyle {\alpha _{2} \alpha _{3} {\cdots } \alpha _{p} \alpha _{1}+\alpha _{1}}}$, and hence $\alpha _{1} {\alpha _{2}^{2}} \alpha _{3} {\cdots } \alpha _{p-1} \alpha _{p}+\alpha _{1} \alpha _{2}-1=0$. Continuing this process we get the following system of equations among the α _i

$$ \left\{ \begin{array}{lll} {\alpha_{1}^{2}} \alpha_{2} {\cdots} \alpha_{p-1} \alpha_{p}+\alpha_{1}-1 &=& 0 \, ,\\ &&\\ \alpha_{1} {\alpha_{2}^{2}} \alpha_{3} {\cdots} \alpha_{p-1} \alpha_{p}+\alpha_{1} \alpha_{2}-1 &=& 0 \, ,\\ &&\\ \alpha_{1} \alpha_{2} {\alpha_{3}^{2}} \alpha_{4} {\cdots} \alpha_{p-1} \alpha_{p}+\alpha_{1} \alpha_{2} \alpha_{3}-1&=& 0\, , \\ &&\\ {\vdots} & & \\ &&\\ \alpha_{1} \alpha_{2} \alpha_{3} \alpha_{4} {\cdots} \alpha_{p-1} {\alpha_{p}^{2}}+\alpha_{1} \alpha_{2} \cdots \alpha_{p}-1&=& 0\, . \end{array} \right. $$

(28)

Using the Maple SolveTools library, it was determined that this system has a unique real solution. A proof of this solution is given in the AAppendix. □

The following relations among the entries of each row of the encoded matrix E are obtained from (22)

$$ \begin{array}{llll} e_{1}/e_{2}\approx \alpha_{1},&e_{2}/e_{3}\approx \alpha_{2},&\cdots&e_{p}/e_{p+1}\approx \alpha_{p},\\ e_{1}/e_{3}\approx \alpha_{1}\alpha_{2},&e_{2}/e_{4}\approx \alpha_{2}\alpha_{3},&\cdots&e_{p-1}/e_{p+1}\approx\alpha_{p-1} \alpha_{p},\\ e_{1}/e_{4}\approx \alpha_{1}\alpha_{2}\alpha_{3},&e_{2}/e_{5}\approx \alpha_{2}\alpha_{3}\alpha_{4},&\cdots&e_{p-2}/e_{p+1}\approx\alpha_{p-2}\alpha_{p-1}\alpha_{p},\\ \vdots\\ e_{1}/e_{p+1}\approx\alpha_{1}\alpha_{2}\cdots\alpha_{p}. \end{array} $$

(29)

To provide a better understanding of the method for finding the relations among the α _i , we give the following theorem for p = 2 as a special case of Theorem 5.

Theorem 6

For n ≥ 30 and p = 2 we have

$$\left\{\begin{array}{l} e_{1}/e_{2}=e_{4}/e_{5}=e_{7}/e_{8}\approx \alpha_{1}:=0.64779887126,\\e_{2}/e_{3}=e_{5}/e_{6}=e_{8}/e_{9}\approx \alpha_{2}:= 0.83928675521,\\ e_{1}/e_{3}=e_{4}/e_{6}=e_{7}/e_{9}\approx \alpha_{1}\alpha_{2}=0.54368901269. \end{array}\right. $$

Proof

For p = 2, consider a _n given in (9). Define α ₁ and α ₂ as

$$\alpha_{1}:=\lim_{n\to \infty}\frac{a_{2n}}{a_{2n+1}},~~~~\alpha_{2}:=\lim_{n\to \infty}\frac{a_{2n+1}}{a_{2n+2}}.$$

It follows from (9) that

$$ \frac{a_{2n}}{a_{2n+1}}=\frac{a_{2n}}{a_{2n-2}+a_{2n}}=\frac{1}{\displaystyle{1+\frac{a_{2n-2}}{a_{2n}}}} =\frac{1}{\displaystyle{1+\frac{a_{2n-2}}{a_{2n-1}}\frac{a_{2n-1}}{a_{2n}}}}\, . $$

(30)

It is obvious that

$$\lim_{n\to \infty}\frac{a_{2n-2}}{a_{2n-1}}=\lim_{n\to \infty}\frac{a_{2n}}{a_{2n+1}}=\alpha_{1}\, , \hspace{.5cm} \lim_{n\to \infty}\frac{a_{2n-1}}{a_{2n}}=\lim_{n\to \infty}\frac{a_{2n+1}}{a_{2n+2}}=\alpha_{2}\, .$$

By taking the limit on both sides of (30) we obtain

$$\begin{array}{@{}rcl@{}} \alpha_{1}=\frac{1}{\displaystyle{1+\alpha_{1}\alpha_{2}}},&\text{implying~that}& {\alpha_{1}^{2}} \alpha_{2} +\alpha_{1} -1=0\, . \end{array} $$

Similarly, it follows from (9) that

$$\begin{array}{@{}rcl@{}} \frac{a_{2n+1}}{a_{2n+2}}=\frac{a_{2n+1}}{a_{2n-1}+a_{2n}}=\frac{1}{\displaystyle{\frac{a_{2n-1}}{a_{2n+1}}+\frac{a_{2n}}{a_{2n+1}}}} =\frac{1}{\displaystyle{\frac{a_{2n-1}}{a_{2n}}\times \frac{a_{2n}}{a_{2n+1}}+\frac{a_{2n}}{a_{2n+1}}}}\, , \end{array} $$

and hence

$$\begin{array}{@{}rcl@{}} \alpha_{2}=\frac{1}{\displaystyle{\alpha_{2} \alpha_{1} +\alpha_{1}}},&\text{implying~that}& \alpha_{1} {\alpha_{2}^{2}} +\alpha_{1} \alpha_{2}-1=0\, . \end{array} $$

Thus, we have the following two relations between α ₁ and α ₂

$$ \left\{ \begin{array}{ccc} {\alpha_{1}^{2}} \alpha_{2} +\alpha_{1} -1 &=& 0\, , \\ \alpha_{1} {\alpha_{2}^{2}} +\alpha_{1} \alpha_{2}-1 &=& 0\, . \end{array} \right. $$

(31)

Using the Maple library SolveTools, we obtained the following solution for the system given by (31)

$$\alpha_{1} = 0.64779887126104238549,~~~\alpha_{2}= 0.83928675521416113255, $$

which are the same numbers obtained previously by simulation. $\ \Box$

Note that in general, for p ≥ 2 we need not form the fractions considered in Theorem 5, as the α _i can be computed directly using (28). As an example, for p = 10 the system of equations given by (28) is

$$ \left\{\small{ \begin{array}{lcc} {\alpha_{1}^{2}} \alpha_{2} \alpha_{3} \alpha_{4} \alpha_{5}\alpha_{6} \alpha_{7} \alpha_{8} \alpha_{9} \alpha_{10}+\alpha_{1}-1 &=& 0\, , \\ &&\\ \alpha_{1} {\alpha_{2}^{2}} \alpha_{3} \alpha_{4} \alpha_{5}\alpha_{6} \alpha_{7} \alpha_{8} \alpha_{9} \alpha_{10}+\alpha_{1} \alpha_{2}-1 &=& 0\, , \\ &&\\ \alpha_{1} \alpha_{2} {\alpha_{3}^{2}} \alpha_{4} \alpha_{5}\alpha_{6} \alpha_{7} \alpha_{8} \alpha_{9} \alpha_{10}+\alpha_{1} \alpha_{2} \alpha_{3} -1&=& 0 \, ,\\ &&\\ \alpha_{1} \alpha_{2} \alpha_{3} {\alpha_{4}^{2}} \alpha_{5}\alpha_{6} \alpha_{7} \alpha_{8} \alpha_{9} \alpha_{10}+\alpha_{1} \alpha_{2} \alpha_{3} \alpha_{4} -1&=& 0\, , \\ &&\\ \alpha_{1} \alpha_{2} \alpha_{3} \alpha_{4} {\alpha_{5}^{2}}\alpha_{6} \alpha_{7} \alpha_{8} \alpha_{9} \alpha_{10}+\alpha_{1} \alpha_{2} \alpha_{3} \alpha_{4} \alpha_{5} -1&=& 0\, ,\\ &&\\ \alpha_{1} \alpha_{2} \alpha_{3} \alpha_{4} \alpha_{5}{\alpha_{6}^{2}} \alpha_{7} \alpha_{8} \alpha_{9} \alpha_{10}+\alpha_{1} \alpha_{2} \alpha_{3} \alpha_{4} \alpha_{5}\alpha_{6} -1&=& 0\, ,\\ &&\\ \alpha_{1} \alpha_{2} \alpha_{3} \alpha_{4} \alpha_{5}\alpha_{6} {\alpha_{7}^{2}} \alpha_{8} \alpha_{9} \alpha_{10}+\alpha_{1} \alpha_{2} \alpha_{3} \alpha_{4} \alpha_{5}\alpha_{6} \alpha_{7}-1&=& 0\, ,\\ &&\\ \alpha_{1} \alpha_{2} \alpha_{3} \alpha_{4} \alpha_{5}\alpha_{6} \alpha_{7} {\alpha_{8}^{2}} \alpha_{9} \alpha_{10}+\alpha_{1} \alpha_{2} \alpha_{3} \alpha_{4} \alpha_{5}\alpha_{6}\alpha_{7}\alpha_{8} -1&=& 0\, ,\\ &&\\ \alpha_{1} \alpha_{2} \alpha_{3} \alpha_{4} \alpha_{5}\alpha_{6} \alpha_{7} \alpha_{8} {\alpha_{9}^{2}} \alpha_{10}+\alpha_{1} \alpha_{2} \alpha_{3} \alpha_{4} \alpha_{5}\alpha_{6}\alpha_{7}\alpha_{8}\alpha_{9} -1&=& 0\, \\ &&\\ \alpha_{1} \alpha_{2} \alpha_{3} \alpha_{4} \alpha_{5}\alpha_{6} \alpha_{7} \alpha_{8} \alpha_{9} \alpha_{10}^{2}+\alpha_{1} \alpha_{2} \alpha_{3} \alpha_{4} \alpha_{5}\alpha_{6}\alpha_{7}\alpha_{8}\alpha_{9}\alpha_{10} -1&=& 0\, , \end{array}} \right. $$

(32)

and the corresponding solution is

$$\begin{array}{ccc} \alpha_{1}=0.666612258007018789\, , & \alpha_{2}=0.857092885579025346\, , & \\ &&\\ \alpha_{3}=0.93329632841073983391\, , & \alpha_{4}=0.9677169599982014719\, , & \\ &&\\ \alpha_{5}=0.98411106201310646160\, , & \alpha_{6}=0.992116233407534976\, , & \\ &&\\ \alpha_{7}=0.9960726364976549641\, , & \alpha_{8}=0.998039687795641184\, , & \\ &&\\ \alpha_{9}=0.99902056413293093583\, , & \alpha_{10}=0.99951040197828549144\, . & \end{array} $$

7 Error detection and correction

The error correction algorithm for Fibonacci coding is described in [6]. This method also applies to the codes in this paper. To make the paper more self contained, we explain this decoding method here. An example illustrating the method is given at the end of this section.

It follows from $E=M{M_{p}^{n}}$ that

$$ \begin{array}{c} \det(E)=\det(M) \times \det({M_{p}^{n}})=(-1)^{np}\det(M). \end{array} $$

(33)

When matrix E is transmitted and a matrix $\hat E$ is received, (33) provides a means of detecting if an error has occurred. We say that there are no errors if this relation is satisfied. For a conventional linear code with parity check matrix H, a received word x is a codeword if and only if H x = 0. Hence the error detecting role of (33) is similar to that of the parity check matrices of linear codes. If $\det (M)$ is transmitted several times, using an algorithm such as majority logic decoding it can be assumed that it is received correctly. Therefore, (33) can be used as an error detection criterion for the entries of $\hat E$. More precisely, we say that no error has occurred if and only if (29) (similarly for the other rows of $\hat E$), and (33) are satisfied.

Suppose that there are errors in $\hat E$. This matrix can contain one-fold, two-fold, …, or (p+1)²-fold errors. The error correcting process is explained for the case p = 2 (the other cases are similar), and hence $\det (E)=\det (M) \times \det ({M_{p}^{n}})=(-1)^{2n}\det (M)=\det (M)$. Among the possible correctable error patterns, due to the similarity of the arguments, we consider the case of a single error, double error or eight errors.

Case 1

Suppose that one matrix element has been received in error. Using (33), each entry e _i of $\hat E$ can be expressed in terms of the other entries of E and $\det (M)$. Denoting the elements of $\hat E$ by e _i , we have the following system of equations

$$ \begin{array}{ccl} e_{1}&=&\left( e_{2}(e_{4}e_{9}-e_{6}e_{7})-e_{3}(e_{4}e_{8}-e_{5}e_{7})+\det(M)\right)/(e_{5}e_{9}-e_{6}e_{8}),\\ e_{2}&=&\left( e_{1}(e_{6}e_{8}-e_{5}e_{9})-e_{3}(e_{4}e_{8}-e_{5}e_{7})+\det(M)\right)/(e_{6}e_{7}-e_{4}e_{9}),\\ \vdots&&\\ e_{9}&=&\left( e_{7}(e_{3}e_{5}-e_{2}e_{6})+e_{8}(e_{1}e_{6}-e_{3}e_{4})+\det(M)\right)/(e_{1}e_{5}-e_{2}e_{4}). \end{array} $$

(34)

Assuming that only e _i is received in error, among the nine equations in (34), only the right-hand-side of the ith equation will be an integer. This indicates that e _i is in error, and the corresponding correct value is the right-hand-side of the ith equation.

Case 2

If Case 1 fails, there are $\left (\begin {array}{c}{9}\\{2} \end {array}\right )=36$ double error patterns.

Case 2.1

(Two errors in the same row) Suppose $\hat E$ contains two errors in the same row, for example the first two entries of the third row. Denoting these entries by x and y and using (21), we have that x = α y. Replacing x by α y in (33), i.e. $e_{1}(e_{5}e_{9}-e_{6}y)-e_{2}(e_{4}e_{9}-e_{6}x)+e_{3}(ye_{4}-xe_{5})=\det (M)$, we first obtain y and then x. Alternatively, we may set x = α β e ₉ and y = β e ₉, and then check the validity of (33).

Case 2.2

(Two errors in the same column) Suppose e ₄ and e ₆, denoted by x and y, respectively, are in error and the other entries are correct. It follows from (21) that x = α e ₅ and y = α e ₈.

Case 2.3

(Two errors in different columns and rows) Without loss of generality, suppose that e ₄ and e ₇, denoted by x and y, respectively, are in error. Using (21) we have that x = α e ₅ and y = β e ₉. Note that, in general, the locations of the erroneous symbols are not known and hence only if (21) and (33) are satisfied by these values for x and y and the other received symbols can it be said that the 4th and 7th entries have been received in error. The corresponding correct values at these positions are α e ₅ and β e ₉, respectively.

Case 8

(Eight error patterns) Assume that among the nine entries of $\hat E$ only e ₉ is correct. Then using (21), the correct values of e ₇ and e ₈ are obtained. Next, using the relations e ₁ = α e ₂, e ₂ = β e ₃, and e ₁/e ₇ = e ₂/e ₈ = e ₃/e ₉, the equations x α/e ₇ = x/e ₈ and y β/e ₈ = y/e ₈ are solved to obtain x = e ₂, y = e ₃ and e ₁ = α e ₂. The same process is applied to obtain e ₄, e ₅ and e ₆.

Example 1

Consider the message matrix M, the encoder matrix $M_{2}^{25}$ and the corresponding encoded matrix E, and suppose that E is transmitted and $\widehat {E}$ is received

$$M=\left( \begin{array}{ccc}358&965&741 \\ 652&715&347 \\ 354&876&785 \end{array}\right)~~~ M_{2}^{25}=\left( \begin{array}{ccc}410744&634061&755476 \\ 755476&1166220&1389537 \\ 1389537&2145013&2555757 \end{array}\right) $$

$$E=M\times M_{2}^{25}=\left( \begin{array}{ccc}1905727609&2941850771&3505179550 \\ 1290139767&1991574583&2372936986 \\ 1897986897&2929901519&3490942161 \end{array}\right) $$

$$\widehat{E}=\left( \begin{array}{ccc}3568745203&9856412580&3505179550 \\ 1290139767&1991574583&2372936986 \\ 1897986897&2929901519&3490942161 \end{array}\right) $$

Clearly, the first two entries of the first row of E have been received in error. It is easily checked that (33) is not satisfied indicating that some entries of $\widehat {E}$ are incorrect. Further, none of the nine single-error patterns gives the transmitted matrix E.

Using Table 1 and setting e ₁/e ₂ = α = 0.64779887126 and e ₂/e ₃ = β = 0.83928675521, $\hat {e_{3}} \times \alpha \beta =3505179550 \times 0.54368901269\approx 1905727609$, and hence we set e ₁ = 1905727609. Further, $\hat {e_{3}}\times \beta =3505179550 \times 0.8392867552\approx 2941850771$, so that we may set e ₂ = 2941850771. These values for e ₁ and e ₂ together with the other elements of $\widehat {E}$ satisfy (33). The same process applied on a pair of entries of $\widehat E$ distinct from (e ₁, e ₂) does not produce a matrix satisfying (33).

Code rate and error-correcting capability

Based on the given decoding algorithm, for n sufficiently large, all error-patterns of size less than (p+1)² are correctable. The number of nonzero error-patterns is

$$\left( \begin{array}{c}{(p+1)}^{2}\\{1} \end{array}\right) +\left( \begin{array}{c}{{(p+1)}^{2}}\\{2} \end{array}\right)+\cdots+\left( \begin{array}{c}{{(p+1)}^{2}}\\ {{(p+1)}^{2}} \end{array}\right)=2^{{(p+1)}^{2}}-1\, . $$

Hence the percentage of correctable error-patterns is $\frac {2^{{(p+1)}^{2}}-2}{2^{{(p+1)}^{2}}-1}\,$, and this number for p = 2 is $\frac {2^{{(2+1)}^{2}}-2}{2^{{(2+1)}^{2}}-1}=\frac {510}{511}=0.998\,$.

Let L ₁ and L ₂ be the average number of decimal digits in the entries of the message matrix M and encoding matrix ${M_{p}^{n}}$, respectively. Then the average number of decimal digits in the entries of the encoded matrix E is almost L ₁ + L ₂. Hence the code rate is $\frac {L_{1}}{L_{1}+L_{2}}$.

Consider an encoded matrix E, and suppose ℓ _i , 1 ≤ i≤(p+1)², is the number of decimal digits in the ith entry of E, and set ℓ = (ℓ ₁ + ℓ ₂+⋯ + ℓ _m )/m where m = (p+1)². Suppose the channel error probability per decimal symbol is q. Then the probability of receiving the ith entry of matrix E with no errors is $(1-q)^{\ell _{i}}$ since the decimal length of this entry of E is ℓ _i and each decimal symbol is received correctly with probability 1−q. This implies that all entries of E are received in error with probability ${\Pi }_{i=1}^{m}(1-a^{\ell _{i}})$ where a = 1−q. Hence the probability of correctly decoding a received matrix $\widehat {E}$, which is equivalent to receiving at least one entry of E without error, is $P_{ec}=1-{\Pi }_{i=1}^{m}(1-a^{\ell _{i}})$.

Note that ${\Pi }_{i=1}^{m}(1-a^{\ell _{i}})\leq (1-a^{\ell })^{m}$, as this inequality is equivalent to ${\Sigma }_{i=1}^{m} \ln (1-a^{\ell _{i}})\leq m\ln (1-a^{\ell })$, and this inequality can be proven by applying Jensen’s inequality, E[F(Y)] ≤ F(E[Y]), on the function $F(y)= \ln (1 - a^{y})$. Hence P _{e c} ≥ 1−(1−a ^ℓ)^m.

8 Summary

A new class of square matrices was introduced that extends Fibonacci coding theory. For a given positive integer p, a (p+1)×(p+1) matrix M _p was defined. The matrices ${M_{p}^{n}}$, the nth power of M _p , and $M_{p}^{-n}$ were used as the encoding and decoding matrices, respectively. The most important property of M _p is that ${M_{p}^{n}}$ has determinant (−1)^np. Both ${M_{p}^{n}}$ and $M_{p}^{-n}$ have a simple closed-form expression. It was shown that for n sufficiently large, there exist relations among the entries of the encoded matrix that allow for error correction.

Appendix

This appendix provides a proof of the existence of a unique real solution for the system of equations given by (28). By setting u = α ₁ α ₂⋯α _p , the system of equations given by (28) is changed to

$$\left\{ \begin{array}{ccl} \frac{1}{\alpha_{1}} &=& 1+u \, ,\\ &&\\ \frac{1}{ \alpha_{1} \alpha_{2}} &=& 1+u+u^{2} \, ,\\ &&\\ \frac{1}{\alpha_{1} \alpha_{2} \alpha_{3}}&=& 1+u+u^{2}+u^{3}\, , \\ &&\\ {\vdots} & & {\vdots} \\ &&\\ \frac{1}{\alpha_{1} \alpha_{2} {\cdots} \alpha_{p}}&=& 1+u+u^{2}+{\cdots} +u^{p}\, , \end{array} \right. $$

so that in general

$$\frac{1}{\alpha_{1} \alpha_{2} {\cdots} \alpha_{k}}=1+u+u^{2}+{\cdots} +u^{k},~~~1\leq k\leq p. $$

It follows from $\frac {1}{\alpha _{1} \alpha _{2} {\cdots } \alpha _{p}}= 1+u+u^{2}+{\cdots } +u^{p}$ that $\frac {1}{u}= 1+u+u^{2}+{\cdots } +u^{p}$ and hence u ≠ 1. From

$$\alpha_{k}=\frac{\frac{1}{\alpha_{1} \alpha_{2} {\cdots} \alpha_{k-1}}}{\frac{1}{\alpha_{1} \alpha_{2} \cdots \alpha_{k-1} \alpha_{k}}} =\frac{1+u+u^{2}+{\cdots} +u^{k-1}}{1+u+u^{2}+{\cdots} +u^{k}}, $$

we have that

$$\alpha_{k}=\frac{(u-1)(1+u+{\cdots} +u^{k-1})}{(u-1)(1+u+{\cdots} +u^{k})} =\frac{u^{k}-1}{u^{k+1}-1}. $$

This results in

$$u=\alpha_{1} \alpha_{2} {\cdots} \alpha_{p}=\frac{u-1}{u^{2}-1} \times \frac{u^{2}-1}{u^{3}-1}{\cdots} \frac{u^{p}-1}{u^{p+1}-1}= \frac{u-1}{u^{p+1}-1}, $$

and hence

$$u^{p+2}=2u-1. $$

A real solution for this equation is u = 1 which is not acceptable as mentioned above. For an even number p, the function y ₁(u) = u ^p+2 is concave, and the two functions y ₁(u) = u ^p+2 and y ₂(u) = 2u−1 are equal at u = 1 and a number in (0, 1), so the latter is the desired solution. If p is odd, y ₁(u) = u ^p+2 is negative for u < 0, and y ₁(u) = u ^p+2 and y ₂(u) = 2u−1 intersect at u = 1, a number in (0,1) and a number in $(-\infty , 0)$. As the α _i are positive, a negative solution for (28) is not acceptable, so (28) has a unique real solution. This argument provides the following method for solving (28). First find a real solution for u ^p+2−2u+1=0 in the interval (0,1), and then compute α _k by making use of $\alpha _{k}=\frac {u^{k}-1}{u^{k+1}-1}$.