Устройство обнаружения и коррекции ошибки модулярного кода
DEVICE FOR DETECTING AND CORRECTING THE ERROR OF THE MODULAR CODE

Изобретение относится к вычислительной технике и предназначено для обнаружения и коррекции ошибки, возникающей в модулярном коде при вычислении и передаче данных.
В качестве основы для представления модулярных чисел выступает система остаточных классов (СОК), в которой целое число представляется в виде остатков от деления на набор модулей, а арифметические операции над числами заменяются на операциями над остатками. Выполнение операций происходит параллельно без межразрядных переносов, что позволяет эффективно реализовать сложение, вычитание и умножение. Независимость выполнения действий над каждым модулем обеспечивает внутренние корректирующие способности модулярного кода, поскольку каждый остаток содержит информацию о всем числе.
Известна нейронная сеть для обнаружения, локализации и исправления ошибок в системе остаточных классов (Патент РФ №2301442, опубл. 20.06.2007), которая содержит входной слой, нейронные сети конечного кольца для определения синдрома ошибок, блок памяти для хранения констант, нейронные сети для вычисления правильного результата и элемент ИЛИ для определения наличия ошибки.
Недостатком данного устройства является низкое быстродействие, большие аппаратные затраты и жесткие условия, накладываемые на абсолютную надежность каналов по избыточным модулям.
Известна адаптивная параллельно-конвейерная нейронная сеть для коррекции ошибок (Патент РФ №2279131, опубл. 27.06.2006), которая содержит блок обнаружения ошибок, блок реконфигурации и локализации ошибок, блок исправления ошибок, блок нейронной сети конечного кольца формирования цифр в представлении обобщенной позиционной системы.
Недостатками данного устройства являются сложность, которая объясняется наличием большого количества нейронных сетей конечного кольца и низкое быстродействие, которое пропорционально количеству модулей системы остаточных классов.
1
2
n+r
i
i
i
1
i
i
i
i
Наиболее близким к предлагаемому устройству, выбранным в качестве прототипа, является устройство для обнаружения переполнения динамического диапазона, определения ошибки и локализации неисправности вычислительного канала в ЭВМ, функционирующих в системе остаточных классов (Патент РФ №2483346, опубл. 27.05.2013). Устройство содержит входной регистр, содержащий n+r разрядных регистров для временного хранения контролируемого числа А, представленного по модулям p, р, …, p, схему формирования проекций A числа А по основаниям p [i=[1,n+r]), (число A, полученное из А зачеркиванием цифры α называется проекцией числа по основанию p); блоки памяти, содержащие n+r элементов памяти для хранения констант по модулям p; сумматор для суммирования произведения разрядных констант и соответствующих цифр разрядов числа; блок анализа на равенство, больше или меньше рабочего диапазона; триггер для запуска и остановки счетчика проекций; блок логических элементов «И», содержащий n+r элементов «И» для локализации неисправного канала p; входные шины для подачи контролируемого числа А, схему формирования проекций константы, соответствующей рабочему диапазону; блок хранения констант рабочего диапазона, состоящий из n+r элементов; сумматор; шину, сигнализирующую о неисправности p канала; шину сигнала «ошибка не установлена» и шину для подключения разрядов константы, соответствующей рабочему диапазону; шину «переполнение диапазона и ошибка», сигнализирующую о переполнении рабочего диапазона и появлении ошибки.
Недостатком данного изобретения является ограниченные функциональные возможности, связанные с невозможностью получения скорректированного числа.
Техническим результатом является расширение функциональных возможностей, а именно возможность не только обнаружения, но и коррекции ошибки модулярных чисел.
i
i
i
i
n+1
n+1
n+2
n+2
i
i
n+1
n+1
n+2
n+2
i
i
i
i
i
n+1
n+1
n+2
n+2
i
i
i
i
n+1
n+1
n+2
n+2
n+1
n+1
n+2
n+2
i
i
n+1
n+1
n+2
n+2
i
n+1
n+2
i
i
i
n+1
n+2
i
i
i
i
i
n+1
n+2
i
i
n+1
n+1
n+2
n+2
i
i
n+1
n+1
n+2
n+2
i
i
n+2
n+2
n+1
n+1
n
1
i
i
n+1
n+2
n+1
n+2
i
n+1
n+2
i
i
i
i
i
i
i
i
i
i
i
i
Данный технический результат достигается тем, что в устройство обнаружения и коррекции ошибки модулярного кода, содержащее n+2 входа остатка α, где i=1, …, n+2, n+2 регистра хранения остатка α, блок формирования проекций, n+2 блока хранения произведений kα, 2 блока хранения произведений km и km соответственно, сумматор произведений kα, сумматор произведений km и km, счетчик, блок сравнения, n+2 элемента И локализации ошибки по модулю p, причем каждый из входов остатка α подключен ко входу соответствующего регистра хранения остатка α, выходы которых подключены ко входам блока формирования проекций, первые выходы которого подключены к первым входам соответствующих блоков хранения произведений kα и блоков хранения произведений km и km, выходы блоков хранения произведений kα подключены к входам сумматора произведений kα, выходы блоков хранения произведений km и km соединены со входами сумматора произведений km и km, выход сумматора произведений kα подключен к первому входу блока сравнения, выход сумматора произведений km и km подключен ко второму входу блока сравнения, выход которого соединен со входами соответствующих элементов И локализации ошибки по модулю p, введены 2 регистра хранения остатков m и m, блок управления, n+2 регистра хранения скорректированного остатка α, n+2 выхода скорректированного остатка α, в блок формирования проекций, содержащий счетчик, добавлено n+2 элемента И формирования проекции α, 2 элемента И формирования проекций m и m, в блок управления, содержащий блок сравнения и n+2 элемента И локализации ошибки по модулю p, добавлены n+3 - битный циклический регистр сдвига, n+2 модулярных умножителя на P по модулю p, n+2 мультиплексора выбора корректного остатка α, причем выходы регистров хранения остатка α подключены ко входам блока управления, выходы регистров хранения остатков m и m подключены ко входам блока формирования проекций, вторые выходы которого подключены ко вторым входам соответствующих блоков хранения произведений kα и блоков хранения произведений km и km, выходы сумматора произведений kα и сумматора произведений km и km подключены ко входам блока управления, управляющий выход которого соединен с управляющим входом блока формирования проекций, выходы блока управления подключены к входам соответствующих регистров хранения скорректированного остатка α, выходы которых соединены с соответствующими выходами скорректированного остатка α, при этом старший, n+3-й бит управляющего входа блока формирования проекций соединен со входом счетчика, младший, 1-й бит подключен ко вторым входам элементов И формирования проекции α и m, 2-й бит подключен ко вторым входам элементов И формирования проекции α и m, оставшиеся n бит управляющего входа подключены соответственно ко вторым входам элементов И формирования проекции α, …, α, к первым входам элементов И формирования проекции α подключены входы блока формирования проекций, соединенные с регистрами хранения остатка α, к первым входам элементов И формирования проекции m и m подключены входы блока формирования проекций, соединенные с регистрами хранения остатков m и m, выходы элементов И формирования проекции α и элементов И формирования проекций m и m подключены к соответствующим первым выходам блока формирования проекций, вторые выходы которого соединены с выходом счетчика; в блоке управления первый вход блока сравнения, подключенный к выходу сумматора произведений kα, соединен со входами модулярных умножителей на P по модулю p, выход блока сравнения подключен ко входу n+3-битного циклического регистра сдвига, выход которого подключен к управляющему выходу блока управления, а также по битам, начиная с младшего, одновременно к входам элементов И локализации ошибки по модулю p и управляющим входам мультиплексоров выбора корректного остатка α соответственно; выходы регистров хранения остатка α, соединенные со входами блока управления, подключены к входам соответствующих элементов И локализации ошибки по модулю p, выходы которых подключены ко вторым входам соответствующих мультиплексоров выбора корректного остатка α, первые входы которых подключены к выходам соответствующих модулярных умножителей на P по модулю p, а выходы подключены к выходам блока управления и соединены с входами соответствующих регистров хранения скорректированного остатка α.
i
i
i
i
n+1
n+2
1
2
n
n+1
n+2
n+1
n+2
n+1
n+1
n+2
n+2
Сущность изобретения основана на следующем математическом аппарате. В системе остаточных классов любое число А<М однозначно представляется набором остатков α от деления А на взаимно простые модули СОК p, где α = A mod p,  - рабочий диапазон, i=[1,n]. Для обнаружения и исправления ошибки в СОК добавляют два избыточных модуля p и p и тогда диапазон избыточной системы остаточных классов составит  Разрешенным считается число А=(α, α, …, α, α,α), если А∈[0,М], в случае же А∈(М,Р] можно сказать, что число содержит ошибку. При этом М представляется в избыточной СОК и очевидно, что М=(0, …, 0, m,m), где m=Mmodp, m=Mmodp.
Для эффективной аппаратной реализации берут относительное приближенное значение
,
где  - константа выбранной СОК,  - мультипликативная инверсия. В данном случае для определения ошибки используется сравнение относительной величины  с константой .
1
i
i
1
1
1
i
2
1
n+2
В для обнаружения и исправления ошибок применяется метод проекций, который заключается в следующем. Предполагают, что ошибка допущена по первому модулю p и повторяют вычисления без участия этого модуля, т.е. берут в качестве избыточного диапазона , для нового диапазона вычисляют новые константы k, и в конечном счете сравнивают  с константой . В случае, если , то считают, что ошибка произошла по модулю p и для нахождения точного значения остатка А по модулю р умножают  на Р и находят остаток по модулю р. В случае  можно сказать, что ошибка еще присутствует и для ее обнаружения и исправления вместо p исключают р и проводят аналогичную проверку. Такие проекции строятся по всем модулям p, …, p.
1
Значения констант k берут с точностью N, необходимой для корректных вычислений.
i
i
n+1
n+2
i
i
n+1
n+1
n+2
n+2
i
i
n+1
n+1
n+2
n+2
i
i
Данное устройство обнаружения и коррекции ошибки модулярного кода поясняется фигурами 1-3. На фигуре 1 представлен общий вид устройства, которое содержит входы 1.i остатка α, где i=1, …, n+2, регистры 2.i хранения остатка α, регистры 3.1 и 3.2 хранения остатков m и m соответственно, блок формирования проекций 4, блоки 5.i хранения произведений kα, блоки 6.1 и 6.2 хранения произведений km и km соответственно, сумматор 7 произведений kα, сумматор 8 произведений km и km, блок управления 9, регистры 10.i храпения скорректированного остатка α, выходы 11.i скорректированного остатка α.
i
n+1
n+2
На фиг. 2 показано устройство блока формирования проекций 4, состоящего из элементов И 12.i формирования проекций α, элементов И 13.1 и 13.2 формирования проекций m и m соответственно и счетчика 14.
i
i
i
i
На фиг. 3 представлен блок управления 9, который состоит из блока сравнения 15, n+3-битного циклического регистра сдвига 16, модулярных умножителей 17.i на P по модулю p, элементов И 18.i локализации ошибки по модулю p, мультиплексоров 19.i выбора корректного остатка α.
1
2
3
4
5
6
7
i
i
1
2
3
4
5
6
7
Поясним работу устройства примерами. Пусть задана система остаточных классов с модулями р=2, p=3, р=5, р=7, р=11, р=13, р=17, следовательно n=5. Значение рабочего диапазона М=2310. В качестве сомножителей в модулярных умножителях 17.i на P по модулю p используются следующие значения: Р=255255, Р=170170, Р=102102, Р=72930, Р=46410, Р=39270, Р=30030.
1
1
1
1
1
1
i
1
1
1
1
1
1
В блок 5.1 хранения произведения kα записывают все произведения k⋅α при α=[0,p)=[0,1] и k, выбираемом из Таблицы 1 в зависимости от адреса со счетчика 14. Так, например, на вход блока 5.1 хранения произведения kα подается значение α=1 и адрес 0, тогда k=0.5 и на выход блока 5.1 хранения произведения kα будет подано значение 0.5.
2
2
2
2
2
2
2
3
3
3
3
3
3
3
4
4
4
4
4
4
4
5
5
5
5
5
5
5
6
6
6
6
6
6
6
6
6
6
6
6
6
7
7
7
7
7
7
7
7
7
7
7
7
7
Аналогично в блоке 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 хранения произведения km записаны все произведения k⋅α и k⋅m при α=[0,р)=[0,12], m={0,М mod р}={0,9} и k, выбираемом из Таблицы 1 в зависимости от адреса со счетчика 14. В блоках 5.7 хранения произведения kα и 6.2 хранения произведения km записаны все произведения k⋅α и k⋅m при α=[0,р)=[0,16], m={0,М mod р}={0,15} и k, выбираемом из Таблицы 1 в зависимости от адреса со счетчика 14.
i
i
6
6
7
7
i
6
7
i
i
i
6
6
7
7
i
6
7
i
1
1
Рассмотрим конструкцию и принцип работы n+3-битного циклического регистра сдвига 16. В начале работы он содержит значение "0111 …11". Старший бит, который на первом шаге равен 0 подается на счетчик 14, который подает адрес 0 па блоки 5.1-5.7 и 6.1-6.2 хранения произведений kα и km и km. Остальные биты данного числа подаются на элементы И 12.1-12.7 формирования проекций α, элементы И 13.1-13.2 формирования проекций m и m, элементы И 18.1-18.7 локализации ошибки по модулю p. В случае возникновения ошибки с блока сравнения 15 в n+3-битный циклический регистр сдвига 16 поступает сигнал и его значение меняется на "1011 …11". Тогда на счетчик 14 подается старший бит, равный 1 и адрес 1 подается на блоки 5.1-5.7 и 6.1-6.2 хранения произведений kα и km и km. Остальные биты данного числа подаются на элементы И 12.1-12.7 формирования проекций α, элементы И 13.1-13.2 формирования проекций m и m, элементы И 18.1-18.7 локализации ошибки по модулю p. При этом n+2-й бит со значением 0 подается на элемент И 12.1 формирования проекций α и элемент И 18.1 локализации ошибки по модулю p что соответствует вычеркиванию первого основания в методе проекций. Аналогично пулевой бит на каждом шаге сдвигается вправо до достижения значения "1111 …10", при этом нулевой бит во всех случаях в результате логического умножения подает на выход соответствующих элементов нулевое значение, что означает выбор проекции.
1
7
1
7
1
7
i
i
i
i
i
i
6
7
6
6
7
7
i
1
7
i
i
i
i
i
1
7
Рассмотрим работу устройства на примере значения А=(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α, на второй вход которых подается адрес 0. С выходов блоков 5.1-5.7 хранения произведений kα значения соответствующих произведений поступают на сумматор 7 произведений kα где происходит суммирование по модулю 1 и на выходе сформируется значение, эквивалентное 0.0039196. В это время аналогичные процессы проходят для коэффициентов m и m и на выходе сумматора 8 произведений km и km получится значение 0.0045249. В блоке сравнения 15 данные значения сравниваются и поскольку 0.0039196<0.0045249, то на выходе блока сравнения 16 будет значение 1, которое поступает на входы элементов И 18.1-18.7 локализации ошибки по модулю p, на вход которых также поступают значения 1,0,1,6,10,12,12 с выходов регистров 2.1-2.7 хранения остатков α, …, α. С выхода n+3-битного циклического регистра сдвига 16 на входы элементов И 18.1-18.7 локализации ошибки по модулю p и на управляющие входы мультиплексоров 19.1-19.7 выбора корректного остатка α поступают значения 1. Таким образом, мультиплексоры 19.1-19.7 выбора корректного остатка α подают значения 1,0,1,6,10,12,12 с выходов элементов И 18.1-18.7 локализации ошибки по модулю p на соответствующие регистры 10.1-10.7 хранения скорректированного остатка α, откуда значения поступают на выходы 11.1-11.7 скорректированного остатка α, …, α. Таким образом на выход устройства подается корректное значение.
1
7
i
i
1
7
1
1
Рассмотрим случай, когда по третьему основанию возникла ошибка и на входы 1.1-1.7 остатков α, …, α поступило значение (1,0,4,6,10,12,12)=410409. Работа устройства происходит аналогично и на выходе сумматора 7 произведений kα формируется сигнал, эквивалентный 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.
i
i
6
6
7
7
Аналогично происходят вычисления сумм и на выходе сумматора 7 произведений kα формируется сигнал, эквивалентный 0.6078392, на выходе сумматора 8 произведений km и km формируется сигнал, эквивалентный 0.0090497 и поскольку 0.6078392>0.0090497, то на выходе блока сравнения 16 будет значение 0, что соответствует наличию ошибки и в n+3-битном циклическом регистре сдвига 16 происходит сдвиг и формирование второй проекции.
i
i
6
6
7
7
В результате вычислений по второй проекции на выходе сумматора 7 произведений kα формируется сигнал, эквивалентный 0.4117588, на выходе сумматора 8 произведений km и km формируется сигнал, эквивалентный 0.0135747 и поскольку 0.4117588>0.0135747, то на выходе блока сравнения 16 будет значение 0, что соответствует наличию ошибки и в n+3-битном циклическом регистре сдвига 16 происходит сдвиг и формирование третьей проекции.
i
i
6
6
7
7
i
i
3
3
3
3
3
i
i
i
1
7
В результате вычислений по третьей проекции па выходе сумматора 7 произведений kα формируется сигнал, эквивалентный 0.0195980, на выходе сумматора 8 произведений km и km формируется сигнал, эквивалентный 0.0226244 и поскольку 0.0195980<0.0226244, то на выходе блока сравнения 16 будет значение 1, что соответствует отсутствию ошибки и следующий сдвиг в n+3-битном циклическом регистре сдвига 16 не происходит. Следовательно ошибка произошла по третьему основанию. Значение 0.0195980 с выхода сумматора 7 произведений kα, поступает па модулярный умножитель 17.3 на Р по модулю р, на выходе которого формируется значение 1. Поскольку значение, подаваемое на управляющий вход мультиплексора 19.3 выбора корректного остатка α, равно нулю, то на выход подается значение 1 с выхода модулярного умножителя 17.3 на Р по модулю р. На остальные управляющие входы мультиплексоров 19.1-19.2, 19.4-19.7 выбора корректного остатка α подаются значения 1 и на выход подаются значения с соответствующих элементов И 18.1-18.2, 18.4-18.7 локализации ошибки по модулю p, которые равны полученным α, которые хранятся в регистрах 2.1-2.7 хранения остатков Таким образом на выходы 11.1-11.7 скорректированного остатка α, …, α поступают значения 1,0,1,6,10,12,12, что соответствует исправленному значению.
Устройство обнаружения и коррекции ошибки модулярного кода