Файл: прикладная теория информации.pdf

195 ние нескольких разных полиномом ℎ(????) позволяет получить код, обеспечиваю- щий высокую степень защиты телекоммуникационной системы от воздействия помех (шумов) и несанкционированного доступа.
Структура проверочного полинома ℎ(????) m-кода однозначно определяет свойства линейной схемы генератора кодовых последовательностей (слов). Ге- нератор реализуется с использованием регистра сдвига (РС) с обратной связью.
Схема линейных обратных связей генератора описывается проверочным поли- номом над полем ????????(2
????
) вида
ℎ(????) = ℎ
0
????
0
+ ℎ
1
???? + ⋯ ℎ
????
????
????
+ ⋯ + ℎ
????
????
????
, 0 ≤ ???? ≤ ????, ℎ
????
∈ ????????(2).
Если некоторое ненулевое состояние (начальная фаза) ячеек памяти
(????
0
????
1
????
2
… ????
????
) РС выбрать в качестве начального, то регистр принимает (2
????
− 1) возможных двоичных состояний, прежде чем состояния начинают повторяться.
На рис. 11.4 изображена схема кодера m-кода на основе регистра РС с об- ратной связью. Структура линейных обратных связей схемы, показанной на рис.
11.4, описывается проверочным полиномом над полем
????????(2 3
) вида
ℎ(????) = 1 + ???? + ????
3
h
1
+
c
0
c
2
h
0
c = (c c ...c )
0 1
n-1
h
3
Рис. 11.4. Структурная схема кодера
Пусть в результате однотактной записи по параллельным входам ячеек РС формируется его начальное состояние вида (????
0
= 1, ????
1
= 0 ????
2
= 0). Изменения состояний РС после (???? + 1) тактов приведены в таблице 11.1.

196
Таблица 11.1
Формирование m-кода
№ такта c
0
c
1
c
2
ПСП
???? = (????
0
????
1
… ????
????−1
)
β = α
????
α
0
+ α
1
+ ⋯ + α
????−1
Дв. век- тор
1 1
0 0
0
α
0
α
0 1 0 0 2
0 1
0 0
α
1
α
1 0 1 0 3
0 0
1 1
α
2
α
2 0 0 1 4
1 1
0 0
α
3 1 +
α
1 1 0 5
0 1
1 1
α
4
α + α
2 0 1 1 6
1 1
1 1
α
5 1 +
α + α
2 1 1 1 7
1 0
1 1
α
6 1
+ α
2 1 0 1 8
1 0
0 0
α
7
α
0 1 0 0
C выхода третьей ячейки генератора формируется
????-последовательность
???? = (0 0 1 0 111). Последовательность символов является периодической с пери- одом 7. Это ‒ максимально возможный период для 3-х ячеек памяти. Имеется только 2 3
− 1 = 7 ненулевых состояний. Выходные последовательности значно- стью семь представляют собой слова кода максимальной длины.
В последних трех столбцах записаны, получающиеся по ℎ(????) = 1 + ???? + ????
3
(схема 11.4) элементы поля ????????(2 3
).
Элементы
β = α
????
представляются в виде степеней примитивного элемента α поля.
Элементы
(α
0
+ α
1
+ ⋯ + α
????−1
). представляются в виде многочленов поля.
Последний столбец таблицы отражает запись элементов поля в виде дво- ичных векторов. Любой элемент поля представляется m - разрядным двоичным числом и может храниться в m -разрядном регистре памяти. Как видно, двоичные состояния РС эквивалентны степеням примитивного элемента поля α и формам многочленов поля.
Устройство (рис. 11.4) умножает содержимое РС на элемент α в поле
????????(2 3
). Например, если в начальный момент времени регистр содержит 100 →
α
0
= 1, то в последующие моменты времени он будет содержать α, α
2
, … , α
7
=
((1)), так как α ‒ примитивный элемент поля. Таким образом, схема, показанная на рисунке 11.4, является генератором элементов расширенного поля Галуа.

197
Очевидно, различные формы представления элементов поля ????????(2
????
) поз- воляют существенно упростить обработку сигналов, выполняя основные опера- ции в поле: сложение и умножение и обратные операции: вычитание и деление.
11.8. Задание для самостоятельного выполнения
1 . Источник символов и код задаются матрицей
???? (см. пример 11.9). На вход декодера поступил вектор ???? = (−1 − 1 − 1 1 1 − 11). Определить прини- маемый символ источника на основе корреляционного метода. Построить гра- фик корреляционной функции.
2. Источник символов и m-код задаются матрицей ???? (см. пример 11.9). На вход декодера поступил вектор ???? = (1 − 1 − 1 1 1 − 11). Определить прини- маемый символ источника на выходе канала с шумами на основе корреляцион- ного метода. Построить график корреляционной функции.
3. Источник символов и m-код задаются матрицей
???? (см. пример 11.9). На выходе канала с шумами имеется вектор ???? = (1 − 1 − 1 1 − 1 − 11). Декоди- ровать вектор основе принципа максимального правдоподобия. Пояснить полу- ченный результат приема информации.

198
Список использованных источников
1. Митюхин, А. И. Прикладная теория кодирования : учеб.-метод пособие.
/ А. И. Митюхин ‒ Минск : БГУИР, 2018.
2. Кудряшов, Б. Д. Основы теории кодирования : учеб. пособие / Б. Д. Куд- ряшов. – СПб. : БХВ-Петербург, 2016.
3. Кудряшов, Б. Д. Теория информации : учебник для вузов / Б. Д. Кудря- шов. – СПб. : Питер, 2009.
4. Теория прикладного кодирования : учеб. пособие. В 2 т. / В. К. Коно- пелько [и др.]. ‒ Минск : БГУИР, 2004.
5. Ватолин, Д. Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео / Д. Ватолин, А. Ратушняк, М. Смирнов, В. Юкин. – М. :
Диалог-МИФИ, 2002.
6. Луенбергер, Д. Дж. Информатика / Д. Дж. Луенбергер. ‒ М. : Техно- сфера, 2008.
7. Митюхин, А. И. Элементы алгебраических структур теории кодирования
: учеб. пособие / А. И. Митюхин, Пачинин В. И. ‒ Минск : БГУИР, 2012.
8. Вернер, М. Основы кодирования : учебник для вузов / M. Вернер. – М. :
Техносфера, 2004.
9. Андерсон, Дж. А. Дискретная математика и комбинаторика / Дж. А. Ан- дерсон; пер. с англ. ‒ М. : Вильямс, 2004.
10. Лидл, Р. Конечные поля. В 2 т. / Р. Лидл, Г. Нидеррайдер. ‒ М. : Мир,
1988.
11. Хаггарти, Р. Дискретная математика для программистов / Р. Хаггарти.–
М. : Техносфера, 2005.

199
Св. план , поз.
Учебное издание
Митюхин Анатолий Иванович
ПРИКЛАДНАЯ ТЕОРИЯ ИНФОРМАЦИИ
УЧЕБНО-МЕТОДИЧЕСКОЕ ПОСОБИЕ
Редактор Е. С. Юрец
Корректор Е. Н. Батурчик
Компьютерная правка, оригинал-макет В. М. Задоля
Подписано в печать Формат 60×84 1/16. Бумага офсетная. Гарнитура «Таймс».
Отпечатано на ризографе. Усл. печ. л. Уч.-изд. л. 11.7 Тираж экз. Заказ
Издатель и полиграфическое исполнение: учреждение образования
«
Белорусский государственный университет информатики и радиоэлектроники».
Свидетельство о государственной регистрации издателя, изготовителя, распространителя печатных изданий №1/238 от 24.03.2014,
№2/113 от 07.04.2014, №3/615 от 07.04.2014.
ЛП №02330/264 от 14.04.2014.
220013, Минск, П. Бровки, 6