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

Кодирование - процесс представления информации (сообщения) в виде кода.

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

Научные основы кодирования были описаны К.Шенноном, который исследовал процессы передачи информации по техническим каналам связи (теория связи , теория кодирования ). При таком подходе кодирование понимается в более узком смысле: как переход от представления информации в одной символьной системе к представлению в другой символьной системе . Например, преобразование письменного русского текста в код азбуки Морзе для передачи его по телеграфной связи или радиосвязи. Такое кодирование связано с потребностью приспособить код к используемым техническим средствам работы с информацией (см. “Передача информации” ).

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

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

Цели кодирования и способы кодирования

Способ кодирования одного и того же сообщения может быть разным. Например, русский текст мы привыкли записывать с помощью русского алфавита. Но то же самое можно сделать, используя английский алфавит. Иногда так приходится поступать, посылая SMS по мобильному телефону, на котором нет русских букв, или отправляя электронное письмо на русском языке из-за границы, если на компьютере нет русифицированного программного обеспечения. Например, фразу: “Здравствуй, дорогой Саша!” приходится писать так: “Zdravstvui, dorogoi Sasha!”.

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

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

Еще одно важное обстоятельство: выбор способа кодирования информации может быть связан с предполагаемым способом ее обработки . Покажем это на примере представления чисел - количественной информации. Используя русский алфавит, можно записать число “тридцать пять”. Используя же алфавит арабской десятичной системы счисления, пишем: “35”. Второй способ не только короче первого, но и удобнее для выполнения вычислений. Какая запись удобнее для выполнения расчетов: “тридцать пять умножить на сто двадцать семь” или “35 х 127”? Очевидно - вторая.

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

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

История технических способов кодирования информации

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

Сэмюэль Финли Бриз Морзе (1791–1872), США

Такой способ кодирования получил название азбуки Морзе. В ней каждая буква алфавита кодируется последовательностью коротких сигналов (точек) и длинных сигналов (тире). Буквы отделяются друг от друга паузами - отсутствием сигналов.

Самым знаменитым телеграфным сообщением является сигнал бедствия “SOS” (S ave O ur S ouls - спасите наши души). Вот как он выглядит в коде азбуки Морзе, применяемом к английскому алфавиту:

–––

Три точки (буква S), три тире (буква О), три точки (буква S). Две паузы отделяют буквы друг от друга.

На рисунке показана азбука Морзе применительно к русскому алфавиту. Специальных знаков препинания не было. Их записывали словами: “тчк” - точка, “зпт” - запятая и т.п.

Характерной особенностью азбуки Морзе является переменная длина кода разных букв , поэтому код Морзе называют неравномерным кодом . Буквы, которые встречаются в тексте чаще, имеют более короткий код, чем редкие буквы. Например, код буквы “Е” - одна точка, а код твердого знака состоит из шести знаков. Это сделано для того, чтобы сократить длину всего сообщения. Но из-за переменной длины кода букв возникает проблема отделения букв друг от друга в тексте. Поэтому приходится для разделения использовать паузу (пропуск). Следовательно, телеграфный алфавит Морзе является троичным, т.к. в нем используется три знака: точка, тире, пропуск.

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

Жан Морис Эмиль Бодо (1845–1903), Франция

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

В современных компьютерах для кодирования текстов также применяется равномерный двоичный код (см. “Системы кодирования текста” ).

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

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

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

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

Предложите ученикам подумать о том, как можно обойтись без разделения букв в коде. Эти размышления должны привести к идее равномерного кода, в котором каждый символ кодируется двумя десятичными цифрами: А - 01, Б - 02 и т.д.

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

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

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

1. Андреева Е .В ., Босова Л .Л ., Фалина И .Н . Математические основы информатики. Элективный курс. М.: БИНОМ. Лаборатория Знаний, 2005.

2. Бешенков С .А ., Ракитина Е .А . Информатика. Систематический курс. Учебник для 10-го класса. М.: Лаборатория Базовых Знаний, 2001, 57 с.

3. Винер Н . Кибернетика, или Управление и связь в животном и машине. М.: Советское радио, 1968, 201 с.

4. Информатика. Задачник-практикум в 2 т. / Под ред. И.Г. Семакина, Е.К. Хеннера. Т. 1. М.: БИНОМ. Лаборатория Знаний, 2005.

5. Кузнецов А.А., Бешенков С.А., Ракитина Е.А., Матвеева Н.В., Милохина Л.В. Непрерывный курс информатики (концепция, система модулей, типовая программа). Информатика и образование, № 1, 2005.

6. Математический энциклопедический словарь. Раздел: “Словарь школьной информатики”. М.: Советская энциклопедия, 1988.

7. Фридланд А .Я . Информатика: процессы, системы, ресурсы. М.: БИНОМ. Лаборатория Знаний, 2003.

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

Способы кодирования информации. Для кодирования одной и той же информации могут быть использованы разные способы; их выбор зависит от ряда обстоятельств: цели кодирования, условий, имеющихся средств. Если надо записать текст в темпе речи используем стенографию; если надо передать текст за границу используем английский алфавит; если надо представить текст в виде, понятном для грамотного русского человека, записываем его по правилам грамматики русского языка. «Здравствуй, Саша!» «Zdravstvuy, Sasha!»

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

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

Двоичное кодирование в компьютере . Вся информация, которую обрабатывает компьютер должна быть представлена двоичным кодом с помощью двух цифр: 0 и 1. Эти два символа принято называть двоичными цифрами или битами. С помощью двух цифр 0 и 1 можно закодировать любое сообщение. Это явилось причиной того, что в компьютере обязательно должно быть организованно два важных процесса: кодирование и декодирование. Кодирование – преобразование входной информации в форму, воспринимаемую компьютером, т.е. двоичный код. Декодирование – преобразование данных из двоичного кода в форму, понятную человеку. Привет! 1001011

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

КОДИРОВАНИЕ И ДЕКОДИРОВАНИЕ

Процесс представления информации в определенной стандартной форме и обратный процесс восстановления информации по ее такому представлению. В математич. литературе кодированием наз. произвольного множества Ав конечных последовательностей (слов) в нек-ром алфавите В, а декодированием - . Примерами кодирования являются: представление натуральных чисел в r-ичной системе счисления, при к-ром каждому числу N=i, 2, ... ставится в слово b 1 b 2 ... b l в алфавите В r = {0, 1, ..., r-1} такое, что b 1 неравно 0 и b 1 r l -1 +...+ b l -1 r+b l =N; текстов на русском языке с помощью телеграфного кода в последовательности, составленные из посылок тока и пауз различной длительности; отображение, применяемое при написании цифр почтового индекса (см. рис.). В последнем случае каждой десятичной цифре соответствует слово в алфавите В 2 = {0, 1} длины 9, в котором символами 1 отмечены номера использованных линий (напр., цифре 5 соответствует слово 110010011). Исследование различных свойств К. и д. и построение эффективных в определенном смысле кодирований, обладающих требуемыми свойствами, составляет проблематику теории кодирования. Обычно критерий эффективности кодирования так или иначе связан с минимизацией длин кодовых слов (образов

элементов множества А), а требуемые свойства кодирования связаны с обеспечением заданного уровня помехоустойчивости, понимаемой в том или ином смысле. В частности, под помехоустойчивостью понимается возможность однозначного декодирования при отсутствии или допустимом уровне искажений в кодовых словах. Помимо помехоустойчивости, к кодированию может предъявляться дополнительных требований. Напр., при выборе кодирования для цифр почтового индекса необходимо согласование с обычным способом написания цифр. В качестве дополнительных требований часто используются ограничения, связанные с допустимой сложностью схем, осуществляющих К. и д. Проблематика теории кодирования в основном создавалась под влиянием разработанной К. Шенноном (С. Shannon, ) теории передачи информации. Источником новых задач теории кодирования служат создание и совершенствование автоматизированных систем сбора, хранения, передачи и обработки информации. Методы решения задач теории кодирования главным образом комбинаторные, теоретико-вероятностные и алгебраические. Произвольное кодирование f множества (алфавита) Асловами в алфавите Вможно распространить на множество А* всех слов в А(сообщений) следующим образом:

где i=1, 2, . . ., k. Такое отображение f: наз. побуквенным кодированием сооб. щений. Более общий кодирований сообщений образуют автоматные кодирования, реализуемые инициальными асинхронными автоматами, выдающими в каждый времени нек-рое (быть может, пустое) слово в алфавите В. Содержательный смысл этого обобщения заключается в том, что в разных состояниях реализует различные кодирования букв алфавита сообщений. Побуквенное кодирование - это автоматное кодирование, реализуемое автоматом с одним состоянием: Одним из направлений теории кодирования является изучение общих свойств кодирования и построение алгоритмов распознавания этих свойств (см. Кодирование алфавитное ). В частности, для побуквенных и автоматных кодирований найдены необходимые и достаточные условия для того, чтобы:

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

Большинство задач теории кодирования сводится к изучению конечных или счетных множеств слов в алфавите В r . Такие множества наз. кодами. В частности, каждому однозначному кодированию f: (и побуквенному кодированию ) соответствует Одно из основных утверждений теории кодирования состоит в том, что условие взаимной однозначности побуквенного кодирования накладывает следующее ограничение на длины li=l,if )кодовых слов f(i):

Справедливо и обратное утверждение: если (l 0 , .. ., l m -1)- набор натуральных чисел, удовлетворяющих (1), то существует взаимно однозначное побуквенное кодирование такое, что слово f(i)имеет длину l i ;. При этом, если числа l i упорядочены по возрастанию, то в качестве f(i) можно взять первые после запятой l i символов разложения числа в r-ичную (метод Шеннона).

Наиболее законченные результаты в теории кодирования связаны с построением эффективных взаимно однозначных кодирований. Описанные здесь конструкции используются на практике для сжатия информации и выборки информации из памяти. Понятие эффективности кодирования зависит от выбора критерия стоимости. При определении стоимости L(f)взаимно однозначного побуквенного кодирования предполагается, что каждому числу поставлено в соответствие положительное р i и Р= {р 0 , ..., P m-1 ). Исследованы следующие варианты определения стоимости L(f):

причем предполагается, что в первых двух случаях р i - вероятности, с к-рыми некоторый бернуллиевый порождает соответствующие буквы алфавита В т а в третьем случае р i - заданные длины кодовых слов. При первом определении стоимость равна средней длине кодового слова, при втором определении с ростом параметра tболее длинные кодовые слова оказывают все большее влияние на стоимость ( при и при ), при. третьем определении стоимость равна максимальному превышению длины l i кодового слова над заданной длиной р i . Задача построения взаимно однозначного побуквенного кодирования f: В* т ->В* r , минимизирующего стоимость L(f), равносильна задаче минимизации функции L(f) на наборах (l 0 , ..., 1 т-1 )из натуральных чисел, удовлетворяющих (1). Решение этой задачи известно при каждом из указанных определений стоимости. Пусть величины L(f)на наборах (l 0 , . . ., l m-1 )из произвольных (не обязательно натуральных) чисел равен L r (P)и достигается на наборе (l 0 (Р), ..., l т-1 (Р)). Неотрицательная I(f) = L (f) - L r (P)наз. избыточностью, а величина I(f)/L (f)- относительной избыточностью кодирования f. Для избыточности взаимно однозначного кодирования построенного по методу Шеннона для длин справедливо I(f)<1. При первом, наиболее употребительном, определении стоимости как среднего числа кодовых символов, приходящихся на одну букву порождаемого источником сообщения, величина L r (P)равна энтропии Шеннона

источника, вычисленной по основанию r, a l i (P)=-log r p i . Граница избыточности I(f) = L ср (f)- Н r (P)< 1 может быть улучшена с помощью так наз. кодирования блоками длины k, при к-ром сообщения длины k(а не отдельные буквы) кодируются по методу Шеннона. Избыточность такого кодирования не превышает 1/k. Этот же прием используется для эффективного кодирования зависимых источников. В связи с тем, что определение длин l i при кодировании по методу Шеннона основано на знании статистики источника, для нек-рых классов источников разработаны методы построения универсального кодирования, гарантирующего определенную верхнюю границу избыточности для любого источника из этого класса. В частности, построено кодирование блоками длины к, избыточность к-рого для любого бернуллиевого источника асимптотически не превышает (при фиксированных ), причем эта асимптотическая не может быть улучшена.

продолжение Кодирование и декодорование...

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

При исследовании задач построения эффективных помехоустойчивых кодирований обычно рассматривают кодирования к-рым соответствуют коды {f(0), . .., f(m-1)}, принадлежащие множеству слов длины пв алфавите В r , и предполагают, чтo буквы алфавита сообщений В т равновероятны. Эффективность такого кодирования оценивают избыточностью I(f)= п-log r m или скоростью передачи В(f)= При определении помехоустойчивости кодирования формализуется понятие ошибки и вводится в рассмотрение нек-рая образования ошибок. Ошибкой типа замещения (или просто ошибкой) наз. преобразование слова, состоящее в замещении одного из его символов другим символом алфавита В r . Напр., проведение лишней линии при написании почтового индекса приводит к замещению в кодовом слове символа 0 символом 1, а отсутствие нужной линии - к замещению символа 1 символом 0. Возможность обнаружения и исправления ошибок основана на том, что для кодирования f, обладающего ненулевой избыточностью, декодирование f -1 может быть произвольным образом доопределено на r п -тсловах из не являющихся кодовыми. В частности, если множество разбито на тнепересекающихся подмножеств D 0 , . . ., D m-1 таких, что а декодирование f -1 доопределено так, что f -1 (D i )=i, то при декодировании будут исправлены все ошибки, преобразующие кодовое слово f(i) в D i , i=0, ..., т-1. Аналогичная возможность имеется и в случае ошибок других типов таких, как стирание символа (замещение символом другого алфавита), изменение числового значения кодового слова на b=1, ..., r-1, i=0, 1, ... (арифметическая ошибка), выпадение или вставка символа и т. п.

В теории передачи информации (см. Информации передача )рассматриваются вероятностные модели образования ошибок, называемые каналами. Простейший задается вероятностями р ij замещения символа iсимволом j. Для канала определяется величина (пропускная способность)

где максимум берется по всем наборам (q 0 , . . ., q m-1 )таким, что и Эффективность кодирования f характеризуется скоростью передачи R(f), а помехоустойчивость - средней вероятностью ошибки декодирования Р(f) (при наилучшем разбиении. В n r на подмножества D i ). Основной результат теории передачи информации ( Шеннона) состоит в том, что пропускная способность Сявляется верхней гранью чисел Rтаких, что для любого е>0 при всех п, начиная с нек-рого, существует кодирование

для к-рого и Р(f)

Другая модель образования ошибок (см. Код с исправлением ошибок, Код с исправлением арифметических ошибок, Код с исправлением выпадений и вставок )характеризуется тем, что в каждом слове длины ппроисходит не более заданного числа tошибок. Пусть E i (t)- множество слов, получаемых из f(i)в результате tили менее ошибок. Если для кода

множества E i (t), i=0, ..., m-1, попарно не пересекаются, то при декодировании таком, что E i (t)Н D i , будут исправлены все ошибки, допустимые рассматриваемой моделью образования ошибок, и такой код наз. кодом с исправлением tошибок. Для многих типов ошибок (напр., замещений, арифметич. ошибок, выпадений и вставок) d( х, у ), равная минимальному числу ошибок данного типа, преобразующих слово в слово является метрикой, а множества E i (t)- метрическими шарами радиуса t. Поэтому задача построения наиболее эффективного (т. е. максимального по числу слов т)кода в В n r с исправлением tошибок равносильна задаче плотнейшей упаковки метрического пространства шарами радиуса t. Код для цифр почтового индекса не является кодом с исправлением одной ошибки, так как d(f(0), f (8))=1 и d(f(5), f (8)) = 2, хотя все другие расстояния между кодовыми словами не менее 3.

Задача исследования величины I r (n, t )- минимальной избыточности кода в с исправлением tошибок типа замещения распадается на два основных случая. В первом случае, когда tфиксировано, а справедлива асимптотика

причем достигается "мощностная" граница, основанная на подсчете числа слов длины пв шаре радиуса t. Асимптотика величины I r (n, t )при г>2, а также при r=2 для многих других типов ошибок (напр., арифметич. ошибок, выпадений и вставок) не известна (1978). Во втором случае, когда t= [pn ], где р - некоторое фиксированное число, 0<р<(r-1)/2r, а "мощностная" граница

где T r (p)=-p log r (p/ (r- 1))-(1-р)log r (l- p), существенно улучшена. Имеется предположение, что верхняя граница

полученная методом случайного выбора кода, является асимптотически точной, т. е. I r ( п, [ рп ])~пТ r (2р ). Доказательство или опровержение этого предположения - одна из центральных задач теории кодирования.

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

Еще одно исследований в теории кодирования связано с тем, что многие результаты (напр., теорема Шеннона и граница (3)) не являются "конструктивными", а представляют собой теоремы существования бесконечных последовательностей {К п } кодов В связи с этим предпринимаются усилия, чтобы доказать эти результаты в классе таких последовательностей {К п } кодов, для к-рых существует Тьюринга, распознающая принадлежность произвольного слова длины lмножеству за время, имеющее медленный роста относительно l(напр., llog l).

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

Лит. : Шеннон К., Работы по теории информации и кибернетике, пер. с англ., М., 1963; Берлекэмп Э., Алгебраическая кодирования, пер. с англ., М., 1971; Питерсон У., Уэлдон Э., Коды, исправляющие ошибки, пер. с англ., 2 изд., М., 1976; Дискретная и математические вопросы кибернетики, т.1, М., 1974, раздел 5; Бассалыго Л. А., Зяблов В. В., Пинскер М. С, "Пробл. передачи информации", 1977, т. 13, № 3, с. 5-17; [В] Сидельников В. М., "Матем. сб.", 1974, т. 95, в. 1, с. 148 - 58.

В. И. Левенштейн.

Математическая энциклопедия. - М.: Советская энциклопедия . И. М. Виноградов . 1977-1985 .

Смотреть что такое "КОДИРОВАНИЕ И ДЕКОДИРОВАНИЕ" в других словарях:

См. Кодирование и декодирование … Математическая энциклопедия

- (от франц. code – свод законов, правил) – отображение (преобразование) нек рых объектов (событий, состояний) в систему конструктивных объектов (называемых кодовыми образами), совершаемое по определ. правилам, совокупность к рых наз. шифром К.,… … Философская энциклопедия

Кодирование - Encoding Отождествление квантованного сигнала электросвязи с кодовыми словами Примечания: 1. Под кодовым словом понимается упорядоченная последовательность символов некоторого алфавита. 2. В конкретных устройствах квантование сигнала электросвязи … Словарь-справочник терминов нормативно-технической документации

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

Декодировка, дешифрование, дешифровка, дешифрирование, расшифровка, расшифровывание. Ant. кодирование Словарь русских синонимов. декодирование сущ., кол во синонимов: 8 декодировка (8) … Словарь синонимов

декодирование - Восстановление дискретного сообщения по сигналу на выходе дискретного канала, осуществляемое с учетом правила кодирования. [Сборник рекомендуемых терминов. Выпуск 94. Теория передачи информации. Академия наук СССР. Комитет технической… … Справочник технического переводчика

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

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

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

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

Пусть 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