Как обнаруживать ошибки?

Одна из целей теории кодирования состоит в обнаружении и коррекции ошибок, возникающих в кодовом сообщении E под влиянием "помех" в "канале".

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

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

Продемонстрируем нашу идею на примере интерпретации сообщения M как квадратной (2 ´ 2)-матрицы следующего вида:

(2)

Мы знаем из предыдущих страниц нашего Музея, что детерминант матрицы (2) может быть вычислен согласно следующей формуле:

Det M = m1m4 - m2m3.(3)

Рассмотрим теперь детерминант кодового сообщения E = M ´ Qn, представленного в матричной форме. Согласно теории кодирования мы имеем:

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

Используя (1), мы можем записать выражение(4) в следующем виде:

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

Формула (5) показывает, что детерминанты исходной матрицы (Det M) и кодовой матрицы (Det E) связаны очень простым соотношением. Формула (5) означает, что детерминант переданного сообщения E равен детерминанту исходного сообщения M по абсолютной величине. Знак детерминанта сообщения E зависит от числа n. Если число n четное, тогда мы имеем:

Det E = Det M.(6)

Если число n нечетное, тогда мы имеем:

Det E = - Det M.(7)

Математические тождества (5), (6), (7) лежат в основе нового метода обнаружения ошибок, основанного на применении "фибоначчиевой" Q-матрицы. Существо метода состоит в следующем. Отправитель вычисляет детерминант исходного сообщения M, представленного в матричной форме (1) и посылает его в "канал" после кодового сообщения E. Получатель вычисляет детерминант кодового сообщения E и сравнивает его с детерминантом исходного сообщения M, полученного из "канала". Если это сравнение соответствует (6) или (7), это означает, что кодовое сообщение E корректно и получатель может декодировать кодовое сообщение E.

Продемонстрируем этот метод на рассмотренном выше примере. Детерминант исходного сообщения определяется согласно (3). Мы будем использовать матрицу Q5 для кодирования. Тогда согласно (7) детерминант матрицы E должен быть равным

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

Действительно, мы имеем:

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)

Это означает, что кодовое сообщение E является корректным, и мы можем декодировать кодовое сообщение E.

Рассмотрим численный пример, рассмотренный на предыдущей странице нашего Музея. Пусть исходная матрица имеет следующий вид:

(9)

Тогда детерминант (9) равен:

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

После "фибоначчиевого" кодирования сообщения (9) путем умножения на кодирующую матрицу Q5 мы получаем следующую кодовую матрицу:

(11)

Ее детерминант равен:

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

Сравним теперь результаты вычислений (10) и (12). Мы видим, что Det E = - Det M, что соответствует контрольному соотношению (8). Это означает, что кодовая матрица E является корректной, и мы можем декодировать ее путем умножения на "обратную" матрицу Q -5.

Рассмотрим случай, когда матрица (11) оказалась "разрушенной" в процессе ее передачи через "канал". Пусть "разрушение" матрицы (11) состоит в том, что один из ее элементов отличается от исходного значения. Например, первый элемент 3319 принял значение 2076.

Рассмотрим теперь "разрушенную" матрицу

(13)

Вычислим детерминант матрицы (13):

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

Сравнивая (14) и (10), мы можем увидеть, что значения детерминантов матриц не соответствуют фундаментальному условию (8) и, следовательно, матрица (13) является некорректной.

Однако, обнаружение ошибок есть только первый шаг в передаче сообщений. Мы должны научиться корректировать ошибки в кодовом сообщении. И мы покажем на следующей странице нашего Музея, как это может быть сделано. Следуйте за нами!