- •Санкт-Петербургский государственный университет телекоммуникаций им.Проф. М.А. Бонч-Бруевича в.М. Охорзин
- •Санкт-Петербург
- •Тема 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.3. Формулировка задачи сверточного декодирования
8.3.1. Алгоритм сверточного декодирования Витерби
В 1967 году Витерби разработал и проанализировал алгоритм, в котором, по сути, реализуется декодирование, основанное на принципе максимального правдоподобия; однако в нем уменьшается вычислительная нагрузка за счет использования особенностей структуры конкретной решетки кода. Преимущество декодирования Витерби заключается в том, что сложность декодера Витерби не является функцией количества символов в последовательности кодовых слов. Алгоритм включает в себя вычисление меры подобия (или расстояния), между сигналом, полученным в момент времени ti ,и всеми путями решетки, входящими в каждое состояние в момент времени ti. В алгоритме Витерби не рассматриваются те пути решетки, которые, согласно принципу максимального правдоподобия, заведомо не могут быть оптимальными. Если в одно и то же состояние входят два пути, выбирается тот, который имеет лучшую метрику; такой путь называется выживающим. Отбор выживающих путей выполняется для каждого состояния. Таким образом, декодер углубляется в решетку, принимая решения путем исключения менее вероятных путей. Предварительный отказ от маловероятных путей упрощает процесс декодирования. В 1969 году Омура (Omura) показал, что основу алгоритма Витерби составляет оценка максимума правдоподобия. Отметим, что задачу отбора оптимальных путей можно выразить как выбор кодового слова с максимальной метрикой правдоподобия или минимальной метрикой расстояния.
8.3.2. Пример сверточного декодирования Витерби
Пусть мы имеем дело с двоичным симметричным каналом BSC; приемлемая мера расстояния в этом случае есть расстояние Хэмминга. Кодер для этого примера показан на рис. 8.3, а решетчатая
диаграмма — на рис. 8.7. Для представления декодера, как показано на рис. 8.8, можно воспользоваться подобной решеткой. Мы начинаем в момент времени t1 в состоянии 00 (вследствие очистки кодера между сообщениями декодер находится в начальном состоянии). Поскольку в этом примере возможны только два перехода, разрешающих другое состояние, для начала не нужно показывать все ветви. Полная решетчатая структура образуется после момента времени t3. Принцип работы происходящего после процедуры декодирования можно понять, изучив решетку кодера на рис. 8.7 и решетку декодера, показанную на рис. 8.8. Для решетки декодера каждую ветвь за каждый временной интервал удобно пометить расстоянием Хэмминга между полученным кодовым символом и кодовым словом, соответствующим той же ветви из решетки кодера. На рис. 8.8 показана входная последовательность m, соответствующая ей последовательность кодовых слов U, и искаженная шумом последовательность Z = 11 01 01 10 01 ... . Как показано на рис. 8.7, кодер характеризуется кодовыми словами, находящимися на ветвях решетки кодера и заведомо известными как кодеру, так и декодеру. Эти слова являются кодовыми символами, которые можно было бы ожидать на выходе кодера в результате каждого перехода между состояниями. Пометки на ветвях решетки декодера накапливаются декодером в процессе. Другими словами, когда получен кодовый символ, каждая ветвь решетки декодера помечается метрикой подобия (расстоянием Хэмминга) между полученным кодовым символом и каждым словом ветви за этот временной интервал. Из полученной последовательности Z, показанной на рис. 8.8, можно видеть, что кодовые символы, полученные в (следующий) момент времени t1, — это 11. Чтобы пометить ветви декодера подходящей метрикой расстояния Хэмминга в (прошедший) момент времени t1, рассмотрим решетку кодера на рис. 8.7. Видим, что переход между состояниями 00 → 00 порождает на выходе ветви слово 00. Однако получено 11. Следовательно, на решетке декодера помечаем переход между состояниями 00 → 00 расстоянием Хэмминга между ними, а именно 2. Глядя вновь на решетку кодера, видим, что переход между состояниями 00 → 10 порождает на выходе кодовое слово 11, точно соответствующее полученному в момент t1 кодовому символу. Следовательно, переход на решетке декодера между состояниями 00 → 10 помечаем расстоянием Хэмминга 0. В итоге, метрика входящих в решетку декодера ветвей описывает разницу (расстояние) между тем, что было получено, и тем, что "могло бы быть" получено, имея кодовые слова, связанные с теми ветвями, с которых они были переданы. По сути, эти метрики описывают величину, подобную корреляциям между полученным кодовым словом и каждым из кандидатов на роль кодового слова. Таким же образом продолжаем помечать ветви решетки декодера по мере получения символов в каждый момент времени ti . В алгоритме декодирования эти метрики расстояния Хэмминга используются для нахождения наиболее вероятного (с минимальным расстоянием) пути через решетку. Смысл декодирования Витерби заключается в следующем. Если любые два пути сливаются в одном состоянии, то при поиске оптимального пути один из них всегда можно исключить. Например, на рис. 8.9 показано два пути, сливающихся в момент времени t5 в состоянии 00.
Давайте определим суммарную метрику пути по Хэммингу для данного пути в момент времени ti как сумму метрик расстояний Хэмминга ветвей, по которым проходит путь до момента ti. На рис. 8.9 верхний путь имеет метрику 4, нижний — метрику 1. Верхний путь нельзя выделить как оптимальный, поскольку нижний путь, входящий в то же состояние, имеет меньшую метрику. Это наблюдение
поддерживается Марковской природой состояний кодера. Настоящее состояние завершает историю кодера в том смысле, что предыдущие состояния не могут повлиять на будущие состояния или будущие ветви на выходе.
В каждый момент времени ti в решетке существует 2К-1 состояний, где К — это длина кодового ограничения, и в каждое состояние может войти два пути. Декодирование Витерби состоит в вычислении метрики двух путей, входящих в каждое состояние, и исключении одного из них. Такие вычисления проводятся для каждого из 2K-1 состояний или узлов в момент времени ti ; затем декодер переходит к моменту времени ti+1 , и процесс повторяется. В данный момент времени метрика выжившего пути для каждого состояния обозначается как метрика для этого состояния в этот момент времени. Первые несколько шагов в нашем примере декодирования будут следующими (рис. 8.10). Предположим, что последовательность входных данных m, кодовое слово U и полученная последовательность Z аналогичны показанным на рис. 8.8. Допустим, что декодер знает верное исходное состояние решетки. (Это предположение не является необходимым, однако упрощает объяснения.) В момент времени t1 получены кодовые символы 11. Из состояния 00 можно перейти только в состояние 00 или 10, как показано на рис. 8.10, а. Переход между состояниями 00 → 10 имеет метрику ветви 0; переход между состояниями 00 → 00 — метрику ветви 2. В момент времени t2 из каждого состояния также может выходить только две ветви, как показано на рис. 8.10, б. Суммарная метрика этих ветвей обозначена как метрика состояний Гa, Гb, Гc и Гd, соответствующих конечным состояниям. В момент времени t3 на рис. 8.10, в опять есть две ветви, выходящие из каждого состояния. В результате имеется два пути, входящих в каждое состояние, в момент времени t4.. Один из путей, входящих в каждое состояние, может быть исключен, а точнее — это путь, имеющий большую суммарную метрику пути. Если бы метрики двух входящих путей имели одинаковое значение, то путь, который будет исключаться, выбирался бы произвольно. Выживший путь в каждом состоянии показан на рис. 8.10, г. В этой точке процесса декодирования имеется только один выживший путь, который называется полной ветвью, между моментами времени t1 и t2. Следовательно, декодер теперь может решить, что между моментами t1 и t2 произошел переход 00 → 10. Поскольку переход вызывается единичным входным битом, на выходе декодера первым битом будет единица. Здесь легко можно проследить процесс декодирования выживших ветвей, поскольку ветви решетки показаны пунктирными линиями для входных единиц и сплошной линией для входных нулей. Заметим, что первый бит не декодируется, пока вычисление метрики пути не пройдет далее вглубь решетки. Для обычного декодера такая задержка декодирования может оказаться раз в пять больше длины кодового ограничения в битах.На каждом следующем шаге процесса декодирования всегда будет два пути для каждого состояния; после сравнения метрик путей один из них будет исключен. Этот шаг в процессе декодирования показан на рис. 8.10, д.
В момент t5 снова имеется по два входных пути для каждого состояния, и один путь из каждой пары подлежит исключению. Выжившие пути на момент t5 показаны на рис. 8.10, е. Заметим, что в нашем примере мы еще не можем принять решения относительно второго входного информационного бита, поскольку еще остается два пути, исходящих в момент t2 из состояния в узле 10.
. В момент времени t6 на рис. 8.10, ж снова можем видеть структуру сливающихся путей, а на рис. 8.10, з — выжившие пути на момент t6.
. Здесь же, на рис. 8.10, з, на выходе декодера в качестве второго декодированного бита показана единица как итог единственного оставшегося пути между точками t2 и t3. Аналогичным образом декодер продолжает углубляться в решетку и принимать решения, касающиеся информационных битов, устраняя все пути, кроме одного.
Отсекание (сходящихся путей) в решетке гарантирует, что у нас никогда не будет путей больше, чем состояний. В этом примере можно проверить, что после каждого отсекания (рис. 8.10, б— д) остается только 4 пути. Сравните это с попыткой декодирования без алгоритма Витерби при использовании принципа максимального правдоподобия по древовидной диаграмме. В этом случае число возможных путей (соответствующее возможным вариантам последовательности) является степенной функцией
длины последовательности. Для двоичной последовательности кодовых слов с длиной кодовых слов L имеется 2L возможные последовательности.
В контексте решетчатой диаграммы, показанной на рис. 8.8, переходы за один промежуток времени можно сгруппировать в 2v-1 непересекающиеся ячейки; каждая ячейка будет изображать четыре возможных перехода, причем v = K- 1 называется памятью кодера (encoder memory). Если К = 3, то v = 2, и, следовательно, мы имеем 2v-1 = 2 ячейки. Эти ячейки показаны на рис. 8.11, где буквы а, b, с и d обозначают состояния в момент ti а а', b', с' и d’ — состояния в момент времени ti+1. Для каждого перехода изображена метрика ветви δxy, индексы которой означают переход из состояния х в состояние у. Эти ячейки и соответствующие логические элементы, которые корректируют метрики состояний {Гх}, где х означает конкретное расстояние состояния, представляют основные составляющие элементы декодера.