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

 

Изобретение относится к вычислительной технике и может быть использовано в системах связи и обработки информации, оперирующих с модулярными кодами. Цель изобретения - увеличение быстродействия. Цель достигается изменением алгоритма работы, распараллеливанием операций сравнения числа с интервалами распределения ошибок, введением блока 2 групп элементов сравнения с константой, блока 4 умножителей на константу, блока 3 групп элементов ИЛИ, блока 5 элементов ИЛИ, блоков 11, 14 элементов И, блока 12 сравнения, триггера 13 в устройство, содержащее входной 1 и выходной 7 преобразователи кода и вычитатель 6. 1 ил.

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

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

Однако данное устройство обладает низким быстродействием.

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

Однако данное устройство имеет низкое быстродействие.

Целью изобретения является повышение быстродействия.

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

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

В модулярном коде число представляется совокупностью неотрицательных вычетов α₁ , α₂ , α₃ , ... , α_n , α_{n + 1} по группе взаимно простых оснований ρ₁ , ρ₂ , ρ₃ , . ... ,ρ_n , ρ_{n + 1}.При этом рабочий диапазон чисел P_р= , а полный диапазон P_п=. Величину Р_и = P_п - P_p назовем избыточным диапазоном. Появление ошибки по одному какому-либо основанию переводит число из рабочего диапазона в избыточный при условии ρ₁ < ρ₂ < ... < ρ_n < ρ_{n + 1} . (1) Распределение ошибок в избыточном диапазоне осуществляется вполне определенно и зависит от величины ρ_{n + 1} . При этом если ρ_{n + 1} > ρ_n ˙ ρ_{n + 1} , то существует возможность по величине неправильного числа А, равного = (A+Δα_iβ_i) mod P_п (2) однозначно определить ошибочное основание и значение ошибки.

Зная Δ α_i, можно исправить неправильное число A=(-Δα_iβ_i) mod P_п Границы интервалов распределения ошибок можно определить из выражения (2), если в качестве А использовать числа 0 и Р_р - 1, а Δ α изменять от 1 до ρ_{i - 1}.

П р и м е р. Пусть ρ₁ = 2 , ρ₂ = 3 , ρ₃ = 5 - рабочие основания. P_n+1 выбирают из условия ρ_{n + 1} > ρ_n ˙ ρ_{n +1} , т.е. ϕ_{n +1} = 17, когда Р_р= =30, Р_п = 510.

Определяют границы интервалов распределения ошибок в избыточном диапазоне: основание ρ₁= 1,Δα₁=1 __→ =[255-284] основание ρ₂ = 3,Δα₂=1 __→ =[340-369] Δα₂=2 __→ =[170-199] основания ρ₃ = 5,Δα₃=1 __→ =[306-335] Δα₃=2 __→ =[102-131] Δα₃=3 __→ =[408-437] Δα₃=4 __→ =[204-233].

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

Пусть в результате вычислений на выходе преобразователя СОК в ПСС получено неправильное число = 128 = (0, 2, 3, 9). По принадлежности интервалу Δ определяют ошибочное основание и величину ошибки Δ α₃ = 2. Производят исправление числа = 128:
A = (128 - 2,306) mod 510 = 26 = (0, 2, 1, 9).

На чертеже представлена функциональная схема предлагаемого устройства.

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

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

Блок 2 групп схем сравнения с константой состоит из K=(ρ_i-1) комбинационных схем (для примера, приведенного в описании, К = 7), осуществляющих сравнение чисел с выхода преобразователя 1 кода с интервалами распределения ошибок. Каждой схеме сравнения соответствует только один интервал, вполне определенный Δ α_i . Причем при попадании в интервал какой-либо схемы сравнения на ее выходе формируется соответствующее значение Δ α_i , в противном случае на выходе ноль.

Блок 3 групп элементов ИЛИ состоит из n групп log ₂ ] ρ_i - 1 [( ρ_i- 1)-входовых элементов ИЛИ при представлении значений Δ α_i в двоичном коде или ( ρ_i - 1)( ρ_i-1)-входовых элементов ИЛИ при представлении в унитарном коде.

Блок 4 умножителей на константу состоит из n умножителей по модулю Р_n, осуществляющих умножение значения Δ α_i на соответствующий ортогональный базис β_i , которые могут быть выполнены в табличном (что наиболее предпочтительно) либо в суммарном варианте.

Блок 5 элементов ИЛИ состоит из log 2 ] P_п [n-входовых элементов ИЛИ при представлении значений в двоичном коде либо из P_п n-входовых элементов ИЛИ при представлении в унитарном коде.

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

Блок 12 сравнения с рабочим диапазоном представляет собой комбинационное устройство, на выходе которого значение равно логической "1" только тогда, когда на входе число попадает в интервал [0, P_p], в противном случае на выходе ноль.

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

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

Устройство работает следующим образом.

На вход 15 установки устройства подается импульс, который устанавливает триггер 13 в единичное состояние, которое разрешает прохождение информации через первый блок 14 элементов И. На информационные входы 8, 16 входного преобразователя 1 подано число в модулярном коде α₁¹, α₂¹,..., α_n¹, α ¹_n+1 через время, определяемое переходными процессами в преобразователе 1. На его выходе устанавливается значение числа А в позиционном коде, которое поступает на блок 2 групп элементов сравнения с константой. Здесь возможны варианты: либо число правильно, т.е. А¹ < <Р, либо неправильно, т.е. А¹> Р_р. Если число правильно и не попадает ни в один интервал распределения ошибок, то на выходах элементов сравнения устанавливается значение "0", которое проходят через блок 3 групп элементов ИЛИ на входы блока 4 умножителей, на выходах которых значения также равны "0". Эти значения поступают через группу 5 элементов ИЛИ на вход вычитаемого вычитателя 6, на входе уменьшаемого которого присутствует число А¹. Число А¹ поступает на блок 12 сравнения с рабочим диапазоном и на первые входы второго блока 11 элементов И. Так как число А¹ правильное и лежит внутри рабочего интервала, то на выходе блока 12 сравнения с рабочим диапазоном устанавливается единичный уровень, который разрешает прохождение числа А¹ на информационные выходы 9 устройства и вход выходного преобразователя 7 кода, на выходах которого устанавливается правильное число А ¹в коде СОК.

Если число А¹ ошибочно (А¹ > Р_р), могут быть два варианта: число А¹ ошибочно по какому-либо рабочему основанию; ошибка произошла в избыточном основании. Рассмотрим первый вариант. С выхода входного преобразователя 1 кода число поступает на входы блока 2 групп схем сравнения с константой. Так как ошибка произошла по одному из рабочих оснований, то число А¹ попадает в интервал соответствующего элемента сравнения, на выходе которого устанавливается значение величины ошибки Δ α_i . Оно через блок 3 групп элементов ИЛИ поступает на умножитель 4.i на константу, с выхода которого значение Δ α_i β_i поступает на вход вычитаемого вычитателя 6, на входе уменьшаемого которого присутствует неправильное число А¹ . С выхода вычитателя 6 откорректированное число поступает на блок 12 сравнения с рабочим диапазоном и на первые входы второго блока 11 элементов И. На выходе блока 12 сравнения устанавливается уровень логической "1", так как число А попадает в рабочий диапазон, который разрешает прохождение числа через второй блок 11 элементов И на первые информационные выходы 9 устройства и входы выходного преобразователя 7 кода.

Если ошибка произошла по избыточному основанию ρ_{n + 1} , то число А1, даже если попадает в интервал какой-либо схемы сравнения с константой, все равно на выходе вычитателя 6 неправильное. Оно больше рабочего диапазона Р_р, следовательно, на выходе блока 12 сравнения с рабочим диапазоном устанавливается уровень "0", который запрещает прохождение информации через второй блок 11 элементов И. Переход с высокого уровня на низкий на счетном входе триггера 13 устанавливает триггер в нулевое состояние и запрещает прохождение неправильной информации по информационному входу 16 избыточного модуля. Так как ошибочным допускается только одно основание, то считается, что ошибок по рабочим основаниям нет, следовательно, на выходе входного преобразователя 1 кода формируется правильное число А, которое проходит на информационные выходы 9 и 10 устройства без корректировки.

Преимущества предлагаемого устройства по сравнению с базовым объектом. В базовом объекте быстродействие определяется числом членов разложения в цепную дробь [a_o, a₁...], соответствующим числу тактов, и максимально может быть равно σ_m=log2 . Даже в случае, если имеют одно контрольное основание ρ_{n + 1} > ρ_n ˙ ρ_{n - 1} , число тактов не меньше четырех. С увеличением величин как рабочих, так и контрольных оснований число тактов возрастает.

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

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

УСТРОЙСТВО ДЛЯ КОНТРОЛЯ И ИСПРАВЛЕНИЯ ОШИБОК В ИЗБЫТОЧНОМ МОДУЛЯТОРНОМ КОДЕ, содержащее входной преобразователь кода, первые входы которого являются первыми информационными входами устройства, а выход соединен с первыми входами вычитателя, выходной преобразователь кода, выходы которого являются первыми информационными выходами устройства, отличающееся тем, что, с целью повышения быстродействия устройства, в него введены блок групп элементов сравнения, блок групп элементов ИЛИ, блок умножителей, блок сравнения, триггер, блок элементов ИЛИ и блоки элементов И, первые входы первого блока элементов И являются вторыми информационными входами устройства, выходы соединены с вторыми входами входного преобразователя кода, входы элементов сравнения всех групп блока объединены и подключены к выходу входного преобразователя кода, выходы элементов сравнения каждой группы блока соединены с соответствующими входами соответствующих групп элементов ИЛИ блока, выходы которых соединены с входами соответствующих умножителей блока, выходы которых соединены с соответствующими входами блока элементов ИЛИ, выходы которого соединены с вторыми входами вычислителя, выходы вычитателя соединены с первыми входами второго блока элементов И и блока сравнения, выход которого соединен с вторым входом второго блока элементов И и счетным входом триггера, установочный вход которого является входом установки устройства, выход триггера соединен с вторым входом первого блока элементов И, выходы второго блока элементов И соединены с входом выходного преобразователя кода и являются вторыми информационными выходами устройства.

РИСУНКИ

Рисунок 1