Трансформация идеи в сообщение с помощью кодовых знаков называется

Обновлено: 02.07.2024

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

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

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

Преобразование знаков или групп знаков одной знаковой системы в знаки или группы знаков другой знаковой системы называется перекодированием.

Кодирование может быть равномерным и неравномерным. При равномерном кодировании все символы заменяются кодами равной длины; при неравномерном кодировании разные символы могут кодироваться кодами разной длины (это затрудняет декодирование). Неравномерный код называют еще кодом переменной длины.

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

Коды Морзе для некоторых букв.

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

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

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

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

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

Например, код Морзе не является префиксным — для него не выполняется условие Фано. Поэтому в кодовый алфавит Морзе, кроме точки и тире, входит также символ–разделитель — пауза длиной в тире. Без разделителя однозначно декодировать код Морзе в общем случае нельзя.

Содержание

Кодирование

Кодовые деревья

Для наглядного описания кодов используются кодовые деревья. Если число узлов на каждом его уровне содержит узлов, где l — номер уровня (корень дерева находится на нулевом уровне), оно называется полным. Очевидно, величина >" width="" height="" />
, называемая объёмом дерева, характеризует максимальное число кодовых комбинаций, которое можно построть при помощи данного дерева.

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

Префиксное свойство

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

Примеры

Равномерное кодирование: для алфавита с m₁ символами используются кодовые слова с длиной m_1)" width="" height="" />
, где up — округление до большего целого. В этом случае неиспользованными остаются m_1-n" width="" height="" />
кодовых слов, а остальным проставляются в соответствие символы первичного алфавита. Код Бодо имеет фиксированную длину 5 символов.

Префиксные коды: Код Шеннона-Фано — первый алгоритм неравномерного кодирования. Код Хаффмана — известный метод построения оптимального неравномерного кода (ОНК) с использованием деревьев. Арифметическое кодирование — обобщение кода Хаффмана.

Литература

Цымбал В. П. Теория информации и кодирование. — К.:Выща Школа, 1977. — 288 с.

В десятичной системе основанием счисления является число 10. Поэтому любое целое число Кможно представить в виде

где a₀, a₁, . a_n - коэффициенты, принимающие значение от 0 до 9. Так, число 265 можно записать как 2 10 2 + 6 10 1 + 5 10°. Очевидно, в качестве основания счисления можно принять любое целое число т и представить число N как

где a₀, a₁, . a_n - коэффициенты, принимающие значение от 0 до т - 1. Задаваясь величиной m, можно построить любую систему счисления.

При m=2 получим двоичную систему, в которой числа записываются с помощью двух цифр 0 и 1.

Например, число 13 в двоичной системе записывается 1101, что соответствует выражению 1 2 3 +1 2 2 +0 2 1 + 1 2°.

Арифметические действия в двоичной системе весьма просты. Так, сложение осуществляется по следующим правилам:

Различают поразрядное сложение без переноса в старший разряд, так называемое "сложение по модулю два". Правила этого сложения следующие:

Для передачи данных рекомендован семиэлементный код МТК-5. Коды МТК-2 и МТК-5 являются первичными (простыми). Основными параметрами кодов являются: основание кода т, длина кодовой комбинации n, расстояние между кодовыми комбинациями d_ij и вес кодовой комбинации w. Расстояние d_ij характеризует различие между двумя кодовыми комбинациями и определяется по Хеммингу числом несовпадающих в них разрядов, т.е. числом единиц в сумме двух комбинаций по модулю 2. Число ненулевых элементов в кодовой комбинации определяет её вес w. Применение равномерных кодов упрощает построение автоматических буквопечатающих устройств и не требует передачи разделительных символов между кодовыми комбинациями.

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

Типичным примером неравномерных кодов является код Морзе, в котором символы 0 и 1 используются только в двух сочетаниях - как одиночные (1 и 0) или как тройные (111 и 000). Сигнал, соответствующий одной единице, называется точкой, трём единицам - тире. Символ 0 используется как знак, отделяющий точку от тире, точку от точки и тире от тире. Совокупность 000 используется как разделительный знак между кодовыми комбинациями.

Модуляция. Общие понятия

Следует иметь в виду, что в системах радиосвязи после передатчика посредством передающих антенн образуется пространственно-временной сигнал u(t, r) (электромагнитная волна), который зависит не только от времени t, но и пространственных координат точки наблюдения

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

z(t, r) = s(t, r) + n(t, r).

Чаще всего оно сначала посредством приёмной антенны превращается в чисто временной сигнал z(t), который в дальнейшем подвергается чисто временной обработке. Вопросы формирования и обработки пространственно-временных сигналов в настоящем учебнике не рассматриваются, т.е. будем считать, что устройства преобразования временной сигнал - поле на передаче и поле — временной сигнал на приёме включены внутри заданной "линии связи". Эти вопросы рассматриваются в специальных курсах.

Рис. 4.3. Виды модуляции

амплитудную (AM),

частотную (ЧМ) и

фазовую (ФМ).

Если переносчиком является периодическая последовательность импульсов, то при заданной форме импульсов v(t) можно образовать четыре основных вида импульсной модуляции:

амплитудно- импульсную (АИМ),

широтно- импульсную (ШИМ),

время-импульсную (ВИМ, ФИМ) и

Применение радиоимпульсов позволяет получить ещё два вида модуляции: по частоте и по фазе высокочастотного заполнения.

На рис. 4.4 приведены формы сигнала при двоичном коде для различных видов дискретной или цифровой модуляции (манипуляции). При AM символу 1 соответствует передача несущего колебания в течение времени Т (посылка), символу 0 - отсутствие колебания (пауза). При ЧМ передача несущего колебания с частотой f_l соответствует символу 1, а передача колебания с частотой f_o соответствует 0. При двоичной ФМ меняется фаза несущей при каждом переходе от 1 к 0 и от 0 к 1.

Наконец, на практике применяют систему относительной фазовой модуляции (ОФМ). В отличие от ФМ, при ОФМ фазу сигналов отсчитывают не от некоторого эталона, а от фазы предыдущего элемента сигнала. Например, символ 0 передаётся отрезком синусоиды с начальной фазой предшествующего элемента сигнала, а символ 1 — таким же отрезком с начальной фазой, отличающейся от начальной фазы предшествующего элемента сигнала на . При ОФМ передача начинается с посылки одного не несущего информации элемента, который служит опорным сигналом для сравнения фазы последующего элемента.

В более общем случае дискретную модуляцию следует рассматривать как преобразование кодовых символов 0, 1, . т - 1 в определённые отрезки сигнала u_i(t), где i = 0, 1, . т-1 — передаваемый символ. При этом вид сигнала ui(t),в принципе, может быть произволен. В действительности его выбирают так, чтобы удовлетворить требованиям, предъявляемым к системе связи (в частности, по скорости передачи и по занимаемой полосе частот), и чтобы сигналы хорошо различались с учётом воздействующих помех.

Длительность посылки первичного сигнала b(t) при дискретной передаче определяет скорость передачи посылок (техническую скорость или скорость модуляции). Эта скорость v выражается числом посылок, передаваемых за единицу времени. Измеряется техническая скорость в Бодах. Один Бод — это скорость, при которой за 1 с передаётся одна посылка. Если длительность посылки Т выражена в секундах, то скорость модуляции v = 1/T вБодах.

В качестве переносчика сигнала связи можно использовать не только постоянный или синусоидальный ток, но и периодическая последовательность импульсов (а).

АИМ – амплитудно-импульсная модуляция,

ЧИМ – частотно-импульсная модуляция,

ДИМ – модуляция импульсов по длительности (ШИМ),

ФИМ – фазово-импульсная модуляция.

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

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

КОНСПЕКТ

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

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

Декодирование — обратный процесс восстановления информации из закодированного представления.

РЕШЕНИЕ ЗАДАЧ

Задача 1: Для кодирования букв О , В , Д , П , А решили использовать двоичное представление чисел 0 , 1 , 2 , 3 и 4 соответственно (с сохранением одного незначащего нуля в случае одноразрядного представления).

Закодируйте последовательность букв ВОДОПАД таким способом и результат запишите восьмеричным кодом.

Решение:

Переведем числа в двоичные коды и поставим их в соответствие нашим буквам:

Теперь закодируем последовательность букв из слова ВОДОПАД :

Разобьем результат на группы из трех символов справа налево, чтобы перевести их в восьмеричную систему счисления:

010 010 001 110 010

Результат: 22162

Задача 2: Для 5 букв латинского алфавита заданы их двоичные коды (для некоторых букв — из двух бит, для некоторых — из трех). Эти коды представлены в таблице:

Какой набор букв закодирован двоичной строкой 1100000100110 ?

Решение:

Во-первых, проверяем условие Фано: никакое кодовое слово не является началом другого кодового слова. Условие верно.

Код разбиваем слева направо согласно данным, представленным в таблице. Затем переведём его в буквы:

110 000 01 001 10

Результат: b a c d e.

2 вариант решения:

Сделаем дерево, согласно кодам в таблице:

110 000 01 001 10

Результат: b a c d e.

Задача 3:

Для кодирования некоторой последовательности, состоящей из букв К , Л , М , Н решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для буквы Н использовали кодовое слово 0 , для буквы К — кодовое слово 10 .

Какова наименьшая возможная суммарная длина всех четырёх кодовых слов?

Решение:

Будем использовать дерево. Влево откладываем 0 , вправо — 1 :

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

(К) -> 10 -> 2 символа

(Л) -> 110 -> 3 символа

(М) -> 111 -> 3 символа

Суммарная длина всех четырёх кодовых слов равна:

(Н)1 + (К)2 + (Л)3 + (М)3 = 9

Ответ: 9.

ДОМАШНЕЕ ЗАДАНИЕ:

ВАРИАНТ 1 (для ребят, у которых фамилия начинается на букву А. Г, Д, Ж )

1) Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д, Е, Ж, З, И, Й. решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для букв А, Б, В, Г, Д, Е, Ж, З, И использовали соответственно кодовые слова 1100, 0010, 1010, 0000, 0111, 1101, 0101, 100, 0001. Укажите кратчайшее возможное кодовое слово для буквы Й, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением.

2) Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д, Е, Ж, З, И, Й. решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для букв А, Б, В, Г, Д, Е, Ж, З, И использовали соответственно кодовые слова 1010, 1101, 010, 00, 1000, 1110, 1001, 0111, 1011. Укажите кратчайшее возможное кодовое слово для буквы Й, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением.

ВАРИАНТ 2 (для ребят, у которых фамилия начинается на букву К, М, П, С )

3) Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д, Е, Ж, З, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для букв А, Б, В, Г, Д, Е, Ж использовали соответственно кодовые слова 11, 0010, 1011, 01, 0011, 000, 1010. Укажите кратчайшее возможное кодовое слово для буквы З, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением.

4) Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д, Е, Ж, З, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для букв А, Б, В, Г, Д, Е использовали соответственно кодовые слова 10, 110, 010, 0110, 111, 0111. Укажите кратчайшее возможное кодовое слово для буквы Ж, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением.

ВАРИАНТ 3 (для ребят, у которых фамилия начинается на букву Т, У, Ч, Ш, Я)

5) Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д, Е, Ж, З, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для букв А, Б, В, Г, Д, Е использовали соответственно кодовые слова 0101, 101, 011, 00, 0100, 11. Укажите кратчайшее возможное кодовое слово для буквы Ж, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением.

6) Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д, Е, Ж, З, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для букв А, Б, В, Г, Д, Е использовали соответственно кодовые слова 11, 0010, 100, 0011, 01, 000. Укажите кратчайшее возможное кодовое слово для буквы Ж, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением.

Читайте также: