9.5. Булева производная

Производная первого порядка от булевой функции f по переменной x_i определяется следующим образом [9]:

=f(х₁,х₂,...,х_i-1,1,x_i+1,...,x_n)Åf(x₁,x₂,...,x_i-1,0,x_i+1,...,x_n),

где f(х₁,х₂,...,х_i-1,1,x_i+1,...,x_n) – единичная остаточная функция, получаемая в результате подстановки вместо х_i константы 1, а f(х₁,х₂,...,х_i-1,0,x_i+1,...,x_n) – нулевая остаточная функция, получаемая в результате подстановки вместо x_i константы 0.

Пример. f=х₁Úх₂.

Пример.

Пример.

Булева производная по x_i=0, если f не зависит от x_i, булева производная по x_i=1, если f зависит только от x_i.

Булева производная первого порядка определяет условия, при которых функция изменяет свое значение при изменении значения переменной x_i .

В нашем примере функция f(х₁х₂х₃) изменяет свое значение при изменении х₁, если истинна конъюнкция х₂х₃, т.е. х₂=1, х₃=1.

Пример. Определим все булевы производные функции

Итак, значение функции изменяется (функция переключается) при изменении х₁, если х₂=1 или х₃=0 ; при изменении х₂, если х₁=х₃=1 (х₁х₃=1); при изменении х₃, если х₁=1; х₂=0 .

Смешанная булева производная k-го порядка определяется путем вычисления k раз булевых производных первого порядка от булевых производных первого порядка, например [9]:

Булева производная k-го порядка равна сумме по модулю 2 всех производных первых, вторых, третьих, ..., k-х смешанных производных, и определяет условия, при которых функция изменяет значение при одновременном изменении соответствующих переменных, например:

Таким образом, f переключается при одновременном переключении х₁, х₂, когда х₃=0, либо независимо от х₃ при переключении х₁ и х₂ с 1,1 на 0,0 или с 0,0 на 1,1.

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

30 Элементарные автоматы памяти на основе комбинационного

автомата и задержки

Последовательностный автомат может быть синтезирован как композиция комбинационного автомата, реализующего функции переходов j и выходов y и элементарных автоматов памяти [10, 19], например, задержек на один такт (рис. 64).

Рис. 64. Задержка на один такт

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

Рассмотрим синтез элементарных автоматов памяти на основе задержек на один такт. Пусть требуется синтезировать автомат, выход которого устанавливается в состояние логической единицы при поступлении сигнала логической единицы на вход установки (обычно он обозначается S – «Set») и хранящий это состояние до поступления сигнала логической единицы на вход сброса (обычно он обозначается R – «Reset»). Таким образом, требуется создать автомат, имеющий два входа R и S и один выход, который обозначим z (рис. 65). Иногда добавляют и инверсный выход .

Рис. 65. Элементарный автомат памяти

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

,

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

В таком случае опишем функционирование автомата первичной таблицей переходов-выходов (табл. 55).

Таблица 55

Первичная таблица переходов-выходов

Итак, в исходном состоянии автомат находится в строке с номером 1, в клетке, соответствующей нулевому состоянию RS. При поступлении набора сигналов 01 (начинается установка) автомат начинает переходить в состояние 2 (возникает неустойчивый такт 2), затем происходит перемещение во вторую строку – в устойчивый такт 2, обведенный кружком, при этом на выходе возникает сигнал 1. При поступлении сигнала 10 в первой строке и сигналов 00, 01 во второй строке состояние автомата не меняется, состояние 11 считается невозможным.

Очевидно, что сокращение числа строк табл. 55 невозможно, иначе мы имели бы комбинационный автомат (у которого одно состояние – одна строка).

Приступим к кодированию состояний. Оно в данном случае тривиально: исходное состояние сопоставим с состоянием 0 (1 строка), другое состояние сопоставим с 1.

Получим таблицы переходов-выходов для автомата Мили (табл. 56) и автомата Мура (табл. 57).

Таблица 56

Таблица переходов-выходов элементарного автомата памяти Мили

Таблица 57

Таблица переходов-выходов элементарного автомата памяти Мура

Таким образом, для автомата Мура (табл. 57) z(t)=y(t).

Построим автомат Мура. Получим функции переходов y(t+1) и выходов z(t):

Минимизируя y(t+1) по карте Карно, какой и является табл. 57, получаем:

.

Реализуем эту функцию в виде переключательной схемы (рис. 66).

Рис. 66. Переключательные схемы элементарного автомата памяти Мура

На рис. 66 Y – хранитель состояния автомата (например, обмотка реле), обратная связь, указанная пунктиром реализует так называемую самоблокировку. Задержка на один такт осуществляется следующим образом: сначала срабатывает Y, затем замыкается его контакт y. Технически предполагается, что к моменту размыкания S, y уже замкнут.

Построим схему на функциональных элементах в базисе И-НЕ:

Таким образом, один элемент 2И-НЕ реализует функцию , второй – .

Соответствующая схема показана на рис. 67.

Рис. 67. Реализация элементарного автомата памяти

на функциональных элементах 2И-НЕ

Можно заметить, что выход второго элемента в цепи R при R=0 соответствует значению . Эту схему часто изображают в несколько другом виде, полагая, что задержка реализуется в линии связи (рис. 68).

Рис. 68. Элементарный автомат памяти RS триггер

Это известная схема так называемого RS триггера.

Его условное графическое обозначение приведено на рис. 69.

Рис. 69. Условное графическое обозначение RS триггера

Для описания работы элементарных автоматов памяти применяются таблицы возбуждения, указывающие условия перехода от текущего к последующему внутреннему состоянию. Такая таблица для RS триггера – табл. 58.

Таблица 58

Таблица возбуждения RS триггера

y(t)	y(t+1)
	0	1
0	0 ~	1 0
1	0 1	~ 0	S R

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

Рис. 70. Условное графическое обозначение

дистанционного переключателя

Задержка на один такт может быть реализована и так называемым D триггером, устанавливающимся в состояние, определяемое его входом D по специальному разрешающему сигналу – синхроимпульсу. Это уже синхронный автомат в отличие от рассмотренных выше асинхронных (рис. 71, табл. 59).

Рис. 71. Условное графическое обозначение синхронного D триггера

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

Таблица 59

Таблица возбуждения D триггера

y(t)	y(t+1)
	0	1
0	0	1
1	0	1	D(t)

D триггер без синхронизации – аналог обычного реле (рис. 72).

Рис. 72. Условное графическое обозначение реле

и временная диаграмма работы

Имеются и другие элементарные автоматы памяти, например, асинхронный RS триггер с инверсным управлением (нулями, а не единицами, рис. 73, табл. 60), синхронный JK триггер (рис. 74, табл. 61).

Рис. 73. Условное графическое обозначение

RS триггера с инверсным управлением

Таблица 60

Таблица возбуждения RS триггера с инверсным управлением

y(t)	y(t+1)
	0	1
0	1 ~	0 1
1	1 0	~ 1	S R

Рис. 74. Условное графическое обозначение синхронного JK триггера,

срабатывающего по заднему фронту импульса

Таблица 61

Таблица возбуждения синхронного JK триггера,

срабатывающего по заднему фронту импульса

y(t)	y(t+1)
	0	1
0	0 ~	1 ~
1	~ 1	~ 0	J K

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

31 Синтез автомата – распознавателя последовательности

Дано: кодовая последовательность 0-1-3-2 двоичного двухразрядного сигнала (в десятичном коде).

Получить ПФ, описывающие соответствующий конечный автомат-распознаватель последовательности (рис. 75).

Рис. 75. Распознаватель последовательности на входах а, b

Последовательность поступает на входы a,b конечного автомата (КА):

20	a	0	0	1	1
21	b	0	1	1	0

Это правильная последовательность изменения входов a,b в соответствии с заданием.

Возможны и неправильные последовательности из алфавита А={0,1,2,3}.

Ограничим возможные неправильные коды изменением только одного двоичного разряда.

Рассмотрим соответствующий квадрат соседних чисел (рис. 76, т.к. всего два входа).

Рис. 76. Иллюстрация изменения входов

Направление изменения входных кодов показано стрелками. Видно, что в начале из 00 (0) имеем переход в 01 (1). Это если последовательность правильная. А если не правильная?

Тогда возможен лишь один вариант (рис. 77).

Рис. 77. Иллюстрация возможного нарушения последовательности:

из 00(0) в 10(2)

На втором шаге правильно: 01 (1) в 11 (3), а неправильно (рис. 78)?

Рис. 78. Иллюстрация возможного нарушения последовательности:

из 01(1) в 00(0)

Т.е. возможен возврат, в 00.

Аналогично на третьем шаге неправильным будет переход (рис. 79) из 11 (3) в 01 (1).

Рис. 79. Иллюстрация возможного нарушения последовательности:

из 11(3) в 01(1)

Таким образом, можно построить граф возможных последовательностей (рис. 80).

Рис. 80. Граф последовательностей распознавателя 0-1-3-2

Таким образом, имеем всего 4 последовательности:

1. 0-1-3-2 (правильная);

2. 0-2 (неправильная);

3. 0-1-0 (неправильная);

4. 0-1-3-1 (неправильная).

Строим первичную таблицу переходов (ПТП) соответствующего конечного автомата – распознавателя последовательности 0-1-3-2 (табл. 62).

Таблица 62

Первичная таблица переходов-выходов распознавателя 0-1-3-2

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

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

Это удобно делать путем построения графа объединения строк. В таком графе число вершин равно числу строк ПТП. В нашем случае – 7. Ребром соединяются вершины, соответствующие двум строкам, которые можно слить в одну строку, т.е. в этих строках клетки не противоречат друг другу. Такими клетками будут:

1) пустые клетки и клетки с цифрами, и наоборот;

2) клетки с цифрой i и клетки с цифрой в кружке, и наоборот, т.е. соответствующие неустойчивый и устойчивый такты сливаются в один устойчивый такт.

Граф объединения строк показан на 81.

Рис. 81. Граф объединения строк

Теперь в графе объединения строк необходимо выделить минимальное количество максимальных полных подграфов. В нашем случае это подграфы 3,4,6,7; 1,5 и одна вершина 2.

Возможны другие варианты объединения. Но ни при одном варианте мы не получим две строки (это идеал – к нему надо стремиться).

Получим минимизированную таблицу переходов (табл. 63).

Таблица 63

Минимизированная таблица переходов

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

Кодирование может иметь вид:

I: 00

II: 01

III: 11

Т.е. необходимо два двоичных разряда, которые обозначим y₁y₂. Это не что иное, как текущее состояние автомата, которое принято обозначать у₂(t) y₁(t) или сокращенно у₂ y₁(t).

Теперь получим таблицу переходов-выходов (ТПВ, табл. 64), в которой указывается, как автомат переходит из текущего состояния (коды строки) в последующее (у₂y₁(t+1) – код в некоторой клетке) при различных комбинациях входов ab.

Таблица 64

Таблица переходов-выходов

Код клетки – это соединение (конкатенация) двоичного кода строки и столбца, представленные в виде десятичного числа. Очевидно, что кружки в МТП и ТПВ располагаются в одинаковых клетках. Если такт устойчивый, то в кружке ТПВ в числителе указывается номер соответствующей строки. Если такт неустойчивый – то указывается код той строки, в которую осуществляется переход. В знаменателе указываются выходные сигналы z₂z₁. Они берутся из первичной таблицы переходов-выходов. Так, если в клетке МТП находится цифра 5 (пятый такт), то из пятой строки ПТП берется код 10 (нарушение последовательности). Указываем это число в клетке 2 ТПВ ( ).

Теперь получаем все четыре ПФ, описывающие наш автомат в символической форме:

По этим ПФ можно построить схему автомата, предварительно проведя минимизацию. Получим структурную схему автомата (рис. 82).

Рис. 82. Структурная схема автомата-распознавателя

34 Представление чисел в ЭВМ в двоично-кодированном десятичном формате (BCD или десятичном).

В BCD-формате десятичные цифры хранятся в виде 4-битных двоичных эквивалентов. В упакованном BCD-формате цепочка десятичных цифр хранится в виде последовательности 4-битных групп, например: 9502 в виде 1001 0101 0000 0010.

В неупакованном BCD-формате каждая цифра хранится в младшей тетраде соответствующего байта.

Представление чисел в ЭВМ в формате с плавающей запятой.

Такой формат предусматривает представление числа в показательной форме.

Например, десятичное число 685,73₁₀. представляется в виде 0,68573×10³, здесь 0,68573 – мантисса, 10 – основание десятичной системы счисления, 3 – порядок.

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

Кодирование буквально пронизывает информационные технологии [36].

В теории кодирования рассматриваются:

• представление данных произвольной природы в памяти ЭВМ (мы рассмотрели представление чисел);

• обеспечение помехоустойчивости при передаче данных по каналам связи (кодирование по нечетности, по Хэммингу, с использованием циклических полиномов);

• защита данных от несанкционированного доступа (криптографическое кодирование);

• сжатие информации в базах данных.

35 Понятие о помехоустойчивом кодировании

Код – это совокупность символов в представлении информации. Каждому знаку соответствует определённая комбинация нулей и единиц (бинарное кодирование).

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

Равномерный код – если все его слова имеют одинаковое количество разрядов.

Существуют коды обнаруживающие ошибки и коды, обнаруживающие и исправляющие ошибки.

Как правило, при передаче информации используется избыточность – не все разряды используются для передачи информации, не все 2ⁿ (где n количество разрядов) комбинаций используются для её представления.

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

В теории кодирования используется понятие кодового расстояния (расстояние Хэмминга).

d – кодовое расстояние – это число разрядов, по которым отличаются две кодовые комбинации.

В этих двух четырехразрядных кодовых комбинациях d=2.

Рассмотрим двухразрядную информацию.

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

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

d_min ³ t +1,

где t – кратность ошибок, а d_min – минимальное кодовое расстояние.

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

Для исправления необходимо: d_min³2t+1 (рис. 83).

Рис. 83. Принцип исправления ошибок

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

Рис. 84. Возможные ошибки при передаче трехразрядной информации

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

Примеры кодов.

1. Код с проверкой четности.

x2	x2	k
0	0	1
0	1	0
1	0	0
1	1	1

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

В приемнике формируется контрольный разряд с помощью элемента сложения по модулю 2 (рис. 85).

Рис. 85. Передатчик и приемник информации с контролем по нечетности на основе элементов сложения по модулю 2 с инверсией

2. Коды с простым повторением – это коды, в которых повторяется кодовая комбинация.

3. Корреляционные коды.

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

0®01

1®10

4. Равновесные коды.

Характеризуются тем, что каждая комбинация содержит одинаковое количество нулей и единиц. Например, 2 из 5:

01100®0

11000®1

10100®2

10010®3

01010®4

00110®5

10001®6

01001®7

00101®8

00011®9

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

36

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

В кодовом слове всего m разрядов, где m=n+k, n – количество информационных разрядов, k – количество контрольных разрядов.

Используется контроль по нечетности, причем формируется несколько групп контроля по нечетности.

Пример. Передается четырехразрядная информация:

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

В нашем случае: n=4, k=3. Разместим передаваемую информацию в секторах диаграммы Эйлера для трех взаимно пересекающихся множеств А, В, С (рис. 86).

A: k₁=1

B: k₂=1

C: k₃=0

Рис. 86. Диаграмма Эйлера для кодирования по Хэммингу

четырехразрядной информации

Пусть произошла ошибка в разряде х₂ (рис. 87).

Рис. 87. Ошибка в разряде х₂

Искажение (ошибка) привела к изменению информации и нарушению нечетности в двух контрольных группах А и С. Именно это и укажет на номер искаженного разряда. Каждый сектор («кусочек») диаграммы Эйлера определяет один из разрядов n или k.

Для определения числа контрольного разряда необходимо использовать соотношение m£2^k–1, или n+k£2^k–1.

Далее строится матрица Хэмминга.

1 0 1 0 1 0 1

1 1 0 0 1 1 0

1 1 1 1 0 0 0

x₄ x₃ x₂ k₃ x₁ k₂ k₁

Если дано число информационных разрядов n, то необходимо определить число контрольных разрядов. Выбираются двоичные эквиваленты номеров всех m разрядов (справа налево, младшие разряды вверху). Столбцы с одной единицей отводятся под контрольные разряды. Выделяются три группы контрольных разрядов k₁, k₂, k₃.

В передатчике формируются контрольные разряды по нечётности k₁,k₂,k₃ путём суммирования по модулю 2 соответствующих разрядов.

Записываются уравнения Хэмминга:

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

Синдром ошибки – вектор .

Если искажение не произошло, то синдром нулевой. Если не нулевой он укажет на место ошибки. Если (101), то ошибка в 5-ом столбце, разряд х₂, поскольку этот разряд входит в две группы контроля по нечетности – первую и вторую – это области А и С диаграммы Эйлера (рис. 87).

Иногда реальную информацию передают в другом порядке: отдельно информационные, отдельно контрольные разряды. Представим информацию в матричном виде. Матрица Хэмминга обозначается Н. Информационную подматрицу обозначим Р, а контрольную – I:

Если – входной вектор, – полное кодовое слово, тогда кодирование заключается в следующих матричных операциях:

, где – конкатенация (сцепление) информации в определенном порядке следования разрядов.

На вектор воздействуют ошибки. Используем вектор ошибок :

,

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

.

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