ОСНОВЫ ТЕОРИИ ИНФОРМАЦИИ И КОДИРОВАНИЯ
I . Сообщения.
Система связи предназначена для передачи сообщений от отправителя к получателю. Подлежащее передаче сообщение преобразуется в сигнал, который поступает в канал связи, а после приема подвергается обратному преобразованию в сообщение. Внешние помехи, воздействующие,на канал связи, вносят в передаваемые сигналы искажения. Главная задача системы связи состоит в том, чтобы с достаточной точностью обеспечить взаимно-однозначное соответствие между переданным и принятым сообщением. Типичными примерами систем связи являются: телефонные сети, радиорелейные линии, телеметрические системы, космическая связь, радиовещание, телевидение. В общем случае любая передача сообщений может рассматриваться как система связи.
Сообщение называется дискретным, если оно представляет собой последовательность отдельных элементов (букв, цифр, символов). Дискретное сообщение, состоящее из л элементов, можно рассматривать как слово длины п, элементы которого принимают значения из конечного алфавита. Обычно буквы алфавита кодируются числами, преимущественно в двоичной системе счисления, а соответствующие им сигналы представляют собой последовательности импульсов определенной длительности. Используются равномерные коды, в которых буквы алфавита представляются комбинациями из одинакового числа элементов, и неравномерные коды, составленные из комбинаций различной длины. Примером равномерного кода может служить телетайпный код Бодо, а неравномерного — азбука Морзе
|
|
|
Непрерывное сообщение, в отличие от дискретного, представляется непрерывной функцией времени (например, при передаче звуков или изображений). Однако на практике спектр функций обычно ограничивается, т. е. считается, что спектральное разложение не содержит частот выше некоторой граничной частоты ю. В соответствии с теоремой Котельникова такие функции вполне определяются конечным числом значений, отсчитанных через интервалы времени. Таким образом, передача непрерывного сообщения в том практически важном случае, когда оно может быть представлено функцией с ограниченным спектром, сводится, как и в случае дискретного сообщения, к передаче последовательности чисел.
Из-за неизбежных помех передаваемая последовательность значений непрерывной функции претерпевает в системе связи искажения. Поэтому обычно используют дискретную шкалу передаваемых значений с таким расчетом, чтобы помеха не превосходила половины интервала между двумя соседними уровнями. Замена непрерывной шкалы дискретной называется квантованием, а представляемый последовательностью дискретных значений сигнал называется квантованным.
|
|
|
2. Статистическая мера информации.
В качестве основной характеристики сообщения теория связи принимает величину, называемую количеством информации. Это понятие не затрагивает смысла и важности передаваемого сообщения, а связано со степенью его неопределенности.
Пусть алфавит состоит из m букв, каждая из которых может служить элементом сообщения. Количество возможных сообщений длины п равно числу перестановок с неограниченными повторениями. Для получателя все N сообщений являются равновероятными, а получение конкретного сообщения равносильно для него случайному выбору одного из N объектов с некоторой вероятностью. Ясно, что чем больше N, тем большая степень неопределенности характеризует этот выбор и тем более информативным можно считать сообщение. Итак, число N могло бы служить мерой информации. Однако с позиций техники связи естественно наделить эту меру свойством аддитивности, т. е. определить ее так, чтобы она была пропорциональна длине п сообщения (ведь при передаче и оплате сообщения, например телеграммы, важно не его содержание, а общее число элементов). Этому требованию отвечает логарифмическая функция, которая и принимается в качестве количества информации
|
|
|
Количество информации, приходящееся на один элемент сообщения, называется энтропией. В принципе безразлично, какое основание логарифма используется для определения количества информации и энтропии, так как переход от одного основания другому сводится лишь к изменению единицы измерения. Чаще зсего используют двоичные логарифмы,
При этом единицу количества информации на рдин элемент сообщения называют двоичной единицей или битом. 1 бит — это количество информации, которым характеризуется один двоичный элемент при равновероятных состояниях 0 и 1. Двоичное сообщение длины п содержит п бит информации. Единица количества иформации, равная 8 битам, называется байтом. Если основание логарифма выбрать равным десяти, то энтропия выражается в десятичных единицах на элемент сообщения (дитах), причем 1 дит = Iog10, 1 бит = 3,32 бит.
Определим, например, количество информации, которое содержится в телевизионном сигнале, соответствующем одному кадру развертки. В кадре 625 строк, а сигнал, соответствующий одной строке, представляет собой последовательность из 600 случайных амплитуде импульсов, причем амплитуда каждого импульса ложет принять любое из 8 значений с шагом в I В. Искомое количество 'информации 625 • 600 Iog8 = 1125 106 бит.
|
|
|
Приведенная выше количественная оценка информации оснона на предположении о равновероятности всех букв алфавита. В общем случае каждая из букв появляется в сообщениях с различной вероятностью.
Если элементы сообщения могут принимать значения на непрерывном интервале, то вместо конечного алфавита необходимо рассматривать бесконечное множество возможных состояний элементов, определяемое непрерывным распределением плотности вероятностей w(x). Итак, энтропия и количество информации зависят от распределения w(x). В теории связи большое значение имеет решение вопроса о том, при каком распределении обеспечивается максимальная энтропия Н(х). Можно показать, что при заданной дисперсии наибольшей информативностью сообщение обладает тогда, когда состояния элементов распределены по нормальному закону:
Так как дисперсия определяет среднюю мощность сигнала, то отсюда следуют практически важные выводы. Передача наибольшего количества информации при заданной мощности сигнала (или наиболее экономичная передача данного количества информации) достигается при такой обработке сигнала, которая приближает распределение к нормальному. В то же время, приписывая нормальное распределение помехе, обеспечивают ее наибольшую «информативность», т. е. учитывают ее пагубное воздействие на прохождение сигналов в самом худшем случае. Если дисперсия не ограничена, то, как показывает анализ, энтропия максимальна при условии, что состояния элементов внутри интервала их существования а < х < Ъ распределены по равномерному закону, т. е.
Это значит, что при одинаковой информативности сообщений средняя мощность сигналов для равновероятного распределения их амплитуд должна быть на 42% больше, чем при нормальном распределении.
Избыточность сообщений.
Чем больше энтропия, тем большее количество информации содержит в среднем каждый элемент сообщения.
При передаче одинакового количества информации сообщение тем длиннее, чем меньше его энтропия. Величина r, называемая коэффициентом сжатия, характеризует степень укорочения сообщений при переходе к кодированию состояний элементов, характеризующимся большей энтропией. При этом доля излишних элементов оценивается коэффициентом избыточности
Русский алфавит, включая пропуск между словами, содержит 32 элемента, следовательно, Н = Iog32 = 5 бит. Анализ показывает, что с учетом неравномерности появления различных букв алфавита Н = 4,35 бит, а с учетом зависимости двухбуквенных сочетаний Н = 3,52 бит.
На самом деле вследствие зависимости между сочетаниями, содержащими две и больше букв, а также смысловой зависимости между словами, избыточность русского языка (как и других европейских языков) превышает 50% . Избыточность устраняется построением оптимальных кодов, которые укорачивают сообщения по сравнению с равномерными кодами. В то же время избыточность играет и положительную роль, так как благодаря ей сообщения менее уязвимы со стороны помех. Это обстоятельство используется при помехоустойчивом кодировании.
3 . Эффективное кодирование. При кодировании каждая буква исходного алфавита представляется различимыми последовательностями, состоящими из кодовых букв (цифр). Если исходный алфавит содержит т букв, то для построения равномерного кода с использованием k кодовых букв необходимо удовлетворить соотношение т < kq, где q — количество элементов в кодовой последовательности. Отсюда
Для построения равномерного кода достаточно пронумеровать буквы исходного алфавита и записать их коды как q –разрядные числа в k-ичной системе счисления. Например, при двоичном кодировании 32 букв русского алфавита используется q — Iog32 = 5 разрядов, на чем и основан телетайпный код. Кроме двоичных, наибольшее распространение получили восьмеричные коды. Пусть, например, необходимо закодировать алфавит, состоящий из 64 букв. Для этого потребуется 6 двоичных или 2 восьмеричных разряда. Буква с номером 13 получит соответственно коды 001 101 или 15. Часто используются также двоично-десятичные коды, в которых цифры десятичного номера буквы представляются двоичными кодами. Так, для нашего примера буква с номером 13 кодируется как 0001 0011.
Ясно, что при различной вероятности появления букв исходного алфавита равномерный код является избыточным, так как его энтропия всегда больше энтропии данного алфавита, т. е. информационные возможности такого кода используются не полностью. Устранение избыточности достигается применением неравномерных кодов, в которых буквы, имеющие наибольшую вероятность, кодируются наиболее короткими кодовыми последовательностями, а более длинные комбинации присваиваются редким буквам.
При построении неравномерных кодов необходимо обеспечить возможность их однозначной расшифровки. В равномерных кодах такая проблема не возникает, так как при расшифровке достаточно кодовую последовательность разделить на группы, каждая из которых состоит из q элементов. В неравномерных кодах можно использовать разделительный символ между буквами алфавита (так поступают, например, при передаче сообщений с помощью азбуки Морзе). Если же отказаться от разделительных символов, то следует запретить такие кодовые комбинации, начальные части которых уже использованы в качестве самостоятельной комбинации. Например, если 101 означает код какой-то буквы, то нельзя использовать комбинации 1, 10 или 10101.
Практические методы оптимального кодирования просты и основаны на очевидных соображениях. Прежде всего, буквы (или любые сообщения, подлежащие кодированию) исходного алфавита записываются в порядке убывающей вероятности. Упорядоченное таким образом множество букв разбивается на два подмножества так, чтобы суммарные вероятности этих подмножеств были примерно равны. Затем каждое подмножество снова разбивается на два подмножества с соблюдением того же условия равенства вероятностей. Такое разбиение продолжается до тех пор, пока в подмножествах не окажется только по одной букве кодируемого алфавита. При каждом разбиении буквам верхнего подмножества присваивается кодовый элемент 1, а буквам нижнего подмножества — 0.
4 . Корректирующие коды. Для защиты от помех в связи и вычислительной технике используются корректирующие коды, которые основаны на введении избыточности. Обычно корректирующие коды являются двоичными и равномерными.
Ошибка в кодовой комбинации появляется вследствие замены одних элементов другими, причем r-кратная ошибка возникает при искажении г элементов. Например, если кодовая комбинация 0110111 принята как 0100110, то имеет место двукратная ошибка. Вообще различие между парой кодовых комбинаций выражается расстоянием, которое равно числу несовпадающих двоичных разрядов. Его можно также определить как число единиц в сумме этих комбинаций по модулю два: 0110111 +0100110 = 0010001. Если двоичным комбинациям длины q (равномерный код) сопоставить вершины q-мерного куба, то расстояние означает число ребер, отделяющих одну вершину от другой.
Корректирующие коды позволяют обнаруживать и исправлять ошибки. Ясно, что при использовании для кодирования букв исходного алфавита (или любых сообщений) всех комбинаций любая ошибка останется незамеченной, так как искажающая буква будет воспринята как некоторая другая буква алфавита. Поэтому необходимо располагать избыточным набором кодовых комбинаций, что обычно достигается применением кодов большей длины по сравнению с минимально необходимой. Использованные для кодирования комбинации называют разрешенными, а избыточные—запрещенными.
Наименьшее расстояние между комбинациями данного кода называют кодовым расстоянием. Более полное представление о свойствах кода дает матрица расстояний D, элементы которой равны расстояниям между каждой парой из всех т разрешенных комбинаций. Например, код 000; 001; 010; 111, кодовое расстояние которого d = 1, представляется симметричной матрицей четвертого порядка:
Ошибка может быть обнаружена, если разрешенная комбинация вследствие ее искажения переходит в запрещенную и не может совпасть с какой-либо другой разрешенной комбинацией. Ясно, что для обнаружения однократной ошибки данной комбинации необходимо, чтобы ее расстояние от любой другой комбинации было не меньше двух. Ошибка будет не только обнаружена, но и исправлена, если искаженная комбинация остается ближе к первоначальной, чем к любой другой разрешенной комбинации.
Дата добавления: 2022-01-22; просмотров: 32; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!