Среди всего разнообразия информации, обрабатываемой на компьютере, значительную часть составляют числовая, текстовая, графическая и аудиоинформация. Познакомимся с некоторыми способами кодирования этих типов информации в ЭВМ.
Кодирование чисел
Существуют два основных формата представления чисел в памяти компьютера. Один из них используется для кодирования целых чисел, второй (так называемое представление числа в формате с плавающей точкой) используется для задания некоторого подмножества действительных чисел.
Множество целых чисел, представимых в памяти ЭВМ, ограничено. Диапазон значений зависит от размера области памяти, используемой для размещения чисел. В k-разрядной ячейке может храниться 2 k различных значений целых чисел.
Чтобы получить внутреннее представление целого положительного числа N, хранящегося в k-разрядном машинном слове, необходимо:
- перевести число N в двоичную систему счисления;
- полученный результат дополнить слева незначащими нулями до k разрядов.
Пример. Получить внутреннее представление целого числа 1607 в 2-х байтовой ячейке.
Просто о двоичной системе счисления и двоичном коде. #1
Переведем число в двоичную систему: 160710 = 110010001112. Внутреннее представление этого числа в ячейке будет следующим: 0000 0110 0100 0111.
Для записи внутреннего представления целого отрицательного числа (-N) необходимо:
- получить внутреннее представление положительного числа N;
- обратный код этого числа заменой 0 на 1 и 1 на 0;
- полученному числу прибавить 1.
Пример. Получим внутреннее представление целого отрицательного числа -1607. Воспользуемся результатом предыдущего примера и запишем внутреннее представление положительного числа 1607: 0000 0110 0100 0111. Инвертированием получим обратный код : 1111 1001 1011 1000. Добавим единицу: 1111 1001 1011 1001 — это и есть внутреннее двоичное представление числа -1607.
Формат с плавающей точкой использует представление вещественного числа R в виде произведения мантиссы m на основание системы счисления n в некоторой целой степени p, которую называют порядком: R = m * n p .
Представление числа в форме с плавающей точкой неоднозначно. Например, справедливы следующие равенства:
12.345 = 0.0012345 x 10 4 = 1234.5 x 10 -2 = 0.12345 x 10 2
Чаще всего в ЭВМ используют нормализованное представление числа в форме с плавающей точкой. Мантисса в таком представлении должна удовлетворять условию: 0.1p p. Иначе говоря, мантисса меньше 1 и первая значащая цифра — не ноль (p — основание системы счисления).
В памяти компьютера мантисса представляется как целое число, содержащее только значащие цифры (0 целых и запятая не хранятся), так для числа 12.345 в ячейке памяти, отведенной для хранения мантиссы, будет сохранено число 12345. Для однозначного восстановления исходного числа остается сохранить только его порядок, в данном примере — это 2.
Кодирование текста
Множество символов, используемых при записи текста, называется алфавитом. Количество символов в алфавите называется его мощностью.
Как на самом деле работает двоичный код?
Для представления текстовой информации в компьютере чаще всего используется алфавит мощностью 256 символов. Один символ из такого алфавита несет 8 бит информации, т. к. 2 8 = 256. Но 8 бит составляют один байт, следовательно, двоичный код каждого символа занимает 1 байт памяти ЭВМ.
Все символы такого алфавита пронумерованы от 0 до 255, а каждому номеру соответствует 8-разрядный двоичный код от 00000000 до 11111111. Этот код является порядковым номером символа в двоичной системе счисления .
Для разных типов ЭВМ и операционных систем используются различные таблицы кодировки, отличающиеся порядком размещения символов алфавита в кодовой таблице. Международным стандартом на персональных компьютерах является уже упоминавшаяся таблица кодировки ASCII.
Принцип последовательного кодирования алфавита заключается в том, что в кодовой таблице ASCII латинские буквы (прописные и строчные) располагаются в алфавитном порядке. Расположение цифр также упорядочено по возрастанию значений.
Стандартными в этой таблице являются только первые 128 символов, т. е. символы с номерами от нуля (двоичный код 00000000) до 127 (01111111). Сюда входят буквы латинского алфавита, цифры, знаки препинания, скобки и некоторые другие символы. Остальные 128 кодов, начиная со 128 (двоичный код 10000000) и кончая 255 (11111111), используются для кодировки букв национальных алфавитов, символов псевдографики и научных символов. О кодировании символов русского алфавита рассказывается в главе «Обработка документов».
Кодирование графической информации
В видеопамяти находится двоичная информация об изображении, выводимом на экран. Почти все создаваемые, обрабатываемые или просматриваемые с помощью компьютера изображения можно разделить на две большие части — растровую и векторную графику .
Растровые изображения представляют собой однослойную сетку точек, называемых пикселами (pixel, от англ. picture element ). Код пиксела содержит информацию о его цвете.
Для черно-белого изображения (без полутонов) пиксел может принимать только два значения: белый и черный (светится — не светится), а для его кодирования достаточно одного бита памяти: 1 — белый, 0 — черный.
Пиксел на цветном дисплее может иметь различную окраску, поэтому одного бита на пиксел недостаточно. Для кодирования 4-цветного изображения требуются два бита на пиксел, поскольку два бита могут принимать 4 различных состояния. Может использоваться, например, такой вариант кодировки цветов: 00 — черный, 10 — зеленый, 01 — красный, 11 — коричневый.
На RGB-мониторах все разнообразие цветов получается сочетанием базовых цветов — красного (Red), зеленого (Green), синего (Blue), из которых можно получить 8 основных комбинаций:
| черный | |||
| 1 | синий | ||
| 1 | зеленый | ||
| 1 | 1 | голубой |
| 1 | красный | ||
| 1 | 1 | розовый | |
| 1 | 1 | коричневый | |
| 1 | 1 | 1 | белый |
Разумеется, если иметь возможность управлять интенсивностью (яркостью) свечения базовых цветов, то количество различных вариантов их сочетаний, порождающих разнообразные оттенки, увеличивается. Количество различных цветов — К и количество битов для их кодировки — N связаны между собой простой формулой: 2 N = К.
В противоположность растровой графике векторное изображение многослойно. Каждый элемент векторного изображения — линия, прямоугольник, окружность или фрагмент текста — располагается в своем собственном слое, пикселы которого устанавливаются независимо от других слоев. Каждый элемент векторного изображения является объектом, который описывается с помощью специального языка (математических уравнения линий, дуг, окружностей и т. д.). Сложные объекты (ломаные линии, различные геометрические фигуры) представляются в виде совокупности элементарных графических объектов.
Объекты векторного изображения, в отличии от растровой графики, могут изменять свои размеры без потери качества (при увеличении растрового изображения увеличивается зернистость). Подробнее о графических форматах рассказывается в разделе «Графика на компьютере».
Кодирование звука
Из курса физики вам известно, что звук — это колебания воздуха. Если преобразовать звук в электрический сигнал (например, с помощью микрофона), мы увидим плавно изменяющееся с течением времени напряжение. Для компьютерной обработки такой — аналоговый — сигнал нужно каким-то образом преобразовать в последовательность двоичных чисел.
Поступим следующим образом. Будем измерять напряжение через равные промежутки времени и записывать полученные значения в память компьютера . Этот процесс называется дискретизацией (или оцифровкой), а устройство, выполняющее его — аналого-цифровым преобразователем (АЦП).
Для того чтобы воспроизвести закодированный таким образом звук, нужно выполнить обратное преобразование (для него служит цифро-аналоговый преобразователь — ЦАП ), а затем сгладить получившийся ступенчатый сигнал.
Чем выше частота дискретизации (т. е. количество отсчетов за секунду) и чем больше разрядов отводится для каждого отсчета, тем точнее будет представлен звук. Но при этом увеличивается и размер звукового файла. Поэтому в зависимости от характера звука, требований, предъявляемых к его качеству и объему занимаемой памяти, выбирают некоторые компромиссные значения.
Описанный способ кодирования звуковой информации достаточно универсален, он позволяет представить любой звук и преобразовывать его самыми разными способами. Но бывают случаи, когда выгодней действовать по-иному.
Человек издавна использует довольно компактный способ представления музыки — нотную запись. В ней специальными символами указывается, какой высоты звук, на каком инструменте и как сыграть. Фактически, ее можно считать алгоритмом для музыканта, записанным на особом формальном языке . В 1983 г. ведущие производители компьютеров и музыкальных синтезаторов разработали стандарт, определивший такую систему кодов. Он получил название MIDI .
Конечно, такая система кодирования позволяет записать далеко не всякий звук, она годится только для инструментальной музыки. Но есть у нее и неоспоримые преимущества: чрезвычайно компактная запись, естественность для музыканта (практически любой MIDI -редактор позволяет работать с музыкой в виде обычных нот), легкость замены инструментов, изменения темпа и тональности мелодии.
Заметим, что существуют и другие, чисто компьютерные, форматы записи музыки. Среди них следует отметить формат MP3, позволяющий с очень большим качеством и степенью сжатия кодировать музыку. При этом вместо 18-20 музыкальных композиций на стандартный компакт-диск (CDROM) помещается около 200. Одна песня занимает примерно 3,5 Mb, что позволяет пользователям сети Интернет легко обмениваться музыкальными композициями.
Источник: intuit.ru
2. Кодирование программ и система команд
Все операции в ЭВМ выполняются над электрическими сигналами, закодированными двоичной цифрой 0 или 1. Поэтому перед занесением в память данные и команды должны быть вручную или аппаратно преобразованы в двоичную форму. Однако при написании программы команды могут быть записаны в любой другой форме (например, мнемонической, как в табл. 1). В общем случае программа может кодироваться четырьмя способами: в двоичной, восьмеричной, шестнадцатеричной и символической или мнемонической форме.
Двоичная форма команды. Эта форма является единственной, которую понимает машина. Каждой ЭВМ присуща система команд в двоичном коде, которая понятна ей. Регистр команд, куда помещается команда из памяти, связан электрическими цепями с устройством управления ЭВМ, где производится декодирование команды и инициируются сигналы по реализации команды. В табл.
2 приведено содержимое части памяти ЭВМ, где хранятся программа и данные для суммирования двух чисел из примера параграфа 2.1. Левый столбец — это адреса ячеек в двоичной форме. Правый столбец представляет содержимое ячеек в двоичной форме. Адрес имеет 11 разрядов (память ЭВМ состоит из 2048 = 2 11 ячеек), а каждая из ячеек — по 16 разрядов. Для удобства чтения двоичных чисел и их перевода в шестнадцатеричную систему они разбиты на тетрады.
Восьмеричное и шестнадцатеричное кодирование. Из предыдущего примера ясно, что записывать программу в двоичном коде очень неудобно и утомительно, если учесть, что средняя по сложности программа состоит из нескольких сотен или тысяч нулей и единиц. Для сокращения записи целесообразно использовать систему счисления с основанием 2 3 = 8 или 2 4 = 16.
Выбор для кодирования команд той или иной системы счисления в основном связан с форматом команд ЭВМ. В нашем случае удобнее шестнадцатеричная система, так как большинство полей в командах базовой ЭВМ (см. рис. 3) равно или кратно 4. В табл. 3 приведена та же программа, что и в табл. 1 и 2, только закодированная в шестнадцатеричной системе.
Для программиста такое кодирование более удобно, чем двоичное.
Таблица 2 Таблица 3
Пример двоичного кодирования Пример шестнадцатеричного кодирования
содержимого памяти содержимого памяти
Мнемоническое (символическое) кодирование. Шестнадцатеричное (или восьмеричное) кодирование имеет очевидное преимущество перед двоичным. Однако для длинных программ и оно неудобно. Программист должен выучить наизусть шестнадцатеричные коды всех команд, использующихся в машине (в некоторых ЭВМ их более сотни).
Чтобы упростить процесс написания, отладки и чтения программы, предложен мнемонический или символический код: каждая команда представляется простым двух-, трех- или четырехбуквенным мнемоническим символом. Мнемонические символы значительно легче связать с машинными операциями, так как их можно выбирать таким образом, чтобы они напоминали название команды. Большинство мнемонических кодов — это сокращения английских названий команд: SUB от SUBtract (вычесть), BR от Branch (перейти), BPL от Branch if Plus (перейти по положительному числу) и т. п. Намного легче запомнить, что инвертирование аккумулятора (CoMplement Accumulator) кодируется СМА, чем запомнить двоичный код 1111010000000000 или даже его шестнадцатеричный эквивалент F400. Пример символического кодирования программы был приведен в параграфе 1 (см. табл. 1).
Хотя символическое кодирование очень удобно для программиста, оно не может быть понято машиной. Единственным языком, понятным машине, является язык двоичных кодов. Следовательно, необходимо транслировать символическую программу в ее двоичный эквивалент. Это можно сделать вручную, используя таблицы соответствия (вида табл. 4).
На практике трансляция осуществляется специальной машинной программой.
Классификация команд. ЭВМ способна понимать и выполнять определенный набор команд. При составлении программы программист ограничен этими командами. Количество и тип команд изменяются в зависимости от возможностей и назначения ЭВМ.
В зависимости от того, к каким блокам машины обращается команда или на какие блоки она ссылается, команды можно разделить на три группы: обращения к памяти (адресные команды); обращения к регистрам (регистровые или безадресные); ввода-вывода.
Команды обращения к памяти предписывают машине производить действия с содержимым ячейки памяти, адрес которой указан в адресной части команды. Например, команда ADD 20 из табл. 2.1 является командой обращения к памяти. Она предписывает машине обращение по адресу 20 и использование содержимого этой ячейки в качестве первого операнда. Второй операнд находится в аккумуляторе.
Эти два операнда суммируются.
Безадресные команды выполняют различные действия без ссылок на ячейку памяти. Например, команда CLA из табл. 1 предписывает машине очистить аккумулятор. Эта команда имеет дело с операндом, расположенным в конкретном месте — в аккумуляторе. Другой пример безадресной команды — команда HLT из табл. 1.
Команды ввода-вывода осуществляют обмен данными между ЭВМ и внешними устройствами. В них задаются адрес (название) устройства ввода-вывода и код той операции, которую должно выполнить это устройство (приказ на ввод-вывод).
В табл. 4 дан перечень команд базовой ЭВМ. Подробно действия, выполняемые машиной по этим командам, рассмотрены в следующих параграфах. Поясним одно из описаний: (СК) + 1 => СК в командах ISZ и TSF. После выполнения этой операции счетчик команд будет указывать не на следующую команду программы, а на команду, расположенную за ней.
Это произойдет потому, что после выборки команды ISZ или TSF содержимое счетчика команд уже было увеличеноавтоматически на единицу.
Существует и другой способ разделения команд на группы. Он основан на учете функций, выполняемых командой. Можно выделить восемь типов команд: пересылок или обмена, арифметические, логические, сдвигов, переходов, обращения к подпрограмме, управления и ввода-вывода.
Форматы команд и способы адресации. Ранее рассматривались различные форматы (структуры) команд. Разработчики базовой ЭВМ выбрали три формата 16-битовых (однословных) команд с 4-битовым кодом операций (рис. 4).
Таблица 4.Система команд базовой ЭВМ
С помощью 4-битового числа можно закодировать не более чем 2 4 =16 различныхопераций. Разработчики отвели два кода (1110 и 1111) на команды ввода-вывода и безадресные команды, а так как в этих командах либо используется меньшая по длине адресная часть (8-битовый адрес устройства ввода-вывода на рис. 4, в), либо эта часть вообще отсутствует (рис. 4, б), то появилась возможность иметь до 2 4 = 16 команд ввода-вывода (4-битовый приказ на ввод-вывод) и до 2 12 = 4096 безадресных команд (12-битовое расширение кода операции).
В командах обращения к памяти на адрес отведено 11 бит, что позволяет осуществить прямое адресование всех 2048 (2 м ) ячеек памяти базовой ЭВМ. Однако встречаются приложения, когда в команде целесообразнее размещать не сам адрес операнда (результата или перехода), а его указатель, т. е. адрес ячейки памяти, в которой сохраняется адрес операнда (результата или перехода). Такое косвенное адресование упрощает построение циклических программ, организацию работы с подпрограммами, а также создает условия для расширения адресуемого пространства (косвенное адресование 16-битовых ячеек базовой ЭВМ позволяет ей иметь память объемом до 2 16 = 65536 слов).
Для указания вида адресации в командах используется бит с номером 11 (рис. 4, а), в который при прямой адресации следует записывать 0, а при косвенной— 1. В мнемонических изображениях команд для указания косвенной адресации операнд помещается в скобки. Так, на рис. 5 команда ADD 25 или 4025 указывает, что из ячейки 25 должно быть взято число (53), которое нужно сложить с содержимым аккумулятора. Команда же ADD (25) или 4825 указывает, что из ячейки 25 должен быть взят адрес ячейки (53), в которой хранится число (47), которое и нужно сложить с содержимым аккумулятора. («А это веселая птица-синица, которая ловко ворует пшеницу, которая в темном чулане хранится в доме, который построил Джек.» Похоже?).
Источник: studfile.net
Печатать двоичное представление числа — C, C++, Java и Python
Печатайте двоичное представление заданного числа в C, C++, Java и Python, используя встроенные методы и пользовательские процедуры.
Input: 20
Output: 00000000000000000000000000010100
Input: 64
Output: 00000000000000000000000001000000
Input: 127
Output: 00000000000000000000000001111111
Input: -1
Output: 11111111111111111111111111111111
1. Итеративное решение
Идея состоит в том, чтобы проверить, если i’th бит устанавливается для каждой позиции i в данном целом n . Если i’th бит установлен для позиции i в целом n , затем установите i’th бит в 1 в двоичном представлении n ; иначе 0. i находится в диапазоне от 0 до 31 для 32-битного целого числа.
Выражение 1 дает число, которое имеет только i’th набор бит. Если мы делаем побитовое AND этого выражения с любым числом n , т.е. n (n = 20)
00000100 (1 O(c) , и дополнительное пространство не используется. Здесь, c указывает постоянное значение. Ниже приведена реализация на C, Java и Python, основанная на приведенной выше идее:
Источник: www.techiedelight.com