Главная Обратная связь

Дисциплины:






Равномерные простые коды



Как следует из определения, простые равномерные коды сос­тоят из комбинаций одинаковой длины.

Пусть имеется некоторое сообщение, состоящее из М эле­ментов, представляющее собой некоторую последовательность m(m<<M) знаков (например, книга имеет M =100000 элемен­тов, представляющая собой некоторую последовательность из 32 букв, 10 цифр и 11 знаков препинания, т.е. из m = 53 знаков). Как известно, это сообщение несет некоторое количество инфор­мации I, равное:

I=log2N

где N - число возможных вариантов последовательностей из M элементов.

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

На один элемент сообщения будет приходиться в среднем количество информации:

Если каждый знак сообщения кодируется n -элементной кодовой комбинацией, состояний из двоичных символов, то каждый из них будет содержать Нэ количества информации

Очевидно, что код следует считать наилучшим с точки зрения скорости передачи тогда, когда Нэ будет максимально возможным.

Из теории информации известно, что один двоичный элемент может содержать максимальное количество информации равное 1-му биту, т.е. всегда Нэ <= I.

Следовательно, величина

может служить мерой, информационной недогрузки каждого двоич­ного элемента.

Если число знаков, из которых состоит сообщение, m=2n и все знаки равновероятны pi=1/m , то величина R = 0 Действительно.

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


где n - целое число.

 

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

Увеличение алфавита может быть достигнуто за счет того, что кодируются не только отдельные буквы (цифры), а и целые слова и даже отдельные фразы. Естественно - это вызывает не­обходимость увеличения числа регистров при использовании того же 5-элементного равномерного кода.

Неравномерные коды

Как отмечалось выше, неравномерными кодами называют такие коды, которые содержат разное число элементов.



Эти коды, как и равномерные коды, с точки зрения скорости передачи информации могут оцениваться величиной информационной недогрузки каждого двоичного символа:

где - средняя длина кодовой комбинации;

- длина комбинации, соответствующей i-му сим­волу сообщения;

- вероятность появления i-го символа в сообщении.

Если более вероятным символам сообщения сопоставить более короткие кодовые комбинации и наоборот, то средняя длина кодо­вой комбинации будет меньше, т.е. скорость передачи информа­ции таким кодом будет выше.

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

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

9 ВОПРОС





sdamzavas.net - 2018 год. Все права принадлежат их авторам! В случае нарушение авторского права, обращайтесь по форме обратной связи...