Kodowanie informacji za pomocą bitów. 

Część poniższych materiałów pochodzi ze strony:

Informacja i jej przetwarzanie.

Autor materiałów mgr Jerzy Wałaszek  

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji

GNU Free Documentation License.

Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl

LICENCJA

GNU FDL powoduje, że tekst nią objęty może być zarówno kopiowany, jak i modyfikowany nawet bez wiedzy i zgody autora. Konieczne jest zamieszczenie wraz z pochodnym dziełem tekstu licencji GFDL, informacji o źródle i autorach oryginału. 

DANE + INTERPRETACJA + KONTEKST → INFORMACJA 

DANE

Dane to surowe fakty, zjawiska, liczby lub symbole, które same w sobie nie niosą żadnego znaczenia. Są to po prostu zbiory znaków bez określonego kontekstu. Na przykład, „38” to tylko liczba.

INTERPRETACJA

Interpretacja to proces nadawania znaczenia tym danym. Jest to analiza i zrozumienie ich, co pozwala na przekształcenie surowych faktów w coś sensownego. Interpretacja może być subiektywna i zależy od osoby, która jej dokonuje. Na przykład, jeśli dowiemy się, że "38" to temperatura, zaczynamy nadawać tej liczbie znaczenie.

KONTEKST

Kontekst to okoliczności, w jakich dane występują. Bez kontekstu interpretacja może być mylna lub niepełna. Kontekst dostarcza niezbędnych informacji, które pomagają w prawidłowym zrozumieniu danych. Kontynuując przykład, jeśli „38” to temperatura, musimy wiedzieć, czy jest to temperatura ciała, temperatura powietrza, czy może temperatura wrzenia, oraz w jakiej jednostce jest wyrażona (np. stopnie Celsjusza lub Fahrenheita).

INFORMACJA

Informacja to efekt połączenia danych, ich interpretacji oraz kontekstu. To wiedza, która powstaje w momencie, gdy surowe dane zostają uporządkowane i zinterpretowane w określonym kontekście. Informacja jest więc czymś, co ma znaczenie i może prowadzić do podejmowania decyzji. Przykładowo, jeśli wiemy, że „38” to temperatura (dane) ciała (kontekst), możemy zinterpretować (interpretacja) to jako stan podgorączkowy, a w konsekwencji podjąć działania, np. zastosować leki.

Podsumowując, informacja nie istnieje bez danych, ale same dane nie stają się informacją, dopóki nie zostaną poddane interpretacji w odpowiednim kontekście.

Jeśli powyższe trzy punkty spełnimy, otrzymamy system reprezentacji określonych informacji za pomocą wybranych symboli - danych. Gdy to już wiemy i rozumiemy, możemy przejść do pojęcia bitu.

Postawmy się w roli pioniera komputerów. 

Mamy przed sobą bardzo poważne zadanie - budowę komputera, czyli maszyny liczącej, która będzie przetwarzała informację. 

Zanim zaczniemy montować to ogromniaste urządzenie z tysięcy podzespołów i setek kilometrów kabli, musimy określić zbiór symboli, które maszyna ma przetwarzać. Innymi słowy musimy określić zbiór danych dla maszyny oraz sposoby ich interpretacji.

Jakie symbole wybrać? Mowę? Za trudna i jak ją zapisywać wewnątrz maszyny! Pismo? Też trudne. Gesty lepiej zapomnieć. Ideałem byłby symbole najprostsze z możliwych. Dla takich symboli może znaleźlibyśmy jakieś w miarę proste sposoby ich realizacji w naszym komputerze za pomocą odpowiednich obwodów elektronicznych. Co to mogłoby być?

I w tym miejscu ktoś kiedyś dostał olśnienia - najprostszym symbolem byłby taki symbol, który mógłby występować tylko w dwóch rozróżnialnych postaciach, w dwóch formach, najlepiej przeciwnych. Dlaczego akurat w dwóch a nie w trzech. Bo dwie postacie są prostsze od trzech, jasne?!

W układzie elektronicznym taki symbol mógłby być przedstawiany przez np. dwa różne napięcia elektryczne - pierwsza postać symbolu to napięcie powiedzmy 5V, a druga postać to napięcie 0V. Dwa różne napięcia da się łatwo rozróżnić i projekt układów elektronicznych, które na takie napięcia reagują nie jest wcale taki trudny (dla inżyniera elektronika oczywiście - dla większości licealistów jest to problem typu niemożliwego). 

Zamiast napięcia można na przedstawiciela naszego symbolu wybrać wybrać prąd elektryczny - prąd płynie w obwodach - pierwsza postać, prąd nie płynie - druga postać. 

A może światło? Jest strumień świetlny - pierwsza postać, nie ma strumienia - postać druga (cały czas czekam, aż w końcu pojawią się komputery wykorzystujące, zamiast prądów i napięć, fotony. Przyjemnie byłoby zdjąć obudowę i popatrzyć sobie, jak nasz komputerek ładnie w środku sobie świeci).

W tym momencie powinieneś zapytać - no dobrze, ale po co mi to wszystko jest potrzebne?

Cały czas chodzi nam o przedstawianie informacji przy pomocy jak najprostszych symboli. Znaleźliśmy proste dane - symbole dwustanowe. Musimy pokazać, iż takie symbole będą dobrze nadawały się do naszego celu, czyli pozwolą kojarzyć ze sobą dowolną ilość informacji.

Aby ułatwić sobie życie, oznaczmy stany naszego symbolu cyframi 1 (stan wysoki - np. napięcie 5V (wolt), prąd płynie, jest światło, itp.) oraz 0 (stan niski - np. napięcie 0V, brak prądu, brak światła, itp.). Dlaczego akurat wybraliśmy cyfry 1 i 0? A dlaczego nie? Są to znaki równie dobre jak każde inne (np. elektronicy często w tym samym charakterze wykorzystują literki H - stan wysoki i L - stan niski), a dodatkowo, co zobaczymy w dalszych rozdziałach, cyfry 0 i 1 posiadają wiele pożytecznych dla nas zalet. Otrzymany zbiór danych zawiera teraz dwa rozróżnialne symbole:

 Zbiór danych = {0, 1}

Dwóm symbolom można przypisać dwa różne znaczenia, dwie informacje. Jakie? Potrzebne nam w danym zastosowaniu. Dla przykładu wyobraźmy sobie, iż nasz system komputerowy zbiera dane od czujników pożarowych, umieszczonych w różnych punktach budynku. Czujnik pożarowy reaguje na wzrost temperatury lub dym. Jeśli temperatura osiągnie krytyczną wartość lub pojawi się dym w otaczającym czujnik powietrzu, wewnątrz zostają zwarte dwa przewody i zaczynie płynąć prąd elektryczny. Brak prądu (stan niski 0) oznacza zatem normalną temperaturę w chronionym pomieszczeniu. Pojawienie się prądu (stan wysoki 1) informuje nas o wysokiej temperaturze, czyli o wybuchu pożaru. W tym kontekście stany 0 i 1 mają oczywiste znaczenie:

0 - wszystko jest w porządku, 1 - pożar

W innym kontekście symbole 0 i 1 mogą posiadać zupełnie inne znaczenia (np. 1 - mamy czekoladę, jest dobrze; 0 - brakło czekolady, panika!). To od nas zależy co im przypiszemy - o znaczeniu używanych przez ludzi słów decydowali używający je ludzie, a nie niedźwiedzie w Alpach (te być może przyczyniły się do powstania słów w stylu AUUUUU..., które są rzadkimi, wspólnymi słowami dla prawie wszystkich języków, których użytkownicy mieli okazję spotkać niedźwiedzia. Jest to fascynujące, ale nie na temat).

Symbol, który może występować w jednym z dwóch stanów (form, postaci), nazwano bitem. Twórcą tej nazwy był amerykański statystyk John Turkey, który ją wymyślił w trakcie drugiego śniadania (najprawdopodobniej po wypiciu dokładnie dwóch łyków kawy z niewielkim dodatkiem mleka, co jednakże nie ma wpływu na dalsze losy bitów) na jednej z konferencji naukowych w zimie roku 1943-44. W owym czasie istniały już komputery wykorzystujące opisane przez nas powyżej symbole dwustanowe do wykonywania różnych obliczeń. Informatycy oznaczali je cyframi 0 i 1, ponieważ w tej postaci nadawały się doskonale do przedstawiania liczb binarnych, dwójkowych, za pomocą których komputery liczyły. John Turkey utworzył nazwę bit z literek dwóch słów angielskich: binary digit (cyfra dwójkowa, czyli 0 lub 1):

bit = binary digit

W późniejszym okresie John ujawnił, iż rozważał jeszcze dwie inne kombinacje literek:

bigit = binary digit
binit = binary digit

Jak dzisiaj już wiemy, przyjęła się tylko pierwsza forma. Określenie bit w charakterze symbolu dwustanowego, przeznaczonego do symbolicznego reprezentowania informacji pojawiło się po raz pierwszy w 1948 roku w pracach wybitnego informatyka, Claude Shannona, twórcy teorii informacji.

Jednemu bitowi możemy przypisać maksymalnie dwie różne informacje - jedną dla stanu 1 oraz drugą dla stanu 0. Co jednak mamy zrobić, jeśli w pewnym kontekście musimy operować większą ilością informacji? Cóż, musimy potraktować bity jako literki i tworzyć z nich słowa - zupełnie tak samo jak w naszym ojczystym języku. Zbadajmy tę możliwość. 

Nowe kombinacje słówek binarnych otrzymujemy z poprzednich kombinacji dołączając do nich raz bit o stanie 0, a następnie jeszcze raz dołączając bit o stanie 1. W efekcie ilość kombinacji zawsze podwaja się.

Widzimy wyraźnie, iż dodanie kolejnego bitu do słówka binarnego zwiększa dwukrotnie ilość możliwych kombinacji stanów bitów tworzących to słowo. Większa ilość kombinacji przekłada się na większą ilość informacji, które można bezpośrednio przypisać tworzonym słówkom binarnym. Ponieważ ilość kombinacji podwaja się przy każdym dodanym bicie, otrzymujemy proste zależności: 

Co z tego wynika? Otóż dla każdej skończonej ilości informacji x zawsze możemy dobrać takie n, aby n bitowe słówka binarne przyjęły tyle różnych stanów, ile jest potrzebne do zakodowania tej ilości informacji. W tym celu wystarczy, aby był spełniony warunek:

dla x > 1: n ≥ log2x, n Î N

Przykład:

Załóżmy, iż w pewnym systemie informatycznym musimy przetwarzać (posługiwać się) 1000 różnych informacji. Przetwarzane informacje będziemy w tym systemie przedstawiać n bitowymi słówkami. 

ZADANIE

Ile musi wynosić n, aby n bitowe słówka binarne przyjęły co najmniej 1000 różnych kombinacji?

Odpowiedź: n ≥  log21000 ≈ 9,96578..., Przyjmijmy zatem n = 10.

Dla słówek 10 bitowych liczba wszystkich możliwych kombinacji wynosi 210 = 1024. Wynika z tego, iż w naszym systemie 24 słówka nie będą posiadały żadnego znaczenia - to nic, pozostaną na zapas, gdyby w przyszłości okazało się, iż zamiast 1000 informacji będziemy potrzebowali np. 1005.

Teraz możemy odpowiedzieć na postawione na początku rozdziału pytania:

• Czym jest bit?
  Bit jest dwustanowym sygnałem, daną, która może być skojarzona z dokładnie dwoma różnymi informacjami. Stany bitu oznaczamy cyfrą 1 i 0.
   

• Do czego jest nam potrzebny bit?
  Bitu potrzebujemy do tworzenia słówek binarnych, które z kolei kojarzymy z odpowiednimi informacjami. W ten sposób dowolną ale skończoną ilość informacji możemy przypisać do odpowiedniej liczby różnych słówek binarnych.

W ten sposób zbudujemy tzw. kod binarny (ang. binary code). Słówka tego kodu będą reprezentowały przydzielone im informacje. Oczywiście aby odczytać te informacje, należy znać dokładnie sposób kodowania, czyli przydzielania informacji słówkom kodowym. 

Na pierwszy rzut oka zadanie wydaje się beznadziejne - jak mogę przekształcić piękne obrazy Rubensa w jakieś tam bity przyjmujące stany 0 lub 1? Na pewno masz rację, przekształcić ich nie możemy, lecz z pewnym przybliżeniem możemy zakodować zawartą w tych obrazach informację o kolorach. Na początek musimy zastanowić się, w jaki sposób będziemy przedstawiali informację zawartą w grafice, czyli nad sposobami jej reprezentacji.

Postawmy sobie chwilowo mniej ambitne zadanie. Załóżmy, iż nasza grafika zawiera tylko dwa różne kolory - biały i czarny. Za pomocą bitów zakodujemy kolor na obrazku. Ponieważ mamy tylko dwa różne kolory, wystarczy na to jeden bit:

bit 0 - kolor biały

bit 1 - kolor czarny

Określiliśmy sposób przyporządkowania informacji do bitu - to jakby język naszej nowej mowy kodującej grafikę czarno-białą. Pozostaje tylko problem, w jaki sposób ta informacja zawarta w bitach będzie połączona z obrazkiem. Rozwiązanie jest dosyć proste. Obrazek dzielimy na drobną siateczkę punktów, tzw. raster. W obrębie danego punktu (zwanego pikselem - ang. pixel = picture element, czyli element obrazowy) kolor jest stały - albo biały, albo czarny.

Na pewno jest to pewnym oszustwem. Ale jeśli siateczka punktów jest bardzo gęsta, to możemy dać się na nie nabrać - po prostu nasze oko nie zobaczy poszczególnych punktów, tylko obraz. O to właśnie chodzi. Poniżej ten sam obrazek, ale w "normalnej wielkości".

Wygląda całkiem miło. Tak otrzymany obrazek zamieniamy na bity: punkty czarne kodujemy bitem o stanie 1, a punkty białe kodujemy bitem o stanie 0. W postaci bitowej obrazek wygląda tak:

W takiej formie obrazek może być przechowywany we wnętrzu komputera (pamiętamy oczywiście, iż bity są kodowane w komputerze poziomami napięć), przesłany przez sieć teleinformatyczną lub przetwarzany przez odpowiednie algorytmy operujące na bitach. Z postaci bitowej też można bez problemu odzyskać zawartość obrazka. W tym celu wystarczy zbudować urządzenie, które na ekranie monitora obrazuje siatkę punktów graficznych, czyli raster. Następnie do urządzenia przesyłamy informację w postaci bitów dla poszczególnych punktów siatki, a ono wyświetla na ekranie odpowiednio punkt biały dla bitu 0 i czarny dla bitu 1. Tak właśnie działa karta graficzna komputera.

Zadanie kodowania grafiki pozornie się komplikuje, gdy obrazek zawiera więcej kolorów. Załóżmy, iż do narysowania naszej mordki wykorzystamy cztery kolory:

Ponieważ teraz każdy piksel obrazka może przyjąć jeden z czterech różnych kolorów, to informacji tej nie zmieścimy w jednym bicie - potrzebujemy pary bitów. Dwa bity mogą przyjąć cztery różne kombinacje swoich stanów: 00, 01, 10 i 11 tworząc cztery różne binarne słówka kodowe. Każdemu słowu kodowemu przypiszemy jeden kolor piksela. Określmy takie przypisanie: 

Taki sposób kodowania kolorów nazywa się kodowaniem palety barw. Polega on na tym, iż każdemu kolorowi na obrazku przypisujemy osobne słowo kodowe. Zdefiniowawszy paletę można już bez problemów przekształcić obrazek w odpowiedni ciąg bitów: 

Odkodowanie obrazka nie nastarcza większych trudności, jeśli znamy paletę kolorów i sposób jej przyporządkowania słowom kodu. Paleta dwubitowa pozwala na zdefiniowanie czterech kolorów. Paleta 8 bitowa definiuje już 256 kolorów. Paleta 16 bitowa to 65536 barw.

Wniosek: bity nadają się do kodowania grafiki.

W tekstach występują litery oraz inne znaki pisarskie. To właśnie one będą informacjami kodowanymi za pomocą bitów. Dla uproszczenia załóżmy, iż nasze teksty składają tylko z wielkich liter, cyfr, przecinków, kropek oraz spacji. W ten sposób określimy zbiór informacji do zakodowania:

{A, B, C, Ć, D, E, Ę, F, G, H, I, J, K, L, Ł, M, N, Ń, O, Ó, P, R, S, Ś, T, U, W, Y, Z, Ź, Ż,
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, przecinek, kropka, spacja}

Wybrany zbiór zawiera 44 różne znaki. Potrzebujemy słówek binarnych o liczbie bitów równej:

n ≥ log244 = 5,4594..., n = 6

6 bitowe słówka binarne dają 26 = 64 różnych kombinacji. My wykorzystamy tylko 44, zatem 20 słów kodowych pozostanie wolne, bez określonego znaczenia (możemy je w przyszłości wykorzystać na nowe znaki - np. literę X, której chwilowo nie potrzebujemy). Sam przydział słówek binarnych literkom na etapie projektowania jest zupełnie dowolny (dobrze jednak zastosować tutaj pewien schemat - w przyszłości może to zaowocować uproszczeniem przy sortowaniu alfabetycznym tekstów) - ważne jest jedynie to, aby każda literka otrzymała inny kod. W przeciwnym razie skąd byśmy wiedzieli, o którą literkę chodzi?. Możemy to zrobić tak:

 Określiliśmy tzw. kod znakowy (ang. character code). W takiej postaci literki mogą już być przetwarzane przez komputery. Dla przykładu zakodujmy w tym systemie jakieś zdanie:

W drugą stronę też nie ma specjalnych problemów. Mamy ciąg bitów:

000000001110000000101011010000000000101011011110010011001111011010001011000000

Ponieważ wiemy, iż literki kodowane są za pomocą słówek 6 bitowych, dzielimy ciąg bitów na takie właśnie słówka:

000000  001110  000000  101011  010000  000000  101011  011110  010011  001111  011010  001011  000000

Każde słówko kodowe zamieniamy na skojarzony z nim znak wg tabeli kodu znakowego. Otrzymujemy czytelną dla nas postać tekstu:

Wniosek: bity nadają się do kodowania znaków.

Teraz pokażemy sposób przedstawiania liczb naturalnych za pomocą bitów. Wyobraźmy sobie, iż żyjemy w takim dziwnym kraju (no, może tak bardzo tego nie musimy sobie wyobrażać, wystarczy się rozglądnąć), w którym wszystkie monety mają nominały równe potęgom liczby 2: 

Załóżmy, iż w tym dziwnym kraju wyszło zarządzenie, które głosi, iż wszystkie kwoty należy wypłacać najmniejszą możliwą liczbą monet. Za nieprzestrzeganie tego zarządzenia rząd nałożył olbrzymią karę 264. Cóż, nikt tyle pieniążków nie miał, zatem wszyscy rozpoczęli skrupulatne odmierzanie sum pieniężnych.

Z sumami będącymi potęgami liczby 2 nie ma problemu - wystarczy jedna moneta o właściwym nominale. Pozostałe sumy wyliczamy następująco:

Trzeba wypłacić 157. Aby monet było jak najmniej, każda o właściwym nominale powinna wystąpić co najwyżej raz. Ano zobaczmy:

Pierwszą monetą może być 128 (256 byłoby za duże, a 64 musielibyśmy użyć dwukrotnie). Zatem płacimy 128. Pozostaje wciąż:

157 - 128 = 29

Najbliższą monetą będzie 16. Płacimy 16. Pozostaje:

29 - 16 = 13

Teraz płacimy 8. Pozostaje:

13 - 8 = 5

Płacimy 4. Pozostaje:

5 - 4 = 1

I na koniec wypłacamy 1. Podsumujmy:

157 = 128 + 16 + 8 + 4 + 1

No dobrze, powiesz. Co to ma jednak wspólnego z bitami? A ma. Zwróć uwagę, iż przy wypłacie sumy podejmujemy dla poszczególnych nominałów monet jedną z decyzji:

Wypłacić daną monetę  - 1

Nie wypłacać monety  - 0

A to są przecież nasze kochane bity. Ułóżmy monety kolejno z prawa na lewo od najmniejszej do największej. Otrzymamy następujący ciąg nominałów:

Teraz pod tak wypisanymi nominałami zapisujemy dla danej sumy pieniężnej wypłaconą liczbę monet danego nominału: 

Ponieważ dana moneta może wystąpić co najwyżej raz, to pod nominałami zapisujemy tylko cyfry 0 lub 1. Jeśli cyfry potraktujemy teraz jako bity, otrzymamy zapis binarny danej liczby dziesiętnej:

157(10) = ...00010011101(2)

W zapisie tym bit o stanie 1 ma wartość odpowiadającej mu potęgi liczby 2. Bit o stanie 0 ma wartość 0. Aby obliczyć wartość całej liczby binarnej wystarczy zatem zsumować wartości bitów o stanie 1.

Oto inny przykład:

W dziwnym kraju na czeku bankier wypisał sumę pieniężną zaznaczając liczbę monet o kolejnych nominałach, które należy wypłacić klientowi banku. Zrobił to tak:

1011101101

Jaką sumę należy wypłacić? My już wiemy. Skoro poszczególne cyfry oznaczają liczbę monet o danym nominale, zapisujemy to tak:

Teraz sumujemy nominały wypłaconych monet i otrzymujemy:

512 + 128 + 64 + 32 + 8 + 4 + 1 = 749

Proste? Jeśli nie, to przeczytaj to kolejny raz, aż zrozumiesz.

Formalnie rzecz biorąc, jeśli mamy n bitową liczbę binarną:

bn-1 bn-2 ... b2 b1 b0, gdzie bi = 0 lub 1, dla i = 0,1,2,...,n-1

to jej wartość dziesiętną obliczamy zgodnie z poniższym wzorem:

wartość = bn-12n-1 + bn-22n-2 + ... + b222 + b121 + b020

Wniosek: bity nadają się do kodowania liczb.

Podsumowanie

W rozdziale pokazaliśmy trzy sposoby kodowania informacji za pomocą bitów:

• Kodowanie grafiki

• Kodowanie tekstu

• Kodowanie liczb

Bity dają nieograniczone możliwości kodowania informacji. Jeśli tylko znajdziemy zbiór wiadomości, które chcemy zakodować, a następnie określimy sposoby przypisania tym wiadomościom słówek bitowych, będziemy mogli zakodować je za pomocą bitów i przetwarzać na komputerach. Dlatego bity są tak potężnym narzędziem w rękach informatyków.

Zadania do samodzielnego rozwiązania

link 1

link 2

odp