Login lub e-mail Hasło   

Kody binarne

Odnośnik do oryginalnej publikacji: http://www.i-lo.tarnow.pl/edu/inf/alg/nu(...)ex.html
Historia rozwoju komputerów pokazuje nam, iż system binarny nie został od razu wybrany jako podstawowy system reprezentacji liczb w maszynach cyfrowych. Początkowo kon...
Wyświetlenia: 33.052 Zamieszczono 30/10/2006

Maszyna różnicowa Charlesa Babbage'a

Historia rozwoju komputerów pokazuje nam, iż system binarny nie został od razu wybrany jako podstawowy system reprezentacji liczb w maszynach cyfrowych. Początkowo konstruktorzy próbowali stosować system dziesiętny, ponieważ był im najbliższy i bardziej zrozumiały. Jednakże system ten sprawia wiele kłopotów. Przede wszystkim operuje dziesięcioma symbolami, które należy w jakiś sposób reprezentować w maszynie cyfrowej. Prosta tabliczka dodawania czy mnożenia zawiera sto pozycji. Wszystko to znacznie komplikuje budowę komputera oraz wykonywanie obliczeń.

W latach czterdziestych XX wieku opracowywano teoretyczne podstawy działania maszyn cyfrowych i zwrócono uwagę na system binarny (dwójkowy) (przeczytaj również opracowania o Konradzie Zuse oraz jego komputerach). System ten posiada dwie cyfry - 0 i 1, które w prosty sposób można reprezentować w maszynie cyfrowej za pomocą odpowiednich napięć czy prądów elektrycznych. Układy realizujące operacje na cyfrach binarnych są nieporównywalnie prostsze od analogicznych układów operujących na cyfrach dziesiętnych. Te zalety systemu binarnego przyczyniły się do wybrania go za podstawowy system reprezentacji informacji we współczesnych komputerach.

Claude Shannon

Słówko bit po raz pierwszy pojawiło się w literaturze informatycznej w roku 1948 w pracach znanego teoretyka informatyki Claude'a Shannona, który przyznał, iż zapożyczył ten termin od naukowca Johna Turkey'a (uważa się, iż termin software również wymyślił John). Bit powstał w trakcie drugiego śniadania, gdy John obmyślał zgrabne terminy dla pojęcia cyfry dwójkowej (binary digit):

bit - binary digit,     binit - binary digit, bigit - binary digit

Jak wiemy, terminy binit oraz bigit nie przyjęły się i pozostało krótkie bit. Zatem bit oznacza po prostu cyfrę binarną 0 lub 1. Cóż, trudno o coś bardziej prostego, lecz co nam to daje? W jaki sposób przy pomocy bitów można kodować informację?

Po pierwsze musimy sobie uświadomić, czym tak naprawdę jest informacja. Jest to twór abstrakcyjny, niematerialny (jeśli nie wierzysz, to odpowiedz, ile waży informacja, jaka jest w dotyku, jaki ma kolor, jak smakuje?). Przy komunikacji nie mamy bezpośrednio do czynienia z informacją, lecz z symbolami, którym tę informację przypisujemy. Dla przykładu weźmy język polski. Słowo "samolot" jest tylko ciągiem odpowiednio ze sobą połączonych dźwięków, którym nadaliśmy określone znaczenie. Również pismo to zbiór znaków, linii, które odpowiednio odczytujemy (interpretujemy przypisaną im informację).

Zatem informacja zawarta jest w symbolach - kojarzymy informację z odpowiednimi symbolami takimi jak słowa, pismo, gesty, znaki umowne (wg teorii Shannona z informacją mamy do czynienia zawsze wtedy, gdy występuje przepływ energii od nadawcy do odbiorcy - jest to definicja najbardziej ogólna). Wynika stąd wniosek, iż do przekazywania informacji potrzebujemy symboli - nośników informacji. Takim symbolem może być bit.

Bit przyjmuje dwie postacie, które (również umownie) oznaczamy odpowiednio cyfrą 0 i 1. Wyobraźmy sobie, iż cyfra 0 jest jednym symbolem, a cyfra 1 drugim (bo w rzeczywistości tak jest). Posiadamy zatem dwa symbole, którym możemy nadać dowolne, pożądane znaczenie. Jeden bit pozwoli nam przekazać informację o dwóch różnych zdarzeniach.

 

W pokoju hotelowym zainstalowany jest czujnik pożarowy. Czujnik ten łączy się z centralką za pomocą przewodu. Jeśli w pomieszczeniu jest normalna temperatura, to czujnik nie przesyła przewodem prądu. Zinterpretujmy to jako stan 0 - brak pożaru. Jeśli jednak wykryty zostanie ogień, to czujnik prześle przewodem prąd elektryczny. Zinterpretujmy to jako stan 1 - pożar. Czujnik i centralka komunikują się za pomocą informacji jednobitowej. Ich język składa się tylko z dwóch symboli:

0 - brak pożaru
1 - pożar

Na identycznej zasadzie mogą pracować inne proste urządzenia: czujnik zamkniętych okien lub drzwi, czujnik włączenia świateł w samochodzie, urządzenie włączania oświetlenia nocnego, itp.

   
   
   

Bit przyjmuje dwa stany: 0 i 1. Za pomocą bitu można przekazać dwie różne informacje przypisując je odpowiednio stanowi 0 i 1.

 
       

Lp. b4 b3 b2 b1
1. 0 0 0 0
2. 0 0 0 1
3. 0 0 1 0
4. 0 0 1 1
5. 0 1 0 0
6. 0 1 0 1
7. 0 1 1 0
8. 0 1 1 1
9. 1 0 0 0
10. 1 0 0 1
11. 1 0 1 0
12. 1 0 1 1
13. 1 1 0 0
14. 1 1 0 1
15. 1 1 1 0
16. 1 1 1 1

Jeden bit to za mało, aby efektywnie kodować informację. Na szczęście możemy sobie w prosty sposób poradzić łącząc bity w grupy. Grupę taką traktujemy jak jeden symbol złożony. Poniższa tabelka przedstawia wszystkie symbole 1, 2, 3 i 4 bitowe:

Jeśli słowo binarne złożone jest z jednego bitu, to można z niego zbudować tylko dwa symbole 0 i 1 (kolor różowy w tablicy).

Dwa bity dają nam już cztery różne symbole (kolor zielony): 00, 01, 10 i 11.

Dalej trzy bity pozwalają utworzyć 8 różnych symboli (kolor niebieski), a 4 bity 16 symboli.

Zauważ, iż zwiększenie długości słowa bitowego o jeden bit podwaja liczbę możliwych do utworzenia symboli. Możemy zatem napisać:

Liczba
bitów
Liczba
symboli
Potęga
liczby 2
1 2 = 21
2 4 = 22
3 8 = 23
4 16 = 24
5 32 = 25
6 64 = 26
7 128 = 27
8 256 = 28
... ... ...
16 65536 = 216
... ... ...
32 4294967296 = 232
... ... ...
n 2n = 2n

Wynika stąd prosty wniosek: dla dowolnej skończonej ilości informacji zawsze można dobrać słówka binarne o takiej ilości bitów, aby utworzyć z nich pożądaną liczbę symboli. W ten sposób powstaje kod binarny. Teraz wystarczy otrzymanym symbolom binarnym nadać znaczenia i już możemy ich używać w ten sam sposób, co słów języka polskiego.

   
   
   
  • n bitów tworzy 2n różnych symboli binarnych.

  • do utworzenia n symboli binarnych, gdzie n > 1, potrzebne jest co najmniej [log2(n - 1) + 1] bitów

 
       

Kodowanie grafiki

Załóżmy, iż chcemy zakodować binarnie obrazek pokazany poniżej: Jest on złożony z różnokolorowych punktów, które nazywamy pikselami (z języka ang. picture element - element obrazu, punkt).

               
               
               
               
               
               
               
               

Od razu zauważamy, że punkty są tylko w czterech kolorach. Układamy tablicę kodową kolorów, w której każdemu kolorowi punktu przyporządkujemy jeden symbol dwubitowy:

   - 00
   - 01
   - 10
   - 11

Powiązaliśmy w ten sposób informację z reprezentującymi ją symbolami. Teraz wystarczy już tylko każdy piksel zastąpić symbolem dwubitowym. W tej postaci obrazek może być przechowywany w pamięci komputera, przesyłany przez sieci teleinformatyczne oraz przetwarzany.

00 00 00 00 00 00 00 00 0000000000000000
00 00 11 11 11 11 00 00 0000111111110000
00 11 11 11 11 11 00 00 0011111111110000
00 00 11 11 11 11 11 00 0000111111111100
00 00 00 11 11 00 00 00 0000001111000000
00 00 00 00 10 00 00 00 0000000010000000
00 00 00 00 10 00 00 00 0000000010000000
01 01 01 01 01 01 01 01 0101010101010101

Zwróćmy uwagę na małą czytelność dla ludzi informacji zapisanej w systemie binarnym. Szczególnie, jeśli wszystkie bity zapiszemy w jednym ciągu:

0000000000000000000011111111000000111111111100000000111111111100000000111100000000000000100000000101010101010101

Należy jednak pamiętać o tym, iż system ten jest przeznaczony dla maszyn, które nie nudzą się i nie męczą.


Kodowanie znaków

Zaprojektujemy kod binarny przeznaczony do kodowania małych liter alfabetu łacińskiego.

W tym przypadku wiadomościami będą literki. W alfabecie łacińskim jest ich 26: abcdefghijklmnopqrstuvwxyz. Każda literka musi być kodowana innym symbolem binarnym. Musimy określić zatem niezbędną liczbę bitów tworzących te symbole. W tym celu wykorzystujemy drugi z podanych wzorów i otrzymujemy:

[log2(26 - 1) + 1] = [log225 + 1] = [4,64 + 1] = [5,64] = 5 bitów

5 bitów tworzy 32 symbole. Nam potrzebne jest 26, zatem 6 symboli nie zostanie wykorzystanych. Od przybytku głowa nie boli. Ważne jest, aby symboli nie było mniej niż liczba wiadomości do zakodowania. Więcej w niczym nam nie przeszkadza - nawet lepiej, gdyż w przyszłości będzie można do takiego systemu dodać 6 nowych znaków (np. spacja, przecinek, kropka itp.).

W następnym kroku układamy tabelkę kodu znakowego, w której każdej literce przydzielamy jeden symbol binarny. Po tej operacji można literki przedstawiać jako symbole binarne oraz z symboli binarnych odczytywać literki. Odwzorowanie jest zatem obustronne.

Binarny kod znakowy
Znak Kod Znak Kod Znak Kod Znak Kod
a 00000 h 00111 o 01110 v 10101
b 00001 i 01000 p 01111 w 10110
c 00010 j 01001 q 10000 x 10111
d 00011 k 01010 r 10001 y 11000
e 00100 l 01011 s 10010 z 11001
f 00101 m 01100 t 10011  
g 00110 n 01101 u 10100

Wykorzystując tabelkę kodową zamieńmy na symbole binarne słowo "wagon":

w a g o n
10110 00000 00110 01110 01101

Po połączeniu bitów w jeden ciąg otrzymujemy:

1011000000001100111001101

Dla człowieka zapis ten staje się zupełnie nieczytelny, lecz komputery radzą sobie z nim znakomicie - bity to ich żywioł. Spróbujmy teraz dokonać operacji odwrotnej, tzn. odczytać słowo zakodowane w bitach, które np. otrzymaliśmy za pomocą sieci teleinformatycznej z drugiego końca świata:

1001101110010101100001110

Najpierw rozdzielamy otrzymane bity na grupy pięciobitowe:

10011  01110  01010  11000  01110

Dla każdej grupy bitów (symbolu binarnego) odszukujemy w tabelce kodu odpowiednią literkę:

10011 01110 01010 11000 01110
t o k y o

Chociaż wolno nam tworzyć kody binarne o dowolnej liczbie bitów na symbol, to jednak z technicznego punktu widzenia wygodnie jest przyjąć pewne ustalone jednostki. Standardowe grupy bitów można w prosty sposób przechowywać w pamięciach komputerów, na nośnikach danych oraz przesyłać za pomocą sieci teleinformatycznych.

Bajt  (z ang. byte) jest taką właśnie standaryzacją. Najczęściej przyjmuje się, iż jest to grupa 8 bitów. Komórki pamięci komputera przechowują informację w postaci bajtów. Również wiele urządzeń przystosowane zostało do danych przekazywanych w takiej formie (porcjami po 8 bitów) - np. drukarki, terminale, modemy, dyski elastyczne i twarde, itp. Dlatego bajt stał się kolejną po bicie jednostką informacji. Bajt utożsamiany jest ze znakiem, literą, ponieważ używa się często 8 bitowego kodu do reprezentowania znaków (ASCII - American Standard Code for Information Interchange).

   
   
   

Bajt jest grupą 8 bitów. Oznaczamy go dużą literką B w odróżnieniu od bitu - b. 1B pozwala reprezentować 256 różnych informacji.

 
       

W fizyce i technice stosowane są wielokrotności jednostek podstawowych. Oznaczamy je odpowiednimi przyrostkami kilo, mega, giga i tera. Podstawą tych wielokrotności jest liczba 10:

kilo = 1000 = 103  
mega  = 1000000 = 106 = kilo 1000
giga = 1000000000 = 109 = mega 1000
tera = 1000000000000  = 1012  = giga 1000

W systemie binarnym, ze względu na podobieństwo, zastosowano również podobne mnożniki, jednakże podstawą ich jest liczba 2, nie 10, gdyż tak jest dużo wygodniej (pod koniec tego opracowania zrozumiesz dlaczego). Starano się przy tym, aby mnożnik binarny był jak najbliższy odpowiednikowi dziesiętnemu. I tak otrzymano:

Kilo = 1024 = 210  
Mega  = 1048576 = 220 = Kilo 1024
Giga = 1073741824 = 230 = Mega 1024
Tera = 1099511627776  = 240  = Giga 1024

Dla odróżnienia mnożników binarnych od dziesiętnych zapisujemy je dużą literką. Jednostki binarne dzielimy na bitowe (podstawą jest bit) oraz bajtowe (podstawą jest bajt).

Jednostki binarne
bitowe bajtowe
b bit B bajt
Kb kilobit KB kilobajt
Mb megabit MB megabajt
Gb gigabit GB gigabajt
Tb terabit TB terabajt

   
   
   

Podstawą mnożników binarnych jest liczba 2, a nie 10. Więc zamiast 1000 = 103 stosujemy 1024 = 210.

 
       

   
   
   

Poniższe, przykładowe programy są praktyczną realizacją omawianego w tym rozdziale algorytmu. Zapewne można je napisać bardziej efektywnie. To już twoje zadanie. Dokładny opis stosowanych środowisk programowania znajdziesz we wstępie. Programy przed opublikowaniem w serwisie edukacyjnym zostały dokładnie przetestowane. Jeśli jednak znajdziesz jakąś usterkę (co zawsze może się zdarzyć), to prześlij o niej informację do autora. Pozwoli to ulepszyć nasze artykuły. Będziemy Ci za to wdzięczni.

 
       

Program generuje wszystkie słowa binarne możliwe do utworzenia z zadanej ilości bitów. Ilość bitów nie jest ograniczona, jednakże pamiętajcie, iż wygenerowanie wszystkich, długich słów binarnych może zająć sporo czasu (nawet kilka wieków!!!).

Wydruk z uruchomionego programu
 Generacja kodów binarnych
o zadanej liczbie bitów
---------------------------
(C)2005 mgr Jerzy Wałaszek
I LO w Tarnowie

Podaj liczbę bitów n = 3

000
001
010
011
100
101
110
111

KONIEC. Naciśnij dowolny klawisz...
Microsoft Visual Basic 2005 Express Edition

 

Borland
Delphi 7.0
Personal
Edition
// Program generuje wszystkie słowa binarne
// o zadanej liczbie bitów
//-----------------------------------------
// (C)2005 mgr Jerzy Wałaszek
// I Liceum Ogólnokształcące
// im. K. Brodzińskiego
// w Tarnowie
//-----------------------------------------

program bincode;

{$APPTYPE CONSOLE}

var
s : string;
i,n,p : integer;
begin
writeln(' Generacja kodow binarnych');
writeln(' o zadanej liczbie bitow');
writeln('---------------------------');
writeln('(C)2005 mgr Jerzy Walaszek');
writeln(' I LO w Tarnowie');
writeln;
write('Podaj liczbe bitow n = '); readln(n);
writeln;
if n > 0 then
begin

s := '';
for i := 1 to n do s := s + '0';
while true do
begin

writeln(s);
i := length(s); p := 1;
repeat
if
p = 1 then
case
s[i] of
'0' : begin
s[i] := '1';
p := 0;
end;
'1' : s[i] := '0';
end;
dec(i);
until (p = 0) or (i = 0);
if p = 1 then break;
end;
end
else
writeln('Zla liczba bitow');
writeln;
writeln('Nacisnij klawisz Enter...'); readln;
end.
Borland
C++ Builder
6.0
Personal
Edition
// Program generuje wszystkie słowa binarne
// o zadanej liczbie bitów
//-----------------------------------------
// (C)2005 mgr Jerzy Wałaszek
// I Liceum Ogólnokształcące
// im. K. Brodzińskiego
// w Tarnowie
//-----------------------------------------

#include <iostream>
#include <string>

using namespace std;

main()
{
string s;
int i,n,p;
char z[1];

cout << " Generacja kodow binarnych\n"
" o zadanej liczbie bitow\n"
"---------------------------\n"
"(C)2005 mgr Jerzy Walaszek\n"
" I LO w Tarnowie\n\n"
"Podaj liczbe bitow n = "
;
cin >> n;
cout << endl;
if(n > 0)
{
s = "";
for(i = 1; i <= n; i++) s += '0';
while(true)
{
cout << s << endl;
i = s.length(); p = 1;
do
{
if(p)
switch(s[i-1])
{
case '0' : s[i-1] = '1'; p = 0; break;
case '1' : s[i-1] = '0'; break;
};
i--;
} while(p && i);
if(p) break;
};
}
else cout << "Zla liczba bitow\n";
cout << "\nNacisnij ENTER...\n";
cin.getline(z,1);
cin.getline(z,1);
}
Microsoft
Visual
Basic 2005
Express
Edition
' Program generuje wszystkie słowa binarne
' o zadanej liczbie bitów
'-----------------------------------------
' (C)2005 mgr Jerzy Wałaszek
' I Liceum Ogólnokształcące
' im. K. Brodzińskiego
' w Tarnowie
'-----------------------------------------

Option Explicit On

Module
Module1

Sub Main()

Dim s As String
Dim
i, n As Integer
Dim
p As Boolean

Console.WriteLine(" Generacja kodów binarnych")
Console.WriteLine(" o zadanej liczbie bitów")
Console.WriteLine("---------------------------")
Console.WriteLine("(C)2005 mgr Jerzy Wałaszek")
Console.WriteLine(" I LO w Tarnowie")
Console.WriteLine()
Console.Write("Podaj liczbę bitów n = ") : n = Val(Console.ReadLine)
Console.WriteLine()
If n > 0 Then
s = ""
For i = 1 To n : s += "0" : Next
Do

Console.WriteLine(s)
i = s.Length() : p = True
Do
If
p Then
If
s.Chars(i - 1) = "0" Then
Mid
(s, i, 1) = "1" : p = False
Else
Mid
(s, i, 1) = "0"
End If
End If

i = i - 1
Loop Until (Not p) Or (i = 0)
If p Then Exit Do
Loop
Else

Console.WriteLine("Zła liczba bitów")
End If
Console.WriteLine()
Console.WriteLine("KONIEC. Naciśnij dowolny klawisz...")
Console.ReadLine()

End Sub

End Module
Python
# -*- coding: cp1250 -*-
# Program generuje wszystkie słowa binarne
# o zadanej liczbie bitów
#-----------------------------------------
# (C)2005 mgr Jerzy Wałaszek
# I Liceum Ogólnokształcące
# im. K. Brodzińskiego
# w Tarnowie
#-----------------------------------------

print " Generacja kodow binarnych"
print " o zadanej liczbie bitow"
print "---------------------------"
print "(C)2005 mgr Jerzy Walaszek"
print " I LO w Tarnowie"
print
n = int(raw_input("Podaj liczbe bitow n = "))
print
if
n:
s = "";
for i in range(n): s += "0"
while True:
print s
i = len(s) - 1; p = 1
while p and (i >= 0):
if p == 1:
if s[i] == "0":
s = s[:i] + "1" + s[i + 1:]
p = 0
else:
s = s[:i] + "0" + s[i + 1:]
i -= 1
if p == 1: break
else
: print "Zla liczba bitow"
print
raw_input
("Nacisnij klawisz Enter...")
JavaScript
<html>
<head>
</head>
<body>
<div align=
"center">
<form style=
"BORDER-RIGHT: #ff9933 1px outset; PADDING-RIGHT: 4px;
BORDER-TOP: #ff9933 1px outset; PADDING-LEFT: 4px;
PADDING-BOTTOM: 1px; BORDER-LEFT: #ff9933 1px outset;
PADDING-TOP: 1px; BORDER-BOTTOM: #ff9933 1px outset;
BACKGROUND-COLOR: #ffcc66"
name="frmbincode">
<h3 style=
"text-align: center">
Generacja kodów binarnych<br>
o zadanej liczbie bitów
</h3>
<p style=
"TEXT-ALIGN: center">
(C)2005 mgr Jerzy Wałaszek&nbsp;&nbsp; I LO w Tarnowie
</p>
<hr>
<div align=
"center">
<table border=
"0" cellpadding="4" style="border-collapse: collapse">
<tr>
<td align=
"right">Liczba bitów n = </td>
<td>
<input value=
"3" name="inp_n" size="20" style="text-align: right">
</td>
<td>
<input onclick=
"main();" type="button" value="Generuj" name="B1">
</td>
</tr>
</table>
</div>
<p id=
"out_t" style="TEXT-ALIGN: center">...</p>
</form>

<script language=
javascript>

// Program generuje wszystkie słowa binarne
// o zadanej liczbie bitów
//-----------------------------------------
// (C)2005 mgr Jerzy Wałaszek
// I Liceum Ogólnokształcące
// im. K. Brodzińskiego
// w Tarnowie
//-----------------------------------------

function main()
{
var s,t,i,n,p;

n = parseInt(document.frmbincode.inp_n.value);
if(!isNaN(n))
{
t = s = "";
for(i = 1; i <= n; i++) s += '0';
while(true)
{
t += s + " ";
i = s.length; p = 1;
do
{
if(p)
switch(s.charAt(i-1))
{
case '0' : s = s.substr(0,i-1) + '1' + s.substring(i,s.length);
p = 0; break;
case '1' : s = s.substr(0,i-1) + '0' + s.substring(i,s.length);
break;
};
i--;
} while(p && i);
if(p) break;
};
}
else t = "<font color=red><b>Złe dane wejściowe</b></font>";
document.getElementById("out_t").innerHTML = t;
}

</script>
</div>
</body>
</html>

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.

Podobne artykuły


8
komentarze: 79 | wyświetlenia: 943
111
komentarze: 32 | wyświetlenia: 60401
54
komentarze: 56 | wyświetlenia: 32410
54
komentarze: 68 | wyświetlenia: 31147
50
komentarze: 27 | wyświetlenia: 63284
49
komentarze: 18 | wyświetlenia: 64796
39
komentarze: 30 | wyświetlenia: 28636
39
komentarze: 50 | wyświetlenia: 23130
37
komentarze: 9 | wyświetlenia: 28357
36
komentarze: 37 | wyświetlenia: 23203
34
komentarze: 21 | wyświetlenia: 26228
32
komentarze: 76 | wyświetlenia: 12380
 
Autor
Artykuł

Powiązane tematy





Artykuł bardzo ciekawy - acz zdjęcie Claude'a Shannona się nie wyświetla. Pewnie było zaciągnięte z innej witryny ale ta padła lub przeadresowała fotke:( Bywa. To znowu mam szczęście żeby ciekawy artykuł wykopać oceną do katalogu:) Bo system binarny bardzo potrzebny dla kompika:)

  Bambus®  (www),  22/03/2009

http://chomikuj.pl/bambus1994/(...)den.rar tutaj jest program do pobrania który koduje prawie wszystkie znaki na system binarny 6-o bitowy.



Dodaj swoją opinię
W trosce o jakość komentarzy wymagamy od użytkowników, aby zalogowali się przed dodaniem komentarza. Jeżeli nie posiadasz jeszcze swojego konta, zarejestruj się. To tylko chwila, a uzyskasz dostęp do dodatkowych możliwości!
 

© 2005-2018 grupa EIOBA. Wrocław, Polska