Счетчик

 

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

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

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

РЕСПУБЛИК (19) (11) (51) 4 H 03 K 23/00

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

К А ВТОРСКОМУ СВИДЕТЕЛЬСТВУ

ЯЩЯР9 - ::;

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИИ (21) 4163308/24-21 (22) 19. 12.86 (46) 07.09.88. Бюл. N 33 (71) Московский инженерно-физический институт (72) M.À.Èâàíoâ (53) 62 1.374(088.8) (56) Авторское свидетельство СССР

9 1116431, кл. Н 03 К 21/00, 1983,.

Иванов М.В., Кларин А.П.Сигнатурный анализ в задачах контроля и диагностики цифровых устройств. — M.

МИФИ, 1986, с. 28, рис, 13. (54) СЧЕТЧИК (57) Изобретение относится к области автоматики и вычислительной техники.

Цель изобретения — расширение функциональных возможностей счетчика.

Счетчик содержит N регистров 1, где

N — степень образующего многочлена, К групп 2 блоков 3 умножения, К бло.ков 4 деления, К блоков 5 сложения, где 1 б К < N, и элемент И 6. Введение и блоков 9 сложения, где 0 п бМ-К, и образование новых функциональных связей обеспечивают счетчику возможность счета по любому модулю, не пре вышающему 1., и увеличивают его надежность ° 4 ил.

1422403

Изобретение относится .к импульсной технике и может быть использовано в устройствах автоматики и вычислительной техники.

Целью изобретения является расширение функциональных возможностей за счет обеспечения возможности счета н по любому модулю, не превышающему L и увеличение надежности. 10

На фиг. 1 дана блок-схема счетчика; на фиг. 2 — пример выполнения счетчика для Е = 5, К = 1; на фиг.З— таблица соответствия элементов поля

GF(5) содержимому регистров, на 15 фиг.4 — таблица переходов устройства.

Счетчик (фиг. 1), содержащий N регистров 1, где N — степень образующего многочлена, К групп 2 блоков 3 умножения, K блоков 4 деления, К первых 20 блоков 5 сложения, где 1 » К » И, элемент И 6, выход которого соединен с соответствующими входами последних групп входов К первых блоков сложения, оставшиеся группы входов которых через соответствующие блоки умножения соответствующих групп подключены к выходам соответствующих регистров, выходы K первых блоков 5 сложения через соответствующие блоки 4 деления 30 соединены с информационными входами первых К регистров, тактовые и установочные входы регистров соединены соответственно с тактовым 7 и устано-1 вочным 8 входами счетчика. Устройст35 во также содержит и вторых блоков 9 сложения, где 0 «»п «» (N-К), выход элемента И соединен с соответствующими. входамн первых групп входов вторых блоков сложения, вторые группы входов которых соединены с выходами соответствующих предыдущих регистров, выходы вторых блоков сложения соединены с информационными входами соответствующих последующих N-К регистров, входы элемента б И соединены с выходами регистров.

Счетчик работает следующим образом, Число РегистРов счетчика И. опреде-5 ляется степенью образующего многочлена, .коэффициенты которого принадлежат полю Галуа из L элементов, где L— степень простого числа, степень образующего многочлена определяется, в свою очередь модулем счетчика и наУ

N х од итс я из выр аже ния М «» L

Основу счетчика составляет гене-, ратор L-ричных псевдослучайных последовательностей, в состав которого входят регистры, блоки умножения, сложения и деления в поле Галуа из

L элементов GF(L). Исходными данными для проектирования собственно генератора являются L, К, N, Ф(х), где L — степень простого числа, К> 0 — целое,-"N — степень образующего многочлена Ф(х), примитивного над

GF(L).

Генератор функционирует в соответствии с уравнением

Q(t + I) = Q(t) ° 7 где Q(t) и Q(t+1) — векторы, характеризующие состояние регистров генератора в момен" ты й,и a+1 соответственно, Т вЂ” квадратная матрица порядка N вид которой однозначным образом определяется образующим многочленом

Ф(х) = а х + ... а х + ... ах +

+ а,, а;, аЕ GF(L).

В состав генератора входят N регистров, разрядность которых равна

R = 1 logzL ((величина R должна позволять представлять в двоичном виде числа от 0 до Ь-1). В состав генератора входят также К блоков сложения (БС) в поле GF(L), К блоков деления в поле .GF(L), К групп блоков умножения (БУ) в поле GF(L). Величины, на которые происходит умножение и деление в соответствующих БУ и БД, однозначно определяются видом сопровожда ющей матрицы Т . При К = 1 (фиг.1) величина, на которую происходит умножение в i-м БУ, i = 1,N, равна соответствующему коэффициенту а; образующего многочлена Ф(х), величина, на которую происходит деление в блоке деления (БД), равна а„ где а, - свободный член Ф(х). БС, БУ и БД представляют собой комбинационные схемы, которые строятся на основе соответствующих им таблиц истинности, которые, в свою очередь, однозначно определяются правилами сложения, умножения и деления в поле GF(L), а так» же соответствием между элементами поля и содержимым регистров генератора. При L = 2, где Р > 0 — целое, Р указанные блоки легко реализуются на

1422403 сумматорах по модулю два. В более сложJ:ûõ случаях возможна их реализация на основе ПЗУ. В последнем случае карта загрузки ПЗУ опять же однозначно определяется правилами выполнения соответствующих операций.

Для построения счетчика по произвольному модулю M в устройство дополнительно введено N-К вторых БС и элемент И, а также новые связи. Каждый из К первых БС в самом сложном случае, когда все коэффициенты а;, отличны от нуля, имеет N+1 групп входов, причем в каждой группе R-входов.

Часть входов последней группы входов первых и вторых БС (вторые БС всегда имеют две группы входов) подключается к выходу элемента И.

Оставшиеся N групп входов первых блоков сложения через соответствующие

БУ подключаются к выходам соответствующих регистров. Каждый из блоков умножения и сложения имеет R-входов и R-выходов. Если соответствующий коэффициент а, образующего многочлена равен 1, то i-й БУ осуществляет умножение на 1, что эквивалентно простой передаче сигналов с входов на выходы

БУ без изменения, Аналогично, если а, = 1, то соответствующий БД также осуществляет простую передачу сигналов со своих входов на выходы без изменения.

Для того, чтобы на выходе элемента

И мог появляться сигнал лог. "1", один из элементов поля GF(L) должен представляться в виде комбинации "все единицы". Конкретный вид соответствия между элементами поля GF(L) и содержимым регистров никак не влияет на структуру и характер функционирования устройства. При L = 2 комбинация все единицы автоматически соответствует одному из элементов поля

СР(2 ).

Алгоритм построения синхронного счетчика по заданному модулю M имеет следующий вид. н

На основе неравенства L ъ М выбирается многочлен Ф(х) степени N, примитивный над GF(L) °

Если М с Е 1, то переходим к шагу Ь, в противном. случае синтез счетчика сводится к построению по известным правилам генератора L-ричной н последовательности длиной L или

1 -1.

Моделируем (L — M) тактов работы н генератора, соответствующего Ф(х) с начальным состоянием q(n) = (q,(O) ° ° °

q;(О)... Q (0)f = а,... а",,... а„), где а E GF(L), i = 1,N.

Определяем состояние Q(L — M)

Pq,(т, - и)... Q;(L — М) . . (?." — M) = pb ... Ь ... bÄ), в ко10 торое должен перейти генератор из состояния (а,... а; ... ан), b,, E GF(L).

Строим счетчик в соответствии с уравнением

Q(t + 1) = Q(t) Т + z С, где С,= (С,... С;... Сн), С„ — L-ричное число, поступающее на соответствующую группу входов i-го БС, когда сигнал z = 1

20 z — сигнал, принимающий единичное значение, если генератор находится в состоянии (а,... а ... а„), где а — элемент

GF(L), которому соответствует код

Все единицы", C; E GF(L) находятся из равенств н где а; — элементы Т

Таким образом, необходимый модуль

30 пересчета обеспечивается за счет пропуска генератором некоторых из своих состояний.

На фиг.2 показан пример конкретной реализации счетчика для случая М =

35 23, L = 5, Ф(х) = Зх + х + 4 примитивный над CF(S), К = 1.

Основу счетчика составляет генератор пятиричной псевдослучайной послен довательности длины L — - 1 = 24. На

4р фиг.3 показан один из возможных вариантов соответствия элементов GF(5) и состоЯний регистров генератора и

a, = а = 4. Так как требуемый модуль пересчета на единицу меньше периода

45 последовательности генератора (который равен числу состояний регистров генератора), .в устройстве должна быть обеспечена возможность пропуска одного состояния регистров, а именно сос50 тояния, которое следует сразу за сос тоянием (а, а j = (4,4). Моделирование

N — М = 2 тактов работы генератора позволяет определить состояние, которое должно быть пропущено — (1 4), и

55 со оян е, в которое должен перейти генератор из состояния (4 4) (b,b j = j3 11. Отсюда можно найти слагаемые С, и С, которые необходимо подать на соответствукщие группы

142? 403 вхс,:,он БС, чтобы при z = 1 (z = 1, ког,„.а регистры 2, и 2 находятся в состоянии (а» а ) = (4 44) ) регистры устройства из состояния (4 4) сразу

5 г.=-ð åmëu н состояние (3 1), пропустин состояние fl 4) . С„= 2. C = 2. Для того, чтобы на соответствующие входы

БС при z = был подан код "?" 101 (фиг.З), необходимо первый и третий 10 входы соответствующих входов подключить к выходу элемента И, на выходе которого формируется сигнал z, а остальные, соответствующие "0 в представлении числа 2, т.е. вторые, под- 15 ключить к шине лог. "0" (фиг.2). При — 2 или реализации БС на основе

ПЗУ при Е г 2 подключать к шине с лог. "0" входы, соответствующие "0" в представлении чисел С, нет необхо- 20 димости. На фиг. 1 показаны только связи некоторых входов соответствую- ших групп входон БС с выходами элемента И.

Один из блоков 3, умножения, осуществляющий умножение на а, = 1, и блох деления, осущестнпяющий деление

-4 =. 1 (фиг.2), показаны пунктиро, так как осуществляют простую пе- 30

".: äà,у сигналов со своих входов на ньгкоды без изменения.

Уравнения работы счетчика по мо) q, (-ь",) =

q„(t+l) = jq, (t) + z 2< (mod 5), О; () и q; (t+1) — содержимое

1.-го регистра н моменты времени t u

t+1 соответственно, i = 1,2.

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

Счетчик, содержащий N регистров, где N — степень образующего многочлена, К групп блоков умножения, К блоков деления, К первых блоков сложения, где 1 К N, элемент И, выход которого соединен с последней группой входов К первых блоков сложения, оставшиеся группы входов которых через соответствующие блоки умножения соответствующих групп подключены к выходам соответствующих регистров, выходы

К первых блоков сложения через соответствующие блоки деления соединены с информацибнными входами первых К регистров„ тактовые.и установочные входы регистров соединены, соответственно, с тактовым и установочным входами счетчика, о т л и ч а ю щ и й-, с я тем, что, с целью расширения функциональных возможностей и увеличения надежности, он дополнительно содержит п вторых блоков сложения, где 0 п (N-К), причем выход элемента И соединен с соответствующими входами первых групп входов вторых блоков сложения, вторые группы входов которых соединены с выходами соответствующих предыдущих регистров, выходы вторых блоков сложения соединены. с информационными входами соответствующих последующих (N-К) регистров, входы элемента И подключены к выходам регистров.!

422403

Редактор О.Головач

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

f

4 г

4 о г г

4

О

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

Техред М.Ходанич Корректор И.Муска

Заказ 444!/57 Тираж 928 Подписное

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

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

0

2