Автор: Пользователь скрыл имя, 01 Мая 2012 в 17:54, курсовая работа
Столь привычная для нас десятичная система оказалась неудобной для электронно-вычислительных машин (ЭВМ). Если в механических вычислительных устройствах, использующих десятичную систему, достаточно просто применить элемент с множеством состояний (колесо с девятью зубьями), то в электронных машинах надо было бы иметь 10 различных потенциалов в цепях. Цель курсовой работы – рассмотреть системы счисления с компьютерной обработке.
Введение
Глава 1. Использование систем счисления в информатике
1.1. Понятие системы счисления
1.2. Непозиционные и позиционные системы счисления
1.3. Двоичное кодирование информации в компьютере
1.4. Представление чисел в компьютере
1.5. Способы построения двоичных кодов
Глава 2. Алгоритм решения задачи
Заключение
Список использованной литературы
— разделителю слов (000) всегда предшествует признак конца знака;
при этом реализуется последовательность 00000 (т.е. если в конце кода встречается комбинация ...000 или ...0000, они не воспринимаются как разделитель слов); следовательно, коды букв могут оканчиваться на 0 или 00 (до признака конца знака).
Длительность передачи каждого отдельного кода 4 очевидно, может быть найдена: ti = ki • τ, где ki - количество элементарных сигналов (бит) в коде символа L.
Алфавитное неравномерное двоичное кодирование. Префиксный код
Рассмотрев
один из вариантов двоичного
Суть
первой проблемы состоит в нахождении
такого варианта кодирования сообщения,
при котором последующее
ииииииииииии
Неравномерный код может быть однозначно декодирован, если никакой из кодов не совпадает с началом какого-либо иного более длинного кода.
Например, если имеется код ПО, то уже не могут использоваться коды 1, 11, 1101, 110101 и пр. Если условие Фано выполняется, то при прочтении (расшифровке) закодированного сообщения путем сопоставления со списком кодов всегда можно точно указать, где заканчивается один код и начинается другой.
Пример:
Пусть имеется следующая
а | л | м | р | у | ы |
10 | 010 | 00 | 11 | 0110 | 0111 |
Требуется декодировать сообщение: 00100010000111010101110000110. Декодирование производится циклическим повторением следующих действий:
1.
отрезать от текущего
2.
сравнить рабочее кодовое
3. декодировать рабочее кодовое слово, очистить его;
4.
проверить, имеются ли еще
Применение данного алгоритма дает:
Шаг | Рабочее слово | Текущее сообщение | Распознанный знак | Декодированное сообщение |
0 | пусто | 00100010000111010101110000110 | - | - |
1 | 0 | 0100010000111010101110000110 | нет | - |
2 | 00 | 100010000111010101110000110 | м | М |
3 | 1 | 00010000111010101110000110 | нет | М |
4 | 10 | 0010000111010101110000110 | а | МА |
5 | 0 | 010000111010101110000110 | нет | МА |
6 | 00 | 10000111010101110000110 | м | Мам |
• • • |
Доведя процедуру до конца, получим сообщение: «мама мыла раму».
Код Хаффмана
Способ
оптимального префиксного двоичного
кодирования был предложен Д.
шагов
будет равно N - 2, где N - число знаков
исходного алфавита (в нашем случае
N = 6, следовательно, необходимо построить
4 вспомогательных алфавита). В промежуточных
алфавитах каждый раз будем переупорядочивать
знаки по убыванию вероятностей. Всю процедуру
построения представим в виде таблицы:
Теперь в обратном направлении поведем процедуру кодирования. Двум знакам последнего алфавита присвоим коды 0 и 1 (которому какой - роли не играет; условимся, что верхний знак будет иметь код 0, а нижний - 1). В нашем примере знак а1(4) алфавита А(4), имеющий вероятность 0,6 , получит код 0, а а2(4) с вероятностью 0,4 - код 1. В алфавите A(3) знак а1(3) с вероятностью 0,4 сохранит свой код (1); коды знаков a2(3) и a3(3), объединенных знаком a1(4) с вероятностью 0,6 , будут уже двузначным: их первой цифрой станет код связанного с ними знака (т.е. 0), а вторая цифра -как условились - у верхнего 0, у нижнего - 1; таким образом, а2(3) будет иметь код 00, a a3(3) - код 01. Полностью процедура кодирования представлена в следующей таблице:
Из
самой процедуры построения кодов
легко видеть, что они удовлетворяют
условию Фано и, следовательно, не требуют
разделителя. Средняя длина кода при этом
оказывается: К(2) = 0,3-2+0,2-2+0,2-2+0,15-3+0,1-
Для
сравнения можно найти I1{A)-
Код Хаффмана важен в теоретическом отношении, поскольку он является самым экономичным из всех возможных, т.е. ни для какого метода алфавитного кодирования длина кода не может оказаться меньше, чем код Хаффмана. Можно заключить, что существует метод построения оптимального неравномерного алфавитного кода. Метод Хаффмана и его модификация - метод адаптивного кодирования (динамическое кодирование Хаффмана) - нашли применение в программах-архиваторах, программах резервного копирования файлов и дисков, в системах сжатия информации в модемах и факсах.
Равномерное алфавитное двоичное кодирование. Байтовый код
В этом случае двоичный код первичного алфавита строится цепочками равной длины, т.е. со всеми знаками связано одинаковое количество информации равное 10. Передавать признак конца знака не требуется, поэтому для определения длины кодовой цепочки можно воспользоваться формулой: К(2) > log2N. Приемное устройство просто отсчитывает оговоренное заранее количество элементарных сигналов и интерпретирует цепочку (устанавливает, какому знаку она соответствует). Правда, при этом недопустимы сбои, например, пропуск (непрочтение) одного элементарного сигнала приведет к сдвигу всей кодовой последовательности и неправильной ее интерпретации; решается проблема путем синхронизации передачи или иными способами. С другой стороны, применение равномерного кода оказывается одним из средств контроля правильности передачи, поскольку факт поступления лишнего элементарного сигнала или, наоборот, поступление неполного кода сразу интерпретируется как ошибка.
Пример:
Символ | Код |
А | 00000001 |
Б | 00000010 |
В | 00000011 |
Г | 00000100 |
Д | 00000101 |
Е | 00000110 |
Ё | 00000111 |
Ж | 00001000 |
Глава 2. Алгоритм решения задачи
Агентство по грузоперевозкам «Летучий голландец» предоставляет услуги по перевозке грузов по различным маршрутам. Данные о маршрутах, выполненных в течение недели, по каждому водителю приведены на рис. 2.1. Справочные данные о технических характеристиках автомобилей и протяженности маршрутов приведены на рис. 2.2.
Сведения о выполненных маршрутах | |||||||||
№ п/п | ФИО водитепя | Марка автомобиля | № рейса | Выполнено рейсов | Протяженность | Расход топлива на 100 км, л | Израсходовано топлива, л | Грузоподьёмность, тонн | Вес перевезенного груза, тонн |
рейса, км | |||||||||
1 | Соловьев В. В. | КАМАЗ | А112 | 4 | |||||
2 | Михайлов С. С. | ЗИЛ | С431 | 3 | |||||
3 | Кузнецов Я.Я. | МАЗ | А112 | 5 | |||||
4 | Иванов К.К | МАЗ | М 023 | 7 | |||||
5 | Сидоров А. А. | ЗИЛ | В447 | 2 | |||||
6 | Волков Д. Д. | КАМАЗ | С431 | 8 | |||||
7 | Быков Л.Л. | КАМАЗ | В447 | 4 | |||||
ИТОГО | X | X | X | ||||||
В СРЕДНЕМ | X | X | X |
Рис. 2.1. Данные о выполненных маршрутах
|
Рис. 2.2.
Технические характеристики автомобилей
и данные о протяженности выполняемых
рейсов
|