close

Вход

Забыли?

вход по аккаунту

?

Nikitin

код для вставкиСкачать
Федеральное агенТство по образованию
Государственное образовательное учреждение
высшего профессионального образования
Санкт-петербургский государственный университет
аэрокосмического приборостроения
Г. И. Никитин
РАДИОТЕХНИЧЕСКИЕ СИСТЕМЫ
ПЕРЕДАЧИ ИНФОРМАЦИИ
ОСНОВЫ ТЕОРИИ КОДИРОВАНИЯ
Учебно-методическое пособие
Санкт-Петербург
2008
УДК 621.396.946(075)
ББК 32.844.1
Н62
Рецензенты:
кафедра информационных и вычислительных систем
Санкт-Петербургского университета путей сообщения;
доктор технических наук, профессор,
главный научный сотрудник НТО ЗАО «ПЕЛЕНГ»
А. А. Монаков
Утверждено
редакционно-издательским советом университета
в качестве учебно-методического пособия
Никитин Г. И.
Н62 Радиотехнические системы передачи информации. Основы теории кодирования: учебно-методическое пособие /
Г. И Никитин. – СПб.: ГУАП, 2008. – 93 с.: ил.
ISBN 978-5-8088-0335-0
Учебно-методическое пособие содержит основы теории, принципы
построения и методы расчета характеристик кодирующих устройств
в системах передачи информации по каналам связи. Рассмотрены
практически все коды, используемые в системах передачи: эффективные, помехозащищенные, модуляционные, синхронизирующие и
коды защиты от несанкционированного доступа. Кроме того, приводятся принципы построения устройств штрихового кодирования, широко применяющихся в настоящее время для автоматической идентификации материальных потоков. В учебно-методическом пособии
содержится ряд вариантов практических расчетов и заданий, которые должны быть самостоятельно выполнены студентами в процессе
практических занятий, предусмотренных в учебном плане лекционного курса «Радиотехнические системы передачи информации».
Предназначено для студентов, обучающихся по направлению
654200 «Радиотехника», специальность 200700 «Радиоэлектронные
системы» при изучении курса «Радиотехнические системы передачи
информации» очной и заочной форм обучения.
УДК 621.396.946(075)
ББК 32.844.1
ISBN 978-5-8088-0335-0
© ГУАП, 2008
© Г. И. Никитин, 2008
Содержание
Введение.......................................................................... 1. Особенности представления сигналов в цифровой форме ..... 1.1. Формы представления сигналов................................ 1.2. Преимущества цифровой формы представления
сигналов.......................................................................... 1.3. Характеристики систем счисления............................ 1.4. Определение оптимальной системы счисления............ 1.5. Преобразование непрерывных сообщений в цифровую
форму.............................................................................. 2. Эффективное кодирование.............................................. 2.1. Характеристика эффективных кодов......................... 2.2. Процедура построения кода шеннона–фано............... 2.3. Процедура построения кода хафмена........................ 2.4. Достоинства и недостатки эффективных кодов............ 2.5. Построение и характеристики эффективных кодов ..... 3. Помехоустойчивое кодирование...................................... 3.1. Основные характеристики корректирующих кодов..... 3.2. Простейшие помехоустойчивые коды........................ 3.4. Параметры кода хемминга....................................... 4. Циклические коды........................................................ 4.1. Полиноминальное представление циклических кодов . 4.2. Порождающие полиномы циклических кодов............. 4.3. Принципы формирования и обработки комбинаций
циклических кодов........................................................... 4.4. Плотноупакованный код голея................................. 4.5. Процедуры кодирования и декодирования
циклических кодов........................................................... 5. Сверточные корректирующие коды.................................. 5.1. Рекуррентный код финка........................................ 5.2. Формирование кода финка–хагельбергера................ 6. Кодирование с перемежением.......................................... 6.1. Назначение процедуры перемежения........................ 6.2. Диагональное перемежение...................................... 6.3. Блочное перемежение.............................................. 7. Модуляционные коды.................................................... 7.1. Двоичный код грея................................................. 7.2. Перекодировка при относительной фазовой
модуляции (офм)............................................................. 7.3. Код – дифференциальный манчестер......................... 7.4. Диаграммы работы кодека с офм............................. 5
7
7
8
9
14
15
20
20
22
24
26
27
30
30
31
40
43
43
44
47
53
55
57
57
63
65
65
66
66
67
67
69
70
71
3
8. Синхронизирующие коды............................................... 8.1. Разновидности синхронизирующих кодов.................. 8.2. Преамбула формата сообщения аварийного радиобуя
арб – 406........................................................................ 8.3. Синхронизирующие коды баркера............................ 8.4. Автокорреляционные функции кодовых слов............. 9. Коды защиты от несанкционированного доступа................ 9.1. Шифры тайнописи текстовых сообщений................... 9.2. Шифр по задающей ключевой матрице ...................... 9.3. Защита с помощью м-последовательности.................. 10. Системы и устройства штрихового кодирования............... 10.1. Построение устройств штрихового кодирования........ 10.2. Основные структуры штриховых кодов.................... 10.3. Устройства считывания штриховых кодов................ Рекомендуемая литература................................................ 4
73
73
73
76
78
79
79
81
82
85
85
86
89
92
ВВЕДЕНИЕ
Коды появились в глубокой древности в виде криптограмм (погреч. – тайнописи), когда ими пользовались для засекречивания
важного сообщения от тех, кому оно не было предназначено.
Иное направление в кодировании, которое возникло в начале
ХХ в., связано с проблемой передачи сообщений по линиям связи,
без которых (т. е. без телеграфа, телефона, радио, телевидения и
т. д.) немыслимо наше нынешнее существование. В задачу такого
кодирования входит отнюдь не только засекречивание сообщений,
а иная цель: сделать передачу сообщений быстрой, удобной и надежной. Предназначенное для этой цели кодирующее устройство
сопоставляет каждому символу передаваемого текста, а иногда и
целым словам или фразам определенную комбинацию сигналов, называемую кодом или кодовым словом. При этом операцию перевода
сообщений в определенные последовательности сигналов называют
кодированием, а обратную операцию, восстанавливающую по принятым сигналам передаваемые сообщения, декодированием.
Исторически первый код, предназначенный для передачи сообщений, связан с именем изобретателя телеграфного аппарата Самюэля Морзе и известен всем как азбука Морзе. В этом коде
каждой букве или цифре сопоставляется своя последовательность
из кратковременных (точек) и длительных (тире) импульсов тока,
разделяемых паузами. Другой код, столь же широко распространенный в телеграфии (код Бодо), использует для кодирования два
элементарных сигнала – импульс и паузу, при этом сопоставляемые буквам кодовые слова состоят из пяти таких сигналов.
Коды, использующие два различных элементарных сигнала, называются двоичными. Удобно, отвлекаясь от их физической природы, обозначать эти два сигнала символами 0 и 1. Тогда кодовые
слова можно представлять как последовательности из нулей и единиц.
В учебно-методическом пособии, дополняющем лекционный
курс «Радиотехнические системы передачи информации» (РТСПИ), излагаются вопросы применения различных вариантов кодов при передаче сообщений. Перечень кодов, используемых в РТСПИ, следующий:
− первичные коды;
− эффективные коды;
− помехоустойчивые коды:
простейшие,
коды Хемминга,
5
циклические,
сверточные,
кодирование с процедурой перемежения;
− модуляционные коды;
− синхронизирующие коды;
− коды защиты от несанкционированного доступа.
В дополнение к этим кодам рассмотрены системы штрихового
кодирования. Описание соответствующих кодов дополняется практическими расчетами и заданиями, которые студенты должны самостоятельно выполнить.
Автор выражает глубокую признательность и благодарность
ведущему инженеру-программисту М. Я. Романовой за помощь в
подготовке издания.
6
1. ОСОБЕННОСТИ ПРЕДСТАВЛЕНИЯ СИГНАЛОВ
В ЦИФРОВОЙ ФОРМЕ
1.1. Формы представления сигналов
По своей природе сигналы могут быть электрическими, световыми, звуковыми и т. п. В радиосистемах передачи информации
используются электрические сигналы, поэтому сообщения неэлектрической природы при передаче предварительно преобразуются в
электрические колебания с помощью преобразователей: микрофонов, передающих телевизионных трубок, датчиков температуры,
давления и т. п. Эти электрические колебания обычно называют
первичными сигналами.
В зависимости от области возможных значений по уровню и времени различают следующие виды сигналов (рис. 1.1):
– непрерывные по уровню и по времени (рис. 1.1, а);
– непрерывные по уровню и дискретные по времени (рис. 1.1, б);
– дискретные (квантованные) по уровню и непрерывные по времени (рис.1.1, в);
– дискретные по уровню и по времени (рис. 1.1, г).
Непрерывные сигналы задаются на конечном или бесx(t)
а)
конечном временном интервале и могут принимать любые
значения в некотором диапа0
зоне. Являясь электрическиt
ми моделями аналогичных
б) x(t)
физических величин, такие
сигналы называют аналоговыми.
0
t
Сигналы второго вида моx(t)
в)
гут принимать любые значения из некоторого диапазона
путем взятия отсчетов в определенные моменты. Это пре0
t
x(t)
образование называется дискг)
ретизацией во времени. Шаг
дискретизации (промежуток
времени между двумя сосед0
ними отсчетами) может быть
t
как постоянным, так и переРис. 1.1. Основные виды сигналов
менным.
7
Сигналы третьего вида, называемые квантованными по уровню, характеризуются тем, что принимают только вполне определенные дискретные значения. В результате квантования непрерывный сигнал заменяется ступенчатой функцией.
Шаг квантования (расстояние между двумя соседними разрешенными уровнями) может быть как постоянным, так и переменным. Его обычно выбирают из условия уменьшения шума квантования и получения требуемой точности восстановления непрерывного сигнала из квантованного.
Сигналы четвертого вида, называемые дискретными, задаются
в определенные дискретные моменты и принимают определенные
дискретные значения. Именно такие сигналы легко представляются в цифровой форме, т. е. в виде чисел с конечным числом разрядов в кодовом слове. Такие сигналы называют цифровыми.
Таким образом, если провести нумерацию уровней квантования,
то передача сведется к передаче чисел. Тогда, выразив эти числа в
какой-либо системе счисления, можно обойтись меньшим множеством передаваемых сигналов. Как правило, дискретный сигнал
преобразуется в последовательность чисел, выраженных в двоичном коде. Каждое дискретное значение сигнала представляется в
этом случае последовательностью сигналов двух уровней. Наличие
или отсутствие импульса на определенном месте интерпретируется
единицей или нулем в соответствующем разряде двоичного числа.
1.2. Преимущества цифровой формы
представления сигналов
Преимущества и причины перехода к цифровому выражению
информации заключаются в следующем.
1. Для конкретных задач управления объектами или исследования ряда процессов обычно требуется значительно меньше информации, чем поступает с датчиков в виде сигналов, изменяющихся
во времени непрерывно. Это позволяет ограничиться цифровыми
отсчетами, взятыми через определенные моменты времени.
2. В подавляющем числе случаев информация извлекается и
передается с целью дальнейшей обработки средствами цифровой
техники, в первую очередь компьютерами и микропроцессорами.
Рациональное выполнение операций дискретизации и квантования при этом приводит к значительному экономическому эффекту
как за счет снижения затрат на хранение и обработку получаемой
информации, так и вследствие сокращения времени обработки информации.
8
3. Применение представления чисел в двоичной системе счисления позволяет при передаче единичных импульсов использовать
постоянную и максимальную мощность передатчика.
4. При передаче речевых сообщений (в частности, в сотовых системах связи) удается уменьшить необходимое число передаваемых
импульсов и получить коэффициент сжатия порядка 5 – 8 за счет
применения соответствующих алгоритмов. Это дает возможность
одновременно передавать дополнительную служебную информацию наряду с речевой.
5. Выход на передачу информации в цифровом виде позволяет
просто решить задачу многостанционного доступа при работе ряда
радиостанций на одной несущей частоте с временным разделением
каналов.
6. При передаче и обработке информации в цифровой технике
существует принципиальная возможность снижения вероятности
получения ошибочного результата до весьма малых значений при
применении методов помехоустойчивого кодирования, которые
обеспечивают обнаружение и исправление возникающих при передаче ошибок.
7. Массовость изготовления типовых цифровых узлов и блоков,
простота их настройки, отсутствие необходимости регулировки
в процессе эксплуатации позволяют улучшить такие важнейшие
технико-экономические показатели средств цифровой техники,
как стоимость изготовления и эксплуатации, а также надежность.
Низкая стоимость и высокая надежность интегральных схем являются стимулами дальнейшего расширения областей использования цифровых сигналов.
1.3. Характеристики систем счисления
Любому дискретному сообщению или знаку сообщения можно
приписать какой-либо порядковый номер. Числа можно выразить
в одной из систем счисления. Таким образом, будет получен один
из кодов, основанный на данной системе счисления.
Рассмотрим разновидности применяемых и применявшихся
систем счисления для поиска оптимального значения основания
системы m. В общем случае системой счисления называется совокупность правил наименования и записи чисел. Эти системы подразделяются на позиционные и непозиционные.
В непозиционных системах счисления, которые появились значительно раньше позиционных, символы, обозначающие то или
иное число, не меняют своего значения в зависимости от местополо9
жения в изображении этого числа. Примером непозиционной системы счисления является римская система, в которой для записи
чисел используются буквы латинского алфавита. При этом буква I
всегда означает единицу, буквы V – пять, X – десять, L – пятьдесят,
C – сто, D – пятьсот, М – тысячу и т. д. Например, число 268 записывается в виде CCLXVIII. Римские числа используются и сейчас,
например, на циферблатах часов, однако в математической практике они не применяются.
В позиционной системе счисления используется определенный
набор символов (цифр), последовательная запись которых изображает число. Количество символов в наборе соответствует основанию системы счисления. Позиция символа в изображении числа
называется разрядом. Разряду с номером 0 соответствует младший
разряд целой части числа. Каждому символу соответствует определенное число, которое меньше основания системы счисления. В
зависимости от позиции (разряда) числа значение символа умножается на степень основания, показатель которой равен номеру
разряда.
Причины, по которым именно десятичная система оказалась общепринятой, совсем не математического характера. Десять пальцев рук – вот тот первоначальный аппарат для счета, которым
человек пользовался, начиная с доисторических времен. Однако
десятичная система счисления далеко не сразу заняла то главенствующее положение, которая она имеет сейчас. В разные исторические периоды многие народы пользовались системами счисления, отличными от десятичной системы. Так, например, довольно
широкое распространение имела двенадцатеричная система. Происхождение этой системы тоже связано с расчетом на пальцах, так
как четыре пальца руки (кроме большого) имеют в совокупности
12 фаланг. По этим фалангам, перебирая их по очереди большим
пальцем, ведут счет от 1 до 12. Затем 12 (дюжина) принимается за
единицу следующего разряда и т. д. Многие наборы предметов, например мебельные гарнитуры (12 стульев), столовые приборы (на
12 персон) изготовляют именно дюжинами, а не десятками. Несомненно, остатки двенадцатеричной системы имеются и у англичан – в системе мер (1фут равен 12 дюймам) и в денежной системе
(1шиллинг равен 12 пенсам).
В древнем Вавилоне, культура которого, в том числе и математическая, была достаточно высока, существовала весьма сложная
шестидесятеричная система.
Эта система, как и двенадцатеричная, в какой-то степени сохранилась и до наших дней (например, в делении часа на 60 минут, а
10
минуты – на 60 секунд и в системе измерения углов: 1 градус = 60
минутам, 1 минута = 60 секундам). Интересно, что у древних вавилонян и египтян в календаре, созданном в четвертом тысячелетии
до нашей эры, год состоял из 365 дней; он делился на 12 месяцев
по 30 дней каждый, и в конце года добавлялось пять праздничных
дней, не входящих в состав месяцев.
Позиционные системы удобны тем, что они позволяют записывать большие числа с помощью сравнительно небольшого числа
знаков. Еще более важное преимущество позиционных систем –
это простота и легкость выполнения арифметических операций над
числами, записанными в этой системе. Для чисел, записанных в десятичной системе, пользуются правилами сложения и умножения
чисел – столбиком, деления – углом. Эти же правила полностью
применимы и для чисел, записанных в любой другой позиционной
системе.
В системах цифровой техники для представления числовой информации используются следующие системы счисления: двоичная, восьмеричная, десятичная и шестнадцатеричная. Первым,
кто понял, что для кодирования достаточно двоичной системы
был английский философ XVII в. Фрэнсис Бэкон. Он использовал
в криптографических целях кодовые слова, составленные из двух
символов (0 и 1).
Сравним системы счисления и построенные на их основе коды
с позиций применения в системах передачи, хранения и преобразования информации. Значение каждого символа (цифры) в позиционных системах зависят от их положения – позиции в ряду
символов, представляющих число. Показатель степени m каждого
следующего разряда больше показателя предыдущего разряда в m
раз, где m – основание системы счисления. Полное число получается при суммировании значений по разрядам
A=
n
∑ aim i−1 = anm n−1 + an−1m n−2 +
... +a2m 1 + a1m 0, (1.1)
i =1
где m – основание системы счисления, целое положительное число;
i – номер разряда данного числа; n – количество разрядов; a – множитель, принимающий любые целочисленные значения в пределах от 0 до m – 1 и показывающий, сколько единиц i-го разряда
содержится в числе.
Количество цифр, которое требуется для изображения чисел в
позиционной системе счисления, равно основанию системы счисления. Например, для изображения чисел в двоичной системе счис-
11
ления требуется две цифры, в десятичной – десять, в шестнадцатеричной – шестнадцать цифр. В ней для обозначения первых десяти
цифр используются цифры десятичной системы, а для изображения шести остальных – шесть заглавных (прописных) букв латинского алфавита A, B, C, D, E, F, соответствующих цифровым эквивалентам 10, 11, 12, 13, 14, 15, хотя можно было бы использовать
любые другие шесть знаков.
Рассмотрим алгоритм перевода целых чисел из одной в системы в
другую, например, из привычной десятичной системы в двоичную,
и оценим число символов в новой записи исходного числа. В этом
алгоритме вычисления сводятся к целочисленному делению заданного числа на основание новой системы счисления. Алгоритм перевода записывается в виде следующей последовательности шагов.
1. Разделить в целых числах заданное число A на основание m
той системы, в которую осуществляется перевод, и запомнить частное q и остаток a.
2. Полученное частное q принять за новое число A и вернуться к
шагу 1.
3. Когда частное становится меньше основания m (делителя), то
действия прекратить и считать его последним остатком. Выписать
остатки в порядке, обратном их получению, и принять их за цифры
искомого числа an an-1, …, a2 a1. Вычисления удобно проводить в
форме, которая ясна из следующих примеров.
Пример: перевести произвольное число 1708 из десятичной системы в шестнадцатеричную, восьмеричную, троичную и двоичную
системы.
Основание системы m = 16
Проверка
1708 / 16 = 106;остаток 12
1 × 12 = 12
106 / 16 = 6;остаток 10
16 × 10 = 160
6 → остаток 6
256 × 6 = 1536
Код для m = 16 – 6(10)(12) = 6АС n = 3
∑ = 1708
Основание системы m = 8
Проверка
1708 / 8 = 213; остаток 4
1×4=4
213 / 8 = 26; остаток 5
8 × 5 = 40
26 / 8 = 3; остаток 2
64 × 2 = 128
3 → остаток 3
512 × 3 = 1536
Код для m = 8 – 3254
n=4
∑ = 1708
Основание системы m = 3
Проверка
1708 / 3 = 569; остаток 1
1×1=1
569 / 3 = 189; остаток 2
3×2=6
12
189 / 3 = 63; остаток 0
63 / 3 = 21; остаток 0
21 / 3 = 7; остаток 0
7 / 3 = 2; остаток 1
2 → остаток 2
Код для m = 3 – 2100021
Основание системы m = 2
1708 / 2 = 854; остаток 0
854 / 2 = 427; остаток 0
427 / 2 = 213; остаток 1
213 / 2 = 106; остаток 1
106 / 2 = 53; остаток 0
53 / 2 = 26; остаток 1
26 / 2 = 13; остаток 0
13 / 2 = 6; остаток 1
6 / 2 = 3; остаток 0
3 / 2 = 1; остаток 1
1 → остаток 1
Код для m = 2 – 11010101100
9×0=0
27 × 0 = 0
81 × 0 = 0
243 × 1 = 243
729 × 2 = 1458
n=7
∑ = 1708
Проверка
1×0=0
2×0=0
4×1=4
8×1=8
16 × 0 = 0
32 × 1 = 32
64 × 0 = 0
128 × 1 = 128
256 × 0 = 0
512 × 1 = 512
1024 × 1 = 1024
n =11
∑ = 1708
Обратим внимание на то, что в системах с основанием больше 10
возможно в остатках получать значения с числом цифр 2 и более.
Однако все они заменяются в коде латинскими буквами и считаются одним разрядом.
В примерах произведена проверка правильности представления
кодов, при которой нарастающие степени основания систем умножаются на коэффициенты a, являющиеся полученными остатками
(см. формулу 1.1).
Из примеров видно, что, чем больше основание системы счисления m, тем меньше число разрядов n требуется для представления
данного числа, следовательно, и меньшее время для его передачи.
Однако с ростом основания существенно повышаются требования к линии связи и к аппаратуре создания и распознавания элементарных сигналов, соответствующих различным символам. Логические элементы вычислительных устройств в этом случае должны иметь большее число устойчивых состояний.
Учитывая оба эти обстоятельства, целесообразно выбрать систему, обеспечивающую минимум произведения количества различных символов m на количество разрядов n при выражении любого
числа. Это значение E = mn получило название экономичность системы, по минимуму которой определяется оптимальное значение
основания системы счисления.
13
Для поиска этого значения предполагается выполнить ряд вычислений, которые оформляются студентами в виде практического
расчета, сдаваемого преподавателю. Каждый расчет предполагает
индивидуальность данных.
1.4. Определение оптимальной системы счисления
(практическое задание)
Определение оптимального значения основания системы счисления предполагает задание исходного числа в десятичной системе.
Для индивидуальности расчетов это число выбирается в соответствии с датой рождения студента, которая может быть в пределах от
1 января до 31 декабря. В соответствии с этим исходное десятичное
число A варьируется в интервале от 101 до 3112. Выполнение расчета производится по следующим пунктам.
1. Задание числа A. Далее в расчете предполагается для примера
воспользоваться результатами подразд. 1.3, где используется число 1708, соответствующее дате рождения – 17 августа.
2. Десятичное число A перевести в другие системы счисления.
Для этого выполнить расчеты, аналогичные переводу числа 1708,
представленные в подразд. 1.3. При определении каждого кода
выполнить их проверку. Значения систем счисления при расчетах
принять равными значениям m, приведенными в табл. 1.1. следующего п. 3.
3. Заполнить табл. 1.1 значениями оснований систем счисления,
полученными кодами, числом разрядов в кодах и экономичностью.
Таблица 1.1. Расчет значений систем счисления
14
Основание
системы
m
Значение
кода
Число
разрядов
n
Экономичность
Е = mn
1
2
3
4
6
8
10
12
16
А = 1708
…
11010101100
2100021
…
…
3254
1708
…
6АС
…
…
11
7
…
…
4
4
…
3
…
…
22
21
…
…
32
40
…
48
...
Обратить внимание на правильность заполнения строк при m =
1 и А.
4. Построить график зависимости экономичности от значений
оснований систем счисления E = f(m) в пределах m = 1 ÷ 16 по результатам табл. 1.1. Шкалу ординаты E ограничить значением 60.
Прокомментировать результаты, определить значение m при минимуме Е.
5. Аналитически определить оптимальное значение основания
m. С этой целью целесообразно учесть, что значения m и n, определяющие экономичность E, связаны также функциональной зависимостью, определяющей количество чисел, которое с их помощью
можно записать как N = mn. Из этой формулы можно получить при
логарифмировании явное значение для n: n = log N / log m, тогда
E = log N m/ log m. Для определения оптимального m при минимальном значении E необходимо продифференцировать выражение E = f (m), полагая N постоянной величиной. Определить значение m, при котором производная равна нулю. Отметим, что логарифмирование может быть выполнено при любом его основании и
двоичном, и десятичном, но при натуральном логарифмировании
упрощается процесс дифференцирования, поскольку производная
от натурального логарифма равна 1/ m. Прокомментировать полученный результат.
6. Привести выводы по работе. Отметить, почему в вычислительной технике в основном используется двоичная система счисления,
хотя она и не является оптимальной. В дальнейшем будем ориентироваться на коды, представленные в двоичной системе счисления.
1.5. Преобразование непрерывных сообщений
в цифровую форму
Как отмечалось выше, аналоговые сигналы представляются в
цифровом виде с помощью операций квантования по уровню, дискретизации по времени и кодированию. Операция квантования по
уровню заключается в замене непрерывного множества значений,
которые может принимать сообщение, дискретным множеством
заранее определенных значений, называемых уровнями квантования. Такое преобразование выполняет аналого-цифровой преобразователь (АЦП). Диапазон возможных значений сообщения разбивается на L интервалов. При попадании отсчета в i-й интервал
сигналу приписывается значение xi. В случае передачи речевых
сигналов, как правило, число двоичных разрядов в АЦП может до-
15
стигать значений n = 8, что соответствует числу уровней квантования L = 28 = 256 в АЦП.
Различают равномерное и неравномерное квантование. При равномерном квантовании шаг ∆x берется постоянным, а уровень xi соответствует середине i-го интервала квантования. При неравномерном квантовании шаг ∆x является переменным.
Замена непрерывного множества возможных значений сообщения дискретным множеством фиксированных значений приводит
к погрешности, достигающей ∆/2, называемой шумом квантования.
Неравномерное квантование, хотя и сложнее в реализации, чем
равномерное, довольно часто используется при передаче речевых
сигналов. Это объясняется тем, что распределение мгновенных
значений речевых сигналов отлично от равномерного: как правило,
малые значения сигналов гораздо более вероятны, чем большие.
Чтобы сохранить разборчивость речи «тихого» абонента, шаг квантования в области малых значений сигнала должен быть небольшим. В области больших значений сигнала можно допустить более
крупный шаг. Этого можно достичь путем сжатия (компрессирования) динамического диапазона сигнала, применения равномерного
квантования и последующего расширения (экспандирования) после восстановления отсчетов на приемной стороне. Характеристики
компрессора и экспандера должны быть взаимно обратными. Этот
метод получил название квантование с компандированием сигнала.
Под временной дискретизацией понимается процесс непрерывного сообщения, заданного на временном интервале (0, Тс) совокупностью ординат, следующих с интервалами ∆t. Правило выбора
шага ∆t при равномерной дискретизации с использованием модели
сигнала с ограниченным спектром сформулировано и доказано академиком В. А. Котельниковым в виде теоремы, получившей в отечественной литературе его имя. В зарубежной литературе эту теорему называют теоремой Найквиста или просто теоремой отсчетов.
Теорема устанавливает принципиальную возможность полного
восстановления непрерывной функции с ограниченным спектром
по ее отсчетам и указывает предельное значение интервала времени
между отсчетами, при котором такое восстановление еще возможно. Она формулируется следующим образом: аналоговая функция,
имеющая непрерывный спектр, ограниченный полосой частот от 0
до Fc, полностью определяется дискретным рядом своих мгновенных значений через интервалы времени
16
∆t =
1
.
2Fc
(1.2)
Восстановление непрерывной функции u(t) выполняется с
помощью базисных функций вида sin(x) /x, которые можно
получить на выходе идеального фильтра нижних частот, подав на
его вход сигнал в виде дельта-функции δ(t –∆t). Однако ни сигнал
в виде δ-функции, ни идеальный фильтр нижних частот физически
нереализуемы. Поэтому на практике вместо δ-функции используют
короткие импульсы, полученные на выходе цифроаналогового
преобразователя (ЦАП), а вместо идеального фильтра нижних
частот – обычный фильтр нижних частот. На рис. 1.2 показан
результат суммирования откликов фильтра нижних частот при
получении исходного аналогового сигнала.
На практике квантованные отсчеты передают с использованием
кодовых комбинаций, кажu(t)
дая из которых соответству- u(nΔt) Δt Δt Δt
ет определенному уровню
квантования. При равноu(t)
мерном коде с основанием
m длина кодовых комбина0
T
t
ций не может быть меньше
числа разрядов n, которое
sin ωc (t-∆t)
u(∆t)
ωc(t-∆t)
выбирается из условия, что
число уровней квантования
0
L ≤ mn. При выборе осноt
вания кода в первую очеsin ωc(t-2∆t)
u(2∆t)
редь необходимо учитывать
ωc(t-2∆t)
простоту, экономичность и
удобство реализации цифt
0
рового представления непрерывных сообщений. На
sin ωc (t-3∆t)
u(3∆t)
практике обычно применяωc (t-3∆t)
ют простые (безызбыточные) двоичные коды, среди
t
0
которых наибольшее приu*(t)
менение нашли двоичный
натуральный код (ДНК),
симметричный натуральt
ный код (СНК) и код Грея,
T
0
называемый также рефлексным двоичным кодом Рис 1.2. Восстановление сигнала
17
(РДК). Первые 16 кодовых комбинаций этих кодов приведены на
рис. 1. 3.
ДНК
СНК
РДК
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
0
0
0
0
1
1
1
1
0
0
0
0
1
1
1
1
0
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
23
22
21
8
4
2
−
−
−
−
−
−
−
−
+
+
+
+
+
+
+
+
1
1
1
1
0
0
0
0
0
0
0
0
1
1
1
1
1
1
0
0
1
1
0
0
0
0
1
1
0
0
1
1
1
0
1
0
1
0
1
0
0
1
0
1
0
1
0
1
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
0
0
0
0
1
1
1
1
1
1
1
1
0
0
0
0
0
0
1
1
1
1
0
0
0
0
1
1
1
1
0
0
20
±
22
21
20
Код
1
±
4
2
1
невзвешенный
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1
0
Рис. 1.3. Коды ДНК, СНК и РДК
Двоичный натуральный код – это код, комбинации которого
представляют собой двоичные номера уровней квантования. Он
прост в реализации и удобен при обработке на ЭВМ.
Симметричный натуральный код используется для представления биполярных квантованных отсчетов. При этом высший разряд несет информацию о знаке отсчета, а остальные разряды – об
абсолютном значении отсчета в натуральном двоичном коде.
Рефлексный двоичный код (код Грея) называют рефлексным,
поскольку он имеет ось симметрии (рис. 1.3). Этот код обладает следующими двумя особенностями, которые способствуют повышению быстродействия кодирующих устройств по сравнению с применением двоичного натурального кода: любые две кодовые комбинации, соответствующие соседним уровням квантования, отличаются друг от друга только в одном разряде, что уменьшает число
погрешностей при съеме кодов с АЦП. Кроме того, смена значений
18
элементов в каждом разряде при переходе от одной комбинации к
другой происходит вдвое реже, чем в двоичном натуральном коде.
Кроме простых двоичных кодов, при передаче непрерывных
сообщений используются эффективные коды, уменьшающие избыточность сообщений, и помехоустойчивые коды, позволяющие
обнаруживать и исправлять ошибки, возникающие из-за действия
помех в канале связи.
19
2. ЭФФЕКТИВНОЕ КОДИРОВАНИЕ
2.1. Характеристика эффективных кодов
Одной из задач кодирования сообщений передающего источника является устранение избыточности в сообщениях. Кодирование,
при котором в закодированных сообщениях отсутствует избыточность, называется эффективным, экономным или статистическим. Кодирование огромного множества сообщений кодовыми
словами одинаковой длительности не всегда бывает выгодно. Одни
сообщения приходится передавать довольно часто, другие – редко,
третьи – совсем в исключительных случаях, т. е. с разными вероятностями их появления. При этом первые лучше кодировать короткими кодовыми словами, оставив более длинные слова для кодирования сообщений, появляющихся реже, с меньшей вероятностью.
В результате кодовый текст будет в среднем короче, он станет более
экономным и потребует для передачи меньше времени.
Впервые эта простая идея была реализована американцем Морзе
в предложенном им коде. Создавая свой код, Морзе отправился в
ближайшую типографию и подсчитал число литер (букв) в наборных кассах. Буквам и знакам, для которых литер в этих кассах было
больше, т. е. они встречаются чаще, он сопоставил более короткие
сообщения. Так, например, в русском варианте азбуки Морзе буква
«е» передается одной точкой (при большой вероятности появления
в тексте – 0,072), а редко встречающаяся буква «ф» (при вероятности 0,002) – набором из четырех символов.
При применении равномерных кодов с постоянной длиной (n =
const) кодовых слов и замене их на неравномерные эффективные,
статистические коды (n = var) избыточность кода источника сообщений определяется выражением
(2.1)
ǽ  O  O NJO   O NJO   
æ
O
O
где отношение µ = nmin /n получило название коэффициента сжатия.
Таким образом, источник с избыточностью ǽ ≠ 0 формирует последовательность сообщений, в которых число символов n больше
минимально необходимого числа nmin для данного количества информации. Установлено, что избыточность текстов на русском и
английском языках ǽ = 0,7, т. е. объем книг, статей и другой печатной продукции примерно в 3,3 раза больше, чем это необходимо
20
содержащейся в них информации (при ǽ = 0,7 значение µ = 0,3 =
= 1/3,3).
Идея метода эффективного, экономного кодирования сообщений, символы алфавита которых не равновероятны и независимы,
заключается в следующем: наиболее часто встречающимся символам сообщения надо ставить в соответствие более короткие кодовые комбинации, а менее вероятным символам – более длинные.
Учитывая статистические свойства источника сообщения, можно
минимизировать среднее число символов, требующихся для выражения одного знака сообщения, что при отсутствии шума в канале
передачи позволяет уменьшить время передачи или объем запоминающего устройства.
Возможность сжатия передаваемого сообщения при избыточности составляет содержание основной теоремы кодирования при
отсутствии помех Клода Шеннона. В упрощенной трактовке она
утверждает: минимальное среднее число кодовых символов, приходящееся на один символ сообщения, можно сделать сколь угодно
близким к минимальному значению.
Теорема кодирования является теоремой существования, т. е.
она доказывает, что эффективные (оптимальные) коды существуют, но не дает указаний о том, как построить такие коды. Однако основные свойства и особенности, которыми должны обладать
такие эффективные коды, следуют из теоремы кодирования. Эти
свойства следующие.
1. Для обеспечения средней длины кодового слова избыточность
должна быть сведена к минимуму (желательно к нулю). Для этого
эффективный код должен состоять из кодовых слов, в которых все
символы равновероятны и статистически независимы. Это позволяет уравнять скорость передачи с пропускной способностью канала связи, что и является целью безызбыточного кодирования.
2. Ни одна из кодовых комбинаций не должна получаться из
другой, более короткой, путем добавления новых символов. Эффективные коды не требуют разделительных знаков (маркеров), и при
этом должно выполняться их однозначное декодирование. Коды,
удовлетворяющие этому условию, называются префиксными кодами, так как ни одно из кодовых слов не является передней частью
(«префиксом» – приставкой) другого слова.
3. Эффективные коды являются неравномерными, так как для
передачи разных символов сообщения используются кодовые комбинации разной длины. Наиболее вероятные сообщения кодируются самыми короткими кодовыми словами, вследствие чего средняя
длина кодового слова в сообщении уменьшается, что позволяет ре21
шить задачу равенства скорости передачи и пропускной способности канала.
При неравномерном эффективном коде средняя длина кодового
слова nср определяется выражением
n ср =
K max
∑
n к p(x к ), (2.2)
к =1
где p(xк) – вероятность появления сообщения (кодового слова) xк;
nк – длина кодового слова xк (к = 1, 2, …, Kmax). Процедуру построения эффективного кода, близкого к оптимальному, предложили
практически одновременно Шеннон и Фано (код Шеннона–Фано).
Рассмотрим эту процедуру на примере построения кода в двоичном
алфавите.
2.2. Процедура построения кода Шеннона–Фано
Метод кодирования, позволяющий получить эффективный код,
предложенный Шенноном и Фано, заключается в следующем.
1. Элементарные сообщения (символы) xi, подлежащие кодированию, записываются в порядке убывания их вероятностей p(xi).
2. Полученная последовательность сообщений разбивается на
две группы так, чтобы суммы вероятностей сообщений в каждой
группе были по возможности одинаковыми.
3. Всем сообщениям первой группы приписывается символ 0
(или 1), а сообщениям второй группы – символ 1 (или 0). Эти двоичные символы используются в качестве первых символов кодовых
комбинаций.
4. Каждая из полученных групп снова разбивается на две, по
возможности равновероятные подгруппы, и символы 0 и 1 берутся
в качестве вторых символов кодового слова в зависимости от того, к
какой подгруппе относится кодируемый символ.
5. Такое разбиение на подгруппы и кодирование продолжается
до тех пор, пока в подгруппе не останется по одному из кодируемых
символов.
Пример эффективного кодирования по методу Шеннона–Фано
приведен в табл. 2.1.
Понятно, что чем более вероятно сообщение, тем быстрее оно образует «самостоятельную» группу и тем более коротким словом оно
будет закодировано. Это обстоятельство и обеспечивает высокую
эффективность кода Шеннона–Фано.
22
Таблица 2.1. Эффективное кодирование по методу Шеннона–Фано
Сообщения
Символы кода
xi
p(x)
1
x1
1/2
0
x2
1/4
1
0
x3
1/8
1
1
0
x4
1/16
1
1
1
x5
1/16
1
1
1
2
3
Код
Число
nr
0
1
10
2
110
3
0
1110
4
1
1111
4
4
∑=1
В рассмотренном примере среднее число двоичных символов,
приходящееся на одно сообщение, равно (см. формулу 2.2)
nср = 1•0,5 + 2•0,25 + 3•0,125 + 4•0,0625•2 = 1,875.
При обычном равномерном кодировании, поскольку в примере
используется пять сообщений xi, для представления каждого знака
потребуется n = 3 двоичных символа. В этом случае коэффициент
сжатия можно определить следующим соотношением:
µ=
n ср
,
(2.3)
n
откуда µ = 1,875 / 3 = 0,625.
Избыточность источника, обусловленная наличием статистических связей между элементарными сообщениями, устраняется
кодированием укрупненных сообщений. При передаче письменного текста это означает, что необходимо кодировать не отдельные
буквы, а слова. В результате такого кодирования остается избыточность, обусловленная наличием статистической связи между
словами, которая значительно слабее статистической связи между
буквами.
Эффективное кодирование можно применять и в случае любого
основания системы счисления m с той лишь разницей, что на каждом шаге следует производить разбиение на m примерно равновероятных групп (в частности, при m = 3 – на три).
Методика Шеннона–Фано не всегда приводит к однозначному
построению кода, поскольку при разбиении на подгруппы можно
23
сделать большей по вероятности как верхнюю, так и нижнюю подгруппы.
От этого недостатка свободна методика, предложенная Хафменом. Она гарантирует однозначное построение кода с наименьшим
для данного распределения вероятностей средним числом символов на букву.
2.3. Процедура построения кода Хафмена
Для дискретных систем с двоичным алфавитом кодера источника сообщений методика построения кода Хафмена сводится к следующей процедуре
1. Все xi сообщений (буквы алфавита источника) записываются
по вертикали в таблицу в порядке убывания вероятностей p(xi).
2. Две последние буквы алфавита, имеющие наименьшие вероятности, группируются вместе и объединяются в одну вспомогательную букву, которой приписывается суммарная вероятность
p∑ = pi + pi−1.
3. Вероятности букв, не участвующих в объединении, и полученная суммарная вероятность снова располагаются в порядке убывания вероятностей (в следующем столбце таблицы). Таким образом,
объем нового алфавита уменьшается на единицу.
4. Производят второе укрупнение алфавита, состоящего уже из
x – 1 символов, путем объединения двух нижних символов с наименьшими вероятностями и вычисляют их суммарную вероятность. Получают новый алфавит с объемом x – 2.
5. Упорядочивают по вероятности символы этого нового алфавита.
6. Образуют последовательность укрупненных алфавитов путем
последовательного повторения операций пп. 4 и 5, пока в ансамбле
не останется единственное сообщение с вероятностью, равной единице (шаговая процедура, записываемая в столбцах таблицы).
7. Проводя линии, соединяющие символы при последовательном укрупнении алфавита, получают так называемое кодовое дерево, концы ветвей которого являются символами исходного алфавита источника сообщений. Приписывая ветвям дерева, исходящим
из каждого промежуточного узла, различные символы алфавита
кодера (0 или 1), получают кодовые слова, соответствующие кодируемым сообщениям источника.
Методика приведена в табл. 2.2, где для алфавита источника с
объемом z = 8 приняты произвольные значения вероятностей p(zi)
с учетом того, что ∑ p(zi) = 1.
24
Таблица 2.2. Алфавит источника с объемом z = 8
Вспомогательные столбцы
Знаки Вероятности
Z1
Z2
Z3
Z4
Z5
Z6
Z7
Z8
0,22
0,20
0,16
0,16
0,10
0,10
0,04
0,02
1
2
3
4
5
6
0,22
0,20
0,16
0,16
0,10
0,10
0,06
0,22
0,20
0,16
0,16
0,16
0,10
0,26
0,22
0,20
0,16
0,16
0,32
0,26
0,22
0,20
0,42
0,32
0,26
0,58
0,42
7
1
Для составления кодовой комбинации, соответствующей данному знаку, необходимо проследить путь перехода знака по строкам и столбцам. Для наглядности строим кодовое дерево. Из точки,
соответствующей вероятности 1, направляются две ветви, причем
ветви с большей вероятностью присваивается символ 1 (или 0), а
меньшей 0 (или 1).
Такое последовательное ветвление продолжается до тех пор,
пока ветвь не закончится узлом с вероятностью каждой буквы алфавита источника. Отдельно кодовое дерево для алфавита источника, рассматриваемого в примере, приведено на рис. 2.1.
0,58
0,32
0,16
1
0
1
0
0,16
Z3
0,26
0
0,42
0,22
1
Z1
0,16
Z4
0,1 1
Z6
1
1 0
0
0,06
0,04 1
Z7
0
0,2
Z2
0,1
Z5
0 0,02
Z8
Рис. 2.1. Кодовое дерево
25
Перемещаясь по кодовому дереву сверху вниз, можно записать
для каждой буквы алфавита соответствующую ей кодовую комбинацию
z1
z2
z3
z4
z5
z6
z7
z8
01
00
111
110 100 1011 10101 10100
Среднее число символов для этого набора равно 2,8.
При представлении восьми символов источника сообщений равномерным кодом потребовалось бы четыре разряда, и тогда коэффициент сжатия при эффективном кодировании µ = 0,7.
Существенное преимущество кода Хафмена по сравнению с кодом Шеннона–Фано проявляется при применении кодов с основанием m, большим 2, и заключается в том, что методика Хафмена
гарантирует однозначное построение кода с наименьшим для данного распределения вероятностей средним числом символов на букву источника сообщений.
2.4. Достоинства и недостатки эффективных кодов
Кратко сформулируем перечисленные выше достоинства эффективных кодов.
1. При эффективном кодировании, учитывающем вероятности
появления букв алфавита источника сообщений, удается построить коды с минимальным количеством символов, приходящихся
на букву.
2. Обеспечивается преобразование сообщения в сигнал с меньшей, чем у сообщения избыточностью (в пределе – без избыточности).
3. Решается задача согласования источника сообщений с каналом связи, в результате скорость передачи информации может быть
приближена к пропускной способности канала.
4. Не требуется введения специальных разделительных символов (маркеров) для отделения одной кодовой комбинации от другой, так как ни одна кодовая комбинация эффективного кода не
совпадает с началом другой, более длинной. Такое свойство кода
называется «неприводимостью», а коды называются префиксными
или кодами без запятой.
К недостаткам эффективных кодов можно отнести следующее.
1. Эффективные коды являются неравномерными, т. е. кодовые
комбинации имеют разное число символов. Если линия связи работает с постоянной скоростью передачи, то на выходе кодера источника необходимо буферное запоминающее устройство («упругая
задержка») для записи в него «пульсирующих» по длительности
26
кодовых групп и последующего считывания в канал символов с
постоянной скоростью. Аналогичная «упругая задержка» должна
быть и на стороне приема.
2. Наибольший эффект эффективные коды дают при кодировании исходного сообщения длинными блоками, поскольку при этом
достигается равная вероятность и статистическая независимость
блоков. Однако блочное кодирование вызывает необходимость накапливать буквы алфавита источника, прежде чем поставить им в
соответствие определенную группу эффективного кода. Это приводит к большим задержкам при передаче и приеме сообщений, что
затрудняет (или исключает) применение эффективных кодов в системах, работающих в реальном масштабе времени.
3. Существенным недостатком эффективных кодов является то,
что они непомехозащищенные. Любая одиночная ошибка при приеме переводит передаваемую кодовую комбинацию в другую комбинацию, не равную ей по длительности, что влечет за собой неправильное декодирование целого ряда последующих кодовых групп.
Такое специфическое влияние помех называется «треком ошибок»
или пакетом ошибок. В чистом виде эффективное кодирование может применяться только для каналов без помех.
Таким образом, непосредственная передача сообщений при применении эффективных кодов по каналам связи с шумами приводит
к недопустимым искажениям (потере информации). Однако эффективное кодирование, устраняющее статистическую избыточность
в передаваемом сообщении, наилучшим образом подготавливает
непрерывную кодовую последовательность, полученную после первичного кодирования сообщений источника, к последующему помехоустойчивому кодированию с помощью корректирующих кодов
в кодере канала. Целенаправленное введение избыточности при помехоустойчивом кодировании, путем добавления дополнительных
проверочных символов в кодовые информативные группы, позволяет при декодировании обнаруживать и исправлять ошибки, вызванные помехами.
2.5. Построение и характеристики эффективных кодов
(практическое задание)
При малом алфавите источника сообщений и неравновероятных
символах p(x) выгодно кодировать не отдельные символы, а целые
блоки из нескольких символов (букв). Данный практический расчет, при начальном числе сообщений, равном двум, позволяет убедиться в этом. Порядок выполнения его следующий.
27
1. В качестве значащих цифр значения вероятности p(x1) выбирается номер квартала и дня рождения студента. Например, при
дате рождения 12 апреля (2-й квартал) вводимое значение вероятности p(x1) = 0,212, а при дне рождения 7 ноября (4-й квартал) –
p(x1) = 0,407. Для двоичного источника сообщений – х1 и х2 задание
вероятности p(x1) однозначно определяет значение p(х2) = 1 − p(x1),
т. е. при p(x1) = 0,212 p(x2) = 1 − 0,212 = 0,788, а при p(x1) = 0,407
p(x2) = 0,593, поскольку два сообщения источника составляют полную группу событий.
2. Составляется очевидная исходная таблица, как образец последующих таблиц, при эффективном кодировании для двоичного
источника сообщений, передающего всего две буквы, по процедуре
Шеннона–Фано.
Буквы в табл. 2.3 располагаются в порядке убывающих вероятностей. Букве с большей вероятностью приписывается символ 0
(или 1), с меньшей – (1 или 0).
Таблица 2.3. Исходная таблица (ℓ = 1)
Буква
p(xi)
Разбиения
Коды
nк
х1
х2
0,788
0,212
I
II
0
1
1
1
∑=1
Очевидная длина кодового слова nк = 1.
3. Производится укрупнение символов источника сообщений до
двух букв (ℓ = 2). Кодируемые сообщения уi состоят из всех различных попарных комбинаций x1 и x2. Вероятность значений y определяется произведением вероятностей значений x, составляющих y.
Данные заносятся в табл. 2.4. для своих вероятностей.
После заполнения таблицы определяется среднее число символов в полученном коде (см. формулу 2.2) и оценивается число символов n1 в коде на исходную букву xi алфавита источника (n1 = nср /
ℓ, где ℓ − число объединяемых букв).
Таблица 2.4. Укрупнение символов источника до двух букв (ℓ = 2)
28
Буква
р(уi)
у1 = х1х1
у2 = х1х2
у3 = х2х1
у4 = х2х2
0,621
0,167
0,167
0,045
∑=1
1
0
1
Разбиения
2
3
──10
11
──110
111
Коды
nк
0
10
110
111
1
2
3
3
4. Производится последующее укрупнение символов источника
до трех букв (ℓ = 3), строится и заполняется табл. 2.5 по аналогии с
табл. 2.4. Однако теперь укрупненных букв zi будет уже 8.
Таблица 2.5. Укрупнение символов источника до трех букв (ℓ = 3)
Буква
z1 = х1х1х1
z2 = х1х1х2
z3 = …
z4 = …
z5 = …
z6 = …
z7 = …
z8 = х2х2х2
p(zi)
0,489
0,199
…
…
…
…
…
0,095
Разбиения
Коды
nк
…
…
…
…
…
…
…
…
…
∑=1
Определяется среднее число символов в полученном эффективном коде и при ℓ = 3 находится число символов на одну исходную
букву источника xi. Построить на одном графике для у и для z зависимости nср(ℓ) и nк(ℓ) и сделать соответствующие выводы.
5. Для значений у (табл. 2.4) и z (табл. 2.5) строятся кодовые деревья. Двигаясь по кодовому дереву сверху вниз, необходимо определить для каждой из букв у и z (при ℓ = 2 и ℓ = 3) соответствующие
им кодовые комбинации.
6. Записать для значений z коды впритык, без разделительных
символов, в последовательном порядке от z1 до z8, поскольку эффективные коды – это коды без запятой. В получившейся последовательности заменить 5-й одиночный символ (0 или 1) на противоположный (1 или 0) и декодировать весь искаженный ряд, отметив
новые получившиеся значения zi. Проделать это же самое для записи значений z в обратном порядке от z8 до z1. Определить в обоих случаях длину трека ошибки. Сформулировать основные выводы по заданию.
После выполнения практического расчета задание сдается преподавателю для проверки.
29
3. ПОМЕХОУСТОЙЧИВОЕ КОДИРОВАНИЕ
3.1. Основные характеристики корректирующих кодов
Непосредственная передача сообщений при применении эффективных кодов по каналу связи с шумами приводит к недопустимо
большим искажениям (трек ошибки). Однако эффективное кодирование, устраняющее статистическую избыточность в передаваемом
сообщении, наилучшим образом подготавливает непрерывную кодовую последовательность, полученную после первичного кодирования сообщений источника, к последующему помехоустойчивому
кодированию с помощью корректирующих кодов в кодере канала.
Целенаправленное введение избыточности при помехоустойчивом
кодировании путем добавления дополнительных символов в кодовые информативные группы, позволяет обнаруживать и исправлять ошибки.
Теория помехоустойчивого кодирования базируется на результатах исследований, проведенных Шенноном и сформулированных
им в виде второй теоремы для канала с шумом: при любой производительности источника сообщений, меньшей, чем пропускная способность канала, существует такой способ кодирования, который
позволяет обеспечить передачу всей информации, создаваемой источником сообщений, со сколь угодно малой вероятностью ошибки.
Доказано только существование искомого способа кодирования
и показано, что она может быть сделана сколь угодно малой. Отсюда принципиальная необходимость введения избыточности в кодируемые последовательности для компенсации потерь информации
в канале из-за действия помех. При этом помехозащищенные коды
находятся эвристическим путем различными авторами, чьи имена
и приобретают предлагаемые коды.
К числу основных характеристик кода относятся:
− длина кода (число разрядов кода) n;
− основание кода m;
− полное число кодовых комбинаций N0;
− число разрешенных кодовых комбинаций N;
− число запрещенных кодовых комбинаций N З (N З = N 0 – N);
− число информационных символов в коде k;
− число проверочных символов в коде r = n – k;
− вес кодовой комбинации (число единиц в комбинации) W;
− относительная скорость кода R = = k/n;
30
− избыточность кода ǽ = 1 – log N/ logN0 и для двоичного кода
(m = 2)
ǽ = 1 – k/n = r/n.
(3.1)
Вводится понятие кодового расстояния (расстояние Хемминга)
для отличия одной кодовой комбинации от другой. Кодовое расстояние определяется числом разрядов, в которых одна кодовая
комбинация отличается от другой. Наименьшее расстояние Хемминга, взятое для всего кода по всем парам кодовых разрешенных
комбинаций, называется минимальным кодовым расстоянием, и
в дальнейшем будет обозначаться буквой d. Хемминг показал, что
для обнаружения всех ошибок кратности g, где g – число ошибок,
требуется код с минимальным расстоянием
d ≥ g + 1,
(3.2)
а при исправлении ошибок кратности g минимальное расстояние d
должно удовлетворять условию
d ≥ 2g + 1,
(3.3)
где кратность g ≤ (d – 1)/2 – принимает только целочисленные значения.
Большинство разработанных до настоящего времени кодов предназначено для корректирования взаимно независимых ошибок определенной кратности и пачек (пакетов) ошибок.
3.2. Простейшие помехоустойчивые коды
Код с повторением.
При построении помехоустойчивых кодов не обойтись без дополнительных символов, которые должны быть присоединены к
кодовым словам безызбыточного кода. Эти символы уже не несут
информации о передаваемых сообщениях, но могут дать информацию о происшедших при передаче ошибках, поэтому дополнительные символы называются контрольными или проверочными.
Самый простой способ, позволяющий исправлять ошибки, состоит в том, что каждый информационный символ повторяется несколько раз. Например, символ 0 заменяется блоком из n нулей, а
символ 1 – блоком из n единиц. При декодировании n-буквенного
блока, содержащего ошибочные символы, решение принимается
«большинством голосов» (мажоритарный метод). Если в принятом блоке нулей больше, чем единиц, то он декодируется как 00…0
(т. е. считается, что был послан нулевой символ), в противном слу31
чае – как 11…1. Такое правило декодирования позволяет восстановить посланные символы, если помехи в канале искажают менее
половины символов в каждом передаваемом блоке. Если длину блока n выбрать достаточно большой, то практически исправляются
все ошибки, но передача ведется чрезвычайно медленно. По этой
причине код с повторением не имеет большого практического значения, однако правило его декодирования (голосование) содержит
в себе весьма полезную идею, которая с успехом применяется в других, практически более интересных помехоустойчивых кодах.
Код с постоянным весом (КПВ)
Число кодовых комбинаций N0 для кода с основанием m и числом
элементов n определяется известным выражением N0 = mn. Если все
возможные комбинации n-элементного кода используются для кодирования сообщений, то такой непомехозащищенный первичный
код принято называть простым, обыкновенным или примитивным.
В зависимости от соотношения числа элементов кодовых комбинаций коды делятся на равномерные, каждая комбинация которых
содержит одинаковое число разрядов, и неравномерные (пример –
эффективные коды). Равномерный пятиэлементный код получил
наибольшее распространение. Это обусловлено тем, что при передаче текста (телеграмм) число наиболее часто употребляемых знаков
не превышает 32 (число букв в русском алфавите), хотя общее число
подлежащих передаче знаков составляет 52 (буквы, цифры, знаки
препинания). С целью сокращения средней длительности знака все
знаки разбиваются на два регистра, т. е. одну кодовую комбинацию
присваивают двум знакам. Такой пятиэлементный код используется как международный телеграфный код – МТК-2. Однако этот код
является непомехозащищенным, поскольку у него минимальное
кодовое расстояние равно единице.
К кодам с постоянным весом (КПВ) относятся все коды, в которых каждая разрешенная комбинация содержит одинаковое число
единиц. Число разрешенных комбинаций такого кода N определяется как число сочетаний из n элементов по W, где W – вес кода
N = CnW = n!/W! (n – W)!
Типичным примером такого кода является код «3 из 7», в котором каждая кодовая комбинация содержит три единицы и четыре
нуля (стандартный телеграфный код № 3). Из общего числа комбинаций семиэлементного N0 = 27 = 128 кода, число разрешенных
комбинаций N составляет 35 (С73). Избыточность семиэлементного
кода с весом 3, подсчитанная по формуле (3.1), равна
32
ǽ = 1 – log2 35/ log 2 27 ≈ 0,26.
Минимальное кодовое расстояние КПВ равно двум, т. е. такой
код обнаруживает одиночные ошибки. Однако такой код обнаруживает также двойные, тройные и т. д. ошибки одинаковых элементов, за исключением случаев, когда одна из единиц переходит
в нуль, а один из нулей – в единицу. Искажение такого вида называется смещением. Очевидно, что при переходе двух единиц в нуль
и двух нулей в единицу искажения также не обнаруживаются. В
полностью асимметричных каналах, в которых имеет место только
один вид ошибок (преобразование нулей в единицы или единиц в
нули), такой код позволяет обнаруживать все ошибки.
Ошибки при приеме комбинаций КПВ с весом W обнаруживаются посредством счетчика единиц, коэффициент счета которого равен W. Если по окончании приема комбинации счетчик не вернется
в исходное положение, то это означает, что принятая комбинация
искажена.
Код с числом единиц, кратных трем
В этом коде к кодовым комбинациям k-элементного простого кода добавляются два проверочных элемента так, чтобы число
единиц в кодовых комбинациях нового n = k + 2–элементного кода
было кратно 3. Этот код позволяет обнаружить все одиночные и
все четные ошибки одинаковых элементов (двойные, четверные и
т. д.). Не обнаруживаются двойные ошибки вида смещения и тройные ошибки одинаковых элементов. Пренебрегая весьма малой вероятностью появления тройных ошибок, можно считать, что необнаруженные ошибки будут иметь место только при наличии двойных ошибок типа смещения.
Согласно принципу построения кода, любая n-элементная комбинация может содержать 3i единиц, где i – целое число, принимающее одно из значений 1, 2, …, I. Обнаружение ошибок в таком
коде осуществляется посредством счетчика на 3.
Коды Бергера
Проверочные символы у кода Бергера представляют двоичную
запись числа единиц в последовательности информационных символов. Примером такого кода при k = 3 является код: 00000, 00101,
01001, 01110, 10001, 10110, 11010, 11111. Коды Бергера применяются, как правило, в асимметричных каналах. В симметричных
каналах (вероятности ошибок приема 1 и 0 равны) код обнаруживает все одиночные ошибки и некоторую часть многократных.
33
Код Манчестера (корреляционный код)
При построении кода Манчестера каждый элемент обыкновенного (первичного) кода преобразуется в два элемента, при этом единица преобразуется в 10, а нуль – в 01. Таким образом, код Манчестера базируется на методе двукратного повторения с инверсией
элементов, и он будет содержать вдвое больше символов, чем первичный код. Поэтому вне зависимости от числа элементов первичного кода коэффициент избыточности кода ǽ = 1/2. Код Манчестера
позволяет обнаруживать однократные ошибки, поскольку минимальное кодовое расстояние кода равно двум. Помехоустойчивость
кода обусловлена тем, что появление необнаруживаемой сшибки
возможно только в том случае, когда два рядом расположенных
элемента, соответствующих одному элементу первичного кода, будут искажены так, что единица перейдет в нуль, а нуль – в единицу. Наряду с возможностью обнаружения ошибок, код Манчестера
применяется как синхронизирующий код для получения при приеме импульсов тактовой синхронизации, поскольку при передаче
любой информационной последовательность (подряд несколько
единиц или нулей) итоговое значение единиц и нулей будет одинаковым и чередующимся. Это свойство прореживания одноименных
символов противоположными позволяет легко получать импульсы
тактовой синхронизации, т. е. импульсы, определяющие начало
и конец каждого элемента кода. Такая процедура, обеспечивающая равенство чередующихся элементов 1 и 0, получила название
скремблирования. Это позволяет относить код Манчестера и к классу синхронизирующих кодов.
Инверсный код
В основу построения этого кода, характеризующегося высокой
эффективностью при простоте реализации, положен метод повторения исходной кодовой комбинации. При этом передаваемая комбинация в зависимости от четного или нечетного числа единиц в
ней либо просто повторяется, либо повторяется в инвертированном
виде. Поясним это положение на примере пятиэлементного кода.
Комбинации
первичного кода
10010
10110
01000
Комбинации инверсного кода
Основные элементы
Дополнительные
10010
10110
01000
10010
01001
10111
Пусть пятиэлементная комбинация содержит четное число единиц. Тогда, согласно принципу построения кода, дополнительные
34
пять элементов будут совпадать с основным. Если же передаваемая
комбинация содержит нечетное число единиц, то дополнительные
элементы будут соответствовать инвертируемой исходной комбинации. Таким образом, избыточность инверсного кода ǽ = 0,5, а минимальное кодовое расстояние d = 4 при любом k. Следовательно,
такой код позволяет обнаруживать все тройные ошибки и исправлять однократную ошибку. Процедура обнаружения ошибок при
приеме комбинаций инверсного кода состоит из двух операций.
Сначала суммируются единицы, содержащиеся в первых n/2 элементах. Если их окажется четное число, то вторые n/2 элементов
принимаются в прямом виде. После этого обе зарегистрированные
комбинации сравниваются поэлементно (первый элемент с первым, второй со вторым и т. д.), и при обнаружении хотя бы одного
несовпадения вся последовательность из n элементов бракуется.
Если же количество единиц среди первых n/2 элементов нечетное,
то вторые n/2 элементов принимаются инвертированными. Затем,
как и в предыдущем случае, обе зарегистрированные комбинации
сравниваются поэлементно. Наличие несовпадений указывает на
то, что принятая комбинация искажена.
Исправление одиночной ошибки происходит следующим образом. Предположим, что в принятой комбинации один из элементов
искажен. Если этот элемент расположен в первой половине кодовой
комбинации, то при сложении по модулю два первой и второй половин кодовых комбинаций совпадает только одна пара, что является
признаком искажения информационного элемента. Если искаженный элемент расположен во второй половине кодовой комбинации, то при сложении по модулю два только одна пара элементов
не совпадает, что указывает на искажение проверочного элемента.
Основным недостатком инверсных кодов является их высокая избыточность.
Код с проверкой на четность (КПЧ)
Блочный код, образуемый добавлением всего одного элемента к
комбинации простого k-элементного кода, представляет собой код с
четным числом единиц при условии, что количество единиц в кодовых комбинациях полученного нового n = k + 1- элементного кода
будет четным. Такой код характеризуется минимальным кодовым
расстоянием d = 2 и поэтому, согласно (3.2), позволяет обнаружить
все кодовые комбинации, содержащие один искаженный элемент.
Наличие четного числа единиц в любой неискаженной кодовой
комбинации дает возможность обнаружить все комбинации, в которых искажено нечетное число элементов.
35
Алгоритм оценки проверочного символа r сводится к суммированию числа единиц в кодовой комбинации и при четном их числе
проверочный символ r будет равен нулю, а при нечетном – единице,
т. е.
0 − при четном весе W = 2i,
(3.4)
r = a1 ⊕ a2 ⊕ ... ⊕ ak = 
1 − при нечетном весе W = 2i + 1,
где k – число информационных символов в коде. Избыточность
кода с четным числом единиц ǽ = 1/n минимальна.
Процедура декодирования КПЧ сводится к подсчету числа единиц при суммировании (по модулю два) принимаемой комбинации
с числом символов в коде с учетом проверочного элемента n = k + 1
0 − искажений нет, S = 0,
(3.5)
S = a1* ⊕ a2* ⊕ ... ⊕ a k* ⊕ r * = 
1 − обнаружена ошибка, S = 1,
где знак * соответствует символу, прошедшему через зашумленный
канал.
Результат проверок на четность, записанный в виде двоичного
числа S, называется синдромом. Равенство синдрома нулю указывает на отсутствие ошибок в принятой комбинации. Термин «синдром» (от греч. – вместе бегущий) часто используется и в медицине
как сочетание (комплекс) симптомов болезни, характерное для определенного заболевания (в технике кодирования – как искажение
принятого кода). Синдром также иногда называют опознавателем.
Код с повторением и код с проверкой четности – до некоторой
степени антиподы. Возможности первого кода исправлять ошибки практически безграничны, но он крайне «медлителен». Второй очень быстр (всего один дополнительный символ), но зачастую «легкомысленен». В реальных каналах связи, как правило,
приходится считаться с возможностью ошибок более чем в одном
символе, поэтому в чистом виде КПВ применяется крайне редко.
Гораздо чаще применяют коды с несколькими проверочными символами и, соответственно, с несколькими проверками на четность.
Они позволяют не только обнаруживать, но и исправлять ошибки,
и не только одиночные, но и кратные, и притом делать это гораздо
эффективнее, чем код с повторением. В частности, код Хемминга
позволяет исправлять однократную ошибку всего при трех проверочных символах.
36
Защита по горизонтали
№
кодового слова
Код с проверкой на четность «по горизонтали и вертикали»
(итеративный код)
Идея создания итеративных кодов принадлежит П. Элайесу.
Если расположить последовательность М-разрядных кодовых
слов с проверкой на четность
№ разряда
(М-защитный разряд) в виде
1 2 3 4 ... M
матрицы, содержащей L строк,
r
причем каждый разряд L-й
1
строки дополняет соответстr
2
вующий столбец до КПЧ (рис.
r
3.1), то получим код с проверкой
3
на четность «по горизонтали и
r
4.
вертикали». Общее число раз.
.
.
рядов такого кода n = ML. Число
.
.
информационных символов nи =
... r
L r r r r
= (M – 1) (L – 1), минимальное
кодовое расстояние d = 4 (исЗащита по вертикали
правляет одну ошибку).
Отметим, что КПЧ иногда Рис.3.1. Итеративный КПЧ
называют кодом с защитой по
паритету.
3.3. Помехоустойчивые коды Хемминга
Увеличивая число дополнительных проверочных разрядов, и
формируя по определенным правилам проверочные символы r,
равные 0 или 1, можно усилить корректирующие свойства кода
так, чтобы код позволял не только обнаруживать, но и исправлять
ошибки. Код Хемминга имеет значение минимального кодового
расстояния d = 3, что позволяет исправлять одну ошибку и обнаруживать две (см. формулы 3.2 и 3.3). На этом и основано построение кода Хемминга. Код Хемминга относится к блочным кодам,
которые обозначаются как (n, k), где n – длина кода, k – число информационных символов. В общем случае для классических кодов
Хемминга
n = 2r – 1, k = 2r – 1 – r,
(3.6)
т. е. к ним относятся коды (7, 4), (15, 11), (31, 26), (63, 57) и т. д.
При больших значениях r скорость блочного кода, определяемая
равенством R = k/n (безразмерна), близка к 1.
В простейшем варианте для кода (7, 4) при заданных четырех
информационных символах (i1, i2, i3, i4) будем полагать, что они
сгруппированы в начале кодового слова, хотя это и не обязательно.
37
Дополним эти информационные символы проверочными (r = 3), задавая их следующими равенствами проверки на четность (предложил Хемминг):
r1 = i1 ⊕ i2 ⊕ i3,
r2 = i2 ⊕ i3 ⊕ i4,
(3.7)
r3 = i1 ⊕ i2 ⊕ i4,
где знак ⊕ означает сложение по модулю 2, индексу 1 соответствует
старший разряд. Например, информационное слово 1010 дополняется проверочными символами 011.
В соответствии с этим алгоритмом после прохождения канала
связи (индекс *) на вход приемной части поступает кодовое слово
A * = i1* + i2* + i3* + i4* + r1* + r2* + r3*. (3.8)
На приемной стороне в декодере в режиме исправления ошибки
строится последовательность трехбитового синдрома:
S1 = r1* ⊕ i1* ⊕ i2* ⊕ i3* ,
S2 = r2* ⊕ i2* ⊕ i3* ⊕ i4* , (3.9)
S3 = r3* ⊕ i1* ⊕ i2* ⊕ i4* .
В данном случае синдром S = (S1, S2, S3) представляет собой сочетание результатов проверки на четность соответствующих символов кодовой группы и характеризует определенную конфигурацию
ошибок (вектор ошибки).
Вектором ошибки (шумовым) называют n-разрядную последовательность, имеющую единицы в разрядах, подвергшихся искажению, и нули во всех остальных разрядах. Например, при искажении второго символа принимаемой кодовой комбинации шумовой
вектор записывается в виде 0100000. Любую искаженную кодовую
комбинацию можно рассматривать теперь как сумму по модулю 2
истинной разрешенной кодовой комбинации и вектора ошибки. В
этом случае синдром в соответствии с (3.9) будет равен 111. При отсутствии ошибок в результате всех проверок на четность образуется синдром, состоящий из всех нулей – 000.
Таким образом, количество подлежащих исправлению ошибок
является определяющим для выбора числа избыточных (проверочных) r = n – k символов. Их должно быть достаточно для того, чтобы обеспечить необходимое число синдромов.
38
Если, например, необходимо исправить все одиночные независимые ошибки, то исправлению подлежат в соответствии с шумовыми векторами n ошибок: 100…00, 010…00, …, 000…10, 000…01,
т. е. число различных ненулевых синдромов должно быть равно n
(плюс один – нулевой для безошибочного приема). Это условие как
раз и выполняется для классических кодов Хемминга (см. формулу
3.6). Такие коды при равенстве числа синдромов числу разрядов в
кодовых комбинациях называются плотноупакованными.
Если отказаться от группирования проверочных символов в
конце кодовой комбинации и перетасовать их с информационными
символами соответствующим образом, то можно сделать так, чтобы двоичное число синдрома соответствовало номеру искаженного
при передаче разряда кода. Именно коды, в которых синдромы реализуют это правило, известны как первоначальные коды Хемминга. Это приводит к необходимости поэлементного формирования
проверочных символов. Позже были разработаны циклические
коды, которые включают коды Хемминга с группированием проверочных символов в конце кодовых комбинаций, что позволяет
формировать проверочные символы сразу в целом. При этом коды
синдромов не соответствуют номерам искаженных символов, и в
декодерах приемной стороны требуется постановка дешифраторов
(локаторов ошибок).
Однако плотноупакованные классические коды Хемминга при
значениях чисел проверочных символов r = 3, 4, 5, … существуют
только, соответственно, для числа информационных символов k =
= 4, 11, 26, … (см. формулу 3.6). При промежуточных значениях чисел информационных символов применяют усеченные коды
Хемминга. Так, например, для равномерного пятиэлементного
кода при k = 5 используется код (15, 11) с вычетом из n и k шести
символов, что приводит к усеченному коду (9, 5).
Усеченный код (9, 5) имеет r = 4 проверочных символа и, следовательно, 4 разряда в синдроме. При этом число синдромов равно
2r = 16, в то время как при 9 символах в кодовом слове их требуется
всего 10 (один – нулевой). Это и приводит к тому, что код становится неплотноупакованным с перебором в 6 синдромов. Алгоритм
построения кода (9, 5) следующий:
r1 = i2 ⊕ i3,
r2 = i1 ⊕ i3 ⊕ i4,
r3 = i2 ⊕ i4 ⊕ i5,
(3.10)
r4 = i1 ⊕ i2 ⊕ i5.
39
По аналогии с (3.9) алгоритм нахождения четырех синдромов на
приемной стороне сводится к суммированию четырех строк (3.10).
Код Хемминга можно сделать расширенным путем добавления к
стандартным проверочным символам в конце кодовой группы еще
одного (0 или 1), доводящего общее число единиц в коде до четного
значения. При этом минимальное кодовое расстояние увеличивается на единицу и становится равным d = 4, что ведет за собой возможность обнаруживать не две ошибки, а три, но значение исправляемой ошибки остается прежним, равным единице (см. формулы
3.2 и 3.3).
Техническое построение кодека кода Хемминга выполняется достаточно просто. Кодирующее устройство для блочного группового
кода (n, k) состоит из k-разрядного сдвигающего регистра и r = n −
k сумматоров по модулю 2. Информационные символы одновременно поступают на вход регистра и на выход кодирующего устройства
через коммутатор. С поступлением k-го информационного символа
на выходах сумматоров формируются проверочные символы, которые последовательной группой поступают на выход кодера вслед за
информационными. Декодер кода состоит также из k-разрядного
регистра, r сумматоров по модулю 2, схемы сравнения, анализатора
ошибок и корректора. Регистр служит для запоминания информационных символов принятой кодовой последовательности, из которых
в сумматорах формируются биты синдромов. Анализатор ошибок по
конкретному виду синдрома определяет места ошибочных символов.
Исправление информационных символов производится в корректоре. Определим некоторые параметры кода Хемминга (9, 5).
3.4. Параметры кода Хемминга
(практическое задание)
В задании рассматривается блочный усеченный код Хемминга
(9, 5).
1. Подготовить к заполнению табл. 3.1.
Таблица 3.1. Усеченный код Хемминга
Символы
Код МТК-2
Код (9, 5)
Ошибки
Синдром
Ф
И
О
В первый столбец таблицы в три строки вписать свои инициалы:
(Фамилия, Имя, Отчество)
40
2. По данным табл. 3.2 выписать во второй столбец табл. 3.1 соответствующие пятисимвольные коды МТК-2 для этих букв (без
учета кода цифрового регистра).
3. Определить по формуле (3.10) значения четырех проверочных
символов и в третьем столбце табл. 3.1 записать соответствующие
коды (9, 5).
4. В четвертый столбец табл. 3.1 записать коды (9, 5) с однократными ошибками в соответствующих символах кодов. Номера символов, в которые вводятся ошибки, определяются по номеру квартала и даты рождения студента. Например, при рождении 07 ноябТаблица 3.2. Международный телеграфный код №2 (МТК-2)
Числа
в десятичной
форме
24
23
22
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
0
0
0
0
1
1
1
1
0
0
0
0
1
1
1
1
0
0
0
0
1
1
1
1
0
0
0
0
1
1
1
1
0
Те же числа в двоичной форме
Регистры
2
20
русский цифры латинский
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
Т
5
T
Возврат каретки
О
9
O
Пробел
Х
Щ
H
Н
,
N
М
.
M
Перевод строки
Л
)
L
Р
4Ч
R
Г
Ш
G
И
8
I
П
0
P
Ц
:
C
Ж
=
V
Е
3
E
З
+
Z
Д
Кто там? D
Б
?
B
С
‘
S
Ы
6
Y
Ф
Э
F
Ь
/
X
А
A
В
2
W
Й
Ю
J
Цифровой регистр
У
7
U
Я
1
O
К
(
K
Латинский регистр
Русский регистр
41
ря (4-й квартал) получается трехзначное число 407, в соответствии
с которым в первой строке табл. 3.1 в коде искажается символ 4, во
вторую строку ошибка не вводится, а в третьей строке искажается
символ 7 (0 заменяется на 1 или 1 заменяется на 0). Определить все
10 синдромов при однократных ошибках во всех последовательных
символах кода и записать в табл. 3.3. Синдромы для ошибок, определенных для числа 407, записать в пятый столбец табл. 3.1.
Таблица 3.3. Значения синдромов для позиций символов
1
2
3
4
5
6
7
8
9
0
5. Для исходного индивидуального числа 407 в строчку записываются шумовые векторы.
6. В один из исходных кодов табл. 3.1 вводятся две ошибки на
любых позициях, определяется синдром, сравнивается с синдромами из табл. 3.3 и комментируется результат.
7. Заканчиваются расчеты выводами, и в дальнейшем текст расчетов сдается для проверки преподавателю.
42
4. ЦИКЛИЧЕСКИЕ КОДЫ
4.1. Полиноминальное представление циклических кодов
Название циклические коды (ЦК) получили из-за своего основного свойства: циклическая перестановка символов разрешенной
кодовой комбинации дает также разрешенную кодовую комбинацию. При циклической перестановке символы кодового слова перемещаются слева направо на одну позицию, причем крайний справа
символ переносится на место крайнего левого.
Если, например, А1 = 101100, то разрешенной кодовой комбинацией будет и А2 = 010110, полученная циклической перестановкой.
Отметим, что перестановка производится вместе с проверочными
символами, и по правилам линейных кодов сумма по модулю 2
двух разрешенных кодовых комбинаций дает также разрешенную
кодовую комбинацию. Описание ЦК связано с представлением кодовых комбинаций в виде полиномов (многочленов) фиктивной переменной Х. Для примера переведем кодовое слово А1 = 101100 в
полиномиальный вид
i
Код
5
1
4
0
3
1
2
1
1
0
0
0
При этом А1 (X) = 1 · X5 + 0 · X4 + 1 · X3 + 1 · X2 + 0 · X1 + 0 · X0 =
= X5 +X 3 + X2.
Действия с кодовыми векторами, представленными в виде полиномов, производятся по правилам арифметики по модулю 2, в которой вычитание равносильно сложению. Так, из равенства Xn − 1 = 0
получаем X n = 1. Прибавив к левой и правой частям выражения по
единице, имеем X n + 1 = 1 ⊕ 1 = 0. Таким образом, вместо двучлена
Xn − 1 можно ввести Xn + 1 или 1 + Xn, из чего следует, что Xk ⊕
Xk = Xk (1 ⊕ 1) = 0, и при последующих операциях с полиномами
необходимо вычеркивать пары фиктивных переменных Х с одинаковыми степенями.
Приведем далее порядок суммирования (вычитания), умножения и деления полиномов с учетом того, что операция суммирования осуществляется по модулю 2. В примерах используем вышеприведенные кодовые комбинации
А1 = А1 (X) = X 5 + X 3 + X 2 и А2 = А2 (Х) = Х 4 + Х 2 + Х.
Суммирование (вычитание):
А1 + А2 = А1 − А2 =
= X 5 + Х4+ X 3 + X 2+ X 2+ X = X 5 + Х4+ X 3 + Х
43
или
А1
101100
⊕
А2 010110
_______________________________
∑
111010 = X5 + Х4 + X3 + Х.
Умножение:
А1 × А2 = (X 5 + X 3 + X 2) × (Х 4 + X 2 + Х) =
= Х9+Х7 + Х6+ Х7+ X 5+
4
6
+ Х + Х + Х 4 + X 3 = Х 9 + X 5 + X 3 = 1000101000.
Деление:
X 5 + X 3 + X 2│ Х4 + X 2+ Х
−
¯¯¯ X ¯¯¯¯¯¯¯¯
X 5+ X 3+ X 2
——————
0
0
0 − остаток при делении R(X) = 0.
Из последнего примера следует, что при циклическом сдвиге
вправо на один разряд необходимо исходную кодовую комбинацию
поделить на X, а умножение на X эквивалентно сдвигу влево на
один символ.
4.2. Порождающие полиномы циклических кодов
Формирование разрешенных кодовых комбинаций ЦК Bi (X) основано на предварительном выборе так называемого порождающего
(образующего) полинома G(X), который обладает важным отличительным признаком: все комбинации Bi (X) делятся на порождающий полином G(X) без остатка, т. е.
Bi (X) / G(X) = Ai (Х),
(4.1)
где Ai (Х) − информативный полином (кодовая комбинация первичного кода, преобразуемого в корректирующий ЦК).
Поскольку ЦК относятся к классу блочных разделимых кодов, у
которых при общем числе символов n число информационных символов в Ai (Х) равно k, степень порождающего полинома определяет
число проверочных символов r = n − k.
Из этого свойства следует сравнительно простой способ формирования разрешенных кодовых комбинаций ЦК − умножение комбинаций информационного Ai(Х) на порождающий полином
44
Bi (X) = Ai (Х)G(X).
(4.2)
В теории циклических кодов доказывается, что порождающими
могут быть только такие полиномы, которые являются делителями
двучлена (бинома) X n + 1
(X n + 1) / G(X) = H(X) − (при остатке R(X) = 0).
(4.3)
Некоторые из порождающих полиномов приведены в табл. 4.1.
Таблица 4.1. Порождающие полиномы
r − степень
полинома
G(X)
Порождающий
полином
G(X)
1
X+1
11
2
X2+ X + 1
111
3
4
5
6
Запись
Запись
полинома полинома
по mod 2 по mod 8
X3+ X + 1
1011
X3+ X2+ 1
1101
X 4 +X 3 + 1
11001
X4+ X + 1
10011
X 4 + X 2 + X + 1 10111
X 4 + X 3 + X2 + 1 11101
X 5 + X2 + 1
100101
X5+ X3+ 1
101001
...
...
X 6 + X 5 + X 4 + 1111111
X3+ X2+ X1+ 1
...
n
k
Примечание
3
3
2
7
3
1
13
15
31
23
27
35
45
51
7
7
15
15
7
7
31
31
4
4
11
11
3
3
26
26
Код
с проверкой на
четность (КПЧ)
Код
с повторением
Классический
код Хемминга
Классический
код Хемминга
Коды ФайраАбрамсона
Классический
код Хемминга
177
7
1
Код
с повторением
Восьмеричная система счисления для записи многочленов (столбец 4 в табл. 4.1) выбрана, в частности, из соображений экономии
длины записи (бумаги) в три раза при больших объемах табулированных значений, что подчеркивает известный недостаток двоичной системы счисления.
Следует отметить, что с увеличением максимальной степени r
порождающих полиномов резко увеличивается их количество. Так,
при r = 3 всего два полинома, а при r = 10 их уже несколько десятков. Первый порождающий полином минимальной степени r = 1,
удовлетворяющий условию (4.3), формирует код с проверкой на
четность при двух информативных символах и одном проверочном,
обеспечивающем обнаружение однократной ошибки, поскольку
минимальное кодовое расстояние dmin = 2.
У второго кода с повторением единственного информационного
символа возможности обнаружения и исправления ошибок безгра45
ничны, поскольку число повторений ℓ определяет минимальное кодовое расстояние.
Следующие порождающие полиномы со степенью r = 3 в табл.
4. 1 позволяют сформировать набор классических кодов Хемминга
(7, 4). Отметим, что два варианта порождающих полиномов кода
Хемминга (7, 4) в виде 1011 и 1101, представляют собой так называемые двойственные многочлены (полиномы). Весовые коэффициенты исходного полинома, зачитываемые слева направо, становятся весовыми коэффициентами двойственного полинома при
считывании их справа налево. Говоря образно, набор весовых коэффициентов «вывертывается наизнанку». Наряду с тем, что порождающие полиномы кода Хемминга (7, 4) являются двойственными
друг другу, они также являются неприводимыми.
Неприводимые полиномы не делятся ни на какой другой полином степени меньше r, поэтому их называют еще неразложимыми,
простыми и примитивными. Далее в табл. 4.1 при значениях r = 4 и
5 попадают следующие классические коды Хемминга (15, 11) и (31,
26). Порождающие их полиномы также являются двойственными
друг к другу и неприводимыми. Напомним, что к классическим кодам Хемминга относятся коды, у которых n = 2r − 1, a k = 2r − 1 −
– r, с минимальным кодовым расстоянием dmin = 3, позволяющим
исправлять однократные ошибки и обнаруживать двойные.
При значениях r = 4 в табл. 4.1 попадают двойственные порождающие многочлены кода Абрамсона (7, 3), являющиеся частным
случаем кодов Файра. Число проверочных символов r = 4 определяет общее число символов в коде (значность кода), поскольку
для этих кодов n = 2r – 1 − 1. Эти коды исправляют все одиночные
и смежные двойные ошибки (т. е. серии длиной 2). Помещенные
в табл. 4.1 коды Абрамсона (7, 3) являются первыми циклическими кодами, исправляющими серийные ошибки (пакеты ошибок).
В этом применении ЦК оказываются особенно эффективными.
Серийные ошибки возникают в результате воздействия в канале
передачи сообщений помех импульсного характера, длительность
которых больше длительности одного символа. При этих условиях
ошибки уже не независимы, а возникают пачками, общая длительность которых соответствует длительности помехи.
В заключение на основании данных табл. 4.1 приведем все возможные порождающие полиномы для кодовых комбинаций с числом символов n = 7. В соответствии со свойством (4.3) порождающих полиномов G(X) бином X 7 + 1 раскладывается на три неприводимых полинома:
46
X 7 + 1 = (X + 1)(X 3 + X 2 + 1)(X 3 + X + 1) =
= G1 (X) × G2 (X) × G3 (X),
(4.4)
каждый из которых является порождающим для следующих кодов:
G1 (X) = Х + 1 − код с проверкой на четность, КПЧ (7, 6),
G2 (X) = X 3 + X 2 + 1 − первый вариант кода Хемминга (7, 4),
G3 (X) = X 3 + Х + 1 − двойственный, второй вариант кода Хемминга.
Кроме того, различные вариации произведений G1,2,3 (X) дают
возможность получить остальные порождающие полиномы:
код Абрамсона (7, 3) − G4 (X) = G1 (X) · G2 (X) =
= (X + 1) · (X 3 + X 2 + 1) = X 4 + X 2 + X + 1,
двойственный G4 (X) − G5 (X) = G1 (X) · G3 (X) =
= (X + 1) · (X 3 + X + 1) = X 4 + X 3 + X 2 + 1,
код с повторением (7, 1) − G6 (X) = G2 (X) · G3 (X) =
= (X 3 + X 2 + 1) · (X 3 + X + 1) = X 6 + X 5 + X 4 + X 3 + X 2 + X + 1.
Таким образом, для постоянного заданного значения n все возможные порождающие полиномы ЦК размещаются между кодами
с проверкой на четность (n, n − 1), где r = 1, и кодами с повторением
(n, 1), где r = n − 1, их правомерно называют «кодами антиподами».
При выборе применяемых в системах связи корректирующих
кодов необходимо позаботиться о том, чтобы, во-первых, избыточность кода была минимальной, т. е. относительная скорость кода
или эффективность кода была максимальной, а, во-вторых, техника кодирования и декодирования была по возможности проста.
4.3. Принципы формирования и обработки комбинаций
циклических кодов
На основании материалов предыдущего раздела можно дать следующее определение циклических кодов (ЦК).
Циклические коды составляют множество многочленов Вi (Х)
степени n − 1 и менее (до r = n − k, где r − число проверочных символов), кратных порождающему (образующему) полиному G(Х)
степени r, который в свою очередь должен быть делителем бинома
X n + 1 (остаток после деления бинома на G(X) должен равняться
нулю).
Учитывая, что ЦК принадлежат к классу линейных, групповых
кодов, сформулируем ряд основных свойств, им присущих.
47
1. Сумма разрешенных кодовых комбинаций ЦК образует разрешенную кодовую комбинацию
Bi (X) ⊕ Bj (X) = Bk (X).
(4.5)
2. Поскольку к числу разрешенных кодовых комбинаций ЦК
относится нулевая комбинация 000...00, то минимальное кодовое
расстояние dmin для ЦК определяется минимальным весом разрешенной кодовой комбинации:
dmin = Wmin.
(4.6)
3. Циклический код не обнаруживает только такие искаженные
помехами кодовые комбинации, которые приводят к появлению на
стороне приема других разрешенных комбинаций этого кода из набора N0.
4. Значения проверочных элементов r = n − k для ЦК могут определяться путем суммирования по модулю 2 ряда определенных
информационных символов кодовой комбинации Ai (Х). Например,
для кодов Хемминга (7, 4) с порождающим полиномом G(X) = X 3
+ Х + 1 и дуальным G(X) = X 3 + X 2 + 1 алгоритм получения проверочных символов будет (см. формулу 3.7)
для G (Х) = Х 3 + Х + 1
для G(Х) = Х 3 + Х 2 + 1
r1 = i1 ⊕ i2 ⊕ i3,
r1 = i1 ⊕ i3 ⊕ i4,
r2 = i2 ⊕ i3 ⊕ i4,
r2 = i1 ⊕ i2 ⊕ i3,
r3 = i1 ⊕ i2 ⊕ i4,
r3 = i2 ⊕ i3 ⊕ i4.
(4.7)
Эта процедура свидетельствует о возможности «поэлементного»
получения проверочной группы для каждой кодовой комбинации
Ai (Х). В соответствии с (4.7) могут строиться кодирующие устройства для ЦК.
5. Как было показано ранее, умножение полинома на X приводит к сдвигу членов полинома на один разряд влево, а при умножении на X r, соответственно, на r разрядов влево, с заменой r
младших разрядов полинома «нулями». Умножение полинома на
X свидетельствует о том, что при этой процедуре X является «оператором сдвига». Деление полинома на X приводит к соответствующему сдвигу членов полинома вправо с уменьшением показателей членов на 1. Процедура сдвига позволяет к исходной кодовой
комбинации Ai (Х) после домножения ее на X r дописать справа r
проверочных символов.
48
6. Поскольку разрешенные кодовые слова циклического кода
Bi(X) без остатка делятся на порождающий полином G(X) с получением итога в виде информационной комбинации Ai(Х) (4.1), то
имеется возможность формировать Вi (Х) на стороне передачи (кодирующее устройство) простым методом умножения (4.2).
Два последних свойства позволяют осуществить построение кодеров ЦК двумя методами: методом умножения и методом деления
полиномов. Рассмотрим достоинства и недостатки этих методов
с учетом вариантов построения декодеров ЦК, соответствующих
этим методам.
Метод умножения позволяет при формировании разрешенных
кодовых комбинаций по алгоритму (4.2) использовать любой порождающий полином, лишь бы его максимальная степень была
равна числу необходимых проверочных символов r. Однако этот
метод обладает двумя существенными недостатками.
1. При формировании ЦК методом умножения в полученной
комбинации Вi (Х) в явном виде не содержатся информационные
символы. Код получается неразделимым с «перетасованными» информативными и проверочными символами, что затрудняет его
декодирование, так как это приводит к необходимости применять
метод максимального правдоподобия в декодирующем устройстве
(ДУ).
2. Метод максимального правдоподобия (ММП) предполагает при исправлении ошибок принимаемую кодовую комбинацию
отождествлять с той разрешенной, к которой принятая комбинация находится ближе всего. При таком непосредственном способе
декодирования в памяти запоминающего устройства (ЗУ) декодера
необходимо хранить все разрешенные кодовые комбинации N0, что
требует на стороне приема больших объемов ЗУ и большого времени обработки при декодировании. Эти обстоятельства являются
вторым недостатком метода умножения при кодировании ЦК.
В соответствии с этим, основным направлением в теории кодирования является поиск таких кодов и алгоритмов их формирования
и обработки, для которых не требуется хранение в запоминающем
устройстве (ЗУ) разрешенных кодовых комбинаций. Эти задачи
решаются, в частности, при построении кодеров на основе деления
полиномов, а при декодировании — на основе синдромного метода
декодирования (СМД).
Метод деления полиномов позволяет представить разрешенные
к передаче кодовые комбинации в виде разделенных символов: информационных Ai (Х) и проверочных Ri (X), т. е. получить блочный
код. Поскольку число проверочных символов равно r, то для ком49
пактной их записи в последние младшие разряды кодового слова
надо предварительно к Ai (Х) справа приписать r «нулей», что эквивалентно умножению Ai (Х) на оператор сдвига X r (см. п. 5 ЦК).
На практике предпочитают использование метода деления полиномов при построении кодеков, поскольку при этом имеется возможность представить кодовую комбинацию в виде разделенных
информационных и проверочных символов
Bi (X) = Ai (X) · X r + Ri (X),
(4.8)
r
где Ri (X) − остаток от деления Ai (X) · X /G(X).
В алгоритме (4.8) можно выделить три этапа формирования разрешенных кодовых комбинаций в кодирующем устройстве:
1) к комбинации первичного кода Ai (X) дописывается справа r
нулей, а степени Х, входящие в Ai (X), увеличиваются на r, что эквивалентно умножению Ai (X) на X r;
2) произведение Ai (X) · X r (без учета дописываемых справа r нулей) делится на соответствующий порождающий полином G(X) и
определяется остаток Ri (X), степень которого не превышает r − 1,
этот остаток и дает группу проверочных символов;
3) вычисленный остаток присоединяется справа (на место нулей)
к Ai (X) · X r, что и дает исходную комбинацию ЦК.
Пример: рассмотрим процедуру кодирования по алгоритму
(4.8): для кодовой комбинации A = 1001 сформировать кодовую
комбинацию циклического кода (7, 4). В заданном ЦК n = 7, k = 4,
r = 3, из табл. 4. 1 выберем порождающий полином G(X) = X 3 + X–1
(код Хемминга). Выполним три необходимые операции для получения кодовой комбинации ЦК, согласно алгоритму (4.8)
Ai (X) = 1001 ~ X 3 + 1, ( знак « ~ » – тильда означает соответствие).
1. Ai (X) · X r = (X 3 + 1 ) · X 3 = X 6 + X 3 ~ 1001000, ( n = 7).
2. Ai (X) • Xr / G(X) = X6 + X3  
X3 + X + 1
+
 
——————
X6 + X4 + X3
X3 + X
——————
X4
+
X4 + X2 + X
——————
X2 + X –
остаток Ri (X) = X2 +
+ X ~ 110.
r
3. Bi (X) = Ai (X) · X + Ri (X) = 1001110 – итоговая комбинация
ЦК.
50
Синдромный метод декодирования (СМД) предполагает в декодирующем устройстве (ДУ) принятую кодовую комбинацию поделить на порождающий полином. Если принятая комбинация является разрешенной, т. е. не искажена помехами в канале связи, то
остаток от деления будет нулевым. Ненулевой остаток свидетельствует о наличии в принятой кодовой комбинации ошибок, остаток
от деления и является синдромом (см. подразд.3.3).
Для исправления ошибки на стороне приема необходимо знать
не только факт ее существования, но и ее местонахождение, которое определяется по установленному виду вектора ошибки (шумового вектора) z(X).
После передачи по каналу с помехами принимается кодовое слово
B′i (X) = Bi (X) + z(X), (4.9)
где Bi (X) – передаваемая кодовая комбинация; z(X) – полином
(вектор) ошибки, имеющий степень от 1 до n – 1.
При декодировании принятое кодовое слово делится на G(X):
B′i
= Ui (X) + Si (X), G(X)
(4.10)
где остаток от деления Si (X) и является синдромом.
Как отмечалось выше, если при делении получается нулевой остаток Si (X) = 0, то выносится решение об отсутствии ошибки z(X) =
= 0. Если остаток (синдром) ненулевой Si (X) ≠ 0, то выносится решение о наличии ошибки и определяется шумовой вектор (полином) z(X), а затем передаваемое кодовое слово, поскольку из (4.9)
следует
Bi (X) = B′i (X) + z(X). (4.11)
Всякому ненулевому синдрому соответствует определенное расположение (конфигурация) ошибок. Взаимосвязь между видом
синдрома и местоположением ошибочного символа находится довольно просто. Достаточно в любую разрешенную кодовую комбинацию ввести ошибку и выполнить деление на G(X). Полученный
остаток (4.11) – синдром и будет указывать на ошибку в этом символе.
Наряду с полиномиальным способом задания кода, структуру
построения кода можно определить с помощью матричного представления. При этом в ряде случаев проще реализуется построение
кодирующих и декодирующих устройств ЦК. Поскольку ЦК по51
рождаются делителями бинома X n + 1 (4.3), то для большей части
значений n и k имеется относительно мало кодов, удовлетворяющих
всем свойствам, присущим ЦК. Поэтому естественно попытаться
найти среди линейных кодов такие, которые хотя и не являются в
действительности циклическими, обладают похожей математической структурой и столь же легко реализуются.
При этом n и k часто не совпадают с табулированными в технических изданиях ЦК. В этом случае по таблицам находят ЦК, который соответствует обоснованному значению r = n – k для классического, табулированного ЦК, а затем уменьшают n и kΣ до n – ℓ и kΣ =
k – ℓ, получая укороченный (усеченный) ЦК.
Укороченные циклические коды (УЦК) получают из полных
ЦК, используя для передачи информации только кодовые комбинации полного кода, содержащие слева ℓ нулей. Это дает возможность
построить УЦК (n – ℓ, k – ℓ) путем исключения первых ℓ столбцов и
ℓ строк из порождающей матрицы. Полученный код не будет строго
циклическим, так как циклический сдвиг не всегда будет приводить к получению очередной разрешенной кодовой комбинации.
Поэтому укороченные (усеченные) ЦК часто называют псевдоциклическими или квазициклическими. Укороченные ЦК сохраняют
основные свойства классических ЦК.
К циклическим кодам относятся также коды Боуза–Чоудхури–
Хоквингема (БЧХ). Они представляют собой обширный класс кодов, способных исправлять несколько ошибок, и занимают заметное место в теории и практике кодирования. Интерес к кодам БЧХ
определяется, по меньшей мере, тремя следующими обстоятельствами:
1) среди кодов БЧХ при небольших длинах существуют хорошие
коды, но, как правило, не лучшие из известных;
2) известны относительно простые и конструктивные методы их
кодирования и декодирования;
3) полное понимание построения кодов БЧХ является наилучшей отправной точкой для изучения многих других классов кодов.
Коды БЧХ открыли Хоквингем (1959) и Боуз, и Рой–Чоудхури
(1960), которые доказали ряд теорем, устанавливающих существование таких ЦК, у которых минимизируется число проверочных
символов, а также указывающих пути нахождения порождающих
полиномов для этих кодов.
Важным и широко используемым подмножеством кодов БЧХ
являются коды Рида–Соломона. Двоичный код Рида–Соломона
(РС) получится, если взять основание кода q = 2S. Это означает, что
каждый символ кода заменяется s -значной двоичной последова52
тельностью. Коды PC, наряду с кодами Файра, являются наиболее
подходящими для исправления серийных ошибок.
Построение кодеров и декодеров циклических кодов основывается на применении линейных переключательных схем, содержащих сдвигающие регистры и сумматоры по модулю 2.
4.4. Плотноупакованный код Голея
Как отмечалось ранее, число проверочных символов r = n – k
определяет число исправляемых ошибок. Значение r должно быть
достаточным для получения необходимого числа синдромов SΣ
(опознавателей ошибок). Для исправления всех одиночных (однократных) ошибок необходимо определить вид шумового вектора,
который может принимать следующие n значений:
000...01, 000...10,..., 001...00, 010...00, 100...00.
Кроме того, необходим один синдром для определения факта
безошибочного приема кодовой комбинации S0 = 000...00. Таким
образом, для двоичных кодов при необходимости исправления всех
однократных ошибок требуется выполнение соотношения
SΣ = 2n – k = 2r = n + 1,
(4.12)
поскольку количество синдромов определяется числом r проверочных разрядов.
Плотноупакованные коды – такое название получили коды, у
которых соблюдается точное равенство (4.12) числа необходимых
синдромов для исправления ошибок заданной кратности. Вследствие уникальности таких кодов плотноупакованные коды называют также «совершенными» или «оптимальными». К таким кодам,
как отмечалось ранее, относятся коды Хемминга, которые при минимальном кодовом расстоянии dmin = 3 обеспечивают исправление
всех однократных ошибок, поскольку у классических кодов Хемминга число символов n = 2r – 1 удовлетворяет условию (4.12).
В общем случае при необходимости исправления всех независимых ошибок кратности до g включительно требуемое число синдромов определяется выражением
SΣ = 1 + Cn1 + Cn2 + Cn3 + ... + Cng =
где Cni =
∑ Cng , (4.13)
n!
– число сочетаний из n по i, причем Cn0 = 1 , так как
(n − i)!⋅ i !
0! = 1.
53
С учетом (4.12) и (4.13), можно получить выражение для оценки
числа проверочных символов r при необходимости исправления gи
-кратных ошибок в принятых кодовых комбинациях
r ≥ log 2
∑ Cni . (4.14)
Занимаясь поиском плотноупакованных кодов («кодов без потерь»), М. Голей заметил (опубликовано в 1949 г.), что
0
1
2
3
C23
+ C23
+ C23
+ C23
= 1 + 23 + 253 + 1771 = 211,
а это означало, что может существовать плотноупакованный двоичный (23, 12) код, удовлетворяющий условию (4.13), исправляющий
все кодовые комбинации с тремя или менее ошибками. В дальнейшем этот код получил его имя.
Код Голея относится к классу ЦК с порождающими двойственными (дуальными) полиномами:
G(Х) = Х 11 + Х 10 + Х 6 + Х 5 + Х 4 + Х 2 + 1;
 ̃(X) = Х 11 + X 9 + X 7 + Х 6 + Х 5 + X + 1.
G
Д
Простым вычислением проверяется, что
 (X) ,
Х 23 + 1 = (Х + 1) ⋅ G(X) G
(4.15)
Д
в соответствии с чем в качестве порождающего полинома ЦК Голея
 (X) .
(23, 12) можно использовать как G(X), так и G
д
Код Голея, гарантированно исправляющий ошибки с кратностью не менее трех включительно, обладает минимальным кодовым
расстоянием dmin = 2g + 1 = 7, что, как правило, указывается в маркировке кода (23, 12, 7). Добавление к этому коду общей проверки
на четность по всем позициям увеличивает как общую длину кода,
так и минимальное кодовое расстояние – на единицу (dmin = 8).
Расширенный код Голея, имеющий маркировку (24, 12, 8), состоит из 12 информационных символов и 12 проверочных, т. е.
представляет собой код, обладающий скоростью 1/2 и избыточностью, также равной 1/2.
Обратим внимание на то, что плотноупакованные коды Хемминга и Голея – циклические, которые принадлежат классу двоичных линейных кодов. Общим для линейных двоичных кодов является наличие, в качестве разрешенного, нулевого кодового слова
000…00; это приводит к тому, что минимальный вес Wmin ненулевого разрешенного кодового слова равен минимальному кодовому
расстоянию dmin.
54
В общем случае вес кодовых комбинаций может принимать
различные значения, и совокупность чисел кодовых комбинаций
с постоянным весом NW определяют как распределение весов кода
или как спектр весов кода. Распределение весов в коде Голея (23,
12, 7) следующее:
N0 = N23 = 1; N7 = N16 = 253; N8 = N15 = 506;
N11 = N12 = 1288.
(4.16)
К сожалению, кроме кодов Хемминга (dmin = 3, gи = 1) и кода
Голея (23, 12, 7) пока не найдено других совершенных, плотноупакованных кодов, число синдромов у которых точно соответствует
требуемому значению для гарантированного исправления ошибок
заданной кратности.
4.5. Процедуры кодирования и декодирования
циклических кодов
(практическое задание)
Сформировать информационную кодовую комбинацию по следующему правилу.
1. Записать свою собственную фамилию и первые 4 буквы трансформировать в двоичный код, заменив согласные буквы на 1, а гласные – на 0. Например, следующие фамилии будут представлены в
виде: Зубков – 1011, Грызлов – 1101, Иванов – 0101, Ким – 1010.
2. Принять полученную кодовую группу за информационную
кодовую комбинацию A(Х) циклического кода Хемминга (7, 4).
Для полученного кода A(Х), в котором n = 7, k = 4, r = 3, из выражения 4.7 поэлементно найти 3 символа проверочных групп для двух
порождающих полиномов кода Хемминга и справа добавить их к
A(Х), получая полные кодовые комбинации ЦК – B(Х). Например,
кодовая комбинация 0101 для первого порождающего полинома
будет иметь вид B(Х) = 0101100.
3. В полученной, предназначенной для передачи кодовой комбинации B(Х), изменить последовательно все 7 символов на противоположные (1 на 0, 0 на 1). Это предполагает возникновение однократной ошибки последовательно в каждом символе в канале связи
(в соответствии с выражением 4.9). На приемной стороне получаем
код B’(Х). Например, при ошибке во втором символе комбинация
п. 2 будет иметь вид B’(Х) = 0001100.
4. Выполнить три необходимые операции, проводимые при декодировании:
55
а) в соответствии с алгоритмом (4.10) произвести деление для определения конфигурации синдрома:
B’(Х) / G (X) → 0001100 = Х 3 + Х 2 │ Х3 + Х + 1
–
¯¯¯¯¯1¯¯¯¯¯
Х 3+ Х + 1
¯¯¯¯¯¯¯¯¯¯
Х 2 + Х + 1 → остаток S(Х) =
= 111,
остаток 111 и является синдромом при втором искаженном символе;
б) полученный синдром будет определять вид шумового вектора
z(X) = 0100000;
в) по алгоритму (4.11) исправляется принятая кодовая комбинация.
Результаты расчетов синдромов для двух порождающих полиномов циклического кода Хемминга и определения вида шумовых
векторов заносятся в табл. 4.2. Пользуясь этой таблицей, можно
найти местоположение ошибки и исправить ее.
5. Построить график распределения весов (спектр) W = f (Ni)
кода Голея (4.16) и самостоятельно дополнить этот график спектром расширенного кода Голея с представлением его как код с КПЧ.
Записать, как будет выглядеть маркировка этого кода (n, k, d) и
определить избыточность и относительную скорость расширенного
кода Голея.
Таблица 4.2. Расчет синдромов и шумовых векторов
Символ
комбинации
со старшего
разряда
Ошибочный
символ
полинома
комбинации
Синдром для
порождающего
полинома
G(X) = X 3 + X + 1
Синдром для
порождающего
полинома
G(X) = X 3 + X 2 + 1
Шумовой
вектор
z(X)
i1
i2
i3
i4
r1
r2
r3
X6
X5
X4
X3
X2
X1
X0
Нет ошибки
000
000
0000000
Пользуясь табл. 4.2, найти местоположение ошибки и исправить
ее. Результаты расчета после выполнения сдаются преподавателю.
56
5. СВЕРТОЧНЫЕ КОРРЕКТИРУЮЩИЕ КОДЫ
5.1. Рекуррентный код Финка
Первый непрерывный рекуррентный код был предложен в
1955 г. нашим соотечественником Л. М. Финком, который долгие годы заведовал кафедрой в Ленинградской военной академии
связи, а затем работал в электротехническом институте связи им.
М. А. Бонч-Бруевича. Однако западные специалисты имели слабое
представление о работах наших отечественных ученых в области
кодирования, и поэтому лишь спустя четыре года (1959 г.) вновь
открытый рекуррентный код был назван по фамилии его западного
автора – кодом Хагельбергера. В дальнейшем эти коды получили
название – сверточные.
Рассмотрим идею построения рекуррентного кода Финка в изложении самого Финка, скромно умолчавшего в своей монографии «Теория передачи дискретных сообщений» о своем авторстве.
В этом коде последовательность кодовых символов не разделяется на отдельные кодовые комбинации. В поток информационных
символов включаются корректирующие символы так, что между
каждыми двумя информационными символами помещается один
корректирующий. Обозначая информационные символы через ai, а
корректирующие через bi, получаем последовательность символов
a1b1 a2b2 a3b3, …, akbk ak+1bk +1.
(5.1)
Информационные символы определяются передаваемым сообщением, а корректирующие формируются по следующему принципу:
bi = ak– S + ak + S + 1 (mod 2),
(5.2)
где s – произвольное целое число, называемое шагом кода (s = 0, 1,
2, …).
Очевидно, что при ошибочном приеме корректирующего символа bi в принятой последовательности соотношение (5.2) не будет
выполняться для i = k. В случае же ошибочного приема информационного символа аi соотношение (5.2) не будет выполняться при
двух значениях k, а именно при k1 = i – s – 1 и при k2 = i + s. Отсюда
легко ввести правило исправления ошибок при декодировании. В
принятой кодовой последовательности для каждого bk проверяется
соотношение (5.2). Если оно оказалось не выполненным при двух
значениях k (k = k1 и k = k2) и при этом
k2 – k1 = 2s + 1,
(5.3)
57
то информационный элемент ak1+S +1 должен быть заменен на противоположный.
Избыточность такого кода равна 1/2, он позволяет исправлять
все ошибочно принятые символы, кроме некоторых неудачных сочетаний. Так, он обеспечивает правильное декодирование при s = 0,
когда между двумя ошибочными символами имеется не менее трех
(а в некоторых случаях двух) правильно принятых символов (при
этом учитываются как информационные, так и корректирующие
символы).
Для наглядности в табл. 5.1 графически показаны процессы формирования (кодирования) кодов Финка при шаге s = 0 для исходной
информативной последовательности из 10 символов 0001101011.
Как следует из выражения (5.2), последовательность проверочных символов при s ≠ 0 будет различной и определяется значением
шага s. В табл. 5.1 также представлены варианты декодирования
принятых последовательностей с искаженными за счет помех различными символами. Искаженные символы и результаты их декодирования отображены в таблице жирным шрифтом. Полученные
проверочные символы встраиваются между соседними информационными символами, образуя соответствующую входную последовательность, подлежащую передаче по каналу связи.
На стороне приема осуществляется та же самая процедура получения проверочных символов, что и на стороне передачи (5.2),
и производится сравнение их с принятыми проверочными символами. Если при приеме ошибок нет, то результат суммирования по
модулю 2 будет состоять из последовательности, содержащей одни
нули. Эта последовательность так же, как и в блочных циклических кодах, называется синдромом. Синдромом полностью определяется комбинация ошибок в принятой кодовой комбинации.
Как видно из табл. 5.1, при шаге s = 0 ошибка при приеме одного 5-го информационного символа приводит при декодировании к
ошибке двух проверочных символов – 4-го и 5-го, что позволяет исправить находящийся между ними 5-й информационный символ.
Декодирование при ошибке в одном проверочном символе при
разных значениях шага s вызывает в результате суммирования различие только в одном символе, что не влияет на правильный прием
информационной группы.
Декодирование при ошибке в двух информационных символах
показывает, что для верного декодирования ошибочные символы
должны быть разнесены, чтобы не участвовать в формировании
одинаковых проверочных символов.
58
59
0
0
a1 b1
1
0
0
0
0
0
0
a2b 2
2
0
0
1
1
a3b3
3
1
1
0
0
a4b4
4
1
1
1
1
a5b5
5
0
0
0
0
1
1
0
0
1
0
1
1
1
1
0
0
0
0
1
1
Декодированная
1
1
0
0
0
0
последовательность
Декодирование при ошибке в одном проверочном символе
0
0 0 0 0 0 1 1
1 0 0
Принятая последовательность,
суммирование по mod 2,
результат суммирования
1
0
0
0
1
Декодированная
0
0
1
1
0
0
последовательность
Декодирование при ошибке в двух проверочных символах
0 0 0
0 0 1 0
0
1 1 1
Принятая последовательность,
суммирование по mod 2,
результат суммирования
1
0
0
0
0
Декодированная
0
0
1
1
0
0
последовательность
lc = 3
0
1
0
0
Принятая последовательность,
суммирование по mod 2,
результат суммирования
1
1
a6b6
6
Декодирование при ошибке в одном информационном символе
Выходная последовательность
Информационные символы,
суммирование по mod 2,
проверочные символы
Маркировка символов,
текущее значение i
Процесс формирования кода при шаге s = 0
Таблица 5.1. Коды Финка для последовательности из 10 символов
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
a7b 7
7
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
a8b8
8
1
1
1
1
1
1
1
1
0
0
0
0
0
0
0
0
a9b9
9
1
1
1
1
1
1
1
1
a10b 10
10
Это условие «стыковки» требует наличия трех (ℓс = 3), верно
принятых символов между двумя искаженными информативными
символами. Этот интервал ℓс называют – расстоянием стыковки.
Однако в ряде случаев верно принятый информационный символ, расположенный между исправляемыми двумя ошибочно
принятыми, сам в декодере заменяется на противоположный.
Это приводит к тому, что стыковочное расстояние ℓс = 3 требуется увеличить при s = 0, по крайней мере, на два дополнительных
символа – ℓд = 2. Таким образом, для однозначного декодирования
информационных символов требуется между двумя ошибочно принимаемыми символами иметь защитный интервал
ℓ0 = ℓс + ℓд
(5.4)
из верно принимаемых символов с учетом проверочных.
Для кода Финка с шагом s = 0 значение ℓ0 = 5. Увеличение шага
(s > 0) приводит к возможности исправления не только одиночных
символов в принимаемой комбинации, но и групп подряд следующих символов. При s = 0 код Финка не способен исправлять даже
два подряд следующих ошибочных символа, а при шаге s = 1 появляется возможность исправления групп из трех соседних символов.
Подобные «серийные» ошибки возникают в результате воздействия в каналах передачи помех импульсного характера, длительность которых больше одного символа. Такая же ситуация
возникает и в каналах с кратковременными замираниями сигнала
(мультипликативная помеха), в частности, в системах подвижной
связи. При этих условиях ошибки уже не независимы, а возникают
«пачками», общая длительность которых соответствует длительности помехи. Но при шаге s = 0 в коде Финка исправляемая пачка
ошибок вырождается в один символ. Именно с целью возможности
исправления пачек ошибок в коде Финка применяется отличный
от нуля шаг s. При достаточно большом значении s символы, входящие в одну и ту же проверку на четность (5.2), будут разнесены
по времени настолько, что состояние канала за это время успеет измениться. При этом пакет ошибок будет, как правило, захватывать
только символы, не связанные друг с другом выражением (5.2).
Так для шага s = 1 в пачке ошибок из трех символов стыковочное
расстояние ℓс = 7, а число необходимых дополнительных правильно принимаемых символов для однозначного декодирования ℓд = 6.
Это приводит к тому, что правильное декодирование очередного
(даже одиночного) символа или очередной пачки ошибок из трех
информативных символов возможно при результирующем защит60
ном интервале ℓ0 = ℓс + ℓд = 7 + 6 = 13 с неискаженными помехами
символами. Таким образом, с увеличением значения шага увеличивается не только длина исправляемой пачки, но и длина защитного интервала.
Сверточный кодер представляет собой устройство, воспринимающее за каждый такт работы в общем случае k входных информационных символов, и выдающее на выход n выходных символов,
подлежащих передаче по каналу связи. Отношение R = k/n называется относительной скоростью кода.
Основными элементами сверточного кодера являются: регистр
сдвига, сумматоры по модулю 2 и коммутатор. Тактовая частота
переключения и число контактов коммутатора в сверточных кодерах определяется относительной скоростью кода. В соответствии с
этим число контактов коммутатора должно быть равно n, а частота
переключения должна быть в n раз больше входной тактовой частоты. Так, при скорости R = 1/2 у коммутатора должно быть два
контакта и переключение должно производиться с удвоенной тактовой частотой.
В качестве примера на рис. 5.1 приведены кодеры кода Финка с
различными шагами s, работающие со скоростью R = 1/2.
В общем случае в применяемых кодерах современных сверточных кодов сдвигающий регистр (рис. 5.2) содержит m ячеек, а комВыход
s=0
s=1
+
s=2
Выход
+
Выход
+
Рис. 5.1. Кодеры для кода Финка.
Информационные
символы
0
1
2
+
+
...
...
m–2
+
m–1
+
В канал
Рис. 5.2. Общий вид двоичного сверточного кодера.
61
мутатор делает один цикл опроса при приходе 1 ≤ k < m очередных
информационных символов, где m кратно k, опрашивая за один
цикл n ≥ 2 выходов кодера.
Одним из параметров кодеров является длина кодового ограничения (ДКО) или кодовая длина блока, которая представляется
числом кодовых символов, порождаемых кодером в промежутках
времени между поступлением в него данного информационного
символа и выходом в канал соответствующего символа, в формировании которого входной символ принимает участие.
Для того чтобы задать структуру сверточного кодера, необходимо указать, какие разряды регистра сдвига связаны с каждым из
сумматоров по модулю 2; ДКО и конкретный выбор связей с ячейками сдвигающего регистра на сумматоры по модулю 2 будут определять корректирующие свойства получаемого сверточного кода.
Значение ДКО показывает, на какое максимальное число выходных символов влияет данный информационный символ, и играет
ту же роль, что и длина блочного кода. Сверточный код задается
порождающими полиномами или матрицами подобно тому, как это
делается для блоковых циклических кодов. Порождающие многочлены полностью определяют структуру двоичного кодера сверточного кода. Выходные кодовые символы можно представить в виде
свертки последовательности информационных символов и порождающих многочленов кода, задающих рекуррентные правила кодирования. Однако в отличие от блоковых кодов, каждый из которых
описывается единственным порождающим многочленом, сверточный код требует для своего описания нескольких порождающих
полиномов, число которых определяется числом n выходных символов, передаваемых за каждый такт в канал связи. Практически
все параметры блочных кодов, в частности, минимальное кодовое
расстояние сохраняются и для сверточных кодов.
При передаче информации с корректирующим кодированием
уже вместо k информативных символов за данное время требуется передача n символов с добавлением проверочных за то же время при том же уровне сигналов. При этом приходится сокращать
длительность символов при передаче (при скорости R = 1/3 − в три
раза), что потребует расширения полосы частот в n/k раз. Исходное
заданное значение вероятности правильного приема будет обеспечиваться уже при другом отношении сигнал/шум. Разница отношения сигнал/шум при применении кодирования и без него, при
ее положительном значении определяет энергетический выигрыш
кода, выражаемый в децибелах. Выигрыш от кодирования может
быть использован наиболее эффективным способом, например, пу62
тем уменьшения мощности передатчиков в системах связи, уменьшения размеров антенн или увеличения скорости передачи.
Сложность построения декодеров СК определяется методом декодирования. В настоящее время используется три основных метода декодирования СК: пороговое, аналогичное мажоритарному
методу декодирования блочных кодов, последовательное и декодирование по алгоритму Витерби. Сложность реализации декодеров
растет практически пропорционально полной длине кодового ограничения. Так, при использовании алгоритма Витерби увеличение
ДКО на единицу более чем вдвое увеличивает объем декодера. Поэтому практически используемые декодеры выполняются для кодов
с ДКО до 7÷ 8.
К настоящему времени найдено большое число сверточных кодов
с самыми различными параметрами для борьбы с различного рода
помехами. Подробно со схемным построением декодеров СК можно
познакомиться в специальной технической литературе. Обратим
внимание на то, что для верного декодирования принимаемой кодовой последовательности на стороне приема должна быть обеспечена
жесткая синхронизация по тактовым импульсам, определяющим
порядок следования информативных и проверочных символов. В
противном случае, при сбое синхронизации, верное декодирование
становится невозможным, поскольку принимаемые информационные символы могут быть восприняты как проверочные и наоборот.
При рассмотрении вопросов, связанных с любым декодированием,
всегда априорно предполагается наличие правильной синхронизации как по тактовым, так и по цикловым (при блочном кодировании) импульсам.
5.2. Формирование кода Финка–Хагельбергера
(практическое задание)
Выполнить практическое задание по следующим пунктам.
1. Слитно (без пробела) записать свою фамилию, имя и отчество.
Заменить согласные буквы на 1, а гласные на 0. Первые 12 символов принять за информативную кодовую комбинацию.
2. Записать в строки информативные символы, суммирование
по модулю 2 и выходную последовательность (по аналогии с табл.
5.1) при шаге в коде Финка s = 1.
3. Ввести однократную ошибку в один из информационных символов (отметить его) принятой последовательности и декодировать
ее.
63
4. Ввести однократную ошибку в один из проверочных символов
и декодировать принимаемую последовательность.
5. В принятой последовательности изменить на противоположные два соседних символа и выполнить декодирование.
6. В принятой последовательности изменить два соседних информационных символа и провести декодирование. Все пп. 2−6 выполнять по аналогии с данными табл. 5.1.
При выполнении заданий по пунктам оценивать стыковочное
и дополнительное расстояния и защитный интервал. Результаты
расчетов сдать преподавателю.
64
6. КОДИРОВАНИЕ С ПЕРЕМЕЖЕНИЕМ
6.1. Назначение процедуры перемежения
Процедура перемежения сама по себе не добавляет проверочных символов и избыточность ее равна нулю. Однако перемежение
предполагает перестановку информативных символов, способствующую исправлению пачек ошибок помехозащищенными кодами.
По определению Малой советской энциклопедии код (от лат. –
codex) – система условных обозначений или сигналов, что и можно
отнести к процедуре перемежения. При этом операцию перевода
сообщений в определенные последовательности сигналов называют кодированием, а обратную операцию, восстанавливающую по
принятым сигналам (кодовым словам) передаваемые сообщения,
декодированием.
Перемежение представляет собой такое изменение порядка
следования символов информационной последовательности, т. е.
такую перестановку символов, при которой стоящие рядом символы оказываются разделенными несколькими другими символами.
Такая процедура предпринимается с целью преобразования групповых ошибок (пакетов ошибок) в одиночные ошибки, с которыми
легче бороться с помощью блочного и сверточного кодирования.
Процедура перемежения реализуется блоком перемежителя, который по-английски называется интерливером (interleave – 1) прокладывать белую бумагу между листами книги; 2) прослаивать).
Использование перемежения – одна из характерных особенностей
сотовой связи, и это является следствием неизбежных глубоких замираний сигнала в условиях многолучевого распространения, которое практически всегда имеет место, особенно в местах плотной
городской застройки. При этом группа следующих один за другим
символов, попадающих на интервал замирания (провала) сигнала,
с большой вероятностью оказывается ошибочной. Если же перед
выдачей информационной последовательности в радиоканал она
подвергается процедуре перемежения, а на приемной стороне восстанавливается прежний порядок следования символов, то пакеты
ошибок с большой вероятностью рассыпаются на одиночные ошибки. Известно несколько различных схем перемежения и их модификаций – диагональная, блочная, сверточная и др. Рассмотрим
вкратце первые две из них, лежащие в основе схем, применяемых
в сотовой связи.
65
6.2. Диагональное перемежение
При диагональном перемежении входная информация делится
на блоки, а блоки – на субблоки. В выходной последовательности
субблоки, например, второй половины предыдущего блока чередуются с субблоками второй половины следующего блока. Такая схема
приведена на рис. 6.1, где каждый блок состоит из шести субблоков,
и субблоки первого блока обозначены а, второго – b, третьего – c.
Блок 1
a3
a2
a 5 a4
a1 ...
Блок 2
b6
b5
b4
b3
b2
b1
Блок 3
... c6
c4
c3
c2
c1
c5
… b6 c3 b5 c2 b 4 c1a6 b3 a5 b 2 a4 b1 …
Выход
a6
Вход
Рис. 6.1. Пример схемы диагонального перемежения
Субблок может состоять из нескольких символов или из одного символа. Приведенная схема диагонального перемежения вносит малую задержку, но расставляет соседние символы лишь через
один, т. е. рассредоточение ошибочных символов группы получается сравнительно небольшим.
6.3. Блочное перемежение
При блочном перемежении входная информация также делится
на блоки, по n субблоков (или символов) в каждом, и в выходной
последовательности чередуются субблоки k последовательных блоков. Работу этой схемы можно представить в виде записи блоков
входной последовательности в качестве строк матрицы размерности k × n (рис. 6.2), считывание информации из которой производится по столбцам.
Следовательно, если входная последовательность в этом примере имеет вид a1, a2, …, an, b1, b2, …,
Вход
a 1 a2 a3 . . . a n
bn, …, k1, k2, …, kn, то выходная будет
b1 b 2 b3 . . . bn
a1,b1, …, k1, a2,b2, …, k2, …, an, bn, …,
. .
kn. Субблоки или символы здесь так. .
. .
же могут состоять лишь из одного
бита. Схема блочного перемежения
k1 k2 k3 . . . kn
вносит большую задержку, чем диа...
гонального, но значительно сильнее
Выход
Рис.6.2. Схема блочного пере- рассредоточивает символы группы
ошибок.
межения
66
7. МОДУЛЯЦИОННЫЕ КОДЫ
7.1. Двоичный код Грея
В ряде случаев, в частности, в системах беспроводной мобильной телефонии с целью эффективного энергосбережения, продлевающего срок автономной (без подзарядки или смены батареи) работы портативного терминала и способствующего коммерческой привлекательности его массогабаритных характеристик, применяют
многократную фазовую модуляцию радиосигналов. Во многих телекоммуникационных сетях, таких как кабельная, сотовая, радиорелейная связь и т. д., применяется амплитудно-фазовая и квадратурная амплитудная модуляция с числом фазовых векторов до 16.
Восьмипозиционная фазовая модуляция избрана как инструмент
увеличения скорости передачи в сотовой системе второго поколения EDGE. В подобных многопозиционных системах с фазовой модуляцией применяется в качестве модуляционного кода – код Грея,
способствующий повышению помехозащищенности систем связи.
В кодоимпульсных телеизмерительных устройствах, в которых
используется преобразование угла поворота в код, например, угла
поворота антенны радиолокационных станций, в качестве модуляционного кода применяется также код Грея, рассмотренный в
подразд. 1.5. Код Грея часто называют циклическим или рефлексно-двоичным. Отличительной особенностью этого кода является
то, что соседние кодовые комбинации, расположенные в порядке
возрастания номеров, отличаются лишь в одном разряде. В простом двоичном коде это правило не соблюдается: например, при переходе от комбинации № 3 к № 4 единицы меняются во всех трех
разрядах, от № 7 к № 8 – во всех четырех и т. д. Двоичный код Грея
(первые 16 комбинаций) ранее приведен на рис.1.3.
Комбинации этого кода образуются из соответствующей комбинации простого двоичного кода путем суммирования по модулю 2
с этой же комбинацией, но сдвинутой на один разряд вправо. При
этом младший разряд кода отбрасывается.
Преимущество применения кода Грея в качестве модуляционного кода состоит в том, что при преобразовании аналоговой величины (угла поворота, механического перемещения и т. п.) в код, например, с помощью кодовой маски, погрешность преобразования
не превышает погрешности дискретности, т. е. единицы младшего
разряда. Это происходит потому, что при переходе от одного уровня
дискретности к другому меняется единица только в одном разряде.
Кодирующую маску выполняют в виде прямоугольной пластины
67
или диска, насаживаемого на ось вращения. В последнем случае
знаки разрядов наносят на концентрические дорожки, каждая из
которых соответствует определенному разряду двоичного числа.
Внешняя дорожка диска соответствует младшему разряду (рис.
7.1). Каждому дискретному значению угла ставится в соответствие
вполне определенная неповторяющаяся комбинация сегментов
двух типов, соответствующих 1 и 0. На рис. 7.1 кодирующая маска
на диске – для двоичного кода. Аналогично наносится маска для
кода Грея.
В зависимости от способов съема (контактный, фотоэлектрический, магнитный и т. д.) сегменты рисунка кода выполняются
проводящими и непроводящими, прозрачными и непрозрачными, магнитопроницаемыми и магнитонепроницаемыми и т. д.
Для считывания с каждого из разрядов устанавливаются чувствительные элементы: щетки, фотоэлементы, индуктивные катушки
и т. д.
К сожалению, при использовании масок с обычным двоичным
кодом (рис. 7.1) в местах, где одновременно изменяется состояние нескольких чувствительных элементов, могут возникать значительные погрешности при считывании. Например, если чувствительные элементы располагаются на границе между числом 7
(0111) и 8 (1000), преобразователь может выдать на выходе любое
число от 0 до 15, что, конечно, недопустимо. Этот недостаток и устраняется модуляционным кодом Грея, у которого при переходе
от числа к соседнему числу (от фазы – к соседней фазе) изменяется
только один разряд. Однако в этом случае при необходимости требуется иметь дополнительный преобразователь для представления
полученных в коде Грея чисел в
обыкновенном двоичном коде.
Обратное преобразование кода
Грея в двоичный код производит0
ся, начиная со старшего разряда,
1
1415
2
по следующему правилу. Снача13
3
ла переписывается без изменения
12
11
4
старший разряд преобразуемой
10
5
комбинации. Значение каждого
98
6
последующего разряда двоично7
го кода находится путем сложения по модулю 2 этого разряда в
коде Грея с предыдущими, более
старшими разрядами. Например,
Рис. 7.1. Кодирующий диск
комбинация кода Грея 1001соот68
ветствует следующей комбинации двоичного кода: старший разряд
– 1, следующие разряды 0 + 1 = 1, 0 + 0 + 1 = 1, 1 + 0 + 0 + 1 = 0, т. е.
1110. Отметим, что код Грея отходит от систем счисления.
7.2. Перекодировка при относительной фазовой модуляции
(ОФМ)
В существующих системах передачи информации (СПИ) с фазоманипулированными сигналами (ФМ) реализация демодуляторов
ФМ сигналов на приемной стороне встречает определенные трудности, связанные с созданием опорного напряжения с неизменной
начальной фазой. Дело в том, что фазовый детектор демодулятора
должен иметь два входа: информационный и опорный для определения начальной фазы символов при абсолютной фазовой модуляции – 0 или π. Как правило, в СПИ опорный сигнал формируется из
принимаемого сигнала. Однако при равновероятных ФМ сигналах
в их спектре отсутствует опорная составляющая на частоте несущей и ее невозможно получить путем фильтрации. В этом случае
приходится применять способы формирования опорного напряжения, основанные на снятии манипуляции принятого сигнала. Примерами соответствующих устройств служат схемы Пистолькорса,
Сифорова, Костаса и др.
Однако всем известным схемам формирования опорного сигнала
в системах с ФМ присущ одинаковый недостаток: из-за воздействия
различных неконтролируемых факторов возможны случайные изменения фазы опорного сигнала на π. При этом даже в отсутствие
помех передаваемый символ 1 регистрируется как 0, а передаваемый символ 0 – как 1. Возникает явление, называемое «обратной
работой» или «работой в негативе», которое будет продолжаться
до следующего случайного скачка фазы опорного сигнала, поэтому противоположные сигналы (с фазой 0 и π) невозможно использовать в режиме обычной абсолютной ФМ в радиоканалах. Однако
существует метод, позволяющий ценой небольшого энергетического проигрыша реализовать в радиоканалах преимущества таких
сигналов. Этот метод, предложенный Н.Т. Петровичем и первоначально названный им относительной фазовой телеграфией (ОФТ),
в дальнейшем стали называть относительной фазовой модуляцией
(ОФМ), фазоразностной модуляцией (ФРМ) или дифференциальной фазовой модуляцией. Метод заключается в том, что полезная
информация содержится не в абсолютном значении начальной
фазы сигнала, а в разности начальных фаз двух соседних сигналов.
Для передачи символа 0 начальная фаза передаваемого колебания
69
сохраняется неизменной по отношению к начальной фазе колебания на интервале длительности предшествующего символа. Для
передачи символа 1 начальная фаза излучаемого колебания поворачивается на π по отношению к предшествующему символу.
При обработке сигналов с ОФМ на приемной стороне, прежде
всего, определяются начальные фазы принятых сигналов, а затем
на основе сравнения начальных фаз соседних сигналов принимаются решения о переданных информационных символах. В данном
случае при каждом случайном скачке фазы опорного колебания в
приемнике будет ошибочно принят только один символ и исключается возможность работы в негативе. Однако работа с ОФМ требует на передающей стороне перекодировки исходной информационной видеопоследовательности. Необходимо получить короткие
импульсы, соответствующие передним фронтам единичных информационных символов, даже подряд следующих, а затем ими
запустить триггер, напряжение с которого и подается на фазовый
модулятор передатчика. Для выделения фронтов подряд следующих единичных символов потребуется использовать непрерывную
последовательность тактовых импульсов, формируемую в синхронизаторе передающей стороны. Алгоритм приема сигналов с ОФМ
реализуется фазовым детектором, на который в качестве опорного
напряжения подается предыдущий символ, задержанный на длительность одного такта.
Таким образом, относительную ФМ можно рассматривать как
обычную, но при соответствующем дополнительном кодировании
передаваемого сообщения в модуляторе передающей стороны.
7.3. Код – дифференциальный Манчестер
В современных телемеханических системах применяются различные импульсные последовательности для передачи двоичных
кодов. Как правило, проводные каналы связи являются наиболее
дорогостоящей составляющей системы передачи информации. Поэтому наряду с передачей телемеханической информации, в частности, в энергосистемах, они используются для телефонной, телеграфной и других видов связи. В телефонных каналах частотная полоса каналов телемеханики обычно ограничена надтональным или
подтональным диапазоном, вследствие чего скорость передачи телемеханической информации обычно не превышает 200 бит/с. При
передаче двоичных кодовых последовательностей видеоимпульсов
с большим числом подряд следующих 1 или 0 в спектре присутствует постоянная составляющая, что отрицательно сказывается
70
II
1
1
0
0
1
1
1
0
+
+
+
+
+
+
+
+
0 + 1 + 0 + 0 + 0 + 1 + 0 + 1 + 1
III
0
I
0
1
1
0
0
1
1
1
0
Рис. 7.2. Прямое и обратное преобразование простого двоичного кода в
сигнал «дифференциальный Манчестер»: I – двоичный код; II –
сигнал «дифференциальный Манчестер»; III – восстановление
двоичного кода
на прохождении сигналов через разделительные трансформаторы.
Для устранения этого недостатка применяют сигналы с чередующейся инверсией знака в пределах одного бита (+ – или – +), что и
характерно для дифференциального Манчестера. Его отличительной чертой является то, что переходы с высокого на низкий потенциал и наоборот всегда располагаются посередине бита. Последнее
обстоятельство используется для самосинхронизации генераторов
приемника и передатчика. В пределах одного бита при передаче 1
последовательность смены «+» на «–» или «–» на «+» определяется
противоположным значением начальной «фазы» (+ или –) предыдущего бита, как это делается при относительной (дифференциальной) фазовой модуляции (π на 0 или 0 на π), а при передаче 0 – с
сохранением «фазы» предыдущего символа.
Сигналы этой последовательности образуются следующим образом: очередной бит «дифференциальный Манчестер» равен биту
исходного информационного двоичного кода плюс значение предыдущего бита «дифференциальный Манчестер» по модулю. Так,
например, двоичная последовательность 011001110 записывается
сигналами «дифференциальный Манчестер» следующим образом:
10001011, что и является перекодировкой при модуляции.
Преобразование сигналов из исходной двоичной последовательности в сигналы «дифференциальный Манчестер» и обратное восстановление на приемной стороне иллюстрируется рис. 7.2.
Таким образом, перекодировка видеосигналов для нужд телемеханики осуществляется аналогично перекодировке радиосигналов
при символах с относительной фазовой модуляцией.
7.4. Диаграммы работы кодека с ОФМ
(практическое задание)
Разработать, изобразить схему и соответствующие временные
диаграммы для кодека с относительной фазовой модуляцией.
71
1. Записать слитно свою фамилию и имя, заменить согласные
буквы – единицей, а гласные – нулем. Эту информационную последовательность из 10 символов записать в строчку с интервалом
между символами порядка одного сантиметра. С этим интервалом
на временной диаграмме зарисовать последовательность тактовых
импульсов синхронизатора передающей стороны, и сбоку от диаграммы изобразить сам блок синхронизатора. Выделить соответствующие импульсы, необходимые для перекодировки информационной последовательности при ОФМ, изобразить соответствующие
временные диаграммы и сбоку формирующие их схемы. Подать
полученную перекодированную последовательность на фазовый
модулятор передатчика и нарисовать его диаграмму с изображением одного периода синусоиды с начальной фазой 0 или π в пределах
одного тактового интервала.
2. В декодере приемной стороны на выходе приемника повторить временную диаграмму передатчика (считая задержку на время распространения радиоволн от передатчика до приемника, равной нулю). Изобразить соответствующие временные диаграммы и
схемные блоки приемной части и получить диаграмму исходной
информационной видеопоследовательности.
3. В принимаемой последовательности изменить фазу одного
(любого) принятого синусоидального импульса на противоположную. На выходной временной диаграмме показать результат декодирования. Прокомментировать результат.
Результаты практического задания сдать преподавателю для
проверки.
72
8. СИНХРОНИЗИРУЮЩИЕ КОДЫ
8.1. Разновидности синхронизирующих кодов
Системы синхронизации радиотехнических систем должны поддерживать постоянство следующих синхропараметров сигналов:
− фазу высокочастотного несущего колебания (фазовая синхронизация ФС);
− временные границы принимаемых посылок (тактовая синхронизация);
− моменты, соответствующие началу кодовых слов (цикловая
синхронизация);
− моменты, соответствующие началу и концу групповых сигналов
в многоканальных системах передачи (кадровая синхронизация);
− начало и конец передаваемого сообщения.
В подавляющем числе случаев сигналы тактовой, цикловой и
кадровой синхронизации связаны по фазе между собой (синхронны). Частота повторения кодовых слов fЦ получается путем деления тактовой частоты fТ на число разрядов в кодовом слове (fЦ =
= fТ /n), частота повторения кадров – делением частоты повторения
кодовых слов на число кодовых слов в кадре (fК = fЦ /nС).
В ряде радиотехнических систем передачи, в частности, с периодической групповой передачей, важно знать начало передаваемого
сообщения. Для этого в начале сеанса связи передается специальный сигнал (преамбула), по которому определяется факт передачи
сообщения и его временное положение. Такой сигнал используется
в международной Космической системе поиска аварийных судов
(КОСПАС – САРСАТ) при посылке сообщений с Аварийных радиобуев АРБ-406, работающих на частоте 406 МГц. Сигналы с АРБ
в кодированной форме компонуются в виде кадра аварийного сообщения, после включения буя они в автоматическом режиме периодически посылаются для приема на борту искусственного спутника
земли (ИСЗ). Рассмотрим формат сообщения с аварийного радиобуя
АРБ-406 с позиций обеспечения синхронизации его посылки.
8.2. Преамбула формата сообщения аварийного радиобуя
АРБ – 406
Передатчик АРБ первоначально излучает преамбулу в виде немодулированной несущей в течение времени, необходимого для его
обнаружения и установления синхронизации с помощью следящей системы бортового приемника искусственного спутника земли
(ИСЗ). После этого передаются модулированные по фазе синхросиг73
налы, и лишь затем аварийное сообщение в цифровом виде, содержащее данные о стране регистрации АРБ, его номере и т. п.
Временная структура излучаемого сигнала АРБ (формата сообщения) приведена в табл. 8.1, где определены интервалы времени,
отведенные для передачи синхросигнала и аварийной информации.
В табл. 8.1 показан «короткий формат» портативного морского АРБ
с длительностью сообщения 440 мс без ввода координат и характера
бедствия. На больших судах имеется возможность вводить в сообщения эти данные, тогда длительность сообщения увеличивается до
520 мс («длинный формат»). Эти кодовые группы посылаются с периодичностью 50 с при времени непрерывной работы АРБ порядка 24 ч.
Таблица 8.1. Временная структура излучаемого сигнала АРБ
Время, мс
160
37,5
22,5
2,5
10
20
120
52,5
2,5
12,5
Содержание сигнала
Несущая частота
Символьная синхронизация (все 1)
Кадровая синхронизация (000101111)
Признак формата
Тип потребителя
Страна
Код идентификации объекта
Код коррекции ошибок
Признак информационного поля
Время, прошедшее с момента аварии
∑ = 440 мс – короткий формат
Бит
64
15
9
1
4
8
48
21
1
5
176
Устройства синхронизации (УС), входящие в систему синхронизации, можно разделить на два принципиально различных типа.
Первый тип служит для синхронизации отсчета времени (фазовая
и тактовая синхронизация). С их помощью формируются временные шкалы.
Второй тип устройства служит для устранения неоднозначности
отсчетов времени при установлении начала слова, кадра и сообщения. Устройства синхронизации отсчетов времени должны функционировать непрерывно, отслеживая изменения фазы входного
колебания, функции устройства устранения неоднозначности сводятся к периодическому, а иногда и к однократному фазированию.
Для простоты и экономичности производства в АРБ-406 используется нетермостатированный кварцевый генератор, обладающий
относительной средневременной нестабильностью порядка 10-8.
Отметим, что в других системах фазовой синхронизации на ИСЗ
применяются атомные цезиевые стандарты частоты с нестабильностью до 10-14. В наземных станциях при приеме сигналов АРБ
с ИСЗ используются системы фазовой автоподстройки частоты
(ФАПЧ), которые запоминают значение принятой опорной часто74
ты и обеспечивают когерентный прием последующих сигналов во
всем кадре. Системы ФАПЧ являются основным звеном устройств
синхронизации отсчетов времени. Они в том или ином виде входят
в устройства фазовой и устройства тактовой синхронизации демодулятора и служат для фильтрации синхроколебаний.
Последующие, после несущей частоты, 15 бит символьной (тактовой) синхронизации передаются классическим кодом Манчестера, который, как отмечалось ранее, при передаче всех «единиц»
трансформируется в чередующую последовательность единиц и нулей (101010…), называемую меандром. Меандр также с помощью
системы ФАПЧ обеспечивает полную тактовую синхронизацию на
интервале всего последующего кадра.
Интересно отметить, что геометрический орнамент в виде ломаной линии − меандр получил название в Древней Греции от названия извилистой реки Меандр.
При установлении тактовой синхронизации для синхронизации
информационного кадра используется одно определенное кодовое
слово, называемое уникальным, передаваемое в начале кадра. Кадровое синхрослово (КСС) по своей структуре должно существенно
отличаться от всех возможных кодовых комбинаций, образуемых
при последующей передаче дискретной информации, и обеспечивать наилучшие условия его поиска и обнаружения в информационной последовательности символов даже при наличии искажений
принимаемых посылок. В качестве кодового слова кадровой синхронизации в формате сообщения АРБ-406 используется последовательность из 9 символов – 000101111.
Для выделения КСС в приемнике системы используется дискретный оптимальный согласованный фильтр, настроенный на КСС,
для приема его в целом. На выходе фильтра выходное напряжение
повторяет по форме автокорреляционную функцию (АКФ) с максимальным значением в момент окончания КСС. В момент превышения выходным напряжением порога выделяется импульс кадровой
синхронизации. Желательно, чтобы кодовая комбинация КСС или
вообще в последующем информационном потоке не встречалась,
или ее появление в нем было маловероятным. Специальным выбором структуры КСС можно добиться того, чтобы эта вероятность
была достаточно малой. Кодовые последовательности, удовлетворяющие этому требованию, должны иметь автокорреляционные
функции (АКФ) с низким уровнем боковых лепестков для исключения превышения боковым лепестком АКФ заданного порога.
В качестве КСС в настоящее время широко используются коды
Баркера и М-последовательности, формируемыми генераторами,
75
включающими в свой состав сдвигающие регистры и сумматоры по
модулю 2. О них и пойдет речь далее.
8.3. Синхронизирующие коды Баркера
Код Баркера имеет отличную автокорреляционную функцию
(АКФ), которая делает его идеальным кодом для кадровой синхронизации, поскольку в условиях многолучевых замираний синхронизация зависит от превышения корреляционным пиком некоторого заданного порогового уровня, а уровень боковых лепестков
АКФ, по форме совпадающей с выходным напряжением согласованного фильтра, самый миниатюрный и равен всего единице.
Малый уровень боковых лепестков кода Баркера позволяет с малой вероятностью неоднозначности определять начало цикла информационных символов, длительности их кодовых групп в дальнейшем
определяются априорно с помощью счетчиков тактовых импульсов.
Известные двоичные баркеровские последовательности (слова)
приведены в табл. 8.2. Максимальное число символов в коде Баркера не превышает 13.
Таблица 8.2. Двоичные баркеровские последовательности
№
N
1
2
3
4
5
6
3
4
5
7
11
13
Коды Баркера
110 (101)
1101 (1110)
11101
1110010
11100010010
1111100110101
Мнемоника
Чти
план.
Впрок
скроена
сбруя у воина.
В РТС ПИ экзамен.
Для N = 3 и N = 4 существуют 2 последовательности.
Поскольку кодов Баркера всего 6, то по причине уникальности
этих кодов их целесообразно запомнить, что легко делается с помощью мнемонического текста, помещенного в табл. 8.1. В общем случае, мнемоника (от греч. – искусство запоминания) – совокупность
приемов, имеющих целью обеспечить запоминание возможно большего числа сведений или фактов. Достаточно в соответствующей
строчке текста заменить согласные буквы – 1, а гласные – 0, как
будет получен N-символьный код Баркера. В коде для N = 13 подряд следует 5 единиц, но в русском языке не имеется слов с подряд
следующими пятью согласными буквами и приходится прибегать
к аббревиатуре (от латинского – краткий). РТС ПИ – название лекционного курса радиотехнические системы передачи информации.
Рассмотрим один из вариантов формирования и обработки сигналов Баркера. В верхней части рис. 8.1 изображен генератор сиг76
налов Баркера с числом импульсов N = 5. На вход сдвигающего
регистра (СР) поступает запускающий одиночный импульс, совпадающий по временному положению с тактовым импульсом. Запускающий импульс с частотой тактовых импульсов перемещается
по разрядам СР к его выходу. Так как кодовая последовательность
Баркера с N = 5 имеет вид 11101, то импульсы с первых трех и пятого разрядов СР поступают на вход схемы ИЛИ непосредственно,
а импульс с четвертого отвода поступает на вход схемы через инвертор (ИН), который превращает положительный импульс в отрицательный, т. е. осуществляет изменение фазы на π. На выходе схемы
ИЛИ имеет место видеосигнал Баркера, который затем поступает
на вход модулятора передатчика.
Оптимальная обработка сигналов Баркера на приемной стороне
производится с помощью согласованного фильтра, выполняемого также на базе сдвигающего регистра (рис.8.1, справа). Так как
импульсная характеристика согласованного фильтра совпадает с
зеркально отраженным сигналом, то кодовую импульсную характеристику фильтра для сигнала Баркера следует устанавливать
в соответствии с «вывернутой наизнанку» последовательностью
10111. Поэтому импульсы с первого, третьего, четвертого и пятого
отводов СР поступают на сумматор Σ непосредственно, а со второго
отвода – через инвертор (ИН), который меняет фазу на π. На выходе
сумматора имеет место АКФ сигнала Баркера, построение и огибающая которой приведены в центре рис. 8.1.
И К ПРД
Л
И 11101
ИН
«1»
Сдвиг
СР
+
+ +
−
+
+
+
+
+
−
−
−
−
+
+
+
+
−
+
+
+
+
+
+
+
−
−
+
+
Сдвиг
От ПРМ
10111
ИН
+
−
+
+
−
+
СР
Σ
Выход
1
0
1
0
5
0
1
0
1
0
Рис. 8.1. Кодек и АКФ сигнала Баркера для N = 5.
77
К сожалению, максимальное число символов в коде Баркера
N = 13, и кодовых последовательностей в АКФ с уровнем боковых
лепестков, равных 1, больше не существует. Однако Нейман и Гофман путем моделирования на ЭВМ определили последовательности
с хорошими синхронизирующими свойствами и числом символов в
кодовых словах до N = 24 с уровнем боковых лепестков в АКФ порядка 2 ÷ 4. Интересно отметить, что Нейману и Гофману только
для N = 24 пришлось просмотреть 224 = 24 × 210 × 210 = 16 × 1024 ×
× 1024 ≈ 16 миллионов кодовых комбинаций для публикации соответствующих таблиц.
Наряду с рассмотренными синхронизирующими кодовыми последовательностями для этих же целей могут быть применены Мпоследовательности, достаточно просто формируемые, с уровнем
боковых лепестков АКФ порядка 1/ N .
8.4. Автокорреляционные функции кодовых слов
(практическое задание)
Требуется построить две автокорреляционные функции.
1. Записать дату своего дня рождения. Взять за номер задания
одиночную цифру или вторую цифру двузначного числа. По номеру задания выбрать последовательность Неймана–Гофмана и построить ее АКФ. Поскольку АКФ симметрична относительно своего
максимума, построить можно до значения, равного N (число символов в коде Неймана–Гофмана). Часть кодов Неймана–Гофмана
приведена в табл.8.3.
Таблица 8.3. Коды Неймана–Гофмана
№
1
2
3
4
5
6
7
8
9
0
Кодовое слово
0000001100101
0000010110011
00001100110101
00110011111010
001111100110101
000011001001010
0000011001101011
0000111011101101
00001011001110101
00001111011011101
N
13
13
14
14
15
15
16
16
17
17
2. Построить АКФ уникального кодового слова, используемого в
посылке аварийного радиобуя АРБ-406 системы КОСПАС-САРСАТ
(см. табл. 8.1.) – 000101111. По результатам построений сформулировать выводы.
Типовой расчет сдать преподавателю.
78
9. КОДЫ ЗАЩИТЫ
ОТ НЕСАНКЦИОНИРОВАННОГО ДОСТУПА
9.1. Шифры тайнописи текстовых сообщений
Коды появились в глубокой древности в виде криптограмм.
В средние века и эпоху Возрождения над изобретением тайных
шрифтов трудились многие философы и математики. Собственная
секретная азбука была и у Юлия Цезаря. Шифр Цезаря состоит в
том, что весь исходный алфавит сдвигается на определенное число
букв влево или вправо относительно шифруемого текста. В частности, при сдвиге влево на одну букву каждая буква шифруемого
текста заменялась предшествующей буквой алфавита (при этом,
для буквы «а» предшествующей считалась буква «я»). В настоящее
время подобный вид криптограмм получил название подстановочных криптограмм.
Однако расшифровка подобных шифрограмм не составляет
большой проблемы. Все основывается на том, что различные буквы
естественного языка – английского, русского или какого-либо другого встречаются в осмысленных текстах неодинаково часто. Следовательно, то же самое верно и для соответствующих им знаков.
В еще большей мере это относится к буквосочетаниям из двух или
нескольких букв: лишь некоторые из них часты, многие же вообще
не употребляются.
Анализируя частоту появления тех или иных знаков и их сочетаний, можно с большой уверенностью восстановить буквы зашифрованного текста. Даже если в каких-то частях текста возникает
неоднозначность, она легко устраняется по смыслу. Этот метод,
именуемый частотным анализом, основывается, таким образом,
на заранее известных частотах зашифрованных знаков. В соответствующих таблицах указаны относительные частоты букв русского
языка. Наиболее частая буква русского языка – «о». Ее относительная частота, равная 0,090, означает, что на 1000 букв русского текста приходится в среднем 90 букв «о». В таком же смысле понимаются относительные частоты и остальных букв.
Ненадежность подстановочных криптограмм (сравнительная
легкость их расшифровки) была замечена уже давно, и поэтому в
разное время предлагались различные другие методы шифрования. Среди них важное место занимают перестановочные криптограммы. При их составлении весь текст разбивается на группы,
состоящие из одинакового числа букв, и внутри каждой группы
буквы некоторым образом переставляются. Если группа достаточ79
но длинная (иногда это весь текст целиком), то число возможных
перестановок очень велико, отсюда большое многообразие перестановочных криптограмм. Ряд типов перестановочных криптограмм
составляется при помощи так называемого ключевого слова. Буквы текста, который должен быть передан в зашифрованном виде,
первоначально записываются в клетки прямоугольной таблицы
по строчкам. Буквы ключевого слова пишутся над столбцами и
указывают порядок (нумерацию) этих столбцов. Чтобы получить
закодированный текст (в качестве текста возьмем одно лишь слово – «криптограмма»), надо выписывать буквы по столбцам с учетом нумерации столбцов. Для примера возьмем ключевое слово из
6 букв – «лекция», столбцы занумеруем в соответствии с порядковым положением букв ключевого слова в русском алфавите. В результате получится следующая кодовая таблица (начало ее):
Л Е К Ц ИЯ ЛЕКЦИЯ
413526413526
К Р И П Т О Г РА ММА
...
Выписывая буквы из столбцов таблицы (сначала из первого,
затем из второго и т. д.), получаем такую шифрограмму: РРТМИАКГПМОА.
Ключевое слово известно, конечно, и адресату, который поэтому
без труда расшифрует это сообщение. Но для тех, кто этим ключом
не владеет, восстановление исходного текста весьма проблематично (хотя, в принципе, возможно). Частотный анализ здесь по вполне понятным причинам не решает задачи. Использование ключевого слова, конечно, не обязательно, можно было указать нумерацию
столбцов цифровым ключом, в данном случае, числом 413526. Слово удобнее, если ключ надо хранить в памяти. Обратим внимание на
то, что идея построения перестановочных криптограмм повторяет
в принципе процедуру перемежения, рассмотренную в подразд. 6.
Имеется ряд шифров, в которых совмещены приемы подстановочного и перестановочного кодирования. Шифр можно еще более
усложнить, если каждую букву заменить не одним, а двумя или несколькими символами (буквами или числами). В частности, можно расположить буквы русского алфавита (32 буквы) в квадратной
матрице 6 × 6 (36 клеток) произвольным, хаотическим образом.
Каждая буква шифруемого текста заменяется парой цифр: первая
цифра – номер строки, в которой стоит данная буква, вторая – номер этой буквы в данной строке (№ столбца). Вместо алфавита можно использовать некоторый заранее условленный текст, известный
80
и отправителю, и адресату. Однако при этом размер матрицы будет
больше из-за повторяемости букв в осмысленном тексте, содержащем все (большинство) буквы русского алфавита.
9.2. Шифр по задающей ключевой матрице
(практическое задание)
Приведем пример использования для шифрования матрицы с
ключевым текстом и кодированием букв сообщения двумя цифрами: первая – номер строки, вторая – номер столбца матрицы из
табл. 9.1.
Таблица 9.1. Шифрование матрицы
1
2
3
4
5
6
7
1
Б
У
Й
О
М
Н
Е
2
Е
С
В
Р
Ч
В
К
3
Л
О
Т
Я
Т
К
О
4
Е
Д
У
Г
О
Р
М
5
Е
И
М
О
И
А
6
Т
Н
А
Л
Щ
Ю
Ь
7
П
О
Н
У
Е
Д
8
А
К
Е
Б
Т
А
Ы
9
Р
И
М
О
О
Л
В этом ключевом тексте 58 букв и буква «О» в нем встречается 8
раз, т. е. с вероятностью 8/58 = 0.137, буква «Е» − 6 раз (с вероятностью 0,103), буквы «А» и «И» по 4 раза (с вероятностью 0,069).
Эти наиболее часто встречающиеся в русских текстах буквы, имеют официально признанные вероятности появления: «О» − 0,090,
«Е» − 0,072, «А» и «И» по 0,062. Эта же закономерность справедлива и для шифруемого текста. Поэтому при цифровом кодировании предназначенного для передачи текста, необходимо эти часто
встречающиеся буквы кодировать разным набором цифр, чтобы невозможно было применить при несанкционированной расшифровке текста метод «частотного анализа». В конце ключевого текста
приведены две буквы (Ь и Ы), которые в тексте не встречаются, но
есть в кодограмме.
Для выполнения задания требуется с использованием табл. 9.1
расшифровать следующую цифровую кодограмму:
4317233526665221426227125144374132146176151738195724457
43754314362556922438578
При передаче по радиоканалу этой кодограммы можно использовать любые коды с обязательным применением синхронизирующих кодов для нарезки непрерывной последовательности цифр в
группы по 2 цифры.
Расшифровку кодограммы сообщить преподавателю.
81
9.3. Защита с помощью М-последовательности
Наиболее широкое применение для защиты от несанкционированного доступа (ЗНД) в системах связи нашли так называемые
М-последовательности – последовательности максимальной длины или псевдослучайные последовательности (ПСП). В процессе
шифрования цифровые эквиваленты знаков криптографически закрываемого сообщения складываются с псевдослучайной последовательностью чисел, именуемой гаммой. Таким образом, ПСП выполняет роль ключа. Наиболее часто гаммирование используется
для криптографического закрытия сообщений, уже выраженных в
двоичном коде. При этом, как правило, используются двоичные Мпоследовательности, символы которых принимают значения 1 и 0.
Такие последовательности обладают следующими свойствами.
1. М-последовательности являются периодическими с периодом
N = 2n – 1 символов, где n – произвольное целое положительное
число.
2. Количество символов, принимающих значение единица на
длине одного периода М-последовательности, равно 2n – 1, что на
единицу больше, чем количество символов, принимающих значение нуль.
3. Любые комбинации символов длины n на одном периоде Мпоследовательности встречаются не более одного раза.
4. Сумма по модулю 2 любой М-последовательности с ее произвольным циклическим сдвигом также является М-последовательностью.
5. Периодическая автокорреляционная функция (АКФ) любой
М-последовательности имеет постоянный уровень боковых лепестков, равный 1/N. Уровень максимальных боковых лепестков апериодической АКФ примерно составляет1/ N .
Формируются М-последовательности многотактными линейными фильтрами в виде сдвигающих регистров с обратной связью. Для
формирования М-последовательности с периодом N = 2n – 1 может
использоваться регистр сдвига длины n. Структура обратных связей регистра определяется, как для циклических и сверточных кодов, соответствующими многочленами степени n. Схема фильтра,
генерирующего М-последовательность длины N, построенного на
основе многочлена G(X) = X 5 + X 2 + 1, приведена на рис. 9.1.
С поступлением на тактовый вход регистра очередного тактового импульса состояние ячеек регистра последовательно меняется
(на данной схеме слева направо).
82
+
1
0
0
0
0
Сдвиг
Рис. 9.1. Генератор М-последовательности для N = 31
М-последовательность (один период), генерируемая таким регистром, имеет следующий вид: 00001001011001111100011011101
01. К последовательностям немаксимальной длины относятся ПСП
Голда и Кассами.
В сотовых системах связи, в частности, для защиты от подслушивания используются различные методы шифрования передаваемой
информации. Шифрование осуществляется путем помехоустойчивого кодирования и перемежения на стороне передачи и заключается в поразрядном сложении по модулю 2 информационной битовой последовательности и специальной битовой псевдослучайной
последовательности (ПСП), составляющей основу шифра, которая
генерируется аналогично М-последовательности. Повторное применение операции сложения по модулю 2 с той же ПСП к зашифрованной информационной последовательности восстанавливает
на стороне приема исходную информационную битовую последовательность, т. е. реализует дешифрацию шифрованного сообщения
(рис. 9.2).
Исходная информация
Шифрующая ПСП
Зашифрованная информация
Дешифрующая ПСП
Расшифрованная информация
100101101000110…
010010110011100…
110111011011010…
010010110011100…
100101101000110…
Рис.9.2. Принцип шифрования и дешифрования в сотовой связи
Для засекречивания вида шифрующей последовательности имеются три варианта изменения параметров схемы формирования
ПСП: число триггеров (разрядов) в схеме сдвигающего регистра
(СР), нумерация отводов от ячеек регистра на схемы суммирования
по модулю 2 и конфигурация соединения схем суммирования друг
с другом до подачи результата на вход сдвигающего регистра. В сотовых системах связи с кодовым разделением каналов IS-95 для целей шифрования одновременно используются две ПСП: первая – в
прямом канале для шифрования информации на базовой станции
83
и дешифрации на подвижной станции (при 42 разрядах СР) и вторая – в обратном канале для шифрования информации на подвижной станции и дешифрации на базовой (при 15 разрядах СР).
Алгоритм шифрования с использованием ПСП в стандарте сотовой связи GSM является секретным. Описание этого алгоритма
не включено в общие спецификации стандарта GSM, он распространяется под жестким контролем Международной ассоциации
компаний операторов стандарта. Надежность криптографического
закрытия методом гаммирования определяется, главным образом,
длиной неповторяющейся части гаммы. Фрод (англ. термин fraud –
обман, мошенничество) существенно затрудняется для фродстеров
при применении рассмотренных соответствующих мер по защите
от несанкционированного доступа в системы сотовой связи. Интересно отметить, что в США в Своде федеральных законов имеется
статья 1029, относящаяся к системам мобильной связи, «Фрод и
связанная с ним деятельность в сочетании с устройствами доступа». Она устанавливает в числе прочего наказания в виде штрафов
и тюремное заключение на срок до 10–20 лет за мошенничество с
целью получения несанкционированного доступа к телекоммуникационным услугам.
84
10. СИСТЕМЫ И УСТРОЙСТВА
ШТРИХОВОГО КОДИРОВАНИЯ
10.1. Построение устройств штрихового кодирования
Сфера применения штриховых кодов (ШК) охватывает практически все возможные области человеческой деятельности, в которых она связана с обработкой информации о материальных потоках различных видов. Такие системы нашли применение в магазинах для автоматизации кассового учета приобретенных товаров,
контроля состояния складов, приема и выдачи грузов в аэропортах, контроля и регистрации рабочего времени в офисах, учета движения партий продукции и отдельных изделий в промышленном
производстве и т. д. Интенсивная разработка ШК началась в начале
70-х гг. и продолжается по настоящее время.
Необходимо отметить, что первыми системами штрихового кодирования были системы «2 из 5», «39», «93», «Codabar», «Code 11».
Однако самые распространенные системы – это Универсальный товарный код – UPS, используемый как в торговой, так и в промышленной сети, а также – Европейская система кодирования – EAN.
Америка приняла UPS в 1973 г., в 1977 г. в Европе, а затем и в других странах утвердилась EAN.
По исследованиям, проведенным в США, имевшим целью определить преимущества автоматической идентификации материальных потоков, оказалось, что скорость ввода штрихового кода по
сравнению со скоростью ввода символов с клавиатуры возрастает в
1,5–2 раза, а достоверность считываемых данных повышается на
несколько порядков. Так, в проекте Министерства обороны США
с помощью штрихового кода было обработано 70 млн символов и
произошло лишь четыре ошибки. При вводе того же количества
данных с клавиатуры их было бы 22000.
В самом общем виде структура построения системы обработки
и нанесения штриховых кодов включает в себя: устройство считывания штрихового кода; компьютер или микропроцессорный комплект (МПК), осуществляющие прием и расшифровку сигналов
считываемого кода, обработку закодированной в нем информации,
выработку в случае необходимости управляющих и корректирующих сигналов. В состав системы входят также устройства кодирования информации и распечатки штриховых кодов на твердом или
любом другом носителе; блок сопряжения устройства считывания с
МПК; печатающее устройство (принтер), подключаемое к МПК для
нанесения штриховых кодов на носитель.
85
Таким образом, процесс считывания информации со штрихового кода можно разделить на три модуля: 1) сканирование; 2) декодирование; 3) обработка информации.
При сканировании источник светового излучения, двигаясь с
постоянной скоростью вдоль кода, освещает светлые и темные полосы кода, а светочувствительный элемент преобразует отраженный свет в электрический сигнал, который обрабатывается на выходе в модуле декодирования. При этом сканирование может быть
ручным; тогда оператор, держа в руках сканирующий прибор, проводит им по штриховому коду; механическим, когда сканирующий
прибор приводится в движение с помощью, например, электромотора, а также когда сканер неподвижен и передвигается сам носитель штрихового кода с помощью конвейера.
Основной задачей модуля декодирования является преобразование полученного в результате сканирования электрического сигнала в соответствующий код, читаемый МПК. Обычно это достигается с помощью микропроцессора или специальных декодирующих
схем.
И, наконец, третий модуль осуществляет расшифровку и обработку закодированной в штриховом коде информации; если необходимо, то направляет полученные данные на периферию МПК и, в
свою очередь, принимает те или иные команды от него.
10.2. Основные структуры штриховых кодов
Распознавание закодированных символов в штриховом коде выполняется по изменению на рисунке кода коэффициента отражения на границе белого и черного. Каждый из кодируемых символов,
например, цифра, буква, или служебный символ, представляются
в штриховом коде определенным набором штрихов определенной
ширины и пробелов между ними.
К числу основных требований, предъявляемых к кодам подобного рода, относятся:
− нечувствительность к ошибкам оператора при использовании
ручного считывающего устройства вследствие нестабильности скорости перемещения;
− возможность считывания кода в прямом и обратном направлениях;
− нечувствительность к отклонениям от прямолинейной траектории, перпендикулярной линиям кода;
− минимальная длина последовательности штрихов и пробелов
на один представляемый символ;
86
− нечувствительность к ошибкам считывания и возможность
автоматического выявления ошибок считывания за счет введения
дополнительных контрольных комбинаций.
Рассмотрим далее структуры некоторых кодов.
Структура кода 39. Это алфавитно-цифровой код, в состав которого включены 44 знака данных: цифры, латинские буквы от A до
Z, шесть специальных знаков, знак пробела и старт-стопный знак.
Код 39 своим названием обязан тому, что является кодовой комбинацией трех из девяти. Каждый отображенный символ в этом
коде представляется с помощью 9 элементов (5 темных штрихов и
4 пробелов между ними). Три элемента из девяти – широкие, шесть
элементов – узкие.
Пример представления в коде 39 символов А76 приведен на рис.
10.1. Для синхронизации считывания и определения направления
движения в этом коде используется старт-стопный знак *, наносимый в начале и в конце набора символов. Штрихи и пробелы имеют
два размера по ширине. Минимальное отношение ширины широкого элемента к ширине узкого составляет 2:1. Максимальное отношение может достигать 3:1. Постоянство относительных размеров широких и узких элементов должно выдерживаться в пределах
считываемых символов на одном носителе ШК.
Код 39 обладает полной нечувствительностью к ошибкам считывания пробелов при обработке цифровых данных.
На рис. 10.1 показан формат цифро-буквенного кода 39. Ширина светлых начальных зон 1 и конечных 7 обычно принимается в 10
раз больше ширины узкого элемента 2. Узкие 4 и широкие 5 пробелы имеют такие же размеры, как и узкие 2 и широкие 3 штрихи.
Расстояние между символами 6 может находиться в пределах 1−3
по отношению к узкому элементу и не воспринимаются считывающим устройством. Следует отметить, что длина каждого из символов составляет 12 узких элементов и имеется два уровня по ширине
светлых и темных полос.
На рис. 10.2 приведена структура цифро-буквенного кода 39.
Структура кода 93. Код 93 также является буквенно-цифровым, включающим 43 знака данных и соответствующие вспомога1
2
3
*
4 5
А
6
7
7
6
*
Рис. 10.1. Формат штрихового кода 39
87
№
Символ
п/п
1
2
Штриховой
код
3
№
Символ
п/п
1
2
M
1
1
23
2
2
24
N
3
3
25
O
4
4
26
P
5
5
27
Q
6
6
28
R
7
7
29
S
8
8
30
T
9
9
31
U
10
0
32
V
11
A
33
W
12
B
34
X
13
C
35
Y
14
D
36
Z
15
E
37
–
16
F
38
:
17
G
39 SPACE
18
H
40
19
I
41
*
$
20
J
42
/
21
K
43
+
22
L
44
%
Штриховой
код
3
Рис. 10.2. Структура штрихового кода 39
тельные знаки. Ширина каждого из элементов может составлять
1, 2 или 3 размера узкого элемента. Старт-стопный знак содержит
штрих размером в четыре ширины узкого элемента. Для этого кода
также характерна возможность двунаправленного считывания
и введение контрольных знаков для выявления возможных ошибок при считывании. В отличие от кода 39 в 93 не предусмотрены
межзначные пробелы. Следует отметить, что коды 39 и 93 имеют
переменную длину. Максимальная длина последовательности сим88
волов (не более 100 мм) определяется возможностями поддержания
стабильной скорости относительного перемещения носителя штрихового кода и считывающего устройства.
Структура кода EAN. Цифровой код EAN (European Article
Number) предназначен для кодирования групп цифр от 0 до 9. Каждый символ состоит из группы штрихов и пробелов длиной в семь
единичных элементов. Ширина штрихов и пробелов может составлять 1, 2, 3 и 4 ширины единичного элемента. Каждая цифра представляется двумя штрихами и двумя пробелами.
Существуют две наиболее распространенные модификации кода
EAN-8 и EAN-13. В EAN-8 может быть закодировано число с восемью десятичными знаками, а в EAN-13 – с тринадцатью. Форматы
представления данных в кодах EAN-8 и EAN-13 жестко фиксированы соответственно на 8 и 13 позициях и не допускают возможности наращивания и использования буквенных обозначений, что
существенно ограничивает область их применения. В этих кодах
предусмотрены символы контроля четности.
Можно отметить, что большинству требований, предъявляемых
к ШК, в наибольшей степени удовлетворяет код 39, что объясняет
расширяющуюся сферу его применения для автоматической идентификации объектов различного назначения.
10.3. Устройства считывания штриховых кодов
Устройства считывания штриховых кодов (УСШК) являются
одним из необходимых и основных узлов, определяющих работу
любой системы обработки и нанесения штриховых кодов в целом.
Они поставляют первичную информацию о считанном коде, как
правило, в виде последовательности импульсов через блок сопряжения непосредственно в микропроцессор или компьютер; УСШК
разделяются по структуре построения фотосчитывающего преобразователя на устройства прямого преобразования и с электронным
сканированием; УСШК прямого преобразования работают по принципу приема отраженного от штрихового кода светового потока,
его преобразования в электрический сигнал с последующим усилением и нормализацией. В качестве источников излучения используются светодиоды, световой поток от которых концентрируется в
одной точке штрихового кода. Приемником отраженного излучения обычно служит один или несколько фотоприемников-фотодиодов. Таким образом, передвигая УСШК (в ручном варианте), а,
следовательно, и пучок света вдоль всего кода, получим на выходе
электрический сигнал, однозначно соответствующий считываемо89
му коду. В случае стационарного варианта передвигается сам носитель ШК с помощью, например, конвейера.
На рис. 10.3 показана в качестве примера конструкция оптоэлектронного преобразователя перьевого типа для штриховых кодов.
В корпусе типа фломастера большого диаметра находится источник излучения − светодиод СД, оптическая система ОС, фокусирующая излучение на штриховой код. Отраженный от ШК световой
поток концентрируется на входном зрачке фотодиода ФД. Фотодиод преобразует этот изменяющийся по интенсивности в зависимости от штрихового кода световой поток в электрический сигнал высокого или низкого уровня (соответственно, при переходе от белых
к черным полосам ШК или наоборот). Усиленный выходной сигнал
ФД и является результатом считывания. Описанная конструкция
проста и надежна и в различных вариантах реализуется в большинстве известных световых перьях.
Другие способы построения УСШК с использованием фиксированного направленного излучения основаны на применении светочувствительных преобразователей и полностью электронного сканирования. В качестве таких преобразователей используют обычно телекамеры, видиконы и лазерные источники излучения. При
этом можно производить в стационарных условиях считывание с
нескольких метров. Использование лазеров позволяет получить
очень качественную спектральную селекцию излучения на фоне
помех, небольшая расходимость пучка излучения на выходе лазера
заметно уменьшает потери энергии при работе на больших расстояниях, особенно в условиях производства.
Считывающие устройства подключаются к микропроцессорам
и компьютерам с соответствующими печатающими устройствами
СД
ОС
Д
ФД
У
Выход
ШК
Рис. 10.3. Оптоэлектронный преобразователь перьевого типа
90
и принтерами. Их программные средства выполняют обработку
последовательностей электрических сигналов от считывающих
устройств, расшифровку считанных символов в соответствующий
код изделия, фиксацию момента времени прихода сообщения и ведение локальной базы данных.
Подключение компьютера, считывающего ШК, к сети на уровне
предприятия позволяет получить объективную картину производственного процесса на основе оперативной информации по каждому
изделию, материалам, инструменту, комплектующим изделиям и
т. д.
Штриховой код для каждого вида товара уникален. При 13 символах в ШК первые два (иногда 3) из них определяют родину изделия. Следующие пять содержат данные о предприятии − изготовителе. Еще пять – некоторые характеристики продукта: его массу,
цвет, размер, стоимость и т. д. Последняя цифра – контрольная,
определяющая правильность считывания кода сканером.
Код страны присваивается Международной ассоциацией товарной нумерации – EAN. Бывший Советский Союз стал ее членом в
1987 г. и получил номера 460 ÷ 469. Ряд других стран имеют следующие номера: США и Канада – 00 ÷ 09, Франция – 30 ÷ 37, ФРГ –
40 ÷ 43, Китай – 690.
С помощью штрихового кода удобно контролировать качество
продукции, а также ее соответствие первоначально заданному образцу.
Применение того или иного типа устройства считывания штрихового кода регламентируется в конечном счете условиями, в которых производится считывание штрихового кода, т. е. условиями
и требованиями самого процесса автоматической идентификации
объектов различного назначения.
91
Рекомендуемая литература
1. Радиосистемы передачи информации: учебное пособие для
вузов/под ред. И. Б. Федорова и В. В. Калмыкова. М.: Горячая линия – Телеком, 2005. 472 с.
2. Волков Л. Н., Немировский М. С., Шинаков Ю. С. Системы
цифровой радиосвязи: учебное пособие для вузов. М.: Эко-Трендз,
2005. 397 с.
3. Попов В. И. Основы сотовой связи стандарта GSM. М.: ЭкоТрендз, 2005. 296 с.
4. Системы мобильной связи: учебное пособие для вузов/под ред.
В. П. Ипатова. М.: Горячая линия – Телеком, 2003. 272 с.
5. Ратынский М. В. Основы сотовой связи / под ред.Д. Б. Зимина. М.: Радио и связь, 1998. 248 с.
6. Митюшкин К. Г. Телеконтроль и телеуправление в энергосистемах. М.: Энергоатомиздат, 1990. 288 с.
7. Дмитриев В. И. Прикладная теория информации: учебное пособие для вузов. М.: Высш. шк., 1989. 320 с.
8. Бузников С. Е., Кафафов А. А., Матвеевский В. Р. Системы и
устройства штрихового кодирования. М.: Знание, 1990. 64 с.
9. Аршинов М. Н., Садовский Л. Е. Коды и математика. М.: Наука, 1983. 144 с.
10. Фомин С. В. Системы счисления. М.: Наука, 1980. 49 с.
11. Никитин Г. И., Поддубный С. С. Помехоустойчивые циклические коды: учебное пособие/ СПбГУАП. СПб., 1998. 72 с.
12. Никитин Г. И. Сверточные коды: учебное пособие/ СПбГУАП.
СПб., 2001. 80 с.
13. Никитин Г. И. Применение функций Уолша в сотовых системах связи с кодовым разделением каналов: учебное пособие /
СПбГУАП. СПб., 2003. 86 с.
14. Никитин Г. И. Основы кодирования сообщений в системах
связи: учебное пособие/ СПбГУАП. СПб., 2004. 136 с.
15. Никитин Г. И. Наземные системы мобильной связи: курс
лекций/ СПб.: ГУАП. 2007. 82 с.
92
Учебное издание
Никитин Герман Иванович
РАДИОТЕХНИЧЕСКИЕ СИСТЕМЫ
ПЕРЕДАЧИ ИНФОРМАЦИИ
ОСНОВЫ ТЕОРИИ КОДИРОВАНИЯ
Учебно-методическое пособие
Редактор А. В. Семенчук
Верстальщик С. Б. Мацапура
Сдано в набор 17.06.08. Подписано к печати 25.08.08.
Формат 60×84 1/16. Бумага офсетная. Печать офсетная.
Усл.-печ. л. 5,46. Уч.-изд. л. 6,38. Тираж 150 экз. Заказ №
Редакционно-издательский центр ГУАП
190000, Санкт-Петербург, Б. Морская ул., 67
Документ
Категория
Без категории
Просмотров
9
Размер файла
976 Кб
Теги
nikitin
1/--страниц
Пожаловаться на содержимое документа