Теория информации

1 /30 Лекции по дисциплине «Теория информации» Литература 1. Лидовский В. В. Теория информации: Учебное пособие. — М.: Компания Спутник+, 2004. — 111 с. http://globalteka.ru/books/doc_details/9415----.html Основные понятия теории информации Информация (от лат. informatio, разъяснение, изложение, осведомленность) — сведения о чем-либо, независимо от формы их представления. Теория информации — комплексная, в основном математическая теория, включающая в себя описание и оценки методов извлечения, передачи, хранения и классификации информации. Получение, создание, сбор, обработка, накопление, хранение, поиск, распространение и использование информации называется информационным процессом. Математическое представление информационного процесса называется математической моделью. Для извлечения, передачи, хранения и классификации информации требуется формальное представление информации. При формальном представлении информации каждому описываемому объекту или понятию ставится в соответствие некоторый числовой код. Формализованный вид информации, представленный математическими величинами (числовым кодом), называют данными. Данные, являющиеся результатом фиксации некоторой информации, сами могут выступать как источник информации. Информация, извлекаемая из данных, может подвергаться обработке, и результаты обработки фиксируются в виде новых данных. Форма представления информации, имеющая признаки начала и конца, предназначенная для передачи через среду связи называется сообщением. Сообщением также является форма предоставления информации как совокупность первичных сигналов или знаков, содержащих информацию. Знак (символ) представляет собой соглашение (явное или неявное) о приписывании чему-либо Сообщением также является форма предоставления информации как совокупность первичных сигналов или знаков, содержащих информацию. Знак представляет собой соглашение (явное или неявное) о приписывании чему-либо (означающему) какого-либо определённого смысла. Знаком также называют конкретный случай использования такого соглашения для передачи информации. Знак может быть составным, то есть состоять из нескольких других знаков. Например, цифры являются знаками чисел. Буквы являются знаками звуков и, вместе со словами, являются знаками человеческого языка. Материальным носителем информации, используемым для передачи сообщений, является сигнал. Сигнал может генерироваться, но его приём не обязателен, в отличие от сообщения, которое должно быть принято принимающей стороной, иначе оно не является сообщением. Сигналом может быть любой физический процесс, параметры которого изменяются в соответствии с передаваемым сообщением. Теория информации оперирует с математическими моделями. Использует, главным образом, математический аппарат теории вероятностей и математической статистики. Основные разделы теории информации — кодирование источника (сжимающее или экономное кодирование) и канальное (помехоустойчивое) кодирование. Кодированием называется процесс преобразования сообщения в комбинацию символов в соответствии с кодом. Процесс восстановления сообщения из комбинации символов называется декодированием. Теория информации тесно связана с криптографией и другими смежными дисциплинами. Криптография — наука о методах обеспечения конфиденциальности (невозможности прочтения информации посторонним) и аутентичности (целостности и подлинности авторства, а также невозможности отказа от авторства) информации. Формальное представление информации Для перевода информации в формальный, цифровой вид используются специальные таблицы, сопоставляющие кодируемым сущностям их коды и называемые таблицами кодировки. Такой процесс сопоставления называют примитивным кодированием. Примеры подобных таблиц (их еще называют кодовыми страницами или применяют английский термин character set, который иногда сокращают до charset). 2 /30 Самой известной таблицей кодировки является код ASCII (Американский стандартный код для обмена информацией). Первоначально он был разработан для передачи текстов по телеграфу, причем в то время он был 7-битовым, то есть для кодирования символов английского языка, служебных и управляющих символов использовались только 128 7-битовых комбинаций. При этом первые 32 комбинации (кода) служили для кодирования управляющих сигналов (начало текста, конец строки, перевод каретки, звонок, конец текста и т.д.). При разработке первых компьютеров фирмы IBM этот код был использован для представления символов в компьютере. Поскольку в исходном коде ASCII было всего 128 символов, для их кодирования хватило значений байта, у которых 8-ой бит равен 0. Значения байта с 8-ым битом, равным 1, стали использовать для представления символов псевдографики, математических знаков и некоторых символов из языков, отличных от английского. Когда стали приспосабливать компьютеры для других стран и языков, места для новых символов уже не стало хватать. Для того, чтобы полноценно поддерживать помимо английского и другие языки, фирма IBM ввела в употребление несколько кодовых таблиц, ориентированных на конкретные страны. Так для скандинавских стран была предложена таблица 865 (Nordic), для арабских стран — таблица 864 (Arabic), для Израиля — таблица 862 (Israel) и так далее. В этих таблицах часть кодов из второй половины кодовой таблицы использовалась для представления символов национальных алфавитов (за счет исключения некоторых символов псевдографики). С русским языком ситуация развивалась особым образом. Очевидно, что замену символов во второй половине кодовой таблицы можно произвести разными способами. Вот и появились для русского языка несколько разных таблиц кодировки символов кириллицы: KOI8-R, IBM-866, CP-1251, ISO-8551-5. Все они одинаково изображают символы первой половины таблицы (от 0 до 127) и различаются представлением символов русского алфавита и псевдографики. Для таких же языков, как китайский или японский, вообще 256 символов недостаточно. Кроме того, всегда существует проблема вывода или сохранения в одном файле одновременно текстов на разных языках (например, при цитировании). Поэтому была разработана универсальная кодовая таблица UNICODE, содержащая символы, применяемые в языках всех народов мира, а также различные служебные и вспомогательные символы (знаки препинания, математические и технические символы, стрелки, диакритические знаки и т.д.). Очевидно, что одного байта недостаточно для кодирования такого большого множества символов. Поэтому в UNICODE используются 16-битовые (2-байтовые) коды, что позволяет представить 65 536 символов. К настоящему времени задействовано около 49 000 кодов (последнее значительное изменение — введение символа валюты EURO в сентябре 1998 г.). Для совместимости с предыдущими кодировками первые 256 кодов совпадают со стандартом ASCII. В стандарте UNICODE кроме определенного двоичного кода (эти коды принято обозначать буквой U, после которой следуют знак + и собственно код в шестнадцатеричном представлении) каждому символу присвоено определенное имя. Еще одним компонентом стандарта UNICODE являются алгоритмы для взаимнооднозначного преобразования кодов UNICODE в последовательности байтов переменной длины. Необходимость таких алгоритмов обусловлена тем, что не все приложения умеют работать с UNICODE. Некоторые приложения понимают только 7-битовые ASCII-коды, другие приложения - 8-битовые ASCII-коды. Такие приложения используют для представления символов, не поместившихся, соответственно, в 128-символьный или 256-символьный набор, так называемые расширенные ASCII-коды, когда символы кодируются цепочками байтов переменной длины. Алгоритм UTF-7 служит для обратимого преобразования кодов UNICODE в расширенные 7-битовые ASCII-коды, а UTF-8 - для обратимого преобразования кодов UNICODE в расширенные 8-битовые ASCII-коды. Отметим, что и ASCII и UNICODE и другие стандарты кодировки символов не определяют изображения символов, а только состав набора символов и способ его представления в компьютере. Кроме того (что, может быть, не сразу очевидно), очень важен порядок перечисления символов в наборе, так как он влияет самым существенным образом на алгоритмы сортировки. Именно таблицу соответствия символов из какого-то определенного набора (скажем, символов, применяемых для представления информации на английском языке, или на разных языках, как в случае с UNICODE) и обозначают термином таблица кодировки символов или charset. Каждая стандартная кодировка имеет имя, например, KOI8-R, ISO_88591, ASCII. Стандарта на имена кодировок не существует. Единицы измерения информации Бит (англ. binary digit; также игра слов: англ. bit — немного) — один двоичный разряд в двоичной системе счисления. Обозначается по ГОСТ 8.417-2002. Для образования кратных единиц применяется с приставками СИ и с двоичными приставками, принятыми МЭК. Международная электротехническая комиссия (МЭК) — международная некоммерческая организация по стандартизации в области электрических, электронных и смежных технологий. 3 /30 Приставка Аналогичная десятичная приставка Сокращения по МЭК для битов, байтов Значение, на которое исходная величина умножается киби кило (103) Кибит, КиБ 210 = 1 024 меби мега (106) Мибит, МиБ 220 = 1 048 576 гиби гига (109) Гибит, ГиБ 230 = 1 073 741 824 теби тера (1012) Тибит, ТиБ 240 = 1 099 511 627 776 пеби пета (1015) Пибит, ПиБ 250 = 1 125 899 906 842 624 эксби экса (1018) Эибит, ЭиБ 260 = 1 152 921 504 606 846 976 зеби зетта (1021) Зибит, ЗиБ 270 = 1 180 591 620 717 411 303 424 йоби йотта (1024) Йибит, ЙиБ 280 = 1 208 925 819 614 629 174 706 176 Клод Элвуд Шеннон (Claude Elwood Shannon — американский инженер и математик, является основателем количественной теории информации) в 1948 г предложил использовать слово bit для обозначения наименьшей единицы информации: Бит — это двоичный логарифм вероятности равновероятных событий или сумма произведений вероятности на двоичный логарифм вероятности при равновероятных событиях; Бит — базовая единица измерения количества информации, равная количеству информации, содержащемуся в опыте, имеющем два равновероятных исхода. Бит — один разряд двоичного кода (двоичная цифра). Может принимать только два взаимоисключающих значения: да/нет, 1/0, включено/выключено, и т. п. В электронике 1 двоичному разряду соответствует 1 двоичный триггер, который имеет два устойчивых состояния. Двоичные логарифмы других оснований Нат Замена логарифма 2 на e, приводит к единицам нат (log2e ≈ 1,443 бит.), 1 бит = ln 2 ≈ 0,693 нат, Трит Один трит (trinary digit), как один троичный разряд, может принимать три возможных значения (состояния, кода): 0, 1 и 2. 1 трит (трор) равен троичному логарифму 3-х возможных состояний (кодов) одного троичного разряда Трит является подмножеством троичного разряда, который является одним троичным числовым разрядом троичного представления числа в троичной системе счисления. Один троичный числовой разряд (одна позиция, одно знакоместо) троичного представления числа в троичной системе счисления Троичный разряд может принимать только три взаимоисключающих значения (три троичных величины), которым соответствуют три троичные цифры (три троичных знака), которые могут иметь разные обозначения: Состояния в троичных системах счисления 1 −1 1 − i N N ложь ложно false false false 2 1 O Z неизвестно Не определено null unknown Fail 3 2 +1 1 + 1 P P истина истинно true true True Децит Один децит (decimal digit) (дит — dit, Хартли — Hart, бан — ban) как один десятичный разряд, может принимать десять возможных значения (состояния, кода): 0, 1, 2, 3, 4, 5, 6, 7, 8 и 9. Байт Байт (англ. byte) — единица хранения и обработки цифровой информации, это совокупность битов, обрабатываемая компьютером одномоментно. В современных вычислительных системах байт считается равным восьми битам, в этом случае он может принимать одно из 256 (28) различных значений (состояний, кодов). Однако в истории компьютеров известны решения с другим размером байта, 4 /30 например 6 битов, 36 битов в PDP-10. Поэтому иногда в компьютерных стандартах и официальных документах для однозначного обозначения 8-битного слова используется термин «октет» (лат. octet). В большинстве вычислительных архитектур байт — это минимальный независимо адресуемый набор данных. Название «байт» (слово byte представляет собой сокращение словосочетания BinarY TErm — «двоичный терм») было впервые использовано в 1956 году В. Бухгольцем (англ. Werner Buchholz) при проектировании первого суперкомпьютера IBM 7030 (англ.) для пучка одновременно передаваемых в устройствах ввода-вывода шести битов. Позже, в рамках того же проекта, байт был расширен до восьми бит. Байтовая адресация памяти была впервые применена в системе IBM System/360. В более ранних компьютерах адресовать можно было только целиком машинное слово, состоявшее из нескольких байтов, что затрудняло обработку текстовых данных. Восьмибитные байты были приняты в System/360, вероятно, из-за использования BCD-формата представления чисел: одна десятичная цифра (0-9) требует 4 бита (тетраду) для хранения; один 8битный байт может представлять две десятичные цифры. 6-битные байты могут хранить только по одной десятичной цифре, два бита остаются незадействованными. По другой версии, 8-битный размер байта связан с 8-битным же числовым представлением символов в кодировке EBCDIC. По третьей версии, из-за двоичной системы кодирования в компьютерах наиболее выгодными для аппаратной реализации и удобными для обработки данных являются длины слов кратные степеням 2, в том числе и 1 Байт = 23 = 8 битов, системы и компьютеры с длинами слов не кратными степеням 2 отпали из-за невыгодности и неудобства. Постепенно 8-битные байты стали стандартом де-факто и с начала 1970-х в большинстве компьютеров байты состоят из 8 бит и размер машинного слова кратен 8 битам. Из соображений удобства единицы нетекстовых типов данных также делают кратными 8 битам, например: • размер одного сэмпла в звуковых файлах равен 8, 16 или 24 битам; • размер пикселя в системе RGB равен 24 битам (по 8 бит на цвет). В таких обозначениях как байт (русское) или B (английское) под байтом (B) подразумевается именно 8 бит, хотя сам термин «байт» не вполне корректен с точки зрения теории. Октет Октет в информатике — 8 двоичных разрядов (8 битов). В русском языке октет обычно называют байтом. Октет имеет 256 возможных состояний (кодов, значений). Во французском языке используются обозначения o, Ko, Mo и т. д. (от слова octet) дабы подчеркнуть, что речь идёт именно о 8 битах. Ниббл Ниббл (англ. nibble, nybble), или полубайт — единица измерения информации, равная четырём двоичным разрядам (битам), удобна тем, что представима одной шестнадцатеричной цифрой, то есть является одним шестнадцатеричным разрядом. Переменная размера «ниббл» может принимать 24=16 различных значений. В русском языке используется синоним «тетрада». Трайт трайт: 1 трайт = 6 трит = 6log33; Понятие информации, количественное определение информации Для количественного сравнения между собой различных источников сообщений, устройств хранения информации, а также различных каналов и систем связи необходимо ввести количественную меру информации, которая дала бы возможность объективно оценить объём информации, содержащийся в сообщении и переносимый сигналом. 5 /30 Рассмотрим понятие информации на примере источника дискретных сообщений, выдающего последовательность элементарных сообщений {ai } , выбранных из алфавита A = (a1, a2, ..., aK ) . Величину K называют объёмом алфавита источника. В каждом отдельном сообщении ai содержится определённая информация как совокупность сведений выдаваемых источником. Определяя конкретную меру этой информации, мы не будем учитывать её смыслового содержания, а также полезность или ценность информации для получателя. Определим информацию как функцию объёма алфавита K . I (ai ) = f (K ) В 1928 г. Хартли предложил в качестве такой функции использовать логарифм: I (ai ) = logm K Основание логарифма m определяет единицу измерения информации. Если m = 2 , то информация будет измеряться в битах. (bit — BInary digiT, слово, предложенное Тьюки). Логарифмическая мера является наиболее удобной по ряду причин. Например, устройство с двумя состояниями может хранить 1 бит информации, а N таких устройств — хранят N бит (свойство аддитивности информации). Число возможных состояний равно 2N и информационная ёмкость равна log2 (2N ) = N . Одним из критериев, определяющих сложность алгоритмов для решения этих задач, является неопределенность сообщений. Чем больше элементов во множестве сообщений, тем больше неопределенность того, какой из них выбран в качестве аргумента поиска, тем больше сравнений требуется произвести для нахождения элемента. Чем больше неопределенность сообщения, тем длиннее требуется последовательность знаков, чтобы указать на выбранное сообщение, то есть закодировать сообщение. Степень неопределённости (неожиданности) сообщения определяется не только объёмом алфавита источника. Например, в любом алфавите языка (русский, английский и т. п.) некоторые буквы встречаются чаще, а некоторые реже. То есть можно утверждать, что количество информации является функцией вероятности символа: I (ai ) = f (P (ai )) В данном случае также выбрана логарифмическая мера, предложенная Шенноном в 1946 г. I (ai ) = − log (P (ai )) Такая мера удовлетворяет интуитивным требованиям: 1. Если выбор источником символа ai заранее предопределён, то его вероятность P (ai ) = 1 и содержащаяся в нём информация I (ai ) = − log (1) = 0 . 2. Чем меньше вероятность появления символа ai , тем более он информативен, то есть при P (ai ) → 0 информативность этого символа I (ai ) → +∞ . До получения конкретного сообщения количество информации характеризуется для получателя некоторой неопределенностью. После получения сообщения неопределенность исчезает, а мы обогащаемся некоторыми сведениями. Это можно трактовать как переход неопределенности в информацию. Следовательно, количество информации является параметром уменьшения неопределенности. Вероятность — это мера возможности случайного события. Случайным называется всякое событие, которое в результате опыта может произойти или не произойти. Вероятность события лежит в пределах от 0 до 1. Если вероятность события равна 0, то его называют невозможным, если 1 — достоверным. Если какие-то события ни при каких условиях не могут произойти одновременно, то их называют несовместными. События называют равновозможными (равновероятными), если нет оснований считать, что одно из них является более возможным (вероятным) чем другое. Полной группой событий называется несколько событий таких, что в результате опыта непременно должно произойти одно из 6 /30 них. Если несколько событий образуют полную группу, несовместны и равновозможны, то они называются случаями. Два способа определения вероятности: 1. (Классическое) Если результаты опыта сводятся к схеме случаев, то вероятность A вычисляется по формуле m P (A) = , n где m — число благоприятных событию A случаев, n — общее число случаев. 2. Статистическое определение вероятности: относительная частота (частость) появления события A ω P * (A) = , W где ω — число появления события A , W — число опытов (выборка). При n → ∞ частость стремится к вероятности: P * (A) → P (A) . Суммой событий называется событие, состоящее в появлении хотя бы одного из них. Если события несовместны, то вероятность их суммы равна сумме вероятностей каждого из событий в отдельности: P (A, B ) = P (A) + P (B ) . Если же события совместны, то надо исключать вероятность их одновременного появления: P (A, B ) = P (A) + P (B ) − P (AB ) . Если события несовместны и образуют полную группу, то сумма их вероятностей равна 1. Произведением событий называется событие, состоящее в совместном появлении всех этих событий. Если события независимы, то есть появление одного из них не изменяет вероятности другого, то вероятность их произведения P (AB ) = P (A) P (B ) . Если же события зависимы, то P (AB ) = P (A) P (B A) = P (B ) P (A B ) . Вероятности P (B A) и P (A B ) называют условными. При анализе последовательности символов источника вероятность этой последовательности будет равна произведению вероятностей, и итоговое количество информации будет равно сумме количества информации в каждом из символов. Появление каждого отдельного символа можно рассматривать как случайное событие, но в теории вероятности для описания источника используют понятие случайной величины (случайного символа). Случайной величиной (СВ) называется величина, которая в результате опыта может принять то или иное значение, заранее неизвестно какое. Случайные величины могут быть как дискретными, если они принимают изолированные друг от друга значения, так и непрерывными, если возможные значения такой величины непрерывны. Соответственно, и источники также называют дискретными или непрерывными. Для дискретных случайных величин X и Y , заданных законами распределения P ( X = X i ) = pi , P (Y = Y j ) = q j и совместным распределением P ( X = X i , Y = Y j ) = pij , количество информации, содержащёйся в X относительно Y , равно p I ( X , Y ) = ∑ pij log 2 ij . pi p j i, j Для непрерывных случайных величин X и Y , заданных плотностями распределения вероятностей p X (t1 ) , pY (t2 ) и p XY (t1 , t2 ) , аналогичная формула имеет вид I ( X , Y ) = ∫∫ p XY (t1 , t2 )log2 ℝ2 7 /30 p XY (t1 , t2 ) dt1dt2 . p X (t1 ) pY (t2 ) Так как 0, при i ≠ j ,  P ( X = X i , X = X j ) =   P ( X = X i ), при i ≠ j. следовательно I ( X , X ) = ∑ pi log2 i pi = −∑ pi log 2 pi . pi pi i То есть энтропия дискретной случайной величины X в теории информации определяется формулой H (X )= I (X , X ). Свойства меры информации и энтропии: 1) I ( X , Y ) ≥ 0, I ( X , Y ) = 0 ⇔ X и Y независимы; 2) I ( X , Y ) = I (Y , X ); 3) H ( X ) = 0 ⇔ X − константа; ∑p 4) I ( X , Y ) = H ( X ) + H (Y ) − H ( X , Y ), где H ( X , Y ) = − ij log2 pij ; i, j 5) I ( X , Y ) ≤ I ( X , X ) = 0. Если I ( X , Y ) = I ( X , X ), то X − функция от Y . При независимости случайных величин X и Y одна из них ничем не описывает другую. Для таких случайных величин I ( X , Y ) = 0 . Пример Даны дискретные случайные величины X 1 , X 2 и Y . Величины X 1 и X 2 — количества очков, выпавших соответственно на 1-й и 2-й игральной кости, а Y = X 1 + X 2 . Найти I (Y , X 1 ) , I ( X 1 , X 1 ) , I (Y , Y ) . Законы распределения вероятностей для дискретных случайных величин X 1 и X 2 совпадают. X 1,i 1 2 3 4 5 6 pi 1 6 1 6 1 6 1 6 1 6 1 6 Закон распределения вероятностей для дискретной случайной величины Y P (Y = i) = P ( X 1 + X 2 = i ), i = 2...12 , вследствие того, что X 1 , X 2 — независимы и поэтому P ( X 1 = n, X 2 = m) = P ( X 1 = n) P ( X 2 = m) , будет pi = P ( X 1 + X 2 = i ) = ∑ n+m=i 1≤n , m≤6 P ( X 1 = n ) P ( X 2 = m) = ∑ n+m=i 1≤n , m≤6 1 . 36 8 /30 Таблицы, определяющие Y : 1 X X 2, j \ 1,i 2 3 4 5 6 1 2 3 4 5 6 7 2 3 4 5 6 7 8 3 4 5 6 7 8 9 4 5 6 7 8 9 10 5 6 7 8 9 10 11 6 7 8 9 10 11 12 Yi = X 1 + X 2 2 3 4 5 6 7 8 9 10 11 12 pi 1 36 2 36 3 36 4 36 5 36 6 36 5 36 4 36 3 36 2 36 1 36 Закон совместного распределения вероятностей дискретных случайных величин X 1 и Y будет pij = P (Y = i, X 1 = j ) = P (Y = i, X 1 = j ) P ( X 1 = j ) , например, P (Y = 2, X 1 = 1) = P (Y = 2 | X 1 = 1) P ( X 1 = 1) = P ( X 2 = 1) P ( X 1 = 1) =  1  , при 1 ≤ i − j ≤ 6, В общем случае получится pij = P (Y = i, X 1 = j ) =   36  иначе.  0, X X 2, j \ 1,i 2 3 4 5 6 7 8 9 10 11 12 1 1 36 1 36 1 36 1 36 1 36 1 36 2 1 36 1 36 1 36 1 36 1 36 1 36 3 1 36 1 36 1 36 1 36 1 36 1 36 4 1 36 1 36 1 36 1 36 1 36 1 36 5 1 36 1 36 1 36 1 36 1 36 1 36 6 1 36 1 36 1 36 1 36 1 36 1 36 Тогда 1 . 36 9 /30 6 I (Y , X 1 ) = ∑ ∑ pij log 2 j =1 1≤i− j≤6 pij pi p j = 6 1 1 log 2 = ∑ ∑ 36 j=1 1≤i− j≤6 6 pi 8 11 12 1  7 1 1 1 1  = ∑ log2 + ∑ log 2 + ... + ∑ log2 + ∑ log2 = 36  i=2 6 pi i=3 6 pi 6 pi i=7 6 pi  i=6  6  1  6 6 6  6 6  log + log + ... + log + ... + log + log + ... + lo g   =   2 2 2 2  2 2  1  36  1 2 6 6 5  1 3 6 = 2 log2 6 + 4 log 2 3 + 6 log 2 2 + 8 log2 + 10 log2 + 6 log 2 1 =  36  2 5 1 = (2 + 2 log 2 3 + 4 log2 3 + 6 + 8 log2 3 − 8 + 10 log 2 3 + 10 − 10 log 2 5) = 36 1 бит = (10 + 24 log2 3 − 10 log 2 5) ≈ 0, 69 . 36 симв. 6 бит I ( X 1 , X 1 ) = I ( X 2 , X 2 ) = −∑ q j log2 q j = log2 6 = 1 + log2 3 ≈ 2, 58 . симв. j =1 = 12 I (Y , Y ) = −∑ pi log2 pi = i=2  1  36 2 log 36 + 4 log 18 + 6 log 12 + 8 log 9 + 10 log + 6 log 6 = 2 2 2 2 2 2   36  5 1 (4+4 log2 3+4+8 log2 3+12+6 log2 3+16 log2 3+20+20 log2 3−10 log2 5+6+6 log2 3) = 36 1 бит = (46 + 60 log 2 3 − 10 log 2 5) ≈ 3, 27 36 симв. Здесь 0 < I (Y , X 1 ) = I (Y , X 2 ) < I ( X 1 , X 1 ) = I ( X 2 , X 2 ) < I (Y , Y ) , что соответствует свойствам = информации. I ( X1, X1 ) 1 2 log 2 6 = в расчёте I ( X 1 , Y ) соответствует информации о двух 36 18 случаях из 36, когда Y = 2 и Y = 12 , которые однозначно определяют X 1 . Шесть случаев, когда Y = 7 , не несут никакой информации об X 1 , что соответствует подчёркнутому члену 6 log 2 1 = 0 . Подчёркнутый член Зависимость между последовательностью выбираемыми символами также уменьшает неопределённость и ведёт к дальнейшему уменьшению энтропии. Действительно, чем больше вероятностные связи между соседними символами сообщения, тем меньше свобода выбора последующего символа, а следовательно, тем меньше информации содержится в среднем в каждом вновь выбираемом символе источника. Обозначим через P ( ai a j ) вероятность того, что источник выберет символ ai , при условии, что ранее он выбрал символ a j . Тогда при фиксированном a j энтропия источника K H (A a j ) = −∑ P (ai a j ) log P (ai a j ) . i =1 Усредняя по всем возможным значениям предшествующего символа a j , получаем K K K H (A A′) = ∑ H (A a j ) P (a j ) = ∑ ∑ P (a j ) P (ai a j ) log P (ai a j ) . j =1 Совместная вероятность i =1 j =1 10 /30 P (ai , a j ) = P (a j ) P (ai a j ) . Тогда энтропия источника с памятью, простирающейся лишь на соседний символ (марковского источника): K K H (A A′ ) = −∑ ∑ P (ai , a j ) log P (ai a j ) . i =1 j =1 Энтропия H (A A′) называется условной. Условная энтропия не может превышать безусловную: H (A A′) ≤ H (A) Типичным примером источника с памятью и неравновероятным выбором символов является текст, написанный на естественном языке. Неравные вероятности символов (букв) и связи между ними обусловлены структурой языка. Так в русском языке вероятность буквы «о» составляет примерно 0,09, а буквы «ф» — лишь 0,002. Наибольшую вероятность имеет символ «пробел» — примерно 0,125. Формула для определения энтропии источника с памятью всё более усложняется по мере дальнейшего учёта вероятностных связей между символами. Однако, энтропию источника можно определить и опытным путём. Согласно многочисленным экспериментальным данным для текста на русском языке энтропия составляет 1,5 бита на букву. Если считать, что русский алфавит содержит 32 бит буквы, то максимальная энтропия H max ( A) = log 2 32 = 5 . симв. Таким образом, средняя информация, содержащаяся в одной букве «абсолютно хаотического 5 ≈ 3,3 раза больше, чем в русском тексте, соответствующем нормальной речи. русского текста» в 1,5 Энтропия источника связана с понятием его избыточности: ρи = 1 − H ( A) . H max ( A) Избыточность представляет собой безразмерную величину, которая может принимать значения от 0 до 1. Избыточность равна 0, если энтропия источника максимальна, то есть выдаваемые источником символы равновероятны и независимы. Такой источник называют источником без избыточности. Смысл избыточности можно пояснить следующим образом. Для передачи или хранения некоторого I объёма информации I от источника с энтропией H (A) требуется n = символов. Если же теперь H (A) каким-то образом полностью устранить избыточность источника, то для передачи этого же объёма I информации потребуется n 0 = символов. Поскольку H ( A) < H max ( A) , то n > n0 . H max (A) Избыточность I ⋅ n0 n ρи = 1 − = 1− 0 . n⋅ I n Избыточность характеризует относительное удлинение сообщения по сравнению с сообщением от 1,5 источника без избыточности (ρ и = 0) . Избыточность источника русского текста ρи = 1 − = 0,7 (70%) . 5 Это означает, что устранив избыточность, можно было бы сократить сообщение в n 1 10 = = ≈ 3,3 раза . n0 1 −ρ и 3 Ещё одной важной характеристикой источника является его производительность. Если скорость выдачи символов источником постоянна и равняется υ и , то его производительность H ′ ( A) = υ и H ( A) . 11 /30 Это выражение определяет среднее количество информации, которое может выдавать (создавать) бит источник в единицу времени. Если H ( A) определяется в битах, то H ′ ( A) имеет размерность . с Источник называется стационарным, если его вероятностные, а следовательно, и информационные характеристики не зависят от времени. Задача Память двоичного стационарного источника с символами 0 и 1 простирается лишь на соседний символ и, следовательно, дискретная последовательность символов, выдаваемых источником, описывается простой цепью Маркова с матрицей переходных вероятностей: P (1 1ˆ) P (1 0ˆ ) P (0 1ˆ) P (0 0ˆ ) ( ) где P ai aɵ j — вероятность символа ai при условии, что ему предшествует символ aɵ j . ( ) ( ) Полагая, что P 11ɵ = 0,9 ; P 10ɵ = 0,7 , найти энтропию источника и его избыточность. Найти энтропию и избыточность двоичного источника без памяти, но с теми же значениями вероятностей передачи символов. Решение: ( ) ( ) Прежде всего, найдем P 01ɵ = 1 − 0,9 = 0,1 ; P 0 0ɵ = 1 − 0,7 = 0,3 и безусловные вероятности передачи символов. ()( ) ( ( )) ( ) ɵ ) , тогда В силу однородности цепи (последовательности символов) P( 0) = P( 0 ɵ P 01ɵ . По формулу полной вероятности P( 0) = P 0ɵ P 0 0ɵ + 1 − P 0 P (0) = P (0) P (0 0ˆ ) + (1 − P (0)) P (0 1ˆ) . Имеем P( 0) = P( 0) ⋅ 0,3 + (1 − P( 0)) ⋅ 0,1 ; 0, 8 ⋅ P (0) = 0,1 ; Отсюда P (0) = 0,125 , P (1) = 0, 875 . Можно убедиться в справедливости соотношения ( ) ( ) P(1) = P( 0) P 10ɵ + (1 − P( 0)) P 11ɵ . Энтропия источника ( ) ( ) H A( Aˆ = −P (0) P (0( 0ˆ ) log2 P (0( 0ˆ ) + P (1( 0ˆ ) log 2 P (1( 0ˆ ) − бит −P (1) P (0(1ˆ )log2 P (0(1ˆ ) + P (1(1ˆ )log 2 P (1(1ˆ ) = 0, 51 симв. ( ) Избыточность источника  и =1 − H ( A Aˆ ) = 0, 49 . H max ( A) Для источника без памяти при тех же безусловных вероятностях передачи символов H ( A) = −P (1)log 2 P (1) − P (0)log2 P (0) = 0, 541 Избыточность источника бит . симв. 12 /30  и =1 − H ( A) = 0, 459 H max ( A) Сущность и цели операции кодирования Под кодированием (в узком смысле или дискретном кодировании) понимается процедура сопоставления дискретному сообщению ai (i = 0, 1, ..., K − 1) определённой последовательности элементов bi = {bk }(i = 0, 1, ..., K − 1; k = 0, 1, ..., m − 1;) . Обычно m < K (например, ai — буквы русского алфавита и K = 32 , а bk — двоичные символы 0 и 1, и m = 2 ). С помощью кодирования решатся следующие задачи: 1. Согласование алфавита источника сообщений с алфавитом канала. 2. «Сжатие» информации (уменьшение или полное устранение избыточности, содержащейся в сообщении). 3. Обнаружение или исправление ошибок, возникающих в канале связи из-за помех и искажений сигнала. Если кодирование решает только первую задачу, код называют примитивным. Вторую задачу решает экономный код. Третью задачу решает помехоустойчивый код. Помехоустойчивые коды также называют корректирующими (они способны обнаруживать и исправлять возникающие в канале ошибки и таким образом повышают верность приёма). Корректирующие коды работают за счёт внесения определённой избыточности в передаваемую кодовую последовательность. При помехоустойчивом кодировании считают, что избыточность источника на входе кодера равна нулю. Это справедливо, во-первых, для многих дискретных источников (например, ЭВМ), обладающих малой избыточностью. А во-вторых, если избыточность первичного источника существенна, она обычно порождается сложными связями, которые в месте приёма затруднительно использовать для повышения верности. Поэтому разумно сначала по возможности уменьшить избыточность первичного источника, применив экономный код, а затем методами помехоустойчивого кодирования внести такую избыточность в сообщение, которая позволит достаточно простыми средствами повысить верность приёма. В современных цифровых информационных системах часто встречаются все три вида кодирования, применяемых последовательно: сначала первичное сообщение представляется в двоичной форме (примитивный код), затем оно сжимается для устранения избыточности (экономный код), затем кодируется помехоустойчивым кодом для повышения верности передачи. Классификация кодов и их представление Основной признак классификации: основание кода m — число различных используемых в коде символов. Наиболее простыми и наиболее распространёнными являются двоичные (бинарные) коды, у которых m = 2 . Коды с m > 2 называют многопозиционными. Различают блочные и непрерывные коды. Блочными называют коды, в которых каждый элемент («символ») сообщения ai преобразуется в определённую последовательность (блок) кодовых символов bi , называемую кодовой комбинацией. Непрерывные коды образуют последовательность кодовых символов bi , в которой невозможно выделить отдельные кодовые комбинации. Коды подразделят также на равномерные и неравномерные. В равномерных кодах все кодовые комбинации содержат одинаковое количество символов (разрядов). В неравномерных кодах число символов (разрядов) в кодовых комбинациях, соответствующих различным исходным символам источника может быть различно. К любому коду обязательно предъявляется требование однозначности декодирования. Это означает, что всякой последовательности или группе последовательностей кодовых символов должна однозначно соответствовать последовательность элементов передаваемого сообщения, то есть потери информации при кодировании и декодировании должны равняться нулю. Если объём алфавита источника сообщений равен K , то каждую букву можно закодировать с помощью n-разрядного m-позиционного кода при условии, что 13 /30 m ≥K . Если имеет место равенство, то есть при кодировании используются все возможные кодовые комбинации, то код называется безызбыточным или примитивным. Если же число возможных кодовых комбинаций больше числа различных символов источника и, следовательно, часть кодовых комбинаций остаётся «неиспользованной», то такой код называют избыточным или корректирующим. Любой код характеризуется коэффициентом избыточности: H ( B) υ H ( B) H ′ ( B) ρк = 1 − = 1− к = 1− , log m υк log m υк log m n где υ к — скорость выдачи символов кодером, H ′ ( B) — производительность кодера. Поскольку при кодировании потери информации отсутствуют, производительность кодера равняется ( ) ( ) ′ ′ производительности источника: H B = H A . Тогда H ′ ( A) υ H ( A) H ( A) ρк = 1 − = 1− и = 1− υ к log m υ к log m n log m где υ и — скорость выдачи символов источником, n = υк — среднее число кодовых символов, υи приходящееся на один символ источника. Для источника без избыточности и равномерного кода log K ρк = 1 − . n log m При кодировании совокупность символов источника сообщений ai удобно представить последовательностью чисел: 0, 1, 2, ..., K − 1 (то есть пронумеровать символы источника). С другой стороны, любое число M можно записать в заданной m-ичной системе счисления следующим образом: M = bn−1m n−1 + bn−2 m n−2 + ... + bk m k + ... + b1m1 + b0 m0 , где коэффициенты bk принимают значения от 0 до m −1 . Такой же принцип применяется и при кодировании символов источника безызбыточным m-разрядным n-позиционным кодом. Число разрядов n , необходимое для представления всех символов источника, зависит от объёма алфавита K этого источника и от основания кода m . Например, при K = 64 любое число, соответствующее символу источника, может быть представлено в десятичной системе счисления двумя разрядами, так как 102 > 64 , в четверичной — тремя (43 = 64) , в двоичной — шестью (26 = 64) . В общем виде минимально необходимое число разрядов можно найти из соотношения m n ≥ K ⇒ n = log m K . Всякий блочный код можно представить в виде таблицы, в которой каждой букве алфавита источника поставлена в соответствие определённая кодовая комбинация. Ниже приведена часть кодовой таблицы для кода ASCII (American Standard Code for Information Interchange) — американский стандартный код для обмена информацией, — который используется для представления в ЭВМ символов (знаков текста). Каждый символ кодируется 8-разрядной комбинацией двоичных чисел. Общее число комбинаций K = 28 = 256 . 14 /30 Символ Номер Код A 65 01000001 Z 90 01011010 А 128 10000000 Я 159 10011111 Помимо таблицы код часто представляют в виде «кодового дерева». Рассмотрим пример построения кодового дерева на примере двоичного кода. Для этого, начиная с определённой точки («корня»), будем проводить отрезки прямой («ветви»), наклонённые влево (если кодовый символ равен 0) или вправо (если кодовый символ равен 1). На рис. 1 приведены примеры кодовых деревьев для различных кодов. Рис. 1. Кодовые деревья двоичных кодов: а) равномерного; б) неравномерного приводимого; в) неравномерного неприводимого На рис. 1 (а) каждой букве источника соответствует своя вершина кодового дерева. С помощью такого дерева можно однозначно декодировать любую последовательность символов, если только она принята с самого начала. Это справедливо для любого равномерного кода. На рис. 1 (б) показано кодовое дерево неравномерного кода. В данном случае символы располагаются не только в вершинах, но и в узлах дерева. Декодирование такого кода будет неоднозначным. Действительно, символ 0 на входе декодера может означать символ «Б», а может оказаться началом кодовых комбинаций, соответствующих символов «Д» и «Е». Такой код называют приводимым. В этом случае для однозначного декодирования необходимо использовать специальные символы-разделители. Примером неравномерного приводимого кода может служить код Морзе. В качестве разделителей в коде Морзе используются длинные паузы между последовательностями точек и тире, представляющими символы (буквы) алфавита. Однако, можно построить неравномерный код таким образом, чтобы однозначное декодирование было возможным без разделителей. Для этого достаточно потребовать, чтобы все буквы располагались только в вершинах кодового дерева, тогда ни одна кодовая комбинация не будет являться началом другой. Пример такого кода показан на рис. 1 (в). Этот код является неприводимым или префиксным. Если последовательность кодовых символов принята сначала, мы сумеем образовать законченную кодовую комбинацию только дойдя до какой-либо вершины. Затем мы возвращаемся к корню дерева и декодируем следующую кодовую комбинацию. Такие коды широко применяются в современных архиваторах. Неприводимость кода является достаточным, но не необходимым условием однозначности декодирования. Теоретически возможно составить коды, не обладающие этим свойством, но допускающие однозначное декодирование без применения дополнительных разделителей при помощи более сложной логики. 15 /30 Свойства кодов без избыточности При использовании n-разрядного равномерного кода условием передачи без потерь информации является выполнение неравенства υ к ≥ nυ и . Среднее число кодовых символов, приходящееся на один символ источника υ n= к . υи Из формулы для избыточности кода: n= H ( A) H ( A) log K ≥ max = . log m log m (1 − ρк )log m Минимально возможное значение n , получаемое при примитивном кодировании достигается при максимально возможной энтропии источника (то есть при отсутствии избыточности источника): log K n min = . log m Таким образом примитивный код обеспечивает предельное согласование источника с каналом лишь при H ( A) = H max ( A) = log K . При наличии помех в канале код без избыточности не может обеспечить сколь угодно высокую верность передачи. На самом деле, пусть канал является симметричным с вероятностью ошибочного приёма одного элемента p . Тогда вероятность правильного приёма одного элемента q = 1 − p , а вероятность правильного приёма n элементов qn = (1 − p) . В примитивном коде каждая кодовая комбинация соответствует одному символу источника. Таким образом, если хотя бы один элемент кодовой комбинации принят ошибочно, на выходе кодера будет зарегистрирована кодовая комбинация, соответствующая другому символу (букве) сообщения. Вероятность этого события n pк = 1 − qn = 1 − (1 − p) . n При p ≪ 1 можно записать pк ≈ np . То есть вероятность ошибки в символах на выходе источника будет в n раз превышать вероятность ошибки в канале. 16 /30 Экономное кодирование Экономное кодирование, называемое также сжатием данных, используется для уменьшения времени передачи информации или объёма памяти, необходимой для её хранения. Суть экономного кодирования заключается в том, что избыточность на выходе кодера уменьшается по сравнению с избыточностью на его входе (избыточностью первичного источника). Экономное кодирование широко используется в компьютерной технике для сжатия данных (архиваторы) и в цифровых системах передачи информации. Минимально возможное среднее количество кодовых символов на один символ источника (предел Шеннона) можно найти из условия ρи = 1 − H ( A) H ( A) = 0 ⇒ nmin = . nmin log m log m Так как примитивный код не может обеспечить эффективное согласование источника с избыточностью с каналом связи, то для канала без помех эффективно согласование для такого источника может быть достигнуто при использовании неравномерного кода, длительность комбинации которого должна соответствовать вероятности выбора источником отдельных символов (букв). Такое кодирование называют статистическим. Неравномерный код при статистическом кодировании выбирается так, чтобы более вероятные символы передавались более короткими кодовыми комбинациями, а менее вероятные — более длинными. В итоге средняя длина кодовой комбинации уменьшается по сравнению с равномерным кодированием. Рассмотрим примеры некоторых часто встречающихся экономных кодов. Код Хаффмана Построение этого кода рассмотрим на конкретном примере источника с объёмом алфавита K = 8 . Символы (буквы) алфавита располагают в порядке убывающей вероятности (рис. 1), затем выбирают пару букв с наименьшими вероятностями (0,02 и 0,03), от них проводят прямые (ветви на кодовом дереве) до узла I — точки условного символа с суммарной вероятностью 0,02 + 0,03 = 0,05 . При этом ветви, проведённой сверху вниз, приписывают символ 1, а ветви, проведённой снизу вверх, — символ 0. Среди символов a1 , a6 и I снова находят пару символов с наименьшими вероятностями (0,08 и 0,05) и от них проводят прямые до точки II — точки условного символа с суммарной вероятностью 0,08 + 0,05 = 0,13 . Этот процесс продолжается дальше, пока построение не замыкается к вершине, то есть формирование кодовой комбинации идёт слева направо. Мы получили кодовое дерево, которое позволяет нам написать кодовые комбинации для всех символов, начиная построение с вершины дерева. Полученный неравномерный код является префиксным. Рис. 1 Пример построения кода Хаффмана Средняя длина n 7 бит кодовой комбинации в нашем примере символ n = ∑ nk pk = 2,6 , k =0 17 /30 в то время как при примитивном кодировании двоичным кодом пришлось бы для всех кодовых комбинаций использовать три символа (разряда). Предел Шеннона при двоичном коде для среднего числа символов на букву nmin = H ( A) = H ( A) . log2 2 В нашем примере энтропия источника (считаем, что отсутствуют вероятностные связи между символами) 8 H ( A) = −∑ pk log2 pk = 2,535 k =1 бит . символ То есть код Хаффмана позволил получить близкое к теоретическому пределу значение средней длины кодового слова. Код Шеннона Фано Закодируем источник из предыдущего примера кодом Шеннона Фано. Процедура сводится к тому, что поэтапно, начиная от вершины, массив символов источника делится на две группы с примерно равными суммарными вероятностями. Символам первой группы приписывается символ 1, символам второй группы приписывается кодовый символ 0. Формирование кодовой комбинации идёт справа налево В нашем примере n = 2,65 , что на много больше, чем для кода Хаффмана. Рис. 2. Пример построения кода Шеннона-Фано Если помимо неравномерного распределения символов первичного источника между ними также присутствует статистическая связь (соседние символы или группы символов зависимы), то рассмотренные коды Хаффмана и Шеннона-Фано окажутся менее эффективными. Так, например, для русского языка избыточность, обусловленная неравновероятностью символов ρвер = 0,13 , а статистической связью — ρсв = 0,73 . В этом случае более эффективным окажется подход, при котором описанными выше методами кодируются не отдельные символы источника, а целые последовательности символов. Такое кодирование называют кодированием с укрупнением алфавита. При глубоких статистических связях длины кодируемых цепочек значительно увеличиваются и возрастает сложность алгоритмов кодирования и декодирования, а также время, затрачиваемое на обработку. Арифметическое кодирование Алгоритм кодирования Хаффмана не может передавать на каждый символ сообщения менее одного бита информации. Схема кодирования, при которой некоторые символы кодируются менее, чем одним битом является арифметическое кодирование. По исходному распределению вероятностей при выбранной для кодирования дискретной случайной величине строится таблица, состоящая из пересекающихся только в граничных точках отрезков для каждого из значений этой дискретной случайной величины.; объединение этих отрезков должно образовывать отрезок [ 0, 1] , а их длины должны быть пропорциональными вероятностям соответствующих значений дискретных случайных величин. Алгоритм кодирования заключается в построении отрезка, однозначно определяющего данную последовательность значений дискретных случайных величин. Затем для построенного отрезка находится число, принадлежащее его внутренней 18 /30 части и равное целому числу, делённому на минимально возможную положительную целую степень двойки. Это число и будет кодом для рассматриваемой последовательности. Все возможные конкретные коды — это числа строго большие нуля и строго меньшие одного, поэтому можно отбрасывать лидирующий ноль и десятичную запятую, но нужен ещё специальный код-маркер, сигнализирующий о конце сообщения. Отрезки строятся так. Если имеется отрезок для сообщения длины n −1 , то для построения отрезка для сообщения длины n , разбиваем его на столько же частей, сколько значений имеет рассматриваемая дискретная случайная величина. Это разбиение делается совершенно также как и самое первое (с сохранением порядка). Затем выбирается из полученных отрезков тот, который соответствует заданной конкретной последовательности длины n . Принципиальное отличие этого кодирования от рассмотренных ранее методов в его непрерывности, то есть в ненужности блокирования. Эффективность арифметического кодирования растёт с ростом длины сжимаемого сообщения (для кодирования Хаффмана и Шеннона-Фано этого не происходит). Недостатком арифметического кодирования является большие требования к вычислительным ресурсам. При сжатии заданных данных, например, из файла все рассмотренные методы требуют двух проходов. Первый для сбора частот символов, используемых как приближённые значения вероятностей символов, и второй для собственно сжатия. Пример арифметического кодирования. Пусть дискретная случайная величина X может принимать 2 1 и соответственно. Сопоставим значению 0 отрезок 3 3   2 2  0,  , а 1 —  ,1 . Тогда для дискретной случайной величины X только два значения 0 и 1 с вероятностями  3   3    2 бит dim ( X ) = 3, H ( X ) = H ( X ) / 3 = log2 3 − ≈ 0, 9183 3 симв. таблица построения кодов —  65 бит M ( L1 ( X )) = ≈ 0, 8025 (арифметическое), 81 симв.  76 бит M ( L1 ( X )) = ≈ 0, 9383 (блочный Хаффмана), 81 симв.  бит ( ( M L1 X )) = M ( L ( X )) = 1 (Хаффмана). симв. Среднее количество бит на единицу сообщения для арифметического кодирования получилось меньше, чем энтропия. Это связано с тем, что в рассмотренной простейшей схеме кодирования, не 19 /30 описан код-маркер конца сообщения, введение которого неминуемо сделает это среднее количество бит большим энтропии. Получение исходного сообщения из его арифметического происходит по следующему алгоритму. Шаг 1. В таблице для кодирования значений дискретной случайной величины определяется интервал, содержащий текущий код, — по этому интервалу однозначно определяется один символ исходного сообщения. Если этот символ — маркер конца сообщения, то конец. Шаг 2. Из текущего кода вычитается нижняя граница содержащего его интервала. Полученное число считывается новым текущим значением кода. Переход к шагу 1. Подстановочные или словарно-ориентированные алгоритмы сжатия информации. Методы Лемпела-Зива Методы Шеннона-Фано, Хаффмана и арифметического кодирования называют статистическими. Далее рассматриваются словарные алгоритмы, которые носят менее математически обоснованный, но более практичный характер. Алгоритм LZ77 Алгоритм LZ77 был опубликован в 1977 г. Разработан израильскими математиками Якобом Зивом и Авраамом Лемпелом. Основная идея LZ77 состоит в том, что второе и последующие вхождения некоторой строки символов в сообщении заменяются ссылками на её первое вхождение. Алгоритм LZ77 использует уже просмотренную часть сообщения как словарь. Чтобы добиться сжатия, он пытается заменить очередной фрагмент сообщения на указатель в содержимое словаря. Алгоритм LZ77 использует «скользящее» по сообщению окно, разделённое на две неравные части. Первая, большая по размеру, включает уже просмотренную часть сообщения. Вторая, намного меньшая, является буфером, содержащим ещё незакодированные символы входного потока. Обычно размер окна составляет несколько килобайт, а размер буфера — не более 100 байт. Алгоритм пытается найти в словаре (большей части окна) фрагмент, совпадающий с содержимым буфера. Алгоритм LZ77 выдаёт коды, состоящие из трёх элементов: – смещение в словаре относительно его начала подстроки, совпадающей с началом содержимого буфера; – длина этой подстроки; – первый символ буфера, следующий за подстрокой. Пример. Размер окна — 20 символов, словаря — 12 символов, а буфера — 8. Кодируется сообщение «ПРОГРАММНЫЕ ПРОДУКТЫ ФИРМЫ MICROSOFT». Пусть словарь уже заполнен. Тогда он содержит строку «ПРОГРАММНЫЕ », а буфер — строку «ПРОДУКТЫ». Просматривая словарь, алгоритм обнаружит, что совпадающей подстрокой будет «ПРО», в словаре она расположена со смещением 0 и имеет длину 3 символа, а следующим символом в буфере является «Д». Таким образом, выходным кодом будет тройка 0, 3, 'Д ' . После этого алгоритм сдвигает влево всё содержимое окна на длину совпадающей подстроки +1 и одновременно считывает столько же символов из входного потока в буфер. Получаем в словаре строку «РАММНЫЕ ПРОД», в буфере — «УКТЫ ФИР». В данной ситуации совпадающей подстроки обнаружить не удаться и алгоритм выдаст код 0, 0, ' У ' , после чего сдвинет окно влево на один символ. Затем словарь будет содержать «АММНЫЕ ПРОДУ», а буфер «КТЫ ФИРМ». И т. д. Декодирование кодов LZ77 проще их получения, так как не нужно осуществлять поиск в словаре. Недостатки LZ77: 1) с ростом размеров словаря скорость работы алгоритма –кодера пропорционально замедляется; 2) кодирование одиночных символов очень неэффективно. Пример. Закодировать по алгоритму LZ77 строку «КРАСНАЯ КРАСКА». СЛОВАРЬ(8) БУФЕР(5) КОД 20 /30 «........» «КРАСН» <0,0‘K’> «.......К» «РАСНА» <0,0‘Р’> «......КР» «АСНАЯ» <0,0‘А’> «.....КРА» «СНАЯ » <0,0‘С’> «....КРАС» «НАЯ К» <0,0‘Н’> «...КРАСН» «АЯ КР» <5,1‘Я’> «.КРАСНАЯ» « КРАС» <0,0‘ ’> «КРАСНАЯ » «КРАСК» <0,4‘K’> «АЯ КРАСК» «А....» <0,0‘А’> В последней строчке, буква «А» берётся не из словаря, так как она последняя. Длина кода вычисляется следующим образом: длина подстроки не может быть больше размера буфера, а смещение не может быть больше размера словаря –1. Следовательно, длина двоичного кода смещения будет округлённым в большую сторону log2 (размер словаря ) , а длина двоичного кода дл длины подстроки будет округлённым в большую сторону log2 (размер буфера + 1) . А символ кодируется 8 битами (например ASCII+) В последнем примере длина полученного кода равна 9 ⋅ (3 + 3 + 8) = 126 бит , против 112 бит исходной длины строки. Алгоритм LZSS В 1982 году Сторером (Storer) и Шиманским (Szimanski) на базе LZ77 был разработан алгоритм LZSS. Код, выдаваемый алгоритмом LZSS, начинается с однобитового префикса, различающего собственно код от незакодированного символа. Код состоит из пары: смещение и длина, такими же как и для LZ77. В LZSS окно сдвигается ровно на длину найденной подстроки или на 1, если не найдено вхождение подстроки из буфера в словарь. Длина подстроки в LZSS всегда больше нуля, поэтому длина двоичного кода для длины подстроки — это округлённый до большего целого двоичный логарифм от длины буфера. Пример. Закодировать по алгоритму LZSS строку «КРАСНАЯ КРАСКА». СЛОВАРЬ(8) БУФЕР(5) КОД ДЛИНА КОДА «........» «КРАСН» 0‘K’ 9 «.......К» «РАСНА» 0‘Р’ 9 «......КР» «АСНАЯ» 0‘А’ 9 «.....КРА» «СНАЯ » 0‘С’ 9 «....КРАС» «НАЯ К» 0‘Н’ 9 «...КРАСН» «АЯ КР» 1<5,1> 7 «..КРАСНА» «Я КРА» 0‘Я’ 9 «.КРАСНАЯ» « КРАС» 0‘ ’ 9 «КРАСНАЯ » «КРАСК» 1<0,4> 7 «НАЯ КРАС» «КА...» 1<4,1> 7 «АЯ КРАСК» «А....» 1<0,1> 7 Здесь длина полученного кода равна 7 ⋅ 9 + 4 ⋅ 7 = 91 бит. LS77 и LZSS обладают следующими очевидными недостатками: 21 /30 1) невозможность кодирования подстрок, отстоящих друг от друга на расстоянии, большем длины словаря; 2) длина подстроки, которую можно закодировать, ограничена размером буфера. Если механически чрезмерно увеличивать размеры словаря и буфера, то это приведёт к снижению эффективности кодирования, так как с ростом этих величин будут расти и длины кодов для смещения и длины, что сделает коды для коротких подстрок недопустимо большими. Кроме того, резко увеличится время работы алгоритма-кодера. Алгоритм LZ78 В 1978 году авторами LZ77 был разработан алгоритм LZ78, лишённый названных недостатков. Алгоритм LZ78 не использует «скользящее» окно, он хранит словарь из уже просмотренных фраз. При старте алгоритма этот словарь содержит только одну пустую строку (строку длины нуль). Алгоритм считывает символы сообщения до тех пор, пока накапливаемая подстрока входит целиком в одну из фраз словаря. Как только эта строка перестанет соответствовать хотя бы одной фразе словаря, алгоритм генерирует код, состоящий из индекса строки в словаре, которая до последнего введённого символа содержала входную строку, и символа, нарушившего совпадение. Затем в словарь добавляется введённая подстрока. Если словарь уже заполнен, то из него предварительно удаляют менее всех используемую в сравнениях фразу. Ключевым для размера получаемых кодов является размер словаря во фразах, потому что каждый ко при кодировании по методу LZ78 содержит номер фразы в словаре. Из последнего следует, что эти коды имеют постоянную длину, равную округлённому в большую сторону двоичному логарифму размера словаря +8 (это количество бит в байт-коде расширенного ASCII). 22 /30 Пример. Закодировать по алгоритму LZ78 строку «КРАСНАЯ КРАСКА», используя словарь длиной 16 фраз. ВХОДНАЯ ФРАЗА (В СЛОВАРЬ) КОД «» ПОЗИЦИЯ СЛОВАРЯ «К» <0‘K’> 1 «Р» <0‘Р’> 2 «А» <0‘А’> 3 «С» <0‘С’> 4 «Н» <0‘Н’> 5 «АЯ» <3‘Я’> 6 « » <0‘ ’> 7 «КР» <1‘Р’> 8 «АС» <3‘С’> 9 «КА» <1‘А’> 10 Указатель на любую фразу такого словаря — это число от 0 до 15, для его кодирования достаточно четырёх бит. В последнем примере длина полученного кода равна 10 ⋅ (4 + 8) = 120 битам. Алгоритм Лемпела-Зива для двоичных символов В технике экономного кодирования более типичной является ситуация, когда о некотором избыточном источнике известен лишь его алфавит, но не известна его статистика (распределение вероятностей последовательностей символов). Так, например, может стоять задача разработки некоторого универсального сжимающего двоичного префиксного кода для передачи текста на различных языках, заданных каждый своим алфавитом, или для сжатия данных различного рода. Основная идея этого алгоритма заключается в том, что последовательность символов источника разбивается на максимально короткие различимые цепочки, которые не встречались раньше, а затем эти цепочки кодируются равномерным кодом. Например, если источник выдаёт двоичную последовательность из 18 символов: 101100110001111000, то она будет разбита на такие цепочки: 1, 0, 11, 00, 110, 001, 111, 000. При таком разбиении все префиксы конкретной цепочки могут находиться лишь слева, и две цепочки с одинаковым префиксом всегда отличаются в последнем символе (бите). В каждой цепочке кодируется её префикс равномерным двоичным кодом и один бит используется для кодирования последнего (справа) символа цепочки. Если C ( n) означает число различных цепочек разбиения для данной последовательности из n символов (в нашем примере C (n) = 8 ), то требуется log 2 C (n) бит, чтобы закодировать номер префикса к данной цепочке (в нашем примере 3 бита) и ещё один бит для описания последнего элемента этой цепочки. Для приведённой выше цепочки и её разбиения получаем следующий равномерный код: (000, 1) , (000, 0) , (001, 1) , (010, 0) , (011, 0) , (100, 1) , (011,1) , (100, 0) . Декодирование такого кода однозначное. В нашем примере кодовые комбинации содержат 32 символа (4 × 8) вместо исходных 18 символов, то есть получилось растяжение вместо сжатия. Однако для длинных последовательностей сообщений эффективность алгоритма растёт, и при n → ∞ сжатие сообщений приближается к своему пределу, поскольку доказано, что для любого стационарного источника сообщений при использовании двоичного кода Зива-Лемпела среднее число кодовых символов на один символ источника стремится к величине энтропии. Алгоритм LZW В 1984 году Уэлчем (Welch) был создан алгоритм LZW путём модификации LZ78. Пошаговое описание алгоритма-кодера. 23 /30 Шаг 1. Инициализация словаря всеми возможными односимвольными фразами (обычно 256 символами расширенного ASCII). Инициализация входной фразы w первым символом сообщения. Шаг 2. Считать очередной символ K из кодируемого сообщения. Шаг 3. Если КОНЕЦ_СООБЩЕНИЯ Выдать код для w Конец Если фраза wK уже есть в словаре Присвоить входной фразе значение wK Перейти к Шагу 2 Иначе Выдать код w Добавить wK в словарь Присвоить входной фразе значение K Перейти к Шагу 2 Как и в случае с LZ78 для LZW ключевым для размера получаемых кодов является размер словаря во фразах: LZW-коды имеют постоянную длину, равную округлённую в большую сторону двоичному логарифму размера словаря. Пример. Закодировать по алгоритму LZ78 строку «КРАСНАЯ КРАСКА». Размер словаря — 500 фраз. ВХОДНАЯ ФРАЗА, wK (В СЛОВАРЬ) КОД для w ПОЗИЦИЯ СЛОВАРЯ ASCII+ 0-255 «КР» 0‘K’ 256 «РА» 0‘Р’ 257 «АС» 0‘А’ 258 «СН» 0‘С’ 259 «НА» 0‘Н’ 260 «АЯ» 0‘А’ 261 «Я » 0‘Я’ 262 « К» 0‘ ’ 263 «КРА» <256> 264 «АСК» <258> 265 «КА» 0‘К’ 266 «А» 0‘А’ В этом примере длина полученного кода равна 12 ⋅ 9 = 108 битам . При переполнении словаря, то есть когда необходимо внести новую фразу в полностью заполненный словарь, из него удаляют либо наиболее редко используемую фразу, либо все фразы, отличающиеся от одиночного символа. Для LZ78 возможна и полна очистка словаря. Эффективность кодирования источника (сжатия данных) оценивается через его избыточность следующим соотношением: ηи = 1 −ρ и . Для русского языка кодирования ηи ≈ 0,25 . ρи ≈ 0,75 и, следовательно, максимальная эффективность экономного 24 /30 Корректирующие коды и их свойства Корректирующими свойствами обладают только избыточные коды, для которых справедливо неравенство mn > K , где m — число позиций, n — число разрядов кода (длина кодовой комбинации), K — объём алфавита источника. Идея обнаружения ошибок в принятой кодовой комбинации b′k состоит в том, что для передачи информации от источника используются не все N = m n возможных кодовых комбинаций, а лишь некоторая часть из них: K < mn = N . Эти K используемых комбинаций называются разрешёнными, а оставшиеся N − K комбинаций — запрещёнными. Если в результате воздействия помех передаваемая разрешённая комбинация превращается в одну из запрещённых, то тем самым и обнаруживается факт ошибки (или ошибок). Если же совокупность ошибок окажется такой, что переданная разрешённая комбинация превратится в одну из других разрешённых, то такие ошибки не будут обнаружены. Как только ошибка обнаружена, по обратному каналу на передающую сторону оправляется запрос на повторную передачу комбинации, в которой обнаружена ошибка. Если же обратный канал в системе не предусмотрен, то информация просто теряется. Как следствие, в системах без обратного канала используют коды, которые позволяют не только обнаружить, но и исправить ошибку. В системах с исправлением ошибок принятые кодовые комбинации декодируются в соответствии с выбранным алгоритмом. Рассмотрим простую геометрическую интерпретацию декодирования с исправлением ошибок. Всё множество возможных кодовых комбинаций N разбивается на K непересекающихся подмножеств, приписываемых отдельным решениям (то есть отдельным символам источника). Разбиение выполняется так, чтобы при декодировании запрещённых комбинаций восстановить ту из разрешённых, которая могла быть передана с наибольшей вероятностью. Если кодовую комбинацию длиной n рассматривать как вектор в n-мерном пространстве, то это будет та из разрешённых комбинаций, которая находится ближе всего к принятой запрещённой: bˆ = arg min b′ − b , j i i где bˆ j — решение декодера о переданной комбинации, b′ — принятая комбинация, bi — все возможные разрешённые кодовые комбинации, ⋅ — норма (длина) разностного вектора (расстояние). В двоичном случае (m = 2) пространство двоичных векторов длиной n называют пространством Хемминга. Длина вектора в пространстве Хемминга равна числу единиц в этом векторе, а расстояние между двумя векторами равно числу разрядов, в которых эти вектора различаются: b = ∑b 2 l ∑b ; = l l b′ − b = l ∑ (b′ ⊕ b ) 2 l l l = ∑ (b′ ⊕ b ). l l l Обычно система работает или в режиме обнаружения, или в режиме исправления ошибок, однако, возможны и системы, в которых некоторые запрещённые комбинации (например, близкие по расстоянию к разрешённой) сначала декодируются, а другие (например те, для которых отличие по расстоянию велико) перезапрашиваются. Исправляющая и обнаруживающая способности кодов Для корректирующих кодов с исправлением и обнаружением ошибок вводится понятие обнаруживающей и исправляющей способности кода. Количество ошибок в кодовой комбинации, которое позволяет обнаружить данный код, называется обнаруживающей способностью кода. Исправляющей способностью называется количество ошибок, 25 /30 которое может исправить данный код. Обнаруживающая и исправляющая способности кодов определяются величиной кодового расстояния. Кодовым расстоянием d min называется минимальное расстояние между двумя разрешёнными комбинациями данного кода. Блочный код с кодовым расстоянием d min может гарантированно обнаружить qо = d min −1 ошибок. Действительно, поскольку между двумя разрешёнными кодовыми комбинациями расстояние не меньше d min , то любая комбинация с числом ошибок меньше d min попадает в число запрещённых, что позволяет обнаружить ошибку. Поскольку в принципе из-за большого числа ошибок передаваемая кодовая комбинация может превратиться в запрещённую, расстояние до которой будет больше d min и, кроме того, расстояние между некоторыми кодовыми комбинациями также могут быть больше d min , код может обнаружить и большее число ошибок. Однако, вероятности появления таких ошибок пренебрежимо малы и поэтому они обычно не учитываются. Аналогичным образом, можно сказать, что исправляющая способность кода с заданным d min qи < d min , 2 d min окажутся внутри области разбиения 2 соответствующей переданной комбинации и, следовательно, будут исправлены. Для нечётных d min исправляющая способность d −1 qи = min , 2 а для чётных d qи = min −1 . 2 В симметричном двоичном канале вероятность ошибки кратности q в комбинации длины n поскольку все комбинации с числом ошибок меньше n−q pq = Cnq p0q (1 − p0 ) , где p0 — вероятность ошибки в элементе, быстро убывает с ростом q . Как следствие, обычно достаточно малую вероятность ошибки декодирования позволяют получить коды с исправляющей способностью qи порядка 1...3 ошибок. Виды корректирующих кодов Основная теорема кодирования Шеннона говорит о том, что сколь угодно малой вероятности ошибки можно достичь, используя кодовые комбинации большой длины. Однако, с ростом n существенно возрастает сложность декодирования по описанному выше алгоритму минимума расстояния. Поэтому большой интерес представляют избыточные коды и методы кодирования, не требующие перебора всех возможных кодовых комбинаций, но вместе с тем позволяющие получить малую вероятность ошибки декодирования. Такие избыточные коды найдены, а наибольшее распространение среди них получили линейные коды. Линейным двоичным кодом длины n называется такой код, для которого сумма (по модулю два) любых двух разрешённых комбинаций данного кода также является разрешённой комбинацией данного кода. Среди разрешённых комбинаций линейного кода обязательно должна присутствовать комбинация, состоящая из всех нулей, чтобы сумма по модулю два любой разрешённой комбинации с самой собой также давала разрешённую («нулевую») комбинацию. Если первые k символов кодовой комбинации длины n являются информационными, а остальные r = n − k — неинформационными (избыточными или проверочными), то такой код будет называться систематическим. 26 /30 Линейные коды можно сформировать следующим образом. К k информационным символам кодовых комбинаций, соответствующих K = m k сообщениям, прибавляются r проверочных символов, которые являются линейными комбинациями информационных. Для линейного двоичного кода расстояние d min определяется минимальным весом (числом единиц) по всем кодовым комбинациям (кроме нулевой). Действительно, расстояние по Хеммингу между двумя кодовыми комбинациями равно числу единиц в сумме этих комбинаций по модулю 2. Но для линейного кода сама эта сумма также является разрешённой комбинацией. Линейные блочные систематические коды обычно обозначают как (n, k ) . Избыточность линейного двоичного кода можно определить формулой log 2 2k k r = 1− = . n n n Величина r r R = 1 −ρ к = 1 − = n n называется скоростью кода. Свобода выбора проверочных символов позволяет при заданных n и k построить большое число различных кодов. Естественно, код стараются построить так, чтобы он был в некотором смысле оптимальным. В теории передачи информации оптимальным считается код, который при той же длине n и избыточности обеспечивает минимум вероятности ошибки декодирования. Коды, вся избыточность которых расходуется на исправление ошибок заданной кратности, называются совершенными. ρк = 1 − Примеры линейных блочных двоичных систематических кодов 1. Код с одной проверкой на чётность (n, n −1) К k = n −1 информационным разрядам добавляется один проверочный. Общее число комбинаций N N равно N = 2n , из них K = 2 n−1 = — разрешённые, а остальные N − K = — запрещённые. 2 2 Проверочный символ получается из k информационных сложением разрядов по модулю 2: k −1 bn−1 = ∑ bl . l =0 Из формулы видно, что проверочный разряд равен нулю, если среди информационных символов чётное число единиц, и единице — если число единиц нечётное. Таким образом, в кодовой комбинации число единиц всегда чётное. Следовательно, если в канале произойдёт одна ошибка, то число единиц станет нечётным. Комбинации, содержащие нечётное число единиц, являются запрещёнными, их ровно половина. Появление на приёме запрещённой комбинации — признак ошибки. Если в канале произойдут одновременно две ошибки в одной кодовой комбинации, число единиц останется чётным, и такая ситуация окажется незамеченной декодером, так же, как и появление 4, 6, 8 и т. д. (то есть чётного числа) ошибок. Ошибки же нечётной кратности (1, 3, 5 и т. д.) будут обнаружены. Вероятность того, что ошибка в кодовой комбинации не будет обнаружена, равна сумме вероятностей того, что произойдёт чётное число ошибок: pно = p2 + p4 + ... . Кодовое расстояние кода с одной проверкой на чётность d min = 2 , то есть этот код гарантированно обнаруживает 1 ошибку (а также все ошибки нечётной кратности), но не может исправлять ошибки. 2. Коды Хемминга Коды Хемминга получаются по следующему правилу: n = 2 r − 1 , где n — общее число разрядов, r — число проверочных разрядов и n − r — число информационных разрядов. Кодовое расстояние кодов Хемминга d min = 3 . Коды Хемминга являются совершенными: они исправляют одну и только одну ошибку. Рассмотрим подробно случай r = 3 — код Хемминга (7, 4) . 27 /30 Три проверочных разряда получаются из информационных таким образом, чтобы соблюдалось условие их линейной независимости. Например: b4 = b0 ⊕ b1 ⊕ b2 , b5 = b1 ⊕ b2 ⊕ b3 , b6 = b0 ⊕ b2 ⊕ b3 . Таким образом, каждый из 7 символов участвует хотя бы в одной проверке (символ b2 участвует в трёх проверках). Эти равенства используются как проверочные при приёме кодовой комбинации. Если в одном из разрядов содержится ошибка, то те равенства, в которых он участвует, не соблюдаются. Так как равенств три, то возможны 8 вариантов ситуаций. В ситуации, когда все равенства выполняются, кодовая комбинация или принята безошибочно, или в канале произошли ошибки, приведшие к новой разрешённой кодовой комбинации, то есть ошибка в кодовой комбинации не обнаружена. В другом случае, в зависимости от того, какая из оставшихся семи ситуаций имеет место в конкретном опыте, декодер определяет, какой из семи элементов принят неверно. Например, если не выполняются все три проверки, то это указывает на b2 , а если не выполняется только одна проверка, например, b4 , то это указывает на то, что произошла ошибка в самом проверочном символе, в данном случае это b4 . Таким образом, одиночные ошибки не только обнаруживаются, но и могут быть исправлены путём замены ошибочного элемента на противоположный. Двойные ошибки обнаруживаются, но не исправляются. Код Хемминга может использоваться в двух режимах: режиме исправления или режиме обнаружения ошибок. В режиме исправления ошибок исправляются все одиночные ошибки в кодовой комбинации, следовательно, вероятность остаточной ошибки при декодировании равна вероятности того, что в кодовой комбинации произойдёт более одной ошибки: 7 pк = ∑ Ci7 p i (1 − p) 7−i . i=2 Для малых p pк ≈ C27 p 2 (1 − p) ≈ C27 p 2 = 21 p 2 . 5 В режиме обнаружения ошибок гарантированно обнаруживаются две ошибки, то есть вероятность необнаруженной ошибки определяется как вероятность того, что в принятой кодовой комбинации будет более двух ошибочных элементов: 7 pно = ∑ Ci7 p i (1 − p) . 7−i i=3 Для малых p pно ≈ C73 p 3 (1 − p) ≈ C73 p 3 = 35 p 3 . 4 Векторно-матричное представление кодов Символы исходного сообщения и кодового слова можно соответствующих векторов. Обозначим информационный вектор как рассматривать как элементы a = (a0 a1 ... ak−1 ) , а кодовый вектор как b = (b0 b1 ... bn−1 ) Для линейных блоковых кодов операцию кодирования можно представить совокупностью линейных уравнений вида bi = a0 ,i g 0,i + a1,i g1,i + ... + ak−1,i g k−1,i , i = 0, 1, ..., n − 1 . 28 /30 принимают значения 0 или 1. Эти линейные уравнения можно В двоичном случае коэффициенты gi , j переписать в векторно-матричной форме: b = aG Матрица G называется порождающей матрицей кода:  g 0   g 0 ,0 g 0,1 ... g 0 ,n−1       g1   g1 , 0 g1,1 ... g1,n−1  . = G =     ... ... ... ... ...      g  g  k−1   k−1,0 g k−1,1 ... g k−1,n−1  Таким образом, произвольное слово представляет собой линейную комбинацию векторов g i — строк матрицы G : b = a0g 0 + a1g1 + ... + ak−1g k−1 . Векторы g i должны выбираться таким образом, чтобы соблюдалось условие их линейной независимости. Такие векторы называются базисом (n, k ) кода. Совокупность базисных векторов не единственная и, следовательно, матрица G не уникальна. Любую порождающую матрицу (n, k ) кода путём проведения операций над строками и перестановкой столбцов можно свести к систематической форме:  1 0 ... 0   p0,0 p0,1 ... p0,r−1       0 1 ... 0   p1,0 p1,1 ... p1,r−1  . = G = [ I : P ] =     ... ... ... ... ... ... ... ...       0 0 ... 1   p    k−1,0 pk−1,1 ... pk−1,r−1  Здесь I — единичная матрица, P — матрица, которая определяет r проверочных символов. Такую форму записи проверочной матрицы называют канонической. После умножения информационного вектора на порождающую матрицу в канонической форме, получается кодовый вектор, в котором первые k элементов — информационные, а последние — проверочные. Любой несистематический линейный ( n, k ) код, эквивалентен ( n, k ) блочный несистематической порождающей матрицы, систематической порождающей матрицей. полученный коду с с помощью соответствующей С любым линейным (n, k ) кодом связан дуальный код (n, n − k ) . Дуальный код является линейным кодом с 2 n−k кодовыми векторами, которые образуют нуль-пространство по отношению к (n, k ) коду. Порождающая матрица H дуального кода состоит из (n − k ) линейно независимых векторов, выбираемых в нуль-пространстве. То есть любое кодовое слово (n, k ) кода ортогонально любому кодовому слову дуального (n, n − k ) кода. Следовательно, любое кодовое слово (n, k ) кода ортогонально любой строке матрицы H : bH T = 0 . Поскольку это равенство справедливо для любого кодового слова, то GHT = 0 . Если линейный (n, k ) код является систематическим, то из этого равенства следует, что H = [−PT : I ] . Для двоичных кодов знак «–» может быть опущен, так как операции сложения и вычитания по модулю 2 идентичны. Матрица H используется при декодировании (n, k ) кода в качестве проверочной. Если выполняется условие b′HT = 0 , значит, принятый кодовый вектор является разрешённым и ошибок нет. Принятый вектор b′ = b + e , где b — переданный вектор, e — вектор ошибки. Произведение b′HT = (b + e) H T = bHT + eHT = eHT = c . 29 /30 Вектор c называется вектором синдрома. Число элементов вектора c равняется числу проверочных символов. Отличие синдрома от нуля всегда указывает на наличие ошибки. Кроме того, в режиме исправления по виду синдрома можно определить вектор ошибки и, следовательно, исправить ошибки в принятой кодовой комбинации. При декодировании все возможные варианты синдрома сводятся в таблицу синдромов. Пример таблицы синдромов: Синдром Номер ошибочного разряда 001 4 010 5 011 3 … … Синдром c является характеристикой вектора ошибок, а не переданного кодового вектора. Хотя в принципе возможно 2 n вариантов ошибок, из них лишь 2 n−k = 2r будут синдромными. Следовательно, разные ошибки могут приводить к одинаковым синдромам. Полиномиальное представление кодов, циклические коды Кодовое слово также можно представить в виде полинома степени ≤ n −1 : B ( p) = bn−1 p n−1 + bn−2 p n−2 + ... + b1 p + b0 Для двоичного кода каждый из коэффициентов полинома bi равен или 0, или 1. Определим также полином информационного слова A( p) = ak−1 p k−1 + ak−2 p k −2 + ... + a1 p + a0 и порождающий полином G ( p) = p n−k + g n−k−1 p n−k−1 + ... + g1 p + 1 . Тогда операция кодирования будет иметь вид B ( p) = A( p) G ( p) . Поскольку степень информационного полинома не выше k −1 , а порождающего — не выше n − k , степень их произведения будет не выше n −1 — максимальной степени кодового слова. Циклическими называют коды, для которых циклический сдвиг разрешённой кодовой комбинации также является разрешённой кодовой комбинацией: bi = [bn−1 bn−2 ... b1 b0 ] → b j = [bn−2 bn−3 ... b0 bn−1 ] . В полиномиальной форме циклический сдвиг записывается как: pB ( p) = bn−1 p n + bn−2 p n−1 + ... + b1 p 2 + b0 p ; pB ( p) B ( p) ; = bn−1 + 1n n p −1 p +1 B1 ( p) = bn−2 p n−1 + bn−3 p n−2 + ... + b0 p + bn−1 . То есть циклически сдвинутая на одну позицию комбинация получается как остаток от деления pB ( p ) на полином p n +1 : B1 ( p) = pB ( p) mod ( p n + 1) . Аналогично, сдвиг на i позиций можно записать как Bi ( p) = p i B ( p) mod ( p n +1) . 30 /30 В общем виде можно записать p B ( p) = Q ( p)( p n + 1) + Bi ( p) . i Здесь Bi ( p) — кодовое слово циклического сдвига, Q ( p) — частное. Порождающий полином циклического кода G ( p) получается как один из множителей при факторизации полинома p n +1 : p n + 1 = G ( p ) H ( p) . Полином H ( p) будет с одной стороны являться проверочным для циклического (n, k ) кода, а с другой стороны — порождающим для дуального (n, n − k ) кода. Из порождающего полинома (n, k ) кода можно получить порождающую матрицу. Порождающая матрица должна состоять из любого набора k линейно независимых векторов. По заданному порождающему полиному G ( p) такой набор генерируется циклическим сдвигом этого полинома: p k−1G ( p) , p k−2G ( p) , ..., pG ( p) , G ( p) . Проверочная матрица получается аналогичным образом из соответствующего проверочного полинома. Декодирование циклических кодов Принимаемый кодовый вектор в полиномиальной форме B ′ ( p ) = B ( p ) + E ( p ) = A( p ) G ( p ) + E ( p ) . Здесь E ( p ) — полиномиальная запись вектора ошибки. Разделим B ′ ( p) на порождающий полином: B ′ ( p) E ( p) R ( p) = A( p ) + = Q ( p) + . G ( p) G ( p) G ( p) Здесь R ( p) — остаток от деления B ′ ( p) на G ( p) , представляющий собой полином степени не выше n − k −1 , Q ( p) — частное. Поскольку первое (полезное) слагаемое B ′ ( p) делится на G ( p) без остатка, остаток от деления R ( p) будет определяться только вектором ошибки E ( p ) . Если C ( p) = R ( p) = 0 , то есть принятый полином делится на порождающий без остатка, то ошибок нет. Вместо деления на порождающий полином можно умножать принятый вектор на проверочный полином H ( p) . Примером циклического кода является код Хемминга (7, 4) . Свёрточные коды Свёрточные коды не являются блочными и не являются систематическими. Свёрточный кодер представляет собой сдвиговый регистр с отводами 31 /30 1 2 Число ячеек сдвигового регистра K = v +1 . Величину v называют кодовым ограничением свёрточного кодера. Кодовое ограничение определяет память свёрточного кодера. Рис. 1. Пример построения свёрточного кода со скоростью R = Конфигурация отводов кодера определяется коэффициентами порождающих полиномов G1 , G2 , ... . Для кодера, изображённого на рисунке, порождающие полиномы равны соответственно: G1 ( p) = p 2 + 1 , G2 ( p) = p 2 + p + 1 . В векторной форме записи: g1 = [101] , g 2 = [111] . Порождающие полиномы свёрточного кода принято записывать в восьмеричной форме: G1 = 5 , G2 = 7 . Реакция свёрточного кодера на изолированную единицу (последовательность вида 100000... ) называется импульсной характеристикой (ИХ) кодера. Число единиц («вес») ИХ определяет свободное расстояние свёрточного кода d св . Свободное расстояние является эквивалентом кодового расстояния d min для блочных кодов, оно позволяет оценить исправляющую способность свёрточного кода: d qи < св . 2 Считается, что свёрточный декодер исправляет не более qи ошибок на интервале удвоенного кодового ограничения n = 2v . Вероятность ошибки декодирования для свёрточного кода можно оценить через вероятность того, что в выбранном наугад отрезке декодируемой последовательности длиной n = 2v произойдёт qи +1 ошибок: 2 v−qи +1 pк = C2qиv+1 p qи +1 (1 − p) .