Как исправлять ошибки?

Покажем теперь возможность восстановления кодового сообщения E используя свойства детерминанта "фибоначчиевой" Q-матрицы. Продолжим рассмотрение примера из предыдущих страниц Музея, когда исходное сообщение представляется в матричной форме:

(1)

Детерминант матрицы (1) равен:

Det M = m1m4 - m2m3.(2)

Пусть матрица Q5 выбрана для "фибоначчиевого" кодирования. Тогда кодовая матрица E принимает следующий вид:

(3)

Существо восстановления "разрушенной" кодовой матрицы состоит в следующем. После "конструирования" кодовой матрицы E вычисляется детерминант исходной матрицы M согласно (2). Детерминант посылается в "канал" после кодового сообщения

Предположим, что "канал" имеет специальные средства для обнаружения ошибок в каждом из элементов кодового сообщения E. Предположим, что обнаружена ошибка в первом элементе матрицы E. Тогда мы можем представить "разрушенное" кодовое сообщение в следующем виде:

(4)

где x есть "разрушенный" элемент кодового сообщения E, а остальные элементы матрицы должны быть корректными и равными следующим значениям:

(5)

Тогда согласно свойствам "фибоначчиевого" кодирования для случая кодирующей матрицы Q5 детерминант матрицы М' должен быть равным детерминанту (2) с противоположным знаком. Тогда мы можем записать следующее уравнение для вычисления "разрушенного" элемента x:

(6)

После выполнения элементарных математических преобразований над уравнением (6) мы можем получить решение уравнения (6) в виде:

x = 8m1 + 5m2.(7)

Сравнивая вычисленное значение (7) с элементом кодовой матрицы E, задаваемой (3), мы можем сделать следующее важное заключение:

x = .

Таким образом, мы восстановили кодовое сообщение E, используя свойства детерминанта "фибоначчиевой" матрицы Q!

Но в реальных ситуациях мы обычно не знаем, какие элементы кодового сообщения "разрушены". Рассмотрим численный пример из предыдущей страницы нашего Музея, когда кодирующая матрица Q5, исходная матрица M и кодовая матрица E имеют следующий вид соответственно:

(8)
(9)
(10)

и имеет место следующее соотношение для детерминантов:

Det E = - Det M.(11)

Предположим, что после сравнения детерминантов Det E и Det M мы нашли, что оно не соответствует соотношению (11), что является признаком ошибки в кодовой матрице (10). Но мы не имеем информации относительно "разрушенного" элемента матрицы (10). В этом случае мы можем предложить различные "гипотезы" относительно возможного "разрушенного" элемента и после этого мы можем проверить все эти "гипотезы". Однако мы имеем еще одно условие для элементов кодовой матрицы E: все ее элементы должны быть целыми числами. Вот почему мы можем выбирать как достоверные только те результаты проверки наших "гипотез", которые приводят нас к целым числам. Наконец, если наши тесты не приводят к целым числам ни в одном из тестов, это означает, что возможная ошибка возникла в двух, трех или четырех элементах нашей кодовой матрицы и такая ошибка не может быть скорректированной.

И сейчас мы подведем итог нашему рассмотрению нового метода кодирования, основанного на "фибоначчиевой" Q-матрице. Мы рассмотрели весьма необычный метод! В нашем методе объектами обнаружения и исправления ошибок являются элементы матрицы E! Мы корректируем не отдельные биты или их комбинации в двоичных кодах, как это принято в классической теории кодирования, а числа, являющиеся элементами матриц. И наконец, мы используем необычный математический аппарат для нашей теории кодирования, а именно теорию матриц и теорию чисел Фибоначчи. И мы показали, что мы можем корректировать элементы матриц, которые могут быть числами огромной величины (например, двоичными числами длины 106 или 1012 бит, что невозможно в классической теории кодирования)! Вот почему рассмотренный выше метод имеет принципиальную важность для теории корректирующих кодов. И если вас заинтересует наша теория кодирования, мы готовы сотрудничать с вами в направлении software и hardware реализации "фибоначчиевого" метода кодирования. Обращайтесь к нам!