Основы прикладной теории цифровых автоматов

Основы прикладной теории цифровых автоматов

 

(учебное пособие)

 

 

Тбилиси

 

 

РЕФЕРАТ

 

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

 

В.В. Коштоев, К.К. Кипиани

 

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

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

- принципы организации арифметических действий с двоичными и двоично-десятичными числами и организации контроля работы цифрового автомата;

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

- методы анализа и синтеза логических электронных схем.

Кратко описываются основы теории автоматов, приводятся методы струк-турного синтеза цифровых автоматов.

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

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

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

 

Объем книги: 155 стр.

ОГЛАВЛЕНИЕ

 

Предисловие 3

 

Г л а в а 1. Информационные основы цифровых автоматов 4

 

1.1. Информация и общие принципы ее преобразования 4

1.2. Обмен информацией между различными информационными

устройствами 7

1.3. Аппаратные средства хранения и обработки информации 8

1.4. Общие понятия о цифровом автомате и алгоритме 9

 

Г л а в а 2. Представление числовой информации в цифровом автомате 12

2.1. Системы счисления и понятие кода 12

2.2. Выбор системы счисления 15

2.3. Формальные правила двоичной арифметики 15

2.4. Перевод числовой информации из одной позиционной

системы счисления в другую 18

 

Г л а в а 3. Формы представления чисел в цифровых автоматах 20

3.1. Форма представления чисел с фиксированной запятой 21

3.2. Представление отрицательных чисел в формате

с фиксированной запятой 22

3.3. Форма представления чисел с плавающей запятой 24

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

в формат с плавающей запятой и обратно 27

3.5. Погрешности представления чисел 29

 

Г л а в а 4. Арифметические действия с двоичными числами 32

4.1. Сложение двоичных чисел 32

4.1.1. Алгебраическое сложение чисел, представленных в форме

с фиксированной запятой 32

4.1.2. Переполнение разрядной сетки 34

4.1.3. Модифицированный прямой, обратный и дополнительный код 34

4.1.4. Алгебраическое сложение чисел, представленных в форме

с плавающей запятой 35

4.2. Умножение двоичных чисел 36

4.2.1. Методы умножения двоичных чисел 36

4.2.2. Умножение чисел, представленных в форме

с фиксированной запятой 37

4.2.3. Умножение чисел, представленных в форме с плавающей запятой 37

4.2.4. Ускорение операции умножения 38

4.3. Деление двоичных чисел 39

4.3.1. Деление чисел, представленных в форме с фиксированной запятой 39

4.3.2. Деление чисел, представленных в форме с плавающей запятой 42

4.4. Оценка точности выполнения арифметических операций 43

4.4.1. Погрешность округления 44

 

Г л а в а 5. Выполнение операций над десятичными числами 46

5.1. Представление десятичных чисел в Д-кодах 46

5.2. Формальные правила поразрядного сложения в Д-кодах 46

5.3. Представление отрицательных чисел в Д-кодах 47

5.4. Выполнение операций сложения и вычитания чисел в Д-кодах 48

5.5. Умножение чисел в Д-кодах 48

5.6. Деление чисел в Д-кодах 49

5.7. Перевод чисел из Д-кода в двоичный и из двоичного в Д-код 50

 

Г л а в а 6. Контроль работы цифрового автомата 51

6.1. Основные понятия теории кодирования 51

6.2. Кодирование по методу четности-нечетности 51

6.3. Коды Хеминга 52

6.4. Контроль по модулю 53

6.5. Контроль арифметических операций 54

 

Г л а в а 7. Основы алгебры логики 55

7.1. Основные понятия алгебры логики 55

7.2. Свойства элементарных функций алгебры логики 59

7.3. Аналитическое представление функций алгебры логики 61

7.4. Совершенные нормальные формы 64

7.5. Системы функций алгебры логики 66

7.6. Числовое и геометрическое представление логических функций 69

 

Г л а в а 8. Упрощение и минимизация логических функций 71

8.1. Задача минимизации 71

8.2. Метод Квайна и импликантные матрицы 75

8.3. Метод Карно (диаграммы Вейча) 78

 

Г л а в а 9. Методы анализа и синтеза логических электронных схем 85

9.1. Логические операторы электронных схем или цепей 85

9.1.1. Задачи анализа и синтеза электронных схем 87

9.2. Синтез логических схем с одним выходом 88

9.3. Электронные схемы с несколькими выходами 94

9.4. Временные булевы функции и последовательностные автоматы 95

 

Г л а в а 10. Введение в теорию автоматов и структурный синтез

цифровых автоматов 98

10.1 Основные понятия и определения 98

10.2. Методы структурного синтеза и языки описания цифровых автоматов 102

10.3. Элементарный автомат (триггерный элемент) 104

10.4. Синтез цифрового автомата с памятью 195

 

Г л а в а 11. Алгоритмы рализации арифметических действий

в цифровых автоматах 110

 

Приложение Определения основных понятий и терминов 145

 

Литература 153

 

 

ПРЕДИСЛОВИЕ

 

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

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

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

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

 

 

Глава 1.

 

Обмен информацией между различными информационными

Устройствами

 

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

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

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

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

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

Все перечисленные средства стандартного интерфейса (СИ) должны обеспечить строгое выполнение протокола специфического для данного СИ.

На практике использу.т различные стандартные интерфейсы, например: SCSI, RS-232, CAMAC, VME, MULTIBUS, FASTBUS и т.д.

 

Выбор системы счисления

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

Если имеется n разрядов для изображения числа в q -ичной системе счисления, то тогда максимальное число М, которое можно изобразить в пределах данной разрядной сетки, будет равно:

 

M = q n - 1 q n

 

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

 

N = qn

 

Из приведенных равенств следует, что N = q lnM / ln q. Используя полученную зависимость, можно найти основание системы счисления, при которой требуется минимум оборудования. Определив dN/d q и приравняв ее к нулю, получим экстремум при q = e. Но е не целое число, поэтому нужно использовать системы с q = 2 или q = 3. Эти системы практически равноценны, т.к.

 

N2/ N3 = 2ln3 / 3ln2 1.056

 

Подобное сравнение десятичной и двоичной систем счисления показывает, что десятичная в 1.5 раз менее экономична двоичной.

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

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

 

Другую

 

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

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

Например

 

(3 0 5. 4)8 = 11000101.100(2);

011 000 101. 100

 

(7 B 2. E)16 = 11110110010.1110(2).

0111 1011 0010. 1110

 

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

Например:

1) перевод 1101111001.11012 в восьмеричное

 

001101111001. 110100 = 1571.648;

1 5 7 1 6 4

 

2) перевод 11111111011.100111(2) в шестнадцатеричное

 

011111111011. 10011100 = 7FB.9C(16).

7 F B 9 C

 

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

Например,

0001 1001 1000 0100(D) = 1984(10)

 

0001100110000100

1 9 8 4

 

Для реализации машинных алгоритмов перевода из одной системы счисления в другую существуют различные методы. Так, например, для перевода целого десятичного числа в его двоичный (восьмеричный, шестнадцатеричный) эквивалент используется деление на 2 (8, 16), т.е. выполняется деление на основание новой системы счисления. В процессе такого деления последовательно, начиная с младшего разря-да 2-го (8-го, 16-го) эквивалента, записывается остаток, если он получается на очередном этапе деления десятичного числа. В противном случае записывается ноль. Далее результат очередного деления опять делится на 2 (8, 16), если этот результат больше или равен 2 (8, 16). Если же результат меньше, то он прямо переписывается в старший разряд:

 

1) 53:2 = 26:2 = 13:2 = 6:2 = 3:2 = 1

(мл. раз.) 1 0 1 0 1 1 (ст. раз.)

n\t\ 53(10) = 110101(2).

 

2) 128:8 = 16:8 = 2

0 0 2

12810 = 2008

 

3) 128:16 = 8

0 8

12810 = 8016

 

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

Процедуру преобразования десятичной дроби в двоичную рассмотрим на примере преобразования числа 0,375.

1. Преобразование осуществляется умножением дроби на основание системы счисления, в которой дробь должна быть представлена. В данном случае умножаем на 2: 0,375 х 2 = 0.75. Окончательный результат формируется поразрядно, начиная со старшего разряда, к примеру, в некотором трехразрядном регистре С = 0.XXX, где XXX - разрядная сетка мантиссы этого регистра.

2. Если результат <1, то старшему значащему разряду присваивается значение 0; если больше 1, то присваивается 1. Поскольку 0,75<1, то в старший разряд регистра С записывается 0, т.е. С = 0,0XX.

3. Результат предыдущей операции умножения снова умножаем на 2. Заметим, что если бы результат предыдущей операции умножения был больше 1, то в данной операции умножения участвовала лишь его дробная часть. В данном случае 0,75 x 2 = 1,5.

4. Так как результат больше 1, то следующему значащему разряду регистра С присваивается значение 1, т.е. С = 0,01X.

5. Шаги описанной процедуры повторяются до тех пор, пока либо результат умножения не будет точно равен 1, либо не будет достигнута требуемая точность. В нашем примере после выполнения очередного шага результат равен 0,5 x 2 = 1,0. Поэтому очередному значащему разряду регистра С присваивается 1, т.е. окончательно получена двоичная дробь С = 0.0112.

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

 

Расмотрим еще пример: переведем число 0,3437510 в двоичное

2 x 0,34375 = 0,6875 0 (старший разряд - СЗР, результата перевода)

2 x 0,6875 = 1,375 1

2 x 0,375 = 0,75 0

2 x 0,75 = 1,5 1

2 x 0,5 = 1,0 1

2 x 0 = 0 0 (младший разряд - МЗР, результата перевода)

Ответ: 0,01011(2)

 

Для перевода десятичной правильной дроби в восмеричную (шест-надцатеричную) надо умножать ее на 8 (16). Если очередное произведение правильная дробь, то, начиная со старшего разряда результата записываются 0. Если произведение целое и меньше 8 (16), то оно прямо переписывается в соответствующий разряд результата.

Например:

1) 0,0625 x 8 = 0,5 0

0,5 x 8 = 4 4

0,062510 = 0,048

 

2) 0,875 x 16 = 14(E)

0,87510 = 0,E16

 

Перевод двоичного числа в десятичный его эквивалент можно выполнить при помощи формулы (2.1):

 

1) 110101(2) = 125+ 124 + 023 + 122 + 021 + 120 =

132 + 116 + 08 + 14 + 02 + 11 = 32 + 16 + 4 + 1 = 53(10).

2) 2008 = 282+ 081 + 080 = 12810

3) 1F16 = 1161+ 15160 = 3110

 

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

 

Глава 3.

 

Фиксированной запятой

 

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

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

А - В = А + (- В)

 

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

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

 

[A]пр= 0.an an-1 an-2.....a1 a0,

 

тогда число -А в этом же коде представляется как

 

[-A]пр = 1.an an-1 an-2.....a1 a0,

 

а в обратном (инверсном) коде это число будет иметь вид:

 

[-A]об = 1.an an-1 an-2.....a1 a0,

 

где

ai = 1, если ai = 0,

ai = 0, если ai = 1,

 

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

Тогда число -A в дополнительном коде изображается в виде

 

[-A]доп = [-A]об + 1

 

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

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

Представим, что мы имеем только два разряда для представления чисел в десятичной системе счисления. Тогда максимальное число, которое можно изобразить будет 99, а вес третьего несуществующего старшего разряда будет 102, т.е. 100. В таком случае для числа 20 дополнительным будет число 80, которое дополняет 20 до 100 (100 - 20 = 80). Следовательно по определению вычитание

50 - 20 = 30

можно заменить на сложение:

50 + 80 = 1 30

Здесь старшая единица выходит за пределы выделенной разрядной сетки, в которой остается только число 30, т.е. результат вычитания из 50 числа 20.

А теперь рассмотрим похожий пример для чисел, представленных 4-х разрядным двоичным кодом. Найдем дополнительное число для 00102= 210. Надо из [1]0000 вычесть [0]0010, получим [0]1110, которое и является дополнительным кодом 2. Разряд, изображенный в квадратных скобках на самом деле не существует. Но так как у нас 4-х разрядная сетка, то выполнить такое вычитание в принципе невозможно, а тем более мы стараемся избавиться от вычитания. Поэтому дополнительный код числа получают способом, описанным ранее, т.е. сначала получают обратный код числа, а затем прибавляют к нему 1. Проделав все это с нашим числом (2), нетрудно убедиться, что получится аналогичный ответ.

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

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

Рассмотрим простые примеры.

Семерка в прямом коде представляется так:

 

[7]пр = 0.0001112

 

Число -7 в прямом коде:

 

[-7]пр = 1.0001112,

 

а в обратном коде будет иметь вид

 

[-7]об = 1.1110002,

 

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

 

[-7]доп = 1.1110012.

 

Рассмотрим еще раз как процедура вычитания, при помощи представления вычитаемого в дополнительном коде, сводится к процедуре сложения. Вычтем из 10 число 7: 10 - 7 = 3. Если оба операнда представлены в прямом коде, то процедура вычитания выполняется так:

 

 

0.001010

-1.000111

0.000011 = 310

 

А если вычитаемое, т.е. -7, представить в дополнительном коде, то процедура вычитания сводится к процедуре сложения:

 

0.001010

+ 1.111001

1 0.000011 = 310.

 

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

 

Сложение двоичных чисел

 

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

 

Умножение двоичных чисел

 

Деление двоичных чисел

Погрешность округления

 

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

 

Aq= [m] q n+ [A0] q p-n,

 

где [A0] q p-n= A0- "хвост" числа, не попавший в разрядную сетку.

В зависимости от того, как учитывается величина А0 в машинном изображении, существует несколько способов округления.

1. Отбрасывание А0. При этом относительная погрешность равна

 

окр = .

 

Так как q-1 |m| < 1; то 0 |A0| < 1, поэтому

 

окр = = q-(n-1),

 

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

2. Симметричное округление. При этом производится анализ величины А0. Принимая, что

 

\

 

При условии |A0| q -1производится прибавление единицы к младшему разряду мантиссы. Абсолютная погрешность при этом

 

 

Максимально возможное значение модуля абсолютной погрешности равно 0,5 q p-n, а относительная погрешность равна

 

окр0,5 q p-n/(m q p) = 0,5 q -(n-1),

 

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

3. Округление по дополнению. В этом случае для округления берется информация, содержащаяся в (n +1)-м разряде. При q = 2, если в (n +1)-м разряде содержится 1, в n -й разряд добавляется 1; если же там ноль, содержимое разрядов правее n -го отбрасывается.

 

Глава 5.

 

Умножение чисел в Д-кодах

 

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

Рассмотрим пример умножения двух чисел, представленных в коде Д1:

умножим X = 2510 = 0010 0101 на Y = 1210 = 0001 0010, частные произведения формируем в P. Анализ тетрад Y начинаем с младшей.

 

0010 0101 x 0001 0010 = 0011 0000 0000 = 30010

P 0000 0000 0000

+ X 0010 0101 0010 - 0001 = 0001 > 0, значит надо еще раз X + P

P 0000 0010 0101

+ X 0010 0101 0010 - 0001 = 0, конец анализа младшей тетрады.

P 0000 0100 1010

+ 0110 поправка

P 0000 0101 0000 сдвигаем X на 4 разряда влево и складываем с P, анализируя старшую тетраду Y.

 

P 0000 0101 0000

+ X 0010 0101 0000 0001 - 0001 = 0

P 0010 1010 0000

+ 0110 поправка

P 0011 0000 00002 = 30010 ответ.

 

Деление чисел в Д-кодах

 

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

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

Рассмотрим пример деления двух чисел, представленных в коде Д1:

X = 48 = 0100 1000, Y = 2 = 0000 0010, X:Y = 24 = 0010 0100, в С1 - формируем старшую тетраду частного, а в С2 - младшую.

0100 1000: 0010

- 0010

0010 > 0 С1 = С1 + 1 = 1

- 0010

0000 С1 = 1 + 1 = 2 = 0010

-0010

+ 0010

0000 сдвигаем Y на 4 разряда (1 тетраду) вправо и выполняем те же действия:

0100 1000

- 0010

0110 >0 С2 = С2 + 1 = 1

- 0010

0100 > 0 С2 = 1 + 1 = 2

- 0010

0010 > 0 С2 = 2 + 1 = 3

- 0010

0000 С2 = 3 + 1 = 4 = 0100

 

Ответ С1 + С2 = 0010 0000 + 0000 0100 = 0010 0100 = 2410

 

Основные понятия теории кодирования

 

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

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

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

 

Коды Хеминга

 

Коды, предложенные американским ученым Р.Хемингом, позволяют не только обнаружить но и исправить одиночные ошибки. Эти коды - систематические. Хеминг впервые ввел понятие кодового расстояния.

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

Минимальным кодовым расстоянием (dmin) данного кода называется минимальное расстояние между двумя любыми словами в этом коде. Если длина слова n, то кодовое расстояние может принимать значение от 1 до n. Если имеется хоть одна пара слов, отличающихся в одном разряде, то минимальное кодовое расстояние равно 1. Для систематических кодов

d min > 1. В общем случае, чтобы код позволял обнаруживать ошибки кратностью r, должно выполняться условие:

 

d min r + 1.

 

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

 

n +1 = n 0 + k + 1 2k отсюда n 0 2k- k - 1.

 

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

Информационные и контрольные разряды необходимо размещать на определенных местах для нахождения ошибок. Обычно контрольные разряды принято размещать на позициях кода 20, 21, 22,... (1, 2, 4, 8, 16...), у которых в записи есть только одна 1 (для удобства). При этом нумерация позиций идет слева направо. А нумерация позиций для записи информационных разрядов идет справа налево. Рассмотрим пример перевода двоичного кода числа в код Хеминга. Пусть надо передать информацию, для которой выделено 3 контрольных разряда, т.е. k = 3, тогда n 0= 4, т.е. для представления числа нам отводится 4 разряда. В итоге передается 7-разрядный код. Через И обозначим информационные разряды, а через К - контрольные.

 

1 2 3 4 5 6 7

К1 К2 И4 К3 И3 И2 И1

0 0 0 0 1 1 0

 

т.е. передается 01102 = 610. Для проверки на четность складываем позиции 1, 3, 5, 7 (отсчет идет слева направо), т.е. порядковые номера которых имеют 1 в младшем разряде (в двоичном представлении). Получаем: 0 + 0 + 1 + 0 = 1, сумма равна 1, значит в К1 записываем 1 (для четности). Далее аналогично складываем позиции 2, 3, 6, 7 (порядковые номера содержат 1 во втором разряде), получаем: 0 + 0 + 1 + 0 = 1, значит в К2 записываем тоже 1. И наконец складываем позиции 4, 5, 6, 7 (порядковые номера содержат 1 в третьем разряде), получаем: 0 + 1 + 1 + 0 = 0, в К3 записывается 0. Таким образом мы получили следующий код:

 

1 2 3 4 5 6 7

К1 К2 И4 К3 И3 И2 И1

1 1 0 0 1 1 0

 

Это и есть 6 в коде Хеминга. Надо отметить, что общее количество 1 в коде должно быть четным.

Теперь рассмотрим пример корректировки полученного кодированного в коде Хеминга числа, в котором есть сбой: число 0111000. Надо определить позицию, в которой произошел сбой. Для этого суммируем позиции 1, 3, 5, 7, получаем: К1 = 0 + 1 + 0 + 0 = 1. Далее суммируем позиции 2, 3, 6, 7, получаем: К2 = 1 + 1 + 0 + 0 = 0. И наконец суммируем позиции 4, 5, 6, 7, получим К3 = 1 + 0 + 0 + 0 = 1. Контрольный код равен 1012 = 510, значит ошибка на 5-й позиции кода, т.е 01111002 = 1210.

Существует модифицированный код Хеминга, в котором добавляется еще один разряд общей четности. Такой код позволяет обнаруживать и устранять двойные ошибки. Например, записываем число 1011010, а считываем со сбоем: 1 1 110 0 0. Надо проинвертировать считанное число, послать его и снова считать (опять с таким же сбоем): А = 1 1 110 0 0 = А = 0000111, посылаем и читаем В = 0 1 001 0 1, складываем А и В, получаем: С = 0 1 000 1 0, в котором единицы показывают в каких разрядах произошел сбой.

 

Контроль по модулю

 

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

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

Например: определить контрольный код чисел А = 125 и В = 89 по модулю 11. 1) 125: 11 = 12 (4), т.е. контрольный код равен 4. 2) 89: 11 = 8 (1), т.е. контрольный код равен 1.

При цифровом методе контроля контрольный код числа образуется делением суммы цифр числа на выбранный модуль. В данном варианте возможны два пути получения контрольного кода: 1) непосредственное деление суммы цифр на модуль; 2) просто суммирование цифр по выбранному модулю.

Например: определить контрольный код для чисел 153 и 41 по модулю 3. Сумма цифр 153 равна 9, а сумма цифр 41 равна 5. Разделив эти суммы на 3 получим соответственно контрольные коды 0 и 2.

 

ОСНОВЫ АЛГЕБРЫ ЛОГИКИ

 

Основные понятия алгебры логики

 

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

Функция f(x1, x2,..., xn) называется логической (пере