Помехоустойчивое кодирование, распознавание символов (стр. 2 из 5)
Х1=(0 0 0) Х2=(1 1 1)
Вероятность каждого из них определяется по формуле:
(1.1.7)где к=0,1;
- количество элементов «к» в коде Zi.При передаче Xк по каналу связи возможны ошибки с вероятностями, определяемыми следующим образом:
P10=0.2 + 0.02A (1.1.8)
P01=0.2 + 0.02B (1.1.9)
где р10 – вероятность принятия нуля при передаче единицы;
р01 – вероятность принятия единицы при передаче нуля;
А, В – заданные величины.
В дальнейшем, для удобства будут использоваться следующие принятые обозначения:
Х - передаваемый код;
Y - принимаемый код.
При построении канальной матрицы P(Y/X) воспользуемся тем, что при передаче может произойти ошибка лишь в одном разряде X1 или X2.
Тогда в 1 строке матрицы элементы определятся следующим образом:
1 – p01 , i = 1P(xi,yj) = P01/3 , i = 2,3,4. (1.1.10)
0 , i = 5,6,7,8.
Элементы канальной матрицы совместной вероятности P(X,Y) определяются по формуле:
P(xi,yj)=P(xi)P(yj/xi) (1.1.11)
Зная матрицу совместной вероятности P(X,Y), можно вычислить элементы матрицы вероятностей P(Y). Они находятся по формуле:
P(yi)=P(x1,yi)+ P(x2,yi) (1.1.12)
В свою очередь, формула для расчета элементов матрицы условной вероятности P(X/Y) имеет вид:
P(xi/yj)=P(xi,yj)/P(yj) (1.1.13)
Энтропия передаваемого сигнала H(X), бит/символ и принимаемого сигнала H(Y), бит/символ определяется соответственно по формуле:
(1.1.14)
(1.1.15)Условные энтропии H(X/Y), бит/символ и H(Y/X), бит/символ рассчитываются соответственно по формулам:
(1.1.16)
(1.1.17)Совместная энтропия H(X,Y), бит/символ находится по формуле:
(1.1.18)Взаимная энтропия I(X,Y), бит/символ определяется по формуле:
(1.1.19)Передача информации по каналу связи осуществляется со скоростью V, рассчитываемой по формуле:
V = 1000(A+1) (1.1.20)
Постоянную скорость передачи двоичных символов по каналу связи R, бит/с можно рассчитать по формуле:
R = V × I(X,Y) / 3; (1.1.21)
Производительность источника
, бит/с определяется по следующей формуле:
= (H(X) × V ) (1.1.22)1.2 ПОЛУЧЕННЫЕ РЕЗУЛЬТАТЫ
По условию варианта определены следующие постоянные:
m = 15;
r = 10;
Определим характеристики посылаемых символов.
Вероятности символов Vi(они же - вероятности кода Zi), генерируемых источником рассчитываем по формуле 1.1.1. Полученные значения вероятностей приведены в таблице 1.2.2.
Сначала вероятности строятся по убыванию. После этого все вероятности делятся на две группы так, чтобы в пределах каждой группы их значения были примерно одинаковыми. В старший разряд кодов, соответствующих первой группе вероятностей, записывается 1,для второй группы кодов – 0. Затем каждая из полученных подгрупп, в свою очередь, делится аналогичным образом. При прохождении цикла деления по одному разряду происходит переход на разряд вправо. Деление продолжается до тех пор, пока в каждой группе не окажется по одному коду.
Результаты разработки кодов показаны в таблице 1.2.1.
Таблица 1.2.1 - Вероятности и коды символов
| Vi | P(Vi) | Zi | L(Zi) |
| 1 | 0.231 | 11 | 2 |
| 2 | 0.183 | 10 | 2 |
| 3 | 0.1408 | 011 | 3 |
| 4 | 0.1042 | 0101 | 4 |
| 5 | 0.0732 | 01001 | 5 |
| 6 | 0.0732 | 01000 | 5 |
| 7 | 0.0479 | 00111 | 5 |
| 8 | 0.0479 | 00110 | 5 |
| 9 | 0.0282 | 00101 | 5 |
| 10 | 0.0282 | 00100 | 5 |
| 11 | 0.0141 | 00011 | 5 |
| 12 | 0.0141 | 00010 | 5 |
| 13 | 0.0056 | 000011 | 6 |
| 14 | 0.0056 | 000010 | 6 |
| 15 | 0.0028 | 000000 | 6 |
Вычислим энтропию сообщения H(Z),бит/символ по формуле
1.1.2 :
H(Z) = 3.218 бит/символ
Среднюю длину неравномерного кода определим по формуле
1.1.3 :
Lср = 3.5652 бит
Максимальную энтропию неравномерного двоичного кода Zi определяем по формуле 1.1.4:
H(Z)max = 3.218 бит
По формуле 1.1.5 вычислим коэффициент эффективности Кэф неравномерного двоичного кода Zi:
Кэф = 0.903
Для расчета коэффициента избыточности Кизб воспользуемся формулой 1.1.6:
Кизб = 0.176
При простом кодировании повторением n=3 раз каждого двоичного сигнала сообщения Zi имеется два кода: Х1 и Х2, вероятности которых Р(Х1) и Р(Х2) находятся по формуле 1.1.7:
Р(Х1) = 0.4113 Р(Х2) = 0.5885
Вероятности возможных ошибок, при прохождении кода по каналу определяются по формулам 1.1.8 и 1.1.9 соответственно:
P10 = 0.3 P01 = 0.2
Канальная матрица P(Y/X) со стороны приемника для кода Х0 и Х1, рассчитанная по формуле 1.1.10, приведена в таблице 1.2.3. Для проверки расчета в последнем столбце таблицы 1.2.3 приведена сумма по текущей строке. Значения вероятностей в таблице 1.2.3 приводятся в десятитысячных долях единицы.
Таблица 1.2.2 - Канальная матрица P(Y/X)
| X | Y | сумма | |||||||
| 000 | 001 | 010 | 100 | 011 | 101 | 110 | 111 | ||
| 000 | 8000 | 0667 | 0667 | 0667 | 0000 | 0000 | 0000 | 0000 | 10000 |
| 111 | 0000 | 0000 | 0000 | 0000 | 1000 | 1000 | 1000 | 1000 | 10000 |
В таблице 1.2.3 приведены значения элементов канальной матрицы совместной вероятности P(X,Y), определенные по формуле 1.1.11. Значения вероятностей в таблице 1.2.3 приводятся в десятитысячных долях единицы.
Таблица 1.2.3 - Матрица совместных вероятностей P(X,Y)
| Х | Y | |||||||
| 000 | 001 | 010 | 100 | 011 | 101 | 110 | 111 | |
| 000 | 3292 | 0274 | 0274 | 0274 | 0000 | 0000 | 0000 | 0000 |
| 111 | 0000 | 0000 | 0000 | 0000 | 0588 | 0588 | 0588 | 4119 |
Элементы матрицы вероятностей P(Y) находятся по формуле 1.1.12. Полученные данные приведены в таблице 1.2.4 в десятитысячных долях единицы. В последнем столбце для проверки приведена сумма по строке.
Таблица 1.2.4 - Матрица P(Y)
| Y | Сумма | |||||||
| 000 | 001 | 010 | 100 | 011 | 101 | 110 | 111 | |
| 3292 | 0274 | 0274 | 0274 | 0588 | 0588 | 0588 | 4119 | 10000 |
Рассчитав матрицы P(X,Y) и P(Y), можно вычислить элементы матрицы условной вероятности P(X/Y) по формуле 1.1.13. Матрица P(X/Y) приведена в таблице 1.2.6.
Рассчитываем энтропию передаваемого сигнала H(X) и энтропию принимаемого сигнала H(Y) по формулам 1.1.14 и 1.1.15 соответственно:
H(X) = 0.9777 бит/символ
H(Y) = 2.2025 бит/символ
Условные энтропии H(X/Y) и H(Y/X) рассчитаем, воспользовавшись формулами 1.1.16 и 1.1.17 соответственно:
H(X/Y) = 0.0000 бит/символ
H(Y/X) = 1.2244 бит/символ
Таблица 1.2.5 - Матрица P(X/Y)
| X | Y | Сумма | |
| 000 | 111 | ||
| 000 | 1 | 0 | 1.0000 |
| 001 | 1 | 0 | 1.0000 |
| 010 | 1 | 0 | 1.0000 |
| 100 | 1 | 0 | 1.0000 |
| 011 | 0 | 1 | 1.0000 |
| 101 | 0 | 1 | 1.0000 |
| 110 | 0 | 1 | 1.0000 |
| 111 | 0 | 1 | 1.0000 |
По формуле 1.1.18 находим совместную энтропию H(X,Y):
H(X,Y) = 2.2014 бит/символ
Сделаем проверку полученных значений энтропий:
H(Y/X) + H(X) = 2.2025 бит/символ
H(X/Y) + H(Y) = 2.2025 бит/символ
Совпадение полученных значений свидетельствует о правильности найденных значений энтропий.
Определим значение взаимной энтропии I(X,Y), используя формулу 1.1.19:
I(X,Y) = 0.9777 бит/символ
Для отыскания следующих характеристик канала вычислим скорость передачи двоичных символов по каналу связи с помощью формулы 1.1.20:
V = 6000 символов/c
Информация передается по каналу связи с постоянной скоростью R, вычисляемой с помощью формулы 1.1.21:
R = 1956.1 бит/с
Производительность источника по формуле 1.1.22 равна:
= 5868.3 бит/сРезультатом работы программы являются графики числа ошибок восстановления информации от параметра n (n,1) – кода и от p01 и p10. При теоретическом расчёте мы предположили, что в канале нет ошибок. Действительно, полученное нулевое значение энтропии H(X/Y) также об этом свидетельствует.
Однако полученный график говорит о том, что это предположение становится соответствующим действительности только начиная со значений n, равных 20..25.
Примерный вид полученных графиков приведен на рисунках 1.2.1 и 1.2.2.
 |
45
Количество
ошибок,%
15
20 40 60 100
Количество повторений, n
Рисунок 1.2.1 – Число ошибок восстановления
 |
100