Устройство для исправления ошибок p-кодов фибоначчи

 

Изобретение относится к вычислительной технике и может быть использовано для исправления ошибок. Техническим результатом является повышение быстродействия. Оно достигается за счет того, что устройство содержит первый и второй элементы И, p 2 групп из элементов И, n 3p групп из элементов И, p 2 групп из элементов И и группу из n p 2 элементов ИСКЛЮЧАЮЩЕЕ ИЛИ и соответствующих связей. Устройство может быть использовано для построения высоконадежных электронных устройств хранения и обработки информации в системах с высокими требованиями по достоверности, а также может быть использовано в системах с высоким уровнем помех. 1 ил.

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

Известно устройство для контроля фибоначчиевого p-кода, содержащее n-разрядный регистр, элемент ИЛИ и n-p блоков фиксации сбоев [1] Недостаток этого устройства заключается в его низкой помехоустойчивости.

Наиболее близким по технической сущности к предлагаемому является устройство для исправления однократных ошибок p-кодов Фибоначчи [2] содержащее элементы ИЛИ первой и второй группы, n-разрядных регистр (n-разрядность кода), единичные входы разрядов которого являются информационными входами устройства, а выходы информационными выходами устройства, вторую группу из n-p-2 элементов И и третью группу из n-p-3 элементов ИЛИ, выходы младших p разрядов соединены с соответствующими входами элемента ИЛИ, выход которого является выходом ошибки устройства, выход i-го разряда n-разрядного регистра (i=p+2,n) соединен с первым входом (i-p+1)-го элемента И первой группы и j-м входом (i-p-2+j)-го элемента ИЛИ второй группы (j=1,p), выход k-го (k=1, n-p-3) элемента ИЛИ второй группы соединен с вторым входом (k+1)-го элемента И первой группы, выход (p+1)-го разряда n-разрядного регистра соединен с вторым входом первого элемента И первой группы, выходы элементов И первой группы соединены с соответствующими входами элемента ИЛИ, входы сброса (p+1)-го и n-го разрядов n-разрядного регистра подключены к входу сброса устройства, выход i-го элемента (i=1,n-p-3) И первой группы соединен с первым входом соответствующего элемента И второй группы и j-м (j=1,p) входом (i-j)-го элемента ИЛИ третьей группы, выход которого соединен с вторым входом соответствующего элемента И второй группы, выход последнего элемента И первой группы подключен к второму входу последнего элемента И второй группы, выход k-го элемента И второй группы (k=1,n-p-2) подключен к первому входу (k+p)-го элемента ИЛИ первой группы, выход которого подключен к входу сброса (k+p+1)-го разряда n-разрядного регистра, выходы первых p разрядов n-разрядного регистра соединены с первыми входами соответствующих элементов ИЛИ первой группы, выходы которых соединены с входами сброса соответствующих разрядов n-разрядного регистра, вторые входы элементов ИЛИ первой группы подключены к входу сброса устройства. Недостаток известного устройства низкое быстродействие.

Технической задачей данного изобретения является повышение быстродействия.

Поставленная цель достигается тем, что устройство, содержащее группу элементов ИЛИ, дополнительно содержит первый и второй трехвходовые элементы И, p-2 групп из (k+2) трехвходовых элементов И (k=1,p-2), n-3p групп из (p+1) трехвходовых элементов И, p-2 групп из (n-p-m-1) трехвходовых элементов И (m= n-2p-1,n-p-4) и группу из n-p-2 элементов ИСКЛЮЧАЮЩЕЕ ИЛИ, причем первый вход каждого [(k- ) b+c]-го (b=o. k; c=b+1,k+1) трехвходового элемента И k-й группы соединен с (p+b+1)-м входом устройства, второй вход этого элемента соединен с (2p+c+1)-м входом устройства, а третий вход с (p+k+2)-м входом устройства, первый вход каждого [(p-)i+j]-го (i=0,p-1; j= i+1, p) трехвходового элемента И l-й группы (l=p-1,n-2p-2) соединен с (l+i+2)-м входом устройства, второй вход этого элемента соединен с (l+p+j+2)-м входом устройства, а третий вход с (p+l+2)-м входом устройства, первый вход каждого [(n-p-m-3-)d+e] -го (d=0, n-p-m-3; e=d+1,n-p-m-2) трехвходового элемента И m-й группы соединен с (m+d+2)-м входом устройства, второй вход этого элемента соединен с (n-p+e+1)-м входом устройства, а третий вход с (p+m+2)-м входом устройства, выходы трехвходовых элементов И каждой r-й группы (r= 1,n-p-4) объединены соответствующим элементом ИЛИ, выход которого соединен с первым входом (r+1)-го элемента ИСКЛЮЧАЮЩЕЕ ИЛИ, второй вход которого соединен с (r+p+2)-м входом устройства, входы первого трехвходового элемента И соединены соответственно с (p+1)-м, (2p+2)-м и (p+2)-м входами устройства, а входы второго трехвходового элемента И соединены соответственно с (n-p-1)-м, n-м и (n-1)-м входами устройства, выходы первого и второго трехвходовых элементов И соединены соответственно с первыми входами первого и (n-p-2)-го элементов ИСКЛЮЧАЮЩЕЕ ИЛИ, вторые входы которых соединены соответственно с (p+2)-м и (n-1)-м входами устройства, выходы элементов ИСКЛЮЧАЮЩЕЕ ИЛИ являются информационными выходами устройства, p+1 младших и n-й входы устройства являются одновременно и его выходами.

Любое натуральное число в n-разрядном фибоначчиевом p-коде представляется в виде многочлена Aa_sϕ_p(s), (1) где a_s∈0,1} ϕ _p(S)-p-число Фибоначчи (p=0,1.) ϕ_p(s)= Метод исправления ошибок в S-м разряде описывается булевой функцией: I _(s)^0-1= a _(s-p+i)a _(s)a _(s+j) (2) где a_(s) двоичный коэффициент S-го разряда; I _(s)^0-1- единичный сигнал исправления ошибки типа переход "0" в "1" i=0;p-1; j=i+1,p Сущность изобретения заключается в реализации формулы (2).

На чертеже изображена схема устройства для p=2 и n=8. Следует отметить, что так как p младших разрядов кода не обрабатываются устройством, то два младших разряда кода из устройства исключены.

Предлагаемое устройство содержит первую группу трехвходовых элементов И 1.1-1.3, вторую группу тревходовых элементов И 2.1-2.3, первый и второй трехвходовые элементы И 3,4, группу элементов ИЛИ 5,1, 5,2, группу элементов ИСКЛЮЧАЮЩЕЕ ИЛИ 6.1-6.4, группу информационных входов 7 и группу информационных выходов 8 устройства. Первая и вторая группы трехвходовых элементов И 1.1-2.3, первый и второй трехвходовые элементы И 3,4 предназначены для формирования сигналов исправления ошибок, а группа элементов ИЛИ 5.1, 5.2 предназначена для объединения этих сигналов. Группа элементов ИСКЛЮЧАЮЩЕЕ ИЛИ 6.1-6.4 предназначена для исправления возникших ошибок на входах 7 и формирования верной кодовой комбинации на выходах 8 устройства. Введенные элементы удовлетворяют критерию "существенные отличия".

Устройство работает следующим образом. Предположим, что на вход устройства подано представление числа 5 в двоичном коде Фибоначчи 00100100. Эта комбинация, поступая на соответствующие входы элементов И 1.1-2.3, 3,4, ни в одном случае не дает на выходе элементов И единичного потенциала, т. е. "0" через элементы ИЛИ 5.1, 5.2 и непосредственно с выходов элементов И 3,4 поступает на первые входы соответствующих элементов ИСКЛЮЧАЮЩЕЕ ИЛИ 6.2, 6.3, 6.1, 6.4, на вторые входы которых поступают потенциалы контролируемого кода, которые в этом случае проходят на выход устройства без изменений. Предположим, что в четвертом разряде произошел сбой типа переход "0" в "1" и кодовая комбинация приняла вид 00110100. В этом случае сработает элемент И 3, так как на все его входы поданы единичные потенциалы соответственно третьего, шестого и четвертого разрядов. Единичный потенциал с выхода элемента И 3 поступает на первый вход элемента ИСКЛЮЧАЮЩЕЕ ИЛИ 6.1, на второй вход которого поступает "1" искаженного четвертого разряда. На выходе элемента ИСКЛЮЧАЮЩЕЕ ИЛИ 6.1 появится нулевой потенциал, который и пройдет на выход устройства, исправив таким образом возникшую ошибку. Аналогично исправляется и сбой в пятом разряде. В этом случае срабатывает элемент И 1.1 и "1" через элемент ИЛИ 5.1 поступает на первый вход элемента ИСКЛЮЧАЮЩЕЕ ИЛИ 6.2, где и исправляет возникшую ошибку пятого разряда. Если же контролируемая кодовая комбинация имела вид 00100010, то сбой пятого разряда вызовет срабатывание элемента И 1.2 и далее аналогично через элемент ИЛИ 5.1 срабатывание элемента ИСКЛЮЧАЮЩЕЕ ИЛИ 6.2. Точно так же будет исправлен сбой пятого разряда в случае кодовой комбинации 00010010, только в этот раз срабатывает элемент И 1.3.

Таким образом, предложенное устройство полностью сохраняет способность известного устройства исправлять часть однократных ошибок типа переход "0" в "1". Повышение быстродействия достигается за счет уменьшения количества промежуточных элементов.

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

Формула изобретения

УСТРОЙСТВО ДЛЯ ИСПРАВЛЕНИЯ ОШИБОК P-КОДОВ ФИБОНАЧЧИ, содержащее группу элементов ИЛИ, отличающееся тем, что оно содержит два элемента И, p 2 групп из элементов И (K 1, p 2), n 3p групп из элементов И, P 2 групп из элементов И (m n 2p 1, n p 4) и группу из n p - 2 элементов ИСКЛЮЧАЮЩЕЕ ИЛИ, причем (p + b + 1)-й вход устройства соединен с первым входом каждого элемента И k-й группы (b 0, k, c b + 1, k + 1), второй и третий входы которого соединены соответственно с (2 p + c + 1)-м и (P + K + 2)-м входами устройства, (l + i + z)-й вход которого (l p 1, n 2p 2) соединен с первым входом каждого элемента И l-й группы (i 0, p 1; j i + 1, p) второй и третий входы которого соединены соответственно с (l + p + j + 2)-м и (p + l + 2)-м входами устройства, (m + d + 2)-й вход которого (d 0, n p m -3) соединен с первым входом каждого элемента И m-й группы (s d + 1, n p m 2), второй и третий входы которого соединены соответственно с (n p + s + 1)-м и (p + m + 2)-м входами устройства, выходы элементов И r-й группы (r 1, n p 4) соединены с входами r-го элемента ИЛИ группы, выход которого соединены с первым входом (r + 1)-го элемента ИСКЛЮЧАЮЩЕЕ ИЛИ группы, второй вход которого соединен с (n + p + 2)-м входом устройства, (p + 1)-й, (2p + 2)-й и (p + 2)-й входы которого соединены с входами первого элемента И, входы второго элемента И соединены с (n p 1)-м, n м и (n 1)-м входами устройства, выходы первого и второго элементов И соединены соответственно с первыми входами первого и (n p 2)-го элементов ИСКЛЮЧАЮЩЕЕ ИЛИ, вторые входы которых соединены соответственно с (p + 2)-м и (n 1)-м входами устройства, выходы элементов ИСКЛЮЧАЮЩЕЕ ИЛИ группы, (p + 1)-е младшие входы и n-й входы устройства являются выходами устройства.

РИСУНКИ

Рисунок 1