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

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

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

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

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

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

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

Императора Александра 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. Значения доли необнаруживаемых ошибок от общего их количества

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