Авиационно инженерство Административно право Административно право Беларус Алгебра Архитектура Безопасност на живота Въведение в професията „психолог” Въведение в икономиката на културата Висша математика Геология Геоморфология Хидрология и хидрометрия Хидросистеми и хидравлични машини Културология Медицина Психология икономика дескриптивна геометрия Основи на икономически т Oria професионална безопасност Пожарна тактика процеси и структури на мисълта, Професионална психология Психология Психология на управлението на съвременната фундаментални и приложни изследвания в апаратура социалната психология социални и философски проблеми Социология Статистика теоретичните основи на компютъра автоматично управление теория на вероятностите транспорт Закон Turoperator Наказателно право Наказателно-процесуалния управление модерна производствена Физика Физични феномени Философски хладилни инсталации и екология Икономика История на икономиката Основи на икономиката Икономика на предприятията Икономическа история Икономическа теория Икономически анализ Развитие на икономиката на ЕС Спешни ситуации ВКонтакте Однокласници Моят свят Facebook LiveJournal Instagram
border=0

Общи подходи към описанието на устройствата за обработка на дискретна информация

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

Тъй като устройството комуникира с външната среда, очевидно, то трябва да има входен канал, през който да постъпва информация в него, както и изходен канал, през който се извежда резултатът от преобразуването. В допълнение, устройството може да има памет, в която е фиксирано неговото текущо състояние; Резултатът от обработката обикновено се определя от входните ефекти и вътрешното състояние на устройството. Предполагаме, че за представяне на входната информация се използва някаква крайна азбука X (входна азбука), а крайната азбука Y (изходна азбука) се използва за представяне на изходната информация . Както беше отбелязано по-рано, изискването за крайността на азбуките е следствие от крайността на времето за обработка на информацията. Вътрешните състояния на устройството също образуват дискретен набор, който може да се счита за вътрешна азбука - го обозначаваме с Q. Що се отнася до броя на различните вътрешни състояния, ние няма да правим никакви предположения по отношение на него.

Предполагаме също, че въвеждането на входни символи и превключването на състояния на устройството не се случват непрекъснато, а в определени моменти във времето, т.е. дискретно. Ако последователността от моменти е произволна, тогава ние говорим за асинхронната организация на работата на елементите на устройството, например, набиране на телефонен номер или код за заключване. В сложните устройства обаче по-често се използва синхронна организация, в която моментите на пристигане и излизане на сигналите, както и превключването на вътрешните състояния следват един и същ фиксиран интервал от време =t = const, наречен такт. Тези моменти се задават с помощта на специално устройство - часовник генератор (или часовник генератор). Броят на тактовите импулси за единица време се нарича тактова честота - това е един от най-важните фактори, определящи скоростта на устройството. Можете да въведете времето t 0 , t 1 , t 2 , ..., обозначавайки границите на кърлежи (t 0) съответства на началото на работата). В този случай можем да приемем, че събитията, свързани с цикъл i - пристигане на входния символ, промяна във вътрешното състояние, генериране и извеждане на изходния символ - се появяват незабавно в момента t i .

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

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

· Информационно - справочни автомати, електронни табла, светофари, алармени устройства и др .;

· Мениджъри - кодирано заключване, устройство за управление на асансьори, програмируеми машини, микропроцесори за камери, видео и др .;

· Компютърни - калкулатор, микропроцесори на компютри.

Има устройства, които извършват дейностите на трите вида, например компютър, автопилот и др.

За нашето разсъждение е важно изходните символи и вътрешните състояния на такова устройство да се окажат дискретни функции на входните символи и номера на работния цикъл. Въвеждаме концепцията за функцията на преходите Y , която ще свързва вътрешното състояние на устройството при следващия цикъл с състоянието и входния символ в текущия цикъл:

С други думи, преходната функция показва състоянието на дискретното устройство от всички възможни Q , ако е било в състоянието q i , и входният символ x i е получен.

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

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

Казва се, че петте от компонентите <X, Y, Q, Θ, Θ> задават автомата, който осигурява преобразуването според определени правила на последователностите от знаци на входната азбука в изходната последователност. Всъщност, ако приемем първоначалното условие q 1 = q 0 , тогава рекуррентните отношения (9.1) и (9.2) определят реда на преобразуване на крайната последователност на входните символи x 0 , x 1 ..., x n в някаква последователност от изходни символи с една и съща дължина y 0 , y 1 , ... y n ; в същото време ще възникне определена последователност от вътрешни състояния q 1 , q 2 , .... Това е функционирането на машината. Изходният символ, произведен от автомата при определен цикъл i , зависи не само от входния символ, възприет при същия такт, но и от по-рано получените символи - те се фиксират в автомата чрез промяна на неговото вътрешно състояние. В този смисъл, наборът от вътрешни състояния на автомата е неговата вътрешна памет. В зависимост от размера на тази памет се разпределят следните типове автомати:

· Без памет;

· С максимална памет;

· С безкрайна памет.

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

Що се отнася до дискретни устройства с безкрайна памет, това е чисто моделно теоретично представяне, тъй като нито едно истинско устройство не може да притежава безкрайна памет. Пример за автомат с безкрайна памет е машината на Тюринг, в която, както е посочено в раздел 7.3.3, ролята на паметта се играе от безкрайна (или, ако е необходимо, разтегателна) хартиена лента в двете посоки. По този начин можем да приемем, че автомат с безкрайна памет е алгоритъм, представен под формата на машина на Тюринг. Тъй като въпросите, свързани с функционирането на машините на Тюринг, вече са били разглеждани по-рано, те няма да бъдат обсъждани в тази глава.

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

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

второ, изследват се еквивалентни трансформации на автомата; проблемът за еквивалентната трансформация се състои в конструиране на автомат, еквивалентен на даден, но с различен брой състояния (обикновено по-малък);

на трето място, се разглеждат редица въпроси, при които структурата на автомата се определя от естеството и съотношението на входните и изходните сигнали (автомат - „черна кутия“) - това е важна приложна задача на техническата диагностика на устройства, без която практическото им функциониране е невъзможно;

Четвърто, се подчертават структурните елементи на автомата и се дефинират правилата за конструиране на сложни устройства от тях (задачата за синтез на автомати) - с това се свързва развитието на нови автомати, по-специално компютри.

Важен случай за практиката е автоматът, в който цялата информация е представена с помощта на двоичен код, т.е. Буквите X, Y и Q са двоични - такива автомати се наричат двоични или логически. Последното име се дължи на факта, че както теорията показва, при двоично кодиране, всеки краен автомат може да бъде представен като комбинация от определен брой елементи, които изпълняват AND, OR, NOT логически операции, както и елементи на паметта (закъснение и тригер). Съединението на елементите се нарича логическа схема. Две обстоятелства са важни: първо, работата на логическите схеми може да бъде описана от законите и правилата на математическата логика (т.е. резултатът от действието на логическата схема се свежда до изчисляване на стойността на логическия израз); второ, всеки краен автомат може да бъде конструиран от този малък набор от елементи.





Вижте също:

Блоково двоично кодиране

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

Пример 3.1.

Пример 7.12

Пример 7.6

Връщане към съдържанието: Теоретични основи на компютърните науки

2019 @ ailback.ru