- •Министерство образования и науки республики казахстан Южно - Казахстанский государственный университет им. М. Ауезова технологии цифровой связи
- •6 Лекция №6.
- •1.1 Функциональная схема и основные элементы цифровой системы
- •Проводные, волоконно - оптические и беспроводные каналы. Математические модели каналов связи.
- •Определения понятий непрерывный, дискретного канала (дк) и расширенный дискретный канал (рдк) и их основные характеристики. Определение понятия синхронного и асинхронного дк.
- •Особенности сопряжения анизохронного и изохронных дискретных сигналов с синхронным дк.
- •2.1Типы линий связи
- •2.2. Типы характеристик и способы их определения
- •Амплитудно-частотная характеристика, полоса пропускания и затухание
- •Синхронный канал - канал, обеспечивающий синхронизацию процесса передачи данных.
- •3.1 Математические модели каналов связи
- •2 Межсимвольная интерференция
- •Формирование энергетического спектра.
- •Скремблирование.
- •6.1 Алгоритмы цифрового кодирования
- •6.2 Биполярный метод
- •6.3 Псевдотроичный метод
- •6.4 Парно-селективный троичный код
- •7.2 Многопозиционная модуляция
- •7.3 Амплитудная манипуляция
- •7.4 Амплитудно-фазовая манипуляция
- •7.5 Оптимальный прием дс сигнала
- •7.8. Спектральные характеристики модулированных колебаний
- •7.9 Оптимальный приемник
- •7.10 Когерентный и некогерентный прием
- •7.11 Цифровой согласованный фильтр
- •7.12 Оценка помехоустойчивости модулированных сигналов
- •8.2 Синхронизация поэлементная, групповая и цикловая
- •9.1 Основные принципы обнаружения и исправления ошибок
- •Связь между корректирующей способностью кода и длиной кода
- •9.3 Классификация корректирующих кодов
- •9.4 Граничные соотношения между параметрами помехоустойчивых кодов
- •Порождающие матрицы блочных кодов
- •Характеристики блочных линейных кодов
- •10.2. Систематические коды
- •Обнаружение ошибок с помощью систематических кодов
- •Коды Хемминга
- •Циклические коды
- •Кодирование с использованием циклических кодов
- •Неалгебраические методы помехоустойчивого декодирования
- •13.1 Характеристики систем с обратной связью и их особенности
- •13.2 Структурная схема системы с информационной обратной связью (иос) и решающей обратной связью (рос), характеристики и алгоритмы работы
- •14 Лекция №14. Сжатие данных в цсс
- •Применение эффективного (статистического) кодирования для сжатия данных.
- •Алгоритмы сжатия без потерь: rle, lzw (Лемпелла - Зива - Узлча), Хаффмана.
- •Особенности применения алгоритма Хаффмана в факсимильной связи (Использование алгоритма с фиксированной таблицей ccit). Сжатие данных
- •Типы сжатия с потерями
- •Сжатие с потерями против сжатия без потерь
- •Сжатие без потерь
- •Многоцелевые
- •Сжатие аудио
- •Сжатие графики
- •Сжатие видео
- •Сжатие текстов
- •14.1 Алгоритмы сжатия без потерь
9.1 Основные принципы обнаружения и исправления ошибок
Рассмотрим два основных метода использования избыточности для защиты от ошибок. В первом методе, обнаружение ошибок и повторная передача, для проверки на наличие ошибки используется контрольный бит четности (дополнительный бит, присоединяемый к данным). При этом приемное оконечное устройство не предпринимает попыток исправить ошибку, оно просто посылает передатчику запрос на повторную передачу данных. Следует заметить, что для такого диалога между передатчиком и приемником необходима двухсторонняя связь. Второй метод, прямое исправление, требует лишь односторонней линии связи, поскольку в этом случае контрольный бит четности служит как для обнаружения, так и исправления ошибок. Далее мы увидим, что не все комбинации ошибок можно исправить, так что коды коррекции классифицируются в соответствии с их возможностями исправления ошибок.
Принцип обнаружения и исправления ошибок кодами хорошо иллюстрируется с помощью геометрических моделей. Любой n- элементный двоичный код можно представить n – мерным кубом, в котором каждая вершина отображает кодовую комбинацию, а длина ребра куба соответствует одной единице. В таком кубе расстояние между вершинами измеряется минимальным количеством ребер, находящихся между ними, обозначается d и называется кодовым расстоянием.
Связь между корректирующей способностью кода и кодовым расстоянием
Важная характеристика помехоустойчивого кода – наименьшее расстояние между разрешенными кодовыми комбинациями dmin. Оно обеспечивает корректирующие свойства кода.
Проиллюстрируем этот подход для (3,2)-кода: количество информационных разрядов k = 2, следовательно, число разрешенных кодовых комбинаций Sр = 22 = 4; общее число кодов S=23 =8. Число проверочных бит r = n – k = 1 и устанавливать их значение условимся таким образом, чтобы количество «единиц» во всех кодовых комбинациях было бы четным (по этой причине такой проверочный бит называется битом четности).
Ui |
a1 |
a2 |
b |
∑ |
U1 |
0 |
0 |
0 |
0 |
U2 |
0 |
1 |
1 |
2 |
U3 |
1 |
0 |
1 |
2 |
U4 |
1 |
1 |
0 |
2 |
Будем обозначать разрешенные кодовые комбинации Ui. Их информационная часть может принимать значения 00, 01,10 и 11 (обозначим эти биты a1 и a2); проверочный бит b принимает значения, приведенные в таблице. Последняя колонка содержит суммы (количество) бит со значением "1" в каждой кодовой комбинации. Любую из 8 существующих для n = 3 кодовых комбинаций можно считать вектором в пространстве, построенном на единичных векторах a1, a2, b – это иллюстрируется рисунком 9.1. Отметим разрешенные комбинации ноликами; остальные, очевидно, будут запрещенными - их отметим крестиками. Видно, что минимальное кодовое расстояние между разрешенными комбинациями равно 2 (расстояние между разрешенными вершинами по ребрам куба). На рисунке однократной ошибке соответствует переход из вершины куба в соседнюю вершину. Любая однократная ошибка переводит разрешенную комбинацию в запрещенную, следовательно, может быть обнаружена. Однако исправить такую ошибку нельзя, поскольку в любую из запрещенных вершин за один шаг можно попасть, по крайней мере, из двух разрешенных.
Рис. 9.1. К вопросу о связи кодового расстояния и корректирующей способности кода.
Обобщим рассуждения. Пусть необходимо построить код, обнаруживающий все ошибки кратности τ и меньше. Построить такой код – это значит из множества S возможных комбинаций выбрать Sp разрешенных комбинаций так, чтобы любая сумма по модулю 2 с любым вектором ошибок с весом ω ≤ τ не дала бы в результате никакой другой разрешенной комбинации. Для этого необходимо, чтобы наименьшее кодовое расстояние удовлетворяло условию
Рассмотрим код со значностью n=3. Все возможные комбинации этого кода приведены в таблице:
А1 |
А2 |
А3 |
А4 |
А5 |
А6 |
А7 |
А8 |
000 |
001 |
010 |
011 |
100 |
101 |
110 |
111 |
Составим матрицу кодовых расстояний:
|
А1 |
А2 |
А3 |
А4 |
А5 |
А6 |
А7 |
А8 |
А1 |
0 |
1 |
1 |
2 |
1 |
2 |
2 |
3 |
А2 |
1 |
0 |
2 |
1 |
2 |
1 |
3 |
2 |
А3 |
1 |
2 |
0 |
1 |
2 |
3 |
1 |
2 |
А4 |
2 |
1 |
1 |
0 |
3 |
2 |
2 |
1 |
А5 |
1 |
2 |
2 |
3 |
0 |
1 |
1 |
2 |
А6 |
2 |
1 |
3 |
2 |
1 |
0 |
2 |
1 |
А7 |
2 |
3 |
1 |
2 |
1 |
2 |
0 |
1 |
А8 |
3 |
2 |
2 |
1 |
2 |
1 |
1 |
0 |
Для того, чтобы код обеспечивал обнаружение однократных ошибок, необходимо из 8 возможных комбинаций выбрать в качестве разрешенных такие, расстояние между которыми было бы не менее d=2. Например, определим разрешенными комбинациями такие: А2 = 001, А3 = 010, А5 = 100, А8 = 111. Любая однократная ошибка переводит разрешенную комбинацию в запрещенную.
Для обнаружения двукратных ошибок наименьшее кодовое расстояние должно быть dmin=3. В качестве примера разрешенных комбинаций в этом случае можно выбрать А3=010 и А6=101.
Пусть теперь необходимо построить код, обеспечивающий исправление однократных ошибок. Выберем в качестве первой разрешенной комбинации А2=001. При однократной ошибке комбинация А2 перейдет в одну из трех комбинаций: А1=000, А4=011 или А6=101 (рис. 9.1). Эти комбинации объявляются запрещенными комбинациями для А2. Это означает, что при появлении одной из этих комбинаций на выходе канала связи будет принято решение, что передана комбинация А2.
Рис. 9.2. Варианты перехода между кодовыми комбинациями при однократной ошибке.
Допустим, в качестве второй разрешенной комбинации выбрана А3=010, отстоящая на расстоянии d=2. Ей соответствует подмножество запрещенных комбинаций А4=011, А1=000 и А7=110. Однако получилось пересечение подмножеств запрещенных комбинаций. При приеме запрещенных комбинаций А4 и А1 нельзя однозначно установить, какая комбинация была послана – А2 или А3. Если же в качестве второй разрешенной комбинации принять А7=110, которой соответствуют запрещенные комбинации А8=111, А5=100 и А3=010, то в этом случае подмножества запрещенных комбинаций не пересекаются и имеется однозначное соответствие принятой и переданной комбинации.
Следовательно, при dmin=3 обеспечивается исправление всех однократных ошибок.
В общем случае, для исправления ошибок кратности t минимальное кодовое расстояние должно удовлетворять условию
dmin ≥ 2t + 1
Аналогично рассуждая, можно установить, что для исправления всех ошибок кратности не более t и одновременного обнаружения всех ошибок кратности не более τ (при τ ≥ t) кодовое расстояние должно удовлетворять условию
dmin ≥ t + τ + 1
