Тема 1. Физиология и биохимия пищеварения

Задания для самостоятельной работы

Задания для аудиторной работы

Задание 1. Составить таблицу 8.2 образующих всех Г-орбит 15-мерных векторов-ошибок весом 1 – 3, их синдромов и норм синдромов в БЧХ-коде С₇ над полем с примитивным элементом корнем полинома

Решение.

Таблица 8.2.

Образующие Г-орбит ошибок веса 1, 2, 3 в пространстве , их синдромы и нормы синдромов
№ п/п	Образующая Г-орбиты	Синдром S()	Норма Г-орбиты
	(1)	(1, 1, 1)	(1, 1, 1)
	(1, 2)	(a^4, a^14, a^10)	(a^2, a^5, a^5)
	(1, 3)	(a^8, a^13, a^5)	(a^4, a^10, a^10)
	(1, 4)	(a^14, a^7, 0)	(a^10, 0, 0)
	(1, 5)	(a, a^11, a^10)	(a^8, a^5, a^5)
	(1, 6)	(a^10, 0, a^5)	(0, 1, ¥)
	(1, 7)	(a^13, a^14, 0)	(a^5, 0, 0)
	(1, 8)	(a^9, a^13, a^9)	(a, a^10, a^10)
	(1, 2, 3)	(a^10, a^8, 0)	(a^8, 0, 0)
	(1, 2, 4)	(a^7, a^4, a^5)	(a^13, 1, a^10)
	(1, 3, 4)	(a^13, a^10, a^10)	(a, a^5, a^10)
	(1, 2, 5)	(0, a^5, 1)	(¥, ¥, a^5)
	(1, 3, 5)	(a^5, a, 0)	(a, 0, 0)
	(1, 4, 5)	(a^9, a^2, a^5)	(a^5, a^5, a^5)
	(1, 2, 6)	(a^8, a^3, 0)	(a^9, 0, 0)
	(1, 3, 6)	(a^4, a^6, 1)	(a^9, a^10, 1)
	(1, 4, 6)	(a^12, a^9, a^10)	(a^3, a^10, 1)
	(1, 5, 6)	(a^2, a^12, 0)	(a^6, 0, 0)
	(1, 2, 7)	(a^12, 1, a^5)	(a^9, a^5, 1)
	(1, 3, 7)	(a^14, a^8, a^10)	(a^11, 1, a^5)
	(1, 4, 7)	(a^8, a^4, 1)	(a^10, a^5, a^10)
	(1, 5, 7)	(a^11, a^5, a^5)	(a^2, a^10, a^5)
	(1, 6, 7)	(a^7, a^3, a^10)	(a^12, a^5, 1)
	(1, 2, 8)	(a^3, a^8, 1)	(a^14, 1, a^5)
	(1, 3, 8)	(a^11, 1, 0)	(a^12, 0, 0)
	(1, 4, 8)	(a, a^10, a^5)	(a^7, 1, a^10)
	(1, 5, 8)	(a^14, a, 1)	(a^4, a^5, a^10)
	(1, 6, 8)	(a^6, a^6, 0)	(a^3, 0, 0)
	(1, 7, 8)	(a^5, a^8, a^5)	(a^8, a^10, a^5)
	(1, 2, 9)	(a^5, a^4, 0)	(a^4, 0, 0)
	(1, 3, 9)	(0, a^10, 1)	(¥, ¥, a^10)
	(1, 4, 9)	(a^6, 1, a^10)	(a^12, a^10, 1)
	(1, 5, 9)	(a^10, a^2, a^0)	(a^2, 0, 0)
	(1, 6, 9)	(a, a^9, 1)	(a^6, a^10, 1)
	(1, 7, 9)	(a^3, a^4, a^10)	(a^10, a^10, a^10)
	(1, 4, 10)	(a^4, a^2, 1)	(a^5, a^10, a^5)
	(1, 5, 10)	(a^3, 1, a^5)	(a^6, a^5, 1)
	(1, 6, 10)	(a^13, a^12, a^10)	(a^3, a^5, 1)
	(1, 6, 11)	(0, 1, 0)	(¥, —, 0)

Задание 2. ТКС с кодом из задания 1 получило сообщение с синдромом . Найти норменным метом вектор ошибок в этом сообщении.

Задание 3. Взять в ПЗ5 в разделе «задания для аудиторной работы» задание 1 и решить его модифицированным методом.

Решение. В двоичном коде длиной 15 имеется 455 тройных ошибок, которые делятся на 31 орбиту. Прямой норменный метод требует построения таблицы образующих всех орбит тройных ошибок, синдромов этих образующих, а также норм синдромов образующих.

Модифицируем норменный метод, преобразуем искомую вектор-ошибку в другую тройную ошибку , синдром которой имеет первую компоненту Пусть локаторы ошибочных позиций вектора , ненулевых координат вектора В качестве берём вектор-ошибку весом 3 с локаторами ненулевых позиций . Тогда компоненты синдрома выражаются следующим образом через компоненты синдрома :

;

;

.

У нас . Следовательно, ; . Таким образом, . Тогда .

Поищем в нашем (15, 7)-БЧХ-коде Г -орбиту с такой экзотической нормой. Единственная неполная Г -орбита тройных ошибок в этом коде задаётся вектором с ненулевыми координатами на 1-й, 6-й и 11-й позициях. Его синдром имеет компоненты ; ; . . Следовательно, и получается циклическим сдвигом вектора . . . Значит, тройная вектор-ошибка с ненулевыми координатами на 3-й, 8-й, 13-й позициях, локаторы которых , . Отсюда легко находятся локаторы ненулевых координат искомого вектора ошибок : ; ; . Следовательно, тройная ошибка на 1-й, 10-й и 14-й позициях, что полностью совпадает с решением задания 1 практического занятия №5.

Задание 4. Пусть ТКС функционирует на основе БЧХ-кода длиной 31 с проверочной матрицей для примитивного элемента поля корня полинома Пусть приёмное устройство ТКС приняло сообщение с синдромом ошибок Найти ошибку в данном сообщении.

Решение. Естественно предполагать, что в сообщении произошла тройная ошибка на позициях с неизвестными локаторами В этом случае для их определения имеем систему уравнений:

Сделаем замену Получим новую систему уравнений:

В данном коде норма синдрома где Тогда Известно, что в данном БЧХ-коде имеется лишь пять Г-орбит тройных векторов-ошибок с Ниже приведен весь список этих Г-орбит (таблица 8.3).

Таблица 8.3

Образующие Г-орбит тройных ошибок, их синдромы и нормы синдромов в (31, 16) – БЧХ-коде с нормой вида

№ п/п	Образующая	Синдром	Норма

Из таблицы следует, что вектор принадлежит Г-орбите порождённой вектором с ненулевыми координатами на первой, второй и 20-й позициях. Осталось определить величину циклического сдвига вектора для получения Конкретное значение этой величины получается сравнением синдромов и Если в БЧХ-коде синдром то синдром Существует такое натуральное что Следовательно, для подходящего целого или Подберём наименьшее при котором делится на 3. Легко видеть, что требуемое Тогда то есть Следовательно, Поэтому Тогда

Вычисленные локаторы однозначно высвечивают искомую вектор-ошибку

Задания для самостоятельной работы из ПЗ5 решить модифицированным норменным методом.

Литература

1. Шеннон К. Работы по теории информации и кибернетике /К. Шеннон/. – М.: ИЛ, 1963. – 732 с.

2. Мак-Вильямс Ф. Дж., Теория кодов, исправляющих ошибки / Ф.Дж. Мак-Вильямс, А. Слоэн/. – М.: Связь, 1979. – 744 с.

3. Блейхут Р. Теория и практика кодов, контролирующих ошибки /Р. Блейхут/. – М.: Мир, 1986. – 576 с.

4. Питерсон У., Коды, исправляющие ошибки / У. Питерсон, Э.Уэндон /. – М.: Мир, 1976. – 574 с.

5. Кассами Т., Теория кодирования / Т.Кассами, Н.Токура, Ё. Ивадари, Я.Инагаки /. – М.: Мир, 1978. – 576 с.

6. Самсонов Б.Б., Теория информации и кодирование / Б.Б.Самсонов, Е.М. Плохов, А.И. Филоненков, Т.В. Кречет/. Ростов-на-Дону: Феникс, 2002. – 288 с. (Серия «Учебники и учебные пособия»).

7. Конопелько В.К., Прикладная теория кодирования / В.К Конопелько, В.А. Липницкий /. Т. 1 – 2. – Учебное пособие для ВУЗов. Мн.: БГУИР, 2004. – 688 c.

8. Вернер М., Основы кодирования /М. Вернер/. – Учебник для ВУЗов. М.: Техносфера, 2006. – 288 с.

9. Морелос-Сарагоса Р., Искусство помехоустойчивого кодирования. Методы, алгоритмы, применение / Р.Морелос-Сарагоса /. – Учебное пособие для ВУЗов. М.: Техносфера, 2006. – 320 с.

10. Лиддл Р., Конечные поля / Р. Лиддл, Г. Нидеррайтер /. Т. 1, 2. - М.: Мир, 1988. – 822 с.

11. Липницкий В.А. Современная прикладная алгебра. Математические основы защиты информации от помех и несанкционированного доступа /В.А. Липницкий /. – Мн.: БГУИР, 2005. – 88 с.; 2-е издание: Мн.: БГУИР, 2006. – 88 с.

12. Липницкий В.А. Теория норм синдромов / В.А. Липницкий /. Методическое пособие. - Мн.: БГУИР, 2011. – 96 с.

13. Конопелько В.К., Теория норм синдромов и перестановочное декодирование помехоустойчивых кодов / В.К Конопелько, В.А. Липницкий /.- Мн.: БГУИР, 2000. – 242 с.; 2-е издание: М.УРСС, 2004. – 176 с.

14. Конопелько В.К., Норменное декодирование помехоустойчивых кодов и алгебраические уравнения / В.К Конопелько, В.А. Липницкий /. – Мн.: Издательский центр БГУ, 2007. – 240 с.

15. Липницкий В.А., Норменное декодирование ошибок посредством их модификации /В.А. Липницкий, Е.К.Аль-Хайдар/. – Доклады БГУИР, №5(43). – 2009. – С. 12 – 16.

16. Дворников В.Д., Теория и практика низкоскоростных кодов / В.Д. Дворников, В.К. Конопелько, В.А. Липницкий /. – Мн.: БГУИР, 2002. – 210 с.

17. Лосев В.В. Микропроцессорные устройства обработки информации. Алгоритмы цифровой обработки /В.В. Лосев/. Мн.: Вышэйшая школа. 1990. – 132 с.

18. Муттер В.М. Основы помехоустойчивой телепередачи информации /В.М. Муттер/. – Л.: Энергоатомиздат, 1990. – 286 с.

СОДЕРЖАНИЕ

Введение……………………………………………………………………..….….3

1.Линейные коды. Порождающая матрица кода….…..……………………..…6

2. Проверочная матрица линейного кода. Метрика Хемминга. Синдромы ошибок…………………………………………………………………………………..18

3. Неприводимые полиномы. Поля Галуа и коды Хемминга…...……………..29

4. Коды Боуза-Чоудхури-Хоквингема, исправляющие двойные ошибки….…44

5. Синдромное декодирование произвольных БЧХ-кодов ……………….….….55

6. Циклическая и циклотомическая классификация векторов-ошибок ……….66

7. Норменное декодирование реверсивных и БЧХ-кодов ………………..…...78

8 Норменное декодирование тройных ошибок в БЧХ-кодах …………………..85

Литература ……..………………………………………………………………….93

Учебное издание   Липницкий Валерий Антонович     ТЕОРИЯ НОРМ СИНДРОМОВ       Редактор И.П. острикова Корректор Е.Н. Батурчик Компьютерная верстка И.Э. Антонович Подписано в печать Формат 60х84 1/16. Бумага офсетная. Гарнитура TimesNewRoman. Печать ризографическая. Усл. печ. л. 3,9. Уч.- изд. л. 3,5. Тираж 200 экз. Заказ 200. Издатель и полиграфическое исполнение: Учреждение образования «Белорусский государственный университет информатики и радиоэлектроники» Лицензия ЛП № 156 от 30.12. 2002. Лицензия ЛВ № 509 от 03.08. 2001. 220013, Минск, П.Бровки, 6.

Св. план 2012, п.35

Дата добавления: 2017-02-01