ГЛАВА 3. КОЛИЧЕСТВЕННАЯ ОЦЕНКА ИНФОРМАЦИИ 12 страница

Рассмотренные выше схемы умножения и деления многочленов непосредственно в том виде, в каком они представлены на рис. 6.11, 6.12, в качестве кодирующих устройств циклических кодов на практике не применяются: первая — из-за того, что образующаяся кодовая комбинация в явном виде не содержит информационных символов, а вторая — из-за того, что между информационными и проверочными символами образуется разрыв в n — k разрядов.

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

Схемы первого типа вычисляют значения проверочных символов путем непосредственного деления многочлена а(х)х^m на образующий многочлен g(x). Это делается с помощью регистра сдвига, содержащего n — k разрядов (рис. 6.14). Схема отличается от ранее рассмотренной тем, что коэффициенты кодируемого многочлена участвуют в обратной связи не через n — k сдвигов, а сразу с первого такта. Это позволяет устранить разрыв между информационными и проверочными символами

В исходном состоянии ключ К1 находится в положении 1. Информационные символы одновременно поступают как в линию связи, так и в регистр сдвига, где за k тактов образуется остаток. Затем ключ Κ1 переходит в положение 2 и остаток поступает в линию связи.

Пример 6.16. Рассмотрим процесс деления многочлена а(х)х^m = = (х³ + +1)x³ на многочлен g(x) = x³ + x²+ 1 за k тактов

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

Таблица 6.15.

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

В исходном положении ключ Κ1 находится в положении 1. За первые k тактов поступающие на вход информационные символы заполняют все ячейки регистра. После этого ключ переводят в положение 2. На каждом из последующих тактов один из информационных символов выдается в канал связи и одновременно формируется проверочный символ, который записывается в последнюю ячейку регистра. Через n — k тактов процесс формирования проверочных символов заканчивается и ключ Κ1 снова переводится в положение 1.

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

Пример 6.17. Рассмотрим процесс формирования кодовой комбинации с использованием генераторного многочлена для случая g(x) = = х³ + х² + 1 и а(х) = =х³+1

Определяем генераторный многочлен.

Соответствующая h(x) схема кодирующего устройства приведена на рис. 6.17. Формирование кодовой комбинации поясняется табл. 6.16. Оно начинается после заполнения регистра информационными символами.

Таблица 6.16

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

Рассмотрим сначала устройства декодирования, в которых для обнаружения и исправления ошибок производится деление произвольного многочлена f(x), соответствующего принятой комбинации, на образующий многочлен кода go(x). В этом случае при декодировании могут использоваться те же регистры сдвига, что и при кодировании.

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

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

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

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

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

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

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

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

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

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

В качестве схем деления в декодирующем устройстве могут быть использованы как схемы, определяющие остаток за n тактов (см. рис. 6.12), так и схемы, определяющие остаток за k тактов (рис. 6.14). При использовании схемы деления за k тактов векторам одиночных ошибок ξ(x) будут соответствовать другие остатки на n-м такте, являющиеся результатом деления на образующий многочлен кода векторов ξ(x)x^m, а не ξ(x). Поэтому выделенные синдромы, а следовательно, и детекторы ошибок для указанных схем будут различны.

Пример 6.18. Рассмотрим процесс исправления единичной ошибки при использовании кода (7,4) с образующим многочленом g(x) = х³ + x² + 1 и применении в декодирующем устройстве схем деления за n и k тактов.

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

Поиск по сайту: