Примитивные (образующие) полиномы и их использование в помехоустойчивых циклических кодах

5. Примитивные (образующие) полиномы и их использование в помехоустойчивых циклических кодах. Определение количества проверочных символов в словах помехоустойчивых кодов Проверочные символы, добавляемые к информационным в сообщении нам необходимы для устранения потенциальных ошибок. Всегда предполагается, что ошибочных символов гораздо меньше, чем правильных, т. е. вероятность р ошибки в каждом отдельно взятом бите сообщения много меньше 0,5, иначе никакие математические методы не помогут в восстановлении информации. Мы разбиваем наше сообщение на небольшие порции равной длины n и смеем надеяться, что, в силу малости р, количество ошибок в этой порции мало, например, не более 1 или не более двух. (И далее строим алгоритм, который в этом предположении позволяет найти позиции ошибочных символов и изменить их на противоположные.) К сожалению, в реальной жизни сразу такое предположение даже при малости р неоправданно, т. к. места ошибок в сообщении не представляют собой простейший поток событий. Напротив, ошибки имеют тенденции группироваться. К примеру, если на коротком промежутке времени на канал передачи сообщений воздействует молния, то появится много подряд идущих ошибочных битов. Выходом из этой ситуации является предварительное блочное кодирование: записываем наш вектор данных по строкам в матрицу, а затем считываем информацию по столбцам (транспонируем). В этом случае происходит рассредоточение ошибок. После восстановления данных снова транспонируем матрицу: Теперь в каждой порции из n символов мы должны разместить r проверочных бит. Оставшиеся k = n – r будут информационными (такой код называют [n, k]-кодом), они могут принимать любые значения. Хотя в сообщении, написанном на русском языке, информационные символы – буквы нашего алфавита – не могут образовывать совсем уж любую последовательность, многие буквосочетания неприемлемы, и именно это и делает такое сообщение до определённой степени помехозащищённым, т. е. редкие ошибки часто удаётся однозначно исправить, но не всегда! Проверочные символы вычисляются через информационные. Идея состоит в том, что каждая единичная ошибка (она может быть и в проверочном символе) в слове из n символов приводила бы к недопустимой комбинации, которую можно было б однозначно отнести к 1-окрестности некой допустимой комбинации, в том смысле, что расстояние t между ними (т. е. число бит, где они отличаются) было равно 1. В таком случае очевидно, что необходимым условием однозначного исправления ошибки будет то, что расстояние между любыми двумя допустимыми словами d было не меньше 3. Возвращаясь к русскому языку, мы видим, что там это условие конечно же не выполняется. А как было б хорошо для программы проверки грамматики: встретив слово, которого нет в словаре, она просто перебрала бы все слова, отличающиеся от него на одну букву, и, найдя единственное слово, без помощи человека сама исправила бы ошибку. Но русский язык, как и все ему подобные, придумывался задолго до того, как человечество всерьёз взялось за решение подобных задач. Продемонстрируем сказанное на примере самого простого из возможных помехоустойчивых кодов – повторного кода типа [3, 1]. Оба проверочных символа просто дублируют информационный. Таким образом мы имеем всего 2 допустимые комбинации из 8 возможных: 000 и 111, расстояние между ними равно 3. Остальные 6 недопустимых комбинаций группируются вокруг одной из этих двух, именно той, которая отличается от них на 1 символ. О различных помехоустойчивых кодах: https://habr.com/ru/post/111336/; http://ie.tusur.ru/books/COI/page_08.htm. Теперь, предположив, что нам удалось таким хитрым образом сконструировать помехоустойчивый код, посчитаем, какое минимальное количество проверочных символов должно быть в слове длиною n бит. Всё-таки двукратное дублирование информации, описанное выше, выглядит несколько расточительно. Причина состояла в том, что мы взяли достаточно короткое слово. В общем случае, слово длины n можно брать, когда мы уверены, что . Из r бит мы сможем составить 2r различных комбинаций. В то же время при получении слова, в котором допущена 1 или 0 ошибок, мы имеем возможных комбинаций, которые надо суметь распознать. Поэтому необходимым условием на r будет: . Скажем, четырьмя проверочными символами можно «обслужить» 11 информационных в слове, неплохой результат, но это при условии, что мы будем уверены, что вероятность ошибочного символа будет порядка 1%. Если же мы собираемся построить код, умеющий распознавать в слове не более двух ошибок, у нас получится более стргое условие на r: . Возьмём например . Тогда на r имеем неравенство: . Кодом с минимальной длиной слова будет код [5, 1]. Конечно его, так же как и выше, можно сделать повторным. Определение необходимого количества избыточных символов: http://peredacha-informacii.ru/ opredelenie-neobhodimogo-kolichestva-izbytochnyh-simvolov.html. Неприводимые и образующие многочлены Для построения циклических кодов нам потребуются многочлены из Z2[x], обладающие определёнными свойствами. Далее для краткости будем записывать такой многочлен набором его коэффициентов в скобках, т. е. . Применим алгоритм Берлекэмпа, чтобы определить, какие из трёх многочленов: 4-й степени (10011), (10111) и (11111) являются неприводимыми. Напомним, что на первом этапе необходимо проверить, имеют ли многочлены кратные делители. Это будет в том случае, когда и их производные имеют такие же делители. Удостоверимся, что в каждом из этих случаев НОД(P,DP) = = (1): D(10011) = D(10111) = (0001), D(11111) = (0101). В первых двух случаях мы автоматически это получили, а для третьего многочлена достаточно сделать 1 шаг алгоритма Эвклида: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 На втором этапе находим остатки от деления (1), (100), (10000) и (1000000) на многочлены и записываем их строками в матрицы 4×4, только коэффициенты в этом случае нужно записать по возрастанию степеней. Транспонировав эти матрицы, получаем матрицы Берлекэмпа В для этих многочленов. В наших случаях они выглядят так: Теперь нужно находить собственные вектора, соответствующие собственному числу 1. Конечно всегда будет собственный вектор , Но он нас не интересует, т. к. соответствует множителю (0001), который есть у каждого многочлена. А вот есть ли другие собственные вектора и соответственно др. делители у этих многочленов будет зависеть от ранга В – Е. Выпишем миноры M41 у этих матриц: . Первый и последний не равны 0, что означает неприводимость многочленов (10011) и (11111). А вот второй равен 0 Линейно независимый с собственный вектор будет ещё один: . Это значит, что у (10111) есть делитель вида (110с), разложение находим делением столбиком: 1 1 1 1 1 1 с 1 1 с 1 1 1 1 1–с 1 1 1 с 1–с 1–с Для того, чтоб остатка не было, нужно взять с = 1: (10111) = (1101)(11). Интересно, что количество неприводимых многочленов степени r в Z2[x] определяется так называемой формулой Мёбиуса: где , В частности, . Ещё одним неприводимым многочленом степени 4 является (11001). Задача. Напишите программу, считающую число неприводимых многочленов для произвольного r. Для построения циклических кодов подойдут не любые неприводимые многочлены. Нужны такие, которые дадут полный набор 2r – 1 = 15 ненулевых остатков от деления на него xn. Эти многочлены называются образующими (примитивными). Такому условию удовлетворяет из рассматриваемых только (10011). Выпишем остатки (10011), они нам пригодятся. Их ещё называют синдромами. 1 Остатки: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 Для многочлена (11111) имеем только 5 различных остатков: Остатки: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 Многочлен (11001) также является образующим. Об образующих многочленах: https://studopedia.ru/3_23317_poluchenie-ostatkov- dlya-strok-edinichnoy-transponirovannoy-matritsi.html; https://studref.com/365833/tehnika/primitivnyy_mnogochlen. Алгоритм шифрования сообщения и исправления одной ошибки Покажем, как строится циклический код, и реализуем его. Следует понимать, что для правильного кодирования (добавления проверочных символов) и декодирования (исправления возможной ошибки в слове с последующим отбрасыванием проверочных символов) требуется знать конкретный образующий многочлен Р. Пусть Q – многочлен степени не выше k, соответствующий информационному сообщению, которое нужно передать. Тогда проверочным символам соответствует многочлен R = xrQ mod P, приписываемый справа от Q. Для обнаружения места потенциальной ошибки в переданном сообщении F требуется последовательно сравнить F mod P с синдромами xn mod P. Номер совпадающего синдрома соответствует степени многочлена F, считая с нулевой, где стоит неверный коэффициент. Если , то ошибки нет. Исправление ошибки для двоичного кода просто: заменяем неверный символ на противоположный. Задание. Проделав всё описанное выше для многочлена Р = (111), убедитесь, что получается уже упомянутый код. Примеры кодирования сообщений с Р = (10011): • Q = (1001001100). Если k = 10, то видно, что минимальным натуральным числом r, удовлетворяющим неравенству: , будет r = 4. Значит, нам достаточно нашего многочлена 4-й степени. Мы здесь и далее используем код [15, 11]. Если не хватает в слове информационных символов, то всегда можно считать, что старший коэффициент многочлена Q равен 0, т. к. на остатки деления на Р это не повлияет: (010010011000000) mod P = = (1101). Тогда F = (10010011001101). Декодирующий сообщение тоже может считать, что к слову F впереди нужно добавить ещё 0. Если это сообщение будет передано без ошибки, то получивший сможет в этом убедиться, разделив F на Р без остатка. • Q = (01100011010). (011000110100000) mod P = (1010). Следовательно, передаваемым словом должно быть F = (011000110101010). Примеры декодирования сообщений с Р = (10011): • F = (1010101111010). Трёх проверочных символов здесь было бы недостаточно, т. к. . Отталкиваемся от того, что при кодировании использован (10011). Вычисляем первым делом F mod P = (1110). Обращаясь к таблице синдромов этого многочлена видим, что такой остаток стоит на 12-м месте, следовательно, инвертировать необходимо 12-й справа символ: Q = = (111010111). Если бы остаток оказался, например, (1101), это показывало, что ошибка у нас в мнимом символе, которого нет, а в F ничего заменять не надо, просто отбросить последние 4 бита. В том случае, когда остаток совпадает с одним из первых четырёх синдромов, – ошибка коснулась проверочного символа, – также следует просто отбрасывание. • F = (10101111101010). Здесь также используется код [15, 11]. 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 F mod P = (0111), изменению подлежит 11-й справа символ: Q = = (1011111110). • F = (101111110101010). F mod P = (0111), остаток тот же, но инвертировать необходимо уже бит не на 4-м (слева) месте, а на 5-м: Q = (10110111010). Посмотреть на видео примеры для кода [15, 11] c P = (10011): https://www.youtube.com/watch?time_continue= 170&v=2BfjAIJjneQ&feature=emb_logo. Задача. Написать программы, кодирующие и декодирующие сообщения определённой длины с помощью образующего полинома 3-й степени.