- •Санкт-Петербургский государственный университет телекоммуникаций им.Проф. М.А. Бонч-Бруевича в.М. Охорзин
- •Санкт-Петербург
- •Тема 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
8.2.3. Древовидные диаграммы
Несмотря на то, что диаграммы состояний полностью описывают кодер, по сути, их нельзя использовать для легкого отслеживания переходов кодера в зависимости от времени, поскольку диаграмма не представляет динамики изменений. Древовидная диаграмма (tree diagram) прибавляет к диаграмме состояния временное измерение. Древовидная диаграмма сверточного кодера, показанного на рис. 8.3, изображена на рис. 8.6. В каждый последующий момент прохождения входного бита процедура кодирования может быть описана с помощью перемещения по диаграмме слева направо, причем каждая ветвь дерева описывает кодовое слово на выходе. Правило ветвления для нахождения последовательности кодовых слов следующее: если входным битом является нуль, то он связывается со словом, которое находится путем перемещения в следующую (по направлению вверх) правую ветвь; если входной бит — это единица, то кодовое слово находится путем перемещения в следующую (по направлению вниз) правую ветвь. Предполагается, что первоначально кодер содержал одни нули. Диаграмма показывает, что если первым входным битом был нуль, то кодовым словом ветви на выходе будет 00, а если первым входным битом была единица, то кодовым словом на выходе будет 11. Аналогично, если первым входным битом была единица, а вторым — нуль, на выходе вторым словом ветви будет 10. Если первым входным битом была единица и вторым входным битом была единица, вторым кодовым словом на выходе будет 01. Следуя этой процедуре, видим, что входная последовательность 1 1 0 1 1 представляется жирной линией, нарисованной на древовидной диаграмме (рис. 8.6). Этот путь соответствует выходной последовательности кодовых слов 1 1 0 1 0 1 0 0 0 1.
Добавленное измерение времени в древовидной диаграмме (по сравнению с диаграммой состояния) допускает динамическое описание кодера как функции конкретной входной последовательности. Однако заметили ли вы, что при попытке описания с помощью древовидной диаграммы последовательности произвольной длины возникает проблема? Число ответвлений растет как 2L, где L — это количество кодовых слов ветвей в последовательности. При большом L вы бы очень быстро исписали бумагу и исчерпали терпение.
8.2.4. Решетчатая диаграмма
Исследование древовидной диаграммы на рис. 8.6 показывает, что в этом примере после третьего ветвления в момент времени t4 структура повторяется (в общем случае древовидная структура повторяется после К ответвлений, где К — длина кодового ограничения). Пометим каждый узел в дереве (рис. 8.6), ставя в соответствие четыре возможных состояния в регистре сдвига: а = 00, b= 10, с = 01 и d = 11. Первое ветвление древовидной структуры в момент времени t1 дает пару узлов, помеченных как а и b . При каждом последующем ветвлении количество узлов удваивается. Второе ветвление в момент времени t2 дает в результате четыре узла, помеченных как а,b , с и d. После третьего ветвления всего имеется восемь узлов: два — а, два — b, два — с и два — d.
Можно видеть, что все ветви выходят из двух узлов одного и того же состояния, образуя идентичные ветви последовательностей кодовых слов. В этот момент дерево делится на идентичные верхнюю и нижнюю части. Смысл этого становится яснее после рассмотрения кодера, изображенного на рис. 8.3. Когда четвертый входной бит входит в кодер слева, первый входной бит справа выбрасывается и больше не влияет на кодовые слова на выходе. Следовательно, входные последовательности 1 0 0 x y... и 0 0 0 x y..., где крайний левый бит является самым ранним, после (К = 3)-го ветвления генерируют одинаковые кодовые слова ветвей. Это означает, что любые состояния, имеющие одинаковую метку в один и тот же момент ti можно соединить, поскольку все последующие пути будут неразличимы. Если мы проделаем это для древовидной структуры, показанной на рис. 8.6, получим иную диаграмму, называемую решетчатой.
Решетчатая диаграмма, которая использует повторяющуюся структуру, дает более удобное описание кодера, по сравнению с древовидной диаграммой. Решетчатая диаграмма для сверточного кодера,
изображенного на рис. 8.3, показана на рис. 8.7.
При изображении решетчатой диаграммы мы воспользовались теми же условными обозначениями, что и для диаграммы состояния: сплошная линия обозначает выходные данные, генерируемые входным нулевым битом, а пунктирная — выходные данные, генерируемые входным единичным битом. Узлы решетки представляют состояния кодера; первый ряд узлов соответствует состоянию а = 00, второй и последующие — состояниям b = 10, с = 01 и d - 11. В каждый момент времени для представления 2К-1 возможных состояний кодера решетка требует 2К-1 узлов. В нашем примере после достижения глубины решетки, равной трем (в момент времени t4), замечаем, что решетка имеет фиксированную периодическую структуру. В общем случае фиксированная структура реализуется после достижения глубины К. Следовательно, с этого момента в каждое состояние можно войти из любого из двух предыдущих состояний. Также из каждого состояния можно перейти в одно из двух состояний. Из двух исходящих ветвей одна соответствует нулевому входному биту, а другая — единичному входному биту. На рис. 8.7 кодовые слова на выходе соответствуют переходам между состояниями, показанными как метки на ветвях решетки.
Один столбец временного интервала сформировавшейся решетчатой структуры кодирования полностью определяет код. Несколько столбцов показаны исключительно для визуализации последовательности кодовых символов как функции времени. Состояние сверточного кодера представлено содержанием крайних правых К - 1 разрядов в регистре кодера. Некоторые авторы описывают состояние с помощью крайних левых К -1 разрядов. Какое описание правильно? Они оба верны. Каждый переход имеет начальное и конечное состояние. Крайние правые К - 1 разрядов описывают начальное состояние для текущих входных данных, которые находятся в крайнем левом разряде (степень кодирования предполагается равной 1/n). Крайние левые К – 1 разрядов являются конечным состоянием для такого перехода. Последовательность кодовых символов характеризуется N ветвями (что представляет N бит данных), занимающими N интервалов времени. Она связана с конкретным состоянием в каждый из N +1 интервалов времени (от начала до конца). Таким образом, мы запускаем биты в моменты времени t1 ,t2, ..., tN и интересуемся метрикой состояния в моменты времени t1 ,t2, ..., tN+1. Здесь использовано следующее условие: текущий бит располагается в крайнем левом разряде, а крайние правые К - 1 разрядов стартуют из состояния со всеми нулями. Этот момент времени обозначим как начальное время, t1. Время завершения последнего перехода обозначим как время прекращения работы, tN+1.