Устройство для определения двузначного характера элементов конечного поля @

 

Изобретение относится к технике генерирования сложных сигналов. Цель изобретения - повышение быстродействия устройства. Поставленная дель достигается тем, что устройство содержит прямой генератор 1 поля GF(p) первый дешифратор нуля 2, мультиплексор 3, дешифратор знака 4, обратный генератор 5 поля GF(p ), второй дешифратор нуля 6, генератор 7 тактовых импульсов, элемент И 8, триггер 9, сумматор по модулю два. Увеличение быстродействия обеспечивается тем, что в устройстве одновременно генерируются две последовательности элементов конечного поля, в одной из которых эти элементы выстроены в порядке возрастания степеней примитивного элемента, а в другой - в порядке их убывания. Генерирование начинается с того элемента, характер ко- .торого подлежит определению, а завершается при появлении в одной из указанных последовательностей элемента , представляющего собой степень примитивного элемента, кратную h. Таким образом, максимальное число тактов, достаточное для определения двузначного характера любого элемента , равно E(h/2), где Е(х) - целая часть числа х. Следовательно, выигрыш во времени определения характера, даваемый изобретением, равен (h-1) E(h/2). При любых нечетных h выигрыш всегда равен двум, а при четных h он стремится к двум, всегда оставаясь не меньше полутора. 2 ил. (О (Л

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК

А1 (19) (11) (5D4 G06F 7 52

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ

К А BTOPCHOMV СВИДЕТЕЛЬСТВУ (21) 3991147/24-24 (22) 18. 12. 85 (46) 23.05.87. Бюл. Р 19 (71) Ленинградский электротехнический институт (72) В.П.Ипатов, Б.Ж.Камалетдинов и О.И.Корнилов (53) 681.32 (088.8) (56) Гилл А. Линейные последовательностные машины. M. Наука, 1984, с. 22 1,222, рис. 6 .11 и 6.12.

Ипатов В.П. Троичные последовательности с идеальными периодическими автокорреляционными свойствами.

Радиотехника и электроника, 1979, т. 24, 9 10, с. 2053. (54) УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ ДВУЗНАЧНОГО ХАРАКТЕРА ЭЛЕМЕНТОВ КОНЕЧНОГО ПОЛЯ СР(р ) (57) Изобретение относится к технике генерирования сложных сигналов. Цель изобретения — повышение быстродействия устройства. Поставленная цель достигается тем, что устройство содержит прямой генератор 1 поля СР(р") первый дешифратор нуля 2, мультиплексор 3, дешифратор знака 4, обратный генератор S a GF(p"), второй дешифратор нуля 6, генератор 7 тактовых импульсов, элемент И 8, триггер

9, сумматор по модулю два. Увеличение быстродействия обеспечивается тем, что в устройстве одновременно генерируются две последовательности элементов конечного поля, в одной из которых эти элементы выстроены в порядке возрастания степеней примитивного элемента, а в другой — в порядке их убывания. Генерирование начинается с того элемента, характер которого подлежит определению, а завершается при появлении в одной из укаэанных последовательностей элемента, представляющего собой степень примитивного элемента, кратную h.

Таким образом, максимальное число тактов, достаточное для определения двузначного характера любого элемента, равно E(h/2), где Е(х) — целая часть числа х. Следовательно, выигрыш во времени определения характера, даваемый изобретением, равен (h-1)

Е(Ь/2). При любых нечетных 11 выигрыш всегда равен двум, а при четных h он стремится к двум, всегда оставаясь не меньше полутора. 2 ил.

1312568

u-g а =с, о(, сК

Изобретение относится к технике генерирования сложных сигналов.

Целью изобретения является повышение быстродействия, На фиг.1 приведена схема устройства для определения двузначного характера элементов конечного поля, на фиг.2 — схемы прямого генератора поля GF(p ) и обратного генератора по— ля GF(p ).

Устройство содержит прямой генератор 1 поля GF(p ), первый дешиф— ратор 2 нуля, мультиплексор 3, дешифратор 4 знака, обратный генератор 5 поля СГ(р"), второй дешифратор 6 нуля, генератор 7 тактовых импульсов, элемент И 8, триггер 9 и сумматор 10 по модулю два.

Двузначный характер Ц (а) любого элемента а поля GF(р") определяется следующим образом. Примитивный элемент поля GF(p ) последовательно возводят в возрастающую целую степень до тех пор, пока не будет выполнено условие а = <а . Оно будет выполнено при

M каком-то Б, так как любой ненулевой элемент а поля GF(p") может быть представлен как степень примитивного элемента d . .Если U четно,,то Ч (а) =1, в противном случае Ф (а) = -1 . Функция Ч (а) имеет следующее свойство двузначного характера:

Ч (аЬ) = ч (а) W(b), (1) где а и Ь, а также произведение аЪ являются элементами поля GF(p ).

В самом деле, если а = d,u и Ь =: и

u v при каких-то U и V, то аЬ = d.

Если U u V оба четны, т.е. V(a)

= Ч (Ь) = 1, или оба нечетны, т.е.

М(а) = 11 (Ь),,= -1, то U+V четно, и

Ч (аЬ) = Ч)(1 +"),= 1. Если же только один из U М V нечетен, то U+V нечетно, и LV(ck ) = -1.

Любой элемент а = 1i" поля GF(p") может быть записан как сумма вида

1 а = o(аы + а с +...+ак" (2) при соответствующем подборе элементов а (=1,2,...,п) числового подполя AF(p). Таким образом, элементу а = Ы можно поставить в оцнозначное соответствие (а,,а,...,а„). Отметим, !

11 2Ф . Ф 11 что элементу числового подполя GF(p) соответствует вектор, у которого со

2-1 по и-ю компоненты равны нулю.

Изначально прямой и обратный генераторы поля QF(p") по объединенным установочным входам устанавливаются в состояние а,,а,...,а„, соответствующее элементу а = о. В то же время триггер устанавливается в нулевое состояние. Под воздействием тактовых импульсов прямой генератор поля GF(p ) начинает генерировать элементы поля

fP GF(p) в порядке возрастания степеней примитивного элемента с(,т.е. тогда как обратный генератор поля

GF(p") формирует на своих выходах элементы этого же поля GF(p ") в порядке возрастания степеней примитивного элемента о поля GF(p"), т.е. в порядке убывания степеней элемен-, та са:

Таким образом, прямой и обратный генераторы поля GF(p ) удаляются от элемента а = oC в разные стороны. Еси ли прямой генератор поля СГ(р") устремляется к элементу числового подполя сс, то обратный — к предыдущему элементу числового подполя об ) "

Генерирование продолжается до тех пор, пока одним из генераторов не

TTl. h будут сформирован элемент вида д. где m = 1,2,,..., р-1, h=(p"-1) (р-1) .

35 Как уже отмечалось, с 1-й по (и-1)-ю координаты элемента al. равны нулю, поскольку с). " " является элементом числового подполя GF(p). Эти нули дешифрируются тем дешифратором куля, на входах которого они появились.

Сигнал с выхода этого дешифратора нуля останавливает работу устройства.

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

Через входы коэффициентов представления элементов поля устройства прямой и обратный генераторы 1 и 5 поля GF(p") устанавливаются в состо5О яние 1 à,а,...,а„3, соответствующее и элементу поля: GF(p ), двузначный характер которого надо определить. Одновременно обнуляется триггер 9 по входу установки в нуль. Далее, если и

55 элемент а = са имеет вид d. где

h=(p — 1)/(р-1), ш= 1,2,;...р-1, то с

1-й по (и-1)-ю координаты этого элемента равны нулю (а = а = ...=а =.О),,я Ь,h т.е. с = а,. Это означает, что пря3 . 13125 мой и обратный генераторы поля GF(p"), установлены в состояние à,O,...,0 .

Как первый 2, так.и второй 6 дешифраторы нуля дешифрируют нули на своих входах и формируют на выходах управ5 ляющие сигналы для мультиплексора 3, .который при одновременном присутствии обоих управляющих сигналов должен пропускать на свой. выход любой из р-ичных входных сигналов. Эти же 10 сигналы поступают в качестве запрещающих на первый и третий входы эле-. мента И 8. Если нули поля GF(p<) закодированы низкими потенциалами, то каждый из дешифраторов нуля может . 15 быть выполнен в виде элемента ИЛИ, на выходе которого появится нуль лишь в . том случае, когда на всех его входах присутствуют нули.

Сигналы запрета, .присутствующие 20 на первом и третьем входах элемента

И 8, препятствуют прохождению тактовых импульсов от генератора 7 тактовых импульсов через элемент И на тактовые входы обоих генераторов поля 25

СР(р ) и триггера, который остается в нулевом состоянии. Нулевой .сигнал с выхода триггера 9 подается на вто рой .вход сумматора 10 по модулю два.

При. этом выходной сигнал сумматора 10 30 по модулю два совпадает с выходным сигналом, дешифратора 4 знака. На вход дешифратора 4 знака с выхода мультиплексора 3 поступает код элементас числового подполя. На выходе дешифратора 4 знака сигнал равен нулю, если двузначный характер элемента числового подполя GF(p), поданного на его вход, равен единице, и равен единице, когда двузначный харак- 4д тер входного элемента равен .минус единице.

М

В случае, когда элемент а =. д- не равен ot. ", где h = (р"-1)/(р-1), ш = 1,2,...,р-1, ни один из дешифраторов нуля не формирует на своем выходе сигнала запрета на элемент И 8.

Поэтому под воздействием тактовых импульсов на своем тактовом входе пря- 50 мой генератор 1 поля СР(р") начинает генерировать элементы поля СР(р"). в порядке возрастания степеней примитивного элемента, а обратный генератор 5 поля СР(р") — в порядке убывания степеней этого же примитивного элемента. Это продолжается до тех пор, пока на выходе хотя бы одного из генераторов поля СР(р") не

68 4 появится элемент вида " ". Предположим, что это произошло через Z тактов. Если этот элемент . был перпк-h вым по времени сгенерирован прямым генератором 1 поля СР(р"), то это означает, что наступило равенство +z — которое фиксируется первым дешифратором 2 нуля.

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

3 пропустить на свой выход сигнал с первого р-ичного выхода. прямого генератора 1 поля GF(p ). .Дешифратор 4 знака определяет двузначный характер элемента с,. т.е. находит Р (с ).

Поскольку работа устройства была ос- тановлена при наступлении равенства а = d. то V(+ ) .= М(А ), что с учетом (1) дает Ц (сА ) М (О()=Ч (с ). т.е. искомый двузначный характер .элемента а = совпадает с характером V (ct 7, опреДеляемым дешифратором 4 знака, если Z четно, и противоположен Ч (), если Z нечетно.

Учет влияния четности или нечетности и на двузначный характер элементами осуществляется триггером 9 и сумматором 10 .по модулю два. В самом деле, если 2 нечетно, то триггер 9 после остановки окажется в единичном состоянии, и на второй вход сумматора tp по модулю два подается единица.

Тогда сигналы на первом входе и на выхоце сумматора 10 по модулю два противоположны, что.соответствует противоположным значениям двузначного

1т ., характера N(ot ) и искомого двузначного характера. Если 2 четко, то с выхода триггера .9 на второй вход сумматора 10 по модулю два подается нуль и выходной сигнал сумматора, т.е. выход устройства, совпадает с выход-. ным сигналом дешифратора 4 знака, что и требуется при четном Z

Ф. Если первый по времени элемент вида о был сформирован обратным геутi. h нератором 5 поля GF(p ) то, следовательно, на 2-м такте наступило ран-Z венство с = о, которое фиксируется в этом случае вторым дешифратором

6 нуля. Сигнал с выхода этого дешифратора запрещает прохождение тактовых импульсов через элемент И 8, останавливая работу устройства, и переклю5 13125 чает мультиплексор 3 таким образом, что на его выход поступают сигналы с первого р-ичного выхода обратного генератора 5 поля СР(р").

Дешифратор 4 знака определяет двузначный характер 4(J ),выда— вая как и прежде, на первый вход сумматора 10 по модулю два единицу, если Ч (g )= -1, и нуль, если Ч)(К )=

1. Поскольку в этом случае останов- 1О ка предложенного устройства наступила при равенстве d. = А то Ф )=

= Ц (о "), т.е. согласно (1) Ц)(Ы )х

" Ч (d. ) = Ч (о1 "). Поскольку значения двузначного характера элементов по- 15 ля СР(р"), расставленных в порядке убывания степеней примитивного элемента, определяются четностью или нечетностью номера элемента в этой последовательности, то Ч)() совпада- 2р ет с 4 (о(), если Е четно, и Ч (сС ) противоположно < (d ), если Z нечетно, т4

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

Устройство для определения двузначного характера элементов конечного поля GF(p ), содержащее прямой генератор поля GF(p"), первый дешифратор нуля, дешифратор знака, генератор 30 тактовых импульсов, элемент И, триггер, сумматор по модулю два, с первого по и-й входы коэффициентов представления элементов поля устройства подключены к информационным входам 35 прямого генератора поля GF(p"), выходы с первого по (n-1)-й прямого генератора поля СГ(р") подключены к входам первого дешифратора нуля, выход которого подключен к первому вхо68 6 ду элемента И, второй вход элемента

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

"0" триггера, о т л и ч а ю щ е е с я тем, что, с целью повьппения быстродействия, в него введены второй дешифратор нуля, мультиплексор и обратный генератор поля GF(p"), с первого по и-й входы коэффициентов представления элементов поля устройства подключены к информационным входам обратного генератора поля GF(p"), выходы с первого по (n-1)-й обратного генератора поля GF(p") подключены к входам второго дешифратора нуля, и-й выход прямого генератора поля G1(p") и и-й выход обратного поля СГ(р") подключены соответственно к первому и второму информационным входам мультиплексора, выход которого подключен к информационному входу дешифратора знака, выхбд первого дешифратора нуля подключен к первому управляющему входу мультиплексора, выход второго дешифратора нуля подключен к второму управляющему входу мультиплексора и к третьему входу элемента И, выход которого подключен к тактовым входам прямого и обратного генераторов поля СР (р") .

13 1 25б8

Прямои генерапюр поля РР (р" 7

Обратный генерцлир ЛОля / (Р— умнажитель на сс по модулю р — p — ичный элемент задержки на ддин п7акт — сумматор пп юофлю Р фиг.2

Составитель В. Смирнов

Техред Л.Олийнык Корректор С.Черни

Редактор В.Данко

Заказ 1972/47 Тираж 673 Подписное

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

113035, Москва, 3-35, Раушская наб., д. 4/5

Производственно-полиграфическое предприятие, r. Ужгород, ул. Проектная, 4