Artikel
Grundlagen - Datenstrukturen


Rubrik:
Grundlagen

Typ:
Zusammenfassung

Stand:
abgeschlossen

Stichworte:
Datenverarbeitung, Datentypen, Zahlensysteme, Datenformat, Umrechnung von Zahlensystemen, Typen, Ganzzahlen, Gleitkommazahlen, Speicherorganisation, binäre Daten, Befehle, Dateien, Datenkompression, Datenverschlüsselung
 
 
 
Inhalt

1.1 Definition
1.2 Datenverarbeitung
1.3 Datenformat
   1 Zahlen
     1 Umrechnung von Zahlensystemen
       a) Horner Verfahren
       b) Restverfahren
     2 Typen
       a) Ganzzahlen
       b) Gleitkommazahlen
       c) Andere Typen
3.4 Speicherorganisation
   1 binäre Daten
   2 Befehle
3.5 Dateien
3.6 Datenkompression
3.7 Datenverschlüsselung



1.1 Definition

Daten: Objekte die zu verarbeiten sind.
 
Nachricht: Aus Symbolen/Zeichen zusammengesetzte Menge (Folge von Binärzeichen bei Computern)
Nachrichten werden durch Signale(analog/digital) physikalisch dargestellt.
 
Information:  Durch Anwendung einer Interpretationsregel aus Nachrichten gewonnen.Die abstrakte Information wird durch die konkrete Nachricht übertragen.
 

BSP: Zeichen/Symbolvorrat : a, b, c, ... (Alphabet) Nachricht : "H", "a", "l", "l", "o" Interpretationsregel : deutsche Sprache => INFORMATION : "Hallo"

Exkurs:
  • ANALOGE SIGNALE:
    kontinuierliche Zuordnung einer physikalischen Größe (beliebige Zwischenwerte)
  • DIGITALE SIGNALE:
    endliche Zahl von Möglichkeiten einer physikalischen Größe


1.2 Datenverarbeitung

Computer (Beispiel für eine mögliche Definition):
Jedes Gerät zur
  1. Dateneingabe
  2. Datenverarbeitung
  3. Datenausgabe
[Computer System = Hardware + Software]
 
BSP: Basic Programm 10 INPUT Name$ ' Eingabe 20 LET Name$ = "Hallo " + Name$ ' Verarbeitung 30 PRINT Name$ ' Ausgabe

Bedingung:
Daten müssen in binärer Form vorliegen um verarbeitet zu werden.
Eingabe -------------> Verarbeitung -------------> Ausgabe Kodierung Dekodierung z.B. [Tastatur] [Screen] "A" -------------> 65 + 1 -------------> "B" ASCII ASCII
Die Kodierung ist die Interpretationsregel für Computernachrichten.


EXKURS: Genormte Zeichensätze


ASCII (USASCII)

1953 U.S./AT&T Teletype code
  • 64 Positionen (codes 32-95), Großteils dem heutigen ASCII entsprechend
1963 ASCII (American Standard Code for Information Interchange)
  • Genormt als 7-Bit Zeichensatz für den Fernschreibverkehr und Datenaustausch
  • Von den 128 Positionen wurden nur 100 genutzt (nur Großbuchstaben)
1965 ECMA-6 (European Computer Manufacturers Association, Genf)
  • Entsprach ASCII allerdings wurde er um Kleinbuchstaben erweitert
  • 10 Positionen wurden für nationale Sonderzeichen freigehalten
1968 ANSI's X3.4 (American National Standards Association, New York)
  • Der Code wird zum amerikanischen Normenzeichensatz
1974 ISO 646 (International Organization for Standarization, Genf)
  • Er wird internationale Norm
1974 DIN 66003 (Deutsches Institut für Normen)
  • Er wird deutsche Norm

Latin

1981 IBM Codepage 437
  • IBM nutzt das achte Bit und erweitert den ASCII auf 256 Positionen
  • im engeren Sinne kein direkter Latin Vorgänger
1985 ECMA-94
  • 8-Bit Code der westeuropäische Sonderzeichen abdeckt
1986 ISO 8859-1, genannt Latin-1
  • Der Code wird internationale Norm
  • Entspricht IBM Codepage 819 und 850 (Positionen teilw. vertauscht)
  • Ab 1997 weitere Ergänzungen für andere Sprachen (ISO 8859-1 bis 10)
  • In Windows enthalten mit einigen zusätzlichen Zeichen
1986 DIN 66303
  • Er wird deutsche Norm

Unicode (UCS)

1987 Unicode (UCS)
  • Von Xerox entwickelt, erweitert von Apple u.a.
  • 16 Bit (65469 Positionen) Code der Schriftzeichen aller Welt aufnehmen soll
  • z.Z. nur von WindowsNT, Linux u. Java verwendet
1992 ISO/IEC 10646-1
  • 32 Bit, Position 0-65469 entsprechen Unicode
  • Der Code wird internationale Norm


1.3 Datenformat

Allgemein: In binärer Form.

BSP: Einheiten 1 Bit = 2 Zahlen 1 Byte = 8 Bit = 256 Zahlen 1 KByte = 1024 Bytes = 8192 Bit = 262144 Zahlen 1 MByte = 1024 KByte ~ 1Million Bytes 1 GByte = 1024 MByte = 1048576 KByte ~ 1Milliarde Bytes

1.3.1 Zahlen

Intern als Bitfolge, dh. im Dualsystem berechnet
(In der Praxis teilweise im Oktal- bzw. Hexadezimalsystem eingegeben)

Umrechnung von Zahlensystemen (allgemein):
Die Umrechnung von Zahlensystemen kann nach verschiedenen Verfahren erfolgen. Hier eine kurze Einführung anhand einiger Beispiele.


1.3.1.1 Umrechnung von Zahlensystemen


a) Horner Verfahren

Horner Schema zur Darstellung von Zahlen:

Formal:

horner.gif


BSP: BSP: Tabellen-/Potenzverfahren 123,45 = ( 1 + ( 2 + ( 3 + ( 4 + 5 * 10^-1 ) * 10^-1 ) * 10^-1 ) * 10^-1 ) = 1*10^2 + 2*10^1 + 3*10^0 + 4*10^-1 + 5*10^-2

Horner Schema zur Umrechnung von Zahlen:

BSP: 13FC,E8 (Hex) = 5116,90625 (Dez)

 13FC  0,E8   
16*1+3  =19  8 :16= 0.5
16*19 +15 =319 (14 +0.5):16= 0.90625
16*319  +12=5116      
     =5116      = 0.90625 

oder

13FC 0,E8
 16+3304+155104+12  0.90625 0.5 
1*1619*16319*165116   14.5:168:16
        
 ===>    <=== 



b) Restverfahren


BSP: 5116,33 (Dez) = 13FC,547AE (Hex) 5116 | ,33 ------------------------+------------------------- 5116 : 16 = 319 Rest C | 0,33 * 16 = 0,28 + 5 319 : 16 = 19 Rest F | 0,28 * 16 = 0,48 + 4 19 : 16 = 1 Rest 3 | 0,48 * 16 = 0,68 + 7 1 : 16 = 0 Rest 1 | 0,68 * 16 = 0,88 + A | 0,88 * 16 = 0,08 + E | usw.


Anmerkung:
Der bei Windows enthaltene Taschenrechner kann verschiedene Zahlensysteme umwandeln.



1.3.1.2 Typen


a) Ganzzahlen (Integer)

Ein Bit wird als Vorzeichen verwendet

BSP: 4 Byte ermöglichen theoretisch die Darstellung von 2^32 Zahlen, es sind aber nur 31 Bit verfügbar + ein Vorzeichen Bit. neg. Vorzeichenbit : - 2^31 Zahlen pos. Vorzeichenbit : + 2^31 Zahlen ---------------------------------- insg. 2 x 2^31 Zahlen

Komplemente:

Da das Rechenwerk eines Computers eine maximale Genauigkeit besitzt können Subtraktionen auf Additionen zurückgeführt werden.

BSP: 4 Bit Rechenwerk | 4 | 3 | 2 | 1 Bit ----------------------------------+---+---+---+--------- max. darstellbare Zahl : | 1 | 1 | 1 | 1 = 15 nicht mehr darstellbare Zahl : 1 | 0 | 0 | 0 | 0 = 16

Allgemein:
Erste gerade nicht mehr darstellbare Zahl bei einem Rechenwert mit n Bit

C = 2^n



Konsequenz: max. darstellbare Zahl plus Eins ergibt Null (!)

BSP: 4 Bit Rechenwerk 1 1 1 1 + 0 0 0 1 --------- = 0 0 0 0

Computer speichern negative Zahlen als Komplement. Dadurch kann jede Subtraktionen auf eine Addition zurückgeführt werden.

BSP: Beschreibung | Dez. | Dual (7 Bit + 1 Vorzeichenbit) -----------------+------------+------------------------------- pos. Zahl | 11 | 0 0001011 Inversion | | 0 1110100 Addition von 1 | | 0 1110101 Komplement | -11 | 1 1110101

b) Gleitkommazahlen (float, real, double, ...)

Halbalgorithmische Darstellung:
x = M * B^e x = (Mantisse) * (Basis)^(Exponent)
BSP: 0,00123 = 0,123 * 10^(-2) = 0,123 E -3 1230,0 = 0,123 * 10^(+4) = 0,123 E +4

Anmerkung:
  1. idR. gespeichert in doppelter Genauigkeit (dh. 2Wort = 8 Byte = 64 Bit)
c) Andere Typen

Textzeichen:
Kodierung als Zahlen (ASCII, Latin)

Maschinenbefehle:
Speicherwort in einer prozessorspezifischen Verschlüsselung

Bitmaps: z.B.
.....111111..... ...11......11... ..1..........1.. .1............1. .1...11..11...1. 1....11..11....1 1....11..11....1 1....11..11....1 1..............1 1...1......1...1 1...1......1...1 .1...1....1...1. .1....1111....1. ..1..........1.. ...11......11... .....111111.....

3.4 Speicherorganisation (RAM)


3.4.1 binäre Daten

  1. lineare Anordnung von binären Speicherelementen
  2. jedes Speicherelement kann ein Bit speichern (0/1, An/Aus)
  3. die Position einer Speicherzelle wird durch ihre Adresse eindeutig bestimmt
  4. die kleinste adressierbare Einheit ist eine Speicherzelle
  5. Speicherzelle (idR.): 8 Bit, 1 Byte, 1 Zeichen
  6. eine bestimmte Anzahl von Bytes wird als Wort zusammengefasst
  7. in einem Wort können eine ganze Zahl oder mehrere Zeichen gespeichert werden
  8. die Wortlänge klassifiziert einen Rechner ( BSP Wortlänge 4 Byte => 4*8=32-Bit-Rechner)

BSP: Adresse | Speicherinhalt (32 Bit Wort) | Klartext --------+-------------------------------------+-------------- 0 | 01110101 01101110 01100100 00100000 | und 4 | 01101111 01100100 01100101 01110010 | oder 8 | 00000000 00000000 00000000 00000001 | 1 12 | 11111111 11111111 11111111 11111111 | 4294967295

3.4.2 Befehle

Befehlsstruktur:
  1. Operationsteil auszuführende Operation (8Bit)
  2. Adressteil Speicherzelle (24Bit)

BSP: --------------------+---------------------------------------------------------- B e f e h l | B e d e u t u n g ----------+---------| Operation | Adresse | ----------+---------+---------------------------------------------------------- LOAD | 40210 | Lade Speicherzelle 40210 ins Rechenwerk ADD | 47836 | Addiere Inhalt von Zelle 47836 zu dem Wert im Rechenwerk STORE | 90026 | Speichere den Wert im Rechenwerk in Zelle 90026

Anmerkung:
Der Operationsteil wird als Binärzahl codiert (LOAD=1, STORE=10). Einige Befehle können mehrere Maschinenworte umfassen.


3.5 Dateien

  1. in Dateien werden Daten zusammengefaßt
  2. idR. haben Dateien Erweiterungen die auf den Inhalt der Datei schließen lassen
  3. Dateien haben eine festgelegte Struktur die idR. mit einen Header beginnt
  4. der Header enthält Informationen wie die Daten in der interpretiert werden sollen

BSP: Header (erste 2Byte) | Erweiterung | Bedeutung ---------------------+-------------+-------------------- - | .txt | Text Datei 42 4D | .bmp | Bitmap Grafik 4D 5A | .exe | Ausführbare Datei

Anmerkung:
2Byte sind nicht ausreichend zur eindeutigen Bestimmung aller Dateien. Die Länge des Headers hängt vom jeweiligen Dateiformat ab.
Link: Programmers Fileformat Collektion


3.6 Datenkompression

Datenkompression macht sich die Tatsache zu nutze, dass Daten wiederholende Bitfolgen enthalten die komprimiert werden können (Eine echte Folge aus Zufallszahlen kann deshalb prinzipiell nicht komprimiert werden). Je größer die Anzahl der Wiederholungen desto größer ist die Kompression. Ein typisches Kompressionsverfahren ist z.B. RLE (Run Length Encoding). Diese Kompressionsverfahren arbeiten verlustfrei.

Handelt sich um Daten bei denen eine exakte Wiederherstellung nicht notwendig ist (Bilder, Audio, Video), so kann eine verlustbehaftete Kompression verwendet werden, die Daten verändert/wegläßt. Das JPG Bildformat z.B. läßt Bildinformationen weg, die im Optimalfall (je nach Kompressionrate) für das menschliche Auge ohnehin nicht sichtbar sind.

Link: Algorithms (BSP. für Kompressionsalgorithmen)


3.7 Datenverschlüsselung

Unverschlüsselte Daten nennt man Klartext, verschlüsselte Chiffrat. Wird der selbe Schlüssel zum Ver- und Entschlüsseln verwendet so spricht man von einem symmetrischen Verschlüsselungsverfahren. Durch die Notwendigkeit den Schlüssel dem Empfänger zu Übermitteln ist das Verfahren unsicher. Werden verschiedene Schlüssel verwendet so spricht man von einem asymmetrischen Verschlüsselungsverfahren (RSA-Verfahren)

BSP: Algorithmus | Schlüssellänge (Bit) | Programme =================+===============================+======================= DES u. Varianten | 64 bis 168(Triple-DES) | Norton Your Eyes only | | PGP (insb. E-Mail) | | Safe House -----------------+-------------------------------+----------------------- Blowfish | 32 bis 448 | Blowfish Advanced | | Norton Secret Stuff | | Datasafe | | Safe House -----------------+-------------------------------+----------------------- Ghost | bis 256 | Blowfish Advanced -----------------+-------------------------------+----------------------- RCx | 40 bis 2048(RC5,Exportverbot) | Norton Your Eyes only | | Top Secret



Impressum
 


Copyright 2002,2003 M. Schmitz