Устройство для коррекции ошибок в полиномиальной системе классов вычетов

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

 

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

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

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

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

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

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

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

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

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

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

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

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

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

αn+2(z).

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

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

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

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

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

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

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

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

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

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

Если синдром ошибки δ1(z)=0 и δ2(z)=0, то данная комбинация не содержит ошибки. В противном случае (δ1(z)≠0 и δ2(z)≠0) принятая комбинация ПСКВ является запрещенной, т.е. ошибочной. По величине δ1(z)≠0 и δ2(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)=(α1(z), α2(z),…, αn(z), αn+1(z), αn+2(z)) записывается в регистр 1. На вход первого блока вычисления синдрома ошибки 4, входящего в модуль вычисления синдрома ошибки 3, с первого выхода регистра 1 поступает значение (α1(z), α2(z), …, αn(z)), а на второй вход - со второго выхода регистра 1 - значение αn+1(z). Данный блок вычисления синдрома ошибки реализует выражение (9).

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

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

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

p1(z)=z+1; p2(z)=z2+z+1; p3(z)=z4+z3+z2+z+1.

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

.

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

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

Имеем

,

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

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

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

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

A(z)=(1, z+1, z3+1, z+1, z2).

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

.

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

δ1(z)=z+1+z3+z+1=z3.

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

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

δ2(z)=z2+z3+z2+z+1=z3+z+1.

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

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

A(z)=A(z)+Δконст=(1, z+1, z3+1, z+1, z2)+(0, 0, z3, 0, 0)=(1, z+1, 1, z+1, z2).

Структура модуля вычисления синдрома ошибки 3 представлена на фигуре 2. Модуль содержит входы 8-14, подключенные к выходам регистра 1, первый и второй блоки вычисления синдрома ошибки. Данный модуль предназначен для работы с рабочими основаниями p1(z)=z+1, p2(z)=z2+z+1, p3(z)=z4+z3+z2+z+1 и контрольным p4(z)=z4+z+1. На входы 8, 9-10, 11-14 поступают значения остатков α1(z), α2(z), α3(z) по рабочим основаниям, снимаемые с первого выхода регистра 1. На входы 15-18 подается значение остатка α4(z) со второго выхода регистра 1. На входы 19-22 подается значение остатка α5(z) с третьего выхода регистра. Все остатки подаются в двоичном параллельном коде. Три младших разряда остатков α1(z), α2(z), α3(z), α4(z) и α5(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. С выходов этих сумматоров по модулю два снимается параллельный двоичный код первого синдрома ошибки δ1(z). Младший разряд δ1(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. Значение второго синдрома ошибки δ2(z) снимается в параллельном двоичном коде с выходов 35-38, при этом младший разряд - с выхода 35, а старший - с выхода 38 соответственно.

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

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

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

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

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

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

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

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

Таблица 1
δ1(z) δ2(z) Константа ошибки Δконст
0 0 (0, 0, 0, 0, 0)
1 1 (1, 0, 0, 0, 0)
1 z (0, 1, 0, 0, 0)
z z2 (0, z, 0, 0, 0)
1 z+1 (0, 0, 1, 0, 0)
z z2+z (0, 0, z, 0, 0)
z2 z3+z2 (0, 0, z2, 0, 0)
z3 z3+z+1 (0, 0, z3, 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

Устройство для коррекции ошибок в полиномиальной системе классов вычетов, содержащее регистр, вход которого является входом устройства, блок памяти и выходной сумматор, первый, второй и третий входы которого соединены соответственно с первым, вторым и третьим выходами регистра, а четвертый вход соединен с выходом блока памяти, отличающееся тем, что в него введен модуль вычисления синдрома ошибки, входы которого подключены в первому, второму и третьему выходам регистра, выходы модуля вычисления синдрома ошибки подсоединены к входам блока памяти, при этом модуль вычисления синдрома ошибки содержит 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 входам, при этом выходы многовходовых сумматоров являются соответствующими выходами модуля вычисления синдрома.



 

Похожие патенты:

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

Изобретение относится к области видеокодирования с предсказанием и, в частности, к обеспечению соответствия между состояниями кодера и декодера. .

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

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

Изобретение относится к вычислительной технике и, в частности, к модулярным нейрокомпьютерным средствам и предназначено для определения ошибок в кодовых конструкциях непозиционного кода полиномиальной системы классов вычетов (ПСКВ), представленных в расширенных полях Галуа GF(2v).

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

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

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

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

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

Изобретение относится к вычислительной технике. Технический результат заключается в восстановлении большого числа одновременно отказавших частей запоминающего устройства. Способ восстановления записей в запоминающем устройстве при отказе или повреждении части запоминающего устройства или при искажении данных на запоминающем устройстве, в котором разделяют область памяти запоминающего устройства на информационные зоны одинакового размера и контрольные зоны, выбранные из разных частей запоминающего устройства. Записывают каждую группу подлежащих запоминанию данных в виде набора кодовых слов в соответствующую информационную зону. Находят при каждой записи данных с помощью соответствующего вычислительного блока три эталонных контрольных суммы каждую по заранее установленной формуле. Далее записывают каждую из найденных эталонных контрольных сумм в виде кодового слова с тем же номером в соответствующую контрольную зону, при этом каждая из трех контрольных сумм хранится в отдельной зоне запоминающего устройства. При отказе или повреждении части запоминающего устройства вычисляют с помощью вычислительного блока текущие контрольные суммы по формулам для каждого набора кодовых слов с одинаковыми номерами во всех информационных зонах. Используют значения хранящихся эталонных контрольных сумм и значения текущих контрольных сумм для восстановления утраченных данных путем решения систем уравнений. 2 н. и 8 з.п. ф-лы, 2 ил.

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

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

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

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