Помехоустойчивое кодирование

В коде «3 из 7» возможных  комбинаций сто двадцать восемь ( =128), а разрешенных кода только тридцать пять. Относительная избыточность _отн = 0,28.

Схема устройства определения  веса комбинаций кода «3 из 7» приведена  на рис. 2.6.

Рис. 2.6 - Схема  определения веса комбинаций кода «3 из 7»

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

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

 - комбинация циклического кода;

 - также комбинация циклического  кода.

При рассмотрении циклических  кодов двоичные числа представляют в виде многочлена, степень которого (п - 1), п - длина кодовой комбинации.

Например, комбинация 1001111 (п=7) будет представлена многочленом

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

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

Построение комбинаций циклического кода возможно путем умножения  исходной комбинации А(х) на образующий полином G(x)с приведением подобных членов по модулю 2:

• если старшая степень произведения не превышает (п - 1), то полученный полином будет представлять кодовую комбинацию циклического кода;
• если старшая степень произведения больше или равна п, то полином произведения делится на заранее выбранный полином степени п и результатом умножения считается полученный остаток от деления.

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

Часто в качестве полинома, на который осуществляется деление, берется полином G(x)= +1. При таком формировании кодовых комбинаций позиции информационных и контрольных символов заранее определить нельзя.

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

Число разрядов регистра выбирается равным степени образующего полинома.

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

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

Рис. 2.7 - Схема  кодирующего регистра

В табл. 2.3 показано, как путем сдвигов исходной комбинации 0101 получается комбинация циклического кода 1010011. п=7, k=4. Комбинация 0101, ключ в положении 1. В течение первых четырех тактов регистр будет заполнен, затем ключ переводится в положение 2. Обратная связь замыкается. Под действием семи сдвигающих тактов проходит формирование семиразрядного циклического кода.

Таблица 2.3

Свойства  циклического кода:

1) циклический код  обнаруживает все одиночные ошибки, если образующий полином содержит  более одного члена. Если G(x)=x+1, то код обнаруживает одиночные ошибки и все нечетные;

2) циклический код  с G(x)=(x+1)G(x) обнаруживает все одиночные, двойные и тройные ошибки;

3) циклический код  с образующим полиномом G(x) степени r = n - k обнаруживает все групповые ошибки длительностью в r символов.