Циклические коды составляют большую группу наиболее широко используемых на
 Скачать 201 Kb.
|
0111001, принимаемой без ошибок. Декодирующее устройство работает
1001. Учитывая наличие обратной связи в СР с g задержки (D-триггером). Устройства задержки, включенные последовательно, составляют сдвигающий регистр (СР), в ячейках которого выходной символ совпадает с входным символом в предшествующий момент времени. К СР подводится шина сдвига, с помощью которой тактовыми импульсами (ТИ) осуществляется продвижение по разрядам СР записанной кодовой информации. Как правило, шина сдвига не показывается на схемах с изображениями ЛПС. При формировании и обработке двоичных ЦК введение в схему ЛПС умножителя на константу, равную 1, эквивалентно введению дополнительного соединения, а умножитель на константу, равную 0, соответствует отсутствию такого соединения. Предполагается, что на вход СР, входящего в состав ЛПС, кодовая комбинация подается последовательно, с периодичностью, равной периоду следования ТИ в шине сдвига. Аналогично, последовательно во времени, появляются кодовые символы на выходе СР. Когда входом или выходом является многочлен, представляющий при двоичной обработке набор «1» и «0», то на входном или выходном конце СР появляются только коэффициенты («1» или «0»), начиная с коэффициентов высших порядков. Это обусловливается тем, что при делении у делителя сначала должны быть обработаны коэффициенты высших порядков. 1.5.6. УМНОЖЕНИЕ ПОЛИНОМОВ НА БАЗЕ ЛПС Схема, изображенная на рис. 1.5, используется для умножения любого полинома на входе A(X) = a0 + a1 X + a2 X 2 + … + ak X k на фиксированный полином, в частности, порождающий: G(X) = g0 + g1 X + g2 X2 + … + gm X m . Предполагается, что первоначально все разряды СР содержат нули, а на вход коэффициенты полинома А(Х) поступают, начиная с коэффициентов высших порядков (со старших разрядов), после чего следует m нулей. OUT gr gr-1 gr-2 gr-3 g1 g0 . . . . . . IN Рис. 1.5. Первый вариант схемы умножителя полиномов Произведение полиномов A(X)G(X) = a0 g0 + (ao g1 + a1 g0)X + ... + akgmX k+m . (1.37) Когда на входе ЛПС появляется первый (старший) коэффициент полинома А(Х), то он умножится в первом устройстве умножения на gr и появится на выходе уже как результат перемножения akgr , проследовав «транзитом» через все схемы суммирования «по модулю 2». Кроме того, ak запишется в первом разряде СР, а все остальные разряды СР будут содержать нули. Спустя единицу времени, с появлением в шине сдвига 2-го ТИ, на входе появится ak-1, который перемножается с gm и сложится в первой схеме суммирования «по модулю 2» с akgr–1, сформировав на выходе сумму ak–1gr + akgr-1, т. е. второй коэффициент произведения A(X)G(X). Дальнейшие операции производятся аналогичным образом. После m + k сдвигов СР полностью обнуляется и на выходе появляется значение a0g0, равное первому коэффициенту произведения (1.43), так что произведение на выходе ЛПС последовательно получается в полном составе. Второй вариант ЛПС для умножения полиномов показан на рис. 1.6. Коэффициенты произведения формируются непосредственно в СР. После того, как первый символ подается на вход, на выходе появляется последний коэффициент (1.37) ak gm , а разряды СР содержат только нули. После одного сдвига ячейки СР содержат элементы ak g0, ak g1, ..., ak gm-1, a вход равен ak-1. При этом выход СР равен ak gm-1 + ak-1 gm, т. е. равен второму коэффициенту (1.37). После появления очередного ТИ в шине сдвига (не показана на рис. 1.5 и 1.6) на выходе появляется третий коэффициент (1.37). Дальнейшие операции производятся аналогичным образом. Схемы умножения могут иметь более чем один вход, если добавить к ЛПС, изображенной на рис. 1.7, вторую шину с цепочкой устройств умножения, связанных с соответствующими схемами суммирования «по модулю 2». Тогда схема будет реализовывать процедуру суммирования произведений двух пар полиномов C(X) = A1(X) G1(X) + A2(X)G2(X) , (1.38) причем ЗУ в виде СР – только одно. 1.5.7. ДЕЛЕНИЕ ПОЛИНОМОВ НА БАЗЕ ЛПС OUT g0 g1 g2 gr-2 gr-1 gr IN … … Рис. 1.6. Второй вариант схемы умножителя полиномов Схема для деления полинома A(X) = a0 + a1 X + a2 X 2 + … + ak X k на полином G(X) = g0 + g1 X + g2 X 2 + … + gm X m показана на рис. 1.8. Динамическое ЗУ в виде СР вначале должно содержать все нули. Для деления полиномов СР охвачен обратной связью, т. е. выход СР соединяется с входом. Для подчеркивания противоположного направления шины обратной связи коэффициент умножителя обозначается как gm–1. Однако для двоичных кодов результат умножения и деления на единицу одинаков, поэтому указанное обозначение в дальнейшем использоваться не будет. Первый вариант ЛПС для деления полиномов (рис. 1.7). Для первых m-сдвигов, т. е. до тех пор, пока первый входной символ не достигнет конца PC, выход принимает значения, равные «0». После этого на выходе появляется первый ненулевой выход, который равен akgm–1 – первому коэффициенту частного. Для каждого коэффициента частного gj необходимо вычесть из делимого полином G(X). Это вычитание производится с помощью обратной связи. После k сдвигов на выходе появится частное от деления, а остаток от деления будет находиться в СР. Работу схемы легче всего понять с помощью примеров построения КУ и ДКУ на базе ЛПС, рассматриваемых далее в разд. 1.5.8. Второй вариант ЛПС с делением на генераторный полином (рис. 1.8). При построении КУ ЦК, а также генераторов различных кодовых последовательностей, в частности, последовательностей максимальной длины (М- последовательностей), применяется в ряде случаев так называемый генераторный полином Н(Х). Этот полином называют также проверочным, если он получается при делении бинома 1 n + X на порождающий полином G(X): 1 ( ) . ( ) n X H X G X + = (1.39) -g0 -g1 -g2 -gr-2 -gr-1 gr -1 IN … OUT … Рис. 1.7. Первый вариант схемы делителя на генераторный полином При использовании этой схемы в качестве КУ ЦК, исходную кодовую комбинацию А(Х) параллельно и одновременно записывают в k разрядов СР. С первым тактом на выход будет выдан коэффициент bn – 1 = ak – 1, произойдет сдвиг вправо в СР, и в освободившуюся ячейку памяти будет записано вычисленное значение проверочного бита mn – k – 1 = h0 ak – 1 + h1 ak – 2 + ... + hk – 1 a0. Со вторым тактом на выход будет считан коэффициент bn – 2 = ak – 2, произойдет сдвиг, и в освободившуюся первую ячейку СР запишется второй проверочный бит mn – k – 2 = h0 ak – 2 + h1 ak – 3 + ... + hk – 1 mn –k – 1. Чеpез n – k тактов будут вычислены все n – k проверочных символов r0, r1, …, mn – k – 1 и записаны в СР. После k тактов, т. е. после вывода на выход всех информационных символов, станут выводиться проверочные символы в том же порядке, в каком они вычислялись. На выходе получается блочный код. После k тактов процесс кодирования одной комбинации Аi(Х) заканчивается, и СР принимает исходное состояние. Для кодирования следующей комбинации необходимо стереть Аi(Х), ввести в СР новую Аj(Х) и повторить цикл из n тактов. Рассмотрим более конкретно работу этой схемы на примере использования ее в качестве КУ с привязкой начальных условий к данным предыдущих примеров. Пример Построить схему КУ, обеспечивающего кодирование ЦК Хемминга (7,4) с порождающим полиномом G(X) = 1 + X + Х 2 путем вычисления блока проверочных символов «в целом», используя проверочный полином Н(Х). Проследить по тактам процесс кодирования и состояние элементов схемы при кодировании исходной комбинации 1001 выхода на вход, суммирование «по модулю 2» выходов ячеек Х 1 , Х 2 и X 3 даст символ записи в ячейку Х 0 . После первого сдвига в Х 0 будет записан символ проверочной группы r1, который при последующих сдвигах продефилирует на выход СР. Из табл.1.6 видно, что после n = 7 тактов на выходе образуется комбинация 0111001 (старшим разрядом вперед). При этом триггерные ячейки СР принимают исходное значение 1001, и при необходимости возможно повторение процедуры кодирования этой же кодовой комбинации Ai(X) путем подачи очередных следующих n = 7 тактов. Таким образом, этот способ кодирования так же, как и первый вариант схемы для деления полиномов, обеспечивает получение кодовых комбинаций разделимого, блочного ЦК. Рассмотрение вариантов построения ЛПС, выполняющих операции умножения и деления полиномов, с целью использования в кодеках ЦК, позволяет сделать следующие выводы: 1) В КУ ЦК процедура умножения полиномов приводит к получению неразделимых кодов, что усложняет их последующее декодирование. Поэтому операция умножения редко используется в устройствах формирования и обработки ЦК. 2) При делении на порождающий полином G(X) код на выходе КУ получается разделимым и СР содержит r разрядов. Так как в большинстве случаев используются ЦК, у которых число проверочных символов r существенно меньше числа информационных (m < k), то СР в этом случае будет иметь меньшее число разрядов, чем при делении на генераторный полином. Таблица 1.6. Состояния КУ Номер такта Состояния ячеек Выход X 0 X 1 X 2 X 3 A(X) 1 0 0 1 − 1 1 1 0 0 1 2 1 1 1 0 0 3 0 1 1 1 0 4 1 0 1 1 1 5 0 1 0 1 1 6 0 0 1 0 1 7 1 0 0 1 0 OUT X 0 X 1 X 2 X 3 h4=1 h3=0 h2=1 h1=1 h0=1 a0=1 a1=0 a2=0 a3=1 Bi(X) Ai(X) 3) При делении в КУ исходной кодовой комбинации на генераторный многочлен ЦК также получается разделимым, но в СР требуется использовать не m, а k разрядов, которых, как правило, больше. 1.5.8. КОДИРУЮЩЕЕ И ДЕКОДИРУЮЩЕЕ УСТРОЙСТВО ДЛЯ КОДА ХЕММИНГА (7, 4) Покажем, как реализуются схемы с учетом того, что коды Хемминга относятся и к классу ЦК. Кодер для кода Хемминга (7,4). Для построения КУ по классической схеме деления (см. рис. 1.7), так как кодирование путем вычисления остатка «в целом» требует предварительного выполнения операции умножения на оператор сдвига m X и сложения полинома – остатка с полиномом – произведением ( ) m A X X i (1.29), требуется предварительно видоизменить структуру схемы. Для выполнения операции умножения следует разместить сумматор, на который подключен вход, в конце СР, перед обратной связью m 1 g − . Такое подключение входа эквивалентно умножению на m X , так как исключается задержка на m ТИ. Для выполнения операции сложения остатка Ri(X) с полиномом Ai(X)X m (1.29) необходимо выход КУ подключить к одному из входов схемы логического сложения (ИЛИ), ко второму входу которой подключается вход схемы для выдачи на выход без задержки информационной кодовой комбинации Ai(X) (старшим разрядом вперед). Подробнее рассмотрим работу схемы на конкретном примере. Пример Построить схему КУ, обеспечивающего кодирование ЦК (7,4) с порождающим полиномом G(X) = 1 + X + X 3 путем определения проверочной группы методом деления полиномов и определения остатка R(X). Проследить по тактам процесс кодирования и состояние элементов схемы при кодировании исходного полинома 3 ( ) 1 1001. A X X i = + X 0 X 1 X 2 AND2 AND2 OR2 Ai(X) Bi(X) (1-4)TИ (5-7)TИ IN OUT DD1 DD2 g0=1 g1=1 g2=0 g3=1 Рис. 1.10. Схема кодера для (7,4)-кода Хемминга.Схема кодера для условий примера изображена на рис. 1.10, состояние ячеек СР и выхода схемы по тактам — в табл. 1.7. Наряду с особенностями построения схемы, КУ дополнено двумя ключевыми схемами, роль которых выполняют схемы логического умножения DD1 и DD2 соответственно. В течение первых k = 4 тактов на второй вход схемы DD1 поступают ТИ, обеспечивая прохождение символов от выходного сумматора в шину обратной связи СР. Начиная с 5-го по 7-й такт, ТИ на второй вход схемы DD1 не поступают, и обратная связь разрывается. В это время поступают ТИ на второй вход схемы DD2, благодаря чему выход СР подключается к выходу всего КУ, обеспечивая выдачу остатка от деления кодовой комбинации Ai (X) на порождающий полином G(X) на выход, для подстыковки проверочных символов к Ai(X). Из табл.1.7 видно, что после 4-го такта в СР образуется остаток 011, т. е. 2 R X X X ( ) = + , а в течение n тактов на выход поступает кодовая комбинация 2 3 6 0111001 |