Технические средства кодирования и декодирования для циклических кодов
Основу кодирующих и декодирующих устройств циклических кодов составляют регистры сдвига с обратными связями, позволяющие осуществлять как умножение, так и деление многочленов с приведением коэффициентов по модулю два. Такие регистры также называют многотактными линейными переключательными схемами и линейными кодовыми фильтрами Хаффмена. Они состоят из ячеек памяти, сумматоров по модулю два и устройств умножения на коэффициенты многочленов множителя или делителя. В случае двоичных кодов для умножения на коэффициент, равный 1, требуется только наличие связи в схеме. Если коэффициент равен 0, то связь отсутствует. Сдвиг информации в регистре осуществляется импульсами, поступающими с генератора продвигающих импульсов, который на схеме, как правило, не указывается. На вход устройств поступают только коэффициенты многочленов, причем начиная с коэффициента при переменной в старшей степени.
Рис. 4.9.
На рис. 4.9 представлена схема, выполняющая умножение произвольного (например, информационного) многочлена
a(x) = a0 + a1x + … + ak-1xk-1
на некоторый фиксированный (например, образующий) многочлен
Предполагаем, что первоначально ячейки памяти находятся в нулевом состоянии и что за коэффициентами множимого следует n-k нулей.
На первом такте на вход схемы поступает первый коэффициент аk-1 многочлена а(х) и на выходе появляется первый коэффициент произведения, равный
ak-1gn-k
На следующем такте на выход поступит сумма
ak-2gn-k + ak-1gn-k-1 ,
т.е. второй коэффициент произведения, и т. д. На n-м такте все ячейки, кроме последней, будут в нулевом состоянии и на выходе получим последний коэффициент а0g0
Используется также схема умножения многочленов при поступлении множимого младшим разрядом вперед (рис. 4.10).
На рис. 4.11 представлена схема, выполняющая деление произвольного многочлена, например
a(x)xm = a0 + a1x + … + an-1xn-1
на некоторый фиксированный (например, образующий) многочлен
g(x) = g0 + g1x + … + gn-kxn-k
Обратные связи регистра соответствуют виду многочлена g(x). Количество включаемых в него сумматоров равно числу отличных от нуля коэффициентов g(x), уменьшенному на единицу. Это объясняется тем, что сумматор сложения коэффициентов старших разрядов многочленов делимого и делителя в регистр не включается, так как результат сложения заранее известен (он равен 0).
Рис. 4.10.
Рис. 4.11.
За первые n-k тактов коэффициенты многочлена-делимого заполняют регистр, причем коэффициент при х в старшей степени достигает крайней правой ячейки. На следующем такте «единица» делимого, выходящая из крайней ячейки регистра, по цепи обратной связи подается к сумматорам по модулю два, что равносильно вычитанию многочлена-делителя из многочлена-делимого. Если в результате предыдущей операции коэффициент при старшей степени х уостатка оказался равным нулю, то на следующем такте делитель не вычитается. Коэффициенты делимого только сдвигаются вперед по регистру на один разряд, что находится в полном соответствии с тем, как это делается при делении многочленов столбиком.
Деление заканчивается с приходом последнего символа многочлена-делимого. При этом разность будет иметь более низкую степень, чем делитель. Эта разность и есть остаток.
Отметим, что если в качестве многочлена-делителя выбран простой многочлен степени m = n-k, то, продолжая делить образовавшийся остаток при отключенном входе, будем получать в регистре по одному разу каждое из ненулевых m-разрядных двоичных чисел. Затем эта последовательность чисел повторяется.
Пример 37.Рассмотрим процесс деления многочлена а(х)хт =(x3+1)x3 на образующий многочлен g(x) = х3+ х2+1. Схема для этого случая представлена на рис. 4.12, где 1, 2, 3-ячейки регистра. Работа схемы поясняется табл. 4.16.
Рис. 4.12.
Вычисление остатка начинается с четвертого такта и заканчивается после седьмого такта. Последующие сдвиги приводят к образованию в регистре последовательности из семи различных ненулевых трехразрядных чисел. В дальнейшем эта последовательность чисел повторяется.
Рассмотренные выше схемы умножения и деления многочленов непосредственно в том виде, в каком они представлены на рис. 4.10, 4.11, в качестве кодирующих устройств циклических кодов на практике не применяются: первая - из-за того, что образующаяся кодовая комбинация в явном виде не содержит информационных символов, а вторая - из-за того, что между информационными и проверочными символами образуется разрыв в n - k разрядов.
