WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!

Pages:     | 1 ||

«В. В. Лидовский ТЕОРИЯ ИНФОРМАЦИИ В. В. ЛИДОВСКИЙ ТЕОРИЯ ИНФОРМАЦИИ Допущено учебно-методическим объединением вузов по университетскому политехническому образованию в качестве учебного пособия для ...»

-- [ Страница 2 ] --

Упражнение Построить кодовые слова квазисовершенного (9, n)-кода, исправляюще го однократные ошибки, для тех сообщений, которые соответствуют числам 55, 200 и декодировать слова 1000001000001, 1100010111100, по лученные по каналу связи, использующему этот код.

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

Пусть a = a0... am-1 — двоичное сообщение. Тогда сопоставим ему многочлен a(x) = a0 + a1x + · · · + am-1xm-1. Все вычисления про исходят в поле классов вычетов по модулю 2, т. е. от результата любой арифметической операции берется остаток от его деления на 2.

Например, последовательности 10011 при m = 5 соответствует многочлен 1 + x3 + x4.

Зафиксируем некоторый многочлен степени k, g(x) = g0 + g1x + · · · + gkxk, g0 = 0, gk = 0.

Полиномиальный код с кодирующим многочленом g(x) кодирует слово сообщения a(x) многочленом b(x) = a(x)g(x) = b0 + b1x + · · · + bn-1xn- или кодовым словом из коэффициентов этого многочлена b = b0... bn-1.

Условия g0 = 0 и gk = 0 необходимы, потому что в противном случае b0 и bn-1 не будут нести никакой информации, т. к. они всегда будут нулями.

Пример. Рассмотрим кодирующий многочлен g(x) = 1 + x2 + x3.

Сообщение 01011, отвечающее многочлену a(x) = x + x3 + x4, будет закодировано коэффициентами многочлена b(x) = g(x)a(x) = x+x5+x7, т.е. b = 01000101.

Полиномиальный код с кодирующим многочленом g(x) степени k является матричным кодом с кодирующей матрицей G размерности m (m + k):

g0 g1 g2 · · · gk 0 0 · · · 0 g0 g1 · · · gk-1 gk 0 · · · G = 0 0 g0 · · · gk-2 gk-1 gk · · · 0.

· · · · · · · · · · · · · · · · · · · · · · · · · · · 0 0 0 · · · · · · · · · · · · · · · gk Т.е. ненулевые элементы в j-й строке — это последовательность коэф фициентов кодирующего многочлена, расположенных с j-го по (j + k)-й столбцах.

Например, (3, 6)-код с кодирующим многочленом 1+x+x3 отвечает матрице 1 1 0 1 0 G = 0 1 1 0 1 0 0 1 1 0 или отображению: 000 000000;

001 001101;

010 011010;

010111;

100 110100;

101 111001;

110 101110;

111 100011.

Полиномиальные коды являются групповыми.

Это следует из того, что коды, получаемые матричным кодированием, — групповые.

Рассмотрим (m, n)-код с кодирующим многочленом g(x). Строка ошибок e = e0... en-1 останется необнаруженной в том и только в том случае, если соответствующий ей многочлен e(x) = e0 + e1x + · · · + en-1xn-1 делится на g(x).

Действительно, a(x)g(x) + e(x) делится на g(x) тогда и только тогда, когда e(x) делится на g(x). Поэтому любая ошибка, многочлен которой не де лится на g(x), будет обнаружена и, соответственно, любая ошибка, многочлен которой делится на g(x), не может быть обнаружена.

Таким образом, обнаружение ошибки при использовании полино миального кода с кодирующим многочленом g(x) может быть реали зовано при помощи алгоритма деления многочленов с остатком: если остаток ненулевой, то при передаче произошло искажение данных.

Коды Хэмминга можно строить как полиномиальные, например, кодирующий многочлен x3 + x2 + 1 определяет совершенный (4, 7)-код, отличный от рассмотренного ранее.

Вообще же, если кодирующий многочлен g(x), порождающий соот ветствующий (m, n)-код, не является делителем ни одного из многочле нов вида xj + 1 при j < n, то минимальное расстояние между кодовыми словами порожденного им кода не меньше 3.

Пусть d — минимальное расстояние между кодовыми словами, оно равно минимуму среди весов ненулевых кодовых слов. Предположим d = 2. Тогда существует a(x) такой, что a(x)g(x) = b(x) и степень b(x) не больше n. Вес b равен 2, поэтому b(x) = xm + xl и l < m < n. Следовательно, b(x) = xl(xm-l + 1), что означает, что xm-l + 1 должен делиться на g(x), а это невозможно по условию. Если предположить, что d = 1, то это приведет к утверждению о том, что xm должен делиться на g(x), что тоже противоречит условию. Итак, d 3.

Кодирующий многочлен x11 + x9 + x7 + x6 + x5 + x + 1 определяет совершенный (12, 23)-код Голея (Golay) с минимальным расстоянием между кодовыми словами 7.

В 1971 году финскими и советскими математиками было доказано [20], что кроме кодов Хэмминга и Голея других совершенных кодов нет.

Наиболее интересными среди полиномиальных кодов являются циклические коды, в которых вместе с любым кодовым словом вида b0... bn-2bn-1 есть кодовое слово bn-1b0... bn-2.

Упражнение По кодирующему многочлену x7 +x5 +x+1 построить полиномиальные коды для двоичных сообщений 0100, 10001101, 11110.

Упражнение Принадлежат ли коду Голея кодовые слова 10000101011111010011111 и 11000111011110010011111?

26. Понятие о кодах Боуза-Чоудхури-Хоккенгема Остался открытым вопрос о методике построения кодов, мини мальное расстояние между кодовыми словами которых равно заданно му числу. В 1960 году независимо Боуз (Bose), Чоудхури (Chaudhuri) и Хоккенгем (Hocquengem) открыли способ построения полиномиальных кодов, удовлетворяющих таким требованиям. Эти коды получили на звания кодов Боуза-Чоудхури-Хоккенгема или БЧХ-кодов (BCH codes).

БЧХ-коды могут быть не только двоичными, например, на практи ке достаточно широко используются недвоичные коды Рида-Соломона (Reed, Solomon), но далее будут рассматриваться только двоичные.

Многочлен g(x) степени k называется примитивным, если xj + делится на g(x) без остатка для j = 2k - 1 и не делится ни для какого меньшего значения j.

Например, многочлен 1 + x2 + x3 примитивен: он делит x7 + 1, но не делит xj + 1 при j < 7. Примитивен также многочлен 1 + x3 + x4 — он делит x15 + 1, но не делит xj + 1 при j < 15.

Кодирующий многочлен g(x) для БЧХ-кода, длина кодовых слов которого n, строится так. Находится примитивный многочлен мини мальной степени q такой, что n 2q - 1 или q log2(n + 1). Пусть — корень этого многочлена, тогда рассмотрим кодирующий мно гочлен g(x) = НОК(m1(x),..., md-1(x)), где m1(x),..., md-1(x) — многочлены минимальной степени, имеющие корнями соответственно, 2,..., d-1.

Построенный кодирующий многочлен производит код с минималь ным расстоянием между кодовыми словами, не меньшим d, и длиной кодовых слов n [1].

Пример. Нужно построить БЧХ-код с длиной кодовых слов n = и минимальным расстоянием между кодовыми словами d = 5. Степень примитивного многочлена равна q = log2(n + 1) = 4 и сам он равен x4 + x3 + 1. Пусть — его корень, тогда 2 и 4 — также его корни.

Минимальным многочленом для 3 будет x4 + x3 + x2 + x + 1. Следова тельно, g(x) = НОК(x4 + x3 + 1, x4 + x3 + x2 + x + 1) = = (x4 + x3 + 1)(x4 + x3 + x2 + x + 1) = x8 + x4 + x2 + x + 1.

Степень полученного многочлена равна 8, следовательно, построенный БЧХ-код будет (7, 15)-кодом. Слово 1000100 или a(x) = x4 + 1 будет закодировано кодовым словом a(x)g(x) = x12 + x6 + x5 + x2 + x + 1 или 111001100000100.

Можно построить [1] двоичный БЧХ-код с кодовыми словами дли ны n = 2q - 1 и нечетным минимальным расстоянием d, у которого q(d - 1) число контрольных символов не больше.

Первый БЧХ-код, примененный на практике, был (92, 127)-кодом, исправляющим ошибки кратности до 5, но наиболее широкое распро странение получил (231, 255)-код, обнаруживающий ошибки кратности до 6.

БЧХ-коды умеренной длины не слишком далеки от совершенных или квазисовершенных кодов. Коды Хэмминга, например, являются БЧХ-кодами, а БЧХ-коды с минимальным весом кодового слова 5 — квазисовершенны. Но с ростом длины кодовых слов качество БЧХ-кодов падает. Код Голея, например, — это не код БЧХ.

Упражнение Найти кодирующий многочлен БЧХ-кода g(x) с длиной кодовых слов и минимальным расстоянием между кодовыми словами 7. Использовать примитивный многочлен m1(x) = 1 + x + x4 с корнем. Проверить, будут ли 3 и 5 корнями соответственно многочленов m3(x) = 1 + x + x2 + x3 + x4 и m5(x) = 1 + x + x2.

27. Циклические избыточные коды Циклический избыточный код (Cyclical Redundancy Check — CRC) имеет фиксированную длину и используется для обнаружения ошибок.

Наибольшее распространения получили коды CRC-16 и CRC-32, имею щие длину 16 и 32 бита соответственно. Код CRC строится по исходно му сообщению произвольной длины, т.е. этот код не является блочным в строгом смысле этого слова. Но при каждом конкретном применении этот код — блочный, (m, m + 16)-код для CRC-16 или (m, m + 32)-код для CRC-32.

Вычисление значения кода CRC происходит посредством деле ния многочлена, соответствующего исходному сообщению (полином сообщение), на фиксированный многочлен (полином-генератор). Оста ток от такого деления и есть код CRC, соответствующий исходно му сообщению. Для кода CRC-16 полином-генератор имеет степень 16, а для CRC-32 — 32. Полиномы-генераторы подбираются специаль ным образом и для кодов CRC-16/32 стандартизированы Международ ным консультативным комитетом по телеграфной и телефонной свя зи (CCITT). Для CRC-16, например, стандартным является полином генератор x16 + x12 + x5 + 1.

Пример построения CRC-4 кода для сообщения 11010111, используя полином-генератор x4+x3+x2+1. Исходному сообщению соответствует полином x7 +x6 +x4 +x2 +x+1, т.е. нумерация битов здесь начинается справа.

x7 + x6 + x4 + x2 + x + 1 x4 + x3 + x2 + x7 + x6 + x5 + x3 x3 + x x5 + x4 + x3 + x2 + x + x5 + x4 + x3 + x x2 + Полиному x2 + 1 соответствуют биты 0101 — это и есть CRC-4 код.

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

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

Коды CRC используются очень широко: модемами, телекоммуника ционными программами, программами архивации и проверки целост ности данных и многими другими программными и аппаратными ком понентами вычислительных систем.

Упражнение Построить CRC-4 код для сообщений 10000000 и 101111001, используя полином-генератор x4 + 1.

28. Основы теории защиты информации Криптография (тайнопись) — это раздел математики, в котором изучаются и разрабатываются системы изменения письма с целью сде лать его непонятным для непосвященных лиц. Известно, что еще в V веке до нашей эры тайнопись использовалась в Греции. В современ ном мире, где все больше и больше услуг предоставляется через ис пользование информационных технологий, проблема защиты информа ции методами криптографии имеет первостепенное значение. Сегодня большая часть обмена информацией проходит по компьютерным сетям и часто (в бизнесе, военным и прочее) нужно обеспечивать конфиден циальность такого обмена. Теоретические основы классической крип тографии впервые были изложены Клодом Шенноном в конце 1940-х годов.

Простейшая система шифрования — это замена каждого знака письма на другой знак по выбранному правилу. Юлий Цезарь, напри мер, заменял в своих секретных письмах первую букву алфавита на четвертую, вторую — на пятую, последнюю — на третью и т.п., т.е. A на D, B на E, Z на C и т.п. Подобные шифры, называемые простой за меной или подстановкой, описаны в рассказах “Пляшущие человечки” А. К. Дойла, “Золотой жук” Э. По и других.

Шифры простой замены легко поддаются расшифровке, при зна нии исходного языка сообщения, т.к. каждый письменный язык харак теризуется частотой встречаемости своих знаков. Например, в англий ском языке чаще всего встречается буква E, а в русском — О. Таким образом, в шифрованном подстановкой сообщении на русском языке са мому частому знаку будет с большой вероятностью соответствовать буква О. Вероятность будет расти с ростом длины сообщения.

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

В шифрах-перестановках знаки сообщения специальным образом переставляются между собой, например, записывая сообщение в стро ки заданной длины и беря затем последовательность слов в столбцах в качестве шифра. Сообщение “ТЕОРИЯИНФОРМАЦИИ”, используя строки длины 4, будет в шифрованном таким методом виде выглядеть как “ТИФАЕЯОЦОИРИРНМИ”, потому что при шифровании исполь зовался следующий прямоугольник:

ТЕОР ИЯИН ФОРМ АЦИИ.

Шифры-перестановки в общем случае практически не поддаются дешифровке. Для их дешифровки необходимо знать дополнительную информацию. Крупный недостаток подобных шифров в том, что ес ли удастся каким-то образом расшифровать хотя бы одно сообщение, то в дальнейшем можно расшифровать и любое другое. Модифика цией шифров-перестановок являются шифры-перестановки со словом ключом, которое определяет порядок взятия слов-столбцов. Например, если для рассмотренного шифра взять ключ “РЫБА”, то шифрованное сообщение будет выглядеть как “РНМИОИРИТИФАЕЯОЦ”.

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

Наиболее простой способ использования ключа хорошего шифра следующий: под символами сообщения записывается раз за разом ключ, затем номера соответствующих знаков сообщения и ключа складыва ются. Если полученная сумма больше общего числа знаков, то от нее отнимается это общее число знаков. Полученные числа будут номера ми символов кода. С ростом длины ключа трудоемкость дешифровки подобного шифра стремительно растет. Например, рассмотренное ра нее сообщение с ключом “КИБЕРНЕТИКА” в шифрованном виде бу дет выглядеть как “ЮОРЦЪНОБЮЪСШЙШОЪ”. Процесс шифровки описывается схемой:

Т Е О Р И Я И Н Ф О Р М А Ц И И 20 6 16 18 10 33 10 15 22 16 18 14 1 24 10 К И Б Е Р Н Е Т И К А К И Б Е Р 12 10 2 6 18 15 6 20 10 12 1 12 10 2 6 32 16 18 24 28 15 16 2 32 28 19 26 11 26 16 Ю О Р Ц Ъ Н О Б Ю Ъ С Ш Й Ш О Ъ.

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

В информационных сетях использование традиционных систем шифрования с ключом затрудненно необходимостью иметь специаль ный особо защищенный способ для передачи ключа. В 1976 году У. Диф фи (Diffie W.) и М. Хеллман (Hellman M.) — инженеры-электрики из Станфордского университета, а также студент Калифорнийского уни верситета Р. Меркль (Merkle R.), предложили новый принцип постро ения криптосистем, не требующий передачи ключа принимающему со общение и сохранения в тайне метода шифрования. В дальнейшем, в ка честве примеров, рассмотрим три системы, основанные на идеях Диффи и Хеллмана: без передачи ключей, с открытым ключом и электронную подпись — все они в свою очередь основаны на математическом фун даменте теории чисел.

Упражнение Зашифровать сообщение “КИБЕРНЕТИКА” ключом “ДИСК”.

29. Криптосистема без передачи ключей Пусть абоненты A, B, C,... условились организовать между собой секретную переписку. Для этой цели они выбирают достаточно боль шое простое число p такое, что p - 1 хорошо разлагается на не очень большие простые множители. Затем каждый из абонентов независимо один от другого выбирает себе некоторое натуральное число, взаимно простое с p - 1. Пусть число абонента A — a, абонента B — b и т. д.

Числа a, b,... составляют первые секретные ключи соответствующих абонентов. Вторые секретные ключи ( для A, для B и т. д.) нахо дятся из уравнений: для A из a 1 (mod (p)), 0 < < p - 1;

для B — из b 1 (mod (p)), 0 < < p - 1 и т.д. Пересылаемые сообще ния, коды-числа, должны быть меньше p-1. В случае, когда сообщение больше или равно p-1, оно разбивается на части таким образом, чтобы каждая часть была числом, меньшим p - 1.

Предположим абонент A решил отправить сообщение m (m < p-1) B. Для этого он сначала зашифровывает свое сообщение ключом a, по лучая по формуле m1 ma (mod p) шифрованное сообщение m1, кото рое отправляется B. B, получив m1, зашифровывает его своим ключом b, получая по формуле m2 mb (mod p) шифрованное сообщение m2, которое отправляется обратно к A. A шифрует полученное сообщение ключом по формуле m3 m (mod p) и окончательно отправляет m3 к B. B, используя ключ, сможет теперь расшифровать исходное сообщение m. Действительно, m4 m mab m (mod p), т. к.

ab 1 (mod (p)), следовательно, ab = k(p) + 1 для некото рого целого k и mk(p)+1 (m(p))km m (mod p), т. к. m(p) (mod p) по теореме Эйлера-Ферма.

Пример. Абоненты A и B вместе выбрали p = 23 ((23) = 22), A выбрал a = 5, а B — b = 7. Затем из уравнения 5 1 (mod (23)) A находит = 9, а B из подобного уравнения находит = 19. При передаче сообщения m = 17 от A к B сначала A отправляет к B m 175 21 (mod 23), из m1 = 21 B вычисляет m2 217 10 (mod 23) и отправляет его обратно A, из m2 = 10 A вычисляет для B m3 20 (mod 23), наконец, B может прочитать посланное ему сообщение 2019 17 (mod 23).

Упражнение Между абонентами A и B установлен секретный канал связи без пе редачи ключей при заданных p = 167 и их первых ключах 15 и 21.

Описать процесс передачи сообщений 22 (от A к B) и 17 (от B к A).

30. Криптосистема с открытым ключом Первую и наиболее известную систему с открытым ключом раз работали в 1978 году американцы Р. Ривест (Rivest R.), Э. Шамир (Shamir A.) и Л. Адлеман (Adleman L.). По их именам эта система получила название RSA.

Пусть абоненты A и B решили организовать для себя возможность секретной переписки. Для этого каждый из них независимо выбирает два больших простых числа (pA, pA и pB, pB ), находит их произведе 1 2 1 ние (rA и rB), функцию Эйлера от этого произведения ((rA) и (rB)) и случайное число (a и b), меньшее вычисленного значения функции Эйлера и взаимно простое с ним. Кроме того, A из уравнения a (mod (rA)) находит (0 < < (rA)), а B из уравнения b (mod (rB)) находит (0 < < (rB)). Затем A и B печатают доступ ную всем книгу паролей вида:

A: rA, a.

B: rB, b Теперь кто-угодно может отправлять конфиденциальные сообще ния A или B. Например, если пользователь книги паролей хочет от править сообщение m для B (m должно быть меньшим rB, или де литься на куски, меньшие rB), то он использует ключ b из книги паро лей для получения шифрованного сообщения m1 по формуле m1 mb (mod rB), которое и отправляется B. B для дешифровки m1 исполь зует ключ в формуле m mb m (mod rB), т. к. b (mod (rB)), следовательно, b = k(rB) + 1 для некоторого целого k и B B B mk(r )+1 (m(r ))km m (mod rB), т.к. m(r ) 1 (mod rB) по теореме Эйлера-Ферма. Доказано [12], что задача нахождения секрет ного ключа по данным из книги паролей имеет ту же сложность, что и задача разложения числа rB на простые множители.

Пример. Пусть для A pA = 7 и pA = 23, тогда rA = pA pA = 161, 1 2 1 (161) = 6 22 = 132, a = 7, = 19 (из уравнения 7 1 (mod 132)).

Следовательно, запись в книге паролей для A будет иметь вид A: 161, 7.

Если кто-то захочет отправить A секретное сообщение m = 3, то он должен сначала превратить его в шифровку m1 по формуле m1 94 (mod 161). Когда A получит m1 = 94 он дешифрует его по формуле m 9419 3 (mod 161).

Упражнение Нужно послать секретные сообщения 25 и 2 для JB и 14 для CIA, используя следующие записи открытой книги паролей криптосистемы RSA:

JB: 77,7;

CIA: 667,15.

Упражнение Пользователь системы RSA выбрал p1 = 11 и p2 = 47. Какие из чисел 12, 33, 125, 513 он может выбрать для открытого ключа? Вычислить для них закрытый ключ.

Упражнение Пользователь системы RSA, выбравший p1 = 17, p2 = 11 и a = 61, получил шифрованное сообщение m1 = 3. Дешифровать m1.

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

Пусть W1, W2,..., Wn — абоненты системы с электронной подпи сью. Все они независимо друг от друга выбирают и вычисляют ряд чисел точно так же как и в системе с открытым ключом. Пусть i-ый абонент (1 = i n) выбирает два больших простых числа pi1 и pi2, затем вычисляет их произведение — ri = pi1pi2 и функцию Эйлера от него — (ri), затем выбирает первый ключ ai из условий 0 < ai < (ri), НОД(ai, (ri)) = 1 и, наконец, вычисляет второй ключ i из уравнения aii 1 (mod (ri)). Записи в книге паролей будут иметь вид:

W1: r1, a W2: r2, a.

· · · Wn: rn, an Если абонент W1 решает отправить секретное письмо m W2, то ему следует проделать следующую последовательность операций:

1) Если m > min(r1, r2), то m разбивается на части, каждая из кото рых меньше меньшего из чисел r1 и r2;

2) Если r1 < r2, то сообщение m сначала шифруется ключом 1 (m m (mod r1)), а затем — ключом a2 (m2 ma (mod r2)), если же r1 > r2, то сообщение m сначала шифруется ключом a2 (m ma (mod r2)), а затем — ключом 1 (m2 m (mod r1));

3) Шифрованное сообщение m2 отправляется W2.

W2 для дешифровки сообщения m2 должен знать, кто его отправил, поэтому к m2 должна быть добавлена электронная подпись, указываю щая на W1. Если r1 < r2, то для расшифровки m2 сначала применяется ключ 2, а затем — a1, если же r1 > r2, то для расшифровки m2 сна чала применяется ключ a1, а затем — 2. Рассмотрим случай r1 < r2:

2 2 m ma 2 m1 (mod r2) и ma m a1 m (mod r1) по теореме 2 1 Эйлера-Ферма.

Пример. Пусть W1 выбрал и вычислил следующие числа p11 = 7, p12 = 13, r1 = p11p12 = 91, (91) = 72, a1 = 5, 1 = 29, а W2 — следу ющие p21 = 11, p22 = 23, r2 = 253, (253) = 220, a2 = 31, 2 = 71. После занесения записей о W1 и W2 в открытую книгу паролей, W2 решает послать сообщение m = 41 для W1. Т.к. r2 > r1, то сообщение сначала шифруется ключом a1, а затем ключом 2: m1 415 6 (mod 91), m2 671 94 (mod 253). Сообщение m2 отправляется W1. Получив m2 = 94, W1, зная, что оно пришло от W2, дешифрует его сначала клю чом a2, а затем ключом 1: 9431 (mod 253) 6, 629 (mod 91) 41.

Если подписать сообщение открытым образом, например, именем отправителя, то такая “подпись” будет ничем не защищена от поддел ки. Защита электронной подписи обычно реализуется с использованием таких же методов, что в криптосистеме с открытым ключом.

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

Стандартные системы электронной подписи считаются настолько надежными, что электронная подпись юридически приравнена к руко писной. Электронная подпись часто используется с открытыми, неза шифрованными электронными документами.

32. Стандарт шифрования данных В 1977 году в США был предложен стандарт для шифрования дан ных — DES (Data Encryption Standard), разработанный в IBM. В он был одобрен ведущей мировой организацией по стандартам — AN SI. В настоящее время алгоритм DES широко используется для защиты коммерческой информации.

DES — это классическая криптосистема с открытым способом шифровки и дешифровки, секретность которой обеспечивается исклю чительно ключом. Основные достоинства DES:

• используется только один ключ фиксированной длины 56 бит (в системах с открытым ключом длина ключа должна быть более 300 бит);

• зашифровав сообщение с помощью одной программы, для расшиф ровки можно использовать другую;

• относительная простота алгоритма обеспечивает высокую ско рость работы (как минимум, на порядок выше скорости работы алгоритма для криптосистемы с открытым ключом);

• достаточно высокая стойкость алгоритма (стойкость конкретного зашифрованного сообщения зависит от выбора ключа).

Главный недостаток DES связан с его классической организацией, т.е. с необходимостью обеспечивать сверхнадежный канал для переда чи ключей.

Алгоритм DES предназначен для шифровки ровно 64 бит исход ных данных — более длинные сообщения должны разбиваться на части длиной 64 бита, а более короткие дополняться нулями или пробелами.

Собственно шифровка и дешифровка обеспечиваются многократными битовыми перестановками в исходном сообщении, определяемыми стан дартными перестановочными матрицами и ключом.

Примером программы, реализующей алгоритм DES, является про грамма DISKREET из пакета Norton Utilities.

33. Информация в Internet Самый распространенный тип данных в компьютерном мире — это текстовые файлы, которые непосредственно в той или иной мере по нятны для человека, в отличие от бинарных файлов, ориентированных исключительно на компьютерные методы обработки. С использованием текстовых файлов связаны две проблемы.

Первая заключается в сложности единообразного представления символов текста. Для представления английских текстов достаточно ASCII. Для работы с другими языками на основе латинского алфави та, языками на основе кириллицы и некоторыми другими нужно уже несколько десятков наборов расширенного ASCII. Это означает, что одному и тому же коду, большему 127, в каждом наборе соответствует свой символ. Ситуацию усложняет и то, что для некоторых языков, в частности, русского существует несколько наборов ASCII+. Кроме то го, необходимо, чтобы все символы каждого языка помещались в один набор, что невозможно для таких языков, как китайский или японский.

Таблица кодировки Unicode, предназначенная для постепенной замены ASCII, — 16-разрядная, что позволяет представить 65536 кодов. Она широко используется в Linux и Microsoft Windows. Варианты Unicode позволяют использовать 31-разрядное кодирование. Использование Uni code требует переделки всех программ, рассчитанных для работы с текстами ASCII.

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

Компьютерный шрифт — это набор именованных кодами рисун ков знаков.

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

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

Внесение в простой текст (plain text) дополнительной информации об его оформлении или структуре осуществляется при помощи размет ки текста (markup). Различают физическую или процедурную размет ку и логическую или обобщенную разметку.

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

Для печати документа на принтере или показе на экране использу ется физическая разметка. Исторически она появилась первой, но име ет очевидные недостатки. Например, в Америке и Европе существуют разные стандарты на размер писчей бумаги, наборы шрифтов и раз мер экрана меняются от системы к системе, — подобные обстоятель ства требуют трудоемкого изменения физической разметки текста при использовании одного и того же документа на разных компьютерах.

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

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

Основные форматы текста с разметкой:

1) HTML — Hyper Text Markup Language, язык разметки гипертек ста;

2) XML — eXtensible Markup Language, расширяемый язык разметки;

3) SGML — Standard Generalized Markup Language, стандартный язык обобщенной разметки;

4) TEX;

5) PostScript;

6) PDF — Portable Document Format, формат для переносимых доку ментов, или Acrobat (частично бинарный).

Документы в Internet часто публикуются в обработанном програм мами сжатия данных виде. Наиболее используемые форматы сжатия — это zip и tgz (tar.gz). Формат tgz — это результат конвейерного приме нения команд: сначала tar (собирает файлы и каталоги в один файл с сохранением структуры каталогов) и затем gzip.

Часто в Internet нужно преобразовывать бинарные данные в тек стовые (для отправке по электронной почте, например) и затем наобо рот. Для этого, в частности, служат программы uuencode (перевести в текст) и uudecode (перевести из текста). В текстовом файле закодиро ванный текстом бинарный файл помещается между строками, начина ющимся со слов begin и end. Строка begin должна содержать атрибуты и имя бинарного файла.

34. HTML, XML и SGML World Wide Web (WWW, всемирная паутина) базируется на трех стандартах: URI (Universal Resource Identifier, универсальный иденти фикатор ресурса, раньше назывался URL) — предоставляет стандарт ный способ задания местоположения любого ресурса Internet, HTTP (Hyper Text Transfer Protocol, протокол передачи гипертекста), HTML — язык страниц WWW.

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

Документы HTML из-за содержащихся в них, как правило, большого количества ссылок на другие документы HTML, с которыми они обра зуют единое целое, мало приспособлены для распечатки на принтере.

Имя файла с документом HTML имеет обычно расширение html или htm. Существуют ряд программ, позволяющих создавать докумен ты HTML в визуальном режиме и не требующих от их пользователя знания HTML. Но создать сложный интерактивный документ без та кого знания непросто.

Элементы разметки HTML состоят из тегов (tag). Теги заключа ются в угловые скобки, у них, как правило, есть имя и они могут иметь дополнительные атрибуты. Например, тег A HREF=”http://www.

linux.org” имеет имя A (anchor, якорь), атрибут HREF со значением “http://www.linux.org”.

Некоторые теги самодостаточны, например, тег разрыва строки BR (break), но большинство тегов — это пары из открывающего (start tag) и закрывающего (end tag) тегов. Имя закрывающего тега отличается от имени открывающего только тем, что перед ним ставит ся наклонная черта (slash). Например, если имя открывающего тега A, то имя закрывающего — /A. Открывающий и закрывающий теги об рамляют некоторый фрагмент текста, вместе с которым они образуют элемент текста. Элементы текста могут быть вложенными.

Парные теги EM (emphasis, выделение), STRONG (особо выде лить), CITE (цитата или ссылка), CODE (компьютерная программа), SAMP (sample, текст примера), STRIKE (зачеркнуть) и некоторые дру гие позволяют логически выделить фрагменты текста, а парные теги B (bold, полужирный), I (italic, курсив), U (undelined, подчеркнутый), TT (typewriter, пишущая машинка), SUB (subscript, нижний индекс), SUP (superscript, верхний индекс) и другие — рекомендовать физически выделить фрагмент текста указанным образом.

Полный документ представляет собой один элемент текста HTML.

Заголовки — это элементы H1, H2, H3 и т. д. Число после H (header) — это уровень вложенности заголовка, т. е. H1 — это заголовок всего документа, H2 — заголовок раздела документа, H3 — подраздела и т.д.

Абзацы — это элементы P (paragraph). Элементы PRE (preformatted) должны отображаться браузером с таким же разбиением на строки как и в исходном документе.

Специальные символы можно ввести в документ, используя их име на (entity), заключенные между знаками & и точка с запятой. Напри мер, сам знак & можно ввести как &

, а знак кавычка — "

.

Ссылки и маркеры, объявляются при помощи атрибутов HREF и NAME соответственно. Например, элемент A NAME=”chapter3” /A — это метка, на которую можно ссылаться по имени chapter3, исполь зуя, например, ссылку A HREF=”#chapter3” Глава 3 /A.

Тег IMG (image, образ) позволяет вставить графическую картинку в документ, используя два основных атрибута: SRC (source, источник) для указания URI файла с графикой и ALT (alternative, альтернатива) для указания альтернативного текста, показываемого вместо картинки, в случае, когда файл с графикой недоступен или его тип неизвестен браузеру.

Документы HTML могут быть использованы для интерактив ной работы. Например, элемент FORM позволяет пользователю web страницы передать введенную в страницу информацию на HTTP сервер. Элемент FORM может содержать разнообразные кнопки, спис ки, всплывающие меню, однострочные и многострочные текстовые по ля и другие компоненты. Обработкой введенных, переданных на сервер данных и созданием динамических HTML-документов в ответ на них занимаются специальные программы, CGI-скрипты (common gate in terface), установленные на сервере.

Комментарии вводятся между символами !-- и --.

HTML содержит средства для описания данных в виде таблиц и ис пользования таблиц стилей. HTML использует стандартные системные шрифты, т.е. не существует шрифтов специально для www-страниц.

Имена файлов-документов SGML, как правило, имеют расширение sgml. SGML с начала 1970-х разрабатывался фирмой IBM, а с 1986 года принят в качестве международного стандарта (ISO 8879) для формата документов с логической разметкой. Сначала документ SGML содержит описание вида кодирования и разметки текста и затем сам размечен ный текст. HTML — это SGML с фиксированной разметкой. Создатели технологии WWW отказались от полной поддержки SGML только по тому, что в начале 1990-х системы, которые могли работать с SGML в реальном времени были очень дороги.

Элементы SGML делятся на четыре категории:

1) описательные маркеры — определяют структуру документа — им соответствуют элементы разметки HTML типа H1, P, A, IMG и т.п.;

2) ссылки на данные — им соответствуют элементы разметки HTML типа &

3) описательные конструкции компонент документа в их структурной взаимосвязи — они не входят в HTML, но определяют его. Их реко мендуется начинать с комбинации знаков ! и заканчивать знаком. Примером конструкции, определяющей ссылку &ref;

на словосо четание “The Reference” будет !ENTITY ref"The Reference" ;

4) инструкции по обработки текста — их рекомендуется заключать между знаками ? и — они вводят элементы текста, ориентиро ванного на конкретную, зависящую от системы обработку (физи ческую разметку). В HTML с их помощью, например, вставляют код для обработки на сервере WWW страниц.

Документы SGML можно конвертировать как в гипертекст, так и в любой формат, ориентированный на распечатку, например, TEX или Microsoft Word. Ведение документации в формате SGML во многих отношениях оптимально.

С 1996 официально идет разработка формата XML — подмноже ства SGML, которое предполагается использовать в Internet наряду с HTML. Преимущество XML перед HTML в его четкой связи с SGML, что позволяет стандартным образом вводить в документ новые кон струкции, избегая тем самым неконтролируемого введения в язык но вых возможностей, как это происходит с HTML.

Упражнение Как на HTML описать заголовок первого уровня “Глава 2”, на который можно будет ссылаться по имени “2”?

35. TEX Известный американский математик и теоретик программирова ния Дональд Кнут (D. E. Knuth) более 10 лет с конца 1970-х годов разрабатывал систему верстки книг TEX (произносится “тех”). Суще ствует множество расширений возможностей базового (plain) TEX. TEX популярен прежде всего в академических кругах, т.к. в целом он весь ма сложен для изучения. В отличие от систем, ориентированных на интерпретацию разметки, подобных Microsoft Word или Sun Star Writ er, TEX — компилирующая система. Результат компиляции докумен та TEX — это файл в бинарном формате dvi (device independent), ко торый можно, используя драйверы конкретных устройств (принтеров, экрана), распечатать. TEX использует собственную систему масшта бируемых шрифтов, которые масштабируются не в реальном времени, интерпретацией как шрифты True Type или PostScript, а компиляци ей при помощи программы METAFONT. В Internet доступны тексты программ TEX и METAFONT — они написаны на Паскале. Шрифты METAFONT написаны на специальном языке, с декларативным синтак сисом. TEX позволяет также использовать шрифты True Type и Adobe Type 1 и Type 3. Прочитать и понять содержимое документа TEX не сложно, но скомпилировать и распечатать, а тем более создать новый документ без помощи специалиста или основательной подготовки не просто. Однако TEX до сих пор является почти единственной доступной бесплатно системой, позволяющей получать документы типографского качества. В plain TEX используется физическая разметка, а в наибо A лее популярном его расширении L TEX также и логическая. TEX — это язык макросов, большинство из которых начинаются с символа обрат ная косая черта и состоят затем из букв. Например, запись в документе plain TEX \centerline{Это {\it мой} заголовок} означает центрировать строку-абзац “Это мой заголовок”, напечатав слово “мой” в нем курси вом, а запись $$\int 1x{dt\over t}=\ln x$$ — формулу x dt = ln x.

t TEX — это особый язык программирования. Энтузиасты TEX написа ли на нем интерпретатор языка Бэйсик. Документы TEX могут иметь очень сложную структуру и из-за этого их в общем случае нельзя кон вертировать в другие форматы. Документы HTML или Microsoft Word теоретически можно всегда конвертировать в формат TEX.

Система GNU texinfo основана на TEX, но использует совершенно другой набор макросов. Макросы в этой системе должны начинаться со знака @. Документы texinfo можно преобразовать как в документ HTML, так и в качественную распечатку. В отличие от SGML, средства для такого преобразования — это часть системы texinfo. Возможности texinfo для верстки документов несколько ограниченней по сравнению с другими развитыми TEX-системами.

A Расширения имен файлов документов TEX — tex;

L TEX — tex, latex, ltx, sty (стили) и др.;

METAFONT — mf (исходные программы шрифтов), tfm (метрики шрифтов, нужны на этапе компиляции доку мента TEX), pk (матрицы шрифтов, нужны при печати dvi-файла);

tex info — texi, texinfo.

36. PostScript и PDF PostScript — это универсальный язык программирования (имеет много общего с языками Форт и Лисп), предоставляющий большой на бор команд для работы с графикой и шрифтами. Он является факти ческим международным стандартом издательских систем. Разрабаты вается фирмой Adobe Systems с первой половины 1980-х. Использует ся, как встроенный язык принтеров для высококачественной печати, а также некоторыми системами X Window при выводе данных на экран дисплея. Существуют и программы-интерпретаторы языка PostScript.

Лучшая из них — это Ghostscript. Программа GhostView предостав ляет удобный оконный интерфейс для Ghostscript и существует для большинства ОС.

PostScript-программы можно писать вручную, но обычно текст PostScript генерируется автоматически программами вывода данных.

Расширения имен файлов с PostScript-программой — это, как прави ло, ps, eps (Encapsulated PostScript, файл-картинка с заданными раз мерами), pfa (шрифт), pfb (бинарное представление pfa), afm (метри ки шрифта, могут быть частично получены из соответствующего pfa файла), pfm (бинарное представление afm).

Преимущество формата PostScript в том, что он, как и формат DVI, независим от физических устройств воспроизведения. Один и тот же PostScript-файл можно выводить как на экран с разрешением 72 dpi (dot per inch, точек на дюйм) или лазерный принтер с разрешением 600 dpi, так и на типографскую аппаратуру с разрешением 2400 dpi, имея гарантии, что изображение будет наилучшего качества, возмож ного на выбранной аппаратуре. Возможности PostScript перекрывают возможности DVI, поэтому некоторые TEX-системы при компиляции документов производят сразу файлы в формате PostScript или PDF.

Файлы PostScript можно вручную корректировать, но из-за слож ности языка — это очень не просто, особенно если используются сим волы, не входящие в ASCII. Фактически эти файлы можно рассмат ривать как “только для чтения” и использовать для распространения информации, не подлежащей изменению. Комментарии в PostScript, как и в TEX, начинаются знаком % и заканчиваются концом строки. Пер вая строчка PostScript-программы обычно содержит точное название формата файла. Собственно программа начинается в файле с символов %! и заканчивается символами %%EOF. PostScript-программы кроме собственной системы шрифтов могут использовать шрифты True Type фирм Apple и Microsoft.

Различают уровни (levels) языка PostScript. Уровень 1 может под держивать только черно-белую графику. Уровень 2 может работать с цветом. Уровень 3 — это современное состояние языка.

Данные из файла PostScript можно показывать по мере их поступ ления, что удобно для использования в Internet. Однако есть две причи ны, по которым документы PostScript сравнительно редко включаются в web-страницы:

1) они весьма велики по размерам (этот недостаток снимается про граммами сжатия, работающими в реальном времени);

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

Файлы в формате PDF лишены двух означенных недостатков: они сжаты и из них сложно извлечь отдельные шрифты, — поэтому они стали фактическим стандартом Internet для обмена документами, не подлежащими изменению. Программы для просмотра PDF-файлов до ступны бесплатно. Наиболее используемая из них — это Adobe Acrobat Reader. Первая строчка файла в формате PDF начинается со знака %, за которым следует идентификационная запись версии формата PDF, используемой в этом файле. Далее, как правило, идут бинарные данные.

Расширение имени PDF-файла — pdf.

Между документами PostScript и PDF можно осуществлять взаим но-однозначное преобразование, хотя PDF в отличие от PostScript — это не язык программирования, а скорее язык описания документа.

Приложение А. Ответы на все упражнения 1. 87 и 119.

2. 24 КГц.

3. 8192.

4. x = 5.

5. HX = 0.9 + log2 5 - 0.3 log2 3 2.75 бит/сим.

6. I(Y, X1) = 0.5 бит/сим.

7. I(Z, X1) = I(X1, X1) = HX1 = 1 бит/сим, т. е. Z полностью определяет X1 и, следовательно, X1 — это функцией от Z. HZ = бит/сим.

8. I(X1, X2) = (5 - 3 log2 3)/3 0.08 бит/сим.

9. I(X1, Y ) = (10 - 3 log2 3)/8 0.66 бит/сим, HX1 = 2 бит/сим, HY = (26 - 3 log2 3)/8 2.65 бит/сим.

10. I(Z, X1) = (22 - 3 log2 3)/16 1.08 бит/сим, HZ = (54 3 log2 3)/16 3.08 бит/сим.

11. I(X1, Y ) = (3 log2 3 - 2)/9 0.31 бит/сим, I(X2, Y ) = (3 log2 3 + 4)/9 0.97 бит/сим, HX1 = HX2 = log2 3 1.58 бит/сим, HY = (12 log2 3 - 2)/9 1.89 бит/сим.

12. HX = 7/4 = 1.75 бит/сим, HY = (24 - 3 log2 3 - 5 log2 5)/ 0.95 бит/сим, HZ = (328 - 12 log2 3 - 35 log2 5 - 17 log2 17)/64 2. бит/сим, I(Z, Y ) = (216 - 12 log2 3 - 35 log2 5 - 17 log2 17)/64 0. бит/сим.

13. ML1(X) = 3 бит/сим, ML2, 3, 4(X) = 2.2 бит/сим, HX = log2 5 - 0.2 2.12 бит/сим.

14. code(0) = 10, code(1) = 0, code(2) = 11 — это один из вариантов кодирующей функции. ML(X) = HX = 1.5 бит/сим.

15. code(2n) = 1 · · 1 0 или code(2n) = 0 · · 0 1. HX = n/2n = · · n= n-1 n- ML(X) = 2 бит/сим.

16. ML(X) HX 3.25 бит/сим.

17. inf(s1) = 1, cont(s1) = 2, inf(s2) = 0.5, cont(s2) = 0.75.

18. 1.56 бит/сим.

19. HX 2.17 бит/сим, код Хаффмена ML(X) 2.22 бит/сим, код Шеннона-Фэно ML(X) 2.28 бит/сим.

20. Шеннона-Фэно, Хаффмена: ML1(X1) = 2 бит/сим., ML1(X2) = 2.25 бит/сим., ML1(X3) = 2.7 бит/сим., ML1(X4) = 213/60 бит/сим.

Арифметический: ML1(X1) = 15/6 бит/сим., ML1(X2) = 2.05 бит/сим., ML1(X3) = 2.3 бит/сим., ML1(X4) = 21/60 бит/сим.

21. LХаффмена = 3 бита, Lарифметический = 4 бита.

22. 010001011, 01011111.

23. 81, в 27 раз.

24. Считая, что код генерирутся д.с.в. X с распределением P (X = A) = 2/3, P (X = B) = 1/3, можно получить наилучшие коды, для которых LХаффмена-1(ABAAAB) = 6 бит, LХаффмена-2(ABAAAB) = бит, LХаффмена-3(ABAAAB) = 5 бит, Lарифметический(ABAAAB) = 1 бит 25. ’B’10’C’ 26. code(AABCDAACCCCDBB) = ’A’10’B’00’C’000’D’ 100110011001, L(AABCDAACCCCDBB) = 62 бит, длина исходного со общения — 112 бит. code(КИБЕРНЕТИКИ) = ’К’0’И’00’Б’100’Е’000’Р’ 100’Н’1111000’Т’100110111, L(КИБЕРНЕТИКИ) = 85 бит, длина ис ходного сообщения — 88 бит. code(СИНЯЯ СИНЕВА СИНИ) = ’С’0’И’ 00’Н’100’Я’001100’ ’101001011100’Е’11000’В’10100’А’1010101101101111, L(СИНЯЯ СИНЕВА СИНИ) = 114 бит, длина исходного сообщения — 136 бит.

27. Распакованное сообщение — AFXAFFXFXAXAFFA, его длина — 120 бит, длина сжатого кода — 52 бит.

28. 01000010111001.

29. AABCDAACCCCDBB, LZ77: 0,0,’A’ 11,1,’B’ 0,0,’C’ 0,0, ’D’ 7,2,’C’ 11,2,’C’ 5,2,’B’ 0,0,’B’, длина 8 15 = 120 бит;

LZSS:

0’A’1 11,1 0’B’0’C’0’D’1 7,2 1 8,1 1 11,1 1 10,2 1 5,1 1 3,1 1 11,1, дли на 8 7 + 4 9 = 92 бит;

LZ78: 0,’A’ 1,’B’ 0,’C’ 0,’D’ 1,’A’ 3,’C’ 6,’D’ 0,’B’ 0,’B’, длина 9 12 = 108 бит;

LZW: 0’A’0’A’0’B’0’C’0’D’ 256 0’C’ 262 259 0’B’0’B’, длина 11 9 = 99 бит. КИБЕРНЕТИКИ, LZ77: 0,0,’К’ 0,0,’И’, 0,0,’Б’ 0,0,’Е’ 0,0,’Р’ 0,0,’Н’ 9,1,’Т’ 5,1,’К’ 0,0,’И’, длина 9 15 = 135 бит;

LZSS: 0’К’0’И’0’Б’0’Е’0’Р’0’Н’ 1 9,1 0’Т’1 5,1 1 5,2, длина 3 7 + 7 9 = 84 бит;

LZ78: 0,’К’ 0,’И’ 0,’Б’ 0,’Е’ 0,’Р’ 0,’Н’ 4,’Т’ 2,’К’ 0,’И’, длина 9 12 = бит;

LZW: 0’К’0’И’0’Б’0’Е’0’Р’0’Н’0’Е’0’Т’0’И’ 256, длина 10 9 = 90 бит. “СИНЯЯ СИНЕВА СИНИ”, LZ77: 0,0,’С’ 0,0,’И’ 0,0,’Н’ 0,0,’Я’ 11,1’ ’ 6,3,’Е’ 0,0,’В’ 0,0,’А’ 5,4,’И’, длина 9 15 = бит;

LZSS: 0’С’0’И’0’Н’0’Я’1 11,1 0’ ’ 6,3 0’Е’0’В’0’А’1 5,4 1 10,1, дли на 4 7 + 8 9 = 100 бит;

LZ78: 0,’С’ 0,’И’ 0,’Н’ 0,’Я’ 4,’ ’ 1,’И’ 3,’Е’ 0,’В’ 0,’А’ 0,’ ’ 6,’Н’ 0,’И’, длина 12 12 = 144 бит;

LZW: 0’С’0’И’0’Н’0’Я’0’Я’0’ ’ 256 0’Н’0’Е’0’В’0’А’ 261 257 0’И’, длина 14 9 = 126 бит.

30. Нет. Это следует из очевидного неравенства для длин кодов log2(LD + 256) < log2(LD) + 8, где LD — это размер словаря.

31. Во всех случаях сообщение — AFXAFFXFXAXAFFA, длина кода LZ77 — 105 бит, LZSS — 62 бит, LZ78 — 108 бит, LZW — 99 бит.

32. 2000 бод.

33. 1) 8000/3 2666.67 сим/сек;

2) 2523 сим/сек;

3) 2000 сим/сек.

34. Пусть X — д. с. в., определяющая передатчик, а Y — д. с. в., определяющая приемник. Тогда P (Y = 00/X = 00) = pp, P (Y = 00/X = 01) = pq,..., P (Y = 00/X = 11) = qq,...

4 i 4 i 35. C14p9q5, C14p14-iqi, C14 = 1471.

i=0 i= 36. 0.3%, 7.7%;

0.004%, 0.797%.

37. r = 6, 11 r 16.

38. r 2, r 9.

39. E1: 1. 00 00000, 01 01110, 10 10101, 11 11011;

2. min d = 3, Pнеобнаружения ошибки = 2p2q3 + pq4, код исправляет или обнаруживает все ошибки кратности соответственно до 1 или 2;

3. 00000 01110 10101 00001 01111 10100 00010 01100 10111 00100 01010 10001 01000 00110 11101 10000 11110 00101 00011 01101 10110 10010 11100 00111 01001;

4. Pправильной передачи = p5 + 5p4q + 2p3q2, код исправляет все ошибки кратности 1 и 2 из 10 ошибок кратности 2;

5. 10001 10, 01, 10101 10. E2: 1. 000 0000, 001 0010, 010 0101, 0111, 100 1001, 101 1011, 110 1100, 111 1110;

2. min d = 1, Pнеобнаружения ошибки = p3q + 3p2q2 + 3pq3, код не исправляет и не обнаруживает все ошибки никакой кратности;

3. 0000 0010 0101 0111 1001 1011 1100 0001 0011 0100 0110 1000 1010 1101 1111;

4. Pправильной передачи = p4+p3q, код исправляет 1 из 4 ошибок кратности 1;

5. 1001 100, 0110 011, 1101 110.

2 i 40. нет, т.к. C14 = 28.

i= 41. 5510 = 001010101 0001001010111, 20010 100011001000, 1000001000001 000100101, 1100010111100 001011101.

42. 0100 01100010100, 10001101 110011101111001, 10001110110.

43. Первое — нет, второе — да.

44. g(x) = 1 + x + x2 + x4 + x5 + x8 + x10.

45. 1000, 1111.

46. ПТУРХЧЧЮНФЫ.

47. 22: A отправляет B 58, B возвращает 94, A окончательно от правляет 115;

17: B отправляет A 135, A возвращает 15, B окончательно отправляет 143.

48. 53, 51;

247.

49. для a = 33 = 237.

50. = 21, 124.

51. H1 A name=”2” /A Глава 2 /H1.

Приложение Б. Управляющие коды ASCII Код Полное имя кода в Unicode 10-й 16-й Клавиатурный (краткое имя в ASCII) Перевод имени кода — описание использования кода.

Выше представлен шаблон для следующей далее таблицы управляю щих символов. Под клавиатурным кодом подразумевается комбинация двух клавиш, Ctrl (Control, в таблице это знак ) и приводимой, од новременное нажатие которых должно производить соответствующий код.

0 00 ^@ NULL (NUL) Пусто — этот код используется как завершающий в представлении строк многими системами программирования, например, Си, поэто му его использование в текстовых файлах крайне нежелательно.

1 01 ^A START OF HEADING (SOH) Начало заголовка — практически не используется.

2 02 ^B START OF TEXT (STX) Начало текста — практически не используется.

3 03 ^C END OF TEXT (ETX) Конец текста — в Unix и MS-DOS ввод этого символа с клавиа туры служит сигналом для прекращения выполнения программы.

4 04 ^D END OF TRANSMISSION (EOT) Конец передачи — в Unix и PostScript означает конец вводимых данных.

5 05 ^E ENQUIRY (ENQ) Кто там? — практически не используется.

6 06 ^F ACKNOWLEDGE (ACK) Подтверждение, да — практически не используется.

7 07 ^G BELL (BEL) Звонок — при его печати на консоли MS-DOS или Unix должен производиться звуковой сигнал.

8 08 ^H BACKSPACE (BS) Возврат на шаг — означает, что следующий символ следует печа тать с предшествующей позиции.

9 09 ^I HORISONTAL TABULATION (TAB) Горизонтальная табуляция — переход на следующую позицию та буляции.

10 0A ^J LINE FEED (LF) Подача новой строки — переход на новую строку. В текстовых фай лах MS-DOS и Microsoft Windows с сохранением текущей горизон тальной позицию. В текстовых файлах Unix с переходом на первую горизонтальную позицию.

11 0B ^K VERTICAL TABULATION (VT) Вертикальная табуляция — используется очень редко, как прави ло, принтерами.

12 0C ^L FORM FEED (FF) Подача новой формы — для консоли, как правило, означает очистку экрана, для принтера — завершение печати на текущем листе и запрос нового.

13 0D ^M CARRIAGE RETURN (CR) Возврат каретки — переход на первую горизонтальную позицию строки. В текстовых файлах MS-DOS и Microsoft Windows с сохра нением текущей строки, а в текстовых файлах Macintosh OS с пере ходом на новую строку. В текстовых файлах Unix не используется.

14 0E ^N SHIFT OUT (SO) Выход — используется очень редко, как правило, принтерами.

15 0F ^O SHIFT IN (SI) Вход — используется очень редко, как правило, принтерами.

16 10 ^P DATA LINK ESCAPE (DLE) Авторегистр 1 — практически не используется.

17 11 ^Q DEVICE CONTROL ONE (DC1) Используется некоторыми телекоммуникационными протоколами как байт X-ON.

18 12 ^R DEVICE CONTROL TWO (DC2) Практически не используется.

19 13 ^S DEVICE CONTROL THREE (DC3) Используется некоторыми телекоммуникационными протоколами как байт X-OFF.

20 14 ^T DEVICE CONTROL FOUR (DC4) Практически не используется.

21 15 ^U NEGATIVE ACKNOWLEDGE (NAK) Нет — практически не используется.

22 16 ^V SYNCHRONOUS IDLE (SYN) Синхронизация — практически не используется.

23 17 ^W END OF TRANSMISSION BLOCK (ETB) Конец блока — практически не используется.

24 18 ^X CANCEL (CAN) Аннулирование — используется очень редко, как правило, принте рами.

25 19 ^Y END OF MEDIUM (EM) Конец носителя — практически не используется.

26 1A ^Z SUBSTITUTE (SUB) Замена — в MS-DOS, Macintosh OS и CP/M — это маркер конца текстового файла.

27 1B ^[ ESCAPE (ESC) Авторегистр 2 — указывает на то, что некоторое количество кодов после него и он сам образуют группу, рассматриваемую как один код.

28 1С ^\ FILE SEPARATOR (FS) Разделитель файлов — практически не используется.

29 1D ^] GROUP SEPARATOR (GS) Разделитель групп — практически не используется.

30 1E ^^ RECORD SEPARATOR (RS) Разделитель записей — практически не используется.

31 1F ^ UNIT SEPARATOR (US) Разделитель элементов — практически не используется.

127 7F DELETE (DEL) Забой — удаление последнего видимого знака печатаемой строки.

В “чисто” текстовых (plain text) файлах допустимы только управ ляющие символы, отмечающие концы строк и, как правило, переходы на позиции табуляции (код 9). Маркер конца строки в Unix — это код 10, в Macintosh OS — 13, в CP/M, MS-DOS и Microsoft Windows — последовательность 13, 10.

Приложение В. Кодировка видимых символов ASCII Код Имя символа Символ 10-й 16-й в Unicode 3. 32 20 SPACE 33 21 ! EXCLAMATION MARK 34 22 " QUOTATION MARK 35 23 # NUMBER SIGN 36 24 $ DOLLAR SIGN 37 25 % PERCENT SIGN 38 26 & AMPERSAND 39 27 APOSTROPHE 40 28 ( LEFT PARENTHESIS 41 29 ) RIGHT PARENTHESIS 42 2A * ASTERISK 43 2B + PLUS SIGN 44 2C, COMMA 45 2D - HYPHEN-MINUS 46 2E. FULL STOP 47 2F / SOLIDUS 48 30 0 DIGIT ZERO 49 31 1 DIGIT ONE 50 32 2 DIGIT TWO 51 33 3 DIGIT THREE 52 34 4 DIGIT FOUR 53 35 5 DIGIT FIVE 54 36 6 DIGIT SIX 55 37 7 DIGIT SEVEN 56 38 8 DIGIT EIGHT 57 39 9 DIGIT NINE 58 3A : COLON 59 3B ;

SEMICOLON 60 3C < LESS-THAN SIGN 61 3D = EQUALS SIGN 62 3E > GREATER-THAN SIGN 63 3F ? QUESTION MARK Код Имя символа Символ 10-й 16-й в Unicode 3. 64 40 @ COMMERCIAL AT 65 41 A LATIN CAPITAL LETTER A 66 42 B LATIN CAPITAL LETTER B 67 43 C LATIN CAPITAL LETTER C 68 44 D LATIN CAPITAL LETTER D 69 45 E LATIN CAPITAL LETTER E 70 46 F LATIN CAPITAL LETTER F 71 47 G LATIN CAPITAL LETTER G 72 48 H LATIN CAPITAL LETTER H 73 49 I LATIN CAPITAL LETTER I 74 4A J LATIN CAPITAL LETTER J 75 4B K LATIN CAPITAL LETTER K 76 4C L LATIN CAPITAL LETTER L 77 4D M LATIN CAPITAL LETTER M 78 4E N LATIN CAPITAL LETTER N 79 4F O LATIN CAPITAL LETTER O 80 50 P LATIN CAPITAL LETTER P 81 51 Q LATIN CAPITAL LETTER Q 82 52 R LATIN CAPITAL LETTER R 83 53 S LATIN CAPITAL LETTER S 84 54 T LATIN CAPITAL LETTER T 85 55 U LATIN CAPITAL LETTER U 86 56 V LATIN CAPITAL LETTER V 87 57 W LATIN CAPITAL LETTER W 88 58 X LATIN CAPITAL LETTER X 89 59 Y LATIN CAPITAL LETTER Y 90 5A Z LATIN CAPITAL LETTER Z 91 5B [ LEFT SQUARE BRACKET 92 5C \ REVERSE SOLIDUS 93 5D ] RIGHT SQUARE BRACKET 94 5E ^ CIRCUMFLEX ACCENT 95 5F LOW LINE Код Имя символа Символ 10-й 16-й в Unicode 3. 96 60 ‘ GRAVE ACCENT 97 61 a LATIN SMALL LETTER A 98 62 b LATIN SMALL LETTER B 99 63 c LATIN SMALL LETTER C 100 64 d LATIN SMALL LETTER D 101 65 e LATIN SMALL LETTER E 102 66 f LATIN SMALL LETTER F 103 67 g LATIN SMALL LETTER G 104 68 h LATIN SMALL LETTER H 105 69 i LATIN SMALL LETTER I 106 6A j LATIN SMALL LETTER J 107 6B k LATIN SMALL LETTER K 108 6C l LATIN SMALL LETTER L 109 6D m LATIN SMALL LETTER M 110 6E n LATIN SMALL LETTER N 111 6F o LATIN SMALL LETTER O 112 70 p LATIN SMALL LETTER P 113 71 q LATIN SMALL LETTER Q 114 72 r LATIN SMALL LETTER R 115 73 s LATIN SMALL LETTER S 116 74 t LATIN SMALL LETTER T 117 75 u LATIN SMALL LETTER U 118 76 v LATIN SMALL LETTER V 119 77 w LATIN SMALL LETTER W 120 78 x LATIN SMALL LETTER X 121 79 y LATIN SMALL LETTER Y 122 7A z LATIN SMALL LETTER Z 123 7B { LEFT CURLY BRACKET 124 7C | VERTICAL LINE 125 7D } RIGHT CURLY BRACKET 126 7E ~ TILDE Приложение Г. Кодировка букв русского алфавита В настоящее время наиболее широко используются пять (!) различ ных таблиц кодировки для формального представления русских букв:

I. ISO 8859-5 — международный стандарт;

II. Кодовая страница 866 (Microsoft CP866) — используется в MS DOS;

III. Кодовая страница 1251 (Microsoft CP1251) для Microsoft Windows;

IV. На базе ГОСТ КОИ-8, koi8-r — применяется в мире Unix;

V. Unicode — используется в Microsoft Windows, Unix и клонах Unix.

Основная кодировка ГОСТ (государственный стандарт СССР) от 1987 года создана на основе рекомендаций ISO и в дальнейшем ста ла основой для представления знаков русских букв в Unicode. В ней и в кодировках II, III и V все буквы кроме и Е расположены в алфа е витном порядке. На практике эту кодировку можно встретить только на старых IBM PC совместимых компьютерах ЕС-1840 и в некоторых принтерах. Internet браузеры обычно поддерживают ее наряду с коди ровками II–IV.

Кодировка CP866, разработанная на основе альтернативной коди ровки ГОСТ, создана специально для ОС MS-DOS, в которой часто используются символы псевдографики. В этой кодировке эти символы имеют те же коды, что и в стандартном IBM PC совместимом компью тере.

Альтернативная кодировка ГОСТ, которая имеет два варианта, совпадает с CP866 по позициям для букв русского алфавита и знакам псевдографики. Основная кодировка ГОСТ совпадает с ISO 8859-5 толь ко по всем знакам русских букв, кроме загланой буквы Е.

Использование CP1251 обусловлено почти исключительно влияни ем на компьютерные технологии разработок фирмы Microsoft. В ней наиболее полно по сравнению с I, II, IV представлены такие символы как ©,, №, различные виды кавычек и тире и т. п.

Кодировка koi8-r основана на стандартах по обмену информаци ей, используемых на компьютерах под управлением ОС Unix, CP/M и некоторых других с середины 1970-х. В 1993 она стандартизирована в Internet документом RFC1489.

Кодировка Unicode опирается на каталог символов UCS (Univer sal Character Set) стандарта ISO 10646. UCS может содержать до различных знаков. Коды UCS-2 — 2-байтные, UCS-4 — 4-байтные. Ис пользуются также коды переменной длины UTF-8 (Unicode Transfer Format) — 1–6-байтные, наиболее совместимые с ASCII, и UTF-16 — или 4-байтные. Unicode в прикладных программах реализуется лишь частично, и в полном объеме пока нигде не поддерживается. В Linux используется UTF-8.

Достаточно широко используется кодирование на основе ASCII:

VI. На базе КОИ-7 — можно использовать при отсутствии кирилли ческих шрифтов, код получается вычитанием 128 от соответству ющего кода в koi8-r, что, как правило, дает код латинской буквы, близкой фонетически к русской.

В кодировке VI нет видимого символа для для Ъ.

Далее следует таблица, в которой представлены все перечислен ные способы кодирования букв русского алфавита. В этой таблице в колонке 1 находятся символы букв, в колонке 2 часть названия букв в Unicode 3.2 (названия строчных кириллических букв начинается слова ми CYRILLIC SMALL LETTER, а заглавных — CYRILLIC CAPITAL LETTER, т. о., полное название буквы Д — CYRILLIC CAPITAL LET TER DE), в колонках с I по V коды десятичные и шестнадцатеричные соответствующих таблиц кодировки, а в колонке VI — символ ASCII для КОИ-7.

Кроме перечисленных можно встретить еще используемую до вве дения кодировок ГОСТ болгарскую кодировку, называемую также MIC, Interprog или “старый вариант ВЦ АН СССР”. На компьютерах под управлением Macintosh OS используется также своя собственная та блица кодировки для русских букв, по своему набору знаков почти сов падающая с CP1251.

1 2 I II III IV V VI а A 208 D0 160 A0 224 E0 193 C1 1072 0430 A б BE 209 D1 161 A1 225 E1 194 C2 1073 0431 B в VE 210 D2 162 A2 226 E2 215 D7 1074 0432 W г GHE 211 D3 163 A3 227 E3 199 C7 1075 0433 G д DE 212 D4 164 A4 228 E4 196 C4 1076 0434 D е IE 213 D5 165 A5 229 E5 197 C5 1077 0435 E IO 241 F1 241 F1 184 B8 163 A3 1105 0451 # е ж ZHE 214 D6 166 A6 230 E6 214 D6 1078 0436 V з ZE 215 D7 167 A7 231 E7 218 DA 1079 0437 Z и I 216 D8 168 A8 232 E8 201 C9 1080 0438 I й SHORT I 217 D9 169 A9 233 E9 202 CA 1081 0439 J к KA 218 DA 170 AA 234 EA 203 CB 1082 043A K л EL 219 DB 171 AB 235 EB 204 CC 1083 043B L м EM 220 DC 172 AC 236 EC 205 CD 1084 043C M н EN 221 DD 173 AD 237 ED 206 CE 1085 043D N о O 222 DE 174 AE 238 EE 207 CF 1086 043E O п PE 223 DF 175 AF 239 EF 208 D0 1087 043F P р ER 224 E0 224 E0 240 F0 210 D2 1088 0440 R с ES 225 E1 225 E1 241 F1 211 D3 1089 0441 S т TE 226 E2 226 E2 242 F2 212 D4 1090 0442 T у U 227 E3 227 E3 243 F3 213 D5 1091 0443 U ф EF 228 E4 228 E4 244 F4 198 C6 1092 0444 F х HA 229 E5 229 E5 245 F5 200 C8 1093 0445 H ц TSE 230 E6 230 E6 246 F6 195 C3 1094 0446 C ч CHE 231 E7 231 E7 247 F7 222 DE 1095 ш SHA 232 E8 232 E8 248 F8 219 DB 1096 0448 [ щ SHCHA 233 E9 233 E9 249 F9 221 DD 1097 0449 ] ъ HARD SIGN 234 EA 234 EA 250 FA 223 DF 1098 044A ы YERU 235 EB 235 EB 251 FB 217 D9 1099 044B Y ь SOFT SIGN 236 EC 236 EC 252 FC 216 D8 1100 044C X э E 237 ED 237 ED 253 FD 220 DC 1101 044D \ ю YU 238 EE 238 EE 254 FE 192 C0 1102 044E @ я YA 239 EF 239 EF 255 FF 209 D1 1103 044F Q 1 2 I II III IV V VI А A 176 B0 128 80 192 C0 225 E1 1040 0410 a Б BE 177 B1 129 81 193 C1 226 E2 1041 0411 b В VE 178 B2 130 82 194 C2 247 F7 1042 0412 w Г GHE 179 B3 131 83 195 C3 231 E7 1043 0413 g Д DE 180 B4 132 84 196 C4 228 E4 1044 0414 d Е IE 181 B5 133 85 197 C5 229 E5 1045 0415 e Е IO 161 A1 240 F0 168 A8 179 B3 1025 0401 Ж ZHE 182 B6 134 86 198 C6 246 F6 1046 0416 v З ZE 183 B7 135 87 199 C7 250 FA 1047 0417 z И I 184 B8 136 88 200 C8 233 E9 1048 0418 i Й SHORT I 185 B9 137 89 201 C9 234 EA 1049 0419 j К KA 186 BA 138 8A 202 CA 235 EB 1050 041A k Л EL 187 BB 139 8B 203 CB 236 EC 1051 041B l М EM 188 BC 140 8C 204 CC 237 ED 1052 041C m Н EN 189 BD 141 8D 205 CD 238 EE 1053 041D n О O 190 BE 142 8E 206 CE 239 EF 1054 041E o П PE 191 BF 143 8F 207 CF 240 F0 1055 041F p Р ER 192 C0 144 90 208 D0 242 F2 1056 0420 r С ES 193 C1 145 91 209 D1 243 F3 1057 0421 s Т TE 194 C2 146 92 210 D2 244 F4 1058 0422 t У U 195 C3 147 93 211 D3 245 F5 1059 0423 u Ф EF 196 C4 148 94 212 D4 230 E6 1060 0424 f Х HA 197 C5 149 95 213 D5 232 E8 1061 0425 h Ц TSE 198 C6 150 96 214 D6 227 E3 1062 0426 c Ч CHE 199 C7 151 97 215 D7 254 FE 1063 Ш SHA 200 C8 152 98 216 D8 251 FB 1064 0428 { Щ SHCHA 201 C9 153 99 217 D9 253 FD 1065 0429 } Ъ HARD SIGN 202 CA 154 9A 218 DA 255 FF 1066 042A Ы YERU 203 CB 155 9B 219 DB 249 F9 1067 042B y Ь SOFT SIGN 204 CC 156 9C 220 DC 248 F8 1068 042C x Э E 205 CD 157 9D 221 DD 252 FC 1069 042D | Ю YU 206 CE 158 9E 222 DE 224 E0 1070 042E ‘ Я YA 207 CF 159 9F 223 DF 241 F1 1071 042F q Приложение Д. Элементы теории чисел Каноническим разложением числа m называется разложение его 1 2 k на простые сомножители в виде m = p p · · · p, где p1, p2,..., pk 1 2 k — все различные простые делители числа m, а 1, 2,..., k — целые положительные числа.

Функцией Эйлера называется, отображение : N N, 1 2 k (m) = p -1(p1 - 1)p -1(p2 - 1) · · · p -1(pk - 1), 1 2 k 1 2 k p p · · · p — каноническое разложение m.

1 2 k Например, (2) = 1, (12) = (223) = 21(2 - 1)30(3 - 1) = 2 2 = 4, (1000) = (2353) = 22524 = 4 25 4 = 400.

Числа m и n называются взаимно простыми, если у них нет общих делителей больших 1, т.е. НОД(m, n) = 1.

Функция Эйлера от числа m равна числу чисел меньших m и вза имно простых с m [7].

Для взаимно простых m и n верно равенство (mn) = (m)(n) [7].

Число примитивных многочленов степени n над полем (Z2, +, ) равно (2n - 1)/n [12].

Теорема Эйлера-Ферма [7]. Для взаимно простых m и a имеет ме сто соотношение a(m) 1 (mod m).

Для решения уравнения ax 1 (mod m), где НОД(a, m) = 1, мож но использовать теорему Эйлера-Ферма, т.е. x a(m)-1 (mod m), но это весьма трудоемкий способ. Получим решения искомого уравнения через формулу для решения эквивалентного уравнения ax - my = 1.

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

Для чисел a и m последовательность шагов алгоритма Евклида выглядит как a = mq0 + a1, m = a1q1 + a2, a1 = a2q2 + a3,...

an-2 = an-1qn-1 + an, an-1 = anqn, a где a1, a2,..., an — остатки. Разложение в цепную дробь по после m довательности частных q0,..., qn имеет вид a a1 1 1 = q0 + = q0 + = q0 + = · · · = q0 +.

m m m a2 q1 + q1 + a a q2 + q3 + · · · Обозначим за Pk/Qk дробь, получаемую из приведенной цепной дроби отбрасыванием членов с индексами, большими k. Например, P0/Q0 = q0, P1/Q1 = q0+1/q1 = (q0q1+1)/q1 и т.д. Числитель, Pk, и знаменатель, Qk, можно вычислять рекуррентно по следующим формулам:

P-2 = 0, P-1 = 1, Q-2 = 1, Q-1 = 0;

при k 0 Pk = qkPk-1 + Pk-2, Qk = qkQk-1 + Qk-2.

По определению Pn = a и Qn = m. Кроме того, Fn = PnQn-1-Pn-1Qn = (qnPn-1+Pn-2)Qn-1-Pn-1(qnQn-1+Qn-2) = = -Pn-1Qn-2 +Pn-2Qn-1 = -Fn-1 = · · · = Fn-2 = · · · = (-1)n+1F-1 = = (-1)n+1(P-1Q-2 - P-2Q-1) = (-1)n+ или (-1)n+1PnQn-1 - Pn-1(-1)n+1Qn = 1, что означает a(-1)n+1Qn-1 - m(-1)n+1Pn-1 = 1, т.е. x = (-1)n-1Qn-1 и y = (-1)n-1Pn-1.

Процесс получения числителей и знаменателей удобно оформить в виде таблицы:

k -2 -1 0 1 2 · · · n - 1 n qk q0 q1 q2 · · · qn-1 qn Pk 0 1 P0 P1 P2 · · · Pn-1 Pn Qk 1 0 Q0 Q1 Q2 · · · Qn-1 Qn.

Таким образом, корни уравнения ax 1 (mod m) вычисляются по формуле x = (-1)n-1Qn-1.

Пример. Решить уравнение 1181x 1 (mod 1290816). Сначала по алгоритму Евклида получается следующая цепочка соотношений:

1181 = 1290816 0 + 1181, 1290816 = 1181 1092 + 1164, 1181 = 1164 1 + 17, 1164 = 17 68 + 8, 17 = 8 2 + 1, 8 = 1 8.

Затем составляется таблица для вычисления Q5:

k -2 -1 0 1 2 3 4 qk 0 1092 1 68 2 Qk 1 0 1 1092 1093 75416 151925 1290816.

Таким образом, искомый x равен 151925.

Гипотеза. Задача разложения целого числа с заданным числом раз рядов на множители является труднорешаемой*.

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

Эта гипотеза лежит в основе методов Диффи-Хеллмана.

* Задача называется труднорешаемой, если время ее решения за висит от объема входных данных по экспоненциальному закону и не может быть сведено к полиномиальному Приложение Е. Используемые обозначения P (A) — вероятность события A.

P (A/B) — вероятность события A, если известно, что событие B произошло. Условная вероятность.

P (A, B) — вероятность одновременного наступления событий A и B.

N — множество натуральных чисел.

Z2 — множество из 0 и 1 — {0, 1}.

R — множество вещественных чисел.

R2 — числовая плоскость.

i xi — сумма xi по всем возможным значениям индекса i.

xij — сумма xij по всем возможным значениям пар индексов i,j i и j.

k Cn — биномиальный коэффициент в формуле бинома Ньютона n n!

k k (p + q)n = Cnpkqn-k, Cn = k!(n - k)!

k= или число возможных разных выборок k элементов из множества из n элементов, число сочетаний из n по k.

dim(X) — размерность вектора X, число компонент X.

#X — количество элементов в множестве X, мощность X.

НОД(n, m) — наибольший общий делитель n и m.

НОК(n, m) — наименьшее общее кратное n и m.

a b (mod n) — числа a и b сравнимы по модулю n, т. е. разность a - b делится на n нацело.

f: A B — функция f с областью определения A и областью, содержащей все значения f, B.

f g — композиция функций f и g, т.е. (f g)(x) = f(g(x)).

(X, +, ) — поле над множеством X с аддитивной операцией + и мультипликативной операцией.

Приложение Ж. Список литературы 1. Биркгоф Г., Барти Т. Современная прикладная алгебра — М.: Мир, 1976.

2. Блейхер Р. Теория и практика кодов, контролирующих ошибки — М.: Мир, 1986.

3. Борн Г. Форматы данных — Киев: Торгово-издательское бюро BHV, 1995.

4. Букчин Л. В., Безрукий Ю. Л. Дисковая подсистема IBM-совме стимых персональных компьютеров — М.: МИКАП, 1993.

5. Винер Н. Кибернетика — М.: Наука, 1983.

6. Воробьев Н. Н. Признаки делимости — М.: Наука, 1988.

7. Глушков В. М. Основы безбумажной информатики — М.: Наука, 1987.

8. Джордж Ф. Основы кибернетики — М.: Радио и Связь, 1984.

9. Кенцл Т. Форматы файлов Internet — СПб: Питер, 1997.

10. Нельсон М. Верификация файлов //“Журнал д-ра Добба” 1/93.

11. Нефедов В. Н., Осипова В. А. Курс дискретной математики — М.: МАИ, 1992.

12. Нечаев В. И. Элементы криптографии — М.: Высшая школа, 1999.

13. Мастрюков Д. Алгоритмы сжатия информации //“Монитор” 7/93–6/94.

14. Питерсон Р., Уэлдон Э. Коды, исправляющие ошибки — М.: Мир, 1976.

15. Перспективы развития вычислительной техники: в 11 кн.: Спра вочное пособие/Под ред. Ю. М. Смирнова. Кн. 9. — М.: Высшая школа, 1989.

16. Розанов Ю. А. Лекции по теории вероятностей — М.: Наука, 1986.

17. Титце У., Шенк К. Полупроводниковая схемотехника — М.: Мир, 1983.

18. Чисар И., К Я. Теория информации — М.: Мир, 1985.

ернер 19. Шеннон К. Работы по теории информации и кибернетики — М.:

Издательство иностранной литературы, 1963.

20. Яглом А., Яглом И. Вероятность и информация — М.: Наука, 1973.

21. Введение в криптографию /Под общей редакцией В. В. Ященко.

— М.: МЦНМО—ЧеРо, 2000.

22. HTML 4.01 Specification /Edited by D. Ragget, A. L. Hors, I. Jacobs — W3C: http://www.w3c.org/TR/REC-html401-19991224, 1999.

23. The Unicode Standard, Version 3.0 — Addison Wesley Longman Pub lisher, 2000, ISBN 0-201-61633-5.

Приложение З. Предметный указатель ADC (A/C) — связи дискретный ARJ 21, — — непрерывный ASCII 6, 76, 88, код блочный BMP — циклический bzip2 — древовидный адаптивный алгоритм сжатия ин — групповой формации — квазисовершенный 61, алгоритм Евклида — линейный аналоговая информация — оптимальный арифметическое кодирование — полиномиальный байт (byte) — последовательный бинарные файлы — совершенный бит (bit) — с проверкой четности 50, блочные коды — — тройным повторением 50, бод (baud) — Голея цифровая информация — Хэмминга циклические коды кодирование декодирование — арифметическое дискретная информация — — адаптивное древовидные коды — помехозащитное двоичный (m, n)-код — префиксное емкость канала связи 10, — Диффи-Хеллмана 72, физическая разметка текста — Хаффмена формальное представление зна — — адаптивное ний — Шеннона-Фэно 21, функция ошибок — LZ77 — Эйлера — LZ78 гибридные вычислительные маши — LZSS ны — LZW групповой код кодировка ГОСТ информация количество информации — аналоговая компьютер — цифровая контрольная сумма — дискретная квазисовершенный код 61, — непрерывная — семантическая 20 лидер смежного класса канал без “шумов” 46 линейные коды логическая разметка текста 77 систематические помехозащитные коды CCITT 44, словарные методы сжатия матричное кодирование совершенный код метод блокирования статистические методы сжатия модуляция частотная непрерывная информация строка ошибок нераскрываемый шифр таблица декодирования неравенство (нижняя граница) Хэм — кодировки 6, минга — стилей — (верхняя граница) Варшамова Гильберта 56 тег (tag) HTML нижняя граница Плоткина 57 текстовые файлы упорядоченное бинарное дерево обратная теорема о кодировании при наличии помех 49 управление (основная категория ки бернетики) общая схема передачи информа ции 10 вес двоичного слова оптимальный код 61 взаимно простые числа основная теорема о кодировании при DAC (D/A) наличии помех 49 запись с групповым кодированим — — — — — отсутствии помех 22 (RLL) основной факт теории передачи ин- шифр без передачи ключей формации 49 — нераскрываемый CGI 80 — простой замены CP1251 94 — с открытым ключом CP866 94 — — подписью CRC 69 шифры с ключевым словом полиномиальное кодирование 65 — Диффи-Хеллмана 72, последовательные коды 53 шифры-перестановки префиксное кодирование 19 электронная подпись примитивный многочлен 68, 98 элемент текста HTML процедурная разметка текста 77 энтропия пропускная способность (емкость) частота дискретизации канала 10, 46 частотная модуляция расстояние Хэмминга 53 DES расширенный ASCII (ASCII+) 6 АЦП разметка текста (markup). 77 АВМ репитер 45 БЧХ-коды FM Циклический избыточный код GIF ЦАП gzip ЦВМ HTML Двоичный симметричный канал HTTP ISDN Информация JPEG 44, Канал информационный koi8-r — связи LHA Каноническое разложение числа LZ77 35, LZ78 38, Кибернетика LZSS 37, Кодирование LZW 39, Коды с исправлением ошибок MFM — — обнаружением ошибок MPEG Компьютерный шрифт PDF 78, Криптография PostScript 78, КОИ-7 RAR КОИ-8 RLE Линии связи RLL Полиномиальный код RSA Последовательность Фибоначчи SGML 78, TEX 78, Теорема о выборках TIFF — Шеннона UCS — Эйлера-Ферма Unicode 77, 88, 91, Теория информации URI, URL Устройства канала связи UTF Задержка сигнала во времени WWW Шум в канале связи 10 XML 78, Энтропия 13, 18 ZIP 21, Приложение И. Именной указатель Адлеман (Adleman) Котельников Берг Лагранж (Lagrange) Боуз (Bose) Лемпел (Lempel) Цезарь (Caesar) Найквист (Nyquist) Диффи (Diffie) Плоткин (Plotkin) Дойл (Doyle) По (Poe) Евклид (Euclid, E ` ) Рид (Reed) Ферма (Fermat) Ривест (Rivest) Фибоначчи (Fibonacci) Соломон (Solomon) Фишер (Fisher) Сторер (Storer) Фэно (Fano) 21, 23, 49 Уэлч (Welch) Гильберт (Gilbert) 56 Варшамов Глушков 5 Винер (Wiener) Голей (Golay) 67 Зив (Ziv) Хаффмен (Huffman) 23, 28 Шамир (Shamir) Хеллман (Hellman) 72 Шеннон (Shannon) 4, 12, 18, 21, 23, Хоккенгем (Hocquengem) 68 49, Хэмминг (Hamming) 53, 56, 61, 67 Шиманский (Szimanski) Клаузиус (Clausius) 12 Эйлер (Euler) Кнут (Knuth) 81 Чоудхури (Chaudhuri) ОГЛАВЛЕНИЕ Введение...................................................... 1 Предмет и основные разделы кибернетики................... 2 Формальное представление знаний........................... 3 Виды информации............................................ 4 Хранение, измерение, обработка и передача информации.... 5 Базовые понятия теории информации....................... 6 Способы измерения информации............................ 7 Вероятностный подход к измерению дискретной и непрерывной информации................................... 8 Смысл энтропии Шеннона.................................. 9 Семантическая информация................................. 10 Сжатие информации........................................ 11 Простейшие алгоритмы сжатия информации............... 12 Арифметическое кодирование............................... 13 Адаптивные алгоритмы сжатия. Кодирование Хаффмена... 14 Адаптивное арифметическое кодирование................... 15 Подстановочные или словарно-ориентированные алгоритмы сжатия информации. Методы Лемпела-Зива................ 16 LZ-алгоритмы распаковки данных. Примеры............... 17 Особенности программ-архиваторов........................ 18 Сжатие информации с потерями............................ 19 Информационный канал..................................... 20 Помехозащитное кодирование............................... 21 Математическая модель системы связи..................... 22 Матричное кодирование..................................... 23 Групповые коды............................................. 24 Совершенные и квазисовершенные коды.................... 25 Полиномиальные коды...................................... 26 Понятие о кодах Боуза-Чоудхури-Хоккенгема............... 27 Циклические избыточные коды.............................. 28 Основы теории защиты информации........................ 29 Криптосистема без передачи ключей........................ 30 Криптосистема с открытым ключом........................ 31 Электронная подпись........................................ 32 Стандарт шифрования данных.............................. 33 Информация в Internet...................................... 34 HTML, XML и SGML....................................... 35 TEX.......................................................... 36 PostScript и PDF............................................ Приложения А Ответы на все упражнения.................................. Б Управляющие коды ASCII.................................. В Кодировка видимых символов ASCII........................ Г Кодировка букв русского алфавита......................... Д Элементы теории чисел..................................... Е Используемые обозначения................................. Ж Список литературы........................................ З Предметный указатель..................................... И Именной указатель......................................... ДЛЯ ЗАМЕТОК УЧЕБНОЕ ПОСОБИЕ Владимир Викторович Лидовский ТЕОРИЯ ИНФОРМАЦИИ Издательство «Компания Спутник+» 109428, Москва, Рязанский проспект, д. 8а Подписано в печать 17.03.2004. Формат 6090/16.

Усл. печ. л. 6.81. Тираж 70 экз. Заказ 60.

... самые разные категории читателей найдут в книге что-то интересное для себя.

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

Pages:     | 1 ||



© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.