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

 

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

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

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

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

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

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

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

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

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

Зная _i, можно исправить неправильное число A = (-_ii)modP_n.

Границы интервалов распределения ошибок можно определить из выражения (2), если в качестве А использовать числа О и Р_р -1, а _i изменять от 1 до _i - 1.

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

Определяют границы интервалов распределения ошибок в избыточном диапазоне: основание ₁= 2, ₁= 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 устройства.

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

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

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

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

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

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

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

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

В случае, если число А¹ ошибочно (А¹ >Р_р) по какому-либо рабочему основанию, то оно попадает в соответствующий величине ошибки интервал схемы сравнения с константой блока 2, на выходе которой устанавливается величина ошибки _i. Пройдя группу элементов ИЛИ блока 3, она подается на соответствующий умножитель блока 4, где происходит умножение по модулю с величиной ортогонального базиса _i. Далее, пройдя через блок 5 элементов ИЛИ, величина _{i i}. подается на вход вычитаемого вычитателя 6, на входе уменьшаемого которого присутствует значение А¹. С выхода вычитателя 6 исправленное число А¹ поступает на первые информационные выходы 9 устройства и на вход выходного преобразователя 7 кода, после преобразования в модулярный код число А¹ поступает на вторые информационные выходы 10 устройства. Преимущества предлагаемого устройства по сравнению с базовым объектом. В базовом объекте быстродействие определяется числом членов разложения в цепную дробь [a_o, a₁,...]. соответствующим числу тактов, и максимально может быть равна S_m= log₂ .Даже если имеют одно контрольное основание _{n + 1} > _{n n - 1} , то число тактов не меньше четырех. С увеличением величин как рабочих, так и контрольных оснований число тактов возрастает.

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

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

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

РИСУНКИ

Рисунок 1