Содержание к диссертации
Введение
Глава 1. Сущность и необходимость сжатия текстов 12
1.1. Важность и эффективность использования текстового сжатия 12
1.2. Предмет текстового сжатия 15
1.3. Область применения методов сжатия текстов на практике 16
1.4. Алгоритм Шеннона - Фано 20
1.5. Алгоритм Хаффмена 24
1.6. Адаптивное кодирование Хаффмена 29
1.7. Арифметическое кодирование 34
Глава 2. Анализ статистики арабских и английских текстовых сообщений 39
2.1. Измерение информации в компьютерной системе 39
2.2. Энтропия — мера количества информации 40
2.3. Сравнительная характеристика степени сжатия текстов на арабском и английском языках 41
2.4. Статистический подход к сжатию текстов через моделирование и кодирование 45
2.5. Моделирование естественного языка 47
2.6. Анализ вероятности появления очередных символов в арабских текстах 48
2.7. Сравнительный анализ арабских и английских текстов 52
Глава 3. Методы кодирования и декодирования с использованием обобщенного статистического распределения символов алфавита 59
3.1. Методика кодирования по модели сообщения первого порядка59
3.2. Методика декодирования 61
3.3. Сравнительная характеристика разных способов сжатия 69
3.4. Сравнение предлагаемого метода с другими способами сжатия по модели высокого порядка 76
3.5. Описание алгоритмов программ 78
3.5.1. Общая схема программы 78
3.5.2. Процедуры подсчета диграмм и триграмм 86
3.5.3. Процедуры построения деревьев для диграмм и триграмм 88
Выводы к главе 3 91
Глава 4. Вопросы практической реализации кодека с моделью источника сообщения высокого порядка 92
4.1. Структурная схема кодека 92
4.2. Выбор элементной базы 93
4.3. Микроконтроллер PIC16F877 94
4.4. Микросхема статистического ОЗУ 62256 97
4.5. Программатор PIC-контроллеров 99
Выводы к главе 4 101
Заключение 102
Список литературы 103
Приложение 1
- Область применения методов сжатия текстов на практике
- Сравнительная характеристика степени сжатия текстов на арабском и английском языках
- Сравнение предлагаемого метода с другими способами сжатия по модели высокого порядка
- Выбор элементной базы
Введение к работе
Жизнь современного общества фактически невозможна без хорошо развитых электронных систем. Любая радиотехническая система имеет своей целью доставить информацию о каком-либо явлении, событии или состоянии некоторой материальной системы в условиях, когда источник информации удален от места ее приема. Это может быть текстовая информация (радиосвязь), информация о координатах или скорости движения удаленного объекта (радиолокация), изображение объекта (телевидение), информация о состоянии удаленной материальной системы (телеметрия), команды на изменение состояния объекта (командные радиолинии) и т.д.
Электронные автоматические телефонные станции с широким использованием ЭВМ, радиовещание, телевидение, обработка и передача данных, спутниковые системы связи, лазерные системы связи, управление работой устройств, находящихся на различных и довольно существенных расстояниях, радиолокация, радионавигация и др. - далеко не полный список электронных устройств и систем, широко используемых в нашей жизни. В передаче и приеме самой разнообразной информации нуждаются промышленность, транспорт, координационные и управленческие органы, предприятия культуры и образования, без связи невозможно организовать защиту страны, обеспечить необходимое общение населения друг с другом. О связи часто говорят, это - нерв страны. Без точно действующей передачи информации деятельность фактически любого учреждения или предприятия либо сильно затрудняется, либо становится просто невозможной.
Но современная связь обеспечивается совокупностью электротехнических и электронных устройств различной сложности, состоящих из элементов, к которым приложены электрические
6 напряжения или по которым протекают электрические токи. С помощью таких токов удобно передавать энергию, но, в принципе, невозможно передать какую-либо информацию, тем более, что при передаче энергии главную роль играют мощность и КПД системы, а при передаче информации - отсутствие искажений и скорость.
Многоканальные телекоммуникационные системы, позволяющие организовать по одной физической цепи связи большое число одновременно и независимо действующих каналов, являются, наряду со средствами коммутации каналов и сообщений, основой сети связи любой страны. Современные системы передачи (СП) представляют собой комплекс сложных и разнообразных технических средств, осуществляющих преобразование, усиление (регенерацию) и передачу различных сигналов электросвязи. В этих условиях задача обеспечения качественного функционирования сети передачи информации решается на этапах проектирования, разработки и изготовления оборудования СП, проектирования и строительства линий связи, организации технической эксплуатации и обслуживания оборудования.
Сеть электросвязи (СЭС) представляет собой комплекс технических средств электросвязи, взаимодействующих на основе некоторых принципов и обеспечивающих возможности своевременно, качественно и полно удовлетворить все потребности населения страны, отраслей народного хозяйства, органов государственного управления и обороны, науки и образования, здравоохранения и культуры в различных услугах связи. В структуру СЭС входят государственные, ведомственные и акционерные сети и системы электросвязи, содержащие сложную коммутационную аппаратуру и оборудование СП, линейные и гражданские сооружения, электронные вычислительные и управляющие комплексы.
7 Актуальность темы.
Развитие компьютерных технологий привело к тому, что современный мир невозможно представить без цифровой обработки передаваемой информации. Её постоянно возрастающие объёмы настоятельно требуют эффективного решения проблемы передачи больших информационных пакетов с большой скоростью. Одним из направлений решения указанной проблемы является сжатие текстовой информации. Особенно актуально это для арабского языка, что связано с интенсивным развитием стран арабского мира и вовлечением их в мировое разделение труда.
В конце 40-х годов, на заре теории информации, стартовала идея создания новой техники эффективного кодирования информации. Исследователи использовали понятия энтропии, количества информации и потерь. Было осознано, что если вероятность символов в сообщении известна, то их можно закодировать таким образом, что сообщение будет занимать минимальное объем.
Примечательно, что эти первые работы по сжатию данных были выполнены еще до появления современных цифровых компьютеров. Сейчас кажется естественным, что теория информации идет рука об руку с компьютерным программированием, но во времена, последовавшие за второй мировой войной, во всех исходных предпосылках цифровые компьютеры не фигурировали. Последующая идея разработки алгоритмов с использованием двоичной арифметики для кодирования символов оказалась большим шагом вперед.
Основная причина использования сжатия - уменьшение объема, необходимого для хранения информации. Способ сжатия по Бройлю может сократить размер книги на 20% или уменьшить число томов, необходимых для хранения одной печатной книги. Для компьютеров сжатие позволяет увеличить количество информации, хранимой на диске, уменьшить число носителей информации, уменьшить время доступа и т.д.
Сжатие означает уменьшение объема текста. Другими словами, сжатие текста - это нахождение способа представить его меньшим количеством битов или байтов. Необходимо, чтобы закодированная форма не осложняла восстановление первоначального (оригинального) текста, и обычно важно, чтобы оригинал восстанавливался точно, а не приблизительно. Это отличает сжатие текста от сокращения многих других видов данных, типа голоса или кодирования картины, где небольшая деградация качества может быть вполне терпима, если достигнуто более компактное представление информации.
Люди часто задаются вопросом, актуально ли сжатие в век персональных компьютеров и автоматизированных рабочих мест. На современных средствах хранения можно разместить мегабайты, возможно гигабайты информации. Очевидно, что пользователей интересует достижение двойного или тройного уменьшения занимаемого объема.
Сжатие также позволяет использовать ограниченную передачу с определённой шириной полосы. Несмотря на внушительный прогресс в широкополосной технологии связи (спутники, волоконная оптика), многие из нас связываются ежедневно с компьютерами по телефонным каналам. Информацию на дальние расстояния также часто передают по непритязательной телефонной сети. Сжатие текста может сократить эффективную полосу пропускания, сокращая затраты связи и потери конечного пользователя.
Существуют известные методы кодирования, такие как метод Шеннона-Фано, Хаффмена, адаптивный метод Хаффмена и арифметический. Эти методы внесли значительный вклад в развитие теории статистического кодирования текста. Но они не используют на практике методы сжатия с моделью источников сообщений высокого порядка. Хотя известно, что с помощью этих моделей можно получить высокую степень коэффициента сжатия.
9 Цель работы
Целью настоящей диссертационной работы является исследование статистики арабских и английских текстов и разработка на этой основе эффективных алгоритмов кодирования.
Задачи
Анализ существующих моделей сжатия текстовой информации для разных языков.
Анализ статистики текстов на арабском языке различной тематики и объема.
Разработка метода сжатия, основанного на модели 1-го и 2-го порядка.
Экспериментально - статистическая проверка разработанного метода и сравнение его с другими методами.
Разработка программы кодирования и декодирования, основанной на данном методе.
Методы исследования
Основные результаты диссертационной работы получены и математически обоснованы с использованием методов теории вероятности, статистического анализа, математической статистики и программных методов сжатия информации.
Научная новизна
Внедрение принципа кодирования текста на базе модели сообщения высокого порядка.
Разработка алгоритмов кодирования с моделями первого и второго порядков.
10 Практическая ценность
Полученные в работе результаты теоретического и практического характера являются основой для теории кодирования сообщений, а разработанные эффективные алгоритмы сжатия могут непосредственно использоваться на практике.
Личный вклад. Все основные научные результаты в
диссертационной работы получены автором лично.
Публикации. По материалам диссертационной работы
опубликовано 2 научные работы и третья в процессе издания. Основные положения, выносимые на защиту:
Результаты анализа основных особенностей современных и самых распространенных методов статистического кодирования.
Результаты анализа текстов на арабском и английском языке и расчет распределения вероятностей их п-грамм.
Разработанный новый метод сжатия текста, отличающейся от традиционного тем, что он основан на использовании информации о предыдущих символах с моделью первого порядка (диграмма) и второго порядка (триграмма).
Результаты проведенного экспериментального исследовании и подтверждение работоспособности и эффективности предложенного нового метода кодирования.
Разработаны программа и алгоритм кодирования на базе диграмм и триграмм.
Разработано устройство кодирования - декодирования (кодек) для предлагаемого метода сжатия с моделями источника сообщения высокого порядка.
Объем и структура работы. Диссертационная работа состоит из введения, четырех глав, заключения, список литературы включает 69 наименований и приложений. Работа изложена на 132 страницах машинного текста, включая 27 таблиц и 41 рисунка.
Краткое содержание работы
Первая глава посвящена рассмотрению вопросов необходимости и целесообразности сжатия текстов. Глава содержит краткий обзор наиболее известных существующих методов сжатия текста (в порядке их исторического появления). Приведены описания следующих методов: Шеннона - Фано; Хаффмена; адаптивное сжатие Хаффмена; арифметическое кодирование.
Во второй главе приведены некоторые теоретические аспекты сжатия информации. Показаны вероятностно-статистические основы построения различных моделей сжатия текстов. Также приведены практические результаты статистического анализа текстов на английском и арабском языках. Показана возможность получения лучших показателей сжатия для арабского языка. Также во второй главе приведена статистика сжатия двумя различными способами.
Третья глава посвящена подробному описанию предлагаемого нами способа сжатия. Построение данного способа сравнивается с построениями других способов. Приведены результаты практических применений разных способов сжатия. Также даны алгоритмы построения программы сжатия.
В четвертой главе описано устройство, реализующее предлагаемый способ сжатия текста. Данное устройство может быть использовано как промежуточное звено в разных системах передачи информации. Приведены его структурная и принципиальная схемы.
Область применения методов сжатия текстов на практике
Сжатие сокращает объем пространства, требуемого для хранения файлов в ЭВМ, и количество времени, необходимого для передачи информации по каналу установленной ширины пропускания. Сжатие — это своего рода форма кодирования. Другими целями кодирования являются поиск и исправление ошибок, а также шифрование. Процесс поиска и исправления ошибок противоположен сжатию. Он увеличивает избыточность данных, когда их не нужно представлять в удобной для восприятия человеком форме. Удаляя из текста избыточность, сжатие способствует шифрованию, что затрудняет поиск шифра доступным для взломщика статистическим методом.
Мы будем рассматривать лишь обратимое сжатие или сжатие без наличия помех, где первоначальный текст может быть в точности восстановлен из сжатого состояния. Необратимое или ущербное сжатие используется для цифровой записи аналоговых сигналов, таких как человеческая речь или рисунки. Обратимое сжатие особенно важно для текстов, записанных на естественных и на искусственных языках, поскольку в этом случае ошибки обычно недопустимы. Хотя первоочередной областью применения рассматриваемых методов является сжатие текстов, что отражает и наша терминология, однако, эта техника может найти применение и в других случаях, включая обратимое кодирование последовательностей дискретных данных. Существует много веских причин выделять ресурсы ЭВМ в расчете на сжатое представление, так как более быстрая передача данных и сокращение пространства для их хранения позволяют сберечь значительные средства и зачастую улучшить показатели ЭВМ. Сжатие, вероятно, будет оставаться в сфере внимания из-за все возрастающих объемов хранимых и передаваемых в ЭВМ данных, кроме того его можно использовать для преодоления некоторых физических ограничений, таких как, например, сравнительно узкая полоса пропускания телефонных каналов [2, 6, 24].
Первый обще известный метод эффективного кодирования символов называется в настоящее время кодированием по Шеннону - Фано . Клод Шеннон в лаборатории Белла и Р.М.Фано в M.I.T. построили свои методы практически одновременно [51, 56]. Оба они исходили из известности вероятности каждого символа сообщения. При заданных вероятностях могут быть построены таблицы кодов со следующими важными свойствами:? Различные коды имеют различное число бит.? Коды символов с малыми вероятностями имеют большее количество бит, а коды с большими вероятностями - меньшее их количество.? При различной битовой длине кодов они могут быть однозначно декодированы.
Первые два свойства взаимосвязаны. Вырабатывая коды, длина которых изменяется в соответствии с вероятностью символа, можем обеспечить максимально возможное сжатие данных. Располагая затем коды в виде бинарного дерева, мы, тем самым, решаем проблему декодирования.
Пример декодирующего дерева, используемого при кодировании по Шеннону - Фано, показан ниже (рис. 1.2). Декодирование принимаемого кода включает в себя старт от корня (ROOT) и поворот влево или вправо в каждом узле после считывания очередного бита из входного потока. Если корневой узел дерева достигнут, то соответствующий ему символ считается декодированным. На рис. 1.2 представлено дерево Шеннона - Фано, предназначенное для кодирования или декодирования простого 5-символьного сообщения, алфавит которого состоит из букв от А до Е. Перемещаясь по дереву, мы получаем следующую кодовую таблицу 1.1:
Структура дерева показывает, каким образом однозначно определяемые им коды получают различное количество бит. Очевидно, что эта структура удобна для компьютерной реализации, но она также хорошо приспособлена и для машин, работающих на основе реле и переключателей, подобных телефонным станциям 1950-х годов. Таблица иллюстрирует одно из обсуждавшихся выше свойств дерева, а именно, переменное количество бит.
Большинство широко изучаемых алгоритмов сжатия данных основаны на кодах Хаффмена. В коде Хаффмена каждая буква исходного текста представляется в архиве кодом переменной длины, наиболее повторяемые буквы представляются короткими кодами, менее повторяемые — длинными. Коды, используемые в сжатом тексте, должны подчиняться свойствам префикса, а именно: код, использованный в сжатом тексте не может быть префиксом любого другого кода.
Коды могут быть найдены посредством дерева, в котором каждый лист соответствует одной букве алфавита источника. Коды для буквы может быть прочитан при обходе дерева от корня к этой букве, где О соответствует выбору левой его ветви, а 1 - правой. Дерево кода Хаффмена есть дерево с выровненным весом, где каждый лист имеет вес, равный частоте встречаемости буквы в исходном тексте. Хаффменовское кодирование по большинству своих характеристиксовпадает с кодированием Шеннона - Фано. Оно создает кодыпеременной длины с целым числом бит. Более вероятным символамсоответствуют более короткие коды.
Как и алгоритм Шеннона - Фано, алгоритм Хаффмена требует читать входной файл дважды. Один раз, — при подсчете количества повторений символов, а другой — в процессе непосредственного кодирования.
Сравнительная характеристика степени сжатия текстов на арабском и английском языках
Предположим, что имеется набор возможных событий с известными вероятностями р1,р2,...,р„- Их "энтропия" показывает, какширок набор, в среднем, при выборе события, или, что эквивалентно, как не уверены мы в результате выбора. В своей работе, ознаменовавшей рождение теории информации, Шеннон постулировал, что энтропия Е{рх,р2,...,рп) должна удовлетворить следующим требованиям:Е- непрерывная функция от pt. Если каждый случай одинаково вероятен, то Е должна быть монотонно возрастающей функцией от п. Если выбор сделан в несколько последовательных этапов, то Е должна быть суммой энтропии выборов на каждом этапе, взвешенной в соответствии с их вероятностями [1, 13,31,42].
Третье условие аппелирует к интуитивному понятию многоступенчатого решения. В качестве примера, можно создать двухступенчатую процедуру реализации одного из п возможных событий, выбирая 1 или "остаток" с вероятностями рх и 1 - рх. Если был выбран "остаток", то необходимо сделать дальнейший выбор из 2, 3, ..., n , с распределением вероятностей р2,ръ,...,р„ , соответственно ренормали зованных. Обозначим энтропии из этих двух выборов как Е, = (/7,,1-/7,) и Е2 =Е(Р 2,Р 3,...,Р „), где штрих указывает на ренормализацию. Тогда третье условие просто устанавливает, что E = l-Ei+(\-pl)-E2 . Веса 1 и 1-р, используются потому, что первый выбор делался каждый раз, в то время как второй — только с вероятностью 1 - р1
Как показал Шеннон, единственная функция, которая удовлетворяет этим требованиям, естьгде положительная константа к вводит единицы, в которых измеряется энтропия. Обычно в качестве единиц используются "биты" (при этом к = 1), а логарифм берётся по основанию 2:
Энтропия - мера количества информации. Однако, как определено выше, она применима только к распределению вероятности, то есть к набору выборов с вероятностями, дающими в сумме 1. Часто мы в большей степени заинтересованы в количественной оценке информации, содержащейся в конкретном выборе, чем в знании её среднего значения по всем возможным выборам. Если вероятность выбора есть pt , то егоинформационное содержание или энтропия определены как отрицательный логарифм его вероятности,
Это означает, что более вероятные сообщения содержат меньшее количество "информации". Другими словами, чем неожиданнее сообщение, тем больше оно содержит информации. Например, в нашем мире сообщение "Я шел, чтобы работать сегодня" будет обычно передавать значительно меньшее количество информации, чем сообщение "Я телепортировался, чтобы работать сегодня". Фактически, сообщение о чём-то, что, в принципе, может произойти, не содержит информации (неожиданности) вообще, в то время как невозможное сообщение содержало бы её бесконечно много.
Наше определение информационного содержания индивидуального случая тесно связано с определением (2.1) энтропии выбора между событиями. При п -ступенчатом выборе с индивидуальными вероятностями Pi,p2- - и энтропиями Е ,Е2,... средняя энтропия индивидуальных решений
Включение Е, в формулу для индивидуальных энтропии приводит к формуле (2.2), совпадающей с формулой (2.1) для полной энтропии выбора. Таким образом, мы можем сказать, что полная энтропия - это среднее значение энтропии индивидуального выбора [27, 43].
Идентифицировав набор потенциальных сообщений, можем приступить теперь к выполнению сжатия при помощи наборов кодов, по одному для каждого возможного сообщения. Каждый код - уникальная строка символов (обычно битов), позволяющая выбрать соответствующее частное сообщение из числа всех возможных. При генерации кодов учёт энтропии не требуется. Например, можно взять конкретное сообщение — даже очень маловероятное — и приписать ему очень короткий код. В крайнем случае, его можно закодировать всего одним битом. Но это приведёт к сокращению кода только для одного, очень маловероятного сообщения, в то время как придётся удлинить, примерно на один бит, коды для всех других сообщений, чтобы они также могли быть идентифицированы своими уникальными кодами. Хотя учёт энтропии при назначении кодов и не требуется, однако желательно поступать следующим образом. Фундаментальный результат Шеннона, называемый "теоремой кодирования бесшумового источника", показывает, что среднее число двоичных символов, приходящихся на один символ источника, может быть сделано близким к значению исходной энтропии, но не меньше. Мы увидим, как методика арифметического кодирования обеспечивает позитивную часть теоремы, создавая оптимальные коды. Следует подчеркнуть, что это — истина только в среднем. Иногда может повезти, и результат окажется лучше ожидаемого. Энтропийный подход может быть обеспечен путём назначения каждому сообщению кода длиной -log;? бит, где р — его вероятность. Данный выбор делает среднее значение длин кодов равным - / log/ ,, т.е. такимже, как энтропия ансамбля сообщений, и, следовательно, минимизирует среднюю длину кода. Так что наше довольно абстрактное рассмотрение энтропии в предшествующем разделе дало очень точное правило оценивания величины ожидаемого сжатия [4, 8, 19].
Представляет интерес исследование возможностей сжатия текстов на различных языках по известным алгоритмам без потерь. Такие исследования уже выполнены, в частности, для английского языка [48].Мы поставили своей задачей провести аналогичное изучение возможностей сжатия текстов на арабском языке.
Полученные нами предварительные результаты сжатия художественных текстов на арабском и английском языках [66, 67, 68] с помощью нескольких алгоритмов (HUFF - хаффменовский, AHUFF — адаптивный хаффменовский, ARITH - арифметический, LZSS, LZW12, LZW15V — разновидности алгоритма Лемпеля и Зива) [56] изображены на графике рис. 2.1, где левые столбики относятся к английскому языку, а правые - к арабскому. Рис. 2.1 позволяет сравнить степени сжатия текстов по каждому из этих алгоритмов. Согласно этим данным, самым Такие результаты можно объяснить следующим образом.
Сравнение предлагаемого метода с другими способами сжатия по модели высокого порядка
Наряду с рассмотренными нами методами сжатия по модели высокого порядка, существуют и другие способы, менее эффективные, но также основанные на модели высокого порядка, с которыми мы сейчас сравним предлагаемый нами способ.
Для некоторых языков возможно построение модели кодирование по слогам (например для русского языка). Так как вероятности слогов намного выше вероятностей обычных диграмм или триграмм, то можно ожидать, что и длина кода для них будет меньше. Однако процесс выделения и подсчета слогов весьма сложен для программирования. Практически усилия необходимые на построение программы сжатия по слогам полностью нивелируют выгоды в степени сжатия. Кроме того во многих языках (например в арабском) не возможно выделить такой структурный элемент как слог. В арабском письменном языке отсутствуют гласные. Вместо них используют дополнительные диакритические знаки, добавляемые к согласным.
По модели источника сообщения первого порядка, существует простой способ, когда рассматривается диграмма как единый символ. В этом случае количество возможных диграмм будет: 256x256 = 65536 байт. Если строить дерево Хаффмена для всех этих диграмм, то его ширина и высота будут большими, при этом средняя длина кодов диграмм увеличивается. Несмотря на то, что количество диграмм в тексте в два раза меньше чем монограмм, получить высокую степень сжатия не всегда представляется возможным.
При использовании триграмм также возможны несколько способов построения деревьев. Самый простой — это рассматривать триграмму как единый символ. В этом случае количество возможных триграмм будет: 256x256x256 = 16777216. Если строить дерево Хаффмена для всех этих триграмм, то его ширина и, соответственно, высота будут большими. Но чем выше дерево, тем длиннее коды. Как правило, средняя длина кода при этом способе сжатия составляет 12 бит. И, хотя количество триграмм в тексте в три раза меньше, чем монограмм, получить высокую степень сжатия не удается. А иногда текст вообще не сжимается [53, 55, 62].
Основные подпрограммы (рис. 3.13) построены в соответствии с задачамивсей программы [35]:подпрограмма countJbytes осуществляет подсчет «-грамм (или считываниеих из обобщенной таблицы);подпрограмма scale_counts выполняет масштабирование таблицы частости,выравнивая все её значения на двухбайтное целое число;подпрограмма print counts выводит на экран (или в файл) таблицу частости;подпрограмма buildjree выполняет построение Хаффменовского деревадля текущей диграммы (триграммы);подпрограмма converter ее_to_code выполняет построение кодов «-грамм,выполняя рекурсивный обход текущего Хаффменовского дерева.
Программа сжатия данных выполняет циклы ввода/вывода (I/O), в которых считыванию или записи подлежит нестандартное количество бит. Хаффменовское кодирование, например, требует побитового считывания и записи или считывает и записывает коды, размер которых лежит в диапазоне от 9 до 16 бит. Стандартная С-библиотека для I/O, определенная в STDIO.H, приспосабливает I/O только при наличии границ байтов. Подпрограмма, подобно putc() и getc(), читает и записывает одиночные байты, в то время как fread() и fwrite() считывает и записывает блоки байтов. Чтобы поддерживать нестандартный I/O стандартным путем, бит-ориентированные подпрограммы I/O объединены в один модуль BITIO.C. Обращение к этим подпрограммам обеспечивается при помощи головного файла BITIO.H, содержащего структурное определение и прототипы различных функций.
Две подпрограммы открывают файлы для битовых I/O. Одна из них используется при вводе, а другая - при выводе. Как определено в BITIO.H, это подпрограммы: int pacifier_counter; } BIT_FILE; Подпрограммы OpenInputBitFile() и OpenOutputBitFile() реализуют обычный вызов функции fopen() и запоминают возвращаемый указатель на FILE-структуру в BiT_FILE-crpyKType. Другие два структурных элемента инициализируются стартовыми значениями, после чего возвращается указатель на результирующую BIT_FILE-CTpyKTypy.
Два новых структурных элемента (rack и mask) обеспечивают бит-ориентированный аспект в BIT_FILE. "rack" содержит текущий байт данных как при считывании из файла, так и при ожидании записи в файл, "mask" содержит однобитовую маску, используемую для установки/сброса текущего выходного бита или для маскирования текущего входного бита.В BITIO.H старший значащий бит байта I/O принимает или возвращает первый бит, а последний значащий бит байта I/O принимает или возвращает последний бит. Это приводит к тому, что при первом открывании BIT_FILE масочный элемент структуры инициализируется значением 0x80. При выводе первая запись в BIT_FILE будет устанавливать или сбрасывать этот бит, после чего масочный элемент переключается в
Выбор элементной базы
При выборе элементной базы основное внимание было уделено выбору исполнительного устройства. Решение задачи возможно с применением программируемых логических интегральных схем (ПЛИС) или микропроцессоров. Использование ПЛИС позволит реализовать максимально высокое быстродействие устройства, но требует большого объёма как программного, так и приборного обеспечения, что также связано с большими материальными затратами.
Так как по техническому заданию нет требований по быстродействию то в качестве исполнительного устройства выберем микропроцессор. При выборе типа микропроцессора, наиболее подходящего для решения данной задачи, были рассмотрены некоторые варианты микроконтроллеров фирм Atmel, Intel, Microchip и использования сигнального процессора Taxes Instruments.
Использование сигнального процессора Taxes Instruments оказалось невыгодно с экономической точка зрения: высокая цена самого процессора и очень высокая цена средств разработки.
Тогда для макетного образца было предложено использовать недорогие микроконтроллеры. Среди фирм, производящих микроконтроллеры (Atmel, Intel, Microchip) предпочтение было отдано фирме Microchip [39, 64] и семейству её недорогих контроллеров РІС.
Фирма Microchip представляет компакт-диски с полной информацией о своих микроконтроллерах и бесплатной средой отладки и симуляции MPLAB. Также микроконтроллеры РІС относительной недороги, некоторые из них оснащены FLASH-памятью, что очень удобно при отладке программы. Кроме того, некоторые микроконтроллеры не требуют специального программатора, а используют технологию In-circuit serial programming, что позволяет осуществлять программирование с помощью ПЭВМ, несложной программы и небольшого устройства подключаемого к LPT-порту IBM PC по двумя входам. Далее требовалось выбрать подходящий микроконтроллер из свойства PIC micro.
Для адресации 64Кбайт памяти требуется 16 бит. Также требуется использовать 8 разрядную шину данных, т.е. число портов ввода / вывода должно быть не более 24. Также желательно присутствие встроенного US ART — контроллера для более простой передачи данных по RS-232. Обязательно наличие FLASH-памяти для откладки программы и технологии In-circuit serial programming.
Для макета целесообразно выбрать микроконтроллер с максимальным объёмом памяти для программ. Всем перечисленным требованиям удовлетворяет микроконтроллер PIC16F877 [39, 64]. Структурная схема микро- контроллер PIC16F877 показана на рис. 4.2, В приложении 3 даны схема выводов микроконтроллера и их назначение.
Основные достоинства PIC16F877 Высокопроизводительный RISC процессор, всего 35 команд; Тактовая частота 20 МГц, длительность командного такта 200 не; » 14336 байт памяти программ, 368 байт памяти данных, 256 байт FLASH-памяти данных; Возможность прямой и косвенной адресации памяти данных; До 14 различных прерываний; Восьмиуровневый стек; Таймер задержки включения;
Сторожевой таймер; Защита программного кода; Энергосберегающий режим; Программирование по двум входам; Работа при напряжениях питания от 2 В до 5,5 В; Низкое энергопотребление (2 мА при Un=5 В, F=4 МГц ); Два 8-битных счетчика, один 16-битный счетчик; Встроенное 8-канальное 10-битное АЦП;
Встроенный US ART, синхронный последовательный порт с поддержкой SPI и 12С; Два встроенных компаратора.
Итого PIC16F877 имеет 33 цифровых ввода-вывода. В макете распределим их следующим образом:
Сигналы POERT В и PORT D образуют адресную шину: PORT В - будет содержать младшие 8 бит адреса для ОЗУ; PORT D - будет содержать старшие 8 бит адреса для ОЗУ. Сигналы PORT С образуют шину данных:PORT С - 8 бит шины данных, а также при работы по RS-232 RC6 и RC7 применяются для передачи и приема данных от ПЭВМ соответственно. PORT Е применим для вспомогательных сигналов ОЗУ (выбор микросхемы, чтение, запись). PORT А зарезервируем для дальнейшего использования.Часть области памяти данных PIC16F877 зарезервирована используется для служебных целей. Кроме того 368 байт могут быть задействованы при написании программ (рис. 4.3).
Похожие диссертации на Исследование и разработка методов сжатия текста на арабском языке
