Выводы для чего требуется кодирование и декодирование. Кодирование и декодирование информации. Что означает понятие «декодирование»

Кодирование информации

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

Определение 1

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

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

Наиболее распространенными из которых являются:

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

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

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

Замечание 1

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

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

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

Декодирование информации

Определение 2

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

а) процесс придания определенного смысла полученным сигналам;

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

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

Модель кодирования/декодирования С. Холла

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

Замечание 2

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

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

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

Свою теорию С. Холл сформулировал, используя в качестве примера работу телевидения, но ее можно применить к любым видам средств массовой информации. Суть теории заключается в том, что медиасообщение, проходя на своем пути от источника до получателя, претерпевает ряд преобразований. В результате средства медиакоммуникации передают сообщения, конформные или оппозиционные по отношению к правящим властям, различным общественным, политическим и экономическим социальным институтам. Эти сообщения кодируются зачастую в форме устоявшихся содержательных жанров (к ним можно отнести новости политического, спортивного, экономического содержания; музыкальные передачи, сериалы и пр., в общем все то, что смотрят обыватели), имеющих очевидный содержательный смысл, актуализированную направленность и встроенные руководства для их интерпретации заинтересованной целевой аудиторией. Зрители же, в свою очередь, подходят к содержанию, предлагаемому СМИ, с другими «смысловыми структурами», которые строятся на их собственном здравом смысле, идеях и опыте.

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

Теория Холла содержит ряд принципиальных положений , это:

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

Таким образом, мы пришли к определению того, кто такой получатель.

Определение 3

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

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

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

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

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

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

Что представляет собой кодирование информации?

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

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

Что представляет собой декодирование информации?

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

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

Кодирование и декодирование текстовых данных

Если нажать на клавишу клавиатуры, компьютер получает сигнал, представленный двоичным числом, расшифровку которого легко отыскать в кодовой таблице. Мировым стандартом считается таблица ASCII. Правда, знать, что такое кодирование и декодирование, мало. Необходимо также понимать, как размещаются данные в компьютере. Например, для хранения одного символа двоичного кода выделен 1 байт или 8 бит. Данная ячейка способна принимать лишь два значения: 0 и 1. Таким образом, выходит, что один байт дает возможность зашифровать 256 различных символов, поскольку это число комбинаций существует возможность составить.

Данные сочетания и выступают в качестве ключевой части таблицы ASCII. Например, буква S кодируется в виде 01010011. Если совершить ее нажатие на клавиатуре, выполняется кодирование и декодирование данных, а пользователь получает требуемый результат, который отображается на экране. Половина таблицы стандартов ASCII имеет коды цифр, управляющих символов, а также латинских букв. Остальная ее часть заполняется следующим:

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

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

Кодирование чисел

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

Примеры кодирования и декодирования чисел

Стоит ознакомиться с двумя способами кодировки числа 45. Когда данная цифра встречается в текстовом фрагменте, каждая ее составляющая закодирована в соответствии с таблицей стандартов ASCII, 8 битами. Таким образом, четверка обратится в 01000011, а пятерка превратится в 01010011. Когда число 45 задействовано для вычислений, используется специальная методика преобразования в восьмиразрядный двоичный код 001011012. Для его хранения требуется всего 1 байт.

Кодирование графической информации

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

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

Зеленый;
красный;
синий.

Почему именно эти цвета?

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

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

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

Кодирование звуковой информации

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

Кодирование данных в двоичном коде

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

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

Плюсы двоичного кодирования

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

Минусы двоичного кодирования

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

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

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

В настоящее время понятие "код" трактуют по-разному. Ряд авторов (Р. Бландел, А. Б. Зверинцев, В. Г. Корольке, А. П. Панфилова и др.) понимают коды в самом широком плане - как любую форму представления информации либо как набор однозначных правил, посредством которых сообщение может быть представлено в той или иной форме. Человеческая речь также представляет собой один из кодов.

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

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

Декодирование - в техническом смысле - это процесс, обратный процессу кодирования. В более широком плане это: - процесс придания определенного смысла полученным сигналам;

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

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

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

Модель кодирования/декодирования С. Холла

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

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

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

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

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

Теория Холла содержит ряд принципиальных положений, а именно:

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

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

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

Теория кодирования информации является одним из разделов теоретической информатики. К основным задачам, решаемым в данном разделе, необходимо отнести следующие:

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

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

Кодирование - это переход от одного алфавита (буквенного кода) к другому.

Пусть A = {а 1 ,а 2 ,...,а т) и В = {b l ,b 2 ,...,b n) - алфавиты.

Элементы алфавита называются буквами.

Последовательность букв некоторого алфавита называют словом в этом алфавите.

Л*, В* - множество слов в алфавите Ли В соответственно.

Кодированием будем называть функцию F: В* где S с А*.

S называется множеством сообщений.

Образы сообщений называют кодами , т. е. р е В *: (3 = F{ а),а е S.

Измерением кодирования является количество букв в алфавите В, т. е. это п-ичное кодирование.

Двоичное кодирование ^>В = 2,В = {0,1}.

Декодирование - это F~ { .

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

Свойства кодирования

1. Существование декодирования (компиляция, трансляция программ не требует декодирования).
2. Помехоустойчивость или исправление ошибок Ф" близок к коду Р) => (F -1 (р) = F~ l (р")).
3. Сложность или простота кодирования и декодирования (криптографический алфавит: F - простая, a F~" сложная).

Алфавитное кодирование

Количество букв в слове называется длиной слова.

Пусть а = а. а, 2 ...д 4 - слово. |а| = к - длина слова а.

Пустое слово - слово нулевой длины. |л| = О, Л g А.

Пусть а = а,а 2 - слово, полученное склеиванием слов а (и а 2 .

Тогда а, - начало, префикс слова а, а 2 - окончание, постфикс слова а. Алфавитное (побуквенное) кодирование задается схемой а:Р, я 2 ->Р 2 , ..., >> где а к е Д р Л е 2Г.

Т. е. частный случай кодирования, когда задаются коды каждой буквы алфавита А, кодами являются слова алфавита В.

V = {р А }” ч - элементарные коды.

Алфавитное кодирование определяет кодирование для любого множества сообщений S из А*.

Примеры

Л = {°,1,-,9} ^ = {0,1}

1. ст: 1,2 -> 10,3 -> 11,4 -? 100, ..., 9-> 1001 > - схема алфавитного кодирования.

/г(123) = 11011

Это кодирование не взаимнооднозначное, т. к. ДЗОЗ) = 11011, т. е. а, = 123 * а 2 = 303, но F(a,) = /’(a 2).

2. ст: 0000,1->0001,2->0010, ...,9 -> 1001 >.

Это двоично-десятичное кодирование. Эта схема является взаимнооднозначной. Следовательно, существует декодирование.

разделимой, если любое слово, составленное из элементарных кодов, единственным образом разделяется на элементарные коды.

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

Примеры (предыдущий)

1. Неразделимая схема кодирования (11 1/1 и 11);

не префиксная (элементарный код 1 является элементарным кодом 2).

2. Разделимая и префиксная.

Теорема

Любая префиксная схема является разделимой.

Допустим, что схема префиксная, но неразделимая.

Тогда существует два разных представления одного слова: р. ...р^ = р У| ...р^ . Пусть Р,. * Р Л.

Тогда либо Р (. является началом слова р у. (р. р = Р у.), либо наоборот (р у. р = Р (.). Следовательно, схема не префиксная. Получили противоречие.

Обратное утверждение неверно!!!

Не любая разделимая схема является префиксной.

Достаточное условие разделимости (но не является необходимым): префиксная => разделимая.

Пример

А = {а,Ь) й = {0,1}

а:0, Z>->01> - не префиксная, разделимая.

Теорема (необходимое условие разделимости)

о:-^ Ь к >" =1 - разделимая, то выполняется неравенство:

Обратное неверно!!!

Теорема

Если для чисел /, ...,1 т выполняется неравенство то существует разделимая схема алфавитного кодирования о:Ь к >“ =1 , где В = {0,1}, такая, что

IPJ = К’ к= 1 ’ т

Пример

1. а:а -» 0,Ь -» 01 > - не префиксная, разделимая.

По теореме выполняется неравенство:

2. а:0,6-»1 > - разделимая, т. к.

Если неравенство не выполняется, то схема не является разделимой.

Если неравенство выполняется, то ничего нельзя сказать про разделимость схемы.

Минимизация длины кода сообщения

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

Очевидно:

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

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

Если длины элементарных кодов различны, то длина кода сообщения зависит от состава букв в сообщении и от того, какие элементарные коды каким буквам назначены.

Пусть задан вектор p = (p i ,...,p m) распределения вероятностей букв в сообщении, причем р х > р 2 >...>р т >0 (упорядочены не по возрастанию).

Пусть дана схема алфавитного кодирования о: Ъ к >“ =1 . Определим для этой схемы математическое ожидание коэффициента увеличения длины сообщения, или среднюю длину кода одного символа:

которая называется средней ценой (длиной) алфавитного кодирования а для распределения вероятностей р.

Схема алфавитного кодирования, для которой длины всех элементарных кодов равны, называется равномерной.

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

Для равномерного кодирования средняя цена кодирования равна

L(p) - минимальная длина разделимой схемы алфавитного кодирования при распределении вероятностейр.

Среди схем алфавитного кодирования, средняя длина которых не превосходит конечное количество / 0 , существует схема с минимальной длиной а» (р), для которой /„.(/>) = inf/„(/>).

Такая схема а* (р) называется кодированием с минимальной избыточностью или оптимальным кодированием для распределения вероятности р.

Свойства оптимального кодирования

1. Пусть ст, - схема оптимального кодирования.

Тогда

Доказательство (от противного)

Пусть это свойство не выполняется, т. е. p t > Pj & |(3, | > |р у |).

а/ , полученная из а, перестановкой кодов (3,. и р у, т.е. а/ : a j -» р у; а } -» Р (..

Тогда

Получили противоречие с тем, что а, - схема оптимального кодирования.

2. Пусть а, - схема оптимального кодирования.

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

3. Пусть стГ 1 : ->р Л >"“/ - схема оптимального кодирования. р.Р>р 2 >...>р т _> 0, Pj = q x + q 2 , гдер т _ х >q x >q 2 > 0.

Тогда схема алфавитного кодирования

является оптимальной для распределения вероятностей

Самокорректирующиеся коды

Помехоустойчивый код

Пусть есть канал связи С, содержащий источник помех.

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

где S с A*, KgB А = В = {0,1}.

Виды ошибок:

1. Ошибка замещения разряда: 0 -> 1; 1^0.
2. Ошибка выпадения разряда: 0 -> Л; 1 -> Л.
3. Ошибка вставки разряда: Л -» 0; Л ^ 1.

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

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

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

Код с обнаружением ошибок

Нужно добавить бит четности - контрольная сумма:

а = а 1 а 2 ...а т - бит четности - сумма по модулю 2 всех остальных - контрольная сумма.

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

Код Хаффмана

Код Хаффмана является оптимальным кодированием.

Правила построения

Построение кода Хаффмана основано на сжатии алфавита.

Пусть есть алфавит А = {а х,а 2 ,...,а т) с вероятностями р х > р 2 >...> р т.

Условимся не различать две наименее вероятные буквы а т _ х и а т.

Переупорядочим буквы алфавита А х по не возрастанию вероятностей. Полученный алфавит снова подвергнем однократному сжатию. Получим алфавит А 2:А 2 = т-2 и т. д., сжимаем до алфавита А т _ 2 :|Д т _ 2 | = 2. Двум буквам этого алфавита приписываем коды 0 и 1.

Пусть определены коды всех букв алфавита А } _ х, определим коды букв алфавита Aj_ 2 .

Буквы алфавита Aj_ 2 , которые входят в алфавит А у._ х , имеют тот же код.

Пусть буквы а" и а" при сжатии объединяются в одну букву Ь, имеющую код р и вероятность р(я")> р(я").

Тогда а" р0 , а" -> pi.

Следовательно, А т _ 2 ,...,А.

Таким образом, начиная с А т _ 2 , строится код исходного алфавита А По построению этот код будет префиксным и, следовательно, разделимым. Набор кодов {0,1} является оптимальным для алфавита из двух букв А т _ 2 . На каждом шаге из оптимальной схемы кодирования снова строится оптимальная схема кодирования, и полученный код является оптимальным.

Код Хаффмана используется для упорядоченных вероятностей.

Пример

Построить схему оптимального кодирования для алфавита с распределением вероятностей /? = (0,2;0,2;0,19;0,12;0,11;0,09;0,09) (вероятности не возрастают). Решение

1. Выписываем вероятности в порядке убывания в первый столбец таблицы.
2. Складываем две последние вероятности: 0,09 + 0,09 = 0,18.
3. Упорядочиваем оставшиеся вероятности в порядке убывания и записываем результат в третий столбец.
4. Опять складываем две последние вероятности и, упорядочивая, записываем в пятый столбец и т. д., пока не останется всего два числа: 0,6 и 0,4, которые в сумме дают единицу.
5. Верхнему числу присваиваем код «0», нижнему - «1».
6. Теперь двигаемся справа налево: тем числам, которые присутствуют, присваиваем тот же самый код (0,4 - «1»), а тем, которые в сумме дают число 0,6, присваиваем коды «00» (верхнему) и «01» (нижнему).
7. Аналогично доходим до самого первого столбика и формируем коды для всех элементов вектора р (см. табл. 11).

Таблица 11

Ответ: а 2 -»11; а 3 000; я 4 -» 010; а 5 -> 011; я 6 0010; я 7 -> 0011 >. Оптимальная длина кодирования:

/.=0,2-2 + 0,2-2 + 0,19-3 + 0,12-3 + 0,11-3 + 0,09-4 + 0,09-4 = 2,78 / 0 = 3 - длина равномерного кодирования

Код Фано

При кодировании по Фано все сообщения записываются в таблицу по степени убывания вероятности и разбиваются на две группы примерно (насколько это возможно) равной вероятности. Соответственно этой процедуре из корня кодового дерева исходят два ребра, которым в качестве весов присваиваются полученные вероятности. Двум образовавшимся вершинам приписываются кодовые символы 0 и 1. Затем каждая из групп вероятностей вновь делится на две подгруппы примерно равной вероятности. В соответствии с этим из каждой вершины 0 и 1 исходят по два ребра с весами, равными вероятностям подгрупп, а вновь образованным вершинам приписывают символы 00 и 01, 10 и 11.

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

Пример (табличный способ)

Построить схему оптимального кодирования для алфавита с распределением вероятностей р = (0,2; 0,2; 0,19; 0,12; 0,11; 0,09; 0,09) (вероятности не возрастают). Решение

Смысл: выделяем две группы в зависимости от разности суммы, которая должна быть минимальной. Верхней группе чисел присваиваем «0», а нижней «1». Алгоритм:

1. Посчитать суммы сверху и суммы снизу (см. табл. 12).
2. Найти модуль разности сумм сверху и сумм снизу:

3. Выбрать наименьший модуль разности:

|0,59-0,41| = 0,18

4. Разбить группу на две подгруппы: получается, что в первую подгруппу входят первые три элемента, а во вторую - все остальные.
5. Присваиваем верхним трем элементам коды «О», а остальным нижним коды «1».
6. Теперь разбиваем первую подгруппу, состоящую из трех элементов, на две подгруппы (см. пункты 1-4):

Таблица 12

Сумма сверху		Сумма снизу

|0,2 - 0,39| = 0,19 - наименьший модуль разности |0,4 - 0,19| = 0,21

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

7. Присваиваем код первой подгруппе, т. е. одному элементу - «00» (это итоговый код первого элемента), а второй подгруппе, состоящей из двух элементов, код «01». Когда группа состоит из двух элементов, то можно сразу присвоить итоговые коды: «010» и «011».

Аналогично разбиваем вторую подгруппу и получаем итоговые коды.

Таблица 13

Сумма сверху		Сумма снизу

Кодирование информации

Определение 1

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

Наиболее распространенными из которых являются:

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

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

Замечание 1