Теория информации (стр. 28 из 29)
Используется также схема умножения многочленов при поступлении множимого младшим разрядом вперед (рис. 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разрядов.
4.11.2 Кодирующие устройства
Все известные кодирующие устройства для любых типов циклических кодов, выполненные на регистрах сдвига, можно свести к двум типам схем согласно рассмотренным ранее методам кодирования.
Таблица 4.16.
| Номер такта | Вход | Состояние ячеек регистра | Номер такта | Вход | Состояние ячеек регистра | ||||
| 1 | 2 | 3 | 1 | 2 | 3 | ||||
| 1234567 | 1001000 | 1000111 | 0100011 | 0011110 | 891011121314 | ------- | 0100111 | 1010011 | 1001110 |
Схемы первого типа вычисляют значения проверочных символов путем непосредственного деления многочлена а(х)хтна образующий многочлен g(x). Это делается с помощью регистра сдвига, содержащего n-kразрядов (рис. 4.13).
Рис. 4.13.
Схема отличается от ранее рассмотренной тем, что коэффициенты кодируемого многочлена участвуют в обратной связи не через n-kсдвигов, а сразу с первого такта. Это позволяет устранить разрыв между информационными и проверочными символами.
В исходном состоянии ключ К1находится в положении 1. Информационные символы одновременно поступают как в линию связи, так и в регистр сдвига, где за kтактов образуется остаток. Затем ключ K1переходит в положение 2 и остаток поступает в линию связи.
Пример 38.Рассмотрим процесс деления многочлена а(х)хт = (х3 + 1)x3 на многочлен g(x) = x3 + х2+ 1 за k тактов.
Схема кодирующего устройства для заданного g(x) приведена на рис. 4.14. Процесс формирования кодовой комбинации шаг за шагом представлен в табл. 4.17, где черточками отмечены освобождающиеся ячейки, занимаемые новыми информационными символами.
С помощью схем второго типа вычисляют значения проверочных символов как линейную комбинацию информационных символов, т. е. они построены на использовании основного свойства систематических кодов. Кодирующее устройство строится на основе k-разрядного регистра сдвига (рис. 4.15).
Рис. 4.14.
Таблица 4.17.
| Номер такта | Вход | Состояние ячеек регистра | Выход | ||
| 1 | 2 | 3 | |||
| 1234567 | 1001000 | 1111--- | 01111-- | 110011- | 1010011001010011010011101001 |
Выходы ячеек памяти подключаются к сумматору в цепи обратной связи в соответствии с видом генераторного многочлена
h(x) = (xn + 1)/g(x) = h0 + h1x + … + hkxk
В исходном положении ключ К1находится в положении 1. За первые kтактов поступающие на вход информационные символы заполняют все ячейки регистра. После этого ключ переводят в положение 2. На каждом из последующих тактов один из информационных символов выдается в канал связи и одновременно формируется проверочный символ, который записывается в последнюю ячейку регистра. Через n-kтактов процесс формирования проверочных символов заканчивается и ключ K1 снова переводится в положение 1.
В течение последующих kтактов содержимое регистра выдается в канал связи с одновременным заполнением ячеек новой последовательности информационных символов.
Пример 39.Рассмотрим процесс формирования кодовой комбинации с использованием генераторного многочлена для случая g(x) = x3 + x2 + 1 и а(x) = x3 + 1.
Определяем генераторный многочлен:
Рис. 4.15.
Рис. 4.16.
Соответствующая h(x) схема кодирующего устройства приведена на рис. 4.16. Формирование кодовой комбинации поясняется табл. 4.18. Оно начинается после заполнения регистра информационными символами.
4.11.3 Декодирующие устройства
Декодирование комбинаций циклического кода можно проводить различными методами. Существуют методы, основанные на использовании рекуррентных соотношений, на мажоритарном принципе, на вычислении остатка от деления принятой комбинации на образующий многочлен кода и др. Целесообразность применения каждого из них зависит от конкретных характеристик используемого кода.
Рассмотрим сначала устройства декодирования, в которых для обнаружения и исправления ошибок производится деление произвольного многочлена f(x), соответствующего принятой комбинации, на образующий многочлен кода g0(x). В этом случае при декодировании могут использоваться те же регистры сдвига, что и при кодировании.
Таблица 4.18.
| Номер такта | Состояние ячеек регистра | Выход | |||
| 1 | 2 | 3 | 4 | ||
| 1234567 | 1011--- | 01011--- | 001011-- | 1001011- | 1010011001010011010011101001 |
Рис. 4.17.
Декодирующие устройства для кодов, обнаруживающих ошибки, по существу ничем не отличаются от схем кодирующих устройств. В них добавляется лишь буферный регистр для хранения принятого сообщения на время проведения операции деления. Если остатка не обнаружено (случай отсутствия ошибки), то информация с буферного регистра считывается в дешифратор сообщения. Если остаток обнаружен (случай наличия ошибки), то информация в буферном регистре уничтожается и на передающую сторону посылается импульс запроса повторной передачи.
В случае исправления ошибок схема несколько усложняется. Информацию о разрядах, в которых произошла ошибка, несет, как и ранее, остаток. Схема декодирующего устройства представлена на рис. 4.17.
Символы подлежащей декодированию кодовой комбинации, возможно, содержащей ошибку, последовательно, начиная со старшего разряда, вводятся в n-разрядный буферный регистр сдвига и одновременно в схему деления, где за n тактов определяется остаток, который в случае непрерывной передачи сразу же переписывается в регистр второй аналогичной схемы деления.