Тема: Алфавитное кодирование.

a = a₁, a₂, … , a_i, …, a_n ,

где iÎ[1, n], число п показывает количество букв в слове и называется длиной слова a, обозначается п = l(a) = |a|.

Пустое слово обозначается L: l(L) = |L| = 0.

Для слова a = a₁, a₂, … , a_i, …, a_n буква a₁ называется началом, или префиксом слова a, а буква a_n – окончанием, или постфиксом слова a.

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

Соединение слов a₁ и a₂ обозначается a₁,a₂, соединение п одинаковых слов a обозначается aⁿ, причем a⁰ = L.

Множество всех непустых слов алфавита Аобозначается А^*:

А^* = {a | l(a) > 0}.

Множество А называется алфавитомсообщений, а множество В– кодирующималфавитом. Множество слов, составленных в алфавите В, обозначим В^*.

Обозначим через F отображение слов алфавита А в алфавит В.Тогда слово b = F(a) называется кодом слова a.

Кодированиемназывается универсальный способ отображения информации при ее хранении, передаче и обработке в виде системы соответствий между элементами сообщений и сигналами, при помощи которых эти элементы можно зафиксировать. Таким образом, код – это правило однозначного преобразования (т.е. функция) сообщения из одной символической формы представления (исходного алфавита А)в другую (объектный алфавит В), обычно без каких-либо потерь информации. Процесс преобразования F: А^*→В^* слов исходного алфавита Ав алфавит В называетсякодированиеминформации.

Процесс обратного преобразования слова bÎB^* в слово aÎA^* называется декодированием. Таким образом, декодирование – функция, обратная F, т.е. F^-1.

Так как для любого кодирования должна выполняться операция декодирования, то отображение должно быть обратимым (биекция).

Если |B|= m, то F называется m-ичным кодированием, наиболее распространенный случай В = {0, 1} – двоичное кодирование. Именно этот случай и рассматривается в дальнейшем.

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

Алфавитное(или побуквенное), кодирование можно задать таблицей кодов. Кодом или кодирующей функцией будет служить некоторая подстановка s. Тогда:

,

где a_i Î A, b_i Î B.

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

ПРИМЕР

Пусть заданы алфавиты:

А = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}

В = {0, 1}.

Тогда таблица кодирования может быть подстановкой:

.

Это двоично-десятичное кодирование, оно является взаимно однозначным и потому допускает декодирование.

Однако схема:

не является взаимно-однозначной. Например, набор из шести единиц 111111 может соответствовать как слову 333, так и 77, а также 111111, 137, 3311 или 7111 плюс любая перестановка.

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

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

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

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

Неравенство Макмиллана

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

разделима, то справедливо неравенство:

.

ПРИМЕР

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

А = { а, b} и В = {0, 1},

является разделимой, так как:

| b₁ | = 1, | b₂ | = 2,

и, значит, выполняется неравенство Макмиллана:

.

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

Лекция 4.

Мы поможем в написании ваших работ!