bigpo.ru
добавить свой файл
1 2 3 4
ВЪПРОС № 1

Историческо развитие на изчислителната техника


Историята показва,че хората създават и използват различни технологии за решаване на съответните проблеми, които възникват с развитието на човечеството и с нарастването на неговите потребности.

Едно от първите технически средства за изчисление е т.нар. абак, представляващ първообраз на днешното сметало. Неговата поява би могла да се търси във времето от преди 4000год. в Древен Китай. Абакът е дъска с вдлъбнатини, в които се поставят камъчета. С течение на времето вдлъбнатините на дъската и камъчетата били заместени от връвчици с нанизани манисти, при което абакът придобива видът на познатото сметало.

Първата самостоятелно действаща машина е сметачната лихварска машина на Блез Паскал (1642г.). Той я нарича още “цифров калкулатор с колела”. Този калкулатор може да събира и да изважда. Някои от нейните основни принципи се прилагат в клавишните машини.

През 1673г. Готфрид Вилхелм Лайбнец (1649-1716) представя пред Парижката академия машина, която за пръв път извършва по механичен път четири аритмитични действиа (+, -, *, / ).

През 1801г. Жозеф-Мари Жакард създава автоматичен тъкачен стан, довел до истински преврат в текстилната индустрия. Той въвежда за пръв път перфокарти за управление на тъкачните станове при получаване на желаната фигура.

В ранните година на XIX век английският учен Чарлз Бебидж конструира своята първа сметачна машина (машина за разлики), но независимо, че получава финансова подкрепа от английското правилтелство не успява да я завърши.

През 1834г. започва да работи по втората си машина – “аналитична машина”и по нея работи до края на живота си, но отново поради липса на средства тя остава незавършена.

Неговата идея е била да създаде автоматичнодействаща механична сметачна машина за изпълнение на всички математически функции. Техническото изпълние на замисъла му претърпява неуспех, но много от идеите му намират широко приложение и са залегнали дори в основата на съвремените компютри.

  • Той използва десетични колела

  • Машината е почти напълно автоматизирана и работи без намесата на оператор

  • Разделя машината на 3 части – склад, който съхранява междинните числови данни, мелница, която извършва аритметичните дейности с числата от склада, управляващо устройство, което организира изпълнението на алгоритъма и периферните устройства за вход и изход на данните

Единствената дъщеря на английския поет лорд Байрон – Августа Ада – разработва програми, които да управляват английската машина на Бебидж при решаването на някоя математическа задача. Тя остава в историята като първият програмист. За отбелязване на делото и на нейно име е наречен езикът за програмиране АДА.

В края на XIX век – 1890 - Херман Холерит построява изчислителна машина, която възприема данни, фиксирани върху перфокарта. Холерит използва табуларната машина за преброяване на населението в САЩ. Тя е първата система за автоматизирана обработка на данни. Тя използва ръчна перфорация за регистриране и записване на данните върху перфокарти с размерите на доларова банкнота. След първото и приложение тя започва да се продава и разпространява в цял свят за извършване на различни счетоводни операции.

С настъпването на XX век развитието и приложението на електронните устройства непрекъснато нараства – изобретена е електрическата лампа, а по-късно и радиоприемникът. Създадени са и множество електро-механични и електронни изчислителни устройства, главно в САЩ и Великобритания.

През 1937г. българинът Джон Атанасов предлага нов тип сметачна машина, като той демонстрира за пръв път използването на двуичната система в сметачните машини, първият последователен суматор, първата регенерирана памет. През 1942г. заедно с Клифърд Бери създава първата цифрово-електронизирана машина, която може да решава линейни уравнения. Той създава АБС компютъра.

През 1939-1943г. е създадена машината МАРК 1- първият в света компютър от голям мащаб от Хауърд Айкен - построена от компанията IBM.

През 1944г. е моделирана и първата автоматична изчислителна машина.

През 1946г. Екерт и Молки, които използват идеите на Джон Атанасов, създават ENIAC – елементарен числов интегратор и изчислител.

В проетка по създаването на ENIAC участва и американският учен математик Джон фон Нойман. Той разработва концепция за серийния програмен процесор, т.е компютър който сам съхранява своите инструкции за работа и ги изпълнява последователно.

През 1953г. на пазара се появява IBM-701 и започва да се разпространява масово.

През 1976г. Стиф Джобс и Стефан Возняк създават първия миникомпютър

(8-битов) на фирмата Apple. През 1981г. излиза успешно на пазара IBM PC – първият 16-битов компютър.


^ ВЪПРОС №2

Видове данни и тяхното битово представяне


Данните са факти,получени и регистрирани чрез наблюдения, преброявания, измервания, и т. н., които след тава са записани в/у някой носител.Докато информацията е резултат от обработката на данни.

Характерни черти на данните са:

-наричат се още сурови, базисни или първични данни и обикновено представят записи за различни всекидневни дейности

-те могат да бъдат получени както от вътрешни, така и от външни източници

Под обработка на данни се разбира процес на произвеждане на полезна информация.Това е едно от най-ранните понятия на бизнес информатиката.Методите на обработка на данни са варирали от ръчни и механичнидо базиращи се на големи компютри.

Данните в компютъра се съхраняват в двоичен код (0 и 1). Общите категории данни в компютъра са числа, адреси, символи, логически данни, звуци, образи.

По своята същност адресите са числа в компътъра. Те се третират като цели числа и без знак. В някои компютри са заложени по-сложни типове данни като например структури от данни или стрингове от символи. Числовите данни в компютъра са 3 типа: цели числа ( числа с фиксирана точка ) , числа с плаваща точка, пакетирани десетични числа.

-при двоичната бройна система се използват две цифри за представянето на числата-

0 и 1;

-при 10-ичната – 10 цифри( от 0 до 9 )

-при 16-ичната – 0,1,...9, A, B, C, D, E, F

Еденици за информация

-бит – най-малката единица за информация в компютрите. В един бит може да се запише или „0” или „1”. Използва се за машинно представяне и обработка на данните и командите.

- Байт- единица за измерване на компютърната памет. Един байт се състои от 8 бита и може да съдържа един символ- буква, цифра или специален символ.

-по-окрупнени единици са:

1 Килобайт = 1024байта

1 Мегабайт = 1024 КБ

1 GB=1024МB

1TB=1024GB

Байтовете информация могат да се съхраняват или обработват поотделно или в групи, които съдържат фиксиран бр. байтове. Прието е 2 байта да се нарича една полудума, група от 4 байта една дума, а от 8 байта – двойна дума.

Битовете се съхраняват в специални устройства

-тригери – елект. Схеми

-феритни пръстени- пръстени, през които преминават проводници ж различни посоки. Биват използвани в ОП за съхраняване на битове до появата на микрокомпютъра.

-кондензатори- имат един недостатък-трябва постоянно да бъдат презареждани, защото има изтичане на заряди.

Представяне на данни в двоичен код

01001000- H, 01100101- E,

01101100-L и т. н.

Представяне на звук

Извършва се чрез така наречения метод на дискретизацията.

Стойностите се групират в специален пункт и след това се възпроизвеждат . Дискретизацията се характеризира с честота. Когато се изпраща звук( сигнал надалеч ) честотата е 8000 засичания/ секунда. А при съвременните CD е 44100 зас./сек. Данните за 1 засичане се запомнят в 16 бита, а ако звука е стерео в 32 байта. За една секунда звучене са нужни над 1мил. бита.

В музикалните синтезатори се използва др. с-ма –MIDI ( Musical Instrument Digital Interface ). Кодирането е значително по- икономично. Кодира се как да се възпроизведе сигнала ( инсрумент, нота, продълйителност на нотата ) = 3 байта

Подход на ISO- има експертна група за движещите се изображения ( Motion Picture Expert Group). Използва стандарт 12:1 за компенсиране на данни.

Представяне на изображения

Изображенията биват растерни и векторни. При растерните изображения за всеки пиксел се приписват цветове. Изображението се представя в 3 цвята- червен, син, зелен ( RGB ). Взема се принципа на цветната телевизия. Той взема трите цвята от анатомията на човешкото око, което по принцип вижда само три цвята, но с различнен интензитет. Има два формата:

-GIF- при него броя цветове, които могат да се приписват на един пиксел е 256 ( ограничен брой, за да може на 1 пиксел да се отделя 1 байт). Един от цветовете е прозрачен. Границите м/у цветовете е драстична. Той се използва в компютърните Games и анимациите.

-JPEG ( Joint Photographic Expert Group ) – има два метода:

1) без загуби – когато се иска предена точност; използва се относително кодиране. Помни се различието м/у отделните пиксели,а не в интензитета на цвета. Този метод не дава изображение, чийто пазмер може да се променя. Но дава най-доброто фотографско изображение .

2) базисен стандарт- при него за определяне на състоянието на пиксела се използват 2 параметъра- яркост и цвят. По-голяма роля играе яркостта. Това позволява да се намали размера на изображението. Има 4 ст-сти за яркост и 2 за цвят. При този формат двойно се намаляват ст-ст.

Относително кодиране- ако е даден базисен цвят, следващия цвят е изменението, т. е. само промяната в цвета.

-използва се и дискретно косинусово преобразувание

Векторно изображение- не се ориентираме по пиксели,а изчертаване образците ( обектът се представя чрез своите контури) . Използва се не само за анимации, но и при шрифтове True Type. Те са разработени от Apple Computer и Microsoft. Образът може да бъде уголемяван, намаляван, завъртян. Но качеството е лошо.

Представяне на логични данни:

Логическите операции в процесора са побитови. Следователно представянето на логическите данни трябва да бъде битово ориентирано, т. е. имат само две ст-сти: 1 ( true) и 0 ( false ).

Представяне на символи

Символите се представят чрез последователност от битове. Най-популярният код е ASCII код. При този код всеки символ се представя с последователност от 7 бита, при което е възможно използването на 128 комбинации. Една част от кодовете се използва за представяне на символите, останалата част се използва за кодиране на управляващи кодове. Кодираните символи се съхраняват и се предават в 8-битов формат, като осмият бит може да съдържа 0 или контролен бит за проверка по отчетност.


Едни и същи данни могат да бъдат третирани като числови, логически или символи. Типът на данните се определя от операциите, които се извършват с тях.


^ ВЪПРОС №3

Оперативна памет и външни запомнящи устройства

Оперативната памет е задължителна част от всеки компютър. Тя се състои от интегрални схеми, реализирани във вид на силициеви чипове, разположени върху специална платка. Тя е съставена от клетки, които имат вградени номера, наречени адреси. В нея се съхраняват данни и програми в процес на изпълнение.

Най-широко използваната вътрешна памет се нарича ^ RAM (Random Access Memory). Тази памет е уязвима или енергозависима, което означава, че при изключване на захранването нейното съдържание се изтрива. RAM паметта заема преобладаващата част на вътрешната памет. Това позволява тя постепенно да се презарежда с различни данни и програми – например от дискови запомнящи устройства според нуждите на потребителя. RAM паметта е с произволен достъп. Индивидуалните думи в паметта директно се четат или записват на съответния адрес. Технологията на RAM може да бъде статична или динамична. При статичните RAM памети битовите се съхраняват в тригери, тоест те имат регистрова структура. В общия случай статичните RAM памети са по-бързи от динамичните, но за сметка на това са по-скъпи и имат по-ниска плътност на компонентите. Динамичните RAM памети допускат висока плътност на компонентите, което означава, че те осигуряват по-голям капацитет на паметта в рамките на един чип. Динамичните RAM памети са изградени от запомнящи елементи, съхраняващи информация под формата на капацитивни заряди. Наличието на капацитивни заряди или отсъствието им се интерпретира като съдържание на бита – двоично 1 или 0.

^ ROM (Read Only Memory) – тя е енергонезависима памет, която не губи съдържанието си след изключване на захранването. Нейното съдържание не може да се променя, а само да се чете. Най-често тя се използва за съхраняване на най-често използваните програми. Поради серийното производство имат ниска цена.

Основни характеристики на паметта:

  1. Капацитет – измерва се в байтове или битове.

  2. Бързодействие – определя се от три основни параметъра:

А) време за достъп – интервала от време от момента на подаването на адрес към паметта до момента, в който данните са прочетени от или записани в паметта;

Б) цикъл – време за достъп до паметта + допълнително време, което трябва да измине преди да се стартира другия достъп;

В) скорост на трансфер – скоростта, с която информацията се подава от или приема в паметта.


В оперативната памет всеки символ се представя с така наречения ASCII код. При този код всеки символ се представя с последователност от 7 бита, при което е възможно използването на 128 комбинации. Една част от кодовете се използва за представяне на символите, останалата част се използва за кодиране на управляващи кодове. Кодираните символи се съхраняват и се предават в 8-битов формат, като осмият бит може да съдържа 0 или контролен бит за проверка по отчетност.

^ Външни запомнящи устройства

Външните запомнящи устройства съхраняват данни записани върху феромагнитни повърхности. Към тях спадат дисковите запомнящи устройства. Те служат за съхранение на програмни продукти и файлове с данни, които се прехвърлят на порции във вътрешната RAM памет, когато се наложи да се използват.

Дисковете са тънки плочи с феромагнитно покритие, които приличат на грамофонни плочи, но са по-малки. Информацията в тях не се записва спираловидно, а върху множество концентрични окръжности, наречени пътечки или писти. Обменът на данните между тях и ОЗУ се извършва посредством магнитни четящо-записващи глави. Те са толкова на брой, колкото е броя повърхности на магнитните дискове в пакета.

Твърдите дискови пакети имат повече от един диск с обща ос на въртене.

Четящо-записващите глави са закрепени една под друга към каретка, образвайки нещо като гребен, който при работа едновременно ги придвижва възвратно-постъпателно между въртящите се дискове. Всяка писта е разделена на еднакъв брой сектори. Секторът съдържа порция данни, която се чете или записва на диска за една входно-изходна операция. Четящо-записващите глави се преместват на следващата писта само след като се запълнят всички писти с еднакъв радиус, на които те са позиционирани. Пистите с еднакъв радиус на един дисков пакет се наричат цилиндри. За да се осигури достъп до даден сектор е необходимо да се зададе номера на дисковата повърхност, номера на пътечката и номера на сектора. В рамките на една пътечка се записват един и същ брой битове независимо от нейното разположение, така че гъстотата на битовете се увеличава в посока от външните към вътрешните пътечки.

Времеви параметри за дисковете:

  1. Скорост на въртене

  2. Seek time – време за търсене; средно време за позициониране на пътечка

  3. Rotation delay – колко време се изчаква до поява на определен сектор от пътечката. Най-много ½ оборот на диска.

  4. Access time – равно е на seek time + rotation delay

  5. Transfer rate – времето за предаване към/от диска



^ Флопи дискети –Представляват гъвкав пластмасов диск върху двете повърхности, на които е нанесено покритие от феромагнитен слой. За предпазване от замърсяване и механични повреди дискът е затворен или в картонен калъф – при 5.25 инчовите дискети, или в пластмасова кутия – при 3.5 инчовите дискети. С този калъф дискетите се поставят в дисковод (drive) и по определен начин чрез централната част се извършва въртеливо движение на диска в неподвижния калъф. Чрез индексния отвор се маркира началото на всяка писта. Достъпът на записващите и четящите глави до носителя се осъществява чрез специален отвор. Освен това на всяка дискета е направен изрез, чрез който се разрешава или забранява изпълнението на операция „запис”. Въртят се с 30 оборота/минута.

^ Компакт дискове(CD) – 600-700 MB запис. Компакт дисковете са такива носители, при които операциите за запис и четене се извършват с лазерен лъч върху фоточувствителен слой от диска. Обикновеното време за достъп при по-евтините устройства е между 300 и 700 ms, а скоростта на обмен – между 150 и 300 KB/s. Предлагат се и по-скъпи модели, при които тези стойности се доближават до твърдите магнитни дискове. Компакт дисковете имат трайност над 10 години. Повишената температура (над 100 градуса) и влажност не оказват влияние върху нормалната им работа. Има възможност върху един и същ компакт диск да се съхранява както цифрова, така и аналогова информация.

DVD – 4,7 GB. Данните се записват по спираловидна пътечка. Секторите са с еднаква дължина – по 2 KB за разлика от секторите на харддиска. Това означава, че се въртят с различна скорост. Колкото се доближава към центъра, толкова скоростта намалява, за да е еднаква минималната скорост на четене.

^ Магнитни ленти – не се използват по принцип днес. Ако се използват, то е само за архивиране на големи обеми информация. При тях достъпът е строго последователен и е свързан с механично движение. Бързо може да се позиционира на произволно място.

^ ВЪПРОС №4

Двоична бройна система – представяне на цели и дробни числа


1.Бройна система

Система от символи и правила за тяхната употреба, чрез които може да се изобрази всяко число. Символите на бройните системи се наричат цифри. Положението, което те могат да заемат при представяне на числото, се нарича позиция или разре. Отделните разреди се номерират последователно отдясно наляво, като най-младшият на цялата част на числото има нулев номер.

В математиката се използва десетичната бройна система. Изучаването на други бройни системи, различни от десетичната, се налага от специфичния начин, по който информацията се съхранява в паметта на компютъра. На този етап от развитието на изчислителната техника данните се представят чрез електрически сигнали и затова говорим за две възможни състояния – наличие на електрическо напрежение и липса на такова. Затова най-елементарното количество информация – битът – може да се представи като превключвател с две състояния – включено и изключено. За целите на програмирането тези две състояния се представят съответно чрез 1 и 0 (това е причината за използване на двоичната бройна система). Т.е. всяка една информация – числова, символна и т.н. – се представя, използвайки двоична бройна система. Широко приложение намира още и шестнадесетичната бройна система.

1.1 Видове бройни системи

Съществуват два вида бройни системи-позиционни и непозиционни. При непозиционните бройни системи количественият аквивалент, който се съпоставя на една цифра, зависи само от нейната стойност, но не и от нейното място в записа на числото. Непозиционна бройна система е римкста бройна система.

При позиционните бройни системи количественият еквивалент, който се съпоставя на някоя цифра, зависи от стойността на самата цифра, позицията, на която е разположена, и от основата на системата.

Броят на цифрите, които се използват за изобразяване на числата в дадена бройна система, се определя от нейната основа.

1.2 Преминаване от една бройна система към друга.
Преминаването от една бройна система към друга се извършва съгласно теоремата:

Всяко естествено число N може да се представи по един единствен начин във вида:
N = an.pn-1+an-1.pn-2+an-2.pn-3+.....+a2.p1+a1.p0
където а1, а2, ..., аn се наричат цифри на числото N, числото p се нарича основа на бройната система.
 Например нека да разгледаме десетичното число N=1267. Неговата стойност се получава по следния начин:
N=1267=1. 1000+2.100+6.10+7=
т.е. в този случай: а4=1, а3=2, а2=6, а1=7, р=10
Ако основата на бройната система е Р, то за запис на числата използваме цифрите 0, 1, 2, ..., Р-1. Например в десетична бройна система, чиято основа е 10, ние използваме цифрите 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. Аналогично, в двоична бройна система, чиято основа е 2, ще използваме само цифрите 0 и 1.
За да знаем дадено число в коя бройна система е записано, след числото като долен индекс в скоби се записва основата на бройната система, в която то е представено. Например, за да укажем, че числото 1011 е записано в двоична бройна система, пишем: 1011(2). Изключение прави само десетичната система, когато това обозначение обикновено се изпуска.

2. Правило за преминаване от p-ична бройна система в двоична бройна система за целите числа

1. Изходното число се дели на 2 до получаване на частно и остатък.

2. Проверява се дали не се е получило частно по-малко от 2, ако е така, се преминава към точка 4.

3. За изходно число се взема полученото частно. Връшаме се към точка 1.

4. Всички получени остатъци се записват в ред, обратен на получаването им. Полученият запис е запис на числото в 2-ична бройна система.

*в лекцията има пример с число.

3. Правило за преминаване от p-ична бройна система в двоична бройна система за дробните числа

1. Изходното число се умножава с 2. Цялата част се запомня.

2.проверява се дали броят на извършените до този момент умножения се равнява на броя на разредите, които по условие трябва да се намерят. Ако да-т.4, ако не-т.3.

3. дробната част на произведението се приема за ново изходно число и се преминава към т.1.

4. Всички цели числа се записват в такава последователност в каквато са получени. Този запис отговаря на 2-ичния запис на дробта с предварително зададена точност.

Когато число има цяла и дробна част, преминаването се извършва като се приложат двата алгоритъма съответно за цялата и за дробната 4аст.

4.Запис на числа с фиксирана запетая в ЦЕИМ

Числата с фиксирана запетая се записват, като запетаята се фиксира след най-малдшия разред, т.е. машината ще оперира само с цели числа. Ясно е, че тук се въвежда мащабен коефициент, с помощта на който изходните данни, междинните данни и крайните величини остават винаги цели числа. Данните с фиксирана дължина могат да бъдат с дължина една дума(32 бита) или една полудума(16 бита). И при двата формата обаче най-старшият разред на клетката(разред 0) съдържа знака на числото. Останалите разреди(от 1 до 15 или от 1 до 31) са абсолютната стойност на числото. Прието е за положително число да се използва символът 0, а за отрицателно – 1. Положителните числа с фиксирана запетая се записват в прав код, а отрицателните – в допълнителен код. Правият код е кодът на самото число. Допълниелният код се образува, когато самото число се инвертира и към най-младшия му разред се прибави 1.

4Запис на числа с плаваща запетая в ЦЕИМ

Аритметиката с плаваща запетая улеснява програмирането чрез автоматичното записване на запетаята на подходящото място, което е особено удобно за изчисления, при които обхватът на използваните числа е много широк или предварително не е известен. В основата на представянето му стои отделянето на значещите цифри на числото от неговата размерност или числото се записва като произведение от мантисата му и степен с основа 16.



По такъв начин на числото с плаваща запетая съответстват две множества от стойности. Едното множество има за елементи всички набори от значещи цифри на числото и се нарича мантиса. Второто множество посочва степента, на която се повдига основата 16 и по този начин посочва мястото на запетаята в числото. Двете множества се записват във формати с дължина една или две две думи. Всяко от множествата има отделен знак, като трябва да се използва и метод за отразяване на двата знака. Това се постига като знакът на мантисата са взема за знак на съответната дума (или двойна дума), а порядъкът се представя в аритметика с излишък 64. това означава, че порядъкът се прибавя като число към 64. числото, което се получава в резултат на това прибавяне се нарича характеристика.

ВЪПРОС №6

Компресиране на данни



1.Същност

Компресирането на данни е едно от основните проявления на теорията на информацията. Тя е клон на математиката, водеща началото си от работата на Клод Шенън в Bell Labs през втората половина на 40-те години, където той разглежда различни въпроси, свързани с информацията като метод на възникване, съхраняване и предаване. Копресирането на данните е част от Теорията на информацията, тъй като се занимава с излишеството на информация в дадено съобщение. Излишната информация в едно съобщение ни принуждава да използваме повече битове за неговото кодиране. Ако можа да се премахне излишеството, ще се намали размерът на съобщението. Теорията на информацията използва термина ентропия като мярка колко информация е закодирана в дадено съобщение. Колкото е по-висока ентропията на дадео съобщение, толкова по-голямо е информационното му съдържание. Ентропията на дадео съобщение се дефинира като отрицателен логаритъм при основа две. Ентропията на цялото съобщение е сумата от ентропиите на всички символи в съобщението.

Забележително е, че тези първи разработки са направени много преди възникването на съвременния компютър, затова идеята за създаването на алгоритми, базирани на двоичната бройна система е огромен скок в науката. За да се измери нивото на компресията, трябва всички алгоритми да се поставят в еднакви условия. Те компресират един едни и същи файлове, които се разделят на три големи групи:

1.Текст – бележки, ръкописи, програмен код и друга текстова информация.

2.Двоични данни – таблици, изпълними файлове, бази данни.

3.Графична информация.

Алгоритмите се групират по три показателя:

1.Времето, необходимо за компресиране на даден файл.

2. Нивото на компресия на целия пакет от файлове – текстове, двоични и графични.

3. Ниво на загуба на качество при компресиране на данните.

Методите за компресия на данните могат да се разделят най-общо на две основни области - със и без загуба на информацията. При компресирането със загуби се губи известна част от информацията за сметка на многократно увеличаване на компресията. То се указва много полезно при компютърната обработка на графика и на цифровата обработка на музика. Повечето от тези методи могат да се настройват на различни нива на качество, като по-високо качество на представянето се извършва за сметка на по-ниска степен на компресия. И обратно, по-висока степен на компресия води до по-лошо качество. Подборът на настройките зависи изцяло от предназначението на конкретната информация.

Методите за компресиране без загуби на информация са, тези които гарантират, че при цикъла компресиране/декомпресиране изходните и входните данни ще съвпадат. Това са програми, които се използват за архивиране на програмен код, бази данни, електронни таблици, текстови документи. При подобни приложения, дори загубата на един бит може да доведе до катастрофални последици.
Най-общо казано компресирането на данни се състои в превръщане на потока входни данни в кодове. Ако компресирането е ефективно, то полученият поток от кодове е по-кратък от входящия поток данни.

Решението определен знак или поредица от знаци от входните данни да бъдат съпоставени с определен код се базира на модел. Компресирането може да се разгледа като Моделиране плюс Кодиране. Моделът е прост набор от правила и данни как да се обработват и съпоставят определени кодове на отделните знаци. Програмата използва модела за да определи вероятността на всеки символ и кодиращия алгоритъм, за да получи съответния код, базиран на тези вероятности.

Има няколко широкоразпространени метода за кодиране ка информация, като всеки от тях има конкретни предимства и недостатъци.

2. Методи за кодиране на информация

2.1 Кодиране дължината на серията (run-length encoding)

Това е метод за намаляване размера на повтарящи се поредици от знаци. Обикновено RLE използва два байта за представянето на един знак – брой повторения и самия знак. RLE може да се използва върху произволни данни, но техният тип влияе върху коефициента на компресията. Обикновено RLE не води до високи нива на компресия, но е бърз за изпълнение и алгоритъмът му се имплементира много лесно.

Пример:

АААААААААААААААААААА →след кодиране→20А, което отнема само два байта. Коефициентът на компресия е много голям.

ABCD→ след кодиране→1A1B1C1D→размерът вместо да намалява се увеличава.

Ако компресираните данни не съдържат достатъчно дълги поредици от повтаряеми знаци, коефициентът на компресия може да падне до 1.

2.2 Относително кодиране(relative encoding)

При него се записват разликите между два блока от информация, а не самите блокове. Може да се прилига ефективно при приложения с последователно регистриране на данни.

2.3 Честотно кодиране(frequency dependent encoding)

Ако някой символ се среща по-често, той трябва да има съкратен код. Например буквите, които се използват по-често имат определен код. Развитие този метод получава прз 40-те години на миналия век във връзка с надеждността на релетата. Системата от кодове се нарича Кодове на Хъфман. Основната идея е, че най-чесо срещаните символи в поредицата се записват с най-малък брой битожа. . Хъфмановите кодове имат свойството уникалност, което означава, че могат еднозначно да бъдат декодирани независимо от различната си дължина. Декодирането става чрез декодиращо двоично дърво, което се построява в посока от корена към листата.
Използването на този метод води до създаването на нова азбука, която използва този метод. Кодирането е обратимо.

2.4 Метод на Lempel Ziv encoding

Той е свързан с кодиране с адаптивен речник, всъщност е подход, който се реализира чрез използването на много други методи. Основан е на изследванията на Лемпел и Зив и намира развитие чрез два сходни алгоритъма за речниково кодиране - LZ77 и LZ78. Първият е с плъзгащ прозорец, при който речникът се състои от множеството от фрази с фиксиран размер, открити в "прозорец" към вече прочетения текст. LZ78 подхожда по съвсем различен начин към съставянето на речника. Вместо да използва фрази с фиксирана дължина, към вече прочетения текст, LZ78 увеличава дължината на фразата при всяко следващо нейно срещане в обработвания текст или пакет от данни.

2.4Адаптивен метод с речници

Понастоящем повечето използвани статични речници методи се използват за тясно специализирани дейности, което обяснява защо по-извените речникови схеми използват адаптивни речници.Вместо да започва компресирането с вече готов речник, адаптивните методи започват или от нула или с минимално готов речник.. В процеса на компресиране се добавят нови и все по-нови изрази (или фрази), които в последствие се заместват с подходящи кодове, които са свързани с вече протеклото кодиране.
ВЪПРОС №7

Контролни и коригиращи кодове

1. Същност

Това са контролиращи кодове или за корекция на грешки наречени коригиращи кодове. Всеки коригиращ код е и контролиращ.

Ако приемем, че предавателя предава само разрешени комбинации, а в приемника се получи забранена информация, това означава, че при предаването (запомнянето) е възникнала грешка и информацията не трябва да се използува. Това е процедура за откриване на грешката.

Ако чрез обработка на забранената комбинация в приемника, по определен алгоритъм, се получи разрешена информация, това означава че информацията е коригирана и може да се използува. Тази процедура се нарича коригиране на грешката.

Както е известно, един символ отоваря на 4 байта. В такъ случай между два кода не може да има по-малко от 3 различни по стойност бита. Това разстояние се нарича разстояние на Хеминг.


2.Код на Хеминг.

Кодът на Хеминг е един от най-ефективните кодове за отстраняване на единични грешки. Кодовото разстояние е d = 3. Кодът се образува като към към информацонната част, съставена от k бита се добавят r контролни бита. В информационната част могат да бъдат включени и служебни символи (номер, начало и край на предавания блок). При избора на дължината на предавания блок n трябва да се отчита неравненството

,

откъдето при r = n – k неравенството може да се запише:



Правилото, по което се формира кодът на Хеминг е следното:

Първият проверочен елемент (бит) П1 се образува като се сумират по модул 2 (операция изключващо ИЛИ) всички нечетни битове на блока:

П1 = a1 + a3 + a5 + a7 +….

Вторият проверочен бит се получава чрез сумиране на тези битове от блока, чиито номера съответстват на n-разрядно двоично число, което съдържа 1 във втория разряд:

П2 = a2 + a3 + a6 + a7 + a10 + a11+….

Третият проверочен бит се получава чрез сумиране на тези битове от блока, чиито номера съответстват на n-разрядно двоично число, което съдържа 1 във третия разряд:

П3 = a4 + a6 + a7 + a12 + a13 + a15 +….

Аналогично се определят четвъртият, петият и т.н. проверочни бита.

Мястото на разпологане на проверочните битове няма значени – те могат да се разпологат пред или след информационните битове, както и между тях. Ако се разположат на места, кратни на степените на 2, т.е. на позиции 1, 2, 4, 8 и т.н. В последния случай кодът на двоичното число, образувано от проверочните битове показва номера на разряда, в който е станала грешката, при което тя може да се коригира.

Можем да откриваме до 2 грешки, защото от 3 нагоре е разстоянието, но може да коригираме само по 1 грешка. Ако искаме да откриваме и съответно да коригираме повече грещки, трябва да увеличим разстоянието на Хеминг.

3.Контрол по четност/нечетност.

Един от най-простите методи за откриване на грешки е методът за контрол по четност или нечетност. При предаване на информация по т.н. последователен способ т.е. бит по бит след информационните битове се предава бит за контрол по четност (или нечетност) bp, който се установява в 1 или 0 за да допълни броя на единиците до четно (или нечетно) число и може да се определи съгласно логическото уравнение:

bp = b0  b1  b2  b3  b4  b5  b6  b7

При 7 информационни бита и 1 контролен бит коефициента на излишък е 1/8.

При сложните преобразувания на информацията (като например прекодиране) вероятността за грешка нараства, но последиците от нея са фатални, когато грешното съобщение се приеме за вярно и компютъра продължи работата си с грешните данни, които ще дадат грешен резултат без това да се регистрира от системите за обработка на грешки. Ако приемника раздели приетите съобщения на разрешени (верни) и на забранени (грешни), тогава само верните данни ще се обработват и ще дават верни резултати.


следующая страница >>