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

Размещено на http://www.allbest.ru

Российский университет транспорта «МИИТ»

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

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

Д.В. Ефанов, д-р техн. наук Р.Б. Абдуллаев

Анализируются полиномиальные коды и их особенности, связанные с обнаружением ошибок в информационных векторах. Установлены образующие полиномы, которые позволяют строить полиномиальные коды, обладающие свойством обнаружения любых симметричных и асимметричных искажений в информационных векторах. Приведены результаты экспериментов с комбинационными схемами из набора LGSynth' 89, подтверждающие теоретические результаты. Использование полиномиальных кодов с установленными свойствами позволяет учитывать их при синтезе контролепригодных дискретных систем и их диагностического обеспечения.

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

Введение

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

Минимизация габаритов, уплотнение размещения единиц на одном кристалле, многослойные технологии размещения объектов - все эти этапы в эволюции техники влекут за собой трудности в обеспечении надежного и безопасного функционирования конечных систем. На ведущие роли в процессе эффективной эксплуатации современных систем выходят методы и средства технического диагностирования и мониторинга состояния блоков и узлов, а также обеспечения отказоустойчивой работы компонентов [1 - 3].

Важнейшим средством обеспечения высоких показателей надежности и эффективности использования современной техники является помехоустойчивое кодирование информации на всех уровнях ее реализации [4, 5]. Принципы помехоустойчивого кодирования используются при внесении аппаратной избыточности в архитектуру управляющих систем при выборе способов резервирования компонентов, они же применяются при защите и обработке управляющей информации и, в конечном итоге, определяют эффективность реализации технологических процессов [6]. Специфика решаемой задачи по построению высоконадежного технического объекта и выбранный способ кодирования определяют все ключевые характеристики конечного устройства. В некоторых задачах важны свойства коррекции ошибок (например, при передаче данных на расстояния), а в некоторых - свойства обнаружения ошибок (например, в аппаратных реализациях устройств для исключения накопления неисправностей) [7].

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

1. Постановка задачи

помехоустойчивый кодирование полиномиальный надежность

В задачах синтеза контролепригодных дискретных систем и их диагностического обеспечения применяют разнообразные разделимые двоичные коды, в том числе полиномиальные коды. Эти коды обладают разнообразными характеристиками обнаружения ошибок по их видам и кратностям [8, 9]. В данной статье приводится решение задачи поиска таких полиномов, которые дают возможность построения кода со свойствами обнаружения отдельных подклассов ошибок в информационных векторах - симметричных и асимметричных ошибок [10]. Особые типы полиномиальных кодов могут быть использованы при выборе способов построения дискретных систем с обнаружением неисправностей.

2. Коды с обнаружением различных видов ошибок

Свойства обнаружения ошибок различных видов часто используют при реализации технических средств диагностирования и построении систем с контролепригодными архитектурами [11 - 14]. В этом плане широко распространены классические равновесные коды и коды Бергера, обладающие свойством обнаружения любых однонаправленных, или монотонных проявлений искажений [15]. К монотонным относятся такие ошибки в кодовых словах (или отдельно информационных векторах), которые возникают при наличии искажений только нулевых или только единичных разрядов. Все остальные ошибки являются немонотонными. Во множестве немонотонных ошибок выделяются симметричные и асимметричные ошибки. Симметричные ошибки возникают при одинаковом числе искажений нулевых и единичных разрядов, асимметричные - при различном числе таких искажений. В [10] показано, что с увеличением значения кратности ошибки доля монотонных ошибок от общего их числа постепенно уменьшается, а асимметричных - увеличивается. Доля симметричных ошибок с увеличением кратности d уменьшается, но не так стремительно, как монотонных. Эти особенности можно учитывать в процессе разработки надежных систем с обнаружением неисправностей.

Само по себе выделение симметричных ошибок из множества немонотонных связано с тем, что все подобные ошибки не будут обнаруживаться классическими кодами Бергера и некоторая их часть - равновесными кодами. Остальные же виды ошибок обнаруживаться данными кодами будут. В [16] показано, что для того, чтобы обнаруживались любые симметричные ошибки, какой-либо избыточный код должен обладать высокой избыточностью, не соизмеримой с избыточностью тех же кодов Бергера. Для обнаружения монотонных ошибок (поскольку их доля в общем числе значительно меньше) требуется гораздо меньшая избыточность. Например, коды Бергера имеют

к = [log 2(m +1)"|

контрольных разрядов (здесь m - количество информационных разрядов). Равновесные коды и коды Бергера образуют класс так называемых UAED(m,&)-кодов (unidirectional and asymmetrical error-detection codes). Их можно без специальных ограничений применять, например, при построении внешних схем контроля для логических устройств с такими структурами, на выходах которых возможны лишь монотонные и асимметричные проявления неисправностей. Известны алгоритмы преобразования схем автоматики в схемы данного вида как отдельно с допускаемыми монотонными искажениями [17 - 21], так и с допускаемыми и монотонными и асимметричными искажениями на выходах [22, 23].

При уменьшении избыточности (например, относительно классических кодов Бергера) свойства обнаружения любых монотонных и асимметричных ошибок теряются. Получаемые таким образом коды уже не принадлежат к классу UAED(m,к)-кодов. Однако для многих способов построения кодов могут быть выделены предельные кратности необнаруживаемых монотонных (dU) и асимметричных ошибок (da). Данный класс кодов обозначим как dv,da-UAED(m,k)-коды, где dv и da - те минимальные значения кратностей, при которых возникают необнаруживаемые монотонные и асимметричные ошибки. Примерами dv,da-UAED(m,k)-кодов являются классические и модифицированные коды Боуза - Лина [24]. Для таких кодов значения dv и da зафиксированы, а сами коды являются (M,M+2)-UAED(m,к)-кодами, гдеM- значение модуля подсчета вычетов при формировании кодовых слов.

Однако для некоторых частных случаев возможно построение кодов, обнаруживающих любые симметричные ошибки - так называемых SED(m,k)- кодов (или же da-SED(m,к)-кодов, где da - минимальная кратность необнару- живаемой симметричной ошибки) [16]. Само приложение таких кодов может быть аналогичным приложению UAED(m,k)-кодов, но с контролем устройств по другому свойству - симметричности проявления искажений.

С учетом особенностей приложений кодов при построении систем с обнаружением неисправностей отдельно могут быть выделены также классы кодов с обнаружением любых монотонных и с обнаружением любых асимметричных ошибок - UED(m,k) и AED(m,k) коды (включая du-UED(m,k) и da- AED(m,k) коды). Классификация кодов по свойствам обнаруживаемых ими ошибок различных видов изображена на рисунке.

Полиномиальные коды с обнаружением немонотонных ошибок

Полиномиальные коды широко используются при построении устройств автоматики и вычислительной техники: как при обработке данных, так и при выборе архитектуры управляющего и диагностического обеспечения [25 - 27]. Во многих приложениях данных кодов применяется свойство обнаружения ими ошибок в информационных разрядах. В [8, 9] исследованы общие характеристики обнаружения ошибок в информационных векторах полиномиальными кодами. Дальнейшие исследования показали, что данный класс кодов при определенных образующих полиномах позволяет идентифицировать любые симметричные и асимметричные ошибки. Другими словами, среди множества полиномиальных кодов могут быть выделены классы SED(m,k) и AED(m,k) кодов.

Полиномиальные коды строятся следующим образом:

1. Определяется значение длины информационного вектора т.

2. Выбирается образующий полином б(/) со степенью к = n - m.

3. Каждый информационный вектор записывается в виде полинома M (f ) и умножается на величину fk.

4. Полученный полином fkM(f ) делится на образующий полином G(f ).

5. Полином R(f), соответствующий остатку от деления полинома fkM (f ) на образующий полином G(f ), представляется в виде двоичного числа и записывается в контрольный вектор.

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

В исследовании характеристик полиномиальных кодов были установлены особые виды образующих полиномов, позволяющие получать SED(m,k) и AED(m,k) коды. При этом в ходе анализа все информационные векторы распределялись между контрольными векторами с целью установления видов и кратностей ошибок информационных векторов, при которых не происходит изменения контрольных векторов [28]. Путем такого анализа и были установлены особые виды полиномов, дающие коды с определенными свойствами. Свойство 1. Полиномиальные коды, построенные с помощью образующих полиномов вида:

xk + xk -- + ... + xk-- +... + x1 + x0, (1)

где k = m -1, j є {1;2;...},

j < k, с нечетным количеством членов и при условии k = m -1, обнаруживают любые симметричные ошибки.

Приведем пример полиномиального кода, удовлетворяющего условию (1). Возьмем в качестве образующего полином x3 + x2 + x0. В табл. 1 приведено распределение всех информационных векторов между контрольными векторами для данного кода.

Таблица 1 Контрольные векторы

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

Исследования также показывают, что для каждого конкретного полиномиального кода, являющегося SED(m,к)-кодом, в классе необнаруживаемых ошибок имеются ошибки только одной определенной кратности. Например, для рассматриваемого примера это трехкратные ошибки, которые могут быть монотонными или асимметричными.

Свойство 2. Полиномиальные коды, построенные с помощью образующих полиномов вида:

xk + x\ (2)

где k = m -1,

обнаруживают любые асимметричные ошибки.

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

Таблица 2 Контрольные векторы

В [8, 9] показано, что полиномиальные коды, образующие полиномы которых не содержат свободного члена, не обнаруживают большое количество ошибок, часть из них не является помехоустойчивыми кодами (не обнаруживаются однократные искажения), некоторые контрольные векторы не используются и т.д. Поэтому перспективными для решения задач организации надежных систем автоматики и вычислительной техники являются только полиномиальные коды, образующие полиномы которых свободный член имеют. В табл. 3 перечислены все полиномиальные коды, которые могут быть применены в рассматриваемых задачах, а также отмечены те коды, для которых выполняются условия (1) и (2).

Таблица 3