- •В. И. Дмитриев
- •Глава 1 Математические модели сигналов…………………………………………...19
- •Глава 1 математические модели сигналов
- •§ 1.1. Понятия сигнала и его модели
- •§ 1.2. Формы представления детерминированных сигналов
- •§ 1.3. Временная форма представления сигнала
- •§ 1.4. Частотная форма представления сигнала
- •§ 1.5. Соотношения между длительностью импульсов и шириной их спектров
- •§ 1.6. Спектральная плотность мощности детерминированного сигнала
- •§ 1.7. Функция автокорреляции детерминированного сигнала
- •§ 1.8. Случайный процесс как модель сигнала
- •§ 1.9. Стационарные и эргодические случайные процессы
- •§ 1.10. Спектральное представление случайных сигналов
- •§ 1.11. Частотное представление стационарных
- •Глава 2. Преобразование непрерывных сигналов в дискретные
- •§ 2.1. Преимущества цифровой формы представления сигналов
- •§ 2.2. Общая постановка задачи дискретизации
- •Воспроизводящая функция представляется аппроксимирующим полиномом
- •§ 2.3. Способы восстановления непрерывного сигнала
- •§ 2.4. Критерии качества восстановления
- •§ 2.5. Методы дискретизации посредством выборок
- •§ 2.6. Равномерная дискретизация. Теорема котельникова
- •§ 2.7. Теоретические и практические аспекты использования теоремы котельникова
- •§ 2.8. Дискретизация по критерию наибольшего отклонения
- •Оценка снизу для остаточного члена имеет вид
- •§ 2.9. Адаптивная дискретизация
- •Момент очередного отсчета определяется выполнением равенства
- •§ 2.10. Квантование сигналов
- •§ 2.11. Квантование сигналов при наличии помех
- •§ 2.12. Геометрическая форма представления сигналов
- •Контрольные вопросы
- •Глава 3. Количественная оценка информации
- •§ 3.1. Энтропия как мера неопределенности выбора
- •§ 3.2 Свойства энтропии
- •§ 3.3. Условная энтропия и ее свойства
- •§ 3.4. Энтропия непрерывного источника информации (дифференциальная энтропия)
- •§ 3.5. Свойства дифференциальной энтропии
- •§ 3.6. Количество информации как мера снятой неопределенности
- •§ 3.7. Эпсилон-энтропия случайной величины
- •Контрольные вопросы
- •Глава 4. Информационные характеристики источника сообщений и канала связи
- •§ 4.1. Основные понятия и определения
- •§ 4.2. Информационные характеристики источника дискретных сообщений
- •§ 4.3 Информационные характеристики дискретных каналов связи
- •§ 4.4. Информационные характеристики источника непрерывных сообщений
- •§ 4.5. Информационные характеристики непрерывных каналов связи
- •§ 4.6. Согласование физических характеристик сигнала и канала
- •§ 4.7. Согласование статистических свойств источника сообщений и канала связи
- •Глава 5. Кодирование информации при передаче по дискретному каналу без помех
- •§ 5.1. Кодирование как процесс выражения информации в цифровом виде
- •111 100 101
- •§ 5.2. Технические средства представления информации в цифровой форме
- •§ 5.3. Кодирование как средство криптографического закрытия информации
- •§ 5.4. Эффективное кодирование
- •§ 5.5. Технические средства кодирования
- •Глава 6. Кодирование информации при передаче
- •§ 6.1. Основная теорема шеннона о кодировании
- •§ 6.2. Разновидности помехоустойчивых кодов
- •§ 6.3. Блоковые коды
- •§ 6.4. Построение двоичного группового кода
- •0...01001, 0...01010, 0...01100.
- •§ 6.5. Технические средства кодирования и декодирования для групповых кодов
- •§ 6.6. Построение циклических кодов
- •§ 6.7. Выбор образующего многочлена по заданному объему кода и заданной корректирующей способности
- •§ 6.8 Технические средства кодирования и декодирования для циклических кодов
- •Остатки Векторы ошибок Опознаватели
- •Остатки Векторы ошибок Остатки
- •§ 6.9. Коды боуза — чоудхури — хоквингема
- •§ 6.10. Итеративные коды
- •Число ошибок такого вида в4 для блока изlхn символов равно
- •§ 6.11 Сверточные коды
- •Контрольные вопросы
- •Заключение
- •Список литературы
- •Приложения
Глава 6. Кодирование информации при передаче
ПО ДИСКРЕТНОМУ КАНАЛУ С ПОМЕХАМИ
§ 6.1. Основная теорема шеннона о кодировании
ДЛЯ КАНАЛА С ПОМЕХАМИ
Теория помехоустойчивого кодирования базируется на результатах исследований, проведенных Шенноном и сформулированных им в виде теоремы:
1. При любой производительности источника сообщений, меньшей, чем пропускная способность канала, существует такой способ кодирования, который позволяет обеспечить передачу всей информации, создаваемой источником сообщений, со сколь угодно малой вероятностью ошибки.
2. Не существует способа кодирования, позволяющего вести передачу информации со сколь угодно малой вероятностью ошибки, если производительность источника сообщений больше пропускной способности канала.
Хотя доказательство этой теоремы, предложенной Шенноном, в дальнейшем подвергалось более глубокому и строгому математическому представлению [34], идея его осталась неизменной. Доказывается только существование искомого способа кодирования, для чего находят среднюю вероятность ошибки по всем возможным способам кодирования и показывают, что она может быть сделана сколь угодно малой. При этом существует хотя бы один способ кодирования, для которого вероятность ошибки меньше средней.
Доказательство теоремы. Будем кодировать сообщения такой длительности Т, чтобы была справедлива теорема об асимптотической вероятности длинных последовательностей букв (см. § 4.2). Тогда при заданной производительности источника сообщений Ī(Ζ) кодированию подлежат только Ν(z) типичных последовательностей, причем:
Ориентируясь на равновероятное поступление в канал любого из m различных элементарных входных сигналов и отсутствие между ними статистической связи на входе канала, можно сформировать N(u) равновероятных последовательностей длительности Т, причем
Если условие существования способа кодирования выполняется, т. е.
то
и
Следовательно, существуетспособов кодирования, при которых множеству сообщенийN(z) случайным образом ставятся в соответствие различные подмножества разрешенных последовательностей элементарных сигналов из множества N(u).
При равновероятном выборе последовательностей элементарных сигналов из множества N(u) для любого подмножества разрешенных последовательностей вероятность ρ того, что конкретная последовательность будет отнесена к числу разрешенных,
В результате действия помех при получении на выходе канала сигналов v остается неопределенность относительно переданных последовательностей u. Она характеризуется условной энтропией Hv(U) и эквивалентна неопределенности выбора из последовательностей. Конкретная последовательность может быть идентифицирована со сколь угодно малой вероятностью ошибки, если средиNv(U) последовательностей она единственная разрешенная. Отсюда принципиальная необходимость введения избыточности в кодируемые последовательности для компенсации потерь информации в канале из-за действия помех.
Определим среднюю по всем возможным способам кодирования вероятность того, что ни одна изNv(U)-1 последовательностей не является разрешенной:
Так как (1 — р)<1, то увеличение степени на единицу приведет к неравенству
Правую часть неравенства разложим в ряд
Покажем, что члены ряда убывают по абсолютному значению. Для этого выразим ρ через Nv(U) [14].
Используя соотношение (6.3), запишем
или
гдеВыражение (6.4) теперь можно привести к виду
Согласно признаку Лейбница, остаток знакопеременного ряда с убывающими по абсолютному значению членами имеет тот же знак, что и первый отбрасываемый член, и меньше его по абсолютному значению. Следовательно, отбросив в разложении (6.5) все члены, содержащие ρ во второй и более высоких степенях, мы только усилим неравенство
Тогда для средней вероятности ошибочного приема типичной последовательности ошзапишем:
Вероятность ош пристремится к нулю. Принимая во внимание, что при неограниченном увеличении Т вероятность появления на входе канала нетипичной последовательности в соответствии с теоремой об асимптотической равновероятности также стремится к нулю, справедливо утверждение: при любом заданномη>0 можно выбрать такое T, при котором средняя вероятность ошибочной передачи информации по каналу будет меньше произвольно малого положительного числа.
Теорему можно считать доказанной, поскольку среди всего множества способов кодирования должен существовать хотя бы один, при котором вероятность ошибочного приема меньше средней.
С доказательством второй части рассматриваемой теоремы (обратного утверждения) можно ознакомиться в [36].
Обсуждение теоремы. В первую очередь отметим фундаментальность полученного результата. Теорема устанавливает теоретический предел возможной эффективности системы при достоверной передаче информации. Ею опровергнуто казавшееся интуитивно правильным представление о том, что достижение сколь угодно малой вероятности ошибки в случае передачи информации по каналу с помехами возможно лишь при введении бесконечно большой избыточности, т. е. при уменьшении скорости передачи до нуля. Из теоремы следует, что помехи в канале не накладывают ограничений на точность передачи. Ограничение накладывается только на скорость передачи, при которой может быть достигнута сколь угодно высокая достоверность передачи.
Теорема неконструктивна в том смысле, что в ней не затрагивается вопрос о путях построения кодов, обеспечивающих указанную идеальную передачу. Однако, обосновав принципиальную возможность такого кодирования, она мобилизовала усилия ученых на разработку конкретных кодов.
Следует отметить, что при любой конечной скорости передачи информации вплоть до пропускной способности сколь угодно малая вероятность ошибки, как следует из соотношения (6.10), достигается лишь при безграничном увеличении длительности кодируемых последовательностей знаков. Таким образом, безошибочная передача при наличии помех возможна лишь теоретически.
Обеспечение передачи информации с весьма малой вероятностью ошибки и достаточно высокой эффективностью возможно при кодировании чрезвычайно длинных последовательностей знаков. На практике степень достоверности и эффективности ограничивается двумя факторами: размерами и стоимостью аппаратуры кодирования и декодирования и временем задержки передаваемого сообщения. В настоящее время используются относительно простые методы кодирования, которые не реализуют возможностей, указанных теорией. Однако постоянно растущие требования в отношении достоверности передачи и успехи в технологии создания больших интегральных схем способствуют внедрению для указанных целей все более сложного оборудования.