Ćwiczenie XII

 

1. Pojęcia

            Grafy i drzewa

            Format zmiennoprzecinkowy dwuskładnikowy NKB cd.

            Przepełnienie

            Kody korekcyjne i detekcyjne

            Sumy kontrolne CRC

2. Wiadomości

  

2.1 Grafy i drzewa

 

            Grafy- są to struktury danych. Grafem nazywamy parę (X, T) gdzie X oznacza zbiór tzw. Węzłów (wierzchołków) a T jest zespołem krawędzi. Garf jest skierowany jeśli krawędziom został przypisany jakiś kierunek (symbol, strzałka) biorąc pod uwagę dwa węzły grafu x, y połączone krawędzią to węzeł x jest węzłem początkowym a węzeł y końcowym.

 

            W informatyce drzewa są strukturami danych reprezentującymi drzewa matematyczne. W naturalny sposób reprezentują hierarchię danych (obiektów fizycznych i abstrakcyjnych, pojęć, itp.), toteż głównie do tego celu są stosowane. Drzewa ułatwiają i przyspieszają wyszukiwanie, a także pozwalają w łatwy sposób operować na posortowanych danych. Znaczenie tych struktury jest bardzo duże i ze względu na swoje własności drzewa są stosowane praktycznie w każdej dziedzinie informatyki (np. bazy danych, grafika komputerowa, przetwarzanie tekstu, telekomunikacja).

 

 

Drzewa składają się z wierzchołków (węzłów) oraz łączących je krawędzi. Wszystkie wierzchołki połączone z danym wierzchołkiem, a leżące na następnym poziomie są nazywane synami tego węzła (np. synami wierzchołka D są G i H, wierzchołka H: J, K oraz L). Wierzchołek może mieć dowolną liczbę synów, jeśli nie ma ich wcale nazywany jest liściem; na rysunku liście zaznaczone są kolorem niebieskim.

Wierzchołek jest rodzicem dla każdego swojego syna; każdy węzeł ma dokładnie jednego rodzica. Wyjątkiem jest korzeń drzewa, który nie ma rodzica

 

 

 

 

Drzewa binarne

 

W drzewie binarnym węzeł może mieć co najwyżej dwoje bezpośrednich potomków oraz występuje rozgraniczenie na potomny węzeł prawy i lewy.

 

 

2.2 Format zmiennoprzecinkowy dwuskładnikowy NKB

 

            W przypadku formatu zmiennoprzecinkowego ważna jest kontrola przepełnienia. Przepełnienie ma miejsce w przypadku występowania na dwu najstarszych bitach przeniesienia różnych wartości – tj. zera i jedynki.

 

            Drugą wymaganą operacją jest operacja normalizacji, czyli doprowadzania do postaci w której bit znaku oraz najstarszy bit mantysy są różne czyli wynoszą 0 i 1 lub odwrotnie 1 i 0. Normalizacja polega na kolejnym przesuwaniu w prawo (dzieleniu przez dwa) i jednoczesnym zwiększaniu cechy o jeden, do chwili uzyskania postaci znormalizowanej.

 

Przykład:

 

A = 12

B = 5.5

 

A         011000 | 1100

B         5.5 / 8 * 8 = (4 + 1 + 0.5) / 8 * 2^3 = (1/2 + 1/8 + 1/16)*2^3

 

mB      010110

mB/2   001011­

 

 

mA                  0 1 1 0 0 0

mB/2              0 0 1 0 1 1

                    0 1 1  0 0 0

                    ==========

                    1 0 0 0 1 1

 

 

Nadmiar, więc należy podzielić przez 2, zanegować bit znaku i cechę zmniejszyć o jeden.

 

 

                        1 1 0 0 0 1

A + B              0 1 0 0 0 1 | 1 1 0 1

 

 

                        spr. (1/2 + 1/32)*2^5 = 17/32 * 32 = 17

 

Wynik z niedomiarem z powodu dzielenia przez 2.

 

 

2.2. Kody detekcyjne i korekcyjne

 

Kody detekcyjne i korekcyjne umożliwiają wykrycie i skorygowanie błędów występujących w systemach cyfrowych oraz w systemach transmisji danych. Kody takie są tworzone poprzez dodanie bitów kontrolnych do przesyłanej informacji. Dla określonej klasy błędów istnieją kody detekcyjne i korekcyjne umożliwiające ich wykrycie. Kody korekcyjne pozwalają dodatkowo skorygować wykryte błędy.

 

Wśród kodów detekcyjnych największe zastosowanie znalazł kod z kontrolą parzystości oraz kod ze stałą liczbą jedynek. Natomiast z grupy kodów korekcyjnych najczęściej są wykorzystywane binarne kody cykliczne, np. kod Bose-Chaudhuri-Hocquenghema (BCH) lub niebinarne kody cykliczne korygujące błędy grupowe, np. kod Reeda-Solomona (RS).

 

Kod z kontrolą parzystości

 

Kod ten jest tworzony przez dodanie do każdego słowa kodu dwójkowego bitu przyjmującego taką wartość, aby liczba jedynek w słowie była parzysta (lub nieparzysta). Kontrolę parzystości można zastosować w dowolnym kodzie. Słowa kodowe są rozszerzane o dodatkową pozycję kontrolną.

 

Dla kodu BCD 8421 bit parzystości umożliwia wykrycie zniekształcenia dowolnej

nieparzystej liczby bitów kodu, natomiast są niewykrywalne zniekształcenia dowolnej parzystej liczby elementów. W celu rozdzielenia bitów części informacyjnej od bitów części kontrolnej słów kodowych wprowadzono kropkę.

 

Wagi: 8 4 2 1 . 0

Cyfry

0 0 0 0 0 . 0

1 0 0 0 1 . 1

2 0 0 1 0 . 1

3 0 0 1 1 . 0

4 0 1 0 0 . 1

5 0 1 0 1 . 0

6 0 1 1 0 . 0

7 0 1 1 1 . 1

8 1 0 0 0 . 1

9 1 0 0 1 . 0

 

Kody ze stałą liczbą jedynek

 

Kody tej klasy zawierają stałą liczbę jedynek we wszystkich słowach kodowych. Mogą one być zarówno wagowe, jak i niewagowe. Stała liczba jedynek umożliwia wykrycie błędów przy odbiorze słów kodowych.

 

Najbardziej rozpowszechnionym kodem o stałej liczbie jedynek jest kod „1 z 10”. Jest

to kod wagowy dwójkowo-dziesiętny, w którym jedynka jest umieszczana w słowach kodowych

na pozycjach o wagach 0,1,2,3,4,5,6,7,8,9.

 

Wagi: 9 8 7 6 5 4 3 2 1 0

 

Cyfry

 

0 0 0 0 0 0 0 0 0 0 1

1 0 0 0 0 0 0 0 0 1 0

2 0 0 0 0 0 0 0 1 0 0

3 0 0 0 0 0 0 1 0 0 0

4 0 0 0 0 0 1 0 0 0 0

5 0 0 0 0 1 0 0 0 0 0

6 0 0 0 1 0 0 0 0 0 0

7 0 0 1 0 0 0 0 0 0 0

8 0 1 0 0 0 0 0 0 0 0

9 1 0 0 0 0 0 0 0 0 0

 

 

 

 

2.3 Sumy kontrolne CRC

 

 

CRC – Cyclic Redundancy control

 

Ciąg znaków do przesłania zapisujemy w postaci binarnej.

Wybieramy wielomian generator G(x): np. 5 bitowy.

Do przesyłanego ciągu znaków M(x) dopisujemy z prawej strony zera w ilości o jeden mniejszej od długości generatora – w omawianym przypadku 4 bity.

Wykonujemy operacje M(x) xor G(x) do uzyskania reszty R(x) mniejszej od rozmiaru generatora G(x)

Resztę otrzymaną R(x) dopisujemy z prawej strony do generatora G(x).

W ten sposób otrzymaliśmy ciąg znaków z sumą kontrolną.

 

Sprawdzenie poprawności polega na podzieleniu (operacja xor) wygenerowanego ciągu znaków przez generator G(x). W przypadku poprawnego przesłania ciągu powinniśmy otrzymać resztę zero.

 

 

 

Przykład 1

 

G(x) = x4 + x3 + 1 = 11001

 

M(x)

 

11110101|0000  :  11001  = 1010101

11001

=====

    11110

    11001

     =====

         11110

         11001

         =====

             11100

             11001

             =====

                  1010

 

 

 

Sprawdzenie poprawności:

 

11110101|1010  :  11001  =  1010110

11001

--------

     11110

     11001

      -------

          11111

          11001

          -------

              11101   

              11101

              -------

 

3. Zadania i ćwiczenia

 

Zadanie 1

 

A = 7, B = 11

 

Obliczyć A + B oraz A - B

 

 

Zadanie 2

 

A = 14, B = 21.5

 

Obliczyć A + B oraz A - B

 

 

Zadanie 3

Obliczyć sumę kontrolną CRC dla podanych wielomianów:

 

    G(x) = x4 + x2 + 1 = 10101

 

    M(x) = 10111011

 

Zadanie 4

Obliczyć sumę kontrolną CRC dla podanych wielomianów:

 

    G(x) = x4 + x3 + 1 = 10101

 

    M(x) = 1101101

 

 

 

Przykłady

A = 60

B = -6.5

 

A – B = ?

 

A         60/64 * 64 = (32 + 16 + 8 + 4) / 64 * 2 ^ 6 = (1/2 + ¼ + 1/8 + 1/16) * 2^6

 

A         011110 | 1110

 

B = -6.5 / 8 * 8 = (-8 + 1 + 0.5) / 8 * 2 ^ 3 = (-1 + 1/8 + 1/16) 2^3

 

B         1 0 0 1 1 0 | 1 0 1 1

 

            cA – cB = 3

 

mB / 2^3        =          1 1 1 1 0 0| 1 0 1 1

 

mA                  =          0 1 1 1 1 0

 

 

           

mA                             0 1 1 1 1 0

mB/2^3                      1 1 1 1 0 0

                                           

                               1 1 1 1 0 0 0

                        ==============                                                   

 

                              1 0 1 1 0 1 0 | 1 0 1 1

 

 

                        spr. (1/2 + ¼ + 1/16) * 2^6 = 52.0 == wynik niedokładny, dzielenie przez 2^3