- •Санкт-Петербургский государственный университет телекоммуникаций им.Проф. М.А. Бонч-Бруевича в.М. Охорзин
- •Санкт-Петербург
- •Тема 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
5.2.4. Матричное описание групповых кодов
Отождествление кодовых комбинаций групповых кодов с векторами позволяет упростить их задание и описание.
Известно, что векторное пространство однозначно определяется своим базисом. Поэтому естественно стремление использовать базис векторного пространства для описания (n, k) – кода, соответствующего данному векторному пространству. Используя понятие базиса, можно утверждать, что для описания (n, k) – кода достаточно использоватьkлинейно независимых кодовых комбинаций, т.е. справедливо следующее:
Свойство 5.2. Групповой (n, k) – код полностью определяется набором из k линейно независимых комбинаций, принадлежащих этому коду.
Обычно эти kлинейно независимые комбинации записывают в виде прямоугольной таблицы - матрицы, имеющейkстрок иnстолбцов, где строками являются кодовые комбинации.
По аналогии с векторным пространством все остальные кодовые комбинации могут быть получены путем линейной комбинации строк построенной матрицы. В связи с этим указанную прямоугольную матрицу принято называть порождающей матрицей группового кода.
Для порождающей матрицы будем использовать обозначение G(n, k). Размерность порождающей матрицы (k n).
Пример 5.5.Построим (5, 3) – код. Такой код должен иметькодовых комбинаций. В качестве информационной части используем всевозможные двоичные последовательности длины три. Условимся первые два разряда в кодовой комбинацииотводить под избыточные элементы; а три последние под информационные. Пусть проверочные элементы формируются как сумма по модулю 2 определенных информационных элементов:.
Используя такой принцип построения кодовой комбинации (5, 3) – кода, получаем все его комбинации в следующем виде:
-
Простой код
(5, 3) –код
Вес кодовой комбинации
1
001
01001
2
2
010
11010
3
3
011
10011
3
4
100
10100
2
5
101
11101
4
6
110
01110
3
7
111
00111
3
8
000
00000
0
Анализируя веса кодовых комбинаций, приходим к выводу, что минимальное кодовое расстояние в данном коде равно 2.
В этом можно убедиться, построив таблицу кодовых расстояний для данного кода:
|
00000 |
01001 |
11010 |
10011 |
10100 |
11101 |
01110 |
00111 |
00000 |
0 |
2 |
3 |
3 |
2 |
4 |
3 |
3 |
01001 |
2 |
0 |
3 |
3 |
4 |
2 |
3 |
3 |
11010 |
3 |
3 |
0 |
2 |
3 |
3 |
2 |
4 |
10011 |
3 |
3 |
2 |
0 |
3 |
3 |
4 |
2 |
10100 |
2 |
4 |
3 |
3 |
0 |
2 |
3 |
3 |
11101 |
4 |
2 |
3 |
3 |
2 |
0 |
3 |
3 |
01110 |
3 |
3 |
2 |
4 |
3 |
3 |
0 |
2 |
00111 |
3 |
3 |
4 |
2 |
3 |
3 |
2 |
0 |
Можно указать несколько троек линейно-независимых комбинаций этого кода. Например:
4. 10100 4. 10100 4. 10100
2. 11010 5. 11101 6. 01110
1. 01001 6. 01110 7. 00111
и так далее.
Каждый из этих наборов комбинаций может служить порождающей матрицей данного (5, 3) – кода.
Предположим, что в качестве порождающей матрицы данного кода (5, 3) выбраны кодовые комбинации
Покажем, что все кодовые комбинации могут быть получены как линейные комбинации базисных векторов, т.е. строк порождающей матрицы:
00000=0(10100)+0(11010)+0(01001),
01001=0(10100)+0(11010)+1(01001),
11010=0(10100)+1(11010)+0(01001),
10011=0(10100)+1(11010)+1(01001),
10100=1(10100)+0(11010)+0(01001),
11101=1(10100)+0(11010)+1(01001),
01110=1(10100)+1(11010)+0(01001),
00111=1(10100)+1(11010)+1(01001).
Аналогично можно показать, что любой другой набор линейно-независимых комбинаций порождает тот же самый код.
Преимущество матричного описания кодов очевидно по сравнению с перечислением всех кодовых комбинаций. Действительно, если (n, k) – код содержит 2kкомбинаций, то для его задания требуется всего лишьkкодовых комбинаций.
Представляет интерес определить число возможных порождающих матриц для групповых кодов с параметрами nиk. Для этого подсчитаем сколькими способами можно набратьkлинейно независимых строк порождающей матрицы из 2k– 1 кодовых комбинаций (чисто нулевая кодовая комбинация, естественно, исключается). В качестве первой строки может быть выбрана любая из 2k– 1 кодовых комбинаций (т.е. 2k– 1 способов). Так как среди кодовых комбинаций нет повторяющихся, то в качестве второй строки можно выбрать любую их оставшихся 2k– 2 комбинаций (2k– 2 способов). При выборе третьей строки следует исключить из рассмотренных, кроме двух записанных строк, их сумму, т.е. третья строка может быть выбрана 2k– 22способами. Рассуждая аналогично, находим, что при выбореi– той строки следует исключить из рассмотрения все линейные комбинации (i- 1) предшествующих строк, т.е. 2i – 1комбинаций.
Общее же число наборов kлинейно независимых комбинаций из множества 2kкодовых комбинаций составит число
Для группового кода (5,3) полное число возможных порождающих матриц оказывается равным
Столь большое число возможных порождающих матриц для (n, k) - кода затрудняет их использование для задания кода.
Для однозначности задания кода порождающей матрицей вводят понятие о канонической форме порождающей матрицы.
Каноническая форма порождающей матрицы имеет следующий вид:
,
где Ik– единичная матрица размерности (k k), то есть такая квадратная матрица, у которой на главной диагонали находятся единицы, а все остальные элементы – нули.Ikсодержит информационные элементы кодовых комбинаций, образующих порождающую матрицу.- матрица размерности, составленная из проверочных элементов базисных кодовых комбинаций.
Для рассмотренного выше кода (5, 3) каноническая форма порождающей матрицы имеет вид:
В линейной комбинации строк порождающей матрицы примера 5.5. скаляры при строках в своей совокупности повторяют информационную часть отыскиваемой кодовой комбинации. Из этого вытекает важный вывод: для получения кодовой комбинации (n,k)-кода по ее информационной части необходимо умножить последовательность длиныk,являющейся информационной частью кодовой комбинации, на порождающую матрицу этого кода в канонической форме по правилам умножения матриц:
( k- последовательность)×G(n,k)=[комбинация (n,k)-кода].
Матрица может быть преобразована к канонической форме при любом исходном наборе базисных кодовых комбинаций посредством элементарных операций над строками матрицы, которые включают:
перестановку любых двух строк;
умножение любой строки на скаляр;
прибавление произведения одной из строк матрицы на скаляр к другой строке матрицы;
Порождающая матрица (n, k) – кода в канонической форме задает тот же самый код, что и исходная порождающая матрица, т.к. пространства строк этих матриц совпадают в силу выполнения свойства замкнутости.
Пример 5.6.Рассмотрим процедуру приведения матрицыG(5, 3)кода предыдущего примера к канонической форме.
Первая строка матрицы соответствует канонической форме, а вторая и третья должны быть преобразованы. Прибавим ко второй строке первую и результат запишем во второй строке матрицы:
Затем прибавим к третьей строке вторую, а результат запишем в третьей строке
Итак, каноническая форма матрицы кода (5, 3) имеет уже известный вид.
Следует отметить, что если элементарные операции над строками порождающей матрицы в результате дают в точности тот же самый код, то применение элементарных операций к столбцам матрицы приводит к новому коду, корректирующие свойства которого могут отличаться от свойств исходного кода. Только лишь перестановка столбцов не изменяет весов кодовых комбинаций, а в некоторых случаях и их вида. Поэтому (n, k) – коды, полученные из матрицынекоторого (n, k) – кода перестановкой столбцов этой матрицы, называютэквивалентными.Таким образом, перестановка столбцов порождающей матрицы (n, k) – кода дает порождающую матрицу для эквивалентного кода (n, k) – кода.
Заметим, что единичная матрица Ikв канонической форме порождающей матрицы может находиться либо перед матрицейпроверочных элементов, либо после нее в зависимости от того, где в кодовой комбинации располагаются информационные элементы – в начале или конце комбинации. Понятие об эквивалентности кодов позволяет находить каноническую форму порождающей матрицы неразделимого группового кода.
Широкое применение нашел также и другой способ матричного описания кодов. Сущность его сводится к следующему. Если записать правило формирования каждого их проверочных соотношений кодовой комбинации в виде вектора из нулей и единиц, где единицы указывают, какие элементы кодовой комбинации охвачены проверкой на четность, то получим n-kвекторов. Такие векторы получили названиепроверочных. Так как каждый проверочный вектор отражает проверку на четность, введенную для любой кодовой комбинации, то справедливо следующее.
Свойство 5.3. Скалярное произведение любой кодовой комбинации на проверочный вектор равно нулю.
Действительно, обозначим проверочный вектор через , а кодовую комбинацию через, тогда их скалярное произведение равно. Сумма берется по всем слагаемым, в которых, т.е. сводится к сумме элементов кодовой комбинации, охваченных проверкой на четность, а потому эта сумма должны дать 0. Записывая проверочные вектора в прямоугольную таблицу, получимпроверочную матрицу кода, обозначаемуюH(n, k)и имеющую размерность. Единицы на позициях, соответствующих информационным элементам в кодовой комбинации, указывают, какие информационные элементы участвуют в формировании проверочного элемента, а единица на позициях избыточных элементов указывает, какой именно проверочный элемент образован данной суммой информационных элементов Так как каждый полученный таким образом проверочный вектор отличается от других, по крайней мере, видом элементов, соответствующих избыточным разрядам, то все (n-k) проверочных вектора являются линейно независимыми. Это означает, что матрицаH(n, k)является базисом подпространстваn– мерного векторного пространства размерности (n-k), каждый вектор которого ортогонален любой кодовой комбинации. Такое подпространство называютнулевым пространством кодаилидвойственным кодом.
Рис5.5
Векторные подпространства построенные на основе порождающей G(n,k) и проверочнойH(n,k) матриц
Проверочная матрица позволяет формализовать процесс вычисления проверочных соотношений для любой кодовой комбинации, сведя его к произведению кодовой комбинации на проверочную матрицу по правилам умножения матриц: , то естьнекоторая комбинация V принадлежит (n, k) – коду тогда и только тогда, когда она ортогональна каждой строке матрицы H(n, k).Соотношениележит в основе процедуры декодирования для групповых кодов.
В результате умножения принятой комбинации на матрицу проверок получаем вектор из (n-k) символов, называемыйсиндромом. В случае, если синдром чисто нулевой, то кодовая комбинация считается принятой безошибочно. При наличии в синдроме ненулевых компонент фиксируется наличие ошибок в кодовой комбинации.
Пример 5.7.Для рассматриваемого выше группового (5, 3) - кода проверочные вектора имеют вид:
1 0 1 1 0 ,
0 1 0 1 1 .
Проверочная матрица:
Двойственный код содержит 4 комбинации:
1 0 1 1 0
0 1 0 1 1
1 1 1 0 1
0 0 0 0 0
Это (5,2) – код с dmin=3
Каноническая форма матрицы H(n, k)имеет следующий вид:
,
где In-k– единичная матрица размеровзанимает места, соответствующие избыточным элементам кодовой комбинации;
- матрица размеров , расположенная на местах, соответствующих информационным элементам; каждая строка этой матрицы указывает, какие информационные элементы кодовой комбинации охвачены проверками на четность.
Вид матрицы устанавливается на основе следующего свойства.
Свойство 5.4. Если есть порождающая матрица систематического (n, k) – кода в канонической форме, то нулевое пространство этого кода порождается матрицей .
Доказательство этого свойства основывается на следующих рассуждениях. Поскольку любая кодовая комбинация при умножении на транспонированную проверочную матрицу должна давать (n-k) – разрядный нулевой вектор, то этот же результат должен быть получен при умножении каждой строки порождающей матрицы на проверочную матрицу, а, следовательно, и умножение матрицына матрицудает нулевую матрицу размеров, т.е. справедливо равенство.
Решение данного матричного уравнения и позволяет установить вид проверочной матрицы:
,
т.е. илиR'=.
Итак, порождающая матрица (n, k) – кода является сокращенной записью кода. Проверочная матрица указывает соотношение между избыточными и информационными элементами в каждой кодовой комбинации. Между порождающей и проверочной матрицами в канонической форме существует жесткая связь, на основе которой знание одной матрицы позволяет построить другую.
Пример 5.8.Проиллюстрируем выполнение соотношенийидля кода (5, 3). Порождающая матрица и транспонированная матрица проверок имеют вид:
Вычисляем их произведение:
Здесь элементы матрицы Sijразмерности (3х2) вычисляются следующим образом:
Таким образом:
Пусть на приемную станцию системы передачи данных поступила комбинация (1 1 1 1 1). Каким образом можно установить факт наличия ошибок в комбинации?
Во-первых, проверить соответствие информационных и проверочных элементов в соответствии с правилом их формирования:
или иили.
Для принятой комбинации получаем
.
По результату этой проверки делаем вывод о том, что в принятой кодовой комбинации имеются ошибки.
Этот же самый процесс выявления соответствия принятой комбинации коду (5, 3) формализуется вычислением:
Проверочное соотношение дает ненулевой синдром, указывающий на наличие ошибок в принятой комбинации.
Для рассматриваемого кода (5, 3):
, ,.
Используя свойство 5.4. получаем:
,
что полностью совпадает с матрицей, полученной в примере 5.7.