Потапов И.В. Элементы прикладной теории цифровых автоматов - файл n1.doc

приобрести
Потапов И.В. Элементы прикладной теории цифровых автоматов
скачать (623.4 kb.)
Доступные файлы (1):
n1.doc3790kb.15.02.2011 14:37скачать

n1.doc

  1   2   3   4   5   6   7   8   9   10   11


Министерство образования и науки Российской Федерации




Государственное образовательное учреждение

высшего профессионального образования

«Омский государственный технический университет»



И. В. Потапов




ЭЛЕМЕНТЫ ПРИКЛАДНОЙ ТЕОРИИ
ЦИФРОВЫХ АВТОМАТОВ



Учебное пособие


Омск

Издательство ОмГТУ

2011

УДК 004.315(075)

ББК 32.973.2я73

П64


Рецензенты:

М. Ф. Шакиров, канд. техн. наук, доцент, зам. руководителя
Управления Роскомнадзора по Омской области;

В. Т. Гиль, канд. техн. наук, доцент ОмА МВД России

Потапов, И. В.

П64 Элементы прикладной теории цифровых автоматов: учеб. пособие /
И. В. Потапов. – Омск: Изд-во ОмГТУ, 2011. – 156 с.
ISBN 978-5-8149-1039-4
В пособии рассматриваются основы построения алгоритмов выполнения арифметических операций над числами, представленными прямыми и инверсными кодами в двоичной однородной позиционной системе счисления, а также в D-кодах. Даны подробные примеры выполнения арифметических операций. Рассмотрены различные способы представления числовой информации в ЭВМ. Описаны базовые принципы построения логических схем прямого распространения по их аналитическому описанию и методы минимизации таких схем. Рассмотрены базовые подходы к построению моделей функционирования и структурному синтезу цифровых автоматов с памятью.

Пособие предназначено для студентов технических вузов очной, заочной и дистанционной форм обучения, обучающихся по направлению «Информатика и вычислительная техника», изучающих базовые специальные дисциплины.

Печатается по решению редакционно-издательского совета

Омского государственного технического университета

УДК 004.315(075)

ББК 32.973.2я73


© ГОУ ВПО «Омский государственный

технический университет», 2011


ISBN 978-5-8149-1039-4

ОГЛАВЛЕНИЕ
ВВЕДЕНИЕ 5

1. ПРЕДСТАВЛЕНИЕ ЧИСЕЛ В ЭВМ 8

1.1. Позиционные системы счисления 8

1.2. Обоснование применения в ЭВМ двоичной системы счисления 10

1.3. Представление двоичных чисел с фиксированной
и плавающей запятой 12

1.4. Прямой и инверсные коды чисел 15

1.5. Двоично-десятичные коды чисел 18

Вопросы для самоконтроля 21

2. АРИФМЕТИЧЕСКИЕ ОПЕРАЦИИ В ДВОИЧНЫХ КОДАХ 22

2.1. Сложение двоичных кодов 22

2.2. Вычитание двоичных кодов 25

2.3. Выполнение операции округления чисел 26

2.3.1. Округление прямых кодов 26

2.3.2. Округление инверсных кодов 29

2.4. Умножение двоичных кодов 29

2.4.1. Умножение прямых кодов чисел 30

2.4.2. Ускоренное выполнение операции умножения 34

2.4.3. Умножение инверсных кодов чисел 40

2.5. Деление двоичных кодов 42

2.5.1. Деление прямых кодов чисел 43

2.5.2. Ускоренное выполнение операции деления 47

2.5.3. Деление дополнительных кодов чисел 50

2.6. Извлечение квадратного корня 52

2.7. Выполнение арифметических операций в D-кодах 55

2.7.1. Сложение в D-кодах 55

2.7.2. Умножение в D-кодах 57

2.7.3. Деление в D-кодах 60

Вопросы для самоконтроля 62

3. ПЕРЕКЛЮЧАТЕЛЬНЫЕ ФУНКЦИИ 64

3.1. Основные определения и способы задания ПФ 65

3.2. Элементарные логические функции 68

3.3. Основные законы алгебры логики 69

3.4. Полные системы переключательных функций 70

3.5. Канонические формы аналитического представления ПФ 72

3.6. Кубическое представление ПФ 76

3.7. Синтез комбинационных схем 78

3.7.1. Синтез КС на логических элементах 78

3.7.2. Синтез КС на дешифраторах 80

3.7.3 Синтез КС на мультиплексорах 83

3.7.4 Синтез многовыходных схем 85

3.8. Риски сбоя в комбинационных схемах 85

Вопросы для самоконтроля 88

4. МИНИМИЗАЦИЯ ПЕРЕКЛЮЧАТЕЛЬНЫХ ФУНКЦИЙ 89

4.1. Минимизация ПФ с помощью карт Карно 92

4.2. Минимизация ПФ методом Квайна 96

4.3. Минимизация методом Квайна – Мак-Класки 100

4.4. Минимизация ПФ методом Блейка – Порецкого 103

4.5. Минимизация ПФ, заданных в конъюнктивной форме 105

4.6. Минимизация не полностью определенных ПФ 107

4.7. Минимизация систем ПФ 109

4.8. Минимизация ПФ в универсальных базисах И-НЕ, ИЛИ-НЕ 115

Вопросы для самоконтроля 119

5. МОДЕЛИРОВАНИЕ РАБОТЫ И СИНТЕЗ АВТОМАТОВ
С ПАМЯТЬЮ 120

5.1. Основные модели, понятия и определения 120

5.1.1. Общее понятие цифрового автомата с памятью 120

5.1.2. Основные модели цифровых автоматов 122

5.1.3. Описание функционирования цифровых автоматов 124

5.1.4. Задание цифровых автоматов 125

5.1.5. Правила перехода между моделями Мили и Мура 127

5.2. Минимизация числа состояний цифровых автоматов 129

5.2.1. Минимизация числа состояний синхронного автомата
методом Полла-Ангера 130

5.2.2. Минимизация числа состояний автомата Мура методом
l-эквивалентных разбиений 135

5.2.3. Минимизация числа состояний автомата Мили методом
l-эквивалентных разбиений 137

5.3. Структурный синтез цифровых автоматов 140

5.3.1. Типы элементарных автоматов, обладающие полной
системой переходов-выходов 141

5.3.2. Основные этапы структурного синтеза 144

5.4. Рациональный выбор варианта кодирования состояний
синхронных автоматов 151

Вопросы для самоконтроля 153

БИБЛИОГРАФИЧЕСКИЙ СПИСОК 154

ПРИЛОЖЕНИЕ. Задания для выполнения самостоятельных работ 155

ВВЕДЕНИЕ

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

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

В цифровых вычислительных машинах (ЦВМ) все исходные, промежуточные и выходные данные изображаются в виде совокупности цифр в позиционной системе счисления. Наибольшее распространение в цифровых машинах получила двоичная система счисления, в которой цифра имеет только два значения – «0» и «1». Это обусловлено близким к оптимальному соотношению между надежностью, помехоустойчивостью, быстродействием, функциональными возможностями, схемотехнической сложностью, технологичностью производства, удобством эксплуатации
и т.д.

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

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

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

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

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

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

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

Для более полного освоения специализированных дисциплин студентам рекомендуется самостоятельно освоить материал источников, приведенных в разделе «Библиографический список» [1–12].

1. Представление чисел в ЭВМ

1.1. Позиционные системы счисления

Системой счисления называется совокупность приемов записи чисел. Запись числа в некоторой системе счисления называют кодом числа. Отдельную позицию в изображении числа называют разрядом, а номер позиции – номером разряда. Любая система счисления, предназначенная для практического использования, должна обладать следующими свойствами:

– возможностью представления любого числа в заданном диапазоне;

– однозначностью представления чисел;

– простотой оперирования числами.

Системы счисления можно разделить на позиционные и непозиционные. К последним относится, например, римская система счисления. Основными недостатками непозиционных систем счисления являются:

– отсутствие нуля;

– необходимость использования бесконечного количества символов;

– сложность арифметических операций над числами.

Позиционными называют системы счисления, алфавит которых содержит ограниченное число символов, а значение каждой цифры числа определяется ее местоположением в числе. Например, десятичное число 545 означает 5 сотен, 4 десятка и 5 единиц.

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

,

где – цифра i-го разряда числа, ; – основание системы счисления.

Позиционные системы счисления подразделяются на неоднородные и однородные.

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

A = 5∙365∙24∙60∙60∙1+10∙24∙60∙60∙1+22∙60∙60∙1+11∙60∙1+50∙1

является записью времени в 5 лет, 10 суток, 22 часа, 11 минут, 50 секунд. В этом примере p4 = 365 суток, p3 = 24 часа, p2 = 60 минут, p1 = 60 секунд, p0 = 1 секунда.

Однородные позиционные системы счисления характеризуются тем, что в них веса отдельных разрядов числа представляют собой ряд членов геометрической прогрессии со знаменателем p. Число в таких системах счисления представляется полиномом вида

,

причем целой части числа соответствует полином

,

а дробной части – полином

.

Здесь, как и ранее, – цифры числа, p – натуральное целое число, называемое основанием системы счисления. Следует помнить, что основание p записывается числом «10» в своей системе счисления.

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



Примером такой системы может служить так называемая двоично-десятичная система представления чисел (D-код), в которой каждой цифре десятичного числа соответствует двоичная тетрада с весами 8421. Например, десятичное число 259 в двоично-десятичной системе с естественными весами 8421 запишется как


0010

0101

1001

2

5

9.


D-код 8421 редко применяется в вычислительной технике, поскольку он не является самодополняющимся, т.е. двоичные коды любых двух десятичных цифр, дополняющих друг друга до 9 (их сумма равна 9), не дополняют друг друга до 15. Примером самодополняющегося D-кода является D-код 8421+3 с потетрадным избытком 3, в котором вышеприведенное число 259 запишется как


0101

1000

1100

2+3

5+3

9+3.


Более подробно о D-кодах см. в разделе 1.5.
1.2. Обоснование применения в ЭВМ
двоичной системы счисления


При выборе системы счисления для применения в ЭВМ следует учитывать совокупность различных параметров, среди которых можно выделить:

– наличие физических элементов для представления и хранения цифр системы;

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

– быстродействие вычислительных устройств;

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

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

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

Оценим экономичность использования различных систем счисления. Для этого введем некоторую оценочную величину , пропорциональную количеству деталей оборудования [4], где индекс i соответствует i-й системе счисления, а – число разрядов.

Количество чисел, которые можно представить в i-й системе счисления, определяется следующим образом:

,

откуда



Таким образом, выражение для записывается как



Предположим, что величина изменяется не дискретно, а непрерывно и количество чисел одинаково для всех систем. Тогда после исследования на экстремум функционала



получим следующий вывод: оптимальное значение основания системы счисления равно основанию натурального логарифма, т.е. pопт = e  2,7182. Для определения экономичности системы счисления с целочисленным основанием введем относительное значение



откуда, с учетом предыдущих формул, получим



Сведем в таблицу решения вышеприведенного уравнения для различных целочисленных оснований систем счисления.
Таблица 1.1

Основание

2

3

4

5

10



1,062

1,005

1,062

1,143

1,598


Из табл. 1.1 следует, что в цифровых вычислительных устройствах наиболее выгодно применять систему счисления с основанием . Однако для хранения произвольной троичной цифры требуется элемент с тремя устойчивыми состояниями, уступающий в плане помехоустойчивости и простоты физической реализации элементу с двумя устойчивыми состояниями.

Рассмотрим еще один критерий оценки систем счисления с разными основаниями – по быстродействию выполнения арифметических операций. В качестве характеристики быстродействия выберем количество элементарных сложений, выполняемых при умножении n-разрядных p-ичных чисел.

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



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


Таблица 1.2

Основание

2

3

4

5

10



1,000

1,262

1,500

1,725

2,709


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


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

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

При использовании формы представления чисел с фиксированной запятой определяется место фиксации запятой после старшего разряда в разрядной сетке ЭВМ или перед младшим разрядом. Поскольку для любого числа положение запятой строго фиксировано, специальный разряд для нее не отводится. Если запятая фиксирована после старшего разряда, то вычислительное устройство оперирует с дробями, а если перед младшим – то устройство оперирует с целыми числами. В дальнейшем будем полагать, что запятая фиксирована после старшего разряда, если обратное специально не оговорено. При этом числа должны быть представлены в виде правильных дробей, для чего используются специальные масштабные коэффициенты. Следует учитывать, что при такой форме представления возможны потери старших значащих цифр числа вследствие переполнения разрядной сетки, т.е. в том случае, когда результат выполнения арифметической операции является неправильной дробью (по модулю больше 1). Это обстоятельство накладывает ряд ограничений на используемые при вычислениях числа: во-первых, модуль суммы двух чисел не должен превышать единицу; во-вторых, модуль делимого должен быть меньше модуля делителя.

На рис. 1.1 изображено машинное представление n-разрядного числа с фиксированной после знакового разряда запятой.

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

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



а диапазон представления чисел в машине с фиксированной запятой равен



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



где a – правильная дробь, удовлетворяющая условию , называемая мантиссой числа; p – основание системы счисления; m – целое положительное или отрицательное число, называемое порядком числа, указывающее местоположение запятой в числе.

На рис. 1.2 изображено машинное представление числа с плавающей запятой.



Максимальное по абсолютной величине число, которое может быть представлено в машине с плавающей запятой, определяется как

,

однако, учитывая, что при больших n величина мала, ею можно пренебречь.

Таким образом, величины двоичных чисел, представляемых в машинах с плавающей запятой, лежат в пределах



а диапазон представления чисел в машине с плавающей запятой равен



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

Различают прямой код числа и инверсные коды, к которым относятся обратный и дополнительный коды.

Прямым кодом двоичного числа называется его изображение в естественной записи, причем в знаковом разряде отрицательного числа записывается единица, а положительного числа – ноль. Таким образом, прямой код двоичной правильной дроби определяется выражением



На рис. 1.3 представлена геометрическая интерпретация области чисел и области их изображений в прямом коде.

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

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

0,000…0;

1,000…0.

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

Дополнительный код двоичной правильной дроби определяется выражением



а дополнительный код целого двоичного n-разрядного числа – выраже­нием



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

Число ноль в дополнительном коде имеет только одно изображение:

0,000…0.

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



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

00,000…0.

На рис. 1.4 представлена геометрическая интерпретация области чисел и области их изображений в модифицированном дополнительном коде.


Различают также еще один инверсный код, называемый обратным кодом и определяемый для n-разрядных двоичных правильных дробей выражением



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

Ноль в обратном коде имеет два значения:

0,000…0;

1,111…1.

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

Модифицированный обратный код n-разрядной двоичной правильной дроби определяется выражением



Ноль в модифицированном обратном коде записывается двумя способами:

00,000…0;

11,111…1.
1.5. Двоично-десятичные коды чисел

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

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

,

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

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

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

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

Упорядоченность двоично-десятичных кодов определяется выполнением одного из условий:

,

,

где – двоично-десятичный код i-й десятичной цифры.

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

Свойство самодополняемости кратко рассмотрено в разделе 1.1 и заключается в том, что сумма двоичного кода любой десятичной цифры и ее обратного двоично-десятичного кода должна быть равна двоично-десятичному коду цифры 9.

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

,

где – двоичные цифры кода; – некоторые веса, соответствующие разрядам двоичных кодовых комбинаций.

В табл. 1.3 представлены некоторые двоично-десятичные коды () десятичных цифр.
Таблица 1.3

Десятичные цифры

Коды

8421

8421+3

8421+6

2421

3321

0

0000

0011

0110

0000

0000

1

0001

0100

0111

0001

0111

2

0010

0101

1000

1000

0010

0010

3

0011

0110

1001

1001

0011

1000

0100

0011

4

0100

0111

1010

1010

0100

1001

0101

5

0101

1000

1011

0101

1011

1010

0110

6

0110

1001

1100

0110

1100

1100

1011

0111

7

0111

1010

1101

0111

1101

1101

8

1000

1011

1110

1110

1110

9

1001

1100

1111

1111

1111


Код 8421 по сути является простейшим D-кодом с естественным порядком весов, т.е. в двоичной тетраде старший разряд имеет наибольший вес – 8 (), а младший разряд – наименьший вес – 1 (). Этот код обладает свойствами аддитивности, упорядоченности, четности и взвешенности, однако, как указывалось выше, не обладает свойством самодополняемости. Для получения обратного кода необходимо увеличить значения, записанные в каждой тетраде числа на 6, т.е. преобразовать код 8421 в код 8421 с избытком 6 (8421+6), а затем инвертировать двоичные разряды.

Код 8421 с потетрадным избытком 3 (8421+3) обладает свойством самодополняемости, поэтому для получения обратного кода отрицательного числа достаточно просто инвертировать двоичные разряды в тет­радах.

Коды 2421 и 3321 являются кодами с искусственным порядком весов. В таких кодах некоторые десятичные цифры могут быть представлены несколькими кодовыми комбинациями. Для выполнения условия единственности некоторые разрешенные кодовые комбинации считают запрещенными.

Подробнее об арифметике двоично-десятичных кодов см. в разде­- ле 2.7.
Вопросы для самоконтроля

  1. Что такое позиционные системы счисления и в чем их отличие от непозиционных? Какие позиционные системы счисления вам известны?

  2. Какие способы представления чисел в ЦВМ вам известны? В чем заключаются особенности представления чисел с фиксированной запятой?

  3. В чем заключаются особенности представления чисел с плавающей запятой?

  4. Какие инверсные коды чисел вам известны? Как они образуются и в чем их отличие от прямого кода?

  5. Что такое двоично-десятичные коды чисел? Какие двоично-десятичные коды получили наибольшее распространение в цифровой вычислительной технике? Какими свойствами они характеризуются?

  1   2   3   4   5   6   7   8   9   10   11


Учебный материал
© nashaucheba.ru
При копировании укажите ссылку.
обратиться к администрации