Как определить избыточность кода
Перейти к содержимому

Как определить избыточность кода

  • автор:

Кодирование информации и избыточность кода

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

В большинстве случаев используемые системы кодирования обладают избыточностью, то есть требуют для записи большее количество информации, чем оно содержится в кодируемом сообщении. Избыточность определяется формулой \[E = 1 — \frac\] где \(H\) — энтропия сообщения, \(Q\)- среднее количество информации, приходящееся на один символ кодированного сообщения.

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

Величина \(H /Q\) называется экономичностью кода. Для оптимального кода \(H /Q=1\) а избыточность отсутствует, то есть \(E = 0\).

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

Пример: определить энтропию информации, содержащейся в сообщении «ученье − свет, а не ученье – тьма» и избыточность кода. Каждый символ в сообщении кодируется 1 байтом (8 бит).
Решение: Подсчитаем количество символов в сообщении, для простоты игнорируя пробелы: N=26. Найдём частоту повторения каждого символа (вероятность в сообщении), составив следующую таблицу, приведенную на скрине слева.

Удельная энтропия (энтропия одного символа в сообщении) в битах на символ, равна \[\tilde H = 5 \cdot \frac><\log _2>13 + \frac><\log _2>\frac> + 2 \cdot \frac><\log _2>\frac> + 4 \cdot \frac><\log _2>26 \approx \] \[ \approx \frac> \cdot 3.7004 + \frac> \cdot 2.1155 + \frac> \cdot 3.1155 + \frac> \cdot 4.7004 \approx 3.3535\] Полная энтропия сообщения \(H = 3.3535 \cdot 26 = 87.19\) бит. Количество бит, необходимое для кодирования каждого символа одним байтом, составляет \(Q = 208\;\) бит.
Избыточность кода \(E=1-87.19/208=0.58=58%\).

Корректирующие коды. Начало новой теории кодирования

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

Введение

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

Вся математическая классика ориентирована, как правило, на бесконечный теоретический случай, а специальные дисциплины опираются на случай конечных конструкций и математических структур. Отличие подходов колоссальное, отсутствие или недостаток хороших полных примеров — пожалуй главный минус и недостаток вузовских учебников. Очень редко существует задачник с решениями для начинающих (для первокурсников), а те, что имеются, грешат пропусками в объяснениях. В общем я полюбил букинистические магазины технической книги, благодаря чему пополнилась библиотека и в определенной мере багаж знаний. Читать довелось много, очень много, но «не заходило».

Этот путь привел меня к вопросу, а что я уже могу самостоятельно делать без книжных «костылей», имея перед собой только чистый лист бумаги и карандаш с ластиком? Оказалось совсем немного и не совсем то, что было нужно. Пройден был сложный путь бессистемного самообразования. Вопрос был такой. Могу ли я построить и объяснить, прежде всего себе, работу кода, обнаруживающего и исправляющего ошибки, например, код Хемминга, (7, 4)-код?

Известно, что код Хемминга широко используется во многих прикладных программах в области хранения и обмена данными, особенно в RAID; кроме того, в памяти типа ECC и позволяет «на лету» исправлять однократные и обнаруживать двукратные ошибки.

Информационная безопасность. Коды, шифры, стегосообщения

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

Защита информации в информационных телекоммуникационных системах (ИТКС) становится практически основной проблемой при решении задач управления, как в масштабе отдельной личности – пользователя, так и для фирм, объединений, ведомств и государства в целом. Из всех аспектов защиты ИТКС в этой статье будем рассматривать защиту информации при ее добывании, обработке, хранении и передаче в системах связи.

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

Рисунок А – Схема основных направлений и взаимосвязи теорий, направленных на решение задач защиты информационного взаимодействия

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

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

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

В общем «поехали». По определению, а их довольно много, понять что есть код очень даже не просто. Авторы пишут, что код — это алгоритм, отображение и ещё что-то. О классификации кодов я не буду здесь писать, скажу только, что (7, 4)-код блоковый.

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

Поскольку роль сторон переменчива оба этих устройства объединяют в одно и называют сокращенно кодек (кодер/декодер), и устанавливают на обоих концах канала. Дальше, раз есть слова, есть и алфавит. Алфавит — это два символа , в технике массово используются блоковые двоичные коды. Алфавит естественного языка (ЕЯ) — множество символов — букв, заменяющих при письме звуки устной речи. Здесь не будем углубляться в иероглифическую письменность в слоговое или узелковое письмо.

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

Ричард Хемминг, наверное, раньше других понял, что если избыточность не устранять, а разумно организовать, то ее можно использовать в системах связи для обнаружения ошибок и автоматического их исправления в кодовых словах передаваемого текста. Он понял, что все 128 семиразрядных двоичных слов могут использоваться для обнаружения ошибок в кодовых словах, которые образуют код — подмножество из 16 семиразрядных двоичных слов. Это была гениальная догадка.

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

Построение (7, 4)-кода Хемминга

Вернемся к Хеммингу. Слова (7, 4)-кода образованы из 7 разрядов С j = , j = 0(1)15, 4-информационные и 3-проверочные символа, т.е. по существу избыточные, так как они не несут информации сообщения. Эти три проверочных разряда удалось представить линейными функциями 4-х информационных символов в каждом слове, что и обеспечило обнаружение факта ошибки и ее места в словах, чтобы внести исправление. А (7, 4)-код получил новое прилагательное и стал линейным блоковым двоичным.

Линейные функциональные зависимости (правила (*)) вычислений значений символов
имеют следующий вид:

Исправление ошибки стало очень простой операцией — в ошибочном разряде определялся символ (ноль или единица) и заменялся другим противоположным 0 на 1 или 1 на 0.
Сколько же различных слов образуют код? Ответ на этот вопрос для (7, 4)-кода получается очень просто. Раз имеется лишь 4 информационных разряда, а их разнообразие при заполнении символами имеет = 16 вариантов, то других возможностей просто нет, т. е. код состоящий всего из 16 слов, обеспечивает представление этими 16-ю словами всю письменность всего языка.

Информационные части этих 16 слов получают нумерованный вид №
():

0=0000; 4= 0100; 8=1000; 12=1100;
1=0001; 5= 0101; 9=1001; 13=1101;
2=0010; 6= 0110; 10=1010; 14=1110;
3=0011; 7= 0111; 11=1011; 15=1111.

Каждому из этих 4-разрядных слов необходимо вычислить и добавить справа по 3 проверочных разряда, которые вычисляются по правилам (*). Например, для информационного слова №6 равного 0110 имеем и вычисления проверочных символов дают для этого слова такой результат:

Шестое кодовое слово при этом приобретает вид: Таким же образом необходимо вычислить проверочные символы для всех 16-и кодовых слов. Подготовим для слов кода 16-строчную таблицу К и последовательно будем заполнять ее клетки (читателю рекомендую проделать это с карандашом в руках).

Таблица К – кодовые слова Сj, j = 0(1)15, (7, 4) – кода Хемминга

Описание таблицы: 16 строк — кодовые слова; 10 колонок: порядковый номер, десятичное представление кодового слова, 4 информационных символа, 3 проверочных символа, W-вес кодового слова равен числу ненулевых разрядов (≠ 0). Заливкой выделены 4 кодовых слова-строки — это базис векторного подпространства. Собственно, на этом все — код построен.

Таким образом, в таблице получены все слова (7, 4) — кода Хемминга. Как видите это было не очень сложно. Далее речь пойдет о том, какие идеи привели Хемминга к такому построению кода. Мы все знакомы с кодом Морзе, с флотским семафорным алфавитом и др. системами построенными на разных эвристических принципах, но здесь в (7, 4)-коде используются впервые строгие математические принципы и методы. Рассказ будет как раз о них.

Математические основы кода. Высшая алгебра

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

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

Создатели кодов, долго не могли додуматься до кода, обнаруживающего и исправляющего две ошибки. Идеи, использованные Хеммингом, там не срабатывали. Пришлось искать, и нашлись новые идеи. Очень интересно! Захватывает. Для поиска новых идей потребовалось около 10 лет и только после этого произошел прорыв. Коды, обнаруживающие произвольное число ошибок, были получены сравнительно быстро.

Векторные пространства, поля и группы. Полученный (7, 4)-код (Таблица К) представляет множество кодовых слов, являющихся элементами векторного подпространства (порядка 16, с размерностью 4), т.е. частью векторного пространства размерности 7 с порядком Из 128 слов в код включены лишь 16, но они попали в состав кода не просто так.

Во-первых, они являются подпространством со всеми вытекающими отсюда свойствами и особенностями, во-вторых, кодовые слова являются подгруппой большой группы порядка 128, даже более того, аддитивной подгруппой конечного расширенного поля Галуа GF() степени расширения n = 7 и характеристики 2. Эта большая подгруппа раскладывается в смежные классы по меньшей подгруппе, что хорошо иллюстрируется следующей таблицей Г. Таблица разделена на две части: верхняя и нижняя, но читать следует как одну длинную. Каждый смежный класс (строка таблицы) — элемент факторгруппы по эквивалентности составляющих.

Таблица Г – Разложение аддитивной группы поля Галуа GF () в смежные классы (строки таблицы Г) по подгруппе 16 порядка.

Столбцы таблицы – это сферы радиуса 1. Левый столбец (повторяется) – синдром слова (7, 4)-кода Хемминга, следующий столбец — лидеры смежного класса. Раскроем двоичное представление одного из элементов (25-го выделен заливкой) факторгруппы и его десятичное представление:

Техника получение строк таблицы Г. Элемент из столбца лидеров класса суммируется с каждым элементом из заголовка столбца таблицы Г (суммирование выполняется для строки лидера в двоичном виде по mod2). Поскольку все лидеры классов имеют вес W=1, то все суммы отличаются от слова в заголовке столбца только в одной позиции (одной и той же для всей строки, но разных для столбца). Таблица Г имеет замечательную геометрическую интерпретацию. Все 16 кодовых слов представляются центрами сфер в 7-мерном векторном пространстве. Все слова в столбце от верхнего слова отличаются в одной позиции, т. е. лежат на поверхности сферы с радиусом r =1.

В этой интерпретации скрывается идея обнаружения одной ошибки в любом кодовом слове. Работа идет со сферами. Первое условие обнаружения ошибки — сферы радиуса 1 не должны касаться или пересекаться. Это означает, что центры сфер удалены друг от друга на расстояние 3 или более. При этом сферы не только не пересекаются, но и не касаются одна другой. Это требование для однозначности решения: какой сфере отнести полученное на приемной стороне декодером ошибочное (не кодовое одно из 128 -16 = 112) слово.

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

Здесь возникает требование к словам кода и к коду в целом: расстояние между любыми двумя кодовыми словами должно быть не менее трех, т. е. разность для пары кодовых слов, например, Сi = 85==1010101; Сj = 25== 0011001 должна быть не менее 3; 85 — 25 = 1010101 — 0011001 =1001100 = 76, вес слова-разности W(76) = 3. (табл. Д заменяет вычисления разностей и сумм). Здесь под расстоянием между двоичными словами-векторами понимается количество не совпадающих позиций в двух словах. Это расстояние Хемминга, которое стало повсеместно использоваться в теории, и на практике, так как удовлетворяет всем аксиомам расстояния.

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

Таблица Д — Сумма элементов группы (кодовых слов), используемой для построения кода Хемминга

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

Применение кода. Кодер

Кодер размещается на передающей стороне канала и им пользуется отправитель сообщения. Отправитель сообщения (автор) формирует сообщение в алфавите естественного языка и представляет его в цифровом виде. (Имя символа в ASCII-соде и в двоичном виде).
Тексты удобно формировать в файлах для ПК с использованием стандартной клавиатуры (ASCII — кодов). Каждому символу (букве алфавита) соответствует в этой кодировке октет бит (восемь разрядов). Для (7, 4)- кода Хемминга, в словах которого только 4 информационных символа, при кодировании символа клавиатуры на букву требуется два кодовых слова, т.е. октет буквы разбивается на два информационных слова естественного языка (ЕЯ) вида
.

Пример 1. Необходимо передать слово «цифра» в ЕЯ. Входим в таблицу ASCII-кодов, буквам соответствуют: ц –11110110, и –11101000, ф – 11110100, р – 11110000, а – 11100000 октеты. Или иначе в ASCII — кодах слово «цифра» = 1111 0110 1110 1000 1111 0100 1111 0000 1110 0000

с разбивкой на тетрады (по 4 разряда). Таким образом, кодирование слова «цифра» ЕЯ требует 10 кодовых слов (7, 4)-кода Хемминга. Тетрады представляют информационные разряды слов сообщения. Эти информационные слова (тетрады) преобразуются в слова кода (по 7 разрядов) перед отправкой в канал сети связи. Выполняется это путем векторно-матричного умножения: информационного слова на порождающую матрицу. Плата за удобства получается весьма дорого и длинно, но все работает автоматически и главное — сообщение защищается от ошибок.
Порождающая матрица (7, 4)-кода Хемминга или генератор слов кода получается выписыванием базисных векторов кода и объединением их в матрицу. Это следует из теоремы линейной алгебры: любой вектор пространства (подпространства) является линейной комбинацией базисных векторов, т.е. линейно независимых в этом пространстве. Это как раз и требуется — порождать любые векторы (7-разрядные кодовые слова) из информационных 4-разрядных.

Порождающая матрица (7, 4, 3)-кода Хемминга или генератор слов кода имеет вид:

Справа указаны десятичные представления кодовых слов Базиса подпространства и их порядковые номера в таблице К
№ i строки матрицы — это слова кода, являющиеся базисом векторного подпространства.

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

Информационные слова сообщения имеют вид:

Это половины символа (ц). Для (7, 4)-кода, определенного ранее, требуется найти кодовые слова, соответствующее информационному слову-сообщению (ц) из 8-и символов в виде:

Чтобы превратить эту букву–сообщение (ц) в кодовые слова u, каждую половинку буквы-сообщения i умножают на порождающую матрицу G[k, n] кода (матрица для таблицы К):

Получили два кодовых слова с порядковыми номерами 15 и 6.

Покажем детальное формирование нижнего результата №6 – кодового слова (умножение строки информационного слова на столбцы порождающей матрицы); суммирование по (mod2)

∙ = 0∙1 +1∙0 + 1∙0 + 0∙0 = 0(mod2);
∙ = 0∙0 +1∙1 + 1∙0 + 0∙0 = 1(mod2);
∙ = 0∙0 +1∙0 + 1∙1 + 0∙0 = 1(mod2);
∙ = 0∙0 +1∙0 + 1∙0 + 0∙1 = 0(mod2);
∙ = 0∙0 +1∙1 + 1∙1 + 0∙1 = 0(mod2);
∙ = 0∙1 +1∙0 + 1∙1 + 0∙1 = 1(mod2);
∙ = 0∙1 +1∙1 + 1∙0 + 0∙1 = 1(mod2).

Получили в результате перемножения пятнадцатое и шестое слова из таблицы К. Первые четыре разряда в этих кодовых словах (результатах умножения) представляют информационные слова. Они имеют вид: , (в таблице ASCII это только половины буквы ц). Для кодирующей матрицы выбраны в качестве базисных векторов в таблице К совокупности слов с номерами: 1, 2, 4, 8. В таблице они выделены заливкой. Тогда для этой таблицы К кодирующая матрица получит вид G[k,n].

В результате перемножения получили 15 и 6 слова таблицы К кода.

Применение кода. Декодер

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

Основной задачей декодера является проверка того, является ли полученное слово (7 разрядов) тем, которое было отправлено на передающей стороне, не содержит ли слово ошибок. Для решения этой задачи для каждого полученного слова декодером путем умножения его на проверочную матрицу Н[n-k, n] вычисляется короткий вектор-синдром S (3 разряда).

Для слов, которые являются кодовыми, т. е. не содержат ошибок, синдром всегда принимает нулевое значение S =. Для слова с ошибкой синдром не нулевой S ≠ 0. Значение синдрома позволяет обнаружить и локализовать положение ошибки с точностью до разряда в принятом на приемной стороне слове, и декодер может изменить значение этого разряда. В проверочной матрице кода декодер находит столбец, совпадающий со значением синдрома, и порядковый номер этого столбца принимает равным искаженному ошибкой разряду. После этого для двоичных кодов декодером выполняется изменение этого разряда – просто замена на противоположное значение, т. е. единицу заменяют нулем, а нуль – единицей.

Рассматриваемый код является систематическим, т. е. символы информационного слова размещаются подряд в старших разрядах кодового слова. Восстановление информационных слов выполняется простым отбрасыванием младших (проверочных) разрядов, число которых известно. Далее используется таблица ASCII-кодов в обратном порядке: входом являются информационные двоичные последовательности, а выходом – буквы алфавита естественного языка. Итак, (7, 4)-код систематический, групповой, линейный, блочный, двоичный.

Основу декодера образует проверочная матрица Н[n-k, n], которая содержит число строк, равное числу проверочных символов, а столбцами все возможные, кроме нулевого, столбцы из трех символов . Проверочная матрица строится из слов таблицы К, они выбираются так, чтобы быть ортогональными к кодирующей матрице, т.е. их произведение — нулевая матрица. Проверочная матрица получает следующий вид в операциях умножения она транспонируется. Для конкретного примера проверочная матрица Н[n-k, n] приведена ниже:

Видим, что произведение порождающей матрицы на проверочную в результате дает нулевую матрицу.

Пример 2. Декодирование слова кода Хемминга без ошибки (е =).
Пусть на приемном конце канала приняты слова №7→60 и №13→105 из таблицы К,
u + е = + ,
где ошибка отсутствует, т. е. имеет вид е = .

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

Пример 3. Обнаружение одной ошибки в слове, полученном на приемном конце канала (таблица К).

А) Пусть требуется передать 7 – е кодовое слово, т.е.

u = и в одном третьем слева разряде слова, допущена ошибка. Тогда она суммируется по mod2 с 7-м передаваемым по каналу связи кодовым словом
u + е = + = ,
где ошибка имеет вид е = .

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

Выполним такое умножение для наших исходных (7-го вектора с ошибкой) данных.

В результате такого умножения на приемном конце канала получили вектор-синдром S, размерность которого (n–k). Если синдром S= нулевой, то делается вывод о том, что принятое на приемной стороне слово принадлежит коду С и передано без искажений. Если синдром не равен нулю S ≠ , то его значение указывает на наличие ошибки и ее место в слове. Искаженный разряд соответствует номеру позиции столбца матрицы Н[n-k, n], совпадающего с синдромом. После этого искаженный разряд исправляется, и полученное слово обрабатывается декодером далее. На практике для каждого принятого слова сразу вычисляется синдром и при наличии ошибки, она автоматически устраняется.

Итак, при вычислениях получен синдром S= для обоих слов одинаковый. Смотрим на проверочную матрицу и отыскиваем в ней столбец, совпадающий с синдромом. Это третий слева столбец. Следовательно, ошибка допущена в третьем слева разряде, что совпадает с условиями примера. Этот третий разряд изменяется на противоположное значение и мы вернули принятые декодером слова к виду кодовых. Ошибка обнаружена и исправлена.

Вот собственно и все, именно так устроен и работает классический (7, 4)-код Хемминга.

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

Заключение

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

Задача защиты информационного взаимодействия субъектов и объектов от ошибок среды и от воздействий нарушителя относится к кодологии.

Рассмотрен в деталях (7, 4)-код Хемминга, положивший начало нового направлению в теории кодирования — синтеза корректирующих кодов.

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

Литература

Питерсон У., Уэлдон Э. Коды, исправляющие ошибки: Пер. с англ. М.: Мир, 1976, 594 c.
Блейхут Р. Теория и практика кодов, контролирующих ошибки. Пер.с англ. М.: Мир, 1986, 576 с.

Кодирование сообщений, коды Фано, Шеннона и Хаффмана

Условие ФАНО

Под
кодированием
понимают
преобразование
алфавита источника сообщений A=, ( i = 1,2…,K ) в
алфавит некоторых кодовых символов R=, (j =
1,2,…,N ).
Обычно размер алфавита кодовых символов |R|
существенно меньше размера алфавита источника |A|.
Последовательность кодовых символов, описывающих
сообщение источника, называется кодовым словом.
19.03.2019
2

3.

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

4.

5.

Кодирование сообщений может преследовать различные цели.
Одна из них — представить сообщение в такой системе символов, которая обеспечивала бы
простоту и надежность аппаратной реализации устройств и их эффективность.
Другая цель кодирования — обеспечить наилучшее согласование свойств источника
сообщений со свойствами канала связи. При этом добиваются выигрыша во времени
передачи
Еще одной целью кодирования является засекречивание передаваемой информации. При
этом элементарным сообщениям
ak1 ak2…akn
из алфавита A ставятся в соответствие последовательности, к примеру, цифр или букв из
специальных кодовых таблиц, известных лишь отправителю и получателю информации.
Примером кодирования может служить преобразование дискретных сообщений ak1 ak2…akn
из одних систем счисления в другие.
Кодирование в канале, или помехоустойчивое кодирование информации, используется для
уменьшения количества ошибок, возникающих при передаче по каналу с помехами.
19.03.2019
5

6.

По условиям построения кодовых слов коды делятся на
равномерные и неравномерные. Если кодовые слова имеют разную
длину, то код называется неравномерным. Типичным представителем
этой группы является код Морзе.
В равномерных кодах все сообщения передаются кодовыми словами
с одинаковым числом элементов. Примером является телеграфный код
с длиной кодового слова равной 5.
По размеру алфавита кодовых символов различают следующие виды
кодов: единичные, двоичные, многопозиционные.
Наибольшее распространение получили двоичные коды, или коды с
основанием 2, для которых размер алфавита кодовых символов
R= равен двум
19.03.2019
6

7.

Самым простым способом задания кодов являются кодовые таблицы, ставящие в
соответствие сообщениям ai соответствующие им коды
Буква ai Число ai
А
Б
В
Г
Д
Е
Ж
З
19.03.2019
0
1
2
3
4
5
6
7
Код с основанием 10
0
1
2
3
4
5
6
7
Код с основанием 2
000
001
010
011
100
101
110
111
7

8.

Другим наглядным способом описания кодов является их
представление в виде кодового дерева
19.03.2019
8

9.

Для того, чтобы построить кодовое дерево для данного кода, начиная с некоторой
точки — корня кодового дерева — проводятся ветви — 0 или 1. На вершинах кодового
дерева находятся буквы алфавита источника, причем каждой букве соответствуют
свой лист и свой путь от корня к листу. К примеру, букве А соответствует код 000,
букве В – 010, букве Е – 101 и т.д.
Код, полученный с использованием кодового дерева, изображенного на рис. 1,
является равномерным трехразрядным кодом.
Равномерные коды очень широко используются в силу своей простоты и
удобства процедур кодирования-декодирования: каждой букве – одинаковое число
бит; при получении заданного числа бит – в кодовой таблице ищется
соответствующая буква
19.03.2019
9

10.

Если исходный алфавит содержит K символов, то для построения равномерного
кода с использованием N кодовых символов необходимо обеспечить выполнение
следующего условия:
K ≤ Nq ,
или
log K
q
,
log N
где q – количество элементов кодовой последовательности.
Например, при двоичном кодировании 32-х букв русского алфавита
используется q = log2 32 = 5 разрядов, на чем и основывается телетайпный код.
19.03.2019
10

11.

Очевидно, что при различной вероятности появления букв исходного
алфавита равномерный код является избыточным, так как энтропия,
характеризующая информационную емкость сообщения максимальна при
равновероятных буквах исходного текста.
Например, для телетайпного кода Н0 = 5 бит, а с учетом
неравномерности появления различных букв исходного алфавита Н 4,35
бит. Устранение избыточности достигается применением неравномерных
кодов, в которых буквы, имеющие наибольшую вероятность, кодируются
наиболее короткими кодовыми последовательностями, а более длинные
комбинации присваиваются редким буквам.
19.03.2019
11

12.

Если i-я буква, вероятность которой Рi, получает кодовую
комбинацию длины qi, то средняя длина комбинации
K
qср Pq
i i
i 1
Считая кодовые буквы равномерными, определяем наибольшую
энтропию закодированного алфавита как qср log K, которая не
может быть меньше энтропии исходного алфавита Н, т.е.
qср log K Н.
Отсюда имеем
qср (Н / log K).
Обычно К=2 и qср Н !!
19.03.2019
12

13.

Чем ближе значение qср к энтропии Н, тем более эффективно
кодирование. В идеальном случае, когда qср Н, код называют
эффективным.
Эффективное кодирование устраняет избыточность,
приводит к сокращению длины сообщений, а значит,
позволяет уменьшить время передачи сообщений или объем
памяти, необходимой для их хранения.
19.03.2019
13

14.

При построении неравномерных кодов необходимо обеспечить
возможность их однозначной расшифровки. В равномерных кодах такая
проблема не возникает, т.к. при расшифровке достаточно кодовую
последовательность разделить на группы, каждая из которых состоит из q
элементов. В неравномерных кодах можно использовать разделительный
символ между буквами алфавита (так поступают, например, при передаче
сообщений с помощью азбуки Морзе).
Если же отказаться от разделительных символов, то следует
запретить такие кодовые комбинации, начальные части которых уже
использованы в качестве самостоятельной комбинации. Например, если
101 означает код какой-то буквы, то нельзя использовать комбинации 1, 10
или 10101
19.03.2019
14

15.

Для построения неравномерных кодов, допускающих однозначное декодирование
необходимо, чтобы всем буквам алфавита соответствовали лишь листья кодового дерева
(Рисунок). Здесь ни одна кодовая комбинация не является началом другой, более длинной,
поэтому неоднозначности декодирования не будет. Такие неравномерные коды
называются префиксными.
0
1
0
1
А
Б
0
1
В
1
Г
19.03.2019
0
Д
15

16.

Прием и декодирование неравномерных кодов — процедура гораздо более сложная, чем для
равномерных. Возникает вопрос, зачем же используются неравномерные коды?
Рассмотрим пример кодирования сообщений ai из алфавита объемом K = 8 с помощью
произвольного q-разрядного двоичного кода.
Пусть источник сообщений выдает некоторый текст с алфавитом от А до З и одинаковой вероятностью букв
Р(ai) = 1/8.
Кодирующее устройство кодирует эти буквы равномерным трехразрядным кодом (см. таблицу).
Определим основные информационные характеристики источника с таким алфавитом:
— энтропия источника
K
H 0 log K 3
H Pi log Pi
i 1
H0 H

0
H0
— избыточность источника
K
— среднее число символов в коде
— избыточность кода
19.03.2019
rk
qср H
qср
8
1
qср qi Pi 3 3
8
i 1
i 1
0
.
16

17.

Таким образом, при кодировании сообщений с равновероятными буквами
избыточность выбранного (равномерного) кода оказалась равной нулю.
Пусть теперь вероятности появления в тексте различных букв будут разными :
Буква
А
Б
В
Г
Д
Е
Ж
З
вероятность
0.6 0.2
0.1
0.04
0.025
0.015
0.01
0.01
K
H Pi log Pi
H =1,781
i 1
Среднее число символов на одно сообщение при использовании того же равномерного
трехразрядного кода,
K
8
1
qср qi Pi 3 3
8
i 1
i 1
а избыточность rk
qср H
qср
1.781
1
0.41
3
или довольно значительной величиной — в среднем 4 символа из 10 не несут никакой
информации .
19.03.2019
17

18.

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

19.

Первый метод (Метод Р. Фано). Алгоритм сводится к последовательному
выполнению следующих ПЯТИ шагов:
1. Буквы алфавита А упорядочиваем по убыванию вероятностей:
Р(a1) ≥ Р(a2) ≥…≥ Р(aK).
2. Множество упорядоченных букв разбивается на два подмножества А(0), А(1) с
помощью некоторого порогового целого числа 1 ≤ k(1) ≤ K -1 так, чтобы величина
J (1)
k (1)
K
P (a )
i 1
i
P (ai )
i k (1) 1
достигала наименьшего возможного значения.
Буквам из подмножества А(0) приписываем 0, буквам подмножества А(1)
приписываем 1.
19.03.2019
19

20.

3. Если подгруппы А(0), А(1) состоят более чем из двух букв, то разбиваем множество букв
каждой из подгрупп на две подгруппы А(00), А(01) и А(10), А(11), соответственно, с помощью
пороговых целых чисел ,
1 ≤ k(11) ≤ k(1) -1,
k(1) ≤ k(12) ≤ K -1
J (21)
k (11)
k1
P(a )
i 1
P (ai )
i
i k (11) 1
так, чтобы величины
J
(22)
k (12)
i k (1) 1
P (ai )
K
P (ai )
i k (12) 1
достигали наименьших возможных значений. Буквам из подгрупп А(00), А(10) с нулевыми
последними индексами приписываем 0, буквам из подгрупп А(10), А(11) приписываем 1.
Если подгруппа А(ij) i,j = 0,1 состоит более чем из одной буквы, то переходим к шагу 4. Если
все подгруппы состоят из одной буквы, то переходим к шагу 5.
19.03.2019
20

21.

4.
Если есть подгруппы, состоящие более чем из одной буквы, то разбиваем
каждую из них на две подгруппы, исходя из соотношения, введенного на шаге 2.
Буквам подгрупп с нулевыми последними индексами приписываем нуль, буквам
подгрупп с единичными последними индексами приписываем единицу.
Если все образовавшиеся подгруппы состоят из одной буквы, то переходим к
шагу 5. Если есть подгруппы, состоящие более чем из одной буквы, то повторяем
шаг 4.
5. Если образовавшиеся подгруппы состоят из одной буквы, то
последовательно, начиная с первой метки, выписываем нули и единицы,
относящиеся к каждой букве алфавита А.
В итоге получается двоичный префиксный код для заданного источника.
19.03.2019
21

22.

Рассмотрим следующий пример:
Буква
a1
a2
a3
a4
a5
a6
Р(ai)
0.36
0.18
0.18
0.12
0.09
0.07
I
А(0)
А(1)
II
0
0
1
1
1
1
А(00)
А(01)
А(10)
А(11)
III
0
1
0
1
1
1
А(110)
А(111)
IV
0
1
1
А(1110)
А(1111)
0
1
Kод
00
01
10
110
1110
1111
qi Pi
0.72
0.36
0.36
0.36
0.36
0.28
Средняя длина для построенного кода qср = 2,44. Соответствующее кодовое дерево
имеет вид:
19.03.2019
22

23.

19.03.2019
23

24.

Полученный код называют еще префиксным множеством.
В нашем случае это множество следующее:
S = .
19.03.2019
24

25.

ОПЕРАЦИЯ УСЕЧЕНИЯ
Рассмотрим кодовое дерево, максимальный порядок концевых вершин
которого равен n. Предположим, что вершине а n-го порядка предшествует
вершина b (n-l)-гo порядка, из которой выходит единственное ребро, ведущее
в а. Других рёбер из вершины b не выходит. Операцию удаления этого ребра
и превращения промежуточной вершины b (n-l)-гo порядка в концевую
вершину будем называть операцией усечения. Средняя кодовая длина после
операции усечения становится меньше. Пример, приведен ниже.
19.03.2019
25

26.

Вектор КРАФТА
Если S = – префиксное множество, то можно определить некоторый
вектор v(S) = (q1, q2, . , qK), состоящий из чисел, являющихся длинами соответствующих
префиксных последовательностей т.е. qi – это длина wi.
Вектор (q1, q2, . , qk), состоящий из неуменьшающихся положительных целых
чисел, удовлетворяющих неравенству Крафта
q1 q 2 . q K 1
2
2
2
,
называется вектором Крафта.
Для него справедливо следующее утверждение: если S – какое-либо префиксное
множество, то v(S) – вектор Крафта.
Иными словами, длины двоичных последовательностей в префиксном множестве
удовлетворяют неравенству Крафта.
19.03.2019
26

27.

Для него справедливо следующее утверждение: если S –
какое-либо префиксное множество, то v(S) – вектор Крафта.
Иными словами, длины двоичных последовательностей в
префиксном
множестве
удовлетворяют
неравенству
Крафта.
Неравенство Крафта формулируется в виде следующей
теоремы:
Теорема. Пусть q1, q2, . , qK набор положительных целых
чисел. Для того чтобы существовал префиксный код с
длинами кодовых слов q1, q2, . , qK, необходимо и достаточно,
чтобы выполнялось неравенство
q1 q 2 . q K 1
2
2
2
19.03.2019
27

28.

Теорема не утверждает, что любой код с длинами кодовых слов,
удовлетворяющими неравенству Крафта, является префиксным. Например,
множество двоичных кодовых слов удовлетворяет неравенству, но не
обладает свойством префикса
Примеры простейших префиксных множеств и соответствующие им векторы
Крафта:
S1 = и v(S1) = ( 1, 2, 2 );
S2 = и v(S2) = ( 1, 2, 3, 3 );
S3 = и v(S3) = ( 1, 2, 3, 4, 4 );
S4 = и v(S4) = ( 1, 2, 4, 4, 4, 4 );
19.03.2019
28

29.

Второй метод построения двоичных префиксных кодов
(Метод К. Шеннона).
1. Буквы алфавита А упорядочиваем по убыванию
вероятностей:
Р(a1) ≥ Р(a2) ≥…≥ Р(aK).
2. Находим числа qi, i=1, …, K, исходя из условия:
1
1
P (ai ) qi 1
qi
2
2
3. Подсчитываем накопленные суммы:
K
P1 =0, Р2 = P(a1), Р3 = P(a1) + P(a2), .
Pn P (ai )
i 1
19.03.2019
29

30.

4. Находим первые после запятой qi знаков в разложении числа Рi в двоичную
дробь: i=1, …, K. Цифры этого разложения, стоящие после запятой, являются
кодовым словом, соответствующим букве ai.
5. Если необходимо, производим операцию усечения.
Для сравнения методов рассмотрим тот же самый источник сообщений и
проделаем последовательно шаги алгоритма:
19.03.2019
30

31.

Буква
a1
a2
a3
a4
a5
a6
19.03.2019
1
Р(ai)
0.36
0.18
0.18
0.12
0.09
0.07
2
qi
2
3
3
4
4
4
3
Накопленная Pi
0,00
0,36 = 0,01011…
0,54 = 0, 10001…
0,72 = 0,10111…
0,84 = 0,11010…
0,93 = 0,11101…
4
код до
00
010
100
1011
1101
1110
5
код после
00
01
100
101
110
111
qi Pi
0,72
0,36
0,54
0,36
0,27
0,21
31

32.

Средняя длина для построенного кода qср = 2,46. Соответствующее кодовое дерево до и после
усечения имеет вид:
Алгоритм Шеннона-Фано применим и при основании кода больше двух (K >
2). В этом случае алфавит разбивается на K частей примерно одинаковой суммарной
вероятности
19.03.2019
32

33.

Методика кодирования Хаффмана (Хаффмэна)
Рассмотренные выше алгоритмы кодирования не всегда приводят к хорошему результату, вследствие отсутствия
четких рекомендаций относительно того, как делить множество кодируемых знаков на подгруппы. Рассмотрим
методику кодирования Хаффмана, которая свободна от этого недостатка.
1. Кодируемые знаки, также как при использовании метода Шеннона и Фано, располагают в порядке
убывания их вероятностей (таблица).
2. Далее на каждом этапе две последние позиции списка заменяются одной и ей приписывают
вероятность, равную сумме вероятностей заменяемых позиций.
3. После этого производится пересортировка списка по убыванию вероятностей, с сохранением
информации о том, какие именно знаки объединялись на каждом этапе.
4. Процесс продолжается до тех пор, пока не останется единственная позиция с вероятностью, равной 1.
19.03.2019
33

34.

35.

После этого строится кодовое дерево.
а) Корню дерева ставится в соответствие узел с
вероятностью, равной 1.
б) Далее каждому узлу приписываются два потомка с
вероятностями, которые участвовали в формировании значения
вероятности обрабатываемого узла.
в) Так продолжают до достижения узлов, соответствующих
вероятностям исходных знаков
19.03.2019
35

36.

19.03.2019
36

37.

Процесс кодирования по кодовому дереву осуществляется следующим образом.
Одной из ветвей, выходящей из каждого узла, например, с более высокой
вероятностью, ставится в соответствие символ 1, а с меньшей – 0.
Спуск от корня к нужному знаку дает код этого знака. Правило кодирования в
случае равных вероятностей оговаривается особо.
Жирным шрифтом в таблице выделены объединяемые позиции, подчеркиванием –
получаемые при объединении позиции.
19.03.2019
37

38.

Буква
a1
a2
a3
a4
a5
a6
Р(ai)
0.36
0.18
0.18
0.12
0.09
0.07
qi
1
3
3
3
4
4
код
0
111
110
100
1011
1010
qi Pi
0,36
0,54
0,54
0,36
0,36
0,28
Средняя длина для построенного кода qср = 2,44,
ЭНТРОПИЯ ИСТОЧНИКА В ЭТОМ ПРИМЕРЕ:
19.03.2019
H(Z) = 2,37
38

39.

БЛОЧНОЕ КОДИРОВАНИЕ
19.03.2019
39

40.

Можно видеть, что как для кода Хаффмана, так и для кодов Фано и
Шеннона среднее количество двоичных символов, приходящееся на символ
источника, приближается к энтропии источника, но не равно ей.
Данный результат представляет собой следствие теоремы кодирования
без шума для источника (первой теоремы Шеннона), которая утверждает:
1. При любой производительности источника сообщений, меньшей
пропускной способности канала, т. е. при условии
Ī(Z) =Сд – ε,
где ε — сколь угодно малая, положительная величина,
существует способ кодирования, позволяющий передавать по каналу все
сообщения, вырабатываемые источником.
2. Не существует способа кодирования, обеспечивающего передачу
сообщений без их неограниченного накопления, если Ī(Z) > Сд.
19.03.2019
40

41.

Рассматриваемая теорема Шеннона часто приводится и в другой
формулировке:
сообщения источника с энтропией Н(Z) всегда можно закодировать
последовательностями символов с объемом алфавита m так, что среднее
число символов на знак сообщения qср будет сколь угодно близко к величине
Н(Z)/log m,
но не менее ее.
Данное утверждение обосновывается также указанием на возможную
процедуру кодирования, при которой обеспечивается равновероятное и
независимое поступление символов на вход канала, а следовательно, и
максимальное количество переносимой каждым из них информации, равное
log m. Как мы установили ранее, в общем случае это возможно, если
кодировать сообщения длинными блоками. Указанная граница достигается
асимптотически при безграничном увеличении длины кодируемых
блоков.
19.03.2019
41

42.

Итак, из теоремы Шеннона следует, что
избыточность в последовательностях символов можно
устранить, если перейти к кодированию достаточно
большими блоками.
Попробуем на примере алфавита из 2 букв – А и Б.
Пусть р(А)=0.7 и р(Б)=0.3
Н=-0.7*log(0.7)-0.3*log(0.3)=0.881…
19.03.2019
42

43.

Используем метод Шеннона-Фано
Буква
А
Б
Вероятность
0.7
0.3
код
1
0
1*0.7+1*0.3=1 двоичн. знаков на букву.
1-0.881= 0.12 . Стало быть, на 12% больше минимального по
Шеннону значения 0.881.
19.03.2019
43

44.

Буква
АА
АБ
БА
ББ
Вероятность
0.7*0.7=0,49
0.7*0.3=0,21
0.3*0.7=0,21
0.3*0.3=0,21
код
1
01
001
000
1*0.49+2*0.21+3*0.3=1,81
На одну букву приходится 1,81/2=0,905 на 3% больше 0,881 .
Если применить метод Ш-Ф для 3-х буквенных комбинаций ААА, ААБ итд
получится 0, 895 двоичных знаков – на 1.5% больше.
19.03.2019
44

45.

Недостатки методов эффективного кодирования
1. Различия в длине кодовых комбинаций. Обычно знаки на вход устройства кодирования
поступают через равные промежутки времени. Если им соответствуют комбинации
различной длины, то для обеспечения полной загрузки канала при передаче без потерь
необходимо предусмотреть буферное устройство, как на передающей, так и на приемной
стороне.
2. Задержка в передаче информации. Достоинства эффективного кодирования проявляются
в полной мере при кодировании длинными блоками. Для этого необходимо накапливать
знаки, как при кодировании, так и при декодировании, что приводит к значительным
задержкам.
3. Низкая помехозащищенность. Даже одиночная ошибка, возникшая в процессе передачи,
может нарушить свойство префиксности кода и повлечь за собой неправильное
декодирование ряда последующих комбинаций. Это явление называют треком ошибки.
4. Сложность технической реализации. Использование буферных устройств, для
обеспечения равномерной загрузки канала, при разной длине кодовых комбинаций и
организация кодирования блоками для повышения эффективности приводят к усложнению
реализации систем эффективного кодирования.
19.03.2019
45

46.

Задача 1. Для передачи сообщений используется код, состоящий из трех
символов, вероятности появления которых равны 0.6, 0.3 и 0.1. Корреляция
между символами отсутствует. Определить избыточность кода.
19.03.2019
46

47.

Задача 2
На вход дискретного симметричного канала без памяти поступают
двоичные символы
и
с априорными вероятностями
и
. Переходные вероятности
в таком канале
задаются соотношением
,
где p=0.05 — вероятность ошибки. Определить все апостериорные вероятности.
19.03.2019
47

48.

В таком канале каждый кодовый символ может быть принят с ошибочной
вероятностью
.
А может быть передан правильно с вероятностью
P( y j | xi )
P( xi | y j )
19.03.2019
P( xi , y j )
P( xi )
,
P(xi , y j )= P( y j )P(xi | y j ) .
P( xi , y j )
P( y j )
48

2.2. Избыточность кодов.

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

Понятие избыточности легко пояснить следующим примером.

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

Действительно, по теореме Котельникова (§ 1.7), непрерывное сообщение (сигнал) можно передать последовательностью мгновенных отсчетов его значений с промежутками между ними :

где fmax – верхняя граничная частота в спектре сигнала.

При наличии помех промежутки между отсчетами (Δtn) необходимо уменьшать, т.е.

В этом случае мы увеличиваем число отсчетов и, следовательно, увеличиваем избыточность сообщения и тем самым повышаем его помехозащищенность.

Пусть сообщение из n символов содержит количество информации I. Если сообщение обладает избыточностью, то его (при отсутствии шума) можно передать меньшим числом символов n0 (n0 < n). При этом, количества информации (I1 и I1max), приходящиеся на один символ сообщения, будут связаны соотношением:

и, следовательно,

За меру избыточности принимается величина R:

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

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

По наличию избыточности коды также делятся на избыточные и неизбыточные. Для неизбыточных кодов характерно то, что они позволяют просто определить различные символы сообщения. Переход от неизбыточного кода к избыточному осуществляется путем добавления позиций в кодовых символах, которые можно получить либо путем различных логических операций, выполняемых над основными информационными позициями, либо путем использования алгоритмов, связывающих неизбыточный и избыточный коды. Например, если есть символы сообщения А1; А2; А3; А4, то их можно закодировать в двоичном неизбыточном коде:

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

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

    1. Эффективное кодирование. Алгоритм Шеннона-Фено.

    Эффективное кодирование равновероятных символов сообщений.

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

    В случае, если все символы алфавита кодируемого сообщения независимы и их появление равновероятно, построение оптимального эффективного кода не представляет трудностей. Действительно, пусть Н(х) — энтропия исходного сообщения. Будем считать, что символы сообщения (хi) равновероятны и объем алфавита исходного источника сообщений равен m. Следовательно, вероятность появления любого i-го символа данного сообщения (P(хi)) будет одинакова, т.е.

    а энтропия сообщения равна (Н(х)):

    Если для кодирования используется числовой код по основанию k (объем алфавита элементов кодовых символов равен k), то энтропия элементов кодовых символов (Н1), при условии, что элементы символов кода появляются равновероятно и взаимнонезависимо, определится из соотношения:

    Тогда длина эффективного равномерного кода, т.е. число элементов в кодовом символе (lэфф.), может быть найдена из соотношения:

    где m = k n .

    Эффективное кодирование неравновероятных символов сообщений

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

    Очевидно, что эффективное кодирование будет оптимальным, если неравномерное распределение вероятностей появления символов алфавита источника сообщений с помощью определенным образом выбранного кода переводят в равновероятное распределение вероятностей появления независимых элементов кодовых символов. В этом случае среднее количество инфор­мации, приходящееся на один элемент символа кода, будет максимальным. Для определения вида кода, удовлетворяющего этому требованию, можно рассмот­реть «функцию стоимости» (цены передачи символов сообщения) в виде:

    где P(xi) — вероятность появления i-го символа алфавита исходного кодируемого сообщения;

    m — объем алфавита;

    Wi — стоимость передачи i-го символа алфавита, которая пропорциональна длине кодового слова.

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

    Длина кодового символа (ni) должна быть обратно пропорциональна вероятности появления соответствующего символа исходного кодируемого сообщения (xi);

    Начало более длинного кодового символа не должно совпадать с началом более короткого (для возможности разделения кодовых символов без применения разделительных знаков);

    В длинной последовательности элементы символов кода должны быть независимы и равновероятны.

    Теоретическое обоснование возможности эффективного кодирования передаваемых по каналу сообщений обеспечивает теорема, доказанная К. Шенноном и которая носит название первая теорема Шеннона или основная теорема Шеннона о кодировании для каналов без помех. Эта теорема гласит, что если источник сообщений имеет энтропию Н [бит/символ], а канал обладает пропускной способностью С [бит/сек] (пропускная способность характеризует максимально возможное значение скорости передачи информации), то всегда можно найти способ кодирования, который обеспечит передачу символов сообщения по каналу со средней скоростью

    где ε — сколь угодно малая величина.

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

    Эта теорема часто приводится в иной формулировке: сообщения источника сообщений с энтропией Н всегда можно закодировать последовательностями элементов кодовых символов с объемом алфавита k так, что среднее число элементов символов кода на один символ кодируемого сообщения (l ср. ) будет сколь угодно близко к величине H / log2 k, но не менее ее.

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

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

    Алгоритм Шеннона-Фено. Суть этого алгоритма, при использовании двоичного кода (объем алфавита элементов символов кода равен 2), заключается в следующем.

    Все символы алфавита источника сообщений ранжируют, т. е. располагают в порядке убывания вероятностей их появления. Затем символы алфавита делятся на две группы приблизительно равной суммарной вероятности их появления. Все символы первой группы получают «0» в качестве первого элемента кодового символа, а все символы второй группы — «1». Далее группы делятся на подгруппы, по тому же правилу примерно равных суммарных вероятностей, и в каждой подгруппе присваивается вторая позиция кодовых символов. Процесс повторяется до закодирования всех символов алфавита кодируемого источника сообщений. В кодовый символ, соответствующий последней группе, добавляется в качестве последнего элемента «0» для того, чтобы начальный элемент символов кода не совпадал с конечным, что позволяет исключить разделительные элементы между символами кода.

    Таблица 2.2 иллюстрирует процесс построения кода Шеннона–Фено на примере источника сообщений, алфавит которого состоит из восьми символов.

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *