Обнаружением ошибок. Коды с исправлением ошибок.

↑

▷ Содержание

⇐ ПредыдущаяСтр 5 из 11Следующая ⇒

Для того, чтобы избежать ошибки в случае одиночных искажений, нужно увеличить кодовое расстояние до d = 2, исключив комбинации только в одном разряде (элементе). Кодовое расстояние, обозначаемое буквой d, определяется путем сложения двух комбинаций по модулю 2 (mod 2), которое обозначается знаком + и производится в соответствии с табл.

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

Отсюда d =3.

Для того, чтобы определить кодовое расстояние между различными кодовыми
комбинациями, составляют матрицы

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

где n — число элементов в комбинациях кода с избыточностью; n₀ — число элементов в комбинациях неизбыточного кода. При кодовом расстоянии d_min > 2 можно не только обнаружить, но и исправить ошибку. Рассмотрим две кодовые комбинации 0011 и 1000, отличающиеся тремя элементами. Допустим, при передаче комбинации 1000 произошло одиночное искажение, получим 0000 1100 1010 или 1001. Можно с уверенностью сказать, что была передана комбинация 1000, т.е. исправить ошибку. Чтобы исправить любое число ошибок r_и, минимальное кодовое расстояние нужно определить по формуле  Отсюда для исправления одиночной ошибки (r_и=1) d_min = 3.Способность кода обнаруживать и исправлять ошибки определяется минимальным кодовым расстоянием из выражения  где r_об и r_и — число обнаруженных и исправленных ошибок при условии Среди помехозащищенных кодов различают блочные и непрерывные. К блочным кодам относятся такие, с помощью которых сообщения передаются блоками определенной длины из некоторого конечного числа символов. В непрерывных кодах нет последовательности информационных символов определенной длины. Между информационными символами по определенному закону размещают проверочные.

Комбинаторные коды. Пример применения комбинаторного кода.

Комбинаторные коды основаны на математической теории соединений: перестановок, размещений и сочетаний.

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

где Р_n — число перестановок.

Коды, построенные по закону размещений, представляют собой комбинации из n элементов по m символов, отличающихся символами или порядком их следования. Число возможных комбинаций определяется выражением

Например, имеем n = 3 (а, б, в) и m = 2, тогда число возможных комбинаций

Коды, построенные по закону сочетаний, представляют собой комбинации по m символов из n возможных, отличающиеся только символами. Число возможных комбинаций определяется выражением

Такие коды называют кодами на одно сочетание.

Код типа  при временном разделении элементов сигналов называют распределительным. Кодом на все сочетания называют код, составленный из заданного числа элементов n и представляющий суммарную комбинацию сочетания:

Циклические коды.

Из систематических большое распространение получили циклические коды. Комбинации в этих кодах обладают свойством цикличности при последовательной перестановке их элементов. Так, если комбинация 1101011 принадлежит циклическому коду, то и комбинации, образованные путем перестановки символов, например, с крайней правой позиции на крайнюю левую (1110101, 1111010, 0111101, 1011110), принадлежат этому же коду. Выбрав определенное число проверочных позиций, можно обеспечить высокую обнаруживающую способность, когда не только при одиночных ошибках, но и при пакетах ошибок. При этом кодирующие и декодирующие устройства будут сравнительно простыми. Несколько усложнив декодирующее устройство, можно обеспечить исправление ошибок.

Познавательные статьи:



Как правильно слушать собеседника

Типичные ошибки при выполнении бросков в баскетболе

Принятие христианства на Руси и его значение

Средства массовой информации США