9.Кодирование информации. Префиксный код Хаффмана.

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

Префиксный код Хаффмана. Алгоритм Хаффмана – адаптивный жадный алгоритм оптимального префиксного кодирования с минимальной избыточностью.

Классический алгоритм Хаффмана на входе получает таблицу частот встречаемости символов в сообщении. Далее на основании этой таблицы строится дерево кодирования Хаффмана (Н-дерево). 

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

2. Выбираются два свободных узла дерева с наименьшими весами.

3. Создается их родитель с весом, равным их суммарному весу.

4. Родитель добавляется в список свободных узлов, а два его потомка удаляются из этого списка.

5. Одной дуге, выходящей из родителя, ставится в соответствие бит 1, другой — бит 0.

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

10. Циклический код. Свёрточный код. Кодовое расстояние. Систематические коды. Контроль по чётности/нечётности, код Хемминга. Преффиксный код Хаффмана. Код Грея. Самоконтролирующиеся и самокорректирующиеся коды. Контрольные суммы.

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

Свёрточный код — это корректирующий ошибки код, в котором

(a) на каждом такте работы кодера символов входной полубесконечной последовательности преобразуются всимволов выходной, и

(b) в преобразовании также участвуют предыдущих символов;

(c) выполняется свойство линейности (если двум кодируемым последовательностям и соответствуют кодовые последовательности и , то кодируемой последовательности соответствует).

Свёрточный код является частным случаем древовидных и решетчатых кодов.

Кодовое расстояние- Расстоянием d_ij между кодами (кодовыми комбинациями) i и j называется число различных разрядов в кодовых комбинациях i и j. Например, если есть коды 01 и 10, расстояние между ними равно 2: они различаются в двух разрядах.

Систематический код - код, содержащий в себе кроме информационных контрольные разряды.

В контрольные разряды записывается некоторая информация об исходном числе. Поэтому можно говорить, что систематический код обладает избы-точностью. При этом абсолютная избыточность будет выражаться количеством контрольных разрядов k, а относительная избыточность - отношением k/n, где n=m+k - общее количество разрядов в кодовом слове (m - количество информационных разрядов)

Контроль Четности и Нечетности - Контроль на чётность (нечётность) заключается в следующем: к передаваемым байтам данных (8 бит) добавляется 1 контрольный бит. Контрольный бит вычисляется по следующему правилу: если в информационном байте число единиц четное, то контрольный бит равен 1. При этом общее число единиц передаваемой информации должно быть нечетным. Данный способ контроля не позволяет обнаружить ошибки четной кратности (т.е. ошибки одновременно в двух, четырех и т.д. битах) и поэтому используется при невысоких требованиях к достоверности принимаемых данных (или при малой вероятности ошибок в линии передачи).

Код Хэмминга - Коды, предложенные Р. Хэммингом, обладают способностью обнаружить и исправить одиночные ошибки. Предположим, что имеется код, содержащий m информационных разрядов и k контрольных разрядов. Запись на k позиций определяется при проверке на четность каждой из проверяемых k групп информационных символов. Пусть было проведено k проверок. Если результат проверки свидетельствует об отсутствии ошибок, запишем 0, если есть ошибка - 1. Запись полученной последовательности символов образует двоичное число.Свойство кодов Хэмминга таково, что контрольное число указывает номер позиции, где произошла ошибка. При отсутствии ошибки в коде данная последовательность будет содержать только нули. Полученное число описывает таким образом n=(m+k+1) событий. Следовательно, справедливо неравенство

Префиксный код Хаффмана. Алгоритм Хаффмана – адаптивный жадный алгоритм оптимального префиксного кодирования с минимальной избыточностью. Классический алгоритм Хаффмана на входе получает таблицу частот встречаемости символов в сообщении. Далее на основании этой таблицы строится дерево кодирования Хаффмана (Н-дерево). 

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

8. Выбираются два свободных узла дерева с наименьшими весами.

9. Создается их родитель с весом, равным их суммарному весу.

10. Родитель добавляется в список свободных узлов, а два его потомка удаляются из этого списка.

11. Одной дуге, выходящей из родителя, ставится в соответствие бит 1, другой — бит 0.

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

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

Самокорректирующиеся и самоконтролирующиеся коды –

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

Языки программирования С. Основные алгоритмы.

1. Формы записи алгоритмов: язык псевдокода, блок-схема.

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

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

Пример:

"Начало Объявить массив i Открыть файл Считать из файла строку Добавить строку в массив i Закрыть файл Вывести кол-во элементов массива i Конец"

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