Результат интеллектуальной деятельности: Устройство обнаружения и коррекции ошибки модулярного кода

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

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

Известна нейронная сеть для обнаружения, локализации и исправления ошибок в системе остаточных классов (Патент РФ №2301442, опубл. 20.06.2007), которая содержит входной слой, нейронные сети конечного кольца для определения синдрома ошибок, блок памяти для хранения констант, нейронные сети для вычисления правильного результата и элемент ИЛИ для определения наличия ошибки.

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

Известна адаптивная параллельно-конвейерная нейронная сеть для коррекции ошибок (Патент РФ №2279131, опубл. 27.06.2006), которая содержит блок обнаружения ошибок, блок реконфигурации и локализации ошибок, блок исправления ошибок, блок нейронной сети конечного кольца формирования цифр в представлении обобщенной позиционной системы.

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

Наиболее близким к предлагаемому устройству, выбранным в качестве прототипа, является устройство для обнаружения переполнения динамического диапазона, определения ошибки и локализации неисправности вычислительного канала в ЭВМ, функционирующих в системе остаточных классов (Патент РФ №2483346, опубл. 27.05.2013). Устройство содержит входной регистр, содержащий n+r разрядных регистров для временного хранения контролируемого числа А, представленного по модулям p₁, р₂, …, p_n+r, схему формирования проекций A_i числа А по основаниям p_i [i=[1,n+r]), (число A_i, полученное из А зачеркиванием цифры α₁ называется проекцией числа по основанию p_i); блоки памяти, содержащие n+r элементов памяти для хранения констант по модулям p_i; сумматор для суммирования произведения разрядных констант и соответствующих цифр разрядов числа; блок анализа на равенство, больше или меньше рабочего диапазона; триггер для запуска и остановки счетчика проекций; блок логических элементов «И», содержащий n+r элементов «И» для локализации неисправного канала p_i; входные шины для подачи контролируемого числа А, схему формирования проекций константы, соответствующей рабочему диапазону; блок хранения констант рабочего диапазона, состоящий из n+r элементов; сумматор; шину, сигнализирующую о неисправности p_i канала; шину сигнала «ошибка не установлена» и шину для подключения разрядов константы, соответствующей рабочему диапазону; шину «переполнение диапазона и ошибка», сигнализирующую о переполнении рабочего диапазона и появлении ошибки.

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

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

Данный технический результат достигается тем, что в устройство обнаружения и коррекции ошибки модулярного кода, содержащее n+2 входа остатка α_i, где i=1, …, n+2, n+2 регистра хранения остатка α_i, блок формирования проекций, n+2 блока хранения произведений k_iα_i, 2 блока хранения произведений k_n+1m_n+1 и k_n+2m_n+2 соответственно, сумматор произведений k_iα_i, сумматор произведений k_n+1m_n+1 и k_n+2m_n+2, счетчик, блок сравнения, n+2 элемента И локализации ошибки по модулю p_i, причем каждый из входов остатка α_i подключен ко входу соответствующего регистра хранения остатка α_i, выходы которых подключены ко входам блока формирования проекций, первые выходы которого подключены к первым входам соответствующих блоков хранения произведений k_iα_i и блоков хранения произведений k _n+1m_n+1 и k_n+2m_n+2, выходы блоков хранения произведений k_iα_i подключены к входам сумматора произведений k_iα_i, выходы блоков хранения произведений k_n+1m_n+1 и k_n+2m_n+2 соединены со входами сумматора произведений k_n+1m_n+1 и k_n+2m_n+2, выход сумматора произведений k_iα_i подключен к первому входу блока сравнения, выход сумматора произведений k_n+1m_n+1 и k_n+2m_n+2 подключен ко второму входу блока сравнения, выход которого соединен со входами соответствующих элементов И локализации ошибки по модулю p_i, введены 2 регистра хранения остатков m_n+1 и m_n+2, блок управления, n+2 регистра хранения скорректированного остатка α_i, n+2 выхода скорректированного остатка α_i, в блок формирования проекций, содержащий счетчик, добавлено n+2 элемента И формирования проекции α_i, 2 элемента И формирования проекций m_n+1 и m_n+2, в блок управления, содержащий блок сравнения и n+2 элемента И локализации ошибки по модулю p_i, добавлены n+3 - битный циклический регистр сдвига, n+2 модулярных умножителя на P_i по модулю p_i, n+2 мультиплексора выбора корректного остатка α_i, причем выходы регистров хранения остатка α_i подключены ко входам блока управления, выходы регистров хранения остатков m_n+1 и m_n+2 подключены ко входам блока формирования проекций, вторые выходы которого подключены ко вторым входам соответствующих блоков хранения произведений k_iα_i и блоков хранения произведений k_n+1m_n+1 и k_n+2m_n+2, выходы сумматора произведений k_iα_i и сумматора произведений k_n+1m_n+1 и k_n+2m_n+2 подключены ко входам блока управления, управляющий выход которого соединен с управляющим входом блока формирования проекций, выходы блока управления подключены к входам соответствующих регистров хранения скорректированного остатка α_i, выходы которых соединены с соответствующими выходами скорректированного остатка α_i, при этом старший, n+3-й бит управляющего входа блока формирования проекций соединен со входом счетчика, младший, 1-й бит подключен ко вторым входам элементов И формирования проекции α_n+2 и m_n+2, 2-й бит подключен ко вторым входам элементов И формирования проекции α_n+1 и m_n+1, оставшиеся n бит управляющего входа подключены соответственно ко вторым входам элементов И формирования проекции α_n, …, α₁, к первым входам элементов И формирования проекции α_i подключены входы блока формирования проекций, соединенные с регистрами хранения остатка α_i, к первым входам элементов И формирования проекции m_n+1 и m_n+2 подключены входы блока формирования проекций, соединенные с регистрами хранения остатков m_n+1 и m_n+2, выходы элементов И формирования проекции α_i и элементов И формирования проекций m_n+1 и m_n+2 подключены к соответствующим первым выходам блока формирования проекций, вторые выходы которого соединены с выходом счетчика; в блоке управления первый вход блока сравнения, подключенный к выходу сумматора произведений k_iα_i, соединен со входами модулярных умножителей на P_i по модулю p_i, выход блока сравнения подключен ко входу n+3-битного циклического регистра сдвига, выход которого подключен к управляющему выходу блока управления, а также по битам, начиная с младшего, одновременно к входам элементов И локализации ошибки по модулю p_i и управляющим входам мультиплексоров выбора корректного остатка α_i соответственно; выходы регистров хранения остатка α_i, соединенные со входами блока управления, подключены к входам соответствующих элементов И локализации ошибки по модулю p_i, выходы которых подключены ко вторым входам соответствующих мультиплексоров выбора корректного остатка α_i, первые входы которых подключены к выходам соответствующих модулярных умножителей на P_i по модулю p_i, а выходы подключены к выходам блока управления и соединены с входами соответствующих регистров хранения скорректированного остатка α_i.

Сущность изобретения основана на следующем математическом аппарате. В системе остаточных классов любое число А<М однозначно представляется набором остатков α_i от деления А на взаимно простые модули СОК p_i, где α_i = A mod p_i, - рабочий диапазон, i=[1,n]. Для обнаружения и исправления ошибки в СОК добавляют два избыточных модуля p_n+1 и p_n+2 и тогда диапазон избыточной системы остаточных классов составит Разрешенным считается число А=(α₁, α₂, …, α_n, α_n+1,α_n+2), если А∈[0,М], в случае же А∈(М,Р] можно сказать, что число содержит ошибку. При этом М представляется в избыточной СОК и очевидно, что М=(0, …, 0, m_n+1,m_n+2), где m_n+1=Mmodp_n+1, m_n+2=Mmodp_n+2.

Для эффективной аппаратной реализации берут относительное приближенное значение

,

где - константа выбранной СОК, - мультипликативная инверсия. В данном случае для определения ошибки используется сравнение относительной величины с константой .

В для обнаружения и исправления ошибок применяется метод проекций, который заключается в следующем. Предполагают, что ошибка допущена по первому модулю p₁ и повторяют вычисления без участия этого модуля, т.е. берут в качестве избыточного диапазона , для нового диапазона вычисляют новые константы k_i, и в конечном счете сравнивают с константой . В случае, если , то считают, что ошибка произошла по модулю p_i и для нахождения точного значения остатка А по модулю р₁ умножают на Р₁ и находят остаток по модулю р₁. В случае можно сказать, что ошибка еще присутствует и для ее обнаружения и исправления вместо p_i исключают р₂ и проводят аналогичную проверку. Такие проекции строятся по всем модулям p₁, …, p_n+2.

Значения констант k₁ берут с точностью N, необходимой для корректных вычислений.

Данное устройство обнаружения и коррекции ошибки модулярного кода поясняется фигурами 1-3. На фигуре 1 представлен общий вид устройства, которое содержит входы 1.i остатка α_i, где i=1, …, n+2, регистры 2.i хранения остатка α_i, регистры 3.1 и 3.2 хранения остатков m_n+1 и m_n+2 соответственно, блок формирования проекций 4, блоки 5.i хранения произведений k_iα_i, блоки 6.1 и 6.2 хранения произведений k_n+1m_n+1 и k_n+2m_n+2 соответственно, сумматор 7 произведений k_iα_i, сумматор 8 произведений k_n+1m_n+1 и k_n+2m_n+2, блок управления 9, регистры 10.i храпения скорректированного остатка α_i, выходы 11.i скорректированного остатка α_i.

На фиг. 2 показано устройство блока формирования проекций 4, состоящего из элементов И 12.i формирования проекций α_i, элементов И 13.1 и 13.2 формирования проекций m_n+1 и m_n+2 соответственно и счетчика 14.

На фиг. 3 представлен блок управления 9, который состоит из блока сравнения 15, n+3-битного циклического регистра сдвига 16, модулярных умножителей 17.i на P_i по модулю p_i, элементов И 18.i локализации ошибки по модулю p_i, мультиплексоров 19.i выбора корректного остатка α_i.

Поясним работу устройства примерами. Пусть задана система остаточных классов с модулями р₁=2, p₂=3, р₃=5, р₄=7, р₅=11, р₆=13, р₇=17, следовательно n=5. Значение рабочего диапазона М=2310. В качестве сомножителей в модулярных умножителях 17.i на P_i по модулю p_i используются следующие значения: Р₁=255255, Р₂=170170, Р₃=102102, Р₄=72930, Р₅=46410, Р₆=39270, Р₇=30030.

В блок 5.1 хранения произведения k₁α₁ записывают все произведения k₁⋅α₁ при α₁=[0,p₁)=[0,1] и k_i, выбираемом из Таблицы 1 в зависимости от адреса со счетчика 14. Так, например, на вход блока 5.1 хранения произведения k₁α₁ подается значение α₁=1 и адрес 0, тогда k₁=0.5 и на выход блока 5.1 хранения произведения k₁α₁ будет подано значение 0.5.

Аналогично в блоке 5.2 хранения произведения k₂α₂ записаны все произведения k₂⋅α₂ при α₂=[0,р₂)=[0,2] и k₂, выбираемом из Таблицы 1 в зависимости от адреса со счетчика 14. В блоке 5.3 хранения произведения k₃α₃ записаны все произведения k₃⋅α₃ при α₃=[0,р₃)=[0,4] и k₃, выбираемом из Таблицы 1 в зависимости от адреса со счетчика 14. В блоке 5.4 хранения произведения k₄α₄ записаны все произведения k₄⋅α₄ при α₄=[0,p₄)=[0,6] и k₄, выбираемом из Таблицы 1 в зависимости от адреса со счетчика 14. В блоке 5.5 хранения произведения k₅α₅ записаны все произведения k₅⋅α₅ при α₅=[0,p₅)=[0,10] и k₅, выбираемом из Таблицы 1 в зависимости от адреса со счетчика 14. В блоках 5.6 хранения произведения k₆α₆ и 6.1 хранения произведения k₆m₆ записаны все произведения k₆⋅α₆ и k₆⋅m₆ при α₆=[0,р₆)=[0,12], m₆={0,М mod р₆}={0,9} и k₆, выбираемом из Таблицы 1 в зависимости от адреса со счетчика 14. В блоках 5.7 хранения произведения k₇α₇ и 6.2 хранения произведения k₇m₇ записаны все произведения k₇⋅α₇ и k₇⋅m₇ при α₇=[0,р₇)=[0,16], m₇={0,М mod р₇}={0,15} и k₇, выбираемом из Таблицы 1 в зависимости от адреса со счетчика 14.

Рассмотрим конструкцию и принцип работы n+3-битного циклического регистра сдвига 16. В начале работы он содержит значение "0111 …11". Старший бит, который на первом шаге равен 0 подается на счетчик 14, который подает адрес 0 па блоки 5.1-5.7 и 6.1-6.2 хранения произведений k_iα_i и k₆m₆ и k₇m₇. Остальные биты данного числа подаются на элементы И 12.1-12.7 формирования проекций α_i, элементы И 13.1-13.2 формирования проекций m₆ и m₇, элементы И 18.1-18.7 локализации ошибки по модулю p_i. В случае возникновения ошибки с блока сравнения 15 в n+3-битный циклический регистр сдвига 16 поступает сигнал и его значение меняется на "1011 …11". Тогда на счетчик 14 подается старший бит, равный 1 и адрес 1 подается на блоки 5.1-5.7 и 6.1-6.2 хранения произведений k_iα_i и k₆m₆ и k₇m₇. Остальные биты данного числа подаются на элементы И 12.1-12.7 формирования проекций α_i, элементы И 13.1-13.2 формирования проекций m₆ и m₇, элементы И 18.1-18.7 локализации ошибки по модулю p_i. При этом n+2-й бит со значением 0 подается на элемент И 12.1 формирования проекций α₁ и элемент И 18.1 локализации ошибки по модулю p₁ что соответствует вычеркиванию первого основания в методе проекций. Аналогично пулевой бит на каждом шаге сдвигается вправо до достижения значения "1111 …10", при этом нулевой бит во всех случаях в результате логического умножения подает на выход соответствующих элементов нулевое значение, что означает выбор проекции.

Рассмотрим работу устройства на примере значения А=(1,0,1,6,10,12,12)=2001. На входы 1.1-1.7 остатков α₁, …, α₇ подаются соответственно значения 1,0,1,6,10,12,12, которые затем записываются в регистры 2.1-2.7 хранения остатков α₁, …, α₇. Значения поступают в блок формирования проекций 4, где проходя через элементы И 12.1-12.7 формирования проекций α₁, …, α₇ поступают на соответствующие первые входы блоков 5.1-5.7 хранения произведений k_iα_i, на второй вход которых подается адрес 0. С выходов блоков 5.1-5.7 хранения произведений k_iα_i значения соответствующих произведений поступают на сумматор 7 произведений k_iα_i где происходит суммирование по модулю 1 и на выходе сформируется значение, эквивалентное 0.0039196. В это время аналогичные процессы проходят для коэффициентов m₆ и m₇ и на выходе сумматора 8 произведений k₆m₆ и k₇m₇ получится значение 0.0045249. В блоке сравнения 15 данные значения сравниваются и поскольку 0.0039196<0.0045249, то на выходе блока сравнения 16 будет значение 1, которое поступает на входы элементов И 18.1-18.7 локализации ошибки по модулю p_i, на вход которых также поступают значения 1,0,1,6,10,12,12 с выходов регистров 2.1-2.7 хранения остатков α₁, …, α₇. С выхода n+3-битного циклического регистра сдвига 16 на входы элементов И 18.1-18.7 локализации ошибки по модулю p_i и на управляющие входы мультиплексоров 19.1-19.7 выбора корректного остатка α_i поступают значения 1. Таким образом, мультиплексоры 19.1-19.7 выбора корректного остатка α_i подают значения 1,0,1,6,10,12,12 с выходов элементов И 18.1-18.7 локализации ошибки по модулю p_i на соответствующие регистры 10.1-10.7 хранения скорректированного остатка α_i, откуда значения поступают на выходы 11.1-11.7 скорректированного остатка α₁, …, α₇. Таким образом на выход устройства подается корректное значение.

Рассмотрим случай, когда по третьему основанию возникла ошибка и на входы 1.1-1.7 остатков α₁, …, α₇ поступило значение (1,0,4,6,10,12,12)=410409. Работа устройства происходит аналогично и на выходе сумматора 7 произведений k_iα_i формируется сигнал, эквивалентный 0.8039196. Поскольку 0.8039196>0.0045249, то на выходе блока сравнения 16 будет значение 0, и в результате на выходах 11.1-11.7 скорректированного остатка α₁, …, α₇ будут значения 0, при этом сигнал 0 с выхода блока сравнения 16 поступает на вход n+3-битного циклического регистра сдвига 16, где происходит сдвиг значения и формирования первой проекции в результате которой выходы элемента И 12.1 формирования проекций α₁ и элемента И 18.1 локализации ошибки по модулю p₁ будут нулевыми, а значение счетчика изменится на 1, что соответствует адресу 1 Таблицы 1.

Аналогично происходят вычисления сумм и на выходе сумматора 7 произведений k_iα_i формируется сигнал, эквивалентный 0.6078392, на выходе сумматора 8 произведений k₆m₆ и k₇m₇ формируется сигнал, эквивалентный 0.0090497 и поскольку 0.6078392>0.0090497, то на выходе блока сравнения 16 будет значение 0, что соответствует наличию ошибки и в n+3-битном циклическом регистре сдвига 16 происходит сдвиг и формирование второй проекции.

В результате вычислений по второй проекции на выходе сумматора 7 произведений k_iα_i формируется сигнал, эквивалентный 0.4117588, на выходе сумматора 8 произведений k₆m₆ и k₇m₇ формируется сигнал, эквивалентный 0.0135747 и поскольку 0.4117588>0.0135747, то на выходе блока сравнения 16 будет значение 0, что соответствует наличию ошибки и в n+3-битном циклическом регистре сдвига 16 происходит сдвиг и формирование третьей проекции.

В результате вычислений по третьей проекции па выходе сумматора 7 произведений k_iα_i формируется сигнал, эквивалентный 0.0195980, на выходе сумматора 8 произведений k₆m₆ и k₇m₇ формируется сигнал, эквивалентный 0.0226244 и поскольку 0.0195980<0.0226244, то на выходе блока сравнения 16 будет значение 1, что соответствует отсутствию ошибки и следующий сдвиг в n+3-битном циклическом регистре сдвига 16 не происходит. Следовательно ошибка произошла по третьему основанию. Значение 0.0195980 с выхода сумматора 7 произведений k_iα_i, поступает па модулярный умножитель 17.3 на Р₃ по модулю р₃, на выходе которого формируется значение 1. Поскольку значение, подаваемое на управляющий вход мультиплексора 19.3 выбора корректного остатка α₃, равно нулю, то на выход подается значение 1 с выхода модулярного умножителя 17.3 на Р₃ по модулю р₃. На остальные управляющие входы мультиплексоров 19.1-19.2, 19.4-19.7 выбора корректного остатка α_i подаются значения 1 и на выход подаются значения с соответствующих элементов И 18.1-18.2, 18.4-18.7 локализации ошибки по модулю p_i, которые равны полученным α_i, которые хранятся в регистрах 2.1-2.7 хранения остатков Таким образом на выходы 11.1-11.7 скорректированного остатка α₁, …, α₇ поступают значения 1,0,1,6,10,12,12, что соответствует исправленному значению.

Устройство обнаружения и коррекции ошибки модулярного кода