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

Чертежи

Описание

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

Известно устройство расширения оснований модулярного кода [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, любой полином А(х), удовлетворяющий условию

где

где α_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) в этом случае определяется выражением

где

Анализ выражения (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).

Тогда для вычисления первого контрольного остатка

Вычисление второго контрольного остатка

После этого вычисленные остатки

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

Структура устройства коррекции ошибок в модулярном коде на основе расширения системы оснований представлена на фиг. 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 для хранения

Причем вход устройства подключен к входам регистров 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) соответственно, поступают значения

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

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

Вычисленное значение остатка

Вычисленное значение остатка

С выхода сумматора 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-го регистра, выход корректирующих сумматоров являются выходом устройства.