O processzor)

´ ´ITASTECHNIKA ´ SZAM

Fazekas G´abor (2003/2004) 1

´ ´ITOG ´ EP ´ FUNKCION ´ ´ ´ITESE ´ A számítógép funkcionális felépítése A SZAM ALIS FELEP

KÖZPONTI EGYSÉG Központi vezérloegység (CPU, processzor) - utasítás vezérlo - aritmetikai-logikai egység - regisztertár - belso busz - … Busz-rendszer - adatok - címek - vezérlés Memória (operatív tár, fotár, RAM, ROM)

Input-output vezérlo egység (csatorna, channel, I/O processzor)

Input-output vezérlo egység (csatorna, channel, I/O processzor)

Input-output vezérlo egység (csatorna, channel, I/O processzor)

Berendezés vezérlo egység (DCU, device control unit) Berendezés vezérlo egység (DCU, device control unit) Berendezés vezérlo egység (DCU, device control unit) Berendezés vezérlo egység (DCU, device control unit) Berendezés vezérlo egység (DCU, device control unit)

I/O berendezés periféria, (pl. grafikus display) I/O berendezés (pl. grafikus display) I/O berendezés (pl. klaviatúra)

I/O berendezés (pl.merevlemez) I/O berendezés (pl. merevlemez) I/O berendezés (pl. mágnesszalag) I/O berendezés (pl. mágnesszalag) I/O berendezés (pl. hálózati csatolás) I/O berendezés (pl. hálózati csatolás)

´ ´ITASTECHNIKA ´ SZAM

Fazekas G´abor (2003/2004) 2

• - CPU: a sz´am´ıt´og´ep ¨osszes folyamatainak, az utas´ıt´asok v´egrehajt´as´anak, az ´allapotv´altoz´asoknak vez´erl´ese ´es u ¨temez´ese (rendszer ´ora, ´orajel szerepe) • - ALU: aritmetikai ´es logikai m˝ uveletek elv´egz´ese, eredm´eny´enek meghat´aroz´asa • -regiszter t´ ar: ”gyors” t´ar, vez´erlˆo ´es programoz´oi regiszterek • -CPU ROM: mikroprogram t´ar (ha van!) • -Busz rendszer: belsˆo adat ´es vez´erlˆojel forgalom sz´am´ara (c´ım-, adat-, vez´erlˆo busz) • -Mem´ oria: adatok ´es utas´ıt´asok t´arol´asa az operat´ıv t´ar szervez´ese (byte=b´ajt, sz´o, mezˆo,...) ´es c´ımz´ese a bin´aris rendszer szerepe • -Csatorna: – ”cs¨okkent k´epess´eg” processzor, k¨ozvetlen mem´oria hozz´af´er´essel, (programozhat´o!, csatorna program, multiplex ´es szelektor m´od) – a megszak´ıt´asi rendszer szerepe az I/O v´egrehajt´asa sor´an • -DCU: – azonos t´ıpus´ u I/O berendez´esek vez´erl´ese, ´atk´odol´as • -I/O berendez´ es: – beviteli, kiviteli eszk¨oz, h´att´ert´ar

´ ´ITASTECHNIKA ´ SZAM

Fazekas G´abor (2003/2004) 3

A g´ epi utas´ıt´ asok szerkezete, a sz´ am´ıt´ og´ ep m˝ uk¨ od´ ese • -a g´ epi utas´ıt´ as ´ altal tartalmazott inform´ aci´ o: – mit kell tenni (utas´ıt´as k´od) – mivel (mikkel) kell tenni (operandusok) – technikai inform´aci´o (pl. az utas´ıt´as hossza) • -a g´ epi utas´ıt´ as ´ abr´ azol´ asa az operat´ıv mem´ ori´ aban: – az alkalmazott processzort´ol f¨ ugg, pl. IBM SYSTEM 360: 2,4,6 b´ajt hossz´ u utas´ıt´asok szerkezete:

´ KOD 1.OPERANDUS v. C´IM 2.OPERANDUS v. C´IM

INTEL 80 xxx: 1-7 b´ajt hossz´ u utas´ıt´asok szerkezete: vagy:

´ KOD 1.OPERANDUS v. C´IM 2.OPERANDUS v. C´IM , ´ KOD OPERANDUS v. C´IM

• -CPU program: g´epi utas´ıt´asok sorozata • -a program v´ egrehajt´ asa: – az utas´ıt´assz´aml´al´o (program counter, instruction pointer) szerepe – szekvenci´alis m˝ uk¨od´es (von Neumann elv) – vez´erl´es´atad´as – az utas´ıt´asok v´egrahajt´asakor l´etrej¨ovˆo ´allapotok (felt´etelek) – megszak´ıt´asok

´ ´ITASTECHNIKA ´ SZAM

Fazekas G´abor (2003/2004) 4

A sz´ am´ıt´ og´ epek ´ es a sz´ am´ıt´ astechnika t¨ ort´ enete • - tudom´anyt¨ort´enet — ipart¨ort´enet • - M´ar az ´okorban is ... ?! – sz´amol´as ´es eszk¨ozhaszn´alat – az automatika, a szab´alyoz´o rendszerek elˆodei calculus = ,,j´at´ek a kavicsokkal” abakusz H´eron ,,automat´ai” (Kr. u. 100) Leonardo da Vinci ,,rep¨ ulˆo” szerkezetei Pierre Jacquet Droz (1773) ,,Androidok” Antropomorf szeml´elet: zongor´az´o (mama), ´ır´o (gyerek), rajzol´o (gyerek) b´abuk. κυβ²ρνητ ηζ(k¨ ubern´et´ez)=korm´anyos → kibernetika • - 1630: Wilhelm Shickard, T¨ ubingen mechanikus g´ep (+,-,*,/); 1960-ban rekonstru´alt´ak • - 1642: Blaise Pascal (+,-) • - 1671: Gottfried W. Liebnitz t¨ok´eletes´ıti Pascal g´ep´et – Mathesis Universalis: kettes sz´amrendszer • jelentˆos´eg¨ uk: az aritmetikai m˝ uveletek mechaniz´alhat´ok • t´arsadalmi–gazdas´agi h´att´er (motiv´aci´ok): haj´oz´as, ipar, kereskedelem, tˆozsde, biztos´ıt´as

´ ´ITASTECHNIKA ´ SZAM

Fazekas G´abor (2003/2004) 5

• - 1822: Charles Babbage, Cambridge Difference Engine (differencia g´ep) (+,-) eg´esz eggy¨ utthat´os polinom eg´esz helyen felvett helyettes´ıt´esi ´ert´ek´enek kisz´am´ıt´asa visszavezethetˆo a ,,differencia” el´eg sokszori ¨osszegz´es´ere • - 1823–1830: Analitical Engine, (+,-,*,/), 25000 font. – Csak a terve k´esz¨ ult el! • Babbage munk´ass´ag´anak jelentˆos´ege: analitikus = digit´alis egy ilyen g´ep ,,programozhat´o” (aritmetikai ´es logikai m˝ uveletek sorozat´at lehet megadni Jacquard-f´ele lyukk´arty´ak seg´ıts´eg´evel) nemcsak numerikus sz´am´ıt´asokra alkalmas ,, ... az analitikus g´ep nem azzal az ig´ennyel l´ep fel, hogy valamit is l´etrehozzon. De mindent megtehet, amirˆol meg tudjuk mondani, hogyan tegye.” Ada Augusta (Lady Lovelace) • 1880: dr. Hermann Hollerith (U.S.A.) Lyukk´artya feldolgoz´as ↔ 1990-es n´epsz´aml´al´as IBM (International Business Machines Corporation)el˝odje • 19. sz´azad - 20. sz´azad eleje: - fizika, elektronika fejlod´ese - matematika fejlod´ese - Georg Boole: logikai algebra - Alan Turing: to compute ? COMPUTER absztrakt g´ep ? Turing g´ep

´ ´ITASTECHNIKA ´ SZAM

Fazekas G´abor (2003/2004) 6

• 20. sz´azad K¨ozvetlen el˝ozm´enyek: - elektronika gyors fejl˝od´ese (elektroncs˝o: 1906 Robert von Lieben) - ir´any´ıt´astechnika, szab´alyoz´aselm´elet fejl˝od´ese (Norbert Wiener) - matematika fejl˝od´ese (Neumann J´anos) - g´epes´ıtett adatfeldolgoz´as - t´arsadalmi ig´enyek (II. vil´agh´abor´ u: sz´all´ıt´as, ballisztika) 1933 - 44 Saarbr¨ ucken, Konrad Zuse Z22 1939 - 44 Harward Egyetem, Howard Aiken (MARK1) elektromechanikus g´epek (rel´ek, forg´okapcsol´ok, a program lyukszalagon) 1946 Pennsylvania Egyetem: J.P. Eckert J. W. Mauchly ENIAC (Electronic Numerical Integrator and Calculator) Jellemz˝oi: hatalmas m´eretek, 18000 elektroncs˝o 10 Megawatt teljes´ıtm´eny gyakran elromlott nincs programt´arol´as → ”dugaszol´as” adatok lyukk´arty´an gyors: 300 szorz´as/sec. • A Neumann-f´ele elv: - a sz´am´ıt´asok elv´egz´es´et el˝o´ır´o utas´ıt´asokat a sz´am´ıt´og´ep t´ar´aban kell elhelyezni (bels˝o programt´arol´as, bin´aris rendszer) - bels˝o programvez´erl´es ↔ aritmetika - line´aris, szekvenci´alis m˝ uk¨od´es • Az elv jelent˝os´ege: - gyors m˝ uk¨od´es - lehet˝ov´e v´alik az utas´ıt´asok adatk´ent val´o kezel´ese (a sz´am´ıt´og´ep m´odos´ıthatja saj´at programj´at u ´gy, hogy a k´odolt utas´ıt´asokkal u ´gy dolgozik, mintha sz´amok lenn´enek), pl. adatk´ent kezelhet˝o, hogy az ´eppen v´egrehajt´as alatt ´all´o utas´ıt´as ut´an melyik k¨ovetkezz´ek:→ vez´erl´es´atad´as, ciklus. • Az 1946 ut´an k´esz´ıtett un. els˝o gener´aci´os g´epek a Neumann-f´ele elvnek megfelelo˝oen ´ep¨ ultek. IAS (Institute for Advanced Study) : 1952 EDSAC : 1949 EDVAS : 1952

´ ´ITASTECHNIKA ´ SZAM

Fazekas G´abor (2003/2004) 7

UNIVAC1 : 1951 ßEBM (Szovjetuni´o): 1953 • 2. gener´aci´os g´epek (1955 - 64) - Az elektroncs˝o szerep´et ´atveszi a tranzisztor (´altal´aban a g´epek fizikai m´erete cs¨okken, a nagy g´epek mellett megjelennek a mini g´epek) 1958 IBM - 1400 1959 IBM - 7090 - adat´atviteli, perif´eri´as berendez´esek fejlod´ese - sz´amol´as ´es adat´atvitel szimult´an v´egrehajt´as - megszak´ıt´asi rendszer - folyamatvez´erl´es - a teljes m˝ uk¨od´es automatiz´al´asa program seg´ıts´eg´evel ==¿ oper´aci´os rendszer - programoz´asi nyelvek kialakul´as´anak kezdetei 1954 - 57 FORTRAN (Formula TRANslation Language 1959 COBOL (COmmon Business Oriented Language 1958 - 60 - 62 ALGOL (ALGOrithmic Language) 1964 PL/1 (Programming Language 1) • 3. gener´aci´os g´epek - integr´alt ´aramk¨or¨ok - tudom´anyos c´el´ u ´es adatfeldolgoz´asra orient´alt m˝ uveletek - sok adatforma - adatcsatorn´ak - fejlett oper´aci´os rendszer IBM System/360 sorozat, ipari szabv´any (1964), ESzR sorozat megjelen´ese • 4. ´es tov´abbi gener´aci´ok VLSI, mikrochipek, nanotechnol´ogia

´ ´ITASTECHNIKA ´ SZAM

Fazekas G´abor (2003/2004) 8

Az informatika t¨ ort´ enete (internetes forr´ asok) A sz´ am´ıt´ og´ epek t¨ ort´ enete (id˝ osorrendben): • http://www.computer.org/history/development/index.html • http://www.ox.compsoc.net/ swhite/history/timeline.html IEEE Virtu´ alis M´ uzeum: • http://www.ieee-virtual-museum.org/ The History of Computing Foundation • http://www.thocp.net/ Charles Babbage Institute (University of Minnesota) • http://www.cbi.umn.edu/ American Computer Museum: • http://www.compustory.com/ Sz´ am´ıt´ astechnika t¨ ort´ enet (Szerz˝o: Rozgonyi-Borus Ferenc, magyar nyelven): • http://www.inlap.jate.u-szeged.hu/

´ ´ITASTECHNIKA ´ SZAM

Fazekas G´abor (2003/2004) 9

Az inform´ aci´ o´ abr´ azol´ asa, k´ odol´ as ´ O: ´ ,,minden”, ami valamilyen k´erd´esben a bizonytalans´agunkat cs¨okkenti. INFORMACI • – filoz´ofiai kateg´oria • – f¨oltev´es: az inform´aci´ot anyag, vagy energia hordozza (jel) • – Matematikai elm´elet: Claude E. Shannon: ,,A kommunik´aci´o matematikai elm´elete”; 1948. • – Az inform´aci´o m´er´ese: Menn´el kisebb egy esem´eny bek¨ovetkez´es´enek val´osz´ın˝ us´ege (, azaz menn´el nagyobb az esem´eny bek¨ovetkez´es´evel kapcsolatos bizonytalans´agunk), ann´al nagyobbnak ´erezz¨ uk az esem´eny bek¨ovetkez´es´erˆol tud´os´ıt´o k¨ozl´es inform´aci´otartalm´at. • – A bizonytalans´ag m´er´ese: entr´ opia. Ha A = {A1 , A2 , ... , An } teljes esem´enyrendszer, az i-edik esem´eny bek¨ovetkez´es´enek es´elye (val´osz´ın˝ us´ege) rendre p1 , p2 , ... , pn , n P (pi > 0, pi = 1), akkor az esem´enyrendszer kimenetel´evel kapcsolatos entr´opia (bizonytalans´ag): i=1

H=−

n X

pi log2 pi

i=1

A = {A1 , A2 } teljes esem´enyrendszer, ´es p1 = p2 =

1 2

(egyszer˝ u alternat´ıva), akkor az esem´enyrendszer kimenetel´evel kapcsolatos

entr´opia (bizonytalans´ag): H=−

2 X

pi log2 pi = 1

i=1

• – Az inform´aci´o m´ert´ekegys´ege: 1 bit (egy igen-nem k´erd´esre adott v´alasz – barkochba)

• – ADAT: a jelent´es´etˆol megfosztott inform´aci´o, a v´alasz.

´ ´ITASTECHNIKA ´ SZAM

Fazekas G´abor (2003/2004) 10

´ ´ KODOL AS: A:

forr´as abc, A∗ : forr´ask¨ozlem´enyek halmaza

K:

k´od abc, K×(i) = K | × K ×{z ... × K} i−szer

K∗ =

∞ S

K×(i)

k´odszavak halmaza

i=1

f : A∗ 7→ K∗

f¨ uggv´eny (k´odol´asi elj´ar´as)

Bet˝ unk´ enti k´ odol´ as: Minden n-re ´es a1 , a2 , ... an ∈ A-ra f (a1 a2 ... an ) = f (a1 )f (a2 ) ... f (an ) → El´eg a forr´as abc jeleinek k´odj´at ismerni (megadni)! Automata k´ odol´ as: — (esetleg) t¨obb forr´asjelhez rendel¨ unk egy k´odsz´ot. A k´ odol´ asi elj´ ar´ asokkal szemben t´ amasztott legfontosabb k¨ ovetelm´ enyek: – egy´ertelm˝ u dek´odolhat´os´ag (irreducibilit´as) – gazdas´agoss´ag (egy jel k´odol´as´anak ´atlagos k¨olts´ege → minimum) H=−

n X

pi log2 pi ≤

i=1

pi li

i=1

pi

az i−edik forr´asjel elˆofordul´asi val´osz´ın˝ us´ege

li

az i−edik k´odsz´o hossza

– hibafelismer´es, hibajav´ıt´as Bin´aris k´odok: |K| = 2,

n X

Pl. MORSE abc

Azonos hossz´ us´ag´ u k´odok: minden k´odsz´o ugyanolyan hossz´ u

´ ´ITASTECHNIKA ´ SZAM

Fazekas G´abor (2003/2004) 11

A k´ odol´ as gyakorlati alkalmaz´ asai: – t´avk¨ozl´es (szabv´anyok – CCITT narancsk¨onyv) – adatr¨ogz´ıt´es adathordoz´okon, sz.g´epek mem´ori´aj´aban, h´att´ert´arakon

A gyakorlatban alkalmazott elj´ar´asok t´ ulnyom´o t¨obbs´ege azonos hossz´ us´ag´ u, bin´aris k´odrendszert haszn´al.

´ ABC: bet˝ FORRAS ukbˆol, sz´amjegyekbˆol, speci´alis jelekbˆol, technikai jelekbˆol ´all A 2- ´es 2 hatv´any alap´ u sz´amrendszerek szerepe: a k´odsz´o bin´aris(2), okt´alis(8), hexadecim´alis(16) sz´amk´ent interpret´alhat´o.

´ KODRENDSZEREK:

BCD (Binary–Coded Decimal) k´od: Bin´arisan k´odolt decim´alis sz´amjegyek ( ,,4 bites”, sz´amjegy szervez´es˝ u t´arak.) 0 0 0 0 0 1 0 0 0 1 2 0 0 1 0 3 0 0 1 1 . . . . . . 8 1 0 0 0 9 1 0 0 1

´ ´ITASTECHNIKA ´ SZAM

Fazekas G´abor (2003/2004) 12

3 t¨ obblet˝ u (STIBITZ) k´ od: Bin´arisan k´odolt decim´alis sz´amjegyek (Jelentˆos´ege: a decim´alis ´atvitel a legnagyobb helyi´ert´eken jelentkezik!) 0 1 2 3 . . . 8 9

0 0 0 0

0 1 1 1

1 1

0 0

1 0 0 1 . . . 1 1

1 0 1 0

1 0

´ ´ITASTECHNIKA ´ SZAM

Fazekas G´abor (2003/2004) 13

TELEX k´ od 5 bites, lyukszalag orient´alt OPTIMA, ISO k´odok ASCII (American Standard Code for Information Interchage) EBCDIC (Extended Binary Coded Decimal Interchange Code) DKOI k´odrendszer K´odok megad´asa t´abl´azattal, z´ona ´es numerikus r´esz fogalma K´odok monotonit´asa, lexikografikus rendez´es problematik´aja

Sz¨ oveg reprezent´ aci´ o • ASCII (American Standard Code for Information Interchange) - Angol ABC kis- ´es nagybet˝ ui, sz´amjegyek, ´ır´asjelek, szegment´al´o- ´es ´atvitelvez´erl˝o jelek, - 7/8 bites v´altozat, - a fel nemhaszn´alt jelek egy´eni ´ertelmez´ese → inkompatibilit´as. • ISO (International Standard Organisation) — az ASCII rendszer standard kiterjeszt´esei - tervezte: ECMA (European Computer Manufacturers Association), - regisztr´alta: IANA (Internet Assigned Number Authority) a MIME (Multi-purpose Internet Mail Extensions) sz´am´ara, - ISO Latin1 (ISO 8859-1) nyugat-eur´opai nyelvek, - ISO Latin2 (ISO 8859-2) k¨oz´ep-eur´opai nyelvek (16 db, pl. magyar),→ http://sizif.mf.uni-lj.si/linux/iso8859-2.html - ISO 8859-5 cirill, ISO 8859-7 t¨or¨ok, - van (IEEE) Chinese, Japanese, Korean, Arabic, ... is. - Alkalmaz´asai: X-window rendszer, PostScript rendszer, szoftver csomagok nemzetk¨ozi verzi´oi - Windows 1250 karakterk´eszlet → http://www.microsoft.com/tuetype/unicode/1250.htm • Marked-up sz¨oveg * karakterk´eszletek a tartalom kifejez´es´et szolg´alj´ak, * formai megjelen´eshez (prezent´aci´ohoz) tov´abbi inform´aci´o kell (pl. pozicion´al´as, tipogr´afiai jellemz˝ok megad´asa). * egy megold´as: speci´alis karaktersorozatok (mark-upstring) elhelyez´ese a sz¨ovegben, amelyek struktur´alis hat´arokat ´es form´atum specifik´aci´okat jelentenek. * pl. a troff (UNIX, Ossana, 1976) rendszerben .ce =center line jelent´ese: a k¨ovetkez˝o sort k¨oz´epre kell pozicion´alni a lapon. * potenci´alis probl´ema: keveredik a logikai struktura (pl. paragrafus v´ege) az u.n layout-tal (marg´ok) glob´alis form´az´as lehet˝os´ege. * c´el: megszabadulni a display rabs´ag´at´ol port´abilit´as.

´ ´ITASTECHNIKA ´ SZAM

Fazekas G´abor (2003/2004) 14

* egy megold´as: SGML (Standardized Generalized Markup Language, ISO 1986) elv´alasztja a layout-ot a logikai szerkezett˝ol dokumentum t´ıpus absztrakt ´es dokumentum el˝ofordul´as konkr´et fogalma. * extr´em esetek (szolg´altat´asok): * troff: + vez´erl´esi szerkezetek + v´altoz´ok + makr´ok; * TEX (D. Knuth, 1984); * LATEX (L. Lamport, 1986) * speci´alis ter¨ uletek kezel´ese: SMDL (Standard Music Description Language) * PostScript, PDF, RTF form´atumok szerepe • Strukt´ ur´alt sz¨oveg * A tag-ek (c´ımk´ek) lehet˝ov´e teszik, hogy a sz¨oveget strukt´ ur´aljuk. A strukt´ ura lehet a sz¨oveg tartalmi egys´egeit kifejez˝o logikai strukt´ ura (fejezet, szakasz, paragrafus, stb) ez pl. lehet egy fa-szerkezet. * Sok dokumentum feldolgoz´o rendszernek saj´at megold´asa van a fenti hierarchikus dokumentumszerkezetek kezel´es´ere, de * van szabv´any is! ODA (Office Document Architecture, ISO 1989) • Hypertext * a hagyom´anyos sz¨ovegek a layout szempontj´ab´ol- ´es logikai ´ertelemben v´eve is hierarchikusak, sokszor egyszer˝ uen line´arisak. * a hypertextnek ezzel szemben h´al´o-szer˝ u szerkezete van: csom´opontokb´ol (node) ´all, amelyek kapcsol´okkal (link) vannak ¨osszek¨otve. * a felhaszn´al´o rendelkezik egy sz´am´ıt´og´epes b¨ong´esz˝ovel (browser, sz´am´ıt´og´epes prezent´aci´os rendszer), amelynek seg´ıts´eg´evel a kapcsol´okat k¨ovetve k´epes (interakt´ıv m´odon) a csom´opontokat gyorsan el´erni. * node m´erete k´eperny˝om´eret * igazi probl´ema: a kapcsol´ok k¨ovet´ese q * a kapcsol´ok t´ıpusai: - egy, vagy k´etir´any´ u, - csom´opontra, paragrafusra, sz´ora mutat, - attrib´ utummal ell´atott, vagy attrib´ utum mentes (pl. a link k¨ovet´ese felt´etelezi bizonyos akci´ok v´egrehajt´as´at. * szabv´anyok: HTML, HYTEX, ...

´ ´ITASTECHNIKA ´ SZAM

Fazekas G´abor (2003/2004) 15

Hibafelismer´ es ´ es hibajav´ıt´ as, hibajav´ıt´ o k´ odok: K = {0, 1}:

k´od abc,

Kn = K×(n) = |K × K ×{z ... × K} n−szer

Kn a lehets´eges k´odszavak halmaza (bin´aris, azonos hossz´ us´ag´ u k´od: C ⊂ Kn ) Kn a k´et elem˝ u test (K) f¨ol¨otti n dimenzi´os vektort´erk´ent interpret´alhat´o. Minden x = (x1 , x2 , ... , xn ) ∈ K eset´en |x| =

n X

xi

i=1

az x vektor s´ ulya (az egyesek sz´ama x-ben). d(x, y) = |x ⊕ y| az x ´es y k´odszavak Hamming-t´ avols´ aga (azon pozici´ok sz´ama, ahol x ´es y k¨ ul¨onb¨ozik). Hamming-t´avols´ag: az ´atvitel sor´an keletkezett torzul´as m´ert´eke. A C k´od k´ odt´ avols´ aga: d(C) =

min

x,y∈C, x6=y

d(x, y)

´ TETEL: Annak sz¨ uks´eges ´es el´egs´eges felt´etele, hogy a C k´od t ´atviteli hib´at felismerjen, ill. jav´ıtson, az, hogy a d(C) > t, ill. d(C) > 2t egyenlˆotlens´egek teljes¨ uljenek. Legyen

n X Pn = {x ∈ Kn | ° xi = 0} i=1

Pn az n-bites parit´ asellenˆ orzˆ o k´ od. Pn line´aris k´od. d(Pn ) = 2. Legyen k : 2k−1 ≤ n < 2k ´es

´ ´ITASTECHNIKA ´ SZAM

Fazekas G´abor (2003/2004) 16 

 1 0 1 . . . a1,n 0 1 1 . . . a2,n     H= 0 0 0 . . . a3,n  . . . . . . . . . . . . . . . . . . . . 0 . . . . ak,n−1 1 H i−edik oszlopa: i bin´aris alakja. Legyen Hn = {x ∈ Kn | Hx = 0} Hn az n-bites Hamming k´ od. Hn line´aris k´od. d(Hn ) ≥ 3. P´ elda: Legyen n = 6, akkor k = 3 ´es 

 1 0 1 0 1 0 H = 0 1 1 0 0 1  0 0 0 1 1 1 Az x = (0, 1, 0, 1, 0, 1)T vektor k´odsz´o. (∈ H6 ). Ha x-et tov´abb´ıtva, helyette y = (0, 1, 0, 1, 1, 1)T -t kapunk, akkor   1  Hy = 0 7→ 5 1 Hy 6= 0 megmutatja, hogy melyik pozici´oban volt a hiba (felt´eve, hogy egy hiba volt).

´ ´ITASTECHNIKA ´ SZAM

Fazekas G´abor (2003/2004) 17

Adatt´ıpusok, ´ ert´ ek szerinti k´ odol´ as (´ abr´ azol´ as) ADAT

numerikus

bin´aris

fixpontos

lebegˆopontos

logikai

decim´alis

fixpontos

lebegˆopontos

Bin´ aris / decim´ alis: az ´abr´azoland´o sz´am bin´aris/decim´alis sz´amrendszerbeli alakj´ab´ol indulunk ki. Fixpontos: x = m · a−k alak´ u sz´amokat ´abr´azolunk. m, k eg´esz, k ≥ 0 r¨ogz´ıtett, igy el´eg m-et ´abr´azolni. k Lebegˆ opontos: x = m · a alak´ u sz´amokat ´abr´azolunk. k eg´esz. Az (m, k) rendezett p´art ´abr´azoljuk.

Fixpontos bin´ aris sz´ am´ abr´ azol´ as m bin´ aris pozici´ on Alapelv: Legyen I0 az [0, 2m − 1] intervallumba esˆo eg´esz sz´amok halmaza. Mivel m biten az I0 halmaz elemei ´abr´azolhat´ok (filoz´ofia mentesen, mint m jegy˝ u bin´aris sz´amok), ez´ert valamilyen sz´am´abr´azol´asi filoz´ofi´ahoz u ´gy juthatunk, hogy az ´abr´azolni k´ıv´ant sz´amtartom´anyt (I-t) lek´epezz¨ uk I0 -ra. – elˆ ojeles abszol´ ut´ ert´ ekes: I = {x eg´esz| − 2m−1 + 1 ≤ x ≤ 2m−1 − 1}, x 7→ x e = x, ha x ≥ 0, 2m−1 + |x|, ha x ≤ 0. elˆojelbit, ±0, m˝ uveletek, konverzi´ok

´ ´ITASTECHNIKA ´ SZAM

Fazekas G´abor (2003/2004) 18

– (kettes/t´ızes) komplemens: I = {x eg´esz| − 2m−1 ≤ x ≤ 2m−1 − 1}, x 7→ x = x, ha x ≥ 0, 2m + x, ha x < 0. elˆojelbit, nincs ±0, konverzi´ok, m˝ uveletek. • – Mivel 2m + x = 2m − 1 + x + 1 ´es 2m − 1 olyan m jegy˝ u bin´aris sz´am, amelynek minden jegye 1, x < 0−ra x¯-et megkapjuk, ha |x| m jegy˝ u bin´ aris alakj´ aban minden jegyet ellenkezˆ oj´ ere v´ altoztatunk, majd az eredm´ enyhez 1-et adunk ( mod 2m , azaz a legmagasabb helyi´ert´eken esetleg keletkezˆo ´atviteltˆol eltekint¨ unk). L´athat´o, hogy ezzel a transzform´aci´oval k´epezhetj¨ uk egy pozit´ıv sz´am negat´ıvj´at. • – Mivel 2m − (2m + x) = −x, az elˆozˆo transzform´aci´o negat´ıv sz´am negat´ıvj´anak k´epz´es´ere is alkalmas! • – Meg lehet mutatni, hogy ha x, y, x + y ∈ I, akkor x+y =x+y

mod 2m .

• – Meg lehet mutatni, hogy ha x, y ∈ I, akkor x + y ∈ I akkor ´es csak akkor, ha az x + y ¨osszeg k´epz´epsekor a legmagasabb helyi´ert´ek˝ u ´es az azt k¨ovetˆo biten keletkezˆo ´atvitel ´ert´eke megegyezik. Egy´ebk´ent fixpontos t´ ulcsordul´ as j¨on l´etre. (pl. −2m−1 negat´ıvja!). • – Szorz´as, oszt´as: Booth algoritmus.

– t¨ obbletes ´ abr´ azol´ as: I = {x eg´esz| − 2m−1 ≤ x ≤ 2m−1 − 1}, x 7→ x0 = 2m−1 + x∗ elˆojelbit, nincs ±0, konverzi´ok, m˝ uveletek.

´ ´ITASTECHNIKA ´ SZAM

Fazekas G´abor (2003/2004) 19

lebegˆ opontos bin´ aris sz´ am´ abr´ azol´ as • – Az ´abr´azoland´o x sz´amot x = m · ak

(|m| < 1)

alakban fel´ırtnak k´epzelj¨ uk, ahol a = 2l (legt¨obbsz¨or l = 1, 4). m: mantissza, k karakterisztika. • – Ha |m| ≥ a1 , akkor a (!) fel´ır´as normaliz´alt (egy´ertelm˝ u). • – Az (m, k) rendezett p´art ´abr´azoljuk fixpontosan. • – M˝ uveleti algoritmusok: ¨ – – Osszead´ as, kivon´as: (1) karakterisztik´ak igaz´ıt´asa (a kisebbik nˆo, a mantissza jobbra eltol´odik); (2) m˝ uvelet elv´egz´ese; (3) postnormaliz´al´as. – – szorz´as, oszt´as: (1) karakterisztik´ak ¨osszead´odnak, mantissz´ak ¨osszeszorz´odnak; (2) postnormaliz´al´as. – – hib´ak: (1) kitevˆo alulcsordul´as; (2) kitevˆo t´ ulcsordul´as; (3) ´ert´ekveszt´es.

´ ´ITASTECHNIKA ´ SZAM

Fazekas G´abor (2003/2004) 20

´ ADATHORDOZOK Lyukszalag Lyukk´ artya – - Hollerith k´artya, IBM k´artya: 80 oszlop, oszloponk´ent 12 lyukaszt´asi poz´ıci´o. – - Whittaker k´artya: 96 oszlop, oszloponk´ent 6 lyukaszt´asi pozici´o M´ agnes szalag – - f´el h¨ uvelyk (inch) sz´eles, 2400 (300,600,1200) l´ab hossz´ u, – - 7-9 csatorna – - ´ır´ass˝ ur˝ us´eg: 800 bit/inch (BPI) – - ´ır´as elve: NRZ (No Return to Zero) – - blokk koncepci´o, IBG (gap), a gap ´es a hasznos adatter¨ ulet ar´anya. – - hibaellelnˆorz´es: CRC, LRC, parit´as M´ agneslemez diszk, hard disc, Winchester – - 14 (8, 5 14 , 3 12 ) inch ´atm´erˆoj˝ u, m´agnesezhetˆo oxidr´eteggel bevont aluminium lemezek k¨oz¨os tengelyen r¨ogz´ıtve. – - ´ır´o/olvas´o fejek, mechanizmus – - s´av (track), szektor/blokk, cilinder – - szinkroniz´aci´o, ´orajel, a lemez form´az´asa – - access time = seek (track) time + search (block) time Hajl´ ekony m´ agneslemez floppy disc, diskette – - index lyuk, ´ır´asv´edelem – - direct access ↔ random access alapfogalmak: k¨ otet (volume), meghajt´ o (drive), fizikai ´ allom´ any (file), cimke (label), katal´ ogus (directory)

´ ´ITASTECHNIKA ´ SZAM

Fazekas G´abor (2003/2004) 21

A m´ agneslemezes ´ es szalagos adatt´ arol´ as elˆ onyei, h´ atr´ anyai – - lemezen az adatok t´arolhat´ok ´es feldolgozhat´ok szekvenci´alisan, de direkt m´odon is. – - (on line) lemezen az adatok n´eh´any millisecundum alatt el´erhetˆok, a tranzakci´ok semmif´ele rendez´ese nem sz¨ uks´eges. – - (on line) lemezen azonos feldolgoz´asok k¨ ul¨onb¨ozˆo t´ıpus´ u adatai szimult´an m´odos´ıthat´oak. – - m´agnes szalagon t´arolt adatok m´odos´ıt´asakor a r´egi (master) szalag egy ideig megmarad. – - m´agneslemezen t´arolt adatok m´odos´ıt´asakor a r´egi (master) adat ´altal´aban nem marad meg (ha ezt k¨ ul¨on nem szevezik meg). – - m´agneslemezen t´arolt adatok ´erz´ekenyek a meghajt´o s´er¨ ul´es´ere (Winchester). – - (on line) m´agneslemezen t´arolt adatok kev´esb´e v´edettek az illet´ektelen felhaszn´al´as ellen. Optikai lemez compact disc – - l´ezerrel (f´embe, vagy alkalmas m˝ uanyagba) ´egetett jelek – - t´arol´asi kapacit´asa az azonos m´eret˝ u m´agnes lemez´enek sokszorosa. ¨zemszer˝ uen nem ´ırhat´o u ´jra (jelenleg!) – - h´atr´any/elˆony: u

´ ´ITASTECHNIKA ´ SZAM

Fazekas G´abor (2003/2004) 22 ´ AK ´ PERIFERI ´ ´ ARAK ´ INPUT (Beviteli)-, OUTPUT (Kiviteli) eszk¨oz¨ok, HATT ERT Output: alfanumerikus (grafikus) display (VDT – Visual Display Terminal, CRT – Cathode-Ray Tube, LCD – Liquid-crystal display), printer (m´atrix-, sornyomtat´o, lapnyomtat´o, laser, tintasugaras, margar´etakerekes...) plotter (rajzg´ep), stb...

Input: alfanumerikus billenty˝ uzet, konzol´ır´og´ep, lyukszalag olvas´o, lyukk´artya olvas´o, f´enyceruza, scanner, eg´er, touch screen, digitaliz´al´ok, stb. H´ att´ ert´ arak: M´agneslemez, M´agnes szalag, Optikai lemez, stb...

´ ´ITASTECHNIKA ´ SZAM

Fazekas G´abor (2003/2004) 23

ALGORITMUSOK (intuit´ıv) defin´ıci´o: egy feladat megold´as´ara vezetˆo elemi l´ep´esek egy´ertelm˝ uen meghat´arozott v´eges sorozat´at algoritmusnak nevezz¨ uk. Az algoritmus mindig valamilyen input adatokhoz output adatokat rendel. elemi: meg´ıt´el´ese szubjekt´ıv egy´ertelm˝ u: b´armely l´ep´es (kiv´eve az utols´ot) ut´an pontosan egy k¨ovetkezhet v´eges: befejezˆodik v´eges sok l´ep´es ut´an ↔ m´odszer! input: az az inform´aci´o, amellyel az algoritmus v´egrehajt´oj´anak a v´egrehajt´as elˆott rendelkeznie kell output: az az inform´aci´o, amely az algoritmus v´egrehajt´asa ut´an rendelkez´esre ´all

Algoritmus le´ır´ asi m´ odok – - verb´alisan (szak´acsk¨onyv, haszn´alati utas´ıt´as) – - folyamat´abra, blokkdiagramm seg´ıts´eg´evel - ¨osszef¨ uggˆo ir´any´ıtott gr´af egy kezdˆoponttal ´es legal´abb egy v´egponttal - a gr´af sz¨ogpontjai az algoritmus elemi l´ep´eseinek felelnek meg, az ´elek a l´ep´esek egym´asut´ani sorrendj´et fejezik ki - folyamat´abra szimb´olumok - kezdˆopont/v´egpont utas´ıt´as d¨ont´es folyamat vonal - modell- ´es programv´altoz´ok – - speci´alis (program) nyelv seg´ıts´eg´evel

´ ´ITASTECHNIKA ´ SZAM

Fazekas G´abor (2003/2004) 24

Az algoritmus matematikai fogalma TURING g´ ep: Tm = {A, S, f, k} form´alis n´egyes, ahol A: egy v´eges halmaz, a Turing g´ep abc-je, amely tartalmaz egy speci´alis jelet, a blank jelet S: egy v´eges halmaz, a Turing g´ep ´allapotainak halmaza f : egy lek´epez´es, amely a A × S halmaz bizonyos elemeihez a A × S × M halmaz elemeit rendeli, ahol M = {←, →, ↑} k: ∈ S a g´ep kezdˆoa´llapota M˝ uk¨ od´ ese: a g´ep rendelkezik egy k´et ir´anyban v´egtelen szalaggal, amely kock´akra (mezˆokre) van osztva. Minden mezˆobe az abc egy jele ´ırhat´o, amelyet a g´ep ´ır´o/olvas´o fej´evel ´ırhat ´es olvashat. Az ir´o/olvas´o fej a szalag hossz´aban mozoghat. Kezdetben a szalagon egy folytonos sz¨oveg tal´alhat´o, az ´ır´o/olvas´o fej a sz¨oveg legbaloldalibb karakter´en´el ´all ´es a g´ep a k kezdˆoa´llapotban van. Ezut´an a karaktert beolvasva az f lek´epez´esnek megfelelˆoen egy u ´j jelet ´ır a szalagra, u ´j ´allapotba ker¨ ul ´es elmozdul jobbra, vagy balra, vagy helyben marad. Meg´all, ha az f lek´epez´es nincs defini´alva. Ekkor azt mondjuk, hogy az input sz¨oveget leford´ıtotta arra a sz¨ovegre, amely meg´all´askor a szalag tartalma. ´ Turing g´epek, mint transzform´atorok, akceptorok, gener´atorok. Turing kisz´am´ıthat´o f¨ uggv´enyek. CHURCH TEZISE: Az algoritmikusan kisz´am´ıthat´o f¨ uggv´enyek oszt´alya megegyezik a TURING-kisz´am´ıthat´o f¨ uggv´enyek oszt´aly´aval. TURING g´epek (algoritmusok) bonyolults´ag´anak m´ert´ekei: – - le´ır´asi bonyolults´ag – - szalagbonyolults´ag – - idˆobonyolults´ag P ´es NP probl´emaoszt´alyok