УСТРОЙСТВО ДЛЯ КОРРЕКЦИИ ОШИБОК В ПОЛИНОМИАЛЬНОЙ СИСТЕМЕ КЛАССОВ ВЫЧЕТОВ Российский патент 2012 года по МПК G06F11/08 

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

Известно устройство для обнаружения и исправления ошибок в системе остаточных классов вычетов (а.с. 714399, кл. G06F 11/08, 1980 г.), содержащее регистр, вход которого соединен со входом устройства, два блока модульной свертки, три сумматора, причем выход третьего сумматора является выходом устройства, блок памяти.

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

Основной задачей является уменьшение объема оборудования.

Техническим результатом, достигнутым при осуществлении заявленного изобретения, является снижение объема оборудования.

Указанный технический результат достигается за счет применения полиномиальной системы классов вычетов (ПСКВ) и нового алгоритма вычисления синдрома ошибки, в результате чего вводится модуль вычисления синдрома ошибки, входы которого подключены в первому, второму и третьему выходам регистра, при этом выходы модуля вычисления синдрома ошибки подсоединены к входам блока памяти. Технический результат достигается тем, что в устройство для коррекции ошибок в полиномиальной системе классов вычетов, содержащее регистр, вход которого является входом устройства, блок памяти и выходной сумматор, первый, второй и третий входы которого соединены соответственно с первым, вторым и третьим выходами регистра, а четвертый вход соединен с выходом блока памяти, согласно изобретению введен модуль вычисления синдрома ошибки, входы которого подключены в первому, второму и третьему выходам регистра, при этом выходы модуля вычисления синдрома ошибки подсоединены к входам блока памяти. При этом модуль вычисления синдрома ошибки содержит 15 входов, первый и второй блок вычисления синдрома ошибки, причем каждый такой блок содержит по четыре многовходовых сумматора, вход первого многовходового сумматора по модулю два первого блока вычисления синдрома ошибки подключен к 1, 2, 4, 8 входам модуля, вход второго многовходового сумматора по модулю два первого блока вычисления синдрома ошибки подключен к 3, 5, 9 входам модуля, вход третьего многовходового сумматора по модулю два первого блока вычисления синдрома ошибки подключен к 6 и 10 входам, вход четвертого многовходового сумматора по модулю два первого блока вычисления синдрома ошибки подключен к 7 и 11 входам модуля, вход первого многовходового сумматора по модулю два второго блока вычисления синдрома ошибки подключен к 1, 4, 7, 12 входам модуля, вход второго многовходового сумматора по модулю два второго блока вычисления синдрома ошибки подключен к 2, 4, 5, 7, 13 входам модуля, вход третьего многовходового сумматора по модулю два второго блока вычисления синдрома ошибки подключен к 3, 5, 6, 14 входам модуля, вход четвертого многовходового сумматора по модулю два второго блока вычисления синдрома ошибки подключен к 6, 7, 15 входам, при этом выходы многовходовых сумматоров являются соответствующими выходами модуля вычисления синдрома.

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

В этом случае любой полином A(z), удовлетворяющий условию

где - рабочий диапазон системы,

ord A(z) - степень полинома A(z),

можно представить в виде набора остатков, т.е.

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

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

Введение одного контрольного основания p_n+1(z), удовлетворяющего условию

позволяет осуществлять процедуры обнаружения и коррекции однократной ошибки, возникшей в кодовой комбинации (2).

Под однократной ошибкой будем понимать искажение одного разряда в кодовой комбинации (2), представленной в ПСКВ.

Для реализации процедуры обнаружения и коррекции ошибок по n рабочим основаниям ПСКВ необходимо вычислить два дополнительных остатка α_n+1(z) и

α_n+2(z).

При этом значение первого остатка определяется согласно выражению

где Σ - суммирование по модулю два.

Второй остаток α_n+2(z) берется по модулю контрольного основания p_n+1(z) согласно

где i(z) - полиномиальная форма i-го порядкового номера,

Σ - суммирование по модулю два.

Тогда полином A(z), представленный в ПСКВ, имеет вид

При этом n остатков α₁(z), …, α_n(z) являются информационными, а два последних остатка α_n+1(z), α_n+2(z) - контрольными.

Для обнаружения ошибки в переданной кодовой комбинации вычисляются значения

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

где операция ⊕ - суммирование по модулю два.

Если синдром ошибки δ₁(z)=0 и δ₂(z)=0, то данная комбинация не содержит ошибки. В противном случае (δ₁(z)≠0 и δ₂(z)≠0) принятая комбинация ПСКВ является запрещенной, т.е. ошибочной. По величине δ₁(z)≠0 и δ₂(z)≠0 можно однозначно определить местоположение ошибочного разряда и откорректировать результат.

Функциональная схема устройства представлена на фигуре 1. Она включает: регистр 1, вход 2, модуль вычисления синдрома ошибки 3, содержащий первый блок вычисления синдрома ошибки 4, второй блок вычисления синдрома ошибки 5, блок памяти 6, сумматор 7.

При этом вход регистра 1 подключен к входу устройства 2. Первый выход регистра 1 подсоединен к первым входам первого 4 и второго 5 блоков вычисления синдрома ошибки, входящих в состав модуля вычисления синдрома ошибки 3, и сумматора 7. Второй выход регистра 1 подключен ко второму входу первого блока вычисления синдрома ошибки 4 и второму входу сумматора 7. Третий выход регистра 1 подключается ко второму входу второго блока вычисления синдрома ошибки 5 и третьему входу сумматора 7. Выходы блоков вычисления синдрома ошибки 4 и 5 подсоединены к входам блока памяти 6, выход которого подключен к четвертому входу сумматора 7. Выход сумматора 7 является выходом устройства.

Структура модуля вычисления синдрома ошибки 3 представлена на фигуре 2. Модуль содержит входы 8-22, подключенные к выходам регистра 1, первый и второй блоки вычисления синдрома ошибки. Первый блок вычисления синдрома ошибки содержит многовходовые сумматоры по модулю два 23-26, имеющие соответствующие выходы 27-30. Второй блок вычисления синдрома ошибки содержит четыре многовходовых сумматора по модулю два 31-34, имеющих выходы 35-38 соответственно. Устройство работает следующим образом.

На вход 2 устройства поступает контролируемая кодовая комбинация, представленная в полиномиальной форме согласно (6). Данная комбинация A(z)=(α₁(z), α₂(z),…, α_n(z), α_n+1(z), α_n+2(z)) записывается в регистр 1. На вход первого блока вычисления синдрома ошибки 4, входящего в модуль вычисления синдрома ошибки 3, с первого выхода регистра 1 поступает значение (α₁(z), α₂(z), …, α_n(z)), а на второй вход - со второго выхода регистра 1 - значение α_n+1(z). Данный блок вычисления синдрома ошибки реализует выражение (9).

На первый вход второго блока вычисления синдрома ошибки 5, входящего в модуль вычисления синдрома ошибки 3, с первого выхода регистра 1 также поступают n информационных остатков α₁(z), …, α_n(z), а на второй вход - с третьего выхода регистра 1 подается значение α_n+2(z). Данный блок вычисления синдрома ошибки реализует выражение (10).

Величины δ₁(z) и δ₂(z) в двоичном виде поступают на входы блока памяти 6 и выбирают оттуда соответствующую константу ошибки. Эта константа ошибки поступает в сумматор 7, где суммируется с искаженным значением A^∗(z), представленным в непозиционном виде из регистра 1. Исправленное значение A(z) с выхода сумматора 7 подается на выход устройства.

Рассмотрим пример. Пусть в качестве информационных оснований ПСКВ выбраны следующие n=3 неприводимых полинома

p₁(z)=z+1; p₂(z)=z²+z+1; p₃(z)=z⁴+z³+z²+z+1.

Данные основания образуют рабочий диапазон

.

В качестве контрольного основания выбираем неприводимый полином p_n+1(z)=p₄(z)=z⁴+z+1.

Пусть на вход устройства поступила разрешенная комбинация A(z)=z⁵=(1, z+1, 1). Определим значения α_n+1(z) и α_n+2(z), используя выражения (4) и (5) соответственно.

Имеем

,

Тогда на вход устройства подается кодовая комбинация

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

Так как данная комбинация не содержит ошибки, то значения δ₁(z)=0 и δ₂(z)=0.

Пусть ошибка произошла в основании p₃(z), а ее глубина Δα₃(z)=z³. Тогда на вход устройства поступает комбинация

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

Первый блок вычисления синдрома ошибки 4 определяет значение согласно (7). Имеем

.

А затем, согласно (9), вычисляет синдром

δ₁(z)=z+1+z³+z+1=z³.

Второй блок вычисления синдрома ошибки 5 определяет значение согласно (8):

Тогда значение синдрома равно

δ₂(z)=z²+z³+z²+z+1=z³+z+1.

В таблице 1 представлены значения синдромов ошибок δ₁(z) и δ₂(z) и соответствующие им константы ошибок Δконст.

В соответствии с полученными данными δ₁(z)=z³ и δ₂(z)=z³+z+1 из блока памяти 6 будет выбрана константа ошибки Δконст=(0, 0, z³, 0 0). Данная константа ошибки подается на четвертый вход сумматора 7, где складывается по модулю два с представлением A^∗(z). Тогда имеем откорректированное значение кода ПСКВ в следующем виде:

A(z)=A^∗(z)+Δконст=(1, z+1, z³+1, z+1, z²)+(0, 0, z³, 0, 0)=(1, z+1, 1, z+1, z²).

Структура модуля вычисления синдрома ошибки 3 представлена на фигуре 2. Модуль содержит входы 8-14, подключенные к выходам регистра 1, первый и второй блоки вычисления синдрома ошибки. Данный модуль предназначен для работы с рабочими основаниями p₁(z)=z+1, p₂(z)=z²+z+1, p₃(z)=z⁴+z³+z²+z+1 и контрольным p₄(z)=z⁴+z+1. На входы 8, 9-10, 11-14 поступают значения остатков α₁(z), α₂(z), α₃(z) по рабочим основаниям, снимаемые с первого выхода регистра 1. На входы 15-18 подается значение остатка α₄(z) со второго выхода регистра 1. На входы 19-22 подается значение остатка α₅(z) с третьего выхода регистра. Все остатки подаются в двоичном параллельном коде. Три младших разряда остатков α₁(z), α₂(z), α₃(z), α₄(z) и α₅(z) поступают соответственно на 8, 9, 11, 15 и 19 входы. Первый блок вычисления синдрома ошибки содержит многовходовые сумматоры по модулю два 23-26, имеющие соответствующие выходы 27-30. Входы первого сумматора 23 по модулю два подключены к входам 8, 9, 11, 15. Входы второго сумматора 24 по модулю два подключены к входам 10, 12, 16. Входы третьего сумматора 25 по модулю два соединены с входами 13, 17. Входы четвертого сумматора 26 по модулю два соединены с входами 14 и 18. С выходов этих сумматоров по модулю два снимается параллельный двоичный код первого синдрома ошибки δ₁(z). Младший разряд δ₁(z) снимается с выхода 27, а старший - с выхода 30 соответственно.

Второй блок вычисления синдрома ошибки содержит четыре многовходовых сумматора по модулю два 31-34, имеющих выходы 35-38 соответственно. Входы первого сумматора 31 по модулю два подключены ко входам 8, 11, 14, 19. Входы второго сумматора 32 по модулю два подключены к входам 9, 11, 12, 14, 20. Входы третьего сумматора 33 по модулю два подключены к входам 10, 12, 13, 21. Входы четвертого сумматора 34 по модулю два подключены к входам 13, 14, 22. Значение второго синдрома ошибки δ₂(z) снимается в параллельном двоичном коде с выходов 35-38, при этом младший разряд - с выхода 35, а старший - с выхода 38 соответственно.

Рассмотрим работу модуля вычисления синдрома ошибки при отсутствии ошибок, то есть когда A(z)=(1, z+1, 1, z+1, z²). Значение сигналов, поступивших на входы, представлены в таблице 2.

В таблице 3 представлены значения сигналов на входах и выходах первого блока вычисления синдрома ошибки. Суммирование производится по модулю два.

В таблице 4 представлены значения сигналов на входах и выходах второго блока вычисления синдрома ошибки. Суммирование производится по модулю два.

В этом случае синдромы ошибки равны δ₁(z)=0 и δ₂(z)=0. Следовательно, комбинация не содержит ошибки.

Пусть на вход устройства подана ошибочная комбинация A^*(z)=(1, z+1, z³+1, z+1, z²). Значения сигналов на входах 8-22 приведены в таблице 5.

В таблице 6 представлены значения сигналов на входах и выходах первого блока вычисления синдрома ошибки.

В таблице 7 представлены значения сигналов на входах и выходах второго блока вычисления синдрома ошибки.

В результате получили δ₁(z)=1000=z³ и δ₂(z)=1011=z³+z+1. Полученные данные совпали с приведенными примерами.

Таблица 1 δ₁(z) δ₂(z) Константа ошибки Δконст 0 0 (0, 0, 0, 0, 0) 1 1 (1, 0, 0, 0, 0) 1 z (0, 1, 0, 0, 0) z z² (0, z, 0, 0, 0) 1 z+1 (0, 0, 1, 0, 0) z z²+z (0, 0, z, 0, 0) z² z³+z² (0, 0, z², 0, 0) z³ z³+z+1 (0, 0, z³, 0, 0)

Таблица 2 Входы 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 Сигналы 1 1 1 1 0 0 0 1 1 0 0 0 0 1 0

Таблица 5 Входы 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 Сигналы 1 1 1 1 0 0 1 1 1 0 0 0 0 1 0

Изобретение относится к вычислительной технике и может быть использовано для обнаружения и коррекции ошибок для передачи информации. Техническим результатом является снижение объема оборудования. Устройство содержит регистр, модуль вычисления синдрома ошибки, блок памяти, сумматор, при этом модуль вычисления синдрома ошибки содержит два блока вычисления синдрома ошибки, каждый из которых содержит четыре многовходовых сумматора по модулю два. 2 ил., 7 табл.

Устройство для коррекции ошибок в полиномиальной системе классов вычетов, содержащее регистр, вход которого является входом устройства, блок памяти и выходной сумматор, первый, второй и третий входы которого соединены соответственно с первым, вторым и третьим выходами регистра, а четвертый вход соединен с выходом блока памяти, отличающееся тем, что в него введен модуль вычисления синдрома ошибки, входы которого подключены в первому, второму и третьему выходам регистра, выходы модуля вычисления синдрома ошибки подсоединены к входам блока памяти, при этом модуль вычисления синдрома ошибки содержит 15 входов, первый и второй блок вычисления синдрома ошибки, причем каждый такой блок содержит по четыре многовходовых сумматора, вход первого многовходового сумматора по модулю два первого блока вычисления синдрома ошибки подключен к 1, 2, 4, 8 входам модуля, вход второго многовходового сумматора по модулю два первого блока вычисления синдрома ошибки подключен к 3, 5, 9 входам модуля, вход третьего многовходового сумматора по модулю два первого блока вычисления синдрома ошибки подключен к 6 и 10 входам, вход четвертого многовходового сумматора по модулю два первого блока вычисления синдрома ошибки подключен к 7 и 11 входам модуля, вход первого многовходового сумматора по модулю два второго блока вычисления синдрома ошибки подключен к 1, 4, 7, 12 входам модуля, вход второго многовходового сумматора по модулю два второго блока вычисления синдрома ошибки подключен к 2, 4, 5, 7, 13 входам модуля, вход третьего многовходового сумматора по модулю два второго блока вычисления синдрома ошибки подключен к 3, 5, 6, 14 входам модуля, вход четвертого многовходового сумматора по модулю два второго блока вычисления синдрома ошибки подключен к 6, 7, 15 входам, при этом выходы многовходовых сумматоров являются соответствующими выходами модуля вычисления синдрома.