Kodowanie informacji

Kodowanie informacji

Kod [łac.], ciąg składników

sygnału (kombinacji sygnałów

elementarnych, np. kropek i

kresek, impulsów prądu,

symboli) oraz reguła ich

przyporządkowania

składnikom wiadomości (np.

znakom pisma);

Kody otwarte i zamknięte

• Kod otwarty jest to jednoklasowy

system znaków, do którego ciągle
można wprowadzać nowe elementy

• Kod zamknięty jest to jednoklasowy

system znaków, do którego nie można
wprowadzać nowych elementów.

Przykładem kodu zamkniętego jest

alfabet.

• Louis Braille (1809 - 1852)

opracował wypukły alfabet
dla

niewidzących

jako

szesnastoletnie dziecko na
podstawie

szyfru

wojskowego.

Symbole

brajlowskie

tzw

„sześciopunkty. Sześciopunkt
to  dwie  kolumny  punktów,  z
których  każdy  ma  swój
numer.  Od  góry  ku  dołowi  w
lewej kolumnie od 1 do 3 i w
prawej  kolumnie  od  4  do  6
(czyli  literę  „a”  oznacza
punkt  „1”,  zaś  literę  „b”
punkty „1” oraz „2”).

Reguły alfabetu Braill’a

• I. Pierwszy rząd znaków, punkty: „1”,”2”,”4”,”5”; jest

podstawą alfabetu.

• II. Drugi rząd (k-t) jest powtórzeniem rzędu pierwszego

z dodaniem punktu „3”.

• III. Trzeci rząd (u-]) jest powtórzeniem rzędu pierwszego

z dodaniem punktów „3” i „6”.

• IV. Czwarty rząd (ą-w) jest powtórzeniem rzędu

pierwszego z dodaniem punktu „6”.

• V. Piąty rząd (znaki przestankowe) jest powtórzeniem

rzędu pierwszego „opuszczonego” o jeden punkt

(zbudowany na punktach 2,3,4,5).

• VI. Szósty rząd to dwa górne znaki prawostronne (4i5),

które ulegają takim samym modyfikacjom jak rząd 1.

• VII. Siódmy rząd zawierza trzy znaki oparte na

punktach dolnych (3i6) oraz „pusty sześciopunkt.

Kod Baudot ( Émile

Baudot)

• Kod jest zestawem znaków używanych w

dalekopisach, był pierwowzorem kodów EBCDIC

oraz ASCII.

• Oryginalny kod Baudot powstał około roku 1874 i

znany jest jako International Telegraph Alphabet No

1 (ITA1), i nie był już więcej używany.

• Około roku 1901 kod Baudot został zmodyfikowany

przez

Donalda Murraya

. Kolejne modyfikacje zrobił

Western Union

. Od tego czasu kod Baudot nosi

nazwę International Telegraph Alphabet No 2

(ITA2). ITA2 jest wciąż używany między innymi w

telekomunikacyjnych urządzeniach dla

głuchoniemych

TDD

i w krótkofalarstwie jako RTTY.

Donald Murray

•

Donald Murray, dziennikarz z Nowej Zelandii,
zmodyfikował system Baudota, łącząc go z
linotypem do odlewania czcionek, co umożliwiło
skład gazet na odległość. "Fortepianowe" klawisze,
wymagające dużej wprawy w bezpośrednim
kodowaniu znaków, zostały zastąpione klawiszami
dla poszczególnych znaków, jak w maszynie do
pisania.

•

Zastosowanie Kodu Murray’a dało początek
dziennikom o zasięgu krajowym, drukowanym i
dystrybuowanym co rano równocześnie w wielu
miastach

Kiedy to się zaczęło...?

Właściwie wtedy, gdy zaczęto kodować ... np.



Alfabet Braile’a (poziom 2).

6 bitów (czyli 64 możliwości)

wykorzystane do kodowania liter, cyfr i znaków przestankowych,

oraz... najczęściej występujących krótkich słów:

and



Kod Baudota.

Kod do komunikacji telegraficznej: 5 bitów, ale

jedno ze słów kodowych pozwala na przełączanie między

literami i „obrazkami” (obrazki to cyfry, znaki przestankowe,

kody sterujące, operatory arytmetyczne). W wyniku kodujemy

nie 32 elementy lecz 64, i liczymy na to, że przełączanie

występuje rzadko....

• Kody generowane były

dwoma palcami lewej i
trzema palcami prawej rąki,
za pomocą klawiszy
przypominających
fortepianowe, w rytm sygnału
dźwiękowego, co wymagało
pewnej wprawy.

• Przełomowe znaczenie

konstrukcji Baudota polegało
na tym, że przewidywała ona
tylko dwa stany elektryczne:
istnienie lub brak napięcia,
interpretowanych niezależnie
od czasu trwania takich
zmian.

Kodowanie Huffmana

• Kodowanie Huffmana to jedna z najprostszych i

łatwych w implementacji metod kompresji

bezstratnej. Została opracowana w 1952 roku przez

Amerykanina Davida Huffmana.

• Algorytm Huffmana nie należy do

najefektywniejszych systemów bezstratnej

kompresji danych, dlatego też praktycznie nie

używa się go samodzielnie. Często wykorzystuje się

go jako ostatni etap w różnych systemach

kompresji, zarówno bezstratnej jak i stratnej, np.

MP3 lub JPEG. Pomimo, że nie jest doskonały,

stosuje się go ze względu na prostotę oraz brak

ograniczeń patentowych

Kodowanie.

Kodowanie o stałej długości:

• Każde słowo kodowe ma tę samą długość

np. K(a)=

0001

, K(b)=

0010

, K(c) musi mieć 4

bity

Kodowanie o zmiennej długości:

• Słowa kodowe mogą mieć różne długości

np. K(a)=

0001

, K(b)=

100

Kodowanie jednoznaczne

• Po zakodowaniu słowa

do postaci

można je

odkodować tylko na jeden sposób, uzyskując

Kod ASCII (17.06. 1963)

• ASCII [aski] ( American Standard Code for

Information Interchange) - 7-bitowy kod

przyporządkowujący liczby z zakresu 0-127 literom

(alfabetu angielskiego), cyfrom, znakom

przestankowym i innym symbolom oraz poleceniom

sterującym. Przykładowo litera "a" jest kodowana

liczbą 97, a polecenie "powrót karetki" – liczbą 13.

• Litery, cyfry oraz inne znaki drukowane tworzą zbiór

znaków ASCII. Jest to 95 znaków o kodach 32-126.

Pozostałe 33 kody (0-31 i 127) to tzw. kody sterujące

służące do sterowania urządzeniem odbierającym

komunikat, np. drukarką czy terminalem.

Kod ASCII

sterowanie

transmisją

cyfry, interpunkcja i

inne
sterujące i kontrolne

sterowanie

urządzeniami
formatowanie

przekazu
separatory

informacji
wielkie i małe litery
nieznaczące oraz

spacja

Nie-pozycyjny kod Gray’a

• Podstawową cechą wyrazów kodu Gray'a jest

to, iż każde dwa kolejne wyrazy

(również

pierwszy i ostatni)

różnią się od siebie stanem

tylko jednego bitu.

• 1 bitowy kod Gray'a : 0 1
• 2 bitowy kod Gray'a :00 01 11 10
• 3 bitowy kod Gray'a :

000 001 011 010 110 111 101 100

Kodowanie naturalne

binarne

• Tarcza kodowa. Kod naturalny

binarny .

Załóżmy, iż jasny pas odczytujemy

jako zero, a pas czarny jako 1. Na
powyższym rysunku tarcza
kodowa zwraca zatem kod 010 →
2. Stan ten jest ustabilizowany. Co
jednak się stanie, gdy tarcza
zacznie się obracać: nieuchronne
niedokładności w układzie
mechanicznym oraz parametry
obwodów optycznych spowodują,
że nie otrzymamy ładnego
przejścia kodu 011 → 3 w 100 → 4.
Zwróć uwagę, iż na tej granicy
zmieniają się wszystkie bity
słówka kodowego

Kodowanie binarne Gray’a

• Tarcza kodowa, nie

pozycyjny kod Gray’a

W tym przypadku

niepewność

kodowania może

dotyczyć tylko

jednego bitu - albo

otrzymamy kod

poprzedni, albo kod

następny - nie będzie

natomiast błędnych

odczytów pośrednich.

Algorytm

• Algorytm – w matematyce oraz informatyce

to skończony, uporządkowany ciąg jasno
zdefiniowanych czynności, koniecznych do
wykonania pewnego zadania. Słowo
"algorytm" pochodzi od nazwiska
Muhammed ibn Musa Alchwarizmi (دبع وبأبو عبد

يمزراوخلااا ىسوم ناااب دمح م هللااا) matematyka

perskiego z IX wieku i początkowo
oznaczało w Europie sposób obliczeń oparty
na dziesiętnym systemie liczbowym

Algorytm w matematyce

Algorytm to jednoznaczny przepis

przetworzenia w skończonym czasie
pewnych danych wejściowych do pewnych
danych wynikowych.

Zazwyczaj przy analizowaniu bądź

projektowaniu algorytmu zakłada się, że
dostarczane dane wejściowe są poprawne,
czasem istotną częścią algorytmu jest nie
tylko przetworzenie ale i weryfikacja
danych

Algorytm w informatyce

Komputery przetwarzają przekazywane im informacje

z wykorzystaniem algorytmów. Program jest

algorytmem zapisanym w języku zrozumiałym dla

maszyny (asemblerze). Każdy kod maszynowy da się

przełożyć na zestaw instrukcji dla teoretycznego

modelu komputera - maszyny Turinga.

Zwykle algorytmy pracują na danych wejściowych i

uzyskują z nich dane wyjściowe. Informacje

zapisane w pamięci maszyny traktuje się jako jej

stan wewnętrzny. Niektóre algorytmy mają za
zadanie wyłącznie przeprowadzanie komputera

jednego stanu wewnętrznego do innego.

Euklides „Elementy”

• Elementy (

gr.

Στοιχεῖα,

Stoicheia) – jedno z

najsłynniejszych dzieł

naukowych w historii ludzkości,

pochodzący z III wieku p.n.e.

traktat arytmetyczny i

geometryczny, obejmujący

swym zakresem podstawowe

zagadnienia obu tych nauk.

Elementy ukształtowały sposób

myślenia o teoriach

matematycznych i stały się

wzorcem do naśladowania w

wielu dziedzinach nauki. Są

klasycznym przykładem metody

dedukcyjnej i świadectwem siły

rozumowania formalnego

opartego na logice.

Maszyna Turinga

• Przebywając w Cambridge Turing napisał swoją

prawdopodobnie najważniejszą pracę matematyczną On
Computable Numbers czyli O liczbach obliczalnych. To
właśnie w niej wprowadził abstrakcyjną maszynę, która była
w stanie wykonywać zaprogramowaną matematyczną
operację czyli tak zwany algorytm. Maszyna mogła wykonać
jednak tylko jeden, określony algorytm, na przykład mogła
podnieść liczbę do kwadratu, podzielić, dodać, odjąć. Według
Turinga liczby miały być podawane maszynie za pomocą
papierowej taśmy podobnej do taśmy z melodią zapisaną dla

pianoli

. W swojej pracy Turing opisał wiele takich maszyn,

które uzyskały wspólne miano maszyn Turinga. Następnie
Turing opracował tak zwaną uniwersalną maszynę Turinga,
która w zależności od instrukcji zapisanej na taśmie, miała
wykonywać dowolną operację

Maszyna Turinga

Maszyna Turinga składa się z nieskończenie długiej

taśmy podzielonej na pola. Taśma może być

nieskończona jednostronnie lub obustronnie.

Każde pole może znajdować się w jednym z N

stanów. Maszyna zawsze jest ustawiona nad

jednym z pól i znajduje się w jednym z M stanów.

Zależnie od kombinacji stanu maszyny i pola

maszyna zapisuje nową wartość w polu, zmienia

stan, a następnie może przesunąć się o jedno pole

w prawo lub w lewo. Taka operacja nazywana jest

rozkazem. Maszyna Turinga jest sterowana listą

zawierającą dowolną ilość takich rozkazów. Liczby

N i M mogą być dowolne, byle skończone

Maszyna Turinga

MT= <Q, S, , , q

, , F>

Gdzie:
 q

,......q

Q skończony dopuszczalny zbiór stanów

maszyny,

 s

1,..............

S

zbiór symboli wejściowych maszyny,

                               funkcja ( instrukcja).
                               skończony zbiór dopuszczalnych symboli,
        q

stan początkowy,

                         symbol pusty,
        F                       zbiór stanów końcowych,
Instrukcja Maszyny Turinga:

                                   (s

, L/R)

Von Neumann

• John von Neumann (ur. 28

grudnia 1903 w

Budapeszcie, zm. 8 lutego

1957 w Waszyngtonie),

inżynier chemik, fizyk,

matematyk i informatyk.

Wniósł znaczący wkład do

wielu dziedzin matematyki,

szczególnie teorii gier i

uporządkował formalizm

matematyczny mechaniki

kwantowej. Uczestniczył w

projekcie Manhattan.

Przyczynił się do rozwoju

numerycznych prognoz

pogody.

Architektura von

Neumanna

Architektura von Neumanna - rodzaj architektury

komputera, przedstawionej po raz pierwszy w 1945

roku przez von Neumanna stworzonej wspólnie z

Johnem W. Mauchly'ym i Johnem Presper Eckertem .

Mauchly i Eckert oskarżali von Neumanna o przywłaszczenie wspólnych wyników prac.

Sam von Neumann uważał ich pracę za dzieło zbiorowe o licencji public domain

(projekt był współfinansowany przez rząd amerykański).

Polega na ścisłym podziale komputera na trzy

podstawowe części:

• Procesor (w ramach którego wydzielona bywa część

sterująca oraz część arytmetyczno-logiczna)

• pamięć komputera (zawierająca dane i sam program)
• urządzenia wejścia/wyjścia

Architektura von Neumana

• System komputerowy zbudowany w oparciu o

architekturę von Neumanna powinien:

• mieć skończoną i funkcjonalnie pełną listę rozkazów
• mieć możliwość wprowadzenia programu do systemu

komputerowego poprzez urządzenia zewnętrzne i prze-

chowywanie w pamięci w sposób identyczny jak danych

• dane i instrukcje w takim systemie powinny być

jednakowo dostępne dla procesora

• Informacja jest tam przetwarzana dzięki sekwencyjnemu

odczytywaniu instrukcji z pamięci komputera i

wykonywaniu tych instrukcji w procesorze.

• Podane warunki pozwalają przełączać system

komputerowy z wykonania jednego zadania (programu)

na inne bez fizycznej ingerencji w strukturę systemu, a

tym samym gwarantują jego uniwersalność.

Architektura von Neumana

W 1945 Von Neumann opublikował książkę: "First Draft of a

Report on the EDVAC", opisującą architekturę Von Neumanna.

System komputerowy von Neumanna nie

posiada oddzielnych pamięci do

przechowywania danych i instrukcji.

Instrukcje jak i dane są zakodowane w

postaci liczb. Bez analizy programu trudno

jest określić czy dany obszar pamięci zawiera

dane czy instrukcje. Wykonywany program

może się sam modyfikować traktując obszar

instrukcji jako dane, a po przetworzeniu tych

instrukcji - danych - zacząć je wykonywać.

Architektura Von Neumanna

PROCESOR (CPU)
1.

Jednostka arytmetyczno-logiczna ALU-wyposażona w
zestaw rejestrów Blok wstępnego pobierania i
dekodowania instrukcji.

Zapewnia ona prawidłowe przetworzenie wszystkich
danych stałoprzecinkowych.

FPU(Floating Point Unit) czyli koprocesor wykonujący
wszystkie obliczenia zmiennoprzecinkowe .

Moduł wyjściowy procesora. Jego zadaniem jest
sterowanie strumieniem informacji np. do
odpowiedniego adresu w pamięci operacyjnej lub
urządzenia wejścia/wyjścia.

Architektura Von Neumanna

PAMIĘĆ :
• RAM (ang. Random Access Memory) - zwana też

pamięcią użytkownika lub pamięcią o dostępie
swobodnym.

W pamięci RAM przechowywane są. Zawartość pamięci

RAM, którą są aktualnie wykonywane programy i dane dla
tych programów, oraz wyniki ich pracy jest tracona w
momencie zaniku napięcia zasilania.

• ROM (ang. Read-Only Memory - pamięć tylko do odczytu)

Jest to rodzaj pamięci operacyjnej urządzenia
elektronicznego, w szczególności komputera. Zawiera ona
stałe dane potrzebne w pracy urządzenia - np. procedury
startowe komputera, czy próbki przebiegu w cyfrowym
generatorze funkcyjnym.

Architektura harwardzka

Architektura harwardzka - rodzaj architektury komputera. W

odróżnieniu od architektury von Neumanna, pamięć danych
programu jest oddzielona od pamięci rozkazów. Prostsza (w
stosunku do architektury von Neumanna) budowa przekłada
się na większą szybkość działania - dlatego ten typ
architektury jest często wykorzystywany w procesorach
sygnałowych oraz przy dostępie procesora do pamięci cache

Separacja pamięci danych od

pamięci rozkazów

sprawia, że

architektura harwardzka jest obecnie powszechnie stosowana
w mikrokomputerach jednoukładowych , w których dane
programu są najczęściej zapisane w nieulotnej pamięci ROM
(EPROM/EEPROM), natomiast dla danych tymczasowych
wykorzystana jest pamięć RAM (wewnętrzna lub zewnętrzna).

Języki Programowania

•

Początkowo proces programowania polegał na

zapisywaniu wszystkich algorytmów w języku
maszynowym a więc zdeterminowa-nym fizyczną
realizacją hardware’u komputera. Lista rozkazów
maszynowych nie jest długa. Rozkazy można podzielić
na 3 kategorie:

• -         przesyłanie danych
• -         operacje arytmetyczno-logiczne
• -         rozkazy sterujące

Języki programowania - przykład

• Zakładamy, że wartości „ceny” i „podatku”

zapisane będą w pamięci pod adresami 6C

HEX

(01101100)

BIN

i 6D

HEX

(01101101)

BIN

w notacji

uzupełnieniowej do dwóch. Suma ma zostać
umieszczona w pamięci pod adresem 6E
(01101111).Struktura umownego komputera ma
postać jak poprzednio

Języki programowania – język wewnętrzny

(przykład)

Krok 1. 156C (przesłanie danej

z adresu 6C do rejestru 5)

Krok 2. 166D (przesłanie danej

z adresu 6D do rejestru 6)

Krok 3. 5056 (sumowanie

danych z rejestru 5 i 6, wynik
w rejestrze0)

Krok 4. 306E (przesłanie sumy

do komórki 6E)

Krok 5. C000 (stop)

Języki programowania – asembler

• Asembler – korzysta z kodów mnemotechnicznych (mnemonicz
nych) do przedstawiania zadań odnoszących się bezpośrednio

do sprzętu.

• Kod mnemotechniczny to łatwe do zapamiętania słowo lub

skrót, który przedstawia całe zadanie dla mikroprocesora.
Np.
MOV (move – przesuń) przemieść lub przesuń informację z

jednego miejsca pamięci w inne.
JMP   (jump – skocz) przejdź do innego miejsca w pamięci
MUL  (multiplay – mnóż) mnóż zawartość akumulatora,
   przez zawartość wyszczególnionego rejestru
RET   (return – wróć) powróć z podprogramu do progra-
   mu głownego.
SETB (set bit – ustaw bit) wstaw wartość „1” na pozycji

bezpośrednio zaadresowanej

Języki programowania – asembler (przykład)

LD R5, CENA

LD R6, PODATEK

ADDI R0, R5, R6

ST R0, SUMA

HLT

Języki programowania – kompilator

• Kompilator – Tłumaczy na raz cały program i

zachowuje go na dysku. Kompilator sprawdza
czy plik źródłowy przygotowany został zgodnie
z regułami danego języka i wspólnie z
konsolidatorem, czyli programem łączącym
zamienia wszystkie instrukcje w ciągi binarne
w języku wewnętrznym procesora (plik
wykonywalny). Przetłumaczony program jest
uruchamiany z pliku wykonywalnego

Języki programowania – kompilator

• Programy kompilowane

zapamiętane w postaci pliku
wykonywalnego działają bez
potrzeby następnej kompilacji, a
więc działają szybko.

•

Języki kompilowane to: C, C

, Pascal, Cobol, Fortran.

Paradygmaty programowania

Paradygmat - w rozumieniu wprowadzonym

przez filozofa Thomasa Kuhna w książce

Struktura rewolucji naukowych (The Structure

of Scientific Revolutions) opublikowanej w

1962 r. - to zbiór pojęć i teorii tworzących

podstawy danej nauki.

Paradygmat

Paradygmat od tzw. dogmatu odróżnia kilka zasadniczych cech:
• nie jest on dany raz na zawsze - lecz jest przyjęty na

zasadzie konsensusu większości badaczy;

• może okresowo ulec zasadniczym przemianom prowadzącym

do głębokich zmian w nauce zwanych rewolucją naukową;

• podważa sens absolutnej słuszności.
Dobry paradygmat posiada kilka cech, i m. in. musi:
• być spójny logicznie i pojęciowo;
• być jak najprostszy i zawierać tylko te pojęcia i teorie, które

są dla danej nauki rzeczywiście niezbędne;

• dawać możliwość tworzenia teorii szczegółowych zgodnych

ze znanymi faktami.

Paradygmat imperatywny

• Programowanie proceduralne to

paradygmat

• programowania zalecający dzielenie kodu na

procedury, czyli fragmenty wykonujące
ściśle określone operacje.

• Procedury nie powinny korzystać ze

zmiennych globalnych (w miarę możliwości),
lecz pobierać i przekazywać wszystkie dane
(czy też wskaźniki do nich) jako parametry
wywołania.

Paradygmat deklaratywny

• Zadanie polega na odkryciu i

zaimplementowaniu ogólnego algorytmu
rozwiązywania problemów. Zadanie
programisty polega na takim precyzyjnym
opisie problemu aby dało się go rozwiązać
wspomnianym ogólnym algorytmem. Z tego
względu języki deklaratywne były językami
opracowanymi dla wąskich zastosowań, np.
symulacji zjawisk ekonomicznych w czasie,
fizycznych w czasie, politycznych w czasie.

Paradygmat funkcyjny

• Program powstaje jako konstruowanie „czarnych

skrzynek” każda pobiera dane wejściowe i
produkuje wyniki. Matematycy takie „skrzynki”
nazywają funkcjami. Konstrukcjami pierwotnymi
języka funkcyjnego są funkcje elementarne, z
których programista tworzy bardziej złożone
funkcje. Paradygmat funkcyjny wymusza
konstruowanie programów w sposób modularny,
programy traktuje się jak funkcje i konstruuje
dla innych funkcji. Informatycy uważają, że jest
to najlepsza metoda konstruowania dużych
pakietów oprogramowania.

Paradygmat obiektowy

• Dane traktuje się jako aktywne „obiekty” a nie pasywne

jednostki jak w paradygmacie imperatywnym. W podejściu
obiektowym obiekt zawiera zbiór danych oraz kompletny
zestaw procedur obsługujących te dane:

• - każdy obiekt implementuje się jako oddzielny dobrze

określony moduł,

• - raz zdefiniowany obiekt można wykorzystać gdy

potrzebny jest nowy jego egzemplarz,

• - zdefiniowane obiekty można włączać do bibliotek

programowych, z których można konstruować nowe systemy
oprogramowania,

• komunikacja między obiektami odbywa się na zasadzie

przesyłania komunikatów – techniki podstawowej w sieciach
komputerowych, implementacja takiego systemu obiektów o
zasięgu ogólnosieciowym jest celem otwartego

systemu

CORBA (Common Object Request Broker Architecture

Paradygmat obiektowy

Np. Listę osób w podejściu

imperatywnym traktuje się jako zbiór
danych,

w podejściu obiektowym lista jest

obiektem zawierającym listę osób wraz
z procedurami obsługi, wstawianie
nowych danych, sortowanie,
sprawdzanie zawartości, usuwanie
elementu itp.

Document Outline