Экзамен 2021 / ОТС Лекции 1 и 2 часть

Источник создает сообщения, символы аk , которые могут принимать значения от 1 до m. Символы статистически связаны между собой – это исходный код К1. Последовательности из n символов образуют слова, статистические связи между которыми практически отсутствуют.

Осуществим укрупнение алфавита источника, будем кодировать не буквы, а целые слова Аi. Эти слова Аi являются символами нового кода К2. Вероятность символов нового кода К2 равна вероятности слов первичного кода К1 . Т.к. слово состоит из n букв , то энтропия на символ нового кода H2 больше в n раз энтропии на символ старого кода H1 .

Рассмотрим пример, который подробно изложен в описании лабораторной работы №20а. Источник двоичных сообщений A и M производит слова из двух букв (AM, MA, MM, AA); буквы в слове коррелированы, слова - некоррелированы. Статистические характеристики источника следующие:

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

Порядок расчета энтропии источника зависимых сообщений:

1)Определяем общее количество N независимых слов источника. В данном случае их 4, т.к. m =2 , и n =2 (слова состоят из двух букв) , N=22=4.

2)Определяем вероятность каждого слова:

p(AM)=p(A)*p(M/A)=0.7*0.2=0.14;

p(MA)=p(M)*p(A/M)=0.3*0.7=0.21;

p(MM)=p(M)*p(M/M)=0.3*0.3=0.09;

p(AA)=p(A)*p(A/A)=0.7*0.8=0.56;

3) Т.к. слова независимы, то энтропию источника «на слово», т.е. среднее количество информации, приходящееся на одно слово источника, найдем по формуле :

N

Hсл = −∑ pk log pk = − p(АМ) log p(АМ)− p(ММ) log p(ММ) −

k=1

−p(МА) log p(МА)− p(АА)log p(АА) =1.656 [дв.ед.] ;

слово

4) Энтропия на одну букву или символ (n=2):

H=Hсл / n = 0.828 дв.ед/символ

Рассчитаем избыточность нашего источника, т.е. степень отличия энтропии

Так как наш источник создаёт только 2 разных сообщения A и M, т.е. является двоичным источником, то его максимальная энтропия равна Hmax=log2 2 =

= 1 дв.ед./символ. Следовательно, его избыточность равна: R=(1- 0.828)/1=0.172

26

Укрупним алфавит источника и будем кодировать кодом К2 целые слова. Т.к. разных слов – 4, то нужно использовать код с основанием m=4.

АМ – первое слово S1 кодируем символом 0,

МА – второе слово S2 кодируем символом 1,

ММ – третье слово S3 кодируем символом 2,

АА – четвертое слово S4 кодируем символом 3.

Получили новый код К2 с основанием m=4, длиной комбинации n=1, общее число комбинаций N=mn=4.

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

H = = -P(S1) logP(S1) -P(S2) logP(S2) -P(S3) logP(S3) -P(S4) logP(S4) = =1.656 (дв.ед. / сообщение)

Вместо «сообщение» можно употребить термин «буква», т.к. буквами нового источника являются слова первичного источника.

Ранее для исходного первичного источника было H=0.828(дв.ед./ символ). Таким образом мы увеличили энтропию в 2 раза. Определим избыточность нового источника, для которого Нmax=log4=2(дв.ед./ символ) :

R’=1-H/Hmax=1-1.656/2= 0.172

Избыточность осталась та же. Т.о., увеличив энтропию с помощью кода К2, мы не уменьшили избыточность. Это означает, что есть возможность еще более увеличить энтропию.

4.4. Устранение корреляционных связей между символами. Кодирование с предсказанием.

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

Для устранения корреляционных связей между символами можно использовать линейное кодирование с предсказанием (Line Prediction Coding =LPC-кодер).

Слово или сегмент в последовательности из n букв, символов (х1,х2,…,хn) описывается корреляционной матрицей:

Rik - коэффициент корреляции между i-ой и k-ой буквами.

Зная предыдущие буквы, можно предсказать последующие. Предсказанное значение xk запишем в виде:

27

Ошибка предсказания равна:

xk -xk =xk -(c1x1 +c2x2 +......+ck-1xk-1)

Коэффициенты сj подбирается таким образом, чтобы обеспечить минимум среднеквадратической ошибки предсказания. Поиск минимума сводится к решению системы уравнений:

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

Алгебраическое дополнение Аij элемента аij равно определителю (минору), который получается после вычеркивания строки и столбца, в которых стоит элемент аij .

В линию связи передается ошибка предсказания. Рассмотрим простейший случай предсказания к-го символа по (к-1)-му:

xɶk = ck-1xk-1

где сk-1=R – коэффициент корреляции между к-ым и (к-1)-ым символами. В линию связи передаётся ошибка предсказания:

Дx = xk - xɶk ;

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

4.5.Увеличение энтропии дискретного источника независимых, неравновероятных сообщений с помощью неравномерного кодирования. Алгоритм Хаффмена.

Из вышеприведенного примера видно, что после укрупнения сообщений источника мы имеем те же сообщения. Они были закодированы кодом К2, энтропия которого больше, чем энтропия исходного сообщения, т.е. кода К1 . Символы нового кода независимы, некоррелированы. Однако, энтропия этого кода К2, вообще говоря, не максимальна, так как символы нового кода не равновероятны. Для дальнейшего увеличения энтропии необходимо закодировать символы кода К2 так, чтобы символы нового кода К3 были равновероятны. Это достигается неравномерным кодированием, например, в соответствии с алгоритмом Хаффмена. В соответствии с этим алгоритмом

получим код с префиксными свойствами:

более короткая кодовая комбинация не должна являться началом более длинной комбинации.

Это позволяет осуществить однозначное декодирование без разделительных символов ( в отсутствии помех). Алгоритм Хаффмена предполагает построение «кодового дерева».

28

Алгоритм построения кодового дерева:

а) Расположить исходные сообщения в порядке убывания (невозрастания) вероятностей; б) Объединить два наименее вероятных сообщения в одно, вероятность

которого равна сумме вероятностей объединяемых сообщений (точка объединения сообщений называется «узлом кодового дерева»); в) Повторять шаги а) и б) до тех пор, пока не получим одно сообщение с

вероятностью 1. Эта точка называется «вершиной кодового дерева». Например, кодовое дерево имеет вид рис.4.2 для источника сообщений, заданного в примере.

Рис.4.2.

Алгоритм кодирования слов новым двоичным кодом следующий: -идём от вершины кодового дерева к сообщению,

-если в узле мы идём вверх, то в кодовую комбинацию записывается единица, если вниз – ноль. В результате получим:

S4 => “1” ; S2 => “00” ; S1 => “011” ; S3 => “010” .

Проследите кодирование по кодовому дереву. Мы получили код К3 с префиксными свойствами.

сообщение; S3 - 9 сообщений; S4 - 56 сообщений. В соответствии с новым кодом имеем:

*14 сообщений S1, т.е. 14 символов 0 и 28 символов 1;

*21 сообщение S2, т.е. 42 символа 0;

*9 сообщений S3, т.е. 9 символов 1 и 18 символов 0; *56 сообщений S4, т.е. 56 символов 1.

Таким образом, 100 среднестатистических сообщений содержат: cимвол 0: N0 = 14*1 + 21*2 + 9*2 = 74 штуки;

cимвол 1: N1 = 14*2 +9*1 + 56*1= 93 штуки. Вероятность появления единиц и нулей:

29

Энтропия нового двоичного источника H’’:

H’’ = - p(1) log p(1) – p(0) log p(0)= - 0.557 log0.557–0.443 log0.443 = =0.994 (двоичных ед./символ)

Избыточность нового двоичного источника, существенно уменьшилась: R’’=1-0.994=0.006.

Определим среднюю длину кодовой комбинации:

k=1

рк - вероятность k-того сообщения,комбинации; nk – длина кодовой комбинации k-го сообщения. Для нашей задачи получим:

nср =0.56+ 0.14 3 + 0.21 2 + 0.09 3 = 1.67 (дв.симв. / сообщение)

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

4.6. Эффективные способы передачи Описанные методы нашли широкое применение в современных

модификациях ИКМ.

Дифференциальная ИКМ (ДИКМ). Этот способ передачи состоит в вычислении ошибки предсказания. Ошибка предсказания кодируется при меньшем числе уровней квантования. Структурная схема системы связи с ДИКМ показана на рис.4.3. Предсказатель - это трансверсальный фильтр. Его структурная схема показана на рис.4.4.

Предсказатель

Рис.4.3.

30

Каждый символ нового четверичного кода несёт уже не 1 дв.ед. информации (бит), а 2 дв.ед., т.к. при m=4 Hmax = log 4 =2 [бит/символ]. Энтропия этого кода максимальна, т.к. при равной вероятности каждого бита равновероятны и все дибиты.

Два символа двоичного кода длительностью 2Т несут, максимум, 2 бита информации (m=2; Hmax=1бит/символ; n=2; I = n * Hmax = 2бита). Один символ четверичного кода длительностью Т несет тоже 2 бита информации (m=4; Hmax=2бит/символ ; n=1; I = n * Hmax = 2 бита). Следовательно, мы в 2 раза увеличили скорость передачи информации. При этом помехоустойчивость приёма уменьшается.

5. ПОМЕХОУСТОЙЧИВОЕ КОДИРОВАНИЕ ( КАНАЛЬНОЕ КОДИРОВАНИЕ ).

5.1. Основные определения.

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

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

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

Отличие одной кодовой комбинации от другой характеризуется кодовым расстоянием. Кодовое расстояние d - это количество позиций, в которых одна

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

кодовыми комбинациями, принадлежащими коду, - это вес Хэмминга, т.е. число ненулевых символов в векторе α , равном сумме ( xi xj ) по модулю 2. Очевидно, что 1≤d(xi,xj) ≤ n. Расстояние Хэмминга удовлетворяют аксиомам: d(xi,xj) ≥0; d(xj,xj) =0; d(xi,xj)= d(xj,xi) ; d(xi,xj) ≤ d(xi,xk)+d(xk,xj).

Вектор ошибки е - это двоичная комбинация длиной n, у которой символ “1” находится в тех позициях, где переданная и принятая комбинации не совпадают. Кратность ошибки равна весу Хемминга вектора е.

Исправляющая способность кода зависит от минимального кодового

расстояния данного кода. Минимальное кодовое расстояние: dmin=min i j d(xi,xj).

Для обнаружения одиночных ошибок минимальное кодовое расстояние между комбинациями должно равняться dmin=2. Например, для двоичного кода с основанием кода m=2 и длиной n=3 возможный набор разрешенных комбинаций с dmin=2 имеет вид:

32

Предположим, что была передана комбинация 000. В линии связи помеха исказила второй символ и мы приняли 010. Это запрещенная комбинация, т.е. декодер обнаружит ошибку. Выигрыш в помехоустойчивости получен за счет проигрыша в скорости передачи, т.к. четыре сообщения мы могли бы передавать с помощью четырех комбинаций примитивного кода с m=2, n=2: 00, 01, 10, 11. Т.о. проигрыш по скорости передачи равен 1,5. Иными словами, к

кодовой комбинации из k информационных символов 00, 01, 10, 11 добавляется (n-k) избыточных или корректирующих символов, связанных по

определенному алгоритму с информационными символами. Количество корректирующих символов характеризует избыточность кода R:

R=(n-k)/n; (5.1)

Избыточность рассмотренного выше кода равна: R=(3-2)/3=0,33.

Для обнаружения ошибок кратности k следует использовать код, имеющий

dmin= k+1.

Для исправления одиночных ошибок следует использовать код с dmin=3. Например, для кода с m=2; n=3 можно использовать комбинации:

Пусть передается комбинация 000. Допустим, что помеха исказила второй символ и мы приняли 010. Эта комбинация запрещенная, но она ближе к переданной комбинации 000 (d=1), чем к другой возможной 111 (d=2). Таким образом, мы декодируем комбинацию 010 как 000, т.е. исправляем ошибку. Выигрыш в помехоустойчивости достигается за счет еще большего проигрыша в скорости передачи, т.к. два сообщения мы могли бы передавать с помощью двух комбинаций примитивного кода с m=2, n=1: т.е. 0 и 1.Таким образом, к каждой информационной комбинации из одного символа мы добавили по 2 корректирующих (проверочных) символа.

Проигрыш по скорости передачи данного кода, исправляющего одиночные ошибки, по сравнению с примитивным или безызбыточным кодом равен 3. Избыточность этого кода равна: R=(3 -1)/3=0,667.

Для исправления ошибок с кратностью k следует использовать коды с минимальным кодовым расстоянием dmin=2k+1.

Проверка на четность.

Для обнаружения одиночных ошибок одним из наиболее совершенных способов кодирования является «проверка на четность»: к кодовой

комбинации из n информационных символов добавляется один проверочный такой, чтобы количество единиц в кодовой комбинации было четным. Например, к комбинации 0100110 добавляем проверочный символ 1, и передаем комбинацию 01001101. Одиночная ошибка делает число единиц в

33

принятой кодовой комбинации нечетным ( 3 или 5), что и обнаруживается на приеме.

5.2. Линейный двоичный блочный код.

Широко используются в технике связи линейные блочные систематические коды. Блочный код состоит из кодовых комбинаций, называемых также кодовыми словами. Длина каждого кодового слова равна n. Код - систематический, т.е. первые k символов являются информационными, а следующие (n - k) являются корректирующими. Блочный код обозначается, как код (n,k). Общее количество кодовых комбинаций равно N=mk. Если код – двоичный, то N=2k.

АЛГОРИТМ КОДИРОВАНИЯ

Рассмотрим алгоритм кодирования для двоичного блочного кода (7,3), у которого каждое слово имеет n=7 символов, из которых k=3 – информационные и (n-k)=4 – проверочные.

Алгоритм формирования кодовых комбинаций следующий: 1.Присваиваем каждому символу кода номер : a1, а2, а3, а4, а5, а6, а7.

Первые три символа (a1, а2, а3) являются информационными. Последние четыре символа - корректирующие (проверочные): а4, а5, а6, а7.

2. Составляем порождающую матрицу G. Эта матрица должна иметь n столбцов и k строк. Левая часть матрицы – это единичная матрица размером k*k. Правая часть G–это матрица-дополнение Р размером (n-k)*k:

Матрица-дополнение P имеет в данном случае вид:

0 1 1 1 P = 1 0 1 1 1 1 0 1

3. Формируем кодовые комбинации. Для этого, сначала, записываем все

возможные информационные комбинации из трех символов (всего восемь комбинаций ): 000,001,010,011,100,101, 110,111.

4. К информационным символам приписываем четыре проверочных символа, получающихся в результате умножения информационного вектора-строки

(a1a2a3) на матрицу-дополнение Р. Произведение есть вектор-строка (a4a5a6a7):

(a1a2a3) * P = (а4, а5, а6, а7)

Очевидно, для заданной матрицы Р: а4 = а2 а3; a5 = a1 а3; а6 = а1 а2; а7= а1 а2 а3;

Знак означает суммирование по модулю 2, т.е. 0 0 = 0; 1 0 = 1; 0 1 = 1; 1 1 = 0.

5. Составляем кодовую таблицу разрешенных кодовых комбинаций:

34

Для полученного кода dmin = 4, т.е. наш код может исправлять все одиночные ошибки и некоторые двойные.

АЛГОРИТМ ДЕКОДИРОВАНИЯ

Однако, количество операций необходимых для такого алгоритма быстро растет с ростом n. Более оптимальным способом является вычисление синдромов.

2. Вычисляем синдром принятой кодовой комбинации, т.е. кодовую комбинацию, равную произведению принятого вектора-строки на транспонированную проверочную матрицу. Синдром не зависит от переданной комбинации. Он зависит только от позиции, в которой произошла ошибка.

где а1, а2.....а7 - принятый кодовый символ, возможно искаженный помехой.

35