- •Санкт-Петербургский государственный университет телекоммуникаций им.Проф. М.А. Бонч-Бруевича в.М. Охорзин
- •Санкт-Петербург
- •Тема 1. Основные понятия и определения в области пдс
- •1.1.Дискретность
- •Соответствующие виды сигналов:
- •1.2.Модуляция
- •1.3.Кодирование
- •1.4.Упрощенная структурная схема аппаратуры пдс.
- •Модулятор – устройство, осуществляющее модуляцию. Демодулятор осуществляет обратное преобразование. Совокупность модулятора и демодулятора образует модем.
- •1.5. Основные параметры и характеристики системы пдс
- •Тема 2. Системные характеристики систем передачи дискретных сообщений 2.1 Понятие об эталонной модели взаимодействия открытых систем
- •2.2. Понятие о телеуслугах
- •2.3 Первичные коды в системах пдс
- •2.3.1. Телеграфные коды
- •2.3.2. Коды для передачи данных
- •Тема 3. Основные характеристики уровня дискретногоканаласистем пдс
- •3.1. Понятие об искажениях дискретных сигналов
- •3.1.1. Классификация искажений
- •3.1.2.Характеристические краевые искажения
- •3.1.3 Краевые искажения типа преобладаний
- •3.1.4.Случайные искажения
- •3.2.Понятие о методах регистрации дискретных сигналов
- •3.2.1.Метод стробирования
- •3.2.2. Интегральный метод
- •Интегрирование в промежутке, меньшем длительности элементарной посылки
- •3.3 Оценка эффективности методов регистрации
- •3.3.1.Распределение краевых искажений
- •3.3.2. Распределение дроблений
- •3.3.3. Расчет вероятности ошибки при краевых искажениях
- •3.3.4.Расчет вероятности ошибки при дроблениях
- •3.4.Модели дискретных каналов
- •3.4.1.Поток ошибок в дискретном канале
- •3.4.2.Методы выявления и исследования последовательностей ошибок
- •3.4.3 Основные закономерности распределения ошибок в реальных каналах связи
- •3.4.4 Математические модели дискретных каналов с группированием ошибок
- •А. Модель неоднородного канала.
- •Б. Двухпараметрическая модель дискретного канала
- •Тема 4. Устройство синхронизации по элементам (усп).
- •4.1.Назначение и классификация
- •Основные элементы устройства , реализующего фапч:
- •4.2. Необходимость поэлементной синхронизации . Расчет времени удержания синхронизма.
- •4.3.Схема фапч с дискретным управлением.
- •4.4.Основные характеристики системы фапч.
- •Тема 5. Линейные (n,k)-коды
- •5.1. Определение помехоустойчивых кодов и их общие характеристики
- •5.1.1. Принципы построения помехоустойчивых кодов
- •5.1.2. Основные характеристики помехоустойчивых кодов
- •5.1.3 Классификация помехоустойчивых кодов
- •5.1.4.Граничные соотношения между характеристиками помехоустойчивых кодов
- •5.1.5.Задачи
- •5.2. Групповые коды и способы их описания
- •5.2.1. Основные алгебраические системы, используемые в теории кодирования
- •5.2.2. Способы представления кодовых комбинаций
- •5.2.3. Определение группового кода
- •5.2.4. Матричное описание групповых кодов
- •5.2.5. Задачи
- •5.3. Другие свойства групповых кодов
- •5.3.1. Корректирующие свойства групповых кодов
- •5.3.2. Процедуры кодирования и декодирования для группового кода
- •5.3.3. Укорочение кода
- •5.3.4. Оценка эффективности групповых кодов
- •5.3.5. Смежно-групповые коды
- •5.3.6. Задачи
- •5.4. Примеры групповых кодов
- •5.4.1. Коды с единственной проверкой на четность
- •5.4.2. Коды Хэмминга
- •5.4.3. Итеративные коды.
- •5.4.4 Задачи
- •Тема 6. Двоичные циклические (n,k) - коды
- •6.1. Основные алгебраические системы, используемые в теории кодирования.
- •6.2. Определение циклического кода
- •6.3. Построение порождающей и проверочной матриц циклических кодов.
- •6.4. Коды Боуза-Чоудхури-Хоквингема (бчх).
- •6.5. Выбор порождающего многочлена для кода бчх
- •6.6. Эффективность двоичных кодов бчх
- •6.6.1. Задачи
- •6.7. Кодирующие и декодирующие устройства циклических кодов
- •6.7.1 Процедура кодирования и декодирования для циклических кодов
- •6.7.2. Линейные переключательные схемы, используемые в кодирующих и декодирующих устройствах циклических кодов
- •6.7.3. Схемы кодирующих устройств циклических кодов
- •6.7.4. Декодирующие устройства циклических кодов
- •6.7.5. Задачи
- •Тема 7. Коды Рида- Соломона (рс)
- •7.1. Определение и основные свойства
- •Пример 7.1
- •Пример 7.2
- •7.1.1. Расширенные рс-коды
- •Пример 7.3
- •7.1.2. Укороченные рс-коды
- •7.1.3. Отображение рс-кодов над gf(2m) на двоичные коды
- •7.1.4. Способы кодирования и декодирования рс-кодов
- •1. Многочлен локаторов ошибок:
- •2.Синдромный многочлен
- •3. Многочлен значений ошибок
- •7.2. Быстрое декодирование кодов бчх
- •7.2.1. Ключевое уравнение
- •7.2.2. Решение ключевого уравнения
- •7.2.3. Примеры решения ключевого уравнения
- •7.3.Кодирование на основе решения ключевого уравнения
- •7.4.Задачи
- •Тема 8. Непрерывные коды
- •8.1. Сверточное кодирование
- •8.2. Представление сверточного кодера
- •8.2.1. Представление связи
- •8.2.1.1. Реакция кодера на импульсное возмущение
- •8.2.1.2. Полиномиальное представление
- •8.2.2. Представление состояния и диаграмма состояний
- •8.2.3. Древовидные диаграммы
- •8.2.4. Решетчатая диаграмма
- •8.3. Формулировка задачи сверточного декодирования
- •8.3.1. Алгоритм сверточного декодирования Витерби
- •8.3.2. Пример сверточного декодирования Витерби
- •8.4. Декодирование с мягким решением
- •8.4.1. Модель канала с абгш
- •2.1.2. Передача двоичных сигналов по каналам с абгш
- •2.1.3. Алгоритм Витерби с Евклидовой метрикой
- •8.5. Связь с блоковыми кодами
- •8.5.1. Терминированная конструкция (нулевой хвост)
- •8.5.2. Усеченная конструкция (direct truncation)
- •8.5.3. Кольцевая (циклическая или циклически замкнутая) (tail-biting) конструкция
- •8.5.4. Распределение весов
- •8.6. Модифицированный граф состояний
- •8.7. Решение задач
- •8.7.1. Задачи
- •8.7.2. Решение
- •8.3.2.1. Процедура сложения, сравнения и выбора
- •8.3.2.2. Вид процедуры сложения, сравнения и выбора на решетке
- •8.3.3. Память путей и синхронизация
- •8.4. Свойства сверточных кодов
- •8.4.1. Пространственные характеристики сверточных кодов
- •8.4.1.1. Возможности сверточного кода в коррекции ошибок
- •8.4.2. Систематические и несистематические сверточные коды
- •8.4.3. Распространение катастрофических ошибок в сверточных кодах
- •8.4.4. Границы рабочих характеристик сверточных кодов
- •8.4.5. Эффективность кодирования
- •8.4.6. Наиболее известные сверточные коды
- •8.5. Задачи
- •Тема 9. Некоторые специальные классы кодов. Составные коды
- •9.1. Коды для исправления пачек ошибок
- •9.2. Коды на основе последовательностей максимальной длины
- •9.3. Коды для асимметричных каналов
- •9.3.1. Коды с постоянным весом
- •9.3.2. Коды Бергера
- •9.4 Каскадные коды
- •9.4.1. Принципы построения каскадных кодов
- •9.4.2. Режимы использования каскадных кодов
- •9.4.3. Построение двоичных каскадных кодов на основе кодов Рида–Соломона и Боуза–Чоудхури–Хоквингема
- •Пример 9.2.
- •Пример 9.3.
- •9.5. Задачи
- •Тема 10. Цикловая синхронизация
- •10.1 Назначение и классификация способов цикловой синхронизации
- •10.2. Способ установки фазы приемного распределителя путем сдвига.
- •10.3. Способ мгновенной установки фазы
- •10.3.1. Маркерный способ цикловой синхронизации на основе синхронизирующих кодовых последовательностей
- •10.4 . Способ выделения сигнала фазового запуска по зачетному отрезку
- •Тема 11. Системные методы защиты от ошибок без обратной связи
- •11.1. Классификация и основные характеристики систем повышения достоверности
- •11.1.1. Теоретические основы системных методов защиты от ошибок
- •11.1.2. Классификация системных методов защиты от ошибок
- •11.1.3 .Основные параметры и характеристики систем повышения достоверности
- •11.2. Методы повышения достоверности в однонаправленных системах
- •11.2.1.Однонаправленные системы с многократным повторением сообщений
- •11.2.2.Однонаправленные системы с исправляющим ошибки кодом
- •11.2.3.Однонаправленные системы с исправлением стираний
- •11.3. Задачи
- •Тема 12. Системные методы защиты от ошибок с обратной связью
- •12.1. Системы повышения достоверности с решающей обратной связью с непрерывной последовательной передачей сообщений и блокировкой (рос-пПбл).Общие положения
- •12.2. Описание работы системы рос-пПбл
- •12.3. Режим переспроса
- •12.4. Расчет параметров системы рос-пПбл Относительная скорость передачи
- •Расчет вероятности ошибок на выходе системы
- •12.5. Рекомендации по выбору оптимального кода
- •Охарактеризуем поток ошибок, пропущенных в приемник сообщений средней вероятностью ошибки на бит, равной и показателем группирования ошибок.
- •12.6. Выбор порождающего многочлена
- •12.7. Задачи
- •Приложение 1. Коды бчх
- •Приложение 4
- •Список использованных источников
- •Предметный указатель
- •Тема 1. Основные понятия и определения в области пдс………………..……....2
- •Тема 2. Системные характеристики систем передачи дискретных сообще……...11
- •Тема 3. Основные характеристики уровня дискретного канала пдс…………………21
- •Тема 4. Устройство синхронизации по элементам (усп)…………………………...50
- •Тема 5. Линейные (n,k)-коды…….………………………………………………………..54
- •Тема 6. Двоичные циклические (n,k) – коды…………………………………… …….105
- •Тема 7. Коды Рида- Соломона (рс)…………………………………………..………..165
- •7.1.3. Отображение рс-кодов над gf(2m) на двоичные коды…………………….170
- •Тема 8. Непрерывные коды……………………………………………..………………..185
- •Тема 9. Некоторые специальные классы кодов. Составные коды………………..……210
- •9.4.1. Принципы построения каскадных кодов…………………………………………………215
- •9.4.2. Режимы использования каскадных кодов……………………………………………….218
- •9.4.3. Построение двоичных каскадных кодов на основе кодов Рида–Соломона и Боуза–Чоудхури–Хоквингема………………..……………………………………………….…219
- •Тема 11. Системные методы защиты от ошибок без обратной связи………………..……234
- •Тема 12. Системные методы защиты от ошибок с обратной связью…..…………….244
6.7.4. Декодирующие устройства циклических кодов
а) Обнаружение ошибок
Рассмотрим способ построения декодирующих устройств для циклических кодов в режиме обнаружения ошибок. Декодирующее устройство, использующее свойство делимости любой комбинации циклического кода на его порождающий многочлен g(x), показано на рис. 6.14.
Кодовая комбинация после регистрирующего устройства последовательно вводится в схему деления на g(x), и одновременно информационные элементы этой принятой комбинации записываются в накопитель информационных разрядов. После ввода последнего элемента кодовой комбинации в схему деления разряды регистра сдвига этой схемы будут содержать остаток от деления принятой комбинации наg(x).
В случае, когда остаток чисто нулевой, комбинация считается принятой верно, если же остаток не равен нулю, то фиксируется ошибка. С целью принятия решения о наличии или отсутствии ошибок в комбинации содержимое разрядов регистра после завершения деления вводится в схему ИЛИ.
Если ошибки отсутствуют (или не обнаружены), то на выходе схемы получаем сигнал “0”, по которому информация из накопителя информационных разрядов выдается потребителю информации. В том случае, когда на выходе схемы ИЛИ появляется сигнал “1”, а это произойдет, когда хотя бы в одном из разрядов регистра после деления появится “1”, т.е. полученный остаток не равен нулю, информационные разряды из накопителя потребителю не выдаются и фиксируется ошибка.
Пример 6.18.Построить декодирующее устройство для обнаружения ошибок циклическим (7,4) – кодом си проследить по тактам процесс выявления ошибок.
Схема декодирующего устройства для данного кода изображена на рисунке 6.15.
Пусть приемное устройство зарегистрировало комбинацию (1100101). Состояние элементов схемы деления при поступлении на ее вход данной комбинации отражено в таблице 6.6.
Таблица 6.6
-
№ такта
Вход
Содержимое разрядов
Цепь обратной связи
0
1
2
3
4
5
6
7
-
1
0
1
0
0
1
1
0
1
0
1
1
0
1
0
0
0
1
0
0
1
0
0
0
0
0
1
0
0
1
0
0
0
0
0
1
0
0
1
Таким образом, в результате деления установлено, что принятая комбинация принадлежит циклическому (7,4) – коду и ее информационные элементы поступают к потребителю информации.
Предположим теперь, что в процессе передачи исказился первый элемент комбинации и принятая комбинация имеет вид (1100100). Процесс деления приведен в таблице 6.7.
Таблица 6.7
-
№ такта
Вход
Содержимое разрядов
1
2
3
4
5
6
7
0
0
1
0
0
1
1
0
0
1
0
0
0
1
0
0
0
1
0
1
0
0
0
0
0
1
0
1
В результате деления принятой комбинации на получен остаток 101, вследствие чего на выходе схемы ИЛИ появится “1”, запрещающая выдачу кодовой комбинации потребителю.
В ряде случаев может оказаться целесообразным построение декодирующего устройства на основе схемы для решения рекуррентных соотношений (рис. 6.7).
В этом случае процедура обнаружения ошибок строится следующим образом. По принятым информационным разрядам кодовой комбинации восстанавливаются избыточные элементы принимаемой кодовой комбинации и сравниваются с избыточными элементами, поступающими из канала. Если нет отличия в принимаемых и восстановленных избыточных элементах, то кодовая комбинация считается принятой верно. Если же восстановленные избыточные элементы отличаются от принятых, то фиксируется факт обнаружения ошибки.
Структурная схема устройства обнаружения ошибок, реализующая описанную процедуру, представлена на рис. 6.16.
Информационные разряды принятой кодовой комбинации циклического (n, k) – кода через схемуИ1, открытую на время приемаkинформационных элементов, вводятся в регистр изkразрядов. После приемаk-го разряда в схеме происходит сдвиг информации вправо, и по (k+1)-му такту в ячейкеоказывается записанным старший избыточный разряд. Сформированный избыточный разряд поступает из ячейкина вход сумматора по модулю 2. В то же самое время со входа схемы на второй вход сумматора поступает старший избыточный разряд от входа схемы. Начиная с (k+1)-го такта открывается выход сумматора через схемуИ2и определяется сумма по модулю 2 сравниваемых избыточных символов. “1” на выходе сумматора означает ошибку, “0” – правильный прием. По (k+2)-му такту вформируется следующий избыточный символ. Соответствующий избыточный символ в этот же момент поступает от входа схемы и т.д. Сумматор выдает решение по каждому избыточному разряду. Общее время работы схемы, необходимое для выявления ошибок в принимаемой комбинации, не выходит за пределы времени приема комбинации.
На рис. 6.17 для сравнения приведены устройства обнаружения ошибок для циклического кода (7,3), построенные по h(x) (Рис 6.17а) и поg(x) (Рис 6.17б)
б) Исправление ошибок
Исправление ошибок циклическим кодом – задача достаточно сложная как в теоретическом, так и в практическом, т.е. схемном отношении.
Существует несколько методов исправления ошибок для циклических кодов. В настоящем параграфе рассмотрим один из них, базирующийся на схемах, который были описаны выше.
Подробно будет рассмотрен способ исправления однократных ошибок. На рисунке 6.18 показана структурная схема декодирующего устройства, предназначенная для исправления ошибок произвольной кратности в комбинации циклического кода.
В общих чертах работа этой схемы может быть описана следующим образом:
Принятая кодовая комбинация вводится в буферное запоминающее устройство (БЗУ) и одновременно в схему вычисления синдрома (СВС), СВС аналогична схеме, изображенной на рис.6.4.
Между синдромом и предполагаемой комбинацией ошибок (образующий элемент смежного класса) имеется взаимно однозначное соответствие, определяемое комбинаторной логической схемой (КЛС). КЛС строится таким образом, чтобы на ее выходе появилась 1 всякий раз, когда при выводе информации из БЗУ предполагается появление ошибочного элемента, т.е. 1 на выходе КЛС должна всегда соответствовать старшей степени многочлена ошибок e(x)содержащегося в той части кодовой комбинации, которая еще содержится в БЗУ.
Одновременно с появлением из БЗУ каждого элемента производится сдвиг в СВС. Если символ, появляющийся на выходе БЗУ подлежит исправлению, то синдром также должен быть изменен, для чего с выхода КЛС 1 подается как на выход БЗУ, так и на вход СВС. Это делается для того, чтобы синдром соответствовал каждому изменению принятой комбинации.
Второй и третий шаги повторяются до тех пор, пока вся принятая комбинация не будет считана из БЗУ. Каждому разряду, считываемому из БЗУ, должен соответствовать сдвиг на один разряд вправо одновременно в БЗУ и в КЛС.
После того, как считана вся принятая комбинация, будут исправлены все ошибки, соответствующие образцам ошибок, предусмотренным КЛС, и в разрядах регистра СВС останутся одни нули. Если после окончания процедуры исправления в разрядах регистра содержатся не только нули, то это значит, что обнаружена ошибка, не исправляемая с помощью данной КЛС.
Поясним подробнее работу данной схемы на примере исправления однократных ошибок.
В этом случае КЛС должна выдавать 1 тогда, когда из БЗУ выходит элемент, в котором предполагается ошибка. С этой целью каждый синдром должен быть однозначно связан с номером элемента кодовой комбинации. Эта связь может быть установлена следующим образом. Принятая комбинация вводится в схему деления на порождающий многочлен и вычисляется остаток от деления данной комбинации на g(x), являющийся синдромом. Как было показано при рассмотрении исправления ошибок кодом Хэмминга, вычисленный синдром имеет такой же вид, как и столбец проверочной матрицы кода, соответствующий искаженному элементу принятой кодовой комбинации Пусть ошибка произошла вi– ом разряде кодовой комбинации.
В соответствии с правилом построения матрицы проверок синдром соответствует остатку от делениянаg(x). Рассмотрим теперь, что будет происходить в схеме деления наg(x), если после вычисления синдрома продолжать сдвиги в регистре. Если от входа схемы исправления на схему деления никакой информации не поступает, а в регистре схемы деления записан остаток от делениянаg(x), в результате сдвига содержимого регистра на единицу вправо с учетом работы обратных связей получим в регистре остаток от делениянаg(x). Следующий сдвиг дает остаток от делениянаg(x)и т.д. Таким образом, схема деления на многочленg(x) после вычисления синдрома начинает работать как генератор элементов поляGF(2m), гдеm=n-k- степень порождающего многочленаg(x). Начальным состоянием работы генератора является вычисленный синдром, т.е. αi. После (n-i) – го сдвига в регистре будет записан остаток от делениянаg(x), который для равен единичному элементу по операции умножения поляGF(2m).Итак, при наличии в принятой комбинации единичной ошибки в любомi– ом разряде после дополнительных (n-i) сдвигов в схеме деления будем иметь в ячейкеединицу, а во всех остальных ячейках – нули.
Автоматическое исправление ошибки можно осуществить следующим образом. К разрядам регистра сдвига подключается дешифратор на комбинацию вида 100…0. Выход дешифратора и выход БЗУ подключается ко входам сумматора по модулю 2.
Одновременно со сдвигами в схеме деления после вычисления синдрома осуществляется вывод информации из БЗУ. На (n-i)-м сдвиге на входы сумматора поступят от БЗУ искаженный элемент, а от дешифратора - единица. На выходе сумматора искаженный элемент инвертируется, т.е. ошибка будет исправлена.
Пример 6.19. Рассмотрим исправление ошибок циклическим (7,4) - кодом с. Этот код имеетdmin = 3, т.е. исправляет все одиночные ошибки. Общий вид схемы исправления одиночных ошибок для данного кода представлен на рис. 6.19.
Поясним работу схемы при исправлении одиночных ошибок на примере. Пусть приемное устройство зарегистрировало комбинацию 1101101. Данная комбинация поступает в СВС и БЗУ. После 7-го такта СВС содержит синдром , что свидетельствует о том, что искажен элемент при(см. пример 6.15). С 8-го такта комбинация выводится из БЗУ, начиная со старшей степени. Одновременно в СВС происходят сдвиги синдрома.
Этот процесс представлен в таблице 6.8.
Таблица 6.8
№ такта |
Состояние СВС |
Выход БЗУ |
Выход КЛС |
Выход схемы | ||
r0 |
r1 |
r2 | ||||
7 |
1 |
1 |
0 |
- |
0 |
- |
8 |
0 |
1 |
1 |
1 |
0 |
1 |
9 |
1 |
1 |
1 |
0 |
0 |
0 |
10 |
1 |
0 |
1 |
1 |
0 |
1 |
11 |
1 |
0 |
0 |
1 |
1 |
0 |
12 |
0 |
0 |
0 |
0 |
0 |
0 |
13 |
0 |
0 |
0 |
1 |
0 |
1 |
14 |
0 |
0 |
0 |
1 |
0 |
1 |
Сравните состояние ячеек СВС с состоянием ячеек генератора элементов поля GF(23), начиная с 3 такта (рис 6.9).
Таким образом, исправленная комбинация имеет вид 1100101. С выхода схемы проверочные элементы могут не выдаваться к потребителю, т.е. вся процедура может быть окончена после выдачи последнего информационного элемента.
В теме 7 будут изложены методы кодирования и декодирования для циклических кодов, известные как быстрое декодирование кодов БЧХ.