ЛК2(б) > Основные формы представления чисел в компьютере

Тема: Особенности представления чисел в компьютере, ошибки округления и способы ускорения выполнения программы цифровой обработки сигналов

5. Представление информации в цифровом компьютере

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

В любом процессоре (вычислителе) цифровые данные представляются определенным количеством бит – 8, 16, 32 или 64. В зависимости от количества бит, определяется диапазон возможных значений, которые может принимать данное число. Например, для 8-битного представления числа, количество его возможных значений равно . Это число может отображать разные величины: от 0 до 255; от 1 до 256; от -127 до 128 или от 1 до 10256 – все зависит от назначения битов. Т.е. для правильной интерпретации данных необходимо знать назначение бит и иметь формулу (алгоритм) для перевода последовательности бит в истинное значение величины.

Существует множество алгоритмов кодирования данных, но только два основных формата их представления – с фиксированной точкой или целые числа (fixed point or integer number) и с плавающей запятой или действительные числа (floating point or real number). Для каждого из этих двух форматов существует два основных параметра – диапазон (range) представляемых чисел (наименьшее и наибольшее число) и точность представления (precision) числа (минимальная величина между двумя соседними значениями).

Формат с фиксированной точкой используется для представления положительных и отрицательных целых чисел. Диапазон значений представляемых чисел равен , где N – разрядность двоичного числа. Если диапазон принимаемых значений числа только положительный (т.е. от 20 до 2N), то такие числа называются беззнаковыми целыми (unsigned integer).

Следующие формы представления чисел используются в том случае, если надо представлять положительные и отрицательные числа. Двоичный код со смещением (offset binary) – в этом случае код «смещается» на пол-шкалы для представления отрицательных чисел, т.е. наименьшему отрицательному числу соответствует двоичный код с нулями во всех двоичных разрядах. Такая форма представления чисел не является широко распространенной и чаще всего используется в ЦАП и АЦП.

Следующая форма представления отрицательных чисел – прямой код (sign and magnitude). В этом случае самый старший бит представляет знак числа и называется – знаковый бит (sign bit). Для положительных чисел он равен нулю, для отрицательных – единице. Остальные биты представляют абсолютное значение числа в двоичном коде. Недостатком такой формы представления чисел является наличие двух нулей – 0000 (положительный ноль) и 1000 (отрицательный ноль).

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

Наиболее удобная форма для представления отрицательных чисел с точки зрения выполнения арифметических операций (она же используется во всех компьютерах) – двоичный дополнительный код (two’s complement). Чтобы понять принцип представления чисел в дополнительном коде, представьте себе двоичный счетчик со сложением/вычитанием. Если счетчик находится в нулевом состоянии (0000) то прибавление единицы переведет его в состояние 0001 (единица в дополнительном коде), следующее состояние будет 0010 (двойка в дополнительном коде). Если в состоянии 0000 от счетчика вычесть единицу, то он перейдет в состояние 1111 (мину единица в дополнительном коде), дальше 1110 (минус два в дополнительном коде) и т.д. Также как и для прямого кода, старший бит представляет знак числа в дополнительном коде. Положительные числа соответствуют прямому коду. Для получения отрицательного числа необходимо проделать следующие действия:

– представить модуль числа в двоичном коде;

– проинвертировать его (заменить нули единицами и наоборот);

– прибавить к результату 1.

Форма дополнительного кода сложна для понимания, но очень хорошо подходит для выполнения арифметических действий.

Формы представления чисел в формате с плавающей запятой сложнее, чем в формате с фиксированной запятой. Основная идея – такая же, как и в научных представлениях чисел, где мантисса
(mantissa) умножается на число десять в степени, равной экспоненте (exponent). Например, число 5.4321х106, где 5.4321 представляет мантиссу, а 6 – экспоненту. Такая форма записи удобная для представления очень больших и очень маленьких чисел. Отметим, что научная форма представления чисел является нормализованной, т.к. только одна, не равная нулю цифра, располагается слева от децимальной точки. Это достигается выбором необходимой экспоненты для числа.

Форма представления числа с плавающей запятой схожа с научной формой записи, за исключением того, что в ней используется основание равное 2, а не 10. Существует несколько форм записи чисел в формате с плавающей запятой, но наиболее распространенным является стандарт ANSI/IEEE Std×754-1985. Этот стандарт описывает форму представления 32-битных чисел, называемый с одинарной точностью (signal precision), и 64-битных чисел, называемых с двойной точностью (double precision). Разряды в 32-битном числе с плавающей запятой распределяются следующим образом: биты с 0 по 22 занимает мантисса, биты с 23 по 30 – экспонента, а бит 31 – знаковый бит. Представляемое этой формой число определяется следующим соотношением:

            (2.2)

Выражение определяет знак числа в соответствии со значением S знакового бита, и для положительных чисел S равен 0, а для отрицательных чисел S равен 1. Переменная E – число в диапазоне от 0 до 255, которое представлено 8 битами экспоненты. Вычитание 127 из этого числа позволяет формировать диапазон изменения экспоненты от 2-127 до 2128. Другими словами, экспонента представляется со смещением, равным 127. Мантисса М формируется 23 битами, представляющими дробные части числа по основанию два. Например, запись 1.0101, представляет число: . Числа с плавающей запятой являются нормализованными, т.е. только одна цифра, не равная нулю, располагается слева от десятичной точки (называется двоичной точкой). Для числа по основанию 2 существует только одна цифра, не равная нулю – это 1. Поэтому для мантиссы эта цифра всегда равна 1 и ее можно не записывать. Это позволяет выделить еще один бит для мантиссы и увеличивает точность представления числа. Таким образом, мантисса (23-битная) описывает число по следующей формуле:

            (2.3)

Другими словами:

            (2.4)

Если все биты мантиссы, с нулевого по 22, равны нулю, то М принимает значение, равное единице. Если все биты мантиссы равны единице, то значение М очень близко к двойке: .

При таком формате представления, максимальное число может быть: . Соответственно, минимальное представляемое число, равно: .

Для чисел с двойной точностью представления (64-битных), дополнительно увеличивается количество разрядов для представления мантиссы и экспоненты. Так, биты с 0 по 51 выделены для мантиссы, биты с 52 по 62 – для экспоненты, бит 63 – знаковый. Соответственно, наибольшее представляемое число будет равно , а наименьшее: . Это очень большой диапазон значений, достаточен практически для всех видов вычислений.

6. Ошибки округления, возникающие при цифровой обработке сигналов

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

Для примера, рассмотрим двоичное число, записанное с помощью 32 бит. 32 разряда позволяют представить разных чисел. Некоторые языки программирования используют 32-разрядные числа для представления длинных целых чисел (long integer) в формате с фиксирований точкой в дополнительном коде. Такая форма представления позволяет представить любое целое число в диапазоне от -2147783648 до 2147783647. Для сравнения, при представлении 32 разрядами числа с плавающей запятой, диапазон принимаемых значений больше – от до .

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

Из-за конечной точности представления чисел возникают ошибки округления (round-off error), создающие ряд трудностей при цифровой обработке сигналов. Для проверки влияния ошибок округления можно написать программу, которая бы прибавляла к величине Х случайного числа с плавающей запятой, а затем вычитала бы его. В идеале, значение Х должно оставаться постоянным, но на самом деле, из-за ошибок округления, значение Х будет изменяться. Такое смещение значения исходной величины может быть двух видов. Если ошибки округления случайны и могут принимать положительные и отрицательные значения, то наблюдаемая величина тоже будет увеличиваться или уменьшаться по случайному закону. Если же эти ошибки фиксированы и имеют постоянный знак, то и наблюдаемая величина будет изменяться линейно и в определенном направлении. Такие виды ошибок округления называются: случайными ошибками и аддитивными ошибками соответственно. Аддитивные ошибки значительно сильнее влияют на результат, т.к. они имеют тенденцию накапливаться, а случайные ошибки взаимно компенсируются. Суммарная ошибка результата при аддитивных ошибках округления определяется как величина ошибки округления, умноженная на количество операций. При случайных ошибках округления величина ошибки округления умножается на квадратный корень количества операций. В реальных задачах очень сложно контролировать закон, по которому накапливаются ошибки округления.

Учитывая тот факт, что ошибки округления определяются сложно, можно предложить следующий алгоритм. Предположим, что любое число с одинарной точностью вычисляется с ошибкой, равной одной сорокамиллионной от его значения. Эту величину необходимо умножить на количество операций. Это основное определение для вычисления аддитивной ошибки. Ошибки округления значения составляют одну четверть от уровня квантования для одиночной операции. Для чисел с двойной точностью аддитивная ошибка определяется как одна сорокаквадрилионная, умноженная на количество операций.

7. Этапы решения задач цифровой обработки сигналов

Решение задач ЦОС разделяется на три логических уровня: ассемблирование (assembly), компиляция (complied) и прикладное программирование (application specific). Внутри памяти микроконтроллера вся программа хранится в машинных кодах (machine code) – набора нулей и единиц, которые обрабатываются конкретными электронными схемами. Работать человеку с программами, представленными в машинных кодах, очень сложно, поэтому для набора цифр была разработана форма их представления с помощью имен, отражающих их функцию. Такой уровень представления программы называется ассемблерной. Ассемблерные программы легче понимаются, они адекватно соответствуют машинному коду (транслируется один к одному в машинный код) и описываю все действия, выполняемые микроконтроллером. Программа, называемая ассемблером, переводит ассемблерную программу (называемую исходным кодом (source code)) в соответствующий машинный код (называемый объектным кодом (object code) или исполнительным кодом (executable code)). Исполнительный код выполняется непосредственно микроконтроллером. Естественно, что программирование на ассемблере требует от программиста отличного понимания архитектуры конкретного микроконтроллера. Ассемблерная программа непосредственно взаимодействует с устройствами внутренней архитектуры микроконтроллера: регистрами, областями памяти, битами статуса и пр.

Следующий логический уровень программирования позволяет манипулировать абстрактными переменными, без их соотнесения к конкретным устройствам. Этот уровень называется компилируемые или высокоуровневые языки. Примером таких языков могут быть: С, BASIC, FORTRAN, PASCAL, APL, COBOL, LIST и т.д. Программа, называемая компилятором, преобразует исходный код на языке высокого уровня непосредственно в машинный код.

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

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

Граница между этими тремя уровнями весьма расплывчата. Следует отметить, что на первом уровне вы работаете с аппаратурой, на втором – с абстрактными переменными, на третьем – с процедурами и алгоритмами. Есть еще один важный момент. Когда вы работаете с языком высокого уровня, ваш результат зависит от программиста, писавшего программу компилятора, его понимания архитектуры микроконтроллеров. Когда вы работаете на уровне прикладных программ, ваш результат зависит от программиста, разрабатывавшего эти алгоритмы и программы. Если вы работаете на верхних уровнях программирования, ваш исполнительный код всегда будет проигрывать по используемой памяти, скорости выполнения и точности. Подпрограмма, написанная на языке ассемблер, выполняется в 1,5 – 2 раза быстрее, чем на высокоуровневом языке.

8. Цифровые сигнальные процессоры: области применения и особенности

Скорость выполнения задачи существенно зависит от архитектуры вычислителя. Если в вычислительной системе, кроме центрального процессорного устройства ЦПУ (Central Processing Unit, CPU) присутствует математический сопроцессор или арифметико-логическое устройство, AЛУ (math coprocessor, arithmetic logic unit, ALU) скорость выполнения программы существенно возрастает. Основная память должна быть очень большой и очень быстрой. Поэтому, часто используется вспомогательная память, очень быстрая, но небольшого объема – кэш память (memory cache). Скорость обмена данными зависит от количества шин для передачи. Данные передаются гораздо быстрее внутри кристалла, чем между кристаллами. Еще медленнее данные передаются между печатными платами.

Для уменьшения времени выполнения операций для задач ЦОС были разработаны специальные процессора, называемые цифровые сигнальные процессора, ЦСП (DSP microprocessor, Digital Signal Processor, DSP) с RISC (Reduced Instruction Set Computer) – архитектурой. Эти процессора работают с данными в формате с фиксированной точкой и с плавающей запятой. Их архитектура имеет ряд особенностей – (1) наличие очень быстрой кэш-памяти внутри кристалла, (2) – независимый тип доступа к памяти программ и памяти данных (так называемая Гарвардская архитектура, Harvard Architecture), (3) быстрый вычислитель для выполнения математических операций, (4) использование конвейера (pipeline). Конвейерная архитектура – разбиение цикла выполнения команды на несколько подциклов. Т.е., начало выполнения следующей команды происходит еще до завершения выполнения предыдущей.

9. Способы повысить быстродействие выполнения программы

Еще ряд советов как повысить быстродействие программы:

1) Где возможно, используйте числа с фиксированной точкой вместо чисел с плавающей запятой;

2) Старайтесь не использовать в программе функций типа , , и т.д. Эти функции вычисляются разложением в ряд – с большим количеством операций сложения и умножения. Заменяйте их табличными функциями (look-up table (LUT)).

3) Хорошо изучите и определите, какие операции выполняются медленно в вашей системе, а какие быстро. Используйте только быстрые операции, где это возможно!