Линейные переключательные схемы
Технические средства кодирования
Основу кодирующих и декодирующих устройств циклических кодов составляют регистры сдвига с обратными связями, позволяющие осуществлять как умножение, так и деление многочленов с приведением коэффициентов по модулю два. Такие регистры также называют многотактными линейными переключательными схемами и линейными кодовыми фильтрами Хаффмена. Они состоят из ячеек памяти, сумматоров по модулю два и устройств умножения на коэффициенты многочленов множителя или делителя. В случае двоичных кодов для умножения на коэффициент, равный 1, требуется только наличие связи в схеме. Если коэффициент равен 0, то связь отсутствует. Сдвиг информации в регистре осуществляется импульсами, поступающими с генератора продвигающих импульсов, который на схеме, как правило, не указывается. На вход устройств поступают только коэффициенты многочленов, причем начиная с коэффициента при переменной в старшей степени.
Рис. 4.9.
На рис. 4.9 представлена схема, выполняющая умножение произвольного (например, информационного) многочлена
a(x) = a0 + a1x + … + ak-1xk-1
на некоторый фиксированный (например, образующий) многочлен
g(x) = g0 + g1x + … + gn-kxn-k.
Произведение этих многочленов равно
a(x)g(x)=a0g0 + (a0g1 + a1g0)x + … +(ak-2gn-k + ak-1gn-k-1)xn-2 +ak-1gn-kxn-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-разрядных двоичных чисел. Затем эта последовательность чисел повторяется.
Рассмотренные выше схемы умножения и деления многочленов непосредственно в том виде, в каком они представлены на рис. 4.10, 4.11, в качестве кодирующих устройств циклических кодов на практике не применяются: первая - из-за того, что образующаяся кодовая комбинация в явном виде не содержит информационных символов, а вторая - из-за того, что между информационными и проверочными символами образуется разрыв в n - k разрядов.
Кодирующие устройства
Все известные кодирующие устройства для любых типов циклических кодов, выполненные на регистрах сдвига, можно свести к двум типам схем согласно рассмотренным ранее методам кодирования.
Таблица 4.16.
Номер такта
| Вход
| Состояние ячеек регистра
| Номер такта
| Вход
| Состояние ячеек регистра
|
|
|
|
|
|
|
|
|
|
|
|
| -
-
-
-
-
-
-
|
|
|
|
Схемы первого типа вычисляют значения проверочных символов путем непосредственного деления многочлена а(х)хт на образующий многочлен g(x). Это делается с помощью регистра сдвига, содержащего n-k разрядов (рис. 4.13).
Рис. 4.13.
Схема отличается от ранее рассмотренной тем, что коэффициенты кодируемого многочлена участвуют в обратной связи не через n-k сдвигов, а сразу с первого такта. Это позволяет устранить разрыв между информационными и проверочными символами.
В исходном состоянии ключ К1 находится в положении 1. Информационные символы одновременно поступают как в линию связи, так и в регистр сдвига, где за k тактов образуется остаток. Затем ключ K1 переходит в положение 2 и остаток поступает в линию связи.
Схема кодирующего устройства для заданного g(x) приведена на рис. 4.14. Процесс формирования кодовой комбинации шаг за шагом представлен в табл. 4.17, где черточками отмечены освобождающиеся ячейки, занимаемые новыми информационными символами.
С помощью схем второго типа вычисляют значения проверочных символов как линейную комбинацию информационных символов, т. е. они построены на использовании основного свойства систематических кодов. Кодирующее устройство строится на основе k-разрядного регистра сдвига (рис. 4.15).
Рис. 4.14.
Таблица 4.17.
Номер такта
| Вход
| Состояние ячеек регистра
| Выход
|
|
|
|
|
|
-
-
-
|
-
-
|
-
|
|
Выходы ячеек памяти подключаются к сумматору в цепи обратной связи в соответствии с видом генераторного многочлена
h(x) = (xn + 1)/g(x) = h0 + h1x + … + hkxk
В исходном положении ключ К1 находится в положении 1. За первые k тактов поступающие на вход информационные символы заполняют все ячейки регистра. После этого ключ переводят в положение 2. На каждом из последующих тактов один из информационных символов выдается в канал связи и одновременно формируется проверочный символ, который записывается в последнюю ячейку регистра. Через n-k тактов процесс формирования проверочных символов заканчивается и ключ K1 снова переводится в положение 1.
В течение последующих k тактов содержимое регистра выдается в канал связи с одновременным заполнением ячеек новой последовательности информационных символов.
Не нашли, что искали? Воспользуйтесь поиском по сайту:
©2015 - 2024 stydopedia.ru Все материалы защищены законодательством РФ.
|