Error detection

One of the coding theory aims is the detection and correction of errors arising in the code message E under influence of "noise" in the "communication channel".

And now we will show how detect errors in the code message by using the Fibonacci coding. The main idea is using the property of the matrix determinant as the check criterion of the transmitted message E. We remember that the determinant of the coding Qn-matrix is given with the following expression:

Det Qn = (-1)n.(1)

Let's demonstrate this idea for the example of interpretation of the message M as the 2 ´ 2 matrix of the following kind:

(2)

We know from the preceding pages of our Museum that the determinant of the matrix (2) can be calculated according to the following formula:

Det M = m1m4 - m2m3.(3)

Let's consider now the determinant of the code message E = M ´ Qn represented in the matrix form. According tÓ the matrix theory we have:

Det E = Det [M ´ Qn] = Det M ´ Det Qn.(4)

Using (1) we can write the expression (4) in the following form:

Det E = Det M ´ (-1)n.(5)

The formula (5) shows that the determinants of the initial matrix (Det M) and the code matrix (Det E) are connected by the very simple correlation. The formula (5) means that the determinant of the transmitted message E is equal to the determinant of the initial message M by the absolute value. The sign of the determinant of the message E depends on the number n. If the number n is even then we have:

Det E = Det M.(6)

If the number n is odd then we have:

Det E = - Det M.(7)

The identities (5), (6), (7) underlay the basis of the new method of the error detection based on the application of the Fibonacci Q-matrix. The essence of the method consists of the following. The sender calculates the determinant of the initial message M represented in the matrix form (1) and sends it to the channel after the code message E. The receiver calculates the determinant of the code message E and compares the latter with the determinant of the initial message of M received from the channel. If this comparison corresponds to (6) or (7) it means that the code message E is correct and the receiver can decode the code message E.

Let's demonstrate this method for the above-considered example. The determinant of the initial message is determined according to (3). We will use the Q5-matrix for coding. Then, according to (7) the determinant of E has to be equal to

Det E = - Det M = - (m1m4 - m2m3).

Really, we have:

Det M ´ Q5 = Det =

= (8m1 + 5m2)(5m3 + 3m4) - (5m1 + 3m2)(8m3 + 5m4) =

= 40m1m3 + 24m1m4 +25m2m3 +15m2m4 - 40m1m3 - 25m1m4 - 24m2m3 - 15m2m4 =

= - m1m4 + m2m3 = - Det M.
(8)

It means that the code message E is correct and we can decode the code message E.

Let's consider now the numerical example considered in the preceding page of our Museum. Let's suppose that the initial matrix has the following form:

(9)

The determinant of (9) is equal to

Det M = 358 ´ 725 - 466 ´ 91 = 259550 - 42406 = 217144.(10)

Then after the Fibonacci coding by means of the multiplication by the coding matrix Q5 we get the following code matrix

(11)

Its determinant is equal to

Det E = 3319 ´ 4505 - 7353 ´ 2063 = 14952095 - 15169239 = - 217144.(12)

Let's compare the calculation results (10) and (12). We can see that Det E = - Det M that corresponds to (8). This means that the code matrix E is correct and we can decode it by means of its multiplication by the "inverse" matrix of Q -5.

Let's consider the case when the code matrix (11) is destroyed in process of its transmission through the "communication" channel. Lets suppose the "destruction" of the matrix (11) consists of the fact that one of the entries differs from the initial value. For example the first entry 3319 takes the value 2076.

Let's consider now the "destroyed" matrix

(13)

Let's calculate the determinant of the matrix (13):

Det E' = 2076 ´ 4505 - 7353 ´ 2063 = 9352380 - 15169239 = - 5816859.(14)

Comparing (14) and (10) we can see that this douse not correspond to the fundamental condition (8) and hence the matrix (13) is not correct.

However, the error detection is only the first step in communication of messages. We should correct the error in the code message. And we will show at the next page of our Museum how this can be made. Follow us!