14.4. ЭЛЕМЕНТЫ ТЕОРИИ САМОПРОВЕРЯЕМЫХ ЦИФРОВЫХ АВТОМАТОВ

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

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

Определение. ДУ называется полностью самопроверяемым в классе неисправностей если выполняются условия самотестируемости и защищенности ДУ в классе неисправностей

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

Пример. Пусть — код выходов ДУ. Пусть в данный момент времени на выходах ДУ ожидается вектор 00, однако под воздействием неисправности, возникшей в схеме ДУ, вместо вектора 00 появляется вектор Это означает, что неисправность проявилась на выходах ДУ.

Определение. ДУ называется защищенным в классе неисправностей если каждо? проявление неисправности на выходах ДУ означает появление вектора выхоюв, не принадлежащего коду выходов ДУ.

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

Выполнение только условия защищенности ДУ означает, что если неисправность проявляется на выходах, то это проявление есть появление нерабочего вектора выходов ДУ, т. е. вектора, не принадлежащего коду выходов ДУ Однако выполнение условия защищенности ДУ не гарантирует, что каждая неисправность, возникшая в схеме ДУ, проявляется на выходах ДУ. Поэтому возможны ситуации, когда некоторые неисправности вообще никак не проявляются на выходах ДУ, т. е. не влияют на правильность его работы. Последнее может привести к накоплению некоторых неисправностей в схеме ДУ. Совокупность накопленных неисправностей уже может не принадлежать рассматриваемому классу неисправностей и может вызвать такое искажение информации на выходах ДУ, которое не будет соответствовать условию защищенности ДУ (например, искаженный вектор выходов ДУ также является рабочим вектором выходов, так как принадлежит коду выходов ДУ), т. е. неправильное функционирование ДУ не будет обнаружено. Именно поэтому необходимо также и решение задачи самотестируемости. При этом, однако, следует помнить, что самотестируемость не всегда обеспечивается автоматически. Это объясняется тем, что на входы некоторых элементов, находящихся в глубине схемы ДУ, поступают не все возможные входные комбинации. Например, для схемы, изображенной на рис. 14.7, отказ типа «константа 0» элемента ИЛИ по входу не тестируется, если на входы этой схемы в процессе работы поступают только наборы 00, 10 и 11. Рассмотренный

Рис. 14.7

Рис. 14.8

пример говорит о том, что любую схему следует тщательно анализировать на тестируемость.

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

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

Самопроверяемые дискретные устройства (СДУ) обычно строятся в совокупности с самопроверяемыми схемами встроенного контроля (ССВК), имеющими два выхода. Функции ССВК следующие! обнаружение неправильного функционирование СДУ; обнаружение неправильного функционирования ССВК. Входными наборами ССВК обычно являются двоичные векторы кода выходов СДУ, хотя не исключается возможность использования и некоторых внутренних точек схемы СДУ. Выходными наборами двухвыходовой ССВК при правильной работе СДУ и ССВК являются наборы а при неправильной работе — 00 либо 11. Сложность задачи обеспечения самотестируемости хорошо иллюстрируется как раз в применении к ССВК. Если для всего ДУ очень часто можно предполагать, что на его входы поступают векторы натурального двоичного кода, то для ССВК множество входных векторов всегда ограничено выбранным помехоустойчивым кодом выходов ДУ. Любая неисправность из класса для ССВК должна быть тестируема только этими векторами. Система, включающая в себя СДУ и ССВК, условно может быть изображена в соответствии о

рис. 14.8. При организации системы считается, что в начале работы СДУ исправно. Исправное СДУ позволяет обеспечить проверку правильности функционирования ССВК. Если же неисправность возникает в схеме СДУ, то она обнаруживается с помощью правильно работающей ССВК. При построении СДУ ориентируются, как правило, на обнаружение одиночных неисправностей, и случай возникновения неисправностей одновременно в СДУ и ССВК не рассматривается.

ССВК для кодов с проверкой на четность

Код с проверкой на четность является простейшим представителем линейных групповых кодов. Для его построения, как уже рассматривалось ранее, необходим один проверочный разряд. Любой вектор такого кода имеет четный вес в смысле Хэмминга, т. е. содержит четное число единиц. Для реализации ССВК все разряды кодового вектора произвольным образом разбиваются на два непересекающихся подмножества. Каждое подмножество объединяется с помощью одной схемы свертки по модулю 2. На выходе одной из схем свертки ставится инвертор. Полученная ССВК представлена на рис. 14.9. Нетрудно убедиться, что на любом векторе кода с проверкой на четность выходы принимают значения из множества а на любом векторе, не принадлежащем коду, — значения из множества Построенная схема встроенного контроля защищена от всех одиночных неисправностей логических элементов, составляющих схемы свертки по модулю 2, поскольку они имеют раздельную реализацию. Самотестируемость обеспечивается поступлением на входы СВК всех векторов кода с проверкой на четность. Иными словами, приведенная СВК является самопроверяемой. ССВК для кода с проверкой на нечетность строится аналогично, за исключением инвертора на выходе одной из схем свертки по модулю 2. В этом случае он не нужен,

Самопроверяемые схемы сжатия

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

где — выходы CCBK, — выходы ССВК, ССС позволяет обнаруживать

Рис. 14.9

Рис. 14.10

Рис. 14.11

Рис. 14.12

одиночную константную неисправность, возникающую в самой а также фиксировать ошибки, появляющиеся на выходах CCBK и ССВК Как показывают исследования, для обеспечения самотестируемости ССС достаточно на ее входы подать четыре набора; . В случае, если требуется объединить через самопроверяемые схемы сжатия выходы большего числа ССВК, поступают следующим образом. Первый способ основан на построении дерева, каждый узел которого есть ССС, реализующая систему уравнений описанного выше вида. На рис. 14.11 представлен случай объединения выходов четырех ССВК с помощью Функции описываются системами уравнений:

Второй способ объединения выходов ССВК показан на рис. 14.12. Функции описываются системами уравнений:

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

где — выходы устройства — выходы устройства В. Однако при этом обязательно выполнение соотношений Если устройства А и В имеют более двух выходов, то ССВК на основе ССС организуется в соответствии с уже описанными способами (см. рис. 14.11, 14,12). Приведенные для этих способов системы уравнений булевых функций остаются справедливыми, если между выходами устройства А и выходами устройства В установлены соотношения и т. д.

ССВК для равновесных кодов

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

ССВК для кодов к из можно построить, используя, например, следующие процедуры:

1. Множество всех разрядов кода разбивается на два подмножества: А и В (с равным числом элементов в каждом из них). Пример такого разбиения для кода 3 из 6 показан на рис. 14.13.

2. На подмножестве А вводится булева функция

Рис. 14.13

Рис. 14.14

Таблица 14.18 (см. скан)

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

3. Булевы функции каждая из которых описывается уравнением вида

объявляются выходами ССВК.

Для кода 3 из 6 имеем:

4. Функция реализуется схемой, представленной на рис. 14.14, где комбинационные схемы есть двухуровневые схемы типа элементы И которых реализуют конъюнкцию соответствующих выражении для Функция реализуется, по аналогии с функцией

Рис. 14.15

Построим ССВК для кода 3 из 6. Таблицы истинности всех функций представлены в табл. 14.18. Как следует из таблицы, функция Функция Т (К 0 принимает единичное значение на всех тех двоичных наборах из подмножества А, которые содержат хотя бы одну единицу. Поэтому функция может быть записана выражением Рассуждая аналогично, получим аналитические выражения для остальных функций:

Согласно выражениям для имеем

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

ССВК для разделимых кодов

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

Рис. 14.16

где — информационные разряды; — проверочные разряды кода; — схема формирования проверочных разрядов (для линейных групповых кодов схема реализует уравнения обобщенной проверки на четность; для кодов Бергера схема есть комбинационный сумматор числа нулей в информационной части кодового вектора длины С — многоразрядная ССВК, состоящая из самопроверяемых схем сжатия.