Politechnika Śląska

Wydział Automatyki, Elektroniki i Informatyki

Instytut Informatyki

Wojciech Mnich

Praca Dyplomowa Magisterska

Temat: Opracowanie programu dydaktycznego z zakresu projektowania liczników o strukturze szeregowo-równoległej

Promotor: Prof. dr hab. inż. Bolesław Pochopień

Gliwice, 2005Spis treści

1. Cel pracy

Celem pracy dyplomowej jest opracowanie programu dydaktycznego, wraz z jego uruchomieniem i przetestowaniem, z zakresu projektowania liczników o strukturze szeregowo-równoległej. Dodatkowo należy opracować instrukcję dla użytkownika.

Na etapie projektowania zostały przyjęte następujące założenia:

• Niezależność programu od systemu operacyjnego

Obecnie użytkownicy komputerów korzystają z wielu różnych systemów operacyjnych, z których dwa najpopularniejsze to MS Windows oraz Linux. Dzięki uniezależnieniu programu od platformy uruchomieniowej znacznie więcej użytkowników może z niego korzystać. Dodatkowo możliwość uruchomienia programu w oknie przeglądarki internetowej, np. poprzez umieszczenie na stronie www, wyeliminuje potrzebę ściągania i instalacji koniecznych plików, co z kolei znacznie ułatwi korzystanie z programu.

• Łatwość obsługi

Przejrzysty interfejs użytkownika i wygodna nawigacja, powinna zachęcić do poznawania tematu nawet najbardziej wymagających czy też niecierpliwych użytkowników. Prosty dostęp do wszystkich funkcji programu, czyli np. brak zagnieżdżonych pozycji menu czy zakładek, zmniejszy potrzebę sięgania do systemu pomocy.

• Teoria i praktyka

Podział programu na dwie części umożliwi początkującym zdobycie niezbędnej wiedzy potrzebnej do zrozumienia kolejnych etapów realizacji licznika w części praktycznej, gdzie zaznajomieni z tematem mogą utrwalić zdobytą wiedzę.

• System pomocy kontekstowej

Uzależnienie treści pomocy od aktualnej sytuacji w jakiej znalazł się użytkownik, pozwoli oszczędzić jego czas potrzebny na wyszukiwanie interesujących go informacji.

• Konkretne informacje

Materiał w części teoretycznej powinien przedstawić tematykę pracy całościowo przy wykorzystaniu zwięzłego zapisu, często ilustrowanego przykładami przy jednoczesnym unikaniu skomplikowanych wzorów, które nieraz można krótko wyrazić słowami. Taki rodzaj przekazu, pozwala szybko opanować kompletną wiedzę.

• Kontrola wizualizacji

Dobrym rozwiązaniem przedstawienia części praktycznej może być kreator z wizualizacją kolejnych etapów syntezy. Należy zapewnić dowolne kontrolowanie przebiegu prezentacji:

- praca krokowa i cykliczna,

- wygodna zmiana opóźnienia pomiędzy krokami w pracy cyklicznej,

- możliwość powtórzenia przebiegu aktualnego lub wcześniejszego etapu.

• Nieograniczona kreatywność

Część praktyczna ma umożliwiać nie tylko utrwalanie wiedzy, lecz także pozwalać na dowolną konfigurację tworzonego licznika. Użytkownik powinien mieć prawo wyboru:

- typu przerzutników składających się na licznik,

- typu wyzwalania przerzutników,

- liczby stopni licznika,

- liczby stanów.

W przypadku, gdy niemożliwa jest realizacja struktury szeregowo-równoległej należy pozwolić na realizację licznika równoległego. Dzięki temu możliwe będzie porównanie zarówno przebiegu syntezy, jak również jej wyniku w postaci funkcji wzbudzeń.

• Minimalna postać wyniku

Aby móc porównać wynik syntezy różnych struktur, konieczne jest podanie funkcji wzbudzeń w postaci minimalnej. Dodatkowo po minimalizacji wyniki końcowe zaprojektowanego licznika będą nadawać się do realizacji układowej.

2. Wybrane zagadnienia teoretyczne

2.1. Metoda syntezy liczników o strukturze szeregowo-równoległej

Zagadnienia dotyczące syntezy liczników realizowanych z zastosowaniem różnych typów przerzutników synchronicznych są prezentowane na łamach wielu książek. Omawiane w nich metody syntezy cechuje duża różnorodność i różny stopień skomplikowania. Przedstawiona w tym rozdziale metoda [1] wyróżnia się spośród innych uniwersalnością przy stosunkowo prostej realizacji.

2.1.1. Cel syntezy

W celu zrealizowania na przerzutnikach synchronicznych licznika o określonej pojemności i kodzie zliczania, należy dla każdego z przerzutników bloku pamięci BP określić funkcje wzbudzeń dla:

- wejść taktujących C,

- wejść informacyjnych I (rys. 2.1).

Rys. 2.1. Schemat blokowy licznika: BP - blok pamięci, WEUK - wejściowy układ kombinacyjny

Synteza licznika sprowadza się więc do znalezienia struktury wejściowego układu kombinacyjnego (WEUK).

W przypadku ogólnym funkcje wzbudzeń przerzutników mają postać:

C = C(x, k₀, k₁, ..., k_R-1, Q₀, Q₁, ..., Q_N-1);

I = I(k₀, k₁, ..., k_R-1, Q₀, Q₁, ..., Q_N-1);

przy czym:

x - sygnał wejścia licznikowego,

k₀, k₁, ..., k_R-1 - sygnały zewnętrzne określające np. kierunek zliczania, pojemność licznika.

Wśród struktur liczników można wyróżnić:

- strukturę szeregową,

- strukturę równoległą,

- strukturę szeregowo-równoległą.

W licznikach szeregowych zmiany stanów wyjść przerzutników następują niesynchronicznie z sygnałem wejściowym. Zmiana stanu określonego stopnia jest wymuszana przez wejście taktujące sygnałem wyjściowym stopnia bezpośrednio go poprzedzającego.

W licznikach równoległych zmiany kolejnych stanów wyjść następują prawie równocześnie w chwilach określonych zmianami na wejściu licznikowym stanowiącym zwarte wszystkie wejścia taktujące przerzutników poszczególnych stopni.

W licznikach szeregowo-równoległych zmiana stanu określonego stopnia jest wymuszana poprzez wejście taktujące sygnałem niekoniecznie uzależnionym od stanu stopnia bezpośrednio go poprzedzającego.

Chcąc porównać powyższe struktury można podzielić wszystkie stopnie licznika na:

- realizowane równolegle: wejście taktujące tego stopnia jest zwarte z wejściem licznikowym,

- realizowane szeregowo: na wejście taktujące tego stopnia podany jest sygnał różny od sygnału z wejścia licznikowego.

Liczba stopni o określonej realizacji wyznacza typ struktury:

- struktura równoległa: wszystkie stopnie realizowane równolegle,

- struktura szeregowa: dokładnie jeden stopień równoległy i co najmniej jeden szeregowy,

- struktura szeregowo-równoległa: co najmniej jeden stopień równoległy i co najmniej jeden szeregowy.

Zarówno z definicji jak i z powyższego porównania wynika, że liczniki szeregowe są szczególnym przypadkiem liczników szeregowo-równoległych, dzięki czemu omawianą metodę można także stosować do syntezy liczników szeregowych.

2.1.2. Realizowalność struktury szeregowo-równoległej

Zakłada się, że w szeregowo-równoległym liczniku:

- co najmniej jeden stopień realizowany jest jako równoległy,

- co najmniej jeden stopień realizowany jest jako szeregowy.

Spośród wszystkich struktur najbardziej optymalną jest struktura szeregowa, w związku z czym należy zmierzać do tego, aby jak najwięcej stopni było realizowanych jako szeregowe. Należy przy tym spełnić dwa warunki:

1. Spośród stopni realizowanych jako szeregowe wyklucza się te, dla których w kolejnych chwilach, wyznaczonych przez sygnał zliczany, występuje chociaż jedna zmiana typu
Q_i = 0 → 1 → 0 lub Q_i = 1 → 0 → 1; stopnie te muszą więc być zrealizowane jako równoległe.

2. Każdemu przejściu licznika do następnego stanu powinna towarzyszyć zmiana stanu na przynajmniej jednym stopniu realizowanym jako równoległy. Wynika to z faktu, że na wejścia taktujące przerzutników należących do stopni szeregowych podawany jest sygnał będący funkcją sygnałów wyjściowych licznika, dlatego ich zmiana jest uzależniona (pośrednio lub bezpośrednio) od zmian na stopniach równoległych.

2.1.3. Określenie funkcji wzbudzeń wejść taktujących

Dla stopni równoległych na wejście taktujące podawany jest sygnał z wejścia licznikowego. Następnie, na podstawie znajomości kolejnych sekwencji cyklu, określa się postać zależności dla stopni szeregowych. W tym celu określa się typ zmiany stanu C, jaki powinien towarzyszyć zmianom Q = 0 → 1 lub Q = 1 → 0, w zależności od sposobu wyzwalania przerzutnika, co zilustrowano w tablicach przedstawionych na rys. 2.2.

Tablica zależności dla sygnału taktującego przerzutników synchronicznych wyzwalanych dodatnim zboczem			Tablica zależności dla sygnału taktującego przerzutników synchronicznych wyzwalanych ujemnym zboczem i przerzutników dwutaktowych
Q	C		Q	C
.	.		.	.
.	.		.	.
.	.		.	.
0	0		0	1
1	1		1	0
.	.		.	.
.	.		.	.
.	.		.	.
1	0		1	1
0	1		0	0
.	.		.	.
.	.		.	.
.	.		.	.

Rys. 2.2. Tablice zależności dla sygnału taktującego przerzutników synchronicznych

2.1.4. Określenie funkcji wzbudzeń wejść informacyjnych

Wykorzystując znajomość przebiegów C oraz znajomość przebiegów czasowych stosowanych przerzutników synchronicznych (rys. 2.3) można określić stany wejść informacyjnych niezbędne do uzyskania zadanego cyklu licznika, co pozwala określić postać wyrażeń dla funkcji wzbudzeń wejść informacyjnych przerzutników stopni szeregowych.

Rys. 2.3. Realizacja zmian w przerzutnikach:

a) wyzwalanych dodatnim zboczem, b) wyzwalanych ujemnym zboczem,

c) dwutaktowych

Określenie funkcji wejść informacyjnych przerzutników stopni równoległych, z uwagi na taktowanie ich sygnałem x, odbywa się bezpośrednio na podstawie tablicy wzbudzeń przerzutników (rys. 2.4).

Q^t	→	Q^t+1	J^t	K^t	D^t	T^t
0 0 1 1		0 1 0 1	0 1 Ø Ø	Ø Ø 1 0	0 1 0 1	0 1 1 0

Rys. 2.4. Tablica wzbudzeń przerzutników synchronicznych

2.2. Minimalizacja wyrażeń logicznych

2.2.1. Pojęcia podstawowe

Elementarny implikant, czyli składnik jedynki - elementarnym implikantem funkcji F jest kombinacja wartości argumentów, dla których wartość funkcji F wynosi 1. W elementarnym implikancie zeru (w odpowiadającej mu kombinacji wartości argumentów) odpowiada zmienna zanegowana, jedynce zmienna prosta.

Elementarny implicent, czyli czynnik zera - elementarnym implicentem funkcji F jest kombinacja wartości argumentów, dla których wartość funkcji F wynosi 0. W elementarnym implicencie zeru (w odpowiadającej mu kombinacji wartości argumentów) odpowiada zmienna prosta, a jedynce zmienna zanegowana.

Stan Ø (stan obojętny) - kombinacja wartości argumentów funkcji, dla których wartość funkcji jest dowolna.

Funkcja, która posiada stany Ø jest funkcją nie w pełni określoną.

Literał - argument lub negacja argumentu.

Implikant - implikantem funkcji F jest funkcja G mająca tę właściwość, że dla wszystkich możliwych kombinacji wartości argumentów, dla których funkcja G przyjmuje wartość "1" funkcja F również przyjmuje wartość "1".

Implikant prosty to taki implikant funkcji F będący iloczynem jej literałów, że usunięcie z jego zapisu dowolnego literału powoduje, że przestaje on być implikantem funkcji F.

Implicent - implicentem funkcji F jest funkcja G mająca tę właściwość, że dla wszystkich możliwych kombinacji wartości argumentów, dla których funkcja G przyjmuje wartość "0" funkcja F również przyjmuje wartość "0".

Implicent prosty to taki implicent funkcji F będący sumą jej literałów, że usunięcie z jego zapisu dowolnego literału powoduje, że przestaje on być implicentem funkcji F.

Postać sumy (alternatywna) funkcji F to suma składników (implikantów) tej funkcji, gdzie składnik jest iloczynem pojedynczych literałów.

Postać iloczynu (koniunkcyjna) funkcji F to iloczyn czynników (implicentów) tej funkcji, gdzie czynnik jest sumą pojedynczych literałów.

Kanoniczna postać sumy funkcji F (nieuproszczona) to suma wszystkich składników "1" funkcji F.

Kanoniczna postać iloczynu funkcji F (nieuproszczona) to iloczyn wszystkich czynników "0" funkcji F.

Postać kanoniczna funkcji przełączającej z reguły nie jest postacią najprostszą ( zawierającą minimalną liczbę symboli operacji i literałów).

Postać skrócona funkcji logicznej charakteryzuje się tym, że wyrażenie literowe opisujące je w porównaniu z kanoniczną postacią iloczynu/sumy zawiera mniej czynników/składników oraz ilość liter w poszczególnych sumach/iloczynach jest zmniejszona i różna. Postać skrócona może, ale nie musi być postacią minimalną.

Postać nieskracalna (nieredundancyjna) - nie można z niej usunąć żadnego literału bez zmiany funkcji.

Postać minimalna - wyrażenie logiczne opisujące funkcję F, które zawiera najmniejszą liczbę literałów i działań logicznych.

Postać skrócona sumy lub iloczynu to postać zawierająca mniej literałów niż postać kanoniczna.

Poszukiwanie postaci minimalnej polega na odpowiednim stosowaniu tzw. reguł sklejania:

lub pochłaniania:

gdzie:

w - wyrażenie logiczne,

a - zmienna.

Wyrażenia podlegające sklejaniu nazywa się sąsiednimi logicznie.

Normalna postać sumy to taka postać sumy, w której nie występują składniki tożsamościowo równe zero.

Normalna postać iloczynu to taka postać iloczynu, w której nie występują czynniki tożsamościowo równe jeden.

2.2.2. Opis zagadnienia minimalizacji

 

Minimalizacja wyrażeń logicznych ma na celu określenie wyrażenia minimalnego, czyli takiego, które zawiera minimalną liczbę literałów i minimalną liczbę operacji z uwzględnieniem pewnej funkcji kosztu, w której literały i operacje logiczne posiadają ściśle określone wagi. Minimalizacja ma swoje znaczenie przy realizacji układów logicznych. Układ zrealizowany w oparciu o minimalną postać wyrażenia zazwyczaj zawiera minimalną liczbę elementów logicznych. Minimalizacja przeprowadzona na określonych zasadach pozwala określić rozwiązanie wolne od hazardu.

 

Stosowanie przekształceń zgodnie z zasadami algebry Boole'a może prowadzić do uproszczenia wyrażenia, lecz sposób ten jest pracochłonny i dlatego rzadko stosowany. Do najbardziej rozpowszechnionych sposobów minimalizacji formalnej należą metody: 

• Metoda siatek Karnaugh'a,

• Metoda Quine'a-McCluskey'a,

• Metoda Kazakowa,

• Metoda tablic niezgodności.

 Umożliwiają one uzyskanie wyrażeń skróconych w postaci normalnej sumy lub iloczynu. W przypadku minimalizacji niewspomaganej komputerowo liczba zmiennych jest ograniczona do ośmiu. Metody te bazują na odpowiednim stosowaniu reguł sklejania.

Metoda Quine'a McCluskey'a operuje zbiorami: elementarnych implikantów i stanów Ø albo elementarnych implicentów i stanów Ø; ma zastosowanie szczególnie wtedy, kiedy liczba elementów zbioru, którym operuje jest mała.

Dla większej liczby zmiennych zwłaszcza dla funkcji słabo określonych stosuje się metodę Kazakowa, lub metodę tablic niezgodności, które operują tylko zbiorami stanów określonych przy poszukiwaniu implikantów prostych.

2.2.3. Metoda siatek Karnaugh'a

Metoda siatek Karnaugh'a jest stosunkowo prostą i intuicyjną metodą ręcznej minimalizacji wyrażeń logicznych. Niestety, jak i dla innych metod ręcznych jej podstawowym ograniczeniem jest maksymalna liczba możliwych do uwzględnienia zmiennych wejściowych. W praktyce nie powinna ona przekraczać ośmiu zmiennych.

Siatka Karnaugh'a stanowi graficzną prezentację funkcji przełączającej. Zawiera ona te same informacje czyli stany argumentów i odpowiadające im wartości funkcji, co tablica zależności. Każdemu wierszowi w tablicy zależności odpowiada jedna kratka w siatce Karnaugh'a.

Oto kolejne kroki minimalizacji funkcji logicznej F metodą siatek Karnaugh'a:

1) Wartości funkcji F wpisujemy do siatki Karnaugh'a:

- '1' odpowiadają elementarnym implikantom,

- '0' odpowiadają elementarnym implicentom,

- stan Ø odpowiada stanom nieokreślonym.

2) Chcąc otrzymać w wyniku minimalizacji funkcji F jej skróconą postać sumy (skróconą postać iloczynu), należy wszystkie kratki jedynkowe (zerowe) pokryć możliwie jak najmniejszą liczbą jak największych grup jedynkowych (zerowych). Reguły tworzenia grup jedynkowych (zerowych):

- grupa może zawierać 2^c kratek sąsiednich logicznie,

- kratki mogą należeć jednocześnie do kilku grup,

- kratki odpowiadające stanom nieokreślonym funkcji mogą wchodzić w skład grup jedynkowych (zerowych), jeżeli zwiększają liczność zawartych w niej kratek.

3) Grupę jedynkową (zerową) opisuje wyrażenie logiczne w postaci iloczynu/sumy literałów odpowiadającym tylko tym argumentom, od których zależy wartość funkcji w rozważanej grupie (czyli tych, które w opisie kratek rozważanej grupy posiadają stałą wartość). Dany argument występuje w postaci prostej, jeżeli na jego pozycji w opisie rozważanej grupy jedynkowej (zerowej) występuje wartość binarna '1' ('0') lub w postaci zanegowanej, jeżeli na jego pozycji występuje wartość binarna '0' ('1').

4) Suma logiczna (iloczyn logiczny) tak utworzonych wyrażeń opisujących grupy jedynkowe (zerowe) daje postać minimalną sumy (iloczynu).

2.2.4. Metoda Kazakowa

Algorytm Kazakowa przeznaczony jest do minimalizacji słabo określonych funkcji wielu zmiennych. Funkcja jest opisywana za pomocą obu postaci kanonicznych - kanonicznej postaci sumy i kanonicznej postaci iloczynu. Algorytm ten można podzielić na dwa etapy.

I etap.

Pierwszy etap polega na poszukiwaniu zbioru implikantów prostych. Szukanie implikantów prostych dla poszczególnych składników polega na generacji kolejno binarnych wyrażeń jednoliterałowych, dwuliterałowych, trzyliterałowych itd., każde wygenerowane wyrażenie sprawdza się czy ono jest implikantem prostym, to znaczy czy nie pochłania żadnego wyrażenia binarnego ze zbioru czynników '0'. Jeżeli dane wyrażenie jest implikantem prostym to sprawdza się pozostałe wyrazy ze zbioru składników '1' czy są pochłaniane (pokryte) przez ten implikant i zaznacza się to, jeżeli tak, to nie szuka się już dla nich oddzielnie implikantów (co dla metody ręcznej nie jest bez znaczenia). Postępowanie powtarza się tak długo dopóki wszystkie wyrazy funkcji (składniki '1') nie zostaną pokryte. W ten sposób znajduje się niepełny zbiór (podzbiór) implikantów prostych. Podzbiór ten zależny jest od kierunku poszukiwań.

II etap.

Suma prostych implikantów danej funkcji nie zawsze jest minimalną postacią sumy. Niektóre proste implikanty są zbędne i można je usunąć.

W celu sprawdzenia, które z prostych implikantów powinny wejść do minimalnej postaci sumy należy zestawić tzw. tablicę implikantów (tablicę pokrycia). Wiersze tej tablicy odpowiadają znalezionym w pierwszym etapie implikantom prostym, kolumny odpowiadają składnikom jedynki danej funkcji. Wypełnienie tabeli polega na tym, że jeżeli dany implikant pokrywa dany składnik jedynki, to zaznaczamy to na przecięciu kolumny odpowiadającej składnikowi oraz wiersza odpowiadającego implikantowi np. znakiem 'x'. Prosty implikant (wiersz) pokrywa składnik jedynki (kolumnę), jeżeli wszystkie litery z jakich się składa implikant, występują w składniku w tej samej postaci, tzn. zanegowanej lub nie zanegowanej. Następnie analizujemy kolumny tabeli. Jeżeli w jakiejś kolumnie znajduje się tylko jeden znak pokrycia, to odpowiadający temu znakowi prosty implikant jest implikantem niezbędnym i powinien obowiązkowo wejść do końcowego wyrażenia minimalnej postaci sumy. Wszystkie takie implikanty zaznaczamy (np. stawiając z lewej strony tablicy gwiazdki). Zaznaczamy również te kolumny, które są pokryte przez wybrany implikant prosty. Dalsze proste implikanty wybieramy w ten sposób, aby pokryte zostały przez nie wszystkie pozostałe kolumny tablicy.

W przypadku, gdy żaden z implikantów prostych nie jest niezbędnym, może istnieć kilka możliwości wyboru różnych implikantów. Są różne metody określania rozwiązania tablicy pokrycia, a wśród nich najpopularniejszą jest metoda Bowman'a-McVey'a.

W metodzie Bowman'a-McVey'a operuje się współczynnikami:

- P - współczynnik obliczany dla każdej kolumny. Jest to liczba wierszy pokrywających tę kolumnę,

- S - współczynnik obliczany dla każdego wiersza. Jest to suma odwrotności współczynników P kolumn pokrywanych przez ten wiersz.

Na początku do rozwiązania włącza się te wiersze, które pokrywają tylko jedną kolumnę (P = 1). Z tablicy pokrycia redukuje się wiersze wprowadzone do rozwiązania i kolumny przez nie pokryte. Po przeprowadzeniu redukcji oblicza się ponownie współczynniki P i S. W sytuacji, kiedy żadna z kolumn nie posiada współczynnika P = 1, poszukuje się pokrycia dla kolumny najtrudniejszej do pokrycia, czyli mającej minimalne P. Dla tej kolumny do pokrycia wybiera się wiersz posiadający maksymalny współczynnik S. Tablica pokrycia jest redukowana o ten wiersz i kolumny przez niego pokryte. Na nowo oblicza się współczynniki P i S. Te operacje powtarza się aż do pokrycia wszystkich kolumn.

W klasycznej metodzie Bowman'a-McVey'a do rozwiązania wybiera się wszystkie wiersze pokrywające kolumny o P = 1, a po wyczerpaniu tych możliwości postępowanie sprowadza się do poszukiwania wierszy o największym współczynniku S (wskaźnik S jest największy dla wiersza związanego z kolumnami, które będą najtrudniejsze do pokrycia przez pozostałe implikanty) dla elementów o najmniejszym P. Wiersz o największym S włącza się do rozwiązania. Modyfikacja tego algorytmu, wprowadzona przez dr Halinę Kamionkę-Mikułę, polega na tym, że w przypadku, gdy żadna z kolumn nie posiada współczynnika P = 1, poszukuje się, jak wyżej, kolumn o minimalnym P [6]. Teraz jednak spośród wierszy pokrywających kolumny o P_min > 0 znajduje się wiersze o minimalnym S. Redukuje się z tablicy pokrycia wiersze posiadające S_min. Po każdej takiej operacji na nowo oblicza się współczynniki S i P i całe postępowanie powtarza się. Ten sposób zapewnia, że otrzymane rozwiązanie będzie nieskracalne i bardziej zbliżone do minimalnego.

3. Opis programu

3.1. Analiza problemu

Początkowa faza projektowania polegała na spełnianiu kolejnych założeń podanych w pierwszym rozdziale pracy. Aby spełnić pierwsze z nich należało wybrać odpowiednie narzędzie programistyczne generujące kod wynikowy niezależny od systemu operacyjnego. Najpopularniejsze języki i wspierające je narzędzia to:

1. C# i MS Visual Studio .NET

Zalety:

- język i pakiet Microsoftu oferują duże możliwości, dzięki czemu pisanie jak i testowanie aplikacji jest bardzo wygodne;

- wykorzystanie gotowych elementów interfejsu użytkownika (UI) nie tylko oszczędza czas spędzony przy jego projektowaniu, ale także powoduje, że program wyglądem i sposobem obsługi nie różni się od innych aplikacji systemu Windows.

Wady:

- niemożliwe umieszczenie programu na stronie www;

- teoretycznie niezależny kod wynikowy jest bezawaryjny w 100% jedynie pod systemem Windows (wciąż trwają prace nad Linuxową wersją frameworka);

- poważne utrudnienia przy projektowaniu niektórych elementów interfejsu graficznego, np. płynna animacja, przezroczystość z użyciem kanału alfa.

2. Java i Eclipse

Zalety:

- kod bajtowy Javy w 100% niezależny od platformy uruchomieniowej;

- Eclipse - jedno z najlepszych (w dodatku darmowych) środowisk programistycznych, oferuje dużą wygodę przy edycji i odpluskwianiu kodu, dodatkowo możliwa jest instalacja odpowiednich wtyczek (np. do UI),

- możliwość umieszczenia na stronie www w postaci apletu Javy

Wady:

- brak wsparcia dla animacji.

3. ActionScript i Macromedia Flash

Zalety:

- kod wynikowy w postaci pliku 'shockwave flash' wyświetlany przez każdą przeglądarkę internetową z zainstalowaną wtyczką Macromedii (kod w 100% niezależny od systemu)

- środowisko dedykowane do tworzenia animacji i prezentacji wektorowych - duże wsparcie przy kreowaniu interaktywnej prezentacji zawierającej zaawansowaną animację (m.in. przyciski, klipy filmowe, kanał alfa)

- grafika wektorowa - bezstratna jakość obrazu przy powiększaniu oraz krótki kod wynikowy

Wady:

- utrudnione zarządzanie większym kodem - stosunkowo liberalna gramatyka języka ActionScript sprawia trudności przy ewentualnym odpluskwianiu kodu źródłowego.

Wyżej wspomniane pierwsze założenie spełniają Java i Flash. Spośród nich ciekawszy wydaje się Flash oferujący wsparcie dla prezentacji multimedialnych, dlatego program został napisany przy użyciu tego narzędzia.

Realizacja kolejnego założenia (łatwość obsługi), sprowadza się do zastosowania jak najmniejszej liczby przycisków, których przeznaczenie nie powinno budzić wątpliwości. W trakcie działania programu nieprzerwanie będą widoczne i aktywne następujące przyciski:

- Teoria - umożliwia przejście do zagadnień teoretycznych,

- Kreator - pozwala na wizualizację przebiegu syntezy dowolnego licznika,

- Pomoc - pokazuje pomoc kontekstową.

Etykiety na przyciskach jasno określają ich przeznaczenie. Wybranie przycisku podświetla go, co ułatwia orientację w programie. Dodatkowo kliknięcie podświetlonego przycisku powoduje zamknięcie wcześniej otwartego okna (np. okna pomocy).

Powyższe zasady znalazły zastosowanie także przy budowie paneli sterujących w części teoretycznej i w kreatorze.

3.2. Specyfikacja wewnętrzna

3.2.1. Budowa aplikacji

Obiekty, którymi manipuluje Flash mogą być różnego typu: grafiką, przyciskiem lub klipem filmowym. Przycisk i klip filmowy mogą zawierać obiekty dowolnego typu. Grafika to reprezentacja graficzna pozostałych typów obiektów, dlatego znajduje się na samym dole hierarchii zawierania wszystkich obiektów. Największe możliwości posiada klip filmowy. Posiada własną listwę czasową, na której można umieścić nieograniczoną liczbę klatek. Przycisk jest rodzajem klipu filmowego z liczbą klatek ograniczoną do trzech - każda z nich zawiera jego obraz w różnych sytuacjach: przed wskazaniem go kursorem myszy, po wskazaniu i po przyciśnięciu. Ponadto przycisk obsługuje inne zdarzenia (np. przyciśnięcie, zwolnienie) niż klip filmowy (np. przejście do kolejnej klatki). Kod programu w języku ActionScript może być przypisany przyciskowi, klipowi oraz klatce kluczowej filmu.

Program będący przedmiotem tej pracy jest filmem Flasha z jedną sceną (Scene 1) zawierającą w kolejnych klatkach inne klipy filmowe. Obok znajduje się główna listwa czasowa animacji. Na główny klip filmowy składają się trzy klatki (czerwoną linią oznaczona jest pierwsza klatka). Obraz każdej klatki jest komponowany w oparciu o 5 warstw. Warstwy umieszczone wyżej przesłaniają warstwy niższe, np. 'kratka' i 'gradient' służą za tło więc są warstwami najniższymi. Klatka kluczowa (oznaczona kropką na listwie czasowej) służy do separacji klatek o różnej zawartości. Na głównej listwie czasowej klatki różnią się zatem tylko na warstwie 'strony':

1. klatka - rozpoczęcie programu, plansza informacyjna, wszystkie przyciski przygaszone,

2. klatka - część teoretyczna, podświetlony przycisk Teoria,

3. klatka - kreator, podświetlony przycisk Kreator.

Przechodzenie między klatkami następuje po wybraniu przycisku, któremu przypisany jest skrypt z akcją zmiany klatki filmu, np.:

on(release){

gotoAndStop(2);

}

Powyższy kod oznacza, że po zwolnieniu (release) przycisku ma nastąpić przejście do drugiej klatki filmu. W programie niektóre przyciski mają kilka funkcji, np. wybranie przycisku Teoria powoduje:

- w 1. klatce przejście do 2. klatki i jego podświetlenie,

- w 2. klatce przejście do 1. klatki i jego zgaszenie.

Przycisk może mieć przypisany tylko jeden skrypt, dlatego aby umożliwić jego wielofunkcjonalność w każdej z trzech klatek kluczowych na warstwie 'strony' zostały umieszczone inne przyciski. Kolejnym powodem dla którego należało tak uczynić była różnica w wyglądzie przycisków: przygaszony i podświetlony.

W części teoretycznej (2. klatka listwy głównej) większą część ekranu zajmuje klip filmowy 'Teoria', którego listwa czasowa jest podobna do listwy głównej. Posiada 8 klatek (7 tematów + 1 wolna) i 3 warstwy. Warstwa 'przyciski+strony' zawiera klatki kluczowe oraz przypisany do nich kod (oznaczony symbolem α).

Analogicznie jest w części praktycznej (3. klatka listwy głównej). Klip 'Kreator' ma tę samą budowę co 'Teoria'. Posiada dodatkową warstwę 'tks+tabele', na której tworzona jest dynamicznie
tablica kolejnych stanów oraz tabele z funkcjami wzbudzeń. Ta warstwa ma tylko jedną klatkę kluczową ponieważ jej zawartość nie może znikać przy przechodzeniu do następnej klatki.

Klip filmowy 'TKS' na swej listwie czasowej nie zawiera żadnych klatek kluczowych - jego zawartość jest w całości tworzona dynamicznie. Do pierwszej klatki filmu jest przypisany skrypt, który jest odpowiedzialny za:

- utworzenie aktywnej tablicy (z przyciskami pozwalającymi zmieniać stany),

- 'zamrożenie' aktywnej tablicy (aby nie można jej było modyfikować w trakcie trwania syntezy),

- sprawdzenie czy występują powtórzenia stanów,

- wypełnienie naturalnym kodem dwójkowym,

- czyszczenie podświetlenia stanów.

Do budowy tablicy kolejnych stanów wykorzystywany jest klip 'Stan', który reprezentuje wartość pojedynczego bitu jednego stanu. Klip posiada dwie warstwy:

- tekst, na której znajduje się dynamiczne pole tekstowe z wartością 0 lub 1;

- tło, którym jest kwadrat w różnym kolorze.

Strzałki miedzy klatkami kluczowymi oznaczają, że Flash sam wygeneruje klatki pośrednie, w tym przypadku kwadrat w odpowiednim nasyceniu koloru. Pierwsza strzałka oznacza zwiększenie nasycenia koloru, druga - zmniejszenie. W następnej klatce po drugiej strzałce jest bezwarunkowe polecenie powrotu do pierwszej strzałki, np. w 15 klatce jest kod:

gotoAndPlay("turkusowy");

który wykonuje skok do wcześniejszej klatki bez przerywania odtwarzania, co daje efekt pulsującego koloru. Jak widać, nie jest konieczne posługiwanie się numerami klatek - do tego celu równie dobrze nadają się etykiety przypisane klatkom (oznaczane czerwoną flagą nad kropką).

3.2.2. Wizualizacja procesu syntezy

Znaczna część klipów filmowych, podobnie jak 'TKS', jest tworzona dynamicznie. Dotyczy to w szczególności klipów odpowiedzialnych za wizualizację kolejnych etapów syntezy. Różnice polegają na użyciu skryptów przypisanych do klatek tych klipów:

- w przypadku 'TKS' - skrypt uruchamiany jest raz, na początku pracy kreatora, wtedy tworzona jest tablica tks,

- skrypty przypisane do klipów etapów uruchamiane są z szybkością odtwarzania filmu, czyli 25 razy na sekundę.

Aby funkcja skryptu mogła być uruchamiana dla każdej klatki filmu (filmu jako całej prezentacji) należy klipowi zawierającemu daną funkcję przypisać następujący skrypt:

onClipEvent(enterFrame){

animuj();

}

Każdy klip obsługujący etap syntezy zawiera funkcję animuj(), w której następują odwołania do lokalnych (w danym skrypcie) lub globalnych (w całym filmie) funkcji i zmiennych. Poniżej zamieszczona została jej wersja dla etapu drugiego, w którym ma najprostszą postać; działanie jej odpowiedników w innych etapach jest analogiczne.

function animuj()

{ // podswietl kolejne stany na wyjściach równoległych

if(_root.kreator.enterFrame && frame < maxframe){

_root.kreator.enterFrame = false;

frame++;

stan = frame % lstanow + 1;

podswietl(stan);

}

else if(_root.kreator.enterFrame && frame >= maxframe){

_root.kreator.enterFrame = false;

podsumowanie_etapu();

}

}

Znaczenie poszczególnych zmiennych jest następujące:

_root.kreator.enterFrame - zmienna boolowska, ustawiana na wartość true przez pilot kontroli przy przejściu do następnego kroku wizualizacji (opisane w dalszej części),

frame - zmienna typu całkowitego, jest równa liczbie kroków (klatek) na danym etapie (na początku każdego etapu jest zerowana),

maxframe - zmienna całkowita, służy do przechowywania maksymalnej liczby kroków wizualizacji na danym etapie, np. przy sprawdzaniu warunku 2 jest równa liczbie stanów w cyklu licznika, ponieważ weryfikowane są kolejno wszystkie przejścia jednocześnie dla wszystkich stopni równoległych,

lstanow - liczba stanów cyklu licznika.

Podczas całej wizualizacji danego etapu wykonywana jest tylko pierwsza część warunku. Druga część, wykonywana jest po zakończeniu etapu i wyświetla komunikat podsumowujący. Obie części są blokowane do momentu wygenerowania kolejnego kroku przez pilot. Wskaźnik opóźnienia jest częścią pilota umieszczoną nad suwakiem, informującą o czasie pozostałym do wygenerowania kolejnego kroku. Klipowi reprezentującym wskaźnik został przypisany następujący skrypt:

onClipEvent(enterFrame){

x1=10; //min x polozenia wajchy

x2=63.001; // max x pol wajchy

x0=_parent.wajcha._x; // polozenie wajchy <10;63>

_root.kreator.rate = 25 * Math.pow( (2.0*(x2-x0))/(x2-x1), 3 );

_root.kreator.fr += _root.kreator.fr_step;

frame = Math.round((200 * _root.kreator.fr)/_root.kreator.rate);

frame = frame * _root.kreator.fr_step + 1;

if(frame>200){

_root.kreator.fr=0;

_root.kreator.enterFrame=true; //zezwol na klatke prezentacji

}

gotoAndStop(frame); // pokaż aktualne zapełnienie wskaźnika

}

Na początku działania kreatora zmienne, z których korzysta pilot zostały zainicjalizowane następująco:

_root.kreator.fr = 1;

_root.kreator.rate = 0;

_root.kreator.fr_step = 0;

_root.kreator.enterFrame = false;

gdzie:

_root.kreator.fr - zmienna służąca do wyznaczenia klatki klipu wskaźnika (fr=200 gdy wskaźnik cały wypełniony kolorem zielonym)

_root.kreator.rate - służy do obliczania prędkości wizualizacji na podstawie położenia suwaka,

_root.kreator.fr_step - zatrzymuje (0) lub uruchamia (1) tryb pracy cyklicznej, wartość tej zmiennej jest ustawiana po naciśnięciu przycisku pracy cyklicznej.

_root.kreator.enterFrame - zezwala na przejście do kolejnego kroku, jej wartość jest ustawiana na true przez wskaźnik pilota (po wypełnieniu) lub po naciśnięciu przycisku pracy krokowej; po wykonaniu wizualizacji kroku należy ustawić jej wartość na false.

3.2.3. Generowanie kombinacji

W pierwszym etapie syntezy może zdarzyć się sytuacja, że wszystkie stopnie mogą być realizowane jako szeregowe, dlatego należy spośród wszystkich wybrać co najmniej dwa do realizacji równoległej. Nie można wybrać tylko jednego stopnia, ponieważ sygnał na wyjściu stopnie zmienia się zbyt wolno by spełnić warunek 2, w przeciwnym razie dany stopień zostałby wybrany do realizacji równoległej. Jeśli brak jest dwóch stopni spełniających warunek, wybierane są trzy, itd. Kolejne zestawy z dwoma stopniami są kombinacjami 2-elementowymi, podobnie z trzema i więcej. Dlatego konieczne było opracowanie algorytmu generującego kolejne kombinacje począwszy od dwuelementowych.

Aby powstał algorytm należy określić dane na jego wejściu oraz wynik jego działania na wyjściu. Przykładowe dane dla zbioru 4-elementowego zostały przedstawione w tabeli. Dla uproszczenia zakłada się, że na początku generowane są kombinacje jednoelementowe.

Dane wejściowe	Wynik działania
Numer kombinacji	Elementy w kombinacji				Tablica z indeksami elementów w kombinacji
x	0	1	2	3
0	o				0
1		o			1
2			o		2
3				o	3
4	o	o			0,1
5	o		o		0,2
6	o			o	0,3
7		o	o		1,2
8		o		o	1,3
9			o	o	2,3
10	o	o	o		0,1,2
11	o	o		o	0,1,3
12	o		o	o	0,2,3
13		o	o	o	1,2,3
14	o	o	o	o	1,2,3,4

Liczba wszystkich kombinacji dla zbioru 4-elementowego jest równa:

Generowanie kombinacji o określonej liczbie elementów jest proste, gdyż sprowadza się do zagnieżdżonych iteracji, np. funkcja wypisująca zadaną argumentem kombinację 2-elementową zbioru 4-elementowego ma postać:

function komb2(x)

{

int nr=0; // numer iteracji

boolean znaleziono=false; // czy znaleziono x-ta kombinacje

for(i=0; i<3; i++){

for(j=i+1; j<4; j++, nr++){

if(nr==x){

znaleziono=true;

println("%d,",j);

break;

}

}

if(znaleziono){

printf("%d",i);

break;

}

}

return znaleziono;

}

Przykład działania tej funkcji zamieszczono w tabeli

Dane wejściowe	Wynik działania
Numer kombinacji	Elementy w kombinacji				Wartość zwrócona	Indeksy el. w kombinacji
x	0	1	2	3	komb2(x)	Wyjście standardowe
0	o	o			true	1,0
1	o		o		true	2,0
2	o			o	true	3,0
3		o	o		true	2,1
4		o		o	true	3,1
5			o	o	true	3,2
6	-	-	-	-	false

Analogicznie zbudowane są funkcje generujące kombinacje 3-, 4- i n-elementowe. Aby nie ograniczać się do stałej wielkości zbioru, można wprowadzić w tym celu drugi parametr. Pozostaje jednak problem generowania wszystkich kombinacji. Oczywiście istnieje możliwość użycia n funkcji dla n-elementowego zbioru, ale jest to rozwiązanie nieefektywne i nieeleganckie szczególnie dla zbiorów wieloelementowych.

Dużo lepsze rozwiązanie polega na wykorzystaniu rekurencji przy tworzeniu kolejnych zagnieżdżonych iteracji. Poniżej zamieszczona jest funkcja poszukująca xx-tej kombinacji z-elementowej:

function next_iter(i0, z, xx)

{

var ll = z-1;

var i = 0;

for(i=i0; i < lwyjsc - ll; i++){

if(ll == 0){

x++;

}

else{

next_iter(i+1, ll, xx);

}

if(x == xx){

stopnie[ll] = i;

return true;

}

}

}

Do przeszukiwania wszystkich kombinacji służy funkcja:

function znajdz_kombinacje(xx)

{

x = -1;

for(l=1; l<=lwyjsc; l++){// l - liczba elementów w kombinacji

if(next_iter(0, l, xx)){

return l;

}

}

return 0; // nie zostala znaleziona

}

X jest zmienną globalną (brak deklaracji 'var' oznaczającej zmienną lokalną) po to, by każda funkcja wywoływana rekurencyjnie 'orientowała się' czy znaleziono kombinację. W funkcji komb2() podobną rolę pełniła zmienna 'znaleziono'. Oto znaczenie kolejnych parametrów funkcji next_iter():

i0 - pierwszy indeks tworzonej iteracji; dla pierwszej: 0, dla drugiej: 1, dla trzeciej: 2,...

z - liczba elementów w kombinacji;

xx - numer poszukiwanej kombinacji.

3.2.4. Minimalizacja funkcji logicznej

Do minimalizacji wyrażeń logicznych została wykorzystana metoda Kazakowa (szukanie implikantów prostych) oraz zmodyfikowana metoda Bowman'a-McVey'a (redukcja tablicy pokrycia). Funkcja minimalizuj() składa się z dwóch części, odpowiednio dla pierwszego i drugiego etapu syntezy. Działanie funkcji sprowadza się do wypełnienia tablicy implikanty_bp[] implikantami prostymi. Do zakodowania implikantów posłużono się systemem trójkowym, ponieważ każdy argument może mieć jedną z trzech wartości: '0' - występuje w postaci zanegowanej, '1' - występuje w postaci prostej, '-' - nie występuje, np. implikantowi '-1-0' odpowiada w systemie trójkowym 2120₃ = 2*27 + 1*9 + 2*3 + 0*1 = 54 + 9 + 6 = 69. Natomiast elementarne implikanty (składniki jedynki) występują w systemie dwójkowym. Liczby w obu systemach są porównywane ze sobą w funkcji pokrywa(x,y), która sprawdza czy implikant x pokrywa składnik jedynki y.

// czy x pokrywa y? np. dla x=121 i y=101 ->true, a dla x=102, y=111 -> false

function pokrywa(x, y)

{ // x jest w systemie trojkowym, y jest w dwojkowym

if(x==0 && y!=0){

return false;

}

while(x>0){

a = x%3; b = y%2;

if(a!=2 && a!=b){ // porownaj najmlodsze cyfry

return false;

}

x = Math.floor(x/3); // przesun w prawo obie liczby

y = Math.floor(y/2);

}

if(y>0){

return false; // nie pokrywa bo x=0 a y>0

}

else{

return true;

}

}

W pierwszym etapie zastosowano modyfikację metody Kazakowa polegającą na tym, że jeżeli dane wyrażenie jest implikantem prostym to nie sprawdza się pozostałych składników jedynki czy są pochłaniane przez ten implikant, tylko szuka się dla nich oddzielnie implikantów. Zmiana ta wynikła z ograniczeń narzuconych przez język ActionScript (brak tablic wielowymiarowych).

W tej części funkcja korzysta z następujących zmiennych:

implikanty[] - tablica z implikantami prostymi,

implikanty_bp[] - tablica z nie powtarzającymi się implikantami prostymi,

sk.jedynki[] - tablica z elementarnymi implikantami,

sk.zera[] - tablica z elementarnymi implicentami,

j - indeks w iteracji po wszystkich składnikach jedynki.

k - indeks w iteracji po wszystkich kombinacjach, służących do generacji binarnych wyrażeń jednoliterałowych, dwuliterałowych, itd.,

i - indeks w iteracji po wszystkich elementach kombinacji,

z - indeks w iteracji sprawdzającej pokrycie czynników zera przez utworzony implikant,

lelem - liczba elementów w kombinacji.

function minimalizuj(){

war = Math.round(Math.pow(3, lwyjsc)); // liczba wariancji z powtorzeniami

implikanty = new Array();

implikanty_bp = new Array();

nastepny_imp = false;

if(sk.zera.length==0 && sk.jedynki.length>0){

implikanty_bp.push(war-1);

return;

}

for(j=0; j<sk.jedynki.length; j++){

k=-1;

do{

k++;

lelem = znajdz_kombinacje(k);

imp = war-1; // najwiekszy implikant ( np. 2222)

for(i=0; i<lelem; i++){ // tworzenie implikanta

indeks = stopnie[i];

waga3 = Math.pow(3,indeks);

waga2 = Math.pow(2,indeks);

m = Math.floor(sk.jedynki[j] / waga2); m = m%2; // odczytaj wartosc na najmlodeszej pozycji

imp -= (2-m) * waga3;

}

imp = Math.round(imp);

nastepny_imp = false;

for(z=0; z<sk.zera.length; z++){

if(pokrywa(imp, sk.zera[z])){

nastepny_imp = true; // ten impl. Pokrywa czynnik

break; // zera wiec znajdz nowy

}

}

}while(nastepny_imp)

implikanty.push(imp); // wstaw implikant do tablicy

}

// usun powtorzenia

implikanty.sort(); // po posortowaniu te same implikanty są obok siebie
// dzieki czemu wystarczy jedna iteracja by usunac powt.

imp = -1; // zmienna przechowująca wcześniej dodany implikant

for(i=0; i<implikanty.length; i++){

if(imp != implikanty[i]){

imp = implikanty[i];

implikanty_bp.push(imp);

}

}

Drugi etap składa się z jednej głównej pętli wykonywanej dopóki w tablicy pokrycia istnieją nieskreślone kolumny. Skreślanie odbywa się poprzez przypisanie wartości `-1' elementowi tablicy.

// zredukuj implikanty proste (zmodyfikowana metoda Bowman'a-McVey'a)

jed = new Array(); // tablica z kolumnami

impl = new Array(); // tablica z wierszami

for(i=0; i<sk.jedynki.length; i++)

jed.push(sk.jedynki[i]);

for(i=0; i<implikanty_bp.length; i++)

impl.push(implikanty_bp[i]);

implikanty_bp = new Array(); // wyczysc tabl. z impl. bez powtorzen

skreslone_kol=0; // na poczatku brak skreslonych kolumn

while(1) // petla glowna, wykonywana do momentu w ktorym

// wszystkie kolumny beda skreslone

{

p = new Array(jed.length); // utwórz nową tablicę ze współczynnikami p

// oblicz p

minp = 100;

for(i=0; i<jed.length; i++){ // petla po wszystkich kolumnach, oblicz p

if(jed[i]==-1)

continue; //omin skreslona kolumne

tp=0; // na poczatku brak pokrycia dla tej kolumny

ii=0; // indeks implikanta

for(j=0; j<impl.length; j++){

if(impl[j]==-1)

continue; // omin skreslony wiersz

if(pokrywa(impl[j],jed[i])){

tp++; ii=j;

}

}

if(tp==1){ // p=1, ii - indeks jedynego implikanta pokrywajacego

// skresl wszystkie kolumny pokrywane przez ten wiersz

for(s=0; s<jed.length; s++){

if(jed[s]==-1)

continue; //omin skreslona kolumne

if(pokrywa(impl[ii],jed[s])){

jed[s] = -1; skreslone_kol++;

}

}

implikanty_bp.push(impl[ii]); //dodaj implikant

impl[ii] = -1; // skresl wiersz

}

else{

p[i] = tp; // zapisz wspolczynnik p w tablicy

if(tp < minp)

minp = tp; // zachowaj inform. o najmniejszym p

}

}

if(skreslone_kol==jed.length){

return; // koniec redukcji, bo wszystkie kolumny skreslone

}

// obilcz s

s = new Array(imp.length); // utworz nowa talice ze współczynnikami s

for(j=0; j<impl.length; j++){

if(impl[j]==-1)

continue; // omin skreslony wiersz

ts = 0;

for(i=0; i<jed.length; i++){

if(jed[i]==-1)

continue; // omin skreslona kolumne

ts += 1/p[i];

}

s[j] = ts;

}

// dla kolumny z min p wybierz wiersz z min s

mins=100;

ii=0;

for(i=0; i<jed.length; i++){

if(jed[i]==-1)

continue; // omin skreslona kolumne

if(p[i]==minp){

for(j=0; j<impl.length; j++){

if(impl[j]==-1)

continue; // omin skreslony wiersz

if(pokrywa(impl[j],jed[i])){

if(s[j]<mins){

mins = s[j];

ii = j;

}

}

}

}

}

// skresl wszystkie kolumny pokrywane przez ten wiersz

for(s=0; s<jed.length; s++){

if(jed[s]==-1)

continue; // omin skreslona kolumne

if(pokrywa(impl[ii],jed[s])){

jed[s] = -1; skreslone_kol++;

}

}

implikanty_bp.push(impl[ii]); // dodaj implikant

impl[ii] = -1; // skresl wiersz

if(skreslone_kol==jed.length){

return; // koniec

}

}// koniec while(1)

}// koniec funkcji minimalizuj()

4. Instrukcja użytkownika

Zgodnie z założeniami program został tak zaprojektowany, aby jego obsługa była wygodna oraz intuicyjna. W każdym momencie jest możliwe skorzystanie z pomocy kontekstowej, która w dużej części stanowi podręczną instrukcję obsługi.

4.1. Wymagania programowe i sprzętowe

Do uruchomienia programu potrzebna jest dowolna przeglądarka internetowa z zainstalowaną wtyczką do obsługi animacji Flasha. Część przeglądarek ma już wbudowany odtwarzacz plików swf w dość starej już wersji 5. Natomiast inne w przypadku braku odpowiedniej wtyczki potrafią ją pobrać automatycznie z serwera Macromedii.

Jeżeli w systemie plik z rozszerzeniem .swf nie został dotychczas skojarzony z przeglądarką można postąpić następująco:

- uruchomić przeglądarkę (np. poprzez kliknięcie jej ikonki),

- z menu Plik wybrać opcję Otwórz,

- odszukać plik z rozszerzeniem .swf i zaakceptować jego wybór klikając Otwórz lub OK.

Do poprawnej pracy programu wystarczy komputer z procesorem Pentium MMX.
Chcąc jednak wygodnie korzystać z programu w trybie pełnoekranowym należy zaopatrzyć się w procesor klasy co najmniej Pentium II. Na słabszych komputerach możliwe jest przyspieszenie animacji kosztem zmniejszenia jakości obrazu, w tym celu należy postąpić następująco:

- w trakcie działania programu kliknąć prawym przyciskiem myszy

- w otwartym menu wybrać opcję Quality a potem Medium.

Program jest w całości obsługiwany tylko za pomocą myszy przy wykorzystaniu jedynie jej lewego przycisku. Kliknięcie prawego przycisku myszy powoduje otwarcie menu odtwarzacza plików Flasha - FlashPlayera, za pomocą którego można na przykład dostosować jakość prezentacji lub powiększyć wybrany fragment obrazu.

4.2. Obsługa programu

Po uruchomieniu program wita użytkownika planszą informacyjną, zawierającą m.in. temat pracy dyplomowej. U góry ekranu znajduje się główny panel z trzema przyciskami pozwalającymi w każdej chwili na:

- przejście do części teoretycznej,

- przejście do kreatora liczników,

- skorzystanie z pomocy kontekstowej.

Wybór dowolnej opcji sygnalizowany jest podświetleniem klikniętego przycisku.

4.2.1. Poznawanie zagadnień teoretycznych

W części teoretycznej na ekranie oprócz panelu głównego znajdują się:

- panel z tematami - zestaw przycisków służących do poruszania się po najważniejszych zagadnieniach teoretycznych,

- obszar roboczy - okno, w którym prezentowany jest wybrany temat.

Cały materiał został podzielony na siedem części:

- cel syntezy - wstęp teoretyczny oraz schemat blokowy licznika

- struktury liczników - krótka charakterystyka trzech struktur liczników wraz z przykładami ich realizacji

- blok pamięci - wykresy wraz z prezentacją różnych sposobów wyzwalania przerzutników

- tablica wzbudzeń - osobne zakładki z tablicami wzbudzeń dla przerzutników JK, D i T; dodatkowo dołączone zostały działające modele przerzutników,

- założenia - opis założeń do realizacji struktury szeregowo-równoległej

- warunek 1 - pierwszy warunek realizowalności wraz z przykładami

- warunek 2 - drugi warunek realizowalności oraz prezentacje dotyczące spełnienia i niespełnienia warunku.

4.2.2. Tworzenie liczników za pomocą kreatora

W trakcie pracy kreatora niezależnie od realizowanego etapu syntezy na ekranie znajdują się następujące elementy:

- panel z kolejnymi etapami syntezy - zestaw przycisków służących do przechodzenia między etapami począwszy od ustawienia parametrów aż do podsumowania prezentującego wynik syntezy

- tablica kolejnych stanów - tabela z nagłówkiem 'KOD' zawierająca kolejne stany cyklu licznika, których edycja możliwa jest jedynie na etapie ustawiania parametrów licznika

- pilot kontroli wizualizacji - narzędzie pozwalające na ustawienie parametrów wizualizacji tj. praca krokowa lub cykliczna, opóźnienie między kolejnymi krokami w pracy cyklicznej; w razie potrzeby pilot może być przeniesiony w dowolne miejsce na ekranie,

- pasek tytułowy - szczegółowa informacja na temat aktualnego etapu,

- obszar roboczy - zawartość tego obszaru jest zależna od prezentowanego etapu syntezy.

Przed rozpoczęciem syntezy można zmienić następujące parametry licznika:

- liczba wyjść - innymi słowy liczba stopni licznika lub ilość przerzutników;

­- liczba stanów - długość cyklu licznika;

- typ przerzutników - do dyspozycji są trzy najpopularniejsze typy: D, T, JK;

- typ wyzwalania - zboczem narastającym (ET+), opadającym (ET-), dwutaktowe (MS)
(ET - ang. Edge Triggered, MS - ang. Master Slave)

Dodatkowo możliwa jest zmiana dowolnej wartości w tablicy kolejnych stanów poprzez kliknięcie jej myszką. W przypadku gdy nowy stan występuje już w tablicy, oba powtórzenia podświetlone zostają kolorem czerwonym. Rozpoczęcie syntezy możliwe jest dopiero po usunięciu wszystkich powtórzeń. Aby usunąć powtórzenie można postąpić na dwa sposoby:

- kliknąć jedną z wartości podświetlonych na czerwono, taką by uzyskać unikalny stan w cyklu,

- zmienić parametry cyklu (liczba wyjść lub liczba stanów), wtedy cały cykl jest wypełniany naturalnym kodem dwójkowym.

W celu rozpoczęcia syntezy należy wybrać przycisk z etykietą Warunek 1, co spowoduje przejście do pierwszego etapu. Uruchomienie prezentacji następuje po wybraniu za pomocą pilota trybu pracy:

- przycisk włącza tryb pracy cyklicznej, ponowne wciśnięcie tego przycisku zatrzymuje odtwarzanie prezentacji do momentu kolejnego wciśnięcia, po którym następuje kontynuowanie wizualizacji; w trybie tym prędkość odtwarzania jest kontrolowana za pomocą suwaka; wskaźnik znajdujący się powyżej suwaka wskazuje kiedy nastąpi przejście do następnego kroku (po zapełnieniu wskaźnika)

- przycisk umożliwia przejście w dowolnym momencie (także w trybie pracy cyklicznej) do kolejnego kroku syntezy.

Po wyczerpaniu wszystkich kroków zostaje wyświetlona informacja o zakończeniu etapu. Dalej możliwe jest:

- przejście do kolejnego etapu poprzez kliknięcie następnego przycisku (poniżej podświetlonego wskazującego aktualny etap)

- ponowne odtworzenie bieżącego etapu poprzez wybranie aktualnego przycisku,

- odtworzenie któregoś z wcześniejszych etapów lub przejście do modyfikacji parametrów licznika.

Cały przebieg syntezy został podzielony na kilka części:

- ustawianie parametrów licznika,

- spełnienie warunku 1 i sprawdzenie założeń,

- spełnienie warunku 2 realizowalności struktury szeregowo-równoległej,

- określenie funkcji wzbudzeń sygnałów taktujących,

- określenie funkcji wzbudzeń sygnałów informacyjnych,

- minimalizacja funkcji wzbudzeń,

- prezentacja wyników syntezy.

4.2.3. Przebieg syntezy przykładowego licznika.

Etap 1.

Na tym etapie wpierw następuje poszukiwanie na wyjściach kolejnych stopni sekwencji 0→1→0 i 1→0→1, dlatego w każdym kroku analizowane są wartości sygnału w trzech kolejnych stanach. W przypadku znalezienia jednej z nich - zgodnie z warunkiem 1 - dany stopień licznika musi być realizowany jako równoległy. Stopnie przeznaczone do realizacji równoległej są oznaczone kolorem zielonym, a stopnie szeregowe - kolorem czerwonym. Po zakończeniu tej operacji możliwe są - w zależności od wyników poszukiwań - następujące rozwiązania:

1. Gdy istnieje co najmniej jeden stopień szeregowy i co najmniej jeden równoległy, wtedy spełnione są założenia realizowalności struktury szeregowo-równoległej i możliwe jest przejście do kolejnego etapu syntezy.

2. W momencie gdy wszystkie stopnie mogą być realizowane jako szeregowe, następuje wybór spośród nich co najmniej dwóch, które spełnią warunek 2 w kolejnym etapie. W skrajnym przypadku konieczne będzie wybranie wszystkich stopni do realizacji równoległej (3 rozwiązanie)

3. Jeżeli wszystkie stopnie muszą być realizowane równolegle, to założenia nie są spełnione i synteza licznika o strukturze szeregowo-równoległej nie jest możliwa. Istnieje jednak możliwość wizualizacji syntezy licznika równoległego.

Etap 2.

Aby możliwa była realizacja licznika, konieczne jest spełnienie warunku 2, co jest weryfikowane na tym etapie. W kolejnych krokach analizowane są sąsiednie wartości stanów wyjść stopni równoległych. W przypadku braku zmian na co najmniej jednym stopniu następuje przerwanie sprawdzania oraz zakończenie wizualizacji.

Natomiast spełnienie warunku umożliwia przejście do kolejnego etapu.

Etap 3.

W tym miejscu wyznaczane są funkcje wzbudzeń sygnałów taktujących. Wizualizacja tego procesu dotyczy tylko stopni szeregowych, gdyż stopnie równoległe taktowane są sygnałem z wejścia licznika (C=x). Dla każdej zmiany sygnału na wyjściu danego stopnia ustawiane jest zbocze aktywne w sygnale taktującym tego stopnia, czyli 0-1 dla wyzwalania zboczem narastającym (ET+) lub 1-0 dla wyzwalania zboczem opadającym i wyzwalania dwustopniowego (ET- i MS).

Im wolniej zmieniający się sygnał na wyjściu tym więcej wartości nieokreślonych w funkcji wzbudzeń sygnału taktowania, których należy się pozbyć by móc wyznaczyć funkcje dla sygnałów informacyjnych. Eliminacja stanów nieokreślonych polega na znalezieniu takiego sygnału wyjściowego, który jest pokrywany przez sygnał taktujący. Dopasowanie może wystąpić jako pokrycie wprost (wtedy na wejście podawany jest sygnał z wyjścia prostego) lub nie wprost (na wejście podawany jest sygnał z wyjścia zanegowanego). W przypadku braku dopasowania wartości nieokreślone zostają zastąpione zerami.

Aby liczba aktywnych zboczy była jak najmniejsza, co upraszcza funkcje wzbudzeń sygnałów informacyjnych, przeszukiwanie sygnałów wyjściowych następuje począwszy od tych z najmniejszą liczbą zmian.

Etap 4.

Na tym etapie określane są funkcje wzbudzeń sygnałów informacyjnych dla wszystkich stopni. Na podstawie dwóch kolejnych wartości sygnału wyjściowego wyznaczany jest wiersz w tablicy wzbudzeń. Następnie wartość sygnału informacyjnego z tablicy wzbudzeń jest wstawiana do tablicy danego sygnału według zasad opisanych w rozdziale 2.4.

Etap 5.

W ostatnim etapie syntezy przeprowadzana jest minimalizacja funkcji wzbudzeń wszystkich sygnałów (taktujących oraz informacyjnych) metodą siatek Karnaugh'a. W kolejnych krokach odpowiednie wartości sygnału są wstawiane do siatki w miejscu określonym przez stan licznika.

Po wypełnieniu siatki w kolejnych krokach wypisywane są implikanty proste wraz z podświetleniem odpowiednich grup w siatce Karnaugha.

Podsumowanie

Na koniec następuje prezentacja wyników minimalizacji dokonanej w poprzednim etapie. Dla każdego przerzutnika funkcje wzbudzeń zostały zgrupowane w osobnych oknach.

4.2.4. Korzystanie z pomocy kontekstowej

W każdej chwili możliwe jest wyświetlenie pomocy dotyczącej bieżącej sytuacji poprzez wybranie przycisku umieszczonego na panelu głównym. Schowanie okna (lub okien) pomocy następuje po kliknięciu lewym klawiszem myszy w dowolnym miejscu na ekranie.

W części teoretycznej treść pomocy informuje najczęściej o ukrytych (pod niektórymi elementami) informacjach lub o sposobie korzystania z załączonych przykładów.

Podczas pracy z kreatorem informacje zawarte w pomocy wyjaśniają metodę postępowania na aktualnym etapie syntezy licznika. Dodatkowo w trakcie ustawiania parametrów licznika pomoc kontekstowa opisuje elementy towarzyszące podczas całego procesu syntezy (tablica kolejnych stanów, panel z etapami, pilot kontroli wizualizacji).

5. Uruchamianie i testowanie programu

Uruchamianie jest procesem polegającym na lokalizowaniu i usuwaniu błędów znalezionych podczas testowania programu. Natomiast testowanie jest sposobem wykonywania programu w celu wykrycia maksymalnej liczby błędów. Do poprawnego przeprowadzenia tego procesu niezbędne jest przygotowanie odpowiednich danych testowych, pozwalających zweryfikować poprawność działania programu. Aby dobrze przeprowadzić testowanie należy je wykonać podczas działania programu we wszystkich możliwych konfiguracjach. Po usunięciu znalezionych błędów należy przeprowadzić testowanie od początku by sprawdzić, czy w procesie uruchamiania nie powstały nowe błędy. Podczas testowania i uruchamiania oba procesy przebiegają naprzemiennie aż do momentu uzyskania niezawodnego programu.

Flash został zaprojektowany z myślą o tworzeniu grafiki wektorowej i animacji, dlatego język ActionScript używany najczęściej do obsługi interaktywności w filmach nadaje się głównie do krótkich, kilkulinijkowych skryptów realizujących podstawowe akcje. Mimo to Flash zawiera niezbędne narzędzia pomocne podczas uruchamiania i testowania.

Stosunkowo łatwą w obsłudze i uniwersalną jest paleta Movie Explorer, która znacznie ułatwia orientację w rozbudowanym filmie z racji wyświetlania zawartości na różne sposoby i szybkiego nawigowania do wskazanego elementu. Ponadto pozwala przedstawić wybiórczo graficzną reprezentację komponentów filmu i uzyskać informacje o poszczególnych ujęciach, warstwach, jak również fragmentach skryptu przypisanych do przycisków, klipów filmowych i ujęć kluczowych. Wyświetlana zawartość jest ułożona hierarchicznie, dzięki czemu łatwo dostrzec powiązania pomiędzy różnymi elementami filmu.

Chociaż paleta Movie Explorer daje dostęp do większości elementów graficznych filmu oraz fragmentów skryptu, to jednak nie umożliwia wyświetlania zmiennych lub ścieżek dostępu do obiektów. W tym celu używa się okna Output. Często w czasie odtwarzania filmu istnieje potrzeba podglądu wartości przyjmowanych przez zmienne i ścieżek dostępu do klipów filmowych, żeby móc ocenić, czy Flash właściwie manipuluje danymi. Jest to szczególnie ważne w przypadku najbardziej skomplikowanych filmów, zawierających wiele parametrów przekazywanych między funkcjami lub dużą ilość dynamicznie przydzielanych zmiennych. Do wyprowadzania danych do okna Output służy akcja trace, pozwalająca na podgląd wartości wybranych zmiennych a także na śledzenie przebiegu wykonywania programu.

W połączeniu z akcją trace można jeszcze użyć operatora typeof i w efekcie uzyskać informację o typie danych przechowywanych w zmiennej. Informacja tego rodzaju staje się bardzo użyteczna w przypadku problemów z niespodziewanymi wartościami zmiennych.

W części teoretycznej testowanie miało miejsce tylko przy badaniu zgodności modeli przerzutników z tablicą wzbudzeń. Z uwagi na niewielką liczbę możliwych kombinacji (3 typy przerzutników, 3 typy wyzwalania, 3-4 zadawane sygnały) proces testowania i uruchamiania przebiegł szybko i bezproblemowo.

Bez porównania o wiele bardziej skomplikowane i pracochłonne było przeprowadzenie omawianych procesów podczas pracy kreatora. Zadanie to zostało nieco uproszczone poprzez wyeliminowanie możliwości popełnienia błędów przez użytkownika, np. jeżeli w momencie zmniejszania liczby wyjść liczba stopni przekracza dopuszczalną (2^{liczba_wyjść}) zostaje ona ustawiona na wartość maksymalną.

Czas potrzebny na przetestowanie wszystkich możliwości wzrastał wraz z dodawaniem nowego etapu syntezy. Ponadto, aby zweryfikować poprawność nowego etapu, za każdym razem należało przejść poprzez wcześniejsze stadia.

Po pomyślnym przetestowaniu wszystkich etapów pod względem poprawności generowanych wyników, nadszedł czas na optymalizacje całego procesu syntezy tak, by wyniki w postaci funkcji wzbudzeń były minimalne. Jak się okazało, do osiągnięcia tego celu nie wystarczyła minimalizacja przeprowadzona w ostatnim etapie. Już na etapie określania wartości sygnałów taktujących konieczne było podanie minimalnej funkcji wzbudzeń dla tych sygnałów. Zadanie to polega na sprawdzeniu czy jeden z sygnałów wyjściowych pokrywa minimalizowany sygnał taktujący; jeśli tak - wartości nieokreślone w sygnale taktującym są zastępowane wartościami z wyjścia jednego ze stopni; w przeciwnym razie w miejsce wartości nieokreślonych wpisywane są zera, po to by nie występowały dodatkowe (niepotrzebne) zbocza aktywne. Aby dodatkowo zoptymalizować ten proces, przeszukiwanie sygnałów wyjściowych zaczyna się od sygnałów, które zmieniają się najrzadziej. Dzięki temu liczba aktywnych zboczy, dla których należy ustawić sygnał informacyjny (w następnym etapie syntezy) jest możliwie najmniejsza.

Wszystkim zabiegom optymalizacyjnym towarzyszyło testowanie, gdyż wciąż istniało ryzyko pojawienia się nowych błędów.

6. Podsumowanie

Wszystkie przyjęte w trakcie projektowania założenia znalazły swe odzwierciedlenie w programie, dzięki czemu został osiągnięty cel pracy - sprawnie działający program dydaktyczny z zakresu projektowania liczników o strukturze szeregowo-równoległej.

Uniezależnienie programu od systemu operacyjnego przyczynia się do znacznego zwiększenia grona potencjalnych użytkowników. Do poznawania tematu i pogłębiania wiedzy zachęca przejrzysty interfejs użytkownika i wygodna nawigacja, a łatwy dostęp do wszystkich funkcji programu minimalizuje potrzebę sięgania do systemu pomocy.

Największym jednak atutem programu jest możliwość wizualizacji procesu syntezy. Pełna kontrola nad przebiegiem tego procesu oraz jasny podział całego procesu na etapy ułatwia przyswajanie reguł, na których opiera się konstrukcja licznika. Kontrolowanie wizualizacji polega nie tylko na wyborze trybu pracy (cykliczna, krokowa) i opóźnienia prezentacji, ale pozwala na powtórzenie przebiegu dowolnego wcześniejszego lub aktualnego etapu. Możliwość realizacji liczników w oparciu o różne rodzaje przerzutników synchronicznych z dowolnym typem wyzwalania zachęca do prowadzenia eksperymentów.

Kolejnym udogodnieniem jest brak ograniczenia realizacji jedynie do struktury szeregowo-równoległej i szeregowej, która jest jej szczególnym przypadkiem. W momencie gdy wszystkie stopnie muszą być realizowane jako równoległe, możliwa jest także realizacja licznika o strukturze równoległej. Dzięki tej opcji, użytkownik jest w stanie zaobserwować podobieństwa w przebiegu syntezy różnych struktur.

Na zakończenie należy wspomnieć o możliwościach rozwoju programu. Aby prócz walorów dydaktycznych program zyskał także cechy praktyczne, warto by rozwiązać problem syntezy opartej na większej liczbie przerzutników niż cztery. Ograniczenie to zostało przyjęte w celu eliminacji potrzeby przesuwania zawartości całego ekranu, co w przypadku filmów Flasha jest nieco kłopotliwe - możliwe jest tylko po powiększeniu obrazu. Rozwiązanie mogłoby polegać na stworzeniu we Flashu czegoś w rodzaju okien, których zawartość można by przesuwać umieszczonym obok suwakiem. Takie okno zawierałoby wszystkie elementy kreatora, choć lepszym rozwiązaniem byłoby umieszczenie każdej tablicy w osobnym oknie - wtedy automatyczne przewijanie okna odbywałoby się na tych oknach, które tego potrzebują.

Przydatną opcją byłoby przechowywanie w pamięci wyników wszystkich (lub tylko wybranych) wcześniej przeprowadzonych syntez, by przy kolejnych podsumowaniach istniała możliwość porównania otrzymanych wyników z poprzednimi.

W części teoretycznej działające modele przerzutników można wzbogacić o możliwość generowania przebiegów w trakcie zadawania kolejnych stanów. Wykres mógłby wykorzystywać wcześniej opracowane okno, tak by umożliwić analizę początku przebiegu. Czyszczenie okna mogłoby następować automatycznie po zmianie przez użytkownika sygnału wyjściowego lub poprzez wybranie odpowiedniego przycisku.

Program można również rozbudować o trzecią część, która pozwalałaby użytkownikowi na sprawdzenie swojej wiedzy na temat syntezy liczników. Opcja 'Zadania' mogłaby przypominać wyglądem kreator, z tą różnicą że to użytkownik przeprowadzałby syntezę a nie komputer. Rola tego drugiego ograniczałaby się do weryfikacji całego procesu i ewentualnym generowaniu podpowiedzi.

Jak widać, istnieje wiele sposobów na zwiększenie funkcjonalności i atrakcyjności programu, jednak niektóre z nich wykraczają poza dydaktyczny charakter pracy a implementacja wszystkich wymienionych ulepszeń wymaga znacznie więcej czasu.

7. Literatura

1. Pochopień B.: Logiczne projektowanie liczników o dowolnej strukturze opartych na przerzutnikach synchronicznych. Informatyka, Z. 10, Gliwice 1987 r.

2. Kamionka-Mikuła H., Małysiak H., Pochopień B.: Układy cyfrowe. Teoria i przykłady.
WKJS, Gliwice 2003.

3. Traczyk W.: Układy cyfrowe. Podstawy teoretyczne i metody syntezy.
WNT, Warszawa 1982.

4. Chun R.: Po prostu Flash 5. Techniki zaawansowane. Helion, Gliwice 2001.

5. Reinhardt R., Lentz J. W.: Flash 5. Biblia. Helion, Gliwice 2002.

6. Programy dydaktyczne dostępne w witrynie internetowej: http://zmitac.iinf.polsl.gliwice.pl

15

Kolejne klatki listwy głównej

Algorytm

Dane wejściowe

Wynik działania

---