Помехоустойчивость данных

Кодирование последовательностей символов

 

Пусть количество передаваемых сообщений заранее неизвестно и, следовательно, заранее неизвестны вероятности поступления каждого из сообщений на вход канала связи. Однако, известно, что сообщения формируются из символов алфавита A={a,b}, появляющихся независимо друг от друга с вероятностями p1=0,7 и p2=0,3.

При посимвольном кодировании этих сообщений, например, с помощью процедуры Шеннона-Фано, получим равномерные коды, приведенные в таблице 1.2:

Таблица 1.2

Символ ai Вероятность pi Кодовое слово ki Средняя длина кодового слова λkA
a 0,7 1 бит/символ
b 0,3

 

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

Например, для всевозможных двухсимвольных последовательностей алфавита A получим данные, приведенные в таблице 4.3. Из сравнения данных в таблицах 1.2 и 1.1 видно, что кодирование двухсимвольных комбинаций более экономно, чем трехсимвольное кодирование. Еще лучшие результаты дает трехсимвольное кодирование (0,895 бит.символ).

 

Таблица 1.3

Последовательность символов aiaj Вероятность pij Кодовое слово kij Средняя длина кодового слова λkA
aa 0,49 0,905 бит/символ
ab 0,21
ba 0,21
bb 0,09

 

При дальнейшем увеличении размерности кодируемых комбинаций средняя длина кодового слова уменьшается, стремясь к предельному значению, приблизительно равному 0,881 бит/символ. Повышение экономности кода достигается за счет того, что с увеличением числа кодируемых последовательностей расширяется диапазон возможных значений вероятностей их появления и на каждом шаге кодирования удается точнее разбивать множество кодируемых последовательностей на приблизительно равновероятные подмножества.

 

 

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

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

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

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

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

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

Как обнаружить появление ошибок и исправить их? Издавна известен следующий простой способ: многократно повторять исходные знаки.

Например, вместо двоичных знаков 0 и 1 можно передавать через канал связи последовательности 0…0 и 1…1, каждая из которых содержит нечетное число знаков. Ясно, что если помехи действуют на знаки независимо и вероятность искажения знака меньше 1/2, то принятая комбинация будет содержать больше неискаженных знаков, чем искаженных. Следовательно, приемник сообщений должен подсчитывать число нулей и единиц в полученных комбинациях и делать вывод о том, что была передана единица, если в некоторой комбинации больше единиц, или был передан нуль, если в ней больше нулей. Чем больше кратность повторения, тем достовернее такой вывод.

Применение процедуры повторения ведет к тому, что при кодировании сообщений используются не все возможные кодовые комбинации. Такое кодирование называется избыточным. При этом используемые кодовые комбинации называются разрешенными, а неиспользуемые – запрещенными. Например, если вместо знаков 0 и 1 мы передаем кодовые слова 00000 и 11111 (пятикратное повторение), то разрешенными являются всего две кодовые комбинации из 25 = 32 возможных.

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

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