Базисные элементы

На рис. 2.22 показан пример контроля логического преобразователя ЛП, воспроизводящего систему переключательных функций от m переменных. Для осуществления контроля к системе добавляется еще одна функция Fдоп = Fi F2 ... Fn, которая воспроизводится на индивидуальных элемен­тах (во избежание маскирования контролируемых ошибок). Затем вырабо­танные функции F₁.-Fn свертываются по модулю 2, и результат сравнивает­ся с дополнительной функцией Fдоп. Ясно, что при отсутствии ошибок должны сравниваться одинаковые величины. Если они различны, то на вы­ходе элемента сложения по модулю 2 возникнет сигнал ошибки.

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

Рис. 2.22. Схема контроля логического преобразователя по модулю 2

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

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

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

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

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

Первый контрольный разряд входит в группу разрядов с номерами XX...XXI, где Х означает произвольное значение. Иными словами в первую группу входят разряды с нечетными номерами: 1, 3, 5, 7, 9,... .

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

Третий контрольный разряд входит в группу, у которой номера разрядов имеют единицу в третьем справа разряде: ХХ...1ХХ, т. е. с номерами 4, 5, 6, 7, 12, 13, 14, 15,... . '

Таблица 2.10

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

Пример составления кода Хемминга для четырехразрядного информацион­ного слова приведен в табл. 2.10.

Через р в таблице обозначен общий контрольный разряд для всей кодовой комбинации, через p₁, р₂, р₃ — первый, второй и третий групповые кон­трольные разряды.

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

Рассмотрим теперь процесс исправления и выявления ошибок. Пусть, на­пример, передавалось информационное слово 0110 = 6₁₀. Не учитывая пока разряд р, получим, что правильная кодовая комбинация имеет вид:

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

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

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

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

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

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

Таблица 2.11

Схемы кодера и декодера для кода Хемминга

На рис. 2.23 показана схема кодирования и декодирования для кодов Хем­минга. Верхняя часть, схемы показывает выработку контрольных разрядов для составления кода Хемминга. Нижняя часть содержит три четырехраз­рядных схемы свертки для проведения групповых проверок (разрядов син­дрома). Синдром поступает на дешифратор, который вырабатывает единич­ный сигнал на линии, соответствующей номеру ошибочного разряда. Эта единица выполняет инвертирование ошибочного разряда слова А, поступая на второй вход элемента сложения по модулю 2, через который данный раз­ряд передается на выход схемы. Таким образом, нижняя часть схемы пред­ставляет собою декодирующее устройство для кода Хемминга.

Двойная ошибка обнаруживается элементом 2k согласно логике ситуаций, указанной выше.

Кодирование-декодирование для 16-разрядных слов с формированием 6 контрольных разрядов модифицированного кода Хемминга реализуется микросхемой ВЖ1 серий К555, 533. Время кодирования-декодирования со­ставляет для этой ИС 50...60 не.

Код Хемминга относится к числу простых. Есть много более сложных кодов с большими корректирующими возможностями (БЧХ, код Файра, код Рида-Соломона и др.).

Рис. 2.23. Схема кодирования и декодирования для кодов Хемминга

Базисные элементы

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

Базис "И-НЕ"

И-НЕ - это схема И и схема НЕ, сложенные вместе. Операция, которую производит такой элемент называется инверсией логического умножения или отрицанием логического умножения, ну или инверсией конъюнкции и еще красивым словосочетанием штрих Шеффера. Штрих кого-то там называется потому, что в виде формулы опреция И-НЕ записывается так: y = x₁ | x₂. Вертикальная черта между иксами и есть штрих какого-то Шеффера.

Логический элемент И-НЕ обозначается так:

Таблица истинности для него:

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