Автоматика и телемеханика, № 8, 2014
Логическое управление
© 2014 г. А.А. БЛЮДОВ, канд. техн. наук (tosha_super@mail.ru), Д.В. ЕФАНОВ, канд. техн. наук (TrES-4b@yandex.ru), В.В. САПОЖНИКОВ, д-р техн. наук (kat@pgups.edu), Вл.В. САПОЖНИКОВ, д-р техн. наук (kat@pgups.edu) (Петербургский государственный университет путей сообщения, Санкт-Петербург)
О КОДАХ С СУММИРОВАНИЕМ ЕДИНИЧНЫХ РАЗРЯДОВ В СИСТЕМАХ ФУНКЦИОНАЛЬНОГО КОНТРОЛЯ
Рассмотрено полное множество кодов с суммированием единичных разрядов, используемых при организации систем функционального контроля комбинационных логических устройств. Предложены новые модифицированные коды, а также установлены их свойства по обнаружению ошибок в информационных разрядах. Дана классификация кодов.
1. Введение
Для контроля правильности вычисления функций комбинационными логическими устройствами используются системы функционального диагностирования [1—5]. В подобной системе исходная комбинационная схема /(х), реализующая ряд рабочих булевых функций, снабжается дополнительным блоком д(х), формирующим некоторое множество контрольных функций (рис. 1). Таким образом, выходы обоих блоков /(х) и д(х) можно сопоставить с вектором некоторого, заранее выбранного помехоустойчивого кода. Тогда функции /\(х), /2(ж), ..., /т(х) определяют значения разрядов информационного вектора кода длины т, а функции д^х), д2(х), ..., д^ (х) - значения разрядов контрольного вектора длины к. Факт принадлежности формируемого кодового вектора выбранному коду определяется самопроверяемой схемой тестера. В этом случае на выходах тестера вырабатывается парафазный сигнал <10> или <01>. При наличии внутренних ошибок в схеме тестера или же при несоответствии контрольной и информационной составляющих кодового вектора парафазность нарушается [6].
Подобный вариант организации контроля комбинационных логических устройств получил название метода вычисления контрольных разрядов. Он применим при использовании любого разделимого кода. Но наиболее эффективным техническим решением является применение свойств кодов с суммированием единичных разрядов. В случае применения неразделимых кодов используется структура логического дополнения, описанная в [7].
5* 131
Контрольные разряды Рис. 1. Система функционального контроля.
Кодовые векторы кодов с суммированием единичных разрядов или (п, т)-кодов образуются при дополнении информационного вектора длины т контрольным вектором длины к (к = п — т), содержащим двоичное число, полученное путем вычислений сумм единичных информационных разрядов. Наиболее простым вариантом является использование классических кодов с суммированием (кодов Бергера, 5(п, т)-кодов) [8]. В таких кодах контрольные разряды принимают значения, равные двоичному числу, характеризующему сумму единичных разрядов информационных векторов кода [9, 10].
В настоящей статье рассматриваются не только классические 5 (п, т)-ко-ды, но и коды с суммированием, полученные с использованием модульного принципа подсчета числа единиц в информационных векторах, а также полное множество их модификаций. Проводится сравнение кодов по эффективности обнаружения искажений в информационных векторах, что актуально для систем функционального контроля, ввиду раздельной реализации структуры, изображенной на рис. 1. В ней невозможно одновременное возникновение искажений в обоих вычислительных блоках, так как одновременное появление двух и более не зависимых друг от друга неисправностей микроэлектронной аппаратуры является событием маловероятным; а любой одиночный отказ в системе функционального контроля не может привести к искажению выходов обоих блоков в силу того, что они реализованы раздельно.
2. Коды с суммированием единичных разрядов и оптимальные коды
Правила вычисления контрольных разрядов выбранного (п, т)-кода однозначно определяют его свойства по обнаружению искажений в информационных разрядах. Ошибка в информационном векторе (п, т)-кода будет необ-наруживаемой тогда и только тогда, когда она переведет данный информа-
Группы контрольных векторов
000 001 010 011 100 101
00000 00001 00011 00111 01111 11111
00010 00101 01011 10111
00100 00110 01101 11011
01000 01001 01110 11101
10000 01010 10011 11110
01100 10101
10001 10110
10010 11001
10100 11010
11000 11100
ционный вектор в другой информационный вектор с аналогичным контрольным словом. Исходя из этого, любой код с суммированием может быть представлен как совокупность групп информационных векторов с одинаковыми контрольными векторами. Например, в табл. 1 представлено разбиение информационных векторов на контрольные группы для кода Бергера £(8,5). Информационным векторам с одинаковым весом г соответствует одна и та же контрольная группа. Число необнаруживаемых искажений (характеристика свойств кода по обнаружению ошибок в информационных разрядах) может быть получено путем суммирования всех возможных переходов внутри всех контрольных групп.
В общем случае, так как в каждой контрольной группе веса г расположено ровно по Ст информационных векторов, а число переходов векторов внутри группы равно Ст(С^ — 1), суммарное число необнаруживаемых ошибок вычисляется по формуле
т
(1) = £ С^ (С^ — 1).
г=о
Для кода £(8,5) подсчет по формуле (1) дает следующее число:
N5 = СО (С5° — 1) + С1 (С1 — 1) + ... + С55 (С55 — 1) = = 1 ■ 0 + 5 ■ 4 + 10 ■ 9 + 10 ■ 9 + 5 ■ 4 + 1 ■ 0 = = 0 + 20 + 90 + 90 + 20 + 0 = 220.
Общее же количество искажений в информационных разрядах £(п, т)-ко-да равно
(2) N = 2т (2т — 1).
Для кода £(8,5)-кода это число равно N = 25(25 — 1) = 32 ■ 31 = 992.
£(п,т)-коды обладают важным свойством [11]: для любого кода Бергера доля необнаруживаемых ошибок в информационных разрядах кратности ^ от общего числа ошибок информационных разрядов данной кратности не за-
висит от числа информационных разрядов и является постоянной величиной:
(3) Д* = 2~ас].
5(п, т)-коды обладают весьма низкой эффективностью обнаружения ошибок в области малой кратности: ими не обнаруживается 50% двукратных искажений и 37,5% четырехкратных искажений.
В целом свойство по обнаружению ошибок любого кода с суммированием можно характеризовать коэффициентом 7, равным отношению числа необ-наруживаемых искажений информационных разрядов к общему числу искажений информационных разрядов. Для кодов Бергера эта величина может быть рассчитана по формуле
дт ст (Ст — 1)
/ л \ 1т Г=0
(4) 7
N 2т (2т - 1)
т
Классические коды с суммированием имеют сравнительно высокое значение величины 7 [11]. В рассмотренном примере кода Б(8,5) 7 = 0,22177, т.е. данный код не обнаруживает 22,177% искажений в информационных векторах.
Сравнительно высокое значение 7 в области искажений информационных разрядов у кода Бергера объясняется неравномерностью распределения информационных векторов по группам контрольных векторов (см. табл. 1). Если распределить все информационные векторы в контрольные группы равномерно, то получим код, имеющий минимальное число необнаружива-емых ошибок информационных разрядов, т.е. некоторый оптимальный код (0(п, т)-код) в смысле обнаружения ошибок в информационных разрядах при заданных т и к. Число необнаруживаемых искажений в информационных разрядах оптимальных кодов можно подсчитать по формуле [12]
(5)
= 2т 2т-к — 1
К примеру, для 0(8,5)кода число необнаруживаемых ошибок равно 1™п = 25(25-3 — 1) = 96, что в 2,29 раза меньше, чем у рассмотренного выше Б(8,5)-кода.
Так как при заданных т и к имеется конкретный оптимальный код, то удобно число необнаруживаемых искажений информационных векторов кодов сравнивать с числом необнаруживаемых искажений в оптимальных кодах. Более того, можно ввести относительную величину, равную отношению числа необнаруживаемых ошибок в 0(п, т)-коде к числу необнаруживаемых ошибок 1т,к в данном (п, т)-коде:
(6) е =
1ГП
N
т,к
Величину £ назовем коэффициентом эффективности кодов с суммированием. Чем ближе £ к единице, тем ближе код с суммированием к оптимальному коду. Код Б(8,5) имеет эффективность, равную £ = 0,43636.
3. Модульно модифицированные коды с суммированием единичных разрядов
Классические коды с суммированием обладают низким значением эффективности обнаружения ошибок информационных разрядов. Эту характеристику можно повысить, не увеличивая при этом число контрольных разрядов, за счет модификации кода по следующему алгоритму [13]:
1. Подсчитывается вес информационного вектора г.
2. Выбирается модуль М € 21, 22,..., 2 Г1оез (т+1)1-1 (где запись \Ь"| обозначает целое сверху от Ь).
3. Вес г берется по выбранному модулю Ш = (г)шоё М.
4. Подсчитывается специальный поправочный коэффициент а как сумма по модулю двух заранее выбранных информационных разрядов.
5. Подсчитывается результирующий вес информационного слова V = = Ш + аМ.
Коды, полученные по приведенному алгоритму, обозначим как КБИ (п, т)-коды.
В [13] предложено выбирать а по следующей формуле: а = хт ф хт-1 ф ... ф хд+ь Однако а может содержать любое количество информационных разрядов от 1 до т — 1 К примеру, в табл. 2 даны несколько векторов, принадлежащих КБ4(8,5)-коду, в котором поправочный коэффициент вычисляется как а = х5 ф х4 ф х3.
Из табл. 2 видно, что вес V совпадает по четности с обычным весом информационного вектора г. Поэтому в контрольные группы КБИ(п,т)-кодов попадают информационные векторы с различным числом единичных разрядов, но одинаковым по четности. Подобное свойство обеспечивает сохранение основной особенности Б(п, т)-кода - возможности обнаружения всех ошибок нечетной кратности. Из табл. 2, например, следует, что векторы <01010> и <11000>, имеющие одинаковый вес, располагаются в КБ4(8,5)-коде с а = = х5 ф х4 ф х3 в разных контрольных группах, так как имеют разный результирующий вес V. С другой стороны, векторы <00000> и <10111>, имеющие
Таблица 2. Некоторые векторы КБ4(8,5)-кодa (а = х5 ф х4 ф х3)
Информационные разряды г \¥ а V Контрольные разряды
х5 Х4 х-з Х2 Х\ Уз У2 У1
0 0 0 0 0 0 0 0 0 0 0 0
0 1 0 0 0 1 1 1 5 1 0 1
0 1 0 1 0 2 2 1 6 1 1 0
1 0 1 1 1 4 0 0 0 0 0 0
1 1 0 0 0 2 2 0 2 0 1 0
1 1 1 1 1 5 1 1
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.