ГЕНЕРАТОР ЛОКАТОРОВ ПОЛЯ ГАЛУА GF(Q*99M) Российский патент 1998 года по МПК H03M13/02 

Изобретение относится к вычислительной технике, в частности к выполнению операции в полях Галуа, например, в устройствах декодирования кодов Рида-Соломона и БЧХ.

Известны способы и устройства определения локаторов при декодировании кодов Рида-Соломона (Блейхут Р., Теория и практика кодов, контролирующих ошибки, M.: Мир, 1986; Питерсон У., Уэлдон Э., Коды, исправляющие ошибки. М.: Мир, 1976).

Наибольшее распространение получили устройства определения локаторов ошибок, выполненные на ПЗУ, в которой хранится таблица локаторов.

Существенным недостатком данных технических решений является большая аппаратная избыточность устройств, например, для кода GF(2⁸) требуется ПЗУ объемом 256х8 бит.

В различных устройствах декодирования используют две последовательности локаторов {αⁱ,αⁱ⁺¹, ... ,1} и {αⁱ⁺¹,αⁱ⁺², ... ,1} . Последняя последовательность эквивалентна следующей {α^q,α^q-1, ... ,1} (Кларк Дж., Кейн Дж., Кодирование с исправлением ошибок в системах цифровой связи, М.: Радио и связь, 1987). Последовательности локаторов образуются из мультипликативной группы поля GF(q^m), т.e. исключается нулевой элемент поля. Известен алгоритм генерации ненулевых элементов поля GF(2⁸) (Муттер В.М. и др., Микропроцессорные кодеры и декодеры, М.: Радио и связь, 1991, с. 21-22). Алгоритм является рекуррентным - комбинация, соответствующая элементу N , находится по комбинации с номером N - 1 за два шага:
а) умножение на x = α элемента поля в полиномиальном представлении, т.е. сдвиг двоичной комбинации (a_m-1, ... , a₁, a₀) влево, где a_i ∈ {0,1}, i=0, . .., m-1;
б) приведение полинома, полученного на предыдущем шаге, по модулю g(x) (g(x) - порождающий полином поля), т.е. сложение полученной комбинации с комбинацией, соответствующей полиному a_mg(x), где a_m - разряд переполнения.

m - разрядные комбинации (0...0) и (0...01) принимаются в качестве нулевого (N = 0) и единичного (N = 1) элементов.

Наиболее близким по техническому решению является устройство последовательного порождения ненулевых элементов поля GF(2⁸), реализуемое на двух регистрах и m - разрядных сумматорах по модулю 2. Вычисление элементов поля производится за 7 шагов алгоритма. Существенным недостатком данного технического решения является аппаратурная избыточность, низкое быстродействие и невозможность генерации всех допустимых последовательностей локаторов
{αⁱ,αⁱ⁺¹, ... ,1} и {αⁱ,α^i-1, ... ,1} .
Цель изобретения - упрощение, расширение области применения и повышение быстродействия устройства.

Поставленная цель достигается тем, что в известное устройство, содержащее регистр из m ячеек, сумматоры по модулю q, введены m-блоков начальной установки значения локаторов, (m+1+p) двунаправленных коммутаторов данных, p одноименных сумматоров по модулю q, причем связи выполнены так, что информационные входы блоков начальной установки являются группой информационных входов начальной установки значения локатора первого символа кодового слова, управляющие входы которых объединены и являются управляющим входом начальной установки устройства, выходы блоков начальной установки соединены с входами начальной установки ячеек регистра соответственно, группы информационных выходов m ячеек регистра являются группой информационных выходов устройства и соединены с первыми группами информационных входов коммутаторов с первого по m-й соответственно, выход m-й ячейки регистра дополнительно соединен с вторыми группами первого и второго коммутаторов данных, выходы коммутаторов данных с m-го по (m-k)-го соединены с информационными входами с m-й по (m-k)-й ячеек регистра соответственно, выходы коммутаторов данных с (m-k-p)-го по (m-k-p)-го соединены с информационными входами с (m-k-p)-й до первой ячеек регистра соответственно, выходы коммутаторов данных с (m- k)-го по (m-k-p)-й соединены с первыми входами сумматоров с первого по p-й соответственно, группа выходов первого сумматора соединена с первой группой (m+1)-го коммутатора данных и второй группой (m-k-1)-го коммутатора данных соответственно, группы выходов сумматоров с второго по p-й соединены с первыми группами входов с (m+2)-го коммутатора данных по (m+p-2)-го коммутатора данных соответственно и с вторыми входами коммутаторов данных с (m+1)-го до (m+p-1)-го соответственно, группы выходов с (m+1)-го до (m+p)-го коммутаторов данных соединены с информационными входами ячеек регистра с (m-k+1)-го до (m-k+p)-го соответственно, группа выходов первого коммутатора данных соединена с вторыми группами входов всех p одноименных сумматоров и с первой группой входов (m+p+1)-го коммутатора данных, группа выходов которого соединена с информационными входами m-й ячейки регистра, группа информационных выходов (m-1)-й ячейки дополнительно соединена с вторыми входами (m+p+1)-го коммутатора данных, группы информационных выходов ячеек регистра с (m-2)-й по (m-k)-ю дополнительно соединены с вторыми группами входов коммутаторов данных с m по (m-k-1)-го соответственно, группа информационных выходов (m-k-p-1)-го коммутатора данных дополнительна соединена с второй группой информационных входов (m+p)-го коммутатора данных, группы выходов ячеек регистра с (m-k-2)-й по первую дополнительно соединены с вторыми группами информационных входов коммутаторов данных с (m-k)-го по второй коммутатор данных соответственно, управляющие группы всех коммутаторов объединены и являются управляющим входом режима работы устройства, управляющие входы записи всех ячеек регистра объединены и являются управляющим входом сдвига регистра.

Сущность изобретения заключается в том, что операции умножения на элемент α^q и приведения по модулю порождающего полинома g(x) поля Галуа (GF2^m) совмещены по времени и выполняются за один такт сдвига влево регистра генератора локаторов для последовательности локаторов {αⁱ,αⁱ⁺¹, ... ,1} . Для последовательности локаторов {αⁱ,α^i-1, ... ,1} операция деления на элемент α^q и приведения по модулю модифицированного g_m(x) полинома также совмещены во времени и выполняются за один такт сдвига вправо регистра генераторов локаторов. Для реализации двух режимов с помощью управляющего входа задания режима происходит модификация обратных связей регистра.

Например, для поля GF(2⁸) с порождающим полиномом g(x) = x⁸ + x⁴ + x³ + x² + 1 = 435₈ - в восьмеричном представлении, тогда g_m(x) = 216₈ в восьмеричном представлении.

На фиг. 1 и 2 приведены структурные схемы регистров, генерирующих последовательности {αⁱ,α^i-1, ... ,1} и {αⁱ,αⁱ⁺¹, ... ,1} локаторов поля GF(2⁸).

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

Вначале в регистр генератора локаторов загружается значение αⁱ .

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

На фиг. 1 приведена структурная схема генератора локаторов для последовательностей {αⁱ,α^i-1, ... ,1} и {αⁱ,αⁱ⁺¹, ... ,1} на фиг. 2. Регистр содержит восемь ячеек (триггеров) 1...8 и 3 сумматора (СМ) по модулю m (m = 2) - 9, 10, 11.

На фиг. 3 приведен вариант выполнения генератора локаторов. На фиг. 4 и 5 приведены варианты выполнения ячеек регистров с блоками начальной установки значения αⁱ .

Предлагаемое устройство (генератор локаторов) (фиг. 3) содержит 8 ячеек (триггеров) 1...8, двунаправленные коммутаторы данных 9...20 (КМ), блоки начальной установки αⁱ - 21...28.

На фиг. 3 также показаны: 29...36 - группа информационных входов устройства для задания начального значения αⁱ ; 47 - первый управляющий вход начальной установки устройства; 46- второй управляющий вход сдвига регистра; 45 - третий управляющий вход задания режима работы устройства; 37...44 - группа информационных выходов значения локаторов устройства.

На фиг. 4 приведен вариант выполнения блока начальной загрузки и ячейки регистра, содержащий: 50 - D-триггер с установкой и сбросом; два элемента И-НЕ 48, 49. На фиг. 4 также показаны: 51 -информационный вход D_i начальной установки i-го бита регистра, 52 - информационный вход D-триггера регистра; 47 и 46 - управляющие входы, 53 - информационный выход i-го разряда локатора.

На фиг. 5 приведен вариант выполнения блока начальной загрузки и ячейки регистра, содержащий триггер-защелку 54, D-триггер ячейки регистра 50, элементы И-НЕ 48, 49. На фиг. 5 также показаны: 51, 52, 47, 46, 53 - входы и выход, аналогичные показанным на фиг. 3а; 55 - вход управления записью в триггер 54.

При реализации устройства могут быть применены микросхемы серий 133, 155, 555, 531. Наиболее эффективно выполнение устройства в интегральном исполнении.

Устройство работает следующим образом.

Рассмотрим вариант выполнения устройства для поля Галуа GF(2⁸) с порождающим полиномом g(x) = x⁸ + x⁴ + x³ + x² + 1. По группе информационных входов устройства D8. . . D1-29. ..36 (фиг. 2) при активном высоком уровне сигнала на входе 47 загружается начальное значение локатора, например, α³¹ = 11000000.

При низком уровне на управляющем входе режима работы устройства 45 будет порождаться последовательность α³¹ = 01100000, α³⁰ = 00110000,...,1 при поступлении тактового сигнала по входу сдвига 46. Конфигурация регистра будет функционировать, как показано на фиг. 1, что обеспечивается соответствующим управлением коммутаторов, и информация при сдвиге распространяется таким образам: сдвиг информации происходит от выхода ячейки 1 через коммутатор 9 на соответствующие вторые группы входов одноименных сумматоров по модулю q и первый вход коммутатора 20. С выхода коммутатора 20 на информационный вход ячейки 8, дальше с выхода ячейки 8 через группу первых входов коммутатора 16 на вход ячейки 7, с выхода ячейки 7 через первую группу выходов коммутатора 15 на вход ячейки 6, с ее выхода через первую группу входов коммутатора 14 на вход ячейки 5, с ее выхода через первую группу входов коммутатора 13 на первую группу входов сумматора 1, с его выходов через первую группу входов коммутатора 17 на вход ячейки 4, с ее выходов через первую группу входов коммутатора 12 на вторую группу входов СМ2, с его выходов через первую группу входов коммутатора 18 на вход ячейки 3, с ее выхода через первую группу входов коммутатора 11 на вторую группу входов CM3, с его выхода через первую группу входов коммутатора 19 на вход ячейки 2, с ее выходов через первую группу входов коммутатора 10 на вход ячейки 1.

При высоком уровне на управляющем входе 45 информация будет распространяться через вторые группы коммутаторов, что соответствует функционированию регистра по схеме (фиг. 2). Сдвиг регистра происходит вправо. Информация с выхода ячейки 1 регистра поступает через вторую группу входов коммутатора 19 на вход ячейки 2 и с ее выходов через вторую группу входов коммутатора 11 на первую группу входов СМ3, с его выходов через вторую группу входов коммутатора 18 на входы ячейки 3, с ее выходов через вторую группу входов КМ 12 на первую группу входов второго СМ, с его выходов через вторую группу входов КМ 17 на вход ячейки 4, с ее выходов через вторую группу входов КМ 13 на первую группу входов первого СМ, с выходов которого через вторую группу входов КМ 14 на входы ячейки 5, с выходов которой через вторую группу входов КМ 15 на входы ячейки 6, с выходов которой через вторую группу входов КМ 16 на входы ячейки 7, с выходов которой через вторую группу входов КМ 20 на вход ячейки 8, с выходов которой на вторую группу входов КМ 10 и КМ 9. С выходов КМ 10 информация передается на входы ячейки 1, а с выходов КМ 9 - на вторые группы входов одноименных сумматоров.

Применение предлагаемого устройства позволяет значительно снизить (приблизительно в 250 раз) аппаратные затраты, что очень важно в интегральном выполнении, так как применяется сдвиговый регистр вместо ПЗУ, например 256х8 бит, а также повысить быстродействие устройства.

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

Изобретение относится к вычислительной технике, в частности к выполнению операций в полях Галуа, например, в устройствах декодирования кодов Рида-Соломона. Цель изобретения - упрощение, расширение области применения и повышение быстродействия устройства. Генератор локаторов содержит сдвиговый регистр из m ячеек, p сумматоров по модулю q, m+p+1 двунаправленных коммутаторов данных, m блоков начальной установки локаторов. Выходы ячеек регистра являются информационными выходами устройства. Введение коммутаторов, управляемых входом задания режима, и соответствующее их соединение с ячейками регистра и сумматорами позволило реализовать два режима работы устройства: генерацию последовательностей с увеличением или уменьшением степени элемента. Введение блоков начальной установки локаторов позволило воспроизвести все допустимые последовательности локаторов. 5 ил.

Генератор локаторов поля Галуа GF(q^m), содержащий сдвиговый регистр из m ячеек, отличающийся тем, что в устройство введены m блоков начальной установки значения локаторов, (m + 1 + p) двунаправленных коммутаторов данных, p сумматоров по модулю q, причем информационные входы блоков начальной установки значения локаторов являются группой информационных входов начальной установки значения локатора первого символа кодового слова, управляющие входы объединены и являются управляющим входом начальной установки генератора, а выходы блоков начальной установки значения локаторов соединены с входами начальной установки соответствующих ячеек сдвигового регистра, выходы которых являются группой информационных выходов генератора, выход ячейки регистра соединен с первым информационным входом соответствующего коммутатора данных с первого по m-й, причем выход m-й ячейки сдвигового регистра соединен с вторыми информационными входами первого и второго коммутаторов данных, выходы коммутаторов данных с m-го по (m k)-й соединены с информационными входами с m-й по (m k)-й ячеек сдвигового регистра соответственно, выходы коммутаторов данных с (m k p)-го до первого соединены с информационными входами с (m k p)-й до первой ячеек сдвигового регистра соответственно, выходы коммутаторов данных с (m k)-го по (m k p)-й соединены с первыми входами с первого по p-й сумматоров соответственно, группа выходов первого сумматора по модулю q соединена с первой группой входов (m + 1)-го коммутатора данных и второй группой (m k 1)-го коммутатора данных, группы выходов сумматоров по модулю q с второго по p-й соединены с первыми группами входов с (m + 2)-го по (m + p 2)-й коммутаторов данных соответственно и с вторыми входами коммутаторов данных с (m + 1)-го до (m + p 1)-го соответственно, группы выходов с (m + 1)-го до (m + p)-го коммутаторов данных соединены с информационными входами ячеек регистра с (m k + 1)-го до (m k + p)-го соответственно, группа выходов первого коммутатора данных соединена с вторыми группами входов сумматоров и с первой группой входов (m + p + 1)-го коммутатора данных, группа выходов которого соединена с информационными входами m-й ячейки регистра, группа информационных выходов (m 1)-й ячейки соединена с вторыми входами (m + p + 1)-го коммутатора данных, группы информационных выходов ячеек регистра с (m 2)-й по (m k)-ю соединены с вторыми группами входов коммутаторов данных с m по (m k 1)-го соответственно, группа выходов (m k p 1)-го коммутатора данных соединена с второй группой информационных входов (m + p)-го коммутатора данных, группы выходов ячеек регистра с (m k 2)-й по первую дополнительно соединены с вторыми группами информационных входов коммутаторов данных с (m k)-го по второй коммутатор данных соответственно, управляющие входы коммутаторов объединены и являются управляющим входом режима работы устройства, управляющие входы записи ячеек регистра объединены и являются управляющим входом сдвига регистра.