Устройство коррекции ошибок в модулярном коде на основе расширения системы оснований Российский патент 2018 года по МПК G06F7/72 G06F11/08 

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

Известно устройство расширения оснований модулярного кода [1] (Патент РФ №2562366, Устройство расширения оснований модулярного кода), которое имеет вход устройства, первый блок умножителей, который содержит n умножителей по модулю p_i(z), где i=1, 2,…, n, первый блок памяти для хранения ортогональных весов m_i(z); второй блок умножителей, который содержит n умножителей по модулю p_n+1(z), второй блок памяти для хранения , сумматор по модулю два, выход устройства.

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

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

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

Указанный технический результат достигается за счет введения блока регистров, состоящего из n+2 регистров, предназначенных для хранения остатков, где n - количество информационных оснований ПСКВ, n+1 и n+2 - контрольные основания ПСКВ, блока вычисления второго контрольного остатка, структура которого соответствует структуре прототипа [1], двух сумматоров вычисления синдрома ошибки, блока памяти, предназначенного для хранения вектора ошибки, n+2 корректирующих сумматоров, с помощью которых происходит исправление ошибки по модулю два.

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

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

В ПСКВ в качестве оснований системы используются неприводимые полиномы p_i(x), где i=1, 2, …, n, любой полином А(х), удовлетворяющий условию

где - рабочий диапазон системы, degP_раб(x) - степень полинома, можно однозначно представить в виде набора остатков

где α_i(x)=А(x)modp_i(x); i=1, 2, …, n.

Для обнаружения и исправления однократных ошибок в модулярном коде полинома А(x)=(α₁(x),α₂(x),…,α_n(x)) вводят два контрольных основания p_n+1(x) и p_n+2(x), которые удовлетворяют условию

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

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

где - полный диапазон кода ПСКВ; Δα_j(z) - глубина ошибки по j-му основанию кода ПСКВ; B_j(z) - ортогональный базис j-го основания кода ПСКВ; j=1, 2, …, n+2.

Анализ выражения (4) показывает, что местоположение ошибочного полинома A^*(z) относительно рабочего диапазона P_раб(z) определяется величиной второго слагаемого.

Рассмотрим алгоритм перевода из безызбыточного полиномиального модулярного кода в позиционный код согласно КТО имеем

где В_i(z)=m_i(z)P_i(z) - ортогональный базис; m_i(z) - вес ортогонального базиса; - ранг кода ПСКВ.

Воспользуемся определением ортогональных базисов, тогда выражение (5) можно представить в виде

Умножение остатка α_i(z) на вес ортогонального базиса m_i(z) выполняется по модулю p_i(z), что позволяют отказаться от вычисления ранга r_A(z) при использовании китайской теоремы об остатках при переводе к позиционному коду.

Чтобы осуществить поиск и коррекцию ошибки в коде ПСКВ на основе расширения системы оснований, необходимо, используя остатки по рабочим основаниям (α₁(z), …, α_n(z)), вычислить остатки по контрольным основаниям p_n+1(z) и p_n+2(z).

Тогда для вычисления первого контрольного остатка по основанию p_n+1(z) используем следующее выражение

Вычисление второго контрольного остатка по основанию p_n+2(z) определяется выражением

После этого вычисленные остатки и складываются по модулю два с остатками α_n+1(z) и α_n+2(z), которые входят в состав комбинации кода ПСКВ A(z)=(α₁(z), α₂(z), …, α_n+1(z), α_n+2(z)). В результате получается синдром ошибки, который определит местоположение и глубину ошибки в коде

Если полученный синдром будет равен нулю, то это означает, что код ПСКВ не содержит ошибки. Если синдром будет отличен от нуля, то это будет означать, что код ПСКВ содержит ошибку.

Структура устройства коррекции ошибок в модулярном коде на основе расширения системы оснований представлена на фиг. 1.

Устройство содержит блок регистров, состоящий из n+2 регистров 1.1, …, 1.n+2, который подключен к входу устройства, на который подается код ПСКВ. Регистры предназначены для хранения остатков кода ПСКВ. Для вычисления остатков по контрольным основаниям используется блок 2.1 вычисления первого контрольного остатка и блок 2.2 вычисления второго контрольного остатка. Структура этих блоков одинаковая. Каждый из блоков содержит первый 3.m блок умножителей, где m=1, 2, в состав которого входят n умножителей по модулю p_i(z) 3.m.i, где i=1, 2, …, n, первый блок 4.m памяти для хранения ортогональных весов m_i(z); второй блок умножителей 5.m, который содержит n умножителей по модулю p_n+m(z), второй блок памяти 6.m для хранения , сумматор 7.m по модулю два. Устройство содержит также два сумматора вычисления синдрома ошибки 8.1 и 8.2, блок памяти 9, предназначенный для хранения вектора ошибки, n+2 корректирующих сумматора 10.1, …, 10.n+2, выходы которых являются выходом устройства.

Причем вход устройства подключен к входам регистров 1.1, …, 1.n+2. Выход i-го регистра 1.i, где i=1, 2, …, n, предназначенного для хранения информационного остатка α_i(z), подключен к первому входу соответствующего умножителя по модулю p_i(z) 3.1.i блока 2.1 вычисления первого контрольного основания и 3.2.i блока 2.2 вычисления второго контрольного основания. Ко второму входу этих умножителей по модулю p_i(z) 3.1.i и 3.2.i соответственно подключены выходы первых блоков памяти 4.1 и 4.2. Выходы умножителей по модулю p_i(z) 3.1.i и 3.2.i подключены соответственно к первым входам умножителей 5.1.i по модулю p_n+1(z) и 5.2.i по модулю p_n+2(z), входящих в состав второго блока умножителей 5.1 и 5.2 соответственно. Вторые входы умножителей 5.1.i по модулю p_n+1(z) и 5.2.i по модулю p_n+2(z) соединены с выходами второго блока памяти 6.1 и 6.2, а выходы подключены к входам сумматора по модулю два 7.1 и 7.2 блока 2.1 вычисления первого контрольного основания и блока 2.2 вычисления второго контрольного основания. Выходы сумматоров по модулю два 7.1 и 7.2 соответственно подключены к первым входам сумматоров вычисления синдрома ошибки 8.1 и 8.2, вторые входы которых соединены с выходами регистров 1.n+1 и 1.n+2. Выходы сумматоров вычисления синдрома ошибки 8.1 и 8.2 подключены соответственно к входам блока памяти 9, выходы которого подключены соответственно ко вторым входам корректирующих сумматоров 10.1, …, 10.n+2. Первые входы корректирующих сумматоров 10.1 …, 10.n+2 подключены к соответствующим выходам регистров 1.1-1.n+2. Выход корректирующих сумматоров 10.1, …, 10.n+2 являются выходом устройства.

Устройство работает следующим образом. На вход устройства поступает модулярный код α₁(z), α₂(z), …, α_n(z), α_n+1(z), α_n+2(z). Данные остатки записываются в регистры 1.1-1.n+2. Информационный остаток α_i(z), где i=1, 2, …, n с выхода регистра 1.i подается на первый вход умножителя 3.1.i, первого блока 3.1 умножителей блока 2.1 вычисления первого контрольного остатка и на первый вход умножителя 3.2.i, первого блока 3.2 умножителей блока 2.2 вычисления второго контрольного остатка. На второй вход умножителя по модулю p_i(z) 3.1.i и 3.2.i подается с выходов первых блоков памяти 4.1 и 4.2 значения базиса m_i(z). С выхода умножителя по модулю p_i(z) 3.1.i и 3.2.i соответственно первого блока умножителей 3.1 и 3.2 снимаются значения α_i(z)m_i(z)modp_i(z), которые затем подаются на первый вход умножителя по модулю p_n+1(z) 5.1.i второго блока умножителей 5.1 и вход умножителя по модулю p_n+2(z) 5.2.i второго блока умножителей 5.2. На вторые входы этих умножителей, выполняющих умножение по модулю p_n+1(z) и p_n+2(z) соответственно, поступают значения , и , которые хранились в втором блоке памяти 6.1 и 6.2. С выхода умножителя по модулю p_n+1(z) 5.1.i, второго блока умножителей 5.1 блока 2.1 вычисления первого контрольного остатка снимается значение

С выхода умножителя по модулю p_n+2(z) 5.2.i, второго блока умножителей 5.2 блока 2.2 вычисления второго контрольного остатка снимается значение

Вычисленные значения произведения соответственно подаются на входы сумматора 7.1 и 7.2 по модулю 2. На выходе сумматора 7.1 по модулю два блока 2.1 вычисления первого контрольного остатка появляется значение остатка в расширенной системе оснований. На выходе сумматора 7.2 по модулю два блока 2.2 вычисления второго контрольного остатка появляется значение остатка в расширенной системе оснований.

Вычисленное значение остатка поступает на первый вход сумматора 8.1 вычисления синдрома ошибки. На второй вход сумматора 8.1 вычисления синдрома с выхода регистра 1.n+1 подается значение контрольного основания , комбинации поступившей на вход устройства.

Вычисленное значение остатка поступает на первый вход сумматора 8.2 вычисления синдрома ошибки. На второй вход сумматора 8.1 вычисления синдрома с выхода регистра 1.n+2 подается значение контрольного основания α_n+2(z), комбинации, поступившей на вход устройства.

С выхода сумматора 8.1 вычисления синдрома ошибки значение синдром ошибки S₁ поступает на первый вход блока памяти 9. С выхода сумматора 8.2 вычисления синдрома ошибки значение синдром ошибки S₂ поступает на второй вход блока памяти 9. С выхода блока памяти 9 снимается значение, которое предназначено для исправления ошибки в коде ПСКВ. Данное значение поступает на вторые входы корректирующих сумматоров по модулю два 10.1, …, 10.n+2. На первые входы этих сумматоров по модулю два 10.1, …, 10.n+2 подаются значения остатков кода ПСКВ α₁(z), α₂(z), …, α_n(z), α_n+1(z), α_n+2(z) с выходов регистров 1.1, …, 1.n+2 соответственно. С выходов сумматоров по модулю два 10.1, …, 10.n+2 откорректированный код ПСКВ подается на выход устройства.

Рассмотрим пример. Пусть задано расширенное поле Галуа GF(2⁴), в котором определены информационные основания p_i(z)=z+1, p₂(z)=z²+z+1, p₃(z)=z⁴+z³+z²+z+1, расширяем систему оснований за счет введения двух контрольных оснований p₄(z)=z⁴+z³+1 и р₅(z)=z⁴+z+1. В этом случае .

При этом полный диапазон составляет:

Р_полн(z)=z¹⁵+1.

Р_конт45(z)=z⁸+z⁷+z⁵+z⁴+z³+z+1.

Определим значения рабочих оснований P_i(z) и m_i(z):

P₁(z)=p₂(z)⋅p₃(z)=z⁶+z⁴+z³+z²+1

P₂(z)=p₁(z)⋅p₃(z)=z⁵+1

P₃(z)=p₁(z)⋅p₂(z)=z³+1,

m₁(z)=1; m₂(z)=z+1; m₃(z)=z²+z+1.

Следовательно, ортогональные базисы В_i(z) соответственно равны

B₁(z)=m₁(z)⋅P₁(z)=z⁶+z⁴+z³+z²+1;

B₂(z)=m₂(z)⋅P₂(z)=z⁶+z⁵+z+1;

B₃(z)=m₃(z)⋅P₃(z)=z⁵+z⁴+z³+z²+z+1.

Воспользуемся полином A(z)=z⁶. В модулярном коде полином представляет A(z)=(1, 1, z).

Расширяем систему оснований за счет введения двух контрольных оснований p₄(z)=z⁴+z³+1 и p₅(z)=z⁴+z+1.

Первое основание расширения системы p_n+1(z)=р₄(z)=z⁴+z³+1

Вычислим значения P_i(z)modp₄(z). Тогда имеем

Определим произведение они соответственно равны

Подставляем полученные значения в выражение (7)

Результат расширения по основанию p_n+1(z)=p₄(z)=z⁴+z³+1 получили остаток α₄(z)=z³+z²+z+1. Проведем проверку и определим остаток исходного полинома

Второе основание расширения p_n+2(z)=p₅(z)=z⁴+z+1.

Вычислим значения P_i(z)modp₅(z). Тогда имеем

Определим произведение Они соответственно равны

Подставляем полученные значения в выражение (8)

Результат расширения по основанию p_n+2(z)=p₅(z)=z⁴+z+1 - остаток α₅(z)=z³+z². Проведем проверку и определим остаток исходного полинома

Таким образом, расширенная комбинация избыточного кода ПСКВ будет иметь вид

A(z)=(1, 1, z, z³+z², z³+z²+z+1).

Если на вход устройства и обнаружения ошибки, использующего разработанный алгоритм расширения системы оснований, поступит A(z)=(1, 1, z, z³+z², z³+z²+z+1), то синдром ошибки будет равен

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

Рассмотрим ситуацию, когда проверяемая комбинация ПСКВ содержит ошибку по первому основанию и ее глубина равна Δα(z)=1. Тогда значение первого остатка равно Ошибочная комбинация модулярного кода ПСКВ имеет вид

A^*(z)=(0, 1, z, z³+z²,z³+z²+z+1).

Определим произведение для данной ошибочной комбинации кода ПСКВ

Вычислим первый контрольный остаток, подставив значения в выражение (7)

Результатом расширения по основанию p_n+1(z)=p₄(z)=z⁴+z³+1 является остаток .

Вычислим второй контрольный остаток, подставив значения в выражение (8)

Результатом расширения по основанию p_n+2(z)=p₅(z)=z⁴+z+1 является остаток

Выполним проверку комбинации путем вычисления синдрома ошибки, имеем

Проверяемая комбинация содержит ошибки, так как синдром ошибки отличен от нуля. В таблице 1 приведены значения глубины и местоположения ошибки в коде ПСКВ по рабочим основаниям и соответствующего им синдрома ошибки S₁(z) и S₂(z). Данные в таблице приведены в шестнадцетеричной системе счисления. По значению синдрома ошибки определяем, что ошибка произошла по первому основанию p₁(z)=z+1, а ее глубина равна Δα_i(z)=1. Значит, вектор ошибки будет равен e(z)=(1, 0, 0, 0, 0).

Для коррекции ошибки необходимо данный вектор ошибки сложить с ошибочной комбинацией кода ПСКВ. Имеем

Если ошибка произойдет по первому контрольному основанию p₄(z)=z⁴+z³+1, то значение первой составной синдрома S₁(z) будет показывать глубину ошибки, а значение S₂(z) будет равняться нулю.

Если ошибка произойдет по второму контрольному основанию p₅(z)=z⁴+z+1, то значение второй составной синдрома S₂(z) будет показывать глубину ошибки, а значение первой составляющей синдрома S₁(z) будет равняться нулю.

Изобретение относится к вычислительной технике и, в частности к непозиционным компьютерам. Технический результат заключается в обеспечении коррекции ошибок в кодовой комбинации ПСКВ на основе выполнения операции расширения оснований. Технический результат достигается за счет введения блока регистров, состоящих из n+2 регистров, предназначенных для хранения остатков, где n - количество информационных оснований ПСКВ, n+1 и n+2 - контрольные основания ПСКВ, блока вычисления второго контрольного остатка, структура которого соответствует структуре прототипа, двух сумматоров вычисления синдрома ошибки, блока памяти, предназначенного для хранения вектора ошибки, n+2 корректирующих сумматоров, с помощью которых происходит исправление ошибки по модулю два. 1 ил.

Устройство коррекции ошибок в модулярном коде на основе расширения системы оснований содержит первый блок умножителей, который содержит n умножителей по модулю p_i(z), где i=1, 2, …, n, первый блок памяти, для хранения ортогональных весов m_i(z), второй блок умножителей, который содержит n умножителей по модулю p_n+1(z), второй блок памяти для хранения , сумматор по модулю два, которые входят в состав блока вычисления первого контрольного остатка, при этом на первый вход i-го умножителя по модулю p_i(z) первого блока умножителей подается остаток α_i(z) кода полиномиальной системы классов вычетов ПСКВ, второй вход i-го умножителя по модулю p_i(z) соединен с выходом первого блока памяти, а выход i-го умножителя по модулю p_i(z) подключен к первому входу i-го умножителя по модулю p_n+1(z) второго блока умножителей, при этом второй вход умножителя по модулю p_n+1(z) подключен к выходу второго блока памяти, выходы умножителей второго блока умножителей подсоединены к входам сумматора по модулю два, отличающееся тем, что в устройство введены блок вычисления второго контрольного остатка, структура которого аналогична блоку вычисления первого контрольного остатка, n+2 регистра, предназначенных для хранения остатков (α₁(z), α₂(z), …, α_n(z), α_n+1(z), α_n+2(z)) кода ПСКВ, два сумматора вычисления синдрома ошибки, блок памяти, предназначенный для хранения вектора ошибки, n+2 корректирующих сумматора, выходы которых являются выходом устройства, входы регистров подключены к входу устройства, на который поступает код ПСКВ, выход i-го регистра подключен к первому входу i-го умножителя по модулю p_i(z) блока вычисления первого контрольного остатка и блока вычисления второго контрольного остатка, а выходы сумматоров по модулю два блока вычисления первого контрольного остатка и блока вычисления второго контрольного остатка подключены соответственно к первым входам первого и второго сумматоров вычисления синдрома ошибки, второй вход первого сумматора вычисления синдрома ошибки подключен к выходу (n+1)-го регистра, второй вход второго сумматора вычисления синдрома ошибки подключен к выходу (n+2)-го регистра, выходы сумматоров вычисления синдрома ошибки подключены к входам блока памяти, выходы которого подключены соответственно ко вторым входам n+2 корректирующих сумматоров, первые входы j-го корректирующего сумматора, где j=1, …, n+2, подключены к выходу j-го регистра, выход корректирующих сумматоров являются выходом устройства.