Коды, исправляющие ошибки.

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

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

Применение программных методов позволяет снизить вес кодеров и декодеров.

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

Декодеры циклических кодов.

1) Декодеры, обнаруживающие ошибки. Декодер этого типа состоит обычно из буферного регистра, предназначенного для хранения принятого кодового слова, и схемы деления принятого слова на порождающий многочлен кода g(X). Если полученный в результате деления остаток равен нулю, то считается, что ошибок при передаче не было. В противном случае, т.е. если хотя бы один из коэффициентов остатка отличен от нуля, принимается решение о том, что произошла ошибка при передаче; при этом прием прекращается и на передающую сторону посылается запрос на повторную передачу этого кодового слова.

2) Декодер БЧХ-кода. БЧХ-коды могут иметь достаточно большое кодовое расстояние. Алгоритм декодирования БЧХ-кода включает следующие тять операций: Вычисление синдрома; Вычисление многочлена, имеющего своими корнями локаторы ошибок; Нахождение корней этого многочлена; Вычисление значений ошибок (в двоичном случае операция не нужна); Исправление ошибок.

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

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

Имеются два типа кодеров: - разрядные кодеры, предложенные, - поразрядные кодеры. k0 информационных последовательностей , j=1, …, k0, подаются на k0 входов m-разрядных регистров сдвига и одновременно на выходы кодера для передачи по каналу. Построение n0 - k0 проверочных последовательностей , осуществляется с помощью сумматоров по модулю 2 по порождающим многочленам кода. Общее число разрядов регистров в схеме равно .

В - разрядном кодере сумматоры устанавливаются между ячейками памяти регистра сдвига и, следовательно, каждый из них имеет не более k+1 входов. Определив отклики схемы на единичные воздействия и воспользовавшись свойством линейности точно так же, как и в случае - разрядного кодера. Кодер содержит m-разрядный регистр сдвига для каждой из n0 - k0 проверочных последовательностей и, следовательно, требует для построения разрядов регистров сдвига.

Схема декодера. Принимаемые информационные последовательности подаются на входы содержащегося в декодере - разрядного кодера, который точно так же, как и при кодировании, вычисляет для поступающих на его входы последовательностей проверочную последовательность. Эта проверочная последовательность складывается с принимаемой проверочной последовательностью и таким образом формируется синдром . Синдром вводится в m-разрядный регистр сдвига, с m+1 выходов которого в свою очередь символы поступают на входы логической части декодирующей схемы. При использовании самоортогональных кодов логическая часть декодирующей схемы представляет собой совокупность пороговых элементов с порогом (J/2)+ 1. В случае же использования ортогоанализируемых кодов логические части декодирующей схемы, кроме пороговых элементов, содержат также сумматоры по модулю 2, предназначенные для линейного преобразования синдрома. На выходах логической части декодирующей схемы формируются оценки шумовых символов. Эти оценки складываются с соответствующими выходными символами - разрядного кодера, и таким образом процесс исправления ошибок завершается. После устранения с помощью цепи обратной связи воздействия символов на синдром в последующие моменты времени 1, 2,... точно также осуществляется исправление ошибок.

AN – код.

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

Для исследования AN -кодов необходимо знать основы теории чисел.

Пусть m > 0 - целое положительное число. Произвольное целое число единственным образом может быть представлено в виде (17.1)

Целое число q называется частным, а целое число r - остатком от деления на m или наименьшим неотрицательным вычетом по модулю m.

Для произвольных целых чисел и b имеют место следующие равенства:

или (17.3) кроме того, или (17.4)

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

Целое число, которое делит каждое из чисел называется их общим делителем. Наибольший из делителей называется наибольшим общим делителем или .

Если = 1, то числа называются взаимно простыми.

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

Произвольное целое число > 1 единственным с точностью до порядка образом разлагается в произведение попарно различных простых чисел рi: . (17.7)

Для любого натурального а функция Эйлера j (а) определяется как количество чисел х среди 1, 2, 3,..., а, взаимно простых с а. Пусть р - простое число. Поскольку все целые положительные числа, меньшие р, взаимно просты с р, то j (р) = р - 1. (17.8)

Мультипликативность функции Эйлера означает, что для любых взаимно простых чисел а и b j (а b) = j (а) j (b). (17.9). Для произвольного целого числа а

, или, что то же самое, (17.10)

Если задано целое число m, называемое модулем, то, для любого целого числа а определен остаток rm(a) = r. Если целые числа а и b имеют один и тот же остаток, т. е. если rm(a) = rm(b) = r, то они называются сравнимыми по модулю m: . (17.11)

Множество {a|a = r (mod m)} всех чисел, сравнимых с r, называется классом вычетов, содержащим r.

Теорема Эйлера. Если m > 1 и (а,m)=1, , (17.12) т. е. делится на m.

Эта теорема является обобщением теоремы Ферма.

Теорема Ферма. Если р - простое число и а не делится на р-, то , (17.13)

Справедливо для любого а.

AN-код представляет собой отображение целых чисел 0, 1, 2,..., N0 в целые числа , где А — некоторое фиксированное для каждого кода целое положительное число, называемое порождающим числом. Числа называют кодовыми числами, а их представления в системе счисления по основанию r- кодовыми словами.

Важным свойством AN-кодов является то, что сумма кодовых чисел также является кодовым числом, а именно для любых двух целых чисел N1 и N2 . (17.14)

Следовательно, если N1 + N2 ≤ No, то число A (N1 + N2) = AN1 + AN2 также является одним из кодовых чисел. Поэтому, если закодированные числа сложить с помощью обычного сумматора, то полученная в результате сумма будет кодовым числом суммы исходных чисел. Благодаря этому AN -коды могут обнаруживать и исправлять ошибки, возникающие в сумматорах.

Если r является делителем А, т. е. если r является делителем каждого кодового числа AN, то в представлении чисел по основанию r самый младший разряд всегда будет равен 0. Далее, если А и r не являются взаимно простыми, то в младших разрядах, начиная с некоторого, будут появляться только определенные символы, тогда как другие цифры никогда не появятся.