Структурируйте текст. Создайте автооглавление.
История
кодирования и защиты информации.
С
глубокой древности люди искали эффективные
способы передачи информации.
Одновременно
с потребностью передавать информацию
люди искали способы скрыть смысл
передаваемых сообщений от посторонних
любопытных глаз. Императоры, торговцы,
политики и шпионы искали способы
шифрования своих посланий. Образцы
тайнописи можно встретить еще у Геродота
(V в. до н. э.).
К
тайнописи – криптографии прибегал Гай
Юлий Цезарь, заменяя в своих тайных
записях одни буквы другими. Использовали
шифрование не только древнегреческие
жрецы, но и ученые Средневековья:
математики итальянец Джероламо Кардано
и француз Франсуа Виет, нидерландский
гуманист, историк, юрист Гроций, выдающийся
английский философ Фрэнсис Бэкон. Однако
отцом криптографии считается архитектор
Леон Баттиста Альберти (1404-1472), который
ввел шифрующие коды и много алфавитные
подстановки.
Первые
манипуляции с символами в виде различных
кодов возникли с потребностью шифровать
информацию.
Знания
математики нужны для того, чтобы найти
простую, но надежную систему кодирования,
недоступную для расшифровки посторонним
лицам, а так же найти способы декодирования
чужой системы тайнописи, чужих кодов.
Например,
механическая замена одних букв или
чисел другими – подстановки Цезаря –
достаточно легко поддается дешифровке.
Причем сам процесс декодирования
аналогичен решению неопределенных
уравнений со многими неизвестными.
Кодирование
имеет значение не только в конспиративных
целях для шифровки информации. Так, в
математике с помощью кодирования
изучение одних объектов заменяют
изучением других, более доступных или
уже известных. Ярким примером кодирования
в математике является метод координат,
введенный Декартом, который дает
возможность изучать геометрические
объекты через их аналитическое выражение
в виде чисел, букв и их комбинаций –
формул.
Теория
кодирования – довольно молодая наука.
Исследование надежности кодов получило
новый импульс после создания в 1948 г.
Клодом Эльвудом Шенноном теории
информации.
В
любой системе счисления для представления
чисел выбираются некоторые символы
(слова или знаки), называемые базисными
числами, а все остальные числа получаются
в результате каких-либо операции из
базисных чисел данной системы исчисления.
Символы, используемые для записи чисел,
могут быть любыми, только они должны
быть разными и значение каждого из них
должно быть известно.
Системы
счисления для представления информации
в ЭВМ.
Системы
счисления подразделяются:
Позиционные
системы – каждый числовой знак в записи
любого числа имеет значение, зависящее
от его расположения в записи числа.
Примером служит современная десятичная
система счисления. Так в числе 555, первая
справа цифра 5 обозначает единицы, вторая
– десятки, третья – сотни. Позиционные
системы счисления занимают
преимущественное положение среди
остальных систем. Особенности
этих систем будут рассмотрены в
следующем разделе данной темы.
Непозиционные
системы – каждый числовой знак в записи
любого числа имеет одно и то же значение,
т.е. значение его не зависит от его
расположения в записи числа. Примером такой
системы служит “римская нумерация
Системы
счисления, в которых любое число
получается путем сложения или вычитания
базисных чисел, называются аддитивными.
Унарная
система – это система счисления, в
которой для записи чисел используется
только один знак – 1 .Следующее число
получается из предыдущего добавлением
новой 1; их количество (сумма) равно
самому числу.
Основные
понятия вероятностной теории информации
Сигнал
есть сообщение, передаваемое с помощью
некоторого носителя. Если источник
вырабатывает сигнал, параметр которого
является непрерывной функцией времени,
то он называется непрерывным. Непрерывна
и информация, передаваемая такими
сигналами.
Сигнал
называется дискретным, если соответствующие
ему числовые значения существуют в
конечный момент времени и представляют
собой конечную последовательность
символов, например 0 и 1.
В
дискретных сообщениях, конечных или
бесконечных последовательностях знаков,
можно проводить разбиения на конечные
последовательности знаков – слова.
Пусть
дано некоторое множество знаков М.
Говорят, что задано слово над множеством
М, если оно составлено из элементов
множества М.
Для
множества двоичных символов В={0,1}
двоичным словом длины п будет
последовательность знаков, содержащая
k нулей и i единиц, причем k + i = п. Например,
кортеж 010111 есть слово длины 6 над B,
двоичный код некоторого числа, содержащий
k = 2 нулей и i = 4 единиц. Длина двоичного
слова может быть неограниченной.
Процедура
преобразования непрерывных
сигналов в дискретные, называется
дискретизацией. Для ее проведения
выбирают из алфавита конкретные символы,
которые характеризуют все целостное
сообщение.
К
анализу информации возможны различные
подходы.
Объемный
подход связан с подсчетом количества
информации в двоичной системе счисления
с учетом количества символов.
Вероятностный
подход учитывает частоту появления
символа в тексте.
Однако
при таких подходах упускается истинность
(семантическая характеристика), а также
полнота, актуальность, ценность текста.
К
свойствам информации можно отнести:
- запоминаемость (возможность сохранения);
- передаваемостъ без искажений, с помощью различных каналов связи;
- воспроизводимость;
- преобразуемость, т.е. представление информации в разной форме, в том числе ее копирование;
- стираемость – преобразование, при котором количество информации в новой форме уменьшается до нуля.
Понятие
кодирования информации
Теория
кодирования информации является одним
из важных разделов теоретической
информатики. В нем рассматриваются
такие вопросы как: принципов кодирования
информации и приемов, обеспечивающих
надежность передачи информации по
каналам связи, т.е. отсутствие потерь
информации.
Первая
же задача – кодирование информации –
касается не только передачи, но и
обработки, и хранения информации, т.е.
охватывает широкий круг проблем; частным
их решением будет представление
информации в компьютере. С обсуждения
этих вопросов и начнем освоение теории
кодирования.
Для
представления дискретных сообщений
используется некоторый алфавит. Однако
однозначное соответствие между
содержащейся в сообщении информацией
и его алфавитом отсутствует.
В
целом ряде практических приложений
возникает необходимость перевода
сообщения хода из одного алфавита к
другому, причем, такое преобразование
не должно приводить к потере информации.
Кодирование
предшествует передаче и хранению
информации. При этом, как указывалось
ранее, хранение связано с фиксацией
некоторого состояния носителя информации,
а передача – с изменением состояния с
течением времени (т.е. процессом). Эти
состояния или сигналы будем называть
элементарными сигналами -именно их
совокупность и составляет вторичный
алфавит.
Первая
теорема Шеннона: При отсутствии помех
всегда возможен такой вариант кодирования
сообщения, при котором среднее число
знаков кода, приходящихся на один знак
первичного алфавита, будет сколь угодно
близко к отношению средних информации
на знак первичного и вторичного алфавитов.
Множество
A часто называют алфавитом
сообщений, множество В –
кодирующим алфавитом.
Обозначим
через F отображение слов алфавита А в
алфавит В. Тогда слово р = F(a) назовем
кодом слова а (от лат. codex).
Код
- правило однозначного преобразования
(т. е. функция) сообщения из одной
символической формы представления
(исходного алфавита А) в другую (объектный
алфавит В), обычно без каких- либо потерь
информации.
Код
– правило, описывающее соответствие
знаков или их сочетаний первичного
алфавита знакам или их сочетаниям
вторичного алфавита.
Код
– набор знаков вторичного алфавита,
используемый для представления знаков
или их сочетаний первичного алфавита
Кодированием
называют универсальный способ отображения
информации при ее хранении, передаче и
обработке в виде системы соответствий
между элементами сообщений и сигналами,
при помощи которых эти элементы можно
зафиксировать.
Процесс
преобразования слов исходного алфавита
A в алфавит B называется кодированием информации.
В символьном виде запишем F: A*®B*
Кодирование
- перевод информации, представленной
сообщением в первичном алфавите, в
последовательность кодов.
Процесс
обратного преобразования слова называется
декодированием. Декодирование можно
рассматривать как функцию F-1 – обратную
функции F – кодированию.
Декодирование
- операция, обратная кодированию, т.е.
восстановление информации в первичном
алфавите по полученной последовательности
кодов.
Кодер
- устройство, обеспечивающее выполнение
операции кодирования.
Декодер
- устройство, производящее декодирование.
Операции
кодирования и декодирования называются
обратимыми, если их последовательное
применение обеспечивает возврат к
исходной информации без каких-либо ее
потерь.
Примером
обратимого кодирования является
представление знаков в телеграфном
коде и их восстановление после передачи.
Примером кодирования необратимого
может служить перевод с одного
естественного языка на другой – обратный
перевод, вообще говоря, не восстанавливает
исходного текста. Безусловно, для
практических задач, связанных со знаковым
представлением информации, возможность
восстановления информации по ее коду
является необходимым условием применения
кода, поэтому в дальнейшем изложении
ограничим себя рассмотрением только
обратимого кодирования.
Правила
обработки могут быть различными:
- поэлементное кодирование,
- кодирование с помощью алгоритма,
- кодирование с помощью различных видов графики и др.
Так
как для любого кодирования должна
выполняться операция декодирования,
то отображение должно быть обратимым
(биекция).
Код
называется равномерным или блочным,
если все кодовые слова имеют одинаковую
длину.
- Абстрактным алфавитом является упорядоченное дискретное множество символов.
Алфавитное
неравномерное кодирование
Знаки
первичного алфавита (например, русского)
кодируются комбинациями символов
двоичного алфавита. Это: 0 и 1. Длина
кодов и, соответственно, длительность
передачи отдельного кода, могут
различаться. Длительности элементарных
сигналов при этом одинаковые.
Для
передачи информации, в среднем приходящейся
на знак первичного алфавита, необходимо
время. В виду этого, задача по оптимизации
неравномерного кодирования заключается
в построении схемы кодирования, в которой
суммарная длительность кодов при
передаче (или суммарное число кодов при
хранении) данного сообщения была бы
наименьшей.
Суммарная
длительность сообщения будет меньше,
если знакам первичного алфавита, которые
встречаются в сообщении чаще, присвоить
меньшие по длине коды, а тем, относительная
частота которых меньше – коды более
длинные. Другими словами, коды знаков
первичного алфавита, вероятность
появления которых в сообщении выше,
следует строить из возможно меньшего
числа элементарных сигналов, а длинные
коды использовать для знаков с малыми
вероятностями.
Параллельно
должна решаться проблема различимости
кодов. Представим, что на выходе кодера
получена следующая последовательность
элементарных сигналов:
00100010000111010101110000110
Если
бы код был равномерным, то приемное
устройство отсчитывало бы заданное
число элементарных сигналов и
интерпретировало бы их в соответствии
с кодовой таблицей. При использовании
неравномерного кодирования возможны
два подхода к обеспечению различимости
кодов.
Первый
состоит в использовании специальной
комбинации элементарных сигналов,
которая интерпретируется декодером
как разделитель знаков. Его называют
“Неравномерный код с разделителем”
Разделителем
отдельных кодов букв может быть
последовательность 00 (признак конца
знака), а разделителем слов – 000
(признак конца слова – пробел). При этом
можно установить правила построения
кодов, например некоторые их таковых:
- код признака конца знака может быть включен в код буквы, поскольку не существует отдельно (т.е. кода всех букв будут заканчиваться 00);
- коды букв не должны содержать двух и более нулей подряд в середине (иначе они будут восприниматься как конец знака);
- разделителю слов (000) всегда предшествует признак конца знака и др.
Неравномерный
код может быть однозначно декодирован,
если никакой из кодов не совпадает с
началом (префиксом) какого-либо иного
более длинного кода.
Второй
– в применении префиксных кодов. В
языковедении термин «префикс» означает
«приставка». При прочтении (расшифровке)
закодированного сообщения путем
сопоставления с таблицей кодов всегда
можно точно указать, где заканчивается
один код и начинается другой.
Равномерное
алфавитное двоичное кодирование.
Байтовый код
Двоичный
код первичного алфавита строится
цепочками равной длины. Формировать
признак конца знака не требуется.
Приемное устройство отсчитывает
оговоренное заранее количество
элементарных сигналов и интерпретирует
цепочку, соотнося ее с таблицей кодов.
При этом недопустимы сбои, например,
пропуск одного элементарного сигнала
приведет к сдвигу всей кодовой
последовательности и неправильной ее
интерпретации; решается проблема путем
синхронизации передачи или иными
способами.
С
другой стороны, применение равномерного
кода оказывается одним из средств
контроля правильности передачи, поскольку
факт поступления лишнего элементарного
сигнала или, наоборот, поступление
неполного кода сразу интерпретируется
как ошибка.
Алфавитное
кодирование с неравной длительностью
элементарных сигналов. Код Морзе.
В
качестве примера использования данного
варианта кодирования, рассмотрим
телеграфный код Морзе (азбука Морзе). В
нем каждой букве или цифре сопоставляется
некоторая последовательность
кратковременных импульсов – точек и
тире, разделяемых паузами.
Пусть t-
длительность импульса соответствует
точке, тогда:
3t
– соответствует тире
3t
– пауза между буквами
t
- длительность паузы между точками,
точкой и тире, между тире
6t
– длительность пазы между словами и
т.д.
Свой
код Морзе разработал в 1838 г., т.е. задолго
до исследований относительной частоты
появления различных букв в текстах. При
составлении кодов Морзе для букв русского
алфавита учет относительной частоты
букв не производился, что, естественно,
повысило его избыточность.
Блочное
двоичное кодирование
Наилучший
результат (наименьшая избыточность)
был получен при кодировании по методу
Хаффмана – для русского алфавита
избыточность оказалась менее 1%. При
этом указывалось, что код Хаффмана
улучшить невозможно. На первый взгляд
это противоречит первой теореме Шеннона,
утверждающей, что всегда можно предложить
способ кодирования, при котором
избыточность будет сколь угодно малой
величиной. На самом деле это противоречие
возникло из-за того, что до сих пор мы
ограничивали себя алфавитным кодированием.
При
алфавитном кодировании передаваемое
сообщение представляет собой
последовательность кодов отдельных
знаков первичного алфавита. Имеется
вариант кодирования, когда кодовый знак
относится к нескольким буквам первичного
алфавита или к целому слову первичного
языка. Такая комбинация называется
блоком. Кодирование блоков понижает
избыточность.
Системы
контроля кодирования
Рассмотренные
методы кодирования информации обеспечивают
надежное кодирование только в том
случае, если ЭВМ функционирует без
каких- либо нарушений. Если же появились
отклонения в работе ЭВМ, повлекшие за
собой ошибки при передаче и хранении
информации, то пользователь ЭВМ даже
не узнает об этом.
Системой
контроля называется совокупность
определенных методов и средств,
обеспечивающих необходимое
качество работы как всей ЭВМ, так
и отдельных ее элементов, а также
автоматическое исправление возникающих
ошибок называется
В
задачи системы контроля надежности
работы ЭВМ входят:
- профилактический контроль, т.е. предупреждение появления возможных ошибок;
- оперативный контроль – проверка качества выполнения машинных операций.
Будем
называть закодированное сообщение
эффективным, если для его передачи по
некоторому каналу связи использовалось
минимальное количество сигналов. Тогда
с учетом скорости передачи каждого
сигнала на передачу всего сообщения
будет затрачено минимальное
количество времени. Такой “выгодный”
код позволяет получить реальный
экономический эффект благодаря уменьшению
времени эксплуатации канала связи.
Как
известно, возможность эффективного
использования лишь двух символов 0 и 1
для кодирования указал Фрэнсис Бэкон.
Он первым применил в XVI в. принцип
двоичного кодирования для маскировки
тайнописи. Так, Бэкон, передавая сообщения
с помощью букв А и В, закодировал
пятерками, состоящими из этих букв, весь
латинский алфавит. Как известно, Лейбниц
использовал принцип двоичного кодирования
не только в своей двоичной арифметике,
но также и в так называемой двухзначной
логике.
Три
глобальные проблемы кодирования:
1. Создание
шифра кодирования;
2. Создание
специальных корректирующих кодов для
поиска и исправления ошибок, возникающих
в результате передачи и хранения
информации;
3. Минимизация
избыточной информации для успешной
коррекции и сокращения потерь в скорости
передачи сообщения.
Кодирование
и обработка чисел компьютером
Для
представления чисел в компьютере и
выполнения над ними арифметических
действий числа кодируются с помощью
нулей и единиц. Способы кодирования
чисел и допустимые над ними действия
зависят от принадлежности таковых
чисел к следующим числовым
множествам:
- Целые положительные числа (целые числа без знака);
- Целые числа со знаком;
- Вещественные нормализованные числа.
Кодирование
в компьютере целых положительных чисел
Для
записи числа в устройствах компьютера
выделяется фиксированное количество
двоичных разрядов. Память компьютера
имеет байтовую структуру, однако, размер
одной адресуемой ячейки обычно составляет
несколько байт. В компьютерах IBM ячейка
памяти объединяет 2 байта (16 двоичных
разрядов), что называется машинным
словом
Машинное
слово – комбинация связанных
соседних ячеек, обрабатываемая совместно
Для
представления числа в регистре арифметико-
логического устройства процессора,
где формируется результат операции,
имеется еще один дополнительный
одноразрядный регистр, который называется
регистром переноса и который можно
рассматривать в качестве продолжения
регистра результата (17- го бит).
Назначение этого бита выяснится позже.
Размер
разрядной сетки строго определен, в
связи с этим и количество чисел, с
которыми может оперировать компьютер
конечно, среди которых можно установить
наименьшее и наибольшее число. В обычном
не машинном представлении чисел такого
понятия как “наибольшее целое число”
просто не существует.
