14.3. ФУНКЦИОНАЛЬНЫЙ КОНТРОЛЬ ЦИФРОВЫХ АВТОМАТОВ ПРИ ИСПОЛЬЗОВАНИИ ЛИНЕЙНЫХ ГРУППОВЫХ КОДОВ

Контроль комбинационных схем

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

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

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

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

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

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

1. Если исходная таблица истинности КС задана для совокупности булевых функций то формат единичной части порождающей матрицы линейного группового кода выходов КС с обнаружением -кратной ошибки равен Любой проверочный столбец порождающей матрицы Армируется как сумма по модулю 2 некоторого числа ее информационных столбцов. При этом любой информационный столбец должен присутствовать в качестве компоненты суммы хотя бы для организации одного проверочного столбца (см. гл. 13).

2. Каждый вектор и, порождающей матрицы должен иметь вес в смысле Хэмминга

3. Кодовое расстояние в смысле Хэмминга между двумя любыми векторами порождающей матрицы должно удовлетворять соотношению а между любыми двумя проверочными векторами к — соотношению

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

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

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

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

Таблица 14.2

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

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

Уравнения, определяющие процедуру декодирования построенного кода, очевидно будут иметь вид:

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

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

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

Рис. 14.3

Таблица 14.3

кодов. Порождающая матрица кеда будет иметь вид

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

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

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

Контроль автоматов с памятью

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

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

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

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

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

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

К построенному таким образом автомату добавляют Таких схем может быть две: СОО — присоединяется к выходам элементов памяти автомата и фиксирует искажения информации в векторах его кода состояний; — присоединяется к выходным каналам автомата и фиксирует искажения информации в векторах его кода выходов.

Таблица 14.4

Таблица 14.5

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

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

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

Таблица 14.6

Таблица 14.7

Рис. 14.4.

Уравнение, определяющее процедуру декодирования» может быть представлено в виде

которое фактически определяет структуру схем обнаружения ошибои и Кодируем состояния и выходные сигналы автомата соответствии с выбранным кодом (см. табл. 14.5 и 14.6).

Структурная таблица переходов автомата (она же таблица функций возбуждения) представлена табл. 14.7.

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

Запишем уравнения для Укрупненная структурная схема автомата с контролем представлена на рис. 14.4.

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

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

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

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

Таблица 14.8

Рис. 14.5

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

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

и функций выходов:

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

Код состояний исходного автомата представляет множество векторов а код выходов — множество векторов Порождающая матрица линейного группового кода состояний с

Рис. 14.6

Таблица 14.9

обнаружением однократной ошибки имеет вид

Порождающая матрица линейного группового кода выходов с обнаружением однократной ошибки имеет вид

Уравнения, определяющие структуру схем и могут быть представлены следующим образом:

Окончательный вариант структурной таблицы переходов автомата имеет вид (табл. 14.9).

Функции возбуждения и выходов представляются уравнениями:

Реализация схемы автомата с контролем приведена на рис. 14.6.

Коррекция ошибок в автоматах с памятью

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

линейных групповых кодов с где — кратность корректируемой ошибки. Рассмотрим один из методов коррекции ошибок, предложенный М. А. Гавриловым. Для упрощения рассмотрим коррекцию ошибки кратности возникающей в векторах двоичного кода состояний автомата. Основная идея метода базируется на том факте, что при появлении -кратной ошибки в векторе состояния структурного автомата автомат попадает в некоторое состояние отстоящее от состояния на расстоянии Хэмминга Поэтому, если автомат из состояния будет осуществлять точно такие же переходы, как из состояния то ошибка кратности не повлияет на правильность его работы. При этом, естественно, полагается, что автомат (если это автомат Мура) выдает одинаковые выходные сигналы как в состоянии так и в состоянии Для автомата Мили переходы из некоторого состояния и из в должны нагружаться одной и той же буквой выходного сигнала. Таким образом, описанный метод переводит исходный автомат в некоторый автомат, эквивалентный исходному, с помощью преобразований над таблицей переходов и выходов исходного автомата. Преобразование исходного автомата может быть выполнено в несколько этапов:

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

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

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

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

Синтезируем автомат Мура с коррекцией однократной ошибки в векторе состояния, используя метод 130]. Таблица переходов автомата представлена в табл. 14.10.

Таблица 14.10

Таблица 14.11

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

Кодирование состояний представлено табл. 14.11.

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

Исходная таблица переходов преобразуется с учетом введенных периферийных точек сфер (табл. 14.13). Дальнейший синтез производится обычным способом с учетом сформулированных требований.

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

Таблица 14.12

Таблица 14.13

Таблица 14.14

Таблица 14.15

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

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

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

Кодирование состояний и выходов автомата унитарными кодами представлено в табл. 14.15, 14.16.

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

Таблица 14.16

Таблица 14.17

Функции возбуждения и функции выходов аналитически представляются в виде

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