Гост-алгоритм

Обладает 256-битным ключом и в настоящее время считается лучшим алгоритмом шифрования.

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

7.2. Компрессия данных Эффективное кодирование

Основная теорема Шеннона для передачи информации по каналу без помех:

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

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

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

Код Шеннона-Фано

Строится алфавит сообщения. Для каждого символа определяется вероятность его появления в сообщении. Алфавит упорядочивается по значению вероятности. Затем алфавит делится на две группы таким образом, чтобы суммарная вероятность групп была примерно одинаковой. Первому биту кода символа присваивается ‘0’ для символов первой группы и ‘1’ для символов второй группы. Затем каждая группа рассматривается отдельно, процедура деления повторяется для вновь получившихся групп. Эта процедура заканчивается, когда в группе остается один символ

Код Хаффмана

Код Хаффмана обладает большей эффективностью по сравнению с кодом Шеннона-Фано, за счет того, что во время кодирования символы объединяются в группы, которые затем рассматриваются как отдельные символы алфавита, которые на каждом шаге переупорядочиваются в соответствии с новым значением вероятности групповых символов.

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

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

По таблице кодирования строится дерево. В корне – единичная вероятность и соответствующие ей символы алфавита. Из корня выходят две ветви – в узлы, соответствующие предпоследнему столбцу таблицы. Листья дерева – единичные символы алфавита. Всем левым ребрам (соответствующим меньшей вероятности) присваивается код ‘0’, правым – ‘1’. Код символа определяется при восходящем движении от листа к корню.

7.3. Кодирование информации при передаче по каналу с помехами

Основная теорема Шеннона:

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

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

Кодирование должно осуществляться так, чтобы сигнал, соответствующий принятой последовательности символов после воздействия на него предполагаемой помехи, оставался ближе к сигналу, соответствующего переданной последовательности, чем к сигналам, соответствующим другим возможным последовательностям символов. Это достигается введением при кодировании избыточности, которая позволяет так выбрать передаваемую последовательность символов, чтобы они удовлетворяли условиям, проверка которых на принимающей стороне дает возможность обнаружить и исправить ошибку. Этот класс кодов называют помехоустойчивым. Коды, позволяющие исправлять ошибки, называюткорректирующими. В них для каждой комбинации информационных символов значение кода может иметь неединственное значение, т.е. для каждой исходной комбинации существует некоторое множество закодированных комбинаций, каждая из которых позволяет восстановить исходную. В результате воздействия помехи, приводящей к изменению внутри допустимого множества, не влияет на правильность результата. Например, корректирующие коды в ЭВМ СМ-420, в которых 16 бит представляются в виде 23бит, значение которых вычисляется по специальным формулам, позволяющим собой полином некоторой степени, позволяют обнаруживать двойные ошибки и исправлять одиночные. Проверка четности, применяемая в модулях памятиDRAM,DDRсовременных ПК, позволяют обнаруживать единичные ошибки. Интегрированный кэш современных процессоров осуществляет проверку с помощью циклических кодов. Такая же ЕЦЦпроверка имеется в так называемой серверной памяти (которая предназначена для использования в серверах; стоимость такой памяти на порядок выше).

Необходимость применения корректирующих кодов определяется с помощью теории вероятности. По оценке фирмы IBMв 2000 года, в ОЗУ емкостью 256 Мб возможно появление ошибки в течение одного месяца. К основным причинам возникновения ошибок в ОЗУ относят космическое излучение.