Przedmiotem wynalazku jest urzadzenie do prze^ twarzania danych przeznaczone do automatycznego wyszukiwania lancucha uporzadkowanych znaków w strumieniu danych czytanych z tasmy magne¬ tycznej, linii transmisyjnej lub innego nosnika.W procesie przetwarzania danych wystepuje czesto koniecznosc lokalizowania lancucha uporzad¬ kowanych znaków przechowywanych na jakims nosniku maszynowym lub przychodzacych z innego zródla danych podczas operacji wydawniczych, ope¬ racji przesylania, przetwarzania itd. Zwykle wyma¬ ga to utworzenia uporzadkowanego strumienia znaków wzorcowych, za pomoca którego mozna zidentyfikowac lancuch poszukiwany.Problem porównywania uporzadkowanych lancu¬ chów znaków staje sie bardziej zlozony w przy¬ padku zmiennej dlugosci porównywanych lancu¬ chów. Problemy te rozwiazywano dotychczas w róz¬ ny sposób. Jeden ze sposobów polega na zastoso¬ waniu liczników dwójkowych, z których jeden zli¬ cza porównywane znaki, a drugi jest ustawiony na wartosc odpowiadajaca dlugosci porównywanych lancuchów. Stosowanie takich liczników ma pewne wady, jak dodatkowe koszty, nieefektywne wyko¬ rzystanie przestrzeni i zmniejszenie niezawodnosci ukladu.Celem wynalazku jest opracowanie uproszczone¬ go ukladu automatycznego wyszukiwania lancucha uporzadkowanych znaków o zmiennej dlugosci, po¬ chodzacych ze zródla. 15 20 30 2 Urzadzenie wedlug wynalazku zawiera pierwszy dynamiczny rejestr pamieciowy, przeznaczony do przechowywania badanego lancucha uporzadkowa¬ nych znaków o dlugosci co najwyzej M znaków na M + 1 pozycjach rejestru, przy czym M jest liczba calkowita wieksza lub równa 3.Drugi dynamiczny rejestr pamieciowy jest prze¬ znaczony do przechowywania wzorcowego lancucha znaków uporzadkowanych, o dlugosci co najwyzej N na N + 1 pozycjach rejestru, przy czym N jest liczba calkowita wieksza lub równa 1, przy czym M-N jest wieksze lub równe 2.Zastosowano uklady do porównywania lancuchów badanego i wzorcowego w celu stwierdzenia ich zgodnosci. Realizuje sie to za pomoca ukladów prze¬ suwajacych cyklicznie zawartosci odpowiednich re¬ jestrów i porównujacych lancuchy znaków w try¬ bie równoleglym w sensie bitów i szeregowym w serisie znaków w celu wytworzenia sygnalu pierwsze¬ go informujacego o równosci lub nierównosci po¬ równywanych lancuchów.• Zastosowano uklady wytwarzajace sygnal drugi informujacy o tym, czym lancuch badany jest dluz¬ szy niz lancuch wzorcowy. Gdy sygnal drugi wska¬ ze, ze lancuch badany jest dluzszy niz lancuch wzor¬ cowy, nastepuje przesuniecie odpowiednich pozycji znakowych rejestrów co najmniej o jedna pozycje.Porównywanie i odpowiednie przesuwanie trwa do chwili uzyskania sygnalu informujacego o jed¬ nakowej dlugosci lancuchów. Po wytworzeniu syg- 116 380116 380 nalu pierwszego informujacego o równosci porów¬ nywanych lancuchów, mozna wykorzystac zlokalizo¬ wany lancuch znaków do dalszego przetwarzania.Urzadzenie wedlug wynalazku zawiera pierwszy cykliczny rejestr przesuwany M+l pozycyjny,, w którym przechowuje sie badany lancuch uporzadko¬ wanych znaków o dlugosci maksymalnej N znaków.W drugim statyczno-dynamicznym rejestrze N+l pozycyjnym)' przechowuje sie wzorcowy lancuch zna¬ ków o dlugosci maksymalnej N znaków.Zastosowano elementy do porównywania lancu¬ chów badanych z lancuchem wzorcowym w celu odszukania lancucha tozsamego z wzorcowym. Zre¬ alizowano to, stosujac elementy przesuwajace cyk¬ licznie lancuchy znaków w rejestrach i porównu¬ jace te lancuchy równolegle w sensie bitów i sze¬ regowo w sensie znaków w celu wytworzenia syg¬ nalu okreslajacego zgodnosc lub niezgodnosc porów¬ nywanych lancuchów.Zastosowano elementy wytwarzajace drugi syg¬ nal informujacy o sytuacji, gdy lancuch badany jest dluzszy niz lancuch wzorcowy.Gdy sygnal pierwszy sygnalizuje brak zgodnosci, a sygnal drugi — przypadek dluzszego lancucha ba¬ danego, nastepuje przesuniecie lancucha badanego o jedna pozycje wzgledem lancucha' wzorcowego.Porównywanie i przesuwanie trwa az do uzyskania sygnalu pierwszego o wartosci odpowiadajacej rów¬ nosci lancuchów.Do sledzenia polozenia lancuchów badanego i wzorcowego w ich rejestrach zastosowano dwa rejestry znacznikowe. Jeden rejestr znacznikowy jest zwiazany z rejestrem lancucha badanego, a drugi rejestr znacznikowy — z rejestrem lancucha wzorcowego. Jednoczesnie z zaladowanie znaku do któregos z rejestrów znakowych nastepuje zalado¬ wanie znacznika do odpowiedniego rejestru znacz¬ nikowego. Zawartosc rejestrów znacznikowych jest przesuwana cyklicznie z zawartoscia zwiazanych z nimi rejestrów znakowych, dzieki czemu mozliwe jest. sledzenie lancuchów znakowych w kazdym z rejestrów.Urzadzenie wedlug wynalazku zawiera rejestr dynamiczny wykorzystywany jako wejsciowy uklad buforowy dla danych przechodzacych z czytnika, koncówki lub procesora, oraz rejestr dynamiczno- -statyczny przeznaczony do przechowywania i prze¬ suwania lancucha znaków wzorcowych, z którymi porównuje sie znaki rejestru dynamicznego.Urzadzenie wedlug wynalazku ¦ zapewnia ulepszo¬ ny uklad kontroli stanu i sterowania wejsciem/ /wyjsciem rejestru dynamicznego i dynamiczno- -statycznego, wykorzystywanych do porównywania lancuchów znaków przechowywanych w obu re¬ jestrach.Urzadzenie wedlug wynalazku zapewnia równiez ulepszony uklad sterowania do automatycznego wy¬ stukania lancucha uporzadkowanych znaków o zmiennej dlugosci przy jednoczesnej minimaliza¬ cji calosci ukladu i polepszeniu jego niezawodnosci.Przedmiot wynalazku jest przedstawiony w przy¬ kladzie wykonania na rysunku, na którym fig. 1 przedstawia schemat logiczno-blokowy urzadzenia do automatycznego wyszukiwania lancucha znaków uporzadkowanych, o zadanej dlugosci, pochodza- 10 15 40 45 50 55 60 65 cych ze zródla danych, fig. 2 — schemat logiczno- -blokowy start-stopowego ukladu logicznego z ukla¬ du na fig. 1, fig. 3 — schemat logiczno-blokowy ukladu detektora kasowania i ukladu logicznego z fig. 1, fig. 4 — schemat logiczno-blokowy logicz¬ nego ukladu komparatora znakowego z fig. 1, fig. 5 — szczególowy schemat logiczny ukladu logiczne¬ go z fig. 1, fig. 6 — szczególowy schemat detektora pozycji znaku z fig. 1 i fig. 7 — szczególowy sche¬ mat imiego detektora pozycji znaku z fig. 1.Na figurze 1 rejestr pierwszy ma dlugosc 128 po¬ zycji, mozna w nim wiec przesuwac lancuchy o dlugosci co najwyzej 127 znaków, a rejestr drugi — 17 pozycji (móglby miec co najwyzej 125 pozy¬ cji) i mozna w nim przesuwac lancuchy o dlugosci 16znaków. • Na figurze 1 przedstawiono zródlo znaków 1, be¬ dace np. jakims nosnikiem maszynowym. Dla uproszczenia nosnik 18 mozna traktowac jako tas¬ mowy rejestrator magnetyczny, z którego — za po¬ srednictwem ukladu sterowania 16 tasma odczy¬ tuje sie znaki szeregowo w sensie znaków i równo¬ legle w sensie bitów, przy czym znaki te tworza uporzadkowany lancuch.Poniewaz na nosniku 18 przechowuje sie duza liczbe znaków, czesto pozadane jest wybranie spo¬ sród nich okreslonego lancucha znaków. Aby to osiagnac zapamietuje sie lancuch znaków w dyna¬ micznym, cyklicznym rejestrze przesuwajacym 17.W przykladzie wykonania urzadzenia wedlug wy¬ nalazku rejestr 17 ma 128 pozycji znakowych, na których mozna zapamietac odpowiedni lancuch zna¬ ków.Dla ustalenia uwagi zauwazmy, ze dany lancuch znaków nalezy zlokalizowac posród znaków prze¬ chowywanych na nosniku 18.W ukladzie przedstawionym na fig. 1 klawiatura 3 wytwarza lancuch znaków wzorcowych, wprowa¬ dzanych na wejsciowe elementy kombinacyjne 10 statyczho-dynamicznego rejestru wyszukiwania 8, przy czym znaki te wprowadzane sa do rejestru 8 w odpowiedniej kolejnosci i przesuwane sa w kie¬ runku wyjscia tak, ze znak pierwszy pojawia sie jako pierwszy na pozycji wyjsciowej rejestru.W przykladzie wykonania urzadzenia wedlug wy¬ nalazku rejestr 8 zawiera 17 pozycji znakowych.Badany lancuch znaków przesuwa sie w rejestrze 17 pod wplywem impulsów sterujacych C, wystepu¬ jacych na koncówce wejsciowej. W odpowiedniej chwili nastepuje przesuniecie znaków wzorcowych* w rejestrze 8. Znaki pojawiajace sie kolejno w po¬ zycjach wyjsciowych rejestru 17 i 8 sa porówny¬ wane w ukladzie 29.W przypadku braku zgodnosci wszystkich zna¬ ków w lancuchu badanym i wzorcowym i gdy lan¬ cuch badany okaze sie dluzszy niz lancuch wzroco- wy, nastepuje przesuniecie zawartosci odpowied¬ nich pozycji znakowych w rejestrach 8 i 17, przy czym przesuwanie to trwa az do uzyskania na, wyjs¬ ciu 40 sygnalu informujacego o identycznosci lan¬ cuchów w rejstrach 17 i 8. Sygnal z wyjscia 40 wchodzi na uklad sterowania tasma 16 i steruje zródlem danych 18 lub innym urzadzeniem 115 za posrednictwem przelacznika 116. Urzadzenie 115 mo-5 ze byc sygnalizatorem, drukarka, lub innym urza¬ dzeniem.Po tych operacjach rejestr 17 zawiera wyszuka¬ ny lancuch znaków, identyczny z lancuchem prze¬ chowywanym w rejestrze 8. O tym, co nalezy zro¬ bic z wyszukanymi w ten sposób danymi, decyduje operator. I tak np. dane z rejestru 17 moga stano¬ wic adres zwiazany z danymi przechowywanymi w nosniku tasmowym 18, którymi to danymi jest wlas¬ nie zainteresowany operator.W innym przykladzie wykonania urzadzenie we¬ dlug wynalazku nacisniecie klawiczy ESC i K dale¬ kopisu 1 powoduje wykonanie operacji kasowania i zapamietania, a wybranie klawiszy ESC i L-wyko- nanie operacji wyszukania.Jezeli operator nacisnie klawisz ESC, a nastepnie klawisz K na klawiaturze dalekopisu, spowoduje to skasowanie zadanego lancucha znaków wzorcowych i umozliwi zadanie nowego lancucha znaków. Nowy lancuch znaków wzrocowych operator wprowadza nastepnie, z klawiatury. Lancuch ten moze zawierac dowolna kombinacje i6 znaków, wylaczywszy kom¬ binacje klawiszy ESC, K i ESC,L.Po zadaniu lancucha operator naciska kolejno klawisze ESC, L. Nacisniecie klawiszy ESC i L w tej kolejnosci oznacza zakonczenie sekwencji zada¬ wania lancucha znaków" wzorcowych i zainicjowa¬ nie operacji przeszukiwania tasmy.Po odszukaniu zadanego lancucha znaków tasma zatrzymuje sie. Operator moze wykorzystac odszu¬ kana informacje wedlug swego uznania. Lancuch znaków wzorcowych nie jest niszczony po odszuka¬ niu i moze go wykorzystac do nastepnych wyszu¬ kiwan.Zostanie terez przedstawiony zwiezly opis dzia¬ lania ukladu z fig. 1. Dalekopis 1 wytwarza pod wplywem sygnalów przychodzacych z klawiatury znaki ESC i K, np. w kodzie ASCII. Kod ten jest wprawdzie kodem dziesieciobitowym, ale dla uprosz¬ czenia zajmujemy sie tylko siedmioma bitami defi¬ niujacymi sam znak, pomijajac bity start-stopowe i bity parzystosci. Termin „doprowadzenie" lub koncówka stosowane w opisie oznacza polaczenie pojedyncze lub wielokrotne, którym przesyla sie sygnaly proste lub zlozone z wielu elementów skla¬ dowych, jak np. sygnal reprezentujacy znak zlozo¬ ny z kilku bitów przesylanych równolegle.Po wytworzeniu siedmiobitowego kodu reprezen¬ tujacego znak, na koncówce 4 pojawia sie impuls strobujacy. I tak znak zwiazany z klawiszem ESC pojawia sie na koncówce 2, a za nim pojawia sie sygnal strobttjacy na koncówce 4. Podobnie za syg¬ nalem zwiazanym ze znakiem K na koncówce 2 pojawia sie impuls strobujacy na koncówce 4.Po ^wykryciu w dekoderze 5 sygnalów na kon¬ cówkach 2 i 4 wytwarzany jest sygnal na konców¬ ce 6. Sygnal ten — za posrednictwem przerzutnika 9 — powoduje skasowanie zawartosci rejestru zna¬ kowego 8 i rejestru znaczników lancuclia wzorco¬ wego 12. Sygnal pojawiajacy sie na koncówce 6 dziala równiez na przerzutnik 7, umozliwiajac za¬ ladowanie nowego lancucha znaków wzorcowych i sygnalów znacznikowych lancucha wzorcowego do rejestrów 8 i 12.Operator zadaje nowy lancuch znaków wzorco- S 380 6 wych za pomoca klawiatury. W wyniku tego dale¬ kopis wysyla koncówka 2 impulsy reprezentujace znaki wzorcowe, a koncówka 4 impulsy strobujace.Sygnaly te wchodza przez elementy 10 do rejestru 5 znaków lancucha wzorcowego 8. Sygnaly strobuja¬ ce na koncówce 4 i towarzyszace im sygnaly lan¬ cucha wzorcowego na koncówce 2 powoduja zala¬ dowanie sygnalów znacznikowych do rejestru 12 przez elementy wejsciowe 13. io Sygnaly strobujace wchodzace z koncówki 4 do ukladu logicznego start-stopowego 11 taktuja na elemencie I 90 sygnaly lancucha wzorcowego do¬ stepne na koncówce 2 i sygnaly strobujace na kon¬ cówce 4, wprowadzajac jev odpowiednio do rejestru 15 8 i 12. Sygnaly strobujace podawane koncówka .4 do ukladu logicznego start-stopowego 11 przylacza¬ ja równiez przerzutnik kasujacy, zabezpieczajac przed skasowaniem informacji w rejestrach 8 i 12.Nacisniecie znaku L na klawiaturze 3 powoduje 20 wygenerowanie zakodowanej sekwencji do dekode¬ ra 5. Po zdekodowaniu tej sekwencji w ukladzie 5 wytwarzany jest sygnal sterujacy dostarczany kon¬ cówka 15 do jednostki sterujacej 16. Jednostka ste¬ rujaca 16 tasma pod wplywem sygnalu na konców- 25 ce 15 dostarcza sygnal koncówka 19 do ukladu ka¬ sowania 20. Sygnal ten powoduje skasowanie wszyst¬ kich znaków i sygnalów znacznikowych wystepuja¬ cych w rejestrach 17 i 24, zanim rejestrator tasmowy 18 zareaguje na sygnal sterujacy z ukladu sterowa- 30 nia 16 tasma, dostarczajac nowy lancuch znaków badanych i zwiazane z nim sygnaly strobujace po¬ przez koncówki 27 i 28 do elementów wejsciowych 22 i 23.Zawartosc rejestru 17 i 24 jest przesuwana cy- 35 klicznie pod wplywem sygnalów zegarowych C.Sygnal strobujacy na koncówce 28 otwiera element 22, przez który przechodza sygnaly znakowe po-, dawane z rejestratora tasmowego 18 koncówka 27 do rejestru 17. 40 Ponadto sygnaly strobujace podawane koncówka 28 do elementów 23 wprowadzaja sygnaly znacz¬ nikowe do rejestru 24. Sygnaly znacznikowe w re¬ jestrach 24 i 12 sa zwiazane z odpowiednim sygna¬ lem znakowym, przesuwanym cyklicznie w rejes- « trach 17 i 8.Nalezy zauwazyc, ze sygnaly znakowe i znacz¬ nikowe w rejestrach 8 i 12 przesuwane sa w strone pozycji wyjsciowej pod wplywem ukladu logicz¬ nego start-stopowego 11 i oczekuja na tej pozycji 50 na zaladowanie sygnalów znakowych i znaczniko¬ wych do rejestrów 17 i 24.Po przesunieciu pierwszego sygnalu znaczniko¬ wego przez rejestr 24 na pozycje wyjsciowa, jest on wykrywany przez detektor 25 w celu wytwo- 55 rzenia sygnalu na koncówce 39. Sygnal ten pobudza logike start-stopowa 11 dla zainicjowania przesu¬ wania sygnalów znakowych i znacznikowych w re¬ jestrach 8 i 12 synchronicznie z rejestrami 17 i 24.Sygnaly znakowe w rejestrach 17 i 8 porównuje 60 sie w komparatorze znakowym 29 i komparatorze lancuchowym 28 w celu wytworzenia sygnalu na koncówce 41, informujacego o równosci lancuchów znakowych. Sygnal ten stopuje rejestrator tasmo¬ wy 18 za posrednictwem ukladu sterowania 16 65 tasma. %116 380 8 Jezeli lancuch znaków w rejestrze 17 nie jest równy lancuchowi znaków w rejestrze 8, to sygna¬ lizowane jest tó odpowiednimi stanami ukladów 28 i 40 i brakiem sygnalu na koncówce 41, który za¬ trzymalby rejestrator tasmowy 18. Czytanie zna¬ ków z rejestratora 18 do rejestru 17 jest kontynu¬ owane podobnie jak porównywanie tych znaków ze znakami przesuwanymi w rejestrze 8.Jezeli porównywane lancuchy okaza sie równe, wtedy na koncówce 41 wytwarzany jest sygnal za¬ trzymujacy za posrednictwem ukladu sterujacego 16 odczytem rejestratora tasmowego 18. Moze oka¬ zac sie, ze liczba znaków przechowywana w rejes¬ trze 17 jest wieksza niz liczba znaków w rejestrze 8. Taki przypadek jest wykrywany przez uklad 35 i pociaga za soba skasowanie przez uklad 36 pierw¬ szego znaku zapamietanego w rejestrze 17. Porów¬ nywane sa zawartosci rejestrów 17 i 8, przy czym zawartosc rejestru 17 jest przesuwana o jedna pozy¬ cje wzgledem zawartosci rejestru 8. Szybkosc po¬ równywania jest znacznie wieksza od predkosci od¬ czytu, dzieki czemu przed odczytaniem kolejnego znaku z rejestratora mozna wykonac nawet kilka porównan lancuchów.W przykladzie wykonania urzadzenia wedlug wy¬ nalazku szybkosc porównywania, czyli szybkosc przesuwania wynosi 100 000 znaków na sekunde, natomiast szybkosc czytania znaków z rejestratora wynosi tylko 500 znaków na sekunde. Przesuwanie znaków rejestru 17 wzgledem rejestru 8 trwa, az do wykrycia równosci lancuchów. Gdy to nastapi wytwarzany jest sygnal na koncówce 41 powo¬ dujacy zatrzymanie rejestratora 18, czyli zlokalizo¬ wanie na tasmie miejsca odczytania poszukiwanego lancucha.Szczególy prascy rejestrów 17 i 24 i opis ich ope¬ racji wejscia/wyjscia opisane zostaly przez Do¬ nalda S. Lindsay'a w opisie patentowym nr 4012721 z z7.09.1976, opublikowanym 15.03.1977 pt.„Cyfrowy uklad logiczny dla dynamicznych rejes¬ trów buforowych". Szczególy dotyczace formatu da¬ nych, zegarowania, strobowania i Ukladów logicz¬ nych mozna równiez znalezc w opisie patentowym nr 3995252.Obecnie podany zostanie) bardziej szczególowy opis elementów przedstawionych na fig. 1.W przykladzie wykonania urzadzenia wedlug wy¬ nalazku przedstawionym na fig. 1 ograniczniki (ESC, K; ESC, L) i znaki lancucha wzorcowego sa generowane przez dalekopis 1. Znaki te mozna ge¬ nerowac recznie za pomoca klawiatury 3 lub za pomoca innego dalekopisu, procesora lub ze zródla danych. Znaki te mozna odbierac równoleglymi li¬ niami równolegle w sensie bitów i szeregowo w sensie znaków, lub jedna linia 2 szeregowo bit po bfcie, jak pokazano to na fig. 1. Kazdemu znakowi towarzyszy impuls strobujacy znakowy 4, okresla¬ jacy precyzyjnie chwile, gdy znak znajduje sie w linii. Jest to zwiazane z dobrze znana technika prze¬ sylania danych.Po odebraniu linia znakowa 2 sekwencji znaków ESC, K z towarzyszacymi im impulsami strobuja- jacymi na linii strobowej 4, sekwencje te rozpoz¬ naje detektor sekwencji 5„ który generuje sygnal ESCK 6 informujacy o wykryciu takiej sekwencji.Tego rodzaju detektory sa dobrze znane (patrz opis patentowy nr 3934228 Paila J. Morgana z 20.01.1976 pt. „Interfejs równolegly z szybka dru¬ karka"). 5 Sygnal ESCK 6 wlacza przerzutnik 9, który za posrednictwem elementów 10 i 13 i ukladu logicz¬ nego start-stopowego 11 kasuje wszystkie znaki i zwiazane z nimi znaczniki starego lancucha wzor¬ cowego w rejestrze lancucha wzorcowego, 8 i reje- io strze znacznikowym 12. Realizuja to elementy 10 i 13 wprowadzajace sygnaly braku znaków i braku znacz¬ ników na pierwsze pozycje odpowiednio rejestrów 8 i 12, podczas gdy uklad logiczny start-stopowy 11 przesuwa cyklicznie laczna zawartosc obu tych re- 15 jestrów.Sygnal ESCK 6 wlacza równiez przerzutnik 7, co umdzliwia wprowadzenie nowego lancucha zna¬ kowego do rejestru 8.Rejestr znaczników lancucha wzorcowego 12 poz- 20 wala okreslic, czy i gdzie sa znaki w rejestrze lan¬ cucha wzorcowego 8.Jednoczesnie z zaladowaniem pierwszego znaku na pierwsza pozycje rejestru lancucha wzorcowego 8 nastepuje zaladowanie znacznika na pierwsza po- 25 zycje rejestru 12. Proces ten inicjowany jest przez strob na linii 4 i sterowany elementami wejsciowy¬ mi 13 za posrednictwem przerzutnika 7 ladowania.Znacznik ten propaguje na wyjscie pierwszej po¬ zycji rejestru 12, przy czym operacja ta steruje lo- 30 gika start-stopowa 11, podczas propagowania pierw¬ szego znaku w rejestrze 8.Nastepuje podobne do opisanego wyzej doprowa¬ dzenie kolejnych znaków wzorcowych i towarzy¬ szacych im znaczników odpowiednio do rejestrów 8 35 - i 12. Kazdy znak i znacznik przesuwaja sie o jedna pozycje po wprowadzeniu nowego znaku na po¬ zycje wejsciowa. Oznacza to ustawienie znaków w rejestrze 8 w takiej kolejnosci, w jakiej odebrano je z dalekopisu 1. 40 Rejestr lancucha wzorcowego ma o jedna pozy¬ cje wiecej niz wynosi maksymalna dlugosc lancucha wzorcowego. Umozliwia to okreslenie znaku pierw¬ szego i ostatniego lancucha. Oznacza to, ze na po¬ zycji od 1 do N-tej rejestru lancucha wzorcowego 45 8 i rejestru znacznikowego 12 rozpoczyna sie brak znaków lub znaczników w procesie doprowadzania lancucha wzorcowego/ Te puste pozycje w rejes¬ trach 8 i 12 sa najblizej pozycji wyjsciowej w tym punkcie procesu. - 50 Jezeli rejestr lancucha wzorcowego S i zwiazany z nim rejestr znacznikowy 12 zostana zaladowane N znakami, to fakt ten jest sygnalizowany stanem sygnalów na koncówkach 33a i 33b. Stan ten jest wykrywany przez detektor pozycji znakto 14, który 55 wylacza przerzutnik 7, co blokuje dalsze doprowa¬ dzenie znaków.Sekwencja sygnalów ESC, L i zwiazany z nia sygnal strobujacy sa przyjmowane z koncówek 2 i 4, co opisano wyzej dla sekwencji znakowej ESC, 60 K. Sekwencja znaków ESC, L oznaczajaca koniec lancucha znaków wzorcowych wykrywana jest przez dekoder sekwencji 5, który generuje sygnal ESCL 15.Sygnal ESCL 15 zeruje przerzutnik 7 ladowania 65 (jezeli nie zostal dotychczas wyzerowany pod wply-116 380 9 10 wem zapelnienia Rejestru 8 lancucha wzorcowego — co opisano wyzej). Sygnal ESCL 15 oddzialuje rów¬ niez na uklad logiczny start-stopowy 11 w celu przepropagowania lancucha wzorcowego i zwia¬ zanych z nim znaczników do konca rejestrów odpo¬ wiednio 8 i 12, czyli do osiagniecia przez pierwszy znak lancucha wzorcowego wyjscia 31 rejestru, co wykrywane jest przez uklad logiczny start-stopowy 11 na podstawie stanu wyjscia 33 rejestru znacz¬ ników.Sygnal ESCL 15 wysteruje ponadto uklad stero¬ wania tasma 16 w celu skasowania zawartosci re¬ jestru lancucha badanego 17 i uruchomienia reje¬ stratora tasmowego 18. Uklad sterowania tasma 16 dostarcza równiez sygnal X przeszukiwania do ukladu 11, sygnalizujac wykonanie operacji przeszu¬ kiwania. * .Uklad sterowania 16 tasma dostarcza sygnal star¬ tu kasowania 19 na uklad kasujacy 20, który za posrednictwem ukladu logicznego „LUB" 21 prze¬ syla do elementów wejsciowych 22 i 23 sygnaly wy¬ magane do skasowania zawartosci odpowiednio re¬ jestru lancucha badanego 17 i rejestru znaczniko¬ wego lancucha badanego 24. Operacje kasowania zawartosci rejestru lancucha badanego 17 i rejestru znaczników 24 koncza elementy 22 i 23 przesylaja¬ ce sygnaly braku znaków i znaczników na pierwsza pozycje odpowiednich rejestrów, podczas gdy ich zawartosc jest przesuwana cyklicznie pod wplywem sygnalu C.Operacja kasowania jest kontynuowana, az do wykrycia przez detektor 25 faktu, ze rejestry 17 i 24 sa puste i wygenerowania sygnalu „rejestr pusty" 26 w Celu zatrzymania kasowania. Ze wzgle¬ du na duza szybkosc przesuwa*nia znaków operacja kasowania zakonczy sie, zanim rejestrator tasmo¬ wy 18 odczyta znaki z tasmy i wprowadzi je wraz z sygnalami strobujacymi odpowiednio na szerego¬ wa koncówke znakowa 27 i koncówke strobowa 28.Po doczytaniu z tasmy pierwszego znaku lancucha badanego i wprowadzeniu go na szeregowa kon¬ cówke znakowa 27 wraz z impulsem strobujacym na koncówce 28, impuls strobujacy otworzy elemen¬ ty 22 i 23 w celu wprowadzenia znaku i jego strobu na wejscie odpowiednio pierwszej pozycji rejestru lancucha badanego 17 i rejestru znacznikowego 24 lancucha badanego. Szczególy tej operacji mozna znalezc we wspomnianym juz opisie patentowym Donalda S. Lindsay'a.Sygnaly znakowe i zwiazane z nimi sygnaly znacznikowe zaczna natychmiast przesuwac sie w swych odpowiednich rejestrach synchronicznie z sygnalem zegarowym C.Gdy znak i jego znacznik przejda przez M+l po¬ zycji i pojawia sie na ostatnich pozycjach wyjscio¬ wych 34 i 37, sygnal znacznika uruchamia detek¬ tor 25 polozenia znaku, który sygnalizuje na kon¬ cówce 39 fakt pojawienia sie pierwszego znaku badanego w rejestrze wyjsciowym. Pierwszy syg¬ nal na koncówce 39 powoduje, ze uklad logiczny start-stopowy 11 przesuwa cyklicznie lancuch wzor¬ cowy w rejestrze 8 synchronicznie z sygnalem zega¬ rowym C, a wiec synchronicznie ze znakiem bada¬ nym w rejestrze 17. Ten pierwszy sygnal na kon- 10 15 20 25 30 35 40 45 50 55 65 cówce 39 wlacza ponadto przerzutnik porównania lancuchów "28.Podczas, gdy lancuch badany (mowa na razie o jednym znaku) i lancuch wzorcowy przesuwane sai cyklicznie w swych odpowiednich rejestrach wraz ze znacznikami w ich odpowiednich rejestrach, kom¬ parator znakowy 29 porównuje ze soba odpowiada¬ jace sobie znaki z pierwszym znakiem wzorcowym, drugi z drugim, itd.Jezeli któres znaki z porównywanej pary ©ka¬ za sie rózne, komparator 29 generuje sygnal na koncówce R, który gasi przerzutnik 28 porównania lancuchów. Jednoczesnie z operacja porównywania wykonywana przez komparator 29, uklad logiczny 30 sprawdza wyjscia 37a i 33,a rejestru znaczniko¬ wego w celu wykrycia sytuacji, czy istnieje jesz¬ cze jakis znak w lancuchu wzorcowym podczas, gdy brak juz znaku w lancuchu badanym.Jezeli sytuacja taka wystapi, uklad 30 wytwarza sygnal na koncówce R, który równiez gasi przerzut¬ nik 28 porównania lancuchów.Gdy ostatni znak lancucha wzorcowego pojawi sie na wyjsciu 31 swego rejestru, detektor 14 po¬ zycji znaku generuje ostatni sygnal na koncówce 32, tworzony na podstawie wyjsc 33a i 33b rejestru znacznikowego. Ostatni sygnal na koncówce 32 jest wykorzystywany na elemencie I 40 do badania sta- . nu przerzutnika 28 porównania lancuchów. Jezeli przerzutnik 28 jest wlaczony oznacza to, ze porów¬ nywane lancuchy sa tozsamosciowo jednakowe.Wówczas, jezeli okaze sie, ze przerzutnik 28 ba¬ dania lancuchów jest wylaczony, porównywane lan¬ cuchy sa rózne. Podczas synchronicznego przesuwa¬ nia cyklicznego lancuchów w ich rejestrach, lan¬ cuch badany moze byc uzupelniony z rejestratora 18 drugim znakiem, gdy znak pierwszy znajdzie sie na drugiej pozycji od wejscia rejestru 17 lancucha badanego w taki sam sposób, jak przyjety zostal znak pierwszy z rejestratora 18. Równiez z tego wzgledu, ze rejestr wzorcowy 8 jest krótszy od re¬ jestru badanego 17, pierwszy znak wzorcowy po¬ jawi sie na wyjsciu 31 swego rejestru, zanim pierw¬ szy znak badany przepropaguje na wyjscie 34 re¬ jestru.Gdy pierwszy znak lancucha wzorcowego pojawi sie na wyjsciu 31 rejestru lancucha wzorcowego, uklad logiczny start-stopowy 11 wykryje ten fakt na podstawie stanu wyjscia 33a rejestru znaczników wzorcowych i zatrzyma przesuwanie zawartosci re¬ jestru 8 lancucha wzorcowego i rejestru 12 znacz¬ ników wzorcowych. Lancuch wzorcowy oczekuje nastepnie na odebranie znaków lancucha badanego.Cykl opisany wyzej powtarzany jest dla kazdego nastepnego znaku lancucha badanego czytanego z rejestratora tasmowego 18 do rejestru 17 oba lancuchy zostaja porównane po kazdym pelnym przesunieciu cyklicznym rejestrów.Poniewaz operacja odczytu znaków przebiega znacznie wolniej niz operacja przesuwania cyklicz¬ nego rejestru lancucha badanego, porównianie lan¬ cuchów odbywa sie co najmniej po doprowadzeniu nowego znaku do rejestru 17 lancucha badanego z rejestratora tasmowego 18.W miare wykonywania operacji cyklicznego prze¬ suwania obu rejestrów i zwiazanych z nimi reje-11 strów znacznikowych, porównywania znaków i ladowania znaków nowych do rejestru 17, to za¬ kladajac róznosc obu lancuchów, moze sie zdarzyc ze w rejestrze 17 lancucha badanego bedzie wie¬ cej o jeden lub kilka znaków w rejestrze 8 lan¬ cucha wzorcowego. Stan ten wykryje detektor ka¬ sowania 35, badajac wyjscie 37a rejestru znacz¬ ników lancucha badanego i wyjscia 33a rejestru lancucha wzorcowego. Stan ten zostanie wykryty, gdy ostatni znak lancucha badanego znajdzie sie na wyjsciu 34 rejestru, tak wiec operacja kaso¬ wania nie moze byc wykonana natychmiast.Uklad detektora kasowania 35 po stwierdzeniu, ze zapamietany lancuch badany jest dluzszy niz lancuch wzorcowy wlacza przerzutriik oczekiwania na kasowanie 36. Stan oczekiwania na kasowanie trwa od chwili pojawienia sie na wyjsciu 34 pierw¬ szego znaku lancucha badanego. Fakt ten wykrywa detektor pozycji znaku 25, który za posrednictwem ukladu logicznego 38 i elementu LUB 21 wystero- wuje elementy 22 i 23 w celu zablokowania opera¬ cji przesuwania znaku nadmiarowego na pozycje wejsciowa rejestrów 17 i 24.Jezeli przerzutnik 36 nie bylby w stanie „oczeki¬ wanie na kasowanie", uklad logiczny start-stopowy 11 zainicjowalby przesuwanie lancucha wzorcowe¬ go w rejestrze 8 w chwili, gdy pierwszy znak lan¬ cucha badanego pojawilby sie na wyjsciu 34. Ope¬ racja ta jednak jest opózniana do chwili, gdy dru¬ gi znak pojawi sie na wyjsciu 34, przy czym opóz¬ nienie to ma miejsce wlasnie wówczas, gdy prze¬ rzutnik 36 jest w stanie „oczekiwanie na kasowa¬ nie", co oddzialywuje na uklad logiczny start-sto¬ powy 11. Tak wiec nastepuje skasowanie pierwsze¬ go znaku lancucha badanego i przesuniecie wzgle¬ dem siebie obu lancuchów. Oznacza to, ze porówny¬ wany bedzie drugi znak lancucha badanego z pierw¬ szym znakiem wzorcowym, trzeci z drugim itd.Jezeli stan oczekiwania na kasowanie nie bylby ustawiony, wtedy przerzutnik 28 zostalby wla¬ czony w chwili pojawienia sie na wyjsciu 34 pierw¬ szego znaku lancucha badanego, operacje te opóz¬ nia przerzutnik 36 do chwili pojawienia sie dru¬ giego znaku lancucha badanego na wyjsciu 34 reje¬ stru lancucha badanego.Operacja kasowania realizowana przez uklad 38 powoduje ponadto gaszenie przerzutnika 36 ocze¬ kiwania na kasowanie, przygotowujac go do nowe¬ go cyklu kasowaiiia-przesuwania. Tak wiec pod¬ czas trwania cyklu kasowanie-przesuwanie porów¬ nywanie znaków i lancuchów jest kontynuowane.Cykl tych operacji jest kontynuowany do chwi¬ li wykrycia zapalenia sie przerzutnika 28, czyli do chwili, gdy ostatni znak lancucha wzorcowego po¬ jawi sie na wyjsciu 31 rejestru.Po stwierdzeniu tozsamosci obu lancuchów przez uklad logiczny 40, sygnal porównania lancuchów 41 gasi przerzutnik 36 oczekiwania na kasowanie w celu uniemozliwienia skasowania pierwszego zna¬ ku nastepnego lancucha badanego. Sygnal porów¬ nania lancuchów 41 sygnalizuje ukladowi steruja¬ cemu 16, ze lancuchy sa tozsamosciowo jednakowe.Uklad 16 sterowania tasma wymusza na ukladzie logicznym start-stopowym 11 zatrzymanie operacji przesuwania cyklicznego lancucha badanego i lan- 6380 # 12 cucha wzorcowego i zastopowania rejestratora tas¬ mowego 18. Tak wiec operacja przeszukiwania tasmy trwa do chwili zlokalizowania na niej lan¬ cucha znaków identycznego z zadanym w rejestrze 5 8 lancuchem wzorcowym.Szczególy ukladu logicznego start-stopowego 11 przedstawiono na fig. 2. Jezeli tylko to bylo mozli¬ we, zastosowano wspólne oznaczenia cyfrowe. Syg¬ nal wyjsciowy 62 przesuniecia jest wykorzystywa¬ lo ny jedynie przez cykliczne rejestry przesuwajace 8 i 12, jak, przedstawiono to na fig. 1.Gdy sygnal 62 ma wartosc logiczna „0" zawar¬ tosc rejestrów jest przesuwana synchronicznie z ze¬ garem C. Kazdy z sygnalów, sygnal kasowania 43, 15 impulsy ladowania 44 lub 45, które wchodza do ele¬ mentu LUB 42 moze wyzerowac sygnal 62. Tak wiec kazdy sposród tych trzech sygnalów moze spowo¬ dowac przesuniecie zawartosci rejestrów 8 i 12 z fig. 1. 20 Wyjscie 43 przerzutnika kasowania powoduje przesuwanie zawartosci rejestrów, po kazdym wla¬ czeniu przerzutnika, czyli powoduje przesuwanie re- ' jestrów, blokujac jednoczesnfe cykliczne ladowa¬ nie sygnalów znakowych na pozycje wejsciowa re- 25 jestru.Impuls ladowania 44 generuje linia strobowa 4 ustawiona w stanie „1" tylko wówczas, gdy na liniii znakowej 2 jest obecny znak (fig. 1). Jednakze li¬ nia strobowa 4 generuje impuls ladowania 44 tylko 30 wówczas, gdy przerzutnik ladowania zostanie zapa¬ lony, co wykrywane jest na jego wyjsciu 46. Tak wiec sygnal z wyjscia 46 przerzutnika ladowania umozliwia za posrednictwem inwerterów 47 i 48 i elementu NIE-LUB 49 wytworzenie przez linie 35 strobowa 4 impulsu ladowania 44. Taka kombina¬ cja sygnalów . umozliwia* przesuwanie znaków i znaczników w odpowiednich 8 i 12 z fig. 1 w mia¬ re ich ladowania z dalekopisu 1 z fig. 1.Uklad bedacy kombinacja przerzutnika 51 i ukla- 40 du opózniajacego 91 powoduje cykliczne i ciagle przesuwanie zawartosci rejestrów 8 i 12 z fig. 1 po uplywie jednej chwili zegarowej od zapalenia przerzutnika 51. Sygnal przeszukiwania o wartosci „0" na koncówce 92, przechodzacy przez element 45 NIE-LUB 50 i sygnalizujacy tryb przeszukiwania, umozliwia wlaczenie przerzutnika 51 przez sygnal ESCL, na 15 "lub sygnal na koncówce 39 (który syg¬ nalizuje obecnosc pierwszego znaku badanego na wyjsciu rejestru 17). 50 Sygnal ESCL na koncówce 15 powoduje przesu¬ niecie lancucha wzorcowego na pozycje gotowosci z pierwszym znakiem lancucha ustawionym na wyjsciu Tejestru. Sygnal ESCL na 15 ma wartosc „1" tylko podczas tego okresu zapoczatkowujacego, 55 nie wplywa wiec na nastepne operacje przesuwa¬ nia.Sygnal pierwszy 39 wykorzystuje sie do inicjo¬ wania przesuwania cyklicznego lancucha wzorco¬ wego, gdy pierwszy lub drugi znak lancucha bada- 50 nego znajduje sie na wyjsciu rejestru.Jezeli nie ma sygnalu oczekiwania na kasowanie na koncówce 55, przerzutnik 51 zostaje zapalony za posrednictwem elementów 56 i 57, gdy pierwszy znak lancucha badanego pojawi sie na wyjsciu swe- 35 go rejestru.•/ 13 Jezeli natomiast istnieje sygnal oczekiwania na kasowanie, wtedy sygnal pierwszy 39 zostaje opóz¬ niony o jedna chwile zegarowa przez uklad opóz¬ niajacy 59, wytwarzajac sygnal aktywny dopiero po pojawieniu sie drugiego znaku lancucha badanego na wyjsciu rejestru. Ten opózniony sygnal przecho¬ dzi przez elementy 57 i 58, wlaczajac przerzutnik 51.Omawiajac role sygnalu pierwszego 39 i sygnalu 55 przerzutnika oczekiwania na kasowanie przy wlaczeniu przerzutnika 51 nalezy podkreslic, ze syg¬ nal przeszukiwania na koncówce 92 wykorzystuje sie do blokowania cyklicznego przesuwania lancu¬ cha wzorcowego po stwierdzeniu tozsamosci porów¬ nywanych lancuchów, co sygnalizowane jest na wyjsciu 41 (fig. 1), dzialajacym poprzez uklad steru¬ jacy 16 (fig. 1) w celu ustawienia sygnalu przeszu¬ kiwania 92 w stanie „1" w celu zasygnalizowania konca przeszukiwania.Przerzutnik 51 jest gaszony sygnalem pochodza¬ cym z wyjscia 33a rejestru znacznikowego lancucha wzorcowego.Sygnal na wyjsciu 38a ma wartosc „1" zawsze, gdy znaki lancucha badanego znajduja sie na wyjs¬ ciu swego rejestru. Uklad rózniczkujacy 60 pracuja¬ cy na przednim zboczu sygnalów generuje impuls, gdy stan wyjscia 33a zmienia sie z „0" na „1". Im¬ puls ten przechodzac przez inwerter 61 zeruje prze¬ rzutnik 51, gdy pierwszy znak lancucha wzorcowego znajduje sie na wyjsciu swego rejestru.Detektor kasowania 35, przerzutnik 36 oczekiwa¬ nia na kasowanie i uklad logiczny z fig. 1 przedsta¬ wiono dokladniej na fig.3. • Detektor kasowania 35 wysterowany jest z wyjs¬ cia 37a rejestru znacznikowego lancucha badanego i wyjscia 33a rejestru znacznikowego lancucha wzorcowego.Gdy wyjscie 37a ma wartosc „1", a wyjscie 33a — „0", co oznacza, ze znak lancucha badanego jest na wyjsciu 34 (fig. 1) i brak znaku lancucha wzor¬ cowego na wyjsciu 31 (fig. 1), detektor 35 wytwarza sygnal 64, który przechodzac przez elementy 65 i 66 wlacza przerzutnik 36 oczekiwania na kasowa¬ nie.Przerzutnik oczekiwania na kasowanie jest gaszo¬ ny sygnalem porównania lancuchów 41 lub sygna¬ lem wyjsciowym elementu I 67. Sygnal porówna¬ nia lancuchów 41 wylacza przerzutnik 36 oczekiwa¬ nia na kasowanie 36, aby nie dopuscic do skasowa¬ nia pierwszego znaku nastepnego lancucha bada¬ nego.Sygnal wyjsciowy 67 elementu I gasi przerzutnik 36 po zakonczeniu oczekiwania na kasowanie.Opóznione wyjscie przerzutnika oczekiwania na kasowanie wykorzystuje sie do wysterowania ukla¬ du logicznego 11 (fig. 1 i 2), jak równiez ukladu logicznego 38. Sygnal wyjsciowy 63 przerzutnika oczekiwania na kasowanie, dzialajac przez element 68 umozliwia skasowanie pierwszego znaku lancu¬ cha badanego przez sygnal na koncówce 39.Sygnal pierwszy na koncówce 39 ma wartosc „1", gdy znak pierwszy znajduje sie w pozycji poprze¬ dzajacej pozycje wyjsciowa rejestru, sygnal ten musi zatem zostac opózniony o jedna chw,ile zega¬ rowa, w celu zadzialania w chwili pojawienia sie znaku pierwszego na wyjsciu tego rejestru. Opóz- L6 380 14 nienie sygnalu pierwszego na koncówce 39 realizu¬ je uklad opózniajacy 64a. Tak wiec- pierwszy znak lancucha badanego jest kasowany sygnalem 67, który wylacza równiez przerzutnik 36 oczekiwania 5 na kasowanie po zakonczeniu kasowania znaku.Na figurach 4^7 przedstawiono szczególowo od¬ powiednio komparator 29, uklad logiczny 30, detek¬ tor 14 pozycji znaku i detektor 25 pozycji znaku z fig. 1. io Sygnal pierwszy 39 wlacza przerzutnik 28, gdy pierwszy znak lancucha badanego znajdzie sie na pozycji wyjsciowej swego rejestru. Aby to nastapi¬ lo, niezbedne jest opóznienie sygnalu pierwszego 39 w ukladzie 95 o jedna chwile zegarowa. Wynika to. 15 z faktu wykrywania pierwszego znaku przez de¬ tektor pozycji znaku 25 w jedna chwile zegarowa przed pojawieniem sie tego znaku na wyjsciu rejes¬ tru, bedacym pozycja poprzedzajaca pozycje wyjs¬ ciowa ze wzgledu na charakter polaczen 37a'i 37b. 20 Przerzutnik ten jest wylaczany przez sygnal na wyjsciu 69 komparatora znakowego lub wyjsciu 70 ukladu 30.Komparator znakowy wytwarza sygnal 69, gdy znak na wyjsciu rejestru lancucha badanego rózni 25 sie od znaku na wyjsciu rejestru lancucha wzorco¬ wego. Znaki te sa przechowywane w rejestrach w postaci siedmiobitowych reprezentacji logicznych.Komparator znakowy porównuje odpowiadajace so¬ bie bity porównywanych znaków. Uklad róznicy 30 symetrycznej 71 wytwarza sygnaly 72 o wartosci „1", gdy porównywane bity sa rózne.Element NIE-LUB 73 wysterowuje sygnal 69 do wartosci „1" za posrednictwem inwertera 74, gdy któres z jej wejsc ma wartosc „1". Tak wiec syg- 35 nal 69 miec bedzie wartosc „1", gdy którakolwiek z par porównywanych bitów jest rózna. Sygnal 69 wykorzystuje sie do zerowania przerzutnika porów¬ nania lancuchów.' Uklad logiczny 30 przedstawiony na fig. 5 porów- 4o nuje wyjscie rejestru znacznikowego lancucha od¬ niesienia z lancuchem badanym. Inwertery 75, 76 i 78 wraz z elementem NIE-LUB 77, polaczone jak pokazano to na fig. 5, wytwarzaja sygnal na kon¬ cówce 70, zawsze, gdy w jednym lub obu rejestrach 45 jest brak znaków. Powoduje to wylaczenie prze¬ rzutnika porównania lancuchów, gdy lancuch bada¬ ny jest krótszy od lancucha wzorcowego.Na fig. 6 przedstawiono szczególowa budowe ukladu 14. Gdy na wyjsciach 33a i 33b ustawi sie 50 stan odpowiednio „0" i „1", co oznacza, ze pierwszy znak lancucha badanego znajduje sie o jedna po-« zycje przed pozycja wyjsciowa, inwertor 99 i ele¬ ment NIE-LUB 100 generuja pierwszy sygnal na koncówce 101. 55 Gdy na wspomnianych wyjsciach ustawi sie stan „1" i „0", co oznacza, ze ostatni ze znaków jest na pozycji wyjsciowej swego rejestru, inwerter 102 i element NIE-LUB 103 generuja ostatni sygnal na koncówce 32. 60 Na figurze 7 przedstawiono budowe detektora znakowego 25. Sygnal pustosci rejestru na konców¬ ce 26 uruchamia kasowanie 20 w celu zablokowania kasowania, gdy na wyjsciu 24 rejestru nie wykryto znaku przez czas dluzszy niz okres pelnego przesu- 65 niecia cyklicznego danych rejestru 17.116 380 15 16 W przykladzie wykonania urzadzenia wedlug wynalazku, w którym szybkosc przesuwania wynosi 100 000 znaków na sekunde, a pojemnosc pamieci wynosi 127 znaków, czas ten wynosi 2—4 milise¬ kund. Sygnal ten generowany jest w nastepujacy sposób. Licznik 104 zlicza impulsy zegarowe C w ce¬ lu wytworzenia w ukladzie logiki okresowej 1 im¬ pulsu wyjsciowego o dlugosci 10 mikrosekund, pow¬ tarzanego co 2 milisekundy. Ten impus okresowy wlacza przerzutnik 105, który pozostaje w tym sta¬ nie az do pojawienia sie nowego impulsu, zaklada¬ jac, ze rejestr jest pusty. Nastepny impuls 2 msek. wytwarza na wyjsciu elementu LUB-NIE 106 syg¬ nal „1" po negacji w 107. Oznacza to, ze rejestr jest pusty.Jezeli rejestr nie jest pusty, wtedy sygnal „1" wy¬ zeruje 105 i wytworzy stan „0" na wyjsciu elemen¬ tu NIE-LUB 106 po zanegowaniu go na 108.Jak powiedziano poprzednio przy omawianiu de¬ tektora 14, na wyjsciu elementu NIE-LUB 109 wy¬ twarzany jest sygnal „1", gdy znak pierwszy znaj¬ dzie sie jedna pozycje przed pozycja wyjsciowa re¬ jestru.Jezeli przerzutnik oczekiwania na kasowanie jest zgaszony, wtedy na wyjsciu elementu LUB-NIE 109 pojawia sie stan „1" oznaczajacy, ze pierwszy znak, który ma zostac porównywany, pojawi sie na wyjsciu swego rejestru po uplywie jednej chwili zegarawej.Jezeli przerzutnik oczekiwania na kasowanie jest zapalony, wtedy sygnal „1" na koncówce 109 zostaje opózniony o jedna chwile zegarowa w 110 tak, ze jego pojawienie sie na wyjsciu elementu 109 ozna¬ cza, ze pierwszy znak, który ma zostac porównywa¬ ny (znakiem tym jest obecnie drugi znak lancucha) pojawi sie na wyjsciu swego rejestru po uplywie jednej chwili zegarowej.Gdy przerzutnik oczekiwania na kasowanie jest zgaszony, element NIE-LUB 111 jest zamkniety, gdy jest wlaczony — zamknitey jest element NIE- -LUB 112.Cykliczne rejestry przesuwajace powinny byc zrealizowane w technice dynamicznych ukladów pamieciowych, jak np. linii opózniajacych, rejestrów przesuwajacych itd.Wprawdzie opisano tu przyklad wykonania urza¬ dzenia wedlug wynalazku, to mozliwe jest wykona¬ nie W nim szeregu zmian i modyfikacji nie odbiega¬ jacych od istoty i zakresu tego wynalazku, który to zakres wynika z zalaczonych zastrzezen.Zastrzezenia patentowe 1. Urzadzenie do przetwarzania danych, znamien¬ ne tym, ze zawiera pierwszy cykliczny rejestr prze¬ suwajacy do przechowywania badanego lancucha uporzadkowanych znaków o dlugosci równej co najwyzej M, przechowywanych na M+l pozycjach rejestru, gdzie M jest liczba calkowita równa co najmniej 3, drugi cykliczny rejestr przesuwajacy wykonujacy operacje przesuwania pod wplywem rozkazu zapamietania wzorcowego lancucha zna¬ ków uporzadkowanych o dlugosci co najwyzej N znaków przechowywanych na N+l pozycjach rejes¬ tru, gdzie N jest liczba calkowita równa co naj¬ mniej 1, a M-N jest równe co najmniej 2, elemen¬ ty do porównywania badanego lancucha znaków przechowywanych w rejestrze pierwszym z lancu¬ chem znaków przechowywanych w rejestrze dru- 5 gim dla stwierdzenia tozsamosci przechowywanych lancuchów znaków, przy czym elementy te zawie¬ raja elementy do szeregowego porównywania ostat^ nio wymienionych znaków przesuwanych cyklicznie dla wytworzenia sygnalu pierwszego, sygnalizuja- io cego równosc lub róznosc lancuchów, elementy wy¬ krywajace fakt, ze liczba znaków przesuwanego cy¬ klicznie lancucha badanego jest wieksza od liczby znaków przesuwanego cyklicznie lancucha znaków wzorcowych dla wytworzenia sygnalu drugiego, 15 elementy drugie, które na podstawie sygnalu dru¬ giego i sygnalu pierwszego sygnalizuja, ze przecho¬ wywane lancuchy znakowe sa rózne, przy czym sygnalizacja ta mana celu zastopowanie przesuwa¬ nia cyklicznego na czas wystarczajacy do przesunie- 20 cia wzglednego polozenia znaku badanego i wzor¬ cowego na pozycjach ich odpowiednich rejestrów o calkowita liczbe pozycji wieksza od zera, przy czym elementy pierwsze, elementy drugie, elemen¬ ty do porównywania i elementy wykrywajace dzia- 25 laja powtarzalnie az do chwili wytworzenia pierw¬ szego sygnalu wyjsciowego, sygnalizujacego rów¬ nosc porównywanych lancuchów i elementy wyko¬ rzystujace wymieniony ostatnio sygnal wyjsciowy. 2. Urzadzenie wedlug zasttz. 1, znamienne tym, ze 30 zawiera elementy czule na sygnal pierwszy sygnali¬ zujacy nierównosc przechowywanych lancuchów i sygnal drugi dla kasowania pierwszego znaku lancucha badanego przechowywanego w rejestrze pierwszym. 35 3. Urzadzenie wedlug zastrz. 1, znamienne tym, ze zawiera zródlo sygnalów znaków badanych^ ele¬ menty do szeregowego zapamietywania znaków lancucha badanego w rejestrze pierwszym, elemen¬ ty do szeregowego porównywania znaków przesu- 40 wanych cyklicznie w rejestrach dla wytworzenia sygnalu porównania znaków o wartosci nierównej, gdy porównywane znaki sa rózne, przy czym ele¬ menty drugie zawieraja przerzutnik, elementy do ustawiania pod wplywem pierwszego znaku bada- 45 nego lancucha znaków przerzutnika w stanie pier¬ wszym, elementy do ustawiania pod wplywem syg¬ nalów porównania znaków nierównych przerzut¬ nika w stanie drugim, elementy do identyfikacji pod wplywem ostatniego znaku przechowywanego lan- 50 cucha wzorcowego stanu przerzutnika oraz elemen¬ ty sterujace po identyfikacji, ze przerzutnik znaj¬ duje sie w stanie pierwszym, elementami do wpro¬ wadzania znaków badanych ze zródla do pierwsze¬ go rejestru przesuwajacego. • 55 4. Urzadzenie wedlug zastrz. 3, znamienne tym, ze zawiera elementy identyfikacji pierwszego znaku* przechowywanego lancucha znaków badanych, po¬ jawiajacego sie w pozycji wyjsciowej rejestru lan¬ cucha badanego, przy czym elementy te zawieraja 60 rejestr znaczników znaków badanych, elementy do¬ starczajace odpowiedni znacznik badany, zwiazany z kazdym znakiem przechowywanym w rejestrze znaków .badanych, elementy do zapamietywania znaczników badanych w rejestrze znaczników bada- 65 nych, elementy do cyklicznego przesuwania znacz- /17 ników badanych w rejestrze znaczników badanych synchronicznie z cyklicznym przesuwaniem zwiaza¬ nych z nimi znaków badanych przechowywanych w rejestrze lancucha badanego oraz elementy do wykry¬ wania ostatniego znacznika badanego, pojawiaja¬ cego sie w wyjsciowej pozycji rejestru znaczników badanych. 5. Urzadzenie wedlug zastrz. 3, znamienne tym, ze zawiera elementy do wykrywania pojawienia sie pierwszego znaku wzorcowego na wyjsciu rejestru znaków wzorcowych, przy czym elementy te zawie¬ raja rejestr znaczników wzorcowych, elementy do dostarczania odpowiednich znaczników wzorcowych, zwiazanych ze znakami wzorcowymi przechowywa¬ nymi w rejestrze znaków wzorcowych, elementy do zapamietywania znaczników wzorcowych w rejes¬ trze znaczników wzorcowych, elementy do synchro¬ nicznego i cyklicznego przesuwania przechowywa¬ nych znaczników wzorcowych i badanych oraz zna¬ ków badanych i wzorcowych w ich odpowiednich rejestrach oraz elementy do wykrywania pojawie¬ nia sie ostatnieg;o znacznika wzorcowego w pozycji wyjsciowej rejestru znaczników wzorcowych. 6. Urzadzenie wedlug zastrz. 5, znamienne tym, ze zawiera elmenty do szeregowego porównywania znaczników przesuwanych cyklicznie w rejestrach znaczników wzorcowych i badanych dla wytworze¬ nia sygnalu porównania znacznik6w o wartosci nie¬ równej w przypadku, gdy porównywane znaczniki sa równe oraz elementy do ustawiania na podstawie' nierównego sygnalu porównania znaczników prze- rzutnika w drugim stanie. 7. Urzadzenie wedlug zastrz. 1, znamienne tym, ze zawiera elementy do sterowania cyklicznym prze¬ suwaniem znaczników wzorcowych ii znaczników ba¬ danych w ich odpowiednich rejestrach, przy czym elementy te zawieraja elementy do zapoczatkowa¬ nia pod wplywem sygnalu sygnalizujacego pojawie¬ nia sie pierwszego znaku badanego w pozycji wyjs¬ ciowej /: rejestru znaków badanych cyklicznego przesuwania znaków wzorcowych w rejestrze zna¬ ków wzorcowych oraz elementy do realizacji pod wplywem sygnalu sygnalizujacego pelnego cyklu przesuniec cyklicznych przez pierwszy znak wzor¬ cowy w rejestrze znaków wzorcowych i pojawienia sie jego na pozycji wyjsciowej rejestru znaków wzorcowych dla stopowania cyklicznego przesuwa¬ nia znaków wzorcowych w rejestrze znaków wzor¬ cowych. 8. Urzadzenie wedlug zastrz. 7, znamienne tym, ze zawiera zródlo znaków odniesienia, elementy do za¬ pamietywania lancucha znaków wzorcowych o za¬ dawanej dlugosci, przychodzacych ze zródla w re¬ jestrze znaków wzorcowych, przy czym elementy te zawieraja zródlo sygnalów poczatkowych reprezen¬ tujacych poczatek nowego lancucha znaków wzor¬ cowych, zródlo sygnalów koncowych reprezentuja¬ cych koniec nowego lancucha znaków wzorcowych, elementy do kasowania pod wplywem sygnalu po¬ czatkowego wszystkich znaków wzorcowych i zna¬ czników wzorcowych przechowywanych w rejestrze znaków wzorcowych i rejestrze znaczników wzor¬ cowych, elementy do przesuwania pod wplywem sygnalu koncowego nowego lancucha znaków w re¬ jestrze znaków wzorcowych tak, aby znaki te byly L6 380 1* zapamietane we wlasciwym porzadku, przy czym pierwszy znak nowego lancucha pojawia sie na po¬ zycji wyjsciowej rejestru znaków wzorcowych oraz elementy do kasowania pod wplywem sygnalu kón- 5 cowego wszystkich znaków badanych i znaczników badanych przechowywanych odpowiednio w rejes¬ trze znaków badanych i rejestrze znaczników ba¬ danych. 9. Urzadzenie wedlug zastrz. 8, znamienne tym, ze io sygnaly konczace i zapoczatkowujace operacje sa reprezentowane przez odpowiednia sekwencje zna¬ ków, przy czym elementy czule na sygnaly koncza¬ ce i zapoczatkowujace zawieraja elementy dekodo¬ wania sekwencji znakowych zakonczenia i zapo- 15 czatkowania dla dostarczenia sygnalów umozliwia¬ jacych przeszukiwanie dowolnych sekwencji zna¬ kowych róznych od sekwencji sygnalów zakoncze¬ nia i zapoczatkowania. 10. Urzadzenie do przetwarzania danych, znamien- 20 ne tym, ze zawiera pamiec pierwsza do przecho¬ wywania M znaków badanych w M+l komórkach pamieciowych, gdzie M jest liczba calkowtia równa co najmniej 3, drugi cykliczny pamieciowy rejestr przesuwajacy do przechowywania N znaków wzor- 25 cowych w N+l komórkach pamieciowych, gdzie N jest liczba calkowita równa co najmniej 1, a M-N jest równe co najmniej 3, przy czym kazdy znak reprezentowany jest przez grupe impulsów, ele¬ menty dostarczajace odpowiednie znaczniki zwiaza- 30 ne ze znakami wzorcowymi przechowywanymi w pa¬ mieci wzorcowej, elementy dostarczajace znaczni¬ ki badane, zwiazane z odpowiednimi znakami ba¬ danymi przechowywanymi w pamieci badanej, pa¬ miec trzecia do przechowywania N znaczników ba- 35 danych, pamiec czwarta do przechowywania N znaczników wzorcowych, elementy przesuwajace cy¬ klicznie znaki badane, znaczniki badane, znaki wzorcowe i znaczniki wzorcowe w ich odpowiednich pamieciach synchronicznie wedlug porzadku ich 40 przyjmowania, elementy do rozpoczecia przesuwania pod wplywem odpowiedniego znacznika badanego cyklicznych zawartosci rejestoi drugiego i czwartego, • elementy do przerywania przesuwania pod wplywem odpowiedniego znacznika wzorcowego cyklicznych 45 zawartosci rejestrów drugiego i czwartego, elementy zwykle nieczynne do porównywania znaku po znaku znaków badanych ze wzorcowymi znakami dla dos¬ tarczania sygnalów wyjsciowych sygnalizujacych równosc porównywanych znaków, elementy do wla- 50 czenia pod wplywem okreslonych znaczników bada¬ nych ostatnio wymienionych elementów inicjuja¬ cych porównywanie znaków badanych ze znakami wzorcowymi oraz elementy do dostarczania pod wplywem pierwszych sygnalów wyjsciowych dru- 55 giego sygnalu wyjsciowego sygnalizujacego równosc porównanych lancuchów znaków badanych i wzor¬ cowych oraz elementy do sygnalizacji pod wply¬ wem drugiego sygnalu wyjsciowego równosci po¬ równanych lancuchów dla wykorzystania wyszuka-- 60 nego lancucha znaków badanych. 11. Urzadzenie wedlug zastrz. 10, znamienne tym, ze zawiera elementy do badania znaczników bada¬ nych i wzorcowych dla dostarczenia trzeciego syg¬ nalu wyjsciowego sygnalizujacego, ze lancuch zna- 65 ków badanych jest dluzszy niz lancuch znaków116 380 19 wzorcowych, elementy do przesuwania pod wply¬ wem drugiego sygnalu wyjsciowego sygnalizujace¬ go nierównosc porównanych lancuchów badanego i wzorcowego, oraz trzeciego sygnalu wyjsciowego wzglednej pozycji znaków przechowywanych w pa¬ mieci pierwszej i drugiej o jedna pozycje znakowa. 12. Urzadzenie do przetwarzania danych, znamien¬ ne tym, ze zawiera rejestr dynamiczny do przecho¬ wywania lancucha znaków badanych przeznaczo¬ nych do przeszukiwania, dynamiczno-statyczny re¬ jestr do przechowywania lancucha znaków wzorco¬ wych o; zadawanej dlugosci, rejestr znaczników wzor¬ cowych do przechowywania lancucha znaczników wzorcowych odpowiadajacych znakom wzorcowym przechowywanym w rejestrze znaków wzorcowych, rejestr znaczników badanych do przechowywania 10 20 lancucha znaczników badanych odpowiadajacych znakom badanym przechowywanym w rejestrze znaków badanych, elementy do inicjowania pod wplywem okreslonych znaczników badanych syn¬ chronicznego przesuwania cyklicznego zawartosci rejestrów i porównywania znaku po znaku lancu¬ chów znaków badanych i wzorcowych, przy czym porównywane sa znaki pojawiajace sie na wyjscio¬ wych pozycjach rejestru znaków badanych i rejes¬ tru znaków wzorcowych, przy czym porównanie to sluzy do wygenerowania sygnalu równosci oraz ele¬ menty do dostarczania sygnalu uzytkowego pod wplywem okreslonych sygnalów znacznikowych przychodzacych z rejestru znaczników wzorcowych i sygnalu równosci wszystkich porównanych zna¬ ków w lancuchu badanym i wzorcowym. *^*7 P—h[S^ ar CTi -C^5* -fit -AqF 2 ów n—r ZF M-bM •tt116 380 FiG.3 33a i 12 33t FIG.6. 14 r rv_ 1/03 L 102 -fy-T^óo K32 MOI & i" 37a 37b f^f Fg^fn t3^ r---- 1/ EBH^ FIG.4 FIG.7 ^*IP=i5rtH=s" ~1 *" tO€ -&- PL PL PL