устройство для контроля и исправления ошибок в избыточном модулярном коде
Классы МПК: | H03M13/00 Кодирование, декодирование или преобразование кода для обнаружения ошибок или их исправления; основные предположения теории кодирования; границы кодирования; способы оценки вероятности ошибки; модели каналов связи; моделирование или проверка кодов |
Автор(ы): | Бережной Виктор Васильевич, Оленев Александр Анатольевич, Микула Николай Павлович, Николаев Юрий Иванович |
Патентообладатель(и): | Бережной Виктор Васильевич, Оленев Александр Анатольевич, Микула Николай Павлович, Николаев Юрий Иванович |
Приоритеты: |
подача заявки:
1991-07-08 публикация патента:
30.06.1994 |
Устройство для контроля и исправления ошибок в избыточном модулярном коде относится к вычислительной технике и может быть использовано в системах связи и обработки информации, оперирующих с модулярными кодами. Цель изобретения - повышение быстродействия устройства. Цель достигается изменением алгоритма работы, распараллеливанием операций сравнения числа с интервалами распределения ошибок, введением блока 2 группы элементов сравнения с константой, блока 4 умножителей на константу, блока 3 группы элементов ИЛИ в устройство, содержащее входной преобразователь 1 кода, выходной преобразователь 7 кода и вычитатель 6. 1 ил.
Рисунок 1
Формула изобретения
УСТРОЙСТВО ДЛЯ КОНТРОЛЯ И ИСПРАВЛЕНИЯ ОШИБОК В ИЗБЫТОЧНОМ МОДУЛЯРНОМ КОДЕ, содержащее входной преобразователь кода, входы которого являются информационными входами устройства, выход соединен с первым входом вычитателя, выход которого соединен с входом выходного преобразователя кода и является первым информационным выходом устройства, выходы выходного преобразователя являются вторыми информационными выходами устройства, отличающееся тем, что, с целью повышения быстродействия устройства, в него введены блок групп элементов сравнения, блок групп элементов ИЛИ, блок умножителей и блок элементов ИЛИ, выход которого соединен с вторым входом вычитателя, входы элементов сравнения всех групп блока объединены и подключены к выходу входного преобразователя кода, выходы элементов сравнения каждой группы блока соединены с соответствующими входами соответствующей группы элементов ИЛИ блока, выходы групп элементов ИЛИ блока соединены с входами соответствующих умножителей блока, выходы которых соединены с соответствующими входами блока элементов ИЛИ.Описание изобретения к патенту
Изобретение относится к вычислительной технике и может быть использовано в системах связи и обработки информации, оперирующих с модулярными кодами (кодами в системе остаточных классов - СОК). Известно устройство для обнаружения и исправления ошибок арифметических операций, содержащее первый и второй регистры контрольных разрядов, выходы которых соединены с первыми входами соответственно первого и второго сумматоров, вторые входы которых соединены с входами блоков памяти, третий, четвертый и пятый сумматоры, третий и четвертый регистры контрольных разрядов, выходы которых соединены с первыми входами соответственно первого и второго регистров контрольных разрядов, выходы которых соединены с первыми входами соответственно четвертого и пятого сумматоров, вторые входы которых соединены с выходами соответственно четвертого и пятого сумматоров, причем выходы третьего сумматора соединены с входами первого и второго блоков модульной свертки, выходы которых соединены с входами соответственно третьего и четвертого регистров контрольных разрядов [1]. Однако данное устройство обладает низким быстродействием. Наиболее близким по сущности технического решения к изобретению является устройство для контроля ошибок в избыточном модулярном коде, содержащее входной преобразователь кода, входы которого являются соответствующими информационными входами устройства, блок вычисления поправок, первые входы которого подключены к первым информационным входам блока анализа, контрольные выходы которого являются контрольными выходами устройства, блок преобразования числа в цепную дробь, вычитатель и выходной преобразователь кода, причем выходы входного преобразователя кода подключены к соответствующим первым входам вычитателя и информационным входам блока преобразования числа в цепную дробь, выходы которого соединены с информационными входами блока вычисления поправок, выходы которого соединены с вторыми входами вычитателя, выходы которого подключены к соответствующим вторым информационным входам блока анализа, входам выходного преобразователя кода и являются первыми информационными выходами устройства, управляющие выходы блока анализа соединены с соответствующими управляющими входами блока вычисления поправок и блока преобразования числа в цепную дробь, установочные входы которых соответственно объединены и являются первыми установочными входами устройства, первые и вторые установочные входы блока анализа являются соответственно вторыми и третьими установочными входами устройства, выходы выходного преобразователя кода являются вторыми информационными выходами устройства [2]. Однако данное устройство имеет низкое быстродействие. Целью изобретения является повышение быстродействия. Предлагаемое устройство использует в своей работе следующее. Известно, что наличие избыточного основания в информации, представленной в СОК, позволяет обнаруживать ошибки. Причем при определенной величине избыточного (контрольного) основания появляется возможность не только обнаружить, но также локализовать и исправить ошибку. В модулярном коде число представляется совокупностью неотрицательных вычетов 1, 2 , 3,...., n, n+1 по группе взаимно простых оснований, 1 , 2 , 3 , ... , n , n + 1 . При этом рабочий диапазон чисел равен Pp= i, а полный диапазон Pn= i, величину n = Pn - Pp назовем избыточным диапазоном. Появление ошибки по одному какому-либо основанию переводит число из рабочего диапазона в избыточный при условии1 < 2 < ... < n < n + 1 (1)
Распределение ошибок в избыточном диапазоне осуществляется вполне определенно и зависит от величины n+1. При этом, если n + 1 > n n + 1 , то существует возможность по величине неправильного числа А, равного
= (A+ii)modPn, (2) Однозначно определить ошибочное основание и значение ошибки. Зная i, можно исправить неправильное число
A = (-ii)modPn. Границы интервалов распределения ошибок можно определить из выражения (2), если в качестве А использовать числа О и Рр -1,
а i изменять от 1 до i - 1. П р и м е р. Пусть 1 = 2, 2 = 3, 3 = 5 - рабочие основания. n+1 выбирают из условия n+1 > n n-1, т.е. n+1=17, тогда Рр = 30, Рn = 510. Определяют границы интервалов распределения ошибок в избыточном диапазоне:
основание 1= 2, 1= 1 _ = [255-284];
основание 2= 3, 2= 1 _ = [340-369];
2= 2 _ = [170-199];
основание 3= 5, 3= 1 _ = [306-335];
3= 2 _ = [102-131];
3= 3 _ = [408-437];
3= 4 _ = [204-233]. Ошибки по контрольному основанию охватывают весь избыточный диапазон. Пусть в результате вычислений на выходе преобразователя СОК в ПСС получено неправильное число = 128 = (0, 2, 3, 9). По принадлежности интервалу определяют ошибочное основание и величину ошибки 3= 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 групп log2] i-1[( i-1)-входовых элементов ИЛИ при представлении значений i-1 iв двоичном коде и i-1 ( i-1)-входовых элементов ИЛИ при представлении в унитарном коде. Блок 4 умножителей на константу состоит из n умножителей по модулю Рn, осуществляющих умножение значения i на соответствующий ортогональный базис i, и может быть выполнен в табличном (что наиболее предпочтительно) либо в суммарном варианте. Блок 5 элементов ИЛИ состоит из log2]Pn[n-входовых элементов ИЛИ при представлении значений в двоичном коде либо из Рn n-входовых элементов ИЛИ при представлении в унитарном коде. Вычитатель 6 осуществляет операцию вычитания, и может быть как табличного, так и суммарного типа. Выходной преобразователь 7 кода служит для преобразования позиционного кода в исправленный модулярный код. Этот преобразователь, как и входной преобразователь 1, может быть выполнен в комбинационном или регистровом виде. Предлагаемое устройство работает следующим образом. На информационные входы 8 входного преобразователя 1 подано число в модулярном виде 1 , 2 , ... , n , n + 1 через время, определяемое переходными процессами в преобразователе 1. На его выходе устанавливается значение числа А1 в позиционном коде, которое поступает на блок 2 группы схем сравнения с константой. Здесь возможны варианты: либо число правильно, т. е. А1 < Рр, либо неправильно, т.е. А1 > Рр. Если число правильно и не попадает ни в один интервал распределения ошибок, то на выходах схем сравнения устанавливается значение "0", которое проходят через блок 3группы элементов ИЛИ на входы блока 4 умножителей, на выходах которых значения также равны "0". Эти значения поступают через блок 5 элементов ИЛИ на вход вычитаемого вычитателя 6, на входе уменьшаемого которого присутствует число А1.Число А1 поступает на первые информационные выходы 9 устройства и вход выходного преобразователя 7 кода без изменений. На вторых информационных выходах 10 устройства появляется число А1 в модулярном коде без изменений. В случае, если число А1 ошибочно (А1 >Рр) по какому-либо рабочему основанию, то оно попадает в соответствующий величине ошибки интервал схемы сравнения с константой блока 2, на выходе которой устанавливается величина ошибки i. Пройдя группу элементов ИЛИ блока 3, она подается на соответствующий умножитель блока 4, где происходит умножение по модулю с величиной ортогонального базиса i. Далее, пройдя через блок 5 элементов ИЛИ, величина i i. подается на вход вычитаемого вычитателя 6, на входе уменьшаемого которого присутствует значение А1. С выхода вычитателя 6 исправленное число А1 поступает на первые информационные выходы 9 устройства и на вход выходного преобразователя 7 кода, после преобразования в модулярный код число А1 поступает на вторые информационные выходы 10 устройства. Преимущества предлагаемого устройства по сравнению с базовым объектом. В базовом объекте быстродействие определяется числом членов разложения в цепную дробь [ao, a1,...]. соответствующим числу тактов, и максимально может быть равна Sm= log2 .Даже если имеют одно контрольное основание n + 1 > n n - 1 , то число тактов не меньше четырех. С увеличением величин как рабочих, так и контрольных оснований число тактов возрастает. В предлагаемом устройстве за счет распараллеливания операций сравнения неправильного числа с интервалами распределения ошибок достигается максимальное быстродействие.
Класс H03M13/00 Кодирование, декодирование или преобразование кода для обнаружения ошибок или их исправления; основные предположения теории кодирования; границы кодирования; способы оценки вероятности ошибки; модели каналов связи; моделирование или проверка кодов