ПОМЕХОУСТОЙЧИВОЕ КОДИРОВАНИЕ СООБЩЕНИЙ

Цель работы

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

Задачи

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

Теоретическая часть

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

Метод контроля четности. Данный метод является наиболее простым и эффективным средством обнаружения однократных ошибок, а также ошибок нечетной кратности. При этом кратностью ошибки в некоторой кодовой комбинации называется число искаженных в ней символов. В качестве разрешенных используется половина возможных 2ⁿ (n – количество разрядов кода) кодовых комбинаций – те из них, которые имеют четное число единиц. При передаче через канал связи возникновение однократной ошибки неизбежно приведет к нарушению четности, что и будет обнаружено на выходе канала.

Метод контроля четности реализуется на практике следующим образом. Из последовательности символов, подлежащих передаче через канал связи, выбирается очередной блок из (k-1) символов, называемых информационными, и к нему добавляется k -й символ, называемый контрольным. Значение контрольного символа выбирается таким, чтобы обеспечить четность получаемой кодовой комбинации из k символов.

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

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

Каждые четыре информационных символа a₁, …, a₄ будем дополнять тремя контрольными a₅, a₆, a₇ так, чтобы оказались четными следующие три суммы:

S₁ = a₁ + a₂ + a₃ + a₅

S₂ = a₁ + a₂ + a₄ + a₆

S₃ = a₁ + a₃ + a₄ + a₇

Контроль четности сумм S₁, S₂ и S₃ на выходе канала связи позволяет однозначно установить, была ли допущена однократная ошибка и, если была, то какой из переданных символов был искажен:

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

лишь одна сумма будет нечетной тогда и только тогда, когда искажен входящий в эту сумму один из трех контрольных символов (a₅, a₆ или a₇);

нечетность двух из трех сумм S₁, S₂ и S₃ будет означать, что искажен тот из символов a₂, a₃ или a₄, который входит в обе эти суммы;

наконец, нечетность всех трех сумм означает, что неверно принят входящий во все суммы первый символ a₁.

Использование данного метода сокращает скорость передачи данных в 7/4=1.75 раза и позволяет исправлять все однократные ошибки (но не ошибки большей кратности).

Способность кодов обнаруживать ошибки зависит от минимального расстояния между кодовыми словами. При этом кодовым расстоянием или расстоянием Хэмминга между двумя кодовыми словами одинаковой длины называется число несовпадающих в них символов (при поразрядном сравнении). Например, расстояние Хэмминга между комбинациями 10010011 и 10000001 составляет d =2. Чем больше минимальное расстояние между разрешенными кодовыми комбинациями, тем больше избыточность. При безызбыточном кодировании d =1.

Ошибка кратности r приводит к тому, что искаженная комбинация отодвигается на расстояние d = r от исходной. Если она при этом оказывается разрешенной, то ошибка не может быть обнаружена. Следовательно, чем больше кодовое расстояние между исходными комбинациями, тем большую кратность должны иметь ошибки, чтобы отсутствовала возможность их обнаружения. Если обозначить через d_min минимальное кодовое расстояние между исходными разрешенными комбинациями, то всегда можно обнаружить ошибки кратностью r≤ d_min -1.

Способность кодов исправлять обнаруженные ошибки состоит в возможности однозначного отнесения каждой запрещенной комбинации к некоторой единственной разрешенной. Для этого достаточно, чтобы выполнялось условие d_min ≥ 2r +1. Следовательно, при заданном d_min обеспечивается исправление ошибок кратностью r≤ (d_min -1)/2. Так, коды, используемые выше в методе контрольных сумм, содержат 4 информационных и 3 контрольных символа, d_min=3, поэтому они могут обнаруживать однократные и двукратные ошибки, а исправлять только однократные.