Двухмодульный код с суммированием

ДВУХМОДУЛЬНЫЙ КОД С СУММИРОВАНИЕМ

ЕДИНИЧНЫХ ИНФОРМАЦИОННЫХ РАЗРЯДОВ ПО МОДУЛЮ

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

Д. В. Ефанов, В. А. Щагина

Кафедра «Автоматика и телемеханика на железных дорогах»

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

Императора Александра 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. Для данной длины информационного вектора осуществляется выделение двух подмножеств разрядов информационных векторов D₁ и D₂:

и

где запись обозначает целое снизу от вычисляемого значения.

2. Каждому из подмножеств D₁ и D₂ ставится в соответствие свой информационный вектор <D₁> и <D₂>.

3. Для каждого из векторов <D₁> и <D₂> определяются значения наименьших неотрицательных вычетов их весов по модулю M=4 – числа r₁(mod4) и r₂(mod4).

4. Числа r₁(mod4) и r₂(mod4) представляются в двоичном виде и записываются в младшие и старшие разряды контрольных векторов соответственно.

Обозначим код, строящийся по данному алгоритму, как TM(m,k)-код (two-modulus code). Правила его построения иллюстрируются рисунком 1.

TM(m,k)-код всегда будет иметь 4 контрольных разряда и может быть сравним с классическим и модифицированным кодами Бергера при длинах информационных векторов m=8÷15. На данных длинах информационных векторов описываемый код будет иметь существенное преимущество в обнаруживающей способности перед классическими и модифицированными кодами Бергера (рис. 2).

Рис. 1. Принцип построения двухмодульного кода с суммированием

Рис. 2. Значения доли необнаруживаемых ошибок от общего их количества

в зависимости от длины информационного вектора