Система счисления

Содержание 

Введение ………………………………………………………………………………………

Глава 1. Использование систем счисления в компьютерной технике и информационных технологиях………………………………………………………………

1.1 Двоичное кодирование информации в компьютере……………………………….

1.2 Представление чисел в компьютере………………………………………………….

1.3 Способы построения двоичных кодов………………………………......................

Введение

Глава 1. Использование систем счисления

1.1 Двоичное кодирование информации в компьютере

Для обмена информацией с  другими людьми человек использует естественные языки (русский, английский, китайский и т.д.), те есть информация представляется с помощью естественных языков. В основе языка лежит алфавит, то есть набор символов (знаков, которые человек различает по их начертанию. Последовательности символов алфавита в соответствии с правилами грамматики образуют основные объекты языка -слова. Правила, согласно которым образуются предложения из слов данного языка называются синтаксисом. Необходимо от метить, что в естественных языках грамматика и синтаксис языка формируются с помощью большого количество правил, из которых существуют исключения, так как такие правила складывались исторически.

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

Создатели первых компьютеров  столкнулись с проблемой представления  и обработки информации. Так как  компьютер это всего лишь машина у которой нет ни интеллекта, ни логики, и мыслить она не способна, разработчикам пришлось найти такой способ представления информации, который был бы максимально прост для восприятия компьютером. Столь привычная для нас десятичная система оказалась неудобной для ЭВМ. Если в механических вычислительных устройствах, использующих десятичную систему, достаточно просто применить элемент с множеством состояний (колесо с девятью зубьями), то в электронных машинах надо было бы иметь 10 различных потенциалов в цепях. Наиболее просто реализуется элементы с двумя состояниями - триггеры. Поэтому естественным был переход на двоичную систему, т.е. системы по основанию 2. В этой системе всего две цифры - 0 и 1 . Каждая цифра называется двоичной (от английского binary digit - двоичная цифра). Сокращение от этого выражения привело к появлению термина бит, ставшего названием разряда двоичного числа.

Бит - это минимальная  единица измерения информации (0 или1). За битом следует байт, состоящий из восьми бит, затем килобайт (кбайт) - 1024 байта, мегабайт (мбайт) - 1024 кбайта, гигобайт (гбайт) - 1024мбайт.

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

Таким образом, информация представляется в виде конечной последовательности 0 и 1. Например целое неотрицательное  число А₂=Т 11110000₂ будет храниться в ячейке следующим образом:

Значит, мы можем записать все числа от 0 до 255 в двоичной системе счисления в 1 ячейке памяти.

1.2 Представление чисел в компьютере

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

Для хранения целых неотрицательных  чисел отводится одна ячейка памяти состоящая из восьми бит.

Например, число 19₁₀ будет выглядеть:

Для хранения целых чисел  со знаком (отрицательных) отводиться две ячейки памяти (16 битов), причем старший (левый) разряд отводиться под  знак числа (если число положительное, то в знаковый разряд записывается 0, если отрицательное - 1).

Например, число -98₁₀ будет выглядеть:

Представление целых чисел  в компьютере в формате «знак - величина» называется прямым кодом  числа. Например, число 200210=11111010010₂ будет представлено в шестнадцатиразрядном представлении следует следующим образом:

Для представления отрицательных  чисел используется дополнительный код. Дополнительный код позволяет  заменить арифметическую операцию

вычитания операцией сложения, что существенно упрощает работу процессора и увеличивает его  быстродействие. Дополнительный код  представляет собой дополнение модуля отрицательного числа А до О,

2ⁿ-|А|+|А| =0

поскольку в компьютерной 2ⁿ=0.

Алгоритм построения такого кода довольно прост:

1. Записать модуль числа  в прямом коде.

2. Получить обратный код  числа (то есть заменить все нули на единицы, а все единицы на нули).

3. К полученному результату  прибавить единицу.

Запишем дополнительный код  отрицательного числа -2002 для 16-разрядного представления:

Запишем дополнительный код  отрицательного числа -16320 для 16-разрядного представления:

1.3 Способы построения двоичных кодов

Начиная с конца 60-х годов, компьютеры все больше использовать для обработки текстовой информации и в настоящее время большая часть компьютеров в мире занято именно обработкой текстовой информации.

Традиционно для кодирования одного символа используется количество информации равное 1 байту, то есть 8 бит. Если рассматривать символы как возможные события, то получаем, что количество различных символов, которые можно закодировать, будет равно 256. Такое количество символов вполне достаточно для представления текстовой информации, включая прописные и строчные буквы русского и латинского алфавитов, а так же цифры, знаки препинания и математических операций, графические символы и так далее.

Но способов построения таких  кодов очень много, рассмотрим некоторые  из них:

Алфавитное неравномерное  двоичное кодирование

При алфавитном способе двоичного  кодирования символы некоторого первичного алфавита (например, русского) кодируются комбинациями символов двоичного  алфавита (т.е. 0 и 1), причем, длина кодов  и, соответственно, длительность передачи отдельного кода, могут различаться. Оптимизировать кодирование можно  за счет суммарной длительности сообщения.

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

Возможны различные варианты двоичного кодирования, однако, не все  они будут пригодны для практического  использования - важно, чтобы закодированное сообщение могло быть однозначно декодировано, т.е. чтобы в последовательности 0 и 1, которая представляет собой многобуквенное кодированное сообщение, всегда можно было бы различить обозначения отдельных букв.

Рассмотрим пример построения двоичного кода для символов русского алфавита:

Неравномерный код с разделителями

Для того что бы было проще  декодировать сообщения был придуман код с разделителями.

Проще всего достичь однозначного декодирования, если коды будут разграничены разделителем - некоторой постоянной комбинацией двоичных знаков. Условимся, что разделителем отдельных кодов букв будет последовательность 00 (признак конца знака), а разделителем слов - 000 (признак конца слова - пробел). Довольно очевидными оказываются следующие правила построения кодов:

— код признака конца  знака может быть включен в  код буквы, поскольку не существует отдельно (т.е. кода всех букв будут  заканчиваться 00);

— коды букв не должны содержать  двух и более нулей подряд в

середине (иначе они будут  восприниматься как конец знака);

— код буквы (кроме пробела) всегда должен начинаться с 1;

— разделителю слов (000) всегда предшествует признак конца знака;

при этом реализуется последовательность 00000 (т.е. если в конце кода встречается комбинация ...000 или ...0000, они не воспринимаются как разделитель слов); следовательно, коды букв могут оканчиваться на 0 или 00 (до признака конца знака).

Длительность передачи каждого  отдельного кода 4 очевидно, может быть найдена: t_i = k_i • τ, где k_i - количество элементарных сигналов (бит) в коде символа L.

Алфавитное неравномерное  двоичное кодирование. Префиксный код

Рассмотрев один из вариантов  двоичного неравномерного кодирования, попробуем найти ответы на следующие  вопросы: возможно ли такое кодирование  без использования разделителя  знаков? Существует ли наиболее оптимальный  способ неравномерного двоичного кодирования?

Суть первой проблемы состоит  в нахождении такого варианта кодирования  сообщения, при котором последующее  выделение из него каждого отдельного знака (т.е. декодирование) оказывается  однозначным без специальных  указателей разделения знаков. Наиболее простыми и употребимыми кодами такого типа являются так называемые префиксные коды, которые удовлетворяют следующему условию (условию Фано):

ииииииииииии

Неравномерный код может  быть однозначно декодирован, если никакой  из кодов не совпадает с началом  какого-либо иного более длинного кода.

Например, если имеется код  ПО, то уже не могут использоваться коды 1, 11, 1101, 110101 и пр. Если условие  Фано выполняется, то при прочтении (расшифровке) закодированного сообщения путем сопоставления со списком кодов всегда можно точно указать, где заканчивается один код и начинается другой.

Пример: Пусть имеется  следующая таблица префиксных кодов:

Требуется декодировать сообщение: 00100010000111010101110000110. Декодирование производится циклическим повторением следующих  действий:

1. отрезать от текущего  сообщения крайний левый символ, присоединить к рабочему кодовому  слову;

2. сравнить рабочее кодовое  слово с кодовой таблицей; если  совпадения нет, перейти к (1);

3. декодировать рабочее  кодовое слово, очистить его;

4. проверить, имеются ли  еще знаки в сообщении; если  «да», перейти к (1).

Применение данного алгоритма  дает:

Доведя процедуру до конца, получим сообщение: «мама мыла раму».

Код Хаффмана

Способ оптимального префиксного  двоичного кодирования был предложен  Д.Хаффманом. Построение кодов Хаффмана мы рассмотрим на следующем примере: пусть имеется первичный алфавит А, состоящий из шести знаков a₁…а₆ с вероятностями появления в сообщении, соответственно, 0,3; 0,2; 0,2; 0,15; 0,1; 0,05. Создадим новый вспомогательный алфавит А_b объединив два знака с наименьшими вероятностями (а₅ и а₆) и заменив их одним знаком (например, а⁽¹⁾); вероятность нового знака будет равна сумме вероятностей тех, что в него вошли, т.е. 0,15; остальные знаки исходного алфавита включим в новый без изменений; общее число знаков в новом алфавите, очевидно, будет на 1 меньше, чем в исходном. Аналогичным образом продолжим создавать новые алфавиты, пока в последнем не останется два знака; ясно, что число таких

шагов будет равно N - 2, где N - число знаков исходного алфавита (в нашем случае N = 6, следовательно, необходимо построить 4 вспомогательных  алфавита). В промежуточных алфавитах  каждый раз будем переупорядочивать  знаки по убыванию вероятностей. Всю  процедуру построения представим в  виде таблицы:

Теперь в обратном направлении  поведем процедуру кодирования. Двум знакам последнего алфавита присвоим коды 0 и 1 (которому какой - роли не играет; условимся, что верхний знак будет  иметь код 0, а нижний - 1). В нашем  примере знак а₁⁽⁴⁾ алфавита А⁽⁴⁾, имеющий вероятность 0,6 , получит код 0, а а₂⁽⁴⁾ с вероятностью 0,4 - код 1. В алфавите A⁽³⁾ знак а₁⁽³⁾ с вероятностью 0,4 сохранит свой код (1); коды знаков a₂⁽³⁾ и a₃⁽³⁾, объединенных знаком a₁⁽⁴⁾ с вероятностью 0,6 , будут уже двузначным: их первой цифрой станет код связанного с ними знака (т.е. 0), а вторая цифра -как условились - у верхнего 0, у нижнего - 1; таким образом, а₂⁽³⁾ будет иметь код 00,  a a₃⁽³⁾ - код 01.  Полностью процедура кодирования

представлена в следующей таблице:

Из самой процедуры  построения кодов легко видеть, что  они удовлетворяют условию Фано и, следовательно, не требуют разделителя. Средняя длина кода при этом оказывается: К⁽²⁾ = 0,3-2+0,2-2+0,2-2+0,15-3+0,1-4+0,05-4 = 2,45

Для сравнения можно найти  I₁^{A)-она оказывается равной 2,409. что соответствует избыточности кода Q = 0,0169, т.е. менее 2%.

Код Хаффмана важен в теоретическом  отношении, поскольку он является самым  экономичным из всех возможных, т.е. ни для какого метода алфавитного  кодирования длина кода не может  оказаться меньше, чем код Хаффмана. Можно заключить, что существует метод построения оптимального неравномерного алфавитного кода. Метод Хаффмана и его модификация - метод адаптивного  кодирования (динамическое кодирование  Хаффмана) - нашли применение в программах-архиваторах, программах резервного копирования  файлов и дисков, в системах сжатия информации в модемах и факсах.

Равномерное алфавитное двоичное кодирование. Байтовый код

В этом случае двоичный код  первичного алфавита строится цепочками  равной длины, т.е. со всеми знаками  связано одинаковое количество информации равное 1₀. Передавать признак конца знака не требуется, поэтому для определения длины кодовой цепочки можно воспользоваться формулой: К⁽²⁾ > log₂N. Приемное устройство просто отсчитывает оговоренное заранее количество элементарных сигналов и интерпретирует цепочку (устанавливает, какому знаку она соответствует). Правда, при этом недопустимы сбои, например, пропуск (непрочтение) одного элементарного сигнала приведет к сдвигу всей кодовой последовательности и неправильной ее интерпретации; решается проблема путем синхронизации передачи или иными способами. С другой стороны, применение равномерного кода оказывается одним из средств контроля правильности передачи, поскольку факт поступления лишнего элементарного сигнала или, наоборот, поступление неполного кода сразу интерпретируется как ошибка.

Пример: