Двухмодульный код с суммированием
ДВУХМОДУЛЬНЫЙ КОД С СУММИРОВАНИЕМ
ЕДИНИЧНЫХ ИНФОРМАЦИОННЫХ РАЗРЯДОВ ПО МОДУЛЮ
ЧЕТЫРЕ В СИСТЕМАХ ФУНКЦИОНАЛЬНОГО КОНТРОЛЯ
Д. В. Ефанов, В. А. Щагина
Кафедра «Автоматика и телемеханика на железных дорогах»
Петербургского государственного университета путей сообщения
Императора Александра I
Анализируются свойства двухмодульных кодов с суммированием единичных информационных разрядов с установленными значениями модулей M=4 в системах функционального контроля комбинационных логических схем. Приводятся результаты сравнения двухмодульных кодов с известными классическими и модифицированными кодами Бергера, часто применяемыми при организации систем функционального контроля.
Ключевые слова: система функционального контроля; обнаружение ошибок; код Бергера; модифицированный код Бергера; двухмодульный код с суммированием; свойства обнаружения ошибок; структурная избыточность.
Введение
При организации надежных дискретных устройств автоматики и вычислительной техники часто используют самопроверяемые схемы встроенного контроля, или системы функционального контроля [1 – 3]. Одним из способов их построения является использование помехоустойчивых кодов с небольшой избыточностью и простыми правилами построения, как правило, реализующими принципы обнаружения отказов [4, 5]. Часто при решении таких задач используются классические и модифицированные коды с суммированием [6 – 9].
Классические коды с суммированием, или коды Бергера [10], строятся путем записи в разряды контрольного вектора двоичного эквивалента десятичного числа, равного сумме единичных разрядов в информационном векторе (равного весу r информационного вектора). Обозначим их как S(m,k)-коды, где m и k – длины информационных и контрольных векторов соответственно. Такие правила построения кода предполагают наличие одного и того же контрольного вектора у информационных векторов (m – длина информационного вектора). В зависимости от значения r количество информационных векторов с одинаковыми контрольными векторами варьируется и является минимальным при r=0 или r=m и максимальным – для значений r, близких к величине
. Неравномерность распределения информационных векторов между контрольными определяет высокое количество необнаруживаемых кодом Бергера ошибок, в том числе, в области ошибок малых кратностей: к примеру, ими не обнаруживается 50% двукратных и 37,5% четырехкратных ошибок в информационных векторах [11]. Кроме того, поскольку
, для всех кодов Бергера с длинами информационных векторов
i=1,2,… невозможно формирование полного множества контрольных векторов. Это является проблемой при решении задачи обеспечения свойства полной самопроверяемости структуры генератора тестера кода в системах функционального контроля [12].
Для повышения эффективности обнаружения ошибок в системах функционального контроля разработаны модифицированные коды Бергера (RS(m,k)-коды), принципы построения которых описаны в [13]. Данные коды обнаруживают гораздо большее количество ошибок, чем коды Бергера, но, к сожалению, не являются кодами с суммированием, максимально близкими к кодам с наименьшим значением общего числа необнаруживаемых ошибок при своих значениях длин информационных и контрольных векторов.
В данной работе мы покажем, что может быть построен код с суммированием единичных информационных разрядов с улучшенными по сравнению с классическими и модифицированными кодами Бергера свойствами.
Двухмодульный код с суммированием
Способ построения кода основывается на использовании следующего алгоритма:
1. Для данной длины информационного вектора осуществляется выделение двух подмножеств разрядов информационных векторов D1 и D2:
и
где запись обозначает целое снизу от вычисляемого значения.
2. Каждому из подмножеств D1 и D2 ставится в соответствие свой информационный вектор <D1> и <D2>.
3. Для каждого из векторов <D1> и <D2> определяются значения наименьших неотрицательных вычетов их весов по модулю M=4 – числа r1(mod4) и r2(mod4).
4. Числа r1(mod4) и r2(mod4) представляются в двоичном виде и записываются в младшие и старшие разряды контрольных векторов соответственно.
Обозначим код, строящийся по данному алгоритму, как TM(m,k)-код (two-modulus code). Правила его построения иллюстрируются рисунком 1.
TM(m,k)-код всегда будет иметь 4 контрольных разряда и может быть сравним с классическим и модифицированным кодами Бергера при длинах информационных векторов m=8÷15. На данных длинах информационных векторов описываемый код будет иметь существенное преимущество в обнаруживающей способности перед классическими и модифицированными кодами Бергера (рис. 2).
Рис. 1. Принцип построения двухмодульного кода с суммированием
Рис. 2. Значения доли необнаруживаемых ошибок от общего их количества
в зависимости от длины информационного вектора