Защита информации

Размещено на http://www.allbest.ru/

Лекция 1. Основные понятия теории информации

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

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

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

Информация может быть двух видов: дискретная (цифровая) и непрерывная (аналоговая). Дискретная информация характеризуется последовательными точными значениями некоторой величины, а непрерывная - непрерывным процессом изменения некоторой величины. Непрерывную информацию может, например, выдавать датчик атмосферного давления или датчик скорости автомашины. Дискретную информацию можно получить от любого цифрового индикатора: электронных часов, счетчика магнитофона и т.п.

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

При переводе непрерывной информации в дискретную важна так называемая частота дискретизации н, определяющая период (T = 1/н) между измерениями значений непрерывной величины (см. рисунок).

информация кодирование помехоустойчивый алгоритм

Размещено на http://www.allbest.ru/

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

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

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

Информацию принято измерять в битах и байтах. Данные понятия связаны с математическим понятием вероятности. Классический опыт, постоянно применяемый в теории вероятности - серия из n бросаний монеты. Выпадение «решки» на монете обозначим буквой «Р», орла - «О». Предположим, что мы хотим передать сообщение о результате серии из четырех испытаний, например «ООРО». Вероятность выпадения такой серии равна 1/16, для передачи сообщения требуется 4 бита. Этот простой пример может служить оправданием для следующего определения количества информации:

I = -log₂( P ),

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

Таким образом, если мы имеем источник, выдающий с равной вероятностью числа 0 и 1 (то есть P(0)=P(1)=1/2), то информация, приходящаяся на одну цифру равна -log(1/2) = 1 бит. Таким источником может быть, например, пешеходный светофор (красный или зеленый), время суток за окном (день или ночь), пол человека (мужчина или женщина).

Рассмотрим несколько примеров, в каждом из которых будем предполагать, что вероятности всех символов одинаковы. В случае русского алфавита (33 буквы) количество информации, приходящейся на одну букву равно -log₂(1/33)=5.044 битов, в случае латинского: -log₂(1/26)=4.7, для десятичных цифр - 3.32 бита на символ.

Вышесказанное можно изложить иначе:

Пусть алфавит источника сообщений состоит из m знаков, каждый из которых может служить элементом сообщения. Количество N возможных сообщений длины n равно числу перестановок с неограниченными повторениями: N = mⁿ

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

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

В качестве меры неопределенности выбора состояния источника с равновероятными состояниями принимают логарифм числа состояний:

I = log N = log mⁿ = n log m.

Эта логарифмическая функция характеризует количество информации в сообщении.

В принципе безразлично, какое основание логарифма использовать для определения количества информации, т. к. в силу соотношения log_am = log_a b / log_b m переход от одного основания логарифма к другому сводится лишь к изменению единицы измерения.

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

Так как из log₂ m = 1 следует m = 2, то ясно, что 1 бит - это количество информации, которым характеризуется один двоичный элемент при равновероятных состояниях 0 и 1.

Если основание логарифма выбрать равным десяти, то количество информации выражается в десятичных единицах на элемент сообщения - дитах, причем 1 дит = log₂10 бит = 3,32 бит. Данный факт проявляется, например, в том, что запись числа в двоичной системе счисления выглядит в среднем в 3,32 раза длиннее, чем запись этого же числа в десятичной системе счисления.

Можно сформулировать следующие свойства количества информации:

1. Количество информации в сообщении обратно пропорционально вероятности появления данного сообщения.

2. Свойство аддитивности - суммарное количество информации двух источников равно сумме информации источников.

3. Для события с одним исходом количество информации равно нулю.

4. Количество информации в дискретном сообщении растет в зависимости от увеличения объема алфавита - m.

Лекция 2. Энтропия

Как уже говорилось выше, если источник выдает цифры 0 и 1 с одинаковой вероятностью 1/2, то количество информации, приходящейся на одну цифру равно -log₂(1/2)=1 биту. Предположим теперь, что цифры появляются с различной вероятностью, P(0)=p, P(1)=q=1-p. Тогда количество информации, содержащейся в одной цифре так же будет различным. Если P(0)=0.99 и P(1)=0.01, то количество информации, соответствующей цифре "0" будет равно -log₂(0.99)=0.0145 битов, а цифре "1" - -log₂(0.01)=6.64 бита.

Пусть мы имеем достаточно длинное (длины n) сообщение в таком алфавите. В нем «0» появится в среднем p*n раз, а «1» - q*n=(1-p)*n раз. Учитывая количество информации, содержащейся в каждой цифре, мы можем сказать, что общее количество информации в сообщении длины n равно

- p*n*log(p) - q*n*log(q) = n*( - p*log(p) - q*log(q) ),

а среднее количество информации, приходящееся на один символ, равно

- p*log(p) - q*log(q).

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

Пусть алфавит состоит из N различных символов, которые появляются с вероятностями p(1),..., p(N) независимо друг от друга. Тогда среднее количество информации, приходящееся на один символ, равно

H = - p(1)*log(p(1)) - ... - p(n)*log(p(N)) = .

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

Для двухсимвольного алфавита, если вероятности появления символов одинаковы и равны 1/2, то энтропия потока равна 1 бит/символ. Если же P(0)=0.99, P(1)=0.01, то энтропия потока примерно равна 0.08 бит/символ. Подчеркнем, что эти рассуждения применимы только в потоку независимых символов, когда вероятность появления очередного символа не зависит от предыдущих.

Если в алфавите m символов и вероятности их появления равны (и составляют 1/m), то энтропия для одного символа данного алфавита будет равна

.

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

H = log₂(33) = 5,044394 бита.

При проектировании вычислительной техники в силу ее универсальности вероятности появления различных символов обычно считают одинаковыми. При этом энтропия показывает, какое минимальное количество бит требуется для кодирования одного символа заданного алфавита. Для 33 символов русского языка требуется, как показано выше, 5,044 бита. Однако для физической (аппаратной) реализации может быть выбрано только целое количество бит. Таким образом, округляя величину 5,044 к ближайшему большему целому, получаем, что для кодирования 33 символов требуется 6 бит. Если бы число букв в русском языке было равно 32, то энтропия была бы равной 5, и для кодирования букв требовалось бы ровно 5 двоичных разрядов.

Свойства энтропии:

1. Энтропия Н - величина вещественная, неотрицательная и ограниченная, т.е. Н 0. Это свойство следует из того, что такими же качествами обладают все ее слагаемые P(i) *log P(i).

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

3. Энтропия максимальна, если все знаки алфавита равновероятны, т.е. Н_max = log m.

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

Буква	Вероятность	Буква	Вероятность	Буква	Вероятность	Буква	Вероятность
а	0,062	й	0,010	т	0,053	ы	0,016
б	0,014	к	0,028	у	0,021	э	0,003
в	0,038	л	0,035	ф	0,002	ю	0,006
г	0,013	м	0,026	х	0,009	я	0,018
д	0,025	н	0,053	ц	0,004	пробел	0,175
е,ё	0,072	о	0,090	ч	0,012
ж	0,007	п	0,023	ш	0,006
з	0,016	р	0,040	щ	0,003
и	0,062	с	0,045	ъ,ь	0,014

Лекция 3. Некоторые методы сжатия информации

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

Пусть энтропии двух источников сообщений Н₁<Н₂, а количество информации, получаемое от них, одинаковое, т.е. I = n₁H₁ = n₂H₂, где n₁ и n₂ - длина сообщения от первого и второго источников. Обозначим

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

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

При этом доля излишних элементов оценивается коэффициентом избыточности:



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

Избыточность устраняют построением оптимальных кодов, которые укорачивают сообщения по сравнению с равномерными кодами. Это используют при архивации данных. Действие средств архивации основано на использовании алгоритмов сжатия, имеющих достаточно длинную историю развития, начавшуюся задолго до появления первого компьютера еще в 40-х гг. XX века. Группа ученых-математиков, работавших в области электротехники, заинтересовалась возможностью создания технологии хранения данных, обеспечивающей более экономное расходование пространства. Одним из них был Клод Элвуд Шеннон, основоположник современной теории информации. Из разработок того времени позже практическое применение нашли алгоритмы сжатия Хаффмана и Шеннона-Фано. А в 1977 г. математики Якоб Зив и Абрахам Лемпел придумали новый алгоритм сжатия, который позже доработал Терри Велч. Большинство методов данного преобразования имеют сложную теоретическую математическую основу. Суть работы архиваторов заключается в следующем: они находят в файлах избыточную информацию (например, повторяющиеся участки и пробелы), кодируют их, а затем при распаковке восстанавливают исходные файлы по особым отметкам. Основой для архивации послужили алгоритмы сжатия Я. Зива и А. Лемпела. Первым широкое признание получил архиватор Zip. Со временем завоевали популярность и другие программы: RAR, ARJ, АСЕ, TAR, LHA и т.д.

При архивации надо иметь в виду, что качество сжатия файлов сильно зависит от степени избыточности хранящихся в них данных, которая определяется их типом. К примеру, степень избыточности у видеоданных обычно в несколько раз больше, чем у графических, а степень избыточности графических данных в несколько раз больше, чем текстовых. На практике это означает, что, скажем, изображения форматов BMP и TIFF, будучи помещенными в архив, как правило, уменьшаются в размере сильнее, чем документы MS Word. А вот рисунки JPEG уже заранее компрессированы, поэтому даже самый лучший архиватор для них будет мало эффективен. Также крайне незначительно сжимаются исполняемые файлы программ и архивы.

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

В В В В В L L L L L А А А А А

В шестнадцатеричной системе

42 42 42 42 42 4С 4С 4С 4С 4С 41 41 41 41 41

Архиватор может представить этот файл в следующем виде (шестнадцатеричном):

01 05 42 06 05 4С 0А 05 41

Это значит: с первой позиции пять раз повторяется символ "В", с позиции 6 пять раз повторяется символ "L" и с позиции 11 пять раз повторяется символ "А". Для хранения файла в такой форме потребуется всего 9 байт, что на 6 байт меньше исходного.

Описанный метод является простым и очень эффективным способом сжатия файлов. Однако он не обеспечивает большой экономии объема, если обрабатываемый текст содержит небольшое количество последовательностей повторяющихся символов.

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

Эффективность кода определяется средним числом двоичных разрядов для кодирования одного символа I_ср по формуле

,

где k - число символов исходного алфавита, n_i - число двоичных разрядов для кодирования i-го символа, p_i - частота i-го символа (сумма частот всех символов равна единице).

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

.

Существуют два классических метода эффективного кодирования: метод Шеннона-Фано и метод Хаффмана. Входными данными для обоих методов является заданное множество исходных символов для кодирования с их частотами; результатом кодирования являются эффективные двоичные коды символов.

Метод Шеннона-Фано

Этот метод требует упорядочения исходного множества символов по не возрастанию их частот. Затем выполняются следующие шаги:

а) список символов делится на две части (назовем их первой и второй частями) так, чтобы суммы частот обеих частей (назовем их У₁ и У₂) были точно или примерно равны. В случае, когда точного равенства достичь не удается, разница между суммами должна быть минимальна;

б) кодовым комбинациям первой части дописывается бит «1», кодовым комбинациям второй части дописывается бит «0»;

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

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

д) анализируется оставшийся список: если он пуст - код построен, работа заканчивается. Если нет, - выполняется шаг а).

Пример 1. Даны символы `a', `b', `c', `d' с частотами p_a=0,5; p_b=0,25; p_c=0,125; p_d=0,125. Построить эффективный код методом Шеннона-Фано. Сведем исходные данные в таблицу, упорядочив их по невозрастанию частот:

Исходные символы	Частоты символов
a	0,5
b	0,25
c	0,125
d	0,125

Первая линия деления проходит под символом a: соответствующие суммы У₁ и У₂ равны между собой и равны 0,5. Тогда формируемым кодовым комбинациям дописывается 1 для верхней (первой) части и 0 для нижней (второй) части. Поскольку это первый шаг формирования кода, двоичные цифры не дописываются, а только начинают формировать код:

Исходные символы	Частоты символов	Формируемый код
a	0,5	1
b	0,25	0
c	0,125	0
d	0,125	0

В силу того, что верхняя часть списка содержит только один элемент (символ а), работа с ней заканчивается, а эффективный код для этого символа считается сформированным (в таблице, приведенной выше, эта часть списка частот символов выделена заливкой). Второе деление выполняется под символом b: суммы частот У₁ и У₂ вновь равны между собой и равны 0,25. Тогда кодовой комбинации символов верхней части дописывается 1, а нижней части - 0. Таким образом, к полученным на первом шаге фрагментам кода, равным 0, добавляются новые символы:

Исходные символы	Частоты символов	Формируемый код
a	0,5	1
b	0,25	01
c	0,125	00
d	0,125	00

Поскольку верхняя часть нового списка содержит только один символ (b), формирование кода для него закончено (соответствующая строка таблицы вновь выделена заливкой). Третье деление проходит между символами c и d: к кодовой комбинации символа c приписывается 1, коду символа d приписывается 0:

Исходные символы	Частоты символов	Формируемый код
a	0,5	1
b	0,25	01
c	0,125	001
d	0,125	000

Поскольку обе оставшиеся половины исходного списка содержат по одному элементу, работа со списком в целом заканчивается. Таким образом, получили коды: а - 1, b - 01, c - 001, d - 000. Определим эффективность построенного кода по формуле:

I_ср = 0,5*1 + 0,25*2 + 0,125*3 + 0,125*3 = 1,75.

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

Лекция 4. Оптимальное кодирование (метод Хаффмана)

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

1) объединение частот:

- две последние частоты списка складываются, а соответствующие символы исключаются из списка;

- оставшийся после исключения символов список пополняется суммой частот и вновь упорядочивается;

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

2) построение кодового дерева:

- строится двоичное кодовое дерево: корнем его является вершина, полученная в результате объединения частот, равная 1, листьями - исходные вершины;

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

- ребра дерева связывают вершины-суммы с вершинами-слагаемыми.

Структура дерева показывает, как происходило объединение частот. Ребра дерева кодируются: каждое левое кодируется единицей, каждое правое - нулём.

3) формирование кода: для получения кодов листьев (исходных кодируемых символов) продвигаются от корня к нужной вершине и «собирают» веса проходимых рёбер.

Рассмотрим пример.

Даны символы a, b, c, d с частотами p(a) = 0,5; p(b) = 0,25; p(c) = 0,125; p(d)= 0,125. Построить эффективный код методом Хаффмана.

1) объединение частот (результат объединения двух последних частот в списке выделен в правом соседнем столбце штриховкой).

Исходные символы	Частоты символов	Этапы объединения
		первый	второй	третий
a	0,5	0,5	0,5	1
b	0,25	0,25	0,5
c	0,125	0,25
d	0,125

2) Построение кодового дерева.

Размещено на http://www.allbest.ru/

3) формирование кода:

K(a) = 1; K(b) = 01; K(c) = 001; K(d) = 000.

Как видно, полученные коды совпадают с теми, что были сформированы методом Шеннона-Фано, следовательно, они имеют одинаковую эффективность.

Повышение эффективности кодирования

Повысить эффективность кодирования можно, строя код не для символа, а для блоков из n символов, причем частота блока рассчитывается как произведение частот символов, входящих в блок. Рассмотрим этот тезис на примере.

Даны символы a и b с частотами, соответственно, 0,9 и 0,1. Построить эффективный код методом Шеннона-Фано для блоков из двух символов (n = 2). Сформируем список возможных блоков и их частот. При этом частоту блока будем рассчитывать как произведение частот символов, входящих в блок. Тогда имеем:

Блоки символов Частоты блоков

aa 0,81

ab 0,09

ba 0,09

bb 0,01

Построение кода сведём в таблицу:

Блоки символов	Частоты блоков	Этапы построения кода
		первый	второй	третий
aa	0,81	1
ab	0,09	0	1
ba	0,09	0	0	1
bb	0,01	0	0	0

Таким образом, получены коды:

K(aa) = 1; K(ab) = 01; K(ba) = 001; K(bb) = 000.

Определим эффективность построенного кода. Для этого рассчитаем сначала показатель эффективности для блока символов:

I_{ср. блока} = 0,81*1 + 0,09*2 + 0,09*3 + 0,01*3 = 1,28.

Поскольку в блоке 2 символа (n=2), для одного символа

I_ср =I_{ср. блока}/2 = 1,28/2 = 0,64.

При посимвольном кодировании для эффективного кода потребуется по одному двоичному разряду, т.е. на (1-0,64)=0,36 бита больше. В самом деле, применение метода Шеннона-Фано для отдельных символов даёт результат, представленный в следующей таблице:

Исходные символы	Частоты символов	Коды символов
a	0,5	1
b	0,25	0

Лекция 5. Принципы помехоустойчивого кодирования

Ошибка в кодовой комбинации появляется при ее передаче по каналу связи вследствие замены одних элементов другими под воздействием помех. Например, 2-кратная ошибка возникает при замене (искажении) двух элементов: если кодовая комбинация 0110111 принята как 0100110, то имеет место двукратная ошибка.

Теория помехоустойчивого кодирования базируется на результатах исследований, проведенных Шенноном и сформулированных в виде теоремы:

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

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

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

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

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

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

На практике точность передачи информации и эффективность каналов связи ограничивается двумя факторами:

размером и стоимостью аппаратуры кодирования/декодирования;

временем задержки передаваемого сообщения.

Разновидности помехоустойчивых кодов

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

Эти коды используют для:

исправления ошибок - корректирующие коды;

обнаружения ошибок.

Корректирующие коды основаны на введении избыточности.

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

Алгебраические коды подразделяются на два класса:

блоковые;

непрерывные (сверточные).

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

Блоковый код называют равномерным, если n остается постоянным для всех букв сообщения.

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

При кодировании неразделимыми кодами разделить символы входной последовательности на информационные и проверочные невозможно.

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

Общие принципы использования избыточности

Способность кода обнаруживать и исправлять ошибки обусловлена наличием в нем избыточных символов.

На вход кодирующего устройства поступает последовательность из k информационных двоичных символов. На выходе ей соответствует последовательность из n двоичных символов, причем n>k.

Всего может быть 2^k различных входных и 2ⁿ различных выходных последовательностей.

Из общего числа 2ⁿ выходных последовательностей только 2^k последовательностей соответствуют входным. Их называют разрешенными кодовыми комбинациями.

Остальные (2ⁿ-2^k) возможных выходных последовательностей для передачи не используются. Их называют запрещенными кодовыми комбинациями.

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

Так как каждая из 2^k разрешенных комбинаций в результате действия помех может трансформироваться в любую другую, то всегда имеется 2^k * 2ⁿ возможных случаев передачи. В это число входят:

2^k случаев безошибочной передачи;

2^k(2^k -1) случаев перехода в другие разрешенные комбинации, что соответствует необнаруженным ошибкам;

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

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

.

Пример: Определим обнаруживающую способность кода, каждая комбинация которого содержит всего один избыточный символ (n=k+1).

1. Общее число выходных последовательностей составляет 2ⁿ=2^k+1, т.е. вдвое больше общего числа кодируемых входных последовательностей.

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

3. При кодировании к каждой последовательности из k информационных символов добавляют один символ (0 или 1), такой, чтобы число единиц в кодовой комбинации было четным. Изменение (в процессе передачи) любого нечетного числа символов переводит разрешенную кодовую комбинацию в подмножество запрещенных комбинаций, что обнаруживается на приемной стороне по нечетности числа единиц. Часть опознанных ошибок составляет

.

Любой метод декодирования можно рассматривать как правило разбиения всего множества запрещенных кодовых комбинаций на 2^k пересекающихся подмножеств M_i, каждая из которых ставится в соответствие одной из разрешенных комбинаций. При получении запрещенной комбинации, принадлежащей подмножеству M_i, принимают решение, что передавалась запрещенная комбинация A_i. Ошибка будет исправлена в тех случаях, когда полученная комбинация действительно образовалась из A_i, т.е. 2ⁿ-2^k cлучаях.

Всего случаев перехода в неразрешенные комбинации 2^k(2ⁿ - 2^k). Таким образом, при наличии избыточности любой код способен исправлять ошибки.

Отношение числа исправляемых кодом ошибочных кодовых комбинаций к числу обнаруживаемых ошибочных комбинаций равно

.

Способ разбиения на подмножества зависит от того, какие ошибки должны направляться конкретным кодом.

Лекция 7. Коды, обнаруживающие ошибки. CRC-коды

CRC (Cyclic Redundancy Code - циклический избыточный код) - последовательность бит, полученная по определенному алгоритму на основании другой (исходной) битовой последовательности. Главная особенность (и практическая значимость) значения CRC состоит в том, что оно однозначно идентифицирует исходную битовую последовательность.

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

Основная идея вычисления CRC заключается в следующем. Исходная последовательность байтов, которой могут быть и огромный файл, и текст размером несколько слов и даже символов, представляется единой последовательностью битов. Эта последовательность делится (по определенным правилам) на некоторое фиксированное двоичное число. Интерес представляет остаток от этого деления, который и является значением CRC. Все, что теперь требуется, -- это некоторым образом запомнить его и передать вместе с исходной последовательностью. Приемник данной информации всегда может таким же образом выполнить деление и сравнить его остаток с исходным значением CRC. Если они равны, то считается, что исходное сообщение не повреждено.

CRC-арифметика

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

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

u(x) = u_nxⁿ + u_n-1x^n-1 + … + u₁x¹ + u₀x⁰.

Здесь u_i - элементы некоторой алгебраической системы S, называемые коэффициентами; x - переменная полинома, которую можно рассматривать как формальный символ без определенного значения. Алгебраическая система S обычно представляет собой множество целых или рациональных чисел в диапазоне 0...m-1 со сложением, вычитанием и умножением, выполняемыми по модулю m. Для нашего рассмотрения особенно важна полиномиальная арифметика по модулю 2, в которой каждый коэффициент полинома равен одному из двух значений - 0 или 1. Например, шестнадцатеричное значение E3₁₆ может быть представлено следующим полиномом:

12⁷ + 12⁶ + 12⁵ + 02⁴ + 02³ + 02² + 12¹ + 12⁰.

Если вместо двойки использовать переменную x=2, то получим следующий двоичный полином:

1x⁷ + 1x⁶ + 1x⁵ + 0x⁴ + 0x³ + 0x² + 1x¹ + 1x⁰.

В этом полиноме, строго говоря, значение х не играет особой роли, так как данное двоичное число можно представить полиномом в другой системе счисления, например, шестнадцатеричной: Eх¹ + 3х⁰, где х=16. При этом заметим, что в том и другом случае цифры 0, 1, E, 3 - это просто цифры двоичной и шестнадцатеричной систем счисления.

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

1x⁷ + 1x⁶ + 1x⁵ + 0x⁴ + 0x³ + 0x² + 1x¹ + 1x⁰ =

= 1x⁷ + 1x⁶ + 1x⁵ + 1x¹ + 1x⁰ =

= x⁷ + x⁶ + x⁵ + x¹ + x⁰.

Над полиномами можно выполнять арифметические операции: сложение, вычитание, умножение и деление. Процессы выполнения этих операций для полиномиальной арифметики и обычной арифметики похожи. Главное отличие в том, что из-за отсутствия связи между коэффициентами полинома понятие переноса в полиномиальной арифметике отсутствует. Например, для умножения 7h (полином с коэффициентами 0111) на 5h (полином с коэффициентами 0101) выполняются действия:

(x² + x¹ + x⁰)(x² + x⁰) = x⁴ + x³ + x² + x² + x¹ + x⁰ = x⁴ + x³ + 2x² + x¹ + x⁰.

Для того, чтобы в ответе получить 35, необходимо взять x=2 и привести коэффициенты, не равные 1, к двоичным, сделав переносы соответствующих единиц в старшие разряды. В нашем случае коэффициент при x² равен 2₁₀=10₂, что для двоичной системы счисления эквивалентно выражению (1x³ + 0x²). Тогда полином принимает вид: x⁴ + 2x³ + 0x² + x¹ + x⁰, и при подстановке x=2 получаем 2⁴ + 22³ + 2¹ + 2⁰ = 2⁴ + 2⁴ + 2¹ + 2⁰ = 22⁴ + 2¹ + 2⁰ = 2⁵ + 2¹ + 2⁰ = 32+2+1 = 35. Последнее выражение соответствует двоичному полиному x⁵+x¹+x⁰.

Эти рассуждения призваны сформулировать тезис о том, что переносы, как и в обычной арифметике, можно выполнять в случае, когда известно основание системы счисления. То есть до тех пор, пока мы не знаем х, мы не можем производить и переносы. В приведенном выше примере, мы не знаем, что 2х² на самом деле является х³ до тех пор, пока не известно, что х=2. То есть в полиномиальной арифметике коэффициенты при разных степенях изолированы друг от друга и отношения между ними не определены. Из-за этого возникает первая странность полиномиальной арифметики - операции сложения и вычитания в ней абсолютно идентичны и вместо них можно смело оставлять одну. Например, сложение по правилам полиномиальной арифметики по модулю 2 (CRC-арифметики), будет выполнено так:

	11111011
+	11001010
	00110001

Из этого примера видны правила сложения двоичных разрядов в арифметике t с отсутствием переносов: 0+0=0; 0+1=1; 1+0=1; 1+1=0.

Операцию вычитания демонстрирует следующий пример:

	11111011
-	11001010
	00110001

Правила выполнения вычитания в арифметике с отсутствием переносов: 0-0=0; 0-1=1; 1-0=1; 1-1=0.

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

Умножение в арифметике с отсутствием переносов также выполняется с учетом особенностей CRC-сложения:

		x	1101
			1011 ----
1101
1101
0000
1101 -------
1111111

Видно, что в самом умножении особенностей нет, а вот сложение промежуточных результатов производится по правилам CRC-сложения.

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

Здесь необходимо ввести так называемое слабое понятие размерности: число X больше или равно числу Y, если оба числа имеют одинаковую размерность и значения их старших битов единичны. При этом соотношение остальных битов чисел X и Y для операции сравнения не имеет значения. Рассмотрим примеры операции деления, причем для лучшего понимания сделаем это в двух вариантах: вначале вспомним, как выполняется обычное деление (по правилам двоичной арифметики с циклическим переносом), а затем выполним собственно CRC-деление.

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

Обычное деление:

CRC-деление:

Реальные двоичные последовательности являются результатом сцепления огромного количества отдельных байтов (символов), образуя одно большое двоичное число, для представления которого нужно использовать двоичные полиномы огромных степеней. При этом каждый бит в подобной последовательности произвольной длины представляется в виде коэффициента полинома. Например, для представления 128-байтового блока необходим полином, состоящий из 128*8=1024 слагаемых, а для 1024-битного блока необходим полином уже с 1024*8=8192 слагаемыми. В терминах полиномиальной арифметики двоичное число, сформированное в результате подобной сцепки составляющих блока данных, называется полиномом данных и обозначается как D(x). В алгоритме вычисления CRC вводится еще несколько полиномов и соотношений между ними:

- порождающий полипом G(x) - предварительно особым образом выбранный полином, на который делится исходный полином D(x);

- полином-частное Q(x) - полином, получившийся в качестве частного от деления полиномов D(x)/G(x);

- полином-остаток R(x) - полином, получившийся в качестве остатка от деления полиномов D(x)/G(x).

Между перечисленными полиномами существуют следующие отношения:

D(x) = Q(x) G(x) + R(x),

Q(x) = (D(x) - R(x)) / G(x).

Эти соотношения приводят к следующим основополагающим для дальнейшего рассмотрения тезисам:

- операция деления двух двоичных полиномов D(x)/G(x), где G(x)?0, дает в качестве результата полином-частное Q(x) и полином-остаток R(x), удовлетворяющие условиям: D(x)=Q(x)G(x)+R(x);

- остаток от деления двух полиномов R(x) является двоичным числом, которое после вычитания из D(x) дает в результате еще один полином, делящийся без остатка на G(x); получающееся в результате этого деления частное Q(x) отбрасывается за ненадобностью, а полином-остаток R(x) называют CRC.

Из приведенного выше описания общей схемы вычисления CRC возникает ряд вопросов: что представляет собой этот магический делитель G(x), каков его размер? Выбор порождающего полинома G(x) - достаточно сложная задача. Перечислим некоторые важные свойства, которые должны учитываться при этом.

1. Число разрядов (количество членов) в полиноме-остатке R(x) непосредственно определяется длиной самого порождающего полинома G(x). Выбор G(x) длиной n гарантирует, что полином-остаток от деления R(x) будет иметь разрядность не более, чем n-1. Это следует из общего свойства операции деления, которое предполагает, что остаток от деления должен быть меньше делителя.

2. Порождающий полином G(x) должен быть полиномиально простым. Это означает его неделимость нацело на полиномы со значением в диапазоне от 2 до самого себя.

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

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

- х¹⁶+х¹²+х⁵+х⁰ - полином 1021₁₆, используемый в протоколе XMODEM и производных от него протоколах передачи данных. Он стандартизован в спецификации V.41 МККТТ «Кодонезависимая система контроля ошибок».

- х¹⁶+х¹⁵+х²+х⁰ - полином C005₁₆, используемый в протоколах двоичной синхронной передачи фирмы IBM. Он также стандартизован в приложении А «Процедура коррекции ошибок для оконечного оборудования линии с использованием асинхронно-синхронного преобразования» к стандарту V.42 МККТТ. Этот же полином широко известен как полином, используемый в алгоритме вычисления CRC -- CRC16.

- x³²+x²⁶+x²³+x²²+x¹⁶+x¹²+x¹¹+x¹⁰+x⁸+x⁷+x⁵+x⁴+x²+x¹+x⁰ - полином 04C11DB7₁₆, используемый в алгоритме вычисления CRC - CRC32 и также стандартизованный в стандарте V.42 МККТТ. Этот полином, в частности, используется в технологии локальных вычислительных сетей Ethernet. Необходимо отметить, что вычисление по алгоритму CRC32 зачастую проводят и с другим полиномом: 0EDB88320₁₆:

- x³²+x³¹+x³⁰+x²⁹+x²⁷+x²⁶+x²⁴+x²³+x²¹+x²⁰+х¹⁹+х¹⁵+х⁹+х⁸+х⁵. Такой полином используют различные архиваторы. Необходимо заметить, что полином 0EDB88320₁₆ - это просто зеркальное отражение полинома 04C11DB7₁₆.

С полиномом связано еще одно понятие - степени полинома, которое по определению является номером позиции его старшего единичного бита (считая от нуля). Например, для полинома 1011 степень равна 3.

В качестве выводов отметим, что CRC-арифметика отличается от двоичной отсутствием переносов/заемов, а CRC-вычитание и сложение выполняются по тем же правилам, что и логическая операция XOR, что и обусловливает ее важную роль при вычислении значений CRC.

Лекция 8. Алгоритмы вычисления CRC

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

1. Выбрать полином Р. При этом становится известной его степень N.

2. Добавить в конец исходной двоичной последовательности N нулевых битов. Это добавление делается для гарантированной обработки всех битов исходной последовательности.

3. Выполнить деление дополненной N нулями исходной строки S на полином Р по правилам CRC-арифметики. Запомнить остаток, который и будет являться CRC.

4. Сформировать окончательное сообщение, которое будет состоять из двух частей: собственно сообщения и добавленного в его конец значения CRC.

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



Из рисунка видно, что в начале вычисления исходная последовательность 1101001110010110100 дополняется нулями в количестве, равном степени полинома (используемый полином Р=1011, степень полинома N=3): 1101001110010110100+000. При выполнении CRC-деления эти дополнительные биты гарантируют, что все биты исходной последовательности примут участие в процессе формирования значения CRC, что позволит обнаружить ошибку, возникшую в любом из битов исходного сообщения. Результирующая последовательность получается равной исходной последовательности, дополненной значением CRC: 1101001110010110100+011. Заметим, что длина присоединяемого к исходной последовательности значения CRC должна быть равна степени полинома, даже если CRC, как в нашем случае, имеет незначащие нули. Это очень важный момент, понимание которого является ключом к пониманию сути процессов, происходящих на стороне приемника при получении и определении целостности исходного сообщения. Действия алгоритма для приемника просты - выполнить деление полученной последовательности на полином. При этом для выполнения деления нет необходимости дополнять исходную последовательность нулями, тем более что на практике соблюдение этого условия крайне неудобно. Приемник попросту выполняет CRC-деление полученной исходной строки (дополненной в конце

...