Кодирование и декодирование

29 Письменность и кодирование информации

Цели кодирования:

1)засекречивание информации

2)быстрый способ записи

3)передача по техническим каналам связи

4)выполнение математических вычислений

Передача информации — перемещение сообщений от источника к приемнику по каналу передачи. В процессе передачи информации всегда имеется несколько участников:

· тот, кто предоставляет информацию (выступает ее источником);

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

· канал связи, по которому передается информация.

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

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

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

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

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

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

По типу среды распространения каналы связи делятся на проводные, акустические, оптические, инфракрасные и радиоканалы. Например, один из современных каналов передачи информации — световод (оптоволокно) — позволяет передавать сигналы лазеров на расстояние более 100 км без усиления.

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

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

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

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

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

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

Дополнительная информация в интернет-источнике:

https://spravochnick.ru/informatika/kodirovanie_informacii/kodirovanie_i_dekodirovanie_informacii/

Понятие о теоремах шеннона

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

Помехи в передачи информации — вполне обычное дело во всех сферах профессиональной деятельности и в быту. Один из примеров был приведен выше, другие примеры — разговор по телефону, в трубке которого «трещит», вождение автомобиля в тумане и т.д. Чаще всего человек вполне справляется с каждой из указанных выше задач, хотя и не всегда отдает себе отчет, как он это делает (т.е. неалгоритмически, а исходя из каких-то ассоциативных связей). Известно, что естественный язык обладает большойизбыточностью (в европейских языках — до 7%), чем объясняется большая помехоустойчивость сообщений, составленных из знаков алфавитов таких языков. Примером, иллюстрирующим устойчивость русского языка к помехам, может служить предложение «в словох всо глосноо зомононо боквой о». Здесь 26% символов «поражены», однако это не приводит к потере смысла. Таким образом, в данном случае избыточность является полезным свойством.

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

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

Задача эффективного кодирования описывается триадой:

Х = {X 4i} — кодирующее устройство — В.

Здесь X, В — соответственно входной и выходной алфавит. Под множеством хi можно понимать любые знаки (буквы, слова, предложения). В — множество, число элементов которого в случае кодирования знаков числами определяется основанием системы счисления (например, т = 2). Кодирующее устройство сопоставляет каждому сообщению хi из Х кодовую комбинацию, составленную из пi символов множества В. Ограничением данной задачи является отсутствие помех. Требуется оценить минимальную среднюю длину кодовой комбинации.

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

n cр = пiРi (средняя величина).

Этому среднему числу символов алфавита В соответствует максимальная энтропия Нтаx = nср log т. Для обеспечения передачи информации, содержащейся в сообщениях Х кодовыми комбинациями из В, должно выполняться условие H4mах? Н(х), или пcр log т? — Рi log Рi. В этом случае закодированное сообщение имеет избыточность пcр? H(x) / log т, nmin = H(x) / log т.

Коэффициент избыточности

Кu = (Hmax – H(x)) / Hmax = (ncp – nmin) / ncp

Выпишем эти значения в виде табл. 1.8. Имеем:

Nmin = H(x) / log2 = 2,85, Ku = (2,92 — 2,85) / 2,92 = 0,024,

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

Таблица 1.8 Пример к первой теореме Шеннона

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

Доказательство теоремы основывается на следующих рассуждениях. Первоначально последовательность Х = {xi} кодируется символами из В так, что достигается максимальная пропускная способность (канал не имеет помех). Затем в последовательность из В длины п вводится r символов и по каналу передается новая последовательность из п + r символов. Число возможных последовательностей длины и + т больше числа возможных последовательностей длины п. Множество всех последовательностей длины п + r может быть разбито на п подмножеств, каждому из которых сопоставлена одна из последовательностей длины п. При наличии помехи на последовательность из п + r выводит ее из соответствующего подмножества с вероятностью сколь угодно малой.

Это позволяет определять на приемной стороне канала, какому подмножеству принадлежит искаженная помехами принятая последовательность длины п + r, и тем самым восстановить исходную последовательность длины п.

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

Дополнительная информация в интернет-источнике:

(см.пункт 2.)

https://profbeckman.narod.ru/InformLekc.files/Inf10.pdf