Устройство для распознавания образов Советский патент 1987 года по МПК G06K9/00 

1

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

Цель изобретения - повышение быстродействия устройства за счет ускорения процесса сравнения признаков образов.

На фиг.1 приведена структурная схема устройства; на фиг .2 - структурная схема блока управления.

Устройство для распознавания образов содержит блоки 1 и 2 сравнения, 15 Элемент 20 задержки осуществляет элемент ИЛИ 3, кольцевой сдвигающий задержку на время 2Т + 2Т:5 относиблок 6

регистр 4, счетчик 5 адреса, памяти, блок 7 управления, параллельный регистр. 8, мультиплексор 9, дополнительный счетчик 1Г) адреса, эле- 20 мент 11 задержки. Блок управления содержит триггер 12, второй элемент 13 задержки, генератор 14 импульсов, первый элемент 15 задержки, элемент И 16, третий элемент 17 задержки, 25 четвертый элемент 18 задержки, элемент И-НЕ 19,пятый 20 и шестой 21 элементы задержки, триггер 22.

Реализовано устройство на следующих интегральных микросхемах: блоки ЗО 1 и 2 сравнения - К 531 СП 1П, К 531 ЛИ 1П; элемент ИЛИ 3 - К 531 ЛЕ Ш; регистры 4 и 8 - К 155 ИР 13; счетчики 5 и 10 - К-531 НЕ 7П; блок 6 памяти - К 155 РЕ 3; мультиплексор 9 - К 531 КП 7П; тригг ер 12 - К 531 ТВ 9П; элементы 11, 13, 15, 17, 18, 20 и 21 задержки - К 155 АГ 3; элемент И 16 - К 531 ЛИ ЗП; элемент И 19 - К 531 ЛА 2П; триггер 22 - К 40 531 ТМ 2П.

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

В исходном состоянии (перед началом распознавания) в каждый разряд 45 кольцевого сдвигающего регистра 4 и параллельного регистра 8 занесены 1, счетчики 5 и 10 обнуления, триггер 12 установлен в О, триггер 22 установлен в 1 (линии обнуления 50 и установки не показаны).

Элементы задержки устройства осуществляют задержки и формируют следующие длительности импульсов. Э.ле35

тельно импульса, появляющегося йа выходе элемента И-НЕ 19, и формируе импульс длительностью Т : 2. Элемен 11 задержки осуп1ествляет задержку н время 2Т : 5 относительно импульса, формируемого мультиплексором 9, и формирует импульс длительностью Т. Элемент 21 задержки осуществляет задержку на время Т : 2 относительн импульса, формируемого элементом 20 задержки, и формирует импульс длительностью Т : 2. Т - период тактовой частоты генератора 14.

С приходом первого тактового импульса с генератора 14 импульсов на второй вход элемента И 16, на пе вом и третьем входах которого 1, на его выходе появляется импульс, который поступает на счетный вход счетчика 5 через элементы 17 и 18 задержки на вход разрешения записи регистра 4, через элемент 17 задержки на вход элемента И-НЕ 19 и на вх.од синхронизации мультиплексора 9 На разрядных выходах счетчика 5 появляется первый адрес ячейки блока 6 памяти, который поступает соответственно на информационные входы счетчика 10, на первые входы мультиплексора 9 и входы элемента И-НЕ 19 Так как на первые (селекционные) вхо ды мультиплексора 9 прищел первый адрес ячейки блока 6 памяти и так как на втором информационном входе мультиплексора 9 уровень 1, Црихо- дящей с младщего разряда регистра 8 то по приходу стробирующего импульса с выхода элемента 17 задержки на

мент 13 задержки осуществляет задерж-55инверсном выходе мультиплексора 9

ку на время Т относительно срезапоявляется импульс О, который, посимпульса, формируемого триггером 12,тупив на тактовьт вход триггера 12,

и формирует импульс длительностьюустанавливает на своем инверсном выТ : 2. Элемент 15 задержки осущест-ходе уровень О, заблокировав про5

5А2232

вляет задержку на время Т + Т:10 относительно фронта импульса, формируемого триггером 12, и формирует импульс длительностью Т:2 + Т: 10. Элемент 17 задержки осуществляет задержку на время 2Т:5 относительно импульса, появляющегося на выходе элемента И 16, и формирует импульс длитель- 1Q ностью Т:2, Элемент 18 задержки осу- П5естБляет задержку на время 2Т относительно импульса, появляющегося на выходе элемента 17 задержки, и формирует импульс длительностью Т : 2.

0 5

О 0

5

5

тельно импульса, появляющегося йа выходе элемента И-НЕ 19, и формирует импульс длительностью Т : 2. Элемент 11 задержки осуп1ествляет задержку на время 2Т : 5 относительно импульса, формируемого мультиплексором 9, и формирует импульс длительностью Т. Элемент 21 задержки осуществляет задержку на время Т : 2 относительно импульса, формируемого элементом 20 задержки, и формирует импульс длительностью Т : 2. Т - период тактовой частоты генератора 14.

С приходом первого тактового импульса с генератора 14 импульсов на второй вход элемента И 16, на первом и третьем входах которого 1, на его выходе появляется импульс, который поступает на счетный вход счетчика 5 через элементы 17 и 18 задержки на вход разрешения записи регистра 4, через элемент 17 задержки на вход элемента И-НЕ 19 и на вх.од синхронизации мультиплексора 9. На разрядных выходах счетчика 5 появляется первый адрес ячейки блока 6 памяти, который поступает соответственно на информационные входы счетчика 10, на первые входы мультиплексора 9 и входы элемента И-НЕ 19. Так как на первые (селекционные) входы мультиплексора 9 прищел первый адрес ячейки блока 6 памяти и так как на втором информационном входе мультиплексора 9 уровень 1, Црихо- дящей с младщего разряда регистра 8, то по приходу стробирующего импульса с выхода элемента 17 задержки на

хождение тактовых импульсов через элемент И 16, а перепадом этого уровня, поступающим на элемент 13 задержки, формирует в ней нулевой импульс, который, поступив на вход установки триггера в О, устанавливает триггер 12 в исходное состояние. На прямом выходе мультиплексора 9 появляется импульс 1, который записывает в счетчик 10 информацию с выхода счетчика 5, выставив нд своих разрядных выходах первый адрес ячейки блока 6 памяти, и через элемент 11 задержки поступает в блок 6 памяти, разрешив выдачу информации, хранящейся в первом адресу ячейки блока 6 памяти. Проверка принадлежности измеренного признака Р, соответствуюряд регистра 4 по сигналу, поступившему с элемента 18 задержки, что соответствует исключению из дальнейшего рассмотрения класса образов с порядковым номером i.

Аналогично производится проверка принадлежности i-ro признака интервалом (а;; , В;; ), i 1, N (для всех

j J н ij

ТО N классов). Адреса ячеек блока 6 памяти, в которых хранятся границы интервалов, задаются счетчиком 10 адреса. При анализе j-ro признака с последним интервалом на соответствующих

15 входах элемента И-НЕ 19 с соответствующих разрядных выходов счетчика 5 появляются 1 и с приходом задержанного элементом 17 задержки импульса на соответствующий вход элемента

импульс U, который устанавливает триггер 22 в нуль,.заблокировав прохождение тактовых импульсов через элемент И 16, через элемент 20 занения - условия PJ м Величина с входа устройства распознавания поступает на первые входы блоков 1 и 2 сравнения. На третьи входы этих блоков из блока 6 памяти поступают

величины а;;

соответственно.

ЗЕ

щего интервалу (а, в), осуществляется 20 И-НЕ 19 на его выходе сформируется блоками 1 и 2 сравнения по сигналу импульс О с элемента 15 задержки, который сформируется перепадом с О на 1 на прямом выходе триггера 12.

Блок 1 сравнения осуществляет про- 25 держки записывает в регистр 8 инфор- верку условия 5 a;j , а блок 2 срав- мацию из регистра 4, занявшего исход- ное положение. Информация в регистре

8 хранится в течение циклов сравнения каждого признака Р. со всеми 30 интервалами (a;j , в-- ), не исключенными из дальнейшего рассмотрения классов образов с порядковыми номерами, и запись обновленной информации в него происходит после прохождения этих циклов, когда регистр 4 занимает исходное положение. Импульс с элемента 20 задержки, задержанный элементом 21 задержки, устанавливает триггер 22 в 1, разрешив прохождение тактовых импульсов через элемент И 16. Таким образом начинается анализ следующего (J + 1)-го признака.

При анализе признаков,следующих после первого, на разрядных выходах 45 .регистра 8 возможно присутствие как ГГ , так и П. Присутствие О свидетельствует о том, что признак Р не попал в соответствующие интерва- лы и они исключены из набора N классов. Поэтому при адресах, последовательно формируемых счетчиком 5, по которым соответственно находятся интервалы, исключенные из набора Ь классов мультиплексором 9, не вырабатываются импульсы записи этих адресов в счетчик 10 и сравнение признаков с интервалами, хранящимися по этим адресам, не производится. Процесс анализа признаков продолжается

и в,

Выходы блоков 1 и . сравнения подаются на входы элемента ИЛИ 3, выход которого подключен к информационному входу младшего разряда кольцевого сдвигающего регистра 4. Число разрядов регистров 4 и 8 равно числу классов образов N. Причем номера разрядов регистров 4 и 8 соответствуют порядковым номерам классов образов. Информация в регистре 4 может циркулировать, переписьшаясь с выхода на . вход. Циркуляция осуществляется синхронно с извлечением значений границ интервалов из блока 6 памяти таким образом, что при извлечении интервала (а;; , в- ) i-ro класса в младшем разряде регистра 4 находится информация, содержавшаяся в исходном состоянии в i-M разряде кольцевого сдвигающего регистра 4. При попадании признака Р1 в интервал (а ; , ) информация в младшем разряде регистра 4 сохраняется. В противном случае хотя бы один из блоков 1 и 2 сравнения вьфабатывает на своем выходе единичный сигнал, который через элемент ИЛИ 3 записывает О в младший раз40

50

55

354223

ряд регистра 4 по сигналу, поступившему с элемента 18 задержки, что соответствует исключению из дальнейшего рассмотрения класса образов с порядковым номером i.

Аналогично производится проверка принадлежности i-ro признака интервалом (а;; , В;; ), i 1, N (для всех

j J н ij

ТО N классов). Адреса ячеек блока 6 памяти, в которых хранятся границы интервалов, задаются счетчиком 10 адреса. При анализе j-ro признака с последним интервалом на соответствующих

15 входах элемента И-НЕ 19 с соответствующих разрядных выходов счетчика 5 появляются 1 и с приходом задержанного элементом 17 задержки импульса на соответствующий вход элемента

импульс U, который устанавливает триггер 22 в нуль,.заблокировав прохождение тактовых импульсов через элемент И 16, через элемент 20 заИ-НЕ 19 на его выходе сформируется импульс О

до тех пор, пока во всех разрядах регистра 4, за исключением одного, не оказываются О. Распознаваемый образ идентифицируется с тем классом, номер которого совпадает с номером разряда кольцевого сдвигающего регистра 4, в котором сохранилась 1.

Значительное повышение быстродействия распознавания достигается в результате . и исключения интерва- лов, -в которые не попадают предыдущие признаки после циклов из сравнения со всеми, не выбывшими из процесса сравнения, интервалами. Поэтому исключенные интервалы выбирают из дальнейшего процесса сравнения с последующими признаками.

Путем введения параллельного регистра, мультиплексора, второго счетчика адреса, элемента задергкки и изменения блока управления достигается cymecTBeHEioe увеличение рабочей частоты, на которой работает устройство, и реализуется быстродействующий принцип функционирования устройства.

10

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

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

15

20

Формула

35

элементы И и H-FiE, генератор импульсов и шесть элементов задержки, причем прямой выход первого триггера

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

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

д0 которого подключен к входу четвертого элемента задержки и первому входу элемента И-НЕ, остальные входы которого являются адресным входом блока управления, а выход соединен с входом пятого элемента задержки и входом установки в О второго триггера, вход установки в 1 которого подключен к выходу шестого элемента задерж- ки, вход которого соединен с прямым выходом пятого элемента задержки, выходы четвертого элемента задержки и элемента И, а также инверсный выход пятого элемента задержки и выход третьего элемента задержки являются

rg вторым, третьим, четвертым и пятым выходами блока управления соответственно.

1. Устройство для распознавания образов, содержащее два блока сравнения, блок памяти, счетчик адреса, элемент ИЛИ, кольцевой сдвигающий регистр и блок управления, причем первые входы блоков сравнения являются инфopмaциoнны ffl входами устройства, вторые входы подключены к первому выходу блока управления, а третьи входы - к выходу блока памяти, входы элемента ИЛИ подключены к выходам блоков, сравнения, а выход - к информационному входу кольцевого сдвигающего регистра, выход которого является выходом устройства, а вход синхронизации подключен к второму выходу блока управления, третий выход которого соединен со счетным входом счетчика адреса, отличающееся тем, что, с целью повышения быстродействия, в устройство введены параллельный регистр, информационный вход которого подключен к выходу кольцевого сдвигающего регистра, а вход синхронизации - к четвертому выходу блока управления, мультиплексор, первые и вторые информационные входы которого подключены к адресному входу блока

45

50

,

10

354223

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

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

15

20

S)f.3an.

Составитель А.Краснов Редактор Н.Бобкова Техред Л.Олийнык Корректор И.Муска

Заказ 5696/45 Тираж 671 Подписное ВНИИПИ Государственного комитета СССР

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

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

Уаг.г

Изобретение относится к автоматике и вычислительной технике и 8х. может быть использовано в системах автоматического распознавания знаков, сигналов, кодов. Пелью изобретения является повышение быстродействия устройства за счет ускорения процесса сравнения признаков образов. Устройство содержит два блока 1, 2 сравнения, блок 6 памяти, два счетчика 5, 10 адреса, элемент ИЛИ 3, два регистра. 4, 8, блок 7 управления, мультиплексор 9, элемент 11 задержки. Введение дополнительного регистра, мультиплексора, счетчика адреса, элемента задержки и изменение блока управления позволяют повысить рабочую частоту устройства и увеличить его быстродействие. 1 з.п. ф-лы, 2 ил. (Л СА:) СЛ 4 to со