Методы оптимального кодирования. 1) Кодирование часто встречающихся символов более короткими кодами

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

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

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

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

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

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

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

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

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

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

1. 14( Общее описание системы связи. Пропускная способность канала связи. )

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

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

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

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

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

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

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

1. 15( Позиционные системы счисления. Основание, базисные числа. )

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

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

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

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

16 (Теорема о представлении чисел в натуральной системе счисления (формулировка).)

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

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

1. 17( Алгоритмы перевода чисел из десятичной системы счисления в другую натуральную систему счисления и наоборот. )

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. Убрать лишние нули в начале и в конце записи. Полученное число считать результатом и закончить работу алгоритма.

1. 19( Сохранение точности чисел при переводе их в другую натуральную систему счисления. )

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

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

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

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

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

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

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

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

1. 21( Зависимость ошибки округления от выбора системы счисления. Уравновешенные системы счисления. )

Зависимость ошибки округления от выбора системы счисления определяется формулой

где Xs -число все разряды которого, начиная с (s – 1)-го и младше, равны нулю.
ps – единица s –го разряда
Cистема счисления, базисные числа которых образуют последовательность

называется уравновешаной системой счисления. Например троичная уравновешаная система: основание p=3, базисные числа образуют совокупность (-1;0;1)

22( Способы представления чисел в ЭВМ. Описание разрядных сеток с фиксированной и плавающей запятой. )

Представление числа в ЭВМ осуществляется с помощью конечного набора базовых элементов, каждый из которых "запоминает" один разряд числа. Совокупность таких элементов называется разрядной сеткой. Точность представления числа в ЭВМ зависит от количества элементов в разрядной сетке и от способа их использования. Так, разрядные сетки бывают двух типов – с фиксированной запятой (ФЗ) и с плавающей запятой (ПЗ).

Разрядная сетка с фиксированной запятой – это конечная разрядная сетка, в которой строго фиксировано число разрядов для представления целой части числа и дробной части числа (т. е. по сути фиксировано положение запятой.

В машинах чаще используются сетки ФЗ двух типов: а – запятая зафиксирована после последнего разряда и б – запятая зафиксирована перед первым разрядом числа (рис.11.1). Нулевой разряд сетки отведен под код знака числа. Знак числа кодируется нулем, если число положительное, и числом (p – 1), где p – основание системы счисления, если число отрицательное. Вес каждого разряда указан над ним.

a)

б)

Разрядная сетка с плавающей запятой состоит как бы из двух сеток с фиксированной запятой: ФЗ, а и ФЗ, б, причем в сетку типа а заносится порядок числа, в сетку типа б – мантисса числа

1. 23,24( Диапазоны представимых чисел в форме с фиксированной запятой/ Диапазон представимых чисел в форме с плавающей запятой. )

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