Компараторы и схемы контроля

Лекция 4

4. Компараторы и схемы  контроля

4.1 Компараторы

 

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

Компараторы принимают значение 1, если соблюдается условие, указанное в индексе обозначения функции. Например, функция FA = B = 1, если А = В и принимает нулевое значение при А ≠ В.

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

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

Рисунок 4.1 – Условное обозначение компаратора с тремя выходами

Устройства сравнения на равенство строятся на основе поразрядных операций над одноименными разрядами обоих слов. Слова равны, если равны все одноименные их разряды, т. е. если в обоих нули или единицы. Признак равенства разрядов

.

Признак равенства слов

Схема компаратора на равенство в базисе И-НЕ показана на (рис.4.2).

Рисунок 4.2 – Схема компаратора на равенство

Построение компаратора на "больше" для одноразрядных слов (табл.4.1) требует реализации функции .

Таблица 4.1

a	b	FA>B
0	0	0
0	1	0
1	0	1
1	1	0

 

Для общего случая n-разрядных слов имеем

.

    

4.2 Схемы контроля

 

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

    

4.2.1 Мажоритарные элементы

 

Задача мажоритарного элемента - произвести "голосование" и передать на выход величину, соответствующую большинству из входных. Ясно, что мажоритарный элемент может иметь только нечетное число входов.

Функционирование мажоритарного элемента, на входы которого поступают величины F1, F2, и F3 и по результатам голосования вырабатывается выходная величина F, представлено в таблице 4.2.

Таблица 4.2

F1	F2	F3	F	a1	a0
0	0	0	0	0	0
0	0	1	0	1	1
0	1	0	0	1	0
0	1	1	1	0	1
1	0	0	0	0	1
1	0	1	1	1	0
1	1	0	1	1	1
1	1	1	1	0	0

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

Рисунок 4.4 – Схема голосования с мажоритарным элементом

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

 

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

 

Контроль правильности передач и хранения данных - важное условие нормальной работы ЦУ.

Кодовая комбинация - набор из символов принятого алфавита.

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

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

Минимальное кодовое расстояние dmin - минимальное кодовое расстояние для любой пары комбинаций, входящих в данный код.

Кратностью ошибки называют число ошибок в данном слове (число неверных разрядов).

Из теории кодирования известны условия обнаружения и исправления ошибок при использовании кодов:

где dmjn - минимальное кодовое расстояние кода; гобн и гиспр - кратность обнаруживаемых и исправляемых ошибок соответственно.

Вес кода - число единиц в данной комбинации.

Для двоичного кода минимальное кодовое расстояние dmjn = 1, поэтому он не обладает возможностями какого-либо контроля производимых над ним действий. Чтобы получить возможность обнаруживать хотя бы ошибки единичной кратности, нужно увеличить минимальное кодовое расстояние на 1. Это и сделано для кода контроля по модулю 2 (контроля по четности/нечетности).

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

                                                             dmin = 2.

При контроле по четности вес кодовых комбинаций делают четным, при контроле по нечетности - нечетным.

Контроль по модулю 2 реализуется с помощью схем свертки. Для практики типична многоярусная схема свертки пирамидального типа.

Примером ИС свертки по модулю 2 может служить микросхема ИП5 серии КР1533 (рис.4.5, а). Схема имеет 9 входов, что допускает свертку байта с девятым контрольным разрядом. Двумя выходами схемы являются Е (Even) и О (Odd). Если вес входной комбинации четный, то Е = 1 и О = 0, и наоборот, если вес нечетный.

Рисунок 4.6 – Микросхема ИКР1533ИП5

     Схемотехнически ИС КР1533ИП5 представляет собою пирамидальную структуру из трехвходовых элементов типа четность/нечетность (рис.4.6,б).

    Передача данных с контролем по модулю 2 показана на (рис.4.6). Входные данные обозначены через D, а на выходе из канала связи данные обозначены через D', поскольку вследствие ошибок они могут измениться.

Рисунок 4.6 –Применение ИП5 для контроля канала связи (памяти)

 

4.2.3 Контроль с использованием  кодов Хемминга

 

Применение кодов Хемминга позволяет исправлять единичные ошибки приемном конце. Для получения кодовой комбинации кода Хемминга к информационному слову добавляется несколько контрольных разрядов. C целью определения значений контрольных разрядов примем, что контрольные разряды занимают позиции с номерами 2i (i = 0, 1, 2,...), т.е. 1, 2, 4, …

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

Первый контрольный разряд (1-я позиция) входит в группу разрядов с номерами, соответствующие двоичному коду хх...хх1, где х – 0 или 1. Иными словами в первую группу входят разряды с нечетными номерами: 1, 3, 5, 7, ... .

Второй контрольный разряд (2-я позиция) входит в группу разрядов с номерами, имеющими единицу во втором справа разряде, т. е. номерами, соответствующие двоичному коду хх...х1х. Это номера 2, 3, 6, 7, ... .

Третий контрольный разряд (4-я позиция) входит в группу, у которой номера разрядов имеют единицу в третьем справа разряде, соответствующий двоичному коду хх...1хх, т. е. с номерами 4, 5, 6, 7, ... .

Контрольные разряды выводят веса своих групп на четность/нечетность. Далее для определенности примем, что ведется контроль по четности. Производится столько проверок по модулю 2, сколько контрольных разрядов в кодовой комбинации, т. е. проверяется сохранение четности весов групп. Если в кодовой комбинации произошла ошибка, то в одних проверках она скажется, а в других - нет. Это и позволяет определить разряд, в котором произошла ошибка. Для восстановления правильного значения слова теперь остается только проинвертировать ошибочный разряд.

Пример: составить код Хемминга для четырехразрядного информационного слова А = а3а2а1а0 = 0110 (табл. 4.3).

Таблица 4.3

8	7	6	5	4	3	2	1
р	а3	а2	а1	р3	а0	р2	р1
0 1 1 0 1 0	0 0 0 0 0 0	0 0 0 0 1 1	0 0 1 1 0 0	0 0 1 1 1 1	0 1 0 1 0 1	0 1 0 1 1 0	0 1 1 0 0 1
0	0	1	1	0	0	1	1
1 0 … 1	0 1 … 1	1 0 … 1	1 0 … 1	0 1 … 1	1 0 … 1	0 1 … 1	0 0 … 1

 

Через р в таблице обозначен общий контрольный разряд для всей кодовой комбинации, через p1, р2, р3 - первый, второй и третий групповые контрольные разряды.

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

7	6	5	4	3	2	1
0	1	1	0	0	1	1

    

Пусть во втором слева разряде (в 6-м разряде) произошла ошибка и принята комбинация:

 

7	6	5	4	3	2	1
0	0	1	0	0	1	1

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

Вторая проверка (по разрядам 2, 3, 6, 7) обнаруживает нарушение четности веса комбинации, ее результат отмечается единицей.

Третья проверка (по разрядам 4, 5, 6, 7) также обнаруживает нарушение четности, ее результат отмечается единицей.

Результаты проверок образуют слово, называемое синдромом. Синдром указывает номер разряда, в котором произошла ошибка. В этом примере результаты проверок дают слово 110 = 610. Проинвертировав разряд номер 6, возвращаемся к правильной кодовой комбинации - ошибка исправлена.

Минимальное кодовое расстояние обычного кода Хемминга равно dmin =3. Добавление p разряда проверки общей четности приводит к модифицированному коду Хемминга с dmin = 4 и, соответственно, добавляет возможность обнаружения двойной ошибки. Обнаружение двойной ошибки основано на сопоставлении наличия или отсутствия признаков ошибки в синдроме и общей четности. Если обозначить через S любое ненулевое значение синдрома, то возможные ситуации, используемые для обнаружения двойной ошибки, окажутся следующими (табл.4.4).