Информационные характеристики источников дискретных сообщений.

Информационные характеристики источников дискретных сообщений.

Источник сообщений является дискретным, если множество сообщений, которые могут быть им созданы конечны (или счетное). Каждое сообщение такого источника представляет собой дискретную последовательность k элементов, соответствующих одному из возможных его состояний. Все множество возможных состояний {a_m}. Любой источник, располагающий алфавитом из конечного числа элементов может образовать только конечное число различных сообщений заданной длины.

Если все одинаковой длинны К то общее число сообщений Q=m^k. Следовательно, каждое конкретное дискретное сообщение является одним из возможных и характеризуется вероятностью своего появления.

В общем случае вероятности появления различны, так как различны вероятности появления символов, но при определенной длине возможно что появления равны

Основными характеристиками является: энтропия, производительность (поток информации), избыточность.

Энтропия дискретного источника это среднее количество информации, приходящееся на элемент сообщения.

H(A) = -sum(p(ai)log(pi)

Энтропия характеризует вероятность появления символа источника и зависит только от его вероятностных характеристик.

Известно, какие могут быть состояния, известны вероятности появления этих состояний, но не известно какое состояние имеет место в данный момент. После того, как источник произвел выбор конкретного элемента, неопределенность устраняется.

H_ai­ = Log(1/p(ai))

Производительность источника сообщений. Это количество информации, вырабатываемое источником в единицу времени. Скорость создания сообщения. При отсутствии помех производительность равна энтропии приходящейся на единицу времени.

H’(A) = Ui H(A)

Ui – количество символов, вырабатываемых в единицу времени = 1/τi τi – средняя длительность выдачи источником одного знака.

H(A) – безусловная энтропия.

Повышение производительности достигается или снижением времени выдачи символа или за счет повышения энтропии.

Избыточность. Любой естественный язык обладает избыточностью. Это обеспечивает надежное общение при больших искажениях (дефекты речи, акцент и т.д.)

Различают реальные сообщения и оптимальные. Оптимальными являются сообщения, энтропия которых равна максимальному значению.

H­­_max(A) =

H­­(A) <H­­_max(A)

Коэффициент сжатия – мера количественной оценки того, насколько данное реальное сообщение отличается от соответствующего ему оптимального сообщения. µ = H­­(A)/ H­­_max(A) = n_min/n

H­­(A)*n= H­­_max(A)n_min

_­

Что б определить какая доля элементов может быть исключена используют коэффициент избыточности. Он лежит в пределах от 0 до 1.

Избыточность приводт к возрастанию времени передачи, нагрузки на канал связи, но необходимо для обеспечения помехоустойчивости.

Передача информации при отсутствии помех

k>= log(m)/log(b)

Чем меньше сигналов передатчика b тем проще передатчик, но длиннее кодовая комбинация. Необходимо решить 2 задачи кодирования:

1. Составление таких кодовых комбинаций, которые могут быть декодированные. Для этого необходимо выполнение следующих условий: каждое сообщение должно кодироваться своей, отличной от всех других кодовой комбинацией. Отличаться может и входящими сигналами и порядками их следования. При последовательной передачи должен быть введен признак, показывающий, где кончается одна кодовая комбинация, и начинается следующее. Признаком может быть одинкаовое число символов в коде (основание кода). Код – правило, по которому сопоставляется сигнал передатчика и сообщение источника.

2. Использование кода минимальной длины. В идеальном случае длинна должна быть равна энтропии источника.

Можно использовать равномерный двоичный код.

0. 0000 0000

1. 0001 0001

2. 0010 0011

3. 0011 0010

4. 0100 0110

5. 0101 0111

6. 0110 0101

7. 0111 0100

8. 1000 1100

9. 1001

10. 1010 1111

11. 1011

12. 1100

13. 1101

14. 1110

15. 1111 1000

Располагаем совместные вероятности сообщения x y . Расcчитать среднее и частное количество неопределенности в yj при известном исходе xi

-logP

-P*logP

H = -log p(xi,yj)

H = sum(sum(P(xi,yj)logP(xi,yj))) = 2,7528

Энтропия хj относительно yi

H(Yj/Xi) = -logP(Yj/Xi)

P(Yj,Xi) = P(yj) P(xi/yj) = P(xi)P(yj/xi)

P(x1) = 0,45 P(x2) = 0,38 P(x3) = 0,17

P(x/Y) = P(x,y)/P(x)

H(xi/yj)

Дискретный канал с помехами

Дискретным называется канал для передачи дискретных сигналов. Матераильным воплащение передаваемого символа является элементарный сигнал в процессе манипуляции.

Канал может иметь множество состояний, как и источник, и переходить из одного в другой как с течением времени, так и в зависимости от последовательности передаваемых символов.

X1 y1

X2 y2

. .

. .

. .

Xi yi

. .

. .

. .

Xn yn

При отсутсвии помех есть однозначное соответствие между принятыми и переданными сигналами. Помехи нарушают это соответствие, и часть инфы разрушается. Среднее количество информации, получаемое с выхода канала связи в единицу времени не соответствует среднему количеству содержащемуся во входных сообщениях той же длительности. Скорость передачи меньше пропускной способности

max{J(X,Y)} = H(X) – Y(X/Y)

теорема шеннона.

Для дискретного канала с помехами существует такой способ кодирования, при котором может быть обеспечена безошибочная передача всей информации, поступающей от источника сообщения, если только пропускная способность канала превышает производительность источника.

C = log(m) – H(X/Y) > Vi*H(X)

Пропускная способность может быть от 0 до log(m)*Vt

Для канала с шумами не указывается конкретный способ кодирования, обеспечивающее достоверную передачу информации со скоростью близкой к пропускной способностью. Указывается лишь принцып существования такого кода.

Важный вывод из теоремы: достоверность связи тем выше, чем больше длительность кодовой комбинации. Но при этом увеличивается задержка в приеме информации и менее эффективно используется пропускная способность.

Модели дискретных каналов

В каждом состоянии канал характеризуется матрицей условных вероятностей P(Yj/Xi) того, что переданный Xi будет воспринят как Yj. Значение вероятностей зависит от различных факторов, таких как свойство сигналов, характер и интенсивность помех, способ приема сигнала на приемной стороне. В зависимости от этого формируются модели.

Самая распространенная – модель стационарного канала. Канал стационарный если переходные вероятности не зависят от времени. Если зависят, что характерно для всех реальных, то канал является не стационарным.

Если переходные вероятности зависят от предыдущего состояния то канал называется с памятью.

Чаще всего используются: стационарные, дискретные, двоичные без памяти.

Если вероятности приблизительно равны,

Дискретный канал со стиранием. Алфавит выходных символов отличается от алфавита входных. На выходе фиксируется некоторое 3е состояние. Сигнал S с равной вероятностью можно считать 0 или 1. Такие символы легко исправить.

Влияние помех на качество передачи.

Помехой называется стороннее возмущение электромагнитное, электрическое, акустическое и т.д. препятствующее правильному приему полезного сигнала.

Различают внутренние помехи, если физические источники находятся в его канале, и внешние. Внутренние помехи обусловлены тепловым хаотическим движением электронов, источниками их являются электро радио элементы.

К внешним – атмосферные, космические, индустриальные, станционные.

Атмосферные помехи – грозовые разряды. Электризация антенн частицами пыли, снега. Имеют вид апериодических колебания от 0,1 до 3 мс. Уровень помех зависит от географической широты, времени года и суток. От солнечной активности и убывают с ростом частоты.

Космические помехи – радиоизлучение от солнца, галактик, радио туманностей. Уменьшаются с увеличением частоты

Станционные помехи могут быть как не намеренным или намеренным. – какая то аппаратура которая глушит сигнал. Все помехи в апп связи. Коммутационное оборудование как источник. Нелинейные искажения за счет перегрузок в групповых трактах. Влияние линий в каналах друг на друга. Общие источники питания и сам персонал. Проведение профилактических работ.

Индустриальные помехи – электроустановки, коллекторные двигателя и т.д. Асинхронные движки, коммутаторы, генераторы, городской электротранспорт, сварка. Транспорт – особенно мотоциклы.

Общие принцыипы использования избыточности

Способность кода обнаруживать и исправлять ошибки обусловлена наличием избыточных символов. Если на вход кодирующего устройства поступает последовательность из k информационных символов, на выходе ей соответствует последовательность из n двоичных последовательность. N>k.

Всего может быть 2^k входных последовательностей. И 2ⁿ выходных. Всего возможно 2^k * 2ⁿ комбинаций.

2^k случаев безошибочной передачи.

2^k * (2^k -1) – число переходов в другую разрешенную комбинацию. Это необнаруженная ошибка.

Запрещенных комбинаций 2^k * (2ⁿ -2^k ) - число случаев перехода в запрещенную комбинацию. Обнаруживаемые ошибки.

2^k * (2ⁿ -2^k ) / 2^k * 2ⁿ обнаруживающая способность кода.

Для исправления ошибки вводят большую избыточность кода.

Одной передаваемой комбинации соответствует класс полученных комбинаций.

Исправить можно столько ошибок, сколько будет запрещенных комбинаций.

Исправляющая способность = (2ⁿ -2^k )/ 2^k * (2ⁿ -2^k ) = 1/2^k = (n-k)/n

Для исправления ошибки надо все множество запрещенных кодовых комбинаций разделить на 2^k не пересекающихся подмножеств. При получении запрещенной комбинации, принадлежащей подмножеству m‑_i принимается решение, что передавалась разрешенная комбинация A_i .

Все помехоустойчивые коды характеризуются кодовым расстоянием. Обозначается d.

Кодовое расстояние это степень отличия одной кодовой комбинации от другой.

Геометрическая интерпретация кодового расстояния.

Число ребер куба, которые надо пройти от одной вершины до другой, если каждая кодовая комбинация представляется как вершина n мерного единичного куба.

Кратность ошибки – количество искаженных разрядов в кодовой комбинации. При независимых ошибках вероятности искажения любых i символов можно определить по формуле Бернули.

P_n(i) = C_nⁱ pⁱ(1-p)^n-i

S d min>t+1

Для исправления одиночной ошибки d=3. Разрешенные комбинации 000 и 111.

Для исправления ошибок надо dmin>=2S+1 (t+s+1)

Код Хеменга.

К хеменгу относят линейные коды, с кодовым расстоянием d=3, которые позволяют исправить все одиночные ошибки. Особенность Хэменга в том, что контрольное число показывает номер искаженного разряда. Для этого проверочные разряды всегда занимают одну и ту же позицию. Для 7 элементного это 1, 2, 4 позиции.

А1,а2,а3,а4,а5,А6,а7

а1 = 0001

а2 = 0010

а3 = 0011

а4=0100

а5=0101

а6=0110

а7 = 0111

а8 = 1000

а9 = 1001

а10=1010

а11=1011

записываем элементы, где есть 1 в младшем разряде (а1+а3+а5+а7) а1=а3+а5+а7

во второе уравнение записываем все, где есть 1 во втором разряде (а2+а3+а6+а7) а2=а3+а6+а7

третье уравнение с 1 в третьем разряде (а4+а5+а6+а7) а4=а5+а6+а7

к кодам Хэменга так же относят двоичные, 8 элементные, расширенные код. D=4.

К кодовым словам длины 7 добавляется еще один проверочный символ а0 сумма всех разрядов кодовой комбинации. Этот код содержит 16 кодовых слов. В случае одиночной ошибки x0 >< 0, а x1,x2,x3 образуют номер ошибочного разряда. Если двойная ошибка. X0 = 0. Или x1,x2,или x3 равно 1. Обнаружена двойная ошибка, но исправить ее нельзя.

Если информационные символы С занимают в комбинации первые 4 места, то последующие контрольные символы образуются по следующей контрольной правило.

Декодирование производится путем 3х проверок на четность.

X1=e1’+e1” = e1’+∑αCi

Ошибочным информационный символ может быть любым.

X1=e1’+c2’+c3’+c4

X2=e2’+c1+C3+c4

X3=e3’+c1+c2+c4

Пример комбинация 1100

Е1=1+0+0=1

Е2=1+0+0=1

Е3=1+1+0=0

Приняли 0100110

Х1=1+1+0+0=0

Х2=1+0+0+0 = 1

Х3=0+0+1+0=1

Получили 011 что по таблице мы получаем, что неисправно С1.

Циклические коды

Циклические коды относятся к блочным линейным кодам. Код называется циклическим, если любая его комбинация может быть получена из исходного путем циклического сдвига всех элементов на 1 шаг.

При одном шаге символы перемещаются справа налево на одну позицию, причем символ, выходящий за границу разрядности переносится на место крайней правой позиции. Основным свойством циклического кода является возможность представления кодовой комбинации полиномом n-1 степени. Коэффициентами которого являются символы кодовой комбинации.

10011 = 1Х4 + 0Х³ + 0Х2+1Х1+1Х0

При образовании циклического кода должны выполняться все действия по следующим правилам:

1. Сложение по модулю 2.

2. Вычитание идентично сложению по модулю 2.

3. Умножение выполняется по обычным правилам с приведением подобных членов по модулю 2.

Если старшая степень полученного полинома не превышает n-1, то результат является окончательным. Если он превышает, то полином делится на xⁿ⁺¹. Результатом умножения считается остаток от деления.

Линейность циклических кодов вытекает из того, что любая линейная композиция 2х циклических комбинаций, делящихся на G(x) будет обязательно делиться на этот же образующийся полином.

Способы задания циклического кода.

1. С помощью образующего полинома G(x)

2. С помощью образующей матрицы.

3. С помощью корней образующего полинома. БЧХ.

Рассмотрим процедуру кодирования.

1. Первичную информационную последовательность представим в виде полинома k-1 степени.

A^*(x)

2. Умножить A^*(x) * x^r это соответствует к приписыванию к кодовой комбинации r нулей справа.

3. Полином должен быть не приводимым. То есть делится на себя и на 1.

4. Делим на образующий полином. Остаток записываем вместо r нулей.

5. F(x) = A*(x)

A*(x) =1001 = X3+0X2+0x1+1x0 = X3+1

(X3+1)*x3 = X6+x3

G(x) = x3+x+1

(X6+x3)/(x3+x+1) = x3 (x2+1) – остаток

Х6+х3+х2+х

Декодирование. На приемной стороне принятую кодовую комбинацию делят на образующий полином.

B(x) = F(x) +N(x)

N(x) – полином, соответствующий коду ошибки, имеющему единицу на месте искаженного символа и нули на всех остальных позициях.

При делении B(x) на G(x) ошибка может быть обнаружена, если полином N(x) не делится на G(x) без остатка. Исправлено может быть столько ошибок, сколько может быть получено разных остатков при делении различных полиномов G(x).

Основа кодирующего регистра – 2 регистра на r разрядов, накопитель и регистр сдвига с обратными связями. Регистр сдвига состоит из ячеек памяти и сумматоров по модулю 2. Операция умножения соответствует наличию обратной связи. Если коэффициент для образующего кода равна 0, то связь отсутствует. Сдвиг осуществляется тактовыми импульсами от специального генератора. Число сумматоров равно числу не нулевых членов образующего полинома -1 для старших разрядов. Место включения сумматоров определяются структурой образующего полинома. В исходном состоянии ключи разомкнуты. В течении r тактов символы заполняют накопитель и разряды регистра сдвига. Затем ключ k1 остается разомкнут, ключ 2 замкнут. Происходит деление в течении k+1 тактов. За это время на выход поступает k информационных разрядов. Накопитель освобождается, а в регистр сдвига записывается остаток. Ключ 2 размыкается, ключ 1 замыкается и на выход кодирующего устройства поступает устройство R(x) и одновременно записывается следующая комбинация. И цикл повторяется. Недостаток – рассчитан на конкретный полином и конкретную ошибку. Так же задержка на r тактов.

Задание. Кодовая комбинация

Закодировать ее с проверкой на четность, инверсным кодом, циклическим кодом (указан полином) x4 + x3 + 1.

четный 100100011,0

инверсный 100100011,100100011 (после запятой инверсная, если число 1 не четное)

X8+X5+X1+X0.

(X8+X5+X1+X0)*Х4 = X12+x9+x5+x4

(X12+x9+x5+x4)/(X4+x3+1) = (x8+X7+X6+x4+x2) + X2

X12+x9+x5+x4+x2

1001000110100.

Системы с обратной связью

Эти системы – адаптивны, то есть приспосабливаются к качеству канала связи. Чем хуже качество канала, тем большее число раз повторяется одна и та же информация.

Общая схема

Недостатки – скорость ниже.

Все системы с обратной связи можно классифицировать по типу связи, способу функционирования, методу проверки принимаемых сигналов, величине коэффициента повторения, способу повторения, емкости памяти.

В зависимости от типа обратной связи бывают:

1. Системы с информационной обратной связью

2. С решающей обратной связью

3. Комбинированная обратная связь.

В системах с информационной обратной связи решение о правильности принятой информации принимается на передающий стороне. Для этого по обратному каналу посылается квитанция сигнала принятого в прямом канале.

Решающее устройство сравнивает полученную квитанцию с фактически переданном сигнале. При совпадении подтверждается правильность приема, и за тем передается следующий рабочий сигнал. В этих системах характерна малая избыточность при высокой верности.

В системах с решающей обратной связью решение принимается на принимающей стороне. Для этого по обратному каналу посылается сигнал подтверждения, либо запрос на повторение той же самой информации, если обнаружена ошибка. Избыточность тут больше. Загрузка обратного канала меньше, чем у систем с информационной обратной связью.

В системах с комбинированной обратной связью решение может приниматься и на передающей стороне. Решающее устройство отвергает наименее достоверные сигналы, и требует их повторение. На остальные сигналы подается квитанция подтверждение.

Информационные характеристики источников дискретных сообщений.

Источник сообщений является дискретным, если множество сообщений, которые могут быть им созданы конечны (или счетное). Каждое сообщение такого источника представляет собой дискретную последовательность k элементов, соответствующих одному из возможных его состояний. Все множество возможных состояний {a_m}. Любой источник, располагающий алфавитом из конечного числа элементов может образовать только конечное число различных сообщений заданной длины.

Если все одинаковой длинны К то общее число сообщений Q=m^k. Следовательно, каждое конкретное дискретное сообщение является одним из возможных и характеризуется вероятностью своего появления.

В общем случае вероятности появления различны, так как различны вероятности появления символов, но при определенной длине возможно что появления равны

Основными характеристиками является: энтропия, производительность (поток информации), избыточность.

Энтропия дискретного источника это среднее количество информации, приходящееся на элемент сообщения.

H(A) = -sum(p(ai)log(pi)

Энтропия характеризует вероятность появления символа источника и зависит только от его вероятностных характеристик.

Известно, какие могут быть состояния, известны вероятности появления этих состояний, но не известно какое состояние имеет место в данный момент. После того, как источник произвел выбор конкретного элемента, неопределенность устраняется.

H_ai­ = Log(1/p(ai))

Производительность источника сообщений. Это количество информации, вырабатываемое источником в единицу времени. Скорость создания сообщения. При отсутствии помех производительность равна энтропии приходящейся на единицу времени.

H’(A) = Ui H(A)

Ui – количество символов, вырабатываемых в единицу времени = 1/τi τi – средняя длительность выдачи источником одного знака.

H(A) – безусловная энтропия.

Повышение производительности достигается или снижением времени выдачи символа или за счет повышения энтропии.

Избыточность. Любой естественный язык обладает избыточностью. Это обеспечивает надежное общение при больших искажениях (дефекты речи, акцент и т.д.)

Различают реальные сообщения и оптимальные. Оптимальными являются сообщения, энтропия которых равна максимальному значению.

H­­_max(A) =

H­­(A) <H­­_max(A)

Коэффициент сжатия – мера количественной оценки того, насколько данное реальное сообщение отличается от соответствующего ему оптимального сообщения. µ = H­­(A)/ H­­_max(A) = n_min/n

H­­(A)*n= H­­_max(A)n_min

_­

Что б определить какая доля элементов может быть исключена используют коэффициент избыточности. Он лежит в пределах от 0 до 1.

Избыточность приводт к возрастанию времени передачи, нагрузки на канал связи, но необходимо для обеспечения помехоустойчивости.