Тізімдер. Циклдік тізімдер. Ортогоналды тізімдер 8 страница

⇐ ПредыдущаяСтр 8 из 15Следующая ⇒

Біздің мысалда (2-кесте, e3, e2 және e1 бағандарында) барлық ішкі күй кодтары s1_2 және s3 күйлерін қоспағанда өзара ортогоналды болып табылады. Сондықтан олардың айырмашылығы үшін e0 коэффициентіне сәйкес келетін e0 коды сәйкес келетін, қосымша кодты енгізеді, e0 санымен s1_2, «1» мәнімен кодталады және «0» мәні бар s3 күйі. Е0 бағанының қалған жолдарындағы мəселелер мəселенің шешілуіне əсер етпейді жəне сенімділік үшін нөлге келтірілуі мүмкін. С класындағы автоматтың ішкі күйлерін кодтау және оны шешу әдістері туралы мәселені неғұрлым қатаң түрде тұжырымдау [9] келтірілген. С класындағы автоматтың ішкі күйлерінің кодтары ретінде матрица В-ның тиісті жолдарының мәндері алынды.Верилогтағы C автоматының сипаттамасы біздің мысал үшін 5-листеде келтірілген.

module FSM_C_2 (input clk, reset, // синхросигналисигналсброса in, // входнаяпеременная output [2:0] out); // тривыходныепеременные reg [3:0] state, next; // настоящееиследующее // состояние localparam [3:0] s0=4’b000_0, // кодысостояний s1_1=4’b001_0, s1_2=4’b100_1, s2=4’b010_0, s3=4’b100_0,a s4=4’b011_0; always @(*) // первыйпроцесс (* full_case, parallel_case *) casex (state) s0: if (in) next=s1_1; else next=s2; s1_1: if (in) next=s3; else next=s2; s1_2: if (in) next=s3; else next=s2; s2: next=s3; s3: next=s4; s4: if (in) next=s1_2; else next=s0; endcase always @ (posedge clk) // второйпроцесс if (!reset) state <= s0; else state <= next; assign out=state[3:1]; // определениезначенийвыходов endmodule Листинг 5. Описание автомата класса C на языке Verilog для автомата на рис. 7

Орындалған эксперименталдық зерттеулер FPGA-де ақырғы автоматтың іске асырылуында, сонымен қатар жылдамдықта және C жылдамдықта да C класс автоматының құрылымдық моделінің жоғары тиімділігін көрсетті. Дегенмен, C класс автоматының моделін қолдану үшін түпкілікті автомат операцияның басында бір реттік кідіріспен жұмыс істейтін және бастапқы күйге қайтарылған жағдайда жұмыс істейтін Мур типіне ауысуы керек. Бұл жағдайда C кластың автоматикасының моделін қолданған кезде ескеру керек. D класс автоматының моделі де өте тиімді және C сыныбының автоматикасынан айырмашылығы кез-келген түпкілікті автоматқа қолданылуы мүмкін.

Ұсынылған жұмыста соңғы күйдегі машинаның шығыс айнымалы мәндерінің ішкі күйлерін кодтау үшін пайдаланылған, бірақ осы мақсат үшін кіріс айнымалы мәндерінің мәндері де пайдаланылуы мүмкін. Сондықтан, соңғы автоматтың ішкі жай-күйінің кодтары ретінде кіріс айнымалы мәндерінің мәндерін, сондай-ақ екі әдісті біріктіру мүмкіндігін зерттеу мүмкіндігін қарастырады.

Жұмыс Белосток техникалық университетінің (Польша), S / WI / 1/2013 грантының жартылай қаржылық қолдауымен жүзеге асырылды.

БИЛЕТ -10

Стектер, кезектер және дектер.

Стек (англ. stack — бума) — деректер құрылымы, LIFO (англ. last in — first out, «Соңынан шығып — бірінші кіру») принципі бойынша ұйымдастырылған элементтер тізімінен тұрады.

Аппаратты стек

Стек шақыруларды және қайтаруларды үзу кезінде (ыңғайлы си тілі функциясының локальды аймағын қараңыз) немесе жадыда уақытша деректерді сақтау кезінде қолданылады (айнымалылар, функциялар параметрлері).

Программалы стекСтектің программалы түрі деректер құрылымын тексеруде қолданылады, мысалы, ағаш немесе граф.

Рекурсивті функцияларды пайдаланғанда да аппаратты стек қолданылады. Бұдан басқа тағайындалған стек стекті машиналарды ұйымдастыруда пайдаланылады. Ішкі программалардың қайту нүктесін зерттеуде шақыру стектері пайдаланылады. Арифметикалық сопроцессорлар мирокалькуляторларды программалайды және Forth тілі есептеудің стектік моделін пайдаланады.

Кезек (файл) - біртекті реттелген динамикалық құрылым. Кезек дегеніміз сызыкты реттелген бірінен кейін бірі орналасқан, екі жету әдісі бар қүрылым, ол жету ережелері: Жазу В: B. name B. number B. length “байт” 16 35.6

а) жаңа компонент кезектің тек соңына қосыла

алады;

b) компоненттердің мәні тек қана басынан

аяғына орналасу бағытында ғана оқылады.

Негізгі қасиеттері:

· өлшемі алдын - ала келісілмеген;

· компоненттерін сақтау үшін сыртқы сақтауқұралдары қолданылады;

· кезекке компонент қосу және алу "бірінші кірген –бірінші алады" ("ҒІҒО") принципі бойынша жүзегеасырылады.

Дек(deque) – екі жақты кезек. Дек контейнері вектор контейнеріне өте ұқсас. Дек ол динамикалық массивтер. Дек пен вектор айырмашылығы, дек екі жағынан да ашық,сондықтан элементтерді алдынан да, соңынан да тез қосуға болады, ал векторларда тек соңынан ғана қосуға болады.

Байланыс сұлбасы. Байланыс түрлері.

Байланыстарды байланыстардың дәрежесімен және мәндердің байланысқа тиістілік кластарымен сипаттайды. Байланыстың дәірежесі (қуаты) – бұл байланысты құруға қатысатын түпмәндер санының бір – біріне қтынасы. М/ы, «бірден бірге» (1:), «бірден көпке» (1:К) және «көптен көпке» (К:К) түріндегі. Ақпараттық модельдің деңгейінде анықталмаған және шешілмеген байланыс болуы мүмкін. Түпмәннің тиістілік класы түпмәннің байланысқа қатысуының сипатын білдіреді.

Түпмәннің байланысқа тиістілік класының 2 түрі бар: міндетті және міндетті емес. Міндетті тиістілік класы деп түпмәннің экземплярлары байланыс орнатуға міндетті түрде қатысатын класты айтады. Ал керісінше жағдайда түпмән міндетті емес класына жатады.

Міндетті емес тиістілік класының түпмәнінің байланыс дәрежесі нөлге тең, яғни түпмәннің экземплярын басқа түпмәннің 0,1 немесе бірнеше экземплярымен байланыстыруға болады.міндетті тиістілік класының байланыс дәрежесі нөлге тең болмайды.

Түпмәннің өзін өзімен байланыстыратын қатынасты рефлексивті деп атайды. Мұндай рефлексивтң қатынастың мысалы ретінде, «Қызметкерлер» қатынасындағы бағыныштылық құрылымын анықтауды айтуға болады. Рефлексивті қатынастар көбінесе деректер құрылымының ішіндегі иерархиялық қатынастарды бейнелейді. Олар жобалаудың бірнеше проблемасын тудырады.

Қатынастардың түрғысынан әлсіз түпмәндер болады. Әлсіз түпмәндер– бұл олармен байланысқан басқа түпмәндерді экземплярлары пайда болмайынша деректер базасында бола алмайтын түпмәндер. Мұндай түпмәннің мысалына «Тапсырыс» жатады, ол «Клиентсіз» бар бола алмайды. Әлсіз түпмәндердің міндетті тиістілік класы болады және мұндай түпмәннің байланыс дәрежесі нөлге тең болмайды. «Тапсырыс – Клиент» байланысты міндетті тиістілік класына жатады.

Әлсіз түпмәндерді және олармен байланысқан міндетті қатынастарды анықтау деректердің бүтіндігінің келіспеушілігін қамтамасыз ету үшін қажет. М/ы, белгісіз клиентке тапсырыс жаза алмаймыз.

Ақырлы автоматтардың тізбекті және параллель декомпозициясы.

Жалпы жағдайда ыдырау арқылы реферативті автоматтың бірнеше қарапайым автоматтың жиналуын білдіреді. Ең қарапайым жағдайда біз параллель, дәйекті немесе аралас жұмыс істейтін автоматқа ыдырауды қарастырамыз. Жалпы жағдайда бұл әрқашан мүмкін емес.

Реферат автоматының ыдырау мәселесі алгебралық операцияларда автоматтың ыдырау мәселесі ретінде тұжырымдалуы мүмкін. Сондықтан дерексіз автоматта ресми операциялардың қасиеттерін зерттеу маңызды. Көбейту, автоматтандыруды алгебралық операциялардың міндеттерін қарастырыңыз.

Операция умножения автоматов И содержательно соответствует параллельной работе автоматов и (рис. 7.11). Отсюда следует, что входной сигнал соответствует паре и то же можно сказать о выходном сигнале.

Рис. 7.11. Иллюстрация операции умножения

Рис. 7.12. Графы автоматов и

Различают два типа умножения. Первый, обозначаемый , применяется для автоматов, у которых . Второй тип, обозначаемый , соответствует случаю .

Пусть автоматы И заданы графами на рис. 7.12, причем оба они инициальные с начальными состояниями (для ) и (для ) или для автомата это состояние задается парой Если приходит сигнал То параллельная работа автомата приводит к состоянию (см. рис. 7.12) ( ) с выходным сигналом ( ). Если проанализировать все комбинации выходов и состояний, то получим граф автомата на рис. 7.13.

Рис. 7.13. Граф автомата

Если теперь ввести алфавиты для полученного автомата , получим:

Теперь граф автомата принимает вид как на рис. 7.14.

Рис. 7.14. Модифицированный граф автомата

Вторая операция умножения Соответствует параллельной работе автоматов И с одним выходом (рис. 7.15).

Рис. 7.15. Иллюстрация операции умножения

Для примера воспользуемся графами автоматов И (рис. 7.12) и составим алфавит составного автомата:

Тогда, полагая, что автоматы И инициальные с начальными состояниями И , получим граф автомата (рис. 7.16).

Рис. 7.16. Граф автомата

Операция суммирования автоматов И соответствует автомату с параллельной неодновременной работой автоматов И , когда любое входное слово для автомата образуется чередованием входных букв автоматов и . Точно так же выходное слово для автомата - это чередование выходных слов И . В этом случае выходное слово можно представить последовательностью Где прочерк означает отсутствие входного сигнала на соответствующий автомат. Последовательность такой же структуры будет и на выходе автомата .

Для рассматриваемой операции для автоматов И из рис. 7.12 можно получить граф переходов, представленный на рис. 7.17, где обозначения: Входной сигнал На автомате , а Выходной сигнал На автомате .