Serwis Edukacyjny w I-LO w Tarnowie Materiały dla uczniów liceum |
Wyjście Spis treści Wstecz Dalej Autor artykułu: mgr Jerzy Wałaszek |
©2024 mgr Jerzy Wałaszek |
SPIS TREŚCI |
|
Podrozdziały |
Zadaniem programu będzie przesunięcie bitów liczby binarnej o 1 w lewo, czyli np. z liczby 1101(2) powinniśmy otrzymać liczbę 11010(2). Operacja taka jest równoważna pomnożeniu wartości liczby przez 2. Cyfry liczby zostaną umieszczone w kolejnych komórkach taśmy. Przed wykonaniem programu głowica ustawi się na ostatniej cyfrze. Na znak pusty wybieramy pytajnik.
Maszyna może znajdować się w jednym z trzech stanów:
Program |
---|
** Przesuwanie bitów liczby binarnej o 1 w lewo ** (C)2004 mgr Jerzy Wałaszek ** I LO w Tarnowie ************************************************ 0,q0,0,q0,L stan początkowy, zapamiętujemy 0 1,q0,0,q1,L stan początkowy, zapamiętujemy 1 0,q1,1,q0,L zapisujemy zapamiętane 1,zapamiętujemy 0 1,q1,1,q1,L zapisujemy zapamiętane 1,zapamiętujemy 1 ?,q0,0,q2,L koniec, zapisujemy zapamiętane 0 ?,q1,1,q2,L koniec, zapisujemy zapamiętane 1 |
Jak to działa? To proste. Maszyna umieszcza w bieżącej komórce taśmy zapamiętane z poprzedniej pozycji cyfry binarne. Cyfry zapamiętywane są w stanie maszyny. Jeśli odczytanym symbolem jest 0, maszyna przechodzi w stan q0 i w następnym ruchu wypisze w sąsiedniej komórce 0. Jeśli odczytany symbol to 1, maszyna przechodzi w stan q1 i w następnym ruchu wypisze 1. W bieżącej komórce zapisuje 0 lub 1 w zależności od swojego bieżącego stanu, przy którym rozpoczęto wykonywanie instrukcji. Jeśli skończą się cyfry, to maszyna zapisuje to, co zapamiętała z poprzedniej komórki i przechodzi w stan końcowy.
Sprawdźmy działanie programu dla danych wejściowych 110101:
Taśma z głowicą |
Odczytany znak |
Stan bieżący |
Wykonywana operacja |
Zapisywany znak |
Nowy stan |
---|---|---|---|---|---|
? ? 1 1 0 1 0 1 ? |
1 | q0 | 1,q0,0,q1,L | 0 | q1 |
? ? 1 1 0 1 0 0 ? |
0 | q1 | 0,q1,1,q0,L | 1 | q0 |
? ? 1 1 0 1 1 0 ?
|
1 | q0 | 1,q0,0,q1,L | 0 | q1 |
? ? 1 1 0 0 1 0 ?
|
0 | q1 | 0,q1,1,q0,L | 1 | q0 |
? ? 1 1 1 0 1 0 ?
|
1 | q0 | 1,q0,0,q1,L | 0 | q1 |
? ? 1 0 1 0 1 0 ?
|
1 | q1 | 1,q1,1,q1,L | 1 | q1 |
? ? 1 0 1 0 1 0 ?
|
? | q1 | ?,q1,1,q2,L | 1 | q2 |
? 1 1 0 1 0 1 0 ?
|
? | q2 | brak instrukcji, koniec |
Z ciągu wejściowego 110101 otrzymaliśmy ciąg wyjściowy 1101010, zatem cyfry binarne zostały przesunięte o 1 pozycję w lewo. Program spełnił swoje zadanie.
Liczba binarna będzie zapisywana na taśmie w postaci ciągu symboli 0 i 1.
Znakiem pustym jest znak pytajnika. Przed wykonaniem programu głowica musi być
ustawiona na pierwszej cyfrze liczby od prawej strony. Zanim ułożymy program,
przyjrzyjmy się zasadom zwiększania o 1 liczby binarnej. Zwiększanie
rozpoczynamy zawsze od ostatniej cyfry.
L.p. | Przykład | Opis |
---|---|---|
Reguła 1 |
110010 + 1 110011 |
Jeśli ostatnią cyfrą jest 0, to zamieniamy je na 1 i kończymy. Reszta bitów pozostaje bez zmian. |
Reguła 2 |
110001 + 1 110010 |
Jeśli ostatnią cyfrą jest 1, to zamieniamy je na 0. Do następnej pozycji należy dodać 1. Taką sytuację nazywamy stanem przeniesienia. W tym przypadku działanie przenosimy do kolejnej pozycji w lewą stronę. |
Reguła 3 |
110001 + 1 110010 |
Jeśli kolejną cyfrą jest 0 i występuje stan przeniesienia, zamieniamy ją na 1 i kończymy. Reszta bitów pozostaje bez zmian. |
Reguła 4 |
110011 + 1 110100 |
Jeśli kolejną cyfrą jest 1 i występuje stan przeniesienia, to zamieniamy ją na 0, utrzymujemy stan przeniesienia i przesuwamy się na kolejną pozycję po lewej stronie. Dla nowej pozycji znów będą obowiązywały reguły 3 i 4. |
Reguła 5 |
11 + 1 100 |
Jeśli skończyły się cyfry (natrafiliśmy na znak pusty) i występuje stan przeniesienia, to znak pusty zamieniamy na cyfrę 1 i kończymy. |
Mając taką analizę każdą regułę kodujemy odpowiednią instrukcją dla maszyny
Turinga.
L.p. | instrukcja | Opis |
---|---|---|
Reguła 1 |
0,g0,1,q2,L |
W stanie początkowym q0 symbol 0 przechodzi w 1. Stan q0 zmienia się na stan q2. Zwróć uwagę, iż żadna instrukcja nie wykorzystuje tego stanu. Zatem dla dowolnego symbolu wejściowego maszyna Turinga zatrzyma wykonywanie programu. |
Reguła 2 |
1,q0,0,q1,L |
Jeśli w stanie początkowym odczytanym symbolem będzie 1, to zmieni się ona na 0, a maszyna przejdzie w stan q1, czyli w stan przeniesienia. Program nie zatrzyma się. Głowica zostanie przesunięta w lewo do sąsiedniej komórki, czyli do następnej cyfry w zapisie liczby. |
Reguła 3 |
0,q1,1,q2,L |
Jeśli w stanie przeniesienia q1 odczytany zostanie symbol 0, to maszyna zmieni go na 1 i przejdzie w stan końcowy, który spowoduje w następnym kroku zatrzymanie programu. |
Reguła 4 |
1,q1,0,q1,L |
Jeśli w stanie przeniesienia q1 odczytany zostanie symbol 1, to maszyna zamieni go na symbol 0, utrzyma stan przeniesienia q1 i przejdzie do następnej pozycji w zapisie liczby. |
Reguła 5 |
?,q1,1,q2,L |
Jeśli w stanie przeniesienia q1 natrafimy na koniec zapisu liczby (czyli znak pusty), to maszyna zapisze w bieżącej komórce taśmy symbol 1 i przejdzie w stan końcowy. Program zakończy się w następnym kroku |
Zatem kompletny program wygląda następująco:
Program |
---|
** Zwiększanie liczby binarnej o 1 ** (C)2004 mgr Jerzy Wałaszek ** I LO w Tarnowie ************************************************ 0,q0,1,q2,L do 0 dodajemy 1 i kończymy 1,q0,0,q1,L do 1 dodajemy 1 i przeniesienie 0,q1,1,q2,L do 0 dodajemy przeniesienie i koniec 1,q1,0,q1,L do 1 dodajemy przeniesienie i dalej ?,q1,1,q2,L zapisujemy przeniesienie i koniec |
Prześledźmy jego działanie dla liczby binarnej 1011(2)
= 11(10). Głowicę ustawiamy na ostatniej cyfrze zapisu
liczby. Maszyna startuje w stanie q0.
Taśma z głowicą |
Odczytany znak |
Stan bieżący |
Wykonywana operacja |
Zapisywany znak |
Nowy stan |
---|---|---|---|---|---|
? 1 0 1 1 ? |
1 | q0 | 1,q0,0,q1,L | 0 | q1 |
? 1 0 1 0 ? |
1 | q1 | 1,q1,0,q1,L | 0 | q1 |
? 1 0 0 0 ?
|
0 | q1 | 0,q1,1,q2,L | 1 | q2 |
? 1 1 0 0 ? |
1 | q2 | brak instrukcji - koniec |
Otrzymaliśmy liczbę binarną 1100(2) = 12(10). Program spełnił swoje zadanie.
Kod U2 umożliwia zapis liczb ze znakiem. Dokładne omówienie zasad tworzenia tego kodu znajdziecie w naszym artykule o systemach liczbowych. Definicja liczby przeciwnej jest następująca:
Liczba b jest liczbą przeciwną do liczby a, jeśli a + b = 0
Istnieje kilka metod znajdowania liczby przeciwnej w kodzie U2. Na nasz użytek wybierzemy metodę następującą:
Algorytm wyznaczania liczby przeciwnej w kodzie U2 |
---|
|
Chociaż algorytm wydaje się na pierwszy rzut oka nieco zawiły, to jednak jest bardzo prosty. Oto przykład:
Znajdziemy liczbę przeciwną do 00101000(U2)
= 40(10).
00101000 |
Rozpoczynamy od ostatniej cyfry. Pomijamy wszystkie cyfry 0. |
00101000 |
Pierwszą napotkaną cyfrę 1 pozostawiamy bez zmian. |
11011000 |
Od tego momentu wszystkie pozostałe cyfry zmieniamy na przeciwne. |
11011000 |
Otrzymana liczba ma wartość przeciwną w kodzie U2. Sprawdzamy: 1x(-27) + 1x26 + 0x25 + 1x24 + 1x23 + 0x22 + 0x21 + 0x20 = 1x(-128) + 1x64 + 1x16 + 1x8 = -128 + 64 + 16 + 8 = - 40, zgadza się. |
Wynika z tego, iż maszyna Turinga odczytując cyfry 0 nie powinna zmieniać swojego stanu. Po napotkaniu pierwszej cyfry 1 stan maszyny powinien się zmienić. Teraz w tym nowym stanie wszystkie cyfry powinny być zmieniane na przeciwne. Oto odpowiedni program:
Program |
---|
** Zamiana liczby U2 na przeciwną ** (C)2004 mgr Jerzy Wałaszek ** I LO w Tarnowie ************************************************ 0,q0,0,q0,L pomijamy początkowe 0 1,q0,1,q1,L pierwsze 1 pozostawiamy bez zmian 0,q1,1,q1,L pozostałe bity zmieniamy 1,q1,0,q1,L na przeciwne |
Dla przykładu prześledźmy działanie tego programu dla liczby
1110(U2) = -2.
Głowicę ustawiamy na ostatniej cyfrze zapisu liczby. Maszyna rozpoczyna
wykonywanie programu od stanu q0.
Taśma z głowicą |
Odczytany znak |
Stan bieżący |
Wykonywana operacja |
Zapisywany znak |
Nowy stan |
---|---|---|---|---|---|
? 1 1 1 0 ?
|
0 | q0 | 0,q0,0,q0,L | 0 | q0 |
? 1 1 1 0 ? |
1 | q0 | 1,q0,1,q1,L | 1 | q1 |
? 1 1 1 0 ? |
1 | q1 | 1,q1,0,q1,L | 0 | q1 |
? 1 0 1 0 ? |
1 | q1 | 1,q1,0,q1,L | 0 | q1 |
? 0 0 1 0 ? |
? | q1 | brak instrukcji - koniec |
Otrzymaliśmy liczbę 0010(U2) =
2, a więc przeciwną do 1110(U2)
= -2. Program spełnił swoje zadanie.
W transmisjach cyfrowych pojawiają się błędy polegające na tym, iż odbiornik odczytuje zakłócone bity ze stanem przeciwnym, tzn. jeśli nadano bit o wartości 1, odczytane zostaje 0 i na odwrót. Na występowanie zakłóceń zwykle nie mamy wpływu - mogą to być np. wyładowania elektryczne w trakcie burzy, iskrzenie w układach elektrycznych maszyny pracującej w pobliżu toru transmisyjnego, różne zakłócenia losowe. Dlatego transmisję zabezpiecza się przy pomocy różnych kodów, które umożliwiają odbiornikowi wykrycie błędu w odebranych danych (kody detekcyjne) lub poprawienie błędu (kody korekcyjne).
Najprostszym rodzajem kodu detekcyjnego jest bit parzystości. Do przesyłanych danych dodajemy dodatkowy bit o takiej wartości 0 lub 1, aby liczba bitów 1 w przesyłanym słowie była parzysta. Jeśli teraz wystąpi przekłamanie w odbiorze, to odbiornik zliczając otrzymane bity o wartości 1 otrzyma liczbę nieparzystą, ponieważ jeden z bitów zmienił się na przeciwny Stąd będzie wiadome, iż odebrana informacja jest błędna - odbiornik w takim przypadku może połączyć się kanałem zwrotnym z nadajnikiem i zażądać ponowienia transmisji danych.
Zasada wyznaczania bitu parzystości jest bardzo prosta:
Algorytm wyznaczania bitu parzystości |
---|
|
W programie dla maszyny Turinga stan bitu parzystości będziemy kodowali stanami: q0 - stan 0 i q1 - stan 1.
Program |
---|
** Bit parzystości ** (C)2004 mgr Jerzy Wałaszek ** I LO w Tarnowie ************************************************ 0,q0,0,q0,L bity 0 ignorujemy 1,q0,1,q1,L bity 1 uzupełniamy do parzystych 0,q1,0,q1,L bity 0 ignorujemy 1,q1,1,q0,L bity 1 uzupełniamy do parzystych ?,q0,0,q2,L zapisujemy wynikowy bit ?,q1,1,q2,L parzystości |
Dla przykładu prześledźmy działanie tego programu dla danych binarnych 110100. Głowicę ustawiamy na ostatniej cyfrze zapisu liczby. Maszyna rozpoczyna wykonywanie programu od stanu q0.
Taśma z głowicą |
Odczytany znak |
Stan bieżący |
Wykonywana operacja |
Zapisywany znak |
Nowy stan |
---|---|---|---|---|---|
? ? 1 1 0 1 0 0 ?
|
0 | q0 | 0,q0,0,q0,L | 0 | q0 |
? ? 1 1 0 1 0 0 ? |
0 | q0 | 0,q0,0,q0,L | 0 | q0 |
? ? 1 1 0 1 0 0 ? |
1 | q0 | 1,q0,1,q1,L | 1 | q1 |
? ? 1 1 0 1 0 0 ? |
0 | q1 | 0,q1,0,q1,L | 0 | q1 |
? ? 1 1 0 1 0 0 ? |
1 | q1 | 1,q1,1,q0,L | 1 | q0 |
? ? 1 1 0 1 0 0 ? |
1 | q0 | 1,q0,1,q1,L | 1 | q1 |
? ? 1 1 0 1 0 0 ? |
? | q1 | ?,q1,1,q2,L | 1 | q2 |
? 1 1 1 0 1 0 0 ? |
? | q2 | brak instrukcji, koniec |
Otrzymaliśmy wynik 1110100 - liczba jedynek wynosi 4, czyli jest parzysta.
Zespół Przedmiotowy Chemii-Fizyki-Informatyki w I Liceum Ogólnokształcącym im. Kazimierza Brodzińskiego w Tarnowie ul. Piłsudskiego 4 ©2024 mgr Jerzy Wałaszek |
Materiały tylko do użytku dydaktycznego. Ich kopiowanie i powielanie jest dozwolone
pod warunkiem podania źródła oraz niepobierania za to pieniędzy.
Pytania proszę przesyłać na adres email:
Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.
Informacje dodatkowe.