- •Санкт-Петербургский государственный университет телекоммуникаций им.Проф. М.А. Бонч-Бруевича в.М. Охорзин
- •Санкт-Петербург
- •Тема 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. Групповые коды и способы их описания
5.2.1. Основные алгебраические системы, используемые в теории кодирования
Современные и перспективные помехоустойчивые коды строятся на основе некоторой математической модели, что позволяет достаточно просто решать вопросы определения их свойств и реализуемости. При построении кодов используются алгебраические системы: группа, векторное пространство, кольцо и поле.
а) Группа
Пусть имеется множество Gэлементов произвольной природы, которые обозначимa, b, c…, и пусть над этими элементами можно производить операцию сложения или умножения таким образом, что двум любым элементам множестваGпо определенным правилам ставится в однозначное соответствие некоторый элемент того же множестваG. В общем виде введенную операцию будем обозначать знаком. Для операции сложения и умножения будем использовать общепринятые знаки (“+” и ”” соответственно).
Множество Gназывают группой, если для введенной операции оно удовлетворяет следующим требованиям:
G1. Множество замкнуто: еслиaиbпринадлежатG,то и c, полученное на основе введенной операциитакже принадлежит этому же множеству элементовG. При сложении, при умножении.
G2. Выполняется сочетательный (ассоциативный) закон:
.
При сложении ,
При умножении .
G3. Наличие единичного элементаe: среди элементов множестваG имеется такой элементe, для которого справедливо, гдеa- произвольный элементG.
В случае операции сложения над числами равенство возможно лишь в том случае, когдаe= 0. Если же над числами производится операция умножения, то равенствовозможно лишь в том случае, когдаe= 1.
G4. Наличие обратных элементов: для произвольного элементаамножестваGсуществует в этом множестве такой элемент, для которого справедливо
.
Если элементами множества Gявляются числа, то при сложении, а при умножении.
Примеры групп:
1. Множество целых чисел положительных, отрицательных и нуля является группой по операции сложения.
2. Числа 0 и 1 образуют группу по операции “сложение по модулю 2”.
1) Замкнутость. Обусловлена таблицей сложения
-
+
0
1
0
0
1
1
1
0
2) Сочетательность. Легко проверить, что сложение по модулю 2 подчиняется сочетательному закону, например
,
.
3) Единичный элемент. Здесь 0 является единичным элементом
4) Обратные элементы. Каждое число является обратным к самому себе, т.к. и.
Пример 5.1. Проверить, является ли множество трехразрядных комбинаций 000,001, 010 и 011 группой по операции поразрядного сложения по модулю 2.
Замкнутость. Составим таблицу сложения:
+ |
|
|
|
|
000 |
000 |
001 |
010 |
011 |
001 |
001 |
000 |
011 |
010 |
010 |
010 |
011 |
000 |
001 |
011 |
011 |
010 |
001 |
000 |
Мы видим, что сумма любой пары комбинаций также является комбинацией из данного множества, т.е. требование замкнутости удовлетворяется.
2) Сочетательность. Это требование также удовлетворяется, т.к. в основе операции – сложение по модулю 2.
3) Единичный элемент. Комбинация 000 является единичным элементом в данном множестве (см. таблицу сложения).
4) Обратные элементы. Обратной комбинацией для любой комбинации является эта же комбинация (см. таблицу сложения).
Итак, множество комбинаций 000, 001, 010 и 011 является группой по операции поразрядного сложения по модулю 2.
Группа называется абелевой в честь известного норвежского математика Н.Х. Абеля (1802-1829), если множество Gпо введенной операции обладает еще и следующими свойствами:, т.е. выполняется переместительный (коммутативный) закон. Группы, рассмотренные в предыдущих примерах, являются абелевыми.
Важным понятием в теории групп является понятие подгруппы.
Если множество элементов составляет группу и некоторая часть этого множества (Н) также обладает всеми групповыми свойствами, то эту часть элементов группы называют подгруппой. Слово “подгруппа” означает “группа внутри группы”. Для того, чтобы установить, является лиНподгруппойнеобходимо проверить замкнутость и наличие обратных элементов. Если множествоНзамкнуто относительно заданной в группе операций и содержит обратные элементы, то это множество содержит и единичный элемент группы, а сочетательный закон выполняется, так как он справедлив для всех элементов группы.
Основные свойства группы:
1. Группа содержит единственный единичный элемент, и для каждого элемента группы имеется единственный обратный элемент.
2. Группа разлагается на смежные классы по подгруппе. Смысл этого разложения заключается в следующем.
Обозначим элемент группы через а элемент подгруппыН– через Рассмотрим таблицу, образованную следующим образом.
Запишем все элементы подгруппы Н, начиная с единичного элемента, в первую строку, причем каждый элемент подгруппы появится в этой строке только один раз. Далее выбираем любой элемент, не принадлежащийН, и записываем его на первое место во второй строке, а все остальные элементы второй строки находятся применением заданной в группе операции над первым элементом второй строки и соответствующими элементами подгруппыH, записанными в первой строке. Аналогично образуются третья, четвертая и т.д. строки, до тех пор, пока все элементыне войдут в таблицу. В качестве первого элемента каждой строки всякий раз выбирается произвольный элемент, не вошедший в предшествующие строки. Этот элемент называют образующим смежного класса.
В результате получаем таблицу следующего вида:
Строки полученной подобным образом таблицы называются смежными классами.
Основные свойства разложения группы на смежные классы по подгруппе формулируются следующим образом:
3. В таблице разложения группы на смежные классы по подгруппе Н перечисляются все элементы группы, причем каждый элемент появляется в таблице только один раз.
4. Состав смежного класса постоянен и не зависит от выбора образующего элемента.
5. Число элементов в Н является делителем числа элементов в .
6. Два элемента gi и gj группы G принадлежит одному и тому смежному классу по подгруппе H тогда и только тогда, когда gi gj принадлежат H.
7. Операция, введенная над элементами группы, может быть введена и над смежными классами. Обозначим{gi} смежный класс, содержащий элемент группы {gi} . Тогда {gi}{gj}={gigj}, т.е. в результате операции над смежными классами, содержащими элементыgi и gj, получается новый смежный класс, содержащийgigj. В случае абелевой группы операция над смежными классами приводит к группе, элементами, которой является смежные классы.
Пример 5.2.
Пусть G - группа по операции сложения (т.е. аддитивная группа), состоящая из всех положительных и отрицательных целых чисел и нуля, и пустьH– подгруппа, состоящая из всех чисел, кратных целому числуn. Все числа от нуля доn-1 принадлежат различным смежным классам, т.к. для того, чтобыaиb принадлежали одному смежному классу необходимо, чтобы число(-a)+bпринадлежало подгруппе, т.е. было кратноn, что невозможно. Значит, числа от 0 доn-1 могут быть выбраны в качестве образующих смежных классов и других чисел, быть не может. Легко проверить, что группаG - абелева, поэтому можно ввести операцию сложения смежных классов и смежные классы образуют группу. Положимn=2. Тогда смежные классы имеют вид:
0, 2, -2, 4, -4, 6, -6,…
1, 3, -1, 5, -3, 7, -5,…
Если обозначить смежные классы {0}и {1} соответственно, то таблица сложения смежных классов получит вид:
+ |
{0} |
{1} |
{0} |
{0} |
{1} |
{1} |
{1} |
{0} |
В этой таблице легко узнается таблица сложения чисел по модулю 2.
б) Векторное пространство.
Множество элементов произвольной природы V, называемых далее векторами, образует векторное пространство, если оно удовлетворяет следующим требованиям.
1. Множество векторов образует абелеву группупо операции сложения векторов.
2. Определено правило умножения вектора V на скалярс, гдесв рассматриваемом нами случае принимает значение 0 или 1, и произведениеявляется вектором того же векторного пространстваV.
3. Выполняется распределительный закон:
- если сиdскаляры, аv - вектор (vV), то,
- если v иu– векторы (V), ас– скаляр, то.
4. Операция умножения на скаляр подчиняется сочетательному закону: если с,d– скаляры, аv- вектор (vV), то.
Пример 5.3.Проверить, является ли набор комбинаций 000,001,010 и 011 векторным пространством.
В примере 5.1. было показано, что эти комбинации образуют группу по операции поразрядного сложения по модулю 2. Так как для любых комбинаций порядок сложения несущественен, например,001+010=010+001=011, то эта группа является абелевой.
Будем полагать каждую комбинацию вектором и умножение на скаляр производить следующим образом: , еслис= 1, и, еслис = 0, гдеv- любая из рассматриваемых комбинаций.
При таком введении операции умножения на скаляр выполняются распределительные законы, например:
и
1∙(011+010)=.
Операция умножения на скаляр подчиняется сочетательному закону, например,
, равно как .
Таким образом, набор комбинаций 000, 001, 010 и 011 при введении операций указанным выше способом удовлетворяет требованиям векторного пространства.
Рассмотренный пример показывает, что для двоичного случая свойства векторного пространства в основном определены свойствами абелевой группы.
Сформулируем некоторые понятия и определения, относящиеся к векторному пространству.
Сложение векторов
Пусть Vи- два вектораn– мерного векторного пространствагде- скаляры (двоичные элементы). Тогда суммой этих векторов будем называть новый вектор, образованный по следующему правилу:
.
Умножение вектора на скаляр
Пусть вектор, ас– скаляр. Умножение вектора на скаляр дает новые вектор, образованный по следующему правилу:
.
Скалярное произведение векторов
Пусть VиU векторы:. Скалярным произведением векторов называется скаляр (двоичный элемент), образованный по следующему правилу:
Знак “+”здесь имеет смысл сложения по модулю 2.
Если скалярное произведение векторов равно 0, то такие векторы называются ортогональными.
Линейная комбинация векторов
Линейной комбинацией векторов называют вектор, образованный по следующему правилу:
, где - скаляры (двоичные элементы).
Линейная зависимость векторов
Если есть векторы,есть скаляры, причем хотя бы один из них не равен0, то указанный набор векторов называется линейно-зависимым, если
В этом случае, когда эта сумма обращается в 0 (чисто нулевой вектор 00…0) только лишь при равенстве всех скаляров нулю, этот набор векторов называют линейно-независимым.
6) Базис векторного пространства
Векторное пространство размерности n (n– мерное векторное пространство) со значением скаляров 0 или 1 содержит в своем составе 2nразличных векторов.
Это пространство может быть охарактеризовано базисом, состоящим из nлинейно независимых векторов. Все остальные векторы можно получить путем линейных комбинаций базисных векторов.
Подпространство n – мерного векторного пространства размерностиk, гдеk<n, содержит 2kразличных векторов, выбранных на 2nвекторов, составляющихn – мерное пространство, таким образом, что удовлетворяются все требования векторного пространства. Любой набор изkлинейно-независимых векторов данного пространства может служить его базисом.
Пример 5.4.Набор векторов 000, 001, 010, 011, 100, 101, 110, 111 образует 3-мерное векторное пространство (23векторов). Его базисом могут служить следующие тройки векторов:
001, 010, 100 или 010, 011, 110 и т.д.
С помощью базисных векторов можно получить любой другой вектор данного 3-мерного пространства. Используя линейную комбинацию базисных векторов
,
получим, например, вектор101. Для этого надо взять , тогда
.
Подбором можно получить каждый вектор рассматриваемого пространства.
В примере 5.3. мы установили, что набор векторов 000, 001, 010 и 011 удовлетворяет всем требованиям векторного пространства.
По отношению к полному набору векторов 3-мерного векторного пространства данный набор векторов является подпространством размерности 2.
Его базисы