ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 22.02.2019
Просмотров: 2377
Скачиваний: 37
. (3.44)
При
нетрудно отыскать с учетом (3.32) и (3.44)
. (3.45)
Пороговому
сигналу (3.45) будет соответствовать (см.
рис. 3.5) значение
.
Для заданной шумовой погрешности
(3.39) и с учетом (3.45) будем иметь
,
откуда
,
для которого с учетом (3.41) и условия β
1 находим
.
Более выгодное использование полосы частот канала обеспечивается в реальном канале с кодово-импульсной модуляцией (КИМ), для которого среднеквадратическая погрешность с учетом теоремы Котельникова примет вид
.
Известно,
что если на выходе канала с ЧМ отношение
линейно зависит от ширины полосы канала,
то при КИМ отношение
растет экспоненциально, как в идеальном
канале по Шеннону, что подчеркивает
достоинство КИМ. Заметим, что в канале
с КИМ, как и в канале с ЧМ, имеют место
аномальные помехи. Более выгодное
использование полосы частот пропускания,
аналогичное идеальному каналу,
обеспечивается в
реальных каналах с кодово-импульсной
модуляцией (КИМ).
3.4 Основные теоремы Шеннона
Основная теорема Шеннона для дискретного канала без шумов
Если поток информации, вырабатываемый источником, равен
, (3.46)
где ε может быть как угодно малым, то всегда можно найти такой способ кодирования, который обеспечит передачу всех сообщений, вырабатываемых источником, причем скорость передачи информации будет равна
Если
же
,
то невозможно будет обеспечить длительную
передачу всех сообщений источника.
Основная теорема Шеннона для дискретного канала с шумами
Если поток информации, вырабатываемый источником, равен
, (3.46а)
где ε сколь угодно мало, то существует способ кодирования, при котором все сообщения, вырабатываемые источником, могут быть переданными, а вероятность ошибочного опознания любого переданного сообщения может быть как угодно малой, т.е.
,
(3.47)
где рР – вероятность неправильного опознания любого переданного сообщения, η – как угодно малая положительная величина. Обратное утверждение этой теоремы состоит в том, что если
,
то не существует способа кодирования,
обеспечивающего передачу всех сообщений
с малой вероятностью ошибки.
В общем случае выполнение (3.46а) может быть достигнуто с помощью кодирования достаточно длинных последовательностей сообщений. Если МХ – число сообщений в одной кодируемой последовательности, то чем меньше ε в (3.46а) и η в (3.47), теми большим должно быть число МХ, т.е. тем длиннее должна быть кодируемая последовательность.
Основная теорема Шеннона для непрерывных каналов
Если
ε-энтропия
источника непрерывных сообщений,
определяющая количество информации,
вырабатываемое источником в единицу
времени (поток информации непрерывного
источника) при заданной оценке g
верности воспроизведения равна
, (3.48)
где α как угодно мало, то существует метод передачи, при котором все сообщения вырабатываемые источником, могут быть переданы, а верность воспроизведения при этом как угодно близка к g.
Обратное утверждение этой теоремы говорит о том, что такая передача невозможна, если
.
ε-энтропия определяется как наименьшее значение количества информации в принятой случайной величине Y относительно переданной случайной величине Х при заданной верности произведения g:
, (3.49)
где ε – приемлемо малая величина.
3.5 Энтропия источника при наличии коррелятивных связей между двумя соседними символами
Полученные ранее выражения для энтропии дискретного источника сообщений справедливы в случае, когда все сообщения независимы.
Рассмотрим источник, у которого имеют место коррелятивные связи между двумя соседними символами. Вероятность появления символа xi зависит лишь от того, какой символ был выработан до этого.
Для описания такого источника необходимо задать распределение вероятностей p(xi) и вероятности переходов (условная вероятность) p(xi|xk) или вероятности всех возможных пар символов p(xi, xk).
Нижеприведенное выражение описывает связь между этими вероятностями
.
(3.50)
Если коррелятивные связи имеются между двумя соседними символами, то энтропия источника равна
(3.51)
Сравним энтропии источников с независимыми событиями и с коррелятивными связями между двумя соседними сообщениями.
Вероятности каждого из четырех сообщений равны:
p(x1)=1/2, p(x2)=1/4, p(x3)= p(x4)=1/8.
Для независимых событий
.
Пусть между двумя соседними символами имеются коррелятивные связи, которые описываются таблицей
|
xixj |
p(xi, xj) |
p(xi | xj) |
xixj |
p(xi, xj) |
p(xi | xj) |
|
x1x1 |
13/32 |
13/16 |
x3x1 |
0 |
0 |
|
x1x2 |
3/32 |
3/16 |
x3x2 |
0 |
0 |
|
x1x3 |
0 |
0 |
x3x3 |
0 |
0 |
|
x1x4 |
0 |
0 |
x3x4 |
1/8 |
1 |
|
x2x1 |
1/32 |
1/8 |
x4x1 |
1/16 |
1/2 |
|
x2x2 |
1/8 |
1/2 |
x4x2 |
1/32 |
1/4 |
|
x2x3 |
3/32 |
3/8 |
x4x3 |
1/32 |
1/4 |
|
x2x4 |
0 |
0 |
x4x4 |
0 |
0 |
По заданным вероятностям появления символов p(xi) и вероятностям пар импульсов p(xi, xj) из (3.50) определяются условные вероятности
,
представленные в третьем и шестом
столбцах таблицы.
Используя
(3.51), получим
,
т.е. при наличии коррелятивных связей
между сообщениями источника энтропия
уменьшается.
4 ПОМЕХОУСТОЙЧИВОЕ КОДИРОВАНИЕ
Помехоустойчивое кодирование
Необходимость передачи цифровых сообщений на значительные расстояния, использование сетевых технологий предъявляют повышенные требования к достоверности передачи, обработки и ранения информации. Простые двоичные коды не удовлетворяют этим требованиям. Рассмотрим простой трехразрядный код: 000,
001,
010 …
Для простого двоичного кода искажения любого символа воспринимаются как другая кодовая комбинация. В результате на приемной стороне принимается ошибочная кодовая комбинация. Оценим вероятность такой ошибки.
Пусть р – вероятность искажения одного символа, а q – вероятность правильного приема одного символа.
Искажение и правильный прием образуют пару несовместных событий, поэтому сумма их вероятностей равна единице.
Тогда q=1 – p.
Так как символы искажаются независимо друг от друга, то вероятность правильного приема комбинации из n символов:
(4.1)
Вероятность искажения кодовой комбинации:
(4.2)
При
и менее (1– р)n≈1–рn.
Тогда Рк≈np.
Для
.
Для повышения достоверности приема цифровых сигналов используют помехоустойчивое кодирование.
Основной принцип помехоустойчивого кодирования
Пусть
имеется простой двоичный код, с помощью
которого можно передать
кодовых комбинаций. Из этого числа N
используют лишь
кодовых комбинаций.
- число разрешенных кодовых комбинаций.
- число запрещенных кодовых комбинаций.
Для
исключения возможности перехода одной
разрешенной комбинации в другую
разрешенную кодовую комбинацию
выполняется соотношение
.
Так как в помехоустойчивом коде число разрешенных кодовых комбинаций меньше общего числа кодовых комбинаций, возможных для двоичного кода данной разрядности, то помехоустойчивые коды называют еще избыточными кодами.
Избыточность кода можно оценить выражением:
(4.3)
-
число избыточных символов в переданной
кодовой комбинации.
Декодирование избыточных кодов
Декодирование избыточных кодов можно осуществить двумя способами:
-
Декодирование с обнаружением ошибок.
-
Декодирование с исправление ошибок.
В первом случае устанавливается только факт приема запрещенной кодовой комбинации. При этом дальнейшая обработка принятых сигналов может быть организована следующим образом: 1) ошибочная кодовая комбинация либо уничтожается, и теряется информация, переданная в исходной кодовой комбинации; 2) запрашивается повторная передача исходной кодовой комбинации до тех пор, пока она не будет принята без ошибки. Это не всегда возможно при обработке сигналов в режиме реального времени, так как затягивает общее время передачи.
Во втором способе декодирования принятые запрещенные кодовые комбинации преобразуются в переданные разрешенные кодовые комбинации. При этом чаще всего процедура декодирования основывается на критерии максимального правдоподобия. Каждая принятая кодовая комбинация сопоставляется с каждой разрешенной кодовой комбинацией. Та из них, которая меньше всего отличается от принятой кодовой комбинации и принимается за принятую кодовую комбинацию.
Рассмотрим
это на примере. Пусть
.
Тогда N=8,
но используется всего
кодовые комбинации, а именно 000 и 111.
Каждой из этих разрешенных кодовых
комбинаций соответствует своя группа
запрещенных кодовых комбинаций
а) б)
Если принята одна из запрещенных кодовых комбинаций группы а), то наиболее вероятно, что была передана разрешенная комбинация 000, а если из группы б), то передана комбинация 111.
Введение избыточных символов позволяет существенно увеличить вероятность правильного приема.
Для двоичного симметричного канала передачи вероятность ошибочного приема любых l символов в n-элементной кодовой комбинации подчиняется биномиальному закону распределения
Pn(l)=Cnlpl(1-p)n-l.
Неправильный прием одного, двух, и т.д. элементов из n-элементной кодовой комбинации обозначают термином «одиночная», «двойная» и т. д. ошибка соответственно. Или говорят, что произошла ошибка кратности l.
Если код исправляет ошибки кратности t, то вероятность ошибочного приема кодовой комбинации равна
.
(4.4)
Пусть исправляется ошибка кратности t=1. Тогда из (4.4) для рассмотренного выше примера (где n=8) получим:
РК=8*10-3 – 8*10-3*0.9997)≈5.6*10-5.
Исправление всего лишь однократной ошибки повышает помехоустойчивость избыточного кода на два порядка.
Кодовое расстояние
Возможность корректирующих кодов по исправлению и обнаружению ошибок определяется кодовым расстоянием.
Кодовым расстоянием d называется минимальное количество разрядов в которых одна кодовая комбинация отличается от другой кодовой комбинации.
Для конкретного кода кодовым расстоянием данного кода называется минимальное число элементов, которыми одна кодовая комбинация данного кода отличается от другой кодовой комбинации того же кода.
Иногда кодовое расстояние называется хемминговым расстоянием (по имени Ричарда Хемминга, основателя помехоустойчивых кодов) .
У простого двоичного кода d=1. Каким должно быть кодовое расстояние у кодов, обнаруживающих ошибки, и у кодов, исправляющих ошибки?
В общем случае для обеспечения возможности исправления всех ошибок кратности до t включительно при декодировании по методу максимального правдоподобия каждая из ошибок должна приводить к запрещенной кодовой комбинации, входящей в группу таких комбинаций, соответствующих исходной кодовой комбинации.
Пусть
имеется n-разрядный
двоичный код. Выберем 2 кодовые комбинации
и
,
которые будем считать разрешенными
(рисунок 4.1). Каждой разрешенной кодовой
комбинации соответствует свое подмножество
запрещенных кодовых комбинаций с
одиночными ошибками. Число их равно
Cn1,
а кодовое расстояние относительно
исходной кодовой комбинации d=1.
Графически это представляется окружностью
с радиусом d=1.
Рисунок 4.1 – Определение кодового расстояния
Аналогично, подмножество запрещенных кодовых комбинаций с двойной ошибкой имеет кодовое расстояние относительно исходной d=2, а число их равно Cn2. И так далее до ошибок кратности t включительно.
Для
того чтобы при приеме восстановить
именно
кодовую комбинацию необходимо, чтобы
набор ее запрещенных кодовых комбинаций
не пересекался с набором запрещенных
кодовых комбинаций
.
Для
исправления ошибок кратности t
кодовое
расстояние должно удовлетворять условию:
.
Для исправления ошибки кратности s кодовое расстояние должно быть:
.
Если
код должен исправлять ошибки кратности
t
и обнаруживать ошибки кратности s,
то кодовое расстояние должно быть не
менее
Помехоустойчивые коды делятся на два больших класса:
-
Блоковые коды;
-
Непрерывные коды.
Для блоковых кодов к каждой исходной комбинации добавляется блок избыточных символов и получается новая комбинация (рисунок 4.2).
Рисунок 4.2 – Построение блокового кода
Различают разделимые и неразделимые блоковые коды. В разделимых блоковых кодах k символов являются информативными, а r - проверочными.
Такие коды обозначают как (n,k) – коды.
Для неразделимых кодов разделить символы на информативные и проверочные невозможно (см. далее корреляционный код).
Непрерывными кодами называются коды, в которых введение избыточных символов в кодируемую последовательность осуществляется непрерывно, без разделения ее на независимые блоки.
ПРОСТЕЙШИЕ ИЗБЫТОЧНЫЕ КОДЫ
Код с четным числом единиц. Код с четным числом единиц образуется из исходного k-элементного кода добавлением еще одного элемента, нуля или единицы, таким образом, чтобы количество единиц в новой кодовой комбинации было четным. Для определения дополнительного элемента все элементы исходной кодовой комбинации складывают по модулю 2:
0 1 1 1 0 1 1 0 = 1,
0 0 1 1 0 1 1 0 = 0.
Таким образом, число элементов в новой кодовой комбинации n=k+r=k+1. Избыточность кода с четным числом единиц
.
(4.5)
Этот код имеет кодовое расстояние d=2 и обнаруживает все нечетные ошибки.
Корреляционный код
При построении корреляционного кода каждый элемент исходного кода преобразуется в 2 элемента:
1 à 10,
0 à 01.
Таким образом, корреляционный код относится к непрерывным кодам.
Если исходная комбинация содержит k элементов, то новая кодовая комбинация – n=2k. Избыточность корреляционного кода R=0,5 .
Помехоустойчивость корреляционного кода обеспечивается тем, что появление необнаруживаемой ошибки возможно возможно только в случае, когда два рядом стоящих элемента, соответствующих одному элементу исходной кодовой комбинации будут одновременно искажены, то есть 1à0, а 0à1. Вероятность этого события
РНО=р2. В корреляционном коде в линию связи всегда передается одинаковое число 0 и 1, что обеспечивает эффективное использование ее пропускной способности.
КОДЫ С ОБНАРУЖЕНИЕМ И ИСПРАВЛЕНИЕМ ОШИБОК.
КОД ХЕММИНГА
Код Хемминга относится к блоковым кодам. Наиболее простой код, исправляющий ошибки кратности t=1, имеет кодовое расстояние d=3.
Принцип построения:
1) На передающей стороне к k информационным символам добавляется r проверочных символов. Значения проверочных символов (0 или 1) определяются путем проверок на четность. В проверку на четность включают определенные элементы кодовых комбинаций, образующие проверочную группу. Сформированный n-разрядный код, состоящий из k информационных и r проверочных элементов, передается в линию связи.