Методы оптимального кодирования

7,8

Развертывание сети центров бесплатной юридической антикоррупционной помощи.

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

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

Кодированием будем считать процесс отображения одного набора знаков в другой, а кодом – множество образов при этом отображении.
Коды делятся на два вида равномерные коды и неравномерные
Равномерные коды характеризуются минимальной разрядностью кодовых слов, которая рассчитывается по формуле. для случая двоичного кода М=2
где N– объем исходного лфавита M-объем кодового лфавита B

Неравномерные коды характеризуются средней длиной кодового слова.

где li – длина кодового слова i -го символа;
pi– вероятность появления i -го символа;
N– объем исходного алфавита.

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

9
Отправитель передал сообщение, состоящее из m букв алфавита A, обладающего энтропией H(A). Количество информации в сообщении равно

Объёмом информации называется количество переданной информации, рассчитанное относительно кодового (вторичного) алфавита

где m - количество слов в сообщении

H(B)- энтропия
10

Неравномерные коды характеризуются средней длиной кодового слова.

где li – длина кодового слова i -го символа;
pi– вероятность появления i -го символа;
N– объем исходного алфавита.

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

Для оценивания оптимальности кода используют разные критерии. Основным показателем является коэффициент относительной оптимальности, вычисляемый по формуле

эта величина не превышает единицы. И чем меньше она отличается от единицы, тем более эффективным считается код.

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

1) Кодирование часто встречающихся символов более короткими кодами

2) Соблюдение принципа префиксности (никакое кодовое слово не является началом другого слова)

Этим требованиям отвечают методы Шеннона-Фано и Хаффмана

Виды кодирования:

I. Кодирование текстовой ин-фы.

II. Кодирование как средство криптографического закрытия информации

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

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

Шифр замены. При использовании данного метода буквы кодируемого сообщения заменяются буквами того же или другого алфавита. Если исходный алфавит насчитывает k символов, то существует k! способов записать сообщение с помощью символов этого же алфавита. А это значит, что существует (k! – 1) ключей.
Шифр Вижинера. Шифр Вижинера обладает более высокой степенью защиты информации, которая достигается благодаря нарушению статистистических закономерностей появления букв исходного алфавита. Вместе с тем он достаточно прост для шифрования.Прежде всего, буквы исходного алфавита объемом N нумеруются числами от 0 до N – 1 включительно. Например, буквам латинского алфавита ставятся в соответствие числа от 0 до 25. Ключом может быть произвольное слово.
Гаммирование. Идея этого метода близка к методу Вижинера. Но важное отличие состоит в том, что последовательность, выполняющая роль ключа, является псевдослучайной и генерируется с помощью датчика псевдослучайных чисел. Она называется гаммой.Исходное сообщение суммируется с гаммой по модулю N (число букв в исходном алфавите) и преобразуется так же, как в методе Вижинера.

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

Рассмотрим схему общей модели системы связи

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

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

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

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

где - Vt техническая скорость передачи информации, измеряется в бодах (1бод соответствует передаче одного элементарного сигнала с секунду); Hср- средняя энтропия алфавита, в котором передается сообщение.

Система счисления- совокупность правил наименования и записи чисел.Системы счисления подразделяются на позиционные и непозиционные.

Позиционные СС. Наиболее совершенной из позиционных систем счисления является десятичная. Значение цифры в записи десятичного числа зависит от ее позиции относительно запятой. Так, в числе x = 231,02 цифра 2 в начале записи означает две сотни, а в конце – две сотых доли единицы.

Любая Позиционная СС характеризуется основание и базисными числами/
Любая позиционная система счисления характеризуется своим основанием p и базисными числами. Основание p > 1 – целое положительное (натуральное) число. Базисные числа тоже целые, их количество равно p.

Если базисные числа образуют последовательность {0.1.2….(p-1)},где p>1 целое положительное число то это и есть основание СС

Теорема: (док-во не надо)

Если базисные числа образуют совокупность B={0.1.2…(p-1)} то любое вещественное число Х может быть представлено в виде р-ичной дроби.

I. Алгоритм замещения.

p-любое натуральное q=10

• Представить исходное число Х в виде ряда.

• Перевести основание р в десятичную СС

• Перевести коэффициенты a_i(p) в десятичную СС

• Представить Р(10) и a_i(10) в ряд и вычислить по правилам десятичной арифметики.

2. p = 10, q – любое натуральное
В данном случае целая и дробная части числа переводятся отдельно. Пусть число A = A1 + A2, где A1 – целая часть числа, A2 – дробная часть. Приведем алгоритмы перевода, отметив, что все арифметические действия выполняются по правилам десятичной арифметики.

• Переводим основание q в десятичную СС

• Разделить A на q(10) в целых числах запомнить частное B и остаток b

• Если B!=0 то A=B и возврат на шаг 2 иначе 4 шаг

• Выписать остаток в порядке обратном их получению и это даст запись числа A в q CC

III. Алгоритм последовательного умножения(для дробной части числа)

• Перевести q в десятичную СС

• Умножить A₂₍₁₀₎ на q(10) запомнить целую часть произведения А и дробную В

• Если B=0 или достигнута требуемая точность перевода то шаг 4 иначе А₂=В и шаг 2

• Выписать целые части в порядке их получения.

18
q = p^m; p, q – натуральные; m – целое положительное

В настоящем пункте приведены алгоритмы перевода чисел для случаев степенной зависимости между основаниями систем счисления.Используются 2 алгоритма: Рсщепление и групирования.
Алгоритм группирования
Шаг 1. Начиная от запятой, разбить исходную запись числа на группы по цифр, дополняя крайние неполные группы нулями.
Шаг 2. Каждую группу перевести как отдельное число в -ичную СС либо с помощью алгоритма замещения, либо с помощью таблицы -ичных эквивалентов -ичных базисных чисел.
Шаг 3. Записать полученные цифры в порядке следования групп. Полученное число считать результатом и закончить работу алгоритма.

Алгоритм расщепления
Алгоритм расщепления является обратным по отношению к алгоритму группирования. Каждая цифра -ичной записи заменяется на -разрядное -ичное число. Его можно получить с помощью алгоритма целочисленного деления либо с помощью таблицы q -ичных эквивалентов p -ичных базисных чисел.
Шаг 1. Каждую p -ичную цифру в исходной записи представить в виде m -разрядного q -ичного числа.
Шаг 2. Выписать полученные m -разрядные числа в том порядке (относительно запятой), в котором расположены в исходной записи соответствующие им p -ичные цифры.
Шаг 3. Убрать лишние нули в начале и в конце записи. Полученное число считать результатом и закончить работу алгоритма.

При переводе дробной части числа в другую систему счисления может получиться бесконечная дробь. В этом случае либо заранее ограничивают число знаков после запятой, либо рассчитывают их количество, исходя из соображений сохранения точности числа, по формуле
где m – число знаков после запятой в исходной p- ичной дроби;

k– характеризует степенную зависимость между и, т. е.;

m*k – необходимое число знаков в q- ичной дроби.

20
Округление числа в позиционных системах счисления. Поскольку все числа в ЭВМ записываются в конечную разрядную сетку, очень актуальна процедура округления числа до требуемого количества разрядов.Округлением числа x до s разрядов в заданной системе счисления называется операция замены его таким числом xs, все разряды которого, начиная с (s – 1)-го и младше, равны нулю.Простейшая процедура округления заключается в " отбрасывании" разрядов, начиная с (s – 1)-го. Таким образом, если число x имеет вид
то

Разность между округлённым и округляемым значениями называется ошибкой (погрешностью) округления:

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

Округление числа до верной цифры. Числа, представляющие собой результат вычислений или измерений, как правило, содержат ошибку и в общем случае их принято записывать в виде
В подобных случаях требуется округление числа a до верной s -й цифры as. При этом ошибка округления суммируется с исходной абсолютной погрешностью числа Пусть, начиная с (s – 1)-го разряда, все цифры числа a являются сомнительными. Обозначим сомнительную часть числа Тогда алгоритм округления до верной s -й цифры имеет вид.

где это округленное число а.

Из условия |x_s-x|<= 1\2 p^s получим СС в которой основание р нечетное

И базисные числа образуют совокупность

{-1/2(p-1), -1/2(p-3)…0….1/2(p-1)}

Такая СС называется уравновешенной

В уравновешенной СС легко реализуется округление(с минимальной ошибкой), запись отрицательных чисел и вычитание.

Дата добавления: 2015-04-23