Теория передачи и кодирования сообщений

1.1.1 Основы теории передачи информации

[1, с. 220–245]; [2, с. 101–130]; [3, с. 70–83].

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

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

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

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

Количество собственной информации, вырабатываемой источником, определяется безусловной (собственной) энтропией. Безусловная энтропия характеризует меру априорной неопределённости о сообщении до его передачи. После приёма сообщения эта неопределённость снимается полностью, если сообщение принято верно, либо частично, если оно не полностью соответствует исходному. Остаточная (частичная) неопределённость в принятом сообщении относительно переданного оценивают условной энтропией. Количество взаимной информации (той, которая содержится в принятом сообщении (сигнале) относительно переданного) определяют как разность безусловной и условной энтропий. Она характеризует меру уменьшения неопределённости относительно реализации переданного сообщения (сигнала), при наблюдении реализации принятого сообщения (сигнала). Количество взаимной информации, передаваемой в единицу времени по каналу связи, называют скоростью R передачи информации. Максимально возможная скорость передачи информации называется пропускной способностью канала связи C; она является характеристикой только канала (т.е. определяется помеховой ситуацией в канале) и не зависит от статистики сигнала. Отношение скорости передачи информации к пропускной способности называют коэффициентом использования канала; он тем больше, чем ближе R к C.

К. Шеннон доказал следующую теорему. Если ошибки в канале отсутствуют, то сообщения на выходе источника можно закодировать так, чтобы передавать информацию со средней скоростью R, сколь угодно близкой к C. Передавать информацию с R > C невозможно. Эта теорема служит основой для построения эффективных статистических кодов, предназначенных для сокращения избыточности передаваемых сообщений и повышения эффективности использования каналов связи. Разработаны статистические коды Хаффмена, Шеннона–Фано. Принцип кодирования здесь состоит в том, что наименее вероятным (редко встречающимся) сообщениям приписываются кодовые комбинации большой значности (длины), а наиболее вероятным сообщениям – кодовые комбинации малой значности. При этом уменьшается среднее число кодовых символов на одно сообщение, что и приводит к увеличению средней скорости передачи информации.

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

Известна теорема К. Шеннона для канала с помехами, которая устанавливает то предельное количество информации, которое может быть передано в единицу времени в данной полосе частот, при данном отношении сигнал/помеха со сколь угодно малой вероятностью ошибок. Отыскание практических путей более полной реализации C является важной задачей теории и техники связи, так как потребность в обмене информации по каналам связи непрерывно возрастает. Кроме того, реализовав высокую скорость передачи R, имеется возможность "обмена" её на более высокую помехоустойчивость.

1.1.2 Основы теории помехоустойчивого кодирования

[1, с. 262–306]; [2, с. 131–158]; [3, с. 168–193].

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

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

Следует чётко усвоить, что результаты К. Шеннона указывают на предельные возможности при оптимальном кодировании и декодировании дискретных сообщений, но не дают рекомендаций по их конкретной реализации. Поэтому основной задачей теории корректирующих кодов, опреде­лившей последующие пути её развития, является нахождение практически реализуемых (конструктивных) методов построения кодеров и декодеров (кодеков).

Для понимания принципов кодирования и декодирования дискретных сообщений необходимо усвоить следующие основные понятия. Кодирование – это процесс преобразования элементов дискретного сообщения в соответствующие числа, представленные кодовыми символами. Например, любое десятичное число можно представить в m_k -ичной системе счисления. Кодовая комбинация (кодовое слово) – это последовательность кодовых символов, соответствующих одному элементу дискретного сообщения. Ко­дом называют полную совокупность кодовых комбинаций, применяемую для кодирования сообщений. Значность кодовой комбинации – это число n символов в ней (длина кодовой комбинации). Если все кодовые комбинации кода имеют одинаковую значимость (длину) – код называется равномерным, например телеграфный код (Бодо, М–2 и т.д.); в противном случае код является неравномерным, например код Морзе, статистический код Шеннона–Фано–Хаффмена и др. Число различных символов в коде называют основанием кода m_k. Если m_k = 2 – код называется двоичным, при m_k > 2 – код многопозиционный.

Корректирующая способность кода – это способность кода обнару­живать или исправлять ошибки. Ошибки при передаче кодированного сообщения сводятся к тому, что некоторые из переданных кодовых символов на приёме заменяются другими – неверными из-за действия помех в канале. Число t искаженных кодовых символов в пределах одной кодовой комбинации называют кратностью ошибок. В теории помехоустойчивого кодирования пользуются понятием расстояния между двумя кодовыми комбинациями и понятием кодового расстояния кода. Расстояние d_mn между двумя m -й и n -й кодовыми комбинациями кода – это суммарный результат сложения по модулю m_k их одноимённых кодовых символов (расстояние Хэмминга). Для двоичных кодов расстояние d_mn – есть число разрядов, в которых символы этих кодовых комбинаций не совпадают. Кодовое расстояние кода, содержащего более двух кодовых комбинаций, есть минимальное расстояние d = min{ d_mn } из совокупности расстояний между различными парами кодовых комбинаций кода. Число d определяет корректирующую способность кода. Если d = 1, код называется примитивным (некорректирующим). Такой код не способен обнаруживать и исправлять на приёме возникающие при передаче в канале связи ошибки. Код - корректирующий (помехоустойчивый), если d > 1. Чем больше кодовое расстояние, тем лучше корректирующая способность кода. Кратность гарантированно обнаруживаемых и исправляемых кодом ошибок определяется соотношениями

t _обн = d - 1 и t _исп = (d - 1)/2.

В настоящее время на практике используются как блочные коды, так и непрерывные (сверточные) коды. При блочном кодировании последовательность информационных кодовых символов разбивается на блоки (кодовые комбинации) по k символов в каждом. Затем каждому такому k- значному блоку сопоставляется n -значный блок, в котором k кодовых символов называются информационными, а добавочные (избыточные) r= (n–k) – корректирующими или проверочными. Такой код называют блочным (n,k) кодом. Двоичный блочный (n,k) код содержит N _р = 2 ^k разрешённых n -значных кодовых комбинаций. Всего же двоичных n -значных кодовых комбинаций можно образовать N ₀=2 ⁿ. Неиспользуемые N _з = N ₀ – N _р кодовые комбинации называют запрещёнными, они по каналу связи не передаются, но необходимы для обнаружения ошибок на приёме.

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

Декодирование корректирующего кода на основе хранения всех разрешенных кодовых комбинаций не является конструктивным. С целью упрощения декодеров был разработан класс линейных корректирующих кодов, когда в памяти декодера достаточно хранить только k = log₂ N _р линейно независимых кодовых комбинаций кода. Двоичный код называется линейным, если сумма по модулю 2 любых разрешенных кодовых комбинаций кода также принадлежит данному коду. При этом любая разрешенная кодовая комбинация линейного кода образуется путём суммирования по модулю 2 линейно независимых кодовых комбинаций.

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

Вопросы для самопроверки

1 Как оценить количество информации, содержащееся в случайной величине, появляющейся с заданной вероятностью?

2 Как оценить энтропию источника дискретных сообщений?

3 Как оценить энтропию источника непрерывных сообщений?

4 Что такое условная энтропия и как она определяется?

5 Как вычислить производительность и избыточность источника?

6 Что такое взаимная информация и скорость передачи информации?

7 Как определить пропускную способность и коэффициент использования канала связи?

8 В чём состоит принцип построения эффективного кода?

9 В чём состоит принцип построения корректирующего кода?

10 В чём состоит принцип декодирования с обнаружением ошибок?

11 В чём состоит принцип декодирования с исправлением ошибок?

12 В чём состоит принцип построения линейного корректирующего кода?

13 Дайте определение расстояния между двумя кодовыми комбинациями и
кодового расстояния кода.

14 Как определить число разрешенных, число запрещённых и общее число кодовых комбинаций блочного (n, k) кода?

15 Каким должно быть кодовое расстояние кода, обнаруживающего ошибки заданной кратности?

16 Каким должно быть кодовое расстояние кода, исправляющего ошибки
заданной кратности?

17 В чём состоит синдромный принцип декодирования линейного корректирующего кода?

18 Что такое порождающая и проверочная матрицы линейного корректирующего кода и их взаимосвязь?

19 Как оценить помехоустойчивость корректирующего кода?

20 Приведите разновидности помехоустойчивого кодирования.