Сортировка массива чисел по возрастанию

Федеральное государственное бюджетное образовательное  учреждение высшего профессионального образования "Московский  государственный технический университет  радиотехники, электроники и  автоматики" МГТУ МИРЭА

Факультет Кибернетики

 

КУРСОВОЙ ПРОЕКТ
по  дисциплине
«Микропроцессорные устройства  управления роботов и их программное обеспечение»
Тема курсового проекта «Сортировка массива чисел по возрастанию»
Руководитель курсового проекта доцент, к.т.н.	Герасимов В. В.
Рецензент

 

Работа представлена к защите	«12» мая 2012 г.
«Допущен к защите»	«14» мая 2012 г.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Москва 2012

 

Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования "Московский  государственный технический университет  радиотехники, электроники и  автоматики" МГТУ МИРЭА
Факультет Кибернетики
		Утверждаю
		«____» __________201___ г.
ЗАДАНИЕ
на выполнение  курсового проекта
по дисциплине «Микропроцессорные устройства  управления роботов и их программное обеспечение»
Студент
Тема «Разработка алгоритма и программы сортировки массива из 20 чисел по возрастанию»
Исходные данные:
13h, 11h, 01h, 17h, 07h, 03h, 21h, 32h, 32h, 12h, 42h, 34h, 22h, 14h, 55h, 11h, 17h, 77h, 31h, 12h.
Перечень вопросов, подлежащих разработке, и обязательного графического материала:
алгоритм (рис 1), программа, блок-схема  алгоритма
Срок представления к защите курсового проекта (работы): до «12» мая 2012 г.
Задание на курсовой проект, выдал	«12» апреля 2012г.
Задание на курсовой проект, получил	«12» апреля 2012г.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Содержание:

Введение            4

Основная часть           5

Блок-схема алгоритма работы программы      7

Алгоритм работы программы         8

Листинг программы          9

Результаты выполнения программы              12

Заключение                           13

Список литературы                                                                                                                            14

 

 

Введение

 
Программы можно писать не только для x86 компьютеров. Более того, большая  часть процессоров в мире - НЕ x86. Основная часть микропроцессоров сейчас - это микроконтроллеры. В большинстве учебных заведений бывшего СССР изучение микроконтроллеров начинается с легендарного Intel 8051 (официальное название - MCS 51, также он известен как i8051 и MCS-51). У этого микроконтроллера есть assembler, очень похожий на ассемблер привычных нам процессоров x86 архитектуры. Этот контроллер применялся в старых клавиатурах, да и вообще много где он применялся. Будем называть этот микропроцессор Intel 8051 или MCS 51, потому что во всем мире он известен именно под этим названием.

 

Цель работы:

Необходимо отсортировать  по возрастанию массив из 20 шестнадцатеричных  чисел. Чтобы это сделать надо найти максимальный элемент и  поместить в конец массива, потом  второй по величине и поставить его  на предпоследнее место массива и т.д.

Особенности микроконтроллера

 
Intel 8051 — это 8 разрядный однокристальный микроконтроллер гардвардской архитектуры, впервые произведенный компанией Intel в 1980 году и предназначенный для использования во встраиваемых (embedded) системах. Он состоит из процессорного ядра (CPU), ОЗУ, ПЗУ, последовательного и параллельного порта, и еще небольшого количества дополнительных элементов. Программы для него можно писать на специализированном ассемблере, который очень напоминает ассемблер для x86-процессоров, или на языке С. Но, конечно, есть ограничения. У нас в распоряжении всего 128 байт ОЗУ (называется память DATA), 4 кбайта встроенного ПЗУ для хранения самой программы (память программ), и 64 кбайта в ПЗУ (называется XDATA - external data, или память данных). Зато есть прерывания.

 

 

 

 

 

 

 

 

 

 

 

Основная часть

Восьмиразрядные  высокопроизводительные  однокристальные  микроЭВМ (ОМЭВМ) семейства  МК51 выполнены по высококачественной n-МОП технологий (серия 1816) и КМОП технологии (серия 1830) .

Семейство МК51 включает пять модификаций ОМЭВМ (имеющих  идентичные основные характеристики), основное различие, между которыми состоит в реализации памяти программ и мощности потребления.

ОМЭВМ КР1816ВЕ51 и КР1830ВЕ51 содержат масочно-программируемое в процессе изготовления кристалла ПЗУ памяти программ емкостью 4096 байт и рассчитаны на применение в массовой продукции. За счет использования внешних микросхем памяти общий объем памяти программ может быть расширен до 64 Кбайт.

ОМЭВМ КМ1816ВЕ751 содержит ППЗУ емкостью 4096 байт со стиранием ультрафиолетовым излучением и удобна на этапе разработки системы при отладке программ, а также при производстве небольшими партиями или при создании систем, требующих в процессе эксплуатации периодической подстройки. За счет использования внешних микросхем памяти общий объем памяти программ может быть расширен до 64 Кбайт.

ОМЭВМ КР1816ВЕ31 и КР183ОВЕ31 не содержат встроенной памяти программ, однако  могут  использовать  до  64  Кбайт  внешней  постоянной  или  перепрограммируемой памяти программ и эффективно использоваться в системах, требующих существенно большего по объему (чем 4 Кбайт на кристалле) ПЗУ памяти программ.

Каждая из перечисленных выше микросхем  является соответственно аналогом БИС 8051, 80С51, 8751, 8031, 80С31 семейства MCS-51 фирмы Intel (США).

Каждая ОМЭВМ рассматриваемого семейства содержит встроенное ОЗУ  памяти данных емкостью 128 байт с возможностью расширения общего объема оперативной памяти данных до 64 Кбайт за счет использования внешних микросхем ЗУПВ.

Общий объем памяти ОМЭВМ семейства  МК51 может достигать 128 Кбайт: 64 Кбайт  памяти программ и 64 Кбайт памяти данных.

При разработке на базе ОМЭВМ  более сложных систем могут быть использованы стандартные ИС с байтовой организацией, например, серии КР580. В дальнейшем обозначение "МК51" будет общим для всех моделей семейства, за исключением случаев, которые будут оговорены особо. ОМЭВМ содержат все узлы, необходимые для автономной работы:

1) центральный восьмиразрядный  процессор;

2) память программ объемом 4 Кбайт (только КМ1816ВЕ751, КР1816ВЕ51 и КР1830ВЕ51);

3) память данных объемом  128 байт;

4) четыре восьмиразрядных программируемых  канала ввода-вывода;

5) два 16-битовых многорежимных  таймера/счетчика;

6) систему прерываний с пятью  векторами и двумя уровнями;

7) последовательный интерфейс;

8) тактовый генератор.

 

Аккумулятор. АСС — регистр аккумулятора. Команды, предназначенные для работы с аккумулятором, используют мнемонику "А", например, MOV А, Р2.Мнемоника "АСС" используется, к примеру, при побитовой адресации аккумулятора. Так, символическое имя пятого бита аккумулятора при использовании ассемблера ASM51 будет следующим:    АСС.5.

Регистр В. Используется во время операций умножения и деления. Для других инструкций регистр В может рассматриваться как дополнительный сверхоперативный регистр.

Регистр состояния программы. Регистр PSW содержит информацию о состоянии программы.

Указатель   стека   SP.   8-битовый   регистр,   содержимое   которого инкрементируется перед записью данных в стек при выполнении команд PUSH и CALL. При начальном сбросе указатель стека устанавливается в 07Н, а область стека в ОЗУ данных начинается с адреса 08Н. При необходимости путем переопределения указателя стека область стека может быть расположена в любом месте внутреннего ОЗУ данных микроЭВМ.

Указатель данных. Указатель данных (DPTR) состоит из старшего байта (DPH) и младшего байта (DPL). Содержит 16-битовый адрес при обращении к внешней памяти. Может использоваться как 16-битовый регистр или как два независимых восьмибитовых регистра.

Порт0—ПортЗ. Регистрами специальных функций Р0, Р1, Р2, РЗ являются регистры-"защелки" соответственно портов Р0, Р1, Р2, РЗ.

Буфер последовательного  порта. SBUF представляет собой два отдельных регистра: буфер передатчика и буфер приемника. Когда данные записываются в SBUF, они поступают в буфер передатчика, причем запись байта в SBUF 
автоматически инициирует его передачу через последовательный порт. Когда данные читаются из SBUF, они выбираются из буфера приемника.

Регистры таймера. Регистровые пары (TH0.TL0) и (TH1.TL1) образуют 16- битовые счетные регистры соответственно таймера/счетчика 0 и таймера/счетчика 1.

Регистры управления. Регистры специальных функций IP, IE, TMOD, TCON, SCON и PCON содержат биты управления и биты состояния системы прерываний, таймеров/счетчиков и последовательного порта. ОМЭВМ при функционировании обеспечивает:

— минимальное время  выполнения команд сложения — 1 мкс;  
— аппаратное умножение и деление с минимальным временем выполнения команд умножения/деления — 4 мкс

 

 

 

 

 

Блок-схема алгоритма работы программы

 

Сначала программа записывает данные во внешнюю память. После  этого она считывает исходные числа из внешней памяти во внутреннюю и одновременно сортирует их.

Процесс сортировки происходит во время считывания данных из внешней памяти и выглядит следующим образом.

Программа просматривает  все исходные числа во внешней  памяти и выбирает самое большое  число. После этого она записывает это число в ячейку во внутренней памяти с самым большим запланированным номером. Далее ячейка во внешней памяти, откуда было считано это число, обнуляется.

После этого снова  производится поиск самого большого из оставшихся чисел, это число записывается в следующую ячейку во внешней  памяти.

Процесс продолжается до использования всех чисел из внешней памяти.

После этого отсортированные  элементы переписываются обратно во внешнюю память.

Использование памяти

Участки памяти:

Xdata:  0000h…0019h – область сортируемых чисел

data:  40h…53h - область, используемая для промежуточного хранения и сортировки чисел

Регистры:

DPTR: хранит адрес байта в XDATA (0000h..0019h).

A: используется как  буфер для передачи данных  из XDATA в DATA и для копирования  данных из одного участка памяти  в другой.

R0: хранит адрес обрабатываемого  элемента в DATA (40h..53h)

R1: используется как  локальный счетчик цикла.

R2: хранит данные из DPL для запоминания адреса текущего  самого большего элемента.

Участок 36h: хранит текущее самое большое число.

Рис 1. 
Листинг программы

 

    org 00h  ;смещение от начала

jmp start ;переход к началу

org 50h  ;память данных

 

Start:   

 

; ИНИЦИАЛИЗАЦИЯ

 

module_create_data:  ;Модуль  устанавливает начальные значения  байтам в XDATA с адресами 00h..09h

 

mov DPTR, #0000h ;адрес

mov A, #13h  ; 1-e число

movx @DPTR, A  ; занести число по адресу

inc DPTR  ;увеличить адрес на 1

 

mov A, #11h  ; 2-e число

movx @DPTR, A

inc DPTR

 

mov A, #01h  ; 3-e число

movx @DPTR, A

inc DPTR

 

mov A, #17h  ; 4-e число

movx @DPTR, A

inc DPTR

 

mov A, #07h  ; 5-e число

movx @DPTR, A

inc DPTR

 

mov A, #03h  ; 6-e число

movx @DPTR, A

inc DPTR

 

mov A, #21h  ; 7-e число

movx @DPTR, A

inc DPTR

 

mov A, #32h  ; 8-e число

movx @DPTR, A

inc DPTR 

 

mov A, #32h  ; 9-e число

movx @DPTR, A

inc DPTR

 

mov A, #12h  ; 10-e число

movx @DPTR, A

 

mov A, #42h  ; 11-e число

movx @DPTR, A

inc DPTR

 

mov A, #34h  ; 12-e число

movx @DPTR, A

inc DPTR

 

mov A, #22h  ; 13-e число

movx @DPTR, A

inc DPTR

 

mov A, #14h  ; 14-e число

movx @DPTR, A

inc DPTR

 

mov A, #55h  ; 15-e число

movx @DPTR, A

inc DPTR

 

mov A, #11h  ; 16-e число

movx @DPTR, A

inc DPTR

 

mov A, #17h  ; 17-e число

movx @DPTR, A

inc DPTR

 

mov A, #77h  ; 18-e число

movx @DPTR, A

inc DPTR

 

mov A, #31h  ; 19-e число

movx @DPTR, A

inc DPTR

 

mov A, #12h  ; 20-e число

movx @DPTR, A

 

 

 

 

;СОРТИРОВКА 
 
module_sort_massiv: метка начала сортировки 
 
mov R0, #53h 
metka1: метка главного цикла сортировки 
mov 54h, #00h 
mov R2, DPL 
jmp module_search_massiv переход на метку поиска макс 
 
metka_vozvrata1: метка возврата из поиска макс эл. 
 
mov DPL, R2 
mov A, #00h 
dec DPL 
movx @DPTR, A 
 
mov @R0, 54h 
dec R0 
cjne R0, #3Fh, metka1 
jmp module_data_to_xdata переход на метку вывода данных 
 
;ДОПОЛНИТЕЛЬНЫЕ МОДУЛИ 
 
module_search_massiv: начало кода поска макс эл массива 
mov DPTR, #0000h 
metka2: главный цикл поиска  
movx A, @DPTR 
inc DPTR 
mov R1, DPL 
cjne A, 54h, metka3  
 
metka_vozvrata2: перед возвратом 
cjne R1, #14h, metka2 переход на метку вложенного цикла 
jmp metka_vozvrata1 переход на возврат из поиска 
metka3: 
jc metka_vozvrata2 продолжаем сканировать 
mov 54h, A 
mov R2, DPL 
jmp metka_vozvrata2 пока все не переберем программа в цикле 
 
 
;ПЕРЕМЕЩЕНИЕ ОТСОРТИРОВАННЫХ ЧИСЕЛ ОБРАТНО ВО ВНЕШНЮЮ ПАМЯТЬ