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

 

Устройство для контроля и исправления ошибок в избыточном модулярном коде относится к вычислительной технике и может быть использовано в системах связи и обработки информации, оперирующих с модулярными кодами. Цель изобретения - повышение быстродействия устройства. Цель достигается изменением алгоритма работы, распараллеливанием операций сравнения числа с интервалами распределения ошибок, введением блока 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+Δα_i·β_i)modP_n, (2) Однозначно определить ошибочное основание и значение ошибки.

Зная Δ α_i, можно исправить неправильное число A = (-Δα_i·β_i)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