УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ КОЭФФИЦИЕНТОВ ОБОБЩЕННОЙ ПОЛИАДИЧЕСКОЙ СИСТЕМЫ С КОРРЕКЦИЕЙ ОШИБОК

Изобретение относится к вычислительной технике, в частности к модулярным нейрокомпьютерным средствам, и предназначено для вычисления коэффициентов обобщенной полиадической системы (ОПС), представленных в полях Галуа GF(2^ν).

Известна нейронная сеть для вычисления коэффициентов обобщенной полиадической системы (ОПС), представленных в расширенных полях Галуа GF(2^ν) ([1] Калмыков И.А., Лободин М.В., Алексишин Е.В., Щелкунова Ю.О. Нейронная сеть для вычисления коэффициентов обобщенной полиадической системы, представленной в расширенных полях Галуа // Патент РФ №2258956, G06N 3/04), содержащая два слоя по 15 нейронов в каждом, при этом первый слой 15 нейронов подключен к соответствующим входам 15 нейронов второго слоя.

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

Основной задачей является расширение функциональных возможностей, которые позволят нейронной сети корректировать ошибки.

Техническим результатом, достигнутым при осуществлении заявленного изобретения, является расширение функциональных возможностей, позволяющих исправлять ошибки в коэффициентах ОПС, которые были получены из кодовой комбинации, представленной в полиномиальной системе классов вычетов (ПСКВ).

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

В полиномиальной системе классов вычетов в качестве основания системы используются минимальные многочлены p_i(z), i=1, 2, …, n, определенные в расширенных полях Галуа GF(2^ν). Тогда любой полином A(z), удовлетворяющий условию

где degA(z) - степень полинома A(z); - полный диапазон, можно представить в виде n-мерного вектора

где i=1, 2, …, n.

Используя коды ПСКВ, можно операцию сложения, вычитания и умножения двух операндов, представленных в полиномиальной форме A(z) и B(z), свести к выполнению этих операций над соответствующими остатками α_i(z) и β_i(z). При этом в ПСКВ эти операции производятся независимо по каждому из модулей p_i(z), что указывает на параллелизм данной алгебраической системы. При этом, благодаря параллелизму алгебраической системы вычисления могут быть реализованы с помощью нейронных сетей ([2] - Калмыков И.А., Воронкин Р.А., Резеньков Д.Н, Емарлукова Я.В., Фалько А.А. Генетические алгоритмы в системах цифровой обработки сигналов // Нейрокомпьютеры: разработка и применение. - 2011. - №5. - С. 20-27).

Кроме того, особенность ПСКВ состоит еще и в том, что независимость обработки информации по основаниям ПСКВ позволяет не только повысить скорость и точность обработки, но также и обеспечить обнаружение и коррекцию ошибок в процессе функционирования вычислительного устройства класса вычетов. Если на диапазон возможного изменения кодируемого множества полиномов наложить ограничения, то есть выбрать k из n оснований ПСКВ (k<n), то это позволит осуществить разбиение полного диапазона расширенного поля Галуа GF(p^v) на два непересекающихся подмножества.

Первое подмножество называется рабочим диапазоном и определяется выражением

Многочлен A(z) с коэффициентами из поля GF(p) будет считаться разрешенным в том и только том случае, если он является элементом нулевого интервала полного диапазона P_полн(z), то есть принадлежит рабочему диапазону degA(z)<degP_раб(z).

Второе подмножество GF(p^v), определяемое произведением r=n-k контрольных оснований

задает совокупность запрещенных комбинаций. Если A(z) является элементом второго подмножества, то считается, что данная комбинация содержит ошибку. Таким образом, местоположение полинома A(z) относительно двух данных подмножеств позволяет однозначно определить, является ли кодовая комбинация A(z)=(α₁(z), α₂(z), …, α_k+r(z)) разрешенной или содержит ошибочные символы ([3] Калмыков И.А., Саркисов А.Б., Яковлева Е.М., Калмыков М.И. Модулярный систолический процессор цифровой обработки сигналов с реконфигурируемой структурой // Вестник Северо-Кавказского федерального университета. - 2013. - №2 (35). - С. 30-35.)

В [1] приведена нейронная сеть для перевода из модулярного кода ПСКВ в обобщенную полиадическую систему, в которой используются 5 неприводимых полиномов p₁(z)=z+1, p₂(z)=z²+z+1, p₃(z)=z⁴+z³+z²+z+1, p₄(z)=z⁴+z³+1, p₅(z)=z⁴+z+1. Если положить, что первые три основания являются информационными, т.е. k=3, то рабочий диапазон будет определяться согласно (6) и равен

Оставшиеся два основания p₄(z)=z⁴+z³+1 и p₅(z)=z⁴+z+1 будем считать контрольными модулями, с помощью которых будут производиться поиск и коррекция ошибок, возникающих в кодах ПСКВ.

В этом случае любой полином, представленный в коде ПСКВ, чья степень будет меньше семи, т.е. degA(z)<7, является разрешенным, а его кодовая комбинация не содержит ошибки. В противном случае кодовая комбинация содержит ошибки.

Коэффициенты обобщенной полиадической системы позволяют осуществить поиск и коррекцию ошибок в кодах ПСКВ. Для данного примера полином A(z) можно представить в обобщенной полиадической системе как

где

Ортогональные базисы такой системы равны:

B₁(z)=z¹⁴+z¹³+z¹²+z¹¹+z¹⁰+z⁹+z⁸+z⁷+z⁶+z⁵+z⁴+z³+z²+z+1;

B₂(z)=z¹⁴+z¹³+z¹¹+z¹⁰+z⁸+z⁷+z⁵+z⁴+z²+z;

B₃(z)=z¹⁴+z¹³+z¹²+z¹¹+z⁹+z⁸+z⁷+z⁶+z⁴+z³+z²+z;

B₄(z)=z¹⁴+z¹³+z¹²+z¹¹+z⁹+z⁷+z⁶+z³;

B₅(z)=z¹²+z⁹+z⁸+z⁶+z⁴+z³+z²+z.

Представим ортогональные базисы в виде коэффициентов ОПС

Согласно Китайской теореме об остатках полином A(z) определяется как

где - полный диапазон ПСКВ.

Если в качестве ортогональных базисов B_i(z) взять их представления в ОПС, то при умножении остатков α_i(z) на последние можно получить коэффициенты ОПС

где - коэффициенты ОПС i-го ортогонального базиса с учетом переполнения (i-l)-го основания.

При этом умножение вычетов на соответствующие коэффициенты осуществляется помодульно и поразрядно, при этом учитывается превышение модуля p_i(z) как перенос в старший коэффициент ОПС a_i+1(z).

Из выражения (8) наглядно видно, что если полином A(z), представленный в ПСКВ, не содержит ошибки, то его степень не превысит степень рабочего диапазона. Следовательно, значения старших коэффициентов ОПС должны равняться нулю, т.е. a₄(z)=0 и a₅(z)=0.

Если полином A^*(z), представленный в ПСКВ, содержит ошибку, то его значение будет определяться как

где - глубина ошибки по j-му основанию ПСКВ.

В результате этого результат ошибочного кода A^*(z) при переводе в позиционный код окажется за пределами рабочего диапазона P_paб(z). Следовательно, значения старших коэффициентов ОПС не будут равняться нулю. При этом по величине значений старших коэффициентов ОПС можно однозначно определить местоположение и глубину ошибки.

Чтобы осуществлять коррекцию ошибок в комбинации кода ПСКВ были введены два дополнительных слоя нейронов. Структура устройства представлена на фигуре 1. Устройство состоит из двухслойной нейронной сети (нейроны 1-15 образуют первый слой, нейроны 16-30 создают второй слой), блока памяти 31, имеющего восемь входов 32-39 и семь выходов 40-46, семи двухвходовых корректирующих сумматоров 47-53.

Рассмотрим двухслойную нейронную сеть, структура которой совпадает с прототипом [1]. Каждый слой содержит по 15 нейронов. Входной слой состоит из 15 нейронов, распределенных в соответствии с размерностью разрядных сеток модулей -1-2-4-4-4. Данные нейроны осуществляют разветвление входного вектора (α₁(z), α₂(z), α₃(z), α₄(z), α₅(z)), представленного в двоичной форме. Причем нейрон 1 предназначен для распределения нулевого разряда первого основания. Нейроны 2, 3 предназначены для распределения нулевого и первого разрядов второго основания соответственно. Нейроны 4-7 используются для приема и распределения , , , разрядов третьего основания соответственно. Для перераспределения разрядов , , , четвертого основания p₄(z) используются нейроны 8, 9, 10, 11 соответственно. Нейроны 12, 13, 14, 15 применяются для приема разрядов , , , пятого основания p₅(z) соответственно.

Второй слой нейронной сети содержит также 15 нейронов, распределенных в соответствии с размерностью разрядных сеток коэффициентов (a_i(z), i=1, 2, 3, 4, 5) ОПС -1-2-4-4-4. Нейроны 16-30 второго слоя выполняют базовую операцию суммирования по модулю два значений разрядов, поступающих с выходов соответствующих нейронов первого слоя. Синаптические веса связей равны единице.

Нейрон 16 предназначен для приема данных, поступающих с выхода нейрона 1 входного слоя. Выход нейрона 16 соответствует нулевому разряду первого коэффициента ОПС a₁(z).

Нейроны 17, 18 осуществляют вычисление нулевого и первого , разрядов второго коэффициента ОПС соответственно. Причем вход нейрона 17 подключен к выходу нейрона 3. Вход нейрона 18 подключен к выходу нейронов 1, 2, 3.

Нейроны 19, 20, 21, 22 осуществляют вычисление нулевого, первого, второго и третьего разрядов , , , третьего коэффициента ОПС a₃(z) соответственно. Причем нейрон 19 подключен к выходам нейронов 2, 4 и 6 первого слоя. Нейрон 20 - к выходам нейронов 1, 4, 5, 6 и 7. Вход нейрона 21 - к выходам нейронов 2, 3, 4, 5 и 7. Вход нейрона 22 - к выходам нейронов 1, 2, 5.

Нейроны 23, 24, 25, 26 осуществляют вычисление нулевого, первого, второго и третьего разрядов , , , четвертого коэффициента ОПС a₄(z) соответственно. Причем входы нейрона 23 подключены к выходам нейронов 2, 4, 7, 10 первого слоя. Вход нейрона 24 - к выходам нейронов 2, 3, 5, 8, 11. Вход нейрона 25 - к выходам нейронов 3, 4, 6, 8, 9. Вход нейрона 26 - к выходам нейронов 1, 2, 3, 4, 5, 6, 9.

Нейроны 27, 28, 29, 30 осуществляют вычисление нулевого, первого, второго и третьего разрядов , , , пятого коэффициента ОПС a₅(z) соответственно. Причем вход нейрона 27 подключен к выходам нейронов 5, 9, 11 и 15 первого слоя. Вход нейрона 28 - к выходам нейронов 1, 3, 5, 7, 8, 9, 11, 12, 15. Вход нейрона 29 - к выходам нейронов 1, 2, 4, 5, 6, 8, 9, 10, 13.Вход нейрона 30 - к выходам нейронов 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 14 первого слоя.

Блок памяти 31 имеет 8 входов. Первый вход 32 подключен к выходу нейрона 23. Второй вход 33 подсоединен к выходу нейрона 24. Третий вход 34 подключен к выходу нейрона 25. Четвертый вход 35 блока памяти 31 подключен к выходу нейрона 26. Пятый вход 36 блока памяти 31 подключен к выходу нейрона 27. Шестой вход 37 блока памяти 31 подключен к выходу нейрона 28. Седьмой вход 38 блока памяти 31 подключен к выходу нейрона 29. Восьмой вход 39 блока памяти 31 подключен к выходу нейрона 30. Таким образом, на первый вход 32 блока памяти 31 поступает значение нулевого разряда четвертого коэффициента a₄(z), на второй вход 33 - первый разряд коэффициента ОПС a₄(z), на третий вход 34 - второй разряд коэффициента ОПС a₄(z), на четвертый вход 35 - третий разряд коэффициента ОПС a₄(z). Значения нулевого, первого, второго и третьего разрядов , , , пятого коэффициента ОПС a₅(z) поступают соответственно на пятый 36, шестой 37, седьмой 38 и восьмой 39 входы блока памяти 31.

Первый вход корректирующего сумматора 47 подключен к выходу нейрона 16, а второй вход подсоединен к первому выходу 40 блока памяти 31. Таким образом, на первый вход корректирующего сумматора 47 поступает нулевой разряд первого коэффициента ОПС a₁(z), а на второй вход - корректирующее значение . В результате этого происходит исправление ошибки по нулевому разряду первого коэффициента а₁(z).

Первый вход корректирующего сумматора 48 подключен к выходу нейрона 17, а второй вход подсоединен ко второму выходу 41 блока памяти 31. Таким образом, на первый вход корректирующего сумматора 48 поступает разряд второго коэффициента ОПС a₂(z), а на второй вход - корректирующее значение . В результате этого происходит исправление ошибки в данном разряде.

Первый вход корректирующего сумматора 49 подключен к выходу нейрона 18, а второй вход подсоединен ко второму выходу 42 блока памяти 31. Таким образом, на первый вход корректирующего сумматора 49 поступает разряд второго коэффициента ОПС a₂(z), а на второй вход - корректирующее значение . В результате этого происходит исправление ошибки в данном разряде.

Первый вход корректирующего сумматора 50 подключен к выходу нейрона 19, а второй вход подсоединен ко второму выходу 43 блока памяти 31. Таким образом, на первый вход корректирующего сумматора 50 поступает разряд третьего коэффициента ОПС a₃(z), а на второй вход - корректирующее значение . В результате этого происходит исправление ошибки в данном разряде.

Первый вход корректирующего сумматора 51 подключен к выходу нейрона 20, а второй вход подсоединен ко второму выходу 44 блока памяти 31. Таким образом, на первый вход корректирующего сумматора 51 поступает разряд третьего коэффициента ОПС a₃(z), а на второй вход - корректирующее значение . В результате этого происходит исправление ошибки в данном разряде.

Первый вход корректирующего сумматора 52 подключен к выходу нейрона 21, а второй вход подсоединен ко второму выходу 45 блока памяти 31. Таким образом, на первый вход корректирующего сумматора 52 поступает разряд третьего коэффициента ОПС a₃(z), а на второй вход - корректирующее значение . В результате этого происходит исправление ошибки в данном разряде.

Первый вход корректирующего сумматора 53 подключен к выходу нейрона 22, а второй вход подсоединен ко второму выходу 46 блока памяти 31. Таким образом, на первый вход корректирующего сумматора 53 поступает разряд третьего коэффициента ОПС a₃(z), а на второй вход - корректирующее значение . В результате этого происходит исправление ошибки в данном разряде.

С выходов корректирующих сумматоров 47-53, которые являются выходами устройства, снимаются исправленные значения коэффициентов ОПС a₁(z), a₂(z), a₃(z).

Блок памяти 31 предназначен для хранения констант коррекции, значение которых зависит от вычисленных величин старших коэффициентов ОПС. Зависимость значений старших коэффициентов ОПС a₄(z) и a₅(z) от местоположения и глубины ошибки в коде ПСКП приведены в таблице 1.

Зависимость между значениями старших коэффициентов a₄(z), a₅(z) и корректирующими значениями коэффициентов ОПС a₁(z), a₂(z), a₃(z) приведена в таблице 2.

Рассмотрим работу устройства.

Пусть задан полином A(z)=z⁶+z⁵+z⁴+z+1, который принадлежит рабочему диапазону P_paб(z). Тогда его код в ПСКВ имеет вид A(z)=(1, z+1, z³+z²+z+1, z³+z²+z, z³+z) и при этом этот код не содержит ошибки. Воспользуемся выражением (10) и произведем вычисление коэффициентов ОПС. Так как полином A(z) принадлежит рабочему диапазону, то при переводе из ПСКВ в обобщенную полиадическую систему, согласно равенству (8), должны быть значения старших коэффициентов ОПС a₄(z)=0 и a₅(z)=0. В результате вычислений были получены следующие значения:

a₁(z)=1, a₂(z)=z+1, a₃(z)=z³+z²+z+1, a₄(z)=0, a₅(z)=0.

Это свидетельствует о том, что данная кодовая комбинация, представленная в ПСКВ, не содержит ошибки.

В прототипе [1] было показано, как можно провести расчет коэффициентов ОПС с использованием двухслойной нейронной сети прямого распространения. Воспользуемся таблицей 3, с помощью которой покажем работу первого и второго слоев нейронной сети. Рассмотрим получение сигнала на выходе нейрона 18, который соответствует первому разряду второго коэффициента ОПС . Так как на его вход подается 3 единицы, то результат суммирования по модулю два (суммируем по столбцам) равен единице. Аналогичным образом вычисляются значения на выходах остальных нейронов второго слоя. Коэффициенты ОПС, полученные с помощью таблицы 3, совпали с вычисленными ранее.

Так как старшие коэффициенты ОПС равны нулю, то это свидетельствуют, что кодовая комбинация ПСКВ не содержит ошибку, и ее не надо корректировать. В этом случае на входы блока памяти 31 поступают нулевые сигналы с выходов нейронов 23-26 и 27-30, которые соответствуют двоичному представлению коэффициентов a₄(z) и a₅(z), В результате этого с выходов 40-46 также снимается нулевой результат, который подается на корректирующие сумматоры 47-53. В соответствии с этим на выходах этих корректирующих сумматоров, выполняющих операцию суммирования по модулю, значения коэффициентов ОПС a₁(z)=1, a₂(z)=z+1, a₃(z)=z³+z²+z+1, которые были получены с выходов нейронов 16-23 второго слоя, останутся без коррекции.

Пусть произошла ошибка в первом остатке кода ПСКВ и ее глубина равна . В результате этого на вход нейронной сети поступает код ПСКВ A^*(z)=(0, z+1, z³+z²+z+1, z³+z²+z, z³+z²). На выходах нейронов 16-30 второго слоя получатся значения коэффициентов ОПС.

а ₁(z)=0;

a ₂(z)=1;

a ₃(z)=z²+1;

a ₄(z)=z³;

a ₅(z)=z³+z²+z.

Работу на нейронной сети прямого распределения можно представить в виде таблицы 4.

Так как значения старших коэффициентов ОПС a ₄(z)≠0 и a ₅(z)≠0, то это свидетельствует о том, что кодовая комбинация содержит ошибку.

В соответствии с полученными значениями a ₄(z)=z³ и a ₅(z)=z³+z²+z единичный сигнал будет на выходе нейронов 26, 28, 29 и 30 второго слоя. Этот сигнал с выходов нейронов 26, 28, 29, 30 подается на четвертый 35, шестой 37, седьмой 38 и восьмой 39 входы блока памяти 31 соответственно.

В результате с выходов блока памяти 31, согласно данным, приведенным в таблице 2, будут сниматься корректирующие значения Δа₁(z)=1, Δа₂(z)=z, Δa₃(z)=z³+z. Это значит, что сигналы появятся соответственно на первом 40, третьем 42, пятом 44 и седьмом 46 выходах блока памяти 31. Следовательно, эти сигналы поступят на вторые входы первого 47, третьего 49, пятого 51 и седьмого 53 корректирующих сумматоров.

В результате на выходе первого 47 корректирующего сумматора получаем

Ошибку исправили. Теперь откорректированное значение первого коэффициента ОПС a₁(z)=1.

На выходе второго 48 корректирующего сумматора получаем сигнал

На выходе третьего 49 корректирующего сумматора получаем сигнал

Произошло исправление ошибки. Теперь откорректированное значение первого коэффициента ОПС а₂(z)=z+1.

На выходе четвертого 50 корректирующего сумматора получаем сигнал

Ошибка в разряде исправлена.

На выходе пятого 51 корректирующего сумматора получаем сигнал

Ошибка в разряде исправлена.

На выходе шестого 52 корректирующего сумматора получаем сигнал

Ошибка в разряде исправлена.

На выходе седьмого 53 корректирующего сумматора получаем сигнал

Ошибка исправлена. Теперь откорректированное значение третьего коэффициента ОПС равно a₃(z)=z³+z²+z+1.