технические средства кодирования и декодирования циклических кодов

§ 6.8 Технические средства кодирования и декодирования для циклических кодов

Линейные переключательные схемы.Основу кодирующих и декодирующих устройств циклических кодов составляют регистры сдвига с обратными связями, позволяющие осуществлять как умножение, так и деление многочленов с приведением коэффициентов по модулю два. Такие регистры также называют многотактными линейными переключательными схемами и линейными кодовыми фильтрами Хаффмена. Они состоят из ячеек памяти, сумматоров по модулю два и устройств умножения на коэффициенты многочленов множителя или делителя. В случае двоичных кодов для умножения на коэффициент, равный 1, требуется только наличие связи в схеме. Если коэффициент равен 0, то связь отсутствует. Сдвиг информации в регистре осуществляется импульсами, поступающими с генератора продвигающих импульсов, который на схеме, как правило, не указывается. На вход устройств поступают только коэффициенты многочленов, причем начиная с коэффициента при переменной в старшей степени.

Предполагаем, что первоначально ячейки памяти находятся в нулевом состоянии и что за коэффициентами множимого следует n — k нулей.

На первом такте на вход схемы поступает первый коэффициент a_k-1 многочлена а(х) и на выходе появляется первый коэффициент произведения, равный а_k-1,g_n—k. На следующем такте на выход поступит сумма a_k-2 g_n—k+a_k-1g_n—k-1, т.е. второй коэффициент произведения, и т. д. На n-м такте все ячейки, кроме последней, будут в нулевом состоянии и на выходе получим последний коэффициент a₀g₀.

Используется также схема умножения многочленов при поступлении множимого младшим разрядом вперед (рис. 6.11).

За первые n — k тактов коэффициенты многочлена-делимого заполняют регистр, причем коэффициент при x в старшей степени достигает крайней правой ячейки. На следующем такте «единица» делимого, выходящая из крайней ячейки регистра, по цепи обратной связи подается к сумматорам по модулю два, что равносильно вычитанию многочлена-делителя из многочлена-делимого. Если в результате предыдущей операции коэффициент при старшей степени x у остатка оказался равным нулю, то на следующем такте делитель не вычитается. Коэффициенты делимого только сдвигаются вперед по регистру на один разряд, что находится в полном соответствии с тем, как это делается при делении многочленов столбиком.

Деление заканчивается с приходом последнего символа многочлена-делимого. При этом разность будет иметь более низкую степень, чем делитель. Эта разность и есть остаток.

Отметим, что если в качестве многочлена-делителя выбран простой многочлен степени m = n — k, то, продолжая делить образовавшийся остаток при отключенном входе, будем получать в регистре по одному разу каждое из ненулевых m-разрядных двоичных чисел. Затем эта последовательность чисел повторяется.

Пример 6.15. Рассмотрим процесс деления многочлена а(х)х m = (x^3+1)x^3 на образующий многочлен g(x) = x^3 + + x^2 + 1. Схема для этого случая представлена на рис. 6.13, где 1, 2, 3 — ячейки регистра. Работа схемы поясняется табл. 6.14.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Источник

Процедура кодирования и декодирования для циклических кодов

Кодирующие и декодирующие устройства циклических кодов

Преобразование комбинации первичного k – разрядного кода в комбинацию циклического (n, k) – кода может быть осуществлено либо при помощи порождающего многочлена g(x), либо при помощи проверочного многочлена h(x).

а) Процедура кодирования для циклического кода по g(x).

Любой циклический (n, k) – код может быть получен в результате следующего процесса. Пусть — многочлен степени n-1, в качестве коэффициентов которого при степенях выбраны информационные символы кодовой комбинации циклического (n, k) – кода, а коэффициенты при степенях х, меньших, чем n—k, равны 0. Тогда результат деления на порождающий многочлен кода g(x), степень которого, как известно, равна n—k, может быть представлен в виде

,

Образуем новый многочлен , у которого коэффициенты при степенях х, меньших n—k, есть соответствующие коэффициенты r(x), а коэффициенты при остальных степенях есть соответствующие коэффициенты .

Для полученного многочлена справедливо

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

В векторе коэффициентами при степенях х, равных n—k и старше, являются информационные элементы кодовой комбинации, а коэффициентами при младших степенях – проверочные (см. рис. 6.0).

Таким образом, для формирования кодовой комбинации циклического (n, k) – кода по данному способу требуется иметь устройство для умножения комбинации первичного кода, представляемой многочленом степени не старшей k-1, на , деления, полученного в результате умножения многочлена степени не старшей n-1 на порождающий многочлен циклического кода g(x) степени n—k и вычисления остатка от этого деления степени n—k-1 и менее.

В комбинации циклического (n, k) – кода коэффициенты многочлена (n, k) – кода являются информационными разрядами, а коэффициенты многочлена — избыточными.

б) Процедура кодирования для циклического кода по h(x).

Для проверочного многочлена h(x) степени k циклического (n, k) – кода справедливо или .

Так как по определению 2 любая кодовая комбинация кратна g(x), то для произвольной комбинации f(x) выполняется .

Если принять , то, учитывая, что степень h(x) равна k, а степень f(x) равна n-1, для коэффициента С_с можно составить соотношение:

.

Учитывая, что находим

Итак, если известны коэффициенты , т.е. информационные элементы кодовой комбинации циклического (n, k) – кода, то при помощи систем рекуррентных соотношений, полученных выше, можно найти значение избыточных элементов Таким образом, для кодирования по проверочному многочлену необходимо иметь устройство для решения рекуррентных соотношений типа

в) Процедура декодирования для циклических кодов

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

.

Если остаток от деления r(x)=0, то считают, что комбинация f(x) и была передана.

В этом случае k коэффициентов отдаются потребителю в качестве переданного сообщения.

Если же остаток от деления , то принятая комбинация f(x) признается запрещенной и в зависимости от логики работы УЗО потребителю выдается сигнал наличия ошибки в принятой информации или организуется исправление ошибок. При исправлении по виду остатка r(x) отыскивается смежный класс, которому принадлежит принятая комбинация и определяется наиболее вероятный образец ошибки. Элементы, в которых предполагаются ошибки, инвертируются, и информационные разряды комбинации отдаются потребителям. Покажем, что остаток от деления r(x) тождественен синдрому в общепринятом определении . Как было показано в разделе 6.3 (пример 6.6) столбцами проверочной матрицы являются остатки от деления на порождающий многочлен g(x).

Пример 6.13. Определить принадлежность комбинации циклическому (7,4) – коду с

1 0 0

Найдем остаток от деления многочлена на

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

Итак, мы установили существование двух способов вычисления синдрома для кодовых комбинаций. При этом второй способ отражает специфику представления кодовой комбинации в виде многочлена. Возможен ещё и третий способ вычисления синдрома, также вытекающий из представления кодовых комбинаций многочленами. Каждая кодовая комбинация циклического (n,k) кода кратна порождающему многочлену g(x) степени n-k. Это в свою очередь означает, что любая кодовая комбинация имеет среди своих корней n-k корней порождающего многочлена. Значит принадлежность принятой комбинации f(x) к используемому коду можно определить подстановкой вместо формальной переменной x в принятой комбинации корней порождающего многочлена g(x).

Пусть – α i – корень порождающего многочлена (n,k)–кода, а f(x) – кодовая комбинация этого кода, тогда должно быть справедливо: f(x=α i )=0 для всех значений i, определяющих корни g(x).

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

Пусть передана комбинация f(x), а принята комбинация f'(x)=f(x)+e(x), где e(x) – многочлен ошибок. Тогда f'(x=α i )=f(x=α i )+e(x=α i )=e(x=α i )=S_i

2.Если e(x) по виду совпадает с одной из кодовых комбинаций, то S_i=e(x=α i )=0,

т.е. имеет место нулевой синдром, который приведёт к необнаруженной ошибке. Если же e(x) отличается от кодовой комбинации, то синдром будет ненулевым: S_i=e(x=α i )≠0 и ошибка будет выявлена.

Пример 6.13. (продолжение)

Покажем, что нахождение синдрома для проверки принадлежности комбинации f(x)=1+x+x 2 +x 3 +x 6 =1111001 циклическому(7,4) – коду с g(x) = 1+x+x 3 может быть осуществлено подстановкой корней многочлена g(x) вместо x в f(x).

Для этого обратимся к процедуре к процедуре умножения:

Обратим внимание, что матрица H T (7,4)- кода в точности соответствует представлению элементов GF(2 3 ) в виде ненулевых векторов в таблице задачи 6 раздела 5.8. Это не случайное совпадение. Обе эти совокупности двоичных последовательностей длины 3 получены как классы вычетов многочленов по модулю одного и того же многочлена 3-ей степени и отображают одну и ту же циклическую группу.

При этом процедура замены в проверяемом многочлене x i на α i и последующего суммирования результатов замены полностью эквивалентна сложению строк матрицы H T соответствующим «1» в двоичном представлении многочлена.

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

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

Источник