Исследование двоичных кодов с суммированием взвешенных переходов для систем технической диагностики и обработки информации в устройствах железнодорожной автоматики и телемеханики тема диссертации и автореферата по ВАК РФ 05.13.06, кандидат наук Дмитриев Вячеслав Владимирович

• Дмитриев Вячеслав Владимирович
• кандидат наук
• 2017

Оглавление диссертации кандидат наук Дмитриев Вячеслав Владимирович

СОДЕРЖАНИЕ

Список условных обозначений

Введение

Глава 1. Функциональный контроль логических схем железнодорож- 15 ной автоматики и телемеханики

1.1 Актуальность задачи обнаружения отказов в логических устрой- 15 ствах железнодорожной автоматики и телемеханики

1.2 Функциональный контроль логических схем железнодорожной 18 автоматики и телемеханики

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

1.4 Постановка задач диссертации 32 Глава 2. Контроль комбинационных схем на основе кодов с сумми- 34 рованием взвешенных переходов

2.1 Построение кода с суммированием взвешенных переходов

2.2 Код с суммированием взвешенных переходов 38 с весовыми коэффициентами в виде натуральной последовательности чисел

2.3 Модульный код с суммированием взвешенных переходов с весо- 43 выми коэффициентами в виде натуральной последовательности чисел

2.4 Выводы по главе 51 Глава 3. Новые структуры системы функционального контроля логи- 52 ческих схем

3.1 Традиционные структуры системы функционального контроля

3.2 Стандартная структура системы функционального контроля «по- 57 чти дублирование»

3.3 Стандартная структура системы функционального контроля на

основе оптимального кода

3.4 Выводы по главе

Глава 4. Коды с суммированием с эффективным обнаружением дву- 83 кратных ошибок

4.1 Анализ состава ошибок по кратностям в комбинационных схемах

4.2 Оптимальный модифицированный код с суммированием с мини- 89 мизированным количеством ошибок малой кратности

4.3 Построение систем функционального контроля на основе новых 94 оптимальных кодов

4.4 Коды с суммированием с обнаружением любых двукратных оши- 100 бок

4.5 Выводы по главе 104 Глава 5. Особенности применения кодов с суммированием в систе- 105 мах технической диагностики железнодорожной автоматики

5.1 Синтез генераторов и тестеров

5.2 Применение кодов с суммированием взвешенных переходов в си- 116 стемах технической диагностики и мониторинга

5.3 Выводы по главе 127 Заключение 128 Библиографический список 130 Приложение А - Каталоги необнаруживаемых ошибок в коде с сум- 146 мированием и его модификациях

Приложение Б - Каталоги необнаруживаемых ошибок в коде с сум- 161 мированием и его модификациях для контрольных примеров из библиотеки LGSynth'89

Приложение В - Справки о внедрении результатов диссертационного 178 исследования

СПИСОК УСЛОВНЫХ ОБОЗНАЧЕНИЙ d - кратность необнаруживаемой ошибки;

F(x) - блок основной логики в системе функционального контроля; fx, f2, ..., fm- рабочие функции системы функционального контроля; <f f ... fm> - информационный вектор кода с суммированием; gi, g2, gk- контрольные функции системы функционального контроля; G - генератор;

Gk(x) - блок контрольной логики;

<gi g2 . gk> - контрольный вектор кода с суммированием; <g\ g'2 . gk> - контрольный вектор кода с суммированием, сформированный генератором в системе функционального контроля; k - количество разрядов в контрольном векторе; m - количество разрядов в информационном векторе;

(т, к, 2)-код - код с обнаружением любых двукратных ошибок в информационных векторах;

(т^)-код - код с суммированием с параметрами m и k; L - площадь логического устройства (в усл. единицах); M - модуль кода с суммированием;

Nm - количество необнаруживаемых ошибок в информационных векторах

кода;

Nm,d - количество необнаруживаемых ошибок кратностью d в информационных векторах кода;

Nd - количество необнаруживаемых ошибок кратностью d в контрольной комбинационной схеме;

N^k - общее количество необнаруживаемых ошибок в оптимальном коде с

суммированием;

r - значение истинного веса кодового вектора;

r(mod M) - наименьший неотрицательный вычет числа r по модулю M;

ЯШТ(т, к, wi Е 21 )-код - модифицированный код с суммированием взвешенных переходов с последовательностью весовых коэффициентов-степеней двоек;

£(т,к)-код - код Бергера;

Еа - вес информационного вектора с учетом весовых коэффициентов переходов или разрядов;

Wi - весовой коэффициент /-го разряда или весовой коэффициент перехода между /-м и /+1-м разрядами;

Ж8(т,к)-код - код с суммированием взвешенных информационных разрядов;

ШБН(т, к)-код - взвешенный код с суммированием весовых коэффициентов разрядов без переносов;

Ж5М(т ,к)-код - модульный код с суммированием взвешенных информационных разрядов;

ЖТ(т,к)-код - код с суммированием взвешенных переходов;

ШТ(т, к, wi Е М)-код - код с суммированием взвешенных переходов с натуральной последовательностью весовых коэффициентов;

ШТ(т, к,Ш1 Е 2')-код - код с суммированием взвешенных переходов с последовательностью весовых коэффициентов-степеней двоек;

ЖТМ(т,к)-код - модульный код с суммированием взвешенных переходов;

ШТМ(т, к, wi Е М)-код - модульный код с суммированием взвешенных переходов с натуральной последовательностью весовых коэффициентов;

ШТМР(т, к)-код - код, полученный по алгоритму перестановок;

а - поправочный коэффициент, используемый при построении модифицированного кода с суммированием;

вс1 - доля необнаруживаемых ошибок кратностью С от общего количества ошибок данной кратностью;

£р - коэффициент эффективности по сложности технической реализации системы функционального контроля по заданному коду с суммированием в сравнении с системой контроля по паритету;

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

ym - доля необнаруживаемых ошибок от общего количества ошибок в информационных векторах;

ym,d - доля необнаруживаемых ошибок кратностью d от общего количества ошибок данной кратностью в информационных векторах;

- коэффициент эффективности кода с суммированием;

HA - полусумматор;

FA - полный сумматор;

TRC - модуль сжатия парафазных сигналов;

TSC - полностью самопроверяемый тестер;

- целое сверху от вычисляемого значения;

. J - целое снизу от вычисляемого значения;

Введение диссертации (часть автореферата) на тему «Исследование двоичных кодов с суммированием взвешенных переходов для систем технической диагностики и обработки информации в устройствах железнодорожной автоматики и телемеханики»

ВВЕДЕНИЕ

Актуальность темы диссертационного исследования. Совершенствование систем управления движением поездов невозможно без использования достижений научно-технического прогресса в области компьютерных технологий. Морально устаревшая релейная техника железнодорожной автоматики и телемеханики (ЖАТ) постепенно сменяется микроэлектронной и микропроцессорной, а сами управляющие комплексы от использования только аппаратных составляющих переходят к использованию аппаратно-программных средств [48].

Микроэлектронные и микропроцессорные элементы имеют ряд преимуществ перед релейными, которые заключаются, прежде всего, в том, что при небольших (и чаще миниатюрных) размерах они способны выполнять гораздо большее количество функций, в том числе, по автоматизации процесса управления напольным технологическим оборудованием ЖАТ. Тем не менее, усложнение микроэлектронной техники, увеличение количества транзисторов, размещаемых на единице площади, низкие пороги срабатывания элементов, проблема обеспечения электромагнитной совместимости и т.д. требуют обеспечения высокого уровня технического диагностирования элементов и узлов управляющих систем. В конечном итоге, такие важные свойства как надежность и безопасность перевозочного процесса напрямую определяются свойствами элементной базы и конфигурациями связи между устройствами в системе управления, а методы тестирования позволяют идентифицировать возникающие в процессе эксплуатации средств ЖАТ неисправности: от сбоев и устойчивых отказов до предотказных состояний [32, 48, 68, 87, 88, 104].

Все современные системы ЖАТ имеют развитые подсистемы технического диагностирования как внешними средствами, так и внутренними (самодиагностирование). На железных дорогах России повсеместно распространены системы технического диагностирования и мониторинга (СТДМ) устройств ЖАТ, являющиеся «надстройками» над действующими системами [22, 31, 51]. Они позволяют

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

Техническое диагностирование элементов и узлов микроэлектронной и микропроцессорной техники может быть реализовано согласно двум стратегиям: тестовому и функциональному контролю [48, 68]. Методы тестового диагностирования подразумевают кратковременное отключение объекта диагностирования от управляемых устройств с целью подачи на его входы специальных проверяющих воздействий [42, 59, 127]. В системах управления данное обстоятельство требует 100% резервирования тестируемого устройства. Функциональное диагностирование позволяет определять техническое состояние объекта диагностирования без отключения его от работы, а входные воздействия в таком случае одновременно являются и проверяющими [109, 123, 126]. Методы тестового и функционального диагностирования в современных системах ЖАТ на микропроцессорной и микроэлектронной основе используются в совокупности.

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

Степень разработанности темы исследования. Сама область технической диагностики развивается активно со второй половины XX века и по настоящее время. Известно большое количество научных школ, изучающих проблемы технической диагностики объектов различной физической и химической природы. В области технической диагностики выдающихся результатов достигли такие ученые постсоветского пространства как А. Д. Закревский, М. Ф. Каравай,

A. Ю. Матросова, А. В. Мозгалевский, П. П. Пархоменко, Вал. В. Сапожников,

B. В. Сапожников, Е. С. Согомонян, В. И. Хаханов и другие. В мировом сообществе известны такие ученые как M. Gössel, D. Das, E. Fujiiwara, P. K. Lala, E. J. McCluskey, D. K. Pradhan, J. Roth, F. F. Sellers, N. A. Touba, R. Ubar, Y. Zorian и др. Много их работ в области технической диагностики посвящено приложению методов помехоустойчивого кодирования в задачах построения надежных дискретных устройств и непосредственно систем функционального контроля.

Прикладные вопросы обеспечения надежности устройств и систем ЖАТ исследовались такими учеными как Д. В. Гавзов, А. В. Горелик, Ю. А. Кравцов, В. М. Лисенков, А. Б. Никитин, Вал. В. Сапожников, Вл. В. Сапожников, В. И. Шаманов и многими другими.

Тема диссертации соответствует специальности паспорту специальности 05.13.06 «Автоматизация и управление технологическими процессами и производствами (транспорт)» по пунктам:

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

п. 14. Теоретические основы, методы и алгоритмы диагностирования (определения работоспособности, поиск неисправностей и прогнозирования), АСУТП, АСУП, АС ТПП и др.

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

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

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

3. Разработка новых стандартных структур систем функционального контроля, основанных на использовании кодов с суммированием взвешенных переходов между разрядами в информационных векторах.

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

5. Разработка метода построения систем функционального контроля со 100%-ным обнаружением одиночных неисправностей в контролируемых объектах

6. Разработка кодов с суммированием с минимальным общим количеством необнаруживаемых ошибок и минимальным количеством ошибок малых кратностей.

7. Разработка методов синтеза генераторов исследуемых кодов с суммированием.

8. Повышение эффективности технологии мониторинга в системе удаленного контроля и мониторинга «Аппаратно-программный комплекс диспетчерского контроля» на основе применения оптимальных кодов с суммированием при обработке дискретных диагностических данных.

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

Научная новизна диссертационного исследования заключается в следующем:

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

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

3. На основе применения модифицированных взвешенных кодов с суммированием разработаны структурные схемы систем функционального контроля, реализуемые на основе стандартных блоков.

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

5. Разработаны способы синтеза генераторов (кодеров) новых кодов с суммированием.

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

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

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

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

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

Положения, выносимые на защиту:

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

2. Результаты исследований свойств кодов с суммированием взвешенных переходов и их модификаций в системах функционального контроля.

3. Способы построения кодов с суммированием с наименьшим общим количеством необнаруживаемых ошибок в информационных векторах.

4. Новые стандартные структуры систем функционального контроля.

5. Способ построения систем функционального контроля со 100%-ным обнаружением ошибок в контролируемых объектах.

6. Методы синтеза генераторов кодов с суммированием взвешенных переходов.

7. Результаты практического использования методов, разработанных в диссертационном исследовании в системах технического диагностирования и мониторинга устройств ЖАТ.

Степень достоверности результатов подтверждается точными вычислениями и экспериментальными исследованиями с системами контрольных логических схем.

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

1. Международную конференцию «Региональная информатика» (г. Санкт-Петербург, Россия, 2014 год).

2. Международную конференцию «IEEE East-West Design & Test Symposium» (г. Батуми, Грузия, 2015 год).

3. Международную конференцию «ИнтеллектТранс» (г. Санкт-Петербург, Россия, 2015 год).

4. Международную конференцию «Новые информационные технологии в исследовании сложных структур» (г. Екатеринбург, Россия, 2016 год).

5. Международную конференцию «Транспортные системы: тенденции развития» (г. Москва, Россия, 2016 год).

6. Семинар по технической диагностике под руководством члена-корреспондента РАН П. П. Пархоменко в Институте проблем управления им. В. А. Трапезникова РАН РФ.

7. Семинары «Автоматика и дискретная математика» на кафедре «Автоматика и телемеханика на железных дорогах» Петербургского государственного университета путей сообщения Императора Александра I в период с 2012 по 2016 гг. (г. Санкт-Петербург, Российская Федерация).

Диссертационная работа состоит из 5 глав, введения, заключения и трех приложений.

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

систем функционального контроля со 100%-ным обнаружением одиночных неисправностей в контролируемых объектах, основанный на разбиении выходов на группы с учетом влияния на них неисправностей и свойств кодов с суммированием. Предложен способ построения кодов с суммированием с минимальным общим количеством необнаруживаемых ошибок и возможностью обнаружения любых двукратных искажений в информационных векторах. Пятая глава посвящена практическим приложениям результатов диссертационного исследования. Отмечены схемотехнические особенности контрольного оборудования систем функционального контроля, организованных по предлагаемым в диссертации кодам. Освещается способ повышения надежности и быстродействия средств программной обработки дискретных данных на нижнем уровне системы технического диагностирования и мониторинга устройств железнодорожной автоматики и телемеханики АПК-ДК. В заключении подводятся результаты диссертационного исследования.

Основные результаты диссертационного исследования опубликованы в

20 работах, в том числе, в 2 академических публикациях, 6 публикациях в изданиях, включенных в Перечень ВАК РФ и 1 публикации, индексированной в международной базе цитируемости SCOPUS.

Основные научные и практические результаты диссертационного исследования внедрены в программное обеспечение нижнего уровня системы технического диагностирования и мониторинга «Аппаратно-программный комплекс диспетчерского контроля» для повышения надежности хранения дискретных данных и уменьшения времени обработки запросов. Обновленное программное обеспечение прошло процедуру тестирования и планируется к внедрению на объектах мониторинга Дальневосточной железной дороги.

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

1.1 Актуальность задачи обнаружения отказов в логических устройствах железнодорожной автоматики и телемеханики

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

Современные устройства и системы ЖАТ строятся на различной элементной базе, включающей в себя как громоздкие электромагнитные реле, так и миниатюрные компоненты на основе полупроводниковой техники. Развитие области ЖАТ направлено на внедрение микроэлектронной и микропроцессорной техники взамен морально устаревшей релейной техники. С внедрением микроэлектронной и микропроцессорной техники появляется возможность создания высокоинтеллектуальных управляющих комплексов, имеющих встроенные подсистемы поддержки принятия решения и оптимизации функций управления перевозочным процессом. Более того, при повышении скоростей перемещения грузов и пассажиров до скоростей свыше 200 км/ч начинают проявляться некоторые недостатки схемных решений на релейной основе, а их модернизация носит чаще всего лишь частный характер [28].

Средства ЖАТ - это весьма важные звенья в механизме регулирования движения поездов. Отказы устройств и систем ЖАТ могут приводить к различным по степени тяжести последствиям: от отсутствия какого-либо влияния вне трафика поездов до пагубного воздействия, связанного со снижением пропускной способности участка или же, вовсе, приводить к возникновению аварий и катастроф. Так, например, в начале 2000 года из-за отказа системы интервального ре-

гулирования движения поездов на линии «Санкт-Петербург - Москва» была допущена катастрофа - столкновение пассажирского поезда с хвостом грузового поезда, следовавшего в попутном направлении. Задача обеспечения надежного и безопасного функционирования средств ЖАТ - первостепенна в хозяйствах автоматики и телемеханики российских железных дорог.

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

Современные микроэлектронные и микропроцессорные средства ЖАТ реализуются на миниатюрных компонентах, чаще всего, имеющих симметричную характеристику отказов, поэтому требуют специальных мер для обеспечения надежности и безопасности функционирования. К таким мерам относятся резервирование, диагностирование, использование помехоустойчивого кодирования и самопроверяемых схем, безопасных схем и т.д. [8 - 10, 23, 47].

Для контроля технического состояния устройств и систем ЖАТ в процессе их эксплуатации используются методы их технического обслуживания и ремонта. Как правило, на российских железных дорогах это ручное техническое обслуживание силами технического персонала дистанций сигнализации, централизации и блокировки (СЦБ). Однако, как следует из большого количества публикаций [1, 7, 18, 25, 32, 35, 51], наметилась тенденция на автоматизацию большого количества работ по техническому обслуживанию, позволяющая снизить влияние человеческого фактора на процесс выполнения данной задачи.

Современные системы ЖАТ на микроэлектронной и микропроцессорной основах снабжаются развитым диагностическим обеспечением, позволяющим в процессе их эксплуатации проводить процедуры определения технического состояния отдельных блоков и узлов, а также прогнозировать дальнейшие изменения технических состояний [32, 48].

В процессе создания подсистемы диагностирования самой системы ЖАТ разработчик используют такие методы технического диагностирования, как тестовое (off-line) и функциональное (on-line) диагностирование. Тестовое диагностирование подразумевает подачу специальных проверочных воздействий на объект диагностирования при отключении его от управляемых объектов. В системах управления, коими являются и системы ЖАТ, использование тестового диагностирования возможно лишь при 100%-ном резервировании и при наличии временного ресурса. Функциональное диагностирование связано с техническим диагностированием объекта в процессе его использования по назначению, когда все входные воздействия, по сути, являются и проверочными. Тестовое и функциональное виды диагностирования используются в современных системах ЖАТ в комплексе [48].

На рис. 1.1 и рис. 1.2 изображены системы тестового и функционального технического диагностирования соответственно, где иллюстрируются и принципы их работы [68]. Под системой технического диагностирования понимается совокупность объекта диагностирования (ОД) и технических средств диагностирования (ТСД). Для реализации любой системы технического диагностирования характерно наличие аппаратурных затрат.

Тестовые

воздействия

ТСД ОД

Ответы

I

Результаты диагностирования

Рисунок 1.1. Система тестового технического диагностирования

Рабочие воздействия

V V

У

Результаты диагностирования

Рисунок 1.2. Система функционального технического диагностирования

1.2 Функциональный контроль логических схем железнодорожной автоматики и телемеханики

Системы ЖАТ, построенные на современной элементной базе, содержат в своих структурах большое разнообразие компонентов, которые могут быть классифицированы как логические объекты без памяти (комбинационные составляющие) и логические объекты с памятью (многотактные составляющие). Например, к комбинационным устройствам относятся арифметико-логические устройства автоматики и вычислительной техники, а к многотактным - различные триггеры [72]. Для определения технического состояния многотактных схем автоматики используются методы сканирования [68], а для определения технического состояния комбинационной логики - методы тестового и функционального контроля [57, 93, 107, 108, 112, 122, 124].

В структурах микроэлектронных и микропроцессорных устройств возможны неисправности различного вида - от коротких замыканий и обрывов до «временных задержек» передачи сигналов на рабочие выходы. Как правило, при построении систем с обнаружением ошибок рассматривают так называемые константные неисправности выходов внутренних логических элементов: константа 1 (неисправность вида 0^1) и константа 0 (неисправность вида 1^0). В [68] отмечается что модель константной неисправности покрывает до 90% - 95% реальных физических дефектов логических схем автоматики.

ТСД ОД

Ответы

Под константной неисправностью выхода логического элемента понимают наличие на выходе постоянного сигнала определенного вида (0 или 1) вне зависимости от состояния входов логического элемента [68].

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

Определение 1.1. Ошибкой будем называть искажение выходного вектора комбинационной логической схемы в результате неисправности.

При рассмотрении систем функционального контроля важным является разделение ошибок на виды [64].

Определение 1.2. Будем называть ошибку, происходящую на некотором входном наборе, монотонной, если она искажает разряды выходного вектора одинаковым образом (0^1 или 1 ^ 0).

Определение 1.3. Будем называть ошибку, происходящую на некотором входном наборе, симметричной, если количество искажений вида 0^1 равно количеству искажений вида 1^0.

Определение 1.4. Будем называть ошибку, происходящую на некотором входном наборе, ассиметричной, если количество искажений вида 0^1 не равно количеству искажений вида 1^0.

Для косвенного контроля возникновения одиночных неисправностей в логических устройствах автоматики по результатам вычислений значений рабочих функций используют системы функционального контроля [61].

На рис. 1.3 изображена традиционная структура системы функционального контроля [74, 98]. В качестве объекта диагностирования в ней выступает логическое устройство F(x), реализующее систему булевых функцийfi,f2, ..., fm. Технические средства диагностирования включают в себя специальный блок контрольной логики G(x) и тестер (TSC). Блок G(x) вычисляет систему контрольных функ-

ций gi, g2, ..., gk, а TSC осуществляет проверку соответствия значений функций fi,f2, fm и gi, g2, gk. При наличии соответствия между значениями рабочих и контрольных функций тестер вырабатывает специальный сигнал контроля об «отсутствии неисправностей» в системе функционального контроля, а при нарушении соответствия - сигнал контроля «о наличии неисправностей» в системе функционального контроля.

xi Х2

Рисунок 1.3. Структура системы функционального контроля

x

Тестер в системе функционального контроля выполняет особую роль - от результатов его вычислений зависит правильность постановки диагноза. Таким образом, тестер является «последним сторожем» в системе функционального контроля, и должен обеспечивать свойство полной самопроверяемости [75]. Данное свойство подразумевает выполнение двух условий:

1) технический объект должен быть защищенным от внутренних неисправностей;

2) технический объект должен быть самотестируемым.

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

Тестер, фактически, сравнивает между собой булевы векторы рабочих функций </1/2 ... /т> и контрольных функций g2 ... gk> Будем в дальнейшем называть вектор рабочих функций информационным вектором, а вектор кон-

трольных функций - контрольным вектором. Длины информационных и контрольных векторов обозначим, соответственно, как т и к.

При организации системы функционального контроля по структуре, изображенной на рис. 1.3, в качестве основы используется некоторый систематический (т,к)-код [75, 95]. Это позволяет применять в качестве тестера стандартное устройство на основе генератора (кодера) контрольных разрядов и компаратора (рис. 1.4). Генератор по значениям информационного вектора </1 /2 ... /т> формирует значения контрольного вектора ¥2 ... ¥к>, а компаратор сравнивает одноименные сигналы и

Список литературы диссертационного исследования кандидат наук Дмитриев Вячеслав Владимирович, 2017 год

—Л -

п\\ а \\ а \\

и V, V.

;; I

V, /' ч \\ I1 \\ X /' \\ { ; '«, \ ! \

1

4

100000000 10000000 1000000 100000 10000 1000 100 10 1

5

6

7

8

9

10 11 12 13 14 15

16

9 10 11 12 13 14 15 16

Рисунок 2.3. Сравнение количества необнаруживаемых ошибок (ось ординат) для кодов ШТМ(т, к, £ И), ШТ(т, к, £ И) и Б(т, к) при различном т (ось абсцисс)

4

5

6

7

8

500000

50000

5000

500

8

>— "Т I—WTM

а1и4 ст85а ст163а стЬ

си

f51m 74т! ст82а а1и2

х2 ст162а

Рисунок 2.4. Сложность контрольного оборудования для кодов №ТМ(т, к, Wi Е М), WT(m, к, Е М) и Б(т, к), для различных контрольных схем

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

1000000

100000

10000

1000

100

10

\\ • Л

• \х » 1 » \ 1 \ » \ 1 \ 1 \ \ \ Уч / \ / \ / \ / \

1 \ / 'А * , |\ 1 / я V / ' » » / / \ V / ' 4 V / ' 4 V / \ 1 \ / 1 \ \

»\ / »\ / * \ / / ч /» Н / / / % / \ / \ 1 \ V 1 \\ / \\\/ / Л • / \\ / « /

\ /''

♦ 8 ....... "Т

—■— "ТМ

А

/ \

/?- \ // ^ \ Л \ Л //

/' 4 // // X / ,

Г/ \ ''

/ N Г V

а!и4 ст85а ст163а стЬ си f51m 74т! ст82а а!и2 х2 ст162а

1

Рисунок 2.5. Обнаруживающие способности кодов WTM(m,k,wi Е М), WT(m,k,wi ЕМ) и

Б(т, к), для различных контрольных схем

Анализируя оба графика одновременно, можно принять решение о том, какой способ кодирования целесообразно применить. Например, для схемы f51m оба кода не обнаруживают около 0,9% неисправностей, но при этом реализация контрольного оборудования при использовании ШТ(т, к, wi Е М)-кода получается сложнее на 37%, чем при использовании Б(т, к)--кода.

2.4 Выводы по главе

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

1. При использовании идеи приписывания весовых коэффициентов переходам между разрядами в информационных векторах возможно построение кода с суммированием с улучшенными характеристиками по сравнению с классическими подходами к построению кода.

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

3. Для значений длин информационных векторов шф2г (¿=1,2,...) могут быть построены модульные коды с суммированием взвешенных переходов, являющиеся оптимальными кодами с суммированием с количеством контрольных разрядов, как у классических кодов Бергера.

4. Результаты экспериментов с комбинационными схемами системы Ь08упШЛ89 подтверждают теоретические положения, сформулированные в данном разделе диссертации.

ГЛАВА 3. РАЗРАБОТКА НОВЫХ СТРУКТУР СИСТЕМЫ ФУНКЦИОНАЛЬНОГО КОНТРОЛЯ ЛОГИЧЕСКИХ СХЕМ

3.1 Традиционные структуры системы функционального контроля

При решении практических задач разработки систем функционального контроля логических схем часто используют такие структуры, которые не требуют применения специальных методов для построения блоков контрольной логики д(х), генератора £ и компаратора ТЯС (см. рис. 1.3). К таким структурам относится схема дублирования (рис. 1.5), в которой в качестве блока С(х) используется еще один экземпляр контролируемого блока Р(х), а блок ТЯС реализуется из стандартных модулей сравнения. Схема дублирования реализует идею контроля схемы на основе применения кода с повторением. В ней отсутствует специальный генератор £, используемый при реализации других структур систем функционального контроля. Также при выборе кода отличного от кода с повторением появляется необходимость синтезировать специфичного для данного блока Р(х) блок дополнительной логики С(х). Если для систем функционального контроля известна стандартная структура генератора в, то блок С(х) может быть получен при помощи стандартной программы оптимизации структуры комбинационной схемы [111, 119], состоящей из последовательного соединения схем блоков С(х) и £ (рис. 3.1). Блок С(х), полученный таким образом, будем обозначать д(х)[орг].

XI. Х2-

Р(Х)

.ш > О

/2(Х) . Я2(х)

!ш(х) ' • —► Е0

#(х)[ор1]

Х

Рисунок 3.1. Получение оптимизированной структуры блока С(х)

Таким образом, для получения стандартной структуры системы функционального контроля, для построения которой можно использовать только стандартные структуры блоков g(x)[opt], G и TRC, необходимо чтобы метод контроля, положенный в основу системы функционального контроля, обеспечивал стандартную структуру генератора G. Данному условию отвечает метод контроля, основанный на применении кода паритета. Структура контроля для данного кода изображена на рис. 1.5. Генератор G вычисляет по значениям выходных сигналов блока F(x) функцию паритета

fp(x) = f1(x)Bf2(x)e ... @fm(x) и реализуется при помощи стандартной линейной схемы.

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

В табл. 3.1 приведены результаты экспериментальных исследований с системой контрольных комбинационных схем LGSynth'89 с целью определения показателей аппаратурной избыточности системы функционального контроля дублирования и кода паритета по сравнению с контролируемой схемой. Контрольные комбинационные схемы описаны в формате *.netblif, который является списочной формой задания схемы в виде net-листа - он содержит информацию о логических элементах структуры и задает конфигурацию связей между входами и выходами самой схемы и внутренними логическими элементами. Все контрольные комбинационные схемы записаны в базисе ИЛИ-НЕ (библитека nor.genlib).

Таблица 3.1. Сравнение аппаратурной избыточности для системы контроля

по коду паритета и системы дублирования для ряда контрольных схем

# Контрольная схема Площадь контрольной схемы Площадь системы функционального контроля Отношение площадей систем контроля и контролируемых схем, %

По коду паритета Дублирования По коду паритета Дублирования

1 alu2 8856 15816 19008 178,59 214,63

2 alu4 17288 101468 36384 586,93 210,46

3 b1 304 800 1392 263,16 457,89

4 c17 256 640 784 250 306,25

5 cm42a 640 1688 3600 263,75 562,5

6 cm82a 656 1536 1840 234,15 280,49

7 cm85a 992 3032 2512 305,65 253,23

8 cm138a 560 1368 2928 244,29 522,86

9 cm151a 760 896 1792 117,89 235,79

10 cm162a 1176 3400 3392 289,12 288,44

11 cm163a 1176 4288 3392 364,63 288,44

12 cmb 1248 2176 3280 174,36 262,82

13 cu 1464 3176 5504 216,94 375,96

14 decod 800 2392 5456 299 682

15 f51m 3360 6632 8528 197,38 253,81

16 pcle 1816 5576 5696 307,05 313,66

17 pm1 1280 4112 5648 321,25 441,25

18 tcon 1152 4344 6160 377,08 534,72

19 x2 1304 2400 4160 184,05 319,02

20 z4ml 1600 4112 3984 257 249

Средние значения 271,61 352,66

Показателем сложности является площадь, занимаемая устройством на кристалле. Площадь рассчитывается с применением известного интерпретатора SIS (Sequential Interactive Synthesis), разработанного в Университете Калифорнии (Berkeley) специально для решения задач технической диагностики [90]. В SIS

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

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

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

Данные, представленные в табл. 3.1 и 3.2, позволяют сделать следующие выводы. Разработчиков систем функционального контроля во многих случаях могут не удовлетворять схемы дублирования поскольку часто сложность схемы увеличивается более чем в три раза. Система функционального контроля на основе кода паритета имеют меньшую аппаратурную избыточность, но количество необ-наруживаемых ошибок на выходах для некоторых схем превышает 20-40%, что также может не отвечать требованиям практики. В связи с этим, актуальным является вопрос разработки новых стандартных структур систем функционального контроля, которые позволяли бы при решении конкретных практических задач получать схемы с лучшими характеристиками по сложности и обнаружению неисправностей по сравнению с дублированием и методом паритета.

Таблица 3.2. Сравнение количества необнаруживаемых ошибок для систем контроля по коду паритета для серии контрольных схем

# Контрольная схема Всего ошибок Не обнаруживается Доля необнаруживаемых ошибок от общего их количества, %

1 alu2 61988 12260 19,78

2 alu4 1966881 368588 18,74

3 b1 44 2 4,55

4 c17 234 46 19,66

5 cm42a 278 8 2,88

6 cm82a 648 68 10,49

7 cm85a 30912 176 0,57

8 cm138a 680 0 0

9 cm151a 14592 14592 100

10 cm162a 317331 44763 14,11

11 cm163a 1221312 153920 12,6

12 cmb 288218 39462 13,69

13 cu 137984 61888 44,85

14 decod 224 0 0

15 f51m 13008 783 6,02

16 pcle 17472087 1018583 5,83

17 pm1 189440 10944 5,78

18 tcon 4849664 0 0

19 x2 19708 2524 12,81

20 z4ml 4168 128 3,07

Среднее значение 14,77

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

3.2 Стандартная структура системы функционального контроля

«почти дублирование»

Недостаток структуры дублирования заключается в том, что при ее построении невозможно для уменьшения сложности систем функционального контрля использовать особенности структуры блока С(х). Такая возможность появляется, если использовать при построении системы функционального контрля специальный код с суммированием взвешенных переходов. В табл. 3.3 отражены правила построения различных (т, ^)-кодов для случая т = 6. В классическом коде с суммированием Б(т, к) вес каждого разряда равен единице. Контрольные векторы образуются путем записи в контрольные разряды двоичного числа, равного сумме единичных информационных разрядов. Это число называется весом г информационного вектора. Количество контрольных разрядов к = \1од2(ш + 1)1. В коде со взвешенными информационными разрядами ШБ(т, к) последним присваиваются веса с различными значениями. В табл. 3.3 эти веса образуют прямую последовательность натуральных чисел. Общий вес г информационного вектора образуется путем суммирования весов всех разрядов.

Таблица 3.3. Весовые коэффициенты для различных модификаций кодов с суммированием

Код Весовые коэффициенты разрядов

™6 ^5 Ш4 Шз

Б(т, к) 1 1 1 1 1 1

ШБ(т, к) 6 5 4 3 2 1

Код Весовые коэффициенты переходов

^5 ш4 Шз w1

ШТ(т, к^^еИ) 5 4 3 2 1

ШТ(т,к^1е21) 16 8 4 2 1

В предыдущей главе диссертации исследованы коды с суммированием взвешенных переходов ШТ(т, к), при построении которых рассматривается каждый переход между соседними информационными разрядами ^ и , которому присваивается вес . Веса следуют в последовательности, образующей натуральный ряд чисел: 1, 2, 3, ..., начиная с младшего информационного разряда. Общий вес информационного вектора определяется как сумма активных переходов (см. формулу 2.1).

Значения разрядов контрольного вектора получают путем двоичного представления числа Ш. Введем в рассмотрение ШТ(т, к^1е21) - код, веса переходов которого представляют собой последовательность чисел, равных 21 (I = 0,1,2,...) (см. таблицу 3.3). В табл. 3.4 приведен код ШТ(4,3,Ш1б21). Данный код имеет следующие особенности.

Так как в сумме (2.1) элементы суммирования равны 21 (I Е {0; 1; 2; ...;т — 1}), то веса информационных векторов Ш составляют подмножество чисел

Q = {0;1;2;...;2m — 1}. (3.1)

Из (3.1) следует, что число контрольных разрядов ШТ(т, к, wie2l) - кода

к = \1од2(2т —1)]=т-1, (3.2)

что на единицу меньше, чем в схеме дублирования. Поэтому данный код можно обозначить как ШТ(т^1е21)-код. Из (2.1) и (3.1) также следует, что каждому контрольному вектору соответствуют два информационных вектора, которые являются противоположными, т.е. отличаются друг от друга во всех разрядах. По это причине в ШТ(т^1б21) - коде не обнаруживаются только искажения с кратностью т, число которых равно 2т.

Из правил построения Е 2')-кода (см. табл. 3.3) следует, что кон-

трольный вектор для данного информационного вектора образуется из значений весовых коэффициентов wi, число которых равно т — 1.

Например, для ШТ(4, Е 21)-кода имеем (см. таблицу 3.4)

f4 fs f2 fl W3 w2 W1 93 92 9l

01 01 111 111 0 0 1 1 0 1 0 0 1 0

По этой причине значения контрольных разрядов вычисляются по стандартным формулам

91 = кШ

92 = f2®f3

9з = fs®f4 (3.3)

9т-1 = fm-1®fm

Таблица 3.4. Формирование контрольного вектора кода WT(4,3, wt62l)

И нформационные разряды w Контрольные раз ряды

f4 fs f2 fl 9з 92 9i

0 0 0 0 0 0 0 0

0 0 0 1 1 0 0 1

0 0 1 0 3 0 1 1

0 0 1 1 2 0 1 0

0 1 0 0 6 1 1 0

0 1 0 1 7 1 1 1

0 1 1 0 5 1 0 1

0 1 1 1 4 1 0 0

1 0 0 0 4 1 0 0

1 0 0 1 5 1 0 1

1 0 1 0 7 1 1 1

1 0 1 1 6 1 1 0

1 1 0 0 2 0 1 0

1 1 0 1 3 0 1 1

1 1 1 0 1 0 0 1

1 1 1 1 0 0 0 0

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

Рабочие выходы

X]

Х2

X,

Контрольные выходы

Рисунок 3.2. Структура системы «почти дублирование»

В табл. 3.5 приведены результаты эксперимента со схемами из набора контрольных примеров ЬОЗупШ'91 [90]. Эксперимент заключался в оценке сложности технической реализации систем функционального контроля, построенных по методам дублирование и «почти дублирование».

Для 15 из 25 выбранных комбинационных схем площадь системы функционального контроля, построенной по методу «почти дублирование», оказалась меньшей, чем площадь системы функционального контроля, построенной по методу дублирования (см. табл. 3.5). Максимальное улучшение показателя площади было получено для схемы т3 (73,86% от площади системы функционального контроля, построенной по методу дублирования). Для 10 схем из выбранного набора контрольных примеров система функционального контроля, построенная

по методу «почти дублирование», получилась более сложной, чем системы функционального контроля, построенная по методу дублирования. Максимальное ухудшение дал эксперимент со схемой 14 (130,412% от площади системы, построенной по методу дублирования).

В среднем площадь системы функционального контроля, построенной по методу «почти дублирование», составила 95,997% от площади системы дублирования.

Если взять в рассмотрение только те контрольные примеры, для которых получено уменьшение сложности систем функционального контроля, то для них в среднем площадь системы функционального контроля, построенная по методу «почти дублирование» составляет 81,008% от площади системы дублирования.

Таким образом, при построении системы функционального контроля на основе дублирования разработчик имеет возможность выбора между двумя системами, учитывая, что уменьшение сложности системы на 20-25% является существенным фактором.

Таблица 3.5. Результаты экспериментов с оценкой площадей

# Контрольная схема Входы/выход ы Площадь системы функционального контроля Отношение площадей систем контроля и контролируемых схем, % Отношение площадей систем «почти дуб-лирова-ние» и дублирование, %

F(x) Система дубли-рова-ние Система «почти дублирование» Система дублирование Система «почти дублирование»

1 apla 10/12 3048 9552 10536 313,39 345,67 110,3

2 b2 16/17 40952 86920 69824 212,25 170,5 80,33

3 b12 15/9 1848 6216 7352 336,36 397,84 118,28

4 br2 12/8 2952 8112 6848 274,80 231,98 84,42

5 dist 8/5 6968 15208 12584 218,25 180,6 82,75

6 dk17 10/11 1768 6680 7728 377,83 437,1 115,69

7 dk48 15/17 1808 8632 10192 477,43 563,72 118,07

8 in1 16/17 40952 86920 69824 212,25 170,50 80,33

9 intb 15/7 22248 46392 50320 208,52 226,18 108,47

10 m1 6/12 3064 9584 8128 312,79 265,27 84,81

11 m2 8/16 10096 24896 18736 246,59 185,58 75,26

12 m3 8/16 13464 31632 23288 234,94 172,96 73,62

13 m4 8/16 18704 42112 31680 225,15 169,38 75,23

14 max512 9/6 9632 20848 16528 216,45 171,59 79,28

15 max1024 10/6 17816 37216 29712 208,89 166,77 79,84

16 mp2d 14/14 2568 9216 11528 358,88 448,91 125,09

17 newapla 12/10 1192 5216 6304 437,58 528,86 120,86

18 newcpla2 7/10 1896 6624 5920 349,37 312,24 89,37

19 newcwp 4/5 440 2152 1784 489,09 405,45 82,9

20 newtpla2 10/4 840 2640 2056 314,29 244,76 77,88

21 root 8/5 3496 8264 6320 236,38 180,78 76,48

22 sex 9/14 1360 6800 7856 500 577,65 115,53

23 shift 19/16 3728 12160 15520 326,18 416,31 127,63

24 t4 12/8 1080 4368 5784 404,44 535,56 132,42

25 tms 8/16 6784 18272 15424 269,34 227,36 84,41

Средние значения 310,46 309,34 95,97

3.3 Стандартная структура системы функционального контроля на основе оптимального кода

Система функционального контроля типа дублирование и «почти дублирование» могут не удовлетворять разработчика в тех случаях, когда эти системы имеют слишком большую сложность (например, больше сложности основного блока F(x) в 4^5 раз). Из табл. 3.5 видно, что такое увеличение сложности имеет место для схем dk17,dk48,newpla,newcwp, sex, mp2d, shift и t4. Поэтому представляет интерес разработка такой стандартной структуры системы функционального контроля, которая в таких случаях обеспечивает уменьшение аппаратурной избыточности, но в то же время обладает лучшими характеристиками по обнаружению чем стандартная система, основанная на коде паритета.

В первой главе диссертации упоминается понятие об оптимальном коде с суммированием. Информационные векторы такого (т,£)-кода равномерно распределены между контрольными векторами, в результате чего он не обнаруживает минимальное общее количество ошибок в информационных векторах. Классический код Бергера и его модификации не являются оптимальными [33, 53, 60, 114]. Применяя принцип взвешивания переходов между разрядами, занимающими соседние позиции в информационных векторах, можно строить оптимальные коды с суммированием.

WT(m, к, wie2l)-код может быть преобразован в оптимальный код [54].

Алгоритм 3.1. Построение оптимального кода с суммированием.

1. Каждому переходу между разрядами, занимающими соседние позиции в информационном векторе, присваивается весовой коэффициент

Щ = 2, (3.4)

где i = 0,1,2,..., (т — 1) - номер позиции разряда в информационном

векторе.

2. Вводится функция активизации перехода

ti = fiBfi+i. (3.5)

3. Определяется число W, равное сумме весовых коэффициентов активизи-

*

рованных переходов w*:

w = Ж-1™; = ir=r01ti 2. (3.6)

4. Устанавливается модуль М = 2к-1, где к = \1од2(т +1)1.

5. Определяется наименьший неотрицательный вычет числа W по модулю М: число W (mod М).

6. Для каждого информационного вектора подсчитывается поправочный коэффициент а как сумма по модулю два (т — к) старших информационных разрядов

а = fm@fm-1© ■■■ ®fk+1. (3.7)

7. Определяется модифицированный вес информационного вектора:

V = W( mod М) + аМ. (3.8)

8. Число V представляется в двоичном виде и записывается в разряды контрольного вектора.

Код, построенный по алгоритму 3.1 обозначим как RWT(m,k,Wie2l). В таблице 3.6 для примера представлен RWT(4,3, Ш;в2')-код.

В приложении А приведены характеристики RWT(m, к, Ш;б2')-кодов по обнаружению ошибок в информационных векторах для значений т = 5 + 10.

Из табл. 3.6 следует, что все 2т = 24 = 16 информационных векторов ЯШТ(4,3,Ш1б21)-кода равномерно распределены между всеми 2k = 23 = 8 контрольными векторами, что является признаком оптимального кода [60]. При этом одному контрольному вектору соответствует по два информационных вектора с расстоянием Хэмминга, равным d = 3. Таким образом, ЯШТ(4,3,Ш1б21)-код не обнаруживает 16 трехкратных ошибок в информационных векторах. Для сравнения 5 (4,3)-код не обнаруживает 48 двукратных и 6 четырехкратных ошибок в информационных векторах, что в 3,375 раза больше, чем ЯШТ(4,3,Ш1б21)-код [55].

# Разряды информационного вектора 2а РаЪ 2а(той4) [!а(той4)]2 а V Разряды контрольного вектора

9з 92 31

ь Гз Г2

0 0 0 0 0 0 000 0 00 0 0 0 0 0

1 0 0 0 1 1 001 1 01 0 1 0 0 1

2 0 0 1 0 3 011 3 11 0 3 0 1 1

3 0 0 1 1 2 010 2 10 0 2 0 1 0

4 0 1 0 0 6 110 2 10 0 2 0 1 0

5 0 1 0 1 7 111 3 11 0 3 0 1 1

6 0 1 1 0 5 101 1 01 0 1 0 0 1

7 0 1 1 1 4 100 0 00 0 0 0 0 0

8 1 0 0 0 4 100 0 00 1 0 1 0 0

9 1 0 0 1 5 101 1 01 1 1 1 0 1

10 1 0 1 0 7 111 3 11 1 3 1 1 1

11 1 0 1 1 6 110 2 10 1 2 1 1 0

12 1 1 0 0 2 010 2 10 1 2 1 1 0

13 1 1 0 1 3 011 3 11 1 3 1 1 1

14 1 1 1 0 1 001 1 01 1 1 1 0 1

15 1 1 1 1 0 000 0 00 1 0 1 0 0

Определим, что повлияло на характеристики обнаружения ошибок кодами при их модификации.

Теорема 3.1. ЯШТ(т, к^1б21) - код, реализованный в соответствии с алгоритмом 3.1, является оптимальным.

Доказательство. Заметим, что при получении суммарного веса активизированных переходов используется линейная функция (3.4). Для формирования веса активизированного перехода значение весового коэффициента /-го разряда умножается на функцию активизации, другими словами, в /-й разряд двоичного числа, соответствующего весу перехода, записывается 0 или 1, а все остальные

разряды заполняются нулями. Таким образом, двоичное число, соответствующее весу активизированного перехода, [wi]2 = А =< aiai-1... а1 >:Л=<00...0> либо А =< 10 .0 >. При получении суммарного веса активизированных переходов в двоичном представлении числа [lj2 =< WiWt-1... w1 > единицами заполняются только те разряды, которые соответствуют весовым коэффициентам активизированных переходов. Так как значения весовых коэффициентов выбираются из ряда {1; 2; 4;...; 2т-1}, все возможные комбинации сумм весовых коэффициентов не повторяются и образуют ряд чисел: Та = {0; 1; 2;...; 2т — 1}. Учитывая (3.6) и свойства функции сложения по модулю два (при ft = 1,fi+1 = 0 имеем tt = 1©0 = 1, и при ft = 0,fi+1 = 1 имеем ti = 0©1 = 1), получаем, что каждое число Та при выполнении п. 3 алгоритма 3.1 повторяется дважды. При этом значения Та будут одинаковыми для противоположных наборов с инверсными значениями одноименных разрядов (такие наборы расположены симметрично относительно середины таблицы истинности (см. табл. 3.6)). С увеличением на единицу номеров двоичных наборов < f1f2 ...fm > в двоичных представлениях соответствующих чисел [za]2 =< wiwi-1 ... w1 > меняется значение ровно одного разряда. Отсюда непосредственно следует, что функция вычисления контрольных разрядов контрольного вектора являются линейными уже на этапе выполнения п. 3 алгоритма 3.1.

На следующем этапе построения кода определяются наименьшие неотрицательные вычеты суммарных весов информационных векторов по модулю М = 2к-1, где к = \1од2(т + 1)1. Это соответствует операции отбрасывания старшего разряда числа [1а]2. Другими словами, числа Ia(mod М) =< wi—1wi—2 ..w1 > меняется значение только одного разряда.

Модифицированный вес V =< a wi-1wi-2 ...w1 >, старший разряд которого вычисляется по линейной функции (3.8). Таким образом, функции вычисления разрядов контрольных векторов RWT(m, к, we21)--кода являются линейными:

Зк = а = !т©1т-1© — ©!к+1 9к-1 = Гк-1 еГк

... (3.9)

91 = л ш

Учитывая тот факт, что функция сложения по модулю два -го количества переменных Д©^© ...©^ при формировании всех наборов < ^^ > ровно на половине из них принимает значение 0 и ровно на половине из них - значение 1, можно заключить, что все информационные векторы ЯШТ(т,к^1б21) - кода распределены равномерно между всеми 2к контрольными векторами. Это и есть признак того, что ЯШТ(т, к, wie2l)-код является оптимальным.

Теорема доказана.

На рис. 3.2 изображена структура системы функционального контроля, организованная по оптимальному ЯШТ(т, к^1е21)-коду. Она, также как и структуры, изображенные на рис. 1.5 и рис. 1.6, является стандартной, где генератор контрольных разрядов вычисляет стандартные функции вида (3.9).

Сравним между собой структуры систем функционального контроля по паритету и по ЯШТ(т, к, wi62l) - коду.

Следует заметить, что генератор ЯШТ(т,к^1б21) - кода всегда имеет более простую структуру, чем генератор кода паритета, что следует из способа построения генераторов обоих кодов. Известно, что для реализации функции паритета требуется т — 1 сумматоров по модулю два (рисунок 3.3). При реализации генератора ЯШТ(т, к, wie2l) - кода вычисляется система к = \1од2(т + 1)] контрольных функций, такая, что т — к информационных разрядов входят в одну функцию паритета, а к информационных разрядов с использованием к — 1 сумматоров по модулю определяют значения к — 1 контрольных функций g'2, ..., (рис. 3.3). Для реализации первой требуется т — к — 1 сумматоров по модулю два, а для реализации второй - к — 1 сумматоров по модулю два, что в сумме

равно: т — к — 1 + к — 1 = т — 2, что на единицу меньше чем требуется для по-

строения генератора кода паритета.

Рабочие

Xl X2

выходы

.-Л-.

Контрольные выходы

Рисунок 3.3. Структура системы функционального контроля на основе оптимального

КШТ(т, к, Wle2l)-кода

х

Несмотря на отмеченное преимущество ЯШТ(т,к^1е21) - кода перед кодом паритета, структура функционального контроля, организованная с его использованием, оказывается сложнее в технической реализации, чем структура контроля по методу паритета, так как требует наличия блока контрольной логики с большим количеством выходов и компаратора для сравнения парафазных сигналов д^д2,-,дк и я'к-1.

В табл. 3.7 приведены экспериментальные результаты сравнения по сложности систем функционального контроля на основе кодов ЯШТ(т, к^1б21) и паритета. В среднем площадь системы, организованной по ЯШТ(т,к^1е21)-коду, составляет 125,161% от площади системы контроля по паритету. Однако можно выделить несколько схем, для которых применение при организации контроля

RWT(m, к, wie2l)-K0^a дало существенное уменьшение площади - например, для контрольной схемы int8 получена площадь системы контроля в 58,587% от площади системы контроля по паритету.

В табл. 3.8 приведены площади систем функционального контроля для указанных выше контрольных схем, для которых системы дублирования оказались наиболее сложными. Для пяти из шести схем (кроме схемы shift) применение системы контроля на основе RWT(m, к, wie2l)-кода по сравнению с системами дублирования дает значительное уменьшение сложности.

Сравним по показателю сложности систем функционального контроля на основе RWT(m, к, wie2l)-кода с системами контроля на основе классического кода Бергера. Результаты соответствующих экспериментов приведены в табл. 3.9. Для большинства схем достигнуто уменьшение площади по сравнению с применением кода Бергера. Результаты соответствующих экспериментов приведены в табл. 3.9. Для большинства схем достигнуто уменьшение площади по сравнению с применением кода Бергера.

Лучший результат получен для схемы shift (13,38% от площади системы контроля на основе кода Бергера), худший - небольшое превышение сложности новой структуры - для схемы тах1024 (100,861%). Среднее значение отношения площадей систем функционального контроля, построенных на основе S(m, к) и RWT(m,k,wie2l) кодов, составило 53,436%. Значительное улучшение показателя сложности технической реализации достигается, за счет применения простых выражений, описывающих функции контрольных разрядов RWT(m, к, wt€2l) - кода.

функционального контроля на основе оптимального кода и кода паритета

# Контрольная схема Входы/выходы Площадь системы функционального контроля Отношение площадей систем контроля на основе RWT(m,k,wie2i) -кода и паритета, %

F(x) Система контроля на основе RWT(m,k, ы^) -кода Система контроля по паритету

1 apla 10/12 3048 7392 4624 159,86

2 b2 16/17 40952 53992 44868 120,34

3 b12 15/9 1848 5600 5544 101,01

4 br2 12/8 2952 5392 3792 142,19

5 dist 8/5 6968 11656 9888 117,88

6 dk17 10/11 1768 5024 2920 172,05

7 dk48 15/17 1808 6112 5920 103,24

8 in1 16/17 40952 53992 44864 120,35

9 intb 15/7 22248 43584 73144 59,59

10 m1 6/12 3064 5248 3816 137,53

11 m2 8/16 10096 14208 11448 124,11

12 m3 8/16 13464 18504 15208 121,67

13 m4 8/16 18704 25128 21072 119,25

14 max512 9/6 9632 15232 12400 122,84

15 max1024 10/6 17816 27816 22920 121,36

16 mp2d 14/14 2568 4568 6256 73,02

17 newapla 12/10 1192 3728 2072 179,92

18 newcpla2 7/10 1896 3984 2712 146,9

19 newcwp 4/5 440 1392 800 174

20 newtpla2 10/4 840 3984 2712 146,9

21 root 8/5 3496 5736 4776 120,1

22 sex 9/14 1360 2648 3056 86,65

23 shift 19/16 3728 23392 24728 94,6

24 t4 12/8 1080 3688 2800 131,71

25 tms 8/16 6784 10376 7864 131,94

Среднее значение 125,16

Контрольная схема Площадь схемы в условных единицах

F(x) Система дублирования Система «почти дублирование» Система на основе RWT(m,k, Ю1б21) -кода

dk17 1768 6680 7728 5024

dk48 1808 8632 10192 6112

newapla 1192 5216 6304 3728

mp2d 2568 9216 11528 4568

sex 1360 6800 7856 2648

shift 3728 12160 15520 23392

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

Для 14 из 15 рассмотренных в табл. 3.9 контрольных схем площадь системы функционального контроля составила менее 200%, а для 5 - даже менее 150%, что говорит об эффективности ЯШТ(т,к^1б21) -кода при организации контроля. Далее рассмотрим вопрос об обнаруживающей способности систем функционального контроля.

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

по новым стандартным структурам в сравнении с системами контроля по коду Бергера

№ Название схемы Входы/выходы Площадь схем в условных единицах Отношение площадей систем функционального контроля и контролируемых схем в % Отношение площадей систем контроля на основе ЯШТ(т, к, ы^Укода и £(га,£)-кода, % Отношение площадей системы контроля на основе ЯШТ(т, к, ы^Укода и системы дублирования, %

F(x) Система контроля на основе £(га,£)-кода Система контроля на основе ПШТ(т,к,ще21)-кода Система контроля на основе £(га,£)-кода Система контроля на основе ПШТ(т,к,ще21)-кода

1 apla 10/12 3048 14936 7392 499,475 251,969 50,447 80,402

2 b2 16/17 40952 75224 53992 184,391 132,545 71,883 62,448

3 b12 15/9 1848 13952 5600 770,563 318,615 41,348 94,723

4 br2 12/8 2952 8280 5392 290,244 192,412 66,293 70,02

5 dist 8/5 6968 13264 11656 194,489 171,412 88,135 78,538

6 dk17 10/11 1768 21904 5024 1255,204 300,452 23,937 79,521

7 dk48 15/17 1808 38888 6112 2166,814 353,982 16,337 74,143

8 in1 16/17 40952 75224 53992 184,391 132,545 71,883 62,448

9 intb 15/7 22248 114224 43584 514,707 197,195 38,312 94,568

10 m1 6/12 3064 13416 5248 447,258 180,679 40,397 57,763

11 m2 8/16 10096 30232 14208 302,298 143,582 47,497 58,226

12 m3 8/16 13464 34232 18504 256,387 139,572 54,438 59,408

13 m4 8/16 18704 40400 25128 217,536 135,885 62,466 60,353

14 max512 9/6 9632 15680 15232 165,781 161,13 97,194 74,444

15 max1024 10/6 17816 27576 27816 156,399 157,746 100,861 75,516

16 mp2d 14/14 2568 20032 4568 791,277 189,097 23,898 52,691

17 newapla 12/10 1192 10544 3728 908,725 336,913 37,075 76,994

18 newcpla2 7/10 1896 11032 3984 597,046 225,316 37,739 64,493

19 newcwp 4/5 440 2136 1392 550,909 381,818 69,307 78,067

20 newtpla2 10/4 840 2224 2016 299,048 274,286 91,72 87,273

21 root 8/5 3496 6384 5736 190,847 172,311 90,288 72,894

22 sex 9/14 1360 17072 2648 1276,471 215,882 16,912 43,176

23 shift 19/16 3728 176688 23392 4747,21 635,193 13,38 194,737

24 t4 12/8 1080 8648 3688 827,407 368,148 44,494 91,026

25 tms 8/16 6784 26600 10376 396,344 157,193 39,661 58,363

Средние значения 727,649 237,035 53,436 76,089

Теорема 3.2. В системе функционального контроля по ЯШТ(т,к^1б21)-коду всегда обнаруживается большее количество ошибок в контрольной схеме, чем в системе функционального контроля по коду паритета.

Доказательство. Действительно, поскольку ЯШТ(т,к^1б21) - код и код паритета являются оптимальными, то количество необнаруживаемых ошибок в них вычисляется по формуле [60]:

Ыт = 2т(2т-к - 1), (3.10)

где к = 1 для кода паритета и к = \1од2(т+ 1)] для ЯШТ(т,к,Ш1б21) -

кода.

Результаты расчетов количества необнаруживаемых рассматриваемыми кодами ошибок приведены в табл. 3.10.

Для сравнения ЯШТ(т,к^1е21)-кода с кодом паритета введем специальный коэффициент эффективности обнаружения ошибок:

РагИу ^тг^т—! ^т—1 ^

г _ "т_ _ 2 (2 -1) _ 2 -1 (3 11")

™т

который показывает, во сколько раз код паритета не обнаруживает ошибок больше, чем ЯШТ(т, к, Ш;в2')-код.

Преобразуем выражение (3.12):

2\1од2(т+1)]—1__1_

Я _ 2 -1 —_2т—\1°32(т+1)] _ ?\1оа2(т+1)]-1

°т 2т—\1од2(т+1)]-1 , 1 ~2 . (312)

I — —

2т—\1од2(т+1)]

Таким образом, новым кодом обнаруживается примерно в 2\1од2(т+1)]-1 больше ошибок, чем кодом паритета.

Теорема доказана.

Из табл. 3.10 следует, что при т> 10 значение величины 8т достаточно точно можно аппроксимировать величиной 2\1о92(т+1^-1. Таким образом, ЯШТ(т,к,ше21)-код не обнаруживает примерно в 2^1од2(т+1^^-1 меньше ошибок в информационных векторах, чем код паритета.

Подобное свойство является несомненным преимуществом нового оптимального кода.

т Количество необнаруживаемых ошибок, Ыт 8т

Код паритета RWT(m,k,wie2i)-код

2 4 0 -

3 24 8 3

4 112 16 7

5 480 96 5

6 1984 448 4,429

7 8064 1920 4,2

8 32512 3840 8,467

9 130560 15872 8,226

10 523264 64512 8,111