Устройство для определения двузначного характера элементов конечного поля @ Советский патент 1987 года по МПК G06F7/52 

1

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

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

На фиг.1 приведена схема устройства для определения двузначного характера элементов конечного поля; на фиг.2 - схемы прямого генератора поля GFCp) и обратного генератора по- ля GF(p).

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

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

каком-то и, так как любой ненулевой элемент а поля GF(p ) может быть представлен как степень примитивного

livyjl/l 1.4J 1W riDlJTA1

элемента d. Если U четно, то Ч(а) 1, 30 у элементу числового подполя в противном случае Ф(а) -1.-Функция Ч(а) имеет следующее свойство

Таким образом, прямой и обратный генераторы поля GFCp ) удаляются от элемента а oi в разные стороны. Если прямой генератор поля GFCp) устремляется к элементу числового под- поля оС , то обратный - к предыдуГенерирование продолжается до тех пор, пока одним и генераторов не будут сформирован элемент видаoL f где m 1,2,..., р-1, Ь(р -1Ир-1). 35 Как уже отмечалось, с 1-й по (п-1)-ю координаты элемента оС равны нулю, поскольку Ы является элементом числового подполя GF(p). Эти нули дешифрируются тем дешифратором нуля, на входах которого они появились. Сигнал с выкода этого дешифратора нуля останавливает работу устройства.

двузначного характера:

Ц(аЪ) 4(a).iV(b),

(1)

где а и Ь, а также произведение а.Ь являются элементами поля .

В самом деле, если а d IA ,Ъ , А при каких-то и и V, то аЬ с. Если и и V оба четны, т.е; vCa) Ч (Ь) 1, или оба нечетны, т.е. (а) (Ъ), -1, то U+V четно, и VCab) (d) . . Если же только один из и г/ V нечетен, то U+V нечетно, и Ч С) -1.

Любой а «. поля GF(p) может быть записан как сумма вида

а,с.

+ a,j -«.

п- I

(2)

при соответствующем подборе элементов а (,2,,..,п) числового подполя GF(p), Таким образом, элементу

„, I (|

- Л

50 яние {а,а,...,а, соответствующее элементу поля GF(p), двузначный характер которого надо определить. Одновременно обнуляется триггер 9 по входу установки в нуль. Далее, если

а ut можно поставить в однозначное 55 элемент а &(. имеет вид , где соответствие (а, ,а ,... ,. Отметим, h()/(р-1), т 1,2,;..,р-1, то с что элементу числового подполя GF(p) 1-й по (п-1)-ю координаты этого элесоответствует вектор, у которого со 2-1 по п-ю компоненты равны нулю.

13125682

Изначально прямой и обратный генераторы поля GF(p) по объединенным установочным входам устанавливаются

соответ и. В то же врев состояние |а ,а,...,с ствующее элементу а ot- . мя триггер устанавливается в нулевое состояние. Под воздействием тактовых импульсов прямой генератор поля GF(p) начинает генерировать элементы поля GF(p ) в порядке возрастания степеней примитивного элемента d ,т.е.

а

, , 1И-1 , U + 2 rf at i ol

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

U

ot ,

, и-1 oL ,

Ы

и-ч

livyjl/l 1.4J 1W riDlJTA1

у элементу числового подполя

Таким образом, прямой и обратный генераторы поля GFCp ) удаляются от элемента а oi в разные стороны. Если прямой генератор поля GFCp) устремляется к элементу числового под- поля оС , то обратный - к предыду у элементу числового подполя

I нт Ь

Генерирование продолжается до тех пор, пока одним и генераторов не будут сформирован элемент видаoL f где m 1,2,..., р-1, Ь(р -1Ир-1). Как уже отмечалось, с 1-й по (п-1)-ю координаты элемента оС равны нулю, поскольку Ы является элементом числового подполя GF(p). Эти нули дешифрируются тем дешифратором нуля, на входах которого они появились. Сигнал с выкода этого дешифратора нуля останавливает работу устройства.

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

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

55 элемент а &(. имеет вид , где h()/(р-1), т 1,2,;..,р-1, то с 1-й по (п-1)-ю координаты этого элемента равны нулю (а а ...а Ь ,

т.е. ci

а

Это означает, ч то . . 31

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

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

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

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

осуществляется триггером 9 и сумматором 10 .по модулю два. В самом де- .ле, если Z не.четно, то триггер 9 после остановки окажется в единичном

35 состоянии, и на второй вход суммато- . ра 10 по м.одулю два подается единица Тогда сигналы на первом входе и на выходе сумматора 10 по модулю два противоположны, что соответствует про40 тивоположным значениям двузначного характера (tJL ) и искомого двузначного характера. Если Z четно, то с выхода триггера .9 на второй вход сумматора 10 по модулю два подается нуль

.U

не

В случае, когда элемент а ;(. равен где h (р -1)/(р-1) , m 1,2,...,р-1, ни один из дешифраторов нуля не формирует на своем вы- ходе сигнала запрета на элемент ИВ. Поэтому под воздействием тактовых импульсов на своем тактовом входе пря- мой генератор 1 поля GF(p) начинает генерировать элементы поля GFCp в порядке возрастания степеней примитивного элемента oi а обратный генератор 5 поля GFCp) - в порядке убывания степеней этого же примитивного элемента. Это продолжается до тех пор, пока на выходе хотя бы одного из генераторов поля pF(p) не

4

появится элемент вида . Предположим., что это произошло через Z тактов. Если этот -элемент ог. был первым по времени сгенерир1Ован прямым генератором 1 поля GFCp), то это означает, что наступило .равенство р( , которое фиксируется первым дешифратором 2 нуля.

Сигнал с выхода последнего пре кра- щает прохождение тактовых импульсов через элемент Ичб, останавливая та- КИМ образом работу устройства. Этот же сигнал с выхода первого дешифратора 2 нуля заставляет мультиплексор 3 проЬустить на свой выход сигнал с первого р-ичного выхода прямого ге- Hepafopa 1 поля GFCp). Дешифратор 4 знака определяет двузначный характер элемента ,. т.е. находит Ц (cf ) . Поскольку работа устройства была остановлена при наступлении равенства о..ь , q;(t ц( - Ь) „

с учетом (1) дает (d) ()(d )

20

25

т.е. искомый двузначный характер .элемента а о совпадает с характером V (р( ), определяемым дешифратором 4 знака, если Z четно, и противоположен Ч ( , если Z нечетно.. Учет влияния четности или нечетности

30 Z на двузначный . характер элемента

-о) 5

осуществляется триггером 9 и сумматором 10 .по модулю два. В самом де- .ле, если Z не.четно, то триггер 9 после остановки окажется в единичном

35 состоянии, и на второй вход суммато- . ра 10 по м.одулю два подается единица. Тогда сигналы на первом входе и на выходе сумматора 10 по модулю два противоположны, что соответствует про40 тивоположным значениям двузначного характера (tJL ) и искомого двузначного характера. Если Z четно, то с выхода триггера .9 на второй вход сумматора 10 по модулю два подается нуль

45 и выходной сигнал сумматора, т.е. выход устройства, совпадает с выход сигналом дешифратора 4 знака, что и требуется при четном Z.

Если первый по времени элемент вида ot.T был сформирован обратным ге- нерат.ором 5 поля GF(p) то, следовательно, такте наступило равенство с. oL , которое фиксируется в этом случае вторым дешифратором 6 нуля. Сигнал d выхода этого дешифратора запрещает прохождение тактовых импульсов через элемент И 8, останавливая работу устройства, и переклю5. 13125686

чает мультиплексор 3 таким образом, ду элемента И, второй вход элемента что на его выход поступают сигналы И подключен к выходу генератора так- с первого р-ичного выхода обратного товых импульсов, выход элемента И генератора 5 поля GFCp ).подключен к счетному входу триггера.

Дешифратор 4 знака определяет г выход дешифратора знака подключен к двузначньш характер Ф( ) ,выда- первому информационному входу сумма- вая как и прежде, на первый вход сум- тора по модулю два, второй информа- матора 10 по модулю два единицу, ее- ционный вход которого подключен к выли Ч ({, ) -1, и нуль, если V ( ходу триггера, выход результата уст- 1. Поскольку в этом случае останов- Ю ройства подключен к информационному ка предложенного, устройства наступи- .выходу сумматора по модулю два, вход ла при равенстве ot , ) установки устройства в исходное сое- Ф(Ы ), т.е. согласно (1)(ы )х тояние подключен к входу установки в Ф (Ы ) ф(). Поскольку значения О триггера, отличающееся двузначного характера Элементов по- 15 тем, что, с целью повьшения быстро- ля GFCp), расставл.енных в порядке действия, в него введены второй де- убывания степеней примитивного эле- шифратор нуля, мультиплексор и обрат- мента, определяются четностью или ный генератор поля GF(p), с первого нечетностью номера элемента в этой по п-й входы коэффициентов представ- последовательности, ) совпала-20 ления элементов поля устройства под- ет с V (d ), если Z четно, и ) ключены к информационным входам об- противоположно f (), если Z нечетно ратного генератора поля GFCp), выходы с первого по (п-1)-й обратного

Формула изобретен.ия генератора поля GF(p) подключены к

25 входам второго дешифратора нуля, п-й

Устройство для определения дву- выход прямого генератора поля Gr() значного характера элементов конечно- и п-й выход обратного поля GF(p) го поля GF(p), содержащее прямой ге- подключены соответственно к первому нератор поля GF(p), первый дешифра- и второму информационным входам муль- тор нуля, дешифратор знака, генератор 30 типлексора, в.ыход которого подключен тактовых импульсов, элемент И, триг- к информационному входу дешифратора гер, сумкатор по модулю два, с перво- знака, выход первого дешифратора нуля го по п-й входы коэффициентов пред- подключен к первому управляющему вхо- ставления элементов поля устройства ду мультиплексора, выход второго де- подключены к информационным входам j шифратора нуля подключен к второму прямого генератора поля GFCp), вы- управляющему входу мультиплексора и к ходы с первого по (п-1)-й прямого третьему входу элемента И, выход ко- генератора поля GFCp) подключены к торого подключен к тактовым входам входам первого дешифратора нуля, вы- прямого и обратного генераторов поход которого подключен к первому вхо- ля GF(p).

Прямой генератор поля (гР(р

Изобретение относится к технике генерирования сложных сигналов. Цель изобретения - повышение быстродействия устройства. Поставленная дель достигается тем, что устройство содержит прямой генератор 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 ил. (О (Л

Обратный генера/тр поля G-F{р

гс.

м

гп-1

- ijмножитель на л по мод(/лю р

Ь р - ичный элемент задержки на один такт

сумматор по модулю Р Фиг. г

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

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

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

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

ВНИИПН Государственного комитета СССР

по делам изобретений и открытий 113035, Москва, Ж-35, Раушская наб., д. 4/3

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